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.cpp205
1 files changed, 87 insertions, 118 deletions
diff --git a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
index 567b866f7777..4b5ade99767b 100644
--- a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
+++ b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
@@ -377,18 +377,12 @@ static void AddPredecessorToBlock(BasicBlock *Succ, BasicBlock *NewPred,
/// expensive.
static InstructionCost computeSpeculationCost(const User *I,
const TargetTransformInfo &TTI) {
- assert(isSafeToSpeculativelyExecute(I) &&
+ assert((!isa<Instruction>(I) ||
+ isSafeToSpeculativelyExecute(cast<Instruction>(I))) &&
"Instruction is not safe to speculatively execute!");
return TTI.getUserCost(I, TargetTransformInfo::TCK_SizeAndLatency);
}
-/// Check whether this is a potentially trapping constant.
-static bool canTrap(const Value *V) {
- if (auto *C = dyn_cast<Constant>(V))
- return C->canTrap();
- return false;
-}
-
/// If we have a merge point of an "if condition" as accepted above,
/// return true if the specified value dominates the block. We
/// don't handle the true generality of domination here, just a special case
@@ -421,9 +415,9 @@ static bool dominatesMergePoint(Value *V, BasicBlock *BB,
Instruction *I = dyn_cast<Instruction>(V);
if (!I) {
- // Non-instructions all dominate instructions, but not all constantexprs
- // can be executed unconditionally.
- return !canTrap(V);
+ // Non-instructions dominate all instructions and can be executed
+ // unconditionally.
+ return true;
}
BasicBlock *PBB = I->getParent();
@@ -1473,10 +1467,7 @@ bool SimplifyCFGOpt::HoistThenElseCodeToIf(BranchInst *BI,
while (isa<DbgInfoIntrinsic>(I2))
I2 = &*BB2_Itr++;
}
- // FIXME: Can we define a safety predicate for CallBr?
- if (isa<PHINode>(I1) || !I1->isIdenticalToWhenDefined(I2) ||
- (isa<InvokeInst>(I1) && !isSafeToHoistInvoke(BB1, BB2, I1, I2)) ||
- isa<CallBrInst>(I1))
+ if (isa<PHINode>(I1) || !I1->isIdenticalToWhenDefined(I2))
return false;
BasicBlock *BIParent = BI->getParent();
@@ -1609,11 +1600,6 @@ HoistTerminator:
if (passingValueIsAlwaysUndefined(BB1V, &PN) ||
passingValueIsAlwaysUndefined(BB2V, &PN))
return Changed;
-
- if (isa<ConstantExpr>(BB1V) && !isSafeToSpeculativelyExecute(BB1V))
- return Changed;
- if (isa<ConstantExpr>(BB2V) && !isSafeToSpeculativelyExecute(BB2V))
- return Changed;
}
}
@@ -2679,9 +2665,6 @@ static bool validateAndCostRequiredSelects(BasicBlock *BB, BasicBlock *ThenBB,
passingValueIsAlwaysUndefined(ThenV, &PN))
return false;
- if (canTrap(OrigV) || canTrap(ThenV))
- return false;
-
HaveRewritablePHIs = true;
ConstantExpr *OrigCE = dyn_cast<ConstantExpr>(OrigV);
ConstantExpr *ThenCE = dyn_cast<ConstantExpr>(ThenV);
@@ -2979,10 +2962,8 @@ static bool BlockIsSimpleEnoughToThreadThrough(BasicBlock *BB) {
return true;
}
-static ConstantInt *
-getKnownValueOnEdge(Value *V, BasicBlock *From, BasicBlock *To,
- SmallDenseMap<std::pair<BasicBlock *, BasicBlock *>,
- ConstantInt *> &Visited) {
+static ConstantInt *getKnownValueOnEdge(Value *V, BasicBlock *From,
+ BasicBlock *To) {
// 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);
@@ -2996,23 +2977,7 @@ getKnownValueOnEdge(Value *V, BasicBlock *From, BasicBlock *To,
return BI->getSuccessor(0) == To ? ConstantInt::getTrue(BI->getContext())
: ConstantInt::getFalse(BI->getContext());
- // Limit the amount of blocks we inspect.
- if (Visited.size() >= 8)
- return nullptr;
-
- auto Pair = Visited.try_emplace({From, To}, nullptr);
- if (!Pair.second)
- return Pair.first->second;
-
- // Check whether the known value is the same for all predecessors.
- ConstantInt *Common = nullptr;
- for (BasicBlock *Pred : predecessors(From)) {
- ConstantInt *C = getKnownValueOnEdge(V, Pred, From, Visited);
- if (!C || (Common && Common != C))
- return nullptr;
- Common = C;
- }
- return Visited[{From, To}] = Common;
+ return nullptr;
}
/// If we have a conditional branch on something for which we know the constant
@@ -3022,7 +2987,7 @@ static Optional<bool>
FoldCondBranchOnValueKnownInPredecessorImpl(BranchInst *BI, DomTreeUpdater *DTU,
const DataLayout &DL,
AssumptionCache *AC) {
- SmallMapVector<BasicBlock *, ConstantInt *, 8> KnownValues;
+ SmallMapVector<ConstantInt *, SmallSetVector<BasicBlock *, 2>, 2> KnownValues;
BasicBlock *BB = BI->getParent();
Value *Cond = BI->getCondition();
PHINode *PN = dyn_cast<PHINode>(Cond);
@@ -3035,12 +3000,11 @@ FoldCondBranchOnValueKnownInPredecessorImpl(BranchInst *BI, DomTreeUpdater *DTU,
for (Use &U : PN->incoming_values())
if (auto *CB = dyn_cast<ConstantInt>(U))
- KnownValues.insert({PN->getIncomingBlock(U), CB});
+ KnownValues[CB].insert(PN->getIncomingBlock(U));
} else {
- SmallDenseMap<std::pair<BasicBlock *, BasicBlock *>, ConstantInt *> Visited;
for (BasicBlock *Pred : predecessors(BB)) {
- if (ConstantInt *CB = getKnownValueOnEdge(Cond, Pred, BB, Visited))
- KnownValues.insert({Pred, CB});
+ if (ConstantInt *CB = getKnownValueOnEdge(Cond, Pred, BB))
+ KnownValues[CB].insert(Pred);
}
}
@@ -3056,29 +3020,34 @@ FoldCondBranchOnValueKnownInPredecessorImpl(BranchInst *BI, DomTreeUpdater *DTU,
for (const auto &Pair : KnownValues) {
// Okay, we now know that all edges from PredBB should be revectored to
// branch to RealDest.
- ConstantInt *CB = Pair.second;
- BasicBlock *PredBB = Pair.first;
+ ConstantInt *CB = Pair.first;
+ ArrayRef<BasicBlock *> PredBBs = Pair.second.getArrayRef();
BasicBlock *RealDest = BI->getSuccessor(!CB->getZExtValue());
if (RealDest == BB)
continue; // Skip self loops.
+
// Skip if the predecessor's terminator is an indirect branch.
- if (isa<IndirectBrInst>(PredBB->getTerminator()))
+ if (any_of(PredBBs, [](BasicBlock *PredBB) {
+ return isa<IndirectBrInst>(PredBB->getTerminator());
+ }))
continue;
- SmallVector<DominatorTree::UpdateType, 3> Updates;
+ LLVM_DEBUG({
+ dbgs() << "Condition " << *Cond << " in " << BB->getName()
+ << " has value " << *Pair.first << " in predecessors:\n";
+ for (const BasicBlock *PredBB : Pair.second)
+ dbgs() << " " << PredBB->getName() << "\n";
+ dbgs() << "Threading to destination " << RealDest->getName() << ".\n";
+ });
+
+ // Split the predecessors we are threading into a new edge block. We'll
+ // clone the instructions into this block, and then redirect it to RealDest.
+ BasicBlock *EdgeBB = SplitBlockPredecessors(BB, PredBBs, ".critedge", DTU);
- // The dest block might have PHI nodes, other predecessors and other
- // difficult cases. Instead of being smart about this, just insert a new
- // block that jumps to the destination block, effectively splitting
- // the edge we are about to create.
- BasicBlock *EdgeBB =
- BasicBlock::Create(BB->getContext(), RealDest->getName() + ".critedge",
- RealDest->getParent(), RealDest);
- BranchInst *CritEdgeBranch = BranchInst::Create(RealDest, EdgeBB);
- if (DTU)
- Updates.push_back({DominatorTree::Insert, EdgeBB, RealDest});
- CritEdgeBranch->setDebugLoc(BI->getDebugLoc());
+ // TODO: These just exist to reduce test diff, we can drop them if we like.
+ EdgeBB->setName(RealDest->getName() + ".critedge");
+ EdgeBB->moveBefore(RealDest);
// Update PHI nodes.
AddPredecessorToBlock(RealDest, EdgeBB, BB);
@@ -3086,12 +3055,12 @@ FoldCondBranchOnValueKnownInPredecessorImpl(BranchInst *BI, DomTreeUpdater *DTU,
// BB may have instructions that are being threaded over. Clone these
// instructions into EdgeBB. We know that there will be no uses of the
// cloned instructions outside of EdgeBB.
- BasicBlock::iterator InsertPt = EdgeBB->begin();
+ BasicBlock::iterator InsertPt = EdgeBB->getFirstInsertionPt();
DenseMap<Value *, Value *> TranslateMap; // Track translated values.
- TranslateMap[Cond] = Pair.second;
+ TranslateMap[Cond] = CB;
for (BasicBlock::iterator BBI = BB->begin(); &*BBI != BI; ++BBI) {
if (PHINode *PN = dyn_cast<PHINode>(BBI)) {
- TranslateMap[PN] = PN->getIncomingValueForBlock(PredBB);
+ TranslateMap[PN] = PN->getIncomingValueForBlock(EdgeBB);
continue;
}
// Clone the instruction.
@@ -3129,19 +3098,15 @@ FoldCondBranchOnValueKnownInPredecessorImpl(BranchInst *BI, DomTreeUpdater *DTU,
}
}
- // Loop over all of the edges from PredBB to BB, changing them to branch
- // to EdgeBB instead.
- Instruction *PredBBTI = PredBB->getTerminator();
- for (unsigned i = 0, e = PredBBTI->getNumSuccessors(); i != e; ++i)
- if (PredBBTI->getSuccessor(i) == BB) {
- BB->removePredecessor(PredBB);
- PredBBTI->setSuccessor(i, EdgeBB);
- }
+ BB->removePredecessor(EdgeBB);
+ BranchInst *EdgeBI = cast<BranchInst>(EdgeBB->getTerminator());
+ EdgeBI->setSuccessor(0, RealDest);
+ EdgeBI->setDebugLoc(BI->getDebugLoc());
if (DTU) {
- Updates.push_back({DominatorTree::Insert, PredBB, EdgeBB});
- Updates.push_back({DominatorTree::Delete, PredBB, BB});
-
+ SmallVector<DominatorTree::UpdateType, 2> Updates;
+ Updates.push_back({DominatorTree::Delete, EdgeBB, BB});
+ Updates.push_back({DominatorTree::Insert, EdgeBB, RealDest});
DTU->applyUpdates(Updates);
}
@@ -3599,13 +3564,6 @@ bool llvm::FoldBranchToCommonDest(BranchInst *BI, DomTreeUpdater *DTU,
Cond->getParent() != BB || !Cond->hasOneUse())
return false;
- // Cond is known to be a compare or binary operator. Check to make sure that
- // neither operand is a potentially-trapping constant expression.
- if (canTrap(Cond->getOperand(0)))
- return false;
- if (canTrap(Cond->getOperand(1)))
- return false;
-
// Finally, don't infinitely unroll conditional loops.
if (is_contained(successors(BB), BB))
return false;
@@ -4113,9 +4071,6 @@ static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI,
if (tryWidenCondBranchToCondBranch(PBI, BI, DTU))
return true;
- if (canTrap(BI->getCondition()))
- return false;
-
// If both branches are conditional and both contain stores to the same
// address, remove the stores from the conditionals and create a conditional
// merged store at the end.
@@ -4157,10 +4112,6 @@ static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI,
// insertion of a large number of select instructions. For targets
// without predication/cmovs, this is a big pessimization.
- // Also do not perform this transformation if any phi node in the common
- // destination block can trap when reached by BB or PBB (PR17073). In that
- // case, it would be unsafe to hoist the operation into a select instruction.
-
BasicBlock *CommonDest = PBI->getSuccessor(PBIOp);
BasicBlock *RemovedDest = PBI->getSuccessor(PBIOp ^ 1);
unsigned NumPhis = 0;
@@ -4168,16 +4119,6 @@ static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI,
++II, ++NumPhis) {
if (NumPhis > 2) // Disable this xform.
return false;
-
- PHINode *PN = cast<PHINode>(II);
- Value *BIV = PN->getIncomingValueForBlock(BB);
- if (canTrap(BIV))
- return false;
-
- unsigned PBBIdx = PN->getBasicBlockIndex(PBI->getParent());
- Value *PBIV = PN->getIncomingValue(PBBIdx);
- if (canTrap(PBIV))
- return false;
}
// Finally, if everything is ok, fold the branches to logical ops.
@@ -6174,6 +6115,23 @@ ShouldBuildLookupTable(SwitchInst *SI, uint64_t TableSize,
return isSwitchDense(SI->getNumCases(), TableSize);
}
+static bool ShouldUseSwitchConditionAsTableIndex(
+ ConstantInt &MinCaseVal, const ConstantInt &MaxCaseVal,
+ bool HasDefaultResults, const SmallDenseMap<PHINode *, Type *> &ResultTypes,
+ const DataLayout &DL, const TargetTransformInfo &TTI) {
+ if (MinCaseVal.isNullValue())
+ return true;
+ if (MinCaseVal.isNegative() ||
+ MaxCaseVal.getLimitedValue() == std::numeric_limits<uint64_t>::max() ||
+ !HasDefaultResults)
+ return false;
+ return all_of(ResultTypes, [&](const auto &KV) {
+ return SwitchLookupTable::WouldFitInRegister(
+ DL, MaxCaseVal.getLimitedValue() + 1 /* TableSize */,
+ KV.second /* ResultType */);
+ });
+}
+
/// Try to reuse the switch table index compare. Following pattern:
/// \code
/// if (idx < tablesize)
@@ -6329,9 +6287,6 @@ static bool SwitchToLookupTable(SwitchInst *SI, IRBuilder<> &Builder,
}
uint64_t NumResults = ResultLists[PHIs[0]].size();
- APInt RangeSpread = MaxCaseVal->getValue() - MinCaseVal->getValue();
- uint64_t TableSize = RangeSpread.getLimitedValue() + 1;
- bool TableHasHoles = (NumResults < TableSize);
// If the table has holes, we need a constant result for the default case
// or a bitmask that fits in a register.
@@ -6340,6 +6295,22 @@ static bool SwitchToLookupTable(SwitchInst *SI, IRBuilder<> &Builder,
getCaseResults(SI, nullptr, SI->getDefaultDest(), &CommonDest,
DefaultResultsList, DL, TTI);
+ for (const auto &I : DefaultResultsList) {
+ PHINode *PHI = I.first;
+ Constant *Result = I.second;
+ DefaultResults[PHI] = Result;
+ }
+
+ bool UseSwitchConditionAsTableIndex = ShouldUseSwitchConditionAsTableIndex(
+ *MinCaseVal, *MaxCaseVal, HasDefaultResults, ResultTypes, DL, TTI);
+ uint64_t TableSize;
+ if (UseSwitchConditionAsTableIndex)
+ TableSize = MaxCaseVal->getLimitedValue() + 1;
+ else
+ TableSize =
+ (MaxCaseVal->getValue() - MinCaseVal->getValue()).getLimitedValue() + 1;
+
+ bool TableHasHoles = (NumResults < TableSize);
bool NeedMask = (TableHasHoles && !HasDefaultResults);
if (NeedMask) {
// As an extra penalty for the validity test we require more cases.
@@ -6349,12 +6320,6 @@ static bool SwitchToLookupTable(SwitchInst *SI, IRBuilder<> &Builder,
return false;
}
- for (const auto &I : DefaultResultsList) {
- PHINode *PHI = I.first;
- Constant *Result = I.second;
- DefaultResults[PHI] = Result;
- }
-
if (!ShouldBuildLookupTable(SI, TableSize, TTI, DL, ResultTypes))
return false;
@@ -6368,11 +6333,15 @@ static bool SwitchToLookupTable(SwitchInst *SI, IRBuilder<> &Builder,
// Compute the table index value.
Builder.SetInsertPoint(SI);
Value *TableIndex;
- if (MinCaseVal->isNullValue())
+ ConstantInt *TableIndexOffset;
+ if (UseSwitchConditionAsTableIndex) {
+ TableIndexOffset = ConstantInt::get(MaxCaseVal->getType(), 0);
TableIndex = SI->getCondition();
- else
- TableIndex = Builder.CreateSub(SI->getCondition(), MinCaseVal,
- "switch.tableidx");
+ } else {
+ TableIndexOffset = MinCaseVal;
+ TableIndex =
+ Builder.CreateSub(SI->getCondition(), TableIndexOffset, "switch.tableidx");
+ }
// Compute the maximum table size representable by the integer type we are
// switching upon.
@@ -6424,7 +6393,7 @@ static bool SwitchToLookupTable(SwitchInst *SI, IRBuilder<> &Builder,
// Build bitmask; fill in a 1 bit for every case.
const ResultListTy &ResultList = ResultLists[PHIs[0]];
for (size_t I = 0, E = ResultList.size(); I != E; ++I) {
- uint64_t Idx = (ResultList[I].first->getValue() - MinCaseVal->getValue())
+ uint64_t Idx = (ResultList[I].first->getValue() - TableIndexOffset->getValue())
.getLimitedValue();
MaskInt |= One << Idx;
}
@@ -6463,8 +6432,8 @@ static bool SwitchToLookupTable(SwitchInst *SI, IRBuilder<> &Builder,
// If using a bitmask, use any value to fill the lookup table holes.
Constant *DV = NeedMask ? ResultLists[PHI][0].second : DefaultResults[PHI];
StringRef FuncName = Fn->getName();
- SwitchLookupTable Table(Mod, TableSize, MinCaseVal, ResultList, DV, DL,
- FuncName);
+ SwitchLookupTable Table(Mod, TableSize, TableIndexOffset, ResultList, DV,
+ DL, FuncName);
Value *Result = Table.BuildLookup(TableIndex, Builder);
generated by cgit v1.2.3 (git 2.25.1) at 2025-10-18 09:06:43 +0000