// There are several aspects to this library. First is the representation of
// scalar expressions, which are represented as subclasses of the SCEV class.
// These classes are used to represent certain types of subexpressions that we
-// can handle. These classes are reference counted, managed by the SCEVHandle
+// can handle. These classes are reference counted, managed by the const SCEV*
// class. We only create one SCEV of a particular shape, so pointer-comparisons
// for equality are legal.
//
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Assembly/Writer.h"
#include "llvm/Target/TargetData.h"
#include "llvm/Support/CommandLine.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/raw_ostream.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
-#include <ostream>
#include <algorithm>
using namespace llvm;
return false;
}
-SCEVCouldNotCompute::SCEVCouldNotCompute() : SCEV(scCouldNotCompute) {}
-SCEVCouldNotCompute::~SCEVCouldNotCompute() {}
+bool SCEV::isAllOnesValue() const {
+ if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(this))
+ return SC->getValue()->isAllOnesValue();
+ return false;
+}
+
+SCEVCouldNotCompute::SCEVCouldNotCompute() :
+ SCEV(scCouldNotCompute) {}
bool SCEVCouldNotCompute::isLoopInvariant(const Loop *L) const {
assert(0 && "Attempt to use a SCEVCouldNotCompute object!");
return false;
}
-SCEVHandle SCEVCouldNotCompute::
-replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
- const SCEVHandle &Conc,
+const SCEV* SCEVCouldNotCompute::
+replaceSymbolicValuesWithConcrete(const SCEV* Sym,
+ const SCEV* Conc,
ScalarEvolution &SE) const {
return this;
}
// SCEVConstants - Only allow the creation of one SCEVConstant for any
-// particular value. Don't use a SCEVHandle here, or else the object will
+// particular value. Don't use a const SCEV* here, or else the object will
// never be deleted!
-static ManagedStatic<std::map<ConstantInt*, SCEVConstant*> > SCEVConstants;
-
-SCEVConstant::~SCEVConstant() {
- SCEVConstants->erase(V);
-}
-
-SCEVHandle ScalarEvolution::getConstant(ConstantInt *V) {
- SCEVConstant *&R = (*SCEVConstants)[V];
+const SCEV* ScalarEvolution::getConstant(ConstantInt *V) {
+ SCEVConstant *&R = SCEVConstants[V];
if (R == 0) R = new SCEVConstant(V);
return R;
}
-SCEVHandle ScalarEvolution::getConstant(const APInt& Val) {
+const SCEV* ScalarEvolution::getConstant(const APInt& Val) {
return getConstant(ConstantInt::get(Val));
}
+const SCEV*
+ScalarEvolution::getConstant(const Type *Ty, uint64_t V, bool isSigned) {
+ return getConstant(ConstantInt::get(cast<IntegerType>(Ty), V, isSigned));
+}
+
const Type *SCEVConstant::getType() const { return V->getType(); }
void SCEVConstant::print(raw_ostream &OS) const {
}
SCEVCastExpr::SCEVCastExpr(unsigned SCEVTy,
- const SCEVHandle &op, const Type *ty)
+ const SCEV* 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
+// particular input. Don't use a const SCEV* here, or else the object will
// never be deleted!
-static ManagedStatic<std::map<std::pair<const SCEV*, const Type*>,
- SCEVTruncateExpr*> > SCEVTruncates;
-SCEVTruncateExpr::SCEVTruncateExpr(const SCEVHandle &op, const Type *ty)
+SCEVTruncateExpr::SCEVTruncateExpr(const SCEV* op, const Type *ty)
: SCEVCastExpr(scTruncate, op, ty) {
assert((Op->getType()->isInteger() || isa<PointerType>(Op->getType())) &&
(Ty->isInteger() || isa<PointerType>(Ty)) &&
"Cannot truncate non-integer value!");
}
-SCEVTruncateExpr::~SCEVTruncateExpr() {
- SCEVTruncates->erase(std::make_pair(Op, 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
+// particular input. Don't use a const SCEV* here, or else the object will never
// be deleted!
-static ManagedStatic<std::map<std::pair<const SCEV*, const Type*>,
- SCEVZeroExtendExpr*> > SCEVZeroExtends;
-SCEVZeroExtendExpr::SCEVZeroExtendExpr(const SCEVHandle &op, const Type *ty)
+SCEVZeroExtendExpr::SCEVZeroExtendExpr(const SCEV* op, const Type *ty)
: SCEVCastExpr(scZeroExtend, op, ty) {
assert((Op->getType()->isInteger() || isa<PointerType>(Op->getType())) &&
(Ty->isInteger() || isa<PointerType>(Ty)) &&
"Cannot zero extend non-integer value!");
}
-SCEVZeroExtendExpr::~SCEVZeroExtendExpr() {
- SCEVZeroExtends->erase(std::make_pair(Op, 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
+// particular input. Don't use a const SCEV* here, or else the object will never
// be deleted!
-static ManagedStatic<std::map<std::pair<const SCEV*, const Type*>,
- SCEVSignExtendExpr*> > SCEVSignExtends;
-SCEVSignExtendExpr::SCEVSignExtendExpr(const SCEVHandle &op, const Type *ty)
+SCEVSignExtendExpr::SCEVSignExtendExpr(const SCEV* op, const Type *ty)
: SCEVCastExpr(scSignExtend, op, ty) {
assert((Op->getType()->isInteger() || isa<PointerType>(Op->getType())) &&
(Ty->isInteger() || isa<PointerType>(Ty)) &&
"Cannot sign extend non-integer value!");
}
-SCEVSignExtendExpr::~SCEVSignExtendExpr() {
- SCEVSignExtends->erase(std::make_pair(Op, 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
+// particular input. Don't use a const SCEV* here, or else the object will never
// be deleted!
-static ManagedStatic<std::map<std::pair<unsigned, std::vector<const SCEV*> >,
- SCEVCommutativeExpr*> > SCEVCommExprs;
-
-SCEVCommutativeExpr::~SCEVCommutativeExpr() {
- std::vector<const SCEV*> SCEVOps(Operands.begin(), Operands.end());
- SCEVCommExprs->erase(std::make_pair(getSCEVType(), SCEVOps));
-}
void SCEVCommutativeExpr::print(raw_ostream &OS) const {
assert(Operands.size() > 1 && "This plus expr shouldn't exist!");
OS << ")";
}
-SCEVHandle SCEVCommutativeExpr::
-replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
- const SCEVHandle &Conc,
+const SCEV* SCEVCommutativeExpr::
+replaceSymbolicValuesWithConcrete(const SCEV* Sym,
+ const SCEV* Conc,
ScalarEvolution &SE) const {
for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
- SCEVHandle H =
+ const SCEV* H =
getOperand(i)->replaceSymbolicValuesWithConcrete(Sym, Conc, SE);
if (H != getOperand(i)) {
- std::vector<SCEVHandle> NewOps;
+ SmallVector<const SCEV*, 8> NewOps;
NewOps.reserve(getNumOperands());
for (unsigned j = 0; j != i; ++j)
NewOps.push_back(getOperand(j));
// 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
+// input. Don't use a const SCEV* here, or else the object will never be
// deleted!
-static ManagedStatic<std::map<std::pair<const SCEV*, const SCEV*>,
- SCEVUDivExpr*> > SCEVUDivs;
-
-SCEVUDivExpr::~SCEVUDivExpr() {
- SCEVUDivs->erase(std::make_pair(LHS, RHS));
-}
bool SCEVUDivExpr::dominates(BasicBlock *BB, DominatorTree *DT) const {
return LHS->dominates(BB, DT) && RHS->dominates(BB, DT);
}
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
+// particular input. Don't use a const SCEV* here, or else the object will never
// be deleted!
-static ManagedStatic<std::map<std::pair<const Loop *,
- std::vector<const SCEV*> >,
- SCEVAddRecExpr*> > SCEVAddRecExprs;
-SCEVAddRecExpr::~SCEVAddRecExpr() {
- std::vector<const SCEV*> SCEVOps(Operands.begin(), Operands.end());
- SCEVAddRecExprs->erase(std::make_pair(L, SCEVOps));
-}
-
-SCEVHandle SCEVAddRecExpr::
-replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
- const SCEVHandle &Conc,
+const SCEV* SCEVAddRecExpr::
+replaceSymbolicValuesWithConcrete(const SCEV* Sym,
+ const SCEV* Conc,
ScalarEvolution &SE) const {
for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
- SCEVHandle H =
+ const SCEV* H =
getOperand(i)->replaceSymbolicValuesWithConcrete(Sym, Conc, SE);
if (H != getOperand(i)) {
- std::vector<SCEVHandle> NewOps;
+ SmallVector<const SCEV*, 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);
}
}
// SCEVUnknowns - Only allow the creation of one SCEVUnknown for any particular
-// value. Don't use a SCEVHandle here, or else the object will never be
+// value. Don't use a const SCEV* here, or else the object will never be
// deleted!
-static ManagedStatic<std::map<Value*, SCEVUnknown*> > SCEVUnknowns;
-
-SCEVUnknown::~SCEVUnknown() { SCEVUnknowns->erase(V); }
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;
}
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();
return false;
}
- // Constant sorting doesn't matter since they'll be folded.
- if (isa<SCEVConstant>(LHS))
- 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)) {
/// 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<const SCEV*> &Ops,
LoopInfo *LI) {
if (Ops.size() < 2) return; // Noop
if (Ops.size() == 2) {
//===----------------------------------------------------------------------===//
/// BinomialCoefficient - Compute BC(It, K). The result has width W.
-// Assume, K > 0.
-static SCEVHandle BinomialCoefficient(SCEVHandle It, unsigned K,
+/// Assume, K > 0.
+static const SCEV* BinomialCoefficient(const SCEV* It, unsigned K,
ScalarEvolution &SE,
const Type* ResultTy) {
// Handle the simplest case efficiently.
// Calculate the product, at width T+W
const IntegerType *CalculationTy = IntegerType::get(CalculationBits);
- SCEVHandle Dividend = SE.getTruncateOrZeroExtend(It, CalculationTy);
+ const SCEV* Dividend = SE.getTruncateOrZeroExtend(It, CalculationTy);
for (unsigned i = 1; i != K; ++i) {
- SCEVHandle S = SE.getMinusSCEV(It, SE.getIntegerSCEV(i, It->getType()));
+ const SCEV* S = SE.getMinusSCEV(It, SE.getIntegerSCEV(i, It->getType()));
Dividend = SE.getMulExpr(Dividend,
SE.getTruncateOrZeroExtend(S, CalculationTy));
}
// Divide by 2^T
- SCEVHandle DivResult = SE.getUDivExpr(Dividend, SE.getConstant(DivFactor));
+ const SCEV* DivResult = SE.getUDivExpr(Dividend, SE.getConstant(DivFactor));
// Truncate the result, and divide by K! / 2^T.
///
/// where BC(It, k) stands for binomial coefficient.
///
-SCEVHandle SCEVAddRecExpr::evaluateAtIteration(SCEVHandle It,
+const SCEV* SCEVAddRecExpr::evaluateAtIteration(const SCEV* It,
ScalarEvolution &SE) const {
- SCEVHandle Result = getStart();
+ const SCEV* Result = getStart();
for (unsigned i = 1, e = getNumOperands(); i != e; ++i) {
// 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, getType());
+ const SCEV* Coeff = BinomialCoefficient(It, i, SE, getType());
if (isa<SCEVCouldNotCompute>(Coeff))
return Coeff;
// SCEV Expression folder implementations
//===----------------------------------------------------------------------===//
-SCEVHandle ScalarEvolution::getTruncateExpr(const SCEVHandle &Op,
+const SCEV* ScalarEvolution::getTruncateExpr(const SCEV* Op,
const Type *Ty) {
assert(getTypeSizeInBits(Op->getType()) > getTypeSizeInBits(Ty) &&
"This is not a truncating conversion!");
Ty = getEffectiveSCEVType(Ty);
if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op))
- return getUnknown(
- ConstantExpr::getTrunc(SC->getValue(), Ty));
+ return getConstant(
+ cast<ConstantInt>(ConstantExpr::getTrunc(SC->getValue(), Ty)));
// trunc(trunc(x)) --> trunc(x)
if (const SCEVTruncateExpr *ST = dyn_cast<SCEVTruncateExpr>(Op))
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 the input value is a chrec scev, truncate the chrec's operands.
if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Op)) {
- std::vector<SCEVHandle> Operands;
+ SmallVector<const SCEV*, 4> Operands;
for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i)
Operands.push_back(getTruncateExpr(AddRec->getOperand(i), Ty));
return getAddRecExpr(Operands, AddRec->getLoop());
}
- SCEVTruncateExpr *&Result = (*SCEVTruncates)[std::make_pair(Op, Ty)];
+ SCEVTruncateExpr *&Result = SCEVTruncates[std::make_pair(Op, Ty)];
if (Result == 0) Result = new SCEVTruncateExpr(Op, Ty);
return Result;
}
-SCEVHandle ScalarEvolution::getZeroExtendExpr(const SCEVHandle &Op,
+const SCEV* ScalarEvolution::getZeroExtendExpr(const SCEV* Op,
const Type *Ty) {
assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) &&
"This is not an extending conversion!");
const Type *IntTy = getEffectiveSCEVType(Ty);
Constant *C = ConstantExpr::getZExt(SC->getValue(), IntTy);
if (IntTy != Ty) C = ConstantExpr::getIntToPtr(C, Ty);
- return getUnknown(C);
+ return getConstant(cast<ConstantInt>(C));
}
// zext(zext(x)) --> zext(x)
// 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());
+ const SCEV* 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);
+ const SCEV* Start = AR->getStart();
+ const SCEV* 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 =
+ const SCEV* CastedMaxBECount =
getTruncateOrZeroExtend(MaxBECount, Start->getType());
- if (MaxBECount ==
- getTruncateOrZeroExtend(CastedMaxBECount, MaxBECount->getType())) {
+ const SCEV* 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 =
+ const SCEV* ZMul =
getMulExpr(CastedMaxBECount,
getTruncateOrZeroExtend(Step, Start->getType()));
- SCEVHandle Add = getAddExpr(Start, ZMul);
- if (getZeroExtendExpr(Add, WideTy) ==
- getAddExpr(getZeroExtendExpr(Start, WideTy),
- getMulExpr(getZeroExtendExpr(CastedMaxBECount, WideTy),
- getZeroExtendExpr(Step, WideTy))))
+ const SCEV* Add = getAddExpr(Start, ZMul);
+ const SCEV* 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),
// Similar to above, only this time treat the step value as signed.
// This covers loops that count down.
- SCEVHandle SMul =
+ const SCEV* SMul =
getMulExpr(CastedMaxBECount,
getTruncateOrSignExtend(Step, Start->getType()));
Add = getAddExpr(Start, SMul);
- if (getZeroExtendExpr(Add, WideTy) ==
- getAddExpr(getZeroExtendExpr(Start, WideTy),
- getMulExpr(getZeroExtendExpr(CastedMaxBECount, WideTy),
- getSignExtendExpr(Step, WideTy))))
+ 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),
}
}
- SCEVZeroExtendExpr *&Result = (*SCEVZeroExtends)[std::make_pair(Op, Ty)];
+ SCEVZeroExtendExpr *&Result = SCEVZeroExtends[std::make_pair(Op, Ty)];
if (Result == 0) Result = new SCEVZeroExtendExpr(Op, Ty);
return Result;
}
-SCEVHandle ScalarEvolution::getSignExtendExpr(const SCEVHandle &Op,
+const SCEV* ScalarEvolution::getSignExtendExpr(const SCEV* Op,
const Type *Ty) {
assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) &&
"This is not an extending conversion!");
const Type *IntTy = getEffectiveSCEVType(Ty);
Constant *C = ConstantExpr::getSExt(SC->getValue(), IntTy);
if (IntTy != Ty) C = ConstantExpr::getIntToPtr(C, Ty);
- return getUnknown(C);
+ return getConstant(cast<ConstantInt>(C));
}
// sext(sext(x)) --> sext(x)
// 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());
+ const SCEV* 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);
+ const SCEV* Start = AR->getStart();
+ const SCEV* 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 =
+ const SCEV* CastedMaxBECount =
getTruncateOrZeroExtend(MaxBECount, Start->getType());
- if (MaxBECount ==
- getTruncateOrZeroExtend(CastedMaxBECount, MaxBECount->getType())) {
+ const SCEV* 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 =
+ const SCEV* SMul =
getMulExpr(CastedMaxBECount,
getTruncateOrSignExtend(Step, Start->getType()));
- SCEVHandle Add = getAddExpr(Start, SMul);
- if (getSignExtendExpr(Add, WideTy) ==
- getAddExpr(getSignExtendExpr(Start, WideTy),
- getMulExpr(getZeroExtendExpr(CastedMaxBECount, WideTy),
- getSignExtendExpr(Step, WideTy))))
+ const SCEV* Add = getAddExpr(Start, SMul);
+ const SCEV* 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),
}
}
- SCEVSignExtendExpr *&Result = (*SCEVSignExtends)[std::make_pair(Op, Ty)];
+ SCEVSignExtendExpr *&Result = SCEVSignExtends[std::make_pair(Op, Ty)];
if (Result == 0) Result = new SCEVSignExtendExpr(Op, Ty);
return Result;
}
-// get - Get a canonical add expression, or something simpler if possible.
-SCEVHandle ScalarEvolution::getAddExpr(std::vector<SCEVHandle> &Ops) {
+/// getAnyExtendExpr - Return a SCEV for the given operand extended with
+/// unspecified bits out to the given type.
+///
+const SCEV* ScalarEvolution::getAnyExtendExpr(const SCEV* 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)) {
+ const SCEV* 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.
+ const SCEV* ZExt = getZeroExtendExpr(Op, Ty);
+ if (!isa<SCEVZeroExtendExpr>(ZExt))
+ return ZExt;
+
+ // Next try a sext cast. If the cast is folded, use it.
+ const SCEV* 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;
+}
+
+/// 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<const SCEV*, APInt> &M,
+ SmallVector<const SCEV*, 8> &NewOps,
+ APInt &AccumulatedConstant,
+ const SmallVectorImpl<const SCEV*> &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<const SCEV*, 4> MulOps(Mul->op_begin()+1, Mul->op_end());
+ const SCEV* Key = SE.getMulExpr(MulOps);
+ std::pair<DenseMap<const SCEV*, 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<const SCEV*, 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.
+const SCEV* ScalarEvolution::getAddExpr(SmallVectorImpl<const SCEV*> &Ops) {
assert(!Ops.empty() && "Cannot get empty add!");
if (Ops.size() == 1) return Ops[0];
#ifndef NDEBUG
assert(Idx < Ops.size());
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]);
}
if (Ops[i] == Ops[i+1]) { // X + Y + Y --> X + Y*2
// Found a match, merge the two values into a multiply, and add any
// remaining values to the result.
- SCEVHandle Two = getIntegerSCEV(2, Ty);
- SCEVHandle Mul = getMulExpr(Ops[i], Two);
+ const SCEV* Two = getIntegerSCEV(2, Ty);
+ const SCEV* Mul = getMulExpr(Ops[i], Two);
if (Ops.size() == 2)
return Mul;
Ops.erase(Ops.begin()+i, Ops.begin()+i+2);
const SCEVTruncateExpr *Trunc = cast<SCEVTruncateExpr>(Ops[Idx]);
const Type *DstType = Trunc->getType();
const Type *SrcType = Trunc->getOperand()->getType();
- std::vector<SCEVHandle> LargeOps;
+ SmallVector<const SCEV*, 8> LargeOps;
bool Ok = true;
// Check all the operands to see if they can be represented in the
// source type of the truncate.
// is much more likely to be foldable here.
LargeOps.push_back(getSignExtendExpr(C, SrcType));
} else if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(Ops[i])) {
- std::vector<SCEVHandle> LargeMulOps;
+ SmallVector<const SCEV*, 8> LargeMulOps;
for (unsigned j = 0, f = M->getNumOperands(); j != f && Ok; ++j) {
if (const SCEVTruncateExpr *T =
dyn_cast<SCEVTruncateExpr>(M->getOperand(j))) {
}
if (Ok) {
// Evaluate the expression in the larger type.
- SCEVHandle Fold = getAddExpr(LargeOps);
+ const SCEV* 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);
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<const SCEV*, APInt> M;
+ SmallVector<const SCEV*, 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<const SCEV*, 4>, APIntCompare> MulOpLists;
+ for (SmallVector<const SCEV*, 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<const SCEV*, 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 (unsigned MulOp = 0, e = Mul->getNumOperands(); MulOp != e; ++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);
+ const SCEV* 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<const SCEV*, 4> MulOps(Mul->op_begin(), Mul->op_end());
MulOps.erase(MulOps.begin()+MulOp);
InnerMul = getMulExpr(MulOps);
}
- SCEVHandle One = getIntegerSCEV(1, Ty);
- SCEVHandle AddOne = getAddExpr(InnerMul, One);
- SCEVHandle OuterMul = getMulExpr(AddOne, Ops[AddOp]);
+ const SCEV* One = getIntegerSCEV(1, Ty);
+ const SCEV* AddOne = getAddExpr(InnerMul, One);
+ const SCEV* OuterMul = getMulExpr(AddOne, Ops[AddOp]);
if (Ops.size() == 2) return OuterMul;
if (AddOp < Idx) {
Ops.erase(Ops.begin()+AddOp);
OMulOp != e; ++OMulOp)
if (OtherMul->getOperand(OMulOp) == MulOpSCEV) {
// Fold X + (A*B*C) + (A*D*E) --> X + (A*(B*C+D*E))
- SCEVHandle InnerMul1 = Mul->getOperand(MulOp == 0);
+ const SCEV* InnerMul1 = Mul->getOperand(MulOp == 0);
if (Mul->getNumOperands() != 2) {
- std::vector<SCEVHandle> MulOps(Mul->op_begin(), Mul->op_end());
+ SmallVector<const SCEV*, 4> MulOps(Mul->op_begin(), Mul->op_end());
MulOps.erase(MulOps.begin()+MulOp);
InnerMul1 = getMulExpr(MulOps);
}
- SCEVHandle InnerMul2 = OtherMul->getOperand(OMulOp == 0);
+ const SCEV* InnerMul2 = OtherMul->getOperand(OMulOp == 0);
if (OtherMul->getNumOperands() != 2) {
- std::vector<SCEVHandle> MulOps(OtherMul->op_begin(),
+ SmallVector<const SCEV*, 4> MulOps(OtherMul->op_begin(),
OtherMul->op_end());
MulOps.erase(MulOps.begin()+OMulOp);
InnerMul2 = getMulExpr(MulOps);
}
- SCEVHandle InnerMulSum = getAddExpr(InnerMul1,InnerMul2);
- SCEVHandle OuterMul = getMulExpr(MulOpSCEV, InnerMulSum);
+ const SCEV* InnerMulSum = getAddExpr(InnerMul1,InnerMul2);
+ const SCEV* OuterMul = getMulExpr(MulOpSCEV, InnerMulSum);
if (Ops.size() == 2) return OuterMul;
Ops.erase(Ops.begin()+Idx);
Ops.erase(Ops.begin()+OtherMulIdx-1);
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;
+ SmallVector<const SCEV*, 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())) {
// NLI + LI + {Start,+,Step} --> NLI + {LI+Start,+,Step}
LIOps.push_back(AddRec->getStart());
- std::vector<SCEVHandle> AddRecOps(AddRec->op_begin(), AddRec->op_end());
+ SmallVector<const SCEV*, 4> AddRecOps(AddRec->op_begin(),
+ AddRec->op_end());
AddRecOps[0] = getAddExpr(LIOps);
- SCEVHandle NewRec = getAddRecExpr(AddRecOps, AddRec->getLoop());
+ const SCEV* NewRec = getAddRecExpr(AddRecOps, AddRec->getLoop());
// If all of the other operands were loop invariant, we are done.
if (Ops.size() == 1) return NewRec;
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<const SCEV*, 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,
}
NewOps[i] = getAddExpr(NewOps[i], OtherAddRec->getOperand(i));
}
- SCEVHandle NewAddRec = getAddRecExpr(NewOps, AddRec->getLoop());
+ const SCEV* NewAddRec = getAddRecExpr(NewOps, AddRec->getLoop());
if (Ops.size() == 2) return NewAddRec;
// 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<const SCEV*> SCEVOps(Ops.begin(), Ops.end());
- SCEVCommutativeExpr *&Result = (*SCEVCommExprs)[std::make_pair(scAddExpr,
+ SCEVCommutativeExpr *&Result = SCEVCommExprs[std::make_pair(scAddExpr,
SCEVOps)];
if (Result == 0) Result = new SCEVAddExpr(Ops);
return Result;
}
-SCEVHandle ScalarEvolution::getMulExpr(std::vector<SCEVHandle> &Ops) {
+/// getMulExpr - Get a canonical multiply expression, or something simpler if
+/// possible.
+const SCEV* ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV*> &Ops) {
assert(!Ops.empty() && "Cannot get empty mul!");
#ifndef NDEBUG
for (unsigned i = 1, e = Ops.size(); i != e; ++i)
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;
+ SmallVector<const SCEV*, 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())) {
// 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<const SCEV*, 4> NewOps;
NewOps.reserve(AddRec->getNumOperands());
if (LIOps.size() == 1) {
const SCEV *Scale = LIOps[0];
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<const SCEV*, 4> MulOps(LIOps.begin(), LIOps.end());
MulOps.push_back(AddRec->getOperand(i));
NewOps.push_back(getMulExpr(MulOps));
}
}
- SCEVHandle NewRec = getAddRecExpr(NewOps, AddRec->getLoop());
+ const SCEV* NewRec = getAddRecExpr(NewOps, AddRec->getLoop());
// If all of the other operands were loop invariant, we are done.
if (Ops.size() == 1) return NewRec;
if (AddRec->getLoop() == OtherAddRec->getLoop()) {
// F * G --> {A,+,B} * {C,+,D} --> {A*C,+,F*D + G*B + B*D}
const SCEVAddRecExpr *F = AddRec, *G = OtherAddRec;
- SCEVHandle NewStart = getMulExpr(F->getStart(),
+ const SCEV* NewStart = getMulExpr(F->getStart(),
G->getStart());
- SCEVHandle B = F->getStepRecurrence(*this);
- SCEVHandle D = G->getStepRecurrence(*this);
- SCEVHandle NewStep = getAddExpr(getMulExpr(F, D),
+ const SCEV* B = F->getStepRecurrence(*this);
+ const SCEV* D = G->getStepRecurrence(*this);
+ const SCEV* NewStep = getAddExpr(getMulExpr(F, D),
getMulExpr(G, B),
getMulExpr(B, D));
- SCEVHandle NewAddRec = getAddRecExpr(NewStart, NewStep,
+ const SCEV* NewAddRec = getAddRecExpr(NewStart, NewStep,
F->getLoop());
if (Ops.size() == 2) return NewAddRec;
// 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<const SCEV*> SCEVOps(Ops.begin(), Ops.end());
- SCEVCommutativeExpr *&Result = (*SCEVCommExprs)[std::make_pair(scMulExpr,
+ SCEVCommutativeExpr *&Result = SCEVCommExprs[std::make_pair(scMulExpr,
SCEVOps)];
if (Result == 0)
Result = new SCEVMulExpr(Ops);
return Result;
}
-SCEVHandle ScalarEvolution::getUDivExpr(const SCEVHandle &LHS,
- const SCEVHandle &RHS) {
+/// getUDivExpr - Get a canonical multiply expression, or something simpler if
+/// possible.
+const SCEV* ScalarEvolution::getUDivExpr(const SCEV* LHS,
+ const SCEV* RHS) {
assert(getEffectiveSCEVType(LHS->getType()) ==
getEffectiveSCEVType(RHS->getType()) &&
"SCEVUDivExpr operand types don't match!");
getAddRecExpr(getZeroExtendExpr(AR->getStart(), ExtTy),
getZeroExtendExpr(Step, ExtTy),
AR->getLoop())) {
- std::vector<SCEVHandle> Operands;
+ SmallVector<const SCEV*, 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)) {
- std::vector<SCEVHandle> Operands;
+ SmallVector<const SCEV*, 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);
+ const SCEV* Op = M->getOperand(i);
+ const SCEV* Div = getUDivExpr(Op, RHSC);
if (!isa<SCEVUDivExpr>(Div) && getMulExpr(Div, RHSC) == Op) {
- Operands = M->getOperands();
+ const SmallVectorImpl<const SCEV*> &MOperands = M->getOperands();
+ Operands = SmallVector<const SCEV*, 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)) {
- std::vector<SCEVHandle> Operands;
+ SmallVector<const SCEV*, 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);
+ const SCEV* Op = getUDivExpr(A->getOperand(i), RHS);
if (isa<SCEVUDivExpr>(Op) || getMulExpr(Op, RHS) != A->getOperand(i))
break;
Operands.push_back(Op);
if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(LHS)) {
Constant *LHSCV = LHSC->getValue();
Constant *RHSCV = RHSC->getValue();
- return getUnknown(ConstantExpr::getUDiv(LHSCV, RHSCV));
+ return getConstant(cast<ConstantInt>(ConstantExpr::getUDiv(LHSCV,
+ RHSCV)));
}
}
- SCEVUDivExpr *&Result = (*SCEVUDivs)[std::make_pair(LHS, RHS)];
+ 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.
-SCEVHandle ScalarEvolution::getAddRecExpr(const SCEVHandle &Start,
- const SCEVHandle &Step, const Loop *L) {
- std::vector<SCEVHandle> Operands;
+/// getAddRecExpr - Get an add recurrence expression for the specified loop.
+/// Simplify the expression as much as possible.
+const SCEV* ScalarEvolution::getAddRecExpr(const SCEV* Start,
+ const SCEV* Step, const Loop *L) {
+ SmallVector<const SCEV*, 4> Operands;
Operands.push_back(Start);
if (const SCEVAddRecExpr *StepChrec = dyn_cast<SCEVAddRecExpr>(Step))
if (StepChrec->getLoop() == L) {
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,
+/// getAddRecExpr - Get an add recurrence expression for the specified loop.
+/// Simplify the expression as much as possible.
+const SCEV* ScalarEvolution::getAddRecExpr(SmallVectorImpl<const SCEV*> &Operands,
const Loop *L) {
if (Operands.size() == 1) return Operands[0];
#ifndef NDEBUG
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());
- SCEVHandle NestedARHandle(NestedAR);
+ SmallVector<const SCEV*, 4> NestedOperands(NestedAR->op_begin(),
+ NestedAR->op_end());
Operands[0] = NestedAR->getStart();
NestedOperands[0] = getAddRecExpr(Operands, L);
return getAddRecExpr(NestedOperands, NestedLoop);
}
std::vector<const SCEV*> SCEVOps(Operands.begin(), Operands.end());
- SCEVAddRecExpr *&Result = (*SCEVAddRecExprs)[std::make_pair(L, SCEVOps)];
+ 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;
+const SCEV* ScalarEvolution::getSMaxExpr(const SCEV* LHS,
+ const SCEV* RHS) {
+ SmallVector<const SCEV*, 2> Ops;
Ops.push_back(LHS);
Ops.push_back(RHS);
return getSMaxExpr(Ops);
}
-SCEVHandle ScalarEvolution::getSMaxExpr(std::vector<SCEVHandle> Ops) {
+const SCEV*
+ScalarEvolution::getSMaxExpr(SmallVectorImpl<const SCEV*> &Ops) {
assert(!Ops.empty() && "Cannot get empty smax!");
if (Ops.size() == 1) return Ops[0];
#ifndef NDEBUG
// 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<const SCEV*> SCEVOps(Ops.begin(), Ops.end());
- SCEVCommutativeExpr *&Result = (*SCEVCommExprs)[std::make_pair(scSMaxExpr,
+ SCEVCommutativeExpr *&Result = SCEVCommExprs[std::make_pair(scSMaxExpr,
SCEVOps)];
if (Result == 0) Result = new SCEVSMaxExpr(Ops);
return Result;
}
-SCEVHandle ScalarEvolution::getUMaxExpr(const SCEVHandle &LHS,
- const SCEVHandle &RHS) {
- std::vector<SCEVHandle> Ops;
+const SCEV* ScalarEvolution::getUMaxExpr(const SCEV* LHS,
+ const SCEV* RHS) {
+ SmallVector<const SCEV*, 2> Ops;
Ops.push_back(LHS);
Ops.push_back(RHS);
return getUMaxExpr(Ops);
}
-SCEVHandle ScalarEvolution::getUMaxExpr(std::vector<SCEVHandle> Ops) {
+const SCEV*
+ScalarEvolution::getUMaxExpr(SmallVectorImpl<const SCEV*> &Ops) {
assert(!Ops.empty() && "Cannot get empty umax!");
if (Ops.size() == 1) return Ops[0];
#ifndef NDEBUG
// 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<const SCEV*> SCEVOps(Ops.begin(), Ops.end());
- SCEVCommutativeExpr *&Result = (*SCEVCommExprs)[std::make_pair(scUMaxExpr,
+ SCEVCommutativeExpr *&Result = SCEVCommExprs[std::make_pair(scUMaxExpr,
SCEVOps)];
if (Result == 0) Result = new SCEVUMaxExpr(Ops);
return Result;
}
-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];
+const SCEV* ScalarEvolution::getSMinExpr(const SCEV* LHS,
+ const SCEV* RHS) {
+ // ~smax(~x, ~y) == smin(x, y).
+ return getNotSCEV(getSMaxExpr(getNotSCEV(LHS), getNotSCEV(RHS)));
+}
+
+const SCEV* ScalarEvolution::getUMinExpr(const SCEV* LHS,
+ const SCEV* RHS) {
+ // ~umax(~x, ~y) == umin(x, y)
+ return getNotSCEV(getUMaxExpr(getNotSCEV(LHS), getNotSCEV(RHS)));
+}
+
+const SCEV* ScalarEvolution::getUnknown(Value *V) {
+ // Don't attempt to do anything other than create a SCEVUnknown object
+ // here. createSCEV only calls getUnknown after checking for all other
+ // interesting possibilities, and any other code that calls getUnknown
+ // is doing so in order to hide a value from SCEV canonicalization.
+
+ SCEVUnknown *&Result = SCEVUnknowns[V];
if (Result == 0) Result = new SCEVUnknown(V);
return Result;
}
return TD->getIntPtrType();
}
-SCEVHandle ScalarEvolution::getCouldNotCompute() {
- return UnknownValue;
+const SCEV* ScalarEvolution::getCouldNotCompute() {
+ return CouldNotCompute;
}
/// hasSCEV - Return true if the SCEV for this value has already been
/// getSCEV - Return an existing SCEV if it exists, otherwise analyze the
/// expression and create a new one.
-SCEVHandle ScalarEvolution::getSCEV(Value *V) {
+const SCEV* ScalarEvolution::getSCEV(Value *V) {
assert(isSCEVable(V->getType()) && "Value is not SCEVable!");
- std::map<SCEVCallbackVH, SCEVHandle>::iterator I = Scalars.find(V);
+ std::map<SCEVCallbackVH, const SCEV*>::iterator I = Scalars.find(V);
if (I != Scalars.end()) return I->second;
- SCEVHandle S = createSCEV(V);
+ const SCEV* S = createSCEV(V);
Scalars.insert(std::make_pair(SCEVCallbackVH(V, this), S));
return S;
}
-/// getIntegerSCEV - Given an integer or FP type, create a constant for the
+/// getIntegerSCEV - Given a SCEVable 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);
+const SCEV* ScalarEvolution::getIntegerSCEV(int Val, const Type *Ty) {
+ const IntegerType *ITy = cast<IntegerType>(getEffectiveSCEVType(Ty));
+ return getConstant(ConstantInt::get(ITy, Val));
}
/// getNegativeSCEV - Return a SCEV corresponding to -V = -1*V
///
-SCEVHandle ScalarEvolution::getNegativeSCEV(const SCEVHandle &V) {
+const SCEV* ScalarEvolution::getNegativeSCEV(const SCEV* V) {
if (const SCEVConstant *VC = dyn_cast<SCEVConstant>(V))
- return getUnknown(ConstantExpr::getNeg(VC->getValue()));
+ return getConstant(cast<ConstantInt>(ConstantExpr::getNeg(VC->getValue())));
const Type *Ty = V->getType();
Ty = getEffectiveSCEVType(Ty);
}
/// getNotSCEV - Return a SCEV corresponding to ~V = -1-V
-SCEVHandle ScalarEvolution::getNotSCEV(const SCEVHandle &V) {
+const SCEV* ScalarEvolution::getNotSCEV(const SCEV* V) {
if (const SCEVConstant *VC = dyn_cast<SCEVConstant>(V))
- return getUnknown(ConstantExpr::getNot(VC->getValue()));
+ return getConstant(cast<ConstantInt>(ConstantExpr::getNot(VC->getValue())));
const Type *Ty = V->getType();
Ty = getEffectiveSCEVType(Ty);
- SCEVHandle AllOnes = getConstant(ConstantInt::getAllOnesValue(Ty));
+ const SCEV* 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) {
+const SCEV* ScalarEvolution::getMinusSCEV(const SCEV* LHS,
+ const SCEV* RHS) {
// X - Y --> X + -Y
return getAddExpr(LHS, getNegativeSCEV(RHS));
}
/// 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 SCEV*
+ScalarEvolution::getTruncateOrZeroExtend(const SCEV* V,
const Type *Ty) {
const Type *SrcTy = V->getType();
assert((SrcTy->isInteger() || (TD && isa<PointerType>(SrcTy))) &&
/// 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 SCEV*
+ScalarEvolution::getTruncateOrSignExtend(const SCEV* V,
const Type *Ty) {
const Type *SrcTy = V->getType();
assert((SrcTy->isInteger() || (TD && isa<PointerType>(SrcTy))) &&
/// 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 SCEV*
+ScalarEvolution::getNoopOrZeroExtend(const SCEV* V, const Type *Ty) {
const Type *SrcTy = V->getType();
assert((SrcTy->isInteger() || (TD && isa<PointerType>(SrcTy))) &&
(Ty->isInteger() || (TD && isa<PointerType>(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 SCEV*
+ScalarEvolution::getNoopOrSignExtend(const SCEV* V, const Type *Ty) {
const Type *SrcTy = V->getType();
assert((SrcTy->isInteger() || (TD && isa<PointerType>(SrcTy))) &&
(Ty->isInteger() || (TD && isa<PointerType>(Ty))) &&
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.
+const SCEV*
+ScalarEvolution::getNoopOrAnyExtend(const SCEV* 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 SCEV*
+ScalarEvolution::getTruncateOrNoop(const SCEV* V, const Type *Ty) {
const Type *SrcTy = V->getType();
assert((SrcTy->isInteger() || (TD && isa<PointerType>(SrcTy))) &&
(Ty->isInteger() || (TD && isa<PointerType>(Ty))) &&
return getTruncateExpr(V, Ty);
}
+/// getUMaxFromMismatchedTypes - Promote the operands to the wider of
+/// the types using zero-extension, and then perform a umax operation
+/// with them.
+const SCEV* ScalarEvolution::getUMaxFromMismatchedTypes(const SCEV* LHS,
+ const SCEV* RHS) {
+ const SCEV* PromotedLHS = LHS;
+ const SCEV* PromotedRHS = RHS;
+
+ if (getTypeSizeInBits(LHS->getType()) > getTypeSizeInBits(RHS->getType()))
+ PromotedRHS = getZeroExtendExpr(RHS, LHS->getType());
+ else
+ PromotedLHS = getNoopOrZeroExtend(LHS, RHS->getType());
+
+ return getUMaxExpr(PromotedLHS, PromotedRHS);
+}
+
+/// getUMinFromMismatchedTypes - Promote the operands to the wider of
+/// the types using zero-extension, and then perform a umin operation
+/// with them.
+const SCEV* ScalarEvolution::getUMinFromMismatchedTypes(const SCEV* LHS,
+ const SCEV* RHS) {
+ const SCEV* PromotedLHS = LHS;
+ const SCEV* PromotedRHS = RHS;
+
+ if (getTypeSizeInBits(LHS->getType()) > getTypeSizeInBits(RHS->getType()))
+ PromotedRHS = getZeroExtendExpr(RHS, LHS->getType());
+ else
+ PromotedLHS = getNoopOrZeroExtend(LHS, RHS->getType());
+
+ return getUMinExpr(PromotedLHS, PromotedRHS);
+}
+
/// 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 ScalarEvolution::
-ReplaceSymbolicValueWithConcrete(Instruction *I, const SCEVHandle &SymName,
- const SCEVHandle &NewVal) {
- std::map<SCEVCallbackVH, SCEVHandle>::iterator SI =
+ReplaceSymbolicValueWithConcrete(Instruction *I, const SCEV* SymName,
+ const SCEV* NewVal) {
+ std::map<SCEVCallbackVH, const SCEV*>::iterator SI =
Scalars.find(SCEVCallbackVH(I, this));
if (SI == Scalars.end()) return;
- SCEVHandle NV =
+ const SCEV* NV =
SI->second->replaceSymbolicValuesWithConcrete(SymName, NewVal, *this);
if (NV == SI->second) return; // No change.
/// 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 ScalarEvolution::createNodeForPHI(PHINode *PN) {
+const SCEV* ScalarEvolution::createNodeForPHI(PHINode *PN) {
if (PN->getNumIncomingValues() == 2) // The loops have been canonicalized.
if (const Loop *L = LI->getLoopFor(PN->getParent()))
if (L->getHeader() == PN->getParent()) {
unsigned BackEdge = IncomingEdge^1;
// While we are analyzing this PHI node, handle its value symbolically.
- SCEVHandle SymbolicName = getUnknown(PN);
+ const SCEV* SymbolicName = getUnknown(PN);
assert(Scalars.find(PN) == Scalars.end() &&
"PHI node already processed?");
Scalars.insert(std::make_pair(SCEVCallbackVH(PN, this), SymbolicName));
// Using this symbolic name for the PHI, analyze the value coming around
// the back-edge.
- SCEVHandle BEValue = getSCEV(PN->getIncomingValue(BackEdge));
+ const SCEV* BEValue = getSCEV(PN->getIncomingValue(BackEdge));
// NOTE: If BEValue is loop invariant, we know that the PHI node just
// has a special value for the first iteration of the loop.
if (FoundIndex != Add->getNumOperands()) {
// Create an add with everything but the specified operand.
- std::vector<SCEVHandle> Ops;
+ SmallVector<const SCEV*, 8> Ops;
for (unsigned i = 0, e = Add->getNumOperands(); i != e; ++i)
if (i != FoundIndex)
Ops.push_back(Add->getOperand(i));
- SCEVHandle Accum = getAddExpr(Ops);
+ const SCEV* 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.
if (Accum->isLoopInvariant(L) ||
(isa<SCEVAddRecExpr>(Accum) &&
cast<SCEVAddRecExpr>(Accum)->getLoop() == L)) {
- SCEVHandle StartVal = getSCEV(PN->getIncomingValue(IncomingEdge));
- SCEVHandle PHISCEV = getAddRecExpr(StartVal, Accum, L);
+ const SCEV* StartVal = getSCEV(PN->getIncomingValue(IncomingEdge));
+ const SCEV* 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
// Because the other in-value of i (0) fits the evolution of BEValue
// i really is an addrec evolution.
if (AddRec->getLoop() == L && AddRec->isAffine()) {
- SCEVHandle StartVal = getSCEV(PN->getIncomingValue(IncomingEdge));
+ const SCEV* StartVal = getSCEV(PN->getIncomingValue(IncomingEdge));
// If StartVal = j.start - j.stride, we can use StartVal as the
// initial step of the addrec evolution.
if (StartVal == getMinusSCEV(AddRec->getOperand(0),
AddRec->getOperand(1))) {
- SCEVHandle PHISCEV =
+ const SCEV* PHISCEV =
getAddRecExpr(StartVal, AddRec->getOperand(1), L);
// Okay, for the entire analysis of this edge we assumed the PHI
/// 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 SCEV* 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);
+ const SCEV* 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();
getIntegerSCEV(Offset, IntPtrTy));
} else {
// For an array, add the element offset, explicitly scaled.
- SCEVHandle LocalOffset = getSCEV(Index);
+ const SCEV* LocalOffset = getSCEV(Index);
if (!isa<PointerType>(LocalOffset->getType()))
// Getelementptr indicies are signed.
LocalOffset = getTruncateOrSignExtend(LocalOffset,
/// 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, const ScalarEvolution &SE) {
+uint32_t
+ScalarEvolution::GetMinTrailingZeros(const SCEV* S) {
if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S))
return C->getValue()->getValue().countTrailingZeros();
if (const SCEVTruncateExpr *T = dyn_cast<SCEVTruncateExpr>(S))
- return std::min(GetMinTrailingZeros(T->getOperand(), SE),
- (uint32_t)SE.getTypeSizeInBits(T->getType()));
+ return std::min(GetMinTrailingZeros(T->getOperand()),
+ (uint32_t)getTypeSizeInBits(T->getType()));
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;
+ uint32_t OpRes = GetMinTrailingZeros(E->getOperand());
+ return OpRes == getTypeSizeInBits(E->getOperand()->getType()) ?
+ getTypeSizeInBits(E->getType()) : 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;
+ uint32_t OpRes = GetMinTrailingZeros(E->getOperand());
+ return OpRes == getTypeSizeInBits(E->getOperand()->getType()) ?
+ getTypeSizeInBits(E->getType()) : OpRes;
}
if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) {
// The result is the min of all operands results.
- uint32_t MinOpRes = GetMinTrailingZeros(A->getOperand(0), SE);
+ uint32_t MinOpRes = GetMinTrailingZeros(A->getOperand(0));
for (unsigned i = 1, e = A->getNumOperands(); MinOpRes && i != e; ++i)
- MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(A->getOperand(i), SE));
+ MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(A->getOperand(i)));
return MinOpRes;
}
if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(S)) {
// The result is the sum of all operands results.
- uint32_t SumOpRes = GetMinTrailingZeros(M->getOperand(0), SE);
- uint32_t BitWidth = SE.getTypeSizeInBits(M->getType());
+ uint32_t SumOpRes = GetMinTrailingZeros(M->getOperand(0));
+ uint32_t BitWidth = getTypeSizeInBits(M->getType());
for (unsigned i = 1, e = M->getNumOperands();
SumOpRes != BitWidth && i != e; ++i)
- SumOpRes = std::min(SumOpRes + GetMinTrailingZeros(M->getOperand(i), SE),
+ SumOpRes = std::min(SumOpRes + GetMinTrailingZeros(M->getOperand(i)),
BitWidth);
return SumOpRes;
}
if (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(S)) {
// The result is the min of all operands results.
- uint32_t MinOpRes = GetMinTrailingZeros(A->getOperand(0), SE);
+ uint32_t MinOpRes = GetMinTrailingZeros(A->getOperand(0));
for (unsigned i = 1, e = A->getNumOperands(); MinOpRes && i != e; ++i)
- MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(A->getOperand(i), SE));
+ MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(A->getOperand(i)));
return MinOpRes;
}
if (const SCEVSMaxExpr *M = dyn_cast<SCEVSMaxExpr>(S)) {
// The result is the min of all operands results.
- uint32_t MinOpRes = GetMinTrailingZeros(M->getOperand(0), SE);
+ uint32_t MinOpRes = GetMinTrailingZeros(M->getOperand(0));
for (unsigned i = 1, e = M->getNumOperands(); MinOpRes && i != e; ++i)
- MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(M->getOperand(i), SE));
+ MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(M->getOperand(i)));
return MinOpRes;
}
if (const SCEVUMaxExpr *M = dyn_cast<SCEVUMaxExpr>(S)) {
// The result is the min of all operands results.
- uint32_t MinOpRes = GetMinTrailingZeros(M->getOperand(0), SE);
+ uint32_t MinOpRes = GetMinTrailingZeros(M->getOperand(0));
for (unsigned i = 1, e = M->getNumOperands(); MinOpRes && i != e; ++i)
- MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(M->getOperand(i), SE));
+ MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(M->getOperand(i)));
return MinOpRes;
}
- // SCEVUDivExpr, SCEVUnknown
+ if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
+ // For a SCEVUnknown, ask ValueTracking.
+ unsigned BitWidth = getTypeSizeInBits(U->getType());
+ APInt Mask = APInt::getAllOnesValue(BitWidth);
+ APInt Zeros(BitWidth, 0), Ones(BitWidth, 0);
+ ComputeMaskedBits(U->getValue(), Mask, Zeros, Ones);
+ return Zeros.countTrailingOnes();
+ }
+
+ // SCEVUDivExpr
return 0;
}
+uint32_t
+ScalarEvolution::GetMinLeadingZeros(const SCEV* S) {
+ // TODO: Handle other SCEV expression types here.
+
+ if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S))
+ return C->getValue()->getValue().countLeadingZeros();
+
+ if (const SCEVZeroExtendExpr *C = dyn_cast<SCEVZeroExtendExpr>(S)) {
+ // A zero-extension cast adds zero bits.
+ return GetMinLeadingZeros(C->getOperand()) +
+ (getTypeSizeInBits(C->getType()) -
+ getTypeSizeInBits(C->getOperand()->getType()));
+ }
+
+ if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
+ // For a SCEVUnknown, ask ValueTracking.
+ unsigned BitWidth = getTypeSizeInBits(U->getType());
+ APInt Mask = APInt::getAllOnesValue(BitWidth);
+ APInt Zeros(BitWidth, 0), Ones(BitWidth, 0);
+ ComputeMaskedBits(U->getValue(), Mask, Zeros, Ones, TD);
+ return Zeros.countLeadingOnes();
+ }
+
+ return 1;
+}
+
+uint32_t
+ScalarEvolution::GetMinSignBits(const SCEV* S) {
+ // TODO: Handle other SCEV expression types here.
+
+ if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S)) {
+ const APInt &A = C->getValue()->getValue();
+ return A.isNegative() ? A.countLeadingOnes() :
+ A.countLeadingZeros();
+ }
+
+ if (const SCEVSignExtendExpr *C = dyn_cast<SCEVSignExtendExpr>(S)) {
+ // A sign-extension cast adds sign bits.
+ return GetMinSignBits(C->getOperand()) +
+ (getTypeSizeInBits(C->getType()) -
+ getTypeSizeInBits(C->getOperand()->getType()));
+ }
+
+ if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) {
+ unsigned BitWidth = getTypeSizeInBits(A->getType());
+
+ // Special case decrementing a value (ADD X, -1):
+ if (const SCEVConstant *CRHS = dyn_cast<SCEVConstant>(A->getOperand(0)))
+ if (CRHS->isAllOnesValue()) {
+ SmallVector<const SCEV *, 4> OtherOps(A->op_begin() + 1, A->op_end());
+ const SCEV *OtherOpsAdd = getAddExpr(OtherOps);
+ unsigned LZ = GetMinLeadingZeros(OtherOpsAdd);
+
+ // If the input is known to be 0 or 1, the output is 0/-1, which is all
+ // sign bits set.
+ if (LZ == BitWidth - 1)
+ return BitWidth;
+
+ // If we are subtracting one from a positive number, there is no carry
+ // out of the result.
+ if (LZ > 0)
+ return GetMinSignBits(OtherOpsAdd);
+ }
+
+ // Add can have at most one carry bit. Thus we know that the output
+ // is, at worst, one more bit than the inputs.
+ unsigned Min = BitWidth;
+ for (unsigned i = 0, e = A->getNumOperands(); i != e; ++i) {
+ unsigned N = GetMinSignBits(A->getOperand(i));
+ Min = std::min(Min, N) - 1;
+ if (Min == 0) return 1;
+ }
+ return 1;
+ }
+
+ if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
+ // For a SCEVUnknown, ask ValueTracking.
+ return ComputeNumSignBits(U->getValue(), TD);
+ }
+
+ return 1;
+}
+
/// createSCEV - We know that there is no SCEV for the specified value.
/// Analyze the expression.
///
-SCEVHandle ScalarEvolution::createSCEV(Value *V) {
+const SCEV* ScalarEvolution::createSCEV(Value *V) {
if (!isSCEVable(V->getType()))
return getUnknown(V);
Opcode = I->getOpcode();
else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
Opcode = CE->getOpcode();
+ else if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
+ return getConstant(CI);
+ else if (isa<ConstantPointerNull>(V))
+ return getIntegerSCEV(0, V->getType());
+ else if (isa<UndefValue>(V))
+ return getIntegerSCEV(0, V->getType());
else
return getUnknown(V);
if (CI->isAllOnesValue())
return getSCEV(U->getOperand(0));
const APInt &A = CI->getValue();
- unsigned Ones = A.countTrailingOnes();
- if (APIntOps::isMask(Ones, A))
+
+ // Instcombine's ShrinkDemandedConstant may strip bits out of
+ // constants, obscuring what would otherwise be a low-bits mask.
+ // Use ComputeMaskedBits to compute what ShrinkDemandedConstant
+ // knew about to reconstruct a low-bits mask value.
+ unsigned LZ = A.countLeadingZeros();
+ unsigned BitWidth = A.getBitWidth();
+ APInt AllOnes = APInt::getAllOnesValue(BitWidth);
+ APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0);
+ ComputeMaskedBits(U->getOperand(0), AllOnes, KnownZero, KnownOne, TD);
+
+ APInt EffectiveMask = APInt::getLowBitsSet(BitWidth, BitWidth - LZ);
+
+ if (LZ != 0 && !((~A & ~KnownZero) & EffectiveMask))
return
getZeroExtendExpr(getTruncateExpr(getSCEV(U->getOperand(0)),
- IntegerType::get(Ones)),
+ IntegerType::get(BitWidth - LZ)),
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
// In order for this transformation to be safe, the LHS must be of the
// form X*(2^n) and the Or constant must be less than 2^n.
if (ConstantInt *CI = dyn_cast<ConstantInt>(U->getOperand(1))) {
- SCEVHandle LHS = getSCEV(U->getOperand(0));
+ const SCEV* LHS = getSCEV(U->getOperand(0));
const APInt &CIVal = CI->getValue();
- if (GetMinTrailingZeros(LHS, *this) >=
+ if (GetMinTrailingZeros(LHS) >=
(CIVal.getBitWidth() - CIVal.countLeadingZeros()))
return getAddExpr(LHS, getSCEV(U->getOperand(1)));
}
getSCEV(U->getOperand(1)));
// If the RHS of xor is -1, then this is a not operation.
- else if (CI->isAllOnesValue())
+ 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)))) {
+ const Type *UTy = U->getType();
+ const SCEV* Z0 = Z->getOperand();
+ const Type *Z0Ty = Z0->getType();
+ unsigned Z0TySize = getTypeSizeInBits(Z0Ty);
+
+ // If C is a low-bits mask, the zero extend is zerving to
+ // mask off the high bits. Complement the operand and
+ // re-apply the zext.
+ if (APIntOps::isMask(Z0TySize, CI->getValue()))
+ return getZeroExtendExpr(getNotSCEV(Z0), UTy);
+
+ // If C is a single bit, it may be in the sign-bit position
+ // before the zero-extend. In this case, represent the xor
+ // using an add, which is equivalent, and re-apply the zext.
+ APInt Trunc = APInt(CI->getValue()).trunc(Z0TySize);
+ if (APInt(Trunc).zext(getTypeSizeInBits(UTy)) == CI->getValue() &&
+ Trunc.isSignBit())
+ return getZeroExtendExpr(getAddExpr(Z0, getConstant(Trunc)),
+ UTy);
+ }
}
break;
if (LHS == U->getOperand(1) && RHS == U->getOperand(2))
return getSMaxExpr(getSCEV(LHS), getSCEV(RHS));
else if (LHS == U->getOperand(2) && RHS == U->getOperand(1))
- // ~smax(~x, ~y) == smin(x, y).
- return getNotSCEV(getSMaxExpr(
- getNotSCEV(getSCEV(LHS)),
- getNotSCEV(getSCEV(RHS))));
+ return getSMinExpr(getSCEV(LHS), getSCEV(RHS));
break;
case ICmpInst::ICMP_ULT:
case ICmpInst::ICMP_ULE:
if (LHS == U->getOperand(1) && RHS == U->getOperand(2))
return getUMaxExpr(getSCEV(LHS), getSCEV(RHS));
else if (LHS == U->getOperand(2) && RHS == U->getOperand(1))
- // ~umax(~x, ~y) == umin(x, y)
- return getNotSCEV(getUMaxExpr(getNotSCEV(getSCEV(LHS)),
- getNotSCEV(getSCEV(RHS))));
+ return getUMinExpr(getSCEV(LHS), getSCEV(RHS));
+ break;
+ case ICmpInst::ICMP_NE:
+ // n != 0 ? n : 1 -> umax(n, 1)
+ if (LHS == U->getOperand(1) &&
+ isa<ConstantInt>(U->getOperand(2)) &&
+ cast<ConstantInt>(U->getOperand(2))->isOne() &&
+ isa<ConstantInt>(RHS) &&
+ cast<ConstantInt>(RHS)->isZero())
+ return getUMaxExpr(getSCEV(LHS), getSCEV(U->getOperand(2)));
+ break;
+ case ICmpInst::ICMP_EQ:
+ // n == 0 ? 1 : n -> umax(n, 1)
+ if (LHS == U->getOperand(2) &&
+ isa<ConstantInt>(U->getOperand(1)) &&
+ cast<ConstantInt>(U->getOperand(1))->isOne() &&
+ isa<ConstantInt>(RHS) &&
+ cast<ConstantInt>(RHS)->isZero())
+ return getUMaxExpr(getSCEV(LHS), getSCEV(U->getOperand(1)));
break;
default:
break;
/// loop-invariant backedge-taken count (see
/// hasLoopInvariantBackedgeTakenCount).
///
-SCEVHandle ScalarEvolution::getBackedgeTakenCount(const Loop *L) {
+const SCEV* 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) {
+const SCEV* ScalarEvolution::getMaxBackedgeTakenCount(const Loop *L) {
return getBackedgeTakenInfo(L).Max;
}
BackedgeTakenCounts.insert(std::make_pair(L, getCouldNotCompute()));
if (Pair.second) {
BackedgeTakenInfo ItCount = ComputeBackedgeTakenCount(L);
- if (ItCount.Exact != UnknownValue) {
+ if (ItCount.Exact != CouldNotCompute) {
assert(ItCount.Exact->isLoopInvariant(L) &&
ItCount.Max->isLoopInvariant(L) &&
"Computed trip count isn't loop invariant for loop!");
// 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;
+ } else {
+ if (ItCount.Max != CouldNotCompute)
+ // Update the value in the map.
+ Pair.first->second = ItCount;
+ 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
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);
+ std::map<SCEVCallbackVH, const SCEV*>::iterator It = Scalars.find((Value*)I);
if (It != Scalars.end() && !isa<SCEVUnknown>(It->second))
Worklist.push_back(PN);
}
/// 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;
-
- // 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;
+ SmallVector<BasicBlock*, 8> ExitingBlocks;
+ L->getExitingBlocks(ExitingBlocks);
+
+ // Examine all exits and pick the most conservative values.
+ const SCEV* BECount = CouldNotCompute;
+ const SCEV* MaxBECount = CouldNotCompute;
+ bool CouldNotComputeBECount = false;
+ for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) {
+ BackedgeTakenInfo NewBTI =
+ ComputeBackedgeTakenCountFromExit(L, ExitingBlocks[i]);
+
+ if (NewBTI.Exact == CouldNotCompute) {
+ // We couldn't compute an exact value for this exit, so
+ // we won't be able to compute an exact value for the loop.
+ CouldNotComputeBECount = true;
+ BECount = CouldNotCompute;
+ } else if (!CouldNotComputeBECount) {
+ if (BECount == CouldNotCompute)
+ BECount = NewBTI.Exact;
else
- return UnknownValue; // More than one block exiting!
+ BECount = getUMinFromMismatchedTypes(BECount, NewBTI.Exact);
}
- assert(ExitingBlock && "No exits from loop, something is broken!");
+ if (MaxBECount == CouldNotCompute)
+ MaxBECount = NewBTI.Max;
+ else if (NewBTI.Max != CouldNotCompute)
+ MaxBECount = getUMinFromMismatchedTypes(MaxBECount, NewBTI.Max);
+ }
+
+ return BackedgeTakenInfo(BECount, MaxBECount);
+}
- // Okay, we've computed the exiting block. See what condition causes us to
- // exit.
+/// ComputeBackedgeTakenCountFromExit - Compute the number of times the backedge
+/// of the specified loop will execute if it exits via the specified block.
+ScalarEvolution::BackedgeTakenInfo
+ScalarEvolution::ComputeBackedgeTakenCountFromExit(const Loop *L,
+ BasicBlock *ExitingBlock) {
+
+ // Okay, we've chosen an exiting block. See what condition causes us to
+ // exit at this block.
//
// 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
// Currently we check for this by checking to see if the Exit branch goes to
// the loop header. If so, we know it will always execute the same number of
// times as the loop. We also handle the case where the exit block *is* the
- // loop header. This is common for un-rotated loops. More extensive analysis
- // could be done to handle more cases here.
+ // loop header. This is common for un-rotated loops.
+ //
+ // If both of those tests fail, walk up the unique predecessor chain to the
+ // header, stopping if there is an edge that doesn't exit the loop. If the
+ // header is reached, the execution count of the branch will be equal to the
+ // trip count of the loop.
+ //
+ // More extensive analysis could be done to handle more cases here.
+ //
if (ExitBr->getSuccessor(0) != L->getHeader() &&
ExitBr->getSuccessor(1) != L->getHeader() &&
- ExitBr->getParent() != L->getHeader())
- return UnknownValue;
-
- ICmpInst *ExitCond = dyn_cast<ICmpInst>(ExitBr->getCondition());
+ ExitBr->getParent() != L->getHeader()) {
+ // The simple checks failed, try climbing the unique predecessor chain
+ // up to the header.
+ bool Ok = false;
+ for (BasicBlock *BB = ExitBr->getParent(); BB; ) {
+ BasicBlock *Pred = BB->getUniquePredecessor();
+ if (!Pred)
+ return CouldNotCompute;
+ TerminatorInst *PredTerm = Pred->getTerminator();
+ for (unsigned i = 0, e = PredTerm->getNumSuccessors(); i != e; ++i) {
+ BasicBlock *PredSucc = PredTerm->getSuccessor(i);
+ if (PredSucc == BB)
+ continue;
+ // If the predecessor has a successor that isn't BB and isn't
+ // outside the loop, assume the worst.
+ if (L->contains(PredSucc))
+ return CouldNotCompute;
+ }
+ if (Pred == L->getHeader()) {
+ Ok = true;
+ break;
+ }
+ BB = Pred;
+ }
+ if (!Ok)
+ return CouldNotCompute;
+ }
+
+ // Procede to the next level to examine the exit condition expression.
+ return ComputeBackedgeTakenCountFromExitCond(L, ExitBr->getCondition(),
+ ExitBr->getSuccessor(0),
+ ExitBr->getSuccessor(1));
+}
+
+/// ComputeBackedgeTakenCountFromExitCond - Compute the number of times the
+/// backedge of the specified loop will execute if its exit condition
+/// were a conditional branch of ExitCond, TBB, and FBB.
+ScalarEvolution::BackedgeTakenInfo
+ScalarEvolution::ComputeBackedgeTakenCountFromExitCond(const Loop *L,
+ Value *ExitCond,
+ BasicBlock *TBB,
+ BasicBlock *FBB) {
+ // Check if the controlling expression for this loop is an And or Or.
+ if (BinaryOperator *BO = dyn_cast<BinaryOperator>(ExitCond)) {
+ if (BO->getOpcode() == Instruction::And) {
+ // Recurse on the operands of the and.
+ BackedgeTakenInfo BTI0 =
+ ComputeBackedgeTakenCountFromExitCond(L, BO->getOperand(0), TBB, FBB);
+ BackedgeTakenInfo BTI1 =
+ ComputeBackedgeTakenCountFromExitCond(L, BO->getOperand(1), TBB, FBB);
+ const SCEV* BECount = CouldNotCompute;
+ const SCEV* MaxBECount = CouldNotCompute;
+ if (L->contains(TBB)) {
+ // Both conditions must be true for the loop to continue executing.
+ // Choose the less conservative count.
+ if (BTI0.Exact == CouldNotCompute || BTI1.Exact == CouldNotCompute)
+ BECount = CouldNotCompute;
+ else
+ BECount = getUMinFromMismatchedTypes(BTI0.Exact, BTI1.Exact);
+ if (BTI0.Max == CouldNotCompute)
+ MaxBECount = BTI1.Max;
+ else if (BTI1.Max == CouldNotCompute)
+ MaxBECount = BTI0.Max;
+ else
+ MaxBECount = getUMinFromMismatchedTypes(BTI0.Max, BTI1.Max);
+ } else {
+ // Both conditions must be true for the loop to exit.
+ assert(L->contains(FBB) && "Loop block has no successor in loop!");
+ if (BTI0.Exact != CouldNotCompute && BTI1.Exact != CouldNotCompute)
+ BECount = getUMaxFromMismatchedTypes(BTI0.Exact, BTI1.Exact);
+ if (BTI0.Max != CouldNotCompute && BTI1.Max != CouldNotCompute)
+ MaxBECount = getUMaxFromMismatchedTypes(BTI0.Max, BTI1.Max);
+ }
+
+ return BackedgeTakenInfo(BECount, MaxBECount);
+ }
+ if (BO->getOpcode() == Instruction::Or) {
+ // Recurse on the operands of the or.
+ BackedgeTakenInfo BTI0 =
+ ComputeBackedgeTakenCountFromExitCond(L, BO->getOperand(0), TBB, FBB);
+ BackedgeTakenInfo BTI1 =
+ ComputeBackedgeTakenCountFromExitCond(L, BO->getOperand(1), TBB, FBB);
+ const SCEV* BECount = CouldNotCompute;
+ const SCEV* MaxBECount = CouldNotCompute;
+ if (L->contains(FBB)) {
+ // Both conditions must be false for the loop to continue executing.
+ // Choose the less conservative count.
+ if (BTI0.Exact == CouldNotCompute || BTI1.Exact == CouldNotCompute)
+ BECount = CouldNotCompute;
+ else
+ BECount = getUMinFromMismatchedTypes(BTI0.Exact, BTI1.Exact);
+ if (BTI0.Max == CouldNotCompute)
+ MaxBECount = BTI1.Max;
+ else if (BTI1.Max == CouldNotCompute)
+ MaxBECount = BTI0.Max;
+ else
+ MaxBECount = getUMinFromMismatchedTypes(BTI0.Max, BTI1.Max);
+ } else {
+ // Both conditions must be false for the loop to exit.
+ assert(L->contains(TBB) && "Loop block has no successor in loop!");
+ if (BTI0.Exact != CouldNotCompute && BTI1.Exact != CouldNotCompute)
+ BECount = getUMaxFromMismatchedTypes(BTI0.Exact, BTI1.Exact);
+ if (BTI0.Max != CouldNotCompute && BTI1.Max != CouldNotCompute)
+ MaxBECount = getUMaxFromMismatchedTypes(BTI0.Max, BTI1.Max);
+ }
+
+ return BackedgeTakenInfo(BECount, MaxBECount);
+ }
+ }
+
+ // With an icmp, it may be feasible to compute an exact backedge-taken count.
+ // Procede to the next level to examine the icmp.
+ if (ICmpInst *ExitCondICmp = dyn_cast<ICmpInst>(ExitCond))
+ return ComputeBackedgeTakenCountFromExitCondICmp(L, ExitCondICmp, TBB, FBB);
// 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);
+ return ComputeBackedgeTakenCountExhaustively(L, ExitCond, !L->contains(TBB));
+}
+
+/// ComputeBackedgeTakenCountFromExitCondICmp - Compute the number of times the
+/// backedge of the specified loop will execute if its exit condition
+/// were a conditional branch of the ICmpInst ExitCond, TBB, and FBB.
+ScalarEvolution::BackedgeTakenInfo
+ScalarEvolution::ComputeBackedgeTakenCountFromExitCondICmp(const Loop *L,
+ ICmpInst *ExitCond,
+ BasicBlock *TBB,
+ BasicBlock *FBB) {
// If the condition was exit on true, convert the condition to exit on false
ICmpInst::Predicate Cond;
- if (ExitBr->getSuccessor(1) == ExitBlock)
+ if (!L->contains(FBB))
Cond = ExitCond->getPredicate();
else
Cond = ExitCond->getInversePredicate();
// Handle common loops like: for (X = "string"; *X; ++X)
if (LoadInst *LI = dyn_cast<LoadInst>(ExitCond->getOperand(0)))
if (Constant *RHS = dyn_cast<Constant>(ExitCond->getOperand(1))) {
- SCEVHandle ItCnt =
+ const SCEV* ItCnt =
ComputeLoadConstantCompareBackedgeTakenCount(LI, RHS, L, Cond);
- if (!isa<SCEVCouldNotCompute>(ItCnt)) return ItCnt;
+ if (!isa<SCEVCouldNotCompute>(ItCnt)) {
+ unsigned BitWidth = getTypeSizeInBits(ItCnt->getType());
+ return BackedgeTakenInfo(ItCnt,
+ isa<SCEVConstant>(ItCnt) ? ItCnt :
+ getConstant(APInt::getMaxValue(BitWidth)-1));
+ }
}
- SCEVHandle LHS = getSCEV(ExitCond->getOperand(0));
- SCEVHandle RHS = getSCEV(ExitCond->getOperand(1));
+ const SCEV* LHS = getSCEV(ExitCond->getOperand(0));
+ const SCEV* 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.
ConstantRange CompRange(
ICmpInst::makeConstantRange(Cond, RHSC->getValue()->getValue()));
- SCEVHandle Ret = AddRec->getNumIterationsInRange(CompRange, *this);
+ const SCEV* 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(getMinusSCEV(LHS, RHS), L);
+ const SCEV* 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(getMinusSCEV(LHS, RHS), L);
+ const SCEV* TC = HowFarToNonZero(getMinusSCEV(LHS, RHS), L);
if (!isa<SCEVCouldNotCompute>(TC)) return TC;
break;
}
break;
}
return
- ComputeBackedgeTakenCountExhaustively(L, ExitCond,
- ExitBr->getSuccessor(0) == ExitBlock);
+ ComputeBackedgeTakenCountExhaustively(L, ExitCond, !L->contains(TBB));
}
static ConstantInt *
EvaluateConstantChrecAtConstant(const SCEVAddRecExpr *AddRec, ConstantInt *C,
ScalarEvolution &SE) {
- SCEVHandle InVal = SE.getConstant(C);
- SCEVHandle Val = AddRec->evaluateAtIteration(InVal, SE);
+ const SCEV* InVal = SE.getConstant(C);
+ const SCEV* Val = AddRec->evaluateAtIteration(InVal, SE);
assert(isa<SCEVConstant>(Val) &&
"Evaluation of SCEV at constant didn't fold correctly?");
return cast<SCEVConstant>(Val)->getValue();
/// ComputeLoadConstantCompareBackedgeTakenCount - Given an exit condition of
/// 'icmp op load X, cst', try to see if we can compute the backedge
/// execution count.
-SCEVHandle ScalarEvolution::
+const SCEV* ScalarEvolution::
ComputeLoadConstantCompareBackedgeTakenCount(LoadInst *LI, Constant *RHS,
const Loop *L,
ICmpInst::Predicate predicate) {
- if (LI->isVolatile()) return UnknownValue;
+ 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;
+ const SCEV* Idx = getSCEV(VarIdx);
+ Idx = getSCEVAtScope(Idx, L);
// We can only recognize very limited forms of loop index expressions, in
// particular, only affine AddRec's like {C1,+,C2}.
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::get(cast<IntegerType>(IdxExpr->getType()), IterationNum);
ConstantInt *Val = EvaluateConstantChrecAtConstant(IdxExpr, ItCst, *this);
// Form the GEP offset.
return getConstant(ItCst); // Found terminating iteration!
}
}
- return UnknownValue;
+ return CouldNotCompute;
}
/// 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 ScalarEvolution::
+/// evaluate the trip count of the loop, return CouldNotCompute.
+const SCEV* 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 getConstant(ConstantInt::get(Type::Int32Ty, IterationNum));
+ return getConstant(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 - Return a SCEV expression handle for the specified value
/// 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.
///
-/// If this value is not computable at this scope, a SCEVCouldNotCompute
-/// object is returned.
-SCEVHandle ScalarEvolution::getSCEVAtScope(const SCEV *V, const Loop *L) {
+/// In the case that a relevant loop exit value cannot be computed, the
+/// original value V is returned.
+const SCEV* 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;
// 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);
+ const SCEV* BackedgeTakenCount = getBackedgeTakenCount(LI);
if (const SCEVConstant *BTCC =
dyn_cast<SCEVConstant>(BackedgeTakenCount)) {
// Okay, we know how many times the containing loop executes. If
if (!isSCEVable(Op->getType()))
return V;
- SCEVHandle OpV = getSCEVAtScope(getSCEV(Op), L);
+ const SCEV* OpV = getSCEVAtScope(getSCEV(Op), L);
if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(OpV)) {
Constant *C = SC->getValue();
if (C->getType() != Op->getType())
// 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);
+ const SCEV* 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<const SCEV*, 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))
}
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;
+ const SCEV* LHS = getSCEVAtScope(Div->getLHS(), L);
+ const SCEV* RHS = getSCEVAtScope(Div->getRHS(), L);
if (LHS == Div->getLHS() && RHS == Div->getRHS())
return Div; // must be loop invariant
return getUDivExpr(LHS, RHS);
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 BackedgeTakenCount = getBackedgeTakenCount(AddRec->getLoop());
- if (BackedgeTakenCount == UnknownValue) return UnknownValue;
+ const SCEV* BackedgeTakenCount = getBackedgeTakenCount(AddRec->getLoop());
+ if (BackedgeTakenCount == CouldNotCompute) return AddRec;
// Then, evaluate the AddRec.
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 == UnknownValue) return Op;
+ const SCEV* 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 == UnknownValue) return Op;
+ const SCEV* Op = getSCEVAtScope(Cast->getOperand(), L);
if (Op == Cast->getOperand())
return Cast; // must be loop invariant
return getSignExtendExpr(Op, Cast->getType());
}
if (const SCEVTruncateExpr *Cast = dyn_cast<SCEVTruncateExpr>(V)) {
- SCEVHandle Op = getSCEVAtScope(Cast->getOperand(), L);
- if (Op == UnknownValue) return Op;
+ const SCEV* 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) {
+const SCEV* ScalarEvolution::getSCEVAtScope(Value *V, const Loop *L) {
return getSCEVAtScope(getSCEV(V), L);
}
/// A and B isn't important.
///
/// If the equation does not have a solution, SCEVCouldNotCompute is returned.
-static SCEVHandle SolveLinEquationWithOverflow(const APInt &A, const APInt &B,
+static const SCEV* SolveLinEquationWithOverflow(const APInt &A, const APInt &B,
ScalarEvolution &SE) {
uint32_t BW = A.getBitWidth();
assert(BW == B.getBitWidth() && "Bit widths must be the same.");
/// given quadratic chrec {L,+,M,+,N}. This returns either the two roots (which
/// might be the same) or two SCEVCouldNotCompute objects.
///
-static std::pair<SCEVHandle,SCEVHandle>
+static std::pair<const SCEV*,const SCEV*>
SolveQuadraticEquation(const SCEVAddRecExpr *AddRec, ScalarEvolution &SE) {
assert(AddRec->getNumOperands() == 3 && "This is not a quadratic chrec!");
const SCEVConstant *LC = dyn_cast<SCEVConstant>(AddRec->getOperand(0));
}
/// HowFarToZero - Return the number of times a backedge comparing the specified
-/// value to zero will execute. If not computable, return UnknownValue
-SCEVHandle ScalarEvolution::HowFarToZero(const SCEV *V, const Loop *L) {
+/// value to zero will execute. If not computable, return CouldNotCompute.
+const SCEV* ScalarEvolution::HowFarToZero(const SCEV *V, const Loop *L) {
// If the value is a constant
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.
}
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
// where BW is the common bit width of Start and Step.
// 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());
+ const SCEV* Start = getSCEVAtScope(AddRec->getStart(), L->getParentLoop());
+ const SCEV* Step = getSCEVAtScope(AddRec->getOperand(1), L->getParentLoop());
if (const SCEVConstant *StepC = dyn_cast<SCEVConstant>(Step)) {
// For now we handle only constant steps.
} 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,
+ std::pair<const SCEV*,const SCEV*> Roots = SolveQuadraticEquation(AddRec,
*this);
const SCEVConstant *R1 = dyn_cast<SCEVConstant>(Roots.first);
const SCEVConstant *R2 = dyn_cast<SCEVConstant>(Roots.second);
// 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, *this);
+ const SCEV* 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 ScalarEvolution::HowFarToNonZero(const SCEV *V, const Loop *L) {
+/// CouldNotCompute
+const SCEV* 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 (const SCEVConstant *C = dyn_cast<SCEVConstant>(V)) {
if (!C->getValue()->isNullValue())
return getIntegerSCEV(0, C->getType());
- return UnknownValue; // Otherwise it will loop infinitely.
+ 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
return 0;
}
+/// HasSameValue - SCEV structural equivalence is usually sufficient for
+/// testing whether two expressions are equal, however for the purposes of
+/// looking for a condition guarding a loop, it can be useful to be a little
+/// more general, since a front-end may have replicated the controlling
+/// expression.
+///
+static bool HasSameValue(const SCEV* A, const SCEV* B) {
+ // Quick check to see if they are the same SCEV.
+ if (A == B) return true;
+
+ // Otherwise, if they're both SCEVUnknown, it's possible that they hold
+ // two different instructions with the same value. Check for this case.
+ if (const SCEVUnknown *AU = dyn_cast<SCEVUnknown>(A))
+ if (const SCEVUnknown *BU = dyn_cast<SCEVUnknown>(B))
+ if (const Instruction *AI = dyn_cast<Instruction>(AU->getValue()))
+ if (const Instruction *BI = dyn_cast<Instruction>(BU->getValue()))
+ if (AI->isIdenticalTo(BI))
+ return true;
+
+ // Otherwise assume they may have a different value.
+ return false;
+}
+
/// 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();
LoopEntryPredicate->isUnconditional())
continue;
- ICmpInst *ICI = dyn_cast<ICmpInst>(LoopEntryPredicate->getCondition());
- if (!ICI) continue;
+ if (isNecessaryCond(LoopEntryPredicate->getCondition(), Pred, LHS, RHS,
+ LoopEntryPredicate->getSuccessor(0) != PredecessorDest))
+ return true;
+ }
- // Now that we found a conditional branch that dominates the loop, check to
- // see if it is the comparison we are looking for.
- Value *PreCondLHS = ICI->getOperand(0);
- Value *PreCondRHS = ICI->getOperand(1);
- ICmpInst::Predicate Cond;
- if (LoopEntryPredicate->getSuccessor(0) == PredecessorDest)
- Cond = ICI->getPredicate();
- else
- Cond = ICI->getInversePredicate();
+ return false;
+}
- 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;
+/// isNecessaryCond - Test whether the given CondValue value is a condition
+/// which is at least as strict as the one described by Pred, LHS, and RHS.
+bool ScalarEvolution::isNecessaryCond(Value *CondValue,
+ ICmpInst::Predicate Pred,
+ const SCEV *LHS, const SCEV *RHS,
+ bool Inverse) {
+ // Recursivly handle And and Or conditions.
+ if (BinaryOperator *BO = dyn_cast<BinaryOperator>(CondValue)) {
+ if (BO->getOpcode() == Instruction::And) {
+ if (!Inverse)
+ return isNecessaryCond(BO->getOperand(0), Pred, LHS, RHS, Inverse) ||
+ isNecessaryCond(BO->getOperand(1), Pred, LHS, RHS, Inverse);
+ } else if (BO->getOpcode() == Instruction::Or) {
+ if (Inverse)
+ return isNecessaryCond(BO->getOperand(0), Pred, LHS, RHS, Inverse) ||
+ isNecessaryCond(BO->getOperand(1), Pred, LHS, RHS, Inverse);
+ }
+ }
+
+ ICmpInst *ICI = dyn_cast<ICmpInst>(CondValue);
+ if (!ICI) return false;
+
+ // Now that we found a conditional branch that dominates the loop, check to
+ // see if it is the comparison we are looking for.
+ Value *PreCondLHS = ICI->getOperand(0);
+ Value *PreCondRHS = ICI->getOperand(1);
+ ICmpInst::Predicate Cond;
+ if (Inverse)
+ Cond = ICI->getInversePredicate();
+ else
+ Cond = ICI->getPredicate();
+
+ 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;
+ }
+ return false;
+ case ICmpInst::ICMP_SGT:
+ if (Pred == ICmpInst::ICMP_SLT) {
+ std::swap(PreCondLHS, PreCondRHS);
+ Cond = ICmpInst::ICMP_SLT;
+ break;
+ }
+ return false;
+ 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;
+ return false;
+ case ICmpInst::ICMP_SGT:
+ if (A.isMinSignedValue()) break;
+ return false;
+ case ICmpInst::ICMP_ULT:
+ if (A.isMaxValue()) break;
+ return false;
+ case ICmpInst::ICMP_UGT:
+ if (A.isMinValue()) break;
+ return false;
+ default:
+ return false;
+ }
+ 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;
- 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;
- }
+ return false;
+ default:
+ // We weren't able to reconcile the condition.
+ return false;
+ }
- if (!PreCondLHS->getType()->isInteger()) continue;
+ if (!PreCondLHS->getType()->isInteger()) return false;
- SCEVHandle PreCondLHSSCEV = getSCEV(PreCondLHS);
- SCEVHandle PreCondRHSSCEV = getSCEV(PreCondRHS);
- if ((LHS == PreCondLHSSCEV && RHS == PreCondRHSSCEV) ||
- (LHS == getNotSCEV(PreCondRHSSCEV) &&
- RHS == getNotSCEV(PreCondLHSSCEV)))
- return true;
- }
+ const SCEV *PreCondLHSSCEV = getSCEV(PreCondLHS);
+ const SCEV *PreCondRHSSCEV = getSCEV(PreCondRHS);
+ return (HasSameValue(LHS, PreCondLHSSCEV) &&
+ HasSameValue(RHS, PreCondRHSSCEV)) ||
+ (HasSameValue(LHS, getNotSCEV(PreCondRHSSCEV)) &&
+ HasSameValue(RHS, getNotSCEV(PreCondLHSSCEV)));
+}
- return false;
+/// getBECount - Subtract the end and start values and divide by the step,
+/// rounding up, to get the number of times the backedge is executed. Return
+/// CouldNotCompute if an intermediate computation overflows.
+const SCEV* ScalarEvolution::getBECount(const SCEV* Start,
+ const SCEV* End,
+ const SCEV* Step) {
+ const Type *Ty = Start->getType();
+ const SCEV* NegOne = getIntegerSCEV(-1, Ty);
+ const SCEV* Diff = getMinusSCEV(End, Start);
+ const SCEV* RoundUp = getAddExpr(Step, NegOne);
+
+ // Add an adjustment to the difference between End and Start so that
+ // the division will effectively round up.
+ const SCEV* Add = getAddExpr(Diff, RoundUp);
+
+ // Check Add for unsigned overflow.
+ // TODO: More sophisticated things could be done here.
+ const Type *WideTy = IntegerType::get(getTypeSizeInBits(Ty) + 1);
+ const SCEV* OperandExtendedAdd =
+ getAddExpr(getZeroExtendExpr(Diff, WideTy),
+ getZeroExtendExpr(RoundUp, WideTy));
+ if (getZeroExtendExpr(Add, WideTy) != OperandExtendedAdd)
+ return CouldNotCompute;
+
+ return getUDivExpr(Add, Step);
}
/// HowManyLessThans - Return the number of times a backedge containing the
/// specified less-than comparison will execute. If not computable, return
-/// UnknownValue.
+/// 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;
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.
unsigned BitWidth = getTypeSizeInBits(AddRec->getType());
- SCEVHandle Step = AddRec->getStepRecurrence(*this);
- SCEVHandle NegOne = getIntegerSCEV(-1, AddRec->getType());
+ const SCEV* Step = AddRec->getStepRecurrence(*this);
// TODO: handle non-constant strides.
const SCEVConstant *CStep = dyn_cast<SCEVConstant>(Step);
if (!CStep || CStep->isZero())
- return UnknownValue;
+ return CouldNotCompute;
if (CStep->isOne()) {
// With unit stride, the iteration never steps past the limit value.
} else if (CStep->getValue()->getValue().isStrictlyPositive()) {
APInt Max = APInt::getSignedMaxValue(BitWidth);
if ((Max - CStep->getValue()->getValue())
.slt(CLimit->getValue()->getValue()))
- return UnknownValue;
+ return CouldNotCompute;
} else {
APInt Max = APInt::getMaxValue(BitWidth);
if ((Max - CStep->getValue()->getValue())
.ult(CLimit->getValue()->getValue()))
- return UnknownValue;
+ return CouldNotCompute;
}
} else
// TODO: handle non-constant limit values below.
- return UnknownValue;
+ return CouldNotCompute;
} else
// TODO: handle negative strides below.
- return UnknownValue;
+ 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.
// 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);
+ const SCEV* Start = AddRec->getOperand(0);
// Determine the minimum constant start value.
- SCEVHandle MinStart = isa<SCEVConstant>(Start) ? Start :
+ const SCEV* 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 if will execute (max(m,n)-n)/s times. In both cases, the
- // division must round up.
- SCEVHandle End = RHS;
+ // only know that it will execute (max(m,n)-n)/s times. In both cases,
+ // the division must round up.
+ const SCEV* End = RHS;
if (!isLoopGuardedByCond(L,
isSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
getMinusSCEV(Start, Step), RHS))
: getUMaxExpr(RHS, Start);
// Determine the maximum constant end value.
- SCEVHandle MaxEnd = isa<SCEVConstant>(End) ? End :
- getConstant(isSigned ? APInt::getSignedMaxValue(BitWidth) :
- APInt::getMaxValue(BitWidth));
+ const SCEV* MaxEnd =
+ isa<SCEVConstant>(End) ? End :
+ getConstant(isSigned ? APInt::getSignedMaxValue(BitWidth)
+ .ashr(GetMinSignBits(End) - 1) :
+ APInt::getMaxValue(BitWidth)
+ .lshr(GetMinLeadingZeros(End)));
// 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);
+ const SCEV* BECount = getBECount(Start, End, 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);
+ const SCEV* MaxBECount = getBECount(MinStart, MaxEnd, Step);;
return BackedgeTakenInfo(BECount, MaxBECount);
}
- return UnknownValue;
+ return CouldNotCompute;
}
/// getNumIterationsInRange - Return the number of iterations of this loop that
/// this is that it returns the first iteration number where the value is not in
/// the condition, thus computing the exit count. If the iteration count can't
/// be computed, an instance of SCEVCouldNotCompute is returned.
-SCEVHandle SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range,
+const SCEV* SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range,
ScalarEvolution &SE) const {
if (Range.isFullSet()) // Infinite loop.
return SE.getCouldNotCompute();
// If the start is a non-zero constant, shift the range to simplify things.
if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(getStart()))
if (!SC->getValue()->isZero()) {
- std::vector<SCEVHandle> Operands(op_begin(), op_end());
+ SmallVector<const SCEV*, 4> Operands(op_begin(), op_end());
Operands[0] = SE.getIntegerSCEV(0, SC->getType());
- SCEVHandle Shifted = SE.getAddRecExpr(Operands, getLoop());
+ const SCEV* Shifted = SE.getAddRecExpr(Operands, getLoop());
if (const SCEVAddRecExpr *ShiftedAddRec =
dyn_cast<SCEVAddRecExpr>(Shifted))
return ShiftedAddRec->getNumIterationsInRange(
// iteration exits.
unsigned BitWidth = SE.getTypeSizeInBits(getType());
if (!Range.contains(APInt(BitWidth, 0)))
- return SE.getConstant(ConstantInt::get(getType(),0));
+ return SE.getIntegerSCEV(0, getType());
if (isAffine()) {
// If this is an affine expression then we have this situation:
// 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<const SCEV*, 4> NewOps(op_begin(), op_end());
NewOps[0] = SE.getNegativeSCEV(SE.getConstant(Range.getUpper()));
- SCEVHandle NewAddRec = SE.getAddRecExpr(NewOps, getLoop());
+ const SCEV* NewAddRec = SE.getAddRecExpr(NewOps, getLoop());
// Next, solve the constructed addrec
- std::pair<SCEVHandle,SCEVHandle> Roots =
+ std::pair<const SCEV*,const SCEV*> Roots =
SolveQuadraticEquation(cast<SCEVAddRecExpr>(NewAddRec), SE);
const SCEVConstant *R1 = dyn_cast<SCEVConstant>(Roots.first);
const SCEVConstant *R2 = dyn_cast<SCEVConstant>(Roots.second);
// SCEVCallbackVH Class Implementation
//===----------------------------------------------------------------------===//
-void SCEVCallbackVH::deleted() {
+void ScalarEvolution::SCEVCallbackVH::deleted() {
assert(SE && "SCEVCallbackVH called with a non-null ScalarEvolution!");
if (PHINode *PN = dyn_cast<PHINode>(getValPtr()))
SE->ConstantEvolutionLoopExitValue.erase(PN);
// this now dangles!
}
-void SCEVCallbackVH::allUsesReplacedWith(Value *) {
+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,
// this may dangle!
}
-SCEVCallbackVH::SCEVCallbackVH(Value *V, ScalarEvolution *se)
+ScalarEvolution::SCEVCallbackVH::SCEVCallbackVH(Value *V, ScalarEvolution *se)
: CallbackVH(V), SE(se) {}
//===----------------------------------------------------------------------===//
//===----------------------------------------------------------------------===//
ScalarEvolution::ScalarEvolution()
- : FunctionPass(&ID), UnknownValue(new SCEVCouldNotCompute()) {
+ : FunctionPass(&ID), CouldNotCompute(new SCEVCouldNotCompute()) {
}
bool ScalarEvolution::runOnFunction(Function &F) {
BackedgeTakenCounts.clear();
ConstantEvolutionLoopExitValue.clear();
ValuesAtScopes.clear();
+
+ for (std::map<ConstantInt*, SCEVConstant*>::iterator
+ I = SCEVConstants.begin(), E = SCEVConstants.end(); I != E; ++I)
+ delete I->second;
+ for (std::map<std::pair<const SCEV*, const Type*>,
+ SCEVTruncateExpr*>::iterator I = SCEVTruncates.begin(),
+ E = SCEVTruncates.end(); I != E; ++I)
+ delete I->second;
+ for (std::map<std::pair<const SCEV*, const Type*>,
+ SCEVZeroExtendExpr*>::iterator I = SCEVZeroExtends.begin(),
+ E = SCEVZeroExtends.end(); I != E; ++I)
+ delete I->second;
+ for (std::map<std::pair<unsigned, std::vector<const SCEV*> >,
+ SCEVCommutativeExpr*>::iterator I = SCEVCommExprs.begin(),
+ E = SCEVCommExprs.end(); I != E; ++I)
+ delete I->second;
+ for (std::map<std::pair<const SCEV*, const SCEV*>, SCEVUDivExpr*>::iterator
+ I = SCEVUDivs.begin(), E = SCEVUDivs.end(); I != E; ++I)
+ delete I->second;
+ for (std::map<std::pair<const SCEV*, const Type*>,
+ SCEVSignExtendExpr*>::iterator I = SCEVSignExtends.begin(),
+ E = SCEVSignExtends.end(); I != E; ++I)
+ delete I->second;
+ for (std::map<std::pair<const Loop *, std::vector<const SCEV*> >,
+ SCEVAddRecExpr*>::iterator I = SCEVAddRecExprs.begin(),
+ E = SCEVAddRecExprs.end(); I != E; ++I)
+ delete I->second;
+ for (std::map<Value*, SCEVUnknown*>::iterator I = SCEVUnknowns.begin(),
+ E = SCEVUnknowns.end(); I != E; ++I)
+ delete I->second;
+
+ SCEVConstants.clear();
+ SCEVTruncates.clear();
+ SCEVZeroExtends.clear();
+ SCEVCommExprs.clear();
+ SCEVUDivs.clear();
+ SCEVSignExtends.clear();
+ SCEVAddRecExprs.clear();
+ SCEVUnknowns.clear();
}
void ScalarEvolution::getAnalysisUsage(AnalysisUsage &AU) const {
OS << "Unpredictable backedge-taken count. ";
}
+ OS << "\n";
+ OS << "Loop " << L->getHeader()->getName() << ": ";
+
+ if (!isa<SCEVCouldNotCompute>(SE->getMaxBackedgeTakenCount(L))) {
+ OS << "max backedge-taken count is " << *SE->getMaxBackedgeTakenCount(L);
+ } else {
+ OS << "Unpredictable max backedge-taken count. ";
+ }
+
OS << "\n";
}
if (isSCEVable(I->getType())) {
OS << *I;
OS << " --> ";
- SCEVHandle SV = SE.getSCEV(&*I);
+ const SCEV* SV = SE.getSCEV(&*I);
SV->print(OS);
- OS << "\t\t";
- if (const Loop *L = LI->getLoopFor((*I).getParent())) {
- OS << "Exits: ";
- SCEVHandle ExitValue = SE.getSCEVAtScope(&*I, L->getParentLoop());
- if (isa<SCEVCouldNotCompute>(ExitValue)) {
+ const Loop *L = LI->getLoopFor((*I).getParent());
+
+ const SCEV* AtUse = SE.getSCEVAtScope(SV, L);
+ if (AtUse != SV) {
+ OS << " --> ";
+ AtUse->print(OS);
+ }
+
+ if (L) {
+ OS << "\t\t" "Exits: ";
+ const SCEV* ExitValue = SE.getSCEVAtScope(SV, L->getParentLoop());
+ if (!ExitValue->isLoopInvariant(L)) {
OS << "<<Unknown>>";
} else {
OS << *ExitValue;
}
}
-
OS << "\n";
}
projects / oota-llvm.git / blobdiff