206#define DEBUG_TYPE "loop-predication"
208STATISTIC(TotalConsidered,
"Number of guards considered");
229 cl::desc(
"scale factor for the latch probability. Value should be greater "
230 "than 1. Lower values are ignored"));
233 "loop-predication-predicate-widenable-branches-to-deopt",
cl::Hidden,
234 cl::desc(
"Whether or not we should predicate guards "
235 "expressed as widenable branches to deoptimize blocks"),
239 "loop-predication-insert-assumes-of-predicated-guards-conditions",
241 cl::desc(
"Whether or not we should insert assumes of conditions of "
242 "predicated guards"),
254 : Pred(Pred), IV(IV), Limit(Limit) {}
255 LoopICmp() =
default;
257 dbgs() <<
"LoopICmp Pred = " << Pred <<
", IV = " << *IV
258 <<
", Limit = " << *Limit <<
"\n";
262class LoopPredication {
274 bool isSupportedStep(
const SCEV* Step);
275 std::optional<LoopICmp> parseLoopICmp(
ICmpInst *ICI);
276 std::optional<LoopICmp> parseLoopLatchICmp();
293 bool isLoopInvariantValue(
const SCEV* S);
299 std::optional<Value *> widenICmpRangeCheck(
ICmpInst *ICI,
302 std::optional<Value *>
303 widenICmpRangeCheckIncrementingLoop(LoopICmp LatchCheck, LoopICmp RangeCheck,
306 std::optional<Value *>
307 widenICmpRangeCheckDecrementingLoop(LoopICmp LatchCheck, LoopICmp RangeCheck,
318 bool isLoopProfitableToPredicate();
325 : AA(AA), DT(DT), SE(SE), LI(LI), MSSAU(MSSAU){};
326 bool runOnLoop(
Loop *L);
329class LoopPredicationLegacyPass :
public LoopPass {
345 auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
346 auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
347 auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
348 auto *MSSAWP = getAnalysisIfAvailable<MemorySSAWrapperPass>();
349 std::unique_ptr<MemorySSAUpdater> MSSAU;
351 MSSAU = std::make_unique<MemorySSAUpdater>(&MSSAWP->getMSSA());
352 auto *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
353 LoopPredication LP(AA, DT, SE, LI, MSSAU ? MSSAU.get() :
nullptr);
354 return LP.runOnLoop(L);
358char LoopPredicationLegacyPass::ID = 0;
362 "Loop predication",
false,
false)
369 return new LoopPredicationLegacyPass();
375 std::unique_ptr<MemorySSAUpdater> MSSAU;
377 MSSAU = std::make_unique<MemorySSAUpdater>(AR.
MSSA);
378 LoopPredication LP(&AR.
AA, &AR.
DT, &AR.
SE, &AR.
LI,
379 MSSAU ? MSSAU.get() :
nullptr);
380 if (!LP.runOnLoop(&L))
389std::optional<LoopICmp> LoopPredication::parseLoopICmp(
ICmpInst *ICI) {
394 const SCEV *LHSS = SE->getSCEV(LHS);
395 if (isa<SCEVCouldNotCompute>(LHSS))
397 const SCEV *RHSS = SE->getSCEV(RHS);
398 if (isa<SCEVCouldNotCompute>(RHSS))
402 if (SE->isLoopInvariant(LHSS, L)) {
412 return LoopICmp(Pred, AR, RHSS);
420 assert(Ty ==
RHS->
getType() &&
"expandCheck operands have different types?");
422 if (SE->isLoopInvariant(LHS, L) && SE->isLoopInvariant(RHS, L)) {
424 if (SE->isLoopEntryGuardedByCond(L, Pred, LHS, RHS))
436 return Builder.CreateICmp(Pred, LHSV, RHSV);
454 const LoopICmp LatchCheck,
455 Type *RangeCheckType) {
458 assert(
DL.getTypeSizeInBits(LatchCheck.IV->getType()).getFixedValue() >
459 DL.getTypeSizeInBits(RangeCheckType).getFixedValue() &&
460 "Expected latch check IV type to be larger than range check operand "
464 auto *Limit = dyn_cast<SCEVConstant>(LatchCheck.Limit);
465 auto *Start = dyn_cast<SCEVConstant>(LatchCheck.IV->getStart());
466 if (!Limit || !Start)
478 auto RangeCheckTypeBitSize =
479 DL.getTypeSizeInBits(RangeCheckType).getFixedValue();
480 return Start->getAPInt().getActiveBits() < RangeCheckTypeBitSize &&
481 Limit->getAPInt().getActiveBits() < RangeCheckTypeBitSize;
489 const LoopICmp LatchCheck,
490 Type *RangeCheckType) {
492 auto *LatchType = LatchCheck.IV->getType();
493 if (RangeCheckType == LatchType)
496 if (
DL.getTypeSizeInBits(LatchType).getFixedValue() <
497 DL.getTypeSizeInBits(RangeCheckType).getFixedValue())
503 LoopICmp NewLatchCheck;
504 NewLatchCheck.Pred = LatchCheck.Pred;
505 NewLatchCheck.IV = dyn_cast<SCEVAddRecExpr>(
507 if (!NewLatchCheck.IV)
509 NewLatchCheck.Limit = SE.
getTruncateExpr(LatchCheck.Limit, RangeCheckType);
511 <<
"can be represented as range check type:"
512 << *RangeCheckType <<
"\n");
513 LLVM_DEBUG(
dbgs() <<
"LatchCheck.IV: " << *NewLatchCheck.IV <<
"\n");
514 LLVM_DEBUG(
dbgs() <<
"LatchCheck.Limit: " << *NewLatchCheck.Limit <<
"\n");
515 return NewLatchCheck;
518bool LoopPredication::isSupportedStep(
const SCEV* Step) {
524 for (
Value *Op : Ops)
525 if (!
L->isLoopInvariant(Op))
527 return Preheader->getTerminator();
536 for (
const SCEV *Op : Ops)
537 if (!SE->isLoopInvariant(Op, L) ||
540 return Preheader->getTerminator();
543bool LoopPredication::isLoopInvariantValue(
const SCEV* S) {
563 if (SE->isLoopInvariant(S, L))
571 if (
const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S))
572 if (
const auto *LI = dyn_cast<LoadInst>(
U->getValue()))
573 if (LI->isUnordered() &&
L->hasLoopInvariantOperands(LI))
574 if (!
isModSet(AA->getModRefInfoMask(LI->getOperand(0))) ||
575 LI->hasMetadata(LLVMContext::MD_invariant_load))
580std::optional<Value *> LoopPredication::widenICmpRangeCheckIncrementingLoop(
581 LoopICmp LatchCheck, LoopICmp RangeCheck,
SCEVExpander &Expander,
583 auto *Ty = RangeCheck.IV->getType();
590 const SCEV *GuardStart = RangeCheck.IV->getStart();
591 const SCEV *GuardLimit = RangeCheck.Limit;
592 const SCEV *LatchStart = LatchCheck.IV->getStart();
593 const SCEV *LatchLimit = LatchCheck.Limit;
597 if (!isLoopInvariantValue(GuardStart) ||
598 !isLoopInvariantValue(GuardLimit) ||
599 !isLoopInvariantValue(LatchStart) ||
600 !isLoopInvariantValue(LatchLimit)) {
612 SE->getAddExpr(SE->getMinusSCEV(GuardLimit, GuardStart),
613 SE->getMinusSCEV(LatchStart, SE->getOne(Ty)));
614 auto LimitCheckPred =
622 expandCheck(Expander, Guard, LimitCheckPred, LatchLimit, RHS);
623 auto *FirstIterationCheck = expandCheck(Expander, Guard, RangeCheck.Pred,
624 GuardStart, GuardLimit);
627 Builder.CreateAnd(FirstIterationCheck, LimitCheck));
630std::optional<Value *> LoopPredication::widenICmpRangeCheckDecrementingLoop(
631 LoopICmp LatchCheck, LoopICmp RangeCheck,
SCEVExpander &Expander,
633 auto *Ty = RangeCheck.IV->getType();
634 const SCEV *GuardStart = RangeCheck.IV->getStart();
635 const SCEV *GuardLimit = RangeCheck.Limit;
636 const SCEV *LatchStart = LatchCheck.IV->getStart();
637 const SCEV *LatchLimit = LatchCheck.Limit;
641 if (!isLoopInvariantValue(GuardStart) ||
642 !isLoopInvariantValue(GuardLimit) ||
643 !isLoopInvariantValue(LatchStart) ||
644 !isLoopInvariantValue(LatchLimit)) {
655 auto *PostDecLatchCheckIV = LatchCheck.IV->getPostIncExpr(*SE);
656 if (RangeCheck.IV != PostDecLatchCheckIV) {
658 << *PostDecLatchCheckIV
659 <<
" and RangeCheckIV: " << *RangeCheck.IV <<
"\n");
667 auto LimitCheckPred =
669 auto *FirstIterationCheck = expandCheck(Expander, Guard,
671 GuardStart, GuardLimit);
672 auto *LimitCheck = expandCheck(Expander, Guard, LimitCheckPred, LatchLimit,
676 Builder.CreateAnd(FirstIterationCheck, LimitCheck));
684 RC.IV->getStepRecurrence(*SE)->isOne() &&
693std::optional<Value *>
703 auto RangeCheck = parseLoopICmp(ICI);
705 LLVM_DEBUG(
dbgs() <<
"Failed to parse the loop latch condition!\n");
712 << RangeCheck->Pred <<
")!\n");
715 auto *RangeCheckIV = RangeCheck->IV;
716 if (!RangeCheckIV->isAffine()) {
720 auto *Step = RangeCheckIV->getStepRecurrence(*SE);
723 if (!isSupportedStep(Step)) {
724 LLVM_DEBUG(
dbgs() <<
"Range check and latch have IVs different steps!\n");
727 auto *Ty = RangeCheckIV->getType();
729 if (!CurrLatchCheckOpt) {
731 "corresponding to range type: "
736 LoopICmp CurrLatchCheck = *CurrLatchCheckOpt;
740 CurrLatchCheck.IV->getStepRecurrence(*SE)->getType() &&
741 "Range and latch steps should be of same type!");
742 if (Step != CurrLatchCheck.IV->getStepRecurrence(*SE)) {
743 LLVM_DEBUG(
dbgs() <<
"Range and latch have different step values!\n");
748 return widenICmpRangeCheckIncrementingLoop(CurrLatchCheck, *RangeCheck,
752 return widenICmpRangeCheckDecrementingLoop(CurrLatchCheck, *RangeCheck,
761 unsigned NumWidened = 0;
769 Visited.
insert(Condition);
770 Value *WideableCond =
nullptr;
772 Value *Condition = Worklist.pop_back_val();
776 if (Visited.
insert(LHS).second)
777 Worklist.push_back(LHS);
778 if (Visited.
insert(RHS).second)
779 Worklist.push_back(RHS);
784 m_Intrinsic<Intrinsic::experimental_widenable_condition>())) {
786 WideableCond = Condition;
790 if (
ICmpInst *ICI = dyn_cast<ICmpInst>(Condition)) {
791 if (
auto NewRangeCheck = widenICmpRangeCheck(ICI, Expander,
801 }
while (!Worklist.empty());
811bool LoopPredication::widenGuardConditions(
IntrinsicInst *Guard,
818 unsigned NumWidened = collectChecks(Checks, Guard->
getOperand(0), Expander,
823 TotalWidened += NumWidened;
832 Builder.CreateAssumption(OldCond);
840bool LoopPredication::widenWidenableBranchGuardConditions(
849 assert(Parsed &&
"Must be able to parse widenable branch");
854 unsigned NumWidened = collectChecks(Checks, BI->
getCondition(),
859 TotalWidened += NumWidened;
877 PN->addIncoming(Pred == GuardBB ?
Cond :
Builder.getTrue(), Pred);
880 Builder.CreateAssumption(AssumeCond);
884 "Stopped being a guard after transform?");
890std::optional<LoopICmp> LoopPredication::parseLoopLatchICmp() {
891 using namespace PatternMatch;
906 (TrueDest ==
L->getHeader() || BI->
getSuccessor(1) ==
L->getHeader()) &&
907 "One of the latch's destinations must be the header");
914 auto Result = parseLoopICmp(ICI);
916 LLVM_DEBUG(
dbgs() <<
"Failed to parse the loop latch condition!\n");
920 if (TrueDest !=
L->getHeader())
925 if (!
Result->IV->isAffine()) {
930 auto *Step =
Result->IV->getStepRecurrence(*SE);
931 if (!isSupportedStep(Step)) {
932 LLVM_DEBUG(
dbgs() <<
"Unsupported loop stride(" << *Step <<
")!\n");
948 if (IsUnsupportedPredicate(Step,
Result->Pred)) {
957bool LoopPredication::isLoopProfitableToPredicate() {
962 L->getExitEdges(ExitEdges);
965 if (ExitEdges.
size() == 1)
973 auto *LatchBlock =
L->getLoopLatch();
974 assert(LatchBlock &&
"Should have a single latch at this point!");
975 auto *LatchTerm = LatchBlock->getTerminator();
976 assert(LatchTerm->getNumSuccessors() == 2 &&
977 "expected to be an exiting block with 2 succs!");
978 unsigned LatchBrExitIdx =
979 LatchTerm->getSuccessor(0) ==
L->getHeader() ? 1 : 0;
987 auto *LatchExitBlock = LatchTerm->getSuccessor(LatchBrExitIdx);
988 if (isa<UnreachableInst>(LatchTerm) ||
989 LatchExitBlock->getTerminatingDeoptimizeCall())
997 auto ComputeBranchProbability =
1001 unsigned NumSucc =
Term->getNumSuccessors();
1005 uint64_t Numerator = 0, Denominator = 0;
1007 if (
Term->getSuccessor(i) == ExitBlock)
1008 Numerator += Weight;
1009 Denominator += Weight;
1013 assert(LatchBlock != ExitingBlock &&
1014 "Latch term should always have profile data!");
1021 ComputeBranchProbability(LatchBlock, LatchExitBlock);
1026 if (ScaleFactor < 1) {
1029 <<
"Ignored user setting for loop-predication-latch-probability-scale: "
1034 const auto LatchProbabilityThreshold = LatchExitProbability * ScaleFactor;
1036 for (
const auto &ExitEdge : ExitEdges) {
1038 ComputeBranchProbability(ExitEdge.first, ExitEdge.second);
1041 if (ExitingBlockProbability > LatchProbabilityThreshold)
1073 auto *Term = Pred->getTerminator();
1079 return cast<BranchInst>(Term);
1091 L->getExitingBlocks(ExitingBlocks);
1094 for (
BasicBlock *ExitingBB : ExitingBlocks) {
1096 if (isa<SCEVCouldNotCompute>(ExitCount))
1099 "We should only have known counts for exiting blocks that "
1103 if (ExitCounts.
size() < 2)
1134 L->getExitingBlocks(ExitingBlocks);
1136 if (ExitingBlocks.
empty())
1139 auto *Latch =
L->getLoopLatch();
1147 const SCEV *LatchEC = SE->getExitCount(L, Latch);
1148 if (isa<SCEVCouldNotCompute>(LatchEC))
1157 bool ChangedLoop =
false;
1159 for (
auto *ExitingBB : ExitingBlocks) {
1160 if (LI->getLoopFor(ExitingBB) != L)
1163 auto *BI = dyn_cast<BranchInst>(ExitingBB->getTerminator());
1170 L->contains(IfTrueBB)) {
1186 !SE->isLoopInvariant(MinEC, L) ||
1187 !
Rewriter.isSafeToExpandAt(MinEC, WidenableBR))
1194 auto *IP = cast<Instruction>(WidenableBR->getCondition());
1197 IP->moveBefore(WidenableBR);
1199 if (
auto *MUD = MSSAU->getMemorySSA()->getMemoryAccess(IP))
1200 MSSAU->moveToPlace(MUD, WidenableBR->getParent(),
1205 bool InvalidateLoop =
false;
1206 Value *MinECV =
nullptr;
1207 for (
BasicBlock *ExitingBB : ExitingBlocks) {
1211 if (LI->getLoopFor(ExitingBB) != L)
1215 auto *BI = dyn_cast<BranchInst>(ExitingBB->getTerminator());
1223 const SCEV *ExitCount = SE->getExitCount(L, ExitingBB);
1224 if (isa<SCEVCouldNotCompute>(ExitCount) ||
1226 !
Rewriter.isSafeToExpandAt(ExitCount, WidenableBR))
1229 const bool ExitIfTrue = !
L->contains(*
succ_begin(ExitingBB));
1244 MinECV =
Rewriter.expandCodeFor(MinEC);
1248 ECV =
B.CreateZExt(ECV, WiderTy);
1249 RHS =
B.CreateZExt(RHS, WiderTy);
1251 assert(!Latch || DT->dominates(ExitingBB, Latch));
1256 NewCond =
B.CreateFreeze(NewCond);
1262 InvalidateLoop =
true;
1276bool LoopPredication::runOnLoop(
Loop *
Loop) {
1282 Module *
M =
L->getHeader()->getModule();
1287 bool HasIntrinsicGuards = GuardDecl && !GuardDecl->use_empty();
1288 auto *WCDecl =
M->getFunction(
1290 bool HasWidenableConditions =
1292 if (!HasIntrinsicGuards && !HasWidenableConditions)
1295 DL = &
M->getDataLayout();
1297 Preheader =
L->getLoopPreheader();
1301 auto LatchCheckOpt = parseLoopLatchICmp();
1304 LatchCheck = *LatchCheckOpt;
1309 if (!isLoopProfitableToPredicate()) {
1317 for (
const auto BB :
L->blocks()) {
1324 cast<BranchInst>(BB->getTerminator()));
1328 bool Changed =
false;
1329 for (
auto *Guard : Guards)
1330 Changed |= widenGuardConditions(Guard, Expander);
1331 for (
auto *Guard : GuardsAsWidenableBranches)
1332 Changed |= widenWidenableBranchGuardConditions(Guard, Expander);
1333 Changed |= predicateLoopExits(L, Expander);
1336 MSSAU->getMemorySSA()->verifyMemorySSA();
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
SmallVector< MachineOperand, 4 > Cond
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static cl::opt< bool > SkipProfitabilityChecks("irce-skip-profitability-checks", cl::Hidden, cl::init(false))
static cl::opt< float > LatchExitProbabilityScale("loop-predication-latch-probability-scale", cl::Hidden, cl::init(2.0), cl::desc("scale factor for the latch probability. Value should be greater " "than 1. Lower values are ignored"))
static void normalizePredicate(ScalarEvolution *SE, Loop *L, LoopICmp &RC)
static cl::opt< bool > SkipProfitabilityChecks("loop-predication-skip-profitability-checks", cl::Hidden, cl::init(false))
static const SCEV * getMinAnalyzeableBackedgeTakenCount(ScalarEvolution &SE, DominatorTree &DT, Loop *L)
Return the minimum of all analyzeable exit counts.
static cl::opt< bool > EnableCountDownLoop("loop-predication-enable-count-down-loop", cl::Hidden, cl::init(true))
static cl::opt< bool > EnableIVTruncation("loop-predication-enable-iv-truncation", cl::Hidden, cl::init(true))
static std::optional< LoopICmp > generateLoopLatchCheck(const DataLayout &DL, ScalarEvolution &SE, const LoopICmp LatchCheck, Type *RangeCheckType)
static cl::opt< bool > PredicateWidenableBranchGuards("loop-predication-predicate-widenable-branches-to-deopt", cl::Hidden, cl::desc("Whether or not we should predicate guards " "expressed as widenable branches to deoptimize blocks"), cl::init(true))
static bool isSafeToTruncateWideIVType(const DataLayout &DL, ScalarEvolution &SE, const LoopICmp LatchCheck, Type *RangeCheckType)
static cl::opt< bool > InsertAssumesOfPredicatedGuardsConditions("loop-predication-insert-assumes-of-predicated-guards-conditions", cl::Hidden, cl::desc("Whether or not we should insert assumes of conditions of " "predicated guards"), cl::init(true))
static BranchInst * FindWidenableTerminatorAboveLoop(Loop *L, LoopInfo &LI)
If we can (cheaply) find a widenable branch which controls entry into the loop, return it.
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)
This file contains the declarations for profiling metadata utility functions.
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)
Virtual Register Rewriter
A container for analyses that lazily runs them and caches their results.
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
LLVM Basic Block Representation.
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
InstListType::iterator iterator
Instruction iterators...
LLVMContext & getContext() const
Get the context in which this basic block lives.
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...
const CallInst * getPostdominatingDeoptimizeCall() const
Returns the call instruction calling @llvm.experimental.deoptimize that is present either in current ...
Conditional or Unconditional Branch instruction.
void setCondition(Value *V)
bool isConditional() const
BasicBlock * getSuccessor(unsigned i) const
Value * getCondition() const
Legacy analysis pass which computes BranchProbabilityInfo.
static BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
@ ICMP_SLT
signed less than
@ ICMP_SLE
signed less or equal
@ ICMP_UGE
unsigned greater or equal
@ ICMP_UGT
unsigned greater than
@ ICMP_SGT
signed greater than
@ ICMP_ULT
unsigned less than
@ ICMP_SGE
signed greater or equal
@ ICMP_ULE
unsigned less or equal
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
Predicate getPredicate() const
Return the predicate for this instruction.
Predicate getFlippedStrictnessPredicate() const
For predicate of kind "is X or equal to 0" returns the predicate "is X".
static ConstantInt * getTrue(LLVMContext &Context)
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
A parsed version of the target data layout string in and methods for querying it.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
This instruction compares its operands according to the predicate given to the constructor.
bool isEquality() const
Return true if this predicate is either EQ or NE.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
const BasicBlock * getParent() const
A wrapper class for inspecting calls to intrinsic functions.
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
virtual bool runOnLoop(Loop *L, LPPassManager &LPM)=0
bool skipLoop(const Loop *L) const
Optional passes call this function to check whether the pass should be skipped.
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.
A Module instance is used to store all the information related to an LLVM module.
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 Loop * getLoop() const
This class uses information about analyze scalars to rewrite expressions in canonical form.
bool isSafeToExpandAt(const SCEV *S, const Instruction *InsertionPoint) const
Return true if the given expression is safe to expand in the sense that all materialized values are d...
Value * expandCodeFor(const SCEV *SH, Type *Ty, Instruction *I)
Insert code to directly compute the specified SCEV expression into the program.
This means that we are dealing with an entirely unknown SCEV value, and only represent it as its LLVM...
This class represents an analyzed expression in the program.
bool isOne() const
Return true if the expression is a constant one.
bool isAllOnesValue() const
Return true if the expression is a constant all-ones value.
Type * getType() const
Return the LLVM type of this SCEV expression.
The main scalar evolution driver.
bool isKnownPredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
const SCEV * getTruncateExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
const SCEV * getUMinFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS, bool Sequential=false)
Promote the operands to the wider of the types using zero-extension, and then perform a umin operatio...
std::optional< MonotonicPredicateType > getMonotonicPredicateType(const SCEVAddRecExpr *LHS, ICmpInst::Predicate Pred)
If, for all loop invariant X, the predicate "LHS `Pred` X" is monotonically increasing or decreasing,...
const SCEV * getCouldNotCompute()
const SCEV * getExitCount(const Loop *L, const BasicBlock *ExitingBlock, ExitCountKind Kind=Exact)
Return the number of times the backedge executes before the given exit would be taken; if not exactly...
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
The instances of the Type class are immutable: once they are created, they are never changed.
bool isPointerTy() const
True if this is an instance of PointerType.
A Use represents the edge between a Value definition and its users.
void setOperand(unsigned i, Value *Val)
Value * getOperand(unsigned i) const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
void dump() const
Support for debugging, callable in GDB: V->dump()
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
StringRef getName(ID id)
Return the LLVM name for an intrinsic, such as "llvm.ppc.altivec.lvx".
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
bool match(Val *V, const Pattern &P)
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
initializer< Ty > init(const Ty &Val)
This is an optimization pass for GlobalISel generic memory operations.
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())
If the specified value is a trivially dead instruction, delete it.
auto enumerate(FirstRange &&First, RestRanges &&...Rest)
Given two or more input ranges, returns a new range whose values are are tuples (A,...
void widenWidenableBranch(BranchInst *WidenableBR, Value *NewCond)
Given a branch we know is widenable (defined per Analysis/GuardUtils.h), widen it such that condition...
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
bool isGuard(const User *U)
Returns true iff U has semantics of a guard expressed in a form of call of llvm.experimental....
Pass * createLoopPredicationPass()
MDNode * getValidBranchWeightMDNode(const Instruction &I)
Get the valid branch weights metadata node.
bool isModSet(const ModRefInfo MRI)
bool parseWidenableBranch(const User *U, Value *&Condition, Value *&WidenableCondition, BasicBlock *&IfTrueBB, BasicBlock *&IfFalseBB)
If U is widenable branch looking like: cond = ... wc = call i1 @llvm.experimental....
bool hasValidBranchWeightMD(const Instruction &I)
Checks if an instructions has valid Branch Weight Metadata.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass's AnalysisUsage.
bool VerifyMemorySSA
Enables verification of MemorySSA.
bool isGuardAsWidenableBranch(const User *U)
Returns true iff U has semantics of a guard expressed in a form of a widenable conditional branch to ...
bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)
Extract branch weights from MD_prof metadata.
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
auto predecessors(const MachineBasicBlock *BB)
void initializeLoopPredicationLegacyPassPass(PassRegistry &)
unsigned pred_size(const MachineBasicBlock *BB)
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...