1 | //===------ VirtualInstruction.cpp ------------------------------*- 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 | // Tools for determining which instructions are within a statement and the |
10 | // nature of their operands. |
11 | // |
12 | //===----------------------------------------------------------------------===// |
13 | |
14 | #ifndef POLLY_SUPPORT_VIRTUALINSTRUCTION_H |
15 | #define POLLY_SUPPORT_VIRTUALINSTRUCTION_H |
16 | |
17 | #include "polly/ScopInfo.h" |
18 | |
19 | namespace polly { |
20 | using llvm::User; |
21 | |
22 | /// Determine the nature of a value's use within a statement. |
23 | /// |
24 | /// These are not always representable by llvm::Use. For instance, scalar write |
25 | /// MemoryAccesses do use a value, but are not associated with an instruction's |
26 | /// argument. |
27 | /// |
28 | /// Despite its name it is not tied to virtual instructions (although it works |
29 | /// fine with them), but to promote consistent handling of values used in |
30 | /// statements. |
31 | class VirtualUse final { |
32 | public: |
33 | /// The different types of uses. Handling usually differentiates a lot between |
34 | /// these; one can use a switch to handle each case (and get warned by the |
35 | /// compiler if one is not handled). |
36 | enum UseKind { |
37 | // An llvm::Constant. |
38 | Constant, |
39 | |
40 | // An llvm::BasicBlock. |
41 | Block, |
42 | |
43 | // A value that can be generated using ScopExpander. |
44 | Synthesizable, |
45 | |
46 | // A load that always reads the same value throughout the SCoP (address and |
47 | // the value located there a SCoP-invariant) and has been hoisted in front |
48 | // of the SCoP. |
49 | Hoisted, |
50 | |
51 | // Definition before the SCoP and not synthesizable. Can be an instruction |
52 | // outside the SCoP, a function argument or a global value. Whether there is |
53 | // a scalar MemoryAccess in this statement for reading it depends on the |
54 | // -polly-analyze-read-only-scalars switch. |
55 | ReadOnly, |
56 | |
57 | // A definition within the same statement. No MemoryAccess between |
58 | // definition and use are necessary. |
59 | Intra, |
60 | |
61 | // Definition in another statement. There is a scalar MemoryAccess that |
62 | // makes it available in this statement. |
63 | Inter |
64 | }; |
65 | |
66 | private: |
67 | /// The statement where a value is used. |
68 | ScopStmt *User; |
69 | |
70 | /// The value that is used. |
71 | Value *Val; |
72 | |
73 | /// The type of value use. |
74 | UseKind Kind; |
75 | |
76 | /// The value represented as llvm::SCEV expression. |
77 | const SCEV *ScevExpr; |
78 | |
79 | /// If this is an inter-statement (or read-only) use, contains the |
80 | /// MemoryAccess that makes the value available in this statement. In case of |
81 | /// intra-statement uses, can contain a MemoryKind::Array access. In all other |
82 | /// cases, it is a nullptr. |
83 | MemoryAccess *InputMA; |
84 | |
85 | VirtualUse(ScopStmt *User, Value *Val, UseKind Kind, const SCEV *ScevExpr, |
86 | MemoryAccess *InputMA) |
87 | : User(User), Val(Val), Kind(Kind), ScevExpr(ScevExpr), InputMA(InputMA) { |
88 | } |
89 | |
90 | public: |
91 | /// Get a VirtualUse for an llvm::Use. |
92 | /// |
93 | /// @param S The Scop object. |
94 | /// @param U The llvm::Use the get information for. |
95 | /// @param LI The LoopInfo analysis. Needed to determine whether the |
96 | /// value is synthesizable. |
97 | /// @param Virtual Whether to ignore existing MemoryAccess. |
98 | /// |
99 | /// @return The VirtualUse representing the same use as @p U. |
100 | static VirtualUse create(Scop *S, const Use &U, LoopInfo *LI, bool Virtual); |
101 | |
102 | /// Get a VirtualUse for uses within statements. |
103 | /// |
104 | /// It is assumed that the user is not a PHINode. Such uses are always |
105 | /// VirtualUse::Inter unless in a regions statement. |
106 | /// |
107 | /// @param S The Scop object. |
108 | /// @param UserStmt The statement in which @p Val is used. Can be nullptr, in |
109 | /// which case it assumed that the statement has been |
110 | /// removed, which is only possible if no instruction in it |
111 | /// had side-effects or computes a value used by another |
112 | /// statement. |
113 | /// @param UserScope Loop scope in which the value is used. Needed to |
114 | /// determine whether the value is synthesizable. |
115 | /// @param Val The value being used. |
116 | /// @param Virtual Whether to use (and prioritize over instruction location) |
117 | /// information about MemoryAccesses. |
118 | /// |
119 | /// @return A VirtualUse object that gives information about @p Val's use in |
120 | /// @p UserStmt. |
121 | static VirtualUse create(Scop *S, ScopStmt *UserStmt, Loop *UserScope, |
122 | Value *Val, bool Virtual); |
123 | |
124 | static VirtualUse create(ScopStmt *UserStmt, Loop *UserScope, Value *Val, |
125 | bool Virtual) { |
126 | return create(S: UserStmt->getParent(), UserStmt, UserScope, Val, Virtual); |
127 | } |
128 | |
129 | bool isConstant() const { return Kind == Constant; } |
130 | bool isBlock() const { return Kind == Block; } |
131 | bool isSynthesizable() const { return Kind == Synthesizable; } |
132 | bool isHoisted() const { return Kind == Hoisted; } |
133 | bool isReadOnly() const { return Kind == ReadOnly; } |
134 | bool isIntra() const { return Kind == Intra; } |
135 | bool isInter() const { return Kind == Inter; } |
136 | |
137 | /// Return user statement. |
138 | ScopStmt *getUser() const { return User; } |
139 | |
140 | /// Return the used value. |
141 | llvm::Value *getValue() const { return Val; } |
142 | |
143 | /// Return the type of use. |
144 | UseKind getKind() const { return Kind; } |
145 | |
146 | /// Return the ScalarEvolution representation of @p Val. |
147 | const SCEV *getScevExpr() const { return ScevExpr; } |
148 | |
149 | /// Return the MemoryAccess that makes the value available in this statement, |
150 | /// if any. |
151 | MemoryAccess *getMemoryAccess() const { return InputMA; } |
152 | |
153 | /// Print a description of this object. |
154 | /// |
155 | /// @param OS Stream to print to. |
156 | /// @param Reproducible If true, ensures that the output is stable between |
157 | /// runs and is suitable to check in regression tests. |
158 | /// This excludes printing e.g. pointer values. If false, |
159 | /// the output should not be used for regression tests, |
160 | /// but may contain more information useful in debugger |
161 | /// sessions. |
162 | void print(raw_ostream &OS, bool Reproducible = true) const; |
163 | |
164 | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
165 | void dump() const; |
166 | #endif |
167 | }; |
168 | |
169 | /// An iterator for virtual operands. |
170 | class VirtualOperandIterator final { |
171 | friend class VirtualInstruction; |
172 | friend class VirtualUse; |
173 | |
174 | using Self = VirtualOperandIterator; |
175 | |
176 | ScopStmt *User; |
177 | User::op_iterator U; |
178 | |
179 | VirtualOperandIterator(ScopStmt *User, User::op_iterator U) |
180 | : User(User), U(U) {} |
181 | |
182 | public: |
183 | using iterator_category = std::forward_iterator_tag; |
184 | using value_type = VirtualUse; |
185 | using difference_type = std::ptrdiff_t; |
186 | using pointer = value_type *; |
187 | using reference = value_type &; |
188 | |
189 | inline bool operator==(const Self &that) const { |
190 | assert(this->User == that.User); |
191 | return this->U == that.U; |
192 | } |
193 | |
194 | inline bool operator!=(const Self &that) const { |
195 | assert(this->User == that.User); |
196 | return this->U != that.U; |
197 | } |
198 | |
199 | VirtualUse operator*() const { |
200 | return VirtualUse::create(UserStmt: User, UserScope: User->getSurroundingLoop(), Val: U->get(), Virtual: true); |
201 | } |
202 | |
203 | Use *operator->() const { return U; } |
204 | |
205 | Self &operator++() { |
206 | U++; |
207 | return *this; |
208 | } |
209 | |
210 | Self operator++(int) { |
211 | Self tmp = *this; |
212 | ++*this; |
213 | return tmp; |
214 | } |
215 | }; |
216 | |
217 | /// This class represents a "virtual instruction", an instruction in a ScopStmt, |
218 | /// effectively a ScopStmt/Instruction-pair. |
219 | /// |
220 | /// An instructions can be moved between statements (e.g. to avoid a scalar |
221 | /// dependency) and even can be contained in multiple statements (for instance, |
222 | /// to recompute a value instead of transferring it), hence 'virtual'. This |
223 | /// class is required to represent such instructions that are not in their |
224 | /// 'physical' location anymore. |
225 | /// |
226 | /// A statement can currently not contain the same instructions multiple times |
227 | /// (that is, from different loop iterations). Therefore, a |
228 | /// ScopStmt/Instruction-pair uniquely identifies a virtual instructions. |
229 | /// ScopStmt::getInstruction() can contain the same instruction multiple times, |
230 | /// but they necessarily compute the same value. |
231 | class VirtualInstruction final { |
232 | friend class VirtualOperandIterator; |
233 | friend struct llvm::DenseMapInfo<VirtualInstruction>; |
234 | |
235 | private: |
236 | /// The statement this virtual instruction is in. |
237 | ScopStmt *Stmt = nullptr; |
238 | |
239 | /// The instruction of a statement. |
240 | Instruction *Inst = nullptr; |
241 | |
242 | public: |
243 | VirtualInstruction() {} |
244 | |
245 | /// Create a new virtual instruction of an instruction @p Inst in @p Stmt. |
246 | VirtualInstruction(ScopStmt *Stmt, Instruction *Inst) |
247 | : Stmt(Stmt), Inst(Inst) { |
248 | assert(Stmt && Inst); |
249 | } |
250 | |
251 | VirtualOperandIterator operand_begin() const { |
252 | return VirtualOperandIterator(Stmt, Inst->op_begin()); |
253 | } |
254 | |
255 | VirtualOperandIterator operand_end() const { |
256 | return VirtualOperandIterator(Stmt, Inst->op_end()); |
257 | } |
258 | |
259 | /// Returns a list of virtual operands. |
260 | /// |
261 | /// Virtual operands, like virtual instructions, need to encode the ScopStmt |
262 | /// they are in. |
263 | llvm::iterator_range<VirtualOperandIterator> operands() const { |
264 | return {operand_begin(), operand_end()}; |
265 | } |
266 | |
267 | /// Return the SCoP everything is contained in. |
268 | Scop *getScop() const { return Stmt->getParent(); } |
269 | |
270 | /// Return the ScopStmt this virtual instruction is in. |
271 | ScopStmt *getStmt() const { return Stmt; } |
272 | |
273 | /// Return the instruction in the statement. |
274 | Instruction *getInstruction() const { return Inst; } |
275 | |
276 | /// Print a description of this object. |
277 | /// |
278 | /// @param OS Stream to print to. |
279 | /// @param Reproducible If true, ensures that the output is stable between |
280 | /// runs and is suitable for checks in regression tests. |
281 | /// This excludes printing e.g., pointer values. If false, |
282 | /// the output should not be used for regression tests, |
283 | /// but may contain more information useful in debugger |
284 | /// sessions. |
285 | void print(raw_ostream &OS, bool Reproducible = true) const; |
286 | |
287 | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
288 | void dump() const; |
289 | #endif |
290 | }; |
291 | |
292 | static inline bool operator==(VirtualInstruction LHS, VirtualInstruction RHS) { |
293 | return LHS.getStmt() == RHS.getStmt() && |
294 | LHS.getInstruction() == RHS.getInstruction(); |
295 | } |
296 | |
297 | /// Find all reachable instructions and accesses. |
298 | /// |
299 | /// @param S The SCoP to find everything reachable in. |
300 | /// @param LI LoopInfo required for analysis. |
301 | /// @param UsedInsts[out] Receives all reachable instructions. |
302 | /// @param UsedAccs[out] Receives all reachable accesses. |
303 | /// @param OnlyLocal If non-nullptr, activates local mode: The SCoP is |
304 | /// assumed to consist only of this statement and is |
305 | /// conservatively correct. Does not require walking the |
306 | /// whole SCoP. |
307 | void markReachable(Scop *S, LoopInfo *LI, |
308 | DenseSet<VirtualInstruction> &UsedInsts, |
309 | DenseSet<MemoryAccess *> &UsedAccs, |
310 | ScopStmt *OnlyLocal = nullptr); |
311 | } // namespace polly |
312 | |
313 | namespace llvm { |
314 | /// Support VirtualInstructions in llvm::DenseMaps. |
315 | template <> struct DenseMapInfo<polly::VirtualInstruction> { |
316 | public: |
317 | static bool isEqual(polly::VirtualInstruction LHS, |
318 | polly::VirtualInstruction RHS) { |
319 | return DenseMapInfo<polly::ScopStmt *>::isEqual(LHS: LHS.getStmt(), |
320 | RHS: RHS.getStmt()) && |
321 | DenseMapInfo<Instruction *>::isEqual(LHS: LHS.getInstruction(), |
322 | RHS: RHS.getInstruction()); |
323 | } |
324 | |
325 | static polly::VirtualInstruction getTombstoneKey() { |
326 | polly::VirtualInstruction TombstoneKey; |
327 | TombstoneKey.Stmt = DenseMapInfo<polly::ScopStmt *>::getTombstoneKey(); |
328 | TombstoneKey.Inst = DenseMapInfo<Instruction *>::getTombstoneKey(); |
329 | return TombstoneKey; |
330 | } |
331 | |
332 | static polly::VirtualInstruction getEmptyKey() { |
333 | polly::VirtualInstruction EmptyKey; |
334 | EmptyKey.Stmt = DenseMapInfo<polly::ScopStmt *>::getEmptyKey(); |
335 | EmptyKey.Inst = DenseMapInfo<Instruction *>::getEmptyKey(); |
336 | return EmptyKey; |
337 | } |
338 | |
339 | static unsigned getHashValue(polly::VirtualInstruction Val) { |
340 | return DenseMapInfo<std::pair<polly::ScopStmt *, Instruction *>>:: |
341 | getHashValue(PairVal: std::make_pair(x: Val.getStmt(), y: Val.getInstruction())); |
342 | } |
343 | }; |
344 | } // namespace llvm |
345 | |
346 | #endif /* POLLY_SUPPORT_VIRTUALINSTRUCTION_H */ |
347 | |