Remember what branches we delete and do not try to reparent them in cleanup.

git_rebase_update.py

 #!/usr/bin/env python
 # Copyright 2014 The Chromium Authors. All rights reserved.
 # Use of this source code is governed by a BSD-style license that can be
 # found in the LICENSE file.
 
 """
 Tool to update all branches to have the latest changes from their upstreams.
 """
 
 import argparse
@@ skipping 56 matching lines @@
     out, err = git.run_with_stderr('fetch', *fetch_args)
     for data, stream in zip((out, err), (sys.stdout, sys.stderr)):
       if data:
         print >> stream, data
 
 
 def remove_empty_branches(branch_tree):
   tag_set = git.tags()
   ensure_root_checkout = git.once(lambda: git.run('checkout', git.root()))
 
+  deletions = set()
   downstreams = collections.defaultdict(list)
   for branch, parent in git.topo_iter(branch_tree, top_down=False):
     downstreams[parent].append(branch)
 
     if git.hash_one(branch) == git.hash_one(parent):
       ensure_root_checkout()
 
       logging.debug('branch %s merged to %s', branch, parent)
 
       for down in downstreams[branch]:
+        if down in deletions:
+          continue
+
         if parent in tag_set:
           git.set_branch_config(down, 'remote', '.')
           git.set_branch_config(down, 'merge', 'refs/tags/%s' % parent)
           print ('Reparented %s to track %s [tag] (was tracking %s)'
                  % (down, parent, branch))
         else:
           git.run('branch', '--set-upstream-to', parent, down)
           print ('Reparented %s to track %s (was tracking %s)'
                  % (down, parent, branch))
 
+      deletions.add(branch)
       print git.run('branch', '-d', branch)
 
 
 def rebase_branch(branch, parent, start_hash):
   logging.debug('considering %s(%s) -> %s(%s) : %s',
                 branch, git.hash_one(branch), parent, git.hash_one(parent),
                 start_hash)
 
   # If parent has FROZEN commits, don't base branch on top of them. Instead,
   # base branch on top of whatever commit is before them.
@@ skipping 132 matching lines @@
           % (return_branch, root_branch)
         )
       git.run('checkout', root_branch)
     git.del_config(STARTING_BRANCH_KEY)
 
   return retcode
 
 
 if __name__ == '__main__':  # pragma: no cover
   sys.exit(main(sys.argv[1:]))