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");
273 Code = 0x0001,
// 01, Container
274 Ref = 0x0002,
// 10, Reference
285 // Flags: 7 bits for now
287 Shadow = 0x0001 << 5,
// 0000001, Has extra reaching defs.
288 Clobbering = 0x0002 << 5,
// 0000010, Produces unspecified values.
289 PhiRef = 0x0004 << 5,
// 0000100, Member of PhiNode.
290 Preserving = 0x0008 << 5,
// 0001000, Def can keep original bits.
291 Fixed = 0x0010 << 5,
// 0010000, Fixed register.
292 Undef = 0x0020 << 5,
// 0100000, Has no pre-existing value.
293 Dead = 0x0040 << 5,
// 1000000, Does not define a value.
318 // Test if A contains B.
327 return KB ==
Phi || KB ==
Stmt;
348 // Type cast (casting constructor). The reason for having this class
349 // instead of std::pair.
350 template <
typename S>
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) {
423 uint32_t BlockN = N1 >> BitsPerIndex;
433 void startNewBlock();
437 // Add 1 to the id, to avoid the id of 0, which is treated as "null".
438 return ((
Block << BitsPerIndex) | Index) + 1;
444 char *ActiveEnd =
nullptr;
445 std::vector<char *> Blocks;
463// Packed register reference. Only used for storage.
483 return LM.
all() ? 0 :
find(LM);
489 // Make sure this is a POD.
501 // Insert node NA after "this" in the circular chain.
504 // Initialize all members to 0.
505 void init() { 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
523 void *
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");
582 template <
typename Predicate>
625 template <
typename Predicate>
675 :
TrackRegs(Track.begin(), Track.end()) {}
684 return static_cast<T >(
ptr(
N));
708 using value_type =
Def;
710 using value_type = DefStack::value_type;
713 Pos = DS.nextUp(Pos);
717 Pos = DS.nextDown(Pos);
723 return DS.Stack[Pos - 1];
725 const value_type *operator->()
const {
727 return &DS.Stack[Pos - 1];
729 bool operator==(
const Iterator &It)
const {
return Pos == It.Pos; }
730 bool operator!=(
const Iterator &It)
const {
return Pos != It.Pos; }
733 friend struct DefStack;
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.
748 unsigned size()
const;
756 friend struct Iterator;
758 using StorageType = std::vector<value_type>;
760 bool isDelimiter(
const StorageType::value_type &
P,
NodeId N = 0)
const {
761 return (
P.Addr ==
nullptr) && (
N == 0 ||
P.Id ==
N);
764 unsigned nextUp(
unsigned P)
const;
765 unsigned nextDown(
unsigned P)
const;
770 // Make this std::unordered_map for speed of accessing elements.
771 // Map: Register (physical or virtual) -> DefStack
782 return {RR.
Reg, LMI.getIndexForLaneMask(RR.
Mask)};
785 return {RR.
Reg, LMI.getIndexForLaneMask(RR.
Mask)};
816 // Some useful filters.
817 template <u
int16_t Kind>
static bool IsRef(
const Node BA) {
841 uint16_t Flags = DA.Addr->getFlags();
862 template <
typename Predicate>
868 void recordDefsForDF(BlockRefsMap &PhiM, BlockRefsMap &PhiClobberM,
Block BA);
869 void buildPhis(BlockRefsMap &PhiM,
Block BA,
871 void removeUnusedPhis();
875 template <
typename T>
void linkRefUp(
Instr IA,
NodeAddr<T> TA, DefStack &DS);
876 template <
typename Predicate>
880 void unlinkUseDF(
Use UA);
881 void unlinkDefDF(
Def DA);
883 void removeFromOwner(
Ref RA) {
884 Instr IA =
RA.Addr->getOwner(*
this);
885 IA.Addr->removeMember(
RA, *
this);
888 // Default TOI object, if not given in the constructor.
889 std::unique_ptr<TargetOperandInfo> DefaultTOI;
894 const PhysicalRegisterInfo PRI;
897 const TargetOperandInfo &TOI;
899 RegisterAggr LiveIns;
902 // Local map: MachineBasicBlock -> NodeAddr<BlockNode*>
903 std::map<MachineBasicBlock *, Block> BlockNodes;
908 std::set<unsigned> TrackedUnits;
910};
// struct DataFlowGraph
912template <
typename Predicate>
915 // Get the "Next" reference in the circular list that references RR and
916 // satisfies predicate "Pred".
919 while (NA.Addr !=
this) {
922 if (
G.getPRI().equal_to(
RA.Addr->getRegRef(
G), RR) &&
P(NA))
926 NA =
G.addr<
NodeBase *>(NA.Addr->getNext());
928 // We've hit the beginning of the chain.
930 // Make sure we stop here with NextOnly. Otherwise we can return the
931 // wrong ref. Consider the following while creating/linking shadow uses:
932 // -> code -> sr1 -> sr2 -> [back to code]
933 // Say that shadow refs sr1, and sr2 have been linked, but we need to
934 // create and link another one. Starting from sr2, we'd hit the code
935 // node and return sr1 if the iteration didn't stop here.
942 // Return the equivalent of "nullptr" if such a node was not found.
946template <
typename Predicate>
953 while (M.Addr !=
this) {
956 M =
G.addr<
NodeBase *>(M.Addr->getNext());
961 template <
typename T>
struct Print {
993}
// end namespace rdf
994}
// end namespace llvm
996#endif // LLVM_CODEGEN_RDFGRAPH_H
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
This file defines the BumpPtrAllocator interface.
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static RegisterPass< DebugifyModulePass > DM("debugify", "Attach debug info to everything")
const HexagonInstrInfo * TII
A common definition of LaneBitmask for use in TableGen and CodeGen.
Register const TargetRegisterInfo * TRI
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.
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< DefNode * > Def
NodeAddr< InstrNode * > Instr
std::set< RegisterRef, RegisterRefLess > RegisterSet
NodeAddr< BlockNode * > Block
NodeAddr< PhiNode * > Phi
Print(const T &, const DataFlowGraph &) -> Print< T >
NodeAddr< PhiUseNode * > PhiUse
NodeAddr< StmtNode * > Stmt
NodeAddr< UseNode * > Use
NodeAddr< NodeBase * > Node
raw_ostream & operator<<(raw_ostream &OS, const Print< RegisterRef > &P)
std::set< NodeId > NodeSet
SmallVector< Node, 4 > NodeList
NodeAddr< CodeNode * > Code
NodeAddr< FuncNode * > Func
NodeAddr< RefNode * > Ref
This is an optimization pass for GlobalISel generic memory operations.
APInt operator*(APInt a, uint64_t 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.
@ Sub
Subtraction of integers.
DWARFExpression::Operation Op
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)
DataFlowGraph(MachineFunction &mf, const TargetInstrInfo &tii, const TargetRegisterInfo &tri, const MachineDominatorTree &mdt, const MachineDominanceFrontier &mdf)
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)