LLVM  12.0.0git
LoopNestAnalysis.cpp
Go to the documentation of this file.
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 
16 #include "llvm/ADT/Statistic.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 
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());
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 
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 
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 
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) {
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 
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 
291  LPMUpdater &U) {
292  if (auto LN = LoopNest::getLoopNest(L, AR.SE))
293  OS << *LN << "\n";
294 
295  return PreservedAnalyses::all();
296 }
This class represents a loop nest and can be used to query its properties.
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:715
LLVM_NODISCARD std::enable_if_t< !is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type > dyn_cast(const Y &Val)
Definition: Casting.h:334
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:208
This class represents lattice values for constants.
Definition: AllocatorList.h:23
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:69
LoopNest()=delete
void push_back(const T &Elt)
Definition: SmallVector.h:246
The main scalar evolution driver.
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:159
iterator_range< bf_iterator< T > > breadth_first(const T &G)
This file defines the interface for the loop nest analysis.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1491
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
Value * getCondition() const
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...
Definition: BasicBlock.cpp:150
Loop & getOutermostLoop() const
Return the outermost loop in the loop nest.
iterator_range< succ_op_iterator > successors()
#define DEBUG_WITH_TYPE(TYPE, X)
DEBUG_WITH_TYPE macro - This macro should be used by passes to emit debug information.
Definition: Debug.h:64
ArrayRef< Loop * > getLoops() const
Get the loops in the nest.
unsigned getNestDepth() const
Return the loop nest depth (i.e.
BranchInst * getLoopGuardBranch() const
Return the loop guard branch, if it exists.
Definition: LoopInfo.cpp:364
BlockT * getHeader() const
Definition: LoopInfo.h:104
unsigned getMaxPerfectDepth() const
Return the maximum perfect nesting depth.
static std::unique_ptr< LoopNest > getLoopNest(Loop &Root, ScalarEvolution &SE)
Construct a LoopNest object.
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
Definition: BasicBlock.cpp:293
LoopVectorTy Loops
static bool checkLoopsStructure(const Loop &OuterLoop, const Loop &InnerLoop, ScalarEvolution &SE)
Determine whether the loops structure violates basic requirements for perfect nesting: ...
Optional< LoopBounds > getBounds(ScalarEvolution &SE) const
Return the struct LoopBounds collected if all struct members are found, else None.
Definition: LoopInfo.cpp:285
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:154
static const char * VerboseDebug
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
Conditional or Unconditional Branch instruction.
SmallVector< LoopVectorTy, 4 > getPerfectLoops(ScalarEvolution &SE) const
Retrieve a vector of perfect loop nests contained in the current loop nest.
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...
BlockT * getExitBlock() const
If getExitBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:74
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:160
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:883
bool isConditional() const
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
#define DEBUG_TYPE
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
Definition: LoopInfo.h:113
const std::vector< LoopT * > & getSubLoops() const
Return the loops contained entirely within this loop.
Definition: LoopInfo.h:143
bool isLoopSimplifyForm() const
Return true if the Loop is in the form that the LoopSimplify form transforms loops to...
Definition: LoopInfo.cpp:466
StringRef getName() const
Definition: LoopInfo.h:846
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:516
#define I(x, y, z)
Definition: MD5.cpp:59
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2099
iterator_range< df_iterator< T > > depth_first(const T &G)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool isSafeToSpeculativelyExecute(const Value *V, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:46
A container for analyses that lazily runs them and caches their results.
#define LLVM_DEBUG(X)
Definition: Debug.h:122
BlockT * getExitingBlock() const
If getExitingBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:48
static unsigned getMaxPerfectDepth(const Loop &Root, ScalarEvolution &SE)
Return the maximum nesting depth of the loop nest rooted by loop Root.