lib/Target/Hexagon/RDFGraph.h

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