ScalarEvolution.cpp [plain text]
#define DEBUG_TYPE "scalar-evolution"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Assembly/Writer.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/GlobalAlias.h"
#include "llvm/IR/GlobalVariable.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Operator.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/ConstantRange.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/GetElementPtrTypeIterator.h"
#include "llvm/Support/InstIterator.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetLibraryInfo.h"
#include <algorithm>
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 cl::opt<bool>
VerifySCEV("verify-scev",
cl::desc("Verify ScalarEvolution's backedge taken counts (slow)"));
INITIALIZE_PASS_BEGIN(ScalarEvolution, "scalar-evolution",
"Scalar Evolution Analysis", false, true)
INITIALIZE_PASS_DEPENDENCY(LoopInfo)
INITIALIZE_PASS_DEPENDENCY(DominatorTree)
INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo)
INITIALIZE_PASS_END(ScalarEvolution, "scalar-evolution",
"Scalar Evolution Analysis", false, true)
char ScalarEvolution::ID = 0;
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void SCEV::dump() const {
print(dbgs());
dbgs() << '\n';
}
#endif
void SCEV::print(raw_ostream &OS) const {
switch (getSCEVType()) {
case scConstant:
WriteAsOperand(OS, cast<SCEVConstant>(this)->getValue(), false);
return;
case scTruncate: {
const SCEVTruncateExpr *Trunc = cast<SCEVTruncateExpr>(this);
const SCEV *Op = Trunc->getOperand();
OS << "(trunc " << *Op->getType() << " " << *Op << " to "
<< *Trunc->getType() << ")";
return;
}
case scZeroExtend: {
const SCEVZeroExtendExpr *ZExt = cast<SCEVZeroExtendExpr>(this);
const SCEV *Op = ZExt->getOperand();
OS << "(zext " << *Op->getType() << " " << *Op << " to "
<< *ZExt->getType() << ")";
return;
}
case scSignExtend: {
const SCEVSignExtendExpr *SExt = cast<SCEVSignExtendExpr>(this);
const SCEV *Op = SExt->getOperand();
OS << "(sext " << *Op->getType() << " " << *Op << " to "
<< *SExt->getType() << ")";
return;
}
case scAddRecExpr: {
const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(this);
OS << "{" << *AR->getOperand(0);
for (unsigned i = 1, e = AR->getNumOperands(); i != e; ++i)
OS << ",+," << *AR->getOperand(i);
OS << "}<";
if (AR->getNoWrapFlags(FlagNUW))
OS << "nuw><";
if (AR->getNoWrapFlags(FlagNSW))
OS << "nsw><";
if (AR->getNoWrapFlags(FlagNW) &&
!AR->getNoWrapFlags((NoWrapFlags)(FlagNUW | FlagNSW)))
OS << "nw><";
WriteAsOperand(OS, AR->getLoop()->getHeader(), false);
OS << ">";
return;
}
case scAddExpr:
case scMulExpr:
case scUMaxExpr:
case scSMaxExpr: {
const SCEVNAryExpr *NAry = cast<SCEVNAryExpr>(this);
const char *OpStr = 0;
switch (NAry->getSCEVType()) {
case scAddExpr: OpStr = " + "; break;
case scMulExpr: OpStr = " * "; break;
case scUMaxExpr: OpStr = " umax "; break;
case scSMaxExpr: OpStr = " smax "; break;
}
OS << "(";
for (SCEVNAryExpr::op_iterator I = NAry->op_begin(), E = NAry->op_end();
I != E; ++I) {
OS << **I;
if (llvm::next(I) != E)
OS << OpStr;
}
OS << ")";
switch (NAry->getSCEVType()) {
case scAddExpr:
case scMulExpr:
if (NAry->getNoWrapFlags(FlagNUW))
OS << "<nuw>";
if (NAry->getNoWrapFlags(FlagNSW))
OS << "<nsw>";
}
return;
}
case scUDivExpr: {
const SCEVUDivExpr *UDiv = cast<SCEVUDivExpr>(this);
OS << "(" << *UDiv->getLHS() << " /u " << *UDiv->getRHS() << ")";
return;
}
case scUnknown: {
const SCEVUnknown *U = cast<SCEVUnknown>(this);
Type *AllocTy;
if (U->isSizeOf(AllocTy)) {
OS << "sizeof(" << *AllocTy << ")";
return;
}
if (U->isAlignOf(AllocTy)) {
OS << "alignof(" << *AllocTy << ")";
return;
}
Type *CTy;
Constant *FieldNo;
if (U->isOffsetOf(CTy, FieldNo)) {
OS << "offsetof(" << *CTy << ", ";
WriteAsOperand(OS, FieldNo, false);
OS << ")";
return;
}
WriteAsOperand(OS, U->getValue(), false);
return;
}
case scCouldNotCompute:
OS << "***COULDNOTCOMPUTE***";
return;
default: break;
}
llvm_unreachable("Unknown SCEV kind!");
}
Type *SCEV::getType() const {
switch (getSCEVType()) {
case scConstant:
return cast<SCEVConstant>(this)->getType();
case scTruncate:
case scZeroExtend:
case scSignExtend:
return cast<SCEVCastExpr>(this)->getType();
case scAddRecExpr:
case scMulExpr:
case scUMaxExpr:
case scSMaxExpr:
return cast<SCEVNAryExpr>(this)->getType();
case scAddExpr:
return cast<SCEVAddExpr>(this)->getType();
case scUDivExpr:
return cast<SCEVUDivExpr>(this)->getType();
case scUnknown:
return cast<SCEVUnknown>(this)->getType();
case scCouldNotCompute:
llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
default:
llvm_unreachable("Unknown SCEV kind!");
}
}
bool SCEV::isZero() const {
if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(this))
return SC->getValue()->isZero();
return false;
}
bool SCEV::isOne() const {
if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(this))
return SC->getValue()->isOne();
return false;
}
bool SCEV::isAllOnesValue() const {
if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(this))
return SC->getValue()->isAllOnesValue();
return false;
}
bool SCEV::isNonConstantNegative() const {
const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(this);
if (!Mul) return false;
const SCEVConstant *SC = dyn_cast<SCEVConstant>(Mul->getOperand(0));
if (!SC) return false;
return SC->getValue()->getValue().isNegative();
}
SCEVCouldNotCompute::SCEVCouldNotCompute() :
SCEV(FoldingSetNodeIDRef(), scCouldNotCompute) {}
bool SCEVCouldNotCompute::classof(const SCEV *S) {
return S->getSCEVType() == scCouldNotCompute;
}
const SCEV *ScalarEvolution::getConstant(ConstantInt *V) {
FoldingSetNodeID ID;
ID.AddInteger(scConstant);
ID.AddPointer(V);
void *IP = 0;
if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
SCEV *S = new (SCEVAllocator) SCEVConstant(ID.Intern(SCEVAllocator), V);
UniqueSCEVs.InsertNode(S, IP);
return S;
}
const SCEV *ScalarEvolution::getConstant(const APInt& Val) {
return getConstant(ConstantInt::get(getContext(), Val));
}
const SCEV *
ScalarEvolution::getConstant(Type *Ty, uint64_t V, bool isSigned) {
IntegerType *ITy = cast<IntegerType>(getEffectiveSCEVType(Ty));
return getConstant(ConstantInt::get(ITy, V, isSigned));
}
SCEVCastExpr::SCEVCastExpr(const FoldingSetNodeIDRef ID,
unsigned SCEVTy, const SCEV *op, Type *ty)
: SCEV(ID, SCEVTy), Op(op), Ty(ty) {}
SCEVTruncateExpr::SCEVTruncateExpr(const FoldingSetNodeIDRef ID,
const SCEV *op, Type *ty)
: SCEVCastExpr(ID, scTruncate, op, ty) {
assert((Op->getType()->isIntegerTy() || Op->getType()->isPointerTy()) &&
(Ty->isIntegerTy() || Ty->isPointerTy()) &&
"Cannot truncate non-integer value!");
}
SCEVZeroExtendExpr::SCEVZeroExtendExpr(const FoldingSetNodeIDRef ID,
const SCEV *op, Type *ty)
: SCEVCastExpr(ID, scZeroExtend, op, ty) {
assert((Op->getType()->isIntegerTy() || Op->getType()->isPointerTy()) &&
(Ty->isIntegerTy() || Ty->isPointerTy()) &&
"Cannot zero extend non-integer value!");
}
SCEVSignExtendExpr::SCEVSignExtendExpr(const FoldingSetNodeIDRef ID,
const SCEV *op, Type *ty)
: SCEVCastExpr(ID, scSignExtend, op, ty) {
assert((Op->getType()->isIntegerTy() || Op->getType()->isPointerTy()) &&
(Ty->isIntegerTy() || Ty->isPointerTy()) &&
"Cannot sign extend non-integer value!");
}
void SCEVUnknown::deleted() {
SE->forgetMemoizedResults(this);
SE->UniqueSCEVs.RemoveNode(this);
setValPtr(0);
}
void SCEVUnknown::allUsesReplacedWith(Value *New) {
SE->forgetMemoizedResults(this);
SE->UniqueSCEVs.RemoveNode(this);
setValPtr(New);
}
bool SCEVUnknown::isSizeOf(Type *&AllocTy) const {
if (ConstantExpr *VCE = dyn_cast<ConstantExpr>(getValue()))
if (VCE->getOpcode() == Instruction::PtrToInt)
if (ConstantExpr *CE = dyn_cast<ConstantExpr>(VCE->getOperand(0)))
if (CE->getOpcode() == Instruction::GetElementPtr &&
CE->getOperand(0)->isNullValue() &&
CE->getNumOperands() == 2)
if (ConstantInt *CI = dyn_cast<ConstantInt>(CE->getOperand(1)))
if (CI->isOne()) {
AllocTy = cast<PointerType>(CE->getOperand(0)->getType())
->getElementType();
return true;
}
return false;
}
bool SCEVUnknown::isAlignOf(Type *&AllocTy) const {
if (ConstantExpr *VCE = dyn_cast<ConstantExpr>(getValue()))
if (VCE->getOpcode() == Instruction::PtrToInt)
if (ConstantExpr *CE = dyn_cast<ConstantExpr>(VCE->getOperand(0)))
if (CE->getOpcode() == Instruction::GetElementPtr &&
CE->getOperand(0)->isNullValue()) {
Type *Ty =
cast<PointerType>(CE->getOperand(0)->getType())->getElementType();
if (StructType *STy = dyn_cast<StructType>(Ty))
if (!STy->isPacked() &&
CE->getNumOperands() == 3 &&
CE->getOperand(1)->isNullValue()) {
if (ConstantInt *CI = dyn_cast<ConstantInt>(CE->getOperand(2)))
if (CI->isOne() &&
STy->getNumElements() == 2 &&
STy->getElementType(0)->isIntegerTy(1)) {
AllocTy = STy->getElementType(1);
return true;
}
}
}
return false;
}
bool SCEVUnknown::isOffsetOf(Type *&CTy, Constant *&FieldNo) const {
if (ConstantExpr *VCE = dyn_cast<ConstantExpr>(getValue()))
if (VCE->getOpcode() == Instruction::PtrToInt)
if (ConstantExpr *CE = dyn_cast<ConstantExpr>(VCE->getOperand(0)))
if (CE->getOpcode() == Instruction::GetElementPtr &&
CE->getNumOperands() == 3 &&
CE->getOperand(0)->isNullValue() &&
CE->getOperand(1)->isNullValue()) {
Type *Ty =
cast<PointerType>(CE->getOperand(0)->getType())->getElementType();
if (Ty->isStructTy() || Ty->isArrayTy()) {
CTy = Ty;
FieldNo = CE->getOperand(2);
return true;
}
}
return false;
}
namespace {
class SCEVComplexityCompare {
const LoopInfo *const LI;
public:
explicit SCEVComplexityCompare(const LoopInfo *li) : LI(li) {}
bool operator()(const SCEV *LHS, const SCEV *RHS) const {
return compare(LHS, RHS) < 0;
}
int compare(const SCEV *LHS, const SCEV *RHS) const {
if (LHS == RHS)
return 0;
unsigned LType = LHS->getSCEVType(), RType = RHS->getSCEVType();
if (LType != RType)
return (int)LType - (int)RType;
switch (LType) {
case scUnknown: {
const SCEVUnknown *LU = cast<SCEVUnknown>(LHS);
const SCEVUnknown *RU = cast<SCEVUnknown>(RHS);
const Value *LV = LU->getValue(), *RV = RU->getValue();
bool LIsPointer = LV->getType()->isPointerTy(),
RIsPointer = RV->getType()->isPointerTy();
if (LIsPointer != RIsPointer)
return (int)LIsPointer - (int)RIsPointer;
unsigned LID = LV->getValueID(),
RID = RV->getValueID();
if (LID != RID)
return (int)LID - (int)RID;
if (const Argument *LA = dyn_cast<Argument>(LV)) {
const Argument *RA = cast<Argument>(RV);
unsigned LArgNo = LA->getArgNo(), RArgNo = RA->getArgNo();
return (int)LArgNo - (int)RArgNo;
}
if (const Instruction *LInst = dyn_cast<Instruction>(LV)) {
const Instruction *RInst = cast<Instruction>(RV);
const BasicBlock *LParent = LInst->getParent(),
*RParent = RInst->getParent();
if (LParent != RParent) {
unsigned LDepth = LI->getLoopDepth(LParent),
RDepth = LI->getLoopDepth(RParent);
if (LDepth != RDepth)
return (int)LDepth - (int)RDepth;
}
unsigned LNumOps = LInst->getNumOperands(),
RNumOps = RInst->getNumOperands();
return (int)LNumOps - (int)RNumOps;
}
return 0;
}
case scConstant: {
const SCEVConstant *LC = cast<SCEVConstant>(LHS);
const SCEVConstant *RC = cast<SCEVConstant>(RHS);
const APInt &LA = LC->getValue()->getValue();
const APInt &RA = RC->getValue()->getValue();
unsigned LBitWidth = LA.getBitWidth(), RBitWidth = RA.getBitWidth();
if (LBitWidth != RBitWidth)
return (int)LBitWidth - (int)RBitWidth;
return LA.ult(RA) ? -1 : 1;
}
case scAddRecExpr: {
const SCEVAddRecExpr *LA = cast<SCEVAddRecExpr>(LHS);
const SCEVAddRecExpr *RA = cast<SCEVAddRecExpr>(RHS);
const Loop *LLoop = LA->getLoop(), *RLoop = RA->getLoop();
if (LLoop != RLoop) {
unsigned LDepth = LLoop->getLoopDepth(),
RDepth = RLoop->getLoopDepth();
if (LDepth != RDepth)
return (int)LDepth - (int)RDepth;
}
unsigned LNumOps = LA->getNumOperands(), RNumOps = RA->getNumOperands();
if (LNumOps != RNumOps)
return (int)LNumOps - (int)RNumOps;
for (unsigned i = 0; i != LNumOps; ++i) {
long X = compare(LA->getOperand(i), RA->getOperand(i));
if (X != 0)
return X;
}
return 0;
}
case scAddExpr:
case scMulExpr:
case scSMaxExpr:
case scUMaxExpr: {
const SCEVNAryExpr *LC = cast<SCEVNAryExpr>(LHS);
const SCEVNAryExpr *RC = cast<SCEVNAryExpr>(RHS);
unsigned LNumOps = LC->getNumOperands(), RNumOps = RC->getNumOperands();
for (unsigned i = 0; i != LNumOps; ++i) {
if (i >= RNumOps)
return 1;
long X = compare(LC->getOperand(i), RC->getOperand(i));
if (X != 0)
return X;
}
return (int)LNumOps - (int)RNumOps;
}
case scUDivExpr: {
const SCEVUDivExpr *LC = cast<SCEVUDivExpr>(LHS);
const SCEVUDivExpr *RC = cast<SCEVUDivExpr>(RHS);
long X = compare(LC->getLHS(), RC->getLHS());
if (X != 0)
return X;
return compare(LC->getRHS(), RC->getRHS());
}
case scTruncate:
case scZeroExtend:
case scSignExtend: {
const SCEVCastExpr *LC = cast<SCEVCastExpr>(LHS);
const SCEVCastExpr *RC = cast<SCEVCastExpr>(RHS);
return compare(LC->getOperand(), RC->getOperand());
}
default:
llvm_unreachable("Unknown SCEV kind!");
}
}
};
}
static void GroupByComplexity(SmallVectorImpl<const SCEV *> &Ops,
LoopInfo *LI) {
if (Ops.size() < 2) return; if (Ops.size() == 2) {
const SCEV *&LHS = Ops[0], *&RHS = Ops[1];
if (SCEVComplexityCompare(LI)(RHS, LHS))
std::swap(LHS, RHS);
return;
}
std::stable_sort(Ops.begin(), Ops.end(), SCEVComplexityCompare(LI));
for (unsigned i = 0, e = Ops.size(); i != e-2; ++i) {
const 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 const SCEV *BinomialCoefficient(const SCEV *It, unsigned K,
ScalarEvolution &SE,
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);
IntegerType *CalculationTy = IntegerType::get(SE.getContext(),
CalculationBits);
const SCEV *Dividend = SE.getTruncateOrZeroExtend(It, CalculationTy);
for (unsigned i = 1; i != K; ++i) {
const SCEV *S = SE.getMinusSCEV(It, SE.getConstant(It->getType(), i));
Dividend = SE.getMulExpr(Dividend,
SE.getTruncateOrZeroExtend(S, CalculationTy));
}
const SCEV *DivResult = SE.getUDivExpr(Dividend, SE.getConstant(DivFactor));
return SE.getMulExpr(SE.getConstant(MultiplyFactor),
SE.getTruncateOrZeroExtend(DivResult, ResultTy));
}
const SCEV *SCEVAddRecExpr::evaluateAtIteration(const SCEV *It,
ScalarEvolution &SE) const {
const SCEV *Result = getStart();
for (unsigned i = 1, e = getNumOperands(); i != e; ++i) {
const SCEV *Coeff = BinomialCoefficient(It, i, SE, getType());
if (isa<SCEVCouldNotCompute>(Coeff))
return Coeff;
Result = SE.getAddExpr(Result, SE.getMulExpr(getOperand(i), Coeff));
}
return Result;
}
const SCEV *ScalarEvolution::getTruncateExpr(const SCEV *Op,
Type *Ty) {
assert(getTypeSizeInBits(Op->getType()) > getTypeSizeInBits(Ty) &&
"This is not a truncating conversion!");
assert(isSCEVable(Ty) &&
"This is not a conversion to a SCEVable type!");
Ty = getEffectiveSCEVType(Ty);
FoldingSetNodeID ID;
ID.AddInteger(scTruncate);
ID.AddPointer(Op);
ID.AddPointer(Ty);
void *IP = 0;
if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op))
return getConstant(
cast<ConstantInt>(ConstantExpr::getTrunc(SC->getValue(), Ty)));
if (const SCEVTruncateExpr *ST = dyn_cast<SCEVTruncateExpr>(Op))
return getTruncateExpr(ST->getOperand(), Ty);
if (const SCEVSignExtendExpr *SS = dyn_cast<SCEVSignExtendExpr>(Op))
return getTruncateOrSignExtend(SS->getOperand(), Ty);
if (const SCEVZeroExtendExpr *SZ = dyn_cast<SCEVZeroExtendExpr>(Op))
return getTruncateOrZeroExtend(SZ->getOperand(), Ty);
if (const SCEVAddExpr *SA = dyn_cast<SCEVAddExpr>(Op)) {
SmallVector<const SCEV *, 4> Operands;
bool hasTrunc = false;
for (unsigned i = 0, e = SA->getNumOperands(); i != e && !hasTrunc; ++i) {
const SCEV *S = getTruncateExpr(SA->getOperand(i), Ty);
hasTrunc = isa<SCEVTruncateExpr>(S);
Operands.push_back(S);
}
if (!hasTrunc)
return getAddExpr(Operands);
UniqueSCEVs.FindNodeOrInsertPos(ID, IP); }
if (const SCEVMulExpr *SM = dyn_cast<SCEVMulExpr>(Op)) {
SmallVector<const SCEV *, 4> Operands;
bool hasTrunc = false;
for (unsigned i = 0, e = SM->getNumOperands(); i != e && !hasTrunc; ++i) {
const SCEV *S = getTruncateExpr(SM->getOperand(i), Ty);
hasTrunc = isa<SCEVTruncateExpr>(S);
Operands.push_back(S);
}
if (!hasTrunc)
return getMulExpr(Operands);
UniqueSCEVs.FindNodeOrInsertPos(ID, IP); }
if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Op)) {
SmallVector<const SCEV *, 4> Operands;
for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i)
Operands.push_back(getTruncateExpr(AddRec->getOperand(i), Ty));
return getAddRecExpr(Operands, AddRec->getLoop(), SCEV::FlagAnyWrap);
}
SCEV *S = new (SCEVAllocator) SCEVTruncateExpr(ID.Intern(SCEVAllocator),
Op, Ty);
UniqueSCEVs.InsertNode(S, IP);
return S;
}
const SCEV *ScalarEvolution::getZeroExtendExpr(const SCEV *Op,
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);
if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op))
return getConstant(
cast<ConstantInt>(ConstantExpr::getZExt(SC->getValue(), Ty)));
if (const SCEVZeroExtendExpr *SZ = dyn_cast<SCEVZeroExtendExpr>(Op))
return getZeroExtendExpr(SZ->getOperand(), Ty);
FoldingSetNodeID ID;
ID.AddInteger(scZeroExtend);
ID.AddPointer(Op);
ID.AddPointer(Ty);
void *IP = 0;
if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
if (const SCEVTruncateExpr *ST = dyn_cast<SCEVTruncateExpr>(Op)) {
const SCEV *X = ST->getOperand();
ConstantRange CR = getUnsignedRange(X);
unsigned TruncBits = getTypeSizeInBits(ST->getType());
unsigned NewBits = getTypeSizeInBits(Ty);
if (CR.truncate(TruncBits).zeroExtend(NewBits).contains(
CR.zextOrTrunc(NewBits)))
return getTruncateOrZeroExtend(X, Ty);
}
if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Op))
if (AR->isAffine()) {
const SCEV *Start = AR->getStart();
const SCEV *Step = AR->getStepRecurrence(*this);
unsigned BitWidth = getTypeSizeInBits(AR->getType());
const Loop *L = AR->getLoop();
if (AR->getNoWrapFlags(SCEV::FlagNUW))
return getAddRecExpr(getZeroExtendExpr(Start, Ty),
getZeroExtendExpr(Step, Ty),
L, AR->getNoWrapFlags());
const SCEV *MaxBECount = getMaxBackedgeTakenCount(L);
if (!isa<SCEVCouldNotCompute>(MaxBECount)) {
const SCEV *CastedMaxBECount =
getTruncateOrZeroExtend(MaxBECount, Start->getType());
const SCEV *RecastedMaxBECount =
getTruncateOrZeroExtend(CastedMaxBECount, MaxBECount->getType());
if (MaxBECount == RecastedMaxBECount) {
Type *WideTy = IntegerType::get(getContext(), BitWidth * 2);
const SCEV *ZMul = getMulExpr(CastedMaxBECount, Step);
const SCEV *ZAdd = getZeroExtendExpr(getAddExpr(Start, ZMul), WideTy);
const SCEV *WideStart = getZeroExtendExpr(Start, WideTy);
const SCEV *WideMaxBECount =
getZeroExtendExpr(CastedMaxBECount, WideTy);
const SCEV *OperandExtendedAdd =
getAddExpr(WideStart,
getMulExpr(WideMaxBECount,
getZeroExtendExpr(Step, WideTy)));
if (ZAdd == OperandExtendedAdd) {
const_cast<SCEVAddRecExpr *>(AR)->setNoWrapFlags(SCEV::FlagNUW);
return getAddRecExpr(getZeroExtendExpr(Start, Ty),
getZeroExtendExpr(Step, Ty),
L, AR->getNoWrapFlags());
}
OperandExtendedAdd =
getAddExpr(WideStart,
getMulExpr(WideMaxBECount,
getSignExtendExpr(Step, WideTy)));
if (ZAdd == OperandExtendedAdd) {
const_cast<SCEVAddRecExpr *>(AR)->setNoWrapFlags(SCEV::FlagNW);
return getAddRecExpr(getZeroExtendExpr(Start, Ty),
getSignExtendExpr(Step, Ty),
L, AR->getNoWrapFlags());
}
}
if (isKnownPositive(Step)) {
const SCEV *N = getConstant(APInt::getMinValue(BitWidth) -
getUnsignedRange(Step).getUnsignedMax());
if (isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_ULT, AR, N) ||
(isLoopEntryGuardedByCond(L, ICmpInst::ICMP_ULT, Start, N) &&
isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_ULT,
AR->getPostIncExpr(*this), N))) {
const_cast<SCEVAddRecExpr *>(AR)->setNoWrapFlags(SCEV::FlagNUW);
return getAddRecExpr(getZeroExtendExpr(Start, Ty),
getZeroExtendExpr(Step, Ty),
L, AR->getNoWrapFlags());
}
} else if (isKnownNegative(Step)) {
const SCEV *N = getConstant(APInt::getMaxValue(BitWidth) -
getSignedRange(Step).getSignedMin());
if (isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_UGT, AR, N) ||
(isLoopEntryGuardedByCond(L, ICmpInst::ICMP_UGT, Start, N) &&
isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_UGT,
AR->getPostIncExpr(*this), N))) {
const_cast<SCEVAddRecExpr *>(AR)->setNoWrapFlags(SCEV::FlagNW);
return getAddRecExpr(getZeroExtendExpr(Start, Ty),
getSignExtendExpr(Step, Ty),
L, AR->getNoWrapFlags());
}
}
}
}
if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
SCEV *S = new (SCEVAllocator) SCEVZeroExtendExpr(ID.Intern(SCEVAllocator),
Op, Ty);
UniqueSCEVs.InsertNode(S, IP);
return S;
}
static const SCEV *getOverflowLimitForStep(const SCEV *Step,
ICmpInst::Predicate *Pred,
ScalarEvolution *SE) {
unsigned BitWidth = SE->getTypeSizeInBits(Step->getType());
if (SE->isKnownPositive(Step)) {
*Pred = ICmpInst::ICMP_SLT;
return SE->getConstant(APInt::getSignedMinValue(BitWidth) -
SE->getSignedRange(Step).getSignedMax());
}
if (SE->isKnownNegative(Step)) {
*Pred = ICmpInst::ICMP_SGT;
return SE->getConstant(APInt::getSignedMaxValue(BitWidth) -
SE->getSignedRange(Step).getSignedMin());
}
return 0;
}
static const SCEV *getPreStartForSignExtend(const SCEVAddRecExpr *AR,
Type *Ty,
ScalarEvolution *SE) {
const Loop *L = AR->getLoop();
const SCEV *Start = AR->getStart();
const SCEV *Step = AR->getStepRecurrence(*SE);
const SCEVAddExpr *SA = dyn_cast<SCEVAddExpr>(Start);
if (!SA)
return 0;
SmallVector<const SCEV *, 4> DiffOps;
for (SCEVAddExpr::op_iterator I = SA->op_begin(), E = SA->op_end();
I != E; ++I) {
if (*I != Step)
DiffOps.push_back(*I);
}
if (DiffOps.size() == SA->getNumOperands())
return 0;
const SCEV *PreStart = SE->getAddExpr(DiffOps, SA->getNoWrapFlags());
const SCEVAddRecExpr *PreAR = dyn_cast<SCEVAddRecExpr>(
SE->getAddRecExpr(PreStart, Step, L, SCEV::FlagAnyWrap));
if (PreAR && PreAR->getNoWrapFlags(SCEV::FlagNSW))
return PreStart;
unsigned BitWidth = SE->getTypeSizeInBits(AR->getType());
Type *WideTy = IntegerType::get(SE->getContext(), BitWidth * 2);
const SCEV *OperandExtendedStart =
SE->getAddExpr(SE->getSignExtendExpr(PreStart, WideTy),
SE->getSignExtendExpr(Step, WideTy));
if (SE->getSignExtendExpr(Start, WideTy) == OperandExtendedStart) {
if (PreAR)
const_cast<SCEVAddRecExpr *>(PreAR)->setNoWrapFlags(SCEV::FlagNSW);
DEBUG(dbgs() << "SCEV: untested prestart overflow check\n");
return PreStart;
}
ICmpInst::Predicate Pred;
const SCEV *OverflowLimit = getOverflowLimitForStep(Step, &Pred, SE);
if (OverflowLimit &&
SE->isLoopEntryGuardedByCond(L, Pred, PreStart, OverflowLimit)) {
return PreStart;
}
return 0;
}
static const SCEV *getSignExtendAddRecStart(const SCEVAddRecExpr *AR,
Type *Ty,
ScalarEvolution *SE) {
const SCEV *PreStart = getPreStartForSignExtend(AR, Ty, SE);
if (!PreStart)
return SE->getSignExtendExpr(AR->getStart(), Ty);
return SE->getAddExpr(SE->getSignExtendExpr(AR->getStepRecurrence(*SE), Ty),
SE->getSignExtendExpr(PreStart, Ty));
}
const SCEV *ScalarEvolution::getSignExtendExpr(const SCEV *Op,
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);
if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op))
return getConstant(
cast<ConstantInt>(ConstantExpr::getSExt(SC->getValue(), Ty)));
if (const SCEVSignExtendExpr *SS = dyn_cast<SCEVSignExtendExpr>(Op))
return getSignExtendExpr(SS->getOperand(), Ty);
if (const SCEVZeroExtendExpr *SZ = dyn_cast<SCEVZeroExtendExpr>(Op))
return getZeroExtendExpr(SZ->getOperand(), Ty);
FoldingSetNodeID ID;
ID.AddInteger(scSignExtend);
ID.AddPointer(Op);
ID.AddPointer(Ty);
void *IP = 0;
if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
if (isKnownNonNegative(Op))
return getZeroExtendExpr(Op, Ty);
if (const SCEVTruncateExpr *ST = dyn_cast<SCEVTruncateExpr>(Op)) {
const SCEV *X = ST->getOperand();
ConstantRange CR = getSignedRange(X);
unsigned TruncBits = getTypeSizeInBits(ST->getType());
unsigned NewBits = getTypeSizeInBits(Ty);
if (CR.truncate(TruncBits).signExtend(NewBits).contains(
CR.sextOrTrunc(NewBits)))
return getTruncateOrSignExtend(X, Ty);
}
if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Op))
if (AR->isAffine()) {
const SCEV *Start = AR->getStart();
const SCEV *Step = AR->getStepRecurrence(*this);
unsigned BitWidth = getTypeSizeInBits(AR->getType());
const Loop *L = AR->getLoop();
if (AR->getNoWrapFlags(SCEV::FlagNSW))
return getAddRecExpr(getSignExtendAddRecStart(AR, Ty, this),
getSignExtendExpr(Step, Ty),
L, SCEV::FlagNSW);
const SCEV *MaxBECount = getMaxBackedgeTakenCount(L);
if (!isa<SCEVCouldNotCompute>(MaxBECount)) {
const SCEV *CastedMaxBECount =
getTruncateOrZeroExtend(MaxBECount, Start->getType());
const SCEV *RecastedMaxBECount =
getTruncateOrZeroExtend(CastedMaxBECount, MaxBECount->getType());
if (MaxBECount == RecastedMaxBECount) {
Type *WideTy = IntegerType::get(getContext(), BitWidth * 2);
const SCEV *SMul = getMulExpr(CastedMaxBECount, Step);
const SCEV *SAdd = getSignExtendExpr(getAddExpr(Start, SMul), WideTy);
const SCEV *WideStart = getSignExtendExpr(Start, WideTy);
const SCEV *WideMaxBECount =
getZeroExtendExpr(CastedMaxBECount, WideTy);
const SCEV *OperandExtendedAdd =
getAddExpr(WideStart,
getMulExpr(WideMaxBECount,
getSignExtendExpr(Step, WideTy)));
if (SAdd == OperandExtendedAdd) {
const_cast<SCEVAddRecExpr *>(AR)->setNoWrapFlags(SCEV::FlagNSW);
return getAddRecExpr(getSignExtendAddRecStart(AR, Ty, this),
getSignExtendExpr(Step, Ty),
L, AR->getNoWrapFlags());
}
OperandExtendedAdd =
getAddExpr(WideStart,
getMulExpr(WideMaxBECount,
getZeroExtendExpr(Step, WideTy)));
if (SAdd == OperandExtendedAdd) {
const_cast<SCEVAddRecExpr *>(AR)->setNoWrapFlags(SCEV::FlagNSW);
return getAddRecExpr(getSignExtendAddRecStart(AR, Ty, this),
getZeroExtendExpr(Step, Ty),
L, AR->getNoWrapFlags());
}
}
ICmpInst::Predicate Pred;
const SCEV *OverflowLimit = getOverflowLimitForStep(Step, &Pred, this);
if (OverflowLimit &&
(isLoopBackedgeGuardedByCond(L, Pred, AR, OverflowLimit) ||
(isLoopEntryGuardedByCond(L, Pred, Start, OverflowLimit) &&
isLoopBackedgeGuardedByCond(L, Pred, AR->getPostIncExpr(*this),
OverflowLimit)))) {
const_cast<SCEVAddRecExpr *>(AR)->setNoWrapFlags(SCEV::FlagNSW);
return getAddRecExpr(getSignExtendAddRecStart(AR, Ty, this),
getSignExtendExpr(Step, Ty),
L, AR->getNoWrapFlags());
}
}
}
if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
SCEV *S = new (SCEVAllocator) SCEVSignExtendExpr(ID.Intern(SCEVAllocator),
Op, Ty);
UniqueSCEVs.InsertNode(S, IP);
return S;
}
const SCEV *ScalarEvolution::getAnyExtendExpr(const SCEV *Op,
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);
if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op))
if (SC->getValue()->getValue().isNegative())
return getSignExtendExpr(Op, Ty);
if (const SCEVTruncateExpr *T = dyn_cast<SCEVTruncateExpr>(Op)) {
const SCEV *NewOp = T->getOperand();
if (getTypeSizeInBits(NewOp->getType()) < getTypeSizeInBits(Ty))
return getAnyExtendExpr(NewOp, Ty);
return getTruncateOrNoop(NewOp, Ty);
}
const SCEV *ZExt = getZeroExtendExpr(Op, Ty);
if (!isa<SCEVZeroExtendExpr>(ZExt))
return ZExt;
const SCEV *SExt = getSignExtendExpr(Op, Ty);
if (!isa<SCEVSignExtendExpr>(SExt))
return SExt;
if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Op)) {
SmallVector<const SCEV *, 4> Ops;
for (SCEVAddRecExpr::op_iterator I = AR->op_begin(), E = AR->op_end();
I != E; ++I)
Ops.push_back(getAnyExtendExpr(*I, Ty));
return getAddRecExpr(Ops, AR->getLoop(), SCEV::FlagNW);
}
if (isa<SCEVSMaxExpr>(Op))
return SExt;
return ZExt;
}
static bool
CollectAddOperandsWithScales(DenseMap<const SCEV *, APInt> &M,
SmallVector<const SCEV *, 8> &NewOps,
APInt &AccumulatedConstant,
const SCEV *const *Ops, size_t NumOperands,
const APInt &Scale,
ScalarEvolution &SE) {
bool Interesting = false;
unsigned i = 0;
while (const SCEVConstant *C = dyn_cast<SCEVConstant>(Ops[i])) {
++i;
if (Scale != 1 || AccumulatedConstant != 0 || C->getValue()->isZero())
Interesting = true;
AccumulatedConstant += Scale * C->getValue()->getValue();
}
for (; i != NumOperands; ++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))) {
const SCEVAddExpr *Add = cast<SCEVAddExpr>(Mul->getOperand(1));
Interesting |=
CollectAddOperandsWithScales(M, NewOps, AccumulatedConstant,
Add->op_begin(), Add->getNumOperands(),
NewScale, SE);
} else {
SmallVector<const SCEV *, 4> MulOps(Mul->op_begin()+1, Mul->op_end());
const SCEV *Key = SE.getMulExpr(MulOps);
std::pair<DenseMap<const SCEV *, APInt>::iterator, bool> Pair =
M.insert(std::make_pair(Key, NewScale));
if (Pair.second) {
NewOps.push_back(Pair.first->first);
} else {
Pair.first->second += NewScale;
Interesting = true;
}
}
} else {
std::pair<DenseMap<const SCEV *, APInt>::iterator, bool> Pair =
M.insert(std::make_pair(Ops[i], Scale));
if (Pair.second) {
NewOps.push_back(Pair.first->first);
} else {
Pair.first->second += Scale;
Interesting = true;
}
}
}
return Interesting;
}
namespace {
struct APIntCompare {
bool operator()(const APInt &LHS, const APInt &RHS) const {
return LHS.ult(RHS);
}
};
}
const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl<const SCEV *> &Ops,
SCEV::NoWrapFlags Flags) {
assert(!(Flags & ~(SCEV::FlagNUW | SCEV::FlagNSW)) &&
"only nuw or nsw allowed");
assert(!Ops.empty() && "Cannot get empty add!");
if (Ops.size() == 1) return Ops[0];
#ifndef NDEBUG
Type *ETy = getEffectiveSCEVType(Ops[0]->getType());
for (unsigned i = 1, e = Ops.size(); i != e; ++i)
assert(getEffectiveSCEVType(Ops[i]->getType()) == ETy &&
"SCEVAddExpr operand types don't match!");
#endif
int SignOrUnsignMask = SCEV::FlagNUW | SCEV::FlagNSW;
SCEV::NoWrapFlags SignOrUnsignWrap = maskFlags(Flags, SignOrUnsignMask);
if (SignOrUnsignWrap && (SignOrUnsignWrap != SignOrUnsignMask)) {
bool All = true;
for (SmallVectorImpl<const SCEV *>::const_iterator I = Ops.begin(),
E = Ops.end(); I != E; ++I)
if (!isKnownNonNegative(*I)) {
All = false;
break;
}
if (All) Flags = setFlags(Flags, (SCEV::NoWrapFlags)SignOrUnsignMask);
}
GroupByComplexity(Ops, LI);
unsigned Idx = 0;
if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
++Idx;
assert(Idx < Ops.size());
while (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
Ops[0] = getConstant(LHSC->getValue()->getValue() +
RHSC->getValue()->getValue());
if (Ops.size() == 2) return Ops[0];
Ops.erase(Ops.begin()+1); LHSC = cast<SCEVConstant>(Ops[0]);
}
if (LHSC->getValue()->isZero()) {
Ops.erase(Ops.begin());
--Idx;
}
if (Ops.size() == 1) return Ops[0];
}
Type *Ty = Ops[0]->getType();
bool FoundMatch = false;
for (unsigned i = 0, e = Ops.size(); i != e-1; ++i)
if (Ops[i] == Ops[i+1]) { unsigned Count = 2;
while (i+Count != e && Ops[i+Count] == Ops[i])
++Count;
const SCEV *Scale = getConstant(Ty, Count);
const SCEV *Mul = getMulExpr(Scale, Ops[i]);
if (Ops.size() == Count)
return Mul;
Ops[i] = Mul;
Ops.erase(Ops.begin()+i+1, Ops.begin()+i+Count);
--i; e -= Count - 1;
FoundMatch = true;
}
if (FoundMatch)
return getAddExpr(Ops, Flags);
for (; Idx < Ops.size() && isa<SCEVTruncateExpr>(Ops[Idx]); ++Idx) {
const SCEVTruncateExpr *Trunc = cast<SCEVTruncateExpr>(Ops[Idx]);
Type *DstType = Trunc->getType();
Type *SrcType = Trunc->getOperand()->getType();
SmallVector<const SCEV *, 8> LargeOps;
bool Ok = true;
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])) {
LargeOps.push_back(getAnyExtendExpr(C, SrcType));
} else if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(Ops[i])) {
SmallVector<const SCEV *, 8> LargeMulOps;
for (unsigned j = 0, f = M->getNumOperands(); j != f && Ok; ++j) {
if (const SCEVTruncateExpr *T =
dyn_cast<SCEVTruncateExpr>(M->getOperand(j))) {
if (T->getOperand()->getType() != SrcType) {
Ok = false;
break;
}
LargeMulOps.push_back(T->getOperand());
} else if (const SCEVConstant *C =
dyn_cast<SCEVConstant>(M->getOperand(j))) {
LargeMulOps.push_back(getAnyExtendExpr(C, SrcType));
} else {
Ok = false;
break;
}
}
if (Ok)
LargeOps.push_back(getMulExpr(LargeMulOps));
} else {
Ok = false;
break;
}
}
if (Ok) {
const SCEV *Fold = getAddExpr(LargeOps, Flags);
if (isa<SCEVConstant>(Fold) || isa<SCEVUnknown>(Fold))
return getTruncateExpr(Fold, DstType);
}
}
while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scAddExpr)
++Idx;
if (Idx < Ops.size()) {
bool DeletedAdd = false;
while (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[Idx])) {
Ops.erase(Ops.begin()+Idx);
Ops.append(Add->op_begin(), Add->op_end());
DeletedAdd = true;
}
if (DeletedAdd)
return getAddExpr(Ops);
}
while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scMulExpr)
++Idx;
if (Idx < Ops.size() && isa<SCEVMulExpr>(Ops[Idx])) {
uint64_t BitWidth = getTypeSizeInBits(Ty);
DenseMap<const SCEV *, APInt> M;
SmallVector<const SCEV *, 8> NewOps;
APInt AccumulatedConstant(BitWidth, 0);
if (CollectAddOperandsWithScales(M, NewOps, AccumulatedConstant,
Ops.data(), Ops.size(),
APInt(BitWidth, 1), *this)) {
std::map<APInt, SmallVector<const SCEV *, 4>, APIntCompare> MulOpLists;
for (SmallVector<const SCEV *, 8>::const_iterator I = NewOps.begin(),
E = NewOps.end(); I != E; ++I)
MulOpLists[M.find(*I)->second].push_back(*I);
Ops.clear();
if (AccumulatedConstant != 0)
Ops.push_back(getConstant(AccumulatedConstant));
for (std::map<APInt, SmallVector<const SCEV *, 4>, APIntCompare>::iterator
I = MulOpLists.begin(), E = MulOpLists.end(); I != E; ++I)
if (I->first != 0)
Ops.push_back(getMulExpr(getConstant(I->first),
getAddExpr(I->second)));
if (Ops.empty())
return getConstant(Ty, 0);
if (Ops.size() == 1)
return Ops[0];
return getAddExpr(Ops);
}
}
for (; Idx < Ops.size() && isa<SCEVMulExpr>(Ops[Idx]); ++Idx) {
const SCEVMulExpr *Mul = cast<SCEVMulExpr>(Ops[Idx]);
for (unsigned MulOp = 0, e = Mul->getNumOperands(); MulOp != e; ++MulOp) {
const SCEV *MulOpSCEV = Mul->getOperand(MulOp);
if (isa<SCEVConstant>(MulOpSCEV))
continue;
for (unsigned AddOp = 0, e = Ops.size(); AddOp != e; ++AddOp)
if (MulOpSCEV == Ops[AddOp]) {
const SCEV *InnerMul = Mul->getOperand(MulOp == 0);
if (Mul->getNumOperands() != 2) {
SmallVector<const SCEV *, 4> MulOps(Mul->op_begin(),
Mul->op_begin()+MulOp);
MulOps.append(Mul->op_begin()+MulOp+1, Mul->op_end());
InnerMul = getMulExpr(MulOps);
}
const SCEV *One = getConstant(Ty, 1);
const SCEV *AddOne = getAddExpr(One, InnerMul);
const SCEV *OuterMul = getMulExpr(AddOne, MulOpSCEV);
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) {
const SCEVMulExpr *OtherMul = cast<SCEVMulExpr>(Ops[OtherMulIdx]);
for (unsigned OMulOp = 0, e = OtherMul->getNumOperands();
OMulOp != e; ++OMulOp)
if (OtherMul->getOperand(OMulOp) == MulOpSCEV) {
const SCEV *InnerMul1 = Mul->getOperand(MulOp == 0);
if (Mul->getNumOperands() != 2) {
SmallVector<const SCEV *, 4> MulOps(Mul->op_begin(),
Mul->op_begin()+MulOp);
MulOps.append(Mul->op_begin()+MulOp+1, Mul->op_end());
InnerMul1 = getMulExpr(MulOps);
}
const SCEV *InnerMul2 = OtherMul->getOperand(OMulOp == 0);
if (OtherMul->getNumOperands() != 2) {
SmallVector<const SCEV *, 4> MulOps(OtherMul->op_begin(),
OtherMul->op_begin()+OMulOp);
MulOps.append(OtherMul->op_begin()+OMulOp+1, OtherMul->op_end());
InnerMul2 = getMulExpr(MulOps);
}
const SCEV *InnerMulSum = getAddExpr(InnerMul1,InnerMul2);
const SCEV *OuterMul = getMulExpr(MulOpSCEV, InnerMulSum);
if (Ops.size() == 2) return OuterMul;
Ops.erase(Ops.begin()+Idx);
Ops.erase(Ops.begin()+OtherMulIdx-1);
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) {
SmallVector<const SCEV *, 8> LIOps;
const SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(Ops[Idx]);
const Loop *AddRecLoop = AddRec->getLoop();
for (unsigned i = 0, e = Ops.size(); i != e; ++i)
if (isLoopInvariant(Ops[i], AddRecLoop)) {
LIOps.push_back(Ops[i]);
Ops.erase(Ops.begin()+i);
--i; --e;
}
if (!LIOps.empty()) {
LIOps.push_back(AddRec->getStart());
SmallVector<const SCEV *, 4> AddRecOps(AddRec->op_begin(),
AddRec->op_end());
AddRecOps[0] = getAddExpr(LIOps);
Flags = AddRec->getNoWrapFlags(setFlags(Flags, SCEV::FlagNW));
const SCEV *NewRec = getAddRecExpr(AddRecOps, AddRecLoop, Flags);
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 (AddRecLoop == cast<SCEVAddRecExpr>(Ops[OtherIdx])->getLoop()) {
SmallVector<const SCEV *, 4> AddRecOps(AddRec->op_begin(),
AddRec->op_end());
for (; OtherIdx != Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);
++OtherIdx)
if (const SCEVAddRecExpr *OtherAddRec =
dyn_cast<SCEVAddRecExpr>(Ops[OtherIdx]))
if (OtherAddRec->getLoop() == AddRecLoop) {
for (unsigned i = 0, e = OtherAddRec->getNumOperands();
i != e; ++i) {
if (i >= AddRecOps.size()) {
AddRecOps.append(OtherAddRec->op_begin()+i,
OtherAddRec->op_end());
break;
}
AddRecOps[i] = getAddExpr(AddRecOps[i],
OtherAddRec->getOperand(i));
}
Ops.erase(Ops.begin() + OtherIdx); --OtherIdx;
}
Ops[Idx] = getAddRecExpr(AddRecOps, AddRecLoop, SCEV::FlagAnyWrap);
return getAddExpr(Ops);
}
}
FoldingSetNodeID ID;
ID.AddInteger(scAddExpr);
for (unsigned i = 0, e = Ops.size(); i != e; ++i)
ID.AddPointer(Ops[i]);
void *IP = 0;
SCEVAddExpr *S =
static_cast<SCEVAddExpr *>(UniqueSCEVs.FindNodeOrInsertPos(ID, IP));
if (!S) {
const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size());
std::uninitialized_copy(Ops.begin(), Ops.end(), O);
S = new (SCEVAllocator) SCEVAddExpr(ID.Intern(SCEVAllocator),
O, Ops.size());
UniqueSCEVs.InsertNode(S, IP);
}
S->setNoWrapFlags(Flags);
return S;
}
static uint64_t umul_ov(uint64_t i, uint64_t j, bool &Overflow) {
uint64_t k = i*j;
if (j > 1 && k / j != i) Overflow = true;
return k;
}
static uint64_t Choose(uint64_t n, uint64_t k, bool &Overflow) {
if (n == 0 || n == k) return 1;
if (k > n) return 0;
if (k > n/2)
k = n-k;
uint64_t r = 1;
for (uint64_t i = 1; i <= k; ++i) {
r = umul_ov(r, n-(i-1), Overflow);
r /= i;
}
return r;
}
const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV *> &Ops,
SCEV::NoWrapFlags Flags) {
assert(Flags == maskFlags(Flags, SCEV::FlagNUW | SCEV::FlagNSW) &&
"only nuw or nsw allowed");
assert(!Ops.empty() && "Cannot get empty mul!");
if (Ops.size() == 1) return Ops[0];
#ifndef NDEBUG
Type *ETy = getEffectiveSCEVType(Ops[0]->getType());
for (unsigned i = 1, e = Ops.size(); i != e; ++i)
assert(getEffectiveSCEVType(Ops[i]->getType()) == ETy &&
"SCEVMulExpr operand types don't match!");
#endif
int SignOrUnsignMask = SCEV::FlagNUW | SCEV::FlagNSW;
SCEV::NoWrapFlags SignOrUnsignWrap = maskFlags(Flags, SignOrUnsignMask);
if (SignOrUnsignWrap && (SignOrUnsignWrap != SignOrUnsignMask)) {
bool All = true;
for (SmallVectorImpl<const SCEV *>::const_iterator I = Ops.begin(),
E = Ops.end(); I != E; ++I)
if (!isKnownNonNegative(*I)) {
All = false;
break;
}
if (All) Flags = setFlags(Flags, (SCEV::NoWrapFlags)SignOrUnsignMask);
}
GroupByComplexity(Ops, LI);
unsigned Idx = 0;
if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
if (Ops.size() == 2)
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)),
getMulExpr(LHSC, Add->getOperand(1)));
++Idx;
while (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
ConstantInt *Fold = ConstantInt::get(getContext(),
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];
} else if (Ops[0]->isAllOnesValue()) {
if (Ops.size() == 2) {
if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[1])) {
SmallVector<const SCEV *, 4> NewOps;
bool AnyFolded = false;
for (SCEVAddRecExpr::op_iterator I = Add->op_begin(),
E = Add->op_end(); I != E; ++I) {
const SCEV *Mul = getMulExpr(Ops[0], *I);
if (!isa<SCEVMulExpr>(Mul)) AnyFolded = true;
NewOps.push_back(Mul);
}
if (AnyFolded)
return getAddExpr(NewOps);
}
else if (const SCEVAddRecExpr *
AddRec = dyn_cast<SCEVAddRecExpr>(Ops[1])) {
SmallVector<const SCEV *, 4> Operands;
for (SCEVAddRecExpr::op_iterator I = AddRec->op_begin(),
E = AddRec->op_end(); I != E; ++I) {
Operands.push_back(getMulExpr(Ops[0], *I));
}
return getAddRecExpr(Operands, AddRec->getLoop(),
AddRec->getNoWrapFlags(SCEV::FlagNW));
}
}
}
if (Ops.size() == 1)
return Ops[0];
}
while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scMulExpr)
++Idx;
if (Idx < Ops.size()) {
bool DeletedMul = false;
while (const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(Ops[Idx])) {
Ops.erase(Ops.begin()+Idx);
Ops.append(Mul->op_begin(), Mul->op_end());
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) {
SmallVector<const SCEV *, 8> LIOps;
const SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(Ops[Idx]);
const Loop *AddRecLoop = AddRec->getLoop();
for (unsigned i = 0, e = Ops.size(); i != e; ++i)
if (isLoopInvariant(Ops[i], AddRecLoop)) {
LIOps.push_back(Ops[i]);
Ops.erase(Ops.begin()+i);
--i; --e;
}
if (!LIOps.empty()) {
SmallVector<const SCEV *, 4> NewOps;
NewOps.reserve(AddRec->getNumOperands());
const SCEV *Scale = getMulExpr(LIOps);
for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i)
NewOps.push_back(getMulExpr(Scale, AddRec->getOperand(i)));
Flags = AddRec->getNoWrapFlags(clearFlags(Flags, SCEV::FlagNW));
const SCEV *NewRec = getAddRecExpr(NewOps, AddRecLoop, Flags);
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 (AddRecLoop != cast<SCEVAddRecExpr>(Ops[OtherIdx])->getLoop())
continue;
bool OpsModified = false;
for (; OtherIdx != Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);
++OtherIdx) {
const SCEVAddRecExpr *OtherAddRec =
dyn_cast<SCEVAddRecExpr>(Ops[OtherIdx]);
if (!OtherAddRec || OtherAddRec->getLoop() != AddRecLoop)
continue;
bool Overflow = false;
Type *Ty = AddRec->getType();
bool LargerThan64Bits = getTypeSizeInBits(Ty) > 64;
SmallVector<const SCEV*, 7> AddRecOps;
for (int x = 0, xe = AddRec->getNumOperands() +
OtherAddRec->getNumOperands() - 1; x != xe && !Overflow; ++x) {
const SCEV *Term = getConstant(Ty, 0);
for (int y = x, ye = 2*x+1; y != ye && !Overflow; ++y) {
uint64_t Coeff1 = Choose(x, 2*x - y, Overflow);
for (int z = std::max(y-x, y-(int)AddRec->getNumOperands()+1),
ze = std::min(x+1, (int)OtherAddRec->getNumOperands());
z < ze && !Overflow; ++z) {
uint64_t Coeff2 = Choose(2*x - y, x-z, Overflow);
uint64_t Coeff;
if (LargerThan64Bits)
Coeff = umul_ov(Coeff1, Coeff2, Overflow);
else
Coeff = Coeff1*Coeff2;
const SCEV *CoeffTerm = getConstant(Ty, Coeff);
const SCEV *Term1 = AddRec->getOperand(y-z);
const SCEV *Term2 = OtherAddRec->getOperand(z);
Term = getAddExpr(Term, getMulExpr(CoeffTerm, Term1,Term2));
}
}
AddRecOps.push_back(Term);
}
if (!Overflow) {
const SCEV *NewAddRec = getAddRecExpr(AddRecOps, AddRec->getLoop(),
SCEV::FlagAnyWrap);
if (Ops.size() == 2) return NewAddRec;
Ops[Idx] = NewAddRec;
Ops.erase(Ops.begin() + OtherIdx); --OtherIdx;
OpsModified = true;
AddRec = dyn_cast<SCEVAddRecExpr>(NewAddRec);
if (!AddRec)
break;
}
}
if (OpsModified)
return getMulExpr(Ops);
}
}
FoldingSetNodeID ID;
ID.AddInteger(scMulExpr);
for (unsigned i = 0, e = Ops.size(); i != e; ++i)
ID.AddPointer(Ops[i]);
void *IP = 0;
SCEVMulExpr *S =
static_cast<SCEVMulExpr *>(UniqueSCEVs.FindNodeOrInsertPos(ID, IP));
if (!S) {
const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size());
std::uninitialized_copy(Ops.begin(), Ops.end(), O);
S = new (SCEVAllocator) SCEVMulExpr(ID.Intern(SCEVAllocator),
O, Ops.size());
UniqueSCEVs.InsertNode(S, IP);
}
S->setNoWrapFlags(Flags);
return S;
}
const SCEV *ScalarEvolution::getUDivExpr(const SCEV *LHS,
const SCEV *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; if (!RHSC->getValue()->isZero()) {
Type *Ty = LHS->getType();
unsigned LZ = RHSC->getValue()->getValue().countLeadingZeros();
unsigned MaxShiftAmt = getTypeSizeInBits(Ty) - LZ - 1;
if (!RHSC->getValue()->getValue().isPowerOf2())
++MaxShiftAmt;
IntegerType *ExtTy =
IntegerType::get(getContext(), getTypeSizeInBits(Ty) + MaxShiftAmt);
if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(LHS))
if (const SCEVConstant *Step =
dyn_cast<SCEVConstant>(AR->getStepRecurrence(*this))) {
const APInt &StepInt = Step->getValue()->getValue();
const APInt &DivInt = RHSC->getValue()->getValue();
if (!StepInt.urem(DivInt) &&
getZeroExtendExpr(AR, ExtTy) ==
getAddRecExpr(getZeroExtendExpr(AR->getStart(), ExtTy),
getZeroExtendExpr(Step, ExtTy),
AR->getLoop(), SCEV::FlagAnyWrap)) {
SmallVector<const SCEV *, 4> Operands;
for (unsigned i = 0, e = AR->getNumOperands(); i != e; ++i)
Operands.push_back(getUDivExpr(AR->getOperand(i), RHS));
return getAddRecExpr(Operands, AR->getLoop(),
SCEV::FlagNW);
}
const SCEVConstant *StartC = dyn_cast<SCEVConstant>(AR->getStart());
if (StartC && !DivInt.urem(StepInt) &&
getZeroExtendExpr(AR, ExtTy) ==
getAddRecExpr(getZeroExtendExpr(AR->getStart(), ExtTy),
getZeroExtendExpr(Step, ExtTy),
AR->getLoop(), SCEV::FlagAnyWrap)) {
const APInt &StartInt = StartC->getValue()->getValue();
const APInt &StartRem = StartInt.urem(StepInt);
if (StartRem != 0)
LHS = getAddRecExpr(getConstant(StartInt - StartRem), Step,
AR->getLoop(), SCEV::FlagNW);
}
}
if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(LHS)) {
SmallVector<const SCEV *, 4> Operands;
for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i)
Operands.push_back(getZeroExtendExpr(M->getOperand(i), ExtTy));
if (getZeroExtendExpr(M, ExtTy) == getMulExpr(Operands))
for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
const SCEV *Op = M->getOperand(i);
const SCEV *Div = getUDivExpr(Op, RHSC);
if (!isa<SCEVUDivExpr>(Div) && getMulExpr(Div, RHSC) == Op) {
Operands = SmallVector<const SCEV *, 4>(M->op_begin(),
M->op_end());
Operands[i] = Div;
return getMulExpr(Operands);
}
}
}
if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(LHS)) {
SmallVector<const SCEV *, 4> Operands;
for (unsigned i = 0, e = A->getNumOperands(); i != e; ++i)
Operands.push_back(getZeroExtendExpr(A->getOperand(i), ExtTy));
if (getZeroExtendExpr(A, ExtTy) == getAddExpr(Operands)) {
Operands.clear();
for (unsigned i = 0, e = A->getNumOperands(); i != e; ++i) {
const SCEV *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 (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(LHS)) {
Constant *LHSCV = LHSC->getValue();
Constant *RHSCV = RHSC->getValue();
return getConstant(cast<ConstantInt>(ConstantExpr::getUDiv(LHSCV,
RHSCV)));
}
}
}
FoldingSetNodeID ID;
ID.AddInteger(scUDivExpr);
ID.AddPointer(LHS);
ID.AddPointer(RHS);
void *IP = 0;
if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
SCEV *S = new (SCEVAllocator) SCEVUDivExpr(ID.Intern(SCEVAllocator),
LHS, RHS);
UniqueSCEVs.InsertNode(S, IP);
return S;
}
const SCEV *ScalarEvolution::getAddRecExpr(const SCEV *Start, const SCEV *Step,
const Loop *L,
SCEV::NoWrapFlags Flags) {
SmallVector<const SCEV *, 4> Operands;
Operands.push_back(Start);
if (const SCEVAddRecExpr *StepChrec = dyn_cast<SCEVAddRecExpr>(Step))
if (StepChrec->getLoop() == L) {
Operands.append(StepChrec->op_begin(), StepChrec->op_end());
return getAddRecExpr(Operands, L, maskFlags(Flags, SCEV::FlagNW));
}
Operands.push_back(Step);
return getAddRecExpr(Operands, L, Flags);
}
const SCEV *
ScalarEvolution::getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands,
const Loop *L, SCEV::NoWrapFlags Flags) {
if (Operands.size() == 1) return Operands[0];
#ifndef NDEBUG
Type *ETy = getEffectiveSCEVType(Operands[0]->getType());
for (unsigned i = 1, e = Operands.size(); i != e; ++i)
assert(getEffectiveSCEVType(Operands[i]->getType()) == ETy &&
"SCEVAddRecExpr operand types don't match!");
for (unsigned i = 0, e = Operands.size(); i != e; ++i)
assert(isLoopInvariant(Operands[i], L) &&
"SCEVAddRecExpr operand is not loop-invariant!");
#endif
if (Operands.back()->isZero()) {
Operands.pop_back();
return getAddRecExpr(Operands, L, SCEV::FlagAnyWrap); }
int SignOrUnsignMask = SCEV::FlagNUW | SCEV::FlagNSW;
SCEV::NoWrapFlags SignOrUnsignWrap = maskFlags(Flags, SignOrUnsignMask);
if (SignOrUnsignWrap && (SignOrUnsignWrap != SignOrUnsignMask)) {
bool All = true;
for (SmallVectorImpl<const SCEV *>::const_iterator I = Operands.begin(),
E = Operands.end(); I != E; ++I)
if (!isKnownNonNegative(*I)) {
All = false;
break;
}
if (All) Flags = setFlags(Flags, (SCEV::NoWrapFlags)SignOrUnsignMask);
}
if (const SCEVAddRecExpr *NestedAR = dyn_cast<SCEVAddRecExpr>(Operands[0])) {
const Loop *NestedLoop = NestedAR->getLoop();
if (L->contains(NestedLoop) ?
(L->getLoopDepth() < NestedLoop->getLoopDepth()) :
(!NestedLoop->contains(L) &&
DT->dominates(L->getHeader(), NestedLoop->getHeader()))) {
SmallVector<const SCEV *, 4> NestedOperands(NestedAR->op_begin(),
NestedAR->op_end());
Operands[0] = NestedAR->getStart();
bool AllInvariant = true;
for (unsigned i = 0, e = Operands.size(); i != e; ++i)
if (!isLoopInvariant(Operands[i], L)) {
AllInvariant = false;
break;
}
if (AllInvariant) {
SCEV::NoWrapFlags OuterFlags =
maskFlags(Flags, SCEV::FlagNW | NestedAR->getNoWrapFlags());
NestedOperands[0] = getAddRecExpr(Operands, L, OuterFlags);
AllInvariant = true;
for (unsigned i = 0, e = NestedOperands.size(); i != e; ++i)
if (!isLoopInvariant(NestedOperands[i], NestedLoop)) {
AllInvariant = false;
break;
}
if (AllInvariant) {
SCEV::NoWrapFlags InnerFlags =
maskFlags(NestedAR->getNoWrapFlags(), SCEV::FlagNW | Flags);
return getAddRecExpr(NestedOperands, NestedLoop, InnerFlags);
}
}
Operands[0] = NestedAR;
}
}
FoldingSetNodeID ID;
ID.AddInteger(scAddRecExpr);
for (unsigned i = 0, e = Operands.size(); i != e; ++i)
ID.AddPointer(Operands[i]);
ID.AddPointer(L);
void *IP = 0;
SCEVAddRecExpr *S =
static_cast<SCEVAddRecExpr *>(UniqueSCEVs.FindNodeOrInsertPos(ID, IP));
if (!S) {
const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Operands.size());
std::uninitialized_copy(Operands.begin(), Operands.end(), O);
S = new (SCEVAllocator) SCEVAddRecExpr(ID.Intern(SCEVAllocator),
O, Operands.size(), L);
UniqueSCEVs.InsertNode(S, IP);
}
S->setNoWrapFlags(Flags);
return S;
}
const SCEV *ScalarEvolution::getSMaxExpr(const SCEV *LHS,
const SCEV *RHS) {
SmallVector<const SCEV *, 2> Ops;
Ops.push_back(LHS);
Ops.push_back(RHS);
return getSMaxExpr(Ops);
}
const SCEV *
ScalarEvolution::getSMaxExpr(SmallVectorImpl<const SCEV *> &Ops) {
assert(!Ops.empty() && "Cannot get empty smax!");
if (Ops.size() == 1) return Ops[0];
#ifndef NDEBUG
Type *ETy = getEffectiveSCEVType(Ops[0]->getType());
for (unsigned i = 1, e = Ops.size(); i != e; ++i)
assert(getEffectiveSCEVType(Ops[i]->getType()) == ETy &&
"SCEVSMaxExpr operand types don't match!");
#endif
GroupByComplexity(Ops, LI);
unsigned Idx = 0;
if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
++Idx;
assert(Idx < Ops.size());
while (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
ConstantInt *Fold = ConstantInt::get(getContext(),
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;
} else if (cast<SCEVConstant>(Ops[0])->getValue()->isMaxValue(true)) {
return Ops[0];
}
if (Ops.size() == 1) return Ops[0];
}
while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scSMaxExpr)
++Idx;
if (Idx < Ops.size()) {
bool DeletedSMax = false;
while (const SCEVSMaxExpr *SMax = dyn_cast<SCEVSMaxExpr>(Ops[Idx])) {
Ops.erase(Ops.begin()+Idx);
Ops.append(SMax->op_begin(), SMax->op_end());
DeletedSMax = true;
}
if (DeletedSMax)
return getSMaxExpr(Ops);
}
for (unsigned i = 0, e = Ops.size()-1; i != e; ++i)
if (Ops[i] == Ops[i+1] ||
isKnownPredicate(ICmpInst::ICMP_SGE, Ops[i], Ops[i+1])) {
Ops.erase(Ops.begin()+i+1, Ops.begin()+i+2);
--i; --e;
} else if (isKnownPredicate(ICmpInst::ICMP_SLE, 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!");
FoldingSetNodeID ID;
ID.AddInteger(scSMaxExpr);
for (unsigned i = 0, e = Ops.size(); i != e; ++i)
ID.AddPointer(Ops[i]);
void *IP = 0;
if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size());
std::uninitialized_copy(Ops.begin(), Ops.end(), O);
SCEV *S = new (SCEVAllocator) SCEVSMaxExpr(ID.Intern(SCEVAllocator),
O, Ops.size());
UniqueSCEVs.InsertNode(S, IP);
return S;
}
const SCEV *ScalarEvolution::getUMaxExpr(const SCEV *LHS,
const SCEV *RHS) {
SmallVector<const SCEV *, 2> Ops;
Ops.push_back(LHS);
Ops.push_back(RHS);
return getUMaxExpr(Ops);
}
const SCEV *
ScalarEvolution::getUMaxExpr(SmallVectorImpl<const SCEV *> &Ops) {
assert(!Ops.empty() && "Cannot get empty umax!");
if (Ops.size() == 1) return Ops[0];
#ifndef NDEBUG
Type *ETy = getEffectiveSCEVType(Ops[0]->getType());
for (unsigned i = 1, e = Ops.size(); i != e; ++i)
assert(getEffectiveSCEVType(Ops[i]->getType()) == ETy &&
"SCEVUMaxExpr operand types don't match!");
#endif
GroupByComplexity(Ops, LI);
unsigned Idx = 0;
if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
++Idx;
assert(Idx < Ops.size());
while (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
ConstantInt *Fold = ConstantInt::get(getContext(),
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;
} else if (cast<SCEVConstant>(Ops[0])->getValue()->isMaxValue(false)) {
return Ops[0];
}
if (Ops.size() == 1) return Ops[0];
}
while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scUMaxExpr)
++Idx;
if (Idx < Ops.size()) {
bool DeletedUMax = false;
while (const SCEVUMaxExpr *UMax = dyn_cast<SCEVUMaxExpr>(Ops[Idx])) {
Ops.erase(Ops.begin()+Idx);
Ops.append(UMax->op_begin(), UMax->op_end());
DeletedUMax = true;
}
if (DeletedUMax)
return getUMaxExpr(Ops);
}
for (unsigned i = 0, e = Ops.size()-1; i != e; ++i)
if (Ops[i] == Ops[i+1] ||
isKnownPredicate(ICmpInst::ICMP_UGE, Ops[i], Ops[i+1])) {
Ops.erase(Ops.begin()+i+1, Ops.begin()+i+2);
--i; --e;
} else if (isKnownPredicate(ICmpInst::ICMP_ULE, 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!");
FoldingSetNodeID ID;
ID.AddInteger(scUMaxExpr);
for (unsigned i = 0, e = Ops.size(); i != e; ++i)
ID.AddPointer(Ops[i]);
void *IP = 0;
if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size());
std::uninitialized_copy(Ops.begin(), Ops.end(), O);
SCEV *S = new (SCEVAllocator) SCEVUMaxExpr(ID.Intern(SCEVAllocator),
O, Ops.size());
UniqueSCEVs.InsertNode(S, IP);
return S;
}
const SCEV *ScalarEvolution::getSMinExpr(const SCEV *LHS,
const SCEV *RHS) {
return getNotSCEV(getSMaxExpr(getNotSCEV(LHS), getNotSCEV(RHS)));
}
const SCEV *ScalarEvolution::getUMinExpr(const SCEV *LHS,
const SCEV *RHS) {
return getNotSCEV(getUMaxExpr(getNotSCEV(LHS), getNotSCEV(RHS)));
}
const SCEV *ScalarEvolution::getSizeOfExpr(Type *AllocTy) {
if (TD)
return getConstant(TD->getIntPtrType(getContext()),
TD->getTypeAllocSize(AllocTy));
Constant *C = ConstantExpr::getSizeOf(AllocTy);
if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C))
if (Constant *Folded = ConstantFoldConstantExpression(CE, TD, TLI))
C = Folded;
Type *Ty = getEffectiveSCEVType(PointerType::getUnqual(AllocTy));
return getTruncateOrZeroExtend(getSCEV(C), Ty);
}
const SCEV *ScalarEvolution::getAlignOfExpr(Type *AllocTy) {
Constant *C = ConstantExpr::getAlignOf(AllocTy);
if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C))
if (Constant *Folded = ConstantFoldConstantExpression(CE, TD, TLI))
C = Folded;
Type *Ty = getEffectiveSCEVType(PointerType::getUnqual(AllocTy));
return getTruncateOrZeroExtend(getSCEV(C), Ty);
}
const SCEV *ScalarEvolution::getOffsetOfExpr(StructType *STy,
unsigned FieldNo) {
if (TD)
return getConstant(TD->getIntPtrType(getContext()),
TD->getStructLayout(STy)->getElementOffset(FieldNo));
Constant *C = ConstantExpr::getOffsetOf(STy, FieldNo);
if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C))
if (Constant *Folded = ConstantFoldConstantExpression(CE, TD, TLI))
C = Folded;
Type *Ty = getEffectiveSCEVType(PointerType::getUnqual(STy));
return getTruncateOrZeroExtend(getSCEV(C), Ty);
}
const SCEV *ScalarEvolution::getOffsetOfExpr(Type *CTy,
Constant *FieldNo) {
Constant *C = ConstantExpr::getOffsetOf(CTy, FieldNo);
if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C))
if (Constant *Folded = ConstantFoldConstantExpression(CE, TD, TLI))
C = Folded;
Type *Ty = getEffectiveSCEVType(PointerType::getUnqual(CTy));
return getTruncateOrZeroExtend(getSCEV(C), Ty);
}
const SCEV *ScalarEvolution::getUnknown(Value *V) {
FoldingSetNodeID ID;
ID.AddInteger(scUnknown);
ID.AddPointer(V);
void *IP = 0;
if (SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) {
assert(cast<SCEVUnknown>(S)->getValue() == V &&
"Stale SCEVUnknown in uniquing map!");
return S;
}
SCEV *S = new (SCEVAllocator) SCEVUnknown(ID.Intern(SCEVAllocator), V, this,
FirstUnknown);
FirstUnknown = cast<SCEVUnknown>(S);
UniqueSCEVs.InsertNode(S, IP);
return S;
}
bool ScalarEvolution::isSCEVable(Type *Ty) const {
return Ty->isIntegerTy() || Ty->isPointerTy();
}
uint64_t ScalarEvolution::getTypeSizeInBits(Type *Ty) const {
assert(isSCEVable(Ty) && "Type is not SCEVable!");
if (TD)
return TD->getTypeSizeInBits(Ty);
if (Ty->isIntegerTy())
return Ty->getPrimitiveSizeInBits();
assert(Ty->isPointerTy() && "isSCEVable permitted a non-SCEVable type!");
return 64;
}
Type *ScalarEvolution::getEffectiveSCEVType(Type *Ty) const {
assert(isSCEVable(Ty) && "Type is not SCEVable!");
if (Ty->isIntegerTy())
return Ty;
assert(Ty->isPointerTy() && "Unexpected non-pointer non-integer type!");
if (TD) return TD->getIntPtrType(getContext());
return Type::getInt64Ty(getContext());
}
const SCEV *ScalarEvolution::getCouldNotCompute() {
return &CouldNotCompute;
}
namespace {
struct FindInvalidSCEVUnknown {
bool FindOne;
FindInvalidSCEVUnknown() { FindOne = false; }
bool follow(const SCEV *S) {
switch (S->getSCEVType()) {
case scConstant:
return false;
case scUnknown:
if(!cast<SCEVUnknown>(S)->getValue())
FindOne = true;
return false;
default:
return true;
}
}
bool isDone() const { return FindOne; }
};
}
bool ScalarEvolution::checkValidity(const SCEV *S) const {
FindInvalidSCEVUnknown F;
SCEVTraversal<FindInvalidSCEVUnknown> ST(F);
ST.visitAll(S);
return !F.FindOne;
}
const SCEV *ScalarEvolution::getSCEV(Value *V) {
assert(isSCEVable(V->getType()) && "Value is not SCEVable!");
ValueExprMapType::iterator I = ValueExprMap.find_as(V);
if (I != ValueExprMap.end()) {
const SCEV *S = I->second;
if(checkValidity(S))
return S;
else
ValueExprMap.erase(I);
}
const SCEV *S = createSCEV(V);
ValueExprMap.insert(std::make_pair(SCEVCallbackVH(V, this), S));
return S;
}
const SCEV *ScalarEvolution::getNegativeSCEV(const SCEV *V) {
if (const SCEVConstant *VC = dyn_cast<SCEVConstant>(V))
return getConstant(
cast<ConstantInt>(ConstantExpr::getNeg(VC->getValue())));
Type *Ty = V->getType();
Ty = getEffectiveSCEVType(Ty);
return getMulExpr(V,
getConstant(cast<ConstantInt>(Constant::getAllOnesValue(Ty))));
}
const SCEV *ScalarEvolution::getNotSCEV(const SCEV *V) {
if (const SCEVConstant *VC = dyn_cast<SCEVConstant>(V))
return getConstant(
cast<ConstantInt>(ConstantExpr::getNot(VC->getValue())));
Type *Ty = V->getType();
Ty = getEffectiveSCEVType(Ty);
const SCEV *AllOnes =
getConstant(cast<ConstantInt>(Constant::getAllOnesValue(Ty)));
return getMinusSCEV(AllOnes, V);
}
const SCEV *ScalarEvolution::getMinusSCEV(const SCEV *LHS, const SCEV *RHS,
SCEV::NoWrapFlags Flags) {
assert(!maskFlags(Flags, SCEV::FlagNUW) && "subtraction does not have NUW");
if (LHS == RHS)
return getConstant(LHS->getType(), 0);
return getAddExpr(LHS, getNegativeSCEV(RHS), Flags);
}
const SCEV *
ScalarEvolution::getTruncateOrZeroExtend(const SCEV *V, Type *Ty) {
Type *SrcTy = V->getType();
assert((SrcTy->isIntegerTy() || SrcTy->isPointerTy()) &&
(Ty->isIntegerTy() || Ty->isPointerTy()) &&
"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);
}
const SCEV *
ScalarEvolution::getTruncateOrSignExtend(const SCEV *V,
Type *Ty) {
Type *SrcTy = V->getType();
assert((SrcTy->isIntegerTy() || SrcTy->isPointerTy()) &&
(Ty->isIntegerTy() || Ty->isPointerTy()) &&
"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);
}
const SCEV *
ScalarEvolution::getNoopOrZeroExtend(const SCEV *V, Type *Ty) {
Type *SrcTy = V->getType();
assert((SrcTy->isIntegerTy() || SrcTy->isPointerTy()) &&
(Ty->isIntegerTy() || Ty->isPointerTy()) &&
"Cannot noop or zero extend with non-integer arguments!");
assert(getTypeSizeInBits(SrcTy) <= getTypeSizeInBits(Ty) &&
"getNoopOrZeroExtend cannot truncate!");
if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty))
return V; return getZeroExtendExpr(V, Ty);
}
const SCEV *
ScalarEvolution::getNoopOrSignExtend(const SCEV *V, Type *Ty) {
Type *SrcTy = V->getType();
assert((SrcTy->isIntegerTy() || SrcTy->isPointerTy()) &&
(Ty->isIntegerTy() || Ty->isPointerTy()) &&
"Cannot noop or sign extend with non-integer arguments!");
assert(getTypeSizeInBits(SrcTy) <= getTypeSizeInBits(Ty) &&
"getNoopOrSignExtend cannot truncate!");
if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty))
return V; return getSignExtendExpr(V, Ty);
}
const SCEV *
ScalarEvolution::getNoopOrAnyExtend(const SCEV *V, Type *Ty) {
Type *SrcTy = V->getType();
assert((SrcTy->isIntegerTy() || SrcTy->isPointerTy()) &&
(Ty->isIntegerTy() || Ty->isPointerTy()) &&
"Cannot noop or any extend with non-integer arguments!");
assert(getTypeSizeInBits(SrcTy) <= getTypeSizeInBits(Ty) &&
"getNoopOrAnyExtend cannot truncate!");
if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty))
return V; return getAnyExtendExpr(V, Ty);
}
const SCEV *
ScalarEvolution::getTruncateOrNoop(const SCEV *V, Type *Ty) {
Type *SrcTy = V->getType();
assert((SrcTy->isIntegerTy() || SrcTy->isPointerTy()) &&
(Ty->isIntegerTy() || Ty->isPointerTy()) &&
"Cannot truncate or noop with non-integer arguments!");
assert(getTypeSizeInBits(SrcTy) >= getTypeSizeInBits(Ty) &&
"getTruncateOrNoop cannot extend!");
if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty))
return V; return getTruncateExpr(V, Ty);
}
const SCEV *ScalarEvolution::getUMaxFromMismatchedTypes(const SCEV *LHS,
const SCEV *RHS) {
const SCEV *PromotedLHS = LHS;
const SCEV *PromotedRHS = RHS;
if (getTypeSizeInBits(LHS->getType()) > getTypeSizeInBits(RHS->getType()))
PromotedRHS = getZeroExtendExpr(RHS, LHS->getType());
else
PromotedLHS = getNoopOrZeroExtend(LHS, RHS->getType());
return getUMaxExpr(PromotedLHS, PromotedRHS);
}
const SCEV *ScalarEvolution::getUMinFromMismatchedTypes(const SCEV *LHS,
const SCEV *RHS) {
const SCEV *PromotedLHS = LHS;
const SCEV *PromotedRHS = RHS;
if (getTypeSizeInBits(LHS->getType()) > getTypeSizeInBits(RHS->getType()))
PromotedRHS = getZeroExtendExpr(RHS, LHS->getType());
else
PromotedLHS = getNoopOrZeroExtend(LHS, RHS->getType());
return getUMinExpr(PromotedLHS, PromotedRHS);
}
const SCEV *ScalarEvolution::getPointerBase(const SCEV *V) {
if (!V->getType()->isPointerTy())
return V;
if (const SCEVCastExpr *Cast = dyn_cast<SCEVCastExpr>(V)) {
return getPointerBase(Cast->getOperand());
}
else if (const SCEVNAryExpr *NAry = dyn_cast<SCEVNAryExpr>(V)) {
const SCEV *PtrOp = 0;
for (SCEVNAryExpr::op_iterator I = NAry->op_begin(), E = NAry->op_end();
I != E; ++I) {
if ((*I)->getType()->isPointerTy()) {
if (PtrOp)
return V;
PtrOp = *I;
}
}
if (!PtrOp)
return V;
return getPointerBase(PtrOp);
}
return V;
}
static void
PushDefUseChildren(Instruction *I,
SmallVectorImpl<Instruction *> &Worklist) {
for (Value::use_iterator UI = I->use_begin(), UE = I->use_end();
UI != UE; ++UI)
Worklist.push_back(cast<Instruction>(*UI));
}
void
ScalarEvolution::ForgetSymbolicName(Instruction *PN, const SCEV *SymName) {
SmallVector<Instruction *, 16> Worklist;
PushDefUseChildren(PN, Worklist);
SmallPtrSet<Instruction *, 8> Visited;
Visited.insert(PN);
while (!Worklist.empty()) {
Instruction *I = Worklist.pop_back_val();
if (!Visited.insert(I)) continue;
ValueExprMapType::iterator It =
ValueExprMap.find_as(static_cast<Value *>(I));
if (It != ValueExprMap.end()) {
const SCEV *Old = It->second;
if (Old != SymName && !hasOperand(Old, SymName))
continue;
if (!isa<PHINode>(I) ||
!isa<SCEVUnknown>(Old) ||
(I != PN && Old == SymName)) {
forgetMemoizedResults(Old);
ValueExprMap.erase(It);
}
}
PushDefUseChildren(I, Worklist);
}
}
const SCEV *ScalarEvolution::createNodeForPHI(PHINode *PN) {
if (const Loop *L = LI->getLoopFor(PN->getParent()))
if (L->getHeader() == PN->getParent()) {
Value *BEValueV = 0, *StartValueV = 0;
for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
Value *V = PN->getIncomingValue(i);
if (L->contains(PN->getIncomingBlock(i))) {
if (!BEValueV) {
BEValueV = V;
} else if (BEValueV != V) {
BEValueV = 0;
break;
}
} else if (!StartValueV) {
StartValueV = V;
} else if (StartValueV != V) {
StartValueV = 0;
break;
}
}
if (BEValueV && StartValueV) {
const SCEV *SymbolicName = getUnknown(PN);
assert(ValueExprMap.find_as(PN) == ValueExprMap.end() &&
"PHI node already processed?");
ValueExprMap.insert(std::make_pair(SCEVCallbackVH(PN, this), SymbolicName));
const SCEV *BEValue = getSCEV(BEValueV);
if (const 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()) {
SmallVector<const SCEV *, 8> Ops;
for (unsigned i = 0, e = Add->getNumOperands(); i != e; ++i)
if (i != FoundIndex)
Ops.push_back(Add->getOperand(i));
const SCEV *Accum = getAddExpr(Ops);
if (isLoopInvariant(Accum, L) ||
(isa<SCEVAddRecExpr>(Accum) &&
cast<SCEVAddRecExpr>(Accum)->getLoop() == L)) {
SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap;
if (const AddOperator *OBO = dyn_cast<AddOperator>(BEValueV)) {
if (OBO->hasNoUnsignedWrap())
Flags = setFlags(Flags, SCEV::FlagNUW);
if (OBO->hasNoSignedWrap())
Flags = setFlags(Flags, SCEV::FlagNSW);
} else if (const GEPOperator *GEP =
dyn_cast<GEPOperator>(BEValueV)) {
if (GEP->isInBounds())
Flags = setFlags(Flags, SCEV::FlagNW);
}
const SCEV *StartVal = getSCEV(StartValueV);
const SCEV *PHISCEV = getAddRecExpr(StartVal, Accum, L, Flags);
if (isLoopInvariant(Accum, L))
(void)getAddRecExpr(getAddExpr(StartVal, Accum),
Accum, L, Flags);
ForgetSymbolicName(PN, SymbolicName);
ValueExprMap[SCEVCallbackVH(PN, this)] = PHISCEV;
return PHISCEV;
}
}
} else if (const SCEVAddRecExpr *AddRec =
dyn_cast<SCEVAddRecExpr>(BEValue)) {
if (AddRec->getLoop() == L && AddRec->isAffine()) {
const SCEV *StartVal = getSCEV(StartValueV);
if (StartVal == getMinusSCEV(AddRec->getOperand(0),
AddRec->getOperand(1))) {
const SCEV *PHISCEV =
getAddRecExpr(StartVal, AddRec->getOperand(1), L,
SCEV::FlagAnyWrap);
ForgetSymbolicName(PN, SymbolicName);
ValueExprMap[SCEVCallbackVH(PN, this)] = PHISCEV;
return PHISCEV;
}
}
}
}
}
if (Value *V = SimplifyInstruction(PN, TD, TLI, DT))
if (LI->replacementPreservesLCSSAForm(PN, V))
return getSCEV(V);
return getUnknown(PN);
}
const SCEV *ScalarEvolution::createNodeForGEP(GEPOperator *GEP) {
bool isInBounds = GEP->isInBounds();
Type *IntPtrTy = getEffectiveSCEVType(GEP->getType());
Value *Base = GEP->getOperand(0);
if (!cast<PointerType>(Base->getType())->getElementType()->isSized())
return getUnknown(GEP);
const SCEV *TotalOffset = getConstant(IntPtrTy, 0);
gep_type_iterator GTI = gep_type_begin(GEP);
for (GetElementPtrInst::op_iterator I = llvm::next(GEP->op_begin()),
E = GEP->op_end();
I != E; ++I) {
Value *Index = *I;
if (StructType *STy = dyn_cast<StructType>(*GTI++)) {
unsigned FieldNo = cast<ConstantInt>(Index)->getZExtValue();
const SCEV *FieldOffset = getOffsetOfExpr(STy, FieldNo);
TotalOffset = getAddExpr(TotalOffset, FieldOffset);
} else {
const SCEV *ElementSize = getSizeOfExpr(*GTI);
const SCEV *IndexS = getSCEV(Index);
IndexS = getTruncateOrSignExtend(IndexS, IntPtrTy);
const SCEV *LocalOffset = getMulExpr(IndexS, ElementSize,
isInBounds ? SCEV::FlagNSW :
SCEV::FlagAnyWrap);
TotalOffset = getAddExpr(TotalOffset, LocalOffset);
}
}
const SCEV *BaseS = getSCEV(Base);
return getAddExpr(BaseS, TotalOffset,
isInBounds ? SCEV::FlagNSW : SCEV::FlagAnyWrap);
}
uint32_t
ScalarEvolution::GetMinTrailingZeros(const SCEV *S) {
if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S))
return C->getValue()->getValue().countTrailingZeros();
if (const SCEVTruncateExpr *T = dyn_cast<SCEVTruncateExpr>(S))
return std::min(GetMinTrailingZeros(T->getOperand()),
(uint32_t)getTypeSizeInBits(T->getType()));
if (const SCEVZeroExtendExpr *E = dyn_cast<SCEVZeroExtendExpr>(S)) {
uint32_t OpRes = GetMinTrailingZeros(E->getOperand());
return OpRes == getTypeSizeInBits(E->getOperand()->getType()) ?
getTypeSizeInBits(E->getType()) : OpRes;
}
if (const SCEVSignExtendExpr *E = dyn_cast<SCEVSignExtendExpr>(S)) {
uint32_t OpRes = GetMinTrailingZeros(E->getOperand());
return OpRes == getTypeSizeInBits(E->getOperand()->getType()) ?
getTypeSizeInBits(E->getType()) : OpRes;
}
if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) {
uint32_t MinOpRes = GetMinTrailingZeros(A->getOperand(0));
for (unsigned i = 1, e = A->getNumOperands(); MinOpRes && i != e; ++i)
MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(A->getOperand(i)));
return MinOpRes;
}
if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(S)) {
uint32_t SumOpRes = GetMinTrailingZeros(M->getOperand(0));
uint32_t BitWidth = getTypeSizeInBits(M->getType());
for (unsigned i = 1, e = M->getNumOperands();
SumOpRes != BitWidth && i != e; ++i)
SumOpRes = std::min(SumOpRes + GetMinTrailingZeros(M->getOperand(i)),
BitWidth);
return SumOpRes;
}
if (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(S)) {
uint32_t MinOpRes = GetMinTrailingZeros(A->getOperand(0));
for (unsigned i = 1, e = A->getNumOperands(); MinOpRes && i != e; ++i)
MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(A->getOperand(i)));
return MinOpRes;
}
if (const SCEVSMaxExpr *M = dyn_cast<SCEVSMaxExpr>(S)) {
uint32_t MinOpRes = GetMinTrailingZeros(M->getOperand(0));
for (unsigned i = 1, e = M->getNumOperands(); MinOpRes && i != e; ++i)
MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(M->getOperand(i)));
return MinOpRes;
}
if (const SCEVUMaxExpr *M = dyn_cast<SCEVUMaxExpr>(S)) {
uint32_t MinOpRes = GetMinTrailingZeros(M->getOperand(0));
for (unsigned i = 1, e = M->getNumOperands(); MinOpRes && i != e; ++i)
MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(M->getOperand(i)));
return MinOpRes;
}
if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
unsigned BitWidth = getTypeSizeInBits(U->getType());
APInt Zeros(BitWidth, 0), Ones(BitWidth, 0);
ComputeMaskedBits(U->getValue(), Zeros, Ones);
return Zeros.countTrailingOnes();
}
return 0;
}
ConstantRange
ScalarEvolution::getUnsignedRange(const SCEV *S) {
DenseMap<const SCEV *, ConstantRange>::iterator I = UnsignedRanges.find(S);
if (I != UnsignedRanges.end())
return I->second;
if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S))
return setUnsignedRange(C, ConstantRange(C->getValue()->getValue()));
unsigned BitWidth = getTypeSizeInBits(S->getType());
ConstantRange ConservativeResult(BitWidth, true);
uint32_t TZ = GetMinTrailingZeros(S);
if (TZ != 0)
ConservativeResult =
ConstantRange(APInt::getMinValue(BitWidth),
APInt::getMaxValue(BitWidth).lshr(TZ).shl(TZ) + 1);
if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
ConstantRange X = getUnsignedRange(Add->getOperand(0));
for (unsigned i = 1, e = Add->getNumOperands(); i != e; ++i)
X = X.add(getUnsignedRange(Add->getOperand(i)));
return setUnsignedRange(Add, ConservativeResult.intersectWith(X));
}
if (const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(S)) {
ConstantRange X = getUnsignedRange(Mul->getOperand(0));
for (unsigned i = 1, e = Mul->getNumOperands(); i != e; ++i)
X = X.multiply(getUnsignedRange(Mul->getOperand(i)));
return setUnsignedRange(Mul, ConservativeResult.intersectWith(X));
}
if (const SCEVSMaxExpr *SMax = dyn_cast<SCEVSMaxExpr>(S)) {
ConstantRange X = getUnsignedRange(SMax->getOperand(0));
for (unsigned i = 1, e = SMax->getNumOperands(); i != e; ++i)
X = X.smax(getUnsignedRange(SMax->getOperand(i)));
return setUnsignedRange(SMax, ConservativeResult.intersectWith(X));
}
if (const SCEVUMaxExpr *UMax = dyn_cast<SCEVUMaxExpr>(S)) {
ConstantRange X = getUnsignedRange(UMax->getOperand(0));
for (unsigned i = 1, e = UMax->getNumOperands(); i != e; ++i)
X = X.umax(getUnsignedRange(UMax->getOperand(i)));
return setUnsignedRange(UMax, ConservativeResult.intersectWith(X));
}
if (const SCEVUDivExpr *UDiv = dyn_cast<SCEVUDivExpr>(S)) {
ConstantRange X = getUnsignedRange(UDiv->getLHS());
ConstantRange Y = getUnsignedRange(UDiv->getRHS());
return setUnsignedRange(UDiv, ConservativeResult.intersectWith(X.udiv(Y)));
}
if (const SCEVZeroExtendExpr *ZExt = dyn_cast<SCEVZeroExtendExpr>(S)) {
ConstantRange X = getUnsignedRange(ZExt->getOperand());
return setUnsignedRange(ZExt,
ConservativeResult.intersectWith(X.zeroExtend(BitWidth)));
}
if (const SCEVSignExtendExpr *SExt = dyn_cast<SCEVSignExtendExpr>(S)) {
ConstantRange X = getUnsignedRange(SExt->getOperand());
return setUnsignedRange(SExt,
ConservativeResult.intersectWith(X.signExtend(BitWidth)));
}
if (const SCEVTruncateExpr *Trunc = dyn_cast<SCEVTruncateExpr>(S)) {
ConstantRange X = getUnsignedRange(Trunc->getOperand());
return setUnsignedRange(Trunc,
ConservativeResult.intersectWith(X.truncate(BitWidth)));
}
if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S)) {
if (AddRec->getNoWrapFlags(SCEV::FlagNUW))
if (const SCEVConstant *C = dyn_cast<SCEVConstant>(AddRec->getStart()))
if (!C->getValue()->isZero())
ConservativeResult =
ConservativeResult.intersectWith(
ConstantRange(C->getValue()->getValue(), APInt(BitWidth, 0)));
if (AddRec->isAffine()) {
Type *Ty = AddRec->getType();
const SCEV *MaxBECount = getMaxBackedgeTakenCount(AddRec->getLoop());
if (!isa<SCEVCouldNotCompute>(MaxBECount) &&
getTypeSizeInBits(MaxBECount->getType()) <= BitWidth) {
MaxBECount = getNoopOrZeroExtend(MaxBECount, Ty);
const SCEV *Start = AddRec->getStart();
const SCEV *Step = AddRec->getStepRecurrence(*this);
ConstantRange StartRange = getUnsignedRange(Start);
ConstantRange StepRange = getSignedRange(Step);
ConstantRange MaxBECountRange = getUnsignedRange(MaxBECount);
ConstantRange EndRange =
StartRange.add(MaxBECountRange.multiply(StepRange));
ConstantRange ExtStartRange = StartRange.zextOrTrunc(BitWidth*2+1);
ConstantRange ExtStepRange = StepRange.sextOrTrunc(BitWidth*2+1);
ConstantRange ExtMaxBECountRange =
MaxBECountRange.zextOrTrunc(BitWidth*2+1);
ConstantRange ExtEndRange = EndRange.zextOrTrunc(BitWidth*2+1);
if (ExtStartRange.add(ExtMaxBECountRange.multiply(ExtStepRange)) !=
ExtEndRange)
return setUnsignedRange(AddRec, ConservativeResult);
APInt Min = APIntOps::umin(StartRange.getUnsignedMin(),
EndRange.getUnsignedMin());
APInt Max = APIntOps::umax(StartRange.getUnsignedMax(),
EndRange.getUnsignedMax());
if (Min.isMinValue() && Max.isMaxValue())
return setUnsignedRange(AddRec, ConservativeResult);
return setUnsignedRange(AddRec,
ConservativeResult.intersectWith(ConstantRange(Min, Max+1)));
}
}
return setUnsignedRange(AddRec, ConservativeResult);
}
if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
APInt Zeros(BitWidth, 0), Ones(BitWidth, 0);
ComputeMaskedBits(U->getValue(), Zeros, Ones, TD);
if (Ones == ~Zeros + 1)
return setUnsignedRange(U, ConservativeResult);
return setUnsignedRange(U,
ConservativeResult.intersectWith(ConstantRange(Ones, ~Zeros + 1)));
}
return setUnsignedRange(S, ConservativeResult);
}
ConstantRange
ScalarEvolution::getSignedRange(const SCEV *S) {
DenseMap<const SCEV *, ConstantRange>::iterator I = SignedRanges.find(S);
if (I != SignedRanges.end())
return I->second;
if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S))
return setSignedRange(C, ConstantRange(C->getValue()->getValue()));
unsigned BitWidth = getTypeSizeInBits(S->getType());
ConstantRange ConservativeResult(BitWidth, true);
uint32_t TZ = GetMinTrailingZeros(S);
if (TZ != 0)
ConservativeResult =
ConstantRange(APInt::getSignedMinValue(BitWidth),
APInt::getSignedMaxValue(BitWidth).ashr(TZ).shl(TZ) + 1);
if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
ConstantRange X = getSignedRange(Add->getOperand(0));
for (unsigned i = 1, e = Add->getNumOperands(); i != e; ++i)
X = X.add(getSignedRange(Add->getOperand(i)));
return setSignedRange(Add, ConservativeResult.intersectWith(X));
}
if (const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(S)) {
ConstantRange X = getSignedRange(Mul->getOperand(0));
for (unsigned i = 1, e = Mul->getNumOperands(); i != e; ++i)
X = X.multiply(getSignedRange(Mul->getOperand(i)));
return setSignedRange(Mul, ConservativeResult.intersectWith(X));
}
if (const SCEVSMaxExpr *SMax = dyn_cast<SCEVSMaxExpr>(S)) {
ConstantRange X = getSignedRange(SMax->getOperand(0));
for (unsigned i = 1, e = SMax->getNumOperands(); i != e; ++i)
X = X.smax(getSignedRange(SMax->getOperand(i)));
return setSignedRange(SMax, ConservativeResult.intersectWith(X));
}
if (const SCEVUMaxExpr *UMax = dyn_cast<SCEVUMaxExpr>(S)) {
ConstantRange X = getSignedRange(UMax->getOperand(0));
for (unsigned i = 1, e = UMax->getNumOperands(); i != e; ++i)
X = X.umax(getSignedRange(UMax->getOperand(i)));
return setSignedRange(UMax, ConservativeResult.intersectWith(X));
}
if (const SCEVUDivExpr *UDiv = dyn_cast<SCEVUDivExpr>(S)) {
ConstantRange X = getSignedRange(UDiv->getLHS());
ConstantRange Y = getSignedRange(UDiv->getRHS());
return setSignedRange(UDiv, ConservativeResult.intersectWith(X.udiv(Y)));
}
if (const SCEVZeroExtendExpr *ZExt = dyn_cast<SCEVZeroExtendExpr>(S)) {
ConstantRange X = getSignedRange(ZExt->getOperand());
return setSignedRange(ZExt,
ConservativeResult.intersectWith(X.zeroExtend(BitWidth)));
}
if (const SCEVSignExtendExpr *SExt = dyn_cast<SCEVSignExtendExpr>(S)) {
ConstantRange X = getSignedRange(SExt->getOperand());
return setSignedRange(SExt,
ConservativeResult.intersectWith(X.signExtend(BitWidth)));
}
if (const SCEVTruncateExpr *Trunc = dyn_cast<SCEVTruncateExpr>(S)) {
ConstantRange X = getSignedRange(Trunc->getOperand());
return setSignedRange(Trunc,
ConservativeResult.intersectWith(X.truncate(BitWidth)));
}
if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S)) {
if (AddRec->getNoWrapFlags(SCEV::FlagNSW)) {
bool AllNonNeg = true;
bool AllNonPos = true;
for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) {
if (!isKnownNonNegative(AddRec->getOperand(i))) AllNonNeg = false;
if (!isKnownNonPositive(AddRec->getOperand(i))) AllNonPos = false;
}
if (AllNonNeg)
ConservativeResult = ConservativeResult.intersectWith(
ConstantRange(APInt(BitWidth, 0),
APInt::getSignedMinValue(BitWidth)));
else if (AllNonPos)
ConservativeResult = ConservativeResult.intersectWith(
ConstantRange(APInt::getSignedMinValue(BitWidth),
APInt(BitWidth, 1)));
}
if (AddRec->isAffine()) {
Type *Ty = AddRec->getType();
const SCEV *MaxBECount = getMaxBackedgeTakenCount(AddRec->getLoop());
if (!isa<SCEVCouldNotCompute>(MaxBECount) &&
getTypeSizeInBits(MaxBECount->getType()) <= BitWidth) {
MaxBECount = getNoopOrZeroExtend(MaxBECount, Ty);
const SCEV *Start = AddRec->getStart();
const SCEV *Step = AddRec->getStepRecurrence(*this);
ConstantRange StartRange = getSignedRange(Start);
ConstantRange StepRange = getSignedRange(Step);
ConstantRange MaxBECountRange = getUnsignedRange(MaxBECount);
ConstantRange EndRange =
StartRange.add(MaxBECountRange.multiply(StepRange));
ConstantRange ExtStartRange = StartRange.sextOrTrunc(BitWidth*2+1);
ConstantRange ExtStepRange = StepRange.sextOrTrunc(BitWidth*2+1);
ConstantRange ExtMaxBECountRange =
MaxBECountRange.zextOrTrunc(BitWidth*2+1);
ConstantRange ExtEndRange = EndRange.sextOrTrunc(BitWidth*2+1);
if (ExtStartRange.add(ExtMaxBECountRange.multiply(ExtStepRange)) !=
ExtEndRange)
return setSignedRange(AddRec, ConservativeResult);
APInt Min = APIntOps::smin(StartRange.getSignedMin(),
EndRange.getSignedMin());
APInt Max = APIntOps::smax(StartRange.getSignedMax(),
EndRange.getSignedMax());
if (Min.isMinSignedValue() && Max.isMaxSignedValue())
return setSignedRange(AddRec, ConservativeResult);
return setSignedRange(AddRec,
ConservativeResult.intersectWith(ConstantRange(Min, Max+1)));
}
}
return setSignedRange(AddRec, ConservativeResult);
}
if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
if (!U->getValue()->getType()->isIntegerTy() && !TD)
return setSignedRange(U, ConservativeResult);
unsigned NS = ComputeNumSignBits(U->getValue(), TD);
if (NS == 1)
return setSignedRange(U, ConservativeResult);
return setSignedRange(U, ConservativeResult.intersectWith(
ConstantRange(APInt::getSignedMinValue(BitWidth).ashr(NS - 1),
APInt::getSignedMaxValue(BitWidth).ashr(NS - 1)+1)));
}
return setSignedRange(S, ConservativeResult);
}
const SCEV *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();
if (!DT->isReachableFromEntry(I->getParent()))
return getUnknown(V);
} else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
Opcode = CE->getOpcode();
else if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
return getConstant(CI);
else if (isa<ConstantPointerNull>(V))
return getConstant(V->getType(), 0);
else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V))
return GA->mayBeOverridden() ? getUnknown(V) : getSCEV(GA->getAliasee());
else
return getUnknown(V);
Operator *U = cast<Operator>(V);
switch (Opcode) {
case Instruction::Add: {
SmallVector<const SCEV *, 4> AddOps;
AddOps.push_back(getSCEV(U->getOperand(1)));
for (Value *Op = U->getOperand(0); ; Op = U->getOperand(0)) {
unsigned Opcode = Op->getValueID() - Value::InstructionVal;
if (Opcode != Instruction::Add && Opcode != Instruction::Sub)
break;
U = cast<Operator>(Op);
const SCEV *Op1 = getSCEV(U->getOperand(1));
if (Opcode == Instruction::Sub)
AddOps.push_back(getNegativeSCEV(Op1));
else
AddOps.push_back(Op1);
}
AddOps.push_back(getSCEV(U->getOperand(0)));
return getAddExpr(AddOps);
}
case Instruction::Mul: {
SmallVector<const SCEV *, 4> MulOps;
MulOps.push_back(getSCEV(U->getOperand(1)));
for (Value *Op = U->getOperand(0);
Op->getValueID() == Instruction::Mul + Value::InstructionVal;
Op = U->getOperand(0)) {
U = cast<Operator>(Op);
MulOps.push_back(getSCEV(U->getOperand(1)));
}
MulOps.push_back(getSCEV(U->getOperand(0)));
return getMulExpr(MulOps);
}
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))) {
if (CI->isNullValue())
return getSCEV(U->getOperand(1));
if (CI->isAllOnesValue())
return getSCEV(U->getOperand(0));
const APInt &A = CI->getValue();
unsigned LZ = A.countLeadingZeros();
unsigned BitWidth = A.getBitWidth();
APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0);
ComputeMaskedBits(U->getOperand(0), KnownZero, KnownOne, TD);
APInt EffectiveMask = APInt::getLowBitsSet(BitWidth, BitWidth - LZ);
if (LZ != 0 && !((~A & ~KnownZero) & EffectiveMask))
return
getZeroExtendExpr(getTruncateExpr(getSCEV(U->getOperand(0)),
IntegerType::get(getContext(), BitWidth - LZ)),
U->getType());
}
break;
case Instruction::Or:
if (ConstantInt *CI = dyn_cast<ConstantInt>(U->getOperand(1))) {
const SCEV *LHS = getSCEV(U->getOperand(0));
const APInt &CIVal = CI->getValue();
if (GetMinTrailingZeros(LHS) >=
(CIVal.getBitWidth() - CIVal.countLeadingZeros())) {
const SCEV *S = getAddExpr(LHS, getSCEV(CI));
if (const SCEVAddRecExpr *NewAR = dyn_cast<SCEVAddRecExpr>(S)) {
const SCEVAddRecExpr *OldAR = cast<SCEVAddRecExpr>(LHS);
const_cast<SCEVAddRecExpr *>(NewAR)->setNoWrapFlags(
OldAR->getNoWrapFlags());
}
return S;
}
}
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)));
if (CI->isAllOnesValue())
return getNotSCEV(getSCEV(U->getOperand(0)));
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)))) {
Type *UTy = U->getType();
const SCEV *Z0 = Z->getOperand();
Type *Z0Ty = Z0->getType();
unsigned Z0TySize = getTypeSizeInBits(Z0Ty);
if (APIntOps::isMask(Z0TySize, CI->getValue()))
return getZeroExtendExpr(getNotSCEV(Z0), UTy);
APInt Trunc = CI->getValue().trunc(Z0TySize);
if (Trunc.zext(getTypeSizeInBits(UTy)) == CI->getValue() &&
Trunc.isSignBit())
return getZeroExtendExpr(getAddExpr(Z0, getConstant(Trunc)),
UTy);
}
}
break;
case Instruction::Shl:
if (ConstantInt *SA = dyn_cast<ConstantInt>(U->getOperand(1))) {
uint32_t BitWidth = cast<IntegerType>(U->getType())->getBitWidth();
if (SA->getValue().uge(BitWidth))
break;
Constant *X = ConstantInt::get(getContext(),
APInt(BitWidth, 1).shl(SA->getZExtValue()));
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>(U->getType())->getBitWidth();
if (SA->getValue().uge(BitWidth))
break;
Constant *X = ConstantInt::get(getContext(),
APInt(BitWidth, 1).shl(SA->getZExtValue()));
return getUDivExpr(getSCEV(U->getOperand(0)), getSCEV(X));
}
break;
case Instruction::AShr:
if (ConstantInt *CI = dyn_cast<ConstantInt>(U->getOperand(1)))
if (Operator *L = dyn_cast<Operator>(U->getOperand(0)))
if (L->getOpcode() == Instruction::Shl &&
L->getOperand(1) == U->getOperand(1)) {
uint64_t BitWidth = getTypeSizeInBits(U->getType());
if (CI->getValue().uge(BitWidth))
break;
uint64_t Amt = BitWidth - CI->getZExtValue();
if (Amt == BitWidth)
return getSCEV(L->getOperand(0)); return
getSignExtendExpr(getTruncateExpr(getSCEV(L->getOperand(0)),
IntegerType::get(getContext(),
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::GetElementPtr:
return createNodeForGEP(cast<GEPOperator>(U));
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->getType() == U->getType()) {
const SCEV *LS = getSCEV(LHS);
const SCEV *RS = getSCEV(RHS);
const SCEV *LA = getSCEV(U->getOperand(1));
const SCEV *RA = getSCEV(U->getOperand(2));
const SCEV *LDiff = getMinusSCEV(LA, LS);
const SCEV *RDiff = getMinusSCEV(RA, RS);
if (LDiff == RDiff)
return getAddExpr(getSMaxExpr(LS, RS), LDiff);
LDiff = getMinusSCEV(LA, RS);
RDiff = getMinusSCEV(RA, LS);
if (LDiff == RDiff)
return getAddExpr(getSMinExpr(LS, RS), LDiff);
}
break;
case ICmpInst::ICMP_ULT:
case ICmpInst::ICMP_ULE:
std::swap(LHS, RHS);
case ICmpInst::ICMP_UGT:
case ICmpInst::ICMP_UGE:
if (LHS->getType() == U->getType()) {
const SCEV *LS = getSCEV(LHS);
const SCEV *RS = getSCEV(RHS);
const SCEV *LA = getSCEV(U->getOperand(1));
const SCEV *RA = getSCEV(U->getOperand(2));
const SCEV *LDiff = getMinusSCEV(LA, LS);
const SCEV *RDiff = getMinusSCEV(RA, RS);
if (LDiff == RDiff)
return getAddExpr(getUMaxExpr(LS, RS), LDiff);
LDiff = getMinusSCEV(LA, RS);
RDiff = getMinusSCEV(RA, LS);
if (LDiff == RDiff)
return getAddExpr(getUMinExpr(LS, RS), LDiff);
}
break;
case ICmpInst::ICMP_NE:
if (LHS->getType() == U->getType() &&
isa<ConstantInt>(RHS) &&
cast<ConstantInt>(RHS)->isZero()) {
const SCEV *One = getConstant(LHS->getType(), 1);
const SCEV *LS = getSCEV(LHS);
const SCEV *LA = getSCEV(U->getOperand(1));
const SCEV *RA = getSCEV(U->getOperand(2));
const SCEV *LDiff = getMinusSCEV(LA, LS);
const SCEV *RDiff = getMinusSCEV(RA, One);
if (LDiff == RDiff)
return getAddExpr(getUMaxExpr(One, LS), LDiff);
}
break;
case ICmpInst::ICMP_EQ:
if (LHS->getType() == U->getType() &&
isa<ConstantInt>(RHS) &&
cast<ConstantInt>(RHS)->isZero()) {
const SCEV *One = getConstant(LHS->getType(), 1);
const SCEV *LS = getSCEV(LHS);
const SCEV *LA = getSCEV(U->getOperand(1));
const SCEV *RA = getSCEV(U->getOperand(2));
const SCEV *LDiff = getMinusSCEV(LA, One);
const SCEV *RDiff = getMinusSCEV(RA, LS);
if (LDiff == RDiff)
return getAddExpr(getUMaxExpr(One, LS), LDiff);
}
break;
default:
break;
}
}
default: break;
}
return getUnknown(V);
}
unsigned ScalarEvolution::
getSmallConstantTripCount(Loop *L, BasicBlock *) {
const SCEVConstant *ExitCount =
dyn_cast<SCEVConstant>(getBackedgeTakenCount(L));
if (!ExitCount)
return 0;
ConstantInt *ExitConst = ExitCount->getValue();
if (ExitConst->getValue().getActiveBits() > 32)
return 0;
return ((unsigned)ExitConst->getZExtValue()) + 1;
}
unsigned ScalarEvolution::
getSmallConstantTripMultiple(Loop *L, BasicBlock *) {
const SCEV *ExitCount = getBackedgeTakenCount(L);
if (ExitCount == getCouldNotCompute())
return 1;
const SCEV *TCMul = getAddExpr(ExitCount,
getConstant(ExitCount->getType(), 1));
if (const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(TCMul))
TCMul = Mul->getOperand(0);
const SCEVConstant *MulC = dyn_cast<SCEVConstant>(TCMul);
if (!MulC)
return 1;
ConstantInt *Result = MulC->getValue();
if (!Result || Result->getValue().getActiveBits() > 32 ||
Result->getValue().getActiveBits() == 0)
return 1;
return (unsigned)Result->getZExtValue();
}
const SCEV *ScalarEvolution::getExitCount(Loop *L, BasicBlock *ExitingBlock) {
return getBackedgeTakenInfo(L).getExact(ExitingBlock, this);
}
const SCEV *ScalarEvolution::getBackedgeTakenCount(const Loop *L) {
return getBackedgeTakenInfo(L).getExact(this);
}
const SCEV *ScalarEvolution::getMaxBackedgeTakenCount(const Loop *L) {
return getBackedgeTakenInfo(L).getMax(this);
}
static void
PushLoopPHIs(const Loop *L, SmallVectorImpl<Instruction *> &Worklist) {
BasicBlock *Header = L->getHeader();
for (BasicBlock::iterator I = Header->begin();
PHINode *PN = dyn_cast<PHINode>(I); ++I)
Worklist.push_back(PN);
}
const ScalarEvolution::BackedgeTakenInfo &
ScalarEvolution::getBackedgeTakenInfo(const Loop *L) {
std::pair<DenseMap<const Loop *, BackedgeTakenInfo>::iterator, bool> Pair =
BackedgeTakenCounts.insert(std::make_pair(L, BackedgeTakenInfo()));
if (!Pair.second)
return Pair.first->second;
BackedgeTakenInfo Result = ComputeBackedgeTakenCount(L);
if (Result.getExact(this) != getCouldNotCompute()) {
assert(isLoopInvariant(Result.getExact(this), L) &&
isLoopInvariant(Result.getMax(this), L) &&
"Computed backedge-taken count isn't loop invariant for loop!");
++NumTripCountsComputed;
}
else if (Result.getMax(this) == getCouldNotCompute() &&
isa<PHINode>(L->getHeader()->begin())) {
++NumTripCountsNotComputed;
}
if (Result.hasAnyInfo()) {
SmallVector<Instruction *, 16> Worklist;
PushLoopPHIs(L, Worklist);
SmallPtrSet<Instruction *, 8> Visited;
while (!Worklist.empty()) {
Instruction *I = Worklist.pop_back_val();
if (!Visited.insert(I)) continue;
ValueExprMapType::iterator It =
ValueExprMap.find_as(static_cast<Value *>(I));
if (It != ValueExprMap.end()) {
const SCEV *Old = It->second;
if (!isa<PHINode>(I) || !isa<SCEVUnknown>(Old)) {
forgetMemoizedResults(Old);
ValueExprMap.erase(It);
}
if (PHINode *PN = dyn_cast<PHINode>(I))
ConstantEvolutionLoopExitValue.erase(PN);
}
PushDefUseChildren(I, Worklist);
}
}
return BackedgeTakenCounts.find(L)->second = Result;
}
void ScalarEvolution::forgetLoop(const Loop *L) {
DenseMap<const Loop*, BackedgeTakenInfo>::iterator BTCPos =
BackedgeTakenCounts.find(L);
if (BTCPos != BackedgeTakenCounts.end()) {
BTCPos->second.clear();
BackedgeTakenCounts.erase(BTCPos);
}
SmallVector<Instruction *, 16> Worklist;
PushLoopPHIs(L, Worklist);
SmallPtrSet<Instruction *, 8> Visited;
while (!Worklist.empty()) {
Instruction *I = Worklist.pop_back_val();
if (!Visited.insert(I)) continue;
ValueExprMapType::iterator It =
ValueExprMap.find_as(static_cast<Value *>(I));
if (It != ValueExprMap.end()) {
forgetMemoizedResults(It->second);
ValueExprMap.erase(It);
if (PHINode *PN = dyn_cast<PHINode>(I))
ConstantEvolutionLoopExitValue.erase(PN);
}
PushDefUseChildren(I, Worklist);
}
for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
forgetLoop(*I);
}
void ScalarEvolution::forgetValue(Value *V) {
Instruction *I = dyn_cast<Instruction>(V);
if (!I) return;
SmallVector<Instruction *, 16> Worklist;
Worklist.push_back(I);
SmallPtrSet<Instruction *, 8> Visited;
while (!Worklist.empty()) {
I = Worklist.pop_back_val();
if (!Visited.insert(I)) continue;
ValueExprMapType::iterator It =
ValueExprMap.find_as(static_cast<Value *>(I));
if (It != ValueExprMap.end()) {
forgetMemoizedResults(It->second);
ValueExprMap.erase(It);
if (PHINode *PN = dyn_cast<PHINode>(I))
ConstantEvolutionLoopExitValue.erase(PN);
}
PushDefUseChildren(I, Worklist);
}
}
const SCEV *
ScalarEvolution::BackedgeTakenInfo::getExact(ScalarEvolution *SE) const {
if (!ExitNotTaken.isCompleteList()) return SE->getCouldNotCompute();
if (!ExitNotTaken.ExitingBlock) return SE->getCouldNotCompute();
assert(ExitNotTaken.ExactNotTaken && "uninitialized not-taken info");
const SCEV *BECount = 0;
for (const ExitNotTakenInfo *ENT = &ExitNotTaken;
ENT != 0; ENT = ENT->getNextExit()) {
assert(ENT->ExactNotTaken != SE->getCouldNotCompute() && "bad exit SCEV");
if (!BECount)
BECount = ENT->ExactNotTaken;
else if (BECount != ENT->ExactNotTaken)
return SE->getCouldNotCompute();
}
assert(BECount && "Invalid not taken count for loop exit");
return BECount;
}
const SCEV *
ScalarEvolution::BackedgeTakenInfo::getExact(BasicBlock *ExitingBlock,
ScalarEvolution *SE) const {
for (const ExitNotTakenInfo *ENT = &ExitNotTaken;
ENT != 0; ENT = ENT->getNextExit()) {
if (ENT->ExitingBlock == ExitingBlock)
return ENT->ExactNotTaken;
}
return SE->getCouldNotCompute();
}
const SCEV *
ScalarEvolution::BackedgeTakenInfo::getMax(ScalarEvolution *SE) const {
return Max ? Max : SE->getCouldNotCompute();
}
bool ScalarEvolution::BackedgeTakenInfo::hasOperand(const SCEV *S,
ScalarEvolution *SE) const {
if (Max && Max != SE->getCouldNotCompute() && SE->hasOperand(Max, S))
return true;
if (!ExitNotTaken.ExitingBlock)
return false;
for (const ExitNotTakenInfo *ENT = &ExitNotTaken;
ENT != 0; ENT = ENT->getNextExit()) {
if (ENT->ExactNotTaken != SE->getCouldNotCompute()
&& SE->hasOperand(ENT->ExactNotTaken, S)) {
return true;
}
}
return false;
}
ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo(
SmallVectorImpl< std::pair<BasicBlock *, const SCEV *> > &ExitCounts,
bool Complete, const SCEV *MaxCount) : Max(MaxCount) {
if (!Complete)
ExitNotTaken.setIncomplete();
unsigned NumExits = ExitCounts.size();
if (NumExits == 0) return;
ExitNotTaken.ExitingBlock = ExitCounts[0].first;
ExitNotTaken.ExactNotTaken = ExitCounts[0].second;
if (NumExits == 1) return;
ExitNotTakenInfo *ENT = new ExitNotTakenInfo[NumExits-1];
ExitNotTakenInfo *PrevENT = &ExitNotTaken;
for (unsigned i = 1; i < NumExits; ++i, PrevENT = ENT, ++ENT) {
PrevENT->setNextExit(ENT);
ENT->ExitingBlock = ExitCounts[i].first;
ENT->ExactNotTaken = ExitCounts[i].second;
}
}
void ScalarEvolution::BackedgeTakenInfo::clear() {
ExitNotTaken.ExitingBlock = 0;
ExitNotTaken.ExactNotTaken = 0;
delete[] ExitNotTaken.getNextExit();
}
ScalarEvolution::BackedgeTakenInfo
ScalarEvolution::ComputeBackedgeTakenCount(const Loop *L) {
SmallVector<BasicBlock *, 8> ExitingBlocks;
L->getExitingBlocks(ExitingBlocks);
const SCEV *MaxBECount = getCouldNotCompute();
bool CouldComputeBECount = true;
SmallVector<std::pair<BasicBlock *, const SCEV *>, 4> ExitCounts;
for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) {
ExitLimit EL = ComputeExitLimit(L, ExitingBlocks[i]);
if (EL.Exact == getCouldNotCompute())
CouldComputeBECount = false;
else
ExitCounts.push_back(std::make_pair(ExitingBlocks[i], EL.Exact));
if (MaxBECount == getCouldNotCompute())
MaxBECount = EL.Max;
else if (EL.Max != getCouldNotCompute()) {
MaxBECount = getUMaxFromMismatchedTypes(MaxBECount, EL.Max);
}
}
return BackedgeTakenInfo(ExitCounts, CouldComputeBECount, MaxBECount);
}
ScalarEvolution::ExitLimit
ScalarEvolution::ComputeExitLimit(const Loop *L, BasicBlock *ExitingBlock) {
BranchInst *ExitBr = dyn_cast<BranchInst>(ExitingBlock->getTerminator());
if (ExitBr == 0) return getCouldNotCompute();
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()) {
bool Ok = false;
for (BasicBlock *BB = ExitBr->getParent(); BB; ) {
BasicBlock *Pred = BB->getUniquePredecessor();
if (!Pred)
return getCouldNotCompute();
TerminatorInst *PredTerm = Pred->getTerminator();
for (unsigned i = 0, e = PredTerm->getNumSuccessors(); i != e; ++i) {
BasicBlock *PredSucc = PredTerm->getSuccessor(i);
if (PredSucc == BB)
continue;
if (L->contains(PredSucc))
return getCouldNotCompute();
}
if (Pred == L->getHeader()) {
Ok = true;
break;
}
BB = Pred;
}
if (!Ok)
return getCouldNotCompute();
}
return ComputeExitLimitFromCond(L, ExitBr->getCondition(),
ExitBr->getSuccessor(0),
ExitBr->getSuccessor(1),
false);
}
ScalarEvolution::ExitLimit
ScalarEvolution::ComputeExitLimitFromCond(const Loop *L,
Value *ExitCond,
BasicBlock *TBB,
BasicBlock *FBB,
bool IsSubExpr) {
if (BinaryOperator *BO = dyn_cast<BinaryOperator>(ExitCond)) {
if (BO->getOpcode() == Instruction::And) {
bool EitherMayExit = L->contains(TBB);
ExitLimit EL0 = ComputeExitLimitFromCond(L, BO->getOperand(0), TBB, FBB,
IsSubExpr || EitherMayExit);
ExitLimit EL1 = ComputeExitLimitFromCond(L, BO->getOperand(1), TBB, FBB,
IsSubExpr || EitherMayExit);
const SCEV *BECount = getCouldNotCompute();
const SCEV *MaxBECount = getCouldNotCompute();
if (EitherMayExit) {
if (EL0.Exact == getCouldNotCompute() ||
EL1.Exact == getCouldNotCompute())
BECount = getCouldNotCompute();
else
BECount = getUMinFromMismatchedTypes(EL0.Exact, EL1.Exact);
if (EL0.Max == getCouldNotCompute())
MaxBECount = EL1.Max;
else if (EL1.Max == getCouldNotCompute())
MaxBECount = EL0.Max;
else
MaxBECount = getUMinFromMismatchedTypes(EL0.Max, EL1.Max);
} else {
assert(L->contains(FBB) && "Loop block has no successor in loop!");
if (EL0.Max == EL1.Max)
MaxBECount = EL0.Max;
if (EL0.Exact == EL1.Exact)
BECount = EL0.Exact;
}
return ExitLimit(BECount, MaxBECount);
}
if (BO->getOpcode() == Instruction::Or) {
bool EitherMayExit = L->contains(FBB);
ExitLimit EL0 = ComputeExitLimitFromCond(L, BO->getOperand(0), TBB, FBB,
IsSubExpr || EitherMayExit);
ExitLimit EL1 = ComputeExitLimitFromCond(L, BO->getOperand(1), TBB, FBB,
IsSubExpr || EitherMayExit);
const SCEV *BECount = getCouldNotCompute();
const SCEV *MaxBECount = getCouldNotCompute();
if (EitherMayExit) {
if (EL0.Exact == getCouldNotCompute() ||
EL1.Exact == getCouldNotCompute())
BECount = getCouldNotCompute();
else
BECount = getUMinFromMismatchedTypes(EL0.Exact, EL1.Exact);
if (EL0.Max == getCouldNotCompute())
MaxBECount = EL1.Max;
else if (EL1.Max == getCouldNotCompute())
MaxBECount = EL0.Max;
else
MaxBECount = getUMinFromMismatchedTypes(EL0.Max, EL1.Max);
} else {
assert(L->contains(TBB) && "Loop block has no successor in loop!");
if (EL0.Max == EL1.Max)
MaxBECount = EL0.Max;
if (EL0.Exact == EL1.Exact)
BECount = EL0.Exact;
}
return ExitLimit(BECount, MaxBECount);
}
}
if (ICmpInst *ExitCondICmp = dyn_cast<ICmpInst>(ExitCond))
return ComputeExitLimitFromICmp(L, ExitCondICmp, TBB, FBB, IsSubExpr);
if (ConstantInt *CI = dyn_cast<ConstantInt>(ExitCond)) {
if (L->contains(FBB) == !CI->getZExtValue())
return getCouldNotCompute();
else
return getConstant(CI->getType(), 0);
}
return ComputeExitCountExhaustively(L, ExitCond, !L->contains(TBB));
}
ScalarEvolution::ExitLimit
ScalarEvolution::ComputeExitLimitFromICmp(const Loop *L,
ICmpInst *ExitCond,
BasicBlock *TBB,
BasicBlock *FBB,
bool IsSubExpr) {
ICmpInst::Predicate Cond;
if (!L->contains(FBB))
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))) {
ExitLimit ItCnt =
ComputeLoadConstantCompareExitLimit(LI, RHS, L, Cond);
if (ItCnt.hasAnyInfo())
return ItCnt;
}
const SCEV *LHS = getSCEV(ExitCond->getOperand(0));
const SCEV *RHS = getSCEV(ExitCond->getOperand(1));
LHS = getSCEVAtScope(LHS, L);
RHS = getSCEVAtScope(RHS, L);
if (isLoopInvariant(LHS, L) && !isLoopInvariant(RHS, L)) {
std::swap(LHS, RHS);
Cond = ICmpInst::getSwappedPredicate(Cond);
}
(void)SimplifyICmpOperands(Cond, LHS, RHS);
if (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS))
if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS))
if (AddRec->getLoop() == L) {
ConstantRange CompRange(
ICmpInst::makeConstantRange(Cond, RHSC->getValue()->getValue()));
const SCEV *Ret = AddRec->getNumIterationsInRange(CompRange, *this);
if (!isa<SCEVCouldNotCompute>(Ret)) return Ret;
}
switch (Cond) {
case ICmpInst::ICMP_NE: { ExitLimit EL = HowFarToZero(getMinusSCEV(LHS, RHS), L, IsSubExpr);
if (EL.hasAnyInfo()) return EL;
break;
}
case ICmpInst::ICMP_EQ: { ExitLimit EL = HowFarToNonZero(getMinusSCEV(LHS, RHS), L);
if (EL.hasAnyInfo()) return EL;
break;
}
case ICmpInst::ICMP_SLT: {
ExitLimit EL = HowManyLessThans(LHS, RHS, L, true, IsSubExpr);
if (EL.hasAnyInfo()) return EL;
break;
}
case ICmpInst::ICMP_SGT: {
ExitLimit EL = HowManyLessThans(getNotSCEV(LHS),
getNotSCEV(RHS), L, true, IsSubExpr);
if (EL.hasAnyInfo()) return EL;
break;
}
case ICmpInst::ICMP_ULT: {
ExitLimit EL = HowManyLessThans(LHS, RHS, L, false, IsSubExpr);
if (EL.hasAnyInfo()) return EL;
break;
}
case ICmpInst::ICMP_UGT: {
ExitLimit EL = HowManyLessThans(getNotSCEV(LHS),
getNotSCEV(RHS), L, false, IsSubExpr);
if (EL.hasAnyInfo()) return EL;
break;
}
default:
#if 0
dbgs() << "ComputeBackedgeTakenCount ";
if (ExitCond->getOperand(0)->getType()->isUnsigned())
dbgs() << "[unsigned] ";
dbgs() << *LHS << " "
<< Instruction::getOpcodeName(Instruction::ICmp)
<< " " << *RHS << "\n";
#endif
break;
}
return ComputeExitCountExhaustively(L, ExitCond, !L->contains(TBB));
}
static ConstantInt *
EvaluateConstantChrecAtConstant(const SCEVAddRecExpr *AddRec, ConstantInt *C,
ScalarEvolution &SE) {
const SCEV *InVal = SE.getConstant(C);
const SCEV *Val = AddRec->evaluateAtIteration(InVal, SE);
assert(isa<SCEVConstant>(Val) &&
"Evaluation of SCEV at constant didn't fold correctly?");
return cast<SCEVConstant>(Val)->getValue();
}
ScalarEvolution::ExitLimit
ScalarEvolution::ComputeLoadConstantCompareExitLimit(
LoadInst *LI,
Constant *RHS,
const Loop *L,
ICmpInst::Predicate predicate) {
if (LI->isVolatile()) return getCouldNotCompute();
GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(LI->getOperand(0));
if (!GEP) return getCouldNotCompute();
GlobalVariable *GV = dyn_cast<GlobalVariable>(GEP->getOperand(0));
if (!GV || !GV->isConstant() || !GV->hasDefinitiveInitializer() ||
GEP->getNumOperands() < 3 || !isa<Constant>(GEP->getOperand(1)) ||
!cast<Constant>(GEP->getOperand(1))->isNullValue())
return getCouldNotCompute();
Value *VarIdx = 0;
std::vector<Constant*> 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 getCouldNotCompute(); VarIdx = GEP->getOperand(i);
VarIdxNum = i-2;
Indexes.push_back(0);
}
if (!VarIdx)
return getCouldNotCompute();
const SCEV *Idx = getSCEV(VarIdx);
Idx = getSCEVAtScope(Idx, L);
const SCEVAddRecExpr *IdxExpr = dyn_cast<SCEVAddRecExpr>(Idx);
if (!IdxExpr || !IdxExpr->isAffine() || isLoopInvariant(IdxExpr, L) ||
!isa<SCEVConstant>(IdxExpr->getOperand(0)) ||
!isa<SCEVConstant>(IdxExpr->getOperand(1)))
return getCouldNotCompute();
unsigned MaxSteps = MaxBruteForceIterations;
for (unsigned IterationNum = 0; IterationNum != MaxSteps; ++IterationNum) {
ConstantInt *ItCst = ConstantInt::get(
cast<IntegerType>(IdxExpr->getType()), IterationNum);
ConstantInt *Val = EvaluateConstantChrecAtConstant(IdxExpr, ItCst, *this);
Indexes[VarIdxNum] = Val;
Constant *Result = ConstantFoldLoadThroughGEPIndices(GV->getInitializer(),
Indexes);
if (Result == 0) break;
Result = ConstantExpr::getICmp(predicate, Result, RHS);
if (!isa<ConstantInt>(Result)) break; if (cast<ConstantInt>(Result)->getValue().isMinValue()) {
#if 0
dbgs() << "\n***\n*** Computed loop count " << *ItCst
<< "\n*** From global " << *GV << "*** BB: " << *L->getHeader()
<< "***\n";
#endif
++NumArrayLenItCounts;
return getConstant(ItCst); }
}
return getCouldNotCompute();
}
static bool CanConstantFold(const Instruction *I) {
if (isa<BinaryOperator>(I) || isa<CmpInst>(I) ||
isa<SelectInst>(I) || isa<CastInst>(I) || isa<GetElementPtrInst>(I) ||
isa<LoadInst>(I))
return true;
if (const CallInst *CI = dyn_cast<CallInst>(I))
if (const Function *F = CI->getCalledFunction())
return canConstantFoldCallTo(F);
return false;
}
static bool canConstantEvolve(Instruction *I, const Loop *L) {
if (!L->contains(I)) return false;
if (isa<PHINode>(I)) {
if (L->getHeader() == I->getParent())
return true;
else
return false;
}
return CanConstantFold(I);
}
static PHINode *
getConstantEvolvingPHIOperands(Instruction *UseInst, const Loop *L,
DenseMap<Instruction *, PHINode *> &PHIMap) {
PHINode *PHI = 0;
for (Instruction::op_iterator OpI = UseInst->op_begin(),
OpE = UseInst->op_end(); OpI != OpE; ++OpI) {
if (isa<Constant>(*OpI)) continue;
Instruction *OpInst = dyn_cast<Instruction>(*OpI);
if (!OpInst || !canConstantEvolve(OpInst, L)) return 0;
PHINode *P = dyn_cast<PHINode>(OpInst);
if (!P)
P = PHIMap.lookup(OpInst);
if (!P) {
P = getConstantEvolvingPHIOperands(OpInst, L, PHIMap);
PHIMap[OpInst] = P;
}
if (P == 0) return 0; if (PHI && PHI != P) return 0; PHI = P;
}
return PHI;
}
static PHINode *getConstantEvolvingPHI(Value *V, const Loop *L) {
Instruction *I = dyn_cast<Instruction>(V);
if (I == 0 || !canConstantEvolve(I, L)) return 0;
if (PHINode *PN = dyn_cast<PHINode>(I)) {
return PN;
}
DenseMap<Instruction *, PHINode *> PHIMap;
return getConstantEvolvingPHIOperands(I, L, PHIMap);
}
static Constant *EvaluateExpression(Value *V, const Loop *L,
DenseMap<Instruction *, Constant *> &Vals,
const DataLayout *TD,
const TargetLibraryInfo *TLI) {
if (Constant *C = dyn_cast<Constant>(V)) return C;
Instruction *I = dyn_cast<Instruction>(V);
if (!I) return 0;
if (Constant *C = Vals.lookup(I)) return C;
if (!canConstantEvolve(I, L)) return 0;
if (isa<PHINode>(I)) return 0;
std::vector<Constant*> Operands(I->getNumOperands());
for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
Instruction *Operand = dyn_cast<Instruction>(I->getOperand(i));
if (!Operand) {
Operands[i] = dyn_cast<Constant>(I->getOperand(i));
if (!Operands[i]) return 0;
continue;
}
Constant *C = EvaluateExpression(Operand, L, Vals, TD, TLI);
Vals[Operand] = C;
if (!C) return 0;
Operands[i] = C;
}
if (CmpInst *CI = dyn_cast<CmpInst>(I))
return ConstantFoldCompareInstOperands(CI->getPredicate(), Operands[0],
Operands[1], TD, TLI);
if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
if (!LI->isVolatile())
return ConstantFoldLoadFromConstPtr(Operands[0], TD);
}
return ConstantFoldInstOperands(I->getOpcode(), I->getType(), Operands, TD,
TLI);
}
Constant *
ScalarEvolution::getConstantEvolutionLoopExitValue(PHINode *PN,
const APInt &BEs,
const Loop *L) {
DenseMap<PHINode*, Constant*>::const_iterator I =
ConstantEvolutionLoopExitValue.find(PN);
if (I != ConstantEvolutionLoopExitValue.end())
return I->second;
if (BEs.ugt(MaxBruteForceIterations))
return ConstantEvolutionLoopExitValue[PN] = 0;
Constant *&RetVal = ConstantEvolutionLoopExitValue[PN];
DenseMap<Instruction *, Constant *> CurrentIterVals;
BasicBlock *Header = L->getHeader();
assert(PN->getParent() == Header && "Can't evaluate PHI not in loop header!");
bool SecondIsBackedge = L->contains(PN->getIncomingBlock(1));
PHINode *PHI = 0;
for (BasicBlock::iterator I = Header->begin();
(PHI = dyn_cast<PHINode>(I)); ++I) {
Constant *StartCST =
dyn_cast<Constant>(PHI->getIncomingValue(!SecondIsBackedge));
if (StartCST == 0) continue;
CurrentIterVals[PHI] = StartCST;
}
if (!CurrentIterVals.count(PN))
return RetVal = 0;
Value *BEValue = PN->getIncomingValue(SecondIsBackedge);
if (BEs.getActiveBits() >= 32)
return RetVal = 0;
unsigned NumIterations = BEs.getZExtValue(); unsigned IterationNum = 0;
for (; ; ++IterationNum) {
if (IterationNum == NumIterations)
return RetVal = CurrentIterVals[PN];
DenseMap<Instruction *, Constant *> NextIterVals;
Constant *NextPHI = EvaluateExpression(BEValue, L, CurrentIterVals, TD,
TLI);
if (NextPHI == 0)
return 0; NextIterVals[PN] = NextPHI;
bool StoppedEvolving = NextPHI == CurrentIterVals[PN];
SmallVector<std::pair<PHINode *, Constant *>, 8> PHIsToCompute;
for (DenseMap<Instruction *, Constant *>::const_iterator
I = CurrentIterVals.begin(), E = CurrentIterVals.end(); I != E; ++I){
PHINode *PHI = dyn_cast<PHINode>(I->first);
if (!PHI || PHI == PN || PHI->getParent() != Header) continue;
PHIsToCompute.push_back(std::make_pair(PHI, I->second));
}
for (SmallVectorImpl<std::pair<PHINode *, Constant*> >::const_iterator
I = PHIsToCompute.begin(), E = PHIsToCompute.end(); I != E; ++I) {
PHINode *PHI = I->first;
Constant *&NextPHI = NextIterVals[PHI];
if (!NextPHI) { Value *BEValue = PHI->getIncomingValue(SecondIsBackedge);
NextPHI = EvaluateExpression(BEValue, L, CurrentIterVals, TD, TLI);
}
if (NextPHI != I->second)
StoppedEvolving = false;
}
if (StoppedEvolving)
return RetVal = CurrentIterVals[PN];
CurrentIterVals.swap(NextIterVals);
}
}
const SCEV *ScalarEvolution::ComputeExitCountExhaustively(const Loop *L,
Value *Cond,
bool ExitWhen) {
PHINode *PN = getConstantEvolvingPHI(Cond, L);
if (PN == 0) return getCouldNotCompute();
if (PN->getNumIncomingValues() != 2) return getCouldNotCompute();
DenseMap<Instruction *, Constant *> CurrentIterVals;
BasicBlock *Header = L->getHeader();
assert(PN->getParent() == Header && "Can't evaluate PHI not in loop header!");
bool SecondIsBackedge = L->contains(PN->getIncomingBlock(1));
PHINode *PHI = 0;
for (BasicBlock::iterator I = Header->begin();
(PHI = dyn_cast<PHINode>(I)); ++I) {
Constant *StartCST =
dyn_cast<Constant>(PHI->getIncomingValue(!SecondIsBackedge));
if (StartCST == 0) continue;
CurrentIterVals[PHI] = StartCST;
}
if (!CurrentIterVals.count(PN))
return getCouldNotCompute();
unsigned MaxIterations = MaxBruteForceIterations; for (unsigned IterationNum = 0; IterationNum != MaxIterations;++IterationNum){
ConstantInt *CondVal =
dyn_cast_or_null<ConstantInt>(EvaluateExpression(Cond, L, CurrentIterVals,
TD, TLI));
if (!CondVal) return getCouldNotCompute();
if (CondVal->getValue() == uint64_t(ExitWhen)) {
++NumBruteForceTripCountsComputed;
return getConstant(Type::getInt32Ty(getContext()), IterationNum);
}
DenseMap<Instruction *, Constant *> NextIterVals;
SmallVector<PHINode *, 8> PHIsToCompute;
for (DenseMap<Instruction *, Constant *>::const_iterator
I = CurrentIterVals.begin(), E = CurrentIterVals.end(); I != E; ++I){
PHINode *PHI = dyn_cast<PHINode>(I->first);
if (!PHI || PHI->getParent() != Header) continue;
PHIsToCompute.push_back(PHI);
}
for (SmallVectorImpl<PHINode *>::const_iterator I = PHIsToCompute.begin(),
E = PHIsToCompute.end(); I != E; ++I) {
PHINode *PHI = *I;
Constant *&NextPHI = NextIterVals[PHI];
if (NextPHI) continue;
Value *BEValue = PHI->getIncomingValue(SecondIsBackedge);
NextPHI = EvaluateExpression(BEValue, L, CurrentIterVals, TD, TLI);
}
CurrentIterVals.swap(NextIterVals);
}
return getCouldNotCompute();
}
const SCEV *ScalarEvolution::getSCEVAtScope(const SCEV *V, const Loop *L) {
std::map<const Loop *, const SCEV *> &Values = ValuesAtScopes[V];
std::pair<std::map<const Loop *, const SCEV *>::iterator, bool> Pair =
Values.insert(std::make_pair(L, static_cast<const SCEV *>(0)));
if (!Pair.second)
return Pair.first->second ? Pair.first->second : V;
const SCEV *C = computeSCEVAtScope(V, L);
ValuesAtScopes[V][L] = C;
return C;
}
static Constant *BuildConstantFromSCEV(const SCEV *V) {
switch (V->getSCEVType()) {
default: case scCouldNotCompute:
case scAddRecExpr:
break;
case scConstant:
return cast<SCEVConstant>(V)->getValue();
case scUnknown:
return dyn_cast<Constant>(cast<SCEVUnknown>(V)->getValue());
case scSignExtend: {
const SCEVSignExtendExpr *SS = cast<SCEVSignExtendExpr>(V);
if (Constant *CastOp = BuildConstantFromSCEV(SS->getOperand()))
return ConstantExpr::getSExt(CastOp, SS->getType());
break;
}
case scZeroExtend: {
const SCEVZeroExtendExpr *SZ = cast<SCEVZeroExtendExpr>(V);
if (Constant *CastOp = BuildConstantFromSCEV(SZ->getOperand()))
return ConstantExpr::getZExt(CastOp, SZ->getType());
break;
}
case scTruncate: {
const SCEVTruncateExpr *ST = cast<SCEVTruncateExpr>(V);
if (Constant *CastOp = BuildConstantFromSCEV(ST->getOperand()))
return ConstantExpr::getTrunc(CastOp, ST->getType());
break;
}
case scAddExpr: {
const SCEVAddExpr *SA = cast<SCEVAddExpr>(V);
if (Constant *C = BuildConstantFromSCEV(SA->getOperand(0))) {
if (C->getType()->isPointerTy())
C = ConstantExpr::getBitCast(C, Type::getInt8PtrTy(C->getContext()));
for (unsigned i = 1, e = SA->getNumOperands(); i != e; ++i) {
Constant *C2 = BuildConstantFromSCEV(SA->getOperand(i));
if (!C2) return 0;
if (!C->getType()->isPointerTy() && C2->getType()->isPointerTy()) {
std::swap(C, C2);
C = ConstantExpr::getBitCast(C,Type::getInt8PtrTy(C->getContext()));
}
if (C2->getType()->isPointerTy())
return 0;
if (C->getType()->isPointerTy()) {
if (cast<PointerType>(C->getType())->getElementType()->isStructTy())
C2 = ConstantExpr::getIntegerCast(
C2, Type::getInt32Ty(C->getContext()), true);
C = ConstantExpr::getGetElementPtr(C, C2);
} else
C = ConstantExpr::getAdd(C, C2);
}
return C;
}
break;
}
case scMulExpr: {
const SCEVMulExpr *SM = cast<SCEVMulExpr>(V);
if (Constant *C = BuildConstantFromSCEV(SM->getOperand(0))) {
if (C->getType()->isPointerTy()) return 0;
for (unsigned i = 1, e = SM->getNumOperands(); i != e; ++i) {
Constant *C2 = BuildConstantFromSCEV(SM->getOperand(i));
if (!C2 || C2->getType()->isPointerTy()) return 0;
C = ConstantExpr::getMul(C, C2);
}
return C;
}
break;
}
case scUDivExpr: {
const SCEVUDivExpr *SU = cast<SCEVUDivExpr>(V);
if (Constant *LHS = BuildConstantFromSCEV(SU->getLHS()))
if (Constant *RHS = BuildConstantFromSCEV(SU->getRHS()))
if (LHS->getType() == RHS->getType())
return ConstantExpr::getUDiv(LHS, RHS);
break;
}
}
return 0;
}
const SCEV *ScalarEvolution::computeSCEVAtScope(const SCEV *V, const Loop *L) {
if (isa<SCEVConstant>(V)) return 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) if (PHINode *PN = dyn_cast<PHINode>(I))
if (PN->getParent() == LI->getHeader()) {
const SCEV *BackedgeTakenCount = getBackedgeTakenCount(LI);
if (const SCEVConstant *BTCC =
dyn_cast<SCEVConstant>(BackedgeTakenCount)) {
Constant *RV = getConstantEvolutionLoopExitValue(PN,
BTCC->getValue()->getValue(),
LI);
if (RV) return getSCEV(RV);
}
}
if (CanConstantFold(I)) {
SmallVector<Constant *, 4> Operands;
bool MadeImprovement = false;
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);
continue;
}
if (!isSCEVable(Op->getType()))
return V;
const SCEV *OrigV = getSCEV(Op);
const SCEV *OpV = getSCEVAtScope(OrigV, L);
MadeImprovement |= OrigV != OpV;
Constant *C = BuildConstantFromSCEV(OpV);
if (!C) return V;
if (C->getType() != Op->getType())
C = ConstantExpr::getCast(CastInst::getCastOpcode(C, false,
Op->getType(),
false),
C, Op->getType());
Operands.push_back(C);
}
if (MadeImprovement) {
Constant *C = 0;
if (const CmpInst *CI = dyn_cast<CmpInst>(I))
C = ConstantFoldCompareInstOperands(CI->getPredicate(),
Operands[0], Operands[1], TD,
TLI);
else if (const LoadInst *LI = dyn_cast<LoadInst>(I)) {
if (!LI->isVolatile())
C = ConstantFoldLoadFromConstPtr(Operands[0], TD);
} else
C = ConstantFoldInstOperands(I->getOpcode(), I->getType(),
Operands, TD, TLI);
if (!C) return V;
return getSCEV(C);
}
}
}
return V;
}
if (const SCEVCommutativeExpr *Comm = dyn_cast<SCEVCommutativeExpr>(V)) {
for (unsigned i = 0, e = Comm->getNumOperands(); i != e; ++i) {
const SCEV *OpAtScope = getSCEVAtScope(Comm->getOperand(i), L);
if (OpAtScope != Comm->getOperand(i)) {
SmallVector<const SCEV *, 8> NewOps(Comm->op_begin(),
Comm->op_begin()+i);
NewOps.push_back(OpAtScope);
for (++i; i != e; ++i) {
OpAtScope = getSCEVAtScope(Comm->getOperand(i), L);
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);
llvm_unreachable("Unknown commutative SCEV type!");
}
}
return Comm;
}
if (const SCEVUDivExpr *Div = dyn_cast<SCEVUDivExpr>(V)) {
const SCEV *LHS = getSCEVAtScope(Div->getLHS(), L);
const SCEV *RHS = getSCEVAtScope(Div->getRHS(), L);
if (LHS == Div->getLHS() && RHS == Div->getRHS())
return Div; return getUDivExpr(LHS, RHS);
}
if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V)) {
for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) {
const SCEV *OpAtScope = getSCEVAtScope(AddRec->getOperand(i), L);
if (OpAtScope == AddRec->getOperand(i))
continue;
SmallVector<const SCEV *, 8> NewOps(AddRec->op_begin(),
AddRec->op_begin()+i);
NewOps.push_back(OpAtScope);
for (++i; i != e; ++i)
NewOps.push_back(getSCEVAtScope(AddRec->getOperand(i), L));
const SCEV *FoldedRec =
getAddRecExpr(NewOps, AddRec->getLoop(),
AddRec->getNoWrapFlags(SCEV::FlagNW));
AddRec = dyn_cast<SCEVAddRecExpr>(FoldedRec);
if (!AddRec)
return FoldedRec;
break;
}
if (!AddRec->getLoop()->contains(L)) {
const SCEV *BackedgeTakenCount = getBackedgeTakenCount(AddRec->getLoop());
if (BackedgeTakenCount == getCouldNotCompute()) return AddRec;
return AddRec->evaluateAtIteration(BackedgeTakenCount, *this);
}
return AddRec;
}
if (const SCEVZeroExtendExpr *Cast = dyn_cast<SCEVZeroExtendExpr>(V)) {
const SCEV *Op = getSCEVAtScope(Cast->getOperand(), L);
if (Op == Cast->getOperand())
return Cast; return getZeroExtendExpr(Op, Cast->getType());
}
if (const SCEVSignExtendExpr *Cast = dyn_cast<SCEVSignExtendExpr>(V)) {
const SCEV *Op = getSCEVAtScope(Cast->getOperand(), L);
if (Op == Cast->getOperand())
return Cast; return getSignExtendExpr(Op, Cast->getType());
}
if (const SCEVTruncateExpr *Cast = dyn_cast<SCEVTruncateExpr>(V)) {
const SCEV *Op = getSCEVAtScope(Cast->getOperand(), L);
if (Op == Cast->getOperand())
return Cast; return getTruncateExpr(Op, Cast->getType());
}
llvm_unreachable("Unknown SCEV type!");
}
const SCEV *ScalarEvolution::getSCEVAtScope(Value *V, const Loop *L) {
return getSCEVAtScope(getSCEV(V), L);
}
static const SCEV *SolveLinEquationWithOverflow(const APInt &A, const APInt &B,
ScalarEvolution &SE) {
uint32_t BW = A.getBitWidth();
assert(BW == B.getBitWidth() && "Bit widths must be the same.");
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.setBit(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<const SCEV *,const SCEV *>
SolveQuadraticEquation(const SCEVAddRecExpr *AddRec, ScalarEvolution &SE) {
assert(AddRec->getNumOperands() == 3 && "This is not a quadratic chrec!");
const SCEVConstant *LC = dyn_cast<SCEVConstant>(AddRec->getOperand(0));
const SCEVConstant *MC = dyn_cast<SCEVConstant>(AddRec->getOperand(1));
const SCEVConstant *NC = dyn_cast<SCEVConstant>(AddRec->getOperand(2));
if (!LC || !MC || !NC) {
const 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);
if (SqrtTerm.isNegative()) {
const SCEV *CNC = SE.getCouldNotCompute();
return std::make_pair(CNC, CNC);
}
APInt SqrtVal(SqrtTerm.sqrt());
APInt NegB(-B);
APInt TwoA(A << 1);
if (TwoA.isMinValue()) {
const SCEV *CNC = SE.getCouldNotCompute();
return std::make_pair(CNC, CNC);
}
LLVMContext &Context = SE.getContext();
ConstantInt *Solution1 =
ConstantInt::get(Context, (NegB + SqrtVal).sdiv(TwoA));
ConstantInt *Solution2 =
ConstantInt::get(Context, (NegB - SqrtVal).sdiv(TwoA));
return std::make_pair(SE.getConstant(Solution1),
SE.getConstant(Solution2));
} }
ScalarEvolution::ExitLimit
ScalarEvolution::HowFarToZero(const SCEV *V, const Loop *L, bool IsSubExpr) {
if (const SCEVConstant *C = dyn_cast<SCEVConstant>(V)) {
if (C->getValue()->isZero()) return C;
return getCouldNotCompute(); }
const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V);
if (!AddRec || AddRec->getLoop() != L)
return getCouldNotCompute();
if (AddRec->isQuadratic() && AddRec->getType()->isIntegerTy()) {
std::pair<const SCEV *,const SCEV *> Roots =
SolveQuadraticEquation(AddRec, *this);
const SCEVConstant *R1 = dyn_cast<SCEVConstant>(Roots.first);
const SCEVConstant *R2 = dyn_cast<SCEVConstant>(Roots.second);
if (R1 && R2) {
#if 0
dbgs() << "HFTZ: " << *V << " - sol#1: " << *R1
<< " sol#2: " << *R2 << "\n";
#endif
if (ConstantInt *CB =
dyn_cast<ConstantInt>(ConstantExpr::getICmp(CmpInst::ICMP_ULT,
R1->getValue(),
R2->getValue()))) {
if (CB->getZExtValue() == false)
std::swap(R1, R2);
const SCEV *Val = AddRec->evaluateAtIteration(R1, *this);
if (Val->isZero())
return R1; }
}
return getCouldNotCompute();
}
if (!AddRec->isAffine())
return getCouldNotCompute();
const SCEV *Start = getSCEVAtScope(AddRec->getStart(), L->getParentLoop());
const SCEV *Step = getSCEVAtScope(AddRec->getOperand(1), L->getParentLoop());
const SCEVConstant *StepC = dyn_cast<SCEVConstant>(Step);
if (StepC == 0 || StepC->getValue()->equalsInt(0))
return getCouldNotCompute();
bool CountDown = StepC->getValue()->getValue().isNegative();
const SCEV *Distance = CountDown ? Start : getNegativeSCEV(Start);
if (StepC->getValue()->equalsInt(1) || StepC->getValue()->isAllOnesValue()) {
ConstantRange CR = getUnsignedRange(Start);
const SCEV *MaxBECount;
if (!CountDown && CR.getUnsignedMin().isMinValue())
MaxBECount = CR.getUnsignedMax().isMinValue()
? getConstant(APInt::getMinValue(CR.getBitWidth()))
: getConstant(APInt::getMaxValue(CR.getBitWidth()));
else
MaxBECount = getConstant(CountDown ? CR.getUnsignedMax()
: -CR.getUnsignedMin());
return ExitLimit(Distance, MaxBECount);
}
if (!IsSubExpr && AddRec->getNoWrapFlags(SCEV::FlagNW))
return getUDivExpr(Distance, CountDown ? getNegativeSCEV(Step) : Step);
if (const SCEVConstant *StartC = dyn_cast<SCEVConstant>(Start))
return SolveLinEquationWithOverflow(StepC->getValue()->getValue(),
-StartC->getValue()->getValue(),
*this);
return getCouldNotCompute();
}
ScalarEvolution::ExitLimit
ScalarEvolution::HowFarToNonZero(const SCEV *V, const Loop *L) {
if (const SCEVConstant *C = dyn_cast<SCEVConstant>(V)) {
if (!C->getValue()->isNullValue())
return getConstant(C->getType(), 0);
return getCouldNotCompute(); }
return getCouldNotCompute();
}
std::pair<BasicBlock *, BasicBlock *>
ScalarEvolution::getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB) {
if (BasicBlock *Pred = BB->getSinglePredecessor())
return std::make_pair(Pred, BB);
if (Loop *L = LI->getLoopFor(BB))
return std::make_pair(L->getLoopPredecessor(), L->getHeader());
return std::pair<BasicBlock *, BasicBlock *>();
}
static bool HasSameValue(const SCEV *A, const SCEV *B) {
if (A == B) return true;
if (const SCEVUnknown *AU = dyn_cast<SCEVUnknown>(A))
if (const SCEVUnknown *BU = dyn_cast<SCEVUnknown>(B))
if (const Instruction *AI = dyn_cast<Instruction>(AU->getValue()))
if (const Instruction *BI = dyn_cast<Instruction>(BU->getValue()))
if (AI->isIdenticalTo(BI) && !AI->mayReadFromMemory())
return true;
return false;
}
bool ScalarEvolution::SimplifyICmpOperands(ICmpInst::Predicate &Pred,
const SCEV *&LHS, const SCEV *&RHS,
unsigned Depth) {
bool Changed = false;
if (Depth >= 3)
return false;
if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(LHS)) {
if (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS)) {
if (ConstantExpr::getICmp(Pred,
LHSC->getValue(),
RHSC->getValue())->isNullValue())
goto trivially_false;
else
goto trivially_true;
}
std::swap(LHS, RHS);
Pred = ICmpInst::getSwappedPredicate(Pred);
Changed = true;
}
if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(RHS)) {
const Loop *L = AR->getLoop();
if (isLoopInvariant(LHS, L) && properlyDominates(LHS, L->getHeader())) {
std::swap(LHS, RHS);
Pred = ICmpInst::getSwappedPredicate(Pred);
Changed = true;
}
}
if (const SCEVConstant *RC = dyn_cast<SCEVConstant>(RHS)) {
const APInt &RA = RC->getValue()->getValue();
switch (Pred) {
default: llvm_unreachable("Unexpected ICmpInst::Predicate value!");
case ICmpInst::ICMP_EQ:
case ICmpInst::ICMP_NE:
if (!RA)
if (const SCEVAddExpr *AE = dyn_cast<SCEVAddExpr>(LHS))
if (const SCEVMulExpr *ME = dyn_cast<SCEVMulExpr>(AE->getOperand(0)))
if (AE->getNumOperands() == 2 && ME->getNumOperands() == 2 &&
ME->getOperand(0)->isAllOnesValue()) {
RHS = AE->getOperand(1);
LHS = ME->getOperand(1);
Changed = true;
}
break;
case ICmpInst::ICMP_UGE:
if ((RA - 1).isMinValue()) {
Pred = ICmpInst::ICMP_NE;
RHS = getConstant(RA - 1);
Changed = true;
break;
}
if (RA.isMaxValue()) {
Pred = ICmpInst::ICMP_EQ;
Changed = true;
break;
}
if (RA.isMinValue()) goto trivially_true;
Pred = ICmpInst::ICMP_UGT;
RHS = getConstant(RA - 1);
Changed = true;
break;
case ICmpInst::ICMP_ULE:
if ((RA + 1).isMaxValue()) {
Pred = ICmpInst::ICMP_NE;
RHS = getConstant(RA + 1);
Changed = true;
break;
}
if (RA.isMinValue()) {
Pred = ICmpInst::ICMP_EQ;
Changed = true;
break;
}
if (RA.isMaxValue()) goto trivially_true;
Pred = ICmpInst::ICMP_ULT;
RHS = getConstant(RA + 1);
Changed = true;
break;
case ICmpInst::ICMP_SGE:
if ((RA - 1).isMinSignedValue()) {
Pred = ICmpInst::ICMP_NE;
RHS = getConstant(RA - 1);
Changed = true;
break;
}
if (RA.isMaxSignedValue()) {
Pred = ICmpInst::ICMP_EQ;
Changed = true;
break;
}
if (RA.isMinSignedValue()) goto trivially_true;
Pred = ICmpInst::ICMP_SGT;
RHS = getConstant(RA - 1);
Changed = true;
break;
case ICmpInst::ICMP_SLE:
if ((RA + 1).isMaxSignedValue()) {
Pred = ICmpInst::ICMP_NE;
RHS = getConstant(RA + 1);
Changed = true;
break;
}
if (RA.isMinSignedValue()) {
Pred = ICmpInst::ICMP_EQ;
Changed = true;
break;
}
if (RA.isMaxSignedValue()) goto trivially_true;
Pred = ICmpInst::ICMP_SLT;
RHS = getConstant(RA + 1);
Changed = true;
break;
case ICmpInst::ICMP_UGT:
if (RA.isMinValue()) {
Pred = ICmpInst::ICMP_NE;
Changed = true;
break;
}
if ((RA + 1).isMaxValue()) {
Pred = ICmpInst::ICMP_EQ;
RHS = getConstant(RA + 1);
Changed = true;
break;
}
if (RA.isMaxValue()) goto trivially_false;
break;
case ICmpInst::ICMP_ULT:
if (RA.isMaxValue()) {
Pred = ICmpInst::ICMP_NE;
Changed = true;
break;
}
if ((RA - 1).isMinValue()) {
Pred = ICmpInst::ICMP_EQ;
RHS = getConstant(RA - 1);
Changed = true;
break;
}
if (RA.isMinValue()) goto trivially_false;
break;
case ICmpInst::ICMP_SGT:
if (RA.isMinSignedValue()) {
Pred = ICmpInst::ICMP_NE;
Changed = true;
break;
}
if ((RA + 1).isMaxSignedValue()) {
Pred = ICmpInst::ICMP_EQ;
RHS = getConstant(RA + 1);
Changed = true;
break;
}
if (RA.isMaxSignedValue()) goto trivially_false;
break;
case ICmpInst::ICMP_SLT:
if (RA.isMaxSignedValue()) {
Pred = ICmpInst::ICMP_NE;
Changed = true;
break;
}
if ((RA - 1).isMinSignedValue()) {
Pred = ICmpInst::ICMP_EQ;
RHS = getConstant(RA - 1);
Changed = true;
break;
}
if (RA.isMinSignedValue()) goto trivially_false;
break;
}
}
if (HasSameValue(LHS, RHS)) {
if (ICmpInst::isTrueWhenEqual(Pred))
goto trivially_true;
if (ICmpInst::isFalseWhenEqual(Pred))
goto trivially_false;
}
switch (Pred) {
case ICmpInst::ICMP_SLE:
if (!getSignedRange(RHS).getSignedMax().isMaxSignedValue()) {
RHS = getAddExpr(getConstant(RHS->getType(), 1, true), RHS,
SCEV::FlagNSW);
Pred = ICmpInst::ICMP_SLT;
Changed = true;
} else if (!getSignedRange(LHS).getSignedMin().isMinSignedValue()) {
LHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), LHS,
SCEV::FlagNSW);
Pred = ICmpInst::ICMP_SLT;
Changed = true;
}
break;
case ICmpInst::ICMP_SGE:
if (!getSignedRange(RHS).getSignedMin().isMinSignedValue()) {
RHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), RHS,
SCEV::FlagNSW);
Pred = ICmpInst::ICMP_SGT;
Changed = true;
} else if (!getSignedRange(LHS).getSignedMax().isMaxSignedValue()) {
LHS = getAddExpr(getConstant(RHS->getType(), 1, true), LHS,
SCEV::FlagNSW);
Pred = ICmpInst::ICMP_SGT;
Changed = true;
}
break;
case ICmpInst::ICMP_ULE:
if (!getUnsignedRange(RHS).getUnsignedMax().isMaxValue()) {
RHS = getAddExpr(getConstant(RHS->getType(), 1, true), RHS,
SCEV::FlagNUW);
Pred = ICmpInst::ICMP_ULT;
Changed = true;
} else if (!getUnsignedRange(LHS).getUnsignedMin().isMinValue()) {
LHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), LHS,
SCEV::FlagNUW);
Pred = ICmpInst::ICMP_ULT;
Changed = true;
}
break;
case ICmpInst::ICMP_UGE:
if (!getUnsignedRange(RHS).getUnsignedMin().isMinValue()) {
RHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), RHS,
SCEV::FlagNUW);
Pred = ICmpInst::ICMP_UGT;
Changed = true;
} else if (!getUnsignedRange(LHS).getUnsignedMax().isMaxValue()) {
LHS = getAddExpr(getConstant(RHS->getType(), 1, true), LHS,
SCEV::FlagNUW);
Pred = ICmpInst::ICMP_UGT;
Changed = true;
}
break;
default:
break;
}
if (Changed)
return SimplifyICmpOperands(Pred, LHS, RHS, Depth+1);
return Changed;
trivially_true:
LHS = RHS = getConstant(ConstantInt::getFalse(getContext()));
Pred = ICmpInst::ICMP_EQ;
return true;
trivially_false:
LHS = RHS = getConstant(ConstantInt::getFalse(getContext()));
Pred = ICmpInst::ICMP_NE;
return true;
}
bool ScalarEvolution::isKnownNegative(const SCEV *S) {
return getSignedRange(S).getSignedMax().isNegative();
}
bool ScalarEvolution::isKnownPositive(const SCEV *S) {
return getSignedRange(S).getSignedMin().isStrictlyPositive();
}
bool ScalarEvolution::isKnownNonNegative(const SCEV *S) {
return !getSignedRange(S).getSignedMin().isNegative();
}
bool ScalarEvolution::isKnownNonPositive(const SCEV *S) {
return !getSignedRange(S).getSignedMax().isStrictlyPositive();
}
bool ScalarEvolution::isKnownNonZero(const SCEV *S) {
return isKnownNegative(S) || isKnownPositive(S);
}
bool ScalarEvolution::isKnownPredicate(ICmpInst::Predicate Pred,
const SCEV *LHS, const SCEV *RHS) {
(void)SimplifyICmpOperands(Pred, LHS, RHS);
if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(LHS))
if (isLoopEntryGuardedByCond(
AR->getLoop(), Pred, AR->getStart(), RHS) &&
isLoopBackedgeGuardedByCond(
AR->getLoop(), Pred, AR->getPostIncExpr(*this), RHS))
return true;
if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(RHS))
if (isLoopEntryGuardedByCond(
AR->getLoop(), Pred, LHS, AR->getStart()) &&
isLoopBackedgeGuardedByCond(
AR->getLoop(), Pred, LHS, AR->getPostIncExpr(*this)))
return true;
return isKnownPredicateWithRanges(Pred, LHS, RHS);
}
bool
ScalarEvolution::isKnownPredicateWithRanges(ICmpInst::Predicate Pred,
const SCEV *LHS, const SCEV *RHS) {
if (HasSameValue(LHS, RHS))
return ICmpInst::isTrueWhenEqual(Pred);
switch (Pred) {
default:
llvm_unreachable("Unexpected ICmpInst::Predicate value!");
case ICmpInst::ICMP_SGT:
Pred = ICmpInst::ICMP_SLT;
std::swap(LHS, RHS);
case ICmpInst::ICMP_SLT: {
ConstantRange LHSRange = getSignedRange(LHS);
ConstantRange RHSRange = getSignedRange(RHS);
if (LHSRange.getSignedMax().slt(RHSRange.getSignedMin()))
return true;
if (LHSRange.getSignedMin().sge(RHSRange.getSignedMax()))
return false;
break;
}
case ICmpInst::ICMP_SGE:
Pred = ICmpInst::ICMP_SLE;
std::swap(LHS, RHS);
case ICmpInst::ICMP_SLE: {
ConstantRange LHSRange = getSignedRange(LHS);
ConstantRange RHSRange = getSignedRange(RHS);
if (LHSRange.getSignedMax().sle(RHSRange.getSignedMin()))
return true;
if (LHSRange.getSignedMin().sgt(RHSRange.getSignedMax()))
return false;
break;
}
case ICmpInst::ICMP_UGT:
Pred = ICmpInst::ICMP_ULT;
std::swap(LHS, RHS);
case ICmpInst::ICMP_ULT: {
ConstantRange LHSRange = getUnsignedRange(LHS);
ConstantRange RHSRange = getUnsignedRange(RHS);
if (LHSRange.getUnsignedMax().ult(RHSRange.getUnsignedMin()))
return true;
if (LHSRange.getUnsignedMin().uge(RHSRange.getUnsignedMax()))
return false;
break;
}
case ICmpInst::ICMP_UGE:
Pred = ICmpInst::ICMP_ULE;
std::swap(LHS, RHS);
case ICmpInst::ICMP_ULE: {
ConstantRange LHSRange = getUnsignedRange(LHS);
ConstantRange RHSRange = getUnsignedRange(RHS);
if (LHSRange.getUnsignedMax().ule(RHSRange.getUnsignedMin()))
return true;
if (LHSRange.getUnsignedMin().ugt(RHSRange.getUnsignedMax()))
return false;
break;
}
case ICmpInst::ICMP_NE: {
if (getUnsignedRange(LHS).intersectWith(getUnsignedRange(RHS)).isEmptySet())
return true;
if (getSignedRange(LHS).intersectWith(getSignedRange(RHS)).isEmptySet())
return true;
const SCEV *Diff = getMinusSCEV(LHS, RHS);
if (isKnownNonZero(Diff))
return true;
break;
}
case ICmpInst::ICMP_EQ:
break;
}
return false;
}
bool
ScalarEvolution::isLoopBackedgeGuardedByCond(const Loop *L,
ICmpInst::Predicate Pred,
const SCEV *LHS, const SCEV *RHS) {
if (!L) return true;
BasicBlock *Latch = L->getLoopLatch();
if (!Latch)
return false;
BranchInst *LoopContinuePredicate =
dyn_cast<BranchInst>(Latch->getTerminator());
if (!LoopContinuePredicate ||
LoopContinuePredicate->isUnconditional())
return false;
return isImpliedCond(Pred, LHS, RHS,
LoopContinuePredicate->getCondition(),
LoopContinuePredicate->getSuccessor(0) != L->getHeader());
}
bool
ScalarEvolution::isLoopEntryGuardedByCond(const Loop *L,
ICmpInst::Predicate Pred,
const SCEV *LHS, const SCEV *RHS) {
if (!L) return false;
for (std::pair<BasicBlock *, BasicBlock *>
Pair(L->getLoopPredecessor(), L->getHeader());
Pair.first;
Pair = getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
BranchInst *LoopEntryPredicate =
dyn_cast<BranchInst>(Pair.first->getTerminator());
if (!LoopEntryPredicate ||
LoopEntryPredicate->isUnconditional())
continue;
if (isImpliedCond(Pred, LHS, RHS,
LoopEntryPredicate->getCondition(),
LoopEntryPredicate->getSuccessor(0) != Pair.second))
return true;
}
return false;
}
struct MarkPendingLoopPredicate {
Value *Cond;
DenseSet<Value*> &LoopPreds;
bool Pending;
MarkPendingLoopPredicate(Value *C, DenseSet<Value*> &LP)
: Cond(C), LoopPreds(LP) {
Pending = !LoopPreds.insert(Cond).second;
}
~MarkPendingLoopPredicate() {
if (!Pending)
LoopPreds.erase(Cond);
}
};
bool ScalarEvolution::isImpliedCond(ICmpInst::Predicate Pred,
const SCEV *LHS, const SCEV *RHS,
Value *FoundCondValue,
bool Inverse) {
MarkPendingLoopPredicate Mark(FoundCondValue, PendingLoopPredicates);
if (Mark.Pending)
return false;
if (BinaryOperator *BO = dyn_cast<BinaryOperator>(FoundCondValue)) {
if (BO->getOpcode() == Instruction::And) {
if (!Inverse)
return isImpliedCond(Pred, LHS, RHS, BO->getOperand(0), Inverse) ||
isImpliedCond(Pred, LHS, RHS, BO->getOperand(1), Inverse);
} else if (BO->getOpcode() == Instruction::Or) {
if (Inverse)
return isImpliedCond(Pred, LHS, RHS, BO->getOperand(0), Inverse) ||
isImpliedCond(Pred, LHS, RHS, BO->getOperand(1), Inverse);
}
}
ICmpInst *ICI = dyn_cast<ICmpInst>(FoundCondValue);
if (!ICI) return false;
if (getTypeSizeInBits(LHS->getType()) <
getTypeSizeInBits(ICI->getOperand(0)->getType()))
return false;
ICmpInst::Predicate FoundPred;
if (Inverse)
FoundPred = ICI->getInversePredicate();
else
FoundPred = ICI->getPredicate();
const SCEV *FoundLHS = getSCEV(ICI->getOperand(0));
const SCEV *FoundRHS = getSCEV(ICI->getOperand(1));
if (getTypeSizeInBits(LHS->getType()) >
getTypeSizeInBits(FoundLHS->getType())) {
if (CmpInst::isSigned(Pred)) {
FoundLHS = getSignExtendExpr(FoundLHS, LHS->getType());
FoundRHS = getSignExtendExpr(FoundRHS, LHS->getType());
} else {
FoundLHS = getZeroExtendExpr(FoundLHS, LHS->getType());
FoundRHS = getZeroExtendExpr(FoundRHS, LHS->getType());
}
}
if (SimplifyICmpOperands(Pred, LHS, RHS))
if (LHS == RHS)
return CmpInst::isTrueWhenEqual(Pred);
if (SimplifyICmpOperands(FoundPred, FoundLHS, FoundRHS))
if (FoundLHS == FoundRHS)
return CmpInst::isFalseWhenEqual(FoundPred);
if (LHS == FoundRHS || RHS == FoundLHS) {
if (isa<SCEVConstant>(RHS)) {
std::swap(FoundLHS, FoundRHS);
FoundPred = ICmpInst::getSwappedPredicate(FoundPred);
} else {
std::swap(LHS, RHS);
Pred = ICmpInst::getSwappedPredicate(Pred);
}
}
if (FoundPred == Pred)
return isImpliedCondOperands(Pred, LHS, RHS, FoundLHS, FoundRHS);
if (ICmpInst::getSwappedPredicate(FoundPred) == Pred) {
if (isa<SCEVConstant>(RHS))
return isImpliedCondOperands(Pred, LHS, RHS, FoundRHS, FoundLHS);
else
return isImpliedCondOperands(ICmpInst::getSwappedPredicate(Pred),
RHS, LHS, FoundLHS, FoundRHS);
}
if (FoundPred == ICmpInst::ICMP_EQ)
if (ICmpInst::isTrueWhenEqual(Pred))
if (isImpliedCondOperands(Pred, LHS, RHS, FoundLHS, FoundRHS))
return true;
if (Pred == ICmpInst::ICMP_NE)
if (!ICmpInst::isTrueWhenEqual(FoundPred))
if (isImpliedCondOperands(FoundPred, LHS, RHS, FoundLHS, FoundRHS))
return true;
return false;
}
bool ScalarEvolution::isImpliedCondOperands(ICmpInst::Predicate Pred,
const SCEV *LHS, const SCEV *RHS,
const SCEV *FoundLHS,
const SCEV *FoundRHS) {
return isImpliedCondOperandsHelper(Pred, LHS, RHS,
FoundLHS, FoundRHS) ||
isImpliedCondOperandsHelper(Pred, LHS, RHS,
getNotSCEV(FoundRHS),
getNotSCEV(FoundLHS));
}
bool
ScalarEvolution::isImpliedCondOperandsHelper(ICmpInst::Predicate Pred,
const SCEV *LHS, const SCEV *RHS,
const SCEV *FoundLHS,
const SCEV *FoundRHS) {
switch (Pred) {
default: llvm_unreachable("Unexpected ICmpInst::Predicate value!");
case ICmpInst::ICMP_EQ:
case ICmpInst::ICMP_NE:
if (HasSameValue(LHS, FoundLHS) && HasSameValue(RHS, FoundRHS))
return true;
break;
case ICmpInst::ICMP_SLT:
case ICmpInst::ICMP_SLE:
if (isKnownPredicateWithRanges(ICmpInst::ICMP_SLE, LHS, FoundLHS) &&
isKnownPredicateWithRanges(ICmpInst::ICMP_SGE, RHS, FoundRHS))
return true;
break;
case ICmpInst::ICMP_SGT:
case ICmpInst::ICMP_SGE:
if (isKnownPredicateWithRanges(ICmpInst::ICMP_SGE, LHS, FoundLHS) &&
isKnownPredicateWithRanges(ICmpInst::ICMP_SLE, RHS, FoundRHS))
return true;
break;
case ICmpInst::ICMP_ULT:
case ICmpInst::ICMP_ULE:
if (isKnownPredicateWithRanges(ICmpInst::ICMP_ULE, LHS, FoundLHS) &&
isKnownPredicateWithRanges(ICmpInst::ICMP_UGE, RHS, FoundRHS))
return true;
break;
case ICmpInst::ICMP_UGT:
case ICmpInst::ICMP_UGE:
if (isKnownPredicateWithRanges(ICmpInst::ICMP_UGE, LHS, FoundLHS) &&
isKnownPredicateWithRanges(ICmpInst::ICMP_ULE, RHS, FoundRHS))
return true;
break;
}
return false;
}
const SCEV *ScalarEvolution::getBECount(const SCEV *Start,
const SCEV *End,
const SCEV *Step,
bool NoWrap) {
assert(!isKnownNegative(Step) &&
"This code doesn't handle negative strides yet!");
Type *Ty = Start->getType();
if (Start == End)
return getConstant(Ty, 0);
const SCEV *NegOne = getConstant(Ty, (uint64_t)-1);
const SCEV *Diff = getMinusSCEV(End, Start);
const SCEV *RoundUp = getAddExpr(Step, NegOne);
const SCEV *Add = getAddExpr(Diff, RoundUp);
if (!NoWrap) {
Type *WideTy = IntegerType::get(getContext(),
getTypeSizeInBits(Ty) + 1);
const SCEV *EDiff = getZeroExtendExpr(Diff, WideTy);
const SCEV *ERoundUp = getZeroExtendExpr(RoundUp, WideTy);
const SCEV *OperandExtendedAdd = getAddExpr(EDiff, ERoundUp);
if (getZeroExtendExpr(Add, WideTy) != OperandExtendedAdd)
return getCouldNotCompute();
}
return getUDivExpr(Add, Step);
}
ScalarEvolution::ExitLimit
ScalarEvolution::HowManyLessThans(const SCEV *LHS, const SCEV *RHS,
const Loop *L, bool isSigned,
bool IsSubExpr) {
if (!isLoopInvariant(RHS, L)) return getCouldNotCompute();
const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS);
if (!AddRec || AddRec->getLoop() != L)
return getCouldNotCompute();
bool NoWrap = false;
if (!IsSubExpr) {
NoWrap = AddRec->getNoWrapFlags(
(SCEV::NoWrapFlags)(((isSigned ? SCEV::FlagNSW : SCEV::FlagNUW))
| SCEV::FlagNW));
}
if (AddRec->isAffine()) {
unsigned BitWidth = getTypeSizeInBits(AddRec->getType());
const SCEV *Step = AddRec->getStepRecurrence(*this);
if (Step->isZero())
return getCouldNotCompute();
if (Step->isOne()) {
} else if (isKnownPositive(Step)) {
const SCEV *One = getConstant(Step->getType(), 1);
if (isSigned) {
APInt Max = APInt::getSignedMaxValue(BitWidth);
if ((Max - getSignedRange(getMinusSCEV(Step, One)).getSignedMax())
.slt(getSignedRange(RHS).getSignedMax()))
return getCouldNotCompute();
} else {
APInt Max = APInt::getMaxValue(BitWidth);
if ((Max - getUnsignedRange(getMinusSCEV(Step, One)).getUnsignedMax())
.ult(getUnsignedRange(RHS).getUnsignedMax()))
return getCouldNotCompute();
}
} else
return getCouldNotCompute();
const SCEV *Start = AddRec->getOperand(0);
const SCEV *MinStart = getConstant(isSigned ?
getSignedRange(Start).getSignedMin() :
getUnsignedRange(Start).getUnsignedMin());
const SCEV *End = RHS;
if (!isLoopEntryGuardedByCond(L,
isSigned ? ICmpInst::ICMP_SLT :
ICmpInst::ICMP_ULT,
getMinusSCEV(Start, Step), RHS))
End = isSigned ? getSMaxExpr(RHS, Start)
: getUMaxExpr(RHS, Start);
const SCEV *MaxEnd = getConstant(isSigned ?
getSignedRange(End).getSignedMax() :
getUnsignedRange(End).getUnsignedMax());
const SCEV *StepMinusOne = getMinusSCEV(Step,
getConstant(Step->getType(), 1));
MaxEnd = isSigned ?
getSMinExpr(MaxEnd,
getMinusSCEV(getConstant(APInt::getSignedMaxValue(BitWidth)),
StepMinusOne)) :
getUMinExpr(MaxEnd,
getMinusSCEV(getConstant(APInt::getMaxValue(BitWidth)),
StepMinusOne));
const SCEV *BECount = getBECount(Start, End, Step, NoWrap);
const SCEV *MaxBECount = isa<SCEVConstant>(BECount) ? BECount
: getBECount(MinStart, MaxEnd, Step, NoWrap);
if (isa<SCEVCouldNotCompute>(MaxBECount))
MaxBECount = BECount;
return ExitLimit(BECount, MaxBECount);
}
return getCouldNotCompute();
}
const SCEV *SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range,
ScalarEvolution &SE) const {
if (Range.isFullSet()) return SE.getCouldNotCompute();
if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(getStart()))
if (!SC->getValue()->isZero()) {
SmallVector<const SCEV *, 4> Operands(op_begin(), op_end());
Operands[0] = SE.getConstant(SC->getType(), 0);
const SCEV *Shifted = SE.getAddRecExpr(Operands, getLoop(),
getNoWrapFlags(FlagNW));
if (const 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(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(SE.getContext(), ExitVal);
ConstantInt *Val = EvaluateConstantChrecAtConstant(this, ExitValue, SE);
if (Range.contains(Val->getValue()))
return SE.getCouldNotCompute();
assert(Range.contains(
EvaluateConstantChrecAtConstant(this,
ConstantInt::get(SE.getContext(), ExitVal - One), SE)->getValue()) &&
"Linear scev computation is off in a bad way!");
return SE.getConstant(ExitValue);
} else if (isQuadratic()) {
SmallVector<const SCEV *, 4> NewOps(op_begin(), op_end());
NewOps[0] = SE.getNegativeSCEV(SE.getConstant(Range.getUpper()));
const SCEV *NewAddRec = SE.getAddRecExpr(NewOps, getLoop(),
FlagAnyWrap);
std::pair<const SCEV *,const SCEV *> Roots =
SolveQuadraticEquation(cast<SCEVAddRecExpr>(NewAddRec), SE);
const SCEVConstant *R1 = dyn_cast<SCEVConstant>(Roots.first);
const SCEVConstant *R2 = dyn_cast<SCEVConstant>(Roots.second);
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(SE.getContext(), 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(SE.getContext(), R1->getValue()->getValue()-1);
R1Val = EvaluateConstantChrecAtConstant(this, NextVal, SE);
if (Range.contains(R1Val->getValue()))
return R1;
return SE.getCouldNotCompute(); }
}
}
return SE.getCouldNotCompute();
}
void ScalarEvolution::SCEVCallbackVH::deleted() {
assert(SE && "SCEVCallbackVH called with a null ScalarEvolution!");
if (PHINode *PN = dyn_cast<PHINode>(getValPtr()))
SE->ConstantEvolutionLoopExitValue.erase(PN);
SE->ValueExprMap.erase(getValPtr());
}
void ScalarEvolution::SCEVCallbackVH::allUsesReplacedWith(Value *V) {
assert(SE && "SCEVCallbackVH called with a null ScalarEvolution!");
Value *Old = getValPtr();
SmallVector<User *, 16> Worklist;
SmallPtrSet<User *, 8> Visited;
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();
if (U == Old)
continue;
if (!Visited.insert(U))
continue;
if (PHINode *PN = dyn_cast<PHINode>(U))
SE->ConstantEvolutionLoopExitValue.erase(PN);
SE->ValueExprMap.erase(U);
for (Value::use_iterator UI = U->use_begin(), UE = U->use_end();
UI != UE; ++UI)
Worklist.push_back(*UI);
}
if (PHINode *PN = dyn_cast<PHINode>(Old))
SE->ConstantEvolutionLoopExitValue.erase(PN);
SE->ValueExprMap.erase(Old);
}
ScalarEvolution::SCEVCallbackVH::SCEVCallbackVH(Value *V, ScalarEvolution *se)
: CallbackVH(V), SE(se) {}
ScalarEvolution::ScalarEvolution()
: FunctionPass(ID), FirstUnknown(0) {
initializeScalarEvolutionPass(*PassRegistry::getPassRegistry());
}
bool ScalarEvolution::runOnFunction(Function &F) {
this->F = &F;
LI = &getAnalysis<LoopInfo>();
TD = getAnalysisIfAvailable<DataLayout>();
TLI = &getAnalysis<TargetLibraryInfo>();
DT = &getAnalysis<DominatorTree>();
return false;
}
void ScalarEvolution::releaseMemory() {
for (SCEVUnknown *U = FirstUnknown; U; U = U->Next)
U->~SCEVUnknown();
FirstUnknown = 0;
ValueExprMap.clear();
for (DenseMap<const Loop*, BackedgeTakenInfo>::iterator I =
BackedgeTakenCounts.begin(), E = BackedgeTakenCounts.end();
I != E; ++I) {
I->second.clear();
}
assert(PendingLoopPredicates.empty() && "isImpliedCond garbage");
BackedgeTakenCounts.clear();
ConstantEvolutionLoopExitValue.clear();
ValuesAtScopes.clear();
LoopDispositions.clear();
BlockDispositions.clear();
UnsignedRanges.clear();
SignedRanges.clear();
UniqueSCEVs.clear();
SCEVAllocator.Reset();
}
void ScalarEvolution::getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesAll();
AU.addRequiredTransitive<LoopInfo>();
AU.addRequiredTransitive<DominatorTree>();
AU.addRequired<TargetLibraryInfo>();
}
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 ";
WriteAsOperand(OS, L->getHeader(), false);
OS << ": ";
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"
"Loop ";
WriteAsOperand(OS, L->getHeader(), false);
OS << ": ";
if (!isa<SCEVCouldNotCompute>(SE->getMaxBackedgeTakenCount(L))) {
OS << "max backedge-taken count is " << *SE->getMaxBackedgeTakenCount(L);
} else {
OS << "Unpredictable max backedge-taken count. ";
}
OS << "\n";
}
void ScalarEvolution::print(raw_ostream &OS, const Module *) const {
ScalarEvolution &SE = *const_cast<ScalarEvolution *>(this);
OS << "Classifying expressions for: ";
WriteAsOperand(OS, F, false);
OS << "\n";
for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)
if (isSCEVable(I->getType()) && !isa<CmpInst>(*I)) {
OS << *I << '\n';
OS << " --> ";
const SCEV *SV = SE.getSCEV(&*I);
SV->print(OS);
const Loop *L = LI->getLoopFor((*I).getParent());
const SCEV *AtUse = SE.getSCEVAtScope(SV, L);
if (AtUse != SV) {
OS << " --> ";
AtUse->print(OS);
}
if (L) {
OS << "\t\t" "Exits: ";
const SCEV *ExitValue = SE.getSCEVAtScope(SV, L->getParentLoop());
if (!SE.isLoopInvariant(ExitValue, L)) {
OS << "<<Unknown>>";
} else {
OS << *ExitValue;
}
}
OS << "\n";
}
OS << "Determining loop execution counts for: ";
WriteAsOperand(OS, F, false);
OS << "\n";
for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I)
PrintLoopInfo(OS, &SE, *I);
}
ScalarEvolution::LoopDisposition
ScalarEvolution::getLoopDisposition(const SCEV *S, const Loop *L) {
std::map<const Loop *, LoopDisposition> &Values = LoopDispositions[S];
std::pair<std::map<const Loop *, LoopDisposition>::iterator, bool> Pair =
Values.insert(std::make_pair(L, LoopVariant));
if (!Pair.second)
return Pair.first->second;
LoopDisposition D = computeLoopDisposition(S, L);
return LoopDispositions[S][L] = D;
}
ScalarEvolution::LoopDisposition
ScalarEvolution::computeLoopDisposition(const SCEV *S, const Loop *L) {
switch (S->getSCEVType()) {
case scConstant:
return LoopInvariant;
case scTruncate:
case scZeroExtend:
case scSignExtend:
return getLoopDisposition(cast<SCEVCastExpr>(S)->getOperand(), L);
case scAddRecExpr: {
const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(S);
if (AR->getLoop() == L)
return LoopComputable;
if (!L)
return LoopVariant;
if (L->contains(AR->getLoop()))
return LoopVariant;
if (AR->getLoop()->contains(L))
return LoopInvariant;
for (SCEVAddRecExpr::op_iterator I = AR->op_begin(), E = AR->op_end();
I != E; ++I)
if (!isLoopInvariant(*I, L))
return LoopVariant;
return LoopInvariant;
}
case scAddExpr:
case scMulExpr:
case scUMaxExpr:
case scSMaxExpr: {
const SCEVNAryExpr *NAry = cast<SCEVNAryExpr>(S);
bool HasVarying = false;
for (SCEVNAryExpr::op_iterator I = NAry->op_begin(), E = NAry->op_end();
I != E; ++I) {
LoopDisposition D = getLoopDisposition(*I, L);
if (D == LoopVariant)
return LoopVariant;
if (D == LoopComputable)
HasVarying = true;
}
return HasVarying ? LoopComputable : LoopInvariant;
}
case scUDivExpr: {
const SCEVUDivExpr *UDiv = cast<SCEVUDivExpr>(S);
LoopDisposition LD = getLoopDisposition(UDiv->getLHS(), L);
if (LD == LoopVariant)
return LoopVariant;
LoopDisposition RD = getLoopDisposition(UDiv->getRHS(), L);
if (RD == LoopVariant)
return LoopVariant;
return (LD == LoopInvariant && RD == LoopInvariant) ?
LoopInvariant : LoopComputable;
}
case scUnknown:
if (Instruction *I = dyn_cast<Instruction>(cast<SCEVUnknown>(S)->getValue()))
return (L && !L->contains(I)) ? LoopInvariant : LoopVariant;
return LoopInvariant;
case scCouldNotCompute:
llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
default: llvm_unreachable("Unknown SCEV kind!");
}
}
bool ScalarEvolution::isLoopInvariant(const SCEV *S, const Loop *L) {
return getLoopDisposition(S, L) == LoopInvariant;
}
bool ScalarEvolution::hasComputableLoopEvolution(const SCEV *S, const Loop *L) {
return getLoopDisposition(S, L) == LoopComputable;
}
ScalarEvolution::BlockDisposition
ScalarEvolution::getBlockDisposition(const SCEV *S, const BasicBlock *BB) {
std::map<const BasicBlock *, BlockDisposition> &Values = BlockDispositions[S];
std::pair<std::map<const BasicBlock *, BlockDisposition>::iterator, bool>
Pair = Values.insert(std::make_pair(BB, DoesNotDominateBlock));
if (!Pair.second)
return Pair.first->second;
BlockDisposition D = computeBlockDisposition(S, BB);
return BlockDispositions[S][BB] = D;
}
ScalarEvolution::BlockDisposition
ScalarEvolution::computeBlockDisposition(const SCEV *S, const BasicBlock *BB) {
switch (S->getSCEVType()) {
case scConstant:
return ProperlyDominatesBlock;
case scTruncate:
case scZeroExtend:
case scSignExtend:
return getBlockDisposition(cast<SCEVCastExpr>(S)->getOperand(), BB);
case scAddRecExpr: {
const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(S);
if (!DT->dominates(AR->getLoop()->getHeader(), BB))
return DoesNotDominateBlock;
}
case scAddExpr:
case scMulExpr:
case scUMaxExpr:
case scSMaxExpr: {
const SCEVNAryExpr *NAry = cast<SCEVNAryExpr>(S);
bool Proper = true;
for (SCEVNAryExpr::op_iterator I = NAry->op_begin(), E = NAry->op_end();
I != E; ++I) {
BlockDisposition D = getBlockDisposition(*I, BB);
if (D == DoesNotDominateBlock)
return DoesNotDominateBlock;
if (D == DominatesBlock)
Proper = false;
}
return Proper ? ProperlyDominatesBlock : DominatesBlock;
}
case scUDivExpr: {
const SCEVUDivExpr *UDiv = cast<SCEVUDivExpr>(S);
const SCEV *LHS = UDiv->getLHS(), *RHS = UDiv->getRHS();
BlockDisposition LD = getBlockDisposition(LHS, BB);
if (LD == DoesNotDominateBlock)
return DoesNotDominateBlock;
BlockDisposition RD = getBlockDisposition(RHS, BB);
if (RD == DoesNotDominateBlock)
return DoesNotDominateBlock;
return (LD == ProperlyDominatesBlock && RD == ProperlyDominatesBlock) ?
ProperlyDominatesBlock : DominatesBlock;
}
case scUnknown:
if (Instruction *I =
dyn_cast<Instruction>(cast<SCEVUnknown>(S)->getValue())) {
if (I->getParent() == BB)
return DominatesBlock;
if (DT->properlyDominates(I->getParent(), BB))
return ProperlyDominatesBlock;
return DoesNotDominateBlock;
}
return ProperlyDominatesBlock;
case scCouldNotCompute:
llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
default:
llvm_unreachable("Unknown SCEV kind!");
}
}
bool ScalarEvolution::dominates(const SCEV *S, const BasicBlock *BB) {
return getBlockDisposition(S, BB) >= DominatesBlock;
}
bool ScalarEvolution::properlyDominates(const SCEV *S, const BasicBlock *BB) {
return getBlockDisposition(S, BB) == ProperlyDominatesBlock;
}
namespace {
struct SCEVSearch {
const SCEV *Node;
bool IsFound;
SCEVSearch(const SCEV *N): Node(N), IsFound(false) {}
bool follow(const SCEV *S) {
IsFound |= (S == Node);
return !IsFound;
}
bool isDone() const { return IsFound; }
};
}
bool ScalarEvolution::hasOperand(const SCEV *S, const SCEV *Op) const {
SCEVSearch Search(Op);
visitAll(S, Search);
return Search.IsFound;
}
void ScalarEvolution::forgetMemoizedResults(const SCEV *S) {
ValuesAtScopes.erase(S);
LoopDispositions.erase(S);
BlockDispositions.erase(S);
UnsignedRanges.erase(S);
SignedRanges.erase(S);
for (DenseMap<const Loop*, BackedgeTakenInfo>::iterator I =
BackedgeTakenCounts.begin(), E = BackedgeTakenCounts.end(); I != E; ) {
BackedgeTakenInfo &BEInfo = I->second;
if (BEInfo.hasOperand(S, this)) {
BEInfo.clear();
BackedgeTakenCounts.erase(I++);
}
else
++I;
}
}
typedef DenseMap<const Loop *, std::string> VerifyMap;
static void replaceSubString(std::string &Str, StringRef From, StringRef To) {
size_t Pos = 0;
while ((Pos = Str.find(From, Pos)) != std::string::npos) {
Str.replace(Pos, From.size(), To.data(), To.size());
Pos += To.size();
}
}
static void
getLoopBackedgeTakenCounts(Loop *L, VerifyMap &Map, ScalarEvolution &SE) {
for (Loop::reverse_iterator I = L->rbegin(), E = L->rend(); I != E; ++I) {
getLoopBackedgeTakenCounts(*I, Map, SE);
std::string &S = Map[L];
if (S.empty()) {
raw_string_ostream OS(S);
SE.getBackedgeTakenCount(L)->print(OS);
replaceSubString(OS.str(), "false", "0");
replaceSubString(OS.str(), "<nw>", "");
replaceSubString(OS.str(), "<nsw>", "");
replaceSubString(OS.str(), "<nuw>", "");
}
}
}
void ScalarEvolution::verifyAnalysis() const {
if (!VerifySCEV)
return;
ScalarEvolution &SE = *const_cast<ScalarEvolution *>(this);
VerifyMap BackedgeDumpsOld, BackedgeDumpsNew;
for (LoopInfo::reverse_iterator I = LI->rbegin(), E = LI->rend(); I != E; ++I)
getLoopBackedgeTakenCounts(*I, BackedgeDumpsOld, SE);
SE.releaseMemory();
for (LoopInfo::reverse_iterator I = LI->rbegin(), E = LI->rend(); I != E; ++I)
getLoopBackedgeTakenCounts(*I, BackedgeDumpsNew, SE);
assert(BackedgeDumpsOld.size() == BackedgeDumpsNew.size() &&
"New loops suddenly appeared!");
for (VerifyMap::iterator OldI = BackedgeDumpsOld.begin(),
OldE = BackedgeDumpsOld.end(),
NewI = BackedgeDumpsNew.begin();
OldI != OldE; ++OldI, ++NewI) {
assert(OldI->first == NewI->first && "Loop order changed!");
if (OldI->second != NewI->second &&
OldI->second.find("undef") == std::string::npos &&
NewI->second.find("undef") == std::string::npos &&
OldI->second != "***COULDNOTCOMPUTE***" &&
NewI->second != "***COULDNOTCOMPUTE***") {
dbgs() << "SCEVValidator: SCEV for loop '"
<< OldI->first->getHeader()->getName()
<< "' changed from '" << OldI->second
<< "' to '" << NewI->second << "'!\n";
std::abort();
}
}
}