X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FScalarEvolution.cpp;h=a81f24f117f7f27dbf3ba0d5a5d1086a3b85a3b2;hb=643a79b4b32610651fe728ff95c9fecc60eaa687;hp=2bf5e5486abae44aa873449eceaae6a19a03a052;hpb=f1ab4b4eac5603d19c20f4a508f93a118a52bdd5;p=oota-llvm.git diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp index 2bf5e5486ab..a81f24f117f 100644 --- a/lib/Analysis/ScalarEvolution.cpp +++ b/lib/Analysis/ScalarEvolution.cpp @@ -1,10 +1,10 @@ //===- ScalarEvolution.cpp - Scalar Evolution Analysis ----------*- C++ -*-===// -// +// // The LLVM Compiler Infrastructure // // This file was developed by the LLVM research group and is distributed under // the University of Illinois Open Source License. See LICENSE.TXT for details. -// +// //===----------------------------------------------------------------------===// // // This file contains the implementation of the scalar evolution analysis @@ -28,15 +28,11 @@ // have folders that are used to build the *canonical* representation for a // particular expression. These folders are capable of using a variety of // rewrite rules to simplify the expressions. -// +// // Once the folders are defined, we can implement the more interesting // higher-level code, such as the code that recognizes PHI nodes of various // types, computes the execution count of a loop, etc. // -// Orthogonal to the analysis of code above, this file also implements the -// ScalarEvolutionRewriter class, which is used to emit code that represents the -// various recurrences present in a loop, in canonical forms. -// // TODO: We should use these routines and value representations to implement // dependence analysis! // @@ -63,45 +59,51 @@ // //===----------------------------------------------------------------------===// +#define DEBUG_TYPE "scalar-evolution" #include "llvm/Analysis/ScalarEvolutionExpressions.h" #include "llvm/Constants.h" #include "llvm/DerivedTypes.h" +#include "llvm/GlobalVariable.h" #include "llvm/Instructions.h" -#include "llvm/Type.h" -#include "llvm/Value.h" +#include "llvm/Analysis/ConstantFolding.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Assembly/Writer.h" #include "llvm/Transforms/Scalar.h" -#include "llvm/Transforms/Utils/Local.h" #include "llvm/Support/CFG.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Compiler.h" #include "llvm/Support/ConstantRange.h" #include "llvm/Support/InstIterator.h" -#include "Support/CommandLine.h" -#include "Support/Statistic.h" +#include "llvm/Support/ManagedStatic.h" +#include "llvm/Support/MathExtras.h" +#include "llvm/Support/Streams.h" +#include "llvm/ADT/Statistic.h" +#include +#include #include using namespace llvm; +STATISTIC(NumBruteForceEvaluations, + "Number of brute force evaluations needed to " + "calculate high-order polynomial exit values"); +STATISTIC(NumArrayLenItCounts, + "Number of trip counts computed with array length"); +STATISTIC(NumTripCountsComputed, + "Number of loops with predictable loop counts"); +STATISTIC(NumTripCountsNotComputed, + "Number of loops without predictable loop counts"); +STATISTIC(NumBruteForceTripCountsComputed, + "Number of loops with trip counts computed by force"); + +cl::opt +MaxBruteForceIterations("scalar-evolution-max-iterations", cl::ReallyHidden, + cl::desc("Maximum number of iterations SCEV will " + "symbolically execute a constant derived loop"), + cl::init(100)); + namespace { - RegisterAnalysis - R("scalar-evolution", "Scalar Evolution Analysis Printer"); - - Statistic<> - NumBruteForceEvaluations("scalar-evolution", - "Number of brute force evaluations needed to calculate high-order polynomial exit values"); - Statistic<> - NumTripCountsComputed("scalar-evolution", - "Number of loops with predictable loop counts"); - Statistic<> - NumTripCountsNotComputed("scalar-evolution", - "Number of loops without predictable loop counts"); - Statistic<> - NumBruteForceTripCountsComputed("scalar-evolution", - "Number of loops with trip counts computed by force"); - - cl::opt - MaxBruteForceIterations("scalar-evolution-max-iterations", cl::ReallyHidden, - cl::desc("Maximum number of iterations SCEV will symbolically execute a constant derived loop"), - cl::init(100)); + RegisterPass + R("scalar-evolution", "Scalar Evolution Analysis"); } //===----------------------------------------------------------------------===// @@ -111,25 +113,9 @@ namespace { //===----------------------------------------------------------------------===// // Implementation of the SCEV class. // -namespace { - /// SCEVComplexityCompare - Return true if the complexity of the LHS is less - /// than the complexity of the RHS. If the SCEVs have identical complexity, - /// order them by their addresses. This comparator is used to canonicalize - /// expressions. - struct SCEVComplexityCompare { - bool operator()(SCEV *LHS, SCEV *RHS) { - if (LHS->getSCEVType() < RHS->getSCEVType()) - return true; - if (LHS->getSCEVType() == RHS->getSCEVType()) - return LHS < RHS; - return false; - } - }; -} - SCEV::~SCEV() {} void SCEV::dump() const { - print(std::cerr); + print(cerr); } /// getValueRange - Return the tightest constant bounds that this value is @@ -137,7 +123,6 @@ void SCEV::dump() const { ConstantRange SCEV::getValueRange() const { const Type *Ty = getType(); assert(Ty->isInteger() && "Can't get range for a non-integer SCEV!"); - Ty = Ty->getUnsignedVersion(); // Default to a full range if no better information is available. return ConstantRange(getType()); } @@ -160,13 +145,12 @@ bool SCEVCouldNotCompute::hasComputableLoopEvolution(const Loop *L) const { return false; } -Value *SCEVCouldNotCompute::expandCodeFor(ScalarEvolutionRewriter &SER, - Instruction *InsertPt) { - assert(0 && "Attempt to use a SCEVCouldNotCompute object!"); - return 0; +SCEVHandle SCEVCouldNotCompute:: +replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, + const SCEVHandle &Conc) const { + return this; } - void SCEVCouldNotCompute::print(std::ostream &OS) const { OS << "***COULDNOTCOMPUTE***"; } @@ -179,21 +163,15 @@ bool SCEVCouldNotCompute::classof(const SCEV *S) { // SCEVConstants - Only allow the creation of one SCEVConstant for any // particular value. Don't use a SCEVHandle here, or else the object will // never be deleted! -static std::map SCEVConstants; - +static ManagedStatic > SCEVConstants; + SCEVConstant::~SCEVConstant() { - SCEVConstants.erase(V); + SCEVConstants->erase(V); } SCEVHandle SCEVConstant::get(ConstantInt *V) { - // Make sure that SCEVConstant instances are all unsigned. - if (V->getType()->isSigned()) { - const Type *NewTy = V->getType()->getUnsignedVersion(); - V = cast(ConstantExpr::getCast(V, NewTy)); - } - - SCEVConstant *&R = SCEVConstants[V]; + SCEVConstant *&R = (*SCEVConstants)[V]; if (R == 0) R = new SCEVConstant(V); return R; } @@ -211,19 +189,19 @@ void SCEVConstant::print(std::ostream &OS) const { // SCEVTruncates - Only allow the creation of one SCEVTruncateExpr for any // particular input. Don't use a SCEVHandle here, or else the object will // never be deleted! -static std::map, SCEVTruncateExpr*> SCEVTruncates; +static ManagedStatic, + SCEVTruncateExpr*> > SCEVTruncates; SCEVTruncateExpr::SCEVTruncateExpr(const SCEVHandle &op, const Type *ty) : SCEV(scTruncate), Op(op), Ty(ty) { assert(Op->getType()->isInteger() && Ty->isInteger() && - Ty->isUnsigned() && "Cannot truncate non-integer value!"); - assert(Op->getType()->getPrimitiveSize() > Ty->getPrimitiveSize() && - "This is not a truncating conversion!"); + assert(Op->getType()->getPrimitiveSizeInBits() > Ty->getPrimitiveSizeInBits() + && "This is not a truncating conversion!"); } SCEVTruncateExpr::~SCEVTruncateExpr() { - SCEVTruncates.erase(std::make_pair(Op, Ty)); + SCEVTruncates->erase(std::make_pair(Op, Ty)); } ConstantRange SCEVTruncateExpr::getValueRange() const { @@ -237,20 +215,19 @@ void SCEVTruncateExpr::print(std::ostream &OS) const { // SCEVZeroExtends - Only allow the creation of one SCEVZeroExtendExpr for any // particular input. Don't use a SCEVHandle here, or else the object will never // be deleted! -static std::map, - SCEVZeroExtendExpr*> SCEVZeroExtends; +static ManagedStatic, + SCEVZeroExtendExpr*> > SCEVZeroExtends; SCEVZeroExtendExpr::SCEVZeroExtendExpr(const SCEVHandle &op, const Type *ty) - : SCEV(scTruncate), Op(Op), Ty(ty) { + : SCEV(scZeroExtend), Op(op), Ty(ty) { assert(Op->getType()->isInteger() && Ty->isInteger() && - Ty->isUnsigned() && "Cannot zero extend non-integer value!"); - assert(Op->getType()->getPrimitiveSize() < Ty->getPrimitiveSize() && - "This is not an extending conversion!"); + assert(Op->getType()->getPrimitiveSizeInBits() < Ty->getPrimitiveSizeInBits() + && "This is not an extending conversion!"); } SCEVZeroExtendExpr::~SCEVZeroExtendExpr() { - SCEVZeroExtends.erase(std::make_pair(Op, Ty)); + SCEVZeroExtends->erase(std::make_pair(Op, Ty)); } ConstantRange SCEVZeroExtendExpr::getValueRange() const { @@ -264,13 +241,13 @@ void SCEVZeroExtendExpr::print(std::ostream &OS) const { // SCEVCommExprs - Only allow the creation of one SCEVCommutativeExpr for any // particular input. Don't use a SCEVHandle here, or else the object will never // be deleted! -static std::map >, - SCEVCommutativeExpr*> SCEVCommExprs; +static ManagedStatic >, + SCEVCommutativeExpr*> > SCEVCommExprs; SCEVCommutativeExpr::~SCEVCommutativeExpr() { - SCEVCommExprs.erase(std::make_pair(getSCEVType(), - std::vector(Operands.begin(), - Operands.end()))); + SCEVCommExprs->erase(std::make_pair(getSCEVType(), + std::vector(Operands.begin(), + Operands.end()))); } void SCEVCommutativeExpr::print(std::ostream &OS) const { @@ -282,41 +259,90 @@ void SCEVCommutativeExpr::print(std::ostream &OS) const { OS << ")"; } -// SCEVUDivs - Only allow the creation of one SCEVUDivExpr for any particular +SCEVHandle SCEVCommutativeExpr:: +replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, + const SCEVHandle &Conc) const { + for (unsigned i = 0, e = getNumOperands(); i != e; ++i) { + SCEVHandle H = getOperand(i)->replaceSymbolicValuesWithConcrete(Sym, Conc); + if (H != getOperand(i)) { + std::vector NewOps; + NewOps.reserve(getNumOperands()); + for (unsigned j = 0; j != i; ++j) + NewOps.push_back(getOperand(j)); + NewOps.push_back(H); + for (++i; i != e; ++i) + NewOps.push_back(getOperand(i)-> + replaceSymbolicValuesWithConcrete(Sym, Conc)); + + if (isa(this)) + return SCEVAddExpr::get(NewOps); + else if (isa(this)) + return SCEVMulExpr::get(NewOps); + else + assert(0 && "Unknown commutative expr!"); + } + } + return this; +} + + +// SCEVSDivs - Only allow the creation of one SCEVSDivExpr for any particular // input. Don't use a SCEVHandle here, or else the object will never be // deleted! -static std::map, SCEVUDivExpr*> SCEVUDivs; +static ManagedStatic, + SCEVSDivExpr*> > SCEVSDivs; -SCEVUDivExpr::~SCEVUDivExpr() { - SCEVUDivs.erase(std::make_pair(LHS, RHS)); +SCEVSDivExpr::~SCEVSDivExpr() { + SCEVSDivs->erase(std::make_pair(LHS, RHS)); } -void SCEVUDivExpr::print(std::ostream &OS) const { - OS << "(" << *LHS << " /u " << *RHS << ")"; +void SCEVSDivExpr::print(std::ostream &OS) const { + OS << "(" << *LHS << " /s " << *RHS << ")"; } -const Type *SCEVUDivExpr::getType() const { - const Type *Ty = LHS->getType(); - if (Ty->isSigned()) Ty = Ty->getUnsignedVersion(); - return Ty; +const Type *SCEVSDivExpr::getType() const { + return LHS->getType(); } // SCEVAddRecExprs - Only allow the creation of one SCEVAddRecExpr for any // particular input. Don't use a SCEVHandle here, or else the object will never // be deleted! -static std::map >, - SCEVAddRecExpr*> SCEVAddRecExprs; +static ManagedStatic >, + SCEVAddRecExpr*> > SCEVAddRecExprs; SCEVAddRecExpr::~SCEVAddRecExpr() { - SCEVAddRecExprs.erase(std::make_pair(L, - std::vector(Operands.begin(), - Operands.end()))); + SCEVAddRecExprs->erase(std::make_pair(L, + std::vector(Operands.begin(), + Operands.end()))); +} + +SCEVHandle SCEVAddRecExpr:: +replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, + const SCEVHandle &Conc) const { + for (unsigned i = 0, e = getNumOperands(); i != e; ++i) { + SCEVHandle H = getOperand(i)->replaceSymbolicValuesWithConcrete(Sym, Conc); + if (H != getOperand(i)) { + std::vector NewOps; + NewOps.reserve(getNumOperands()); + for (unsigned j = 0; j != i; ++j) + NewOps.push_back(getOperand(j)); + NewOps.push_back(H); + for (++i; i != e; ++i) + NewOps.push_back(getOperand(i)-> + replaceSymbolicValuesWithConcrete(Sym, Conc)); + + return get(NewOps, L); + } + } + return this; } + bool SCEVAddRecExpr::isLoopInvariant(const Loop *QueryLoop) const { // This recurrence is invariant w.r.t to QueryLoop iff QueryLoop doesn't - // contain L. - return !QueryLoop->contains(L->getHeader()); + // contain L and if the start is invariant. + return !QueryLoop->contains(L->getHeader()) && + getOperand(0)->isLoopInvariant(QueryLoop); } @@ -330,9 +356,9 @@ void SCEVAddRecExpr::print(std::ostream &OS) const { // SCEVUnknowns - Only allow the creation of one SCEVUnknown for any particular // value. Don't use a SCEVHandle here, or else the object will never be // deleted! -static std::map SCEVUnknowns; +static ManagedStatic > SCEVUnknowns; -SCEVUnknown::~SCEVUnknown() { SCEVUnknowns.erase(V); } +SCEVUnknown::~SCEVUnknown() { SCEVUnknowns->erase(V); } bool SCEVUnknown::isLoopInvariant(const Loop *L) const { // All non-instruction values are loop invariant. All instructions are loop @@ -350,6 +376,65 @@ void SCEVUnknown::print(std::ostream &OS) const { WriteAsOperand(OS, V, false); } +//===----------------------------------------------------------------------===// +// SCEV Utilities +//===----------------------------------------------------------------------===// + +namespace { + /// SCEVComplexityCompare - Return true if the complexity of the LHS is less + /// than the complexity of the RHS. This comparator is used to canonicalize + /// expressions. + struct VISIBILITY_HIDDEN SCEVComplexityCompare { + bool operator()(SCEV *LHS, SCEV *RHS) { + return LHS->getSCEVType() < RHS->getSCEVType(); + } + }; +} + +/// GroupByComplexity - Given a list of SCEV objects, order them by their +/// complexity, and group objects of the same complexity together by value. +/// When this routine is finished, we know that any duplicates in the vector are +/// consecutive and that complexity is monotonically increasing. +/// +/// Note that we go take special precautions to ensure that we get determinstic +/// results from this routine. In other words, we don't want the results of +/// this to depend on where the addresses of various SCEV objects happened to +/// land in memory. +/// +static void GroupByComplexity(std::vector &Ops) { + if (Ops.size() < 2) return; // Noop + if (Ops.size() == 2) { + // This is the common case, which also happens to be trivially simple. + // Special case it. + if (Ops[0]->getSCEVType() > Ops[1]->getSCEVType()) + std::swap(Ops[0], Ops[1]); + return; + } + + // Do the rough sort by complexity. + std::sort(Ops.begin(), Ops.end(), SCEVComplexityCompare()); + + // Now that we are sorted by complexity, group elements of the same + // complexity. Note that this is, at worst, N^2, but the vector is likely to + // be extremely short in practice. Note that we take this approach because we + // do not want to depend on the addresses of the objects we are grouping. + for (unsigned i = 0, e = Ops.size(); i != e-2; ++i) { + SCEV *S = Ops[i]; + unsigned Complexity = S->getSCEVType(); + + // If there are any objects of the same complexity and same value as this + // one, group them. + for (unsigned j = i+1; j != e && Ops[j]->getSCEVType() == Complexity; ++j) { + if (Ops[j] == S) { // Found a duplicate. + // Move it to immediately after i'th element. + std::swap(Ops[i+1], Ops[j]); + ++i; // no need to rescan it. + if (i == e-2) return; // Done! + } + } + } +} + //===----------------------------------------------------------------------===// @@ -358,18 +443,14 @@ void SCEVUnknown::print(std::ostream &OS) const { /// getIntegerSCEV - Given an integer or FP type, create a constant for the /// specified signed integer value and return a SCEV for the constant. -static SCEVHandle getIntegerSCEV(int Val, const Type *Ty) { +SCEVHandle SCEVUnknown::getIntegerSCEV(int Val, const Type *Ty) { Constant *C; - if (Val == 0) + if (Val == 0) C = Constant::getNullValue(Ty); else if (Ty->isFloatingPoint()) C = ConstantFP::get(Ty, Val); - else if (Ty->isSigned()) - C = ConstantSInt::get(Ty, Val); - else { - C = ConstantSInt::get(Ty->getSignedVersion(), Val); - C = ConstantExpr::getCast(C, Ty); - } + else + C = ConstantInt::get(Ty, Val); return SCEVUnknown::get(C); } @@ -380,69 +461,51 @@ static SCEVHandle 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->getPrimitiveSize() == Ty->getPrimitiveSize()) + if (SrcTy->getPrimitiveSizeInBits() == Ty->getPrimitiveSizeInBits()) return V; // No conversion - if (SrcTy->getPrimitiveSize() > Ty->getPrimitiveSize()) + if (SrcTy->getPrimitiveSizeInBits() > Ty->getPrimitiveSizeInBits()) return SCEVTruncateExpr::get(V, Ty); return SCEVZeroExtendExpr::get(V, Ty); } /// getNegativeSCEV - Return a SCEV corresponding to -V = -1*V /// -static SCEVHandle getNegativeSCEV(const SCEVHandle &V) { +SCEVHandle SCEV::getNegativeSCEV(const SCEVHandle &V) { if (SCEVConstant *VC = dyn_cast(V)) return SCEVUnknown::get(ConstantExpr::getNeg(VC->getValue())); - - return SCEVMulExpr::get(V, getIntegerSCEV(-1, V->getType())); + + return SCEVMulExpr::get(V, SCEVUnknown::getIntegerSCEV(-1, V->getType())); } /// getMinusSCEV - Return a SCEV corresponding to LHS - RHS. /// -static SCEVHandle getMinusSCEV(const SCEVHandle &LHS, const SCEVHandle &RHS) { +SCEVHandle SCEV::getMinusSCEV(const SCEVHandle &LHS, const SCEVHandle &RHS) { // X - Y --> X + -Y - return SCEVAddExpr::get(LHS, getNegativeSCEV(RHS)); + return SCEVAddExpr::get(LHS, SCEV::getNegativeSCEV(RHS)); } -/// Binomial - Evaluate N!/((N-M)!*M!) . Note that N is often large and M is -/// often very small, so we try to reduce the number of N! terms we need to -/// evaluate by evaluating this as (N!/(N-M)!)/M! -static ConstantInt *Binomial(ConstantInt *N, unsigned M) { - uint64_t NVal = N->getRawValue(); - uint64_t FirstTerm = 1; - for (unsigned i = 0; i != M; ++i) - FirstTerm *= NVal-i; - - unsigned MFactorial = 1; - for (; M; --M) - MFactorial *= M; - - Constant *Result = ConstantUInt::get(Type::ULongTy, FirstTerm/MFactorial); - Result = ConstantExpr::getCast(Result, N->getType()); - assert(isa(Result) && "Cast of integer not folded??"); - return cast(Result); -} - /// PartialFact - Compute V!/(V-NumSteps)! static SCEVHandle PartialFact(SCEVHandle V, unsigned NumSteps) { // Handle this case efficiently, it is common to have constant iteration // counts while computing loop exit values. if (SCEVConstant *SC = dyn_cast(V)) { - uint64_t Val = SC->getValue()->getRawValue(); + uint64_t Val = SC->getValue()->getZExtValue(); uint64_t Result = 1; for (; NumSteps; --NumSteps) Result *= Val-(NumSteps-1); - Constant *Res = ConstantUInt::get(Type::ULongTy, Result); - return SCEVUnknown::get(ConstantExpr::getCast(Res, V->getType())); + Constant *Res = ConstantInt::get(Type::Int64Ty, Result); + return SCEVUnknown::get(ConstantExpr::getTruncOrBitCast(Res, V->getType())); } const Type *Ty = V->getType(); if (NumSteps == 0) - return getIntegerSCEV(1, Ty); - + return SCEVUnknown::getIntegerSCEV(1, Ty); + SCEVHandle Result = V; for (unsigned i = 1; i != NumSteps; ++i) - Result = SCEVMulExpr::get(Result, getMinusSCEV(V, getIntegerSCEV(i, Ty))); + Result = SCEVMulExpr::get(Result, SCEV::getMinusSCEV(V, + SCEVUnknown::getIntegerSCEV(i, Ty))); return Result; } @@ -464,8 +527,8 @@ SCEVHandle SCEVAddRecExpr::evaluateAtIteration(SCEVHandle It) const { for (unsigned i = 1, e = getNumOperands(); i != e; ++i) { SCEVHandle BC = PartialFact(It, i); Divisor *= i; - SCEVHandle Val = SCEVUDivExpr::get(SCEVMulExpr::get(BC, getOperand(i)), - getIntegerSCEV(Divisor, Ty)); + SCEVHandle Val = SCEVSDivExpr::get(SCEVMulExpr::get(BC, getOperand(i)), + SCEVUnknown::getIntegerSCEV(Divisor,Ty)); Result = SCEVAddExpr::get(Result, Val); } return Result; @@ -478,7 +541,8 @@ SCEVHandle SCEVAddRecExpr::evaluateAtIteration(SCEVHandle It) const { SCEVHandle SCEVTruncateExpr::get(const SCEVHandle &Op, const Type *Ty) { if (SCEVConstant *SC = dyn_cast(Op)) - return SCEVUnknown::get(ConstantExpr::getCast(SC->getValue(), Ty)); + return SCEVUnknown::get( + ConstantExpr::getTrunc(SC->getValue(), Ty)); // If the input value is a chrec scev made out of constants, truncate // all of the constants. @@ -494,21 +558,22 @@ SCEVHandle SCEVTruncateExpr::get(const SCEVHandle &Op, const Type *Ty) { return SCEVAddRecExpr::get(Operands, AddRec->getLoop()); } - SCEVTruncateExpr *&Result = SCEVTruncates[std::make_pair(Op, Ty)]; + SCEVTruncateExpr *&Result = (*SCEVTruncates)[std::make_pair(Op, Ty)]; if (Result == 0) Result = new SCEVTruncateExpr(Op, Ty); return Result; } SCEVHandle SCEVZeroExtendExpr::get(const SCEVHandle &Op, const Type *Ty) { if (SCEVConstant *SC = dyn_cast(Op)) - return SCEVUnknown::get(ConstantExpr::getCast(SC->getValue(), Ty)); + return SCEVUnknown::get( + ConstantExpr::getZExt(SC->getValue(), Ty)); // 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 // operands (often constants). This would allow analysis of something like // this: for (unsigned char X = 0; X < 100; ++X) { int Y = X; } - SCEVZeroExtendExpr *&Result = SCEVZeroExtends[std::make_pair(Op, Ty)]; + SCEVZeroExtendExpr *&Result = (*SCEVZeroExtends)[std::make_pair(Op, Ty)]; if (Result == 0) Result = new SCEVZeroExtendExpr(Op, Ty); return Result; } @@ -519,7 +584,7 @@ SCEVHandle SCEVAddExpr::get(std::vector &Ops) { if (Ops.size() == 1) return Ops[0]; // Sort by complexity, this groups all similar expression types together. - std::sort(Ops.begin(), Ops.end(), SCEVComplexityCompare()); + GroupByComplexity(Ops); // If there are any constants, fold them together. unsigned Idx = 0; @@ -533,6 +598,7 @@ SCEVHandle SCEVAddExpr::get(std::vector &Ops) { Ops[0] = SCEVConstant::get(CI); Ops.erase(Ops.begin()+1); // Erase the folded element if (Ops.size() == 1) return Ops[0]; + LHSC = cast(Ops[0]); } else { // If we couldn't fold the expression, move to the next constant. Note // that this is impossible to happen in practice because we always @@ -549,7 +615,7 @@ SCEVHandle SCEVAddExpr::get(std::vector &Ops) { } if (Ops.size() == 1) return Ops[0]; - + // Okay, check to see if the same value occurs in the operand list twice. If // so, merge them together into an multiply expression. Since we sorted the // list, these values are required to be adjacent. @@ -558,7 +624,7 @@ SCEVHandle SCEVAddExpr::get(std::vector &Ops) { if (Ops[i] == Ops[i+1]) { // X + Y + Y --> X + Y*2 // Found a match, merge the two values into a multiply, and add any // remaining values to the result. - SCEVHandle Two = getIntegerSCEV(2, Ty); + SCEVHandle Two = SCEVUnknown::getIntegerSCEV(2, Ty); SCEVHandle Mul = SCEVMulExpr::get(Ops[i], Two); if (Ops.size() == 2) return Mul; @@ -598,8 +664,7 @@ SCEVHandle SCEVAddExpr::get(std::vector &Ops) { for (unsigned MulOp = 0, e = Mul->getNumOperands(); MulOp != e; ++MulOp) { SCEV *MulOpSCEV = Mul->getOperand(MulOp); for (unsigned AddOp = 0, e = Ops.size(); AddOp != e; ++AddOp) - if (MulOpSCEV == Ops[AddOp] && - (Mul->getNumOperands() != 2 || !isa(MulOpSCEV))) { + if (MulOpSCEV == Ops[AddOp] && !isa(MulOpSCEV)) { // Fold W + X + (X * Y * Z) --> W + (X * ((Y*Z)+1)) SCEVHandle InnerMul = Mul->getOperand(MulOp == 0); if (Mul->getNumOperands() != 2) { @@ -609,7 +674,7 @@ SCEVHandle SCEVAddExpr::get(std::vector &Ops) { MulOps.erase(MulOps.begin()+MulOp); InnerMul = SCEVMulExpr::get(MulOps); } - SCEVHandle One = getIntegerSCEV(1, Ty); + SCEVHandle One = SCEVUnknown::getIntegerSCEV(1, Ty); SCEVHandle AddOne = SCEVAddExpr::get(InnerMul, One); SCEVHandle OuterMul = SCEVMulExpr::get(AddOne, Ops[AddOp]); if (Ops.size() == 2) return OuterMul; @@ -623,7 +688,7 @@ SCEVHandle SCEVAddExpr::get(std::vector &Ops) { Ops.push_back(OuterMul); return SCEVAddExpr::get(Ops); } - + // Check this multiply against other multiplies being added together. for (unsigned OtherMulIdx = Idx+1; OtherMulIdx < Ops.size() && isa(Ops[OtherMulIdx]); @@ -736,8 +801,8 @@ SCEVHandle SCEVAddExpr::get(std::vector &Ops) { // Okay, it looks like we really DO need an add expr. Check to see if we // already have one, otherwise create a new one. std::vector SCEVOps(Ops.begin(), Ops.end()); - SCEVCommutativeExpr *&Result = SCEVCommExprs[std::make_pair(scAddExpr, - SCEVOps)]; + SCEVCommutativeExpr *&Result = (*SCEVCommExprs)[std::make_pair(scAddExpr, + SCEVOps)]; if (Result == 0) Result = new SCEVAddExpr(Ops); return Result; } @@ -747,7 +812,7 @@ SCEVHandle SCEVMulExpr::get(std::vector &Ops) { assert(!Ops.empty() && "Cannot get empty mul!"); // Sort by complexity, this groups all similar expression types together. - std::sort(Ops.begin(), Ops.end(), SCEVComplexityCompare()); + GroupByComplexity(Ops); // If there are any constants, fold them together. unsigned Idx = 0; @@ -770,6 +835,7 @@ SCEVHandle SCEVMulExpr::get(std::vector &Ops) { Ops[0] = SCEVConstant::get(CI); Ops.erase(Ops.begin()+1); // Erase the folded element if (Ops.size() == 1) return Ops[0]; + LHSC = cast(Ops[0]); } else { // If we couldn't fold the expression, move to the next constant. Note // that this is impossible to happen in practice because we always @@ -794,7 +860,7 @@ SCEVHandle SCEVMulExpr::get(std::vector &Ops) { if (Ops.size() == 1) return Ops[0]; - + // If there are mul operands inline them all into this expression. if (Idx < Ops.size()) { bool DeletedMul = false; @@ -898,35 +964,31 @@ SCEVHandle SCEVMulExpr::get(std::vector &Ops) { // Okay, it looks like we really DO need an mul expr. Check to see if we // already have one, otherwise create a new one. std::vector SCEVOps(Ops.begin(), Ops.end()); - SCEVCommutativeExpr *&Result = SCEVCommExprs[std::make_pair(scMulExpr, - SCEVOps)]; - if (Result == 0) Result = new SCEVMulExpr(Ops); + SCEVCommutativeExpr *&Result = (*SCEVCommExprs)[std::make_pair(scMulExpr, + SCEVOps)]; + if (Result == 0) + Result = new SCEVMulExpr(Ops); return Result; } -SCEVHandle SCEVUDivExpr::get(const SCEVHandle &LHS, const SCEVHandle &RHS) { +SCEVHandle SCEVSDivExpr::get(const SCEVHandle &LHS, const SCEVHandle &RHS) { if (SCEVConstant *RHSC = dyn_cast(RHS)) { if (RHSC->getValue()->equalsInt(1)) - return LHS; // X /u 1 --> x + return LHS; // X sdiv 1 --> x if (RHSC->getValue()->isAllOnesValue()) - return getNegativeSCEV(LHS); // X /u -1 --> -x + return SCEV::getNegativeSCEV(LHS); // X sdiv -1 --> -x if (SCEVConstant *LHSC = dyn_cast(LHS)) { Constant *LHSCV = LHSC->getValue(); Constant *RHSCV = RHSC->getValue(); - if (LHSCV->getType()->isSigned()) - LHSCV = ConstantExpr::getCast(LHSCV, - LHSCV->getType()->getUnsignedVersion()); - if (RHSCV->getType()->isSigned()) - RHSCV = ConstantExpr::getCast(RHSCV, LHSCV->getType()); - return SCEVUnknown::get(ConstantExpr::getDiv(LHSCV, RHSCV)); + return SCEVUnknown::get(ConstantExpr::getSDiv(LHSCV, RHSCV)); } } // FIXME: implement folding of (X*4)/4 when we know X*4 doesn't overflow. - SCEVUDivExpr *&Result = SCEVUDivs[std::make_pair(LHS, RHS)]; - if (Result == 0) Result = new SCEVUDivExpr(LHS, RHS); + SCEVSDivExpr *&Result = (*SCEVSDivs)[std::make_pair(LHS, RHS)]; + if (Result == 0) Result = new SCEVSDivExpr(LHS, RHS); return Result; } @@ -961,8 +1023,8 @@ SCEVHandle SCEVAddRecExpr::get(std::vector &Operands, } SCEVAddRecExpr *&Result = - SCEVAddRecExprs[std::make_pair(L, std::vector(Operands.begin(), - Operands.end()))]; + (*SCEVAddRecExprs)[std::make_pair(L, std::vector(Operands.begin(), + Operands.end()))]; if (Result == 0) Result = new SCEVAddRecExpr(Operands, L); return Result; } @@ -970,143 +1032,12 @@ SCEVHandle SCEVAddRecExpr::get(std::vector &Operands, SCEVHandle SCEVUnknown::get(Value *V) { if (ConstantInt *CI = dyn_cast(V)) return SCEVConstant::get(CI); - SCEVUnknown *&Result = SCEVUnknowns[V]; + SCEVUnknown *&Result = (*SCEVUnknowns)[V]; if (Result == 0) Result = new SCEVUnknown(V); return Result; } -//===----------------------------------------------------------------------===// -// Non-trivial closed-form SCEV Expanders -//===----------------------------------------------------------------------===// - -Value *SCEVTruncateExpr::expandCodeFor(ScalarEvolutionRewriter &SER, - Instruction *InsertPt) { - Value *V = SER.ExpandCodeFor(getOperand(), InsertPt); - return new CastInst(V, getType(), "tmp.", InsertPt); -} - -Value *SCEVZeroExtendExpr::expandCodeFor(ScalarEvolutionRewriter &SER, - Instruction *InsertPt) { - Value *V = SER.ExpandCodeFor(getOperand(), InsertPt, - getOperand()->getType()->getUnsignedVersion()); - return new CastInst(V, getType(), "tmp.", InsertPt); -} - -Value *SCEVAddExpr::expandCodeFor(ScalarEvolutionRewriter &SER, - Instruction *InsertPt) { - const Type *Ty = getType(); - Value *V = SER.ExpandCodeFor(getOperand(getNumOperands()-1), InsertPt, Ty); - - // Emit a bunch of add instructions - for (int i = getNumOperands()-2; i >= 0; --i) - V = BinaryOperator::create(Instruction::Add, V, - SER.ExpandCodeFor(getOperand(i), InsertPt, Ty), - "tmp.", InsertPt); - return V; -} - -Value *SCEVMulExpr::expandCodeFor(ScalarEvolutionRewriter &SER, - Instruction *InsertPt) { - const Type *Ty = getType(); - int FirstOp = 0; // Set if we should emit a subtract. - if (SCEVConstant *SC = dyn_cast(getOperand(0))) - if (SC->getValue()->isAllOnesValue()) - FirstOp = 1; - - int i = getNumOperands()-2; - Value *V = SER.ExpandCodeFor(getOperand(i+1), InsertPt, Ty); - - // Emit a bunch of multiply instructions - for (; i >= FirstOp; --i) - V = BinaryOperator::create(Instruction::Mul, V, - SER.ExpandCodeFor(getOperand(i), InsertPt, Ty), - "tmp.", InsertPt); - // -1 * ... ---> 0 - ... - if (FirstOp == 1) - V = BinaryOperator::create(Instruction::Sub, Constant::getNullValue(Ty), V, - "tmp.", InsertPt); - return V; -} - -Value *SCEVUDivExpr::expandCodeFor(ScalarEvolutionRewriter &SER, - Instruction *InsertPt) { - const Type *Ty = getType(); - Value *LHS = SER.ExpandCodeFor(getLHS(), InsertPt, Ty); - Value *RHS = SER.ExpandCodeFor(getRHS(), InsertPt, Ty); - return BinaryOperator::create(Instruction::Div, LHS, RHS, "tmp.", InsertPt); -} - -Value *SCEVAddRecExpr::expandCodeFor(ScalarEvolutionRewriter &SER, - Instruction *InsertPt) { - const Type *Ty = getType(); - // We cannot yet do fp recurrences, e.g. the xform of {X,+,F} --> X+{0,+,F} - assert(Ty->isIntegral() && "Cannot expand fp recurrences yet!"); - - // {X,+,F} --> X + {0,+,F} - if (!isa(getStart()) || - !cast(getStart())->getValue()->isNullValue()) { - Value *Start = SER.ExpandCodeFor(getStart(), InsertPt, Ty); - std::vector NewOps(op_begin(), op_end()); - NewOps[0] = getIntegerSCEV(0, getType()); - Value *Rest = SER.ExpandCodeFor(SCEVAddRecExpr::get(NewOps, getLoop()), - InsertPt, getType()); - - // FIXME: look for an existing add to use. - return BinaryOperator::create(Instruction::Add, Rest, Start, "tmp.", - InsertPt); - } - - // {0,+,1} --> Insert a canonical induction variable into the loop! - if (getNumOperands() == 2 && getOperand(1) == getIntegerSCEV(1, getType())) { - // Create and insert the PHI node for the induction variable in the - // specified loop. - BasicBlock *Header = getLoop()->getHeader(); - PHINode *PN = new PHINode(Ty, "indvar", Header->begin()); - PN->addIncoming(Constant::getNullValue(Ty), L->getLoopPreheader()); - - pred_iterator HPI = pred_begin(Header); - assert(HPI != pred_end(Header) && "Loop with zero preds???"); - if (!getLoop()->contains(*HPI)) ++HPI; - assert(HPI != pred_end(Header) && getLoop()->contains(*HPI) && - "No backedge in loop?"); - - // Insert a unit add instruction right before the terminator corresponding - // to the back-edge. - Constant *One = Ty->isFloatingPoint() ? (Constant*)ConstantFP::get(Ty, 1.0) - : (Constant*)ConstantInt::get(Ty, 1); - Instruction *Add = BinaryOperator::create(Instruction::Add, PN, One, - "indvar.next", - (*HPI)->getTerminator()); - - pred_iterator PI = pred_begin(Header); - if (*PI == L->getLoopPreheader()) - ++PI; - PN->addIncoming(Add, *PI); - return PN; - } - - // Get the canonical induction variable I for this loop. - Value *I = SER.GetOrInsertCanonicalInductionVariable(getLoop(), Ty); - - if (getNumOperands() == 2) { // {0,+,F} --> i*F - Value *F = SER.ExpandCodeFor(getOperand(1), InsertPt, Ty); - return BinaryOperator::create(Instruction::Mul, I, F, "tmp.", InsertPt); - } - - // If this is a chain of recurrences, turn it into a closed form, using the - // folders, then expandCodeFor the closed form. This allows the folders to - // simplify the expression without having to build a bunch of special code - // into this folder. - SCEVHandle IH = SCEVUnknown::get(I); // Get I as a "symbolic" SCEV. - - SCEVHandle V = evaluateAtIteration(IH); - //std::cerr << "Evaluated: " << *this << "\n to: " << *V << "\n"; - - return SER.ExpandCodeFor(V, InsertPt, Ty); -} - - //===----------------------------------------------------------------------===// // ScalarEvolutionsImpl Definition and Implementation //===----------------------------------------------------------------------===// @@ -1115,7 +1046,7 @@ Value *SCEVAddRecExpr::expandCodeFor(ScalarEvolutionRewriter &SER, /// evolution code. /// namespace { - struct ScalarEvolutionsImpl { + struct VISIBILITY_HIDDEN ScalarEvolutionsImpl { /// F - The function we are analyzing. /// Function &F; @@ -1142,7 +1073,7 @@ namespace { /// properties. An instruction maps to null if we are unable to compute its /// exit value. std::map ConstantEvolutionLoopExitValue; - + public: ScalarEvolutionsImpl(Function &f, LoopInfo &li) : F(f), LI(li), UnknownValue(new SCEVCouldNotCompute()) {} @@ -1151,6 +1082,20 @@ namespace { /// expression and create a new one. SCEVHandle getSCEV(Value *V); + /// hasSCEV - Return true if the SCEV for this value has already been + /// computed. + bool hasSCEV(Value *V) const { + return Scalars.count(V); + } + + /// setSCEV - Insert the specified SCEV into the map of current SCEVs for + /// the specified value. + void setSCEV(Value *V, const SCEVHandle &H) { + bool isNew = Scalars.insert(std::make_pair(V, H)).second; + assert(isNew && "This entry already existed!"); + } + + /// getSCEVAtScope - Compute the value of the specified expression within /// the indicated loop (which may be null to indicate in no loop). If the /// expression cannot be evaluated, return UnknownValue itself. @@ -1175,18 +1120,30 @@ namespace { /// createSCEV - We know that there is no SCEV for the specified value. /// Analyze the expression. SCEVHandle createSCEV(Value *V); - SCEVHandle createNodeForCast(CastInst *CI); /// createNodeForPHI - Provide the special handling we need to analyze PHI /// SCEVs. SCEVHandle createNodeForPHI(PHINode *PN); - void UpdatePHIUserScalarEntries(Instruction *I, PHINode *PN, - std::set &UpdatedInsts); + + /// ReplaceSymbolicValueWithConcrete - This looks up the computed SCEV value + /// for the specified instruction and replaces any references to the + /// symbolic value SymName with the specified value. This is used during + /// PHI resolution. + void ReplaceSymbolicValueWithConcrete(Instruction *I, + const SCEVHandle &SymName, + const SCEVHandle &NewVal); /// ComputeIterationCount - Compute the number of times the specified loop /// will iterate. SCEVHandle ComputeIterationCount(const Loop *L); + /// ComputeLoadConstantCompareIterationCount - Given an exit condition of + /// 'setcc load X, cst', try to se if we can compute the trip count. + SCEVHandle ComputeLoadConstantCompareIterationCount(LoadInst *LI, + Constant *RHS, + const Loop *L, + ICmpInst::Predicate p); + /// ComputeIterationCountExhaustively - If the trip is known to execute a /// constant number of times (the condition evolves only from constants), /// try to evaluate a few iterations of the loop until we get the exit @@ -1197,14 +1154,19 @@ namespace { /// HowFarToZero - Return the number of times a backedge comparing the /// specified value to zero will execute. If not computable, return - /// UnknownValue + /// UnknownValue. SCEVHandle HowFarToZero(SCEV *V, const Loop *L); /// HowFarToNonZero - Return the number of times a backedge checking the /// specified value for nonzero will execute. If not computable, return - /// UnknownValue + /// UnknownValue. SCEVHandle HowFarToNonZero(SCEV *V, const Loop *L); + /// HowManyLessThans - Return the number of times a backedge containing the + /// specified less-than comparison will execute. If not computable, return + /// UnknownValue. + SCEVHandle HowManyLessThans(SCEV *LHS, SCEV *RHS, const Loop *L); + /// getConstantEvolutionLoopExitValue - If we know that the specified Phi is /// in the header of its containing loop, we know the loop executes a /// constant number of times, and the PHI node is just a recurrence @@ -1240,26 +1202,27 @@ SCEVHandle ScalarEvolutionsImpl::getSCEV(Value *V) { return S; } - -/// UpdatePHIUserScalarEntries - After PHI node analysis, we have a bunch of -/// entries in the scalar map that refer to the "symbolic" PHI value instead of -/// the recurrence value. After we resolve the PHI we must loop over all of the -/// using instructions that have scalar map entries and update them. -void ScalarEvolutionsImpl::UpdatePHIUserScalarEntries(Instruction *I, - PHINode *PN, - std::set &UpdatedInsts) { +/// ReplaceSymbolicValueWithConcrete - This looks up the computed SCEV value for +/// the specified instruction and replaces any references to the symbolic value +/// SymName with the specified value. This is used during PHI resolution. +void ScalarEvolutionsImpl:: +ReplaceSymbolicValueWithConcrete(Instruction *I, const SCEVHandle &SymName, + const SCEVHandle &NewVal) { std::map::iterator SI = Scalars.find(I); - if (SI == Scalars.end()) return; // This scalar wasn't previous processed. - if (UpdatedInsts.insert(I).second) { - Scalars.erase(SI); // Remove the old entry - getSCEV(I); // Calculate the new entry - - for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); - UI != E; ++UI) - UpdatePHIUserScalarEntries(cast(*UI), PN, UpdatedInsts); - } -} + if (SI == Scalars.end()) return; + + SCEVHandle NV = + SI->second->replaceSymbolicValuesWithConcrete(SymName, NewVal); + if (NV == SI->second) return; // No change. + SI->second = NV; // Update the scalars map! + + // Any instruction values that use this instruction might also need to be + // updated! + for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); + UI != E; ++UI) + ReplaceSymbolicValueWithConcrete(cast(*UI), SymName, NewVal); +} /// createNodeForPHI - PHI nodes have two cases. Either the PHI node exists in /// a loop header, making it a potential recurrence, or it doesn't. @@ -1272,7 +1235,7 @@ SCEVHandle ScalarEvolutionsImpl::createNodeForPHI(PHINode *PN) { // from outside the loop, and one from inside. unsigned IncomingEdge = L->contains(PN->getIncomingBlock(0)); unsigned BackEdge = IncomingEdge^1; - + // While we are analyzing this PHI node, handle its value symbolically. SCEVHandle SymbolicName = SCEVUnknown::get(PN); assert(Scalars.find(PN) == Scalars.end() && @@ -1320,13 +1283,32 @@ SCEVHandle ScalarEvolutionsImpl::createNodeForPHI(PHINode *PN) { // entries for the scalars that use the PHI (except for the PHI // itself) to use the new analyzed value instead of the "symbolic" // value. - Scalars.find(PN)->second = PHISCEV; // Update the PHI value - std::set UpdatedInsts; - UpdatedInsts.insert(PN); - for (Value::use_iterator UI = PN->use_begin(), E = PN->use_end(); - UI != E; ++UI) - UpdatePHIUserScalarEntries(cast(*UI), PN, - UpdatedInsts); + ReplaceSymbolicValueWithConcrete(PN, SymbolicName, PHISCEV); + return PHISCEV; + } + } + } else if (SCEVAddRecExpr *AddRec = dyn_cast(BEValue)) { + // Otherwise, this could be a loop like this: + // i = 0; for (j = 1; ..; ++j) { .... i = j; } + // In this case, j = {1,+,1} and BEValue is j. + // Because the other in-value of i (0) fits the evolution of BEValue + // i really is an addrec evolution. + if (AddRec->getLoop() == L && AddRec->isAffine()) { + SCEVHandle StartVal = getSCEV(PN->getIncomingValue(IncomingEdge)); + + // If StartVal = j.start - j.stride, we can use StartVal as the + // initial step of the addrec evolution. + if (StartVal == SCEV::getMinusSCEV(AddRec->getOperand(0), + AddRec->getOperand(1))) { + SCEVHandle PHISCEV = + SCEVAddRecExpr::get(StartVal, AddRec->getOperand(1), L); + + // Okay, for the entire analysis of this edge we assumed the PHI + // to be symbolic. We now need to go back and update all of the + // entries for the scalars that use the PHI (except for the PHI + // itself) to use the new analyzed value instead of the "symbolic" + // value. + ReplaceSymbolicValueWithConcrete(PN, SymbolicName, PHISCEV); return PHISCEV; } } @@ -1334,41 +1316,58 @@ SCEVHandle ScalarEvolutionsImpl::createNodeForPHI(PHINode *PN) { return SymbolicName; } - + // If it's not a loop phi, we can't handle it yet. return SCEVUnknown::get(PN); } -/// createNodeForCast - Handle the various forms of casts that we support. -/// -SCEVHandle ScalarEvolutionsImpl::createNodeForCast(CastInst *CI) { - const Type *SrcTy = CI->getOperand(0)->getType(); - const Type *DestTy = CI->getType(); - - // If this is a noop cast (ie, conversion from int to uint), ignore it. - if (SrcTy->isLosslesslyConvertibleTo(DestTy)) - return getSCEV(CI->getOperand(0)); - - if (SrcTy->isInteger() && DestTy->isInteger()) { - // Otherwise, if this is a truncating integer cast, we can represent this - // cast. - if (SrcTy->getPrimitiveSize() > DestTy->getPrimitiveSize()) - return SCEVTruncateExpr::get(getSCEV(CI->getOperand(0)), - CI->getType()->getUnsignedVersion()); - if (SrcTy->isUnsigned() && - SrcTy->getPrimitiveSize() > DestTy->getPrimitiveSize()) - return SCEVZeroExtendExpr::get(getSCEV(CI->getOperand(0)), - CI->getType()->getUnsignedVersion()); +/// GetConstantFactor - Determine the largest constant factor that S has. For +/// example, turn {4,+,8} -> 4. (S umod result) should always equal zero. +static uint64_t GetConstantFactor(SCEVHandle S) { + if (SCEVConstant *C = dyn_cast(S)) { + if (uint64_t V = C->getValue()->getZExtValue()) + return V; + else // Zero is a multiple of everything. + return 1ULL << (S->getType()->getPrimitiveSizeInBits()-1); } - // If this is an sign or zero extending cast and we can prove that the value - // will never overflow, we could do similar transformations. + if (SCEVTruncateExpr *T = dyn_cast(S)) + return GetConstantFactor(T->getOperand()) & + cast(T->getType())->getBitMask(); + if (SCEVZeroExtendExpr *E = dyn_cast(S)) + return GetConstantFactor(E->getOperand()); + + if (SCEVAddExpr *A = dyn_cast(S)) { + // The result is the min of all operands. + uint64_t Res = GetConstantFactor(A->getOperand(0)); + for (unsigned i = 1, e = A->getNumOperands(); i != e && Res > 1; ++i) + Res = std::min(Res, GetConstantFactor(A->getOperand(i))); + return Res; + } - // Otherwise, we can't handle this cast! - return SCEVUnknown::get(CI); + if (SCEVMulExpr *M = dyn_cast(S)) { + // The result is the product of all the operands. + uint64_t Res = GetConstantFactor(M->getOperand(0)); + for (unsigned i = 1, e = M->getNumOperands(); i != e; ++i) + Res *= GetConstantFactor(M->getOperand(i)); + return Res; + } + + if (SCEVAddRecExpr *A = dyn_cast(S)) { + // For now, we just handle linear expressions. + if (A->getNumOperands() == 2) { + // We want the GCD between the start and the stride value. + uint64_t Start = GetConstantFactor(A->getOperand(0)); + if (Start == 1) return 1; + uint64_t Stride = GetConstantFactor(A->getOperand(1)); + return GreatestCommonDivisor64(Start, Stride); + } + } + + // SCEVSDivExpr, SCEVUnknown. + return 1; } - /// createSCEV - We know that there is no SCEV for the specified value. /// Analyze the expression. /// @@ -1381,15 +1380,30 @@ SCEVHandle ScalarEvolutionsImpl::createSCEV(Value *V) { case Instruction::Mul: return SCEVMulExpr::get(getSCEV(I->getOperand(0)), getSCEV(I->getOperand(1))); - case Instruction::Div: - if (V->getType()->isInteger() && V->getType()->isUnsigned()) - return SCEVUDivExpr::get(getSCEV(I->getOperand(0)), - getSCEV(I->getOperand(1))); + case Instruction::SDiv: + return SCEVSDivExpr::get(getSCEV(I->getOperand(0)), + getSCEV(I->getOperand(1))); break; case Instruction::Sub: - return getMinusSCEV(getSCEV(I->getOperand(0)), getSCEV(I->getOperand(1))); - + return SCEV::getMinusSCEV(getSCEV(I->getOperand(0)), + getSCEV(I->getOperand(1))); + case Instruction::Or: + // If the RHS of the Or is a constant, we may have something like: + // X*4+1 which got turned into X*4|1. Handle this as an add so loop + // optimizations will transparently handle this case. + if (ConstantInt *CI = dyn_cast(I->getOperand(1))) { + SCEVHandle LHS = getSCEV(I->getOperand(0)); + uint64_t CommonFact = GetConstantFactor(LHS); + assert(CommonFact && "Common factor should at least be 1!"); + if (CommonFact > CI->getZExtValue()) { + // If the LHS is a multiple that is larger than the RHS, use +. + return SCEVAddExpr::get(LHS, + getSCEV(I->getOperand(1))); + } + } + break; + case Instruction::Shl: // Turn shift left of a constant amount into a multiply. if (ConstantInt *SA = dyn_cast(I->getOperand(1))) { @@ -1399,17 +1413,18 @@ SCEVHandle ScalarEvolutionsImpl::createSCEV(Value *V) { } break; - case Instruction::Shr: - if (ConstantUInt *SA = dyn_cast(I->getOperand(1))) - if (V->getType()->isUnsigned()) { - Constant *X = ConstantInt::get(V->getType(), 1); - X = ConstantExpr::getShl(X, SA); - return SCEVUDivExpr::get(getSCEV(I->getOperand(0)), getSCEV(X)); - } - break; + case Instruction::Trunc: + return SCEVTruncateExpr::get(getSCEV(I->getOperand(0)), I->getType()); - case Instruction::Cast: - return createNodeForCast(cast(I)); + case Instruction::ZExt: + return SCEVZeroExtendExpr::get(getSCEV(I->getOperand(0)), I->getType()); + + case Instruction::BitCast: + // BitCasts are no-op casts so we just eliminate the cast. + if (I->getType()->isInteger() && + I->getOperand(0)->getType()->isInteger()) + return getSCEV(I->getOperand(0)); + break; case Instruction::PHI: return createNodeForPHI(cast(I)); @@ -1475,15 +1490,49 @@ SCEVHandle ScalarEvolutionsImpl::ComputeIterationCount(const Loop *L) { // exit. // // FIXME: we should be able to handle switch instructions (with a single exit) - // FIXME: We should handle cast of int to bool as well BranchInst *ExitBr = dyn_cast(ExitingBlock->getTerminator()); if (ExitBr == 0) return UnknownValue; assert(ExitBr->isConditional() && "If unconditional, it can't be in loop!"); - SetCondInst *ExitCond = dyn_cast(ExitBr->getCondition()); - if (ExitCond == 0) // Not a setcc + + // At this point, we know we have a conditional branch that determines whether + // the loop is exited. However, we don't know if the branch is executed each + // time through the loop. If not, then the execution count of the branch will + // not be equal to the trip count of the loop. + // + // Currently we check for this by checking to see if the Exit branch goes to + // the loop header. If so, we know it will always execute the same number of + // times as the loop. We also handle the case where the exit block *is* the + // loop header. This is common for un-rotated loops. More extensive analysis + // could be done to handle more cases here. + if (ExitBr->getSuccessor(0) != L->getHeader() && + ExitBr->getSuccessor(1) != L->getHeader() && + ExitBr->getParent() != L->getHeader()) + return UnknownValue; + + ICmpInst *ExitCond = dyn_cast(ExitBr->getCondition()); + + // If its not an integer comparison then compute it the hard way. + // Note that ICmpInst deals with pointer comparisons too so we must check + // the type of the operand. + if (ExitCond == 0 || isa(ExitCond->getOperand(0)->getType())) return ComputeIterationCountExhaustively(L, ExitBr->getCondition(), ExitBr->getSuccessor(0) == ExitBlock); + // If the condition was exit on true, convert the condition to exit on false + ICmpInst::Predicate Cond; + if (ExitBr->getSuccessor(1) == ExitBlock) + Cond = ExitCond->getPredicate(); + else + Cond = ExitCond->getInversePredicate(); + + // Handle common loops like: for (X = "string"; *X; ++X) + if (LoadInst *LI = dyn_cast(ExitCond->getOperand(0))) + if (Constant *RHS = dyn_cast(ExitCond->getOperand(1))) { + SCEVHandle ItCnt = + ComputeLoadConstantCompareIterationCount(LI, RHS, L, Cond); + if (!isa(ItCnt)) return ItCnt; + } + SCEVHandle LHS = getSCEV(ExitCond->getOperand(0)); SCEVHandle RHS = getSCEV(ExitCond->getOperand(1)); @@ -1493,19 +1542,12 @@ SCEVHandle ScalarEvolutionsImpl::ComputeIterationCount(const Loop *L) { Tmp = getSCEVAtScope(RHS, L); if (!isa(Tmp)) RHS = Tmp; - // If the condition was exit on true, convert the condition to exit on false. - Instruction::BinaryOps Cond; - if (ExitBr->getSuccessor(1) == ExitBlock) - Cond = ExitCond->getOpcode(); - else - Cond = ExitCond->getInverseCondition(); - - // At this point, we would like to compute how many iterations of the loop the - // predicate will return true for these inputs. + // At this point, we would like to compute how many iterations of the + // loop the predicate will return true for these inputs. if (isa(LHS) && !isa(RHS)) { // If there is a constant, force it into the RHS. std::swap(LHS, RHS); - Cond = SetCondInst::getSwappedCondition(Cond); + Cond = ICmpInst::getSwappedPredicate(Cond); } // FIXME: think about handling pointer comparisons! i.e.: @@ -1521,96 +1563,189 @@ SCEVHandle ScalarEvolutionsImpl::ComputeIterationCount(const Loop *L) { // comparison. ConstantInt *CompVal = RHSC->getValue(); const Type *RealTy = ExitCond->getOperand(0)->getType(); - CompVal = dyn_cast(ConstantExpr::getCast(CompVal, RealTy)); + CompVal = dyn_cast( + ConstantExpr::getBitCast(CompVal, RealTy)); if (CompVal) { // Form the constant range. ConstantRange CompRange(Cond, CompVal); - - // Now that we have it, if it's signed, convert it to an unsigned - // range. - if (CompRange.getLower()->getType()->isSigned()) { - const Type *NewTy = RHSC->getValue()->getType(); - Constant *NewL = ConstantExpr::getCast(CompRange.getLower(), NewTy); - Constant *NewU = ConstantExpr::getCast(CompRange.getUpper(), NewTy); - CompRange = ConstantRange(NewL, NewU); - } - - SCEVHandle Ret = AddRec->getNumIterationsInRange(CompRange); + + SCEVHandle Ret = AddRec->getNumIterationsInRange(CompRange, + false /*Always treat as unsigned range*/); if (!isa(Ret)) return Ret; } } - + switch (Cond) { - case Instruction::SetNE: // while (X != Y) + case ICmpInst::ICMP_NE: { // while (X != Y) // Convert to: while (X-Y != 0) - if (LHS->getType()->isInteger()) { - SCEVHandle TC = HowFarToZero(getMinusSCEV(LHS, RHS), L); - if (!isa(TC)) return TC; - } + SCEVHandle TC = HowFarToZero(SCEV::getMinusSCEV(LHS, RHS), L); + if (!isa(TC)) return TC; break; - case Instruction::SetEQ: + } + case ICmpInst::ICMP_EQ: { // Convert to: while (X-Y == 0) // while (X == Y) - if (LHS->getType()->isInteger()) { - SCEVHandle TC = HowFarToNonZero(getMinusSCEV(LHS, RHS), L); - if (!isa(TC)) return TC; - } + SCEVHandle TC = HowFarToNonZero(SCEV::getMinusSCEV(LHS, RHS), L); + if (!isa(TC)) return TC; break; + } + case ICmpInst::ICMP_SLT: { + SCEVHandle TC = HowManyLessThans(LHS, RHS, L); + if (!isa(TC)) return TC; + break; + } + case ICmpInst::ICMP_SGT: { + SCEVHandle TC = HowManyLessThans(RHS, LHS, L); + if (!isa(TC)) return TC; + break; + } default: #if 0 - std::cerr << "ComputeIterationCount "; + cerr << "ComputeIterationCount "; if (ExitCond->getOperand(0)->getType()->isUnsigned()) - std::cerr << "[unsigned] "; - std::cerr << *LHS << " " - << Instruction::getOpcodeName(Cond) << " " << *RHS << "\n"; + cerr << "[unsigned] "; + cerr << *LHS << " " + << Instruction::getOpcodeName(Instruction::ICmp) + << " " << *RHS << "\n"; #endif break; } - return ComputeIterationCountExhaustively(L, ExitCond, - ExitBr->getSuccessor(0) == ExitBlock); + ExitBr->getSuccessor(0) == ExitBlock); +} + +static ConstantInt * +EvaluateConstantChrecAtConstant(const SCEVAddRecExpr *AddRec, Constant *C) { + SCEVHandle InVal = SCEVConstant::get(cast(C)); + SCEVHandle Val = AddRec->evaluateAtIteration(InVal); + assert(isa(Val) && + "Evaluation of SCEV at constant didn't fold correctly?"); + return cast(Val)->getValue(); } +/// GetAddressedElementFromGlobal - Given a global variable with an initializer +/// and a GEP expression (missing the pointer index) indexing into it, return +/// the addressed element of the initializer or null if the index expression is +/// invalid. +static Constant * +GetAddressedElementFromGlobal(GlobalVariable *GV, + const std::vector &Indices) { + Constant *Init = GV->getInitializer(); + for (unsigned i = 0, e = Indices.size(); i != e; ++i) { + uint64_t Idx = Indices[i]->getZExtValue(); + if (ConstantStruct *CS = dyn_cast(Init)) { + assert(Idx < CS->getNumOperands() && "Bad struct index!"); + Init = cast(CS->getOperand(Idx)); + } else if (ConstantArray *CA = dyn_cast(Init)) { + if (Idx >= CA->getNumOperands()) return 0; // Bogus program + Init = cast(CA->getOperand(Idx)); + } else if (isa(Init)) { + if (const StructType *STy = dyn_cast(Init->getType())) { + assert(Idx < STy->getNumElements() && "Bad struct index!"); + Init = Constant::getNullValue(STy->getElementType(Idx)); + } else if (const ArrayType *ATy = dyn_cast(Init->getType())) { + if (Idx >= ATy->getNumElements()) return 0; // Bogus program + Init = Constant::getNullValue(ATy->getElementType()); + } else { + assert(0 && "Unknown constant aggregate type!"); + } + return 0; + } else { + return 0; // Unknown initializer type + } + } + return Init; +} + +/// ComputeLoadConstantCompareIterationCount - Given an exit condition of +/// 'setcc load X, cst', try to se if we can compute the trip count. +SCEVHandle ScalarEvolutionsImpl:: +ComputeLoadConstantCompareIterationCount(LoadInst *LI, Constant *RHS, + const Loop *L, + ICmpInst::Predicate predicate) { + if (LI->isVolatile()) return UnknownValue; + + // Check to see if the loaded pointer is a getelementptr of a global. + GetElementPtrInst *GEP = dyn_cast(LI->getOperand(0)); + if (!GEP) return UnknownValue; + + // Make sure that it is really a constant global we are gepping, with an + // initializer, and make sure the first IDX is really 0. + GlobalVariable *GV = dyn_cast(GEP->getOperand(0)); + if (!GV || !GV->isConstant() || !GV->hasInitializer() || + GEP->getNumOperands() < 3 || !isa(GEP->getOperand(1)) || + !cast(GEP->getOperand(1))->isNullValue()) + return UnknownValue; + + // Okay, we allow one non-constant index into the GEP instruction. + Value *VarIdx = 0; + std::vector Indexes; + unsigned VarIdxNum = 0; + for (unsigned i = 2, e = GEP->getNumOperands(); i != e; ++i) + if (ConstantInt *CI = dyn_cast(GEP->getOperand(i))) { + Indexes.push_back(CI); + } else if (!isa(GEP->getOperand(i))) { + if (VarIdx) return UnknownValue; // Multiple non-constant idx's. + VarIdx = GEP->getOperand(i); + VarIdxNum = i-2; + Indexes.push_back(0); + } + + // Okay, we know we have a (load (gep GV, 0, X)) comparison with a constant. + // Check to see if X is a loop variant variable value now. + SCEVHandle Idx = getSCEV(VarIdx); + SCEVHandle Tmp = getSCEVAtScope(Idx, L); + if (!isa(Tmp)) Idx = Tmp; + + // We can only recognize very limited forms of loop index expressions, in + // particular, only affine AddRec's like {C1,+,C2}. + SCEVAddRecExpr *IdxExpr = dyn_cast(Idx); + if (!IdxExpr || !IdxExpr->isAffine() || IdxExpr->isLoopInvariant(L) || + !isa(IdxExpr->getOperand(0)) || + !isa(IdxExpr->getOperand(1))) + return UnknownValue; + + unsigned MaxSteps = MaxBruteForceIterations; + for (unsigned IterationNum = 0; IterationNum != MaxSteps; ++IterationNum) { + ConstantInt *ItCst = + ConstantInt::get(IdxExpr->getType(), IterationNum); + ConstantInt *Val = EvaluateConstantChrecAtConstant(IdxExpr, ItCst); + + // Form the GEP offset. + Indexes[VarIdxNum] = Val; + + Constant *Result = GetAddressedElementFromGlobal(GV, Indexes); + if (Result == 0) break; // Cannot compute! + + // Evaluate the condition for this iteration. + Result = ConstantExpr::getICmp(predicate, Result, RHS); + if (!isa(Result)) break; // Couldn't decide for sure + if (cast(Result)->getZExtValue() == false) { +#if 0 + cerr << "\n***\n*** Computed loop count " << *ItCst + << "\n*** From global " << *GV << "*** BB: " << *L->getHeader() + << "***\n"; +#endif + ++NumArrayLenItCounts; + return SCEVConstant::get(ItCst); // Found terminating iteration! + } + } + return UnknownValue; +} + + /// CanConstantFold - Return true if we can constant fold an instruction of the /// specified type, assuming that all operands were constants. static bool CanConstantFold(const Instruction *I) { - if (isa(I) || isa(I) || + if (isa(I) || isa(I) || isa(I) || isa(I) || isa(I)) return true; - + if (const CallInst *CI = dyn_cast(I)) if (const Function *F = CI->getCalledFunction()) return canConstantFoldCallTo((Function*)F); // FIXME: elim cast return false; } -/// ConstantFold - Constant fold an instruction of the specified type with the -/// specified constant operands. This function may modify the operands vector. -static Constant *ConstantFold(const Instruction *I, - std::vector &Operands) { - if (isa(I) || isa(I)) - return ConstantExpr::get(I->getOpcode(), Operands[0], Operands[1]); - - switch (I->getOpcode()) { - case Instruction::Cast: - return ConstantExpr::getCast(Operands[0], I->getType()); - case Instruction::Select: - return ConstantExpr::getSelect(Operands[0], Operands[1], Operands[2]); - case Instruction::Call: - if (ConstantPointerRef *CPR = dyn_cast(Operands[0])) { - Operands.erase(Operands.begin()); - return ConstantFoldCall(cast(CPR->getValue()), Operands); - } - - return 0; - case Instruction::GetElementPtr: - Constant *Base = Operands[0]; - Operands.erase(Operands.begin()); - return ConstantExpr::getGetElementPtr(Base, Operands); - } - return 0; -} - - /// getConstantEvolvingPHI - Given an LLVM value and a loop, return a PHI node /// in the loop that V is derived from. We allow arbitrary operations along the /// way, but the operands of an operation must either be constants or a value @@ -1633,7 +1768,7 @@ static PHINode *getConstantEvolvingPHI(Value *V, const Loop *L) { // If we won't be able to constant fold this expression even if the operands // are constants, return early. if (!CanConstantFold(I)) return 0; - + // Otherwise, we can evaluate this instruction if all of its operands are // constant or derived from a PHI node themselves. PHINode *PHI = 0; @@ -1658,9 +1793,9 @@ static PHINode *getConstantEvolvingPHI(Value *V, const Loop *L) { /// reason, return null. static Constant *EvaluateExpression(Value *V, Constant *PHIVal) { if (isa(V)) return PHIVal; - if (Constant *C = dyn_cast(V)) return C; if (GlobalValue *GV = dyn_cast(V)) - return ConstantPointerRef::get(GV); + return GV; + if (Constant *C = dyn_cast(V)) return C; Instruction *I = cast(V); std::vector Operands; @@ -1671,7 +1806,7 @@ static Constant *EvaluateExpression(Value *V, Constant *PHIVal) { if (Operands[i] == 0) return 0; } - return ConstantFold(I, Operands); + return ConstantFoldInstOperands(I, &Operands[0], Operands.size()); } /// getConstantEvolutionLoopExitValue - If we know that the specified Phi is @@ -1685,7 +1820,7 @@ getConstantEvolutionLoopExitValue(PHINode *PN, uint64_t Its, const Loop *L) { if (I != ConstantEvolutionLoopExitValue.end()) return I->second; - if (Its > MaxBruteForceIterations) + if (Its > MaxBruteForceIterations) return ConstantEvolutionLoopExitValue[PN] = 0; // Not going to evaluate it. Constant *&RetVal = ConstantEvolutionLoopExitValue[PN]; @@ -1753,16 +1888,18 @@ ComputeIterationCountExhaustively(const Loop *L, Value *Cond, bool ExitWhen) { unsigned MaxIterations = MaxBruteForceIterations; // Limit analysis. for (Constant *PHIVal = StartCST; IterationNum != MaxIterations; ++IterationNum) { - ConstantBool *CondVal = - dyn_cast_or_null(EvaluateExpression(Cond, PHIVal)); - if (!CondVal) return UnknownValue; // Couldn't symbolically evaluate. + ConstantInt *CondVal = + dyn_cast_or_null(EvaluateExpression(Cond, PHIVal)); - if (CondVal->getValue() == ExitWhen) { + // Couldn't symbolically evaluate. + if (!CondVal) return UnknownValue; + + if (CondVal->getZExtValue() == uint64_t(ExitWhen)) { ConstantEvolutionLoopExitValue[PN] = PHIVal; ++NumBruteForceTripCountsComputed; - return SCEVConstant::get(ConstantUInt::get(Type::UIntTy, IterationNum)); + return SCEVConstant::get(ConstantInt::get(Type::Int32Ty, IterationNum)); } - + // Compute the value of the PHI node for the next iteration. Constant *NextPHI = EvaluateExpression(BEValue, PHIVal); if (NextPHI == 0 || NextPHI == PHIVal) @@ -1781,7 +1918,7 @@ SCEVHandle ScalarEvolutionsImpl::getSCEVAtScope(SCEV *V, const Loop *L) { // FIXME: this should be turned into a virtual method on SCEV! if (isa(V)) return V; - + // If this instruction is evolves from a constant-evolving PHI, compute the // exit value from the loop without using SCEVs. if (SCEVUnknown *SU = dyn_cast(V)) { @@ -1799,15 +1936,15 @@ SCEVHandle ScalarEvolutionsImpl::getSCEVAtScope(SCEV *V, const Loop *L) { // this is a constant evolving PHI node, get the final value at // the specified iteration number. Constant *RV = getConstantEvolutionLoopExitValue(PN, - ICC->getValue()->getRawValue(), + ICC->getValue()->getZExtValue(), LI); if (RV) return SCEVUnknown::get(RV); } } - // Okay, this is a some expression that we cannot symbolically evaluate + // Okay, this is an expression that we cannot symbolically evaluate // into a SCEV. Check to see if it's possible to symbolically evaluate - // the arguments into constants, and if see, try to constant propagate the + // the arguments into constants, and if so, try to constant propagate the // result. This is particularly useful for computing loop exit values. if (CanConstantFold(I)) { std::vector Operands; @@ -1816,16 +1953,17 @@ SCEVHandle ScalarEvolutionsImpl::getSCEVAtScope(SCEV *V, const Loop *L) { Value *Op = I->getOperand(i); if (Constant *C = dyn_cast(Op)) { Operands.push_back(C); - } else if (GlobalValue *GV = dyn_cast(Op)) { - Operands.push_back(ConstantPointerRef::get(GV)); } else { SCEVHandle OpV = getSCEVAtScope(getSCEV(Op), L); if (SCEVConstant *SC = dyn_cast(OpV)) - Operands.push_back(ConstantExpr::getCast(SC->getValue(), - Op->getType())); + Operands.push_back(ConstantExpr::getIntegerCast(SC->getValue(), + Op->getType(), + false)); else if (SCEVUnknown *SU = dyn_cast(OpV)) { if (Constant *C = dyn_cast(SU->getValue())) - Operands.push_back(ConstantExpr::getCast(C, Op->getType())); + Operands.push_back(ConstantExpr::getIntegerCast(C, + Op->getType(), + false)); else return V; } else { @@ -1833,7 +1971,8 @@ SCEVHandle ScalarEvolutionsImpl::getSCEVAtScope(SCEV *V, const Loop *L) { } } } - return SCEVUnknown::get(ConstantFold(I, Operands)); + Constant *C =ConstantFoldInstOperands(I, &Operands[0], Operands.size()); + return SCEVUnknown::get(C); } } @@ -1868,14 +2007,14 @@ SCEVHandle ScalarEvolutionsImpl::getSCEVAtScope(SCEV *V, const Loop *L) { return Comm; } - if (SCEVUDivExpr *UDiv = dyn_cast(V)) { - SCEVHandle LHS = getSCEVAtScope(UDiv->getLHS(), L); + if (SCEVSDivExpr *Div = dyn_cast(V)) { + SCEVHandle LHS = getSCEVAtScope(Div->getLHS(), L); if (LHS == UnknownValue) return LHS; - SCEVHandle RHS = getSCEVAtScope(UDiv->getRHS(), L); + SCEVHandle RHS = getSCEVAtScope(Div->getRHS(), L); if (RHS == UnknownValue) return RHS; - if (LHS == UDiv->getLHS() && RHS == UDiv->getRHS()) - return UDiv; // must be loop invariant - return SCEVUDivExpr::get(LHS, RHS); + if (LHS == Div->getLHS() && RHS == Div->getRHS()) + return Div; // must be loop invariant + return SCEVSDivExpr::get(LHS, RHS); } // If this is a loop recurrence for a loop that does not contain L, then we @@ -1888,7 +2027,7 @@ SCEVHandle ScalarEvolutionsImpl::getSCEVAtScope(SCEV *V, const Loop *L) { if (IterationCount == UnknownValue) return UnknownValue; IterationCount = getTruncateOrZeroExtend(IterationCount, AddRec->getType()); - + // If the value is affine, simplify the expression evaluation to just // Start + Step*IterationCount. if (AddRec->isAffine()) @@ -1917,24 +2056,24 @@ SolveQuadraticEquation(const SCEVAddRecExpr *AddRec) { SCEVConstant *L = dyn_cast(AddRec->getOperand(0)); SCEVConstant *M = dyn_cast(AddRec->getOperand(1)); SCEVConstant *N = dyn_cast(AddRec->getOperand(2)); - + // We currently can only solve this if the coefficients are constants. if (!L || !M || !N) { SCEV *CNC = new SCEVCouldNotCompute(); return std::make_pair(CNC, CNC); } - Constant *Two = ConstantInt::get(L->getValue()->getType(), 2); - - // Convert from chrec coefficients to polynomial coefficients AX^2+BX+C Constant *C = L->getValue(); + Constant *Two = ConstantInt::get(C->getType(), 2); + + // Convert from chrec coefficients to polynomial coefficients AX^2+BX+C // The B coefficient is M-N/2 Constant *B = ConstantExpr::getSub(M->getValue(), - ConstantExpr::getDiv(N->getValue(), + ConstantExpr::getSDiv(N->getValue(), Two)); // The A coefficient is N/2 - Constant *A = ConstantExpr::getDiv(N->getValue(), Two); - + Constant *A = ConstantExpr::getSDiv(N->getValue(), Two); + // Compute the B^2-4ac term. Constant *SqrtTerm = ConstantExpr::getMul(ConstantInt::get(C->getType(), 4), @@ -1942,11 +2081,8 @@ SolveQuadraticEquation(const SCEVAddRecExpr *AddRec) { SqrtTerm = ConstantExpr::getSub(ConstantExpr::getMul(B, B), SqrtTerm); // Compute floor(sqrt(B^2-4ac)) - ConstantUInt *SqrtVal = - cast(ConstantExpr::getCast(SqrtTerm, - SqrtTerm->getType()->getUnsignedVersion())); - uint64_t SqrtValV = SqrtVal->getValue(); - uint64_t SqrtValV2 = (uint64_t)sqrt(SqrtValV); + uint64_t SqrtValV = cast(SqrtTerm)->getZExtValue(); + uint64_t SqrtValV2 = (uint64_t)sqrt((double)SqrtValV); // The square root might not be precise for arbitrary 64-bit integer // values. Do some sanity checks to ensure it's correct. if (SqrtValV2*SqrtValV2 > SqrtValV || @@ -1955,22 +2091,17 @@ SolveQuadraticEquation(const SCEVAddRecExpr *AddRec) { return std::make_pair(CNC, CNC); } - SqrtVal = ConstantUInt::get(Type::ULongTy, SqrtValV2); - SqrtTerm = ConstantExpr::getCast(SqrtVal, SqrtTerm->getType()); - + ConstantInt *SqrtVal = ConstantInt::get(Type::Int64Ty, SqrtValV2); + SqrtTerm = ConstantExpr::getTruncOrBitCast(SqrtVal, SqrtTerm->getType()); + Constant *NegB = ConstantExpr::getNeg(B); Constant *TwoA = ConstantExpr::getMul(A, Two); - + // The divisions must be performed as signed divisions. - const Type *SignedTy = NegB->getType()->getSignedVersion(); - NegB = ConstantExpr::getCast(NegB, SignedTy); - TwoA = ConstantExpr::getCast(TwoA, SignedTy); - SqrtTerm = ConstantExpr::getCast(SqrtTerm, SignedTy); - Constant *Solution1 = - ConstantExpr::getDiv(ConstantExpr::getAdd(NegB, SqrtTerm), TwoA); + ConstantExpr::getSDiv(ConstantExpr::getAdd(NegB, SqrtTerm), TwoA); Constant *Solution2 = - ConstantExpr::getDiv(ConstantExpr::getSub(NegB, SqrtTerm), TwoA); + ConstantExpr::getSDiv(ConstantExpr::getSub(NegB, SqrtTerm), TwoA); return std::make_pair(SCEVUnknown::get(Solution1), SCEVUnknown::get(Solution2)); } @@ -1997,6 +2128,7 @@ SCEVHandle ScalarEvolutionsImpl::HowFarToZero(SCEV *V, const Loop *L) { // // Get the initial value for the loop. SCEVHandle Start = getSCEVAtScope(AddRec->getStart(), L->getParentLoop()); + if (isa(Start)) return UnknownValue; SCEVHandle Step = AddRec->getOperand(1); Step = getSCEVAtScope(Step, L->getParentLoop()); @@ -2005,7 +2137,7 @@ SCEVHandle ScalarEvolutionsImpl::HowFarToZero(SCEV *V, const Loop *L) { // FIXME: We should add DivExpr and RemExpr operations to our AST. if (SCEVConstant *StepC = dyn_cast(Step)) { if (StepC->getValue()->equalsInt(1)) // N % 1 == 0 - return getNegativeSCEV(Start); // 0 - Start/1 == -Start + return SCEV::getNegativeSCEV(Start); // 0 - Start/1 == -Start if (StepC->getValue()->isAllOnesValue()) // N % -1 == 0 return Start; // 0 - Start/-1 == Start @@ -2013,9 +2145,9 @@ SCEVHandle ScalarEvolutionsImpl::HowFarToZero(SCEV *V, const Loop *L) { if (SCEVConstant *StartC = dyn_cast(Start)) { ConstantInt *StartCC = StartC->getValue(); Constant *StartNegC = ConstantExpr::getNeg(StartCC); - Constant *Rem = ConstantExpr::getRem(StartNegC, StepC->getValue()); + Constant *Rem = ConstantExpr::getSRem(StartNegC, StepC->getValue()); if (Rem->isNullValue()) { - Constant *Result =ConstantExpr::getDiv(StartNegC,StepC->getValue()); + Constant *Result =ConstantExpr::getSDiv(StartNegC,StepC->getValue()); return SCEVUnknown::get(Result); } } @@ -2028,17 +2160,16 @@ SCEVHandle ScalarEvolutionsImpl::HowFarToZero(SCEV *V, const Loop *L) { SCEVConstant *R2 = dyn_cast(Roots.second); if (R1) { #if 0 - std::cerr << "HFTZ: " << *V << " - sol#1: " << *R1 - << " sol#2: " << *R2 << "\n"; + cerr << "HFTZ: " << *V << " - sol#1: " << *R1 + << " sol#2: " << *R2 << "\n"; #endif // Pick the smallest positive root value. - assert(R1->getType()->isUnsigned()&&"Didn't canonicalize to unsigned?"); - if (ConstantBool *CB = - dyn_cast(ConstantExpr::getSetLT(R1->getValue(), - R2->getValue()))) { - if (CB != ConstantBool::True) + if (ConstantInt *CB = + dyn_cast(ConstantExpr::getICmp(ICmpInst::ICMP_ULT, + R1->getValue(), R2->getValue()))) { + if (CB->getZExtValue() == false) std::swap(R1, R2); // R1 is the minimum root now. - + // We can only use this value if the chrec ends up with an exact zero // value at this index. When solving for "X*X != 5", for example, we // should not accept a root of 2. @@ -2049,7 +2180,7 @@ SCEVHandle ScalarEvolutionsImpl::HowFarToZero(SCEV *V, const Loop *L) { } } } - + return UnknownValue; } @@ -2060,38 +2191,125 @@ SCEVHandle ScalarEvolutionsImpl::HowFarToNonZero(SCEV *V, const Loop *L) { // Loops that look like: while (X == 0) are very strange indeed. We don't // handle them yet except for the trivial case. This could be expanded in the // future as needed. - + // If the value is a constant, check to see if it is known to be non-zero // already. If so, the backedge will execute zero times. if (SCEVConstant *C = dyn_cast(V)) { Constant *Zero = Constant::getNullValue(C->getValue()->getType()); - Constant *NonZero = ConstantExpr::getSetNE(C->getValue(), Zero); - if (NonZero == ConstantBool::True) + Constant *NonZero = + ConstantExpr::getICmp(ICmpInst::ICMP_NE, C->getValue(), Zero); + if (NonZero == ConstantInt::getTrue()) return getSCEV(Zero); return UnknownValue; // Otherwise it will loop infinitely. } - + // We could implement others, but I really doubt anyone writes loops like // this, and if they did, they would already be constant folded. return UnknownValue; } -static ConstantInt * -EvaluateConstantChrecAtConstant(const SCEVAddRecExpr *AddRec, Constant *C) { - SCEVHandle InVal = SCEVConstant::get(cast(C)); - SCEVHandle Val = AddRec->evaluateAtIteration(InVal); - assert(isa(Val) && - "Evaluation of SCEV at constant didn't fold correctly?"); - return cast(Val)->getValue(); -} +/// HowManyLessThans - Return the number of times a backedge containing the +/// specified less-than comparison will execute. If not computable, return +/// UnknownValue. +SCEVHandle ScalarEvolutionsImpl:: +HowManyLessThans(SCEV *LHS, SCEV *RHS, const Loop *L) { + // Only handle: "ADDREC < LoopInvariant". + if (!RHS->isLoopInvariant(L)) return UnknownValue; + + SCEVAddRecExpr *AddRec = dyn_cast(LHS); + if (!AddRec || AddRec->getLoop() != L) + return UnknownValue; + + if (AddRec->isAffine()) { + // FORNOW: We only support unit strides. + SCEVHandle One = SCEVUnknown::getIntegerSCEV(1, RHS->getType()); + if (AddRec->getOperand(1) != One) + return UnknownValue; + + // The number of iterations for "[n,+,1] < m", is m-n. However, we don't + // know that m is >= n on input to the loop. If it is, the condition return + // true zero times. What we really should return, for full generality, is + // SMAX(0, m-n). Since we cannot check this, we will instead check for a + // canonical loop form: most do-loops will have a check that dominates the + // loop, that only enters the loop if [n-1]= n. + + // Search for the check. + BasicBlock *Preheader = L->getLoopPreheader(); + BasicBlock *PreheaderDest = L->getHeader(); + if (Preheader == 0) return UnknownValue; + + BranchInst *LoopEntryPredicate = + dyn_cast(Preheader->getTerminator()); + if (!LoopEntryPredicate) return UnknownValue; + + // This might be a critical edge broken out. If the loop preheader ends in + // an unconditional branch to the loop, check to see if the preheader has a + // single predecessor, and if so, look for its terminator. + while (LoopEntryPredicate->isUnconditional()) { + PreheaderDest = Preheader; + Preheader = Preheader->getSinglePredecessor(); + if (!Preheader) return UnknownValue; // Multiple preds. + + LoopEntryPredicate = + dyn_cast(Preheader->getTerminator()); + if (!LoopEntryPredicate) return UnknownValue; + } + // Now that we found a conditional branch that dominates the loop, check to + // see if it is the comparison we are looking for. + if (ICmpInst *ICI = dyn_cast(LoopEntryPredicate->getCondition())){ + Value *PreCondLHS = ICI->getOperand(0); + Value *PreCondRHS = ICI->getOperand(1); + ICmpInst::Predicate Cond; + if (LoopEntryPredicate->getSuccessor(0) == PreheaderDest) + Cond = ICI->getPredicate(); + else + Cond = ICI->getInversePredicate(); + + switch (Cond) { + case ICmpInst::ICMP_UGT: + std::swap(PreCondLHS, PreCondRHS); + Cond = ICmpInst::ICMP_ULT; + break; + case ICmpInst::ICMP_SGT: + std::swap(PreCondLHS, PreCondRHS); + Cond = ICmpInst::ICMP_SLT; + break; + default: break; + } + + if (Cond == ICmpInst::ICMP_SLT) { + if (PreCondLHS->getType()->isInteger()) { + if (RHS != getSCEV(PreCondRHS)) + return UnknownValue; // Not a comparison against 'm'. + + if (SCEV::getMinusSCEV(AddRec->getOperand(0), One) + != getSCEV(PreCondLHS)) + return UnknownValue; // Not a comparison against 'n-1'. + } + else return UnknownValue; + } else if (Cond == ICmpInst::ICMP_ULT) + return UnknownValue; + + // cerr << "Computed Loop Trip Count as: " + // << // *SCEV::getMinusSCEV(RHS, AddRec->getOperand(0)) << "\n"; + return SCEV::getMinusSCEV(RHS, AddRec->getOperand(0)); + } + else + return UnknownValue; + } + + return UnknownValue; +} /// getNumIterationsInRange - Return the number of iterations of this loop that /// produce values in the specified constant range. Another way of looking at /// this is that it returns the first iteration number where the value is not in /// the condition, thus computing the exit count. If the iteration count can't /// be computed, an instance of SCEVCouldNotCompute is returned. -SCEVHandle SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range) const { +SCEVHandle SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range, + bool isSigned) const { if (Range.isFullSet()) // Infinite loop. return new SCEVCouldNotCompute(); @@ -2099,11 +2317,11 @@ SCEVHandle SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range) const { if (SCEVConstant *SC = dyn_cast(getStart())) if (!SC->getValue()->isNullValue()) { std::vector Operands(op_begin(), op_end()); - Operands[0] = getIntegerSCEV(0, SC->getType()); + Operands[0] = SCEVUnknown::getIntegerSCEV(0, SC->getType()); SCEVHandle Shifted = SCEVAddRecExpr::get(Operands, getLoop()); if (SCEVAddRecExpr *ShiftedAddRec = dyn_cast(Shifted)) return ShiftedAddRec->getNumIterationsInRange( - Range.subtract(SC->getValue())); + Range.subtract(SC->getValue()),isSigned); // This is strange and shouldn't happen. return new SCEVCouldNotCompute(); } @@ -2121,8 +2339,8 @@ SCEVHandle SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range) const { // First check to see if the range contains zero. If not, the first // iteration exits. ConstantInt *Zero = ConstantInt::get(getType(), 0); - if (!Range.contains(Zero)) return SCEVConstant::get(Zero); - + if (!Range.contains(Zero, isSigned)) return SCEVConstant::get(Zero); + if (isAffine()) { // If this is an affine expression then we have this situation: // Solve {0,+,A} in Range === Ax in Range @@ -2138,7 +2356,7 @@ SCEVHandle SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range) const { Constant *ExitValue = Upper; if (A != One) { ExitValue = ConstantExpr::getSub(ConstantExpr::getAdd(Upper, A), One); - ExitValue = ConstantExpr::getDiv(ExitValue, A); + ExitValue = ConstantExpr::getSDiv(ExitValue, A); } assert(isa(ExitValue) && "Constant folding of integers not implemented?"); @@ -2147,12 +2365,12 @@ SCEVHandle SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range) const { // range, then we computed our trip count, otherwise wrap around or other // things must have happened. ConstantInt *Val = EvaluateConstantChrecAtConstant(this, ExitValue); - if (Range.contains(Val)) + if (Range.contains(Val, isSigned)) return new SCEVCouldNotCompute(); // Something strange happened // Ensure that the previous value is in the range. This is a sanity check. assert(Range.contains(EvaluateConstantChrecAtConstant(this, - ConstantExpr::getSub(ExitValue, One))) && + ConstantExpr::getSub(ExitValue, One)), isSigned) && "Linear scev computation is off in a bad way!"); return SCEVConstant::get(cast(ExitValue)); } else if (isQuadratic()) { @@ -2161,7 +2379,7 @@ SCEVHandle SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range) const { // terms of figuring out when zero is crossed, instead of when // Range.getUpper() is crossed. std::vector NewOps(op_begin(), op_end()); - NewOps[0] = getNegativeSCEV(SCEVUnknown::get(Range.getUpper())); + NewOps[0] = SCEV::getNegativeSCEV(SCEVUnknown::get(Range.getUpper())); SCEVHandle NewAddRec = SCEVAddRecExpr::get(NewOps, getLoop()); // Next, solve the constructed addrec @@ -2171,37 +2389,36 @@ SCEVHandle SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range) const { SCEVConstant *R2 = dyn_cast(Roots.second); if (R1) { // Pick the smallest positive root value. - assert(R1->getType()->isUnsigned() && "Didn't canonicalize to unsigned?"); - if (ConstantBool *CB = - dyn_cast(ConstantExpr::getSetLT(R1->getValue(), - R2->getValue()))) { - if (CB != ConstantBool::True) + if (ConstantInt *CB = + dyn_cast(ConstantExpr::getICmp(ICmpInst::ICMP_ULT, + R1->getValue(), R2->getValue()))) { + if (CB->getZExtValue() == false) std::swap(R1, R2); // R1 is the minimum root now. - + // Make sure the root is not off by one. The returned iteration should // not be in the range, but the previous one should be. When solving // for "X*X < 5", for example, we should not return a root of 2. ConstantInt *R1Val = EvaluateConstantChrecAtConstant(this, R1->getValue()); - if (Range.contains(R1Val)) { + if (Range.contains(R1Val, isSigned)) { // The next iteration must be out of the range... Constant *NextVal = ConstantExpr::getAdd(R1->getValue(), ConstantInt::get(R1->getType(), 1)); - + R1Val = EvaluateConstantChrecAtConstant(this, NextVal); - if (!Range.contains(R1Val)) + if (!Range.contains(R1Val, isSigned)) return SCEVUnknown::get(NextVal); return new SCEVCouldNotCompute(); // Something strange happened } - + // If R1 was not in the range, then it is a good return value. Make // sure that R1-1 WAS in the range though, just in case. Constant *NextVal = ConstantExpr::getSub(R1->getValue(), ConstantInt::get(R1->getType(), 1)); R1Val = EvaluateConstantChrecAtConstant(this, NextVal); - if (Range.contains(R1Val)) + if (Range.contains(R1Val, isSigned)) return R1; return new SCEVCouldNotCompute(); // Something strange happened } @@ -2223,13 +2440,13 @@ SCEVHandle SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range) const { return new SCEVCouldNotCompute(); // Check to see if we found the value! - if (!Range.contains(cast(Val)->getValue())) + if (!Range.contains(cast(Val)->getValue(), isSigned)) return SCEVConstant::get(TestVal); // Increment to test the next index. TestVal = cast(ConstantExpr::getAdd(TestVal, One)); } while (TestVal != EndVal); - + return new SCEVCouldNotCompute(); } @@ -2251,7 +2468,6 @@ void ScalarEvolution::releaseMemory() { void ScalarEvolution::getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); - AU.addRequiredID(LoopSimplifyID); AU.addRequiredTransitive(); } @@ -2259,6 +2475,20 @@ SCEVHandle ScalarEvolution::getSCEV(Value *V) const { return ((ScalarEvolutionsImpl*)Impl)->getSCEV(V); } +/// hasSCEV - Return true if the SCEV for this value has already been +/// computed. +bool ScalarEvolution::hasSCEV(Value *V) const { + return ((ScalarEvolutionsImpl*)Impl)->hasSCEV(V); +} + + +/// setSCEV - Insert the specified SCEV into the map of current SCEVs for +/// the specified value. +void ScalarEvolution::setSCEV(Value *V, const SCEVHandle &H) { + ((ScalarEvolutionsImpl*)Impl)->setSCEV(V, H); +} + + SCEVHandle ScalarEvolution::getIterationCount(const Loop *L) const { return ((ScalarEvolutionsImpl*)Impl)->getIterationCount(L); } @@ -2275,63 +2505,50 @@ void ScalarEvolution::deleteInstructionFromRecords(Instruction *I) const { return ((ScalarEvolutionsImpl*)Impl)->deleteInstructionFromRecords(I); } - -/// shouldSubstituteIndVar - Return true if we should perform induction variable -/// substitution for this variable. This is a hack because we don't have a -/// strength reduction pass yet. When we do we will promote all vars, because -/// we can strength reduce them later as desired. -bool ScalarEvolution::shouldSubstituteIndVar(const SCEV *S) const { - // Don't substitute high degree polynomials. - if (const SCEVAddRecExpr *AddRec = dyn_cast(S)) - if (AddRec->getNumOperands() > 3) return false; - return true; -} - - -static void PrintLoopInfo(std::ostream &OS, const ScalarEvolution *SE, +static void PrintLoopInfo(std::ostream &OS, const ScalarEvolution *SE, const Loop *L) { // Print all inner loops first for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) PrintLoopInfo(OS, SE, *I); - - std::cerr << "Loop " << L->getHeader()->getName() << ": "; + + cerr << "Loop " << L->getHeader()->getName() << ": "; std::vector ExitBlocks; L->getExitBlocks(ExitBlocks); if (ExitBlocks.size() != 1) - std::cerr << " "; + cerr << " "; if (SE->hasLoopInvariantIterationCount(L)) { - std::cerr << *SE->getIterationCount(L) << " iterations! "; + cerr << *SE->getIterationCount(L) << " iterations! "; } else { - std::cerr << "Unpredictable iteration count. "; + cerr << "Unpredictable iteration count. "; } - std::cerr << "\n"; + cerr << "\n"; } -void ScalarEvolution::print(std::ostream &OS) const { +void ScalarEvolution::print(std::ostream &OS, const Module* ) const { Function &F = ((ScalarEvolutionsImpl*)Impl)->F; LoopInfo &LI = ((ScalarEvolutionsImpl*)Impl)->LI; OS << "Classifying expressions for: " << F.getName() << "\n"; for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) - if ((*I)->getType()->isInteger()) { - OS << **I; + if (I->getType()->isInteger()) { + OS << *I; OS << " --> "; - SCEVHandle SV = getSCEV(*I); + SCEVHandle SV = getSCEV(&*I); SV->print(OS); OS << "\t\t"; - - if ((*I)->getType()->isIntegral()) { + + if ((*I).getType()->isInteger()) { ConstantRange Bounds = SV->getValueRange(); if (!Bounds.isFullSet()) OS << "Bounds: " << Bounds << " "; } - if (const Loop *L = LI.getLoopFor((*I)->getParent())) { + if (const Loop *L = LI.getLoopFor((*I).getParent())) { OS << "Exits: "; - SCEVHandle ExitValue = getSCEVAtScope(*I, L->getParentLoop()); + SCEVHandle ExitValue = getSCEVAtScope(&*I, L->getParentLoop()); if (isa(ExitValue)) { OS << "<>"; } else { @@ -2348,66 +2565,3 @@ void ScalarEvolution::print(std::ostream &OS) const { PrintLoopInfo(OS, this, *I); } -//===----------------------------------------------------------------------===// -// ScalarEvolutionRewriter Class Implementation -//===----------------------------------------------------------------------===// - -Value *ScalarEvolutionRewriter:: -GetOrInsertCanonicalInductionVariable(const Loop *L, const Type *Ty) { - assert((Ty->isInteger() || Ty->isFloatingPoint()) && - "Can only insert integer or floating point induction variables!"); - - // Check to see if we already inserted one. - SCEVHandle H = SCEVAddRecExpr::get(getIntegerSCEV(0, Ty), - getIntegerSCEV(1, Ty), L); - return ExpandCodeFor(H, 0, Ty); -} - -/// ExpandCodeFor - Insert code to directly compute the specified SCEV -/// expression into the program. The inserted code is inserted into the -/// specified block. -Value *ScalarEvolutionRewriter::ExpandCodeFor(SCEVHandle SH, - Instruction *InsertPt, - const Type *Ty) { - std::map::iterator ExistVal =InsertedExpressions.find(SH); - Value *V; - if (ExistVal != InsertedExpressions.end()) { - V = ExistVal->second; - } else { - // Ask the recurrence object to expand the code for itself. - V = SH->expandCodeFor(*this, InsertPt); - // Cache the generated result. - InsertedExpressions.insert(std::make_pair(SH, V)); - } - - if (Ty == 0 || V->getType() == Ty) - return V; - if (Constant *C = dyn_cast(V)) - return ConstantExpr::getCast(C, Ty); - else if (Instruction *I = dyn_cast(V)) { - // Check to see if there is already a cast. If there is, use it. - for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); - UI != E; ++UI) { - if ((*UI)->getType() == Ty) - if (CastInst *CI = dyn_cast(cast(*UI))) { - BasicBlock::iterator It = I; ++It; - while (isa(It)) ++It; - if (It != BasicBlock::iterator(CI)) { - // Splice the cast immediately after the operand in question. - I->getParent()->getInstList().splice(It, - CI->getParent()->getInstList(), - CI); - } - return CI; - } - } - BasicBlock::iterator IP = I; ++IP; - if (InvokeInst *II = dyn_cast(I)) - IP = II->getNormalDest()->begin(); - while (isa(IP)) ++IP; - return new CastInst(V, Ty, V->getName(), IP); - } else { - // FIXME: check to see if there is already a cast! - return new CastInst(V, Ty, V->getName(), InsertPt); - } -}