Coverage Report

Created: 2019-07-24 05:18

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