Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

Rev

Blame | Last modification | View Log | Download | RSS feed

  1. //===- RDFGraph.h -----------------------------------------------*- 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. // Target-independent, SSA-based data flow graph for register data flow (RDF)
  10. // for a non-SSA program representation (e.g. post-RA machine code).
  11. //
  12. //
  13. // *** Introduction
  14. //
  15. // The RDF graph is a collection of nodes, each of which denotes some element
  16. // of the program. There are two main types of such elements: code and refe-
  17. // rences. Conceptually, "code" is something that represents the structure
  18. // of the program, e.g. basic block or a statement, while "reference" is an
  19. // instance of accessing a register, e.g. a definition or a use. Nodes are
  20. // connected with each other based on the structure of the program (such as
  21. // blocks, instructions, etc.), and based on the data flow (e.g. reaching
  22. // definitions, reached uses, etc.). The single-reaching-definition principle
  23. // of SSA is generally observed, although, due to the non-SSA representation
  24. // of the program, there are some differences between the graph and a "pure"
  25. // SSA representation.
  26. //
  27. //
  28. // *** Implementation remarks
  29. //
  30. // Since the graph can contain a large number of nodes, memory consumption
  31. // was one of the major design considerations. As a result, there is a single
  32. // base class NodeBase which defines all members used by all possible derived
  33. // classes. The members are arranged in a union, and a derived class cannot
  34. // add any data members of its own. Each derived class only defines the
  35. // functional interface, i.e. member functions. NodeBase must be a POD,
  36. // which implies that all of its members must also be PODs.
  37. // Since nodes need to be connected with other nodes, pointers have been
  38. // replaced with 32-bit identifiers: each node has an id of type NodeId.
  39. // There are mapping functions in the graph that translate between actual
  40. // memory addresses and the corresponding identifiers.
  41. // A node id of 0 is equivalent to nullptr.
  42. //
  43. //
  44. // *** Structure of the graph
  45. //
  46. // A code node is always a collection of other nodes. For example, a code
  47. // node corresponding to a basic block will contain code nodes corresponding
  48. // to instructions. In turn, a code node corresponding to an instruction will
  49. // contain a list of reference nodes that correspond to the definitions and
  50. // uses of registers in that instruction. The members are arranged into a
  51. // circular list, which is yet another consequence of the effort to save
  52. // memory: for each member node it should be possible to obtain its owner,
  53. // and it should be possible to access all other members. There are other
  54. // ways to accomplish that, but the circular list seemed the most natural.
  55. //
  56. // +- CodeNode -+
  57. // |            | <---------------------------------------------------+
  58. // +-+--------+-+                                                     |
  59. //   |FirstM  |LastM                                                  |
  60. //   |        +-------------------------------------+                 |
  61. //   |                                              |                 |
  62. //   V                                              V                 |
  63. //  +----------+ Next +----------+ Next       Next +----------+ Next  |
  64. //  |          |----->|          |-----> ... ----->|          |----->-+
  65. //  +- Member -+      +- Member -+                 +- Member -+
  66. //
  67. // The order of members is such that related reference nodes (see below)
  68. // should be contiguous on the member list.
  69. //
  70. // A reference node is a node that encapsulates an access to a register,
  71. // in other words, data flowing into or out of a register. There are two
  72. // major kinds of reference nodes: defs and uses. A def node will contain
  73. // the id of the first reached use, and the id of the first reached def.
  74. // Each def and use will contain the id of the reaching def, and also the
  75. // id of the next reached def (for def nodes) or use (for use nodes).
  76. // The "next node sharing the same reaching def" is denoted as "sibling".
  77. // In summary:
  78. // - Def node contains: reaching def, sibling, first reached def, and first
  79. // reached use.
  80. // - Use node contains: reaching def and sibling.
  81. //
  82. // +-- DefNode --+
  83. // | R2 = ...    | <---+--------------------+
  84. // ++---------+--+     |                    |
  85. //  |Reached  |Reached |                    |
  86. //  |Def      |Use     |                    |
  87. //  |         |        |Reaching            |Reaching
  88. //  |         V        |Def                 |Def
  89. //  |      +-- UseNode --+ Sib  +-- UseNode --+ Sib       Sib
  90. //  |      | ... = R2    |----->| ... = R2    |----> ... ----> 0
  91. //  |      +-------------+      +-------------+
  92. //  V
  93. // +-- DefNode --+ Sib
  94. // | R2 = ...    |----> ...
  95. // ++---------+--+
  96. //  |         |
  97. //  |         |
  98. // ...       ...
  99. //
  100. // To get a full picture, the circular lists connecting blocks within a
  101. // function, instructions within a block, etc. should be superimposed with
  102. // the def-def, def-use links shown above.
  103. // To illustrate this, consider a small example in a pseudo-assembly:
  104. // foo:
  105. //   add r2, r0, r1   ; r2 = r0+r1
  106. //   addi r0, r2, 1   ; r0 = r2+1
  107. //   ret r0           ; return value in r0
  108. //
  109. // The graph (in a format used by the debugging functions) would look like:
  110. //
  111. //   DFG dump:[
  112. //   f1: Function foo
  113. //   b2: === %bb.0 === preds(0), succs(0):
  114. //   p3: phi [d4<r0>(,d12,u9):]
  115. //   p5: phi [d6<r1>(,,u10):]
  116. //   s7: add [d8<r2>(,,u13):, u9<r0>(d4):, u10<r1>(d6):]
  117. //   s11: addi [d12<r0>(d4,,u15):, u13<r2>(d8):]
  118. //   s14: ret [u15<r0>(d12):]
  119. //   ]
  120. //
  121. // The f1, b2, p3, etc. are node ids. The letter is prepended to indicate the
  122. // kind of the node (i.e. f - function, b - basic block, p - phi, s - state-
  123. // ment, d - def, u - use).
  124. // The format of a def node is:
  125. //   dN<R>(rd,d,u):sib,
  126. // where
  127. //   N   - numeric node id,
  128. //   R   - register being defined
  129. //   rd  - reaching def,
  130. //   d   - reached def,
  131. //   u   - reached use,
  132. //   sib - sibling.
  133. // The format of a use node is:
  134. //   uN<R>[!](rd):sib,
  135. // where
  136. //   N   - numeric node id,
  137. //   R   - register being used,
  138. //   rd  - reaching def,
  139. //   sib - sibling.
  140. // Possible annotations (usually preceding the node id):
  141. //   +   - preserving def,
  142. //   ~   - clobbering def,
  143. //   "   - shadow ref (follows the node id),
  144. //   !   - fixed register (appears after register name).
  145. //
  146. // The circular lists are not explicit in the dump.
  147. //
  148. //
  149. // *** Node attributes
  150. //
  151. // NodeBase has a member "Attrs", which is the primary way of determining
  152. // the node's characteristics. The fields in this member decide whether
  153. // the node is a code node or a reference node (i.e. node's "type"), then
  154. // within each type, the "kind" determines what specifically this node
  155. // represents. The remaining bits, "flags", contain additional information
  156. // that is even more detailed than the "kind".
  157. // CodeNode's kinds are:
  158. // - Phi:   Phi node, members are reference nodes.
  159. // - Stmt:  Statement, members are reference nodes.
  160. // - Block: Basic block, members are instruction nodes (i.e. Phi or Stmt).
  161. // - Func:  The whole function. The members are basic block nodes.
  162. // RefNode's kinds are:
  163. // - Use.
  164. // - Def.
  165. //
  166. // Meaning of flags:
  167. // - Preserving: applies only to defs. A preserving def is one that can
  168. //   preserve some of the original bits among those that are included in
  169. //   the register associated with that def. For example, if R0 is a 32-bit
  170. //   register, but a def can only change the lower 16 bits, then it will
  171. //   be marked as preserving.
  172. // - Shadow: a reference that has duplicates holding additional reaching
  173. //   defs (see more below).
  174. // - Clobbering: applied only to defs, indicates that the value generated
  175. //   by this def is unspecified. A typical example would be volatile registers
  176. //   after function calls.
  177. // - Fixed: the register in this def/use cannot be replaced with any other
  178. //   register. A typical case would be a parameter register to a call, or
  179. //   the register with the return value from a function.
  180. // - Undef: the register in this reference the register is assumed to have
  181. //   no pre-existing value, even if it appears to be reached by some def.
  182. //   This is typically used to prevent keeping registers artificially live
  183. //   in cases when they are defined via predicated instructions. For example:
  184. //     r0 = add-if-true cond, r10, r11                (1)
  185. //     r0 = add-if-false cond, r12, r13, implicit r0  (2)
  186. //     ... = r0                                       (3)
  187. //   Before (1), r0 is not intended to be live, and the use of r0 in (3) is
  188. //   not meant to be reached by any def preceding (1). However, since the
  189. //   defs in (1) and (2) are both preserving, these properties alone would
  190. //   imply that the use in (3) may indeed be reached by some prior def.
  191. //   Adding Undef flag to the def in (1) prevents that. The Undef flag
  192. //   may be applied to both defs and uses.
  193. // - Dead: applies only to defs. The value coming out of a "dead" def is
  194. //   assumed to be unused, even if the def appears to be reaching other defs
  195. //   or uses. The motivation for this flag comes from dead defs on function
  196. //   calls: there is no way to determine if such a def is dead without
  197. //   analyzing the target's ABI. Hence the graph should contain this info,
  198. //   as it is unavailable otherwise. On the other hand, a def without any
  199. //   uses on a typical instruction is not the intended target for this flag.
  200. //
  201. // *** Shadow references
  202. //
  203. // It may happen that a super-register can have two (or more) non-overlapping
  204. // sub-registers. When both of these sub-registers are defined and followed
  205. // by a use of the super-register, the use of the super-register will not
  206. // have a unique reaching def: both defs of the sub-registers need to be
  207. // accounted for. In such cases, a duplicate use of the super-register is
  208. // added and it points to the extra reaching def. Both uses are marked with
  209. // a flag "shadow". Example:
  210. // Assume t0 is a super-register of r0 and r1, r0 and r1 do not overlap:
  211. //   set r0, 1        ; r0 = 1
  212. //   set r1, 1        ; r1 = 1
  213. //   addi t1, t0, 1   ; t1 = t0+1
  214. //
  215. // The DFG:
  216. //   s1: set [d2<r0>(,,u9):]
  217. //   s3: set [d4<r1>(,,u10):]
  218. //   s5: addi [d6<t1>(,,):, u7"<t0>(d2):, u8"<t0>(d4):]
  219. //
  220. // The statement s5 has two use nodes for t0: u7" and u9". The quotation
  221. // mark " indicates that the node is a shadow.
  222. //
  223.  
  224. #ifndef LLVM_CODEGEN_RDFGRAPH_H
  225. #define LLVM_CODEGEN_RDFGRAPH_H
  226.  
  227. #include "RDFRegisters.h"
  228. #include "llvm/ADT/SmallVector.h"
  229. #include "llvm/MC/LaneBitmask.h"
  230. #include "llvm/Support/Allocator.h"
  231. #include "llvm/Support/MathExtras.h"
  232. #include <cassert>
  233. #include <cstdint>
  234. #include <cstring>
  235. #include <map>
  236. #include <memory>
  237. #include <set>
  238. #include <unordered_map>
  239. #include <utility>
  240. #include <vector>
  241.  
  242. // RDF uses uint32_t to refer to registers. This is to ensure that the type
  243. // size remains specific. In other places, registers are often stored using
  244. // unsigned.
  245. static_assert(sizeof(uint32_t) == sizeof(unsigned), "Those should be equal");
  246.  
  247. namespace llvm {
  248.  
  249. class MachineBasicBlock;
  250. class MachineDominanceFrontier;
  251. class MachineDominatorTree;
  252. class MachineFunction;
  253. class MachineInstr;
  254. class MachineOperand;
  255. class raw_ostream;
  256. class TargetInstrInfo;
  257. class TargetRegisterInfo;
  258.  
  259. namespace rdf {
  260.  
  261.   using NodeId = uint32_t;
  262.  
  263.   struct DataFlowGraph;
  264.  
  265.   struct NodeAttrs {
  266.     enum : uint16_t {
  267.       None          = 0x0000,   // Nothing
  268.  
  269.       // Types: 2 bits
  270.       TypeMask      = 0x0003,
  271.       Code          = 0x0001,   // 01, Container
  272.       Ref           = 0x0002,   // 10, Reference
  273.  
  274.       // Kind: 3 bits
  275.       KindMask      = 0x0007 << 2,
  276.       Def           = 0x0001 << 2,  // 001
  277.       Use           = 0x0002 << 2,  // 010
  278.       Phi           = 0x0003 << 2,  // 011
  279.       Stmt          = 0x0004 << 2,  // 100
  280.       Block         = 0x0005 << 2,  // 101
  281.       Func          = 0x0006 << 2,  // 110
  282.  
  283.       // Flags: 7 bits for now
  284.       FlagMask      = 0x007F << 5,
  285.       Shadow        = 0x0001 << 5,  // 0000001, Has extra reaching defs.
  286.       Clobbering    = 0x0002 << 5,  // 0000010, Produces unspecified values.
  287.       PhiRef        = 0x0004 << 5,  // 0000100, Member of PhiNode.
  288.       Preserving    = 0x0008 << 5,  // 0001000, Def can keep original bits.
  289.       Fixed         = 0x0010 << 5,  // 0010000, Fixed register.
  290.       Undef         = 0x0020 << 5,  // 0100000, Has no pre-existing value.
  291.       Dead          = 0x0040 << 5,  // 1000000, Does not define a value.
  292.     };
  293.  
  294.     static uint16_t type(uint16_t T)  { return T & TypeMask; }
  295.     static uint16_t kind(uint16_t T)  { return T & KindMask; }
  296.     static uint16_t flags(uint16_t T) { return T & FlagMask; }
  297.  
  298.     static uint16_t set_type(uint16_t A, uint16_t T) {
  299.       return (A & ~TypeMask) | T;
  300.     }
  301.  
  302.     static uint16_t set_kind(uint16_t A, uint16_t K) {
  303.       return (A & ~KindMask) | K;
  304.     }
  305.  
  306.     static uint16_t set_flags(uint16_t A, uint16_t F) {
  307.       return (A & ~FlagMask) | F;
  308.     }
  309.  
  310.     // Test if A contains B.
  311.     static bool contains(uint16_t A, uint16_t B) {
  312.       if (type(A) != Code)
  313.         return false;
  314.       uint16_t KB = kind(B);
  315.       switch (kind(A)) {
  316.         case Func:
  317.           return KB == Block;
  318.         case Block:
  319.           return KB == Phi || KB == Stmt;
  320.         case Phi:
  321.         case Stmt:
  322.           return type(B) == Ref;
  323.       }
  324.       return false;
  325.     }
  326.   };
  327.  
  328.   struct BuildOptions {
  329.     enum : unsigned {
  330.       None          = 0x00,
  331.       KeepDeadPhis  = 0x01,   // Do not remove dead phis during build.
  332.     };
  333.   };
  334.  
  335.   template <typename T> struct NodeAddr {
  336.     NodeAddr() = default;
  337.     NodeAddr(T A, NodeId I) : Addr(A), Id(I) {}
  338.  
  339.     // Type cast (casting constructor). The reason for having this class
  340.     // instead of std::pair.
  341.     template <typename S> NodeAddr(const NodeAddr<S> &NA)
  342.       : Addr(static_cast<T>(NA.Addr)), Id(NA.Id) {}
  343.  
  344.     bool operator== (const NodeAddr<T> &NA) const {
  345.       assert((Addr == NA.Addr) == (Id == NA.Id));
  346.       return Addr == NA.Addr;
  347.     }
  348.     bool operator!= (const NodeAddr<T> &NA) const {
  349.       return !operator==(NA);
  350.     }
  351.  
  352.     T Addr = nullptr;
  353.     NodeId Id = 0;
  354.   };
  355.  
  356.   struct NodeBase;
  357.  
  358.   // Fast memory allocation and translation between node id and node address.
  359.   // This is really the same idea as the one underlying the "bump pointer
  360.   // allocator", the difference being in the translation. A node id is
  361.   // composed of two components: the index of the block in which it was
  362.   // allocated, and the index within the block. With the default settings,
  363.   // where the number of nodes per block is 4096, the node id (minus 1) is:
  364.   //
  365.   // bit position:                11             0
  366.   // +----------------------------+--------------+
  367.   // | Index of the block         |Index in block|
  368.   // +----------------------------+--------------+
  369.   //
  370.   // The actual node id is the above plus 1, to avoid creating a node id of 0.
  371.   //
  372.   // This method significantly improved the build time, compared to using maps
  373.   // (std::unordered_map or DenseMap) to translate between pointers and ids.
  374.   struct NodeAllocator {
  375.     // Amount of storage for a single node.
  376.     enum { NodeMemSize = 32 };
  377.  
  378.     NodeAllocator(uint32_t NPB = 4096)
  379.         : NodesPerBlock(NPB), BitsPerIndex(Log2_32(NPB)),
  380.           IndexMask((1 << BitsPerIndex)-1) {
  381.       assert(isPowerOf2_32(NPB));
  382.     }
  383.  
  384.     NodeBase *ptr(NodeId N) const {
  385.       uint32_t N1 = N-1;
  386.       uint32_t BlockN = N1 >> BitsPerIndex;
  387.       uint32_t Offset = (N1 & IndexMask) * NodeMemSize;
  388.       return reinterpret_cast<NodeBase*>(Blocks[BlockN]+Offset);
  389.     }
  390.  
  391.     NodeId id(const NodeBase *P) const;
  392.     NodeAddr<NodeBase*> New();
  393.     void clear();
  394.  
  395.   private:
  396.     void startNewBlock();
  397.     bool needNewBlock();
  398.  
  399.     uint32_t makeId(uint32_t Block, uint32_t Index) const {
  400.       // Add 1 to the id, to avoid the id of 0, which is treated as "null".
  401.       return ((Block << BitsPerIndex) | Index) + 1;
  402.     }
  403.  
  404.     const uint32_t NodesPerBlock;
  405.     const uint32_t BitsPerIndex;
  406.     const uint32_t IndexMask;
  407.     char *ActiveEnd = nullptr;
  408.     std::vector<char*> Blocks;
  409.     using AllocatorTy = BumpPtrAllocatorImpl<MallocAllocator, 65536>;
  410.     AllocatorTy MemPool;
  411.   };
  412.  
  413.   using RegisterSet = std::set<RegisterRef>;
  414.  
  415.   struct TargetOperandInfo {
  416.     TargetOperandInfo(const TargetInstrInfo &tii) : TII(tii) {}
  417.     virtual ~TargetOperandInfo() = default;
  418.  
  419.     virtual bool isPreserving(const MachineInstr &In, unsigned OpNum) const;
  420.     virtual bool isClobbering(const MachineInstr &In, unsigned OpNum) const;
  421.     virtual bool isFixedReg(const MachineInstr &In, unsigned OpNum) const;
  422.  
  423.     const TargetInstrInfo &TII;
  424.   };
  425.  
  426.   // Packed register reference. Only used for storage.
  427.   struct PackedRegisterRef {
  428.     RegisterId Reg;
  429.     uint32_t MaskId;
  430.   };
  431.  
  432.   struct LaneMaskIndex : private IndexedSet<LaneBitmask> {
  433.     LaneMaskIndex() = default;
  434.  
  435.     LaneBitmask getLaneMaskForIndex(uint32_t K) const {
  436.       return K == 0 ? LaneBitmask::getAll() : get(K);
  437.     }
  438.  
  439.     uint32_t getIndexForLaneMask(LaneBitmask LM) {
  440.       assert(LM.any());
  441.       return LM.all() ? 0 : insert(LM);
  442.     }
  443.  
  444.     uint32_t getIndexForLaneMask(LaneBitmask LM) const {
  445.       assert(LM.any());
  446.       return LM.all() ? 0 : find(LM);
  447.     }
  448.   };
  449.  
  450.   struct NodeBase {
  451.   public:
  452.     // Make sure this is a POD.
  453.     NodeBase() = default;
  454.  
  455.     uint16_t getType()  const { return NodeAttrs::type(Attrs); }
  456.     uint16_t getKind()  const { return NodeAttrs::kind(Attrs); }
  457.     uint16_t getFlags() const { return NodeAttrs::flags(Attrs); }
  458.     NodeId   getNext()  const { return Next; }
  459.  
  460.     uint16_t getAttrs() const { return Attrs; }
  461.     void setAttrs(uint16_t A) { Attrs = A; }
  462.     void setFlags(uint16_t F) { setAttrs(NodeAttrs::set_flags(getAttrs(), F)); }
  463.  
  464.     // Insert node NA after "this" in the circular chain.
  465.     void append(NodeAddr<NodeBase*> NA);
  466.  
  467.     // Initialize all members to 0.
  468.     void init() { memset(this, 0, sizeof *this); }
  469.  
  470.     void setNext(NodeId N) { Next = N; }
  471.  
  472.   protected:
  473.     uint16_t Attrs;
  474.     uint16_t Reserved;
  475.     NodeId Next;                // Id of the next node in the circular chain.
  476.     // Definitions of nested types. Using anonymous nested structs would make
  477.     // this class definition clearer, but unnamed structs are not a part of
  478.     // the standard.
  479.     struct Def_struct  {
  480.       NodeId DD, DU;          // Ids of the first reached def and use.
  481.     };
  482.     struct PhiU_struct  {
  483.       NodeId PredB;           // Id of the predecessor block for a phi use.
  484.     };
  485.     struct Code_struct {
  486.       void *CP;               // Pointer to the actual code.
  487.       NodeId FirstM, LastM;   // Id of the first member and last.
  488.     };
  489.     struct Ref_struct {
  490.       NodeId RD, Sib;         // Ids of the reaching def and the sibling.
  491.       union {
  492.         Def_struct Def;
  493.         PhiU_struct PhiU;
  494.       };
  495.       union {
  496.         MachineOperand *Op;   // Non-phi refs point to a machine operand.
  497.         PackedRegisterRef PR; // Phi refs store register info directly.
  498.       };
  499.     };
  500.  
  501.     // The actual payload.
  502.     union {
  503.       Ref_struct Ref;
  504.       Code_struct Code;
  505.     };
  506.   };
  507.   // The allocator allocates chunks of 32 bytes for each node. The fact that
  508.   // each node takes 32 bytes in memory is used for fast translation between
  509.   // the node id and the node address.
  510.   static_assert(sizeof(NodeBase) <= NodeAllocator::NodeMemSize,
  511.         "NodeBase must be at most NodeAllocator::NodeMemSize bytes");
  512.  
  513.   using NodeList = SmallVector<NodeAddr<NodeBase *>, 4>;
  514.   using NodeSet = std::set<NodeId>;
  515.  
  516.   struct RefNode : public NodeBase {
  517.     RefNode() = default;
  518.  
  519.     RegisterRef getRegRef(const DataFlowGraph &G) const;
  520.  
  521.     MachineOperand &getOp() {
  522.       assert(!(getFlags() & NodeAttrs::PhiRef));
  523.       return *Ref.Op;
  524.     }
  525.  
  526.     void setRegRef(RegisterRef RR, DataFlowGraph &G);
  527.     void setRegRef(MachineOperand *Op, DataFlowGraph &G);
  528.  
  529.     NodeId getReachingDef() const {
  530.       return Ref.RD;
  531.     }
  532.     void setReachingDef(NodeId RD) {
  533.       Ref.RD = RD;
  534.     }
  535.  
  536.     NodeId getSibling() const {
  537.       return Ref.Sib;
  538.     }
  539.     void setSibling(NodeId Sib) {
  540.       Ref.Sib = Sib;
  541.     }
  542.  
  543.     bool isUse() const {
  544.       assert(getType() == NodeAttrs::Ref);
  545.       return getKind() == NodeAttrs::Use;
  546.     }
  547.  
  548.     bool isDef() const {
  549.       assert(getType() == NodeAttrs::Ref);
  550.       return getKind() == NodeAttrs::Def;
  551.     }
  552.  
  553.     template <typename Predicate>
  554.     NodeAddr<RefNode*> getNextRef(RegisterRef RR, Predicate P, bool NextOnly,
  555.         const DataFlowGraph &G);
  556.     NodeAddr<NodeBase*> getOwner(const DataFlowGraph &G);
  557.   };
  558.  
  559.   struct DefNode : public RefNode {
  560.     NodeId getReachedDef() const {
  561.       return Ref.Def.DD;
  562.     }
  563.     void setReachedDef(NodeId D) {
  564.       Ref.Def.DD = D;
  565.     }
  566.     NodeId getReachedUse() const {
  567.       return Ref.Def.DU;
  568.     }
  569.     void setReachedUse(NodeId U) {
  570.       Ref.Def.DU = U;
  571.     }
  572.  
  573.     void linkToDef(NodeId Self, NodeAddr<DefNode*> DA);
  574.   };
  575.  
  576.   struct UseNode : public RefNode {
  577.     void linkToDef(NodeId Self, NodeAddr<DefNode*> DA);
  578.   };
  579.  
  580.   struct PhiUseNode : public UseNode {
  581.     NodeId getPredecessor() const {
  582.       assert(getFlags() & NodeAttrs::PhiRef);
  583.       return Ref.PhiU.PredB;
  584.     }
  585.     void setPredecessor(NodeId B) {
  586.       assert(getFlags() & NodeAttrs::PhiRef);
  587.       Ref.PhiU.PredB = B;
  588.     }
  589.   };
  590.  
  591.   struct CodeNode : public NodeBase {
  592.     template <typename T> T getCode() const {
  593.       return static_cast<T>(Code.CP);
  594.     }
  595.     void setCode(void *C) {
  596.       Code.CP = C;
  597.     }
  598.  
  599.     NodeAddr<NodeBase*> getFirstMember(const DataFlowGraph &G) const;
  600.     NodeAddr<NodeBase*> getLastMember(const DataFlowGraph &G) const;
  601.     void addMember(NodeAddr<NodeBase*> NA, const DataFlowGraph &G);
  602.     void addMemberAfter(NodeAddr<NodeBase*> MA, NodeAddr<NodeBase*> NA,
  603.         const DataFlowGraph &G);
  604.     void removeMember(NodeAddr<NodeBase*> NA, const DataFlowGraph &G);
  605.  
  606.     NodeList members(const DataFlowGraph &G) const;
  607.     template <typename Predicate>
  608.     NodeList members_if(Predicate P, const DataFlowGraph &G) const;
  609.   };
  610.  
  611.   struct InstrNode : public CodeNode {
  612.     NodeAddr<NodeBase*> getOwner(const DataFlowGraph &G);
  613.   };
  614.  
  615.   struct PhiNode : public InstrNode {
  616.     MachineInstr *getCode() const {
  617.       return nullptr;
  618.     }
  619.   };
  620.  
  621.   struct StmtNode : public InstrNode {
  622.     MachineInstr *getCode() const {
  623.       return CodeNode::getCode<MachineInstr*>();
  624.     }
  625.   };
  626.  
  627.   struct BlockNode : public CodeNode {
  628.     MachineBasicBlock *getCode() const {
  629.       return CodeNode::getCode<MachineBasicBlock*>();
  630.     }
  631.  
  632.     void addPhi(NodeAddr<PhiNode*> PA, const DataFlowGraph &G);
  633.   };
  634.  
  635.   struct FuncNode : public CodeNode {
  636.     MachineFunction *getCode() const {
  637.       return CodeNode::getCode<MachineFunction*>();
  638.     }
  639.  
  640.     NodeAddr<BlockNode*> findBlock(const MachineBasicBlock *BB,
  641.         const DataFlowGraph &G) const;
  642.     NodeAddr<BlockNode*> getEntryBlock(const DataFlowGraph &G);
  643.   };
  644.  
  645.   struct DataFlowGraph {
  646.     DataFlowGraph(MachineFunction &mf, const TargetInstrInfo &tii,
  647.         const TargetRegisterInfo &tri, const MachineDominatorTree &mdt,
  648.         const MachineDominanceFrontier &mdf);
  649.     DataFlowGraph(MachineFunction &mf, const TargetInstrInfo &tii,
  650.         const TargetRegisterInfo &tri, const MachineDominatorTree &mdt,
  651.         const MachineDominanceFrontier &mdf, const TargetOperandInfo &toi);
  652.  
  653.     NodeBase *ptr(NodeId N) const;
  654.     template <typename T> T ptr(NodeId N) const {
  655.       return static_cast<T>(ptr(N));
  656.     }
  657.  
  658.     NodeId id(const NodeBase *P) const;
  659.  
  660.     template <typename T> NodeAddr<T> addr(NodeId N) const {
  661.       return { ptr<T>(N), N };
  662.     }
  663.  
  664.     NodeAddr<FuncNode*> getFunc() const { return Func; }
  665.     MachineFunction &getMF() const { return MF; }
  666.     const TargetInstrInfo &getTII() const { return TII; }
  667.     const TargetRegisterInfo &getTRI() const { return TRI; }
  668.     const PhysicalRegisterInfo &getPRI() const { return PRI; }
  669.     const MachineDominatorTree &getDT() const { return MDT; }
  670.     const MachineDominanceFrontier &getDF() const { return MDF; }
  671.     const RegisterAggr &getLiveIns() const { return LiveIns; }
  672.  
  673.     struct DefStack {
  674.       DefStack() = default;
  675.  
  676.       bool empty() const { return Stack.empty() || top() == bottom(); }
  677.  
  678.     private:
  679.       using value_type = NodeAddr<DefNode *>;
  680.       struct Iterator {
  681.         using value_type = DefStack::value_type;
  682.  
  683.         Iterator &up() { Pos = DS.nextUp(Pos); return *this; }
  684.         Iterator &down() { Pos = DS.nextDown(Pos); return *this; }
  685.  
  686.         value_type operator*() const {
  687.           assert(Pos >= 1);
  688.           return DS.Stack[Pos-1];
  689.         }
  690.         const value_type *operator->() const {
  691.           assert(Pos >= 1);
  692.           return &DS.Stack[Pos-1];
  693.         }
  694.         bool operator==(const Iterator &It) const { return Pos == It.Pos; }
  695.         bool operator!=(const Iterator &It) const { return Pos != It.Pos; }
  696.  
  697.       private:
  698.         friend struct DefStack;
  699.  
  700.         Iterator(const DefStack &S, bool Top);
  701.  
  702.         // Pos-1 is the index in the StorageType object that corresponds to
  703.         // the top of the DefStack.
  704.         const DefStack &DS;
  705.         unsigned Pos;
  706.       };
  707.  
  708.     public:
  709.       using iterator = Iterator;
  710.  
  711.       iterator top() const { return Iterator(*this, true); }
  712.       iterator bottom() const { return Iterator(*this, false); }
  713.       unsigned size() const;
  714.  
  715.       void push(NodeAddr<DefNode*> DA) { Stack.push_back(DA); }
  716.       void pop();
  717.       void start_block(NodeId N);
  718.       void clear_block(NodeId N);
  719.  
  720.     private:
  721.       friend struct Iterator;
  722.  
  723.       using StorageType = std::vector<value_type>;
  724.  
  725.       bool isDelimiter(const StorageType::value_type &P, NodeId N = 0) const {
  726.         return (P.Addr == nullptr) && (N == 0 || P.Id == N);
  727.       }
  728.  
  729.       unsigned nextUp(unsigned P) const;
  730.       unsigned nextDown(unsigned P) const;
  731.  
  732.       StorageType Stack;
  733.     };
  734.  
  735.     // Make this std::unordered_map for speed of accessing elements.
  736.     // Map: Register (physical or virtual) -> DefStack
  737.     using DefStackMap = std::unordered_map<RegisterId, DefStack>;
  738.  
  739.     void build(unsigned Options = BuildOptions::None);
  740.     void pushAllDefs(NodeAddr<InstrNode*> IA, DefStackMap &DM);
  741.     void markBlock(NodeId B, DefStackMap &DefM);
  742.     void releaseBlock(NodeId B, DefStackMap &DefM);
  743.  
  744.     PackedRegisterRef pack(RegisterRef RR) {
  745.       return { RR.Reg, LMI.getIndexForLaneMask(RR.Mask) };
  746.     }
  747.     PackedRegisterRef pack(RegisterRef RR) const {
  748.       return { RR.Reg, LMI.getIndexForLaneMask(RR.Mask) };
  749.     }
  750.     RegisterRef unpack(PackedRegisterRef PR) const {
  751.       return RegisterRef(PR.Reg, LMI.getLaneMaskForIndex(PR.MaskId));
  752.     }
  753.  
  754.     RegisterRef makeRegRef(unsigned Reg, unsigned Sub) const;
  755.     RegisterRef makeRegRef(const MachineOperand &Op) const;
  756.  
  757.     NodeAddr<RefNode*> getNextRelated(NodeAddr<InstrNode*> IA,
  758.         NodeAddr<RefNode*> RA) const;
  759.     NodeAddr<RefNode*> getNextShadow(NodeAddr<InstrNode*> IA,
  760.         NodeAddr<RefNode*> RA, bool Create);
  761.     NodeAddr<RefNode*> getNextShadow(NodeAddr<InstrNode*> IA,
  762.         NodeAddr<RefNode*> RA) const;
  763.  
  764.     NodeList getRelatedRefs(NodeAddr<InstrNode*> IA,
  765.         NodeAddr<RefNode*> RA) const;
  766.  
  767.     NodeAddr<BlockNode*> findBlock(MachineBasicBlock *BB) const {
  768.       return BlockNodes.at(BB);
  769.     }
  770.  
  771.     void unlinkUse(NodeAddr<UseNode*> UA, bool RemoveFromOwner) {
  772.       unlinkUseDF(UA);
  773.       if (RemoveFromOwner)
  774.         removeFromOwner(UA);
  775.     }
  776.  
  777.     void unlinkDef(NodeAddr<DefNode*> DA, bool RemoveFromOwner) {
  778.       unlinkDefDF(DA);
  779.       if (RemoveFromOwner)
  780.         removeFromOwner(DA);
  781.     }
  782.  
  783.     // Some useful filters.
  784.     template <uint16_t Kind>
  785.     static bool IsRef(const NodeAddr<NodeBase*> BA) {
  786.       return BA.Addr->getType() == NodeAttrs::Ref &&
  787.              BA.Addr->getKind() == Kind;
  788.     }
  789.  
  790.     template <uint16_t Kind>
  791.     static bool IsCode(const NodeAddr<NodeBase*> BA) {
  792.       return BA.Addr->getType() == NodeAttrs::Code &&
  793.              BA.Addr->getKind() == Kind;
  794.     }
  795.  
  796.     static bool IsDef(const NodeAddr<NodeBase*> BA) {
  797.       return BA.Addr->getType() == NodeAttrs::Ref &&
  798.              BA.Addr->getKind() == NodeAttrs::Def;
  799.     }
  800.  
  801.     static bool IsUse(const NodeAddr<NodeBase*> BA) {
  802.       return BA.Addr->getType() == NodeAttrs::Ref &&
  803.              BA.Addr->getKind() == NodeAttrs::Use;
  804.     }
  805.  
  806.     static bool IsPhi(const NodeAddr<NodeBase*> BA) {
  807.       return BA.Addr->getType() == NodeAttrs::Code &&
  808.              BA.Addr->getKind() == NodeAttrs::Phi;
  809.     }
  810.  
  811.     static bool IsPreservingDef(const NodeAddr<DefNode*> DA) {
  812.       uint16_t Flags = DA.Addr->getFlags();
  813.       return (Flags & NodeAttrs::Preserving) && !(Flags & NodeAttrs::Undef);
  814.     }
  815.  
  816.   private:
  817.     void reset();
  818.  
  819.     RegisterSet getLandingPadLiveIns() const;
  820.  
  821.     NodeAddr<NodeBase*> newNode(uint16_t Attrs);
  822.     NodeAddr<NodeBase*> cloneNode(const NodeAddr<NodeBase*> B);
  823.     NodeAddr<UseNode*> newUse(NodeAddr<InstrNode*> Owner,
  824.         MachineOperand &Op, uint16_t Flags = NodeAttrs::None);
  825.     NodeAddr<PhiUseNode*> newPhiUse(NodeAddr<PhiNode*> Owner,
  826.         RegisterRef RR, NodeAddr<BlockNode*> PredB,
  827.         uint16_t Flags = NodeAttrs::PhiRef);
  828.     NodeAddr<DefNode*> newDef(NodeAddr<InstrNode*> Owner,
  829.         MachineOperand &Op, uint16_t Flags = NodeAttrs::None);
  830.     NodeAddr<DefNode*> newDef(NodeAddr<InstrNode*> Owner,
  831.         RegisterRef RR, uint16_t Flags = NodeAttrs::PhiRef);
  832.     NodeAddr<PhiNode*> newPhi(NodeAddr<BlockNode*> Owner);
  833.     NodeAddr<StmtNode*> newStmt(NodeAddr<BlockNode*> Owner,
  834.         MachineInstr *MI);
  835.     NodeAddr<BlockNode*> newBlock(NodeAddr<FuncNode*> Owner,
  836.         MachineBasicBlock *BB);
  837.     NodeAddr<FuncNode*> newFunc(MachineFunction *MF);
  838.  
  839.     template <typename Predicate>
  840.     std::pair<NodeAddr<RefNode*>,NodeAddr<RefNode*>>
  841.     locateNextRef(NodeAddr<InstrNode*> IA, NodeAddr<RefNode*> RA,
  842.         Predicate P) const;
  843.  
  844.     using BlockRefsMap = std::map<NodeId, RegisterSet>;
  845.  
  846.     void buildStmt(NodeAddr<BlockNode*> BA, MachineInstr &In);
  847.     void recordDefsForDF(BlockRefsMap &PhiM, NodeAddr<BlockNode*> BA);
  848.     void buildPhis(BlockRefsMap &PhiM, RegisterSet &AllRefs,
  849.         NodeAddr<BlockNode*> BA);
  850.     void removeUnusedPhis();
  851.  
  852.     void pushClobbers(NodeAddr<InstrNode*> IA, DefStackMap &DM);
  853.     void pushDefs(NodeAddr<InstrNode*> IA, DefStackMap &DM);
  854.     template <typename T> void linkRefUp(NodeAddr<InstrNode*> IA,
  855.         NodeAddr<T> TA, DefStack &DS);
  856.     template <typename Predicate> void linkStmtRefs(DefStackMap &DefM,
  857.         NodeAddr<StmtNode*> SA, Predicate P);
  858.     void linkBlockRefs(DefStackMap &DefM, NodeAddr<BlockNode*> BA);
  859.  
  860.     void unlinkUseDF(NodeAddr<UseNode*> UA);
  861.     void unlinkDefDF(NodeAddr<DefNode*> DA);
  862.  
  863.     void removeFromOwner(NodeAddr<RefNode*> RA) {
  864.       NodeAddr<InstrNode*> IA = RA.Addr->getOwner(*this);
  865.       IA.Addr->removeMember(RA, *this);
  866.     }
  867.  
  868.     // Default TOI object, if not given in the constructor.
  869.     std::unique_ptr<TargetOperandInfo> DefaultTOI;
  870.  
  871.     MachineFunction &MF;
  872.     const TargetInstrInfo &TII;
  873.     const TargetRegisterInfo &TRI;
  874.     const PhysicalRegisterInfo PRI;
  875.     const MachineDominatorTree &MDT;
  876.     const MachineDominanceFrontier &MDF;
  877.     const TargetOperandInfo &TOI;
  878.  
  879.     RegisterAggr LiveIns;
  880.     NodeAddr<FuncNode*> Func;
  881.     NodeAllocator Memory;
  882.     // Local map:  MachineBasicBlock -> NodeAddr<BlockNode*>
  883.     std::map<MachineBasicBlock*,NodeAddr<BlockNode*>> BlockNodes;
  884.     // Lane mask map.
  885.     LaneMaskIndex LMI;
  886.   };  // struct DataFlowGraph
  887.  
  888.   template <typename Predicate>
  889.   NodeAddr<RefNode*> RefNode::getNextRef(RegisterRef RR, Predicate P,
  890.         bool NextOnly, const DataFlowGraph &G) {
  891.     // Get the "Next" reference in the circular list that references RR and
  892.     // satisfies predicate "Pred".
  893.     auto NA = G.addr<NodeBase*>(getNext());
  894.  
  895.     while (NA.Addr != this) {
  896.       if (NA.Addr->getType() == NodeAttrs::Ref) {
  897.         NodeAddr<RefNode*> RA = NA;
  898.         if (RA.Addr->getRegRef(G) == RR && P(NA))
  899.           return NA;
  900.         if (NextOnly)
  901.           break;
  902.         NA = G.addr<NodeBase*>(NA.Addr->getNext());
  903.       } else {
  904.         // We've hit the beginning of the chain.
  905.         assert(NA.Addr->getType() == NodeAttrs::Code);
  906.         NodeAddr<CodeNode*> CA = NA;
  907.         NA = CA.Addr->getFirstMember(G);
  908.       }
  909.     }
  910.     // Return the equivalent of "nullptr" if such a node was not found.
  911.     return NodeAddr<RefNode*>();
  912.   }
  913.  
  914.   template <typename Predicate>
  915.   NodeList CodeNode::members_if(Predicate P, const DataFlowGraph &G) const {
  916.     NodeList MM;
  917.     auto M = getFirstMember(G);
  918.     if (M.Id == 0)
  919.       return MM;
  920.  
  921.     while (M.Addr != this) {
  922.       if (P(M))
  923.         MM.push_back(M);
  924.       M = G.addr<NodeBase*>(M.Addr->getNext());
  925.     }
  926.     return MM;
  927.   }
  928.  
  929.   template <typename T>
  930.   struct Print {
  931.     Print(const T &x, const DataFlowGraph &g) : Obj(x), G(g) {}
  932.  
  933.     const T &Obj;
  934.     const DataFlowGraph &G;
  935.   };
  936.  
  937.   template <typename T> Print(const T &, const DataFlowGraph &) -> Print<T>;
  938.  
  939.   template <typename T>
  940.   struct PrintNode : Print<NodeAddr<T>> {
  941.     PrintNode(const NodeAddr<T> &x, const DataFlowGraph &g)
  942.       : Print<NodeAddr<T>>(x, g) {}
  943.   };
  944.  
  945.   raw_ostream &operator<<(raw_ostream &OS, const Print<RegisterRef> &P);
  946.   raw_ostream &operator<<(raw_ostream &OS, const Print<NodeId> &P);
  947.   raw_ostream &operator<<(raw_ostream &OS, const Print<NodeAddr<DefNode *>> &P);
  948.   raw_ostream &operator<<(raw_ostream &OS, const Print<NodeAddr<UseNode *>> &P);
  949.   raw_ostream &operator<<(raw_ostream &OS,
  950.                           const Print<NodeAddr<PhiUseNode *>> &P);
  951.   raw_ostream &operator<<(raw_ostream &OS, const Print<NodeAddr<RefNode *>> &P);
  952.   raw_ostream &operator<<(raw_ostream &OS, const Print<NodeList> &P);
  953.   raw_ostream &operator<<(raw_ostream &OS, const Print<NodeSet> &P);
  954.   raw_ostream &operator<<(raw_ostream &OS, const Print<NodeAddr<PhiNode *>> &P);
  955.   raw_ostream &operator<<(raw_ostream &OS,
  956.                           const Print<NodeAddr<StmtNode *>> &P);
  957.   raw_ostream &operator<<(raw_ostream &OS,
  958.                           const Print<NodeAddr<InstrNode *>> &P);
  959.   raw_ostream &operator<<(raw_ostream &OS,
  960.                           const Print<NodeAddr<BlockNode *>> &P);
  961.   raw_ostream &operator<<(raw_ostream &OS,
  962.                           const Print<NodeAddr<FuncNode *>> &P);
  963.   raw_ostream &operator<<(raw_ostream &OS, const Print<RegisterSet> &P);
  964.   raw_ostream &operator<<(raw_ostream &OS, const Print<RegisterAggr> &P);
  965.   raw_ostream &operator<<(raw_ostream &OS,
  966.                           const Print<DataFlowGraph::DefStack> &P);
  967.  
  968. } // end namespace rdf
  969.  
  970. } // end namespace llvm
  971.  
  972. #endif // LLVM_CODEGEN_RDFGRAPH_H
  973.