#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Assembly/Writer.h"
#include "llvm/Target/TargetData.h"
-#include "llvm/Transforms/Scalar.h"
-#include "llvm/Support/CFG.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/ConstantRange.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
-#include <ostream>
#include <algorithm>
-#include <cmath>
using namespace llvm;
STATISTIC(NumArrayLenItCounts,
return false;
}
+bool SCEV::isOne() const {
+ if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(this))
+ return SC->getValue()->isOne();
+ return false;
+}
SCEVCouldNotCompute::SCEVCouldNotCompute() : SCEV(scCouldNotCompute) {}
SCEVCouldNotCompute::~SCEVCouldNotCompute() {}
// SCEVTruncates - Only allow the creation of one SCEVTruncateExpr for any
// particular input. Don't use a SCEVHandle here, or else the object will
// never be deleted!
-static ManagedStatic<std::map<std::pair<SCEV*, const Type*>,
+static ManagedStatic<std::map<std::pair<const SCEV*, const Type*>,
SCEVTruncateExpr*> > SCEVTruncates;
SCEVTruncateExpr::SCEVTruncateExpr(const SCEVHandle &op, const Type *ty)
// SCEVZeroExtends - Only allow the creation of one SCEVZeroExtendExpr for any
// particular input. Don't use a SCEVHandle here, or else the object will never
// be deleted!
-static ManagedStatic<std::map<std::pair<SCEV*, const Type*>,
+static ManagedStatic<std::map<std::pair<const SCEV*, const Type*>,
SCEVZeroExtendExpr*> > SCEVZeroExtends;
SCEVZeroExtendExpr::SCEVZeroExtendExpr(const SCEVHandle &op, const Type *ty)
// SCEVSignExtends - Only allow the creation of one SCEVSignExtendExpr for any
// particular input. Don't use a SCEVHandle here, or else the object will never
// be deleted!
-static ManagedStatic<std::map<std::pair<SCEV*, const Type*>,
+static ManagedStatic<std::map<std::pair<const SCEV*, const Type*>,
SCEVSignExtendExpr*> > SCEVSignExtends;
SCEVSignExtendExpr::SCEVSignExtendExpr(const SCEVHandle &op, const Type *ty)
// SCEVCommExprs - Only allow the creation of one SCEVCommutativeExpr for any
// particular input. Don't use a SCEVHandle here, or else the object will never
// be deleted!
-static ManagedStatic<std::map<std::pair<unsigned, std::vector<SCEV*> >,
+static ManagedStatic<std::map<std::pair<unsigned, std::vector<const SCEV*> >,
SCEVCommutativeExpr*> > SCEVCommExprs;
SCEVCommutativeExpr::~SCEVCommutativeExpr() {
- SCEVCommExprs->erase(std::make_pair(getSCEVType(),
- std::vector<SCEV*>(Operands.begin(),
- Operands.end())));
+ std::vector<const SCEV*> SCEVOps(Operands.begin(), Operands.end());
+ SCEVCommExprs->erase(std::make_pair(getSCEVType(), SCEVOps));
}
void SCEVCommutativeExpr::print(raw_ostream &OS) const {
SCEVHandle H =
getOperand(i)->replaceSymbolicValuesWithConcrete(Sym, Conc, SE);
if (H != getOperand(i)) {
- std::vector<SCEVHandle> NewOps;
+ SmallVector<SCEVHandle, 8> NewOps;
NewOps.reserve(getNumOperands());
for (unsigned j = 0; j != i; ++j)
NewOps.push_back(getOperand(j));
return this;
}
-bool SCEVCommutativeExpr::dominates(BasicBlock *BB, DominatorTree *DT) const {
+bool SCEVNAryExpr::dominates(BasicBlock *BB, DominatorTree *DT) const {
for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
if (!getOperand(i)->dominates(BB, DT))
return false;
// SCEVUDivs - Only allow the creation of one SCEVUDivExpr for any particular
// input. Don't use a SCEVHandle here, or else the object will never be
// deleted!
-static ManagedStatic<std::map<std::pair<SCEV*, SCEV*>,
+static ManagedStatic<std::map<std::pair<const SCEV*, const SCEV*>,
SCEVUDivExpr*> > SCEVUDivs;
SCEVUDivExpr::~SCEVUDivExpr() {
}
const Type *SCEVUDivExpr::getType() const {
- return LHS->getType();
+ // In most cases the types of LHS and RHS will be the same, but in some
+ // crazy cases one or the other may be a pointer. ScalarEvolution doesn't
+ // depend on the type for correctness, but handling types carefully can
+ // avoid extra casts in the SCEVExpander. The LHS is more likely to be
+ // a pointer type than the RHS, so use the RHS' type here.
+ return RHS->getType();
}
// SCEVAddRecExprs - Only allow the creation of one SCEVAddRecExpr for any
// particular input. Don't use a SCEVHandle here, or else the object will never
// be deleted!
-static ManagedStatic<std::map<std::pair<const Loop *, std::vector<SCEV*> >,
+static ManagedStatic<std::map<std::pair<const Loop *,
+ std::vector<const SCEV*> >,
SCEVAddRecExpr*> > SCEVAddRecExprs;
SCEVAddRecExpr::~SCEVAddRecExpr() {
- SCEVAddRecExprs->erase(std::make_pair(L,
- std::vector<SCEV*>(Operands.begin(),
- Operands.end())));
-}
-
-bool SCEVAddRecExpr::dominates(BasicBlock *BB, DominatorTree *DT) const {
- for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
- if (!getOperand(i)->dominates(BB, DT))
- return false;
- }
- return true;
+ 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,
SCEVHandle H =
getOperand(i)->replaceSymbolicValuesWithConcrete(Sym, Conc, SE);
if (H != getOperand(i)) {
- std::vector<SCEVHandle> NewOps;
+ SmallVector<SCEVHandle, 8> NewOps;
NewOps.reserve(getNumOperands());
for (unsigned j = 0; j != i; ++j)
NewOps.push_back(getOperand(j));
bool SCEVAddRecExpr::isLoopInvariant(const Loop *QueryLoop) const {
// This recurrence is invariant w.r.t to QueryLoop iff QueryLoop doesn't
// contain L and if the start is invariant.
- return !QueryLoop->contains(L->getHeader()) &&
+ // Add recurrences are never invariant in the function-body (null loop).
+ return QueryLoop &&
+ !QueryLoop->contains(L->getHeader()) &&
getOperand(0)->isLoopInvariant(QueryLoop);
}
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;
}
/// SCEVComplexityCompare - Return true if the complexity of the LHS is less
/// than the complexity of the RHS. This comparator is used to canonicalize
/// expressions.
- struct VISIBILITY_HIDDEN SCEVComplexityCompare {
+ class VISIBILITY_HIDDEN SCEVComplexityCompare {
+ LoopInfo *LI;
+ public:
+ explicit SCEVComplexityCompare(LoopInfo *li) : LI(li) {}
+
bool operator()(const SCEV *LHS, const SCEV *RHS) const {
- return LHS->getSCEVType() < RHS->getSCEVType();
+ // Primarily, sort the SCEVs by their getSCEVType().
+ if (LHS->getSCEVType() != RHS->getSCEVType())
+ return LHS->getSCEVType() < RHS->getSCEVType();
+
+ // Aside from the getSCEVType() ordering, the particular ordering
+ // isn't very important except that it's beneficial to be consistent,
+ // so that (a + b) and (b + a) don't end up as different expressions.
+
+ // Sort SCEVUnknown values with some loose heuristics. TODO: This is
+ // not as complete as it could be.
+ if (const SCEVUnknown *LU = dyn_cast<SCEVUnknown>(LHS)) {
+ const SCEVUnknown *RU = cast<SCEVUnknown>(RHS);
+
+ // Order pointer values after integer values. This helps SCEVExpander
+ // form GEPs.
+ if (isa<PointerType>(LU->getType()) && !isa<PointerType>(RU->getType()))
+ return false;
+ if (isa<PointerType>(RU->getType()) && !isa<PointerType>(LU->getType()))
+ return true;
+
+ // Compare getValueID values.
+ if (LU->getValue()->getValueID() != RU->getValue()->getValueID())
+ return LU->getValue()->getValueID() < RU->getValue()->getValueID();
+
+ // Sort arguments by their position.
+ if (const Argument *LA = dyn_cast<Argument>(LU->getValue())) {
+ const Argument *RA = cast<Argument>(RU->getValue());
+ return LA->getArgNo() < RA->getArgNo();
+ }
+
+ // For instructions, compare their loop depth, and their opcode.
+ // This is pretty loose.
+ if (Instruction *LV = dyn_cast<Instruction>(LU->getValue())) {
+ Instruction *RV = cast<Instruction>(RU->getValue());
+
+ // Compare loop depths.
+ if (LI->getLoopDepth(LV->getParent()) !=
+ LI->getLoopDepth(RV->getParent()))
+ return LI->getLoopDepth(LV->getParent()) <
+ LI->getLoopDepth(RV->getParent());
+
+ // Compare opcodes.
+ if (LV->getOpcode() != RV->getOpcode())
+ return LV->getOpcode() < RV->getOpcode();
+
+ // Compare the number of operands.
+ if (LV->getNumOperands() != RV->getNumOperands())
+ return LV->getNumOperands() < RV->getNumOperands();
+ }
+
+ return false;
+ }
+
+ // Compare constant values.
+ if (const SCEVConstant *LC = dyn_cast<SCEVConstant>(LHS)) {
+ const SCEVConstant *RC = cast<SCEVConstant>(RHS);
+ return LC->getValue()->getValue().ult(RC->getValue()->getValue());
+ }
+
+ // Compare addrec loop depths.
+ if (const SCEVAddRecExpr *LA = dyn_cast<SCEVAddRecExpr>(LHS)) {
+ const SCEVAddRecExpr *RA = cast<SCEVAddRecExpr>(RHS);
+ if (LA->getLoop()->getLoopDepth() != RA->getLoop()->getLoopDepth())
+ return LA->getLoop()->getLoopDepth() < RA->getLoop()->getLoopDepth();
+ }
+
+ // Lexicographically compare n-ary expressions.
+ if (const SCEVNAryExpr *LC = dyn_cast<SCEVNAryExpr>(LHS)) {
+ const SCEVNAryExpr *RC = cast<SCEVNAryExpr>(RHS);
+ for (unsigned i = 0, e = LC->getNumOperands(); i != e; ++i) {
+ if (i >= RC->getNumOperands())
+ return false;
+ if (operator()(LC->getOperand(i), RC->getOperand(i)))
+ return true;
+ if (operator()(RC->getOperand(i), LC->getOperand(i)))
+ return false;
+ }
+ return LC->getNumOperands() < RC->getNumOperands();
+ }
+
+ // Lexicographically compare udiv expressions.
+ if (const SCEVUDivExpr *LC = dyn_cast<SCEVUDivExpr>(LHS)) {
+ const SCEVUDivExpr *RC = cast<SCEVUDivExpr>(RHS);
+ if (operator()(LC->getLHS(), RC->getLHS()))
+ return true;
+ if (operator()(RC->getLHS(), LC->getLHS()))
+ return false;
+ if (operator()(LC->getRHS(), RC->getRHS()))
+ return true;
+ if (operator()(RC->getRHS(), LC->getRHS()))
+ return false;
+ return false;
+ }
+
+ // Compare cast expressions by operand.
+ if (const SCEVCastExpr *LC = dyn_cast<SCEVCastExpr>(LHS)) {
+ const SCEVCastExpr *RC = cast<SCEVCastExpr>(RHS);
+ return operator()(LC->getOperand(), RC->getOperand());
+ }
+
+ assert(0 && "Unknown SCEV kind!");
+ return false;
}
};
}
/// this to depend on where the addresses of various SCEV objects happened to
/// land in memory.
///
-static void GroupByComplexity(std::vector<SCEVHandle> &Ops) {
+static void GroupByComplexity(SmallVectorImpl<SCEVHandle> &Ops,
+ LoopInfo *LI) {
if (Ops.size() < 2) return; // Noop
if (Ops.size() == 2) {
// This is the common case, which also happens to be trivially simple.
// Special case it.
- if (SCEVComplexityCompare()(Ops[1], Ops[0]))
+ if (SCEVComplexityCompare(LI)(Ops[1], Ops[0]))
std::swap(Ops[0], Ops[1]);
return;
}
// Do the rough sort by complexity.
- std::sort(Ops.begin(), Ops.end(), SCEVComplexityCompare());
+ std::stable_sort(Ops.begin(), Ops.end(), SCEVComplexityCompare(LI));
// Now that we are sorted by complexity, group elements of the same
// complexity. Note that this is, at worst, N^2, but the vector is likely to
// be extremely short in practice. Note that we take this approach because we
// do not want to depend on the addresses of the objects we are grouping.
for (unsigned i = 0, e = Ops.size(); i != e-2; ++i) {
- SCEV *S = Ops[i];
+ const SCEV *S = Ops[i];
unsigned Complexity = S->getSCEVType();
// If there are any objects of the same complexity and same value as this
//===----------------------------------------------------------------------===//
/// BinomialCoefficient - Compute BC(It, K). The result has width W.
-// Assume, K > 0.
+/// Assume, K > 0.
static SCEVHandle BinomialCoefficient(SCEVHandle It, unsigned K,
ScalarEvolution &SE,
const Type* ResultTy) {
"This is not a conversion to a SCEVable type!");
Ty = getEffectiveSCEVType(Ty);
- if (SCEVConstant *SC = dyn_cast<SCEVConstant>(Op))
+ if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op))
return getUnknown(
ConstantExpr::getTrunc(SC->getValue(), Ty));
// trunc(trunc(x)) --> trunc(x)
- if (SCEVTruncateExpr *ST = dyn_cast<SCEVTruncateExpr>(Op))
+ if (const SCEVTruncateExpr *ST = dyn_cast<SCEVTruncateExpr>(Op))
return getTruncateExpr(ST->getOperand(), Ty);
// trunc(sext(x)) --> sext(x) if widening or trunc(x) if narrowing
- if (SCEVSignExtendExpr *SS = dyn_cast<SCEVSignExtendExpr>(Op))
+ if (const SCEVSignExtendExpr *SS = dyn_cast<SCEVSignExtendExpr>(Op))
return getTruncateOrSignExtend(SS->getOperand(), Ty);
// trunc(zext(x)) --> zext(x) if widening or trunc(x) if narrowing
- if (SCEVZeroExtendExpr *SZ = dyn_cast<SCEVZeroExtendExpr>(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 (SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Op)) {
- std::vector<SCEVHandle> Operands;
+ if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Op)) {
+ SmallVector<SCEVHandle, 4> Operands;
for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i)
- // FIXME: This should allow truncation of other expression types!
- if (isa<SCEVConstant>(AddRec->getOperand(i)))
- Operands.push_back(getTruncateExpr(AddRec->getOperand(i), Ty));
- else
- break;
- if (Operands.size() == AddRec->getNumOperands())
- return getAddRecExpr(Operands, AddRec->getLoop());
+ Operands.push_back(getTruncateExpr(AddRec->getOperand(i), Ty));
+ return getAddRecExpr(Operands, AddRec->getLoop());
}
SCEVTruncateExpr *&Result = (*SCEVTruncates)[std::make_pair(Op, Ty)];
"This is not a conversion to a SCEVable type!");
Ty = getEffectiveSCEVType(Ty);
- if (SCEVConstant *SC = dyn_cast<SCEVConstant>(Op)) {
+ if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op)) {
const Type *IntTy = getEffectiveSCEVType(Ty);
Constant *C = ConstantExpr::getZExt(SC->getValue(), IntTy);
if (IntTy != Ty) C = ConstantExpr::getIntToPtr(C, Ty);
}
// zext(zext(x)) --> zext(x)
- if (SCEVZeroExtendExpr *SZ = dyn_cast<SCEVZeroExtendExpr>(Op))
+ if (const SCEVZeroExtendExpr *SZ = dyn_cast<SCEVZeroExtendExpr>(Op))
return getZeroExtendExpr(SZ->getOperand(), Ty);
// If the input value is a chrec scev, and we can prove that the value
// did not overflow the old, smaller, value, we can zero extend all of the
// operands (often constants). This allows analysis of something like
// this: for (unsigned char X = 0; X < 100; ++X) { int Y = X; }
- if (SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Op))
+ if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Op))
if (AR->isAffine()) {
// Check whether the backedge-taken count is SCEVCouldNotCompute.
// Note that this serves two purposes: It filters out loops that are
// the addrec's type. The count is always unsigned.
SCEVHandle CastedMaxBECount =
getTruncateOrZeroExtend(MaxBECount, Start->getType());
- if (MaxBECount ==
- getTruncateOrZeroExtend(CastedMaxBECount, MaxBECount->getType())) {
+ SCEVHandle RecastedMaxBECount =
+ getTruncateOrZeroExtend(CastedMaxBECount, MaxBECount->getType());
+ if (MaxBECount == RecastedMaxBECount) {
const Type *WideTy =
IntegerType::get(getTypeSizeInBits(Start->getType()) * 2);
// Check whether Start+Step*MaxBECount has no unsigned overflow.
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))))
+ SCEVHandle OperandExtendedAdd =
+ getAddExpr(getZeroExtendExpr(Start, WideTy),
+ getMulExpr(getZeroExtendExpr(CastedMaxBECount, WideTy),
+ getZeroExtendExpr(Step, WideTy)));
+ if (getZeroExtendExpr(Add, WideTy) == OperandExtendedAdd)
// Return the expression with the addrec on the outside.
return getAddRecExpr(getZeroExtendExpr(Start, Ty),
getZeroExtendExpr(Step, Ty),
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),
"This is not a conversion to a SCEVable type!");
Ty = getEffectiveSCEVType(Ty);
- if (SCEVConstant *SC = dyn_cast<SCEVConstant>(Op)) {
+ if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op)) {
const Type *IntTy = getEffectiveSCEVType(Ty);
Constant *C = ConstantExpr::getSExt(SC->getValue(), IntTy);
if (IntTy != Ty) C = ConstantExpr::getIntToPtr(C, Ty);
}
// sext(sext(x)) --> sext(x)
- if (SCEVSignExtendExpr *SS = dyn_cast<SCEVSignExtendExpr>(Op))
+ if (const SCEVSignExtendExpr *SS = dyn_cast<SCEVSignExtendExpr>(Op))
return getSignExtendExpr(SS->getOperand(), Ty);
// If the input value is a chrec scev, and we can prove that the value
// did not overflow the old, smaller, value, we can sign extend all of the
// operands (often constants). This allows analysis of something like
// this: for (signed char X = 0; X < 100; ++X) { int Y = X; }
- if (SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Op))
+ if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Op))
if (AR->isAffine()) {
// Check whether the backedge-taken count is SCEVCouldNotCompute.
// Note that this serves two purposes: It filters out loops that are
// the addrec's type. The count is always unsigned.
SCEVHandle CastedMaxBECount =
getTruncateOrZeroExtend(MaxBECount, Start->getType());
- if (MaxBECount ==
- getTruncateOrZeroExtend(CastedMaxBECount, MaxBECount->getType())) {
+ SCEVHandle RecastedMaxBECount =
+ getTruncateOrZeroExtend(CastedMaxBECount, MaxBECount->getType());
+ if (MaxBECount == RecastedMaxBECount) {
const Type *WideTy =
IntegerType::get(getTypeSizeInBits(Start->getType()) * 2);
// Check whether Start+Step*MaxBECount has no signed overflow.
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))))
+ SCEVHandle OperandExtendedAdd =
+ getAddExpr(getSignExtendExpr(Start, WideTy),
+ getMulExpr(getZeroExtendExpr(CastedMaxBECount, WideTy),
+ getSignExtendExpr(Step, WideTy)));
+ if (getSignExtendExpr(Add, WideTy) == OperandExtendedAdd)
// Return the expression with the addrec on the outside.
return getAddRecExpr(getSignExtendExpr(Start, Ty),
getSignExtendExpr(Step, Ty),
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.
+///
+SCEVHandle ScalarEvolution::getAnyExtendExpr(const SCEVHandle &Op,
+ const Type *Ty) {
+ assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) &&
+ "This is not an extending conversion!");
+ assert(isSCEVable(Ty) &&
+ "This is not a conversion to a SCEVable type!");
+ Ty = getEffectiveSCEVType(Ty);
+
+ // Sign-extend negative constants.
+ if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op))
+ if (SC->getValue()->getValue().isNegative())
+ return getSignExtendExpr(Op, Ty);
+
+ // Peel off a truncate cast.
+ if (const SCEVTruncateExpr *T = dyn_cast<SCEVTruncateExpr>(Op)) {
+ SCEVHandle NewOp = T->getOperand();
+ if (getTypeSizeInBits(NewOp->getType()) < getTypeSizeInBits(Ty))
+ return getAnyExtendExpr(NewOp, Ty);
+ return getTruncateOrNoop(NewOp, Ty);
+ }
+
+ // Next try a zext cast. If the cast is folded, use it.
+ SCEVHandle ZExt = getZeroExtendExpr(Op, Ty);
+ if (!isa<SCEVZeroExtendExpr>(ZExt))
+ return ZExt;
+
+ // Next try a sext cast. If the cast is folded, use it.
+ SCEVHandle SExt = getSignExtendExpr(Op, Ty);
+ if (!isa<SCEVSignExtendExpr>(SExt))
+ return SExt;
+
+ // If the expression is obviously signed, use the sext cast value.
+ if (isa<SCEVSMaxExpr>(Op))
+ return SExt;
+
+ // Absent any other information, use the zext cast value.
+ return ZExt;
+}
+
+/// CollectAddOperandsWithScales - Process the given Ops list, which is
+/// a list of operands to be added under the given scale, update the given
+/// map. This is a helper function for getAddRecExpr. As an example of
+/// what it does, given a sequence of operands that would form an add
+/// expression like this:
+///
+/// m + n + 13 + (A * (o + p + (B * q + m + 29))) + r + (-1 * r)
+///
+/// where A and B are constants, update the map with these values:
+///
+/// (m, 1+A*B), (n, 1), (o, A), (p, A), (q, A*B), (r, 0)
+///
+/// and add 13 + A*B*29 to AccumulatedConstant.
+/// This will allow getAddRecExpr to produce this:
+///
+/// 13+A*B*29 + n + (m * (1+A*B)) + ((o + p) * A) + (q * A*B)
+///
+/// This form often exposes folding opportunities that are hidden in
+/// the original operand list.
+///
+/// Return true iff it appears that any interesting folding opportunities
+/// may be exposed. This helps getAddRecExpr short-circuit extra work in
+/// the common case where no interesting opportunities are present, and
+/// is also used as a check to avoid infinite recursion.
+///
+static bool
+CollectAddOperandsWithScales(DenseMap<SCEVHandle, APInt> &M,
+ SmallVector<SCEVHandle, 8> &NewOps,
+ APInt &AccumulatedConstant,
+ const SmallVectorImpl<SCEVHandle> &Ops,
+ const APInt &Scale,
+ ScalarEvolution &SE) {
+ bool Interesting = false;
+
+ // Iterate over the add operands.
+ for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
+ const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(Ops[i]);
+ if (Mul && isa<SCEVConstant>(Mul->getOperand(0))) {
+ APInt NewScale =
+ Scale * cast<SCEVConstant>(Mul->getOperand(0))->getValue()->getValue();
+ if (Mul->getNumOperands() == 2 && isa<SCEVAddExpr>(Mul->getOperand(1))) {
+ // A multiplication of a constant with another add; recurse.
+ Interesting |=
+ CollectAddOperandsWithScales(M, NewOps, AccumulatedConstant,
+ cast<SCEVAddExpr>(Mul->getOperand(1))
+ ->getOperands(),
+ NewScale, SE);
+ } else {
+ // A multiplication of a constant with some other value. Update
+ // the map.
+ SmallVector<SCEVHandle, 4> MulOps(Mul->op_begin()+1, Mul->op_end());
+ SCEVHandle Key = SE.getMulExpr(MulOps);
+ std::pair<DenseMap<SCEVHandle, APInt>::iterator, bool> Pair =
+ M.insert(std::make_pair(Key, APInt()));
+ if (Pair.second) {
+ Pair.first->second = NewScale;
+ NewOps.push_back(Pair.first->first);
+ } else {
+ Pair.first->second += NewScale;
+ // The map already had an entry for this value, which may indicate
+ // a folding opportunity.
+ Interesting = true;
+ }
+ }
+ } else if (const SCEVConstant *C = dyn_cast<SCEVConstant>(Ops[i])) {
+ // Pull a buried constant out to the outside.
+ if (Scale != 1 || AccumulatedConstant != 0 || C->isZero())
+ Interesting = true;
+ AccumulatedConstant += Scale * C->getValue()->getValue();
+ } else {
+ // An ordinary operand. Update the map.
+ std::pair<DenseMap<SCEVHandle, APInt>::iterator, bool> Pair =
+ M.insert(std::make_pair(Ops[i], APInt()));
+ if (Pair.second) {
+ Pair.first->second = Scale;
+ NewOps.push_back(Pair.first->first);
+ } else {
+ Pair.first->second += Scale;
+ // The map already had an entry for this value, which may indicate
+ // a folding opportunity.
+ Interesting = true;
+ }
+ }
+ }
+
+ return Interesting;
+}
+
+namespace {
+ struct APIntCompare {
+ bool operator()(const APInt &LHS, const APInt &RHS) const {
+ return LHS.ult(RHS);
+ }
+ };
+}
+
+/// getAddExpr - Get a canonical add expression, or something simpler if
+/// possible.
+SCEVHandle ScalarEvolution::getAddExpr(SmallVectorImpl<SCEVHandle> &Ops) {
assert(!Ops.empty() && "Cannot get empty add!");
if (Ops.size() == 1) return Ops[0];
+#ifndef NDEBUG
+ for (unsigned i = 1, e = Ops.size(); i != e; ++i)
+ assert(getEffectiveSCEVType(Ops[i]->getType()) ==
+ getEffectiveSCEVType(Ops[0]->getType()) &&
+ "SCEVAddExpr operand types don't match!");
+#endif
// Sort by complexity, this groups all similar expression types together.
- GroupByComplexity(Ops);
+ GroupByComplexity(Ops, LI);
// If there are any constants, fold them together.
unsigned Idx = 0;
- if (SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
+ if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
++Idx;
assert(Idx < Ops.size());
- while (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
+ while (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
// We found two constants, fold them together!
- ConstantInt *Fold = ConstantInt::get(LHSC->getValue()->getValue() +
- RHSC->getValue()->getValue());
- Ops[0] = getConstant(Fold);
+ Ops[0] = getConstant(LHSC->getValue()->getValue() +
+ RHSC->getValue()->getValue());
+ if (Ops.size() == 2) return Ops[0];
Ops.erase(Ops.begin()+1); // Erase the folded element
- if (Ops.size() == 1) return Ops[0];
LHSC = cast<SCEVConstant>(Ops[0]);
}
return getAddExpr(Ops);
}
- // Now we know the first non-constant operand. Skip past any cast SCEVs.
+ // Check for truncates. If all the operands are truncated from the same
+ // type, see if factoring out the truncate would permit the result to be
+ // folded. eg., trunc(x) + m*trunc(n) --> trunc(x + trunc(m)*n)
+ // if the contents of the resulting outer trunc fold to something simple.
+ for (; Idx < Ops.size() && isa<SCEVTruncateExpr>(Ops[Idx]); ++Idx) {
+ const SCEVTruncateExpr *Trunc = cast<SCEVTruncateExpr>(Ops[Idx]);
+ const Type *DstType = Trunc->getType();
+ const Type *SrcType = Trunc->getOperand()->getType();
+ SmallVector<SCEVHandle, 8> LargeOps;
+ bool Ok = true;
+ // Check all the operands to see if they can be represented in the
+ // source type of the truncate.
+ for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
+ if (const SCEVTruncateExpr *T = dyn_cast<SCEVTruncateExpr>(Ops[i])) {
+ if (T->getOperand()->getType() != SrcType) {
+ Ok = false;
+ break;
+ }
+ LargeOps.push_back(T->getOperand());
+ } else if (const SCEVConstant *C = dyn_cast<SCEVConstant>(Ops[i])) {
+ // This could be either sign or zero extension, but sign extension
+ // is much more likely to be foldable here.
+ LargeOps.push_back(getSignExtendExpr(C, SrcType));
+ } else if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(Ops[i])) {
+ SmallVector<SCEVHandle, 8> LargeMulOps;
+ for (unsigned j = 0, f = M->getNumOperands(); j != f && Ok; ++j) {
+ if (const SCEVTruncateExpr *T =
+ dyn_cast<SCEVTruncateExpr>(M->getOperand(j))) {
+ if (T->getOperand()->getType() != SrcType) {
+ Ok = false;
+ break;
+ }
+ LargeMulOps.push_back(T->getOperand());
+ } else if (const SCEVConstant *C =
+ dyn_cast<SCEVConstant>(M->getOperand(j))) {
+ // This could be either sign or zero extension, but sign extension
+ // is much more likely to be foldable here.
+ LargeMulOps.push_back(getSignExtendExpr(C, SrcType));
+ } else {
+ Ok = false;
+ break;
+ }
+ }
+ if (Ok)
+ LargeOps.push_back(getMulExpr(LargeMulOps));
+ } else {
+ Ok = false;
+ break;
+ }
+ }
+ if (Ok) {
+ // Evaluate the expression in the larger type.
+ SCEVHandle Fold = getAddExpr(LargeOps);
+ // If it folds to something simple, use it. Otherwise, don't.
+ if (isa<SCEVConstant>(Fold) || isa<SCEVUnknown>(Fold))
+ return getTruncateExpr(Fold, DstType);
+ }
+ }
+
+ // Skip past any other cast SCEVs.
while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scAddExpr)
++Idx;
// If there are add operands they would be next.
if (Idx < Ops.size()) {
bool DeletedAdd = false;
- while (SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[Idx])) {
+ while (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[Idx])) {
// If we have an add, expand the add operands onto the end of the operands
// list.
Ops.insert(Ops.end(), Add->op_begin(), Add->op_end());
while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scMulExpr)
++Idx;
+ // Check to see if there are any folding opportunities present with
+ // operands multiplied by constant values.
+ if (Idx < Ops.size() && isa<SCEVMulExpr>(Ops[Idx])) {
+ uint64_t BitWidth = getTypeSizeInBits(Ty);
+ DenseMap<SCEVHandle, APInt> M;
+ SmallVector<SCEVHandle, 8> NewOps;
+ APInt AccumulatedConstant(BitWidth, 0);
+ if (CollectAddOperandsWithScales(M, NewOps, AccumulatedConstant,
+ Ops, APInt(BitWidth, 1), *this)) {
+ // Some interesting folding opportunity is present, so its worthwhile to
+ // re-generate the operands list. Group the operands by constant scale,
+ // to avoid multiplying by the same constant scale multiple times.
+ std::map<APInt, SmallVector<SCEVHandle, 4>, APIntCompare> MulOpLists;
+ for (SmallVector<SCEVHandle, 8>::iterator I = NewOps.begin(),
+ E = NewOps.end(); I != E; ++I)
+ MulOpLists[M.find(*I)->second].push_back(*I);
+ // Re-generate the operands list.
+ Ops.clear();
+ if (AccumulatedConstant != 0)
+ Ops.push_back(getConstant(AccumulatedConstant));
+ for (std::map<APInt, SmallVector<SCEVHandle, 4>, APIntCompare>::iterator I =
+ MulOpLists.begin(), E = MulOpLists.end(); I != E; ++I)
+ if (I->first != 0)
+ Ops.push_back(getMulExpr(getConstant(I->first), getAddExpr(I->second)));
+ if (Ops.empty())
+ return getIntegerSCEV(0, Ty);
+ if (Ops.size() == 1)
+ return Ops[0];
+ return getAddExpr(Ops);
+ }
+ }
+
// If we are adding something to a multiply expression, make sure the
// something is not already an operand of the multiply. If so, merge it into
// the multiply.
for (; Idx < Ops.size() && isa<SCEVMulExpr>(Ops[Idx]); ++Idx) {
- SCEVMulExpr *Mul = cast<SCEVMulExpr>(Ops[Idx]);
+ const SCEVMulExpr *Mul = cast<SCEVMulExpr>(Ops[Idx]);
for (unsigned MulOp = 0, e = Mul->getNumOperands(); MulOp != e; ++MulOp) {
- SCEV *MulOpSCEV = Mul->getOperand(MulOp);
+ const SCEV *MulOpSCEV = Mul->getOperand(MulOp);
for (unsigned AddOp = 0, e = Ops.size(); AddOp != e; ++AddOp)
- if (MulOpSCEV == Ops[AddOp] && !isa<SCEVConstant>(MulOpSCEV)) {
+ if (MulOpSCEV == Ops[AddOp] && !isa<SCEVConstant>(Ops[AddOp])) {
// Fold W + X + (X * Y * Z) --> W + (X * ((Y*Z)+1))
SCEVHandle InnerMul = Mul->getOperand(MulOp == 0);
if (Mul->getNumOperands() != 2) {
// If the multiply has more than two operands, we must get the
// Y*Z term.
- std::vector<SCEVHandle> MulOps(Mul->op_begin(), Mul->op_end());
+ SmallVector<SCEVHandle, 4> MulOps(Mul->op_begin(), Mul->op_end());
MulOps.erase(MulOps.begin()+MulOp);
InnerMul = getMulExpr(MulOps);
}
for (unsigned OtherMulIdx = Idx+1;
OtherMulIdx < Ops.size() && isa<SCEVMulExpr>(Ops[OtherMulIdx]);
++OtherMulIdx) {
- SCEVMulExpr *OtherMul = cast<SCEVMulExpr>(Ops[OtherMulIdx]);
+ const SCEVMulExpr *OtherMul = cast<SCEVMulExpr>(Ops[OtherMulIdx]);
// If MulOp occurs in OtherMul, we can fold the two multiplies
// together.
for (unsigned OMulOp = 0, e = OtherMul->getNumOperands();
// Fold X + (A*B*C) + (A*D*E) --> X + (A*(B*C+D*E))
SCEVHandle InnerMul1 = Mul->getOperand(MulOp == 0);
if (Mul->getNumOperands() != 2) {
- std::vector<SCEVHandle> MulOps(Mul->op_begin(), Mul->op_end());
+ SmallVector<SCEVHandle, 4> MulOps(Mul->op_begin(), Mul->op_end());
MulOps.erase(MulOps.begin()+MulOp);
InnerMul1 = getMulExpr(MulOps);
}
SCEVHandle InnerMul2 = OtherMul->getOperand(OMulOp == 0);
if (OtherMul->getNumOperands() != 2) {
- std::vector<SCEVHandle> MulOps(OtherMul->op_begin(),
+ SmallVector<SCEVHandle, 4> MulOps(OtherMul->op_begin(),
OtherMul->op_end());
MulOps.erase(MulOps.begin()+OMulOp);
InnerMul2 = getMulExpr(MulOps);
for (; Idx < Ops.size() && isa<SCEVAddRecExpr>(Ops[Idx]); ++Idx) {
// Scan all of the other operands to this add and add them to the vector if
// they are loop invariant w.r.t. the recurrence.
- std::vector<SCEVHandle> LIOps;
- SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(Ops[Idx]);
+ SmallVector<SCEVHandle, 8> LIOps;
+ const SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(Ops[Idx]);
for (unsigned i = 0, e = Ops.size(); i != e; ++i)
if (Ops[i]->isLoopInvariant(AddRec->getLoop())) {
LIOps.push_back(Ops[i]);
// NLI + LI + {Start,+,Step} --> NLI + {LI+Start,+,Step}
LIOps.push_back(AddRec->getStart());
- std::vector<SCEVHandle> AddRecOps(AddRec->op_begin(), AddRec->op_end());
+ SmallVector<SCEVHandle, 4> AddRecOps(AddRec->op_begin(),
+ AddRec->op_end());
AddRecOps[0] = getAddExpr(LIOps);
SCEVHandle NewRec = getAddRecExpr(AddRecOps, AddRec->getLoop());
for (unsigned OtherIdx = Idx+1;
OtherIdx < Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);++OtherIdx)
if (OtherIdx != Idx) {
- SCEVAddRecExpr *OtherAddRec = cast<SCEVAddRecExpr>(Ops[OtherIdx]);
+ const SCEVAddRecExpr *OtherAddRec = cast<SCEVAddRecExpr>(Ops[OtherIdx]);
if (AddRec->getLoop() == OtherAddRec->getLoop()) {
// Other + {A,+,B} + {C,+,D} --> Other + {A+C,+,B+D}
- std::vector<SCEVHandle> NewOps(AddRec->op_begin(), AddRec->op_end());
+ SmallVector<SCEVHandle, 4> NewOps(AddRec->op_begin(), AddRec->op_end());
for (unsigned i = 0, e = OtherAddRec->getNumOperands(); i != e; ++i) {
if (i >= NewOps.size()) {
NewOps.insert(NewOps.end(), OtherAddRec->op_begin()+i,
// Okay, it looks like we really DO need an add expr. Check to see if we
// already have one, otherwise create a new one.
- std::vector<SCEV*> SCEVOps(Ops.begin(), Ops.end());
+ std::vector<const SCEV*> SCEVOps(Ops.begin(), Ops.end());
SCEVCommutativeExpr *&Result = (*SCEVCommExprs)[std::make_pair(scAddExpr,
SCEVOps)];
if (Result == 0) Result = new SCEVAddExpr(Ops);
}
-SCEVHandle ScalarEvolution::getMulExpr(std::vector<SCEVHandle> &Ops) {
+/// getMulExpr - Get a canonical multiply expression, or something simpler if
+/// possible.
+SCEVHandle ScalarEvolution::getMulExpr(SmallVectorImpl<SCEVHandle> &Ops) {
assert(!Ops.empty() && "Cannot get empty mul!");
+#ifndef NDEBUG
+ for (unsigned i = 1, e = Ops.size(); i != e; ++i)
+ assert(getEffectiveSCEVType(Ops[i]->getType()) ==
+ getEffectiveSCEVType(Ops[0]->getType()) &&
+ "SCEVMulExpr operand types don't match!");
+#endif
// Sort by complexity, this groups all similar expression types together.
- GroupByComplexity(Ops);
+ GroupByComplexity(Ops, LI);
// If there are any constants, fold them together.
unsigned Idx = 0;
- if (SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
+ if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
// C1*(C2+V) -> C1*C2 + C1*V
if (Ops.size() == 2)
- if (SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[1]))
+ if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[1]))
if (Add->getNumOperands() == 2 &&
isa<SCEVConstant>(Add->getOperand(0)))
return getAddExpr(getMulExpr(LHSC, Add->getOperand(0)),
++Idx;
- while (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
+ while (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
// We found two constants, fold them together!
ConstantInt *Fold = ConstantInt::get(LHSC->getValue()->getValue() *
RHSC->getValue()->getValue());
// If there are mul operands inline them all into this expression.
if (Idx < Ops.size()) {
bool DeletedMul = false;
- while (SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(Ops[Idx])) {
+ while (const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(Ops[Idx])) {
// If we have an mul, expand the mul operands onto the end of the operands
// list.
Ops.insert(Ops.end(), Mul->op_begin(), Mul->op_end());
for (; Idx < Ops.size() && isa<SCEVAddRecExpr>(Ops[Idx]); ++Idx) {
// Scan all of the other operands to this mul and add them to the vector if
// they are loop invariant w.r.t. the recurrence.
- std::vector<SCEVHandle> LIOps;
- SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(Ops[Idx]);
+ SmallVector<SCEVHandle, 8> LIOps;
+ const SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(Ops[Idx]);
for (unsigned i = 0, e = Ops.size(); i != e; ++i)
if (Ops[i]->isLoopInvariant(AddRec->getLoop())) {
LIOps.push_back(Ops[i]);
// If we found some loop invariants, fold them into the recurrence.
if (!LIOps.empty()) {
// NLI * LI * {Start,+,Step} --> NLI * {LI*Start,+,LI*Step}
- std::vector<SCEVHandle> NewOps;
+ SmallVector<SCEVHandle, 4> NewOps;
NewOps.reserve(AddRec->getNumOperands());
if (LIOps.size() == 1) {
- SCEV *Scale = LIOps[0];
+ const SCEV *Scale = LIOps[0];
for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i)
NewOps.push_back(getMulExpr(Scale, AddRec->getOperand(i)));
} else {
for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) {
- std::vector<SCEVHandle> MulOps(LIOps);
+ SmallVector<SCEVHandle, 4> MulOps(LIOps.begin(), LIOps.end());
MulOps.push_back(AddRec->getOperand(i));
NewOps.push_back(getMulExpr(MulOps));
}
for (unsigned OtherIdx = Idx+1;
OtherIdx < Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);++OtherIdx)
if (OtherIdx != Idx) {
- SCEVAddRecExpr *OtherAddRec = cast<SCEVAddRecExpr>(Ops[OtherIdx]);
+ const SCEVAddRecExpr *OtherAddRec = cast<SCEVAddRecExpr>(Ops[OtherIdx]);
if (AddRec->getLoop() == OtherAddRec->getLoop()) {
// F * G --> {A,+,B} * {C,+,D} --> {A*C,+,F*D + G*B + B*D}
- SCEVAddRecExpr *F = AddRec, *G = OtherAddRec;
+ const SCEVAddRecExpr *F = AddRec, *G = OtherAddRec;
SCEVHandle NewStart = getMulExpr(F->getStart(),
G->getStart());
SCEVHandle B = F->getStepRecurrence(*this);
// Okay, it looks like we really DO need an mul expr. Check to see if we
// already have one, otherwise create a new one.
- std::vector<SCEV*> SCEVOps(Ops.begin(), Ops.end());
+ std::vector<const SCEV*> SCEVOps(Ops.begin(), Ops.end());
SCEVCommutativeExpr *&Result = (*SCEVCommExprs)[std::make_pair(scMulExpr,
SCEVOps)];
if (Result == 0)
return Result;
}
-SCEVHandle ScalarEvolution::getUDivExpr(const SCEVHandle &LHS, const SCEVHandle &RHS) {
- if (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS)) {
+/// getUDivExpr - Get a canonical multiply expression, or something simpler if
+/// possible.
+SCEVHandle ScalarEvolution::getUDivExpr(const SCEVHandle &LHS,
+ const SCEVHandle &RHS) {
+ assert(getEffectiveSCEVType(LHS->getType()) ==
+ getEffectiveSCEVType(RHS->getType()) &&
+ "SCEVUDivExpr operand types don't match!");
+
+ if (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS)) {
if (RHSC->getValue()->equalsInt(1))
return LHS; // X udiv 1 --> x
+ if (RHSC->isZero())
+ return getIntegerSCEV(0, LHS->getType()); // value is undefined
+
+ // Determine if the division can be folded into the operands of
+ // its operands.
+ // TODO: Generalize this to non-constants by using known-bits information.
+ const Type *Ty = LHS->getType();
+ unsigned LZ = RHSC->getValue()->getValue().countLeadingZeros();
+ unsigned MaxShiftAmt = getTypeSizeInBits(Ty) - LZ;
+ // For non-power-of-two values, effectively round the value up to the
+ // nearest power of two.
+ if (!RHSC->getValue()->getValue().isPowerOf2())
+ ++MaxShiftAmt;
+ const IntegerType *ExtTy =
+ IntegerType::get(getTypeSizeInBits(Ty) + MaxShiftAmt);
+ // {X,+,N}/C --> {X/C,+,N/C} if safe and N/C can be folded.
+ if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(LHS))
+ if (const SCEVConstant *Step =
+ dyn_cast<SCEVConstant>(AR->getStepRecurrence(*this)))
+ if (!Step->getValue()->getValue()
+ .urem(RHSC->getValue()->getValue()) &&
+ getZeroExtendExpr(AR, ExtTy) ==
+ getAddRecExpr(getZeroExtendExpr(AR->getStart(), ExtTy),
+ getZeroExtendExpr(Step, ExtTy),
+ AR->getLoop())) {
+ SmallVector<SCEVHandle, 4> Operands;
+ for (unsigned i = 0, e = AR->getNumOperands(); i != e; ++i)
+ Operands.push_back(getUDivExpr(AR->getOperand(i), RHS));
+ return getAddRecExpr(Operands, AR->getLoop());
+ }
+ // (A*B)/C --> A*(B/C) if safe and B/C can be folded.
+ if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(LHS)) {
+ SmallVector<SCEVHandle, 4> Operands;
+ for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i)
+ Operands.push_back(getZeroExtendExpr(M->getOperand(i), ExtTy));
+ if (getZeroExtendExpr(M, ExtTy) == getMulExpr(Operands))
+ // Find an operand that's safely divisible.
+ for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
+ SCEVHandle Op = M->getOperand(i);
+ SCEVHandle Div = getUDivExpr(Op, RHSC);
+ if (!isa<SCEVUDivExpr>(Div) && getMulExpr(Div, RHSC) == Op) {
+ const SmallVectorImpl<SCEVHandle> &MOperands = M->getOperands();
+ Operands = SmallVector<SCEVHandle, 4>(MOperands.begin(),
+ MOperands.end());
+ Operands[i] = Div;
+ return getMulExpr(Operands);
+ }
+ }
+ }
+ // (A+B)/C --> (A/C + B/C) if safe and A/C and B/C can be folded.
+ if (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(LHS)) {
+ SmallVector<SCEVHandle, 4> Operands;
+ for (unsigned i = 0, e = A->getNumOperands(); i != e; ++i)
+ Operands.push_back(getZeroExtendExpr(A->getOperand(i), ExtTy));
+ if (getZeroExtendExpr(A, ExtTy) == getAddExpr(Operands)) {
+ Operands.clear();
+ for (unsigned i = 0, e = A->getNumOperands(); i != e; ++i) {
+ SCEVHandle Op = getUDivExpr(A->getOperand(i), RHS);
+ if (isa<SCEVUDivExpr>(Op) || getMulExpr(Op, RHS) != A->getOperand(i))
+ break;
+ Operands.push_back(Op);
+ }
+ if (Operands.size() == A->getNumOperands())
+ return getAddExpr(Operands);
+ }
+ }
- if (SCEVConstant *LHSC = dyn_cast<SCEVConstant>(LHS)) {
+ // Fold if both operands are constant.
+ if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(LHS)) {
Constant *LHSCV = LHSC->getValue();
Constant *RHSCV = RHSC->getValue();
return getUnknown(ConstantExpr::getUDiv(LHSCV, RHSCV));
}
}
- // FIXME: implement folding of (X*4)/4 when we know X*4 doesn't overflow.
-
SCEVUDivExpr *&Result = (*SCEVUDivs)[std::make_pair(LHS, RHS)];
if (Result == 0) Result = new SCEVUDivExpr(LHS, RHS);
return Result;
}
-/// SCEVAddRecExpr::get - Get a add recurrence expression for the
-/// specified loop. Simplify the expression as much as possible.
+/// getAddRecExpr - Get an add recurrence expression for the specified loop.
+/// Simplify the expression as much as possible.
SCEVHandle ScalarEvolution::getAddRecExpr(const SCEVHandle &Start,
const SCEVHandle &Step, const Loop *L) {
- std::vector<SCEVHandle> Operands;
+ SmallVector<SCEVHandle, 4> Operands;
Operands.push_back(Start);
- if (SCEVAddRecExpr *StepChrec = dyn_cast<SCEVAddRecExpr>(Step))
+ if (const SCEVAddRecExpr *StepChrec = dyn_cast<SCEVAddRecExpr>(Step))
if (StepChrec->getLoop() == L) {
Operands.insert(Operands.end(), StepChrec->op_begin(),
StepChrec->op_end());
return getAddRecExpr(Operands, L);
}
-/// SCEVAddRecExpr::get - Get a add recurrence expression for the
-/// specified loop. Simplify the expression as much as possible.
-SCEVHandle ScalarEvolution::getAddRecExpr(std::vector<SCEVHandle> &Operands,
+/// getAddRecExpr - Get an add recurrence expression for the specified loop.
+/// Simplify the expression as much as possible.
+SCEVHandle ScalarEvolution::getAddRecExpr(SmallVectorImpl<SCEVHandle> &Operands,
const Loop *L) {
if (Operands.size() == 1) return Operands[0];
+#ifndef NDEBUG
+ for (unsigned i = 1, e = Operands.size(); i != e; ++i)
+ assert(getEffectiveSCEVType(Operands[i]->getType()) ==
+ getEffectiveSCEVType(Operands[0]->getType()) &&
+ "SCEVAddRecExpr operand types don't match!");
+#endif
if (Operands.back()->isZero()) {
Operands.pop_back();
}
// Canonicalize nested AddRecs in by nesting them in order of loop depth.
- if (SCEVAddRecExpr *NestedAR = dyn_cast<SCEVAddRecExpr>(Operands[0])) {
+ if (const SCEVAddRecExpr *NestedAR = dyn_cast<SCEVAddRecExpr>(Operands[0])) {
const Loop* NestedLoop = NestedAR->getLoop();
if (L->getLoopDepth() < NestedLoop->getLoopDepth()) {
- std::vector<SCEVHandle> NestedOperands(NestedAR->op_begin(),
- NestedAR->op_end());
+ SmallVector<SCEVHandle, 4> NestedOperands(NestedAR->op_begin(),
+ NestedAR->op_end());
SCEVHandle NestedARHandle(NestedAR);
Operands[0] = NestedAR->getStart();
NestedOperands[0] = getAddRecExpr(Operands, L);
}
}
- SCEVAddRecExpr *&Result =
- (*SCEVAddRecExprs)[std::make_pair(L, std::vector<SCEV*>(Operands.begin(),
- Operands.end()))];
+ std::vector<const SCEV*> SCEVOps(Operands.begin(), Operands.end());
+ SCEVAddRecExpr *&Result = (*SCEVAddRecExprs)[std::make_pair(L, SCEVOps)];
if (Result == 0) Result = new SCEVAddRecExpr(Operands, L);
return Result;
}
SCEVHandle ScalarEvolution::getSMaxExpr(const SCEVHandle &LHS,
const SCEVHandle &RHS) {
- std::vector<SCEVHandle> Ops;
+ SmallVector<SCEVHandle, 2> Ops;
Ops.push_back(LHS);
Ops.push_back(RHS);
return getSMaxExpr(Ops);
}
-SCEVHandle ScalarEvolution::getSMaxExpr(std::vector<SCEVHandle> Ops) {
+SCEVHandle
+ScalarEvolution::getSMaxExpr(SmallVectorImpl<SCEVHandle> &Ops) {
assert(!Ops.empty() && "Cannot get empty smax!");
if (Ops.size() == 1) return Ops[0];
+#ifndef NDEBUG
+ for (unsigned i = 1, e = Ops.size(); i != e; ++i)
+ assert(getEffectiveSCEVType(Ops[i]->getType()) ==
+ getEffectiveSCEVType(Ops[0]->getType()) &&
+ "SCEVSMaxExpr operand types don't match!");
+#endif
// Sort by complexity, this groups all similar expression types together.
- GroupByComplexity(Ops);
+ GroupByComplexity(Ops, LI);
// If there are any constants, fold them together.
unsigned Idx = 0;
- if (SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
+ if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
++Idx;
assert(Idx < Ops.size());
- while (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
+ while (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
// We found two constants, fold them together!
ConstantInt *Fold = ConstantInt::get(
APIntOps::smax(LHSC->getValue()->getValue(),
// onto our operand list, and recurse to simplify.
if (Idx < Ops.size()) {
bool DeletedSMax = false;
- while (SCEVSMaxExpr *SMax = dyn_cast<SCEVSMaxExpr>(Ops[Idx])) {
+ while (const SCEVSMaxExpr *SMax = dyn_cast<SCEVSMaxExpr>(Ops[Idx])) {
Ops.insert(Ops.end(), SMax->op_begin(), SMax->op_end());
Ops.erase(Ops.begin()+Idx);
DeletedSMax = true;
// Okay, it looks like we really DO need an smax expr. Check to see if we
// already have one, otherwise create a new one.
- std::vector<SCEV*> SCEVOps(Ops.begin(), Ops.end());
+ std::vector<const SCEV*> SCEVOps(Ops.begin(), Ops.end());
SCEVCommutativeExpr *&Result = (*SCEVCommExprs)[std::make_pair(scSMaxExpr,
SCEVOps)];
if (Result == 0) Result = new SCEVSMaxExpr(Ops);
SCEVHandle ScalarEvolution::getUMaxExpr(const SCEVHandle &LHS,
const SCEVHandle &RHS) {
- std::vector<SCEVHandle> Ops;
+ SmallVector<SCEVHandle, 2> Ops;
Ops.push_back(LHS);
Ops.push_back(RHS);
return getUMaxExpr(Ops);
}
-SCEVHandle ScalarEvolution::getUMaxExpr(std::vector<SCEVHandle> Ops) {
+SCEVHandle
+ScalarEvolution::getUMaxExpr(SmallVectorImpl<SCEVHandle> &Ops) {
assert(!Ops.empty() && "Cannot get empty umax!");
if (Ops.size() == 1) return Ops[0];
+#ifndef NDEBUG
+ for (unsigned i = 1, e = Ops.size(); i != e; ++i)
+ assert(getEffectiveSCEVType(Ops[i]->getType()) ==
+ getEffectiveSCEVType(Ops[0]->getType()) &&
+ "SCEVUMaxExpr operand types don't match!");
+#endif
// Sort by complexity, this groups all similar expression types together.
- GroupByComplexity(Ops);
+ GroupByComplexity(Ops, LI);
// If there are any constants, fold them together.
unsigned Idx = 0;
- if (SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
+ if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
++Idx;
assert(Idx < Ops.size());
- while (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
+ while (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
// We found two constants, fold them together!
ConstantInt *Fold = ConstantInt::get(
APIntOps::umax(LHSC->getValue()->getValue(),
// onto our operand list, and recurse to simplify.
if (Idx < Ops.size()) {
bool DeletedUMax = false;
- while (SCEVUMaxExpr *UMax = dyn_cast<SCEVUMaxExpr>(Ops[Idx])) {
+ while (const SCEVUMaxExpr *UMax = dyn_cast<SCEVUMaxExpr>(Ops[Idx])) {
Ops.insert(Ops.end(), UMax->op_begin(), UMax->op_end());
Ops.erase(Ops.begin()+Idx);
DeletedUMax = true;
// Okay, it looks like we really DO need a umax expr. Check to see if we
// already have one, otherwise create a new one.
- std::vector<SCEV*> SCEVOps(Ops.begin(), Ops.end());
+ std::vector<const SCEV*> SCEVOps(Ops.begin(), Ops.end());
SCEVCommutativeExpr *&Result = (*SCEVCommExprs)[std::make_pair(scUMaxExpr,
SCEVOps)];
if (Result == 0) Result = new SCEVUMaxExpr(Ops);
// Basic SCEV Analysis and PHI Idiom Recognition Code
//
-/// deleteValueFromRecords - This method should be called by the
-/// client before it removes an instruction from the program, to make sure
-/// that no dangling references are left around.
-void ScalarEvolution::deleteValueFromRecords(Value *V) {
- SmallVector<Value *, 16> Worklist;
-
- if (Scalars.erase(V)) {
- if (PHINode *PN = dyn_cast<PHINode>(V))
- ConstantEvolutionLoopExitValue.erase(PN);
- Worklist.push_back(V);
- }
-
- while (!Worklist.empty()) {
- Value *VV = Worklist.back();
- Worklist.pop_back();
-
- for (Instruction::use_iterator UI = VV->use_begin(), UE = VV->use_end();
- UI != UE; ++UI) {
- Instruction *Inst = cast<Instruction>(*UI);
- if (Scalars.erase(Inst)) {
- if (PHINode *PN = dyn_cast<PHINode>(VV))
- ConstantEvolutionLoopExitValue.erase(PN);
- Worklist.push_back(Inst);
- }
- }
- }
-}
-
/// isSCEVable - Test if values of the given type are analyzable within
/// the SCEV framework. This primarily includes integer types, and it
/// can optionally include pointer types if the ScalarEvolution class
}
SCEVHandle ScalarEvolution::getCouldNotCompute() {
- return UnknownValue;
+ return CouldNotCompute;
}
-// hasSCEV - Return true if the SCEV for this value has already been
+/// hasSCEV - Return true if the SCEV for this value has already been
/// computed.
bool ScalarEvolution::hasSCEV(Value *V) const {
return Scalars.count(V);
SCEVHandle ScalarEvolution::getSCEV(Value *V) {
assert(isSCEVable(V->getType()) && "Value is not SCEVable!");
- std::map<Value*, SCEVHandle>::iterator I = Scalars.find(V);
+ std::map<SCEVCallbackVH, SCEVHandle>::iterator I = Scalars.find(V);
if (I != Scalars.end()) return I->second;
SCEVHandle S = createSCEV(V);
- Scalars.insert(std::make_pair(V, S));
+ Scalars.insert(std::make_pair(SCEVCallbackVH(V, this), S));
return S;
}
/// getNegativeSCEV - Return a SCEV corresponding to -V = -1*V
///
SCEVHandle ScalarEvolution::getNegativeSCEV(const SCEVHandle &V) {
- if (SCEVConstant *VC = dyn_cast<SCEVConstant>(V))
+ if (const SCEVConstant *VC = dyn_cast<SCEVConstant>(V))
return getUnknown(ConstantExpr::getNeg(VC->getValue()));
const Type *Ty = V->getType();
/// getNotSCEV - Return a SCEV corresponding to ~V = -1-V
SCEVHandle ScalarEvolution::getNotSCEV(const SCEVHandle &V) {
- if (SCEVConstant *VC = dyn_cast<SCEVConstant>(V))
+ if (const SCEVConstant *VC = dyn_cast<SCEVConstant>(V))
return getUnknown(ConstantExpr::getNot(VC->getValue()));
const Type *Ty = V->getType();
return getSignExtendExpr(V, Ty);
}
+/// getNoopOrZeroExtend - Return a SCEV corresponding to a conversion of the
+/// input value to the specified type. If the type must be extended, it is zero
+/// extended. The conversion must not be narrowing.
+SCEVHandle
+ScalarEvolution::getNoopOrZeroExtend(const SCEVHandle &V, const Type *Ty) {
+ const Type *SrcTy = V->getType();
+ assert((SrcTy->isInteger() || (TD && isa<PointerType>(SrcTy))) &&
+ (Ty->isInteger() || (TD && isa<PointerType>(Ty))) &&
+ "Cannot noop or zero extend with non-integer arguments!");
+ assert(getTypeSizeInBits(SrcTy) <= getTypeSizeInBits(Ty) &&
+ "getNoopOrZeroExtend cannot truncate!");
+ if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty))
+ return V; // No conversion
+ return getZeroExtendExpr(V, Ty);
+}
+
+/// getNoopOrSignExtend - Return a SCEV corresponding to a conversion of the
+/// input value to the specified type. If the type must be extended, it is sign
+/// extended. The conversion must not be narrowing.
+SCEVHandle
+ScalarEvolution::getNoopOrSignExtend(const SCEVHandle &V, const Type *Ty) {
+ const Type *SrcTy = V->getType();
+ assert((SrcTy->isInteger() || (TD && isa<PointerType>(SrcTy))) &&
+ (Ty->isInteger() || (TD && isa<PointerType>(Ty))) &&
+ "Cannot noop or sign extend with non-integer arguments!");
+ assert(getTypeSizeInBits(SrcTy) <= getTypeSizeInBits(Ty) &&
+ "getNoopOrSignExtend cannot truncate!");
+ if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty))
+ return V; // No conversion
+ return getSignExtendExpr(V, Ty);
+}
+
+/// getNoopOrAnyExtend - Return a SCEV corresponding to a conversion of
+/// the input value to the specified type. If the type must be extended,
+/// it is extended with unspecified bits. The conversion must not be
+/// narrowing.
+SCEVHandle
+ScalarEvolution::getNoopOrAnyExtend(const SCEVHandle &V, const Type *Ty) {
+ const Type *SrcTy = V->getType();
+ assert((SrcTy->isInteger() || (TD && isa<PointerType>(SrcTy))) &&
+ (Ty->isInteger() || (TD && isa<PointerType>(Ty))) &&
+ "Cannot noop or any extend with non-integer arguments!");
+ assert(getTypeSizeInBits(SrcTy) <= getTypeSizeInBits(Ty) &&
+ "getNoopOrAnyExtend cannot truncate!");
+ if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty))
+ return V; // No conversion
+ return getAnyExtendExpr(V, Ty);
+}
+
+/// getTruncateOrNoop - Return a SCEV corresponding to a conversion of the
+/// input value to the specified type. The conversion must not be widening.
+SCEVHandle
+ScalarEvolution::getTruncateOrNoop(const SCEVHandle &V, const Type *Ty) {
+ const Type *SrcTy = V->getType();
+ assert((SrcTy->isInteger() || (TD && isa<PointerType>(SrcTy))) &&
+ (Ty->isInteger() || (TD && isa<PointerType>(Ty))) &&
+ "Cannot truncate or noop with non-integer arguments!");
+ assert(getTypeSizeInBits(SrcTy) >= getTypeSizeInBits(Ty) &&
+ "getTruncateOrNoop cannot extend!");
+ if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty))
+ return V; // No conversion
+ return getTruncateExpr(V, Ty);
+}
+
/// ReplaceSymbolicValueWithConcrete - This looks up the computed SCEV value for
/// the specified instruction and replaces any references to the symbolic value
/// SymName with the specified value. This is used during PHI resolution.
void ScalarEvolution::
ReplaceSymbolicValueWithConcrete(Instruction *I, const SCEVHandle &SymName,
const SCEVHandle &NewVal) {
- std::map<Value*, SCEVHandle>::iterator SI = Scalars.find(I);
+ std::map<SCEVCallbackVH, SCEVHandle>::iterator SI =
+ Scalars.find(SCEVCallbackVH(I, this));
if (SI == Scalars.end()) return;
SCEVHandle NV =
SCEVHandle SymbolicName = getUnknown(PN);
assert(Scalars.find(PN) == Scalars.end() &&
"PHI node already processed?");
- Scalars.insert(std::make_pair(PN, SymbolicName));
+ Scalars.insert(std::make_pair(SCEVCallbackVH(PN, this), SymbolicName));
// Using this symbolic name for the PHI, analyze the value coming around
// the back-edge.
// If the value coming around the backedge is an add with the symbolic
// value we just inserted, then we found a simple induction variable!
- if (SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(BEValue)) {
+ if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(BEValue)) {
// If there is a single occurrence of the symbolic value, replace it
// with a recurrence.
unsigned FoundIndex = Add->getNumOperands();
if (FoundIndex != Add->getNumOperands()) {
// Create an add with everything but the specified operand.
- std::vector<SCEVHandle> Ops;
+ SmallVector<SCEVHandle, 8> Ops;
for (unsigned i = 0, e = Add->getNumOperands(); i != e; ++i)
if (i != FoundIndex)
Ops.push_back(Add->getOperand(i));
return PHISCEV;
}
}
- } else if (SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(BEValue)) {
+ } else if (const SCEVAddRecExpr *AddRec =
+ dyn_cast<SCEVAddRecExpr>(BEValue)) {
// Otherwise, this could be a loop like this:
// i = 0; for (j = 1; ..; ++j) { .... i = j; }
// In this case, j = {1,+,1} and BEValue is j.
return getUnknown(PN);
}
+/// createNodeForGEP - Expand GEP instructions into add and multiply
+/// operations. This allows them to be analyzed by regular SCEV code.
+///
+SCEVHandle ScalarEvolution::createNodeForGEP(User *GEP) {
+
+ const Type *IntPtrTy = TD->getIntPtrType();
+ Value *Base = GEP->getOperand(0);
+ // Don't attempt to analyze GEPs over unsized objects.
+ if (!cast<PointerType>(Base->getType())->getElementType()->isSized())
+ return getUnknown(GEP);
+ SCEVHandle TotalOffset = getIntegerSCEV(0, IntPtrTy);
+ gep_type_iterator GTI = gep_type_begin(GEP);
+ for (GetElementPtrInst::op_iterator I = next(GEP->op_begin()),
+ E = GEP->op_end();
+ I != E; ++I) {
+ Value *Index = *I;
+ // Compute the (potentially symbolic) offset in bytes for this index.
+ if (const StructType *STy = dyn_cast<StructType>(*GTI++)) {
+ // For a struct, add the member offset.
+ const StructLayout &SL = *TD->getStructLayout(STy);
+ unsigned FieldNo = cast<ConstantInt>(Index)->getZExtValue();
+ uint64_t Offset = SL.getElementOffset(FieldNo);
+ TotalOffset = getAddExpr(TotalOffset,
+ getIntegerSCEV(Offset, IntPtrTy));
+ } else {
+ // For an array, add the element offset, explicitly scaled.
+ SCEVHandle LocalOffset = getSCEV(Index);
+ if (!isa<PointerType>(LocalOffset->getType()))
+ // Getelementptr indicies are signed.
+ LocalOffset = getTruncateOrSignExtend(LocalOffset,
+ IntPtrTy);
+ LocalOffset =
+ getMulExpr(LocalOffset,
+ getIntegerSCEV(TD->getTypeAllocSize(*GTI),
+ IntPtrTy));
+ TotalOffset = getAddExpr(TotalOffset, LocalOffset);
+ }
+ }
+ return getAddExpr(getSCEV(Base), TotalOffset);
+}
+
/// GetMinTrailingZeros - Determine the minimum number of zero bits that S is
/// guaranteed to end in (at every loop iteration). It is, at the same time,
/// the minimum number of times S is divisible by 2. For example, given {4,+,8}
/// it returns 2. If S is guaranteed to be 0, it returns the bitwidth of S.
static uint32_t GetMinTrailingZeros(SCEVHandle S, const ScalarEvolution &SE) {
- if (SCEVConstant *C = dyn_cast<SCEVConstant>(S))
+ if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S))
return C->getValue()->getValue().countTrailingZeros();
- if (SCEVTruncateExpr *T = dyn_cast<SCEVTruncateExpr>(S))
+ if (const SCEVTruncateExpr *T = dyn_cast<SCEVTruncateExpr>(S))
return std::min(GetMinTrailingZeros(T->getOperand(), SE),
(uint32_t)SE.getTypeSizeInBits(T->getType()));
- if (SCEVZeroExtendExpr *E = dyn_cast<SCEVZeroExtendExpr>(S)) {
+ 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->getOperand()->getType()) : OpRes;
+ SE.getTypeSizeInBits(E->getType()) : OpRes;
}
- if (SCEVSignExtendExpr *E = dyn_cast<SCEVSignExtendExpr>(S)) {
+ 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->getOperand()->getType()) : OpRes;
+ SE.getTypeSizeInBits(E->getType()) : OpRes;
}
- if (SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) {
+ if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) {
// The result is the min of all operands results.
uint32_t MinOpRes = GetMinTrailingZeros(A->getOperand(0), SE);
for (unsigned i = 1, e = A->getNumOperands(); MinOpRes && i != e; ++i)
return MinOpRes;
}
- if (SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(S)) {
+ if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(S)) {
// The result is the sum of all operands results.
uint32_t SumOpRes = GetMinTrailingZeros(M->getOperand(0), SE);
uint32_t BitWidth = SE.getTypeSizeInBits(M->getType());
return SumOpRes;
}
- if (SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(S)) {
+ if (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(S)) {
// The result is the min of all operands results.
uint32_t MinOpRes = GetMinTrailingZeros(A->getOperand(0), SE);
for (unsigned i = 1, e = A->getNumOperands(); MinOpRes && i != e; ++i)
return MinOpRes;
}
- if (SCEVSMaxExpr *M = dyn_cast<SCEVSMaxExpr>(S)) {
+ if (const SCEVSMaxExpr *M = dyn_cast<SCEVSMaxExpr>(S)) {
// The result is the min of all operands results.
uint32_t MinOpRes = GetMinTrailingZeros(M->getOperand(0), SE);
for (unsigned i = 1, e = M->getNumOperands(); MinOpRes && i != e; ++i)
return MinOpRes;
}
- if (SCEVUMaxExpr *M = dyn_cast<SCEVUMaxExpr>(S)) {
+ if (const SCEVUMaxExpr *M = dyn_cast<SCEVUMaxExpr>(S)) {
// The result is the min of all operands results.
uint32_t MinOpRes = GetMinTrailingZeros(M->getOperand(0), SE);
for (unsigned i = 1, e = M->getNumOperands(); MinOpRes && i != e; ++i)
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))))
+ return getZeroExtendExpr(getNotSCEV(Z->getOperand()),
+ U->getType());
}
break;
return getTruncateOrZeroExtend(getSCEV(U->getOperand(0)),
U->getType());
- case Instruction::GetElementPtr: {
+ case Instruction::GetElementPtr:
if (!TD) break; // Without TD we can't analyze pointers.
- const Type *IntPtrTy = TD->getIntPtrType();
- Value *Base = U->getOperand(0);
- SCEVHandle TotalOffset = getIntegerSCEV(0, IntPtrTy);
- gep_type_iterator GTI = gep_type_begin(U);
- for (GetElementPtrInst::op_iterator I = next(U->op_begin()),
- E = U->op_end();
- I != E; ++I) {
- Value *Index = *I;
- // Compute the (potentially symbolic) offset in bytes for this index.
- if (const StructType *STy = dyn_cast<StructType>(*GTI++)) {
- // For a struct, add the member offset.
- const StructLayout &SL = *TD->getStructLayout(STy);
- unsigned FieldNo = cast<ConstantInt>(Index)->getZExtValue();
- uint64_t Offset = SL.getElementOffset(FieldNo);
- TotalOffset = getAddExpr(TotalOffset,
- getIntegerSCEV(Offset, IntPtrTy));
- } else {
- // For an array, add the element offset, explicitly scaled.
- SCEVHandle LocalOffset = getSCEV(Index);
- if (!isa<PointerType>(LocalOffset->getType()))
- // Getelementptr indicies are signed.
- LocalOffset = getTruncateOrSignExtend(LocalOffset,
- IntPtrTy);
- LocalOffset =
- getMulExpr(LocalOffset,
- getIntegerSCEV(TD->getTypePaddedSize(*GTI),
- IntPtrTy));
- TotalOffset = getAddExpr(TotalOffset, LocalOffset);
- }
- }
- return getAddExpr(getSCEV(Base), TotalOffset);
- }
+ return createNodeForGEP(U);
case Instruction::PHI:
return createNodeForPHI(cast<PHINode>(U));
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!");
// conservative estimates made without the benefit
// of trip count information.
if (ItCount.hasAnyInfo())
- for (BasicBlock::iterator I = L->getHeader()->begin();
- PHINode *PN = dyn_cast<PHINode>(I); ++I)
- deleteValueFromRecords(PN);
+ forgetLoopPHIs(L);
}
return Pair.first->second;
}
/// is deleted.
void ScalarEvolution::forgetLoopBackedgeTakenCount(const Loop *L) {
BackedgeTakenCounts.erase(L);
+ forgetLoopPHIs(L);
+}
+
+/// forgetLoopPHIs - Delete the memoized SCEVs associated with the
+/// PHI nodes in the given loop. This is used when the trip count of
+/// the loop may have changed.
+void ScalarEvolution::forgetLoopPHIs(const Loop *L) {
+ BasicBlock *Header = L->getHeader();
+
+ // Push all Loop-header PHIs onto the Worklist stack, except those
+ // that are presently represented via a SCEVUnknown. SCEVUnknown for
+ // a PHI either means that it has an unrecognized structure, or it's
+ // a PHI that's in the progress of being computed by createNodeForPHI.
+ // In the former case, additional loop trip count information isn't
+ // going to change anything. In the later case, createNodeForPHI will
+ // perform the necessary updates on its own when it gets to that point.
+ SmallVector<Instruction *, 16> Worklist;
+ for (BasicBlock::iterator I = Header->begin();
+ PHINode *PN = dyn_cast<PHINode>(I); ++I) {
+ std::map<SCEVCallbackVH, SCEVHandle>::iterator It = Scalars.find((Value*)I);
+ if (It != Scalars.end() && !isa<SCEVUnknown>(It->second))
+ Worklist.push_back(PN);
+ }
+
+ while (!Worklist.empty()) {
+ Instruction *I = Worklist.pop_back_val();
+ if (Scalars.erase(I))
+ for (Value::use_iterator UI = I->use_begin(), UE = I->use_end();
+ UI != UE; ++UI)
+ Worklist.push_back(cast<Instruction>(UI));
+ }
}
/// ComputeBackedgeTakenCount - Compute the number of times the backedge
ScalarEvolution::BackedgeTakenInfo
ScalarEvolution::ComputeBackedgeTakenCount(const Loop *L) {
// If the loop has a non-one exit block count, we can't analyze it.
- SmallVector<BasicBlock*, 8> ExitBlocks;
- L->getExitBlocks(ExitBlocks);
- if (ExitBlocks.size() != 1) return UnknownValue;
+ BasicBlock *ExitBlock = L->getExitBlock();
+ if (!ExitBlock)
+ return CouldNotCompute;
// Okay, there is one exit block. Try to find the condition that causes the
// loop to be exited.
- BasicBlock *ExitBlock = ExitBlocks[0];
-
- BasicBlock *ExitingBlock = 0;
- for (pred_iterator PI = pred_begin(ExitBlock), E = pred_end(ExitBlock);
- PI != E; ++PI)
- if (L->contains(*PI)) {
- if (ExitingBlock == 0)
- ExitingBlock = *PI;
- else
- return UnknownValue; // More than one block exiting!
- }
- assert(ExitingBlock && "No exits from loop, something is broken!");
+ BasicBlock *ExitingBlock = L->getExitingBlock();
+ if (!ExitingBlock)
+ return CouldNotCompute; // More than one block exiting!
// Okay, we've computed the exiting block. See what condition causes us to
// exit.
//
// FIXME: we should be able to handle switch instructions (with a single exit)
BranchInst *ExitBr = dyn_cast<BranchInst>(ExitingBlock->getTerminator());
- if (ExitBr == 0) return UnknownValue;
+ if (ExitBr == 0) return CouldNotCompute;
assert(ExitBr->isConditional() && "If unconditional, it can't be in loop!");
// At this point, we know we have a conditional branch that determines whether
if (ExitBr->getSuccessor(0) != L->getHeader() &&
ExitBr->getSuccessor(1) != L->getHeader() &&
ExitBr->getParent() != L->getHeader())
- return UnknownValue;
+ return CouldNotCompute;
ICmpInst *ExitCond = dyn_cast<ICmpInst>(ExitBr->getCondition());
- // If it's not an integer comparison then compute it the hard way.
- // Note that ICmpInst deals with pointer comparisons too so we must check
- // the type of the operand.
- if (ExitCond == 0 || isa<PointerType>(ExitCond->getOperand(0)->getType()))
+ // 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);
SCEVHandle RHS = getSCEV(ExitCond->getOperand(1));
// Try to evaluate any dependencies out of the loop.
- SCEVHandle Tmp = getSCEVAtScope(LHS, L);
- if (!isa<SCEVCouldNotCompute>(Tmp)) LHS = Tmp;
- Tmp = getSCEVAtScope(RHS, L);
- if (!isa<SCEVCouldNotCompute>(Tmp)) RHS = Tmp;
+ LHS = getSCEVAtScope(LHS, L);
+ RHS = getSCEVAtScope(RHS, L);
// At this point, we would like to compute how many iterations of the
// loop the predicate will return true for these inputs.
// If we have a comparison of a chrec against a constant, try to use value
// ranges to answer this query.
- if (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS))
- if (SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS))
+ if (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS))
+ if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS))
if (AddRec->getLoop() == L) {
- // Form the comparison range using the constant of the correct type so
- // that the ConstantRange class knows to do a signed or unsigned
- // comparison.
- ConstantInt *CompVal = RHSC->getValue();
- const Type *RealTy = ExitCond->getOperand(0)->getType();
- CompVal = dyn_cast<ConstantInt>(
- ConstantExpr::getBitCast(CompVal, RealTy));
- if (CompVal) {
- // Form the constant range.
- ConstantRange CompRange(
- ICmpInst::makeConstantRange(Cond, CompVal->getValue()));
-
- SCEVHandle Ret = AddRec->getNumIterationsInRange(CompRange, *this);
- if (!isa<SCEVCouldNotCompute>(Ret)) return Ret;
- }
+ // Form the constant range.
+ ConstantRange CompRange(
+ ICmpInst::makeConstantRange(Cond, RHSC->getValue()->getValue()));
+
+ SCEVHandle Ret = AddRec->getNumIterationsInRange(CompRange, *this);
+ if (!isa<SCEVCouldNotCompute>(Ret)) return Ret;
}
switch (Cond) {
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;
+ Idx = getSCEVAtScope(Idx, L);
// We can only recognize very limited forms of loop index expressions, in
// particular, only affine AddRec's like {C1,+,C2}.
- SCEVAddRecExpr *IdxExpr = dyn_cast<SCEVAddRecExpr>(Idx);
+ const SCEVAddRecExpr *IdxExpr = dyn_cast<SCEVAddRecExpr>(Idx);
if (!IdxExpr || !IdxExpr->isAffine() || IdxExpr->isLoopInvariant(L) ||
!isa<SCEVConstant>(IdxExpr->getOperand(0)) ||
!isa<SCEVConstant>(IdxExpr->getOperand(1)))
- return UnknownValue;
+ return CouldNotCompute;
unsigned MaxSteps = MaxBruteForceIterations;
for (unsigned IterationNum = 0; IterationNum != MaxSteps; ++IterationNum) {
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.
+/// evaluate the trip count of the loop, return CouldNotCompute.
SCEVHandle ScalarEvolution::
ComputeBackedgeTakenCountExhaustively(const Loop *L, Value *Cond, bool ExitWhen) {
PHINode *PN = getConstantEvolvingPHI(Cond, L);
- if (PN == 0) return UnknownValue;
+ if (PN == 0) return CouldNotCompute;
// Since the loop is canonicalized, the PHI node must have two entries. One
// entry must be a constant (coming in from outside of the loop), and the
bool SecondIsBackedge = L->contains(PN->getIncomingBlock(1));
Constant *StartCST =
dyn_cast<Constant>(PN->getIncomingValue(!SecondIsBackedge));
- if (StartCST == 0) return UnknownValue; // Must be a constant.
+ if (StartCST == 0) return CouldNotCompute; // Must be a constant.
Value *BEValue = PN->getIncomingValue(SecondIsBackedge);
PHINode *PN2 = getConstantEvolvingPHI(BEValue, L);
- if (PN2 != PN) return UnknownValue; // Not derived from same PHI.
+ if (PN2 != PN) return CouldNotCompute; // Not derived from same PHI.
// Okay, we find a PHI node that defines the trip count of this loop. Execute
// the loop symbolically to determine when the condition gets a value of
dyn_cast_or_null<ConstantInt>(EvaluateExpression(Cond, PHIVal));
// Couldn't symbolically evaluate.
- if (!CondVal) return UnknownValue;
+ if (!CondVal) return CouldNotCompute;
if (CondVal->getValue() == uint64_t(ExitWhen)) {
ConstantEvolutionLoopExitValue[PN] = PHIVal;
// Compute the value of the PHI node for the next iteration.
Constant *NextPHI = EvaluateExpression(BEValue, PHIVal);
if (NextPHI == 0 || NextPHI == PHIVal)
- return UnknownValue; // Couldn't evaluate or not making progress...
+ return CouldNotCompute; // Couldn't evaluate or not making progress...
PHIVal = NextPHI;
}
// Too many iterations were needed to evaluate.
- return UnknownValue;
+ return CouldNotCompute;
}
-/// getSCEVAtScope - Compute the value of the specified expression within the
-/// indicated loop (which may be null to indicate in no loop). If the
-/// expression cannot be evaluated, return UnknownValue.
-SCEVHandle ScalarEvolution::getSCEVAtScope(SCEV *V, const Loop *L) {
+/// getSCEVAtScope - Return a SCEV expression handle for the specified value
+/// at the specified scope in the program. The L value specifies a loop
+/// nest to evaluate the expression at, where null is the top-level or a
+/// specified loop is immediately inside of the loop.
+///
+/// This method can be used to compute the exit value for a variable defined
+/// in a loop by querying what the value will hold in the parent loop.
+///
+/// In the case that a relevant loop exit value cannot be computed, the
+/// original value V is returned.
+SCEVHandle ScalarEvolution::getSCEVAtScope(const SCEV *V, const Loop *L) {
// FIXME: this should be turned into a virtual method on SCEV!
if (isa<SCEVConstant>(V)) return V;
// If this instruction is evolved from a constant-evolving PHI, compute the
// exit value from the loop without using SCEVs.
- if (SCEVUnknown *SU = dyn_cast<SCEVUnknown>(V)) {
+ if (const SCEVUnknown *SU = dyn_cast<SCEVUnknown>(V)) {
if (Instruction *I = dyn_cast<Instruction>(SU->getValue())) {
const Loop *LI = (*this->LI)[I->getParent()];
if (LI && LI->getParentLoop() == L) // Looking for loop exit value.
// count. If so, we may be able to force computation of the exit
// value.
SCEVHandle BackedgeTakenCount = getBackedgeTakenCount(LI);
- if (SCEVConstant *BTCC =
+ if (const SCEVConstant *BTCC =
dyn_cast<SCEVConstant>(BackedgeTakenCount)) {
// Okay, we know how many times the containing loop executes. If
// this is a constant evolving PHI node, get the final value at
// the arguments into constants, and if so, try to constant propagate the
// result. This is particularly useful for computing loop exit values.
if (CanConstantFold(I)) {
+ // Check to see if we've folded this instruction at this loop before.
+ std::map<const Loop *, Constant *> &Values = ValuesAtScopes[I];
+ std::pair<std::map<const Loop *, Constant *>::iterator, bool> Pair =
+ Values.insert(std::make_pair(L, static_cast<Constant *>(0)));
+ if (!Pair.second)
+ return Pair.first->second ? &*getUnknown(Pair.first->second) : V;
+
std::vector<Constant*> Operands;
Operands.reserve(I->getNumOperands());
for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
return V;
SCEVHandle OpV = getSCEVAtScope(getSCEV(Op), L);
- if (SCEVConstant *SC = dyn_cast<SCEVConstant>(OpV)) {
+ if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(OpV)) {
Constant *C = SC->getValue();
if (C->getType() != Op->getType())
C = ConstantExpr::getCast(CastInst::getCastOpcode(C, false,
false),
C, Op->getType());
Operands.push_back(C);
- } else if (SCEVUnknown *SU = dyn_cast<SCEVUnknown>(OpV)) {
+ } else if (const SCEVUnknown *SU = dyn_cast<SCEVUnknown>(OpV)) {
if (Constant *C = dyn_cast<Constant>(SU->getValue())) {
if (C->getType() != Op->getType())
C =
else
C = ConstantFoldInstOperands(I->getOpcode(), I->getType(),
&Operands[0], Operands.size());
+ Pair.first->second = C;
return getUnknown(C);
}
}
return V;
}
- if (SCEVCommutativeExpr *Comm = dyn_cast<SCEVCommutativeExpr>(V)) {
+ if (const SCEVCommutativeExpr *Comm = dyn_cast<SCEVCommutativeExpr>(V)) {
// Avoid performing the look-up in the common case where the specified
// expression has no loop-variant portions.
for (unsigned i = 0, e = Comm->getNumOperands(); i != e; ++i) {
SCEVHandle OpAtScope = getSCEVAtScope(Comm->getOperand(i), L);
if (OpAtScope != Comm->getOperand(i)) {
- if (OpAtScope == UnknownValue) return UnknownValue;
// Okay, at least one of these operands is loop variant but might be
// foldable. Build a new instance of the folded commutative expression.
- std::vector<SCEVHandle> NewOps(Comm->op_begin(), Comm->op_begin()+i);
+ SmallVector<SCEVHandle, 8> NewOps(Comm->op_begin(), Comm->op_begin()+i);
NewOps.push_back(OpAtScope);
for (++i; i != e; ++i) {
OpAtScope = getSCEVAtScope(Comm->getOperand(i), L);
- if (OpAtScope == UnknownValue) return UnknownValue;
NewOps.push_back(OpAtScope);
}
if (isa<SCEVAddExpr>(Comm))
return Comm;
}
- if (SCEVUDivExpr *Div = dyn_cast<SCEVUDivExpr>(V)) {
+ if (const SCEVUDivExpr *Div = dyn_cast<SCEVUDivExpr>(V)) {
SCEVHandle LHS = getSCEVAtScope(Div->getLHS(), L);
- if (LHS == UnknownValue) return LHS;
SCEVHandle RHS = getSCEVAtScope(Div->getRHS(), L);
- if (RHS == UnknownValue) return RHS;
if (LHS == Div->getLHS() && RHS == Div->getRHS())
return Div; // must be loop invariant
return getUDivExpr(LHS, RHS);
// If this is a loop recurrence for a loop that does not contain L, then we
// are dealing with the final value computed by the loop.
- if (SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V)) {
+ if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V)) {
if (!L || !AddRec->getLoop()->contains(L->getHeader())) {
// To evaluate this recurrence, we need to know how many times the AddRec
// loop iterates. Compute this now.
SCEVHandle BackedgeTakenCount = getBackedgeTakenCount(AddRec->getLoop());
- if (BackedgeTakenCount == UnknownValue) return UnknownValue;
+ if (BackedgeTakenCount == CouldNotCompute) return AddRec;
// Then, evaluate the AddRec.
return AddRec->evaluateAtIteration(BackedgeTakenCount, *this);
}
- return UnknownValue;
+ return AddRec;
}
- if (SCEVZeroExtendExpr *Cast = dyn_cast<SCEVZeroExtendExpr>(V)) {
+ if (const SCEVZeroExtendExpr *Cast = dyn_cast<SCEVZeroExtendExpr>(V)) {
SCEVHandle Op = getSCEVAtScope(Cast->getOperand(), L);
- if (Op == UnknownValue) return Op;
if (Op == Cast->getOperand())
return Cast; // must be loop invariant
return getZeroExtendExpr(Op, Cast->getType());
}
- if (SCEVSignExtendExpr *Cast = dyn_cast<SCEVSignExtendExpr>(V)) {
+ if (const SCEVSignExtendExpr *Cast = dyn_cast<SCEVSignExtendExpr>(V)) {
SCEVHandle Op = getSCEVAtScope(Cast->getOperand(), L);
- if (Op == UnknownValue) return Op;
if (Op == Cast->getOperand())
return Cast; // must be loop invariant
return getSignExtendExpr(Op, Cast->getType());
}
- if (SCEVTruncateExpr *Cast = dyn_cast<SCEVTruncateExpr>(V)) {
+ if (const SCEVTruncateExpr *Cast = dyn_cast<SCEVTruncateExpr>(V)) {
SCEVHandle Op = getSCEVAtScope(Cast->getOperand(), L);
- if (Op == UnknownValue) return Op;
if (Op == Cast->getOperand())
return Cast; // must be loop invariant
return getTruncateExpr(Op, Cast->getType());
}
assert(0 && "Unknown SCEV type!");
+ return 0;
}
-/// getSCEVAtScope - Return a SCEV expression handle for the specified value
-/// at the specified scope in the program. The L value specifies a loop
-/// nest to evaluate the expression at, where null is the top-level or a
-/// specified loop is immediately inside of the loop.
-///
-/// This method can be used to compute the exit value for a variable defined
-/// in a loop by querying what the value will hold in the parent loop.
-///
-/// If this value is not computable at this scope, a SCEVCouldNotCompute
-/// object is returned.
+/// getSCEVAtScope - This is a convenience function which does
+/// getSCEVAtScope(getSCEV(V), L).
SCEVHandle ScalarEvolution::getSCEVAtScope(Value *V, const Loop *L) {
return getSCEVAtScope(getSCEV(V), L);
}
static std::pair<SCEVHandle,SCEVHandle>
SolveQuadraticEquation(const SCEVAddRecExpr *AddRec, ScalarEvolution &SE) {
assert(AddRec->getNumOperands() == 3 && "This is not a quadratic chrec!");
- SCEVConstant *LC = dyn_cast<SCEVConstant>(AddRec->getOperand(0));
- SCEVConstant *MC = dyn_cast<SCEVConstant>(AddRec->getOperand(1));
- SCEVConstant *NC = dyn_cast<SCEVConstant>(AddRec->getOperand(2));
+ const SCEVConstant *LC = dyn_cast<SCEVConstant>(AddRec->getOperand(0));
+ const SCEVConstant *MC = dyn_cast<SCEVConstant>(AddRec->getOperand(1));
+ const SCEVConstant *NC = dyn_cast<SCEVConstant>(AddRec->getOperand(2));
// We currently can only solve this if the coefficients are constants.
if (!LC || !MC || !NC) {
- SCEV *CNC = SE.getCouldNotCompute();
+ const SCEV *CNC = SE.getCouldNotCompute();
return std::make_pair(CNC, CNC);
}
APInt NegB(-B);
APInt TwoA( A << 1 );
if (TwoA.isMinValue()) {
- SCEV *CNC = SE.getCouldNotCompute();
+ const SCEV *CNC = SE.getCouldNotCompute();
return std::make_pair(CNC, CNC);
}
}
/// HowFarToZero - Return the number of times a backedge comparing the specified
-/// value to zero will execute. If not computable, return UnknownValue
-SCEVHandle ScalarEvolution::HowFarToZero(SCEV *V, const Loop *L) {
+/// value to zero will execute. If not computable, return CouldNotCompute.
+SCEVHandle ScalarEvolution::HowFarToZero(const SCEV *V, const Loop *L) {
// If the value is a constant
- if (SCEVConstant *C = dyn_cast<SCEVConstant>(V)) {
+ if (const SCEVConstant *C = dyn_cast<SCEVConstant>(V)) {
// If the value is already zero, the branch will execute zero times.
if (C->getValue()->isZero()) return C;
- return UnknownValue; // Otherwise it will loop infinitely.
+ return CouldNotCompute; // Otherwise it will loop infinitely.
}
- SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V);
+ const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V);
if (!AddRec || AddRec->getLoop() != L)
- return UnknownValue;
+ return CouldNotCompute;
if (AddRec->isAffine()) {
// If this is an affine expression, the execution count of this branch is
// Get the initial value for the loop.
SCEVHandle Start = getSCEVAtScope(AddRec->getStart(), L->getParentLoop());
- if (isa<SCEVCouldNotCompute>(Start)) return UnknownValue;
-
SCEVHandle Step = getSCEVAtScope(AddRec->getOperand(1), L->getParentLoop());
- if (SCEVConstant *StepC = dyn_cast<SCEVConstant>(Step)) {
+ if (const SCEVConstant *StepC = dyn_cast<SCEVConstant>(Step)) {
// For now we handle only constant steps.
// First, handle unitary steps.
return Start; // N = Start (as unsigned)
// Then, try to solve the above equation provided that Start is constant.
- if (SCEVConstant *StartC = dyn_cast<SCEVConstant>(Start))
+ if (const SCEVConstant *StartC = dyn_cast<SCEVConstant>(Start))
return SolveLinEquationWithOverflow(StepC->getValue()->getValue(),
-StartC->getValue()->getValue(),
*this);
// the quadratic equation to solve it.
std::pair<SCEVHandle,SCEVHandle> Roots = SolveQuadraticEquation(AddRec,
*this);
- SCEVConstant *R1 = dyn_cast<SCEVConstant>(Roots.first);
- SCEVConstant *R2 = dyn_cast<SCEVConstant>(Roots.second);
+ const SCEVConstant *R1 = dyn_cast<SCEVConstant>(Roots.first);
+ const SCEVConstant *R2 = dyn_cast<SCEVConstant>(Roots.second);
if (R1) {
#if 0
errs() << "HFTZ: " << *V << " - sol#1: " << *R1
}
}
- 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(SCEV *V, const Loop *L) {
+/// CouldNotCompute
+SCEVHandle ScalarEvolution::HowFarToNonZero(const SCEV *V, const Loop *L) {
// Loops that look like: while (X == 0) are very strange indeed. We don't
// handle them yet except for the trivial case. This could be expanded in the
// future as needed.
// If the value is a constant, check to see if it is known to be non-zero
// already. If so, the backedge will execute zero times.
- if (SCEVConstant *C = dyn_cast<SCEVConstant>(V)) {
+ if (const SCEVConstant *C = dyn_cast<SCEVConstant>(V)) {
if (!C->getValue()->isNullValue())
return 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
+/// predecessor outside the loop, return it. Otherwise return null.
+///
+BasicBlock *ScalarEvolution::getLoopPredecessor(const Loop *L) {
+ BasicBlock *Header = L->getHeader();
+ BasicBlock *Pred = 0;
+ for (pred_iterator PI = pred_begin(Header), E = pred_end(Header);
+ PI != E; ++PI)
+ if (!L->contains(*PI)) {
+ if (Pred && Pred != *PI) return 0; // Multiple predecessors.
+ Pred = *PI;
+ }
+ return Pred;
}
/// getPredecessorWithUniqueSuccessorForBB - Return a predecessor of BB
return Pred;
// A loop's header is defined to be a block that dominates the loop.
- // If the loop has a preheader, it must be a block that has exactly
- // one successor that can reach BB. This is slightly more strict
- // than necessary, but works if critical edges are split.
+ // If the header has a unique predecessor outside the loop, it must be
+ // a block that has exactly one successor that can reach the loop.
if (Loop *L = LI->getLoopFor(BB))
- return L->getLoopPreheader();
+ return getLoopPredecessor(L);
return 0;
}
/// expressions in loop trip counts.
bool ScalarEvolution::isLoopGuardedByCond(const Loop *L,
ICmpInst::Predicate Pred,
- SCEV *LHS, SCEV *RHS) {
- BasicBlock *Preheader = L->getLoopPreheader();
- BasicBlock *PreheaderDest = L->getHeader();
+ 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;
- // Starting at the preheader, climb up the predecessor chain, as long as
- // there are predecessors that can be found that have unique successors
+ BasicBlock *Predecessor = getLoopPredecessor(L);
+ BasicBlock *PredecessorDest = L->getHeader();
+
+ // Starting at the loop predecessor, climb up the predecessor chain, as long
+ // as there are predecessors that can be found that have unique successors
// leading to the original header.
- for (; Preheader;
- PreheaderDest = Preheader,
- Preheader = getPredecessorWithUniqueSuccessorForBB(Preheader)) {
+ for (; Predecessor;
+ PredecessorDest = Predecessor,
+ Predecessor = getPredecessorWithUniqueSuccessorForBB(Predecessor)) {
BranchInst *LoopEntryPredicate =
- dyn_cast<BranchInst>(Preheader->getTerminator());
+ dyn_cast<BranchInst>(Predecessor->getTerminator());
if (!LoopEntryPredicate ||
LoopEntryPredicate->isUnconditional())
continue;
Value *PreCondLHS = ICI->getOperand(0);
Value *PreCondRHS = ICI->getOperand(1);
ICmpInst::Predicate Cond;
- if (LoopEntryPredicate->getSuccessor(0) == PreheaderDest)
+ if (LoopEntryPredicate->getSuccessor(0) == PredecessorDest)
Cond = ICI->getPredicate();
else
Cond = ICI->getInversePredicate();
/// 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(SCEV *LHS, SCEV *RHS, const Loop *L, bool isSigned) {
+HowManyLessThans(const SCEV *LHS, const SCEV *RHS,
+ const Loop *L, bool isSigned) {
// Only handle: "ADDREC < LoopInvariant".
- if (!RHS->isLoopInvariant(L)) return UnknownValue;
+ if (!RHS->isLoopInvariant(L)) return CouldNotCompute;
- SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS);
+ const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS);
if (!AddRec || AddRec->getLoop() != L)
- return UnknownValue;
+ return CouldNotCompute;
if (AddRec->isAffine()) {
// FORNOW: We only support unit strides.
// TODO: handle non-constant strides.
const SCEVConstant *CStep = dyn_cast<SCEVConstant>(Step);
if (!CStep || CStep->isZero())
- return UnknownValue;
- if (CStep->getValue()->getValue() == 1) {
+ return CouldNotCompute;
+ if (CStep->isOne()) {
// With unit stride, the iteration never steps past the limit value.
} else if (CStep->getValue()->getValue().isStrictlyPositive()) {
if (const SCEVConstant *CLimit = dyn_cast<SCEVConstant>(RHS)) {
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.
// 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.
+ // only know that it will execute (max(m,n)-n)/s times. In both cases,
+ // the division must round up.
SCEVHandle End = RHS;
if (!isLoopGuardedByCond(L,
isSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
return BackedgeTakenInfo(BECount, MaxBECount);
}
- return UnknownValue;
+ return CouldNotCompute;
}
/// getNumIterationsInRange - Return the number of iterations of this loop that
return SE.getCouldNotCompute();
// If the start is a non-zero constant, shift the range to simplify things.
- if (SCEVConstant *SC = dyn_cast<SCEVConstant>(getStart()))
+ if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(getStart()))
if (!SC->getValue()->isZero()) {
- std::vector<SCEVHandle> Operands(op_begin(), op_end());
+ SmallVector<SCEVHandle, 4> Operands(op_begin(), op_end());
Operands[0] = SE.getIntegerSCEV(0, SC->getType());
SCEVHandle Shifted = SE.getAddRecExpr(Operands, getLoop());
- if (SCEVAddRecExpr *ShiftedAddRec = dyn_cast<SCEVAddRecExpr>(Shifted))
+ if (const SCEVAddRecExpr *ShiftedAddRec =
+ dyn_cast<SCEVAddRecExpr>(Shifted))
return ShiftedAddRec->getNumIterationsInRange(
Range.subtract(SC->getValue()->getValue()), SE);
// This is strange and shouldn't happen.
// quadratic equation to solve it. To do this, we must frame our problem in
// terms of figuring out when zero is crossed, instead of when
// Range.getUpper() is crossed.
- std::vector<SCEVHandle> NewOps(op_begin(), op_end());
+ SmallVector<SCEVHandle, 4> NewOps(op_begin(), op_end());
NewOps[0] = SE.getNegativeSCEV(SE.getConstant(Range.getUpper()));
SCEVHandle NewAddRec = SE.getAddRecExpr(NewOps, getLoop());
// Next, solve the constructed addrec
std::pair<SCEVHandle,SCEVHandle> Roots =
SolveQuadraticEquation(cast<SCEVAddRecExpr>(NewAddRec), SE);
- SCEVConstant *R1 = dyn_cast<SCEVConstant>(Roots.first);
- SCEVConstant *R2 = dyn_cast<SCEVConstant>(Roots.second);
+ const SCEVConstant *R1 = dyn_cast<SCEVConstant>(Roots.first);
+ const SCEVConstant *R2 = dyn_cast<SCEVConstant>(Roots.second);
if (R1) {
// Pick the smallest positive root value.
if (ConstantInt *CB =
+//===----------------------------------------------------------------------===//
+// SCEVCallbackVH Class Implementation
+//===----------------------------------------------------------------------===//
+
+void ScalarEvolution::SCEVCallbackVH::deleted() {
+ assert(SE && "SCEVCallbackVH called with a non-null ScalarEvolution!");
+ if (PHINode *PN = dyn_cast<PHINode>(getValPtr()))
+ SE->ConstantEvolutionLoopExitValue.erase(PN);
+ if (Instruction *I = dyn_cast<Instruction>(getValPtr()))
+ SE->ValuesAtScopes.erase(I);
+ SE->Scalars.erase(getValPtr());
+ // this now dangles!
+}
+
+void ScalarEvolution::SCEVCallbackVH::allUsesReplacedWith(Value *) {
+ assert(SE && "SCEVCallbackVH called with a non-null ScalarEvolution!");
+
+ // Forget all the expressions associated with users of the old value,
+ // so that future queries will recompute the expressions using the new
+ // value.
+ SmallVector<User *, 16> Worklist;
+ Value *Old = getValPtr();
+ bool DeleteOld = false;
+ for (Value::use_iterator UI = Old->use_begin(), UE = Old->use_end();
+ UI != UE; ++UI)
+ Worklist.push_back(*UI);
+ while (!Worklist.empty()) {
+ User *U = Worklist.pop_back_val();
+ // Deleting the Old value will cause this to dangle. Postpone
+ // that until everything else is done.
+ if (U == Old) {
+ DeleteOld = true;
+ continue;
+ }
+ if (PHINode *PN = dyn_cast<PHINode>(U))
+ SE->ConstantEvolutionLoopExitValue.erase(PN);
+ if (Instruction *I = dyn_cast<Instruction>(U))
+ SE->ValuesAtScopes.erase(I);
+ if (SE->Scalars.erase(U))
+ for (Value::use_iterator UI = U->use_begin(), UE = U->use_end();
+ UI != UE; ++UI)
+ Worklist.push_back(*UI);
+ }
+ if (DeleteOld) {
+ if (PHINode *PN = dyn_cast<PHINode>(Old))
+ SE->ConstantEvolutionLoopExitValue.erase(PN);
+ if (Instruction *I = dyn_cast<Instruction>(Old))
+ SE->ValuesAtScopes.erase(I);
+ SE->Scalars.erase(Old);
+ // this now dangles!
+ }
+ // this may dangle!
+}
+
+ScalarEvolution::SCEVCallbackVH::SCEVCallbackVH(Value *V, ScalarEvolution *se)
+ : CallbackVH(V), SE(se) {}
+
//===----------------------------------------------------------------------===//
// ScalarEvolution Class Implementation
//===----------------------------------------------------------------------===//
ScalarEvolution::ScalarEvolution()
- : FunctionPass(&ID), UnknownValue(new SCEVCouldNotCompute()) {
+ : FunctionPass(&ID), CouldNotCompute(new SCEVCouldNotCompute()) {
}
bool ScalarEvolution::runOnFunction(Function &F) {
Scalars.clear();
BackedgeTakenCounts.clear();
ConstantEvolutionLoopExitValue.clear();
+ ValuesAtScopes.clear();
}
void ScalarEvolution::getAnalysisUsage(AnalysisUsage &AU) const {
if (const Loop *L = LI->getLoopFor((*I).getParent())) {
OS << "Exits: ";
SCEVHandle ExitValue = SE.getSCEVAtScope(&*I, L->getParentLoop());
- if (isa<SCEVCouldNotCompute>(ExitValue)) {
+ if (!ExitValue->isLoopInvariant(L)) {
OS << "<<Unknown>>";
} else {
OS << *ExitValue;
}
}
-
OS << "\n";
}
projects / oota-llvm.git / blobdiff