ScalarEvolution.cpp [plain text]
#define DEBUG_TYPE "scalar-evolution"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Constants.h"
#include "llvm/DerivedTypes.h"
#include "llvm/GlobalVariable.h"
#include "llvm/Instructions.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Assembly/Writer.h"
#include "llvm/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/GetElementPtrTypeIterator.h"
#include "llvm/Support/InstIterator.h"
#include "llvm/Support/ManagedStatic.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
#include <ostream>
#include <algorithm>
#include <cmath>
using namespace llvm;
STATISTIC(NumArrayLenItCounts,
"Number of trip counts computed with array length");
STATISTIC(NumTripCountsComputed,
"Number of loops with predictable loop counts");
STATISTIC(NumTripCountsNotComputed,
"Number of loops without predictable loop counts");
STATISTIC(NumBruteForceTripCountsComputed,
"Number of loops with trip counts computed by force");
static cl::opt<unsigned>
MaxBruteForceIterations("scalar-evolution-max-iterations", cl::ReallyHidden,
cl::desc("Maximum number of iterations SCEV will "
"symbolically execute a constant derived loop"),
cl::init(100));
static RegisterPass<ScalarEvolution>
R("scalar-evolution", "Scalar Evolution Analysis", false, true);
char ScalarEvolution::ID = 0;
SCEV::~SCEV() {}
void SCEV::dump() const {
print(errs());
errs() << '\n';
}
void SCEV::print(std::ostream &o) const {
raw_os_ostream OS(o);
print(OS);
}
bool SCEV::isZero() const {
if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(this))
return SC->getValue()->isZero();
return false;
}
SCEVCouldNotCompute::SCEVCouldNotCompute() : SCEV(scCouldNotCompute) {}
SCEVCouldNotCompute::~SCEVCouldNotCompute() {}
bool SCEVCouldNotCompute::isLoopInvariant(const Loop *L) const {
assert(0 && "Attempt to use a SCEVCouldNotCompute object!");
return false;
}
const Type *SCEVCouldNotCompute::getType() const {
assert(0 && "Attempt to use a SCEVCouldNotCompute object!");
return 0;
}
bool SCEVCouldNotCompute::hasComputableLoopEvolution(const Loop *L) const {
assert(0 && "Attempt to use a SCEVCouldNotCompute object!");
return false;
}
SCEVHandle SCEVCouldNotCompute::
replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
const SCEVHandle &Conc,
ScalarEvolution &SE) const {
return this;
}
void SCEVCouldNotCompute::print(raw_ostream &OS) const {
OS << "***COULDNOTCOMPUTE***";
}
bool SCEVCouldNotCompute::classof(const SCEV *S) {
return S->getSCEVType() == scCouldNotCompute;
}
static ManagedStatic<std::map<ConstantInt*, SCEVConstant*> > SCEVConstants;
SCEVConstant::~SCEVConstant() {
SCEVConstants->erase(V);
}
SCEVHandle ScalarEvolution::getConstant(ConstantInt *V) {
SCEVConstant *&R = (*SCEVConstants)[V];
if (R == 0) R = new SCEVConstant(V);
return R;
}
SCEVHandle ScalarEvolution::getConstant(const APInt& Val) {
return getConstant(ConstantInt::get(Val));
}
const Type *SCEVConstant::getType() const { return V->getType(); }
void SCEVConstant::print(raw_ostream &OS) const {
WriteAsOperand(OS, V, false);
}
SCEVCastExpr::SCEVCastExpr(unsigned SCEVTy,
const SCEVHandle &op, const Type *ty)
: SCEV(SCEVTy), Op(op), Ty(ty) {}
SCEVCastExpr::~SCEVCastExpr() {}
bool SCEVCastExpr::dominates(BasicBlock *BB, DominatorTree *DT) const {
return Op->dominates(BB, DT);
}
static ManagedStatic<std::map<std::pair<SCEV*, const Type*>,
SCEVTruncateExpr*> > SCEVTruncates;
SCEVTruncateExpr::SCEVTruncateExpr(const SCEVHandle &op, const Type *ty)
: SCEVCastExpr(scTruncate, op, ty) {
assert((Op->getType()->isInteger() || isa<PointerType>(Op->getType())) &&
(Ty->isInteger() || isa<PointerType>(Ty)) &&
"Cannot truncate non-integer value!");
}
SCEVTruncateExpr::~SCEVTruncateExpr() {
SCEVTruncates->erase(std::make_pair(Op, Ty));
}
void SCEVTruncateExpr::print(raw_ostream &OS) const {
OS << "(truncate " << *Op << " to " << *Ty << ")";
}
static ManagedStatic<std::map<std::pair<SCEV*, const Type*>,
SCEVZeroExtendExpr*> > SCEVZeroExtends;
SCEVZeroExtendExpr::SCEVZeroExtendExpr(const SCEVHandle &op, const Type *ty)
: SCEVCastExpr(scZeroExtend, op, ty) {
assert((Op->getType()->isInteger() || isa<PointerType>(Op->getType())) &&
(Ty->isInteger() || isa<PointerType>(Ty)) &&
"Cannot zero extend non-integer value!");
}
SCEVZeroExtendExpr::~SCEVZeroExtendExpr() {
SCEVZeroExtends->erase(std::make_pair(Op, Ty));
}
void SCEVZeroExtendExpr::print(raw_ostream &OS) const {
OS << "(zeroextend " << *Op << " to " << *Ty << ")";
}
static ManagedStatic<std::map<std::pair<SCEV*, const Type*>,
SCEVSignExtendExpr*> > SCEVSignExtends;
SCEVSignExtendExpr::SCEVSignExtendExpr(const SCEVHandle &op, const Type *ty)
: SCEVCastExpr(scSignExtend, op, ty) {
assert((Op->getType()->isInteger() || isa<PointerType>(Op->getType())) &&
(Ty->isInteger() || isa<PointerType>(Ty)) &&
"Cannot sign extend non-integer value!");
}
SCEVSignExtendExpr::~SCEVSignExtendExpr() {
SCEVSignExtends->erase(std::make_pair(Op, Ty));
}
void SCEVSignExtendExpr::print(raw_ostream &OS) const {
OS << "(signextend " << *Op << " to " << *Ty << ")";
}
static ManagedStatic<std::map<std::pair<unsigned, std::vector<SCEV*> >,
SCEVCommutativeExpr*> > SCEVCommExprs;
SCEVCommutativeExpr::~SCEVCommutativeExpr() {
SCEVCommExprs->erase(std::make_pair(getSCEVType(),
std::vector<SCEV*>(Operands.begin(),
Operands.end())));
}
void SCEVCommutativeExpr::print(raw_ostream &OS) const {
assert(Operands.size() > 1 && "This plus expr shouldn't exist!");
const char *OpStr = getOperationStr();
OS << "(" << *Operands[0];
for (unsigned i = 1, e = Operands.size(); i != e; ++i)
OS << OpStr << *Operands[i];
OS << ")";
}
SCEVHandle SCEVCommutativeExpr::
replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
const SCEVHandle &Conc,
ScalarEvolution &SE) const {
for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
SCEVHandle H =
getOperand(i)->replaceSymbolicValuesWithConcrete(Sym, Conc, SE);
if (H != getOperand(i)) {
std::vector<SCEVHandle> NewOps;
NewOps.reserve(getNumOperands());
for (unsigned j = 0; j != i; ++j)
NewOps.push_back(getOperand(j));
NewOps.push_back(H);
for (++i; i != e; ++i)
NewOps.push_back(getOperand(i)->
replaceSymbolicValuesWithConcrete(Sym, Conc, SE));
if (isa<SCEVAddExpr>(this))
return SE.getAddExpr(NewOps);
else if (isa<SCEVMulExpr>(this))
return SE.getMulExpr(NewOps);
else if (isa<SCEVSMaxExpr>(this))
return SE.getSMaxExpr(NewOps);
else if (isa<SCEVUMaxExpr>(this))
return SE.getUMaxExpr(NewOps);
else
assert(0 && "Unknown commutative expr!");
}
}
return this;
}
bool SCEVCommutativeExpr::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;
}
static ManagedStatic<std::map<std::pair<SCEV*, SCEV*>,
SCEVUDivExpr*> > SCEVUDivs;
SCEVUDivExpr::~SCEVUDivExpr() {
SCEVUDivs->erase(std::make_pair(LHS, RHS));
}
bool SCEVUDivExpr::dominates(BasicBlock *BB, DominatorTree *DT) const {
return LHS->dominates(BB, DT) && RHS->dominates(BB, DT);
}
void SCEVUDivExpr::print(raw_ostream &OS) const {
OS << "(" << *LHS << " /u " << *RHS << ")";
}
const Type *SCEVUDivExpr::getType() const {
return LHS->getType();
}
static ManagedStatic<std::map<std::pair<const Loop *, std::vector<SCEV*> >,
SCEVAddRecExpr*> > SCEVAddRecExprs;
SCEVAddRecExpr::~SCEVAddRecExpr() {
SCEVAddRecExprs->erase(std::make_pair(L,
std::vector<SCEV*>(Operands.begin(),
Operands.end())));
}
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;
}
SCEVHandle SCEVAddRecExpr::
replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
const SCEVHandle &Conc,
ScalarEvolution &SE) const {
for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
SCEVHandle H =
getOperand(i)->replaceSymbolicValuesWithConcrete(Sym, Conc, SE);
if (H != getOperand(i)) {
std::vector<SCEVHandle> NewOps;
NewOps.reserve(getNumOperands());
for (unsigned j = 0; j != i; ++j)
NewOps.push_back(getOperand(j));
NewOps.push_back(H);
for (++i; i != e; ++i)
NewOps.push_back(getOperand(i)->
replaceSymbolicValuesWithConcrete(Sym, Conc, SE));
return SE.getAddRecExpr(NewOps, L);
}
}
return this;
}
bool SCEVAddRecExpr::isLoopInvariant(const Loop *QueryLoop) const {
return !QueryLoop->contains(L->getHeader()) &&
getOperand(0)->isLoopInvariant(QueryLoop);
}
void SCEVAddRecExpr::print(raw_ostream &OS) const {
OS << "{" << *Operands[0];
for (unsigned i = 1, e = Operands.size(); i != e; ++i)
OS << ",+," << *Operands[i];
OS << "}<" << L->getHeader()->getName() + ">";
}
static ManagedStatic<std::map<Value*, SCEVUnknown*> > SCEVUnknowns;
SCEVUnknown::~SCEVUnknown() { SCEVUnknowns->erase(V); }
bool SCEVUnknown::isLoopInvariant(const Loop *L) const {
if (Instruction *I = dyn_cast<Instruction>(V))
return !L->contains(I->getParent());
return true;
}
bool SCEVUnknown::dominates(BasicBlock *BB, DominatorTree *DT) const {
if (Instruction *I = dyn_cast<Instruction>(getValue()))
return DT->dominates(I->getParent(), BB);
return true;
}
const Type *SCEVUnknown::getType() const {
return V->getType();
}
void SCEVUnknown::print(raw_ostream &OS) const {
if (isa<PointerType>(V->getType()))
OS << "(ptrtoint " << *V->getType() << " ";
WriteAsOperand(OS, V, false);
if (isa<PointerType>(V->getType()))
OS << " to iPTR)";
}
namespace {
struct VISIBILITY_HIDDEN SCEVComplexityCompare {
bool operator()(const SCEV *LHS, const SCEV *RHS) const {
return LHS->getSCEVType() < RHS->getSCEVType();
}
};
}
static void GroupByComplexity(std::vector<SCEVHandle> &Ops) {
if (Ops.size() < 2) return; if (Ops.size() == 2) {
if (SCEVComplexityCompare()(Ops[1], Ops[0]))
std::swap(Ops[0], Ops[1]);
return;
}
std::sort(Ops.begin(), Ops.end(), SCEVComplexityCompare());
for (unsigned i = 0, e = Ops.size(); i != e-2; ++i) {
SCEV *S = Ops[i];
unsigned Complexity = S->getSCEVType();
for (unsigned j = i+1; j != e && Ops[j]->getSCEVType() == Complexity; ++j) {
if (Ops[j] == S) { std::swap(Ops[i+1], Ops[j]);
++i; if (i == e-2) return; }
}
}
}
static SCEVHandle BinomialCoefficient(SCEVHandle It, unsigned K,
ScalarEvolution &SE,
const Type* ResultTy) {
if (K == 1)
return SE.getTruncateOrZeroExtend(It, ResultTy);
if (K > 1000)
return SE.getCouldNotCompute();
unsigned W = SE.getTypeSizeInBits(ResultTy);
APInt OddFactorial(W, 1);
unsigned T = 1;
for (unsigned i = 3; i <= K; ++i) {
APInt Mult(W, i);
unsigned TwoFactors = Mult.countTrailingZeros();
T += TwoFactors;
Mult = Mult.lshr(TwoFactors);
OddFactorial *= Mult;
}
unsigned CalculationBits = W + T;
APInt DivFactor = APInt(CalculationBits, 1).shl(T);
APInt Mod = APInt::getSignedMinValue(W+1);
APInt MultiplyFactor = OddFactorial.zext(W+1);
MultiplyFactor = MultiplyFactor.multiplicativeInverse(Mod);
MultiplyFactor = MultiplyFactor.trunc(W);
const IntegerType *CalculationTy = IntegerType::get(CalculationBits);
SCEVHandle Dividend = SE.getTruncateOrZeroExtend(It, CalculationTy);
for (unsigned i = 1; i != K; ++i) {
SCEVHandle S = SE.getMinusSCEV(It, SE.getIntegerSCEV(i, It->getType()));
Dividend = SE.getMulExpr(Dividend,
SE.getTruncateOrZeroExtend(S, CalculationTy));
}
SCEVHandle DivResult = SE.getUDivExpr(Dividend, SE.getConstant(DivFactor));
return SE.getMulExpr(SE.getConstant(MultiplyFactor),
SE.getTruncateOrZeroExtend(DivResult, ResultTy));
}
SCEVHandle SCEVAddRecExpr::evaluateAtIteration(SCEVHandle It,
ScalarEvolution &SE) const {
SCEVHandle Result = getStart();
for (unsigned i = 1, e = getNumOperands(); i != e; ++i) {
SCEVHandle Coeff = BinomialCoefficient(It, i, SE, getType());
if (isa<SCEVCouldNotCompute>(Coeff))
return Coeff;
Result = SE.getAddExpr(Result, SE.getMulExpr(getOperand(i), Coeff));
}
return Result;
}
SCEVHandle ScalarEvolution::getTruncateExpr(const SCEVHandle &Op, const Type *Ty) {
assert(getTypeSizeInBits(Op->getType()) > getTypeSizeInBits(Ty) &&
"This is not a truncating conversion!");
if (SCEVConstant *SC = dyn_cast<SCEVConstant>(Op))
return getUnknown(
ConstantExpr::getTrunc(SC->getValue(), Ty));
if (SCEVTruncateExpr *ST = dyn_cast<SCEVTruncateExpr>(Op))
return getTruncateExpr(ST->getOperand(), Ty);
if (SCEVSignExtendExpr *SS = dyn_cast<SCEVSignExtendExpr>(Op))
return getTruncateOrSignExtend(SS->getOperand(), Ty);
if (SCEVZeroExtendExpr *SZ = dyn_cast<SCEVZeroExtendExpr>(Op))
return getTruncateOrZeroExtend(SZ->getOperand(), Ty);
if (SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Op)) {
std::vector<SCEVHandle> Operands;
for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i)
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());
}
SCEVTruncateExpr *&Result = (*SCEVTruncates)[std::make_pair(Op, Ty)];
if (Result == 0) Result = new SCEVTruncateExpr(Op, Ty);
return Result;
}
SCEVHandle ScalarEvolution::getZeroExtendExpr(const SCEVHandle &Op,
const Type *Ty) {
assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) &&
"This is not an extending conversion!");
if (SCEVConstant *SC = dyn_cast<SCEVConstant>(Op)) {
const Type *IntTy = getEffectiveSCEVType(Ty);
Constant *C = ConstantExpr::getZExt(SC->getValue(), IntTy);
if (IntTy != Ty) C = ConstantExpr::getIntToPtr(C, Ty);
return getUnknown(C);
}
if (SCEVZeroExtendExpr *SZ = dyn_cast<SCEVZeroExtendExpr>(Op))
return getZeroExtendExpr(SZ->getOperand(), Ty);
if (SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Op))
if (AR->isAffine()) {
SCEVHandle BECount = getBackedgeTakenCount(AR->getLoop());
if (!isa<SCEVCouldNotCompute>(BECount)) {
SCEVHandle Start = AR->getStart();
SCEVHandle Step = AR->getStepRecurrence(*this);
SCEVHandle CastedBECount =
getTruncateOrZeroExtend(BECount, Start->getType());
if (BECount ==
getTruncateOrZeroExtend(CastedBECount, BECount->getType())) {
const Type *WideTy =
IntegerType::get(getTypeSizeInBits(Start->getType()) * 2);
SCEVHandle ZMul =
getMulExpr(CastedBECount,
getTruncateOrZeroExtend(Step, Start->getType()));
if (getZeroExtendExpr(ZMul, WideTy) ==
getMulExpr(getZeroExtendExpr(CastedBECount, WideTy),
getZeroExtendExpr(Step, WideTy))) {
SCEVHandle Add = getAddExpr(Start, ZMul);
if (getZeroExtendExpr(Add, WideTy) ==
getAddExpr(getZeroExtendExpr(Start, WideTy),
getZeroExtendExpr(ZMul, WideTy)))
return getAddRecExpr(getZeroExtendExpr(Start, Ty),
getZeroExtendExpr(Step, Ty),
AR->getLoop());
}
SCEVHandle SMul =
getMulExpr(CastedBECount,
getTruncateOrSignExtend(Step, Start->getType()));
if (getSignExtendExpr(SMul, WideTy) ==
getMulExpr(getZeroExtendExpr(CastedBECount, WideTy),
getSignExtendExpr(Step, WideTy))) {
SCEVHandle Add = getAddExpr(Start, SMul);
if (getZeroExtendExpr(Add, WideTy) ==
getAddExpr(getZeroExtendExpr(Start, WideTy),
getSignExtendExpr(SMul, WideTy)))
return getAddRecExpr(getZeroExtendExpr(Start, Ty),
getSignExtendExpr(Step, Ty),
AR->getLoop());
}
}
}
}
SCEVZeroExtendExpr *&Result = (*SCEVZeroExtends)[std::make_pair(Op, Ty)];
if (Result == 0) Result = new SCEVZeroExtendExpr(Op, Ty);
return Result;
}
SCEVHandle ScalarEvolution::getSignExtendExpr(const SCEVHandle &Op,
const Type *Ty) {
assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) &&
"This is not an extending conversion!");
if (SCEVConstant *SC = dyn_cast<SCEVConstant>(Op)) {
const Type *IntTy = getEffectiveSCEVType(Ty);
Constant *C = ConstantExpr::getSExt(SC->getValue(), IntTy);
if (IntTy != Ty) C = ConstantExpr::getIntToPtr(C, Ty);
return getUnknown(C);
}
if (SCEVSignExtendExpr *SS = dyn_cast<SCEVSignExtendExpr>(Op))
return getSignExtendExpr(SS->getOperand(), Ty);
if (SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Op))
if (AR->isAffine()) {
SCEVHandle BECount = getBackedgeTakenCount(AR->getLoop());
if (!isa<SCEVCouldNotCompute>(BECount)) {
SCEVHandle Start = AR->getStart();
SCEVHandle Step = AR->getStepRecurrence(*this);
SCEVHandle CastedBECount =
getTruncateOrZeroExtend(BECount, Start->getType());
if (BECount ==
getTruncateOrZeroExtend(CastedBECount, BECount->getType()) &&
BECount ==
getTruncateOrSignExtend(CastedBECount, BECount->getType())) {
const Type *WideTy =
IntegerType::get(getTypeSizeInBits(Start->getType()) * 2);
SCEVHandle SMul =
getMulExpr(CastedBECount,
getTruncateOrSignExtend(Step, Start->getType()));
if (getSignExtendExpr(SMul, WideTy) ==
getMulExpr(getSignExtendExpr(CastedBECount, WideTy),
getSignExtendExpr(Step, WideTy))) {
SCEVHandle Add = getAddExpr(Start, SMul);
if (getSignExtendExpr(Add, WideTy) ==
getAddExpr(getSignExtendExpr(Start, WideTy),
getSignExtendExpr(SMul, WideTy)))
return getAddRecExpr(getSignExtendExpr(Start, Ty),
getSignExtendExpr(Step, Ty),
AR->getLoop());
}
}
}
}
SCEVSignExtendExpr *&Result = (*SCEVSignExtends)[std::make_pair(Op, Ty)];
if (Result == 0) Result = new SCEVSignExtendExpr(Op, Ty);
return Result;
}
SCEVHandle ScalarEvolution::getAddExpr(std::vector<SCEVHandle> &Ops) {
assert(!Ops.empty() && "Cannot get empty add!");
if (Ops.size() == 1) return Ops[0];
GroupByComplexity(Ops);
unsigned Idx = 0;
if (SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
++Idx;
assert(Idx < Ops.size());
while (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
ConstantInt *Fold = ConstantInt::get(LHSC->getValue()->getValue() +
RHSC->getValue()->getValue());
Ops[0] = getConstant(Fold);
Ops.erase(Ops.begin()+1); if (Ops.size() == 1) return Ops[0];
LHSC = cast<SCEVConstant>(Ops[0]);
}
if (cast<SCEVConstant>(Ops[0])->getValue()->isZero()) {
Ops.erase(Ops.begin());
--Idx;
}
}
if (Ops.size() == 1) return Ops[0];
const Type *Ty = Ops[0]->getType();
for (unsigned i = 0, e = Ops.size()-1; i != e; ++i)
if (Ops[i] == Ops[i+1]) { SCEVHandle Two = getIntegerSCEV(2, Ty);
SCEVHandle Mul = getMulExpr(Ops[i], Two);
if (Ops.size() == 2)
return Mul;
Ops.erase(Ops.begin()+i, Ops.begin()+i+2);
Ops.push_back(Mul);
return getAddExpr(Ops);
}
while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scAddExpr)
++Idx;
if (Idx < Ops.size()) {
bool DeletedAdd = false;
while (SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[Idx])) {
Ops.insert(Ops.end(), Add->op_begin(), Add->op_end());
Ops.erase(Ops.begin()+Idx);
DeletedAdd = true;
}
if (DeletedAdd)
return getAddExpr(Ops);
}
while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scMulExpr)
++Idx;
for (; Idx < Ops.size() && isa<SCEVMulExpr>(Ops[Idx]); ++Idx) {
SCEVMulExpr *Mul = cast<SCEVMulExpr>(Ops[Idx]);
for (unsigned MulOp = 0, e = Mul->getNumOperands(); MulOp != e; ++MulOp) {
SCEV *MulOpSCEV = Mul->getOperand(MulOp);
for (unsigned AddOp = 0, e = Ops.size(); AddOp != e; ++AddOp)
if (MulOpSCEV == Ops[AddOp] && !isa<SCEVConstant>(MulOpSCEV)) {
SCEVHandle InnerMul = Mul->getOperand(MulOp == 0);
if (Mul->getNumOperands() != 2) {
std::vector<SCEVHandle> MulOps(Mul->op_begin(), Mul->op_end());
MulOps.erase(MulOps.begin()+MulOp);
InnerMul = getMulExpr(MulOps);
}
SCEVHandle One = getIntegerSCEV(1, Ty);
SCEVHandle AddOne = getAddExpr(InnerMul, One);
SCEVHandle OuterMul = getMulExpr(AddOne, Ops[AddOp]);
if (Ops.size() == 2) return OuterMul;
if (AddOp < Idx) {
Ops.erase(Ops.begin()+AddOp);
Ops.erase(Ops.begin()+Idx-1);
} else {
Ops.erase(Ops.begin()+Idx);
Ops.erase(Ops.begin()+AddOp-1);
}
Ops.push_back(OuterMul);
return getAddExpr(Ops);
}
for (unsigned OtherMulIdx = Idx+1;
OtherMulIdx < Ops.size() && isa<SCEVMulExpr>(Ops[OtherMulIdx]);
++OtherMulIdx) {
SCEVMulExpr *OtherMul = cast<SCEVMulExpr>(Ops[OtherMulIdx]);
for (unsigned OMulOp = 0, e = OtherMul->getNumOperands();
OMulOp != e; ++OMulOp)
if (OtherMul->getOperand(OMulOp) == MulOpSCEV) {
SCEVHandle InnerMul1 = Mul->getOperand(MulOp == 0);
if (Mul->getNumOperands() != 2) {
std::vector<SCEVHandle> 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(),
OtherMul->op_end());
MulOps.erase(MulOps.begin()+OMulOp);
InnerMul2 = getMulExpr(MulOps);
}
SCEVHandle InnerMulSum = getAddExpr(InnerMul1,InnerMul2);
SCEVHandle OuterMul = getMulExpr(MulOpSCEV, InnerMulSum);
if (Ops.size() == 2) return OuterMul;
Ops.erase(Ops.begin()+Idx);
Ops.erase(Ops.begin()+OtherMulIdx-1);
Ops.push_back(OuterMul);
return getAddExpr(Ops);
}
}
}
}
while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scAddRecExpr)
++Idx;
for (; Idx < Ops.size() && isa<SCEVAddRecExpr>(Ops[Idx]); ++Idx) {
std::vector<SCEVHandle> LIOps;
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]);
Ops.erase(Ops.begin()+i);
--i; --e;
}
if (!LIOps.empty()) {
LIOps.push_back(AddRec->getStart());
std::vector<SCEVHandle> AddRecOps(AddRec->op_begin(), AddRec->op_end());
AddRecOps[0] = getAddExpr(LIOps);
SCEVHandle NewRec = getAddRecExpr(AddRecOps, AddRec->getLoop());
if (Ops.size() == 1) return NewRec;
for (unsigned i = 0;; ++i)
if (Ops[i] == AddRec) {
Ops[i] = NewRec;
break;
}
return getAddExpr(Ops);
}
for (unsigned OtherIdx = Idx+1;
OtherIdx < Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);++OtherIdx)
if (OtherIdx != Idx) {
SCEVAddRecExpr *OtherAddRec = cast<SCEVAddRecExpr>(Ops[OtherIdx]);
if (AddRec->getLoop() == OtherAddRec->getLoop()) {
std::vector<SCEVHandle> 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,
OtherAddRec->op_end());
break;
}
NewOps[i] = getAddExpr(NewOps[i], OtherAddRec->getOperand(i));
}
SCEVHandle NewAddRec = getAddRecExpr(NewOps, AddRec->getLoop());
if (Ops.size() == 2) return NewAddRec;
Ops.erase(Ops.begin()+Idx);
Ops.erase(Ops.begin()+OtherIdx-1);
Ops.push_back(NewAddRec);
return getAddExpr(Ops);
}
}
}
std::vector<SCEV*> SCEVOps(Ops.begin(), Ops.end());
SCEVCommutativeExpr *&Result = (*SCEVCommExprs)[std::make_pair(scAddExpr,
SCEVOps)];
if (Result == 0) Result = new SCEVAddExpr(Ops);
return Result;
}
SCEVHandle ScalarEvolution::getMulExpr(std::vector<SCEVHandle> &Ops) {
assert(!Ops.empty() && "Cannot get empty mul!");
GroupByComplexity(Ops);
unsigned Idx = 0;
if (SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
if (Ops.size() == 2)
if (SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[1]))
if (Add->getNumOperands() == 2 &&
isa<SCEVConstant>(Add->getOperand(0)))
return getAddExpr(getMulExpr(LHSC, Add->getOperand(0)),
getMulExpr(LHSC, Add->getOperand(1)));
++Idx;
while (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
ConstantInt *Fold = ConstantInt::get(LHSC->getValue()->getValue() *
RHSC->getValue()->getValue());
Ops[0] = getConstant(Fold);
Ops.erase(Ops.begin()+1); if (Ops.size() == 1) return Ops[0];
LHSC = cast<SCEVConstant>(Ops[0]);
}
if (cast<SCEVConstant>(Ops[0])->getValue()->equalsInt(1)) {
Ops.erase(Ops.begin());
--Idx;
} else if (cast<SCEVConstant>(Ops[0])->getValue()->isZero()) {
return Ops[0];
}
}
while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scMulExpr)
++Idx;
if (Ops.size() == 1)
return Ops[0];
if (Idx < Ops.size()) {
bool DeletedMul = false;
while (SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(Ops[Idx])) {
Ops.insert(Ops.end(), Mul->op_begin(), Mul->op_end());
Ops.erase(Ops.begin()+Idx);
DeletedMul = true;
}
if (DeletedMul)
return getMulExpr(Ops);
}
while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scAddRecExpr)
++Idx;
for (; Idx < Ops.size() && isa<SCEVAddRecExpr>(Ops[Idx]); ++Idx) {
std::vector<SCEVHandle> LIOps;
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]);
Ops.erase(Ops.begin()+i);
--i; --e;
}
if (!LIOps.empty()) {
std::vector<SCEVHandle> NewOps;
NewOps.reserve(AddRec->getNumOperands());
if (LIOps.size() == 1) {
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);
MulOps.push_back(AddRec->getOperand(i));
NewOps.push_back(getMulExpr(MulOps));
}
}
SCEVHandle NewRec = getAddRecExpr(NewOps, AddRec->getLoop());
if (Ops.size() == 1) return NewRec;
for (unsigned i = 0;; ++i)
if (Ops[i] == AddRec) {
Ops[i] = NewRec;
break;
}
return getMulExpr(Ops);
}
for (unsigned OtherIdx = Idx+1;
OtherIdx < Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);++OtherIdx)
if (OtherIdx != Idx) {
SCEVAddRecExpr *OtherAddRec = cast<SCEVAddRecExpr>(Ops[OtherIdx]);
if (AddRec->getLoop() == OtherAddRec->getLoop()) {
SCEVAddRecExpr *F = AddRec, *G = OtherAddRec;
SCEVHandle NewStart = getMulExpr(F->getStart(),
G->getStart());
SCEVHandle B = F->getStepRecurrence(*this);
SCEVHandle D = G->getStepRecurrence(*this);
SCEVHandle NewStep = getAddExpr(getMulExpr(F, D),
getMulExpr(G, B),
getMulExpr(B, D));
SCEVHandle NewAddRec = getAddRecExpr(NewStart, NewStep,
F->getLoop());
if (Ops.size() == 2) return NewAddRec;
Ops.erase(Ops.begin()+Idx);
Ops.erase(Ops.begin()+OtherIdx-1);
Ops.push_back(NewAddRec);
return getMulExpr(Ops);
}
}
}
std::vector<SCEV*> SCEVOps(Ops.begin(), Ops.end());
SCEVCommutativeExpr *&Result = (*SCEVCommExprs)[std::make_pair(scMulExpr,
SCEVOps)];
if (Result == 0)
Result = new SCEVMulExpr(Ops);
return Result;
}
SCEVHandle ScalarEvolution::getUDivExpr(const SCEVHandle &LHS, const SCEVHandle &RHS) {
if (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS)) {
if (RHSC->getValue()->equalsInt(1))
return LHS;
if (SCEVConstant *LHSC = dyn_cast<SCEVConstant>(LHS)) {
Constant *LHSCV = LHSC->getValue();
Constant *RHSCV = RHSC->getValue();
return getUnknown(ConstantExpr::getUDiv(LHSCV, RHSCV));
}
}
SCEVUDivExpr *&Result = (*SCEVUDivs)[std::make_pair(LHS, RHS)];
if (Result == 0) Result = new SCEVUDivExpr(LHS, RHS);
return Result;
}
SCEVHandle ScalarEvolution::getAddRecExpr(const SCEVHandle &Start,
const SCEVHandle &Step, const Loop *L) {
std::vector<SCEVHandle> Operands;
Operands.push_back(Start);
if (SCEVAddRecExpr *StepChrec = dyn_cast<SCEVAddRecExpr>(Step))
if (StepChrec->getLoop() == L) {
Operands.insert(Operands.end(), StepChrec->op_begin(),
StepChrec->op_end());
return getAddRecExpr(Operands, L);
}
Operands.push_back(Step);
return getAddRecExpr(Operands, L);
}
SCEVHandle ScalarEvolution::getAddRecExpr(std::vector<SCEVHandle> &Operands,
const Loop *L) {
if (Operands.size() == 1) return Operands[0];
if (Operands.back()->isZero()) {
Operands.pop_back();
return getAddRecExpr(Operands, L); }
if (SCEVAddRecExpr *NestedAR = dyn_cast<SCEVAddRecExpr>(Operands[0])) {
const Loop* NestedLoop = NestedAR->getLoop();
if (L->getLoopDepth() < NestedLoop->getLoopDepth()) {
std::vector<SCEVHandle> NestedOperands(NestedAR->op_begin(),
NestedAR->op_end());
SCEVHandle NestedARHandle(NestedAR);
Operands[0] = NestedAR->getStart();
NestedOperands[0] = getAddRecExpr(Operands, L);
return getAddRecExpr(NestedOperands, NestedLoop);
}
}
SCEVAddRecExpr *&Result =
(*SCEVAddRecExprs)[std::make_pair(L, std::vector<SCEV*>(Operands.begin(),
Operands.end()))];
if (Result == 0) Result = new SCEVAddRecExpr(Operands, L);
return Result;
}
SCEVHandle ScalarEvolution::getSMaxExpr(const SCEVHandle &LHS,
const SCEVHandle &RHS) {
std::vector<SCEVHandle> Ops;
Ops.push_back(LHS);
Ops.push_back(RHS);
return getSMaxExpr(Ops);
}
SCEVHandle ScalarEvolution::getSMaxExpr(std::vector<SCEVHandle> Ops) {
assert(!Ops.empty() && "Cannot get empty smax!");
if (Ops.size() == 1) return Ops[0];
GroupByComplexity(Ops);
unsigned Idx = 0;
if (SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
++Idx;
assert(Idx < Ops.size());
while (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
ConstantInt *Fold = ConstantInt::get(
APIntOps::smax(LHSC->getValue()->getValue(),
RHSC->getValue()->getValue()));
Ops[0] = getConstant(Fold);
Ops.erase(Ops.begin()+1); if (Ops.size() == 1) return Ops[0];
LHSC = cast<SCEVConstant>(Ops[0]);
}
if (cast<SCEVConstant>(Ops[0])->getValue()->isMinValue(true)) {
Ops.erase(Ops.begin());
--Idx;
}
}
if (Ops.size() == 1) return Ops[0];
while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scSMaxExpr)
++Idx;
if (Idx < Ops.size()) {
bool DeletedSMax = false;
while (SCEVSMaxExpr *SMax = dyn_cast<SCEVSMaxExpr>(Ops[Idx])) {
Ops.insert(Ops.end(), SMax->op_begin(), SMax->op_end());
Ops.erase(Ops.begin()+Idx);
DeletedSMax = true;
}
if (DeletedSMax)
return getSMaxExpr(Ops);
}
for (unsigned i = 0, e = Ops.size()-1; i != e; ++i)
if (Ops[i] == Ops[i+1]) { Ops.erase(Ops.begin()+i, Ops.begin()+i+1);
--i; --e;
}
if (Ops.size() == 1) return Ops[0];
assert(!Ops.empty() && "Reduced smax down to nothing!");
std::vector<SCEV*> SCEVOps(Ops.begin(), Ops.end());
SCEVCommutativeExpr *&Result = (*SCEVCommExprs)[std::make_pair(scSMaxExpr,
SCEVOps)];
if (Result == 0) Result = new SCEVSMaxExpr(Ops);
return Result;
}
SCEVHandle ScalarEvolution::getUMaxExpr(const SCEVHandle &LHS,
const SCEVHandle &RHS) {
std::vector<SCEVHandle> Ops;
Ops.push_back(LHS);
Ops.push_back(RHS);
return getUMaxExpr(Ops);
}
SCEVHandle ScalarEvolution::getUMaxExpr(std::vector<SCEVHandle> Ops) {
assert(!Ops.empty() && "Cannot get empty umax!");
if (Ops.size() == 1) return Ops[0];
GroupByComplexity(Ops);
unsigned Idx = 0;
if (SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
++Idx;
assert(Idx < Ops.size());
while (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
ConstantInt *Fold = ConstantInt::get(
APIntOps::umax(LHSC->getValue()->getValue(),
RHSC->getValue()->getValue()));
Ops[0] = getConstant(Fold);
Ops.erase(Ops.begin()+1); if (Ops.size() == 1) return Ops[0];
LHSC = cast<SCEVConstant>(Ops[0]);
}
if (cast<SCEVConstant>(Ops[0])->getValue()->isMinValue(false)) {
Ops.erase(Ops.begin());
--Idx;
}
}
if (Ops.size() == 1) return Ops[0];
while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scUMaxExpr)
++Idx;
if (Idx < Ops.size()) {
bool DeletedUMax = false;
while (SCEVUMaxExpr *UMax = dyn_cast<SCEVUMaxExpr>(Ops[Idx])) {
Ops.insert(Ops.end(), UMax->op_begin(), UMax->op_end());
Ops.erase(Ops.begin()+Idx);
DeletedUMax = true;
}
if (DeletedUMax)
return getUMaxExpr(Ops);
}
for (unsigned i = 0, e = Ops.size()-1; i != e; ++i)
if (Ops[i] == Ops[i+1]) { Ops.erase(Ops.begin()+i, Ops.begin()+i+1);
--i; --e;
}
if (Ops.size() == 1) return Ops[0];
assert(!Ops.empty() && "Reduced umax down to nothing!");
std::vector<SCEV*> SCEVOps(Ops.begin(), Ops.end());
SCEVCommutativeExpr *&Result = (*SCEVCommExprs)[std::make_pair(scUMaxExpr,
SCEVOps)];
if (Result == 0) Result = new SCEVUMaxExpr(Ops);
return Result;
}
SCEVHandle ScalarEvolution::getUnknown(Value *V) {
if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
return getConstant(CI);
if (isa<ConstantPointerNull>(V))
return getIntegerSCEV(0, V->getType());
SCEVUnknown *&Result = (*SCEVUnknowns)[V];
if (Result == 0) Result = new SCEVUnknown(V);
return Result;
}
void ScalarEvolution::deleteValueFromRecords(Value *V) {
SmallVector<Value *, 16> Worklist;
if (Scalars.erase(V)) {
if (PHINode *PN = dyn_cast<PHINode>(V))
ConstantEvolutionLoopExitValue.erase(PN);
if (Instruction *I = dyn_cast<Instruction>(V))
ValuesAtScopes.erase(I);
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);
if (Instruction *I = dyn_cast<Instruction>(VV))
ValuesAtScopes.erase(I);
Worklist.push_back(Inst);
}
}
}
}
bool ScalarEvolution::isSCEVable(const Type *Ty) const {
if (Ty->isInteger())
return true;
if (isa<PointerType>(Ty))
return TD != NULL;
return false;
}
uint64_t ScalarEvolution::getTypeSizeInBits(const Type *Ty) const {
assert(isSCEVable(Ty) && "Type is not SCEVable!");
if (TD)
return TD->getTypeSizeInBits(Ty);
assert(Ty->isInteger() && "isSCEVable permitted a non-SCEVable type!");
return Ty->getPrimitiveSizeInBits();
}
const Type *ScalarEvolution::getEffectiveSCEVType(const Type *Ty) const {
assert(isSCEVable(Ty) && "Type is not SCEVable!");
if (Ty->isInteger())
return Ty;
assert(isa<PointerType>(Ty) && "Unexpected non-pointer non-integer type!");
return TD->getIntPtrType();
}
SCEVHandle ScalarEvolution::getCouldNotCompute() {
return UnknownValue;
}
SCEVHandle ScalarEvolution::getSCEV(Value *V) {
assert(isSCEVable(V->getType()) && "Value is not SCEVable!");
std::map<Value*, SCEVHandle>::iterator I = Scalars.find(V);
if (I != Scalars.end()) return I->second;
SCEVHandle S = createSCEV(V);
Scalars.insert(std::make_pair(V, S));
return S;
}
SCEVHandle ScalarEvolution::getIntegerSCEV(int Val, const Type *Ty) {
Ty = getEffectiveSCEVType(Ty);
Constant *C;
if (Val == 0)
C = Constant::getNullValue(Ty);
else if (Ty->isFloatingPoint())
C = ConstantFP::get(APFloat(Ty==Type::FloatTy ? APFloat::IEEEsingle :
APFloat::IEEEdouble, Val));
else
C = ConstantInt::get(Ty, Val);
return getUnknown(C);
}
SCEVHandle ScalarEvolution::getNegativeSCEV(const SCEVHandle &V) {
if (SCEVConstant *VC = dyn_cast<SCEVConstant>(V))
return getUnknown(ConstantExpr::getNeg(VC->getValue()));
const Type *Ty = V->getType();
Ty = getEffectiveSCEVType(Ty);
return getMulExpr(V, getConstant(ConstantInt::getAllOnesValue(Ty)));
}
SCEVHandle ScalarEvolution::getNotSCEV(const SCEVHandle &V) {
if (SCEVConstant *VC = dyn_cast<SCEVConstant>(V))
return getUnknown(ConstantExpr::getNot(VC->getValue()));
const Type *Ty = V->getType();
Ty = getEffectiveSCEVType(Ty);
SCEVHandle AllOnes = getConstant(ConstantInt::getAllOnesValue(Ty));
return getMinusSCEV(AllOnes, V);
}
SCEVHandle ScalarEvolution::getMinusSCEV(const SCEVHandle &LHS,
const SCEVHandle &RHS) {
return getAddExpr(LHS, getNegativeSCEV(RHS));
}
SCEVHandle
ScalarEvolution::getTruncateOrZeroExtend(const SCEVHandle &V,
const Type *Ty) {
const Type *SrcTy = V->getType();
assert((SrcTy->isInteger() || (TD && isa<PointerType>(SrcTy))) &&
(Ty->isInteger() || (TD && isa<PointerType>(Ty))) &&
"Cannot truncate or zero extend with non-integer arguments!");
if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty))
return V; if (getTypeSizeInBits(SrcTy) > getTypeSizeInBits(Ty))
return getTruncateExpr(V, Ty);
return getZeroExtendExpr(V, Ty);
}
SCEVHandle
ScalarEvolution::getTruncateOrSignExtend(const SCEVHandle &V,
const Type *Ty) {
const Type *SrcTy = V->getType();
assert((SrcTy->isInteger() || (TD && isa<PointerType>(SrcTy))) &&
(Ty->isInteger() || (TD && isa<PointerType>(Ty))) &&
"Cannot truncate or zero extend with non-integer arguments!");
if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty))
return V; if (getTypeSizeInBits(SrcTy) > getTypeSizeInBits(Ty))
return getTruncateExpr(V, Ty);
return getSignExtendExpr(V, Ty);
}
void ScalarEvolution::
ReplaceSymbolicValueWithConcrete(Instruction *I, const SCEVHandle &SymName,
const SCEVHandle &NewVal) {
std::map<Value*, SCEVHandle>::iterator SI = Scalars.find(I);
if (SI == Scalars.end()) return;
SCEVHandle NV =
SI->second->replaceSymbolicValuesWithConcrete(SymName, NewVal, *this);
if (NV == SI->second) return;
SI->second = NV;
for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
UI != E; ++UI)
ReplaceSymbolicValueWithConcrete(cast<Instruction>(*UI), SymName, NewVal);
}
SCEVHandle ScalarEvolution::createNodeForPHI(PHINode *PN) {
if (PN->getNumIncomingValues() == 2) if (const Loop *L = LI->getLoopFor(PN->getParent()))
if (L->getHeader() == PN->getParent()) {
unsigned IncomingEdge = L->contains(PN->getIncomingBlock(0));
unsigned BackEdge = IncomingEdge^1;
SCEVHandle SymbolicName = getUnknown(PN);
assert(Scalars.find(PN) == Scalars.end() &&
"PHI node already processed?");
Scalars.insert(std::make_pair(PN, SymbolicName));
SCEVHandle BEValue = getSCEV(PN->getIncomingValue(BackEdge));
if (SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(BEValue)) {
unsigned FoundIndex = Add->getNumOperands();
for (unsigned i = 0, e = Add->getNumOperands(); i != e; ++i)
if (Add->getOperand(i) == SymbolicName)
if (FoundIndex == e) {
FoundIndex = i;
break;
}
if (FoundIndex != Add->getNumOperands()) {
std::vector<SCEVHandle> Ops;
for (unsigned i = 0, e = Add->getNumOperands(); i != e; ++i)
if (i != FoundIndex)
Ops.push_back(Add->getOperand(i));
SCEVHandle Accum = getAddExpr(Ops);
if (Accum->isLoopInvariant(L) ||
(isa<SCEVAddRecExpr>(Accum) &&
cast<SCEVAddRecExpr>(Accum)->getLoop() == L)) {
SCEVHandle StartVal = getSCEV(PN->getIncomingValue(IncomingEdge));
SCEVHandle PHISCEV = getAddRecExpr(StartVal, Accum, L);
ReplaceSymbolicValueWithConcrete(PN, SymbolicName, PHISCEV);
return PHISCEV;
}
}
} else if (SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(BEValue)) {
if (AddRec->getLoop() == L && AddRec->isAffine()) {
SCEVHandle StartVal = getSCEV(PN->getIncomingValue(IncomingEdge));
if (StartVal == getMinusSCEV(AddRec->getOperand(0),
AddRec->getOperand(1))) {
SCEVHandle PHISCEV =
getAddRecExpr(StartVal, AddRec->getOperand(1), L);
ReplaceSymbolicValueWithConcrete(PN, SymbolicName, PHISCEV);
return PHISCEV;
}
}
}
return SymbolicName;
}
return getUnknown(PN);
}
static uint32_t GetMinTrailingZeros(SCEVHandle S, const ScalarEvolution &SE) {
if (SCEVConstant *C = dyn_cast<SCEVConstant>(S))
return C->getValue()->getValue().countTrailingZeros();
if (SCEVTruncateExpr *T = dyn_cast<SCEVTruncateExpr>(S))
return std::min(GetMinTrailingZeros(T->getOperand(), SE),
(uint32_t)SE.getTypeSizeInBits(T->getType()));
if (SCEVZeroExtendExpr *E = dyn_cast<SCEVZeroExtendExpr>(S)) {
uint32_t OpRes = GetMinTrailingZeros(E->getOperand(), SE);
return OpRes == SE.getTypeSizeInBits(E->getOperand()->getType()) ?
SE.getTypeSizeInBits(E->getOperand()->getType()) : OpRes;
}
if (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;
}
if (SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) {
uint32_t MinOpRes = GetMinTrailingZeros(A->getOperand(0), SE);
for (unsigned i = 1, e = A->getNumOperands(); MinOpRes && i != e; ++i)
MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(A->getOperand(i), SE));
return MinOpRes;
}
if (SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(S)) {
uint32_t SumOpRes = GetMinTrailingZeros(M->getOperand(0), SE);
uint32_t BitWidth = SE.getTypeSizeInBits(M->getType());
for (unsigned i = 1, e = M->getNumOperands();
SumOpRes != BitWidth && i != e; ++i)
SumOpRes = std::min(SumOpRes + GetMinTrailingZeros(M->getOperand(i), SE),
BitWidth);
return SumOpRes;
}
if (SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(S)) {
uint32_t MinOpRes = GetMinTrailingZeros(A->getOperand(0), SE);
for (unsigned i = 1, e = A->getNumOperands(); MinOpRes && i != e; ++i)
MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(A->getOperand(i), SE));
return MinOpRes;
}
if (SCEVSMaxExpr *M = dyn_cast<SCEVSMaxExpr>(S)) {
uint32_t MinOpRes = GetMinTrailingZeros(M->getOperand(0), SE);
for (unsigned i = 1, e = M->getNumOperands(); MinOpRes && i != e; ++i)
MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(M->getOperand(i), SE));
return MinOpRes;
}
if (SCEVUMaxExpr *M = dyn_cast<SCEVUMaxExpr>(S)) {
uint32_t MinOpRes = GetMinTrailingZeros(M->getOperand(0), SE);
for (unsigned i = 1, e = M->getNumOperands(); MinOpRes && i != e; ++i)
MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(M->getOperand(i), SE));
return MinOpRes;
}
return 0;
}
SCEVHandle ScalarEvolution::createSCEV(Value *V) {
if (!isSCEVable(V->getType()))
return getUnknown(V);
unsigned Opcode = Instruction::UserOp1;
if (Instruction *I = dyn_cast<Instruction>(V))
Opcode = I->getOpcode();
else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
Opcode = CE->getOpcode();
else
return getUnknown(V);
User *U = cast<User>(V);
switch (Opcode) {
case Instruction::Add:
return getAddExpr(getSCEV(U->getOperand(0)),
getSCEV(U->getOperand(1)));
case Instruction::Mul:
return getMulExpr(getSCEV(U->getOperand(0)),
getSCEV(U->getOperand(1)));
case Instruction::UDiv:
return getUDivExpr(getSCEV(U->getOperand(0)),
getSCEV(U->getOperand(1)));
case Instruction::Sub:
return getMinusSCEV(getSCEV(U->getOperand(0)),
getSCEV(U->getOperand(1)));
case Instruction::And:
if (ConstantInt *CI = dyn_cast<ConstantInt>(U->getOperand(1))) {
const APInt &A = CI->getValue();
unsigned Ones = A.countTrailingOnes();
if (APIntOps::isMask(Ones, A))
return
getZeroExtendExpr(getTruncateExpr(getSCEV(U->getOperand(0)),
IntegerType::get(Ones)),
U->getType());
}
break;
case Instruction::Or:
if (ConstantInt *CI = dyn_cast<ConstantInt>(U->getOperand(1))) {
SCEVHandle LHS = getSCEV(U->getOperand(0));
const APInt &CIVal = CI->getValue();
if (GetMinTrailingZeros(LHS, *this) >=
(CIVal.getBitWidth() - CIVal.countLeadingZeros()))
return getAddExpr(LHS, getSCEV(U->getOperand(1)));
}
break;
case Instruction::Xor:
if (ConstantInt *CI = dyn_cast<ConstantInt>(U->getOperand(1))) {
if (CI->getValue().isSignBit())
return getAddExpr(getSCEV(U->getOperand(0)),
getSCEV(U->getOperand(1)));
else if (CI->isAllOnesValue())
return getNotSCEV(getSCEV(U->getOperand(0)));
}
break;
case Instruction::Shl:
if (ConstantInt *SA = dyn_cast<ConstantInt>(U->getOperand(1))) {
uint32_t BitWidth = cast<IntegerType>(V->getType())->getBitWidth();
Constant *X = ConstantInt::get(
APInt(BitWidth, 1).shl(SA->getLimitedValue(BitWidth)));
return getMulExpr(getSCEV(U->getOperand(0)), getSCEV(X));
}
break;
case Instruction::LShr:
if (ConstantInt *SA = dyn_cast<ConstantInt>(U->getOperand(1))) {
uint32_t BitWidth = cast<IntegerType>(V->getType())->getBitWidth();
Constant *X = ConstantInt::get(
APInt(BitWidth, 1).shl(SA->getLimitedValue(BitWidth)));
return getUDivExpr(getSCEV(U->getOperand(0)), getSCEV(X));
}
break;
case Instruction::AShr:
if (ConstantInt *CI = dyn_cast<ConstantInt>(U->getOperand(1)))
if (Instruction *L = dyn_cast<Instruction>(U->getOperand(0)))
if (L->getOpcode() == Instruction::Shl &&
L->getOperand(1) == U->getOperand(1)) {
uint64_t Amt = getTypeSizeInBits(U->getType()) - CI->getZExtValue();
return
getSignExtendExpr(getTruncateExpr(getSCEV(L->getOperand(0)),
IntegerType::get(Amt)),
U->getType());
}
break;
case Instruction::Trunc:
return getTruncateExpr(getSCEV(U->getOperand(0)), U->getType());
case Instruction::ZExt:
return getZeroExtendExpr(getSCEV(U->getOperand(0)), U->getType());
case Instruction::SExt:
return getSignExtendExpr(getSCEV(U->getOperand(0)), U->getType());
case Instruction::BitCast:
if (isSCEVable(U->getType()) && isSCEVable(U->getOperand(0)->getType()))
return getSCEV(U->getOperand(0));
break;
case Instruction::IntToPtr:
if (!TD) break; return getTruncateOrZeroExtend(getSCEV(U->getOperand(0)),
TD->getIntPtrType());
case Instruction::PtrToInt:
if (!TD) break; return getTruncateOrZeroExtend(getSCEV(U->getOperand(0)),
U->getType());
case Instruction::GetElementPtr: {
if (!TD) break; 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;
if (const StructType *STy = dyn_cast<StructType>(*GTI++)) {
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 {
SCEVHandle LocalOffset = getSCEV(Index);
if (!isa<PointerType>(LocalOffset->getType()))
LocalOffset = getTruncateOrSignExtend(LocalOffset,
IntPtrTy);
LocalOffset =
getMulExpr(LocalOffset,
getIntegerSCEV(TD->getTypePaddedSize(*GTI),
IntPtrTy));
TotalOffset = getAddExpr(TotalOffset, LocalOffset);
}
}
return getAddExpr(getSCEV(Base), TotalOffset);
}
case Instruction::PHI:
return createNodeForPHI(cast<PHINode>(U));
case Instruction::Select:
if (ICmpInst *ICI = dyn_cast<ICmpInst>(U->getOperand(0))) {
Value *LHS = ICI->getOperand(0);
Value *RHS = ICI->getOperand(1);
switch (ICI->getPredicate()) {
case ICmpInst::ICMP_SLT:
case ICmpInst::ICMP_SLE:
std::swap(LHS, RHS);
case ICmpInst::ICMP_SGT:
case ICmpInst::ICMP_SGE:
if (LHS == U->getOperand(1) && RHS == U->getOperand(2))
return getSMaxExpr(getSCEV(LHS), getSCEV(RHS));
else if (LHS == U->getOperand(2) && RHS == U->getOperand(1))
return getNotSCEV(getSMaxExpr(
getNotSCEV(getSCEV(LHS)),
getNotSCEV(getSCEV(RHS))));
break;
case ICmpInst::ICMP_ULT:
case ICmpInst::ICMP_ULE:
std::swap(LHS, RHS);
case ICmpInst::ICMP_UGT:
case ICmpInst::ICMP_UGE:
if (LHS == U->getOperand(1) && RHS == U->getOperand(2))
return getUMaxExpr(getSCEV(LHS), getSCEV(RHS));
else if (LHS == U->getOperand(2) && RHS == U->getOperand(1))
return getNotSCEV(getUMaxExpr(getNotSCEV(getSCEV(LHS)),
getNotSCEV(getSCEV(RHS))));
break;
default:
break;
}
}
default: break;
}
return getUnknown(V);
}
SCEVHandle ScalarEvolution::getBackedgeTakenCount(const Loop *L) {
std::pair<std::map<const Loop*, SCEVHandle>::iterator, bool> Pair =
BackedgeTakenCounts.insert(std::make_pair(L, getCouldNotCompute()));
if (Pair.second) {
SCEVHandle ItCount = ComputeBackedgeTakenCount(L);
if (ItCount != UnknownValue) {
assert(ItCount->isLoopInvariant(L) &&
"Computed trip count isn't loop invariant for loop!");
++NumTripCountsComputed;
for (BasicBlock::iterator I = L->getHeader()->begin();
PHINode *PN = dyn_cast<PHINode>(I); ++I)
deleteValueFromRecords(PN);
Pair.first->second = ItCount;
} else if (isa<PHINode>(L->getHeader()->begin())) {
++NumTripCountsNotComputed;
}
}
return Pair.first->second;
}
void ScalarEvolution::forgetLoopBackedgeTakenCount(const Loop *L) {
BackedgeTakenCounts.erase(L);
}
SCEVHandle ScalarEvolution::ComputeBackedgeTakenCount(const Loop *L) {
SmallVector<BasicBlock*, 8> ExitBlocks;
L->getExitBlocks(ExitBlocks);
if (ExitBlocks.size() != 1) return UnknownValue;
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; }
assert(ExitingBlock && "No exits from loop, something is broken!");
BranchInst *ExitBr = dyn_cast<BranchInst>(ExitingBlock->getTerminator());
if (ExitBr == 0) return UnknownValue;
assert(ExitBr->isConditional() && "If unconditional, it can't be in loop!");
if (ExitBr->getSuccessor(0) != L->getHeader() &&
ExitBr->getSuccessor(1) != L->getHeader() &&
ExitBr->getParent() != L->getHeader())
return UnknownValue;
ICmpInst *ExitCond = dyn_cast<ICmpInst>(ExitBr->getCondition());
if (ExitCond == 0 || isa<PointerType>(ExitCond->getOperand(0)->getType()))
return ComputeBackedgeTakenCountExhaustively(L, ExitBr->getCondition(),
ExitBr->getSuccessor(0) == ExitBlock);
ICmpInst::Predicate Cond;
if (ExitBr->getSuccessor(1) == ExitBlock)
Cond = ExitCond->getPredicate();
else
Cond = ExitCond->getInversePredicate();
if (LoadInst *LI = dyn_cast<LoadInst>(ExitCond->getOperand(0)))
if (Constant *RHS = dyn_cast<Constant>(ExitCond->getOperand(1))) {
SCEVHandle ItCnt =
ComputeLoadConstantCompareBackedgeTakenCount(LI, RHS, L, Cond);
if (!isa<SCEVCouldNotCompute>(ItCnt)) return ItCnt;
}
SCEVHandle LHS = getSCEV(ExitCond->getOperand(0));
SCEVHandle RHS = getSCEV(ExitCond->getOperand(1));
SCEVHandle Tmp = getSCEVAtScope(LHS, L);
if (!isa<SCEVCouldNotCompute>(Tmp)) LHS = Tmp;
Tmp = getSCEVAtScope(RHS, L);
if (!isa<SCEVCouldNotCompute>(Tmp)) RHS = Tmp;
if (LHS->isLoopInvariant(L) && !RHS->isLoopInvariant(L)) {
std::swap(LHS, RHS);
Cond = ICmpInst::getSwappedPredicate(Cond);
}
if (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS))
if (SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS))
if (AddRec->getLoop() == L) {
ConstantInt *CompVal = RHSC->getValue();
const Type *RealTy = ExitCond->getOperand(0)->getType();
CompVal = dyn_cast<ConstantInt>(
ConstantExpr::getBitCast(CompVal, RealTy));
if (CompVal) {
ConstantRange CompRange(
ICmpInst::makeConstantRange(Cond, CompVal->getValue()));
SCEVHandle Ret = AddRec->getNumIterationsInRange(CompRange, *this);
if (!isa<SCEVCouldNotCompute>(Ret)) return Ret;
}
}
switch (Cond) {
case ICmpInst::ICMP_NE: { SCEVHandle TC = HowFarToZero(getMinusSCEV(LHS, RHS), L);
if (!isa<SCEVCouldNotCompute>(TC)) return TC;
break;
}
case ICmpInst::ICMP_EQ: {
SCEVHandle TC = HowFarToNonZero(getMinusSCEV(LHS, RHS), L);
if (!isa<SCEVCouldNotCompute>(TC)) return TC;
break;
}
case ICmpInst::ICMP_SLT: {
SCEVHandle TC = HowManyLessThans(LHS, RHS, L, true);
if (!isa<SCEVCouldNotCompute>(TC)) return TC;
break;
}
case ICmpInst::ICMP_SGT: {
SCEVHandle TC = HowManyLessThans(getNotSCEV(LHS),
getNotSCEV(RHS), L, true);
if (!isa<SCEVCouldNotCompute>(TC)) return TC;
break;
}
case ICmpInst::ICMP_ULT: {
SCEVHandle TC = HowManyLessThans(LHS, RHS, L, false);
if (!isa<SCEVCouldNotCompute>(TC)) return TC;
break;
}
case ICmpInst::ICMP_UGT: {
SCEVHandle TC = HowManyLessThans(getNotSCEV(LHS),
getNotSCEV(RHS), L, false);
if (!isa<SCEVCouldNotCompute>(TC)) return TC;
break;
}
default:
#if 0
errs() << "ComputeBackedgeTakenCount ";
if (ExitCond->getOperand(0)->getType()->isUnsigned())
errs() << "[unsigned] ";
errs() << *LHS << " "
<< Instruction::getOpcodeName(Instruction::ICmp)
<< " " << *RHS << "\n";
#endif
break;
}
return
ComputeBackedgeTakenCountExhaustively(L, ExitCond,
ExitBr->getSuccessor(0) == ExitBlock);
}
static ConstantInt *
EvaluateConstantChrecAtConstant(const SCEVAddRecExpr *AddRec, ConstantInt *C,
ScalarEvolution &SE) {
SCEVHandle InVal = SE.getConstant(C);
SCEVHandle Val = AddRec->evaluateAtIteration(InVal, SE);
assert(isa<SCEVConstant>(Val) &&
"Evaluation of SCEV at constant didn't fold correctly?");
return cast<SCEVConstant>(Val)->getValue();
}
static Constant *
GetAddressedElementFromGlobal(GlobalVariable *GV,
const std::vector<ConstantInt*> &Indices) {
Constant *Init = GV->getInitializer();
for (unsigned i = 0, e = Indices.size(); i != e; ++i) {
uint64_t Idx = Indices[i]->getZExtValue();
if (ConstantStruct *CS = dyn_cast<ConstantStruct>(Init)) {
assert(Idx < CS->getNumOperands() && "Bad struct index!");
Init = cast<Constant>(CS->getOperand(Idx));
} else if (ConstantArray *CA = dyn_cast<ConstantArray>(Init)) {
if (Idx >= CA->getNumOperands()) return 0; Init = cast<Constant>(CA->getOperand(Idx));
} else if (isa<ConstantAggregateZero>(Init)) {
if (const StructType *STy = dyn_cast<StructType>(Init->getType())) {
assert(Idx < STy->getNumElements() && "Bad struct index!");
Init = Constant::getNullValue(STy->getElementType(Idx));
} else if (const ArrayType *ATy = dyn_cast<ArrayType>(Init->getType())) {
if (Idx >= ATy->getNumElements()) return 0; Init = Constant::getNullValue(ATy->getElementType());
} else {
assert(0 && "Unknown constant aggregate type!");
}
return 0;
} else {
return 0; }
}
return Init;
}
SCEVHandle ScalarEvolution::
ComputeLoadConstantCompareBackedgeTakenCount(LoadInst *LI, Constant *RHS,
const Loop *L,
ICmpInst::Predicate predicate) {
if (LI->isVolatile()) return UnknownValue;
GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(LI->getOperand(0));
if (!GEP) return UnknownValue;
GlobalVariable *GV = dyn_cast<GlobalVariable>(GEP->getOperand(0));
if (!GV || !GV->isConstant() || !GV->hasInitializer() ||
GEP->getNumOperands() < 3 || !isa<Constant>(GEP->getOperand(1)) ||
!cast<Constant>(GEP->getOperand(1))->isNullValue())
return UnknownValue;
Value *VarIdx = 0;
std::vector<ConstantInt*> Indexes;
unsigned VarIdxNum = 0;
for (unsigned i = 2, e = GEP->getNumOperands(); i != e; ++i)
if (ConstantInt *CI = dyn_cast<ConstantInt>(GEP->getOperand(i))) {
Indexes.push_back(CI);
} else if (!isa<ConstantInt>(GEP->getOperand(i))) {
if (VarIdx) return UnknownValue; VarIdx = GEP->getOperand(i);
VarIdxNum = i-2;
Indexes.push_back(0);
}
SCEVHandle Idx = getSCEV(VarIdx);
SCEVHandle Tmp = getSCEVAtScope(Idx, L);
if (!isa<SCEVCouldNotCompute>(Tmp)) Idx = Tmp;
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;
unsigned MaxSteps = MaxBruteForceIterations;
for (unsigned IterationNum = 0; IterationNum != MaxSteps; ++IterationNum) {
ConstantInt *ItCst =
ConstantInt::get(IdxExpr->getType(), IterationNum);
ConstantInt *Val = EvaluateConstantChrecAtConstant(IdxExpr, ItCst, *this);
Indexes[VarIdxNum] = Val;
Constant *Result = GetAddressedElementFromGlobal(GV, Indexes);
if (Result == 0) break;
Result = ConstantExpr::getICmp(predicate, Result, RHS);
if (!isa<ConstantInt>(Result)) break; if (cast<ConstantInt>(Result)->getValue().isMinValue()) {
#if 0
errs() << "\n***\n*** Computed loop count " << *ItCst
<< "\n*** From global " << *GV << "*** BB: " << *L->getHeader()
<< "***\n";
#endif
++NumArrayLenItCounts;
return getConstant(ItCst); }
}
return UnknownValue;
}
static bool CanConstantFold(const Instruction *I) {
if (isa<BinaryOperator>(I) || isa<CmpInst>(I) ||
isa<SelectInst>(I) || isa<CastInst>(I) || isa<GetElementPtrInst>(I))
return true;
if (const CallInst *CI = dyn_cast<CallInst>(I))
if (const Function *F = CI->getCalledFunction())
return canConstantFoldCallTo(F);
return false;
}
static PHINode *getConstantEvolvingPHI(Value *V, const Loop *L) {
Instruction *I = dyn_cast<Instruction>(V);
if (I == 0 || !L->contains(I->getParent())) return 0;
if (PHINode *PN = dyn_cast<PHINode>(I)) {
if (L->getHeader() == I->getParent())
return PN;
else
return 0;
}
if (!CanConstantFold(I)) return 0;
PHINode *PHI = 0;
for (unsigned Op = 0, e = I->getNumOperands(); Op != e; ++Op)
if (!(isa<Constant>(I->getOperand(Op)) ||
isa<GlobalValue>(I->getOperand(Op)))) {
PHINode *P = getConstantEvolvingPHI(I->getOperand(Op), L);
if (P == 0) return 0; if (PHI == 0)
PHI = P;
else if (PHI != P)
return 0; }
return PHI;
}
static Constant *EvaluateExpression(Value *V, Constant *PHIVal) {
if (isa<PHINode>(V)) return PHIVal;
if (Constant *C = dyn_cast<Constant>(V)) return C;
if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) return GV;
Instruction *I = cast<Instruction>(V);
std::vector<Constant*> Operands;
Operands.resize(I->getNumOperands());
for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
Operands[i] = EvaluateExpression(I->getOperand(i), PHIVal);
if (Operands[i] == 0) return 0;
}
if (const CmpInst *CI = dyn_cast<CmpInst>(I))
return ConstantFoldCompareInstOperands(CI->getPredicate(),
&Operands[0], Operands.size());
else
return ConstantFoldInstOperands(I->getOpcode(), I->getType(),
&Operands[0], Operands.size());
}
Constant *ScalarEvolution::
getConstantEvolutionLoopExitValue(PHINode *PN, const APInt& BEs, const Loop *L){
std::map<PHINode*, Constant*>::iterator I =
ConstantEvolutionLoopExitValue.find(PN);
if (I != ConstantEvolutionLoopExitValue.end())
return I->second;
if (BEs.ugt(APInt(BEs.getBitWidth(),MaxBruteForceIterations)))
return ConstantEvolutionLoopExitValue[PN] = 0;
Constant *&RetVal = ConstantEvolutionLoopExitValue[PN];
bool SecondIsBackedge = L->contains(PN->getIncomingBlock(1));
Constant *StartCST =
dyn_cast<Constant>(PN->getIncomingValue(!SecondIsBackedge));
if (StartCST == 0)
return RetVal = 0;
Value *BEValue = PN->getIncomingValue(SecondIsBackedge);
PHINode *PN2 = getConstantEvolvingPHI(BEValue, L);
if (PN2 != PN)
return RetVal = 0;
if (BEs.getActiveBits() >= 32)
return RetVal = 0;
unsigned NumIterations = BEs.getZExtValue(); unsigned IterationNum = 0;
for (Constant *PHIVal = StartCST; ; ++IterationNum) {
if (IterationNum == NumIterations)
return RetVal = PHIVal;
Constant *NextPHI = EvaluateExpression(BEValue, PHIVal);
if (NextPHI == PHIVal)
return RetVal = NextPHI; if (NextPHI == 0)
return 0; PHIVal = NextPHI;
}
}
SCEVHandle ScalarEvolution::
ComputeBackedgeTakenCountExhaustively(const Loop *L, Value *Cond, bool ExitWhen) {
PHINode *PN = getConstantEvolvingPHI(Cond, L);
if (PN == 0) return UnknownValue;
bool SecondIsBackedge = L->contains(PN->getIncomingBlock(1));
Constant *StartCST =
dyn_cast<Constant>(PN->getIncomingValue(!SecondIsBackedge));
if (StartCST == 0) return UnknownValue;
Value *BEValue = PN->getIncomingValue(SecondIsBackedge);
PHINode *PN2 = getConstantEvolvingPHI(BEValue, L);
if (PN2 != PN) return UnknownValue;
unsigned IterationNum = 0;
unsigned MaxIterations = MaxBruteForceIterations; for (Constant *PHIVal = StartCST;
IterationNum != MaxIterations; ++IterationNum) {
ConstantInt *CondVal =
dyn_cast_or_null<ConstantInt>(EvaluateExpression(Cond, PHIVal));
if (!CondVal) return UnknownValue;
if (CondVal->getValue() == uint64_t(ExitWhen)) {
ConstantEvolutionLoopExitValue[PN] = PHIVal;
++NumBruteForceTripCountsComputed;
return getConstant(ConstantInt::get(Type::Int32Ty, IterationNum));
}
Constant *NextPHI = EvaluateExpression(BEValue, PHIVal);
if (NextPHI == 0 || NextPHI == PHIVal)
return UnknownValue; PHIVal = NextPHI;
}
return UnknownValue;
}
SCEVHandle ScalarEvolution::getSCEVAtScope(SCEV *V, const Loop *L) {
if (isa<SCEVConstant>(V)) return V;
if (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) if (PHINode *PN = dyn_cast<PHINode>(I))
if (PN->getParent() == LI->getHeader()) {
SCEVHandle BackedgeTakenCount = getBackedgeTakenCount(LI);
if (SCEVConstant *BTCC =
dyn_cast<SCEVConstant>(BackedgeTakenCount)) {
Constant *RV = getConstantEvolutionLoopExitValue(PN,
BTCC->getValue()->getValue(),
LI);
if (RV) return getUnknown(RV);
}
}
if (CanConstantFold(I)) {
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) {
Value *Op = I->getOperand(i);
if (Constant *C = dyn_cast<Constant>(Op)) {
Operands.push_back(C);
} else {
if (!isa<IntegerType>(Op->getType()) &&
!isa<PointerType>(Op->getType()))
return V;
SCEVHandle OpV = getSCEVAtScope(getSCEV(Op), L);
if (SCEVConstant *SC = dyn_cast<SCEVConstant>(OpV))
Operands.push_back(ConstantExpr::getIntegerCast(SC->getValue(),
Op->getType(),
false));
else if (SCEVUnknown *SU = dyn_cast<SCEVUnknown>(OpV)) {
if (Constant *C = dyn_cast<Constant>(SU->getValue()))
Operands.push_back(ConstantExpr::getIntegerCast(C,
Op->getType(),
false));
else
return V;
} else {
return V;
}
}
}
Constant *C;
if (const CmpInst *CI = dyn_cast<CmpInst>(I))
C = ConstantFoldCompareInstOperands(CI->getPredicate(),
&Operands[0], Operands.size());
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)) {
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;
std::vector<SCEVHandle> 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 getAddExpr(NewOps);
if (isa<SCEVMulExpr>(Comm))
return getMulExpr(NewOps);
if (isa<SCEVSMaxExpr>(Comm))
return getSMaxExpr(NewOps);
if (isa<SCEVUMaxExpr>(Comm))
return getUMaxExpr(NewOps);
assert(0 && "Unknown commutative SCEV type!");
}
}
return Comm;
}
if (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; return getUDivExpr(LHS, RHS);
}
if (SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V)) {
if (!L || !AddRec->getLoop()->contains(L->getHeader())) {
SCEVHandle BackedgeTakenCount = getBackedgeTakenCount(AddRec->getLoop());
if (BackedgeTakenCount == UnknownValue) return UnknownValue;
return AddRec->evaluateAtIteration(BackedgeTakenCount, *this);
}
return UnknownValue;
}
if (SCEVZeroExtendExpr *Cast = dyn_cast<SCEVZeroExtendExpr>(V)) {
SCEVHandle Op = getSCEVAtScope(Cast->getOperand(), L);
if (Op == UnknownValue) return Op;
if (Op == Cast->getOperand())
return Cast; return getZeroExtendExpr(Op, Cast->getType());
}
if (SCEVSignExtendExpr *Cast = dyn_cast<SCEVSignExtendExpr>(V)) {
SCEVHandle Op = getSCEVAtScope(Cast->getOperand(), L);
if (Op == UnknownValue) return Op;
if (Op == Cast->getOperand())
return Cast; return getSignExtendExpr(Op, Cast->getType());
}
if (SCEVTruncateExpr *Cast = dyn_cast<SCEVTruncateExpr>(V)) {
SCEVHandle Op = getSCEVAtScope(Cast->getOperand(), L);
if (Op == UnknownValue) return Op;
if (Op == Cast->getOperand())
return Cast; return getTruncateExpr(Op, Cast->getType());
}
assert(0 && "Unknown SCEV type!");
}
SCEVHandle ScalarEvolution::getSCEVAtScope(Value *V, const Loop *L) {
return getSCEVAtScope(getSCEV(V), L);
}
static SCEVHandle SolveLinEquationWithOverflow(const APInt &A, const APInt &B,
ScalarEvolution &SE) {
uint32_t BW = A.getBitWidth();
assert(BW == B.getBitWidth() && "Bit widths must be the same.");
assert(A != 0 && "A must be non-zero.");
uint32_t Mult2 = A.countTrailingZeros();
if (B.countTrailingZeros() < Mult2)
return SE.getCouldNotCompute();
APInt AD = A.lshr(Mult2).zext(BW + 1); APInt Mod(BW + 1, 0);
Mod.set(BW - Mult2); APInt I = AD.multiplicativeInverse(Mod);
APInt Result = (I * B.lshr(Mult2).zext(BW + 1)).urem(Mod);
return SE.getConstant(Result.trunc(BW));
}
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));
if (!LC || !MC || !NC) {
SCEV *CNC = SE.getCouldNotCompute();
return std::make_pair(CNC, CNC);
}
uint32_t BitWidth = LC->getValue()->getValue().getBitWidth();
const APInt &L = LC->getValue()->getValue();
const APInt &M = MC->getValue()->getValue();
const APInt &N = NC->getValue()->getValue();
APInt Two(BitWidth, 2);
APInt Four(BitWidth, 4);
{
using namespace APIntOps;
const APInt& C = L;
APInt B(M);
B -= sdiv(N,Two);
APInt A(N.sdiv(Two));
APInt SqrtTerm(B);
SqrtTerm *= B;
SqrtTerm -= Four * (A * C);
APInt SqrtVal(SqrtTerm.sqrt());
APInt NegB(-B);
APInt TwoA( A << 1 );
if (TwoA.isMinValue()) {
SCEV *CNC = SE.getCouldNotCompute();
return std::make_pair(CNC, CNC);
}
ConstantInt *Solution1 = ConstantInt::get((NegB + SqrtVal).sdiv(TwoA));
ConstantInt *Solution2 = ConstantInt::get((NegB - SqrtVal).sdiv(TwoA));
return std::make_pair(SE.getConstant(Solution1),
SE.getConstant(Solution2));
} }
SCEVHandle ScalarEvolution::HowFarToZero(SCEV *V, const Loop *L) {
if (SCEVConstant *C = dyn_cast<SCEVConstant>(V)) {
if (C->getValue()->isZero()) return C;
return UnknownValue; }
SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V);
if (!AddRec || AddRec->getLoop() != L)
return UnknownValue;
if (AddRec->isAffine()) {
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 (StepC->getValue()->equalsInt(1)) return getNegativeSCEV(Start); if (StepC->getValue()->isAllOnesValue()) return Start;
if (SCEVConstant *StartC = dyn_cast<SCEVConstant>(Start))
return SolveLinEquationWithOverflow(StepC->getValue()->getValue(),
-StartC->getValue()->getValue(),
*this);
}
} else if (AddRec->isQuadratic() && AddRec->getType()->isInteger()) {
std::pair<SCEVHandle,SCEVHandle> Roots = SolveQuadraticEquation(AddRec,
*this);
SCEVConstant *R1 = dyn_cast<SCEVConstant>(Roots.first);
SCEVConstant *R2 = dyn_cast<SCEVConstant>(Roots.second);
if (R1) {
#if 0
errs() << "HFTZ: " << *V << " - sol#1: " << *R1
<< " sol#2: " << *R2 << "\n";
#endif
if (ConstantInt *CB =
dyn_cast<ConstantInt>(ConstantExpr::getICmp(ICmpInst::ICMP_ULT,
R1->getValue(), R2->getValue()))) {
if (CB->getZExtValue() == false)
std::swap(R1, R2);
SCEVHandle Val = AddRec->evaluateAtIteration(R1, *this);
if (Val->isZero())
return R1; }
}
}
return UnknownValue;
}
SCEVHandle ScalarEvolution::HowFarToNonZero(SCEV *V, const Loop *L) {
if (SCEVConstant *C = dyn_cast<SCEVConstant>(V)) {
if (!C->getValue()->isNullValue())
return getIntegerSCEV(0, C->getType());
return UnknownValue; }
return UnknownValue;
}
BasicBlock *
ScalarEvolution::getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB) {
if (BasicBlock *Pred = BB->getSinglePredecessor())
return Pred;
if (Loop *L = LI->getLoopFor(BB))
return L->getLoopPreheader();
return 0;
}
bool ScalarEvolution::isLoopGuardedByCond(const Loop *L,
ICmpInst::Predicate Pred,
SCEV *LHS, SCEV *RHS) {
BasicBlock *Preheader = L->getLoopPreheader();
BasicBlock *PreheaderDest = L->getHeader();
for (; Preheader;
PreheaderDest = Preheader,
Preheader = getPredecessorWithUniqueSuccessorForBB(Preheader)) {
BranchInst *LoopEntryPredicate =
dyn_cast<BranchInst>(Preheader->getTerminator());
if (!LoopEntryPredicate ||
LoopEntryPredicate->isUnconditional())
continue;
ICmpInst *ICI = dyn_cast<ICmpInst>(LoopEntryPredicate->getCondition());
if (!ICI) continue;
Value *PreCondLHS = ICI->getOperand(0);
Value *PreCondRHS = ICI->getOperand(1);
ICmpInst::Predicate Cond;
if (LoopEntryPredicate->getSuccessor(0) == PreheaderDest)
Cond = ICI->getPredicate();
else
Cond = ICI->getInversePredicate();
if (Cond == Pred)
; else if (!ICmpInst::isTrueWhenEqual(Cond) && Pred == ICmpInst::ICMP_NE)
; else
switch (Cond) {
case ICmpInst::ICMP_UGT:
if (Pred == ICmpInst::ICMP_ULT) {
std::swap(PreCondLHS, PreCondRHS);
Cond = ICmpInst::ICMP_ULT;
break;
}
continue;
case ICmpInst::ICMP_SGT:
if (Pred == ICmpInst::ICMP_SLT) {
std::swap(PreCondLHS, PreCondRHS);
Cond = ICmpInst::ICMP_SLT;
break;
}
continue;
case ICmpInst::ICMP_NE:
if (!ICmpInst::isTrueWhenEqual(Pred))
if (ConstantInt *CI = dyn_cast<ConstantInt>(PreCondRHS)) {
const APInt &A = CI->getValue();
switch (Pred) {
case ICmpInst::ICMP_SLT:
if (A.isMaxSignedValue()) break;
continue;
case ICmpInst::ICMP_SGT:
if (A.isMinSignedValue()) break;
continue;
case ICmpInst::ICMP_ULT:
if (A.isMaxValue()) break;
continue;
case ICmpInst::ICMP_UGT:
if (A.isMinValue()) break;
continue;
default:
continue;
}
Cond = ICmpInst::ICMP_NE;
if (isa<SCEVConstant>(LHS))
std::swap(PreCondLHS, PreCondRHS);
break;
}
continue;
default:
continue;
}
if (!PreCondLHS->getType()->isInteger()) continue;
SCEVHandle PreCondLHSSCEV = getSCEV(PreCondLHS);
SCEVHandle PreCondRHSSCEV = getSCEV(PreCondRHS);
if ((LHS == PreCondLHSSCEV && RHS == PreCondRHSSCEV) ||
(LHS == getNotSCEV(PreCondRHSSCEV) &&
RHS == getNotSCEV(PreCondLHSSCEV)))
return true;
}
return false;
}
SCEVHandle ScalarEvolution::
HowManyLessThans(SCEV *LHS, SCEV *RHS, const Loop *L, bool isSigned) {
if (!RHS->isLoopInvariant(L)) return UnknownValue;
SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS);
if (!AddRec || AddRec->getLoop() != L)
return UnknownValue;
if (AddRec->isAffine()) {
SCEVHandle One = getIntegerSCEV(1, RHS->getType());
if (AddRec->getOperand(1) != One)
return UnknownValue;
SCEVHandle Start = AddRec->getOperand(0);
if (isLoopGuardedByCond(L,
isSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
getMinusSCEV(AddRec->getOperand(0), One), RHS)) {
return getMinusSCEV(RHS, Start);
} else {
SCEVHandle End = isSigned ? getSMaxExpr(RHS, Start)
: getUMaxExpr(RHS, Start);
return getMinusSCEV(End, Start);
}
}
return UnknownValue;
}
SCEVHandle SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range,
ScalarEvolution &SE) const {
if (Range.isFullSet()) return SE.getCouldNotCompute();
if (SCEVConstant *SC = dyn_cast<SCEVConstant>(getStart()))
if (!SC->getValue()->isZero()) {
std::vector<SCEVHandle> 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))
return ShiftedAddRec->getNumIterationsInRange(
Range.subtract(SC->getValue()->getValue()), SE);
return SE.getCouldNotCompute();
}
for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
if (!isa<SCEVConstant>(getOperand(i)))
return SE.getCouldNotCompute();
unsigned BitWidth = SE.getTypeSizeInBits(getType());
if (!Range.contains(APInt(BitWidth, 0)))
return SE.getConstant(ConstantInt::get(getType(),0));
if (isAffine()) {
APInt One(BitWidth,1);
APInt A = cast<SCEVConstant>(getOperand(1))->getValue()->getValue();
APInt End = A.sge(One) ? (Range.getUpper() - One) : Range.getLower();
APInt ExitVal = (End + A).udiv(A);
ConstantInt *ExitValue = ConstantInt::get(ExitVal);
ConstantInt *Val = EvaluateConstantChrecAtConstant(this, ExitValue, SE);
if (Range.contains(Val->getValue()))
return SE.getCouldNotCompute();
assert(Range.contains(
EvaluateConstantChrecAtConstant(this,
ConstantInt::get(ExitVal - One), SE)->getValue()) &&
"Linear scev computation is off in a bad way!");
return SE.getConstant(ExitValue);
} else if (isQuadratic()) {
std::vector<SCEVHandle> NewOps(op_begin(), op_end());
NewOps[0] = SE.getNegativeSCEV(SE.getConstant(Range.getUpper()));
SCEVHandle NewAddRec = SE.getAddRecExpr(NewOps, getLoop());
std::pair<SCEVHandle,SCEVHandle> Roots =
SolveQuadraticEquation(cast<SCEVAddRecExpr>(NewAddRec), SE);
SCEVConstant *R1 = dyn_cast<SCEVConstant>(Roots.first);
SCEVConstant *R2 = dyn_cast<SCEVConstant>(Roots.second);
if (R1) {
if (ConstantInt *CB =
dyn_cast<ConstantInt>(ConstantExpr::getICmp(ICmpInst::ICMP_ULT,
R1->getValue(), R2->getValue()))) {
if (CB->getZExtValue() == false)
std::swap(R1, R2);
ConstantInt *R1Val = EvaluateConstantChrecAtConstant(this,
R1->getValue(),
SE);
if (Range.contains(R1Val->getValue())) {
ConstantInt *NextVal = ConstantInt::get(R1->getValue()->getValue()+1);
R1Val = EvaluateConstantChrecAtConstant(this, NextVal, SE);
if (!Range.contains(R1Val->getValue()))
return SE.getConstant(NextVal);
return SE.getCouldNotCompute(); }
ConstantInt *NextVal = ConstantInt::get(R1->getValue()->getValue()-1);
R1Val = EvaluateConstantChrecAtConstant(this, NextVal, SE);
if (Range.contains(R1Val->getValue()))
return R1;
return SE.getCouldNotCompute(); }
}
}
return SE.getCouldNotCompute();
}
ScalarEvolution::ScalarEvolution()
: FunctionPass(&ID), UnknownValue(new SCEVCouldNotCompute()) {
}
bool ScalarEvolution::runOnFunction(Function &F) {
this->F = &F;
LI = &getAnalysis<LoopInfo>();
TD = getAnalysisIfAvailable<TargetData>();
return false;
}
void ScalarEvolution::releaseMemory() {
Scalars.clear();
BackedgeTakenCounts.clear();
ConstantEvolutionLoopExitValue.clear();
ValuesAtScopes.clear();
}
void ScalarEvolution::getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesAll();
AU.addRequiredTransitive<LoopInfo>();
}
bool ScalarEvolution::hasLoopInvariantBackedgeTakenCount(const Loop *L) {
return !isa<SCEVCouldNotCompute>(getBackedgeTakenCount(L));
}
static void PrintLoopInfo(raw_ostream &OS, ScalarEvolution *SE,
const Loop *L) {
for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
PrintLoopInfo(OS, SE, *I);
OS << "Loop " << L->getHeader()->getName() << ": ";
SmallVector<BasicBlock*, 8> ExitBlocks;
L->getExitBlocks(ExitBlocks);
if (ExitBlocks.size() != 1)
OS << "<multiple exits> ";
if (SE->hasLoopInvariantBackedgeTakenCount(L)) {
OS << "backedge-taken count is " << *SE->getBackedgeTakenCount(L);
} else {
OS << "Unpredictable backedge-taken count. ";
}
OS << "\n";
}
void ScalarEvolution::print(raw_ostream &OS, const Module* ) const {
ScalarEvolution &SE = *const_cast<ScalarEvolution*>(this);
OS << "Classifying expressions for: " << F->getName() << "\n";
for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)
if (I->getType()->isInteger()) {
OS << *I;
OS << " --> ";
SCEVHandle SV = SE.getSCEV(&*I);
SV->print(OS);
OS << "\t\t";
if (const Loop *L = LI->getLoopFor((*I).getParent())) {
OS << "Exits: ";
SCEVHandle ExitValue = SE.getSCEVAtScope(&*I, L->getParentLoop());
if (isa<SCEVCouldNotCompute>(ExitValue)) {
OS << "<<Unknown>>";
} else {
OS << *ExitValue;
}
}
OS << "\n";
}
OS << "Determining loop execution counts for: " << F->getName() << "\n";
for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I)
PrintLoopInfo(OS, &SE, *I);
}
void ScalarEvolution::print(std::ostream &o, const Module *M) const {
raw_os_ostream OS(o);
print(OS, M);
}