//===- llvm/Analysis/ScalarEvolution.h - Scalar Evolution -------*- 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.
-//
+//
//===----------------------------------------------------------------------===//
//
// The ScalarEvolution class is an LLVM pass which can be used to analyze and
//
// This analysis is primarily useful for induction variable substitution and
// strength reduction.
-//
+//
//===----------------------------------------------------------------------===//
#ifndef LLVM_ANALYSIS_SCALAREVOLUTION_H
#define LLVM_ANALYSIS_SCALAREVOLUTION_H
#include "llvm/Pass.h"
+#include "llvm/Support/DataTypes.h"
+#include "llvm/Support/Streams.h"
#include <set>
namespace llvm {
class Loop;
class LoopInfo;
class SCEVHandle;
- class ScalarEvolutionRewriter;
/// SCEV - This class represent an analyzed expression in the program. These
/// are reference counted opaque objects that the client is not allowed to
///
class SCEV {
const unsigned SCEVType; // The SCEV baseclass this node corresponds to
- unsigned RefCount;
+ mutable unsigned RefCount;
friend class SCEVHandle;
- void addRef() { ++RefCount; }
- void dropRef() {
+ void addRef() const { ++RefCount; }
+ void dropRef() const {
if (--RefCount == 0)
delete this;
}
protected:
virtual ~SCEV();
public:
- SCEV(unsigned SCEVTy) : SCEVType(SCEVTy), RefCount(0) {}
+ explicit SCEV(unsigned SCEVTy) : SCEVType(SCEVTy), RefCount(0) {}
+
+ /// getNegativeSCEV - Return the SCEV object corresponding to -V.
+ ///
+ static SCEVHandle getNegativeSCEV(const SCEVHandle &V);
+
+ /// getMinusSCEV - Return LHS-RHS.
+ ///
+ static SCEVHandle getMinusSCEV(const SCEVHandle &LHS,
+ const SCEVHandle &RHS);
+
unsigned getSCEVType() const { return SCEVType; }
///
virtual const Type *getType() const = 0;
- /// expandCodeFor - Given a rewriter object, expand this SCEV into a closed
- /// form expression and return a Value corresponding to the expression in
- /// question.
- virtual Value *expandCodeFor(ScalarEvolutionRewriter &SER,
- Instruction *InsertPt) = 0;
+ /// getBitWidth - Get the bit width of the type, if it has one, 0 otherwise.
+ ///
+ uint32_t getBitWidth() const;
+ /// replaceSymbolicValuesWithConcrete - If this SCEV internally references
+ /// the symbolic value "Sym", construct and return a new SCEV that produces
+ /// the same value, but which uses the concrete value Conc instead of the
+ /// symbolic value. If this SCEV does not use the symbolic value, it
+ /// returns itself.
+ virtual SCEVHandle
+ replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
+ const SCEVHandle &Conc) const = 0;
/// print - Print out the internal representation of this scalar to the
/// specified stream. This should really only be used for debugging
/// purposes.
virtual void print(std::ostream &OS) const = 0;
+ void print(std::ostream *OS) const { if (OS) print(*OS); }
/// dump - This method is used for debugging.
///
void dump() const;
};
-
+
inline std::ostream &operator<<(std::ostream &OS, const SCEV &S) {
S.print(OS);
return OS;
virtual bool isLoopInvariant(const Loop *L) const;
virtual const Type *getType() const;
virtual bool hasComputableLoopEvolution(const Loop *L) const;
- virtual Value *expandCodeFor(ScalarEvolutionRewriter &, Instruction *);
virtual void print(std::ostream &OS) const;
-
+ void print(std::ostream *OS) const { if (OS) print(*OS); }
+ virtual SCEVHandle
+ replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
+ const SCEVHandle &Conc) const;
/// Methods for support type inquiry through isa, cast, and dyn_cast:
static inline bool classof(const SCEVCouldNotCompute *S) { return true; }
SCEV *S;
SCEVHandle(); // DO NOT IMPLEMENT
public:
- SCEVHandle(SCEV *s) : S(s) {
+ SCEVHandle(const SCEV *s) : S(const_cast<SCEV*>(s)) {
assert(S && "Cannot create a handle to a null SCEV!");
S->addRef();
}
SCEVHandle(const SCEVHandle &RHS) : S(RHS.S) {
- S->addRef();
+ S->addRef();
}
~SCEVHandle() { S->dropRef(); }
class ScalarEvolution : public FunctionPass {
void *Impl; // ScalarEvolution uses the pimpl pattern
public:
- ScalarEvolution() : Impl(0) {}
-
+ static char ID; // Pass identification, replacement for typeid
+ ScalarEvolution() : FunctionPass((intptr_t)&ID), Impl(0) {}
+
/// getSCEV - Return a SCEV expression handle for the full generality of the
/// specified expression.
SCEVHandle getSCEV(Value *V) const;
+ /// hasSCEV - Return true if the SCEV for this value has already been
+ /// computed.
+ bool hasSCEV(Value *V) const;
+
+ /// setSCEV - Insert the specified SCEV into the map of current SCEVs for
+ /// the specified value.
+ void setSCEV(Value *V, const SCEVHandle &H);
+
/// getSCEVAtScope - Return a SCEV expression handle for the specified value
/// at the specified scope in the program. The L value specifies a loop
/// nest to evaluate the expression at, where null is the top-level or a
/// an analyzable loop-invariant iteration count.
bool hasLoopInvariantIterationCount(const Loop *L) const;
- /// deleteInstructionFromRecords - This method should be called by the
- /// client before it removes an instruction from the program, to make sure
+ /// deleteValueFromRecords - This method should be called by the
+ /// client before it removes a Value from the program, to make sure
/// that no dangling references are left around.
- void deleteInstructionFromRecords(Instruction *I) const;
-
- /// 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 shouldSubstituteIndVar(const SCEV *S) const;
+ void deleteValueFromRecords(Value *V) const;
virtual bool runOnFunction(Function &F);
virtual void releaseMemory();
virtual void getAnalysisUsage(AnalysisUsage &AU) const;
- virtual void print(std::ostream &OS) const;
- };
-
- /// ScalarEvolutionRewriter - This class uses information about analyze
- /// scalars to rewrite expressions in canonical form. This can be used for
- /// induction variable substitution, strength reduction, or loop exit value
- /// replacement.
- ///
- /// Clients should create an instance of this class when rewriting is needed,
- /// and destroying it when finished to allow the release of the associated
- /// memory.
- class ScalarEvolutionRewriter {
- ScalarEvolution &SE;
- LoopInfo &LI;
- std::map<SCEVHandle, Value*> InsertedExpressions;
- std::set<Instruction*> InsertedInstructions;
- public:
- ScalarEvolutionRewriter(ScalarEvolution &se, LoopInfo &li)
- : SE(se), LI(li) {}
-
- /// isInsertedInstruction - Return true if the specified instruction was
- /// inserted by the code rewriter. If so, the client should not modify the
- /// instruction.
- bool isInsertedInstruction(Instruction *I) const {
- return InsertedInstructions.count(I);
+ virtual void print(std::ostream &OS, const Module* = 0) const;
+ void print(std::ostream *OS, const Module* M = 0) const {
+ if (OS) print(*OS, M);
}
-
- /// GetOrInsertCanonicalInductionVariable - This method returns the
- /// canonical induction variable of the specified type for the specified
- /// loop (inserts one if there is none). A canonical induction variable
- /// starts at zero and steps by one on each iteration.
- Value *GetOrInsertCanonicalInductionVariable(const Loop *L, const Type *Ty);
-
- /// ExpandCodeFor - Insert code to directly compute the specified SCEV
- /// expression into the program. The inserted code is inserted into the
- /// specified block.
- ///
- /// If a particular value sign is required, a type may be specified for the
- /// result.
- Value *ExpandCodeFor(SCEVHandle SH, Instruction *InsertPt,
- const Type *Ty = 0);
};
}
projects / oota-llvm.git / blobdiff