22#define DEBUG_TYPE "loop-bound-split"
26using namespace PatternMatch;
31 BranchInst *BI =
nullptr;
33 ICmpInst *ICmp =
nullptr;
37 Value *AddRecValue =
nullptr;
39 Value *NonPHIAddRecValue;
41 Value *BoundValue =
nullptr;
43 const SCEVAddRecExpr *AddRecSCEV =
nullptr;
45 const SCEV *BoundSCEV =
nullptr;
47 ConditionInfo() =
default;
52 ConditionInfo &
Cond,
const Loop &L) {
58 const SCEVAddRecExpr *LHSAddRecSCEV = dyn_cast<SCEVAddRecExpr>(AddRecSCEV);
59 const SCEVAddRecExpr *RHSAddRecSCEV = dyn_cast<SCEVAddRecExpr>(BoundSCEV);
61 if (!LHSAddRecSCEV && RHSAddRecSCEV) {
67 Cond.AddRecSCEV = dyn_cast<SCEVAddRecExpr>(AddRecSCEV);
68 Cond.BoundSCEV = BoundSCEV;
69 Cond.NonPHIAddRecValue =
Cond.AddRecValue;
73 if (
Cond.AddRecSCEV && isa<PHINode>(
Cond.AddRecValue)) {
81 ConditionInfo &
Cond,
bool IsExitCond) {
84 if (isa<SCEVCouldNotCompute>(ExitCount))
87 Cond.BoundSCEV = ExitCount;
102 dyn_cast<IntegerType>(
Cond.BoundSCEV->getType())) {
103 unsigned BitWidth = BoundSCEVIntType->getBitWidth();
112 const SCEV *BoundPlusOneSCEV =
114 Cond.BoundSCEV = BoundPlusOneSCEV;
135 if (!
Cond.AddRecSCEV)
138 if (!
Cond.AddRecSCEV->isAffine())
141 const SCEV *StepRecSCEV =
Cond.AddRecSCEV->getStepRecurrence(SE);
143 if (!isa<SCEVConstant>(StepRecSCEV))
173 if (TrueSucc == FalseSucc)
182 if (L.getHeader()->getParent()->hasOptSize())
186 if (!L.isInnermost())
190 if (!L.isLoopSimplifyForm())
194 if (!L.isLCSSAForm(DT))
198 if (!L.isSafeToClone())
235 if (!Succ0Succ || !Succ1Succ || Succ0Succ != Succ1Succ)
244 ConditionInfo &ExitingCond,
245 ConditionInfo &SplitCandidateCond) {
246 for (
auto *BB : L.blocks()) {
248 if (L.getLoopLatch() == BB)
251 auto *BI = dyn_cast<BranchInst>(BB->getTerminator());
260 if (L.isLoopInvariant(BI->getCondition()))
264 ICmpInst *ICmp = cast<ICmpInst>(BI->getCondition());
269 if (ExitingCond.BoundSCEV->getType() !=
270 SplitCandidateCond.BoundSCEV->getType())
277 SplitCandidateCond.AddRecSCEV->getStart(),
278 SplitCandidateCond.BoundSCEV))
281 SplitCandidateCond.BI = BI;
290 ConditionInfo SplitCandidateCond;
291 ConditionInfo ExitingCond;
355 ".split", &LI, &DT, PostLoopBlocks);
362 bool isExitingLatch =
363 (L.getExitingBlock() == L.getLoopLatch()) ?
true :
false;
364 Value *ExitingCondLCSSAPhi =
nullptr;
365 for (
PHINode &PN : L.getHeader()->phis()) {
368 Builder.CreatePHI(PN.getType(), 1, PN.getName() +
".lcssa");
373 isExitingLatch ? PN.getIncomingValueForBlock(L.getLoopLatch()) : &PN,
374 L.getExitingBlock());
377 PHINode *PostLoopPN = cast<PHINode>(VMap[&PN]);
387 if (PhiSCEV && ExitingCond.NonPHIAddRecValue ==
388 PN.getIncomingValueForBlock(L.getLoopLatch()))
389 ExitingCondLCSSAPhi = LCSSAPhi;
396 Builder.CreateICmp(Pred, ExitingCondLCSSAPhi, ExitingCond.BoundValue);
401 const SCEV *NewBoundSCEV = ExitingCond.BoundSCEV;
402 const SCEV *SplitBoundSCEV = SplitCandidateCond.BoundSCEV;
408 SE, L.getHeader()->getParent()->getParent()->getDataLayout(),
"split");
410 Value *NewBoundValue =
412 NewBoundValue->
setName(
"new.bound");
415 ExitingCond.ICmp->setOperand(1, NewBoundValue);
423 cast<BranchInst>(VMap[SplitCandidateCond.BI]);
427 if (L.getExitBlock() == ExitingCond.BI->getSuccessor(0))
428 ExitingCond.BI->setSuccessor(0, PostLoopPreHeader);
430 ExitingCond.BI->setSuccessor(1, PostLoopPreHeader);
433 Builder.SetInsertPoint(PostLoopPreHeader, PostLoopPreHeader->
begin());
435 for (
auto i : seq<int>(0, PN.getNumOperands())) {
437 if (PN.getIncomingBlock(i) == L.getExitingBlock()) {
438 Value *IncomingValue = PN.getIncomingValue(i);
442 Builder.CreatePHI(PN.getType(), 1, PN.getName() +
".lcssa");
444 LCSSAPhi->
addIncoming(IncomingValue, PN.getIncomingBlock(i));
447 PN.setIncomingBlock(i, PostLoopPreHeader);
449 PN.setIncomingValue(i, LCSSAPhi);
464 simplifyLoop(&L, &DT, &LI, &SE,
nullptr,
nullptr,
true);
465 simplifyLoop(PostLoop, &DT, &LI, &SE,
nullptr,
nullptr,
true);
468 U.addSiblingLoops(PostLoop);
476 Function &
F = *L.getHeader()->getParent();
479 LLVM_DEBUG(
dbgs() <<
"Spliting bound of loop in " <<
F.getName() <<
": " << L
This header provides classes for managing per-loop analyses.
This header provides classes for managing a pipeline of passes over loops in LLVM IR.
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Provides some synthesis utilities to produce sequences of values.
Class for arbitrary precision integers.
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
A container for analyses that lazily runs them and caches their results.
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
const Instruction & front() const
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
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...
Conditional or Unconditional Branch instruction.
void setCondition(Value *V)
BasicBlock * getSuccessor(unsigned i) const
Value * getCondition() const
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
@ ICMP_SLT
signed less than
@ ICMP_SLE
signed less or equal
@ ICMP_ULT
unsigned less than
@ ICMP_ULE
unsigned less or equal
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
This is the shared class of boolean and integer constants.
static ConstantInt * getTrue(LLVMContext &Context)
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
static ConstantInt * getFalse(LLVMContext &Context)
const APInt & getValue() const
Return the constant as an APInt value reference.
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.
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...
SymbolTableList< Instruction >::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.
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.
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.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
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.
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.
Type * getType() const
Return the LLVM type of this SCEV expression.
The main scalar evolution driver.
const SCEV * getSMinExpr(const SCEV *LHS, const SCEV *RHS)
const SCEV * getConstant(ConstantInt *V)
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.
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...
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,...
bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
const SCEV * getUMinExpr(const SCEV *LHS, const SCEV *RHS, bool Sequential=false)
bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L)
Determine if the SCEV can be evaluated at loop's entry.
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...
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.
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.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
void setName(const Twine &Name)
Change the name of the value.
bool match(Val *V, const Pattern &P)
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
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.
class_match< BasicBlock > m_BasicBlock()
Match an arbitrary basic block value and ignore it.
This is an optimization pass for GlobalISel generic memory operations.
bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
Simplify each loop in a loop nest recursively.
static bool isProcessableCondBI(const ScalarEvolution &SE, const BranchInst *BI)
static bool splitLoopBound(Loop &L, DominatorTree &DT, LoopInfo &LI, ScalarEvolution &SE, LPMUpdater &U)
static bool canSplitLoopBound(const Loop &L, const DominatorTree &DT, ScalarEvolution &SE, ConditionInfo &Cond)
Loop * cloneLoopWithPreheader(BasicBlock *Before, BasicBlock *LoopDomBB, Loop *OrigLoop, ValueToValueMapTy &VMap, const Twine &NameSuffix, LoopInfo *LI, DominatorTree *DT, SmallVectorImpl< BasicBlock * > &Blocks)
Clones a loop OrigLoop.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
static BranchInst * findSplitCandidate(const Loop &L, ScalarEvolution &SE, ConditionInfo &ExitingCond, ConditionInfo &SplitCandidateCond)
void remapInstructionsInBlocks(ArrayRef< BasicBlock * > Blocks, ValueToValueMapTy &VMap)
Remaps instructions in Blocks using the mapping in VMap.
constexpr unsigned BitWidth
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
static bool calculateUpperBound(const Loop &L, ScalarEvolution &SE, ConditionInfo &Cond, bool IsExitCond)
static bool hasProcessableCondition(const Loop &L, ScalarEvolution &SE, ICmpInst *ICmp, ConditionInfo &Cond, bool IsExitCond)
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...
static void analyzeICmp(ScalarEvolution &SE, ICmpInst *ICmp, ConditionInfo &Cond, const Loop &L)
static bool isProfitableToTransform(const Loop &L, const BranchInst *BI)
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...