1 //===- LoopNestAnalysis.cpp - Loop Nest Analysis --------------------------==//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 ///
9 /// \file
10 /// The implementation for the loop nest analysis.
11 ///
12 //===----------------------------------------------------------------------===//
13 
14 #include "llvm/Analysis/LoopNestAnalysis.h"
15 #include "llvm/ADT/BreadthFirstIterator.h"
16 #include "llvm/ADT/Statistic.h"
17 #include "llvm/Analysis/PostDominators.h"
18 #include "llvm/Analysis/ValueTracking.h"
19 
20 using namespace llvm;
21 
22 #define DEBUG_TYPE "loopnest"
23 #ifndef NDEBUG
24 static const char *VerboseDebug = DEBUG_TYPE "-verbose";
25 #endif
26 
27 /// Determine whether the loops structure violates basic requirements for
28 /// perfect nesting:
29 ///  - the inner loop should be the outer loop's only child
30 ///  - the outer loop header should 'flow' into the inner loop preheader
31 ///    or jump around the inner loop to the outer loop latch
32 ///  - if the inner loop latch exits the inner loop, it should 'flow' into
33 ///    the outer loop latch.
34 /// Returns true if the loop structure satisfies the basic requirements and
35 /// false otherwise.
36 static bool checkLoopsStructure(const Loop &OuterLoop, const Loop &InnerLoop,
37                                 ScalarEvolution &SE);
38 
39 //===----------------------------------------------------------------------===//
40 // LoopNest implementation
41 //
42 
LoopNest(Loop & Root,ScalarEvolution & SE)43 LoopNest::LoopNest(Loop &Root, ScalarEvolution &SE)
44     : MaxPerfectDepth(getMaxPerfectDepth(Root, SE)) {
45   append_range(Loops, breadth_first(&Root));
46 }
47 
getLoopNest(Loop & Root,ScalarEvolution & SE)48 std::unique_ptr<LoopNest> LoopNest::getLoopNest(Loop &Root,
49                                                 ScalarEvolution &SE) {
50   return std::make_unique<LoopNest>(Root, SE);
51 }
52 
getOuterLoopLatchCmp(const Loop & OuterLoop)53 static CmpInst *getOuterLoopLatchCmp(const Loop &OuterLoop) {
54 
55   const BasicBlock *Latch = OuterLoop.getLoopLatch();
56   assert(Latch && "Expecting a valid loop latch");
57 
58   const BranchInst *BI = dyn_cast<BranchInst>(Latch->getTerminator());
59   assert(BI && BI->isConditional() &&
60          "Expecting loop latch terminator to be a branch instruction");
61 
62   CmpInst *OuterLoopLatchCmp = dyn_cast<CmpInst>(BI->getCondition());
63   DEBUG_WITH_TYPE(
64       VerboseDebug, if (OuterLoopLatchCmp) {
65         dbgs() << "Outer loop latch compare instruction: " << *OuterLoopLatchCmp
66                << "\n";
67       });
68   return OuterLoopLatchCmp;
69 }
70 
getInnerLoopGuardCmp(const Loop & InnerLoop)71 static CmpInst *getInnerLoopGuardCmp(const Loop &InnerLoop) {
72 
73   BranchInst *InnerGuard = InnerLoop.getLoopGuardBranch();
74   CmpInst *InnerLoopGuardCmp =
75       (InnerGuard) ? dyn_cast<CmpInst>(InnerGuard->getCondition()) : nullptr;
76 
77   DEBUG_WITH_TYPE(
78       VerboseDebug, if (InnerLoopGuardCmp) {
79         dbgs() << "Inner loop guard compare instruction: " << *InnerLoopGuardCmp
80                << "\n";
81       });
82   return InnerLoopGuardCmp;
83 }
84 
checkSafeInstruction(const Instruction & I,const CmpInst * InnerLoopGuardCmp,const CmpInst * OuterLoopLatchCmp,Optional<Loop::LoopBounds> OuterLoopLB)85 static bool checkSafeInstruction(const Instruction &I,
86                                  const CmpInst *InnerLoopGuardCmp,
87                                  const CmpInst *OuterLoopLatchCmp,
88                                  Optional<Loop::LoopBounds> OuterLoopLB) {
89 
90   bool IsAllowed =
91       isSafeToSpeculativelyExecute(&I) || isa<PHINode>(I) || isa<BranchInst>(I);
92   if (!IsAllowed)
93     return false;
94   // The only binary instruction allowed is the outer loop step instruction,
95   // the only comparison instructions allowed are the inner loop guard
96   // compare instruction and the outer loop latch compare instruction.
97   if ((isa<BinaryOperator>(I) && &I != &OuterLoopLB->getStepInst()) ||
98       (isa<CmpInst>(I) && &I != OuterLoopLatchCmp && &I != InnerLoopGuardCmp)) {
99     return false;
100   }
101   return true;
102 }
103 
arePerfectlyNested(const Loop & OuterLoop,const Loop & InnerLoop,ScalarEvolution & SE)104 bool LoopNest::arePerfectlyNested(const Loop &OuterLoop, const Loop &InnerLoop,
105                                   ScalarEvolution &SE) {
106   return (analyzeLoopNestForPerfectNest(OuterLoop, InnerLoop, SE) ==
107           PerfectLoopNest);
108 }
109 
analyzeLoopNestForPerfectNest(const Loop & OuterLoop,const Loop & InnerLoop,ScalarEvolution & SE)110 LoopNest::LoopNestEnum LoopNest::analyzeLoopNestForPerfectNest(
111     const Loop &OuterLoop, const Loop &InnerLoop, ScalarEvolution &SE) {
112 
113   assert(!OuterLoop.isInnermost() && "Outer loop should have subloops");
114   assert(!InnerLoop.isOutermost() && "Inner loop should have a parent");
115   LLVM_DEBUG(dbgs() << "Checking whether loop '" << OuterLoop.getName()
116                     << "' and '" << InnerLoop.getName()
117                     << "' are perfectly nested.\n");
118 
119   // Determine whether the loops structure satisfies the following requirements:
120   //  - the inner loop should be the outer loop's only child
121   //  - the outer loop header should 'flow' into the inner loop preheader
122   //    or jump around the inner loop to the outer loop latch
123   //  - if the inner loop latch exits the inner loop, it should 'flow' into
124   //    the outer loop latch.
125   if (!checkLoopsStructure(OuterLoop, InnerLoop, SE)) {
126     LLVM_DEBUG(dbgs() << "Not perfectly nested: invalid loop structure.\n");
127     return InvalidLoopStructure;
128   }
129 
130   // Bail out if we cannot retrieve the outer loop bounds.
131   auto OuterLoopLB = OuterLoop.getBounds(SE);
132   if (OuterLoopLB == None) {
133     LLVM_DEBUG(dbgs() << "Cannot compute loop bounds of OuterLoop: "
134                       << OuterLoop << "\n";);
135     return OuterLoopLowerBoundUnknown;
136   }
137 
138   CmpInst *OuterLoopLatchCmp = getOuterLoopLatchCmp(OuterLoop);
139   CmpInst *InnerLoopGuardCmp = getInnerLoopGuardCmp(InnerLoop);
140 
141   // Determine whether instructions in a basic block are one of:
142   //  - the inner loop guard comparison
143   //  - the outer loop latch comparison
144   //  - the outer loop induction variable increment
145   //  - a phi node, a cast or a branch
146   auto containsOnlySafeInstructions = [&](const BasicBlock &BB) {
147     return llvm::all_of(BB, [&](const Instruction &I) {
148       bool IsSafeInstr = checkSafeInstruction(I, InnerLoopGuardCmp,
149                                               OuterLoopLatchCmp, OuterLoopLB);
150       if (IsSafeInstr) {
151         DEBUG_WITH_TYPE(VerboseDebug, {
152           dbgs() << "Instruction: " << I << "\nin basic block:" << BB
153                  << "is unsafe.\n";
154         });
155       }
156       return IsSafeInstr;
157     });
158   };
159 
160   // Check the code surrounding the inner loop for instructions that are deemed
161   // unsafe.
162   const BasicBlock *OuterLoopHeader = OuterLoop.getHeader();
163   const BasicBlock *OuterLoopLatch = OuterLoop.getLoopLatch();
164   const BasicBlock *InnerLoopPreHeader = InnerLoop.getLoopPreheader();
165 
166   if (!containsOnlySafeInstructions(*OuterLoopHeader) ||
167       !containsOnlySafeInstructions(*OuterLoopLatch) ||
168       (InnerLoopPreHeader != OuterLoopHeader &&
169        !containsOnlySafeInstructions(*InnerLoopPreHeader)) ||
170       !containsOnlySafeInstructions(*InnerLoop.getExitBlock())) {
171     LLVM_DEBUG(dbgs() << "Not perfectly nested: code surrounding inner loop is "
172                          "unsafe\n";);
173     return ImperfectLoopNest;
174   }
175 
176   LLVM_DEBUG(dbgs() << "Loop '" << OuterLoop.getName() << "' and '"
177                     << InnerLoop.getName() << "' are perfectly nested.\n");
178 
179   return PerfectLoopNest;
180 }
181 
getInterveningInstructions(const Loop & OuterLoop,const Loop & InnerLoop,ScalarEvolution & SE)182 LoopNest::InstrVectorTy LoopNest::getInterveningInstructions(
183     const Loop &OuterLoop, const Loop &InnerLoop, ScalarEvolution &SE) {
184   InstrVectorTy Instr;
185   switch (analyzeLoopNestForPerfectNest(OuterLoop, InnerLoop, SE)) {
186   case PerfectLoopNest:
187     LLVM_DEBUG(dbgs() << "The loop Nest is Perfect, returning empty "
188                          "instruction vector. \n";);
189     return Instr;
190 
191   case InvalidLoopStructure:
192     LLVM_DEBUG(dbgs() << "Not perfectly nested: invalid loop structure. "
193                          "Instruction vector is empty.\n";);
194     return Instr;
195 
196   case OuterLoopLowerBoundUnknown:
197     LLVM_DEBUG(dbgs() << "Cannot compute loop bounds of OuterLoop: "
198                       << OuterLoop << "\nInstruction vector is empty.\n";);
199     return Instr;
200 
201   case ImperfectLoopNest:
202     break;
203   }
204 
205   // Identify the outer loop latch comparison instruction.
206   auto OuterLoopLB = OuterLoop.getBounds(SE);
207 
208   CmpInst *OuterLoopLatchCmp = getOuterLoopLatchCmp(OuterLoop);
209   CmpInst *InnerLoopGuardCmp = getInnerLoopGuardCmp(InnerLoop);
210 
211   auto GetUnsafeInstructions = [&](const BasicBlock &BB) {
212     for (const Instruction &I : BB) {
213       if (!checkSafeInstruction(I, InnerLoopGuardCmp, OuterLoopLatchCmp,
214                                 OuterLoopLB)) {
215         Instr.push_back(&I);
216         DEBUG_WITH_TYPE(VerboseDebug, {
217           dbgs() << "Instruction: " << I << "\nin basic block:" << BB
218                  << "is unsafe.\n";
219         });
220       }
221     }
222   };
223 
224   // Check the code surrounding the inner loop for instructions that are deemed
225   // unsafe.
226   const BasicBlock *OuterLoopHeader = OuterLoop.getHeader();
227   const BasicBlock *OuterLoopLatch = OuterLoop.getLoopLatch();
228   const BasicBlock *InnerLoopPreHeader = InnerLoop.getLoopPreheader();
229   const BasicBlock *InnerLoopExitBlock = InnerLoop.getExitBlock();
230 
231   GetUnsafeInstructions(*OuterLoopHeader);
232   GetUnsafeInstructions(*OuterLoopLatch);
233   GetUnsafeInstructions(*InnerLoopExitBlock);
234 
235   if (InnerLoopPreHeader != OuterLoopHeader) {
236     GetUnsafeInstructions(*InnerLoopPreHeader);
237   }
238   return Instr;
239 }
240 
241 SmallVector<LoopVectorTy, 4>
getPerfectLoops(ScalarEvolution & SE) const242 LoopNest::getPerfectLoops(ScalarEvolution &SE) const {
243   SmallVector<LoopVectorTy, 4> LV;
244   LoopVectorTy PerfectNest;
245 
246   for (Loop *L : depth_first(const_cast<Loop *>(Loops.front()))) {
247     if (PerfectNest.empty())
248       PerfectNest.push_back(L);
249 
250     auto &SubLoops = L->getSubLoops();
251     if (SubLoops.size() == 1 && arePerfectlyNested(*L, *SubLoops.front(), SE)) {
252       PerfectNest.push_back(SubLoops.front());
253     } else {
254       LV.push_back(PerfectNest);
255       PerfectNest.clear();
256     }
257   }
258 
259   return LV;
260 }
261 
getMaxPerfectDepth(const Loop & Root,ScalarEvolution & SE)262 unsigned LoopNest::getMaxPerfectDepth(const Loop &Root, ScalarEvolution &SE) {
263   LLVM_DEBUG(dbgs() << "Get maximum perfect depth of loop nest rooted by loop '"
264                     << Root.getName() << "'\n");
265 
266   const Loop *CurrentLoop = &Root;
267   const auto *SubLoops = &CurrentLoop->getSubLoops();
268   unsigned CurrentDepth = 1;
269 
270   while (SubLoops->size() == 1) {
271     const Loop *InnerLoop = SubLoops->front();
272     if (!arePerfectlyNested(*CurrentLoop, *InnerLoop, SE)) {
273       LLVM_DEBUG({
274         dbgs() << "Not a perfect nest: loop '" << CurrentLoop->getName()
275                << "' is not perfectly nested with loop '"
276                << InnerLoop->getName() << "'\n";
277       });
278       break;
279     }
280 
281     CurrentLoop = InnerLoop;
282     SubLoops = &CurrentLoop->getSubLoops();
283     ++CurrentDepth;
284   }
285 
286   return CurrentDepth;
287 }
288 
skipEmptyBlockUntil(const BasicBlock * From,const BasicBlock * End,bool CheckUniquePred)289 const BasicBlock &LoopNest::skipEmptyBlockUntil(const BasicBlock *From,
290                                                 const BasicBlock *End,
291                                                 bool CheckUniquePred) {
292   assert(From && "Expecting valid From");
293   assert(End && "Expecting valid End");
294 
295   if (From == End || !From->getUniqueSuccessor())
296     return *From;
297 
298   auto IsEmpty = [](const BasicBlock *BB) {
299     return (BB->getInstList().size() == 1);
300   };
301 
302   // Visited is used to avoid running into an infinite loop.
303   SmallPtrSet<const BasicBlock *, 4> Visited;
304   const BasicBlock *BB = From->getUniqueSuccessor();
305   const BasicBlock *PredBB = From;
306   while (BB && BB != End && IsEmpty(BB) && !Visited.count(BB) &&
307          (!CheckUniquePred || BB->getUniquePredecessor())) {
308     Visited.insert(BB);
309     PredBB = BB;
310     BB = BB->getUniqueSuccessor();
311   }
312 
313   return (BB == End) ? *End : *PredBB;
314 }
315 
checkLoopsStructure(const Loop & OuterLoop,const Loop & InnerLoop,ScalarEvolution & SE)316 static bool checkLoopsStructure(const Loop &OuterLoop, const Loop &InnerLoop,
317                                 ScalarEvolution &SE) {
318   // The inner loop must be the only outer loop's child.
319   if ((OuterLoop.getSubLoops().size() != 1) ||
320       (InnerLoop.getParentLoop() != &OuterLoop))
321     return false;
322 
323   // We expect loops in normal form which have a preheader, header, latch...
324   if (!OuterLoop.isLoopSimplifyForm() || !InnerLoop.isLoopSimplifyForm())
325     return false;
326 
327   const BasicBlock *OuterLoopHeader = OuterLoop.getHeader();
328   const BasicBlock *OuterLoopLatch = OuterLoop.getLoopLatch();
329   const BasicBlock *InnerLoopPreHeader = InnerLoop.getLoopPreheader();
330   const BasicBlock *InnerLoopLatch = InnerLoop.getLoopLatch();
331   const BasicBlock *InnerLoopExit = InnerLoop.getExitBlock();
332 
333   // We expect rotated loops. The inner loop should have a single exit block.
334   if (OuterLoop.getExitingBlock() != OuterLoopLatch ||
335       InnerLoop.getExitingBlock() != InnerLoopLatch || !InnerLoopExit)
336     return false;
337 
338   // Returns whether the block `ExitBlock` contains at least one LCSSA Phi node.
339   auto ContainsLCSSAPhi = [](const BasicBlock &ExitBlock) {
340     return any_of(ExitBlock.phis(), [](const PHINode &PN) {
341       return PN.getNumIncomingValues() == 1;
342     });
343   };
344 
345   // Returns whether the block `BB` qualifies for being an extra Phi block. The
346   // extra Phi block is the additional block inserted after the exit block of an
347   // "guarded" inner loop which contains "only" Phi nodes corresponding to the
348   // LCSSA Phi nodes in the exit block.
349   auto IsExtraPhiBlock = [&](const BasicBlock &BB) {
350     return BB.getFirstNonPHI() == BB.getTerminator() &&
351            all_of(BB.phis(), [&](const PHINode &PN) {
352              return all_of(PN.blocks(), [&](const BasicBlock *IncomingBlock) {
353                return IncomingBlock == InnerLoopExit ||
354                       IncomingBlock == OuterLoopHeader;
355              });
356            });
357   };
358 
359   const BasicBlock *ExtraPhiBlock = nullptr;
360   // Ensure the only branch that may exist between the loops is the inner loop
361   // guard.
362   if (OuterLoopHeader != InnerLoopPreHeader) {
363     const BasicBlock &SingleSucc =
364         LoopNest::skipEmptyBlockUntil(OuterLoopHeader, InnerLoopPreHeader);
365 
366     // no conditional branch present
367     if (&SingleSucc != InnerLoopPreHeader) {
368       const BranchInst *BI = dyn_cast<BranchInst>(SingleSucc.getTerminator());
369 
370       if (!BI || BI != InnerLoop.getLoopGuardBranch())
371         return false;
372 
373       bool InnerLoopExitContainsLCSSA = ContainsLCSSAPhi(*InnerLoopExit);
374 
375       // The successors of the inner loop guard should be the inner loop
376       // preheader or the outer loop latch possibly through empty blocks.
377       for (const BasicBlock *Succ : BI->successors()) {
378         const BasicBlock *PotentialInnerPreHeader = Succ;
379         const BasicBlock *PotentialOuterLatch = Succ;
380 
381         // Ensure the inner loop guard successor is empty before skipping
382         // blocks.
383         if (Succ->getInstList().size() == 1) {
384           PotentialInnerPreHeader =
385               &LoopNest::skipEmptyBlockUntil(Succ, InnerLoopPreHeader);
386           PotentialOuterLatch =
387               &LoopNest::skipEmptyBlockUntil(Succ, OuterLoopLatch);
388         }
389 
390         if (PotentialInnerPreHeader == InnerLoopPreHeader)
391           continue;
392         if (PotentialOuterLatch == OuterLoopLatch)
393           continue;
394 
395         // If `InnerLoopExit` contains LCSSA Phi instructions, additional block
396         // may be inserted before the `OuterLoopLatch` to which `BI` jumps. The
397         // loops are still considered perfectly nested if the extra block only
398         // contains Phi instructions from InnerLoopExit and OuterLoopHeader.
399         if (InnerLoopExitContainsLCSSA && IsExtraPhiBlock(*Succ) &&
400             Succ->getSingleSuccessor() == OuterLoopLatch) {
401           // Points to the extra block so that we can reference it later in the
402           // final check. We can also conclude that the inner loop is
403           // guarded and there exists LCSSA Phi node in the exit block later if
404           // we see a non-null `ExtraPhiBlock`.
405           ExtraPhiBlock = Succ;
406           continue;
407         }
408 
409         DEBUG_WITH_TYPE(VerboseDebug, {
410           dbgs() << "Inner loop guard successor " << Succ->getName()
411                  << " doesn't lead to inner loop preheader or "
412                     "outer loop latch.\n";
413         });
414         return false;
415       }
416     }
417   }
418 
419   // Ensure the inner loop exit block lead to the outer loop latch possibly
420   // through empty blocks.
421   if ((!ExtraPhiBlock ||
422        &LoopNest::skipEmptyBlockUntil(InnerLoop.getExitBlock(),
423                                       ExtraPhiBlock) != ExtraPhiBlock) &&
424       (&LoopNest::skipEmptyBlockUntil(InnerLoop.getExitBlock(),
425                                       OuterLoopLatch) != OuterLoopLatch)) {
426     DEBUG_WITH_TYPE(
427         VerboseDebug,
428         dbgs() << "Inner loop exit block " << *InnerLoopExit
429                << " does not directly lead to the outer loop latch.\n";);
430     return false;
431   }
432 
433   return true;
434 }
435 
436 AnalysisKey LoopNestAnalysis::Key;
437 
operator <<(raw_ostream & OS,const LoopNest & LN)438 raw_ostream &llvm::operator<<(raw_ostream &OS, const LoopNest &LN) {
439   OS << "IsPerfect=";
440   if (LN.getMaxPerfectDepth() == LN.getNestDepth())
441     OS << "true";
442   else
443     OS << "false";
444   OS << ", Depth=" << LN.getNestDepth();
445   OS << ", OutermostLoop: " << LN.getOutermostLoop().getName();
446   OS << ", Loops: ( ";
447   for (const Loop *L : LN.getLoops())
448     OS << L->getName() << " ";
449   OS << ")";
450 
451   return OS;
452 }
453 
454 //===----------------------------------------------------------------------===//
455 // LoopNestPrinterPass implementation
456 //
457 
run(Loop & L,LoopAnalysisManager & AM,LoopStandardAnalysisResults & AR,LPMUpdater & U)458 PreservedAnalyses LoopNestPrinterPass::run(Loop &L, LoopAnalysisManager &AM,
459                                            LoopStandardAnalysisResults &AR,
460                                            LPMUpdater &U) {
461   if (auto LN = LoopNest::getLoopNest(L, AR.SE))
462     OS << *LN << "\n";
463 
464   return PreservedAnalyses::all();
465 }
466