Expand GEPs in ScalarEvolution expressions. SCEV expressions can now
have pointer types, though in contrast to C pointer types, SCEV
addition is never implicitly scaled. This not only eliminates the
need for special code like IndVars' EliminatePointerRecurrence
and LSR's own GEP expansion code, it also does a better job because
it lets the normal optimizations handle pointer expressions just
like integer expressions.
Also, since LLVM IR GEPs can't directly index into multi-dimensional
VLAs, moving the GEP analysis out of client code and into the SCEV
framework makes it easier for clients to handle multi-dimensional
VLAs the same way as other arrays.
Some existing regression tests show improved optimization.
test/CodeGen/ARM/2007-03-13-InstrSched.ll in particular improved to
the point where if-conversion started kicking in; I turned it off
for this test to preserve the intent of the test.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69258 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp
index 067b83e..972e4e9 100644
--- a/lib/Analysis/ScalarEvolution.cpp
+++ b/lib/Analysis/ScalarEvolution.cpp
@@ -69,16 +69,19 @@
#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Assembly/Writer.h"
+#include "llvm/Target/TargetData.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/ConstantRange.h"
+#include "llvm/Support/GetElementPtrTypeIterator.h"
#include "llvm/Support/InstIterator.h"
#include "llvm/Support/ManagedStatic.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/Streams.h"
#include "llvm/ADT/Statistic.h"
+#include "llvm/ADT/STLExtras.h"
#include <ostream>
#include <algorithm>
#include <cmath>
@@ -116,12 +119,6 @@
cerr << '\n';
}
-uint32_t SCEV::getBitWidth() const {
- if (const IntegerType* ITy = dyn_cast<IntegerType>(getType()))
- return ITy->getBitWidth();
- return 0;
-}
-
bool SCEV::isZero() const {
if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(this))
return SC->getValue()->isZero();
@@ -196,10 +193,13 @@
SCEVTruncateExpr::SCEVTruncateExpr(const SCEVHandle &op, const Type *ty)
: SCEV(scTruncate), Op(op), Ty(ty) {
- assert(Op->getType()->isInteger() && Ty->isInteger() &&
+ assert((Op->getType()->isInteger() || isa<PointerType>(Op->getType())) &&
+ (Ty->isInteger() || isa<PointerType>(Ty)) &&
"Cannot truncate non-integer value!");
- assert(Op->getType()->getPrimitiveSizeInBits() > Ty->getPrimitiveSizeInBits()
- && "This is not a truncating conversion!");
+ assert((!Op->getType()->isInteger() || !Ty->isInteger() ||
+ Op->getType()->getPrimitiveSizeInBits() >
+ Ty->getPrimitiveSizeInBits()) &&
+ "This is not a truncating conversion!");
}
SCEVTruncateExpr::~SCEVTruncateExpr() {
@@ -222,7 +222,8 @@
SCEVZeroExtendExpr::SCEVZeroExtendExpr(const SCEVHandle &op, const Type *ty)
: SCEV(scZeroExtend), Op(op), Ty(ty) {
- assert(Op->getType()->isInteger() && Ty->isInteger() &&
+ assert((Op->getType()->isInteger() || isa<PointerType>(Op->getType())) &&
+ (Ty->isInteger() || isa<PointerType>(Ty)) &&
"Cannot zero extend non-integer value!");
assert(Op->getType()->getPrimitiveSizeInBits() < Ty->getPrimitiveSizeInBits()
&& "This is not an extending conversion!");
@@ -248,7 +249,8 @@
SCEVSignExtendExpr::SCEVSignExtendExpr(const SCEVHandle &op, const Type *ty)
: SCEV(scSignExtend), Op(op), Ty(ty) {
- assert(Op->getType()->isInteger() && Ty->isInteger() &&
+ assert((Op->getType()->isInteger() || isa<PointerType>(Op->getType())) &&
+ (Ty->isInteger() || isa<PointerType>(Ty)) &&
"Cannot sign extend non-integer value!");
assert(Op->getType()->getPrimitiveSizeInBits() < Ty->getPrimitiveSizeInBits()
&& "This is not an extending conversion!");
@@ -436,7 +438,11 @@
}
void SCEVUnknown::print(std::ostream &OS) const {
+ if (isa<PointerType>(V->getType()))
+ OS << "(ptrtoint " << *V->getType() << " ";
WriteAsOperand(OS, V, false);
+ if (isa<PointerType>(V->getType()))
+ OS << " to iPTR)";
}
//===----------------------------------------------------------------------===//
@@ -504,52 +510,11 @@
// Simple SCEV method implementations
//===----------------------------------------------------------------------===//
-/// getIntegerSCEV - Given an integer or FP type, create a constant for the
-/// specified signed integer value and return a SCEV for the constant.
-SCEVHandle ScalarEvolution::getIntegerSCEV(int Val, const Type *Ty) {
- Constant *C;
- if (Val == 0)
- C = Constant::getNullValue(Ty);
- else if (Ty->isFloatingPoint())
- C = ConstantFP::get(APFloat(Ty==Type::FloatTy ? APFloat::IEEEsingle :
- APFloat::IEEEdouble, Val));
- else
- C = ConstantInt::get(Ty, Val);
- return getUnknown(C);
-}
-
-/// getNegativeSCEV - Return a SCEV corresponding to -V = -1*V
-///
-SCEVHandle ScalarEvolution::getNegativeSCEV(const SCEVHandle &V) {
- if (SCEVConstant *VC = dyn_cast<SCEVConstant>(V))
- return getUnknown(ConstantExpr::getNeg(VC->getValue()));
-
- return getMulExpr(V, getConstant(ConstantInt::getAllOnesValue(V->getType())));
-}
-
-/// getNotSCEV - Return a SCEV corresponding to ~V = -1-V
-SCEVHandle ScalarEvolution::getNotSCEV(const SCEVHandle &V) {
- if (SCEVConstant *VC = dyn_cast<SCEVConstant>(V))
- return getUnknown(ConstantExpr::getNot(VC->getValue()));
-
- SCEVHandle AllOnes = getConstant(ConstantInt::getAllOnesValue(V->getType()));
- return getMinusSCEV(AllOnes, V);
-}
-
-/// getMinusSCEV - Return a SCEV corresponding to LHS - RHS.
-///
-SCEVHandle ScalarEvolution::getMinusSCEV(const SCEVHandle &LHS,
- const SCEVHandle &RHS) {
- // X - Y --> X + -Y
- return getAddExpr(LHS, getNegativeSCEV(RHS));
-}
-
-
/// BinomialCoefficient - Compute BC(It, K). The result has width W.
// Assume, K > 0.
static SCEVHandle BinomialCoefficient(SCEVHandle It, unsigned K,
ScalarEvolution &SE,
- const IntegerType* ResultTy) {
+ const Type* ResultTy) {
// Handle the simplest case efficiently.
if (K == 1)
return SE.getTruncateOrZeroExtend(It, ResultTy);
@@ -608,7 +573,7 @@
if (K > 1000)
return new SCEVCouldNotCompute();
- unsigned W = ResultTy->getBitWidth();
+ unsigned W = SE.getTargetData().getTypeSizeInBits(ResultTy);
// Calculate K! / 2^T and T; we divide out the factors of two before
// multiplying for calculating K! / 2^T to avoid overflow.
@@ -672,8 +637,7 @@
// The computation is correct in the face of overflow provided that the
// multiplication is performed _after_ the evaluation of the binomial
// coefficient.
- SCEVHandle Coeff = BinomialCoefficient(It, i, SE,
- cast<IntegerType>(getType()));
+ SCEVHandle Coeff = BinomialCoefficient(It, i, SE, getType());
if (isa<SCEVCouldNotCompute>(Coeff))
return Coeff;
@@ -711,9 +675,13 @@
}
SCEVHandle ScalarEvolution::getZeroExtendExpr(const SCEVHandle &Op, const Type *Ty) {
- if (SCEVConstant *SC = dyn_cast<SCEVConstant>(Op))
- return getUnknown(
- ConstantExpr::getZExt(SC->getValue(), Ty));
+ if (SCEVConstant *SC = dyn_cast<SCEVConstant>(Op)) {
+ const Type *IntTy = Ty;
+ if (isa<PointerType>(IntTy)) IntTy = getTargetData().getIntPtrType();
+ Constant *C = ConstantExpr::getZExt(SC->getValue(), IntTy);
+ if (IntTy != Ty) C = ConstantExpr::getIntToPtr(C, Ty);
+ return getUnknown(C);
+ }
// FIXME: If the input value is a chrec scev, and we can prove that the value
// did not overflow the old, smaller, value, we can zero extend all of the
@@ -726,9 +694,13 @@
}
SCEVHandle ScalarEvolution::getSignExtendExpr(const SCEVHandle &Op, const Type *Ty) {
- if (SCEVConstant *SC = dyn_cast<SCEVConstant>(Op))
- return getUnknown(
- ConstantExpr::getSExt(SC->getValue(), Ty));
+ if (SCEVConstant *SC = dyn_cast<SCEVConstant>(Op)) {
+ const Type *IntTy = Ty;
+ if (isa<PointerType>(IntTy)) IntTy = getTargetData().getIntPtrType();
+ Constant *C = ConstantExpr::getSExt(SC->getValue(), IntTy);
+ if (IntTy != Ty) C = ConstantExpr::getIntToPtr(C, Ty);
+ return getUnknown(C);
+ }
// FIXME: If the input value is a chrec scev, and we can prove that the value
// did not overflow the old, smaller, value, we can sign extend all of the
@@ -740,36 +712,6 @@
return Result;
}
-/// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion
-/// of the input value to the specified type. If the type must be
-/// extended, it is zero extended.
-SCEVHandle ScalarEvolution::getTruncateOrZeroExtend(const SCEVHandle &V,
- const Type *Ty) {
- const Type *SrcTy = V->getType();
- assert(SrcTy->isInteger() && Ty->isInteger() &&
- "Cannot truncate or zero extend with non-integer arguments!");
- if (SrcTy->getPrimitiveSizeInBits() == Ty->getPrimitiveSizeInBits())
- return V; // No conversion
- if (SrcTy->getPrimitiveSizeInBits() > Ty->getPrimitiveSizeInBits())
- return getTruncateExpr(V, Ty);
- return getZeroExtendExpr(V, Ty);
-}
-
-/// getTruncateOrSignExtend - Return a SCEV corresponding to a conversion
-/// of the input value to the specified type. If the type must be
-/// extended, it is sign extended.
-SCEVHandle ScalarEvolution::getTruncateOrSignExtend(const SCEVHandle &V,
- const Type *Ty) {
- const Type *SrcTy = V->getType();
- assert(SrcTy->isInteger() && Ty->isInteger() &&
- "Cannot truncate or sign extend with non-integer arguments!");
- if (SrcTy->getPrimitiveSizeInBits() == Ty->getPrimitiveSizeInBits())
- return V; // No conversion
- if (SrcTy->getPrimitiveSizeInBits() > Ty->getPrimitiveSizeInBits())
- return getTruncateExpr(V, Ty);
- return getSignExtendExpr(V, Ty);
-}
-
// get - Get a canonical add expression, or something simpler if possible.
SCEVHandle ScalarEvolution::getAddExpr(std::vector<SCEVHandle> &Ops) {
assert(!Ops.empty() && "Cannot get empty add!");
@@ -1385,6 +1327,8 @@
SCEVHandle ScalarEvolution::getUnknown(Value *V) {
if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
return getConstant(CI);
+ if (isa<ConstantPointerNull>(V))
+ return getIntegerSCEV(0, V->getType());
SCEVUnknown *&Result = (*SCEVUnknowns)[V];
if (Result == 0) Result = new SCEVUnknown(V);
return Result;
@@ -1411,6 +1355,10 @@
///
LoopInfo &LI;
+ /// TD - The target data information for the target we are targetting.
+ ///
+ TargetData &TD;
+
/// UnknownValue - This SCEV is used to represent unknown trip counts and
/// things.
SCEVHandle UnknownValue;
@@ -1431,8 +1379,35 @@
std::map<PHINode*, Constant*> ConstantEvolutionLoopExitValue;
public:
- ScalarEvolutionsImpl(ScalarEvolution &se, Function &f, LoopInfo &li)
- : SE(se), F(f), LI(li), UnknownValue(new SCEVCouldNotCompute()) {}
+ ScalarEvolutionsImpl(ScalarEvolution &se, Function &f, LoopInfo &li,
+ TargetData &td)
+ : SE(se), F(f), LI(li), TD(td), UnknownValue(new SCEVCouldNotCompute()) {}
+
+ /// getIntegerSCEV - Given an integer or FP type, create a constant for the
+ /// specified signed integer value and return a SCEV for the constant.
+ SCEVHandle getIntegerSCEV(int Val, const Type *Ty);
+
+ /// getNegativeSCEV - Return a SCEV corresponding to -V = -1*V
+ ///
+ SCEVHandle getNegativeSCEV(const SCEVHandle &V);
+
+ /// getNotSCEV - Return a SCEV corresponding to ~V = -1-V
+ ///
+ SCEVHandle getNotSCEV(const SCEVHandle &V);
+
+ /// getMinusSCEV - Return a SCEV corresponding to LHS - RHS.
+ ///
+ SCEVHandle getMinusSCEV(const SCEVHandle &LHS, const SCEVHandle &RHS);
+
+ /// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion
+ /// of the input value to the specified type. If the type must be extended,
+ /// it is zero extended.
+ SCEVHandle getTruncateOrZeroExtend(const SCEVHandle &V, const Type *Ty);
+
+ /// getTruncateOrSignExtend - Return a SCEV corresponding to a conversion
+ /// of the input value to the specified type. If the type must be extended,
+ /// it is sign extended.
+ SCEVHandle getTruncateOrSignExtend(const SCEVHandle &V, const Type *Ty);
/// getSCEV - Return an existing SCEV if it exists, otherwise analyze the
/// expression and create a new one.
@@ -1492,6 +1467,9 @@
/// that no dangling references are left around.
void deleteValueFromRecords(Value *V);
+ /// getTargetData - Return the TargetData.
+ const TargetData &getTargetData() const;
+
private:
/// createSCEV - We know that there is no SCEV for the specified value.
/// Analyze the expression.
@@ -1592,6 +1570,9 @@
}
}
+const TargetData &ScalarEvolutionsImpl::getTargetData() const {
+ return TD;
+}
/// getSCEV - Return an existing SCEV if it exists, otherwise analyze the
/// expression and create a new one.
@@ -1605,6 +1586,88 @@
return S;
}
+/// getIntegerSCEV - Given an integer or FP type, create a constant for the
+/// specified signed integer value and return a SCEV for the constant.
+SCEVHandle ScalarEvolutionsImpl::getIntegerSCEV(int Val, const Type *Ty) {
+ if (isa<PointerType>(Ty))
+ Ty = TD.getIntPtrType();
+ Constant *C;
+ if (Val == 0)
+ C = Constant::getNullValue(Ty);
+ else if (Ty->isFloatingPoint())
+ C = ConstantFP::get(APFloat(Ty==Type::FloatTy ? APFloat::IEEEsingle :
+ APFloat::IEEEdouble, Val));
+ else
+ C = ConstantInt::get(Ty, Val);
+ return SE.getUnknown(C);
+}
+
+/// getNegativeSCEV - Return a SCEV corresponding to -V = -1*V
+///
+SCEVHandle ScalarEvolutionsImpl::getNegativeSCEV(const SCEVHandle &V) {
+ if (SCEVConstant *VC = dyn_cast<SCEVConstant>(V))
+ return SE.getUnknown(ConstantExpr::getNeg(VC->getValue()));
+
+ const Type *Ty = V->getType();
+ if (isa<PointerType>(Ty))
+ Ty = TD.getIntPtrType();
+ return SE.getMulExpr(V, SE.getConstant(ConstantInt::getAllOnesValue(Ty)));
+}
+
+/// getNotSCEV - Return a SCEV corresponding to ~V = -1-V
+SCEVHandle ScalarEvolutionsImpl::getNotSCEV(const SCEVHandle &V) {
+ if (SCEVConstant *VC = dyn_cast<SCEVConstant>(V))
+ return SE.getUnknown(ConstantExpr::getNot(VC->getValue()));
+
+ const Type *Ty = V->getType();
+ if (isa<PointerType>(Ty))
+ Ty = TD.getIntPtrType();
+ SCEVHandle AllOnes = SE.getConstant(ConstantInt::getAllOnesValue(Ty));
+ return getMinusSCEV(AllOnes, V);
+}
+
+/// getMinusSCEV - Return a SCEV corresponding to LHS - RHS.
+///
+SCEVHandle ScalarEvolutionsImpl::getMinusSCEV(const SCEVHandle &LHS,
+ const SCEVHandle &RHS) {
+ // X - Y --> X + -Y
+ return SE.getAddExpr(LHS, SE.getNegativeSCEV(RHS));
+}
+
+/// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion of the
+/// input value to the specified type. If the type must be extended, it is zero
+/// extended.
+SCEVHandle
+ScalarEvolutionsImpl::getTruncateOrZeroExtend(const SCEVHandle &V,
+ const Type *Ty) {
+ const Type *SrcTy = V->getType();
+ assert((SrcTy->isInteger() || isa<PointerType>(SrcTy)) &&
+ (Ty->isInteger() || isa<PointerType>(Ty)) &&
+ "Cannot truncate or zero extend with non-integer arguments!");
+ if (TD.getTypeSizeInBits(SrcTy) == TD.getTypeSizeInBits(Ty))
+ return V; // No conversion
+ if (TD.getTypeSizeInBits(SrcTy) > TD.getTypeSizeInBits(Ty))
+ return SE.getTruncateExpr(V, Ty);
+ return SE.getZeroExtendExpr(V, Ty);
+}
+
+/// getTruncateOrSignExtend - Return a SCEV corresponding to a conversion of the
+/// input value to the specified type. If the type must be extended, it is sign
+/// extended.
+SCEVHandle
+ScalarEvolutionsImpl::getTruncateOrSignExtend(const SCEVHandle &V,
+ const Type *Ty) {
+ const Type *SrcTy = V->getType();
+ assert((SrcTy->isInteger() || isa<PointerType>(SrcTy)) &&
+ (Ty->isInteger() || isa<PointerType>(Ty)) &&
+ "Cannot truncate or zero extend with non-integer arguments!");
+ if (TD.getTypeSizeInBits(SrcTy) == TD.getTypeSizeInBits(Ty))
+ return V; // No conversion
+ if (TD.getTypeSizeInBits(SrcTy) > TD.getTypeSizeInBits(Ty))
+ return SE.getTruncateExpr(V, Ty);
+ return SE.getSignExtendExpr(V, Ty);
+}
+
/// ReplaceSymbolicValueWithConcrete - This looks up the computed SCEV value for
/// the specified instruction and replaces any references to the symbolic value
/// SymName with the specified value. This is used during PHI resolution.
@@ -1728,63 +1791,66 @@
/// guaranteed to end in (at every loop iteration). It is, at the same time,
/// the minimum number of times S is divisible by 2. For example, given {4,+,8}
/// it returns 2. If S is guaranteed to be 0, it returns the bitwidth of S.
-static uint32_t GetMinTrailingZeros(SCEVHandle S) {
+static uint32_t GetMinTrailingZeros(SCEVHandle S, const TargetData &TD) {
if (SCEVConstant *C = dyn_cast<SCEVConstant>(S))
return C->getValue()->getValue().countTrailingZeros();
if (SCEVTruncateExpr *T = dyn_cast<SCEVTruncateExpr>(S))
- return std::min(GetMinTrailingZeros(T->getOperand()), T->getBitWidth());
+ return std::min(GetMinTrailingZeros(T->getOperand(), TD),
+ (uint32_t)TD.getTypeSizeInBits(T->getType()));
if (SCEVZeroExtendExpr *E = dyn_cast<SCEVZeroExtendExpr>(S)) {
- uint32_t OpRes = GetMinTrailingZeros(E->getOperand());
- return OpRes == E->getOperand()->getBitWidth() ? E->getBitWidth() : OpRes;
+ uint32_t OpRes = GetMinTrailingZeros(E->getOperand(), TD);
+ return OpRes == TD.getTypeSizeInBits(E->getOperand()->getType()) ?
+ TD.getTypeSizeInBits(E->getOperand()->getType()) : OpRes;
}
if (SCEVSignExtendExpr *E = dyn_cast<SCEVSignExtendExpr>(S)) {
- uint32_t OpRes = GetMinTrailingZeros(E->getOperand());
- return OpRes == E->getOperand()->getBitWidth() ? E->getBitWidth() : OpRes;
+ uint32_t OpRes = GetMinTrailingZeros(E->getOperand(), TD);
+ return OpRes == TD.getTypeSizeInBits(E->getOperand()->getType()) ?
+ TD.getTypeSizeInBits(E->getOperand()->getType()) : OpRes;
}
if (SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) {
// The result is the min of all operands results.
- uint32_t MinOpRes = GetMinTrailingZeros(A->getOperand(0));
+ uint32_t MinOpRes = GetMinTrailingZeros(A->getOperand(0), TD);
for (unsigned i = 1, e = A->getNumOperands(); MinOpRes && i != e; ++i)
- MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(A->getOperand(i)));
+ MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(A->getOperand(i), TD));
return MinOpRes;
}
if (SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(S)) {
// The result is the sum of all operands results.
- uint32_t SumOpRes = GetMinTrailingZeros(M->getOperand(0));
- uint32_t BitWidth = M->getBitWidth();
+ uint32_t SumOpRes = GetMinTrailingZeros(M->getOperand(0), TD);
+ uint32_t BitWidth = TD.getTypeSizeInBits(M->getType());
for (unsigned i = 1, e = M->getNumOperands();
SumOpRes != BitWidth && i != e; ++i)
- SumOpRes = std::min(SumOpRes + GetMinTrailingZeros(M->getOperand(i)),
+ SumOpRes = std::min(SumOpRes + GetMinTrailingZeros(M->getOperand(i), TD),
BitWidth);
return SumOpRes;
}
if (SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(S)) {
// The result is the min of all operands results.
- uint32_t MinOpRes = GetMinTrailingZeros(A->getOperand(0));
+ uint32_t MinOpRes = GetMinTrailingZeros(A->getOperand(0), TD);
for (unsigned i = 1, e = A->getNumOperands(); MinOpRes && i != e; ++i)
- MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(A->getOperand(i)));
+ MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(A->getOperand(i), TD));
return MinOpRes;
}
if (SCEVSMaxExpr *M = dyn_cast<SCEVSMaxExpr>(S)) {
// The result is the min of all operands results.
- uint32_t MinOpRes = GetMinTrailingZeros(M->getOperand(0));
+ uint32_t MinOpRes = GetMinTrailingZeros(M->getOperand(0), TD);
for (unsigned i = 1, e = M->getNumOperands(); MinOpRes && i != e; ++i)
- MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(M->getOperand(i)));
+ MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(M->getOperand(i), TD));
return MinOpRes;
}
if (SCEVUMaxExpr *M = dyn_cast<SCEVUMaxExpr>(S)) {
// The result is the min of all operands results.
- uint32_t MinOpRes = GetMinTrailingZeros(M->getOperand(0));
+ uint32_t MinOpRes = GetMinTrailingZeros(M->getOperand(0), TD);
for (unsigned i = 1, e = M->getNumOperands(); MinOpRes && i != e; ++i)
- MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(M->getOperand(i)));
+ MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(M->getOperand(i), TD));
return MinOpRes;
}
@@ -1796,9 +1862,10 @@
/// Analyze the expression.
///
SCEVHandle ScalarEvolutionsImpl::createSCEV(Value *V) {
- if (!isa<IntegerType>(V->getType()))
+ if (!isa<IntegerType>(V->getType()) &&
+ !isa<PointerType>(V->getType()))
return SE.getUnknown(V);
-
+
unsigned Opcode = Instruction::UserOp1;
if (Instruction *I = dyn_cast<Instruction>(V))
Opcode = I->getOpcode();
@@ -1831,7 +1898,7 @@
if (ConstantInt *CI = dyn_cast<ConstantInt>(U->getOperand(1))) {
SCEVHandle LHS = getSCEV(U->getOperand(0));
const APInt &CIVal = CI->getValue();
- if (GetMinTrailingZeros(LHS) >=
+ if (GetMinTrailingZeros(LHS, TD) >=
(CIVal.getBitWidth() - CIVal.countLeadingZeros()))
return SE.getAddExpr(LHS, getSCEV(U->getOperand(1)));
}
@@ -1881,11 +1948,55 @@
case Instruction::BitCast:
// BitCasts are no-op casts so we just eliminate the cast.
- if (U->getType()->isInteger() &&
- U->getOperand(0)->getType()->isInteger())
+ if ((U->getType()->isInteger() ||
+ isa<PointerType>(U->getType())) &&
+ (U->getOperand(0)->getType()->isInteger() ||
+ isa<PointerType>(U->getOperand(0)->getType())))
return getSCEV(U->getOperand(0));
break;
+ case Instruction::IntToPtr:
+ return getTruncateOrZeroExtend(getSCEV(U->getOperand(0)),
+ TD.getIntPtrType());
+
+ case Instruction::PtrToInt:
+ return getTruncateOrZeroExtend(getSCEV(U->getOperand(0)),
+ U->getType());
+
+ case Instruction::GetElementPtr: {
+ const Type *IntPtrTy = TD.getIntPtrType();
+ Value *Base = U->getOperand(0);
+ SCEVHandle TotalOffset = SE.getIntegerSCEV(0, IntPtrTy);
+ gep_type_iterator GTI = gep_type_begin(U);
+ for (GetElementPtrInst::op_iterator I = next(U->op_begin()),
+ E = U->op_end();
+ I != E; ++I) {
+ Value *Index = *I;
+ // Compute the (potentially symbolic) offset in bytes for this index.
+ if (const StructType *STy = dyn_cast<StructType>(*GTI++)) {
+ // For a struct, add the member offset.
+ const StructLayout &SL = *TD.getStructLayout(STy);
+ unsigned FieldNo = cast<ConstantInt>(Index)->getZExtValue();
+ uint64_t Offset = SL.getElementOffset(FieldNo);
+ TotalOffset = SE.getAddExpr(TotalOffset,
+ SE.getIntegerSCEV(Offset, IntPtrTy));
+ } else {
+ // For an array, add the element offset, explicitly scaled.
+ SCEVHandle LocalOffset = getSCEV(Index);
+ if (!isa<PointerType>(LocalOffset->getType()))
+ // Getelementptr indicies are signed.
+ LocalOffset = getTruncateOrSignExtend(LocalOffset,
+ IntPtrTy);
+ LocalOffset =
+ SE.getMulExpr(LocalOffset,
+ SE.getIntegerSCEV(TD.getTypePaddedSize(*GTI),
+ IntPtrTy));
+ TotalOffset = SE.getAddExpr(TotalOffset, LocalOffset);
+ }
+ }
+ return SE.getAddExpr(getSCEV(Base), TotalOffset);
+ }
+
case Instruction::PHI:
return createNodeForPHI(cast<PHINode>(U));
@@ -2324,6 +2435,7 @@
static Constant *EvaluateExpression(Value *V, Constant *PHIVal) {
if (isa<PHINode>(V)) return PHIVal;
if (Constant *C = dyn_cast<Constant>(V)) return C;
+ if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) return GV;
Instruction *I = cast<Instruction>(V);
std::vector<Constant*> Operands;
@@ -2490,10 +2602,12 @@
Operands.push_back(C);
} else {
// If any of the operands is non-constant and if they are
- // non-integer, don't even try to analyze them with scev techniques.
- if (!isa<IntegerType>(Op->getType()))
+ // non-integer and non-pointer, don't even try to analyze them
+ // with scev techniques.
+ if (!isa<IntegerType>(Op->getType()) &&
+ !isa<PointerType>(Op->getType()))
return V;
-
+
SCEVHandle OpV = getSCEVAtScope(getSCEV(Op), L);
if (SCEVConstant *SC = dyn_cast<SCEVConstant>(OpV))
Operands.push_back(ConstantExpr::getIntegerCast(SC->getValue(),
@@ -3003,7 +3117,8 @@
// First check to see if the range contains zero. If not, the first
// iteration exits.
- if (!Range.contains(APInt(getBitWidth(),0)))
+ unsigned BitWidth = SE.getTargetData().getTypeSizeInBits(getType());
+ if (!Range.contains(APInt(BitWidth, 0)))
return SE.getConstant(ConstantInt::get(getType(),0));
if (isAffine()) {
@@ -3014,7 +3129,7 @@
// the upper value of the range must be the first possible exit value.
// If A is negative then the lower of the range is the last possible loop
// value. Also note that we already checked for a full range.
- APInt One(getBitWidth(),1);
+ APInt One(BitWidth,1);
APInt A = cast<SCEVConstant>(getOperand(1))->getValue()->getValue();
APInt End = A.sge(One) ? (Range.getUpper() - One) : Range.getLower();
@@ -3094,7 +3209,9 @@
//===----------------------------------------------------------------------===//
bool ScalarEvolution::runOnFunction(Function &F) {
- Impl = new ScalarEvolutionsImpl(*this, F, getAnalysis<LoopInfo>());
+ Impl = new ScalarEvolutionsImpl(*this, F,
+ getAnalysis<LoopInfo>(),
+ getAnalysis<TargetData>());
return false;
}
@@ -3106,6 +3223,15 @@
void ScalarEvolution::getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesAll();
AU.addRequiredTransitive<LoopInfo>();
+ AU.addRequiredTransitive<TargetData>();
+}
+
+const TargetData &ScalarEvolution::getTargetData() const {
+ return ((ScalarEvolutionsImpl*)Impl)->getTargetData();
+}
+
+SCEVHandle ScalarEvolution::getIntegerSCEV(int Val, const Type *Ty) {
+ return ((ScalarEvolutionsImpl*)Impl)->getIntegerSCEV(Val, Ty);
}
SCEVHandle ScalarEvolution::getSCEV(Value *V) const {
@@ -3125,6 +3251,41 @@
((ScalarEvolutionsImpl*)Impl)->setSCEV(V, H);
}
+/// getNegativeSCEV - Return a SCEV corresponding to -V = -1*V
+///
+SCEVHandle ScalarEvolution::getNegativeSCEV(const SCEVHandle &V) {
+ return ((ScalarEvolutionsImpl*)Impl)->getNegativeSCEV(V);
+}
+
+/// getNotSCEV - Return a SCEV corresponding to ~V = -1-V
+///
+SCEVHandle ScalarEvolution::getNotSCEV(const SCEVHandle &V) {
+ return ((ScalarEvolutionsImpl*)Impl)->getNotSCEV(V);
+}
+
+/// getMinusSCEV - Return a SCEV corresponding to LHS - RHS.
+///
+SCEVHandle ScalarEvolution::getMinusSCEV(const SCEVHandle &LHS,
+ const SCEVHandle &RHS) {
+ return ((ScalarEvolutionsImpl*)Impl)->getMinusSCEV(LHS, RHS);
+}
+
+/// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion
+/// of the input value to the specified type. If the type must be
+/// extended, it is zero extended.
+SCEVHandle ScalarEvolution::getTruncateOrZeroExtend(const SCEVHandle &V,
+ const Type *Ty) {
+ return ((ScalarEvolutionsImpl*)Impl)->getTruncateOrZeroExtend(V, Ty);
+}
+
+/// getTruncateOrSignExtend - Return a SCEV corresponding to a conversion
+/// of the input value to the specified type. If the type must be
+/// extended, it is sign extended.
+SCEVHandle ScalarEvolution::getTruncateOrSignExtend(const SCEVHandle &V,
+ const Type *Ty) {
+ return ((ScalarEvolutionsImpl*)Impl)->getTruncateOrSignExtend(V, Ty);
+}
+
bool ScalarEvolution::isLoopGuardedByCond(const Loop *L,
ICmpInst::Predicate Pred,
diff --git a/lib/Analysis/ScalarEvolutionExpander.cpp b/lib/Analysis/ScalarEvolutionExpander.cpp
index 30df087..d91061b 100644
--- a/lib/Analysis/ScalarEvolutionExpander.cpp
+++ b/lib/Analysis/ScalarEvolutionExpander.cpp
@@ -15,12 +15,17 @@
#include "llvm/Analysis/ScalarEvolutionExpander.h"
#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Target/TargetData.h"
using namespace llvm;
/// InsertCastOfTo - Insert a cast of V to the specified type, doing what
/// we can to share the casts.
Value *SCEVExpander::InsertCastOfTo(Instruction::CastOps opcode, Value *V,
const Type *Ty) {
+ // Short-circuit unnecessary bitcasts.
+ if (opcode == Instruction::BitCast && V->getType() == Ty)
+ return V;
+
// FIXME: keep track of the cast instruction.
if (Constant *C = dyn_cast<Constant>(V))
return ConstantExpr::getCast(opcode, C, Ty);
@@ -100,16 +105,23 @@
}
Value *SCEVExpander::visitAddExpr(SCEVAddExpr *S) {
+ const Type *Ty = S->getType();
+ if (isa<PointerType>(Ty)) Ty = TD.getIntPtrType();
Value *V = expand(S->getOperand(S->getNumOperands()-1));
+ V = InsertCastOfTo(CastInst::getCastOpcode(V, false, Ty, false), V, Ty);
// Emit a bunch of add instructions
- for (int i = S->getNumOperands()-2; i >= 0; --i)
- V = InsertBinop(Instruction::Add, V, expand(S->getOperand(i)),
- InsertPt);
+ for (int i = S->getNumOperands()-2; i >= 0; --i) {
+ Value *W = expand(S->getOperand(i));
+ W = InsertCastOfTo(CastInst::getCastOpcode(W, false, Ty, false), W, Ty);
+ V = InsertBinop(Instruction::Add, V, W, InsertPt);
+ }
return V;
}
Value *SCEVExpander::visitMulExpr(SCEVMulExpr *S) {
+ const Type *Ty = S->getType();
+ if (isa<PointerType>(Ty)) Ty = TD.getIntPtrType();
int FirstOp = 0; // Set if we should emit a subtract.
if (SCEVConstant *SC = dyn_cast<SCEVConstant>(S->getOperand(0)))
if (SC->getValue()->isAllOnesValue())
@@ -117,29 +129,37 @@
int i = S->getNumOperands()-2;
Value *V = expand(S->getOperand(i+1));
+ V = InsertCastOfTo(CastInst::getCastOpcode(V, false, Ty, false), V, Ty);
// Emit a bunch of multiply instructions
- for (; i >= FirstOp; --i)
- V = InsertBinop(Instruction::Mul, V, expand(S->getOperand(i)),
- InsertPt);
+ for (; i >= FirstOp; --i) {
+ Value *W = expand(S->getOperand(i));
+ W = InsertCastOfTo(CastInst::getCastOpcode(W, false, Ty, false), W, Ty);
+ V = InsertBinop(Instruction::Mul, V, W, InsertPt);
+ }
+
// -1 * ... ---> 0 - ...
if (FirstOp == 1)
- V = InsertBinop(Instruction::Sub, Constant::getNullValue(V->getType()), V,
- InsertPt);
+ V = InsertBinop(Instruction::Sub, Constant::getNullValue(Ty), V, InsertPt);
return V;
}
Value *SCEVExpander::visitUDivExpr(SCEVUDivExpr *S) {
+ const Type *Ty = S->getType();
+ if (isa<PointerType>(Ty)) Ty = TD.getIntPtrType();
+
Value *LHS = expand(S->getLHS());
+ LHS = InsertCastOfTo(CastInst::getCastOpcode(LHS, false, Ty, false), LHS, Ty);
if (SCEVConstant *SC = dyn_cast<SCEVConstant>(S->getRHS())) {
const APInt &RHS = SC->getValue()->getValue();
if (RHS.isPowerOf2())
return InsertBinop(Instruction::LShr, LHS,
- ConstantInt::get(S->getType(), RHS.logBase2()),
+ ConstantInt::get(Ty, RHS.logBase2()),
InsertPt);
}
Value *RHS = expand(S->getRHS());
+ RHS = InsertCastOfTo(CastInst::getCastOpcode(RHS, false, Ty, false), RHS, Ty);
return InsertBinop(Instruction::UDiv, LHS, RHS, InsertPt);
}
@@ -147,14 +167,19 @@
const Type *Ty = S->getType();
const Loop *L = S->getLoop();
// We cannot yet do fp recurrences, e.g. the xform of {X,+,F} --> X+{0,+,F}
- assert(Ty->isInteger() && "Cannot expand fp recurrences yet!");
+ assert((Ty->isInteger() || isa<PointerType>(Ty)) &&
+ "Cannot expand fp recurrences yet!");
// {X,+,F} --> X + {0,+,F}
if (!S->getStart()->isZero()) {
Value *Start = expand(S->getStart());
+ if (isa<PointerType>(Start->getType()))
+ Start = InsertCastOfTo(Instruction::PtrToInt, Start, TD.getIntPtrType());
std::vector<SCEVHandle> NewOps(S->op_begin(), S->op_end());
NewOps[0] = SE.getIntegerSCEV(0, Ty);
Value *Rest = expand(SE.getAddRecExpr(NewOps, L));
+ if (isa<PointerType>(Rest->getType()))
+ Rest = InsertCastOfTo(Instruction::PtrToInt, Rest, TD.getIntPtrType());
// FIXME: look for an existing add to use.
return InsertBinop(Instruction::Add, Rest, Start, InsertPt);
@@ -242,16 +267,22 @@
Value *SCEVExpander::visitTruncateExpr(SCEVTruncateExpr *S) {
Value *V = expand(S->getOperand());
+ if (isa<PointerType>(V->getType()))
+ V = InsertCastOfTo(Instruction::PtrToInt, V, TD.getIntPtrType());
return CastInst::CreateTruncOrBitCast(V, S->getType(), "tmp.", InsertPt);
}
Value *SCEVExpander::visitZeroExtendExpr(SCEVZeroExtendExpr *S) {
Value *V = expand(S->getOperand());
+ if (isa<PointerType>(V->getType()))
+ V = InsertCastOfTo(Instruction::PtrToInt, V, TD.getIntPtrType());
return CastInst::CreateZExtOrBitCast(V, S->getType(), "tmp.", InsertPt);
}
Value *SCEVExpander::visitSignExtendExpr(SCEVSignExtendExpr *S) {
Value *V = expand(S->getOperand());
+ if (isa<PointerType>(V->getType()))
+ V = InsertCastOfTo(Instruction::PtrToInt, V, TD.getIntPtrType());
return CastInst::CreateSExtOrBitCast(V, S->getType(), "tmp.", InsertPt);
}
@@ -275,10 +306,14 @@
return LHS;
}
-Value *SCEVExpander::expandCodeFor(SCEVHandle SH, Instruction *IP) {
+Value *SCEVExpander::expandCodeFor(SCEVHandle SH, const Type *Ty,
+ Instruction *IP) {
// Expand the code for this SCEV.
+ assert(TD.getTypeSizeInBits(Ty) == TD.getTypeSizeInBits(SH->getType()) &&
+ "non-trivial casts should be done with the SCEVs directly!");
this->InsertPt = IP;
- return expand(SH);
+ Value *V = expand(SH);
+ return InsertCastOfTo(CastInst::getCastOpcode(V, false, Ty, false), V, Ty);
}
Value *SCEVExpander::expand(SCEV *S) {