/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 |