Improve visited block tracking in isPotentiallyReachable.

[nicholas]

Summary

The outermost loop check and dominator check cover multiple blocks, but we only entered one of the blocks in Visited. Add all blocks we really checked to avoid visiting them again.

In one sense there's no functionality change, but this does change how the accounting towards the threshold is handled. Skipping a visited block does not count towards the block limit.

llvm/lib/Analysis/CFG.cpp

if (!--Limit) {
       // answer true -- that there is potentially a path.
       return true;
     }
 
     if (Outer) {
       // All blocks in a single loop are reachable from all other blocks. From
       // any of these blocks, we can skip directly to the exits of the loop,
       // ignoring any other blocks inside the loop body.
+      Visited.insert(Outer->block_begin(), Outer->block_end());
       Outer->getExitBlocks(Worklist);
     } else if (DTN) {
-      // The dominance check effectively visited all blocks dominated by BB.
-      // Skip over the descendants of the DomTreeNode to visit their successors.
-      for (auto I = df_begin(DTN), E = df_end(DTN); I != E; ++I) {
-        for (auto Succ : successors(I->getBlock()))
+      // The dominance check effectively visits all blocks dominated by BB. Skip
+      // over the domtree-descendants of the block to visit their successors.
+      for (auto I = df_begin(DTN), E = df_end(DTN); I != E;) {
+        for (auto Succ : successors(I->getBlock())) {
           if (!DT->dominates(DTN, DT->getNode(Succ)))
             Worklist.push_back(Succ);
         }
+        ++I;
+        while (I != E && !Visited.insert(I->getBlock()).second) {
+          // Don't enqueue any domtree-descendants of a visited block. We've
+          // already either visited its descendants or enqueued them.
+          // I.skipChildren() implicitly performs ++I.
+          I.skipChildren();
+        }
+      }
     } else {
       Worklist.append(succ_begin(BB), succ_end(BB));
     }
   } while (!Worklist.empty());
 
   // We have exhausted all possible paths and are certain that 'To' can not be
   // reached from 'From'.
   return false;