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