LLVM  14.0.0git
LoopBoundSplit.cpp
Go to the documentation of this file.
1 //===------- LoopBoundSplit.cpp - Split Loop Bound --------------*- C++ -*-===//
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 
10 #include "llvm/ADT/Sequence.h"
13 #include "llvm/Analysis/LoopInfo.h"
15 #include "llvm/Analysis/LoopPass.h"
20 #include "llvm/IR/PatternMatch.h"
26 
27 #define DEBUG_TYPE "loop-bound-split"
28 
29 namespace llvm {
30 
31 using namespace PatternMatch;
32 
33 namespace {
34 struct ConditionInfo {
35  /// Branch instruction with this condition
36  BranchInst *BI;
37  /// ICmp instruction with this condition
38  ICmpInst *ICmp;
39  /// Preciate info
41  /// AddRec llvm value
42  Value *AddRecValue;
43  /// Non PHI AddRec llvm value
44  Value *NonPHIAddRecValue;
45  /// Bound llvm value
46  Value *BoundValue;
47  /// AddRec SCEV
48  const SCEVAddRecExpr *AddRecSCEV;
49  /// Bound SCEV
50  const SCEV *BoundSCEV;
51 
52  ConditionInfo()
53  : BI(nullptr), ICmp(nullptr), Pred(ICmpInst::BAD_ICMP_PREDICATE),
54  AddRecValue(nullptr), BoundValue(nullptr), AddRecSCEV(nullptr),
55  BoundSCEV(nullptr) {}
56 };
57 } // namespace
58 
59 static void analyzeICmp(ScalarEvolution &SE, ICmpInst *ICmp,
60  ConditionInfo &Cond, const Loop &L) {
61  Cond.ICmp = ICmp;
62  if (match(ICmp, m_ICmp(Cond.Pred, m_Value(Cond.AddRecValue),
63  m_Value(Cond.BoundValue)))) {
64  const SCEV *AddRecSCEV = SE.getSCEV(Cond.AddRecValue);
65  const SCEV *BoundSCEV = SE.getSCEV(Cond.BoundValue);
66  const SCEVAddRecExpr *LHSAddRecSCEV = dyn_cast<SCEVAddRecExpr>(AddRecSCEV);
67  const SCEVAddRecExpr *RHSAddRecSCEV = dyn_cast<SCEVAddRecExpr>(BoundSCEV);
68  // Locate AddRec in LHSSCEV and Bound in RHSSCEV.
69  if (!LHSAddRecSCEV && RHSAddRecSCEV) {
70  std::swap(Cond.AddRecValue, Cond.BoundValue);
71  std::swap(AddRecSCEV, BoundSCEV);
73  }
74 
75  Cond.AddRecSCEV = dyn_cast<SCEVAddRecExpr>(AddRecSCEV);
76  Cond.BoundSCEV = BoundSCEV;
77  Cond.NonPHIAddRecValue = Cond.AddRecValue;
78 
79  // If the Cond.AddRecValue is PHI node, update Cond.NonPHIAddRecValue with
80  // value from backedge.
81  if (Cond.AddRecSCEV && isa<PHINode>(Cond.AddRecValue)) {
82  PHINode *PN = cast<PHINode>(Cond.AddRecValue);
83  Cond.NonPHIAddRecValue = PN->getIncomingValueForBlock(L.getLoopLatch());
84  }
85  }
86 }
87 
88 static bool calculateUpperBound(const Loop &L, ScalarEvolution &SE,
89  ConditionInfo &Cond, bool IsExitCond) {
90  if (IsExitCond) {
91  const SCEV *ExitCount = SE.getExitCount(&L, Cond.ICmp->getParent());
92  if (isa<SCEVCouldNotCompute>(ExitCount))
93  return false;
94 
95  Cond.BoundSCEV = ExitCount;
96  return true;
97  }
98 
99  // For non-exit condtion, if pred is LT, keep existing bound.
100  if (Cond.Pred == ICmpInst::ICMP_SLT || Cond.Pred == ICmpInst::ICMP_ULT)
101  return true;
102 
103  // For non-exit condition, if pre is LE, try to convert it to LT.
104  // Range Range
105  // AddRec <= Bound --> AddRec < Bound + 1
106  if (Cond.Pred != ICmpInst::ICMP_ULE && Cond.Pred != ICmpInst::ICMP_SLE)
107  return false;
108 
109  if (IntegerType *BoundSCEVIntType =
110  dyn_cast<IntegerType>(Cond.BoundSCEV->getType())) {
111  unsigned BitWidth = BoundSCEVIntType->getBitWidth();
112  APInt Max = ICmpInst::isSigned(Cond.Pred)
115  const SCEV *MaxSCEV = SE.getConstant(Max);
116  // Check Bound < INT_MAX
117  ICmpInst::Predicate Pred =
119  if (SE.isKnownPredicate(Pred, Cond.BoundSCEV, MaxSCEV)) {
120  const SCEV *BoundPlusOneSCEV =
121  SE.getAddExpr(Cond.BoundSCEV, SE.getOne(BoundSCEVIntType));
122  Cond.BoundSCEV = BoundPlusOneSCEV;
123  Cond.Pred = Pred;
124  return true;
125  }
126  }
127 
128  // ToDo: Support ICMP_NE/EQ.
129 
130  return false;
131 }
132 
133 static bool hasProcessableCondition(const Loop &L, ScalarEvolution &SE,
134  ICmpInst *ICmp, ConditionInfo &Cond,
135  bool IsExitCond) {
136  analyzeICmp(SE, ICmp, Cond, L);
137 
138  // The BoundSCEV should be evaluated at loop entry.
139  if (!SE.isAvailableAtLoopEntry(Cond.BoundSCEV, &L))
140  return false;
141 
142  // Allowed AddRec as induction variable.
143  if (!Cond.AddRecSCEV)
144  return false;
145 
146  if (!Cond.AddRecSCEV->isAffine())
147  return false;
148 
149  const SCEV *StepRecSCEV = Cond.AddRecSCEV->getStepRecurrence(SE);
150  // Allowed constant step.
151  if (!isa<SCEVConstant>(StepRecSCEV))
152  return false;
153 
154  ConstantInt *StepCI = cast<SCEVConstant>(StepRecSCEV)->getValue();
155  // Allowed positive step for now.
156  // TODO: Support negative step.
157  if (StepCI->isNegative() || StepCI->isZero())
158  return false;
159 
160  // Calculate upper bound.
161  if (!calculateUpperBound(L, SE, Cond, IsExitCond))
162  return false;
163 
164  return true;
165 }
166 
167 static bool isProcessableCondBI(const ScalarEvolution &SE,
168  const BranchInst *BI) {
169  BasicBlock *TrueSucc = nullptr;
170  BasicBlock *FalseSucc = nullptr;
171  ICmpInst::Predicate Pred;
172  Value *LHS, *RHS;
173  if (!match(BI, m_Br(m_ICmp(Pred, m_Value(LHS), m_Value(RHS)),
174  m_BasicBlock(TrueSucc), m_BasicBlock(FalseSucc))))
175  return false;
176 
177  if (!SE.isSCEVable(LHS->getType()))
178  return false;
179  assert(SE.isSCEVable(RHS->getType()) && "Expected RHS's type is SCEVable");
180 
181  if (TrueSucc == FalseSucc)
182  return false;
183 
184  return true;
185 }
186 
187 static bool canSplitLoopBound(const Loop &L, const DominatorTree &DT,
188  ScalarEvolution &SE, ConditionInfo &Cond) {
189  // Skip function with optsize.
190  if (L.getHeader()->getParent()->hasOptSize())
191  return false;
192 
193  // Split only innermost loop.
194  if (!L.isInnermost())
195  return false;
196 
197  // Check loop is in simplified form.
198  if (!L.isLoopSimplifyForm())
199  return false;
200 
201  // Check loop is in LCSSA form.
202  if (!L.isLCSSAForm(DT))
203  return false;
204 
205  // Skip loop that cannot be cloned.
206  if (!L.isSafeToClone())
207  return false;
208 
209  BasicBlock *ExitingBB = L.getExitingBlock();
210  // Assumed only one exiting block.
211  if (!ExitingBB)
212  return false;
213 
214  BranchInst *ExitingBI = dyn_cast<BranchInst>(ExitingBB->getTerminator());
215  if (!ExitingBI)
216  return false;
217 
218  // Allowed only conditional branch with ICmp.
219  if (!isProcessableCondBI(SE, ExitingBI))
220  return false;
221 
222  // Check the condition is processable.
223  ICmpInst *ICmp = cast<ICmpInst>(ExitingBI->getCondition());
224  if (!hasProcessableCondition(L, SE, ICmp, Cond, /*IsExitCond*/ true))
225  return false;
226 
227  Cond.BI = ExitingBI;
228  return true;
229 }
230 
231 static bool isProfitableToTransform(const Loop &L, const BranchInst *BI) {
232  // If the conditional branch splits a loop into two halves, we could
233  // generally say it is profitable.
234  //
235  // ToDo: Add more profitable cases here.
236 
237  // Check this branch causes diamond CFG.
238  BasicBlock *Succ0 = BI->getSuccessor(0);
239  BasicBlock *Succ1 = BI->getSuccessor(1);
240 
241  BasicBlock *Succ0Succ = Succ0->getSingleSuccessor();
242  BasicBlock *Succ1Succ = Succ1->getSingleSuccessor();
243  if (!Succ0Succ || !Succ1Succ || Succ0Succ != Succ1Succ)
244  return false;
245 
246  // ToDo: Calculate each successor's instruction cost.
247 
248  return true;
249 }
250 
252  ConditionInfo &ExitingCond,
253  ConditionInfo &SplitCandidateCond) {
254  for (auto *BB : L.blocks()) {
255  // Skip condition of backedge.
256  if (L.getLoopLatch() == BB)
257  continue;
258 
259  auto *BI = dyn_cast<BranchInst>(BB->getTerminator());
260  if (!BI)
261  continue;
262 
263  // Check conditional branch with ICmp.
264  if (!isProcessableCondBI(SE, BI))
265  continue;
266 
267  // Skip loop invariant condition.
268  if (L.isLoopInvariant(BI->getCondition()))
269  continue;
270 
271  // Check the condition is processable.
272  ICmpInst *ICmp = cast<ICmpInst>(BI->getCondition());
273  if (!hasProcessableCondition(L, SE, ICmp, SplitCandidateCond,
274  /*IsExitCond*/ false))
275  continue;
276 
277  if (ExitingCond.BoundSCEV->getType() !=
278  SplitCandidateCond.BoundSCEV->getType())
279  continue;
280 
281  // After transformation, we assume the split condition of the pre-loop is
282  // always true. In order to guarantee it, we need to check the start value
283  // of the split cond AddRec satisfies the split condition.
284  if (!SE.isLoopEntryGuardedByCond(&L, SplitCandidateCond.Pred,
285  SplitCandidateCond.AddRecSCEV->getStart(),
286  SplitCandidateCond.BoundSCEV))
287  continue;
288 
289  SplitCandidateCond.BI = BI;
290  return BI;
291  }
292 
293  return nullptr;
294 }
295 
296 static bool splitLoopBound(Loop &L, DominatorTree &DT, LoopInfo &LI,
297  ScalarEvolution &SE, LPMUpdater &U) {
298  ConditionInfo SplitCandidateCond;
299  ConditionInfo ExitingCond;
300 
301  // Check we can split this loop's bound.
302  if (!canSplitLoopBound(L, DT, SE, ExitingCond))
303  return false;
304 
305  if (!findSplitCandidate(L, SE, ExitingCond, SplitCandidateCond))
306  return false;
307 
308  if (!isProfitableToTransform(L, SplitCandidateCond.BI))
309  return false;
310 
311  // Now, we have a split candidate. Let's build a form as below.
312  // +--------------------+
313  // | preheader |
314  // | set up newbound |
315  // +--------------------+
316  // | /----------------\
317  // +--------v----v------+ |
318  // | header |---\ |
319  // | with true condition| | |
320  // +--------------------+ | |
321  // | | |
322  // +--------v-----------+ | |
323  // | if.then.BB | | |
324  // +--------------------+ | |
325  // | | |
326  // +--------v-----------<---/ |
327  // | latch >----------/
328  // | with newbound |
329  // +--------------------+
330  // |
331  // +--------v-----------+
332  // | preheader2 |--------------\
333  // | if (AddRec i != | |
334  // | org bound) | |
335  // +--------------------+ |
336  // | /----------------\ |
337  // +--------v----v------+ | |
338  // | header2 |---\ | |
339  // | conditional branch | | | |
340  // |with false condition| | | |
341  // +--------------------+ | | |
342  // | | | |
343  // +--------v-----------+ | | |
344  // | if.then.BB2 | | | |
345  // +--------------------+ | | |
346  // | | | |
347  // +--------v-----------<---/ | |
348  // | latch2 >----------/ |
349  // | with org bound | |
350  // +--------v-----------+ |
351  // | |
352  // | +---------------+ |
353  // +--> exit <-------/
354  // +---------------+
355 
356  // Let's create post loop.
357  SmallVector<BasicBlock *, 8> PostLoopBlocks;
358  Loop *PostLoop;
359  ValueToValueMapTy VMap;
360  BasicBlock *PreHeader = L.getLoopPreheader();
361  BasicBlock *SplitLoopPH = SplitEdge(PreHeader, L.getHeader(), &DT, &LI);
362  PostLoop = cloneLoopWithPreheader(L.getExitBlock(), SplitLoopPH, &L, VMap,
363  ".split", &LI, &DT, PostLoopBlocks);
364  remapInstructionsInBlocks(PostLoopBlocks, VMap);
365 
366  BasicBlock *PostLoopPreHeader = PostLoop->getLoopPreheader();
367  IRBuilder<> Builder(&PostLoopPreHeader->front());
368 
369  // Update phi nodes in header of post-loop.
370  bool isExitingLatch =
371  (L.getExitingBlock() == L.getLoopLatch()) ? true : false;
372  Value *ExitingCondLCSSAPhi = nullptr;
373  for (PHINode &PN : L.getHeader()->phis()) {
374  // Create LCSSA phi node in preheader of post-loop.
375  PHINode *LCSSAPhi =
376  Builder.CreatePHI(PN.getType(), 1, PN.getName() + ".lcssa");
377  LCSSAPhi->setDebugLoc(PN.getDebugLoc());
378  // If the exiting block is loop latch, the phi does not have the update at
379  // last iteration. In this case, update lcssa phi with value from backedge.
380  LCSSAPhi->addIncoming(
381  isExitingLatch ? PN.getIncomingValueForBlock(L.getLoopLatch()) : &PN,
382  L.getExitingBlock());
383 
384  // Update the start value of phi node in post-loop with the LCSSA phi node.
385  PHINode *PostLoopPN = cast<PHINode>(VMap[&PN]);
386  PostLoopPN->setIncomingValueForBlock(PostLoopPreHeader, LCSSAPhi);
387 
388  // Find PHI with exiting condition from pre-loop. The PHI should be
389  // SCEVAddRecExpr and have same incoming value from backedge with
390  // ExitingCond.
391  if (!SE.isSCEVable(PN.getType()))
392  continue;
393 
394  const SCEVAddRecExpr *PhiSCEV = dyn_cast<SCEVAddRecExpr>(SE.getSCEV(&PN));
395  if (PhiSCEV && ExitingCond.NonPHIAddRecValue ==
396  PN.getIncomingValueForBlock(L.getLoopLatch()))
397  ExitingCondLCSSAPhi = LCSSAPhi;
398  }
399 
400  // Add conditional branch to check we can skip post-loop in its preheader.
401  Instruction *OrigBI = PostLoopPreHeader->getTerminator();
403  Value *Cond =
404  Builder.CreateICmp(Pred, ExitingCondLCSSAPhi, ExitingCond.BoundValue);
405  Builder.CreateCondBr(Cond, PostLoop->getHeader(), PostLoop->getExitBlock());
406  OrigBI->eraseFromParent();
407 
408  // Create new loop bound and add it into preheader of pre-loop.
409  const SCEV *NewBoundSCEV = ExitingCond.BoundSCEV;
410  const SCEV *SplitBoundSCEV = SplitCandidateCond.BoundSCEV;
411  NewBoundSCEV = ICmpInst::isSigned(ExitingCond.Pred)
412  ? SE.getSMinExpr(NewBoundSCEV, SplitBoundSCEV)
413  : SE.getUMinExpr(NewBoundSCEV, SplitBoundSCEV);
414 
415  SCEVExpander Expander(
416  SE, L.getHeader()->getParent()->getParent()->getDataLayout(), "split");
417  Instruction *InsertPt = SplitLoopPH->getTerminator();
418  Value *NewBoundValue =
419  Expander.expandCodeFor(NewBoundSCEV, NewBoundSCEV->getType(), InsertPt);
420  NewBoundValue->setName("new.bound");
421 
422  // Replace exiting bound value of pre-loop NewBound.
423  ExitingCond.ICmp->setOperand(1, NewBoundValue);
424 
425  // Replace SplitCandidateCond.BI's condition of pre-loop by True.
426  LLVMContext &Context = PreHeader->getContext();
427  SplitCandidateCond.BI->setCondition(ConstantInt::getTrue(Context));
428 
429  // Replace cloned SplitCandidateCond.BI's condition in post-loop by False.
430  BranchInst *ClonedSplitCandidateBI =
431  cast<BranchInst>(VMap[SplitCandidateCond.BI]);
432  ClonedSplitCandidateBI->setCondition(ConstantInt::getFalse(Context));
433 
434  // Replace exit branch target of pre-loop by post-loop's preheader.
435  if (L.getExitBlock() == ExitingCond.BI->getSuccessor(0))
436  ExitingCond.BI->setSuccessor(0, PostLoopPreHeader);
437  else
438  ExitingCond.BI->setSuccessor(1, PostLoopPreHeader);
439 
440  // Update phi node in exit block of post-loop.
441  Builder.SetInsertPoint(&PostLoopPreHeader->front());
442  for (PHINode &PN : PostLoop->getExitBlock()->phis()) {
443  for (auto i : seq<int>(0, PN.getNumOperands())) {
444  // Check incoming block is pre-loop's exiting block.
445  if (PN.getIncomingBlock(i) == L.getExitingBlock()) {
446  Value *IncomingValue = PN.getIncomingValue(i);
447 
448  // Create LCSSA phi node for incoming value.
449  PHINode *LCSSAPhi =
450  Builder.CreatePHI(PN.getType(), 1, PN.getName() + ".lcssa");
451  LCSSAPhi->setDebugLoc(PN.getDebugLoc());
452  LCSSAPhi->addIncoming(IncomingValue, PN.getIncomingBlock(i));
453 
454  // Replace pre-loop's exiting block by post-loop's preheader.
455  PN.setIncomingBlock(i, PostLoopPreHeader);
456  // Replace incoming value by LCSSAPhi.
457  PN.setIncomingValue(i, LCSSAPhi);
458  // Add a new incoming value with post-loop's exiting block.
459  PN.addIncoming(VMap[IncomingValue], PostLoop->getExitingBlock());
460  }
461  }
462  }
463 
464  // Update dominator tree.
465  DT.changeImmediateDominator(PostLoopPreHeader, L.getExitingBlock());
466  DT.changeImmediateDominator(PostLoop->getExitBlock(), PostLoopPreHeader);
467 
468  // Invalidate cached SE information.
469  SE.forgetLoop(&L);
470 
471  // Canonicalize loops.
472  simplifyLoop(&L, &DT, &LI, &SE, nullptr, nullptr, true);
473  simplifyLoop(PostLoop, &DT, &LI, &SE, nullptr, nullptr, true);
474 
475  // Add new post-loop to loop pass manager.
476  U.addSiblingLoops(PostLoop);
477 
478  return true;
479 }
480 
483  LPMUpdater &U) {
484  Function &F = *L.getHeader()->getParent();
485  (void)F;
486 
487  LLVM_DEBUG(dbgs() << "Spliting bound of loop in " << F.getName() << ": " << L
488  << "\n");
489 
490  if (!splitLoopBound(L, AR.DT, AR.LI, AR.SE, U))
491  return PreservedAnalyses::all();
492 
494  AR.LI.verify(AR.DT);
495 
497 }
498 
499 } // end namespace llvm
i
i
Definition: README.txt:29
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::Loop::isLoopInvariant
bool isLoopInvariant(const Value *V) const
Return true if the specified value is loop invariant.
Definition: LoopInfo.cpp:64
llvm::CmpInst::getSwappedPredicate
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Definition: InstrTypes.h:851
llvm::ScalarEvolution::isLoopEntryGuardedByCond
bool isLoopEntryGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether entry to the loop is protected by a conditional between LHS and RHS.
Definition: ScalarEvolution.cpp:10611
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
LoopSimplify.h
llvm::LoopBase::getExitBlock
BlockT * getExitBlock() const
If getExitBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:82
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:721
llvm::cloneLoopWithPreheader
Loop * cloneLoopWithPreheader(BasicBlock *Before, BasicBlock *LoopDomBB, Loop *OrigLoop, ValueToValueMapTy &VMap, const Twine &NameSuffix, LoopInfo *LI, DominatorTree *DT, SmallVectorImpl< BasicBlock * > &Blocks)
Clones a loop OrigLoop.
Definition: CloneFunction.cpp:801
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
ScalarEvolutionExpander.h
MemorySSAUpdater.h
llvm::Function
Definition: Function.h:62
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
llvm::SCEVExpander
This class uses information about analyze scalars to rewrite expressions in canonical form.
Definition: ScalarEvolutionExpander.h:65
llvm::ConstantInt::getValue
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:133
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::LoopInfoBase::verify
void verify(const DominatorTreeBase< BlockT, false > &DomTree) const
Definition: LoopInfoImpl.h:690
llvm::APInt::getMaxValue
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
Definition: APInt.h:186
LoopAccessAnalysis.h
llvm::IRBuilder<>
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:460
llvm::CmpInst::ICMP_NE
@ ICMP_NE
not equal
Definition: InstrTypes.h:743
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
llvm::SCEVExpander::expandCodeFor
Value * expandCodeFor(const SCEV *SH, Type *Ty, Instruction *I)
Insert code to directly compute the specified SCEV expression into the program.
Definition: ScalarEvolutionExpander.h:277
llvm::PatternMatch::m_Br
brc_match< Cond_t, bind_ty< BasicBlock >, bind_ty< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
Definition: PatternMatch.h:1738
llvm::APInt::getSignedMaxValue
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
Definition: APInt.h:189
ScalarEvolution.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::BasicBlock::getSingleSuccessor
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
Definition: BasicBlock.cpp:298
llvm::CmpInst::ICMP_SLE
@ ICMP_SLE
signed less or equal
Definition: InstrTypes.h:751
LoopBoundSplit.h
llvm::LoopStandardAnalysisResults::DT
DominatorTree & DT
Definition: LoopAnalysisManager.h:55
llvm::Sched::Fast
@ Fast
Definition: TargetLowering.h:105
Sequence.h
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
F
#define F(x, y, z)
Definition: MD5.cpp:56
Context
ManagedStatic< detail::RecordContext > Context
Definition: Record.cpp:96
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
LoopAnalysisManager.h
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::findSplitCandidate
static BranchInst * findSplitCandidate(const Loop &L, ScalarEvolution &SE, ConditionInfo &ExitingCond, ConditionInfo &SplitCandidateCond)
Definition: LoopBoundSplit.cpp:251
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
llvm::ScalarEvolution::getOne
const SCEV * getOne(Type *Ty)
Return a SCEV for the constant 1 of a specific type.
Definition: ScalarEvolution.h:647
llvm::PatternMatch::match
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
llvm::CmpInst::ICMP_ULE
@ ICMP_ULE
unsigned less or equal
Definition: InstrTypes.h:747
llvm::remapInstructionsInBlocks
void remapInstructionsInBlocks(const SmallVectorImpl< BasicBlock * > &Blocks, ValueToValueMapTy &VMap)
Remaps instructions in Blocks using the mapping in VMap.
Definition: CloneFunction.cpp:787
llvm::canSplitLoopBound
static bool canSplitLoopBound(const Loop &L, const DominatorTree &DT, ScalarEvolution &SE, ConditionInfo &Cond)
Definition: LoopBoundSplit.cpp:187
llvm::LoopBase::blocks
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:178
llvm::PHINode::getIncomingValueForBlock
Value * getIncomingValueForBlock(const BasicBlock *BB) const
Definition: Instructions.h:2833
llvm::IntegerType
Class to represent integer types.
Definition: DerivedTypes.h:40
llvm::Instruction
Definition: Instruction.h:45
llvm::ScalarEvolution::isKnownPredicate
bool isKnownPredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
Definition: ScalarEvolution.cpp:9994
llvm::BranchInst::setCondition
void setCondition(Value *V)
Definition: Instructions.h:3169
llvm::BasicBlock::phis
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:354
llvm::Value::setName
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:376
llvm::splitLoopBound
static bool splitLoopBound(Loop &L, DominatorTree &DT, LoopInfo &LI, ScalarEvolution &SE, LPMUpdater &U)
Definition: LoopBoundSplit.cpp:296
LoopUtils.h
llvm::DominatorTreeBase::changeImmediateDominator
void changeImmediateDominator(DomTreeNodeBase< NodeT > *N, DomTreeNodeBase< NodeT > *NewIDom)
changeImmediateDominator - This method is used to update the dominator tree information when a node's...
Definition: GenericDomTree.h:655
llvm::LoopBase::getExitingBlock
BlockT * getExitingBlock() const
If getExitingBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:49
PatternMatch.h
LoopIterator.h
LoopInfo.h
llvm::BranchInst::getCondition
Value * getCondition() const
Definition: Instructions.h:3164
llvm::ScalarEvolution::getSCEV
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
Definition: ScalarEvolution.cpp:4110
llvm::hasProcessableCondition
static bool hasProcessableCondition(const Loop &L, ScalarEvolution &SE, ICmpInst *ICmp, ConditionInfo &Cond, bool IsExitCond)
Definition: LoopBoundSplit.cpp:133
llvm::getLoopPassPreservedAnalyses
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
Definition: LoopAnalysisManager.cpp:140
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:479
llvm::LoopBoundSplitPass::run
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
Definition: LoopBoundSplit.cpp:481
llvm::SCEV
This class represents an analyzed expression in the program.
Definition: ScalarEvolution.h:77
llvm::isProcessableCondBI
static bool isProcessableCondBI(const ScalarEvolution &SE, const BranchInst *BI)
Definition: LoopBoundSplit.cpp:167
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:78
llvm::ICmpInst
This instruction compares its operands according to the predicate given to the constructor.
Definition: Instructions.h:1185
llvm::GlobalValue::getParent
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:578
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::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2798
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:68
Cloning.h
llvm::LoopBase::getLoopPreheader
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:167
llvm::Instruction::setDebugLoc
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:367
llvm::LoopBase::getLoopLatch
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:216
llvm::ScalarEvolution::getUMinExpr
const SCEV * getUMinExpr(const SCEV *LHS, const SCEV *RHS)
Definition: ScalarEvolution.cpp:3888
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:840
llvm::PHINode::setIncomingValueForBlock
void setIncomingValueForBlock(const BasicBlock *BB, Value *V)
Set every incoming value(s) for block BB to V.
Definition: Instructions.h:2840
llvm::CmpInst::BAD_ICMP_PREDICATE
@ BAD_ICMP_PREDICATE
Definition: InstrTypes.h:754
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:650
llvm::PatternMatch::m_Value
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:76
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:75
llvm::CmpInst::ICMP_SLT
@ ICMP_SLT
signed less than
Definition: InstrTypes.h:750
llvm::LoopInfo
Definition: LoopInfo.h:1083
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:179
llvm::ScalarEvolution::getConstant
const SCEV * getConstant(ConstantInt *V)
Definition: ScalarEvolution.cpp:444
llvm::CmpInst::ICMP_ULT
@ ICMP_ULT
unsigned less than
Definition: InstrTypes.h:746
LoopPass.h
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
llvm::ConstantInt::isZero
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
Definition: Constants.h:194
llvm::LoopStandardAnalysisResults::LI
LoopInfo & LI
Definition: LoopAnalysisManager.h:56
llvm::calculateUpperBound
static bool calculateUpperBound(const Loop &L, ScalarEvolution &SE, ConditionInfo &Cond, bool IsExitCond)
Definition: LoopBoundSplit.cpp:88
llvm::ValueMap< const Value *, WeakTrackingVH >
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::ConstantInt::getFalse
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:880
llvm::Function::hasOptSize
bool hasOptSize() const
Optimize this function for size (-Os) or minimum size (-Oz).
Definition: Function.h:661
llvm::BasicBlock::front
const Instruction & front() const
Definition: BasicBlock.h:308
llvm::BasicBlock::getContext
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:36
llvm::LoopBase::isInnermost
bool isInnermost() const
Return true if the loop does not contain any (natural) loops.
Definition: LoopInfo.h:165
llvm::SplitEdge
BasicBlock * SplitEdge(BasicBlock *From, BasicBlock *To, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="")
Split the edge connecting the specified blocks, and return the newly created basic block between From...
Definition: BasicBlockUtils.cpp:518
llvm::ScalarEvolution::forgetLoop
void forgetLoop(const Loop *L)
This method should be called by the client when it has changed a loop in a way that may effect Scalar...
Definition: ScalarEvolution.cpp:7622
llvm::ConstantInt::getTrue
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:873
llvm::Loop::isLCSSAForm
bool isLCSSAForm(const DominatorTree &DT) const
Return true if the Loop is in LCSSA form.
Definition: LoopInfo.cpp:462
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
llvm::SCEVAddRecExpr
This node represents a polynomial recurrence on the trip count of the specified loop.
Definition: ScalarEvolutionExpressions.h:352
llvm::BitWidth
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:147
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:104
llvm::isProfitableToTransform
static bool isProfitableToTransform(const Loop &L, const BranchInst *BI)
Definition: LoopBoundSplit.cpp:231
llvm::ScalarEvolution::isSCEVable
bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
Definition: ScalarEvolution.cpp:3968
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
llvm::CmpInst::isSigned
bool isSigned() const
Definition: InstrTypes.h:949
llvm::simplifyLoop
bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
Simplify each loop in a loop nest recursively.
Definition: LoopSimplify.cpp:718
llvm::ScalarEvolution::isAvailableAtLoopEntry
bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L)
Determine if the SCEV can be evaluated at loop's entry.
Definition: ScalarEvolution.cpp:2412
llvm::LoopStandardAnalysisResults::SE
ScalarEvolution & SE
Definition: LoopAnalysisManager.h:57
llvm::analyzeICmp
static void analyzeICmp(ScalarEvolution &SE, ICmpInst *ICmp, ConditionInfo &Cond, const Loop &L)
Definition: LoopBoundSplit.cpp:59
ScalarEvolutionExpressions.h
MemorySSA.h
llvm::ConstantInt::isNegative
bool isNegative() const
Definition: Constants.h:189
llvm::PatternMatch::m_ICmp
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
Definition: PatternMatch.h:1401
llvm::Loop::isSafeToClone
bool isSafeToClone() const
Return true if the loop body is safe to clone in practice.
Definition: LoopInfo.cpp:486
llvm::DominatorTreeBase::verify
bool verify(VerificationLevel VL=VerificationLevel::Full) const
verify - checks if the tree is correct.
Definition: GenericDomTree.h:802
llvm::PHINode
Definition: Instructions.h:2648
llvm::Module::getDataLayout
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.cpp:401
llvm::SCEV::getType
Type * getType() const
Return the LLVM type of this SCEV expression.
Definition: ScalarEvolution.cpp:377
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::ScalarEvolution::getAddExpr
const SCEV * getAddExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical add expression, or something simpler if possible.
Definition: ScalarEvolution.cpp:2417
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
llvm::PatternMatch::m_BasicBlock
class_match< BasicBlock > m_BasicBlock()
Match an arbitrary basic block value and ignore it.
Definition: PatternMatch.h:160
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3083
llvm::LPMUpdater::addSiblingLoops
void addSiblingLoops(ArrayRef< Loop * > NewSibLoops)
Loop passes should use this method to indicate they have added new sibling loops to the current loop.
Definition: LoopPassManager.h:331
BasicBlockUtils.h
llvm::ScalarEvolution::getSMinExpr
const SCEV * getSMinExpr(const SCEV *LHS, const SCEV *RHS)
Definition: ScalarEvolution.cpp:3878
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::ScalarEvolution::getExitCount
const SCEV * getExitCount(const Loop *L, const BasicBlock *ExitingBlock, ExitCountKind Kind=Exact)
Return the number of times the backedge executes before the given exit would be taken; if not exactly...
Definition: ScalarEvolution.cpp:7473
llvm::BranchInst::getSuccessor
BasicBlock * getSuccessor(unsigned i) const
Definition: Instructions.h:3176