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
19namespace polly {
20using 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.
31class VirtualUse final {
32public:
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
66private:
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
90public:
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.
170class 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
182public:
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.
231class VirtualInstruction final {
232 friend class VirtualOperandIterator;
233 friend struct llvm::DenseMapInfo<VirtualInstruction>;
234
235private:
236 /// The statement this virtual instruction is in.
237 ScopStmt *Stmt = nullptr;
238
239 /// The instruction of a statement.
240 Instruction *Inst = nullptr;
241
242public:
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
292static 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.
307void markReachable(Scop *S, LoopInfo *LI,
308 DenseSet<VirtualInstruction> &UsedInsts,
309 DenseSet<MemoryAccess *> &UsedAccs,
310 ScopStmt *OnlyLocal = nullptr);
311} // namespace polly
312
313namespace llvm {
314/// Support VirtualInstructions in llvm::DenseMaps.
315template <> struct DenseMapInfo<polly::VirtualInstruction> {
316public:
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

source code of polly/include/polly/Support/VirtualInstruction.h