LLVM  15.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 
18 
19 using namespace llvm;
20 
21 #define DEBUG_TYPE "loopnest"
22 #ifndef NDEBUG
23 static const char *VerboseDebug = DEBUG_TYPE "-verbose";
24 #endif
25 
26 /// Determine whether the loops structure violates basic requirements for
27 /// perfect nesting:
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
34 /// false otherwise.
35 static bool checkLoopsStructure(const Loop &OuterLoop, const Loop &InnerLoop,
36  ScalarEvolution &SE);
37 
38 //===----------------------------------------------------------------------===//
39 // LoopNest implementation
40 //
41 
43  : MaxPerfectDepth(getMaxPerfectDepth(Root, SE)) {
45 }
46 
47 std::unique_ptr<LoopNest> LoopNest::getLoopNest(Loop &Root,
48  ScalarEvolution &SE) {
49  return std::make_unique<LoopNest>(Root, SE);
50 }
51 
52 static CmpInst *getOuterLoopLatchCmp(const Loop &OuterLoop) {
53 
54  const BasicBlock *Latch = OuterLoop.getLoopLatch();
55  assert(Latch && "Expecting a valid loop latch");
56 
57  const BranchInst *BI = dyn_cast<BranchInst>(Latch->getTerminator());
58  assert(BI && BI->isConditional() &&
59  "Expecting loop latch terminator to be a branch instruction");
60 
61  CmpInst *OuterLoopLatchCmp = dyn_cast<CmpInst>(BI->getCondition());
63  VerboseDebug, if (OuterLoopLatchCmp) {
64  dbgs() << "Outer loop latch compare instruction: " << *OuterLoopLatchCmp
65  << "\n";
66  });
67  return OuterLoopLatchCmp;
68 }
69 
70 static CmpInst *getInnerLoopGuardCmp(const Loop &InnerLoop) {
71 
72  BranchInst *InnerGuard = InnerLoop.getLoopGuardBranch();
73  CmpInst *InnerLoopGuardCmp =
74  (InnerGuard) ? dyn_cast<CmpInst>(InnerGuard->getCondition()) : nullptr;
75 
77  VerboseDebug, if (InnerLoopGuardCmp) {
78  dbgs() << "Inner loop guard compare instruction: " << *InnerLoopGuardCmp
79  << "\n";
80  });
81  return InnerLoopGuardCmp;
82 }
83 
84 static bool checkSafeInstruction(const Instruction &I,
85  const CmpInst *InnerLoopGuardCmp,
86  const CmpInst *OuterLoopLatchCmp,
87  Optional<Loop::LoopBounds> OuterLoopLB) {
88 
89  bool IsAllowed =
90  isSafeToSpeculativelyExecute(&I) || isa<PHINode>(I) || isa<BranchInst>(I);
91  if (!IsAllowed)
92  return false;
93  // The only binary instruction allowed is the outer loop step instruction,
94  // the only comparison instructions allowed are the inner loop guard
95  // compare instruction and the outer loop latch compare instruction.
96  if ((isa<BinaryOperator>(I) && &I != &OuterLoopLB->getStepInst()) ||
97  (isa<CmpInst>(I) && &I != OuterLoopLatchCmp && &I != InnerLoopGuardCmp)) {
98  return false;
99  }
100  return true;
101 }
102 
103 bool LoopNest::arePerfectlyNested(const Loop &OuterLoop, const Loop &InnerLoop,
104  ScalarEvolution &SE) {
105  return (analyzeLoopNestForPerfectNest(OuterLoop, InnerLoop, SE) ==
106  PerfectLoopNest);
107 }
108 
109 LoopNest::LoopNestEnum LoopNest::analyzeLoopNestForPerfectNest(
110  const Loop &OuterLoop, const Loop &InnerLoop, ScalarEvolution &SE) {
111 
112  assert(!OuterLoop.isInnermost() && "Outer loop should have subloops");
113  assert(!InnerLoop.isOutermost() && "Inner loop should have a parent");
114  LLVM_DEBUG(dbgs() << "Checking whether loop '" << OuterLoop.getName()
115  << "' and '" << InnerLoop.getName()
116  << "' are perfectly nested.\n");
117 
118  // Determine whether the loops structure satisfies the following requirements:
119  // - the inner loop should be the outer loop's only child
120  // - the outer loop header should 'flow' into the inner loop preheader
121  // or jump around the inner loop to the outer loop latch
122  // - if the inner loop latch exits the inner loop, it should 'flow' into
123  // the outer loop latch.
124  if (!checkLoopsStructure(OuterLoop, InnerLoop, SE)) {
125  LLVM_DEBUG(dbgs() << "Not perfectly nested: invalid loop structure.\n");
126  return InvalidLoopStructure;
127  }
128 
129  // Bail out if we cannot retrieve the outer loop bounds.
130  auto OuterLoopLB = OuterLoop.getBounds(SE);
131  if (OuterLoopLB == None) {
132  LLVM_DEBUG(dbgs() << "Cannot compute loop bounds of OuterLoop: "
133  << OuterLoop << "\n";);
134  return OuterLoopLowerBoundUnknown;
135  }
136 
137  CmpInst *OuterLoopLatchCmp = getOuterLoopLatchCmp(OuterLoop);
138  CmpInst *InnerLoopGuardCmp = getInnerLoopGuardCmp(InnerLoop);
139 
140  // Determine whether instructions in a basic block are one of:
141  // - the inner loop guard comparison
142  // - the outer loop latch comparison
143  // - the outer loop induction variable increment
144  // - a phi node, a cast or a branch
145  auto containsOnlySafeInstructions = [&](const BasicBlock &BB) {
146  return llvm::all_of(BB, [&](const Instruction &I) {
147  bool IsSafeInstr = checkSafeInstruction(I, InnerLoopGuardCmp,
148  OuterLoopLatchCmp, OuterLoopLB);
149  if (IsSafeInstr) {
151  dbgs() << "Instruction: " << I << "\nin basic block:" << BB
152  << "is unsafe.\n";
153  });
154  }
155  return IsSafeInstr;
156  });
157  };
158 
159  // Check the code surrounding the inner loop for instructions that are deemed
160  // unsafe.
161  const BasicBlock *OuterLoopHeader = OuterLoop.getHeader();
162  const BasicBlock *OuterLoopLatch = OuterLoop.getLoopLatch();
163  const BasicBlock *InnerLoopPreHeader = InnerLoop.getLoopPreheader();
164 
165  if (!containsOnlySafeInstructions(*OuterLoopHeader) ||
166  !containsOnlySafeInstructions(*OuterLoopLatch) ||
167  (InnerLoopPreHeader != OuterLoopHeader &&
168  !containsOnlySafeInstructions(*InnerLoopPreHeader)) ||
169  !containsOnlySafeInstructions(*InnerLoop.getExitBlock())) {
170  LLVM_DEBUG(dbgs() << "Not perfectly nested: code surrounding inner loop is "
171  "unsafe\n";);
172  return ImperfectLoopNest;
173  }
174 
175  LLVM_DEBUG(dbgs() << "Loop '" << OuterLoop.getName() << "' and '"
176  << InnerLoop.getName() << "' are perfectly nested.\n");
177 
178  return PerfectLoopNest;
179 }
180 
182  const Loop &OuterLoop, const Loop &InnerLoop, ScalarEvolution &SE) {
183  InstrVectorTy Instr;
184  switch (analyzeLoopNestForPerfectNest(OuterLoop, InnerLoop, SE)) {
185  case PerfectLoopNest:
186  LLVM_DEBUG(dbgs() << "The loop Nest is Perfect, returning empty "
187  "instruction vector. \n";);
188  return Instr;
189 
190  case InvalidLoopStructure:
191  LLVM_DEBUG(dbgs() << "Not perfectly nested: invalid loop structure. "
192  "Instruction vector is empty.\n";);
193  return Instr;
194 
195  case OuterLoopLowerBoundUnknown:
196  LLVM_DEBUG(dbgs() << "Cannot compute loop bounds of OuterLoop: "
197  << OuterLoop << "\nInstruction vector is empty.\n";);
198  return Instr;
199 
200  case ImperfectLoopNest:
201  break;
202  }
203 
204  // Identify the outer loop latch comparison instruction.
205  auto OuterLoopLB = OuterLoop.getBounds(SE);
206 
207  CmpInst *OuterLoopLatchCmp = getOuterLoopLatchCmp(OuterLoop);
208  CmpInst *InnerLoopGuardCmp = getInnerLoopGuardCmp(InnerLoop);
209 
210  auto GetUnsafeInstructions = [&](const BasicBlock &BB) {
211  for (const Instruction &I : BB) {
212  if (!checkSafeInstruction(I, InnerLoopGuardCmp, OuterLoopLatchCmp,
213  OuterLoopLB)) {
214  Instr.push_back(&I);
216  dbgs() << "Instruction: " << I << "\nin basic block:" << BB
217  << "is unsafe.\n";
218  });
219  }
220  }
221  };
222 
223  // Check the code surrounding the inner loop for instructions that are deemed
224  // unsafe.
225  const BasicBlock *OuterLoopHeader = OuterLoop.getHeader();
226  const BasicBlock *OuterLoopLatch = OuterLoop.getLoopLatch();
227  const BasicBlock *InnerLoopPreHeader = InnerLoop.getLoopPreheader();
228  const BasicBlock *InnerLoopExitBlock = InnerLoop.getExitBlock();
229 
230  GetUnsafeInstructions(*OuterLoopHeader);
231  GetUnsafeInstructions(*OuterLoopLatch);
232  GetUnsafeInstructions(*InnerLoopExitBlock);
233 
234  if (InnerLoopPreHeader != OuterLoopHeader) {
235  GetUnsafeInstructions(*InnerLoopPreHeader);
236  }
237  return Instr;
238 }
239 
243  LoopVectorTy PerfectNest;
244 
245  for (Loop *L : depth_first(const_cast<Loop *>(Loops.front()))) {
246  if (PerfectNest.empty())
247  PerfectNest.push_back(L);
248 
249  auto &SubLoops = L->getSubLoops();
250  if (SubLoops.size() == 1 && arePerfectlyNested(*L, *SubLoops.front(), SE)) {
251  PerfectNest.push_back(SubLoops.front());
252  } else {
253  LV.push_back(PerfectNest);
254  PerfectNest.clear();
255  }
256  }
257 
258  return LV;
259 }
260 
262  LLVM_DEBUG(dbgs() << "Get maximum perfect depth of loop nest rooted by loop '"
263  << Root.getName() << "'\n");
264 
265  const Loop *CurrentLoop = &Root;
266  const auto *SubLoops = &CurrentLoop->getSubLoops();
267  unsigned CurrentDepth = 1;
268 
269  while (SubLoops->size() == 1) {
270  const Loop *InnerLoop = SubLoops->front();
271  if (!arePerfectlyNested(*CurrentLoop, *InnerLoop, SE)) {
272  LLVM_DEBUG({
273  dbgs() << "Not a perfect nest: loop '" << CurrentLoop->getName()
274  << "' is not perfectly nested with loop '"
275  << InnerLoop->getName() << "'\n";
276  });
277  break;
278  }
279 
280  CurrentLoop = InnerLoop;
281  SubLoops = &CurrentLoop->getSubLoops();
282  ++CurrentDepth;
283  }
284 
285  return CurrentDepth;
286 }
287 
289  const BasicBlock *End,
290  bool CheckUniquePred) {
291  assert(From && "Expecting valid From");
292  assert(End && "Expecting valid End");
293 
294  if (From == End || !From->getUniqueSuccessor())
295  return *From;
296 
297  auto IsEmpty = [](const BasicBlock *BB) {
298  return (BB->getInstList().size() == 1);
299  };
300 
301  // Visited is used to avoid running into an infinite loop.
303  const BasicBlock *BB = From->getUniqueSuccessor();
304  const BasicBlock *PredBB = From;
305  while (BB && BB != End && IsEmpty(BB) && !Visited.count(BB) &&
306  (!CheckUniquePred || BB->getUniquePredecessor())) {
307  Visited.insert(BB);
308  PredBB = BB;
309  BB = BB->getUniqueSuccessor();
310  }
311 
312  return (BB == End) ? *End : *PredBB;
313 }
314 
315 static bool checkLoopsStructure(const Loop &OuterLoop, const Loop &InnerLoop,
316  ScalarEvolution &SE) {
317  // The inner loop must be the only outer loop's child.
318  if ((OuterLoop.getSubLoops().size() != 1) ||
319  (InnerLoop.getParentLoop() != &OuterLoop))
320  return false;
321 
322  // We expect loops in normal form which have a preheader, header, latch...
323  if (!OuterLoop.isLoopSimplifyForm() || !InnerLoop.isLoopSimplifyForm())
324  return false;
325 
326  const BasicBlock *OuterLoopHeader = OuterLoop.getHeader();
327  const BasicBlock *OuterLoopLatch = OuterLoop.getLoopLatch();
328  const BasicBlock *InnerLoopPreHeader = InnerLoop.getLoopPreheader();
329  const BasicBlock *InnerLoopLatch = InnerLoop.getLoopLatch();
330  const BasicBlock *InnerLoopExit = InnerLoop.getExitBlock();
331 
332  // We expect rotated loops. The inner loop should have a single exit block.
333  if (OuterLoop.getExitingBlock() != OuterLoopLatch ||
334  InnerLoop.getExitingBlock() != InnerLoopLatch || !InnerLoopExit)
335  return false;
336 
337  // Returns whether the block `ExitBlock` contains at least one LCSSA Phi node.
338  auto ContainsLCSSAPhi = [](const BasicBlock &ExitBlock) {
339  return any_of(ExitBlock.phis(), [](const PHINode &PN) {
340  return PN.getNumIncomingValues() == 1;
341  });
342  };
343 
344  // Returns whether the block `BB` qualifies for being an extra Phi block. The
345  // extra Phi block is the additional block inserted after the exit block of an
346  // "guarded" inner loop which contains "only" Phi nodes corresponding to the
347  // LCSSA Phi nodes in the exit block.
348  auto IsExtraPhiBlock = [&](const BasicBlock &BB) {
349  return BB.getFirstNonPHI() == BB.getTerminator() &&
350  all_of(BB.phis(), [&](const PHINode &PN) {
351  return all_of(PN.blocks(), [&](const BasicBlock *IncomingBlock) {
352  return IncomingBlock == InnerLoopExit ||
353  IncomingBlock == OuterLoopHeader;
354  });
355  });
356  };
357 
358  const BasicBlock *ExtraPhiBlock = nullptr;
359  // Ensure the only branch that may exist between the loops is the inner loop
360  // guard.
361  if (OuterLoopHeader != InnerLoopPreHeader) {
362  const BasicBlock &SingleSucc =
363  LoopNest::skipEmptyBlockUntil(OuterLoopHeader, InnerLoopPreHeader);
364 
365  // no conditional branch present
366  if (&SingleSucc != InnerLoopPreHeader) {
367  const BranchInst *BI = dyn_cast<BranchInst>(SingleSucc.getTerminator());
368 
369  if (!BI || BI != InnerLoop.getLoopGuardBranch())
370  return false;
371 
372  bool InnerLoopExitContainsLCSSA = ContainsLCSSAPhi(*InnerLoopExit);
373 
374  // The successors of the inner loop guard should be the inner loop
375  // preheader or the outer loop latch possibly through empty blocks.
376  for (const BasicBlock *Succ : BI->successors()) {
377  const BasicBlock *PotentialInnerPreHeader = Succ;
378  const BasicBlock *PotentialOuterLatch = Succ;
379 
380  // Ensure the inner loop guard successor is empty before skipping
381  // blocks.
382  if (Succ->getInstList().size() == 1) {
383  PotentialInnerPreHeader =
384  &LoopNest::skipEmptyBlockUntil(Succ, InnerLoopPreHeader);
385  PotentialOuterLatch =
386  &LoopNest::skipEmptyBlockUntil(Succ, OuterLoopLatch);
387  }
388 
389  if (PotentialInnerPreHeader == InnerLoopPreHeader)
390  continue;
391  if (PotentialOuterLatch == OuterLoopLatch)
392  continue;
393 
394  // If `InnerLoopExit` contains LCSSA Phi instructions, additional block
395  // may be inserted before the `OuterLoopLatch` to which `BI` jumps. The
396  // loops are still considered perfectly nested if the extra block only
397  // contains Phi instructions from InnerLoopExit and OuterLoopHeader.
398  if (InnerLoopExitContainsLCSSA && IsExtraPhiBlock(*Succ) &&
399  Succ->getSingleSuccessor() == OuterLoopLatch) {
400  // Points to the extra block so that we can reference it later in the
401  // final check. We can also conclude that the inner loop is
402  // guarded and there exists LCSSA Phi node in the exit block later if
403  // we see a non-null `ExtraPhiBlock`.
404  ExtraPhiBlock = Succ;
405  continue;
406  }
407 
409  dbgs() << "Inner loop guard successor " << Succ->getName()
410  << " doesn't lead to inner loop preheader or "
411  "outer loop latch.\n";
412  });
413  return false;
414  }
415  }
416  }
417 
418  // Ensure the inner loop exit block lead to the outer loop latch possibly
419  // through empty blocks.
420  if ((!ExtraPhiBlock ||
422  ExtraPhiBlock) != ExtraPhiBlock) &&
424  OuterLoopLatch) != OuterLoopLatch)) {
426  VerboseDebug,
427  dbgs() << "Inner loop exit block " << *InnerLoopExit
428  << " does not directly lead to the outer loop latch.\n";);
429  return false;
430  }
431 
432  return true;
433 }
434 
436 
438  OS << "IsPerfect=";
439  if (LN.getMaxPerfectDepth() == LN.getNestDepth())
440  OS << "true";
441  else
442  OS << "false";
443  OS << ", Depth=" << LN.getNestDepth();
444  OS << ", OutermostLoop: " << LN.getOutermostLoop().getName();
445  OS << ", Loops: ( ";
446  for (const Loop *L : LN.getLoops())
447  OS << L->getName() << " ";
448  OS << ")";
449 
450  return OS;
451 }
452 
453 //===----------------------------------------------------------------------===//
454 // LoopNestPrinterPass implementation
455 //
456 
459  LPMUpdater &U) {
460  if (auto LN = LoopNest::getLoopNest(L, AR.SE))
461  OS << *LN << "\n";
462 
463  return PreservedAnalyses::all();
464 }
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
VerboseDebug
static const char * VerboseDebug
Definition: LoopNestAnalysis.cpp:23
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::BranchInst::successors
iterator_range< succ_op_iterator > successors()
Definition: Instructions.h:3209
llvm::LoopBase::getExitBlock
BlockT * getExitBlock() const
If getExitBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:81
BreadthFirstIterator.h
llvm::isSafeToSpeculativelyExecute
bool isSafeToSpeculativelyExecute(const Value *V, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
Definition: ValueTracking.cpp:4576
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
llvm::LoopNest::arePerfectlyNested
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...
Definition: LoopNestAnalysis.cpp:103
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:449
llvm::Loop::getLoopGuardBranch
BranchInst * getLoopGuardBranch() const
Return the loop guard branch, if it exists.
Definition: LoopInfo.cpp:363
ValueTracking.h
llvm::LoopStandardAnalysisResults
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
Definition: LoopAnalysisManager.h:51
llvm::Optional
Definition: APInt.h:33
llvm::SmallPtrSet< const BasicBlock *, 4 >
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
DepthFirstIterator.h
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::LoopBase::getParentLoop
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
Definition: LoopInfo.h:113
llvm::LoopBase::getSubLoops
const std::vector< LoopT * > & getSubLoops() const
Return the loops contained entirely within this loop.
Definition: LoopInfo.h:143
llvm::all_of
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:1605
DEBUG_WITH_TYPE
#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
llvm::AMDGPU::PALMD::Key
Key
PAL metadata keys.
Definition: AMDGPUMetadata.h:486
checkSafeInstruction
static bool checkSafeInstruction(const Instruction &I, const CmpInst *InnerLoopGuardCmp, const CmpInst *OuterLoopLatchCmp, Optional< Loop::LoopBounds > OuterLoopLB)
Definition: LoopNestAnalysis.cpp:84
llvm::breadth_first
iterator_range< bf_iterator< T > > breadth_first(const T &G)
Definition: BreadthFirstIterator.h:158
llvm::Instruction
Definition: Instruction.h:42
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:54
llvm::operator<<
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:230
llvm::LoopBase::getExitingBlock
BlockT * getExitingBlock() const
If getExitingBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:48
llvm::Loop::getName
StringRef getName() const
Definition: LoopInfo.h:869
llvm::None
const NoneType None
Definition: None.h:24
checkLoopsStructure
static bool checkLoopsStructure(const Loop &OuterLoop, const Loop &InnerLoop, ScalarEvolution &SE)
Determine whether the loops structure violates basic requirements for perfect nesting:
Definition: LoopNestAnalysis.cpp:315
llvm::dxil::PointerTypeAnalysis::run
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
Definition: PointerTypeAnalysis.cpp:101
llvm::BranchInst::getCondition
Value * getCondition() const
Definition: Instructions.h:3180
llvm::CmpInst
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:709
llvm::Loop::isLoopSimplifyForm
bool isLoopSimplifyForm() const
Return true if the Loop is in the form that the LoopSimplify form transforms loops to,...
Definition: LoopInfo.cpp:475
llvm::LPMUpdater
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
Definition: LoopPassManager.h:262
llvm::LoopNest::skipEmptyBlockUntil
static const BasicBlock & skipEmptyBlockUntil(const BasicBlock *From, const BasicBlock *End, bool CheckUniquePred=false)
Recursivelly traverse all empty 'single successor' basic blocks of From (if there are any).
Definition: LoopNestAnalysis.cpp:288
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:69
I
#define I(x, y, z)
Definition: MD5.cpp:58
getOuterLoopLatchCmp
static CmpInst * getOuterLoopLatchCmp(const Loop &OuterLoop)
Definition: LoopNestAnalysis.cpp:52
llvm::LoopNest::getMaxPerfectDepth
static unsigned getMaxPerfectDepth(const Loop &Root, ScalarEvolution &SE)
Return the maximum nesting depth of the loop nest rooted by loop Root.
Definition: LoopNestAnalysis.cpp:261
llvm::LoopBase::getLoopPreheader
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:166
llvm::Loop::LoopBounds::getStepInst
Instruction & getStepInst() const
Get the instruction that updates the loop induction variable.
Definition: LoopInfo.h:656
llvm::LoopBase::getLoopLatch
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:215
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LoopNestAnalysis.h
llvm::LoopNest::getOutermostLoop
Loop & getOutermostLoop() const
Return the outermost loop in the loop nest.
Definition: LoopNestAnalysis.h:80
llvm::SmallPtrSetImpl::count
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:383
llvm::LoopNest::LoopNest
LoopNest()=delete
llvm::any_of
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1612
llvm::LoopBase::isOutermost
bool isOutermost() const
Return true if the loop does not have a parent (natural) loop.
Definition: LoopInfo.h:168
llvm::append_range
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:1811
llvm::Loop::getBounds
Optional< LoopBounds > getBounds(ScalarEvolution &SE) const
Return the struct LoopBounds collected if all struct members are found, else None.
Definition: LoopInfo.cpp:283
llvm::depth_first
iterator_range< df_iterator< T > > depth_first(const T &G)
Definition: DepthFirstIterator.h:230
llvm::LoopBase::isInnermost
bool isInnermost() const
Return true if the loop does not contain any (natural) loops.
Definition: LoopInfo.h:165
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
DEBUG_TYPE
#define DEBUG_TYPE
Definition: LoopNestAnalysis.cpp:21
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:104
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:591
llvm::LoopStandardAnalysisResults::SE
ScalarEvolution & SE
Definition: LoopAnalysisManager.h:56
llvm::LoopNest::getLoops
ArrayRef< Loop * > getLoops() const
Get the loops in the nest.
Definition: LoopNestAnalysis.h:117
llvm::LoopNest::getNestDepth
unsigned getNestDepth() const
Return the loop nest depth (i.e.
Definition: LoopNestAnalysis.h:155
getInnerLoopGuardCmp
static CmpInst * getInnerLoopGuardCmp(const Loop &InnerLoop)
Definition: LoopNestAnalysis.cpp:70
llvm::LoopNest::Loops
LoopVectorTy Loops
Definition: LoopNestAnalysis.h:184
llvm::LoopNest::getInterveningInstructions
static InstrVectorTy getInterveningInstructions(const Loop &OuterLoop, const Loop &InnerLoop, ScalarEvolution &SE)
Return a vector of instructions that prevent the LoopNest given by loops OuterLoop and InnerLoop from...
Definition: LoopNestAnalysis.cpp:181
llvm::LoopNest::getMaxPerfectDepth
unsigned getMaxPerfectDepth() const
Return the maximum perfect nesting depth.
Definition: LoopNestAnalysis.h:163
llvm::PHINode
Definition: Instructions.h:2664
llvm::BasicBlock::getTerminator
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.h:119
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3099
llvm::LoopNest::getLoopNest
static std::unique_ptr< LoopNest > getLoopNest(Loop &Root, ScalarEvolution &SE)
Construct a LoopNest object.
Definition: LoopNestAnalysis.cpp:47
llvm::LoopNest
This class represents a loop nest and can be used to query its properties.
Definition: LoopNestAnalysis.h:28
llvm::BranchInst::isConditional
bool isConditional() const
Definition: Instructions.h:3178
llvm::LoopNest::getPerfectLoops
SmallVector< LoopVectorTy, 4 > getPerfectLoops(ScalarEvolution &SE) const
Retrieve a vector of perfect loop nests contained in the current loop nest.
Definition: LoopNestAnalysis.cpp:241
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:365