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  /// Bound llvm value
44  Value *BoundValue;
45  /// AddRec SCEV
46  const SCEV *AddRecSCEV;
47  /// Bound SCEV
48  const SCEV *BoundSCEV;
49 
50  ConditionInfo()
51  : BI(nullptr), ICmp(nullptr), Pred(ICmpInst::BAD_ICMP_PREDICATE),
52  AddRecValue(nullptr), BoundValue(nullptr), AddRecSCEV(nullptr),
53  BoundSCEV(nullptr) {}
54 };
55 } // namespace
56 
57 static void analyzeICmp(ScalarEvolution &SE, ICmpInst *ICmp,
58  ConditionInfo &Cond) {
59  Cond.ICmp = ICmp;
60  if (match(ICmp, m_ICmp(Cond.Pred, m_Value(Cond.AddRecValue),
61  m_Value(Cond.BoundValue)))) {
62  Cond.AddRecSCEV = SE.getSCEV(Cond.AddRecValue);
63  Cond.BoundSCEV = SE.getSCEV(Cond.BoundValue);
64  // Locate AddRec in LHSSCEV and Bound in RHSSCEV.
65  if (isa<SCEVAddRecExpr>(Cond.BoundSCEV) &&
66  !isa<SCEVAddRecExpr>(Cond.AddRecSCEV)) {
67  std::swap(Cond.AddRecValue, Cond.BoundValue);
68  std::swap(Cond.AddRecSCEV, Cond.BoundSCEV);
70  }
71  }
72 }
73 
74 static bool calculateUpperBound(const Loop &L, ScalarEvolution &SE,
75  ConditionInfo &Cond, bool IsExitCond) {
76  if (IsExitCond) {
77  const SCEV *ExitCount = SE.getExitCount(&L, Cond.ICmp->getParent());
78  if (isa<SCEVCouldNotCompute>(ExitCount))
79  return false;
80 
81  Cond.BoundSCEV = ExitCount;
82  return true;
83  }
84 
85  // For non-exit condtion, if pred is LT, keep existing bound.
86  if (Cond.Pred == ICmpInst::ICMP_SLT || Cond.Pred == ICmpInst::ICMP_ULT)
87  return true;
88 
89  // For non-exit condition, if pre is LE, try to convert it to LT.
90  // Range Range
91  // AddRec <= Bound --> AddRec < Bound + 1
92  if (Cond.Pred != ICmpInst::ICMP_ULE && Cond.Pred != ICmpInst::ICMP_SLE)
93  return false;
94 
95  if (IntegerType *BoundSCEVIntType =
96  dyn_cast<IntegerType>(Cond.BoundSCEV->getType())) {
97  unsigned BitWidth = BoundSCEVIntType->getBitWidth();
98  APInt Max = ICmpInst::isSigned(Cond.Pred)
101  const SCEV *MaxSCEV = SE.getConstant(Max);
102  // Check Bound < INT_MAX
103  ICmpInst::Predicate Pred =
105  if (SE.isKnownPredicate(Pred, Cond.BoundSCEV, MaxSCEV)) {
106  const SCEV *BoundPlusOneSCEV =
107  SE.getAddExpr(Cond.BoundSCEV, SE.getOne(BoundSCEVIntType));
108  Cond.BoundSCEV = BoundPlusOneSCEV;
109  Cond.Pred = Pred;
110  return true;
111  }
112  }
113 
114  // ToDo: Support ICMP_NE/EQ.
115 
116  return false;
117 }
118 
119 static bool hasProcessableCondition(const Loop &L, ScalarEvolution &SE,
120  ICmpInst *ICmp, ConditionInfo &Cond,
121  bool IsExitCond) {
122  analyzeICmp(SE, ICmp, Cond);
123 
124  // The BoundSCEV should be evaluated at loop entry.
125  if (!SE.isAvailableAtLoopEntry(Cond.BoundSCEV, &L))
126  return false;
127 
128  const SCEVAddRecExpr *AddRecSCEV = dyn_cast<SCEVAddRecExpr>(Cond.AddRecSCEV);
129  // Allowed AddRec as induction variable.
130  if (!AddRecSCEV)
131  return false;
132 
133  if (!AddRecSCEV->isAffine())
134  return false;
135 
136  const SCEV *StepRecSCEV = AddRecSCEV->getStepRecurrence(SE);
137  // Allowed constant step.
138  if (!isa<SCEVConstant>(StepRecSCEV))
139  return false;
140 
141  ConstantInt *StepCI = cast<SCEVConstant>(StepRecSCEV)->getValue();
142  // Allowed positive step for now.
143  // TODO: Support negative step.
144  if (StepCI->isNegative() || StepCI->isZero())
145  return false;
146 
147  // Calculate upper bound.
148  if (!calculateUpperBound(L, SE, Cond, IsExitCond))
149  return false;
150 
151  return true;
152 }
153 
154 static bool isProcessableCondBI(const ScalarEvolution &SE,
155  const BranchInst *BI) {
156  BasicBlock *TrueSucc = nullptr;
157  BasicBlock *FalseSucc = nullptr;
158  ICmpInst::Predicate Pred;
159  Value *LHS, *RHS;
160  if (!match(BI, m_Br(m_ICmp(Pred, m_Value(LHS), m_Value(RHS)),
161  m_BasicBlock(TrueSucc), m_BasicBlock(FalseSucc))))
162  return false;
163 
164  if (!SE.isSCEVable(LHS->getType()))
165  return false;
166  assert(SE.isSCEVable(RHS->getType()) && "Expected RHS's type is SCEVable");
167 
168  if (TrueSucc == FalseSucc)
169  return false;
170 
171  return true;
172 }
173 
174 static bool canSplitLoopBound(const Loop &L, const DominatorTree &DT,
175  ScalarEvolution &SE, ConditionInfo &Cond) {
176  // Skip function with optsize.
177  if (L.getHeader()->getParent()->hasOptSize())
178  return false;
179 
180  // Split only innermost loop.
181  if (!L.isInnermost())
182  return false;
183 
184  // Check loop is in simplified form.
185  if (!L.isLoopSimplifyForm())
186  return false;
187 
188  // Check loop is in LCSSA form.
189  if (!L.isLCSSAForm(DT))
190  return false;
191 
192  // Skip loop that cannot be cloned.
193  if (!L.isSafeToClone())
194  return false;
195 
196  BasicBlock *ExitingBB = L.getExitingBlock();
197  // Assumed only one exiting block.
198  if (!ExitingBB)
199  return false;
200 
201  BranchInst *ExitingBI = dyn_cast<BranchInst>(ExitingBB->getTerminator());
202  if (!ExitingBI)
203  return false;
204 
205  // Allowed only conditional branch with ICmp.
206  if (!isProcessableCondBI(SE, ExitingBI))
207  return false;
208 
209  // Check the condition is processable.
210  ICmpInst *ICmp = cast<ICmpInst>(ExitingBI->getCondition());
211  if (!hasProcessableCondition(L, SE, ICmp, Cond, /*IsExitCond*/ true))
212  return false;
213 
214  Cond.BI = ExitingBI;
215  return true;
216 }
217 
218 static bool isProfitableToTransform(const Loop &L, const BranchInst *BI) {
219  // If the conditional branch splits a loop into two halves, we could
220  // generally say it is profitable.
221  //
222  // ToDo: Add more profitable cases here.
223 
224  // Check this branch causes diamond CFG.
225  BasicBlock *Succ0 = BI->getSuccessor(0);
226  BasicBlock *Succ1 = BI->getSuccessor(1);
227 
228  BasicBlock *Succ0Succ = Succ0->getSingleSuccessor();
229  BasicBlock *Succ1Succ = Succ1->getSingleSuccessor();
230  if (!Succ0Succ || !Succ1Succ || Succ0Succ != Succ1Succ)
231  return false;
232 
233  // ToDo: Calculate each successor's instruction cost.
234 
235  return true;
236 }
237 
239  ConditionInfo &ExitingCond,
240  ConditionInfo &SplitCandidateCond) {
241  for (auto *BB : L.blocks()) {
242  // Skip condition of backedge.
243  if (L.getLoopLatch() == BB)
244  continue;
245 
246  auto *BI = dyn_cast<BranchInst>(BB->getTerminator());
247  if (!BI)
248  continue;
249 
250  // Check conditional branch with ICmp.
251  if (!isProcessableCondBI(SE, BI))
252  continue;
253 
254  // Skip loop invariant condition.
255  if (L.isLoopInvariant(BI->getCondition()))
256  continue;
257 
258  // Check the condition is processable.
259  ICmpInst *ICmp = cast<ICmpInst>(BI->getCondition());
260  if (!hasProcessableCondition(L, SE, ICmp, SplitCandidateCond,
261  /*IsExitCond*/ false))
262  continue;
263 
264  if (ExitingCond.BoundSCEV->getType() !=
265  SplitCandidateCond.BoundSCEV->getType())
266  continue;
267 
268  // After transformation, we assume the split condition of the pre-loop is
269  // always true. In order to guarantee it, we need to check the start value
270  // of the split cond AddRec satisfies the split condition.
271  const SCEV *SplitAddRecStartSCEV =
272  cast<SCEVAddRecExpr>(SplitCandidateCond.AddRecSCEV)->getStart();
273  if (!SE.isKnownPredicate(SplitCandidateCond.Pred, SplitAddRecStartSCEV,
274  SplitCandidateCond.BoundSCEV))
275  continue;
276 
277  SplitCandidateCond.BI = BI;
278  return BI;
279  }
280 
281  return nullptr;
282 }
283 
284 static bool splitLoopBound(Loop &L, DominatorTree &DT, LoopInfo &LI,
285  ScalarEvolution &SE, LPMUpdater &U) {
286  ConditionInfo SplitCandidateCond;
287  ConditionInfo ExitingCond;
288 
289  // Check we can split this loop's bound.
290  if (!canSplitLoopBound(L, DT, SE, ExitingCond))
291  return false;
292 
293  if (!findSplitCandidate(L, SE, ExitingCond, SplitCandidateCond))
294  return false;
295 
296  if (!isProfitableToTransform(L, SplitCandidateCond.BI))
297  return false;
298 
299  // Now, we have a split candidate. Let's build a form as below.
300  // +--------------------+
301  // | preheader |
302  // | set up newbound |
303  // +--------------------+
304  // | /----------------\
305  // +--------v----v------+ |
306  // | header |---\ |
307  // | with true condition| | |
308  // +--------------------+ | |
309  // | | |
310  // +--------v-----------+ | |
311  // | if.then.BB | | |
312  // +--------------------+ | |
313  // | | |
314  // +--------v-----------<---/ |
315  // | latch >----------/
316  // | with newbound |
317  // +--------------------+
318  // |
319  // +--------v-----------+
320  // | preheader2 |--------------\
321  // | if (AddRec i != | |
322  // | org bound) | |
323  // +--------------------+ |
324  // | /----------------\ |
325  // +--------v----v------+ | |
326  // | header2 |---\ | |
327  // | conditional branch | | | |
328  // |with false condition| | | |
329  // +--------------------+ | | |
330  // | | | |
331  // +--------v-----------+ | | |
332  // | if.then.BB2 | | | |
333  // +--------------------+ | | |
334  // | | | |
335  // +--------v-----------<---/ | |
336  // | latch2 >----------/ |
337  // | with org bound | |
338  // +--------v-----------+ |
339  // | |
340  // | +---------------+ |
341  // +--> exit <-------/
342  // +---------------+
343 
344  // Let's create post loop.
345  SmallVector<BasicBlock *, 8> PostLoopBlocks;
346  Loop *PostLoop;
347  ValueToValueMapTy VMap;
348  BasicBlock *PreHeader = L.getLoopPreheader();
349  BasicBlock *SplitLoopPH = SplitEdge(PreHeader, L.getHeader(), &DT, &LI);
350  PostLoop = cloneLoopWithPreheader(L.getExitBlock(), SplitLoopPH, &L, VMap,
351  ".split", &LI, &DT, PostLoopBlocks);
352  remapInstructionsInBlocks(PostLoopBlocks, VMap);
353 
354  // Add conditional branch to check we can skip post-loop in its preheader.
355  BasicBlock *PostLoopPreHeader = PostLoop->getLoopPreheader();
356  IRBuilder<> Builder(PostLoopPreHeader);
357  Instruction *OrigBI = PostLoopPreHeader->getTerminator();
359  Value *Cond =
360  Builder.CreateICmp(Pred, ExitingCond.AddRecValue, ExitingCond.BoundValue);
361  Builder.CreateCondBr(Cond, PostLoop->getHeader(), PostLoop->getExitBlock());
362  OrigBI->eraseFromParent();
363 
364  // Create new loop bound and add it into preheader of pre-loop.
365  const SCEV *NewBoundSCEV = ExitingCond.BoundSCEV;
366  const SCEV *SplitBoundSCEV = SplitCandidateCond.BoundSCEV;
367  NewBoundSCEV = ICmpInst::isSigned(ExitingCond.Pred)
368  ? SE.getSMinExpr(NewBoundSCEV, SplitBoundSCEV)
369  : SE.getUMinExpr(NewBoundSCEV, SplitBoundSCEV);
370 
371  SCEVExpander Expander(
372  SE, L.getHeader()->getParent()->getParent()->getDataLayout(), "split");
373  Instruction *InsertPt = SplitLoopPH->getTerminator();
374  Value *NewBoundValue =
375  Expander.expandCodeFor(NewBoundSCEV, NewBoundSCEV->getType(), InsertPt);
376  NewBoundValue->setName("new.bound");
377 
378  // Replace exiting bound value of pre-loop NewBound.
379  ExitingCond.ICmp->setOperand(1, NewBoundValue);
380 
381  // Replace IV's start value of post-loop by NewBound.
382  for (PHINode &PN : L.getHeader()->phis()) {
383  // Find PHI with exiting condition from pre-loop.
384  if (SE.isSCEVable(PN.getType()) && isa<SCEVAddRecExpr>(SE.getSCEV(&PN))) {
385  for (Value *Op : PN.incoming_values()) {
386  if (Op == ExitingCond.AddRecValue) {
387  // Find cloned PHI for post-loop.
388  PHINode *PostLoopPN = cast<PHINode>(VMap[&PN]);
389  PostLoopPN->setIncomingValueForBlock(PostLoopPreHeader,
390  NewBoundValue);
391  }
392  }
393  }
394  }
395 
396  // Replace SplitCandidateCond.BI's condition of pre-loop by True.
397  LLVMContext &Context = PreHeader->getContext();
398  SplitCandidateCond.BI->setCondition(ConstantInt::getTrue(Context));
399 
400  // Replace cloned SplitCandidateCond.BI's condition in post-loop by False.
401  BranchInst *ClonedSplitCandidateBI =
402  cast<BranchInst>(VMap[SplitCandidateCond.BI]);
403  ClonedSplitCandidateBI->setCondition(ConstantInt::getFalse(Context));
404 
405  // Replace exit branch target of pre-loop by post-loop's preheader.
406  if (L.getExitBlock() == ExitingCond.BI->getSuccessor(0))
407  ExitingCond.BI->setSuccessor(0, PostLoopPreHeader);
408  else
409  ExitingCond.BI->setSuccessor(1, PostLoopPreHeader);
410 
411  // Update phi node in exit block of post-loop.
412  for (PHINode &PN : PostLoop->getExitBlock()->phis()) {
413  for (auto i : seq<int>(0, PN.getNumOperands())) {
414  // Check incoming block is pre-loop's exiting block.
415  if (PN.getIncomingBlock(i) == L.getExitingBlock()) {
416  // Replace pre-loop's exiting block by post-loop's preheader.
417  PN.setIncomingBlock(i, PostLoopPreHeader);
418  // Add a new incoming value with post-loop's exiting block.
419  PN.addIncoming(VMap[PN.getIncomingValue(i)],
420  PostLoop->getExitingBlock());
421  }
422  }
423  }
424 
425  // Update dominator tree.
426  DT.changeImmediateDominator(PostLoopPreHeader, L.getExitingBlock());
427  DT.changeImmediateDominator(PostLoop->getExitBlock(), PostLoopPreHeader);
428 
429  // Invalidate cached SE information.
430  SE.forgetLoop(&L);
431 
432  // Canonicalize loops.
433  // TODO: Try to update LCSSA information according to above change.
434  formLCSSA(L, DT, &LI, &SE);
435  simplifyLoop(&L, &DT, &LI, &SE, nullptr, nullptr, true);
436  formLCSSA(*PostLoop, DT, &LI, &SE);
437  simplifyLoop(PostLoop, &DT, &LI, &SE, nullptr, nullptr, true);
438 
439  // Add new post-loop to loop pass manager.
440  U.addSiblingLoops(PostLoop);
441 
442  return true;
443 }
444 
447  LPMUpdater &U) {
448  Function &F = *L.getHeader()->getParent();
449  (void)F;
450 
451  LLVM_DEBUG(dbgs() << "Spliting bound of loop in " << F.getName() << ": " << L
452  << "\n");
453 
454  if (!splitLoopBound(L, AR.DT, AR.LI, AR.SE, U))
455  return PreservedAnalyses::all();
456 
458  AR.LI.verify(AR.DT);
459 
461 }
462 
463 } // 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::formLCSSA
bool formLCSSA(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)
Put loop into LCSSA form.
Definition: LCSSA.cpp:336
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:836
llvm
---------------------— PointerInfo ------------------------------------—
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: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:801
llvm::SCEVAddRecExpr::isAffine
bool isAffine() const
Return true if this represents an expression A + B*x where A and B are loop invariant values.
Definition: ScalarEvolutionExpressions.h:379
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:61
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:63
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:461
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: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:275
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:1741
llvm::APInt::getSignedMaxValue
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
Definition: APInt.h:191
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:294
llvm::CmpInst::ICMP_SLE
@ ICMP_SLE
signed less or equal
Definition: InstrTypes.h:750
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
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
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:238
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:629
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:787
llvm::canSplitLoopBound
static bool canSplitLoopBound(const Loop &L, const DominatorTree &DT, ScalarEvolution &SE, ConditionInfo &Cond)
Definition: LoopBoundSplit.cpp:174
llvm::LoopBase::blocks
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:178
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:9905
llvm::BranchInst::setCondition
void setCondition(Value *V)
Definition: Instructions.h:3154
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:284
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:3149
llvm::ScalarEvolution::getSCEV
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
Definition: ScalarEvolution.cpp:4066
llvm::hasProcessableCondition
static bool hasProcessableCondition(const Loop &L, ScalarEvolution &SE, ICmpInst *ICmp, ConditionInfo &Cond, bool IsExitCond)
Definition: LoopBoundSplit.cpp:119
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:478
llvm::LoopBoundSplitPass::run
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
Definition: LoopBoundSplit.cpp:445
llvm::SCEV
This class represents an analyzed expression in the program.
Definition: ScalarEvolution.h:78
llvm::isProcessableCondBI
static bool isProcessableCondBI(const ScalarEvolution &SE, const BranchInst *BI)
Definition: LoopBoundSplit.cpp:154
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:1203
llvm::GlobalValue::getParent
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:572
llvm::LPMUpdater
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
Definition: LoopPassManager.h:249
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::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:3852
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:2825
llvm::CmpInst::BAD_ICMP_PREDICATE
@ BAD_ICMP_PREDICATE
Definition: InstrTypes.h:753
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:1083
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:179
llvm::ScalarEvolution::getConstant
const SCEV * getConstant(ConstantInt *V)
Definition: ScalarEvolution.cpp:446
llvm::CmpInst::ICMP_ULT
@ ICMP_ULT
unsigned less than
Definition: InstrTypes.h:745
LoopPass.h
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
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:74
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:148
llvm::ConstantInt::getFalse
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:855
llvm::Function::hasOptSize
bool hasOptSize() const
Optimize this function for size (-Os) or minimum size (-Oz).
Definition: Function.h:671
llvm::BasicBlock::getContext
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:32
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:493
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:7452
llvm::ConstantInt::getTrue
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:848
llvm::Loop::isLCSSAForm
bool isLCSSAForm(const DominatorTree &DT) const
Return true if the Loop is in LCSSA form.
Definition: LoopInfo.cpp:461
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:321
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:218
llvm::ScalarEvolution::isSCEVable
bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
Definition: ScalarEvolution.cpp:3932
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
llvm::CmpInst::isSigned
bool isSigned() const
Definition: InstrTypes.h:934
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:719
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:2414
llvm::LoopStandardAnalysisResults::SE
ScalarEvolution & SE
Definition: LoopAnalysisManager.h:57
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:1404
llvm::Loop::isSafeToClone
bool isSafeToClone() const
Return true if the loop body is safe to clone in practice.
Definition: LoopInfo.cpp:485
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:2633
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:379
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:2419
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:3068
llvm::analyzeICmp
static void analyzeICmp(ScalarEvolution &SE, ICmpInst *ICmp, ConditionInfo &Cond)
Definition: LoopBoundSplit.cpp:57
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:319
BasicBlockUtils.h
llvm::ScalarEvolution::getSMinExpr
const SCEV * getSMinExpr(const SCEV *LHS, const SCEV *RHS)
Definition: ScalarEvolution.cpp:3842
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
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:7265
llvm::BranchInst::getSuccessor
BasicBlock * getSuccessor(unsigned i) const
Definition: Instructions.h:3161
llvm::SCEVAddRecExpr::getStepRecurrence
const SCEV * getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
Definition: ScalarEvolutionExpressions.h:370