#include "llvm/GlobalVariable.h"
#include "llvm/Instructions.h"
#include "llvm/Analysis/ConstantFolding.h"
+#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Assembly/Writer.h"
-#include "llvm/Transforms/Scalar.h"
-#include "llvm/Support/CFG.h"
+#include "llvm/Target/TargetData.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/ConstantRange.h"
+#include "llvm/Support/GetElementPtrTypeIterator.h"
#include "llvm/Support/InstIterator.h"
#include "llvm/Support/ManagedStatic.h"
#include "llvm/Support/MathExtras.h"
-#include "llvm/Support/Streams.h"
+#include "llvm/Support/raw_ostream.h"
#include "llvm/ADT/Statistic.h"
-#include <ostream>
+#include "llvm/ADT/STLExtras.h"
#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,
//
SCEV::~SCEV() {}
void SCEV::dump() const {
- print(cerr);
+ print(errs());
+ errs() << '\n';
}
-uint32_t SCEV::getBitWidth() const {
- if (const IntegerType* ITy = dyn_cast<IntegerType>(getType()))
- return ITy->getBitWidth();
- return 0;
+void SCEV::print(std::ostream &o) const {
+ raw_os_ostream OS(o);
+ print(OS);
}
bool SCEV::isZero() const {
return false;
}
+bool SCEV::isOne() const {
+ if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(this))
+ return SC->getValue()->isOne();
+ return false;
+}
SCEVCouldNotCompute::SCEVCouldNotCompute() : SCEV(scCouldNotCompute) {}
+SCEVCouldNotCompute::~SCEVCouldNotCompute() {}
bool SCEVCouldNotCompute::isLoopInvariant(const Loop *L) const {
assert(0 && "Attempt to use a SCEVCouldNotCompute object!");
return this;
}
-void SCEVCouldNotCompute::print(std::ostream &OS) const {
+void SCEVCouldNotCompute::print(raw_ostream &OS) const {
OS << "***COULDNOTCOMPUTE***";
}
const Type *SCEVConstant::getType() const { return V->getType(); }
-void SCEVConstant::print(std::ostream &OS) const {
+void SCEVConstant::print(raw_ostream &OS) const {
WriteAsOperand(OS, V, false);
}
+SCEVCastExpr::SCEVCastExpr(unsigned SCEVTy,
+ const SCEVHandle &op, const Type *ty)
+ : SCEV(SCEVTy), Op(op), Ty(ty) {}
+
+SCEVCastExpr::~SCEVCastExpr() {}
+
+bool SCEVCastExpr::dominates(BasicBlock *BB, DominatorTree *DT) const {
+ return Op->dominates(BB, DT);
+}
+
// 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 ManagedStatic<std::map<std::pair<SCEV*, const Type*>,
+static ManagedStatic<std::map<std::pair<const 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() &&
+ : SCEVCastExpr(scTruncate, op, ty) {
+ assert((Op->getType()->isInteger() || isa<PointerType>(Op->getType())) &&
+ (Ty->isInteger() || isa<PointerType>(Ty)) &&
"Cannot truncate non-integer value!");
- assert(Op->getType()->getPrimitiveSizeInBits() > Ty->getPrimitiveSizeInBits()
- && "This is not a truncating conversion!");
}
SCEVTruncateExpr::~SCEVTruncateExpr() {
SCEVTruncates->erase(std::make_pair(Op, Ty));
}
-void SCEVTruncateExpr::print(std::ostream &OS) const {
- OS << "(truncate " << *Op << " to " << *Ty << ")";
+void SCEVTruncateExpr::print(raw_ostream &OS) const {
+ OS << "(trunc " << *Op->getType() << " " << *Op << " to " << *Ty << ")";
}
// 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 ManagedStatic<std::map<std::pair<SCEV*, const Type*>,
+static ManagedStatic<std::map<std::pair<const SCEV*, const Type*>,
SCEVZeroExtendExpr*> > SCEVZeroExtends;
SCEVZeroExtendExpr::SCEVZeroExtendExpr(const SCEVHandle &op, const Type *ty)
- : SCEV(scZeroExtend), Op(op), Ty(ty) {
- assert(Op->getType()->isInteger() && Ty->isInteger() &&
+ : SCEVCastExpr(scZeroExtend, op, ty) {
+ assert((Op->getType()->isInteger() || isa<PointerType>(Op->getType())) &&
+ (Ty->isInteger() || isa<PointerType>(Ty)) &&
"Cannot zero extend non-integer value!");
- assert(Op->getType()->getPrimitiveSizeInBits() < Ty->getPrimitiveSizeInBits()
- && "This is not an extending conversion!");
}
SCEVZeroExtendExpr::~SCEVZeroExtendExpr() {
SCEVZeroExtends->erase(std::make_pair(Op, Ty));
}
-void SCEVZeroExtendExpr::print(std::ostream &OS) const {
- OS << "(zeroextend " << *Op << " to " << *Ty << ")";
+void SCEVZeroExtendExpr::print(raw_ostream &OS) const {
+ OS << "(zext " << *Op->getType() << " " << *Op << " to " << *Ty << ")";
}
// SCEVSignExtends - Only allow the creation of one SCEVSignExtendExpr for any
// particular input. Don't use a SCEVHandle here, or else the object will never
// be deleted!
-static ManagedStatic<std::map<std::pair<SCEV*, const Type*>,
+static ManagedStatic<std::map<std::pair<const SCEV*, const Type*>,
SCEVSignExtendExpr*> > SCEVSignExtends;
SCEVSignExtendExpr::SCEVSignExtendExpr(const SCEVHandle &op, const Type *ty)
- : SCEV(scSignExtend), Op(op), Ty(ty) {
- assert(Op->getType()->isInteger() && Ty->isInteger() &&
+ : SCEVCastExpr(scSignExtend, op, ty) {
+ assert((Op->getType()->isInteger() || isa<PointerType>(Op->getType())) &&
+ (Ty->isInteger() || isa<PointerType>(Ty)) &&
"Cannot sign extend non-integer value!");
- assert(Op->getType()->getPrimitiveSizeInBits() < Ty->getPrimitiveSizeInBits()
- && "This is not an extending conversion!");
}
SCEVSignExtendExpr::~SCEVSignExtendExpr() {
SCEVSignExtends->erase(std::make_pair(Op, Ty));
}
-void SCEVSignExtendExpr::print(std::ostream &OS) const {
- OS << "(signextend " << *Op << " to " << *Ty << ")";
+void SCEVSignExtendExpr::print(raw_ostream &OS) const {
+ OS << "(sext " << *Op->getType() << " " << *Op << " to " << *Ty << ")";
}
// 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 ManagedStatic<std::map<std::pair<unsigned, std::vector<SCEV*> >,
+static ManagedStatic<std::map<std::pair<unsigned, std::vector<const SCEV*> >,
SCEVCommutativeExpr*> > SCEVCommExprs;
SCEVCommutativeExpr::~SCEVCommutativeExpr() {
- SCEVCommExprs->erase(std::make_pair(getSCEVType(),
- std::vector<SCEV*>(Operands.begin(),
- Operands.end())));
+ std::vector<const SCEV*> SCEVOps(Operands.begin(), Operands.end());
+ SCEVCommExprs->erase(std::make_pair(getSCEVType(), SCEVOps));
}
-void SCEVCommutativeExpr::print(std::ostream &OS) const {
+void SCEVCommutativeExpr::print(raw_ostream &OS) const {
assert(Operands.size() > 1 && "This plus expr shouldn't exist!");
const char *OpStr = getOperationStr();
OS << "(" << *Operands[0];
SCEVHandle H =
getOperand(i)->replaceSymbolicValuesWithConcrete(Sym, Conc, SE);
if (H != getOperand(i)) {
- std::vector<SCEVHandle> NewOps;
+ SmallVector<SCEVHandle, 8> NewOps;
NewOps.reserve(getNumOperands());
for (unsigned j = 0; j != i; ++j)
NewOps.push_back(getOperand(j));
return this;
}
+bool SCEVNAryExpr::dominates(BasicBlock *BB, DominatorTree *DT) const {
+ for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
+ if (!getOperand(i)->dominates(BB, DT))
+ return false;
+ }
+ return true;
+}
+
// SCEVUDivs - Only allow the creation of one SCEVUDivExpr for any particular
// input. Don't use a SCEVHandle here, or else the object will never be
// deleted!
-static ManagedStatic<std::map<std::pair<SCEV*, SCEV*>,
+static ManagedStatic<std::map<std::pair<const SCEV*, const SCEV*>,
SCEVUDivExpr*> > SCEVUDivs;
SCEVUDivExpr::~SCEVUDivExpr() {
SCEVUDivs->erase(std::make_pair(LHS, RHS));
}
-void SCEVUDivExpr::print(std::ostream &OS) const {
+bool SCEVUDivExpr::dominates(BasicBlock *BB, DominatorTree *DT) const {
+ return LHS->dominates(BB, DT) && RHS->dominates(BB, DT);
+}
+
+void SCEVUDivExpr::print(raw_ostream &OS) const {
OS << "(" << *LHS << " /u " << *RHS << ")";
}
const Type *SCEVUDivExpr::getType() const {
- return LHS->getType();
+ // In most cases the types of LHS and RHS will be the same, but in some
+ // crazy cases one or the other may be a pointer. ScalarEvolution doesn't
+ // depend on the type for correctness, but handling types carefully can
+ // avoid extra casts in the SCEVExpander. The LHS is more likely to be
+ // a pointer type than the RHS, so use the RHS' type here.
+ return RHS->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 ManagedStatic<std::map<std::pair<const Loop *, std::vector<SCEV*> >,
+static ManagedStatic<std::map<std::pair<const Loop *,
+ std::vector<const SCEV*> >,
SCEVAddRecExpr*> > SCEVAddRecExprs;
SCEVAddRecExpr::~SCEVAddRecExpr() {
- SCEVAddRecExprs->erase(std::make_pair(L,
- std::vector<SCEV*>(Operands.begin(),
- Operands.end())));
+ std::vector<const SCEV*> SCEVOps(Operands.begin(), Operands.end());
+ SCEVAddRecExprs->erase(std::make_pair(L, SCEVOps));
}
SCEVHandle SCEVAddRecExpr::
SCEVHandle H =
getOperand(i)->replaceSymbolicValuesWithConcrete(Sym, Conc, SE);
if (H != getOperand(i)) {
- std::vector<SCEVHandle> NewOps;
+ SmallVector<SCEVHandle, 8> NewOps;
NewOps.reserve(getNumOperands());
for (unsigned j = 0; j != i; ++j)
NewOps.push_back(getOperand(j));
bool SCEVAddRecExpr::isLoopInvariant(const Loop *QueryLoop) const {
// This recurrence is invariant w.r.t to QueryLoop iff QueryLoop doesn't
// contain L and if the start is invariant.
- return !QueryLoop->contains(L->getHeader()) &&
+ // Add recurrences are never invariant in the function-body (null loop).
+ return QueryLoop &&
+ !QueryLoop->contains(L->getHeader()) &&
getOperand(0)->isLoopInvariant(QueryLoop);
}
-void SCEVAddRecExpr::print(std::ostream &OS) const {
+void SCEVAddRecExpr::print(raw_ostream &OS) const {
OS << "{" << *Operands[0];
for (unsigned i = 1, e = Operands.size(); i != e; ++i)
OS << ",+," << *Operands[i];
bool SCEVUnknown::isLoopInvariant(const Loop *L) const {
// All non-instruction values are loop invariant. All instructions are loop
// invariant if they are not contained in the specified loop.
+ // Instructions are never considered invariant in the function body
+ // (null loop) because they are defined within the "loop".
if (Instruction *I = dyn_cast<Instruction>(V))
- return !L->contains(I->getParent());
+ return L && !L->contains(I->getParent());
+ return true;
+}
+
+bool SCEVUnknown::dominates(BasicBlock *BB, DominatorTree *DT) const {
+ if (Instruction *I = dyn_cast<Instruction>(getValue()))
+ return DT->dominates(I->getParent(), BB);
return true;
}
return V->getType();
}
-void SCEVUnknown::print(std::ostream &OS) const {
+void SCEVUnknown::print(raw_ostream &OS) const {
WriteAsOperand(OS, V, false);
}
/// 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 VISIBILITY_HIDDEN SCEVComplexityCompare {
+ class VISIBILITY_HIDDEN SCEVComplexityCompare {
+ LoopInfo *LI;
+ public:
+ explicit SCEVComplexityCompare(LoopInfo *li) : LI(li) {}
+
bool operator()(const SCEV *LHS, const SCEV *RHS) const {
- return LHS->getSCEVType() < RHS->getSCEVType();
+ // Primarily, sort the SCEVs by their getSCEVType().
+ if (LHS->getSCEVType() != RHS->getSCEVType())
+ return LHS->getSCEVType() < RHS->getSCEVType();
+
+ // Aside from the getSCEVType() ordering, the particular ordering
+ // isn't very important except that it's beneficial to be consistent,
+ // so that (a + b) and (b + a) don't end up as different expressions.
+
+ // Sort SCEVUnknown values with some loose heuristics. TODO: This is
+ // not as complete as it could be.
+ if (const SCEVUnknown *LU = dyn_cast<SCEVUnknown>(LHS)) {
+ const SCEVUnknown *RU = cast<SCEVUnknown>(RHS);
+
+ // Order pointer values after integer values. This helps SCEVExpander
+ // form GEPs.
+ if (isa<PointerType>(LU->getType()) && !isa<PointerType>(RU->getType()))
+ return false;
+ if (isa<PointerType>(RU->getType()) && !isa<PointerType>(LU->getType()))
+ return true;
+
+ // Compare getValueID values.
+ if (LU->getValue()->getValueID() != RU->getValue()->getValueID())
+ return LU->getValue()->getValueID() < RU->getValue()->getValueID();
+
+ // Sort arguments by their position.
+ if (const Argument *LA = dyn_cast<Argument>(LU->getValue())) {
+ const Argument *RA = cast<Argument>(RU->getValue());
+ return LA->getArgNo() < RA->getArgNo();
+ }
+
+ // For instructions, compare their loop depth, and their opcode.
+ // This is pretty loose.
+ if (Instruction *LV = dyn_cast<Instruction>(LU->getValue())) {
+ Instruction *RV = cast<Instruction>(RU->getValue());
+
+ // Compare loop depths.
+ if (LI->getLoopDepth(LV->getParent()) !=
+ LI->getLoopDepth(RV->getParent()))
+ return LI->getLoopDepth(LV->getParent()) <
+ LI->getLoopDepth(RV->getParent());
+
+ // Compare opcodes.
+ if (LV->getOpcode() != RV->getOpcode())
+ return LV->getOpcode() < RV->getOpcode();
+
+ // Compare the number of operands.
+ if (LV->getNumOperands() != RV->getNumOperands())
+ return LV->getNumOperands() < RV->getNumOperands();
+ }
+
+ return false;
+ }
+
+ // Compare constant values.
+ if (const SCEVConstant *LC = dyn_cast<SCEVConstant>(LHS)) {
+ const SCEVConstant *RC = cast<SCEVConstant>(RHS);
+ return LC->getValue()->getValue().ult(RC->getValue()->getValue());
+ }
+
+ // Compare addrec loop depths.
+ if (const SCEVAddRecExpr *LA = dyn_cast<SCEVAddRecExpr>(LHS)) {
+ const SCEVAddRecExpr *RA = cast<SCEVAddRecExpr>(RHS);
+ if (LA->getLoop()->getLoopDepth() != RA->getLoop()->getLoopDepth())
+ return LA->getLoop()->getLoopDepth() < RA->getLoop()->getLoopDepth();
+ }
+
+ // Lexicographically compare n-ary expressions.
+ if (const SCEVNAryExpr *LC = dyn_cast<SCEVNAryExpr>(LHS)) {
+ const SCEVNAryExpr *RC = cast<SCEVNAryExpr>(RHS);
+ for (unsigned i = 0, e = LC->getNumOperands(); i != e; ++i) {
+ if (i >= RC->getNumOperands())
+ return false;
+ if (operator()(LC->getOperand(i), RC->getOperand(i)))
+ return true;
+ if (operator()(RC->getOperand(i), LC->getOperand(i)))
+ return false;
+ }
+ return LC->getNumOperands() < RC->getNumOperands();
+ }
+
+ // Lexicographically compare udiv expressions.
+ if (const SCEVUDivExpr *LC = dyn_cast<SCEVUDivExpr>(LHS)) {
+ const SCEVUDivExpr *RC = cast<SCEVUDivExpr>(RHS);
+ if (operator()(LC->getLHS(), RC->getLHS()))
+ return true;
+ if (operator()(RC->getLHS(), LC->getLHS()))
+ return false;
+ if (operator()(LC->getRHS(), RC->getRHS()))
+ return true;
+ if (operator()(RC->getRHS(), LC->getRHS()))
+ return false;
+ return false;
+ }
+
+ // Compare cast expressions by operand.
+ if (const SCEVCastExpr *LC = dyn_cast<SCEVCastExpr>(LHS)) {
+ const SCEVCastExpr *RC = cast<SCEVCastExpr>(RHS);
+ return operator()(LC->getOperand(), RC->getOperand());
+ }
+
+ assert(0 && "Unknown SCEV kind!");
+ return false;
}
};
}
/// this to depend on where the addresses of various SCEV objects happened to
/// land in memory.
///
-static void GroupByComplexity(std::vector<SCEVHandle> &Ops) {
+static void GroupByComplexity(SmallVectorImpl<SCEVHandle> &Ops,
+ LoopInfo *LI) {
if (Ops.size() < 2) return; // Noop
if (Ops.size() == 2) {
// This is the common case, which also happens to be trivially simple.
// Special case it.
- if (SCEVComplexityCompare()(Ops[1], Ops[0]))
+ if (SCEVComplexityCompare(LI)(Ops[1], Ops[0]))
std::swap(Ops[0], Ops[1]);
return;
}
// Do the rough sort by complexity.
- std::sort(Ops.begin(), Ops.end(), SCEVComplexityCompare());
+ std::stable_sort(Ops.begin(), Ops.end(), SCEVComplexityCompare(LI));
// Now that we are sorted by complexity, group elements of the same
// complexity. Note that this is, at worst, N^2, but the vector is likely to
// be extremely short in practice. Note that we take this approach because we
// do not want to depend on the addresses of the objects we are grouping.
for (unsigned i = 0, e = Ops.size(); i != e-2; ++i) {
- SCEV *S = Ops[i];
+ const SCEV *S = Ops[i];
unsigned Complexity = S->getSCEVType();
// If there are any objects of the same complexity and same value as this
// Simple SCEV method implementations
//===----------------------------------------------------------------------===//
-/// getIntegerSCEV - Given an integer or FP type, create a constant for the
-/// specified signed integer value and return a SCEV for the constant.
-SCEVHandle ScalarEvolution::getIntegerSCEV(int Val, const Type *Ty) {
- Constant *C;
- if (Val == 0)
- C = Constant::getNullValue(Ty);
- else if (Ty->isFloatingPoint())
- C = ConstantFP::get(APFloat(Ty==Type::FloatTy ? APFloat::IEEEsingle :
- APFloat::IEEEdouble, Val));
- else
- C = ConstantInt::get(Ty, Val);
- return getUnknown(C);
-}
-
-/// getNegativeSCEV - Return a SCEV corresponding to -V = -1*V
-///
-SCEVHandle ScalarEvolution::getNegativeSCEV(const SCEVHandle &V) {
- if (SCEVConstant *VC = dyn_cast<SCEVConstant>(V))
- return getUnknown(ConstantExpr::getNeg(VC->getValue()));
-
- return getMulExpr(V, getConstant(ConstantInt::getAllOnesValue(V->getType())));
-}
-
-/// getNotSCEV - Return a SCEV corresponding to ~V = -1-V
-SCEVHandle ScalarEvolution::getNotSCEV(const SCEVHandle &V) {
- if (SCEVConstant *VC = dyn_cast<SCEVConstant>(V))
- return getUnknown(ConstantExpr::getNot(VC->getValue()));
-
- SCEVHandle AllOnes = getConstant(ConstantInt::getAllOnesValue(V->getType()));
- return getMinusSCEV(AllOnes, V);
-}
-
-/// getMinusSCEV - Return a SCEV corresponding to LHS - RHS.
-///
-SCEVHandle ScalarEvolution::getMinusSCEV(const SCEVHandle &LHS,
- const SCEVHandle &RHS) {
- // X - Y --> X + -Y
- return getAddExpr(LHS, getNegativeSCEV(RHS));
-}
-
-
/// BinomialCoefficient - Compute BC(It, K). The result has width W.
-// Assume, K > 0.
+/// Assume, K > 0.
static SCEVHandle BinomialCoefficient(SCEVHandle It, unsigned K,
ScalarEvolution &SE,
- const IntegerType* ResultTy) {
+ const Type* ResultTy) {
// Handle the simplest case efficiently.
if (K == 1)
return SE.getTruncateOrZeroExtend(It, ResultTy);
// Protection from insane SCEVs; this bound is conservative,
// but it probably doesn't matter.
if (K > 1000)
- return new SCEVCouldNotCompute();
+ return SE.getCouldNotCompute();
- unsigned W = ResultTy->getBitWidth();
+ unsigned W = SE.getTypeSizeInBits(ResultTy);
// Calculate K! / 2^T and T; we divide out the factors of two before
// multiplying for calculating K! / 2^T to avoid overflow.
}
// We need at least W + T bits for the multiplication step
- // FIXME: A temporary hack; we round up the bitwidths
- // to the nearest power of 2 to be nice to the code generator.
- unsigned CalculationBits = 1U << Log2_32_Ceil(W + T);
- // FIXME: Temporary hack to avoid generating integers that are too wide.
- // Although, it's not completely clear how to determine how much
- // widening is safe; for example, on X86, we can't really widen
- // beyond 64 because we need to be able to do multiplication
- // that's CalculationBits wide, but on X86-64, we can safely widen up to
- // 128 bits.
- if (CalculationBits > 64)
- return new SCEVCouldNotCompute();
+ unsigned CalculationBits = W + T;
// Calcuate 2^T, at width T+W.
APInt DivFactor = APInt(CalculationBits, 1).shl(T);
// The computation is correct in the face of overflow provided that the
// multiplication is performed _after_ the evaluation of the binomial
// coefficient.
- SCEVHandle Coeff = BinomialCoefficient(It, i, SE,
- cast<IntegerType>(getType()));
+ SCEVHandle Coeff = BinomialCoefficient(It, i, SE, getType());
if (isa<SCEVCouldNotCompute>(Coeff))
return Coeff;
// SCEV Expression folder implementations
//===----------------------------------------------------------------------===//
-SCEVHandle ScalarEvolution::getTruncateExpr(const SCEVHandle &Op, const Type *Ty) {
- if (SCEVConstant *SC = dyn_cast<SCEVConstant>(Op))
+SCEVHandle ScalarEvolution::getTruncateExpr(const SCEVHandle &Op,
+ const Type *Ty) {
+ assert(getTypeSizeInBits(Op->getType()) > getTypeSizeInBits(Ty) &&
+ "This is not a truncating conversion!");
+ assert(isSCEVable(Ty) &&
+ "This is not a conversion to a SCEVable type!");
+ Ty = getEffectiveSCEVType(Ty);
+
+ if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op))
return getUnknown(
ConstantExpr::getTrunc(SC->getValue(), Ty));
+ // trunc(trunc(x)) --> trunc(x)
+ if (const SCEVTruncateExpr *ST = dyn_cast<SCEVTruncateExpr>(Op))
+ return getTruncateExpr(ST->getOperand(), Ty);
+
+ // trunc(sext(x)) --> sext(x) if widening or trunc(x) if narrowing
+ if (const SCEVSignExtendExpr *SS = dyn_cast<SCEVSignExtendExpr>(Op))
+ return getTruncateOrSignExtend(SS->getOperand(), Ty);
+
+ // trunc(zext(x)) --> zext(x) if widening or trunc(x) if narrowing
+ if (const SCEVZeroExtendExpr *SZ = dyn_cast<SCEVZeroExtendExpr>(Op))
+ return getTruncateOrZeroExtend(SZ->getOperand(), Ty);
+
// If the input value is a chrec scev made out of constants, truncate
// all of the constants.
- if (SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Op)) {
- std::vector<SCEVHandle> Operands;
+ if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Op)) {
+ SmallVector<SCEVHandle, 4> Operands;
for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i)
- // FIXME: This should allow truncation of other expression types!
- if (isa<SCEVConstant>(AddRec->getOperand(i)))
- Operands.push_back(getTruncateExpr(AddRec->getOperand(i), Ty));
- else
- break;
- if (Operands.size() == AddRec->getNumOperands())
- return getAddRecExpr(Operands, AddRec->getLoop());
+ Operands.push_back(getTruncateExpr(AddRec->getOperand(i), Ty));
+ return getAddRecExpr(Operands, AddRec->getLoop());
}
SCEVTruncateExpr *&Result = (*SCEVTruncates)[std::make_pair(Op, Ty)];
return Result;
}
-SCEVHandle ScalarEvolution::getZeroExtendExpr(const SCEVHandle &Op, const Type *Ty) {
- if (SCEVConstant *SC = dyn_cast<SCEVConstant>(Op))
- return getUnknown(
- ConstantExpr::getZExt(SC->getValue(), Ty));
+SCEVHandle ScalarEvolution::getZeroExtendExpr(const SCEVHandle &Op,
+ const Type *Ty) {
+ assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) &&
+ "This is not an extending conversion!");
+ assert(isSCEVable(Ty) &&
+ "This is not a conversion to a SCEVable type!");
+ Ty = getEffectiveSCEVType(Ty);
- // FIXME: If the input value is a chrec scev, and we can prove that the value
+ if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op)) {
+ const Type *IntTy = getEffectiveSCEVType(Ty);
+ Constant *C = ConstantExpr::getZExt(SC->getValue(), IntTy);
+ if (IntTy != Ty) C = ConstantExpr::getIntToPtr(C, Ty);
+ return getUnknown(C);
+ }
+
+ // zext(zext(x)) --> zext(x)
+ if (const SCEVZeroExtendExpr *SZ = dyn_cast<SCEVZeroExtendExpr>(Op))
+ return getZeroExtendExpr(SZ->getOperand(), Ty);
+
+ // 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
+ // operands (often constants). This allows analysis of something like
// this: for (unsigned char X = 0; X < 100; ++X) { int Y = X; }
+ if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Op))
+ if (AR->isAffine()) {
+ // Check whether the backedge-taken count is SCEVCouldNotCompute.
+ // Note that this serves two purposes: It filters out loops that are
+ // simply not analyzable, and it covers the case where this code is
+ // being called from within backedge-taken count analysis, such that
+ // attempting to ask for the backedge-taken count would likely result
+ // in infinite recursion. In the later case, the analysis code will
+ // cope with a conservative value, and it will take care to purge
+ // that value once it has finished.
+ SCEVHandle MaxBECount = getMaxBackedgeTakenCount(AR->getLoop());
+ if (!isa<SCEVCouldNotCompute>(MaxBECount)) {
+ // Manually compute the final value for AR, checking for
+ // overflow.
+ SCEVHandle Start = AR->getStart();
+ SCEVHandle Step = AR->getStepRecurrence(*this);
+
+ // Check whether the backedge-taken count can be losslessly casted to
+ // the addrec's type. The count is always unsigned.
+ SCEVHandle CastedMaxBECount =
+ getTruncateOrZeroExtend(MaxBECount, Start->getType());
+ SCEVHandle RecastedMaxBECount =
+ getTruncateOrZeroExtend(CastedMaxBECount, MaxBECount->getType());
+ if (MaxBECount == RecastedMaxBECount) {
+ const Type *WideTy =
+ IntegerType::get(getTypeSizeInBits(Start->getType()) * 2);
+ // Check whether Start+Step*MaxBECount has no unsigned overflow.
+ SCEVHandle ZMul =
+ getMulExpr(CastedMaxBECount,
+ getTruncateOrZeroExtend(Step, Start->getType()));
+ SCEVHandle Add = getAddExpr(Start, ZMul);
+ SCEVHandle OperandExtendedAdd =
+ getAddExpr(getZeroExtendExpr(Start, WideTy),
+ getMulExpr(getZeroExtendExpr(CastedMaxBECount, WideTy),
+ getZeroExtendExpr(Step, WideTy)));
+ if (getZeroExtendExpr(Add, WideTy) == OperandExtendedAdd)
+ // Return the expression with the addrec on the outside.
+ return getAddRecExpr(getZeroExtendExpr(Start, Ty),
+ getZeroExtendExpr(Step, Ty),
+ AR->getLoop());
+
+ // Similar to above, only this time treat the step value as signed.
+ // This covers loops that count down.
+ SCEVHandle SMul =
+ getMulExpr(CastedMaxBECount,
+ getTruncateOrSignExtend(Step, Start->getType()));
+ Add = getAddExpr(Start, SMul);
+ OperandExtendedAdd =
+ getAddExpr(getZeroExtendExpr(Start, WideTy),
+ getMulExpr(getZeroExtendExpr(CastedMaxBECount, WideTy),
+ getSignExtendExpr(Step, WideTy)));
+ if (getZeroExtendExpr(Add, WideTy) == OperandExtendedAdd)
+ // Return the expression with the addrec on the outside.
+ return getAddRecExpr(getZeroExtendExpr(Start, Ty),
+ getSignExtendExpr(Step, Ty),
+ AR->getLoop());
+ }
+ }
+ }
SCEVZeroExtendExpr *&Result = (*SCEVZeroExtends)[std::make_pair(Op, Ty)];
if (Result == 0) Result = new SCEVZeroExtendExpr(Op, Ty);
return Result;
}
-SCEVHandle ScalarEvolution::getSignExtendExpr(const SCEVHandle &Op, const Type *Ty) {
- if (SCEVConstant *SC = dyn_cast<SCEVConstant>(Op))
- return getUnknown(
- ConstantExpr::getSExt(SC->getValue(), Ty));
+SCEVHandle ScalarEvolution::getSignExtendExpr(const SCEVHandle &Op,
+ const Type *Ty) {
+ assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) &&
+ "This is not an extending conversion!");
+ assert(isSCEVable(Ty) &&
+ "This is not a conversion to a SCEVable type!");
+ Ty = getEffectiveSCEVType(Ty);
- // FIXME: If the input value is a chrec scev, and we can prove that the value
+ if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op)) {
+ const Type *IntTy = getEffectiveSCEVType(Ty);
+ Constant *C = ConstantExpr::getSExt(SC->getValue(), IntTy);
+ if (IntTy != Ty) C = ConstantExpr::getIntToPtr(C, Ty);
+ return getUnknown(C);
+ }
+
+ // sext(sext(x)) --> sext(x)
+ if (const SCEVSignExtendExpr *SS = dyn_cast<SCEVSignExtendExpr>(Op))
+ return getSignExtendExpr(SS->getOperand(), Ty);
+
+ // If the input value is a chrec scev, and we can prove that the value
// did not overflow the old, smaller, value, we can sign extend all of the
- // operands (often constants). This would allow analysis of something like
+ // operands (often constants). This allows analysis of something like
// this: for (signed char X = 0; X < 100; ++X) { int Y = X; }
+ if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Op))
+ if (AR->isAffine()) {
+ // Check whether the backedge-taken count is SCEVCouldNotCompute.
+ // Note that this serves two purposes: It filters out loops that are
+ // simply not analyzable, and it covers the case where this code is
+ // being called from within backedge-taken count analysis, such that
+ // attempting to ask for the backedge-taken count would likely result
+ // in infinite recursion. In the later case, the analysis code will
+ // cope with a conservative value, and it will take care to purge
+ // that value once it has finished.
+ SCEVHandle MaxBECount = getMaxBackedgeTakenCount(AR->getLoop());
+ if (!isa<SCEVCouldNotCompute>(MaxBECount)) {
+ // Manually compute the final value for AR, checking for
+ // overflow.
+ SCEVHandle Start = AR->getStart();
+ SCEVHandle Step = AR->getStepRecurrence(*this);
+
+ // Check whether the backedge-taken count can be losslessly casted to
+ // the addrec's type. The count is always unsigned.
+ SCEVHandle CastedMaxBECount =
+ getTruncateOrZeroExtend(MaxBECount, Start->getType());
+ SCEVHandle RecastedMaxBECount =
+ getTruncateOrZeroExtend(CastedMaxBECount, MaxBECount->getType());
+ if (MaxBECount == RecastedMaxBECount) {
+ const Type *WideTy =
+ IntegerType::get(getTypeSizeInBits(Start->getType()) * 2);
+ // Check whether Start+Step*MaxBECount has no signed overflow.
+ SCEVHandle SMul =
+ getMulExpr(CastedMaxBECount,
+ getTruncateOrSignExtend(Step, Start->getType()));
+ SCEVHandle Add = getAddExpr(Start, SMul);
+ SCEVHandle OperandExtendedAdd =
+ getAddExpr(getSignExtendExpr(Start, WideTy),
+ getMulExpr(getZeroExtendExpr(CastedMaxBECount, WideTy),
+ getSignExtendExpr(Step, WideTy)));
+ if (getSignExtendExpr(Add, WideTy) == OperandExtendedAdd)
+ // Return the expression with the addrec on the outside.
+ return getAddRecExpr(getSignExtendExpr(Start, Ty),
+ getSignExtendExpr(Step, Ty),
+ AR->getLoop());
+ }
+ }
+ }
SCEVSignExtendExpr *&Result = (*SCEVSignExtends)[std::make_pair(Op, Ty)];
if (Result == 0) Result = new SCEVSignExtendExpr(Op, Ty);
return Result;
}
-/// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion
-/// of the input value to the specified type. If the type must be
-/// extended, it is zero extended.
-SCEVHandle ScalarEvolution::getTruncateOrZeroExtend(const SCEVHandle &V,
- const Type *Ty) {
- const Type *SrcTy = V->getType();
- assert(SrcTy->isInteger() && Ty->isInteger() &&
- "Cannot truncate or zero extend with non-integer arguments!");
- if (SrcTy->getPrimitiveSizeInBits() == Ty->getPrimitiveSizeInBits())
- return V; // No conversion
- if (SrcTy->getPrimitiveSizeInBits() > Ty->getPrimitiveSizeInBits())
- return getTruncateExpr(V, Ty);
- return getZeroExtendExpr(V, Ty);
+/// getAnyExtendExpr - Return a SCEV for the given operand extended with
+/// unspecified bits out to the given type.
+///
+SCEVHandle ScalarEvolution::getAnyExtendExpr(const SCEVHandle &Op,
+ const Type *Ty) {
+ assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) &&
+ "This is not an extending conversion!");
+ assert(isSCEVable(Ty) &&
+ "This is not a conversion to a SCEVable type!");
+ Ty = getEffectiveSCEVType(Ty);
+
+ // Sign-extend negative constants.
+ if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op))
+ if (SC->getValue()->getValue().isNegative())
+ return getSignExtendExpr(Op, Ty);
+
+ // Peel off a truncate cast.
+ if (const SCEVTruncateExpr *T = dyn_cast<SCEVTruncateExpr>(Op)) {
+ SCEVHandle NewOp = T->getOperand();
+ if (getTypeSizeInBits(NewOp->getType()) < getTypeSizeInBits(Ty))
+ return getAnyExtendExpr(NewOp, Ty);
+ return getTruncateOrNoop(NewOp, Ty);
+ }
+
+ // Next try a zext cast. If the cast is folded, use it.
+ SCEVHandle ZExt = getZeroExtendExpr(Op, Ty);
+ if (!isa<SCEVZeroExtendExpr>(ZExt))
+ return ZExt;
+
+ // Next try a sext cast. If the cast is folded, use it.
+ SCEVHandle SExt = getSignExtendExpr(Op, Ty);
+ if (!isa<SCEVSignExtendExpr>(SExt))
+ return SExt;
+
+ // If the expression is obviously signed, use the sext cast value.
+ if (isa<SCEVSMaxExpr>(Op))
+ return SExt;
+
+ // Absent any other information, use the zext cast value.
+ return ZExt;
}
-// get - Get a canonical add expression, or something simpler if possible.
-SCEVHandle ScalarEvolution::getAddExpr(std::vector<SCEVHandle> &Ops) {
+/// CollectAddOperandsWithScales - Process the given Ops list, which is
+/// a list of operands to be added under the given scale, update the given
+/// map. This is a helper function for getAddRecExpr. As an example of
+/// what it does, given a sequence of operands that would form an add
+/// expression like this:
+///
+/// m + n + 13 + (A * (o + p + (B * q + m + 29))) + r + (-1 * r)
+///
+/// where A and B are constants, update the map with these values:
+///
+/// (m, 1+A*B), (n, 1), (o, A), (p, A), (q, A*B), (r, 0)
+///
+/// and add 13 + A*B*29 to AccumulatedConstant.
+/// This will allow getAddRecExpr to produce this:
+///
+/// 13+A*B*29 + n + (m * (1+A*B)) + ((o + p) * A) + (q * A*B)
+///
+/// This form often exposes folding opportunities that are hidden in
+/// the original operand list.
+///
+/// Return true iff it appears that any interesting folding opportunities
+/// may be exposed. This helps getAddRecExpr short-circuit extra work in
+/// the common case where no interesting opportunities are present, and
+/// is also used as a check to avoid infinite recursion.
+///
+static bool
+CollectAddOperandsWithScales(DenseMap<SCEVHandle, APInt> &M,
+ SmallVector<SCEVHandle, 8> &NewOps,
+ APInt &AccumulatedConstant,
+ const SmallVectorImpl<SCEVHandle> &Ops,
+ const APInt &Scale,
+ ScalarEvolution &SE) {
+ bool Interesting = false;
+
+ // Iterate over the add operands.
+ for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
+ const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(Ops[i]);
+ if (Mul && isa<SCEVConstant>(Mul->getOperand(0))) {
+ APInt NewScale =
+ Scale * cast<SCEVConstant>(Mul->getOperand(0))->getValue()->getValue();
+ if (Mul->getNumOperands() == 2 && isa<SCEVAddExpr>(Mul->getOperand(1))) {
+ // A multiplication of a constant with another add; recurse.
+ Interesting |=
+ CollectAddOperandsWithScales(M, NewOps, AccumulatedConstant,
+ cast<SCEVAddExpr>(Mul->getOperand(1))
+ ->getOperands(),
+ NewScale, SE);
+ } else {
+ // A multiplication of a constant with some other value. Update
+ // the map.
+ SmallVector<SCEVHandle, 4> MulOps(Mul->op_begin()+1, Mul->op_end());
+ SCEVHandle Key = SE.getMulExpr(MulOps);
+ std::pair<DenseMap<SCEVHandle, APInt>::iterator, bool> Pair =
+ M.insert(std::make_pair(Key, APInt()));
+ if (Pair.second) {
+ Pair.first->second = NewScale;
+ NewOps.push_back(Pair.first->first);
+ } else {
+ Pair.first->second += NewScale;
+ // The map already had an entry for this value, which may indicate
+ // a folding opportunity.
+ Interesting = true;
+ }
+ }
+ } else if (const SCEVConstant *C = dyn_cast<SCEVConstant>(Ops[i])) {
+ // Pull a buried constant out to the outside.
+ if (Scale != 1 || AccumulatedConstant != 0 || C->isZero())
+ Interesting = true;
+ AccumulatedConstant += Scale * C->getValue()->getValue();
+ } else {
+ // An ordinary operand. Update the map.
+ std::pair<DenseMap<SCEVHandle, APInt>::iterator, bool> Pair =
+ M.insert(std::make_pair(Ops[i], APInt()));
+ if (Pair.second) {
+ Pair.first->second = Scale;
+ NewOps.push_back(Pair.first->first);
+ } else {
+ Pair.first->second += Scale;
+ // The map already had an entry for this value, which may indicate
+ // a folding opportunity.
+ Interesting = true;
+ }
+ }
+ }
+
+ return Interesting;
+}
+
+namespace {
+ struct APIntCompare {
+ bool operator()(const APInt &LHS, const APInt &RHS) const {
+ return LHS.ult(RHS);
+ }
+ };
+}
+
+/// getAddExpr - Get a canonical add expression, or something simpler if
+/// possible.
+SCEVHandle ScalarEvolution::getAddExpr(SmallVectorImpl<SCEVHandle> &Ops) {
assert(!Ops.empty() && "Cannot get empty add!");
if (Ops.size() == 1) return Ops[0];
+#ifndef NDEBUG
+ for (unsigned i = 1, e = Ops.size(); i != e; ++i)
+ assert(getEffectiveSCEVType(Ops[i]->getType()) ==
+ getEffectiveSCEVType(Ops[0]->getType()) &&
+ "SCEVAddExpr operand types don't match!");
+#endif
// Sort by complexity, this groups all similar expression types together.
- GroupByComplexity(Ops);
+ GroupByComplexity(Ops, LI);
// If there are any constants, fold them together.
unsigned Idx = 0;
- if (SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
+ if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
++Idx;
assert(Idx < Ops.size());
- while (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
+ while (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
// We found two constants, fold them together!
- ConstantInt *Fold = ConstantInt::get(LHSC->getValue()->getValue() +
- RHSC->getValue()->getValue());
- Ops[0] = getConstant(Fold);
+ Ops[0] = getConstant(LHSC->getValue()->getValue() +
+ RHSC->getValue()->getValue());
+ if (Ops.size() == 2) return Ops[0];
Ops.erase(Ops.begin()+1); // Erase the folded element
- if (Ops.size() == 1) return Ops[0];
LHSC = cast<SCEVConstant>(Ops[0]);
}
return getAddExpr(Ops);
}
- // Now we know the first non-constant operand. Skip past any cast SCEVs.
+ // Check for truncates. If all the operands are truncated from the same
+ // type, see if factoring out the truncate would permit the result to be
+ // folded. eg., trunc(x) + m*trunc(n) --> trunc(x + trunc(m)*n)
+ // if the contents of the resulting outer trunc fold to something simple.
+ for (; Idx < Ops.size() && isa<SCEVTruncateExpr>(Ops[Idx]); ++Idx) {
+ const SCEVTruncateExpr *Trunc = cast<SCEVTruncateExpr>(Ops[Idx]);
+ const Type *DstType = Trunc->getType();
+ const Type *SrcType = Trunc->getOperand()->getType();
+ SmallVector<SCEVHandle, 8> LargeOps;
+ bool Ok = true;
+ // Check all the operands to see if they can be represented in the
+ // source type of the truncate.
+ for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
+ if (const SCEVTruncateExpr *T = dyn_cast<SCEVTruncateExpr>(Ops[i])) {
+ if (T->getOperand()->getType() != SrcType) {
+ Ok = false;
+ break;
+ }
+ LargeOps.push_back(T->getOperand());
+ } else if (const SCEVConstant *C = dyn_cast<SCEVConstant>(Ops[i])) {
+ // This could be either sign or zero extension, but sign extension
+ // is much more likely to be foldable here.
+ LargeOps.push_back(getSignExtendExpr(C, SrcType));
+ } else if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(Ops[i])) {
+ SmallVector<SCEVHandle, 8> LargeMulOps;
+ for (unsigned j = 0, f = M->getNumOperands(); j != f && Ok; ++j) {
+ if (const SCEVTruncateExpr *T =
+ dyn_cast<SCEVTruncateExpr>(M->getOperand(j))) {
+ if (T->getOperand()->getType() != SrcType) {
+ Ok = false;
+ break;
+ }
+ LargeMulOps.push_back(T->getOperand());
+ } else if (const SCEVConstant *C =
+ dyn_cast<SCEVConstant>(M->getOperand(j))) {
+ // This could be either sign or zero extension, but sign extension
+ // is much more likely to be foldable here.
+ LargeMulOps.push_back(getSignExtendExpr(C, SrcType));
+ } else {
+ Ok = false;
+ break;
+ }
+ }
+ if (Ok)
+ LargeOps.push_back(getMulExpr(LargeMulOps));
+ } else {
+ Ok = false;
+ break;
+ }
+ }
+ if (Ok) {
+ // Evaluate the expression in the larger type.
+ SCEVHandle Fold = getAddExpr(LargeOps);
+ // If it folds to something simple, use it. Otherwise, don't.
+ if (isa<SCEVConstant>(Fold) || isa<SCEVUnknown>(Fold))
+ return getTruncateExpr(Fold, DstType);
+ }
+ }
+
+ // Skip past any other cast SCEVs.
while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scAddExpr)
++Idx;
// If there are add operands they would be next.
if (Idx < Ops.size()) {
bool DeletedAdd = false;
- while (SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[Idx])) {
+ while (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[Idx])) {
// If we have an add, expand the add operands onto the end of the operands
// list.
Ops.insert(Ops.end(), Add->op_begin(), Add->op_end());
while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scMulExpr)
++Idx;
+ // Check to see if there are any folding opportunities present with
+ // operands multiplied by constant values.
+ if (Idx < Ops.size() && isa<SCEVMulExpr>(Ops[Idx])) {
+ uint64_t BitWidth = getTypeSizeInBits(Ty);
+ DenseMap<SCEVHandle, APInt> M;
+ SmallVector<SCEVHandle, 8> NewOps;
+ APInt AccumulatedConstant(BitWidth, 0);
+ if (CollectAddOperandsWithScales(M, NewOps, AccumulatedConstant,
+ Ops, APInt(BitWidth, 1), *this)) {
+ // Some interesting folding opportunity is present, so its worthwhile to
+ // re-generate the operands list. Group the operands by constant scale,
+ // to avoid multiplying by the same constant scale multiple times.
+ std::map<APInt, SmallVector<SCEVHandle, 4>, APIntCompare> MulOpLists;
+ for (SmallVector<SCEVHandle, 8>::iterator I = NewOps.begin(),
+ E = NewOps.end(); I != E; ++I)
+ MulOpLists[M.find(*I)->second].push_back(*I);
+ // Re-generate the operands list.
+ Ops.clear();
+ if (AccumulatedConstant != 0)
+ Ops.push_back(getConstant(AccumulatedConstant));
+ for (std::map<APInt, SmallVector<SCEVHandle, 4>, APIntCompare>::iterator I =
+ MulOpLists.begin(), E = MulOpLists.end(); I != E; ++I)
+ if (I->first != 0)
+ Ops.push_back(getMulExpr(getConstant(I->first), getAddExpr(I->second)));
+ if (Ops.empty())
+ return getIntegerSCEV(0, Ty);
+ if (Ops.size() == 1)
+ return Ops[0];
+ return getAddExpr(Ops);
+ }
+ }
+
// If we are adding something to a multiply expression, make sure the
// something is not already an operand of the multiply. If so, merge it into
// the multiply.
for (; Idx < Ops.size() && isa<SCEVMulExpr>(Ops[Idx]); ++Idx) {
- SCEVMulExpr *Mul = cast<SCEVMulExpr>(Ops[Idx]);
+ const SCEVMulExpr *Mul = cast<SCEVMulExpr>(Ops[Idx]);
for (unsigned MulOp = 0, e = Mul->getNumOperands(); MulOp != e; ++MulOp) {
- SCEV *MulOpSCEV = Mul->getOperand(MulOp);
+ const SCEV *MulOpSCEV = Mul->getOperand(MulOp);
for (unsigned AddOp = 0, e = Ops.size(); AddOp != e; ++AddOp)
- if (MulOpSCEV == Ops[AddOp] && !isa<SCEVConstant>(MulOpSCEV)) {
+ if (MulOpSCEV == Ops[AddOp] && !isa<SCEVConstant>(Ops[AddOp])) {
// Fold W + X + (X * Y * Z) --> W + (X * ((Y*Z)+1))
SCEVHandle InnerMul = Mul->getOperand(MulOp == 0);
if (Mul->getNumOperands() != 2) {
// If the multiply has more than two operands, we must get the
// Y*Z term.
- std::vector<SCEVHandle> MulOps(Mul->op_begin(), Mul->op_end());
+ SmallVector<SCEVHandle, 4> MulOps(Mul->op_begin(), Mul->op_end());
MulOps.erase(MulOps.begin()+MulOp);
InnerMul = getMulExpr(MulOps);
}
for (unsigned OtherMulIdx = Idx+1;
OtherMulIdx < Ops.size() && isa<SCEVMulExpr>(Ops[OtherMulIdx]);
++OtherMulIdx) {
- SCEVMulExpr *OtherMul = cast<SCEVMulExpr>(Ops[OtherMulIdx]);
+ const SCEVMulExpr *OtherMul = cast<SCEVMulExpr>(Ops[OtherMulIdx]);
// If MulOp occurs in OtherMul, we can fold the two multiplies
// together.
for (unsigned OMulOp = 0, e = OtherMul->getNumOperands();
// Fold X + (A*B*C) + (A*D*E) --> X + (A*(B*C+D*E))
SCEVHandle InnerMul1 = Mul->getOperand(MulOp == 0);
if (Mul->getNumOperands() != 2) {
- std::vector<SCEVHandle> MulOps(Mul->op_begin(), Mul->op_end());
+ SmallVector<SCEVHandle, 4> MulOps(Mul->op_begin(), Mul->op_end());
MulOps.erase(MulOps.begin()+MulOp);
InnerMul1 = getMulExpr(MulOps);
}
SCEVHandle InnerMul2 = OtherMul->getOperand(OMulOp == 0);
if (OtherMul->getNumOperands() != 2) {
- std::vector<SCEVHandle> MulOps(OtherMul->op_begin(),
+ SmallVector<SCEVHandle, 4> MulOps(OtherMul->op_begin(),
OtherMul->op_end());
MulOps.erase(MulOps.begin()+OMulOp);
InnerMul2 = getMulExpr(MulOps);
for (; Idx < Ops.size() && isa<SCEVAddRecExpr>(Ops[Idx]); ++Idx) {
// Scan all of the other operands to this add and add them to the vector if
// they are loop invariant w.r.t. the recurrence.
- std::vector<SCEVHandle> LIOps;
- SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(Ops[Idx]);
+ SmallVector<SCEVHandle, 8> LIOps;
+ const SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(Ops[Idx]);
for (unsigned i = 0, e = Ops.size(); i != e; ++i)
if (Ops[i]->isLoopInvariant(AddRec->getLoop())) {
LIOps.push_back(Ops[i]);
// NLI + LI + {Start,+,Step} --> NLI + {LI+Start,+,Step}
LIOps.push_back(AddRec->getStart());
- std::vector<SCEVHandle> AddRecOps(AddRec->op_begin(), AddRec->op_end());
+ SmallVector<SCEVHandle, 4> AddRecOps(AddRec->op_begin(),
+ AddRec->op_end());
AddRecOps[0] = getAddExpr(LIOps);
SCEVHandle NewRec = getAddRecExpr(AddRecOps, AddRec->getLoop());
for (unsigned OtherIdx = Idx+1;
OtherIdx < Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);++OtherIdx)
if (OtherIdx != Idx) {
- SCEVAddRecExpr *OtherAddRec = cast<SCEVAddRecExpr>(Ops[OtherIdx]);
+ const SCEVAddRecExpr *OtherAddRec = cast<SCEVAddRecExpr>(Ops[OtherIdx]);
if (AddRec->getLoop() == OtherAddRec->getLoop()) {
// Other + {A,+,B} + {C,+,D} --> Other + {A+C,+,B+D}
- std::vector<SCEVHandle> NewOps(AddRec->op_begin(), AddRec->op_end());
+ SmallVector<SCEVHandle, 4> NewOps(AddRec->op_begin(), AddRec->op_end());
for (unsigned i = 0, e = OtherAddRec->getNumOperands(); i != e; ++i) {
if (i >= NewOps.size()) {
NewOps.insert(NewOps.end(), OtherAddRec->op_begin()+i,
// 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());
+ std::vector<const SCEV*> SCEVOps(Ops.begin(), Ops.end());
SCEVCommutativeExpr *&Result = (*SCEVCommExprs)[std::make_pair(scAddExpr,
SCEVOps)];
if (Result == 0) Result = new SCEVAddExpr(Ops);
}
-SCEVHandle ScalarEvolution::getMulExpr(std::vector<SCEVHandle> &Ops) {
+/// getMulExpr - Get a canonical multiply expression, or something simpler if
+/// possible.
+SCEVHandle ScalarEvolution::getMulExpr(SmallVectorImpl<SCEVHandle> &Ops) {
assert(!Ops.empty() && "Cannot get empty mul!");
+#ifndef NDEBUG
+ for (unsigned i = 1, e = Ops.size(); i != e; ++i)
+ assert(getEffectiveSCEVType(Ops[i]->getType()) ==
+ getEffectiveSCEVType(Ops[0]->getType()) &&
+ "SCEVMulExpr operand types don't match!");
+#endif
// Sort by complexity, this groups all similar expression types together.
- GroupByComplexity(Ops);
+ GroupByComplexity(Ops, LI);
// If there are any constants, fold them together.
unsigned Idx = 0;
- if (SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
+ if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
// C1*(C2+V) -> C1*C2 + C1*V
if (Ops.size() == 2)
- if (SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[1]))
+ if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[1]))
if (Add->getNumOperands() == 2 &&
isa<SCEVConstant>(Add->getOperand(0)))
return getAddExpr(getMulExpr(LHSC, Add->getOperand(0)),
++Idx;
- while (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
+ while (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
// We found two constants, fold them together!
ConstantInt *Fold = ConstantInt::get(LHSC->getValue()->getValue() *
RHSC->getValue()->getValue());
// If there are mul operands inline them all into this expression.
if (Idx < Ops.size()) {
bool DeletedMul = false;
- while (SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(Ops[Idx])) {
+ while (const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(Ops[Idx])) {
// If we have an mul, expand the mul operands onto the end of the operands
// list.
Ops.insert(Ops.end(), Mul->op_begin(), Mul->op_end());
for (; Idx < Ops.size() && isa<SCEVAddRecExpr>(Ops[Idx]); ++Idx) {
// Scan all of the other operands to this mul and add them to the vector if
// they are loop invariant w.r.t. the recurrence.
- std::vector<SCEVHandle> LIOps;
- SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(Ops[Idx]);
+ SmallVector<SCEVHandle, 8> LIOps;
+ const SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(Ops[Idx]);
for (unsigned i = 0, e = Ops.size(); i != e; ++i)
if (Ops[i]->isLoopInvariant(AddRec->getLoop())) {
LIOps.push_back(Ops[i]);
// If we found some loop invariants, fold them into the recurrence.
if (!LIOps.empty()) {
// NLI * LI * {Start,+,Step} --> NLI * {LI*Start,+,LI*Step}
- std::vector<SCEVHandle> NewOps;
+ SmallVector<SCEVHandle, 4> NewOps;
NewOps.reserve(AddRec->getNumOperands());
if (LIOps.size() == 1) {
- SCEV *Scale = LIOps[0];
+ const SCEV *Scale = LIOps[0];
for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i)
NewOps.push_back(getMulExpr(Scale, AddRec->getOperand(i)));
} else {
for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) {
- std::vector<SCEVHandle> MulOps(LIOps);
+ SmallVector<SCEVHandle, 4> MulOps(LIOps.begin(), LIOps.end());
MulOps.push_back(AddRec->getOperand(i));
NewOps.push_back(getMulExpr(MulOps));
}
for (unsigned OtherIdx = Idx+1;
OtherIdx < Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);++OtherIdx)
if (OtherIdx != Idx) {
- SCEVAddRecExpr *OtherAddRec = cast<SCEVAddRecExpr>(Ops[OtherIdx]);
+ const SCEVAddRecExpr *OtherAddRec = cast<SCEVAddRecExpr>(Ops[OtherIdx]);
if (AddRec->getLoop() == OtherAddRec->getLoop()) {
// F * G --> {A,+,B} * {C,+,D} --> {A*C,+,F*D + G*B + B*D}
- SCEVAddRecExpr *F = AddRec, *G = OtherAddRec;
+ const SCEVAddRecExpr *F = AddRec, *G = OtherAddRec;
SCEVHandle NewStart = getMulExpr(F->getStart(),
G->getStart());
SCEVHandle B = F->getStepRecurrence(*this);
// 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());
+ std::vector<const SCEV*> SCEVOps(Ops.begin(), Ops.end());
SCEVCommutativeExpr *&Result = (*SCEVCommExprs)[std::make_pair(scMulExpr,
SCEVOps)];
if (Result == 0)
return Result;
}
-SCEVHandle ScalarEvolution::getUDivExpr(const SCEVHandle &LHS, const SCEVHandle &RHS) {
- if (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS)) {
+/// getUDivExpr - Get a canonical multiply expression, or something simpler if
+/// possible.
+SCEVHandle ScalarEvolution::getUDivExpr(const SCEVHandle &LHS,
+ const SCEVHandle &RHS) {
+ assert(getEffectiveSCEVType(LHS->getType()) ==
+ getEffectiveSCEVType(RHS->getType()) &&
+ "SCEVUDivExpr operand types don't match!");
+
+ if (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS)) {
if (RHSC->getValue()->equalsInt(1))
return LHS; // X udiv 1 --> x
+ if (RHSC->isZero())
+ return getIntegerSCEV(0, LHS->getType()); // value is undefined
+
+ // Determine if the division can be folded into the operands of
+ // its operands.
+ // TODO: Generalize this to non-constants by using known-bits information.
+ const Type *Ty = LHS->getType();
+ unsigned LZ = RHSC->getValue()->getValue().countLeadingZeros();
+ unsigned MaxShiftAmt = getTypeSizeInBits(Ty) - LZ;
+ // For non-power-of-two values, effectively round the value up to the
+ // nearest power of two.
+ if (!RHSC->getValue()->getValue().isPowerOf2())
+ ++MaxShiftAmt;
+ const IntegerType *ExtTy =
+ IntegerType::get(getTypeSizeInBits(Ty) + MaxShiftAmt);
+ // {X,+,N}/C --> {X/C,+,N/C} if safe and N/C can be folded.
+ if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(LHS))
+ if (const SCEVConstant *Step =
+ dyn_cast<SCEVConstant>(AR->getStepRecurrence(*this)))
+ if (!Step->getValue()->getValue()
+ .urem(RHSC->getValue()->getValue()) &&
+ getZeroExtendExpr(AR, ExtTy) ==
+ getAddRecExpr(getZeroExtendExpr(AR->getStart(), ExtTy),
+ getZeroExtendExpr(Step, ExtTy),
+ AR->getLoop())) {
+ SmallVector<SCEVHandle, 4> Operands;
+ for (unsigned i = 0, e = AR->getNumOperands(); i != e; ++i)
+ Operands.push_back(getUDivExpr(AR->getOperand(i), RHS));
+ return getAddRecExpr(Operands, AR->getLoop());
+ }
+ // (A*B)/C --> A*(B/C) if safe and B/C can be folded.
+ if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(LHS)) {
+ SmallVector<SCEVHandle, 4> Operands;
+ for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i)
+ Operands.push_back(getZeroExtendExpr(M->getOperand(i), ExtTy));
+ if (getZeroExtendExpr(M, ExtTy) == getMulExpr(Operands))
+ // Find an operand that's safely divisible.
+ for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
+ SCEVHandle Op = M->getOperand(i);
+ SCEVHandle Div = getUDivExpr(Op, RHSC);
+ if (!isa<SCEVUDivExpr>(Div) && getMulExpr(Div, RHSC) == Op) {
+ const SmallVectorImpl<SCEVHandle> &MOperands = M->getOperands();
+ Operands = SmallVector<SCEVHandle, 4>(MOperands.begin(),
+ MOperands.end());
+ Operands[i] = Div;
+ return getMulExpr(Operands);
+ }
+ }
+ }
+ // (A+B)/C --> (A/C + B/C) if safe and A/C and B/C can be folded.
+ if (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(LHS)) {
+ SmallVector<SCEVHandle, 4> Operands;
+ for (unsigned i = 0, e = A->getNumOperands(); i != e; ++i)
+ Operands.push_back(getZeroExtendExpr(A->getOperand(i), ExtTy));
+ if (getZeroExtendExpr(A, ExtTy) == getAddExpr(Operands)) {
+ Operands.clear();
+ for (unsigned i = 0, e = A->getNumOperands(); i != e; ++i) {
+ SCEVHandle Op = getUDivExpr(A->getOperand(i), RHS);
+ if (isa<SCEVUDivExpr>(Op) || getMulExpr(Op, RHS) != A->getOperand(i))
+ break;
+ Operands.push_back(Op);
+ }
+ if (Operands.size() == A->getNumOperands())
+ return getAddExpr(Operands);
+ }
+ }
- if (SCEVConstant *LHSC = dyn_cast<SCEVConstant>(LHS)) {
+ // Fold if both operands are constant.
+ if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(LHS)) {
Constant *LHSCV = LHSC->getValue();
Constant *RHSCV = RHSC->getValue();
return getUnknown(ConstantExpr::getUDiv(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);
return Result;
}
-/// SCEVAddRecExpr::get - Get a add recurrence expression for the
-/// specified loop. Simplify the expression as much as possible.
+/// getAddRecExpr - Get an add recurrence expression for the specified loop.
+/// Simplify the expression as much as possible.
SCEVHandle ScalarEvolution::getAddRecExpr(const SCEVHandle &Start,
const SCEVHandle &Step, const Loop *L) {
- std::vector<SCEVHandle> Operands;
+ SmallVector<SCEVHandle, 4> Operands;
Operands.push_back(Start);
- if (SCEVAddRecExpr *StepChrec = dyn_cast<SCEVAddRecExpr>(Step))
+ if (const SCEVAddRecExpr *StepChrec = dyn_cast<SCEVAddRecExpr>(Step))
if (StepChrec->getLoop() == L) {
Operands.insert(Operands.end(), StepChrec->op_begin(),
StepChrec->op_end());
return getAddRecExpr(Operands, L);
}
-/// SCEVAddRecExpr::get - Get a add recurrence expression for the
-/// specified loop. Simplify the expression as much as possible.
-SCEVHandle ScalarEvolution::getAddRecExpr(std::vector<SCEVHandle> &Operands,
- const Loop *L) {
+/// getAddRecExpr - Get an add recurrence expression for the specified loop.
+/// Simplify the expression as much as possible.
+SCEVHandle ScalarEvolution::getAddRecExpr(SmallVectorImpl<SCEVHandle> &Operands,
+ const Loop *L) {
if (Operands.size() == 1) return Operands[0];
+#ifndef NDEBUG
+ for (unsigned i = 1, e = Operands.size(); i != e; ++i)
+ assert(getEffectiveSCEVType(Operands[i]->getType()) ==
+ getEffectiveSCEVType(Operands[0]->getType()) &&
+ "SCEVAddRecExpr operand types don't match!");
+#endif
if (Operands.back()->isZero()) {
Operands.pop_back();
}
// Canonicalize nested AddRecs in by nesting them in order of loop depth.
- if (SCEVAddRecExpr *NestedAR = dyn_cast<SCEVAddRecExpr>(Operands[0])) {
+ if (const SCEVAddRecExpr *NestedAR = dyn_cast<SCEVAddRecExpr>(Operands[0])) {
const Loop* NestedLoop = NestedAR->getLoop();
if (L->getLoopDepth() < NestedLoop->getLoopDepth()) {
- std::vector<SCEVHandle> NestedOperands(NestedAR->op_begin(),
- NestedAR->op_end());
+ SmallVector<SCEVHandle, 4> NestedOperands(NestedAR->op_begin(),
+ NestedAR->op_end());
SCEVHandle NestedARHandle(NestedAR);
Operands[0] = NestedAR->getStart();
NestedOperands[0] = getAddRecExpr(Operands, L);
}
}
- SCEVAddRecExpr *&Result =
- (*SCEVAddRecExprs)[std::make_pair(L, std::vector<SCEV*>(Operands.begin(),
- Operands.end()))];
+ std::vector<const SCEV*> SCEVOps(Operands.begin(), Operands.end());
+ SCEVAddRecExpr *&Result = (*SCEVAddRecExprs)[std::make_pair(L, SCEVOps)];
if (Result == 0) Result = new SCEVAddRecExpr(Operands, L);
return Result;
}
SCEVHandle ScalarEvolution::getSMaxExpr(const SCEVHandle &LHS,
const SCEVHandle &RHS) {
- std::vector<SCEVHandle> Ops;
+ SmallVector<SCEVHandle, 2> Ops;
Ops.push_back(LHS);
Ops.push_back(RHS);
return getSMaxExpr(Ops);
}
-SCEVHandle ScalarEvolution::getSMaxExpr(std::vector<SCEVHandle> Ops) {
+SCEVHandle
+ScalarEvolution::getSMaxExpr(SmallVectorImpl<SCEVHandle> &Ops) {
assert(!Ops.empty() && "Cannot get empty smax!");
if (Ops.size() == 1) return Ops[0];
+#ifndef NDEBUG
+ for (unsigned i = 1, e = Ops.size(); i != e; ++i)
+ assert(getEffectiveSCEVType(Ops[i]->getType()) ==
+ getEffectiveSCEVType(Ops[0]->getType()) &&
+ "SCEVSMaxExpr operand types don't match!");
+#endif
// Sort by complexity, this groups all similar expression types together.
- GroupByComplexity(Ops);
+ GroupByComplexity(Ops, LI);
// If there are any constants, fold them together.
unsigned Idx = 0;
- if (SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
+ if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
++Idx;
assert(Idx < Ops.size());
- while (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
+ while (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
// We found two constants, fold them together!
ConstantInt *Fold = ConstantInt::get(
APIntOps::smax(LHSC->getValue()->getValue(),
// onto our operand list, and recurse to simplify.
if (Idx < Ops.size()) {
bool DeletedSMax = false;
- while (SCEVSMaxExpr *SMax = dyn_cast<SCEVSMaxExpr>(Ops[Idx])) {
+ while (const SCEVSMaxExpr *SMax = dyn_cast<SCEVSMaxExpr>(Ops[Idx])) {
Ops.insert(Ops.end(), SMax->op_begin(), SMax->op_end());
Ops.erase(Ops.begin()+Idx);
DeletedSMax = true;
// Okay, it looks like we really DO need an smax expr. Check to see if we
// already have one, otherwise create a new one.
- std::vector<SCEV*> SCEVOps(Ops.begin(), Ops.end());
+ std::vector<const SCEV*> SCEVOps(Ops.begin(), Ops.end());
SCEVCommutativeExpr *&Result = (*SCEVCommExprs)[std::make_pair(scSMaxExpr,
SCEVOps)];
if (Result == 0) Result = new SCEVSMaxExpr(Ops);
SCEVHandle ScalarEvolution::getUMaxExpr(const SCEVHandle &LHS,
const SCEVHandle &RHS) {
- std::vector<SCEVHandle> Ops;
+ SmallVector<SCEVHandle, 2> Ops;
Ops.push_back(LHS);
Ops.push_back(RHS);
return getUMaxExpr(Ops);
}
-SCEVHandle ScalarEvolution::getUMaxExpr(std::vector<SCEVHandle> Ops) {
+SCEVHandle
+ScalarEvolution::getUMaxExpr(SmallVectorImpl<SCEVHandle> &Ops) {
assert(!Ops.empty() && "Cannot get empty umax!");
if (Ops.size() == 1) return Ops[0];
+#ifndef NDEBUG
+ for (unsigned i = 1, e = Ops.size(); i != e; ++i)
+ assert(getEffectiveSCEVType(Ops[i]->getType()) ==
+ getEffectiveSCEVType(Ops[0]->getType()) &&
+ "SCEVUMaxExpr operand types don't match!");
+#endif
// Sort by complexity, this groups all similar expression types together.
- GroupByComplexity(Ops);
+ GroupByComplexity(Ops, LI);
// If there are any constants, fold them together.
unsigned Idx = 0;
- if (SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
+ if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
++Idx;
assert(Idx < Ops.size());
- while (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
+ while (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
// We found two constants, fold them together!
ConstantInt *Fold = ConstantInt::get(
APIntOps::umax(LHSC->getValue()->getValue(),
// onto our operand list, and recurse to simplify.
if (Idx < Ops.size()) {
bool DeletedUMax = false;
- while (SCEVUMaxExpr *UMax = dyn_cast<SCEVUMaxExpr>(Ops[Idx])) {
+ while (const SCEVUMaxExpr *UMax = dyn_cast<SCEVUMaxExpr>(Ops[Idx])) {
Ops.insert(Ops.end(), UMax->op_begin(), UMax->op_end());
Ops.erase(Ops.begin()+Idx);
DeletedUMax = true;
// Okay, it looks like we really DO need a umax expr. Check to see if we
// already have one, otherwise create a new one.
- std::vector<SCEV*> SCEVOps(Ops.begin(), Ops.end());
+ std::vector<const SCEV*> SCEVOps(Ops.begin(), Ops.end());
SCEVCommutativeExpr *&Result = (*SCEVCommExprs)[std::make_pair(scUMaxExpr,
SCEVOps)];
if (Result == 0) Result = new SCEVUMaxExpr(Ops);
SCEVHandle ScalarEvolution::getUnknown(Value *V) {
if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
return getConstant(CI);
+ if (isa<ConstantPointerNull>(V))
+ return getIntegerSCEV(0, V->getType());
SCEVUnknown *&Result = (*SCEVUnknowns)[V];
if (Result == 0) Result = new SCEVUnknown(V);
return Result;
}
-
-//===----------------------------------------------------------------------===//
-// ScalarEvolutionsImpl Definition and Implementation
//===----------------------------------------------------------------------===//
+// Basic SCEV Analysis and PHI Idiom Recognition Code
//
-/// ScalarEvolutionsImpl - This class implements the main driver for the scalar
-/// evolution code.
-///
-namespace {
- struct VISIBILITY_HIDDEN ScalarEvolutionsImpl {
- /// SE - A reference to the public ScalarEvolution object.
- ScalarEvolution &SE;
- /// F - The function we are analyzing.
- ///
- Function &F;
+/// isSCEVable - Test if values of the given type are analyzable within
+/// the SCEV framework. This primarily includes integer types, and it
+/// can optionally include pointer types if the ScalarEvolution class
+/// has access to target-specific information.
+bool ScalarEvolution::isSCEVable(const Type *Ty) const {
+ // Integers are always SCEVable.
+ if (Ty->isInteger())
+ return true;
- /// LI - The loop information for the function we are currently analyzing.
- ///
- LoopInfo &LI;
+ // Pointers are SCEVable if TargetData information is available
+ // to provide pointer size information.
+ if (isa<PointerType>(Ty))
+ return TD != NULL;
- /// UnknownValue - This SCEV is used to represent unknown trip counts and
- /// things.
- SCEVHandle UnknownValue;
+ // Otherwise it's not SCEVable.
+ return false;
+}
- /// Scalars - This is a cache of the scalars we have analyzed so far.
- ///
- std::map<Value*, SCEVHandle> Scalars;
+/// getTypeSizeInBits - Return the size in bits of the specified type,
+/// for which isSCEVable must return true.
+uint64_t ScalarEvolution::getTypeSizeInBits(const Type *Ty) const {
+ assert(isSCEVable(Ty) && "Type is not SCEVable!");
- /// IterationCounts - Cache the iteration count of the loops for this
- /// function as they are computed.
- std::map<const Loop*, SCEVHandle> IterationCounts;
+ // If we have a TargetData, use it!
+ if (TD)
+ return TD->getTypeSizeInBits(Ty);
- /// ConstantEvolutionLoopExitValue - This map contains entries for all of
- /// the PHI instructions that we attempt to compute constant evolutions for.
- /// This allows us to avoid potentially expensive recomputation of these
- /// properties. An instruction maps to null if we are unable to compute its
- /// exit value.
- std::map<PHINode*, Constant*> ConstantEvolutionLoopExitValue;
+ // Otherwise, we support only integer types.
+ assert(Ty->isInteger() && "isSCEVable permitted a non-SCEVable type!");
+ return Ty->getPrimitiveSizeInBits();
+}
- public:
- ScalarEvolutionsImpl(ScalarEvolution &se, Function &f, LoopInfo &li)
- : SE(se), F(f), LI(li), UnknownValue(new SCEVCouldNotCompute()) {}
+/// getEffectiveSCEVType - Return a type with the same bitwidth as
+/// the given type and which represents how SCEV will treat the given
+/// type, for which isSCEVable must return true. For pointer types,
+/// this is the pointer-sized integer type.
+const Type *ScalarEvolution::getEffectiveSCEVType(const Type *Ty) const {
+ assert(isSCEVable(Ty) && "Type is not SCEVable!");
- /// getSCEV - Return an existing SCEV if it exists, otherwise analyze the
- /// expression and create a new one.
- SCEVHandle getSCEV(Value *V);
+ if (Ty->isInteger())
+ return Ty;
- /// hasSCEV - Return true if the SCEV for this value has already been
- /// computed.
- bool hasSCEV(Value *V) const {
- return Scalars.count(V);
- }
+ assert(isa<PointerType>(Ty) && "Unexpected non-pointer non-integer type!");
+ return TD->getIntPtrType();
+}
- /// 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!");
- isNew = false;
- }
+SCEVHandle ScalarEvolution::getCouldNotCompute() {
+ return CouldNotCompute;
+}
+/// hasSCEV - Return true if the SCEV for this value has already been
+/// computed.
+bool ScalarEvolution::hasSCEV(Value *V) const {
+ return Scalars.count(V);
+}
- /// 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.
- SCEVHandle getSCEVAtScope(SCEV *V, const Loop *L);
-
-
- /// hasLoopInvariantIterationCount - Return true if the specified loop has
- /// an analyzable loop-invariant iteration count.
- bool hasLoopInvariantIterationCount(const Loop *L);
-
- /// getIterationCount - If the specified loop has a predictable iteration
- /// count, return it. Note that it is not valid to call this method on a
- /// loop without a loop-invariant iteration count.
- SCEVHandle getIterationCount(const Loop *L);
-
- /// deleteValueFromRecords - This method should be called by the
- /// client before it removes a value from the program, to make sure
- /// that no dangling references are left around.
- void deleteValueFromRecords(Value *V);
-
- private:
- /// createSCEV - We know that there is no SCEV for the specified value.
- /// Analyze the expression.
- SCEVHandle createSCEV(Value *V);
-
- /// createNodeForPHI - Provide the special handling we need to analyze PHI
- /// SCEVs.
- SCEVHandle createNodeForPHI(PHINode *PN);
-
- /// ReplaceSymbolicValueWithConcrete - This looks up the computed SCEV value
- /// for the specified instruction and replaces any references to the
- /// symbolic value SymName with the specified value. This is used during
- /// PHI resolution.
- void ReplaceSymbolicValueWithConcrete(Instruction *I,
- const SCEVHandle &SymName,
- const SCEVHandle &NewVal);
-
- /// ComputeIterationCount - Compute the number of times the specified loop
- /// will iterate.
- SCEVHandle ComputeIterationCount(const Loop *L);
-
- /// ComputeLoadConstantCompareIterationCount - Given an exit condition of
- /// 'icmp op load X, cst', try to see if we can compute the trip count.
- SCEVHandle ComputeLoadConstantCompareIterationCount(LoadInst *LI,
- Constant *RHS,
- const Loop *L,
- ICmpInst::Predicate p);
-
- /// ComputeIterationCountExhaustively - If the trip is known to execute a
- /// constant number of times (the condition evolves only from constants),
- /// try to evaluate a few iterations of the loop until we get the exit
- /// condition gets a value of ExitWhen (true or false). If we cannot
- /// evaluate the trip count of the loop, return UnknownValue.
- SCEVHandle ComputeIterationCountExhaustively(const Loop *L, Value *Cond,
- bool ExitWhen);
-
- /// HowFarToZero - Return the number of times a backedge comparing the
- /// specified value to zero will execute. If not computable, return
- /// 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.
- 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. isSigned specifies whether the less-than is signed.
- SCEVHandle HowManyLessThans(SCEV *LHS, SCEV *RHS, const Loop *L,
- bool isSigned);
-
- /// getPredecessorWithUniqueSuccessorForBB - Return a predecessor of BB
- /// (which may not be an immediate predecessor) which has exactly one
- /// successor from which BB is reachable, or null if no such block is
- /// found.
- BasicBlock* getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB);
-
- /// executesAtLeastOnce - Test whether entry to the loop is protected by
- /// a conditional between LHS and RHS.
- bool executesAtLeastOnce(const Loop *L, bool isSigned, SCEV *LHS, SCEV *RHS);
-
- /// 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
- /// involving constants, fold it.
- Constant *getConstantEvolutionLoopExitValue(PHINode *PN, const APInt& Its,
- const Loop *L);
- };
+/// getSCEV - Return an existing SCEV if it exists, otherwise analyze the
+/// expression and create a new one.
+SCEVHandle ScalarEvolution::getSCEV(Value *V) {
+ assert(isSCEVable(V->getType()) && "Value is not SCEVable!");
+
+ std::map<SCEVCallbackVH, SCEVHandle>::iterator I = Scalars.find(V);
+ if (I != Scalars.end()) return I->second;
+ SCEVHandle S = createSCEV(V);
+ Scalars.insert(std::make_pair(SCEVCallbackVH(V, this), S));
+ return S;
}
-//===----------------------------------------------------------------------===//
-// Basic SCEV Analysis and PHI Idiom Recognition Code
-//
+/// getIntegerSCEV - Given an integer or FP type, create a constant for the
+/// specified signed integer value and return a SCEV for the constant.
+SCEVHandle ScalarEvolution::getIntegerSCEV(int Val, const Type *Ty) {
+ Ty = getEffectiveSCEVType(Ty);
+ Constant *C;
+ if (Val == 0)
+ C = Constant::getNullValue(Ty);
+ else if (Ty->isFloatingPoint())
+ C = ConstantFP::get(APFloat(Ty==Type::FloatTy ? APFloat::IEEEsingle :
+ APFloat::IEEEdouble, Val));
+ else
+ C = ConstantInt::get(Ty, Val);
+ return getUnknown(C);
+}
-/// deleteValueFromRecords - This method should be called by the
-/// client before it removes an instruction from the program, to make sure
-/// that no dangling references are left around.
-void ScalarEvolutionsImpl::deleteValueFromRecords(Value *V) {
- SmallVector<Value *, 16> Worklist;
+/// getNegativeSCEV - Return a SCEV corresponding to -V = -1*V
+///
+SCEVHandle ScalarEvolution::getNegativeSCEV(const SCEVHandle &V) {
+ if (const SCEVConstant *VC = dyn_cast<SCEVConstant>(V))
+ return getUnknown(ConstantExpr::getNeg(VC->getValue()));
- if (Scalars.erase(V)) {
- if (PHINode *PN = dyn_cast<PHINode>(V))
- ConstantEvolutionLoopExitValue.erase(PN);
- Worklist.push_back(V);
- }
+ const Type *Ty = V->getType();
+ Ty = getEffectiveSCEVType(Ty);
+ return getMulExpr(V, getConstant(ConstantInt::getAllOnesValue(Ty)));
+}
- while (!Worklist.empty()) {
- Value *VV = Worklist.back();
- Worklist.pop_back();
-
- for (Instruction::use_iterator UI = VV->use_begin(), UE = VV->use_end();
- UI != UE; ++UI) {
- Instruction *Inst = cast<Instruction>(*UI);
- if (Scalars.erase(Inst)) {
- if (PHINode *PN = dyn_cast<PHINode>(VV))
- ConstantEvolutionLoopExitValue.erase(PN);
- Worklist.push_back(Inst);
- }
- }
- }
+/// getNotSCEV - Return a SCEV corresponding to ~V = -1-V
+SCEVHandle ScalarEvolution::getNotSCEV(const SCEVHandle &V) {
+ if (const SCEVConstant *VC = dyn_cast<SCEVConstant>(V))
+ return getUnknown(ConstantExpr::getNot(VC->getValue()));
+
+ const Type *Ty = V->getType();
+ Ty = getEffectiveSCEVType(Ty);
+ SCEVHandle AllOnes = getConstant(ConstantInt::getAllOnesValue(Ty));
+ return getMinusSCEV(AllOnes, V);
}
+/// getMinusSCEV - Return a SCEV corresponding to LHS - RHS.
+///
+SCEVHandle ScalarEvolution::getMinusSCEV(const SCEVHandle &LHS,
+ const SCEVHandle &RHS) {
+ // X - Y --> X + -Y
+ return getAddExpr(LHS, getNegativeSCEV(RHS));
+}
-/// getSCEV - Return an existing SCEV if it exists, otherwise analyze the
-/// expression and create a new one.
-SCEVHandle ScalarEvolutionsImpl::getSCEV(Value *V) {
- assert(V->getType() != Type::VoidTy && "Can't analyze void expressions!");
+/// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion of the
+/// input value to the specified type. If the type must be extended, it is zero
+/// extended.
+SCEVHandle
+ScalarEvolution::getTruncateOrZeroExtend(const SCEVHandle &V,
+ const Type *Ty) {
+ const Type *SrcTy = V->getType();
+ assert((SrcTy->isInteger() || (TD && isa<PointerType>(SrcTy))) &&
+ (Ty->isInteger() || (TD && isa<PointerType>(Ty))) &&
+ "Cannot truncate or zero extend with non-integer arguments!");
+ if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty))
+ return V; // No conversion
+ if (getTypeSizeInBits(SrcTy) > getTypeSizeInBits(Ty))
+ return getTruncateExpr(V, Ty);
+ return getZeroExtendExpr(V, Ty);
+}
- std::map<Value*, SCEVHandle>::iterator I = Scalars.find(V);
- if (I != Scalars.end()) return I->second;
- SCEVHandle S = createSCEV(V);
- Scalars.insert(std::make_pair(V, S));
- return S;
+/// getTruncateOrSignExtend - Return a SCEV corresponding to a conversion of the
+/// input value to the specified type. If the type must be extended, it is sign
+/// extended.
+SCEVHandle
+ScalarEvolution::getTruncateOrSignExtend(const SCEVHandle &V,
+ const Type *Ty) {
+ const Type *SrcTy = V->getType();
+ assert((SrcTy->isInteger() || (TD && isa<PointerType>(SrcTy))) &&
+ (Ty->isInteger() || (TD && isa<PointerType>(Ty))) &&
+ "Cannot truncate or zero extend with non-integer arguments!");
+ if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty))
+ return V; // No conversion
+ if (getTypeSizeInBits(SrcTy) > getTypeSizeInBits(Ty))
+ return getTruncateExpr(V, Ty);
+ return getSignExtendExpr(V, Ty);
+}
+
+/// getNoopOrZeroExtend - Return a SCEV corresponding to a conversion of the
+/// input value to the specified type. If the type must be extended, it is zero
+/// extended. The conversion must not be narrowing.
+SCEVHandle
+ScalarEvolution::getNoopOrZeroExtend(const SCEVHandle &V, const Type *Ty) {
+ const Type *SrcTy = V->getType();
+ assert((SrcTy->isInteger() || (TD && isa<PointerType>(SrcTy))) &&
+ (Ty->isInteger() || (TD && isa<PointerType>(Ty))) &&
+ "Cannot noop or zero extend with non-integer arguments!");
+ assert(getTypeSizeInBits(SrcTy) <= getTypeSizeInBits(Ty) &&
+ "getNoopOrZeroExtend cannot truncate!");
+ if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty))
+ return V; // No conversion
+ return getZeroExtendExpr(V, Ty);
+}
+
+/// getNoopOrSignExtend - Return a SCEV corresponding to a conversion of the
+/// input value to the specified type. If the type must be extended, it is sign
+/// extended. The conversion must not be narrowing.
+SCEVHandle
+ScalarEvolution::getNoopOrSignExtend(const SCEVHandle &V, const Type *Ty) {
+ const Type *SrcTy = V->getType();
+ assert((SrcTy->isInteger() || (TD && isa<PointerType>(SrcTy))) &&
+ (Ty->isInteger() || (TD && isa<PointerType>(Ty))) &&
+ "Cannot noop or sign extend with non-integer arguments!");
+ assert(getTypeSizeInBits(SrcTy) <= getTypeSizeInBits(Ty) &&
+ "getNoopOrSignExtend cannot truncate!");
+ if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty))
+ return V; // No conversion
+ return getSignExtendExpr(V, Ty);
+}
+
+/// getNoopOrAnyExtend - Return a SCEV corresponding to a conversion of
+/// the input value to the specified type. If the type must be extended,
+/// it is extended with unspecified bits. The conversion must not be
+/// narrowing.
+SCEVHandle
+ScalarEvolution::getNoopOrAnyExtend(const SCEVHandle &V, const Type *Ty) {
+ const Type *SrcTy = V->getType();
+ assert((SrcTy->isInteger() || (TD && isa<PointerType>(SrcTy))) &&
+ (Ty->isInteger() || (TD && isa<PointerType>(Ty))) &&
+ "Cannot noop or any extend with non-integer arguments!");
+ assert(getTypeSizeInBits(SrcTy) <= getTypeSizeInBits(Ty) &&
+ "getNoopOrAnyExtend cannot truncate!");
+ if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty))
+ return V; // No conversion
+ return getAnyExtendExpr(V, Ty);
+}
+
+/// getTruncateOrNoop - Return a SCEV corresponding to a conversion of the
+/// input value to the specified type. The conversion must not be widening.
+SCEVHandle
+ScalarEvolution::getTruncateOrNoop(const SCEVHandle &V, const Type *Ty) {
+ const Type *SrcTy = V->getType();
+ assert((SrcTy->isInteger() || (TD && isa<PointerType>(SrcTy))) &&
+ (Ty->isInteger() || (TD && isa<PointerType>(Ty))) &&
+ "Cannot truncate or noop with non-integer arguments!");
+ assert(getTypeSizeInBits(SrcTy) >= getTypeSizeInBits(Ty) &&
+ "getTruncateOrNoop cannot extend!");
+ if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty))
+ return V; // No conversion
+ return getTruncateExpr(V, Ty);
}
/// ReplaceSymbolicValueWithConcrete - This looks up the computed SCEV value for
/// the specified instruction and replaces any references to the symbolic value
/// SymName with the specified value. This is used during PHI resolution.
-void ScalarEvolutionsImpl::
+void ScalarEvolution::
ReplaceSymbolicValueWithConcrete(Instruction *I, const SCEVHandle &SymName,
const SCEVHandle &NewVal) {
- std::map<Value*, SCEVHandle>::iterator SI = Scalars.find(I);
+ std::map<SCEVCallbackVH, SCEVHandle>::iterator SI =
+ Scalars.find(SCEVCallbackVH(I, this));
if (SI == Scalars.end()) return;
SCEVHandle NV =
- SI->second->replaceSymbolicValuesWithConcrete(SymName, NewVal, SE);
+ SI->second->replaceSymbolicValuesWithConcrete(SymName, NewVal, *this);
if (NV == SI->second) return; // No change.
SI->second = NV; // Update the scalars map!
/// createNodeForPHI - PHI nodes have two cases. Either the PHI node exists in
/// a loop header, making it a potential recurrence, or it doesn't.
///
-SCEVHandle ScalarEvolutionsImpl::createNodeForPHI(PHINode *PN) {
+SCEVHandle ScalarEvolution::createNodeForPHI(PHINode *PN) {
if (PN->getNumIncomingValues() == 2) // The loops have been canonicalized.
- if (const Loop *L = LI.getLoopFor(PN->getParent()))
+ if (const Loop *L = LI->getLoopFor(PN->getParent()))
if (L->getHeader() == PN->getParent()) {
// If it lives in the loop header, it has two incoming values, one
// from outside the loop, and one from inside.
unsigned BackEdge = IncomingEdge^1;
// While we are analyzing this PHI node, handle its value symbolically.
- SCEVHandle SymbolicName = SE.getUnknown(PN);
+ SCEVHandle SymbolicName = getUnknown(PN);
assert(Scalars.find(PN) == Scalars.end() &&
"PHI node already processed?");
- Scalars.insert(std::make_pair(PN, SymbolicName));
+ Scalars.insert(std::make_pair(SCEVCallbackVH(PN, this), SymbolicName));
// Using this symbolic name for the PHI, analyze the value coming around
// the back-edge.
// If the value coming around the backedge is an add with the symbolic
// value we just inserted, then we found a simple induction variable!
- if (SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(BEValue)) {
+ if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(BEValue)) {
// If there is a single occurrence of the symbolic value, replace it
// with a recurrence.
unsigned FoundIndex = Add->getNumOperands();
if (FoundIndex != Add->getNumOperands()) {
// Create an add with everything but the specified operand.
- std::vector<SCEVHandle> Ops;
+ SmallVector<SCEVHandle, 8> Ops;
for (unsigned i = 0, e = Add->getNumOperands(); i != e; ++i)
if (i != FoundIndex)
Ops.push_back(Add->getOperand(i));
- SCEVHandle Accum = SE.getAddExpr(Ops);
+ SCEVHandle Accum = getAddExpr(Ops);
// This is not a valid addrec if the step amount is varying each
// loop iteration, but is not itself an addrec in this loop.
(isa<SCEVAddRecExpr>(Accum) &&
cast<SCEVAddRecExpr>(Accum)->getLoop() == L)) {
SCEVHandle StartVal = getSCEV(PN->getIncomingValue(IncomingEdge));
- SCEVHandle PHISCEV = SE.getAddRecExpr(StartVal, Accum, L);
+ SCEVHandle PHISCEV = getAddRecExpr(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
return PHISCEV;
}
}
- } else if (SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(BEValue)) {
+ } else if (const 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.
// If StartVal = j.start - j.stride, we can use StartVal as the
// initial step of the addrec evolution.
- if (StartVal == SE.getMinusSCEV(AddRec->getOperand(0),
+ if (StartVal == getMinusSCEV(AddRec->getOperand(0),
AddRec->getOperand(1))) {
SCEVHandle PHISCEV =
- SE.getAddRecExpr(StartVal, AddRec->getOperand(1), L);
+ getAddRecExpr(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
}
// If it's not a loop phi, we can't handle it yet.
- return SE.getUnknown(PN);
+ return getUnknown(PN);
+}
+
+/// createNodeForGEP - Expand GEP instructions into add and multiply
+/// operations. This allows them to be analyzed by regular SCEV code.
+///
+SCEVHandle ScalarEvolution::createNodeForGEP(User *GEP) {
+
+ const Type *IntPtrTy = TD->getIntPtrType();
+ Value *Base = GEP->getOperand(0);
+ // Don't attempt to analyze GEPs over unsized objects.
+ if (!cast<PointerType>(Base->getType())->getElementType()->isSized())
+ return getUnknown(GEP);
+ SCEVHandle TotalOffset = getIntegerSCEV(0, IntPtrTy);
+ gep_type_iterator GTI = gep_type_begin(GEP);
+ for (GetElementPtrInst::op_iterator I = next(GEP->op_begin()),
+ E = GEP->op_end();
+ I != E; ++I) {
+ Value *Index = *I;
+ // Compute the (potentially symbolic) offset in bytes for this index.
+ if (const StructType *STy = dyn_cast<StructType>(*GTI++)) {
+ // For a struct, add the member offset.
+ const StructLayout &SL = *TD->getStructLayout(STy);
+ unsigned FieldNo = cast<ConstantInt>(Index)->getZExtValue();
+ uint64_t Offset = SL.getElementOffset(FieldNo);
+ TotalOffset = getAddExpr(TotalOffset,
+ getIntegerSCEV(Offset, IntPtrTy));
+ } else {
+ // For an array, add the element offset, explicitly scaled.
+ SCEVHandle LocalOffset = getSCEV(Index);
+ if (!isa<PointerType>(LocalOffset->getType()))
+ // Getelementptr indicies are signed.
+ LocalOffset = getTruncateOrSignExtend(LocalOffset,
+ IntPtrTy);
+ LocalOffset =
+ getMulExpr(LocalOffset,
+ getIntegerSCEV(TD->getTypeAllocSize(*GTI),
+ IntPtrTy));
+ TotalOffset = getAddExpr(TotalOffset, LocalOffset);
+ }
+ }
+ return getAddExpr(getSCEV(Base), TotalOffset);
}
/// GetMinTrailingZeros - Determine the minimum number of zero bits that S is
/// guaranteed to end in (at every loop iteration). It is, at the same time,
/// the minimum number of times S is divisible by 2. For example, given {4,+,8}
/// it returns 2. If S is guaranteed to be 0, it returns the bitwidth of S.
-static uint32_t GetMinTrailingZeros(SCEVHandle S) {
- if (SCEVConstant *C = dyn_cast<SCEVConstant>(S))
+static uint32_t GetMinTrailingZeros(SCEVHandle S, const ScalarEvolution &SE) {
+ if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S))
return C->getValue()->getValue().countTrailingZeros();
- if (SCEVTruncateExpr *T = dyn_cast<SCEVTruncateExpr>(S))
- return std::min(GetMinTrailingZeros(T->getOperand()), T->getBitWidth());
+ if (const SCEVTruncateExpr *T = dyn_cast<SCEVTruncateExpr>(S))
+ return std::min(GetMinTrailingZeros(T->getOperand(), SE),
+ (uint32_t)SE.getTypeSizeInBits(T->getType()));
- if (SCEVZeroExtendExpr *E = dyn_cast<SCEVZeroExtendExpr>(S)) {
- uint32_t OpRes = GetMinTrailingZeros(E->getOperand());
- return OpRes == E->getOperand()->getBitWidth() ? E->getBitWidth() : OpRes;
+ if (const SCEVZeroExtendExpr *E = dyn_cast<SCEVZeroExtendExpr>(S)) {
+ uint32_t OpRes = GetMinTrailingZeros(E->getOperand(), SE);
+ return OpRes == SE.getTypeSizeInBits(E->getOperand()->getType()) ?
+ SE.getTypeSizeInBits(E->getType()) : OpRes;
}
- if (SCEVSignExtendExpr *E = dyn_cast<SCEVSignExtendExpr>(S)) {
- uint32_t OpRes = GetMinTrailingZeros(E->getOperand());
- return OpRes == E->getOperand()->getBitWidth() ? E->getBitWidth() : OpRes;
+ if (const SCEVSignExtendExpr *E = dyn_cast<SCEVSignExtendExpr>(S)) {
+ uint32_t OpRes = GetMinTrailingZeros(E->getOperand(), SE);
+ return OpRes == SE.getTypeSizeInBits(E->getOperand()->getType()) ?
+ SE.getTypeSizeInBits(E->getType()) : OpRes;
}
- if (SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) {
+ if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) {
// The result is the min of all operands results.
- uint32_t MinOpRes = GetMinTrailingZeros(A->getOperand(0));
+ uint32_t MinOpRes = GetMinTrailingZeros(A->getOperand(0), SE);
for (unsigned i = 1, e = A->getNumOperands(); MinOpRes && i != e; ++i)
- MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(A->getOperand(i)));
+ MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(A->getOperand(i), SE));
return MinOpRes;
}
- if (SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(S)) {
+ if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(S)) {
// The result is the sum of all operands results.
- uint32_t SumOpRes = GetMinTrailingZeros(M->getOperand(0));
- uint32_t BitWidth = M->getBitWidth();
+ uint32_t SumOpRes = GetMinTrailingZeros(M->getOperand(0), SE);
+ uint32_t BitWidth = SE.getTypeSizeInBits(M->getType());
for (unsigned i = 1, e = M->getNumOperands();
SumOpRes != BitWidth && i != e; ++i)
- SumOpRes = std::min(SumOpRes + GetMinTrailingZeros(M->getOperand(i)),
+ SumOpRes = std::min(SumOpRes + GetMinTrailingZeros(M->getOperand(i), SE),
BitWidth);
return SumOpRes;
}
- if (SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(S)) {
+ if (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(S)) {
// The result is the min of all operands results.
- uint32_t MinOpRes = GetMinTrailingZeros(A->getOperand(0));
+ uint32_t MinOpRes = GetMinTrailingZeros(A->getOperand(0), SE);
for (unsigned i = 1, e = A->getNumOperands(); MinOpRes && i != e; ++i)
- MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(A->getOperand(i)));
+ MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(A->getOperand(i), SE));
return MinOpRes;
}
- if (SCEVSMaxExpr *M = dyn_cast<SCEVSMaxExpr>(S)) {
+ if (const SCEVSMaxExpr *M = dyn_cast<SCEVSMaxExpr>(S)) {
// The result is the min of all operands results.
- uint32_t MinOpRes = GetMinTrailingZeros(M->getOperand(0));
+ uint32_t MinOpRes = GetMinTrailingZeros(M->getOperand(0), SE);
for (unsigned i = 1, e = M->getNumOperands(); MinOpRes && i != e; ++i)
- MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(M->getOperand(i)));
+ MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(M->getOperand(i), SE));
return MinOpRes;
}
- if (SCEVUMaxExpr *M = dyn_cast<SCEVUMaxExpr>(S)) {
+ if (const SCEVUMaxExpr *M = dyn_cast<SCEVUMaxExpr>(S)) {
// The result is the min of all operands results.
- uint32_t MinOpRes = GetMinTrailingZeros(M->getOperand(0));
+ uint32_t MinOpRes = GetMinTrailingZeros(M->getOperand(0), SE);
for (unsigned i = 1, e = M->getNumOperands(); MinOpRes && i != e; ++i)
- MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(M->getOperand(i)));
+ MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(M->getOperand(i), SE));
return MinOpRes;
}
/// createSCEV - We know that there is no SCEV for the specified value.
/// Analyze the expression.
///
-SCEVHandle ScalarEvolutionsImpl::createSCEV(Value *V) {
- if (!isa<IntegerType>(V->getType()))
- return SE.getUnknown(V);
-
+SCEVHandle ScalarEvolution::createSCEV(Value *V) {
+ if (!isSCEVable(V->getType()))
+ return getUnknown(V);
+
unsigned Opcode = Instruction::UserOp1;
if (Instruction *I = dyn_cast<Instruction>(V))
Opcode = I->getOpcode();
else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
Opcode = CE->getOpcode();
else
- return SE.getUnknown(V);
+ return getUnknown(V);
User *U = cast<User>(V);
switch (Opcode) {
case Instruction::Add:
- return SE.getAddExpr(getSCEV(U->getOperand(0)),
- getSCEV(U->getOperand(1)));
+ return getAddExpr(getSCEV(U->getOperand(0)),
+ getSCEV(U->getOperand(1)));
case Instruction::Mul:
- return SE.getMulExpr(getSCEV(U->getOperand(0)),
- getSCEV(U->getOperand(1)));
+ return getMulExpr(getSCEV(U->getOperand(0)),
+ getSCEV(U->getOperand(1)));
case Instruction::UDiv:
- return SE.getUDivExpr(getSCEV(U->getOperand(0)),
- getSCEV(U->getOperand(1)));
+ return getUDivExpr(getSCEV(U->getOperand(0)),
+ getSCEV(U->getOperand(1)));
case Instruction::Sub:
- return SE.getMinusSCEV(getSCEV(U->getOperand(0)),
- getSCEV(U->getOperand(1)));
+ return getMinusSCEV(getSCEV(U->getOperand(0)),
+ getSCEV(U->getOperand(1)));
+ case Instruction::And:
+ // For an expression like x&255 that merely masks off the high bits,
+ // use zext(trunc(x)) as the SCEV expression.
+ if (ConstantInt *CI = dyn_cast<ConstantInt>(U->getOperand(1))) {
+ if (CI->isNullValue())
+ return getSCEV(U->getOperand(1));
+ if (CI->isAllOnesValue())
+ return getSCEV(U->getOperand(0));
+ const APInt &A = CI->getValue();
+ unsigned Ones = A.countTrailingOnes();
+ if (APIntOps::isMask(Ones, A))
+ return
+ getZeroExtendExpr(getTruncateExpr(getSCEV(U->getOperand(0)),
+ IntegerType::get(Ones)),
+ U->getType());
+ }
+ break;
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
if (ConstantInt *CI = dyn_cast<ConstantInt>(U->getOperand(1))) {
SCEVHandle LHS = getSCEV(U->getOperand(0));
const APInt &CIVal = CI->getValue();
- if (GetMinTrailingZeros(LHS) >=
+ if (GetMinTrailingZeros(LHS, *this) >=
(CIVal.getBitWidth() - CIVal.countLeadingZeros()))
- return SE.getAddExpr(LHS, getSCEV(U->getOperand(1)));
+ return getAddExpr(LHS, getSCEV(U->getOperand(1)));
}
break;
case Instruction::Xor:
// If the RHS of the xor is a signbit, then this is just an add.
// Instcombine turns add of signbit into xor as a strength reduction step.
if (CI->getValue().isSignBit())
- return SE.getAddExpr(getSCEV(U->getOperand(0)),
- getSCEV(U->getOperand(1)));
+ return getAddExpr(getSCEV(U->getOperand(0)),
+ getSCEV(U->getOperand(1)));
// If the RHS of xor is -1, then this is a not operation.
- else if (CI->isAllOnesValue())
- return SE.getNotSCEV(getSCEV(U->getOperand(0)));
+ if (CI->isAllOnesValue())
+ return getNotSCEV(getSCEV(U->getOperand(0)));
+
+ // Model xor(and(x, C), C) as and(~x, C), if C is a low-bits mask.
+ // This is a variant of the check for xor with -1, and it handles
+ // the case where instcombine has trimmed non-demanded bits out
+ // of an xor with -1.
+ if (BinaryOperator *BO = dyn_cast<BinaryOperator>(U->getOperand(0)))
+ if (ConstantInt *LCI = dyn_cast<ConstantInt>(BO->getOperand(1)))
+ if (BO->getOpcode() == Instruction::And &&
+ LCI->getValue() == CI->getValue())
+ if (const SCEVZeroExtendExpr *Z =
+ dyn_cast<SCEVZeroExtendExpr>(getSCEV(U->getOperand(0))))
+ return getZeroExtendExpr(getNotSCEV(Z->getOperand()),
+ U->getType());
}
break;
uint32_t BitWidth = cast<IntegerType>(V->getType())->getBitWidth();
Constant *X = ConstantInt::get(
APInt(BitWidth, 1).shl(SA->getLimitedValue(BitWidth)));
- return SE.getMulExpr(getSCEV(U->getOperand(0)), getSCEV(X));
+ return getMulExpr(getSCEV(U->getOperand(0)), getSCEV(X));
}
break;
uint32_t BitWidth = cast<IntegerType>(V->getType())->getBitWidth();
Constant *X = ConstantInt::get(
APInt(BitWidth, 1).shl(SA->getLimitedValue(BitWidth)));
- return SE.getUDivExpr(getSCEV(U->getOperand(0)), getSCEV(X));
+ return getUDivExpr(getSCEV(U->getOperand(0)), getSCEV(X));
}
break;
+ case Instruction::AShr:
+ // For a two-shift sext-inreg, use sext(trunc(x)) as the SCEV expression.
+ if (ConstantInt *CI = dyn_cast<ConstantInt>(U->getOperand(1)))
+ if (Instruction *L = dyn_cast<Instruction>(U->getOperand(0)))
+ if (L->getOpcode() == Instruction::Shl &&
+ L->getOperand(1) == U->getOperand(1)) {
+ unsigned BitWidth = getTypeSizeInBits(U->getType());
+ uint64_t Amt = BitWidth - CI->getZExtValue();
+ if (Amt == BitWidth)
+ return getSCEV(L->getOperand(0)); // shift by zero --> noop
+ if (Amt > BitWidth)
+ return getIntegerSCEV(0, U->getType()); // value is undefined
+ return
+ getSignExtendExpr(getTruncateExpr(getSCEV(L->getOperand(0)),
+ IntegerType::get(Amt)),
+ U->getType());
+ }
+ break;
+
case Instruction::Trunc:
- return SE.getTruncateExpr(getSCEV(U->getOperand(0)), U->getType());
+ return getTruncateExpr(getSCEV(U->getOperand(0)), U->getType());
case Instruction::ZExt:
- return SE.getZeroExtendExpr(getSCEV(U->getOperand(0)), U->getType());
+ return getZeroExtendExpr(getSCEV(U->getOperand(0)), U->getType());
case Instruction::SExt:
- return SE.getSignExtendExpr(getSCEV(U->getOperand(0)), U->getType());
+ return getSignExtendExpr(getSCEV(U->getOperand(0)), U->getType());
case Instruction::BitCast:
// BitCasts are no-op casts so we just eliminate the cast.
- if (U->getType()->isInteger() &&
- U->getOperand(0)->getType()->isInteger())
+ if (isSCEVable(U->getType()) && isSCEVable(U->getOperand(0)->getType()))
return getSCEV(U->getOperand(0));
break;
+ case Instruction::IntToPtr:
+ if (!TD) break; // Without TD we can't analyze pointers.
+ return getTruncateOrZeroExtend(getSCEV(U->getOperand(0)),
+ TD->getIntPtrType());
+
+ case Instruction::PtrToInt:
+ if (!TD) break; // Without TD we can't analyze pointers.
+ return getTruncateOrZeroExtend(getSCEV(U->getOperand(0)),
+ U->getType());
+
+ case Instruction::GetElementPtr:
+ if (!TD) break; // Without TD we can't analyze pointers.
+ return createNodeForGEP(U);
+
case Instruction::PHI:
return createNodeForPHI(cast<PHINode>(U));
case ICmpInst::ICMP_SGT:
case ICmpInst::ICMP_SGE:
if (LHS == U->getOperand(1) && RHS == U->getOperand(2))
- return SE.getSMaxExpr(getSCEV(LHS), getSCEV(RHS));
+ return getSMaxExpr(getSCEV(LHS), getSCEV(RHS));
else if (LHS == U->getOperand(2) && RHS == U->getOperand(1))
// ~smax(~x, ~y) == smin(x, y).
- return SE.getNotSCEV(SE.getSMaxExpr(
- SE.getNotSCEV(getSCEV(LHS)),
- SE.getNotSCEV(getSCEV(RHS))));
+ return getNotSCEV(getSMaxExpr(
+ getNotSCEV(getSCEV(LHS)),
+ getNotSCEV(getSCEV(RHS))));
break;
case ICmpInst::ICMP_ULT:
case ICmpInst::ICMP_ULE:
case ICmpInst::ICMP_UGT:
case ICmpInst::ICMP_UGE:
if (LHS == U->getOperand(1) && RHS == U->getOperand(2))
- return SE.getUMaxExpr(getSCEV(LHS), getSCEV(RHS));
+ return getUMaxExpr(getSCEV(LHS), getSCEV(RHS));
else if (LHS == U->getOperand(2) && RHS == U->getOperand(1))
// ~umax(~x, ~y) == umin(x, y)
- return SE.getNotSCEV(SE.getUMaxExpr(SE.getNotSCEV(getSCEV(LHS)),
- SE.getNotSCEV(getSCEV(RHS))));
+ return getNotSCEV(getUMaxExpr(getNotSCEV(getSCEV(LHS)),
+ getNotSCEV(getSCEV(RHS))));
break;
default:
break;
break;
}
- return SE.getUnknown(V);
+ return getUnknown(V);
}
// Iteration Count Computation Code
//
-/// getIterationCount - If the specified loop has a predictable iteration
-/// count, return it. Note that it is not valid to call this method on a
-/// loop without a loop-invariant iteration count.
-SCEVHandle ScalarEvolutionsImpl::getIterationCount(const Loop *L) {
- std::map<const Loop*, SCEVHandle>::iterator I = IterationCounts.find(L);
- if (I == IterationCounts.end()) {
- SCEVHandle ItCount = ComputeIterationCount(L);
- I = IterationCounts.insert(std::make_pair(L, ItCount)).first;
- if (ItCount != UnknownValue) {
- assert(ItCount->isLoopInvariant(L) &&
+/// getBackedgeTakenCount - If the specified loop has a predictable
+/// backedge-taken count, return it, otherwise return a SCEVCouldNotCompute
+/// object. The backedge-taken count is the number of times the loop header
+/// will be branched to from within the loop. This is one less than the
+/// trip count of the loop, since it doesn't count the first iteration,
+/// when the header is branched to from outside the loop.
+///
+/// Note that it is not valid to call this method on a loop without a
+/// loop-invariant backedge-taken count (see
+/// hasLoopInvariantBackedgeTakenCount).
+///
+SCEVHandle ScalarEvolution::getBackedgeTakenCount(const Loop *L) {
+ return getBackedgeTakenInfo(L).Exact;
+}
+
+/// getMaxBackedgeTakenCount - Similar to getBackedgeTakenCount, except
+/// return the least SCEV value that is known never to be less than the
+/// actual backedge taken count.
+SCEVHandle ScalarEvolution::getMaxBackedgeTakenCount(const Loop *L) {
+ return getBackedgeTakenInfo(L).Max;
+}
+
+const ScalarEvolution::BackedgeTakenInfo &
+ScalarEvolution::getBackedgeTakenInfo(const Loop *L) {
+ // Initially insert a CouldNotCompute for this loop. If the insertion
+ // succeeds, procede to actually compute a backedge-taken count and
+ // update the value. The temporary CouldNotCompute value tells SCEV
+ // code elsewhere that it shouldn't attempt to request a new
+ // backedge-taken count, which could result in infinite recursion.
+ std::pair<std::map<const Loop*, BackedgeTakenInfo>::iterator, bool> Pair =
+ BackedgeTakenCounts.insert(std::make_pair(L, getCouldNotCompute()));
+ if (Pair.second) {
+ BackedgeTakenInfo ItCount = ComputeBackedgeTakenCount(L);
+ if (ItCount.Exact != CouldNotCompute) {
+ assert(ItCount.Exact->isLoopInvariant(L) &&
+ ItCount.Max->isLoopInvariant(L) &&
"Computed trip count isn't loop invariant for loop!");
++NumTripCountsComputed;
+
+ // Update the value in the map.
+ Pair.first->second = ItCount;
} else if (isa<PHINode>(L->getHeader()->begin())) {
// Only count loops that have phi nodes as not being computable.
++NumTripCountsNotComputed;
}
+
+ // Now that we know more about the trip count for this loop, forget any
+ // existing SCEV values for PHI nodes in this loop since they are only
+ // conservative estimates made without the benefit
+ // of trip count information.
+ if (ItCount.hasAnyInfo())
+ forgetLoopPHIs(L);
+ }
+ return Pair.first->second;
+}
+
+/// forgetLoopBackedgeTakenCount - This method should be called by the
+/// client when it has changed a loop in a way that may effect
+/// ScalarEvolution's ability to compute a trip count, or if the loop
+/// is deleted.
+void ScalarEvolution::forgetLoopBackedgeTakenCount(const Loop *L) {
+ BackedgeTakenCounts.erase(L);
+ forgetLoopPHIs(L);
+}
+
+/// forgetLoopPHIs - Delete the memoized SCEVs associated with the
+/// PHI nodes in the given loop. This is used when the trip count of
+/// the loop may have changed.
+void ScalarEvolution::forgetLoopPHIs(const Loop *L) {
+ BasicBlock *Header = L->getHeader();
+
+ // Push all Loop-header PHIs onto the Worklist stack, except those
+ // that are presently represented via a SCEVUnknown. SCEVUnknown for
+ // a PHI either means that it has an unrecognized structure, or it's
+ // a PHI that's in the progress of being computed by createNodeForPHI.
+ // In the former case, additional loop trip count information isn't
+ // going to change anything. In the later case, createNodeForPHI will
+ // perform the necessary updates on its own when it gets to that point.
+ SmallVector<Instruction *, 16> Worklist;
+ for (BasicBlock::iterator I = Header->begin();
+ PHINode *PN = dyn_cast<PHINode>(I); ++I) {
+ std::map<SCEVCallbackVH, SCEVHandle>::iterator It = Scalars.find((Value*)I);
+ if (It != Scalars.end() && !isa<SCEVUnknown>(It->second))
+ Worklist.push_back(PN);
+ }
+
+ while (!Worklist.empty()) {
+ Instruction *I = Worklist.pop_back_val();
+ if (Scalars.erase(I))
+ for (Value::use_iterator UI = I->use_begin(), UE = I->use_end();
+ UI != UE; ++UI)
+ Worklist.push_back(cast<Instruction>(UI));
}
- return I->second;
}
-/// ComputeIterationCount - Compute the number of times the specified loop
-/// will iterate.
-SCEVHandle ScalarEvolutionsImpl::ComputeIterationCount(const Loop *L) {
+/// ComputeBackedgeTakenCount - Compute the number of times the backedge
+/// of the specified loop will execute.
+ScalarEvolution::BackedgeTakenInfo
+ScalarEvolution::ComputeBackedgeTakenCount(const Loop *L) {
// If the loop has a non-one exit block count, we can't analyze it.
- SmallVector<BasicBlock*, 8> ExitBlocks;
- L->getExitBlocks(ExitBlocks);
- if (ExitBlocks.size() != 1) return UnknownValue;
+ BasicBlock *ExitBlock = L->getExitBlock();
+ if (!ExitBlock)
+ return CouldNotCompute;
// Okay, there is one exit block. Try to find the condition that causes the
// loop to be exited.
- BasicBlock *ExitBlock = ExitBlocks[0];
-
- BasicBlock *ExitingBlock = 0;
- for (pred_iterator PI = pred_begin(ExitBlock), E = pred_end(ExitBlock);
- PI != E; ++PI)
- if (L->contains(*PI)) {
- if (ExitingBlock == 0)
- ExitingBlock = *PI;
- else
- return UnknownValue; // More than one block exiting!
- }
- assert(ExitingBlock && "No exits from loop, something is broken!");
+ BasicBlock *ExitingBlock = L->getExitingBlock();
+ if (!ExitingBlock)
+ return CouldNotCompute; // More than one block exiting!
// Okay, we've computed the exiting block. See what condition causes us to
// exit.
//
// FIXME: we should be able to handle switch instructions (with a single exit)
BranchInst *ExitBr = dyn_cast<BranchInst>(ExitingBlock->getTerminator());
- if (ExitBr == 0) return UnknownValue;
+ if (ExitBr == 0) return CouldNotCompute;
assert(ExitBr->isConditional() && "If unconditional, it can't be in loop!");
// At this point, we know we have a conditional branch that determines whether
if (ExitBr->getSuccessor(0) != L->getHeader() &&
ExitBr->getSuccessor(1) != L->getHeader() &&
ExitBr->getParent() != L->getHeader())
- return UnknownValue;
+ return CouldNotCompute;
ICmpInst *ExitCond = dyn_cast<ICmpInst>(ExitBr->getCondition());
- // If it's 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(),
+ // If it's not an integer or pointer comparison then compute it the hard way.
+ if (ExitCond == 0)
+ return ComputeBackedgeTakenCountExhaustively(L, ExitBr->getCondition(),
ExitBr->getSuccessor(0) == ExitBlock);
// If the condition was exit on true, convert the condition to exit on false
if (LoadInst *LI = dyn_cast<LoadInst>(ExitCond->getOperand(0)))
if (Constant *RHS = dyn_cast<Constant>(ExitCond->getOperand(1))) {
SCEVHandle ItCnt =
- ComputeLoadConstantCompareIterationCount(LI, RHS, L, Cond);
+ ComputeLoadConstantCompareBackedgeTakenCount(LI, RHS, L, Cond);
if (!isa<SCEVCouldNotCompute>(ItCnt)) return ItCnt;
}
SCEVHandle RHS = getSCEV(ExitCond->getOperand(1));
// Try to evaluate any dependencies out of the loop.
- SCEVHandle Tmp = getSCEVAtScope(LHS, L);
- if (!isa<SCEVCouldNotCompute>(Tmp)) LHS = Tmp;
- Tmp = getSCEVAtScope(RHS, L);
- if (!isa<SCEVCouldNotCompute>(Tmp)) RHS = Tmp;
+ LHS = getSCEVAtScope(LHS, L);
+ RHS = getSCEVAtScope(RHS, L);
// At this point, we would like to compute how many iterations of the
// loop the predicate will return true for these inputs.
Cond = ICmpInst::getSwappedPredicate(Cond);
}
- // FIXME: think about handling pointer comparisons! i.e.:
- // while (P != P+100) ++P;
-
// If we have a comparison of a chrec against a constant, try to use value
// ranges to answer this query.
- if (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS))
- if (SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS))
+ if (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS))
+ if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS))
if (AddRec->getLoop() == L) {
- // Form the comparison range using the constant of the correct type so
- // that the ConstantRange class knows to do a signed or unsigned
- // comparison.
- ConstantInt *CompVal = RHSC->getValue();
- const Type *RealTy = ExitCond->getOperand(0)->getType();
- CompVal = dyn_cast<ConstantInt>(
- ConstantExpr::getBitCast(CompVal, RealTy));
- if (CompVal) {
- // Form the constant range.
- ConstantRange CompRange(
- ICmpInst::makeConstantRange(Cond, CompVal->getValue()));
-
- SCEVHandle Ret = AddRec->getNumIterationsInRange(CompRange, SE);
- if (!isa<SCEVCouldNotCompute>(Ret)) return Ret;
- }
+ // Form the constant range.
+ ConstantRange CompRange(
+ ICmpInst::makeConstantRange(Cond, RHSC->getValue()->getValue()));
+
+ SCEVHandle Ret = AddRec->getNumIterationsInRange(CompRange, *this);
+ if (!isa<SCEVCouldNotCompute>(Ret)) return Ret;
}
switch (Cond) {
case ICmpInst::ICMP_NE: { // while (X != Y)
// Convert to: while (X-Y != 0)
- SCEVHandle TC = HowFarToZero(SE.getMinusSCEV(LHS, RHS), L);
+ SCEVHandle TC = HowFarToZero(getMinusSCEV(LHS, RHS), L);
if (!isa<SCEVCouldNotCompute>(TC)) return TC;
break;
}
case ICmpInst::ICMP_EQ: {
// Convert to: while (X-Y == 0) // while (X == Y)
- SCEVHandle TC = HowFarToNonZero(SE.getMinusSCEV(LHS, RHS), L);
+ SCEVHandle TC = HowFarToNonZero(getMinusSCEV(LHS, RHS), L);
if (!isa<SCEVCouldNotCompute>(TC)) return TC;
break;
}
case ICmpInst::ICMP_SLT: {
- SCEVHandle TC = HowManyLessThans(LHS, RHS, L, true);
- if (!isa<SCEVCouldNotCompute>(TC)) return TC;
+ BackedgeTakenInfo BTI = HowManyLessThans(LHS, RHS, L, true);
+ if (BTI.hasAnyInfo()) return BTI;
break;
}
case ICmpInst::ICMP_SGT: {
- SCEVHandle TC = HowManyLessThans(SE.getNotSCEV(LHS),
- SE.getNotSCEV(RHS), L, true);
- if (!isa<SCEVCouldNotCompute>(TC)) return TC;
+ BackedgeTakenInfo BTI = HowManyLessThans(getNotSCEV(LHS),
+ getNotSCEV(RHS), L, true);
+ if (BTI.hasAnyInfo()) return BTI;
break;
}
case ICmpInst::ICMP_ULT: {
- SCEVHandle TC = HowManyLessThans(LHS, RHS, L, false);
- if (!isa<SCEVCouldNotCompute>(TC)) return TC;
+ BackedgeTakenInfo BTI = HowManyLessThans(LHS, RHS, L, false);
+ if (BTI.hasAnyInfo()) return BTI;
break;
}
case ICmpInst::ICMP_UGT: {
- SCEVHandle TC = HowManyLessThans(SE.getNotSCEV(LHS),
- SE.getNotSCEV(RHS), L, false);
- if (!isa<SCEVCouldNotCompute>(TC)) return TC;
+ BackedgeTakenInfo BTI = HowManyLessThans(getNotSCEV(LHS),
+ getNotSCEV(RHS), L, false);
+ if (BTI.hasAnyInfo()) return BTI;
break;
}
default:
#if 0
- cerr << "ComputeIterationCount ";
+ errs() << "ComputeBackedgeTakenCount ";
if (ExitCond->getOperand(0)->getType()->isUnsigned())
- cerr << "[unsigned] ";
- cerr << *LHS << " "
+ errs() << "[unsigned] ";
+ errs() << *LHS << " "
<< Instruction::getOpcodeName(Instruction::ICmp)
<< " " << *RHS << "\n";
#endif
break;
}
- return ComputeIterationCountExhaustively(L, ExitCond,
- ExitBr->getSuccessor(0) == ExitBlock);
+ return
+ ComputeBackedgeTakenCountExhaustively(L, ExitCond,
+ ExitBr->getSuccessor(0) == ExitBlock);
}
static ConstantInt *
return Init;
}
-/// ComputeLoadConstantCompareIterationCount - Given an exit condition of
-/// 'icmp op load X, cst', try to see if we can compute the trip count.
-SCEVHandle ScalarEvolutionsImpl::
-ComputeLoadConstantCompareIterationCount(LoadInst *LI, Constant *RHS,
- const Loop *L,
- ICmpInst::Predicate predicate) {
- if (LI->isVolatile()) return UnknownValue;
+/// ComputeLoadConstantCompareBackedgeTakenCount - Given an exit condition of
+/// 'icmp op load X, cst', try to see if we can compute the backedge
+/// execution count.
+SCEVHandle ScalarEvolution::
+ComputeLoadConstantCompareBackedgeTakenCount(LoadInst *LI, Constant *RHS,
+ const Loop *L,
+ ICmpInst::Predicate predicate) {
+ if (LI->isVolatile()) return CouldNotCompute;
// Check to see if the loaded pointer is a getelementptr of a global.
GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(LI->getOperand(0));
- if (!GEP) return UnknownValue;
+ if (!GEP) return CouldNotCompute;
// Make sure that it is really a constant global we are gepping, with an
// initializer, and make sure the first IDX is really 0.
if (!GV || !GV->isConstant() || !GV->hasInitializer() ||
GEP->getNumOperands() < 3 || !isa<Constant>(GEP->getOperand(1)) ||
!cast<Constant>(GEP->getOperand(1))->isNullValue())
- return UnknownValue;
+ return CouldNotCompute;
// Okay, we allow one non-constant index into the GEP instruction.
Value *VarIdx = 0;
if (ConstantInt *CI = dyn_cast<ConstantInt>(GEP->getOperand(i))) {
Indexes.push_back(CI);
} else if (!isa<ConstantInt>(GEP->getOperand(i))) {
- if (VarIdx) return UnknownValue; // Multiple non-constant idx's.
+ if (VarIdx) return CouldNotCompute; // Multiple non-constant idx's.
VarIdx = GEP->getOperand(i);
VarIdxNum = i-2;
Indexes.push_back(0);
// Okay, we know we have a (load (gep GV, 0, X)) comparison with a constant.
// Check to see if X is a loop variant variable value now.
SCEVHandle Idx = getSCEV(VarIdx);
- SCEVHandle Tmp = getSCEVAtScope(Idx, L);
- if (!isa<SCEVCouldNotCompute>(Tmp)) Idx = Tmp;
+ Idx = getSCEVAtScope(Idx, L);
// We can only recognize very limited forms of loop index expressions, in
// particular, only affine AddRec's like {C1,+,C2}.
- SCEVAddRecExpr *IdxExpr = dyn_cast<SCEVAddRecExpr>(Idx);
+ const SCEVAddRecExpr *IdxExpr = dyn_cast<SCEVAddRecExpr>(Idx);
if (!IdxExpr || !IdxExpr->isAffine() || IdxExpr->isLoopInvariant(L) ||
!isa<SCEVConstant>(IdxExpr->getOperand(0)) ||
!isa<SCEVConstant>(IdxExpr->getOperand(1)))
- return UnknownValue;
+ return CouldNotCompute;
unsigned MaxSteps = MaxBruteForceIterations;
for (unsigned IterationNum = 0; IterationNum != MaxSteps; ++IterationNum) {
ConstantInt *ItCst =
ConstantInt::get(IdxExpr->getType(), IterationNum);
- ConstantInt *Val = EvaluateConstantChrecAtConstant(IdxExpr, ItCst, SE);
+ ConstantInt *Val = EvaluateConstantChrecAtConstant(IdxExpr, ItCst, *this);
// Form the GEP offset.
Indexes[VarIdxNum] = Val;
if (!isa<ConstantInt>(Result)) break; // Couldn't decide for sure
if (cast<ConstantInt>(Result)->getValue().isMinValue()) {
#if 0
- cerr << "\n***\n*** Computed loop count " << *ItCst
- << "\n*** From global " << *GV << "*** BB: " << *L->getHeader()
- << "***\n";
+ errs() << "\n***\n*** Computed loop count " << *ItCst
+ << "\n*** From global " << *GV << "*** BB: " << *L->getHeader()
+ << "***\n";
#endif
++NumArrayLenItCounts;
- return SE.getConstant(ItCst); // Found terminating iteration!
+ return getConstant(ItCst); // Found terminating iteration!
}
}
- return UnknownValue;
+ return CouldNotCompute;
}
static Constant *EvaluateExpression(Value *V, Constant *PHIVal) {
if (isa<PHINode>(V)) return PHIVal;
if (Constant *C = dyn_cast<Constant>(V)) return C;
+ if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) return GV;
Instruction *I = cast<Instruction>(V);
std::vector<Constant*> Operands;
/// 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
/// involving constants, fold it.
-Constant *ScalarEvolutionsImpl::
-getConstantEvolutionLoopExitValue(PHINode *PN, const APInt& Its, const Loop *L){
+Constant *ScalarEvolution::
+getConstantEvolutionLoopExitValue(PHINode *PN, const APInt& BEs, const Loop *L){
std::map<PHINode*, Constant*>::iterator I =
ConstantEvolutionLoopExitValue.find(PN);
if (I != ConstantEvolutionLoopExitValue.end())
return I->second;
- if (Its.ugt(APInt(Its.getBitWidth(),MaxBruteForceIterations)))
+ if (BEs.ugt(APInt(BEs.getBitWidth(),MaxBruteForceIterations)))
return ConstantEvolutionLoopExitValue[PN] = 0; // Not going to evaluate it.
Constant *&RetVal = ConstantEvolutionLoopExitValue[PN];
return RetVal = 0; // Not derived from same PHI.
// Execute the loop symbolically to determine the exit value.
- if (Its.getActiveBits() >= 32)
+ if (BEs.getActiveBits() >= 32)
return RetVal = 0; // More than 2^32-1 iterations?? Not doing it!
- unsigned NumIterations = Its.getZExtValue(); // must be in range
+ unsigned NumIterations = BEs.getZExtValue(); // must be in range
unsigned IterationNum = 0;
for (Constant *PHIVal = StartCST; ; ++IterationNum) {
if (IterationNum == NumIterations)
}
}
-/// ComputeIterationCountExhaustively - If the trip is known to execute a
+/// ComputeBackedgeTakenCountExhaustively - If the trip is known to execute a
/// constant number of times (the condition evolves only from constants),
/// try to evaluate a few iterations of the loop until we get the exit
/// condition gets a value of ExitWhen (true or false). If we cannot
-/// evaluate the trip count of the loop, return UnknownValue.
-SCEVHandle ScalarEvolutionsImpl::
-ComputeIterationCountExhaustively(const Loop *L, Value *Cond, bool ExitWhen) {
+/// evaluate the trip count of the loop, return CouldNotCompute.
+SCEVHandle ScalarEvolution::
+ComputeBackedgeTakenCountExhaustively(const Loop *L, Value *Cond, bool ExitWhen) {
PHINode *PN = getConstantEvolvingPHI(Cond, L);
- if (PN == 0) return UnknownValue;
+ if (PN == 0) return CouldNotCompute;
// Since the loop is canonicalized, the PHI node must have two entries. One
// entry must be a constant (coming in from outside of the loop), and the
bool SecondIsBackedge = L->contains(PN->getIncomingBlock(1));
Constant *StartCST =
dyn_cast<Constant>(PN->getIncomingValue(!SecondIsBackedge));
- if (StartCST == 0) return UnknownValue; // Must be a constant.
+ if (StartCST == 0) return CouldNotCompute; // Must be a constant.
Value *BEValue = PN->getIncomingValue(SecondIsBackedge);
PHINode *PN2 = getConstantEvolvingPHI(BEValue, L);
- if (PN2 != PN) return UnknownValue; // Not derived from same PHI.
+ if (PN2 != PN) return CouldNotCompute; // Not derived from same PHI.
// Okay, we find a PHI node that defines the trip count of this loop. Execute
// the loop symbolically to determine when the condition gets a value of
dyn_cast_or_null<ConstantInt>(EvaluateExpression(Cond, PHIVal));
// Couldn't symbolically evaluate.
- if (!CondVal) return UnknownValue;
+ if (!CondVal) return CouldNotCompute;
if (CondVal->getValue() == uint64_t(ExitWhen)) {
ConstantEvolutionLoopExitValue[PN] = PHIVal;
++NumBruteForceTripCountsComputed;
- return SE.getConstant(ConstantInt::get(Type::Int32Ty, IterationNum));
+ return getConstant(ConstantInt::get(Type::Int32Ty, IterationNum));
}
// Compute the value of the PHI node for the next iteration.
Constant *NextPHI = EvaluateExpression(BEValue, PHIVal);
if (NextPHI == 0 || NextPHI == PHIVal)
- return UnknownValue; // Couldn't evaluate or not making progress...
+ return CouldNotCompute; // Couldn't evaluate or not making progress...
PHIVal = NextPHI;
}
// Too many iterations were needed to evaluate.
- return UnknownValue;
+ return CouldNotCompute;
}
-/// 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.
-SCEVHandle ScalarEvolutionsImpl::getSCEVAtScope(SCEV *V, const Loop *L) {
+/// getSCEVAtScope - Return a SCEV expression handle for the specified value
+/// at the specified scope in the program. The L value specifies a loop
+/// nest to evaluate the expression at, where null is the top-level or a
+/// specified loop is immediately inside of the loop.
+///
+/// This method can be used to compute the exit value for a variable defined
+/// in a loop by querying what the value will hold in the parent loop.
+///
+/// In the case that a relevant loop exit value cannot be computed, the
+/// original value V is returned.
+SCEVHandle ScalarEvolution::getSCEVAtScope(const SCEV *V, const Loop *L) {
// FIXME: this should be turned into a virtual method on SCEV!
if (isa<SCEVConstant>(V)) return V;
// If this instruction is evolved from a constant-evolving PHI, compute the
// exit value from the loop without using SCEVs.
- if (SCEVUnknown *SU = dyn_cast<SCEVUnknown>(V)) {
+ if (const SCEVUnknown *SU = dyn_cast<SCEVUnknown>(V)) {
if (Instruction *I = dyn_cast<Instruction>(SU->getValue())) {
- const Loop *LI = this->LI[I->getParent()];
+ const Loop *LI = (*this->LI)[I->getParent()];
if (LI && LI->getParentLoop() == L) // Looking for loop exit value.
if (PHINode *PN = dyn_cast<PHINode>(I))
if (PN->getParent() == LI->getHeader()) {
// Okay, there is no closed form solution for the PHI node. Check
- // to see if the loop that contains it has a known iteration count.
- // If so, we may be able to force computation of the exit value.
- SCEVHandle IterationCount = getIterationCount(LI);
- if (SCEVConstant *ICC = dyn_cast<SCEVConstant>(IterationCount)) {
+ // to see if the loop that contains it has a known backedge-taken
+ // count. If so, we may be able to force computation of the exit
+ // value.
+ SCEVHandle BackedgeTakenCount = getBackedgeTakenCount(LI);
+ if (const SCEVConstant *BTCC =
+ dyn_cast<SCEVConstant>(BackedgeTakenCount)) {
// Okay, we know how many times the containing loop executes. If
// this is a constant evolving PHI node, get the final value at
// the specified iteration number.
Constant *RV = getConstantEvolutionLoopExitValue(PN,
- ICC->getValue()->getValue(),
+ BTCC->getValue()->getValue(),
LI);
- if (RV) return SE.getUnknown(RV);
+ if (RV) return getUnknown(RV);
}
}
// 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)) {
+ // Check to see if we've folded this instruction at this loop before.
+ std::map<const Loop *, Constant *> &Values = ValuesAtScopes[I];
+ std::pair<std::map<const Loop *, Constant *>::iterator, bool> Pair =
+ Values.insert(std::make_pair(L, static_cast<Constant *>(0)));
+ if (!Pair.second)
+ return Pair.first->second ? &*getUnknown(Pair.first->second) : V;
+
std::vector<Constant*> Operands;
Operands.reserve(I->getNumOperands());
for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
Operands.push_back(C);
} else {
// If any of the operands is non-constant and if they are
- // non-integer, don't even try to analyze them with scev techniques.
- if (!isa<IntegerType>(Op->getType()))
+ // non-integer and non-pointer, don't even try to analyze them
+ // with scev techniques.
+ if (!isSCEVable(Op->getType()))
return V;
-
+
SCEVHandle OpV = getSCEVAtScope(getSCEV(Op), L);
- if (SCEVConstant *SC = dyn_cast<SCEVConstant>(OpV))
- 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::getIntegerCast(C,
- Op->getType(),
- false));
- else
+ if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(OpV)) {
+ Constant *C = SC->getValue();
+ if (C->getType() != Op->getType())
+ C = ConstantExpr::getCast(CastInst::getCastOpcode(C, false,
+ Op->getType(),
+ false),
+ C, Op->getType());
+ Operands.push_back(C);
+ } else if (const SCEVUnknown *SU = dyn_cast<SCEVUnknown>(OpV)) {
+ if (Constant *C = dyn_cast<Constant>(SU->getValue())) {
+ if (C->getType() != Op->getType())
+ C =
+ ConstantExpr::getCast(CastInst::getCastOpcode(C, false,
+ Op->getType(),
+ false),
+ C, Op->getType());
+ Operands.push_back(C);
+ } else
return V;
} else {
return V;
else
C = ConstantFoldInstOperands(I->getOpcode(), I->getType(),
&Operands[0], Operands.size());
- return SE.getUnknown(C);
+ Pair.first->second = C;
+ return getUnknown(C);
}
}
return V;
}
- if (SCEVCommutativeExpr *Comm = dyn_cast<SCEVCommutativeExpr>(V)) {
+ if (const SCEVCommutativeExpr *Comm = dyn_cast<SCEVCommutativeExpr>(V)) {
// Avoid performing the look-up in the common case where the specified
// expression has no loop-variant portions.
for (unsigned i = 0, e = Comm->getNumOperands(); i != e; ++i) {
SCEVHandle OpAtScope = getSCEVAtScope(Comm->getOperand(i), L);
if (OpAtScope != Comm->getOperand(i)) {
- if (OpAtScope == UnknownValue) return UnknownValue;
// Okay, at least one of these operands is loop variant but might be
// foldable. Build a new instance of the folded commutative expression.
- std::vector<SCEVHandle> NewOps(Comm->op_begin(), Comm->op_begin()+i);
+ SmallVector<SCEVHandle, 8> NewOps(Comm->op_begin(), Comm->op_begin()+i);
NewOps.push_back(OpAtScope);
for (++i; i != e; ++i) {
OpAtScope = getSCEVAtScope(Comm->getOperand(i), L);
- if (OpAtScope == UnknownValue) return UnknownValue;
NewOps.push_back(OpAtScope);
}
if (isa<SCEVAddExpr>(Comm))
- return SE.getAddExpr(NewOps);
+ return getAddExpr(NewOps);
if (isa<SCEVMulExpr>(Comm))
- return SE.getMulExpr(NewOps);
+ return getMulExpr(NewOps);
if (isa<SCEVSMaxExpr>(Comm))
- return SE.getSMaxExpr(NewOps);
+ return getSMaxExpr(NewOps);
if (isa<SCEVUMaxExpr>(Comm))
- return SE.getUMaxExpr(NewOps);
+ return getUMaxExpr(NewOps);
assert(0 && "Unknown commutative SCEV type!");
}
}
return Comm;
}
- if (SCEVUDivExpr *Div = dyn_cast<SCEVUDivExpr>(V)) {
+ if (const SCEVUDivExpr *Div = dyn_cast<SCEVUDivExpr>(V)) {
SCEVHandle LHS = getSCEVAtScope(Div->getLHS(), L);
- if (LHS == UnknownValue) return LHS;
SCEVHandle RHS = getSCEVAtScope(Div->getRHS(), L);
- if (RHS == UnknownValue) return RHS;
if (LHS == Div->getLHS() && RHS == Div->getRHS())
return Div; // must be loop invariant
- return SE.getUDivExpr(LHS, RHS);
+ return getUDivExpr(LHS, RHS);
}
// If this is a loop recurrence for a loop that does not contain L, then we
// are dealing with the final value computed by the loop.
- if (SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V)) {
+ if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V)) {
if (!L || !AddRec->getLoop()->contains(L->getHeader())) {
// To evaluate this recurrence, we need to know how many times the AddRec
// loop iterates. Compute this now.
- SCEVHandle IterationCount = getIterationCount(AddRec->getLoop());
- if (IterationCount == UnknownValue) return UnknownValue;
+ SCEVHandle BackedgeTakenCount = getBackedgeTakenCount(AddRec->getLoop());
+ if (BackedgeTakenCount == CouldNotCompute) return AddRec;
// Then, evaluate the AddRec.
- return AddRec->evaluateAtIteration(IterationCount, SE);
+ return AddRec->evaluateAtIteration(BackedgeTakenCount, *this);
}
- return UnknownValue;
+ return AddRec;
+ }
+
+ if (const SCEVZeroExtendExpr *Cast = dyn_cast<SCEVZeroExtendExpr>(V)) {
+ SCEVHandle Op = getSCEVAtScope(Cast->getOperand(), L);
+ if (Op == Cast->getOperand())
+ return Cast; // must be loop invariant
+ return getZeroExtendExpr(Op, Cast->getType());
+ }
+
+ if (const SCEVSignExtendExpr *Cast = dyn_cast<SCEVSignExtendExpr>(V)) {
+ SCEVHandle Op = getSCEVAtScope(Cast->getOperand(), L);
+ if (Op == Cast->getOperand())
+ return Cast; // must be loop invariant
+ return getSignExtendExpr(Op, Cast->getType());
}
- //assert(0 && "Unknown SCEV type!");
- return UnknownValue;
+ if (const SCEVTruncateExpr *Cast = dyn_cast<SCEVTruncateExpr>(V)) {
+ SCEVHandle Op = getSCEVAtScope(Cast->getOperand(), L);
+ if (Op == Cast->getOperand())
+ return Cast; // must be loop invariant
+ return getTruncateExpr(Op, Cast->getType());
+ }
+
+ assert(0 && "Unknown SCEV type!");
+ return 0;
+}
+
+/// getSCEVAtScope - This is a convenience function which does
+/// getSCEVAtScope(getSCEV(V), L).
+SCEVHandle ScalarEvolution::getSCEVAtScope(Value *V, const Loop *L) {
+ return getSCEVAtScope(getSCEV(V), L);
}
/// SolveLinEquationWithOverflow - Finds the minimum unsigned root of the
// B is divisible by D if and only if the multiplicity of prime factor 2 for B
// is not less than multiplicity of this prime factor for D.
if (B.countTrailingZeros() < Mult2)
- return new SCEVCouldNotCompute();
+ return SE.getCouldNotCompute();
// 3. Compute I: the multiplicative inverse of (A / D) in arithmetic
// modulo (N / D).
static std::pair<SCEVHandle,SCEVHandle>
SolveQuadraticEquation(const SCEVAddRecExpr *AddRec, ScalarEvolution &SE) {
assert(AddRec->getNumOperands() == 3 && "This is not a quadratic chrec!");
- SCEVConstant *LC = dyn_cast<SCEVConstant>(AddRec->getOperand(0));
- SCEVConstant *MC = dyn_cast<SCEVConstant>(AddRec->getOperand(1));
- SCEVConstant *NC = dyn_cast<SCEVConstant>(AddRec->getOperand(2));
+ const SCEVConstant *LC = dyn_cast<SCEVConstant>(AddRec->getOperand(0));
+ const SCEVConstant *MC = dyn_cast<SCEVConstant>(AddRec->getOperand(1));
+ const SCEVConstant *NC = dyn_cast<SCEVConstant>(AddRec->getOperand(2));
// We currently can only solve this if the coefficients are constants.
if (!LC || !MC || !NC) {
- SCEV *CNC = new SCEVCouldNotCompute();
+ const SCEV *CNC = SE.getCouldNotCompute();
return std::make_pair(CNC, CNC);
}
APInt NegB(-B);
APInt TwoA( A << 1 );
if (TwoA.isMinValue()) {
- SCEV *CNC = new SCEVCouldNotCompute();
+ const SCEV *CNC = SE.getCouldNotCompute();
return std::make_pair(CNC, CNC);
}
}
/// HowFarToZero - Return the number of times a backedge comparing the specified
-/// value to zero will execute. If not computable, return UnknownValue
-SCEVHandle ScalarEvolutionsImpl::HowFarToZero(SCEV *V, const Loop *L) {
+/// value to zero will execute. If not computable, return CouldNotCompute.
+SCEVHandle ScalarEvolution::HowFarToZero(const SCEV *V, const Loop *L) {
// If the value is a constant
- if (SCEVConstant *C = dyn_cast<SCEVConstant>(V)) {
+ if (const SCEVConstant *C = dyn_cast<SCEVConstant>(V)) {
// If the value is already zero, the branch will execute zero times.
if (C->getValue()->isZero()) return C;
- return UnknownValue; // Otherwise it will loop infinitely.
+ return CouldNotCompute; // Otherwise it will loop infinitely.
}
- SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V);
+ const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V);
if (!AddRec || AddRec->getLoop() != L)
- return UnknownValue;
+ return CouldNotCompute;
if (AddRec->isAffine()) {
// If this is an affine expression, the execution count of this branch is
// Get the initial value for the loop.
SCEVHandle Start = getSCEVAtScope(AddRec->getStart(), L->getParentLoop());
- if (isa<SCEVCouldNotCompute>(Start)) return UnknownValue;
-
SCEVHandle Step = getSCEVAtScope(AddRec->getOperand(1), L->getParentLoop());
- if (SCEVConstant *StepC = dyn_cast<SCEVConstant>(Step)) {
+ if (const SCEVConstant *StepC = dyn_cast<SCEVConstant>(Step)) {
// For now we handle only constant steps.
// First, handle unitary steps.
if (StepC->getValue()->equalsInt(1)) // 1*N = -Start (mod 2^BW), so:
- return SE.getNegativeSCEV(Start); // N = -Start (as unsigned)
+ return getNegativeSCEV(Start); // N = -Start (as unsigned)
if (StepC->getValue()->isAllOnesValue()) // -1*N = -Start (mod 2^BW), so:
return Start; // N = Start (as unsigned)
// Then, try to solve the above equation provided that Start is constant.
- if (SCEVConstant *StartC = dyn_cast<SCEVConstant>(Start))
+ if (const SCEVConstant *StartC = dyn_cast<SCEVConstant>(Start))
return SolveLinEquationWithOverflow(StepC->getValue()->getValue(),
- -StartC->getValue()->getValue(),SE);
+ -StartC->getValue()->getValue(),
+ *this);
}
} else if (AddRec->isQuadratic() && AddRec->getType()->isInteger()) {
// If this is a quadratic (3-term) AddRec {L,+,M,+,N}, find the roots of
// the quadratic equation to solve it.
- std::pair<SCEVHandle,SCEVHandle> Roots = SolveQuadraticEquation(AddRec, SE);
- SCEVConstant *R1 = dyn_cast<SCEVConstant>(Roots.first);
- SCEVConstant *R2 = dyn_cast<SCEVConstant>(Roots.second);
+ std::pair<SCEVHandle,SCEVHandle> Roots = SolveQuadraticEquation(AddRec,
+ *this);
+ const SCEVConstant *R1 = dyn_cast<SCEVConstant>(Roots.first);
+ const SCEVConstant *R2 = dyn_cast<SCEVConstant>(Roots.second);
if (R1) {
#if 0
- cerr << "HFTZ: " << *V << " - sol#1: " << *R1
- << " sol#2: " << *R2 << "\n";
+ errs() << "HFTZ: " << *V << " - sol#1: " << *R1
+ << " sol#2: " << *R2 << "\n";
#endif
// Pick the smallest positive root value.
if (ConstantInt *CB =
// 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.
- SCEVHandle Val = AddRec->evaluateAtIteration(R1, SE);
+ SCEVHandle Val = AddRec->evaluateAtIteration(R1, *this);
if (Val->isZero())
return R1; // We found a quadratic root!
}
}
}
- return UnknownValue;
+ return CouldNotCompute;
}
/// HowFarToNonZero - Return the number of times a backedge checking the
/// specified value for nonzero will execute. If not computable, return
-/// UnknownValue
-SCEVHandle ScalarEvolutionsImpl::HowFarToNonZero(SCEV *V, const Loop *L) {
+/// CouldNotCompute
+SCEVHandle ScalarEvolution::HowFarToNonZero(const SCEV *V, const Loop *L) {
// 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)) {
+ if (const SCEVConstant *C = dyn_cast<SCEVConstant>(V)) {
if (!C->getValue()->isNullValue())
- return SE.getIntegerSCEV(0, C->getType());
- return UnknownValue; // Otherwise it will loop infinitely.
+ return getIntegerSCEV(0, C->getType());
+ return CouldNotCompute; // 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;
+ return CouldNotCompute;
+}
+
+/// getLoopPredecessor - If the given loop's header has exactly one unique
+/// predecessor outside the loop, return it. Otherwise return null.
+///
+BasicBlock *ScalarEvolution::getLoopPredecessor(const Loop *L) {
+ BasicBlock *Header = L->getHeader();
+ BasicBlock *Pred = 0;
+ for (pred_iterator PI = pred_begin(Header), E = pred_end(Header);
+ PI != E; ++PI)
+ if (!L->contains(*PI)) {
+ if (Pred && Pred != *PI) return 0; // Multiple predecessors.
+ Pred = *PI;
+ }
+ return Pred;
}
/// getPredecessorWithUniqueSuccessorForBB - Return a predecessor of BB
/// found.
///
BasicBlock *
-ScalarEvolutionsImpl::getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB) {
- // If the block has a unique predecessor, the predecessor must have
- // no other successors from which BB is reachable.
+ScalarEvolution::getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB) {
+ // If the block has a unique predecessor, then there is no path from the
+ // predecessor to the block that does not go through the direct edge
+ // from the predecessor to the block.
if (BasicBlock *Pred = BB->getSinglePredecessor())
return Pred;
// A loop's header is defined to be a block that dominates the loop.
- // If the loop has a preheader, it must be a block that has exactly
- // one successor that can reach BB. This is slightly more strict
- // than necessary, but works if critical edges are split.
- if (Loop *L = LI.getLoopFor(BB))
- return L->getLoopPreheader();
+ // If the header has a unique predecessor outside the loop, it must be
+ // a block that has exactly one successor that can reach the loop.
+ if (Loop *L = LI->getLoopFor(BB))
+ return getLoopPredecessor(L);
return 0;
}
-/// executesAtLeastOnce - Test whether entry to the loop is protected by
-/// a conditional between LHS and RHS.
-bool ScalarEvolutionsImpl::executesAtLeastOnce(const Loop *L, bool isSigned,
- SCEV *LHS, SCEV *RHS) {
- BasicBlock *Preheader = L->getLoopPreheader();
- BasicBlock *PreheaderDest = L->getHeader();
+/// isLoopGuardedByCond - Test whether entry to the loop is protected by
+/// a conditional between LHS and RHS. This is used to help avoid max
+/// expressions in loop trip counts.
+bool ScalarEvolution::isLoopGuardedByCond(const Loop *L,
+ ICmpInst::Predicate Pred,
+ const SCEV *LHS, const SCEV *RHS) {
+ // Interpret a null as meaning no loop, where there is obviously no guard
+ // (interprocedural conditions notwithstanding).
+ if (!L) return false;
+
+ BasicBlock *Predecessor = getLoopPredecessor(L);
+ BasicBlock *PredecessorDest = L->getHeader();
- // Starting at the preheader, climb up the predecessor chain, as long as
- // there are predecessors that can be found that have unique successors
+ // Starting at the loop predecessor, climb up the predecessor chain, as long
+ // as there are predecessors that can be found that have unique successors
// leading to the original header.
- for (; Preheader;
- PreheaderDest = Preheader,
- Preheader = getPredecessorWithUniqueSuccessorForBB(Preheader)) {
+ for (; Predecessor;
+ PredecessorDest = Predecessor,
+ Predecessor = getPredecessorWithUniqueSuccessorForBB(Predecessor)) {
BranchInst *LoopEntryPredicate =
- dyn_cast<BranchInst>(Preheader->getTerminator());
+ dyn_cast<BranchInst>(Predecessor->getTerminator());
if (!LoopEntryPredicate ||
LoopEntryPredicate->isUnconditional())
continue;
Value *PreCondLHS = ICI->getOperand(0);
Value *PreCondRHS = ICI->getOperand(1);
ICmpInst::Predicate Cond;
- if (LoopEntryPredicate->getSuccessor(0) == PreheaderDest)
+ if (LoopEntryPredicate->getSuccessor(0) == PredecessorDest)
Cond = ICI->getPredicate();
else
Cond = ICI->getInversePredicate();
- switch (Cond) {
- case ICmpInst::ICMP_UGT:
- if (isSigned) continue;
- std::swap(PreCondLHS, PreCondRHS);
- Cond = ICmpInst::ICMP_ULT;
- break;
- case ICmpInst::ICMP_SGT:
- if (!isSigned) continue;
- std::swap(PreCondLHS, PreCondRHS);
- Cond = ICmpInst::ICMP_SLT;
- break;
- case ICmpInst::ICMP_ULT:
- if (isSigned) continue;
- break;
- case ICmpInst::ICMP_SLT:
- if (!isSigned) continue;
- break;
- default:
- continue;
- }
+ if (Cond == Pred)
+ ; // An exact match.
+ else if (!ICmpInst::isTrueWhenEqual(Cond) && Pred == ICmpInst::ICMP_NE)
+ ; // The actual condition is beyond sufficient.
+ else
+ // Check a few special cases.
+ switch (Cond) {
+ case ICmpInst::ICMP_UGT:
+ if (Pred == ICmpInst::ICMP_ULT) {
+ std::swap(PreCondLHS, PreCondRHS);
+ Cond = ICmpInst::ICMP_ULT;
+ break;
+ }
+ continue;
+ case ICmpInst::ICMP_SGT:
+ if (Pred == ICmpInst::ICMP_SLT) {
+ std::swap(PreCondLHS, PreCondRHS);
+ Cond = ICmpInst::ICMP_SLT;
+ break;
+ }
+ continue;
+ case ICmpInst::ICMP_NE:
+ // Expressions like (x >u 0) are often canonicalized to (x != 0),
+ // so check for this case by checking if the NE is comparing against
+ // a minimum or maximum constant.
+ if (!ICmpInst::isTrueWhenEqual(Pred))
+ if (ConstantInt *CI = dyn_cast<ConstantInt>(PreCondRHS)) {
+ const APInt &A = CI->getValue();
+ switch (Pred) {
+ case ICmpInst::ICMP_SLT:
+ if (A.isMaxSignedValue()) break;
+ continue;
+ case ICmpInst::ICMP_SGT:
+ if (A.isMinSignedValue()) break;
+ continue;
+ case ICmpInst::ICMP_ULT:
+ if (A.isMaxValue()) break;
+ continue;
+ case ICmpInst::ICMP_UGT:
+ if (A.isMinValue()) break;
+ continue;
+ default:
+ continue;
+ }
+ Cond = ICmpInst::ICMP_NE;
+ // NE is symmetric but the original comparison may not be. Swap
+ // the operands if necessary so that they match below.
+ if (isa<SCEVConstant>(LHS))
+ std::swap(PreCondLHS, PreCondRHS);
+ break;
+ }
+ continue;
+ default:
+ // We weren't able to reconcile the condition.
+ continue;
+ }
if (!PreCondLHS->getType()->isInteger()) continue;
SCEVHandle PreCondLHSSCEV = getSCEV(PreCondLHS);
SCEVHandle PreCondRHSSCEV = getSCEV(PreCondRHS);
if ((LHS == PreCondLHSSCEV && RHS == PreCondRHSSCEV) ||
- (LHS == SE.getNotSCEV(PreCondRHSSCEV) &&
- RHS == SE.getNotSCEV(PreCondLHSSCEV)))
+ (LHS == getNotSCEV(PreCondRHSSCEV) &&
+ RHS == getNotSCEV(PreCondLHSSCEV)))
return true;
}
/// 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, bool isSigned) {
+/// CouldNotCompute.
+ScalarEvolution::BackedgeTakenInfo ScalarEvolution::
+HowManyLessThans(const SCEV *LHS, const SCEV *RHS,
+ const Loop *L, bool isSigned) {
// Only handle: "ADDREC < LoopInvariant".
- if (!RHS->isLoopInvariant(L)) return UnknownValue;
+ if (!RHS->isLoopInvariant(L)) return CouldNotCompute;
- SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS);
+ const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS);
if (!AddRec || AddRec->getLoop() != L)
- return UnknownValue;
+ return CouldNotCompute;
if (AddRec->isAffine()) {
// FORNOW: We only support unit strides.
- SCEVHandle One = SE.getIntegerSCEV(1, RHS->getType());
- if (AddRec->getOperand(1) != One)
- return UnknownValue;
-
- // We know the LHS is of the form {n,+,1} and the RHS is some loop-invariant
- // m. So, we count the number of iterations in which {n,+,1} < m is true.
- // Note that we cannot simply return max(m-n,0) because it's not safe to
+ unsigned BitWidth = getTypeSizeInBits(AddRec->getType());
+ SCEVHandle Step = AddRec->getStepRecurrence(*this);
+ SCEVHandle NegOne = getIntegerSCEV(-1, AddRec->getType());
+
+ // TODO: handle non-constant strides.
+ const SCEVConstant *CStep = dyn_cast<SCEVConstant>(Step);
+ if (!CStep || CStep->isZero())
+ return CouldNotCompute;
+ if (CStep->isOne()) {
+ // With unit stride, the iteration never steps past the limit value.
+ } else if (CStep->getValue()->getValue().isStrictlyPositive()) {
+ if (const SCEVConstant *CLimit = dyn_cast<SCEVConstant>(RHS)) {
+ // Test whether a positive iteration iteration can step past the limit
+ // value and past the maximum value for its type in a single step.
+ if (isSigned) {
+ APInt Max = APInt::getSignedMaxValue(BitWidth);
+ if ((Max - CStep->getValue()->getValue())
+ .slt(CLimit->getValue()->getValue()))
+ return CouldNotCompute;
+ } else {
+ APInt Max = APInt::getMaxValue(BitWidth);
+ if ((Max - CStep->getValue()->getValue())
+ .ult(CLimit->getValue()->getValue()))
+ return CouldNotCompute;
+ }
+ } else
+ // TODO: handle non-constant limit values below.
+ return CouldNotCompute;
+ } else
+ // TODO: handle negative strides below.
+ return CouldNotCompute;
+
+ // We know the LHS is of the form {n,+,s} and the RHS is some loop-invariant
+ // m. So, we count the number of iterations in which {n,+,s} < m is true.
+ // Note that we cannot simply return max(m-n,0)/s because it's not safe to
// treat m-n as signed nor unsigned due to overflow possibility.
// First, we get the value of the LHS in the first iteration: n
SCEVHandle Start = AddRec->getOperand(0);
- if (executesAtLeastOnce(L, isSigned,
- SE.getMinusSCEV(AddRec->getOperand(0), One), RHS)) {
- // Since we know that the condition is true in order to enter the loop,
- // we know that it will run exactly m-n times.
- return SE.getMinusSCEV(RHS, Start);
- } else {
- // Then, we get the value of the LHS in the first iteration in which the
- // above condition doesn't hold. This equals to max(m,n).
- SCEVHandle End = isSigned ? SE.getSMaxExpr(RHS, Start)
- : SE.getUMaxExpr(RHS, Start);
-
- // Finally, we subtract these two values to get the number of times the
- // backedge is executed: max(m,n)-n.
- return SE.getMinusSCEV(End, Start);
- }
+ // Determine the minimum constant start value.
+ SCEVHandle MinStart = isa<SCEVConstant>(Start) ? Start :
+ getConstant(isSigned ? APInt::getSignedMinValue(BitWidth) :
+ APInt::getMinValue(BitWidth));
+
+ // If we know that the condition is true in order to enter the loop,
+ // then we know that it will run exactly (m-n)/s times. Otherwise, we
+ // only know that it will execute (max(m,n)-n)/s times. In both cases,
+ // the division must round up.
+ SCEVHandle End = RHS;
+ if (!isLoopGuardedByCond(L,
+ isSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
+ getMinusSCEV(Start, Step), RHS))
+ End = isSigned ? getSMaxExpr(RHS, Start)
+ : getUMaxExpr(RHS, Start);
+
+ // Determine the maximum constant end value.
+ SCEVHandle MaxEnd = isa<SCEVConstant>(End) ? End :
+ getConstant(isSigned ? APInt::getSignedMaxValue(BitWidth) :
+ APInt::getMaxValue(BitWidth));
+
+ // Finally, we subtract these two values and divide, rounding up, to get
+ // the number of times the backedge is executed.
+ SCEVHandle BECount = getUDivExpr(getAddExpr(getMinusSCEV(End, Start),
+ getAddExpr(Step, NegOne)),
+ Step);
+
+ // The maximum backedge count is similar, except using the minimum start
+ // value and the maximum end value.
+ SCEVHandle MaxBECount = getUDivExpr(getAddExpr(getMinusSCEV(MaxEnd,
+ MinStart),
+ getAddExpr(Step, NegOne)),
+ Step);
+
+ return BackedgeTakenInfo(BECount, MaxBECount);
}
- return UnknownValue;
+ return CouldNotCompute;
}
/// getNumIterationsInRange - Return the number of iterations of this loop that
SCEVHandle SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range,
ScalarEvolution &SE) const {
if (Range.isFullSet()) // Infinite loop.
- return new SCEVCouldNotCompute();
+ return SE.getCouldNotCompute();
// If the start is a non-zero constant, shift the range to simplify things.
- if (SCEVConstant *SC = dyn_cast<SCEVConstant>(getStart()))
+ if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(getStart()))
if (!SC->getValue()->isZero()) {
- std::vector<SCEVHandle> Operands(op_begin(), op_end());
+ SmallVector<SCEVHandle, 4> Operands(op_begin(), op_end());
Operands[0] = SE.getIntegerSCEV(0, SC->getType());
SCEVHandle Shifted = SE.getAddRecExpr(Operands, getLoop());
- if (SCEVAddRecExpr *ShiftedAddRec = dyn_cast<SCEVAddRecExpr>(Shifted))
+ if (const SCEVAddRecExpr *ShiftedAddRec =
+ dyn_cast<SCEVAddRecExpr>(Shifted))
return ShiftedAddRec->getNumIterationsInRange(
Range.subtract(SC->getValue()->getValue()), SE);
// This is strange and shouldn't happen.
- return new SCEVCouldNotCompute();
+ return SE.getCouldNotCompute();
}
// The only time we can solve this is when we have all constant indices.
// Otherwise, we cannot determine the overflow conditions.
for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
if (!isa<SCEVConstant>(getOperand(i)))
- return new SCEVCouldNotCompute();
+ return SE.getCouldNotCompute();
// Okay at this point we know that all elements of the chrec are constants and
// First check to see if the range contains zero. If not, the first
// iteration exits.
- if (!Range.contains(APInt(getBitWidth(),0)))
+ unsigned BitWidth = SE.getTypeSizeInBits(getType());
+ if (!Range.contains(APInt(BitWidth, 0)))
return SE.getConstant(ConstantInt::get(getType(),0));
if (isAffine()) {
// the upper value of the range must be the first possible exit value.
// If A is negative then the lower of the range is the last possible loop
// value. Also note that we already checked for a full range.
- APInt One(getBitWidth(),1);
+ APInt One(BitWidth,1);
APInt A = cast<SCEVConstant>(getOperand(1))->getValue()->getValue();
APInt End = A.sge(One) ? (Range.getUpper() - One) : Range.getLower();
// things must have happened.
ConstantInt *Val = EvaluateConstantChrecAtConstant(this, ExitValue, SE);
if (Range.contains(Val->getValue()))
- return new SCEVCouldNotCompute(); // Something strange happened
+ return SE.getCouldNotCompute(); // Something strange happened
// Ensure that the previous value is in the range. This is a sanity check.
assert(Range.contains(
// quadratic equation to solve it. To do this, we must frame our problem in
// terms of figuring out when zero is crossed, instead of when
// Range.getUpper() is crossed.
- std::vector<SCEVHandle> NewOps(op_begin(), op_end());
+ SmallVector<SCEVHandle, 4> NewOps(op_begin(), op_end());
NewOps[0] = SE.getNegativeSCEV(SE.getConstant(Range.getUpper()));
SCEVHandle NewAddRec = SE.getAddRecExpr(NewOps, getLoop());
// Next, solve the constructed addrec
std::pair<SCEVHandle,SCEVHandle> Roots =
SolveQuadraticEquation(cast<SCEVAddRecExpr>(NewAddRec), SE);
- SCEVConstant *R1 = dyn_cast<SCEVConstant>(Roots.first);
- SCEVConstant *R2 = dyn_cast<SCEVConstant>(Roots.second);
+ const SCEVConstant *R1 = dyn_cast<SCEVConstant>(Roots.first);
+ const SCEVConstant *R2 = dyn_cast<SCEVConstant>(Roots.second);
if (R1) {
// Pick the smallest positive root value.
if (ConstantInt *CB =
R1Val = EvaluateConstantChrecAtConstant(this, NextVal, SE);
if (!Range.contains(R1Val->getValue()))
return SE.getConstant(NextVal);
- return new SCEVCouldNotCompute(); // Something strange happened
+ return SE.getCouldNotCompute(); // Something strange happened
}
// If R1 was not in the range, then it is a good return value. Make
R1Val = EvaluateConstantChrecAtConstant(this, NextVal, SE);
if (Range.contains(R1Val->getValue()))
return R1;
- return new SCEVCouldNotCompute(); // Something strange happened
+ return SE.getCouldNotCompute(); // Something strange happened
}
}
}
- return new SCEVCouldNotCompute();
+ return SE.getCouldNotCompute();
}
+//===----------------------------------------------------------------------===//
+// SCEVCallbackVH Class Implementation
+//===----------------------------------------------------------------------===//
+
+void ScalarEvolution::SCEVCallbackVH::deleted() {
+ assert(SE && "SCEVCallbackVH called with a non-null ScalarEvolution!");
+ if (PHINode *PN = dyn_cast<PHINode>(getValPtr()))
+ SE->ConstantEvolutionLoopExitValue.erase(PN);
+ if (Instruction *I = dyn_cast<Instruction>(getValPtr()))
+ SE->ValuesAtScopes.erase(I);
+ SE->Scalars.erase(getValPtr());
+ // this now dangles!
+}
+
+void ScalarEvolution::SCEVCallbackVH::allUsesReplacedWith(Value *) {
+ assert(SE && "SCEVCallbackVH called with a non-null ScalarEvolution!");
+
+ // Forget all the expressions associated with users of the old value,
+ // so that future queries will recompute the expressions using the new
+ // value.
+ SmallVector<User *, 16> Worklist;
+ Value *Old = getValPtr();
+ bool DeleteOld = false;
+ for (Value::use_iterator UI = Old->use_begin(), UE = Old->use_end();
+ UI != UE; ++UI)
+ Worklist.push_back(*UI);
+ while (!Worklist.empty()) {
+ User *U = Worklist.pop_back_val();
+ // Deleting the Old value will cause this to dangle. Postpone
+ // that until everything else is done.
+ if (U == Old) {
+ DeleteOld = true;
+ continue;
+ }
+ if (PHINode *PN = dyn_cast<PHINode>(U))
+ SE->ConstantEvolutionLoopExitValue.erase(PN);
+ if (Instruction *I = dyn_cast<Instruction>(U))
+ SE->ValuesAtScopes.erase(I);
+ if (SE->Scalars.erase(U))
+ for (Value::use_iterator UI = U->use_begin(), UE = U->use_end();
+ UI != UE; ++UI)
+ Worklist.push_back(*UI);
+ }
+ if (DeleteOld) {
+ if (PHINode *PN = dyn_cast<PHINode>(Old))
+ SE->ConstantEvolutionLoopExitValue.erase(PN);
+ if (Instruction *I = dyn_cast<Instruction>(Old))
+ SE->ValuesAtScopes.erase(I);
+ SE->Scalars.erase(Old);
+ // this now dangles!
+ }
+ // this may dangle!
+}
+
+ScalarEvolution::SCEVCallbackVH::SCEVCallbackVH(Value *V, ScalarEvolution *se)
+ : CallbackVH(V), SE(se) {}
+
//===----------------------------------------------------------------------===//
// ScalarEvolution Class Implementation
//===----------------------------------------------------------------------===//
+ScalarEvolution::ScalarEvolution()
+ : FunctionPass(&ID), CouldNotCompute(new SCEVCouldNotCompute()) {
+}
+
bool ScalarEvolution::runOnFunction(Function &F) {
- Impl = new ScalarEvolutionsImpl(*this, F, getAnalysis<LoopInfo>());
+ this->F = &F;
+ LI = &getAnalysis<LoopInfo>();
+ TD = getAnalysisIfAvailable<TargetData>();
return false;
}
void ScalarEvolution::releaseMemory() {
- delete (ScalarEvolutionsImpl*)Impl;
- Impl = 0;
+ Scalars.clear();
+ BackedgeTakenCounts.clear();
+ ConstantEvolutionLoopExitValue.clear();
+ ValuesAtScopes.clear();
}
void ScalarEvolution::getAnalysisUsage(AnalysisUsage &AU) const {
AU.addRequiredTransitive<LoopInfo>();
}
-SCEVHandle ScalarEvolution::getSCEV(Value *V) const {
- 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);
+bool ScalarEvolution::hasLoopInvariantBackedgeTakenCount(const Loop *L) {
+ return !isa<SCEVCouldNotCompute>(getBackedgeTakenCount(L));
}
-
-SCEVHandle ScalarEvolution::getIterationCount(const Loop *L) const {
- return ((ScalarEvolutionsImpl*)Impl)->getIterationCount(L);
-}
-
-bool ScalarEvolution::hasLoopInvariantIterationCount(const Loop *L) const {
- return !isa<SCEVCouldNotCompute>(getIterationCount(L));
-}
-
-SCEVHandle ScalarEvolution::getSCEVAtScope(Value *V, const Loop *L) const {
- return ((ScalarEvolutionsImpl*)Impl)->getSCEVAtScope(getSCEV(V), L);
-}
-
-void ScalarEvolution::deleteValueFromRecords(Value *V) const {
- return ((ScalarEvolutionsImpl*)Impl)->deleteValueFromRecords(V);
-}
-
-static void PrintLoopInfo(std::ostream &OS, const ScalarEvolution *SE,
+static void PrintLoopInfo(raw_ostream &OS, ScalarEvolution *SE,
const Loop *L) {
// Print all inner loops first
for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
if (ExitBlocks.size() != 1)
OS << "<multiple exits> ";
- if (SE->hasLoopInvariantIterationCount(L)) {
- OS << *SE->getIterationCount(L) << " iterations! ";
+ if (SE->hasLoopInvariantBackedgeTakenCount(L)) {
+ OS << "backedge-taken count is " << *SE->getBackedgeTakenCount(L);
} else {
- OS << "Unpredictable iteration count. ";
+ OS << "Unpredictable backedge-taken count. ";
}
OS << "\n";
}
-void ScalarEvolution::print(std::ostream &OS, const Module* ) const {
- Function &F = ((ScalarEvolutionsImpl*)Impl)->F;
- LoopInfo &LI = ((ScalarEvolutionsImpl*)Impl)->LI;
+void ScalarEvolution::print(raw_ostream &OS, const Module* ) const {
+ // ScalarEvolution's implementaiton of the print method is to print
+ // out SCEV values of all instructions that are interesting. Doing
+ // this potentially causes it to create new SCEV objects though,
+ // which technically conflicts with the const qualifier. This isn't
+ // observable from outside the class though (the hasSCEV function
+ // notwithstanding), so casting away the const isn't dangerous.
+ ScalarEvolution &SE = *const_cast<ScalarEvolution*>(this);
- OS << "Classifying expressions for: " << F.getName() << "\n";
+ OS << "Classifying expressions for: " << F->getName() << "\n";
for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)
- if (I->getType()->isInteger()) {
+ if (isSCEVable(I->getType())) {
OS << *I;
OS << " --> ";
- SCEVHandle SV = getSCEV(&*I);
+ SCEVHandle SV = SE.getSCEV(&*I);
SV->print(OS);
OS << "\t\t";
- if (const Loop *L = LI.getLoopFor((*I).getParent())) {
+ if (const Loop *L = LI->getLoopFor((*I).getParent())) {
OS << "Exits: ";
- SCEVHandle ExitValue = getSCEVAtScope(&*I, L->getParentLoop());
- if (isa<SCEVCouldNotCompute>(ExitValue)) {
+ SCEVHandle ExitValue = SE.getSCEVAtScope(&*I, L->getParentLoop());
+ if (!ExitValue->isLoopInvariant(L)) {
OS << "<<Unknown>>";
} else {
OS << *ExitValue;
}
}
-
OS << "\n";
}
- OS << "Determining loop execution counts for: " << F.getName() << "\n";
- for (LoopInfo::iterator I = LI.begin(), E = LI.end(); I != E; ++I)
- PrintLoopInfo(OS, this, *I);
+ OS << "Determining loop execution counts for: " << F->getName() << "\n";
+ for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I)
+ PrintLoopInfo(OS, &SE, *I);
+}
+
+void ScalarEvolution::print(std::ostream &o, const Module *M) const {
+ raw_os_ostream OS(o);
+ print(OS, M);
}
projects / oota-llvm.git / blobdiff