82#define DEBUG_TYPE "loop-unroll"
85STATISTIC(NumCompletelyUnrolled,
"Number of loops completely unrolled");
86STATISTIC(NumUnrolled,
"Number of loops unrolled (completely or otherwise)");
87STATISTIC(NumUnrolledNotLatch,
"Number of loops unrolled without a conditional "
88 "latch (completely or otherwise)");
92 cl::desc(
"Allow runtime unrolled loops to be unrolled "
93 "with epilog instead of prolog."));
97 cl::desc(
"Verify domtree after unrolling"),
98#ifdef EXPENSIVE_CHECKS
107 cl::desc(
"Verify loopinfo after unrolling"),
108#ifdef EXPENSIVE_CHECKS
126 const std::vector<BasicBlock *> &
Blocks,
132 for (
Use &U :
I.operands()) {
133 if (
const auto *Def = dyn_cast<Instruction>(U)) {
155 assert(OldLoop &&
"Should (at least) be in the loop being unrolled!");
157 Loop *&NewLoop = NewLoops[OldLoop];
161 "Header should be first in RPO");
205 BasicBlock *PreHeader = L->getLoopPreheader();
207 assert(PreHeader && Header);
208 for (
const PHINode &PN : Header->phis()) {
209 if (isa<ConstantInt>(PN.getIncomingValueForBlock(PreHeader)))
225 unsigned CurrentGeneration;
226 unsigned ChildGeneration;
230 bool Processed =
false;
236 : LoadScope(AvailableLoads), CurrentGeneration(cg), ChildGeneration(cg),
237 Node(
N), ChildIter(Child), EndIter(
End) {}
270 if (!MSSA->
dominates(LaterDef, EarlierMA))
284 unsigned CurrentGeneration = 0;
285 while (!NodesToProcess.
empty()) {
304 auto *Load = dyn_cast<LoadInst>(&
I);
305 if (!Load || !Load->isSimple()) {
306 if (
I.mayWriteToMemory())
311 const SCEV *PtrSCEV = SE.
getSCEV(Load->getPointerOperand());
316 Load->replaceAllUsesWith(M);
317 Load->eraseFromParent();
325 }
else if (NodeToProcess->
childIter() != NodeToProcess->
end()) {
328 if (!L->contains(Child->
getBlock()))
352 if (SE && SimplifyIVs) {
358 while (!DeadInsts.
empty()) {
360 if (
Instruction *Inst = dyn_cast_or_null<Instruction>(V))
365 std::unique_ptr<MemorySSA> MSSA =
nullptr;
377 const DataLayout &
DL = L->getHeader()->getModule()->getDataLayout();
383 Inst.replaceAllUsesWith(V);
393 const APInt *C1, *C2;
395 auto *InnerI = dyn_cast<Instruction>(Inst.getOperand(0));
396 auto *InnerOBO = cast<OverflowingBinaryOperator>(Inst.getOperand(0));
399 Inst.setOperand(0,
X);
400 Inst.setOperand(1, ConstantInt::get(Inst.getType(), NewC));
401 Inst.setHasNoUnsignedWrap(Inst.hasNoUnsignedWrap() &&
402 InnerOBO->hasNoUnsignedWrap());
403 Inst.setHasNoSignedWrap(Inst.hasNoSignedWrap() &&
404 InnerOBO->hasNoSignedWrap() &&
440 assert(DT &&
"DomTree is required");
442 if (!L->getLoopPreheader()) {
443 LLVM_DEBUG(
dbgs() <<
" Can't unroll; loop preheader-insertion failed.\n");
444 return LoopUnrollResult::Unmodified;
447 if (!L->getLoopLatch()) {
448 LLVM_DEBUG(
dbgs() <<
" Can't unroll; loop exit-block-insertion failed.\n");
449 return LoopUnrollResult::Unmodified;
453 if (!L->isSafeToClone()) {
454 LLVM_DEBUG(
dbgs() <<
" Can't unroll; Loop body cannot be cloned.\n");
455 return LoopUnrollResult::Unmodified;
458 if (L->getHeader()->hasAddressTaken()) {
461 dbgs() <<
" Won't unroll loop: address of header block is taken.\n");
462 return LoopUnrollResult::Unmodified;
469 BasicBlock *Preheader = L->getLoopPreheader();
473 L->getExitBlocks(ExitBlocks);
474 std::vector<BasicBlock *> OriginalLoopBlocks = L->getBlocks();
478 unsigned EstimatedLoopInvocationWeight = 0;
479 std::optional<unsigned> OriginalTripCount =
484 if (MaxTripCount && ULO.
Count > MaxTripCount)
485 ULO.
Count = MaxTripCount;
489 unsigned TripMultiple;
490 unsigned BreakoutTrip;
497 L->getExitingBlocks(ExitingBlocks);
498 for (
auto *ExitingBlock : ExitingBlocks) {
501 auto *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator());
508 if (
Info.TripCount != 0) {
510 Info.TripMultiple = 0;
512 Info.BreakoutTrip =
Info.TripMultiple =
515 Info.ExitOnTrue = !L->contains(BI->getSuccessor(0));
516 Info.ExitingBlocks.push_back(ExitingBlock);
517 LLVM_DEBUG(
dbgs() <<
" Exiting block %" << ExitingBlock->getName()
518 <<
": TripCount=" <<
Info.TripCount
519 <<
", TripMultiple=" <<
Info.TripMultiple
520 <<
", BreakoutTrip=" <<
Info.BreakoutTrip <<
"\n");
526 const bool CompletelyUnroll = ULO.
Count == MaxTripCount;
528 const bool PreserveOnlyFirst = CompletelyUnroll && MaxOrZero;
532 if (CompletelyUnroll)
541 bool NeedToFixLCSSA =
542 PreserveLCSSA && CompletelyUnroll &&
556 bool LatchIsExiting = L->isLoopExiting(LatchBlock);
557 if (!LatchBI || (LatchBI->isConditional() && !LatchIsExiting)) {
559 dbgs() <<
"Can't unroll; a conditional latch must exit the loop");
560 return LoopUnrollResult::Unmodified;
568 bool HasConvergent =
false;
569 for (
auto &BB : L->blocks())
571 if (
auto *CB = dyn_cast<CallBase>(&
I))
572 HasConvergent |= CB->isConvergent();
574 "Can't runtime unroll if loop contains a convergent operation.");
577 bool EpilogProfitability =
585 PreserveLCSSA, RemainderLoop)) {
590 "generated when assuming runtime trip count\n");
591 return LoopUnrollResult::Unmodified;
597 if (CompletelyUnroll) {
598 LLVM_DEBUG(
dbgs() <<
"COMPLETELY UNROLLING loop %" << Header->getName()
599 <<
" with trip count " << ULO.
Count <<
"!\n");
604 <<
"completely unrolled loop with "
605 << NV(
"UnrollCount", ULO.
Count) <<
" iterations";
608 LLVM_DEBUG(
dbgs() <<
"UNROLLING loop %" << Header->getName() <<
" by "
618 Diag <<
"unrolled loop by a factor of " << NV(
"UnrollCount", ULO.
Count);
620 Diag <<
" with run-time trip count";
643 ++NumUnrolledNotLatch;
648 std::vector<PHINode*> OrigPHINode;
650 OrigPHINode.push_back(cast<PHINode>(
I));
653 std::vector<BasicBlock *> Headers;
654 std::vector<BasicBlock *> Latches;
655 Headers.push_back(Header);
656 Latches.push_back(LatchBlock);
668 std::vector<BasicBlock*> UnrolledLoopBlocks = L->getBlocks();
675 for (
Loop *SubLoop : *L)
676 LoopsToSimplify.
insert(SubLoop);
680 if (Header->getParent()->shouldEmitDebugInfoForProfiling() &&
684 if (!
I.isDebugOrPseudoInst())
686 auto NewDIL = DIL->cloneByMultiplyingDuplicationFactor(ULO.
Count);
688 I.setDebugLoc(*NewDIL);
691 <<
"Failed to create new discriminator: "
692 << DIL->getFilename() <<
" Line: " << DIL->getLine());
703 auto BlockInsertPt = std::next(LatchBlock->
getIterator());
704 for (
unsigned It = 1; It != ULO.
Count; ++It) {
712 Header->getParent()->insert(BlockInsertPt, New);
715 "Header should not be in a sub-loop");
719 LoopsToSimplify.
insert(NewLoops[OldLoop]);
724 for (
PHINode *OrigPHI : OrigPHINode) {
725 PHINode *NewPHI = cast<PHINode>(VMap[OrigPHI]);
727 if (
Instruction *InValI = dyn_cast<Instruction>(InVal))
728 if (It > 1 && L->contains(InValI))
729 InVal = LastValueMap[InValI];
730 VMap[OrigPHI] = InVal;
735 LastValueMap[*BB] = New;
738 LastValueMap[VI->first] = VI->second;
742 if (L->contains(Succ))
747 if (It != LastValueMap.
end())
756 Headers.push_back(New);
757 if (*BB == LatchBlock)
758 Latches.push_back(New);
762 auto ExitInfoIt = ExitInfos.
find(*BB);
763 if (ExitInfoIt != ExitInfos.
end())
764 ExitInfoIt->second.ExitingBlocks.push_back(New);
767 UnrolledLoopBlocks.push_back(New);
776 auto BBDomNode = DT->
getNode(*BB);
777 auto BBIDom = BBDomNode->
getIDom();
778 BasicBlock *OriginalBBIDom = BBIDom->getBlock();
780 New, cast<BasicBlock>(LastValueMap[cast<Value>(OriginalBBIDom)]));
788 if (
auto *II = dyn_cast<AssumeInst>(&
I))
795 std::string ext = (
Twine(
"It") +
Twine(It)).str();
797 Header->getContext(), ext);
802 for (
PHINode *PN : OrigPHINode) {
803 if (CompletelyUnroll) {
804 PN->replaceAllUsesWith(PN->getIncomingValueForBlock(Preheader));
805 PN->eraseFromParent();
806 }
else if (ULO.
Count > 1) {
807 Value *InVal = PN->removeIncomingValue(LatchBlock,
false);
810 if (
Instruction *InValI = dyn_cast<Instruction>(InVal)) {
811 if (L->contains(InValI))
812 InVal = LastValueMap[InVal];
814 assert(Latches.back() == LastValueMap[LatchBlock] &&
"bad last latch");
815 PN->addIncoming(InVal, Latches.back());
821 for (
unsigned i = 0, e = Latches.size(); i != e; ++i) {
822 unsigned j = (i + 1) % e;
823 Latches[i]->getTerminator()->replaceSuccessorWith(Headers[i], Headers[j]);
831 for (
auto *BB : OriginalLoopBlocks) {
832 auto *BBDomNode = DT->
getNode(BB);
834 for (
auto *ChildDomNode : BBDomNode->children()) {
835 auto *ChildBB = ChildDomNode->getBlock();
836 if (!L->contains(ChildBB))
844 for (
auto *ChildBB : ChildrenToUpdate)
850 DT->
verify(DominatorTree::VerificationLevel::Fast));
853 auto SetDest = [&](
BasicBlock *Src,
bool WillExit,
bool ExitOnTrue) {
854 auto *Term = cast<BranchInst>(Src->getTerminator());
855 const unsigned Idx = ExitOnTrue ^ WillExit;
864 Term->eraseFromParent();
866 DTUpdates.
emplace_back(DominatorTree::Delete, Src, DeadSucc);
869 auto WillExit = [&](
const ExitInfo &
Info,
unsigned i,
unsigned j,
870 bool IsLatch) -> std::optional<bool> {
871 if (CompletelyUnroll) {
872 if (PreserveOnlyFirst) {
880 if (
Info.TripCount && j !=
Info.TripCount)
888 if (IsLatch && j != 0)
893 if (j !=
Info.BreakoutTrip &&
894 (
Info.TripMultiple == 0 || j %
Info.TripMultiple != 0)) {
904 for (
auto &Pair : ExitInfos) {
905 ExitInfo &
Info = Pair.second;
906 for (
unsigned i = 0, e =
Info.ExitingBlocks.size(); i != e; ++i) {
908 unsigned j = (i + 1) % e;
909 bool IsLatch = Pair.first == LatchBlock;
910 std::optional<bool> KnownWillExit = WillExit(
Info, i, j, IsLatch);
911 if (!KnownWillExit) {
912 if (!
Info.FirstExitingBlock)
913 Info.FirstExitingBlock =
Info.ExitingBlocks[i];
922 if (*KnownWillExit && !IsLatch) {
923 if (!
Info.FirstExitingBlock)
924 Info.FirstExitingBlock =
Info.ExitingBlocks[i];
928 SetDest(
Info.ExitingBlocks[i], *KnownWillExit,
Info.ExitOnTrue);
934 if (ExitingBlocks.
size() == 1 && ExitInfos.
size() == 1) {
942 auto &[OriginalExit,
Info] = *ExitInfos.
begin();
943 if (!
Info.FirstExitingBlock)
944 Info.FirstExitingBlock =
Info.ExitingBlocks.back();
946 if (L->contains(
C->getBlock()))
955 if (!LatchIsExiting && CompletelyUnroll) {
965 BranchInst *Term = dyn_cast<BranchInst>(Latch->getTerminator());
967 (CompletelyUnroll && !LatchIsExiting && Latch == Latches.back())) &&
968 "Need a branch as terminator, except when fully unrolling with "
969 "unconditional latch");
970 if (Term && Term->isUnconditional()) {
976 DTUToUse ?
nullptr : DT)) {
978 std::replace(Latches.begin(), Latches.end(), Dest, Fold);
989 DT->
verify(DominatorTree::VerificationLevel::Fast));
996 NumCompletelyUnrolled += CompletelyUnroll;
999 Loop *OuterL = L->getParentLoop();
1001 if (CompletelyUnroll) {
1005 }
else if (OriginalTripCount) {
1009 EstimatedLoopInvocationWeight);
1024 if (PreserveLCSSA && OuterL && CompletelyUnroll && !NeedToFixLCSSA)
1034 if (NeedToFixLCSSA) {
1039 Loop *FixLCSSALoop = OuterL;
1040 if (!FixLCSSALoop->
contains(LatchLoop))
1045 }
else if (PreserveLCSSA) {
1047 "Loops should be in LCSSA form after loop-unroll.");
1052 simplifyLoop(OuterL, DT, LI, SE, AC,
nullptr, PreserveLCSSA);
1055 for (
Loop *SubLoop : LoopsToSimplify)
1056 simplifyLoop(SubLoop, DT, LI, SE, AC,
nullptr, PreserveLCSSA);
1059 return CompletelyUnroll ? LoopUnrollResult::FullyUnrolled
1060 : LoopUnrollResult::PartiallyUnrolled;
for(const MachineOperand &MO :llvm::drop_begin(OldMI.operands(), Desc.getNumOperands()))
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Analysis containing CSE Info
Optimize for code generation
This file contains the declarations for the subclasses of Constant, which represent the different fla...
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.
DenseMap< Block *, BlockRelaxAux > Blocks
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
This file defines a set of templates that efficiently compute a dominator tree over a generic graph.
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
static bool needToInsertPhisForLCSSA(Loop *L, const std::vector< BasicBlock * > &Blocks, LoopInfo *LI)
Check if unrolling created a situation where we need to insert phi nodes to preserve LCSSA form.
static bool isEpilogProfitable(Loop *L)
The function chooses which type of unroll (epilog or prolog) is more profitabale.
void loadCSE(Loop *L, DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI, BatchAAResults &BAA, function_ref< MemorySSA *()> GetMSSA)
Value * getMatchingValue(LoadValue LV, LoadInst *LI, unsigned CurrentGeneration, BatchAAResults &BAA, function_ref< MemorySSA *()> GetMSSA)
static cl::opt< bool > UnrollRuntimeEpilog("unroll-runtime-epilog", cl::init(false), cl::Hidden, cl::desc("Allow runtime unrolled loops to be unrolled " "with epilog instead of prolog."))
static cl::opt< bool > UnrollVerifyLoopInfo("unroll-verify-loopinfo", cl::Hidden, cl::desc("Verify loopinfo after unrolling"), cl::init(false))
static cl::opt< bool > UnrollVerifyDomtree("unroll-verify-domtree", cl::Hidden, cl::desc("Verify domtree after unrolling"), cl::init(false))
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.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file implements a set that has insertion order iteration characteristics.
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)
This defines the Use class.
void childGeneration(unsigned generation)
unsigned currentGeneration() const
unsigned childGeneration() const
StackNode(ScopedHashTable< const SCEV *, LoadValue > &AvailableLoads, unsigned cg, DomTreeNode *N, DomTreeNode::const_iterator Child, DomTreeNode::const_iterator End)
DomTreeNode::const_iterator end() const
DomTreeNode * nextChild()
DomTreeNode::const_iterator childIter() const
Class for arbitrary precision integers.
APInt sadd_ov(const APInt &RHS, bool &Overflow) const
A cache of @llvm.assume calls within a function.
void registerAssumption(AssumeInst *CI)
Add an @llvm.assume intrinsic to this function's cache.
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
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...
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
This class is a wrapper over an AAResults, and it is intended to be used only when there are no IR ch...
Conditional or Unconditional Branch instruction.
static BranchInst * Create(BasicBlock *IfTrue, BasicBlock::iterator InsertBefore)
A parsed version of the target data layout string in and methods for querying it.
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
iterator find(const_arg_type_t< KeyT > Val)
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&... Args)
iterator_range< iterator > children()
DomTreeNodeBase * getIDom() const
typename SmallVector< DomTreeNodeBase *, 4 >::const_iterator const_iterator
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
DominatorTree & getDomTree()
Flush DomTree updates and return DomTree.
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...
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
An instruction for reading from memory.
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
BlockT * getHeader() const
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)
This method is used by other analyses to update loop information.
void addChildLoop(LoopT *NewChild)
Add the specified loop to be a child of this loop.
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
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(const LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
RPOIterator endRPO() const
void verify(const DominatorTreeBase< BlockT, false > &DomTree) const
void addTopLevelLoop(LoopT *New)
This adds the specified loop to the collection of top-level loops.
LoopT * AllocateLoop(ArgsTy &&...Args)
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
bool replacementPreservesLCSSAForm(Instruction *From, Value *To)
Returns true if replacing From with To everywhere is guaranteed to preserve LCSSA form.
void erase(Loop *L)
Update LoopInfo after removing the last backedge from a loop.
Represents a single loop in the control flow graph.
bool isLCSSAForm(const DominatorTree &DT, bool IgnoreTokens=true) const
Return true if the Loop is in LCSSA form.
const MDOperand & getOperand(unsigned I) const
unsigned getNumOperands() const
Return number of MDNode operands.
StringRef getString() const
MemoryAccess * getClobberingMemoryAccess(const Instruction *I, BatchAAResults &AA)
Given a memory Mod/Ref/ModRef'ing instruction, calling this will give you the nearest dominating Memo...
Encapsulates MemorySSA, including all data associated with memory accesses.
bool dominates(const MemoryAccess *A, const MemoryAccess *B) const
Given two memory accesses in potentially different blocks, determine whether MemoryAccess A dominates...
MemorySSAWalker * getWalker()
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
Value * getIncomingValueForBlock(const BasicBlock *BB) const
This class represents an analyzed expression in the program.
The main scalar evolution driver.
unsigned getSmallConstantTripMultiple(const Loop *L, const SCEV *ExitCount)
Returns the largest constant divisor of the trip count as a normal unsigned value,...
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
unsigned getSmallConstantMaxTripCount(const Loop *L)
Returns the upper bound of the loop trip count as a normal unsigned value.
bool isBackedgeTakenCountMaxOrZero(const Loop *L)
Return true if the backedge taken count is either the value returned by getConstantMaxBackedgeTakenCo...
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...
void forgetBlockAndLoopDispositions(Value *V=nullptr)
Called when the client has changed the disposition of values in a loop or block.
unsigned getSmallConstantTripCount(const Loop *L)
Returns the exact trip count of the loop if we can compute it, and the result is a small constant.
void insert(const K &Key, const V &Val)
V lookup(const K &Key) const
bool insert(const value_type &X)
Insert a new element into the SetVector.
A SetVector that performs no allocations if smaller than a certain size.
reference emplace_back(ArgTypes &&... Args)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
StringRef - Represent a constant reference to a string, i.e.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
A Use represents the edge between a Value definition and its users.
iterator find(const KeyT &Val)
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
An efficient, type-erasing, non-owning reference to a callable.
self_iterator getIterator()
@ C
The default llvm calling convention, compatible with C.
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
bool match(Val *V, const Pattern &P)
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
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.
std::optional< unsigned > getLoopEstimatedTripCount(Loop *L, unsigned *EstimatedLoopInvocationWeight=nullptr)
Returns a loop's estimated trip count based on branch weight metadata.
void simplifyLoopAfterUnroll(Loop *L, bool SimplifyIVs, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, const TargetTransformInfo *TTI, AAResults *AA=nullptr)
Perform some cleanup and simplifications on loops after unrolling.
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 successors(const MachineBasicBlock *BB)
bool formLCSSARecursively(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)
Put a loop nest into LCSSA form.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
cl::opt< bool > EnableFSDiscriminator
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 isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction will return.
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...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool simplifyLoopIVs(Loop *L, ScalarEvolution *SE, DominatorTree *DT, LoopInfo *LI, const TargetTransformInfo *TTI, SmallVectorImpl< WeakTrackingVH > &Dead)
SimplifyLoopIVs - Simplify users of induction variables within this loop.
SmallVector< ValueTypeFromRangeType< R >, Size > to_vector(R &&Range)
Given a range of type R, iterate the entire range and return a SmallVector with elements of the vecto...
LoopUnrollResult
Represents the result of a UnrollLoop invocation.
unsigned changeToUnreachable(Instruction *I, bool PreserveLCSSA=false, DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Insert an unreachable instruction before the specified instruction, making it and the rest of the cod...
bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr, bool PredecessorWithTwoSuccessors=false, DominatorTree *DT=nullptr)
Attempts to merge a block into its predecessor, if possible.
bool setLoopEstimatedTripCount(Loop *L, unsigned EstimatedTripCount, unsigned EstimatedLoopInvocationWeight)
Set a loop's branch weight metadata to reflect that loop has EstimatedTripCount iterations and Estima...
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.
const Loop * addClonedBlockToLoopInfo(BasicBlock *OriginalBB, BasicBlock *ClonedBB, LoopInfo *LI, NewLoopsMap &NewLoops)
Adds ClonedBB to LoopInfo, creates a new loop for ClonedBB if necessary and adds a mapping from the o...
void identifyNoAliasScopesToClone(ArrayRef< BasicBlock * > BBs, SmallVectorImpl< MDNode * > &NoAliasDeclScopes)
Find the 'llvm.experimental.noalias.scope.decl' intrinsics in the specified basic blocks and extract ...
MDNode * GetUnrollMetadata(MDNode *LoopID, StringRef Name)
Given an llvm.loop loop id metadata node, returns the loop hint metadata node with the given name (fo...
bool UnrollRuntimeLoopRemainder(Loop *L, unsigned Count, bool AllowExpensiveTripCount, bool UseEpilogRemainder, bool UnrollRemainder, bool ForgetAllSCEV, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, const TargetTransformInfo *TTI, bool PreserveLCSSA, Loop **ResultLoop=nullptr)
Insert code in the prolog/epilog code when unrolling a loop with a run-time trip-count.
LoopUnrollResult UnrollLoop(Loop *L, UnrollLoopOptions ULO, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, const llvm::TargetTransformInfo *TTI, OptimizationRemarkEmitter *ORE, bool PreserveLCSSA, Loop **RemainderLoop=nullptr, AAResults *AA=nullptr)
Unroll the given loop by Count.
LoadValue(Instruction *Inst, unsigned Generation)
Incoming for lane maks phi as machine instruction, incoming register Reg and incoming block Block are...
bool AllowExpensiveTripCount