LLVM  16.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"
230 #include "llvm/Support/Allocator.h"
231 #include "llvm/Support/MathExtras.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.
245 static_assert(sizeof(uint32_t) == sizeof(unsigned), "Those should be equal");
246 
247 namespace llvm {
248 
249 class MachineBasicBlock;
250 class MachineDominanceFrontier;
251 class MachineDominatorTree;
252 class MachineFunction;
253 class MachineInstr;
254 class MachineOperand;
255 class raw_ostream;
256 class TargetInstrInfo;
257 class TargetRegisterInfo;
258 
259 namespace rdf {
260 
261  using NodeId = uint32_t;
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 
328  struct BuildOptions {
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;
337  NodeAddr(T A, NodeId I) : Addr(A), Id(I) {}
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;
353  NodeId Id = 0;
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.
374  struct NodeAllocator {
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 
384  NodeBase *ptr(NodeId N) const {
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 
416  TargetOperandInfo(const TargetInstrInfo &tii) : TII(tii) {}
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 
455  uint16_t getType() const { return NodeAttrs::type(Attrs); }
456  uint16_t getKind() const { return NodeAttrs::kind(Attrs); }
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.
465  void append(NodeAddr<NodeBase*> NA);
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 
536  NodeId getSibling() const {
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>
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 
574  };
575 
576  struct UseNode : public RefNode {
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 
601  void addMember(NodeAddr<NodeBase*> NA, const DataFlowGraph &G);
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 
645  struct DataFlowGraph {
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 
822  NodeAddr<NodeBase*> cloneNode(const NodeAddr<NodeBase*> B);
827  uint16_t Flags = NodeAttrs::PhiRef);
834  MachineInstr *MI);
838 
839  template <typename Predicate>
840  std::pair<NodeAddr<RefNode*>,NodeAddr<RefNode*>>
841  locateNextRef(NodeAddr<InstrNode*> IA, NodeAddr<RefNode*> RA,
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,
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) {
897  NodeAddr<RefNode*> RA = NA;
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>
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;
934  const DataFlowGraph &G;
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
llvm::rdf::Print
Definition: RDFGraph.h:930
llvm::LaneBitmask
Definition: LaneBitmask.h:40
llvm::rdf::DataFlowGraph::getMF
MachineFunction & getMF() const
Definition: RDFGraph.h:665
llvm::rdf::RefNode::getSibling
NodeId getSibling() const
Definition: RDFGraph.h:536
llvm::rdf::NodeAttrs::kind
static uint16_t kind(uint16_t T)
Definition: RDFGraph.h:295
llvm::rdf::PhiUseNode::getPredecessor
NodeId getPredecessor() const
Definition: RDFGraph.h:581
Attrs
Function Attrs
Definition: README_ALTIVEC.txt:215
llvm::rdf::NodeAttrs::Preserving
@ Preserving
Definition: RDFGraph.h:288
llvm::rdf::RegisterSet
std::set< RegisterRef > RegisterSet
Definition: RDFGraph.h:413
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:108
llvm::rdf::BlockNode
Definition: RDFGraph.h:627
MathExtras.h
llvm::rdf::TargetOperandInfo::isClobbering
virtual bool isClobbering(const MachineInstr &In, unsigned OpNum) const
Definition: RDFGraph.cpp:602
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::rdf::DefNode::setReachedUse
void setReachedUse(NodeId U)
Definition: RDFGraph.h:569
llvm::rdf::RegisterRef::Reg
RegisterId Reg
Definition: RDFRegisters.h:72
llvm::rdf::TargetOperandInfo::TargetOperandInfo
TargetOperandInfo(const TargetInstrInfo &tii)
Definition: RDFGraph.h:416
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::rdf::DataFlowGraph::getRelatedRefs
NodeList getRelatedRefs(NodeAddr< InstrNode * > IA, NodeAddr< RefNode * > RA) const
Definition: RDFGraph.cpp:1119
llvm::rdf::DataFlowGraph::DefStack::push
void push(NodeAddr< DefNode * > DA)
Definition: RDFGraph.h:715
llvm::M68kBeads::DA
@ DA
Definition: M68kBaseInfo.h:59
llvm::rdf::LaneMaskIndex::LaneMaskIndex
LaneMaskIndex()=default
llvm::rdf::RefNode::setReachingDef
void setReachingDef(NodeId RD)
Definition: RDFGraph.h:532
llvm::rdf::DataFlowGraph::IsPreservingDef
static bool IsPreservingDef(const NodeAddr< DefNode * > DA)
Definition: RDFGraph.h:811
llvm::rdf::CodeNode::members_if
NodeList members_if(Predicate P, const DataFlowGraph &G) const
Definition: RDFGraph.h:915
llvm::rdf::InstrNode
Definition: RDFGraph.h:611
llvm::rdf::NodeAllocator::id
NodeId id(const NodeBase *P) const
Definition: RDFGraph.cpp:375
llvm::X86II::TA
@ TA
Definition: X86BaseInfo.h:808
llvm::rdf::NodeAddr::operator!=
bool operator!=(const NodeAddr< T > &NA) const
Definition: RDFGraph.h:348
llvm::rdf::BuildOptions
Definition: RDFGraph.h:328
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::rdf::DefNode::getReachedUse
NodeId getReachedUse() const
Definition: RDFGraph.h:566
llvm::rdf::UseNode::linkToDef
void linkToDef(NodeId Self, NodeAddr< DefNode * > DA)
Definition: RDFGraph.cpp:451
llvm::rdf::NodeAttrs::Def
@ Def
Definition: RDFGraph.h:276
llvm::rdf::DataFlowGraph::ptr
T ptr(NodeId N) const
Definition: RDFGraph.h:654
DM
static RegisterPass< DebugifyModulePass > DM("debugify", "Attach debug info to everything")
llvm::rdf::TargetOperandInfo::TII
const TargetInstrInfo & TII
Definition: RDFGraph.h:423
llvm::rdf::NodeAttrs::Phi
@ Phi
Definition: RDFGraph.h:278
llvm::rdf::TargetOperandInfo::isFixedReg
virtual bool isFixedReg(const MachineInstr &In, unsigned OpNum) const
Definition: RDFGraph.cpp:615
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1182
llvm::rdf::BlockNode::addPhi
void addPhi(NodeAddr< PhiNode * > PA, const DataFlowGraph &G)
Definition: RDFGraph.cpp:544
llvm::rdf::CodeNode
Definition: RDFGraph.h:591
llvm::rdf::NodeBase::Next
NodeId Next
Definition: RDFGraph.h:475
llvm::X86Disassembler::Reg
Reg
All possible values of the reg field in the ModR/M byte.
Definition: X86DisassemblerDecoder.h:462
Allocator.h
llvm::rdf::DataFlowGraph::DefStack::DefStack
DefStack()=default
llvm::rdf::IndexedSet< LaneBitmask >::get
LaneBitmask get(uint32_t Idx) const
Definition: RDFRegisters.h:39
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:237
llvm::rdf::DataFlowGraph::unlinkUse
void unlinkUse(NodeAddr< UseNode * > UA, bool RemoveFromOwner)
Definition: RDFGraph.h:771
llvm::rdf::DataFlowGraph::releaseBlock
void releaseBlock(NodeId B, DefStackMap &DefM)
Definition: RDFGraph.cpp:996
llvm::rdf::TargetOperandInfo::isPreserving
virtual bool isPreserving(const MachineInstr &In, unsigned OpNum) const
Definition: RDFGraph.cpp:596
llvm::rdf::NodeAttrs::Ref
@ Ref
Definition: RDFGraph.h:272
llvm::operator!=
bool operator!=(uint64_t V1, const APInt &V2)
Definition: APInt.h:1992
llvm::rdf::NodeBase::getAttrs
uint16_t getAttrs() const
Definition: RDFGraph.h:460
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::rdf::NodeBase::Code_struct
Definition: RDFGraph.h:485
llvm::rdf::DataFlowGraph::getNextRelated
NodeAddr< RefNode * > getNextRelated(NodeAddr< InstrNode * > IA, NodeAddr< RefNode * > RA) const
Definition: RDFGraph.cpp:1145
llvm::rdf::PrintNode
Definition: RDFGraph.h:940
g
should just be implemented with a CLZ instruction Since there are other e g
Definition: README.txt:709
llvm::rdf::RefNode::getOp
MachineOperand & getOp()
Definition: RDFGraph.h:521
llvm::rdf::NodeBase::Ref_struct::Op
MachineOperand * Op
Definition: RDFGraph.h:496
llvm::isPowerOf2_32
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
Definition: MathExtras.h:459
llvm::rdf::NodeBase::Ref_struct::Def
Def_struct Def
Definition: RDFGraph.h:492
llvm::rdf::NodeAttrs::contains
static bool contains(uint16_t A, uint16_t B)
Definition: RDFGraph.h:311
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1628
RDFRegisters.h
llvm::rdf::LaneMaskIndex
Definition: RDFGraph.h:432
llvm::rdf::RegisterRef
Definition: RDFRegisters.h:71
llvm::rdf::NodeAllocator::NodeMemSize
@ NodeMemSize
Definition: RDFGraph.h:376
llvm::rdf::BuildOptions::None
@ None
Definition: RDFGraph.h:330
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::rdf::LaneMaskIndex::getIndexForLaneMask
uint32_t getIndexForLaneMask(LaneBitmask LM) const
Definition: RDFGraph.h:444
llvm::rdf::NodeBase::getFlags
uint16_t getFlags() const
Definition: RDFGraph.h:457
llvm::rdf::NodeAttrs::KindMask
@ KindMask
Definition: RDFGraph.h:275
llvm::rdf::PackedRegisterRef::Reg
RegisterId Reg
Definition: RDFGraph.h:428
llvm::rdf::CodeNode::setCode
void setCode(void *C)
Definition: RDFGraph.h:595
llvm::rdf::NodeAddr::NodeAddr
NodeAddr()=default
llvm::rdf::DataFlowGraph::getTII
const TargetInstrInfo & getTII() const
Definition: RDFGraph.h:666
llvm::rdf::DataFlowGraph::getFunc
NodeAddr< FuncNode * > getFunc() const
Definition: RDFGraph.h:664
llvm::rdf::RegisterRef::Mask
LaneBitmask Mask
Definition: RDFRegisters.h:73
llvm::TargetInstrInfo
TargetInstrInfo - Interface to description of machine instruction set.
Definition: TargetInstrInfo.h:98
llvm::rdf::DataFlowGraph::getDT
const MachineDominatorTree & getDT() const
Definition: RDFGraph.h:669
llvm::rdf::NodeAttrs::set_flags
static uint16_t set_flags(uint16_t A, uint16_t F)
Definition: RDFGraph.h:306
llvm::rdf::PrintNode::PrintNode
PrintNode(const NodeAddr< T > &x, const DataFlowGraph &g)
Definition: RDFGraph.h:941
llvm::rdf::NodeAddr
Definition: RDFGraph.h:335
llvm::rdf::RefNode::getRegRef
RegisterRef getRegRef(const DataFlowGraph &G) const
Definition: RDFGraph.cpp:406
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::rdf::NodeBase::Ref_struct::RD
NodeId RD
Definition: RDFGraph.h:490
llvm::rdf::PhiUseNode
Definition: RDFGraph.h:580
llvm::rdf::NodeAllocator::NodeAllocator
NodeAllocator(uint32_t NPB=4096)
Definition: RDFGraph.h:378
llvm::rdf::NodeAttrs::set_type
static uint16_t set_type(uint16_t A, uint16_t T)
Definition: RDFGraph.h:298
TII
const HexagonInstrInfo * TII
Definition: HexagonCopyToCombine.cpp:125
llvm::dwarf::Index
Index
Definition: Dwarf.h:472
llvm::Log2_32
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:548
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:48
llvm::rdf::RegisterAggr
Definition: RDFRegisters.h:168
llvm::rdf::PackedRegisterRef::MaskId
uint32_t MaskId
Definition: RDFGraph.h:429
llvm::rdf::NodeId
uint32_t NodeId
Definition: RDFGraph.h:261
llvm::rdf::RefNode::isDef
bool isDef() const
Definition: RDFGraph.h:548
Options
const char LLVMTargetMachineRef LLVMPassBuilderOptionsRef Options
Definition: PassBuilderBindings.cpp:48
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
llvm::rdf::PhysicalRegisterInfo
Definition: RDFRegisters.h:102
llvm::rdf::DataFlowGraph::DataFlowGraph
DataFlowGraph(MachineFunction &mf, const TargetInstrInfo &tii, const TargetRegisterInfo &tri, const MachineDominatorTree &mdt, const MachineDominanceFrontier &mdf)
Definition: RDFGraph.cpp:649
llvm::rdf::DataFlowGraph::IsDef
static bool IsDef(const NodeAddr< NodeBase * > BA)
Definition: RDFGraph.h:796
llvm::rdf::NodeBase::Reserved
uint16_t Reserved
Definition: RDFGraph.h:474
llvm::rdf::DataFlowGraph::ptr
NodeBase * ptr(NodeId N) const
Definition: RDFGraph.cpp:772
llvm::rdf::NodeAddr::Addr
T Addr
Definition: RDFGraph.h:352
llvm::rdf::NodeBase::getType
uint16_t getType() const
Definition: RDFGraph.h:455
llvm::rdf::CodeNode::addMemberAfter
void addMemberAfter(NodeAddr< NodeBase * > MA, NodeAddr< NodeBase * > NA, const DataFlowGraph &G)
Definition: RDFGraph.cpp:485
llvm::rdf::DataFlowGraph::DefStack::clear_block
void clear_block(NodeId N)
Definition: RDFGraph.cpp:709
llvm::rdf::NodeBase::getNext
NodeId getNext() const
Definition: RDFGraph.h:458
llvm::rdf::NodeAddr::NodeAddr
NodeAddr(T A, NodeId I)
Definition: RDFGraph.h:337
llvm::rdf::NodeAttrs::Clobbering
@ Clobbering
Definition: RDFGraph.h:286
llvm::lltok::Kind
Kind
Definition: LLToken.h:18
llvm::rdf::NodeAttrs::Dead
@ Dead
Definition: RDFGraph.h:291
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:94
llvm::rdf::BuildOptions::KeepDeadPhis
@ KeepDeadPhis
Definition: RDFGraph.h:331
llvm::rdf::DefNode::linkToDef
void linkToDef(NodeId Self, NodeAddr< DefNode * > DA)
Definition: RDFGraph.cpp:444
llvm::rdf::NodeBase::Code
Code_struct Code
Definition: RDFGraph.h:504
llvm::rdf::DataFlowGraph::DefStack::pop
void pop()
Definition: RDFGraph.cpp:694
llvm::rdf::NodeAttrs::TypeMask
@ TypeMask
Definition: RDFGraph.h:270
G
const DataFlowGraph & G
Definition: RDFGraph.cpp:200
llvm::tgtok::In
@ In
Definition: TGLexer.h:51
llvm::rdf::DataFlowGraph::makeRegRef
RegisterRef makeRegRef(unsigned Reg, unsigned Sub) const
Definition: RDFGraph.cpp:972
llvm::rdf::PackedRegisterRef
Definition: RDFGraph.h:427
llvm::rdf::NodeAttrs::Fixed
@ Fixed
Definition: RDFGraph.h:289
llvm::rdf::NodeAttrs
Definition: RDFGraph.h:265
llvm::PPC::Predicate
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
Definition: PPCPredicates.h:26
llvm::rdf::DataFlowGraph::IsCode
static bool IsCode(const NodeAddr< NodeBase * > BA)
Definition: RDFGraph.h:791
llvm::rdf::NodeAttrs::Block
@ Block
Definition: RDFGraph.h:280
llvm::rdf::DefNode::setReachedDef
void setReachedDef(NodeId D)
Definition: RDFGraph.h:563
llvm::rdf::DataFlowGraph::addr
NodeAddr< T > addr(NodeId N) const
Definition: RDFGraph.h:660
llvm::rdf::DataFlowGraph::IsRef
static bool IsRef(const NodeAddr< NodeBase * > BA)
Definition: RDFGraph.h:785
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:66
llvm::rdf::RefNode::RefNode
RefNode()=default
D
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
llvm::rdf::DataFlowGraph::getTRI
const TargetRegisterInfo & getTRI() const
Definition: RDFGraph.h:667
llvm::MachineDominanceFrontier
Definition: MachineDominanceFrontier.h:20
llvm::rdf::CodeNode::addMember
void addMember(NodeAddr< NodeBase * > NA, const DataFlowGraph &G)
Definition: RDFGraph.cpp:472
llvm::rdf::DataFlowGraph::unpack
RegisterRef unpack(PackedRegisterRef PR) const
Definition: RDFGraph.h:750
llvm::rdf::PhiNode
Definition: RDFGraph.h:615
llvm::BumpPtrAllocatorImpl< MallocAllocator, 65536 >
llvm::rdf::CodeNode::members
NodeList members(const DataFlowGraph &G) const
Definition: RDFGraph.cpp:525
llvm::rdf::PhiUseNode::setPredecessor
void setPredecessor(NodeId B)
Definition: RDFGraph.h:585
llvm::rdf::UseNode
Definition: RDFGraph.h:576
llvm::rdf::DataFlowGraph
Definition: RDFGraph.h:645
llvm::rdf::Print::G
const DataFlowGraph & G
Definition: RDFGraph.h:934
llvm::rdf::NodeBase::NodeBase
NodeBase()=default
llvm::rdf::DataFlowGraph::getPRI
const PhysicalRegisterInfo & getPRI() const
Definition: RDFGraph.h:668
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::LaneBitmask::any
constexpr bool any() const
Definition: LaneBitmask.h:53
llvm::rdf::NodeBase::Ref_struct::PR
PackedRegisterRef PR
Definition: RDFGraph.h:497
llvm::rdf::operator<<
raw_ostream & operator<<(raw_ostream &OS, const Print< RegisterRef > &P)
Definition: RDFGraph.cpp:55
llvm::rdf::NodeBase::Def_struct::DD
NodeId DD
Definition: RDFGraph.h:480
llvm::rdf::DataFlowGraph::markBlock
void markBlock(NodeId B, DefStackMap &DefM)
Definition: RDFGraph.cpp:989
llvm::rdf::NodeAllocator
Definition: RDFGraph.h:374
llvm::rdf::LaneMaskIndex::getLaneMaskForIndex
LaneBitmask getLaneMaskForIndex(uint32_t K) const
Definition: RDFGraph.h:435
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::rdf::RefNode::isUse
bool isUse() const
Definition: RDFGraph.h:543
llvm::rdf::DataFlowGraph::IsPhi
static bool IsPhi(const NodeAddr< NodeBase * > BA)
Definition: RDFGraph.h:806
llvm::rdf::IndexedSet< LaneBitmask >::find
uint32_t find(LaneBitmask Val) const
Definition: RDFRegisters.h:54
llvm::rdf::NodeBase::Ref_struct::PhiU
PhiU_struct PhiU
Definition: RDFGraph.h:493
llvm::operator==
bool operator==(uint64_t V1, const APInt &V2)
Definition: APInt.h:1990
llvm::rdf::NodeBase::Attrs
uint16_t Attrs
Definition: RDFGraph.h:473
llvm::rdf::DataFlowGraph::DefStack::top
iterator top() const
Definition: RDFGraph.h:711
llvm::rdf::NodeBase::Ref_struct
Definition: RDFGraph.h:489
llvm::rdf::NodeBase::PhiU_struct
Definition: RDFGraph.h:482
RA
SI optimize exec mask operations pre RA
Definition: SIOptimizeExecMaskingPreRA.cpp:71
llvm::rdf::NodeAddr::operator==
bool operator==(const NodeAddr< T > &NA) const
Definition: RDFGraph.h:344
llvm::rdf::Print::Print
Print(const T &x, const DataFlowGraph &g)
Definition: RDFGraph.h:931
llvm::rdf::DataFlowGraph::pushAllDefs
void pushAllDefs(NodeAddr< InstrNode * > IA, DefStackMap &DM)
Definition: RDFGraph.cpp:1014
llvm::rdf::DataFlowGraph::DefStack::bottom
iterator bottom() const
Definition: RDFGraph.h:712
llvm::rdf::PhiNode::getCode
MachineInstr * getCode() const
Definition: RDFGraph.h:616
llvm::MachineFunction
Definition: MachineFunction.h:257
llvm::rdf::NodeBase::getKind
uint16_t getKind() const
Definition: RDFGraph.h:456
llvm::rdf::CodeNode::getFirstMember
NodeAddr< NodeBase * > getFirstMember(const DataFlowGraph &G) const
Definition: RDFGraph.cpp:458
llvm::rdf::NodeBase::setNext
void setNext(NodeId N)
Definition: RDFGraph.h:470
llvm::operator*
APInt operator*(APInt a, uint64_t RHS)
Definition: APInt.h:2114
llvm::rdf::NodeBase::Code_struct::CP
void * CP
Definition: RDFGraph.h:486
llvm::rdf::NodeAttrs::Undef
@ Undef
Definition: RDFGraph.h:290
llvm::sys::Memory
This class provides various memory handling functions that manipulate MemoryBlock instances.
Definition: Memory.h:52
llvm::rdf::DataFlowGraph::DefStack
Definition: RDFGraph.h:673
llvm::rdf::DataFlowGraph::getDF
const MachineDominanceFrontier & getDF() const
Definition: RDFGraph.h:670
llvm::rdf::NodeBase::Code_struct::FirstM
NodeId FirstM
Definition: RDFGraph.h:487
llvm::rdf::FuncNode::getCode
MachineFunction * getCode() const
Definition: RDFGraph.h:636
llvm::rdf::StmtNode
Definition: RDFGraph.h:621
llvm::rdf::NodeAttrs::Func
@ Func
Definition: RDFGraph.h:281
uint32_t
llvm::rdf::Print
Print(const T &, const DataFlowGraph &) -> Print< T >
llvm::rdf::NodeAttrs::type
static uint16_t type(uint16_t T)
Definition: RDFGraph.h:294
llvm::rdf::DataFlowGraph::IsUse
static bool IsUse(const NodeAddr< NodeBase * > BA)
Definition: RDFGraph.h:801
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::rdf::NodeAttrs::Use
@ Use
Definition: RDFGraph.h:277
llvm::rdf::DataFlowGraph::DefStack::Iterator
friend struct Iterator
Definition: RDFGraph.h:721
llvm::rdf::NodeAllocator::clear
void clear()
Definition: RDFGraph.cpp:387
llvm::rdf::NodeAttrs::Stmt
@ Stmt
Definition: RDFGraph.h:279
llvm::rdf::DataFlowGraph::getLiveIns
const RegisterAggr & getLiveIns() const
Definition: RDFGraph.h:671
llvm::rdf::CodeNode::removeMember
void removeMember(NodeAddr< NodeBase * > NA, const DataFlowGraph &G)
Definition: RDFGraph.cpp:493
llvm::rdf::RefNode::setRegRef
void setRegRef(RegisterRef RR, DataFlowGraph &G)
Definition: RDFGraph.cpp:416
llvm::rdf::DataFlowGraph::pack
PackedRegisterRef pack(RegisterRef RR)
Definition: RDFGraph.h:744
llvm::rdf::DataFlowGraph::build
void build(unsigned Options=BuildOptions::None)
Definition: RDFGraph.cpp:874
llvm::rdf::TargetOperandInfo
Definition: RDFGraph.h:415
llvm::rdf::DataFlowGraph::DefStack::iterator
Iterator iterator
Definition: RDFGraph.h:709
llvm::rdf::CodeNode::getLastMember
NodeAddr< NodeBase * > getLastMember(const DataFlowGraph &G) const
Definition: RDFGraph.cpp:465
uint16_t
llvm::rdf::NodeBase::setAttrs
void setAttrs(uint16_t A)
Definition: RDFGraph.h:461
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:348
llvm::rdf::NodeBase
Definition: RDFGraph.h:450
llvm::rdf::NodeBase::Ref
Ref_struct Ref
Definition: RDFGraph.h:503
llvm::rdf::NodeBase::Ref_struct::Sib
NodeId Sib
Definition: RDFGraph.h:490
llvm::rdf::NodeAttrs::PhiRef
@ PhiRef
Definition: RDFGraph.h:287
llvm::rdf::DataFlowGraph::DefStack::size
unsigned size() const
Definition: RDFGraph.cpp:684
llvm::rdf::DefNode
Definition: RDFGraph.h:559
llvm::LaneBitmask::all
constexpr bool all() const
Definition: LaneBitmask.h:54
llvm::rdf::NodeBase::PhiU_struct::PredB
NodeId PredB
Definition: RDFGraph.h:483
llvm::rdf::NodeBase::setFlags
void setFlags(uint16_t F)
Definition: RDFGraph.h:462
x
TODO unsigned x
Definition: README.txt:10
llvm::rdf::NodeAttrs::None
@ None
Definition: RDFGraph.h:267
llvm::rdf::RefNode::getOwner
NodeAddr< NodeBase * > getOwner(const DataFlowGraph &G)
Definition: RDFGraph.cpp:432
llvm::rdf::DefNode::getReachedDef
NodeId getReachedDef() const
Definition: RDFGraph.h:560
llvm::rdf::NodeBase::Code_struct::LastM
NodeId LastM
Definition: RDFGraph.h:487
llvm::rdf::NodeAttrs::Shadow
@ Shadow
Definition: RDFGraph.h:285
llvm::rdf::NodeBase::Def_struct::DU
NodeId DU
Definition: RDFGraph.h:480
llvm::rdf::CodeNode::getCode
T getCode() const
Definition: RDFGraph.h:592
llvm::rdf::StmtNode::getCode
MachineInstr * getCode() const
Definition: RDFGraph.h:622
llvm::rdf::NodeAttrs::set_kind
static uint16_t set_kind(uint16_t A, uint16_t K)
Definition: RDFGraph.h:302
llvm::rdf::DataFlowGraph::pack
PackedRegisterRef pack(RegisterRef RR) const
Definition: RDFGraph.h:747
llvm::rdf::FuncNode::getEntryBlock
NodeAddr< BlockNode * > getEntryBlock(const DataFlowGraph &G)
Definition: RDFGraph.cpp:586
llvm::rdf::NodeAddr::Id
NodeId Id
Definition: RDFGraph.h:353
llvm::rdf::RefNode::getReachingDef
NodeId getReachingDef() const
Definition: RDFGraph.h:529
llvm::rdf::IndexedSet
Definition: RDFRegisters.h:36
SmallVector.h
llvm::rdf::DataFlowGraph::unlinkDef
void unlinkDef(NodeAddr< DefNode * > DA, bool RemoveFromOwner)
Definition: RDFGraph.h:777
llvm::rdf::NodeSet
std::set< NodeId > NodeSet
Definition: RDFGraph.h:514
llvm::rdf::IndexedSet< LaneBitmask >::insert
uint32_t insert(LaneBitmask Val)
Definition: RDFRegisters.h:45
llvm::rdf::Print::Obj
const T & Obj
Definition: RDFGraph.h:933
N
#define N
llvm::rdf::BlockNode::getCode
MachineBasicBlock * getCode() const
Definition: RDFGraph.h:628
llvm::rdf::LaneMaskIndex::getIndexForLaneMask
uint32_t getIndexForLaneMask(LaneBitmask LM)
Definition: RDFGraph.h:439
llvm::rdf::NodeAttrs::Code
@ Code
Definition: RDFGraph.h:271
llvm::rdf::NodeAttrs::flags
static uint16_t flags(uint16_t T)
Definition: RDFGraph.h:296
llvm::rdf::NodeAllocator::ptr
NodeBase * ptr(NodeId N) const
Definition: RDFGraph.h:384
LaneBitmask.h
llvm::rdf::NodeBase::append
void append(NodeAddr< NodeBase * > NA)
Definition: RDFGraph.cpp:394
llvm::rdf::RefNode
Definition: RDFGraph.h:516
llvm::rdf::FuncNode::findBlock
NodeAddr< BlockNode * > findBlock(const MachineBasicBlock *BB, const DataFlowGraph &G) const
Definition: RDFGraph.cpp:574
llvm::rdf::DataFlowGraph::DefStack::start_block
void start_block(NodeId N)
Definition: RDFGraph.cpp:701
llvm::rdf::DataFlowGraph::getNextShadow
NodeAddr< RefNode * > getNextShadow(NodeAddr< InstrNode * > IA, NodeAddr< RefNode * > RA, bool Create)
Definition: RDFGraph.cpp:1206
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::rdf::NodeAddr::NodeAddr
NodeAddr(const NodeAddr< S > &NA)
Definition: RDFGraph.h:341
llvm::rdf::RefNode::getNextRef
NodeAddr< RefNode * > getNextRef(RegisterRef RR, Predicate P, bool NextOnly, const DataFlowGraph &G)
Definition: RDFGraph.h:889
llvm::rdf::FuncNode
Definition: RDFGraph.h:635
llvm::rdf::TargetOperandInfo::~TargetOperandInfo
virtual ~TargetOperandInfo()=default
llvm::rdf::DataFlowGraph::id
NodeId id(const NodeBase *P) const
Definition: RDFGraph.cpp:779
llvm::rdf::NodeBase::init
void init()
Definition: RDFGraph.h:468
llvm::MachineDominatorTree
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
Definition: MachineDominators.h:51
llvm::rdf::DataFlowGraph::findBlock
NodeAddr< BlockNode * > findBlock(MachineBasicBlock *BB) const
Definition: RDFGraph.h:767
llvm::SIInstrFlags::DS
@ DS
Definition: SIDefines.h:60
llvm::rdf::NodeAttrs::FlagMask
@ FlagMask
Definition: RDFGraph.h:284
llvm::rdf::RefNode::setSibling
void setSibling(NodeId Sib)
Definition: RDFGraph.h:539
llvm::LaneBitmask::getAll
static constexpr LaneBitmask getAll()
Definition: LaneBitmask.h:84
llvm::rdf::DataFlowGraph::DefStack::empty
bool empty() const
Definition: RDFGraph.h:676
llvm::rdf::NodeBase::Def_struct
Definition: RDFGraph.h:479
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
llvm::rdf::DataFlowGraph::DefStackMap
std::unordered_map< RegisterId, DefStack > DefStackMap
Definition: RDFGraph.h:737
llvm::rdf::InstrNode::getOwner
NodeAddr< NodeBase * > getOwner(const DataFlowGraph &G)
Definition: RDFGraph.cpp:531
llvm::rdf::NodeAllocator::New
NodeAddr< NodeBase * > New()
Definition: RDFGraph.cpp:363