1 //===- llvm/Analysis/IVUsers.h - Induction Variable Users -------*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file implements bookkeeping for "interesting" users of expressions 11 // computed from induction variables. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #ifndef LLVM_ANALYSIS_IVUSERS_H 16 #define LLVM_ANALYSIS_IVUSERS_H 17 18 #include "llvm/Analysis/LoopPass.h" 19 #include "llvm/Analysis/ScalarEvolutionNormalization.h" 20 #include "llvm/Support/ValueHandle.h" 21 22 namespace llvm { 23 24 class DominatorTree; 25 class Instruction; 26 class Value; 27 class IVUsers; 28 class ScalarEvolution; 29 class SCEV; 30 class IVUsers; 31 class TargetData; 32 33 /// IVStrideUse - Keep track of one use of a strided induction variable. 34 /// The Expr member keeps track of the expression, User is the actual user 35 /// instruction of the operand, and 'OperandValToReplace' is the operand of 36 /// the User that is the use. 37 class IVStrideUse : public CallbackVH, public ilist_node<IVStrideUse> { 38 friend class IVUsers; 39 public: 40 IVStrideUse(IVUsers *P, Instruction* U, Value *O) 41 : CallbackVH(U), Parent(P), OperandValToReplace(O) { 42 } 43 44 /// getUser - Return the user instruction for this use. 45 Instruction *getUser() const { 46 return cast<Instruction>(getValPtr()); 47 } 48 49 /// setUser - Assign a new user instruction for this use. 50 void setUser(Instruction *NewUser) { 51 setValPtr(NewUser); 52 } 53 54 /// getOperandValToReplace - Return the Value of the operand in the user 55 /// instruction that this IVStrideUse is representing. 56 Value *getOperandValToReplace() const { 57 return OperandValToReplace; 58 } 59 60 /// setOperandValToReplace - Assign a new Value as the operand value 61 /// to replace. 62 void setOperandValToReplace(Value *Op) { 63 OperandValToReplace = Op; 64 } 65 66 /// getPostIncLoops - Return the set of loops for which the expression has 67 /// been adjusted to use post-inc mode. 68 const PostIncLoopSet &getPostIncLoops() const { 69 return PostIncLoops; 70 } 71 72 /// transformToPostInc - Transform the expression to post-inc form for the 73 /// given loop. 74 void transformToPostInc(const Loop *L); 75 76 private: 77 /// Parent - a pointer to the IVUsers that owns this IVStrideUse. 78 IVUsers *Parent; 79 80 /// OperandValToReplace - The Value of the operand in the user instruction 81 /// that this IVStrideUse is representing. 82 WeakVH OperandValToReplace; 83 84 /// PostIncLoops - The set of loops for which Expr has been adjusted to 85 /// use post-inc mode. This corresponds with SCEVExpander's post-inc concept. 86 PostIncLoopSet PostIncLoops; 87 88 /// Deleted - Implementation of CallbackVH virtual function to 89 /// receive notification when the User is deleted. 90 virtual void deleted(); 91 }; 92 93 template<> struct ilist_traits<IVStrideUse> 94 : public ilist_default_traits<IVStrideUse> { 95 // createSentinel is used to get hold of a node that marks the end of 96 // the list... 97 // The sentinel is relative to this instance, so we use a non-static 98 // method. 99 IVStrideUse *createSentinel() const { 100 // since i(p)lists always publicly derive from the corresponding 101 // traits, placing a data member in this class will augment i(p)list. 102 // But since the NodeTy is expected to publicly derive from 103 // ilist_node<NodeTy>, there is a legal viable downcast from it 104 // to NodeTy. We use this trick to superpose i(p)list with a "ghostly" 105 // NodeTy, which becomes the sentinel. Dereferencing the sentinel is 106 // forbidden (save the ilist_node<NodeTy>) so no one will ever notice 107 // the superposition. 108 return static_cast<IVStrideUse*>(&Sentinel); 109 } 110 static void destroySentinel(IVStrideUse*) {} 111 112 IVStrideUse *provideInitialHead() const { return createSentinel(); } 113 IVStrideUse *ensureHead(IVStrideUse*) const { return createSentinel(); } 114 static void noteHead(IVStrideUse*, IVStrideUse*) {} 115 116 private: 117 mutable ilist_node<IVStrideUse> Sentinel; 118 }; 119 120 class IVUsers : public LoopPass { 121 friend class IVStrideUse; 122 Loop *L; 123 LoopInfo *LI; 124 DominatorTree *DT; 125 ScalarEvolution *SE; 126 TargetData *TD; 127 SmallPtrSet<Instruction*,16> Processed; 128 129 /// IVUses - A list of all tracked IV uses of induction variable expressions 130 /// we are interested in. 131 ilist<IVStrideUse> IVUses; 132 133 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 134 135 virtual bool runOnLoop(Loop *L, LPPassManager &LPM); 136 137 virtual void releaseMemory(); 138 139 public: 140 static char ID; // Pass ID, replacement for typeid 141 IVUsers(); 142 143 Loop *getLoop() const { return L; } 144 145 /// AddUsersIfInteresting - Inspect the specified Instruction. If it is a 146 /// reducible SCEV, recursively add its users to the IVUsesByStride set and 147 /// return true. Otherwise, return false. 148 bool AddUsersIfInteresting(Instruction *I); 149 150 IVStrideUse &AddUser(Instruction *User, Value *Operand); 151 152 /// getReplacementExpr - Return a SCEV expression which computes the 153 /// value of the OperandValToReplace of the given IVStrideUse. 154 const SCEV *getReplacementExpr(const IVStrideUse &IU) const; 155 156 /// getExpr - Return the expression for the use. 157 const SCEV *getExpr(const IVStrideUse &IU) const; 158 159 const SCEV *getStride(const IVStrideUse &IU, const Loop *L) const; 160 161 typedef ilist<IVStrideUse>::iterator iterator; 162 typedef ilist<IVStrideUse>::const_iterator const_iterator; 163 iterator begin() { return IVUses.begin(); } 164 iterator end() { return IVUses.end(); } 165 const_iterator begin() const { return IVUses.begin(); } 166 const_iterator end() const { return IVUses.end(); } 167 bool empty() const { return IVUses.empty(); } 168 169 void print(raw_ostream &OS, const Module* = 0) const; 170 171 /// dump - This method is used for debugging. 172 void dump() const; 173 }; 174 175 Pass *createIVUsersPass(); 176 177 } 178 179 #endif 180
