xref: /freebsd/contrib/llvm-project/llvm/lib/Analysis/LoopNestAnalysis.cpp (revision ec0ea6efa1ad229d75c394c1a9b9cac33af2b1d3)
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   append_range(Loops, breadth_first(&Root));
46 }
47 
48 std::unique_ptr<LoopNest> LoopNest::getLoopNest(Loop &Root,
49                                                 ScalarEvolution &SE) {
50   return std::make_unique<LoopNest>(Root, SE);
51 }
52 
53 bool LoopNest::arePerfectlyNested(const Loop &OuterLoop, const Loop &InnerLoop,
54                                   ScalarEvolution &SE) {
55   assert(!OuterLoop.isInnermost() && "Outer loop should have subloops");
56   assert(!InnerLoop.isOutermost() && "Inner loop should have a parent");
57   LLVM_DEBUG(dbgs() << "Checking whether loop '" << OuterLoop.getName()
58                     << "' and '" << InnerLoop.getName()
59                     << "' are perfectly nested.\n");
60 
61   // Determine whether the loops structure satisfies the following requirements:
62   //  - the inner loop should be the outer loop's only child
63   //  - the outer loop header should 'flow' into the inner loop preheader
64   //    or jump around the inner loop to the outer loop latch
65   //  - if the inner loop latch exits the inner loop, it should 'flow' into
66   //    the outer loop latch.
67   if (!checkLoopsStructure(OuterLoop, InnerLoop, SE)) {
68     LLVM_DEBUG(dbgs() << "Not perfectly nested: invalid loop structure.\n");
69     return false;
70   }
71 
72   // Bail out if we cannot retrieve the outer loop bounds.
73   auto OuterLoopLB = OuterLoop.getBounds(SE);
74   if (OuterLoopLB == None) {
75     LLVM_DEBUG(dbgs() << "Cannot compute loop bounds of OuterLoop: "
76                       << OuterLoop << "\n";);
77     return false;
78   }
79 
80   // Identify the outer loop latch comparison instruction.
81   const BasicBlock *Latch = OuterLoop.getLoopLatch();
82   assert(Latch && "Expecting a valid loop latch");
83   const BranchInst *BI = dyn_cast<BranchInst>(Latch->getTerminator());
84   assert(BI && BI->isConditional() &&
85          "Expecting loop latch terminator to be a branch instruction");
86 
87   const CmpInst *OuterLoopLatchCmp = dyn_cast<CmpInst>(BI->getCondition());
88   DEBUG_WITH_TYPE(
89       VerboseDebug, if (OuterLoopLatchCmp) {
90         dbgs() << "Outer loop latch compare instruction: " << *OuterLoopLatchCmp
91                << "\n";
92       });
93 
94   // Identify the inner loop guard instruction.
95   BranchInst *InnerGuard = InnerLoop.getLoopGuardBranch();
96   const CmpInst *InnerLoopGuardCmp =
97       (InnerGuard) ? dyn_cast<CmpInst>(InnerGuard->getCondition()) : nullptr;
98 
99   DEBUG_WITH_TYPE(
100       VerboseDebug, if (InnerLoopGuardCmp) {
101         dbgs() << "Inner loop guard compare instruction: " << *InnerLoopGuardCmp
102                << "\n";
103       });
104 
105   // Determine whether instructions in a basic block are one of:
106   //  - the inner loop guard comparison
107   //  - the outer loop latch comparison
108   //  - the outer loop induction variable increment
109   //  - a phi node, a cast or a branch
110   auto containsOnlySafeInstructions = [&](const BasicBlock &BB) {
111     return llvm::all_of(BB, [&](const Instruction &I) {
112       bool isAllowed = isSafeToSpeculativelyExecute(&I) || isa<PHINode>(I) ||
113                        isa<BranchInst>(I);
114       if (!isAllowed) {
115         DEBUG_WITH_TYPE(VerboseDebug, {
116           dbgs() << "Instruction: " << I << "\nin basic block: " << BB
117                  << " is considered unsafe.\n";
118         });
119         return false;
120       }
121 
122       // The only binary instruction allowed is the outer loop step instruction,
123       // the only comparison instructions allowed are the inner loop guard
124       // compare instruction and the outer loop latch compare instruction.
125       if ((isa<BinaryOperator>(I) && &I != &OuterLoopLB->getStepInst()) ||
126           (isa<CmpInst>(I) && &I != OuterLoopLatchCmp &&
127            &I != InnerLoopGuardCmp)) {
128         DEBUG_WITH_TYPE(VerboseDebug, {
129           dbgs() << "Instruction: " << I << "\nin basic block:" << BB
130                  << "is unsafe.\n";
131         });
132         return false;
133       }
134       return true;
135     });
136   };
137 
138   // Check the code surrounding the inner loop for instructions that are deemed
139   // unsafe.
140   const BasicBlock *OuterLoopHeader = OuterLoop.getHeader();
141   const BasicBlock *OuterLoopLatch = OuterLoop.getLoopLatch();
142   const BasicBlock *InnerLoopPreHeader = InnerLoop.getLoopPreheader();
143 
144   if (!containsOnlySafeInstructions(*OuterLoopHeader) ||
145       !containsOnlySafeInstructions(*OuterLoopLatch) ||
146       (InnerLoopPreHeader != OuterLoopHeader &&
147        !containsOnlySafeInstructions(*InnerLoopPreHeader)) ||
148       !containsOnlySafeInstructions(*InnerLoop.getExitBlock())) {
149     LLVM_DEBUG(dbgs() << "Not perfectly nested: code surrounding inner loop is "
150                          "unsafe\n";);
151     return false;
152   }
153 
154   LLVM_DEBUG(dbgs() << "Loop '" << OuterLoop.getName() << "' and '"
155                     << InnerLoop.getName() << "' are perfectly nested.\n");
156 
157   return true;
158 }
159 
160 SmallVector<LoopVectorTy, 4>
161 LoopNest::getPerfectLoops(ScalarEvolution &SE) const {
162   SmallVector<LoopVectorTy, 4> LV;
163   LoopVectorTy PerfectNest;
164 
165   for (Loop *L : depth_first(const_cast<Loop *>(Loops.front()))) {
166     if (PerfectNest.empty())
167       PerfectNest.push_back(L);
168 
169     auto &SubLoops = L->getSubLoops();
170     if (SubLoops.size() == 1 && arePerfectlyNested(*L, *SubLoops.front(), SE)) {
171       PerfectNest.push_back(SubLoops.front());
172     } else {
173       LV.push_back(PerfectNest);
174       PerfectNest.clear();
175     }
176   }
177 
178   return LV;
179 }
180 
181 unsigned LoopNest::getMaxPerfectDepth(const Loop &Root, ScalarEvolution &SE) {
182   LLVM_DEBUG(dbgs() << "Get maximum perfect depth of loop nest rooted by loop '"
183                     << Root.getName() << "'\n");
184 
185   const Loop *CurrentLoop = &Root;
186   const auto *SubLoops = &CurrentLoop->getSubLoops();
187   unsigned CurrentDepth = 1;
188 
189   while (SubLoops->size() == 1) {
190     const Loop *InnerLoop = SubLoops->front();
191     if (!arePerfectlyNested(*CurrentLoop, *InnerLoop, SE)) {
192       LLVM_DEBUG({
193         dbgs() << "Not a perfect nest: loop '" << CurrentLoop->getName()
194                << "' is not perfectly nested with loop '"
195                << InnerLoop->getName() << "'\n";
196       });
197       break;
198     }
199 
200     CurrentLoop = InnerLoop;
201     SubLoops = &CurrentLoop->getSubLoops();
202     ++CurrentDepth;
203   }
204 
205   return CurrentDepth;
206 }
207 
208 const BasicBlock &LoopNest::skipEmptyBlockUntil(const BasicBlock *From,
209                                                 const BasicBlock *End,
210                                                 bool CheckUniquePred) {
211   assert(From && "Expecting valid From");
212   assert(End && "Expecting valid End");
213 
214   if (From == End || !From->getUniqueSuccessor())
215     return *From;
216 
217   auto IsEmpty = [](const BasicBlock *BB) {
218     return (BB->getInstList().size() == 1);
219   };
220 
221   // Visited is used to avoid running into an infinite loop.
222   SmallPtrSet<const BasicBlock *, 4> Visited;
223   const BasicBlock *BB = From->getUniqueSuccessor();
224   const BasicBlock *PredBB = From;
225   while (BB && BB != End && IsEmpty(BB) && !Visited.count(BB) &&
226          (!CheckUniquePred || BB->getUniquePredecessor())) {
227     Visited.insert(BB);
228     PredBB = BB;
229     BB = BB->getUniqueSuccessor();
230   }
231 
232   return (BB == End) ? *End : *PredBB;
233 }
234 
235 static bool checkLoopsStructure(const Loop &OuterLoop, const Loop &InnerLoop,
236                                 ScalarEvolution &SE) {
237   // The inner loop must be the only outer loop's child.
238   if ((OuterLoop.getSubLoops().size() != 1) ||
239       (InnerLoop.getParentLoop() != &OuterLoop))
240     return false;
241 
242   // We expect loops in normal form which have a preheader, header, latch...
243   if (!OuterLoop.isLoopSimplifyForm() || !InnerLoop.isLoopSimplifyForm())
244     return false;
245 
246   const BasicBlock *OuterLoopHeader = OuterLoop.getHeader();
247   const BasicBlock *OuterLoopLatch = OuterLoop.getLoopLatch();
248   const BasicBlock *InnerLoopPreHeader = InnerLoop.getLoopPreheader();
249   const BasicBlock *InnerLoopLatch = InnerLoop.getLoopLatch();
250   const BasicBlock *InnerLoopExit = InnerLoop.getExitBlock();
251 
252   // We expect rotated loops. The inner loop should have a single exit block.
253   if (OuterLoop.getExitingBlock() != OuterLoopLatch ||
254       InnerLoop.getExitingBlock() != InnerLoopLatch || !InnerLoopExit)
255     return false;
256 
257   // Returns whether the block `ExitBlock` contains at least one LCSSA Phi node.
258   auto ContainsLCSSAPhi = [](const BasicBlock &ExitBlock) {
259     return any_of(ExitBlock.phis(), [](const PHINode &PN) {
260       return PN.getNumIncomingValues() == 1;
261     });
262   };
263 
264   // Returns whether the block `BB` qualifies for being an extra Phi block. The
265   // extra Phi block is the additional block inserted after the exit block of an
266   // "guarded" inner loop which contains "only" Phi nodes corresponding to the
267   // LCSSA Phi nodes in the exit block.
268   auto IsExtraPhiBlock = [&](const BasicBlock &BB) {
269     return BB.getFirstNonPHI() == BB.getTerminator() &&
270            all_of(BB.phis(), [&](const PHINode &PN) {
271              return all_of(PN.blocks(), [&](const BasicBlock *IncomingBlock) {
272                return IncomingBlock == InnerLoopExit ||
273                       IncomingBlock == OuterLoopHeader;
274              });
275            });
276   };
277 
278   const BasicBlock *ExtraPhiBlock = nullptr;
279   // Ensure the only branch that may exist between the loops is the inner loop
280   // guard.
281   if (OuterLoopHeader != InnerLoopPreHeader) {
282     const BasicBlock &SingleSucc =
283         LoopNest::skipEmptyBlockUntil(OuterLoopHeader, InnerLoopPreHeader);
284 
285     // no conditional branch present
286     if (&SingleSucc != InnerLoopPreHeader) {
287       const BranchInst *BI = dyn_cast<BranchInst>(SingleSucc.getTerminator());
288 
289       if (!BI || BI != InnerLoop.getLoopGuardBranch())
290         return false;
291 
292       bool InnerLoopExitContainsLCSSA = ContainsLCSSAPhi(*InnerLoopExit);
293 
294       // The successors of the inner loop guard should be the inner loop
295       // preheader or the outer loop latch possibly through empty blocks.
296       for (const BasicBlock *Succ : BI->successors()) {
297         const BasicBlock *PotentialInnerPreHeader = Succ;
298         const BasicBlock *PotentialOuterLatch = Succ;
299 
300         // Ensure the inner loop guard successor is empty before skipping
301         // blocks.
302         if (Succ->getInstList().size() == 1) {
303           PotentialInnerPreHeader =
304               &LoopNest::skipEmptyBlockUntil(Succ, InnerLoopPreHeader);
305           PotentialOuterLatch =
306               &LoopNest::skipEmptyBlockUntil(Succ, OuterLoopLatch);
307         }
308 
309         if (PotentialInnerPreHeader == InnerLoopPreHeader)
310           continue;
311         if (PotentialOuterLatch == OuterLoopLatch)
312           continue;
313 
314         // If `InnerLoopExit` contains LCSSA Phi instructions, additional block
315         // may be inserted before the `OuterLoopLatch` to which `BI` jumps. The
316         // loops are still considered perfectly nested if the extra block only
317         // contains Phi instructions from InnerLoopExit and OuterLoopHeader.
318         if (InnerLoopExitContainsLCSSA && IsExtraPhiBlock(*Succ) &&
319             Succ->getSingleSuccessor() == OuterLoopLatch) {
320           // Points to the extra block so that we can reference it later in the
321           // final check. We can also conclude that the inner loop is
322           // guarded and there exists LCSSA Phi node in the exit block later if
323           // we see a non-null `ExtraPhiBlock`.
324           ExtraPhiBlock = Succ;
325           continue;
326         }
327 
328         DEBUG_WITH_TYPE(VerboseDebug, {
329           dbgs() << "Inner loop guard successor " << Succ->getName()
330                  << " doesn't lead to inner loop preheader or "
331                     "outer loop latch.\n";
332         });
333         return false;
334       }
335     }
336   }
337 
338   // Ensure the inner loop exit block lead to the outer loop latch possibly
339   // through empty blocks.
340   if ((!ExtraPhiBlock ||
341        &LoopNest::skipEmptyBlockUntil(InnerLoop.getExitBlock(),
342                                       ExtraPhiBlock) != ExtraPhiBlock) &&
343       (&LoopNest::skipEmptyBlockUntil(InnerLoop.getExitBlock(),
344                                       OuterLoopLatch) != OuterLoopLatch)) {
345     DEBUG_WITH_TYPE(
346         VerboseDebug,
347         dbgs() << "Inner loop exit block " << *InnerLoopExit
348                << " does not directly lead to the outer loop latch.\n";);
349     return false;
350   }
351 
352   return true;
353 }
354 
355 AnalysisKey LoopNestAnalysis::Key;
356 
357 raw_ostream &llvm::operator<<(raw_ostream &OS, const LoopNest &LN) {
358   OS << "IsPerfect=";
359   if (LN.getMaxPerfectDepth() == LN.getNestDepth())
360     OS << "true";
361   else
362     OS << "false";
363   OS << ", Depth=" << LN.getNestDepth();
364   OS << ", OutermostLoop: " << LN.getOutermostLoop().getName();
365   OS << ", Loops: ( ";
366   for (const Loop *L : LN.getLoops())
367     OS << L->getName() << " ";
368   OS << ")";
369 
370   return OS;
371 }
372 
373 //===----------------------------------------------------------------------===//
374 // LoopNestPrinterPass implementation
375 //
376 
377 PreservedAnalyses LoopNestPrinterPass::run(Loop &L, LoopAnalysisManager &AM,
378                                            LoopStandardAnalysisResults &AR,
379                                            LPMUpdater &U) {
380   if (auto LN = LoopNest::getLoopNest(L, AR.SE))
381     OS << *LN << "\n";
382 
383   return PreservedAnalyses::all();
384 }
385