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