Go to the documentation of this file.
49 #define DEBUG_TYPE "loop-peel"
51 STATISTIC(NumPeeled,
"Number of loops peeled");
55 cl::desc(
"Set the unroll peeling count, for testing purposes"));
59 cl::desc(
"Allows loops to be peeled when the dynamic "
60 "trip count is known to be low."));
65 cl::desc(
"Allows loop nests to be peeled."));
69 cl::desc(
"Max average trip count which will cause loop peeling."));
73 cl::desc(
"Force a peel count regardless of profiling information."));
78 "Disable advance peeling. Issues for convergent targets (D134803)."));
159 PhiAnalyzer(
const Loop &L,
unsigned MaxIterations);
163 std::optional<unsigned> calculateIterationsToPeel();
166 using PeelCounter = std::optional<unsigned>;
167 const PeelCounter Unknown = std::nullopt;
170 PeelCounter addOne(PeelCounter PC)
const {
173 return (*PC + 1 <= MaxIterations) ? PeelCounter{*PC + 1} :
Unknown;
178 PeelCounter calculate(
const Value &);
181 const unsigned MaxIterations;
187 PhiAnalyzer::PhiAnalyzer(
const Loop &L,
unsigned MaxIterations)
188 : L(L), MaxIterations(MaxIterations) {
190 assert(MaxIterations > 0 &&
"no peeling is allowed?");
207 PhiAnalyzer::PeelCounter PhiAnalyzer::calculate(
const Value &V) {
209 auto I = IterationsToInvariance.find(&V);
210 if (
I != IterationsToInvariance.end())
215 IterationsToInvariance[&V] =
Unknown;
219 return (IterationsToInvariance[&V] = 0);
220 if (
const PHINode *Phi = dyn_cast<PHINode>(&V)) {
223 assert(IterationsToInvariance[&V] ==
Unknown &&
"unexpected value saved");
228 PeelCounter Iterations = calculate(*Input);
229 assert(IterationsToInvariance[Input] == Iterations &&
230 "unexpected value saved");
231 return (IterationsToInvariance[Phi] = addOne(Iterations));
234 if (isa<CmpInst>(
I) ||
I->isBinaryOp()) {
236 PeelCounter
LHS = calculate(*
I->getOperand(0));
239 PeelCounter
RHS = calculate(*
I->getOperand(1));
246 return (IterationsToInvariance[
I] = calculate(*
I->getOperand(0)));
251 assert(IterationsToInvariance[&V] ==
Unknown &&
"unexpected value saved");
255 std::optional<unsigned> PhiAnalyzer::calculateIterationsToPeel() {
256 unsigned Iterations = 0;
258 PeelCounter ToInvariance = calculate(
PHI);
260 assert(*ToInvariance <= MaxIterations &&
"bad result in phi analysis");
261 Iterations =
std::max(Iterations, *ToInvariance);
262 if (Iterations == MaxIterations)
266 assert((Iterations <= MaxIterations) &&
"bad result in phi analysis");
267 return Iterations ? std::optional<unsigned>(Iterations) :
std::nullopt;
289 return !isa<UnreachableInst>(
BB->getTerminator());
304 if (
I.mayWriteToMemory())
307 auto Iter = LoadUsers.
find(&
I);
308 if (Iter != LoadUsers.
end()) {
309 for (
Value *U :
I.users())
316 if (
auto *LI = dyn_cast<LoadInst>(&
I)) {
317 Value *
Ptr = LI->getPointerOperand();
320 for (
Value *U :
I.users())
346 unsigned DesiredPeelCount = 0;
349 auto *BI = dyn_cast<BranchInst>(
BB->getTerminator());
350 if (!BI || BI->isUnconditional())
357 Value *Condition = BI->getCondition();
358 Value *LeftVal, *RightVal;
373 if (!isa<SCEVAddRecExpr>(LeftSCEV)) {
374 if (isa<SCEVAddRecExpr>(RightSCEV)) {
387 if (!(ICmpInst::isEquality(Pred) && LeftAR->
hasNoSelfWrap()) &&
393 unsigned NewPeelCount = DesiredPeelCount;
402 Pred = ICmpInst::getInversePredicate(Pred);
406 auto PeelOneMoreIteration = [&IterVal, &NextIterVal, &SE, Step,
408 IterVal = NextIterVal;
409 NextIterVal = SE.getAddExpr(IterVal, Step);
413 auto CanPeelOneMoreIteration = [&NewPeelCount, &MaxPeelCount]() {
414 return NewPeelCount < MaxPeelCount;
417 while (CanPeelOneMoreIteration() &&
418 SE.isKnownPredicate(Pred, IterVal, RightSCEV))
419 PeelOneMoreIteration();
423 if (!SE.isKnownPredicate(ICmpInst::getInversePredicate(Pred), IterVal,
430 if (ICmpInst::isEquality(Pred) &&
431 !SE.isKnownPredicate(ICmpInst::getInversePredicate(Pred), NextIterVal,
433 !SE.isKnownPredicate(Pred, IterVal, RightSCEV) &&
434 SE.isKnownPredicate(Pred, NextIterVal, RightSCEV)) {
435 if (!CanPeelOneMoreIteration())
437 PeelOneMoreIteration();
440 DesiredPeelCount =
std::max(DesiredPeelCount, NewPeelCount);
443 return DesiredPeelCount;
461 "At least one edge out of the latch must go to the header");
476 unsigned Threshold) {
477 assert(LoopSize > 0 &&
"Zero loop size is not allowed!");
495 <<
" iterations.\n");
506 if (2 * LoopSize > Threshold)
509 unsigned AlreadyPeeled = 0;
511 AlreadyPeeled = *Peeled;
518 MaxPeelCount =
std::min(MaxPeelCount, Threshold / LoopSize - 1);
522 unsigned DesiredPeelCount = TargetPeelCount;
529 if (MaxPeelCount > DesiredPeelCount) {
531 auto NumPeels = PhiAnalyzer(*L, MaxPeelCount).calculateIterationsToPeel();
533 DesiredPeelCount =
std::max(DesiredPeelCount, *NumPeels);
536 DesiredPeelCount =
std::max(DesiredPeelCount,
539 if (DesiredPeelCount == 0)
542 if (DesiredPeelCount > 0) {
543 DesiredPeelCount =
std::min(DesiredPeelCount, MaxPeelCount);
545 assert(DesiredPeelCount > 0 &&
"Wrong loop size estimation?");
548 <<
" iteration(s) to turn"
549 <<
" some Phis into invariants.\n");
573 if (!EstimatedTripCount)
577 << *EstimatedTripCount <<
"\n");
579 if (*EstimatedTripCount) {
580 if (*EstimatedTripCount + AlreadyPeeled <= MaxPeelCount) {
581 unsigned PeelCount = *EstimatedTripCount;
582 LLVM_DEBUG(
dbgs() <<
"Peeling first " << PeelCount <<
" iterations.\n");
586 LLVM_DEBUG(
dbgs() <<
"Already peel count: " << AlreadyPeeled <<
"\n");
591 << (Threshold / LoopSize - 1) <<
"\n");
618 Term->setMetadata(LLVMContext::MD_prof,
622 Info.Weights[Idx] =
Info.Weights[Idx] > SubWeight
623 ?
Info.Weights[Idx] - SubWeight
632 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
644 FallThroughWeights += Weight;
646 ExitWeights += Weight;
650 if (FallThroughWeights == 0)
657 SubWeights.push_back(0);
663 double W = (
double)Weight / (
double)FallThroughWeights;
664 SubWeights.push_back((
uint32_t)(ExitWeights *
W));
675 Term->setMetadata(LLVMContext::MD_prof,
709 NewBlocks.push_back(NewBB);
737 Header->getContext(),
Ext);
742 for (
Loop *ChildLoop : *L) {
743 cloneLoop(ChildLoop, ParentLoop, VMap, LI,
nullptr);
757 BasicBlock *NewLatch = cast<BasicBlock>(VMap[Latch]);
758 auto *LatchTerm = cast<Instruction>(NewLatch->
getTerminator());
759 for (
unsigned idx = 0,
e = LatchTerm->getNumSuccessors(); idx <
e; ++idx)
760 if (LatchTerm->getSuccessor(idx) == Header) {
761 LatchTerm->setSuccessor(idx, InsertBot);
776 PHINode *NewPHI = cast<PHINode>(VMap[&*
I]);
777 if (IterNumber == 0) {
781 Instruction *LatchInst = dyn_cast<Instruction>(LatchVal);
782 if (LatchInst && L->contains(LatchInst))
783 VMap[&*
I] = LVMap[LatchInst];
785 VMap[&*
I] = LatchVal;
794 for (
auto Edge : ExitEdges)
796 Value *LatchVal =
PHI.getIncomingValueForBlock(Edge.first);
797 Instruction *LatchInst = dyn_cast<Instruction>(LatchVal);
798 if (LatchInst && L->contains(LatchInst))
799 LatchVal = VMap[LatchVal];
800 PHI.addIncoming(LatchVal, cast<BasicBlock>(VMap[Edge.first]));
807 LVMap[KV.first] = KV.second;
813 std::optional<bool> UserAllowPeeling,
814 std::optional<bool> UserAllowProfileBasedPeeling,
815 bool UnrollingSpecficValues) {
828 if (UnrollingSpecficValues) {
838 if (UserAllowPeeling)
840 if (UserAllowProfileBasedPeeling)
858 assert(PeelCount > 0 &&
"Attempt to peel out zero iterations?");
859 assert(
canPeel(L) &&
"Attempt to peel a loop which is not peelable?");
878 for (
auto *ChildDomNode : BBDomNode->children()) {
879 auto *ChildBB = ChildDomNode->getBlock();
881 ChildrenToUpdate.push_back(ChildBB);
888 for (
auto *ChildBB : ChildrenToUpdate)
889 NonLoopBlocksIDom[ChildBB] = NewIDom;
945 InsertTop->
setName(Header->getName() +
".peel.begin");
946 InsertBot->
setName(Header->getName() +
".peel.next");
950 cast<Instruction>(cast<BasicBlock>(Latch)->getTerminator());
963 for (
unsigned Iter = 0; Iter < PeelCount; ++Iter) {
968 LoopBlocks, VMap, LVMap, &DT, LI,
969 LoopLocalNoAliasDeclScopes, *SE);
977 for (
auto BBIDom : NonLoopBlocksIDom)
979 cast<BasicBlock>(LVMap[BBIDom.second]));
980 #ifdef EXPENSIVE_CHECKS
984 for (
auto &[
Term,
Info] : Weights) {
985 auto *TermCopy = cast<Instruction>(VMap[
Term]);
991 auto *LatchTermCopy = cast<Instruction>(VMap[LatchTerm]);
992 LatchTermCopy->setMetadata(LLVMContext::MD_loop,
nullptr);
994 InsertTop = InsertBot;
996 InsertBot->
setName(Header->getName() +
".peel.next");
998 F->splice(InsertTop->
getIterator(),
F, NewBlocks[0]->getIterator(),
1006 Value *NewVal =
PHI->getIncomingValueForBlock(Latch);
1007 Instruction *LatchInst = dyn_cast<Instruction>(NewVal);
1008 if (LatchInst && L->
contains(LatchInst))
1009 NewVal = LVMap[LatchInst];
1011 PHI->setIncomingValueForBlock(NewPreHeader, NewVal);
1014 for (
const auto &[
Term,
Info] : Weights)
1018 unsigned AlreadyPeeled = 0;
1020 AlreadyPeeled = *Peeled;
1029 #ifdef EXPENSIVE_CHECKS
1035 simplifyLoop(L, &DT, LI, SE, AC,
nullptr, PreserveLCSSA);
static cl::opt< unsigned > UnrollPeelCount("unroll-peel-count", cl::Hidden, cl::desc("Set the unroll peeling count, for testing purposes"))
const CallInst * getTerminatingDeoptimizeCall() const
Returns the call instruction calling @llvm.experimental.deoptimize prior to the terminating return in...
bool isLoopInvariant(const Value *V) const
Return true if the specified value is loop invariant.
This is an optimization pass for GlobalISel generic memory operations.
A parsed version of the target data layout string in and methods for querying it.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
InstListType::iterator iterator
Instruction iterators...
bool isAffine() const
Return true if this represents an expression A + B*x where A and B are loop invariant values.
const Function * getParent() const
Return the enclosing method, or null if none.
static bool violatesLegacyMultiExitLoopCheck(Loop *L)
This "heuristic" exactly matches implicit behavior which used to exist inside getLoopEstimatedTripCou...
Represents a single loop in the control flow graph.
void computePeelCount(Loop *L, unsigned LoopSize, TargetTransformInfo::PeelingPreferences &PP, unsigned TripCount, DominatorTree &DT, ScalarEvolution &SE, AssumptionCache *AC=nullptr, unsigned Threshold=UINT_MAX)
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
into xmm2 addss xmm2 xmm1 xmm3 addss xmm3 movaps xmm0 unpcklps xmm0 ret seems silly when it could just be one addps Expand libm rounding functions main should enable SSE DAZ mode and other fast SSE modes Think about doing i64 math in SSE regs on x86 This testcase should have no SSE instructions in and only one load from a constant double
auto successors(const MachineBasicBlock *BB)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
detail::enumerator< R > enumerate(R &&TheRange)
Given an input range, returns a new range whose values are are pair (A,B) such that A is the 0-based ...
static cl::opt< unsigned > UnrollPeelMaxCount("unroll-peel-max-count", cl::init(7), cl::Hidden, cl::desc("Max average trip count which will cause loop peeling."))
The main scalar evolution driver.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Predicate getSwappedPredicate(Predicate Opcode)
Assume the condition register is set by MI(a,b), return the predicate if we modify the instructions s...
static void updateBranchWeights(Instruction *Term, WeightInfo &Info)
Update the branch weights of an exiting block of a peeled-off loop iteration.
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
void getExitEdges(SmallVectorImpl< Edge > &ExitEdges) const
Return all pairs of (inside_block,outside_block).
unsigned getNumSuccessors() const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
bool canPeel(const Loop *L)
DomTreeNodeBase * getIDom() const
RPOIterator beginRPO() const
Reverse iterate over the cached postorder blocks.
LLVM Basic Block Representation.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
static const char * PeeledCountMetaData
const SmallVector< uint32_t > SubWeights
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
SmallVector< uint32_t > Weights
bool match(Val *V, const Pattern &P)
static unsigned countToEliminateCompares(Loop &L, unsigned MaxPeelCount, ScalarEvolution &SE)
void remapInstructionsInBlocks(const SmallVectorImpl< BasicBlock * > &Blocks, ValueToValueMapTy &VMap)
Remaps instructions in Blocks using the mapping in VMap.
MDNode * createBranchWeights(uint32_t TrueWeight, uint32_t FalseWeight)
Return metadata containing two branch weights.
static cl::opt< unsigned > UnrollForcePeelCount("unroll-force-peel-count", cl::init(0), cl::Hidden, cl::desc("Force a peel count regardless of profiling information."))
Loop * cloneLoop(Loop *L, Loop *PL, ValueToValueMapTy &VM, LoopInfo *LI, LPPassManager *LPM)
Recursively clone the specified loop and all of its children, mapping the blocks with the specified m...
iterator_range< block_iterator > blocks() const
Value * getIncomingValueForBlock(const BasicBlock *BB) const
ArrayRef< BlockT * > getBlocks() const
Get a list of the basic blocks which make up this loop.
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,...
RPOIterator endRPO() const
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
STATISTIC(NumFunctions, "Total number of functions")
void setName(const Twine &Name)
Change the name of the value.
void getExitingBlocks(SmallVectorImpl< BlockT * > &ExitingBlocks) const
Return all blocks inside the loop that have successors outside of the loop.
int getNumOccurrences() const
Analysis containing CSE Info
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
void changeImmediateDominator(DomTreeNodeBase< NodeT > *N, DomTreeNodeBase< NodeT > *NewIDom)
changeImmediateDominator - This method is used to update the dominator tree information when a node's...
BlockT * getExitingBlock() const
If getExitingBlocks would return exactly one block, return that block.
bool peelLoop(Loop *L, unsigned PeelCount, LoopInfo *LI, ScalarEvolution *SE, DominatorTree &DT, AssumptionCache *AC, bool PreserveLCSSA, ValueToValueMapTy &VMap)
VMap is the value-map that maps instructions from the original loop to instructions in the last peele...
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
std::vector< BasicBlock * >::const_reverse_iterator RPOIterator
Store the result of a depth first search within basic blocks contained by a single loop.
void cloneAndAdaptNoAliasScopes(ArrayRef< MDNode * > NoAliasDeclScopes, ArrayRef< BasicBlock * > NewBlocks, LLVMContext &Context, StringRef Ext)
Clone the specified noalias decl scopes.
std::optional< bool > evaluatePredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
Check whether the condition described by Pred, LHS, and RHS is true or false.
bool isLoopSimplifyForm() const
Return true if the Loop is in the form that the LoopSimplify form transforms loops to,...
BasicBlock * CloneBasicBlock(const BasicBlock *BB, ValueToValueMapTy &VMap, const Twine &NameSuffix="", Function *F=nullptr, ClonedCodeInfo *CodeInfo=nullptr, DebugInfoFinder *DIFinder=nullptr)
Return a copy of the specified basic block, but without embedding the block into a particular functio...
This class represents an analyzed expression in the program.
iterator find(ConstPtrType Ptr) const
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
void addStringMetadataToLoop(Loop *TheLoop, const char *MDString, unsigned V=0)
Set input string into loop metadata by keeping other values intact.
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
bool hasNoSelfWrap() const
initializer< Ty > init(const Ty &Val)
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
void forgetValue(Value *V)
This method should be called by the client when it has changed a value in a way that may effect its v...
void perform(LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
void forgetTopmostLoop(const Loop *L)
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
std::optional< int > getOptionalIntLoopAttribute(const Loop *TheLoop, StringRef Name)
Find named metadata for a loop with an integer value.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
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,...
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
bool isDereferenceablePointer(const Value *V, Type *Ty, const DataLayout &DL, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if this is always a dereferenceable pointer.
void identifyNoAliasScopesToClone(ArrayRef< BasicBlock * > BBs, SmallVectorImpl< MDNode * > &NoAliasDeclScopes)
Find the 'llvm.experimental.noalias.scope.decl' intrinsics in the specified basic blocks and extract ...
void setSuccessor(unsigned Idx, BasicBlock *BB)
Update the specified successor to point at the provided block.
A cache of @llvm.assume calls within a function.
const SCEV * getConstant(ConstantInt *V)
static cl::opt< bool > UnrollAllowLoopNestsPeeling("unroll-allow-loop-nests-peeling", cl::init(false), cl::Hidden, cl::desc("Allows loop nests to be peeled."))
self_iterator getIterator()
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
TargetTransformInfo::PeelingPreferences gatherPeelingPreferences(Loop *L, ScalarEvolution &SE, const TargetTransformInfo &TTI, std::optional< bool > UserAllowPeeling, std::optional< bool > UserAllowProfileBasedPeeling, bool UnrollingSpecficValues=false)
static cl::opt< bool > UnrollAllowPeeling("unroll-allow-peeling", cl::init(true), cl::Hidden, cl::desc("Allows loops to be peeled when the dynamic " "trip count is known to be low."))
StringRef getName() const
Return a constant reference to the value's name.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
void getUniqueNonLatchExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const
Return all unique successor blocks of this loop except successors from Latch block are not considered...
DomTreeNodeBase< NodeT > * addNewBlock(NodeT *BB, NodeT *DomBB)
Add a new node to the dominator tree information.
bool isInnermost() const
Return true if the loop does not contain any (natural) loops.
BasicBlock * SplitEdge(BasicBlock *From, BasicBlock *To, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="")
Split the edge connecting the specified blocks, and return the newly created basic block between From...
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
static void fixupBranchWeights(Instruction *Term, const WeightInfo &Info)
Update the weights of original exiting block after peeling off all iterations.
const Loop * getLoop() const
static void initBranchWeights(DenseMap< Instruction *, WeightInfo > &WeightInfos, Loop *L)
Initialize the weights for all exiting blocks.
This node represents a polynomial recurrence on the trip count of the specified loop.
BlockT * getHeader() const
Instruction * findNearestCommonDominator(Instruction *I1, Instruction *I2) const
Find the nearest instruction I that dominates both I1 and I2, in the sense that a result produced bef...
bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
Simplify each loop in a loop nest recursively.
bool hasProfileData(bool IncludeSynthetic=false) const
Return true if the function is annotated with profile data.
bool IsBlockFollowedByDeoptOrUnreachable(const BasicBlock *BB)
Check if we can prove that all paths starting from this block converge to a block that either has a @...
static unsigned peelToTurnInvariantLoadsDerefencebale(Loop &L, DominatorTree &DT, AssumptionCache *AC)
static void cloneLoopBlocks(Loop *L, unsigned IterNumber, BasicBlock *InsertTop, BasicBlock *InsertBot, SmallVectorImpl< std::pair< BasicBlock *, BasicBlock * >> &ExitEdges, SmallVectorImpl< BasicBlock * > &NewBlocks, LoopBlocksDFS &LoopBlocks, ValueToValueMapTy &VMap, ValueToValueMapTy &LVMap, DominatorTree *DT, LoopInfo *LI, ArrayRef< MDNode * > LoopLocalNoAliasDeclScopes, ScalarEvolution &SE)
Clones the body of the loop L, putting it between InsertTop and InsertBot.
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)
This method is used by other analyses to update loop information.
detail::zippy< detail::zip_shortest, T, U, Args... > zip(T &&t, U &&u, Args &&...args)
zip iterator for two or more iteratable types.
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
bool verify(VerificationLevel VL=VerificationLevel::Full) const
verify - checks if the tree is correct.
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...
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Type * getType() const
Return the LLVM type of this SCEV expression.
const SCEV * getAddExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical add expression, or something simpler if possible.
bool isLoopExiting(const BlockT *BB) const
True if terminator in the block can branch to another block that is outside of the current loop.
bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)
Extract branch weights from MD_prof metadata.
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Conditional or Unconditional Branch instruction.
bool contains(ConstPtrType Ptr) const
static cl::opt< bool > DisableAdvancedPeeling("disable-advanced-peeling", cl::init(false), cl::Hidden, cl::desc("Disable advance peeling. Issues for convergent targets (D134803)."))
BasicBlock * SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)
Split the specified block at the specified instruction.
std::optional< unsigned > getLoopEstimatedTripCount(Loop *L, unsigned *EstimatedLoopInvocationWeight=nullptr)
Returns a loop's estimated trip count based on branch weight metadata.
LLVM Value Representation.
BasicBlock * getSuccessor(unsigned i) const
const SCEV * getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
const SCEV * evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const
Return the value of this chain of recurrences at the specified iteration number.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.