Movatterモバイル変換


[0]ホーム

URL:


Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

Sign up
Appearance settings

[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

Conversation

antoniofrighetto
Copy link
Contributor

Avoid repeatedly queryinggetUniquePredecessor for already-visited switch successors so as not to incur quadratic runtime.

Fixes:#147239.

@llvmbot
Copy link
Member

@llvm/pr-subscribers-llvm-transforms

Author: Antonio Frighetto (antoniofrighetto)

Changes

Avoid repeatedly queryinggetUniquePredecessor for already-visited switch successors so as not to incur quadratic runtime.

Fixes:#147239.


Full diff:https://github.com/llvm/llvm-project/pull/147384.diff

3 Files Affected:

  • (modified) llvm/lib/Transforms/Utils/SimplifyCFG.cpp (+15-13)
  • (modified) llvm/test/Transforms/SimplifyCFG/switch-dup-bbs.ll (+41)
  • (modified) llvm/test/Transforms/SimplifyCFG/switch-range-to-icmp.ll (+1-1)
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 ;

Copy link
Contributor

@nikicnikic left a 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);
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

Suggested change
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.

antoniofrighetto reacted with thumbs up emoji
Copy link
Member

@dtcxzywdtcxzyw left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

LG

@antoniofrighettoantoniofrighettoforce-pushed theperf/scfg-memoize-unique-pred-dups branch 2 times, most recently fromadb70c8 tod62e51eCompareJuly 18, 2025 06:29
Avoid repeatedly querying `getUniquePredecessor` for already-visitedswitch successors so as not to incur quadratic runtime.Fixes:llvm#147239.
@antoniofrighettoantoniofrighettoforce-pushed theperf/scfg-memoize-unique-pred-dups branch fromd62e51e toc435cd1CompareJuly 18, 2025 06:33
@antoniofrighettoantoniofrighetto merged commitc435cd1 intollvm:mainJul 18, 2025
7 of 9 checks passed
Sign up for freeto join this conversation on GitHub. Already have an account?Sign in to comment
Reviewers

@nikicnikicnikic approved these changes

@dtcxzywdtcxzywdtcxzyw approved these changes

Assignees
No one assigned
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.

suboptimal code for switch statement
4 participants
@antoniofrighetto@llvmbot@nikic@dtcxzyw

[8]ページ先頭

©2009-2025 Movatter.jp