//===- RDFGraph.h -----------------------------------------------*- C++ -*-===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// // // Target-independent, SSA-based data flow graph for register data flow (RDF) // for a non-SSA program representation (e.g. post-RA machine code). // // // *** Introduction // // The RDF graph is a collection of nodes, each of which denotes some element // of the program. There are two main types of such elements: code and refe- // rences. Conceptually, "code" is something that represents the structure // of the program, e.g. basic block or a statement, while "reference" is an // instance of accessing a register, e.g. a definition or a use. Nodes are // connected with each other based on the structure of the program (such as // blocks, instructions, etc.), and based on the data flow (e.g. reaching // definitions, reached uses, etc.). The single-reaching-definition principle // of SSA is generally observed, although, due to the non-SSA representation // of the program, there are some differences between the graph and a "pure" // SSA representation. // // // *** Implementation remarks // // Since the graph can contain a large number of nodes, memory consumption // was one of the major design considerations. As a result, there is a single // base class NodeBase which defines all members used by all possible derived // classes. The members are arranged in a union, and a derived class cannot // add any data members of its own. Each derived class only defines the // functional interface, i.e. member functions. NodeBase must be a POD, // which implies that all of its members must also be PODs. // Since nodes need to be connected with other nodes, pointers have been // replaced with 32-bit identifiers: each node has an id of type NodeId. // There are mapping functions in the graph that translate between actual // memory addresses and the corresponding identifiers. // A node id of 0 is equivalent to nullptr. // // // *** Structure of the graph // // A code node is always a collection of other nodes. For example, a code // node corresponding to a basic block will contain code nodes corresponding // to instructions. In turn, a code node corresponding to an instruction will // contain a list of reference nodes that correspond to the definitions and // uses of registers in that instruction. The members are arranged into a // circular list, which is yet another consequence of the effort to save // memory: for each member node it should be possible to obtain its owner, // and it should be possible to access all other members. There are other // ways to accomplish that, but the circular list seemed the most natural. // // +- CodeNode -+ // | | <---------------------------------------------------+ // +-+--------+-+ | // |FirstM |LastM | // | +-------------------------------------+ | // | | | // V V | // +----------+ Next +----------+ Next Next +----------+ Next | // | |----->| |-----> ... ----->| |----->-+ // +- Member -+ +- Member -+ +- Member -+ // // The order of members is such that related reference nodes (see below) // should be contiguous on the member list. // // A reference node is a node that encapsulates an access to a register, // in other words, data flowing into or out of a register. There are two // major kinds of reference nodes: defs and uses. A def node will contain // the id of the first reached use, and the id of the first reached def. // Each def and use will contain the id of the reaching def, and also the // id of the next reached def (for def nodes) or use (for use nodes). // The "next node sharing the same reaching def" is denoted as "sibling". // In summary: // - Def node contains: reaching def, sibling, first reached def, and first // reached use. // - Use node contains: reaching def and sibling. // // +-- DefNode --+ // | R2 = ... | <---+--------------------+ // ++---------+--+ | | // |Reached |Reached | | // |Def |Use | | // | | |Reaching |Reaching // | V |Def |Def // | +-- UseNode --+ Sib +-- UseNode --+ Sib Sib // | | ... = R2 |----->| ... = R2 |----> ... ----> 0 // | +-------------+ +-------------+ // V // +-- DefNode --+ Sib // | R2 = ... |----> ... // ++---------+--+ // | | // | | // ... ... // // To get a full picture, the circular lists connecting blocks within a // function, instructions within a block, etc. should be superimposed with // the def-def, def-use links shown above. // To illustrate this, consider a small example in a pseudo-assembly: // foo: // add r2, r0, r1 ; r2 = r0+r1 // addi r0, r2, 1 ; r0 = r2+1 // ret r0 ; return value in r0 // // The graph (in a format used by the debugging functions) would look like: // // DFG dump:[ // f1: Function foo // b2: === %bb.0 === preds(0), succs(0): // p3: phi [d4<r0>(,d12,u9):] // p5: phi [d6<r1>(,,u10):] // s7: add [d8<r2>(,,u13):, u9<r0>(d4):, u10<r1>(d6):] // s11: addi [d12<r0>(d4,,u15):, u13<r2>(d8):] // s14: ret [u15<r0>(d12):] // ] // // The f1, b2, p3, etc. are node ids. The letter is prepended to indicate the // kind of the node (i.e. f - function, b - basic block, p - phi, s - state- // ment, d - def, u - use). // The format of a def node is: // dN<R>(rd,d,u):sib, // where // N - numeric node id, // R - register being defined // rd - reaching def, // d - reached def, // u - reached use, // sib - sibling. // The format of a use node is: // uN<R>[!](rd):sib, // where // N - numeric node id, // R - register being used, // rd - reaching def, // sib - sibling. // Possible annotations (usually preceding the node id): // + - preserving def, // ~ - clobbering def, // " - shadow ref (follows the node id), // ! - fixed register (appears after register name). // // The circular lists are not explicit in the dump. // // // *** Node attributes // // NodeBase has a member "Attrs", which is the primary way of determining // the node's characteristics. The fields in this member decide whether // the node is a code node or a reference node (i.e. node's "type"), then // within each type, the "kind" determines what specifically this node // represents. The remaining bits, "flags", contain additional information // that is even more detailed than the "kind". // CodeNode's kinds are: // - Phi: Phi node, members are reference nodes. // - Stmt: Statement, members are reference nodes. // - Block: Basic block, members are instruction nodes (i.e. Phi or Stmt). // - Func: The whole function. The members are basic block nodes. // RefNode's kinds are: // - Use. // - Def. // // Meaning of flags: // - Preserving: applies only to defs. A preserving def is one that can // preserve some of the original bits among those that are included in // the register associated with that def. For example, if R0 is a 32-bit // register, but a def can only change the lower 16 bits, then it will // be marked as preserving. // - Shadow: a reference that has duplicates holding additional reaching // defs (see more below). // - Clobbering: applied only to defs, indicates that the value generated // by this def is unspecified. A typical example would be volatile registers // after function calls. // - Fixed: the register in this def/use cannot be replaced with any other // register. A typical case would be a parameter register to a call, or // the register with the return value from a function. // - Undef: the register in this reference the register is assumed to have // no pre-existing value, even if it appears to be reached by some def. // This is typically used to prevent keeping registers artificially live // in cases when they are defined via predicated instructions. For example: // r0 = add-if-true cond, r10, r11 (1) // r0 = add-if-false cond, r12, r13, implicit r0 (2) // ... = r0 (3) // Before (1), r0 is not intended to be live, and the use of r0 in (3) is // not meant to be reached by any def preceding (1). However, since the // defs in (1) and (2) are both preserving, these properties alone would // imply that the use in (3) may indeed be reached by some prior def. // Adding Undef flag to the def in (1) prevents that. The Undef flag // may be applied to both defs and uses. // - Dead: applies only to defs. The value coming out of a "dead" def is // assumed to be unused, even if the def appears to be reaching other defs // or uses. The motivation for this flag comes from dead defs on function // calls: there is no way to determine if such a def is dead without // analyzing the target's ABI. Hence the graph should contain this info, // as it is unavailable otherwise. On the other hand, a def without any // uses on a typical instruction is not the intended target for this flag. // // *** Shadow references // // It may happen that a super-register can have two (or more) non-overlapping // sub-registers. When both of these sub-registers are defined and followed // by a use of the super-register, the use of the super-register will not // have a unique reaching def: both defs of the sub-registers need to be // accounted for. In such cases, a duplicate use of the super-register is // added and it points to the extra reaching def. Both uses are marked with // a flag "shadow". Example: // Assume t0 is a super-register of r0 and r1, r0 and r1 do not overlap: // set r0, 1 ; r0 = 1 // set r1, 1 ; r1 = 1 // addi t1, t0, 1 ; t1 = t0+1 // // The DFG: // s1: set [d2<r0>(,,u9):] // s3: set [d4<r1>(,,u10):] // s5: addi [d6<t1>(,,):, u7"<t0>(d2):, u8"<t0>(d4):] // // The statement s5 has two use nodes for t0: u7" and u9". The quotation // mark " indicates that the node is a shadow. // #ifndef LLVM_CODEGEN_RDFGRAPH_H #define LLVM_CODEGEN_RDFGRAPH_H #include "RDFRegisters.h" #include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/SmallVector.h" #include "llvm/MC/LaneBitmask.h" #include "llvm/Support/Allocator.h" #include "llvm/Support/MathExtras.h" #include <cassert> #include <cstdint> #include <cstring> #include <map> #include <memory> #include <set> #include <unordered_map> #include <utility> #include <vector> // RDF uses uint32_t to refer to registers. This is to ensure that the type // size remains specific. In other places, registers are often stored using // unsigned. static_assert …; namespace llvm { class MachineBasicBlock; class MachineDominanceFrontier; class MachineDominatorTree; class MachineFunction; class MachineInstr; class MachineOperand; class raw_ostream; class TargetInstrInfo; class TargetRegisterInfo; namespace rdf { NodeId; struct DataFlowGraph; struct NodeAttrs { … }; struct BuildOptions { … }; template <typename T> struct NodeAddr { … }; struct NodeBase; struct RefNode; struct DefNode; struct UseNode; struct PhiUseNode; struct CodeNode; struct InstrNode; struct PhiNode; struct StmtNode; struct BlockNode; struct FuncNode; // Use these short names with rdf:: qualification to avoid conflicts with // preexisting names. Do not use 'using namespace rdf'. Node; Ref; Def; Use; // This may conflict with llvm::Use. PhiUse; Code; Instr; Phi; Stmt; Block; Func; // Fast memory allocation and translation between node id and node address. // This is really the same idea as the one underlying the "bump pointer // allocator", the difference being in the translation. A node id is // composed of two components: the index of the block in which it was // allocated, and the index within the block. With the default settings, // where the number of nodes per block is 4096, the node id (minus 1) is: // // bit position: 11 0 // +----------------------------+--------------+ // | Index of the block |Index in block| // +----------------------------+--------------+ // // The actual node id is the above plus 1, to avoid creating a node id of 0. // // This method significantly improved the build time, compared to using maps // (std::unordered_map or DenseMap) to translate between pointers and ids. struct NodeAllocator { … }; RegisterSet; struct TargetOperandInfo { … }; // Packed register reference. Only used for storage. struct PackedRegisterRef { … }; struct LaneMaskIndex : private IndexedSet<LaneBitmask> { … }; struct NodeBase { … }; // The allocator allocates chunks of 32 bytes for each node. The fact that // each node takes 32 bytes in memory is used for fast translation between // the node id and the node address. static_assert …; NodeList; NodeSet; struct RefNode : public NodeBase { … }; struct DefNode : public RefNode { … }; struct UseNode : public RefNode { … }; struct PhiUseNode : public UseNode { … }; struct CodeNode : public NodeBase { … }; struct InstrNode : public CodeNode { … }; struct PhiNode : public InstrNode { … }; struct StmtNode : public InstrNode { … }; struct BlockNode : public CodeNode { … }; struct FuncNode : public CodeNode { … }; struct DataFlowGraph { … }; // struct DataFlowGraph template <typename Predicate> Ref RefNode::getNextRef(RegisterRef RR, Predicate P, bool NextOnly, const DataFlowGraph &G) { … } template <typename Predicate> NodeList CodeNode::members_if(Predicate P, const DataFlowGraph &G) const { … } template <typename T> struct Print { … }; template <typename T> Print(const T &, const DataFlowGraph &) -> Print<T>; template <typename T> struct PrintNode : Print<NodeAddr<T>> { … }; raw_ostream &operator<<(raw_ostream &OS, const Print<RegisterRef> &P); raw_ostream &operator<<(raw_ostream &OS, const Print<NodeId> &P); raw_ostream &operator<<(raw_ostream &OS, const Print<Def> &P); raw_ostream &operator<<(raw_ostream &OS, const Print<Use> &P); raw_ostream &operator<<(raw_ostream &OS, const Print<PhiUse> &P); raw_ostream &operator<<(raw_ostream &OS, const Print<Ref> &P); raw_ostream &operator<<(raw_ostream &OS, const Print<NodeList> &P); raw_ostream &operator<<(raw_ostream &OS, const Print<NodeSet> &P); raw_ostream &operator<<(raw_ostream &OS, const Print<Phi> &P); raw_ostream &operator<<(raw_ostream &OS, const Print<Stmt> &P); raw_ostream &operator<<(raw_ostream &OS, const Print<Instr> &P); raw_ostream &operator<<(raw_ostream &OS, const Print<Block> &P); raw_ostream &operator<<(raw_ostream &OS, const Print<Func> &P); raw_ostream &operator<<(raw_ostream &OS, const Print<RegisterSet> &P); raw_ostream &operator<<(raw_ostream &OS, const Print<RegisterAggr> &P); raw_ostream &operator<<(raw_ostream &OS, const Print<DataFlowGraph::DefStack> &P); } // end namespace rdf } // end namespace llvm #endif // LLVM_CODEGEN_RDFGRAPH_H
Codebase Browser
llvm