1 | // Access-related classes for RTL SSA -*- C++ -*- |
2 | // Copyright (C) 2020-2024 Free Software Foundation, Inc. |
3 | // |
4 | // This file is part of GCC. |
5 | // |
6 | // GCC is free software; you can redistribute it and/or modify it under |
7 | // the terms of the GNU General Public License as published by the Free |
8 | // Software Foundation; either version 3, or (at your option) any later |
9 | // version. |
10 | // |
11 | // GCC is distributed in the hope that it will be useful, but WITHOUT ANY |
12 | // WARRANTY; without even the implied warranty of MERCHANTABILITY or |
13 | // FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
14 | // for more details. |
15 | // |
16 | // You should have received a copy of the GNU General Public License |
17 | // along with GCC; see the file COPYING3. If not see |
18 | // <http://www.gnu.org/licenses/>. |
19 | |
20 | namespace rtl_ssa { |
21 | |
22 | // Forward declarations. |
23 | class bb_info; |
24 | class clobber_group; |
25 | class def_node; |
26 | class ebb_info; |
27 | class insn_info; |
28 | class phi_info; |
29 | class set_info; |
30 | |
31 | // Used as a boolean argunent to certain routines. |
32 | enum class ignore_clobbers { NO, YES }; |
33 | |
34 | // Represents something that the SSA form tracks: either a register |
35 | // or memory. |
36 | class resource_info |
37 | { |
38 | public: |
39 | // Return true if this resource represents memory. |
40 | bool is_mem () const { return regno == MEM_REGNO; } |
41 | |
42 | // Return true if this resource represents a register. |
43 | bool is_reg () const { return regno != MEM_REGNO; } |
44 | |
45 | // Print the name of the resource to PP. |
46 | void print_identifier (pretty_printer *pp) const; |
47 | |
48 | // Possibly print additional information about the resource to PP. |
49 | void print_context (pretty_printer *pp) const; |
50 | |
51 | // A combination of print_identifier and print_context. |
52 | void print (pretty_printer *pp) const; |
53 | |
54 | // The mode with which the resource is being defined or used. This is |
55 | // always BLKmode for memory. It can also be BLKmode for registers if |
56 | // we don't yet know the real mode, or if the mode is not relevant for |
57 | // some reason. |
58 | machine_mode mode; |
59 | |
60 | // The pseudo register or single hard register that the resource represents, |
61 | // or MEM_REGNO for memory. |
62 | unsigned int regno; |
63 | }; |
64 | |
65 | // For simplicity, we treat memory as a single unified entity. |
66 | const resource_info memory = { .mode: E_BLKmode, .regno: MEM_REGNO }; |
67 | |
68 | // Flags used when printing access_infos. |
69 | // |
70 | // Print the location at which the access occurs. This is redundant |
71 | // when the access is being printed as part of the instruction or phi node |
72 | // that contains the access. |
73 | const unsigned int PP_ACCESS_INCLUDE_LOCATION = 1U << 0; |
74 | // |
75 | // Print links to other accesses: the definition that defines a use, |
76 | // the uses of a definition, and the inputs of a phi node. |
77 | const unsigned int PP_ACCESS_INCLUDE_LINKS = 1U << 1; |
78 | // |
79 | // Print additional properties about the access. |
80 | const unsigned int PP_ACCESS_INCLUDE_PROPERTIES = 1U << 2; |
81 | // |
82 | // The usual flags when printing an access in isolation. |
83 | const unsigned int PP_ACCESS_DEFAULT = (PP_ACCESS_INCLUDE_LOCATION |
84 | | PP_ACCESS_INCLUDE_LINKS |
85 | | PP_ACCESS_INCLUDE_PROPERTIES); |
86 | // |
87 | // The usual flags when printing a def_info from its defining instruction. |
88 | const unsigned int PP_ACCESS_SETTER = (PP_ACCESS_INCLUDE_LINKS |
89 | | PP_ACCESS_INCLUDE_PROPERTIES); |
90 | // |
91 | // The usual flags when printing a use_info from its user. |
92 | const unsigned int PP_ACCESS_USER = PP_ACCESS_INCLUDE_PROPERTIES; |
93 | |
94 | // The various ways of accessing a resource. The two range checks that |
95 | // we need to perform are [SET, PHI] (for set_info) and [SET, CLOBBER] |
96 | // (for def_info), so the ordering tries to make those tests as |
97 | // efficient as possible. |
98 | enum class access_kind : uint8_t |
99 | { |
100 | // Set the resource to a useful value. |
101 | SET, |
102 | |
103 | // A form of SET that collects the possible incoming values of the |
104 | // resource using a phi node; the resource does not actually change value. |
105 | PHI, |
106 | |
107 | // Set the resource to a value that is both unknown and not useful. |
108 | CLOBBER, |
109 | |
110 | // Use the current value of the resource. |
111 | USE |
112 | }; |
113 | |
114 | // A base class that represents an access to a resource. |
115 | class access_info |
116 | { |
117 | // Size: 1 LP64 word |
118 | friend class function_info; |
119 | |
120 | public: |
121 | // Return the resource that is being accessed. |
122 | resource_info resource () const { return { .mode: m_mode, .regno: m_regno }; } |
123 | |
124 | // Return true if the access is to memory. |
125 | bool is_mem () const { return m_regno == MEM_REGNO; } |
126 | |
127 | // Return true if the access is to a register. |
128 | bool is_reg () const { return m_regno != MEM_REGNO; } |
129 | |
130 | // If the access is to a register, return the register number, |
131 | // otherwise return MEM_REGNO. |
132 | unsigned int regno () const { return m_regno; } |
133 | |
134 | // For sets, return the mode of the value to which the resource is being set. |
135 | // For uses, return the mode in which the resource is being used (which for |
136 | // hard registers might be different from the mode in which the resource |
137 | // was set). |
138 | // |
139 | // When accessing memory, the mode is always BLKmode. When accessing |
140 | // pseudo registers, the mode is always the mode of the pseudo register |
141 | // (and so doesn't, for example, take subregs into account). |
142 | machine_mode mode () const { return m_mode; } |
143 | |
144 | // Return the kind of access that this is. |
145 | access_kind kind () const { return m_kind; } |
146 | |
147 | // Return true if the access occurs in a phi node or an "artificial" |
148 | // instruction (see insn_info), false if it occurs in a real instruction. |
149 | bool is_artificial () const { return m_is_artificial; } |
150 | |
151 | // Return the opposite of is_artificial. |
152 | bool is_real () const { return !m_is_artificial; } |
153 | |
154 | // Return true if this access is a set_info whose result is used by at least |
155 | // one nondebug instruction. |
156 | bool is_set_with_nondebug_insn_uses () const; |
157 | |
158 | // Return true if the access describes a set_info and if the value |
159 | // is defined by an RTX_AUTOINC rtx. |
160 | bool is_pre_post_modify () const { return m_is_pre_post_modify; } |
161 | |
162 | // Return true if the access is a clobber_info that describes the effect |
163 | // of a called function. This kind of clobber is added for -fipa-ra |
164 | // functions that clobber only a strict subset of the normal ABI set. |
165 | bool is_call_clobber () const { return m_is_call_clobber; } |
166 | |
167 | // Return true if the access is a use_info that simply marks a point in |
168 | // the live range of a set_info at which the value is live out from |
169 | // the containing EBB. |
170 | bool is_live_out_use () const { return m_is_live_out_use; } |
171 | |
172 | // Return true if the access is a use_info for an instruction and if |
173 | // at least some of the uses occur within a MEM address. |
174 | // |
175 | // There shouldn't be a need to check whether *all* uses occur within |
176 | // a MEM address, since in principle: |
177 | // |
178 | // A: (set (reg:SI R1) (mem:SI (post_inc:SI (reg:SI R2)))) |
179 | // |
180 | // should be semantically equivalent to: |
181 | // |
182 | // B: (parallel [(set (reg:SI R1) (mem:SI (reg:SI R2))) |
183 | // (set (reg:SI R2) (plus:SI (reg:SI R2) (const_int 4)))]) |
184 | // |
185 | // even though R2 occurs only in MEMs for A but occurs outside MEMs for B. |
186 | bool includes_address_uses () const { return m_includes_address_uses; } |
187 | |
188 | // Return true if the access occurs in an instruction and if at least |
189 | // some accesses to resource () occur in a read-modify-write context. |
190 | // This is equivalent to the DF_REF_READ_WRITE flag. |
191 | bool includes_read_writes () const { return m_includes_read_writes; } |
192 | |
193 | // Return true if the access occurs in an instruction and if at least |
194 | // some accesses to resource () occur in a subreg context. |
195 | bool includes_subregs () const { return m_includes_subregs; } |
196 | |
197 | // Return true if the access occurs in an instruction and if at least |
198 | // some accesses to resource () occur in a multi-register REG. |
199 | // This implies that resource () is a hard register. |
200 | bool includes_multiregs () const { return m_includes_multiregs; } |
201 | |
202 | // Return true if the access occurs in a real nondebug instruction |
203 | // and if all accesses to resource () occur in notes, rather than |
204 | // in the main instruction pattern. |
205 | bool only_occurs_in_notes () const { return m_only_occurs_in_notes; } |
206 | |
207 | // Return true if this is a temporary access, e.g. one created for |
208 | // an insn that is about to be inserted. |
209 | bool is_temporary () const { return m_is_temp; } |
210 | |
211 | protected: |
212 | access_info (resource_info, access_kind); |
213 | |
214 | void print_prefix_flags (pretty_printer *) const; |
215 | void print_properties_on_new_lines (pretty_printer *) const; |
216 | |
217 | private: |
218 | void set_mode (machine_mode mode) { m_mode = mode; } |
219 | |
220 | // The values returned by the accessors above. |
221 | unsigned int m_regno; |
222 | machine_mode m_mode : MACHINE_MODE_BITSIZE; |
223 | access_kind m_kind : 2; |
224 | |
225 | protected: |
226 | // The value returned by the accessors above. |
227 | unsigned int m_is_artificial : 1; |
228 | unsigned int m_is_set_with_nondebug_insn_uses : 1; |
229 | unsigned int m_is_pre_post_modify : 1; |
230 | unsigned int m_is_call_clobber : 1; |
231 | unsigned int m_is_live_out_use : 1; |
232 | unsigned int m_includes_address_uses : 1; |
233 | unsigned int m_includes_read_writes : 1; |
234 | unsigned int m_includes_subregs : 1; |
235 | unsigned int m_includes_multiregs : 1; |
236 | unsigned int m_only_occurs_in_notes : 1; |
237 | |
238 | // True if this access is a use_insn that occurs in a nondebug instruction, |
239 | // and if there are no following uses by nondebug instructions. The next use |
240 | // is null, a use_info for a debug instruction, or a use_info for a phi node. |
241 | // |
242 | // Providing this helps to optimize use_info::next_nondebug_insn_use. |
243 | unsigned int m_is_last_nondebug_insn_use : 1; |
244 | |
245 | // True if this access is a use_info for a debug instruction or |
246 | // a phi node. |
247 | unsigned int m_is_in_debug_insn_or_phi : 1; |
248 | |
249 | private: |
250 | // Used as a flag during various update routines; has no long-lasting |
251 | // meaning. |
252 | unsigned int m_has_been_superceded : 1; |
253 | |
254 | // Indicates that this access has been allocated on the function_info's |
255 | // temporary obstack and so is not (yet) part of the proper SSA form. |
256 | unsigned int m_is_temp : 1; |
257 | }; |
258 | |
259 | // A contiguous array of access_info pointers. Used to represent a |
260 | // (mostly small) number of definitions and/or uses. |
261 | using access_array = array_slice<access_info *const>; |
262 | |
263 | // A class for building an access_array on an obstack. It automatically |
264 | // frees any in-progress array if the build attempt fails before finish () |
265 | // has been called. |
266 | class access_array_builder : public obstack_watermark |
267 | { |
268 | public: |
269 | using obstack_watermark::obstack_watermark; |
270 | |
271 | // Make sure that the array has enough for NUM_ACCESSES accesses. |
272 | void reserve (unsigned int num_accesses); |
273 | |
274 | // Add ACCESS to the end of the array that we're building, given that |
275 | // reserve () has already made room. |
276 | void quick_push (access_info *access); |
277 | |
278 | // Finish and return the new array. The array survives the destruction |
279 | // of the builder. |
280 | array_slice<access_info *> finish (); |
281 | }; |
282 | |
283 | // An access_info that represents the use of a resource in either a phi node |
284 | // or an instruction. It records which set_info (if any) provides the |
285 | // resource's value. |
286 | class use_info : public access_info |
287 | { |
288 | // Overall size: 5 LP64 words. |
289 | friend class set_info; |
290 | friend class function_info; |
291 | |
292 | public: |
293 | // Return true if the access occurs in an instruction rather than a phi node. |
294 | // The instruction might be a debug instruction or a nondebug instruction. |
295 | bool is_in_any_insn () const { return m_insn_or_phi.is_first (); } |
296 | |
297 | // Return true if the access occurs in a nondebug instruction, |
298 | // false if it occurs in a debug instruction or a phi node. |
299 | bool is_in_nondebug_insn () const { return !m_is_in_debug_insn_or_phi; } |
300 | |
301 | // Return true if the instruction occurs in a debug instruction. |
302 | bool is_in_debug_insn () const; |
303 | |
304 | // Return true if the access occurs in a phi node rather than in an |
305 | // instruction. |
306 | bool is_in_phi () const { return m_insn_or_phi.is_second (); } |
307 | |
308 | // Return true if the access occurs in a debug instruction or a phi node, |
309 | // false if it occurs in a nondebug instruction. |
310 | bool is_in_debug_insn_or_phi () const { return m_is_in_debug_insn_or_phi; } |
311 | |
312 | // Return the instruction that uses the resource. Only valid is |
313 | // is_in_any_insn (). |
314 | insn_info *insn () const { return m_insn_or_phi.known_first (); } |
315 | |
316 | // Return the phi node that uses the resource. Only valid if is_in_phi (). |
317 | phi_info *phi () const { return m_insn_or_phi.known_second (); } |
318 | |
319 | // Return the basic block that contains the access. |
320 | bb_info *bb () const; |
321 | |
322 | // Return the extended basic block that contains the access. |
323 | ebb_info *ebb () const; |
324 | |
325 | // Return the set_info whose result the access uses, or null if the |
326 | // value of the resource is completely undefined. |
327 | // |
328 | // The value is undefined if the use is completely upwards exposed |
329 | // (i.e. has no preceding definition) or if the preceding definition |
330 | // is a clobber rather than a set. |
331 | // |
332 | // The mode of the definition can be different from the mode of the use; |
333 | // for example, a hard register might be set in DImode and used in SImode. |
334 | set_info *def () const { return m_def; } |
335 | |
336 | // Return the previous and next uses of the definition. See set_info |
337 | // for details about the ordering. |
338 | // |
339 | // These routines are only meaningful when def () is nonnull. |
340 | use_info *prev_use () const; |
341 | use_info *next_use () const; |
342 | |
343 | // Return the next use by a nondebug instruction, or null if none. |
344 | // |
345 | // This is only valid if is_in_nondebug_insn (). It is equivalent to, |
346 | // but more efficient than: |
347 | // |
348 | // next_use () && next_use ()->is_in_nondebug_insn () |
349 | // ? next_use () : nullptr |
350 | use_info *next_nondebug_insn_use () const; |
351 | |
352 | // Return the next use by an instruction, or null if none. The use might |
353 | // be by a debug instruction or a nondebug instruction. |
354 | // |
355 | // This is only valid if is_in_any_insn (). It is equivalent to: |
356 | // |
357 | // next_use () && next_use ()->is_in_any_insn () ? next_use () : nullptr |
358 | use_info *next_any_insn_use () const; |
359 | |
360 | // Return the next use by a debug instruction, or null if none. |
361 | // This is only valid if is_in_debug_insn (). |
362 | use_info *next_debug_insn_use () const; |
363 | |
364 | // Return the previous use by a phi node in the list, or null if none. |
365 | // |
366 | // This is only valid if is_in_phi (). It is equivalent to: |
367 | // |
368 | // prev_use () && prev_use ()->is_in_phi () ? prev_use () : nullptr |
369 | use_info *prev_phi_use () const; |
370 | |
371 | // Return true if this is the first use of the definition. See set_info |
372 | // for details about the ordering. |
373 | // |
374 | // This routine is only meaningful when def () is nonnull. |
375 | bool is_first_use () const; |
376 | |
377 | // Return true if this is the last use of the definition. See set_info |
378 | // for details about the ordering. |
379 | // |
380 | // This routine is only meaningful when def () is nonnull. |
381 | bool is_last_use () const; |
382 | |
383 | // Print a description of def () to PP. |
384 | void print_def (pretty_printer *pp) const; |
385 | |
386 | // Print a description of the location of the use to PP. |
387 | void print_location (pretty_printer *pp) const; |
388 | |
389 | // Print a description of the use to PP under the control of |
390 | // PP_ACCESS_* flags FLAGS. |
391 | void print (pretty_printer *pp, |
392 | unsigned int flags = PP_ACCESS_DEFAULT) const; |
393 | |
394 | private: |
395 | // If we only create a set_info splay tree for sets that are used by |
396 | // three instructions or more, then only about 16% of uses need to be in |
397 | // a splay tree. It is therefore more memory-efficient to use separate |
398 | // nodes for the splay tree, instead of storing the child nodes |
399 | // directly in the use_info. |
400 | |
401 | // Make insn_info the first (and thus directly-encoded) choice since |
402 | // insn () is read much more often than phi (). |
403 | using insn_or_phi = pointer_mux<insn_info, phi_info>; |
404 | |
405 | // The use belongs to a list that is partitioned into three sections: |
406 | // |
407 | // (1) all uses in nondebug instructions, in reverse postorder |
408 | // |
409 | // (2) all uses in debug instructions, in reverse postorder |
410 | // |
411 | // (3) all phi nodes, in no particular order. |
412 | // |
413 | // In order to preserve memory: |
414 | // |
415 | // - The set_info just has a pointer to the first use. |
416 | // |
417 | // - The first use's "prev" pointer points to the last use. |
418 | // |
419 | // - The last use's "next" pointer points to the last use in a nondebug |
420 | // instruction, or null if there are no such uses. |
421 | using last_use_or_prev_use = pointer_mux<use_info>; |
422 | using last_nondebug_insn_use_or_next_use = pointer_mux<use_info>; |
423 | |
424 | use_info (insn_or_phi, resource_info, set_info *); |
425 | |
426 | use_info *last_use () const; |
427 | use_info *last_nondebug_insn_use () const; |
428 | bool calculate_is_last_nondebug_insn_use () const; |
429 | |
430 | void record_reference (rtx_obj_reference, bool); |
431 | void set_insn (insn_info *); |
432 | void set_def (set_info *set) { m_def = set; } |
433 | void set_is_live_out_use (bool value) { m_is_live_out_use = value; } |
434 | void copy_prev_from (use_info *); |
435 | void copy_next_from (use_info *); |
436 | void set_last_use (use_info *); |
437 | void set_prev_use (use_info *); |
438 | void set_last_nondebug_insn_use (use_info *); |
439 | void set_next_use (use_info *); |
440 | void clear_use_links (); |
441 | bool has_use_links (); |
442 | bool check_integrity (); |
443 | |
444 | // The location of the use. |
445 | insn_or_phi m_insn_or_phi; |
446 | |
447 | // The overloaded "prev" and "next" pointers, as described above. |
448 | last_use_or_prev_use m_last_use_or_prev_use; |
449 | last_nondebug_insn_use_or_next_use m_last_nondebug_insn_use_or_next_use; |
450 | |
451 | // The value of def (). |
452 | set_info *m_def; |
453 | }; |
454 | |
455 | // Iterators for lists of uses. |
456 | using use_iterator = list_iterator<use_info, &use_info::next_use>; |
457 | using reverse_use_iterator = list_iterator<use_info, &use_info::prev_use>; |
458 | |
459 | // Like use_iterator, but specifically for uses by nondebug instructions, |
460 | // uses by any kind of instruction, and uses by phi nodes respectively. |
461 | // These iterators allow a nullptr end point even if there are other types |
462 | // of use in the same definition. |
463 | using nondebug_insn_use_iterator |
464 | = list_iterator<use_info, &use_info::next_nondebug_insn_use>; |
465 | using debug_insn_use_iterator |
466 | = list_iterator<use_info, &use_info::next_debug_insn_use>; |
467 | using any_insn_use_iterator |
468 | = list_iterator<use_info, &use_info::next_any_insn_use>; |
469 | using phi_use_iterator = list_iterator<use_info, &use_info::prev_phi_use>; |
470 | |
471 | // A view of an access_array in which every entry is known to be a use_info. |
472 | using use_array = const_derived_container<use_info *, access_array>; |
473 | |
474 | // An access_info that describes a definition of a resource. The definition |
475 | // can be a set or a clobber; the difference is that a set provides a known |
476 | // and potentially useful value, while a clobber provides an unknown and |
477 | // unusable value. |
478 | // |
479 | // Every definition is associated with an insn_info. All definitions of |
480 | // a given resource are stored in a linked list, maintained in reverse |
481 | // postorder. |
482 | class def_info : public access_info |
483 | { |
484 | // Overall size: 4 LP64 words |
485 | friend class function_info; |
486 | friend class clobber_group; |
487 | |
488 | public: |
489 | // Return the instruction that contains the definition. |
490 | insn_info *insn () const { return m_insn; } |
491 | |
492 | // Return the basic block that contains the definition. |
493 | bb_info *bb () const; |
494 | |
495 | // Return the extended basic block that contains the access. |
496 | ebb_info *ebb () const; |
497 | |
498 | // Return the previous and next definitions of the same resource, |
499 | // in reverse postorder, or null if no such definition exists. |
500 | def_info *prev_def () const; |
501 | def_info *next_def () const; |
502 | |
503 | // Return true if this is the first definition in the list. |
504 | bool is_first_def () const; |
505 | |
506 | // Return true if this is the last definition in the list. |
507 | bool is_last_def () const; |
508 | |
509 | // Print the location of the definition to PP. |
510 | void print_location (pretty_printer *pp) const; |
511 | |
512 | // Print a unique identifier for this definition to PP. The identifier has |
513 | // the form <resource>:<insn uid>. |
514 | void print_identifier (pretty_printer *pp) const; |
515 | |
516 | protected: |
517 | def_info (insn_info *insn, resource_info resource, access_kind kind); |
518 | |
519 | private: |
520 | // In order to preserve memory, the list head only points to the first |
521 | // definition in the list. The "prev" entry of the first definition |
522 | // then points to the last definition. |
523 | using last_def_or_prev_def = pointer_mux<def_info>; |
524 | |
525 | // For similar memory-saving reasons, if we want to create a splay tree |
526 | // of accesses to a resource, we hang the root off the "next" entry of |
527 | // the last definition in the list. |
528 | using splay_root_or_next_def = pointer_mux<def_node, def_info>; |
529 | |
530 | void set_insn (insn_info *insn) { m_insn = insn; } |
531 | |
532 | def_info *last_def () const; |
533 | def_node *splay_root () const; |
534 | |
535 | void record_reference (rtx_obj_reference, bool); |
536 | void copy_prev_from (def_info *); |
537 | void copy_next_from (def_info *); |
538 | void set_last_def (def_info *); |
539 | void set_prev_def (def_info *); |
540 | void set_splay_root (def_node *); |
541 | void set_next_def (def_info *); |
542 | void clear_def_links (); |
543 | bool has_def_links (); |
544 | |
545 | // The location of the definition. |
546 | insn_info *m_insn; |
547 | |
548 | // The overloaded "prev" and "next" pointers, as described above. |
549 | last_def_or_prev_def m_last_def_or_prev_def; |
550 | splay_root_or_next_def m_splay_root_or_next_def; |
551 | }; |
552 | |
553 | // Iterators for lists of definitions. |
554 | using def_iterator = list_iterator<def_info, &def_info::next_def>; |
555 | using reverse_def_iterator = list_iterator<def_info, &def_info::prev_def>; |
556 | |
557 | // A view of an access_array in which every entry is known to be a |
558 | // def_info. |
559 | using def_array = const_derived_container<def_info *, access_array>; |
560 | |
561 | // A def_info that sets the resource to a value that is both |
562 | // unknown and not useful. This is only ever used for registers, |
563 | // since memory always has some useful contents. |
564 | // |
565 | // Neighboring clobbers are grouped into clobber_groups, so that it's |
566 | // possibly to skip over all neighboring clobbers in a single step. |
567 | class clobber_info : public def_info |
568 | { |
569 | // Overall size: 8 LP64 words |
570 | friend class default_splay_tree_accessors<clobber_info *>; |
571 | friend class default_splay_tree_accessors_with_parent<clobber_info *>; |
572 | friend class function_info; |
573 | friend class clobber_group; |
574 | |
575 | public: |
576 | using splay_tree = default_rootless_splay_tree<clobber_info *>; |
577 | |
578 | // Return true if the clobber belongs to a clobber_group, false if it |
579 | // is standalone. |
580 | bool is_in_group () const { return m_group; } |
581 | |
582 | // Return the group that the clobber is in, or null if none. |
583 | // |
584 | // Complexity: amortized O(1), worst case O(N), where N is the number |
585 | // of clobbers in the containing clobber_group. |
586 | clobber_group *group () const; |
587 | |
588 | // Print a description of the clobber to PP under the control of |
589 | // PP_ACCESS_* flags FLAGS. |
590 | void print (pretty_printer *pp, |
591 | unsigned int flags = PP_ACCESS_DEFAULT) const; |
592 | |
593 | private: |
594 | // Once normal call clobbers are taken out of the equation by |
595 | // insn_call_clobbers_notes, clobber_infos account for roughly 6% of all |
596 | // def_infos, with the rest being set_infos. clobber_infos are |
597 | // therefore much less size-sensitive than set_infos are. |
598 | // |
599 | // As noted above, we want to group neighboring clobbers together so that |
600 | // we can quickly step over them to find the previous or next "real" set. |
601 | // We also want to be able to split the group in sublinear time, |
602 | // for example when inserting a set/use pair between two clobbers |
603 | // in a group. |
604 | // |
605 | // So: |
606 | // |
607 | // - Clobbers need to have ready access to their group, so that we |
608 | // can cheaply skip over the whole group. This means that they |
609 | // need a group pointer. |
610 | // |
611 | // - We need to be able to update the group pointer lazily, so that |
612 | // the cost of updating it is counted against accesses to the clobbers |
613 | // that need updating. |
614 | // |
615 | // We also want to be able to insert clobbers into a group in |
616 | // amortized logarithmic time. |
617 | // |
618 | // We therefore use a splay tree to represent the clobbers in a group, |
619 | // with the nodes storing their parent node. It is then possible to |
620 | // perform splay operations without first getting hold of the root. |
621 | // The root of the splay tree always has a valid, up-to-date group, |
622 | // so lazy group updates can get the new group from there. |
623 | // |
624 | // Roughly 90% of clobbers have a neighboring definition in the same |
625 | // block, which means that most need to be stored in a splay tree. |
626 | // We therefore store the splay tree fields directly in the clobber_info |
627 | // rather than using a separate node object. |
628 | |
629 | clobber_info (insn_info *, unsigned int); |
630 | |
631 | void set_group (clobber_group *group) { m_group = group; } |
632 | void update_group (clobber_group *); |
633 | clobber_group *recompute_group (); |
634 | |
635 | // The child and parent nodes in the splay tree. |
636 | clobber_info *m_children[2]; |
637 | clobber_info *m_parent; |
638 | |
639 | // The last known value of group (), which might now be out of date. |
640 | clobber_group *m_group; |
641 | }; |
642 | |
643 | using clobber_tree = clobber_info::splay_tree::rooted; |
644 | |
645 | // A def_info that sets the resource to a useful value. It records |
646 | // all uses of the value in a linked list. The list is partitioned |
647 | // into three sections: |
648 | // |
649 | // (1) all uses by nondebug instructions, in reverse postorder, followed by |
650 | // (2) all uses by debug instructions, in reverse postorder, followed by |
651 | // (3) all uses by phi nodes, in no particular order. |
652 | // |
653 | // There are two cases: |
654 | // |
655 | // - If we know in advance that there is a single definition of a resource R |
656 | // and therefore decide not to use phi nodes for R, (1) and (2) contain |
657 | // all uses of R, regardless of which blocks contain the uses. (3) is |
658 | // then empty. |
659 | // |
660 | // - Otherwise, (1) only contains uses in the same extended basic block |
661 | // as the definition, and it is terminated by a use that marks the end |
662 | // of the live range for the EBB. In other words, if the resource dies |
663 | // in the EBB, the last use by a nondebug instruction marks the point at |
664 | // which it dies, otherwise there is a fake live-out use at the end of |
665 | // the EBB. |
666 | // |
667 | // Since debug instructions should not affect codegen, they opportunisticly |
668 | // attach to the same set_info as nondebug instructions where possible. |
669 | // If a nondebug instruction would attach to a degenerate phi and if no |
670 | // such phi exists, debug instructions instead attach to whichever set_info |
671 | // provides the value, regardless of where that set_info is. |
672 | class set_info : public def_info |
673 | { |
674 | // Overall size: 6 LP64 words. |
675 | friend class function_info; |
676 | using use_splay_tree = splay_tree<use_info *>; |
677 | |
678 | public: |
679 | // Return the first and last uses of the set, or null if the list is empty. |
680 | // See the comment above for details about the order. |
681 | use_info *first_use () const { return m_first_use; } |
682 | use_info *last_use () const; |
683 | |
684 | // Return the first and last uses of the set by nondebug instructions, |
685 | // or null if there are no such uses. The uses are in reverse postorder. |
686 | use_info *first_nondebug_insn_use () const; |
687 | use_info *last_nondebug_insn_use () const; |
688 | |
689 | // Return the first use of the set by debug instructions, or null if |
690 | // there is no such use. |
691 | use_info *first_debug_insn_use () const; |
692 | |
693 | // Return the first use of the set by any kind of instruction, or null |
694 | // if there are no such uses. The uses are in the order described above. |
695 | use_info *first_any_insn_use () const; |
696 | |
697 | // Return the last use of the set by phi inputs, or null if there are no |
698 | // such uses. The phi input uses are in no particular order. |
699 | use_info *last_phi_use () const; |
700 | |
701 | // Return true if at least one nondebug instruction or phi node uses |
702 | // the set's result. This is equivalent to testing whether the set is |
703 | // ever live. |
704 | bool has_nondebug_uses () const; |
705 | |
706 | // Return true if anything uses the set's result. Note that this includes |
707 | // uses by debug instructions, so it should not be used for optimization |
708 | // decisions. |
709 | bool has_any_uses () const { return m_first_use; } |
710 | |
711 | // Return true if at least one nondebug instruction uses the set's result. |
712 | bool has_nondebug_insn_uses () const; |
713 | |
714 | // Return true if at least one phi node uses the set's result. |
715 | bool has_phi_uses () const; |
716 | |
717 | // If there is exactly one nondebug use of the set's result, return that use, |
718 | // otherwise return null. The use might be in an instruction or in a phi |
719 | // node. |
720 | use_info *single_nondebug_use () const; |
721 | |
722 | // If exactly one nondebug instruction uses the set's result, return the use |
723 | // by that instruction, otherwise return null. |
724 | use_info *single_nondebug_insn_use () const; |
725 | |
726 | // If exactly one phi node uses the set's result, return the use by that phi |
727 | // node, otherwise return null. |
728 | use_info *single_phi_use () const; |
729 | |
730 | // Return true if the set and its uses are contained within a single |
731 | // extended basic block, with the set coming first. This implies |
732 | // that all uses are by instructions rather than phi nodes. |
733 | bool is_local_to_ebb () const; |
734 | |
735 | // List all the uses of the set, in the order described above. |
736 | iterator_range<use_iterator> all_uses () const; |
737 | |
738 | // Return uses () in reverse order. |
739 | iterator_range<reverse_use_iterator> reverse_all_uses () const; |
740 | |
741 | // List the uses of the set by nondebug instructions, in reverse postorder. |
742 | iterator_range<nondebug_insn_use_iterator> nondebug_insn_uses () const; |
743 | |
744 | // List the uses of the set by debug instructions, in reverse postorder. |
745 | iterator_range<debug_insn_use_iterator> debug_insn_uses () const; |
746 | |
747 | // Return nondebug_insn_uses () in reverse order. |
748 | iterator_range<reverse_use_iterator> reverse_nondebug_insn_uses () const; |
749 | |
750 | // List the uses of the set by any kind of instruction. The list follows |
751 | // the order described above. |
752 | iterator_range<any_insn_use_iterator> all_insn_uses () const; |
753 | |
754 | // List the uses of the set by phi nodes, in no particular order. |
755 | // There is therefore no reversed equivalent of this list. |
756 | iterator_range<phi_use_iterator> phi_uses () const; |
757 | |
758 | // Print a description of the set to PP under the control of |
759 | // PP_ACCESS_* flags FLAGS. |
760 | void print (pretty_printer *pp, |
761 | unsigned int flags = PP_ACCESS_DEFAULT) const; |
762 | |
763 | protected: |
764 | set_info (insn_info *, resource_info, access_kind); |
765 | |
766 | // Print information about uses () to PP, continuing information printed |
767 | // about the set itself. |
768 | void print_uses_on_new_lines (pretty_printer *pp) const; |
769 | |
770 | private: |
771 | // Sets (including phis) account for about 94% of all definitions |
772 | |
773 | set_info (insn_info *, resource_info); |
774 | |
775 | void set_first_use (use_info *); |
776 | |
777 | // The first use in the list. |
778 | use_info *m_first_use; |
779 | |
780 | // The root of a splay tree of all uses, built lazily when we first |
781 | // think it's needed. |
782 | use_splay_tree m_use_tree; |
783 | }; |
784 | |
785 | // A set_info for an on-the-side phi node. The phi node is attached |
786 | // to an extended basic block EBB and has one input for each incoming edge. |
787 | // The inputs are represented as an array of use_infos, with input I |
788 | // corresponding to EDGE_PRED (EBB->first_bb ()->cfg_bb (), I). |
789 | // |
790 | // Each phi node has a densely-allocated unique identifier, which is intended |
791 | // to be suitable for bitmaps or sbitmaps. |
792 | // |
793 | // All the phi nodes in an extended basic block are chained together |
794 | // into a linked list. The list has no particular order. |
795 | class phi_info : public set_info |
796 | { |
797 | // Overall size: 8 LP64 words |
798 | friend class function_info; |
799 | |
800 | public: |
801 | // Return the previous and next phi nodes in the extended basic block's list, |
802 | // or null if none. |
803 | phi_info *prev_phi () const { return m_prev_phi; } |
804 | phi_info *next_phi () const { return m_next_phi; } |
805 | |
806 | // Return the number of phi inputs. This is 1 for degenerate phis, |
807 | // otherwise it is equal to the number of incoming edges. |
808 | unsigned int num_inputs () const { return m_num_inputs; } |
809 | |
810 | // Return true if the phi node is degenerate, i.e. if it has only a |
811 | // single input. |
812 | bool is_degenerate () const { return m_num_inputs == 1; } |
813 | |
814 | // Return the phi node's unique identifier. |
815 | unsigned int uid () const { return m_uid; } |
816 | |
817 | // Return the array of inputs. For degenerate phi nodes, this array contains |
818 | // a single element, otherwise it has one input per incoming edge, |
819 | // with element E corresponding to incoming edge E. |
820 | use_array inputs () const; |
821 | |
822 | // Return the use_info that describes the phi input for incoming edge E. |
823 | use_info *input_use (unsigned int e) const; |
824 | |
825 | // Return the value of resource () on incoming edge E, or null if the |
826 | // value is completely undefined for that edge. |
827 | set_info *input_value (unsigned int e) const; |
828 | |
829 | // Print a description of the phi node to PP under the control of |
830 | // PP_ACCESS_* flags FLAGS. |
831 | void print (pretty_printer *pp, |
832 | unsigned int flags = PP_ACCESS_DEFAULT) const; |
833 | |
834 | private: |
835 | phi_info (insn_info *insn, resource_info resource, unsigned int uid); |
836 | |
837 | void make_degenerate (use_info *); |
838 | void set_inputs (use_array inputs); |
839 | void set_prev_phi (phi_info *prev_phi) { m_prev_phi = prev_phi; } |
840 | void set_next_phi (phi_info *next_phi) { m_next_phi = next_phi; } |
841 | void clear_phi_links () { m_prev_phi = m_next_phi = nullptr; } |
842 | bool has_phi_links () { return m_prev_phi || m_next_phi; } |
843 | |
844 | // The values returned by the accessors above. |
845 | unsigned int m_uid; |
846 | unsigned int m_num_inputs; |
847 | union |
848 | { |
849 | access_info *const *m_inputs; |
850 | access_info *m_single_input; |
851 | }; |
852 | phi_info *m_prev_phi; |
853 | phi_info *m_next_phi; |
854 | }; |
855 | |
856 | // An iterator for lists of phi nodes. |
857 | using phi_iterator = list_iterator<phi_info, &phi_info::next_phi>; |
858 | |
859 | // One node in a splay tree of definitions. This base class represents |
860 | // a single def_info, but it is structured to allow derived classes |
861 | // to add a range. |
862 | class def_node |
863 | { |
864 | // Size: 3 LP64 words. |
865 | friend class function_info; |
866 | friend class default_splay_tree_accessors<def_node *>; |
867 | |
868 | public: |
869 | // Return the first definition that the node represents. |
870 | def_info *first_def () const; |
871 | |
872 | // Return which type of access first_def () is. |
873 | bool contains_clobber () const { return m_clobber_or_set.is_first (); } |
874 | bool contains_set () const { return m_clobber_or_set.is_second (); } |
875 | |
876 | protected: |
877 | // More nodes are clobbers rather than sets, so put clobbers first. |
878 | // Neither choice can be null. |
879 | using clobber_or_set = pointer_mux<clobber_info, set_info>; |
880 | |
881 | // Construct a node that represents FIRST_DEF (and possibly later |
882 | // definitions too, if called from a derived class). |
883 | def_node (clobber_or_set first_def); |
884 | |
885 | // The first definition in the node. |
886 | clobber_or_set m_clobber_or_set; |
887 | |
888 | private: |
889 | // The splay tree child nodes. |
890 | def_node *m_children[2]; |
891 | }; |
892 | |
893 | // One node in a splay tree of def_infos, representing a single set_info. |
894 | class set_node : public def_node |
895 | { |
896 | // Overall size: 3 LP64 words. |
897 | friend class function_info; |
898 | |
899 | public: |
900 | // Return the set that the node contains. |
901 | set_info *set () const { return m_clobber_or_set.known_second (); } |
902 | |
903 | // Print a description of the node to PP. |
904 | void print (pretty_printer *pp) const; |
905 | |
906 | private: |
907 | // Construct a node for SET. |
908 | set_node (set_info *set) : def_node (set) {} |
909 | }; |
910 | |
911 | // One node in a splay tree of def_infos. This class represents |
912 | // a list of contiguous clobber_infos, in execution order. |
913 | class clobber_group : public def_node |
914 | { |
915 | // Overall size: 5 LP64 words. |
916 | friend class function_info; |
917 | |
918 | public: |
919 | // Return the first and last clobbers in the group. The results are |
920 | // always nonnull. |
921 | clobber_info *first_clobber () const; |
922 | clobber_info *last_clobber () const { return m_last_clobber; } |
923 | |
924 | // Return the last clobber before INSN in the group, or null if none. |
925 | clobber_info *prev_clobber (insn_info *insn) const; |
926 | |
927 | // Return the next clobber after INSN in the group, or null if none. |
928 | clobber_info *next_clobber (insn_info *insn) const; |
929 | |
930 | // Return true if this group has been replaced by new clobber_groups. |
931 | bool has_been_superceded () const { return !m_last_clobber; } |
932 | |
933 | // Return a list of the clobbers in the group, in execution order. |
934 | iterator_range<def_iterator> clobbers () const; |
935 | |
936 | // Print a description of the group to PP. |
937 | void print (pretty_printer *pp) const; |
938 | |
939 | private: |
940 | clobber_group (clobber_info *clobber); |
941 | |
942 | // Set the values of first_clobber () and last_clobber (). |
943 | void set_first_clobber (clobber_info *c) { m_clobber_or_set = c; } |
944 | void set_last_clobber (clobber_info *c) { m_last_clobber = c; } |
945 | |
946 | // The value returned by last_clobber (). |
947 | clobber_info *m_last_clobber; |
948 | |
949 | // A splay tree that contains all the clobbers in the group. |
950 | // The root of the splay tree always has an up-to-date group |
951 | // pointer, but the other clobbers in the tree might not. |
952 | clobber_tree m_clobber_tree; |
953 | }; |
954 | |
955 | // A splay tree in which one node represents a standalone set_info or a |
956 | // range of consecutive clobber_infos. The nodes follow execution order |
957 | // and maintain the invariant that no two groups of clobber_infos appear |
958 | // next to each other (instead, the groups are merged). |
959 | using def_splay_tree = default_splay_tree<def_node *>; |
960 | |
961 | // This type represents a choice between: |
962 | // |
963 | // (1) a single definition of a resource |
964 | // (2) a node in a def_splay_tree that represents either a single |
965 | // set or a group of clobbers. |
966 | class def_mux : public pointer_mux<def_info, def_node> |
967 | { |
968 | using parent = pointer_mux<def_info, def_node>; |
969 | |
970 | // Provide the same constructors as the pointer_mux. |
971 | using parent::parent; |
972 | |
973 | public: |
974 | // Return the first definition associated with this mux. If the mux holds |
975 | // a single definition, the result is that definition. If the mux holds |
976 | // a clobber_group, the result is the first clobber in the group. |
977 | def_info *first_def () const; |
978 | |
979 | // Return the last definition associated with this mux. If the mux holds |
980 | // a single definition, the result is that definition. If the mux holds |
981 | // a clobber_group, the result is the last clobber in the group. |
982 | def_info *last_def () const; |
983 | |
984 | // If the pointer represents a set_info, return that set_info, |
985 | // otherwise return null. |
986 | set_info *set () const; |
987 | }; |
988 | |
989 | // This class represents the result of looking up the definition of a |
990 | // resource at a particular point, here referred to as point P. |
991 | // There are four states: |
992 | // |
993 | // - MUX is null if there were no definitions to search. |
994 | // |
995 | // - Otherwise, COMPARISON is 0 if we found a definition at P or a |
996 | // clobber_group that spans P. MUX then contains this definition |
997 | // or clobber_group. |
998 | // |
999 | // - Otherwise, COMPARISON is greater than 0 if we found the definition |
1000 | // that precedes P or the group of clobbers that precedes P. MUX then |
1001 | // contains this definition or clobber_group. |
1002 | // |
1003 | // - Otherwise, COMPARISON is less than zero and we found the definition |
1004 | // that follows P, or the group of clobbers that follows P. MUX then |
1005 | // contains this definition or clobber_group. |
1006 | class def_lookup |
1007 | { |
1008 | public: |
1009 | // If we found a clobber_group that spans P, return the definition |
1010 | // that precedes the start of the group, or null if none. |
1011 | // |
1012 | // Otherwise, return the last definition that occurs before P, |
1013 | // or null if none. |
1014 | def_info *last_def_of_prev_group () const; |
1015 | |
1016 | // If we found a clobber_group that spans P, return the definition |
1017 | // that follows the end of the group, or null if none. |
1018 | // |
1019 | // Otherwise, return the first definition that occurs after P, |
1020 | // or null if none. |
1021 | def_info *first_def_of_next_group () const; |
1022 | |
1023 | // If we found a set_info at P, return that set_info, otherwise return null. |
1024 | set_info *matching_set () const; |
1025 | |
1026 | // If we found a set_info at P, return that set_info, otherwise return |
1027 | // prev_def (). |
1028 | def_info *matching_set_or_last_def_of_prev_group () const; |
1029 | |
1030 | // If we found a set_info at P, return that set_info, otherwise return |
1031 | // next_def (). |
1032 | def_info *matching_set_or_first_def_of_next_group () const; |
1033 | |
1034 | // P is the location of INSN. Return the last definition (of any kind) |
1035 | // that occurs before INSN, or null if none. |
1036 | def_info *prev_def (insn_info *insn) const; |
1037 | |
1038 | // P is the location of INSN. Return the next definition (of any kind) |
1039 | // that occurs after INSN, or null if none. |
1040 | def_info *next_def (insn_info *insn) const; |
1041 | |
1042 | def_mux mux; |
1043 | int comparison; |
1044 | }; |
1045 | |
1046 | void pp_resource (pretty_printer *, resource_info); |
1047 | void pp_access (pretty_printer *, const access_info *, |
1048 | unsigned int flags = PP_ACCESS_DEFAULT); |
1049 | void pp_accesses (pretty_printer *, access_array, |
1050 | unsigned int flags = PP_ACCESS_DEFAULT); |
1051 | void pp_def_node (pretty_printer *, const def_node *); |
1052 | void pp_def_mux (pretty_printer *, def_mux); |
1053 | void pp_def_lookup (pretty_printer *, def_lookup); |
1054 | |
1055 | } |
1056 | |
1057 | void dump (FILE *, rtl_ssa::resource_info); |
1058 | void dump (FILE *, const rtl_ssa::access_info *, |
1059 | unsigned int flags = rtl_ssa::PP_ACCESS_DEFAULT); |
1060 | void dump (FILE *, rtl_ssa::access_array, |
1061 | unsigned int flags = rtl_ssa::PP_ACCESS_DEFAULT); |
1062 | void dump (FILE *, const rtl_ssa::def_node *); |
1063 | void dump (FILE *, rtl_ssa::def_mux); |
1064 | void dump (FILE *, rtl_ssa::def_lookup); |
1065 | |
1066 | void DEBUG_FUNCTION debug (const rtl_ssa::resource_info *); |
1067 | void DEBUG_FUNCTION debug (const rtl_ssa::access_info *); |
1068 | void DEBUG_FUNCTION debug (const rtl_ssa::access_array); |
1069 | void DEBUG_FUNCTION debug (const rtl_ssa::def_node *); |
1070 | void DEBUG_FUNCTION debug (const rtl_ssa::def_mux &); |
1071 | void DEBUG_FUNCTION debug (const rtl_ssa::def_lookup &); |
1072 | |