//===- ScalarEvolution.cpp - Scalar Evolution Analysis ----------*- C++ -*-===//
-//
+//
// The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
-//
+//
//===----------------------------------------------------------------------===//
//
// This file contains the implementation of the scalar evolution analysis
// have folders that are used to build the *canonical* representation for a
// particular expression. These folders are capable of using a variety of
// rewrite rules to simplify the expressions.
-//
+//
// Once the folders are defined, we can implement the more interesting
// higher-level code, such as the code that recognizes PHI nodes of various
// types, computes the execution count of a loop, etc.
#include "llvm/DerivedTypes.h"
#include "llvm/GlobalVariable.h"
#include "llvm/Instructions.h"
+#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Assembly/Writer.h"
#include "llvm/Transforms/Scalar.h"
-#include "llvm/Transforms/Utils/Local.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/ADT/Statistic.h"
#include <cmath>
+#include <iostream>
#include <algorithm>
using namespace llvm;
namespace {
- RegisterAnalysis<ScalarEvolution>
+ RegisterPass<ScalarEvolution>
R("scalar-evolution", "Scalar Evolution Analysis");
Statistic<>
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::desc("Maximum number of iterations SCEV will "
+ "symbolically execute a constant derived loop"),
cl::init(100));
}
// 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));
+ V = cast<ConstantInt>(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) {
}
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) {
}
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 {
}
-// SCEVUDivs - Only allow the creation of one SCEVUDivExpr for any particular
+// 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*>, SCEVUDivExpr*> SCEVUDivs;
+static ManagedStatic<std::map<std::pair<SCEV*, SCEV*>,
+ SCEVSDivExpr*> > SCEVSDivs;
-SCEVUDivExpr::~SCEVUDivExpr() {
- SCEVUDivs.erase(std::make_pair(LHS, RHS));
+SCEVSDivExpr::~SCEVSDivExpr() {
+ SCEVSDivs->erase(std::make_pair(LHS, RHS));
}
-void SCEVUDivExpr::print(std::ostream &OS) const {
- OS << "(" << *LHS << " /u " << *RHS << ")";
+void SCEVSDivExpr::print(std::ostream &OS) const {
+ OS << "(" << *LHS << " /s " << *RHS << ")";
}
-const Type *SCEVUDivExpr::getType() const {
+const Type *SCEVSDivExpr::getType() const {
const Type *Ty = LHS->getType();
- if (Ty->isSigned()) Ty = Ty->getUnsignedVersion();
+ if (Ty->isUnsigned()) Ty = Ty->getSignedVersion();
return Ty;
}
// 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::
for (++i; i != e; ++i)
NewOps.push_back(getOperand(i)->
replaceSymbolicValuesWithConcrete(Sym, Conc));
-
+
return get(NewOps, L);
}
}
bool SCEVAddRecExpr::isLoopInvariant(const Loop *QueryLoop) const {
// This recurrence is invariant w.r.t to QueryLoop iff QueryLoop doesn't
- // contain L.
- return !QueryLoop->contains(L->getHeader());
+ // contain L and if the start is invariant.
+ return !QueryLoop->contains(L->getHeader()) &&
+ getOperand(0)->isLoopInvariant(QueryLoop);
}
// 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();
}
/// specified signed integer value and return a SCEV for the constant.
SCEVHandle SCEVUnknown::getIntegerSCEV(int Val, const Type *Ty) {
Constant *C;
- if (Val == 0)
+ if (Val == 0)
C = Constant::getNullValue(Ty);
else if (Ty->isFloatingPoint())
C = ConstantFP::get(Ty, Val);
else if (Ty->isSigned())
- C = ConstantSInt::get(Ty, Val);
+ C = ConstantInt::get(Ty, Val);
else {
- C = ConstantSInt::get(Ty->getSignedVersion(), Val);
+ C = ConstantInt::get(Ty->getSignedVersion(), Val);
C = ConstantExpr::getCast(C, Ty);
}
return SCEVUnknown::get(C);
/// getNegativeSCEV - Return a SCEV corresponding to -V = -1*V
///
-static SCEVHandle getNegativeSCEV(const SCEVHandle &V) {
+SCEVHandle SCEV::getNegativeSCEV(const SCEVHandle &V) {
if (SCEVConstant *VC = dyn_cast<SCEVConstant>(V))
return SCEVUnknown::get(ConstantExpr::getNeg(VC->getValue()));
-
+
return SCEVMulExpr::get(V, SCEVUnknown::getIntegerSCEV(-1, V->getType()));
}
/// getMinusSCEV - Return a SCEV corresponding to LHS - RHS.
///
-static SCEVHandle getMinusSCEV(const SCEVHandle &LHS, const SCEVHandle &RHS) {
+SCEVHandle SCEV::getMinusSCEV(const SCEVHandle &LHS, const SCEVHandle &RHS) {
// X - Y --> X + -Y
- return SCEVAddExpr::get(LHS, getNegativeSCEV(RHS));
+ return SCEVAddExpr::get(LHS, SCEV::getNegativeSCEV(RHS));
}
-/// Binomial - Evaluate N!/((N-M)!*M!) . Note that N is often large and M is
-/// often very small, so we try to reduce the number of N! terms we need to
-/// evaluate by evaluating this as (N!/(N-M)!)/M!
-static ConstantInt *Binomial(ConstantInt *N, unsigned M) {
- uint64_t NVal = N->getRawValue();
- uint64_t FirstTerm = 1;
- for (unsigned i = 0; i != M; ++i)
- FirstTerm *= NVal-i;
-
- unsigned MFactorial = 1;
- for (; M; --M)
- MFactorial *= M;
-
- Constant *Result = ConstantUInt::get(Type::ULongTy, FirstTerm/MFactorial);
- Result = ConstantExpr::getCast(Result, N->getType());
- assert(isa<ConstantInt>(Result) && "Cast of integer not folded??");
- return cast<ConstantInt>(Result);
-}
-
/// PartialFact - Compute V!/(V-NumSteps)!
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<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);
+ Constant *Res = ConstantInt::get(Type::ULongTy, Result);
return SCEVUnknown::get(ConstantExpr::getCast(Res, V->getType()));
}
const Type *Ty = V->getType();
if (NumSteps == 0)
return SCEVUnknown::getIntegerSCEV(1, Ty);
-
+
SCEVHandle Result = V;
for (unsigned i = 1; i != NumSteps; ++i)
- Result = SCEVMulExpr::get(Result, getMinusSCEV(V,
+ Result = SCEVMulExpr::get(Result, SCEV::getMinusSCEV(V,
SCEVUnknown::getIntegerSCEV(i, Ty)));
return Result;
}
for (unsigned i = 1, e = getNumOperands(); i != e; ++i) {
SCEVHandle BC = PartialFact(It, i);
Divisor *= i;
- SCEVHandle Val = SCEVUDivExpr::get(SCEVMulExpr::get(BC, getOperand(i)),
+ SCEVHandle Val = SCEVSDivExpr::get(SCEVMulExpr::get(BC, getOperand(i)),
SCEVUnknown::getIntegerSCEV(Divisor,Ty));
Result = SCEVAddExpr::get(Result, Val);
}
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;
}
// 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;
}
}
if (Ops.size() == 1) return Ops[0];
-
+
// Okay, check to see if the same value occurs in the operand list twice. If
// so, merge them together into an multiply expression. Since we sorted the
// list, these values are required to be adjacent.
Ops.push_back(OuterMul);
return SCEVAddExpr::get(Ops);
}
-
+
// Check this multiply against other multiplies being added together.
for (unsigned OtherMulIdx = Idx+1;
OtherMulIdx < Ops.size() && isa<SCEVMulExpr>(Ops[OtherMulIdx]);
// 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;
}
if (Ops.size() == 1)
return Ops[0];
-
+
// If there are mul operands inline them all into this expression.
if (Idx < Ops.size()) {
bool DeletedMul = false;
// 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 SCEVUDivExpr::get(const SCEVHandle &LHS, const SCEVHandle &RHS) {
+SCEVHandle SCEVSDivExpr::get(const SCEVHandle &LHS, const SCEVHandle &RHS) {
if (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS)) {
if (RHSC->getValue()->equalsInt(1))
- return LHS; // X /u 1 --> x
+ return LHS; // X /s 1 --> x
if (RHSC->getValue()->isAllOnesValue())
- return getNegativeSCEV(LHS); // X /u -1 --> -x
+ return SCEV::getNegativeSCEV(LHS); // X /s -1 --> -x
if (SCEVConstant *LHSC = dyn_cast<SCEVConstant>(LHS)) {
Constant *LHSCV = LHSC->getValue();
Constant *RHSCV = RHSC->getValue();
- if (LHSCV->getType()->isSigned())
+ if (LHSCV->getType()->isUnsigned())
LHSCV = ConstantExpr::getCast(LHSCV,
- LHSCV->getType()->getUnsignedVersion());
- if (RHSCV->getType()->isSigned())
+ LHSCV->getType()->getSignedVersion());
+ if (RHSCV->getType()->isUnsigned())
RHSCV = ConstantExpr::getCast(RHSCV, LHSCV->getType());
return SCEVUnknown::get(ConstantExpr::getDiv(LHSCV, RHSCV));
}
// FIXME: implement folding of (X*4)/4 when we know X*4 doesn't overflow.
- SCEVUDivExpr *&Result = SCEVUDivs[std::make_pair(LHS, RHS)];
- if (Result == 0) Result = new SCEVUDivExpr(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;
/// properties. An instruction maps to null if we are unable to compute its
/// exit value.
std::map<PHINode*, Constant*> ConstantEvolutionLoopExitValue;
-
+
public:
ScalarEvolutionsImpl(Function &f, LoopInfo &li)
: F(f), LI(li), UnknownValue(new SCEVCouldNotCompute()) {}
/// expression and create a new one.
SCEVHandle getSCEV(Value *V);
+ /// hasSCEV - Return true if the SCEV for this value has already been
+ /// computed.
+ bool hasSCEV(Value *V) const {
+ return Scalars.count(V);
+ }
+
+ /// setSCEV - Insert the specified SCEV into the map of current SCEVs for
+ /// the specified value.
+ void setSCEV(Value *V, const SCEVHandle &H) {
+ bool isNew = Scalars.insert(std::make_pair(V, H)).second;
+ assert(isNew && "This entry already existed!");
+ }
+
+
/// getSCEVAtScope - Compute the value of the specified expression within
/// the indicated loop (which may be null to indicate in no loop). If the
/// expression cannot be evaluated, return UnknownValue itself.
/// HowFarToZero - Return the number of times a backedge comparing the
/// specified value to zero will execute. If not computable, return
- /// UnknownValue
+ /// UnknownValue.
SCEVHandle HowFarToZero(SCEV *V, const Loop *L);
/// HowFarToNonZero - Return the number of times a backedge checking the
/// specified value for nonzero will execute. If not computable, return
- /// UnknownValue
+ /// UnknownValue.
SCEVHandle HowFarToNonZero(SCEV *V, const Loop *L);
+ /// HowManyLessThans - Return the number of times a backedge containing the
+ /// specified less-than comparison will execute. If not computable, return
+ /// UnknownValue.
+ SCEVHandle HowManyLessThans(SCEV *LHS, SCEV *RHS, const Loop *L);
+
/// getConstantEvolutionLoopExitValue - If we know that the specified Phi is
/// in the header of its containing loop, we know the loop executes a
/// constant number of times, and the PHI node is just a recurrence
// from outside the loop, and one from inside.
unsigned IncomingEdge = L->contains(PN->getIncomingBlock(0));
unsigned BackEdge = IncomingEdge^1;
-
+
// While we are analyzing this PHI node, handle its value symbolically.
SCEVHandle SymbolicName = SCEVUnknown::get(PN);
assert(Scalars.find(PN) == Scalars.end() &&
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 SymbolicName;
}
-
+
// If it's not a loop phi, we can't handle it yet.
return SCEVUnknown::get(PN);
}
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.
return SCEVMulExpr::get(getSCEV(I->getOperand(0)),
getSCEV(I->getOperand(1)));
case Instruction::Div:
- if (V->getType()->isInteger() && V->getType()->isUnsigned())
- return SCEVUDivExpr::get(getSCEV(I->getOperand(0)),
+ if (V->getType()->isInteger() && V->getType()->isSigned())
+ return SCEVSDivExpr::get(getSCEV(I->getOperand(0)),
getSCEV(I->getOperand(1)));
break;
case Instruction::Sub:
- return getMinusSCEV(getSCEV(I->getOperand(0)), getSCEV(I->getOperand(1)));
+ return SCEV::getMinusSCEV(getSCEV(I->getOperand(0)),
+ getSCEV(I->getOperand(1)));
case Instruction::Shl:
// Turn shift left of a constant amount into a multiply.
}
break;
- case Instruction::Shr:
- if (ConstantUInt *SA = dyn_cast<ConstantUInt>(I->getOperand(1)))
- if (V->getType()->isUnsigned()) {
- Constant *X = ConstantInt::get(V->getType(), 1);
- X = ConstantExpr::getShl(X, SA);
- return SCEVUDivExpr::get(getSCEV(I->getOperand(0)), getSCEV(X));
- }
- break;
-
case Instruction::Cast:
return createNodeForCast(cast<CastInst>(I));
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()) {
Constant *NewU = ConstantExpr::getCast(CompRange.getUpper(), NewTy);
CompRange = ConstantRange(NewL, NewU);
}
-
+
SCEVHandle Ret = AddRec->getNumIterationsInRange(CompRange);
if (!isa<SCEVCouldNotCompute>(Ret)) return Ret;
}
}
-
+
switch (Cond) {
case Instruction::SetNE: // while (X != Y)
// Convert to: while (X-Y != 0)
if (LHS->getType()->isInteger()) {
- SCEVHandle TC = HowFarToZero(getMinusSCEV(LHS, RHS), L);
+ SCEVHandle TC = HowFarToZero(SCEV::getMinusSCEV(LHS, RHS), L);
if (!isa<SCEVCouldNotCompute>(TC)) return TC;
}
break;
case Instruction::SetEQ:
// Convert to: while (X-Y == 0) // while (X == Y)
if (LHS->getType()->isInteger()) {
- SCEVHandle TC = HowFarToNonZero(getMinusSCEV(LHS, RHS), L);
+ 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;
+ }
+ 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;
}
break;
/// the addressed element of the initializer or null if the index expression is
/// invalid.
static Constant *
-GetAddressedElementFromGlobal(GlobalVariable *GV,
+GetAddressedElementFromGlobal(GlobalVariable *GV,
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));
/// ComputeLoadConstantCompareIterationCount - Given an exit condition of
/// 'setcc load X, cst', try to se if we can compute the trip count.
SCEVHandle ScalarEvolutionsImpl::
-ComputeLoadConstantCompareIterationCount(LoadInst *LI, Constant *RHS,
+ComputeLoadConstantCompareIterationCount(LoadInst *LI, Constant *RHS,
const Loop *L, unsigned SetCCOpcode) {
if (LI->isVolatile()) return UnknownValue;
unsigned MaxSteps = MaxBruteForceIterations;
for (unsigned IterationNum = 0; IterationNum != MaxSteps; ++IterationNum) {
- ConstantUInt *ItCst =
- ConstantUInt::get(IdxExpr->getType()->getUnsignedVersion(), IterationNum);
+ ConstantInt *ItCst =
+ ConstantInt::get(IdxExpr->getType()->getUnsignedVersion(), IterationNum);
ConstantInt *Val = EvaluateConstantChrecAtConstant(IdxExpr, ItCst);
// Form the GEP offset.
// Evaluate the condition for this iteration.
Result = ConstantExpr::get(SetCCOpcode, 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()
if (isa<BinaryOperator>(I) || isa<ShiftInst>(I) ||
isa<SelectInst>(I) || isa<CastInst>(I) || isa<GetElementPtrInst>(I))
return true;
-
+
if (const CallInst *CI = dyn_cast<CallInst>(I))
if (const Function *F = CI->getCalledFunction())
return canConstantFoldCallTo((Function*)F); // FIXME: elim cast
// If we won't be able to constant fold this expression even if the operands
// are constants, return early.
if (!CanConstantFold(I)) return 0;
-
+
// Otherwise, we can evaluate this instruction if all of its operands are
// constant or derived from a PHI node themselves.
PHINode *PHI = 0;
if (I != ConstantEvolutionLoopExitValue.end())
return I->second;
- if (Its > MaxBruteForceIterations)
+ if (Its > MaxBruteForceIterations)
return ConstantEvolutionLoopExitValue[PN] = 0; // Not going to evaluate it.
Constant *&RetVal = ConstantEvolutionLoopExitValue[PN];
if (CondVal->getValue() == ExitWhen) {
ConstantEvolutionLoopExitValue[PN] = PHIVal;
++NumBruteForceTripCountsComputed;
- return SCEVConstant::get(ConstantUInt::get(Type::UIntTy, IterationNum));
+ return SCEVConstant::get(ConstantInt::get(Type::UIntTy, IterationNum));
}
-
+
// Compute the value of the PHI node for the next iteration.
Constant *NextPHI = EvaluateExpression(BEValue, PHIVal);
if (NextPHI == 0 || NextPHI == PHIVal)
// FIXME: this should be turned into a virtual method on SCEV!
if (isa<SCEVConstant>(V)) return V;
-
+
// If this instruction is evolves from a constant-evolving PHI, compute the
// exit value from the loop without using SCEVs.
if (SCEVUnknown *SU = dyn_cast<SCEVUnknown>(V)) {
// 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);
}
return Comm;
}
- if (SCEVUDivExpr *UDiv = dyn_cast<SCEVUDivExpr>(V)) {
- SCEVHandle LHS = getSCEVAtScope(UDiv->getLHS(), L);
+ if (SCEVSDivExpr *Div = dyn_cast<SCEVSDivExpr>(V)) {
+ SCEVHandle LHS = getSCEVAtScope(Div->getLHS(), L);
if (LHS == UnknownValue) return LHS;
- SCEVHandle RHS = getSCEVAtScope(UDiv->getRHS(), L);
+ SCEVHandle RHS = getSCEVAtScope(Div->getRHS(), L);
if (RHS == UnknownValue) return RHS;
- if (LHS == UDiv->getLHS() && RHS == UDiv->getRHS())
- return UDiv; // must be loop invariant
- return SCEVUDivExpr::get(LHS, RHS);
+ if (LHS == Div->getLHS() && RHS == Div->getRHS())
+ return Div; // must be loop invariant
+ return SCEVSDivExpr::get(LHS, RHS);
}
// If this is a loop recurrence for a loop that does not contain L, then we
if (IterationCount == UnknownValue) return UnknownValue;
IterationCount = getTruncateOrZeroExtend(IterationCount,
AddRec->getType());
-
+
// If the value is affine, simplify the expression evaluation to just
// Start + Step*IterationCount.
if (AddRec->isAffine())
SCEVConstant *L = dyn_cast<SCEVConstant>(AddRec->getOperand(0));
SCEVConstant *M = dyn_cast<SCEVConstant>(AddRec->getOperand(1));
SCEVConstant *N = dyn_cast<SCEVConstant>(AddRec->getOperand(2));
-
+
// We currently can only solve this if the coefficients are constants.
if (!L || !M || !N) {
SCEV *CNC = new SCEVCouldNotCompute();
}
Constant *Two = ConstantInt::get(L->getValue()->getType(), 2);
-
+
// Convert from chrec coefficients to polynomial coefficients AX^2+BX+C
Constant *C = L->getValue();
// The B coefficient is M-N/2
Two));
// The A coefficient is N/2
Constant *A = ConstantExpr::getDiv(N->getValue(), Two);
-
+
// Compute the B^2-4ac term.
Constant *SqrtTerm =
ConstantExpr::getMul(ConstantInt::get(C->getType(), 4),
SqrtTerm = ConstantExpr::getSub(ConstantExpr::getMul(B, B), SqrtTerm);
// Compute floor(sqrt(B^2-4ac))
- ConstantUInt *SqrtVal =
- cast<ConstantUInt>(ConstantExpr::getCast(SqrtTerm,
+ ConstantInt *SqrtVal =
+ cast<ConstantInt>(ConstantExpr::getCast(SqrtTerm,
SqrtTerm->getType()->getUnsignedVersion()));
- uint64_t SqrtValV = SqrtVal->getValue();
+ uint64_t SqrtValV = SqrtVal->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);
+ SqrtVal = ConstantInt::get(Type::ULongTy, SqrtValV2);
SqrtTerm = ConstantExpr::getCast(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);
Constant *Solution2 =
// FIXME: We should add DivExpr and RemExpr operations to our AST.
if (SCEVConstant *StepC = dyn_cast<SCEVConstant>(Step)) {
if (StepC->getValue()->equalsInt(1)) // N % 1 == 0
- return getNegativeSCEV(Start); // 0 - Start/1 == -Start
+ return SCEV::getNegativeSCEV(Start); // 0 - Start/1 == -Start
if (StepC->getValue()->isAllOnesValue()) // N % -1 == 0
return Start; // 0 - Start/-1 == Start
if (ConstantBool *CB =
dyn_cast<ConstantBool>(ConstantExpr::getSetLT(R1->getValue(),
R2->getValue()))) {
- if (CB != ConstantBool::True)
+ 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
// value at this index. When solving for "X*X != 5", for example, we
// should not accept a root of 2.
}
}
}
-
+
return UnknownValue;
}
// Loops that look like: while (X == 0) are very strange indeed. We don't
// handle them yet except for the trivial case. This could be expanded in the
// future as needed.
-
+
// If the value is a constant, check to see if it is known to be non-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)
+ if (NonZero == ConstantBool::getTrue())
return getSCEV(Zero);
return UnknownValue; // Otherwise it will loop infinitely.
}
-
+
// We could implement others, but I really doubt anyone writes loops like
// this, and if they did, they would already be constant folded.
return UnknownValue;
}
+/// HowManyLessThans - Return the number of times a backedge containing the
+/// specified less-than comparison will execute. If not computable, return
+/// UnknownValue.
+SCEVHandle ScalarEvolutionsImpl::
+HowManyLessThans(SCEV *LHS, SCEV *RHS, const Loop *L) {
+ // Only handle: "ADDREC < LoopInvariant".
+ if (!RHS->isLoopInvariant(L)) return UnknownValue;
+
+ SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS);
+ if (!AddRec || AddRec->getLoop() != L)
+ return UnknownValue;
+
+ if (AddRec->isAffine()) {
+ // FORNOW: We only support unit strides.
+ SCEVHandle One = SCEVUnknown::getIntegerSCEV(1, RHS->getType());
+ if (AddRec->getOperand(1) != One)
+ return UnknownValue;
+
+ // The number of iterations for "[n,+,1] < m", is m-n. However, we don't
+ // know that m is >= n on input to the loop. If it is, the condition return
+ // true zero times. What we really should return, for full generality, is
+ // SMAX(0, m-n). Since we cannot check this, we will instead check for a
+ // canonical loop form: most do-loops will have a check that dominates the
+ // loop, that only enters the loop if [n-1]<m. If we can find this check,
+ // we know that the SMAX will evaluate to m-n, because we know that m >= n.
+
+ // Search for the check.
+ BasicBlock *Preheader = L->getLoopPreheader();
+ BasicBlock *PreheaderDest = L->getHeader();
+ if (Preheader == 0) return UnknownValue;
+
+ BranchInst *LoopEntryPredicate =
+ dyn_cast<BranchInst>(Preheader->getTerminator());
+ if (!LoopEntryPredicate) return UnknownValue;
+
+ // This might be a critical edge broken out. If the loop preheader ends in
+ // an unconditional branch to the loop, check to see if the preheader has a
+ // single predecessor, and if so, look for its terminator.
+ while (LoopEntryPredicate->isUnconditional()) {
+ PreheaderDest = Preheader;
+ Preheader = Preheader->getSinglePredecessor();
+ if (!Preheader) return UnknownValue; // Multiple preds.
+
+ LoopEntryPredicate =
+ dyn_cast<BranchInst>(Preheader->getTerminator());
+ if (!LoopEntryPredicate) return UnknownValue;
+ }
+
+ // 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();
+
+ 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'.
+ break;
+ } else {
+ return UnknownValue;
+ }
+ default: break;
+ }
+
+ //std::cerr << "Computed Loop Trip Count as: " <<
+ // *SCEV::getMinusSCEV(RHS, AddRec->getOperand(0)) << "\n";
+ return SCEV::getMinusSCEV(RHS, AddRec->getOperand(0));
+ }
+
+ return UnknownValue;
+}
+
/// getNumIterationsInRange - Return the number of iterations of this loop that
/// produce values in the specified constant range. Another way of looking at
/// this is that it returns the first iteration number where the value is not in
// iteration exits.
ConstantInt *Zero = ConstantInt::get(getType(), 0);
if (!Range.contains(Zero)) return SCEVConstant::get(Zero);
-
+
if (isAffine()) {
// If this is an affine expression then we have this situation:
// Solve {0,+,A} in Range === Ax in Range
// terms of figuring out when zero is crossed, instead of when
// Range.getUpper() is crossed.
std::vector<SCEVHandle> NewOps(op_begin(), op_end());
- NewOps[0] = getNegativeSCEV(SCEVUnknown::get(Range.getUpper()));
+ NewOps[0] = SCEV::getNegativeSCEV(SCEVUnknown::get(Range.getUpper()));
SCEVHandle NewAddRec = SCEVAddRecExpr::get(NewOps, getLoop());
// Next, solve the constructed addrec
if (ConstantBool *CB =
dyn_cast<ConstantBool>(ConstantExpr::getSetLT(R1->getValue(),
R2->getValue()))) {
- if (CB != ConstantBool::True)
+ 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
// not be in the range, but the previous one should be. When solving
// for "X*X < 5", for example, we should not return a root of 2.
Constant *NextVal =
ConstantExpr::getAdd(R1->getValue(),
ConstantInt::get(R1->getType(), 1));
-
+
R1Val = EvaluateConstantChrecAtConstant(this, NextVal);
if (!Range.contains(R1Val))
return SCEVUnknown::get(NextVal);
return new SCEVCouldNotCompute(); // Something strange happened
}
-
+
// If R1 was not in the range, then it is a good return value. Make
// sure that R1-1 WAS in the range though, just in case.
Constant *NextVal =
// Increment to test the next index.
TestVal = cast<ConstantInt>(ConstantExpr::getAdd(TestVal, One));
} while (TestVal != EndVal);
-
+
return new SCEVCouldNotCompute();
}
void ScalarEvolution::getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesAll();
- AU.addRequiredID(LoopSimplifyID);
AU.addRequiredTransitive<LoopInfo>();
}
return ((ScalarEvolutionsImpl*)Impl)->getSCEV(V);
}
+/// hasSCEV - Return true if the SCEV for this value has already been
+/// computed.
+bool ScalarEvolution::hasSCEV(Value *V) const {
+ return ((ScalarEvolutionsImpl*)Impl)->hasSCEV(V);
+}
+
+
+/// setSCEV - Insert the specified SCEV into the map of current SCEVs for
+/// the specified value.
+void ScalarEvolution::setSCEV(Value *V, const SCEVHandle &H) {
+ ((ScalarEvolutionsImpl*)Impl)->setSCEV(V, H);
+}
+
+
SCEVHandle ScalarEvolution::getIterationCount(const Loop *L) const {
return ((ScalarEvolutionsImpl*)Impl)->getIterationCount(L);
}
return ((ScalarEvolutionsImpl*)Impl)->deleteInstructionFromRecords(I);
}
-static void PrintLoopInfo(std::ostream &OS, const ScalarEvolution *SE,
+static void PrintLoopInfo(std::ostream &OS, const ScalarEvolution *SE,
const Loop *L) {
// Print all inner loops first
for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
PrintLoopInfo(OS, SE, *I);
-
+
std::cerr << "Loop " << L->getHeader()->getName() << ": ";
std::vector<BasicBlock*> ExitBlocks;
SCEVHandle SV = getSCEV(&*I);
SV->print(OS);
OS << "\t\t";
-
+
if ((*I).getType()->isIntegral()) {
ConstantRange Bounds = SV->getValueRange();
if (!Bounds.isFullSet())
projects / oota-llvm.git / blobdiff