Index: llvm/trunk/include/llvm/Support/GenericDomTreeConstruction.h =================================================================== --- llvm/trunk/include/llvm/Support/GenericDomTreeConstruction.h +++ llvm/trunk/include/llvm/Support/GenericDomTreeConstruction.h @@ -628,7 +628,7 @@ DecreasingLevel> Bucket; // Queue of tree nodes sorted by level in descending order. SmallDenseSet Affected; - SmallDenseSet Visited; + SmallDenseMap Visited; SmallVector AffectedQueue; SmallVector VisitedNotAffectedQueue; }; @@ -753,14 +753,16 @@ 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. @@ -772,13 +774,17 @@ 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 Stack = {TN}; assert(TN->getBlock() && II.Visited.count(TN) && "Preconditions!"); + SmallPtrSet Processed; + do { TreeNodePtr Next = Stack.pop_back_val(); + DEBUG(dbgs() << " Next: " << BlockNamePrinter(Next) << "\n"); for (const NodePtr Succ : ChildrenGetter::Get(Next->getBlock(), BUI)) { @@ -786,19 +792,31 @@ 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) - continue; + 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) && @@ -809,6 +827,8 @@ II.Bucket.push({SuccLevel, SuccTN}); } } + + Processed.insert(Next); } while (!Stack.empty()); } Index: llvm/trunk/test/Transforms/JumpThreading/ddt-crash3.ll =================================================================== --- llvm/trunk/test/Transforms/JumpThreading/ddt-crash3.ll +++ llvm/trunk/test/Transforms/JumpThreading/ddt-crash3.ll @@ -0,0 +1,43 @@ +; 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"} Index: llvm/trunk/test/Transforms/JumpThreading/ddt-crash4.ll =================================================================== --- llvm/trunk/test/Transforms/JumpThreading/ddt-crash4.ll +++ llvm/trunk/test/Transforms/JumpThreading/ddt-crash4.ll @@ -0,0 +1,75 @@ +; 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 +} Index: llvm/trunk/unittests/IR/DominatorTreeTest.cpp =================================================================== --- llvm/trunk/unittests/IR/DominatorTreeTest.cpp +++ llvm/trunk/unittests/IR/DominatorTreeTest.cpp @@ -925,3 +925,28 @@ } } } + +TEST(DominatorTree, InsertIntoIrreducible) { + std::vector 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()); +} +