diff --git a/git_common.py b/git_common.py
index 6952c1e..298ecc4 100644
--- a/git_common.py
+++ b/git_common.py
@@ -352,9 +352,16 @@
   If parent is supplied, it's used instead of calling upstream(branch).
   """
   base = branch_config(branch, 'base')
+  base_upstream = branch_config(branch, 'base-upstream')
   parent = parent or upstream(branch)
+  if not parent:
+    return None
   actual_merge_base = run('merge-base', parent, branch)
 
+  if base_upstream != parent:
+    base = None
+    base_upstream = None
+
   def is_ancestor(a, b):
     return run_with_retcode('merge-base', '--is-ancestor', a, b) == 0
 
@@ -370,7 +377,7 @@
 
   if not base:
     base = actual_merge_base
-    manual_merge_base(branch, base)
+    manual_merge_base(branch, base, parent)
 
   return base
 
@@ -409,8 +416,9 @@
   return branch_config(branch, 'dormant', 'false') != 'false'
 
 
-def manual_merge_base(branch, base):
+def manual_merge_base(branch, base, parent):
   set_branch_config(branch, 'base', base)
+  set_branch_config(branch, 'base-upstream', parent)
 
 
 def mktree(treedict):
@@ -475,6 +483,7 @@
 
 def remove_merge_base(branch):
   del_branch_config(branch, 'base')
+  del_branch_config(branch, 'base-upstream')
 
 
 def root():
diff --git a/git_map.py b/git_map.py
index 6fec89d..65814b9 100755
--- a/git_map.py
+++ b/git_map.py
@@ -50,6 +50,7 @@
   current = current_branch()
   all_branches = set(branches())
   merge_base_map = {b: get_or_create_merge_base(b) for b in all_branches}
+  merge_base_map = {b: v for b, v in merge_base_map.iteritems() if v}
   if current in all_branches:
     all_branches.remove(current)
   all_tags = set(tags())
diff --git a/git_mark_merge_base.py b/git_mark_merge_base.py
index cefb6df..673e2b4 100755
--- a/git_mark_merge_base.py
+++ b/git_mark_merge_base.py
@@ -17,7 +17,7 @@
 from subprocess2 import CalledProcessError
 
 from git_common import remove_merge_base, manual_merge_base, current_branch
-from git_common import get_or_create_merge_base, hash_one
+from git_common import get_or_create_merge_base, hash_one, upstream
 
 
 def main(argv):
@@ -51,7 +51,7 @@
       )
       return 1
 
-    manual_merge_base(cur, opts.merge_base)
+    manual_merge_base(cur, opts.merge_base, upstream(cur))
 
   ret = 0
   actual = get_or_create_merge_base(cur)
diff --git a/git_reparent_branch.py b/git_reparent_branch.py
index 9b7dace..f9bf9c5 100755
--- a/git_reparent_branch.py
+++ b/git_reparent_branch.py
@@ -11,7 +11,7 @@
 import subprocess2
 
 from git_common import upstream, current_branch, run, tags, set_branch_config
-from git_common import get_or_create_merge_base, root
+from git_common import get_or_create_merge_base, root, manual_merge_base
 
 import git_rebase_update
 
@@ -44,7 +44,7 @@
   if new_parent == cur_parent:
     parser.error('Cannot reparent a branch to its existing parent')
 
-  get_or_create_merge_base(branch, cur_parent)
+  mbase = get_or_create_merge_base(branch, cur_parent)
 
   all_tags = tags()
   if cur_parent in all_tags:
@@ -66,6 +66,8 @@
            % (branch, new_parent, cur_parent))
     run('branch', '--set-upstream-to', new_parent, branch)
 
+  manual_merge_base(branch, mbase, new_parent)
+
   # TODO(iannucci): ONLY rebase-update the branch which moved (and dependants)
   return git_rebase_update.main(['--no_fetch'])
 
diff --git a/tests/git_common_test.py b/tests/git_common_test.py
index 5695559..bba5b43 100755
--- a/tests/git_common_test.py
+++ b/tests/git_common_test.py
@@ -375,6 +375,8 @@
           J L
 
   X Y Z
+
+  CAT DOG
   """
 
   COMMIT_B = {'file': {'data': 'B'}}
@@ -396,18 +398,18 @@
     for i in xrange(30):
       self.repo.git('branch', 'a'*i)
 
-    with self.assertRaises(SystemExit):
-      self.repo.run(list, self.gc.branches())
+    _, rslt = self.repo.capture_stdio(list, self.gc.branches())
+    self.assertIn('too many branches (39/20)', rslt)
 
     self.repo.git('config', 'depot-tools.branch-limit', 'cat')
 
-    with self.assertRaises(SystemExit):
-      self.repo.run(list, self.gc.branches())
+    _, rslt = self.repo.capture_stdio(list, self.gc.branches())
+    self.assertIn('too many branches (39/20)', rslt)
 
     self.repo.git('config', 'depot-tools.branch-limit', '100')
 
     # should not raise
-    self.assertEqual(36, len(self.repo.run(list, self.gc.branches())))
+    self.assertEqual(38, len(self.repo.run(list, self.gc.branches())))
 
   def testMergeBase(self):
     self.repo.git('checkout', 'branch_K')
@@ -425,9 +427,12 @@
     self.assertEqual(
       self.repo['B'], self.repo.run(self.gc.config, 'branch.branch_K.base')
     )
+    self.assertEqual(
+      'branch_G', self.repo.run(self.gc.config, 'branch.branch_K.base-upstream')
+    )
 
     # deadbeef is a bad hash, so this will result in repo['B']
-    self.repo.run(self.gc.manual_merge_base, 'branch_K', 'deadbeef')
+    self.repo.run(self.gc.manual_merge_base, 'branch_K', 'deadbeef', 'branch_G')
 
     self.assertEqual(
       self.repo['B'],
@@ -435,7 +440,8 @@
     )
 
     # but if we pick a real ancestor, then it'll work
-    self.repo.run(self.gc.manual_merge_base, 'branch_K', self.repo['I'])
+    self.repo.run(self.gc.manual_merge_base, 'branch_K', self.repo['I'],
+                  'branch_G')
 
     self.assertEqual(
       self.repo['I'],
@@ -454,16 +460,28 @@
     self.assertEqual({}, self.repo.run(self.gc.branch_config_map, 'base'))
 
     # if it's too old, then it caps at merge-base
-    self.repo.run(self.gc.manual_merge_base, 'branch_K', self.repo['A'])
+    self.repo.run(self.gc.manual_merge_base, 'branch_K', self.repo['A'],
+                  'branch_G')
 
     self.assertEqual(
       self.repo['B'],
       self.repo.run(self.gc.get_or_create_merge_base, 'branch_K', 'branch_G')
     )
 
+    # If the user does --set-upstream-to something else, then we discard the
+    # base and recompute it.
+    self.repo.run(self.gc.run, 'branch', '-u', 'root_A')
+    self.assertEqual(
+      self.repo['A'],
+      self.repo.run(self.gc.get_or_create_merge_base, 'branch_K')
+    )
+
+    self.assertIsNone(
+      self.repo.run(self.gc.get_or_create_merge_base, 'branch_DOG'))
+
   def testGetBranchTree(self):
     skipped, tree = self.repo.run(self.gc.get_branch_tree)
-    self.assertEqual(skipped, {'master', 'root_X'})
+    self.assertEqual(skipped, {'master', 'root_X', 'branch_DOG', 'root_CAT'})
     self.assertEqual(tree, {
       'branch_G': 'root_A',
       'root_A': 'root_X',
@@ -517,6 +535,8 @@
             J L
 
     X Y Z
+
+    CAT DOG
     """)
 
     rslt = self.repo.run(
@@ -528,6 +548,8 @@
       B H I J L
 
     X Y Z
+
+    CAT DOG
     """)
 
     rslt = self.repo.run(
@@ -551,6 +573,8 @@
     A B C D E F G H I J K L
 
     X Y Z
+
+    CAT DOG
     """)