LLVM  9.0.0svn
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_LIB_TARGET_HEXAGON_RDFGRAPH_H
225 #define LLVM_LIB_TARGET_HEXAGON_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 
297  static uint16_t set_type(uint16_t A, uint16_t T) {
298  return (A & ~TypeMask) | T;
299  }
300 
301  static uint16_t set_kind(uint16_t A, uint16_t K) {
302  return (A & ~KindMask) | K;
303  }
304 
305  static uint16_t set_flags(uint16_t A, uint16_t F) {
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;
391  NodeAddr<NodeBase*> New();
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); }
456  uint16_t getFlags() const { return NodeAttrs::flags(Attrs); }
457  NodeId getNext() const { return Next; }
458 
459  uint16_t getAttrs() const { return Attrs; }
460  void setAttrs(uint16_t A) { Attrs = A; }
461  void setFlags(uint16_t F) { setAttrs(NodeAttrs::set_flags(getAttrs(), F)); }
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:
472  uint16_t Attrs;
473  uint16_t Reserved;
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 
521  assert(!(getFlags() & NodeAttrs::PhiRef));
522  return *Ref.Op;
523  }
524 
525  void setRegRef(RegisterRef RR, DataFlowGraph &G);
526  void setRegRef(MachineOperand *Op, DataFlowGraph &G);
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>
553  NodeAddr<RefNode*> getNextRef(RegisterRef RR, Predicate P, bool NextOnly,
554  const DataFlowGraph &G);
555  NodeAddr<NodeBase*> getOwner(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 
572  void linkToDef(NodeId Self, NodeAddr<DefNode*> DA);
573  };
574 
575  struct UseNode : public RefNode {
576  void linkToDef(NodeId Self, NodeAddr<DefNode*> DA);
577  };
578 
579  struct PhiUseNode : public UseNode {
581  assert(getFlags() & NodeAttrs::PhiRef);
582  return Ref.PhiU.PredB;
583  }
585  assert(getFlags() & NodeAttrs::PhiRef);
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 
598  NodeAddr<NodeBase*> getFirstMember(const DataFlowGraph &G) const;
599  NodeAddr<NodeBase*> getLastMember(const DataFlowGraph &G) const;
600  void addMember(NodeAddr<NodeBase*> NA, const DataFlowGraph &G);
601  void addMemberAfter(NodeAddr<NodeBase*> MA, NodeAddr<NodeBase*> NA,
602  const DataFlowGraph &G);
603  void removeMember(NodeAddr<NodeBase*> NA, const DataFlowGraph &G);
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 {
611  NodeAddr<NodeBase*> getOwner(const DataFlowGraph &G);
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 
639  NodeAddr<BlockNode*> findBlock(const MachineBasicBlock *BB,
640  const DataFlowGraph &G) const;
641  NodeAddr<BlockNode*> getEntryBlock(const DataFlowGraph &G);
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:
676  struct Iterator {
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:
705  using iterator = Iterator;
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);
736  void pushAllDefs(NodeAddr<InstrNode*> IA, DefStackMap &DM);
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;
752  RegisterRef restrictRef(RegisterRef AR, RegisterRef BR) const;
753 
754  NodeAddr<RefNode*> getNextRelated(NodeAddr<InstrNode*> IA,
755  NodeAddr<RefNode*> RA) const;
757  NodeAddr<RefNode*> RA, bool Create);
759  NodeAddr<RefNode*> RA) const;
760  NodeAddr<RefNode*> getNextShadow(NodeAddr<InstrNode*> IA,
761  NodeAddr<RefNode*> RA, bool Create);
762  NodeAddr<RefNode*> getNextShadow(NodeAddr<InstrNode*> IA,
763  NodeAddr<RefNode*> RA) const;
764 
765  NodeList getRelatedRefs(NodeAddr<InstrNode*> IA,
766  NodeAddr<RefNode*> RA) const;
767 
769  return BlockNodes.at(BB);
770  }
771 
772  void unlinkUse(NodeAddr<UseNode*> UA, bool RemoveFromOwner) {
773  unlinkUseDF(UA);
774  if (RemoveFromOwner)
775  removeFromOwner(UA);
776  }
777 
778  void unlinkDef(NodeAddr<DefNode*> DA, bool RemoveFromOwner) {
779  unlinkDefDF(DA);
780  if (RemoveFromOwner)
781  removeFromOwner(DA);
782  }
783 
784  // Some useful filters.
785  template <uint16_t Kind>
786  static bool IsRef(const NodeAddr<NodeBase*> BA) {
787  return BA.Addr->getType() == NodeAttrs::Ref &&
788  BA.Addr->getKind() == Kind;
789  }
790 
791  template <uint16_t Kind>
792  static bool IsCode(const NodeAddr<NodeBase*> BA) {
793  return BA.Addr->getType() == NodeAttrs::Code &&
794  BA.Addr->getKind() == Kind;
795  }
796 
797  static bool IsDef(const NodeAddr<NodeBase*> BA) {
798  return BA.Addr->getType() == NodeAttrs::Ref &&
799  BA.Addr->getKind() == NodeAttrs::Def;
800  }
801 
802  static bool IsUse(const NodeAddr<NodeBase*> BA) {
803  return BA.Addr->getType() == NodeAttrs::Ref &&
804  BA.Addr->getKind() == NodeAttrs::Use;
805  }
806 
807  static bool IsPhi(const NodeAddr<NodeBase*> BA) {
808  return BA.Addr->getType() == NodeAttrs::Code &&
809  BA.Addr->getKind() == NodeAttrs::Phi;
810  }
811 
812  static bool IsPreservingDef(const NodeAddr<DefNode*> DA) {
813  uint16_t Flags = DA.Addr->getFlags();
814  return (Flags & NodeAttrs::Preserving) && !(Flags & NodeAttrs::Undef);
815  }
816 
817  private:
818  void reset();
819 
820  RegisterSet getLandingPadLiveIns() const;
821 
822  NodeAddr<NodeBase*> newNode(uint16_t Attrs);
823  NodeAddr<NodeBase*> cloneNode(const NodeAddr<NodeBase*> B);
825  MachineOperand &Op, uint16_t Flags = NodeAttrs::None);
828  uint16_t Flags = NodeAttrs::PhiRef);
830  MachineOperand &Op, uint16_t Flags = NodeAttrs::None);
832  RegisterRef RR, uint16_t Flags = NodeAttrs::PhiRef);
835  MachineInstr *MI);
837  MachineBasicBlock *BB);
839 
840  template <typename Predicate>
841  std::pair<NodeAddr<RefNode*>,NodeAddr<RefNode*>>
842  locateNextRef(NodeAddr<InstrNode*> IA, NodeAddr<RefNode*> RA,
843  Predicate P) const;
844 
845  using BlockRefsMap = std::map<NodeId, RegisterSet>;
846 
847  void buildStmt(NodeAddr<BlockNode*> BA, MachineInstr &In);
848  void recordDefsForDF(BlockRefsMap &PhiM, NodeAddr<BlockNode*> BA);
849  void buildPhis(BlockRefsMap &PhiM, RegisterSet &AllRefs,
851  void removeUnusedPhis();
852 
853  void pushClobbers(NodeAddr<InstrNode*> IA, DefStackMap &DM);
854  void pushDefs(NodeAddr<InstrNode*> IA, DefStackMap &DM);
855  template <typename T> void linkRefUp(NodeAddr<InstrNode*> IA,
857  template <typename Predicate> void linkStmtRefs(DefStackMap &DefM,
859  void linkBlockRefs(DefStackMap &DefM, NodeAddr<BlockNode*> BA);
860 
861  void unlinkUseDF(NodeAddr<UseNode*> UA);
862  void unlinkDefDF(NodeAddr<DefNode*> DA);
863 
864  void removeFromOwner(NodeAddr<RefNode*> RA) {
865  NodeAddr<InstrNode*> IA = RA.Addr->getOwner(*this);
866  IA.Addr->removeMember(RA, *this);
867  }
868 
869  MachineFunction &MF;
870  const TargetInstrInfo &TII;
871  const TargetRegisterInfo &TRI;
872  const PhysicalRegisterInfo PRI;
873  const MachineDominatorTree &MDT;
874  const MachineDominanceFrontier &MDF;
875  const TargetOperandInfo &TOI;
876 
877  RegisterAggr LiveIns;
880  // Local map: MachineBasicBlock -> NodeAddr<BlockNode*>
881  std::map<MachineBasicBlock*,NodeAddr<BlockNode*>> BlockNodes;
882  // Lane mask map.
883  LaneMaskIndex LMI;
884  }; // struct DataFlowGraph
885 
886  template <typename Predicate>
888  bool NextOnly, const DataFlowGraph &G) {
889  // Get the "Next" reference in the circular list that references RR and
890  // satisfies predicate "Pred".
891  auto NA = G.addr<NodeBase*>(getNext());
892 
893  while (NA.Addr != this) {
894  if (NA.Addr->getType() == NodeAttrs::Ref) {
895  NodeAddr<RefNode*> RA = NA;
896  if (RA.Addr->getRegRef(G) == RR && P(NA))
897  return NA;
898  if (NextOnly)
899  break;
900  NA = G.addr<NodeBase*>(NA.Addr->getNext());
901  } else {
902  // We've hit the beginning of the chain.
903  assert(NA.Addr->getType() == NodeAttrs::Code);
904  NodeAddr<CodeNode*> CA = NA;
905  NA = CA.Addr->getFirstMember(G);
906  }
907  }
908  // Return the equivalent of "nullptr" if such a node was not found.
909  return NodeAddr<RefNode*>();
910  }
911 
912  template <typename Predicate>
914  NodeList MM;
915  auto M = getFirstMember(G);
916  if (M.Id == 0)
917  return MM;
918 
919  while (M.Addr != this) {
920  if (P(M))
921  MM.push_back(M);
922  M = G.addr<NodeBase*>(M.Addr->getNext());
923  }
924  return MM;
925  }
926 
927  template <typename T>
928  struct Print {
929  Print(const T &x, const DataFlowGraph &g) : Obj(x), G(g) {}
930 
931  const T &Obj;
932  const DataFlowGraph &G;
933  };
934 
935  template <typename T>
936  struct PrintNode : Print<NodeAddr<T>> {
937  PrintNode(const NodeAddr<T> &x, const DataFlowGraph &g)
938  : Print<NodeAddr<T>>(x, g) {}
939  };
940 
941  raw_ostream &operator<<(raw_ostream &OS, const Print<RegisterRef> &P);
942  raw_ostream &operator<<(raw_ostream &OS, const Print<NodeId> &P);
943  raw_ostream &operator<<(raw_ostream &OS, const Print<NodeAddr<DefNode *>> &P);
944  raw_ostream &operator<<(raw_ostream &OS, const Print<NodeAddr<UseNode *>> &P);
946  const Print<NodeAddr<PhiUseNode *>> &P);
947  raw_ostream &operator<<(raw_ostream &OS, const Print<NodeAddr<RefNode *>> &P);
948  raw_ostream &operator<<(raw_ostream &OS, const Print<NodeList> &P);
949  raw_ostream &operator<<(raw_ostream &OS, const Print<NodeSet> &P);
950  raw_ostream &operator<<(raw_ostream &OS, const Print<NodeAddr<PhiNode *>> &P);
952  const Print<NodeAddr<StmtNode *>> &P);
954  const Print<NodeAddr<InstrNode *>> &P);
956  const Print<NodeAddr<BlockNode *>> &P);
958  const Print<NodeAddr<FuncNode *>> &P);
959  raw_ostream &operator<<(raw_ostream &OS, const Print<RegisterSet> &P);
960  raw_ostream &operator<<(raw_ostream &OS, const Print<RegisterAggr> &P);
963 
964 } // end namespace rdf
965 
966 } // end namespace llvm
967 
968 #endif // LLVM_LIB_TARGET_HEXAGON_RDFGRAPH_H
NodeAddr< BlockNode * > findBlock(MachineBasicBlock *BB) const
Definition: RDFGraph.h:768
raw_ostream & operator<<(raw_ostream &OS, const PrintLaneMaskOpt &P)
Definition: RDFGraph.cpp:51
uint64_t CallInst * C
void setReachingDef(NodeId RD)
Definition: RDFGraph.h:531
NodeId getReachedUse() const
Definition: RDFGraph.h:565
A common definition of LaneBitmask for use in TableGen and CodeGen.
MachineFunction & getMF() const
Definition: RDFGraph.h:661
uint16_t getFlags() const
Definition: RDFGraph.h:456
static uint16_t kind(uint16_t T)
Definition: RDFGraph.h:294
T ptr(NodeId N) const
Definition: RDFGraph.h:650
This class represents lattice values for constants.
Definition: AllocatorList.h:23
void setCode(void *C)
Definition: RDFGraph.h:594
void setNext(NodeId N)
Definition: RDFGraph.h:469
uint16_t getType() const
Definition: RDFGraph.h:454
static uint16_t type(uint16_t T)
Definition: RDFGraph.h:293
void unlinkDef(NodeAddr< DefNode *> DA, bool RemoveFromOwner)
Definition: RDFGraph.h:778
This class provides various memory handling functions that manipulate MemoryBlock instances...
Definition: Memory.h:53
static bool IsPreservingDef(const NodeAddr< DefNode *> DA)
Definition: RDFGraph.h:812
Code_struct Code
Definition: RDFGraph.h:503
void push_back(const T &Elt)
Definition: SmallVector.h:211
unsigned Reg
uint32_t NodeId
Definition: RDFGraph.h:260
uint32_t getIndexForLaneMask(LaneBitmask LM) const
Definition: RDFGraph.h:443
unsigned const TargetRegisterInfo * TRI
F(f)
MachineOperand & getOp()
Definition: RDFGraph.h:520
const T & Obj
Definition: RDFGraph.h:931
This file defines the MallocAllocator and BumpPtrAllocator interfaces.
const TargetInstrInfo & TII
Definition: RDFGraph.h:422
const TargetInstrInfo & getTII() const
Definition: RDFGraph.h:662
SI optimize exec mask operations pre RA
NodeAddr< FuncNode * > getFunc() const
Definition: RDFGraph.h:660
void append(SmallVectorImpl< char > &path, const Twine &a, const Twine &b="", const Twine &c="", const Twine &d="")
Append to path.
Definition: Path.cpp:455
const HexagonInstrInfo * TII
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
std::set< RegisterRef > RegisterSet
Definition: RDFGraph.h:412
static constexpr LaneBitmask getAll()
Definition: LaneBitmask.h:83
void unlinkUse(NodeAddr< UseNode *> UA, bool RemoveFromOwner)
Definition: RDFGraph.h:772
APInt operator*(APInt a, uint64_t RHS)
Definition: APInt.h:2090
bool isDef() const
Definition: RDFGraph.h:547
uint16_t getAttrs() const
Definition: RDFGraph.h:459
NodeId getNext() const
Definition: RDFGraph.h:457
static uint16_t set_flags(uint16_t A, uint16_t F)
Definition: RDFGraph.h:305
const MachineDominatorTree & getDT() const
Definition: RDFGraph.h:665
constexpr char Attrs[]
Key for Kernel::Metadata::mAttrs.
Ref_struct Ref
Definition: RDFGraph.h:502
TargetInstrInfo - Interface to description of machine instruction set.
NodeAllocator(uint32_t NPB=4096)
Definition: RDFGraph.h:377
void setFlags(uint16_t F)
Definition: RDFGraph.h:461
void setReachedDef(NodeId D)
Definition: RDFGraph.h:562
Error build(ArrayRef< Module *> Mods, SmallVector< char, 0 > &Symtab, StringTableBuilder &StrtabBuilder, BumpPtrAllocator &Alloc)
Fills in Symtab and StrtabBuilder with a valid symbol and string table for Mods.
Definition: IRSymtab.cpp:338
#define P(N)
static bool IsUse(const NodeAddr< NodeBase *> BA)
Definition: RDFGraph.h:802
Control flow instructions. These all have token chains.
Definition: ISDOpcodes.h:657
T getCode() const
Definition: RDFGraph.h:591
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
PrintNode(const NodeAddr< T > &x, const DataFlowGraph &g)
Definition: RDFGraph.h:937
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
Definition: MathExtras.h:428
NodeAddr< T > addr(NodeId N) const
Definition: RDFGraph.h:656
const TargetRegisterInfo & getTRI() const
Definition: RDFGraph.h:663
LaneBitmask getLaneMaskForIndex(uint32_t K) const
Definition: RDFGraph.h:434
uint16_t getKind() const
Definition: RDFGraph.h:455
MachineInstr * getCode() const
Definition: RDFGraph.h:621
static bool IsPhi(const NodeAddr< NodeBase *> BA)
Definition: RDFGraph.h:807
static uint16_t flags(uint16_t T)
Definition: RDFGraph.h:295
TargetOperandInfo(const TargetInstrInfo &tii)
Definition: RDFGraph.h:415
NodeId getPredecessor() const
Definition: RDFGraph.h:580
constexpr bool all() const
Definition: LaneBitmask.h:53
static bool contains(uint16_t A, uint16_t B)
Definition: RDFGraph.h:310
NodeList members_if(Predicate P, const DataFlowGraph &G) const
Definition: RDFGraph.h:913
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
static wasm::ValType getType(const TargetRegisterClass *RC)
auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1213
RegisterRef unpack(PackedRegisterRef PR) const
Definition: RDFGraph.h:746
const PhysicalRegisterInfo & getPRI() const
Definition: RDFGraph.h:664
const DataFlowGraph & G
Definition: RDFGraph.h:932
void setPredecessor(NodeId B)
Definition: RDFGraph.h:584
bool isUse() const
Definition: RDFGraph.h:542
MachineFunction * getCode() const
Definition: RDFGraph.h:635
auto size(R &&Range, typename std::enable_if< std::is_same< typename std::iterator_traits< decltype(Range.begin())>::iterator_category, std::random_access_iterator_tag >::value, void >::type *=nullptr) -> decltype(std::distance(Range.begin(), Range.end()))
Get the size of a range.
Definition: STLExtras.h:1173
MachineOperand class - Representation of each machine instruction operand.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
NodeAddr(const NodeAddr< S > &NA)
Definition: RDFGraph.h:340
MachineInstr * getCode() const
Definition: RDFGraph.h:615
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
Definition: PPCPredicates.h:26
const DataFlowGraph & G
Definition: RDFGraph.cpp:202
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
void setAttrs(uint16_t A)
Definition: RDFGraph.h:460
static uint16_t set_type(uint16_t A, uint16_t T)
Definition: RDFGraph.h:297
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:538
const MachineDominanceFrontier & getDF() const
Definition: RDFGraph.h:666
NodeId getReachedDef() const
Definition: RDFGraph.h:559
static void clear(coro::Shape &Shape)
Definition: Coroutines.cpp:211
const RegisterAggr & getLiveIns() const
Definition: RDFGraph.h:667
std::set< NodeId > NodeSet
Definition: RDFGraph.h:513
bool operator!=(uint64_t V1, const APInt &V2)
Definition: APInt.h:1968
Representation of each machine instruction.
Definition: MachineInstr.h:64
NodeId getReachingDef() const
Definition: RDFGraph.h:528
static uint16_t set_kind(uint16_t A, uint16_t K)
Definition: RDFGraph.h:301
PackedRegisterRef pack(RegisterRef RR)
Definition: RDFGraph.h:740
uint16_t Reserved
Definition: RDFGraph.h:473
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
constexpr bool any() const
Definition: LaneBitmask.h:52
static bool IsCode(const NodeAddr< NodeBase *> BA)
Definition: RDFGraph.h:792
NodeBase * ptr(NodeId N) const
Definition: RDFGraph.h:383
void push(NodeAddr< DefNode *> DA)
Definition: RDFGraph.h:711
PackedRegisterRef pack(RegisterRef RR) const
Definition: RDFGraph.h:743
Print(const T &x, const DataFlowGraph &g)
Definition: RDFGraph.h:929
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
MachineBasicBlock * getCode() const
Definition: RDFGraph.h:627
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
static bool IsDef(const NodeAddr< NodeBase *> BA)
Definition: RDFGraph.h:797
IRTranslator LLVM IR MI
bool operator==(uint64_t V1, const APInt &V2)
Definition: APInt.h:1966
NodeAddr(T A, NodeId I)
Definition: RDFGraph.h:336
NodeId getSibling() const
Definition: RDFGraph.h:535
static bool IsRef(const NodeAddr< NodeBase *> BA)
Definition: RDFGraph.h:786
NodeAddr< RefNode * > getNextRef(RegisterRef RR, Predicate P, bool NextOnly, const DataFlowGraph &G)
Definition: RDFGraph.h:887
std::unordered_map< RegisterId, DefStack > DefStackMap
Definition: RDFGraph.h:733
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
void setReachedUse(NodeId U)
Definition: RDFGraph.h:568
uint32_t getIndexForLaneMask(LaneBitmask LM)
Definition: RDFGraph.h:438
void setSibling(NodeId Sib)
Definition: RDFGraph.h:538