//===----------------------------------------------------------------------===//
#include "llvm/ADT/Optional.h"
-
#include "llvm/Analysis/BranchProbabilityInfo.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/ScalarEvolutionExpander.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/ValueTracking.h"
-
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
-#include "llvm/IR/Instructions.h"
#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/Instructions.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/IR/Verifier.h"
-
+#include "llvm/Pass.h"
#include "llvm/Support/Debug.h"
-
+#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include "llvm/Transforms/Utils/SimplifyIndVar.h"
#include "llvm/Transforms/Utils/UnrollLoop.h"
-
-#include "llvm/Pass.h"
-
#include <array>
using namespace llvm;
static cl::opt<bool> PrintChangedLoops("irce-print-changed-loops", cl::Hidden,
cl::init(false));
+static cl::opt<bool> PrintRangeChecks("irce-print-range-checks", cl::Hidden,
+ cl::init(false));
+
static cl::opt<int> MaxExitProbReciprocal("irce-max-exit-prob-reciprocal",
cl::Hidden, cl::init(10));
///
/// and
///
-/// 2. a condition that is provably true for some range of values taken by the
-/// containing loop's induction variable.
-///
-/// Currently all inductive range checks are branches conditional on an
-/// expression of the form
+/// 2. a condition that is provably true for some contiguous range of values
+/// taken by the containing loop's induction variable.
///
-/// 0 <= (Offset + Scale * I) < Length
-///
-/// where `I' is the canonical induction variable of a loop to which Offset and
-/// Scale are loop invariant, and Length is >= 0. Currently the 'false' branch
-/// is considered cold, looking at profiling data to verify that is a TODO.
-
class InductiveRangeCheck {
+ // Classifies a range check
+ enum RangeCheckKind : unsigned {
+ // Range check of the form "0 <= I".
+ RANGE_CHECK_LOWER = 1,
+
+ // Range check of the form "I < L" where L is known positive.
+ RANGE_CHECK_UPPER = 2,
+
+ // The logical and of the RANGE_CHECK_LOWER and RANGE_CHECK_UPPER
+ // conditions.
+ RANGE_CHECK_BOTH = RANGE_CHECK_LOWER | RANGE_CHECK_UPPER,
+
+ // Unrecognized range check condition.
+ RANGE_CHECK_UNKNOWN = (unsigned)-1
+ };
+
+ static const char *rangeCheckKindToStr(RangeCheckKind);
+
const SCEV *Offset;
const SCEV *Scale;
Value *Length;
BranchInst *Branch;
+ RangeCheckKind Kind;
+
+ static RangeCheckKind parseRangeCheckICmp(Loop *L, ICmpInst *ICI,
+ ScalarEvolution &SE, Value *&Index,
+ Value *&Length);
+
+ static InductiveRangeCheck::RangeCheckKind
+ parseRangeCheck(Loop *L, ScalarEvolution &SE, Value *Condition,
+ const SCEV *&Index, Value *&UpperLimit);
InductiveRangeCheck() :
Offset(nullptr), Scale(nullptr), Length(nullptr), Branch(nullptr) { }
void print(raw_ostream &OS) const {
OS << "InductiveRangeCheck:\n";
+ OS << " Kind: " << rangeCheckKindToStr(Kind) << "\n";
OS << " Offset: ";
Offset->print(OS);
OS << " Scale: ";
Scale->print(OS);
OS << " Length: ";
- Length->print(OS);
- OS << " Branch: ";
+ if (Length)
+ Length->print(OS);
+ else
+ OS << "(null)";
+ OS << "\n Branch: ";
getBranch()->print(OS);
OS << "\n";
}
AU.addRequiredID(LoopSimplifyID);
AU.addRequiredID(LCSSAID);
AU.addRequired<ScalarEvolution>();
- AU.addRequired<BranchProbabilityInfo>();
+ AU.addRequired<BranchProbabilityInfoWrapperPass>();
}
bool runOnLoop(Loop *L, LPPassManager &LPM) override;
INITIALIZE_PASS(InductiveRangeCheckElimination, "irce",
"Inductive range check elimination", false, false)
-static bool IsLowerBoundCheck(Value *Check, Value *&IndexV) {
- using namespace llvm::PatternMatch;
+const char *InductiveRangeCheck::rangeCheckKindToStr(
+ InductiveRangeCheck::RangeCheckKind RCK) {
+ switch (RCK) {
+ case InductiveRangeCheck::RANGE_CHECK_UNKNOWN:
+ return "RANGE_CHECK_UNKNOWN";
- ICmpInst::Predicate Pred = ICmpInst::BAD_ICMP_PREDICATE;
- Value *LHS = nullptr, *RHS = nullptr;
+ case InductiveRangeCheck::RANGE_CHECK_UPPER:
+ return "RANGE_CHECK_UPPER";
- if (!match(Check, m_ICmp(Pred, m_Value(LHS), m_Value(RHS))))
- return false;
+ case InductiveRangeCheck::RANGE_CHECK_LOWER:
+ return "RANGE_CHECK_LOWER";
+
+ case InductiveRangeCheck::RANGE_CHECK_BOTH:
+ return "RANGE_CHECK_BOTH";
+ }
+
+ llvm_unreachable("unknown range check type!");
+}
+
+/// Parse a single ICmp instruction, `ICI`, into a range check. If `ICI`
+/// cannot
+/// be interpreted as a range check, return `RANGE_CHECK_UNKNOWN` and set
+/// `Index` and `Length` to `nullptr`. Otherwise set `Index` to the value
+/// being
+/// range checked, and set `Length` to the upper limit `Index` is being range
+/// checked with if (and only if) the range check type is stronger or equal to
+/// RANGE_CHECK_UPPER.
+///
+InductiveRangeCheck::RangeCheckKind
+InductiveRangeCheck::parseRangeCheckICmp(Loop *L, ICmpInst *ICI,
+ ScalarEvolution &SE, Value *&Index,
+ Value *&Length) {
+
+ auto IsNonNegativeAndNotLoopVarying = [&SE, L](Value *V) {
+ const SCEV *S = SE.getSCEV(V);
+ if (isa<SCEVCouldNotCompute>(S))
+ return false;
+
+ return SE.getLoopDisposition(S, L) == ScalarEvolution::LoopInvariant &&
+ SE.isKnownNonNegative(S);
+ };
+
+ using namespace llvm::PatternMatch;
+
+ ICmpInst::Predicate Pred = ICI->getPredicate();
+ Value *LHS = ICI->getOperand(0);
+ Value *RHS = ICI->getOperand(1);
switch (Pred) {
default:
- return false;
+ return RANGE_CHECK_UNKNOWN;
case ICmpInst::ICMP_SLE:
std::swap(LHS, RHS);
// fallthrough
case ICmpInst::ICMP_SGE:
- if (!match(RHS, m_ConstantInt<0>()))
- return false;
- IndexV = LHS;
- return true;
+ if (match(RHS, m_ConstantInt<0>())) {
+ Index = LHS;
+ return RANGE_CHECK_LOWER;
+ }
+ return RANGE_CHECK_UNKNOWN;
case ICmpInst::ICMP_SLT:
std::swap(LHS, RHS);
// fallthrough
case ICmpInst::ICMP_SGT:
- if (!match(RHS, m_ConstantInt<-1>()))
- return false;
- IndexV = LHS;
- return true;
- }
-}
-
-static bool IsUpperBoundCheck(Value *Check, Value *Index, Value *&UpperLimit) {
- using namespace llvm::PatternMatch;
-
- ICmpInst::Predicate Pred = ICmpInst::BAD_ICMP_PREDICATE;
- Value *LHS = nullptr, *RHS = nullptr;
-
- if (!match(Check, m_ICmp(Pred, m_Value(LHS), m_Value(RHS))))
- return false;
+ if (match(RHS, m_ConstantInt<-1>())) {
+ Index = LHS;
+ return RANGE_CHECK_LOWER;
+ }
- switch (Pred) {
- default:
- return false;
+ if (IsNonNegativeAndNotLoopVarying(LHS)) {
+ Index = RHS;
+ Length = LHS;
+ return RANGE_CHECK_UPPER;
+ }
+ return RANGE_CHECK_UNKNOWN;
- case ICmpInst::ICMP_SGT:
+ case ICmpInst::ICMP_ULT:
std::swap(LHS, RHS);
// fallthrough
- case ICmpInst::ICMP_SLT:
- if (LHS != Index)
- return false;
- UpperLimit = RHS;
- return true;
-
case ICmpInst::ICMP_UGT:
- std::swap(LHS, RHS);
- // fallthrough
- case ICmpInst::ICMP_ULT:
- if (LHS != Index)
- return false;
- UpperLimit = RHS;
- return true;
+ if (IsNonNegativeAndNotLoopVarying(LHS)) {
+ Index = RHS;
+ Length = LHS;
+ return RANGE_CHECK_BOTH;
+ }
+ return RANGE_CHECK_UNKNOWN;
}
+
+ llvm_unreachable("default clause returns!");
}
-/// Split a condition into something semantically equivalent to (0 <= I <
-/// Limit), both comparisons signed and Len loop invariant on L and positive.
-/// On success, return true and set Index to I and UpperLimit to Limit. Return
-/// false on failure (we may still write to UpperLimit and Index on failure).
-/// It does not try to interpret I as a loop index.
-///
-static bool SplitRangeCheckCondition(Loop *L, ScalarEvolution &SE,
+/// Parses an arbitrary condition into a range check. `Length` is set only if
+/// the range check is recognized to be `RANGE_CHECK_UPPER` or stronger.
+InductiveRangeCheck::RangeCheckKind
+InductiveRangeCheck::parseRangeCheck(Loop *L, ScalarEvolution &SE,
Value *Condition, const SCEV *&Index,
- Value *&UpperLimit) {
-
- // TODO: currently this catches some silly cases like comparing "%idx slt 1".
- // Our transformations are still correct, but less likely to be profitable in
- // those cases. We have to come up with some heuristics that pick out the
- // range checks that are more profitable to clone a loop for. This function
- // in general can be made more robust.
-
+ Value *&Length) {
using namespace llvm::PatternMatch;
Value *A = nullptr;
Value *B = nullptr;
- ICmpInst::Predicate Pred = ICmpInst::BAD_ICMP_PREDICATE;
-
- // In these early checks we assume that the matched UpperLimit is positive.
- // We'll verify that fact later, before returning true.
if (match(Condition, m_And(m_Value(A), m_Value(B)))) {
- Value *IndexV = nullptr;
- Value *ExpectedUpperBoundCheck = nullptr;
+ Value *IndexA = nullptr, *IndexB = nullptr;
+ Value *LengthA = nullptr, *LengthB = nullptr;
+ ICmpInst *ICmpA = dyn_cast<ICmpInst>(A), *ICmpB = dyn_cast<ICmpInst>(B);
- if (IsLowerBoundCheck(A, IndexV))
- ExpectedUpperBoundCheck = B;
- else if (IsLowerBoundCheck(B, IndexV))
- ExpectedUpperBoundCheck = A;
- else
- return false;
+ if (!ICmpA || !ICmpB)
+ return InductiveRangeCheck::RANGE_CHECK_UNKNOWN;
- if (!IsUpperBoundCheck(ExpectedUpperBoundCheck, IndexV, UpperLimit))
- return false;
+ auto RCKindA = parseRangeCheckICmp(L, ICmpA, SE, IndexA, LengthA);
+ auto RCKindB = parseRangeCheckICmp(L, ICmpB, SE, IndexB, LengthB);
- Index = SE.getSCEV(IndexV);
+ if (RCKindA == InductiveRangeCheck::RANGE_CHECK_UNKNOWN ||
+ RCKindB == InductiveRangeCheck::RANGE_CHECK_UNKNOWN)
+ return InductiveRangeCheck::RANGE_CHECK_UNKNOWN;
- if (isa<SCEVCouldNotCompute>(Index))
- return false;
+ if (IndexA != IndexB)
+ return InductiveRangeCheck::RANGE_CHECK_UNKNOWN;
- } else if (match(Condition, m_ICmp(Pred, m_Value(A), m_Value(B)))) {
- switch (Pred) {
- default:
- return false;
+ if (LengthA != nullptr && LengthB != nullptr && LengthA != LengthB)
+ return InductiveRangeCheck::RANGE_CHECK_UNKNOWN;
- case ICmpInst::ICMP_SGT:
- std::swap(A, B);
- // fall through
- case ICmpInst::ICMP_SLT:
- UpperLimit = B;
- Index = SE.getSCEV(A);
- if (isa<SCEVCouldNotCompute>(Index) || !SE.isKnownNonNegative(Index))
- return false;
- break;
+ Index = SE.getSCEV(IndexA);
+ if (isa<SCEVCouldNotCompute>(Index))
+ return InductiveRangeCheck::RANGE_CHECK_UNKNOWN;
- case ICmpInst::ICMP_UGT:
- std::swap(A, B);
- // fall through
- case ICmpInst::ICMP_ULT:
- UpperLimit = B;
- Index = SE.getSCEV(A);
- if (isa<SCEVCouldNotCompute>(Index))
- return false;
- break;
- }
- } else {
- return false;
+ Length = LengthA == nullptr ? LengthB : LengthA;
+
+ return (InductiveRangeCheck::RangeCheckKind)(RCKindA | RCKindB);
}
- const SCEV *UpperLimitSCEV = SE.getSCEV(UpperLimit);
- if (isa<SCEVCouldNotCompute>(UpperLimitSCEV) ||
- !SE.isKnownNonNegative(UpperLimitSCEV))
- return false;
+ if (ICmpInst *ICI = dyn_cast<ICmpInst>(Condition)) {
+ Value *IndexVal = nullptr;
- if (SE.getLoopDisposition(UpperLimitSCEV, L) !=
- ScalarEvolution::LoopInvariant) {
- DEBUG(dbgs() << " in function: " << L->getHeader()->getParent()->getName()
- << " ";
- dbgs() << " UpperLimit is not loop invariant: "
- << UpperLimit->getName() << "\n";);
- return false;
+ auto RCKind = parseRangeCheckICmp(L, ICI, SE, IndexVal, Length);
+
+ if (RCKind == InductiveRangeCheck::RANGE_CHECK_UNKNOWN)
+ return InductiveRangeCheck::RANGE_CHECK_UNKNOWN;
+
+ Index = SE.getSCEV(IndexVal);
+ if (isa<SCEVCouldNotCompute>(Index))
+ return InductiveRangeCheck::RANGE_CHECK_UNKNOWN;
+
+ return RCKind;
}
- return true;
+ return InductiveRangeCheck::RANGE_CHECK_UNKNOWN;
}
Value *Length = nullptr;
const SCEV *IndexSCEV = nullptr;
- if (!SplitRangeCheckCondition(L, SE, BI->getCondition(), IndexSCEV, Length))
+ auto RCKind = InductiveRangeCheck::parseRangeCheck(L, SE, BI->getCondition(),
+ IndexSCEV, Length);
+
+ if (RCKind == InductiveRangeCheck::RANGE_CHECK_UNKNOWN)
return nullptr;
- assert(IndexSCEV && Length && "contract with SplitRangeCheckCondition!");
+ assert(IndexSCEV && "contract with SplitRangeCheckCondition!");
+ assert((!(RCKind & InductiveRangeCheck::RANGE_CHECK_UPPER) || Length) &&
+ "contract with SplitRangeCheckCondition!");
const SCEVAddRecExpr *IndexAddRec = dyn_cast<SCEVAddRecExpr>(IndexSCEV);
bool IsAffineIndex =
IRC->Offset = IndexAddRec->getStart();
IRC->Scale = IndexAddRec->getStepRecurrence(SE);
IRC->Branch = BI;
+ IRC->Kind = RCKind;
return IRC;
}
}
}
- auto IsInductionVar = [&SE](const SCEVAddRecExpr *AR, bool &IsIncreasing) {
- if (!AR->isAffine())
- return false;
+ auto HasNoSignedWrap = [&](const SCEVAddRecExpr *AR) {
+ if (AR->getNoWrapFlags(SCEV::FlagNSW))
+ return true;
IntegerType *Ty = cast<IntegerType>(AR->getType());
IntegerType *WideTy =
IntegerType::get(Ty->getContext(), Ty->getBitWidth() * 2);
- // Currently we only work with induction variables that have been proved to
- // not wrap. This restriction can potentially be lifted in the future.
-
const SCEVAddRecExpr *ExtendAfterOp =
dyn_cast<SCEVAddRecExpr>(SE.getSignExtendExpr(AR, WideTy));
- if (!ExtendAfterOp)
- return false;
+ if (ExtendAfterOp) {
+ const SCEV *ExtendedStart = SE.getSignExtendExpr(AR->getStart(), WideTy);
+ const SCEV *ExtendedStep =
+ SE.getSignExtendExpr(AR->getStepRecurrence(SE), WideTy);
- const SCEV *ExtendedStart = SE.getSignExtendExpr(AR->getStart(), WideTy);
- const SCEV *ExtendedStep =
- SE.getSignExtendExpr(AR->getStepRecurrence(SE), WideTy);
+ bool NoSignedWrap = ExtendAfterOp->getStart() == ExtendedStart &&
+ ExtendAfterOp->getStepRecurrence(SE) == ExtendedStep;
- bool NoSignedWrap = ExtendAfterOp->getStart() == ExtendedStart &&
- ExtendAfterOp->getStepRecurrence(SE) == ExtendedStep;
+ if (NoSignedWrap)
+ return true;
+ }
+
+ // We may have proved this when computing the sign extension above.
+ return AR->getNoWrapFlags(SCEV::FlagNSW) != SCEV::FlagAnyWrap;
+ };
- if (!NoSignedWrap)
+ auto IsInductionVar = [&](const SCEVAddRecExpr *AR, bool &IsIncreasing) {
+ if (!AR->isAffine())
+ return false;
+
+ // Currently we only work with induction variables that have been proved to
+ // not wrap. This restriction can potentially be lifted in the future.
+
+ if (!HasNoSignedWrap(AR))
return false;
if (const SCEVConstant *StepExpr =
const SCEV *End = SE.getSCEV(MainLoopStructure.LoopExitAt);
bool Increasing = MainLoopStructure.IndVarIncreasing;
+
// We compute `Smallest` and `Greatest` such that [Smallest, Greatest) is the
// range of values the induction variable takes.
- const SCEV *Smallest =
- Increasing ? Start : SE.getAddExpr(End, SE.getSCEV(One));
- const SCEV *Greatest =
- Increasing ? End : SE.getAddExpr(Start, SE.getSCEV(One));
+
+ const SCEV *Smallest = nullptr, *Greatest = nullptr;
+
+ if (Increasing) {
+ Smallest = Start;
+ Greatest = End;
+ } else {
+ // These two computations may sign-overflow. Here is why that is okay:
+ //
+ // We know that the induction variable does not sign-overflow on any
+ // iteration except the last one, and it starts at `Start` and ends at
+ // `End`, decrementing by one every time.
+ //
+ // * if `Smallest` sign-overflows we know `End` is `INT_SMAX`. Since the
+ // induction variable is decreasing we know that that the smallest value
+ // the loop body is actually executed with is `INT_SMIN` == `Smallest`.
+ //
+ // * if `Greatest` sign-overflows, we know it can only be `INT_SMIN`. In
+ // that case, `Clamp` will always return `Smallest` and
+ // [`Result.LowLimit`, `Result.HighLimit`) = [`Smallest`, `Smallest`)
+ // will be an empty range. Returning an empty range is always safe.
+ //
+
+ Smallest = SE.getAddExpr(End, SE.getSCEV(One));
+ Greatest = SE.getAddExpr(Start, SE.getSCEV(One));
+ }
auto Clamp = [this, Smallest, Greatest](const SCEV *S) {
return SE.getSMaxExpr(Smallest, SE.getSMinExpr(Greatest, S));
const SCEV *M = SE.getMinusSCEV(C, A);
const SCEV *Begin = SE.getNegativeSCEV(M);
- const SCEV *End = SE.getMinusSCEV(SE.getSCEV(getLength()), M);
+ const SCEV *UpperLimit = nullptr;
+
+ // We strengthen "0 <= I" to "0 <= I < INT_SMAX" and "I < L" to "0 <= I < L".
+ // We can potentially do much better here.
+ if (Value *V = getLength()) {
+ UpperLimit = SE.getSCEV(V);
+ } else {
+ assert(Kind == InductiveRangeCheck::RANGE_CHECK_LOWER && "invariant!");
+ unsigned BitWidth = cast<IntegerType>(IndVar->getType())->getBitWidth();
+ UpperLimit = SE.getConstant(APInt::getSignedMaxValue(BitWidth));
+ }
+ const SCEV *End = SE.getMinusSCEV(UpperLimit, M);
return InductiveRangeCheck::Range(Begin, End);
}
InductiveRangeCheck::AllocatorTy IRCAlloc;
SmallVector<InductiveRangeCheck *, 16> RangeChecks;
ScalarEvolution &SE = getAnalysis<ScalarEvolution>();
- BranchProbabilityInfo &BPI = getAnalysis<BranchProbabilityInfo>();
+ BranchProbabilityInfo &BPI =
+ getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
for (auto BBI : L->getBlocks())
if (BranchInst *TBI = dyn_cast<BranchInst>(BBI->getTerminator()))
if (RangeChecks.empty())
return false;
- DEBUG(dbgs() << "irce: looking at loop "; L->print(dbgs());
- dbgs() << "irce: loop has " << RangeChecks.size()
- << " inductive range checks: \n";
- for (InductiveRangeCheck *IRC : RangeChecks)
- IRC->print(dbgs());
- );
+ auto PrintRecognizedRangeChecks = [&](raw_ostream &OS) {
+ OS << "irce: looking at loop "; L->print(OS);
+ OS << "irce: loop has " << RangeChecks.size()
+ << " inductive range checks: \n";
+ for (InductiveRangeCheck *IRC : RangeChecks)
+ IRC->print(OS);
+ };
+
+ DEBUG(PrintRecognizedRangeChecks(dbgs()));
+
+ if (PrintRangeChecks)
+ PrintRecognizedRangeChecks(errs());
const char *FailureReason = nullptr;
Optional<LoopStructure> MaybeLoopStructure =
projects / oota-llvm.git / blobdiff