1 // Access-related classes for RTL SSA -*- C++ -*-
2 // Copyright (C) 2020-2024 Free Software Foundation, Inc.
4 // This file is part of GCC.
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
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
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/>.
22 // Forward declarations.
31 // Used as a boolean argunent to certain routines.
32 enum class ignore_clobbers
{ NO
, YES
};
34 // Represents something that the SSA form tracks: either a register
39 // Return true if this resource represents memory.
40 bool is_mem () const { return regno
== MEM_REGNO
; }
42 // Return true if this resource represents a register.
43 bool is_reg () const { return regno
!= MEM_REGNO
; }
45 // Print the name of the resource to PP.
46 void print_identifier (pretty_printer
*pp
) const;
48 // Possibly print additional information about the resource to PP.
49 void print_context (pretty_printer
*pp
) const;
51 // A combination of print_identifier and print_context.
52 void print (pretty_printer
*pp
) const;
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
60 // The pseudo register or single hard register that the resource represents,
61 // or MEM_REGNO for memory.
65 // For simplicity, we treat memory as a single unified entity.
66 const resource_info memory
= { E_BLKmode
, MEM_REGNO
};
68 // Flags used when printing access_infos.
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;
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;
79 // Print additional properties about the access.
80 const unsigned int PP_ACCESS_INCLUDE_PROPERTIES
= 1U << 2;
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
);
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
);
91 // The usual flags when printing a use_info from its user.
92 const unsigned int PP_ACCESS_USER
= PP_ACCESS_INCLUDE_PROPERTIES
;
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
100 // Set the resource to a useful value.
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.
107 // Set the resource to a value that is both unknown and not useful.
110 // Use the current value of the resource.
114 // A base class that represents an access to a resource.
118 friend class function_info
;
121 // Return the resource that is being accessed.
122 resource_info
resource () const { return { m_mode
, m_regno
}; }
124 // Return true if the access is to memory.
125 bool is_mem () const { return m_regno
== MEM_REGNO
; }
127 // Return true if the access is to a register.
128 bool is_reg () const { return m_regno
!= MEM_REGNO
; }
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
; }
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
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
; }
144 // Return the kind of access that this is.
145 access_kind
kind () const { return m_kind
; }
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
; }
151 // Return the opposite of is_artificial.
152 bool is_real () const { return !m_is_artificial
; }
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;
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
; }
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
; }
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
; }
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.
175 // There shouldn't be a need to check whether *all* uses occur within
176 // a MEM address, since in principle:
178 // A: (set (reg:SI R1) (mem:SI (post_inc:SI (reg:SI R2))))
180 // should be semantically equivalent to:
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)))])
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
; }
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
; }
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
; }
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
; }
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
; }
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
; }
212 access_info (resource_info
, access_kind
);
214 void print_prefix_flags (pretty_printer
*) const;
215 void print_properties_on_new_lines (pretty_printer
*) const;
218 void set_mode (machine_mode mode
) { m_mode
= mode
; }
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;
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;
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.
242 // Providing this helps to optimize use_info::next_nondebug_insn_use.
243 unsigned int m_is_last_nondebug_insn_use
: 1;
245 // True if this access is a use_info for a debug instruction or
247 unsigned int m_is_in_debug_insn_or_phi
: 1;
250 // Used as a flag during various update routines; has no long-lasting
252 unsigned int m_has_been_superceded
: 1;
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;
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>;
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 ()
266 class access_array_builder
: public obstack_watermark
269 using obstack_watermark::obstack_watermark
;
271 // Make sure that the array has enough for NUM_ACCESSES accesses.
272 void reserve (unsigned int num_accesses
);
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
);
278 // Finish and return the new array. The array survives the destruction
280 array_slice
<access_info
*> finish ();
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
286 class use_info
: public access_info
288 // Overall size: 5 LP64 words.
289 friend class set_info
;
290 friend class function_info
;
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 (); }
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
; }
301 // Return true if the instruction occurs in a debug instruction.
302 bool is_in_debug_insn () const;
304 // Return true if the access occurs in a phi node rather than in an
306 bool is_in_phi () const { return m_insn_or_phi
.is_second (); }
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
; }
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 (); }
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 (); }
319 // Return the basic block that contains the access.
320 bb_info
*bb () const;
322 // Return the extended basic block that contains the access.
323 ebb_info
*ebb () const;
325 // Return the set_info whose result the access uses, or null if the
326 // value of the resource is completely undefined.
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.
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
; }
336 // Return the previous and next uses of the definition. See set_info
337 // for details about the ordering.
339 // These routines are only meaningful when def () is nonnull.
340 use_info
*prev_use () const;
341 use_info
*next_use () const;
343 // Return the next use by a nondebug instruction, or null if none.
345 // This is only valid if is_in_nondebug_insn (). It is equivalent to,
346 // but more efficient than:
348 // next_use () && next_use ()->is_in_nondebug_insn ()
349 // ? next_use () : nullptr
350 use_info
*next_nondebug_insn_use () const;
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.
355 // This is only valid if is_in_any_insn (). It is equivalent to:
357 // next_use () && next_use ()->is_in_any_insn () ? next_use () : nullptr
358 use_info
*next_any_insn_use () const;
360 // Return the previous use by a phi node in the list, or null if none.
362 // This is only valid if is_in_phi (). It is equivalent to:
364 // prev_use () && prev_use ()->is_in_phi () ? prev_use () : nullptr
365 use_info
*prev_phi_use () const;
367 // Return true if this is the first use of the definition. See set_info
368 // for details about the ordering.
370 // This routine is only meaningful when def () is nonnull.
371 bool is_first_use () const;
373 // Return true if this is the last use of the definition. See set_info
374 // for details about the ordering.
376 // This routine is only meaningful when def () is nonnull.
377 bool is_last_use () const;
379 // Print a description of def () to PP.
380 void print_def (pretty_printer
*pp
) const;
382 // Print a description of the location of the use to PP.
383 void print_location (pretty_printer
*pp
) const;
385 // Print a description of the use to PP under the control of
386 // PP_ACCESS_* flags FLAGS.
387 void print (pretty_printer
*pp
,
388 unsigned int flags
= PP_ACCESS_DEFAULT
) const;
391 // If we only create a set_info splay tree for sets that are used by
392 // three instructions or more, then only about 16% of uses need to be in
393 // a splay tree. It is therefore more memory-efficient to use separate
394 // nodes for the splay tree, instead of storing the child nodes
395 // directly in the use_info.
397 // Make insn_info the first (and thus directly-encoded) choice since
398 // insn () is read much more often than phi ().
399 using insn_or_phi
= pointer_mux
<insn_info
, phi_info
>;
401 // The use belongs to a list that is partitioned into three sections:
403 // (1) all uses in nondebug instructions, in reverse postorder
405 // (2) all uses in debug instructions, in reverse postorder
407 // (3) all phi nodes, in no particular order.
409 // In order to preserve memory:
411 // - The set_info just has a pointer to the first use.
413 // - The first use's "prev" pointer points to the last use.
415 // - The last use's "next" pointer points to the last use in a nondebug
416 // instruction, or null if there are no such uses.
417 using last_use_or_prev_use
= pointer_mux
<use_info
>;
418 using last_nondebug_insn_use_or_next_use
= pointer_mux
<use_info
>;
420 use_info (insn_or_phi
, resource_info
, set_info
*);
422 use_info
*last_use () const;
423 use_info
*last_nondebug_insn_use () const;
424 bool calculate_is_last_nondebug_insn_use () const;
426 void record_reference (rtx_obj_reference
, bool);
427 void set_insn (insn_info
*);
428 void set_def (set_info
*set
) { m_def
= set
; }
429 void set_is_live_out_use (bool value
) { m_is_live_out_use
= value
; }
430 void copy_prev_from (use_info
*);
431 void copy_next_from (use_info
*);
432 void set_last_use (use_info
*);
433 void set_prev_use (use_info
*);
434 void set_last_nondebug_insn_use (use_info
*);
435 void set_next_use (use_info
*);
436 void clear_use_links ();
437 bool has_use_links ();
438 bool check_integrity ();
440 // The location of the use.
441 insn_or_phi m_insn_or_phi
;
443 // The overloaded "prev" and "next" pointers, as described above.
444 last_use_or_prev_use m_last_use_or_prev_use
;
445 last_nondebug_insn_use_or_next_use m_last_nondebug_insn_use_or_next_use
;
447 // The value of def ().
451 // Iterators for lists of uses.
452 using use_iterator
= list_iterator
<use_info
, &use_info::next_use
>;
453 using reverse_use_iterator
= list_iterator
<use_info
, &use_info::prev_use
>;
455 // Like use_iterator, but specifically for uses by nondebug instructions,
456 // uses by any kind of instruction, and uses by phi nodes respectively.
457 // These iterators allow a nullptr end point even if there are other types
458 // of use in the same definition.
459 using nondebug_insn_use_iterator
460 = list_iterator
<use_info
, &use_info::next_nondebug_insn_use
>;
461 using any_insn_use_iterator
462 = list_iterator
<use_info
, &use_info::next_any_insn_use
>;
463 using phi_use_iterator
= list_iterator
<use_info
, &use_info::prev_phi_use
>;
465 // A view of an access_array in which every entry is known to be a use_info.
466 using use_array
= const_derived_container
<use_info
*, access_array
>;
468 // An access_info that describes a definition of a resource. The definition
469 // can be a set or a clobber; the difference is that a set provides a known
470 // and potentially useful value, while a clobber provides an unknown and
473 // Every definition is associated with an insn_info. All definitions of
474 // a given resource are stored in a linked list, maintained in reverse
476 class def_info
: public access_info
478 // Overall size: 4 LP64 words
479 friend class function_info
;
480 friend class clobber_group
;
483 // Return the instruction that contains the definition.
484 insn_info
*insn () const { return m_insn
; }
486 // Return the basic block that contains the definition.
487 bb_info
*bb () const;
489 // Return the extended basic block that contains the access.
490 ebb_info
*ebb () const;
492 // Return the previous and next definitions of the same resource,
493 // in reverse postorder, or null if no such definition exists.
494 def_info
*prev_def () const;
495 def_info
*next_def () const;
497 // Return true if this is the first definition in the list.
498 bool is_first_def () const;
500 // Return true if this is the last definition in the list.
501 bool is_last_def () const;
503 // Print the location of the definition to PP.
504 void print_location (pretty_printer
*pp
) const;
506 // Print a unique identifier for this definition to PP. The identifier has
507 // the form <resource>:<insn uid>.
508 void print_identifier (pretty_printer
*pp
) const;
511 def_info (insn_info
*insn
, resource_info resource
, access_kind kind
);
514 // In order to preserve memory, the list head only points to the first
515 // definition in the list. The "prev" entry of the first definition
516 // then points to the last definition.
517 using last_def_or_prev_def
= pointer_mux
<def_info
>;
519 // For similar memory-saving reasons, if we want to create a splay tree
520 // of accesses to a resource, we hang the root off the "next" entry of
521 // the last definition in the list.
522 using splay_root_or_next_def
= pointer_mux
<def_node
, def_info
>;
524 void set_insn (insn_info
*insn
) { m_insn
= insn
; }
526 def_info
*last_def () const;
527 def_node
*splay_root () const;
529 void record_reference (rtx_obj_reference
, bool);
530 void copy_prev_from (def_info
*);
531 void copy_next_from (def_info
*);
532 void set_last_def (def_info
*);
533 void set_prev_def (def_info
*);
534 void set_splay_root (def_node
*);
535 void set_next_def (def_info
*);
536 void clear_def_links ();
537 bool has_def_links ();
539 // The location of the definition.
542 // The overloaded "prev" and "next" pointers, as described above.
543 last_def_or_prev_def m_last_def_or_prev_def
;
544 splay_root_or_next_def m_splay_root_or_next_def
;
547 // Iterators for lists of definitions.
548 using def_iterator
= list_iterator
<def_info
, &def_info::next_def
>;
549 using reverse_def_iterator
= list_iterator
<def_info
, &def_info::prev_def
>;
551 // A view of an access_array in which every entry is known to be a
553 using def_array
= const_derived_container
<def_info
*, access_array
>;
555 // A def_info that sets the resource to a value that is both
556 // unknown and not useful. This is only ever used for registers,
557 // since memory always has some useful contents.
559 // Neighboring clobbers are grouped into clobber_groups, so that it's
560 // possibly to skip over all neighboring clobbers in a single step.
561 class clobber_info
: public def_info
563 // Overall size: 8 LP64 words
564 friend class default_splay_tree_accessors
<clobber_info
*>;
565 friend class default_splay_tree_accessors_with_parent
<clobber_info
*>;
566 friend class function_info
;
567 friend class clobber_group
;
570 using splay_tree
= default_rootless_splay_tree
<clobber_info
*>;
572 // Return true if the clobber belongs to a clobber_group, false if it
574 bool is_in_group () const { return m_group
; }
576 // Return the group that the clobber is in, or null if none.
578 // Complexity: amortized O(1), worst case O(N), where N is the number
579 // of clobbers in the containing clobber_group.
580 clobber_group
*group () const;
582 // Print a description of the clobber to PP under the control of
583 // PP_ACCESS_* flags FLAGS.
584 void print (pretty_printer
*pp
,
585 unsigned int flags
= PP_ACCESS_DEFAULT
) const;
588 // Once normal call clobbers are taken out of the equation by
589 // insn_call_clobbers_notes, clobber_infos account for roughly 6% of all
590 // def_infos, with the rest being set_infos. clobber_infos are
591 // therefore much less size-sensitive than set_infos are.
593 // As noted above, we want to group neighboring clobbers together so that
594 // we can quickly step over them to find the previous or next "real" set.
595 // We also want to be able to split the group in sublinear time,
596 // for example when inserting a set/use pair between two clobbers
601 // - Clobbers need to have ready access to their group, so that we
602 // can cheaply skip over the whole group. This means that they
603 // need a group pointer.
605 // - We need to be able to update the group pointer lazily, so that
606 // the cost of updating it is counted against accesses to the clobbers
607 // that need updating.
609 // We also want to be able to insert clobbers into a group in
610 // amortized logarithmic time.
612 // We therefore use a splay tree to represent the clobbers in a group,
613 // with the nodes storing their parent node. It is then possible to
614 // perform splay operations without first getting hold of the root.
615 // The root of the splay tree always has a valid, up-to-date group,
616 // so lazy group updates can get the new group from there.
618 // Roughly 90% of clobbers have a neighboring definition in the same
619 // block, which means that most need to be stored in a splay tree.
620 // We therefore store the splay tree fields directly in the clobber_info
621 // rather than using a separate node object.
623 clobber_info (insn_info
*, unsigned int);
625 void set_group (clobber_group
*group
) { m_group
= group
; }
626 void update_group (clobber_group
*);
627 clobber_group
*recompute_group ();
629 // The child and parent nodes in the splay tree.
630 clobber_info
*m_children
[2];
631 clobber_info
*m_parent
;
633 // The last known value of group (), which might now be out of date.
634 clobber_group
*m_group
;
637 using clobber_tree
= clobber_info::splay_tree::rooted
;
639 // A def_info that sets the resource to a useful value. It records
640 // all uses of the value in a linked list. The list is partitioned
641 // into three sections:
643 // (1) all uses by nondebug instructions, in reverse postorder, followed by
644 // (2) all uses by debug instructions, in reverse postorder, followed by
645 // (3) all uses by phi nodes, in no particular order.
647 // There are two cases:
649 // - If we know in advance that there is a single definition of a resource R
650 // and therefore decide not to use phi nodes for R, (1) and (2) contain
651 // all uses of R, regardless of which blocks contain the uses. (3) is
654 // - Otherwise, (1) only contains uses in the same extended basic block
655 // as the definition, and it is terminated by a use that marks the end
656 // of the live range for the EBB. In other words, if the resource dies
657 // in the EBB, the last use by a nondebug instruction marks the point at
658 // which it dies, otherwise there is a fake live-out use at the end of
661 // Since debug instructions should not affect codegen, they opportunisticly
662 // attach to the same set_info as nondebug instructions where possible.
663 // If a nondebug instruction would attach to a degenerate phi and if no
664 // such phi exists, debug instructions instead attach to whichever set_info
665 // provides the value, regardless of where that set_info is.
666 class set_info
: public def_info
668 // Overall size: 6 LP64 words.
669 friend class function_info
;
670 using use_splay_tree
= splay_tree
<use_info
*>;
673 // Return the first and last uses of the set, or null if the list is empty.
674 // See the comment above for details about the order.
675 use_info
*first_use () const { return m_first_use
; }
676 use_info
*last_use () const;
678 // Return the first and last uses of the set by nondebug instructions,
679 // or null if there are no such uses. The uses are in reverse postorder.
680 use_info
*first_nondebug_insn_use () const;
681 use_info
*last_nondebug_insn_use () const;
683 // Return the first use of the set by any kind of instruction, or null
684 // if there are no such uses. The uses are in the order described above.
685 use_info
*first_any_insn_use () const;
687 // Return the last use of the set by phi inputs, or null if there are no
688 // such uses. The phi input uses are in no particular order.
689 use_info
*last_phi_use () const;
691 // Return true if at least one nondebug instruction or phi node uses
692 // the set's result. This is equivalent to testing whether the set is
694 bool has_nondebug_uses () const;
696 // Return true if anything uses the set's result. Note that this includes
697 // uses by debug instructions, so it should not be used for optimization
699 bool has_any_uses () const { return m_first_use
; }
701 // Return true if at least one nondebug instruction uses the set's result.
702 bool has_nondebug_insn_uses () const;
704 // Return true if at least one phi node uses the set's result.
705 bool has_phi_uses () const;
707 // If there is exactly one nondebug use of the set's result, return that use,
708 // otherwise return null. The use might be in an instruction or in a phi
710 use_info
*single_nondebug_use () const;
712 // If exactly one nondebug instruction uses the set's result, return the use
713 // by that instruction, otherwise return null.
714 use_info
*single_nondebug_insn_use () const;
716 // If exactly one phi node uses the set's result, return the use by that phi
717 // node, otherwise return null.
718 use_info
*single_phi_use () const;
720 // Return true if the set and its uses are contained within a single
721 // extended basic block, with the set coming first. This implies
722 // that all uses are by instructions rather than phi nodes.
723 bool is_local_to_ebb () const;
725 // List all the uses of the set, in the order described above.
726 iterator_range
<use_iterator
> all_uses () const;
728 // Return uses () in reverse order.
729 iterator_range
<reverse_use_iterator
> reverse_all_uses () const;
731 // List the uses of the set by nondebug instructions, in reverse postorder.
732 iterator_range
<nondebug_insn_use_iterator
> nondebug_insn_uses () const;
734 // Return nondebug_insn_uses () in reverse order.
735 iterator_range
<reverse_use_iterator
> reverse_nondebug_insn_uses () const;
737 // List the uses of the set by any kind of instruction. The list follows
738 // the order described above.
739 iterator_range
<any_insn_use_iterator
> all_insn_uses () const;
741 // List the uses of the set by phi nodes, in no particular order.
742 // There is therefore no reversed equivalent of this list.
743 iterator_range
<phi_use_iterator
> phi_uses () const;
745 // Print a description of the set to PP under the control of
746 // PP_ACCESS_* flags FLAGS.
747 void print (pretty_printer
*pp
,
748 unsigned int flags
= PP_ACCESS_DEFAULT
) const;
751 set_info (insn_info
*, resource_info
, access_kind
);
753 // Print information about uses () to PP, continuing information printed
754 // about the set itself.
755 void print_uses_on_new_lines (pretty_printer
*pp
) const;
758 // Sets (including phis) account for about 94% of all definitions
760 set_info (insn_info
*, resource_info
);
762 void set_first_use (use_info
*);
764 // The first use in the list.
765 use_info
*m_first_use
;
767 // The root of a splay tree of all uses, built lazily when we first
768 // think it's needed.
769 use_splay_tree m_use_tree
;
772 // A set_info for an on-the-side phi node. The phi node is attached
773 // to an extended basic block EBB and has one input for each incoming edge.
774 // The inputs are represented as an array of use_infos, with input I
775 // corresponding to EDGE_PRED (EBB->first_bb ()->cfg_bb (), I).
777 // Each phi node has a densely-allocated unique identifier, which is intended
778 // to be suitable for bitmaps or sbitmaps.
780 // All the phi nodes in an extended basic block are chained together
781 // into a linked list. The list has no particular order.
782 class phi_info
: public set_info
784 // Overall size: 8 LP64 words
785 friend class function_info
;
788 // Return the previous and next phi nodes in the extended basic block's list,
790 phi_info
*prev_phi () const { return m_prev_phi
; }
791 phi_info
*next_phi () const { return m_next_phi
; }
793 // Return the number of phi inputs. This is 1 for degenerate phis,
794 // otherwise it is equal to the number of incoming edges.
795 unsigned int num_inputs () const { return m_num_inputs
; }
797 // Return true if the phi node is degenerate, i.e. if it has only a
799 bool is_degenerate () const { return m_num_inputs
== 1; }
801 // Return the phi node's unique identifier.
802 unsigned int uid () const { return m_uid
; }
804 // Return the array of inputs. For degenerate phi nodes, this array contains
805 // a single element, otherwise it has one input per incoming edge,
806 // with element E corresponding to incoming edge E.
807 use_array
inputs () const;
809 // Return the use_info that describes the phi input for incoming edge E.
810 use_info
*input_use (unsigned int e
) const;
812 // Return the value of resource () on incoming edge E, or null if the
813 // value is completely undefined for that edge.
814 set_info
*input_value (unsigned int e
) const;
816 // Print a description of the phi node to PP under the control of
817 // PP_ACCESS_* flags FLAGS.
818 void print (pretty_printer
*pp
,
819 unsigned int flags
= PP_ACCESS_DEFAULT
) const;
822 phi_info (insn_info
*insn
, resource_info resource
, unsigned int uid
);
824 void make_degenerate (use_info
*);
825 void set_inputs (use_array inputs
);
826 void set_prev_phi (phi_info
*prev_phi
) { m_prev_phi
= prev_phi
; }
827 void set_next_phi (phi_info
*next_phi
) { m_next_phi
= next_phi
; }
828 void clear_phi_links () { m_prev_phi
= m_next_phi
= nullptr; }
829 bool has_phi_links () { return m_prev_phi
|| m_next_phi
; }
831 // The values returned by the accessors above.
833 unsigned int m_num_inputs
;
836 access_info
*const *m_inputs
;
837 access_info
*m_single_input
;
839 phi_info
*m_prev_phi
;
840 phi_info
*m_next_phi
;
843 // An iterator for lists of phi nodes.
844 using phi_iterator
= list_iterator
<phi_info
, &phi_info::next_phi
>;
846 // One node in a splay tree of definitions. This base class represents
847 // a single def_info, but it is structured to allow derived classes
851 // Size: 3 LP64 words.
852 friend class function_info
;
853 friend class default_splay_tree_accessors
<def_node
*>;
856 // Return the first definition that the node represents.
857 def_info
*first_def () const;
859 // Return which type of access first_def () is.
860 bool contains_clobber () const { return m_clobber_or_set
.is_first (); }
861 bool contains_set () const { return m_clobber_or_set
.is_second (); }
864 // More nodes are clobbers rather than sets, so put clobbers first.
865 // Neither choice can be null.
866 using clobber_or_set
= pointer_mux
<clobber_info
, set_info
>;
868 // Construct a node that represents FIRST_DEF (and possibly later
869 // definitions too, if called from a derived class).
870 def_node (clobber_or_set first_def
);
872 // The first definition in the node.
873 clobber_or_set m_clobber_or_set
;
876 // The splay tree child nodes.
877 def_node
*m_children
[2];
880 // One node in a splay tree of def_infos, representing a single set_info.
881 class set_node
: public def_node
883 // Overall size: 3 LP64 words.
884 friend class function_info
;
887 // Return the set that the node contains.
888 set_info
*set () const { return m_clobber_or_set
.known_second (); }
890 // Print a description of the node to PP.
891 void print (pretty_printer
*pp
) const;
894 // Construct a node for SET.
895 set_node (set_info
*set
) : def_node (set
) {}
898 // One node in a splay tree of def_infos. This class represents
899 // a list of contiguous clobber_infos, in execution order.
900 class clobber_group
: public def_node
902 // Overall size: 5 LP64 words.
903 friend class function_info
;
906 // Return the first and last clobbers in the group. The results are
908 clobber_info
*first_clobber () const;
909 clobber_info
*last_clobber () const { return m_last_clobber
; }
911 // Return the last clobber before INSN in the group, or null if none.
912 clobber_info
*prev_clobber (insn_info
*insn
) const;
914 // Return the next clobber after INSN in the group, or null if none.
915 clobber_info
*next_clobber (insn_info
*insn
) const;
917 // Return true if this group has been replaced by new clobber_groups.
918 bool has_been_superceded () const { return !m_last_clobber
; }
920 // Return a list of the clobbers in the group, in execution order.
921 iterator_range
<def_iterator
> clobbers () const;
923 // Print a description of the group to PP.
924 void print (pretty_printer
*pp
) const;
927 clobber_group (clobber_info
*clobber
);
929 // Set the values of first_clobber () and last_clobber ().
930 void set_first_clobber (clobber_info
*c
) { m_clobber_or_set
= c
; }
931 void set_last_clobber (clobber_info
*c
) { m_last_clobber
= c
; }
933 // The value returned by last_clobber ().
934 clobber_info
*m_last_clobber
;
936 // A splay tree that contains all the clobbers in the group.
937 // The root of the splay tree always has an up-to-date group
938 // pointer, but the other clobbers in the tree might not.
939 clobber_tree m_clobber_tree
;
942 // A splay tree in which one node represents a standalone set_info or a
943 // range of consecutive clobber_infos. The nodes follow execution order
944 // and maintain the invariant that no two groups of clobber_infos appear
945 // next to each other (instead, the groups are merged).
946 using def_splay_tree
= default_splay_tree
<def_node
*>;
948 // This type represents a choice between:
950 // (1) a single definition of a resource
951 // (2) a node in a def_splay_tree that represents either a single
952 // set or a group of clobbers.
953 class def_mux
: public pointer_mux
<def_info
, def_node
>
955 using parent
= pointer_mux
<def_info
, def_node
>;
957 // Provide the same constructors as the pointer_mux.
958 using parent::parent
;
961 // Return the first definition associated with this mux. If the mux holds
962 // a single definition, the result is that definition. If the mux holds
963 // a clobber_group, the result is the first clobber in the group.
964 def_info
*first_def () const;
966 // Return the last definition associated with this mux. If the mux holds
967 // a single definition, the result is that definition. If the mux holds
968 // a clobber_group, the result is the last clobber in the group.
969 def_info
*last_def () const;
971 // If the pointer represents a set_info, return that set_info,
972 // otherwise return null.
973 set_info
*set () const;
976 // This class represents the result of looking up the definition of a
977 // resource at a particular point, here referred to as point P.
978 // There are four states:
980 // - MUX is null if there were no definitions to search.
982 // - Otherwise, COMPARISON is 0 if we found a definition at P or a
983 // clobber_group that spans P. MUX then contains this definition
986 // - Otherwise, COMPARISON is greater than 0 if we found the definition
987 // that precedes P or the group of clobbers that precedes P. MUX then
988 // contains this definition or clobber_group.
990 // - Otherwise, COMPARISON is less than zero and we found the definition
991 // that follows P, or the group of clobbers that follows P. MUX then
992 // contains this definition or clobber_group.
996 // If we found a clobber_group that spans P, return the definition
997 // that precedes the start of the group, or null if none.
999 // Otherwise, return the last definition that occurs before P,
1001 def_info
*last_def_of_prev_group () const;
1003 // If we found a clobber_group that spans P, return the definition
1004 // that follows the end of the group, or null if none.
1006 // Otherwise, return the first definition that occurs after P,
1008 def_info
*first_def_of_next_group () const;
1010 // If we found a set_info at P, return that set_info, otherwise return null.
1011 set_info
*matching_set () const;
1013 // If we found a set_info at P, return that set_info, otherwise return
1015 def_info
*matching_set_or_last_def_of_prev_group () const;
1017 // If we found a set_info at P, return that set_info, otherwise return
1019 def_info
*matching_set_or_first_def_of_next_group () const;
1021 // P is the location of INSN. Return the last definition (of any kind)
1022 // that occurs before INSN, or null if none.
1023 def_info
*prev_def (insn_info
*insn
) const;
1025 // P is the location of INSN. Return the next definition (of any kind)
1026 // that occurs after INSN, or null if none.
1027 def_info
*next_def (insn_info
*insn
) const;
1033 void pp_resource (pretty_printer
*, resource_info
);
1034 void pp_access (pretty_printer
*, const access_info
*,
1035 unsigned int flags
= PP_ACCESS_DEFAULT
);
1036 void pp_accesses (pretty_printer
*, access_array
,
1037 unsigned int flags
= PP_ACCESS_DEFAULT
);
1038 void pp_def_node (pretty_printer
*, const def_node
*);
1039 void pp_def_mux (pretty_printer
*, def_mux
);
1040 void pp_def_lookup (pretty_printer
*, def_lookup
);
1044 void dump (FILE *, rtl_ssa::resource_info
);
1045 void dump (FILE *, const rtl_ssa::access_info
*,
1046 unsigned int flags
= rtl_ssa::PP_ACCESS_DEFAULT
);
1047 void dump (FILE *, rtl_ssa::access_array
,
1048 unsigned int flags
= rtl_ssa::PP_ACCESS_DEFAULT
);
1049 void dump (FILE *, const rtl_ssa::def_node
*);
1050 void dump (FILE *, rtl_ssa::def_mux
);
1051 void dump (FILE *, rtl_ssa::def_lookup
);
1053 void DEBUG_FUNCTION
debug (const rtl_ssa::resource_info
*);
1054 void DEBUG_FUNCTION
debug (const rtl_ssa::access_info
*);
1055 void DEBUG_FUNCTION
debug (const rtl_ssa::access_array
);
1056 void DEBUG_FUNCTION
debug (const rtl_ssa::def_node
*);
1057 void DEBUG_FUNCTION
debug (const rtl_ssa::def_mux
&);
1058 void DEBUG_FUNCTION
debug (const rtl_ssa::def_lookup
&);