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