Go to the documentation of this file.
59 #include <type_traits>
64 #define DEBUG_TYPE "loop-unroll-and-jam"
66 STATISTIC(NumUnrolledAndJammed,
"Number of loops unroll and jammed");
67 STATISTIC(NumCompletelyUnrolledAndJammed,
"Number of loops unroll and jammed");
91 if (
BB == SubLoopPreHeader)
95 if (!ForeBlocks.count(Succ))
140 template <
typename T>
144 for (
auto &Phi : Header->
phis()) {
145 Value *V = Phi.getIncomingValueForBlock(Latch);
147 Worklist.push_back(
I);
150 while (!Worklist.empty()) {
155 if (AftBlocks.
count(
I->getParent()))
156 for (
auto &U :
I->operands())
158 Worklist.push_back(II);
171 std::vector<Instruction *> Visited;
174 if (AftBlocks.
count(
I->getParent()))
175 Visited.push_back(
I);
182 if (
I->getParent() != InsertLocBB)
183 I->moveBefore(InsertLoc);
223 unsigned TripMultiple,
bool UnrollRemainder,
230 assert(Header &&
"No header.");
235 if (TripCount == 0 && Count < 2) {
236 LLVM_DEBUG(
dbgs() <<
"Won't unroll-and-jam; almost nothing to do\n");
242 assert(TripCount == 0 || TripCount % TripMultiple == 0);
245 bool CompletelyUnroll = (Count == TripCount);
248 if (TripMultiple == 1 || TripMultiple % Count != 0) {
251 UnrollRemainder,
false,
252 LI, SE, DT, AC,
TTI,
true, EpilogueLoop)) {
253 LLVM_DEBUG(
dbgs() <<
"Won't unroll-and-jam; remainder loop could not be "
254 "generated when assuming runtime trip count\n");
268 if (CompletelyUnroll) {
270 << Header->
getName() <<
" with trip count " << TripCount
274 <<
"completely unroll and jammed loop with "
275 <<
NV(
"UnrollCount", TripCount) <<
" iterations");
277 auto DiagBuilder = [&]() {
280 return Diag <<
"unroll and jammed loop by a factor of "
281 <<
NV(
"UnrollCount", Count);
286 if (TripMultiple != 1) {
287 LLVM_DEBUG(
dbgs() <<
" with " << TripMultiple <<
" trips per branch");
289 return DiagBuilder() <<
" with " <<
NV(
"TripMultiple", TripMultiple)
290 <<
" trips per branch";
294 ORE->
emit([&]() {
return DiagBuilder() <<
" with run-time trip count"; });
301 assert(Preheader &&
"No preheader");
302 assert(LatchBlock &&
"No latch block");
307 bool SubLoopContinueOnTrue = SubLoop->
contains(
321 std::vector<BasicBlock *> ForeBlocksFirst;
322 std::vector<BasicBlock *> ForeBlocksLast;
323 std::vector<BasicBlock *> SubLoopBlocksFirst;
324 std::vector<BasicBlock *> SubLoopBlocksLast;
325 std::vector<BasicBlock *> AftBlocksFirst;
326 std::vector<BasicBlock *> AftBlocksLast;
327 ForeBlocksFirst.push_back(Header);
329 SubLoopBlocksFirst.push_back(SubLoop->
getHeader());
338 Header, LatchBlock, ForeBlocksLast[0]->getTerminator(), AftBlocks);
352 if (!isa<DbgInfoIntrinsic>(&
I))
354 auto NewDIL = DIL->cloneByMultiplyingDuplicationFactor(Count);
356 I.setDebugLoc(NewDIL.getValue());
359 <<
"Failed to create new discriminator: "
360 << DIL->getFilename() <<
" Line: " << DIL->getLine());
364 for (
unsigned It = 1; It != Count; ++It) {
370 NewLoops[SubLoop] = SubLoop;
381 if (*
BB == ForeBlocksFirst[0])
382 ForeBlocksFirst.push_back(New);
383 if (*
BB == ForeBlocksLast[0])
384 ForeBlocksLast.push_back(New);
385 }
else if (SubLoopBlocks.
count(*
BB)) {
386 if (*
BB == SubLoopBlocksFirst[0])
387 SubLoopBlocksFirst.push_back(New);
388 if (*
BB == SubLoopBlocksLast[0])
389 SubLoopBlocksLast.push_back(New);
390 }
else if (AftBlocks.
count(*
BB)) {
391 if (*
BB == AftBlocksFirst[0])
392 AftBlocksFirst.push_back(New);
393 if (*
BB == AftBlocksLast[0])
394 AftBlocksLast.push_back(New);
400 PrevItValueMap[New] = (It == 1 ? *
BB : LastValueMap[*
BB]);
401 LastValueMap[*
BB] = New;
404 PrevItValueMap[
VI->second] =
405 const_cast<Value *
>(It == 1 ?
VI->first : LastValueMap[
VI->first]);
406 LastValueMap[
VI->first] =
VI->second;
409 NewBlocks.push_back(New);
412 if (*
BB == ForeBlocksFirst[0])
414 else if (*
BB == SubLoopBlocksFirst[0])
416 else if (*
BB == AftBlocksFirst[0])
422 auto BBIDom = BBDomNode->
getIDom();
423 BasicBlock *OriginalBBIDom = BBIDom->getBlock();
425 assert(LastValueMap[cast<Value>(OriginalBBIDom)]);
427 New, cast<BasicBlock>(LastValueMap[cast<Value>(OriginalBBIDom)]));
435 if (
auto *II = dyn_cast<IntrinsicInst>(&
I))
436 if (II->getIntrinsicID() == Intrinsic::assume)
443 for (
PHINode &Phi : ForeBlocksFirst[It]->phis()) {
444 Value *OldValue = Phi.getIncomingValueForBlock(AftBlocksLast[It]);
445 assert(OldValue &&
"should have incoming edge from Aft[It]");
446 Value *NewValue = OldValue;
447 if (
Value *PrevValue = PrevItValueMap[OldValue])
448 NewValue = PrevValue;
450 assert(Phi.getNumOperands() == 2);
451 Phi.setIncomingBlock(0, ForeBlocksLast[It - 1]);
452 Phi.setIncomingValue(0, NewValue);
453 Phi.removeIncomingValue(1);
467 for (
unsigned b = 0;
b < Phi.getNumIncomingValues(); ++
b) {
468 if (Phi.getIncomingBlock(
b) == OldBB) {
469 Value *OldValue = Phi.getIncomingValue(
b);
470 if (
Value *LastValue = LastValueMap[OldValue])
471 Phi.setIncomingValue(
b, LastValue);
472 Phi.setIncomingBlock(
b, NewBB);
486 updatePHIBlocksAndValues(LoopExit, AftBlocksLast[0], AftBlocksLast.
back(),
491 cast<BranchInst>(ForeBlocksLast.back()->getTerminator());
495 if (CompletelyUnroll) {
496 while (
PHINode *Phi = dyn_cast<PHINode>(ForeBlocksFirst[0]->
begin())) {
497 Phi->replaceAllUsesWith(Phi->getIncomingValueForBlock(Preheader));
498 Phi->getParent()->getInstList().erase(Phi);
502 updatePHIBlocksAndValues(ForeBlocksFirst[0], AftBlocksLast[0],
503 AftBlocksLast.back(), LastValueMap);
506 for (
unsigned It = 1; It != Count; It++) {
509 cast<BranchInst>(ForeBlocksLast[It - 1]->getTerminator());
516 cast<BranchInst>(SubLoopBlocksLast.back()->getTerminator());
517 SubTerm->
setSuccessor(!SubLoopContinueOnTrue, SubLoopBlocksFirst[0]);
518 SubTerm->
setSuccessor(SubLoopContinueOnTrue, AftBlocksFirst[0]);
519 SubLoopBlocksFirst[0]->replacePhiUsesWith(ForeBlocksLast[0],
520 ForeBlocksLast.back());
521 SubLoopBlocksFirst[0]->replacePhiUsesWith(SubLoopBlocksLast[0],
522 SubLoopBlocksLast.back());
524 for (
unsigned It = 1; It != Count; It++) {
528 cast<BranchInst>(SubLoopBlocksLast[It - 1]->getTerminator());
532 SubLoopBlocksFirst[It]->replacePhiUsesWith(ForeBlocksLast[It],
533 ForeBlocksLast.back());
534 SubLoopBlocksFirst[It]->replacePhiUsesWith(SubLoopBlocksLast[It],
535 SubLoopBlocksLast.back());
536 movePHIs(SubLoopBlocksFirst[It], SubLoopBlocksFirst[0]);
540 BranchInst *AftTerm = cast<BranchInst>(AftBlocksLast.back()->getTerminator());
541 if (CompletelyUnroll) {
545 AftTerm->
setSuccessor(!ContinueOnTrue, ForeBlocksFirst[0]);
547 "Expecting the ContinueOnTrue successor of AftTerm to be LoopExit");
549 AftBlocksFirst[0]->replacePhiUsesWith(SubLoopBlocksLast[0],
550 SubLoopBlocksLast.back());
552 for (
unsigned It = 1; It != Count; It++) {
556 cast<BranchInst>(AftBlocksLast[It - 1]->getTerminator());
560 AftBlocksFirst[It]->replacePhiUsesWith(SubLoopBlocksLast[It],
561 SubLoopBlocksLast.back());
562 movePHIs(AftBlocksFirst[It], AftBlocksFirst[0]);
571 SubLoopBlocksFirst[0]);
573 SubLoopBlocksLast[0], AftBlocksFirst[0]);
576 ForeBlocksLast.back(), SubLoopBlocksFirst[0]);
578 SubLoopBlocksLast.back(), AftBlocksFirst[0]);
584 MergeBlocks.
insert(ForeBlocksLast.begin(), ForeBlocksLast.end());
585 MergeBlocks.
insert(SubLoopBlocksLast.begin(), SubLoopBlocksLast.end());
586 MergeBlocks.
insert(AftBlocksLast.begin(), AftBlocksLast.end());
600 NumCompletelyUnrolledAndJammed += CompletelyUnroll;
601 ++NumUnrolledAndJammed;
604 if (CompletelyUnroll)
617 if (!CompletelyUnroll)
633 if (
auto *Ld = dyn_cast<LoadInst>(&
I)) {
636 MemInstr.push_back(&
I);
637 }
else if (
auto *St = dyn_cast<StoreInst>(&
I)) {
640 MemInstr.push_back(&
I);
641 }
else if (
I.mayReadOrWriteMemory()) {
650 unsigned UnrollLevel,
unsigned JamLevel,
654 for (
unsigned CurLoopDepth = UnrollLevel + 1; CurLoopDepth <= JamLevel;
656 auto JammedDir =
D->getDirection(CurLoopDepth);
668 unsigned UnrollLevel,
unsigned JamLevel,
671 for (
unsigned CurLoopDepth = UnrollLevel + 1; CurLoopDepth <= JamLevel;
673 auto JammedDir =
D->getDirection(CurLoopDepth);
682 return Sequentialized;
694 unsigned UnrollLevel,
unsigned JamLevel,
696 assert(UnrollLevel <= JamLevel &&
697 "Expecting JamLevel to be at least UnrollLevel");
702 if (isa<LoadInst>(Src) && isa<LoadInst>(Dst))
715 std::unique_ptr<Dependence>
D = DI.
depends(Src, Dst,
true);
718 assert(
D->isOrdered() &&
"Expected an output, flow or anti dep.");
720 if (
D->isConfused()) {
722 <<
" " << *Src <<
"\n"
723 <<
" " << *Dst <<
"\n");
731 for (
unsigned CurLoopDepth = 1; CurLoopDepth < UnrollLevel; ++CurLoopDepth)
735 auto UnrollDirection =
D->getDirection(UnrollLevel);
745 Sequentialized,
D.get()))
750 Sequentialized,
D.get()))
763 if (ForeBlocksMap.
find(L) != ForeBlocksMap.
end())
764 AllBlocks.push_back(ForeBlocksMap.
lookup(L));
765 AllBlocks.push_back(SubLoopBlocks);
767 if (AftBlocksMap.
find(L) != AftBlocksMap.
end())
768 AllBlocks.push_back(AftBlocksMap.
lookup(L));
774 CurrentLoadsAndStores.
clear();
778 Loop *CurLoop = LI.
getLoopFor((*Blocks.begin())->front().getParent());
781 for (
auto *Earlier : EarlierLoadsAndStores) {
784 unsigned CommonLoopDepth =
std::min(EarlierDepth, CurLoopDepth);
785 for (
auto *Later : CurrentLoadsAndStores) {
786 if (!
checkDependency(Earlier, Later, LoopDepth, CommonLoopDepth,
false,
792 size_t NumInsts = CurrentLoadsAndStores.size();
793 for (
size_t I = 0;
I < NumInsts; ++
I) {
794 for (
size_t J =
I; J < NumInsts; ++J) {
796 LoopDepth, CurLoopDepth,
true, DI))
801 EarlierLoadsAndStores.
append(CurrentLoadsAndStores.begin(),
802 CurrentLoadsAndStores.end());
812 const Loop *L = &Root;
827 if (SubLoopsSize == 0)
831 if (SubLoopsSize != 1)
839 LLVM_DEBUG(
dbgs() <<
"Won't unroll-and-jam; only loops with single exit "
840 "blocks can be unrolled and jammed.\n");
846 LLVM_DEBUG(
dbgs() <<
"Won't unroll-and-jam; only loops with single "
847 "exiting blocks can be unrolled and jammed.\n");
866 LLVM_DEBUG(
dbgs() <<
"Won't unroll-and-jam; Ineligible loop form\n");
928 LLVM_DEBUG(
dbgs() <<
"Won't unroll-and-jam; Incompatible loop layout\n");
935 if (AftBlocksMap[L].
size() != 1) {
936 LLVM_DEBUG(
dbgs() <<
"Won't unroll-and-jam; Can't currently handle "
937 "multiple blocks after the loop\n");
944 return !hasIterationCountInvariantInParent(SubLoop, SE);
946 LLVM_DEBUG(
dbgs() <<
"Won't unroll-and-jam; Inner loop iteration count is "
947 "not consistent on each iteration\n");
955 LLVM_DEBUG(
dbgs() <<
"Won't unroll-and-jam; Something may throw\n");
971 Header, Latch, AftBlocks, [&AftBlocks, &SubLoop](
Instruction *
I) {
974 if (AftBlocks.
count(
I->getParent())) {
981 if (I->mayHaveSideEffects() || I->mayReadOrWriteMemory())
988 "instructions after subloop to before it\n");
997 LLVM_DEBUG(
dbgs() <<
"Won't unroll-and-jam; failed dependency check\n");
This class represents lattice values for constants.
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...
BlockT * getExitBlock() const
If getExitBlocks would return exactly one block, return that block.
const Function * getParent() const
Return the enclosing method, or null if none.
static bool preservesForwardDependence(Instruction *Src, Instruction *Dst, unsigned UnrollLevel, unsigned JamLevel, bool Sequentialized, Dependence *D)
const BasicBlockListType & getBasicBlockList() const
Get the underlying elements of the Function...
static bool checkDependencies(Loop &Root, const BasicBlockSet &SubLoopBlocks, const DenseMap< Loop *, BasicBlockSet > &ForeBlocksMap, const DenseMap< Loop *, BasicBlockSet > &AftBlocksMap, DependenceInfo &DI, LoopInfo &LI)
Represents a single loop in the control flow graph.
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...
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
LoopUnrollResult UnrollAndJamLoop(Loop *L, unsigned Count, unsigned TripCount, unsigned TripMultiple, bool UnrollRemainder, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, const TargetTransformInfo *TTI, OptimizationRemarkEmitter *ORE, Loop **EpilogueLoop=nullptr)
void verify(const DominatorTreeBase< BlockT, false > &DomTree) const
DebugLoc getStartLoc() const
Return the debug location of the start of this loop.
The main scalar evolution driver.
Dependence - This class represents a dependence between two memory memory references in a function.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
bool dominates(const Value *Def, const Use &U) const
Return true if value Def dominates use U, in the sense that Def is available at U,...
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
unsigned getNumSuccessors() const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
DiagnosticInfoOptimizationBase::Argument NV
static bool partitionLoopBlocks(Loop &L, BasicBlockSet &ForeBlocks, BasicBlockSet &AftBlocks, DominatorTree &DT)
LLVM_NODISCARD T pop_back_val()
DomTreeNodeBase * getIDom() const
succ_range successors(Instruction *I)
Simple and conservative implementation of LoopSafetyInfo that can give false-positive answers to its ...
static bool preservesBackwardDependence(Instruction *Src, Instruction *Dst, unsigned UnrollLevel, unsigned JamLevel, bool Sequentialized, Dependence *D)
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
block_iterator block_end() const
LLVM Basic Block Representation.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
const std::vector< LoopT * > & getSubLoops() const
Return the loops contained entirely within this loop.
static bool partitionOuterLoopBlocks(Loop &Root, Loop &JamLoop, BasicBlockSet &JamLoopBlocks, DenseMap< Loop *, BasicBlockSet > &ForeBlocksMap, DenseMap< Loop *, BasicBlockSet > &AftBlocksMap, DominatorTree &DT)
Partition blocks in a loop nest into blocks before and after each inner loop.
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
iterator begin()
Instruction iterator methods.
void remapInstructionsInBlocks(const SmallVectorImpl< BasicBlock * > &Blocks, ValueToValueMapTy &VMap)
Remaps instructions in Blocks using the mapping in VMap.
the resulting code requires compare and branches when and if the revised code is with conditional branches instead of More there is a byte word extend before each where there should be only and the condition codes are not remembered when the same two values are compared twice More LSR enhancements i8 and i32 load store addressing modes are identical int b
iterator_range< block_iterator > blocks() const
void simplifyLoopAfterUnroll(Loop *L, bool SimplifyIVs, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, const TargetTransformInfo *TTI)
Perform some cleanup and simplifications on loops after unrolling.
ArrayRef< BlockT * > getBlocks() const
Get a list of the basic blocks which make up this loop.
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 registerAssumption(CallInst *CI)
Add an @llvm.assume intrinsic to this function's cache.
BasicBlock * getSuccessor(unsigned Idx) const
Return the specified successor. This instruction must be a terminator.
SmallVector< const LoopT *, 4 > getLoopsInPreorder() const
Return all loops in the loop nest rooted by the loop in preorder, with siblings in forward program or...
BlockT * getExitingBlock() const
If getExitingBlocks would return exactly one block, return that block.
@ FullyUnrolled
The loop was fully unrolled into straight-line code.
block_iterator block_begin() const
std::vector< BasicBlock * >::const_reverse_iterator RPOIterator
Store the result of a depth first search within basic blocks contained by a single loop.
static bool getLoadsAndStores(BasicBlockSet &Blocks, SmallVector< Instruction *, 4 > &MemInstr)
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches,...
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...
DependenceInfo - This class is the main dependence-analysis driver.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
static bool processHeaderPhiOperands(BasicBlock *Header, BasicBlock *Latch, BasicBlockSet &AftBlocks, T Visit)
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
bool isDebugInfoForProfiling() const
Returns true if we should emit debug info for profiling.
DominatorTree & getDomTree()
Flush DomTree updates and return DomTree.
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
@ PartiallyUnrolled
The loop was partially unrolled – we still have a loop, but with a smaller trip count.
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
LoopUnrollResult
Represents the result of a UnrollLoop invocation.
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
iterator find(const_arg_type_t< KeyT > Val)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
unsigned getLoopDepth() const
Return the nesting level of this loop.
void erase(Loop *L)
Update LoopInfo after removing the last backedge from a loop.
void computeLoopSafetyInfo(const Loop *CurLoop) override
Computes safety information for a loop checks loop body & header for the possibility of may throw exc...
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
bool isUnconditional() const
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
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.
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.
A cache of @llvm.assume calls within a function.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
static Loop * getInnerMostLoop(Loop *L)
if(llvm_vc STREQUAL "") set(fake_version_inc "$
StringRef getName() const
Return a constant reference to the value's name.
bool isSafeToUnrollAndJam(Loop *L, ScalarEvolution &SE, DominatorTree &DT, DependenceInfo &DI, LoopInfo &LI)
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...
bool anyBlockMayThrow() const override
Returns true iff any block of the loop for which this info is contains an instruction that may throw ...
DomTreeNodeBase< NodeT > * addNewBlock(NodeT *BB, NodeT *DomBB)
Add a new node to the dominator tree information.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
void forgetLoop(const Loop *L)
This method should be called by the client when it has changed a loop in a way that may effect Scalar...
static bool checkDependency(Instruction *Src, Instruction *Dst, unsigned UnrollLevel, unsigned JamLevel, bool Sequentialized, DependenceInfo &DI)
BlockT * getHeader() const
bool isRecursivelyLCSSAForm(const DominatorTree &DT, const LoopInfo &LI) const
Return true if this Loop and all inner subloops are in LCSSA form.
SmallPtrSet< BasicBlock *, 4 > BasicBlockSet
static bool isEligibleLoopForm(const Loop &Root)
static void moveHeaderPhiOperandsToForeBlocks(BasicBlock *Header, BasicBlock *Latch, Instruction *InsertLoc, BasicBlockSet &AftBlocks)
const Instruction & back() const
std::unique_ptr< Dependence > depends(Instruction *Src, Instruction *Dst, bool PossiblyLoopIndependent)
depends - Tests for a dependence between the Src and Dst instructions.
bool MergeBlockSuccessorsIntoGivenBlocks(SmallPtrSetImpl< BasicBlock * > &MergeBlocks, Loop *L=nullptr, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr)
Merge block(s) sucessors, if possible.
const BasicBlock * getParent() const
bool verify(VerificationLevel VL=VerificationLevel::Full) const
verify - checks if the tree is correct.
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
bool isRotatedForm() const
Return true if the loop is in rotated form.
Conditional or Unconditional Branch instruction.
@ Unmodified
The loop was not modified.
void applyUpdatesPermissive(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
LLVM Value Representation.
BasicBlock * getSuccessor(unsigned i) const
void moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
reference emplace_back(ArgTypes &&... Args)
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.