1//===- RDFGraph.h -----------------------------------------------*- C++ -*-===// 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 7//===----------------------------------------------------------------------===// 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). 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" 28// *** Implementation remarks 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. 44// *** Structure of the graph 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. 57// | | <---------------------------------------------------+ 60// | +-------------------------------------+ | 63// +----------+ Next +----------+ Next Next +----------+ Next | 64// | |----->| |-----> ... ----->| |----->-+ 65// +- Member -+ +- Member -+ +- Member -+ 67// The order of members is such that related reference nodes (see below) 68// should be contiguous on the member list. 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". 78// - Def node contains: reaching def, sibling, first reached def, and first 80// - Use node contains: reaching def and sibling. 83// | R2 = ... | <---+--------------------+ 85// |Reached |Reached | | 87// | | |Reaching |Reaching 89// | +-- UseNode --+ Sib +-- UseNode --+ Sib Sib 90// | | ... = R2 |----->| ... = R2 |----> ... ----> 0 91// | +-------------+ +-------------+ 94// | R2 = ... |----> ... 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: 105// add r2, r0, r1 ; r2 = r0+r1 106// addi r0, r2, 1 ; r0 = r2+1 107// ret r0 ; return value in r0 109// The graph (in a format used by the debugging functions) would look like: 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):] 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: 127// N - numeric node id, 128// R - register being defined 133// The format of a use node is: 136// N - numeric node id, 137// R - register being used, 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). 146// The circular lists are not explicit in the dump. 149// *** Node attributes 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: 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) 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. 201// *** Shadow references 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: 213// addi t1, t0, 1 ; t1 = t0+1 216// s1: set [d2<r0>(,,u9):] 217// s3: set [d4<r1>(,,u10):] 218// s5: addi [d6<t1>(,,):, u7"<t0>(d2):, u8"<t0>(d4):] 220// The statement s5 has two use nodes for t0: u7" and u9". The quotation 221// mark " indicates that the node is a shadow. 224#ifndef LLVM_CODEGEN_RDFGRAPH_H 225#define LLVM_CODEGEN_RDFGRAPH_H 239#include <unordered_map> 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 246static_assert(
sizeof(
uint32_t) ==
sizeof(
unsigned),
"Those should be equal");
250classMachineBasicBlock;
251classMachineDominanceFrontier;
252classMachineDominatorTree;
258classTargetRegisterInfo;
274Ref = 0x0002,
// 10, Reference 285// Flags: 7 bits for now 287Shadow = 0x0001 << 5,
// 0000001, Has extra reaching defs. 288Clobbering = 0x0002 << 5,
// 0000010, Produces unspecified values. 289PhiRef = 0x0004 << 5,
// 0000100, Member of PhiNode. 290Preserving = 0x0008 << 5,
// 0001000, Def can keep original bits. 291Fixed = 0x0010 << 5,
// 0010000, Fixed register. 292Undef = 0x0020 << 5,
// 0100000, Has no pre-existing value. 293Dead = 0x0040 << 5,
// 1000000, Does not define a value. 318// Test if A contains B. 348// Type cast (casting constructor). The reason for having this class 349// instead of std::pair. 379// Use these short names with rdf:: qualification to avoid conflicts with 380// preexisting names. Do not use 'using namespace rdf'. 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: 403// +----------------------------+--------------+ 404// | Index of the block |Index in block| 405// +----------------------------+--------------+ 407// The actual node id is the above plus 1, to avoid creating a node id of 0. 409// This method significantly improved the build time, compared to using maps 410// (std::unordered_map or DenseMap) to translate between pointers and ids. 412// Amount of storage for a single node. 416 : NodesPerBlock(NPB), BitsPerIndex(
Log2_32(NPB)),
417 IndexMask((1 << BitsPerIndex) - 1) {
423uint32_t BlockN = N1 >> BitsPerIndex;
437// Add 1 to the id, to avoid the id of 0, which is treated as "null". 444char *ActiveEnd =
nullptr;
445 std::vector<char *> Blocks;
463// Packed register reference. Only used for storage. 489// Make sure this is a POD. 501// Insert node NA after "this" in the circular chain. 504// Initialize all members to 0. 505voidinit() { memset(
this, 0,
sizeof *
this); }
513// Definitions of nested types. Using anonymous nested structs would make 514// this class definition clearer, but unnamed structs are not a part of 523void *
CP;
// Pointer to the actual code. 538// The actual payload. 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. 548"NodeBase must be at most NodeAllocator::NodeMemSize bytes");
582template <
typename Predicate>
625template <
typename Predicate>
639return CodeNode::getCode<MachineInstr *>();
645return CodeNode::getCode<MachineBasicBlock *>();
653return CodeNode::getCode<MachineFunction *>();
675 :
TrackRegs(Track.begin(), Track.end()) {}
684returnstatic_cast<T>(
ptr(
N));
713 Pos = DS.nextUp(Pos);
717 Pos = DS.nextDown(Pos);
723return DS.Stack[Pos - 1];
725const value_type *operator->()
const{
727return &DS.Stack[Pos - 1];
729booloperator==(
const Iterator &It)
const{
return Pos == It.Pos; }
730booloperator!=(
const Iterator &It)
const{
return Pos != It.Pos; }
735 Iterator(
const DefStack &S,
bool Top);
737// Pos-1 is the index in the StorageType object that corresponds to 738// the top of the DefStack. 758usingStorageType = std::vector<value_type>;
760bool isDelimiter(
const StorageType::value_type &
P,
NodeIdN = 0)
const{
761return (
P.Addr ==
nullptr) && (
N == 0 ||
P.Id ==
N);
764unsigned nextUp(
unsignedP)
const;
765unsigned nextDown(
unsignedP)
const;
770// Make this std::unordered_map for speed of accessing elements. 771// Map: Register (physical or virtual) -> DefStack 816// Some useful filters. 841uint16_t Flags = DA.Addr->getFlags();
862template <
typename Predicate>
868void recordDefsForDF(BlockRefsMap &PhiM,
Block BA);
869void buildPhis(BlockRefsMap &PhiM,
Block BA);
870void removeUnusedPhis();
875template <
typename Predicate>
879void unlinkUseDF(
Use UA);
880void unlinkDefDF(
Def DA);
882void removeFromOwner(
RefRA) {
883Instr IA =
RA.Addr->getOwner(*
this);
884 IA.Addr->removeMember(
RA, *
this);
887// Default TOI object, if not given in the constructor. 888 std::unique_ptr<TargetOperandInfo> DefaultTOI;
893const PhysicalRegisterInfo PRI;
896const TargetOperandInfo &TOI;
898 RegisterAggr LiveIns;
901// Local map: MachineBasicBlock -> NodeAddr<BlockNode*> 902 std::map<MachineBasicBlock *, Block> BlockNodes;
907 std::set<unsigned> TrackedUnits;
909};
// struct DataFlowGraph 911template <
typename Predicate>
914// Get the "Next" reference in the circular list that references RR and 915// satisfies predicate "Pred". 918while (NA.Addr !=
this) {
921if (
G.getPRI().equal_to(
RA.Addr->getRegRef(
G), RR) &&
P(NA))
925 NA =
G.addr<
NodeBase *>(NA.Addr->getNext());
927// We've hit the beginning of the chain. 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. 938 NA = CA.
Addr->getFirstMember(
G);
941// Return the equivalent of "nullptr" if such a node was not found. 945template <
typename Predicate>
952while (M.Addr !=
this) {
955 M =
G.addr<
NodeBase *>(M.Addr->getNext());
990const Print<DataFlowGraph::DefStack> &
P);
993}
// end namespace llvm 995#endif// LLVM_CODEGEN_RDFGRAPH_H This file defines the BumpPtrAllocator interface.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static RegisterPass< DebugifyModulePass > DM("debugify", "Attach debug info to everything")
const HexagonInstrInfo * TII
A common definition of LaneBitmask for use in TableGen and CodeGen.
unsigned const TargetRegisterInfo * TRI
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
SI optimize exec mask operations pre RA
This file defines the SmallVector class.
INLINE void g(uint32_t *state, size_t a, size_t b, size_t c, size_t d, uint32_t x, uint32_t y)
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Allocate memory in an ever growing pool, as if by bump-pointer.
This class represents an Operation in the Expression.
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
Representation of each machine instruction.
MachineOperand class - Representation of each machine instruction operand.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
TargetInstrInfo - Interface to description of machine instruction set.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
This class implements an extremely fast bulk output stream that can only output to a stream.
This class provides various memory handling functions that manipulate MemoryBlock instances.
@ C
The default llvm calling convention, compatible with C.
NodeAddr< RefNode * > Ref
std::set< RegisterRef > RegisterSet
NodeAddr< DefNode * > Def
NodeAddr< FuncNode * > Func
raw_ostream & operator<<(raw_ostream &OS, const Print< RegisterRef > &P)
std::set< NodeId > NodeSet
This is an optimization pass for GlobalISel generic memory operations.
APInt operator*(APInt a, uint64_t RHS)
bool operator!=(uint64_t V1, const APInt &V2)
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)
unsigned Log2_32(uint32_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
static constexpr LaneBitmask getAll()
constexpr bool any() const
constexpr bool all() const
MachineBasicBlock * getCode() const
void addPhi(Phi PA, const DataFlowGraph &G)
NodeList members_if(Predicate P, const DataFlowGraph &G) const
void removeMember(Node NA, const DataFlowGraph &G)
NodeList members(const DataFlowGraph &G) const
void addMember(Node NA, const DataFlowGraph &G)
Node getFirstMember(const DataFlowGraph &G) const
void addMemberAfter(Node MA, Node NA, const DataFlowGraph &G)
Node getLastMember(const DataFlowGraph &G) const
Config(ArrayRef< const TargetRegisterClass * > RCs)
SmallVector< const TargetRegisterClass * > Classes
std::set< RegisterId > TrackRegs
Config(ArrayRef< RegisterId > Track)
Config(ArrayRef< MCPhysReg > Track)
void clear_block(NodeId N)
void start_block(NodeId N)
NodeId id(const NodeBase *P) const
void unlinkUse(Use UA, bool RemoveFromOwner)
const RegisterAggr & getLiveIns() const
void releaseBlock(NodeId B, DefStackMap &DefM)
PackedRegisterRef pack(RegisterRef RR)
Ref getNextRelated(Instr IA, Ref RA) const
bool isTracked(RegisterRef RR) const
RegisterRef makeRegRef(unsigned Reg, unsigned Sub) const
RegisterRef unpack(PackedRegisterRef PR) const
static bool IsDef(const Node BA)
Ref getNextShadow(Instr IA, Ref RA, bool Create)
static bool IsPhi(const Node BA)
const MachineDominanceFrontier & getDF() const
static bool IsPreservingDef(const Def DA)
const MachineDominatorTree & getDT() const
NodeList getRelatedRefs(Instr IA, Ref RA) const
void unlinkDef(Def DA, bool RemoveFromOwner)
MachineFunction & getMF() const
const TargetInstrInfo & getTII() const
static bool IsRef(const Node BA)
PackedRegisterRef pack(RegisterRef RR) const
static bool IsUse(const Node BA)
const PhysicalRegisterInfo & getPRI() const
static bool IsCode(const Node BA)
void markBlock(NodeId B, DefStackMap &DefM)
NodeBase * ptr(NodeId N) const
Block findBlock(MachineBasicBlock *BB) const
bool hasUntrackedRef(Stmt S, bool IgnoreReserved=true) const
std::unordered_map< RegisterId, DefStack > DefStackMap
const TargetRegisterInfo & getTRI() const
void pushAllDefs(Instr IA, DefStackMap &DM)
NodeAddr< T > addr(NodeId N) const
NodeId getReachedUse() const
void setReachedUse(NodeId U)
void setReachedDef(NodeId D)
NodeId getReachedDef() const
void linkToDef(NodeId Self, Def DA)
MachineFunction * getCode() const
Block findBlock(const MachineBasicBlock *BB, const DataFlowGraph &G) const
Block getEntryBlock(const DataFlowGraph &G)
LaneBitmask get(uint32_t Idx) const
uint32_t insert(LaneBitmask Val)
uint32_t find(LaneBitmask Val) const
Node getOwner(const DataFlowGraph &G)
uint32_t getIndexForLaneMask(LaneBitmask LM) const
LaneBitmask getLaneMaskForIndex(uint32_t K) const
uint32_t getIndexForLaneMask(LaneBitmask LM)
NodeAddr(const NodeAddr< S > &NA)
bool operator==(const NodeAddr< T > &NA) const
bool operator!=(const NodeAddr< T > &NA) const
NodeBase * ptr(NodeId N) const
NodeId id(const NodeBase *P) const
NodeAllocator(uint32_t NPB=4096)
static uint16_t set_kind(uint16_t A, uint16_t K)
static uint16_t flags(uint16_t T)
static uint16_t kind(uint16_t T)
static uint16_t set_type(uint16_t A, uint16_t T)
static bool contains(uint16_t A, uint16_t B)
static uint16_t set_flags(uint16_t A, uint16_t F)
static uint16_t type(uint16_t T)
void setFlags(uint16_t F)
uint16_t getAttrs() const
void setAttrs(uint16_t A)
uint16_t getFlags() const
MachineInstr * getCode() const
NodeId getPredecessor() const
void setPredecessor(NodeId B)
PrintNode(const NodeAddr< T > &x, const DataFlowGraph &g)
Print(const T &x, const DataFlowGraph &g)
NodeId getReachingDef() const
NodeId getSibling() const
Ref getNextRef(RegisterRef RR, Predicate P, bool NextOnly, const DataFlowGraph &G)
void setRegRef(RegisterRef RR, DataFlowGraph &G)
RegisterRef getRegRef(const DataFlowGraph &G) const
void setSibling(NodeId Sib)
void setReachingDef(NodeId RD)
Node getOwner(const DataFlowGraph &G)
MachineInstr * getCode() const
virtual bool isFixedReg(const MachineInstr &In, unsigned OpNum) const
const TargetInstrInfo & TII
virtual ~TargetOperandInfo()=default
virtual bool isPreserving(const MachineInstr &In, unsigned OpNum) const
virtual bool isClobbering(const MachineInstr &In, unsigned OpNum) const
TargetOperandInfo(const TargetInstrInfo &tii)
void linkToDef(NodeId Self, Def DA)
