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 
43 LoopNest::LoopNest(Loop &Root, ScalarEvolution &SE)
44     : MaxPerfectDepth(getMaxPerfectDepth(Root, SE)) {
45   for (Loop *L : breadth_first(&Root))
46     Loops.push_back(L);
47 }
48 
49 std::unique_ptr<LoopNest> LoopNest::getLoopNest(Loop &Root,
50                                                 ScalarEvolution &SE) {
51   return std::make_unique<LoopNest>(Root, SE);
52 }
53 
54 bool LoopNest::arePerfectlyNested(const Loop &OuterLoop, const Loop &InnerLoop,
55                                   ScalarEvolution &SE) {
56   assert(!OuterLoop.getSubLoops().empty() && "Outer loop should have subloops");
57   assert(InnerLoop.getParentLoop() && "Inner loop should have a parent");
58   LLVM_DEBUG(dbgs() << "Checking whether loop '" << OuterLoop.getName()
59                     << "' and '" << InnerLoop.getName()
60                     << "' are perfectly nested.\n");
61 
62   // Determine whether the loops structure satisfies the following requirements:
63   //  - the inner loop should be the outer loop's only child
64   //  - the outer loop header should 'flow' into the inner loop preheader
65   //    or jump around the inner loop to the outer loop latch
66   //  - if the inner loop latch exits the inner loop, it should 'flow' into
67   //    the outer loop latch.
68   if (!checkLoopsStructure(OuterLoop, InnerLoop, SE)) {
69     LLVM_DEBUG(dbgs() << "Not perfectly nested: invalid loop structure.\n");
70     return false;
71   }
72 
73   // Bail out if we cannot retrieve the outer loop bounds.
74   auto OuterLoopLB = OuterLoop.getBounds(SE);
75   if (OuterLoopLB == None) {
76     LLVM_DEBUG(dbgs() << "Cannot compute loop bounds of OuterLoop: "
77                       << OuterLoop << "\n";);
78     return false;
79   }
80 
81   // Identify the outer loop latch comparison instruction.
82   const BasicBlock *Latch = OuterLoop.getLoopLatch();
83   assert(Latch && "Expecting a valid loop latch");
84   const BranchInst *BI = dyn_cast<BranchInst>(Latch->getTerminator());
85   assert(BI && BI->isConditional() &&
86          "Expecting loop latch terminator to be a branch instruction");
87 
88   const CmpInst *OuterLoopLatchCmp = dyn_cast<CmpInst>(BI->getCondition());
89   DEBUG_WITH_TYPE(
90       VerboseDebug, if (OuterLoopLatchCmp) {
91         dbgs() << "Outer loop latch compare instruction: " << *OuterLoopLatchCmp
92                << "\n";
93       });
94 
95   // Identify the inner loop guard instruction.
96   BranchInst *InnerGuard = InnerLoop.getLoopGuardBranch();
97   const CmpInst *InnerLoopGuardCmp =
98       (InnerGuard) ? dyn_cast<CmpInst>(InnerGuard->getCondition()) : nullptr;
99 
100   DEBUG_WITH_TYPE(
101       VerboseDebug, if (InnerLoopGuardCmp) {
102         dbgs() << "Inner loop guard compare instruction: " << *InnerLoopGuardCmp
103                << "\n";
104       });
105 
106   // Determine whether instructions in a basic block are one of:
107   //  - the inner loop guard comparison
108   //  - the outer loop latch comparison
109   //  - the outer loop induction variable increment
110   //  - a phi node, a cast or a branch
111   auto containsOnlySafeInstructions = [&](const BasicBlock &BB) {
112     return llvm::all_of(BB, [&](const Instruction &I) {
113       bool isAllowed = isSafeToSpeculativelyExecute(&I) || isa<PHINode>(I) ||
114                        isa<BranchInst>(I);
115       if (!isAllowed) {
116         DEBUG_WITH_TYPE(VerboseDebug, {
117           dbgs() << "Instruction: " << I << "\nin basic block: " << BB
118                  << " is considered unsafe.\n";
119         });
120         return false;
121       }
122 
123       // The only binary instruction allowed is the outer loop step instruction,
124       // the only comparison instructions allowed are the inner loop guard
125       // compare instruction and the outer loop latch compare instruction.
126       if ((isa<BinaryOperator>(I) && &I != &OuterLoopLB->getStepInst()) ||
127           (isa<CmpInst>(I) && &I != OuterLoopLatchCmp &&
128            &I != InnerLoopGuardCmp)) {
129         DEBUG_WITH_TYPE(VerboseDebug, {
130           dbgs() << "Instruction: " << I << "\nin basic block:" << BB
131                  << "is unsafe.\n";
132         });
133         return false;
134       }
135       return true;
136     });
137   };
138 
139   // Check the code surrounding the inner loop for instructions that are deemed
140   // unsafe.
141   const BasicBlock *OuterLoopHeader = OuterLoop.getHeader();
142   const BasicBlock *OuterLoopLatch = OuterLoop.getLoopLatch();
143   const BasicBlock *InnerLoopPreHeader = InnerLoop.getLoopPreheader();
144 
145   if (!containsOnlySafeInstructions(*OuterLoopHeader) ||
146       !containsOnlySafeInstructions(*OuterLoopLatch) ||
147       (InnerLoopPreHeader != OuterLoopHeader &&
148        !containsOnlySafeInstructions(*InnerLoopPreHeader)) ||
149       !containsOnlySafeInstructions(*InnerLoop.getExitBlock())) {
150     LLVM_DEBUG(dbgs() << "Not perfectly nested: code surrounding inner loop is "
151                          "unsafe\n";);
152     return false;
153   }
154 
155   LLVM_DEBUG(dbgs() << "Loop '" << OuterLoop.getName() << "' and '"
156                     << InnerLoop.getName() << "' are perfectly nested.\n");
157 
158   return true;
159 }
160 
161 SmallVector<LoopVectorTy, 4>
162 LoopNest::getPerfectLoops(ScalarEvolution &SE) const {
163   SmallVector<LoopVectorTy, 4> LV;
164   LoopVectorTy PerfectNest;
165 
166   for (Loop *L : depth_first(const_cast<Loop *>(Loops.front()))) {
167     if (PerfectNest.empty())
168       PerfectNest.push_back(L);
169 
170     auto &SubLoops = L->getSubLoops();
171     if (SubLoops.size() == 1 && arePerfectlyNested(*L, *SubLoops.front(), SE)) {
172       PerfectNest.push_back(SubLoops.front());
173     } else {
174       LV.push_back(PerfectNest);
175       PerfectNest.clear();
176     }
177   }
178 
179   return LV;
180 }
181 
182 unsigned LoopNest::getMaxPerfectDepth(const Loop &Root, ScalarEvolution &SE) {
183   LLVM_DEBUG(dbgs() << "Get maximum perfect depth of loop nest rooted by loop '"
184                     << Root.getName() << "'\n");
185 
186   const Loop *CurrentLoop = &Root;
187   const auto *SubLoops = &CurrentLoop->getSubLoops();
188   unsigned CurrentDepth = 1;
189 
190   while (SubLoops->size() == 1) {
191     const Loop *InnerLoop = SubLoops->front();
192     if (!arePerfectlyNested(*CurrentLoop, *InnerLoop, SE)) {
193       LLVM_DEBUG({
194         dbgs() << "Not a perfect nest: loop '" << CurrentLoop->getName()
195                << "' is not perfectly nested with loop '"
196                << InnerLoop->getName() << "'\n";
197       });
198       break;
199     }
200 
201     CurrentLoop = InnerLoop;
202     SubLoops = &CurrentLoop->getSubLoops();
203     ++CurrentDepth;
204   }
205 
206   return CurrentDepth;
207 }
208 
209 static bool checkLoopsStructure(const Loop &OuterLoop, const Loop &InnerLoop,
210                                 ScalarEvolution &SE) {
211   // The inner loop must be the only outer loop's child.
212   if ((OuterLoop.getSubLoops().size() != 1) ||
213       (InnerLoop.getParentLoop() != &OuterLoop))
214     return false;
215 
216   // We expect loops in normal form which have a preheader, header, latch...
217   if (!OuterLoop.isLoopSimplifyForm() || !InnerLoop.isLoopSimplifyForm())
218     return false;
219 
220   const BasicBlock *OuterLoopHeader = OuterLoop.getHeader();
221   const BasicBlock *OuterLoopLatch = OuterLoop.getLoopLatch();
222   const BasicBlock *InnerLoopPreHeader = InnerLoop.getLoopPreheader();
223   const BasicBlock *InnerLoopLatch = InnerLoop.getLoopLatch();
224   const BasicBlock *InnerLoopExit = InnerLoop.getExitBlock();
225 
226   // We expect rotated loops. The inner loop should have a single exit block.
227   if (OuterLoop.getExitingBlock() != OuterLoopLatch ||
228       InnerLoop.getExitingBlock() != InnerLoopLatch || !InnerLoopExit)
229     return false;
230 
231   // Ensure the only branch that may exist between the loops is the inner loop
232   // guard.
233   if (OuterLoopHeader != InnerLoopPreHeader) {
234     const BranchInst *BI =
235         dyn_cast<BranchInst>(OuterLoopHeader->getTerminator());
236 
237     if (!BI || BI != InnerLoop.getLoopGuardBranch())
238       return false;
239 
240     // The successors of the inner loop guard should be the inner loop
241     // preheader and the outer loop latch.
242     for (const BasicBlock *Succ : BI->successors()) {
243       if (Succ == InnerLoopPreHeader)
244         continue;
245       if (Succ == OuterLoopLatch)
246         continue;
247 
248       DEBUG_WITH_TYPE(VerboseDebug, {
249         dbgs() << "Inner loop guard successor " << Succ->getName()
250                << " doesn't lead to inner loop preheader or "
251                   "outer loop latch.\n";
252       });
253       return false;
254     }
255   }
256 
257   // Ensure the inner loop exit block leads to the outer loop latch.
258   if (InnerLoopExit->getSingleSuccessor() != OuterLoopLatch) {
259     DEBUG_WITH_TYPE(
260         VerboseDebug,
261         dbgs() << "Inner loop exit block " << *InnerLoopExit
262                << " does not directly lead to the outer loop latch.\n";);
263     return false;
264   }
265 
266   return true;
267 }
268 
269 raw_ostream &llvm::operator<<(raw_ostream &OS, const LoopNest &LN) {
270   OS << "IsPerfect=";
271   if (LN.getMaxPerfectDepth() == LN.getNestDepth())
272     OS << "true";
273   else
274     OS << "false";
275   OS << ", Depth=" << LN.getNestDepth();
276   OS << ", OutermostLoop: " << LN.getOutermostLoop().getName();
277   OS << ", Loops: ( ";
278   for (const Loop *L : LN.getLoops())
279     OS << L->getName() << " ";
280   OS << ")";
281 
282   return OS;
283 }
284 
285 //===----------------------------------------------------------------------===//
286 // LoopNestPrinterPass implementation
287 //
288 
289 PreservedAnalyses LoopNestPrinterPass::run(Loop &L, LoopAnalysisManager &AM,
290                                            LoopStandardAnalysisResults &AR,
291                                            LPMUpdater &U) {
292   if (auto LN = LoopNest::getLoopNest(L, AR.SE))
293     OS << *LN << "\n";
294 
295   return PreservedAnalyses::all();
296 }
297