diff --git a/mercurial/cmdutil.py b/mercurial/cmdutil.py
--- a/mercurial/cmdutil.py
+++ b/mercurial/cmdutil.py
@@ -286,7 +286,6 @@ def addremove(repo, pats=[], opts={}, dr
     if similarity is None:
         similarity = float(opts.get('similarity') or 0)
     add, remove = [], []
-    mapping = {}
     audit_path = util.path_auditor(repo.root)
     m = match(repo, pats, opts)
     for abs in repo.walk(m):
@@ -300,13 +299,11 @@ def addremove(repo, pats=[], opts={}, dr
         exact = m.exact(abs)
         if good and abs not in repo.dirstate:
             add.append(abs)
-            mapping[abs] = rel, m.exact(abs)
             if repo.ui.verbose or not exact:
                 repo.ui.status(_('adding %s\n') % ((pats and rel) or abs))
         if repo.dirstate[abs] != 'r' and (not good or not util.lexists(target)
             or (os.path.isdir(target) and not os.path.islink(target))):
             remove.append(abs)
-            mapping[abs] = rel, exact
             if repo.ui.verbose or not exact:
                 repo.ui.status(_('removing %s\n') % ((pats and rel) or abs))
     if not dry_run:
@@ -314,9 +311,9 @@ def addremove(repo, pats=[], opts={}, dr
         repo.add(add)
     if similarity > 0:
         for old, new, score in findrenames(repo, add, remove, similarity):
-            oldrel, oldexact = mapping[old]
-            newrel, newexact = mapping[new]
+            oldexact, newexact = m.exact(old), m.exact(new)
             if repo.ui.verbose or not oldexact or not newexact:
+                oldrel, newrel = m.rel(old), m.rel(new)
                 repo.ui.status(_('recording removal of %s as rename to %s '
                                  '(%d%% similar)\n') %
                                (oldrel, newrel, score * 100))