22#define DEBUG_TYPE "loop-bound-split"
36 Value *AddRecValue =
nullptr;
38 Value *NonPHIAddRecValue;
40 Value *BoundValue =
nullptr;
44 const SCEV *BoundSCEV =
nullptr;
46 ConditionInfo() =
default;
51 ConditionInfo &
Cond,
const Loop &L) {
60 if (!LHSAddRecSCEV && RHSAddRecSCEV) {
67 Cond.BoundSCEV = BoundSCEV;
68 Cond.NonPHIAddRecValue =
Cond.AddRecValue;
80 ConditionInfo &
Cond,
bool IsExitCond) {
86 Cond.BoundSCEV = ExitCount;
102 unsigned BitWidth = BoundSCEVIntType->getBitWidth();
111 const SCEV *BoundPlusOneSCEV =
113 Cond.BoundSCEV = BoundPlusOneSCEV;
134 if (!
Cond.AddRecSCEV)
137 if (!
Cond.AddRecSCEV->isAffine())
140 const SCEV *StepRecSCEV =
Cond.AddRecSCEV->getStepRecurrence(SE);
171 if (TrueSucc == FalseSucc)
180 if (L.getHeader()->getParent()->hasOptSize())
184 if (!L.isInnermost())
188 if (!L.isLoopSimplifyForm())
192 if (!L.isLCSSAForm(DT))
196 if (!L.isSafeToClone())
233 if (!Succ0Succ || !Succ1Succ || Succ0Succ != Succ1Succ)
242 ConditionInfo &ExitingCond,
243 ConditionInfo &SplitCandidateCond) {
244 for (
auto *BB : L.blocks()) {
246 if (L.getLoopLatch() == BB)
258 if (L.isLoopInvariant(BI->getCondition()))
267 if (ExitingCond.BoundSCEV->
getType() !=
268 SplitCandidateCond.BoundSCEV->
getType())
275 SplitCandidateCond.AddRecSCEV->
getStart(),
276 SplitCandidateCond.BoundSCEV))
279 SplitCandidateCond.BI = BI;
288 ConditionInfo SplitCandidateCond;
289 ConditionInfo ExitingCond;
353 ".split", &LI, &DT, PostLoopBlocks);
360 bool isExitingLatch = L.getExitingBlock() == L.getLoopLatch();
361 Value *ExitingCondLCSSAPhi =
nullptr;
362 for (
PHINode &PN : L.getHeader()->phis()) {
365 Builder.CreatePHI(PN.getType(), 1, PN.getName() +
".lcssa");
370 isExitingLatch ? PN.getIncomingValueForBlock(L.getLoopLatch()) : &PN,
371 L.getExitingBlock());
384 if (PhiSCEV && ExitingCond.NonPHIAddRecValue ==
385 PN.getIncomingValueForBlock(L.getLoopLatch()))
386 ExitingCondLCSSAPhi = LCSSAPhi;
393 Builder.CreateICmp(Pred, ExitingCondLCSSAPhi, ExitingCond.BoundValue);
398 const SCEV *NewBoundSCEV = ExitingCond.BoundSCEV;
399 const SCEV *SplitBoundSCEV = SplitCandidateCond.BoundSCEV;
405 SE, L.getHeader()->getDataLayout(),
"split");
407 Value *NewBoundValue =
409 NewBoundValue->
setName(
"new.bound");
412 ExitingCond.ICmp->
setOperand(1, NewBoundValue);
424 if (L.getExitBlock() == ExitingCond.BI->
getSuccessor(0))
430 Builder.SetInsertPoint(PostLoopPreHeader, PostLoopPreHeader->
begin());
432 for (
auto i :
seq<int>(0, PN.getNumOperands())) {
434 if (PN.getIncomingBlock(i) == L.getExitingBlock()) {
435 Value *IncomingValue = PN.getIncomingValue(i);
439 Builder.CreatePHI(PN.getType(), 1, PN.getName() +
".lcssa");
441 LCSSAPhi->
addIncoming(IncomingValue, PN.getIncomingBlock(i));
444 PN.setIncomingBlock(i, PostLoopPreHeader);
446 PN.setIncomingValue(i, LCSSAPhi);
461 simplifyLoop(&L, &DT, &LI, &SE,
nullptr,
nullptr,
true);
462 simplifyLoop(PostLoop, &DT, &LI, &SE,
nullptr,
nullptr,
true);
465 U.addSiblingLoops(PostLoop);
473 [[maybe_unused]]
Function &
F = *L.getHeader()->getParent();
475 LLVM_DEBUG(
dbgs() <<
"Spliting bound of loop in " <<
F.getName() <<
": " << L
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.
const SmallVectorImpl< MachineOperand > & Cond
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.
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
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...
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.
@ 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.
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.
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.
static LLVM_ABI 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...
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.
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.
const SCEV * getStart() const
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)
LLVM Value Representation.
LLVM_ABI void setName(const Twine &Name)
Change the name of the value.
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.
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.
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...
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.
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.
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.
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...