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/IR/ValueHandle.h" 21 22 namespace llvm { 23 24 class AssumptionCache; 25 class DominatorTree; 26 class Instruction; 27 class Value; 28 class ScalarEvolution; 29 class SCEV; 30 class IVUsers; 31 class DataLayout; 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 final : 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 void deleted() override; 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 AssumptionCache *AC; 124 LoopInfo *LI; 125 DominatorTree *DT; 126 ScalarEvolution *SE; 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 // Ephemeral values used by @llvm.assume in this function. 134 SmallPtrSet<const Value *, 32> EphValues; 135 136 void getAnalysisUsage(AnalysisUsage &AU) const override; 137 138 bool runOnLoop(Loop *L, LPPassManager &LPM) override; 139 140 void releaseMemory() override; 141 142 public: 143 static char ID; // Pass ID, replacement for typeid 144 IVUsers(); 145 146 Loop *getLoop() const { return L; } 147 148 /// AddUsersIfInteresting - Inspect the specified Instruction. If it is a 149 /// reducible SCEV, recursively add its users to the IVUsesByStride set and 150 /// return true. Otherwise, return false. 151 bool AddUsersIfInteresting(Instruction *I); 152 153 IVStrideUse &AddUser(Instruction *User, Value *Operand); 154 155 /// getReplacementExpr - Return a SCEV expression which computes the 156 /// value of the OperandValToReplace of the given IVStrideUse. 157 const SCEV *getReplacementExpr(const IVStrideUse &IU) const; 158 159 /// getExpr - Return the expression for the use. 160 const SCEV *getExpr(const IVStrideUse &IU) const; 161 162 const SCEV *getStride(const IVStrideUse &IU, const Loop *L) const; 163 164 typedef ilist<IVStrideUse>::iterator iterator; 165 typedef ilist<IVStrideUse>::const_iterator const_iterator; 166 iterator begin() { return IVUses.begin(); } 167 iterator end() { return IVUses.end(); } 168 const_iterator begin() const { return IVUses.begin(); } 169 const_iterator end() const { return IVUses.end(); } 170 bool empty() const { return IVUses.empty(); } 171 172 bool isIVUserOrOperand(Instruction *Inst) const { 173 return Processed.count(Inst); 174 } 175 176 void print(raw_ostream &OS, const Module* = nullptr) const override; 177 178 /// dump - This method is used for debugging. 179 void dump() const; 180 protected: 181 bool AddUsersImpl(Instruction *I, SmallPtrSetImpl<Loop*> &SimpleLoopNests); 182 }; 183 184 Pass *createIVUsersPass(); 185 186 } 187 188 #endif 189
