LLVM 17.0.0git
RDFGraph.h
Go to the documentation of this file.
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/SmallVector.h"
229#include "llvm/MC/LaneBitmask.h"
232#include <cassert>
233#include <cstdint>
234#include <cstring>
235#include <map>
236#include <memory>
237#include <set>
238#include <unordered_map>
239#include <utility>
240#include <vector>
241
242// RDF uses uint32_t to refer to registers. This is to ensure that the type
243// size remains specific. In other places, registers are often stored using
244// unsigned.
245static_assert(sizeof(uint32_t) == sizeof(unsigned), "Those should be equal");
246
247namespace llvm {
248
249class MachineBasicBlock;
250class MachineDominanceFrontier;
251class MachineDominatorTree;
252class MachineFunction;
253class MachineInstr;
254class MachineOperand;
255class raw_ostream;
256class TargetInstrInfo;
257class TargetRegisterInfo;
258
259namespace rdf {
260
262
263 struct DataFlowGraph;
264
265 struct NodeAttrs {
266 enum : uint16_t {
267 None = 0x0000, // Nothing
268
269 // Types: 2 bits
270 TypeMask = 0x0003,
271 Code = 0x0001, // 01, Container
272 Ref = 0x0002, // 10, Reference
273
274 // Kind: 3 bits
275 KindMask = 0x0007 << 2,
276 Def = 0x0001 << 2, // 001
277 Use = 0x0002 << 2, // 010
278 Phi = 0x0003 << 2, // 011
279 Stmt = 0x0004 << 2, // 100
280 Block = 0x0005 << 2, // 101
281 Func = 0x0006 << 2, // 110
282
283 // Flags: 7 bits for now
284 FlagMask = 0x007F << 5,
285 Shadow = 0x0001 << 5, // 0000001, Has extra reaching defs.
286 Clobbering = 0x0002 << 5, // 0000010, Produces unspecified values.
287 PhiRef = 0x0004 << 5, // 0000100, Member of PhiNode.
288 Preserving = 0x0008 << 5, // 0001000, Def can keep original bits.
289 Fixed = 0x0010 << 5, // 0010000, Fixed register.
290 Undef = 0x0020 << 5, // 0100000, Has no pre-existing value.
291 Dead = 0x0040 << 5, // 1000000, Does not define a value.
292 };
293
294 static uint16_t type(uint16_t T) { return T & TypeMask; }
295 static uint16_t kind(uint16_t T) { return T & KindMask; }
296 static uint16_t flags(uint16_t T) { return T & FlagMask; }
297
299 return (A & ~TypeMask) | T;
300 }
301
303 return (A & ~KindMask) | K;
304 }
305
307 return (A & ~FlagMask) | F;
308 }
309
310 // Test if A contains B.
311 static bool contains(uint16_t A, uint16_t B) {
312 if (type(A) != Code)
313 return false;
314 uint16_t KB = kind(B);
315 switch (kind(A)) {
316 case Func:
317 return KB == Block;
318 case Block:
319 return KB == Phi || KB == Stmt;
320 case Phi:
321 case Stmt:
322 return type(B) == Ref;
323 }
324 return false;
325 }
326 };
327
329 enum : unsigned {
330 None = 0x00,
331 KeepDeadPhis = 0x01, // Do not remove dead phis during build.
332 };
333 };
334
335 template <typename T> struct NodeAddr {
336 NodeAddr() = default;
338
339 // Type cast (casting constructor). The reason for having this class
340 // instead of std::pair.
341 template <typename S> NodeAddr(const NodeAddr<S> &NA)
342 : Addr(static_cast<T>(NA.Addr)), Id(NA.Id) {}
343
344 bool operator== (const NodeAddr<T> &NA) const {
345 assert((Addr == NA.Addr) == (Id == NA.Id));
346 return Addr == NA.Addr;
347 }
348 bool operator!= (const NodeAddr<T> &NA) const {
349 return !operator==(NA);
350 }
351
352 T Addr = nullptr;
354 };
355
356 struct NodeBase;
357
358 // Fast memory allocation and translation between node id and node address.
359 // This is really the same idea as the one underlying the "bump pointer
360 // allocator", the difference being in the translation. A node id is
361 // composed of two components: the index of the block in which it was
362 // allocated, and the index within the block. With the default settings,
363 // where the number of nodes per block is 4096, the node id (minus 1) is:
364 //
365 // bit position: 11 0
366 // +----------------------------+--------------+
367 // | Index of the block |Index in block|
368 // +----------------------------+--------------+
369 //
370 // The actual node id is the above plus 1, to avoid creating a node id of 0.
371 //
372 // This method significantly improved the build time, compared to using maps
373 // (std::unordered_map or DenseMap) to translate between pointers and ids.
375 // Amount of storage for a single node.
376 enum { NodeMemSize = 32 };
377
379 : NodesPerBlock(NPB), BitsPerIndex(Log2_32(NPB)),
380 IndexMask((1 << BitsPerIndex)-1) {
381 assert(isPowerOf2_32(NPB));
382 }
383
385 uint32_t N1 = N-1;
386 uint32_t BlockN = N1 >> BitsPerIndex;
387 uint32_t Offset = (N1 & IndexMask) * NodeMemSize;
388 return reinterpret_cast<NodeBase*>(Blocks[BlockN]+Offset);
389 }
390
391 NodeId id(const NodeBase *P) const;
393 void clear();
394
395 private:
396 void startNewBlock();
397 bool needNewBlock();
398
399 uint32_t makeId(uint32_t Block, uint32_t Index) const {
400 // Add 1 to the id, to avoid the id of 0, which is treated as "null".
401 return ((Block << BitsPerIndex) | Index) + 1;
402 }
403
404 const uint32_t NodesPerBlock;
405 const uint32_t BitsPerIndex;
406 const uint32_t IndexMask;
407 char *ActiveEnd = nullptr;
408 std::vector<char*> Blocks;
410 AllocatorTy MemPool;
411 };
412
413 using RegisterSet = std::set<RegisterRef>;
414
417 virtual ~TargetOperandInfo() = default;
418
419 virtual bool isPreserving(const MachineInstr &In, unsigned OpNum) const;
420 virtual bool isClobbering(const MachineInstr &In, unsigned OpNum) const;
421 virtual bool isFixedReg(const MachineInstr &In, unsigned OpNum) const;
422
424 };
425
426 // Packed register reference. Only used for storage.
430 };
431
432 struct LaneMaskIndex : private IndexedSet<LaneBitmask> {
433 LaneMaskIndex() = default;
434
436 return K == 0 ? LaneBitmask::getAll() : get(K);
437 }
438
440 assert(LM.any());
441 return LM.all() ? 0 : insert(LM);
442 }
443
445 assert(LM.any());
446 return LM.all() ? 0 : find(LM);
447 }
448 };
449
450 struct NodeBase {
451 public:
452 // Make sure this is a POD.
453 NodeBase() = default;
454
458 NodeId getNext() const { return Next; }
459
460 uint16_t getAttrs() const { return Attrs; }
461 void setAttrs(uint16_t A) { Attrs = A; }
463
464 // Insert node NA after "this" in the circular chain.
466
467 // Initialize all members to 0.
468 void init() { memset(this, 0, sizeof *this); }
469
470 void setNext(NodeId N) { Next = N; }
471
472 protected:
475 NodeId Next; // Id of the next node in the circular chain.
476 // Definitions of nested types. Using anonymous nested structs would make
477 // this class definition clearer, but unnamed structs are not a part of
478 // the standard.
479 struct Def_struct {
480 NodeId DD, DU; // Ids of the first reached def and use.
481 };
482 struct PhiU_struct {
483 NodeId PredB; // Id of the predecessor block for a phi use.
484 };
485 struct Code_struct {
486 void *CP; // Pointer to the actual code.
487 NodeId FirstM, LastM; // Id of the first member and last.
488 };
489 struct Ref_struct {
490 NodeId RD, Sib; // Ids of the reaching def and the sibling.
491 union {
494 };
495 union {
496 MachineOperand *Op; // Non-phi refs point to a machine operand.
497 PackedRegisterRef PR; // Phi refs store register info directly.
498 };
499 };
500
501 // The actual payload.
502 union {
505 };
506 };
507 // The allocator allocates chunks of 32 bytes for each node. The fact that
508 // each node takes 32 bytes in memory is used for fast translation between
509 // the node id and the node address.
510 static_assert(sizeof(NodeBase) <= NodeAllocator::NodeMemSize,
511 "NodeBase must be at most NodeAllocator::NodeMemSize bytes");
512
514 using NodeSet = std::set<NodeId>;
515
516 struct RefNode : public NodeBase {
517 RefNode() = default;
518
519 RegisterRef getRegRef(const DataFlowGraph &G) const;
520
523 return *Ref.Op;
524 }
525
528
530 return Ref.RD;
531 }
533 Ref.RD = RD;
534 }
535
537 return Ref.Sib;
538 }
539 void setSibling(NodeId Sib) {
540 Ref.Sib = Sib;
541 }
542
543 bool isUse() const {
545 return getKind() == NodeAttrs::Use;
546 }
547
548 bool isDef() const {
550 return getKind() == NodeAttrs::Def;
551 }
552
553 template <typename Predicate>
554 NodeAddr<RefNode*> getNextRef(RegisterRef RR, Predicate P, bool NextOnly,
555 const DataFlowGraph &G);
557 };
558
559 struct DefNode : public RefNode {
561 return Ref.Def.DD;
562 }
564 Ref.Def.DD = D;
565 }
567 return Ref.Def.DU;
568 }
570 Ref.Def.DU = U;
571 }
572
573 void linkToDef(NodeId Self, NodeAddr<DefNode*> DA);
574 };
575
576 struct UseNode : public RefNode {
577 void linkToDef(NodeId Self, NodeAddr<DefNode*> DA);
578 };
579
580 struct PhiUseNode : public UseNode {
583 return Ref.PhiU.PredB;
584 }
587 Ref.PhiU.PredB = B;
588 }
589 };
590
591 struct CodeNode : public NodeBase {
592 template <typename T> T getCode() const {
593 return static_cast<T>(Code.CP);
594 }
595 void setCode(void *C) {
596 Code.CP = C;
597 }
598
603 const DataFlowGraph &G);
605
606 NodeList members(const DataFlowGraph &G) const;
607 template <typename Predicate>
608 NodeList members_if(Predicate P, const DataFlowGraph &G) const;
609 };
610
611 struct InstrNode : public CodeNode {
613 };
614
615 struct PhiNode : public InstrNode {
617 return nullptr;
618 }
619 };
620
621 struct StmtNode : public InstrNode {
623 return CodeNode::getCode<MachineInstr*>();
624 }
625 };
626
627 struct BlockNode : public CodeNode {
629 return CodeNode::getCode<MachineBasicBlock*>();
630 }
631
632 void addPhi(NodeAddr<PhiNode*> PA, const DataFlowGraph &G);
633 };
634
635 struct FuncNode : public CodeNode {
637 return CodeNode::getCode<MachineFunction*>();
638 }
639
641 const DataFlowGraph &G) const;
643 };
644
647 const TargetRegisterInfo &tri, const MachineDominatorTree &mdt,
648 const MachineDominanceFrontier &mdf);
650 const TargetRegisterInfo &tri, const MachineDominatorTree &mdt,
651 const MachineDominanceFrontier &mdf, const TargetOperandInfo &toi);
652
653 NodeBase *ptr(NodeId N) const;
654 template <typename T> T ptr(NodeId N) const {
655 return static_cast<T>(ptr(N));
656 }
657
658 NodeId id(const NodeBase *P) const;
659
660 template <typename T> NodeAddr<T> addr(NodeId N) const {
661 return { ptr<T>(N), N };
662 }
663
664 NodeAddr<FuncNode*> getFunc() const { return Func; }
665 MachineFunction &getMF() const { return MF; }
666 const TargetInstrInfo &getTII() const { return TII; }
667 const TargetRegisterInfo &getTRI() const { return TRI; }
668 const PhysicalRegisterInfo &getPRI() const { return PRI; }
669 const MachineDominatorTree &getDT() const { return MDT; }
670 const MachineDominanceFrontier &getDF() const { return MDF; }
671 const RegisterAggr &getLiveIns() const { return LiveIns; }
672
673 struct DefStack {
674 DefStack() = default;
675
676 bool empty() const { return Stack.empty() || top() == bottom(); }
677
678 private:
679 using value_type = NodeAddr<DefNode *>;
680 struct Iterator {
681 using value_type = DefStack::value_type;
682
683 Iterator &up() { Pos = DS.nextUp(Pos); return *this; }
684 Iterator &down() { Pos = DS.nextDown(Pos); return *this; }
685
686 value_type operator*() const {
687 assert(Pos >= 1);
688 return DS.Stack[Pos-1];
689 }
690 const value_type *operator->() const {
691 assert(Pos >= 1);
692 return &DS.Stack[Pos-1];
693 }
694 bool operator==(const Iterator &It) const { return Pos == It.Pos; }
695 bool operator!=(const Iterator &It) const { return Pos != It.Pos; }
696
697 private:
698 friend struct DefStack;
699
700 Iterator(const DefStack &S, bool Top);
701
702 // Pos-1 is the index in the StorageType object that corresponds to
703 // the top of the DefStack.
704 const DefStack &DS;
705 unsigned Pos;
706 };
707
708 public:
710
711 iterator top() const { return Iterator(*this, true); }
712 iterator bottom() const { return Iterator(*this, false); }
713 unsigned size() const;
714
715 void push(NodeAddr<DefNode*> DA) { Stack.push_back(DA); }
716 void pop();
717 void start_block(NodeId N);
718 void clear_block(NodeId N);
719
720 private:
721 friend struct Iterator;
722
723 using StorageType = std::vector<value_type>;
724
725 bool isDelimiter(const StorageType::value_type &P, NodeId N = 0) const {
726 return (P.Addr == nullptr) && (N == 0 || P.Id == N);
727 }
728
729 unsigned nextUp(unsigned P) const;
730 unsigned nextDown(unsigned P) const;
731
732 StorageType Stack;
733 };
734
735 // Make this std::unordered_map for speed of accessing elements.
736 // Map: Register (physical or virtual) -> DefStack
737 using DefStackMap = std::unordered_map<RegisterId, DefStack>;
738
739 void build(unsigned Options = BuildOptions::None);
741 void markBlock(NodeId B, DefStackMap &DefM);
742 void releaseBlock(NodeId B, DefStackMap &DefM);
743
745 return { RR.Reg, LMI.getIndexForLaneMask(RR.Mask) };
746 }
748 return { RR.Reg, LMI.getIndexForLaneMask(RR.Mask) };
749 }
751 return RegisterRef(PR.Reg, LMI.getLaneMaskForIndex(PR.MaskId));
752 }
753
754 RegisterRef makeRegRef(unsigned Reg, unsigned Sub) const;
755 RegisterRef makeRegRef(const MachineOperand &Op) const;
756
758 NodeAddr<RefNode*> RA) const;
760 NodeAddr<RefNode*> RA, bool Create);
762 NodeAddr<RefNode*> RA) const;
763
765 NodeAddr<RefNode*> RA) const;
766
768 return BlockNodes.at(BB);
769 }
770
771 void unlinkUse(NodeAddr<UseNode*> UA, bool RemoveFromOwner) {
772 unlinkUseDF(UA);
773 if (RemoveFromOwner)
774 removeFromOwner(UA);
775 }
776
777 void unlinkDef(NodeAddr<DefNode*> DA, bool RemoveFromOwner) {
778 unlinkDefDF(DA);
779 if (RemoveFromOwner)
780 removeFromOwner(DA);
781 }
782
783 // Some useful filters.
784 template <uint16_t Kind>
785 static bool IsRef(const NodeAddr<NodeBase*> BA) {
786 return BA.Addr->getType() == NodeAttrs::Ref &&
787 BA.Addr->getKind() == Kind;
788 }
789
790 template <uint16_t Kind>
791 static bool IsCode(const NodeAddr<NodeBase*> BA) {
792 return BA.Addr->getType() == NodeAttrs::Code &&
793 BA.Addr->getKind() == Kind;
794 }
795
796 static bool IsDef(const NodeAddr<NodeBase*> BA) {
797 return BA.Addr->getType() == NodeAttrs::Ref &&
798 BA.Addr->getKind() == NodeAttrs::Def;
799 }
800
801 static bool IsUse(const NodeAddr<NodeBase*> BA) {
802 return BA.Addr->getType() == NodeAttrs::Ref &&
803 BA.Addr->getKind() == NodeAttrs::Use;
804 }
805
806 static bool IsPhi(const NodeAddr<NodeBase*> BA) {
807 return BA.Addr->getType() == NodeAttrs::Code &&
808 BA.Addr->getKind() == NodeAttrs::Phi;
809 }
810
811 static bool IsPreservingDef(const NodeAddr<DefNode*> DA) {
812 uint16_t Flags = DA.Addr->getFlags();
813 return (Flags & NodeAttrs::Preserving) && !(Flags & NodeAttrs::Undef);
814 }
815
816 private:
817 void reset();
818
819 RegisterSet getLandingPadLiveIns() const;
820
821 NodeAddr<NodeBase*> newNode(uint16_t Attrs);
838
839 template <typename Predicate>
840 std::pair<NodeAddr<RefNode*>,NodeAddr<RefNode*>>
842 Predicate P) const;
843
844 using BlockRefsMap = std::map<NodeId, RegisterSet>;
845
846 void buildStmt(NodeAddr<BlockNode*> BA, MachineInstr &In);
847 void recordDefsForDF(BlockRefsMap &PhiM, NodeAddr<BlockNode*> BA);
848 void buildPhis(BlockRefsMap &PhiM, RegisterSet &AllRefs,
850 void removeUnusedPhis();
851
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);
859
860 void unlinkUseDF(NodeAddr<UseNode*> UA);
861 void unlinkDefDF(NodeAddr<DefNode*> DA);
862
863 void removeFromOwner(NodeAddr<RefNode*> RA) {
864 NodeAddr<InstrNode*> IA = RA.Addr->getOwner(*this);
865 IA.Addr->removeMember(RA, *this);
866 }
867
868 // Default TOI object, if not given in the constructor.
869 std::unique_ptr<TargetOperandInfo> DefaultTOI;
870
871 MachineFunction &MF;
872 const TargetInstrInfo &TII;
873 const TargetRegisterInfo &TRI;
874 const PhysicalRegisterInfo PRI;
875 const MachineDominatorTree &MDT;
876 const MachineDominanceFrontier &MDF;
877 const TargetOperandInfo &TOI;
878
879 RegisterAggr LiveIns;
880 NodeAddr<FuncNode*> Func;
881 NodeAllocator Memory;
882 // Local map: MachineBasicBlock -> NodeAddr<BlockNode*>
883 std::map<MachineBasicBlock*,NodeAddr<BlockNode*>> BlockNodes;
884 // Lane mask map.
885 LaneMaskIndex LMI;
886 }; // struct DataFlowGraph
887
888 template <typename Predicate>
890 bool NextOnly, const DataFlowGraph &G) {
891 // Get the "Next" reference in the circular list that references RR and
892 // satisfies predicate "Pred".
893 auto NA = G.addr<NodeBase*>(getNext());
894
895 while (NA.Addr != this) {
896 if (NA.Addr->getType() == NodeAttrs::Ref) {
898 if (RA.Addr->getRegRef(G) == RR && P(NA))
899 return NA;
900 if (NextOnly)
901 break;
902 NA = G.addr<NodeBase*>(NA.Addr->getNext());
903 } else {
904 // We've hit the beginning of the chain.
905 assert(NA.Addr->getType() == NodeAttrs::Code);
906 NodeAddr<CodeNode*> CA = NA;
907 NA = CA.Addr->getFirstMember(G);
908 }
909 }
910 // Return the equivalent of "nullptr" if such a node was not found.
911 return NodeAddr<RefNode*>();
912 }
913
914 template <typename Predicate>
915 NodeList CodeNode::members_if(Predicate P, const DataFlowGraph &G) const {
916 NodeList MM;
917 auto M = getFirstMember(G);
918 if (M.Id == 0)
919 return MM;
920
921 while (M.Addr != this) {
922 if (P(M))
923 MM.push_back(M);
924 M = G.addr<NodeBase*>(M.Addr->getNext());
925 }
926 return MM;
927 }
928
929 template <typename T>
930 struct Print {
931 Print(const T &x, const DataFlowGraph &g) : Obj(x), G(g) {}
932
933 const T &Obj;
935 };
936
937 template <typename T> Print(const T &, const DataFlowGraph &) -> Print<T>;
938
939 template <typename T>
940 struct PrintNode : Print<NodeAddr<T>> {
942 : Print<NodeAddr<T>>(x, g) {}
943 };
944
945 raw_ostream &operator<<(raw_ostream &OS, const Print<RegisterRef> &P);
946 raw_ostream &operator<<(raw_ostream &OS, const Print<NodeId> &P);
947 raw_ostream &operator<<(raw_ostream &OS, const Print<NodeAddr<DefNode *>> &P);
948 raw_ostream &operator<<(raw_ostream &OS, const Print<NodeAddr<UseNode *>> &P);
950 const Print<NodeAddr<PhiUseNode *>> &P);
951 raw_ostream &operator<<(raw_ostream &OS, const Print<NodeAddr<RefNode *>> &P);
952 raw_ostream &operator<<(raw_ostream &OS, const Print<NodeList> &P);
953 raw_ostream &operator<<(raw_ostream &OS, const Print<NodeSet> &P);
954 raw_ostream &operator<<(raw_ostream &OS, const Print<NodeAddr<PhiNode *>> &P);
956 const Print<NodeAddr<StmtNode *>> &P);
958 const Print<NodeAddr<InstrNode *>> &P);
960 const Print<NodeAddr<BlockNode *>> &P);
962 const Print<NodeAddr<FuncNode *>> &P);
963 raw_ostream &operator<<(raw_ostream &OS, const Print<RegisterSet> &P);
964 raw_ostream &operator<<(raw_ostream &OS, const Print<RegisterAggr> &P);
966 const Print<DataFlowGraph::DefStack> &P);
967
968} // end namespace rdf
969
970} // end namespace llvm
971
972#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
IRTranslator LLVM IR MI
static LVOptions Options
Definition: LVOptions.cpp:25
A common definition of LaneBitmask for use in TableGen and CodeGen.
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
#define G(x, y, z)
Definition: MD5.cpp:56
unsigned const TargetRegisterInfo * TRI
unsigned Reg
#define T
#define P(N)
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)
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:66
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
Representation of each machine instruction.
Definition: MachineInstr.h:68
MachineOperand class - Representation of each machine instruction operand.
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
TargetInstrInfo - Interface to description of machine instruction set.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
This class provides various memory handling functions that manipulate MemoryBlock instances.
Definition: Memory.h:52
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
std::set< RegisterRef > RegisterSet
Definition: RDFGraph.h:413
uint32_t NodeId
Definition: RDFGraph.h:261
raw_ostream & operator<<(raw_ostream &OS, const Print< RegisterRef > &P)
Definition: RDFGraph.cpp:55
std::set< NodeId > NodeSet
Definition: RDFGraph.h:514
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ Offset
Definition: DWP.cpp:406
APInt operator*(APInt a, uint64_t RHS)
Definition: APInt.h:2162
bool operator!=(uint64_t V1, const APInt &V2)
Definition: APInt.h:2040
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.
Definition: MathExtras.h:373
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
Definition: MathExtras.h:288
#define N
static constexpr LaneBitmask getAll()
Definition: LaneBitmask.h:82
constexpr bool any() const
Definition: LaneBitmask.h:53
constexpr bool all() const
Definition: LaneBitmask.h:54
MachineBasicBlock * getCode() const
Definition: RDFGraph.h:628
void addPhi(NodeAddr< PhiNode * > PA, const DataFlowGraph &G)
Definition: RDFGraph.cpp:544
NodeList members_if(Predicate P, const DataFlowGraph &G) const
Definition: RDFGraph.h:915
void removeMember(NodeAddr< NodeBase * > NA, const DataFlowGraph &G)
Definition: RDFGraph.cpp:493
void addMemberAfter(NodeAddr< NodeBase * > MA, NodeAddr< NodeBase * > NA, const DataFlowGraph &G)
Definition: RDFGraph.cpp:485
NodeAddr< NodeBase * > getLastMember(const DataFlowGraph &G) const
Definition: RDFGraph.cpp:465
NodeAddr< NodeBase * > getFirstMember(const DataFlowGraph &G) const
Definition: RDFGraph.cpp:458
NodeList members(const DataFlowGraph &G) const
Definition: RDFGraph.cpp:525
void setCode(void *C)
Definition: RDFGraph.h:595
void addMember(NodeAddr< NodeBase * > NA, const DataFlowGraph &G)
Definition: RDFGraph.cpp:472
T getCode() const
Definition: RDFGraph.h:592
void push(NodeAddr< DefNode * > DA)
Definition: RDFGraph.h:715
const RegisterAggr & getLiveIns() const
Definition: RDFGraph.h:671
PackedRegisterRef pack(RegisterRef RR)
Definition: RDFGraph.h:744
NodeAddr< FuncNode * > getFunc() const
Definition: RDFGraph.h:664
NodeAddr< BlockNode * > findBlock(MachineBasicBlock *BB) const
Definition: RDFGraph.h:767
void releaseBlock(NodeId B, DefStackMap &DefM)
Definition: RDFGraph.cpp:991
RegisterRef unpack(PackedRegisterRef PR) const
Definition: RDFGraph.h:750
void markBlock(NodeId B, DefStackMap &DefM)
Definition: RDFGraph.cpp:984
NodeAddr< RefNode * > getNextShadow(NodeAddr< InstrNode * > IA, NodeAddr< RefNode * > RA, bool Create)
Definition: RDFGraph.cpp:1201
static bool IsPreservingDef(const NodeAddr< DefNode * > DA)
Definition: RDFGraph.h:811
const MachineDominanceFrontier & getDF() const
Definition: RDFGraph.h:670
static bool IsRef(const NodeAddr< NodeBase * > BA)
Definition: RDFGraph.h:785
const MachineDominatorTree & getDT() const
Definition: RDFGraph.h:669
MachineFunction & getMF() const
Definition: RDFGraph.h:665
const TargetInstrInfo & getTII() const
Definition: RDFGraph.h:666
void unlinkUse(NodeAddr< UseNode * > UA, bool RemoveFromOwner)
Definition: RDFGraph.h:771
static bool IsPhi(const NodeAddr< NodeBase * > BA)
Definition: RDFGraph.h:806
NodeId id(const NodeBase *P) const
Definition: RDFGraph.cpp:774
PackedRegisterRef pack(RegisterRef RR) const
Definition: RDFGraph.h:747
T ptr(NodeId N) const
Definition: RDFGraph.h:654
static bool IsUse(const NodeAddr< NodeBase * > BA)
Definition: RDFGraph.h:801
RegisterRef makeRegRef(unsigned Reg, unsigned Sub) const
Definition: RDFGraph.cpp:967
static bool IsDef(const NodeAddr< NodeBase * > BA)
Definition: RDFGraph.h:796
const PhysicalRegisterInfo & getPRI() const
Definition: RDFGraph.h:668
static bool IsCode(const NodeAddr< NodeBase * > BA)
Definition: RDFGraph.h:791
void unlinkDef(NodeAddr< DefNode * > DA, bool RemoveFromOwner)
Definition: RDFGraph.h:777
void build(unsigned Options=BuildOptions::None)
Definition: RDFGraph.cpp:869
NodeBase * ptr(NodeId N) const
Definition: RDFGraph.cpp:767
void pushAllDefs(NodeAddr< InstrNode * > IA, DefStackMap &DM)
Definition: RDFGraph.cpp:1009
NodeList getRelatedRefs(NodeAddr< InstrNode * > IA, NodeAddr< RefNode * > RA) const
Definition: RDFGraph.cpp:1114
NodeAddr< RefNode * > getNextRelated(NodeAddr< InstrNode * > IA, NodeAddr< RefNode * > RA) const
Definition: RDFGraph.cpp:1140
std::unordered_map< RegisterId, DefStack > DefStackMap
Definition: RDFGraph.h:737
const TargetRegisterInfo & getTRI() const
Definition: RDFGraph.h:667
NodeAddr< T > addr(NodeId N) const
Definition: RDFGraph.h:660
NodeId getReachedUse() const
Definition: RDFGraph.h:566
void linkToDef(NodeId Self, NodeAddr< DefNode * > DA)
Definition: RDFGraph.cpp:444
void setReachedUse(NodeId U)
Definition: RDFGraph.h:569
void setReachedDef(NodeId D)
Definition: RDFGraph.h:563
NodeId getReachedDef() const
Definition: RDFGraph.h:560
MachineFunction * getCode() const
Definition: RDFGraph.h:636
NodeAddr< BlockNode * > getEntryBlock(const DataFlowGraph &G)
Definition: RDFGraph.cpp:586
NodeAddr< BlockNode * > findBlock(const MachineBasicBlock *BB, const DataFlowGraph &G) const
Definition: RDFGraph.cpp:574
LaneBitmask get(uint32_t Idx) const
Definition: RDFRegisters.h:39
uint32_t insert(LaneBitmask Val)
Definition: RDFRegisters.h:45
uint32_t find(LaneBitmask Val) const
Definition: RDFRegisters.h:54
NodeAddr< NodeBase * > getOwner(const DataFlowGraph &G)
Definition: RDFGraph.cpp:531
uint32_t getIndexForLaneMask(LaneBitmask LM) const
Definition: RDFGraph.h:444
LaneBitmask getLaneMaskForIndex(uint32_t K) const
Definition: RDFGraph.h:435
uint32_t getIndexForLaneMask(LaneBitmask LM)
Definition: RDFGraph.h:439
NodeAddr(const NodeAddr< S > &NA)
Definition: RDFGraph.h:341
bool operator==(const NodeAddr< T > &NA) const
Definition: RDFGraph.h:344
NodeAddr(T A, NodeId I)
Definition: RDFGraph.h:337
bool operator!=(const NodeAddr< T > &NA) const
Definition: RDFGraph.h:348
NodeBase * ptr(NodeId N) const
Definition: RDFGraph.h:384
NodeId id(const NodeBase *P) const
Definition: RDFGraph.cpp:375
NodeAddr< NodeBase * > New()
Definition: RDFGraph.cpp:363
NodeAllocator(uint32_t NPB=4096)
Definition: RDFGraph.h:378
static uint16_t set_kind(uint16_t A, uint16_t K)
Definition: RDFGraph.h:302
static uint16_t flags(uint16_t T)
Definition: RDFGraph.h:296
static uint16_t kind(uint16_t T)
Definition: RDFGraph.h:295
static uint16_t set_type(uint16_t A, uint16_t T)
Definition: RDFGraph.h:298
static bool contains(uint16_t A, uint16_t B)
Definition: RDFGraph.h:311
static uint16_t set_flags(uint16_t A, uint16_t F)
Definition: RDFGraph.h:306
static uint16_t type(uint16_t T)
Definition: RDFGraph.h:294
NodeId getNext() const
Definition: RDFGraph.h:458
void setFlags(uint16_t F)
Definition: RDFGraph.h:462
uint16_t Reserved
Definition: RDFGraph.h:474
uint16_t getAttrs() const
Definition: RDFGraph.h:460
uint16_t getType() const
Definition: RDFGraph.h:455
void setAttrs(uint16_t A)
Definition: RDFGraph.h:461
Code_struct Code
Definition: RDFGraph.h:504
uint16_t getFlags() const
Definition: RDFGraph.h:457
void append(NodeAddr< NodeBase * > NA)
Definition: RDFGraph.cpp:394
void setNext(NodeId N)
Definition: RDFGraph.h:470
Ref_struct Ref
Definition: RDFGraph.h:503
uint16_t getKind() const
Definition: RDFGraph.h:456
MachineInstr * getCode() const
Definition: RDFGraph.h:616
NodeId getPredecessor() const
Definition: RDFGraph.h:581
void setPredecessor(NodeId B)
Definition: RDFGraph.h:585
PrintNode(const NodeAddr< T > &x, const DataFlowGraph &g)
Definition: RDFGraph.h:941
Print(const T &x, const DataFlowGraph &g)
Definition: RDFGraph.h:931
const DataFlowGraph & G
Definition: RDFGraph.h:934
const T & Obj
Definition: RDFGraph.h:933
bool isDef() const
Definition: RDFGraph.h:548
NodeId getReachingDef() const
Definition: RDFGraph.h:529
NodeId getSibling() const
Definition: RDFGraph.h:536
MachineOperand & getOp()
Definition: RDFGraph.h:521
void setRegRef(RegisterRef RR, DataFlowGraph &G)
Definition: RDFGraph.cpp:416
bool isUse() const
Definition: RDFGraph.h:543
void setSibling(NodeId Sib)
Definition: RDFGraph.h:539
void setReachingDef(NodeId RD)
Definition: RDFGraph.h:532
NodeAddr< RefNode * > getNextRef(RegisterRef RR, Predicate P, bool NextOnly, const DataFlowGraph &G)
Definition: RDFGraph.h:889
NodeAddr< NodeBase * > getOwner(const DataFlowGraph &G)
Definition: RDFGraph.cpp:432
RegisterRef getRegRef(const DataFlowGraph &G) const
Definition: RDFGraph.cpp:406
MachineInstr * getCode() const
Definition: RDFGraph.h:622
virtual bool isPreserving(const MachineInstr &In, unsigned OpNum) const
Definition: RDFGraph.cpp:596
const TargetInstrInfo & TII
Definition: RDFGraph.h:423
virtual ~TargetOperandInfo()=default
TargetOperandInfo(const TargetInstrInfo &tii)
Definition: RDFGraph.h:416
virtual bool isFixedReg(const MachineInstr &In, unsigned OpNum) const
Definition: RDFGraph.cpp:615
virtual bool isClobbering(const MachineInstr &In, unsigned OpNum) const
Definition: RDFGraph.cpp:602
void linkToDef(NodeId Self, NodeAddr< DefNode * > DA)
Definition: RDFGraph.cpp:451