Go to the documentation of this file.
57 #include <type_traits>
62 #define DEBUG_TYPE "loop-unroll-and-jam"
64 STATISTIC(NumUnrolledAndJammed,
"Number of loops unroll and jammed");
65 STATISTIC(NumCompletelyUnrolledAndJammed,
"Number of loops unroll and jammed");
89 if (
BB == SubLoopPreHeader)
93 if (!ForeBlocks.count(Succ))
138 template <
typename T>
143 for (
auto &Phi : Header->
phis()) {
144 Value *V = Phi.getIncomingValueForBlock(Latch);
146 Worklist.push_back(
I);
149 while (!Worklist.empty()) {
155 if (AftBlocks.
count(
I->getParent()))
156 for (
auto &U :
I->operands())
158 if (!VisitedInstr.
count(II))
159 Worklist.push_back(II);
172 std::vector<Instruction *> Visited;
175 if (AftBlocks.
count(
I->getParent()))
176 Visited.push_back(
I);
183 if (
I->getParent() != InsertLocBB)
184 I->moveBefore(InsertLoc);
224 unsigned TripMultiple,
bool UnrollRemainder,
231 assert(Header &&
"No header.");
236 if (TripCount == 0 && Count < 2) {
237 LLVM_DEBUG(
dbgs() <<
"Won't unroll-and-jam; almost nothing to do\n");
243 assert(TripCount == 0 || TripCount % TripMultiple == 0);
246 bool CompletelyUnroll = (Count == TripCount);
249 if (TripMultiple % Count != 0) {
252 UnrollRemainder,
false,
253 LI, SE, DT, AC,
TTI,
true, EpilogueLoop)) {
254 LLVM_DEBUG(
dbgs() <<
"Won't unroll-and-jam; remainder loop could not be "
255 "generated when assuming runtime trip count\n");
269 if (CompletelyUnroll) {
271 << Header->
getName() <<
" with trip count " << TripCount
275 <<
"completely unroll and jammed loop with "
276 <<
NV(
"UnrollCount", TripCount) <<
" iterations");
278 auto DiagBuilder = [&]() {
281 return Diag <<
"unroll and jammed loop by a factor of "
282 <<
NV(
"UnrollCount", Count);
287 if (TripMultiple != 1) {
288 LLVM_DEBUG(
dbgs() <<
" with " << TripMultiple <<
" trips per branch");
290 return DiagBuilder() <<
" with " <<
NV(
"TripMultiple", TripMultiple)
291 <<
" trips per branch";
295 ORE->
emit([&]() {
return DiagBuilder() <<
" with run-time trip count"; });
302 assert(Preheader &&
"No preheader");
303 assert(LatchBlock &&
"No latch block");
308 bool SubLoopContinueOnTrue = SubLoop->
contains(
322 std::vector<BasicBlock *> ForeBlocksFirst;
323 std::vector<BasicBlock *> ForeBlocksLast;
324 std::vector<BasicBlock *> SubLoopBlocksFirst;
325 std::vector<BasicBlock *> SubLoopBlocksLast;
326 std::vector<BasicBlock *> AftBlocksFirst;
327 std::vector<BasicBlock *> AftBlocksLast;
328 ForeBlocksFirst.push_back(Header);
330 SubLoopBlocksFirst.push_back(SubLoop->
getHeader());
339 Header, LatchBlock, ForeBlocksLast[0]->getTerminator(), AftBlocks);
355 if (!isa<DbgInfoIntrinsic>(&
I))
357 auto NewDIL = DIL->cloneByMultiplyingDuplicationFactor(Count);
359 I.setDebugLoc(*NewDIL);
362 <<
"Failed to create new discriminator: "
363 << DIL->getFilename() <<
" Line: " << DIL->getLine());
367 for (
unsigned It = 1; It != Count; ++It) {
373 NewLoops[SubLoop] = SubLoop;
384 if (*
BB == ForeBlocksFirst[0])
385 ForeBlocksFirst.push_back(New);
386 if (*
BB == ForeBlocksLast[0])
387 ForeBlocksLast.push_back(New);
388 }
else if (SubLoopBlocks.
count(*
BB)) {
389 if (*
BB == SubLoopBlocksFirst[0])
390 SubLoopBlocksFirst.push_back(New);
391 if (*
BB == SubLoopBlocksLast[0])
392 SubLoopBlocksLast.push_back(New);
393 }
else if (AftBlocks.
count(*
BB)) {
394 if (*
BB == AftBlocksFirst[0])
395 AftBlocksFirst.push_back(New);
396 if (*
BB == AftBlocksLast[0])
397 AftBlocksLast.push_back(New);
403 PrevItValueMap[New] = (It == 1 ? *
BB : LastValueMap[*
BB]);
404 LastValueMap[*
BB] = New;
407 PrevItValueMap[
VI->second] =
408 const_cast<Value *
>(It == 1 ?
VI->first : LastValueMap[
VI->first]);
409 LastValueMap[
VI->first] =
VI->second;
412 NewBlocks.push_back(New);
415 if (*
BB == ForeBlocksFirst[0])
417 else if (*
BB == SubLoopBlocksFirst[0])
419 else if (*
BB == AftBlocksFirst[0])
425 auto BBIDom = BBDomNode->
getIDom();
426 BasicBlock *OriginalBBIDom = BBIDom->getBlock();
428 assert(LastValueMap[cast<Value>(OriginalBBIDom)]);
430 New, cast<BasicBlock>(LastValueMap[cast<Value>(OriginalBBIDom)]));
438 if (
auto *II = dyn_cast<AssumeInst>(&
I))
445 for (
PHINode &Phi : ForeBlocksFirst[It]->phis()) {
446 Value *OldValue = Phi.getIncomingValueForBlock(AftBlocksLast[It]);
447 assert(OldValue &&
"should have incoming edge from Aft[It]");
448 Value *NewValue = OldValue;
449 if (
Value *PrevValue = PrevItValueMap[OldValue])
450 NewValue = PrevValue;
452 assert(Phi.getNumOperands() == 2);
453 Phi.setIncomingBlock(0, ForeBlocksLast[It - 1]);
454 Phi.setIncomingValue(0, NewValue);
455 Phi.removeIncomingValue(1);
469 for (
unsigned b = 0;
b < Phi.getNumIncomingValues(); ++
b) {
470 if (Phi.getIncomingBlock(
b) == OldBB) {
471 Value *OldValue = Phi.getIncomingValue(
b);
472 if (
Value *LastValue = LastValueMap[OldValue])
473 Phi.setIncomingValue(
b, LastValue);
474 Phi.setIncomingBlock(
b, NewBB);
483 while (
PHINode *Phi = dyn_cast<PHINode>(Src->begin()))
488 updatePHIBlocksAndValues(LoopExit, AftBlocksLast[0], AftBlocksLast.
back(),
493 cast<BranchInst>(ForeBlocksLast.back()->getTerminator());
497 if (CompletelyUnroll) {
498 while (
PHINode *Phi = dyn_cast<PHINode>(ForeBlocksFirst[0]->
begin())) {
499 Phi->replaceAllUsesWith(Phi->getIncomingValueForBlock(Preheader));
500 Phi->getParent()->getInstList().erase(Phi);
504 updatePHIBlocksAndValues(ForeBlocksFirst[0], AftBlocksLast[0],
505 AftBlocksLast.back(), LastValueMap);
508 for (
unsigned It = 1; It != Count; It++) {
511 cast<BranchInst>(ForeBlocksLast[It - 1]->getTerminator());
518 cast<BranchInst>(SubLoopBlocksLast.back()->getTerminator());
519 SubTerm->
setSuccessor(!SubLoopContinueOnTrue, SubLoopBlocksFirst[0]);
520 SubTerm->
setSuccessor(SubLoopContinueOnTrue, AftBlocksFirst[0]);
521 SubLoopBlocksFirst[0]->replacePhiUsesWith(ForeBlocksLast[0],
522 ForeBlocksLast.back());
523 SubLoopBlocksFirst[0]->replacePhiUsesWith(SubLoopBlocksLast[0],
524 SubLoopBlocksLast.back());
526 for (
unsigned It = 1; It != Count; It++) {
530 cast<BranchInst>(SubLoopBlocksLast[It - 1]->getTerminator());
534 SubLoopBlocksFirst[It]->replacePhiUsesWith(ForeBlocksLast[It],
535 ForeBlocksLast.back());
536 SubLoopBlocksFirst[It]->replacePhiUsesWith(SubLoopBlocksLast[It],
537 SubLoopBlocksLast.back());
538 movePHIs(SubLoopBlocksFirst[It], SubLoopBlocksFirst[0]);
542 BranchInst *AftTerm = cast<BranchInst>(AftBlocksLast.back()->getTerminator());
543 if (CompletelyUnroll) {
547 AftTerm->
setSuccessor(!ContinueOnTrue, ForeBlocksFirst[0]);
549 "Expecting the ContinueOnTrue successor of AftTerm to be LoopExit");
551 AftBlocksFirst[0]->replacePhiUsesWith(SubLoopBlocksLast[0],
552 SubLoopBlocksLast.back());
554 for (
unsigned It = 1; It != Count; It++) {
558 cast<BranchInst>(AftBlocksLast[It - 1]->getTerminator());
562 AftBlocksFirst[It]->replacePhiUsesWith(SubLoopBlocksLast[It],
563 SubLoopBlocksLast.back());
564 movePHIs(AftBlocksFirst[It], AftBlocksFirst[0]);
573 SubLoopBlocksFirst[0]);
575 SubLoopBlocksLast[0], AftBlocksFirst[0]);
578 ForeBlocksLast.back(), SubLoopBlocksFirst[0]);
580 SubLoopBlocksLast.back(), AftBlocksFirst[0]);
586 MergeBlocks.
insert(ForeBlocksLast.begin(), ForeBlocksLast.end());
587 MergeBlocks.
insert(SubLoopBlocksLast.begin(), SubLoopBlocksLast.end());
588 MergeBlocks.
insert(AftBlocksLast.begin(), AftBlocksLast.end());
602 NumCompletelyUnrolledAndJammed += CompletelyUnroll;
603 ++NumUnrolledAndJammed;
606 if (CompletelyUnroll)
619 if (!CompletelyUnroll)
635 if (
auto *Ld = dyn_cast<LoadInst>(&
I)) {
638 MemInstr.push_back(&
I);
639 }
else if (
auto *St = dyn_cast<StoreInst>(&
I)) {
642 MemInstr.push_back(&
I);
643 }
else if (
I.mayReadOrWriteMemory()) {
652 unsigned UnrollLevel,
unsigned JamLevel,
656 for (
unsigned CurLoopDepth = UnrollLevel + 1; CurLoopDepth <= JamLevel;
658 auto JammedDir =
D->getDirection(CurLoopDepth);
670 unsigned UnrollLevel,
unsigned JamLevel,
673 for (
unsigned CurLoopDepth = UnrollLevel + 1; CurLoopDepth <= JamLevel;
675 auto JammedDir =
D->getDirection(CurLoopDepth);
684 return Sequentialized;
696 unsigned UnrollLevel,
unsigned JamLevel,
698 assert(UnrollLevel <= JamLevel &&
699 "Expecting JamLevel to be at least UnrollLevel");
704 if (isa<LoadInst>(Src) && isa<LoadInst>(Dst))
717 std::unique_ptr<Dependence>
D = DI.
depends(Src, Dst,
true);
720 assert(
D->isOrdered() &&
"Expected an output, flow or anti dep.");
722 if (
D->isConfused()) {
724 <<
" " << *Src <<
"\n"
725 <<
" " << *Dst <<
"\n");
733 for (
unsigned CurLoopDepth = 1; CurLoopDepth < UnrollLevel; ++CurLoopDepth)
737 auto UnrollDirection =
D->getDirection(UnrollLevel);
747 Sequentialized,
D.get()))
752 Sequentialized,
D.get()))
765 if (ForeBlocksMap.
find(L) != ForeBlocksMap.
end())
766 AllBlocks.push_back(ForeBlocksMap.
lookup(L));
767 AllBlocks.push_back(SubLoopBlocks);
769 if (AftBlocksMap.
find(L) != AftBlocksMap.
end())
770 AllBlocks.push_back(AftBlocksMap.
lookup(L));
776 CurrentLoadsAndStores.
clear();
780 Loop *CurLoop = LI.
getLoopFor((*Blocks.begin())->front().getParent());
783 for (
auto *Earlier : EarlierLoadsAndStores) {
786 unsigned CommonLoopDepth =
std::min(EarlierDepth, CurLoopDepth);
787 for (
auto *Later : CurrentLoadsAndStores) {
788 if (!
checkDependency(Earlier, Later, LoopDepth, CommonLoopDepth,
false,
794 size_t NumInsts = CurrentLoadsAndStores.size();
795 for (
size_t I = 0;
I < NumInsts; ++
I) {
796 for (
size_t J =
I; J < NumInsts; ++J) {
798 LoopDepth, CurLoopDepth,
true, DI))
803 EarlierLoadsAndStores.
append(CurrentLoadsAndStores.begin(),
804 CurrentLoadsAndStores.end());
814 const Loop *L = &Root;
829 if (SubLoopsSize == 0)
833 if (SubLoopsSize != 1)
841 LLVM_DEBUG(
dbgs() <<
"Won't unroll-and-jam; only loops with single exit "
842 "blocks can be unrolled and jammed.\n");
848 LLVM_DEBUG(
dbgs() <<
"Won't unroll-and-jam; only loops with single "
849 "exiting blocks can be unrolled and jammed.\n");
868 LLVM_DEBUG(
dbgs() <<
"Won't unroll-and-jam; Ineligible loop form\n");
930 LLVM_DEBUG(
dbgs() <<
"Won't unroll-and-jam; Incompatible loop layout\n");
937 if (AftBlocksMap[L].
size() != 1) {
938 LLVM_DEBUG(
dbgs() <<
"Won't unroll-and-jam; Can't currently handle "
939 "multiple blocks after the loop\n");
946 return !hasIterationCountInvariantInParent(SubLoop, SE);
948 LLVM_DEBUG(
dbgs() <<
"Won't unroll-and-jam; Inner loop iteration count is "
949 "not consistent on each iteration\n");
957 LLVM_DEBUG(
dbgs() <<
"Won't unroll-and-jam; Something may throw\n");
973 Header, Latch, AftBlocks, [&AftBlocks, &SubLoop](
Instruction *
I) {
976 if (AftBlocks.
count(
I->getParent())) {
983 if (I->mayHaveSideEffects() || I->mayReadOrWriteMemory())
990 "instructions after subloop to before it\n");
999 LLVM_DEBUG(
dbgs() <<
"Won't unroll-and-jam; failed dependency check\n");
This is an optimization pass for GlobalISel generic memory operations.
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 registerAssumption(AssumeInst *CI)
Add an @llvm.assume intrinsic to this function's cache.
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.
cl::opt< bool > EnableFSDiscriminator
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
auto successors(MachineBasicBlock *BB)
static bool partitionLoopBlocks(Loop &L, BasicBlockSet &ForeBlocks, BasicBlockSet &AftBlocks, DominatorTree &DT)
LLVM_NODISCARD T pop_back_val()
DomTreeNodeBase * getIDom() const
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)
RPOIterator beginRPO() const
Reverse iterate over the cached postorder blocks.
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.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
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.
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.
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")
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.
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.
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)
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.
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...
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.