205#define DEBUG_TYPE "loop-predication"
207STATISTIC(TotalConsidered,
"Number of guards considered");
228 cl::desc(
"scale factor for the latch probability. Value should be greater "
229 "than 1. Lower values are ignored"));
232 "loop-predication-predicate-widenable-branches-to-deopt",
cl::Hidden,
233 cl::desc(
"Whether or not we should predicate guards "
234 "expressed as widenable branches to deoptimize blocks"),
238 "loop-predication-insert-assumes-of-predicated-guards-conditions",
240 cl::desc(
"Whether or not we should insert assumes of conditions of "
241 "predicated guards"),
253 : Pred(Pred), IV(IV), Limit(Limit) {}
254 LoopICmp() =
default;
256 dbgs() <<
"LoopICmp Pred = " << Pred <<
", IV = " << *IV
257 <<
", Limit = " << *Limit <<
"\n";
261class LoopPredication {
273 bool isSupportedStep(
const SCEV* Step);
274 std::optional<LoopICmp> parseLoopICmp(
ICmpInst *ICI);
275 std::optional<LoopICmp> parseLoopLatchICmp();
292 bool isLoopInvariantValue(
const SCEV* S);
298 std::optional<Value *> widenICmpRangeCheck(
ICmpInst *ICI,
301 std::optional<Value *>
302 widenICmpRangeCheckIncrementingLoop(LoopICmp LatchCheck, LoopICmp RangeCheck,
305 std::optional<Value *>
306 widenICmpRangeCheckDecrementingLoop(LoopICmp LatchCheck, LoopICmp RangeCheck,
318 bool isLoopProfitableToPredicate();
325 : AA(AA), DT(DT), SE(SE), LI(LI), MSSAU(MSSAU){};
326 bool runOnLoop(
Loop *L);
334 std::unique_ptr<MemorySSAUpdater> MSSAU;
336 MSSAU = std::make_unique<MemorySSAUpdater>(AR.
MSSA);
337 LoopPredication LP(&AR.
AA, &AR.
DT, &AR.
SE, &AR.
LI,
338 MSSAU ? MSSAU.get() :
nullptr);
339 if (!LP.runOnLoop(&L))
348std::optional<LoopICmp> LoopPredication::parseLoopICmp(
ICmpInst *ICI) {
353 const SCEV *LHSS = SE->getSCEV(LHS);
354 if (isa<SCEVCouldNotCompute>(LHSS))
356 const SCEV *RHSS = SE->getSCEV(RHS);
357 if (isa<SCEVCouldNotCompute>(RHSS))
361 if (SE->isLoopInvariant(LHSS, L)) {
371 return LoopICmp(Pred, AR, RHSS);
379 assert(Ty ==
RHS->
getType() &&
"expandCheck operands have different types?");
381 if (SE->isLoopInvariant(LHS, L) && SE->isLoopInvariant(RHS, L)) {
383 if (SE->isLoopEntryGuardedByCond(L, Pred, LHS, RHS))
384 return Builder.getTrue();
387 return Builder.getFalse();
394 IRBuilder<> Builder(findInsertPt(Guard, {LHSV, RHSV}));
395 return Builder.CreateICmp(Pred, LHSV, RHSV);
413 const LoopICmp LatchCheck,
414 Type *RangeCheckType) {
417 assert(
DL.getTypeSizeInBits(LatchCheck.IV->getType()).getFixedValue() >
418 DL.getTypeSizeInBits(RangeCheckType).getFixedValue() &&
419 "Expected latch check IV type to be larger than range check operand "
423 auto *Limit = dyn_cast<SCEVConstant>(LatchCheck.Limit);
424 auto *Start = dyn_cast<SCEVConstant>(LatchCheck.IV->getStart());
425 if (!Limit || !Start)
437 auto RangeCheckTypeBitSize =
438 DL.getTypeSizeInBits(RangeCheckType).getFixedValue();
439 return Start->getAPInt().getActiveBits() < RangeCheckTypeBitSize &&
440 Limit->getAPInt().getActiveBits() < RangeCheckTypeBitSize;
448 const LoopICmp LatchCheck,
449 Type *RangeCheckType) {
451 auto *LatchType = LatchCheck.IV->getType();
452 if (RangeCheckType == LatchType)
455 if (
DL.getTypeSizeInBits(LatchType).getFixedValue() <
456 DL.getTypeSizeInBits(RangeCheckType).getFixedValue())
462 LoopICmp NewLatchCheck;
463 NewLatchCheck.Pred = LatchCheck.Pred;
464 NewLatchCheck.IV = dyn_cast<SCEVAddRecExpr>(
466 if (!NewLatchCheck.IV)
468 NewLatchCheck.Limit = SE.
getTruncateExpr(LatchCheck.Limit, RangeCheckType);
470 <<
"can be represented as range check type:"
471 << *RangeCheckType <<
"\n");
472 LLVM_DEBUG(
dbgs() <<
"LatchCheck.IV: " << *NewLatchCheck.IV <<
"\n");
473 LLVM_DEBUG(
dbgs() <<
"LatchCheck.Limit: " << *NewLatchCheck.Limit <<
"\n");
474 return NewLatchCheck;
477bool LoopPredication::isSupportedStep(
const SCEV* Step) {
484 if (!
L->isLoopInvariant(
Op))
486 return Preheader->getTerminator();
495 for (
const SCEV *
Op : Ops)
496 if (!SE->isLoopInvariant(
Op, L) ||
499 return Preheader->getTerminator();
502bool LoopPredication::isLoopInvariantValue(
const SCEV* S) {
522 if (SE->isLoopInvariant(S, L))
530 if (
const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S))
531 if (
const auto *LI = dyn_cast<LoadInst>(
U->getValue()))
532 if (LI->isUnordered() &&
L->hasLoopInvariantOperands(LI))
533 if (!
isModSet(AA->getModRefInfoMask(LI->getOperand(0))) ||
534 LI->hasMetadata(LLVMContext::MD_invariant_load))
539std::optional<Value *> LoopPredication::widenICmpRangeCheckIncrementingLoop(
540 LoopICmp LatchCheck, LoopICmp RangeCheck,
SCEVExpander &Expander,
542 auto *Ty = RangeCheck.IV->getType();
549 const SCEV *GuardStart = RangeCheck.IV->getStart();
550 const SCEV *GuardLimit = RangeCheck.Limit;
551 const SCEV *LatchStart = LatchCheck.IV->getStart();
552 const SCEV *LatchLimit = LatchCheck.Limit;
556 if (!isLoopInvariantValue(GuardStart) ||
557 !isLoopInvariantValue(GuardLimit) ||
558 !isLoopInvariantValue(LatchStart) ||
559 !isLoopInvariantValue(LatchLimit)) {
571 SE->getAddExpr(SE->getMinusSCEV(GuardLimit, GuardStart),
572 SE->getMinusSCEV(LatchStart, SE->getOne(Ty)));
573 auto LimitCheckPred =
581 expandCheck(Expander, Guard, LimitCheckPred, LatchLimit, RHS);
582 auto *FirstIterationCheck = expandCheck(Expander, Guard, RangeCheck.Pred,
583 GuardStart, GuardLimit);
584 IRBuilder<> Builder(findInsertPt(Guard, {FirstIterationCheck, LimitCheck}));
585 return Builder.CreateFreeze(
586 Builder.CreateAnd(FirstIterationCheck, LimitCheck));
589std::optional<Value *> LoopPredication::widenICmpRangeCheckDecrementingLoop(
590 LoopICmp LatchCheck, LoopICmp RangeCheck,
SCEVExpander &Expander,
592 auto *Ty = RangeCheck.IV->getType();
593 const SCEV *GuardStart = RangeCheck.IV->getStart();
594 const SCEV *GuardLimit = RangeCheck.Limit;
595 const SCEV *LatchStart = LatchCheck.IV->getStart();
596 const SCEV *LatchLimit = LatchCheck.Limit;
600 if (!isLoopInvariantValue(GuardStart) ||
601 !isLoopInvariantValue(GuardLimit) ||
602 !isLoopInvariantValue(LatchStart) ||
603 !isLoopInvariantValue(LatchLimit)) {
614 auto *PostDecLatchCheckIV = LatchCheck.IV->getPostIncExpr(*SE);
615 if (RangeCheck.IV != PostDecLatchCheckIV) {
617 << *PostDecLatchCheckIV
618 <<
" and RangeCheckIV: " << *RangeCheck.IV <<
"\n");
626 auto LimitCheckPred =
628 auto *FirstIterationCheck = expandCheck(Expander, Guard,
630 GuardStart, GuardLimit);
631 auto *LimitCheck = expandCheck(Expander, Guard, LimitCheckPred, LatchLimit,
633 IRBuilder<> Builder(findInsertPt(Guard, {FirstIterationCheck, LimitCheck}));
634 return Builder.CreateFreeze(
635 Builder.CreateAnd(FirstIterationCheck, LimitCheck));
643 RC.IV->getStepRecurrence(*SE)->isOne() &&
652std::optional<Value *>
662 auto RangeCheck = parseLoopICmp(ICI);
664 LLVM_DEBUG(
dbgs() <<
"Failed to parse the loop latch condition!\n");
671 << RangeCheck->Pred <<
")!\n");
674 auto *RangeCheckIV = RangeCheck->IV;
675 if (!RangeCheckIV->isAffine()) {
679 const SCEV *Step = RangeCheckIV->getStepRecurrence(*SE);
682 if (!isSupportedStep(Step)) {
683 LLVM_DEBUG(
dbgs() <<
"Range check and latch have IVs different steps!\n");
686 auto *Ty = RangeCheckIV->getType();
688 if (!CurrLatchCheckOpt) {
690 "corresponding to range type: "
695 LoopICmp CurrLatchCheck = *CurrLatchCheckOpt;
699 CurrLatchCheck.IV->getStepRecurrence(*SE)->getType() &&
700 "Range and latch steps should be of same type!");
701 if (Step != CurrLatchCheck.IV->getStepRecurrence(*SE)) {
702 LLVM_DEBUG(
dbgs() <<
"Range and latch have different step values!\n");
707 return widenICmpRangeCheckIncrementingLoop(CurrLatchCheck, *RangeCheck,
711 return widenICmpRangeCheckDecrementingLoop(CurrLatchCheck, *RangeCheck,
719 for (
auto &Check : Checks)
720 if (
ICmpInst *ICI = dyn_cast<ICmpInst>(Check))
721 if (
auto NewRangeCheck = widenICmpRangeCheck(ICI, Expander, Guard)) {
723 Check = *NewRangeCheck;
727bool LoopPredication::widenGuardConditions(
IntrinsicInst *Guard,
736 widenChecks(Checks, WidenedChecks, Expander, Guard);
737 if (WidenedChecks.
empty())
740 TotalWidened += WidenedChecks.
size();
744 Value *AllChecks = Builder.CreateAnd(Checks);
749 Builder.CreateAssumption(OldCond);
757bool LoopPredication::widenWidenableBranchGuardConditions(
771 widenChecks(Checks, WidenedChecks, Expander, BI);
772 if (WidenedChecks.
empty())
775 TotalWidened += WidenedChecks.
size();
779 Value *AllChecks = Builder.CreateAnd(Checks);
788 Value *AssumeCond = Builder.CreateAnd(WidenedChecks);
794 PN->addIncoming(Pred == GuardBB ? AssumeCond : Builder.getTrue(), Pred);
797 Builder.CreateAssumption(AssumeCond);
801 "Stopped being a guard after transform?");
807std::optional<LoopICmp> LoopPredication::parseLoopLatchICmp() {
808 using namespace PatternMatch;
823 (TrueDest ==
L->getHeader() || BI->
getSuccessor(1) ==
L->getHeader()) &&
824 "One of the latch's destinations must be the header");
831 auto Result = parseLoopICmp(ICI);
833 LLVM_DEBUG(
dbgs() <<
"Failed to parse the loop latch condition!\n");
837 if (TrueDest !=
L->getHeader())
842 if (!
Result->IV->isAffine()) {
847 const SCEV *Step =
Result->IV->getStepRecurrence(*SE);
848 if (!isSupportedStep(Step)) {
849 LLVM_DEBUG(
dbgs() <<
"Unsupported loop stride(" << *Step <<
")!\n");
865 if (IsUnsupportedPredicate(Step,
Result->Pred)) {
874bool LoopPredication::isLoopProfitableToPredicate() {
879 L->getExitEdges(ExitEdges);
882 if (ExitEdges.
size() == 1)
890 auto *LatchBlock =
L->getLoopLatch();
891 assert(LatchBlock &&
"Should have a single latch at this point!");
892 auto *LatchTerm = LatchBlock->getTerminator();
893 assert(LatchTerm->getNumSuccessors() == 2 &&
894 "expected to be an exiting block with 2 succs!");
895 unsigned LatchBrExitIdx =
896 LatchTerm->getSuccessor(0) ==
L->getHeader() ? 1 : 0;
904 auto *LatchExitBlock = LatchTerm->getSuccessor(LatchBrExitIdx);
905 if (isa<UnreachableInst>(LatchTerm) ||
906 LatchExitBlock->getTerminatingDeoptimizeCall())
914 auto ComputeBranchProbability =
918 unsigned NumSucc =
Term->getNumSuccessors();
922 uint64_t Numerator = 0, Denominator = 0;
924 if (
Term->getSuccessor(i) == ExitBlock)
926 Denominator += Weight;
929 if (Denominator == 0)
933 assert(LatchBlock != ExitingBlock &&
934 "Latch term should always have profile data!");
941 ComputeBranchProbability(LatchBlock, LatchExitBlock);
946 if (ScaleFactor < 1) {
949 <<
"Ignored user setting for loop-predication-latch-probability-scale: "
954 const auto LatchProbabilityThreshold = LatchExitProbability * ScaleFactor;
956 for (
const auto &ExitEdge : ExitEdges) {
958 ComputeBranchProbability(ExitEdge.first, ExitEdge.second);
961 if (ExitingBlockProbability > LatchProbabilityThreshold)
993 if (
auto *BI = dyn_cast<BranchInst>(Pred->getTerminator()))
1007 L->getExitingBlocks(ExitingBlocks);
1010 for (
BasicBlock *ExitingBB : ExitingBlocks) {
1012 if (isa<SCEVCouldNotCompute>(ExitCount))
1015 "We should only have known counts for exiting blocks that "
1019 if (ExitCounts.
size() < 2)
1050 L->getExitingBlocks(ExitingBlocks);
1052 if (ExitingBlocks.
empty())
1055 auto *Latch =
L->getLoopLatch();
1063 const SCEV *LatchEC = SE->getExitCount(L, Latch);
1064 if (isa<SCEVCouldNotCompute>(LatchEC))
1073 bool ChangedLoop =
false;
1075 for (
auto *ExitingBB : ExitingBlocks) {
1076 if (LI->getLoopFor(ExitingBB) != L)
1079 auto *BI = dyn_cast<BranchInst>(ExitingBB->getTerminator());
1085 assert(WC->hasOneUse() &&
"Not appropriate widenable branch!");
1086 WC->user_back()->replaceUsesOfWith(
1097 auto *IP = cast<Instruction>(WidenableBR->getCondition());
1107 !SE->isLoopInvariant(MinEC, L) ||
1108 !
Rewriter.isSafeToExpandAt(MinEC, IP))
1114 bool InvalidateLoop =
false;
1115 Value *MinECV =
nullptr;
1116 for (
BasicBlock *ExitingBB : ExitingBlocks) {
1120 if (LI->getLoopFor(ExitingBB) != L)
1124 auto *BI = dyn_cast<BranchInst>(ExitingBB->getTerminator());
1132 const SCEV *ExitCount = SE->getExitCount(L, ExitingBB);
1133 if (isa<SCEVCouldNotCompute>(ExitCount) ||
1135 !
Rewriter.isSafeToExpandAt(ExitCount, WidenableBR))
1138 const bool ExitIfTrue = !
L->contains(*
succ_begin(ExitingBB));
1153 MinECV =
Rewriter.expandCodeFor(MinEC);
1157 ECV =
B.CreateZExt(ECV, WiderTy);
1158 RHS =
B.CreateZExt(RHS, WiderTy);
1165 NewCond =
B.CreateFreeze(NewCond);
1171 InvalidateLoop =
true;
1185bool LoopPredication::runOnLoop(
Loop *
Loop) {
1191 Module *
M =
L->getHeader()->getModule();
1196 bool HasIntrinsicGuards = GuardDecl && !GuardDecl->use_empty();
1198 M, Intrinsic::experimental_widenable_condition);
1199 bool HasWidenableConditions =
1201 if (!HasIntrinsicGuards && !HasWidenableConditions)
1204 DL = &
M->getDataLayout();
1206 Preheader =
L->getLoopPreheader();
1210 auto LatchCheckOpt = parseLoopLatchICmp();
1213 LatchCheck = *LatchCheckOpt;
1218 if (!isLoopProfitableToPredicate()) {
1226 for (
const auto BB :
L->blocks()) {
1233 cast<BranchInst>(BB->getTerminator()));
1237 bool Changed =
false;
1238 for (
auto *Guard : Guards)
1239 Changed |= widenGuardConditions(Guard, Expander);
1240 for (
auto *Guard : GuardsAsWidenableBranches)
1241 Changed |= widenWidenableBranchGuardConditions(Guard, Expander);
1242 Changed |= predicateLoopExits(L, Expander);
1245 MSSAU->getMemorySSA()->verifyMemorySSA();
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
Module.h This file contains the declarations for the Module class.
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...
uint64_t IntrinsicInst * II
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.
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...
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
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)
This class represents an Operation in the Expression.
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...
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...
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.
A Module instance is used to store all the information related to an LLVM module.
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, BasicBlock::iterator 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...
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.
LLVMContext & getContext() const
All values hold a context through their type.
void dump() const
Support for debugging, callable in GDB: V->dump()
const ParentTy * getParent() const
Function * getDeclarationIfExists(Module *M, ID id, ArrayRef< Type * > Tys, FunctionType *FT=nullptr)
This version supports overloaded intrinsics.
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 tuples (A, B,...
void widenWidenableBranch(BranchInst *WidenableBR, Value *NewCond)
Given a branch we know is widenable (defined per Analysis/GuardUtils.h), widen it such that condition...
Value * extractWidenableCondition(const User *U)
auto pred_size(const MachineBasicBlock *BB)
void parseWidenableGuard(const User *U, llvm::SmallVectorImpl< Value * > &Checks)
bool isGuard(const User *U)
Returns true iff U has semantics of a guard expressed in a form of call of llvm.experimental....
MDNode * getValidBranchWeightMDNode(const Instruction &I)
Get the valid branch weights metadata node.
bool isModSet(const ModRefInfo MRI)
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.
RNSuccIterator< NodeRef, BlockT, RegionT > succ_begin(NodeRef Node)
bool isWidenableBranch(const User *U)
Returns true iff U is a widenable branch (that is, extractWidenableCondition returns widenable condit...
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 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...