X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FScalarEvolution.cpp;h=cc483b8d13775e841040e4f552da97f301aa54f5;hb=257cbf7a8dca9372882a7a98ec626897247aee6d;hp=f0848569ddbe36c30762c8b8381eb6b7160dfe8e;hpb=1f239300d341c0d5d94516f8d0c41cdd31fae54b;p=oota-llvm.git diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp index f0848569ddb..cc483b8d137 100644 --- a/lib/Analysis/ScalarEvolution.cpp +++ b/lib/Analysis/ScalarEvolution.cpp @@ -59,6 +59,7 @@ // //===----------------------------------------------------------------------===// +#define DEBUG_TYPE "scalar-evolution" #include "llvm/Analysis/ScalarEvolutionExpressions.h" #include "llvm/Constants.h" #include "llvm/DerivedTypes.h" @@ -69,41 +70,40 @@ #include "llvm/Assembly/Writer.h" #include "llvm/Transforms/Scalar.h" #include "llvm/Support/CFG.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Compiler.h" #include "llvm/Support/ConstantRange.h" #include "llvm/Support/InstIterator.h" -#include "llvm/Support/CommandLine.h" +#include "llvm/Support/ManagedStatic.h" +#include "llvm/Support/MathExtras.h" +#include "llvm/Support/Streams.h" #include "llvm/ADT/Statistic.h" -#include -#include +#include #include +#include using namespace llvm; +STATISTIC(NumBruteForceEvaluations, + "Number of brute force evaluations needed to " + "calculate high-order polynomial exit values"); +STATISTIC(NumArrayLenItCounts, + "Number of trip counts computed with array length"); +STATISTIC(NumTripCountsComputed, + "Number of loops with predictable loop counts"); +STATISTIC(NumTripCountsNotComputed, + "Number of loops without predictable loop counts"); +STATISTIC(NumBruteForceTripCountsComputed, + "Number of loops with trip counts computed by force"); + +cl::opt +MaxBruteForceIterations("scalar-evolution-max-iterations", cl::ReallyHidden, + cl::desc("Maximum number of iterations SCEV will " + "symbolically execute a constant derived loop"), + cl::init(100)); + namespace { - RegisterAnalysis + RegisterPass R("scalar-evolution", "Scalar Evolution Analysis"); - - Statistic<> - NumBruteForceEvaluations("scalar-evolution", - "Number of brute force evaluations needed to " - "calculate high-order polynomial exit values"); - Statistic<> - NumArrayLenItCounts("scalar-evolution", - "Number of trip counts computed with array length"); - Statistic<> - NumTripCountsComputed("scalar-evolution", - "Number of loops with predictable loop counts"); - Statistic<> - NumTripCountsNotComputed("scalar-evolution", - "Number of loops without predictable loop counts"); - Statistic<> - NumBruteForceTripCountsComputed("scalar-evolution", - "Number of loops with trip counts computed by force"); - - cl::opt - MaxBruteForceIterations("scalar-evolution-max-iterations", cl::ReallyHidden, - cl::desc("Maximum number of iterations SCEV will " - "symbolically execute a constant derived loop"), - cl::init(100)); } //===----------------------------------------------------------------------===// @@ -115,7 +115,7 @@ namespace { // SCEV::~SCEV() {} void SCEV::dump() const { - print(std::cerr); + print(cerr); } /// getValueRange - Return the tightest constant bounds that this value is @@ -123,7 +123,6 @@ void SCEV::dump() const { ConstantRange SCEV::getValueRange() const { const Type *Ty = getType(); assert(Ty->isInteger() && "Can't get range for a non-integer SCEV!"); - Ty = Ty->getUnsignedVersion(); // Default to a full range if no better information is available. return ConstantRange(getType()); } @@ -164,21 +163,15 @@ bool SCEVCouldNotCompute::classof(const SCEV *S) { // SCEVConstants - Only allow the creation of one SCEVConstant for any // particular value. Don't use a SCEVHandle here, or else the object will // never be deleted! -static std::map SCEVConstants; +static ManagedStatic > SCEVConstants; SCEVConstant::~SCEVConstant() { - SCEVConstants.erase(V); + SCEVConstants->erase(V); } SCEVHandle SCEVConstant::get(ConstantInt *V) { - // Make sure that SCEVConstant instances are all unsigned. - if (V->getType()->isSigned()) { - const Type *NewTy = V->getType()->getUnsignedVersion(); - V = cast(ConstantExpr::getCast(V, NewTy)); - } - - SCEVConstant *&R = SCEVConstants[V]; + SCEVConstant *&R = (*SCEVConstants)[V]; if (R == 0) R = new SCEVConstant(V); return R; } @@ -196,19 +189,19 @@ void SCEVConstant::print(std::ostream &OS) const { // SCEVTruncates - Only allow the creation of one SCEVTruncateExpr for any // particular input. Don't use a SCEVHandle here, or else the object will // never be deleted! -static std::map, SCEVTruncateExpr*> SCEVTruncates; +static ManagedStatic, + SCEVTruncateExpr*> > SCEVTruncates; SCEVTruncateExpr::SCEVTruncateExpr(const SCEVHandle &op, const Type *ty) : SCEV(scTruncate), Op(op), Ty(ty) { assert(Op->getType()->isInteger() && Ty->isInteger() && - Ty->isUnsigned() && "Cannot truncate non-integer value!"); assert(Op->getType()->getPrimitiveSize() > Ty->getPrimitiveSize() && "This is not a truncating conversion!"); } SCEVTruncateExpr::~SCEVTruncateExpr() { - SCEVTruncates.erase(std::make_pair(Op, Ty)); + SCEVTruncates->erase(std::make_pair(Op, Ty)); } ConstantRange SCEVTruncateExpr::getValueRange() const { @@ -222,20 +215,19 @@ void SCEVTruncateExpr::print(std::ostream &OS) const { // SCEVZeroExtends - Only allow the creation of one SCEVZeroExtendExpr for any // particular input. Don't use a SCEVHandle here, or else the object will never // be deleted! -static std::map, - SCEVZeroExtendExpr*> SCEVZeroExtends; +static ManagedStatic, + SCEVZeroExtendExpr*> > SCEVZeroExtends; SCEVZeroExtendExpr::SCEVZeroExtendExpr(const SCEVHandle &op, const Type *ty) - : SCEV(scTruncate), Op(op), Ty(ty) { + : SCEV(scZeroExtend), Op(op), Ty(ty) { assert(Op->getType()->isInteger() && Ty->isInteger() && - Ty->isUnsigned() && "Cannot zero extend non-integer value!"); assert(Op->getType()->getPrimitiveSize() < Ty->getPrimitiveSize() && "This is not an extending conversion!"); } SCEVZeroExtendExpr::~SCEVZeroExtendExpr() { - SCEVZeroExtends.erase(std::make_pair(Op, Ty)); + SCEVZeroExtends->erase(std::make_pair(Op, Ty)); } ConstantRange SCEVZeroExtendExpr::getValueRange() const { @@ -249,13 +241,13 @@ void SCEVZeroExtendExpr::print(std::ostream &OS) const { // SCEVCommExprs - Only allow the creation of one SCEVCommutativeExpr for any // particular input. Don't use a SCEVHandle here, or else the object will never // be deleted! -static std::map >, - SCEVCommutativeExpr*> SCEVCommExprs; +static ManagedStatic >, + SCEVCommutativeExpr*> > SCEVCommExprs; SCEVCommutativeExpr::~SCEVCommutativeExpr() { - SCEVCommExprs.erase(std::make_pair(getSCEVType(), - std::vector(Operands.begin(), - Operands.end()))); + SCEVCommExprs->erase(std::make_pair(getSCEVType(), + std::vector(Operands.begin(), + Operands.end()))); } void SCEVCommutativeExpr::print(std::ostream &OS) const { @@ -297,10 +289,11 @@ replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, // SCEVSDivs - Only allow the creation of one SCEVSDivExpr for any particular // input. Don't use a SCEVHandle here, or else the object will never be // deleted! -static std::map, SCEVSDivExpr*> SCEVSDivs; +static ManagedStatic, + SCEVSDivExpr*> > SCEVSDivs; SCEVSDivExpr::~SCEVSDivExpr() { - SCEVSDivs.erase(std::make_pair(LHS, RHS)); + SCEVSDivs->erase(std::make_pair(LHS, RHS)); } void SCEVSDivExpr::print(std::ostream &OS) const { @@ -308,21 +301,19 @@ void SCEVSDivExpr::print(std::ostream &OS) const { } const Type *SCEVSDivExpr::getType() const { - const Type *Ty = LHS->getType(); - if (Ty->isUnsigned()) Ty = Ty->getSignedVersion(); - return Ty; + return LHS->getType(); } // SCEVAddRecExprs - Only allow the creation of one SCEVAddRecExpr for any // particular input. Don't use a SCEVHandle here, or else the object will never // be deleted! -static std::map >, - SCEVAddRecExpr*> SCEVAddRecExprs; +static ManagedStatic >, + SCEVAddRecExpr*> > SCEVAddRecExprs; SCEVAddRecExpr::~SCEVAddRecExpr() { - SCEVAddRecExprs.erase(std::make_pair(L, - std::vector(Operands.begin(), - Operands.end()))); + SCEVAddRecExprs->erase(std::make_pair(L, + std::vector(Operands.begin(), + Operands.end()))); } SCEVHandle SCEVAddRecExpr:: @@ -365,9 +356,9 @@ void SCEVAddRecExpr::print(std::ostream &OS) const { // SCEVUnknowns - Only allow the creation of one SCEVUnknown for any particular // value. Don't use a SCEVHandle here, or else the object will never be // deleted! -static std::map SCEVUnknowns; +static ManagedStatic > SCEVUnknowns; -SCEVUnknown::~SCEVUnknown() { SCEVUnknowns.erase(V); } +SCEVUnknown::~SCEVUnknown() { SCEVUnknowns->erase(V); } bool SCEVUnknown::isLoopInvariant(const Loop *L) const { // All non-instruction values are loop invariant. All instructions are loop @@ -393,7 +384,7 @@ namespace { /// SCEVComplexityCompare - Return true if the complexity of the LHS is less /// than the complexity of the RHS. This comparator is used to canonicalize /// expressions. - struct SCEVComplexityCompare { + struct VISIBILITY_HIDDEN SCEVComplexityCompare { bool operator()(SCEV *LHS, SCEV *RHS) { return LHS->getSCEVType() < RHS->getSCEVType(); } @@ -458,12 +449,8 @@ SCEVHandle SCEVUnknown::getIntegerSCEV(int Val, const Type *Ty) { C = Constant::getNullValue(Ty); else if (Ty->isFloatingPoint()) C = ConstantFP::get(Ty, Val); - else if (Ty->isSigned()) - C = ConstantSInt::get(Ty, Val); - else { - C = ConstantSInt::get(Ty->getSignedVersion(), Val); - C = ConstantExpr::getCast(C, Ty); - } + else + C = ConstantInt::get(Ty, Val); return SCEVUnknown::get(C); } @@ -503,12 +490,12 @@ static SCEVHandle PartialFact(SCEVHandle V, unsigned NumSteps) { // Handle this case efficiently, it is common to have constant iteration // counts while computing loop exit values. if (SCEVConstant *SC = dyn_cast(V)) { - uint64_t Val = SC->getValue()->getRawValue(); + uint64_t Val = SC->getValue()->getZExtValue(); uint64_t Result = 1; for (; NumSteps; --NumSteps) Result *= Val-(NumSteps-1); - Constant *Res = ConstantUInt::get(Type::ULongTy, Result); - return SCEVUnknown::get(ConstantExpr::getCast(Res, V->getType())); + Constant *Res = ConstantInt::get(Type::Int64Ty, Result); + return SCEVUnknown::get(ConstantExpr::getTruncOrBitCast(Res, V->getType())); } const Type *Ty = V->getType(); @@ -554,7 +541,8 @@ SCEVHandle SCEVAddRecExpr::evaluateAtIteration(SCEVHandle It) const { SCEVHandle SCEVTruncateExpr::get(const SCEVHandle &Op, const Type *Ty) { if (SCEVConstant *SC = dyn_cast(Op)) - return SCEVUnknown::get(ConstantExpr::getCast(SC->getValue(), Ty)); + return SCEVUnknown::get( + ConstantExpr::getTrunc(SC->getValue(), Ty)); // If the input value is a chrec scev made out of constants, truncate // all of the constants. @@ -570,21 +558,22 @@ SCEVHandle SCEVTruncateExpr::get(const SCEVHandle &Op, const Type *Ty) { return SCEVAddRecExpr::get(Operands, AddRec->getLoop()); } - SCEVTruncateExpr *&Result = SCEVTruncates[std::make_pair(Op, Ty)]; + SCEVTruncateExpr *&Result = (*SCEVTruncates)[std::make_pair(Op, Ty)]; if (Result == 0) Result = new SCEVTruncateExpr(Op, Ty); return Result; } SCEVHandle SCEVZeroExtendExpr::get(const SCEVHandle &Op, const Type *Ty) { if (SCEVConstant *SC = dyn_cast(Op)) - return SCEVUnknown::get(ConstantExpr::getCast(SC->getValue(), Ty)); + return SCEVUnknown::get( + ConstantExpr::getZExt(SC->getValue(), Ty)); // FIXME: If the input value is a chrec scev, and we can prove that the value // did not overflow the old, smaller, value, we can zero extend all of the // operands (often constants). This would allow analysis of something like // this: for (unsigned char X = 0; X < 100; ++X) { int Y = X; } - SCEVZeroExtendExpr *&Result = SCEVZeroExtends[std::make_pair(Op, Ty)]; + SCEVZeroExtendExpr *&Result = (*SCEVZeroExtends)[std::make_pair(Op, Ty)]; if (Result == 0) Result = new SCEVZeroExtendExpr(Op, Ty); return Result; } @@ -812,8 +801,8 @@ SCEVHandle SCEVAddExpr::get(std::vector &Ops) { // Okay, it looks like we really DO need an add expr. Check to see if we // already have one, otherwise create a new one. std::vector SCEVOps(Ops.begin(), Ops.end()); - SCEVCommutativeExpr *&Result = SCEVCommExprs[std::make_pair(scAddExpr, - SCEVOps)]; + SCEVCommutativeExpr *&Result = (*SCEVCommExprs)[std::make_pair(scAddExpr, + SCEVOps)]; if (Result == 0) Result = new SCEVAddExpr(Ops); return Result; } @@ -975,8 +964,8 @@ SCEVHandle SCEVMulExpr::get(std::vector &Ops) { // Okay, it looks like we really DO need an mul expr. Check to see if we // already have one, otherwise create a new one. std::vector SCEVOps(Ops.begin(), Ops.end()); - SCEVCommutativeExpr *&Result = SCEVCommExprs[std::make_pair(scMulExpr, - SCEVOps)]; + SCEVCommutativeExpr *&Result = (*SCEVCommExprs)[std::make_pair(scMulExpr, + SCEVOps)]; if (Result == 0) Result = new SCEVMulExpr(Ops); return Result; @@ -985,25 +974,20 @@ SCEVHandle SCEVMulExpr::get(std::vector &Ops) { SCEVHandle SCEVSDivExpr::get(const SCEVHandle &LHS, const SCEVHandle &RHS) { if (SCEVConstant *RHSC = dyn_cast(RHS)) { if (RHSC->getValue()->equalsInt(1)) - return LHS; // X /s 1 --> x + return LHS; // X sdiv 1 --> x if (RHSC->getValue()->isAllOnesValue()) - return SCEV::getNegativeSCEV(LHS); // X /s -1 --> -x + return SCEV::getNegativeSCEV(LHS); // X sdiv -1 --> -x if (SCEVConstant *LHSC = dyn_cast(LHS)) { Constant *LHSCV = LHSC->getValue(); Constant *RHSCV = RHSC->getValue(); - if (LHSCV->getType()->isUnsigned()) - LHSCV = ConstantExpr::getCast(LHSCV, - LHSCV->getType()->getSignedVersion()); - if (RHSCV->getType()->isUnsigned()) - RHSCV = ConstantExpr::getCast(RHSCV, LHSCV->getType()); - return SCEVUnknown::get(ConstantExpr::getDiv(LHSCV, RHSCV)); + return SCEVUnknown::get(ConstantExpr::getSDiv(LHSCV, RHSCV)); } } // FIXME: implement folding of (X*4)/4 when we know X*4 doesn't overflow. - SCEVSDivExpr *&Result = SCEVSDivs[std::make_pair(LHS, RHS)]; + SCEVSDivExpr *&Result = (*SCEVSDivs)[std::make_pair(LHS, RHS)]; if (Result == 0) Result = new SCEVSDivExpr(LHS, RHS); return Result; } @@ -1039,8 +1023,8 @@ SCEVHandle SCEVAddRecExpr::get(std::vector &Operands, } SCEVAddRecExpr *&Result = - SCEVAddRecExprs[std::make_pair(L, std::vector(Operands.begin(), - Operands.end()))]; + (*SCEVAddRecExprs)[std::make_pair(L, std::vector(Operands.begin(), + Operands.end()))]; if (Result == 0) Result = new SCEVAddRecExpr(Operands, L); return Result; } @@ -1048,7 +1032,7 @@ SCEVHandle SCEVAddRecExpr::get(std::vector &Operands, SCEVHandle SCEVUnknown::get(Value *V) { if (ConstantInt *CI = dyn_cast(V)) return SCEVConstant::get(CI); - SCEVUnknown *&Result = SCEVUnknowns[V]; + SCEVUnknown *&Result = (*SCEVUnknowns)[V]; if (Result == 0) Result = new SCEVUnknown(V); return Result; } @@ -1062,7 +1046,7 @@ SCEVHandle SCEVUnknown::get(Value *V) { /// evolution code. /// namespace { - struct ScalarEvolutionsImpl { + struct VISIBILITY_HIDDEN ScalarEvolutionsImpl { /// F - The function we are analyzing. /// Function &F; @@ -1136,7 +1120,6 @@ namespace { /// createSCEV - We know that there is no SCEV for the specified value. /// Analyze the expression. SCEVHandle createSCEV(Value *V); - SCEVHandle createNodeForCast(CastInst *CI); /// createNodeForPHI - Provide the special handling we need to analyze PHI /// SCEVs. @@ -1159,7 +1142,7 @@ namespace { SCEVHandle ComputeLoadConstantCompareIterationCount(LoadInst *LI, Constant *RHS, const Loop *L, - unsigned SetCCOpcode); + ICmpInst::Predicate p); /// ComputeIterationCountExhaustively - If the trip is known to execute a /// constant number of times (the condition evolves only from constants), @@ -1295,6 +1278,31 @@ SCEVHandle ScalarEvolutionsImpl::createNodeForPHI(PHINode *PN) { SCEVHandle StartVal = getSCEV(PN->getIncomingValue(IncomingEdge)); SCEVHandle PHISCEV = SCEVAddRecExpr::get(StartVal, Accum, L); + // Okay, for the entire analysis of this edge we assumed the PHI + // to be symbolic. We now need to go back and update all of the + // entries for the scalars that use the PHI (except for the PHI + // itself) to use the new analyzed value instead of the "symbolic" + // value. + ReplaceSymbolicValueWithConcrete(PN, SymbolicName, PHISCEV); + return PHISCEV; + } + } + } else if (SCEVAddRecExpr *AddRec = dyn_cast(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. + // Because the other in-value of i (0) fits the evolution of BEValue + // i really is an addrec evolution. + if (AddRec->getLoop() == L && AddRec->isAffine()) { + SCEVHandle StartVal = getSCEV(PN->getIncomingValue(IncomingEdge)); + + // If StartVal = j.start - j.stride, we can use StartVal as the + // initial step of the addrec evolution. + if (StartVal == SCEV::getMinusSCEV(AddRec->getOperand(0), + AddRec->getOperand(1))) { + SCEVHandle PHISCEV = + SCEVAddRecExpr::get(StartVal, AddRec->getOperand(1), L); + // Okay, for the entire analysis of this edge we assumed the PHI // to be symbolic. We now need to go back and update all of the // entries for the scalars that use the PHI (except for the PHI @@ -1313,36 +1321,53 @@ SCEVHandle ScalarEvolutionsImpl::createNodeForPHI(PHINode *PN) { return SCEVUnknown::get(PN); } -/// createNodeForCast - Handle the various forms of casts that we support. -/// -SCEVHandle ScalarEvolutionsImpl::createNodeForCast(CastInst *CI) { - const Type *SrcTy = CI->getOperand(0)->getType(); - const Type *DestTy = CI->getType(); - - // If this is a noop cast (ie, conversion from int to uint), ignore it. - if (SrcTy->isLosslesslyConvertibleTo(DestTy)) - return getSCEV(CI->getOperand(0)); - - if (SrcTy->isInteger() && DestTy->isInteger()) { - // Otherwise, if this is a truncating integer cast, we can represent this - // cast. - if (SrcTy->getPrimitiveSize() > DestTy->getPrimitiveSize()) - return SCEVTruncateExpr::get(getSCEV(CI->getOperand(0)), - CI->getType()->getUnsignedVersion()); - if (SrcTy->isUnsigned() && - SrcTy->getPrimitiveSize() > DestTy->getPrimitiveSize()) - return SCEVZeroExtendExpr::get(getSCEV(CI->getOperand(0)), - CI->getType()->getUnsignedVersion()); +/// GetConstantFactor - Determine the largest constant factor that S has. For +/// example, turn {4,+,8} -> 4. (S umod result) should always equal zero. +static uint64_t GetConstantFactor(SCEVHandle S) { + if (SCEVConstant *C = dyn_cast(S)) { + if (uint64_t V = C->getValue()->getZExtValue()) + return V; + else // Zero is a multiple of everything. + return 1ULL << (S->getType()->getPrimitiveSizeInBits()-1); } - // If this is an sign or zero extending cast and we can prove that the value - // will never overflow, we could do similar transformations. + if (SCEVTruncateExpr *T = dyn_cast(S)) + return GetConstantFactor(T->getOperand()) & + T->getType()->getIntegralTypeMask(); + if (SCEVZeroExtendExpr *E = dyn_cast(S)) + return GetConstantFactor(E->getOperand()); + + if (SCEVAddExpr *A = dyn_cast(S)) { + // The result is the min of all operands. + uint64_t Res = GetConstantFactor(A->getOperand(0)); + for (unsigned i = 1, e = A->getNumOperands(); i != e && Res > 1; ++i) + Res = std::min(Res, GetConstantFactor(A->getOperand(i))); + return Res; + } - // Otherwise, we can't handle this cast! - return SCEVUnknown::get(CI); + if (SCEVMulExpr *M = dyn_cast(S)) { + // The result is the product of all the operands. + uint64_t Res = GetConstantFactor(M->getOperand(0)); + for (unsigned i = 1, e = M->getNumOperands(); i != e; ++i) + Res *= GetConstantFactor(M->getOperand(i)); + return Res; + } + + if (SCEVAddRecExpr *A = dyn_cast(S)) { + // For now, we just handle linear expressions. + if (A->getNumOperands() == 2) { + // We want the GCD between the start and the stride value. + uint64_t Start = GetConstantFactor(A->getOperand(0)); + if (Start == 1) return 1; + uint64_t Stride = GetConstantFactor(A->getOperand(1)); + return GreatestCommonDivisor64(Start, Stride); + } + } + + // SCEVSDivExpr, SCEVUnknown. + return 1; } - /// createSCEV - We know that there is no SCEV for the specified value. /// Analyze the expression. /// @@ -1355,16 +1380,30 @@ SCEVHandle ScalarEvolutionsImpl::createSCEV(Value *V) { case Instruction::Mul: return SCEVMulExpr::get(getSCEV(I->getOperand(0)), getSCEV(I->getOperand(1))); - case Instruction::Div: - if (V->getType()->isInteger() && V->getType()->isSigned()) - return SCEVSDivExpr::get(getSCEV(I->getOperand(0)), - getSCEV(I->getOperand(1))); + case Instruction::SDiv: + return SCEVSDivExpr::get(getSCEV(I->getOperand(0)), + getSCEV(I->getOperand(1))); break; case Instruction::Sub: return SCEV::getMinusSCEV(getSCEV(I->getOperand(0)), getSCEV(I->getOperand(1))); - + case Instruction::Or: + // If the RHS of the Or is a constant, we may have something like: + // X*4+1 which got turned into X*4|1. Handle this as an add so loop + // optimizations will transparently handle this case. + if (ConstantInt *CI = dyn_cast(I->getOperand(1))) { + SCEVHandle LHS = getSCEV(I->getOperand(0)); + uint64_t CommonFact = GetConstantFactor(LHS); + assert(CommonFact && "Common factor should at least be 1!"); + if (CommonFact > CI->getZExtValue()) { + // If the LHS is a multiple that is larger than the RHS, use +. + return SCEVAddExpr::get(LHS, + getSCEV(I->getOperand(1))); + } + } + break; + case Instruction::Shl: // Turn shift left of a constant amount into a multiply. if (ConstantInt *SA = dyn_cast(I->getOperand(1))) { @@ -1374,8 +1413,23 @@ SCEVHandle ScalarEvolutionsImpl::createSCEV(Value *V) { } break; - case Instruction::Cast: - return createNodeForCast(cast(I)); + case Instruction::Trunc: + // We don't handle trunc to bool yet. + if (I->getType()->isInteger()) + return SCEVTruncateExpr::get(getSCEV(I->getOperand(0)), I->getType()); + break; + + case Instruction::ZExt: + // We don't handle zext from bool yet. + if (I->getOperand(0)->getType()->isInteger()) + return SCEVZeroExtendExpr::get(getSCEV(I->getOperand(0)), I->getType()); + break; + + case Instruction::BitCast: + // BitCasts are no-op casts so we just eliminate the cast. + if (I->getType()->isInteger() && I->getOperand(0)->getType()->isInteger()) + return getSCEV(I->getOperand(0)); + break; case Instruction::PHI: return createNodeForPHI(cast(I)); @@ -1441,21 +1495,38 @@ SCEVHandle ScalarEvolutionsImpl::ComputeIterationCount(const Loop *L) { // exit. // // FIXME: we should be able to handle switch instructions (with a single exit) - // FIXME: We should handle cast of int to bool as well BranchInst *ExitBr = dyn_cast(ExitingBlock->getTerminator()); if (ExitBr == 0) return UnknownValue; assert(ExitBr->isConditional() && "If unconditional, it can't be in loop!"); - SetCondInst *ExitCond = dyn_cast(ExitBr->getCondition()); - if (ExitCond == 0) // Not a setcc + + // At this point, we know we have a conditional branch that determines whether + // the loop is exited. However, we don't know if the branch is executed each + // time through the loop. If not, then the execution count of the branch will + // not be equal to the trip count of the loop. + // + // Currently we check for this by checking to see if the Exit branch goes to + // the loop header. If so, we know it will always execute the same number of + // times as the loop. More extensive analysis could be done to handle more + // cases here. + if (ExitBr->getSuccessor(0) != L->getHeader() && + ExitBr->getSuccessor(1) != L->getHeader()) + return UnknownValue; + + ICmpInst *ExitCond = dyn_cast(ExitBr->getCondition()); + + // If its not an integer comparison then compute it the hard way. + // Note that ICmpInst deals with pointer comparisons too so we must check + // the type of the operand. + if (ExitCond == 0 || isa(ExitCond->getOperand(0)->getType())) return ComputeIterationCountExhaustively(L, ExitBr->getCondition(), ExitBr->getSuccessor(0) == ExitBlock); - // If the condition was exit on true, convert the condition to exit on false. - Instruction::BinaryOps Cond; + // If the condition was exit on true, convert the condition to exit on false + ICmpInst::Predicate Cond; if (ExitBr->getSuccessor(1) == ExitBlock) - Cond = ExitCond->getOpcode(); + Cond = ExitCond->getPredicate(); else - Cond = ExitCond->getInverseCondition(); + Cond = ExitCond->getInversePredicate(); // Handle common loops like: for (X = "string"; *X; ++X) if (LoadInst *LI = dyn_cast(ExitCond->getOperand(0))) @@ -1474,12 +1545,12 @@ SCEVHandle ScalarEvolutionsImpl::ComputeIterationCount(const Loop *L) { Tmp = getSCEVAtScope(RHS, L); if (!isa(Tmp)) RHS = Tmp; - // At this point, we would like to compute how many iterations of the loop the - // predicate will return true for these inputs. + // At this point, we would like to compute how many iterations of the + // loop the predicate will return true for these inputs. if (isa(LHS) && !isa(RHS)) { // If there is a constant, force it into the RHS. std::swap(LHS, RHS); - Cond = SetCondInst::getSwappedCondition(Cond); + Cond = ICmpInst::getSwappedPredicate(Cond); } // FIXME: think about handling pointer comparisons! i.e.: @@ -1495,67 +1566,54 @@ SCEVHandle ScalarEvolutionsImpl::ComputeIterationCount(const Loop *L) { // comparison. ConstantInt *CompVal = RHSC->getValue(); const Type *RealTy = ExitCond->getOperand(0)->getType(); - CompVal = dyn_cast(ConstantExpr::getCast(CompVal, RealTy)); + CompVal = dyn_cast( + ConstantExpr::getBitCast(CompVal, RealTy)); if (CompVal) { // Form the constant range. ConstantRange CompRange(Cond, CompVal); - // Now that we have it, if it's signed, convert it to an unsigned - // range. - if (CompRange.getLower()->getType()->isSigned()) { - const Type *NewTy = RHSC->getValue()->getType(); - Constant *NewL = ConstantExpr::getCast(CompRange.getLower(), NewTy); - Constant *NewU = ConstantExpr::getCast(CompRange.getUpper(), NewTy); - CompRange = ConstantRange(NewL, NewU); - } - - SCEVHandle Ret = AddRec->getNumIterationsInRange(CompRange); + SCEVHandle Ret = AddRec->getNumIterationsInRange(CompRange, + false /*Always treat as unsigned range*/); if (!isa(Ret)) return Ret; } } switch (Cond) { - case Instruction::SetNE: // while (X != Y) + case ICmpInst::ICMP_NE: { // while (X != Y) // Convert to: while (X-Y != 0) - if (LHS->getType()->isInteger()) { - SCEVHandle TC = HowFarToZero(SCEV::getMinusSCEV(LHS, RHS), L); - if (!isa(TC)) return TC; - } + SCEVHandle TC = HowFarToZero(SCEV::getMinusSCEV(LHS, RHS), L); + if (!isa(TC)) return TC; break; - case Instruction::SetEQ: + } + case ICmpInst::ICMP_EQ: { // Convert to: while (X-Y == 0) // while (X == Y) - if (LHS->getType()->isInteger()) { - SCEVHandle TC = HowFarToNonZero(SCEV::getMinusSCEV(LHS, RHS), L); - if (!isa(TC)) return TC; - } + SCEVHandle TC = HowFarToNonZero(SCEV::getMinusSCEV(LHS, RHS), L); + if (!isa(TC)) return TC; break; - case Instruction::SetLT: - if (LHS->getType()->isInteger() && - ExitCond->getOperand(0)->getType()->isSigned()) { - SCEVHandle TC = HowManyLessThans(LHS, RHS, L); - if (!isa(TC)) return TC; - } + } + case ICmpInst::ICMP_SLT: { + SCEVHandle TC = HowManyLessThans(LHS, RHS, L); + if (!isa(TC)) return TC; break; - case Instruction::SetGT: - if (LHS->getType()->isInteger() && - ExitCond->getOperand(0)->getType()->isSigned()) { - SCEVHandle TC = HowManyLessThans(RHS, LHS, L); - if (!isa(TC)) return TC; - } + } + case ICmpInst::ICMP_SGT: { + SCEVHandle TC = HowManyLessThans(RHS, LHS, L); + if (!isa(TC)) return TC; break; + } default: #if 0 - std::cerr << "ComputeIterationCount "; + cerr << "ComputeIterationCount "; if (ExitCond->getOperand(0)->getType()->isUnsigned()) - std::cerr << "[unsigned] "; - std::cerr << *LHS << " " - << Instruction::getOpcodeName(Cond) << " " << *RHS << "\n"; + cerr << "[unsigned] "; + cerr << *LHS << " " + << Instruction::getOpcodeName(Instruction::ICmp) + << " " << *RHS << "\n"; #endif break; } - return ComputeIterationCountExhaustively(L, ExitCond, - ExitBr->getSuccessor(0) == ExitBlock); + ExitBr->getSuccessor(0) == ExitBlock); } static ConstantInt * @@ -1576,7 +1634,7 @@ GetAddressedElementFromGlobal(GlobalVariable *GV, const std::vector &Indices) { Constant *Init = GV->getInitializer(); for (unsigned i = 0, e = Indices.size(); i != e; ++i) { - uint64_t Idx = Indices[i]->getRawValue(); + uint64_t Idx = Indices[i]->getZExtValue(); if (ConstantStruct *CS = dyn_cast(Init)) { assert(Idx < CS->getNumOperands() && "Bad struct index!"); Init = cast(CS->getOperand(Idx)); @@ -1605,7 +1663,8 @@ GetAddressedElementFromGlobal(GlobalVariable *GV, /// 'setcc load X, cst', try to se if we can compute the trip count. SCEVHandle ScalarEvolutionsImpl:: ComputeLoadConstantCompareIterationCount(LoadInst *LI, Constant *RHS, - const Loop *L, unsigned SetCCOpcode) { + const Loop *L, + ICmpInst::Predicate predicate) { if (LI->isVolatile()) return UnknownValue; // Check to see if the loaded pointer is a getelementptr of a global. @@ -1650,8 +1709,8 @@ ComputeLoadConstantCompareIterationCount(LoadInst *LI, Constant *RHS, unsigned MaxSteps = MaxBruteForceIterations; for (unsigned IterationNum = 0; IterationNum != MaxSteps; ++IterationNum) { - ConstantUInt *ItCst = - ConstantUInt::get(IdxExpr->getType()->getUnsignedVersion(), IterationNum); + ConstantInt *ItCst = + ConstantInt::get(IdxExpr->getType(), IterationNum); ConstantInt *Val = EvaluateConstantChrecAtConstant(IdxExpr, ItCst); // Form the GEP offset. @@ -1661,13 +1720,13 @@ ComputeLoadConstantCompareIterationCount(LoadInst *LI, Constant *RHS, if (Result == 0) break; // Cannot compute! // Evaluate the condition for this iteration. - Result = ConstantExpr::get(SetCCOpcode, Result, RHS); + Result = ConstantExpr::getICmp(predicate, Result, RHS); if (!isa(Result)) break; // Couldn't decide for sure - if (Result == ConstantBool::False) { + if (cast(Result)->getValue() == false) { #if 0 - std::cerr << "\n***\n*** Computed loop count " << *ItCst - << "\n*** From global " << *GV << "*** BB: " << *L->getHeader() - << "***\n"; + cerr << "\n***\n*** Computed loop count " << *ItCst + << "\n*** From global " << *GV << "*** BB: " << *L->getHeader() + << "***\n"; #endif ++NumArrayLenItCounts; return SCEVConstant::get(ItCst); // Found terminating iteration! @@ -1680,7 +1739,7 @@ ComputeLoadConstantCompareIterationCount(LoadInst *LI, Constant *RHS, /// CanConstantFold - Return true if we can constant fold an instruction of the /// specified type, assuming that all operands were constants. static bool CanConstantFold(const Instruction *I) { - if (isa(I) || isa(I) || + if (isa(I) || isa(I) || isa(I) || isa(I) || isa(I) || isa(I)) return true; @@ -1697,9 +1756,10 @@ static Constant *ConstantFold(const Instruction *I, if (isa(I) || isa(I)) return ConstantExpr::get(I->getOpcode(), Operands[0], Operands[1]); + if (isa(I)) + return ConstantExpr::getCast(I->getOpcode(), Operands[0], I->getType()); + switch (I->getOpcode()) { - case Instruction::Cast: - return ConstantExpr::getCast(Operands[0], I->getType()); case Instruction::Select: return ConstantExpr::getSelect(Operands[0], Operands[1], Operands[2]); case Instruction::Call: @@ -1707,13 +1767,19 @@ static Constant *ConstantFold(const Instruction *I, Operands.erase(Operands.begin()); return ConstantFoldCall(cast(GV), Operands); } - return 0; - case Instruction::GetElementPtr: + case Instruction::GetElementPtr: { Constant *Base = Operands[0]; Operands.erase(Operands.begin()); return ConstantExpr::getGetElementPtr(Base, Operands); } + case Instruction::ICmp: + return ConstantExpr::getICmp( + cast(I)->getPredicate(), Operands[0], Operands[1]); + case Instruction::FCmp: + return ConstantExpr::getFCmp( + cast(I)->getPredicate(), Operands[0], Operands[1]); + } return 0; } @@ -1867,7 +1933,7 @@ ComputeIterationCountExhaustively(const Loop *L, Value *Cond, bool ExitWhen) { if (CondVal->getValue() == ExitWhen) { ConstantEvolutionLoopExitValue[PN] = PHIVal; ++NumBruteForceTripCountsComputed; - return SCEVConstant::get(ConstantUInt::get(Type::UIntTy, IterationNum)); + return SCEVConstant::get(ConstantInt::get(Type::Int32Ty, IterationNum)); } // Compute the value of the PHI node for the next iteration. @@ -1906,15 +1972,15 @@ SCEVHandle ScalarEvolutionsImpl::getSCEVAtScope(SCEV *V, const Loop *L) { // this is a constant evolving PHI node, get the final value at // the specified iteration number. Constant *RV = getConstantEvolutionLoopExitValue(PN, - ICC->getValue()->getRawValue(), + ICC->getValue()->getZExtValue(), LI); if (RV) return SCEVUnknown::get(RV); } } - // Okay, this is a some expression that we cannot symbolically evaluate + // Okay, this is an expression that we cannot symbolically evaluate // into a SCEV. Check to see if it's possible to symbolically evaluate - // the arguments into constants, and if see, try to constant propagate the + // the arguments into constants, and if so, try to constant propagate the // result. This is particularly useful for computing loop exit values. if (CanConstantFold(I)) { std::vector Operands; @@ -1926,11 +1992,14 @@ SCEVHandle ScalarEvolutionsImpl::getSCEVAtScope(SCEV *V, const Loop *L) { } else { SCEVHandle OpV = getSCEVAtScope(getSCEV(Op), L); if (SCEVConstant *SC = dyn_cast(OpV)) - Operands.push_back(ConstantExpr::getCast(SC->getValue(), - Op->getType())); + Operands.push_back(ConstantExpr::getIntegerCast(SC->getValue(), + Op->getType(), + false)); else if (SCEVUnknown *SU = dyn_cast(OpV)) { if (Constant *C = dyn_cast(SU->getValue())) - Operands.push_back(ConstantExpr::getCast(C, Op->getType())); + Operands.push_back(ConstantExpr::getIntegerCast(C, + Op->getType(), + false)); else return V; } else { @@ -2029,16 +2098,16 @@ SolveQuadraticEquation(const SCEVAddRecExpr *AddRec) { return std::make_pair(CNC, CNC); } - Constant *Two = ConstantInt::get(L->getValue()->getType(), 2); + Constant *C = L->getValue(); + Constant *Two = ConstantInt::get(C->getType(), 2); // Convert from chrec coefficients to polynomial coefficients AX^2+BX+C - Constant *C = L->getValue(); // The B coefficient is M-N/2 Constant *B = ConstantExpr::getSub(M->getValue(), - ConstantExpr::getDiv(N->getValue(), + ConstantExpr::getSDiv(N->getValue(), Two)); // The A coefficient is N/2 - Constant *A = ConstantExpr::getDiv(N->getValue(), Two); + Constant *A = ConstantExpr::getSDiv(N->getValue(), Two); // Compute the B^2-4ac term. Constant *SqrtTerm = @@ -2047,10 +2116,7 @@ SolveQuadraticEquation(const SCEVAddRecExpr *AddRec) { SqrtTerm = ConstantExpr::getSub(ConstantExpr::getMul(B, B), SqrtTerm); // Compute floor(sqrt(B^2-4ac)) - ConstantUInt *SqrtVal = - cast(ConstantExpr::getCast(SqrtTerm, - SqrtTerm->getType()->getUnsignedVersion())); - uint64_t SqrtValV = SqrtVal->getValue(); + uint64_t SqrtValV = cast(SqrtTerm)->getZExtValue(); uint64_t SqrtValV2 = (uint64_t)sqrt((double)SqrtValV); // The square root might not be precise for arbitrary 64-bit integer // values. Do some sanity checks to ensure it's correct. @@ -2060,22 +2126,17 @@ SolveQuadraticEquation(const SCEVAddRecExpr *AddRec) { return std::make_pair(CNC, CNC); } - SqrtVal = ConstantUInt::get(Type::ULongTy, SqrtValV2); - SqrtTerm = ConstantExpr::getCast(SqrtVal, SqrtTerm->getType()); + ConstantInt *SqrtVal = ConstantInt::get(Type::Int64Ty, SqrtValV2); + SqrtTerm = ConstantExpr::getTruncOrBitCast(SqrtVal, SqrtTerm->getType()); Constant *NegB = ConstantExpr::getNeg(B); Constant *TwoA = ConstantExpr::getMul(A, Two); // The divisions must be performed as signed divisions. - const Type *SignedTy = NegB->getType()->getSignedVersion(); - NegB = ConstantExpr::getCast(NegB, SignedTy); - TwoA = ConstantExpr::getCast(TwoA, SignedTy); - SqrtTerm = ConstantExpr::getCast(SqrtTerm, SignedTy); - Constant *Solution1 = - ConstantExpr::getDiv(ConstantExpr::getAdd(NegB, SqrtTerm), TwoA); + ConstantExpr::getSDiv(ConstantExpr::getAdd(NegB, SqrtTerm), TwoA); Constant *Solution2 = - ConstantExpr::getDiv(ConstantExpr::getSub(NegB, SqrtTerm), TwoA); + ConstantExpr::getSDiv(ConstantExpr::getSub(NegB, SqrtTerm), TwoA); return std::make_pair(SCEVUnknown::get(Solution1), SCEVUnknown::get(Solution2)); } @@ -2119,9 +2180,9 @@ SCEVHandle ScalarEvolutionsImpl::HowFarToZero(SCEV *V, const Loop *L) { if (SCEVConstant *StartC = dyn_cast(Start)) { ConstantInt *StartCC = StartC->getValue(); Constant *StartNegC = ConstantExpr::getNeg(StartCC); - Constant *Rem = ConstantExpr::getRem(StartNegC, StepC->getValue()); + Constant *Rem = ConstantExpr::getSRem(StartNegC, StepC->getValue()); if (Rem->isNullValue()) { - Constant *Result =ConstantExpr::getDiv(StartNegC,StepC->getValue()); + Constant *Result =ConstantExpr::getSDiv(StartNegC,StepC->getValue()); return SCEVUnknown::get(Result); } } @@ -2134,15 +2195,14 @@ SCEVHandle ScalarEvolutionsImpl::HowFarToZero(SCEV *V, const Loop *L) { SCEVConstant *R2 = dyn_cast(Roots.second); if (R1) { #if 0 - std::cerr << "HFTZ: " << *V << " - sol#1: " << *R1 - << " sol#2: " << *R2 << "\n"; + cerr << "HFTZ: " << *V << " - sol#1: " << *R1 + << " sol#2: " << *R2 << "\n"; #endif // Pick the smallest positive root value. - assert(R1->getType()->isUnsigned()&&"Didn't canonicalize to unsigned?"); if (ConstantBool *CB = - dyn_cast(ConstantExpr::getSetLT(R1->getValue(), - R2->getValue()))) { - if (CB != ConstantBool::True) + dyn_cast(ConstantExpr::getICmp(ICmpInst::ICMP_ULT, + R1->getValue(), R2->getValue()))) { + if (CB->getValue() == 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 @@ -2171,8 +2231,9 @@ SCEVHandle ScalarEvolutionsImpl::HowFarToNonZero(SCEV *V, const Loop *L) { // already. If so, the backedge will execute zero times. if (SCEVConstant *C = dyn_cast(V)) { Constant *Zero = Constant::getNullValue(C->getValue()->getType()); - Constant *NonZero = ConstantExpr::getSetNE(C->getValue(), Zero); - if (NonZero == ConstantBool::True) + Constant *NonZero = + ConstantExpr::getICmp(ICmpInst::ICMP_NE, C->getValue(), Zero); + if (NonZero == ConstantBool::getTrue()) return getSCEV(Zero); return UnknownValue; // Otherwise it will loop infinitely. } @@ -2232,40 +2293,46 @@ HowManyLessThans(SCEV *LHS, SCEV *RHS, const Loop *L) { // Now that we found a conditional branch that dominates the loop, check to // see if it is the comparison we are looking for. - SetCondInst *SCI =dyn_cast(LoopEntryPredicate->getCondition()); - if (!SCI) return UnknownValue; - Value *PreCondLHS = SCI->getOperand(0); - Value *PreCondRHS = SCI->getOperand(1); - Instruction::BinaryOps Cond; - if (LoopEntryPredicate->getSuccessor(0) == PreheaderDest) - Cond = SCI->getOpcode(); - else - Cond = SCI->getInverseCondition(); + if (ICmpInst *ICI = dyn_cast(LoopEntryPredicate->getCondition())){ + Value *PreCondLHS = ICI->getOperand(0); + Value *PreCondRHS = ICI->getOperand(1); + ICmpInst::Predicate Cond; + if (LoopEntryPredicate->getSuccessor(0) == PreheaderDest) + Cond = ICI->getPredicate(); + else + Cond = ICI->getInversePredicate(); - switch (Cond) { - case Instruction::SetGT: - std::swap(PreCondLHS, PreCondRHS); - Cond = Instruction::SetLT; - // Fall Through. - case Instruction::SetLT: - if (PreCondLHS->getType()->isInteger() && - PreCondLHS->getType()->isSigned()) { - if (RHS != getSCEV(PreCondRHS)) - return UnknownValue; // Not a comparison against 'm'. - - if (SCEV::getMinusSCEV(AddRec->getOperand(0), One) - != getSCEV(PreCondLHS)) - return UnknownValue; // Not a comparison against 'n-1'. + switch (Cond) { + case ICmpInst::ICMP_UGT: + std::swap(PreCondLHS, PreCondRHS); + Cond = ICmpInst::ICMP_ULT; break; - } else { - return UnknownValue; + case ICmpInst::ICMP_SGT: + std::swap(PreCondLHS, PreCondRHS); + Cond = ICmpInst::ICMP_SLT; + break; + default: break; } - default: break; - } - //std::cerr << "Computed Loop Trip Count as: " << - // *SCEV::getMinusSCEV(RHS, AddRec->getOperand(0)) << "\n"; - return SCEV::getMinusSCEV(RHS, AddRec->getOperand(0)); + if (Cond == ICmpInst::ICMP_SLT) { + if (PreCondLHS->getType()->isInteger()) { + if (RHS != getSCEV(PreCondRHS)) + return UnknownValue; // Not a comparison against 'm'. + + if (SCEV::getMinusSCEV(AddRec->getOperand(0), One) + != getSCEV(PreCondLHS)) + return UnknownValue; // Not a comparison against 'n-1'. + } + else return UnknownValue; + } else if (Cond == ICmpInst::ICMP_ULT) + return UnknownValue; + + // cerr << "Computed Loop Trip Count as: " + // << // *SCEV::getMinusSCEV(RHS, AddRec->getOperand(0)) << "\n"; + return SCEV::getMinusSCEV(RHS, AddRec->getOperand(0)); + } + else + return UnknownValue; } return UnknownValue; @@ -2276,7 +2343,8 @@ HowManyLessThans(SCEV *LHS, SCEV *RHS, const Loop *L) { /// this is that it returns the first iteration number where the value is not in /// the condition, thus computing the exit count. If the iteration count can't /// be computed, an instance of SCEVCouldNotCompute is returned. -SCEVHandle SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range) const { +SCEVHandle SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range, + bool isSigned) const { if (Range.isFullSet()) // Infinite loop. return new SCEVCouldNotCompute(); @@ -2288,7 +2356,7 @@ SCEVHandle SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range) const { SCEVHandle Shifted = SCEVAddRecExpr::get(Operands, getLoop()); if (SCEVAddRecExpr *ShiftedAddRec = dyn_cast(Shifted)) return ShiftedAddRec->getNumIterationsInRange( - Range.subtract(SC->getValue())); + Range.subtract(SC->getValue()),isSigned); // This is strange and shouldn't happen. return new SCEVCouldNotCompute(); } @@ -2306,7 +2374,7 @@ SCEVHandle SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range) const { // First check to see if the range contains zero. If not, the first // iteration exits. ConstantInt *Zero = ConstantInt::get(getType(), 0); - if (!Range.contains(Zero)) return SCEVConstant::get(Zero); + if (!Range.contains(Zero, isSigned)) return SCEVConstant::get(Zero); if (isAffine()) { // If this is an affine expression then we have this situation: @@ -2323,7 +2391,7 @@ SCEVHandle SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range) const { Constant *ExitValue = Upper; if (A != One) { ExitValue = ConstantExpr::getSub(ConstantExpr::getAdd(Upper, A), One); - ExitValue = ConstantExpr::getDiv(ExitValue, A); + ExitValue = ConstantExpr::getSDiv(ExitValue, A); } assert(isa(ExitValue) && "Constant folding of integers not implemented?"); @@ -2332,12 +2400,12 @@ SCEVHandle SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range) const { // range, then we computed our trip count, otherwise wrap around or other // things must have happened. ConstantInt *Val = EvaluateConstantChrecAtConstant(this, ExitValue); - if (Range.contains(Val)) + if (Range.contains(Val, isSigned)) return new SCEVCouldNotCompute(); // Something strange happened // Ensure that the previous value is in the range. This is a sanity check. assert(Range.contains(EvaluateConstantChrecAtConstant(this, - ConstantExpr::getSub(ExitValue, One))) && + ConstantExpr::getSub(ExitValue, One)), isSigned) && "Linear scev computation is off in a bad way!"); return SCEVConstant::get(cast(ExitValue)); } else if (isQuadratic()) { @@ -2356,11 +2424,10 @@ SCEVHandle SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range) const { SCEVConstant *R2 = dyn_cast(Roots.second); if (R1) { // Pick the smallest positive root value. - assert(R1->getType()->isUnsigned() && "Didn't canonicalize to unsigned?"); if (ConstantBool *CB = - dyn_cast(ConstantExpr::getSetLT(R1->getValue(), - R2->getValue()))) { - if (CB != ConstantBool::True) + dyn_cast(ConstantExpr::getICmp(ICmpInst::ICMP_ULT, + R1->getValue(), R2->getValue()))) { + if (CB->getValue() == false) std::swap(R1, R2); // R1 is the minimum root now. // Make sure the root is not off by one. The returned iteration should @@ -2368,14 +2435,14 @@ SCEVHandle SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range) const { // for "X*X < 5", for example, we should not return a root of 2. ConstantInt *R1Val = EvaluateConstantChrecAtConstant(this, R1->getValue()); - if (Range.contains(R1Val)) { + if (Range.contains(R1Val, isSigned)) { // The next iteration must be out of the range... Constant *NextVal = ConstantExpr::getAdd(R1->getValue(), ConstantInt::get(R1->getType(), 1)); R1Val = EvaluateConstantChrecAtConstant(this, NextVal); - if (!Range.contains(R1Val)) + if (!Range.contains(R1Val, isSigned)) return SCEVUnknown::get(NextVal); return new SCEVCouldNotCompute(); // Something strange happened } @@ -2386,7 +2453,7 @@ SCEVHandle SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range) const { ConstantExpr::getSub(R1->getValue(), ConstantInt::get(R1->getType(), 1)); R1Val = EvaluateConstantChrecAtConstant(this, NextVal); - if (Range.contains(R1Val)) + if (Range.contains(R1Val, isSigned)) return R1; return new SCEVCouldNotCompute(); // Something strange happened } @@ -2408,7 +2475,7 @@ SCEVHandle SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range) const { return new SCEVCouldNotCompute(); // Check to see if we found the value! - if (!Range.contains(cast(Val)->getValue())) + if (!Range.contains(cast(Val)->getValue(), isSigned)) return SCEVConstant::get(TestVal); // Increment to test the next index. @@ -2479,20 +2546,20 @@ static void PrintLoopInfo(std::ostream &OS, const ScalarEvolution *SE, for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) PrintLoopInfo(OS, SE, *I); - std::cerr << "Loop " << L->getHeader()->getName() << ": "; + cerr << "Loop " << L->getHeader()->getName() << ": "; std::vector ExitBlocks; L->getExitBlocks(ExitBlocks); if (ExitBlocks.size() != 1) - std::cerr << " "; + cerr << " "; if (SE->hasLoopInvariantIterationCount(L)) { - std::cerr << *SE->getIterationCount(L) << " iterations! "; + cerr << *SE->getIterationCount(L) << " iterations! "; } else { - std::cerr << "Unpredictable iteration count. "; + cerr << "Unpredictable iteration count. "; } - std::cerr << "\n"; + cerr << "\n"; } void ScalarEvolution::print(std::ostream &OS, const Module* ) const {