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