1// Licensed to the .NET Foundation under one or more agreements.
2// The .NET Foundation licenses this file to you under the MIT license.
3// See the LICENSE file in the project root for more information.
4
5#ifndef _LIR_H_
6#define _LIR_H_
7
8class Compiler;
9struct GenTree;
10struct BasicBlock;
11class Rationalizer;
12
13class LIR final
14{
15public:
16 class Range;
17
18 //------------------------------------------------------------------------
19 // LIR::Flags: Defines the set of flags that may appear in the
20 // GenTree::gtLIRFlags field.
21 class Flags final
22 {
23 // Disallow the creation of values of this type.
24 Flags() = delete;
25
26 public:
27 enum : unsigned char
28 {
29 None = 0x00,
30
31 Mark = 0x01, // An aribtrary "mark" bit that can be used in place of
32 // a more expensive data structure when processing a set
33 // of LIR nodes. See for example `LIR::GetTreeRange`.
34
35 UnusedValue = 0x02, // Set on a node if it produces a value that is not
36 // subsequently used. Should never be set on nodes
37 // that return `false` for `GenTree::IsValue`. Note
38 // that this bit should not be assumed to be valid
39 // at all points during compilation: it is currently
40 // only computed during target-dependent lowering.
41
42 RegOptional = 0x04, // Set on a node if it produces a value, but does not
43 // require a register (i.e. it can be used from memory).
44 };
45 };
46
47 //------------------------------------------------------------------------
48 // LIR::Use: Represents a use <-> def edge between two nodes in a range
49 // of LIR. Provides utilities to point the use to a different
50 // def. Note that because this type deals in edges between
51 // nodes, it represents the single use of the def.
52 //
53 class Use final
54 {
55 private:
56 Range* m_range;
57 GenTree** m_edge;
58 GenTree* m_user;
59
60 public:
61 Use();
62 Use(const Use& other);
63 Use(Range& range, GenTree** edge, GenTree* user);
64
65 Use& operator=(const Use& other);
66 Use& operator=(Use&& other);
67
68 static Use GetDummyUse(Range& range, GenTree* node);
69
70 GenTree* Def() const;
71 GenTree* User() const;
72
73 bool IsInitialized() const;
74 void AssertIsValid() const;
75 bool IsDummyUse() const;
76
77 void ReplaceWith(Compiler* compiler, GenTree* replacement);
78 unsigned ReplaceWithLclVar(Compiler* compiler, unsigned blockWeight, unsigned lclNum = BAD_VAR_NUM);
79 };
80
81 //------------------------------------------------------------------------
82 // LIR::ReadOnlyRange:
83 //
84 // Represents a contiguous range of LIR nodes that may be a subrange of
85 // a containing range. Provides a small set of utilities for iteration.
86 // Instances of this type are primarily created by and provided to
87 // analysis and utility methods on LIR::Range.
88 //
89 // Although some pains have been taken to help guard against the existence
90 // of invalid subranges, it remains possible to create them. For example,
91 // consider the following:
92 //
93 // // View the block as a range
94 // LIR::Range& blockRange = LIR::AsRange(block);
95 //
96 // // Create a range from the first non-phi node in the block to the
97 // // last node in the block
98 // LIR::ReadOnlyRange nonPhis = blockRange.NonPhiNodes();
99 //
100 // // Remove the last node from the block
101 // blockRange.Remove(blockRange.LastNode());
102 //
103 // After the removal of the last node in the block, the last node of
104 // nonPhis is no longer linked to any of the other nodes in nonPhis. Due
105 // to issues such as the above, some care must be taken in order to
106 // ensure that ranges are not used once they have been invalidated.
107 //
108 class ReadOnlyRange
109 {
110 friend class LIR;
111 friend class Range;
112 friend struct BasicBlock;
113
114 private:
115 GenTree* m_firstNode;
116 GenTree* m_lastNode;
117
118 ReadOnlyRange(const ReadOnlyRange& other) = delete;
119 ReadOnlyRange& operator=(const ReadOnlyRange& other) = delete;
120
121 public:
122 ReadOnlyRange(GenTree* firstNode, GenTree* lastNode);
123
124 class Iterator
125 {
126 friend class ReadOnlyRange;
127
128 GenTree* m_node;
129
130 Iterator(GenTree* begin) : m_node(begin)
131 {
132 }
133
134 public:
135 Iterator() : m_node(nullptr)
136 {
137 }
138
139 inline GenTree* operator*()
140 {
141 return m_node;
142 }
143
144 inline GenTree* operator->()
145 {
146 return m_node;
147 }
148
149 inline bool operator==(const Iterator& other) const
150 {
151 return m_node == other.m_node;
152 }
153
154 inline bool operator!=(const Iterator& other) const
155 {
156 return m_node != other.m_node;
157 }
158
159 inline Iterator& operator++()
160 {
161 m_node = (m_node == nullptr) ? nullptr : m_node->gtNext;
162 return *this;
163 }
164 };
165
166 class ReverseIterator
167 {
168 friend class ReadOnlyRange;
169
170 GenTree* m_node;
171
172 ReverseIterator(GenTree* begin) : m_node(begin)
173 {
174 }
175
176 public:
177 ReverseIterator() : m_node(nullptr)
178 {
179 }
180
181 inline GenTree* operator*()
182 {
183 return m_node;
184 }
185
186 inline GenTree* operator->()
187 {
188 return m_node;
189 }
190
191 inline bool operator==(const ReverseIterator& other) const
192 {
193 return m_node == other.m_node;
194 }
195
196 inline bool operator!=(const ReverseIterator& other) const
197 {
198 return m_node != other.m_node;
199 }
200
201 inline ReverseIterator& operator++()
202 {
203 m_node = (m_node == nullptr) ? nullptr : m_node->gtPrev;
204 return *this;
205 }
206 };
207
208 ReadOnlyRange();
209 ReadOnlyRange(ReadOnlyRange&& other);
210
211 GenTree* FirstNode() const;
212 GenTree* LastNode() const;
213
214 bool IsEmpty() const;
215
216 Iterator begin() const;
217 Iterator end() const;
218
219 ReverseIterator rbegin() const;
220 ReverseIterator rend() const;
221
222#ifdef DEBUG
223 bool Contains(GenTree* node) const;
224#endif
225 };
226
227 //------------------------------------------------------------------------
228 // LIR::Range:
229 //
230 // Represents a contiguous range of LIR nodes. Provides a variety of
231 // variety of utilites that modify the LIR contained in the range. Unlike
232 // `ReadOnlyRange`, values of this type may be edited.
233 //
234 // Because it is not a final class, it is possible to slice values of this
235 // type; this is especially dangerous when the Range value is actually of
236 // type `BasicBlock`. As a result, this type is not copyable and it is
237 // not possible to view a `BasicBlock` as anything other than a `Range&`.
238 //
239 class Range : public ReadOnlyRange
240 {
241 friend class LIR;
242 friend struct BasicBlock;
243 friend class Rationalizer;
244
245 private:
246 Range(GenTree* firstNode, GenTree* lastNode);
247
248 Range(const Range& other) = delete;
249 Range& operator=(const Range& other) = delete;
250
251 ReadOnlyRange GetMarkedRange(unsigned markCount, GenTree* start, bool* isClosed, unsigned* sideEffects) const;
252
253 void FinishInsertBefore(GenTree* insertionPoint, GenTree* first, GenTree* last);
254 void FinishInsertAfter(GenTree* insertionPoint, GenTree* first, GenTree* last);
255
256 public:
257 Range();
258 Range(Range&& other);
259
260 GenTree* LastPhiNode() const;
261 GenTree* FirstNonPhiNode() const;
262 GenTree* FirstNonPhiOrCatchArgNode() const;
263
264 ReadOnlyRange PhiNodes() const;
265 ReadOnlyRange NonPhiNodes() const;
266
267 void InsertBefore(GenTree* insertionPoint, GenTree* node);
268 void InsertAfter(GenTree* insertionPoint, GenTree* node);
269
270 void InsertBefore(GenTree* insertionPoint, GenTree* node1, GenTree* node2);
271 void InsertBefore(GenTree* insertionPoint, GenTree* node1, GenTree* node2, GenTree* node3);
272 void InsertBefore(GenTree* insertionPoint, GenTree* node1, GenTree* node2, GenTree* node3, GenTree* node4);
273
274 void InsertAfter(GenTree* insertionPoint, GenTree* node1, GenTree* node2);
275 void InsertAfter(GenTree* insertionPoint, GenTree* node1, GenTree* node2, GenTree* node3);
276 void InsertAfter(GenTree* insertionPoint, GenTree* node1, GenTree* node2, GenTree* node3, GenTree* node4);
277
278 void InsertBefore(GenTree* insertionPoint, Range&& range);
279 void InsertAfter(GenTree* insertionPoint, Range&& range);
280
281 void InsertAtBeginning(GenTree* node);
282 void InsertAtEnd(GenTree* node);
283
284 void InsertAtBeginning(Range&& range);
285 void InsertAtEnd(Range&& range);
286
287 void Remove(GenTree* node, bool markOperandsUnused = false);
288 Range Remove(GenTree* firstNode, GenTree* lastNode);
289 Range Remove(ReadOnlyRange&& range);
290
291 void Delete(Compiler* compiler, BasicBlock* block, GenTree* node);
292 void Delete(Compiler* compiler, BasicBlock* block, GenTree* firstNode, GenTree* lastNode);
293 void Delete(Compiler* compiler, BasicBlock* block, ReadOnlyRange&& range);
294
295 bool TryGetUse(GenTree* node, Use* use);
296
297 ReadOnlyRange GetTreeRange(GenTree* root, bool* isClosed) const;
298 ReadOnlyRange GetTreeRange(GenTree* root, bool* isClosed, unsigned* sideEffects) const;
299 ReadOnlyRange GetRangeOfOperandTrees(GenTree* root, bool* isClosed, unsigned* sideEffects) const;
300
301#ifdef DEBUG
302 bool CheckLIR(Compiler* compiler, bool checkUnusedValues = false) const;
303#endif
304 };
305
306public:
307 static Range& AsRange(BasicBlock* block);
308
309 static Range EmptyRange();
310 static Range SeqTree(Compiler* compiler, GenTree* tree);
311
312 static void InsertBeforeTerminator(BasicBlock* block, LIR::Range&& range);
313};
314
315inline void GenTree::SetUnusedValue()
316{
317 gtLIRFlags |= LIR::Flags::UnusedValue;
318 ClearContained();
319}
320
321inline void GenTree::ClearUnusedValue()
322{
323 gtLIRFlags &= ~LIR::Flags::UnusedValue;
324}
325
326inline bool GenTree::IsUnusedValue() const
327{
328 return (gtLIRFlags & LIR::Flags::UnusedValue) != 0;
329}
330
331inline void GenTree::SetRegOptional()
332{
333 gtLIRFlags |= LIR::Flags::RegOptional;
334}
335
336inline void GenTree::ClearRegOptional()
337{
338 gtLIRFlags &= ~LIR::Flags::RegOptional;
339}
340
341inline bool GenTree::IsRegOptional() const
342{
343 return (gtLIRFlags & LIR::Flags::RegOptional) != 0;
344}
345
346#endif // _LIR_H_
347