Go to the documentation of this file.
21 #define DEBUG_TYPE "loopnest"
43 : MaxPerfectDepth(getMaxPerfectDepth(Root, SE)) {
49 return std::make_unique<LoopNest>(Root, SE);
55 assert(Latch &&
"Expecting a valid loop latch");
59 "Expecting loop latch terminator to be a branch instruction");
64 dbgs() <<
"Outer loop latch compare instruction: " << *OuterLoopLatchCmp
67 return OuterLoopLatchCmp;
74 (InnerGuard) ? dyn_cast<CmpInst>(InnerGuard->
getCondition()) :
nullptr;
78 dbgs() <<
"Inner loop guard compare instruction: " << *InnerLoopGuardCmp
81 return InnerLoopGuardCmp;
85 const CmpInst *InnerLoopGuardCmp,
86 const CmpInst *OuterLoopLatchCmp,
96 if ((isa<BinaryOperator>(
I) && &
I != &OuterLoopLB->
getStepInst()) ||
97 (isa<CmpInst>(
I) && &
I != OuterLoopLatchCmp && &
I != InnerLoopGuardCmp)) {
105 return (analyzeLoopNestForPerfectNest(OuterLoop, InnerLoop, SE) ==
109 LoopNest::LoopNestEnum LoopNest::analyzeLoopNestForPerfectNest(
115 <<
"' and '" << InnerLoop.
getName()
116 <<
"' are perfectly nested.\n");
125 LLVM_DEBUG(
dbgs() <<
"Not perfectly nested: invalid loop structure.\n");
126 return InvalidLoopStructure;
130 auto OuterLoopLB = OuterLoop.
getBounds(SE);
131 if (OuterLoopLB ==
None) {
133 << OuterLoop <<
"\n";);
134 return OuterLoopLowerBoundUnknown;
145 auto containsOnlySafeInstructions = [&](
const BasicBlock &
BB) {
148 OuterLoopLatchCmp, OuterLoopLB);
151 dbgs() <<
"Instruction: " <<
I <<
"\nin basic block:" <<
BB
165 if (!containsOnlySafeInstructions(*OuterLoopHeader) ||
166 !containsOnlySafeInstructions(*OuterLoopLatch) ||
167 (InnerLoopPreHeader != OuterLoopHeader &&
168 !containsOnlySafeInstructions(*InnerLoopPreHeader)) ||
169 !containsOnlySafeInstructions(*InnerLoop.
getExitBlock())) {
170 LLVM_DEBUG(
dbgs() <<
"Not perfectly nested: code surrounding inner loop is "
172 return ImperfectLoopNest;
176 << InnerLoop.
getName() <<
"' are perfectly nested.\n");
178 return PerfectLoopNest;
184 switch (analyzeLoopNestForPerfectNest(OuterLoop, InnerLoop, SE)) {
185 case PerfectLoopNest:
187 "instruction vector. \n";);
190 case InvalidLoopStructure:
191 LLVM_DEBUG(
dbgs() <<
"Not perfectly nested: invalid loop structure. "
192 "Instruction vector is empty.\n";);
195 case OuterLoopLowerBoundUnknown:
197 << OuterLoop <<
"\nInstruction vector is empty.\n";);
200 case ImperfectLoopNest:
205 auto OuterLoopLB = OuterLoop.
getBounds(SE);
210 auto GetUnsafeInstructions = [&](
const BasicBlock &
BB) {
216 dbgs() <<
"Instruction: " <<
I <<
"\nin basic block:" <<
BB
230 GetUnsafeInstructions(*OuterLoopHeader);
231 GetUnsafeInstructions(*OuterLoopLatch);
232 GetUnsafeInstructions(*InnerLoopExitBlock);
234 if (InnerLoopPreHeader != OuterLoopHeader) {
235 GetUnsafeInstructions(*InnerLoopPreHeader);
246 if (PerfectNest.empty())
247 PerfectNest.push_back(L);
249 auto &SubLoops = L->getSubLoops();
251 PerfectNest.push_back(SubLoops.front());
253 LV.push_back(PerfectNest);
262 LLVM_DEBUG(
dbgs() <<
"Get maximum perfect depth of loop nest rooted by loop '"
265 const Loop *CurrentLoop = &Root;
266 const auto *SubLoops = &CurrentLoop->
getSubLoops();
267 unsigned CurrentDepth = 1;
269 while (SubLoops->size() == 1) {
270 const Loop *InnerLoop = SubLoops->front();
273 dbgs() <<
"Not a perfect nest: loop '" << CurrentLoop->
getName()
274 <<
"' is not perfectly nested with loop '"
275 << InnerLoop->
getName() <<
"'\n";
280 CurrentLoop = InnerLoop;
290 bool CheckUniquePred) {
292 assert(End &&
"Expecting valid End");
294 if (
From == End || !
From->getUniqueSuccessor())
298 return (
BB->getInstList().size() == 1);
305 while (
BB &&
BB != End && IsEmpty(
BB) && !Visited.
count(
BB) &&
306 (!CheckUniquePred ||
BB->getUniquePredecessor())) {
309 BB =
BB->getUniqueSuccessor();
312 return (
BB == End) ? *End : *PredBB;
338 auto ContainsLCSSAPhi = [](
const BasicBlock &ExitBlock) {
340 return PN.getNumIncomingValues() == 1;
349 return BB.getFirstNonPHI() ==
BB.getTerminator() &&
351 return all_of(PN.blocks(), [&](const BasicBlock *IncomingBlock) {
352 return IncomingBlock == InnerLoopExit ||
353 IncomingBlock == OuterLoopHeader;
361 if (OuterLoopHeader != InnerLoopPreHeader) {
366 if (&SingleSucc != InnerLoopPreHeader) {
372 bool InnerLoopExitContainsLCSSA = ContainsLCSSAPhi(*InnerLoopExit);
377 const BasicBlock *PotentialInnerPreHeader = Succ;
382 if (Succ->getInstList().size() == 1) {
383 PotentialInnerPreHeader =
385 PotentialOuterLatch =
389 if (PotentialInnerPreHeader == InnerLoopPreHeader)
391 if (PotentialOuterLatch == OuterLoopLatch)
398 if (InnerLoopExitContainsLCSSA && IsExtraPhiBlock(*Succ) &&
399 Succ->getSingleSuccessor() == OuterLoopLatch) {
404 ExtraPhiBlock = Succ;
409 dbgs() <<
"Inner loop guard successor " << Succ->getName()
410 <<
" doesn't lead to inner loop preheader or "
411 "outer loop latch.\n";
420 if ((!ExtraPhiBlock ||
422 ExtraPhiBlock) != ExtraPhiBlock) &&
424 OuterLoopLatch) != OuterLoopLatch)) {
427 dbgs() <<
"Inner loop exit block " << *InnerLoopExit
428 <<
" does not directly lead to the outer loop latch.\n";);
447 OS << L->getName() <<
" ";
A set of analyses that are preserved following a run of a transformation pass.
static const char * VerboseDebug
This is an optimization pass for GlobalISel generic memory operations.
iterator_range< succ_op_iterator > successors()
BlockT * getExitBlock() const
If getExitBlocks would return exactly one block, return that block.
bool isSafeToSpeculativelyExecute(const Value *V, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
Represents a single loop in the control flow graph.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
static bool arePerfectlyNested(const Loop &OuterLoop, const Loop &InnerLoop, ScalarEvolution &SE)
Return true if the given loops OuterLoop and InnerLoop are perfectly nested with respect to each othe...
The main scalar evolution driver.
BranchInst * getLoopGuardBranch() const
Return the loop guard branch, if it exists.
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
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.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
#define DEBUG_WITH_TYPE(TYPE, X)
DEBUG_WITH_TYPE macro - This macro should be used by passes to emit debug information.
static bool checkSafeInstruction(const Instruction &I, const CmpInst *InnerLoopGuardCmp, const CmpInst *OuterLoopLatchCmp, Optional< Loop::LoopBounds > OuterLoopLB)
iterator_range< bf_iterator< T > > breadth_first(const T &G)
This class implements an extremely fast bulk output stream that can only output to a stream.
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
BlockT * getExitingBlock() const
If getExitingBlocks would return exactly one block, return that block.
StringRef getName() const
static bool checkLoopsStructure(const Loop &OuterLoop, const Loop &InnerLoop, ScalarEvolution &SE)
Determine whether the loops structure violates basic requirements for perfect nesting:
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
Value * getCondition() const
This class is the base class for the comparison instructions.
bool isLoopSimplifyForm() const
Return true if the Loop is in the form that the LoopSimplify form transforms loops to,...
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
static const BasicBlock & skipEmptyBlockUntil(const BasicBlock *From, const BasicBlock *End, bool CheckUniquePred=false)
Recursivelly traverse all empty 'single successor' basic blocks of From (if there are any).
A special type used by analysis passes to provide an address that identifies that particular analysis...
static CmpInst * getOuterLoopLatchCmp(const Loop &OuterLoop)
static unsigned getMaxPerfectDepth(const Loop &Root, ScalarEvolution &SE)
Return the maximum nesting depth of the loop nest rooted by loop Root.
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Instruction & getStepInst() const
Get the instruction that updates the loop induction variable.
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Loop & getOutermostLoop() const
Return the outermost loop in the loop nest.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
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 isOutermost() const
Return true if the loop does not have a parent (natural) loop.
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Optional< LoopBounds > getBounds(ScalarEvolution &SE) const
Return the struct LoopBounds collected if all struct members are found, else None.
iterator_range< df_iterator< T > > depth_first(const T &G)
bool isInnermost() const
Return true if the loop does not contain any (natural) loops.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
BlockT * getHeader() const
ArrayRef< Loop * > getLoops() const
Get the loops in the nest.
unsigned getNestDepth() const
Return the loop nest depth (i.e.
static CmpInst * getInnerLoopGuardCmp(const Loop &InnerLoop)
static InstrVectorTy getInterveningInstructions(const Loop &OuterLoop, const Loop &InnerLoop, ScalarEvolution &SE)
Return a vector of instructions that prevent the LoopNest given by loops OuterLoop and InnerLoop from...
unsigned getMaxPerfectDepth() const
Return the maximum perfect nesting depth.
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...
A container for analyses that lazily runs them and caches their results.
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
BlockVerifier::State From
Conditional or Unconditional Branch instruction.
static std::unique_ptr< LoopNest > getLoopNest(Loop &Root, ScalarEvolution &SE)
Construct a LoopNest object.
This class represents a loop nest and can be used to query its properties.
bool isConditional() const
SmallVector< LoopVectorTy, 4 > getPerfectLoops(ScalarEvolution &SE) const
Retrieve a vector of perfect loop nests contained in the current loop nest.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.