118 cl::desc(
"If set to true, IRCE may eliminate wide range checks in loops "
119 "with narrow latch condition."));
124 "Maximum size of range check type for which can be produced runtime "
125 "overflow check of its limit's computation"));
131#define DEBUG_TYPE "irce"
145class InductiveRangeCheck {
147 const SCEV *Begin =
nullptr;
148 const SCEV *Step =
nullptr;
150 Use *CheckUse =
nullptr;
166 static bool reassociateSubLHS(
Loop *L,
Value *VariantLHS,
Value *InvariantRHS,
171 const SCEV *getBegin()
const {
return Begin; }
172 const SCEV *getStep()
const {
return Step; }
173 const SCEV *getEnd()
const {
return End; }
176 OS <<
"InductiveRangeCheck:\n";
183 OS <<
"\n CheckUse: ";
184 getCheckUse()->getUser()->print(
OS);
185 OS <<
" Operand: " << getCheckUse()->getOperandNo() <<
"\n";
193 Use *getCheckUse()
const {
return CheckUse; }
208 const SCEV *getBegin()
const {
return Begin; }
209 const SCEV *getEnd()
const {
return End; }
222 bool getPassingDirection() {
return true; }
229 bool IsLatchSigned)
const;
236 static void extractRangeChecksFromBranch(
241class InductiveRangeCheckElimination {
258 LoopInfo &LI, GetBFIFunc GetBFI = std::nullopt)
259 : SE(SE), BPI(BPI), DT(DT), LI(LI), GetBFI(GetBFI) {}
270bool InductiveRangeCheck::parseRangeCheckICmp(
Loop *L,
ICmpInst *ICI,
274 auto IsLoopInvariant = [&SE,
L](
Value *
V) {
286 if (IsLoopInvariant(LHS)) {
289 }
else if (!IsLoopInvariant(RHS))
293 if (parseIvAgaisntLimit(L, LHS, RHS, Pred, SE,
Index,
End))
296 if (reassociateSubLHS(L, LHS, RHS, Pred, SE,
Index,
End))
304bool InductiveRangeCheck::parseIvAgaisntLimit(
Loop *L,
Value *LHS,
Value *RHS,
310 auto SIntMaxSCEV = [&](
Type *
T) {
311 unsigned BitWidth = cast<IntegerType>(
T)->getBitWidth();
315 const auto *AddRec = dyn_cast<SCEVAddRecExpr>(SE.
getSCEV(LHS));
327 case ICmpInst::ICMP_SGE:
328 if (
match(RHS, m_ConstantInt<0>())) {
330 End = SIntMaxSCEV(
Index->getType());
335 case ICmpInst::ICMP_SGT:
336 if (
match(RHS, m_ConstantInt<-1>())) {
338 End = SIntMaxSCEV(
Index->getType());
343 case ICmpInst::ICMP_SLT:
344 case ICmpInst::ICMP_ULT:
349 case ICmpInst::ICMP_SLE:
350 case ICmpInst::ICMP_ULE:
353 bool Signed = Pred == ICmpInst::ICMP_SLE;
367bool InductiveRangeCheck::reassociateSubLHS(
378 bool OffsetSubtracted =
false;
384 OffsetSubtracted =
true;
388 const auto *AddRec = dyn_cast<SCEVAddRecExpr>(
IV);
438 case Instruction::Add:
441 case Instruction::Sub:
447 cast<Instruction>(VariantLHS)))
462 if (OffsetSubtracted)
464 Limit = getExprScaledIfOverflow(Instruction::BinaryOps::Add,
Offset, Limit);
467 Limit = getExprScaledIfOverflow(Instruction::BinaryOps::Sub,
Offset, Limit);
468 Pred = ICmpInst::getSwappedPredicate(Pred);
471 if (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SLE) {
473 if (Pred == ICmpInst::ICMP_SLE && Limit)
474 Limit = getExprScaledIfOverflow(Instruction::BinaryOps::Add, Limit,
485void InductiveRangeCheck::extractRangeChecksFromCond(
489 Value *Condition = ConditionUse.
get();
490 if (!Visited.
insert(Condition).second)
495 extractRangeChecksFromCond(L, SE, cast<User>(Condition)->getOperandUse(0),
497 extractRangeChecksFromCond(L, SE, cast<User>(Condition)->getOperandUse(1),
502 ICmpInst *ICI = dyn_cast<ICmpInst>(Condition);
508 if (!parseRangeCheckICmp(L, ICI, SE, IndexAddRec,
End))
511 assert(IndexAddRec &&
"IndexAddRec was not computed");
517 InductiveRangeCheck IRC;
519 IRC.Begin = IndexAddRec->
getStart();
521 IRC.CheckUse = &ConditionUse;
525void InductiveRangeCheck::extractRangeChecksFromBranch(
531 unsigned IndexLoopSucc =
L->contains(BI->
getSuccessor(0)) ? 0 : 1;
533 "No edges coming to loop?");
542 if (IndexLoopSucc != 0) {
551 InductiveRangeCheck::extractRangeChecksFromCond(L, SE, BI->
getOperandUse(0),
565static std::optional<LoopConstrainer::SubRanges>
567 InductiveRangeCheck::Range &
Range,
569 auto *RTy = cast<IntegerType>(
Range.getType());
583 RTy, SE, IsSignedPredicate);
585 SE, IsSignedPredicate);
593 const SCEV *Smallest =
nullptr, *Greatest =
nullptr, *GreatestSeen =
nullptr;
619 GreatestSeen = Start;
622 auto Clamp = [&SE, Smallest, Greatest, IsSignedPredicate](
const SCEV *S) {
623 return IsSignedPredicate
630 IsSignedPredicate ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_ULE;
632 IsSignedPredicate ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
634 bool ProvablyNoPreloop =
636 if (!ProvablyNoPreloop)
637 Result.LowLimit = Clamp(
Range.getBegin());
639 bool ProvablyNoPostLoop =
641 if (!ProvablyNoPostLoop)
642 Result.HighLimit = Clamp(
Range.getEnd());
650std::optional<InductiveRangeCheck::Range>
653 bool IsLatchSigned)
const {
656 auto *IVType = dyn_cast<IntegerType>(IndVar->
getType());
657 auto *RCType = dyn_cast<IntegerType>(getBegin()->
getType());
658 auto *EndType = dyn_cast<IntegerType>(getEnd()->
getType());
660 if (!IVType || !RCType)
662 if (IVType->getBitWidth() > RCType->getBitWidth())
693 assert(!
B->isZero() &&
"Recurrence with zero step?");
695 const SCEV *
C = getBegin();
700 assert(!
D->getValue()->isZero() &&
"Recurrence with zero step?");
701 unsigned BitWidth = RCType->getBitWidth();
717 auto ClampedSubtract = [&](
const SCEV *
X,
const SCEV *
Y) {
753 auto SCEVCheckNonNegative = [&](
const SCEV *
X) {
770 auto SCEVCheckWillNotOverflow = [&](
const SCEV *
X) {
774 const SCEV *OverflowCheck =
780 const SCEV *UnderflowCheck =
783 return SE.
getMulExpr(OverflowCheck, UnderflowCheck);
794 const SCEV *REnd = getEnd();
795 const SCEV *EndWillNotOverflow = SE.
getOne(RCType);
799 OS <<
"irce: in function ";
800 OS <<
L->getHeader()->getParent()->getName();
803 OS <<
"there is range check with scaled boundary:\n";
807 if (EndType->getBitWidth() > RCType->getBitWidth()) {
808 assert(EndType->getBitWidth() == RCType->getBitWidth() * 2);
810 PrintRangeCheck(
errs());
819 const SCEV *RuntimeChecks =
820 SE.
getMulExpr(SCEVCheckNonNegative(REnd), EndWillNotOverflow);
821 const SCEV *Begin = SE.
getMulExpr(ClampedSubtract(Zero, M), RuntimeChecks);
824 return InductiveRangeCheck::Range(Begin,
End);
827static std::optional<InductiveRangeCheck::Range>
829 const std::optional<InductiveRangeCheck::Range> &R1,
830 const InductiveRangeCheck::Range &
R2) {
831 if (
R2.isEmpty(SE,
true))
838 assert(!R1Value.isEmpty(SE,
true) &&
839 "We should never have empty R1!");
843 if (R1Value.getType() !=
R2.getType())
850 auto Ret = InductiveRangeCheck::Range(NewBegin, NewEnd);
851 if (Ret.isEmpty(SE,
true))
856static std::optional<InductiveRangeCheck::Range>
858 const std::optional<InductiveRangeCheck::Range> &R1,
859 const InductiveRangeCheck::Range &
R2) {
860 if (
R2.isEmpty(SE,
false))
867 assert(!R1Value.isEmpty(SE,
false) &&
868 "We should never have empty R1!");
872 if (R1Value.getType() !=
R2.getType())
879 auto Ret = InductiveRangeCheck::Range(NewBegin, NewEnd);
880 if (Ret.isEmpty(SE,
false))
900 InductiveRangeCheckElimination IRCE(SE, &BPI, DT, LI, { getBFI });
902 bool Changed =
false;
904 bool CFGChanged =
false;
905 for (
const auto &L : LI) {
906 CFGChanged |=
simplifyLoop(L, &DT, &LI, &SE,
nullptr,
nullptr,
910 Changed |= CFGChanged;
921 auto LPMAddNewLoop = [&Worklist](
Loop *
NL,
bool IsSubloop) {
926 while (!Worklist.
empty()) {
928 if (IRCE.run(L, LPMAddNewLoop)) {
944InductiveRangeCheckElimination::isProfitableToTransform(
const Loop &L,
950 uint64_t hFreq = BFI.getBlockFreq(LS.Header).getFrequency();
951 uint64_t phFreq = BFI.getBlockFreq(L.getLoopPreheader()).getFrequency();
954 <<
"the estimated number of iterations basing on "
955 "frequency info is " << (hFreq / phFreq) <<
"\n";);
967 <<
"the exit probability is too big " << ExitProbability
974bool InductiveRangeCheckElimination::run(
977 LLVM_DEBUG(
dbgs() <<
"irce: giving up constraining loop, too large\n");
989 bool Changed =
false;
991 for (
auto *BBI :
L->getBlocks())
992 if (
BranchInst *TBI = dyn_cast<BranchInst>(BBI->getTerminator()))
993 InductiveRangeCheck::extractRangeChecksFromBranch(TBI, L, SE, BPI,
994 RangeChecks, Changed);
996 if (RangeChecks.
empty())
1000 OS <<
"irce: looking at loop ";
L->print(
OS);
1001 OS <<
"irce: loop has " << RangeChecks.
size()
1002 <<
" inductive range checks: \n";
1003 for (InductiveRangeCheck &IRC : RangeChecks)
1010 PrintRecognizedRangeChecks(
errs());
1012 const char *FailureReason =
nullptr;
1013 std::optional<LoopStructure> MaybeLoopStructure =
1016 if (!MaybeLoopStructure) {
1018 << FailureReason <<
"\n";);
1027 std::optional<InductiveRangeCheck::Range> SafeIterRange;
1034 auto IntersectRange =
1037 for (InductiveRangeCheck &IRC : RangeChecks) {
1038 auto Result = IRC.computeSafeIterationSpace(SE, IndVar,
1039 LS.IsSignedPredicate);
1041 auto MaybeSafeIterRange = IntersectRange(SE, SafeIterRange, *Result);
1042 if (MaybeSafeIterRange) {
1043 assert(!MaybeSafeIterRange->isEmpty(SE,
LS.IsSignedPredicate) &&
1044 "We should never return empty ranges!");
1046 SafeIterRange = *MaybeSafeIterRange;
1054 std::optional<LoopConstrainer::SubRanges> MaybeSR =
1062 SafeIterRange->getBegin()->getType(), *MaybeSR);
1067 auto PrintConstrainedLoopInfo = [
L]() {
1068 dbgs() <<
"irce: in function ";
1069 dbgs() <<
L->getHeader()->getParent()->getName() <<
": ";
1070 dbgs() <<
"constrained ";
1077 PrintConstrainedLoopInfo();
1081 for (InductiveRangeCheck &IRC : RangeChecksToEliminate) {
1082 ConstantInt *FoldedRangeCheck = IRC.getPassingDirection()
1085 IRC.getCheckUse()->set(FoldedRangeCheck);
This file implements a class to represent arbitrary precision integral constant values and operations...
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
This defines the Use class.
static const SCEV * NoopOrExtend(const SCEV *S, Type *Ty, ScalarEvolution &SE, bool Signed)
If the type of S matches with Ty, return S.
static cl::opt< bool > PrintRangeChecks("irce-print-range-checks", cl::Hidden, cl::init(false))
static cl::opt< bool > AllowUnsignedLatchCondition("irce-allow-unsigned-latch", cl::Hidden, cl::init(true))
static cl::opt< unsigned > MinRuntimeIterations("irce-min-runtime-iterations", cl::Hidden, cl::init(10))
static cl::opt< unsigned > LoopSizeCutoff("irce-loop-size-cutoff", cl::Hidden, cl::init(64))
static std::optional< InductiveRangeCheck::Range > IntersectSignedRange(ScalarEvolution &SE, const std::optional< InductiveRangeCheck::Range > &R1, const InductiveRangeCheck::Range &R2)
static cl::opt< bool > AllowNarrowLatchCondition("irce-allow-narrow-latch", cl::Hidden, cl::init(true), cl::desc("If set to true, IRCE may eliminate wide range checks in loops " "with narrow latch condition."))
static cl::opt< unsigned > MaxTypeSizeForOverflowCheck("irce-max-type-size-for-overflow-check", cl::Hidden, cl::init(32), cl::desc("Maximum size of range check type for which can be produced runtime " "overflow check of its limit's computation"))
static cl::opt< bool > PrintChangedLoops("irce-print-changed-loops", cl::Hidden, cl::init(false))
static std::optional< InductiveRangeCheck::Range > IntersectUnsignedRange(ScalarEvolution &SE, const std::optional< InductiveRangeCheck::Range > &R1, const InductiveRangeCheck::Range &R2)
static cl::opt< bool > SkipProfitabilityChecks("irce-skip-profitability-checks", cl::Hidden, cl::init(false))
static std::optional< LoopConstrainer::SubRanges > calculateSubRanges(ScalarEvolution &SE, const Loop &L, InductiveRangeCheck::Range &Range, const LoopStructure &MainLoopStructure)
static cl::opt< bool > PrintScaledBoundaryRangeChecks("irce-print-scaled-boundary-range-checks", cl::Hidden, cl::init(false))
static Constant * getFalse(Type *Ty)
For a boolean type or a vector of boolean type, return false or a vector with every element false.
This header provides classes for managing per-loop analyses.
Module.h This file contains the declarations for the Module class.
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
PowerPC Reduce CR logical Operation
This file provides a priority worklist.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
static SymbolRef::Type getType(const Symbol *Sym)
static const uint32_t IV[8]
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
A container for analyses that lazily runs them and caches their results.
void invalidate(IRUnitT &IR, const PreservedAnalyses &PA)
Invalidate cached analyses for an IR unit.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
LLVM Basic Block Representation.
LLVMContext & getContext() const
Get the context in which this basic block lives.
Analysis pass which computes BlockFrequencyInfo.
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
Conditional or Unconditional Branch instruction.
BasicBlock * getSuccessor(unsigned i) const
bool isUnconditional() const
Analysis pass which computes BranchProbabilityInfo.
Analysis providing branch probability information.
BranchProbability getEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors) const
Get an edge's probability, relative to other out-edges of the Src.
void swapSuccEdgesProbabilities(const BasicBlock *Src)
Swap outgoing edges probabilities for Src with branch terminator.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Predicate getPredicate() const
Return the predicate for this instruction.
This is the shared class of boolean and integer constants.
static ConstantInt * getTrue(LLVMContext &Context)
Analysis pass which computes a DominatorTree.
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...
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
static IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
unsigned getBitWidth() const
Get the number of bits in this IntegerType.
This is an important class for using LLVM in a threaded context.
Analysis pass that exposes the LoopInfo for a function.
This class is used to constrain loops to run within a given iteration space.
Represents a single loop in the control flow graph.
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.
void abandon()
Mark an analysis as abandoned.
bool empty() const
Determine if the PriorityWorklist is empty or not.
This node represents a polynomial recurrence on the trip count of the specified loop.
const SCEV * getStart() const
const SCEV * getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
bool isAffine() const
Return true if this represents an expression A + B*x where A and B are loop invariant values.
const Loop * getLoop() const
This class represents a constant integer value.
This class represents an analyzed expression in the program.
void print(raw_ostream &OS) const
Print out the internal representation of this scalar to the specified stream.
Type * getType() const
Return the LLVM type of this SCEV expression.
NoWrapFlags
NoWrapFlags are bitfield indices into SubclassData.
Analysis pass that exposes the ScalarEvolution for a function.
The main scalar evolution driver.
const SCEV * getNegativeSCEV(const SCEV *V, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
Return the SCEV object corresponding to -V.
const SCEV * getSMaxExpr(const SCEV *LHS, const SCEV *RHS)
const SCEV * getSMinExpr(const SCEV *LHS, const SCEV *RHS)
const SCEV * getUMaxExpr(const SCEV *LHS, const SCEV *RHS)
const SCEV * getZero(Type *Ty)
Return a SCEV for the constant 0 of a specific type.
bool willNotOverflow(Instruction::BinaryOps BinOp, bool Signed, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI=nullptr)
Is operation BinOp between LHS and RHS provably does not have a signed/unsigned overflow (Signed)?...
const SCEV * getConstant(ConstantInt *V)
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
const SCEV * getNoopOrSignExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
const SCEV * getOne(Type *Ty)
Return a SCEV for the constant 1 of a specific type.
bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
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,...
const SCEV * getUMinExpr(const SCEV *LHS, const SCEV *RHS, bool Sequential=false)
const SCEV * getTruncateExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
const SCEV * getNoopOrZeroExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
const SCEV * getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
const SCEV * getMulExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical multiply expression, or something simpler if possible.
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.
A version of PriorityWorklist that selects small size optimized data structures for the vector and ma...
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
The instances of the Type class are immutable: once they are created, they are never changed.
bool isIntegerTy() const
True if this is an instance of IntegerType.
A Use represents the edge between a Value definition and its users.
const Use & getOperandUse(unsigned i) const
Value * getOperand(unsigned i) const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
An efficient, type-erasing, non-owning reference to a callable.
const ParentTy * getParent() const
This class implements an extremely fast bulk output stream that can only output to a stream.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ C
The default llvm calling convention, compatible with C.
bool match(Val *V, const Pattern &P)
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
BinaryOp_match< LHS, RHS, Instruction::Sub > m_Sub(const LHS &L, const RHS &R)
initializer< Ty > init(const Ty &Val)
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.
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
bool formLCSSARecursively(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)
Put a loop nest into LCSSA form.
void InvertBranch(BranchInst *PBI, IRBuilderBase &Builder)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
void appendLoopsToWorklist(RangeT &&, SmallPriorityWorklist< Loop *, 4 > &)
Utility that implements appending of loops onto a worklist given a range.
bool isKnownNegativeInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE)
Returns true if we can prove that S is defined and always negative in loop L.
constexpr unsigned BitWidth
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
bool isKnownNonNegativeInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE)
Returns true if we can prove that S is defined and always non-negative in 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.
IntegerType * ExitCountTy
static std::optional< LoopStructure > parseLoopStructure(ScalarEvolution &, Loop &, bool, const char *&)