119 cl::desc(
"If set to true, IRCE may eliminate wide range checks in loops "
120 "with narrow latch condition."));
125 "Maximum size of range check type for which can be produced runtime "
126 "overflow check of its limit's computation"));
132#define DEBUG_TYPE "irce"
146class InductiveRangeCheck {
148 const SCEV *Begin =
nullptr;
149 const SCEV *Step =
nullptr;
151 Use *CheckUse =
nullptr;
167 static bool reassociateSubLHS(
Loop *L,
Value *VariantLHS,
Value *InvariantRHS,
172 const SCEV *getBegin()
const {
return Begin; }
173 const SCEV *getStep()
const {
return Step; }
174 const SCEV *getEnd()
const {
return End; }
177 OS <<
"InductiveRangeCheck:\n";
184 OS <<
"\n CheckUse: ";
185 getCheckUse()->getUser()->print(
OS);
186 OS <<
" Operand: " << getCheckUse()->getOperandNo() <<
"\n";
194 Use *getCheckUse()
const {
return CheckUse; }
209 const SCEV *getBegin()
const {
return Begin; }
210 const SCEV *getEnd()
const {
return End; }
223 bool getPassingDirection() {
return true; }
230 bool IsLatchSigned)
const;
237 static void extractRangeChecksFromBranch(
242class InductiveRangeCheckElimination {
259 LoopInfo &LI, GetBFIFunc GetBFI = std::nullopt)
260 : SE(SE), BPI(BPI), DT(DT), LI(LI), GetBFI(GetBFI) {}
271bool InductiveRangeCheck::parseRangeCheckICmp(
Loop *L,
ICmpInst *ICI,
275 auto IsLoopInvariant = [&SE,
L](
Value *
V) {
284 if (IsLoopInvariant(LHS)) {
287 }
else if (!IsLoopInvariant(RHS))
291 if (parseIvAgaisntLimit(L, LHS, RHS, Pred, SE,
Index,
End))
294 if (reassociateSubLHS(L, LHS, RHS, Pred, SE,
Index,
End))
302bool InductiveRangeCheck::parseIvAgaisntLimit(
Loop *L,
Value *LHS,
Value *RHS,
308 auto SIntMaxSCEV = [&](
Type *
T) {
309 unsigned BitWidth = cast<IntegerType>(
T)->getBitWidth();
313 const auto *AddRec = dyn_cast<SCEVAddRecExpr>(SE.
getSCEV(LHS));
325 case ICmpInst::ICMP_SGE:
326 if (
match(RHS, m_ConstantInt<0>())) {
328 End = SIntMaxSCEV(
Index->getType());
333 case ICmpInst::ICMP_SGT:
334 if (
match(RHS, m_ConstantInt<-1>())) {
336 End = SIntMaxSCEV(
Index->getType());
341 case ICmpInst::ICMP_SLT:
342 case ICmpInst::ICMP_ULT:
347 case ICmpInst::ICMP_SLE:
348 case ICmpInst::ICMP_ULE:
351 bool Signed = Pred == ICmpInst::ICMP_SLE;
365bool InductiveRangeCheck::reassociateSubLHS(
376 bool OffsetSubtracted =
false;
382 OffsetSubtracted =
true;
386 const auto *AddRec = dyn_cast<SCEVAddRecExpr>(
IV);
436 case Instruction::Add:
439 case Instruction::Sub:
445 cast<Instruction>(VariantLHS)))
460 if (OffsetSubtracted)
462 Limit = getExprScaledIfOverflow(Instruction::BinaryOps::Add,
Offset, Limit);
465 Limit = getExprScaledIfOverflow(Instruction::BinaryOps::Sub,
Offset, Limit);
466 Pred = ICmpInst::getSwappedPredicate(Pred);
469 if (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SLE) {
471 if (Pred == ICmpInst::ICMP_SLE && Limit)
472 Limit = getExprScaledIfOverflow(Instruction::BinaryOps::Add, Limit,
483void InductiveRangeCheck::extractRangeChecksFromCond(
487 Value *Condition = ConditionUse.
get();
488 if (!Visited.
insert(Condition).second)
493 extractRangeChecksFromCond(L, SE, cast<User>(Condition)->getOperandUse(0),
495 extractRangeChecksFromCond(L, SE, cast<User>(Condition)->getOperandUse(1),
500 ICmpInst *ICI = dyn_cast<ICmpInst>(Condition);
506 if (!parseRangeCheckICmp(L, ICI, SE, IndexAddRec,
End))
509 assert(IndexAddRec &&
"IndexAddRec was not computed");
515 InductiveRangeCheck IRC;
517 IRC.Begin = IndexAddRec->
getStart();
519 IRC.CheckUse = &ConditionUse;
523void InductiveRangeCheck::extractRangeChecksFromBranch(
529 unsigned IndexLoopSucc =
L->contains(BI->
getSuccessor(0)) ? 0 : 1;
531 "No edges coming to loop?");
540 if (IndexLoopSucc != 0) {
549 InductiveRangeCheck::extractRangeChecksFromCond(L, SE, BI->
getOperandUse(0),
563static std::optional<LoopConstrainer::SubRanges>
565 InductiveRangeCheck::Range &Range,
567 auto *RTy = cast<IntegerType>(Range.getType());
581 RTy, SE, IsSignedPredicate);
583 SE, IsSignedPredicate);
591 const SCEV *Smallest =
nullptr, *Greatest =
nullptr, *GreatestSeen =
nullptr;
617 GreatestSeen = Start;
620 auto Clamp = [&SE, Smallest, Greatest, IsSignedPredicate](
const SCEV *S) {
621 return IsSignedPredicate
628 IsSignedPredicate ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_ULE;
630 IsSignedPredicate ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
632 bool ProvablyNoPreloop =
634 if (!ProvablyNoPreloop)
635 Result.LowLimit = Clamp(Range.getBegin());
637 bool ProvablyNoPostLoop =
639 if (!ProvablyNoPostLoop)
640 Result.HighLimit = Clamp(Range.getEnd());
648std::optional<InductiveRangeCheck::Range>
651 bool IsLatchSigned)
const {
654 auto *IVType = dyn_cast<IntegerType>(IndVar->
getType());
655 auto *RCType = dyn_cast<IntegerType>(getBegin()->
getType());
656 auto *EndType = dyn_cast<IntegerType>(getEnd()->
getType());
658 if (!IVType || !RCType)
660 if (IVType->getBitWidth() > RCType->getBitWidth())
691 assert(!
B->isZero() &&
"Recurrence with zero step?");
693 const SCEV *
C = getBegin();
698 assert(!
D->getValue()->isZero() &&
"Recurrence with zero step?");
699 unsigned BitWidth = RCType->getBitWidth();
715 auto ClampedSubtract = [&](
const SCEV *
X,
const SCEV *
Y) {
751 auto SCEVCheckNonNegative = [&](
const SCEV *
X) {
768 auto SCEVCheckWillNotOverflow = [&](
const SCEV *
X) {
772 const SCEV *OverflowCheck =
778 const SCEV *UnderflowCheck =
781 return SE.
getMulExpr(OverflowCheck, UnderflowCheck);
792 const SCEV *REnd = getEnd();
793 const SCEV *EndWillNotOverflow = SE.
getOne(RCType);
797 OS <<
"irce: in function ";
798 OS <<
L->getHeader()->getParent()->getName();
801 OS <<
"there is range check with scaled boundary:\n";
805 if (EndType->getBitWidth() > RCType->getBitWidth()) {
806 assert(EndType->getBitWidth() == RCType->getBitWidth() * 2);
808 PrintRangeCheck(
errs());
817 const SCEV *RuntimeChecks =
818 SE.
getMulExpr(SCEVCheckNonNegative(REnd), EndWillNotOverflow);
819 const SCEV *Begin = SE.
getMulExpr(ClampedSubtract(Zero, M), RuntimeChecks);
822 return InductiveRangeCheck::Range(Begin,
End);
825static std::optional<InductiveRangeCheck::Range>
827 const std::optional<InductiveRangeCheck::Range> &R1,
828 const InductiveRangeCheck::Range &
R2) {
829 if (
R2.isEmpty(SE,
true))
836 assert(!R1Value.isEmpty(SE,
true) &&
837 "We should never have empty R1!");
841 if (R1Value.getType() !=
R2.getType())
848 auto Ret = InductiveRangeCheck::Range(NewBegin, NewEnd);
849 if (Ret.isEmpty(SE,
true))
854static std::optional<InductiveRangeCheck::Range>
856 const std::optional<InductiveRangeCheck::Range> &R1,
857 const InductiveRangeCheck::Range &
R2) {
858 if (
R2.isEmpty(SE,
false))
865 assert(!R1Value.isEmpty(SE,
false) &&
866 "We should never have empty R1!");
870 if (R1Value.getType() !=
R2.getType())
877 auto Ret = InductiveRangeCheck::Range(NewBegin, NewEnd);
878 if (Ret.isEmpty(SE,
false))
898 InductiveRangeCheckElimination IRCE(SE, &BPI, DT, LI, { getBFI });
900 bool Changed =
false;
902 bool CFGChanged =
false;
903 for (
const auto &L : LI) {
904 CFGChanged |=
simplifyLoop(L, &DT, &LI, &SE,
nullptr,
nullptr,
908 Changed |= CFGChanged;
919 auto LPMAddNewLoop = [&Worklist](
Loop *
NL,
bool IsSubloop) {
924 while (!Worklist.
empty()) {
926 if (IRCE.run(L, LPMAddNewLoop)) {
942InductiveRangeCheckElimination::isProfitableToTransform(
const Loop &L,
948 uint64_t hFreq = BFI.getBlockFreq(LS.Header).getFrequency();
949 uint64_t phFreq = BFI.getBlockFreq(L.getLoopPreheader()).getFrequency();
952 <<
"the estimated number of iterations basing on "
953 "frequency info is " << (hFreq / phFreq) <<
"\n";);
965 <<
"the exit probability is too big " << ExitProbability
972bool InductiveRangeCheckElimination::run(
975 LLVM_DEBUG(
dbgs() <<
"irce: giving up constraining loop, too large\n");
987 bool Changed =
false;
989 for (
auto *BBI :
L->getBlocks())
990 if (
BranchInst *TBI = dyn_cast<BranchInst>(BBI->getTerminator()))
991 InductiveRangeCheck::extractRangeChecksFromBranch(TBI, L, SE, BPI,
992 RangeChecks, Changed);
994 if (RangeChecks.
empty())
998 OS <<
"irce: looking at loop ";
L->print(
OS);
999 OS <<
"irce: loop has " << RangeChecks.
size()
1000 <<
" inductive range checks: \n";
1001 for (InductiveRangeCheck &IRC : RangeChecks)
1008 PrintRecognizedRangeChecks(
errs());
1010 const char *FailureReason =
nullptr;
1011 std::optional<LoopStructure> MaybeLoopStructure =
1014 if (!MaybeLoopStructure) {
1016 << FailureReason <<
"\n";);
1025 std::optional<InductiveRangeCheck::Range> SafeIterRange;
1032 auto IntersectRange =
1035 for (InductiveRangeCheck &IRC : RangeChecks) {
1036 auto Result = IRC.computeSafeIterationSpace(SE, IndVar,
1037 LS.IsSignedPredicate);
1039 auto MaybeSafeIterRange = IntersectRange(SE, SafeIterRange, *Result);
1040 if (MaybeSafeIterRange) {
1041 assert(!MaybeSafeIterRange->isEmpty(SE,
LS.IsSignedPredicate) &&
1042 "We should never return empty ranges!");
1044 SafeIterRange = *MaybeSafeIterRange;
1052 std::optional<LoopConstrainer::SubRanges> MaybeSR =
1060 SafeIterRange->getBegin()->getType(), *MaybeSR);
1065 auto PrintConstrainedLoopInfo = [
L]() {
1066 dbgs() <<
"irce: in function ";
1067 dbgs() <<
L->getHeader()->getParent()->getName() <<
": ";
1068 dbgs() <<
"constrained ";
1075 PrintConstrainedLoopInfo();
1079 for (InductiveRangeCheck &IRC : RangeChecksToEliminate) {
1080 ConstantInt *FoldedRangeCheck = IRC.getPassingDirection()
1083 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 *&)