//
//===----------------------------------------------------------------------===//
+#define DEBUG_TYPE "scalar-evolution"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Constants.h"
#include "llvm/DerivedTypes.h"
#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 <cmath>
-#include <iostream>
+#include <ostream>
#include <algorithm>
+#include <cmath>
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<unsigned>
+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<ScalarEvolution>
+ RegisterPass<ScalarEvolution>
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<unsigned>
- MaxBruteForceIterations("scalar-evolution-max-iterations", cl::ReallyHidden,
- cl::desc("Maximum number of iterations SCEV will "
- "symbolically execute a constant derived loop"),
- cl::init(100));
}
//===----------------------------------------------------------------------===//
//
SCEV::~SCEV() {}
void SCEV::dump() const {
- print(std::cerr);
+ print(cerr);
}
/// getValueRange - Return the tightest constant bounds that this value is
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());
}
// 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<ConstantInt*, SCEVConstant*> SCEVConstants;
+static ManagedStatic<std::map<ConstantInt*, SCEVConstant*> > 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<ConstantUInt>(ConstantExpr::getCast(V, NewTy));
- }
-
- SCEVConstant *&R = SCEVConstants[V];
+ SCEVConstant *&R = (*SCEVConstants)[V];
if (R == 0) R = new SCEVConstant(V);
return R;
}
// 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<std::pair<SCEV*, const Type*>, SCEVTruncateExpr*> SCEVTruncates;
+static ManagedStatic<std::map<std::pair<SCEV*, const Type*>,
+ 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 {
// 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<std::pair<SCEV*, const Type*>,
- SCEVZeroExtendExpr*> SCEVZeroExtends;
+static ManagedStatic<std::map<std::pair<SCEV*, const Type*>,
+ 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 {
// 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<std::pair<unsigned, std::vector<SCEV*> >,
- SCEVCommutativeExpr*> SCEVCommExprs;
+static ManagedStatic<std::map<std::pair<unsigned, std::vector<SCEV*> >,
+ SCEVCommutativeExpr*> > SCEVCommExprs;
SCEVCommutativeExpr::~SCEVCommutativeExpr() {
- SCEVCommExprs.erase(std::make_pair(getSCEVType(),
- std::vector<SCEV*>(Operands.begin(),
- Operands.end())));
+ SCEVCommExprs->erase(std::make_pair(getSCEVType(),
+ std::vector<SCEV*>(Operands.begin(),
+ Operands.end())));
}
void SCEVCommutativeExpr::print(std::ostream &OS) const {
// 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<std::pair<SCEV*, SCEV*>, SCEVSDivExpr*> SCEVSDivs;
+static ManagedStatic<std::map<std::pair<SCEV*, SCEV*>,
+ 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 {
}
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<std::pair<const Loop *, std::vector<SCEV*> >,
- SCEVAddRecExpr*> SCEVAddRecExprs;
+static ManagedStatic<std::map<std::pair<const Loop *, std::vector<SCEV*> >,
+ SCEVAddRecExpr*> > SCEVAddRecExprs;
SCEVAddRecExpr::~SCEVAddRecExpr() {
- SCEVAddRecExprs.erase(std::make_pair(L,
- std::vector<SCEV*>(Operands.begin(),
- Operands.end())));
+ SCEVAddRecExprs->erase(std::make_pair(L,
+ std::vector<SCEV*>(Operands.begin(),
+ Operands.end())));
}
SCEVHandle SCEVAddRecExpr::
// 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<Value*, SCEVUnknown*> SCEVUnknowns;
+static ManagedStatic<std::map<Value*, SCEVUnknown*> > 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
/// 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();
}
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);
}
// Handle this case efficiently, it is common to have constant iteration
// counts while computing loop exit values.
if (SCEVConstant *SC = dyn_cast<SCEVConstant>(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();
SCEVHandle SCEVTruncateExpr::get(const SCEVHandle &Op, const Type *Ty) {
if (SCEVConstant *SC = dyn_cast<SCEVConstant>(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.
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<SCEVConstant>(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;
}
// 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<SCEV*> 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;
}
// 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<SCEV*> 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;
SCEVHandle SCEVSDivExpr::get(const SCEVHandle &LHS, const SCEVHandle &RHS) {
if (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(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<SCEVConstant>(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;
}
}
SCEVAddRecExpr *&Result =
- SCEVAddRecExprs[std::make_pair(L, std::vector<SCEV*>(Operands.begin(),
- Operands.end()))];
+ (*SCEVAddRecExprs)[std::make_pair(L, std::vector<SCEV*>(Operands.begin(),
+ Operands.end()))];
if (Result == 0) Result = new SCEVAddRecExpr(Operands, L);
return Result;
}
SCEVHandle SCEVUnknown::get(Value *V) {
if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
return SCEVConstant::get(CI);
- SCEVUnknown *&Result = SCEVUnknowns[V];
+ SCEVUnknown *&Result = (*SCEVUnknowns)[V];
if (Result == 0) Result = new SCEVUnknown(V);
return Result;
}
/// evolution code.
///
namespace {
- struct ScalarEvolutionsImpl {
+ struct VISIBILITY_HIDDEN ScalarEvolutionsImpl {
/// F - The function we are analyzing.
///
Function &F;
/// 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.
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),
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<SCEVAddRecExpr>(BEValue)) {
+ // Otherwise, this could be a loop like this:
+ // i = 0; for (j = 1; ..; ++j) { .... i = j; }
+ // In this case, j = {1,+,1} and BEValue is j.
+ // 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
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<SCEVConstant>(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<SCEVTruncateExpr>(S))
+ return GetConstantFactor(T->getOperand()) &
+ T->getType()->getIntegralTypeMask();
+ if (SCEVZeroExtendExpr *E = dyn_cast<SCEVZeroExtendExpr>(S))
+ return GetConstantFactor(E->getOperand());
+
+ if (SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(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<SCEVMulExpr>(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<SCEVAddRecExpr>(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.
///
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<ConstantInt>(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<ConstantInt>(I->getOperand(1))) {
}
break;
- case Instruction::Cast:
- return createNodeForCast(cast<CastInst>(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<PHINode>(I));
// 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<BranchInst>(ExitingBlock->getTerminator());
if (ExitBr == 0) return UnknownValue;
assert(ExitBr->isConditional() && "If unconditional, it can't be in loop!");
- SetCondInst *ExitCond = dyn_cast<SetCondInst>(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<ICmpInst>(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<PointerType>(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<LoadInst>(ExitCond->getOperand(0)))
Tmp = getSCEVAtScope(RHS, L);
if (!isa<SCEVCouldNotCompute>(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<SCEVConstant>(LHS) && !isa<SCEVConstant>(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.:
// comparison.
ConstantInt *CompVal = RHSC->getValue();
const Type *RealTy = ExitCond->getOperand(0)->getType();
- CompVal = dyn_cast<ConstantInt>(ConstantExpr::getCast(CompVal, RealTy));
+ CompVal = dyn_cast<ConstantInt>(
+ 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<SCEVCouldNotCompute>(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<SCEVCouldNotCompute>(TC)) return TC;
- }
+ SCEVHandle TC = HowFarToZero(SCEV::getMinusSCEV(LHS, RHS), L);
+ if (!isa<SCEVCouldNotCompute>(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<SCEVCouldNotCompute>(TC)) return TC;
- }
+ SCEVHandle TC = HowFarToNonZero(SCEV::getMinusSCEV(LHS, RHS), L);
+ if (!isa<SCEVCouldNotCompute>(TC)) return TC;
break;
- case Instruction::SetLT:
- if (LHS->getType()->isInteger() &&
- ExitCond->getOperand(0)->getType()->isSigned()) {
- SCEVHandle TC = HowManyLessThans(LHS, RHS, L);
- if (!isa<SCEVCouldNotCompute>(TC)) return TC;
- }
+ }
+ case ICmpInst::ICMP_SLT: {
+ SCEVHandle TC = HowManyLessThans(LHS, RHS, L);
+ if (!isa<SCEVCouldNotCompute>(TC)) return TC;
break;
- case Instruction::SetGT:
- if (LHS->getType()->isInteger() &&
- ExitCond->getOperand(0)->getType()->isSigned()) {
- SCEVHandle TC = HowManyLessThans(RHS, LHS, L);
- if (!isa<SCEVCouldNotCompute>(TC)) return TC;
- }
+ }
+ case ICmpInst::ICMP_SGT: {
+ SCEVHandle TC = HowManyLessThans(RHS, LHS, L);
+ if (!isa<SCEVCouldNotCompute>(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 *
const std::vector<ConstantInt*> &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<ConstantStruct>(Init)) {
assert(Idx < CS->getNumOperands() && "Bad struct index!");
Init = cast<Constant>(CS->getOperand(Idx));
/// '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.
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.
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<ConstantBool>(Result)) break; // Couldn't decide for sure
- if (Result == ConstantBool::False) {
+ if (cast<ConstantBool>(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!
/// 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<BinaryOperator>(I) || isa<ShiftInst>(I) ||
+ if (isa<BinaryOperator>(I) || isa<ShiftInst>(I) || isa<CmpInst>(I) ||
isa<SelectInst>(I) || isa<CastInst>(I) || isa<GetElementPtrInst>(I))
return true;
if (isa<BinaryOperator>(I) || isa<ShiftInst>(I))
return ConstantExpr::get(I->getOpcode(), Operands[0], Operands[1]);
+ if (isa<CastInst>(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:
Operands.erase(Operands.begin());
return ConstantFoldCall(cast<Function>(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<ICmpInst>(I)->getPredicate(), Operands[0], Operands[1]);
+ case Instruction::FCmp:
+ return ConstantExpr::getFCmp(
+ cast<FCmpInst>(I)->getPredicate(), Operands[0], Operands[1]);
+ }
return 0;
}
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.
// 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<Constant*> Operands;
} else {
SCEVHandle OpV = getSCEVAtScope(getSCEV(Op), L);
if (SCEVConstant *SC = dyn_cast<SCEVConstant>(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<SCEVUnknown>(OpV)) {
if (Constant *C = dyn_cast<Constant>(SU->getValue()))
- Operands.push_back(ConstantExpr::getCast(C, Op->getType()));
+ Operands.push_back(ConstantExpr::getIntegerCast(C,
+ Op->getType(),
+ false));
else
return V;
} else {
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 =
SqrtTerm = ConstantExpr::getSub(ConstantExpr::getMul(B, B), SqrtTerm);
// Compute floor(sqrt(B^2-4ac))
- ConstantUInt *SqrtVal =
- cast<ConstantUInt>(ConstantExpr::getCast(SqrtTerm,
- SqrtTerm->getType()->getUnsignedVersion()));
- uint64_t SqrtValV = SqrtVal->getValue();
+ uint64_t SqrtValV = cast<ConstantInt>(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.
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));
}
if (SCEVConstant *StartC = dyn_cast<SCEVConstant>(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);
}
}
SCEVConstant *R2 = dyn_cast<SCEVConstant>(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<ConstantBool>(ConstantExpr::getSetLT(R1->getValue(),
- R2->getValue()))) {
- if (CB != ConstantBool::True)
+ dyn_cast<ConstantBool>(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
// already. If so, the backedge will execute zero times.
if (SCEVConstant *C = dyn_cast<SCEVConstant>(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.
}
// 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<SetCondInst>(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<ICmpInst>(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;
/// 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();
SCEVHandle Shifted = SCEVAddRecExpr::get(Operands, getLoop());
if (SCEVAddRecExpr *ShiftedAddRec = dyn_cast<SCEVAddRecExpr>(Shifted))
return ShiftedAddRec->getNumIterationsInRange(
- Range.subtract(SC->getValue()));
+ Range.subtract(SC->getValue()),isSigned);
// This is strange and shouldn't happen.
return new SCEVCouldNotCompute();
}
// 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:
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<ConstantInt>(ExitValue) &&
"Constant folding of integers not implemented?");
// 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<ConstantInt>(ExitValue));
} else if (isQuadratic()) {
SCEVConstant *R2 = dyn_cast<SCEVConstant>(Roots.second);
if (R1) {
// Pick the smallest positive root value.
- assert(R1->getType()->isUnsigned() && "Didn't canonicalize to unsigned?");
if (ConstantBool *CB =
- dyn_cast<ConstantBool>(ConstantExpr::getSetLT(R1->getValue(),
- R2->getValue()))) {
- if (CB != ConstantBool::True)
+ dyn_cast<ConstantBool>(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
// 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
}
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
}
return new SCEVCouldNotCompute();
// Check to see if we found the value!
- if (!Range.contains(cast<SCEVConstant>(Val)->getValue()))
+ if (!Range.contains(cast<SCEVConstant>(Val)->getValue(), isSigned))
return SCEVConstant::get(TestVal);
// Increment to test the next index.
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<BasicBlock*> ExitBlocks;
L->getExitBlocks(ExitBlocks);
if (ExitBlocks.size() != 1)
- std::cerr << "<multiple exits> ";
+ cerr << "<multiple exits> ";
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 {