Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/Target/Hexagon/RDFGraph.h
Line
Count
Source (jump to first uncovered line)
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
1.03M
    static uint16_t type(uint16_t T)  { return T & TypeMask; }
295
1.38M
    static uint16_t kind(uint16_t T)  { return T & KindMask; }
296
1.16M
    static uint16_t flags(uint16_t T) { return T & FlagMask; }
297
298
0
    static uint16_t set_type(uint16_t A, uint16_t T) {
299
0
      return (A & ~TypeMask) | T;
300
0
    }
301
302
0
    static uint16_t set_kind(uint16_t A, uint16_t K) {
303
0
      return (A & ~KindMask) | K;
304
0
    }
305
306
7.63k
    static uint16_t set_flags(uint16_t A, uint16_t F) {
307
7.63k
      return (A & ~FlagMask) | F;
308
7.63k
    }
309
310
    // Test if A contains B.
311
0
    static bool contains(uint16_t A, uint16_t B) {
312
0
      if (type(A) != Code)
313
0
        return false;
314
0
      uint16_t KB = kind(B);
315
0
      switch (kind(A)) {
316
0
        case Func:
317
0
          return KB == Block;
318
0
        case Block:
319
0
          return KB == Phi || KB == Stmt;
320
0
        case Phi:
321
0
        case Stmt:
322
0
          return type(B) == Ref;
323
0
      }
324
0
      return false;
325
0
    }
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
188k
    NodeAddr() = default;
llvm::rdf::NodeAddr<llvm::rdf::UseNode*>::NodeAddr()
Line
Count
Source
336
35.1k
    NodeAddr() = default;
llvm::rdf::NodeAddr<llvm::rdf::RefNode*>::NodeAddr()
Line
Count
Source
336
92.8k
    NodeAddr() = default;
llvm::rdf::NodeAddr<llvm::rdf::DefNode*>::NodeAddr()
Line
Count
Source
336
16.9k
    NodeAddr() = default;
llvm::rdf::NodeAddr<llvm::rdf::FuncNode*>::NodeAddr()
Line
Count
Source
336
3.44k
    NodeAddr() = default;
llvm::rdf::NodeAddr<llvm::rdf::BlockNode*>::NodeAddr()
Line
Count
Source
336
48
    NodeAddr() = default;
llvm::rdf::NodeAddr<llvm::rdf::NodeBase*>::NodeAddr()
Line
Count
Source
336
40.2k
    NodeAddr() = default;
337
2.37M
    NodeAddr(T A, NodeId I) : Addr(A), Id(I) {}
llvm::rdf::NodeAddr<llvm::rdf::NodeBase*>::NodeAddr(llvm::rdf::NodeBase*, unsigned int)
Line
Count
Source
337
2.00M
    NodeAddr(T A, NodeId I) : Addr(A), Id(I) {}
llvm::rdf::NodeAddr<llvm::rdf::UseNode*>::NodeAddr(llvm::rdf::UseNode*, unsigned int)
Line
Count
Source
337
31.4k
    NodeAddr(T A, NodeId I) : Addr(A), Id(I) {}
llvm::rdf::NodeAddr<llvm::rdf::BlockNode*>::NodeAddr(llvm::rdf::BlockNode*, unsigned int)
Line
Count
Source
337
1.66k
    NodeAddr(T A, NodeId I) : Addr(A), Id(I) {}
llvm::rdf::NodeAddr<llvm::rdf::DefNode const*>::NodeAddr(llvm::rdf::DefNode const*, unsigned int)
Line
Count
Source
337
23
    NodeAddr(T A, NodeId I) : Addr(A), Id(I) {}
llvm::rdf::NodeAddr<llvm::rdf::PhiNode*>::NodeAddr(llvm::rdf::PhiNode*, unsigned int)
Line
Count
Source
337
3.58k
    NodeAddr(T A, NodeId I) : Addr(A), Id(I) {}
llvm::rdf::NodeAddr<llvm::rdf::RefNode*>::NodeAddr(llvm::rdf::RefNode*, unsigned int)
Line
Count
Source
337
75.3k
    NodeAddr(T A, NodeId I) : Addr(A), Id(I) {}
llvm::rdf::NodeAddr<llvm::rdf::InstrNode*>::NodeAddr(llvm::rdf::InstrNode*, unsigned int)
Line
Count
Source
337
59.8k
    NodeAddr(T A, NodeId I) : Addr(A), Id(I) {}
llvm::rdf::NodeAddr<llvm::rdf::StmtNode*>::NodeAddr(llvm::rdf::StmtNode*, unsigned int)
Line
Count
Source
337
2
    NodeAddr(T A, NodeId I) : Addr(A), Id(I) {}
llvm::rdf::NodeAddr<llvm::rdf::DefNode*>::NodeAddr(llvm::rdf::DefNode*, unsigned int)
Line
Count
Source
337
203k
    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
2.52M
      : Addr(static_cast<T>(NA.Addr)), Id(NA.Id) {}
llvm::rdf::NodeAddr<llvm::rdf::InstrNode*>::NodeAddr<llvm::rdf::StmtNode*>(llvm::rdf::NodeAddr<llvm::rdf::StmtNode*> const&)
Line
Count
Source
342
92.6k
      : Addr(static_cast<T>(NA.Addr)), Id(NA.Id) {}
llvm::rdf::NodeAddr<llvm::rdf::DefNode*>::NodeAddr<llvm::rdf::RefNode*>(llvm::rdf::NodeAddr<llvm::rdf::RefNode*> const&)
Line
Count
Source
342
35.2k
      : Addr(static_cast<T>(NA.Addr)), Id(NA.Id) {}
llvm::rdf::NodeAddr<llvm::rdf::UseNode*>::NodeAddr<llvm::rdf::RefNode*>(llvm::rdf::NodeAddr<llvm::rdf::RefNode*> const&)
Line
Count
Source
342
47.6k
      : Addr(static_cast<T>(NA.Addr)), Id(NA.Id) {}
llvm::rdf::NodeAddr<llvm::rdf::CodeNode*>::NodeAddr<llvm::rdf::NodeBase*>(llvm::rdf::NodeAddr<llvm::rdf::NodeBase*> const&)
Line
Count
Source
342
27.1k
      : Addr(static_cast<T>(NA.Addr)), Id(NA.Id) {}
llvm::rdf::NodeAddr<llvm::rdf::RefNode*>::NodeAddr<llvm::rdf::PhiUseNode*>(llvm::rdf::NodeAddr<llvm::rdf::PhiUseNode*> const&)
Line
Count
Source
342
17.6k
      : Addr(static_cast<T>(NA.Addr)), Id(NA.Id) {}
Unexecuted instantiation: llvm::rdf::NodeAddr<llvm::rdf::PhiUseNode*>::NodeAddr<llvm::rdf::RefNode*>(llvm::rdf::NodeAddr<llvm::rdf::RefNode*> const&)
llvm::rdf::NodeAddr<llvm::rdf::PhiNode*>::NodeAddr<llvm::rdf::InstrNode*>(llvm::rdf::NodeAddr<llvm::rdf::InstrNode*> const&)
Line
Count
Source
342
2.66k
      : Addr(static_cast<T>(NA.Addr)), Id(NA.Id) {}
llvm::rdf::NodeAddr<llvm::rdf::NodeBase*>::NodeAddr<llvm::rdf::UseNode*>(llvm::rdf::NodeAddr<llvm::rdf::UseNode*> const&)
Line
Count
Source
342
28.9k
      : Addr(static_cast<T>(NA.Addr)), Id(NA.Id) {}
llvm::rdf::NodeAddr<llvm::rdf::PhiUseNode*>::NodeAddr<llvm::rdf::NodeBase*>(llvm::rdf::NodeAddr<llvm::rdf::NodeBase*> const&)
Line
Count
Source
342
68.4k
      : Addr(static_cast<T>(NA.Addr)), Id(NA.Id) {}
llvm::rdf::NodeAddr<llvm::rdf::NodeBase*>::NodeAddr<llvm::rdf::StmtNode*>(llvm::rdf::NodeAddr<llvm::rdf::StmtNode*> const&)
Line
Count
Source
342
23.4k
      : Addr(static_cast<T>(NA.Addr)), Id(NA.Id) {}
llvm::rdf::NodeAddr<llvm::rdf::NodeBase*>::NodeAddr<llvm::rdf::BlockNode*>(llvm::rdf::NodeAddr<llvm::rdf::BlockNode*> const&)
Line
Count
Source
342
6.15k
      : Addr(static_cast<T>(NA.Addr)), Id(NA.Id) {}
llvm::rdf::NodeAddr<llvm::rdf::FuncNode*>::NodeAddr<llvm::rdf::NodeBase*>(llvm::rdf::NodeAddr<llvm::rdf::NodeBase*> const&)
Line
Count
Source
342
1.72k
      : Addr(static_cast<T>(NA.Addr)), Id(NA.Id) {}
llvm::rdf::NodeAddr<llvm::rdf::InstrNode*>::NodeAddr<llvm::rdf::PhiNode*>(llvm::rdf::NodeAddr<llvm::rdf::PhiNode*> const&)
Line
Count
Source
342
16.5k
      : Addr(static_cast<T>(NA.Addr)), Id(NA.Id) {}
llvm::rdf::NodeAddr<llvm::rdf::NodeBase*>::NodeAddr<llvm::rdf::DefNode*>(llvm::rdf::NodeAddr<llvm::rdf::DefNode*> const&)
Line
Count
Source
342
75.6k
      : Addr(static_cast<T>(NA.Addr)), Id(NA.Id) {}
llvm::rdf::NodeAddr<llvm::rdf::NodeBase*>::NodeAddr<llvm::rdf::PhiUseNode*>(llvm::rdf::NodeAddr<llvm::rdf::PhiUseNode*> const&)
Line
Count
Source
342
11.4k
      : Addr(static_cast<T>(NA.Addr)), Id(NA.Id) {}
llvm::rdf::NodeAddr<llvm::rdf::PhiUseNode const*>::NodeAddr<llvm::rdf::RefNode*>(llvm::rdf::NodeAddr<llvm::rdf::RefNode*> const&)
Line
Count
Source
342
28.1k
      : Addr(static_cast<T>(NA.Addr)), Id(NA.Id) {}
llvm::rdf::NodeAddr<llvm::rdf::UseNode*>::NodeAddr<llvm::rdf::PhiUseNode*>(llvm::rdf::NodeAddr<llvm::rdf::PhiUseNode*> const&)
Line
Count
Source
342
11.4k
      : Addr(static_cast<T>(NA.Addr)), Id(NA.Id) {}
llvm::rdf::NodeAddr<llvm::rdf::RefNode*>::NodeAddr<llvm::rdf::DefNode*>(llvm::rdf::NodeAddr<llvm::rdf::DefNode*> const&)
Line
Count
Source
342
65.9k
      : Addr(static_cast<T>(NA.Addr)), Id(NA.Id) {}
llvm::rdf::NodeAddr<llvm::rdf::NodeBase*>::NodeAddr<llvm::rdf::InstrNode*>(llvm::rdf::NodeAddr<llvm::rdf::InstrNode*> const&)
Line
Count
Source
342
98.9k
      : Addr(static_cast<T>(NA.Addr)), Id(NA.Id) {}
llvm::rdf::NodeAddr<llvm::rdf::RefNode*>::NodeAddr<llvm::rdf::NodeBase*>(llvm::rdf::NodeAddr<llvm::rdf::NodeBase*> const&)
Line
Count
Source
342
680k
      : Addr(static_cast<T>(NA.Addr)), Id(NA.Id) {}
llvm::rdf::NodeAddr<llvm::rdf::UseNode*>::NodeAddr<llvm::rdf::NodeBase*>(llvm::rdf::NodeAddr<llvm::rdf::NodeBase*> const&)
Line
Count
Source
342
60.3k
      : Addr(static_cast<T>(NA.Addr)), Id(NA.Id) {}
llvm::rdf::NodeAddr<llvm::rdf::StmtNode*>::NodeAddr<llvm::rdf::InstrNode*>(llvm::rdf::NodeAddr<llvm::rdf::InstrNode*> const&)
Line
Count
Source
342
122k
      : Addr(static_cast<T>(NA.Addr)), Id(NA.Id) {}
llvm::rdf::NodeAddr<llvm::rdf::NodeBase*>::NodeAddr<llvm::rdf::RefNode*>(llvm::rdf::NodeAddr<llvm::rdf::RefNode*> const&)
Line
Count
Source
342
277k
      : Addr(static_cast<T>(NA.Addr)), Id(NA.Id) {}
llvm::rdf::NodeAddr<llvm::rdf::InstrNode*>::NodeAddr<llvm::rdf::NodeBase*>(llvm::rdf::NodeAddr<llvm::rdf::NodeBase*> const&)
Line
Count
Source
342
198k
      : Addr(static_cast<T>(NA.Addr)), Id(NA.Id) {}
llvm::rdf::NodeAddr<llvm::rdf::PhiNode*>::NodeAddr<llvm::rdf::NodeBase*>(llvm::rdf::NodeAddr<llvm::rdf::NodeBase*> const&)
Line
Count
Source
342
14.8k
      : Addr(static_cast<T>(NA.Addr)), Id(NA.Id) {}
llvm::rdf::NodeAddr<llvm::rdf::DefNode*>::NodeAddr<llvm::rdf::NodeBase*>(llvm::rdf::NodeAddr<llvm::rdf::NodeBase*> const&)
Line
Count
Source
342
347k
      : Addr(static_cast<T>(NA.Addr)), Id(NA.Id) {}
llvm::rdf::NodeAddr<llvm::rdf::StmtNode*>::NodeAddr<llvm::rdf::NodeBase*>(llvm::rdf::NodeAddr<llvm::rdf::NodeBase*> const&)
Line
Count
Source
342
42.1k
      : Addr(static_cast<T>(NA.Addr)), Id(NA.Id) {}
llvm::rdf::NodeAddr<llvm::rdf::BlockNode*>::NodeAddr<llvm::rdf::NodeBase*>(llvm::rdf::NodeAddr<llvm::rdf::NodeBase*> const&)
Line
Count
Source
342
73.2k
      : Addr(static_cast<T>(NA.Addr)), Id(NA.Id) {}
llvm::rdf::NodeAddr<llvm::rdf::RefNode*>::NodeAddr<llvm::rdf::UseNode*>(llvm::rdf::NodeAddr<llvm::rdf::UseNode*> const&)
Line
Count
Source
342
39.9k
      : Addr(static_cast<T>(NA.Addr)), Id(NA.Id) {}
llvm::rdf::NodeAddr<llvm::rdf::NodeBase*>::NodeAddr<llvm::rdf::PhiNode*>(llvm::rdf::NodeAddr<llvm::rdf::PhiNode*> const&)
Line
Count
Source
342
6.01k
      : 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
378
    NodeAllocator(uint32_t NPB = 4096)
379
        : NodesPerBlock(NPB), BitsPerIndex(Log2_32(NPB)),
380
1.71k
          IndexMask((1 << BitsPerIndex)-1) {
381
1.71k
      assert(isPowerOf2_32(NPB));
382
1.71k
    }
383
384
2.19M
    NodeBase *ptr(NodeId N) const {
385
2.19M
      uint32_t N1 = N-1;
386
2.19M
      uint32_t BlockN = N1 >> BitsPerIndex;
387
2.19M
      uint32_t Offset = (N1 & IndexMask) * NodeMemSize;
388
2.19M
      return reinterpret_cast<NodeBase*>(Blocks[BlockN]+Offset);
389
2.19M
    }
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
148k
    uint32_t makeId(uint32_t Block, uint32_t Index) const {
400
148k
      // Add 1 to the id, to avoid the id of 0, which is treated as "null".
401
148k
      return ((Block << BitsPerIndex) | Index) + 1;
402
148k
    }
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;
409
    using AllocatorTy = BumpPtrAllocatorImpl<MallocAllocator, 65536>;
410
    AllocatorTy MemPool;
411
  };
412
413
  using RegisterSet = std::set<RegisterRef>;
414
415
  struct TargetOperandInfo {
416
1.71k
    TargetOperandInfo(const TargetInstrInfo &tii) : TII(tii) {}
417
1.71k
    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
423
    const TargetInstrInfo &TII;
424
  };
425
426
  // Packed register reference. Only used for storage.
427
  struct PackedRegisterRef {
428
    RegisterId Reg;
429
    uint32_t MaskId;
430
  };
431
432
  struct LaneMaskIndex : private IndexedSet<LaneBitmask> {
433
1.71k
    LaneMaskIndex() = default;
434
435
171k
    LaneBitmask getLaneMaskForIndex(uint32_t K) const {
436
171k
      return K == 0 ? 
LaneBitmask::getAll()148k
:
get(K)22.6k
;
437
171k
    }
438
439
19.8k
    uint32_t getIndexForLaneMask(LaneBitmask LM) {
440
19.8k
      assert(LM.any());
441
19.8k
      return LM.all() ? 
016.9k
:
insert(LM)2.84k
;
442
19.8k
    }
443
444
0
    uint32_t getIndexForLaneMask(LaneBitmask LM) const {
445
0
      assert(LM.any());
446
0
      return LM.all() ? 0 : find(LM);
447
0
    }
448
  };
449
450
  struct NodeBase {
451
  public:
452
    // Make sure this is a POD.
453
    NodeBase() = default;
454
455
1.03M
    uint16_t getType()  const { return NodeAttrs::type(Attrs); }
456
1.38M
    uint16_t getKind()  const { return NodeAttrs::kind(Attrs); }
457
449k
    uint16_t getFlags() const { return NodeAttrs::flags(Attrs); }
458
1.45M
    NodeId   getNext()  const { return Next; }
459
460
7.63k
    uint16_t getAttrs() const { return Attrs; }
461
119k
    void setAttrs(uint16_t A) { Attrs = A; }
462
7.63k
    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
111k
    void init() { memset(this, 0, sizeof *this); }
469
470
44.3k
    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 {
492
        Def_struct Def;
493
        PhiU_struct PhiU;
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 {
503
      Ref_struct Ref;
504
      Code_struct Code;
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
513
  using NodeList = SmallVector<NodeAddr<NodeBase *>, 4>;
514
  using NodeSet = std::set<NodeId>;
515
516
  struct RefNode : public NodeBase {
517
    RefNode() = default;
518
519
    RegisterRef getRegRef(const DataFlowGraph &G) const;
520
521
13.5k
    MachineOperand &getOp() {
522
13.5k
      assert(!(getFlags() & NodeAttrs::PhiRef));
523
13.5k
      return *Ref.Op;
524
13.5k
    }
525
526
    void setRegRef(RegisterRef RR, DataFlowGraph &G);
527
    void setRegRef(MachineOperand *Op, DataFlowGraph &G);
528
529
80.0k
    NodeId getReachingDef() const {
530
80.0k
      return Ref.RD;
531
80.0k
    }
532
4.67k
    void setReachingDef(NodeId RD) {
533
4.67k
      Ref.RD = RD;
534
4.67k
    }
535
536
33.3k
    NodeId getSibling() const {
537
33.3k
      return Ref.Sib;
538
33.3k
    }
539
5.35k
    void setSibling(NodeId Sib) {
540
5.35k
      Ref.Sib = Sib;
541
5.35k
    }
542
543
0
    bool isUse() const {
544
0
      assert(getType() == NodeAttrs::Ref);
545
0
      return getKind() == NodeAttrs::Use;
546
0
    }
547
548
12
    bool isDef() const {
549
12
      assert(getType() == NodeAttrs::Ref);
550
12
      return getKind() == NodeAttrs::Def;
551
12
    }
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 {
560
34.6k
    NodeId getReachedDef() const {
561
34.6k
      return Ref.Def.DD;
562
34.6k
    }
563
21.0k
    void setReachedDef(NodeId D) {
564
21.0k
      Ref.Def.DD = D;
565
21.0k
    }
566
55.0k
    NodeId getReachedUse() const {
567
55.0k
      return Ref.Def.DU;
568
55.0k
    }
569
41.7k
    void setReachedUse(NodeId U) {
570
41.7k
      Ref.Def.DU = U;
571
41.7k
    }
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 {
581
56.2k
    NodeId getPredecessor() const {
582
56.2k
      assert(getFlags() & NodeAttrs::PhiRef);
583
56.2k
      return Ref.PhiU.PredB;
584
56.2k
    }
585
11.4k
    void setPredecessor(NodeId B) {
586
11.4k
      assert(getFlags() & NodeAttrs::PhiRef);
587
11.4k
      Ref.PhiU.PredB = B;
588
11.4k
    }
589
  };
590
591
  struct CodeNode : public NodeBase {
592
118k
    template <typename T> T getCode() const {
593
118k
      return static_cast<T>(Code.CP);
594
118k
    }
llvm::MachineBasicBlock* llvm::rdf::CodeNode::getCode<llvm::MachineBasicBlock*>() const
Line
Count
Source
592
52.9k
    template <typename T> T getCode() const {
593
52.9k
      return static_cast<T>(Code.CP);
594
52.9k
    }
llvm::MachineInstr* llvm::rdf::CodeNode::getCode<llvm::MachineInstr*>() const
Line
Count
Source
592
64.2k
    template <typename T> T getCode() const {
593
64.2k
      return static_cast<T>(Code.CP);
594
64.2k
    }
llvm::MachineFunction* llvm::rdf::CodeNode::getCode<llvm::MachineFunction*>() const
Line
Count
Source
592
1.72k
    template <typename T> T getCode() const {
593
1.72k
      return static_cast<T>(Code.CP);
594
1.72k
    }
595
29.3k
    void setCode(void *C) {
596
29.3k
      Code.CP = C;
597
29.3k
    }
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 {
616
0
    MachineInstr *getCode() const {
617
0
      return nullptr;
618
0
    }
619
  };
620
621
  struct StmtNode : public InstrNode {
622
64.2k
    MachineInstr *getCode() const {
623
64.2k
      return CodeNode::getCode<MachineInstr*>();
624
64.2k
    }
625
  };
626
627
  struct BlockNode : public CodeNode {
628
52.9k
    MachineBasicBlock *getCode() const {
629
52.9k
      return CodeNode::getCode<MachineBasicBlock*>();
630
52.9k
    }
631
632
    void addPhi(NodeAddr<PhiNode*> PA, const DataFlowGraph &G);
633
  };
634
635
  struct FuncNode : public CodeNode {
636
1.72k
    MachineFunction *getCode() const {
637
1.72k
      return CodeNode::getCode<MachineFunction*>();
638
1.72k
    }
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 {
646
    DataFlowGraph(MachineFunction &mf, const TargetInstrInfo &tii,
647
        const TargetRegisterInfo &tri, const MachineDominatorTree &mdt,
648
        const MachineDominanceFrontier &mdf, const TargetOperandInfo &toi);
649
650
    NodeBase *ptr(NodeId N) const;
651
2.19M
    template <typename T> T ptr(NodeId N) const {
652
2.19M
      return static_cast<T>(ptr(N));
653
2.19M
    }
llvm::rdf::UseNode* llvm::rdf::DataFlowGraph::ptr<llvm::rdf::UseNode*>(unsigned int) const
Line
Count
Source
651
31.4k
    template <typename T> T ptr(NodeId N) const {
652
31.4k
      return static_cast<T>(ptr(N));
653
31.4k
    }
llvm::rdf::NodeBase* llvm::rdf::DataFlowGraph::ptr<llvm::rdf::NodeBase*>(unsigned int) const
Line
Count
Source
651
1.89M
    template <typename T> T ptr(NodeId N) const {
652
1.89M
      return static_cast<T>(ptr(N));
653
1.89M
    }
llvm::rdf::DefNode* llvm::rdf::DataFlowGraph::ptr<llvm::rdf::DefNode*>(unsigned int) const
Line
Count
Source
651
129k
    template <typename T> T ptr(NodeId N) const {
652
129k
      return static_cast<T>(ptr(N));
653
129k
    }
llvm::rdf::PhiNode* llvm::rdf::DataFlowGraph::ptr<llvm::rdf::PhiNode*>(unsigned int) const
Line
Count
Source
651
3.58k
    template <typename T> T ptr(NodeId N) const {
652
3.58k
      return static_cast<T>(ptr(N));
653
3.58k
    }
llvm::rdf::BlockNode* llvm::rdf::DataFlowGraph::ptr<llvm::rdf::BlockNode*>(unsigned int) const
Line
Count
Source
651
1.66k
    template <typename T> T ptr(NodeId N) const {
652
1.66k
      return static_cast<T>(ptr(N));
653
1.66k
    }
llvm::rdf::DefNode const* llvm::rdf::DataFlowGraph::ptr<llvm::rdf::DefNode const*>(unsigned int) const
Line
Count
Source
651
23
    template <typename T> T ptr(NodeId N) const {
652
23
      return static_cast<T>(ptr(N));
653
23
    }
llvm::rdf::RefNode* llvm::rdf::DataFlowGraph::ptr<llvm::rdf::RefNode*>(unsigned int) const
Line
Count
Source
651
75.3k
    template <typename T> T ptr(NodeId N) const {
652
75.3k
      return static_cast<T>(ptr(N));
653
75.3k
    }
llvm::rdf::InstrNode* llvm::rdf::DataFlowGraph::ptr<llvm::rdf::InstrNode*>(unsigned int) const
Line
Count
Source
651
59.8k
    template <typename T> T ptr(NodeId N) const {
652
59.8k
      return static_cast<T>(ptr(N));
653
59.8k
    }
llvm::rdf::StmtNode* llvm::rdf::DataFlowGraph::ptr<llvm::rdf::StmtNode*>(unsigned int) const
Line
Count
Source
651
2
    template <typename T> T ptr(NodeId N) const {
652
2
      return static_cast<T>(ptr(N));
653
2
    }
654
655
    NodeId id(const NodeBase *P) const;
656
657
2.19M
    template <typename T> NodeAddr<T> addr(NodeId N) const {
658
2.19M
      return { ptr<T>(N), N };
659
2.19M
    }
llvm::rdf::NodeAddr<llvm::rdf::StmtNode*> llvm::rdf::DataFlowGraph::addr<llvm::rdf::StmtNode*>(unsigned int) const
Line
Count
Source
657
2
    template <typename T> NodeAddr<T> addr(NodeId N) const {
658
2
      return { ptr<T>(N), N };
659
2
    }
llvm::rdf::NodeAddr<llvm::rdf::DefNode*> llvm::rdf::DataFlowGraph::addr<llvm::rdf::DefNode*>(unsigned int) const
Line
Count
Source
657
129k
    template <typename T> NodeAddr<T> addr(NodeId N) const {
658
129k
      return { ptr<T>(N), N };
659
129k
    }
llvm::rdf::NodeAddr<llvm::rdf::UseNode*> llvm::rdf::DataFlowGraph::addr<llvm::rdf::UseNode*>(unsigned int) const
Line
Count
Source
657
31.4k
    template <typename T> NodeAddr<T> addr(NodeId N) const {
658
31.4k
      return { ptr<T>(N), N };
659
31.4k
    }
llvm::rdf::NodeAddr<llvm::rdf::NodeBase*> llvm::rdf::DataFlowGraph::addr<llvm::rdf::NodeBase*>(unsigned int) const
Line
Count
Source
657
1.89M
    template <typename T> NodeAddr<T> addr(NodeId N) const {
658
1.89M
      return { ptr<T>(N), N };
659
1.89M
    }
llvm::rdf::NodeAddr<llvm::rdf::InstrNode*> llvm::rdf::DataFlowGraph::addr<llvm::rdf::InstrNode*>(unsigned int) const
Line
Count
Source
657
59.8k
    template <typename T> NodeAddr<T> addr(NodeId N) const {
658
59.8k
      return { ptr<T>(N), N };
659
59.8k
    }
llvm::rdf::NodeAddr<llvm::rdf::RefNode*> llvm::rdf::DataFlowGraph::addr<llvm::rdf::RefNode*>(unsigned int) const
Line
Count
Source
657
75.3k
    template <typename T> NodeAddr<T> addr(NodeId N) const {
658
75.3k
      return { ptr<T>(N), N };
659
75.3k
    }
llvm::rdf::NodeAddr<llvm::rdf::PhiNode*> llvm::rdf::DataFlowGraph::addr<llvm::rdf::PhiNode*>(unsigned int) const
Line
Count
Source
657
3.58k
    template <typename T> NodeAddr<T> addr(NodeId N) const {
658
3.58k
      return { ptr<T>(N), N };
659
3.58k
    }
llvm::rdf::NodeAddr<llvm::rdf::BlockNode*> llvm::rdf::DataFlowGraph::addr<llvm::rdf::BlockNode*>(unsigned int) const
Line
Count
Source
657
1.66k
    template <typename T> NodeAddr<T> addr(NodeId N) const {
658
1.66k
      return { ptr<T>(N), N };
659
1.66k
    }
llvm::rdf::NodeAddr<llvm::rdf::DefNode const*> llvm::rdf::DataFlowGraph::addr<llvm::rdf::DefNode const*>(unsigned int) const
Line
Count
Source
657
23
    template <typename T> NodeAddr<T> addr(NodeId N) const {
658
23
      return { ptr<T>(N), N };
659
23
    }
660
661
5.51k
    NodeAddr<FuncNode*> getFunc() const { return Func; }
662
2.33k
    MachineFunction &getMF() const { return MF; }
663
2
    const TargetInstrInfo &getTII() const { return TII; }
664
3.15k
    const TargetRegisterInfo &getTRI() const { return TRI; }
665
8.43k
    const PhysicalRegisterInfo &getPRI() const { return PRI; }
666
3.62k
    const MachineDominatorTree &getDT() const { return MDT; }
667
2.76k
    const MachineDominanceFrontier &getDF() const { return MDF; }
668
204
    const RegisterAggr &getLiveIns() const { return LiveIns; }
669
670
    struct DefStack {
671
55.5k
      DefStack() = default;
672
673
182k
      bool empty() const 
{ return Stack.empty() || 182k
top() == bottom()125k
; }
674
675
    private:
676
      using value_type = NodeAddr<DefNode *>;
677
      struct Iterator {
678
        using value_type = DefStack::value_type;
679
680
0
        Iterator &up() { Pos = DS.nextUp(Pos); return *this; }
681
7.63k
        Iterator &down() { Pos = DS.nextDown(Pos); return *this; }
682
683
55.9k
        value_type operator*() const {
684
55.9k
          assert(Pos >= 1);
685
55.9k
          return DS.Stack[Pos-1];
686
55.9k
        }
687
59.3k
        const value_type *operator->() const {
688
59.3k
          assert(Pos >= 1);
689
59.3k
          return &DS.Stack[Pos-1];
690
59.3k
        }
691
125k
        bool operator==(const Iterator &It) const { return Pos == It.Pos; }
692
59.7k
        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
177k
      iterator top() const { return Iterator(*this, true); }
709
177k
      iterator bottom() const { return Iterator(*this, false); }
710
      unsigned size() const;
711
712
169k
      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
507k
      bool isDelimiter(const StorageType::value_type &P, NodeId N = 0) const {
723
145k
        return (P.Addr == nullptr) && 
(N == 0 || 145k
P.Id == N73.4k
);
724
507k
      }
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
741
19.8k
    PackedRegisterRef pack(RegisterRef RR) {
742
19.8k
      return { RR.Reg, LMI.getIndexForLaneMask(RR.Mask) };
743
19.8k
    }
744
0
    PackedRegisterRef pack(RegisterRef RR) const {
745
0
      return { RR.Reg, LMI.getIndexForLaneMask(RR.Mask) };
746
0
    }
747
171k
    RegisterRef unpack(PackedRegisterRef PR) const {
748
171k
      return RegisterRef(PR.Reg, LMI.getLaneMaskForIndex(PR.MaskId));
749
171k
    }
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;
757
    NodeAddr<RefNode*> getNextImp(NodeAddr<InstrNode*> IA,
758
        NodeAddr<RefNode*> RA, bool Create);
759
    NodeAddr<RefNode*> getNextImp(NodeAddr<InstrNode*> IA,
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
769
17.8k
    NodeAddr<BlockNode*> findBlock(MachineBasicBlock *BB) const {
770
17.8k
      return BlockNodes.at(BB);
771
17.8k
    }
772
773
4.20k
    void unlinkUse(NodeAddr<UseNode*> UA, bool RemoveFromOwner) {
774
4.20k
      unlinkUseDF(UA);
775
4.20k
      if (RemoveFromOwner)
776
4.18k
        removeFromOwner(UA);
777
4.20k
    }
778
779
1.95k
    void unlinkDef(NodeAddr<DefNode*> DA, bool RemoveFromOwner) {
780
1.95k
      unlinkDefDF(DA);
781
1.95k
      if (RemoveFromOwner)
782
1.95k
        removeFromOwner(DA);
783
1.95k
    }
784
785
    // Some useful filters.
786
    template <uint16_t Kind>
787
39.7k
    static bool IsRef(const NodeAddr<NodeBase*> BA) {
788
39.7k
      return BA.Addr->getType() == NodeAttrs::Ref &&
789
39.7k
             BA.Addr->getKind() == Kind;
790
39.7k
    }
bool llvm::rdf::DataFlowGraph::IsRef<(unsigned short)4>(llvm::rdf::NodeAddr<llvm::rdf::NodeBase*>)
Line
Count
Source
787
13.8k
    static bool IsRef(const NodeAddr<NodeBase*> BA) {
788
13.8k
      return BA.Addr->getType() == NodeAttrs::Ref &&
789
13.8k
             BA.Addr->getKind() == Kind;
790
13.8k
    }
bool llvm::rdf::DataFlowGraph::IsRef<(unsigned short)8>(llvm::rdf::NodeAddr<llvm::rdf::NodeBase*>)
Line
Count
Source
787
25.9k
    static bool IsRef(const NodeAddr<NodeBase*> BA) {
788
25.9k
      return BA.Addr->getType() == NodeAttrs::Ref &&
789
25.9k
             BA.Addr->getKind() == Kind;
790
25.9k
    }
791
792
    template <uint16_t Kind>
793
159k
    static bool IsCode(const NodeAddr<NodeBase*> BA) {
794
159k
      return BA.Addr->getType() == NodeAttrs::Code &&
795
159k
             BA.Addr->getKind() == Kind;
796
159k
    }
bool llvm::rdf::DataFlowGraph::IsCode<(unsigned short)16>(llvm::rdf::NodeAddr<llvm::rdf::NodeBase*>)
Line
Count
Source
793
74.3k
    static bool IsCode(const NodeAddr<NodeBase*> BA) {
794
74.3k
      return BA.Addr->getType() == NodeAttrs::Code &&
795
74.3k
             BA.Addr->getKind() == Kind;
796
74.3k
    }
bool llvm::rdf::DataFlowGraph::IsCode<(unsigned short)12>(llvm::rdf::NodeAddr<llvm::rdf::NodeBase*>)
Line
Count
Source
793
84.8k
    static bool IsCode(const NodeAddr<NodeBase*> BA) {
794
84.8k
      return BA.Addr->getType() == NodeAttrs::Code &&
795
84.8k
             BA.Addr->getKind() == Kind;
796
84.8k
    }
797
798
338k
    static bool IsDef(const NodeAddr<NodeBase*> BA) {
799
338k
      return BA.Addr->getType() == NodeAttrs::Ref &&
800
338k
             BA.Addr->getKind() == NodeAttrs::Def;
801
338k
    }
802
803
116k
    static bool IsUse(const NodeAddr<NodeBase*> BA) {
804
116k
      return BA.Addr->getType() == NodeAttrs::Ref &&
805
116k
             BA.Addr->getKind() == NodeAttrs::Use;
806
116k
    }
807
808
29.1k
    static bool IsPhi(const NodeAddr<NodeBase*> BA) {
809
29.1k
      return BA.Addr->getType() == NodeAttrs::Code &&
810
29.1k
             BA.Addr->getKind() == NodeAttrs::Phi;
811
29.1k
    }
812
813
40.1k
    static bool IsPreservingDef(const NodeAddr<DefNode*> DA) {
814
40.1k
      uint16_t Flags = DA.Addr->getFlags();
815
2.34k
      return (Flags & NodeAttrs::Preserving) && !(Flags & NodeAttrs::Undef);
816
40.1k
    }
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);
825
    NodeAddr<UseNode*> newUse(NodeAddr<InstrNode*> Owner,
826
        MachineOperand &Op, uint16_t Flags = NodeAttrs::None);
827
    NodeAddr<PhiUseNode*> newPhiUse(NodeAddr<PhiNode*> Owner,
828
        RegisterRef RR, NodeAddr<BlockNode*> PredB,
829
        uint16_t Flags = NodeAttrs::PhiRef);
830
    NodeAddr<DefNode*> newDef(NodeAddr<InstrNode*> Owner,
831
        MachineOperand &Op, uint16_t Flags = NodeAttrs::None);
832
    NodeAddr<DefNode*> newDef(NodeAddr<InstrNode*> Owner,
833
        RegisterRef RR, uint16_t Flags = NodeAttrs::PhiRef);
834
    NodeAddr<PhiNode*> newPhi(NodeAddr<BlockNode*> Owner);
835
    NodeAddr<StmtNode*> newStmt(NodeAddr<BlockNode*> Owner,
836
        MachineInstr *MI);
837
    NodeAddr<BlockNode*> newBlock(NodeAddr<FuncNode*> Owner,
838
        MachineBasicBlock *BB);
839
    NodeAddr<FuncNode*> newFunc(MachineFunction *MF);
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 buildBlockRefs(NodeAddr<BlockNode*> BA, BlockRefsMap &RefM);
850
    void recordDefsForDF(BlockRefsMap &PhiM, BlockRefsMap &RefM,
851
        NodeAddr<BlockNode*> BA);
852
    void buildPhis(BlockRefsMap &PhiM, BlockRefsMap &RefM,
853
        NodeAddr<BlockNode*> BA);
854
    void removeUnusedPhis();
855
856
    void pushClobbers(NodeAddr<InstrNode*> IA, DefStackMap &DM);
857
    void pushDefs(NodeAddr<InstrNode*> IA, DefStackMap &DM);
858
    template <typename T> void linkRefUp(NodeAddr<InstrNode*> IA,
859
        NodeAddr<T> TA, DefStack &DS);
860
    template <typename Predicate> void linkStmtRefs(DefStackMap &DefM,
861
        NodeAddr<StmtNode*> SA, Predicate P);
862
    void linkBlockRefs(DefStackMap &DefM, NodeAddr<BlockNode*> BA);
863
864
    void unlinkUseDF(NodeAddr<UseNode*> UA);
865
    void unlinkDefDF(NodeAddr<DefNode*> DA);
866
867
6.13k
    void removeFromOwner(NodeAddr<RefNode*> RA) {
868
6.13k
      NodeAddr<InstrNode*> IA = RA.Addr->getOwner(*this);
869
6.13k
      IA.Addr->removeMember(RA, *this);
870
6.13k
    }
871
872
    MachineFunction &MF;
873
    const TargetInstrInfo &TII;
874
    const TargetRegisterInfo &TRI;
875
    const PhysicalRegisterInfo PRI;
876
    const MachineDominatorTree &MDT;
877
    const MachineDominanceFrontier &MDF;
878
    const TargetOperandInfo &TOI;
879
880
    RegisterAggr LiveIns;
881
    NodeAddr<FuncNode*> Func;
882
    NodeAllocator Memory;
883
    // Local map:  MachineBasicBlock -> NodeAddr<BlockNode*>
884
    std::map<MachineBasicBlock*,NodeAddr<BlockNode*>> BlockNodes;
885
    // Lane mask map.
886
    LaneMaskIndex LMI;
887
  };  // struct DataFlowGraph
888
889
  template <typename Predicate>
890
  NodeAddr<RefNode*> RefNode::getNextRef(RegisterRef RR, Predicate P,
891
94.3k
        bool NextOnly, const DataFlowGraph &G) {
892
94.3k
    // Get the "Next" reference in the circular list that references RR and
893
94.3k
    // satisfies predicate "Pred".
894
94.3k
    auto NA = G.addr<NodeBase*>(getNext());
895
94.3k
896
119k
    while (
NA.Addr != this119k
) {
897
104k
      if (
NA.Addr->getType() == NodeAttrs::Ref104k
) {
898
79.3k
        NodeAddr<RefNode*> RA = NA;
899
79.3k
        if (
RA.Addr->getRegRef(G) == RR && 79.3k
P(NA)44.4k
)
900
11.5k
          return NA;
901
67.7k
        
if (67.7k
NextOnly67.7k
)
902
67.7k
          break;
903
0
        NA = G.addr<NodeBase*>(NA.Addr->getNext());
904
104k
      } else {
905
25.1k
        // We've hit the beginning of the chain.
906
25.1k
        assert(NA.Addr->getType() == NodeAttrs::Code);
907
25.1k
        NodeAddr<CodeNode*> CA = NA;
908
25.1k
        NA = CA.Addr->getFirstMember(G);
909
25.1k
      }
910
104k
    }
911
94.3k
    // Return the equivalent of "nullptr" if such a node was not found.
912
82.7k
    return NodeAddr<RefNode*>();
913
94.3k
  }
RDFGraph.cpp:llvm::rdf::NodeAddr<llvm::rdf::RefNode*> llvm::rdf::RefNode::getNextRef<llvm::rdf::DataFlowGraph::getNextRelated(llvm::rdf::NodeAddr<llvm::rdf::InstrNode*>, llvm::rdf::NodeAddr<llvm::rdf::RefNode*>) const::$_5>(llvm::rdf::RegisterRef, llvm::rdf::DataFlowGraph::getNextRelated(llvm::rdf::NodeAddr<llvm::rdf::InstrNode*>, llvm::rdf::NodeAddr<llvm::rdf::RefNode*>) const::$_5, bool, llvm::rdf::DataFlowGraph const&)
Line
Count
Source
891
59.9k
        bool NextOnly, const DataFlowGraph &G) {
892
59.9k
    // Get the "Next" reference in the circular list that references RR and
893
59.9k
    // satisfies predicate "Pred".
894
59.9k
    auto NA = G.addr<NodeBase*>(getNext());
895
59.9k
896
71.0k
    while (
NA.Addr != this71.0k
) {
897
60.4k
      if (
NA.Addr->getType() == NodeAttrs::Ref60.4k
) {
898
49.2k
        NodeAddr<RefNode*> RA = NA;
899
49.2k
        if (
RA.Addr->getRegRef(G) == RR && 49.2k
P(NA)14.3k
)
900
6.75k
          return NA;
901
42.5k
        
if (42.5k
NextOnly42.5k
)
902
42.5k
          break;
903
0
        NA = G.addr<NodeBase*>(NA.Addr->getNext());
904
60.4k
      } else {
905
11.1k
        // We've hit the beginning of the chain.
906
11.1k
        assert(NA.Addr->getType() == NodeAttrs::Code);
907
11.1k
        NodeAddr<CodeNode*> CA = NA;
908
11.1k
        NA = CA.Addr->getFirstMember(G);
909
11.1k
      }
910
60.4k
    }
911
59.9k
    // Return the equivalent of "nullptr" if such a node was not found.
912
53.1k
    return NodeAddr<RefNode*>();
913
59.9k
  }
RDFGraph.cpp:llvm::rdf::NodeAddr<llvm::rdf::RefNode*> llvm::rdf::RefNode::getNextRef<llvm::rdf::DataFlowGraph::getNextRelated(llvm::rdf::NodeAddr<llvm::rdf::InstrNode*>, llvm::rdf::NodeAddr<llvm::rdf::RefNode*>) const::$_6>(llvm::rdf::RegisterRef, llvm::rdf::DataFlowGraph::getNextRelated(llvm::rdf::NodeAddr<llvm::rdf::InstrNode*>, llvm::rdf::NodeAddr<llvm::rdf::RefNode*>) const::$_6, bool, llvm::rdf::DataFlowGraph const&)
Line
Count
Source
891
34.3k
        bool NextOnly, const DataFlowGraph &G) {
892
34.3k
    // Get the "Next" reference in the circular list that references RR and
893
34.3k
    // satisfies predicate "Pred".
894
34.3k
    auto NA = G.addr<NodeBase*>(getNext());
895
34.3k
896
48.3k
    while (
NA.Addr != this48.3k
) {
897
44.0k
      if (
NA.Addr->getType() == NodeAttrs::Ref44.0k
) {
898
30.0k
        NodeAddr<RefNode*> RA = NA;
899
30.0k
        if (
RA.Addr->getRegRef(G) == RR && 30.0k
P(NA)30.0k
)
900
4.84k
          return NA;
901
25.2k
        
if (25.2k
NextOnly25.2k
)
902
25.2k
          break;
903
0
        NA = G.addr<NodeBase*>(NA.Addr->getNext());
904
44.0k
      } else {
905
14.0k
        // We've hit the beginning of the chain.
906
14.0k
        assert(NA.Addr->getType() == NodeAttrs::Code);
907
14.0k
        NodeAddr<CodeNode*> CA = NA;
908
14.0k
        NA = CA.Addr->getFirstMember(G);
909
14.0k
      }
910
44.0k
    }
911
34.3k
    // Return the equivalent of "nullptr" if such a node was not found.
912
29.5k
    return NodeAddr<RefNode*>();
913
34.3k
  }
914
915
  template <typename Predicate>
916
345k
  NodeList CodeNode::members_if(Predicate P, const DataFlowGraph &G) const {
917
345k
    NodeList MM;
918
345k
    auto M = getFirstMember(G);
919
345k
    if (M.Id == 0)
920
2.86k
      return MM;
921
345k
922
1.33M
    
while (342k
M.Addr != this1.33M
) {
923
992k
      if (P(M))
924
579k
        MM.push_back(M);
925
992k
      M = G.addr<NodeBase*>(M.Addr->getNext());
926
992k
    }
927
342k
    return MM;
928
345k
  }
llvm::SmallVector<llvm::rdf::NodeAddr<llvm::rdf::NodeBase*>, 4u> llvm::rdf::CodeNode::members_if<bool (*)(llvm::rdf::NodeAddr<llvm::rdf::NodeBase*>)>(bool (*)(llvm::rdf::NodeAddr<llvm::rdf::NodeBase*>), llvm::rdf::DataFlowGraph const&) const
Line
Count
Source
916
143k
  NodeList CodeNode::members_if(Predicate P, const DataFlowGraph &G) const {
917
143k
    NodeList MM;
918
143k
    auto M = getFirstMember(G);
919
143k
    if (M.Id == 0)
920
1.11k
      return MM;
921
143k
922
531k
    
while (142k
M.Addr != this531k
) {
923
389k
      if (P(M))
924
171k
        MM.push_back(M);
925
389k
      M = G.addr<NodeBase*>(M.Addr->getNext());
926
389k
    }
927
142k
    return MM;
928
143k
  }
RDFGraph.cpp:llvm::SmallVector<llvm::rdf::NodeAddr<llvm::rdf::NodeBase*>, 4u> llvm::rdf::CodeNode::members_if<llvm::rdf::CodeNode::members(llvm::rdf::DataFlowGraph const&) const::$_2>(llvm::rdf::CodeNode::members(llvm::rdf::DataFlowGraph const&) const::$_2, llvm::rdf::DataFlowGraph const&) const
Line
Count
Source
916
94.6k
  NodeList CodeNode::members_if(Predicate P, const DataFlowGraph &G) const {
917
94.6k
    NodeList MM;
918
94.6k
    auto M = getFirstMember(G);
919
94.6k
    if (M.Id == 0)
920
1.55k
      return MM;
921
94.6k
922
418k
    
while (93.1k
M.Addr != this418k
) {
923
324k
      if (P(M))
924
324k
        MM.push_back(M);
925
324k
      M = G.addr<NodeBase*>(M.Addr->getNext());
926
324k
    }
927
93.1k
    return MM;
928
94.6k
  }
RDFGraph.cpp:llvm::SmallVector<llvm::rdf::NodeAddr<llvm::rdf::NodeBase*>, 4u> llvm::rdf::CodeNode::members_if<llvm::rdf::FuncNode::findBlock(llvm::MachineBasicBlock const*, llvm::rdf::DataFlowGraph const&) const::$_3>(llvm::rdf::FuncNode::findBlock(llvm::MachineBasicBlock const*, llvm::rdf::DataFlowGraph const&) const::$_3, llvm::rdf::DataFlowGraph const&) const
Line
Count
Source
916
3.02k
  NodeList CodeNode::members_if(Predicate P, const DataFlowGraph &G) const {
917
3.02k
    NodeList MM;
918
3.02k
    auto M = getFirstMember(G);
919
3.02k
    if (M.Id == 0)
920
0
      return MM;
921
3.02k
922
21.2k
    
while (3.02k
M.Addr != this21.2k
) {
923
18.2k
      if (P(M))
924
3.02k
        MM.push_back(M);
925
18.2k
      M = G.addr<NodeBase*>(M.Addr->getNext());
926
18.2k
    }
927
3.02k
    return MM;
928
3.02k
  }
RDFGraph.cpp:llvm::SmallVector<llvm::rdf::NodeAddr<llvm::rdf::NodeBase*>, 4u> llvm::rdf::CodeNode::members_if<llvm::rdf::DataFlowGraph::linkBlockRefs(std::__1::unordered_map<unsigned int, llvm::rdf::DataFlowGraph::DefStack, std::__1::hash<unsigned int>, std::__1::equal_to<unsigned int>, std::__1::allocator<std::__1::pair<unsigned int const, llvm::rdf::DataFlowGraph::DefStack> > >&, llvm::rdf::NodeAddr<llvm::rdf::BlockNode*>)::$_14>(llvm::rdf::DataFlowGraph::linkBlockRefs(std::__1::unordered_map<unsigned int, llvm::rdf::DataFlowGraph::DefStack, std::__1::hash<unsigned int>, std::__1::equal_to<unsigned int>, std::__1::allocator<std::__1::pair<unsigned int const, llvm::rdf::DataFlowGraph::DefStack> > >&, llvm::rdf::NodeAddr<llvm::rdf::BlockNode*>)::$_14, llvm::rdf::DataFlowGraph const&) const
Line
Count
Source
916
23.4k
  NodeList CodeNode::members_if(Predicate P, const DataFlowGraph &G) const {
917
23.4k
    NodeList MM;
918
23.4k
    auto M = getFirstMember(G);
919
23.4k
    if (M.Id == 0)
920
96
      return MM;
921
23.4k
922
74.2k
    
while (23.3k
M.Addr != this74.2k
) {
923
50.8k
      if (P(M))
924
458
        MM.push_back(M);
925
50.8k
      M = G.addr<NodeBase*>(M.Addr->getNext());
926
50.8k
    }
927
23.3k
    return MM;
928
23.4k
  }
RDFGraph.cpp:llvm::SmallVector<llvm::rdf::NodeAddr<llvm::rdf::NodeBase*>, 4u> llvm::rdf::CodeNode::members_if<llvm::rdf::DataFlowGraph::linkBlockRefs(std::__1::unordered_map<unsigned int, llvm::rdf::DataFlowGraph::DefStack, std::__1::hash<unsigned int>, std::__1::equal_to<unsigned int>, std::__1::allocator<std::__1::pair<unsigned int const, llvm::rdf::DataFlowGraph::DefStack> > >&, llvm::rdf::NodeAddr<llvm::rdf::BlockNode*>)::$_15>(llvm::rdf::DataFlowGraph::linkBlockRefs(std::__1::unordered_map<unsigned int, llvm::rdf::DataFlowGraph::DefStack, std::__1::hash<unsigned int>, std::__1::equal_to<unsigned int>, std::__1::allocator<std::__1::pair<unsigned int const, llvm::rdf::DataFlowGraph::DefStack> > >&, llvm::rdf::NodeAddr<llvm::rdf::BlockNode*>)::$_15, llvm::rdf::DataFlowGraph const&) const
Line
Count
Source
916
23.4k
  NodeList CodeNode::members_if(Predicate P, const DataFlowGraph &G) const {
917
23.4k
    NodeList MM;
918
23.4k
    auto M = getFirstMember(G);
919
23.4k
    if (M.Id == 0)
920
96
      return MM;
921
23.4k
922
75.9k
    
while (23.3k
M.Addr != this75.9k
) {
923
52.5k
      if (P(M))
924
22.0k
        MM.push_back(M);
925
52.5k
      M = G.addr<NodeBase*>(M.Addr->getNext());
926
52.5k
    }
927
23.3k
    return MM;
928
23.4k
  }
RDFGraph.cpp:llvm::SmallVector<llvm::rdf::NodeAddr<llvm::rdf::NodeBase*>, 4u> llvm::rdf::CodeNode::members_if<llvm::rdf::DataFlowGraph::linkBlockRefs(std::__1::unordered_map<unsigned int, llvm::rdf::DataFlowGraph::DefStack, std::__1::hash<unsigned int>, std::__1::equal_to<unsigned int>, std::__1::allocator<std::__1::pair<unsigned int const, llvm::rdf::DataFlowGraph::DefStack> > >&, llvm::rdf::NodeAddr<llvm::rdf::BlockNode*>)::$_16>(llvm::rdf::DataFlowGraph::linkBlockRefs(std::__1::unordered_map<unsigned int, llvm::rdf::DataFlowGraph::DefStack, std::__1::hash<unsigned int>, std::__1::equal_to<unsigned int>, std::__1::allocator<std::__1::pair<unsigned int const, llvm::rdf::DataFlowGraph::DefStack> > >&, llvm::rdf::NodeAddr<llvm::rdf::BlockNode*>)::$_16, llvm::rdf::DataFlowGraph const&) const
Line
Count
Source
916
11.4k
  NodeList CodeNode::members_if(Predicate P, const DataFlowGraph &G) const {
917
11.4k
    NodeList MM;
918
11.4k
    auto M = getFirstMember(G);
919
11.4k
    if (M.Id == 0)
920
0
      return MM;
921
11.4k
922
49.4k
    
while (11.4k
M.Addr != this49.4k
) {
923
37.9k
      if (P(M))
924
11.4k
        MM.push_back(M);
925
37.9k
      M = G.addr<NodeBase*>(M.Addr->getNext());
926
37.9k
    }
927
11.4k
    return MM;
928
11.4k
  }
RDFLiveness.cpp:llvm::SmallVector<llvm::rdf::NodeAddr<llvm::rdf::NodeBase*>, 4u> llvm::rdf::CodeNode::members_if<llvm::rdf::Liveness::getAllReachingDefs(llvm::rdf::RegisterRef, llvm::rdf::NodeAddr<llvm::rdf::RefNode*>, bool, bool, llvm::rdf::RegisterAggr const&)::$_2>(llvm::rdf::Liveness::getAllReachingDefs(llvm::rdf::RegisterRef, llvm::rdf::NodeAddr<llvm::rdf::RefNode*>, bool, bool, llvm::rdf::RegisterAggr const&)::$_2, llvm::rdf::DataFlowGraph const&) const
Line
Count
Source
916
45.4k
  NodeList CodeNode::members_if(Predicate P, const DataFlowGraph &G) const {
917
45.4k
    NodeList MM;
918
45.4k
    auto M = getFirstMember(G);
919
45.4k
    if (M.Id == 0)
920
0
      return MM;
921
45.4k
922
163k
    
while (45.4k
M.Addr != this163k
) {
923
118k
      if (P(M))
924
46.1k
        MM.push_back(M);
925
118k
      M = G.addr<NodeBase*>(M.Addr->getNext());
926
118k
    }
927
45.4k
    return MM;
928
45.4k
  }
929
930
  template <typename T> struct Print;
931
  template <typename T>
932
  raw_ostream &operator<< (raw_ostream &OS, const Print<T> &P);
933
934
  template <typename T>
935
  struct Print {
936
0
    Print(const T &x, const DataFlowGraph &g) : Obj(x), G(g) {}
Unexecuted instantiation: llvm::rdf::Print<std::__1::map<unsigned int, std::__1::set<std::__1::pair<unsigned int, llvm::LaneBitmask>, std::__1::less<std::__1::pair<unsigned int, llvm::LaneBitmask> >, std::__1::allocator<std::__1::pair<unsigned int, llvm::LaneBitmask> > >, std::__1::less<unsigned int>, std::__1::allocator<std::__1::pair<unsigned int const, std::__1::set<std::__1::pair<unsigned int, llvm::LaneBitmask>, std::__1::less<std::__1::pair<unsigned int, llvm::LaneBitmask> >, std::__1::allocator<std::__1::pair<unsigned int, llvm::LaneBitmask> > > > > > >::Print(std::__1::map<unsigned int, std::__1::set<std::__1::pair<unsigned int, llvm::LaneBitmask>, std::__1::less<std::__1::pair<unsigned int, llvm::LaneBitmask> >, std::__1::allocator<std::__1::pair<unsigned int, llvm::LaneBitmask> > >, std::__1::less<unsigned int>, std::__1::allocator<std::__1::pair<unsigned int const, std::__1::set<std::__1::pair<unsigned int, llvm::LaneBitmask>, std::__1::less<std::__1::pair<unsigned int, llvm::LaneBitmask> >, std::__1::allocator<std::__1::pair<unsigned int, llvm::LaneBitmask> > > > > > const&, llvm::rdf::DataFlowGraph const&)
Unexecuted instantiation: llvm::rdf::Print<llvm::rdf::RegisterAggr>::Print(llvm::rdf::RegisterAggr const&, llvm::rdf::DataFlowGraph const&)
Unexecuted instantiation: llvm::rdf::Print<llvm::rdf::NodeAddr<llvm::rdf::BlockNode*> >::Print(llvm::rdf::NodeAddr<llvm::rdf::BlockNode*> const&, llvm::rdf::DataFlowGraph const&)
Unexecuted instantiation: llvm::rdf::Print<llvm::rdf::NodeAddr<llvm::rdf::StmtNode*> >::Print(llvm::rdf::NodeAddr<llvm::rdf::StmtNode*> const&, llvm::rdf::DataFlowGraph const&)
Unexecuted instantiation: llvm::rdf::Print<llvm::rdf::NodeAddr<llvm::rdf::PhiNode*> >::Print(llvm::rdf::NodeAddr<llvm::rdf::PhiNode*> const&, llvm::rdf::DataFlowGraph const&)
Unexecuted instantiation: llvm::rdf::Print<llvm::rdf::NodeAddr<llvm::rdf::UseNode*> >::Print(llvm::rdf::NodeAddr<llvm::rdf::UseNode*> const&, llvm::rdf::DataFlowGraph const&)
Unexecuted instantiation: llvm::rdf::Print<llvm::rdf::NodeAddr<llvm::rdf::PhiUseNode*> >::Print(llvm::rdf::NodeAddr<llvm::rdf::PhiUseNode*> const&, llvm::rdf::DataFlowGraph const&)
Unexecuted instantiation: llvm::rdf::Print<llvm::rdf::NodeAddr<llvm::rdf::InstrNode*> >::Print(llvm::rdf::NodeAddr<llvm::rdf::InstrNode*> const&, llvm::rdf::DataFlowGraph const&)
Unexecuted instantiation: llvm::rdf::Print<unsigned int>::Print(unsigned int const&, llvm::rdf::DataFlowGraph const&)
Unexecuted instantiation: llvm::rdf::Print<llvm::rdf::NodeAddr<llvm::rdf::DefNode*> >::Print(llvm::rdf::NodeAddr<llvm::rdf::DefNode*> const&, llvm::rdf::DataFlowGraph const&)
Unexecuted instantiation: llvm::rdf::Print<llvm::rdf::NodeAddr<llvm::rdf::RefNode*> >::Print(llvm::rdf::NodeAddr<llvm::rdf::RefNode*> const&, llvm::rdf::DataFlowGraph const&)
Unexecuted instantiation: llvm::rdf::Print<llvm::rdf::RegisterRef>::Print(llvm::rdf::RegisterRef const&, llvm::rdf::DataFlowGraph const&)
Unexecuted instantiation: llvm::rdf::Print<llvm::rdf::NodeAddr<llvm::rdf::FuncNode*> >::Print(llvm::rdf::NodeAddr<llvm::rdf::FuncNode*> const&, llvm::rdf::DataFlowGraph const&)
937
938
    const T &Obj;
939
    const DataFlowGraph &G;
940
  };
941
942
  template <typename T>
943
  struct PrintNode : Print<NodeAddr<T>> {
944
    PrintNode(const NodeAddr<T> &x, const DataFlowGraph &g)
945
0
      : Print<NodeAddr<T>>(x, g) {}
Unexecuted instantiation: llvm::rdf::PrintNode<llvm::rdf::FuncNode*>::PrintNode(llvm::rdf::NodeAddr<llvm::rdf::FuncNode*> const&, llvm::rdf::DataFlowGraph const&)
Unexecuted instantiation: llvm::rdf::PrintNode<llvm::rdf::RefNode*>::PrintNode(llvm::rdf::NodeAddr<llvm::rdf::RefNode*> const&, llvm::rdf::DataFlowGraph const&)
Unexecuted instantiation: llvm::rdf::PrintNode<llvm::rdf::InstrNode*>::PrintNode(llvm::rdf::NodeAddr<llvm::rdf::InstrNode*> const&, llvm::rdf::DataFlowGraph const&)
Unexecuted instantiation: llvm::rdf::PrintNode<llvm::rdf::DefNode*>::PrintNode(llvm::rdf::NodeAddr<llvm::rdf::DefNode*> const&, llvm::rdf::DataFlowGraph const&)
Unexecuted instantiation: llvm::rdf::PrintNode<llvm::rdf::PhiUseNode*>::PrintNode(llvm::rdf::NodeAddr<llvm::rdf::PhiUseNode*> const&, llvm::rdf::DataFlowGraph const&)
Unexecuted instantiation: llvm::rdf::PrintNode<llvm::rdf::UseNode*>::PrintNode(llvm::rdf::NodeAddr<llvm::rdf::UseNode*> const&, llvm::rdf::DataFlowGraph const&)
Unexecuted instantiation: llvm::rdf::PrintNode<llvm::rdf::PhiNode*>::PrintNode(llvm::rdf::NodeAddr<llvm::rdf::PhiNode*> const&, llvm::rdf::DataFlowGraph const&)
Unexecuted instantiation: llvm::rdf::PrintNode<llvm::rdf::BlockNode*>::PrintNode(llvm::rdf::NodeAddr<llvm::rdf::BlockNode*> const&, llvm::rdf::DataFlowGraph const&)
Unexecuted instantiation: llvm::rdf::PrintNode<llvm::rdf::StmtNode*>::PrintNode(llvm::rdf::NodeAddr<llvm::rdf::StmtNode*> const&, llvm::rdf::DataFlowGraph const&)
946
  };
947
948
} // end namespace rdf
949
950
} // end namespace llvm
951
952
#endif // LLVM_LIB_TARGET_HEXAGON_RDFGRAPH_H