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/LoopAnalysisManager.h" 19 #include "llvm/Analysis/LoopPass.h" 20 #include "llvm/Analysis/ScalarEvolutionNormalization.h" 21 #include "llvm/IR/ValueHandle.h" 22 23 namespace llvm { 24 25 class AssumptionCache; 26 class DominatorTree; 27 class Instruction; 28 class Value; 29 class ScalarEvolution; 30 class SCEV; 31 class IVUsers; 32 class DataLayout; 33 34 /// IVStrideUse - Keep track of one use of a strided induction variable. 35 /// The Expr member keeps track of the expression, User is the actual user 36 /// instruction of the operand, and 'OperandValToReplace' is the operand of 37 /// the User that is the use. 38 class IVStrideUse final : public CallbackVH, public ilist_node<IVStrideUse> { 39 friend class IVUsers; 40 public: 41 IVStrideUse(IVUsers *P, Instruction* U, Value *O) 42 : CallbackVH(U), Parent(P), OperandValToReplace(O) { 43 } 44 45 /// getUser - Return the user instruction for this use. 46 Instruction *getUser() const { 47 return cast<Instruction>(getValPtr()); 48 } 49 50 /// setUser - Assign a new user instruction for this use. 51 void setUser(Instruction *NewUser) { 52 setValPtr(NewUser); 53 } 54 55 /// getOperandValToReplace - Return the Value of the operand in the user 56 /// instruction that this IVStrideUse is representing. 57 Value *getOperandValToReplace() const { 58 return OperandValToReplace; 59 } 60 61 /// setOperandValToReplace - Assign a new Value as the operand value 62 /// to replace. 63 void setOperandValToReplace(Value *Op) { 64 OperandValToReplace = Op; 65 } 66 67 /// getPostIncLoops - Return the set of loops for which the expression has 68 /// been adjusted to use post-inc mode. 69 const PostIncLoopSet &getPostIncLoops() const { 70 return PostIncLoops; 71 } 72 73 /// transformToPostInc - Transform the expression to post-inc form for the 74 /// given loop. 75 void transformToPostInc(const Loop *L); 76 77 private: 78 /// Parent - a pointer to the IVUsers that owns this IVStrideUse. 79 IVUsers *Parent; 80 81 /// OperandValToReplace - The Value of the operand in the user instruction 82 /// that this IVStrideUse is representing. 83 WeakTrackingVH OperandValToReplace; 84 85 /// PostIncLoops - The set of loops for which Expr has been adjusted to 86 /// use post-inc mode. This corresponds with SCEVExpander's post-inc concept. 87 PostIncLoopSet PostIncLoops; 88 89 /// Deleted - Implementation of CallbackVH virtual function to 90 /// receive notification when the User is deleted. 91 void deleted() override; 92 }; 93 94 class IVUsers { 95 friend class IVStrideUse; 96 Loop *L; 97 AssumptionCache *AC; 98 LoopInfo *LI; 99 DominatorTree *DT; 100 ScalarEvolution *SE; 101 SmallPtrSet<Instruction*, 16> Processed; 102 103 /// IVUses - A list of all tracked IV uses of induction variable expressions 104 /// we are interested in. 105 ilist<IVStrideUse> IVUses; 106 107 // Ephemeral values used by @llvm.assume in this function. 108 SmallPtrSet<const Value *, 32> EphValues; 109 110 public: 111 IVUsers(Loop *L, AssumptionCache *AC, LoopInfo *LI, DominatorTree *DT, 112 ScalarEvolution *SE); 113 114 IVUsers(IVUsers &&X) 115 : L(std::move(X.L)), AC(std::move(X.AC)), DT(std::move(X.DT)), 116 SE(std::move(X.SE)), Processed(std::move(X.Processed)), 117 IVUses(std::move(X.IVUses)), EphValues(std::move(X.EphValues)) { 118 for (IVStrideUse &U : IVUses) 119 U.Parent = this; 120 } 121 IVUsers(const IVUsers &) = delete; 122 IVUsers &operator=(IVUsers &&) = delete; 123 IVUsers &operator=(const IVUsers &) = delete; 124 125 Loop *getLoop() const { return L; } 126 127 /// AddUsersIfInteresting - Inspect the specified Instruction. If it is a 128 /// reducible SCEV, recursively add its users to the IVUsesByStride set and 129 /// return true. Otherwise, return false. 130 bool AddUsersIfInteresting(Instruction *I); 131 132 IVStrideUse &AddUser(Instruction *User, Value *Operand); 133 134 /// getReplacementExpr - Return a SCEV expression which computes the 135 /// value of the OperandValToReplace of the given IVStrideUse. 136 const SCEV *getReplacementExpr(const IVStrideUse &IU) const; 137 138 /// getExpr - Return the expression for the use. 139 const SCEV *getExpr(const IVStrideUse &IU) const; 140 141 const SCEV *getStride(const IVStrideUse &IU, const Loop *L) const; 142 143 typedef ilist<IVStrideUse>::iterator iterator; 144 typedef ilist<IVStrideUse>::const_iterator const_iterator; 145 iterator begin() { return IVUses.begin(); } 146 iterator end() { return IVUses.end(); } 147 const_iterator begin() const { return IVUses.begin(); } 148 const_iterator end() const { return IVUses.end(); } 149 bool empty() const { return IVUses.empty(); } 150 151 bool isIVUserOrOperand(Instruction *Inst) const { 152 return Processed.count(Inst); 153 } 154 155 void releaseMemory(); 156 157 void print(raw_ostream &OS, const Module * = nullptr) const; 158 159 /// dump - This method is used for debugging. 160 void dump() const; 161 162 protected: 163 bool AddUsersImpl(Instruction *I, SmallPtrSetImpl<Loop*> &SimpleLoopNests); 164 }; 165 166 Pass *createIVUsersPass(); 167 168 class IVUsersWrapperPass : public LoopPass { 169 std::unique_ptr<IVUsers> IU; 170 171 public: 172 static char ID; 173 174 IVUsersWrapperPass(); 175 176 IVUsers &getIU() { return *IU; } 177 const IVUsers &getIU() const { return *IU; } 178 179 void getAnalysisUsage(AnalysisUsage &AU) const override; 180 181 bool runOnLoop(Loop *L, LPPassManager &LPM) override; 182 183 void releaseMemory() override; 184 185 void print(raw_ostream &OS, const Module * = nullptr) const override; 186 }; 187 188 /// Analysis pass that exposes the \c IVUsers for a loop. 189 class IVUsersAnalysis : public AnalysisInfoMixin<IVUsersAnalysis> { 190 friend AnalysisInfoMixin<IVUsersAnalysis>; 191 static AnalysisKey Key; 192 193 public: 194 typedef IVUsers Result; 195 196 IVUsers run(Loop &L, LoopAnalysisManager &AM, 197 LoopStandardAnalysisResults &AR); 198 }; 199 200 } 201 202 #endif 203
