aboutsummaryrefslogtreecommitdiff
path: root/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/lib/Transforms/Utils/SimplifyCFG.cpp')
-rw-r--r--llvm/lib/Transforms/Utils/SimplifyCFG.cpp133
1 files changed, 111 insertions, 22 deletions
diff --git a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
index 37c048f..ed2a5c29 100644
--- a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
+++ b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
@@ -302,7 +302,9 @@ class SimplifyCFGOpt {
bool tryToSimplifyUncondBranchWithICmpInIt(ICmpInst *ICI,
IRBuilder<> &Builder);
-
+ bool tryToSimplifyUncondBranchWithICmpSelectInIt(ICmpInst *ICI,
+ SelectInst *Select,
+ IRBuilder<> &Builder);
bool hoistCommonCodeFromSuccessors(Instruction *TI, bool AllInstsEqOnly);
bool hoistSuccIdenticalTerminatorToSwitchOrIf(
Instruction *TI, Instruction *I1,
@@ -5023,16 +5025,65 @@ bool SimplifyCFGOpt::simplifyIndirectBrOnSelect(IndirectBrInst *IBI,
/// the PHI, merging the third icmp into the switch.
bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpInIt(
ICmpInst *ICI, IRBuilder<> &Builder) {
+ // Select == nullptr means we assume that there is a hidden no-op select
+ // instruction of `_ = select %icmp, true, false` after `%icmp = icmp ...`
+ return tryToSimplifyUncondBranchWithICmpSelectInIt(ICI, nullptr, Builder);
+}
+
+/// Similar to tryToSimplifyUncondBranchWithICmpInIt, but handle a more generic
+/// case. This is called when we find an icmp instruction (a seteq/setne with a
+/// constant) and its following select instruction as the only TWO instructions
+/// in a block that ends with an uncond branch. We are looking for a very
+/// specific pattern that occurs when "
+/// if (A == 1) return C1;
+/// if (A == 2) return C2;
+/// if (A < 3) return C3;
+/// return C4;
+/// " gets simplified. In this case, we merge the first two "branches of icmp"
+/// into a switch, but then the default value goes to an uncond block with a lt
+/// icmp and select in it, as InstCombine can not simplify "A < 3" as "A == 2".
+/// After SimplifyCFG and other subsequent optimizations (e.g., SCCP), we might
+/// get something like:
+///
+/// case1:
+/// switch i8 %A, label %DEFAULT [ i8 0, label %end i8 1, label %case2 ]
+/// case2:
+/// br label %end
+/// DEFAULT:
+/// %tmp = icmp eq i8 %A, 2
+/// %val = select i1 %tmp, i8 C3, i8 C4
+/// br label %end
+/// end:
+/// _ = phi i8 [ C1, %case1 ], [ C2, %case2 ], [ %val, %DEFAULT ]
+///
+/// We prefer to split the edge to 'end' so that there are TWO entries of V3/V4
+/// to the PHI, merging the icmp & select into the switch, as follows:
+///
+/// case1:
+/// switch i8 %A, label %DEFAULT [
+/// i8 0, label %end
+/// i8 1, label %case2
+/// i8 2, label %case3
+/// ]
+/// case2:
+/// br label %end
+/// case3:
+/// br label %end
+/// DEFAULT:
+/// br label %end
+/// end:
+/// _ = phi i8 [ C1, %case1 ], [ C2, %case2 ], [ C3, %case2 ], [ C4, %DEFAULT]
+bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpSelectInIt(
+ ICmpInst *ICI, SelectInst *Select, IRBuilder<> &Builder) {
BasicBlock *BB = ICI->getParent();
- // If the block has any PHIs in it or the icmp has multiple uses, it is too
- // complex.
- if (isa<PHINode>(BB->begin()) || !ICI->hasOneUse())
+ // If the block has any PHIs in it or the icmp/select has multiple uses, it is
+ // too complex.
+ /// TODO: support multi-phis in succ BB of select's BB.
+ if (isa<PHINode>(BB->begin()) || !ICI->hasOneUse() ||
+ (Select && !Select->hasOneUse()))
return false;
- Value *V = ICI->getOperand(0);
- ConstantInt *Cst = cast<ConstantInt>(ICI->getOperand(1));
-
// The pattern we're looking for is where our only predecessor is a switch on
// 'V' and this block is the default case for the switch. In this case we can
// fold the compared value into the switch to simplify things.
@@ -5040,8 +5091,36 @@ bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpInIt(
if (!Pred || !isa<SwitchInst>(Pred->getTerminator()))
return false;
+ Value *IcmpCond;
+ ConstantInt *NewCaseVal;
+ CmpPredicate Predicate;
+
+ // Match icmp X, C
+ if (!match(ICI,
+ m_ICmp(Predicate, m_Value(IcmpCond), m_ConstantInt(NewCaseVal))))
+ return false;
+
+ Value *SelectCond, *SelectTrueVal, *SelectFalseVal;
+ Instruction *User;
+ if (!Select) {
+ // If Select == nullptr, we can assume that there is a hidden no-op select
+ // just after icmp
+ SelectCond = ICI;
+ SelectTrueVal = Builder.getTrue();
+ SelectFalseVal = Builder.getFalse();
+ User = ICI->user_back();
+ } else {
+ SelectCond = Select->getCondition();
+ // Check if the select condition is the same as the icmp condition.
+ if (SelectCond != ICI)
+ return false;
+ SelectTrueVal = Select->getTrueValue();
+ SelectFalseVal = Select->getFalseValue();
+ User = Select->user_back();
+ }
+
SwitchInst *SI = cast<SwitchInst>(Pred->getTerminator());
- if (SI->getCondition() != V)
+ if (SI->getCondition() != IcmpCond)
return false;
// If BB is reachable on a non-default case, then we simply know the value of
@@ -5063,9 +5142,9 @@ bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpInIt(
// Ok, the block is reachable from the default dest. If the constant we're
// comparing exists in one of the other edges, then we can constant fold ICI
// and zap it.
- if (SI->findCaseValue(Cst) != SI->case_default()) {
+ if (SI->findCaseValue(NewCaseVal) != SI->case_default()) {
Value *V;
- if (ICI->getPredicate() == ICmpInst::ICMP_EQ)
+ if (Predicate == ICmpInst::ICMP_EQ)
V = ConstantInt::getFalse(BB->getContext());
else
V = ConstantInt::getTrue(BB->getContext());
@@ -5076,25 +5155,30 @@ bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpInIt(
return requestResimplify();
}
- // The use of the icmp has to be in the 'end' block, by the only PHI node in
+ // The use of the select has to be in the 'end' block, by the only PHI node in
// the block.
BasicBlock *SuccBlock = BB->getTerminator()->getSuccessor(0);
- PHINode *PHIUse = dyn_cast<PHINode>(ICI->user_back());
+ PHINode *PHIUse = dyn_cast<PHINode>(User);
if (PHIUse == nullptr || PHIUse != &SuccBlock->front() ||
isa<PHINode>(++BasicBlock::iterator(PHIUse)))
return false;
- // If the icmp is a SETEQ, then the default dest gets false, the new edge gets
- // true in the PHI.
- Constant *DefaultCst = ConstantInt::getTrue(BB->getContext());
- Constant *NewCst = ConstantInt::getFalse(BB->getContext());
+ // If the icmp is a SETEQ, then the default dest gets SelectFalseVal, the new
+ // edge gets SelectTrueVal in the PHI.
+ Value *DefaultCst = SelectFalseVal;
+ Value *NewCst = SelectTrueVal;
- if (ICI->getPredicate() == ICmpInst::ICMP_EQ)
+ if (ICI->getPredicate() == ICmpInst::ICMP_NE)
std::swap(DefaultCst, NewCst);
- // Replace ICI (which is used by the PHI for the default value) with true or
- // false depending on if it is EQ or NE.
- ICI->replaceAllUsesWith(DefaultCst);
+ // Replace Select (which is used by the PHI for the default value) with
+ // SelectFalseVal or SelectTrueVal depending on if ICI is EQ or NE.
+ if (Select) {
+ Select->replaceAllUsesWith(DefaultCst);
+ Select->eraseFromParent();
+ } else {
+ ICI->replaceAllUsesWith(DefaultCst);
+ }
ICI->eraseFromParent();
SmallVector<DominatorTree::UpdateType, 2> Updates;
@@ -5111,7 +5195,7 @@ bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpInIt(
NewW = ((uint64_t(*W0) + 1) >> 1);
SIW.setSuccessorWeight(0, *NewW);
}
- SIW.addCase(Cst, NewBB, NewW);
+ SIW.addCase(NewCaseVal, NewBB, NewW);
if (DTU)
Updates.push_back({DominatorTree::Insert, Pred, NewBB});
}
@@ -8302,13 +8386,18 @@ bool SimplifyCFGOpt::simplifyUncondBranch(BranchInst *BI,
// If the only instruction in the block is a seteq/setne comparison against a
// constant, try to simplify the block.
- if (ICmpInst *ICI = dyn_cast<ICmpInst>(I))
+ if (ICmpInst *ICI = dyn_cast<ICmpInst>(I)) {
if (ICI->isEquality() && isa<ConstantInt>(ICI->getOperand(1))) {
++I;
if (I->isTerminator() &&
tryToSimplifyUncondBranchWithICmpInIt(ICI, Builder))
return true;
+ if (isa<SelectInst>(I) && I->getNextNode()->isTerminator() &&
+ tryToSimplifyUncondBranchWithICmpSelectInIt(ICI, cast<SelectInst>(I),
+ Builder))
+ return true;
}
+ }
// See if we can merge an empty landing pad block with another which is
// equivalent.
generated by cgit v1.1 at 2025-11-08 22:05:47 +0000