LLVM  6.0.0svn
RDFGraph.h
Go to the documentation of this file.
1 //===- RDFGraph.h -----------------------------------------------*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // Target-independent, SSA-based data flow graph for register data flow (RDF)
11 // for a non-SSA program representation (e.g. post-RA machine code).
12 //
13 //
14 // *** Introduction
15 //
16 // The RDF graph is a collection of nodes, each of which denotes some element
17 // of the program. There are two main types of such elements: code and refe-
18 // rences. Conceptually, "code" is something that represents the structure
19 // of the program, e.g. basic block or a statement, while "reference" is an
20 // instance of accessing a register, e.g. a definition or a use. Nodes are
21 // connected with each other based on the structure of the program (such as
22 // blocks, instructions, etc.), and based on the data flow (e.g. reaching
23 // definitions, reached uses, etc.). The single-reaching-definition principle
24 // of SSA is generally observed, although, due to the non-SSA representation
25 // of the program, there are some differences between the graph and a "pure"
26 // SSA representation.
27 //
28 //
29 // *** Implementation remarks
30 //
31 // Since the graph can contain a large number of nodes, memory consumption
32 // was one of the major design considerations. As a result, there is a single
33 // base class NodeBase which defines all members used by all possible derived
34 // classes. The members are arranged in a union, and a derived class cannot
35 // add any data members of its own. Each derived class only defines the
36 // functional interface, i.e. member functions. NodeBase must be a POD,
37 // which implies that all of its members must also be PODs.
38 // Since nodes need to be connected with other nodes, pointers have been
39 // replaced with 32-bit identifiers: each node has an id of type NodeId.
40 // There are mapping functions in the graph that translate between actual
41 // memory addresses and the corresponding identifiers.
42 // A node id of 0 is equivalent to nullptr.
43 //
44 //
45 // *** Structure of the graph
46 //
47 // A code node is always a collection of other nodes. For example, a code
48 // node corresponding to a basic block will contain code nodes corresponding
49 // to instructions. In turn, a code node corresponding to an instruction will
50 // contain a list of reference nodes that correspond to the definitions and
51 // uses of registers in that instruction. The members are arranged into a
52 // circular list, which is yet another consequence of the effort to save
53 // memory: for each member node it should be possible to obtain its owner,
54 // and it should be possible to access all other members. There are other
55 // ways to accomplish that, but the circular list seemed the most natural.
56 //
57 // +- CodeNode -+
58 // | | <---------------------------------------------------+
59 // +-+--------+-+ |
60 // |FirstM |LastM |
61 // | +-------------------------------------+ |
62 // | | |
63 // V V |
64 // +----------+ Next +----------+ Next Next +----------+ Next |
65 // | |----->| |-----> ... ----->| |----->-+
66 // +- Member -+ +- Member -+ +- Member -+
67 //
68 // The order of members is such that related reference nodes (see below)
69 // should be contiguous on the member list.
70 //
71 // A reference node is a node that encapsulates an access to a register,
72 // in other words, data flowing into or out of a register. There are two
73 // major kinds of reference nodes: defs and uses. A def node will contain
74 // the id of the first reached use, and the id of the first reached def.
75 // Each def and use will contain the id of the reaching def, and also the
76 // id of the next reached def (for def nodes) or use (for use nodes).
77 // The "next node sharing the same reaching def" is denoted as "sibling".
78 // In summary:
79 // - Def node contains: reaching def, sibling, first reached def, and first
80 // reached use.
81 // - Use node contains: reaching def and sibling.
82 //
83 // +-- DefNode --+
84 // | R2 = ... | <---+--------------------+
85 // ++---------+--+ | |
86 // |Reached |Reached | |
87 // |Def |Use | |
88 // | | |Reaching |Reaching
89 // | V |Def |Def
90 // | +-- UseNode --+ Sib +-- UseNode --+ Sib Sib
91 // | | ... = R2 |----->| ... = R2 |----> ... ----> 0
92 // | +-------------+ +-------------+
93 // V
94 // +-- DefNode --+ Sib
95 // | R2 = ... |----> ...
96 // ++---------+--+
97 // | |
98 // | |
99 // ... ...
100 //
101 // To get a full picture, the circular lists connecting blocks within a
102 // function, instructions within a block, etc. should be superimposed with
103 // the def-def, def-use links shown above.
104 // To illustrate this, consider a small example in a pseudo-assembly:
105 // foo:
106 // add r2, r0, r1 ; r2 = r0+r1
107 // addi r0, r2, 1 ; r0 = r2+1
108 // ret r0 ; return value in r0
109 //
110 // The graph (in a format used by the debugging functions) would look like:
111 //
112 // DFG dump:[
113 // f1: Function foo
114 // b2: === BB#0 === preds(0), succs(0):
115 // p3: phi [d4<r0>(,d12,u9):]
116 // p5: phi [d6<r1>(,,u10):]
117 // s7: add [d8<r2>(,,u13):, u9<r0>(d4):, u10<r1>(d6):]
118 // s11: addi [d12<r0>(d4,,u15):, u13<r2>(d8):]
119 // s14: ret [u15<r0>(d12):]
120 // ]
121 //
122 // The f1, b2, p3, etc. are node ids. The letter is prepended to indicate the
123 // kind of the node (i.e. f - function, b - basic block, p - phi, s - state-
124 // ment, d - def, u - use).
125 // The format of a def node is:
126 // dN<R>(rd,d,u):sib,
127 // where
128 // N - numeric node id,
129 // R - register being defined
130 // rd - reaching def,
131 // d - reached def,
132 // u - reached use,
133 // sib - sibling.
134 // The format of a use node is:
135 // uN<R>[!](rd):sib,
136 // where
137 // N - numeric node id,
138 // R - register being used,
139 // rd - reaching def,
140 // sib - sibling.
141 // Possible annotations (usually preceding the node id):
142 // + - preserving def,
143 // ~ - clobbering def,
144 // " - shadow ref (follows the node id),
145 // ! - fixed register (appears after register name).
146 //
147 // The circular lists are not explicit in the dump.
148 //
149 //
150 // *** Node attributes
151 //
152 // NodeBase has a member "Attrs", which is the primary way of determining
153 // the node's characteristics. The fields in this member decide whether
154 // the node is a code node or a reference node (i.e. node's "type"), then
155 // within each type, the "kind" determines what specifically this node
156 // represents. The remaining bits, "flags", contain additional information
157 // that is even more detailed than the "kind".
158 // CodeNode's kinds are:
159 // - Phi: Phi node, members are reference nodes.
160 // - Stmt: Statement, members are reference nodes.
161 // - Block: Basic block, members are instruction nodes (i.e. Phi or Stmt).
162 // - Func: The whole function. The members are basic block nodes.
163 // RefNode's kinds are:
164 // - Use.
165 // - Def.
166 //
167 // Meaning of flags:
168 // - Preserving: applies only to defs. A preserving def is one that can
169 // preserve some of the original bits among those that are included in
170 // the register associated with that def. For example, if R0 is a 32-bit
171 // register, but a def can only change the lower 16 bits, then it will
172 // be marked as preserving.
173 // - Shadow: a reference that has duplicates holding additional reaching
174 // defs (see more below).
175 // - Clobbering: applied only to defs, indicates that the value generated
176 // by this def is unspecified. A typical example would be volatile registers
177 // after function calls.
178 // - Fixed: the register in this def/use cannot be replaced with any other
179 // register. A typical case would be a parameter register to a call, or
180 // the register with the return value from a function.
181 // - Undef: the register in this reference the register is assumed to have
182 // no pre-existing value, even if it appears to be reached by some def.
183 // This is typically used to prevent keeping registers artificially live
184 // in cases when they are defined via predicated instructions. For example:
185 // r0 = add-if-true cond, r10, r11 (1)
186 // r0 = add-if-false cond, r12, r13, r0<imp-use> (2)
187 // ... = r0 (3)
188 // Before (1), r0 is not intended to be live, and the use of r0 in (3) is
189 // not meant to be reached by any def preceding (1). However, since the
190 // defs in (1) and (2) are both preserving, these properties alone would
191 // imply that the use in (3) may indeed be reached by some prior def.
192 // Adding Undef flag to the def in (1) prevents that. The Undef flag
193 // may be applied to both defs and uses.
194 // - Dead: applies only to defs. The value coming out of a "dead" def is
195 // assumed to be unused, even if the def appears to be reaching other defs
196 // or uses. The motivation for this flag comes from dead defs on function
197 // calls: there is no way to determine if such a def is dead without
198 // analyzing the target's ABI. Hence the graph should contain this info,
199 // as it is unavailable otherwise. On the other hand, a def without any
200 // uses on a typical instruction is not the intended target for this flag.
201 //
202 // *** Shadow references
203 //
204 // It may happen that a super-register can have two (or more) non-overlapping
205 // sub-registers. When both of these sub-registers are defined and followed
206 // by a use of the super-register, the use of the super-register will not
207 // have a unique reaching def: both defs of the sub-registers need to be
208 // accounted for. In such cases, a duplicate use of the super-register is
209 // added and it points to the extra reaching def. Both uses are marked with
210 // a flag "shadow". Example:
211 // Assume t0 is a super-register of r0 and r1, r0 and r1 do not overlap:
212 // set r0, 1 ; r0 = 1
213 // set r1, 1 ; r1 = 1
214 // addi t1, t0, 1 ; t1 = t0+1
215 //
216 // The DFG:
217 // s1: set [d2<r0>(,,u9):]
218 // s3: set [d4<r1>(,,u10):]
219 // s5: addi [d6<t1>(,,):, u7"<t0>(d2):, u8"<t0>(d4):]
220 //
221 // The statement s5 has two use nodes for t0: u7" and u9". The quotation
222 // mark " indicates that the node is a shadow.
223 //
224 
225 #ifndef LLVM_LIB_TARGET_HEXAGON_RDFGRAPH_H
226 #define LLVM_LIB_TARGET_HEXAGON_RDFGRAPH_H
227 
228 #include "RDFRegisters.h"
229 #include "llvm/ADT/SmallVector.h"
230 #include "llvm/MC/LaneBitmask.h"
231 #include "llvm/Support/Allocator.h"
232 #include "llvm/Support/MathExtras.h"
233 #include <cassert>
234 #include <cstdint>
235 #include <cstring>
236 #include <map>
237 #include <set>
238 #include <unordered_map>
239 #include <utility>
240 #include <vector>
241 
242 // RDF uses uint32_t to refer to registers. This is to ensure that the type
243 // size remains specific. In other places, registers are often stored using
244 // unsigned.
245 static_assert(sizeof(uint32_t) == sizeof(unsigned), "Those should be equal");
246 
247 namespace llvm {
248 
249 class MachineBasicBlock;
250 class MachineDominanceFrontier;
251 class MachineDominatorTree;
252 class MachineFunction;
253 class MachineInstr;
254 class MachineOperand;
255 class raw_ostream;
256 class TargetInstrInfo;
257 class TargetRegisterInfo;
258 
259 namespace rdf {
260 
261  using NodeId = uint32_t;
262 
263  struct DataFlowGraph;
264 
265  struct NodeAttrs {
266  enum : uint16_t {
267  None = 0x0000, // Nothing
268 
269  // Types: 2 bits
270  TypeMask = 0x0003,
271  Code = 0x0001, // 01, Container
272  Ref = 0x0002, // 10, Reference
273 
274  // Kind: 3 bits
275  KindMask = 0x0007 << 2,
276  Def = 0x0001 << 2, // 001
277  Use = 0x0002 << 2, // 010
278  Phi = 0x0003 << 2, // 011
279  Stmt = 0x0004 << 2, // 100
280  Block = 0x0005 << 2, // 101
281  Func = 0x0006 << 2, // 110
282 
283  // Flags: 7 bits for now
284  FlagMask = 0x007F << 5,
285  Shadow = 0x0001 << 5, // 0000001, Has extra reaching defs.
286  Clobbering = 0x0002 << 5, // 0000010, Produces unspecified values.
287  PhiRef = 0x0004 << 5, // 0000100, Member of PhiNode.
288  Preserving = 0x0008 << 5, // 0001000, Def can keep original bits.
289  Fixed = 0x0010 << 5, // 0010000, Fixed register.
290  Undef = 0x0020 << 5, // 0100000, Has no pre-existing value.
291  Dead = 0x0040 << 5, // 1000000, Does not define a value.
292  };
293 
294  static uint16_t type(uint16_t T) { return T & TypeMask; }
295  static uint16_t kind(uint16_t T) { return T & KindMask; }
296  static uint16_t flags(uint16_t T) { return T & FlagMask; }
297 
298  static uint16_t set_type(uint16_t A, uint16_t T) {
299  return (A & ~TypeMask) | T;
300  }
301 
302  static uint16_t set_kind(uint16_t A, uint16_t K) {
303  return (A & ~KindMask) | K;
304  }
305 
306  static uint16_t set_flags(uint16_t A, uint16_t F) {
307  return (A & ~FlagMask) | F;
308  }
309 
310  // Test if A contains B.
311  static bool contains(uint16_t A, uint16_t B) {
312  if (type(A) != Code)
313  return false;
314  uint16_t KB = kind(B);
315  switch (kind(A)) {
316  case Func:
317  return KB == Block;
318  case Block:
319  return KB == Phi || KB == Stmt;
320  case Phi:
321  case Stmt:
322  return type(B) == Ref;
323  }
324  return false;
325  }
326  };
327 
328  struct BuildOptions {
329  enum : unsigned {
330  None = 0x00,
331  KeepDeadPhis = 0x01, // Do not remove dead phis during build.
332  };
333  };
334 
335  template <typename T> struct NodeAddr {
336  NodeAddr() = default;
337  NodeAddr(T A, NodeId I) : Addr(A), Id(I) {}
338 
339  // Type cast (casting constructor). The reason for having this class
340  // instead of std::pair.
341  template <typename S> NodeAddr(const NodeAddr<S> &NA)
342  : Addr(static_cast<T>(NA.Addr)), Id(NA.Id) {}
343 
344  bool operator== (const NodeAddr<T> &NA) const {
345  assert((Addr == NA.Addr) == (Id == NA.Id));
346  return Addr == NA.Addr;
347  }
348  bool operator!= (const NodeAddr<T> &NA) const {
349  return !operator==(NA);
350  }
351 
352  T Addr = nullptr;
353  NodeId Id = 0;
354  };
355 
356  struct NodeBase;
357 
358  // Fast memory allocation and translation between node id and node address.
359  // This is really the same idea as the one underlying the "bump pointer
360  // allocator", the difference being in the translation. A node id is
361  // composed of two components: the index of the block in which it was
362  // allocated, and the index within the block. With the default settings,
363  // where the number of nodes per block is 4096, the node id (minus 1) is:
364  //
365  // bit position: 11 0
366  // +----------------------------+--------------+
367  // | Index of the block |Index in block|
368  // +----------------------------+--------------+
369  //
370  // The actual node id is the above plus 1, to avoid creating a node id of 0.
371  //
372  // This method significantly improved the build time, compared to using maps
373  // (std::unordered_map or DenseMap) to translate between pointers and ids.
374  struct NodeAllocator {
375  // Amount of storage for a single node.
376  enum { NodeMemSize = 32 };
377 
379  : NodesPerBlock(NPB), BitsPerIndex(Log2_32(NPB)),
380  IndexMask((1 << BitsPerIndex)-1) {
381  assert(isPowerOf2_32(NPB));
382  }
383 
384  NodeBase *ptr(NodeId N) const {
385  uint32_t N1 = N-1;
386  uint32_t BlockN = N1 >> BitsPerIndex;
387  uint32_t Offset = (N1 & IndexMask) * NodeMemSize;
388  return reinterpret_cast<NodeBase*>(Blocks[BlockN]+Offset);
389  }
390 
391  NodeId id(const NodeBase *P) const;
392  NodeAddr<NodeBase*> New();
393  void clear();
394 
395  private:
396  void startNewBlock();
397  bool needNewBlock();
398 
399  uint32_t makeId(uint32_t Block, uint32_t Index) const {
400  // Add 1 to the id, to avoid the id of 0, which is treated as "null".
401  return ((Block << BitsPerIndex) | Index) + 1;
402  }
403 
404  const uint32_t NodesPerBlock;
405  const uint32_t BitsPerIndex;
406  const uint32_t IndexMask;
407  char *ActiveEnd = nullptr;
408  std::vector<char*> Blocks;
410  AllocatorTy MemPool;
411  };
412 
413  using RegisterSet = std::set<RegisterRef>;
414 
416  TargetOperandInfo(const TargetInstrInfo &tii) : TII(tii) {}
417  virtual ~TargetOperandInfo() = default;
418 
419  virtual bool isPreserving(const MachineInstr &In, unsigned OpNum) const;
420  virtual bool isClobbering(const MachineInstr &In, unsigned OpNum) const;
421  virtual bool isFixedReg(const MachineInstr &In, unsigned OpNum) const;
422 
424  };
425 
426  // Packed register reference. Only used for storage.
430  };
431 
432  struct LaneMaskIndex : private IndexedSet<LaneBitmask> {
433  LaneMaskIndex() = default;
434 
436  return K == 0 ? LaneBitmask::getAll() : get(K);
437  }
438 
440  assert(LM.any());
441  return LM.all() ? 0 : insert(LM);
442  }
443 
445  assert(LM.any());
446  return LM.all() ? 0 : find(LM);
447  }
448  };
449 
450  struct NodeBase {
451  public:
452  // Make sure this is a POD.
453  NodeBase() = default;
454 
455  uint16_t getType() const { return NodeAttrs::type(Attrs); }
456  uint16_t getKind() const { return NodeAttrs::kind(Attrs); }
457  uint16_t getFlags() const { return NodeAttrs::flags(Attrs); }
458  NodeId getNext() const { return Next; }
459 
460  uint16_t getAttrs() const { return Attrs; }
461  void setAttrs(uint16_t A) { Attrs = A; }
462  void setFlags(uint16_t F) { setAttrs(NodeAttrs::set_flags(getAttrs(), F)); }
463 
464  // Insert node NA after "this" in the circular chain.
465  void append(NodeAddr<NodeBase*> NA);
466 
467  // Initialize all members to 0.
468  void init() { memset(this, 0, sizeof *this); }
469 
470  void setNext(NodeId N) { Next = N; }
471 
472  protected:
473  uint16_t Attrs;
474  uint16_t Reserved;
475  NodeId Next; // Id of the next node in the circular chain.
476  // Definitions of nested types. Using anonymous nested structs would make
477  // this class definition clearer, but unnamed structs are not a part of
478  // the standard.
479  struct Def_struct {
480  NodeId DD, DU; // Ids of the first reached def and use.
481  };
482  struct PhiU_struct {
483  NodeId PredB; // Id of the predecessor block for a phi use.
484  };
485  struct Code_struct {
486  void *CP; // Pointer to the actual code.
487  NodeId FirstM, LastM; // Id of the first member and last.
488  };
489  struct Ref_struct {
490  NodeId RD, Sib; // Ids of the reaching def and the sibling.
491  union {
494  };
495  union {
496  MachineOperand *Op; // Non-phi refs point to a machine operand.
497  PackedRegisterRef PR; // Phi refs store register info directly.
498  };
499  };
500 
501  // The actual payload.
502  union {
505  };
506  };
507  // The allocator allocates chunks of 32 bytes for each node. The fact that
508  // each node takes 32 bytes in memory is used for fast translation between
509  // the node id and the node address.
510  static_assert(sizeof(NodeBase) <= NodeAllocator::NodeMemSize,
511  "NodeBase must be at most NodeAllocator::NodeMemSize bytes");
512 
514  using NodeSet = std::set<NodeId>;
515 
516  struct RefNode : public NodeBase {
517  RefNode() = default;
518 
519  RegisterRef getRegRef(const DataFlowGraph &G) const;
520 
522  assert(!(getFlags() & NodeAttrs::PhiRef));
523  return *Ref.Op;
524  }
525 
526  void setRegRef(RegisterRef RR, DataFlowGraph &G);
527  void setRegRef(MachineOperand *Op, DataFlowGraph &G);
528 
530  return Ref.RD;
531  }
533  Ref.RD = RD;
534  }
535 
536  NodeId getSibling() const {
537  return Ref.Sib;
538  }
539  void setSibling(NodeId Sib) {
540  Ref.Sib = Sib;
541  }
542 
543  bool isUse() const {
545  return getKind() == NodeAttrs::Use;
546  }
547 
548  bool isDef() const {
550  return getKind() == NodeAttrs::Def;
551  }
552 
553  template <typename Predicate>
554  NodeAddr<RefNode*> getNextRef(RegisterRef RR, Predicate P, bool NextOnly,
555  const DataFlowGraph &G);
556  NodeAddr<NodeBase*> getOwner(const DataFlowGraph &G);
557  };
558 
559  struct DefNode : public RefNode {
561  return Ref.Def.DD;
562  }
564  Ref.Def.DD = D;
565  }
567  return Ref.Def.DU;
568  }
570  Ref.Def.DU = U;
571  }
572 
573  void linkToDef(NodeId Self, NodeAddr<DefNode*> DA);
574  };
575 
576  struct UseNode : public RefNode {
577  void linkToDef(NodeId Self, NodeAddr<DefNode*> DA);
578  };
579 
580  struct PhiUseNode : public UseNode {
582  assert(getFlags() & NodeAttrs::PhiRef);
583  return Ref.PhiU.PredB;
584  }
586  assert(getFlags() & NodeAttrs::PhiRef);
587  Ref.PhiU.PredB = B;
588  }
589  };
590 
591  struct CodeNode : public NodeBase {
592  template <typename T> T getCode() const {
593  return static_cast<T>(Code.CP);
594  }
595  void setCode(void *C) {
596  Code.CP = C;
597  }
598 
599  NodeAddr<NodeBase*> getFirstMember(const DataFlowGraph &G) const;
600  NodeAddr<NodeBase*> getLastMember(const DataFlowGraph &G) const;
601  void addMember(NodeAddr<NodeBase*> NA, const DataFlowGraph &G);
602  void addMemberAfter(NodeAddr<NodeBase*> MA, NodeAddr<NodeBase*> NA,
603  const DataFlowGraph &G);
604  void removeMember(NodeAddr<NodeBase*> NA, const DataFlowGraph &G);
605 
606  NodeList members(const DataFlowGraph &G) const;
607  template <typename Predicate>
608  NodeList members_if(Predicate P, const DataFlowGraph &G) const;
609  };
610 
611  struct InstrNode : public CodeNode {
612  NodeAddr<NodeBase*> getOwner(const DataFlowGraph &G);
613  };
614 
615  struct PhiNode : public InstrNode {
617  return nullptr;
618  }
619  };
620 
621  struct StmtNode : public InstrNode {
623  return CodeNode::getCode<MachineInstr*>();
624  }
625  };
626 
627  struct BlockNode : public CodeNode {
629  return CodeNode::getCode<MachineBasicBlock*>();
630  }
631 
632  void addPhi(NodeAddr<PhiNode*> PA, const DataFlowGraph &G);
633  };
634 
635  struct FuncNode : public CodeNode {
637  return CodeNode::getCode<MachineFunction*>();
638  }
639 
640  NodeAddr<BlockNode*> findBlock(const MachineBasicBlock *BB,
641  const DataFlowGraph &G) const;
642  NodeAddr<BlockNode*> getEntryBlock(const DataFlowGraph &G);
643  };
644 
645  struct DataFlowGraph {
647  const TargetRegisterInfo &tri, const MachineDominatorTree &mdt,
648  const MachineDominanceFrontier &mdf, const TargetOperandInfo &toi);
649 
650  NodeBase *ptr(NodeId N) const;
651  template <typename T> T ptr(NodeId N) const {
652  return static_cast<T>(ptr(N));
653  }
654 
655  NodeId id(const NodeBase *P) const;
656 
657  template <typename T> NodeAddr<T> addr(NodeId N) const {
658  return { ptr<T>(N), N };
659  }
660 
661  NodeAddr<FuncNode*> getFunc() const { return Func; }
662  MachineFunction &getMF() const { return MF; }
663  const TargetInstrInfo &getTII() const { return TII; }
664  const TargetRegisterInfo &getTRI() const { return TRI; }
665  const PhysicalRegisterInfo &getPRI() const { return PRI; }
666  const MachineDominatorTree &getDT() const { return MDT; }
667  const MachineDominanceFrontier &getDF() const { return MDF; }
668  const RegisterAggr &getLiveIns() const { return LiveIns; }
669 
670  struct DefStack {
671  DefStack() = default;
672 
673  bool empty() const { return Stack.empty() || top() == bottom(); }
674 
675  private:
677  struct Iterator {
679 
680  Iterator &up() { Pos = DS.nextUp(Pos); return *this; }
681  Iterator &down() { Pos = DS.nextDown(Pos); return *this; }
682 
683  value_type operator*() const {
684  assert(Pos >= 1);
685  return DS.Stack[Pos-1];
686  }
687  const value_type *operator->() const {
688  assert(Pos >= 1);
689  return &DS.Stack[Pos-1];
690  }
691  bool operator==(const Iterator &It) const { return Pos == It.Pos; }
692  bool operator!=(const Iterator &It) const { return Pos != It.Pos; }
693 
694  private:
695  friend struct DefStack;
696 
697  Iterator(const DefStack &S, bool Top);
698 
699  // Pos-1 is the index in the StorageType object that corresponds to
700  // the top of the DefStack.
701  const DefStack &DS;
702  unsigned Pos;
703  };
704 
705  public:
706  using iterator = Iterator;
707 
708  iterator top() const { return Iterator(*this, true); }
709  iterator bottom() const { return Iterator(*this, false); }
710  unsigned size() const;
711 
712  void push(NodeAddr<DefNode*> DA) { Stack.push_back(DA); }
713  void pop();
714  void start_block(NodeId N);
715  void clear_block(NodeId N);
716 
717  private:
718  friend struct Iterator;
719 
720  using StorageType = std::vector<value_type>;
721 
722  bool isDelimiter(const StorageType::value_type &P, NodeId N = 0) const {
723  return (P.Addr == nullptr) && (N == 0 || P.Id == N);
724  }
725 
726  unsigned nextUp(unsigned P) const;
727  unsigned nextDown(unsigned P) const;
728 
729  StorageType Stack;
730  };
731 
732  // Make this std::unordered_map for speed of accessing elements.
733  // Map: Register (physical or virtual) -> DefStack
734  using DefStackMap = std::unordered_map<RegisterId, DefStack>;
735 
736  void build(unsigned Options = BuildOptions::None);
737  void pushAllDefs(NodeAddr<InstrNode*> IA, DefStackMap &DM);
738  void markBlock(NodeId B, DefStackMap &DefM);
739  void releaseBlock(NodeId B, DefStackMap &DefM);
740 
742  return { RR.Reg, LMI.getIndexForLaneMask(RR.Mask) };
743  }
745  return { RR.Reg, LMI.getIndexForLaneMask(RR.Mask) };
746  }
748  return RegisterRef(PR.Reg, LMI.getLaneMaskForIndex(PR.MaskId));
749  }
750 
751  RegisterRef makeRegRef(unsigned Reg, unsigned Sub) const;
752  RegisterRef makeRegRef(const MachineOperand &Op) const;
753  RegisterRef restrictRef(RegisterRef AR, RegisterRef BR) const;
754 
755  NodeAddr<RefNode*> getNextRelated(NodeAddr<InstrNode*> IA,
756  NodeAddr<RefNode*> RA) const;
758  NodeAddr<RefNode*> RA, bool Create);
760  NodeAddr<RefNode*> RA) const;
761  NodeAddr<RefNode*> getNextShadow(NodeAddr<InstrNode*> IA,
762  NodeAddr<RefNode*> RA, bool Create);
763  NodeAddr<RefNode*> getNextShadow(NodeAddr<InstrNode*> IA,
764  NodeAddr<RefNode*> RA) const;
765 
766  NodeList getRelatedRefs(NodeAddr<InstrNode*> IA,
767  NodeAddr<RefNode*> RA) const;
768 
770  return BlockNodes.at(BB);
771  }
772 
773  void unlinkUse(NodeAddr<UseNode*> UA, bool RemoveFromOwner) {
774  unlinkUseDF(UA);
775  if (RemoveFromOwner)
776  removeFromOwner(UA);
777  }
778 
779  void unlinkDef(NodeAddr<DefNode*> DA, bool RemoveFromOwner) {
780  unlinkDefDF(DA);
781  if (RemoveFromOwner)
782  removeFromOwner(DA);
783  }
784 
785  // Some useful filters.
786  template <uint16_t Kind>
787  static bool IsRef(const NodeAddr<NodeBase*> BA) {
788  return BA.Addr->getType() == NodeAttrs::Ref &&
789  BA.Addr->getKind() == Kind;
790  }
791 
792  template <uint16_t Kind>
793  static bool IsCode(const NodeAddr<NodeBase*> BA) {
794  return BA.Addr->getType() == NodeAttrs::Code &&
795  BA.Addr->getKind() == Kind;
796  }
797 
798  static bool IsDef(const NodeAddr<NodeBase*> BA) {
799  return BA.Addr->getType() == NodeAttrs::Ref &&
800  BA.Addr->getKind() == NodeAttrs::Def;
801  }
802 
803  static bool IsUse(const NodeAddr<NodeBase*> BA) {
804  return BA.Addr->getType() == NodeAttrs::Ref &&
805  BA.Addr->getKind() == NodeAttrs::Use;
806  }
807 
808  static bool IsPhi(const NodeAddr<NodeBase*> BA) {
809  return BA.Addr->getType() == NodeAttrs::Code &&
810  BA.Addr->getKind() == NodeAttrs::Phi;
811  }
812 
813  static bool IsPreservingDef(const NodeAddr<DefNode*> DA) {
814  uint16_t Flags = DA.Addr->getFlags();
815  return (Flags & NodeAttrs::Preserving) && !(Flags & NodeAttrs::Undef);
816  }
817 
818  private:
819  void reset();
820 
821  RegisterSet getLandingPadLiveIns() const;
822 
823  NodeAddr<NodeBase*> newNode(uint16_t Attrs);
824  NodeAddr<NodeBase*> cloneNode(const NodeAddr<NodeBase*> B);
826  MachineOperand &Op, uint16_t Flags = NodeAttrs::None);
829  uint16_t Flags = NodeAttrs::PhiRef);
831  MachineOperand &Op, uint16_t Flags = NodeAttrs::None);
833  RegisterRef RR, uint16_t Flags = NodeAttrs::PhiRef);
836  MachineInstr *MI);
838  MachineBasicBlock *BB);
840 
841  template <typename Predicate>
842  std::pair<NodeAddr<RefNode*>,NodeAddr<RefNode*>>
843  locateNextRef(NodeAddr<InstrNode*> IA, NodeAddr<RefNode*> RA,
844  Predicate P) const;
845 
846  using BlockRefsMap = std::map<NodeId, RegisterSet>;
847 
848  void buildStmt(NodeAddr<BlockNode*> BA, MachineInstr &In);
849  void recordDefsForDF(BlockRefsMap &PhiM, NodeAddr<BlockNode*> BA);
850  void buildPhis(BlockRefsMap &PhiM, RegisterSet &AllRefs,
852  void removeUnusedPhis();
853 
854  void pushClobbers(NodeAddr<InstrNode*> IA, DefStackMap &DM);
855  void pushDefs(NodeAddr<InstrNode*> IA, DefStackMap &DM);
856  template <typename T> void linkRefUp(NodeAddr<InstrNode*> IA,
858  template <typename Predicate> void linkStmtRefs(DefStackMap &DefM,
860  void linkBlockRefs(DefStackMap &DefM, NodeAddr<BlockNode*> BA);
861 
862  void unlinkUseDF(NodeAddr<UseNode*> UA);
863  void unlinkDefDF(NodeAddr<DefNode*> DA);
864 
865  void removeFromOwner(NodeAddr<RefNode*> RA) {
866  NodeAddr<InstrNode*> IA = RA.Addr->getOwner(*this);
867  IA.Addr->removeMember(RA, *this);
868  }
869 
870  MachineFunction &MF;
871  const TargetInstrInfo &TII;
872  const TargetRegisterInfo &TRI;
873  const PhysicalRegisterInfo PRI;
874  const MachineDominatorTree &MDT;
875  const MachineDominanceFrontier &MDF;
876  const TargetOperandInfo &TOI;
877 
878  RegisterAggr LiveIns;
881  // Local map: MachineBasicBlock -> NodeAddr<BlockNode*>
882  std::map<MachineBasicBlock*,NodeAddr<BlockNode*>> BlockNodes;
883  // Lane mask map.
884  LaneMaskIndex LMI;
885  }; // struct DataFlowGraph
886 
887  template <typename Predicate>
889  bool NextOnly, const DataFlowGraph &G) {
890  // Get the "Next" reference in the circular list that references RR and
891  // satisfies predicate "Pred".
892  auto NA = G.addr<NodeBase*>(getNext());
893 
894  while (NA.Addr != this) {
895  if (NA.Addr->getType() == NodeAttrs::Ref) {
896  NodeAddr<RefNode*> RA = NA;
897  if (RA.Addr->getRegRef(G) == RR && P(NA))
898  return NA;
899  if (NextOnly)
900  break;
901  NA = G.addr<NodeBase*>(NA.Addr->getNext());
902  } else {
903  // We've hit the beginning of the chain.
904  assert(NA.Addr->getType() == NodeAttrs::Code);
905  NodeAddr<CodeNode*> CA = NA;
906  NA = CA.Addr->getFirstMember(G);
907  }
908  }
909  // Return the equivalent of "nullptr" if such a node was not found.
910  return NodeAddr<RefNode*>();
911  }
912 
913  template <typename Predicate>
915  NodeList MM;
916  auto M = getFirstMember(G);
917  if (M.Id == 0)
918  return MM;
919 
920  while (M.Addr != this) {
921  if (P(M))
922  MM.push_back(M);
923  M = G.addr<NodeBase*>(M.Addr->getNext());
924  }
925  return MM;
926  }
927 
928  template <typename T> struct Print;
929  template <typename T>
930  raw_ostream &operator<< (raw_ostream &OS, const Print<T> &P);
931 
932  template <typename T>
933  struct Print {
934  Print(const T &x, const DataFlowGraph &g) : Obj(x), G(g) {}
935 
936  const T &Obj;
937  const DataFlowGraph &G;
938  };
939 
940  template <typename T>
941  struct PrintNode : Print<NodeAddr<T>> {
942  PrintNode(const NodeAddr<T> &x, const DataFlowGraph &g)
943  : Print<NodeAddr<T>>(x, g) {}
944  };
945 
946 } // end namespace rdf
947 
948 } // end namespace llvm
949 
950 #endif // LLVM_LIB_TARGET_HEXAGON_RDFGRAPH_H
NodeAddr< BlockNode * > findBlock(MachineBasicBlock *BB) const
Definition: RDFGraph.h:769
uint64_t CallInst * C
void setReachingDef(NodeId RD)
Definition: RDFGraph.h:532
void push_back(const T &Elt)
Definition: SmallVector.h:212
NodeId getReachedUse() const
Definition: RDFGraph.h:566
A common definition of LaneBitmask for use in TableGen and CodeGen.
MachineFunction & getMF() const
Definition: RDFGraph.h:662
uint16_t getFlags() const
Definition: RDFGraph.h:457
static uint16_t kind(uint16_t T)
Definition: RDFGraph.h:295
T ptr(NodeId N) const
Definition: RDFGraph.h:651
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
void setCode(void *C)
Definition: RDFGraph.h:595
void setNext(NodeId N)
Definition: RDFGraph.h:470
uint16_t getType() const
Definition: RDFGraph.h:455
static uint16_t type(uint16_t T)
Definition: RDFGraph.h:294
void unlinkDef(NodeAddr< DefNode *> DA, bool RemoveFromOwner)
Definition: RDFGraph.h:779
This class provides various memory handling functions that manipulate MemoryBlock instances...
Definition: Memory.h:46
static bool IsPreservingDef(const NodeAddr< DefNode *> DA)
Definition: RDFGraph.h:813
Code_struct Code
Definition: RDFGraph.h:504
static LaneBitmask getAll()
Definition: LaneBitmask.h:84
uint32_t getIndexForLaneMask(LaneBitmask LM) const
Definition: RDFGraph.h:444
F(f)
MachineOperand & getOp()
Definition: RDFGraph.h:521
const T & Obj
Definition: RDFGraph.h:936
This file defines the MallocAllocator and BumpPtrAllocator interfaces.
const TargetInstrInfo & TII
Definition: RDFGraph.h:423
const TargetInstrInfo & getTII() const
Definition: RDFGraph.h:663
SI optimize exec mask operations pre RA
NodeAddr< FuncNode * > getFunc() const
Definition: RDFGraph.h:661
void append(SmallVectorImpl< char > &path, const Twine &a, const Twine &b="", const Twine &c="", const Twine &d="")
Append to path.
Definition: Path.cpp:465
const HexagonInstrInfo * TII
A Use represents the edge between a Value definition and its users.
Definition: Use.h:56
std::set< RegisterRef > RegisterSet
Definition: RDFGraph.h:413
Reg
All possible values of the reg field in the ModR/M byte.
void unlinkUse(NodeAddr< UseNode *> UA, bool RemoveFromOwner)
Definition: RDFGraph.h:773
APInt operator*(APInt a, uint64_t RHS)
Definition: APInt.h:2070
bool isDef() const
Definition: RDFGraph.h:548
uint16_t getAttrs() const
Definition: RDFGraph.h:460
#define T
NodeId getNext() const
Definition: RDFGraph.h:458
static uint16_t set_flags(uint16_t A, uint16_t F)
Definition: RDFGraph.h:306
const MachineDominatorTree & getDT() const
Definition: RDFGraph.h:666
constexpr char Attrs[]
Key for Kernel::Metadata::mAttrs.
Ref_struct Ref
Definition: RDFGraph.h:503
TargetInstrInfo - Interface to description of machine instruction set.
NodeAllocator(uint32_t NPB=4096)
Definition: RDFGraph.h:378
void setFlags(uint16_t F)
Definition: RDFGraph.h:462
void setReachedDef(NodeId D)
Definition: RDFGraph.h:563
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:311
#define P(N)
static bool IsUse(const NodeAddr< NodeBase *> BA)
Definition: RDFGraph.h:803
Control flow instructions. These all have token chains.
Definition: ISDOpcodes.h:596
T getCode() const
Definition: RDFGraph.h:592
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
PrintNode(const NodeAddr< T > &x, const DataFlowGraph &g)
Definition: RDFGraph.h:942
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
Definition: MathExtras.h:421
NodeAddr< T > addr(NodeId N) const
Definition: RDFGraph.h:657
const TargetRegisterInfo & getTRI() const
Definition: RDFGraph.h:664
LaneBitmask getLaneMaskForIndex(uint32_t K) const
Definition: RDFGraph.h:435
uint16_t getKind() const
Definition: RDFGraph.h:456
MachineInstr * getCode() const
Definition: RDFGraph.h:622
static bool IsPhi(const NodeAddr< NodeBase *> BA)
Definition: RDFGraph.h:808
static uint16_t flags(uint16_t T)
Definition: RDFGraph.h:296
TargetOperandInfo(const TargetInstrInfo &tii)
Definition: RDFGraph.h:416
NodeId getPredecessor() const
Definition: RDFGraph.h:581
constexpr bool all() const
Definition: LaneBitmask.h:54
static bool contains(uint16_t A, uint16_t B)
Definition: RDFGraph.h:311
NodeList members_if(Predicate P, const DataFlowGraph &G) const
Definition: RDFGraph.h:914
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:834
RegisterRef unpack(PackedRegisterRef PR) const
Definition: RDFGraph.h:747
const PhysicalRegisterInfo & getPRI() const
Definition: RDFGraph.h:665
const DataFlowGraph & G
Definition: RDFGraph.h:937
void setPredecessor(NodeId B)
Definition: RDFGraph.h:585
bool isUse() const
Definition: RDFGraph.h:543
MachineFunction * getCode() const
Definition: RDFGraph.h:636
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:864
NodeAddr(const NodeAddr< S > &NA)
Definition: RDFGraph.h:341
MachineInstr * getCode() const
Definition: RDFGraph.h:616
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
Definition: PPCPredicates.h:27
const DataFlowGraph & G
Definition: RDFGraph.cpp:211
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
void setAttrs(uint16_t A)
Definition: RDFGraph.h:461
static uint16_t set_type(uint16_t A, uint16_t T)
Definition: RDFGraph.h:298
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:531
const MachineDominanceFrontier & getDF() const
Definition: RDFGraph.h:667
NodeId getReachedDef() const
Definition: RDFGraph.h:560
static void clear(coro::Shape &Shape)
Definition: Coroutines.cpp:210
const RegisterAggr & getLiveIns() const
Definition: RDFGraph.h:668
std::set< NodeId > NodeSet
Definition: RDFGraph.h:514
bool operator!=(uint64_t V1, const APInt &V2)
Definition: APInt.h:1948
Representation of each machine instruction.
Definition: MachineInstr.h:59
NodeId getReachingDef() const
Definition: RDFGraph.h:529
static uint16_t set_kind(uint16_t A, uint16_t K)
Definition: RDFGraph.h:302
PackedRegisterRef pack(RegisterRef RR)
Definition: RDFGraph.h:741
uint16_t Reserved
Definition: RDFGraph.h:474
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
constexpr bool any() const
Definition: LaneBitmask.h:53
static bool IsCode(const NodeAddr< NodeBase *> BA)
Definition: RDFGraph.h:793
NodeBase * ptr(NodeId N) const
Definition: RDFGraph.h:384
void push(NodeAddr< DefNode *> DA)
Definition: RDFGraph.h:712
PackedRegisterRef pack(RegisterRef RR) const
Definition: RDFGraph.h:744
Print(const T &x, const DataFlowGraph &g)
Definition: RDFGraph.h:934
const unsigned Kind
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
MachineBasicBlock * getCode() const
Definition: RDFGraph.h:628
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:44
static bool IsDef(const NodeAddr< NodeBase *> BA)
Definition: RDFGraph.h:798
IRTranslator LLVM IR MI
bool operator==(uint64_t V1, const APInt &V2)
Definition: APInt.h:1946
NodeAddr(T A, NodeId I)
Definition: RDFGraph.h:337
NodeId getSibling() const
Definition: RDFGraph.h:536
static bool IsRef(const NodeAddr< NodeBase *> BA)
Definition: RDFGraph.h:787
NodeAddr< RefNode * > getNextRef(RegisterRef RR, Predicate P, bool NextOnly, const DataFlowGraph &G)
Definition: RDFGraph.h:888
std::unordered_map< RegisterId, DefStack > DefStackMap
Definition: RDFGraph.h:734
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
void setReachedUse(NodeId U)
Definition: RDFGraph.h:569
uint32_t getIndexForLaneMask(LaneBitmask LM)
Definition: RDFGraph.h:439
void setSibling(NodeId Sib)
Definition: RDFGraph.h:539