10b57cec5SDimitry Andric //===- InductiveRangeCheckElimination.cpp - -------------------------------===//
20b57cec5SDimitry Andric //
30b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
40b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information.
50b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
60b57cec5SDimitry Andric //
70b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
80b57cec5SDimitry Andric //
90b57cec5SDimitry Andric // The InductiveRangeCheckElimination pass splits a loop's iteration space into
100b57cec5SDimitry Andric // three disjoint ranges. It does that in a way such that the loop running in
110b57cec5SDimitry Andric // the middle loop provably does not need range checks. As an example, it will
120b57cec5SDimitry Andric // convert
130b57cec5SDimitry Andric //
140b57cec5SDimitry Andric // len = < known positive >
150b57cec5SDimitry Andric // for (i = 0; i < n; i++) {
160b57cec5SDimitry Andric // if (0 <= i && i < len) {
170b57cec5SDimitry Andric // do_something();
180b57cec5SDimitry Andric // } else {
190b57cec5SDimitry Andric // throw_out_of_bounds();
200b57cec5SDimitry Andric // }
210b57cec5SDimitry Andric // }
220b57cec5SDimitry Andric //
230b57cec5SDimitry Andric // to
240b57cec5SDimitry Andric //
250b57cec5SDimitry Andric // len = < known positive >
260b57cec5SDimitry Andric // limit = smin(n, len)
270b57cec5SDimitry Andric // // no first segment
280b57cec5SDimitry Andric // for (i = 0; i < limit; i++) {
290b57cec5SDimitry Andric // if (0 <= i && i < len) { // this check is fully redundant
300b57cec5SDimitry Andric // do_something();
310b57cec5SDimitry Andric // } else {
320b57cec5SDimitry Andric // throw_out_of_bounds();
330b57cec5SDimitry Andric // }
340b57cec5SDimitry Andric // }
350b57cec5SDimitry Andric // for (i = limit; i < n; i++) {
360b57cec5SDimitry Andric // if (0 <= i && i < len) {
370b57cec5SDimitry Andric // do_something();
380b57cec5SDimitry Andric // } else {
390b57cec5SDimitry Andric // throw_out_of_bounds();
400b57cec5SDimitry Andric // }
410b57cec5SDimitry Andric // }
420b57cec5SDimitry Andric //
430b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
440b57cec5SDimitry Andric
450b57cec5SDimitry Andric #include "llvm/Transforms/Scalar/InductiveRangeCheckElimination.h"
460b57cec5SDimitry Andric #include "llvm/ADT/APInt.h"
470b57cec5SDimitry Andric #include "llvm/ADT/ArrayRef.h"
485ffd83dbSDimitry Andric #include "llvm/ADT/PriorityWorklist.h"
490b57cec5SDimitry Andric #include "llvm/ADT/SmallPtrSet.h"
500b57cec5SDimitry Andric #include "llvm/ADT/SmallVector.h"
510b57cec5SDimitry Andric #include "llvm/ADT/StringRef.h"
520b57cec5SDimitry Andric #include "llvm/ADT/Twine.h"
53e8d8bef9SDimitry Andric #include "llvm/Analysis/BlockFrequencyInfo.h"
540b57cec5SDimitry Andric #include "llvm/Analysis/BranchProbabilityInfo.h"
550b57cec5SDimitry Andric #include "llvm/Analysis/LoopAnalysisManager.h"
560b57cec5SDimitry Andric #include "llvm/Analysis/LoopInfo.h"
570b57cec5SDimitry Andric #include "llvm/Analysis/ScalarEvolution.h"
580b57cec5SDimitry Andric #include "llvm/Analysis/ScalarEvolutionExpressions.h"
590b57cec5SDimitry Andric #include "llvm/IR/BasicBlock.h"
600b57cec5SDimitry Andric #include "llvm/IR/CFG.h"
610b57cec5SDimitry Andric #include "llvm/IR/Constants.h"
620b57cec5SDimitry Andric #include "llvm/IR/DerivedTypes.h"
630b57cec5SDimitry Andric #include "llvm/IR/Dominators.h"
640b57cec5SDimitry Andric #include "llvm/IR/Function.h"
650b57cec5SDimitry Andric #include "llvm/IR/IRBuilder.h"
660b57cec5SDimitry Andric #include "llvm/IR/InstrTypes.h"
670b57cec5SDimitry Andric #include "llvm/IR/Instructions.h"
680b57cec5SDimitry Andric #include "llvm/IR/Metadata.h"
690b57cec5SDimitry Andric #include "llvm/IR/Module.h"
700b57cec5SDimitry Andric #include "llvm/IR/PatternMatch.h"
710b57cec5SDimitry Andric #include "llvm/IR/Type.h"
720b57cec5SDimitry Andric #include "llvm/IR/Use.h"
730b57cec5SDimitry Andric #include "llvm/IR/User.h"
740b57cec5SDimitry Andric #include "llvm/IR/Value.h"
750b57cec5SDimitry Andric #include "llvm/Support/BranchProbability.h"
760b57cec5SDimitry Andric #include "llvm/Support/Casting.h"
770b57cec5SDimitry Andric #include "llvm/Support/CommandLine.h"
780b57cec5SDimitry Andric #include "llvm/Support/Compiler.h"
790b57cec5SDimitry Andric #include "llvm/Support/Debug.h"
800b57cec5SDimitry Andric #include "llvm/Support/ErrorHandling.h"
810b57cec5SDimitry Andric #include "llvm/Support/raw_ostream.h"
8206c3fb27SDimitry Andric #include "llvm/Transforms/Utils/BasicBlockUtils.h"
830b57cec5SDimitry Andric #include "llvm/Transforms/Utils/Cloning.h"
845f757f3fSDimitry Andric #include "llvm/Transforms/Utils/LoopConstrainer.h"
850b57cec5SDimitry Andric #include "llvm/Transforms/Utils/LoopSimplify.h"
860b57cec5SDimitry Andric #include "llvm/Transforms/Utils/LoopUtils.h"
875ffd83dbSDimitry Andric #include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
880b57cec5SDimitry Andric #include "llvm/Transforms/Utils/ValueMapper.h"
890b57cec5SDimitry Andric #include <algorithm>
900b57cec5SDimitry Andric #include <cassert>
910b57cec5SDimitry Andric #include <iterator>
92bdd1243dSDimitry Andric #include <optional>
930b57cec5SDimitry Andric #include <utility>
940b57cec5SDimitry Andric
950b57cec5SDimitry Andric using namespace llvm;
960b57cec5SDimitry Andric using namespace llvm::PatternMatch;
970b57cec5SDimitry Andric
980b57cec5SDimitry Andric static cl::opt<unsigned> LoopSizeCutoff("irce-loop-size-cutoff", cl::Hidden,
990b57cec5SDimitry Andric cl::init(64));
1000b57cec5SDimitry Andric
1010b57cec5SDimitry Andric static cl::opt<bool> PrintChangedLoops("irce-print-changed-loops", cl::Hidden,
1020b57cec5SDimitry Andric cl::init(false));
1030b57cec5SDimitry Andric
1040b57cec5SDimitry Andric static cl::opt<bool> PrintRangeChecks("irce-print-range-checks", cl::Hidden,
1050b57cec5SDimitry Andric cl::init(false));
1060b57cec5SDimitry Andric
1070b57cec5SDimitry Andric static cl::opt<bool> SkipProfitabilityChecks("irce-skip-profitability-checks",
1080b57cec5SDimitry Andric cl::Hidden, cl::init(false));
1090b57cec5SDimitry Andric
110e8d8bef9SDimitry Andric static cl::opt<unsigned> MinRuntimeIterations("irce-min-runtime-iterations",
111e8d8bef9SDimitry Andric cl::Hidden, cl::init(10));
112e8d8bef9SDimitry Andric
1130b57cec5SDimitry Andric static cl::opt<bool> AllowUnsignedLatchCondition("irce-allow-unsigned-latch",
1140b57cec5SDimitry Andric cl::Hidden, cl::init(true));
1150b57cec5SDimitry Andric
1160b57cec5SDimitry Andric static cl::opt<bool> AllowNarrowLatchCondition(
1170b57cec5SDimitry Andric "irce-allow-narrow-latch", cl::Hidden, cl::init(true),
1180b57cec5SDimitry Andric cl::desc("If set to true, IRCE may eliminate wide range checks in loops "
1190b57cec5SDimitry Andric "with narrow latch condition."));
1200b57cec5SDimitry Andric
12106c3fb27SDimitry Andric static cl::opt<unsigned> MaxTypeSizeForOverflowCheck(
12206c3fb27SDimitry Andric "irce-max-type-size-for-overflow-check", cl::Hidden, cl::init(32),
12306c3fb27SDimitry Andric cl::desc(
12406c3fb27SDimitry Andric "Maximum size of range check type for which can be produced runtime "
12506c3fb27SDimitry Andric "overflow check of its limit's computation"));
12606c3fb27SDimitry Andric
12706c3fb27SDimitry Andric static cl::opt<bool>
12806c3fb27SDimitry Andric PrintScaledBoundaryRangeChecks("irce-print-scaled-boundary-range-checks",
12906c3fb27SDimitry Andric cl::Hidden, cl::init(false));
13006c3fb27SDimitry Andric
1310b57cec5SDimitry Andric #define DEBUG_TYPE "irce"
1320b57cec5SDimitry Andric
1330b57cec5SDimitry Andric namespace {
1340b57cec5SDimitry Andric
1350b57cec5SDimitry Andric /// An inductive range check is conditional branch in a loop with
1360b57cec5SDimitry Andric ///
1370b57cec5SDimitry Andric /// 1. a very cold successor (i.e. the branch jumps to that successor very
1380b57cec5SDimitry Andric /// rarely)
1390b57cec5SDimitry Andric ///
1400b57cec5SDimitry Andric /// and
1410b57cec5SDimitry Andric ///
1420b57cec5SDimitry Andric /// 2. a condition that is provably true for some contiguous range of values
1430b57cec5SDimitry Andric /// taken by the containing loop's induction variable.
1440b57cec5SDimitry Andric ///
1450b57cec5SDimitry Andric class InductiveRangeCheck {
1460b57cec5SDimitry Andric
1470b57cec5SDimitry Andric const SCEV *Begin = nullptr;
1480b57cec5SDimitry Andric const SCEV *Step = nullptr;
1490b57cec5SDimitry Andric const SCEV *End = nullptr;
1500b57cec5SDimitry Andric Use *CheckUse = nullptr;
1510b57cec5SDimitry Andric
1520b57cec5SDimitry Andric static bool parseRangeCheckICmp(Loop *L, ICmpInst *ICI, ScalarEvolution &SE,
15306c3fb27SDimitry Andric const SCEVAddRecExpr *&Index,
15406c3fb27SDimitry Andric const SCEV *&End);
1550b57cec5SDimitry Andric
1560b57cec5SDimitry Andric static void
1570b57cec5SDimitry Andric extractRangeChecksFromCond(Loop *L, ScalarEvolution &SE, Use &ConditionUse,
1580b57cec5SDimitry Andric SmallVectorImpl<InductiveRangeCheck> &Checks,
1590b57cec5SDimitry Andric SmallPtrSetImpl<Value *> &Visited);
1600b57cec5SDimitry Andric
16106c3fb27SDimitry Andric static bool parseIvAgaisntLimit(Loop *L, Value *LHS, Value *RHS,
16206c3fb27SDimitry Andric ICmpInst::Predicate Pred, ScalarEvolution &SE,
16306c3fb27SDimitry Andric const SCEVAddRecExpr *&Index,
16406c3fb27SDimitry Andric const SCEV *&End);
16506c3fb27SDimitry Andric
16606c3fb27SDimitry Andric static bool reassociateSubLHS(Loop *L, Value *VariantLHS, Value *InvariantRHS,
16706c3fb27SDimitry Andric ICmpInst::Predicate Pred, ScalarEvolution &SE,
16806c3fb27SDimitry Andric const SCEVAddRecExpr *&Index, const SCEV *&End);
16906c3fb27SDimitry Andric
1700b57cec5SDimitry Andric public:
getBegin() const1710b57cec5SDimitry Andric const SCEV *getBegin() const { return Begin; }
getStep() const1720b57cec5SDimitry Andric const SCEV *getStep() const { return Step; }
getEnd() const1730b57cec5SDimitry Andric const SCEV *getEnd() const { return End; }
1740b57cec5SDimitry Andric
print(raw_ostream & OS) const1750b57cec5SDimitry Andric void print(raw_ostream &OS) const {
1760b57cec5SDimitry Andric OS << "InductiveRangeCheck:\n";
1770b57cec5SDimitry Andric OS << " Begin: ";
1780b57cec5SDimitry Andric Begin->print(OS);
1790b57cec5SDimitry Andric OS << " Step: ";
1800b57cec5SDimitry Andric Step->print(OS);
1810b57cec5SDimitry Andric OS << " End: ";
1820b57cec5SDimitry Andric End->print(OS);
1830b57cec5SDimitry Andric OS << "\n CheckUse: ";
1840b57cec5SDimitry Andric getCheckUse()->getUser()->print(OS);
1850b57cec5SDimitry Andric OS << " Operand: " << getCheckUse()->getOperandNo() << "\n";
1860b57cec5SDimitry Andric }
1870b57cec5SDimitry Andric
1880b57cec5SDimitry Andric LLVM_DUMP_METHOD
dump()1890b57cec5SDimitry Andric void dump() {
1900b57cec5SDimitry Andric print(dbgs());
1910b57cec5SDimitry Andric }
1920b57cec5SDimitry Andric
getCheckUse() const1930b57cec5SDimitry Andric Use *getCheckUse() const { return CheckUse; }
1940b57cec5SDimitry Andric
1950b57cec5SDimitry Andric /// Represents an signed integer range [Range.getBegin(), Range.getEnd()). If
1960b57cec5SDimitry Andric /// R.getEnd() le R.getBegin(), then R denotes the empty range.
1970b57cec5SDimitry Andric
1980b57cec5SDimitry Andric class Range {
1990b57cec5SDimitry Andric const SCEV *Begin;
2000b57cec5SDimitry Andric const SCEV *End;
2010b57cec5SDimitry Andric
2020b57cec5SDimitry Andric public:
Range(const SCEV * Begin,const SCEV * End)2030b57cec5SDimitry Andric Range(const SCEV *Begin, const SCEV *End) : Begin(Begin), End(End) {
2040b57cec5SDimitry Andric assert(Begin->getType() == End->getType() && "ill-typed range!");
2050b57cec5SDimitry Andric }
2060b57cec5SDimitry Andric
getType() const2070b57cec5SDimitry Andric Type *getType() const { return Begin->getType(); }
getBegin() const2080b57cec5SDimitry Andric const SCEV *getBegin() const { return Begin; }
getEnd() const2090b57cec5SDimitry Andric const SCEV *getEnd() const { return End; }
isEmpty(ScalarEvolution & SE,bool IsSigned) const2100b57cec5SDimitry Andric bool isEmpty(ScalarEvolution &SE, bool IsSigned) const {
2110b57cec5SDimitry Andric if (Begin == End)
2120b57cec5SDimitry Andric return true;
2130b57cec5SDimitry Andric if (IsSigned)
2140b57cec5SDimitry Andric return SE.isKnownPredicate(ICmpInst::ICMP_SGE, Begin, End);
2150b57cec5SDimitry Andric else
2160b57cec5SDimitry Andric return SE.isKnownPredicate(ICmpInst::ICMP_UGE, Begin, End);
2170b57cec5SDimitry Andric }
2180b57cec5SDimitry Andric };
2190b57cec5SDimitry Andric
2200b57cec5SDimitry Andric /// This is the value the condition of the branch needs to evaluate to for the
2210b57cec5SDimitry Andric /// branch to take the hot successor (see (1) above).
getPassingDirection()2220b57cec5SDimitry Andric bool getPassingDirection() { return true; }
2230b57cec5SDimitry Andric
2240b57cec5SDimitry Andric /// Computes a range for the induction variable (IndVar) in which the range
2250b57cec5SDimitry Andric /// check is redundant and can be constant-folded away. The induction
2260b57cec5SDimitry Andric /// variable is not required to be the canonical {0,+,1} induction variable.
227bdd1243dSDimitry Andric std::optional<Range> computeSafeIterationSpace(ScalarEvolution &SE,
2280b57cec5SDimitry Andric const SCEVAddRecExpr *IndVar,
2290b57cec5SDimitry Andric bool IsLatchSigned) const;
2300b57cec5SDimitry Andric
2310b57cec5SDimitry Andric /// Parse out a set of inductive range checks from \p BI and append them to \p
2320b57cec5SDimitry Andric /// Checks.
2330b57cec5SDimitry Andric ///
2340b57cec5SDimitry Andric /// NB! There may be conditions feeding into \p BI that aren't inductive range
2350b57cec5SDimitry Andric /// checks, and hence don't end up in \p Checks.
23606c3fb27SDimitry Andric static void extractRangeChecksFromBranch(
23706c3fb27SDimitry Andric BranchInst *BI, Loop *L, ScalarEvolution &SE, BranchProbabilityInfo *BPI,
23806c3fb27SDimitry Andric SmallVectorImpl<InductiveRangeCheck> &Checks, bool &Changed);
2390b57cec5SDimitry Andric };
2400b57cec5SDimitry Andric
2410b57cec5SDimitry Andric class InductiveRangeCheckElimination {
2420b57cec5SDimitry Andric ScalarEvolution &SE;
2430b57cec5SDimitry Andric BranchProbabilityInfo *BPI;
2440b57cec5SDimitry Andric DominatorTree &DT;
2450b57cec5SDimitry Andric LoopInfo &LI;
2460b57cec5SDimitry Andric
247e8d8bef9SDimitry Andric using GetBFIFunc =
248bdd1243dSDimitry Andric std::optional<llvm::function_ref<llvm::BlockFrequencyInfo &()>>;
249e8d8bef9SDimitry Andric GetBFIFunc GetBFI;
250e8d8bef9SDimitry Andric
251e8d8bef9SDimitry Andric // Returns true if it is profitable to do a transform basing on estimation of
252e8d8bef9SDimitry Andric // number of iterations.
253e8d8bef9SDimitry Andric bool isProfitableToTransform(const Loop &L, LoopStructure &LS);
254e8d8bef9SDimitry Andric
2550b57cec5SDimitry Andric public:
InductiveRangeCheckElimination(ScalarEvolution & SE,BranchProbabilityInfo * BPI,DominatorTree & DT,LoopInfo & LI,GetBFIFunc GetBFI=std::nullopt)2560b57cec5SDimitry Andric InductiveRangeCheckElimination(ScalarEvolution &SE,
2570b57cec5SDimitry Andric BranchProbabilityInfo *BPI, DominatorTree &DT,
258bdd1243dSDimitry Andric LoopInfo &LI, GetBFIFunc GetBFI = std::nullopt)
259e8d8bef9SDimitry Andric : SE(SE), BPI(BPI), DT(DT), LI(LI), GetBFI(GetBFI) {}
2600b57cec5SDimitry Andric
2610b57cec5SDimitry Andric bool run(Loop *L, function_ref<void(Loop *, bool)> LPMAddNewLoop);
2620b57cec5SDimitry Andric };
2630b57cec5SDimitry Andric
2640b57cec5SDimitry Andric } // end anonymous namespace
2650b57cec5SDimitry Andric
2660b57cec5SDimitry Andric /// Parse a single ICmp instruction, `ICI`, into a range check. If `ICI` cannot
26706c3fb27SDimitry Andric /// be interpreted as a range check, return false. Otherwise set `Index` to the
26806c3fb27SDimitry Andric /// SCEV being range checked, and set `End` to the upper or lower limit `Index`
26906c3fb27SDimitry Andric /// is being range checked.
parseRangeCheckICmp(Loop * L,ICmpInst * ICI,ScalarEvolution & SE,const SCEVAddRecExpr * & Index,const SCEV * & End)27006c3fb27SDimitry Andric bool InductiveRangeCheck::parseRangeCheckICmp(Loop *L, ICmpInst *ICI,
27106c3fb27SDimitry Andric ScalarEvolution &SE,
27206c3fb27SDimitry Andric const SCEVAddRecExpr *&Index,
27306c3fb27SDimitry Andric const SCEV *&End) {
2740b57cec5SDimitry Andric auto IsLoopInvariant = [&SE, L](Value *V) {
2750b57cec5SDimitry Andric return SE.isLoopInvariant(SE.getSCEV(V), L);
2760b57cec5SDimitry Andric };
2770b57cec5SDimitry Andric
2780b57cec5SDimitry Andric ICmpInst::Predicate Pred = ICI->getPredicate();
2790b57cec5SDimitry Andric Value *LHS = ICI->getOperand(0);
2800b57cec5SDimitry Andric Value *RHS = ICI->getOperand(1);
2810b57cec5SDimitry Andric
282*5678d1d9SDimitry Andric if (!LHS->getType()->isIntegerTy())
283*5678d1d9SDimitry Andric return false;
284*5678d1d9SDimitry Andric
28506c3fb27SDimitry Andric // Canonicalize to the `Index Pred Invariant` comparison
28606c3fb27SDimitry Andric if (IsLoopInvariant(LHS)) {
28706c3fb27SDimitry Andric std::swap(LHS, RHS);
28806c3fb27SDimitry Andric Pred = CmpInst::getSwappedPredicate(Pred);
28906c3fb27SDimitry Andric } else if (!IsLoopInvariant(RHS))
29006c3fb27SDimitry Andric // Both LHS and RHS are loop variant
29106c3fb27SDimitry Andric return false;
29206c3fb27SDimitry Andric
29306c3fb27SDimitry Andric if (parseIvAgaisntLimit(L, LHS, RHS, Pred, SE, Index, End))
29406c3fb27SDimitry Andric return true;
29506c3fb27SDimitry Andric
29606c3fb27SDimitry Andric if (reassociateSubLHS(L, LHS, RHS, Pred, SE, Index, End))
29706c3fb27SDimitry Andric return true;
29806c3fb27SDimitry Andric
29906c3fb27SDimitry Andric // TODO: support ReassociateAddLHS
30006c3fb27SDimitry Andric return false;
30106c3fb27SDimitry Andric }
30206c3fb27SDimitry Andric
30306c3fb27SDimitry Andric // Try to parse range check in the form of "IV vs Limit"
parseIvAgaisntLimit(Loop * L,Value * LHS,Value * RHS,ICmpInst::Predicate Pred,ScalarEvolution & SE,const SCEVAddRecExpr * & Index,const SCEV * & End)30406c3fb27SDimitry Andric bool InductiveRangeCheck::parseIvAgaisntLimit(Loop *L, Value *LHS, Value *RHS,
30506c3fb27SDimitry Andric ICmpInst::Predicate Pred,
30606c3fb27SDimitry Andric ScalarEvolution &SE,
30706c3fb27SDimitry Andric const SCEVAddRecExpr *&Index,
30806c3fb27SDimitry Andric const SCEV *&End) {
30906c3fb27SDimitry Andric
31006c3fb27SDimitry Andric auto SIntMaxSCEV = [&](Type *T) {
31106c3fb27SDimitry Andric unsigned BitWidth = cast<IntegerType>(T)->getBitWidth();
31206c3fb27SDimitry Andric return SE.getConstant(APInt::getSignedMaxValue(BitWidth));
31306c3fb27SDimitry Andric };
31406c3fb27SDimitry Andric
31506c3fb27SDimitry Andric const auto *AddRec = dyn_cast<SCEVAddRecExpr>(SE.getSCEV(LHS));
31606c3fb27SDimitry Andric if (!AddRec)
31706c3fb27SDimitry Andric return false;
31806c3fb27SDimitry Andric
31906c3fb27SDimitry Andric // We strengthen "0 <= I" to "0 <= I < INT_SMAX" and "I < L" to "0 <= I < L".
32006c3fb27SDimitry Andric // We can potentially do much better here.
32106c3fb27SDimitry Andric // If we want to adjust upper bound for the unsigned range check as we do it
32206c3fb27SDimitry Andric // for signed one, we will need to pick Unsigned max
3230b57cec5SDimitry Andric switch (Pred) {
3240b57cec5SDimitry Andric default:
3250b57cec5SDimitry Andric return false;
3260b57cec5SDimitry Andric
3270b57cec5SDimitry Andric case ICmpInst::ICMP_SGE:
3280b57cec5SDimitry Andric if (match(RHS, m_ConstantInt<0>())) {
32906c3fb27SDimitry Andric Index = AddRec;
33006c3fb27SDimitry Andric End = SIntMaxSCEV(Index->getType());
33106c3fb27SDimitry Andric return true;
33206c3fb27SDimitry Andric }
33306c3fb27SDimitry Andric return false;
33406c3fb27SDimitry Andric
33506c3fb27SDimitry Andric case ICmpInst::ICMP_SGT:
33606c3fb27SDimitry Andric if (match(RHS, m_ConstantInt<-1>())) {
33706c3fb27SDimitry Andric Index = AddRec;
33806c3fb27SDimitry Andric End = SIntMaxSCEV(Index->getType());
33906c3fb27SDimitry Andric return true;
3400b57cec5SDimitry Andric }
3410b57cec5SDimitry Andric return false;
3420b57cec5SDimitry Andric
3430b57cec5SDimitry Andric case ICmpInst::ICMP_SLT:
3440b57cec5SDimitry Andric case ICmpInst::ICMP_ULT:
34506c3fb27SDimitry Andric Index = AddRec;
34606c3fb27SDimitry Andric End = SE.getSCEV(RHS);
34706c3fb27SDimitry Andric return true;
34806c3fb27SDimitry Andric
34906c3fb27SDimitry Andric case ICmpInst::ICMP_SLE:
35006c3fb27SDimitry Andric case ICmpInst::ICMP_ULE:
35106c3fb27SDimitry Andric const SCEV *One = SE.getOne(RHS->getType());
35206c3fb27SDimitry Andric const SCEV *RHSS = SE.getSCEV(RHS);
35306c3fb27SDimitry Andric bool Signed = Pred == ICmpInst::ICMP_SLE;
35406c3fb27SDimitry Andric if (SE.willNotOverflow(Instruction::BinaryOps::Add, Signed, RHSS, One)) {
35506c3fb27SDimitry Andric Index = AddRec;
35606c3fb27SDimitry Andric End = SE.getAddExpr(RHSS, One);
35706c3fb27SDimitry Andric return true;
3580b57cec5SDimitry Andric }
3590b57cec5SDimitry Andric return false;
3600b57cec5SDimitry Andric }
3610b57cec5SDimitry Andric
3620b57cec5SDimitry Andric llvm_unreachable("default clause returns!");
3630b57cec5SDimitry Andric }
3640b57cec5SDimitry Andric
36506c3fb27SDimitry Andric // Try to parse range check in the form of "IV - Offset vs Limit" or "Offset -
36606c3fb27SDimitry Andric // IV vs Limit"
reassociateSubLHS(Loop * L,Value * VariantLHS,Value * InvariantRHS,ICmpInst::Predicate Pred,ScalarEvolution & SE,const SCEVAddRecExpr * & Index,const SCEV * & End)36706c3fb27SDimitry Andric bool InductiveRangeCheck::reassociateSubLHS(
36806c3fb27SDimitry Andric Loop *L, Value *VariantLHS, Value *InvariantRHS, ICmpInst::Predicate Pred,
36906c3fb27SDimitry Andric ScalarEvolution &SE, const SCEVAddRecExpr *&Index, const SCEV *&End) {
37006c3fb27SDimitry Andric Value *LHS, *RHS;
37106c3fb27SDimitry Andric if (!match(VariantLHS, m_Sub(m_Value(LHS), m_Value(RHS))))
37206c3fb27SDimitry Andric return false;
37306c3fb27SDimitry Andric
37406c3fb27SDimitry Andric const SCEV *IV = SE.getSCEV(LHS);
37506c3fb27SDimitry Andric const SCEV *Offset = SE.getSCEV(RHS);
37606c3fb27SDimitry Andric const SCEV *Limit = SE.getSCEV(InvariantRHS);
37706c3fb27SDimitry Andric
37806c3fb27SDimitry Andric bool OffsetSubtracted = false;
37906c3fb27SDimitry Andric if (SE.isLoopInvariant(IV, L))
38006c3fb27SDimitry Andric // "Offset - IV vs Limit"
38106c3fb27SDimitry Andric std::swap(IV, Offset);
38206c3fb27SDimitry Andric else if (SE.isLoopInvariant(Offset, L))
38306c3fb27SDimitry Andric // "IV - Offset vs Limit"
38406c3fb27SDimitry Andric OffsetSubtracted = true;
38506c3fb27SDimitry Andric else
38606c3fb27SDimitry Andric return false;
38706c3fb27SDimitry Andric
38806c3fb27SDimitry Andric const auto *AddRec = dyn_cast<SCEVAddRecExpr>(IV);
38906c3fb27SDimitry Andric if (!AddRec)
39006c3fb27SDimitry Andric return false;
39106c3fb27SDimitry Andric
39206c3fb27SDimitry Andric // In order to turn "IV - Offset < Limit" into "IV < Limit + Offset", we need
39306c3fb27SDimitry Andric // to be able to freely move values from left side of inequality to right side
39406c3fb27SDimitry Andric // (just as in normal linear arithmetics). Overflows make things much more
39506c3fb27SDimitry Andric // complicated, so we want to avoid this.
39606c3fb27SDimitry Andric //
39706c3fb27SDimitry Andric // Let's prove that the initial subtraction doesn't overflow with all IV's
39806c3fb27SDimitry Andric // values from the safe range constructed for that check.
39906c3fb27SDimitry Andric //
40006c3fb27SDimitry Andric // [Case 1] IV - Offset < Limit
40106c3fb27SDimitry Andric // It doesn't overflow if:
40206c3fb27SDimitry Andric // SINT_MIN <= IV - Offset <= SINT_MAX
40306c3fb27SDimitry Andric // In terms of scaled SINT we need to prove:
40406c3fb27SDimitry Andric // SINT_MIN + Offset <= IV <= SINT_MAX + Offset
40506c3fb27SDimitry Andric // Safe range will be constructed:
40606c3fb27SDimitry Andric // 0 <= IV < Limit + Offset
40706c3fb27SDimitry Andric // It means that 'IV - Offset' doesn't underflow, because:
40806c3fb27SDimitry Andric // SINT_MIN + Offset < 0 <= IV
40906c3fb27SDimitry Andric // and doesn't overflow:
41006c3fb27SDimitry Andric // IV < Limit + Offset <= SINT_MAX + Offset
41106c3fb27SDimitry Andric //
41206c3fb27SDimitry Andric // [Case 2] Offset - IV > Limit
41306c3fb27SDimitry Andric // It doesn't overflow if:
41406c3fb27SDimitry Andric // SINT_MIN <= Offset - IV <= SINT_MAX
41506c3fb27SDimitry Andric // In terms of scaled SINT we need to prove:
41606c3fb27SDimitry Andric // -SINT_MIN >= IV - Offset >= -SINT_MAX
41706c3fb27SDimitry Andric // Offset - SINT_MIN >= IV >= Offset - SINT_MAX
41806c3fb27SDimitry Andric // Safe range will be constructed:
41906c3fb27SDimitry Andric // 0 <= IV < Offset - Limit
42006c3fb27SDimitry Andric // It means that 'Offset - IV' doesn't underflow, because
42106c3fb27SDimitry Andric // Offset - SINT_MAX < 0 <= IV
42206c3fb27SDimitry Andric // and doesn't overflow:
42306c3fb27SDimitry Andric // IV < Offset - Limit <= Offset - SINT_MIN
42406c3fb27SDimitry Andric //
42506c3fb27SDimitry Andric // For the computed upper boundary of the IV's range (Offset +/- Limit) we
42606c3fb27SDimitry Andric // don't know exactly whether it overflows or not. So if we can't prove this
42706c3fb27SDimitry Andric // fact at compile time, we scale boundary computations to a wider type with
42806c3fb27SDimitry Andric // the intention to add runtime overflow check.
42906c3fb27SDimitry Andric
43006c3fb27SDimitry Andric auto getExprScaledIfOverflow = [&](Instruction::BinaryOps BinOp,
43106c3fb27SDimitry Andric const SCEV *LHS,
43206c3fb27SDimitry Andric const SCEV *RHS) -> const SCEV * {
43306c3fb27SDimitry Andric const SCEV *(ScalarEvolution::*Operation)(const SCEV *, const SCEV *,
43406c3fb27SDimitry Andric SCEV::NoWrapFlags, unsigned);
43506c3fb27SDimitry Andric switch (BinOp) {
43606c3fb27SDimitry Andric default:
43706c3fb27SDimitry Andric llvm_unreachable("Unsupported binary op");
43806c3fb27SDimitry Andric case Instruction::Add:
43906c3fb27SDimitry Andric Operation = &ScalarEvolution::getAddExpr;
44006c3fb27SDimitry Andric break;
44106c3fb27SDimitry Andric case Instruction::Sub:
44206c3fb27SDimitry Andric Operation = &ScalarEvolution::getMinusSCEV;
44306c3fb27SDimitry Andric break;
44406c3fb27SDimitry Andric }
44506c3fb27SDimitry Andric
44606c3fb27SDimitry Andric if (SE.willNotOverflow(BinOp, ICmpInst::isSigned(Pred), LHS, RHS,
44706c3fb27SDimitry Andric cast<Instruction>(VariantLHS)))
44806c3fb27SDimitry Andric return (SE.*Operation)(LHS, RHS, SCEV::FlagAnyWrap, 0);
44906c3fb27SDimitry Andric
45006c3fb27SDimitry Andric // We couldn't prove that the expression does not overflow.
45106c3fb27SDimitry Andric // Than scale it to a wider type to check overflow at runtime.
45206c3fb27SDimitry Andric auto *Ty = cast<IntegerType>(LHS->getType());
45306c3fb27SDimitry Andric if (Ty->getBitWidth() > MaxTypeSizeForOverflowCheck)
45406c3fb27SDimitry Andric return nullptr;
45506c3fb27SDimitry Andric
45606c3fb27SDimitry Andric auto WideTy = IntegerType::get(Ty->getContext(), Ty->getBitWidth() * 2);
45706c3fb27SDimitry Andric return (SE.*Operation)(SE.getSignExtendExpr(LHS, WideTy),
45806c3fb27SDimitry Andric SE.getSignExtendExpr(RHS, WideTy), SCEV::FlagAnyWrap,
45906c3fb27SDimitry Andric 0);
46006c3fb27SDimitry Andric };
46106c3fb27SDimitry Andric
46206c3fb27SDimitry Andric if (OffsetSubtracted)
46306c3fb27SDimitry Andric // "IV - Offset < Limit" -> "IV" < Offset + Limit
46406c3fb27SDimitry Andric Limit = getExprScaledIfOverflow(Instruction::BinaryOps::Add, Offset, Limit);
46506c3fb27SDimitry Andric else {
46606c3fb27SDimitry Andric // "Offset - IV > Limit" -> "IV" < Offset - Limit
46706c3fb27SDimitry Andric Limit = getExprScaledIfOverflow(Instruction::BinaryOps::Sub, Offset, Limit);
46806c3fb27SDimitry Andric Pred = ICmpInst::getSwappedPredicate(Pred);
46906c3fb27SDimitry Andric }
47006c3fb27SDimitry Andric
47106c3fb27SDimitry Andric if (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SLE) {
47206c3fb27SDimitry Andric // "Expr <= Limit" -> "Expr < Limit + 1"
47306c3fb27SDimitry Andric if (Pred == ICmpInst::ICMP_SLE && Limit)
47406c3fb27SDimitry Andric Limit = getExprScaledIfOverflow(Instruction::BinaryOps::Add, Limit,
47506c3fb27SDimitry Andric SE.getOne(Limit->getType()));
47606c3fb27SDimitry Andric if (Limit) {
47706c3fb27SDimitry Andric Index = AddRec;
47806c3fb27SDimitry Andric End = Limit;
47906c3fb27SDimitry Andric return true;
48006c3fb27SDimitry Andric }
48106c3fb27SDimitry Andric }
48206c3fb27SDimitry Andric return false;
48306c3fb27SDimitry Andric }
48406c3fb27SDimitry Andric
extractRangeChecksFromCond(Loop * L,ScalarEvolution & SE,Use & ConditionUse,SmallVectorImpl<InductiveRangeCheck> & Checks,SmallPtrSetImpl<Value * > & Visited)4850b57cec5SDimitry Andric void InductiveRangeCheck::extractRangeChecksFromCond(
4860b57cec5SDimitry Andric Loop *L, ScalarEvolution &SE, Use &ConditionUse,
4870b57cec5SDimitry Andric SmallVectorImpl<InductiveRangeCheck> &Checks,
4880b57cec5SDimitry Andric SmallPtrSetImpl<Value *> &Visited) {
4890b57cec5SDimitry Andric Value *Condition = ConditionUse.get();
4900b57cec5SDimitry Andric if (!Visited.insert(Condition).second)
4910b57cec5SDimitry Andric return;
4920b57cec5SDimitry Andric
4930b57cec5SDimitry Andric // TODO: Do the same for OR, XOR, NOT etc?
494fe6060f1SDimitry Andric if (match(Condition, m_LogicalAnd(m_Value(), m_Value()))) {
4950b57cec5SDimitry Andric extractRangeChecksFromCond(L, SE, cast<User>(Condition)->getOperandUse(0),
4960b57cec5SDimitry Andric Checks, Visited);
4970b57cec5SDimitry Andric extractRangeChecksFromCond(L, SE, cast<User>(Condition)->getOperandUse(1),
4980b57cec5SDimitry Andric Checks, Visited);
4990b57cec5SDimitry Andric return;
5000b57cec5SDimitry Andric }
5010b57cec5SDimitry Andric
5020b57cec5SDimitry Andric ICmpInst *ICI = dyn_cast<ICmpInst>(Condition);
5030b57cec5SDimitry Andric if (!ICI)
5040b57cec5SDimitry Andric return;
5050b57cec5SDimitry Andric
5060b57cec5SDimitry Andric const SCEV *End = nullptr;
50706c3fb27SDimitry Andric const SCEVAddRecExpr *IndexAddRec = nullptr;
50806c3fb27SDimitry Andric if (!parseRangeCheckICmp(L, ICI, SE, IndexAddRec, End))
50906c3fb27SDimitry Andric return;
51006c3fb27SDimitry Andric
51106c3fb27SDimitry Andric assert(IndexAddRec && "IndexAddRec was not computed");
51206c3fb27SDimitry Andric assert(End && "End was not computed");
51306c3fb27SDimitry Andric
51406c3fb27SDimitry Andric if ((IndexAddRec->getLoop() != L) || !IndexAddRec->isAffine())
51506c3fb27SDimitry Andric return;
5160b57cec5SDimitry Andric
5170b57cec5SDimitry Andric InductiveRangeCheck IRC;
5180b57cec5SDimitry Andric IRC.End = End;
5190b57cec5SDimitry Andric IRC.Begin = IndexAddRec->getStart();
5200b57cec5SDimitry Andric IRC.Step = IndexAddRec->getStepRecurrence(SE);
5210b57cec5SDimitry Andric IRC.CheckUse = &ConditionUse;
5220b57cec5SDimitry Andric Checks.push_back(IRC);
5230b57cec5SDimitry Andric }
5240b57cec5SDimitry Andric
extractRangeChecksFromBranch(BranchInst * BI,Loop * L,ScalarEvolution & SE,BranchProbabilityInfo * BPI,SmallVectorImpl<InductiveRangeCheck> & Checks,bool & Changed)5250b57cec5SDimitry Andric void InductiveRangeCheck::extractRangeChecksFromBranch(
5260b57cec5SDimitry Andric BranchInst *BI, Loop *L, ScalarEvolution &SE, BranchProbabilityInfo *BPI,
52706c3fb27SDimitry Andric SmallVectorImpl<InductiveRangeCheck> &Checks, bool &Changed) {
5280b57cec5SDimitry Andric if (BI->isUnconditional() || BI->getParent() == L->getLoopLatch())
5290b57cec5SDimitry Andric return;
5300b57cec5SDimitry Andric
53106c3fb27SDimitry Andric unsigned IndexLoopSucc = L->contains(BI->getSuccessor(0)) ? 0 : 1;
53206c3fb27SDimitry Andric assert(L->contains(BI->getSuccessor(IndexLoopSucc)) &&
53306c3fb27SDimitry Andric "No edges coming to loop?");
5340b57cec5SDimitry Andric BranchProbability LikelyTaken(15, 16);
5350b57cec5SDimitry Andric
5360b57cec5SDimitry Andric if (!SkipProfitabilityChecks && BPI &&
53706c3fb27SDimitry Andric BPI->getEdgeProbability(BI->getParent(), IndexLoopSucc) < LikelyTaken)
5380b57cec5SDimitry Andric return;
5390b57cec5SDimitry Andric
54006c3fb27SDimitry Andric // IRCE expects branch's true edge comes to loop. Invert branch for opposite
54106c3fb27SDimitry Andric // case.
54206c3fb27SDimitry Andric if (IndexLoopSucc != 0) {
54306c3fb27SDimitry Andric IRBuilder<> Builder(BI);
54406c3fb27SDimitry Andric InvertBranch(BI, Builder);
54506c3fb27SDimitry Andric if (BPI)
54606c3fb27SDimitry Andric BPI->swapSuccEdgesProbabilities(BI->getParent());
54706c3fb27SDimitry Andric Changed = true;
54806c3fb27SDimitry Andric }
54906c3fb27SDimitry Andric
5500b57cec5SDimitry Andric SmallPtrSet<Value *, 8> Visited;
5510b57cec5SDimitry Andric InductiveRangeCheck::extractRangeChecksFromCond(L, SE, BI->getOperandUse(0),
5520b57cec5SDimitry Andric Checks, Visited);
5530b57cec5SDimitry Andric }
5540b57cec5SDimitry Andric
5550b57cec5SDimitry Andric /// If the type of \p S matches with \p Ty, return \p S. Otherwise, return
5560b57cec5SDimitry Andric /// signed or unsigned extension of \p S to type \p Ty.
NoopOrExtend(const SCEV * S,Type * Ty,ScalarEvolution & SE,bool Signed)5570b57cec5SDimitry Andric static const SCEV *NoopOrExtend(const SCEV *S, Type *Ty, ScalarEvolution &SE,
5580b57cec5SDimitry Andric bool Signed) {
5590b57cec5SDimitry Andric return Signed ? SE.getNoopOrSignExtend(S, Ty) : SE.getNoopOrZeroExtend(S, Ty);
5600b57cec5SDimitry Andric }
5610b57cec5SDimitry Andric
5625f757f3fSDimitry Andric // Compute a safe set of limits for the main loop to run in -- effectively the
5635f757f3fSDimitry Andric // intersection of `Range' and the iteration space of the original loop.
5645f757f3fSDimitry Andric // Return std::nullopt if unable to compute the set of subranges.
5655f757f3fSDimitry Andric static std::optional<LoopConstrainer::SubRanges>
calculateSubRanges(ScalarEvolution & SE,const Loop & L,InductiveRangeCheck::Range & Range,const LoopStructure & MainLoopStructure)5665f757f3fSDimitry Andric calculateSubRanges(ScalarEvolution &SE, const Loop &L,
5675f757f3fSDimitry Andric InductiveRangeCheck::Range &Range,
5685f757f3fSDimitry Andric const LoopStructure &MainLoopStructure) {
5690b57cec5SDimitry Andric auto *RTy = cast<IntegerType>(Range.getType());
5700b57cec5SDimitry Andric // We only support wide range checks and narrow latches.
5715f757f3fSDimitry Andric if (!AllowNarrowLatchCondition && RTy != MainLoopStructure.ExitCountTy)
572bdd1243dSDimitry Andric return std::nullopt;
5735f757f3fSDimitry Andric if (RTy->getBitWidth() < MainLoopStructure.ExitCountTy->getBitWidth())
574bdd1243dSDimitry Andric return std::nullopt;
5750b57cec5SDimitry Andric
5760b57cec5SDimitry Andric LoopConstrainer::SubRanges Result;
5770b57cec5SDimitry Andric
5785f757f3fSDimitry Andric bool IsSignedPredicate = MainLoopStructure.IsSignedPredicate;
5790b57cec5SDimitry Andric // I think we can be more aggressive here and make this nuw / nsw if the
5800b57cec5SDimitry Andric // addition that feeds into the icmp for the latch's terminating branch is nuw
5810b57cec5SDimitry Andric // / nsw. In any case, a wrapping 2's complement addition is safe.
5820b57cec5SDimitry Andric const SCEV *Start = NoopOrExtend(SE.getSCEV(MainLoopStructure.IndVarStart),
5830b57cec5SDimitry Andric RTy, SE, IsSignedPredicate);
5840b57cec5SDimitry Andric const SCEV *End = NoopOrExtend(SE.getSCEV(MainLoopStructure.LoopExitAt), RTy,
5850b57cec5SDimitry Andric SE, IsSignedPredicate);
5860b57cec5SDimitry Andric
5870b57cec5SDimitry Andric bool Increasing = MainLoopStructure.IndVarIncreasing;
5880b57cec5SDimitry Andric
5890b57cec5SDimitry Andric // We compute `Smallest` and `Greatest` such that [Smallest, Greatest), or
5900b57cec5SDimitry Andric // [Smallest, GreatestSeen] is the range of values the induction variable
5910b57cec5SDimitry Andric // takes.
5920b57cec5SDimitry Andric
5930b57cec5SDimitry Andric const SCEV *Smallest = nullptr, *Greatest = nullptr, *GreatestSeen = nullptr;
5940b57cec5SDimitry Andric
5950b57cec5SDimitry Andric const SCEV *One = SE.getOne(RTy);
5960b57cec5SDimitry Andric if (Increasing) {
5970b57cec5SDimitry Andric Smallest = Start;
5980b57cec5SDimitry Andric Greatest = End;
5990b57cec5SDimitry Andric // No overflow, because the range [Smallest, GreatestSeen] is not empty.
6000b57cec5SDimitry Andric GreatestSeen = SE.getMinusSCEV(End, One);
6010b57cec5SDimitry Andric } else {
6020b57cec5SDimitry Andric // These two computations may sign-overflow. Here is why that is okay:
6030b57cec5SDimitry Andric //
6040b57cec5SDimitry Andric // We know that the induction variable does not sign-overflow on any
6050b57cec5SDimitry Andric // iteration except the last one, and it starts at `Start` and ends at
6060b57cec5SDimitry Andric // `End`, decrementing by one every time.
6070b57cec5SDimitry Andric //
6080b57cec5SDimitry Andric // * if `Smallest` sign-overflows we know `End` is `INT_SMAX`. Since the
6095f757f3fSDimitry Andric // induction variable is decreasing we know that the smallest value
6100b57cec5SDimitry Andric // the loop body is actually executed with is `INT_SMIN` == `Smallest`.
6110b57cec5SDimitry Andric //
6120b57cec5SDimitry Andric // * if `Greatest` sign-overflows, we know it can only be `INT_SMIN`. In
6130b57cec5SDimitry Andric // that case, `Clamp` will always return `Smallest` and
6140b57cec5SDimitry Andric // [`Result.LowLimit`, `Result.HighLimit`) = [`Smallest`, `Smallest`)
6150b57cec5SDimitry Andric // will be an empty range. Returning an empty range is always safe.
6160b57cec5SDimitry Andric
6170b57cec5SDimitry Andric Smallest = SE.getAddExpr(End, One);
6180b57cec5SDimitry Andric Greatest = SE.getAddExpr(Start, One);
6190b57cec5SDimitry Andric GreatestSeen = Start;
6200b57cec5SDimitry Andric }
6210b57cec5SDimitry Andric
6225f757f3fSDimitry Andric auto Clamp = [&SE, Smallest, Greatest, IsSignedPredicate](const SCEV *S) {
6230b57cec5SDimitry Andric return IsSignedPredicate
6240b57cec5SDimitry Andric ? SE.getSMaxExpr(Smallest, SE.getSMinExpr(Greatest, S))
6250b57cec5SDimitry Andric : SE.getUMaxExpr(Smallest, SE.getUMinExpr(Greatest, S));
6260b57cec5SDimitry Andric };
6270b57cec5SDimitry Andric
6280b57cec5SDimitry Andric // In some cases we can prove that we don't need a pre or post loop.
6290b57cec5SDimitry Andric ICmpInst::Predicate PredLE =
6300b57cec5SDimitry Andric IsSignedPredicate ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_ULE;
6310b57cec5SDimitry Andric ICmpInst::Predicate PredLT =
6320b57cec5SDimitry Andric IsSignedPredicate ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
6330b57cec5SDimitry Andric
6340b57cec5SDimitry Andric bool ProvablyNoPreloop =
6350b57cec5SDimitry Andric SE.isKnownPredicate(PredLE, Range.getBegin(), Smallest);
6360b57cec5SDimitry Andric if (!ProvablyNoPreloop)
6370b57cec5SDimitry Andric Result.LowLimit = Clamp(Range.getBegin());
6380b57cec5SDimitry Andric
6390b57cec5SDimitry Andric bool ProvablyNoPostLoop =
6400b57cec5SDimitry Andric SE.isKnownPredicate(PredLT, GreatestSeen, Range.getEnd());
6410b57cec5SDimitry Andric if (!ProvablyNoPostLoop)
6420b57cec5SDimitry Andric Result.HighLimit = Clamp(Range.getEnd());
6430b57cec5SDimitry Andric
6440b57cec5SDimitry Andric return Result;
6450b57cec5SDimitry Andric }
6460b57cec5SDimitry Andric
6470b57cec5SDimitry Andric /// Computes and returns a range of values for the induction variable (IndVar)
6480b57cec5SDimitry Andric /// in which the range check can be safely elided. If it cannot compute such a
649bdd1243dSDimitry Andric /// range, returns std::nullopt.
650bdd1243dSDimitry Andric std::optional<InductiveRangeCheck::Range>
computeSafeIterationSpace(ScalarEvolution & SE,const SCEVAddRecExpr * IndVar,bool IsLatchSigned) const651bdd1243dSDimitry Andric InductiveRangeCheck::computeSafeIterationSpace(ScalarEvolution &SE,
652bdd1243dSDimitry Andric const SCEVAddRecExpr *IndVar,
6530b57cec5SDimitry Andric bool IsLatchSigned) const {
6540b57cec5SDimitry Andric // We can deal when types of latch check and range checks don't match in case
6550b57cec5SDimitry Andric // if latch check is more narrow.
656bdd1243dSDimitry Andric auto *IVType = dyn_cast<IntegerType>(IndVar->getType());
657bdd1243dSDimitry Andric auto *RCType = dyn_cast<IntegerType>(getBegin()->getType());
65806c3fb27SDimitry Andric auto *EndType = dyn_cast<IntegerType>(getEnd()->getType());
659bdd1243dSDimitry Andric // Do not work with pointer types.
660bdd1243dSDimitry Andric if (!IVType || !RCType)
661bdd1243dSDimitry Andric return std::nullopt;
6620b57cec5SDimitry Andric if (IVType->getBitWidth() > RCType->getBitWidth())
663bdd1243dSDimitry Andric return std::nullopt;
66406c3fb27SDimitry Andric
6650b57cec5SDimitry Andric // IndVar is of the form "A + B * I" (where "I" is the canonical induction
6660b57cec5SDimitry Andric // variable, that may or may not exist as a real llvm::Value in the loop) and
6670b57cec5SDimitry Andric // this inductive range check is a range check on the "C + D * I" ("C" is
6680b57cec5SDimitry Andric // getBegin() and "D" is getStep()). We rewrite the value being range
6690b57cec5SDimitry Andric // checked to "M + N * IndVar" where "N" = "D * B^(-1)" and "M" = "C - NA".
6700b57cec5SDimitry Andric //
6710b57cec5SDimitry Andric // The actual inequalities we solve are of the form
6720b57cec5SDimitry Andric //
6730b57cec5SDimitry Andric // 0 <= M + 1 * IndVar < L given L >= 0 (i.e. N == 1)
6740b57cec5SDimitry Andric //
6750b57cec5SDimitry Andric // Here L stands for upper limit of the safe iteration space.
6760b57cec5SDimitry Andric // The inequality is satisfied by (0 - M) <= IndVar < (L - M). To avoid
6770b57cec5SDimitry Andric // overflows when calculating (0 - M) and (L - M) we, depending on type of
6780b57cec5SDimitry Andric // IV's iteration space, limit the calculations by borders of the iteration
6790b57cec5SDimitry Andric // space. For example, if IndVar is unsigned, (0 - M) overflows for any M > 0.
6800b57cec5SDimitry Andric // If we figured out that "anything greater than (-M) is safe", we strengthen
6810b57cec5SDimitry Andric // this to "everything greater than 0 is safe", assuming that values between
6820b57cec5SDimitry Andric // -M and 0 just do not exist in unsigned iteration space, and we don't want
6830b57cec5SDimitry Andric // to deal with overflown values.
6840b57cec5SDimitry Andric
6850b57cec5SDimitry Andric if (!IndVar->isAffine())
686bdd1243dSDimitry Andric return std::nullopt;
6870b57cec5SDimitry Andric
6880b57cec5SDimitry Andric const SCEV *A = NoopOrExtend(IndVar->getStart(), RCType, SE, IsLatchSigned);
6890b57cec5SDimitry Andric const SCEVConstant *B = dyn_cast<SCEVConstant>(
6900b57cec5SDimitry Andric NoopOrExtend(IndVar->getStepRecurrence(SE), RCType, SE, IsLatchSigned));
6910b57cec5SDimitry Andric if (!B)
692bdd1243dSDimitry Andric return std::nullopt;
6930b57cec5SDimitry Andric assert(!B->isZero() && "Recurrence with zero step?");
6940b57cec5SDimitry Andric
6950b57cec5SDimitry Andric const SCEV *C = getBegin();
6960b57cec5SDimitry Andric const SCEVConstant *D = dyn_cast<SCEVConstant>(getStep());
6970b57cec5SDimitry Andric if (D != B)
698bdd1243dSDimitry Andric return std::nullopt;
6990b57cec5SDimitry Andric
7000b57cec5SDimitry Andric assert(!D->getValue()->isZero() && "Recurrence with zero step?");
7010b57cec5SDimitry Andric unsigned BitWidth = RCType->getBitWidth();
7020b57cec5SDimitry Andric const SCEV *SIntMax = SE.getConstant(APInt::getSignedMaxValue(BitWidth));
70306c3fb27SDimitry Andric const SCEV *SIntMin = SE.getConstant(APInt::getSignedMinValue(BitWidth));
7040b57cec5SDimitry Andric
7050b57cec5SDimitry Andric // Subtract Y from X so that it does not go through border of the IV
7060b57cec5SDimitry Andric // iteration space. Mathematically, it is equivalent to:
7070b57cec5SDimitry Andric //
7080b57cec5SDimitry Andric // ClampedSubtract(X, Y) = min(max(X - Y, INT_MIN), INT_MAX). [1]
7090b57cec5SDimitry Andric //
7100b57cec5SDimitry Andric // In [1], 'X - Y' is a mathematical subtraction (result is not bounded to
7110b57cec5SDimitry Andric // any width of bit grid). But after we take min/max, the result is
7120b57cec5SDimitry Andric // guaranteed to be within [INT_MIN, INT_MAX].
7130b57cec5SDimitry Andric //
7140b57cec5SDimitry Andric // In [1], INT_MAX and INT_MIN are respectively signed and unsigned max/min
7150b57cec5SDimitry Andric // values, depending on type of latch condition that defines IV iteration
7160b57cec5SDimitry Andric // space.
7170b57cec5SDimitry Andric auto ClampedSubtract = [&](const SCEV *X, const SCEV *Y) {
7180b57cec5SDimitry Andric // FIXME: The current implementation assumes that X is in [0, SINT_MAX].
7190b57cec5SDimitry Andric // This is required to ensure that SINT_MAX - X does not overflow signed and
7200b57cec5SDimitry Andric // that X - Y does not overflow unsigned if Y is negative. Can we lift this
7210b57cec5SDimitry Andric // restriction and make it work for negative X either?
7220b57cec5SDimitry Andric if (IsLatchSigned) {
7230b57cec5SDimitry Andric // X is a number from signed range, Y is interpreted as signed.
7240b57cec5SDimitry Andric // Even if Y is SINT_MAX, (X - Y) does not reach SINT_MIN. So the only
7250b57cec5SDimitry Andric // thing we should care about is that we didn't cross SINT_MAX.
7260b57cec5SDimitry Andric // So, if Y is positive, we subtract Y safely.
7270b57cec5SDimitry Andric // Rule 1: Y > 0 ---> Y.
7280b57cec5SDimitry Andric // If 0 <= -Y <= (SINT_MAX - X), we subtract Y safely.
7290b57cec5SDimitry Andric // Rule 2: Y >=s (X - SINT_MAX) ---> Y.
7300b57cec5SDimitry Andric // If 0 <= (SINT_MAX - X) < -Y, we can only subtract (X - SINT_MAX).
7310b57cec5SDimitry Andric // Rule 3: Y <s (X - SINT_MAX) ---> (X - SINT_MAX).
7320b57cec5SDimitry Andric // It gives us smax(Y, X - SINT_MAX) to subtract in all cases.
7330b57cec5SDimitry Andric const SCEV *XMinusSIntMax = SE.getMinusSCEV(X, SIntMax);
7340b57cec5SDimitry Andric return SE.getMinusSCEV(X, SE.getSMaxExpr(Y, XMinusSIntMax),
7350b57cec5SDimitry Andric SCEV::FlagNSW);
7360b57cec5SDimitry Andric } else
7370b57cec5SDimitry Andric // X is a number from unsigned range, Y is interpreted as signed.
7380b57cec5SDimitry Andric // Even if Y is SINT_MIN, (X - Y) does not reach UINT_MAX. So the only
7390b57cec5SDimitry Andric // thing we should care about is that we didn't cross zero.
7400b57cec5SDimitry Andric // So, if Y is negative, we subtract Y safely.
7410b57cec5SDimitry Andric // Rule 1: Y <s 0 ---> Y.
7420b57cec5SDimitry Andric // If 0 <= Y <= X, we subtract Y safely.
7430b57cec5SDimitry Andric // Rule 2: Y <=s X ---> Y.
7440b57cec5SDimitry Andric // If 0 <= X < Y, we should stop at 0 and can only subtract X.
7450b57cec5SDimitry Andric // Rule 3: Y >s X ---> X.
7460b57cec5SDimitry Andric // It gives us smin(X, Y) to subtract in all cases.
7470b57cec5SDimitry Andric return SE.getMinusSCEV(X, SE.getSMinExpr(X, Y), SCEV::FlagNUW);
7480b57cec5SDimitry Andric };
7490b57cec5SDimitry Andric const SCEV *M = SE.getMinusSCEV(C, A);
7500b57cec5SDimitry Andric const SCEV *Zero = SE.getZero(M->getType());
7510b57cec5SDimitry Andric
7520b57cec5SDimitry Andric // This function returns SCEV equal to 1 if X is non-negative 0 otherwise.
7530b57cec5SDimitry Andric auto SCEVCheckNonNegative = [&](const SCEV *X) {
7540b57cec5SDimitry Andric const Loop *L = IndVar->getLoop();
75506c3fb27SDimitry Andric const SCEV *Zero = SE.getZero(X->getType());
7560b57cec5SDimitry Andric const SCEV *One = SE.getOne(X->getType());
7570b57cec5SDimitry Andric // Can we trivially prove that X is a non-negative or negative value?
7580b57cec5SDimitry Andric if (isKnownNonNegativeInLoop(X, L, SE))
7590b57cec5SDimitry Andric return One;
7600b57cec5SDimitry Andric else if (isKnownNegativeInLoop(X, L, SE))
7610b57cec5SDimitry Andric return Zero;
7620b57cec5SDimitry Andric // If not, we will have to figure it out during the execution.
7630b57cec5SDimitry Andric // Function smax(smin(X, 0), -1) + 1 equals to 1 if X >= 0 and 0 if X < 0.
7640b57cec5SDimitry Andric const SCEV *NegOne = SE.getNegativeSCEV(One);
7650b57cec5SDimitry Andric return SE.getAddExpr(SE.getSMaxExpr(SE.getSMinExpr(X, Zero), NegOne), One);
7660b57cec5SDimitry Andric };
76706c3fb27SDimitry Andric
76806c3fb27SDimitry Andric // This function returns SCEV equal to 1 if X will not overflow in terms of
76906c3fb27SDimitry Andric // range check type, 0 otherwise.
77006c3fb27SDimitry Andric auto SCEVCheckWillNotOverflow = [&](const SCEV *X) {
77106c3fb27SDimitry Andric // X doesn't overflow if SINT_MAX >= X.
77206c3fb27SDimitry Andric // Then if (SINT_MAX - X) >= 0, X doesn't overflow
77306c3fb27SDimitry Andric const SCEV *SIntMaxExt = SE.getSignExtendExpr(SIntMax, X->getType());
77406c3fb27SDimitry Andric const SCEV *OverflowCheck =
77506c3fb27SDimitry Andric SCEVCheckNonNegative(SE.getMinusSCEV(SIntMaxExt, X));
77606c3fb27SDimitry Andric
77706c3fb27SDimitry Andric // X doesn't underflow if X >= SINT_MIN.
77806c3fb27SDimitry Andric // Then if (X - SINT_MIN) >= 0, X doesn't underflow
77906c3fb27SDimitry Andric const SCEV *SIntMinExt = SE.getSignExtendExpr(SIntMin, X->getType());
78006c3fb27SDimitry Andric const SCEV *UnderflowCheck =
78106c3fb27SDimitry Andric SCEVCheckNonNegative(SE.getMinusSCEV(X, SIntMinExt));
78206c3fb27SDimitry Andric
78306c3fb27SDimitry Andric return SE.getMulExpr(OverflowCheck, UnderflowCheck);
78406c3fb27SDimitry Andric };
78506c3fb27SDimitry Andric
7860b57cec5SDimitry Andric // FIXME: Current implementation of ClampedSubtract implicitly assumes that
7870b57cec5SDimitry Andric // X is non-negative (in sense of a signed value). We need to re-implement
7880b57cec5SDimitry Andric // this function in a way that it will correctly handle negative X as well.
7890b57cec5SDimitry Andric // We use it twice: for X = 0 everything is fine, but for X = getEnd() we can
7900b57cec5SDimitry Andric // end up with a negative X and produce wrong results. So currently we ensure
7910b57cec5SDimitry Andric // that if getEnd() is negative then both ends of the safe range are zero.
7920b57cec5SDimitry Andric // Note that this may pessimize elimination of unsigned range checks against
7930b57cec5SDimitry Andric // negative values.
7940b57cec5SDimitry Andric const SCEV *REnd = getEnd();
79506c3fb27SDimitry Andric const SCEV *EndWillNotOverflow = SE.getOne(RCType);
7960b57cec5SDimitry Andric
79706c3fb27SDimitry Andric auto PrintRangeCheck = [&](raw_ostream &OS) {
79806c3fb27SDimitry Andric auto L = IndVar->getLoop();
79906c3fb27SDimitry Andric OS << "irce: in function ";
80006c3fb27SDimitry Andric OS << L->getHeader()->getParent()->getName();
80106c3fb27SDimitry Andric OS << ", in ";
80206c3fb27SDimitry Andric L->print(OS);
80306c3fb27SDimitry Andric OS << "there is range check with scaled boundary:\n";
80406c3fb27SDimitry Andric print(OS);
80506c3fb27SDimitry Andric };
80606c3fb27SDimitry Andric
80706c3fb27SDimitry Andric if (EndType->getBitWidth() > RCType->getBitWidth()) {
80806c3fb27SDimitry Andric assert(EndType->getBitWidth() == RCType->getBitWidth() * 2);
80906c3fb27SDimitry Andric if (PrintScaledBoundaryRangeChecks)
81006c3fb27SDimitry Andric PrintRangeCheck(errs());
81106c3fb27SDimitry Andric // End is computed with extended type but will be truncated to a narrow one
81206c3fb27SDimitry Andric // type of range check. Therefore we need a check that the result will not
81306c3fb27SDimitry Andric // overflow in terms of narrow type.
81406c3fb27SDimitry Andric EndWillNotOverflow =
81506c3fb27SDimitry Andric SE.getTruncateExpr(SCEVCheckWillNotOverflow(REnd), RCType);
81606c3fb27SDimitry Andric REnd = SE.getTruncateExpr(REnd, RCType);
81706c3fb27SDimitry Andric }
81806c3fb27SDimitry Andric
81906c3fb27SDimitry Andric const SCEV *RuntimeChecks =
82006c3fb27SDimitry Andric SE.getMulExpr(SCEVCheckNonNegative(REnd), EndWillNotOverflow);
82106c3fb27SDimitry Andric const SCEV *Begin = SE.getMulExpr(ClampedSubtract(Zero, M), RuntimeChecks);
82206c3fb27SDimitry Andric const SCEV *End = SE.getMulExpr(ClampedSubtract(REnd, M), RuntimeChecks);
82306c3fb27SDimitry Andric
8240b57cec5SDimitry Andric return InductiveRangeCheck::Range(Begin, End);
8250b57cec5SDimitry Andric }
8260b57cec5SDimitry Andric
827bdd1243dSDimitry Andric static std::optional<InductiveRangeCheck::Range>
IntersectSignedRange(ScalarEvolution & SE,const std::optional<InductiveRangeCheck::Range> & R1,const InductiveRangeCheck::Range & R2)8280b57cec5SDimitry Andric IntersectSignedRange(ScalarEvolution &SE,
829bdd1243dSDimitry Andric const std::optional<InductiveRangeCheck::Range> &R1,
8300b57cec5SDimitry Andric const InductiveRangeCheck::Range &R2) {
8310b57cec5SDimitry Andric if (R2.isEmpty(SE, /* IsSigned */ true))
832bdd1243dSDimitry Andric return std::nullopt;
83381ad6265SDimitry Andric if (!R1)
8340b57cec5SDimitry Andric return R2;
835bdd1243dSDimitry Andric auto &R1Value = *R1;
8360b57cec5SDimitry Andric // We never return empty ranges from this function, and R1 is supposed to be
8370b57cec5SDimitry Andric // a result of intersection. Thus, R1 is never empty.
8380b57cec5SDimitry Andric assert(!R1Value.isEmpty(SE, /* IsSigned */ true) &&
8390b57cec5SDimitry Andric "We should never have empty R1!");
8400b57cec5SDimitry Andric
8410b57cec5SDimitry Andric // TODO: we could widen the smaller range and have this work; but for now we
8420b57cec5SDimitry Andric // bail out to keep things simple.
8430b57cec5SDimitry Andric if (R1Value.getType() != R2.getType())
844bdd1243dSDimitry Andric return std::nullopt;
8450b57cec5SDimitry Andric
8460b57cec5SDimitry Andric const SCEV *NewBegin = SE.getSMaxExpr(R1Value.getBegin(), R2.getBegin());
8470b57cec5SDimitry Andric const SCEV *NewEnd = SE.getSMinExpr(R1Value.getEnd(), R2.getEnd());
8480b57cec5SDimitry Andric
849bdd1243dSDimitry Andric // If the resulting range is empty, just return std::nullopt.
8500b57cec5SDimitry Andric auto Ret = InductiveRangeCheck::Range(NewBegin, NewEnd);
8510b57cec5SDimitry Andric if (Ret.isEmpty(SE, /* IsSigned */ true))
852bdd1243dSDimitry Andric return std::nullopt;
8530b57cec5SDimitry Andric return Ret;
8540b57cec5SDimitry Andric }
8550b57cec5SDimitry Andric
856bdd1243dSDimitry Andric static std::optional<InductiveRangeCheck::Range>
IntersectUnsignedRange(ScalarEvolution & SE,const std::optional<InductiveRangeCheck::Range> & R1,const InductiveRangeCheck::Range & R2)8570b57cec5SDimitry Andric IntersectUnsignedRange(ScalarEvolution &SE,
858bdd1243dSDimitry Andric const std::optional<InductiveRangeCheck::Range> &R1,
8590b57cec5SDimitry Andric const InductiveRangeCheck::Range &R2) {
8600b57cec5SDimitry Andric if (R2.isEmpty(SE, /* IsSigned */ false))
861bdd1243dSDimitry Andric return std::nullopt;
86281ad6265SDimitry Andric if (!R1)
8630b57cec5SDimitry Andric return R2;
864bdd1243dSDimitry Andric auto &R1Value = *R1;
8650b57cec5SDimitry Andric // We never return empty ranges from this function, and R1 is supposed to be
8660b57cec5SDimitry Andric // a result of intersection. Thus, R1 is never empty.
8670b57cec5SDimitry Andric assert(!R1Value.isEmpty(SE, /* IsSigned */ false) &&
8680b57cec5SDimitry Andric "We should never have empty R1!");
8690b57cec5SDimitry Andric
8700b57cec5SDimitry Andric // TODO: we could widen the smaller range and have this work; but for now we
8710b57cec5SDimitry Andric // bail out to keep things simple.
8720b57cec5SDimitry Andric if (R1Value.getType() != R2.getType())
873bdd1243dSDimitry Andric return std::nullopt;
8740b57cec5SDimitry Andric
8750b57cec5SDimitry Andric const SCEV *NewBegin = SE.getUMaxExpr(R1Value.getBegin(), R2.getBegin());
8760b57cec5SDimitry Andric const SCEV *NewEnd = SE.getUMinExpr(R1Value.getEnd(), R2.getEnd());
8770b57cec5SDimitry Andric
878bdd1243dSDimitry Andric // If the resulting range is empty, just return std::nullopt.
8790b57cec5SDimitry Andric auto Ret = InductiveRangeCheck::Range(NewBegin, NewEnd);
8800b57cec5SDimitry Andric if (Ret.isEmpty(SE, /* IsSigned */ false))
881bdd1243dSDimitry Andric return std::nullopt;
8820b57cec5SDimitry Andric return Ret;
8830b57cec5SDimitry Andric }
8840b57cec5SDimitry Andric
run(Function & F,FunctionAnalysisManager & AM)8855ffd83dbSDimitry Andric PreservedAnalyses IRCEPass::run(Function &F, FunctionAnalysisManager &AM) {
8865ffd83dbSDimitry Andric auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
8875ffd83dbSDimitry Andric LoopInfo &LI = AM.getResult<LoopAnalysis>(F);
88881ad6265SDimitry Andric // There are no loops in the function. Return before computing other expensive
88981ad6265SDimitry Andric // analyses.
89081ad6265SDimitry Andric if (LI.empty())
89181ad6265SDimitry Andric return PreservedAnalyses::all();
89281ad6265SDimitry Andric auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F);
89381ad6265SDimitry Andric auto &BPI = AM.getResult<BranchProbabilityAnalysis>(F);
8945ffd83dbSDimitry Andric
895e8d8bef9SDimitry Andric // Get BFI analysis result on demand. Please note that modification of
896e8d8bef9SDimitry Andric // CFG invalidates this analysis and we should handle it.
897e8d8bef9SDimitry Andric auto getBFI = [&F, &AM ]()->BlockFrequencyInfo & {
898e8d8bef9SDimitry Andric return AM.getResult<BlockFrequencyAnalysis>(F);
899e8d8bef9SDimitry Andric };
900e8d8bef9SDimitry Andric InductiveRangeCheckElimination IRCE(SE, &BPI, DT, LI, { getBFI });
9015ffd83dbSDimitry Andric
9025ffd83dbSDimitry Andric bool Changed = false;
903e8d8bef9SDimitry Andric {
904e8d8bef9SDimitry Andric bool CFGChanged = false;
9055ffd83dbSDimitry Andric for (const auto &L : LI) {
906e8d8bef9SDimitry Andric CFGChanged |= simplifyLoop(L, &DT, &LI, &SE, nullptr, nullptr,
9075ffd83dbSDimitry Andric /*PreserveLCSSA=*/false);
9085ffd83dbSDimitry Andric Changed |= formLCSSARecursively(*L, DT, &LI, &SE);
9095ffd83dbSDimitry Andric }
910e8d8bef9SDimitry Andric Changed |= CFGChanged;
911e8d8bef9SDimitry Andric
912fe6060f1SDimitry Andric if (CFGChanged && !SkipProfitabilityChecks) {
913fe6060f1SDimitry Andric PreservedAnalyses PA = PreservedAnalyses::all();
914fe6060f1SDimitry Andric PA.abandon<BlockFrequencyAnalysis>();
915fe6060f1SDimitry Andric AM.invalidate(F, PA);
916fe6060f1SDimitry Andric }
917e8d8bef9SDimitry Andric }
9185ffd83dbSDimitry Andric
9195ffd83dbSDimitry Andric SmallPriorityWorklist<Loop *, 4> Worklist;
9205ffd83dbSDimitry Andric appendLoopsToWorklist(LI, Worklist);
9215ffd83dbSDimitry Andric auto LPMAddNewLoop = [&Worklist](Loop *NL, bool IsSubloop) {
9220b57cec5SDimitry Andric if (!IsSubloop)
9235ffd83dbSDimitry Andric appendLoopsToWorklist(*NL, Worklist);
9240b57cec5SDimitry Andric };
9255ffd83dbSDimitry Andric
9265ffd83dbSDimitry Andric while (!Worklist.empty()) {
9275ffd83dbSDimitry Andric Loop *L = Worklist.pop_back_val();
928e8d8bef9SDimitry Andric if (IRCE.run(L, LPMAddNewLoop)) {
929e8d8bef9SDimitry Andric Changed = true;
930fe6060f1SDimitry Andric if (!SkipProfitabilityChecks) {
931fe6060f1SDimitry Andric PreservedAnalyses PA = PreservedAnalyses::all();
932fe6060f1SDimitry Andric PA.abandon<BlockFrequencyAnalysis>();
933fe6060f1SDimitry Andric AM.invalidate(F, PA);
934fe6060f1SDimitry Andric }
935e8d8bef9SDimitry Andric }
9365ffd83dbSDimitry Andric }
9375ffd83dbSDimitry Andric
9380b57cec5SDimitry Andric if (!Changed)
9390b57cec5SDimitry Andric return PreservedAnalyses::all();
9400b57cec5SDimitry Andric return getLoopPassPreservedAnalyses();
9410b57cec5SDimitry Andric }
9420b57cec5SDimitry Andric
943e8d8bef9SDimitry Andric bool
isProfitableToTransform(const Loop & L,LoopStructure & LS)944e8d8bef9SDimitry Andric InductiveRangeCheckElimination::isProfitableToTransform(const Loop &L,
945e8d8bef9SDimitry Andric LoopStructure &LS) {
946e8d8bef9SDimitry Andric if (SkipProfitabilityChecks)
947e8d8bef9SDimitry Andric return true;
94881ad6265SDimitry Andric if (GetBFI) {
949e8d8bef9SDimitry Andric BlockFrequencyInfo &BFI = (*GetBFI)();
950e8d8bef9SDimitry Andric uint64_t hFreq = BFI.getBlockFreq(LS.Header).getFrequency();
951e8d8bef9SDimitry Andric uint64_t phFreq = BFI.getBlockFreq(L.getLoopPreheader()).getFrequency();
952e8d8bef9SDimitry Andric if (phFreq != 0 && hFreq != 0 && (hFreq / phFreq < MinRuntimeIterations)) {
953e8d8bef9SDimitry Andric LLVM_DEBUG(dbgs() << "irce: could not prove profitability: "
954e8d8bef9SDimitry Andric << "the estimated number of iterations basing on "
955e8d8bef9SDimitry Andric "frequency info is " << (hFreq / phFreq) << "\n";);
956e8d8bef9SDimitry Andric return false;
957e8d8bef9SDimitry Andric }
958e8d8bef9SDimitry Andric return true;
959e8d8bef9SDimitry Andric }
960e8d8bef9SDimitry Andric
961e8d8bef9SDimitry Andric if (!BPI)
962e8d8bef9SDimitry Andric return true;
963e8d8bef9SDimitry Andric BranchProbability ExitProbability =
964e8d8bef9SDimitry Andric BPI->getEdgeProbability(LS.Latch, LS.LatchBrExitIdx);
965e8d8bef9SDimitry Andric if (ExitProbability > BranchProbability(1, MinRuntimeIterations)) {
966e8d8bef9SDimitry Andric LLVM_DEBUG(dbgs() << "irce: could not prove profitability: "
967e8d8bef9SDimitry Andric << "the exit probability is too big " << ExitProbability
968e8d8bef9SDimitry Andric << "\n";);
969e8d8bef9SDimitry Andric return false;
970e8d8bef9SDimitry Andric }
971e8d8bef9SDimitry Andric return true;
972e8d8bef9SDimitry Andric }
973e8d8bef9SDimitry Andric
run(Loop * L,function_ref<void (Loop *,bool)> LPMAddNewLoop)9740b57cec5SDimitry Andric bool InductiveRangeCheckElimination::run(
9750b57cec5SDimitry Andric Loop *L, function_ref<void(Loop *, bool)> LPMAddNewLoop) {
9760b57cec5SDimitry Andric if (L->getBlocks().size() >= LoopSizeCutoff) {
9770b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "irce: giving up constraining loop, too large\n");
9780b57cec5SDimitry Andric return false;
9790b57cec5SDimitry Andric }
9800b57cec5SDimitry Andric
9810b57cec5SDimitry Andric BasicBlock *Preheader = L->getLoopPreheader();
9820b57cec5SDimitry Andric if (!Preheader) {
9830b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "irce: loop has no preheader, leaving\n");
9840b57cec5SDimitry Andric return false;
9850b57cec5SDimitry Andric }
9860b57cec5SDimitry Andric
9870b57cec5SDimitry Andric LLVMContext &Context = Preheader->getContext();
9880b57cec5SDimitry Andric SmallVector<InductiveRangeCheck, 16> RangeChecks;
98906c3fb27SDimitry Andric bool Changed = false;
9900b57cec5SDimitry Andric
991bdd1243dSDimitry Andric for (auto *BBI : L->getBlocks())
9920b57cec5SDimitry Andric if (BranchInst *TBI = dyn_cast<BranchInst>(BBI->getTerminator()))
9930b57cec5SDimitry Andric InductiveRangeCheck::extractRangeChecksFromBranch(TBI, L, SE, BPI,
99406c3fb27SDimitry Andric RangeChecks, Changed);
9950b57cec5SDimitry Andric
9960b57cec5SDimitry Andric if (RangeChecks.empty())
99706c3fb27SDimitry Andric return Changed;
9980b57cec5SDimitry Andric
9990b57cec5SDimitry Andric auto PrintRecognizedRangeChecks = [&](raw_ostream &OS) {
10000b57cec5SDimitry Andric OS << "irce: looking at loop "; L->print(OS);
10010b57cec5SDimitry Andric OS << "irce: loop has " << RangeChecks.size()
10020b57cec5SDimitry Andric << " inductive range checks: \n";
10030b57cec5SDimitry Andric for (InductiveRangeCheck &IRC : RangeChecks)
10040b57cec5SDimitry Andric IRC.print(OS);
10050b57cec5SDimitry Andric };
10060b57cec5SDimitry Andric
10070b57cec5SDimitry Andric LLVM_DEBUG(PrintRecognizedRangeChecks(dbgs()));
10080b57cec5SDimitry Andric
10090b57cec5SDimitry Andric if (PrintRangeChecks)
10100b57cec5SDimitry Andric PrintRecognizedRangeChecks(errs());
10110b57cec5SDimitry Andric
10120b57cec5SDimitry Andric const char *FailureReason = nullptr;
1013bdd1243dSDimitry Andric std::optional<LoopStructure> MaybeLoopStructure =
10145f757f3fSDimitry Andric LoopStructure::parseLoopStructure(SE, *L, AllowUnsignedLatchCondition,
10155f757f3fSDimitry Andric FailureReason);
101681ad6265SDimitry Andric if (!MaybeLoopStructure) {
10170b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "irce: could not parse loop structure: "
10180b57cec5SDimitry Andric << FailureReason << "\n";);
101906c3fb27SDimitry Andric return Changed;
10200b57cec5SDimitry Andric }
102181ad6265SDimitry Andric LoopStructure LS = *MaybeLoopStructure;
1022e8d8bef9SDimitry Andric if (!isProfitableToTransform(*L, LS))
102306c3fb27SDimitry Andric return Changed;
10240b57cec5SDimitry Andric const SCEVAddRecExpr *IndVar =
10250b57cec5SDimitry Andric cast<SCEVAddRecExpr>(SE.getMinusSCEV(SE.getSCEV(LS.IndVarBase), SE.getSCEV(LS.IndVarStep)));
10260b57cec5SDimitry Andric
1027bdd1243dSDimitry Andric std::optional<InductiveRangeCheck::Range> SafeIterRange;
10280b57cec5SDimitry Andric
10290b57cec5SDimitry Andric SmallVector<InductiveRangeCheck, 4> RangeChecksToEliminate;
10300b57cec5SDimitry Andric // Basing on the type of latch predicate, we interpret the IV iteration range
10310b57cec5SDimitry Andric // as signed or unsigned range. We use different min/max functions (signed or
10320b57cec5SDimitry Andric // unsigned) when intersecting this range with safe iteration ranges implied
10330b57cec5SDimitry Andric // by range checks.
10340b57cec5SDimitry Andric auto IntersectRange =
10350b57cec5SDimitry Andric LS.IsSignedPredicate ? IntersectSignedRange : IntersectUnsignedRange;
10360b57cec5SDimitry Andric
10370b57cec5SDimitry Andric for (InductiveRangeCheck &IRC : RangeChecks) {
10380b57cec5SDimitry Andric auto Result = IRC.computeSafeIterationSpace(SE, IndVar,
10390b57cec5SDimitry Andric LS.IsSignedPredicate);
104081ad6265SDimitry Andric if (Result) {
1041bdd1243dSDimitry Andric auto MaybeSafeIterRange = IntersectRange(SE, SafeIterRange, *Result);
104281ad6265SDimitry Andric if (MaybeSafeIterRange) {
1043bdd1243dSDimitry Andric assert(!MaybeSafeIterRange->isEmpty(SE, LS.IsSignedPredicate) &&
10440b57cec5SDimitry Andric "We should never return empty ranges!");
10450b57cec5SDimitry Andric RangeChecksToEliminate.push_back(IRC);
1046bdd1243dSDimitry Andric SafeIterRange = *MaybeSafeIterRange;
10470b57cec5SDimitry Andric }
10480b57cec5SDimitry Andric }
10490b57cec5SDimitry Andric }
10500b57cec5SDimitry Andric
105181ad6265SDimitry Andric if (!SafeIterRange)
105206c3fb27SDimitry Andric return Changed;
10530b57cec5SDimitry Andric
10545f757f3fSDimitry Andric std::optional<LoopConstrainer::SubRanges> MaybeSR =
10555f757f3fSDimitry Andric calculateSubRanges(SE, *L, *SafeIterRange, LS);
10565f757f3fSDimitry Andric if (!MaybeSR) {
10575f757f3fSDimitry Andric LLVM_DEBUG(dbgs() << "irce: could not compute subranges\n");
10585f757f3fSDimitry Andric return false;
10595f757f3fSDimitry Andric }
10605f757f3fSDimitry Andric
10615f757f3fSDimitry Andric LoopConstrainer LC(*L, LI, LPMAddNewLoop, LS, SE, DT,
10625f757f3fSDimitry Andric SafeIterRange->getBegin()->getType(), *MaybeSR);
10630b57cec5SDimitry Andric
106406c3fb27SDimitry Andric if (LC.run()) {
106506c3fb27SDimitry Andric Changed = true;
106606c3fb27SDimitry Andric
10670b57cec5SDimitry Andric auto PrintConstrainedLoopInfo = [L]() {
10680b57cec5SDimitry Andric dbgs() << "irce: in function ";
10690b57cec5SDimitry Andric dbgs() << L->getHeader()->getParent()->getName() << ": ";
10700b57cec5SDimitry Andric dbgs() << "constrained ";
10710b57cec5SDimitry Andric L->print(dbgs());
10720b57cec5SDimitry Andric };
10730b57cec5SDimitry Andric
10740b57cec5SDimitry Andric LLVM_DEBUG(PrintConstrainedLoopInfo());
10750b57cec5SDimitry Andric
10760b57cec5SDimitry Andric if (PrintChangedLoops)
10770b57cec5SDimitry Andric PrintConstrainedLoopInfo();
10780b57cec5SDimitry Andric
10790b57cec5SDimitry Andric // Optimize away the now-redundant range checks.
10800b57cec5SDimitry Andric
10810b57cec5SDimitry Andric for (InductiveRangeCheck &IRC : RangeChecksToEliminate) {
10820b57cec5SDimitry Andric ConstantInt *FoldedRangeCheck = IRC.getPassingDirection()
10830b57cec5SDimitry Andric ? ConstantInt::getTrue(Context)
10840b57cec5SDimitry Andric : ConstantInt::getFalse(Context);
10850b57cec5SDimitry Andric IRC.getCheckUse()->set(FoldedRangeCheck);
10860b57cec5SDimitry Andric }
10870b57cec5SDimitry Andric }
10880b57cec5SDimitry Andric
10890b57cec5SDimitry Andric return Changed;
10900b57cec5SDimitry Andric }
1091