IVUsers.h revision 586f69a11881d828c056ce017b3fb432341d9657
169e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal//===- llvm/Analysis/IVUsers.h - Induction Variable Users -------*- C++ -*-===// 269e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal// 369e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal// The LLVM Compiler Infrastructure 469e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal// 569e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal// This file is distributed under the University of Illinois Open Source 669e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal// License. See LICENSE.TXT for details. 769e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal// 869e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal//===----------------------------------------------------------------------===// 969e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal// 1069e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal// This file implements bookkeeping for "interesting" users of expressions 1169e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal// computed from induction variables. 1269e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal// 1369e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal//===----------------------------------------------------------------------===// 1469e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 1569e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal#ifndef LLVM_ANALYSIS_IVUSERS_H 1669e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal#define LLVM_ANALYSIS_IVUSERS_H 1769e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 1869e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal#include "llvm/Analysis/LoopPass.h" 1969e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal#include "llvm/Analysis/ScalarEvolution.h" 2069e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal#include "llvm/ADT/SmallVector.h" 2169e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal#include <map> 2269e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 2369e17611504376e4d4603925f8528dfc890fd2c6Luis Sigalnamespace llvm { 2469e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 2569e17611504376e4d4603925f8528dfc890fd2c6Luis Sigalclass DominatorTree; 2669e17611504376e4d4603925f8528dfc890fd2c6Luis Sigalclass Instruction; 2769e17611504376e4d4603925f8528dfc890fd2c6Luis Sigalclass Value; 2869e17611504376e4d4603925f8528dfc890fd2c6Luis Sigalstruct IVUsersOfOneStride; 2969e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 3069e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal/// IVStrideUse - Keep track of one use of a strided induction variable, where 3169e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal/// the stride is stored externally. The Offset member keeps track of the 3269e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal/// offset from the IV, User is the actual user of the operand, and 3369e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal/// 'OperandValToReplace' is the operand of the User that is the use. 3469e17611504376e4d4603925f8528dfc890fd2c6Luis Sigalclass IVStrideUse : public CallbackVH, public ilist_node<IVStrideUse> { 3569e17611504376e4d4603925f8528dfc890fd2c6Luis Sigalpublic: 3669e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal IVStrideUse(IVUsersOfOneStride *parent, 3769e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal const SCEV *offset, 3869e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal Instruction* U, Value *O) 3969e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal : CallbackVH(U), Parent(parent), Offset(offset), 4069e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal OperandValToReplace(O), 4169e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal IsUseOfPostIncrementedValue(false) { 4269e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal } 4369e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 4469e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// getUser - Return the user instruction for this use. 4569e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal Instruction *getUser() const { 4669e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal return cast<Instruction>(getValPtr()); 4769e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal } 4869e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 4969e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// setUser - Assign a new user instruction for this use. 5069e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal void setUser(Instruction *NewUser) { 5169e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal setValPtr(NewUser); 5269e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal } 5369e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 5469e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// getParent - Return a pointer to the IVUsersOfOneStride that owns 5569e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// this IVStrideUse. 5669e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal IVUsersOfOneStride *getParent() const { return Parent; } 5769e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 5869e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// getOffset - Return the offset to add to a theoeretical induction 5969e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// variable that starts at zero and counts up by the stride to compute 6069e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// the value for the use. This always has the same type as the stride. 6169e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal const SCEV *getOffset() const { return Offset; } 6269e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 6369e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// setOffset - Assign a new offset to this use. 6469e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal void setOffset(const SCEV *Val) { 6569e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal Offset = Val; 6669e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal } 6769e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 6869e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// getOperandValToReplace - Return the Value of the operand in the user 6969e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// instruction that this IVStrideUse is representing. 7069e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal Value *getOperandValToReplace() const { 7169e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal return OperandValToReplace; 7269e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal } 7369e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 7469e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// setOperandValToReplace - Assign a new Value as the operand value 7569e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// to replace. 7669e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal void setOperandValToReplace(Value *Op) { 7769e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal OperandValToReplace = Op; 7869e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal } 7969e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 8069e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// isUseOfPostIncrementedValue - True if this should use the 8169e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// post-incremented version of this IV, not the preincremented version. 8269e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// This can only be set in special cases, such as the terminating setcc 8369e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// instruction for a loop or uses dominated by the loop. 8469e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal bool isUseOfPostIncrementedValue() const { 8569e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal return IsUseOfPostIncrementedValue; 8669e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal } 8769e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 8869e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// setIsUseOfPostIncrmentedValue - set the flag that indicates whether 8969e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// this is a post-increment use. 9069e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal void setIsUseOfPostIncrementedValue(bool Val) { 9169e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal IsUseOfPostIncrementedValue = Val; 9269e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal } 9369e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 9469e17611504376e4d4603925f8528dfc890fd2c6Luis Sigalprivate: 9569e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// Parent - a pointer to the IVUsersOfOneStride that owns this IVStrideUse. 9669e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal IVUsersOfOneStride *Parent; 9769e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 9869e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// Offset - The offset to add to the base induction expression. 9969e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal const SCEV *Offset; 10069e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 10169e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// OperandValToReplace - The Value of the operand in the user instruction 10269e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// that this IVStrideUse is representing. 10369e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal WeakVH OperandValToReplace; 10469e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 10569e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// IsUseOfPostIncrementedValue - True if this should use the 10669e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// post-incremented version of this IV, not the preincremented version. 10769e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal bool IsUseOfPostIncrementedValue; 10869e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 10969e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// Deleted - Implementation of CallbackVH virtual function to 11069e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// recieve notification when the User is deleted. 11169e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal virtual void deleted(); 11269e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal}; 11369e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 11469e17611504376e4d4603925f8528dfc890fd2c6Luis Sigaltemplate<> struct ilist_traits<IVStrideUse> 11569e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal : public ilist_default_traits<IVStrideUse> { 11669e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal // createSentinel is used to get hold of a node that marks the end of 11769e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal // the list... 11869e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal // The sentinel is relative to this instance, so we use a non-static 11969e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal // method. 12069e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal IVStrideUse *createSentinel() const { 12169e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal // since i(p)lists always publicly derive from the corresponding 12269e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal // traits, placing a data member in this class will augment i(p)list. 12369e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal // But since the NodeTy is expected to publicly derive from 12469e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal // ilist_node<NodeTy>, there is a legal viable downcast from it 12569e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal // to NodeTy. We use this trick to superpose i(p)list with a "ghostly" 12669e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal // NodeTy, which becomes the sentinel. Dereferencing the sentinel is 12769e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal // forbidden (save the ilist_node<NodeTy>) so no one will ever notice 12869e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal // the superposition. 12969e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal return static_cast<IVStrideUse*>(&Sentinel); 13069e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal } 13169e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal static void destroySentinel(IVStrideUse*) {} 13269e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 13369e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal IVStrideUse *provideInitialHead() const { return createSentinel(); } 13469e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal IVStrideUse *ensureHead(IVStrideUse*) const { return createSentinel(); } 13569e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal static void noteHead(IVStrideUse*, IVStrideUse*) {} 13669e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 13769e17611504376e4d4603925f8528dfc890fd2c6Luis Sigalprivate: 13869e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal mutable ilist_node<IVStrideUse> Sentinel; 13969e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal}; 14069e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 14169e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal/// IVUsersOfOneStride - This structure keeps track of all instructions that 14269e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal/// have an operand that is based on the trip count multiplied by some stride. 14369e17611504376e4d4603925f8528dfc890fd2c6Luis Sigalstruct IVUsersOfOneStride : public ilist_node<IVUsersOfOneStride> { 14469e17611504376e4d4603925f8528dfc890fd2c6Luis Sigalprivate: 14569e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal IVUsersOfOneStride(const IVUsersOfOneStride &I); // do not implement 14669e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal void operator=(const IVUsersOfOneStride &I); // do not implement 14769e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 14869e17611504376e4d4603925f8528dfc890fd2c6Luis Sigalpublic: 14969e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal IVUsersOfOneStride() : Stride(0) {} 15069e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 15169e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal explicit IVUsersOfOneStride(const SCEV *stride) : Stride(stride) {} 15269e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 15369e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// Stride - The stride for all the contained IVStrideUses. This is 15469e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// a constant for affine strides. 15569e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal const SCEV *Stride; 15669e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 15769e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// Users - Keep track of all of the users of this stride as well as the 15869e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal /// initial value and the operand that uses the IV. 15969e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal ilist<IVStrideUse> Users; 16069e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 16169e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal void addUser(const SCEV *Offset, Instruction *User, Value *Operand) { 16269e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal Users.push_back(new IVStrideUse(this, Offset, User, Operand)); 16369e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal } 16469e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 16569e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal void removeUser(IVStrideUse *User) { 16669e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal Users.erase(User); 16769e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal } 16869e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal}; 16969e17611504376e4d4603925f8528dfc890fd2c6Luis Sigal 170class IVUsers : public LoopPass { 171 friend class IVStrideUserVH; 172 Loop *L; 173 LoopInfo *LI; 174 DominatorTree *DT; 175 ScalarEvolution *SE; 176 SmallPtrSet<Instruction*,16> Processed; 177 178public: 179 /// IVUses - A list of all tracked IV uses of induction variable expressions 180 /// we are interested in. 181 ilist<IVUsersOfOneStride> IVUses; 182 183 /// IVUsesByStride - A mapping from the strides in StrideOrder to the 184 /// uses in IVUses. 185 std::map<const SCEV *, IVUsersOfOneStride*> IVUsesByStride; 186 187 /// StrideOrder - An ordering of the keys in IVUsesByStride that is stable: 188 /// We use this to iterate over the IVUsesByStride collection without being 189 /// dependent on random ordering of pointers in the process. 190 SmallVector<const SCEV *, 16> StrideOrder; 191 192private: 193 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 194 195 virtual bool runOnLoop(Loop *L, LPPassManager &LPM); 196 197 virtual void releaseMemory(); 198 199public: 200 static char ID; // Pass ID, replacement for typeid 201 IVUsers(); 202 203 /// AddUsersIfInteresting - Inspect the specified Instruction. If it is a 204 /// reducible SCEV, recursively add its users to the IVUsesByStride set and 205 /// return true. Otherwise, return false. 206 bool AddUsersIfInteresting(Instruction *I); 207 208 void AddUser(const SCEV *Stride, const SCEV *Offset, 209 Instruction *User, Value *Operand); 210 211 /// getReplacementExpr - Return a SCEV expression which computes the 212 /// value of the OperandValToReplace of the given IVStrideUse. 213 const SCEV *getReplacementExpr(const IVStrideUse &U) const; 214 215 void print(raw_ostream &OS, const Module* = 0) const; 216 217 /// dump - This method is used for debugging. 218 void dump() const; 219}; 220 221Pass *createIVUsersPass(); 222 223} 224 225#endif 226