LLVM API Documentation

IVUsers.h

Go to the documentation of this file.
00001 //===- llvm/Analysis/IVUsers.h - Induction Variable Users -------*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements bookkeeping for "interesting" users of expressions
00011 // computed from induction variables.
00012 //
00013 //===----------------------------------------------------------------------===//
00014 
00015 #ifndef LLVM_ANALYSIS_IVUSERS_H
00016 #define LLVM_ANALYSIS_IVUSERS_H
00017 
00018 #include "llvm/Analysis/LoopPass.h"
00019 #include "llvm/Analysis/ScalarEvolution.h"
00020 #include "llvm/ADT/SmallVector.h"
00021 #include <map>
00022 
00023 namespace llvm {
00024 
00025 class DominatorTree;
00026 class Instruction;
00027 class Value;
00028 struct IVUsersOfOneStride;
00029 
00030 /// IVStrideUse - Keep track of one use of a strided induction variable, where
00031 /// the stride is stored externally.  The Offset member keeps track of the
00032 /// offset from the IV, User is the actual user of the operand, and
00033 /// 'OperandValToReplace' is the operand of the User that is the use.
00034 class IVStrideUse : public CallbackVH, public ilist_node<IVStrideUse> {
00035 public:
00036   IVStrideUse(IVUsersOfOneStride *parent,
00037               const SCEV *offset,
00038               Instruction* U, Value *O)
00039     : CallbackVH(U), Parent(parent), Offset(offset),
00040       OperandValToReplace(O),
00041       IsUseOfPostIncrementedValue(false) {
00042   }
00043 
00044   /// getUser - Return the user instruction for this use.
00045   Instruction *getUser() const {
00046     return cast<Instruction>(getValPtr());
00047   }
00048 
00049   /// setUser - Assign a new user instruction for this use.
00050   void setUser(Instruction *NewUser) {
00051     setValPtr(NewUser);
00052   }
00053 
00054   /// getParent - Return a pointer to the IVUsersOfOneStride that owns
00055   /// this IVStrideUse.
00056   IVUsersOfOneStride *getParent() const { return Parent; }
00057 
00058   /// getOffset - Return the offset to add to a theoeretical induction
00059   /// variable that starts at zero and counts up by the stride to compute
00060   /// the value for the use. This always has the same type as the stride.
00061   const SCEV *getOffset() const { return Offset; }
00062 
00063   /// setOffset - Assign a new offset to this use.
00064   void setOffset(const SCEV *Val) {
00065     Offset = Val;
00066   }
00067 
00068   /// getOperandValToReplace - Return the Value of the operand in the user
00069   /// instruction that this IVStrideUse is representing.
00070   Value *getOperandValToReplace() const {
00071     return OperandValToReplace;
00072   }
00073 
00074   /// setOperandValToReplace - Assign a new Value as the operand value
00075   /// to replace.
00076   void setOperandValToReplace(Value *Op) {
00077     OperandValToReplace = Op;
00078   }
00079 
00080   /// isUseOfPostIncrementedValue - True if this should use the
00081   /// post-incremented version of this IV, not the preincremented version.
00082   /// This can only be set in special cases, such as the terminating setcc
00083   /// instruction for a loop or uses dominated by the loop.
00084   bool isUseOfPostIncrementedValue() const {
00085     return IsUseOfPostIncrementedValue;
00086   }
00087 
00088   /// setIsUseOfPostIncrmentedValue - set the flag that indicates whether
00089   /// this is a post-increment use.
00090   void setIsUseOfPostIncrementedValue(bool Val) {
00091     IsUseOfPostIncrementedValue = Val;
00092   }
00093 
00094 private:
00095   /// Parent - a pointer to the IVUsersOfOneStride that owns this IVStrideUse.
00096   IVUsersOfOneStride *Parent;
00097 
00098   /// Offset - The offset to add to the base induction expression.
00099   const SCEV *Offset;
00100 
00101   /// OperandValToReplace - The Value of the operand in the user instruction
00102   /// that this IVStrideUse is representing.
00103   WeakVH OperandValToReplace;
00104 
00105   /// IsUseOfPostIncrementedValue - True if this should use the
00106   /// post-incremented version of this IV, not the preincremented version.
00107   bool IsUseOfPostIncrementedValue;
00108 
00109   /// Deleted - Implementation of CallbackVH virtual function to
00110   /// recieve notification when the User is deleted.
00111   virtual void deleted();
00112 };
00113 
00114 template<> struct ilist_traits<IVStrideUse>
00115   : public ilist_default_traits<IVStrideUse> {
00116   // createSentinel is used to get hold of a node that marks the end of
00117   // the list...
00118   // The sentinel is relative to this instance, so we use a non-static
00119   // method.
00120   IVStrideUse *createSentinel() const {
00121     // since i(p)lists always publicly derive from the corresponding
00122     // traits, placing a data member in this class will augment i(p)list.
00123     // But since the NodeTy is expected to publicly derive from
00124     // ilist_node<NodeTy>, there is a legal viable downcast from it
00125     // to NodeTy. We use this trick to superpose i(p)list with a "ghostly"
00126     // NodeTy, which becomes the sentinel. Dereferencing the sentinel is
00127     // forbidden (save the ilist_node<NodeTy>) so no one will ever notice
00128     // the superposition.
00129     return static_cast<IVStrideUse*>(&Sentinel);
00130   }
00131   static void destroySentinel(IVStrideUse*) {}
00132 
00133   IVStrideUse *provideInitialHead() const { return createSentinel(); }
00134   IVStrideUse *ensureHead(IVStrideUse*) const { return createSentinel(); }
00135   static void noteHead(IVStrideUse*, IVStrideUse*) {}
00136 
00137 private:
00138   mutable ilist_node<IVStrideUse> Sentinel;
00139 };
00140 
00141 /// IVUsersOfOneStride - This structure keeps track of all instructions that
00142 /// have an operand that is based on the trip count multiplied by some stride.
00143 struct IVUsersOfOneStride : public ilist_node<IVUsersOfOneStride> {
00144 private:
00145   IVUsersOfOneStride(const IVUsersOfOneStride &I); // do not implement
00146   void operator=(const IVUsersOfOneStride &I);     // do not implement
00147 
00148 public:
00149   IVUsersOfOneStride() : Stride(0) {}
00150 
00151   explicit IVUsersOfOneStride(const SCEV *stride) : Stride(stride) {}
00152 
00153   /// Stride - The stride for all the contained IVStrideUses. This is
00154   /// a constant for affine strides.
00155   const SCEV *Stride;
00156 
00157   /// Users - Keep track of all of the users of this stride as well as the
00158   /// initial value and the operand that uses the IV.
00159   ilist<IVStrideUse> Users;
00160 
00161   void addUser(const SCEV *Offset, Instruction *User, Value *Operand) {
00162     Users.push_back(new IVStrideUse(this, Offset, User, Operand));
00163   }
00164 };
00165 
00166 class IVUsers : public LoopPass {
00167   friend class IVStrideUserVH;
00168   Loop *L;
00169   LoopInfo *LI;
00170   DominatorTree *DT;
00171   ScalarEvolution *SE;
00172   SmallPtrSet<Instruction*,16> Processed;
00173 
00174 public:
00175   /// IVUses - A list of all tracked IV uses of induction variable expressions
00176   /// we are interested in.
00177   ilist<IVUsersOfOneStride> IVUses;
00178 
00179   /// IVUsesByStride - A mapping from the strides in StrideOrder to the
00180   /// uses in IVUses.
00181   std::map<const SCEV *, IVUsersOfOneStride*> IVUsesByStride;
00182 
00183   /// StrideOrder - An ordering of the keys in IVUsesByStride that is stable:
00184   /// We use this to iterate over the IVUsesByStride collection without being
00185   /// dependent on random ordering of pointers in the process.
00186   SmallVector<const SCEV *, 16> StrideOrder;
00187 
00188 private:
00189   virtual void getAnalysisUsage(AnalysisUsage &AU) const;
00190 
00191   virtual bool runOnLoop(Loop *L, LPPassManager &LPM);
00192 
00193   virtual void releaseMemory();
00194 
00195 public:
00196   static char ID; // Pass ID, replacement for typeid
00197   IVUsers();
00198 
00199   /// AddUsersIfInteresting - Inspect the specified Instruction.  If it is a
00200   /// reducible SCEV, recursively add its users to the IVUsesByStride set and
00201   /// return true.  Otherwise, return false.
00202   bool AddUsersIfInteresting(Instruction *I);
00203 
00204   /// getReplacementExpr - Return a SCEV expression which computes the
00205   /// value of the OperandValToReplace of the given IVStrideUse.
00206   const SCEV *getReplacementExpr(const IVStrideUse &U) const;
00207 
00208   void print(raw_ostream &OS, const Module* = 0) const;
00209   virtual void print(std::ostream &OS, const Module* = 0) const;
00210   void print(std::ostream *OS, const Module* M = 0) const {
00211     if (OS) print(*OS, M);
00212   }
00213 
00214   /// dump - This method is used for debugging.
00215   void dump() const;
00216 };
00217 
00218 Pass *createIVUsersPass();
00219 
00220 }
00221 
00222 #endif