// Implementation of the SCEV class.
//
-#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+LLVM_DUMP_METHOD
void SCEV::dump() const {
print(dbgs());
dbgs() << '\n';
}
-#endif
void SCEV::print(raw_ostream &OS) const {
switch (static_cast<SCEVTypes>(getSCEVType())) {
// If the input value is a chrec scev, truncate the chrec's operands.
if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Op)) {
SmallVector<const SCEV *, 4> Operands;
- for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i)
- Operands.push_back(getTruncateExpr(AddRec->getOperand(i), Ty));
+ for (const SCEV *Op : AddRec->operands())
+ Operands.push_back(getTruncateExpr(Op, Ty));
return getAddRecExpr(Operands, AddRec->getLoop(), SCEV::FlagAnyWrap);
}
// `Step`:
// 1. NSW/NUW flags on the step increment.
- const SCEV *PreStart = SE->getAddExpr(DiffOps, SA->getNoWrapFlags());
+ auto PreStartFlags =
+ ScalarEvolution::maskFlags(SA->getNoWrapFlags(), SCEV::FlagNUW);
+ const SCEV *PreStart = SE->getAddExpr(DiffOps, PreStartFlags);
const SCEVAddRecExpr *PreAR = dyn_cast<SCEVAddRecExpr>(
SE->getAddRecExpr(PreStart, Step, L, SCEV::FlagAnyWrap));
ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(Step, &Pred, SE);
if (OverflowLimit &&
- SE->isLoopEntryGuardedByCond(L, Pred, PreStart, OverflowLimit)) {
+ SE->isLoopEntryGuardedByCond(L, Pred, PreStart, OverflowLimit))
return PreStart;
- }
+
return nullptr;
}
for (unsigned Delta : {-2, -1, 1, 2}) {
const SCEV *PreStart = getConstant(StartAI - Delta);
+ FoldingSetNodeID ID;
+ ID.AddInteger(scAddRecExpr);
+ ID.AddPointer(PreStart);
+ ID.AddPointer(Step);
+ ID.AddPointer(L);
+ void *IP = nullptr;
+ const auto *PreAR =
+ static_cast<SCEVAddRecExpr *>(UniqueSCEVs.FindNodeOrInsertPos(ID, IP));
+
// Give up if we don't already have the add recurrence we need because
// actually constructing an add recurrence is relatively expensive.
- const SCEVAddRecExpr *PreAR = [&]() {
- FoldingSetNodeID ID;
- ID.AddInteger(scAddRecExpr);
- ID.AddPointer(PreStart);
- ID.AddPointer(Step);
- ID.AddPointer(L);
- void *IP = nullptr;
- return static_cast<SCEVAddRecExpr *>(
- this->UniqueSCEVs.FindNodeOrInsertPos(ID, IP));
- }();
-
if (PreAR && PreAR->getNoWrapFlags(WrapType)) { // proves (2)
const SCEV *DeltaS = getConstant(StartC->getType(), Delta);
ICmpInst::Predicate Pred = ICmpInst::BAD_ICMP_PREDICATE;
}
}
+ if (auto *SA = dyn_cast<SCEVAddExpr>(Op)) {
+ // zext((A + B + ...)<nuw>) --> (zext(A) + zext(B) + ...)<nuw>
+ if (SA->getNoWrapFlags(SCEV::FlagNUW)) {
+ // If the addition does not unsign overflow then we can, by definition,
+ // commute the zero extension with the addition operation.
+ SmallVector<const SCEV *, 4> Ops;
+ for (const auto *Op : SA->operands())
+ Ops.push_back(getZeroExtendExpr(Op, Ty));
+ return getAddExpr(Ops, SCEV::FlagNUW);
+ }
+ }
+
// The cast wasn't folded; create an explicit cast node.
// Recompute the insert position, as it may have been invalidated.
if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
}
}
}
+
+ // sext((A + B + ...)<nsw>) --> (sext(A) + sext(B) + ...)<nsw>
+ if (SA->getNoWrapFlags(SCEV::FlagNSW)) {
+ // If the addition does not sign overflow then we can, by definition,
+ // commute the sign extension with the addition operation.
+ SmallVector<const SCEV *, 4> Ops;
+ for (const auto *Op : SA->operands())
+ Ops.push_back(getSignExtendExpr(Op, Ty));
+ return getAddExpr(Ops, SCEV::FlagNSW);
+ }
}
// If the input value is a chrec scev, and we can prove that the value
// did not overflow the old, smaller, value, we can sign extend all of the
static SCEV::NoWrapFlags
StrengthenNoWrapFlags(ScalarEvolution *SE, SCEVTypes Type,
const SmallVectorImpl<const SCEV *> &Ops,
- SCEV::NoWrapFlags OldFlags) {
+ SCEV::NoWrapFlags Flags) {
using namespace std::placeholders;
+ typedef OverflowingBinaryOperator OBO;
bool CanAnalyze =
Type == scAddExpr || Type == scAddRecExpr || Type == scMulExpr;
int SignOrUnsignMask = SCEV::FlagNUW | SCEV::FlagNSW;
SCEV::NoWrapFlags SignOrUnsignWrap =
- ScalarEvolution::maskFlags(OldFlags, SignOrUnsignMask);
+ ScalarEvolution::maskFlags(Flags, SignOrUnsignMask);
// If FlagNSW is true and all the operands are non-negative, infer FlagNUW.
auto IsKnownNonNegative =
if (SignOrUnsignWrap == SCEV::FlagNSW &&
std::all_of(Ops.begin(), Ops.end(), IsKnownNonNegative))
- return ScalarEvolution::setFlags(OldFlags,
- (SCEV::NoWrapFlags)SignOrUnsignMask);
+ Flags =
+ ScalarEvolution::setFlags(Flags, (SCEV::NoWrapFlags)SignOrUnsignMask);
+
+ SignOrUnsignWrap = ScalarEvolution::maskFlags(Flags, SignOrUnsignMask);
+
+ if (SignOrUnsignWrap != SignOrUnsignMask && Type == scAddExpr &&
+ Ops.size() == 2 && isa<SCEVConstant>(Ops[0])) {
- return OldFlags;
+ // (A + C) --> (A + C)<nsw> if the addition does not sign overflow
+ // (A + C) --> (A + C)<nuw> if the addition does not unsign overflow
+
+ const APInt &C = cast<SCEVConstant>(Ops[0])->getValue()->getValue();
+ if (!(SignOrUnsignWrap & SCEV::FlagNSW)) {
+ auto NSWRegion =
+ ConstantRange::makeNoWrapRegion(Instruction::Add, C, OBO::NoSignedWrap);
+ if (NSWRegion.contains(SE->getSignedRange(Ops[1])))
+ Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNSW);
+ }
+ if (!(SignOrUnsignWrap & SCEV::FlagNUW)) {
+ auto NUWRegion =
+ ConstantRange::makeNoWrapRegion(Instruction::Add, C,
+ OBO::NoUnsignedWrap);
+ if (NUWRegion.contains(SE->getUnsignedRange(Ops[1])))
+ Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNUW);
+ }
+ }
+
+ return Flags;
}
/// getAddExpr - Get a canonical add expression, or something simpler if
break;
}
LargeMulOps.push_back(T->getOperand());
- } else if (const SCEVConstant *C =
- dyn_cast<SCEVConstant>(M->getOperand(j))) {
+ } else if (const auto *C = dyn_cast<SCEVConstant>(M->getOperand(j))) {
LargeMulOps.push_back(getAnyExtendExpr(C, SrcType));
} else {
Ok = false;
}
if (AnyFolded)
return getAddExpr(NewOps);
- }
- else if (const SCEVAddRecExpr *
- AddRec = dyn_cast<SCEVAddRecExpr>(Ops[1])) {
+ } else if (const auto *AddRec = dyn_cast<SCEVAddRecExpr>(Ops[1])) {
// Negation preserves a recurrence's no self-wrap property.
SmallVector<const SCEV *, 4> Operands;
for (SCEVAddRecExpr::op_iterator I = AddRec->op_begin(),
getZeroExtendExpr(Step, ExtTy),
AR->getLoop(), SCEV::FlagAnyWrap)) {
SmallVector<const SCEV *, 4> Operands;
- for (unsigned i = 0, e = AR->getNumOperands(); i != e; ++i)
- Operands.push_back(getUDivExpr(AR->getOperand(i), RHS));
- return getAddRecExpr(Operands, AR->getLoop(),
- SCEV::FlagNW);
+ for (const SCEV *Op : AR->operands())
+ Operands.push_back(getUDivExpr(Op, RHS));
+ return getAddRecExpr(Operands, AR->getLoop(), SCEV::FlagNW);
}
/// Get a canonical UDivExpr for a recurrence.
/// {X,+,N}/C => {Y,+,N}/C where Y=X-(X%N). Safe when C%N=0.
// (A*B)/C --> A*(B/C) if safe and B/C can be folded.
if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(LHS)) {
SmallVector<const SCEV *, 4> Operands;
- for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i)
- Operands.push_back(getZeroExtendExpr(M->getOperand(i), ExtTy));
+ for (const SCEV *Op : M->operands())
+ Operands.push_back(getZeroExtendExpr(Op, ExtTy));
if (getZeroExtendExpr(M, ExtTy) == getMulExpr(Operands))
// Find an operand that's safely divisible.
for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
// (A+B)/C --> (A/C + B/C) if safe and A/C and B/C can be folded.
if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(LHS)) {
SmallVector<const SCEV *, 4> Operands;
- for (unsigned i = 0, e = A->getNumOperands(); i != e; ++i)
- Operands.push_back(getZeroExtendExpr(A->getOperand(i), ExtTy));
+ for (const SCEV *Op : A->operands())
+ Operands.push_back(getZeroExtendExpr(Op, ExtTy));
if (getZeroExtendExpr(A, ExtTy) == getAddExpr(Operands)) {
Operands.clear();
for (unsigned i = 0, e = A->getNumOperands(); i != e; ++i) {
if (const SCEVConstant *RHSCst = dyn_cast<SCEVConstant>(RHS)) {
// If the mulexpr multiplies by a constant, then that constant must be the
// first element of the mulexpr.
- if (const SCEVConstant *LHSCst =
- dyn_cast<SCEVConstant>(Mul->getOperand(0))) {
+ if (const auto *LHSCst = dyn_cast<SCEVConstant>(Mul->getOperand(0))) {
if (LHSCst == RHSCst) {
SmallVector<const SCEV *, 2> Operands;
Operands.append(Mul->op_begin() + 1, Mul->op_end());
// AddRecs require their operands be loop-invariant with respect to their
// loops. Don't perform this transformation if it would break this
// requirement.
- bool AllInvariant = true;
- for (unsigned i = 0, e = Operands.size(); i != e; ++i)
- if (!isLoopInvariant(Operands[i], L)) {
- AllInvariant = false;
- break;
- }
+ bool AllInvariant =
+ std::all_of(Operands.begin(), Operands.end(),
+ [&](const SCEV *Op) { return isLoopInvariant(Op, L); });
+
if (AllInvariant) {
// Create a recurrence for the outer loop with the same step size.
//
maskFlags(Flags, SCEV::FlagNW | NestedAR->getNoWrapFlags());
NestedOperands[0] = getAddRecExpr(Operands, L, OuterFlags);
- AllInvariant = true;
- for (unsigned i = 0, e = NestedOperands.size(); i != e; ++i)
- if (!isLoopInvariant(NestedOperands[i], NestedLoop)) {
- AllInvariant = false;
- break;
- }
+ AllInvariant = std::all_of(
+ NestedOperands.begin(), NestedOperands.end(),
+ [&](const SCEV *Op) { return isLoopInvariant(Op, NestedLoop); });
+
if (AllInvariant) {
// Ok, both add recurrences are valid after the transformation.
//
// We can bypass creating a target-independent
// constant expression and then folding it back into a ConstantInt.
// This is just a compile-time optimization.
- return getConstant(IntTy,
- F.getParent()->getDataLayout().getTypeAllocSize(AllocTy));
+ return getConstant(IntTy, getDataLayout().getTypeAllocSize(AllocTy));
}
const SCEV *ScalarEvolution::getOffsetOfExpr(Type *IntTy,
// constant expression and then folding it back into a ConstantInt.
// This is just a compile-time optimization.
return getConstant(
- IntTy,
- F.getParent()->getDataLayout().getStructLayout(STy)->getElementOffset(
- FieldNo));
+ IntTy, getDataLayout().getStructLayout(STy)->getElementOffset(FieldNo));
}
const SCEV *ScalarEvolution::getUnknown(Value *V) {
/// for which isSCEVable must return true.
uint64_t ScalarEvolution::getTypeSizeInBits(Type *Ty) const {
assert(isSCEVable(Ty) && "Type is not SCEVable!");
- return F.getParent()->getDataLayout().getTypeSizeInBits(Ty);
+ return getDataLayout().getTypeSizeInBits(Ty);
}
/// getEffectiveSCEVType - Return a type with the same bitwidth as
Type *ScalarEvolution::getEffectiveSCEVType(Type *Ty) const {
assert(isSCEVable(Ty) && "Type is not SCEVable!");
- if (Ty->isIntegerTy()) {
+ if (Ty->isIntegerTy())
return Ty;
- }
// The only other support type is pointer.
assert(Ty->isPointerTy() && "Unexpected non-pointer non-integer type!");
- return F.getParent()->getDataLayout().getIntPtrType(Ty);
+ return getDataLayout().getIntPtrType(Ty);
}
const SCEV *ScalarEvolution::getCouldNotCompute() {
if (const SCEVCastExpr *Cast = dyn_cast<SCEVCastExpr>(V)) {
return getPointerBase(Cast->getOperand());
- }
- else if (const SCEVNAryExpr *NAry = dyn_cast<SCEVNAryExpr>(V)) {
+ } else if (const SCEVNAryExpr *NAry = dyn_cast<SCEVNAryExpr>(V)) {
const SCEV *PtrOp = nullptr;
for (SCEVNAryExpr::op_iterator I = NAry->op_begin(), E = NAry->op_end();
I != E; ++I) {
if (!Visited.insert(I).second)
continue;
- ValueExprMapType::iterator It =
- ValueExprMap.find_as(static_cast<Value *>(I));
+ auto It = ValueExprMap.find_as(static_cast<Value *>(I));
if (It != ValueExprMap.end()) {
const SCEV *Old = It->second;
return PHISCEV;
}
}
- } else if (const SCEVAddRecExpr *AddRec =
- dyn_cast<SCEVAddRecExpr>(BEValue)) {
+ } else if (const auto *AddRec = dyn_cast<SCEVAddRecExpr>(BEValue)) {
// Otherwise, this could be a loop like this:
// i = 0; for (j = 1; ..; ++j) { .... i = j; }
// In this case, j = {1,+,1} and BEValue is j.
switch (S->getSCEVType()) {
case scConstant: case scTruncate: case scZeroExtend: case scSignExtend:
case scAddExpr: case scMulExpr: case scUMaxExpr: case scSMaxExpr:
- // These expressions are available if their operand(s) is/are.
- return true;
+ // These expressions are available if their operand(s) is/are.
+ return true;
case scAddRecExpr: {
// We allow add recurrences that are on the loop BB is in, or some
case scUDivExpr:
case scCouldNotCompute:
- // We do not try to smart about these at all.
- return setUnavailable();
+ // We do not try to smart about these at all.
+ return setUnavailable();
}
llvm_unreachable("switch should be fully covered!");
}
// PHI's incoming blocks are in a different loop, in which case doing so
// risks breaking LCSSA form. Instcombine would normally zap these, but
// it doesn't have DominatorTree information, so it may miss cases.
- if (Value *V = SimplifyInstruction(PN, F.getParent()->getDataLayout(), &TLI,
- &DT, &AC))
+ if (Value *V = SimplifyInstruction(PN, getDataLayout(), &TLI, &DT, &AC))
if (LI.replacementPreservesLCSSAForm(PN, V))
return getSCEV(V);
// For a SCEVUnknown, ask ValueTracking.
unsigned BitWidth = getTypeSizeInBits(U->getType());
APInt Zeros(BitWidth, 0), Ones(BitWidth, 0);
- computeKnownBits(U->getValue(), Zeros, Ones, F.getParent()->getDataLayout(),
- 0, &AC, nullptr, &DT);
+ computeKnownBits(U->getValue(), Zeros, Ones, getDataLayout(), 0, &AC,
+ nullptr, &DT);
return Zeros.countTrailingOnes();
}
/// GetRangeFromMetadata - Helper method to assign a range to V from
/// metadata present in the IR.
static Optional<ConstantRange> GetRangeFromMetadata(Value *V) {
- if (Instruction *I = dyn_cast<Instruction>(V)) {
- if (MDNode *MD = I->getMetadata(LLVMContext::MD_range)) {
- ConstantRange TotalRange(
- cast<IntegerType>(I->getType())->getBitWidth(), false);
-
- unsigned NumRanges = MD->getNumOperands() / 2;
- assert(NumRanges >= 1);
-
- for (unsigned i = 0; i < NumRanges; ++i) {
- ConstantInt *Lower =
- mdconst::extract<ConstantInt>(MD->getOperand(2 * i + 0));
- ConstantInt *Upper =
- mdconst::extract<ConstantInt>(MD->getOperand(2 * i + 1));
- ConstantRange Range(Lower->getValue(), Upper->getValue());
- TotalRange = TotalRange.unionWith(Range);
- }
-
- return TotalRange;
- }
- }
+ if (Instruction *I = dyn_cast<Instruction>(V))
+ if (MDNode *MD = I->getMetadata(LLVMContext::MD_range))
+ return getConstantRangeFromMetadata(*MD);
return None;
}
// Split here to avoid paying the compile-time cost of calling both
// computeKnownBits and ComputeNumSignBits. This restriction can be lifted
// if needed.
- const DataLayout &DL = F.getParent()->getDataLayout();
+ const DataLayout &DL = getDataLayout();
if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED) {
// For a SCEVUnknown, ask ValueTracking.
APInt Zeros(BitWidth, 0), Ones(BitWidth, 0);
unsigned TZ = A.countTrailingZeros();
unsigned BitWidth = A.getBitWidth();
APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0);
- computeKnownBits(U->getOperand(0), KnownZero, KnownOne,
- F.getParent()->getDataLayout(), 0, &AC, nullptr, &DT);
+ computeKnownBits(U->getOperand(0), KnownZero, KnownOne, getDataLayout(),
+ 0, &AC, nullptr, &DT);
APInt EffectiveMask =
APInt::getLowBitsSet(BitWidth, BitWidth - LZ - TZ).shl(TZ);
break;
}
default:
-#if 0
- dbgs() << "computeBackedgeTakenCount ";
- if (ExitCond->getOperand(0)->getType()->isUnsigned())
- dbgs() << "[unsigned] ";
- dbgs() << *LHS << " "
- << Instruction::getOpcodeName(Instruction::ICmp)
- << " " << *RHS << "\n";
-#endif
break;
}
return computeExitCountExhaustively(L, ExitCond, !L->contains(TBB));
Result = ConstantExpr::getICmp(predicate, Result, RHS);
if (!isa<ConstantInt>(Result)) break; // Couldn't decide for sure
if (cast<ConstantInt>(Result)->getValue().isMinValue()) {
-#if 0
- dbgs() << "\n***\n*** Computed loop count " << *ItCst
- << "\n*** From global " << *GV << "*** BB: " << *L->getHeader()
- << "***\n";
-#endif
++NumArrayLenItCounts;
return getConstant(ItCst); // Found terminating iteration!
}
Instruction *I = dyn_cast<Instruction>(V);
if (!I || !canConstantEvolve(I, L)) return nullptr;
- if (PHINode *PN = dyn_cast<PHINode>(I)) {
+ if (PHINode *PN = dyn_cast<PHINode>(I))
return PN;
- }
// Record non-constant instructions contained by the loop.
DenseMap<Instruction *, PHINode *> PHIMap;
unsigned NumIterations = BEs.getZExtValue(); // must be in range
unsigned IterationNum = 0;
- const DataLayout &DL = F.getParent()->getDataLayout();
+ const DataLayout &DL = getDataLayout();
for (; ; ++IterationNum) {
if (IterationNum == NumIterations)
return RetVal = CurrentIterVals[PN]; // Got exit value!
// the loop symbolically to determine when the condition gets a value of
// "ExitWhen".
unsigned MaxIterations = MaxBruteForceIterations; // Limit analysis.
- const DataLayout &DL = F.getParent()->getDataLayout();
+ const DataLayout &DL = getDataLayout();
for (unsigned IterationNum = 0; IterationNum != MaxIterations;++IterationNum){
auto *CondVal = dyn_cast_or_null<ConstantInt>(
EvaluateExpression(Cond, L, CurrentIterVals, DL, &TLI));
if (CanConstantFold(I)) {
SmallVector<Constant *, 4> Operands;
bool MadeImprovement = false;
- for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
- Value *Op = I->getOperand(i);
+ for (Value *Op : I->operands()) {
if (Constant *C = dyn_cast<Constant>(Op)) {
Operands.push_back(C);
continue;
// Check to see if getSCEVAtScope actually made an improvement.
if (MadeImprovement) {
Constant *C = nullptr;
- const DataLayout &DL = F.getParent()->getDataLayout();
+ const DataLayout &DL = getDataLayout();
if (const CmpInst *CI = dyn_cast<CmpInst>(I))
C = ConstantFoldCompareInstOperands(CI->getPredicate(), Operands[0],
Operands[1], DL, &TLI);
const SCEVConstant *R1 = dyn_cast<SCEVConstant>(Roots.first);
const SCEVConstant *R2 = dyn_cast<SCEVConstant>(Roots.second);
if (R1 && R2) {
-#if 0
- dbgs() << "HFTZ: " << *V << " - sol#1: " << *R1
- << " sol#2: " << *R2 << "\n";
-#endif
// Pick the smallest positive root value.
if (ConstantInt *CB =
dyn_cast<ConstantInt>(ConstantExpr::getICmp(CmpInst::ICMP_ULT,
return false;
}
+bool ScalarEvolution::isKnownPredicateViaNoOverflow(ICmpInst::Predicate Pred,
+ const SCEV *LHS,
+ const SCEV *RHS) {
+
+ // Match Result to (X + Y)<ExpectedFlags> where Y is a constant integer.
+ // Return Y via OutY.
+ auto MatchBinaryAddToConst =
+ [this](const SCEV *Result, const SCEV *X, APInt &OutY,
+ SCEV::NoWrapFlags ExpectedFlags) {
+ const SCEV *NonConstOp, *ConstOp;
+ SCEV::NoWrapFlags FlagsPresent;
+
+ if (!splitBinaryAdd(Result, ConstOp, NonConstOp, FlagsPresent) ||
+ !isa<SCEVConstant>(ConstOp) || NonConstOp != X)
+ return false;
+
+ OutY = cast<SCEVConstant>(ConstOp)->getValue()->getValue();
+ return (FlagsPresent & ExpectedFlags) == ExpectedFlags;
+ };
+
+ APInt C;
+
+ switch (Pred) {
+ default:
+ break;
+
+ case ICmpInst::ICMP_SGE:
+ std::swap(LHS, RHS);
+ case ICmpInst::ICMP_SLE:
+ // X s<= (X + C)<nsw> if C >= 0
+ if (MatchBinaryAddToConst(RHS, LHS, C, SCEV::FlagNSW) && C.isNonNegative())
+ return true;
+
+ // (X + C)<nsw> s<= X if C <= 0
+ if (MatchBinaryAddToConst(LHS, RHS, C, SCEV::FlagNSW) &&
+ !C.isStrictlyPositive())
+ return true;
+
+ case ICmpInst::ICMP_SGT:
+ std::swap(LHS, RHS);
+ case ICmpInst::ICMP_SLT:
+ // X s< (X + C)<nsw> if C > 0
+ if (MatchBinaryAddToConst(RHS, LHS, C, SCEV::FlagNSW) &&
+ C.isStrictlyPositive())
+ return true;
+
+ // (X + C)<nsw> s< X if C < 0
+ if (MatchBinaryAddToConst(LHS, RHS, C, SCEV::FlagNSW) && C.isNegative())
+ return true;
+ }
+
+ return false;
+}
+
bool ScalarEvolution::isKnownPredicateViaSplitting(ICmpInst::Predicate Pred,
const SCEV *LHS,
const SCEV *RHS) {
RHS, LHS, FoundLHS, FoundRHS);
}
+ // Unsigned comparison is the same as signed comparison when both the operands
+ // are non-negative.
+ if (CmpInst::isUnsigned(FoundPred) &&
+ CmpInst::getSignedPredicate(FoundPred) == Pred &&
+ isKnownNonNegative(FoundLHS) && isKnownNonNegative(FoundRHS))
+ return isImpliedCondOperands(Pred, LHS, RHS, FoundLHS, FoundRHS);
+
// Check if we can make progress by sharpening ranges.
if (FoundPred == ICmpInst::ICMP_NE &&
(isa<SCEVConstant>(FoundLHS) || isa<SCEVConstant>(FoundRHS))) {
return false;
}
-// Return true if More == (Less + C), where C is a constant.
-static bool IsConstDiff(ScalarEvolution &SE, const SCEV *Less, const SCEV *More,
- APInt &C) {
- // We avoid subtracting expressions here because this function is usually
- // fairly deep in the call stack (i.e. is called many times).
+bool ScalarEvolution::splitBinaryAdd(const SCEV *Expr,
+ const SCEV *&L, const SCEV *&R,
+ SCEV::NoWrapFlags &Flags) {
+ const auto *AE = dyn_cast<SCEVAddExpr>(Expr);
+ if (!AE || AE->getNumOperands() != 2)
+ return false;
- auto SplitBinaryAdd = [](const SCEV *Expr, const SCEV *&L, const SCEV *&R) {
- const auto *AE = dyn_cast<SCEVAddExpr>(Expr);
- if (!AE || AE->getNumOperands() != 2)
- return false;
+ L = AE->getOperand(0);
+ R = AE->getOperand(1);
+ Flags = AE->getNoWrapFlags();
+ return true;
+}
- L = AE->getOperand(0);
- R = AE->getOperand(1);
- return true;
- };
+bool ScalarEvolution::computeConstantDifference(const SCEV *Less,
+ const SCEV *More,
+ APInt &C) {
+ // We avoid subtracting expressions here because this function is usually
+ // fairly deep in the call stack (i.e. is called many times).
if (isa<SCEVAddRecExpr>(Less) && isa<SCEVAddRecExpr>(More)) {
const auto *LAR = cast<SCEVAddRecExpr>(Less);
if (!LAR->isAffine() || !MAR->isAffine())
return false;
- if (LAR->getStepRecurrence(SE) != MAR->getStepRecurrence(SE))
+ if (LAR->getStepRecurrence(*this) != MAR->getStepRecurrence(*this))
return false;
Less = LAR->getStart();
}
const SCEV *L, *R;
- if (SplitBinaryAdd(Less, L, R))
+ SCEV::NoWrapFlags Flags;
+ if (splitBinaryAdd(Less, L, R, Flags))
if (const auto *LC = dyn_cast<SCEVConstant>(L))
if (R == More) {
C = -(LC->getValue()->getValue());
return true;
}
- if (SplitBinaryAdd(More, L, R))
+ if (splitBinaryAdd(More, L, R, Flags))
if (const auto *LC = dyn_cast<SCEVConstant>(L))
if (R == Less) {
C = LC->getValue()->getValue();
// C)".
APInt LDiff, RDiff;
- if (!IsConstDiff(*this, FoundLHS, LHS, LDiff) ||
- !IsConstDiff(*this, FoundRHS, RHS, RDiff) ||
+ if (!computeConstantDifference(FoundLHS, LHS, LDiff) ||
+ !computeConstantDifference(FoundRHS, RHS, RDiff) ||
LDiff != RDiff)
return false;
/// If Expr computes ~A, return A else return nullptr
static const SCEV *MatchNotExpr(const SCEV *Expr) {
const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Expr);
- if (!Add || Add->getNumOperands() != 2) return nullptr;
-
- const SCEVConstant *AddLHS = dyn_cast<SCEVConstant>(Add->getOperand(0));
- if (!(AddLHS && AddLHS->getValue()->getValue().isAllOnesValue()))
+ if (!Add || Add->getNumOperands() != 2 ||
+ !Add->getOperand(0)->isAllOnesValue())
return nullptr;
const SCEVMulExpr *AddRHS = dyn_cast<SCEVMulExpr>(Add->getOperand(1));
- if (!AddRHS || AddRHS->getNumOperands() != 2) return nullptr;
-
- const SCEVConstant *MulLHS = dyn_cast<SCEVConstant>(AddRHS->getOperand(0));
- if (!(MulLHS && MulLHS->getValue()->getValue().isAllOnesValue()))
+ if (!AddRHS || AddRHS->getNumOperands() != 2 ||
+ !AddRHS->getOperand(0)->isAllOnesValue())
return nullptr;
return AddRHS->getOperand(1);
auto IsKnownPredicateFull =
[this](ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS) {
return isKnownPredicateWithRanges(Pred, LHS, RHS) ||
- IsKnownPredicateViaMinOrMax(*this, Pred, LHS, RHS) ||
- IsKnownPredicateViaAddRecStart(*this, Pred, LHS, RHS);
+ IsKnownPredicateViaMinOrMax(*this, Pred, LHS, RHS) ||
+ IsKnownPredicateViaAddRecStart(*this, Pred, LHS, RHS) ||
+ isKnownPredicateViaNoOverflow(Pred, LHS, RHS);
};
switch (Pred) {
Operands[0] = SE.getZero(SC->getType());
const SCEV *Shifted = SE.getAddRecExpr(Operands, getLoop(),
getNoWrapFlags(FlagNW));
- if (const SCEVAddRecExpr *ShiftedAddRec =
- dyn_cast<SCEVAddRecExpr>(Shifted))
+ if (const auto *ShiftedAddRec = dyn_cast<SCEVAddRecExpr>(Shifted))
return ShiftedAddRec->getNumIterationsInRange(
Range.subtract(SC->getValue()->getValue()), SE);
// This is strange and shouldn't happen.
// The only time we can solve this is when we have all constant indices.
// Otherwise, we cannot determine the overflow conditions.
- for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
- if (!isa<SCEVConstant>(getOperand(i)))
- return SE.getCouldNotCompute();
-
+ if (std::any_of(op_begin(), op_end(),
+ [](const SCEV *Op) { return !isa<SCEVConstant>(Op);}))
+ return SE.getCouldNotCompute();
// Okay at this point we know that all elements of the chrec are constants and
// that the start element is zero.
}
bool isDone() const { return false; }
};
+
+// Check if a SCEV contains an AddRecExpr.
+struct SCEVHasAddRec {
+ bool &ContainsAddRec;
+
+ SCEVHasAddRec(bool &ContainsAddRec) : ContainsAddRec(ContainsAddRec) {
+ ContainsAddRec = false;
+ }
+
+ bool follow(const SCEV *S) {
+ if (isa<SCEVAddRecExpr>(S)) {
+ ContainsAddRec = true;
+
+ // Stop recursion: once we collected a term, do not walk its operands.
+ return false;
+ }
+
+ // Keep looking.
+ return true;
+ }
+ bool isDone() const { return false; }
+};
+
+// Find factors that are multiplied with an expression that (possibly as a
+// subexpression) contains an AddRecExpr. In the expression:
+//
+// 8 * (100 + %p * %q * (%a + {0, +, 1}_loop))
+//
+// "%p * %q" are factors multiplied by the expression "(%a + {0, +, 1}_loop)"
+// that contains the AddRec {0, +, 1}_loop. %p * %q are likely to be array size
+// parameters as they form a product with an induction variable.
+//
+// This collector expects all array size parameters to be in the same MulExpr.
+// It might be necessary to later add support for collecting parameters that are
+// spread over different nested MulExpr.
+struct SCEVCollectAddRecMultiplies {
+ SmallVectorImpl<const SCEV *> &Terms;
+ ScalarEvolution &SE;
+
+ SCEVCollectAddRecMultiplies(SmallVectorImpl<const SCEV *> &T, ScalarEvolution &SE)
+ : Terms(T), SE(SE) {}
+
+ bool follow(const SCEV *S) {
+ if (auto *Mul = dyn_cast<SCEVMulExpr>(S)) {
+ bool HasAddRec = false;
+ SmallVector<const SCEV *, 0> Operands;
+ for (auto Op : Mul->operands()) {
+ if (isa<SCEVUnknown>(Op)) {
+ Operands.push_back(Op);
+ } else {
+ bool ContainsAddRec;
+ SCEVHasAddRec ContiansAddRec(ContainsAddRec);
+ visitAll(Op, ContiansAddRec);
+ HasAddRec |= ContainsAddRec;
+ }
+ }
+ if (Operands.size() == 0)
+ return true;
+
+ if (!HasAddRec)
+ return false;
+
+ Terms.push_back(SE.getMulExpr(Operands));
+ // Stop recursion: once we collected a term, do not walk its operands.
+ return false;
+ }
+
+ // Keep looking.
+ return true;
+ }
+ bool isDone() const { return false; }
+};
}
-/// Find parametric terms in this SCEVAddRecExpr.
+/// Find parametric terms in this SCEVAddRecExpr. We first for parameters in
+/// two places:
+/// 1) The strides of AddRec expressions.
+/// 2) Unknowns that are multiplied with AddRec expressions.
void ScalarEvolution::collectParametricTerms(const SCEV *Expr,
SmallVectorImpl<const SCEV *> &Terms) {
SmallVector<const SCEV *, 4> Strides;
for (const SCEV *T : Terms)
dbgs() << *T << "\n";
});
+
+ SCEVCollectAddRecMultiplies MulCollector(Terms, *this);
+ visitAll(Expr, MulCollector);
}
static bool findArrayDimensionsRec(ScalarEvolution &SE,
ScalarEvolution &SE = *const_cast<ScalarEvolution *>(this);
- // Divide all terms by the element size.
+ // Try to divide all terms by the element size. If term is not divisible by
+ // element size, proceed with the original term.
for (const SCEV *&Term : Terms) {
const SCEV *Q, *R;
SCEVDivision::divide(SE, Term, ElementSize, &Q, &R);
- Term = Q;
+ if (!Q->isZero())
+ Term = Q;
}
SmallVector<const SCEV *, 4> NewTerms;
// Free any extra memory created for ExitNotTakenInfo in the unlikely event
// that a loop had multiple computable exits.
- for (DenseMap<const Loop*, BackedgeTakenInfo>::iterator I =
- BackedgeTakenCounts.begin(), E = BackedgeTakenCounts.end();
- I != E; ++I) {
- I->second.clear();
- }
+ for (auto &BTCI : BackedgeTakenCounts)
+ BTCI.second.clear();
assert(PendingLoopPredicates.empty() && "isImpliedCond garbage");
assert(!WalkingBEDominatingConds && "isLoopBackedgeGuardedByCond garbage!");
OS << "Classifying expressions for: ";
F.printAsOperand(OS, /*PrintType=*/false);
OS << "\n";
- for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)
- if (isSCEVable(I->getType()) && !isa<CmpInst>(*I)) {
- OS << *I << '\n';
+ for (Instruction &I : instructions(F))
+ if (isSCEVable(I.getType()) && !isa<CmpInst>(I)) {
+ OS << I << '\n';
OS << " --> ";
- const SCEV *SV = SE.getSCEV(&*I);
+ const SCEV *SV = SE.getSCEV(&I);
SV->print(OS);
if (!isa<SCEVCouldNotCompute>(SV)) {
OS << " U: ";
SE.getSignedRange(SV).print(OS);
}
- const Loop *L = LI.getLoopFor((*I).getParent());
+ const Loop *L = LI.getLoopFor(I.getParent());
const SCEV *AtUse = SE.getSCEVAtScope(SV, L);
if (AtUse != SV) {
projects / oota-llvm.git / blobdiff