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