- Notifications
You must be signed in to change notification settings - Fork14.5k
[SimplifyCFG] Cache unique predecessors insimplifyDuplicateSwitchArms
#147384
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.
Already on GitHub?Sign in to your account
[SimplifyCFG] Cache unique predecessors insimplifyDuplicateSwitchArms
#147384
Conversation
@llvm/pr-subscribers-llvm-transforms Author: Antonio Frighetto (antoniofrighetto) ChangesAvoid repeatedly querying Fixes:#147239. Full diff:https://github.com/llvm/llvm-project/pull/147384.diff 3 Files Affected:
diff --git a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp b/llvm/lib/Transforms/Utils/SimplifyCFG.cppindex a75f29000ca18..30e62367d32f1 100644--- a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp+++ b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp@@ -7493,7 +7493,7 @@ bool SimplifyCFGOpt::simplifyDuplicateSwitchArms(SwitchInst *SI, SmallPtrSet<PHINode *, 8> Phis; SmallPtrSet<BasicBlock *, 8> Seen; DenseMap<PHINode *, SmallDenseMap<BasicBlock *, Value *, 8>> PhiPredIVs;- DenseMap<BasicBlock *, SmallVector<unsigned, 4>> BBToSuccessorIndexes;+ DenseMap<BasicBlock *, SmallVector<unsigned, 32>> BBToSuccessorIndexes; SmallVector<SwitchSuccWrapper> Cases; Cases.reserve(SI->getNumSuccessors());@@ -7505,12 +7505,6 @@ bool SimplifyCFGOpt::simplifyDuplicateSwitchArms(SwitchInst *SI, if (BB->size() != 1) continue;- // FIXME: This case needs some extra care because the terminators other than- // SI need to be updated. For now, consider only backedges to the SI.- if (BB->hasNPredecessorsOrMore(4) ||- BB->getUniquePredecessor() != SI->getParent())- continue;- // FIXME: Relax that the terminator is a BranchInst by checking for equality // on other kinds of terminators. We decide to only support unconditional // branches for now for compile time reasons.@@ -7518,14 +7512,22 @@ bool SimplifyCFGOpt::simplifyDuplicateSwitchArms(SwitchInst *SI, if (!BI || BI->isConditional()) continue;- if (Seen.insert(BB).second) {- // Keep track of which PHIs we need as keys in PhiPredIVs below.- for (BasicBlock *Succ : BI->successors())- Phis.insert_range(llvm::make_pointer_range(Succ->phis()));- // Add the successor only if not previously visited.- Cases.emplace_back(SwitchSuccWrapper{BB, &PhiPredIVs});+ if (!Seen.insert(BB).second) {+ BBToSuccessorIndexes[BB].emplace_back(I);+ continue; }+ // FIXME: This case needs some extra care because the terminators other than+ // SI need to be updated. For now, consider only backedges to the SI.+ if (BB->getUniquePredecessor() != SI->getParent())+ continue;++ // Keep track of which PHIs we need as keys in PhiPredIVs below.+ for (BasicBlock *Succ : BI->successors())+ Phis.insert_range(llvm::make_pointer_range(Succ->phis()));++ // Add the successor only if not previously visited.+ Cases.emplace_back(SwitchSuccWrapper{BB, &PhiPredIVs}); BBToSuccessorIndexes[BB].emplace_back(I); }diff --git a/llvm/test/Transforms/SimplifyCFG/switch-dup-bbs.ll b/llvm/test/Transforms/SimplifyCFG/switch-dup-bbs.llindex 32581bbf8f141..d2d917de11897 100644--- a/llvm/test/Transforms/SimplifyCFG/switch-dup-bbs.ll+++ b/llvm/test/Transforms/SimplifyCFG/switch-dup-bbs.ll@@ -199,3 +199,44 @@ exit: %ret = phi i64 [ 0, %default ], [ 0, %bb1 ], [ 1, %entry ], [ 1, %bb2 ] ret i64 %ret }++define i32 @switch_dup_unbounded_predecessors(i32 %val) {+; SIMPLIFY-CFG-LABEL: define i32 @switch_dup_unbounded_predecessors(+; SIMPLIFY-CFG-SAME: i32 [[VAL:%.*]]) {+; SIMPLIFY-CFG-NEXT: [[ENTRY:.*]]:+; SIMPLIFY-CFG-NEXT: switch i32 [[VAL]], label %[[EXIT:.*]] [+; SIMPLIFY-CFG-NEXT: i32 99, label %[[BB1:.*]]+; SIMPLIFY-CFG-NEXT: i32 115, label %[[BB1]]+; SIMPLIFY-CFG-NEXT: i32 102, label %[[BB1]]+; SIMPLIFY-CFG-NEXT: i32 70, label %[[BB1]]+; SIMPLIFY-CFG-NEXT: i32 101, label %[[BB1]]+; SIMPLIFY-CFG-NEXT: i32 69, label %[[BB1]]+; SIMPLIFY-CFG-NEXT: i32 103, label %[[BB1]]+; SIMPLIFY-CFG-NEXT: ]+; SIMPLIFY-CFG: [[BB1]]:+; SIMPLIFY-CFG-NEXT: br label %[[EXIT]]+; SIMPLIFY-CFG: [[EXIT]]:+; SIMPLIFY-CFG-NEXT: [[PHI:%.*]] = phi i32 [ 0, %[[ENTRY]] ], [ 1, %[[BB1]] ]+; SIMPLIFY-CFG-NEXT: ret i32 [[PHI]]+;+entry:+ switch i32 %val, label %exit [+ i32 99, label %bb1+ i32 115, label %bb1+ i32 102, label %bb2+ i32 70, label %bb2+ i32 101, label %bb2+ i32 69, label %bb2+ i32 103, label %bb2+ ]++bb1:+ br label %exit++bb2:+ br label %exit++exit:+ %phi = phi i32 [ 0, %entry ], [ 1, %bb1 ], [ 1, %bb2 ]+ ret i32 %phi+}diff --git a/llvm/test/Transforms/SimplifyCFG/switch-range-to-icmp.ll b/llvm/test/Transforms/SimplifyCFG/switch-range-to-icmp.llindex 4136f33983a2b..8f2ae2d054f1e 100644--- a/llvm/test/Transforms/SimplifyCFG/switch-range-to-icmp.ll+++ b/llvm/test/Transforms/SimplifyCFG/switch-range-to-icmp.ll@@ -149,7 +149,7 @@ unreach2: define void @pr53208_single_reachable_dest(i8 %sw, ptr %p0) { ; CHECK-LABEL: @pr53208_single_reachable_dest(-; CHECK-NEXT: group2:+; CHECK-NEXT: exit: ; CHECK-NEXT: call void @bar(ptr [[P0:%.*]]) ; CHECK-NEXT: ret void ; |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
LGTM
// Add the successor only if not previously visited. | ||
Cases.emplace_back(SwitchSuccWrapper{BB, &PhiPredIVs}); | ||
if (!Seen.insert(BB).second) { | ||
BBToSuccessorIndexes[BB].emplace_back(I); |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
BBToSuccessorIndexes[BB].emplace_back(I); | |
auto It =BBToSuccessorIndexes.find(BB); | |
if (It != BBToSuccessorIndexes.end()) | |
It->second.emplace_back(I); |
If we don't add the index the first time we meet the BB, don't add the index in later iterations.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
LG
adb70c8
tod62e51e
CompareAvoid repeatedly querying `getUniquePredecessor` for already-visitedswitch successors so as not to incur quadratic runtime.Fixes:llvm#147239.
d62e51e
toc435cd1
Comparec435cd1
intollvm:mainUh oh!
There was an error while loading.Please reload this page.
Avoid repeatedly querying
getUniquePredecessor
for already-visited switch successors so as not to incur quadratic runtime.Fixes:#147239.