aboutsummaryrefslogtreecommitdiff
path: root/lib/Transforms/Scalar/GuardWidening.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'lib/Transforms/Scalar/GuardWidening.cpp')
-rw-r--r--lib/Transforms/Scalar/GuardWidening.cpp212
1 files changed, 127 insertions, 85 deletions
diff --git a/lib/Transforms/Scalar/GuardWidening.cpp b/lib/Transforms/Scalar/GuardWidening.cpp
index efc204d4f74b..e14f44bb7069 100644
--- a/lib/Transforms/Scalar/GuardWidening.cpp
+++ b/lib/Transforms/Scalar/GuardWidening.cpp
@@ -1,9 +1,8 @@
//===- GuardWidening.cpp - ---- Guard widening ----------------------------===//
//
-// The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
@@ -83,6 +82,11 @@ static cl::opt<unsigned> FrequentBranchThreshold(
"it is considered frequently taken"),
cl::init(1000));
+static cl::opt<bool>
+ WidenBranchGuards("guard-widening-widen-branch-guards", cl::Hidden,
+ cl::desc("Whether or not we should widen guards "
+ "expressed as branches by widenable conditions"),
+ cl::init(true));
namespace {
@@ -93,6 +97,10 @@ static Value *getCondition(Instruction *I) {
"Bad guard intrinsic?");
return GI->getArgOperand(0);
}
+ if (isGuardAsWidenableBranch(I)) {
+ auto *Cond = cast<BranchInst>(I)->getCondition();
+ return cast<BinaryOperator>(Cond)->getOperand(0);
+ }
return cast<BranchInst>(I)->getCondition();
}
@@ -133,12 +141,12 @@ class GuardWideningImpl {
/// guards.
DenseSet<Instruction *> WidenedGuards;
- /// Try to eliminate guard \p Guard by widening it into an earlier dominating
- /// guard. \p DFSI is the DFS iterator on the dominator tree that is
- /// currently visiting the block containing \p Guard, and \p GuardsPerBlock
+ /// Try to eliminate instruction \p Instr by widening it into an earlier
+ /// dominating guard. \p DFSI is the DFS iterator on the dominator tree that
+ /// is currently visiting the block containing \p Guard, and \p GuardsPerBlock
/// maps BasicBlocks to the set of guards seen in that block.
- bool eliminateGuardViaWidening(
- Instruction *Guard, const df_iterator<DomTreeNode *> &DFSI,
+ bool eliminateInstrViaWidening(
+ Instruction *Instr, const df_iterator<DomTreeNode *> &DFSI,
const DenseMap<BasicBlock *, SmallVector<Instruction *, 8>> &
GuardsPerBlock, bool InvertCondition = false);
@@ -162,28 +170,25 @@ class GuardWideningImpl {
static StringRef scoreTypeToString(WideningScore WS);
- /// Compute the score for widening the condition in \p DominatedGuard
- /// (contained in \p DominatedGuardLoop) into \p DominatingGuard (contained in
- /// \p DominatingGuardLoop). If \p InvertCond is set, then we widen the
+ /// Compute the score for widening the condition in \p DominatedInstr
+ /// into \p DominatingGuard. If \p InvertCond is set, then we widen the
/// inverted condition of the dominating guard.
- WideningScore computeWideningScore(Instruction *DominatedGuard,
- Loop *DominatedGuardLoop,
+ WideningScore computeWideningScore(Instruction *DominatedInstr,
Instruction *DominatingGuard,
- Loop *DominatingGuardLoop,
bool InvertCond);
/// Helper to check if \p V can be hoisted to \p InsertPos.
- bool isAvailableAt(Value *V, Instruction *InsertPos) {
- SmallPtrSet<Instruction *, 8> Visited;
+ bool isAvailableAt(const Value *V, const Instruction *InsertPos) const {
+ SmallPtrSet<const Instruction *, 8> Visited;
return isAvailableAt(V, InsertPos, Visited);
}
- bool isAvailableAt(Value *V, Instruction *InsertPos,
- SmallPtrSetImpl<Instruction *> &Visited);
+ bool isAvailableAt(const Value *V, const Instruction *InsertPos,
+ SmallPtrSetImpl<const Instruction *> &Visited) const;
/// Helper to hoist \p V to \p InsertPos. Guaranteed to succeed if \c
/// isAvailableAt returned true.
- void makeAvailableAt(Value *V, Instruction *InsertPos);
+ void makeAvailableAt(Value *V, Instruction *InsertPos) const;
/// Common helper used by \c widenGuard and \c isWideningCondProfitable. Try
/// to generate an expression computing the logical AND of \p Cond0 and (\p
@@ -200,23 +205,23 @@ class GuardWideningImpl {
/// pre-existing instruction in the IR that computes the result of this range
/// check.
class RangeCheck {
- Value *Base;
- ConstantInt *Offset;
- Value *Length;
+ const Value *Base;
+ const ConstantInt *Offset;
+ const Value *Length;
ICmpInst *CheckInst;
public:
- explicit RangeCheck(Value *Base, ConstantInt *Offset, Value *Length,
- ICmpInst *CheckInst)
+ explicit RangeCheck(const Value *Base, const ConstantInt *Offset,
+ const Value *Length, ICmpInst *CheckInst)
: Base(Base), Offset(Offset), Length(Length), CheckInst(CheckInst) {}
- void setBase(Value *NewBase) { Base = NewBase; }
- void setOffset(ConstantInt *NewOffset) { Offset = NewOffset; }
+ void setBase(const Value *NewBase) { Base = NewBase; }
+ void setOffset(const ConstantInt *NewOffset) { Offset = NewOffset; }
- Value *getBase() const { return Base; }
- ConstantInt *getOffset() const { return Offset; }
+ const Value *getBase() const { return Base; }
+ const ConstantInt *getOffset() const { return Offset; }
const APInt &getOffsetValue() const { return getOffset()->getValue(); }
- Value *getLength() const { return Length; };
+ const Value *getLength() const { return Length; };
ICmpInst *getCheckInst() const { return CheckInst; }
void print(raw_ostream &OS, bool PrintTypes = false) {
@@ -238,19 +243,19 @@ class GuardWideningImpl {
/// append them to \p Checks. Returns true on success, may clobber \c Checks
/// on failure.
bool parseRangeChecks(Value *CheckCond, SmallVectorImpl<RangeCheck> &Checks) {
- SmallPtrSet<Value *, 8> Visited;
+ SmallPtrSet<const Value *, 8> Visited;
return parseRangeChecks(CheckCond, Checks, Visited);
}
bool parseRangeChecks(Value *CheckCond, SmallVectorImpl<RangeCheck> &Checks,
- SmallPtrSetImpl<Value *> &Visited);
+ SmallPtrSetImpl<const Value *> &Visited);
/// Combine the checks in \p Checks into a smaller set of checks and append
/// them into \p CombinedChecks. Return true on success (i.e. all of checks
/// in \p Checks were combined into \p CombinedChecks). Clobbers \p Checks
/// and \p CombinedChecks on success and on failure.
bool combineRangeChecks(SmallVectorImpl<RangeCheck> &Checks,
- SmallVectorImpl<RangeCheck> &CombinedChecks);
+ SmallVectorImpl<RangeCheck> &CombinedChecks) const;
/// Can we compute the logical AND of \p Cond0 and \p Cond1 for the price of
/// computing only one of the two expressions?
@@ -266,8 +271,16 @@ class GuardWideningImpl {
void widenGuard(Instruction *ToWiden, Value *NewCondition,
bool InvertCondition) {
Value *Result;
- widenCondCommon(ToWiden->getOperand(0), NewCondition, ToWiden, Result,
+ widenCondCommon(getCondition(ToWiden), NewCondition, ToWiden, Result,
InvertCondition);
+ Value *WidenableCondition = nullptr;
+ if (isGuardAsWidenableBranch(ToWiden)) {
+ auto *Cond = cast<BranchInst>(ToWiden)->getCondition();
+ WidenableCondition = cast<BinaryOperator>(Cond)->getOperand(1);
+ }
+ if (WidenableCondition)
+ Result = BinaryOperator::CreateAnd(Result, WidenableCondition,
+ "guard.chk", ToWiden);
setCondition(ToWiden, Result);
}
@@ -285,6 +298,14 @@ public:
};
}
+static bool isSupportedGuardInstruction(const Instruction *Insn) {
+ if (isGuard(Insn))
+ return true;
+ if (WidenBranchGuards && isGuardAsWidenableBranch(Insn))
+ return true;
+ return false;
+}
+
bool GuardWideningImpl::run() {
DenseMap<BasicBlock *, SmallVector<Instruction *, 8>> GuardsInBlock;
bool Changed = false;
@@ -304,20 +325,20 @@ bool GuardWideningImpl::run() {
auto &CurrentList = GuardsInBlock[BB];
for (auto &I : *BB)
- if (isGuard(&I))
+ if (isSupportedGuardInstruction(&I))
CurrentList.push_back(cast<Instruction>(&I));
for (auto *II : CurrentList)
- Changed |= eliminateGuardViaWidening(II, DFI, GuardsInBlock);
+ Changed |= eliminateInstrViaWidening(II, DFI, GuardsInBlock);
if (WidenFrequentBranches && BPI)
if (auto *BI = dyn_cast<BranchInst>(BB->getTerminator()))
if (BI->isConditional()) {
// If one of branches of a conditional is likely taken, try to
// eliminate it.
if (BPI->getEdgeProbability(BB, 0U) >= *LikelyTaken)
- Changed |= eliminateGuardViaWidening(BI, DFI, GuardsInBlock);
+ Changed |= eliminateInstrViaWidening(BI, DFI, GuardsInBlock);
else if (BPI->getEdgeProbability(BB, 1U) >= *LikelyTaken)
- Changed |= eliminateGuardViaWidening(BI, DFI, GuardsInBlock,
+ Changed |= eliminateInstrViaWidening(BI, DFI, GuardsInBlock,
/*InvertCondition*/true);
}
}
@@ -326,7 +347,7 @@ bool GuardWideningImpl::run() {
for (auto *I : EliminatedGuardsAndBranches)
if (!WidenedGuards.count(I)) {
assert(isa<ConstantInt>(getCondition(I)) && "Should be!");
- if (isGuard(I))
+ if (isSupportedGuardInstruction(I))
eliminateGuard(I);
else {
assert(isa<BranchInst>(I) &&
@@ -338,19 +359,18 @@ bool GuardWideningImpl::run() {
return Changed;
}
-bool GuardWideningImpl::eliminateGuardViaWidening(
- Instruction *GuardInst, const df_iterator<DomTreeNode *> &DFSI,
+bool GuardWideningImpl::eliminateInstrViaWidening(
+ Instruction *Instr, const df_iterator<DomTreeNode *> &DFSI,
const DenseMap<BasicBlock *, SmallVector<Instruction *, 8>> &
GuardsInBlock, bool InvertCondition) {
// Ignore trivial true or false conditions. These instructions will be
// trivially eliminated by any cleanup pass. Do not erase them because other
// guards can possibly be widened into them.
- if (isa<ConstantInt>(getCondition(GuardInst)))
+ if (isa<ConstantInt>(getCondition(Instr)))
return false;
Instruction *BestSoFar = nullptr;
auto BestScoreSoFar = WS_IllegalOrNegative;
- auto *GuardInstLoop = LI.getLoopFor(GuardInst->getParent());
// In the set of dominating guards, find the one we can merge GuardInst with
// for the most profit.
@@ -358,12 +378,13 @@ bool GuardWideningImpl::eliminateGuardViaWidening(
auto *CurBB = DFSI.getPath(i)->getBlock();
if (!BlockFilter(CurBB))
break;
- auto *CurLoop = LI.getLoopFor(CurBB);
assert(GuardsInBlock.count(CurBB) && "Must have been populated by now!");
const auto &GuardsInCurBB = GuardsInBlock.find(CurBB)->second;
auto I = GuardsInCurBB.begin();
- auto E = GuardsInCurBB.end();
+ auto E = Instr->getParent() == CurBB
+ ? std::find(GuardsInCurBB.begin(), GuardsInCurBB.end(), Instr)
+ : GuardsInCurBB.end();
#ifndef NDEBUG
{
@@ -379,21 +400,11 @@ bool GuardWideningImpl::eliminateGuardViaWidening(
}
#endif
- assert((i == (e - 1)) == (GuardInst->getParent() == CurBB) && "Bad DFS?");
-
- if (i == (e - 1) && CurBB->getTerminator() != GuardInst) {
- // Corner case: make sure we're only looking at guards strictly dominating
- // GuardInst when visiting GuardInst->getParent().
- auto NewEnd = std::find(I, E, GuardInst);
- assert(NewEnd != E && "GuardInst not in its own block?");
- E = NewEnd;
- }
+ assert((i == (e - 1)) == (Instr->getParent() == CurBB) && "Bad DFS?");
for (auto *Candidate : make_range(I, E)) {
- auto Score =
- computeWideningScore(GuardInst, GuardInstLoop, Candidate, CurLoop,
- InvertCondition);
- LLVM_DEBUG(dbgs() << "Score between " << *getCondition(GuardInst)
+ auto Score = computeWideningScore(Instr, Candidate, InvertCondition);
+ LLVM_DEBUG(dbgs() << "Score between " << *getCondition(Instr)
<< " and " << *getCondition(Candidate) << " is "
<< scoreTypeToString(Score) << "\n");
if (Score > BestScoreSoFar) {
@@ -404,42 +415,45 @@ bool GuardWideningImpl::eliminateGuardViaWidening(
}
if (BestScoreSoFar == WS_IllegalOrNegative) {
- LLVM_DEBUG(dbgs() << "Did not eliminate guard " << *GuardInst << "\n");
+ LLVM_DEBUG(dbgs() << "Did not eliminate guard " << *Instr << "\n");
return false;
}
- assert(BestSoFar != GuardInst && "Should have never visited same guard!");
- assert(DT.dominates(BestSoFar, GuardInst) && "Should be!");
+ assert(BestSoFar != Instr && "Should have never visited same guard!");
+ assert(DT.dominates(BestSoFar, Instr) && "Should be!");
- LLVM_DEBUG(dbgs() << "Widening " << *GuardInst << " into " << *BestSoFar
+ LLVM_DEBUG(dbgs() << "Widening " << *Instr << " into " << *BestSoFar
<< " with score " << scoreTypeToString(BestScoreSoFar)
<< "\n");
- widenGuard(BestSoFar, getCondition(GuardInst), InvertCondition);
+ widenGuard(BestSoFar, getCondition(Instr), InvertCondition);
auto NewGuardCondition = InvertCondition
- ? ConstantInt::getFalse(GuardInst->getContext())
- : ConstantInt::getTrue(GuardInst->getContext());
- setCondition(GuardInst, NewGuardCondition);
- EliminatedGuardsAndBranches.push_back(GuardInst);
+ ? ConstantInt::getFalse(Instr->getContext())
+ : ConstantInt::getTrue(Instr->getContext());
+ setCondition(Instr, NewGuardCondition);
+ EliminatedGuardsAndBranches.push_back(Instr);
WidenedGuards.insert(BestSoFar);
return true;
}
-GuardWideningImpl::WideningScore GuardWideningImpl::computeWideningScore(
- Instruction *DominatedGuard, Loop *DominatedGuardLoop,
- Instruction *DominatingGuard, Loop *DominatingGuardLoop, bool InvertCond) {
+GuardWideningImpl::WideningScore
+GuardWideningImpl::computeWideningScore(Instruction *DominatedInstr,
+ Instruction *DominatingGuard,
+ bool InvertCond) {
+ Loop *DominatedInstrLoop = LI.getLoopFor(DominatedInstr->getParent());
+ Loop *DominatingGuardLoop = LI.getLoopFor(DominatingGuard->getParent());
bool HoistingOutOfLoop = false;
- if (DominatingGuardLoop != DominatedGuardLoop) {
+ if (DominatingGuardLoop != DominatedInstrLoop) {
// Be conservative and don't widen into a sibling loop. TODO: If the
// sibling is colder, we should consider allowing this.
if (DominatingGuardLoop &&
- !DominatingGuardLoop->contains(DominatedGuardLoop))
+ !DominatingGuardLoop->contains(DominatedInstrLoop))
return WS_IllegalOrNegative;
HoistingOutOfLoop = true;
}
- if (!isAvailableAt(getCondition(DominatedGuard), DominatingGuard))
+ if (!isAvailableAt(getCondition(DominatedInstr), DominatingGuard))
return WS_IllegalOrNegative;
// If the guard was conditional executed, it may never be reached
@@ -450,7 +464,7 @@ GuardWideningImpl::WideningScore GuardWideningImpl::computeWideningScore(
// here. TODO: evaluate cost model for spurious deopt
// NOTE: As written, this also lets us hoist right over another guard which
// is essentially just another spelling for control flow.
- if (isWideningCondProfitable(getCondition(DominatedGuard),
+ if (isWideningCondProfitable(getCondition(DominatedInstr),
getCondition(DominatingGuard), InvertCond))
return HoistingOutOfLoop ? WS_VeryPositive : WS_Positive;
@@ -462,7 +476,9 @@ GuardWideningImpl::WideningScore GuardWideningImpl::computeWideningScore(
// throw, etc...). That choice appears arbitrary.
auto MaybeHoistingOutOfIf = [&]() {
auto *DominatingBlock = DominatingGuard->getParent();
- auto *DominatedBlock = DominatedGuard->getParent();
+ auto *DominatedBlock = DominatedInstr->getParent();
+ if (isGuardAsWidenableBranch(DominatingGuard))
+ DominatingBlock = cast<BranchInst>(DominatingGuard)->getSuccessor(0);
// Same Block?
if (DominatedBlock == DominatingBlock)
@@ -478,8 +494,9 @@ GuardWideningImpl::WideningScore GuardWideningImpl::computeWideningScore(
return MaybeHoistingOutOfIf() ? WS_IllegalOrNegative : WS_Neutral;
}
-bool GuardWideningImpl::isAvailableAt(Value *V, Instruction *Loc,
- SmallPtrSetImpl<Instruction *> &Visited) {
+bool GuardWideningImpl::isAvailableAt(
+ const Value *V, const Instruction *Loc,
+ SmallPtrSetImpl<const Instruction *> &Visited) const {
auto *Inst = dyn_cast<Instruction>(V);
if (!Inst || DT.dominates(Inst, Loc) || Visited.count(Inst))
return true;
@@ -499,7 +516,7 @@ bool GuardWideningImpl::isAvailableAt(Value *V, Instruction *Loc,
[&](Value *Op) { return isAvailableAt(Op, Loc, Visited); });
}
-void GuardWideningImpl::makeAvailableAt(Value *V, Instruction *Loc) {
+void GuardWideningImpl::makeAvailableAt(Value *V, Instruction *Loc) const {
auto *Inst = dyn_cast<Instruction>(V);
if (!Inst || DT.dominates(Inst, Loc))
return;
@@ -597,7 +614,7 @@ bool GuardWideningImpl::widenCondCommon(Value *Cond0, Value *Cond1,
bool GuardWideningImpl::parseRangeChecks(
Value *CheckCond, SmallVectorImpl<GuardWideningImpl::RangeCheck> &Checks,
- SmallPtrSetImpl<Value *> &Visited) {
+ SmallPtrSetImpl<const Value *> &Visited) {
if (!Visited.insert(CheckCond).second)
return true;
@@ -616,7 +633,7 @@ bool GuardWideningImpl::parseRangeChecks(
IC->getPredicate() != ICmpInst::ICMP_UGT))
return false;
- Value *CmpLHS = IC->getOperand(0), *CmpRHS = IC->getOperand(1);
+ const Value *CmpLHS = IC->getOperand(0), *CmpRHS = IC->getOperand(1);
if (IC->getPredicate() == ICmpInst::ICMP_UGT)
std::swap(CmpLHS, CmpRHS);
@@ -669,13 +686,13 @@ bool GuardWideningImpl::parseRangeChecks(
bool GuardWideningImpl::combineRangeChecks(
SmallVectorImpl<GuardWideningImpl::RangeCheck> &Checks,
- SmallVectorImpl<GuardWideningImpl::RangeCheck> &RangeChecksOut) {
+ SmallVectorImpl<GuardWideningImpl::RangeCheck> &RangeChecksOut) const {
unsigned OldCount = Checks.size();
while (!Checks.empty()) {
// Pick all of the range checks with a specific base and length, and try to
// merge them.
- Value *CurrentBase = Checks.front().getBase();
- Value *CurrentLength = Checks.front().getLength();
+ const Value *CurrentBase = Checks.front().getBase();
+ const Value *CurrentLength = Checks.front().getLength();
SmallVector<GuardWideningImpl::RangeCheck, 3> CurrentChecks;
@@ -704,8 +721,8 @@ bool GuardWideningImpl::combineRangeChecks(
// Note: std::sort should not invalidate the ChecksStart iterator.
- ConstantInt *MinOffset = CurrentChecks.front().getOffset(),
- *MaxOffset = CurrentChecks.back().getOffset();
+ const ConstantInt *MinOffset = CurrentChecks.front().getOffset();
+ const ConstantInt *MaxOffset = CurrentChecks.back().getOffset();
unsigned BitWidth = MaxOffset->getValue().getBitWidth();
if ((MaxOffset->getValue() - MinOffset->getValue())
@@ -800,6 +817,31 @@ PreservedAnalyses GuardWideningPass::run(Function &F,
return PA;
}
+PreservedAnalyses GuardWideningPass::run(Loop &L, LoopAnalysisManager &AM,
+ LoopStandardAnalysisResults &AR,
+ LPMUpdater &U) {
+
+ const auto &FAM =
+ AM.getResult<FunctionAnalysisManagerLoopProxy>(L, AR).getManager();
+ Function &F = *L.getHeader()->getParent();
+ BranchProbabilityInfo *BPI = nullptr;
+ if (WidenFrequentBranches)
+ BPI = FAM.getCachedResult<BranchProbabilityAnalysis>(F);
+
+ BasicBlock *RootBB = L.getLoopPredecessor();
+ if (!RootBB)
+ RootBB = L.getHeader();
+ auto BlockFilter = [&](BasicBlock *BB) {
+ return BB == RootBB || L.contains(BB);
+ };
+ if (!GuardWideningImpl(AR.DT, nullptr, AR.LI, BPI,
+ AR.DT.getNode(RootBB),
+ BlockFilter).run())
+ return PreservedAnalyses::all();
+
+ return getLoopPassPreservedAnalyses();
+}
+
namespace {
struct GuardWideningLegacyPass : public FunctionPass {
static char ID;
generated by cgit v1.2.3 (git 2.25.1) at 2025-08-09 06:45:46 +0000