//===- llvm/Analysis/ScalarEvolutionExpressions.h - SCEV Exprs --*- 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 defines the classes used to represent and build scalar expressions.
-//
+//
//===----------------------------------------------------------------------===//
#ifndef LLVM_ANALYSIS_SCALAREVOLUTION_EXPRESSIONS_H
enum SCEVTypes {
// These should be ordered in terms of increasing complexity to make the
// folders simpler.
- scConstant, scTruncate, scZeroExtend, scAddExpr, scMulExpr, scUDivExpr,
+ scConstant, scTruncate, scZeroExtend, scAddExpr, scMulExpr, scSDivExpr,
scAddRecExpr, scUnknown, scCouldNotCompute
};
class SCEVConstant : public SCEV {
ConstantInt *V;
SCEVConstant(ConstantInt *v) : SCEV(scConstant), V(v) {}
-
+
virtual ~SCEVConstant();
public:
/// get method - This just gets and returns a new SCEVConstant object.
virtual const Type *getType() const;
- Value *expandCodeFor(ScalarEvolutionRewriter &SER,
- Instruction *InsertPt) {
- return (Value*)getValue();
+ SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
+ const SCEVHandle &Conc) const {
+ return this;
}
-
+
virtual void print(std::ostream &OS) const;
+ void print(std::ostream *OS) const { if (OS) print(*OS); }
/// Methods for support type inquiry through isa, cast, and dyn_cast:
static inline bool classof(const SCEVConstant *S) { return true; }
const SCEVHandle &getOperand() const { return Op; }
virtual const Type *getType() const { return Ty; }
-
+
virtual bool isLoopInvariant(const Loop *L) const {
return Op->isLoopInvariant(L);
}
return Op->hasComputableLoopEvolution(L);
}
+ SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
+ const SCEVHandle &Conc) const {
+ SCEVHandle H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc);
+ if (H == Op)
+ return this;
+ return get(H, Ty);
+ }
+
/// getValueRange - Return the tightest constant bounds that this value is
/// known to have. This method is only valid on integer SCEV objects.
virtual ConstantRange getValueRange() const;
- Value *expandCodeFor(ScalarEvolutionRewriter &SER,
- Instruction *InsertPt);
-
virtual void print(std::ostream &OS) const;
+ void print(std::ostream *OS) const { if (OS) print(*OS); }
/// Methods for support type inquiry through isa, cast, and dyn_cast:
static inline bool classof(const SCEVTruncateExpr *S) { return true; }
const SCEVHandle &getOperand() const { return Op; }
virtual const Type *getType() const { return Ty; }
-
+
virtual bool isLoopInvariant(const Loop *L) const {
return Op->isLoopInvariant(L);
}
/// known to have. This method is only valid on integer SCEV objects.
virtual ConstantRange getValueRange() const;
- Value *expandCodeFor(ScalarEvolutionRewriter &SER,
- Instruction *InsertPt);
-
+ SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
+ const SCEVHandle &Conc) const {
+ SCEVHandle H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc);
+ if (H == Op)
+ return this;
+ return get(H, Ty);
+ }
+
virtual void print(std::ostream &OS) const;
+ void print(std::ostream *OS) const { if (OS) print(*OS); }
/// Methods for support type inquiry through isa, cast, and dyn_cast:
static inline bool classof(const SCEVZeroExtendExpr *S) { return true; }
return true;
}
+ // hasComputableLoopEvolution - Commutative expressions have computable loop
+ // evolutions iff they have at least one operand that varies with the loop,
+ // but that all varying operands are computable.
virtual bool hasComputableLoopEvolution(const Loop *L) const {
+ bool HasVarying = false;
for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
- if (getOperand(i)->hasComputableLoopEvolution(L)) return true;
- return false;
+ if (!getOperand(i)->isLoopInvariant(L))
+ if (getOperand(i)->hasComputableLoopEvolution(L))
+ HasVarying = true;
+ else
+ return false;
+ return HasVarying;
}
+ SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
+ const SCEVHandle &Conc) const;
+
virtual const char *getOperationStr() const = 0;
virtual const Type *getType() const { return getOperand(0)->getType(); }
virtual void print(std::ostream &OS) const;
+ void print(std::ostream *OS) const { if (OS) print(*OS); }
/// Methods for support type inquiry through isa, cast, and dyn_cast:
static inline bool classof(const SCEVCommutativeExpr *S) { return true; }
virtual const char *getOperationStr() const { return " + "; }
- Value *expandCodeFor(ScalarEvolutionRewriter &SER,
- Instruction *InsertPt);
-
/// Methods for support type inquiry through isa, cast, and dyn_cast:
static inline bool classof(const SCEVAddExpr *S) { return true; }
static inline bool classof(const SCEV *S) {
virtual const char *getOperationStr() const { return " * "; }
- Value *expandCodeFor(ScalarEvolutionRewriter &SER,
- Instruction *InsertPt);
-
/// Methods for support type inquiry through isa, cast, and dyn_cast:
static inline bool classof(const SCEVMulExpr *S) { return true; }
static inline bool classof(const SCEV *S) {
//===--------------------------------------------------------------------===//
- /// SCEVUDivExpr - This class represents a binary unsigned division operation.
+ /// SCEVSDivExpr - This class represents a binary signed division operation.
///
- class SCEVUDivExpr : public SCEV {
+ class SCEVSDivExpr : public SCEV {
SCEVHandle LHS, RHS;
- SCEVUDivExpr(const SCEVHandle &lhs, const SCEVHandle &rhs)
- : SCEV(scUDivExpr), LHS(lhs), RHS(rhs) {}
+ SCEVSDivExpr(const SCEVHandle &lhs, const SCEVHandle &rhs)
+ : SCEV(scSDivExpr), LHS(lhs), RHS(rhs) {}
- virtual ~SCEVUDivExpr();
+ virtual ~SCEVSDivExpr();
public:
- /// get method - This just gets and returns a new SCEVUDiv object.
+ /// get method - This just gets and returns a new SCEVSDiv object.
///
static SCEVHandle get(const SCEVHandle &LHS, const SCEVHandle &RHS);
RHS->hasComputableLoopEvolution(L);
}
+ SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
+ const SCEVHandle &Conc) const {
+ SCEVHandle L = LHS->replaceSymbolicValuesWithConcrete(Sym, Conc);
+ SCEVHandle R = RHS->replaceSymbolicValuesWithConcrete(Sym, Conc);
+ if (L == LHS && R == RHS)
+ return this;
+ else
+ return get(L, R);
+ }
+
+
virtual const Type *getType() const;
- Value *expandCodeFor(ScalarEvolutionRewriter &SER,
- Instruction *InsertPt);
-
void print(std::ostream &OS) const;
+ void print(std::ostream *OS) const { if (OS) print(*OS); }
/// Methods for support type inquiry through isa, cast, and dyn_cast:
- static inline bool classof(const SCEVUDivExpr *S) { return true; }
+ static inline bool classof(const SCEVSDivExpr *S) { return true; }
static inline bool classof(const SCEV *S) {
- return S->getSCEVType() == scUDivExpr;
+ return S->getSCEVType() == scSDivExpr;
}
};
virtual bool hasComputableLoopEvolution(const Loop *QL) const {
if (L == QL) return true;
- /// FIXME: What if the start or step value a recurrence for the specified
- /// loop?
return false;
}
virtual const Type *getType() const { return Operands[0]->getType(); }
- Value *expandCodeFor(ScalarEvolutionRewriter &SER,
- Instruction *InsertPt);
-
-
/// isAffine - Return true if this is an affine AddRec (i.e., it represents
/// an expressions A+B*x where A and B are loop invariant values.
bool isAffine() const {
/// 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 getNumIterationsInRange(ConstantRange Range) const;
+ /// returned. The isSigned parameter indicates whether the ConstantRange
+ /// should be treated as signed or unsigned.
+ SCEVHandle getNumIterationsInRange(ConstantRange Range,
+ bool isSigned) const;
+ SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
+ const SCEVHandle &Conc) const;
virtual void print(std::ostream &OS) const;
+ void print(std::ostream *OS) const { if (OS) print(*OS); }
/// Methods for support type inquiry through isa, cast, and dyn_cast:
static inline bool classof(const SCEVAddRecExpr *S) { return true; }
/// SCEVUnknown.
static SCEVHandle get(Value *V);
- Value *getValue() const { return V; }
+ /// 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);
- Value *expandCodeFor(ScalarEvolutionRewriter &SER,
- Instruction *InsertPt) {
- return V;
- }
+ Value *getValue() const { return V; }
virtual bool isLoopInvariant(const Loop *L) const;
virtual bool hasComputableLoopEvolution(const Loop *QL) const {
return false; // not computable
}
+ SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
+ const SCEVHandle &Conc) const {
+ if (&*Sym == this) return Conc;
+ return this;
+ }
+
virtual const Type *getType() const;
virtual void print(std::ostream &OS) const;
+ void print(std::ostream *OS) const { if (OS) print(*OS); }
/// Methods for support type inquiry through isa, cast, and dyn_cast:
static inline bool classof(const SCEVUnknown *S) { return true; }
return S->getSCEVType() == scUnknown;
}
};
+
+ /// SCEVVisitor - This class defines a simple visitor class that may be used
+ /// for various SCEV analysis purposes.
+ template<typename SC, typename RetVal=void>
+ struct SCEVVisitor {
+ RetVal visit(SCEV *S) {
+ switch (S->getSCEVType()) {
+ case scConstant:
+ return ((SC*)this)->visitConstant((SCEVConstant*)S);
+ case scTruncate:
+ return ((SC*)this)->visitTruncateExpr((SCEVTruncateExpr*)S);
+ case scZeroExtend:
+ return ((SC*)this)->visitZeroExtendExpr((SCEVZeroExtendExpr*)S);
+ case scAddExpr:
+ return ((SC*)this)->visitAddExpr((SCEVAddExpr*)S);
+ case scMulExpr:
+ return ((SC*)this)->visitMulExpr((SCEVMulExpr*)S);
+ case scSDivExpr:
+ return ((SC*)this)->visitSDivExpr((SCEVSDivExpr*)S);
+ case scAddRecExpr:
+ return ((SC*)this)->visitAddRecExpr((SCEVAddRecExpr*)S);
+ case scUnknown:
+ return ((SC*)this)->visitUnknown((SCEVUnknown*)S);
+ case scCouldNotCompute:
+ return ((SC*)this)->visitCouldNotCompute((SCEVCouldNotCompute*)S);
+ default:
+ assert(0 && "Unknown SCEV type!");
+ abort();
+ }
+ }
+
+ RetVal visitCouldNotCompute(SCEVCouldNotCompute *S) {
+ assert(0 && "Invalid use of SCEVCouldNotCompute!");
+ abort();
+ return RetVal();
+ }
+ };
}
#endif
projects / oota-llvm.git / blobdiff