[Dominators] Visit affected node candidates found at different root levels

[kuhar]

Summary

This patch attempts to fix the DomTree incremental insertion bug found here PR35969 .

When performing an insertion into a piece of unreachable CFG, we may find the same not at different levels. When this happens, the node can turn out to be affected when we find it starting from a node with a lower level in the tree. The level at which we start visitation affects if we consider a node affected or not.

This patch tracks the lowest level at which each node was visited during insertion and allows it to be visited multiple times, if it can cause it to be considered affected.

[brzycki]

Hi @kuba, I was unable to recreate the crash with the version of ddt-crash3.ll included in this patch. Here's my version of ddt-crash3.ll that fails before the patch. I've also verified this version passes after your patch. I'll take my time and review the real patch later today.

; RUN: opt < %s -jump-threading -disable-output -verify-dom-info
@global = external global i64, align 8

define void @f() {
bb:
  br label %bb1

bb1:
  %tmp = load i64, i64* @global, align 8
  %tmp2 = icmp eq i64 %tmp, 0
  br i1 %tmp2, label %bb27, label %bb3

bb3:
  %tmp4 = load i64, i64* @global, align 8
  %tmp5 = icmp eq i64 %tmp4, 0
  br i1 %tmp5, label %bb6, label %bb7

bb6:
  br label %bb7

bb7:
  %tmp8 = phi i1 [ true, %bb3 ], [ undef, %bb6 ]
  %tmp9 = select i1 %tmp8, i64 %tmp4, i64 0
  br i1 false, label %bb10, label %bb23

bb10:
  %tmp11 = load i64, i64* @global, align 8
  %tmp12 = icmp slt i64 %tmp11, 5
  br i1 %tmp12, label %bb13, label %bb17

bb13:
  br label %bb14

bb14:
  br i1 undef, label %bb15, label %bb16

bb15:
  unreachable

bb16:
  br label %bb10

bb17:
  br label %bb18

bb18:
  br i1 undef, label %bb22, label %bb13

bb19:
  br i1 undef, label %bb20, label %bb21

bb20:
  unreachable

bb21:
  br label %bb18

bb22:
  br label %bb23

bb23:
  br i1 undef, label %bb24, label %bb13

bb24:
  br i1 undef, label %bb26, label %bb25

bb25:
  br label %bb19

bb26:
  br label %bb1

bb27:
  br label %bb24
}

[brzycki]

Your patch to GenericDomTreeConstruction.h passes ninja check-all on x86_64 as well as test-suite on x86_64. I used my version of ddt-crash3.ll posted above for the testing.

[brzycki]

The changes to GenericDomTreeConstruction.h look good to me and I verified the new unit test fails without the patch. Other than my issue with ddt-crash3.ll the patch looks good.

[kuhar]

Apply cosmetic fixes and add Brian's testcase.

The ddt-crash3.ll testcase makes sure we don't go into an infinite loop during visitation, while ddt-crash4.ll is more complicated and exercises the full crash reported in PR35969 .

[brzycki]

LGTM. I've thrown everything I can think of to attempt to trigger a DT regression and found no asserts().

llvm/trunk/include/llvm/Support/GenericDomTreeConstruction.h

struct DecreasingLevel {
         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;
-    SmallDenseSet<TreeNodePtr, 8> Visited;
+    SmallDenseMap<TreeNodePtr, unsigned, 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,
     DEBUG(dbgs() << "Marking " << BlockNamePrinter(To) << " as affected\n");
     II.Affected.insert(To);
     const unsigned ToLevel = To->getLevel();
     DEBUG(dbgs() << "Putting " << BlockNamePrinter(To) << " into a Bucket\n");
     II.Bucket.push({ToLevel, To});
 
     while (!II.Bucket.empty()) {
       const TreeNodePtr CurrentNode = II.Bucket.top().second;
+      const unsigned  CurrentLevel = CurrentNode->getLevel();
       II.Bucket.pop();
       DEBUG(dbgs() << "\tAdding to Visited and AffectedQueue: "
                    << BlockNamePrinter(CurrentNode) << "\n");
-      II.Visited.insert(CurrentNode);
+
+      II.Visited.insert({CurrentNode, CurrentLevel});
       II.AffectedQueue.push_back(CurrentNode);
 
       // Discover and collect affected successors of the current node.
-      VisitInsertion(DT, BUI, CurrentNode, CurrentNode->getLevel(), NCD, II);
+      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();
-    DEBUG(dbgs() << "Visiting " << BlockNamePrinter(TN) << "\n");
+    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();
+      DEBUG(dbgs() << " Next: " << BlockNamePrinter(Next) << "\n");
 
       for (const NodePtr Succ :
            ChildrenGetter<IsPostDom>::Get(Next->getBlock(), BUI)) {
         const TreeNodePtr SuccTN = DT.getNode(Succ);
         assert(SuccTN && "Unreachable successor found at reachable insertion");
         const unsigned SuccLevel = SuccTN->getLevel();
 
-        DEBUG(dbgs() << "\tSuccessor " << BlockNamePrinter(Succ)
-                     << ", level = " << SuccLevel << "\n");
+        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) {
           DEBUG(dbgs() << "\t\tDominated by subtree From\n");
-          if (II.Visited.count(SuccTN) != 0)
+          if (II.Visited.count(SuccTN) != 0) {
+            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;
+          }
 
           DEBUG(dbgs() << "\t\tMarking visited not affected "
                        << BlockNamePrinter(Succ) << "\n");
-          II.Visited.insert(SuccTN);
+          II.Visited.insert({SuccTN, RootLevel});
           II.VisitedNotAffectedQueue.push_back(SuccTN);
           Stack.push_back(SuccTN);
         } else if ((SuccLevel > NCDLevel + 1) &&
             II.Affected.count(SuccTN) == 0) {
           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());
   }
 
   // Updates immediate dominators and levels after insertion.
   static void UpdateInsertion(DomTreeT &DT, const BatchUpdatePtr BUI,
                               const TreeNodePtr NCD, InsertionInfo &II) {
     DEBUG(dbgs() << "Updating NCD = " << BlockNamePrinter(NCD) << "\n");
 

llvm/trunk/test/Transforms/JumpThreading/ddt-crash3.ll

+; RUN: opt < %s -jump-threading -disable-output -verify-dom-info
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+@global = external local_unnamed_addr global i64, align 8
+@global.1 = external local_unnamed_addr global i64, align 8
+@global.2 = external local_unnamed_addr global i64, align 8
+
+; Function Attrs: norecurse noreturn nounwind uwtable
+define void @hoge() local_unnamed_addr #0 {
+bb:
+  br label %bb1
+
+bb1:                                              ; preds = %bb26, %bb
+  %tmp = load i64, i64* @global, align 8, !tbaa !1
+  %tmp2 = icmp eq i64 %tmp, 0
+  br i1 %tmp2, label %bb27, label %bb3
+
+bb3:                                              ; preds = %bb1
+  %tmp4 = load i64, i64* @global.1, align 8, !tbaa !1
+  %tmp5 = icmp eq i64 %tmp4, 0
+  br i1 %tmp5, label %bb23, label %bb23
+
+bb23:                                             ; preds = %bb3, %bb3
+  br label %bb26
+
+bb26:                                             ; preds = %bb27, %bb23
+  br label %bb1
+
+bb27:                                             ; preds = %bb1
+  br label %bb26
+}
+
+attributes #0 = { norecurse noreturn nounwind uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+
+!llvm.ident = !{!0}
+
+!0 = !{!"clang version 7.0.0 "}
+!1 = !{!2, !2, i64 0}
+!2 = !{!"long", !3, i64 0}
+!3 = !{!"omnipotent char", !4, i64 0}
+!4 = !{!"Simple C/C++ TBAA"}

llvm/trunk/test/Transforms/JumpThreading/ddt-crash4.ll

+; RUN: opt < %s -jump-threading -disable-output -verify-dom-info
+@global = external global i64, align 8
+
+define void @f() {
+bb:
+  br label %bb1
+
+bb1:
+  %tmp = load i64, i64* @global, align 8
+  %tmp2 = icmp eq i64 %tmp, 0
+  br i1 %tmp2, label %bb27, label %bb3
+
+bb3:
+  %tmp4 = load i64, i64* @global, align 8
+  %tmp5 = icmp eq i64 %tmp4, 0
+  br i1 %tmp5, label %bb6, label %bb7
+
+bb6:
+  br label %bb7
+
+bb7:
+  %tmp8 = phi i1 [ true, %bb3 ], [ undef, %bb6 ]
+  %tmp9 = select i1 %tmp8, i64 %tmp4, i64 0
+  br i1 false, label %bb10, label %bb23
+
+bb10:
+  %tmp11 = load i64, i64* @global, align 8
+  %tmp12 = icmp slt i64 %tmp11, 5
+  br i1 %tmp12, label %bb13, label %bb17
+
+bb13:
+  br label %bb14
+
+bb14:
+  br i1 undef, label %bb15, label %bb16
+
+bb15:
+  unreachable
+
+bb16:
+  br label %bb10
+
+bb17:
+  br label %bb18
+
+bb18:
+  br i1 undef, label %bb22, label %bb13
+
+bb19:
+  br i1 undef, label %bb20, label %bb21
+
+bb20:
+  unreachable
+
+bb21:
+  br label %bb18
+
+bb22:
+  br label %bb23
+
+bb23:
+  br i1 undef, label %bb24, label %bb13
+
+bb24:
+  br i1 undef, label %bb26, label %bb25
+
+bb25:
+  br label %bb19
+
+bb26:
+  br label %bb1
+
+bb27:
+  br label %bb24
+}

llvm/trunk/unittests/IR/DominatorTreeTest.cpp

while ((LastUpdate = B.applyUpdate())) {
         PDT.deleteEdge(From, To);
       }
 
       EXPECT_TRUE(DT.verify());
       EXPECT_TRUE(PDT.verify());
     }
   }
 }
+
+TEST(DominatorTree, InsertIntoIrreducible) {
+  std::vector<CFGBuilder::Arc> Arcs = {
+      {"0", "1"},
+      {"1", "27"}, {"1", "7"},
+      {"10", "18"},
+      {"13", "10"},
+      {"18", "13"}, {"18", "23"},
+      {"23", "13"}, {"23", "24"},
+      {"24", "1"}, {"24", "18"},
+      {"27", "24"}};
+
+  CFGHolder Holder;
+  CFGBuilder B(Holder.F, Arcs, {{Insert, {"7", "23"}}});
+  DominatorTree DT(*Holder.F);
+  EXPECT_TRUE(DT.verify());
+
+  B.applyUpdate();
+  BasicBlock *From = B.getOrAddBlock("7");
+  BasicBlock *To = B.getOrAddBlock("23");
+  DT.insertEdge(From, To);
+
+  EXPECT_TRUE(DT.verify());
+}
+