49#define DEBUG_TYPE "loop-peel"
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)."));
85 if (!L->isLoopSimplifyForm())
91 L->getUniqueNonLatchExitBlocks(Exits);
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;
187PhiAnalyzer::PhiAnalyzer(
const Loop &L,
unsigned MaxIterations)
188 :
L(
L), MaxIterations(MaxIterations) {
190 assert(MaxIterations > 0 &&
"no peeling is allowed?");
207PhiAnalyzer::PeelCounter PhiAnalyzer::calculate(
const Value &V) {
209 auto I = IterationsToInvariance.find(&V);
210 if (
I != IterationsToInvariance.end())
215 IterationsToInvariance[&
V] =
Unknown;
217 if (
L.isLoopInvariant(&V))
219 return (IterationsToInvariance[&V] = 0);
220 if (
const PHINode *Phi = dyn_cast<PHINode>(&V)) {
221 if (Phi->getParent() !=
L.getHeader()) {
223 assert(IterationsToInvariance[&V] ==
Unknown &&
"unexpected value saved");
227 Value *Input = Phi->getIncomingValueForBlock(
L.getLoopLatch());
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));
242 return (IterationsToInvariance[
I] = {std::max(*LHS, *RHS)});
246 return (IterationsToInvariance[
I] = calculate(*
I->getOperand(0)));
251 assert(IterationsToInvariance[&V] ==
Unknown &&
"unexpected value saved");
255std::optional<unsigned> PhiAnalyzer::calculateIterationsToPeel() {
256 unsigned Iterations = 0;
257 for (
auto &
PHI :
L.getHeader()->phis()) {
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;
281 if (L.getExitingBlock())
287 L.getUniqueNonLatchExitBlocks(Exits);
301 const DataLayout &
DL = L.getHeader()->getModule()->getDataLayout();
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();
318 if (DT.
dominates(BB, Latch) && L.isLoopInvariant(
Ptr) &&
320 for (
Value *U :
I.users())
326 L.getExitingBlocks(ExitingBlocks);
345 assert(L.isLoopSimplifyForm() &&
"Loop needs to be in loop simplify form");
346 unsigned DesiredPeelCount = 0;
348 for (
auto *BB : L.blocks()) {
349 auto *BI = dyn_cast<BranchInst>(BB->getTerminator());
350 if (!BI || BI->isUnconditional())
354 if (L.getLoopLatch() == BB)
357 Value *Condition = BI->getCondition();
358 Value *LeftVal, *RightVal;
373 if (!isa<SCEVAddRecExpr>(LeftSCEV)) {
374 if (isa<SCEVAddRecExpr>(RightSCEV)) {
376 Pred = ICmpInst::getSwappedPredicate(Pred);
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,
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;
456 if (!LatchBR || LatchBR->
getNumSuccessors() != 2 || !L->isLoopExiting(Latch))
461 "At least one edge out of the latch must go to the header");
464 L->getUniqueNonLatchExitBlocks(ExitBlocks);
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");
569 if (L->getHeader()->getParent()->hasProfileData()) {
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,
623 ?
Info.Weights[
Idx] - SubWeight
631 L->getExitingBlocks(ExitingBlocks);
632 for (
BasicBlock *ExitingBlock : ExitingBlocks) {
643 if (L->contains(Succ))
644 FallThroughWeights += Weight;
646 ExitWeights += Weight;
650 if (FallThroughWeights == 0)
655 if (!L->contains(Succ)) {
663 double W = (double)Weight / (
double)FallThroughWeights;
667 WeightInfos.
insert({Term, {std::move(Weights), std::move(SubWeights)}});
675 Term->setMetadata(LLVMContext::MD_prof,
698 BasicBlock *PreHeader = L->getLoopPreheader();
703 Loop *ParentLoop = L->getParentLoop();
735 std::string Ext = (
Twine(
"Peel") +
Twine(IterNumber)).str();
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?");
865 BasicBlock *PreHeader = L->getLoopPreheader();
868 L->getExitEdges(ExitEdges);
875 for (
auto *BB : L->blocks()) {
876 auto *BBDomNode = DT.
getNode(BB);
878 for (
auto *ChildDomNode : BBDomNode->children()) {
879 auto *ChildBB = ChildDomNode->getBlock();
880 if (!L->contains(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
981 assert(DT.
verify(DominatorTree::VerificationLevel::Fast));
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;
1023 if (
Loop *ParentLoop = L->getParentLoop())
1029#ifdef EXPENSIVE_CHECKS
1031 assert(DT.
verify(DominatorTree::VerificationLevel::Fast));
1035 simplifyLoop(L, &DT, LI, SE, AC,
nullptr, PreserveLCSSA);
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Analysis containing CSE Info
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
This file defines the DenseMap class.
static void updateBranchWeights(Instruction *Term, WeightInfo &Info)
Update the branch weights of an exiting block of a peeled-off loop iteration.
static cl::opt< bool > DisableAdvancedPeeling("disable-advanced-peeling", cl::init(false), cl::Hidden, cl::desc("Disable advance peeling. Issues for convergent targets (D134803)."))
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."))
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."))
static cl::opt< unsigned > UnrollForcePeelCount("unroll-force-peel-count", cl::init(0), cl::Hidden, cl::desc("Force a peel count regardless of profiling information."))
static unsigned countToEliminateCompares(Loop &L, unsigned MaxPeelCount, ScalarEvolution &SE)
static bool violatesLegacyMultiExitLoopCheck(Loop *L)
This "heuristic" exactly matches implicit behavior which used to exist inside getLoopEstimatedTripCou...
static const char * PeeledCountMetaData
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.
static cl::opt< bool > UnrollAllowLoopNestsPeeling("unroll-allow-loop-nests-peeling", cl::init(false), cl::Hidden, cl::desc("Allows loop nests to be peeled."))
static cl::opt< unsigned > UnrollPeelCount("unroll-peel-count", cl::Hidden, cl::desc("Set the unroll peeling count, for testing purposes"))
static unsigned peelToTurnInvariantLoadsDerefencebale(Loop &L, DominatorTree &DT, AssumptionCache *AC)
static void fixupBranchWeights(Instruction *Term, const WeightInfo &Info)
Update the weights of original exiting block after peeling off all iterations.
static void initBranchWeights(DenseMap< Instruction *, WeightInfo > &WeightInfos, Loop *L)
Initialize the weights for all exiting blocks.
This file contains the declarations for profiling metadata utility functions.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
const CallInst * getTerminatingDeoptimizeCall() const
Returns the call instruction calling @llvm.experimental.deoptimize prior to the terminating return in...
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...
Conditional or Unconditional Branch instruction.
unsigned getNumSuccessors() const
BasicBlock * getSuccessor(unsigned i) const
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
A parsed version of the target data layout string in and methods for querying it.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
DomTreeNodeBase * getIDom() const
bool verify(VerificationLevel VL=VerificationLevel::Full) const
verify - checks if the tree is correct.
void changeImmediateDominator(DomTreeNodeBase< NodeT > *N, DomTreeNodeBase< NodeT > *NewIDom)
changeImmediateDominator - This method is used to update the dominator tree information when a node's...
DomTreeNodeBase< NodeT > * addNewBlock(NodeT *BB, NodeT *DomBB)
Add a new node to the dominator tree information.
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
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 dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
bool isEquality() const
Return true if this predicate is either EQ or NE.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
void setSuccessor(unsigned Idx, BasicBlock *BB)
Update the specified successor to point at the provided block.
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)
This method is used by other analyses to update loop information.
Store the result of a depth first search within basic blocks contained by a single loop.
RPOIterator beginRPO() const
Reverse iterate over the cached postorder blocks.
std::vector< BasicBlock * >::const_reverse_iterator RPOIterator
void perform(LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
RPOIterator endRPO() const
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Represents a single loop in the control flow graph.
MDNode * createBranchWeights(uint32_t TrueWeight, uint32_t FalseWeight)
Return metadata containing two branch weights.
Value * getIncomingValueForBlock(const BasicBlock *BB) const
This node represents a polynomial recurrence on the trip count of the specified loop.
const SCEV * evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const
Return the value of this chain of recurrences at the specified iteration number.
const SCEV * getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
bool isAffine() const
Return true if this represents an expression A + B*x where A and B are loop invariant values.
const Loop * getLoop() const
bool hasNoSelfWrap() const
This class represents an analyzed expression in the program.
Type * getType() const
Return the LLVM type of this SCEV expression.
The main scalar evolution driver.
const SCEV * getConstant(ConstantInt *V)
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
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 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,...
void forgetTopmostLoop(const Loop *L)
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...
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 * getAddExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical add expression, or something simpler if possible.
iterator find(ConstPtrType Ptr) const
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
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.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
LLVM Value Representation.
void setName(const Twine &Name)
Change the name of the value.
StringRef getName() const
Return a constant reference to the value's name.
self_iterator getIterator()
bool match(Val *V, const Pattern &P)
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
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.
bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
Simplify each loop in a loop nest recursively.
detail::zippy< detail::zip_shortest, T, U, Args... > zip(T &&t, U &&u, Args &&...args)
zip iterator for two or more iteratable types.
std::optional< unsigned > getLoopEstimatedTripCount(Loop *L, unsigned *EstimatedLoopInvocationWeight=nullptr)
Returns a loop's estimated trip count based on branch weight metadata.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
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 @...
void computePeelCount(Loop *L, unsigned LoopSize, TargetTransformInfo::PeelingPreferences &PP, unsigned TripCount, DominatorTree &DT, ScalarEvolution &SE, AssumptionCache *AC=nullptr, unsigned Threshold=UINT_MAX)
auto enumerate(FirstRange &&First, RestRanges &&...Rest)
Given two or more input ranges, returns a new range whose values are are tuples (A,...
auto successors(const MachineBasicBlock *BB)
bool canPeel(const Loop *L)
void addStringMetadataToLoop(Loop *TheLoop, const char *MDString, unsigned V=0)
Set input string into loop metadata by keeping other values intact.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
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...
TargetTransformInfo::PeelingPreferences gatherPeelingPreferences(Loop *L, ScalarEvolution &SE, const TargetTransformInfo &TTI, std::optional< bool > UserAllowPeeling, std::optional< bool > UserAllowProfileBasedPeeling, bool UnrollingSpecficValues=false)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
std::optional< int > getOptionalIntLoopAttribute(const Loop *TheLoop, StringRef Name)
Find named metadata for a loop with an integer value.
void cloneAndAdaptNoAliasScopes(ArrayRef< MDNode * > NoAliasDeclScopes, ArrayRef< BasicBlock * > NewBlocks, LLVMContext &Context, StringRef Ext)
Clone the specified noalias decl scopes.
void remapInstructionsInBlocks(ArrayRef< BasicBlock * > Blocks, ValueToValueMapTy &VMap)
Remaps instructions in Blocks using the mapping in VMap.
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.
bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)
Extract branch weights from MD_prof metadata.
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.
void identifyNoAliasScopesToClone(ArrayRef< BasicBlock * > BBs, SmallVectorImpl< MDNode * > &NoAliasDeclScopes)
Find the 'llvm.experimental.noalias.scope.decl' intrinsics in the specified basic blocks and extract ...
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...
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...
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...
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
SmallVector< uint32_t > Weights
const SmallVector< uint32_t > SubWeights