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/ArrayRef.h" 229 #include "llvm/ADT/SmallVector.h" 230 #include "llvm/MC/LaneBitmask.h" 231 #include "llvm/Support/Allocator.h" 232 #include "llvm/Support/MathExtras.h" 233 #include <cassert> 234 #include <cstdint> 235 #include <cstring> 236 #include <map> 237 #include <memory> 238 #include <set> 239 #include <unordered_map> 240 #include <utility> 241 #include <vector> 242 243 // RDF uses uint32_t to refer to registers. This is to ensure that the type 244 // size remains specific. In other places, registers are often stored using 245 // unsigned. 246 static_assert(sizeof(uint32_t) == sizeof(unsigned), "Those should be equal"); 247 248 namespace llvm { 249 250 class MachineBasicBlock; 251 class MachineDominanceFrontier; 252 class MachineDominatorTree; 253 class MachineFunction; 254 class MachineInstr; 255 class MachineOperand; 256 class raw_ostream; 257 class TargetInstrInfo; 258 class TargetRegisterInfo; 259 260 namespace rdf { 261 262 using NodeId = uint32_t; 263 264 struct DataFlowGraph; 265 266 struct NodeAttrs { 267 // clang-format off 268 enum : uint16_t { 269 None = 0x0000, // Nothing 270 271 // Types: 2 bits 272 TypeMask = 0x0003, 273 Code = 0x0001, // 01, Container 274 Ref = 0x0002, // 10, Reference 275 276 // Kind: 3 bits 277 KindMask = 0x0007 << 2, 278 Def = 0x0001 << 2, // 001 279 Use = 0x0002 << 2, // 010 280 Phi = 0x0003 << 2, // 011 281 Stmt = 0x0004 << 2, // 100 282 Block = 0x0005 << 2, // 101 283 Func = 0x0006 << 2, // 110 284 285 // Flags: 7 bits for now 286 FlagMask = 0x007F << 5, 287 Shadow = 0x0001 << 5, // 0000001, Has extra reaching defs. 288 Clobbering = 0x0002 << 5, // 0000010, Produces unspecified values. 289 PhiRef = 0x0004 << 5, // 0000100, Member of PhiNode. 290 Preserving = 0x0008 << 5, // 0001000, Def can keep original bits. 291 Fixed = 0x0010 << 5, // 0010000, Fixed register. 292 Undef = 0x0020 << 5, // 0100000, Has no pre-existing value. 293 Dead = 0x0040 << 5, // 1000000, Does not define a value. 294 }; 295 // clang-format on 296 297 static uint16_t type(uint16_t T) { // 298 return T & TypeMask; 299 } 300 static uint16_t kind(uint16_t T) { // 301 return T & KindMask; 302 } 303 static uint16_t flags(uint16_t T) { // 304 return T & FlagMask; 305 } 306 static uint16_t set_type(uint16_t A, uint16_t T) { 307 return (A & ~TypeMask) | T; 308 } 309 310 static uint16_t set_kind(uint16_t A, uint16_t K) { 311 return (A & ~KindMask) | K; 312 } 313 314 static uint16_t set_flags(uint16_t A, uint16_t F) { 315 return (A & ~FlagMask) | F; 316 } 317 318 // Test if A contains B. 319 static bool contains(uint16_t A, uint16_t B) { 320 if (type(A) != Code) 321 return false; 322 uint16_t KB = kind(B); 323 switch (kind(A)) { 324 case Func: 325 return KB == Block; 326 case Block: 327 return KB == Phi || KB == Stmt; 328 case Phi: 329 case Stmt: 330 return type(B) == Ref; 331 } 332 return false; 333 } 334 }; 335 336 struct BuildOptions { 337 enum : unsigned { 338 None = 0x00, 339 KeepDeadPhis = 0x01, // Do not remove dead phis during build. 340 OmitReserved = 0x02, // Do not track reserved registers. 341 }; 342 }; 343 344 template <typename T> struct NodeAddr { 345 NodeAddr() = default; 346 NodeAddr(T A, NodeId I) : Addr(A), Id(I) {} 347 348 // Type cast (casting constructor). The reason for having this class 349 // instead of std::pair. 350 template <typename S> 351 NodeAddr(const NodeAddr<S> &NA) : Addr(static_cast<T>(NA.Addr)), Id(NA.Id) {} 352 353 bool operator==(const NodeAddr<T> &NA) const { 354 assert((Addr == NA.Addr) == (Id == NA.Id)); 355 return Addr == NA.Addr; 356 } 357 bool operator!=(const NodeAddr<T> &NA) const { // 358 return !operator==(NA); 359 } 360 361 T Addr = nullptr; 362 NodeId Id = 0; 363 }; 364 365 struct NodeBase; 366 367 struct RefNode; 368 struct DefNode; 369 struct UseNode; 370 struct PhiUseNode; 371 372 struct CodeNode; 373 struct InstrNode; 374 struct PhiNode; 375 struct StmtNode; 376 struct BlockNode; 377 struct FuncNode; 378 379 // Use these short names with rdf:: qualification to avoid conflicts with 380 // preexisting names. Do not use 'using namespace rdf'. 381 using Node = NodeAddr<NodeBase *>; 382 383 using Ref = NodeAddr<RefNode *>; 384 using Def = NodeAddr<DefNode *>; 385 using Use = NodeAddr<UseNode *>; // This may conflict with llvm::Use. 386 using PhiUse = NodeAddr<PhiUseNode *>; 387 388 using Code = NodeAddr<CodeNode *>; 389 using Instr = NodeAddr<InstrNode *>; 390 using Phi = NodeAddr<PhiNode *>; 391 using Stmt = NodeAddr<StmtNode *>; 392 using Block = NodeAddr<BlockNode *>; 393 using Func = NodeAddr<FuncNode *>; 394 395 // Fast memory allocation and translation between node id and node address. 396 // This is really the same idea as the one underlying the "bump pointer 397 // allocator", the difference being in the translation. A node id is 398 // composed of two components: the index of the block in which it was 399 // allocated, and the index within the block. With the default settings, 400 // where the number of nodes per block is 4096, the node id (minus 1) is: 401 // 402 // bit position: 11 0 403 // +----------------------------+--------------+ 404 // | Index of the block |Index in block| 405 // +----------------------------+--------------+ 406 // 407 // The actual node id is the above plus 1, to avoid creating a node id of 0. 408 // 409 // This method significantly improved the build time, compared to using maps 410 // (std::unordered_map or DenseMap) to translate between pointers and ids. 411 struct NodeAllocator { 412 // Amount of storage for a single node. 413 enum { NodeMemSize = 32 }; 414 415 NodeAllocator(uint32_t NPB = 4096) 416 : NodesPerBlock(NPB), BitsPerIndex(Log2_32(NPB)), 417 IndexMask((1 << BitsPerIndex) - 1) { 418 assert(isPowerOf2_32(NPB)); 419 } 420 421 NodeBase *ptr(NodeId N) const { 422 uint32_t N1 = N - 1; 423 uint32_t BlockN = N1 >> BitsPerIndex; 424 uint32_t Offset = (N1 & IndexMask) * NodeMemSize; 425 return reinterpret_cast<NodeBase *>(Blocks[BlockN] + Offset); 426 } 427 428 NodeId id(const NodeBase *P) const; 429 Node New(); 430 void clear(); 431 432 private: 433 void startNewBlock(); 434 bool needNewBlock(); 435 436 uint32_t makeId(uint32_t Block, uint32_t Index) const { 437 // Add 1 to the id, to avoid the id of 0, which is treated as "null". 438 return ((Block << BitsPerIndex) | Index) + 1; 439 } 440 441 const uint32_t NodesPerBlock; 442 const uint32_t BitsPerIndex; 443 const uint32_t IndexMask; 444 char *ActiveEnd = nullptr; 445 std::vector<char *> Blocks; 446 using AllocatorTy = BumpPtrAllocatorImpl<MallocAllocator, 65536>; 447 AllocatorTy MemPool; 448 }; 449 450 using RegisterSet = std::set<RegisterRef>; 451 452 struct TargetOperandInfo { 453 TargetOperandInfo(const TargetInstrInfo &tii) : TII(tii) {} 454 virtual ~TargetOperandInfo() = default; 455 456 virtual bool isPreserving(const MachineInstr &In, unsigned OpNum) const; 457 virtual bool isClobbering(const MachineInstr &In, unsigned OpNum) const; 458 virtual bool isFixedReg(const MachineInstr &In, unsigned OpNum) const; 459 460 const TargetInstrInfo &TII; 461 }; 462 463 // Packed register reference. Only used for storage. 464 struct PackedRegisterRef { 465 RegisterId Reg; 466 uint32_t MaskId; 467 }; 468 469 struct LaneMaskIndex : private IndexedSet<LaneBitmask> { 470 LaneMaskIndex() = default; 471 472 LaneBitmask getLaneMaskForIndex(uint32_t K) const { 473 return K == 0 ? LaneBitmask::getAll() : get(K); 474 } 475 476 uint32_t getIndexForLaneMask(LaneBitmask LM) { 477 assert(LM.any()); 478 return LM.all() ? 0 : insert(LM); 479 } 480 481 uint32_t getIndexForLaneMask(LaneBitmask LM) const { 482 assert(LM.any()); 483 return LM.all() ? 0 : find(LM); 484 } 485 }; 486 487 struct NodeBase { 488 public: 489 // Make sure this is a POD. 490 NodeBase() = default; 491 492 uint16_t getType() const { return NodeAttrs::type(Attrs); } 493 uint16_t getKind() const { return NodeAttrs::kind(Attrs); } 494 uint16_t getFlags() const { return NodeAttrs::flags(Attrs); } 495 NodeId getNext() const { return Next; } 496 497 uint16_t getAttrs() const { return Attrs; } 498 void setAttrs(uint16_t A) { Attrs = A; } 499 void setFlags(uint16_t F) { setAttrs(NodeAttrs::set_flags(getAttrs(), F)); } 500 501 // Insert node NA after "this" in the circular chain. 502 void append(Node NA); 503 504 // Initialize all members to 0. 505 void init() { memset(this, 0, sizeof *this); } 506 507 void setNext(NodeId N) { Next = N; } 508 509 protected: 510 uint16_t Attrs; 511 uint16_t Reserved; 512 NodeId Next; // Id of the next node in the circular chain. 513 // Definitions of nested types. Using anonymous nested structs would make 514 // this class definition clearer, but unnamed structs are not a part of 515 // the standard. 516 struct Def_struct { 517 NodeId DD, DU; // Ids of the first reached def and use. 518 }; 519 struct PhiU_struct { 520 NodeId PredB; // Id of the predecessor block for a phi use. 521 }; 522 struct Code_struct { 523 void *CP; // Pointer to the actual code. 524 NodeId FirstM, LastM; // Id of the first member and last. 525 }; 526 struct Ref_struct { 527 NodeId RD, Sib; // Ids of the reaching def and the sibling. 528 union { 529 Def_struct Def; 530 PhiU_struct PhiU; 531 }; 532 union { 533 MachineOperand *Op; // Non-phi refs point to a machine operand. 534 PackedRegisterRef PR; // Phi refs store register info directly. 535 }; 536 }; 537 538 // The actual payload. 539 union { 540 Ref_struct RefData; 541 Code_struct CodeData; 542 }; 543 }; 544 // The allocator allocates chunks of 32 bytes for each node. The fact that 545 // each node takes 32 bytes in memory is used for fast translation between 546 // the node id and the node address. 547 static_assert(sizeof(NodeBase) <= NodeAllocator::NodeMemSize, 548 "NodeBase must be at most NodeAllocator::NodeMemSize bytes"); 549 550 using NodeList = SmallVector<Node, 4>; 551 using NodeSet = std::set<NodeId>; 552 553 struct RefNode : public NodeBase { 554 RefNode() = default; 555 556 RegisterRef getRegRef(const DataFlowGraph &G) const; 557 558 MachineOperand &getOp() { 559 assert(!(getFlags() & NodeAttrs::PhiRef)); 560 return *RefData.Op; 561 } 562 563 void setRegRef(RegisterRef RR, DataFlowGraph &G); 564 void setRegRef(MachineOperand *Op, DataFlowGraph &G); 565 566 NodeId getReachingDef() const { return RefData.RD; } 567 void setReachingDef(NodeId RD) { RefData.RD = RD; } 568 569 NodeId getSibling() const { return RefData.Sib; } 570 void setSibling(NodeId Sib) { RefData.Sib = Sib; } 571 572 bool isUse() const { 573 assert(getType() == NodeAttrs::Ref); 574 return getKind() == NodeAttrs::Use; 575 } 576 577 bool isDef() const { 578 assert(getType() == NodeAttrs::Ref); 579 return getKind() == NodeAttrs::Def; 580 } 581 582 template <typename Predicate> 583 Ref getNextRef(RegisterRef RR, Predicate P, bool NextOnly, 584 const DataFlowGraph &G); 585 Node getOwner(const DataFlowGraph &G); 586 }; 587 588 struct DefNode : public RefNode { 589 NodeId getReachedDef() const { return RefData.Def.DD; } 590 void setReachedDef(NodeId D) { RefData.Def.DD = D; } 591 NodeId getReachedUse() const { return RefData.Def.DU; } 592 void setReachedUse(NodeId U) { RefData.Def.DU = U; } 593 594 void linkToDef(NodeId Self, Def DA); 595 }; 596 597 struct UseNode : public RefNode { 598 void linkToDef(NodeId Self, Def DA); 599 }; 600 601 struct PhiUseNode : public UseNode { 602 NodeId getPredecessor() const { 603 assert(getFlags() & NodeAttrs::PhiRef); 604 return RefData.PhiU.PredB; 605 } 606 void setPredecessor(NodeId B) { 607 assert(getFlags() & NodeAttrs::PhiRef); 608 RefData.PhiU.PredB = B; 609 } 610 }; 611 612 struct CodeNode : public NodeBase { 613 template <typename T> T getCode() const { // 614 return static_cast<T>(CodeData.CP); 615 } 616 void setCode(void *C) { CodeData.CP = C; } 617 618 Node getFirstMember(const DataFlowGraph &G) const; 619 Node getLastMember(const DataFlowGraph &G) const; 620 void addMember(Node NA, const DataFlowGraph &G); 621 void addMemberAfter(Node MA, Node NA, const DataFlowGraph &G); 622 void removeMember(Node NA, const DataFlowGraph &G); 623 624 NodeList members(const DataFlowGraph &G) const; 625 template <typename Predicate> 626 NodeList members_if(Predicate P, const DataFlowGraph &G) const; 627 }; 628 629 struct InstrNode : public CodeNode { 630 Node getOwner(const DataFlowGraph &G); 631 }; 632 633 struct PhiNode : public InstrNode { 634 MachineInstr *getCode() const { return nullptr; } 635 }; 636 637 struct StmtNode : public InstrNode { 638 MachineInstr *getCode() const { // 639 return CodeNode::getCode<MachineInstr *>(); 640 } 641 }; 642 643 struct BlockNode : public CodeNode { 644 MachineBasicBlock *getCode() const { 645 return CodeNode::getCode<MachineBasicBlock *>(); 646 } 647 648 void addPhi(Phi PA, const DataFlowGraph &G); 649 }; 650 651 struct FuncNode : public CodeNode { 652 MachineFunction *getCode() const { 653 return CodeNode::getCode<MachineFunction *>(); 654 } 655 656 Block findBlock(const MachineBasicBlock *BB, const DataFlowGraph &G) const; 657 Block getEntryBlock(const DataFlowGraph &G); 658 }; 659 660 struct DataFlowGraph { 661 DataFlowGraph(MachineFunction &mf, const TargetInstrInfo &tii, 662 const TargetRegisterInfo &tri, const MachineDominatorTree &mdt, 663 const MachineDominanceFrontier &mdf); 664 DataFlowGraph(MachineFunction &mf, const TargetInstrInfo &tii, 665 const TargetRegisterInfo &tri, const MachineDominatorTree &mdt, 666 const MachineDominanceFrontier &mdf, 667 const TargetOperandInfo &toi); 668 669 struct Config { 670 Config() = default; 671 Config(unsigned Opts) : Options(Opts) {} 672 Config(ArrayRef<const TargetRegisterClass *> RCs) : Classes(RCs) {} 673 Config(ArrayRef<MCPhysReg> Track) : TrackRegs(Track.begin(), Track.end()) {} 674 Config(ArrayRef<RegisterId> Track) 675 : TrackRegs(Track.begin(), Track.end()) {} 676 677 unsigned Options = BuildOptions::None; 678 SmallVector<const TargetRegisterClass *> Classes; 679 std::set<RegisterId> TrackRegs; 680 }; 681 682 NodeBase *ptr(NodeId N) const; 683 template <typename T> T ptr(NodeId N) const { // 684 return static_cast<T>(ptr(N)); 685 } 686 687 NodeId id(const NodeBase *P) const; 688 689 template <typename T> NodeAddr<T> addr(NodeId N) const { 690 return {ptr<T>(N), N}; 691 } 692 693 Func getFunc() const { return TheFunc; } 694 MachineFunction &getMF() const { return MF; } 695 const TargetInstrInfo &getTII() const { return TII; } 696 const TargetRegisterInfo &getTRI() const { return TRI; } 697 const PhysicalRegisterInfo &getPRI() const { return PRI; } 698 const MachineDominatorTree &getDT() const { return MDT; } 699 const MachineDominanceFrontier &getDF() const { return MDF; } 700 const RegisterAggr &getLiveIns() const { return LiveIns; } 701 702 struct DefStack { 703 DefStack() = default; 704 705 bool empty() const { return Stack.empty() || top() == bottom(); } 706 707 private: 708 using value_type = Def; 709 struct Iterator { 710 using value_type = DefStack::value_type; 711 712 Iterator &up() { 713 Pos = DS.nextUp(Pos); 714 return *this; 715 } 716 Iterator &down() { 717 Pos = DS.nextDown(Pos); 718 return *this; 719 } 720 721 value_type operator*() const { 722 assert(Pos >= 1); 723 return DS.Stack[Pos - 1]; 724 } 725 const value_type *operator->() const { 726 assert(Pos >= 1); 727 return &DS.Stack[Pos - 1]; 728 } 729 bool operator==(const Iterator &It) const { return Pos == It.Pos; } 730 bool operator!=(const Iterator &It) const { return Pos != It.Pos; } 731 732 private: 733 friend struct DefStack; 734 735 Iterator(const DefStack &S, bool Top); 736 737 // Pos-1 is the index in the StorageType object that corresponds to 738 // the top of the DefStack. 739 const DefStack &DS; 740 unsigned Pos; 741 }; 742 743 public: 744 using iterator = Iterator; 745 746 iterator top() const { return Iterator(*this, true); } 747 iterator bottom() const { return Iterator(*this, false); } 748 unsigned size() const; 749 750 void push(Def DA) { Stack.push_back(DA); } 751 void pop(); 752 void start_block(NodeId N); 753 void clear_block(NodeId N); 754 755 private: 756 friend struct Iterator; 757 758 using StorageType = std::vector<value_type>; 759 760 bool isDelimiter(const StorageType::value_type &P, NodeId N = 0) const { 761 return (P.Addr == nullptr) && (N == 0 || P.Id == N); 762 } 763 764 unsigned nextUp(unsigned P) const; 765 unsigned nextDown(unsigned P) const; 766 767 StorageType Stack; 768 }; 769 770 // Make this std::unordered_map for speed of accessing elements. 771 // Map: Register (physical or virtual) -> DefStack 772 using DefStackMap = std::unordered_map<RegisterId, DefStack>; 773 774 void build(const Config &config); 775 void build() { build(Config()); } 776 777 void pushAllDefs(Instr IA, DefStackMap &DM); 778 void markBlock(NodeId B, DefStackMap &DefM); 779 void releaseBlock(NodeId B, DefStackMap &DefM); 780 781 PackedRegisterRef pack(RegisterRef RR) { 782 return {RR.Reg, LMI.getIndexForLaneMask(RR.Mask)}; 783 } 784 PackedRegisterRef pack(RegisterRef RR) const { 785 return {RR.Reg, LMI.getIndexForLaneMask(RR.Mask)}; 786 } 787 RegisterRef unpack(PackedRegisterRef PR) const { 788 return RegisterRef(PR.Reg, LMI.getLaneMaskForIndex(PR.MaskId)); 789 } 790 791 RegisterRef makeRegRef(unsigned Reg, unsigned Sub) const; 792 RegisterRef makeRegRef(const MachineOperand &Op) const; 793 794 Ref getNextRelated(Instr IA, Ref RA) const; 795 Ref getNextShadow(Instr IA, Ref RA, bool Create); 796 797 NodeList getRelatedRefs(Instr IA, Ref RA) const; 798 799 Block findBlock(MachineBasicBlock *BB) const { return BlockNodes.at(BB); } 800 801 void unlinkUse(Use UA, bool RemoveFromOwner) { 802 unlinkUseDF(UA); 803 if (RemoveFromOwner) 804 removeFromOwner(UA); 805 } 806 807 void unlinkDef(Def DA, bool RemoveFromOwner) { 808 unlinkDefDF(DA); 809 if (RemoveFromOwner) 810 removeFromOwner(DA); 811 } 812 813 bool isTracked(RegisterRef RR) const; 814 bool hasUntrackedRef(Stmt S, bool IgnoreReserved = true) const; 815 816 // Some useful filters. 817 template <uint16_t Kind> static bool IsRef(const Node BA) { 818 return BA.Addr->getType() == NodeAttrs::Ref && BA.Addr->getKind() == Kind; 819 } 820 821 template <uint16_t Kind> static bool IsCode(const Node BA) { 822 return BA.Addr->getType() == NodeAttrs::Code && BA.Addr->getKind() == Kind; 823 } 824 825 static bool IsDef(const Node BA) { 826 return BA.Addr->getType() == NodeAttrs::Ref && 827 BA.Addr->getKind() == NodeAttrs::Def; 828 } 829 830 static bool IsUse(const Node BA) { 831 return BA.Addr->getType() == NodeAttrs::Ref && 832 BA.Addr->getKind() == NodeAttrs::Use; 833 } 834 835 static bool IsPhi(const Node BA) { 836 return BA.Addr->getType() == NodeAttrs::Code && 837 BA.Addr->getKind() == NodeAttrs::Phi; 838 } 839 840 static bool IsPreservingDef(const Def DA) { 841 uint16_t Flags = DA.Addr->getFlags(); 842 return (Flags & NodeAttrs::Preserving) && !(Flags & NodeAttrs::Undef); 843 } 844 845 private: 846 void reset(); 847 848 RegisterAggr getLandingPadLiveIns() const; 849 850 Node newNode(uint16_t Attrs); 851 Node cloneNode(const Node B); 852 Use newUse(Instr Owner, MachineOperand &Op, uint16_t Flags = NodeAttrs::None); 853 PhiUse newPhiUse(Phi Owner, RegisterRef RR, Block PredB, 854 uint16_t Flags = NodeAttrs::PhiRef); 855 Def newDef(Instr Owner, MachineOperand &Op, uint16_t Flags = NodeAttrs::None); 856 Def newDef(Instr Owner, RegisterRef RR, uint16_t Flags = NodeAttrs::PhiRef); 857 Phi newPhi(Block Owner); 858 Stmt newStmt(Block Owner, MachineInstr *MI); 859 Block newBlock(Func Owner, MachineBasicBlock *BB); 860 Func newFunc(MachineFunction *MF); 861 862 template <typename Predicate> 863 std::pair<Ref, Ref> locateNextRef(Instr IA, Ref RA, Predicate P) const; 864 865 using BlockRefsMap = RegisterAggrMap<NodeId>; 866 867 void buildStmt(Block BA, MachineInstr &In); 868 void recordDefsForDF(BlockRefsMap &PhiM, Block BA); 869 void buildPhis(BlockRefsMap &PhiM, Block BA); 870 void removeUnusedPhis(); 871 872 void pushClobbers(Instr IA, DefStackMap &DM); 873 void pushDefs(Instr IA, DefStackMap &DM); 874 template <typename T> void linkRefUp(Instr IA, NodeAddr<T> TA, DefStack &DS); 875 template <typename Predicate> 876 void linkStmtRefs(DefStackMap &DefM, Stmt SA, Predicate P); 877 void linkBlockRefs(DefStackMap &DefM, Block BA); 878 879 void unlinkUseDF(Use UA); 880 void unlinkDefDF(Def DA); 881 882 void removeFromOwner(Ref RA) { 883 Instr IA = RA.Addr->getOwner(*this); 884 IA.Addr->removeMember(RA, *this); 885 } 886 887 // Default TOI object, if not given in the constructor. 888 std::unique_ptr<TargetOperandInfo> DefaultTOI; 889 890 MachineFunction &MF; 891 const TargetInstrInfo &TII; 892 const TargetRegisterInfo &TRI; 893 const PhysicalRegisterInfo PRI; 894 const MachineDominatorTree &MDT; 895 const MachineDominanceFrontier &MDF; 896 const TargetOperandInfo &TOI; 897 898 RegisterAggr LiveIns; 899 Func TheFunc; 900 NodeAllocator Memory; 901 // Local map: MachineBasicBlock -> NodeAddr<BlockNode*> 902 std::map<MachineBasicBlock *, Block> BlockNodes; 903 // Lane mask map. 904 LaneMaskIndex LMI; 905 906 Config BuildCfg; 907 std::set<unsigned> TrackedUnits; 908 BitVector ReservedRegs; 909 }; // struct DataFlowGraph 910 911 template <typename Predicate> 912 Ref RefNode::getNextRef(RegisterRef RR, Predicate P, bool NextOnly, 913 const DataFlowGraph &G) { 914 // Get the "Next" reference in the circular list that references RR and 915 // satisfies predicate "Pred". 916 auto NA = G.addr<NodeBase *>(getNext()); 917 918 while (NA.Addr != this) { 919 if (NA.Addr->getType() == NodeAttrs::Ref) { 920 Ref RA = NA; 921 if (G.getPRI().equal_to(RA.Addr->getRegRef(G), RR) && P(NA)) 922 return NA; 923 if (NextOnly) 924 break; 925 NA = G.addr<NodeBase *>(NA.Addr->getNext()); 926 } else { 927 // We've hit the beginning of the chain. 928 assert(NA.Addr->getType() == NodeAttrs::Code); 929 // Make sure we stop here with NextOnly. Otherwise we can return the 930 // wrong ref. Consider the following while creating/linking shadow uses: 931 // -> code -> sr1 -> sr2 -> [back to code] 932 // Say that shadow refs sr1, and sr2 have been linked, but we need to 933 // create and link another one. Starting from sr2, we'd hit the code 934 // node and return sr1 if the iteration didn't stop here. 935 if (NextOnly) 936 break; 937 Code CA = NA; 938 NA = CA.Addr->getFirstMember(G); 939 } 940 } 941 // Return the equivalent of "nullptr" if such a node was not found. 942 return Ref(); 943 } 944 945 template <typename Predicate> 946 NodeList CodeNode::members_if(Predicate P, const DataFlowGraph &G) const { 947 NodeList MM; 948 auto M = getFirstMember(G); 949 if (M.Id == 0) 950 return MM; 951 952 while (M.Addr != this) { 953 if (P(M)) 954 MM.push_back(M); 955 M = G.addr<NodeBase *>(M.Addr->getNext()); 956 } 957 return MM; 958 } 959 960 template <typename T> struct Print { 961 Print(const T &x, const DataFlowGraph &g) : Obj(x), G(g) {} 962 963 const T &Obj; 964 const DataFlowGraph &G; 965 }; 966 967 template <typename T> Print(const T &, const DataFlowGraph &) -> Print<T>; 968 969 template <typename T> struct PrintNode : Print<NodeAddr<T>> { 970 PrintNode(const NodeAddr<T> &x, const DataFlowGraph &g) 971 : Print<NodeAddr<T>>(x, g) {} 972 }; 973 974 raw_ostream &operator<<(raw_ostream &OS, const Print<RegisterRef> &P); 975 raw_ostream &operator<<(raw_ostream &OS, const Print<NodeId> &P); 976 raw_ostream &operator<<(raw_ostream &OS, const Print<Def> &P); 977 raw_ostream &operator<<(raw_ostream &OS, const Print<Use> &P); 978 raw_ostream &operator<<(raw_ostream &OS, const Print<PhiUse> &P); 979 raw_ostream &operator<<(raw_ostream &OS, const Print<Ref> &P); 980 raw_ostream &operator<<(raw_ostream &OS, const Print<NodeList> &P); 981 raw_ostream &operator<<(raw_ostream &OS, const Print<NodeSet> &P); 982 raw_ostream &operator<<(raw_ostream &OS, const Print<Phi> &P); 983 raw_ostream &operator<<(raw_ostream &OS, const Print<Stmt> &P); 984 raw_ostream &operator<<(raw_ostream &OS, const Print<Instr> &P); 985 raw_ostream &operator<<(raw_ostream &OS, const Print<Block> &P); 986 raw_ostream &operator<<(raw_ostream &OS, const Print<Func> &P); 987 raw_ostream &operator<<(raw_ostream &OS, const Print<RegisterSet> &P); 988 raw_ostream &operator<<(raw_ostream &OS, const Print<RegisterAggr> &P); 989 raw_ostream &operator<<(raw_ostream &OS, 990 const Print<DataFlowGraph::DefStack> &P); 991 992 } // end namespace rdf 993 } // end namespace llvm 994 995 #endif // LLVM_CODEGEN_RDFGRAPH_H 996