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
20namespace rtl_ssa {
21
22// Forward declarations.
23class bb_info;
24class clobber_group;
25class def_node;
26class ebb_info;
27class insn_info;
28class phi_info;
29class set_info;
30
31// Used as a boolean argunent to certain routines.
32enum class ignore_clobbers { NO, YES };
33
34// Represents something that the SSA form tracks: either a register
35// or memory.
36class resource_info
37{
38public:
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.
66const 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.
73const 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.
77const unsigned int PP_ACCESS_INCLUDE_LINKS = 1U << 1;
78//
79// Print additional properties about the access.
80const unsigned int PP_ACCESS_INCLUDE_PROPERTIES = 1U << 2;
81//
82// The usual flags when printing an access in isolation.
83const 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.
88const 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.
92const 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.
98enum 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.
115class access_info
116{
117 // Size: 1 LP64 word
118 friend class function_info;
119
120public:
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
211protected:
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
217private:
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
225protected:
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
249private:
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.
261using 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.
266class access_array_builder : public obstack_watermark
267{
268public:
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.
286class use_info : public access_info
287{
288 // Overall size: 5 LP64 words.
289 friend class set_info;
290 friend class function_info;
291
292public:
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
394private:
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.
456using use_iterator = list_iterator<use_info, &use_info::next_use>;
457using 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.
463using nondebug_insn_use_iterator
464 = list_iterator<use_info, &use_info::next_nondebug_insn_use>;
465using debug_insn_use_iterator
466 = list_iterator<use_info, &use_info::next_debug_insn_use>;
467using any_insn_use_iterator
468 = list_iterator<use_info, &use_info::next_any_insn_use>;
469using 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.
472using 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.
482class def_info : public access_info
483{
484 // Overall size: 4 LP64 words
485 friend class function_info;
486 friend class clobber_group;
487
488public:
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
516protected:
517 def_info (insn_info *insn, resource_info resource, access_kind kind);
518
519private:
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.
554using def_iterator = list_iterator<def_info, &def_info::next_def>;
555using 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.
559using 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.
567class 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
575public:
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
593private:
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
643using 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.
672class 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
678public:
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
763protected:
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
770private:
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.
795class phi_info : public set_info
796{
797 // Overall size: 8 LP64 words
798 friend class function_info;
799
800public:
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
834private:
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.
857using 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.
862class def_node
863{
864 // Size: 3 LP64 words.
865 friend class function_info;
866 friend class default_splay_tree_accessors<def_node *>;
867
868public:
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
876protected:
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
888private:
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.
894class set_node : public def_node
895{
896 // Overall size: 3 LP64 words.
897 friend class function_info;
898
899public:
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
906private:
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.
913class clobber_group : public def_node
914{
915 // Overall size: 5 LP64 words.
916 friend class function_info;
917
918public:
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
939private:
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).
959using 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.
966class 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
973public:
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.
1006class def_lookup
1007{
1008public:
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
1046void pp_resource (pretty_printer *, resource_info);
1047void pp_access (pretty_printer *, const access_info *,
1048 unsigned int flags = PP_ACCESS_DEFAULT);
1049void pp_accesses (pretty_printer *, access_array,
1050 unsigned int flags = PP_ACCESS_DEFAULT);
1051void pp_def_node (pretty_printer *, const def_node *);
1052void pp_def_mux (pretty_printer *, def_mux);
1053void pp_def_lookup (pretty_printer *, def_lookup);
1054
1055}
1056
1057void dump (FILE *, rtl_ssa::resource_info);
1058void dump (FILE *, const rtl_ssa::access_info *,
1059 unsigned int flags = rtl_ssa::PP_ACCESS_DEFAULT);
1060void dump (FILE *, rtl_ssa::access_array,
1061 unsigned int flags = rtl_ssa::PP_ACCESS_DEFAULT);
1062void dump (FILE *, const rtl_ssa::def_node *);
1063void dump (FILE *, rtl_ssa::def_mux);
1064void dump (FILE *, rtl_ssa::def_lookup);
1065
1066void DEBUG_FUNCTION debug (const rtl_ssa::resource_info *);
1067void DEBUG_FUNCTION debug (const rtl_ssa::access_info *);
1068void DEBUG_FUNCTION debug (const rtl_ssa::access_array);
1069void DEBUG_FUNCTION debug (const rtl_ssa::def_node *);
1070void DEBUG_FUNCTION debug (const rtl_ssa::def_mux &);
1071void DEBUG_FUNCTION debug (const rtl_ssa::def_lookup &);
1072

source code of gcc/rtl-ssa/accesses.h