//===- 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
// 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.
#include "llvm/DerivedTypes.h"
#include "llvm/GlobalVariable.h"
#include "llvm/Instructions.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/ConstantRange.h"
#include "llvm/Support/InstIterator.h"
cl::opt<unsigned>
MaxBruteForceIterations("scalar-evolution-max-iterations", cl::ReallyHidden,
- cl::desc("Maximum number of iterations SCEV will symbolically execute a constant derived loop"),
+ cl::desc("Maximum number of iterations SCEV will "
+ "symbolically execute a constant derived loop"),
cl::init(100));
}
return false;
}
+SCEVHandle SCEVCouldNotCompute::
+replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
+ const SCEVHandle &Conc) const {
+ return this;
+}
+
void SCEVCouldNotCompute::print(std::ostream &OS) const {
OS << "***COULDNOTCOMPUTE***";
}
// particular value. Don't use a SCEVHandle here, or else the object will
// never be deleted!
static std::map<ConstantInt*, SCEVConstant*> SCEVConstants;
-
+
SCEVConstant::~SCEVConstant() {
SCEVConstants.erase(V);
const Type *NewTy = V->getType()->getUnsignedVersion();
V = cast<ConstantUInt>(ConstantExpr::getCast(V, NewTy));
}
-
+
SCEVConstant *&R = SCEVConstants[V];
if (R == 0) R = new SCEVConstant(V);
return R;
SCEVZeroExtendExpr*> SCEVZeroExtends;
SCEVZeroExtendExpr::SCEVZeroExtendExpr(const SCEVHandle &op, const Type *ty)
- : SCEV(scTruncate), Op(Op), Ty(ty) {
+ : SCEV(scTruncate), Op(op), Ty(ty) {
assert(Op->getType()->isInteger() && Ty->isInteger() &&
Ty->isUnsigned() &&
"Cannot zero extend non-integer value!");
OS << ")";
}
+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<SCEVHandle> NewOps;
+ NewOps.reserve(getNumOperands());
+ for (unsigned j = 0; j != i; ++j)
+ NewOps.push_back(getOperand(j));
+ NewOps.push_back(H);
+ for (++i; i != e; ++i)
+ NewOps.push_back(getOperand(i)->
+ replaceSymbolicValuesWithConcrete(Sym, Conc));
+
+ if (isa<SCEVAddExpr>(this))
+ return SCEVAddExpr::get(NewOps);
+ else if (isa<SCEVMulExpr>(this))
+ return SCEVMulExpr::get(NewOps);
+ else
+ assert(0 && "Unknown commutative expr!");
+ }
+ }
+ return this;
+}
+
+
// SCEVUDivs - Only allow the creation of one SCEVUDivExpr for any particular
// input. Don't use a SCEVHandle here, or else the object will never be
// deleted!
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<SCEVHandle> NewOps;
+ NewOps.reserve(getNumOperands());
+ for (unsigned j = 0; j != i; ++j)
+ NewOps.push_back(getOperand(j));
+ NewOps.push_back(H);
+ for (++i; i != e; ++i)
+ NewOps.push_back(getOperand(i)->
+ replaceSymbolicValuesWithConcrete(Sym, Conc));
+
+ 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);
}
/// specified signed integer value and return a SCEV for the constant.
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);
/// 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<SCEVConstant>(V))
return SCEVUnknown::get(ConstantExpr::getNeg(VC->getValue()));
-
+
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<ConstantInt>(Result) && "Cast of integer not folded??");
- return cast<ConstantInt>(Result);
-}
-
/// PartialFact - Compute V!/(V-NumSteps)!
static SCEVHandle PartialFact(SCEVHandle V, unsigned NumSteps) {
// Handle this case efficiently, it is common to have constant iteration
const Type *Ty = V->getType();
if (NumSteps == 0)
return SCEVUnknown::getIntegerSCEV(1, Ty);
-
+
SCEVHandle Result = V;
for (unsigned i = 1; i != NumSteps; ++i)
- Result = SCEVMulExpr::get(Result, getMinusSCEV(V,
+ Result = SCEVMulExpr::get(Result, SCEV::getMinusSCEV(V,
SCEVUnknown::getIntegerSCEV(i, Ty)));
return Result;
}
Ops[0] = SCEVConstant::get(CI);
Ops.erase(Ops.begin()+1); // Erase the folded element
if (Ops.size() == 1) return Ops[0];
+ LHSC = cast<SCEVConstant>(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
}
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.
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<SCEVMulExpr>(Ops[OtherMulIdx]);
Ops[0] = SCEVConstant::get(CI);
Ops.erase(Ops.begin()+1); // Erase the folded element
if (Ops.size() == 1) return Ops[0];
+ LHSC = cast<SCEVConstant>(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
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;
if (RHSC->getValue()->equalsInt(1))
return LHS; // X /u 1 --> x
if (RHSC->getValue()->isAllOnesValue())
- return getNegativeSCEV(LHS); // X /u -1 --> -x
+ return SCEV::getNegativeSCEV(LHS); // X /u -1 --> -x
if (SCEVConstant *LHSC = dyn_cast<SCEVConstant>(LHS)) {
Constant *LHSCV = LHSC->getValue();
/// properties. An instruction maps to null if we are unable to compute its
/// exit value.
std::map<PHINode*, Constant*> ConstantEvolutionLoopExitValue;
-
+
public:
ScalarEvolutionsImpl(Function &f, LoopInfo &li)
: F(f), LI(li), UnknownValue(new SCEVCouldNotCompute()) {}
/// 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.
/// createNodeForPHI - Provide the special handling we need to analyze PHI
/// SCEVs.
SCEVHandle createNodeForPHI(PHINode *PN);
- void UpdatePHIUserScalarEntries(Instruction *I, PHINode *PN,
- std::set<Instruction*> &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.
/// 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
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<Instruction*> &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<Value*, SCEVHandle>::iterator SI = Scalars.find(I);
- if (SI == Scalars.end()) return; // This scalar wasn't previous processed.
- if (UpdatedInsts.insert(I).second && !isa<PHINode>(PN)) {
- 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<Instruction>(*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<Instruction>(*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.
// 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() &&
// 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<Instruction*> UpdatedInsts;
- UpdatedInsts.insert(PN);
- for (Value::use_iterator UI = PN->use_begin(), E = PN->use_end();
- UI != E; ++UI)
- UpdatePHIUserScalarEntries(cast<Instruction>(*UI), PN,
- UpdatedInsts);
+ ReplaceSymbolicValueWithConcrete(PN, SymbolicName, PHISCEV);
return PHISCEV;
}
}
return SymbolicName;
}
-
+
// If it's not a loop phi, we can't handle it yet.
return SCEVUnknown::get(PN);
}
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.
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::Shl:
// Turn shift left of a constant amount into a multiply.
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()) {
Constant *NewU = ConstantExpr::getCast(CompRange.getUpper(), NewTy);
CompRange = ConstantRange(NewL, NewU);
}
-
+
SCEVHandle Ret = AddRec->getNumIterationsInRange(CompRange);
if (!isa<SCEVCouldNotCompute>(Ret)) return Ret;
}
}
-
+
switch (Cond) {
case Instruction::SetNE: // while (X != Y)
// Convert to: while (X-Y != 0)
if (LHS->getType()->isInteger()) {
- SCEVHandle TC = HowFarToZero(getMinusSCEV(LHS, RHS), L);
+ SCEVHandle TC = HowFarToZero(SCEV::getMinusSCEV(LHS, RHS), L);
if (!isa<SCEVCouldNotCompute>(TC)) return TC;
}
break;
case Instruction::SetEQ:
// Convert to: while (X-Y == 0) // while (X == Y)
if (LHS->getType()->isInteger()) {
- SCEVHandle TC = HowFarToNonZero(getMinusSCEV(LHS, RHS), L);
+ SCEVHandle TC = HowFarToNonZero(SCEV::getMinusSCEV(LHS, RHS), L);
+ if (!isa<SCEVCouldNotCompute>(TC)) return TC;
+ }
+ break;
+ case Instruction::SetLT:
+ if (LHS->getType()->isInteger() &&
+ ExitCond->getOperand(0)->getType()->isSigned()) {
+ SCEVHandle TC = HowManyLessThans(LHS, RHS, L);
+ if (!isa<SCEVCouldNotCompute>(TC)) return TC;
+ }
+ break;
+ case Instruction::SetGT:
+ if (LHS->getType()->isInteger() &&
+ ExitCond->getOperand(0)->getType()->isSigned()) {
+ SCEVHandle TC = HowManyLessThans(RHS, LHS, L);
if (!isa<SCEVCouldNotCompute>(TC)) return TC;
}
break;
/// the addressed element of the initializer or null if the index expression is
/// invalid.
static Constant *
-GetAddressedElementFromGlobal(GlobalVariable *GV,
+GetAddressedElementFromGlobal(GlobalVariable *GV,
const std::vector<ConstantInt*> &Indices) {
Constant *Init = GV->getInitializer();
for (unsigned i = 0, e = Indices.size(); i != e; ++i) {
/// 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,
+ComputeLoadConstantCompareIterationCount(LoadInst *LI, Constant *RHS,
const Loop *L, unsigned SetCCOpcode) {
if (LI->isVolatile()) return UnknownValue;
if (isa<BinaryOperator>(I) || isa<ShiftInst>(I) ||
isa<SelectInst>(I) || isa<CastInst>(I) || isa<GetElementPtrInst>(I))
return true;
-
+
if (const CallInst *CI = dyn_cast<CallInst>(I))
if (const Function *F = CI->getCalledFunction())
return canConstantFoldCallTo((Function*)F); // FIXME: elim cast
// 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;
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];
++NumBruteForceTripCountsComputed;
return SCEVConstant::get(ConstantUInt::get(Type::UIntTy, IterationNum));
}
-
+
// Compute the value of the PHI node for the next iteration.
Constant *NextPHI = EvaluateExpression(BEValue, PHIVal);
if (NextPHI == 0 || NextPHI == PHIVal)
// FIXME: this should be turned into a virtual method on SCEV!
if (isa<SCEVConstant>(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<SCEVUnknown>(V)) {
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())
SCEVConstant *L = dyn_cast<SCEVConstant>(AddRec->getOperand(0));
SCEVConstant *M = dyn_cast<SCEVConstant>(AddRec->getOperand(1));
SCEVConstant *N = dyn_cast<SCEVConstant>(AddRec->getOperand(2));
-
+
// We currently can only solve this if the coefficients are constants.
if (!L || !M || !N) {
SCEV *CNC = new SCEVCouldNotCompute();
}
Constant *Two = ConstantInt::get(L->getValue()->getType(), 2);
-
+
// Convert from chrec coefficients to polynomial coefficients AX^2+BX+C
Constant *C = L->getValue();
// The B coefficient is M-N/2
Two));
// The A coefficient is N/2
Constant *A = ConstantExpr::getDiv(N->getValue(), Two);
-
+
// Compute the B^2-4ac term.
Constant *SqrtTerm =
ConstantExpr::getMul(ConstantInt::get(C->getType(), 4),
SqrtVal = ConstantUInt::get(Type::ULongTy, SqrtValV2);
SqrtTerm = ConstantExpr::getCast(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);
Constant *Solution2 =
// FIXME: We should add DivExpr and RemExpr operations to our AST.
if (SCEVConstant *StepC = dyn_cast<SCEVConstant>(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
R2->getValue()))) {
if (CB != ConstantBool::True)
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.
}
}
}
-
+
return UnknownValue;
}
// 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<SCEVConstant>(V)) {
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;
}
+/// 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<SCEVAddRecExpr>(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]<m. If we can find this check,
+ // we know that the SMAX will evaluate to m-n, because we know that m >= n.
+
+ // Search for the check.
+ BasicBlock *Preheader = L->getLoopPreheader();
+ BasicBlock *PreheaderDest = L->getHeader();
+ if (Preheader == 0) return UnknownValue;
+
+ BranchInst *LoopEntryPredicate =
+ dyn_cast<BranchInst>(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<BranchInst>(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.
+ SetCondInst *SCI =dyn_cast<SetCondInst>(LoopEntryPredicate->getCondition());
+ if (!SCI) return UnknownValue;
+ Value *PreCondLHS = SCI->getOperand(0);
+ Value *PreCondRHS = SCI->getOperand(1);
+ Instruction::BinaryOps Cond;
+ if (LoopEntryPredicate->getSuccessor(0) == PreheaderDest)
+ Cond = SCI->getOpcode();
+ else
+ Cond = SCI->getInverseCondition();
+
+ switch (Cond) {
+ case Instruction::SetGT:
+ std::swap(PreCondLHS, PreCondRHS);
+ Cond = Instruction::SetLT;
+ // Fall Through.
+ case Instruction::SetLT:
+ if (PreCondLHS->getType()->isInteger() &&
+ PreCondLHS->getType()->isSigned()) {
+ 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'.
+ break;
+ } else {
+ return UnknownValue;
+ }
+ default: break;
+ }
+
+ //std::cerr << "Computed Loop Trip Count as: " <<
+ // *SCEV::getMinusSCEV(RHS, AddRec->getOperand(0)) << "\n";
+ return SCEV::getMinusSCEV(RHS, AddRec->getOperand(0));
+ }
+
+ 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
// iteration exits.
ConstantInt *Zero = ConstantInt::get(getType(), 0);
if (!Range.contains(Zero)) 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
// terms of figuring out when zero is crossed, instead of when
// Range.getUpper() is crossed.
std::vector<SCEVHandle> 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
R2->getValue()))) {
if (CB != ConstantBool::True)
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.
Constant *NextVal =
ConstantExpr::getAdd(R1->getValue(),
ConstantInt::get(R1->getType(), 1));
-
+
R1Val = EvaluateConstantChrecAtConstant(this, NextVal);
if (!Range.contains(R1Val))
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 =
// Increment to test the next index.
TestVal = cast<ConstantInt>(ConstantExpr::getAdd(TestVal, One));
} while (TestVal != EndVal);
-
+
return new SCEVCouldNotCompute();
}
void ScalarEvolution::getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesAll();
- AU.addRequiredID(LoopSimplifyID);
AU.addRequiredTransitive<LoopInfo>();
}
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);
}
return ((ScalarEvolutionsImpl*)Impl)->deleteInstructionFromRecords(I);
}
-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() << ": ";
std::vector<BasicBlock*> ExitBlocks;
SCEVHandle SV = getSCEV(&*I);
SV->print(OS);
OS << "\t\t";
-
+
if ((*I).getType()->isIntegral()) {
ConstantRange Bounds = SV->getValueRange();
if (!Bounds.isFullSet())
projects / oota-llvm.git / blobdiff