src/jit/lir.h

   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
   8 class Compiler;
   9 struct GenTree;
  10 struct BasicBlock;
  11 class Rationalizer;
  12
  13 class LIR final
  14 {
  15 public:
  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
 306 public:
 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
 315 inline void GenTree::SetUnusedValue()
 316 {
 317     gtLIRFlags |= LIR::Flags::UnusedValue;
 318 #ifndef LEGACY_BACKEND
 319     ClearContained();
 320 #endif
 321 }
 322
 323 inline void GenTree::ClearUnusedValue()
 324 {
 325     gtLIRFlags &= ~LIR::Flags::UnusedValue;
 326 }
 327
 328 inline bool GenTree::IsUnusedValue() const
 329 {
 330     return (gtLIRFlags & LIR::Flags::UnusedValue) != 0;
 331 }
 332
 333 inline void GenTree::SetRegOptional()
 334 {
 335     gtLIRFlags |= LIR::Flags::RegOptional;
 336 }
 337
 338 inline void GenTree::ClearRegOptional()
 339 {
 340     gtLIRFlags &= ~LIR::Flags::RegOptional;
 341 }
 342
 343 inline bool GenTree::IsRegOptional() const
 344 {
 345     return (gtLIRFlags & LIR::Flags::RegOptional) != 0;
 346 }
 347
 348 #endif // _LIR_H_