class Type;
class SCEVHandle;
class ScalarEvolution;
+ class TargetData;
/// SCEV - This class represent an analyzed expression in the program. These
/// are reference counted opaque objects that the client is not allowed to
///
virtual const Type *getType() const = 0;
- /// getBitWidth - Get the bit width of the type, if it has one, 0 otherwise.
- ///
- uint32_t getBitWidth() const;
-
/// isZero - Return true if the expression is a constant zero.
///
bool isZero() const;
static char ID; // Pass identification, replacement for typeid
ScalarEvolution() : FunctionPass(&ID), Impl(0) {}
+ // getTargetData - Return the TargetData object contained in this
+ // ScalarEvolution.
+ const TargetData &getTargetData() const;
+
/// getSCEV - Return a SCEV expression handle for the full generality of the
/// specified expression.
SCEVHandle getSCEV(Value *V) const;
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
namespace llvm {
+ class TargetData;
+
/// SCEVExpander - This class uses information about analyze scalars to
/// rewrite expressions in canonical form.
///
struct SCEVExpander : public SCEVVisitor<SCEVExpander, Value*> {
ScalarEvolution &SE;
LoopInfo &LI;
+ const TargetData &TD;
std::map<SCEVHandle, Value*> InsertedExpressions;
std::set<Instruction*> InsertedInstructions;
friend struct SCEVVisitor<SCEVExpander, Value*>;
public:
- SCEVExpander(ScalarEvolution &se, LoopInfo &li) : SE(se), LI(li) {}
+ SCEVExpander(ScalarEvolution &se, LoopInfo &li, const TargetData &td)
+ : SE(se), LI(li), TD(td) {}
LoopInfo &getLoopInfo() const { return LI; }
/// expandCodeFor - Insert code to directly compute the specified SCEV
/// expression into the program. The inserted code is inserted into the
/// specified block.
- Value *expandCodeFor(SCEVHandle SH, Instruction *IP);
+ Value *expandCodeFor(SCEVHandle SH, const Type *Ty, Instruction *IP);
/// InsertCastOfTo - Insert a cast of V to the specified type, doing what
/// we can to share the casts.
Value *RHS, Instruction *InsertPt);
protected:
Value *expand(SCEV *S);
-
+
Value *visitConstant(SCEVConstant *S) {
return S->getValue();
}
#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>
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();
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() {
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!");
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!");
}
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)";
}
//===----------------------------------------------------------------------===//
// 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);
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.
// 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;
}
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
}
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
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!");
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;
///
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;
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.
/// 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.
}
}
+const TargetData &ScalarEvolutionsImpl::getTargetData() const {
+ return TD;
+}
/// getSCEV - Return an existing SCEV if it exists, otherwise analyze the
/// expression and create a new one.
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.
/// 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;
}
/// 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();
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)));
}
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));
static Constant *EvaluateExpression(Value *V, Constant *PHIVal) {
if (isa<PHINode>(V)) return PHIVal;
if (Constant *C = dyn_cast<Constant>(V)) return C;
+ if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) return GV;
Instruction *I = cast<Instruction>(V);
std::vector<Constant*> Operands;
Operands.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(),
// 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()) {
// 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();
//===----------------------------------------------------------------------===//
bool ScalarEvolution::runOnFunction(Function &F) {
- Impl = new ScalarEvolutionsImpl(*this, F, getAnalysis<LoopInfo>());
+ Impl = new ScalarEvolutionsImpl(*this, F,
+ getAnalysis<LoopInfo>(),
+ getAnalysis<TargetData>());
return false;
}
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 {
((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,
#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);
}
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())
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);
}
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);
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);
}
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) {
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/GetElementPtrTypeIterator.h"
+#include "llvm/Target/TargetData.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/ADT/SmallVector.h"
using namespace llvm;
STATISTIC(NumRemoved , "Number of aux indvars removed");
-STATISTIC(NumPointer , "Number of pointer indvars promoted");
STATISTIC(NumInserted, "Number of canonical indvars added");
STATISTIC(NumReplaced, "Number of exit values replaced");
STATISTIC(NumLFTR , "Number of loop exit tests replaced");
namespace {
class VISIBILITY_HIDDEN IndVarSimplify : public LoopPass {
LoopInfo *LI;
+ TargetData *TD;
ScalarEvolution *SE;
bool Changed;
public:
AU.addRequiredID(LCSSAID);
AU.addRequiredID(LoopSimplifyID);
AU.addRequired<LoopInfo>();
+ AU.addRequired<TargetData>();
AU.addPreserved<ScalarEvolution>();
AU.addPreservedID(LoopSimplifyID);
AU.addPreservedID(LCSSAID);
void RewriteNonIntegerIVs(Loop *L);
- void EliminatePointerRecurrence(PHINode *PN, BasicBlock *Preheader,
- SmallPtrSet<Instruction*, 16> &DeadInsts);
void LinearFunctionTestReplace(Loop *L, SCEVHandle BackedgeTakenCount,
Value *IndVar,
BasicBlock *ExitingBlock,
}
}
-
-/// EliminatePointerRecurrence - Check to see if this is a trivial GEP pointer
-/// recurrence. If so, change it into an integer recurrence, permitting
-/// analysis by the SCEV routines.
-void IndVarSimplify::EliminatePointerRecurrence(PHINode *PN,
- BasicBlock *Preheader,
- SmallPtrSet<Instruction*, 16> &DeadInsts) {
- assert(PN->getNumIncomingValues() == 2 && "Noncanonicalized loop!");
- unsigned PreheaderIdx = PN->getBasicBlockIndex(Preheader);
- unsigned BackedgeIdx = PreheaderIdx^1;
- if (GetElementPtrInst *GEPI =
- dyn_cast<GetElementPtrInst>(PN->getIncomingValue(BackedgeIdx)))
- if (GEPI->getOperand(0) == PN) {
- assert(GEPI->getNumOperands() == 2 && "GEP types must match!");
- DOUT << "INDVARS: Eliminating pointer recurrence: " << *GEPI;
-
- // Okay, we found a pointer recurrence. Transform this pointer
- // recurrence into an integer recurrence. Compute the value that gets
- // added to the pointer at every iteration.
- Value *AddedVal = GEPI->getOperand(1);
-
- // Insert a new integer PHI node into the top of the block.
- PHINode *NewPhi = PHINode::Create(AddedVal->getType(),
- PN->getName()+".rec", PN);
- NewPhi->addIncoming(Constant::getNullValue(NewPhi->getType()), Preheader);
-
- // Create the new add instruction.
- Value *NewAdd = BinaryOperator::CreateAdd(NewPhi, AddedVal,
- GEPI->getName()+".rec", GEPI);
- NewPhi->addIncoming(NewAdd, PN->getIncomingBlock(BackedgeIdx));
-
- // Update the existing GEP to use the recurrence.
- GEPI->setOperand(0, PN->getIncomingValue(PreheaderIdx));
-
- // Update the GEP to use the new recurrence we just inserted.
- GEPI->setOperand(1, NewAdd);
-
- // If the incoming value is a constant expr GEP, try peeling out the array
- // 0 index if possible to make things simpler.
- if (ConstantExpr *CE = dyn_cast<ConstantExpr>(GEPI->getOperand(0)))
- if (CE->getOpcode() == Instruction::GetElementPtr) {
- unsigned NumOps = CE->getNumOperands();
- assert(NumOps > 1 && "CE folding didn't work!");
- if (CE->getOperand(NumOps-1)->isNullValue()) {
- // Check to make sure the last index really is an array index.
- gep_type_iterator GTI = gep_type_begin(CE);
- for (unsigned i = 1, e = CE->getNumOperands()-1;
- i != e; ++i, ++GTI)
- /*empty*/;
- if (isa<SequentialType>(*GTI)) {
- // Pull the last index out of the constant expr GEP.
- SmallVector<Value*, 8> CEIdxs(CE->op_begin()+1, CE->op_end()-1);
- Constant *NCE = ConstantExpr::getGetElementPtr(CE->getOperand(0),
- &CEIdxs[0],
- CEIdxs.size());
- Value *Idx[2];
- Idx[0] = Constant::getNullValue(Type::Int32Ty);
- Idx[1] = NewAdd;
- GetElementPtrInst *NGEPI = GetElementPtrInst::Create(
- NCE, Idx, Idx + 2,
- GEPI->getName(), GEPI);
- SE->deleteValueFromRecords(GEPI);
- GEPI->replaceAllUsesWith(NGEPI);
- GEPI->eraseFromParent();
- GEPI = NGEPI;
- }
- }
- }
-
-
- // Finally, if there are any other users of the PHI node, we must
- // insert a new GEP instruction that uses the pre-incremented version
- // of the induction amount.
- if (!PN->use_empty()) {
- BasicBlock::iterator InsertPos = PN; ++InsertPos;
- while (isa<PHINode>(InsertPos)) ++InsertPos;
- Value *PreInc =
- GetElementPtrInst::Create(PN->getIncomingValue(PreheaderIdx),
- NewPhi, "", InsertPos);
- PreInc->takeName(PN);
- PN->replaceAllUsesWith(PreInc);
- }
-
- // Delete the old PHI for sure, and the GEP if its otherwise unused.
- DeadInsts.insert(PN);
-
- ++NumPointer;
- Changed = true;
- }
-}
-
/// LinearFunctionTestReplace - This method rewrites the exit condition of the
/// loop to be a canonical != comparison against the incremented loop induction
/// variable. This pass is able to rewrite the exit tests of any loop where the
// Expand the code for the iteration count into the preheader of the loop.
BasicBlock *Preheader = L->getLoopPreheader();
- Value *ExitCnt = Rewriter.expandCodeFor(RHS,
+ Value *ExitCnt = Rewriter.expandCodeFor(RHS, IndVar->getType(),
Preheader->getTerminator());
// Insert a new icmp_ne or icmp_eq instruction before the branch.
// Scan all of the instructions in the loop, looking at those that have
// extra-loop users and which are recurrences.
- SCEVExpander Rewriter(*SE, *LI);
+ SCEVExpander Rewriter(*SE, *LI, *TD);
// We insert the code into the preheader of the loop if the loop contains
// multiple exit blocks, or in the exit block if there is exactly one.
Value *InVal = PN->getIncomingValue(i);
if (!isa<Instruction>(InVal) ||
// SCEV only supports integer expressions for now.
- !isa<IntegerType>(InVal->getType()))
+ (!isa<IntegerType>(InVal->getType()) &&
+ !isa<PointerType>(InVal->getType())))
continue;
// If this pred is for a subloop, not L itself, skip it.
// just reuse it.
Value *&ExitVal = ExitValues[Inst];
if (!ExitVal)
- ExitVal = Rewriter.expandCodeFor(ExitValue, InsertPt);
+ ExitVal = Rewriter.expandCodeFor(ExitValue, PN->getType(), InsertPt);
DOUT << "INDVARS: RLEV: AfterLoopVal = " << *ExitVal
<< " LoopVal = " << *Inst << "\n";
}
void IndVarSimplify::RewriteNonIntegerIVs(Loop *L) {
- // First step. Check to see if there are any trivial GEP pointer recurrences.
+ // First step. Check to see if there are any floating-point recurrences.
// If there are, change them into integer recurrences, permitting analysis by
// the SCEV routines.
//
BasicBlock *Header = L->getHeader();
- BasicBlock *Preheader = L->getLoopPreheader();
SmallPtrSet<Instruction*, 16> DeadInsts;
for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
PHINode *PN = cast<PHINode>(I);
- if (isa<PointerType>(PN->getType()))
- EliminatePointerRecurrence(PN, Preheader, DeadInsts);
- else
- HandleFloatingPointIV(L, PN, DeadInsts);
+ HandleFloatingPointIV(L, PN, DeadInsts);
}
- // If the loop previously had a pointer or floating-point IV, ScalarEvolution
+ // If the loop previously had floating-point IV, ScalarEvolution
// may not have been able to compute a trip count. Now that we've done some
// re-writing, the trip count may be computable.
if (Changed)
/// getEffectiveIndvarType - Determine the widest type that the
/// induction-variable PHINode Phi is cast to.
///
-static const Type *getEffectiveIndvarType(const PHINode *Phi) {
+static const Type *getEffectiveIndvarType(const PHINode *Phi,
+ const TargetData *TD) {
const Type *Ty = Phi->getType();
for (Value::use_const_iterator UI = Phi->use_begin(), UE = Phi->use_end();
else if (const SExtInst *SI = dyn_cast<SExtInst>(UI))
CandidateType = SI->getDestTy();
if (CandidateType &&
- CandidateType->getPrimitiveSizeInBits() >
- Ty->getPrimitiveSizeInBits())
+ TD->getTypeSizeInBits(CandidateType) > TD->getTypeSizeInBits(Ty))
Ty = CandidateType;
}
static const PHINode *TestOrigIVForWrap(const Loop *L,
const BranchInst *BI,
const Instruction *OrigCond,
+ const TargetData *TD,
bool &NoSignedWrap,
bool &NoUnsignedWrap,
const ConstantInt* &InitialVal,
if (const SExtInst *SI = dyn_cast<SExtInst>(CmpLHS)) {
if (!isa<ConstantInt>(CmpRHS) ||
!cast<ConstantInt>(CmpRHS)->getValue()
- .isSignedIntN(IncrInst->getType()->getPrimitiveSizeInBits()))
+ .isSignedIntN(TD->getTypeSizeInBits(IncrInst->getType())))
return 0;
IncrInst = SI->getOperand(0);
}
if (const ZExtInst *ZI = dyn_cast<ZExtInst>(CmpLHS)) {
if (!isa<ConstantInt>(CmpRHS) ||
!cast<ConstantInt>(CmpRHS)->getValue()
- .isIntN(IncrInst->getType()->getPrimitiveSizeInBits()))
+ .isIntN(TD->getTypeSizeInBits(IncrInst->getType())))
return 0;
IncrInst = ZI->getOperand(0);
}
SE->getAddRecExpr(ExtendedStart, ExtendedStep, L);
if (LargestType != myType)
ExtendedAddRec = SE->getTruncateExpr(ExtendedAddRec, myType);
- return Rewriter.expandCodeFor(ExtendedAddRec, InsertPt);
+ return Rewriter.expandCodeFor(ExtendedAddRec, myType, InsertPt);
}
static Value *getZeroExtendedTruncVar(const SCEVAddRecExpr *AR,
SE->getAddRecExpr(ExtendedStart, ExtendedStep, L);
if (LargestType != myType)
ExtendedAddRec = SE->getTruncateExpr(ExtendedAddRec, myType);
- return Rewriter.expandCodeFor(ExtendedAddRec, InsertPt);
+ return Rewriter.expandCodeFor(ExtendedAddRec, myType, InsertPt);
}
/// allUsesAreSameTyped - See whether all Uses of I are instructions
bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) {
LI = &getAnalysis<LoopInfo>();
+ TD = &getAnalysis<TargetData>();
SE = &getAnalysis<ScalarEvolution>();
Changed = false;
- // If there are any floating-point or pointer recurrences, attempt to
+ // If there are any floating-point recurrences, attempt to
// transform them to use integer recurrences.
RewriteNonIntegerIVs(L);
for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
PHINode *PN = cast<PHINode>(I);
- if (PN->getType()->isInteger()) { // FIXME: when we have fast-math, enable!
+ if (PN->getType()->isInteger() || isa<PointerType>(PN->getType())) {
SCEVHandle SCEV = SE->getSCEV(PN);
// FIXME: It is an extremely bad idea to indvar substitute anything more
// complex than affine induction variables. Doing so will put expensive
SmallSetVector<const Type *, 4> SizesToInsert;
if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount)) {
LargestType = BackedgeTakenCount->getType();
- SizesToInsert.insert(BackedgeTakenCount->getType());
+ if (isa<PointerType>(LargestType))
+ LargestType = TD->getIntPtrType();
+ SizesToInsert.insert(LargestType);
}
for (unsigned i = 0, e = IndVars.size(); i != e; ++i) {
const PHINode *PN = IndVars[i].first;
- SizesToInsert.insert(PN->getType());
- const Type *EffTy = getEffectiveIndvarType(PN);
+ const Type *PNTy = PN->getType();
+ if (isa<PointerType>(PNTy)) PNTy = TD->getIntPtrType();
+ SizesToInsert.insert(PNTy);
+ const Type *EffTy = getEffectiveIndvarType(PN, TD);
+ if (isa<PointerType>(EffTy)) EffTy = TD->getIntPtrType();
SizesToInsert.insert(EffTy);
if (!LargestType ||
- EffTy->getPrimitiveSizeInBits() >
- LargestType->getPrimitiveSizeInBits())
+ TD->getTypeSizeInBits(EffTy) >
+ TD->getTypeSizeInBits(LargestType))
LargestType = EffTy;
}
// Create a rewriter object which we'll use to transform the code with.
- SCEVExpander Rewriter(*SE, *LI);
+ SCEVExpander Rewriter(*SE, *LI, *TD);
// Now that we know the largest of of the induction variables in this loop,
// insert a canonical induction variable of the largest size.
if (Instruction *OrigCond = dyn_cast<Instruction>(BI->getCondition())) {
// Determine if the OrigIV will ever undergo overflow.
OrigControllingPHI =
- TestOrigIVForWrap(L, BI, OrigCond,
+ TestOrigIVForWrap(L, BI, OrigCond, TD,
NoSignedWrap, NoUnsignedWrap,
InitialVal, IncrVal, LimitVal);
while (!IndVars.empty()) {
PHINode *PN = IndVars.back().first;
SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(IndVars.back().second);
- Value *NewVal = Rewriter.expandCodeFor(AR, InsertPt);
+ Value *NewVal = Rewriter.expandCodeFor(AR, PN->getType(), InsertPt);
DOUT << "INDVARS: Rewrote IV '" << *AR << "' " << *PN
<< " into = " << *NewVal << "\n";
NewVal->takeName(PN);
-//===- LoopStrengthReduce.cpp - Strength Reduce GEPs in Loops -------------===//
+//===- LoopStrengthReduce.cpp - Strength Reduce IVs in Loops --------------===//
//
// The LLVM Compiler Infrastructure
//
//===----------------------------------------------------------------------===//
//
// This pass performs a strength reduction on array references inside loops that
-// have as one or more of their components the loop induction variable. This is
-// accomplished by creating a new Value to hold the initial value of the array
-// access for the first iteration, and then creating a new GEP instruction in
-// the loop to increment the value by the appropriate amount.
+// have as one or more of their components the loop induction variable.
//
//===----------------------------------------------------------------------===//
/// dependent on random ordering of pointers in the process.
SmallVector<SCEVHandle, 16> StrideOrder;
- /// GEPlist - A list of the GEP's that have been remembered in the SCEV
- /// data structures. SCEV does not know to update these when the operands
- /// of the GEP are changed, which means we cannot leave them live across
- /// loops.
- SmallVector<GetElementPtrInst *, 16> GEPlist;
-
- /// CastedValues - As we need to cast values to uintptr_t, this keeps track
- /// of the casted version of each value. This is accessed by
- /// getCastedVersionOf.
- DenseMap<Value*, Value*> CastedPointers;
-
/// DeadInsts - Keep track of instructions we may have made dead, so that
/// we can remove them after we are done working.
SmallVector<Instruction*, 16> DeadInsts;
AU.addRequired<ScalarEvolution>();
AU.addPreserved<ScalarEvolution>();
}
-
- /// getCastedVersionOf - Return the specified value casted to uintptr_t.
- ///
- Value *getCastedVersionOf(Instruction::CastOps opcode, Value *V);
+
private:
bool AddUsersIfInteresting(Instruction *I, Loop *L,
SmallPtrSet<Instruction*,16> &Processed);
- SCEVHandle GetExpressionSCEV(Instruction *E);
ICmpInst *ChangeCompareStride(Loop *L, ICmpInst *Cond,
IVStrideUse* &CondUse,
const SCEVHandle* &CondStride);
return new LoopStrengthReduce(TLI);
}
-/// getCastedVersionOf - Return the specified value casted to uintptr_t. This
-/// assumes that the Value* V is of integer or pointer type only.
-///
-Value *LoopStrengthReduce::getCastedVersionOf(Instruction::CastOps opcode,
- Value *V) {
- if (V->getType() == UIntPtrTy) return V;
- if (Constant *CB = dyn_cast<Constant>(V))
- return ConstantExpr::getCast(opcode, CB, UIntPtrTy);
-
- Value *&New = CastedPointers[V];
- if (New) return New;
-
- New = SCEVExpander::InsertCastOfTo(opcode, V, UIntPtrTy);
- DeadInsts.push_back(cast<Instruction>(New));
- return New;
-}
-
-
/// DeleteTriviallyDeadInstructions - If any of the instructions is the
/// specified set are trivially dead, delete them and see if this makes any of
/// their operands subsequently dead.
}
}
-
-/// GetExpressionSCEV - Compute and return the SCEV for the specified
-/// instruction.
-SCEVHandle LoopStrengthReduce::GetExpressionSCEV(Instruction *Exp) {
- // Pointer to pointer bitcast instructions return the same value as their
- // operand.
- if (BitCastInst *BCI = dyn_cast<BitCastInst>(Exp)) {
- if (SE->hasSCEV(BCI) || !isa<Instruction>(BCI->getOperand(0)))
- return SE->getSCEV(BCI);
- SCEVHandle R = GetExpressionSCEV(cast<Instruction>(BCI->getOperand(0)));
- SE->setSCEV(BCI, R);
- return R;
- }
-
- // Scalar Evolutions doesn't know how to compute SCEV's for GEP instructions.
- // If this is a GEP that SE doesn't know about, compute it now and insert it.
- // If this is not a GEP, or if we have already done this computation, just let
- // SE figure it out.
- GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Exp);
- if (!GEP || SE->hasSCEV(GEP))
- return SE->getSCEV(Exp);
-
- // Analyze all of the subscripts of this getelementptr instruction, looking
- // for uses that are determined by the trip count of the loop. First, skip
- // all operands the are not dependent on the IV.
-
- // Build up the base expression. Insert an LLVM cast of the pointer to
- // uintptr_t first.
- SCEVHandle GEPVal = SE->getUnknown(
- getCastedVersionOf(Instruction::PtrToInt, GEP->getOperand(0)));
-
- gep_type_iterator GTI = gep_type_begin(GEP);
-
- for (User::op_iterator i = GEP->op_begin() + 1, e = GEP->op_end();
- i != e; ++i, ++GTI) {
- // If this is a use of a recurrence that we can analyze, and it comes before
- // Op does in the GEP operand list, we will handle this when we process this
- // operand.
- if (const StructType *STy = dyn_cast<StructType>(*GTI)) {
- const StructLayout *SL = TD->getStructLayout(STy);
- unsigned Idx = cast<ConstantInt>(*i)->getZExtValue();
- uint64_t Offset = SL->getElementOffset(Idx);
- GEPVal = SE->getAddExpr(GEPVal,
- SE->getIntegerSCEV(Offset, UIntPtrTy));
- } else {
- unsigned GEPOpiBits =
- (*i)->getType()->getPrimitiveSizeInBits();
- unsigned IntPtrBits = UIntPtrTy->getPrimitiveSizeInBits();
- Instruction::CastOps opcode = (GEPOpiBits < IntPtrBits ?
- Instruction::SExt : (GEPOpiBits > IntPtrBits ? Instruction::Trunc :
- Instruction::BitCast));
- Value *OpVal = getCastedVersionOf(opcode, *i);
- SCEVHandle Idx = SE->getSCEV(OpVal);
-
- uint64_t TypeSize = TD->getTypePaddedSize(GTI.getIndexedType());
- if (TypeSize != 1)
- Idx = SE->getMulExpr(Idx,
- SE->getConstant(ConstantInt::get(UIntPtrTy,
- TypeSize)));
- GEPVal = SE->getAddExpr(GEPVal, Idx);
- }
- }
-
- SE->setSCEV(GEP, GEPVal);
- GEPlist.push_back(GEP);
- return GEPVal;
-}
-
/// containsAddRecFromDifferentLoop - Determine whether expression S involves a
/// subexpression that is an AddRec from a loop other than L. An outer loop
/// of L is OK, but not an inner loop nor a disjoint loop.
return true; // Instruction already handled.
// Get the symbolic expression for this instruction.
- SCEVHandle ISE = GetExpressionSCEV(I);
+ SCEVHandle ISE = SE->getSCEV(I);
if (isa<SCEVCouldNotCompute>(ISE)) return false;
// Get the start and stride for this expression.
SmallVectorImpl<Instruction*> &DeadInsts);
Value *InsertCodeForBaseAtPosition(const SCEVHandle &NewBase,
+ const Type *Ty,
SCEVExpander &Rewriter,
Instruction *IP, Loop *L);
void dump() const;
}
Value *BasedUser::InsertCodeForBaseAtPosition(const SCEVHandle &NewBase,
+ const Type *Ty,
SCEVExpander &Rewriter,
Instruction *IP, Loop *L) {
// Figure out where we *really* want to insert this code. In particular, if
InsertLoop = InsertLoop->getParentLoop();
}
- Value *Base = Rewriter.expandCodeFor(NewBase, BaseInsertPt);
+ Value *Base = Rewriter.expandCodeFor(NewBase, Ty, BaseInsertPt);
// If there is no immediate value, skip the next part.
if (Imm->isZero())
// Always emit the immediate (if non-zero) into the same block as the user.
SCEVHandle NewValSCEV = SE->getAddExpr(SE->getUnknown(Base), Imm);
- return Rewriter.expandCodeFor(NewValSCEV, IP);
-
+ return Rewriter.expandCodeFor(NewValSCEV, Ty, IP);
}
while (isa<PHINode>(InsertPt)) ++InsertPt;
}
}
- Value *NewVal = InsertCodeForBaseAtPosition(NewBase, Rewriter, InsertPt, L);
- // Adjust the type back to match the Inst. Note that we can't use InsertPt
- // here because the SCEVExpander may have inserted the instructions after
- // that point, in its efforts to avoid inserting redundant expressions.
- if (isa<PointerType>(OperandValToReplace->getType())) {
- NewVal = SCEVExpander::InsertCastOfTo(Instruction::IntToPtr,
- NewVal,
- OperandValToReplace->getType());
- }
+ Value *NewVal = InsertCodeForBaseAtPosition(NewBase,
+ OperandValToReplace->getType(),
+ Rewriter, InsertPt, L);
// Replace the use of the operand Value with the new Phi we just created.
Inst->replaceUsesOfWith(OperandValToReplace, NewVal);
Instruction *InsertPt = (L->contains(OldLoc->getParent())) ?
PN->getIncomingBlock(i)->getTerminator() :
OldLoc->getParent()->getTerminator();
- Code = InsertCodeForBaseAtPosition(NewBase, Rewriter, InsertPt, L);
-
- // Adjust the type back to match the PHI. Note that we can't use
- // InsertPt here because the SCEVExpander may have inserted its
- // instructions after that point, in its efforts to avoid inserting
- // redundant expressions.
- if (isa<PointerType>(PN->getType())) {
- Code = SCEVExpander::InsertCastOfTo(Instruction::IntToPtr,
- Code,
- PN->getType());
- }
+ Code = InsertCodeForBaseAtPosition(NewBase, PN->getType(),
+ Rewriter, InsertPt, L);
DOUT << " Changing PHI use to ";
DEBUG(WriteAsOperand(*DOUT, Code, /*PrintType=*/false));
}
if (SCEVUnknown *SU = dyn_cast<SCEVUnknown>(V))
- if (ConstantExpr *CE = dyn_cast<ConstantExpr>(SU->getValue()))
- if (TLI && CE->getOpcode() == Instruction::PtrToInt) {
- Constant *Op0 = CE->getOperand(0);
- if (GlobalValue *GV = dyn_cast<GlobalValue>(Op0)) {
- TargetLowering::AddrMode AM;
- AM.BaseGV = GV;
- AM.HasBaseReg = HasBaseReg;
- return TLI->isLegalAddressingMode(AM, UseTy);
- }
- }
+ if (GlobalValue *GV = dyn_cast<GlobalValue>(SU->getValue())) {
+ TargetLowering::AddrMode AM;
+ AM.BaseGV = GV;
+ AM.HasBaseReg = HasBaseReg;
+ return TLI->isLegalAddressingMode(AM, UseTy);
+ }
+
return false;
}
///
static PHINode *InsertAffinePhi(SCEVHandle Start, SCEVHandle Step,
const Loop *L,
+ const TargetData *TD,
SCEVExpander &Rewriter) {
assert(Start->isLoopInvariant(L) && "New PHI start is not loop invariant!");
assert(Step->isLoopInvariant(L) && "New PHI stride is not loop invariant!");
BasicBlock *Header = L->getHeader();
BasicBlock *Preheader = L->getLoopPreheader();
BasicBlock *LatchBlock = L->getLoopLatch();
+ const Type *Ty = Start->getType();
+ if (isa<PointerType>(Ty)) Ty = TD->getIntPtrType();
- PHINode *PN = PHINode::Create(Start->getType(), "lsr.iv", Header->begin());
- PN->addIncoming(Rewriter.expandCodeFor(Start, Preheader->getTerminator()),
+ PHINode *PN = PHINode::Create(Ty, "lsr.iv", Header->begin());
+ PN->addIncoming(Rewriter.expandCodeFor(Start, Ty, Preheader->getTerminator()),
Preheader);
// If the stride is negative, insert a sub instead of an add for the
// Insert an add instruction right before the terminator corresponding
// to the back-edge.
- Value *StepV = Rewriter.expandCodeFor(IncAmount, Preheader->getTerminator());
+ Value *StepV = Rewriter.expandCodeFor(IncAmount, Ty,
+ Preheader->getTerminator());
Instruction *IncV;
if (isNegative) {
IncV = BinaryOperator::CreateSub(PN, StepV, "lsr.iv.next",
SCEVHandle Imm = UsersToProcess[i].Imm;
SCEVHandle Base = UsersToProcess[i].Base;
SCEVHandle Start = SE->getAddExpr(CommonExprs, Base, Imm);
- PHINode *Phi = InsertAffinePhi(Start, Stride, L,
+ PHINode *Phi = InsertAffinePhi(Start, Stride, L, TD,
PreheaderRewriter);
// Loop over all the users with the same base.
do {
DOUT << " Inserting new PHI:\n";
PHINode *Phi = InsertAffinePhi(SE->getUnknown(CommonBaseV),
- Stride, L,
+ Stride, L, TD,
PreheaderRewriter);
// Remember this in case a later stride is multiple of this.
bool HaveCommonExprs = !CommonExprs->isZero();
const Type *ReplacedTy = CommonExprs->getType();
+ if (isa<PointerType>(ReplacedTy)) ReplacedTy = TD->getIntPtrType();
// If all uses are addresses, consider sinking the immediate part of the
// common expression back into uses if they can fit in the immediate fields.
// If the immediate part of the common expression is a GV, check if it's
// possible to fold it into the target addressing mode.
GlobalValue *GV = 0;
- if (SCEVUnknown *SU = dyn_cast<SCEVUnknown>(Imm)) {
- if (ConstantExpr *CE = dyn_cast<ConstantExpr>(SU->getValue()))
- if (CE->getOpcode() == Instruction::PtrToInt)
- GV = dyn_cast<GlobalValue>(CE->getOperand(0));
- }
+ if (SCEVUnknown *SU = dyn_cast<SCEVUnknown>(Imm))
+ GV = dyn_cast<GlobalValue>(SU->getValue());
int64_t Offset = 0;
if (SCEVConstant *SC = dyn_cast<SCEVConstant>(Imm))
Offset = SC->getValue()->getSExtValue();
<< *Stride << ":\n"
<< " Common base: " << *CommonExprs << "\n";
- SCEVExpander Rewriter(*SE, *LI);
- SCEVExpander PreheaderRewriter(*SE, *LI);
+ SCEVExpander Rewriter(*SE, *LI, *TD);
+ SCEVExpander PreheaderRewriter(*SE, *LI, *TD);
BasicBlock *Preheader = L->getLoopPreheader();
Instruction *PreInsertPt = Preheader->getTerminator();
PreheaderRewriter);
} else {
// Emit the initial base value into the loop preheader.
- CommonBaseV = PreheaderRewriter.expandCodeFor(CommonExprs, PreInsertPt);
+ CommonBaseV = PreheaderRewriter.expandCodeFor(CommonExprs, ReplacedTy,
+ PreInsertPt);
// If all uses are addresses, check if it is possible to reuse an IV with a
// stride that is a factor of this stride. And that the multiple is a number
Instruction *Inst = UsersToProcess.back().Inst;
// Emit the code for Base into the preheader.
- Value *BaseV = PreheaderRewriter.expandCodeFor(Base, PreInsertPt);
-
- DOUT << " Examining uses with BASE ";
- DEBUG(WriteAsOperand(*DOUT, BaseV, /*PrintType=*/false));
- DOUT << ":\n";
-
- // If BaseV is a constant other than 0, make sure that it gets inserted into
- // the preheader, instead of being forward substituted into the uses. We do
- // this by forcing a BitCast (noop cast) to be inserted into the preheader
- // in this case.
- if (Constant *C = dyn_cast<Constant>(BaseV)) {
- if (!C->isNullValue() && !fitsInAddressMode(Base, getAccessType(Inst),
- TLI, false)) {
+ Value *BaseV = 0;
+ if (!Base->isZero()) {
+ BaseV = PreheaderRewriter.expandCodeFor(Base, Base->getType(),
+ PreInsertPt);
+
+ DOUT << " INSERTING code for BASE = " << *Base << ":";
+ if (BaseV->hasName())
+ DOUT << " Result value name = %" << BaseV->getNameStr();
+ DOUT << "\n";
+
+ // If BaseV is a non-zero constant, make sure that it gets inserted into
+ // the preheader, instead of being forward substituted into the uses. We
+ // do this by forcing a BitCast (noop cast) to be inserted into the
+ // preheader in this case.
+ if (!fitsInAddressMode(Base, getAccessType(Inst), TLI, false)) {
// We want this constant emitted into the preheader! This is just
// using cast as a copy so BitCast (no-op cast) is appropriate
BaseV = new BitCastInst(BaseV, BaseV->getType(), "preheaderinsert",
User.Inst->moveBefore(LatchBlock->getTerminator());
}
if (RewriteOp->getType() != ReplacedTy) {
- Instruction::CastOps opcode = Instruction::Trunc;
- if (ReplacedTy->getPrimitiveSizeInBits() ==
- RewriteOp->getType()->getPrimitiveSizeInBits())
- opcode = Instruction::BitCast;
+ Instruction::CastOps opcode =
+ CastInst::getCastOpcode(RewriteOp, false, ReplacedTy, false);
+ assert(opcode != Instruction::SExt &&
+ opcode != Instruction::ZExt &&
+ "Unexpected widening cast!");
RewriteOp = SCEVExpander::InsertCastOfTo(opcode, RewriteOp, ReplacedTy);
}
// If we are reusing the iv, then it must be multiplied by a constant
// factor to take advantage of the addressing mode scale component.
- if (!isa<SCEVConstant>(RewriteFactor) ||
- !cast<SCEVConstant>(RewriteFactor)->isZero()) {
+ if (!RewriteFactor->isZero()) {
// If we're reusing an IV with a nonzero base (currently this happens
// only when all reuses are outside the loop) subtract that base here.
// The base has been used to initialize the PHI node but we don't want
// When this use is outside the loop, we earlier subtracted the
// common base, and are adding it back here. Use the same expression
// as before, rather than CommonBaseV, so DAGCombiner will zap it.
- if (!isa<ConstantInt>(CommonBaseV) ||
- !cast<ConstantInt>(CommonBaseV)->isZero()) {
+ if (!CommonExprs->isZero()) {
if (L->contains(User.Inst->getParent()))
RewriteExpr = SE->getAddExpr(RewriteExpr,
SE->getUnknown(CommonBaseV));
// Now that we know what we need to do, insert code before User for the
// immediate and any loop-variant expressions.
- if (!isa<ConstantInt>(BaseV) || !cast<ConstantInt>(BaseV)->isZero())
+ if (BaseV)
// Add BaseV to the PHI value if needed.
RewriteExpr = SE->getAddExpr(RewriteExpr, SE->getUnknown(BaseV));
// e.g.
// 4, -1, X, 1, 2 ==> 1, -1, 2, 4, X
struct StrideCompare {
+ const TargetData *TD;
+ explicit StrideCompare(const TargetData *td) : TD(td) {}
+
bool operator()(const SCEVHandle &LHS, const SCEVHandle &RHS) {
SCEVConstant *LHSC = dyn_cast<SCEVConstant>(LHS);
SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS);
// If it's the same value but different type, sort by bit width so
// that we emit larger induction variables before smaller
// ones, letting the smaller be re-written in terms of larger ones.
- return RHS->getBitWidth() < LHS->getBitWidth();
+ return TD->getTypeSizeInBits(RHS->getType()) <
+ TD->getTypeSizeInBits(LHS->getType());
}
return LHSC && !RHSC;
}
ICmpInst::Predicate Predicate = Cond->getPredicate();
int64_t CmpSSInt = SC->getValue()->getSExtValue();
- unsigned BitWidth = (*CondStride)->getBitWidth();
+ unsigned BitWidth = TD->getTypeSizeInBits((*CondStride)->getType());
uint64_t SignBit = 1ULL << (BitWidth-1);
const Type *CmpTy = Cond->getOperand(0)->getType();
const Type *NewCmpTy = NULL;
- unsigned TyBits = CmpTy->getPrimitiveSizeInBits();
+ unsigned TyBits = TD->getTypeSizeInBits(CmpTy);
unsigned NewTyBits = 0;
SCEVHandle *NewStride = NULL;
Value *NewCmpLHS = NULL;
continue;
NewCmpTy = NewCmpLHS->getType();
- NewTyBits = isa<PointerType>(NewCmpTy)
- ? UIntPtrTy->getPrimitiveSizeInBits()
- : NewCmpTy->getPrimitiveSizeInBits();
+ NewTyBits = TD->getTypeSizeInBits(NewCmpTy);
if (RequiresTypeConversion(NewCmpTy, CmpTy)) {
// Check if it is possible to rewrite it using
// an iv / stride of a smaller integer type.
#endif
// Sort the StrideOrder so we process larger strides first.
- std::stable_sort(StrideOrder.begin(), StrideOrder.end(), StrideCompare());
+ std::stable_sort(StrideOrder.begin(), StrideOrder.end(), StrideCompare(TD));
// Optimize induction variables. Some indvar uses can be transformed to use
// strides that will be needed for other purposes. A common example of this
}
// We're done analyzing this loop; release all the state we built up for it.
- CastedPointers.clear();
IVUsesByStride.clear();
IVsByStride.clear();
StrideOrder.clear();
- for (unsigned i=0; i<GEPlist.size(); i++)
- SE->deleteValueFromRecords(GEPlist[i]);
- GEPlist.clear();
// Clean up after ourselves
if (!DeadInsts.empty()) {
; RUN: llvm-as < %s | llc -mtriple=arm-apple-darwin -relocation-model=pic \
-; RUN: -mattr=+v6 -stats |& grep asm-printer | grep 41
+; RUN: -mattr=+v6 -ifcvt-limit=0 -stats |& grep asm-printer | grep 35
define void @test(i32 %tmp56222, i32 %tmp36224, i32 %tmp46223, i32 %i.0196.0.ph, i32 %tmp8, i32* %tmp1011, i32** %tmp1, i32* %d2.1.out, i32* %d3.1.out, i32* %d0.1.out, i32* %d1.1.out) {
newFuncRoot:
; RUN: llvm-as < %s | llc -march=x86-64 -f -o %t
; RUN: grep inc %t | count 2
; RUN: grep addq %t | count 13
-; RUN: grep leaq %t | count 9
+; RUN: grep leaq %t | count 8
+; RUN: grep leal %t | count 4
; RUN: grep movq %t | count 5
; IV users in each of the loops from other loops shouldn't cause LSR
-; RUN: llvm-as < %s | llc -march=x86 -stats |& grep {Number of reloads omited}
-; RUN: llvm-as < %s | llc -march=x86 -stats |& grep {Number of available reloads turned into copies}
+; RUN: llvm-as < %s | llc -march=x86 -stats |& grep {Number of reloads omited} | grep 2
+; RUN: llvm-as < %s | llc -march=x86 -stats |& not grep {Number of available reloads turned into copies}
+; RUN: llvm-as < %s | llc -march=x86 -stats |& grep {Number of machine instrs printed} | grep 39
; PR3495
target triple = "i386-pc-linux-gnu"
; RUN: llvm-as < %s | llc -march=x86 -relocation-model=static | not grep lea
; RUN: llvm-as < %s | llc -march=x86-64 | not grep lea
-; _P should be sunk into the loop and folded into the address mode. There
+; P should be sunk into the loop and folded into the address mode. There
; shouldn't be any lea instructions inside the loop.
@B = external global [1000 x i8], align 32
projects / oota-llvm.git / commitdiff