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