• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //===--- RDFGraph.h -------------------------------------------------------===//
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 //
179 //
180 // *** Shadow references
181 //
182 // It may happen that a super-register can have two (or more) non-overlapping
183 // sub-registers. When both of these sub-registers are defined and followed
184 // by a use of the super-register, the use of the super-register will not
185 // have a unique reaching def: both defs of the sub-registers need to be
186 // accounted for. In such cases, a duplicate use of the super-register is
187 // added and it points to the extra reaching def. Both uses are marked with
188 // a flag "shadow". Example:
189 // Assume t0 is a super-register of r0 and r1, r0 and r1 do not overlap:
190 //   set r0, 1        ; r0 = 1
191 //   set r1, 1        ; r1 = 1
192 //   addi t1, t0, 1   ; t1 = t0+1
193 //
194 // The DFG:
195 //   s1: set [d2<r0>(,,u9):]
196 //   s3: set [d4<r1>(,,u10):]
197 //   s5: addi [d6<t1>(,,):, u7"<t0>(d2):, u8"<t0>(d4):]
198 //
199 // The statement s5 has two use nodes for t0: u7" and u9". The quotation
200 // mark " indicates that the node is a shadow.
201 //
202 #ifndef RDF_GRAPH_H
203 #define RDF_GRAPH_H
204 
205 #include "llvm/Support/Allocator.h"
206 #include "llvm/Support/Debug.h"
207 #include "llvm/Support/raw_ostream.h"
208 #include "llvm/Support/Timer.h"
209 
210 #include <functional>
211 #include <map>
212 #include <set>
213 #include <vector>
214 
215 namespace llvm {
216   class MachineBasicBlock;
217   class MachineFunction;
218   class MachineInstr;
219   class MachineOperand;
220   class MachineDominanceFrontier;
221   class MachineDominatorTree;
222   class TargetInstrInfo;
223   class TargetRegisterInfo;
224 
225 namespace rdf {
226   typedef uint32_t NodeId;
227 
228   struct NodeAttrs {
229     enum : uint16_t {
230       None          = 0x0000,   // Nothing
231 
232       // Types: 2 bits
233       TypeMask      = 0x0003,
234       Code          = 0x0001,   // 01, Container
235       Ref           = 0x0002,   // 10, Reference
236 
237       // Kind: 3 bits
238       KindMask      = 0x0007 << 2,
239       Def           = 0x0001 << 2,  // 001
240       Use           = 0x0002 << 2,  // 010
241       Phi           = 0x0003 << 2,  // 011
242       Stmt          = 0x0004 << 2,  // 100
243       Block         = 0x0005 << 2,  // 101
244       Func          = 0x0006 << 2,  // 110
245 
246       // Flags: 5 bits for now
247       FlagMask      = 0x001F << 5,
248       Shadow        = 0x0001 << 5,  // 00001, Has extra reaching defs.
249       Clobbering    = 0x0002 << 5,  // 00010, Produces unspecified values.
250       PhiRef        = 0x0004 << 5,  // 00100, Member of PhiNode.
251       Preserving    = 0x0008 << 5,  // 01000, Def can keep original bits.
252       Fixed         = 0x0010 << 5,  // 10000, Fixed register.
253     };
254 
typeNodeAttrs255     static uint16_t type(uint16_t T)  { return T & TypeMask; }
kindNodeAttrs256     static uint16_t kind(uint16_t T)  { return T & KindMask; }
flagsNodeAttrs257     static uint16_t flags(uint16_t T) { return T & FlagMask; }
258 
set_typeNodeAttrs259     static uint16_t set_type(uint16_t A, uint16_t T) {
260       return (A & ~TypeMask) | T;
261     }
set_kindNodeAttrs262     static uint16_t set_kind(uint16_t A, uint16_t K) {
263       return (A & ~KindMask) | K;
264     }
set_flagsNodeAttrs265     static uint16_t set_flags(uint16_t A, uint16_t F) {
266       return (A & ~FlagMask) | F;
267     }
268 
269     // Test if A contains B.
containsNodeAttrs270     static bool contains(uint16_t A, uint16_t B) {
271       if (type(A) != Code)
272         return false;
273       uint16_t KB = kind(B);
274       switch (kind(A)) {
275         case Func:
276           return KB == Block;
277         case Block:
278           return KB == Phi || KB == Stmt;
279         case Phi:
280         case Stmt:
281           return type(B) == Ref;
282       }
283       return false;
284     }
285   };
286 
287   struct BuildOptions {
288     enum : unsigned {
289       None          = 0x00,
290       KeepDeadPhis  = 0x01,   // Do not remove dead phis during build.
291     };
292   };
293 
294   template <typename T> struct NodeAddr {
NodeAddrNodeAddr295     NodeAddr() : Addr(nullptr), Id(0) {}
NodeAddrNodeAddr296     NodeAddr(T A, NodeId I) : Addr(A), Id(I) {}
297     NodeAddr(const NodeAddr&) = default;
298     NodeAddr &operator= (const NodeAddr&) = default;
299 
300     bool operator== (const NodeAddr<T> &NA) const {
301       assert((Addr == NA.Addr) == (Id == NA.Id));
302       return Addr == NA.Addr;
303     }
304     bool operator!= (const NodeAddr<T> &NA) const {
305       return !operator==(NA);
306     }
307     // Type cast (casting constructor). The reason for having this class
308     // instead of std::pair.
NodeAddrNodeAddr309     template <typename S> NodeAddr(const NodeAddr<S> &NA)
310       : Addr(static_cast<T>(NA.Addr)), Id(NA.Id) {}
311 
312     T Addr;
313     NodeId Id;
314   };
315 
316   struct NodeBase;
317 
318   // Fast memory allocation and translation between node id and node address.
319   // This is really the same idea as the one underlying the "bump pointer
320   // allocator", the difference being in the translation. A node id is
321   // composed of two components: the index of the block in which it was
322   // allocated, and the index within the block. With the default settings,
323   // where the number of nodes per block is 4096, the node id (minus 1) is:
324   //
325   // bit position:                11             0
326   // +----------------------------+--------------+
327   // | Index of the block         |Index in block|
328   // +----------------------------+--------------+
329   //
330   // The actual node id is the above plus 1, to avoid creating a node id of 0.
331   //
332   // This method significantly improved the build time, compared to using maps
333   // (std::unordered_map or DenseMap) to translate between pointers and ids.
334   struct NodeAllocator {
335     // Amount of storage for a single node.
336     enum { NodeMemSize = 32 };
337     NodeAllocator(uint32_t NPB = 4096)
NodesPerBlockNodeAllocator338         : NodesPerBlock(NPB), BitsPerIndex(Log2_32(NPB)),
339           IndexMask((1 << BitsPerIndex)-1), ActiveEnd(nullptr) {
340       assert(isPowerOf2_32(NPB));
341     }
ptrNodeAllocator342     NodeBase *ptr(NodeId N) const {
343       uint32_t N1 = N-1;
344       uint32_t BlockN = N1 >> BitsPerIndex;
345       uint32_t Offset = (N1 & IndexMask) * NodeMemSize;
346       return reinterpret_cast<NodeBase*>(Blocks[BlockN]+Offset);
347     }
348     NodeId id(const NodeBase *P) const;
349     NodeAddr<NodeBase*> New();
350     void clear();
351 
352   private:
353     void startNewBlock();
354     bool needNewBlock();
makeIdNodeAllocator355     uint32_t makeId(uint32_t Block, uint32_t Index) const {
356       // Add 1 to the id, to avoid the id of 0, which is treated as "null".
357       return ((Block << BitsPerIndex) | Index) + 1;
358     }
359 
360     const uint32_t NodesPerBlock;
361     const uint32_t BitsPerIndex;
362     const uint32_t IndexMask;
363     char *ActiveEnd;
364     std::vector<char*> Blocks;
365     typedef BumpPtrAllocatorImpl<MallocAllocator, 65536> AllocatorTy;
366     AllocatorTy MemPool;
367   };
368 
369   struct RegisterRef {
370     unsigned Reg, Sub;
371 
372     // No non-trivial constructors, since this will be a member of a union.
373     RegisterRef() = default;
374     RegisterRef(const RegisterRef &RR) = default;
375     RegisterRef &operator= (const RegisterRef &RR) = default;
376     bool operator== (const RegisterRef &RR) const {
377       return Reg == RR.Reg && Sub == RR.Sub;
378     }
379     bool operator!= (const RegisterRef &RR) const {
380       return !operator==(RR);
381     }
382     bool operator< (const RegisterRef &RR) const {
383       return Reg < RR.Reg || (Reg == RR.Reg && Sub < RR.Sub);
384     }
385   };
386   typedef std::set<RegisterRef> RegisterSet;
387 
388   struct RegisterAliasInfo {
RegisterAliasInfoRegisterAliasInfo389     RegisterAliasInfo(const TargetRegisterInfo &tri) : TRI(tri) {}
~RegisterAliasInfoRegisterAliasInfo390     virtual ~RegisterAliasInfo() {}
391 
392     virtual std::vector<RegisterRef> getAliasSet(RegisterRef RR) const;
393     virtual bool alias(RegisterRef RA, RegisterRef RB) const;
394     virtual bool covers(RegisterRef RA, RegisterRef RB) const;
395     virtual bool covers(const RegisterSet &RRs, RegisterRef RR) const;
396 
397     const TargetRegisterInfo &TRI;
398   };
399 
400   struct TargetOperandInfo {
TargetOperandInfoTargetOperandInfo401     TargetOperandInfo(const TargetInstrInfo &tii) : TII(tii) {}
~TargetOperandInfoTargetOperandInfo402     virtual ~TargetOperandInfo() {}
403     virtual bool isPreserving(const MachineInstr &In, unsigned OpNum) const;
404     virtual bool isClobbering(const MachineInstr &In, unsigned OpNum) const;
405     virtual bool isFixedReg(const MachineInstr &In, unsigned OpNum) const;
406 
407     const TargetInstrInfo &TII;
408   };
409 
410 
411   struct DataFlowGraph;
412 
413   struct NodeBase {
414   public:
415     // Make sure this is a POD.
416     NodeBase() = default;
getTypeNodeBase417     uint16_t getType()  const { return NodeAttrs::type(Attrs); }
getKindNodeBase418     uint16_t getKind()  const { return NodeAttrs::kind(Attrs); }
getFlagsNodeBase419     uint16_t getFlags() const { return NodeAttrs::flags(Attrs); }
getNextNodeBase420     NodeId   getNext()  const { return Next; }
421 
getAttrsNodeBase422     uint16_t getAttrs() const { return Attrs; }
setAttrsNodeBase423     void setAttrs(uint16_t A) { Attrs = A; }
setFlagsNodeBase424     void setFlags(uint16_t F) { setAttrs(NodeAttrs::set_flags(getAttrs(), F)); }
425 
426     // Insert node NA after "this" in the circular chain.
427     void append(NodeAddr<NodeBase*> NA);
428     // Initialize all members to 0.
initNodeBase429     void init() { memset(this, 0, sizeof *this); }
setNextNodeBase430     void setNext(NodeId N) { Next = N; }
431 
432   protected:
433     uint16_t Attrs;
434     uint16_t Reserved;
435     NodeId Next;                // Id of the next node in the circular chain.
436     // Definitions of nested types. Using anonymous nested structs would make
437     // this class definition clearer, but unnamed structs are not a part of
438     // the standard.
439     struct Def_struct  {
440       NodeId DD, DU;          // Ids of the first reached def and use.
441     };
442     struct PhiU_struct  {
443       NodeId PredB;           // Id of the predecessor block for a phi use.
444     };
445     struct Code_struct {
446       void *CP;               // Pointer to the actual code.
447       NodeId FirstM, LastM;   // Id of the first member and last.
448     };
449     struct Ref_struct {
450       NodeId RD, Sib;         // Ids of the reaching def and the sibling.
451       union {
452         Def_struct Def;
453         PhiU_struct PhiU;
454       };
455       union {
456         MachineOperand *Op;   // Non-phi refs point to a machine operand.
457         RegisterRef RR;       // Phi refs store register info directly.
458       };
459     };
460 
461     // The actual payload.
462     union {
463       Ref_struct Ref;
464       Code_struct Code;
465     };
466   };
467   // The allocator allocates chunks of 32 bytes for each node. The fact that
468   // each node takes 32 bytes in memory is used for fast translation between
469   // the node id and the node address.
470   static_assert(sizeof(NodeBase) <= NodeAllocator::NodeMemSize,
471         "NodeBase must be at most NodeAllocator::NodeMemSize bytes");
472 
473   typedef std::vector<NodeAddr<NodeBase*>> NodeList;
474   typedef std::set<NodeId> NodeSet;
475 
476   struct RefNode : public NodeBase {
477     RefNode() = default;
478     RegisterRef getRegRef() const;
getOpRefNode479     MachineOperand &getOp() {
480       assert(!(getFlags() & NodeAttrs::PhiRef));
481       return *Ref.Op;
482     }
483     void setRegRef(RegisterRef RR);
484     void setRegRef(MachineOperand *Op);
getReachingDefRefNode485     NodeId getReachingDef() const {
486       return Ref.RD;
487     }
setReachingDefRefNode488     void setReachingDef(NodeId RD) {
489       Ref.RD = RD;
490     }
getSiblingRefNode491     NodeId getSibling() const {
492       return Ref.Sib;
493     }
setSiblingRefNode494     void setSibling(NodeId Sib) {
495       Ref.Sib = Sib;
496     }
isUseRefNode497     bool isUse() const {
498       assert(getType() == NodeAttrs::Ref);
499       return getKind() == NodeAttrs::Use;
500     }
isDefRefNode501     bool isDef() const {
502       assert(getType() == NodeAttrs::Ref);
503       return getKind() == NodeAttrs::Def;
504     }
505 
506     template <typename Predicate>
507     NodeAddr<RefNode*> getNextRef(RegisterRef RR, Predicate P, bool NextOnly,
508         const DataFlowGraph &G);
509     NodeAddr<NodeBase*> getOwner(const DataFlowGraph &G);
510   };
511 
512   struct DefNode : public RefNode {
getReachedDefDefNode513     NodeId getReachedDef() const {
514       return Ref.Def.DD;
515     }
setReachedDefDefNode516     void setReachedDef(NodeId D) {
517       Ref.Def.DD = D;
518     }
getReachedUseDefNode519     NodeId getReachedUse() const {
520       return Ref.Def.DU;
521     }
setReachedUseDefNode522     void setReachedUse(NodeId U) {
523       Ref.Def.DU = U;
524     }
525 
526     void linkToDef(NodeId Self, NodeAddr<DefNode*> DA);
527   };
528 
529   struct UseNode : public RefNode {
530     void linkToDef(NodeId Self, NodeAddr<DefNode*> DA);
531   };
532 
533   struct PhiUseNode : public UseNode {
getPredecessorPhiUseNode534     NodeId getPredecessor() const {
535       assert(getFlags() & NodeAttrs::PhiRef);
536       return Ref.PhiU.PredB;
537     }
setPredecessorPhiUseNode538     void setPredecessor(NodeId B) {
539       assert(getFlags() & NodeAttrs::PhiRef);
540       Ref.PhiU.PredB = B;
541     }
542   };
543 
544   struct CodeNode : public NodeBase {
getCodeCodeNode545     template <typename T> T getCode() const {
546       return static_cast<T>(Code.CP);
547     }
setCodeCodeNode548     void setCode(void *C) {
549       Code.CP = C;
550     }
551 
552     NodeAddr<NodeBase*> getFirstMember(const DataFlowGraph &G) const;
553     NodeAddr<NodeBase*> getLastMember(const DataFlowGraph &G) const;
554     void addMember(NodeAddr<NodeBase*> NA, const DataFlowGraph &G);
555     void addMemberAfter(NodeAddr<NodeBase*> MA, NodeAddr<NodeBase*> NA,
556         const DataFlowGraph &G);
557     void removeMember(NodeAddr<NodeBase*> NA, const DataFlowGraph &G);
558 
559     NodeList members(const DataFlowGraph &G) const;
560     template <typename Predicate>
561     NodeList members_if(Predicate P, const DataFlowGraph &G) const;
562   };
563 
564   struct InstrNode : public CodeNode {
565     NodeAddr<NodeBase*> getOwner(const DataFlowGraph &G);
566   };
567 
568   struct PhiNode : public InstrNode {
getCodePhiNode569     MachineInstr *getCode() const {
570       return nullptr;
571     }
572   };
573 
574   struct StmtNode : public InstrNode {
getCodeStmtNode575     MachineInstr *getCode() const {
576       return CodeNode::getCode<MachineInstr*>();
577     }
578   };
579 
580   struct BlockNode : public CodeNode {
getCodeBlockNode581     MachineBasicBlock *getCode() const {
582       return CodeNode::getCode<MachineBasicBlock*>();
583     }
584     void addPhi(NodeAddr<PhiNode*> PA, const DataFlowGraph &G);
585   };
586 
587   struct FuncNode : public CodeNode {
getCodeFuncNode588     MachineFunction *getCode() const {
589       return CodeNode::getCode<MachineFunction*>();
590     }
591     NodeAddr<BlockNode*> findBlock(const MachineBasicBlock *BB,
592         const DataFlowGraph &G) const;
593     NodeAddr<BlockNode*> getEntryBlock(const DataFlowGraph &G);
594   };
595 
596   struct DataFlowGraph {
597     DataFlowGraph(MachineFunction &mf, const TargetInstrInfo &tii,
598         const TargetRegisterInfo &tri, const MachineDominatorTree &mdt,
599         const MachineDominanceFrontier &mdf, const RegisterAliasInfo &rai,
600         const TargetOperandInfo &toi);
601 
602     NodeBase *ptr(NodeId N) const;
ptrDataFlowGraph603     template <typename T> T ptr(NodeId N) const {
604       return static_cast<T>(ptr(N));
605     }
606     NodeId id(const NodeBase *P) const;
607 
addrDataFlowGraph608     template <typename T> NodeAddr<T> addr(NodeId N) const {
609       return { ptr<T>(N), N };
610     }
611 
getFuncDataFlowGraph612     NodeAddr<FuncNode*> getFunc() const {
613       return Func;
614     }
getMFDataFlowGraph615     MachineFunction &getMF() const {
616       return MF;
617     }
getTIIDataFlowGraph618     const TargetInstrInfo &getTII() const {
619       return TII;
620     }
getTRIDataFlowGraph621     const TargetRegisterInfo &getTRI() const {
622       return TRI;
623     }
getDTDataFlowGraph624     const MachineDominatorTree &getDT() const {
625       return MDT;
626     }
getDFDataFlowGraph627     const MachineDominanceFrontier &getDF() const {
628       return MDF;
629     }
getRAIDataFlowGraph630     const RegisterAliasInfo &getRAI() const {
631       return RAI;
632     }
633 
634     struct DefStack {
635       DefStack() = default;
emptyDataFlowGraph::DefStack636       bool empty() const { return Stack.empty() || top() == bottom(); }
637     private:
638       typedef NodeAddr<DefNode*> value_type;
639       struct Iterator {
640         typedef DefStack::value_type value_type;
upDataFlowGraph::DefStack::Iterator641         Iterator &up() { Pos = DS.nextUp(Pos); return *this; }
downDataFlowGraph::DefStack::Iterator642         Iterator &down() { Pos = DS.nextDown(Pos); return *this; }
643         value_type operator*() const {
644           assert(Pos >= 1);
645           return DS.Stack[Pos-1];
646         }
647         const value_type *operator->() const {
648           assert(Pos >= 1);
649           return &DS.Stack[Pos-1];
650         }
651         bool operator==(const Iterator &It) const { return Pos == It.Pos; }
652         bool operator!=(const Iterator &It) const { return Pos != It.Pos; }
653       private:
654         Iterator(const DefStack &S, bool Top);
655         // Pos-1 is the index in the StorageType object that corresponds to
656         // the top of the DefStack.
657         const DefStack &DS;
658         unsigned Pos;
659         friend struct DefStack;
660       };
661     public:
662       typedef Iterator iterator;
topDataFlowGraph::DefStack663       iterator top() const { return Iterator(*this, true); }
bottomDataFlowGraph::DefStack664       iterator bottom() const { return Iterator(*this, false); }
665       unsigned size() const;
666 
pushDataFlowGraph::DefStack667       void push(NodeAddr<DefNode*> DA) { Stack.push_back(DA); }
668       void pop();
669       void start_block(NodeId N);
670       void clear_block(NodeId N);
671     private:
672       friend struct Iterator;
673       typedef std::vector<value_type> StorageType;
674       bool isDelimiter(const StorageType::value_type &P, NodeId N = 0) const {
675         return (P.Addr == nullptr) && (N == 0 || P.Id == N);
676       }
677       unsigned nextUp(unsigned P) const;
678       unsigned nextDown(unsigned P) const;
679       StorageType Stack;
680     };
681 
682     typedef std::map<RegisterRef,DefStack> DefStackMap;
683 
684     void build(unsigned Options = BuildOptions::None);
685     void pushDefs(NodeAddr<InstrNode*> IA, DefStackMap &DM);
686     void markBlock(NodeId B, DefStackMap &DefM);
687     void releaseBlock(NodeId B, DefStackMap &DefM);
688 
689     NodeAddr<RefNode*> getNextRelated(NodeAddr<InstrNode*> IA,
690         NodeAddr<RefNode*> RA) const;
691     NodeAddr<RefNode*> getNextImp(NodeAddr<InstrNode*> IA,
692         NodeAddr<RefNode*> RA, bool Create);
693     NodeAddr<RefNode*> getNextImp(NodeAddr<InstrNode*> IA,
694         NodeAddr<RefNode*> RA) const;
695     NodeAddr<RefNode*> getNextShadow(NodeAddr<InstrNode*> IA,
696         NodeAddr<RefNode*> RA, bool Create);
697     NodeAddr<RefNode*> getNextShadow(NodeAddr<InstrNode*> IA,
698         NodeAddr<RefNode*> RA) const;
699 
700     NodeList getRelatedRefs(NodeAddr<InstrNode*> IA,
701         NodeAddr<RefNode*> RA) const;
702 
unlinkUseDataFlowGraph703     void unlinkUse(NodeAddr<UseNode*> UA, bool RemoveFromOwner) {
704       unlinkUseDF(UA);
705       if (RemoveFromOwner)
706         removeFromOwner(UA);
707     }
unlinkDefDataFlowGraph708     void unlinkDef(NodeAddr<DefNode*> DA, bool RemoveFromOwner) {
709       unlinkDefDF(DA);
710       if (RemoveFromOwner)
711         removeFromOwner(DA);
712     }
713 
714     // Some useful filters.
715     template <uint16_t Kind>
IsRefDataFlowGraph716     static bool IsRef(const NodeAddr<NodeBase*> BA) {
717       return BA.Addr->getType() == NodeAttrs::Ref &&
718              BA.Addr->getKind() == Kind;
719     }
720     template <uint16_t Kind>
IsCodeDataFlowGraph721     static bool IsCode(const NodeAddr<NodeBase*> BA) {
722       return BA.Addr->getType() == NodeAttrs::Code &&
723              BA.Addr->getKind() == Kind;
724     }
IsDefDataFlowGraph725     static bool IsDef(const NodeAddr<NodeBase*> BA) {
726       return BA.Addr->getType() == NodeAttrs::Ref &&
727              BA.Addr->getKind() == NodeAttrs::Def;
728     }
IsUseDataFlowGraph729     static bool IsUse(const NodeAddr<NodeBase*> BA) {
730       return BA.Addr->getType() == NodeAttrs::Ref &&
731              BA.Addr->getKind() == NodeAttrs::Use;
732     }
IsPhiDataFlowGraph733     static bool IsPhi(const NodeAddr<NodeBase*> BA) {
734       return BA.Addr->getType() == NodeAttrs::Code &&
735              BA.Addr->getKind() == NodeAttrs::Phi;
736     }
737 
738   private:
739     void reset();
740 
741     NodeAddr<NodeBase*> newNode(uint16_t Attrs);
742     NodeAddr<NodeBase*> cloneNode(const NodeAddr<NodeBase*> B);
743     NodeAddr<UseNode*> newUse(NodeAddr<InstrNode*> Owner,
744         MachineOperand &Op, uint16_t Flags = NodeAttrs::None);
745     NodeAddr<PhiUseNode*> newPhiUse(NodeAddr<PhiNode*> Owner,
746         RegisterRef RR, NodeAddr<BlockNode*> PredB,
747         uint16_t Flags = NodeAttrs::PhiRef);
748     NodeAddr<DefNode*> newDef(NodeAddr<InstrNode*> Owner,
749         MachineOperand &Op, uint16_t Flags = NodeAttrs::None);
750     NodeAddr<DefNode*> newDef(NodeAddr<InstrNode*> Owner,
751         RegisterRef RR, uint16_t Flags = NodeAttrs::PhiRef);
752     NodeAddr<PhiNode*> newPhi(NodeAddr<BlockNode*> Owner);
753     NodeAddr<StmtNode*> newStmt(NodeAddr<BlockNode*> Owner,
754         MachineInstr *MI);
755     NodeAddr<BlockNode*> newBlock(NodeAddr<FuncNode*> Owner,
756         MachineBasicBlock *BB);
757     NodeAddr<FuncNode*> newFunc(MachineFunction *MF);
758 
759     template <typename Predicate>
760     std::pair<NodeAddr<RefNode*>,NodeAddr<RefNode*>>
761     locateNextRef(NodeAddr<InstrNode*> IA, NodeAddr<RefNode*> RA,
762         Predicate P) const;
763 
764     typedef std::map<NodeId,RegisterSet> BlockRefsMap;
765 
766     void buildStmt(NodeAddr<BlockNode*> BA, MachineInstr &In);
767     void buildBlockRefs(NodeAddr<BlockNode*> BA, BlockRefsMap &RefM);
768     void recordDefsForDF(BlockRefsMap &PhiM, BlockRefsMap &RefM,
769         NodeAddr<BlockNode*> BA);
770     void buildPhis(BlockRefsMap &PhiM, BlockRefsMap &RefM,
771         NodeAddr<BlockNode*> BA);
772     void removeUnusedPhis();
773 
774     template <typename T> void linkRefUp(NodeAddr<InstrNode*> IA,
775         NodeAddr<T> TA, DefStack &DS);
776     void linkStmtRefs(DefStackMap &DefM, NodeAddr<StmtNode*> SA);
777     void linkBlockRefs(DefStackMap &DefM, NodeAddr<BlockNode*> BA);
778 
779     void unlinkUseDF(NodeAddr<UseNode*> UA);
780     void unlinkDefDF(NodeAddr<DefNode*> DA);
removeFromOwnerDataFlowGraph781     void removeFromOwner(NodeAddr<RefNode*> RA) {
782       NodeAddr<InstrNode*> IA = RA.Addr->getOwner(*this);
783       IA.Addr->removeMember(RA, *this);
784     }
785 
786     TimerGroup TimeG;
787     NodeAddr<FuncNode*> Func;
788     NodeAllocator Memory;
789 
790     MachineFunction &MF;
791     const TargetInstrInfo &TII;
792     const TargetRegisterInfo &TRI;
793     const MachineDominatorTree &MDT;
794     const MachineDominanceFrontier &MDF;
795     const RegisterAliasInfo &RAI;
796     const TargetOperandInfo &TOI;
797   };  // struct DataFlowGraph
798 
799   template <typename Predicate>
getNextRef(RegisterRef RR,Predicate P,bool NextOnly,const DataFlowGraph & G)800   NodeAddr<RefNode*> RefNode::getNextRef(RegisterRef RR, Predicate P,
801         bool NextOnly, const DataFlowGraph &G) {
802     // Get the "Next" reference in the circular list that references RR and
803     // satisfies predicate "Pred".
804     auto NA = G.addr<NodeBase*>(getNext());
805 
806     while (NA.Addr != this) {
807       if (NA.Addr->getType() == NodeAttrs::Ref) {
808         NodeAddr<RefNode*> RA = NA;
809         if (RA.Addr->getRegRef() == RR && P(NA))
810           return NA;
811         if (NextOnly)
812           break;
813         NA = G.addr<NodeBase*>(NA.Addr->getNext());
814       } else {
815         // We've hit the beginning of the chain.
816         assert(NA.Addr->getType() == NodeAttrs::Code);
817         NodeAddr<CodeNode*> CA = NA;
818         NA = CA.Addr->getFirstMember(G);
819       }
820     }
821     // Return the equivalent of "nullptr" if such a node was not found.
822     return NodeAddr<RefNode*>();
823   }
824 
825   template <typename Predicate>
members_if(Predicate P,const DataFlowGraph & G)826   NodeList CodeNode::members_if(Predicate P, const DataFlowGraph &G) const {
827     NodeList MM;
828     auto M = getFirstMember(G);
829     if (M.Id == 0)
830       return MM;
831 
832     while (M.Addr != this) {
833       if (P(M))
834         MM.push_back(M);
835       M = G.addr<NodeBase*>(M.Addr->getNext());
836     }
837     return MM;
838   }
839 
840 
841   template <typename T> struct Print;
842   template <typename T>
843   raw_ostream &operator<< (raw_ostream &OS, const Print<T> &P);
844 
845   template <typename T>
846   struct Print {
PrintPrint847     Print(const T &x, const DataFlowGraph &g) : Obj(x), G(g) {}
848     const T &Obj;
849     const DataFlowGraph &G;
850   };
851 
852   template <typename T>
853   struct PrintNode : Print<NodeAddr<T>> {
PrintNodePrintNode854     PrintNode(const NodeAddr<T> &x, const DataFlowGraph &g)
855       : Print<NodeAddr<T>>(x, g) {}
856   };
857 } // namespace rdf
858 } // namespace llvm
859 
860 #endif // RDF_GRAPH_H
861