1 //===--- RDFGraph.h ---------------------------------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Target-independent, SSA-based data flow graph for register data flow (RDF)
11 // for a non-SSA program representation (e.g. post-RA machine code).
16 // The RDF graph is a collection of nodes, each of which denotes some element
17 // of the program. There are two main types of such elements: code and refe-
18 // rences. Conceptually, "code" is something that represents the structure
19 // of the program, e.g. basic block or a statement, while "reference" is an
20 // instance of accessing a register, e.g. a definition or a use. Nodes are
21 // connected with each other based on the structure of the program (such as
22 // blocks, instructions, etc.), and based on the data flow (e.g. reaching
23 // definitions, reached uses, etc.). The single-reaching-definition principle
24 // of SSA is generally observed, although, due to the non-SSA representation
25 // of the program, there are some differences between the graph and a "pure"
26 // SSA representation.
29 // *** Implementation remarks
31 // Since the graph can contain a large number of nodes, memory consumption
32 // was one of the major design considerations. As a result, there is a single
33 // base class NodeBase which defines all members used by all possible derived
34 // classes. The members are arranged in a union, and a derived class cannot
35 // add any data members of its own. Each derived class only defines the
36 // functional interface, i.e. member functions. NodeBase must be a POD,
37 // which implies that all of its members must also be PODs.
38 // Since nodes need to be connected with other nodes, pointers have been
39 // replaced with 32-bit identifiers: each node has an id of type NodeId.
40 // There are mapping functions in the graph that translate between actual
41 // memory addresses and the corresponding identifiers.
42 // A node id of 0 is equivalent to nullptr.
45 // *** Structure of the graph
47 // A code node is always a collection of other nodes. For example, a code
48 // node corresponding to a basic block will contain code nodes corresponding
49 // to instructions. In turn, a code node corresponding to an instruction will
50 // contain a list of reference nodes that correspond to the definitions and
51 // uses of registers in that instruction. The members are arranged into a
52 // circular list, which is yet another consequence of the effort to save
53 // memory: for each member node it should be possible to obtain its owner,
54 // and it should be possible to access all other members. There are other
55 // ways to accomplish that, but the circular list seemed the most natural.
58 // | | <---------------------------------------------------+
61 // | +-------------------------------------+ |
64 // +----------+ Next +----------+ Next Next +----------+ Next |
65 // | |----->| |-----> ... ----->| |----->-+
66 // +- Member -+ +- Member -+ +- Member -+
68 // The order of members is such that related reference nodes (see below)
69 // should be contiguous on the member list.
71 // A reference node is a node that encapsulates an access to a register,
72 // in other words, data flowing into or out of a register. There are two
73 // major kinds of reference nodes: defs and uses. A def node will contain
74 // the id of the first reached use, and the id of the first reached def.
75 // Each def and use will contain the id of the reaching def, and also the
76 // id of the next reached def (for def nodes) or use (for use nodes).
77 // The "next node sharing the same reaching def" is denoted as "sibling".
79 // - Def node contains: reaching def, sibling, first reached def, and first
81 // - Use node contains: reaching def and sibling.
84 // | R2 = ... | <---+--------------------+
85 // ++---------+--+ | |
86 // |Reached |Reached | |
88 // | | |Reaching |Reaching
90 // | +-- UseNode --+ Sib +-- UseNode --+ Sib Sib
91 // | | ... = R2 |----->| ... = R2 |----> ... ----> 0
92 // | +-------------+ +-------------+
94 // +-- DefNode --+ Sib
95 // | R2 = ... |----> ...
101 // To get a full picture, the circular lists connecting blocks within a
102 // function, instructions within a block, etc. should be superimposed with
103 // the def-def, def-use links shown above.
104 // To illustrate this, consider a small example in a pseudo-assembly:
106 // add r2, r0, r1 ; r2 = r0+r1
107 // addi r0, r2, 1 ; r0 = r2+1
108 // ret r0 ; return value in r0
110 // The graph (in a format used by the debugging functions) would look like:
114 // b2: === BB#0 === preds(0), succs(0):
115 // p3: phi [d4<r0>(,d12,u9):]
116 // p5: phi [d6<r1>(,,u10):]
117 // s7: add [d8<r2>(,,u13):, u9<r0>(d4):, u10<r1>(d6):]
118 // s11: addi [d12<r0>(d4,,u15):, u13<r2>(d8):]
119 // s14: ret [u15<r0>(d12):]
122 // The f1, b2, p3, etc. are node ids. The letter is prepended to indicate the
123 // kind of the node (i.e. f - function, b - basic block, p - phi, s - state-
124 // ment, d - def, u - use).
125 // The format of a def node is:
126 // dN<R>(rd,d,u):sib,
128 // N - numeric node id,
129 // R - register being defined
130 // rd - reaching def,
134 // The format of a use node is:
137 // N - numeric node id,
138 // R - register being used,
139 // rd - reaching def,
141 // Possible annotations (usually preceding the node id):
142 // + - preserving def,
143 // ~ - clobbering def,
144 // " - shadow ref (follows the node id),
145 // ! - fixed register (appears after register name).
147 // The circular lists are not explicit in the dump.
150 // *** Node attributes
152 // NodeBase has a member "Attrs", which is the primary way of determining
153 // the node's characteristics. The fields in this member decide whether
154 // the node is a code node or a reference node (i.e. node's "type"), then
155 // within each type, the "kind" determines what specifically this node
156 // represents. The remaining bits, "flags", contain additional information
157 // that is even more detailed than the "kind".
158 // CodeNode's kinds are:
159 // - Phi: Phi node, members are reference nodes.
160 // - Stmt: Statement, members are reference nodes.
161 // - Block: Basic block, members are instruction nodes (i.e. Phi or Stmt).
162 // - Func: The whole function. The members are basic block nodes.
163 // RefNode's kinds are:
168 // - Preserving: applies only to defs. A preserving def is one that can
169 // preserve some of the original bits among those that are included in
170 // the register associated with that def. For example, if R0 is a 32-bit
171 // register, but a def can only change the lower 16 bits, then it will
172 // be marked as preserving.
173 // - Shadow: a reference that has duplicates holding additional reaching
174 // defs (see more below).
175 // - Clobbering: applied only to defs, indicates that the value generated
176 // by this def is unspecified. A typical example would be volatile registers
177 // after function calls.
178 // - Fixed: the register in this def/use cannot be replaced with any other
179 // register. A typical case would be a parameter register to a call, or
180 // the register with the return value from a function.
181 // - Undef: the register in this reference the register is assumed to have
182 // no pre-existing value, even if it appears to be reached by some def.
183 // This is typically used to prevent keeping registers artificially live
184 // in cases when they are defined via predicated instructions. For example:
185 // r0 = add-if-true cond, r10, r11 (1)
186 // r0 = add-if-false cond, r12, r13, r0<imp-use> (2)
188 // Before (1), r0 is not intended to be live, and the use of r0 in (3) is
189 // not meant to be reached by any def preceding (1). However, since the
190 // defs in (1) and (2) are both preserving, these properties alone would
191 // imply that the use in (3) may indeed be reached by some prior def.
192 // Adding Undef flag to the def in (1) prevents that. The Undef flag
193 // may be applied to both defs and uses.
194 // - Dead: applies only to defs. The value coming out of a "dead" def is
195 // assumed to be unused, even if the def appears to be reaching other defs
196 // or uses. The motivation for this flag comes from dead defs on function
197 // calls: there is no way to determine if such a def is dead without
198 // analyzing the target's ABI. Hence the graph should contain this info,
199 // as it is unavailable otherwise. On the other hand, a def without any
200 // uses on a typical instruction is not the intended target for this flag.
202 // *** Shadow references
204 // It may happen that a super-register can have two (or more) non-overlapping
205 // sub-registers. When both of these sub-registers are defined and followed
206 // by a use of the super-register, the use of the super-register will not
207 // have a unique reaching def: both defs of the sub-registers need to be
208 // accounted for. In such cases, a duplicate use of the super-register is
209 // added and it points to the extra reaching def. Both uses are marked with
210 // a flag "shadow". Example:
211 // Assume t0 is a super-register of r0 and r1, r0 and r1 do not overlap:
212 // set r0, 1 ; r0 = 1
213 // set r1, 1 ; r1 = 1
214 // addi t1, t0, 1 ; t1 = t0+1
217 // s1: set [d2<r0>(,,u9):]
218 // s3: set [d4<r1>(,,u10):]
219 // s5: addi [d6<t1>(,,):, u7"<t0>(d2):, u8"<t0>(d4):]
221 // The statement s5 has two use nodes for t0: u7" and u9". The quotation
222 // mark " indicates that the node is a shadow.
225 #ifndef LLVM_LIB_TARGET_HEXAGON_RDFGRAPH_H
226 #define LLVM_LIB_TARGET_HEXAGON_RDFGRAPH_H
228 #include "RDFRegisters.h"
229 #include "llvm/ADT/BitVector.h"
230 #include "llvm/ADT/STLExtras.h"
231 #include "llvm/MC/LaneBitmask.h"
232 #include "llvm/Support/Allocator.h"
233 #include "llvm/Support/MathExtras.h"
234 #include "llvm/Support/raw_ostream.h"
235 #include "llvm/Target/TargetRegisterInfo.h"
239 #include <functional>
242 #include <unordered_map>
246 // RDF uses uint32_t to refer to registers. This is to ensure that the type
247 // size remains specific. In other places, registers are often stored using
249 static_assert(sizeof(uint32_t) == sizeof(unsigned), "Those should be equal");
253 class MachineBasicBlock;
254 class MachineFunction;
256 class MachineOperand;
257 class MachineDominanceFrontier;
258 class MachineDominatorTree;
259 class TargetInstrInfo;
263 typedef uint32_t NodeId;
265 struct DataFlowGraph;
269 None = 0x0000, // Nothing
273 Code = 0x0001, // 01, Container
274 Ref = 0x0002, // 10, Reference
277 KindMask = 0x0007 << 2,
278 Def = 0x0001 << 2, // 001
279 Use = 0x0002 << 2, // 010
280 Phi = 0x0003 << 2, // 011
281 Stmt = 0x0004 << 2, // 100
282 Block = 0x0005 << 2, // 101
283 Func = 0x0006 << 2, // 110
285 // Flags: 7 bits for now
286 FlagMask = 0x007F << 5,
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.
296 static uint16_t type(uint16_t T) { return T & TypeMask; }
297 static uint16_t kind(uint16_t T) { return T & KindMask; }
298 static uint16_t flags(uint16_t T) { return T & FlagMask; }
300 static uint16_t set_type(uint16_t A, uint16_t T) {
301 return (A & ~TypeMask) | T;
304 static uint16_t set_kind(uint16_t A, uint16_t K) {
305 return (A & ~KindMask) | K;
308 static uint16_t set_flags(uint16_t A, uint16_t F) {
309 return (A & ~FlagMask) | F;
312 // Test if A contains B.
313 static bool contains(uint16_t A, uint16_t B) {
316 uint16_t KB = kind(B);
321 return KB == Phi || KB == Stmt;
324 return type(B) == Ref;
330 struct BuildOptions {
333 KeepDeadPhis = 0x01, // Do not remove dead phis during build.
337 template <typename T> struct NodeAddr {
338 NodeAddr() : Addr(nullptr) {}
339 NodeAddr(T A, NodeId I) : Addr(A), Id(I) {}
341 // Type cast (casting constructor). The reason for having this class
342 // instead of std::pair.
343 template <typename S> NodeAddr(const NodeAddr<S> &NA)
344 : Addr(static_cast<T>(NA.Addr)), Id(NA.Id) {}
346 bool operator== (const NodeAddr<T> &NA) const {
347 assert((Addr == NA.Addr) == (Id == NA.Id));
348 return Addr == NA.Addr;
350 bool operator!= (const NodeAddr<T> &NA) const {
351 return !operator==(NA);
360 // Fast memory allocation and translation between node id and node address.
361 // This is really the same idea as the one underlying the "bump pointer
362 // allocator", the difference being in the translation. A node id is
363 // composed of two components: the index of the block in which it was
364 // allocated, and the index within the block. With the default settings,
365 // where the number of nodes per block is 4096, the node id (minus 1) is:
367 // bit position: 11 0
368 // +----------------------------+--------------+
369 // | Index of the block |Index in block|
370 // +----------------------------+--------------+
372 // The actual node id is the above plus 1, to avoid creating a node id of 0.
374 // This method significantly improved the build time, compared to using maps
375 // (std::unordered_map or DenseMap) to translate between pointers and ids.
376 struct NodeAllocator {
377 // Amount of storage for a single node.
378 enum { NodeMemSize = 32 };
380 NodeAllocator(uint32_t NPB = 4096)
381 : NodesPerBlock(NPB), BitsPerIndex(Log2_32(NPB)),
382 IndexMask((1 << BitsPerIndex)-1) {
383 assert(isPowerOf2_32(NPB));
386 NodeBase *ptr(NodeId N) const {
388 uint32_t BlockN = N1 >> BitsPerIndex;
389 uint32_t Offset = (N1 & IndexMask) * NodeMemSize;
390 return reinterpret_cast<NodeBase*>(Blocks[BlockN]+Offset);
393 NodeId id(const NodeBase *P) const;
394 NodeAddr<NodeBase*> New();
398 void startNewBlock();
401 uint32_t makeId(uint32_t Block, uint32_t Index) const {
402 // Add 1 to the id, to avoid the id of 0, which is treated as "null".
403 return ((Block << BitsPerIndex) | Index) + 1;
406 const uint32_t NodesPerBlock;
407 const uint32_t BitsPerIndex;
408 const uint32_t IndexMask;
409 char *ActiveEnd = nullptr;
410 std::vector<char*> Blocks;
411 typedef BumpPtrAllocatorImpl<MallocAllocator, 65536> AllocatorTy;
415 typedef std::set<RegisterRef> RegisterSet;
417 struct TargetOperandInfo {
418 TargetOperandInfo(const TargetInstrInfo &tii) : TII(tii) {}
419 virtual ~TargetOperandInfo() = default;
421 virtual bool isPreserving(const MachineInstr &In, unsigned OpNum) const;
422 virtual bool isClobbering(const MachineInstr &In, unsigned OpNum) const;
423 virtual bool isFixedReg(const MachineInstr &In, unsigned OpNum) const;
425 const TargetInstrInfo &TII;
428 // Packed register reference. Only used for storage.
429 struct PackedRegisterRef {
434 struct LaneMaskIndex : private IndexedSet<LaneBitmask> {
435 LaneMaskIndex() = default;
437 LaneBitmask getLaneMaskForIndex(uint32_t K) const {
438 return K == 0 ? LaneBitmask::getAll() : get(K);
440 uint32_t getIndexForLaneMask(LaneBitmask LM) {
442 return LM.all() ? 0 : insert(LM);
444 uint32_t getIndexForLaneMask(LaneBitmask LM) const {
446 return LM.all() ? 0 : find(LM);
452 // Make sure this is a POD.
453 NodeBase() = default;
455 uint16_t getType() const { return NodeAttrs::type(Attrs); }
456 uint16_t getKind() const { return NodeAttrs::kind(Attrs); }
457 uint16_t getFlags() const { return NodeAttrs::flags(Attrs); }
458 NodeId getNext() const { return Next; }
460 uint16_t getAttrs() const { return Attrs; }
461 void setAttrs(uint16_t A) { Attrs = A; }
462 void setFlags(uint16_t F) { setAttrs(NodeAttrs::set_flags(getAttrs(), F)); }
464 // Insert node NA after "this" in the circular chain.
465 void append(NodeAddr<NodeBase*> NA);
466 // Initialize all members to 0.
467 void init() { memset(this, 0, sizeof *this); }
468 void setNext(NodeId N) { Next = N; }
473 NodeId Next; // Id of the next node in the circular chain.
474 // Definitions of nested types. Using anonymous nested structs would make
475 // this class definition clearer, but unnamed structs are not a part of
478 NodeId DD, DU; // Ids of the first reached def and use.
481 NodeId PredB; // Id of the predecessor block for a phi use.
484 void *CP; // Pointer to the actual code.
485 NodeId FirstM, LastM; // Id of the first member and last.
488 NodeId RD, Sib; // Ids of the reaching def and the sibling.
494 MachineOperand *Op; // Non-phi refs point to a machine operand.
495 PackedRegisterRef PR; // Phi refs store register info directly.
499 // The actual payload.
505 // The allocator allocates chunks of 32 bytes for each node. The fact that
506 // each node takes 32 bytes in memory is used for fast translation between
507 // the node id and the node address.
508 static_assert(sizeof(NodeBase) <= NodeAllocator::NodeMemSize,
509 "NodeBase must be at most NodeAllocator::NodeMemSize bytes");
511 // typedef std::vector<NodeAddr<NodeBase*>> NodeList;
512 typedef SmallVector<NodeAddr<NodeBase*>,4> NodeList;
513 typedef std::set<NodeId> NodeSet;
515 struct RefNode : public NodeBase {
518 RegisterRef getRegRef(const DataFlowGraph &G) const;
520 MachineOperand &getOp() {
521 assert(!(getFlags() & NodeAttrs::PhiRef));
525 void setRegRef(RegisterRef RR, DataFlowGraph &G);
526 void setRegRef(MachineOperand *Op, DataFlowGraph &G);
528 NodeId getReachingDef() const {
531 void setReachingDef(NodeId RD) {
535 NodeId getSibling() const {
538 void setSibling(NodeId Sib) {
543 assert(getType() == NodeAttrs::Ref);
544 return getKind() == NodeAttrs::Use;
548 assert(getType() == NodeAttrs::Ref);
549 return getKind() == NodeAttrs::Def;
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);
558 struct DefNode : public RefNode {
559 NodeId getReachedDef() const {
562 void setReachedDef(NodeId D) {
565 NodeId getReachedUse() const {
568 void setReachedUse(NodeId U) {
572 void linkToDef(NodeId Self, NodeAddr<DefNode*> DA);
575 struct UseNode : public RefNode {
576 void linkToDef(NodeId Self, NodeAddr<DefNode*> DA);
579 struct PhiUseNode : public UseNode {
580 NodeId getPredecessor() const {
581 assert(getFlags() & NodeAttrs::PhiRef);
582 return Ref.PhiU.PredB;
584 void setPredecessor(NodeId B) {
585 assert(getFlags() & NodeAttrs::PhiRef);
590 struct CodeNode : public NodeBase {
591 template <typename T> T getCode() const {
592 return static_cast<T>(Code.CP);
594 void setCode(void *C) {
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);
605 NodeList members(const DataFlowGraph &G) const;
606 template <typename Predicate>
607 NodeList members_if(Predicate P, const DataFlowGraph &G) const;
610 struct InstrNode : public CodeNode {
611 NodeAddr<NodeBase*> getOwner(const DataFlowGraph &G);
614 struct PhiNode : public InstrNode {
615 MachineInstr *getCode() const {
620 struct StmtNode : public InstrNode {
621 MachineInstr *getCode() const {
622 return CodeNode::getCode<MachineInstr*>();
626 struct BlockNode : public CodeNode {
627 MachineBasicBlock *getCode() const {
628 return CodeNode::getCode<MachineBasicBlock*>();
631 void addPhi(NodeAddr<PhiNode*> PA, const DataFlowGraph &G);
634 struct FuncNode : public CodeNode {
635 MachineFunction *getCode() const {
636 return CodeNode::getCode<MachineFunction*>();
639 NodeAddr<BlockNode*> findBlock(const MachineBasicBlock *BB,
640 const DataFlowGraph &G) const;
641 NodeAddr<BlockNode*> getEntryBlock(const DataFlowGraph &G);
644 struct DataFlowGraph {
645 DataFlowGraph(MachineFunction &mf, const TargetInstrInfo &tii,
646 const TargetRegisterInfo &tri, const MachineDominatorTree &mdt,
647 const MachineDominanceFrontier &mdf, const TargetOperandInfo &toi);
649 NodeBase *ptr(NodeId N) const;
650 template <typename T> T ptr(NodeId N) const {
651 return static_cast<T>(ptr(N));
654 NodeId id(const NodeBase *P) const;
656 template <typename T> NodeAddr<T> addr(NodeId N) const {
657 return { ptr<T>(N), N };
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; }
670 DefStack() = default;
672 bool empty() const { return Stack.empty() || top() == bottom(); }
675 typedef NodeAddr<DefNode*> value_type;
677 typedef DefStack::value_type value_type;
679 Iterator &up() { Pos = DS.nextUp(Pos); return *this; }
680 Iterator &down() { Pos = DS.nextDown(Pos); return *this; }
682 value_type operator*() const {
684 return DS.Stack[Pos-1];
686 const value_type *operator->() const {
688 return &DS.Stack[Pos-1];
690 bool operator==(const Iterator &It) const { return Pos == It.Pos; }
691 bool operator!=(const Iterator &It) const { return Pos != It.Pos; }
694 Iterator(const DefStack &S, bool Top);
696 // Pos-1 is the index in the StorageType object that corresponds to
697 // the top of the DefStack.
700 friend struct DefStack;
704 typedef Iterator iterator;
705 iterator top() const { return Iterator(*this, true); }
706 iterator bottom() const { return Iterator(*this, false); }
707 unsigned size() const;
709 void push(NodeAddr<DefNode*> DA) { Stack.push_back(DA); }
711 void start_block(NodeId N);
712 void clear_block(NodeId N);
715 friend struct Iterator;
716 typedef std::vector<value_type> StorageType;
718 bool isDelimiter(const StorageType::value_type &P, NodeId N = 0) const {
719 return (P.Addr == nullptr) && (N == 0 || P.Id == N);
722 unsigned nextUp(unsigned P) const;
723 unsigned nextDown(unsigned P) const;
728 // Make this std::unordered_map for speed of accessing elements.
729 // Map: Register (physical or virtual) -> DefStack
730 typedef std::unordered_map<RegisterId,DefStack> DefStackMap;
732 void build(unsigned Options = BuildOptions::None);
733 void pushAllDefs(NodeAddr<InstrNode*> IA, DefStackMap &DM);
734 void markBlock(NodeId B, DefStackMap &DefM);
735 void releaseBlock(NodeId B, DefStackMap &DefM);
737 PackedRegisterRef pack(RegisterRef RR) {
738 return { RR.Reg, LMI.getIndexForLaneMask(RR.Mask) };
740 PackedRegisterRef pack(RegisterRef RR) const {
741 return { RR.Reg, LMI.getIndexForLaneMask(RR.Mask) };
743 RegisterRef unpack(PackedRegisterRef PR) const {
744 return RegisterRef(PR.Reg, LMI.getLaneMaskForIndex(PR.MaskId));
747 RegisterRef makeRegRef(unsigned Reg, unsigned Sub) const;
748 RegisterRef makeRegRef(const MachineOperand &Op) const;
749 RegisterRef restrictRef(RegisterRef AR, RegisterRef BR) const;
751 NodeAddr<RefNode*> getNextRelated(NodeAddr<InstrNode*> IA,
752 NodeAddr<RefNode*> RA) const;
753 NodeAddr<RefNode*> getNextImp(NodeAddr<InstrNode*> IA,
754 NodeAddr<RefNode*> RA, bool Create);
755 NodeAddr<RefNode*> getNextImp(NodeAddr<InstrNode*> IA,
756 NodeAddr<RefNode*> RA) const;
757 NodeAddr<RefNode*> getNextShadow(NodeAddr<InstrNode*> IA,
758 NodeAddr<RefNode*> RA, bool Create);
759 NodeAddr<RefNode*> getNextShadow(NodeAddr<InstrNode*> IA,
760 NodeAddr<RefNode*> RA) const;
762 NodeList getRelatedRefs(NodeAddr<InstrNode*> IA,
763 NodeAddr<RefNode*> RA) const;
765 NodeAddr<BlockNode*> findBlock(MachineBasicBlock *BB) const {
766 return BlockNodes.at(BB);
769 void unlinkUse(NodeAddr<UseNode*> UA, bool RemoveFromOwner) {
775 void unlinkDef(NodeAddr<DefNode*> DA, bool RemoveFromOwner) {
781 // Some useful filters.
782 template <uint16_t Kind>
783 static bool IsRef(const NodeAddr<NodeBase*> BA) {
784 return BA.Addr->getType() == NodeAttrs::Ref &&
785 BA.Addr->getKind() == Kind;
788 template <uint16_t Kind>
789 static bool IsCode(const NodeAddr<NodeBase*> BA) {
790 return BA.Addr->getType() == NodeAttrs::Code &&
791 BA.Addr->getKind() == Kind;
794 static bool IsDef(const NodeAddr<NodeBase*> BA) {
795 return BA.Addr->getType() == NodeAttrs::Ref &&
796 BA.Addr->getKind() == NodeAttrs::Def;
799 static bool IsUse(const NodeAddr<NodeBase*> BA) {
800 return BA.Addr->getType() == NodeAttrs::Ref &&
801 BA.Addr->getKind() == NodeAttrs::Use;
804 static bool IsPhi(const NodeAddr<NodeBase*> BA) {
805 return BA.Addr->getType() == NodeAttrs::Code &&
806 BA.Addr->getKind() == NodeAttrs::Phi;
809 static bool IsPreservingDef(const NodeAddr<DefNode*> DA) {
810 uint16_t Flags = DA.Addr->getFlags();
811 return (Flags & NodeAttrs::Preserving) && !(Flags & NodeAttrs::Undef);
817 RegisterSet getLandingPadLiveIns() const;
819 NodeAddr<NodeBase*> newNode(uint16_t Attrs);
820 NodeAddr<NodeBase*> cloneNode(const NodeAddr<NodeBase*> B);
821 NodeAddr<UseNode*> newUse(NodeAddr<InstrNode*> Owner,
822 MachineOperand &Op, uint16_t Flags = NodeAttrs::None);
823 NodeAddr<PhiUseNode*> newPhiUse(NodeAddr<PhiNode*> Owner,
824 RegisterRef RR, NodeAddr<BlockNode*> PredB,
825 uint16_t Flags = NodeAttrs::PhiRef);
826 NodeAddr<DefNode*> newDef(NodeAddr<InstrNode*> Owner,
827 MachineOperand &Op, uint16_t Flags = NodeAttrs::None);
828 NodeAddr<DefNode*> newDef(NodeAddr<InstrNode*> Owner,
829 RegisterRef RR, uint16_t Flags = NodeAttrs::PhiRef);
830 NodeAddr<PhiNode*> newPhi(NodeAddr<BlockNode*> Owner);
831 NodeAddr<StmtNode*> newStmt(NodeAddr<BlockNode*> Owner,
833 NodeAddr<BlockNode*> newBlock(NodeAddr<FuncNode*> Owner,
834 MachineBasicBlock *BB);
835 NodeAddr<FuncNode*> newFunc(MachineFunction *MF);
837 template <typename Predicate>
838 std::pair<NodeAddr<RefNode*>,NodeAddr<RefNode*>>
839 locateNextRef(NodeAddr<InstrNode*> IA, NodeAddr<RefNode*> RA,
842 typedef std::map<NodeId,RegisterSet> BlockRefsMap;
844 void buildStmt(NodeAddr<BlockNode*> BA, MachineInstr &In);
845 void buildBlockRefs(NodeAddr<BlockNode*> BA, BlockRefsMap &RefM);
846 void recordDefsForDF(BlockRefsMap &PhiM, BlockRefsMap &RefM,
847 NodeAddr<BlockNode*> BA);
848 void buildPhis(BlockRefsMap &PhiM, BlockRefsMap &RefM,
849 NodeAddr<BlockNode*> BA);
850 void removeUnusedPhis();
852 void pushClobbers(NodeAddr<InstrNode*> IA, DefStackMap &DM);
853 void pushDefs(NodeAddr<InstrNode*> IA, DefStackMap &DM);
854 template <typename T> void linkRefUp(NodeAddr<InstrNode*> IA,
855 NodeAddr<T> TA, DefStack &DS);
856 template <typename Predicate> void linkStmtRefs(DefStackMap &DefM,
857 NodeAddr<StmtNode*> SA, Predicate P);
858 void linkBlockRefs(DefStackMap &DefM, NodeAddr<BlockNode*> BA);
860 void unlinkUseDF(NodeAddr<UseNode*> UA);
861 void unlinkDefDF(NodeAddr<DefNode*> DA);
863 void removeFromOwner(NodeAddr<RefNode*> RA) {
864 NodeAddr<InstrNode*> IA = RA.Addr->getOwner(*this);
865 IA.Addr->removeMember(RA, *this);
869 const TargetInstrInfo &TII;
870 const TargetRegisterInfo &TRI;
871 const PhysicalRegisterInfo PRI;
872 const MachineDominatorTree &MDT;
873 const MachineDominanceFrontier &MDF;
874 const TargetOperandInfo &TOI;
876 RegisterAggr LiveIns;
877 NodeAddr<FuncNode*> Func;
878 NodeAllocator Memory;
879 // Local map: MachineBasicBlock -> NodeAddr<BlockNode*>
880 std::map<MachineBasicBlock*,NodeAddr<BlockNode*>> BlockNodes;
883 }; // struct DataFlowGraph
885 template <typename Predicate>
886 NodeAddr<RefNode*> RefNode::getNextRef(RegisterRef RR, Predicate P,
887 bool NextOnly, const DataFlowGraph &G) {
888 // Get the "Next" reference in the circular list that references RR and
889 // satisfies predicate "Pred".
890 auto NA = G.addr<NodeBase*>(getNext());
892 while (NA.Addr != this) {
893 if (NA.Addr->getType() == NodeAttrs::Ref) {
894 NodeAddr<RefNode*> RA = NA;
895 if (RA.Addr->getRegRef(G) == RR && P(NA))
899 NA = G.addr<NodeBase*>(NA.Addr->getNext());
901 // We've hit the beginning of the chain.
902 assert(NA.Addr->getType() == NodeAttrs::Code);
903 NodeAddr<CodeNode*> CA = NA;
904 NA = CA.Addr->getFirstMember(G);
907 // Return the equivalent of "nullptr" if such a node was not found.
908 return NodeAddr<RefNode*>();
911 template <typename Predicate>
912 NodeList CodeNode::members_if(Predicate P, const DataFlowGraph &G) const {
914 auto M = getFirstMember(G);
918 while (M.Addr != this) {
921 M = G.addr<NodeBase*>(M.Addr->getNext());
927 template <typename T> struct Print;
928 template <typename T>
929 raw_ostream &operator<< (raw_ostream &OS, const Print<T> &P);
931 template <typename T>
933 Print(const T &x, const DataFlowGraph &g) : Obj(x), G(g) {}
935 const DataFlowGraph &G;
938 template <typename T>
939 struct PrintNode : Print<NodeAddr<T>> {
940 PrintNode(const NodeAddr<T> &x, const DataFlowGraph &g)
941 : Print<NodeAddr<T>>(x, g) {}
944 } // end namespace rdf
946 } // end namespace llvm
948 #endif // LLVM_LIB_TARGET_HEXAGON_RDFGRAPH_H