for (unsigned i = 1, e = AR->getNumOperands(); i != e; ++i)
OS << ",+," << *AR->getOperand(i);
OS << "}<";
- if (AR->hasNoUnsignedWrap())
+ if (AR->getNoWrapFlags(FlagNUW))
OS << "nuw><";
- if (AR->hasNoSignedWrap())
+ if (AR->getNoWrapFlags(FlagNSW))
OS << "nsw><";
+ if (AR->getNoWrapFlags(FlagNW) &&
+ !AR->getNoWrapFlags((NoWrapFlags)(FlagNUW | FlagNSW)))
+ OS << "nw><";
WriteAsOperand(OS, AR->getLoop()->getHeader(), /*PrintType=*/false);
OS << ">";
return;
OS << "alignof(" << *AllocTy << ")";
return;
}
-
+
const Type *CTy;
Constant *FieldNo;
if (U->isOffsetOf(CTy, FieldNo)) {
OS << ")";
return;
}
-
+
// Otherwise just print it normally.
WriteAsOperand(OS, U->getValue(), false);
return;
Operands.push_back(S);
}
if (!hasTrunc)
- return getAddExpr(Operands, false, false);
+ return getAddExpr(Operands);
UniqueSCEVs.FindNodeOrInsertPos(ID, IP); // Mutates IP, returns NULL.
}
Operands.push_back(S);
}
if (!hasTrunc)
- return getMulExpr(Operands, false, false);
+ return getMulExpr(Operands);
UniqueSCEVs.FindNodeOrInsertPos(ID, IP); // Mutates IP, returns NULL.
}
SmallVector<const SCEV *, 4> Operands;
for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i)
Operands.push_back(getTruncateExpr(AddRec->getOperand(i), Ty));
- return getAddRecExpr(Operands, AddRec->getLoop());
+ return getAddRecExpr(Operands, AddRec->getLoop(), SCEV::FlagAnyWrap);
}
// As a special case, fold trunc(undef) to undef. We don't want to
// If we have special knowledge that this addrec won't overflow,
// we don't need to do any further analysis.
- if (AR->hasNoUnsignedWrap())
+ if (AR->getNoWrapFlags(SCEV::FlagNUW))
return getAddRecExpr(getZeroExtendExpr(Start, Ty),
getZeroExtendExpr(Step, Ty),
- L);
+ L, AR->getNoWrapFlags());
// Check whether the backedge-taken count is SCEVCouldNotCompute.
// Note that this serves two purposes: It filters out loops that are
getAddExpr(getZeroExtendExpr(Start, WideTy),
getMulExpr(getZeroExtendExpr(CastedMaxBECount, WideTy),
getZeroExtendExpr(Step, WideTy)));
- if (getZeroExtendExpr(Add, WideTy) == OperandExtendedAdd)
+ if (getZeroExtendExpr(Add, WideTy) == OperandExtendedAdd) {
+ // Cache knowledge of AR NUW, which is propagated to this AddRec.
+ const_cast<SCEVAddRecExpr *>(AR)->setNoWrapFlags(SCEV::FlagNUW);
// Return the expression with the addrec on the outside.
return getAddRecExpr(getZeroExtendExpr(Start, Ty),
getZeroExtendExpr(Step, Ty),
- L);
-
+ L, AR->getNoWrapFlags());
+ }
// Similar to above, only this time treat the step value as signed.
// This covers loops that count down.
const SCEV *SMul = getMulExpr(CastedMaxBECount, Step);
getAddExpr(getZeroExtendExpr(Start, WideTy),
getMulExpr(getZeroExtendExpr(CastedMaxBECount, WideTy),
getSignExtendExpr(Step, WideTy)));
- if (getZeroExtendExpr(Add, WideTy) == OperandExtendedAdd)
+ if (getZeroExtendExpr(Add, WideTy) == OperandExtendedAdd) {
+ // Cache knowledge of AR NW, which is propagated to this AddRec.
+ // Negative step causes unsigned wrap, but it still can't self-wrap.
+ const_cast<SCEVAddRecExpr *>(AR)->setNoWrapFlags(SCEV::FlagNW);
// Return the expression with the addrec on the outside.
return getAddRecExpr(getZeroExtendExpr(Start, Ty),
getSignExtendExpr(Step, Ty),
- L);
+ L, AR->getNoWrapFlags());
+ }
}
// If the backedge is guarded by a comparison with the pre-inc value
if (isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_ULT, AR, N) ||
(isLoopEntryGuardedByCond(L, ICmpInst::ICMP_ULT, Start, N) &&
isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_ULT,
- AR->getPostIncExpr(*this), N)))
+ AR->getPostIncExpr(*this), N))) {
+ // Cache knowledge of AR NUW, which is propagated to this AddRec.
+ const_cast<SCEVAddRecExpr *>(AR)->setNoWrapFlags(SCEV::FlagNUW);
// Return the expression with the addrec on the outside.
return getAddRecExpr(getZeroExtendExpr(Start, Ty),
getZeroExtendExpr(Step, Ty),
- L);
+ L, AR->getNoWrapFlags());
+ }
} else if (isKnownNegative(Step)) {
const SCEV *N = getConstant(APInt::getMaxValue(BitWidth) -
getSignedRange(Step).getSignedMin());
if (isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_UGT, AR, N) ||
(isLoopEntryGuardedByCond(L, ICmpInst::ICMP_UGT, Start, N) &&
isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_UGT,
- AR->getPostIncExpr(*this), N)))
+ AR->getPostIncExpr(*this), N))) {
+ // Cache knowledge of AR NW, which is propagated to this AddRec.
+ // Negative step causes unsigned wrap, but it still can't self-wrap.
+ const_cast<SCEVAddRecExpr *>(AR)->setNoWrapFlags(SCEV::FlagNW);
// Return the expression with the addrec on the outside.
return getAddRecExpr(getZeroExtendExpr(Start, Ty),
getSignExtendExpr(Step, Ty),
- L);
+ L, AR->getNoWrapFlags());
+ }
}
}
}
// If we have special knowledge that this addrec won't overflow,
// we don't need to do any further analysis.
- if (AR->hasNoSignedWrap())
+ if (AR->getNoWrapFlags(SCEV::FlagNSW))
return getAddRecExpr(getSignExtendExpr(Start, Ty),
getSignExtendExpr(Step, Ty),
- L);
+ L, SCEV::FlagNSW);
// Check whether the backedge-taken count is SCEVCouldNotCompute.
// Note that this serves two purposes: It filters out loops that are
getAddExpr(getSignExtendExpr(Start, WideTy),
getMulExpr(getZeroExtendExpr(CastedMaxBECount, WideTy),
getSignExtendExpr(Step, WideTy)));
- if (getSignExtendExpr(Add, WideTy) == OperandExtendedAdd)
+ if (getSignExtendExpr(Add, WideTy) == OperandExtendedAdd) {
+ // Cache knowledge of AR NSW, which is propagated to this AddRec.
+ const_cast<SCEVAddRecExpr *>(AR)->setNoWrapFlags(SCEV::FlagNSW);
// Return the expression with the addrec on the outside.
return getAddRecExpr(getSignExtendExpr(Start, Ty),
getSignExtendExpr(Step, Ty),
- L);
-
+ L, AR->getNoWrapFlags());
+ }
// Similar to above, only this time treat the step value as unsigned.
// This covers loops that count up with an unsigned step.
const SCEV *UMul = getMulExpr(CastedMaxBECount, Step);
getAddExpr(getSignExtendExpr(Start, WideTy),
getMulExpr(getZeroExtendExpr(CastedMaxBECount, WideTy),
getZeroExtendExpr(Step, WideTy)));
- if (getSignExtendExpr(Add, WideTy) == OperandExtendedAdd)
+ if (getSignExtendExpr(Add, WideTy) == OperandExtendedAdd) {
+ // Cache knowledge of AR NSW, which is propagated to this AddRec.
+ const_cast<SCEVAddRecExpr *>(AR)->setNoWrapFlags(SCEV::FlagNSW);
// Return the expression with the addrec on the outside.
return getAddRecExpr(getSignExtendExpr(Start, Ty),
getZeroExtendExpr(Step, Ty),
- L);
+ L, AR->getNoWrapFlags());
+ }
}
// If the backedge is guarded by a comparison with the pre-inc value
if (isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_SLT, AR, N) ||
(isLoopEntryGuardedByCond(L, ICmpInst::ICMP_SLT, Start, N) &&
isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_SLT,
- AR->getPostIncExpr(*this), N)))
+ AR->getPostIncExpr(*this), N))) {
+ // Cache knowledge of AR NSW, which is propagated to this AddRec.
+ const_cast<SCEVAddRecExpr *>(AR)->setNoWrapFlags(SCEV::FlagNSW);
// Return the expression with the addrec on the outside.
return getAddRecExpr(getSignExtendExpr(Start, Ty),
getSignExtendExpr(Step, Ty),
- L);
+ L, AR->getNoWrapFlags());
+ }
} else if (isKnownNegative(Step)) {
const SCEV *N = getConstant(APInt::getSignedMaxValue(BitWidth) -
getSignedRange(Step).getSignedMin());
if (isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_SGT, AR, N) ||
(isLoopEntryGuardedByCond(L, ICmpInst::ICMP_SGT, Start, N) &&
isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_SGT,
- AR->getPostIncExpr(*this), N)))
+ AR->getPostIncExpr(*this), N))) {
+ // Cache knowledge of AR NSW, which is propagated to this AddRec.
+ const_cast<SCEVAddRecExpr *>(AR)->setNoWrapFlags(SCEV::FlagNSW);
// Return the expression with the addrec on the outside.
return getAddRecExpr(getSignExtendExpr(Start, Ty),
getSignExtendExpr(Step, Ty),
- L);
+ L, AR->getNoWrapFlags());
+ }
}
}
}
for (SCEVAddRecExpr::op_iterator I = AR->op_begin(), E = AR->op_end();
I != E; ++I)
Ops.push_back(getAnyExtendExpr(*I, Ty));
- return getAddRecExpr(Ops, AR->getLoop());
+ return getAddRecExpr(Ops, AR->getLoop(), SCEV::FlagNW);
}
// As a special case, fold anyext(undef) to undef. We don't want to
/// getAddExpr - Get a canonical add expression, or something simpler if
/// possible.
const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl<const SCEV *> &Ops,
- bool HasNUW, bool HasNSW) {
+ SCEV::NoWrapFlags Flags) {
+ assert(!(Flags & ~(SCEV::FlagNUW | SCEV::FlagNSW)) &&
+ "only nuw or nsw allowed");
assert(!Ops.empty() && "Cannot get empty add!");
if (Ops.size() == 1) return Ops[0];
#ifndef NDEBUG
"SCEVAddExpr operand types don't match!");
#endif
- // If HasNSW is true and all the operands are non-negative, infer HasNUW.
- if (!HasNUW && HasNSW) {
+ // If FlagNSW is true and all the operands are non-negative, infer FlagNUW.
+ // And vice-versa.
+ int SignOrUnsignMask = SCEV::FlagNUW | SCEV::FlagNSW;
+ SCEV::NoWrapFlags SignOrUnsignWrap = maskFlags(Flags, SignOrUnsignMask);
+ if (SignOrUnsignWrap && (SignOrUnsignWrap != SignOrUnsignMask)) {
bool All = true;
for (SmallVectorImpl<const SCEV *>::const_iterator I = Ops.begin(),
E = Ops.end(); I != E; ++I)
All = false;
break;
}
- if (All) HasNUW = true;
+ if (All) Flags = setFlags(Flags, (SCEV::NoWrapFlags)SignOrUnsignMask);
}
// Sort by complexity, this groups all similar expression types together.
FoundMatch = true;
}
if (FoundMatch)
- return getAddExpr(Ops, HasNUW, HasNSW);
+ return getAddExpr(Ops, Flags);
// Check for truncates. If all the operands are truncated from the same
// type, see if factoring out the truncate would permit the result to be
}
if (Ok) {
// Evaluate the expression in the larger type.
- const SCEV *Fold = getAddExpr(LargeOps, HasNUW, HasNSW);
+ const SCEV *Fold = getAddExpr(LargeOps, Flags);
// If it folds to something simple, use it. Otherwise, don't.
if (isa<SCEVConstant>(Fold) || isa<SCEVUnknown>(Fold))
return getTruncateExpr(Fold, DstType);
// Build the new addrec. Propagate the NUW and NSW flags if both the
// outer add and the inner addrec are guaranteed to have no overflow.
- const SCEV *NewRec = getAddRecExpr(AddRecOps, AddRecLoop,
- HasNUW && AddRec->hasNoUnsignedWrap(),
- HasNSW && AddRec->hasNoSignedWrap());
+ // Always propagate NW.
+ Flags = AddRec->getNoWrapFlags(setFlags(Flags, SCEV::FlagNW));
+ const SCEV *NewRec = getAddRecExpr(AddRecOps, AddRecLoop, Flags);
// If all of the other operands were loop invariant, we are done.
if (Ops.size() == 1) return NewRec;
}
Ops.erase(Ops.begin() + OtherIdx); --OtherIdx;
}
- Ops[Idx] = getAddRecExpr(AddRecOps, AddRecLoop);
+ // Step size has changed, so we cannot guarantee no self-wraparound.
+ Ops[Idx] = getAddRecExpr(AddRecOps, AddRecLoop, SCEV::FlagAnyWrap);
return getAddExpr(Ops);
}
O, Ops.size());
UniqueSCEVs.InsertNode(S, IP);
}
- if (HasNUW) S->setHasNoUnsignedWrap(true);
- if (HasNSW) S->setHasNoSignedWrap(true);
+ S->setNoWrapFlags(Flags);
return S;
}
/// getMulExpr - Get a canonical multiply expression, or something simpler if
/// possible.
const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV *> &Ops,
- bool HasNUW, bool HasNSW) {
+ SCEV::NoWrapFlags Flags) {
+ assert(Flags == maskFlags(Flags, SCEV::FlagNUW | SCEV::FlagNSW) &&
+ "only nuw or nsw allowed");
assert(!Ops.empty() && "Cannot get empty mul!");
if (Ops.size() == 1) return Ops[0];
#ifndef NDEBUG
"SCEVMulExpr operand types don't match!");
#endif
- // If HasNSW is true and all the operands are non-negative, infer HasNUW.
- if (!HasNUW && HasNSW) {
+ // If FlagNSW is true and all the operands are non-negative, infer FlagNUW.
+ // And vice-versa.
+ int SignOrUnsignMask = SCEV::FlagNUW | SCEV::FlagNSW;
+ SCEV::NoWrapFlags SignOrUnsignWrap = maskFlags(Flags, SignOrUnsignMask);
+ if (SignOrUnsignWrap && (SignOrUnsignWrap != SignOrUnsignMask)) {
bool All = true;
for (SmallVectorImpl<const SCEV *>::const_iterator I = Ops.begin(),
E = Ops.end(); I != E; ++I)
All = false;
break;
}
- if (All) HasNUW = true;
+ if (All) Flags = setFlags(Flags, (SCEV::NoWrapFlags)SignOrUnsignMask);
}
// Sort by complexity, this groups all similar expression types together.
} else if (Ops[0]->isAllOnesValue()) {
// If we have a mul by -1 of an add, try distributing the -1 among the
// add operands.
- if (Ops.size() == 2)
+ if (Ops.size() == 2) {
if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[1])) {
SmallVector<const SCEV *, 4> NewOps;
bool AnyFolded = false;
- for (SCEVAddRecExpr::op_iterator I = Add->op_begin(), E = Add->op_end();
- I != E; ++I) {
+ for (SCEVAddRecExpr::op_iterator I = Add->op_begin(),
+ E = Add->op_end(); I != E; ++I) {
const SCEV *Mul = getMulExpr(Ops[0], *I);
if (!isa<SCEVMulExpr>(Mul)) AnyFolded = true;
NewOps.push_back(Mul);
if (AnyFolded)
return getAddExpr(NewOps);
}
+ else if (const SCEVAddRecExpr *
+ 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(),
+ E = AddRec->op_end(); I != E; ++I) {
+ Operands.push_back(getMulExpr(Ops[0], *I));
+ }
+ return getAddRecExpr(Operands, AddRec->getLoop(),
+ AddRec->getNoWrapFlags(SCEV::FlagNW));
+ }
+ }
}
if (Ops.size() == 1)
// Build the new addrec. Propagate the NUW and NSW flags if both the
// outer mul and the inner addrec are guaranteed to have no overflow.
- const SCEV *NewRec = getAddRecExpr(NewOps, AddRecLoop,
- HasNUW && AddRec->hasNoUnsignedWrap(),
- HasNSW && AddRec->hasNoSignedWrap());
+ //
+ // No self-wrap cannot be guaranteed after changing the step size, but
+ // will be inferred if either NUW or NSW is true.
+ Flags = AddRec->getNoWrapFlags(clearFlags(Flags, SCEV::FlagNW));
+ const SCEV *NewRec = getAddRecExpr(NewOps, AddRecLoop, Flags);
// If all of the other operands were loop invariant, we are done.
if (Ops.size() == 1) return NewRec;
getMulExpr(G, B),
getMulExpr(B, D));
const SCEV *NewAddRec = getAddRecExpr(NewStart, NewStep,
- F->getLoop());
+ F->getLoop(),
+ SCEV::FlagAnyWrap);
if (Ops.size() == 2) return NewAddRec;
Ops[Idx] = AddRec = cast<SCEVAddRecExpr>(NewAddRec);
Ops.erase(Ops.begin() + OtherIdx); --OtherIdx;
O, Ops.size());
UniqueSCEVs.InsertNode(S, IP);
}
- if (HasNUW) S->setHasNoUnsignedWrap(true);
- if (HasNSW) S->setHasNoSignedWrap(true);
+ S->setNoWrapFlags(Flags);
return S;
}
getZeroExtendExpr(AR, ExtTy) ==
getAddRecExpr(getZeroExtendExpr(AR->getStart(), ExtTy),
getZeroExtendExpr(Step, ExtTy),
- AR->getLoop())) {
+ 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());
+ return getAddRecExpr(Operands, AR->getLoop(),
+ SCEV::FlagNW);
}
// (A*B)/C --> A*(B/C) if safe and B/C can be folded.
if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(LHS)) {
/// getAddRecExpr - Get an add recurrence expression for the specified loop.
/// Simplify the expression as much as possible.
-const SCEV *ScalarEvolution::getAddRecExpr(const SCEV *Start,
- const SCEV *Step, const Loop *L,
- bool HasNUW, bool HasNSW) {
+const SCEV *ScalarEvolution::getAddRecExpr(const SCEV *Start, const SCEV *Step,
+ const Loop *L,
+ SCEV::NoWrapFlags Flags) {
SmallVector<const SCEV *, 4> Operands;
Operands.push_back(Start);
if (const SCEVAddRecExpr *StepChrec = dyn_cast<SCEVAddRecExpr>(Step))
if (StepChrec->getLoop() == L) {
Operands.append(StepChrec->op_begin(), StepChrec->op_end());
- return getAddRecExpr(Operands, L);
+ return getAddRecExpr(Operands, L, maskFlags(Flags, SCEV::FlagNW));
}
Operands.push_back(Step);
- return getAddRecExpr(Operands, L, HasNUW, HasNSW);
+ return getAddRecExpr(Operands, L, Flags);
}
/// getAddRecExpr - Get an add recurrence expression for the specified loop.
/// Simplify the expression as much as possible.
const SCEV *
ScalarEvolution::getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands,
- const Loop *L,
- bool HasNUW, bool HasNSW) {
+ const Loop *L, SCEV::NoWrapFlags Flags) {
if (Operands.size() == 1) return Operands[0];
#ifndef NDEBUG
const Type *ETy = getEffectiveSCEVType(Operands[0]->getType());
if (Operands.back()->isZero()) {
Operands.pop_back();
- return getAddRecExpr(Operands, L, HasNUW, HasNSW); // {X,+,0} --> X
+ return getAddRecExpr(Operands, L, SCEV::FlagAnyWrap); // {X,+,0} --> X
}
// It's tempting to want to call getMaxBackedgeTakenCount count here and
// meaningful BE count at this point (and if we don't, we'd be stuck
// with a SCEVCouldNotCompute as the cached BE count).
- // If HasNSW is true and all the operands are non-negative, infer HasNUW.
- if (!HasNUW && HasNSW) {
+ // If FlagNSW is true and all the operands are non-negative, infer FlagNUW.
+ // And vice-versa.
+ int SignOrUnsignMask = SCEV::FlagNUW | SCEV::FlagNSW;
+ SCEV::NoWrapFlags SignOrUnsignWrap = maskFlags(Flags, SignOrUnsignMask);
+ if (SignOrUnsignWrap && (SignOrUnsignWrap != SignOrUnsignMask)) {
bool All = true;
for (SmallVectorImpl<const SCEV *>::const_iterator I = Operands.begin(),
E = Operands.end(); I != E; ++I)
All = false;
break;
}
- if (All) HasNUW = true;
+ if (All) Flags = setFlags(Flags, (SCEV::NoWrapFlags)SignOrUnsignMask);
}
// Canonicalize nested AddRecs in by nesting them in order of loop depth.
break;
}
if (AllInvariant) {
- NestedOperands[0] = getAddRecExpr(Operands, L);
+ // Create a recurrence for the outer loop with the same step size.
+ //
+ // The outer recurrence keeps its NW flag but only keeps NUW/NSW if the
+ // inner recurrence has the same property.
+ SCEV::NoWrapFlags OuterFlags =
+ 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;
}
- if (AllInvariant)
+ if (AllInvariant) {
// Ok, both add recurrences are valid after the transformation.
- return getAddRecExpr(NestedOperands, NestedLoop, HasNUW, HasNSW);
+ //
+ // The inner recurrence keeps its NW flag but only keeps NUW/NSW if
+ // the outer recurrence has the same property.
+ SCEV::NoWrapFlags InnerFlags =
+ maskFlags(NestedAR->getNoWrapFlags(), SCEV::FlagNW | Flags);
+ return getAddRecExpr(NestedOperands, NestedLoop, InnerFlags);
+ }
}
// Reset Operands to its original state.
Operands[0] = NestedAR;
O, Operands.size(), L);
UniqueSCEVs.InsertNode(S, IP);
}
- if (HasNUW) S->setHasNoUnsignedWrap(true);
- if (HasNSW) S->setHasNoSignedWrap(true);
+ S->setNoWrapFlags(Flags);
return S;
}
return getMinusSCEV(AllOnes, V);
}
-/// getMinusSCEV - Return LHS-RHS. Minus is represented in SCEV as A+B*-1,
-/// and thus the HasNUW and HasNSW bits apply to the resultant add, not
-/// whether the sub would have overflowed.
+/// getMinusSCEV - Return LHS-RHS. Minus is represented in SCEV as A+B*-1.
const SCEV *ScalarEvolution::getMinusSCEV(const SCEV *LHS, const SCEV *RHS,
- bool HasNUW, bool HasNSW) {
+ SCEV::NoWrapFlags Flags) {
+ assert(!maskFlags(Flags, SCEV::FlagNUW) && "subtraction does not have NUW");
+
// Fast path: X - X --> 0.
if (LHS == RHS)
return getConstant(LHS->getType(), 0);
// X - Y --> X + -Y
- return getAddExpr(LHS, getNegativeSCEV(RHS), HasNUW, HasNSW);
+ return getAddExpr(LHS, getNegativeSCEV(RHS), Flags);
}
/// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion of the
return getUMinExpr(PromotedLHS, PromotedRHS);
}
+/// getPointerBase - Transitively follow the chain of pointer-type operands
+/// until reaching a SCEV that does not have a single pointer operand. This
+/// returns a SCEVUnknown pointer for well-formed pointer-type expressions,
+/// but corner cases do exist.
+const SCEV *ScalarEvolution::getPointerBase(const SCEV *V) {
+ // A pointer operand may evaluate to a nonpointer expression, such as null.
+ if (!V->getType()->isPointerTy())
+ return V;
+
+ if (const SCEVCastExpr *Cast = dyn_cast<SCEVCastExpr>(V)) {
+ return getPointerBase(Cast->getOperand());
+ }
+ else if (const SCEVNAryExpr *NAry = dyn_cast<SCEVNAryExpr>(V)) {
+ const SCEV *PtrOp = 0;
+ for (SCEVNAryExpr::op_iterator I = NAry->op_begin(), E = NAry->op_end();
+ I != E; ++I) {
+ if ((*I)->getType()->isPointerTy()) {
+ // Cannot find the base of an expression with multiple pointer operands.
+ if (PtrOp)
+ return V;
+ PtrOp = *I;
+ }
+ }
+ if (!PtrOp)
+ return V;
+ return getPointerBase(PtrOp);
+ }
+ return V;
+}
+
/// PushDefUseChildren - Push users of the given Instruction
/// onto the given Worklist.
static void
if (isLoopInvariant(Accum, L) ||
(isa<SCEVAddRecExpr>(Accum) &&
cast<SCEVAddRecExpr>(Accum)->getLoop() == L)) {
- bool HasNUW = false;
- bool HasNSW = false;
+ SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap;
// If the increment doesn't overflow, then neither the addrec nor
// the post-increment will overflow.
if (const AddOperator *OBO = dyn_cast<AddOperator>(BEValueV)) {
if (OBO->hasNoUnsignedWrap())
- HasNUW = true;
+ Flags = setFlags(Flags, SCEV::FlagNUW);
if (OBO->hasNoSignedWrap())
- HasNSW = true;
- } else if (const GEPOperator *GEP =
- dyn_cast<GEPOperator>(BEValueV)) {
- // If the increment is a GEP, then we know it won't perform an
- // unsigned overflow, because the address space cannot be
- // wrapped around.
- HasNUW |= GEP->isInBounds();
+ Flags = setFlags(Flags, SCEV::FlagNSW);
+ } else if (const GEPOperator *GEP =
+ dyn_cast<GEPOperator>(BEValueV)) {
+ // If the increment is an inbounds GEP, then we know the address
+ // space cannot be wrapped around. We cannot make any guarantee
+ // about signed or unsigned overflow because pointers are
+ // unsigned but we may have a negative index from the base
+ // pointer.
+ if (GEP->isInBounds())
+ Flags = setFlags(Flags, SCEV::FlagNW);
}
const SCEV *StartVal = getSCEV(StartValueV);
- const SCEV *PHISCEV =
- getAddRecExpr(StartVal, Accum, L, HasNUW, HasNSW);
+ const SCEV *PHISCEV = getAddRecExpr(StartVal, Accum, L, Flags);
// Since the no-wrap flags are on the increment, they apply to the
// post-incremented value as well.
if (isLoopInvariant(Accum, L))
(void)getAddRecExpr(getAddExpr(StartVal, Accum),
- Accum, L, HasNUW, HasNSW);
+ Accum, L, Flags);
// Okay, for the entire analysis of this edge we assumed the PHI
// to be symbolic. We now need to go back and purge all of the
// initial step of the addrec evolution.
if (StartVal == getMinusSCEV(AddRec->getOperand(0),
AddRec->getOperand(1))) {
+ // FIXME: For constant StartVal, we should be able to infer
+ // no-wrap flags.
const SCEV *PHISCEV =
- getAddRecExpr(StartVal, AddRec->getOperand(1), L);
+ getAddRecExpr(StartVal, AddRec->getOperand(1), L,
+ SCEV::FlagAnyWrap);
// Okay, for the entire analysis of this edge we assumed the PHI
// to be symbolic. We now need to go back and purge all of the
// Add expression, because the Instruction may be guarded by control flow
// and the no-overflow bits may not be valid for the expression in any
// context.
+ bool isInBounds = GEP->isInBounds();
const Type *IntPtrTy = getEffectiveSCEVType(GEP->getType());
Value *Base = GEP->getOperand(0);
IndexS = getTruncateOrSignExtend(IndexS, IntPtrTy);
// Multiply the index by the element size to compute the element offset.
- const SCEV *LocalOffset = getMulExpr(IndexS, ElementSize);
+ const SCEV *LocalOffset = getMulExpr(IndexS, ElementSize,
+ isInBounds ? SCEV::FlagNSW :
+ SCEV::FlagAnyWrap);
// Add the element offset to the running total offset.
TotalOffset = getAddExpr(TotalOffset, LocalOffset);
const SCEV *BaseS = getSCEV(Base);
// Add the total offset from all the GEP indices to the base.
- return getAddExpr(BaseS, TotalOffset);
+ return getAddExpr(BaseS, TotalOffset,
+ isInBounds ? SCEV::FlagNSW : SCEV::FlagAnyWrap);
}
/// GetMinTrailingZeros - Determine the minimum number of zero bits that S is
if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S)) {
// If there's no unsigned wrap, the value will never be less than its
// initial value.
- if (AddRec->hasNoUnsignedWrap())
+ if (AddRec->getNoWrapFlags(SCEV::FlagNUW))
if (const SCEVConstant *C = dyn_cast<SCEVConstant>(AddRec->getStart()))
if (!C->getValue()->isZero())
ConservativeResult =
if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S)) {
// If there's no signed wrap, and all the operands have the same sign or
// zero, the value won't ever change sign.
- if (AddRec->hasNoSignedWrap()) {
+ if (AddRec->getNoWrapFlags(SCEV::FlagNSW)) {
bool AllNonNeg = true;
bool AllNonPos = true;
for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) {
SmallVector<const SCEV *, 4> MulOps;
MulOps.push_back(getSCEV(U->getOperand(1)));
for (Value *Op = U->getOperand(0);
- Op->getValueID() == Instruction::Mul + Value::InstructionVal;
+ Op->getValueID() == Instruction::Mul + Value::InstructionVal;
Op = U->getOperand(0)) {
U = cast<Operator>(Op);
MulOps.push_back(getSCEV(U->getOperand(1)));
// transfer the no-wrap flags, since an or won't introduce a wrap.
if (const SCEVAddRecExpr *NewAR = dyn_cast<SCEVAddRecExpr>(S)) {
const SCEVAddRecExpr *OldAR = cast<SCEVAddRecExpr>(LHS);
- if (OldAR->hasNoUnsignedWrap())
- const_cast<SCEVAddRecExpr *>(NewAR)->setHasNoUnsignedWrap(true);
- if (OldAR->hasNoSignedWrap())
- const_cast<SCEVAddRecExpr *>(NewAR)->setHasNoSignedWrap(true);
+ const_cast<SCEVAddRecExpr *>(NewAR)->setNoWrapFlags(
+ OldAR->getNoWrapFlags());
}
return S;
}
return ComputeBackedgeTakenCountExhaustively(L, ExitCond, !L->contains(TBB));
}
-static const SCEVAddRecExpr *
-isSimpleUnwrappingAddRec(const SCEV *S, const Loop *L) {
- const SCEVAddRecExpr *SA = dyn_cast<SCEVAddRecExpr>(S);
-
- // The SCEV must be an addrec of this loop.
- if (!SA || SA->getLoop() != L || !SA->isAffine())
- return 0;
-
- // The SCEV must be known to not wrap in some way to be interesting.
- if (!SA->hasNoUnsignedWrap() && !SA->hasNoSignedWrap())
- return 0;
-
- // The stride must be a constant so that we know if it is striding up or down.
- if (!isa<SCEVConstant>(SA->getOperand(1)))
- return 0;
- return SA;
-}
-
-/// getMinusSCEVForExitTest - When considering an exit test for a loop with a
-/// "x != y" exit test, we turn this into a computation that evaluates x-y != 0,
-/// and this function returns the expression to use for x-y. We know and take
-/// advantage of the fact that this subtraction is only being used in a
-/// comparison by zero context.
-///
-static const SCEV *getMinusSCEVForExitTest(const SCEV *LHS, const SCEV *RHS,
- const Loop *L, ScalarEvolution &SE) {
- // If either LHS or RHS is an AddRec SCEV (of this loop) that is known to not
- // wrap (either NSW or NUW), then we know that the value will either become
- // the other one (and thus the loop terminates), that the loop will terminate
- // through some other exit condition first, or that the loop has undefined
- // behavior. This information is useful when the addrec has a stride that is
- // != 1 or -1, because it means we can't "miss" the exit value.
- //
- // In any of these three cases, it is safe to turn the exit condition into a
- // "counting down" AddRec (to zero) by subtracting the two inputs as normal,
- // but since we know that the "end cannot be missed" we can force the
- // resulting AddRec to be a NUW addrec. Since it is counting down, this means
- // that the AddRec *cannot* pass zero.
-
- // See if LHS and RHS are addrec's we can handle.
- const SCEVAddRecExpr *LHSA = isSimpleUnwrappingAddRec(LHS, L);
- const SCEVAddRecExpr *RHSA = isSimpleUnwrappingAddRec(RHS, L);
-
- // If neither addrec is interesting, just return a minus.
- if (RHSA == 0 && LHSA == 0)
- return SE.getMinusSCEV(LHS, RHS);
-
- // If only one of LHS and RHS are an AddRec of this loop, make sure it is LHS.
- if (RHSA && LHSA == 0) {
- // Safe because a-b === b-a for comparisons against zero.
- std::swap(LHS, RHS);
- std::swap(LHSA, RHSA);
- }
-
- // Handle the case when only one is advancing in a non-overflowing way.
- if (RHSA == 0) {
- // If RHS is loop varying, then we can't predict when LHS will cross it.
- if (!SE.isLoopInvariant(RHS, L))
- return SE.getMinusSCEV(LHS, RHS);
-
- // If LHS has a positive stride, then we compute RHS-LHS, because the loop
- // is counting up until it crosses RHS (which must be larger than LHS). If
- // it is negative, we compute LHS-RHS because we're counting down to RHS.
- const ConstantInt *Stride =
- cast<SCEVConstant>(LHSA->getOperand(1))->getValue();
- if (Stride->getValue().isNegative())
- std::swap(LHS, RHS);
-
- return SE.getMinusSCEV(RHS, LHS, true /*HasNUW*/);
- }
-
- // If both LHS and RHS are interesting, we have something like:
- // a+i*4 != b+i*8.
- const ConstantInt *LHSStride =
- cast<SCEVConstant>(LHSA->getOperand(1))->getValue();
- const ConstantInt *RHSStride =
- cast<SCEVConstant>(RHSA->getOperand(1))->getValue();
-
- // If the strides are equal, then this is just a (complex) loop invariant
- // comparison of a and b.
- if (LHSStride == RHSStride)
- return SE.getMinusSCEV(LHSA->getStart(), RHSA->getStart());
-
- // If the signs of the strides differ, then the negative stride is counting
- // down to the positive stride.
- if (LHSStride->getValue().isNegative() != RHSStride->getValue().isNegative()){
- if (RHSStride->getValue().isNegative())
- std::swap(LHS, RHS);
- } else {
- // If LHS's stride is smaller than RHS's stride, then "b" must be less than
- // "a" and "b" is RHS is counting up (catching up) to LHS. This is true
- // whether the strides are positive or negative.
- if (RHSStride->getValue().slt(LHSStride->getValue()))
- std::swap(LHS, RHS);
- }
-
- return SE.getMinusSCEV(LHS, RHS, true /*HasNUW*/);
-}
-
/// ComputeBackedgeTakenCountFromExitCondICmp - Compute the number of times the
/// backedge of the specified loop will execute if its exit condition
/// were a conditional branch of the ICmpInst ExitCond, TBB, and FBB.
switch (Cond) {
case ICmpInst::ICMP_NE: { // while (X != Y)
// Convert to: while (X-Y != 0)
- BackedgeTakenInfo BTI = HowFarToZero(getMinusSCEVForExitTest(LHS, RHS, L,
- *this), L);
+ BackedgeTakenInfo BTI = HowFarToZero(getMinusSCEV(LHS, RHS), L);
if (BTI.hasAnyInfo()) return BTI;
break;
}
for (++i; i != e; ++i)
NewOps.push_back(getSCEVAtScope(AddRec->getOperand(i), L));
- AddRec = cast<SCEVAddRecExpr>(getAddRecExpr(NewOps, AddRec->getLoop()));
+ AddRec = cast<SCEVAddRecExpr>(
+ getAddRecExpr(NewOps, AddRec->getLoop(),
+ AddRec->getNoWrapFlags(SCEV::FlagNW)));
break;
}
/// HowFarToZero - Return the number of times a backedge comparing the specified
/// value to zero will execute. If not computable, return CouldNotCompute.
+///
+/// This is only used for loops with a "x != y" exit test. The exit condition is
+/// now expressed as a single expression, V = x-y. So the exit test is
+/// effectively V != 0. We know and take advantage of the fact that this
+/// expression only being used in a comparison by zero context.
ScalarEvolution::BackedgeTakenInfo
ScalarEvolution::HowFarToZero(const SCEV *V, const Loop *L) {
// If the value is a constant
R2->getValue()))) {
if (CB->getZExtValue() == false)
std::swap(R1, R2); // R1 is the minimum root now.
-
+
// We can only use this value if the chrec ends up with an exact zero
// value at this index. When solving for "X*X != 5", for example, we
// should not accept a root of 2.
const SCEV *Start = getSCEVAtScope(AddRec->getStart(), L->getParentLoop());
const SCEV *Step = getSCEVAtScope(AddRec->getOperand(1), L->getParentLoop());
- // If the AddRec is NUW, then (in an unsigned sense) it cannot be counting up
- // to wrap to 0, it must be counting down to equal 0. Also, while counting
- // down, it cannot "miss" 0 (which would cause it to wrap), regardless of what
- // the stride is. As such, NUW addrec's will always become zero in
- // "start / -stride" steps, and we know that the division is exact.
- if (AddRec->hasNoUnsignedWrap())
- // FIXME: We really want an "isexact" bit for udiv.
- return getUDivExpr(Start, getNegativeSCEV(Step));
-
// For now we handle only constant steps.
+ //
+ // TODO: Handle a nonconstant Step given AddRec<NUW>. If the
+ // AddRec is NUW, then (in an unsigned sense) it cannot be counting up to wrap
+ // to 0, it must be counting down to equal 0. Consequently, N = Start / -Step.
+ // We have not yet seen any such cases.
const SCEVConstant *StepC = dyn_cast<SCEVConstant>(Step);
if (StepC == 0)
return getCouldNotCompute();
- // First, handle unitary steps.
- if (StepC->getValue()->equalsInt(1)) // 1*N = -Start (mod 2^BW), so:
- return getNegativeSCEV(Start); // N = -Start (as unsigned)
-
- if (StepC->getValue()->isAllOnesValue()) // -1*N = -Start (mod 2^BW), so:
- return Start; // N = Start (as unsigned)
+ // For positive steps (counting up until unsigned overflow):
+ // N = -Start/Step (as unsigned)
+ // For negative steps (counting down to zero):
+ // N = Start/-Step
+ // First compute the unsigned distance from zero in the direction of Step.
+ bool CountDown = StepC->getValue()->getValue().isNegative();
+ const SCEV *Distance = CountDown ? Start : getNegativeSCEV(Start);
+
+ // Handle unitary steps, which cannot wraparound.
+ // 1*N = -Start; -1*N = Start (mod 2^BW), so:
+ // N = Distance (as unsigned)
+ if (StepC->getValue()->equalsInt(1) || StepC->getValue()->isAllOnesValue())
+ return Distance;
+
+ // If the recurrence is known not to wraparound, unsigned divide computes the
+ // back edge count. We know that the value will either become zero (and thus
+ // the loop terminates), that the loop will terminate through some other exit
+ // condition first, or that the loop has undefined behavior. This means
+ // we can't "miss" the exit value, even with nonunit stride.
+ //
+ // FIXME: Prove that loops always exhibits *acceptable* undefined
+ // behavior. Loops must exhibit defined behavior until a wrapped value is
+ // actually used. So the trip count computed by udiv could be smaller than the
+ // number of well-defined iterations.
+ if (AddRec->getNoWrapFlags(SCEV::FlagNW))
+ // FIXME: We really want an "isexact" bit for udiv.
+ return getUDivExpr(Distance, CountDown ? getNegativeSCEV(Step) : Step);
// Then, try to solve the above equation provided that Start is constant.
if (const SCEVConstant *StartC = dyn_cast<SCEVConstant>(Start))
case ICmpInst::ICMP_SLE:
if (!getSignedRange(RHS).getSignedMax().isMaxSignedValue()) {
RHS = getAddExpr(getConstant(RHS->getType(), 1, true), RHS,
- /*HasNUW=*/false, /*HasNSW=*/true);
+ SCEV::FlagNSW);
Pred = ICmpInst::ICMP_SLT;
Changed = true;
} else if (!getSignedRange(LHS).getSignedMin().isMinSignedValue()) {
LHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), LHS,
- /*HasNUW=*/false, /*HasNSW=*/true);
+ SCEV::FlagNSW);
Pred = ICmpInst::ICMP_SLT;
Changed = true;
}
case ICmpInst::ICMP_SGE:
if (!getSignedRange(RHS).getSignedMin().isMinSignedValue()) {
RHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), RHS,
- /*HasNUW=*/false, /*HasNSW=*/true);
+ SCEV::FlagNSW);
Pred = ICmpInst::ICMP_SGT;
Changed = true;
} else if (!getSignedRange(LHS).getSignedMax().isMaxSignedValue()) {
LHS = getAddExpr(getConstant(RHS->getType(), 1, true), LHS,
- /*HasNUW=*/false, /*HasNSW=*/true);
+ SCEV::FlagNSW);
Pred = ICmpInst::ICMP_SGT;
Changed = true;
}
case ICmpInst::ICMP_ULE:
if (!getUnsignedRange(RHS).getUnsignedMax().isMaxValue()) {
RHS = getAddExpr(getConstant(RHS->getType(), 1, true), RHS,
- /*HasNUW=*/true, /*HasNSW=*/false);
+ SCEV::FlagNUW);
Pred = ICmpInst::ICMP_ULT;
Changed = true;
} else if (!getUnsignedRange(LHS).getUnsignedMin().isMinValue()) {
LHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), LHS,
- /*HasNUW=*/true, /*HasNSW=*/false);
+ SCEV::FlagNUW);
Pred = ICmpInst::ICMP_ULT;
Changed = true;
}
case ICmpInst::ICMP_UGE:
if (!getUnsignedRange(RHS).getUnsignedMin().isMinValue()) {
RHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), RHS,
- /*HasNUW=*/true, /*HasNSW=*/false);
+ SCEV::FlagNUW);
Pred = ICmpInst::ICMP_UGT;
Changed = true;
} else if (!getUnsignedRange(LHS).getUnsignedMax().isMaxValue()) {
LHS = getAddExpr(getConstant(RHS->getType(), 1, true), LHS,
- /*HasNUW=*/true, /*HasNSW=*/false);
+ SCEV::FlagNUW);
Pred = ICmpInst::ICMP_UGT;
Changed = true;
}
"This code doesn't handle negative strides yet!");
const Type *Ty = Start->getType();
+
+ // When Start == End, we have an exact BECount == 0. Short-circuit this case
+ // here because SCEV may not be able to determine that the unsigned division
+ // after rounding is zero.
+ if (Start == End)
+ return getConstant(Ty, 0);
+
const SCEV *NegOne = getConstant(Ty, (uint64_t)-1);
const SCEV *Diff = getMinusSCEV(End, Start);
const SCEV *RoundUp = getAddExpr(Step, NegOne);
return getCouldNotCompute();
// Check to see if we have a flag which makes analysis easy.
- bool NoWrap = isSigned ? AddRec->hasNoSignedWrap() :
- AddRec->hasNoUnsignedWrap();
+ bool NoWrap = isSigned ? AddRec->getNoWrapFlags(SCEV::FlagNSW) :
+ AddRec->getNoWrapFlags(SCEV::FlagNUW);
if (AddRec->isAffine()) {
unsigned BitWidth = getTypeSizeInBits(AddRec->getType());
// The maximum backedge count is similar, except using the minimum start
// value and the maximum end value.
- const SCEV *MaxBECount = getBECount(MinStart, MaxEnd, Step, NoWrap);
+ // If we already have an exact constant BECount, use it instead.
+ const SCEV *MaxBECount = isa<SCEVConstant>(BECount) ? BECount
+ : getBECount(MinStart, MaxEnd, Step, NoWrap);
+
+ // If the stride is nonconstant, and NoWrap == true, then
+ // getBECount(MinStart, MaxEnd) may not compute. This would result in an
+ // exact BECount and invalid MaxBECount, which should be avoided to catch
+ // more optimization opportunities.
+ if (isa<SCEVCouldNotCompute>(MaxBECount))
+ MaxBECount = BECount;
return BackedgeTakenInfo(BECount, MaxBECount);
}
if (!SC->getValue()->isZero()) {
SmallVector<const SCEV *, 4> Operands(op_begin(), op_end());
Operands[0] = SE.getConstant(SC->getType(), 0);
- const SCEV *Shifted = SE.getAddRecExpr(Operands, getLoop());
+ const SCEV *Shifted = SE.getAddRecExpr(Operands, getLoop(),
+ getNoWrapFlags(FlagNW));
if (const SCEVAddRecExpr *ShiftedAddRec =
dyn_cast<SCEVAddRecExpr>(Shifted))
return ShiftedAddRec->getNumIterationsInRange(
// Range.getUpper() is crossed.
SmallVector<const SCEV *, 4> NewOps(op_begin(), op_end());
NewOps[0] = SE.getNegativeSCEV(SE.getConstant(Range.getUpper()));
- const SCEV *NewAddRec = SE.getAddRecExpr(NewOps, getLoop());
+ const SCEV *NewAddRec = SE.getAddRecExpr(NewOps, getLoop(),
+ // getNoWrapFlags(FlagNW)
+ FlagAnyWrap);
// Next, solve the constructed addrec
std::pair<const SCEV *,const SCEV *> Roots =
projects / oota-llvm.git / blobdiff