commit f03adb86b5f05ae2ae06ea21d0a7fd8aa525c6cf
author Paul Wankadia <junyer@google.com> Mon Mar 11 00:09:44 2019 -0700
committer Paul Wankadia <junyer@google.com> Mon Mar 11 07:11:25 2019 +0000
tree eb9cc216ce825d8c7f0d706ba17075383843404e
parent 8d8f56a3479d48ba8a2a1428beee4aa3286641dd

Make BitState avoid touching the bitmap unnecessarily.

Change-Id: Ifceba996ab4fd591a1a24c14e3d011559875ef35
Reviewed-on: https://code-review.googlesource.com/c/re2/+/38832
Reviewed-by: Paul Wankadia <junyer@google.com>

re2/bitstate.cc

diff --git a/re2/bitstate.cc b/re2/bitstate.cc
index 2f5b247..f53f80d 100644
--- a/re2/bitstate.cc
+++ b/re2/bitstate.cc
@@ -153,6 +153,7 @@
       cap_[prog_->inst(-id)->cap()] = p;
       continue;
     }
+
     if (rle > 0) {
       p += rle;
       // Revivify job on stack.
@@ -160,23 +161,7 @@
       ++njob_;
     }
 
-    // Optimization: rather than push and pop,
-    // code that is going to Push and continue
-    // the loop simply updates (ip, p) and jumps
-    // to CheckAndLoop.  We have to do the
-    // ShouldVisit check that Push would have,
-    // but we avoid the stack manipulation.
-    if (0) {
-    Next:
-      if (prog_->inst(id)->last())
-        continue;
-      id++;
-
-    CheckAndLoop:
-      if (!ShouldVisit(id, p))
-        continue;
-    }
-
+  Loop:
     // Visit ip, p.
     Prog::Inst* ip = prog_->inst(id);
     switch (ip->opcode()) {
@@ -185,21 +170,21 @@
         return false;
 
       case kInstFail:
-        continue;
+        break;
 
       case kInstAltMatch:
         if (ip->greedy(prog_)) {
           // out1 is the Match instruction.
           id = ip->out1();
           p = end;
-          goto CheckAndLoop;
+          goto Loop;
         }
         if (longest_) {
           // ip must be non-greedy...
           // out is the Match instruction.
           id = ip->out();
           p = end;
-          goto CheckAndLoop;
+          goto Loop;
         }
         goto Next;
 
@@ -243,7 +228,20 @@
         if (!ip->last())
           Push(id+1, p);  // try the next when we're done
         id = ip->out();
-        goto CheckAndLoop;
+
+        // Optimization: rather than push and pop,
+        // code that is going to Push and continue
+        // the loop simply updates (ip, p) and jumps
+        // to CheckAndLoop.  We have to do the
+        // ShouldVisit check that Push would have,
+        // but we avoid the stack manipulation.
+      CheckAndLoop:
+        // id must be the head of its list, which must
+        // be the case if id-1 is the last of *its* list. :)
+        DCHECK(id == 0 || prog_->inst(id-1)->last());
+        if (ShouldVisit(id, p))
+          goto Loop;
+        break;
 
       case kInstMatch: {
         if (endmatch_ && p != end)
@@ -276,7 +274,14 @@
           return true;
 
         // Otherwise, continue on in hope of a longer match.
-        goto Next;
+        // Note the absence of the ShouldVisit check here
+        // due to execution remaining in the same list.
+      Next:
+        if (!ip->last()) {
+          id++;
+          goto Loop;
+        }
+        break;
       }
     }
   }