LLVM  14.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)) {
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 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());
64  VerboseDebug, if (OuterLoopLatchCmp) {
65  dbgs() << "Outer loop latch compare instruction: " << *OuterLoopLatchCmp
66  << "\n";
67  });
68  return OuterLoopLatchCmp;
69 }
70 
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 
78  VerboseDebug, if (InnerLoopGuardCmp) {
79  dbgs() << "Inner loop guard compare instruction: " << *InnerLoopGuardCmp
80  << "\n";
81  });
82  return InnerLoopGuardCmp;
83 }
84 
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 
104 bool LoopNest::arePerfectlyNested(const Loop &OuterLoop, const Loop &InnerLoop,
105  ScalarEvolution &SE) {
106  return (analyzeLoopNestForPerfectNest(OuterLoop, InnerLoop, SE) ==
107  PerfectLoopNest);
108 }
109 
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) {
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 
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);
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 
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 
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 
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.
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 
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 
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 ||
423  ExtraPhiBlock) != ExtraPhiBlock) &&
425  OuterLoopLatch) != OuterLoopLatch)) {
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 
437 
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 
458 PreservedAnalyses LoopNestPrinterPass::run(Loop &L, LoopAnalysisManager &AM,
460  LPMUpdater &U) {
461  if (auto LN = LoopNest::getLoopNest(L, AR.SE))
462  OS << *LN << "\n";
463 
464  return PreservedAnalyses::all();
465 }
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
VerboseDebug
static const char * VerboseDebug
Definition: LoopNestAnalysis.cpp:24
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
llvm::BranchInst::successors
iterator_range< succ_op_iterator > successors()
Definition: Instructions.h:3178
llvm::LoopBase::getExitBlock
BlockT * getExitBlock() const
If getExitBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:82
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:4622
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:1168
Statistic.h
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:104
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:460
llvm::Loop::getLoopGuardBranch
BranchInst * getLoopGuardBranch() const
Return the loop guard branch, if it exists.
Definition: LoopInfo.cpp:366
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:52
llvm::Optional
Definition: APInt.h:33
llvm::SmallPtrSet< const BasicBlock *, 4 >
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
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:1551
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
PostDominators.h
llvm::AMDGPU::PALMD::Key
Key
PAL metadata keys.
Definition: AMDGPUMetadata.h:481
checkSafeInstruction
static bool checkSafeInstruction(const Instruction &I, const CmpInst *InnerLoopGuardCmp, const CmpInst *OuterLoopLatchCmp, Optional< Loop::LoopBounds > OuterLoopLB)
Definition: LoopNestAnalysis.cpp:85
llvm::breadth_first
iterator_range< bf_iterator< T > > breadth_first(const T &G)
Definition: BreadthFirstIterator.h:157
llvm::Instruction
Definition: Instruction.h:45
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
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:49
llvm::Loop::getName
StringRef getName() const
Definition: LoopInfo.h:866
llvm::None
const NoneType None
Definition: None.h:23
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:316
llvm::BranchInst::getCondition
Value * getCondition() const
Definition: Instructions.h:3149
llvm::CmpInst
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:710
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:478
llvm::LPMUpdater
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
Definition: LoopPassManager.h:263
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:289
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:72
I
#define I(x, y, z)
Definition: MD5.cpp:59
getOuterLoopLatchCmp
static CmpInst * getOuterLoopLatchCmp(const Loop &OuterLoop)
Definition: LoopNestAnalysis.cpp:53
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:262
llvm::LoopBase::getLoopPreheader
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:167
llvm::Loop::LoopBounds::getStepInst
Instruction & getStepInst() const
Get the instruction that updates the loop induction variable.
Definition: LoopInfo.h:653
llvm::LoopBase::getLoopLatch
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:216
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:382
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:1558
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:1748
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.cpp:152
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:287
llvm::depth_first
iterator_range< df_iterator< T > > depth_first(const T &G)
Definition: DepthFirstIterator.h:229
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:161
DEBUG_TYPE
#define DEBUG_TYPE
Definition: LoopNestAnalysis.cpp:22
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:104
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:585
llvm::LoopStandardAnalysisResults::SE
ScalarEvolution & SE
Definition: LoopAnalysisManager.h:57
llvm::LoopNest::getLoops
ArrayRef< Loop * > getLoops() const
Get the loops in the nest.
Definition: LoopNestAnalysis.h:109
llvm::LoopNest::getNestDepth
unsigned getNestDepth() const
Return the loop nest depth (i.e.
Definition: LoopNestAnalysis.h:132
getInnerLoopGuardCmp
static CmpInst * getInnerLoopGuardCmp(const Loop &InnerLoop)
Definition: LoopNestAnalysis.cpp:71
llvm::LoopNest::Loops
LoopVectorTy Loops
Definition: LoopNestAnalysis.h:161
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:182
llvm::LoopNest::getMaxPerfectDepth
unsigned getMaxPerfectDepth() const
Return the maximum perfect nesting depth.
Definition: LoopNestAnalysis.h:140
llvm::PHINode
Definition: Instructions.h:2633
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
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:3068
llvm::LoopNest::getLoopNest
static std::unique_ptr< LoopNest > getLoopNest(Loop &Root, ScalarEvolution &SE)
Construct a LoopNest object.
Definition: LoopNestAnalysis.cpp:48
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:3147
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:242
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:364