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);
626 return Builder.CreateAnd(FirstIterationCheck, LimitCheck);
629std::optional<Value *> LoopPredication::widenICmpRangeCheckDecrementingLoop(
630 LoopICmp LatchCheck, LoopICmp RangeCheck,
SCEVExpander &Expander,
632 auto *Ty = RangeCheck.IV->getType();
633 const SCEV *GuardStart = RangeCheck.IV->getStart();
634 const SCEV *GuardLimit = RangeCheck.Limit;
635 const SCEV *LatchStart = LatchCheck.IV->getStart();
636 const SCEV *LatchLimit = LatchCheck.Limit;
640 if (!isLoopInvariantValue(GuardStart) ||
641 !isLoopInvariantValue(GuardLimit) ||
642 !isLoopInvariantValue(LatchStart) ||
643 !isLoopInvariantValue(LatchLimit)) {
654 auto *PostDecLatchCheckIV = LatchCheck.IV->getPostIncExpr(*SE);
655 if (RangeCheck.IV != PostDecLatchCheckIV) {
657 << *PostDecLatchCheckIV
658 <<
" and RangeCheckIV: " << *RangeCheck.IV <<
"\n");
666 auto LimitCheckPred =
668 auto *FirstIterationCheck = expandCheck(Expander, Guard,
670 GuardStart, GuardLimit);
671 auto *LimitCheck = expandCheck(Expander, Guard, LimitCheckPred, LatchLimit,
674 return Builder.CreateAnd(FirstIterationCheck, LimitCheck);
682 RC.IV->getStepRecurrence(*SE)->isOne() &&
691std::optional<Value *>
701 auto RangeCheck = parseLoopICmp(ICI);
703 LLVM_DEBUG(
dbgs() <<
"Failed to parse the loop latch condition!\n");
710 << RangeCheck->Pred <<
")!\n");
713 auto *RangeCheckIV = RangeCheck->IV;
714 if (!RangeCheckIV->isAffine()) {
718 auto *Step = RangeCheckIV->getStepRecurrence(*SE);
721 if (!isSupportedStep(Step)) {
722 LLVM_DEBUG(
dbgs() <<
"Range check and latch have IVs different steps!\n");
725 auto *Ty = RangeCheckIV->getType();
727 if (!CurrLatchCheckOpt) {
729 "corresponding to range type: "
734 LoopICmp CurrLatchCheck = *CurrLatchCheckOpt;
738 CurrLatchCheck.IV->getStepRecurrence(*SE)->getType() &&
739 "Range and latch steps should be of same type!");
740 if (Step != CurrLatchCheck.IV->getStepRecurrence(*SE)) {
741 LLVM_DEBUG(
dbgs() <<
"Range and latch have different step values!\n");
746 return widenICmpRangeCheckIncrementingLoop(CurrLatchCheck, *RangeCheck,
750 return widenICmpRangeCheckDecrementingLoop(CurrLatchCheck, *RangeCheck,
759 unsigned NumWidened = 0;
767 Visited.
insert(Condition);
768 Value *WideableCond =
nullptr;
770 Value *Condition = Worklist.pop_back_val();
774 if (Visited.
insert(LHS).second)
775 Worklist.push_back(LHS);
776 if (Visited.
insert(RHS).second)
777 Worklist.push_back(RHS);
782 m_Intrinsic<Intrinsic::experimental_widenable_condition>())) {
784 WideableCond = Condition;
788 if (
ICmpInst *ICI = dyn_cast<ICmpInst>(Condition)) {
789 if (
auto NewRangeCheck = widenICmpRangeCheck(ICI, Expander,
799 }
while (!Worklist.empty());
809bool LoopPredication::widenGuardConditions(
IntrinsicInst *Guard,
816 unsigned NumWidened = collectChecks(Checks, Guard->
getOperand(0), Expander,
821 TotalWidened += NumWidened;
830 Builder.CreateAssumption(OldCond);
838bool LoopPredication::widenWidenableBranchGuardConditions(
847 assert(Parsed &&
"Must be able to parse widenable branch");
852 unsigned NumWidened = collectChecks(Checks, BI->
getCondition(),
857 TotalWidened += NumWidened;
875 PN->addIncoming(Pred == GuardBB ?
Cond :
Builder.getTrue(), Pred);
878 Builder.CreateAssumption(AssumeCond);
882 "Stopped being a guard after transform?");
888std::optional<LoopICmp> LoopPredication::parseLoopLatchICmp() {
889 using namespace PatternMatch;
904 (TrueDest ==
L->getHeader() || BI->
getSuccessor(1) ==
L->getHeader()) &&
905 "One of the latch's destinations must be the header");
912 auto Result = parseLoopICmp(ICI);
914 LLVM_DEBUG(
dbgs() <<
"Failed to parse the loop latch condition!\n");
918 if (TrueDest !=
L->getHeader())
923 if (!
Result->IV->isAffine()) {
928 auto *Step =
Result->IV->getStepRecurrence(*SE);
929 if (!isSupportedStep(Step)) {
930 LLVM_DEBUG(
dbgs() <<
"Unsupported loop stride(" << *Step <<
")!\n");
946 if (IsUnsupportedPredicate(Step,
Result->Pred)) {
955bool LoopPredication::isLoopProfitableToPredicate() {
960 L->getExitEdges(ExitEdges);
963 if (ExitEdges.
size() == 1)
971 auto *LatchBlock =
L->getLoopLatch();
972 assert(LatchBlock &&
"Should have a single latch at this point!");
973 auto *LatchTerm = LatchBlock->getTerminator();
974 assert(LatchTerm->getNumSuccessors() == 2 &&
975 "expected to be an exiting block with 2 succs!");
976 unsigned LatchBrExitIdx =
977 LatchTerm->getSuccessor(0) ==
L->getHeader() ? 1 : 0;
985 auto *LatchExitBlock = LatchTerm->getSuccessor(LatchBrExitIdx);
986 if (isa<UnreachableInst>(LatchTerm) ||
987 LatchExitBlock->getTerminatingDeoptimizeCall())
995 auto ComputeBranchProbability =
999 unsigned NumSucc =
Term->getNumSuccessors();
1003 uint64_t Numerator = 0, Denominator = 0;
1005 if (
Term->getSuccessor(i) == ExitBlock)
1006 Numerator += Weight;
1007 Denominator += Weight;
1011 assert(LatchBlock != ExitingBlock &&
1012 "Latch term should always have profile data!");
1019 ComputeBranchProbability(LatchBlock, LatchExitBlock);
1024 if (ScaleFactor < 1) {
1027 <<
"Ignored user setting for loop-predication-latch-probability-scale: "
1032 const auto LatchProbabilityThreshold = LatchExitProbability * ScaleFactor;
1034 for (
const auto &ExitEdge : ExitEdges) {
1036 ComputeBranchProbability(ExitEdge.first, ExitEdge.second);
1039 if (ExitingBlockProbability > LatchProbabilityThreshold)
1071 auto *Term = Pred->getTerminator();
1077 return cast<BranchInst>(Term);
1089 L->getExitingBlocks(ExitingBlocks);
1092 for (
BasicBlock *ExitingBB : ExitingBlocks) {
1094 if (isa<SCEVCouldNotCompute>(ExitCount))
1097 "We should only have known counts for exiting blocks that "
1101 if (ExitCounts.
size() < 2)
1132 L->getExitingBlocks(ExitingBlocks);
1134 if (ExitingBlocks.
empty())
1137 auto *Latch =
L->getLoopLatch();
1145 const SCEV *LatchEC = SE->getExitCount(L, Latch);
1146 if (isa<SCEVCouldNotCompute>(LatchEC))
1155 bool ChangedLoop =
false;
1157 for (
auto *ExitingBB : ExitingBlocks) {
1158 if (LI->getLoopFor(ExitingBB) != L)
1161 auto *BI = dyn_cast<BranchInst>(ExitingBB->getTerminator());
1168 L->contains(IfTrueBB)) {
1184 !SE->isLoopInvariant(MinEC, L) ||
1185 !
Rewriter.isSafeToExpandAt(MinEC, WidenableBR))
1192 auto *IP = cast<Instruction>(WidenableBR->getCondition());
1195 IP->moveBefore(WidenableBR);
1197 if (
auto *MUD = MSSAU->getMemorySSA()->getMemoryAccess(IP))
1198 MSSAU->moveToPlace(MUD, WidenableBR->getParent(),
1203 bool InvalidateLoop =
false;
1204 Value *MinECV =
nullptr;
1205 for (
BasicBlock *ExitingBB : ExitingBlocks) {
1209 if (LI->getLoopFor(ExitingBB) != L)
1213 auto *BI = dyn_cast<BranchInst>(ExitingBB->getTerminator());
1221 const SCEV *ExitCount = SE->getExitCount(L, ExitingBB);
1222 if (isa<SCEVCouldNotCompute>(ExitCount) ||
1224 !
Rewriter.isSafeToExpandAt(ExitCount, WidenableBR))
1227 const bool ExitIfTrue = !
L->contains(*
succ_begin(ExitingBB));
1242 MinECV =
Rewriter.expandCodeFor(MinEC);
1246 ECV =
B.CreateZExt(ECV, WiderTy);
1247 RHS =
B.CreateZExt(RHS, WiderTy);
1249 assert(!Latch || DT->dominates(ExitingBB, Latch));
1254 NewCond =
B.CreateFreeze(NewCond);
1260 InvalidateLoop =
true;
1274bool LoopPredication::runOnLoop(
Loop *
Loop) {
1280 Module *
M =
L->getHeader()->getModule();
1285 bool HasIntrinsicGuards = GuardDecl && !GuardDecl->use_empty();
1286 auto *WCDecl =
M->getFunction(
1288 bool HasWidenableConditions =
1290 if (!HasIntrinsicGuards && !HasWidenableConditions)
1293 DL = &
M->getDataLayout();
1295 Preheader =
L->getLoopPreheader();
1299 auto LatchCheckOpt = parseLoopLatchICmp();
1302 LatchCheck = *LatchCheckOpt;
1307 if (!isLoopProfitableToPredicate()) {
1315 for (
const auto BB :
L->blocks()) {
1322 cast<BranchInst>(BB->getTerminator()));
1326 bool Changed =
false;
1327 for (
auto *Guard : Guards)
1328 Changed |= widenGuardConditions(Guard, Expander);
1329 for (
auto *Guard : GuardsAsWidenableBranches)
1330 Changed |= widenWidenableBranchGuardConditions(Guard, Expander);
1331 Changed |= predicateLoopExits(L, Expander);
1334 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...