//===----------------------------------------------------------------------===//
#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;
BranchInst *Branch;
RangeCheckKind Kind;
- static RangeCheckKind parseRangeCheckICmp(ICmpInst *ICI, ScalarEvolution &SE,
- Value *&Index, Value *&Length);
+ static RangeCheckKind parseRangeCheckICmp(Loop *L, ICmpInst *ICI,
+ ScalarEvolution &SE, Value *&Index,
+ Value *&Length);
static InductiveRangeCheck::RangeCheckKind
parseRangeCheck(Loop *L, ScalarEvolution &SE, Value *Condition,
/// RANGE_CHECK_UPPER.
///
InductiveRangeCheck::RangeCheckKind
-InductiveRangeCheck::parseRangeCheckICmp(ICmpInst *ICI, ScalarEvolution &SE,
- Value *&Index, Value *&Length) {
+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;
return RANGE_CHECK_LOWER;
}
- if (SE.isKnownNonNegative(SE.getSCEV(LHS))) {
+ if (IsNonNegativeAndNotLoopVarying(LHS)) {
Index = RHS;
Length = LHS;
return RANGE_CHECK_UPPER;
std::swap(LHS, RHS);
// fallthrough
case ICmpInst::ICMP_UGT:
- if (SE.isKnownNonNegative(SE.getSCEV(LHS))) {
+ if (IsNonNegativeAndNotLoopVarying(LHS)) {
Index = RHS;
Length = LHS;
return RANGE_CHECK_BOTH;
if (!ICmpA || !ICmpB)
return InductiveRangeCheck::RANGE_CHECK_UNKNOWN;
- auto RCKindA = parseRangeCheckICmp(ICmpA, SE, IndexA, LengthA);
- auto RCKindB = parseRangeCheckICmp(ICmpB, SE, IndexB, LengthB);
+ auto RCKindA = parseRangeCheckICmp(L, ICmpA, SE, IndexA, LengthA);
+ auto RCKindB = parseRangeCheckICmp(L, ICmpB, SE, IndexB, LengthB);
if (RCKindA == InductiveRangeCheck::RANGE_CHECK_UNKNOWN ||
RCKindB == InductiveRangeCheck::RANGE_CHECK_UNKNOWN)
if (ICmpInst *ICI = dyn_cast<ICmpInst>(Condition)) {
Value *IndexVal = nullptr;
- auto RCKind = parseRangeCheckICmp(ICI, SE, IndexVal, Length);
+ auto RCKind = parseRangeCheckICmp(L, ICI, SE, IndexVal, Length);
if (RCKind == InductiveRangeCheck::RANGE_CHECK_UNKNOWN)
return InductiveRangeCheck::RANGE_CHECK_UNKNOWN;
}
}
- 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);
+
+ bool NoSignedWrap = ExtendAfterOp->getStart() == ExtendedStart &&
+ ExtendAfterOp->getStepRecurrence(SE) == ExtendedStep;
- const SCEV *ExtendedStart = SE.getSignExtendExpr(AR->getStart(), WideTy);
- const SCEV *ExtendedStep =
- SE.getSignExtendExpr(AR->getStepRecurrence(SE), WideTy);
+ if (NoSignedWrap)
+ return true;
+ }
- bool NoSignedWrap = ExtendAfterOp->getStart() == ExtendedStart &&
- ExtendAfterOp->getStepRecurrence(SE) == ExtendedStep;
+ // We may have proved this when computing the sign extension above.
+ return AR->getNoWrapFlags(SCEV::FlagNSW) != SCEV::FlagAnyWrap;
+ };
+
+ 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 (!NoSignedWrap)
+ if (!HasNoSignedWrap(AR))
return false;
if (const SCEVConstant *StepExpr =