1 //===------ VirtualInstruction.cpp ------------------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Tools for determining which instructions are within a statement and the
11 // nature of their operands.
13 //===----------------------------------------------------------------------===//
15 #ifndef POLLY_SUPPORT_VIRTUALINSTRUCTION_H
16 #define POLLY_SUPPORT_VIRTUALINSTRUCTION_H
18 #include "polly/ScopInfo.h"
22 /// Determine the nature of a value's use within a statement.
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
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
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).
40 // An llvm::BasicBlock.
43 // A value that can be generated using ScopExpander.
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
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.
57 // A definition within the same statement. No MemoryAccess between
58 // definition and use are necessary.
61 // Definition in another statement. There is a scalar MemoryAccess that
62 // makes it available in this statement.
67 /// The statement where a value is used.
70 /// The value that is used.
73 /// The type of value use.
76 /// The value represented as llvm::SCEV expression.
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
;
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
) {
91 /// Get a VirtualUse for an llvm::Use.
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 MemoryAcccess.
99 /// @return The VirtualUse representing the same use as @p U.
100 static VirtualUse
create(Scop
*S
, const Use
&U
, LoopInfo
*LI
, bool Virtual
);
102 /// Get a VirtualUse for any kind of use of a value within a statement.
104 /// @param S The Scop object.
105 /// @param UserStmt The statement in which @p Val is used. Can be nullptr, in
106 /// which case it assumed that the statement has been
107 /// removed, which is only possible if no instruction in it
108 /// had side-effects or computes a value used by another
110 /// @param UserScope Loop scope in which the value is used. Needed to
111 /// determine whether the value is synthesizable.
112 /// @param Val The value being used.
113 /// @param Virtual Whether to use (and prioritize over instruction location)
114 /// information about MemoryAccesses.
116 /// @return A VirtualUse object that gives information about @p Val's use in
118 static VirtualUse
create(Scop
*S
, ScopStmt
*UserStmt
, Loop
*UserScope
,
119 Value
*Val
, bool Virtual
);
121 static VirtualUse
create(ScopStmt
*UserStmt
, Loop
*UserScope
, Value
*Val
,
123 return create(UserStmt
->getParent(), UserStmt
, UserScope
, Val
, Virtual
);
126 bool isConstant() const { return Kind
== Constant
; }
127 bool isBlock() const { return Kind
== Block
; }
128 bool isSynthesizable() const { return Kind
== Synthesizable
; }
129 bool isHoisted() const { return Kind
== Hoisted
; }
130 bool isReadOnly() const { return Kind
== ReadOnly
; }
131 bool isIntra() const { return Kind
== Intra
; }
132 bool isInter() const { return Kind
== Inter
; }
134 /// Return user statement.
135 ScopStmt
*getUser() const { return User
; }
137 /// Return the used value.
138 llvm::Value
*getValue() const { return Val
; }
140 /// Return the type of use.
141 UseKind
getKind() const { return Kind
; }
143 /// Return the ScalarEvolution representation of @p Val.
144 const SCEV
*getScevExpr() const { return ScevExpr
; }
146 /// Return the MemoryAccess that makes the value available in this statement,
148 MemoryAccess
*getMemoryAccess() const { return InputMA
; }
150 /// Print a description of this object.
152 /// @param OS Stream to print to.
153 /// @param Reproducible If true, ensures that the output is stable between
154 /// runs and is suitable to check in regression tests. This excludes printing
155 /// e.g. pointer values.
156 /// If false, the output should not be used for regression
157 /// tests, but may contain more information useful in
158 /// debugger sessions.
159 void print(raw_ostream
&OS
, bool Reproducible
= true) const;
161 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
166 /// An iterator for virtual operands.
167 class VirtualOperandIterator
168 : public std::iterator
<std::forward_iterator_tag
, VirtualUse
> {
169 friend class VirtualInstruction
;
170 friend class VirtualUse
;
172 using super
= std::iterator
<std::forward_iterator_tag
, VirtualUse
>;
173 using Self
= VirtualOperandIterator
;
178 VirtualOperandIterator(ScopStmt
*User
, User::op_iterator U
)
179 : User(User
), U(U
) {}
182 using pointer
= typename
super::pointer
;
183 using reference
= typename
super::reference
;
185 inline bool operator==(const Self
&that
) const {
186 assert(this->User
== that
.User
);
187 return this->U
== that
.U
;
190 inline bool operator!=(const Self
&that
) const {
191 assert(this->User
== that
.User
);
192 return this->U
!= that
.U
;
195 VirtualUse
operator*() const {
196 return VirtualUse::create(User
, User
->getSurroundingLoop(), U
->get(), true);
199 Use
*operator->() const { return U
; }
206 Self
operator++(int) {
213 /// This class represents a "virtual instruction", an instruction in a ScopStmt,
214 /// effectively a ScopStmt/Instruction-pair.
216 /// An instructions can be moved between statements (e.g. to avoid a scalar
217 /// dependency) and even can be contained in multiple statements (for instance,
218 /// to recompute a value instead of transferring it), hence 'virtual'. This
219 /// class is required to represent such instructions that are not in their
220 /// 'physical' location anymore.
222 /// A statement can currently not contain the same instructions multiple times
223 /// (that is, from different loop iterations). Therefore, a
224 /// ScopStmt/Instruction-pair uniquely identifies a virtual instructions.
225 /// ScopStmt::getInstruction() can contain the same instruction multiple times,
226 /// but they necessarily compute the same value.
227 class VirtualInstruction
{
228 friend class VirtualOperandIterator
;
229 friend struct llvm::DenseMapInfo
<VirtualInstruction
>;
232 /// The statement this virtual instruction is in.
233 ScopStmt
*Stmt
= nullptr;
235 /// The instruction of a statement.
236 Instruction
*Inst
= nullptr;
239 VirtualInstruction() {}
241 /// Create a new virtual instruction of an instruction @p Inst in @p Stmt.
242 VirtualInstruction(ScopStmt
*Stmt
, Instruction
*Inst
)
243 : Stmt(Stmt
), Inst(Inst
) {
244 assert(Stmt
&& Inst
);
245 assert(Stmt
->contains(Inst
) &&
246 "A virtual instruction must be exist in that statement");
249 VirtualOperandIterator
operand_begin() const {
250 return VirtualOperandIterator(Stmt
, Inst
->op_begin());
253 VirtualOperandIterator
operand_end() const {
254 return VirtualOperandIterator(Stmt
, Inst
->op_end());
257 /// Returns a list of virtual operands.
259 /// Virtual operands, like virtual instructions, need to encode the ScopStmt
261 llvm::iterator_range
<VirtualOperandIterator
> operands() const {
262 return {operand_begin(), operand_end()};
265 /// Return the SCoP everything is contained in.
266 Scop
*getScop() const { return Stmt
->getParent(); }
268 /// Return the ScopStmt this virtual instruction is in.
269 ScopStmt
*getStmt() const { return Stmt
; }
271 /// Return the instruction in the statement.
272 Instruction
*getInstruction() const { return Inst
; }
274 /// Print a description of this object.
276 /// @param OS Stream to print to.
277 /// @param Reproducible If true, ensures that the output is stable between
278 /// runs and is suitable for checks in regression tests.
279 /// This excludes printing e.g., pointer values. If false,
280 /// the output should not be used for regression tests,
281 /// but may contain more information useful in debugger
283 void print(raw_ostream
&OS
, bool Reproducible
= true) const;
285 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
290 static inline bool operator==(VirtualInstruction LHS
, VirtualInstruction RHS
) {
291 return LHS
.getStmt() == RHS
.getStmt() &&
292 LHS
.getInstruction() == RHS
.getInstruction();
295 /// Find all reachable instructions and accesses.
297 /// @param S The SCoP to find everything reachable in.
298 /// @param LI LoopInfo required for analysis.
299 /// @param UsedInsts[out] Receives all reachable instructions.
300 /// @param UsedAccs[out] Receives all reachable accesses.
301 /// @param OnlyLocal If non-nullptr, activates local mode: The SCoP is
302 /// assumed to consist only of this statement and is
303 /// conservatively correct. Does not require walking the
305 void markReachable(Scop
*S
, LoopInfo
*LI
,
306 DenseSet
<VirtualInstruction
> &UsedInsts
,
307 DenseSet
<MemoryAccess
*> &UsedAccs
,
308 ScopStmt
*OnlyLocal
= nullptr);
313 /// Support VirtualInstructions in llvm::DenseMaps.
314 template <> struct DenseMapInfo
<polly::VirtualInstruction
> {
316 static bool isEqual(polly::VirtualInstruction LHS
,
317 polly::VirtualInstruction RHS
) {
318 return DenseMapInfo
<polly::ScopStmt
*>::isEqual(LHS
.getStmt(),
320 DenseMapInfo
<Instruction
*>::isEqual(LHS
.getInstruction(),
321 RHS
.getInstruction());
324 static polly::VirtualInstruction
getTombstoneKey() {
325 polly::VirtualInstruction TombstoneKey
;
326 TombstoneKey
.Stmt
= DenseMapInfo
<polly::ScopStmt
*>::getTombstoneKey();
327 TombstoneKey
.Inst
= DenseMapInfo
<Instruction
*>::getTombstoneKey();
331 static polly::VirtualInstruction
getEmptyKey() {
332 polly::VirtualInstruction EmptyKey
;
333 EmptyKey
.Stmt
= DenseMapInfo
<polly::ScopStmt
*>::getEmptyKey();
334 EmptyKey
.Inst
= DenseMapInfo
<Instruction
*>::getEmptyKey();
338 static unsigned getHashValue(polly::VirtualInstruction Val
) {
339 return DenseMapInfo
<std::pair
<polly::ScopStmt
*, Instruction
*>>::
340 getHashValue(std::make_pair(Val
.getStmt(), Val
.getInstruction()));
345 #endif /* POLLY_SUPPORT_VIRTUALINSTRUCTION_H */