120 cl::desc(
"If set to true, IRCE may eliminate wide range checks in loops "
121 "with narrow latch condition."));
126 "Maximum size of range check type for which can be produced runtime "
127 "overflow check of its limit's computation"));
133#define DEBUG_TYPE "irce"
147class InductiveRangeCheck {
149 const SCEV *Begin =
nullptr;
150 const SCEV *Step =
nullptr;
152 Use *CheckUse =
nullptr;
168 static bool reassociateSubLHS(
Loop *L,
Value *VariantLHS,
Value *InvariantRHS,
173 const SCEV *getBegin()
const {
return Begin; }
174 const SCEV *getStep()
const {
return Step; }
175 const SCEV *getEnd()
const {
return End; }
178 OS <<
"InductiveRangeCheck:\n";
185 OS <<
"\n CheckUse: ";
186 getCheckUse()->getUser()->print(
OS);
187 OS <<
" Operand: " << getCheckUse()->getOperandNo() <<
"\n";
195 Use *getCheckUse()
const {
return CheckUse; }
210 const SCEV *getBegin()
const {
return Begin; }
211 const SCEV *getEnd()
const {
return End; }
224 bool getPassingDirection() {
return true; }
231 bool IsLatchSigned)
const;
238 static void extractRangeChecksFromBranch(
243class InductiveRangeCheckElimination {
260 LoopInfo &LI, GetBFIFunc GetBFI = std::nullopt)
261 : SE(SE), BPI(BPI), DT(DT), LI(LI), GetBFI(GetBFI) {}
272bool InductiveRangeCheck::parseRangeCheckICmp(
Loop *L,
ICmpInst *ICI,
276 auto IsLoopInvariant = [&SE,
L](
Value *
V) {
285 if (IsLoopInvariant(LHS)) {
288 }
else if (!IsLoopInvariant(RHS))
292 if (parseIvAgaisntLimit(L, LHS, RHS, Pred, SE,
Index,
End))
295 if (reassociateSubLHS(L, LHS, RHS, Pred, SE,
Index,
End))
303bool InductiveRangeCheck::parseIvAgaisntLimit(
Loop *L,
Value *LHS,
Value *RHS,
309 auto SIntMaxSCEV = [&](
Type *
T) {
310 unsigned BitWidth = cast<IntegerType>(
T)->getBitWidth();
314 const auto *AddRec = dyn_cast<SCEVAddRecExpr>(SE.
getSCEV(LHS));
326 case ICmpInst::ICMP_SGE:
327 if (
match(RHS, m_ConstantInt<0>())) {
329 End = SIntMaxSCEV(
Index->getType());
334 case ICmpInst::ICMP_SGT:
335 if (
match(RHS, m_ConstantInt<-1>())) {
337 End = SIntMaxSCEV(
Index->getType());
342 case ICmpInst::ICMP_SLT:
343 case ICmpInst::ICMP_ULT:
348 case ICmpInst::ICMP_SLE:
349 case ICmpInst::ICMP_ULE:
352 bool Signed = Pred == ICmpInst::ICMP_SLE;
366bool InductiveRangeCheck::reassociateSubLHS(
377 bool OffsetSubtracted =
false;
383 OffsetSubtracted =
true;
387 const auto *AddRec = dyn_cast<SCEVAddRecExpr>(
IV);
437 case Instruction::Add:
440 case Instruction::Sub:
446 cast<Instruction>(VariantLHS)))
461 if (OffsetSubtracted)
463 Limit = getExprScaledIfOverflow(Instruction::BinaryOps::Add,
Offset, Limit);
466 Limit = getExprScaledIfOverflow(Instruction::BinaryOps::Sub,
Offset, Limit);
467 Pred = ICmpInst::getSwappedPredicate(Pred);
470 if (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SLE) {
472 if (Pred == ICmpInst::ICMP_SLE && Limit)
473 Limit = getExprScaledIfOverflow(Instruction::BinaryOps::Add, Limit,
484void InductiveRangeCheck::extractRangeChecksFromCond(
488 Value *Condition = ConditionUse.
get();
489 if (!Visited.
insert(Condition).second)
494 extractRangeChecksFromCond(L, SE, cast<User>(Condition)->getOperandUse(0),
496 extractRangeChecksFromCond(L, SE, cast<User>(Condition)->getOperandUse(1),
501 ICmpInst *ICI = dyn_cast<ICmpInst>(Condition);
507 if (!parseRangeCheckICmp(L, ICI, SE, IndexAddRec,
End))
510 assert(IndexAddRec &&
"IndexAddRec was not computed");
516 InductiveRangeCheck IRC;
518 IRC.Begin = IndexAddRec->
getStart();
520 IRC.CheckUse = &ConditionUse;
524void InductiveRangeCheck::extractRangeChecksFromBranch(
530 unsigned IndexLoopSucc =
L->contains(BI->
getSuccessor(0)) ? 0 : 1;
532 "No edges coming to loop?");
541 if (IndexLoopSucc != 0) {
550 InductiveRangeCheck::extractRangeChecksFromCond(L, SE, BI->
getOperandUse(0),
564static std::optional<LoopConstrainer::SubRanges>
566 InductiveRangeCheck::Range &Range,
568 auto *RTy = cast<IntegerType>(Range.getType());
582 RTy, SE, IsSignedPredicate);
584 SE, IsSignedPredicate);
592 const SCEV *Smallest =
nullptr, *Greatest =
nullptr, *GreatestSeen =
nullptr;
618 GreatestSeen = Start;
621 auto Clamp = [&SE, Smallest, Greatest, IsSignedPredicate](
const SCEV *S) {
622 return IsSignedPredicate
629 IsSignedPredicate ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_ULE;
631 IsSignedPredicate ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
633 bool ProvablyNoPreloop =
635 if (!ProvablyNoPreloop)
636 Result.LowLimit = Clamp(Range.getBegin());
638 bool ProvablyNoPostLoop =
640 if (!ProvablyNoPostLoop)
641 Result.HighLimit = Clamp(Range.getEnd());
649std::optional<InductiveRangeCheck::Range>
652 bool IsLatchSigned)
const {
655 auto *IVType = dyn_cast<IntegerType>(IndVar->
getType());
656 auto *RCType = dyn_cast<IntegerType>(getBegin()->
getType());
657 auto *EndType = dyn_cast<IntegerType>(getEnd()->
getType());
659 if (!IVType || !RCType)
661 if (IVType->getBitWidth() > RCType->getBitWidth())
692 assert(!
B->isZero() &&
"Recurrence with zero step?");
694 const SCEV *
C = getBegin();
699 assert(!
D->getValue()->isZero() &&
"Recurrence with zero step?");
700 unsigned BitWidth = RCType->getBitWidth();
716 auto ClampedSubtract = [&](
const SCEV *
X,
const SCEV *
Y) {
752 auto SCEVCheckNonNegative = [&](
const SCEV *
X) {
769 auto SCEVCheckWillNotOverflow = [&](
const SCEV *
X) {
773 const SCEV *OverflowCheck =
779 const SCEV *UnderflowCheck =
782 return SE.
getMulExpr(OverflowCheck, UnderflowCheck);
793 const SCEV *REnd = getEnd();
794 const SCEV *EndWillNotOverflow = SE.
getOne(RCType);
798 OS <<
"irce: in function ";
799 OS <<
L->getHeader()->getParent()->getName();
802 OS <<
"there is range check with scaled boundary:\n";
806 if (EndType->getBitWidth() > RCType->getBitWidth()) {
807 assert(EndType->getBitWidth() == RCType->getBitWidth() * 2);
809 PrintRangeCheck(
errs());
818 const SCEV *RuntimeChecks =
819 SE.
getMulExpr(SCEVCheckNonNegative(REnd), EndWillNotOverflow);
820 const SCEV *Begin = SE.
getMulExpr(ClampedSubtract(Zero, M), RuntimeChecks);
823 return InductiveRangeCheck::Range(Begin,
End);
826static std::optional<InductiveRangeCheck::Range>
828 const std::optional<InductiveRangeCheck::Range> &R1,
829 const InductiveRangeCheck::Range &
R2) {
830 if (
R2.isEmpty(SE,
true))
837 assert(!R1Value.isEmpty(SE,
true) &&
838 "We should never have empty R1!");
842 if (R1Value.getType() !=
R2.getType())
849 auto Ret = InductiveRangeCheck::Range(NewBegin, NewEnd);
850 if (Ret.isEmpty(SE,
true))
855static std::optional<InductiveRangeCheck::Range>
857 const std::optional<InductiveRangeCheck::Range> &R1,
858 const InductiveRangeCheck::Range &
R2) {
859 if (
R2.isEmpty(SE,
false))
866 assert(!R1Value.isEmpty(SE,
false) &&
867 "We should never have empty R1!");
871 if (R1Value.getType() !=
R2.getType())
878 auto Ret = InductiveRangeCheck::Range(NewBegin, NewEnd);
879 if (Ret.isEmpty(SE,
false))
899 InductiveRangeCheckElimination IRCE(SE, &BPI, DT, LI, { getBFI });
901 bool Changed =
false;
903 bool CFGChanged =
false;
904 for (
const auto &L : LI) {
905 CFGChanged |=
simplifyLoop(L, &DT, &LI, &SE,
nullptr,
nullptr,
909 Changed |= CFGChanged;
920 auto LPMAddNewLoop = [&Worklist](
Loop *
NL,
bool IsSubloop) {
925 while (!Worklist.
empty()) {
927 if (IRCE.run(L, LPMAddNewLoop)) {
943InductiveRangeCheckElimination::isProfitableToTransform(
const Loop &L,
949 uint64_t hFreq = BFI.getBlockFreq(LS.Header).getFrequency();
950 uint64_t phFreq = BFI.getBlockFreq(L.getLoopPreheader()).getFrequency();
953 <<
"the estimated number of iterations basing on "
954 "frequency info is " << (hFreq / phFreq) <<
"\n";);
966 <<
"the exit probability is too big " << ExitProbability
973bool InductiveRangeCheckElimination::run(
976 LLVM_DEBUG(
dbgs() <<
"irce: giving up constraining loop, too large\n");
988 bool Changed =
false;
990 for (
auto *BBI :
L->getBlocks())
991 if (
BranchInst *TBI = dyn_cast<BranchInst>(BBI->getTerminator()))
992 InductiveRangeCheck::extractRangeChecksFromBranch(TBI, L, SE, BPI,
993 RangeChecks, Changed);
995 if (RangeChecks.
empty())
999 OS <<
"irce: looking at loop ";
L->print(
OS);
1000 OS <<
"irce: loop has " << RangeChecks.
size()
1001 <<
" inductive range checks: \n";
1002 for (InductiveRangeCheck &IRC : RangeChecks)
1009 PrintRecognizedRangeChecks(
errs());
1011 const char *FailureReason =
nullptr;
1012 std::optional<LoopStructure> MaybeLoopStructure =
1015 if (!MaybeLoopStructure) {
1017 << FailureReason <<
"\n";);
1026 std::optional<InductiveRangeCheck::Range> SafeIterRange;
1033 auto IntersectRange =
1036 for (InductiveRangeCheck &IRC : RangeChecks) {
1037 auto Result = IRC.computeSafeIterationSpace(SE, IndVar,
1038 LS.IsSignedPredicate);
1040 auto MaybeSafeIterRange = IntersectRange(SE, SafeIterRange, *Result);
1041 if (MaybeSafeIterRange) {
1042 assert(!MaybeSafeIterRange->isEmpty(SE,
LS.IsSignedPredicate) &&
1043 "We should never return empty ranges!");
1045 SafeIterRange = *MaybeSafeIterRange;
1053 std::optional<LoopConstrainer::SubRanges> MaybeSR =
1061 SafeIterRange->getBegin()->getType(), *MaybeSR);
1066 auto PrintConstrainedLoopInfo = [
L]() {
1067 dbgs() <<
"irce: in function ";
1068 dbgs() <<
L->getHeader()->getParent()->getName() <<
": ";
1069 dbgs() <<
"constrained ";
1076 PrintConstrainedLoopInfo();
1080 for (InductiveRangeCheck &IRC : RangeChecksToEliminate) {
1081 ConstantInt *FoldedRangeCheck = IRC.getPassingDirection()
1084 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...
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.
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)
This defines the Use class.
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)
const BasicBlock * getParent() const
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.
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.
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 *&)