[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

746

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

783

nit: while (true)

812

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

812

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

746

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) {
       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 {
+    struct Compare {
       bool operator()(const BucketElementTy &First,
                       const BucketElementTy &Second) const {
-        return First.first > Second.first;
+        return First.first < Second.first;
       }
     };
 
     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;
+                        Compare>
+        Bucket; // Queue of tree nodes sorted by level in descending order.
+    SmallDenseSet<TreeNodePtr, 8> Visited;
     SmallVector<TreeNodePtr, 8> AffectedQueue;
     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");
static void InsertReachable(DomTreeT &DT, const BatchUpdatePtr BUI,
     const TreeNodePtr ToIDom = To->getIDom();
 
     // Nothing affected -- NCA property holds.
     // (Based on the lemma 2.5 from the second paper.)
     if (NCD == To || NCD == ToIDom) return;
 
     // Identify and collect affected nodes.
     InsertionInfo II;
+    SmallVector<TreeNodePtr, 8> Stack;
     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});
+    II.Visited.insert(To);
 
     while (!II.Bucket.empty()) {
       const TreeNodePtr CurrentNode = II.Bucket.top().second;
       const unsigned  CurrentLevel = CurrentNode->getLevel();
       II.Bucket.pop();
       LLVM_DEBUG(dbgs() << "\tAdding to Visited and AffectedQueue: "
                         << BlockNamePrinter(CurrentNode) << "\n");
 
-      II.Visited.insert({CurrentNode, CurrentLevel});
       II.AffectedQueue.push_back(CurrentNode);
 
       // Discover and collect affected successors of the current node.
-      VisitInsertion(DT, BUI, CurrentNode, CurrentLevel, NCD, II);
+      VisitInsertion(DT, BUI, CurrentNode, CurrentLevel, Stack, 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,
+                             TreeNodePtr TN, const unsigned RootLevel,
+                             SmallVectorImpl<TreeNodePtr> &Stack,
                              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 (1) {
+      LLVM_DEBUG(dbgs() << " Next: " << BlockNamePrinter(TN) << "\n");
 
       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");
         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)
+        if (SuccLevel <= NCDLevel + 1 || !II.Visited.insert(SuccTN).second)
           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;
-          }
-
           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) {
+        } else {
           LLVM_DEBUG(dbgs() << "\t\tMarking affected and adding "
                             << BlockNamePrinter(Succ) << " to a Bucket\n");
-          II.Affected.insert(SuccTN);
           II.Bucket.push({SuccLevel, SuccTN});
         }
       }
 
-      Processed.insert(Next);
-    } while (!Stack.empty());
+      if (Stack.empty())
+        break;
+      TN = Stack.pop_back_val();
+    }
   }
 
   // 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) {