summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--include/llvm/Support/GenericDomTreeConstruction.h38
-rw-r--r--test/Transforms/JumpThreading/ddt-crash3.ll43
-rw-r--r--test/Transforms/JumpThreading/ddt-crash4.ll75
-rw-r--r--unittests/IR/DominatorTreeTest.cpp25
4 files changed, 172 insertions, 9 deletions
diff --git a/include/llvm/Support/GenericDomTreeConstruction.h b/include/llvm/Support/GenericDomTreeConstruction.h
index 8f801662d0f..e85ac76c780 100644
--- a/include/llvm/Support/GenericDomTreeConstruction.h
+++ b/include/llvm/Support/GenericDomTreeConstruction.h
@@ -628,7 +628,7 @@ struct SemiNCAInfo {
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;
};
@@ -753,14 +753,16 @@ struct SemiNCAInfo {
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 @@ struct SemiNCAInfo {
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)) {
@@ -786,19 +792,31 @@ struct SemiNCAInfo {
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 @@ struct SemiNCAInfo {
II.Bucket.push({SuccLevel, SuccTN});
}
}
+
+ Processed.insert(Next);
} while (!Stack.empty());
}
diff --git a/test/Transforms/JumpThreading/ddt-crash3.ll b/test/Transforms/JumpThreading/ddt-crash3.ll
new file mode 100644
index 00000000000..50ac86a3fb5
--- /dev/null
+++ b/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"}
diff --git a/test/Transforms/JumpThreading/ddt-crash4.ll b/test/Transforms/JumpThreading/ddt-crash4.ll
new file mode 100644
index 00000000000..9bf08395d66
--- /dev/null
+++ b/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
+}
diff --git a/unittests/IR/DominatorTreeTest.cpp b/unittests/IR/DominatorTreeTest.cpp
index bf5aced4928..4666f93da2d 100644
--- a/unittests/IR/DominatorTreeTest.cpp
+++ b/unittests/IR/DominatorTreeTest.cpp
@@ -925,3 +925,28 @@ TEST(DominatorTree, InsertDeleteExhaustive) {
}
}
}
+
+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());
+}
+
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-16 21:36:52 +0000