LLVM  13.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 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());
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 
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) {
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)) {
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 
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 
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 
209  const BasicBlock *End) {
210  assert(From && "Expecting valid From");
211  assert(End && "Expecting valid End");
212 
213  if (From == End || !From->getUniqueSuccessor())
214  return *From;
215 
216  auto IsEmpty = [](const BasicBlock *BB) {
217  return (BB->getInstList().size() == 1);
218  };
219 
220  // Visited is used to avoid running into an infinite loop.
222  const BasicBlock *BB = From->getUniqueSuccessor();
223  const BasicBlock *PredBB = BB;
224  while (BB && BB != End && IsEmpty(BB) && !Visited.count(BB)) {
225  Visited.insert(BB);
226  PredBB = BB;
227  BB = BB->getUniqueSuccessor();
228  }
229 
230  return (BB == End) ? *End : *PredBB;
231 }
232 
233 static bool checkLoopsStructure(const Loop &OuterLoop, const Loop &InnerLoop,
234  ScalarEvolution &SE) {
235  // The inner loop must be the only outer loop's child.
236  if ((OuterLoop.getSubLoops().size() != 1) ||
237  (InnerLoop.getParentLoop() != &OuterLoop))
238  return false;
239 
240  // We expect loops in normal form which have a preheader, header, latch...
241  if (!OuterLoop.isLoopSimplifyForm() || !InnerLoop.isLoopSimplifyForm())
242  return false;
243 
244  const BasicBlock *OuterLoopHeader = OuterLoop.getHeader();
245  const BasicBlock *OuterLoopLatch = OuterLoop.getLoopLatch();
246  const BasicBlock *InnerLoopPreHeader = InnerLoop.getLoopPreheader();
247  const BasicBlock *InnerLoopLatch = InnerLoop.getLoopLatch();
248  const BasicBlock *InnerLoopExit = InnerLoop.getExitBlock();
249 
250  // We expect rotated loops. The inner loop should have a single exit block.
251  if (OuterLoop.getExitingBlock() != OuterLoopLatch ||
252  InnerLoop.getExitingBlock() != InnerLoopLatch || !InnerLoopExit)
253  return false;
254 
255  // Returns whether the block `ExitBlock` contains at least one LCSSA Phi node.
256  auto ContainsLCSSAPhi = [](const BasicBlock &ExitBlock) {
257  return any_of(ExitBlock.phis(), [](const PHINode &PN) {
258  return PN.getNumIncomingValues() == 1;
259  });
260  };
261 
262  // Returns whether the block `BB` qualifies for being an extra Phi block. The
263  // extra Phi block is the additional block inserted after the exit block of an
264  // "guarded" inner loop which contains "only" Phi nodes corresponding to the
265  // LCSSA Phi nodes in the exit block.
266  auto IsExtraPhiBlock = [&](const BasicBlock &BB) {
267  return BB.getFirstNonPHI() == BB.getTerminator() &&
268  all_of(BB.phis(), [&](const PHINode &PN) {
269  return all_of(PN.blocks(), [&](const BasicBlock *IncomingBlock) {
270  return IncomingBlock == InnerLoopExit ||
271  IncomingBlock == OuterLoopHeader;
272  });
273  });
274  };
275 
276  const BasicBlock *ExtraPhiBlock = nullptr;
277  // Ensure the only branch that may exist between the loops is the inner loop
278  // guard.
279  if (OuterLoopHeader != InnerLoopPreHeader) {
280  const BasicBlock &SingleSucc =
281  LoopNest::skipEmptyBlockUntil(OuterLoopHeader, InnerLoopPreHeader);
282 
283  // no conditional branch present
284  if (&SingleSucc != InnerLoopPreHeader) {
285  const BranchInst *BI = dyn_cast<BranchInst>(SingleSucc.getTerminator());
286 
287  if (!BI || BI != InnerLoop.getLoopGuardBranch())
288  return false;
289 
290  bool InnerLoopExitContainsLCSSA = ContainsLCSSAPhi(*InnerLoopExit);
291 
292  // The successors of the inner loop guard should be the inner loop
293  // preheader or the outer loop latch possibly through empty blocks.
294  for (const BasicBlock *Succ : BI->successors()) {
295  const BasicBlock *PotentialInnerPreHeader = Succ;
296  const BasicBlock *PotentialOuterLatch = Succ;
297 
298  // Ensure the inner loop guard successor is empty before skipping
299  // blocks.
300  if (Succ->getInstList().size() == 1) {
301  PotentialInnerPreHeader =
302  &LoopNest::skipEmptyBlockUntil(Succ, InnerLoopPreHeader);
303  PotentialOuterLatch =
304  &LoopNest::skipEmptyBlockUntil(Succ, OuterLoopLatch);
305  }
306 
307  if (PotentialInnerPreHeader == InnerLoopPreHeader)
308  continue;
309  if (PotentialOuterLatch == OuterLoopLatch)
310  continue;
311 
312  // If `InnerLoopExit` contains LCSSA Phi instructions, additional block
313  // may be inserted before the `OuterLoopLatch` to which `BI` jumps. The
314  // loops are still considered perfectly nested if the extra block only
315  // contains Phi instructions from InnerLoopExit and OuterLoopHeader.
316  if (InnerLoopExitContainsLCSSA && IsExtraPhiBlock(*Succ) &&
317  Succ->getSingleSuccessor() == OuterLoopLatch) {
318  // Points to the extra block so that we can reference it later in the
319  // final check. We can also conclude that the inner loop is
320  // guarded and there exists LCSSA Phi node in the exit block later if
321  // we see a non-null `ExtraPhiBlock`.
322  ExtraPhiBlock = Succ;
323  continue;
324  }
325 
327  dbgs() << "Inner loop guard successor " << Succ->getName()
328  << " doesn't lead to inner loop preheader or "
329  "outer loop latch.\n";
330  });
331  return false;
332  }
333  }
334  }
335 
336  // Ensure the inner loop exit block lead to the outer loop latch possibly
337  // through empty blocks.
338  const BasicBlock &SuccInner =
339  LoopNest::skipEmptyBlockUntil(InnerLoop.getExitBlock(), OuterLoopLatch);
340  if (&SuccInner != OuterLoopLatch && &SuccInner != ExtraPhiBlock) {
342  VerboseDebug,
343  dbgs() << "Inner loop exit block " << *InnerLoopExit
344  << " does not directly lead to the outer loop latch.\n";);
345  return false;
346  }
347 
348  return true;
349 }
350 
352 
354  OS << "IsPerfect=";
355  if (LN.getMaxPerfectDepth() == LN.getNestDepth())
356  OS << "true";
357  else
358  OS << "false";
359  OS << ", Depth=" << LN.getNestDepth();
360  OS << ", OutermostLoop: " << LN.getOutermostLoop().getName();
361  OS << ", Loops: ( ";
362  for (const Loop *L : LN.getLoops())
363  OS << L->getName() << " ";
364  OS << ")";
365 
366  return OS;
367 }
368 
369 //===----------------------------------------------------------------------===//
370 // LoopNestPrinterPass implementation
371 //
372 
373 PreservedAnalyses LoopNestPrinterPass::run(Loop &L, LoopAnalysisManager &AM,
375  LPMUpdater &U) {
376  if (auto LN = LoopNest::getLoopNest(L, AR.SE))
377  OS << *LN << "\n";
378 
379  return PreservedAnalyses::all();
380 }
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 class represents lattice values for constants.
Definition: AllocatorList.h:23
llvm::BranchInst::successors
iterator_range< succ_op_iterator > successors()
Definition: Instructions.h:3115
llvm::LoopBase::getExitBlock
BlockT * getExitBlock() const
If getExitBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:82
BreadthFirstIterator.h
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:529
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:53
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:443
llvm::Loop::getLoopGuardBranch
BranchInst * getLoopGuardBranch() const
Return the loop guard branch, if it exists.
Definition: LoopInfo.cpp:365
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::SmallPtrSet< const BasicBlock *, 4 >
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:122
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:132
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:1498
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::isSafeToSpeculativelyExecute
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 ...
Definition: ValueTracking.cpp:4392
PostDominators.h
llvm::LoopNest::skipEmptyBlockUntil
static const BasicBlock & skipEmptyBlockUntil(const BasicBlock *From, const BasicBlock *End)
Recursivelly traverse all empty 'single successor' basic blocks of From (if there are any).
Definition: LoopNestAnalysis.cpp:208
llvm::AMDGPU::PALMD::Key
Key
PAL metadata keys.
Definition: AMDGPUMetadata.h:471
llvm::breadth_first
iterator_range< bf_iterator< T > > breadth_first(const T &G)
Definition: BreadthFirstIterator.h:156
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:50
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:862
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:233
llvm::BranchInst::getCondition
Value * getCondition() const
Definition: Instructions.h:3086
llvm::CmpInst
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:712
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:471
llvm::LPMUpdater
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
Definition: LoopPassManager.h:243
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
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:181
llvm::LoopBase::getLoopPreheader
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:167
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:70
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:1505
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:1683
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:148
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:286
llvm::depth_first
iterator_range< df_iterator< T > > depth_first(const T &G)
Definition: DepthFirstIterator.h:227
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:99
llvm::LoopNest::getNestDepth
unsigned getNestDepth() const
Return the loop nest depth (i.e.
Definition: LoopNestAnalysis.h:122
llvm::LoopNest::Loops
LoopVectorTy Loops
Definition: LoopNestAnalysis.h:151
llvm::LoopNest::getMaxPerfectDepth
unsigned getMaxPerfectDepth() const
Return the maximum perfect nesting depth.
Definition: LoopNestAnalysis.h:130
llvm::PHINode
Definition: Instructions.h:2572
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:43
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:3005
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:27
llvm::BranchInst::isConditional
bool isConditional() const
Definition: Instructions.h:3084
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:161
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