LLVM 22.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"
21
22#define DEBUG_TYPE "loop-bound-split"
23
24using namespace llvm;
25using namespace PatternMatch;
26
27namespace {
28struct ConditionInfo {
29 /// Branch instruction with this condition
30 BranchInst *BI = nullptr;
31 /// ICmp instruction with this condition
32 ICmpInst *ICmp = nullptr;
33 /// Preciate info
35 /// AddRec llvm value
36 Value *AddRecValue = nullptr;
37 /// Non PHI AddRec llvm value
38 Value *NonPHIAddRecValue;
39 /// Bound llvm value
40 Value *BoundValue = nullptr;
41 /// AddRec SCEV
42 const SCEVAddRecExpr *AddRecSCEV = nullptr;
43 /// Bound SCEV
44 const SCEV *BoundSCEV = nullptr;
45
46 ConditionInfo() = default;
47};
48} // namespace
49
50static void analyzeICmp(ScalarEvolution &SE, ICmpInst *ICmp,
51 ConditionInfo &Cond, const Loop &L) {
52 Cond.ICmp = ICmp;
53 if (match(ICmp, m_ICmp(Cond.Pred, m_Value(Cond.AddRecValue),
54 m_Value(Cond.BoundValue)))) {
55 const SCEV *AddRecSCEV = SE.getSCEV(Cond.AddRecValue);
56 const SCEV *BoundSCEV = SE.getSCEV(Cond.BoundValue);
57 const SCEVAddRecExpr *LHSAddRecSCEV = dyn_cast<SCEVAddRecExpr>(AddRecSCEV);
58 const SCEVAddRecExpr *RHSAddRecSCEV = dyn_cast<SCEVAddRecExpr>(BoundSCEV);
59 // Locate AddRec in LHSSCEV and Bound in RHSSCEV.
60 if (!LHSAddRecSCEV && RHSAddRecSCEV) {
61 std::swap(Cond.AddRecValue, Cond.BoundValue);
62 std::swap(AddRecSCEV, BoundSCEV);
64 }
65
66 Cond.AddRecSCEV = dyn_cast<SCEVAddRecExpr>(AddRecSCEV);
67 Cond.BoundSCEV = BoundSCEV;
68 Cond.NonPHIAddRecValue = Cond.AddRecValue;
69
70 // If the Cond.AddRecValue is PHI node, update Cond.NonPHIAddRecValue with
71 // value from backedge.
72 if (Cond.AddRecSCEV && isa<PHINode>(Cond.AddRecValue)) {
73 PHINode *PN = cast<PHINode>(Cond.AddRecValue);
74 Cond.NonPHIAddRecValue = PN->getIncomingValueForBlock(L.getLoopLatch());
75 }
76 }
77}
78
79static bool calculateUpperBound(const Loop &L, ScalarEvolution &SE,
80 ConditionInfo &Cond, bool IsExitCond) {
81 if (IsExitCond) {
82 const SCEV *ExitCount = SE.getExitCount(&L, Cond.ICmp->getParent());
83 if (isa<SCEVCouldNotCompute>(ExitCount))
84 return false;
85
86 Cond.BoundSCEV = ExitCount;
87 return true;
88 }
89
90 // For non-exit condtion, if pred is LT, keep existing bound.
91 if (Cond.Pred == ICmpInst::ICMP_SLT || Cond.Pred == ICmpInst::ICMP_ULT)
92 return true;
93
94 // For non-exit condition, if pre is LE, try to convert it to LT.
95 // Range Range
96 // AddRec <= Bound --> AddRec < Bound + 1
97 if (Cond.Pred != ICmpInst::ICMP_ULE && Cond.Pred != ICmpInst::ICMP_SLE)
98 return false;
99
100 if (IntegerType *BoundSCEVIntType =
101 dyn_cast<IntegerType>(Cond.BoundSCEV->getType())) {
102 unsigned BitWidth = BoundSCEVIntType->getBitWidth();
103 APInt Max = ICmpInst::isSigned(Cond.Pred)
106 const SCEV *MaxSCEV = SE.getConstant(Max);
107 // Check Bound < INT_MAX
110 if (SE.isKnownPredicate(Pred, Cond.BoundSCEV, MaxSCEV)) {
111 const SCEV *BoundPlusOneSCEV =
112 SE.getAddExpr(Cond.BoundSCEV, SE.getOne(BoundSCEVIntType));
113 Cond.BoundSCEV = BoundPlusOneSCEV;
114 Cond.Pred = Pred;
115 return true;
116 }
117 }
118
119 // ToDo: Support ICMP_NE/EQ.
120
121 return false;
122}
123
125 ICmpInst *ICmp, ConditionInfo &Cond,
126 bool IsExitCond) {
127 analyzeICmp(SE, ICmp, Cond, L);
128
129 // The BoundSCEV should be evaluated at loop entry.
130 if (!SE.isAvailableAtLoopEntry(Cond.BoundSCEV, &L))
131 return false;
132
133 // Allowed AddRec as induction variable.
134 if (!Cond.AddRecSCEV)
135 return false;
136
137 if (!Cond.AddRecSCEV->isAffine())
138 return false;
139
140 const SCEV *StepRecSCEV = Cond.AddRecSCEV->getStepRecurrence(SE);
141 // Allowed constant step.
142 if (!isa<SCEVConstant>(StepRecSCEV))
143 return false;
144
145 ConstantInt *StepCI = cast<SCEVConstant>(StepRecSCEV)->getValue();
146 // Allowed positive step for now.
147 // TODO: Support negative step.
148 if (StepCI->isNegative() || StepCI->isZero())
149 return false;
150
151 // Calculate upper bound.
152 if (!calculateUpperBound(L, SE, Cond, IsExitCond))
153 return false;
154
155 return true;
156}
157
159 const BranchInst *BI) {
160 BasicBlock *TrueSucc = nullptr;
161 BasicBlock *FalseSucc = nullptr;
162 Value *LHS, *RHS;
163 if (!match(BI, m_Br(m_ICmp(m_Value(LHS), m_Value(RHS)),
164 m_BasicBlock(TrueSucc), m_BasicBlock(FalseSucc))))
165 return false;
166
167 if (!SE.isSCEVable(LHS->getType()))
168 return false;
169 assert(SE.isSCEVable(RHS->getType()) && "Expected RHS's type is SCEVable");
170
171 if (TrueSucc == FalseSucc)
172 return false;
173
174 return true;
175}
176
177static bool canSplitLoopBound(const Loop &L, const DominatorTree &DT,
178 ScalarEvolution &SE, ConditionInfo &Cond) {
179 // Skip function with optsize.
180 if (L.getHeader()->getParent()->hasOptSize())
181 return false;
182
183 // Split only innermost loop.
184 if (!L.isInnermost())
185 return false;
186
187 // Check loop is in simplified form.
188 if (!L.isLoopSimplifyForm())
189 return false;
190
191 // Check loop is in LCSSA form.
192 if (!L.isLCSSAForm(DT))
193 return false;
194
195 // Skip loop that cannot be cloned.
196 if (!L.isSafeToClone())
197 return false;
198
199 BasicBlock *ExitingBB = L.getExitingBlock();
200 // Assumed only one exiting block.
201 if (!ExitingBB)
202 return false;
203
204 BranchInst *ExitingBI = dyn_cast<BranchInst>(ExitingBB->getTerminator());
205 if (!ExitingBI)
206 return false;
207
208 // Allowed only conditional branch with ICmp.
209 if (!isProcessableCondBI(SE, ExitingBI))
210 return false;
211
212 // Check the condition is processable.
213 ICmpInst *ICmp = cast<ICmpInst>(ExitingBI->getCondition());
214 if (!hasProcessableCondition(L, SE, ICmp, Cond, /*IsExitCond*/ true))
215 return false;
216
217 Cond.BI = ExitingBI;
218 return true;
219}
220
221static bool isProfitableToTransform(const Loop &L, const BranchInst *BI) {
222 // If the conditional branch splits a loop into two halves, we could
223 // generally say it is profitable.
224 //
225 // ToDo: Add more profitable cases here.
226
227 // Check this branch causes diamond CFG.
228 BasicBlock *Succ0 = BI->getSuccessor(0);
229 BasicBlock *Succ1 = BI->getSuccessor(1);
230
231 BasicBlock *Succ0Succ = Succ0->getSingleSuccessor();
232 BasicBlock *Succ1Succ = Succ1->getSingleSuccessor();
233 if (!Succ0Succ || !Succ1Succ || Succ0Succ != Succ1Succ)
234 return false;
235
236 // ToDo: Calculate each successor's instruction cost.
237
238 return true;
239}
240
242 ConditionInfo &ExitingCond,
243 ConditionInfo &SplitCandidateCond) {
244 for (auto *BB : L.blocks()) {
245 // Skip condition of backedge.
246 if (L.getLoopLatch() == BB)
247 continue;
248
249 auto *BI = dyn_cast<BranchInst>(BB->getTerminator());
250 if (!BI)
251 continue;
252
253 // Check conditional branch with ICmp.
254 if (!isProcessableCondBI(SE, BI))
255 continue;
256
257 // Skip loop invariant condition.
258 if (L.isLoopInvariant(BI->getCondition()))
259 continue;
260
261 // Check the condition is processable.
262 ICmpInst *ICmp = cast<ICmpInst>(BI->getCondition());
263 if (!hasProcessableCondition(L, SE, ICmp, SplitCandidateCond,
264 /*IsExitCond*/ false))
265 continue;
266
267 if (ExitingCond.BoundSCEV->getType() !=
268 SplitCandidateCond.BoundSCEV->getType())
269 continue;
270
271 // After transformation, we assume the split condition of the pre-loop is
272 // always true. In order to guarantee it, we need to check the start value
273 // of the split cond AddRec satisfies the split condition.
274 if (!SE.isLoopEntryGuardedByCond(&L, SplitCandidateCond.Pred,
275 SplitCandidateCond.AddRecSCEV->getStart(),
276 SplitCandidateCond.BoundSCEV))
277 continue;
278
279 SplitCandidateCond.BI = BI;
280 return BI;
281 }
282
283 return nullptr;
284}
285
286static bool splitLoopBound(Loop &L, DominatorTree &DT, LoopInfo &LI,
287 ScalarEvolution &SE, LPMUpdater &U) {
288 ConditionInfo SplitCandidateCond;
289 ConditionInfo ExitingCond;
290
291 // Check we can split this loop's bound.
292 if (!canSplitLoopBound(L, DT, SE, ExitingCond))
293 return false;
294
295 if (!findSplitCandidate(L, SE, ExitingCond, SplitCandidateCond))
296 return false;
297
298 if (!isProfitableToTransform(L, SplitCandidateCond.BI))
299 return false;
300
301 // Now, we have a split candidate. Let's build a form as below.
302 // +--------------------+
303 // | preheader |
304 // | set up newbound |
305 // +--------------------+
306 // | /----------------\
307 // +--------v----v------+ |
308 // | header |---\ |
309 // | with true condition| | |
310 // +--------------------+ | |
311 // | | |
312 // +--------v-----------+ | |
313 // | if.then.BB | | |
314 // +--------------------+ | |
315 // | | |
316 // +--------v-----------<---/ |
317 // | latch >----------/
318 // | with newbound |
319 // +--------------------+
320 // |
321 // +--------v-----------+
322 // | preheader2 |--------------\
323 // | if (AddRec i != | |
324 // | org bound) | |
325 // +--------------------+ |
326 // | /----------------\ |
327 // +--------v----v------+ | |
328 // | header2 |---\ | |
329 // | conditional branch | | | |
330 // |with false condition| | | |
331 // +--------------------+ | | |
332 // | | | |
333 // +--------v-----------+ | | |
334 // | if.then.BB2 | | | |
335 // +--------------------+ | | |
336 // | | | |
337 // +--------v-----------<---/ | |
338 // | latch2 >----------/ |
339 // | with org bound | |
340 // +--------v-----------+ |
341 // | |
342 // | +---------------+ |
343 // +--> exit <-------/
344 // +---------------+
345
346 // Let's create post loop.
347 SmallVector<BasicBlock *, 8> PostLoopBlocks;
348 Loop *PostLoop;
350 BasicBlock *PreHeader = L.getLoopPreheader();
351 BasicBlock *SplitLoopPH = SplitEdge(PreHeader, L.getHeader(), &DT, &LI);
352 PostLoop = cloneLoopWithPreheader(L.getExitBlock(), SplitLoopPH, &L, VMap,
353 ".split", &LI, &DT, PostLoopBlocks);
354 remapInstructionsInBlocks(PostLoopBlocks, VMap);
355
356 BasicBlock *PostLoopPreHeader = PostLoop->getLoopPreheader();
357 IRBuilder<> Builder(&PostLoopPreHeader->front());
358
359 // Update phi nodes in header of post-loop.
360 bool isExitingLatch = L.getExitingBlock() == L.getLoopLatch();
361 Value *ExitingCondLCSSAPhi = nullptr;
362 for (PHINode &PN : L.getHeader()->phis()) {
363 // Create LCSSA phi node in preheader of post-loop.
364 PHINode *LCSSAPhi =
365 Builder.CreatePHI(PN.getType(), 1, PN.getName() + ".lcssa");
366 LCSSAPhi->setDebugLoc(PN.getDebugLoc());
367 // If the exiting block is loop latch, the phi does not have the update at
368 // last iteration. In this case, update lcssa phi with value from backedge.
369 LCSSAPhi->addIncoming(
370 isExitingLatch ? PN.getIncomingValueForBlock(L.getLoopLatch()) : &PN,
371 L.getExitingBlock());
372
373 // Update the start value of phi node in post-loop with the LCSSA phi node.
374 PHINode *PostLoopPN = cast<PHINode>(VMap[&PN]);
375 PostLoopPN->setIncomingValueForBlock(PostLoopPreHeader, LCSSAPhi);
376
377 // Find PHI with exiting condition from pre-loop. The PHI should be
378 // SCEVAddRecExpr and have same incoming value from backedge with
379 // ExitingCond.
380 if (!SE.isSCEVable(PN.getType()))
381 continue;
382
383 const SCEVAddRecExpr *PhiSCEV = dyn_cast<SCEVAddRecExpr>(SE.getSCEV(&PN));
384 if (PhiSCEV && ExitingCond.NonPHIAddRecValue ==
385 PN.getIncomingValueForBlock(L.getLoopLatch()))
386 ExitingCondLCSSAPhi = LCSSAPhi;
387 }
388
389 // Add conditional branch to check we can skip post-loop in its preheader.
390 Instruction *OrigBI = PostLoopPreHeader->getTerminator();
392 Value *Cond =
393 Builder.CreateICmp(Pred, ExitingCondLCSSAPhi, ExitingCond.BoundValue);
394 Builder.CreateCondBr(Cond, PostLoop->getHeader(), PostLoop->getExitBlock());
395 OrigBI->eraseFromParent();
396
397 // Create new loop bound and add it into preheader of pre-loop.
398 const SCEV *NewBoundSCEV = ExitingCond.BoundSCEV;
399 const SCEV *SplitBoundSCEV = SplitCandidateCond.BoundSCEV;
400 NewBoundSCEV = ICmpInst::isSigned(ExitingCond.Pred)
401 ? SE.getSMinExpr(NewBoundSCEV, SplitBoundSCEV)
402 : SE.getUMinExpr(NewBoundSCEV, SplitBoundSCEV);
403
404 SCEVExpander Expander(
405 SE, L.getHeader()->getDataLayout(), "split");
406 Instruction *InsertPt = SplitLoopPH->getTerminator();
407 Value *NewBoundValue =
408 Expander.expandCodeFor(NewBoundSCEV, NewBoundSCEV->getType(), InsertPt);
409 NewBoundValue->setName("new.bound");
410
411 // Replace exiting bound value of pre-loop NewBound.
412 ExitingCond.ICmp->setOperand(1, NewBoundValue);
413
414 // Replace SplitCandidateCond.BI's condition of pre-loop by True.
415 LLVMContext &Context = PreHeader->getContext();
416 SplitCandidateCond.BI->setCondition(ConstantInt::getTrue(Context));
417
418 // Replace cloned SplitCandidateCond.BI's condition in post-loop by False.
419 BranchInst *ClonedSplitCandidateBI =
420 cast<BranchInst>(VMap[SplitCandidateCond.BI]);
421 ClonedSplitCandidateBI->setCondition(ConstantInt::getFalse(Context));
422
423 // Replace exit branch target of pre-loop by post-loop's preheader.
424 if (L.getExitBlock() == ExitingCond.BI->getSuccessor(0))
425 ExitingCond.BI->setSuccessor(0, PostLoopPreHeader);
426 else
427 ExitingCond.BI->setSuccessor(1, PostLoopPreHeader);
428
429 // Update phi node in exit block of post-loop.
430 Builder.SetInsertPoint(PostLoopPreHeader, PostLoopPreHeader->begin());
431 for (PHINode &PN : PostLoop->getExitBlock()->phis()) {
432 for (auto i : seq<int>(0, PN.getNumOperands())) {
433 // Check incoming block is pre-loop's exiting block.
434 if (PN.getIncomingBlock(i) == L.getExitingBlock()) {
435 Value *IncomingValue = PN.getIncomingValue(i);
436
437 // Create LCSSA phi node for incoming value.
438 PHINode *LCSSAPhi =
439 Builder.CreatePHI(PN.getType(), 1, PN.getName() + ".lcssa");
440 LCSSAPhi->setDebugLoc(PN.getDebugLoc());
441 LCSSAPhi->addIncoming(IncomingValue, PN.getIncomingBlock(i));
442
443 // Replace pre-loop's exiting block by post-loop's preheader.
444 PN.setIncomingBlock(i, PostLoopPreHeader);
445 // Replace incoming value by LCSSAPhi.
446 PN.setIncomingValue(i, LCSSAPhi);
447 // Add a new incoming value with post-loop's exiting block.
448 PN.addIncoming(VMap[IncomingValue], PostLoop->getExitingBlock());
449 }
450 }
451 }
452
453 // Update dominator tree.
454 DT.changeImmediateDominator(PostLoopPreHeader, L.getExitingBlock());
455 DT.changeImmediateDominator(PostLoop->getExitBlock(), PostLoopPreHeader);
456
457 // Invalidate cached SE information.
458 SE.forgetLoop(&L);
459
460 // Canonicalize loops.
461 simplifyLoop(&L, &DT, &LI, &SE, nullptr, nullptr, true);
462 simplifyLoop(PostLoop, &DT, &LI, &SE, nullptr, nullptr, true);
463
464 // Add new post-loop to loop pass manager.
465 U.addSiblingLoops(PostLoop);
466
467 return true;
468}
469
472 LPMUpdater &U) {
473 [[maybe_unused]] Function &F = *L.getHeader()->getParent();
474
475 LLVM_DEBUG(dbgs() << "Spliting bound of loop in " << F.getName() << ": " << L
476 << "\n");
477
478 if (!splitLoopBound(L, AR.DT, AR.LI, AR.SE, U))
479 return PreservedAnalyses::all();
480
481 assert(AR.DT.verify(DominatorTree::VerificationLevel::Fast));
482 AR.LI.verify(AR.DT);
483
485}
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
This header provides classes for managing per-loop analyses.
static BranchInst * findSplitCandidate(const Loop &L, ScalarEvolution &SE, ConditionInfo &ExitingCond, ConditionInfo &SplitCandidateCond)
static bool canSplitLoopBound(const Loop &L, const DominatorTree &DT, ScalarEvolution &SE, ConditionInfo &Cond)
static void analyzeICmp(ScalarEvolution &SE, ICmpInst *ICmp, ConditionInfo &Cond, const Loop &L)
static bool splitLoopBound(Loop &L, DominatorTree &DT, LoopInfo &LI, ScalarEvolution &SE, LPMUpdater &U)
static bool hasProcessableCondition(const Loop &L, ScalarEvolution &SE, ICmpInst *ICmp, ConditionInfo &Cond, bool IsExitCond)
static bool isProcessableCondBI(const ScalarEvolution &SE, const BranchInst *BI)
static bool calculateUpperBound(const Loop &L, ScalarEvolution &SE, ConditionInfo &Cond, bool IsExitCond)
static bool isProfitableToTransform(const Loop &L, const BranchInst *BI)
This header provides classes for managing a pipeline of passes over loops in LLVM IR.
#define F(x, y, z)
Definition MD5.cpp:55
const SmallVectorImpl< MachineOperand > & Cond
Provides some synthesis utilities to produce sequences of values.
#define LLVM_DEBUG(...)
Definition Debug.h:114
Value * RHS
Value * LHS
Class for arbitrary precision integers.
Definition APInt.h:78
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
Definition APInt.h:206
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
Definition APInt.h:209
LLVM Basic Block Representation.
Definition BasicBlock.h:62
iterator begin()
Instruction iterator methods.
Definition BasicBlock.h:459
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition BasicBlock.h:528
const Instruction & front() const
Definition BasicBlock.h:482
LLVM_ABI const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
LLVM_ABI LLVMContext & getContext() const
Get the context in which this basic block lives.
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:233
Conditional or Unconditional Branch instruction.
void setCondition(Value *V)
BasicBlock * getSuccessor(unsigned i) const
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
Value * getCondition() const
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition InstrTypes.h:676
@ ICMP_SLT
signed less than
Definition InstrTypes.h:705
@ ICMP_SLE
signed less or equal
Definition InstrTypes.h:706
@ ICMP_ULT
unsigned less than
Definition InstrTypes.h:701
@ ICMP_NE
not equal
Definition InstrTypes.h:698
@ ICMP_ULE
unsigned less or equal
Definition InstrTypes.h:702
bool isSigned() const
Definition InstrTypes.h:930
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Definition InstrTypes.h:827
An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...
This is the shared class of boolean and integer constants.
Definition Constants.h:87
bool isNegative() const
Definition Constants.h:209
static LLVM_ABI ConstantInt * getTrue(LLVMContext &Context)
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
Definition Constants.h:214
static LLVM_ABI ConstantInt * getFalse(LLVMContext &Context)
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition Constants.h:154
bool verify(VerificationLevel VL=VerificationLevel::Full) const
verify - checks if the tree is correct.
void changeImmediateDominator(DomTreeNodeBase< NodeT > *N, DomTreeNodeBase< NodeT > *NewIDom)
changeImmediateDominator - This method is used to update the dominator tree information when a node's...
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition Dominators.h:165
This instruction compares its operands according to the predicate given to the constructor.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition IRBuilder.h:2788
LLVM_ABI InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Class to represent integer types.
This is an important class for using LLVM in a threaded context.
Definition LLVMContext.h:68
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
BlockT * getHeader() const
BlockT * getExitBlock() const
If getExitBlocks would return exactly one block, return that block.
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
BlockT * getExitingBlock() const
If getExitingBlocks would return exactly one block, return that block.
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
void verify(const DominatorTreeBase< BlockT, false > &DomTree) const
Represents a single loop in the control flow graph.
Definition LoopInfo.h:40
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
void setIncomingValueForBlock(const BasicBlock *BB, Value *V)
Set every incoming value(s) for block BB to V.
Value * getIncomingValueForBlock(const BasicBlock *BB) const
A set of analyses that are preserved following a run of a transformation pass.
Definition Analysis.h:112
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition Analysis.h:118
This node represents a polynomial recurrence on the trip count of the specified loop.
This class uses information about analyze scalars to rewrite expressions in canonical form.
LLVM_ABI Value * expandCodeFor(const SCEV *SH, Type *Ty, BasicBlock::iterator I)
Insert code to directly compute the specified SCEV expression into the program.
This class represents an analyzed expression in the program.
LLVM_ABI Type * getType() const
Return the LLVM type of this SCEV expression.
The main scalar evolution driver.
LLVM_ABI bool isLoopEntryGuardedByCond(const Loop *L, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether entry to the loop is protected by a conditional between LHS and RHS.
LLVM_ABI const SCEV * getSMinExpr(const SCEV *LHS, const SCEV *RHS)
LLVM_ABI const SCEV * getConstant(ConstantInt *V)
LLVM_ABI const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
const SCEV * getOne(Type *Ty)
Return a SCEV for the constant 1 of a specific type.
LLVM_ABI 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...
LLVM_ABI bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
LLVM_ABI const SCEV * getUMinExpr(const SCEV *LHS, const SCEV *RHS, bool Sequential=false)
LLVM_ABI bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L)
Determine if the SCEV can be evaluated at loop's entry.
LLVM_ABI 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...
LLVM_ABI 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.
LLVM_ABI bool isKnownPredicate(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
void setOperand(unsigned i, Value *Val)
Definition User.h:237
LLVM Value Representation.
Definition Value.h:75
LLVM_ABI void setName(const Twine &Name)
Change the name of the value.
Definition Value.cpp:390
bool match(Val *V, const Pattern &P)
brc_match< Cond_t, bind_ty< BasicBlock >, bind_ty< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
CmpClass_match< LHS, RHS, ICmpInst > m_ICmp(CmpPredicate &Pred, const LHS &L, const RHS &R)
class_match< BasicBlock > m_BasicBlock()
Match an arbitrary basic block value and ignore it.
This is an optimization pass for GlobalISel generic memory operations.
LLVM_ABI bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
Simplify each loop in a loop nest recursively.
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:643
AnalysisManager< Loop, LoopStandardAnalysisResults & > LoopAnalysisManager
The loop analysis manager.
LLVM_ABI Loop * cloneLoopWithPreheader(BasicBlock *Before, BasicBlock *LoopDomBB, Loop *OrigLoop, ValueToValueMapTy &VMap, const Twine &NameSuffix, LoopInfo *LI, DominatorTree *DT, SmallVectorImpl< BasicBlock * > &Blocks)
Clones a loop OrigLoop.
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:207
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
Definition Casting.h:547
LLVM_ABI void remapInstructionsInBlocks(ArrayRef< BasicBlock * > Blocks, ValueToValueMapTy &VMap)
Remaps instructions in Blocks using the mapping in VMap.
constexpr unsigned BitWidth
ValueMap< const Value *, WeakTrackingVH > ValueToValueMapTy
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:559
LLVM_ABI PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
auto seq(T Begin, T End)
Iterate over an integral type from Begin up to - but not including - End.
Definition Sequence.h:305
LLVM_ABI 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...
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition BitVector.h:869
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...