[Dominators] Fix and optimize edge insertion of depth-based search

[MaskRay]

Summary

After (x,y) is inserted, depth-based search finds all affected v that satisfies:

depth(nca(x,y))+1 < depth(v) && there exists a path P from y to v where every w on P satisfies depth(v) <= depth(w)

This reduces to a widest path problem (maximizing the weight of the
minimum vertex in the path) which can be solved by a modified version of
Dijkstra with a bucket queue (Depth-based search as mentioned in the paper).

The algorithm visits vertices in decreasing order of bucket number.
However, the current code misused priority_queue to extract them in
increasing order. I cannot think of a failing scenario but it surely may
process vertices more than once due to the local usage of Processed.

This patch fixes this bug and simplifies/optimizes the code a bit. Also
add more comments.

[kuhar]

@MaskRay, awesome, thanks for looking into this.

Does it affect the number of visited nodes and number of calls to VisitInsertion?

depth(nca(x,y))+1 < depth(v) && there exists a path P from y to v where every w on P satisfies depth(v) <= depth(w)

This reduces to a widest path problem (maximizing the weight of the
minimum vertex in the path) which can be solved by a modified version of
BFS with a bucket queue (Depth-based search as mentioned in the paper).

It would be great to also mention that in the implementation -- from what I remember, the paper doesn't mention the widest path problem.

Additionally, this change should be tested extensively -- domtree bugs tend to often be very difficult to discover.

If you are having fun playing with the incremental updater, I think there's much more to squeeze out of deletions -- the implementation cut corners in many cases, while deletions are known to be a bottleneck on some bitcode in JumpThreading and other loop transforms.

include/llvm/Support/GenericDomTreeConstruction.h

754

Is it possible to give Stack a less generic name, or comment on what it corresponds to in the paper?

824–825

nit: while (true)

826

I'd prefer not to reassign(scalar) function arguments, mostly for readability and debugability.

[MaskRay]

Refactor more and add comments

[MaskRay]

include/llvm/Support/GenericDomTreeConstruction.h

826

I think this function actually harms readability. I deleted it.

[MaskRay]

I refactored the code a bit more. I found the split function actually made me hard to follow the logic so I just deleted it.

The current patches passes ninja check-all. Also checked llvm-as.bc (generated by gllvm) and sqlite3.bc

sqlite-autoconf-3270100
clang -Xclang -disable-llvm-passes -c -emit-llvm sqlite3.c # get sqlite.bc

Compared opt -passes='default<O3>,function(print<domtree>)' -disable-output < sqlite3.bc => no difference.

cmake -GNinja -H. -BGLLVM -DCMAKE_BUILD_TYPE=Release -DCMAKE_C_COMPILER=gclang -DCMAKE_CXX_COMPILER=gclang++ -DCMAKE_C_FLAGS='-Xclang -disable-llvm-passes' -DCMAKE_CXX_FLAGS='-Xclang -disable-llvm-passes'

Compared`opt -passes='default<O3>,function(print<domtree>) -disable-output < ~/llvm/GLLVM/bin/llvm-as.bc` (39MiB) => no difference

include/llvm/Support/GenericDomTreeConstruction.h

754

Changed it to UnaffectedOnCurrentLevel

[MaskRay]

Change the comments a bit

[kuhar]

Thanks for the fixes and explanations. Seems good to me now.

[MaskRay]

Add more comments: clarify if (SuccLevel <= NCDLevel + 1 || !II.Visited.insert(SuccTN).second)

include/llvm/Support/GenericDomTreeConstruction.h

for (size_t i = 1, e = NumToNode.size(); i != e; ++i) {
       assert(TN);
       const TreeNodePtr NewIDom = DT.getNode(NodeToInfo[N].IDom);
       TN->setIDom(NewIDom);
     }
   }
 
   // Helper struct used during edge insertions.
   struct InsertionInfo {
-    using BucketElementTy = std::pair<unsigned, TreeNodePtr>;
-    struct DecreasingLevel {
-      bool operator()(const BucketElementTy &First,
-                      const BucketElementTy &Second) const {
-        return First.first > Second.first;
+    struct Compare {
+      bool operator()(TreeNodePtr LHS, TreeNodePtr RHS) const {
+        return LHS->getLevel() < RHS->getLevel();
       }
     };
 
-    std::priority_queue<BucketElementTy, SmallVector<BucketElementTy, 8>,
-        DecreasingLevel>
-        Bucket;  // Queue of tree nodes sorted by level in descending order.
-    SmallDenseSet<TreeNodePtr, 8> Affected;
-    SmallDenseMap<TreeNodePtr, unsigned, 8> Visited;
-    SmallVector<TreeNodePtr, 8> AffectedQueue;
+    // Bucket queue of tree nodes ordered by descending level. For simplicity,
+    // we use a priority_queue here.
+    std::priority_queue<TreeNodePtr, SmallVector<TreeNodePtr, 8>,
+                        Compare>
+        Bucket;
+    SmallDenseSet<TreeNodePtr, 8> Visited;
+    SmallVector<TreeNodePtr, 8> Affected;
     SmallVector<TreeNodePtr, 8> VisitedNotAffectedQueue;
   };
 
   static void InsertEdge(DomTreeT &DT, const BatchUpdatePtr BUI,
                          const NodePtr From, const NodePtr To) {
     assert((From || IsPostDom) &&
            "From has to be a valid CFG node or a virtual root");
     assert(To && "Cannot be a nullptr");
const NodePtr NCDBlock =
         (From->getBlock() && To->getBlock())
             ? DT.findNearestCommonDominator(From->getBlock(), To->getBlock())
             : nullptr;
     assert(NCDBlock || DT.isPostDominator());
     const TreeNodePtr NCD = DT.getNode(NCDBlock);
     assert(NCD);
 
     LLVM_DEBUG(dbgs() << "\t\tNCA == " << BlockNamePrinter(NCD) << "\n");
-    const TreeNodePtr ToIDom = To->getIDom();
+    const unsigned NCDLevel = NCD->getLevel();
 
-    // Nothing affected -- NCA property holds.
-    // (Based on the lemma 2.5 from the second paper.)
-    if (NCD == To || NCD == ToIDom) return;
+    // Based on Lemma 2.5 from the second paper, after insertion of (From,To), v
+    // is affected iff depth(NCD)+1 < depth(v) && a path P from To to v exists
+    // where every w on P s.t. depth(v) <= depth(w)
+    //
+    // This reduces to a widest path problem (maximizing the depth of the
+    // minimum vertex in the path) which can be solved by a modified version of
+    // Dijkstra with a bucket queue (named depth-based search in the paper).
+
+    // To is in the path, so depth(NCD)+1 < depth(v) <= depth(To). Nothing
+    // affected if this does not hold.
+    if (NCDLevel + 1 >= To->getLevel())
+      return;
 
-    // Identify and collect affected nodes.
     InsertionInfo II;
-    LLVM_DEBUG(dbgs() << "Marking " << BlockNamePrinter(To)
-                      << " as affected\n");
-    II.Affected.insert(To);
-    const unsigned ToLevel = To->getLevel();
-    LLVM_DEBUG(dbgs() << "Putting " << BlockNamePrinter(To)
-                      << " into a Bucket\n");
-    II.Bucket.push({ToLevel, To});
+    SmallVector<TreeNodePtr, 8> UnaffectedOnCurrentLevel;
+    II.Bucket.push(To);
+    II.Visited.insert(To);
 
     while (!II.Bucket.empty()) {
-      const TreeNodePtr CurrentNode = II.Bucket.top().second;
-      const unsigned  CurrentLevel = CurrentNode->getLevel();
+      TreeNodePtr TN = II.Bucket.top();
       II.Bucket.pop();
-      LLVM_DEBUG(dbgs() << "\tAdding to Visited and AffectedQueue: "
-                        << BlockNamePrinter(CurrentNode) << "\n");
+      II.Affected.push_back(TN);
 
-      II.Visited.insert({CurrentNode, CurrentLevel});
-      II.AffectedQueue.push_back(CurrentNode);
+      const unsigned CurrentLevel = TN->getLevel();
+      LLVM_DEBUG(dbgs() << "Mark " << BlockNamePrinter(TN) <<
+                 "as affected, CurrentLevel " << CurrentLevel << "\n");
 
-      // Discover and collect affected successors of the current node.
-      VisitInsertion(DT, BUI, CurrentNode, CurrentLevel, NCD, II);
-    }
-
-    // Finish by updating immediate dominators and levels.
-    UpdateInsertion(DT, BUI, NCD, II);
-  }
-
-  // Visits an affected node and collect its affected successors.
-  static void VisitInsertion(DomTreeT &DT, const BatchUpdatePtr BUI,
-                             const TreeNodePtr TN, const unsigned RootLevel,
-                             const TreeNodePtr NCD, InsertionInfo &II) {
-    const unsigned NCDLevel = NCD->getLevel();
-    LLVM_DEBUG(dbgs() << "Visiting " << BlockNamePrinter(TN) << ",  RootLevel "
-                      << RootLevel << "\n");
-
-    SmallVector<TreeNodePtr, 8> Stack = {TN};
       assert(TN->getBlock() && II.Visited.count(TN) && "Preconditions!");
 
-    SmallPtrSet<TreeNodePtr, 8> Processed;
-
-    do {
-      TreeNodePtr Next = Stack.pop_back_val();
-      LLVM_DEBUG(dbgs() << " Next: " << BlockNamePrinter(Next) << "\n");
-
+      while (true) {
+        // Unlike regular Dijkstra, we have an inner loop to expand more
+        // vertices. The first iteration is for the (affected) vertex popped
+        // from II.Bucket and the rest are for vertices in
+        // UnaffectedOnCurrentLevel, which may eventually expand to affected
+        // vertices.
+        //
+        // Invariant: there is an optimal path from `To` to TN with the minimum
+        // depth being CurrentLevel.
         for (const NodePtr Succ :
-           ChildrenGetter<IsPostDom>::Get(Next->getBlock(), BUI)) {
+             ChildrenGetter<IsPostDom>::Get(TN->getBlock(), BUI)) {
           const TreeNodePtr SuccTN = DT.getNode(Succ);
-        assert(SuccTN && "Unreachable successor found at reachable insertion");
+          assert(SuccTN &&
+                 "Unreachable successor found at reachable insertion");
           const unsigned SuccLevel = SuccTN->getLevel();
 
           LLVM_DEBUG(dbgs() << "\tSuccessor " << BlockNamePrinter(Succ)
                             << ", level = " << SuccLevel << "\n");
 
-        // Do not process the same node multiple times.
-        if (Processed.count(Next) > 0)
-          continue;
-
-        // Succ dominated by subtree From -- not affected.
-        // (Based on the lemma 2.5 from the second paper.)
-        if (SuccLevel > RootLevel) {
-          LLVM_DEBUG(dbgs() << "\t\tDominated by subtree From\n");
-          if (II.Visited.count(SuccTN) != 0) {
-            LLVM_DEBUG(dbgs() << "\t\t\talready visited at level "
-                              << II.Visited[SuccTN] << "\n\t\t\tcurrent level "
-                              << RootLevel << ")\n");
-
-            // A node can be necessary to visit again if we see it again at
-            // a lower level than before.
-            if (II.Visited[SuccTN] >= RootLevel)
-              continue;
-          }
+          // There is an optimal path from `To` to Succ with the minimum depth
+          // being min(CurrentLevel, SuccLevel).
+          //
+          // If depth(NCD)+1 < depth(Succ) is not satisfied, Succ is unaffected
+          // and no affected vertex may be reached by a path passing through it.
+          // Stop here. Also, Succ may be visited by other predecessors but the
+          // first visit has the optimal path. Stop if Succ has been visited.
+          if (SuccLevel <= NCDLevel + 1 || !II.Visited.insert(SuccTN).second)
 
+          if (SuccLevel > CurrentLevel) {
+            // Succ is unaffected but it may (transitively) expand to affected
+            // vertices. Store it in UnaffectedOnCurrentLevel.
             LLVM_DEBUG(dbgs() << "\t\tMarking visited not affected "
                               << BlockNamePrinter(Succ) << "\n");
-          II.Visited.insert({SuccTN, RootLevel});
             II.VisitedNotAffectedQueue.push_back(SuccTN);
-          Stack.push_back(SuccTN);
-        } else if ((SuccLevel > NCDLevel + 1) &&
-            II.Affected.count(SuccTN) == 0) {
-          LLVM_DEBUG(dbgs() << "\t\tMarking affected and adding "
-                            << BlockNamePrinter(Succ) << " to a Bucket\n");
-          II.Affected.insert(SuccTN);
-          II.Bucket.push({SuccLevel, SuccTN});
+            UnaffectedOnCurrentLevel.push_back(SuccTN);
+          } else {
+            // The condition is satisfied (Succ is affected). Add Succ to the
+            // bucket queue.
+            LLVM_DEBUG(dbgs() << "\t\tAdd " << BlockNamePrinter(Succ)
+                              << " to a Bucket\n");
+            II.Bucket.push(SuccTN);
           }
         }
 
-      Processed.insert(Next);
-    } while (!Stack.empty());
+        if (UnaffectedOnCurrentLevel.empty())
+          break;
+        TN = UnaffectedOnCurrentLevel.pop_back_val();
+        LLVM_DEBUG(dbgs() << " Next: " << BlockNamePrinter(TN) << "\n");
+      }
+    }
+
+    // Finish by updating immediate dominators and levels.
+    UpdateInsertion(DT, BUI, NCD, II);
   }
 
   // Updates immediate dominators and levels after insertion.
   static void UpdateInsertion(DomTreeT &DT, const BatchUpdatePtr BUI,
                               const TreeNodePtr NCD, InsertionInfo &II) {
     LLVM_DEBUG(dbgs() << "Updating NCD = " << BlockNamePrinter(NCD) << "\n");
 
-    for (const TreeNodePtr TN : II.AffectedQueue) {
+    for (const TreeNodePtr TN : II.Affected) {
       LLVM_DEBUG(dbgs() << "\tIDom(" << BlockNamePrinter(TN)
                         << ") = " << BlockNamePrinter(NCD) << "\n");
       TN->setIDom(NCD);
     }
 
     UpdateLevelsAfterInsertion(II);
     if (IsPostDom) UpdateRootsAfterUpdate(DT, BUI);
   }