LLVM  16.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"
12 #include "llvm/Analysis/LoopInfo.h"
15 #include "llvm/IR/PatternMatch.h"
21 
22 #define DEBUG_TYPE "loop-bound-split"
23 
24 namespace llvm {
25 
26 using namespace PatternMatch;
27 
28 namespace {
29 struct ConditionInfo {
30  /// Branch instruction with this condition
31  BranchInst *BI = nullptr;
32  /// ICmp instruction with this condition
33  ICmpInst *ICmp = nullptr;
34  /// Preciate info
36  /// AddRec llvm value
37  Value *AddRecValue = nullptr;
38  /// Non PHI AddRec llvm value
39  Value *NonPHIAddRecValue;
40  /// Bound llvm value
41  Value *BoundValue = nullptr;
42  /// AddRec SCEV
43  const SCEVAddRecExpr *AddRecSCEV = nullptr;
44  /// Bound SCEV
45  const SCEV *BoundSCEV = nullptr;
46 
47  ConditionInfo() = default;
48 };
49 } // namespace
50 
51 static void analyzeICmp(ScalarEvolution &SE, ICmpInst *ICmp,
52  ConditionInfo &Cond, const Loop &L) {
53  Cond.ICmp = ICmp;
54  if (match(ICmp, m_ICmp(Cond.Pred, m_Value(Cond.AddRecValue),
55  m_Value(Cond.BoundValue)))) {
56  const SCEV *AddRecSCEV = SE.getSCEV(Cond.AddRecValue);
57  const SCEV *BoundSCEV = SE.getSCEV(Cond.BoundValue);
58  const SCEVAddRecExpr *LHSAddRecSCEV = dyn_cast<SCEVAddRecExpr>(AddRecSCEV);
59  const SCEVAddRecExpr *RHSAddRecSCEV = dyn_cast<SCEVAddRecExpr>(BoundSCEV);
60  // Locate AddRec in LHSSCEV and Bound in RHSSCEV.
61  if (!LHSAddRecSCEV && RHSAddRecSCEV) {
62  std::swap(Cond.AddRecValue, Cond.BoundValue);
63  std::swap(AddRecSCEV, BoundSCEV);
65  }
66 
67  Cond.AddRecSCEV = dyn_cast<SCEVAddRecExpr>(AddRecSCEV);
68  Cond.BoundSCEV = BoundSCEV;
69  Cond.NonPHIAddRecValue = Cond.AddRecValue;
70 
71  // If the Cond.AddRecValue is PHI node, update Cond.NonPHIAddRecValue with
72  // value from backedge.
73  if (Cond.AddRecSCEV && isa<PHINode>(Cond.AddRecValue)) {
74  PHINode *PN = cast<PHINode>(Cond.AddRecValue);
75  Cond.NonPHIAddRecValue = PN->getIncomingValueForBlock(L.getLoopLatch());
76  }
77  }
78 }
79 
80 static bool calculateUpperBound(const Loop &L, ScalarEvolution &SE,
81  ConditionInfo &Cond, bool IsExitCond) {
82  if (IsExitCond) {
83  const SCEV *ExitCount = SE.getExitCount(&L, Cond.ICmp->getParent());
84  if (isa<SCEVCouldNotCompute>(ExitCount))
85  return false;
86 
87  Cond.BoundSCEV = ExitCount;
88  return true;
89  }
90 
91  // For non-exit condtion, if pred is LT, keep existing bound.
92  if (Cond.Pred == ICmpInst::ICMP_SLT || Cond.Pred == ICmpInst::ICMP_ULT)
93  return true;
94 
95  // For non-exit condition, if pre is LE, try to convert it to LT.
96  // Range Range
97  // AddRec <= Bound --> AddRec < Bound + 1
98  if (Cond.Pred != ICmpInst::ICMP_ULE && Cond.Pred != ICmpInst::ICMP_SLE)
99  return false;
100 
101  if (IntegerType *BoundSCEVIntType =
102  dyn_cast<IntegerType>(Cond.BoundSCEV->getType())) {
103  unsigned BitWidth = BoundSCEVIntType->getBitWidth();
104  APInt Max = ICmpInst::isSigned(Cond.Pred)
107  const SCEV *MaxSCEV = SE.getConstant(Max);
108  // Check Bound < INT_MAX
109  ICmpInst::Predicate Pred =
111  if (SE.isKnownPredicate(Pred, Cond.BoundSCEV, MaxSCEV)) {
112  const SCEV *BoundPlusOneSCEV =
113  SE.getAddExpr(Cond.BoundSCEV, SE.getOne(BoundSCEVIntType));
114  Cond.BoundSCEV = BoundPlusOneSCEV;
115  Cond.Pred = Pred;
116  return true;
117  }
118  }
119 
120  // ToDo: Support ICMP_NE/EQ.
121 
122  return false;
123 }
124 
125 static bool hasProcessableCondition(const Loop &L, ScalarEvolution &SE,
126  ICmpInst *ICmp, ConditionInfo &Cond,
127  bool IsExitCond) {
128  analyzeICmp(SE, ICmp, Cond, L);
129 
130  // The BoundSCEV should be evaluated at loop entry.
131  if (!SE.isAvailableAtLoopEntry(Cond.BoundSCEV, &L))
132  return false;
133 
134  // Allowed AddRec as induction variable.
135  if (!Cond.AddRecSCEV)
136  return false;
137 
138  if (!Cond.AddRecSCEV->isAffine())
139  return false;
140 
141  const SCEV *StepRecSCEV = Cond.AddRecSCEV->getStepRecurrence(SE);
142  // Allowed constant step.
143  if (!isa<SCEVConstant>(StepRecSCEV))
144  return false;
145 
146  ConstantInt *StepCI = cast<SCEVConstant>(StepRecSCEV)->getValue();
147  // Allowed positive step for now.
148  // TODO: Support negative step.
149  if (StepCI->isNegative() || StepCI->isZero())
150  return false;
151 
152  // Calculate upper bound.
153  if (!calculateUpperBound(L, SE, Cond, IsExitCond))
154  return false;
155 
156  return true;
157 }
158 
159 static bool isProcessableCondBI(const ScalarEvolution &SE,
160  const BranchInst *BI) {
161  BasicBlock *TrueSucc = nullptr;
162  BasicBlock *FalseSucc = nullptr;
163  ICmpInst::Predicate Pred;
164  Value *LHS, *RHS;
165  if (!match(BI, m_Br(m_ICmp(Pred, m_Value(LHS), m_Value(RHS)),
166  m_BasicBlock(TrueSucc), m_BasicBlock(FalseSucc))))
167  return false;
168 
169  if (!SE.isSCEVable(LHS->getType()))
170  return false;
171  assert(SE.isSCEVable(RHS->getType()) && "Expected RHS's type is SCEVable");
172 
173  if (TrueSucc == FalseSucc)
174  return false;
175 
176  return true;
177 }
178 
179 static bool canSplitLoopBound(const Loop &L, const DominatorTree &DT,
180  ScalarEvolution &SE, ConditionInfo &Cond) {
181  // Skip function with optsize.
182  if (L.getHeader()->getParent()->hasOptSize())
183  return false;
184 
185  // Split only innermost loop.
186  if (!L.isInnermost())
187  return false;
188 
189  // Check loop is in simplified form.
190  if (!L.isLoopSimplifyForm())
191  return false;
192 
193  // Check loop is in LCSSA form.
194  if (!L.isLCSSAForm(DT))
195  return false;
196 
197  // Skip loop that cannot be cloned.
198  if (!L.isSafeToClone())
199  return false;
200 
201  BasicBlock *ExitingBB = L.getExitingBlock();
202  // Assumed only one exiting block.
203  if (!ExitingBB)
204  return false;
205 
206  BranchInst *ExitingBI = dyn_cast<BranchInst>(ExitingBB->getTerminator());
207  if (!ExitingBI)
208  return false;
209 
210  // Allowed only conditional branch with ICmp.
211  if (!isProcessableCondBI(SE, ExitingBI))
212  return false;
213 
214  // Check the condition is processable.
215  ICmpInst *ICmp = cast<ICmpInst>(ExitingBI->getCondition());
216  if (!hasProcessableCondition(L, SE, ICmp, Cond, /*IsExitCond*/ true))
217  return false;
218 
219  Cond.BI = ExitingBI;
220  return true;
221 }
222 
223 static bool isProfitableToTransform(const Loop &L, const BranchInst *BI) {
224  // If the conditional branch splits a loop into two halves, we could
225  // generally say it is profitable.
226  //
227  // ToDo: Add more profitable cases here.
228 
229  // Check this branch causes diamond CFG.
230  BasicBlock *Succ0 = BI->getSuccessor(0);
231  BasicBlock *Succ1 = BI->getSuccessor(1);
232 
233  BasicBlock *Succ0Succ = Succ0->getSingleSuccessor();
234  BasicBlock *Succ1Succ = Succ1->getSingleSuccessor();
235  if (!Succ0Succ || !Succ1Succ || Succ0Succ != Succ1Succ)
236  return false;
237 
238  // ToDo: Calculate each successor's instruction cost.
239 
240  return true;
241 }
242 
244  ConditionInfo &ExitingCond,
245  ConditionInfo &SplitCandidateCond) {
246  for (auto *BB : L.blocks()) {
247  // Skip condition of backedge.
248  if (L.getLoopLatch() == BB)
249  continue;
250 
251  auto *BI = dyn_cast<BranchInst>(BB->getTerminator());
252  if (!BI)
253  continue;
254 
255  // Check conditional branch with ICmp.
256  if (!isProcessableCondBI(SE, BI))
257  continue;
258 
259  // Skip loop invariant condition.
260  if (L.isLoopInvariant(BI->getCondition()))
261  continue;
262 
263  // Check the condition is processable.
264  ICmpInst *ICmp = cast<ICmpInst>(BI->getCondition());
265  if (!hasProcessableCondition(L, SE, ICmp, SplitCandidateCond,
266  /*IsExitCond*/ false))
267  continue;
268 
269  if (ExitingCond.BoundSCEV->getType() !=
270  SplitCandidateCond.BoundSCEV->getType())
271  continue;
272 
273  // After transformation, we assume the split condition of the pre-loop is
274  // always true. In order to guarantee it, we need to check the start value
275  // of the split cond AddRec satisfies the split condition.
276  if (!SE.isLoopEntryGuardedByCond(&L, SplitCandidateCond.Pred,
277  SplitCandidateCond.AddRecSCEV->getStart(),
278  SplitCandidateCond.BoundSCEV))
279  continue;
280 
281  SplitCandidateCond.BI = BI;
282  return BI;
283  }
284 
285  return nullptr;
286 }
287 
288 static bool splitLoopBound(Loop &L, DominatorTree &DT, LoopInfo &LI,
289  ScalarEvolution &SE, LPMUpdater &U) {
290  ConditionInfo SplitCandidateCond;
291  ConditionInfo ExitingCond;
292 
293  // Check we can split this loop's bound.
294  if (!canSplitLoopBound(L, DT, SE, ExitingCond))
295  return false;
296 
297  if (!findSplitCandidate(L, SE, ExitingCond, SplitCandidateCond))
298  return false;
299 
300  if (!isProfitableToTransform(L, SplitCandidateCond.BI))
301  return false;
302 
303  // Now, we have a split candidate. Let's build a form as below.
304  // +--------------------+
305  // | preheader |
306  // | set up newbound |
307  // +--------------------+
308  // | /----------------\
309  // +--------v----v------+ |
310  // | header |---\ |
311  // | with true condition| | |
312  // +--------------------+ | |
313  // | | |
314  // +--------v-----------+ | |
315  // | if.then.BB | | |
316  // +--------------------+ | |
317  // | | |
318  // +--------v-----------<---/ |
319  // | latch >----------/
320  // | with newbound |
321  // +--------------------+
322  // |
323  // +--------v-----------+
324  // | preheader2 |--------------\
325  // | if (AddRec i != | |
326  // | org bound) | |
327  // +--------------------+ |
328  // | /----------------\ |
329  // +--------v----v------+ | |
330  // | header2 |---\ | |
331  // | conditional branch | | | |
332  // |with false condition| | | |
333  // +--------------------+ | | |
334  // | | | |
335  // +--------v-----------+ | | |
336  // | if.then.BB2 | | | |
337  // +--------------------+ | | |
338  // | | | |
339  // +--------v-----------<---/ | |
340  // | latch2 >----------/ |
341  // | with org bound | |
342  // +--------v-----------+ |
343  // | |
344  // | +---------------+ |
345  // +--> exit <-------/
346  // +---------------+
347 
348  // Let's create post loop.
349  SmallVector<BasicBlock *, 8> PostLoopBlocks;
350  Loop *PostLoop;
351  ValueToValueMapTy VMap;
352  BasicBlock *PreHeader = L.getLoopPreheader();
353  BasicBlock *SplitLoopPH = SplitEdge(PreHeader, L.getHeader(), &DT, &LI);
354  PostLoop = cloneLoopWithPreheader(L.getExitBlock(), SplitLoopPH, &L, VMap,
355  ".split", &LI, &DT, PostLoopBlocks);
356  remapInstructionsInBlocks(PostLoopBlocks, VMap);
357 
358  BasicBlock *PostLoopPreHeader = PostLoop->getLoopPreheader();
359  IRBuilder<> Builder(&PostLoopPreHeader->front());
360 
361  // Update phi nodes in header of post-loop.
362  bool isExitingLatch =
363  (L.getExitingBlock() == L.getLoopLatch()) ? true : false;
364  Value *ExitingCondLCSSAPhi = nullptr;
365  for (PHINode &PN : L.getHeader()->phis()) {
366  // Create LCSSA phi node in preheader of post-loop.
367  PHINode *LCSSAPhi =
368  Builder.CreatePHI(PN.getType(), 1, PN.getName() + ".lcssa");
369  LCSSAPhi->setDebugLoc(PN.getDebugLoc());
370  // If the exiting block is loop latch, the phi does not have the update at
371  // last iteration. In this case, update lcssa phi with value from backedge.
372  LCSSAPhi->addIncoming(
373  isExitingLatch ? PN.getIncomingValueForBlock(L.getLoopLatch()) : &PN,
374  L.getExitingBlock());
375 
376  // Update the start value of phi node in post-loop with the LCSSA phi node.
377  PHINode *PostLoopPN = cast<PHINode>(VMap[&PN]);
378  PostLoopPN->setIncomingValueForBlock(PostLoopPreHeader, LCSSAPhi);
379 
380  // Find PHI with exiting condition from pre-loop. The PHI should be
381  // SCEVAddRecExpr and have same incoming value from backedge with
382  // ExitingCond.
383  if (!SE.isSCEVable(PN.getType()))
384  continue;
385 
386  const SCEVAddRecExpr *PhiSCEV = dyn_cast<SCEVAddRecExpr>(SE.getSCEV(&PN));
387  if (PhiSCEV && ExitingCond.NonPHIAddRecValue ==
388  PN.getIncomingValueForBlock(L.getLoopLatch()))
389  ExitingCondLCSSAPhi = LCSSAPhi;
390  }
391 
392  // Add conditional branch to check we can skip post-loop in its preheader.
393  Instruction *OrigBI = PostLoopPreHeader->getTerminator();
395  Value *Cond =
396  Builder.CreateICmp(Pred, ExitingCondLCSSAPhi, ExitingCond.BoundValue);
397  Builder.CreateCondBr(Cond, PostLoop->getHeader(), PostLoop->getExitBlock());
398  OrigBI->eraseFromParent();
399 
400  // Create new loop bound and add it into preheader of pre-loop.
401  const SCEV *NewBoundSCEV = ExitingCond.BoundSCEV;
402  const SCEV *SplitBoundSCEV = SplitCandidateCond.BoundSCEV;
403  NewBoundSCEV = ICmpInst::isSigned(ExitingCond.Pred)
404  ? SE.getSMinExpr(NewBoundSCEV, SplitBoundSCEV)
405  : SE.getUMinExpr(NewBoundSCEV, SplitBoundSCEV);
406 
407  SCEVExpander Expander(
408  SE, L.getHeader()->getParent()->getParent()->getDataLayout(), "split");
409  Instruction *InsertPt = SplitLoopPH->getTerminator();
410  Value *NewBoundValue =
411  Expander.expandCodeFor(NewBoundSCEV, NewBoundSCEV->getType(), InsertPt);
412  NewBoundValue->setName("new.bound");
413 
414  // Replace exiting bound value of pre-loop NewBound.
415  ExitingCond.ICmp->setOperand(1, NewBoundValue);
416 
417  // Replace SplitCandidateCond.BI's condition of pre-loop by True.
418  LLVMContext &Context = PreHeader->getContext();
419  SplitCandidateCond.BI->setCondition(ConstantInt::getTrue(Context));
420 
421  // Replace cloned SplitCandidateCond.BI's condition in post-loop by False.
422  BranchInst *ClonedSplitCandidateBI =
423  cast<BranchInst>(VMap[SplitCandidateCond.BI]);
424  ClonedSplitCandidateBI->setCondition(ConstantInt::getFalse(Context));
425 
426  // Replace exit branch target of pre-loop by post-loop's preheader.
427  if (L.getExitBlock() == ExitingCond.BI->getSuccessor(0))
428  ExitingCond.BI->setSuccessor(0, PostLoopPreHeader);
429  else
430  ExitingCond.BI->setSuccessor(1, PostLoopPreHeader);
431 
432  // Update phi node in exit block of post-loop.
433  Builder.SetInsertPoint(&PostLoopPreHeader->front());
434  for (PHINode &PN : PostLoop->getExitBlock()->phis()) {
435  for (auto i : seq<int>(0, PN.getNumOperands())) {
436  // Check incoming block is pre-loop's exiting block.
437  if (PN.getIncomingBlock(i) == L.getExitingBlock()) {
438  Value *IncomingValue = PN.getIncomingValue(i);
439 
440  // Create LCSSA phi node for incoming value.
441  PHINode *LCSSAPhi =
442  Builder.CreatePHI(PN.getType(), 1, PN.getName() + ".lcssa");
443  LCSSAPhi->setDebugLoc(PN.getDebugLoc());
444  LCSSAPhi->addIncoming(IncomingValue, PN.getIncomingBlock(i));
445 
446  // Replace pre-loop's exiting block by post-loop's preheader.
447  PN.setIncomingBlock(i, PostLoopPreHeader);
448  // Replace incoming value by LCSSAPhi.
449  PN.setIncomingValue(i, LCSSAPhi);
450  // Add a new incoming value with post-loop's exiting block.
451  PN.addIncoming(VMap[IncomingValue], PostLoop->getExitingBlock());
452  }
453  }
454  }
455 
456  // Update dominator tree.
457  DT.changeImmediateDominator(PostLoopPreHeader, L.getExitingBlock());
458  DT.changeImmediateDominator(PostLoop->getExitBlock(), PostLoopPreHeader);
459 
460  // Invalidate cached SE information.
461  SE.forgetLoop(&L);
462 
463  // Canonicalize loops.
464  simplifyLoop(&L, &DT, &LI, &SE, nullptr, nullptr, true);
465  simplifyLoop(PostLoop, &DT, &LI, &SE, nullptr, nullptr, true);
466 
467  // Add new post-loop to loop pass manager.
468  U.addSiblingLoops(PostLoop);
469 
470  return true;
471 }
472 
475  LPMUpdater &U) {
476  Function &F = *L.getHeader()->getParent();
477  (void)F;
478 
479  LLVM_DEBUG(dbgs() << "Spliting bound of loop in " << F.getName() << ": " << L
480  << "\n");
481 
482  if (!splitLoopBound(L, AR.DT, AR.LI, AR.SE, U))
483  return PreservedAnalyses::all();
484 
486  AR.LI.verify(AR.DT);
487 
489 }
490 
491 } // 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:152
llvm::Loop::isLoopInvariant
bool isLoopInvariant(const Value *V) const
Return true if the specified value is loop invariant.
Definition: LoopInfo.cpp:60
llvm::CmpInst::getSwappedPredicate
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Definition: InstrTypes.h:850
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:11413
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
LoopSimplify.h
llvm::LoopBase::getExitBlock
BlockT * getExitBlock() const
If getExitBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:107
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:720
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:940
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:104
ScalarEvolutionExpander.h
llvm::Function
Definition: Function.h:60
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:547
llvm::SCEVExpander
This class uses information about analyze scalars to rewrite expressions in canonical form.
Definition: ScalarEvolutionExpander.h:50
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:1199
llvm::LoopInfoBase::verify
void verify(const DominatorTreeBase< BlockT, false > &DomTree) const
Definition: LoopInfoImpl.h:699
llvm::APInt::getMaxValue
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
Definition: APInt.h:186
llvm::IRBuilder<>
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:449
llvm::CmpInst::ICMP_NE
@ ICMP_NE
not equal
Definition: InstrTypes.h:742
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
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:278
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:1731
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:51
llvm::BasicBlock::getSingleSuccessor
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
Definition: BasicBlock.cpp:315
llvm::CmpInst::ICMP_SLE
@ ICMP_SLE
signed less or equal
Definition: InstrTypes.h:750
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
LoopBoundSplit.h
llvm::LoopStandardAnalysisResults::DT
DominatorTree & DT
Definition: LoopAnalysisManager.h:54
llvm::Sched::Fast
@ Fast
Definition: TargetLowering.h:104
Sequence.h
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
LoopAnalysisManager.h
Context
LLVMContext & Context
Definition: NVVMIntrRange.cpp:66
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:243
LHS
Value * LHS
Definition: X86PartialReduction.cpp:75
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:649
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:746
llvm::remapInstructionsInBlocks
void remapInstructionsInBlocks(const SmallVectorImpl< BasicBlock * > &Blocks, ValueToValueMapTy &VMap)
Remaps instructions in Blocks using the mapping in VMap.
Definition: CloneFunction.cpp:926
llvm::canSplitLoopBound
static bool canSplitLoopBound(const Loop &L, const DominatorTree &DT, ScalarEvolution &SE, ConditionInfo &Cond)
Definition: LoopBoundSplit.cpp:179
llvm::LoopBase::blocks
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:195
llvm::PHINode::getIncomingValueForBlock
Value * getIncomingValueForBlock(const BasicBlock *BB) const
Definition: Instructions.h:2884
llvm::IntegerType
Class to represent integer types.
Definition: DerivedTypes.h:40
llvm::Instruction
Definition: Instruction.h:42
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:10757
llvm::BranchInst::setCondition
void setCondition(Value *V)
Definition: Instructions.h:3220
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:364
llvm::Value::setName
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:375
llvm::splitLoopBound
static bool splitLoopBound(Loop &L, DominatorTree &DT, LoopInfo &LI, ScalarEvolution &SE, LPMUpdater &U)
Definition: LoopBoundSplit.cpp:288
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:48
PatternMatch.h
LoopInfo.h
llvm::BranchInst::getCondition
Value * getCondition() const
Definition: Instructions.h:3215
llvm::ScalarEvolution::getSCEV
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
Definition: ScalarEvolution.cpp:4442
llvm::hasProcessableCondition
static bool hasProcessableCondition(const Loop &L, ScalarEvolution &SE, ICmpInst *ICmp, ConditionInfo &Cond, bool IsExitCond)
Definition: LoopBoundSplit.cpp:125
llvm::getLoopPassPreservedAnalyses
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
Definition: LoopAnalysisManager.cpp:138
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:473
llvm::SCEV
This class represents an analyzed expression in the program.
Definition: ScalarEvolution.h:75
llvm::isProcessableCondBI
static bool isProcessableCondBI(const ScalarEvolution &SE, const BranchInst *BI)
Definition: LoopBoundSplit.cpp:159
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:81
llvm::ICmpInst
This instruction compares its operands according to the predicate given to the constructor.
Definition: Instructions.h:1186
llvm::GlobalValue::getParent
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:652
llvm::LPMUpdater
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
Definition: LoopPassManager.h:262
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2849
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
Cloning.h
llvm::LoopBase::getLoopPreheader
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:183
llvm::Instruction::setDebugLoc
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:351
llvm::LoopBase::getLoopLatch
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:232
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:853
llvm::PHINode::setIncomingValueForBlock
void setIncomingValueForBlock(const BasicBlock *BB, Value *V)
Set every incoming value(s) for block BB to V.
Definition: Instructions.h:2891
llvm::CmpInst::BAD_ICMP_PREDICATE
@ BAD_ICMP_PREDICATE
Definition: InstrTypes.h:753
LoopPassManager.h
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:651
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:749
llvm::LoopInfo
Definition: LoopInfo.h:1108
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:138
llvm::ScalarEvolution::getConstant
const SCEV * getConstant(ConstantInt *V)
Definition: ScalarEvolution.cpp:472
llvm::CmpInst::ICMP_ULT
@ ICMP_ULT
unsigned less than
Definition: InstrTypes.h:745
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:55
llvm::ScalarEvolution::getUMinExpr
const SCEV * getUMinExpr(const SCEV *LHS, const SCEV *RHS, bool Sequential=false)
Definition: ScalarEvolution.cpp:4246
llvm::calculateUpperBound
static bool calculateUpperBound(const Loop &L, ScalarEvolution &SE, ConditionInfo &Cond, bool IsExitCond)
Definition: LoopBoundSplit.cpp:80
llvm::ValueMap< const Value *, WeakTrackingVH >
llvm::ConstantInt::getFalse
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:834
llvm::Function::hasOptSize
bool hasOptSize() const
Optimize this function for size (-Os) or minimum size (-Oz).
Definition: Function.h:645
llvm::BasicBlock::front
const Instruction & front() const
Definition: BasicBlock.h:318
llvm::BasicBlock::getContext
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:35
llvm::LoopBase::isInnermost
bool isInnermost() const
Return true if the loop does not contain any (natural) loops.
Definition: LoopInfo.h:182
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:598
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:8372
llvm::ConstantInt::getTrue
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:827
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
llvm::SCEVAddRecExpr
This node represents a polynomial recurrence on the trip count of the specified loop.
Definition: ScalarEvolutionExpressions.h:342
llvm::BitWidth
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:147
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:105
llvm::isProfitableToTransform
static bool isProfitableToTransform(const Loop &L, const BranchInst *BI)
Definition: LoopBoundSplit.cpp:223
llvm::ScalarEvolution::isSCEVable
bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
Definition: ScalarEvolution.cpp:4328
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
llvm::CmpInst::isSigned
bool isSigned() const
Definition: InstrTypes.h:948
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:708
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:2488
llvm::LoopStandardAnalysisResults::SE
ScalarEvolution & SE
Definition: LoopAnalysisManager.h:56
llvm::analyzeICmp
static void analyzeICmp(ScalarEvolution &SE, ICmpInst *ICmp, ConditionInfo &Cond, const Loop &L)
Definition: LoopBoundSplit.cpp:51
ScalarEvolutionExpressions.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:1394
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:2699
llvm::BasicBlock::getTerminator
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.h:119
llvm::Loop::isLCSSAForm
bool isLCSSAForm(const DominatorTree &DT, bool IgnoreTokens=true) const
Return true if the Loop is in LCSSA form.
Definition: LoopInfo.cpp:462
llvm::Module::getDataLayout
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.cpp:399
llvm::SCEV::getType
Type * getType() const
Return the LLVM type of this SCEV expression.
Definition: ScalarEvolution.cpp:403
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
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:2493
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:168
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3134
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:330
BasicBlockUtils.h
llvm::ScalarEvolution::getSMinExpr
const SCEV * getSMinExpr(const SCEV *LHS, const SCEV *RHS)
Definition: ScalarEvolution.cpp:4236
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:8222
llvm::BranchInst::getSuccessor
BasicBlock * getSuccessor(unsigned i) const
Definition: Instructions.h:3227