[SimplifyCFG] Removed the conditional branch #146445
Open
+108
−6
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
|
Thank you for submitting a Pull Request (PR) to the LLVM Project! This PR will be automatically labeled and the relevant teams will be notified. If you wish to, you can add reviewers by using the "Reviewers" section on this page. If this is not working for you, it is probably because you do not have write permissions for the repository. In which case you can instead tag reviewers by name in a comment by using If you have received no comments on your PR for a week, you can request a review by "ping"ing the PR by adding a comment “Ping”. The common courtesy "ping" rate is once a week. Please remember that you are asking for valuable time from other developers. If you have further questions, they may be answered by the LLVM GitHub User Guide. You can also ask questions in a comment on this PR, on the LLVM Discord or on the forums. |
|
Please let me know if anything else is required. |
|
@llvm/pr-subscribers-llvm-transforms Author: David Zheng (davidzhengyes) ChangesThis pull request responds to my issue #146442. I track StronglyKnownValues in an unordered_set, meaning that we can determine the value on the edge, and also that value is an instruction that belongs to the Full diff: https://github.com/llvm/llvm-project/pull/146445.diff 2 Files Affected:
diff --git a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
index 147d2060e8509..fb54b854c6da5 100644
--- a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
+++ b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
@@ -87,6 +87,7 @@
#include <optional>
#include <set>
#include <tuple>
+#include <unordered_set>
#include <utility>
#include <vector>
@@ -3436,7 +3437,7 @@ static bool blockIsSimpleEnoughToThreadThrough(BasicBlock *BB) {
}
static ConstantInt *getKnownValueOnEdge(Value *V, BasicBlock *From,
- BasicBlock *To) {
+ BasicBlock *To, bool Strong = false) {
// Don't look past the block defining the value, we might get the value from
// a previous loop iteration.
auto *I = dyn_cast<Instruction>(V);
@@ -3446,10 +3447,18 @@ static ConstantInt *getKnownValueOnEdge(Value *V, BasicBlock *From,
// We know the value if the From block branches on it.
auto *BI = dyn_cast<BranchInst>(From->getTerminator());
if (BI && BI->isConditional() && BI->getCondition() == V &&
- BI->getSuccessor(0) != BI->getSuccessor(1))
- return BI->getSuccessor(0) == To ? ConstantInt::getTrue(BI->getContext())
- : ConstantInt::getFalse(BI->getContext());
-
+ BI->getSuccessor(0) != BI->getSuccessor(1)) {
+ ConstantInt *KnownValue =
+ BI->getSuccessor(0) == To ? ConstantInt::getTrue(BI->getContext())
+ : ConstantInt::getFalse(BI->getContext());
+ if (Strong) {
+ Value *Cond = BI->getCondition();
+ Instruction *CondInst = dyn_cast<Instruction>(Cond);
+ return (CondInst && CondInst->getParent() == From) ? KnownValue : nullptr;
+ } else {
+ return KnownValue;
+ }
+ }
return nullptr;
}
@@ -3461,6 +3470,7 @@ foldCondBranchOnValueKnownInPredecessorImpl(BranchInst *BI, DomTreeUpdater *DTU,
const DataLayout &DL,
AssumptionCache *AC) {
SmallMapVector<ConstantInt *, SmallSetVector<BasicBlock *, 2>, 2> KnownValues;
+ std::unordered_set<ConstantInt *> StronglyKnownValues;
BasicBlock *BB = BI->getParent();
Value *Cond = BI->getCondition();
PHINode *PN = dyn_cast<PHINode>(Cond);
@@ -3476,8 +3486,12 @@ foldCondBranchOnValueKnownInPredecessorImpl(BranchInst *BI, DomTreeUpdater *DTU,
KnownValues[CB].insert(PN->getIncomingBlock(U));
} else {
for (BasicBlock *Pred : predecessors(BB)) {
- if (ConstantInt *CB = getKnownValueOnEdge(Cond, Pred, BB))
+ if (ConstantInt *CB = getKnownValueOnEdge(Cond, Pred, BB)) {
KnownValues[CB].insert(Pred);
+ if (getKnownValueOnEdge(Cond, Pred, BB, true)) {
+ StronglyKnownValues.insert(CB);
+ }
+ }
}
}
@@ -3593,11 +3607,20 @@ foldCondBranchOnValueKnownInPredecessorImpl(BranchInst *BI, DomTreeUpdater *DTU,
BranchInst *EdgeBI = cast<BranchInst>(EdgeBB->getTerminator());
EdgeBI->setSuccessor(0, RealDest);
EdgeBI->setDebugLoc(BI->getDebugLoc());
+
+ bool RemoveCondBr = StronglyKnownValues.count(CB);
+ if (RemoveCondBr) {
+ RealDest->removePredecessor(BB);
+ ReplaceInstWithInst(BI, BranchInst::Create(BI->getSuccessor(CB->getZExtValue())));
+ }
if (DTU) {
SmallVector<DominatorTree::UpdateType, 2> Updates;
Updates.push_back({DominatorTree::Delete, EdgeBB, BB});
Updates.push_back({DominatorTree::Insert, EdgeBB, RealDest});
+ if (RemoveCondBr) {
+ Updates.push_back({DominatorTree::Delete, BB, RealDest});
+ }
DTU->applyUpdates(Updates);
}
@@ -3607,6 +3630,11 @@ foldCondBranchOnValueKnownInPredecessorImpl(BranchInst *BI, DomTreeUpdater *DTU,
// bypass the check for trivial cycles above.
MergeBlockIntoPredecessor(EdgeBB, DTU);
+ // If we remove the conditional branch, cannot keep simplifying.
+ if (RemoveCondBr) {
+ return true;
+ }
+
// Signal repeat, simplifying any other constants.
return std::nullopt;
}
diff --git a/llvm/test/Transforms/SimplifyCFG/EliminateDeadPhi.ll b/llvm/test/Transforms/SimplifyCFG/EliminateDeadPhi.ll
new file mode 100644
index 0000000000000..2877d759b4940
--- /dev/null
+++ b/llvm/test/Transforms/SimplifyCFG/EliminateDeadPhi.ll
@@ -0,0 +1,74 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 5
+; RUN: opt < %s -passes=simplifycfg -S | FileCheck %s
+
+
+define void @mainfunc(i16 %0) {
+; CHECK-LABEL: define void @mainfunc(
+; CHECK-SAME: i16 [[TMP0:%.*]]) {
+; CHECK-NEXT: [[ENTRY:.*:]]
+; CHECK-NEXT: [[TMP1:%.*]] = icmp ugt i16 [[TMP0]], 10
+; CHECK-NEXT: br i1 [[TMP1]], label %[[OTHERLOOPEND:.*]], label %[[FOR_BODY_CRITEDGE:.*]]
+; CHECK: [[OTHERLOOPEND]]:
+; CHECK-NEXT: [[OTHERLOOPIV:%.*]] = call i16 @ivfunc()
+; CHECK-NEXT: [[OTHERLOOPPRED:%.*]] = icmp slt i16 [[OTHERLOOPIV]], 100
+; CHECK-NEXT: br i1 [[OTHERLOOPPRED]], label %[[OTHERLOOPEND]], label %[[VADDEXIT:.*]]
+; CHECK: [[VADDEXIT]]:
+; CHECK-NEXT: call void @voidfunc()
+; CHECK-NEXT: br label %[[END:.*]]
+; CHECK: [[FOR_BODY_CRITEDGE]]:
+; CHECK-NEXT: call void @voidfunc()
+; CHECK-NEXT: br label %[[FOR_BODY:.*]]
+; CHECK: [[FOR_BODY]]:
+; CHECK-NEXT: [[IV:%.*]] = phi i16 [ [[IV_NEXT:%.*]], %[[FOR_BODY]] ], [ 0, %[[FOR_BODY_CRITEDGE]] ]
+; CHECK-NEXT: [[VAL:%.*]] = tail call <256 x i1> @helperfunc()
+; CHECK-NEXT: [[VAL2:%.*]] = tail call <1 x i32> @helperfunc2()
+; CHECK-NEXT: [[IV_NEXT]] = add i16 [[IV]], 1
+; CHECK-NEXT: [[PRED:%.*]] = icmp slt i16 [[IV_NEXT]], 100
+; CHECK-NEXT: br i1 [[PRED]], label %[[FOR_BODY]], label %[[END]]
+; CHECK: [[END]]:
+; CHECK-NEXT: ret void
+;
+entry:
+ br label %otherlooppreheader
+
+otherlooppreheader:
+ %1 = icmp ugt i16 %0, 10
+ br i1 %1, label %otherloopend, label %VAddExit
+
+otherloopend:
+ %otherloopiv = call i16 @ivfunc()
+ %otherLoopPred = icmp slt i16 %otherloopiv, 100
+ br i1 %otherLoopPred, label %otherloopend, label %VAddExit
+
+
+VAddExit:
+ call void @voidfunc()
+ br i1 %1, label %end, label %for.body
+
+for.body:
+ %iv = phi i16 [ %iv.next, %VMulExit ], [ 0, %VAddExit ]
+ %val = tail call <256 x i1> @helperfunc()
+ br label %for.body.inner
+
+for.body.inner:
+ %val2 = tail call <1 x i32> @helperfunc2()
+ br label %VMulExit
+
+VMulExit:
+ %iv.next = add i16 %iv, 1
+ %pred = icmp slt i16 %iv.next, 100
+ br i1 %pred, label %for.body, label %end
+
+end:
+ ret void
+
+}
+
+
+declare i16 @ivfunc()
+
+declare <256 x i1> @helperfunc()
+
+declare <1 x i32> @helperfunc2()
+
+declare void @voidfunc()
|
You can test this locally with the following command:git-clang-format --diff HEAD~1 HEAD --extensions cpp -- llvm/lib/Transforms/Utils/SimplifyCFG.cppView the diff from clang-format here.diff --git a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
index fb54b854c..5c5ba9b12 100644
--- a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
+++ b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
@@ -3448,13 +3448,13 @@ static ConstantInt *getKnownValueOnEdge(Value *V, BasicBlock *From,
auto *BI = dyn_cast<BranchInst>(From->getTerminator());
if (BI && BI->isConditional() && BI->getCondition() == V &&
BI->getSuccessor(0) != BI->getSuccessor(1)) {
- ConstantInt *KnownValue =
- BI->getSuccessor(0) == To ? ConstantInt::getTrue(BI->getContext())
- : ConstantInt::getFalse(BI->getContext());
+ ConstantInt *KnownValue = BI->getSuccessor(0) == To
+ ? ConstantInt::getTrue(BI->getContext())
+ : ConstantInt::getFalse(BI->getContext());
if (Strong) {
Value *Cond = BI->getCondition();
Instruction *CondInst = dyn_cast<Instruction>(Cond);
- return (CondInst && CondInst->getParent() == From) ? KnownValue : nullptr;
+ return (CondInst && CondInst->getParent() == From) ? KnownValue : nullptr;
} else {
return KnownValue;
}
@@ -3607,11 +3607,12 @@ foldCondBranchOnValueKnownInPredecessorImpl(BranchInst *BI, DomTreeUpdater *DTU,
BranchInst *EdgeBI = cast<BranchInst>(EdgeBB->getTerminator());
EdgeBI->setSuccessor(0, RealDest);
EdgeBI->setDebugLoc(BI->getDebugLoc());
-
+
bool RemoveCondBr = StronglyKnownValues.count(CB);
if (RemoveCondBr) {
RealDest->removePredecessor(BB);
- ReplaceInstWithInst(BI, BranchInst::Create(BI->getSuccessor(CB->getZExtValue())));
+ ReplaceInstWithInst(
+ BI, BranchInst::Create(BI->getSuccessor(CB->getZExtValue())));
}
if (DTU) {
@@ -3632,7 +3633,7 @@ foldCondBranchOnValueKnownInPredecessorImpl(BranchInst *BI, DomTreeUpdater *DTU,
// If we remove the conditional branch, cannot keep simplifying.
if (RemoveCondBr) {
- return true;
+ return true;
}
// Signal repeat, simplifying any other constants.
|
nikic
reviewed
Jul 1, 2025
|
Thanks for the reply! I don't know if JumpThreading handles this, but I think it is a good idea to remove this conditional branch if we know it is not truly conditional, so that we do not need SimplifyCFG to rely on JumpThreading to run after and clean this up; reducing dependency between passes. I view this as an extension of current functionality, if we are already threading control in this pass, we might as well simplify the CFG even more by removing the branch especially if we know the value coming from the predecessor. We only need a little check to see if the value was also defined in that predecessor, which seems like a common case. |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
This pull request responds to my issue #146442. I track StronglyKnownValues in an unordered_set, meaning that we can determine the value on the edge, and also that value is an instruction that belongs to the
Frombasic block.In the function foldCondBranchOnValueKnownInPredecessorImpl, it attempts to thread control from the predecessor block to its real final destination if both blocks branch on the same value. In the case that this value is created in the predecessor block, we know that all predecessor blocks must be dominated by the predecessor that creates this value, as the block being optimized does not have a phi node. This means that the value is determined by the predecessor it comes from, and it is not possible to reach the optimized block with the value to branch to RealDest.