diff --git a/mercurial/cmdutil.py b/mercurial/cmdutil.py
--- a/mercurial/cmdutil.py
+++ b/mercurial/cmdutil.py
@@ -2193,8 +2193,7 @@ def walkchangerevs(repo, match, opts, pr
     if not revs:
         return []
     wanted = set()
-    slowpath = match.anypats() or ((match.isexact() or match.prefix()) and
-                                   opts.get('removed'))
+    slowpath = match.anypats() or (not match.always() and opts.get('removed'))
     fncache = {}
     change = repo.changectx
 
@@ -2390,8 +2389,7 @@ def _makelogrevset(repo, pats, opts, rev
     # platforms without shell expansion (windows).
     wctx = repo[None]
     match, pats = scmutil.matchandpats(wctx, pats, opts)
-    slowpath = match.anypats() or ((match.isexact() or match.prefix()) and
-                                   opts.get('removed'))
+    slowpath = match.anypats() or (not match.always() and opts.get('removed'))
     if not slowpath:
         for f in match.files():
             if follow and f not in wctx: