diff --git a/mercurial/copies.py b/mercurial/copies.py
--- a/mercurial/copies.py
+++ b/mercurial/copies.py
@@ -229,6 +229,8 @@
 
     cl = repo.changelog
     missingrevs = cl.findmissingrevs(common=[a.rev()], heads=[b.rev()])
+    mrset = set(missingrevs)
+    roots = set()
     for r in missingrevs:
         for p in cl.parentrevs(r):
             if p == node.nullrev:
@@ -237,17 +239,23 @@
                 children[p] = [r]
             else:
                 children[p].append(r)
+            if p not in mrset:
+                roots.add(p)
+    if not roots:
+        # no common revision to track copies from
+        return {}
+    min_root = min(roots)
 
-    roots = set(children) - set(missingrevs)
-    work = list(roots)
+    from_head = set(cl.reachableroots(min_root, [b.rev()], list(roots), includepath=True))
+
+    iterrevs = set(from_head)
+    iterrevs &= mrset
+    iterrevs.update(roots)
+    iterrevs.remove(b.rev())
     all_copies = {r: {} for r in roots}
-    heapq.heapify(work)
     alwaysmatch = match.always()
-    while work:
-        r = heapq.heappop(work)
+    for r in sorted(iterrevs):
         copies = all_copies.pop(r)
-        if r == b.rev():
-            return copies
         for i, c in enumerate(children[r]):
             p1, p2, p1copies, p2copies, removed = revinfo(c)
             if r == p1:
@@ -273,7 +281,6 @@
                     del newcopies[f]
             othercopies = all_copies.get(c)
             if othercopies is None:
-                heapq.heappush(work, c)
                 all_copies[c] = newcopies
             else:
                 # we are the second parent to work on c, we need to merge our
@@ -293,7 +300,7 @@
                 else:
                     newcopies.update(othercopies)
                     all_copies[c] = newcopies
-    assert False
+    return all_copies[b.rev()]
 
 
 def _forwardcopies(a, b, base=None, match=None):