#include "llvm/Assembly/Writer.h"
#include "llvm/Target/TargetData.h"
#include "llvm/Support/CommandLine.h"
-#include "llvm/Support/Compiler.h"
#include "llvm/Support/ConstantRange.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/GetElementPtrTypeIterator.h"
return Op->dominates(BB, DT);
}
+bool SCEVCastExpr::properlyDominates(BasicBlock *BB, DominatorTree *DT) const {
+ return Op->properlyDominates(BB, DT);
+}
+
SCEVTruncateExpr::SCEVTruncateExpr(const FoldingSetNodeID &ID,
const SCEV *op, const Type *ty)
: SCEVCastExpr(ID, scTruncate, op, ty) {
return true;
}
+bool SCEVNAryExpr::properlyDominates(BasicBlock *BB, DominatorTree *DT) const {
+ for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
+ if (!getOperand(i)->properlyDominates(BB, DT))
+ return false;
+ }
+ return true;
+}
+
bool SCEVUDivExpr::dominates(BasicBlock *BB, DominatorTree *DT) const {
return LHS->dominates(BB, DT) && RHS->dominates(BB, DT);
}
+bool SCEVUDivExpr::properlyDominates(BasicBlock *BB, DominatorTree *DT) const {
+ return LHS->properlyDominates(BB, DT) && RHS->properlyDominates(BB, DT);
+}
+
void SCEVUDivExpr::print(raw_ostream &OS) const {
OS << "(" << *LHS << " /u " << *RHS << ")";
}
return false;
// This recurrence is variant w.r.t. QueryLoop if QueryLoop contains L.
- if (QueryLoop->contains(L->getHeader()))
+ if (QueryLoop->contains(L))
return false;
// This recurrence is variant w.r.t. QueryLoop if any of its operands
// Instructions are never considered invariant in the function body
// (null loop) because they are defined within the "loop".
if (Instruction *I = dyn_cast<Instruction>(V))
- return L && !L->contains(I->getParent());
+ return L && !L->contains(I);
return true;
}
return true;
}
+bool SCEVUnknown::properlyDominates(BasicBlock *BB, DominatorTree *DT) const {
+ if (Instruction *I = dyn_cast<Instruction>(getValue()))
+ return DT->properlyDominates(I->getParent(), BB);
+ return true;
+}
+
const Type *SCEVUnknown::getType() const {
return V->getType();
}
/// SCEVComplexityCompare - Return true if the complexity of the LHS is less
/// than the complexity of the RHS. This comparator is used to canonicalize
/// expressions.
- class VISIBILITY_HIDDEN SCEVComplexityCompare {
+ class SCEVComplexityCompare {
LoopInfo *LI;
public:
explicit SCEVComplexityCompare(LoopInfo *li) : LI(li) {}
/// getAddExpr - Get a canonical add expression, or something simpler if
/// possible.
-const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl<const SCEV *> &Ops) {
+const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl<const SCEV *> &Ops,
+ bool HasNUW, bool HasNSW) {
assert(!Ops.empty() && "Cannot get empty add!");
if (Ops.size() == 1) return Ops[0];
#ifndef NDEBUG
return Mul;
Ops.erase(Ops.begin()+i, Ops.begin()+i+2);
Ops.push_back(Mul);
- return getAddExpr(Ops);
+ return getAddExpr(Ops, HasNUW, HasNSW);
}
// Check for truncates. If all the operands are truncated from the same
}
if (Ok) {
// Evaluate the expression in the larger type.
- const SCEV *Fold = getAddExpr(LargeOps);
+ const SCEV *Fold = getAddExpr(LargeOps, HasNUW, HasNSW);
// If it folds to something simple, use it. Otherwise, don't.
if (isa<SCEVConstant>(Fold) || isa<SCEVUnknown>(Fold))
return getTruncateExpr(Fold, DstType);
LIOps.push_back(AddRec->getStart());
SmallVector<const SCEV *, 4> AddRecOps(AddRec->op_begin(),
- AddRec->op_end());
+ AddRec->op_end());
AddRecOps[0] = getAddExpr(LIOps);
+ // It's tempting to propagate NUW/NSW flags here, but nuw/nsw addition
+ // is not associative so this isn't necessarily safe.
const SCEV *NewRec = getAddRecExpr(AddRecOps, AddRec->getLoop());
+
// If all of the other operands were loop invariant, we are done.
if (Ops.size() == 1) return NewRec;
ID.AddPointer(Ops[i]);
void *IP = 0;
if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
- SCEV *S = SCEVAllocator.Allocate<SCEVAddExpr>();
+ SCEVAddExpr *S = SCEVAllocator.Allocate<SCEVAddExpr>();
new (S) SCEVAddExpr(ID, Ops);
UniqueSCEVs.InsertNode(S, IP);
+ if (HasNUW) S->setHasNoUnsignedWrap(true);
+ if (HasNSW) S->setHasNoSignedWrap(true);
return S;
}
/// getMulExpr - Get a canonical multiply expression, or something simpler if
/// possible.
-const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV *> &Ops) {
+const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV *> &Ops,
+ bool HasNUW, bool HasNSW) {
assert(!Ops.empty() && "Cannot get empty mul!");
#ifndef NDEBUG
for (unsigned i = 1, e = Ops.size(); i != e; ++i)
}
}
+ // It's tempting to propagate the NSW flag here, but nsw multiplication
+ // is not associative so this isn't necessarily safe.
const SCEV *NewRec = getAddRecExpr(NewOps, AddRec->getLoop());
// If all of the other operands were loop invariant, we are done.
ID.AddPointer(Ops[i]);
void *IP = 0;
if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
- SCEV *S = SCEVAllocator.Allocate<SCEVMulExpr>();
+ SCEVMulExpr *S = SCEVAllocator.Allocate<SCEVMulExpr>();
new (S) SCEVMulExpr(ID, Ops);
UniqueSCEVs.InsertNode(S, IP);
+ if (HasNUW) S->setHasNoUnsignedWrap(true);
+ if (HasNSW) S->setHasNoSignedWrap(true);
return S;
}
/// 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) {
+ const SCEV *Step, const Loop *L,
+ bool HasNUW, bool HasNSW) {
SmallVector<const SCEV *, 4> Operands;
Operands.push_back(Start);
if (const SCEVAddRecExpr *StepChrec = dyn_cast<SCEVAddRecExpr>(Step))
}
Operands.push_back(Step);
- return getAddRecExpr(Operands, L);
+ return getAddRecExpr(Operands, L, HasNUW, HasNSW);
}
/// 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) {
+ const Loop *L,
+ bool HasNUW, bool HasNSW) {
if (Operands.size() == 1) return Operands[0];
#ifndef NDEBUG
for (unsigned i = 1, e = Operands.size(); i != e; ++i)
if (Operands.back()->isZero()) {
Operands.pop_back();
- return getAddRecExpr(Operands, L); // {X,+,0} --> X
+ return getAddRecExpr(Operands, L, HasNUW, HasNSW); // {X,+,0} --> X
}
// Canonicalize nested AddRecs in by nesting them in order of loop depth.
if (const SCEVAddRecExpr *NestedAR = dyn_cast<SCEVAddRecExpr>(Operands[0])) {
- const Loop* NestedLoop = NestedAR->getLoop();
+ const Loop *NestedLoop = NestedAR->getLoop();
if (L->getLoopDepth() < NestedLoop->getLoopDepth()) {
SmallVector<const SCEV *, 4> NestedOperands(NestedAR->op_begin(),
- NestedAR->op_end());
+ NestedAR->op_end());
Operands[0] = NestedAR->getStart();
// AddRecs require their operands be loop-invariant with respect to their
// loops. Don't perform this transformation if it would break this
}
if (AllInvariant)
// Ok, both add recurrences are valid after the transformation.
- return getAddRecExpr(NestedOperands, NestedLoop);
+ return getAddRecExpr(NestedOperands, NestedLoop, HasNUW, HasNSW);
}
// Reset Operands to its original state.
Operands[0] = NestedAR;
ID.AddPointer(L);
void *IP = 0;
if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
- SCEV *S = SCEVAllocator.Allocate<SCEVAddRecExpr>();
+ SCEVAddRecExpr *S = SCEVAllocator.Allocate<SCEVAddRecExpr>();
new (S) SCEVAddRecExpr(ID, Operands, L);
UniqueSCEVs.InsertNode(S, IP);
+ if (HasNUW) S->setHasNoUnsignedWrap(true);
+ if (HasNSW) S->setHasNoSignedWrap(true);
return S;
}
Instruction *I = Worklist.pop_back_val();
if (!Visited.insert(I)) continue;
- std::map<SCEVCallbackVH, const SCEV*>::iterator It =
+ std::map<SCEVCallbackVH, const SCEV *>::iterator It =
Scalars.find(static_cast<Value *>(I));
if (It != Scalars.end()) {
// Short-circuit the def-use traversal if the symbolic name
/// createNodeForGEP - Expand GEP instructions into add and multiply
/// operations. This allows them to be analyzed by regular SCEV code.
///
-const SCEV *ScalarEvolution::createNodeForGEP(Operator *GEP) {
+const SCEV *ScalarEvolution::createNodeForGEP(GEPOperator *GEP) {
+ bool InBounds = GEP->isInBounds();
const Type *IntPtrTy = getEffectiveSCEVType(GEP->getType());
Value *Base = GEP->getOperand(0);
// Don't attempt to analyze GEPs over unsized objects.
// For a struct, add the member offset.
unsigned FieldNo = cast<ConstantInt>(Index)->getZExtValue();
TotalOffset = getAddExpr(TotalOffset,
- getFieldOffsetExpr(STy, FieldNo));
+ getFieldOffsetExpr(STy, FieldNo),
+ /*HasNUW=*/false, /*HasNSW=*/InBounds);
} else {
// For an array, add the element offset, explicitly scaled.
const SCEV *LocalOffset = getSCEV(Index);
if (!isa<PointerType>(LocalOffset->getType()))
// Getelementptr indicies are signed.
LocalOffset = getTruncateOrSignExtend(LocalOffset, IntPtrTy);
- LocalOffset = getMulExpr(LocalOffset, getAllocSizeExpr(*GTI));
- TotalOffset = getAddExpr(TotalOffset, LocalOffset);
+ // Lower "inbounds" GEPs to NSW arithmetic.
+ LocalOffset = getMulExpr(LocalOffset, getAllocSizeExpr(*GTI),
+ /*HasNUW=*/false, /*HasNSW=*/InBounds);
+ TotalOffset = getAddExpr(TotalOffset, LocalOffset,
+ /*HasNUW=*/false, /*HasNSW=*/InBounds);
}
}
- return getAddExpr(getSCEV(Base), TotalOffset);
+ return getAddExpr(getSCEV(Base), TotalOffset,
+ /*HasNUW=*/false, /*HasNSW=*/InBounds);
}
/// GetMinTrailingZeros - Determine the minimum number of zero bits that S is
Operator *U = cast<Operator>(V);
switch (Opcode) {
case Instruction::Add:
+ // Don't transfer the NSW and NUW bits from the Add instruction to 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.
return getAddExpr(getSCEV(U->getOperand(0)),
getSCEV(U->getOperand(1)));
case Instruction::Mul:
+ // Don't transfer the NSW and NUW bits from the Mul instruction to the
+ // Mul expression, as with Add.
return getMulExpr(getSCEV(U->getOperand(0)),
getSCEV(U->getOperand(1)));
case Instruction::UDiv:
const SCEV *LHS = getSCEV(U->getOperand(0));
const APInt &CIVal = CI->getValue();
if (GetMinTrailingZeros(LHS) >=
- (CIVal.getBitWidth() - CIVal.countLeadingZeros()))
- return getAddExpr(LHS, getSCEV(U->getOperand(1)));
+ (CIVal.getBitWidth() - CIVal.countLeadingZeros())) {
+ // Build a plain add SCEV.
+ const SCEV *S = getAddExpr(LHS, getSCEV(CI));
+ // If the LHS of the add was an addrec and it has no-wrap flags,
+ // 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);
+ }
+ return S;
+ }
}
break;
case Instruction::Xor:
// expressions we handle are GEPs and address literals.
case Instruction::GetElementPtr:
- return createNodeForGEP(U);
+ return createNodeForGEP(cast<GEPOperator>(U));
case Instruction::PHI:
return createNodeForPHI(cast<PHINode>(U));
// update the value. The temporary CouldNotCompute value tells SCEV
// code elsewhere that it shouldn't attempt to request a new
// backedge-taken count, which could result in infinite recursion.
- std::pair<std::map<const Loop*, BackedgeTakenInfo>::iterator, bool> Pair =
+ std::pair<std::map<const Loop *, BackedgeTakenInfo>::iterator, bool> Pair =
BackedgeTakenCounts.insert(std::make_pair(L, getCouldNotCompute()));
if (Pair.second) {
BackedgeTakenInfo ItCount = ComputeBackedgeTakenCount(L);
// Now that we know more about the trip count for this loop, forget any
// existing SCEV values for PHI nodes in this loop since they are only
// conservative estimates made without the benefit of trip count
- // information. This is similar to the code in
- // forgetLoopBackedgeTakenCount, except that it handles SCEVUnknown PHI
- // nodes specially.
+ // information. This is similar to the code in forgetLoop, except that
+ // it handles SCEVUnknown PHI nodes specially.
if (ItCount.hasAnyInfo()) {
SmallVector<Instruction *, 16> Worklist;
PushLoopPHIs(L, Worklist);
Instruction *I = Worklist.pop_back_val();
if (!Visited.insert(I)) continue;
- std::map<SCEVCallbackVH, const SCEV*>::iterator It =
+ std::map<SCEVCallbackVH, const SCEV *>::iterator It =
Scalars.find(static_cast<Value *>(I));
if (It != Scalars.end()) {
// SCEVUnknown for a PHI either means that it has an unrecognized
return Pair.first->second;
}
-/// forgetLoopBackedgeTakenCount - This method should be called by the
-/// client when it has changed a loop in a way that may effect
-/// ScalarEvolution's ability to compute a trip count, or if the loop
-/// is deleted.
-void ScalarEvolution::forgetLoopBackedgeTakenCount(const Loop *L) {
+/// forgetLoop - This method should be called by the client when it has
+/// changed a loop in a way that may effect ScalarEvolution's ability to
+/// compute a trip count, or if the loop is deleted.
+void ScalarEvolution::forgetLoop(const Loop *L) {
+ // Drop any stored trip count value.
BackedgeTakenCounts.erase(L);
+ // Drop information about expressions based on loop-header PHIs.
SmallVector<Instruction *, 16> Worklist;
PushLoopPHIs(L, Worklist);
Instruction *I = Worklist.pop_back_val();
if (!Visited.insert(I)) continue;
- std::map<SCEVCallbackVH, const SCEV*>::iterator It =
+ std::map<SCEVCallbackVH, const SCEV *>::iterator It =
Scalars.find(static_cast<Value *>(I));
if (It != Scalars.end()) {
ValuesAtScopes.erase(It->second);
/// of the specified loop will execute.
ScalarEvolution::BackedgeTakenInfo
ScalarEvolution::ComputeBackedgeTakenCount(const Loop *L) {
- SmallVector<BasicBlock*, 8> ExitingBlocks;
+ SmallVector<BasicBlock *, 8> ExitingBlocks;
L->getExitingBlocks(ExitingBlocks);
// Examine all exits and pick the most conservative values.
/// the addressed element of the initializer or null if the index expression is
/// invalid.
static Constant *
-GetAddressedElementFromGlobal(LLVMContext &Context, GlobalVariable *GV,
+GetAddressedElementFromGlobal(GlobalVariable *GV,
const std::vector<ConstantInt*> &Indices) {
Constant *Init = GV->getInitializer();
for (unsigned i = 0, e = Indices.size(); i != e; ++i) {
// Form the GEP offset.
Indexes[VarIdxNum] = Val;
- Constant *Result = GetAddressedElementFromGlobal(getContext(), GV, Indexes);
+ Constant *Result = GetAddressedElementFromGlobal(GV, Indexes);
if (Result == 0) break; // Cannot compute!
// Evaluate the condition for this iteration.
// If this is not an instruction, or if this is an instruction outside of the
// loop, it can't be derived from a loop PHI.
Instruction *I = dyn_cast<Instruction>(V);
- if (I == 0 || !L->contains(I->getParent())) return 0;
+ if (I == 0 || !L->contains(I)) return 0;
if (PHINode *PN = dyn_cast<PHINode>(I)) {
if (L->getHeader() == I->getParent())
/// getConstantEvolvingPHI predicate, evaluate its value assuming the PHI node
/// in the loop has the value PHIVal. If we can't fold this expression for some
/// reason, return null.
-static Constant *EvaluateExpression(Value *V, Constant *PHIVal) {
+static Constant *EvaluateExpression(Value *V, Constant *PHIVal,
+ const TargetData *TD) {
if (isa<PHINode>(V)) return PHIVal;
if (Constant *C = dyn_cast<Constant>(V)) return C;
if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) return GV;
Instruction *I = cast<Instruction>(V);
- LLVMContext &Context = I->getParent()->getContext();
std::vector<Constant*> Operands;
Operands.resize(I->getNumOperands());
for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
- Operands[i] = EvaluateExpression(I->getOperand(i), PHIVal);
+ Operands[i] = EvaluateExpression(I->getOperand(i), PHIVal, TD);
if (Operands[i] == 0) return 0;
}
if (const CmpInst *CI = dyn_cast<CmpInst>(I))
- return ConstantFoldCompareInstOperands(CI->getPredicate(),
- &Operands[0], Operands.size(),
- Context);
- else
- return ConstantFoldInstOperands(I->getOpcode(), I->getType(),
- &Operands[0], Operands.size(),
- Context);
+ return ConstantFoldCompareInstOperands(CI->getPredicate(), Operands[0],
+ Operands[1], TD);
+ return ConstantFoldInstOperands(I->getOpcode(), I->getType(),
+ &Operands[0], Operands.size(), TD);
}
/// getConstantEvolutionLoopExitValue - If we know that the specified Phi is
/// involving constants, fold it.
Constant *
ScalarEvolution::getConstantEvolutionLoopExitValue(PHINode *PN,
- const APInt& BEs,
+ const APInt &BEs,
const Loop *L) {
std::map<PHINode*, Constant*>::iterator I =
ConstantEvolutionLoopExitValue.find(PN);
return RetVal = PHIVal; // Got exit value!
// Compute the value of the PHI node for the next iteration.
- Constant *NextPHI = EvaluateExpression(BEValue, PHIVal);
+ Constant *NextPHI = EvaluateExpression(BEValue, PHIVal, TD);
if (NextPHI == PHIVal)
return RetVal = NextPHI; // Stopped evolving!
if (NextPHI == 0)
for (Constant *PHIVal = StartCST;
IterationNum != MaxIterations; ++IterationNum) {
ConstantInt *CondVal =
- dyn_cast_or_null<ConstantInt>(EvaluateExpression(Cond, PHIVal));
+ dyn_cast_or_null<ConstantInt>(EvaluateExpression(Cond, PHIVal, TD));
// Couldn't symbolically evaluate.
if (!CondVal) return getCouldNotCompute();
}
// Compute the value of the PHI node for the next iteration.
- Constant *NextPHI = EvaluateExpression(BEValue, PHIVal);
+ Constant *NextPHI = EvaluateExpression(BEValue, PHIVal, TD);
if (NextPHI == 0 || NextPHI == PHIVal)
return getCouldNotCompute();// Couldn't evaluate or not making progress...
PHIVal = NextPHI;
return getCouldNotCompute();
}
-/// getSCEVAtScope - Return a SCEV expression handle for the specified value
+/// getSCEVAtScope - Return a SCEV expression for the specified value
/// at the specified scope in the program. The L value specifies a loop
/// nest to evaluate the expression at, where null is the top-level or a
/// specified loop is immediately inside of the loop.
if (!isSCEVable(Op->getType()))
return V;
- const SCEV* OpV = getSCEVAtScope(Op, L);
+ const SCEV *OpV = getSCEVAtScope(Op, L);
if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(OpV)) {
Constant *C = SC->getValue();
if (C->getType() != Op->getType())
Constant *C;
if (const CmpInst *CI = dyn_cast<CmpInst>(I))
C = ConstantFoldCompareInstOperands(CI->getPredicate(),
- &Operands[0], Operands.size(),
- getContext());
+ Operands[0], Operands[1], TD);
else
C = ConstantFoldInstOperands(I->getOpcode(), I->getType(),
- &Operands[0], Operands.size(),
- getContext());
+ &Operands[0], Operands.size(), TD);
return getSCEV(C);
}
}
// If this is a loop recurrence for a loop that does not contain L, then we
// are dealing with the final value computed by the loop.
if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V)) {
- if (!L || !AddRec->getLoop()->contains(L->getHeader())) {
+ if (!L || !AddRec->getLoop()->contains(L)) {
// To evaluate this recurrence, we need to know how many times the AddRec
// loop iterates. Compute this now.
const SCEV *BackedgeTakenCount = getBackedgeTakenCount(AddRec->getLoop());
/// CouldNotCompute if an intermediate computation overflows.
const SCEV *ScalarEvolution::getBECount(const SCEV *Start,
const SCEV *End,
- const SCEV *Step) {
+ const SCEV *Step,
+ bool NoWrap) {
const Type *Ty = Start->getType();
const SCEV *NegOne = getIntegerSCEV(-1, Ty);
const SCEV *Diff = getMinusSCEV(End, Start);
// the division will effectively round up.
const SCEV *Add = getAddExpr(Diff, RoundUp);
- // Check Add for unsigned overflow.
- // TODO: More sophisticated things could be done here.
- const Type *WideTy = IntegerType::get(getContext(),
- getTypeSizeInBits(Ty) + 1);
- const SCEV *EDiff = getZeroExtendExpr(Diff, WideTy);
- const SCEV *ERoundUp = getZeroExtendExpr(RoundUp, WideTy);
- const SCEV *OperandExtendedAdd = getAddExpr(EDiff, ERoundUp);
- if (getZeroExtendExpr(Add, WideTy) != OperandExtendedAdd)
- return getCouldNotCompute();
+ if (!NoWrap) {
+ // Check Add for unsigned overflow.
+ // TODO: More sophisticated things could be done here.
+ const Type *WideTy = IntegerType::get(getContext(),
+ getTypeSizeInBits(Ty) + 1);
+ const SCEV *EDiff = getZeroExtendExpr(Diff, WideTy);
+ const SCEV *ERoundUp = getZeroExtendExpr(RoundUp, WideTy);
+ const SCEV *OperandExtendedAdd = getAddExpr(EDiff, ERoundUp);
+ if (getZeroExtendExpr(Add, WideTy) != OperandExtendedAdd)
+ return getCouldNotCompute();
+ }
return getUDivExpr(Add, Step);
}
if (!AddRec || AddRec->getLoop() != L)
return getCouldNotCompute();
+ // Check to see if we have a flag which makes analysis easy.
+ bool NoWrap = isSigned ? AddRec->hasNoSignedWrap() :
+ AddRec->hasNoUnsignedWrap();
+
if (AddRec->isAffine()) {
// FORNOW: We only support unit strides.
unsigned BitWidth = getTypeSizeInBits(AddRec->getType());
if (CStep->isOne()) {
// With unit stride, the iteration never steps past the limit value.
} else if (CStep->getValue()->getValue().isStrictlyPositive()) {
- if (const SCEVConstant *CLimit = dyn_cast<SCEVConstant>(RHS)) {
+ if (NoWrap) {
+ // We know the iteration won't step past the maximum value for its type.
+ ;
+ } else if (const SCEVConstant *CLimit = dyn_cast<SCEVConstant>(RHS)) {
// Test whether a positive iteration iteration can step past the limit
// value and past the maximum value for its type in a single step.
if (isSigned) {
// Finally, we subtract these two values and divide, rounding up, to get
// the number of times the backedge is executed.
- const SCEV *BECount = getBECount(Start, End, Step);
+ const SCEV *BECount = getBECount(Start, End, Step, NoWrap);
// The maximum backedge count is similar, except using the minimum start
// value and the maximum end value.
- const SCEV *MaxBECount = getBECount(MinStart, MaxEnd, Step);
+ const SCEV *MaxBECount = getBECount(MinStart, MaxEnd, Step, NoWrap);
return BackedgeTakenInfo(BECount, MaxBECount);
}
OS << "Loop " << L->getHeader()->getName() << ": ";
- SmallVector<BasicBlock*, 8> ExitBlocks;
+ SmallVector<BasicBlock *, 8> ExitBlocks;
L->getExitBlocks(ExitBlocks);
if (ExitBlocks.size() != 1)
OS << "<multiple exits> ";
OS << "\n";
}
-void ScalarEvolution::print(raw_ostream &OS, const Module* ) const {
+void ScalarEvolution::print(raw_ostream &OS, const Module *) const {
// ScalarEvolution's implementaiton of the print method is to print
// out SCEV values of all instructions that are interesting. Doing
// this potentially causes it to create new SCEV objects though,
// which technically conflicts with the const qualifier. This isn't
// observable from outside the class though, so casting away the
// const isn't dangerous.
- ScalarEvolution &SE = *const_cast<ScalarEvolution*>(this);
+ ScalarEvolution &SE = *const_cast<ScalarEvolution *>(this);
OS << "Classifying expressions for: " << F->getName() << "\n";
for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)
projects / oota-llvm.git / blobdiff