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  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.
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 
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)) {
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 
356 
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,
379  LPMUpdater &U) {
380  if (auto LN = LoopNest::getLoopNest(L, AR.SE))
381  OS << *LN << "\n";
382 
383  return PreservedAnalyses::all();
384 }
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
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::BranchInst::successors
iterator_range< succ_op_iterator > successors()
Definition: Instructions.h:3142
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:4583
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: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: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::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: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:1534
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
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:235
llvm::BranchInst::getCondition
Value * getCondition() const
Definition: Instructions.h:3113
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:241
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:208
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:71
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:1541
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:1724
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: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:100
llvm::LoopNest::getNestDepth
unsigned getNestDepth() const
Return the loop nest depth (i.e.
Definition: LoopNestAnalysis.h:123
llvm::LoopNest::Loops
LoopVectorTy Loops
Definition: LoopNestAnalysis.h:152
llvm::LoopNest::getMaxPerfectDepth
unsigned getMaxPerfectDepth() const
Return the maximum perfect nesting depth.
Definition: LoopNestAnalysis.h:131
llvm::PHINode
Definition: Instructions.h:2597
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:3032
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:3111
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