1 //===- LoopNestAnalysis.cpp - Loop Nest Analysis --------------------------==//
10 /// The implementation for the loop nest analysis.
28 ///  - the inner loop should be the outer loop's only child
29 ///  - the outer loop header should 'flow' into the inner loop preheader
30 ///    or jump around the inner loop to the outer loop latch
31 ///  - if the inner loop latch exits the inner loop, it should 'flow' into
32 ///    the outer loop latch.
33 /// Returns true if the loop structure satisfies the basic requirements and
35 static bool checkLoopsStructure(const Loop &OuterLoop, const Loop &InnerLoop,
42 LoopNest::LoopNest(Loop &Root, ScalarEvolution &SE)  in LoopNest()
47 std::unique_ptr<LoopNest> LoopNest::getLoopNest(Loop &Root,  in getLoopNest()
52 static CmpInst *getOuterLoopLatchCmp(const Loop &OuterLoop) {  in getOuterLoopLatchCmp()
55   assert(Latch && "Expecting a valid loop latch");  in getOuterLoopLatchCmp()
59          "Expecting loop latch terminator to be a branch instruction");  in getOuterLoopLatchCmp()
64         dbgs() << "Outer loop latch compare instruction: " << *OuterLoopLatchCmp  in getOuterLoopLatchCmp()
70 static CmpInst *getInnerLoopGuardCmp(const Loop &InnerLoop) {  in getInnerLoopGuardCmp()
78         dbgs() << "Inner loop guard compare instruction: " << *InnerLoopGuardCmp  in getInnerLoopGuardCmp()
87                                  std::optional<Loop::LoopBounds> OuterLoopLB) {  in checkSafeInstruction()
93   // The only binary instruction allowed is the outer loop step instruction,  in checkSafeInstruction()
94   // the only comparison instructions allowed are the inner loop guard  in checkSafeInstruction()
95   // compare instruction and the outer loop latch compare instruction.  in checkSafeInstruction()
103 bool LoopNest::arePerfectlyNested(const Loop &OuterLoop, const Loop &InnerLoop,  in arePerfectlyNested()
110     const Loop &OuterLoop, const Loop &InnerLoop, ScalarEvolution &SE) {  in analyzeLoopNestForPerfectNest()
112   assert(!OuterLoop.isInnermost() && "Outer loop should have subloops");  in analyzeLoopNestForPerfectNest()
113   assert(!InnerLoop.isOutermost() && "Inner loop should have a parent");  in analyzeLoopNestForPerfectNest()
114   LLVM_DEBUG(dbgs() << "Checking whether loop '" << OuterLoop.getName()  in analyzeLoopNestForPerfectNest()
119   //  - the inner loop should be the outer loop's only child  in analyzeLoopNestForPerfectNest()
120   //  - the outer loop header should 'flow' into the inner loop preheader  in analyzeLoopNestForPerfectNest()
121   //    or jump around the inner loop to the outer loop latch  in analyzeLoopNestForPerfectNest()
122   //  - if the inner loop latch exits the inner loop, it should 'flow' into  in analyzeLoopNestForPerfectNest()
123   //    the outer loop latch.  in analyzeLoopNestForPerfectNest()
125     LLVM_DEBUG(dbgs() << "Not perfectly nested: invalid loop structure.\n");  in analyzeLoopNestForPerfectNest()
129   // Bail out if we cannot retrieve the outer loop bounds.  in analyzeLoopNestForPerfectNest()
132     LLVM_DEBUG(dbgs() << "Cannot compute loop bounds of OuterLoop: "  in analyzeLoopNestForPerfectNest()
141   //  - the inner loop guard comparison  in analyzeLoopNestForPerfectNest()
142   //  - the outer loop latch comparison  in analyzeLoopNestForPerfectNest()
143   //  - the outer loop induction variable increment  in analyzeLoopNestForPerfectNest()
159   // Check the code surrounding the inner loop for instructions that are deemed  in analyzeLoopNestForPerfectNest()
170     LLVM_DEBUG(dbgs() << "Not perfectly nested: code surrounding inner loop is "  in analyzeLoopNestForPerfectNest()
175   LLVM_DEBUG(dbgs() << "Loop '" << OuterLoop.getName() << "' and '"  in analyzeLoopNestForPerfectNest()
182     const Loop &OuterLoop, const Loop &InnerLoop, ScalarEvolution &SE) {  in getInterveningInstructions()
186     LLVM_DEBUG(dbgs() << "The loop Nest is Perfect, returning empty "  in getInterveningInstructions()
191     LLVM_DEBUG(dbgs() << "Not perfectly nested: invalid loop structure. "  in getInterveningInstructions()
196     LLVM_DEBUG(dbgs() << "Cannot compute loop bounds of OuterLoop: "  in getInterveningInstructions()
204   // Identify the outer loop latch comparison instruction.  in getInterveningInstructions()
223   // Check the code surrounding the inner loop for instructions that are deemed  in getInterveningInstructions()
245   for (Loop *L : depth_first(const_cast<Loop *>(Loops.front()))) {  in getPerfectLoops()
261 unsigned LoopNest::getMaxPerfectDepth(const Loop &Root, ScalarEvolution &SE) {  in getMaxPerfectDepth()
262   LLVM_DEBUG(dbgs() << "Get maximum perfect depth of loop nest rooted by loop '"  in getMaxPerfectDepth()
265   const Loop *CurrentLoop = &Root;  in getMaxPerfectDepth()
270     const Loop *InnerLoop = SubLoops->front();  in getMaxPerfectDepth()
273         dbgs() << "Not a perfect nest: loop '" << CurrentLoop->getName()  in getMaxPerfectDepth()
274                << "' is not perfectly nested with loop '"  in getMaxPerfectDepth()
301   // Visited is used to avoid running into an infinite loop.  in skipEmptyBlockUntil()
315 static bool checkLoopsStructure(const Loop &OuterLoop, const Loop &InnerLoop,  in checkLoopsStructure()
317   // The inner loop must be the only outer loop's child.  in checkLoopsStructure()
332   // We expect rotated loops. The inner loop should have a single exit block.  in checkLoopsStructure()
346   // "guarded" inner loop which contains "only" Phi nodes corresponding to the  in checkLoopsStructure()
359   // Ensure the only branch that may exist between the loops is the inner loop  in checkLoopsStructure()
374       // The successors of the inner loop guard should be the inner loop  in checkLoopsStructure()
375       // preheader or the outer loop latch possibly through empty blocks.  in checkLoopsStructure()
380         // Ensure the inner loop guard successor is empty before skipping  in checkLoopsStructure()
401           // final check. We can also conclude that the inner loop is  in checkLoopsStructure()
409           dbgs() << "Inner loop guard successor " << Succ->getName()  in checkLoopsStructure()
410                  << " doesn't lead to inner loop preheader or "  in checkLoopsStructure()
411                     "outer loop latch.\n";  in checkLoopsStructure()
418   // Ensure the inner loop exit block lead to the outer loop latch possibly  in checkLoopsStructure()
427         dbgs() << "Inner loop exit block " << *InnerLoopExit  in checkLoopsStructure()
428                << " does not directly lead to the outer loop latch.\n";);  in checkLoopsStructure()
446   for (const Loop *L : LN.getLoops())  in operator <<()
457 PreservedAnalyses LoopNestPrinterPass::run(Loop &L, LoopAnalysisManager &AM,  in run()