22#include "llvm/Config/llvm-config.h"
48#define DEBUG_TYPE "loop-term-fold"
51 "Number of terminating condition fold recognized and performed");
53static std::optional<std::tuple<PHINode *, PHINode *, const SCEV *, bool>>
56 if (!L->isInnermost()) {
61 if (!L->isLoopSimplifyForm()) {
67 LLVM_DEBUG(
dbgs() <<
"Cannot fold on backedge that is loop variant\n");
78 dbgs() <<
"Cannot fold on branching condition that is not an ICmpInst");
81 if (!TermCond->hasOneUse()) {
84 <<
"Cannot replace terminating condition with more than one use\n");
89 Value *
RHS = TermCond->getOperand(1);
90 if (!
LHS || !L->isLoopInvariant(
RHS))
97 Value *ToFoldStart, *ToFoldStep;
102 if (ToFold->
getParent() != L->getHeader())
112 const unsigned ExpansionBudget = [&]() {
115 return std::min(Budget, SmallTC);
117 return std::min(Budget, *SmallTC);
127 const SCEV *TermValueS =
nullptr;
128 bool MustDropPoison =
false;
129 auto InsertPt = L->getLoopPreheader()->getTerminator();
130 for (
PHINode &PN : L->getHeader()->phis()) {
136 <<
"' is not SCEV-able, not qualified for the "
137 "terminating condition folding.\n");
142 if (!AddRec || !AddRec->
isAffine()) {
144 <<
"' is not an affine add recursion, not qualified "
145 "for the terminating condition folding.\n");
163 const SCEV *TermValueSLocal =
PostInc->evaluateAtIteration(BECount, SE);
166 dbgs() <<
"Is not safe to expand terminating value for phi node" << PN
174 dbgs() <<
"Is too expensive to expand terminating value for phi node"
182 LLVM_DEBUG(
dbgs() <<
"Can not prove poison safety for IV " << PN <<
"\n");
190 bool MustDropPoisonLocal =
false;
192 cast<Instruction>(PN.getIncomingValueForBlock(LoopLatch));
195 LLVM_DEBUG(
dbgs() <<
"Can not prove poison safety to insert use" << PN
212 TermValueS = TermValueSLocal;
213 MustDropPoison = MustDropPoisonLocal;
217 <<
"Cannot find other AddRec IV to help folding\n";);
220 <<
"\nFound loop that can fold terminating condition\n"
222 <<
" TermCond: " << *TermCond <<
"\n"
223 <<
" BrandInst: " << *BI <<
"\n"
224 <<
" ToFold: " << *ToFold <<
"\n"
225 <<
" ToHelpFold: " << *ToHelpFold <<
"\n");
227 if (!ToFold || !ToHelpFold)
229 return std::make_tuple(ToFold, ToHelpFold, TermValueS, MustDropPoison);
235 std::unique_ptr<MemorySSAUpdater> MSSAU;
237 MSSAU = std::make_unique<MemorySSAUpdater>(MSSA);
243 auto [ToFold, ToHelpFold, TermValueS, MustDrop] = *Opt;
247 BasicBlock *LoopPreheader = L->getLoopPreheader();
253 <<
"New term-cond phi-node:\n"
254 << *ToHelpFold <<
"\n");
256 Value *StartValue = ToHelpFold->getIncomingValueForBlock(LoopPreheader);
258 Value *LoopValue = ToHelpFold->getIncomingValueForBlock(LoopLatch);
262 cast<Instruction>(LoopValue)->dropPoisonGeneratingFlags();
269 "Terminating value was checked safe in canFoldTerminatingCondition");
276 << *StartValue <<
"\n"
277 <<
"Terminating value of new term-cond phi-node:\n"
278 << *TermValue <<
"\n");
286 "lsr_fold_term_cond.replaced_term_cond");
292 << *OldTermCond <<
"\n"
293 <<
"New term-cond:\n"
294 << *NewTermCond <<
"\n");
306class LoopTermFold :
public LoopPass {
323void LoopTermFold::getAnalysisUsage(
AnalysisUsage &AU)
const {
341 auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
342 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
343 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
344 const auto &
TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(
345 *
L->getHeader()->getParent());
346 auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
347 *
L->getHeader()->getParent());
348 auto *MSSAAnalysis = getAnalysisIfAvailable<MemorySSAWrapperPass>();
351 MSSA = &MSSAAnalysis->getMSSA();
367char LoopTermFold::ID = 0;
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
This header provides classes for managing per-loop analyses.
static std::optional< std::tuple< PHINode *, PHINode *, const SCEV *, bool > > canFoldTermCondOfLoop(Loop *L, ScalarEvolution &SE, DominatorTree &DT, const LoopInfo &LI, const TargetTransformInfo &TTI)
loop term Loop Terminator Folding
static bool RunTermFold(Loop *L, ScalarEvolution &SE, DominatorTree &DT, LoopInfo &LI, const TargetTransformInfo &TTI, TargetLibraryInfo &TLI, MemorySSA *MSSA)
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
Module.h This file contains the declarations for the Module class.
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
A container for analyses that lazily runs them and caches their results.
Represent the analysis usage information of a pass.
AnalysisUsage & addRequiredID(const void *ID)
AnalysisUsage & addPreservedID(const void *ID)
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
LLVM Basic Block Representation.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Conditional or Unconditional Branch instruction.
void setCondition(Value *V)
void swapSuccessors()
Swap the successors of this branch instruction.
BasicBlock * getSuccessor(unsigned i) const
bool isUnconditional() const
Value * getCondition() const
A parsed version of the target data layout string in and methods for querying it.
Legacy analysis pass which computes a DominatorTree.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
This instruction compares its operands according to the predicate given to the constructor.
Value * CreateICmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="")
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
bool hasPoisonGeneratingFlags() const LLVM_READONLY
Return true if this operator has flags which may cause this instruction to evaluate to poison despite...
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
The legacy pass manager's analysis pass to compute loop information.
virtual bool runOnLoop(Loop *L, LPPassManager &LPM)=0
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
Represents a single loop in the control flow graph.
An analysis that produces MemorySSA for a function.
Legacy analysis pass which computes MemorySSA.
Encapsulates MemorySSA, including all data associated with memory accesses.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Pass interface - Implemented by all 'passes'.
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
This node represents a polynomial recurrence on the trip count of the specified loop.
const SCEV * getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
bool isAffine() const
Return true if this represents an expression A + B*x where A and B are loop invariant values.
const SCEVAddRecExpr * getPostIncExpr(ScalarEvolution &SE) const
Return an expression representing the value of this expression one iteration of the loop ahead.
This class uses information about analyze scalars to rewrite expressions in canonical form.
bool isSafeToExpand(const SCEV *S) const
Return true if the given expression is safe to expand in the sense that all materialized values are s...
bool isHighCostExpansion(ArrayRef< const SCEV * > Exprs, Loop *L, unsigned Budget, const TargetTransformInfo *TTI, const Instruction *At)
Return true for expressions that can't be evaluated at runtime within given Budget.
void clear()
Erase the contents of the InsertedExpressions map so that users trying to expand the same expression ...
Value * expandCodeFor(const SCEV *SH, Type *Ty, BasicBlock::iterator I)
Insert code to directly compute the specified SCEV expression into the program.
bool hasNoSelfWrap() const
This class represents an analyzed expression in the program.
The main scalar evolution driver.
bool isKnownNonZero(const SCEV *S)
Test if the given expression is known to be non-zero.
const SCEV * getBackedgeTakenCount(const Loop *L, ExitCountKind Kind=Exact)
If the specified loop has a predictable backedge-taken count, return it, otherwise return a SCEVCould...
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
unsigned getSmallConstantMaxTripCount(const Loop *L)
Returns the upper bound of the loop trip count as a normal unsigned value.
bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
bool hasLoopInvariantBackedgeTakenCount(const Loop *L)
Return true if the specified loop has an analyzable loop-invariant backedge-taken count.
Provides information about what library functions are available for the current target.
Value * getOperand(unsigned i) const
LLVM Value Representation.
const ParentTy * getParent() const
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
This is an optimization pass for GlobalISel generic memory operations.
bool mustExecuteUBIfPoisonOnPathTo(Instruction *Root, Instruction *OnPathTo, DominatorTree *DT)
Return true if undefined behavior would provable be executed on the path to OnPathTo if Root produced...
std::optional< unsigned > getLoopEstimatedTripCount(Loop *L, unsigned *EstimatedLoopInvocationWeight=nullptr)
Returns a loop's estimated trip count based on branch weight metadata.
Pass * createLoopTermFoldPass()
bool matchSimpleRecurrence(const PHINode *P, BinaryOperator *&BO, Value *&Start, Value *&Step)
Attempt to match a simple first order recurrence cycle of the form: iv = phi Ty [Start,...
bool DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Examine each PHI in the given block and delete it if it is dead.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
cl::opt< unsigned > SCEVCheapExpansionBudget
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
bool isAlmostDeadIV(PHINode *IV, BasicBlock *LatchBlock, Value *Cond)
Return true if the induction variable IV in a Loop whose latch is LatchBlock would become dead if the...
void initializeLoopTermFoldPass(PassRegistry &)
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
TargetTransformInfo & TTI