1 // Implementation of access-related functions for RTL SSA -*- C++ -*-
2 // Copyright (C) 2020-2021 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/>.
20 #define INCLUDE_ALGORITHM
21 #define INCLUDE_FUNCTIONAL
24 #include "coretypes.h"
29 #include "rtl-ssa/internals.h"
30 #include "rtl-ssa/internals.inl"
32 using namespace rtl_ssa
;
34 // This clobber belongs to a clobber_group but m_group appears to be
35 // out of date. Update it and return the new (correct) value.
37 clobber_info::recompute_group ()
39 using splay_tree
= clobber_info::splay_tree
;
41 // Splay this clobber to the root of the tree while searching for a node
42 // that has the correct group. The root always has the correct group,
43 // so the search always breaks early and does not install this clobber
45 clobber_info
*cursor
= m_parent
;
46 auto find_group
= [](clobber_info
*node
, unsigned int)
48 return node
->m_group
->has_been_superceded () ? nullptr : node
->m_group
;
50 clobber_group
*group
= splay_tree::splay_and_search (this, nullptr,
52 gcc_checking_assert (m_parent
);
54 // If the previous splay operation did anything, this clobber is now an
55 // ancestor of CURSOR, and all the nodes inbetween have a stale group.
56 // Since we have visited the nodes, we might as well update them too.
58 // If the previous splay operation did nothing, start the update from
59 // this clobber instead. In that case we change at most two clobbers:
60 // this clobber and possibly its parent.
61 if (cursor
== m_parent
)
64 // Walk up the tree from CURSOR updating clobbers that need it.
65 // This walk always includes this clobber.
66 while (cursor
->m_group
!= group
)
68 cursor
->m_group
= group
;
69 cursor
= cursor
->m_parent
;
72 gcc_checking_assert (m_group
== group
);
76 // See the comment above the declaration.
78 resource_info::print_identifier (pretty_printer
*pp
) const
81 pp_string (pp
, "mem");
84 char tmp
[3 * sizeof (regno
) + 2];
85 snprintf (tmp
, sizeof (tmp
), "r%d", regno
);
90 // See the comment above the declaration.
92 resource_info::print_context (pretty_printer
*pp
) const
94 if (HARD_REGISTER_NUM_P (regno
))
96 if (const char *name
= reg_names
[regno
])
100 pp_string (pp
, name
);
101 if (mode
!= E_BLKmode
)
104 pp_string (pp
, GET_MODE_NAME (mode
));
113 if (mode
!= E_BLKmode
)
115 pp_string (pp
, GET_MODE_NAME (mode
));
118 pp_string (pp
, "pseudo");
123 // See the comment above the declaration.
125 resource_info::print (pretty_printer
*pp
) const
127 print_identifier (pp
);
131 // Some properties can naturally be described using adjectives that attach
132 // to nouns like "use" or "definition". Print such adjectives to PP.
134 access_info::print_prefix_flags (pretty_printer
*pp
) const
137 pp_string (pp
, "temporary ");
138 if (m_has_been_superceded
)
139 pp_string (pp
, "superceded ");
142 // Print properties not handled by print_prefix_flags to PP, putting
143 // each property on a new line indented by two extra spaces.
145 access_info::print_properties_on_new_lines (pretty_printer
*pp
) const
147 if (m_is_pre_post_modify
)
149 pp_newline_and_indent (pp
, 2);
150 pp_string (pp
, "set by a pre/post-modify");
151 pp_indentation (pp
) -= 2;
153 if (m_includes_address_uses
)
155 pp_newline_and_indent (pp
, 2);
156 pp_string (pp
, "appears inside an address");
157 pp_indentation (pp
) -= 2;
159 if (m_includes_read_writes
)
161 pp_newline_and_indent (pp
, 2);
162 pp_string (pp
, "appears in a read/write context");
163 pp_indentation (pp
) -= 2;
165 if (m_includes_subregs
)
167 pp_newline_and_indent (pp
, 2);
168 pp_string (pp
, "appears inside a subreg");
169 pp_indentation (pp
) -= 2;
173 // Return true if there are no known issues with the integrity of the
176 use_info::check_integrity ()
178 auto subsequence_id
= [](use_info
*use
)
180 if (use
->is_in_nondebug_insn ())
182 if (use
->is_in_debug_insn ())
187 use_info
*prev
= prev_use ();
188 use_info
*next
= next_use ();
190 if (prev
&& subsequence_id (prev
) > subsequence_id (this))
192 if (next
&& subsequence_id (next
) < subsequence_id (this))
194 if (m_is_last_nondebug_insn_use
!= calculate_is_last_nondebug_insn_use ())
197 if (!prev
&& last_use ()->next_use ())
200 if (use_info
*use
= last_nondebug_insn_use ())
201 if (!use
->m_is_last_nondebug_insn_use
)
207 // See the comment above the declaration.
209 use_info::print_location (pretty_printer
*pp
) const
212 pp_access (pp
, phi (), PP_ACCESS_INCLUDE_LOCATION
);
214 insn ()->print_identifier_and_location (pp
);
217 // See the comment above the declaration.
219 use_info::print_def (pretty_printer
*pp
) const
221 if (const set_info
*set
= def ())
222 pp_access (pp
, set
, 0);
225 pp_string (pp
, "undefined ");
226 resource ().print (pp
);
230 // See the comment above the declaration.
232 use_info::print (pretty_printer
*pp
, unsigned int flags
) const
234 print_prefix_flags (pp
);
236 const set_info
*set
= def ();
237 if (set
&& set
->mode () != mode ())
239 pp_string (pp
, GET_MODE_NAME (mode ()));
243 pp_string (pp
, "use of ");
245 if (flags
& PP_ACCESS_INCLUDE_LOCATION
)
247 pp_string (pp
, " by ");
250 if (set
&& (flags
& PP_ACCESS_INCLUDE_LINKS
))
252 pp_newline_and_indent (pp
, 2);
253 pp_string (pp
, "defined in ");
254 set
->insn ()->print_location (pp
);
255 pp_indentation (pp
) -= 2;
257 if (flags
& PP_ACCESS_INCLUDE_PROPERTIES
)
258 print_properties_on_new_lines (pp
);
261 // See the comment above the declaration.
263 def_info::print_identifier (pretty_printer
*pp
) const
265 resource ().print_identifier (pp
);
267 insn ()->print_identifier (pp
);
268 resource ().print_context (pp
);
271 // See the comment above the declaration.
273 def_info::print_location (pretty_printer
*pp
) const
275 insn ()->print_identifier_and_location (pp
);
278 // See the comment above the declaration.
280 clobber_info::print (pretty_printer
*pp
, unsigned int flags
) const
282 print_prefix_flags (pp
);
283 if (is_call_clobber ())
284 pp_string (pp
, "call ");
285 pp_string (pp
, "clobber ");
286 print_identifier (pp
);
287 if (flags
& PP_ACCESS_INCLUDE_LOCATION
)
289 pp_string (pp
, " in ");
290 insn ()->print_location (pp
);
292 if (flags
& PP_ACCESS_INCLUDE_PROPERTIES
)
293 print_properties_on_new_lines (pp
);
296 // See the comment above the declaration.
298 set_info::print_uses_on_new_lines (pretty_printer
*pp
) const
300 for (const use_info
*use
: all_uses ())
302 pp_newline_and_indent (pp
, 2);
303 if (use
->is_live_out_use ())
305 pp_string (pp
, "live out from ");
306 use
->insn ()->print_location (pp
);
310 pp_string (pp
, "used by ");
311 use
->print_location (pp
);
313 pp_indentation (pp
) -= 2;
317 pp_newline_and_indent (pp
, 2);
318 pp_string (pp
, "splay tree:");
319 pp_newline_and_indent (pp
, 2);
320 auto print_use
= [](pretty_printer
*pp
,
321 splay_tree_node
<use_info
*> *node
)
323 pp_string (pp
, "use by ");
324 node
->value ()->print_location (pp
);
326 m_use_tree
.print (pp
, m_use_tree
.root (), print_use
);
327 pp_indentation (pp
) -= 4;
331 // See the comment above the declaration.
333 set_info::print (pretty_printer
*pp
, unsigned int flags
) const
335 print_prefix_flags (pp
);
336 pp_string (pp
, "set ");
337 print_identifier (pp
);
338 if (flags
& PP_ACCESS_INCLUDE_LOCATION
)
340 pp_string (pp
, " in ");
341 insn ()->print_location (pp
);
343 if (flags
& PP_ACCESS_INCLUDE_PROPERTIES
)
344 print_properties_on_new_lines (pp
);
345 if (flags
& PP_ACCESS_INCLUDE_LINKS
)
346 print_uses_on_new_lines (pp
);
349 // See the comment above the declaration.
351 phi_info::print (pretty_printer
*pp
, unsigned int flags
) const
353 print_prefix_flags (pp
);
354 pp_string (pp
, "phi node ");
355 print_identifier (pp
);
356 if (flags
& PP_ACCESS_INCLUDE_LOCATION
)
358 pp_string (pp
, " in ");
359 insn ()->print_location (pp
);
362 if (flags
& PP_ACCESS_INCLUDE_PROPERTIES
)
363 print_properties_on_new_lines (pp
);
365 if (flags
& PP_ACCESS_INCLUDE_LINKS
)
367 basic_block cfg_bb
= bb ()->cfg_bb ();
368 pp_newline_and_indent (pp
, 2);
369 pp_string (pp
, "inputs:");
371 for (const use_info
*input
: inputs ())
373 basic_block pred_cfg_bb
= EDGE_PRED (cfg_bb
, i
)->src
;
374 pp_newline_and_indent (pp
, 2);
375 pp_string (pp
, "bb");
376 pp_decimal_int (pp
, pred_cfg_bb
->index
);
379 input
->print_def (pp
);
380 pp_indentation (pp
) -= 2;
383 pp_indentation (pp
) -= 2;
385 print_uses_on_new_lines (pp
);
389 // See the comment above the declaration.
391 set_node::print (pretty_printer
*pp
) const
393 pp_access (pp
, first_def ());
396 // See the comment above the declaration.
398 clobber_group::print (pretty_printer
*pp
) const
400 auto print_clobber
= [](pretty_printer
*pp
, const def_info
*clobber
)
402 pp_access (pp
, clobber
);
404 pp_string (pp
, "grouped clobber");
405 for (const def_info
*clobber
: clobbers ())
407 pp_newline_and_indent (pp
, 2);
408 print_clobber (pp
, clobber
);
409 pp_indentation (pp
) -= 2;
411 pp_newline_and_indent (pp
, 2);
412 pp_string (pp
, "splay tree");
413 pp_newline_and_indent (pp
, 2);
414 m_clobber_tree
.print (pp
, print_clobber
);
415 pp_indentation (pp
) -= 4;
418 // Return a clobber_group for CLOBBER, creating one if CLOBBER doesn't
419 // already belong to a group.
421 function_info::need_clobber_group (clobber_info
*clobber
)
423 if (clobber
->is_in_group ())
424 return clobber
->group ();
425 return allocate
<clobber_group
> (clobber
);
428 // Return a def_node for inserting DEF into the associated resource's
429 // splay tree. Use a clobber_group if DEF is a clobber and a set_node
432 function_info::need_def_node (def_info
*def
)
434 if (auto *clobber
= dyn_cast
<clobber_info
*> (def
))
435 return need_clobber_group (clobber
);
436 return allocate
<set_node
> (as_a
<set_info
*> (def
));
439 // LAST is the last thing to define LAST->resource (), and is where any
440 // splay tree root for LAST->resource () is stored. Require such a splay tree
441 // to exist, creating a new one if necessary. Return the root of the tree.
443 // The caller must call LAST->set_splay_root after it has finished with
446 function_info::need_def_splay_tree (def_info
*last
)
448 if (def_node
*root
= last
->splay_root ())
451 // Use a left-spine rooted at the last node.
452 def_node
*root
= need_def_node (last
);
453 def_node
*parent
= root
;
454 while (def_info
*prev
= first_def (parent
)->prev_def ())
456 def_node
*node
= need_def_node (prev
);
457 def_splay_tree::insert_child (parent
, 0, node
);
463 // Search TREE for either:
465 // - a set_info at INSN or
466 // - a clobber_group whose range includes INSN
468 // If such a node exists, install it as the root of TREE and return 0.
469 // Otherwise arbitrarily choose between:
471 // (1) Installing the closest preceding node as the root and returning 1.
472 // (2) Installing the closest following node as the root and returning -1.
474 // Note that this routine should not be used to check whether INSN
475 // itself defines a resource; that can be checked more cheaply using
476 // find_access_index.
478 rtl_ssa::lookup_def (def_splay_tree
&tree
, insn_info
*insn
)
480 auto go_left
= [&](def_node
*node
)
482 return *insn
< *first_def (node
)->insn ();
484 auto go_right
= [&](def_node
*node
)
486 return *insn
> *last_def (node
)->insn ();
488 return tree
.lookup (go_left
, go_right
);
491 // Search TREE for a clobber in INSN. If such a clobber exists, install
492 // it as the root of TREE and return 0. Otherwise arbitrarily choose between:
494 // (1) Installing the closest preceding clobber as the root and returning 1.
495 // (2) Installing the closest following clobber as the root and returning -1.
497 rtl_ssa::lookup_clobber (clobber_tree
&tree
, insn_info
*insn
)
499 auto compare
= [&](clobber_info
*clobber
)
501 return insn
->compare_with (clobber
->insn ());
503 return tree
.lookup (compare
);
506 // Search for a definition of RESOURCE at INSN and return the result of
507 // the search as a def_lookup. See the comment above the class for more
510 function_info::find_def (resource_info resource
, insn_info
*insn
)
512 def_info
*first
= m_defs
[resource
.regno
+ 1];
514 // There are no nodes. The comparison result is pretty meaningless
516 return { nullptr, -1 };
518 // See whether the first node matches.
519 auto first_result
= clobber_group_or_single_def (first
);
520 if (*insn
<= *last_def (first_result
)->insn ())
522 int comparison
= (*insn
>= *first
->insn () ? 0 : -1);
523 return { first_result
, comparison
};
526 // See whether the last node matches.
527 def_info
*last
= first
->last_def ();
528 auto last_result
= clobber_group_or_single_def (last
);
529 if (*insn
>= *first_def (last_result
)->insn ())
531 int comparison
= (*insn
<= *last
->insn () ? 0 : 1);
532 return { last_result
, comparison
};
535 // Resort to using a splay tree to search for the result.
536 def_splay_tree tree
= need_def_splay_tree (last
);
537 int comparison
= lookup_def (tree
, insn
);
538 last
->set_splay_root (tree
.root ());
539 return { tree
.root (), comparison
};
542 // Add DEF to the function's list of definitions of DEF->resource (),
543 // inserting DEF immediately before BEFORE. DEF is not currently in the list.
545 function_info::insert_def_before (def_info
*def
, def_info
*before
)
547 gcc_checking_assert (!def
->has_def_links ()
548 && *before
->insn () > *def
->insn ());
550 def
->copy_prev_from (before
);
551 if (def_info
*prev
= def
->prev_def ())
553 gcc_checking_assert (*prev
->insn () < *def
->insn ());
554 prev
->set_next_def (def
);
557 m_defs
[def
->regno () + 1] = def
;
559 def
->set_next_def (before
);
560 before
->set_prev_def (def
);
563 // Add DEF to the function's list of definitions of DEF->resource (),
564 // inserting DEF immediately after AFTER. DEF is not currently in the list.
566 function_info::insert_def_after (def_info
*def
, def_info
*after
)
568 gcc_checking_assert (!def
->has_def_links ()
569 && *after
->insn () < *def
->insn ());
571 def
->copy_next_from (after
);
572 if (def_info
*next
= def
->next_def ())
574 gcc_checking_assert (*next
->insn () > *def
->insn ());
575 next
->set_prev_def (def
);
578 m_defs
[def
->regno () + 1]->set_last_def (def
);
580 def
->set_prev_def (after
);
581 after
->set_next_def (def
);
584 // Remove DEF from the function's list of definitions of DEF->resource ().
586 function_info::remove_def_from_list (def_info
*def
)
588 def_info
*prev
= def
->prev_def ();
589 def_info
*next
= def
->next_def ();
592 next
->copy_prev_from (def
);
594 m_defs
[def
->regno () + 1]->set_last_def (prev
);
597 prev
->copy_next_from (def
);
599 m_defs
[def
->regno () + 1] = next
;
601 def
->clear_def_links ();
604 // Add CLOBBER to GROUP and insert it into the function's list of
605 // accesses to CLOBBER->resource (). CLOBBER is not currently part
606 // of an active group and is not currently in the list.
608 function_info::add_clobber (clobber_info
*clobber
, clobber_group
*group
)
610 // Search for either the previous or next clobber in the group.
611 // The result is less than zero if CLOBBER should come before NEIGHBOR
612 // or greater than zero if CLOBBER should come after NEIGHBOR.
613 int comparison
= lookup_clobber (group
->m_clobber_tree
, clobber
->insn ());
614 gcc_checking_assert (comparison
!= 0);
615 clobber_info
*neighbor
= group
->m_clobber_tree
.root ();
617 // Since HEIGHBOR is now the root of the splay tree, its group needs
619 neighbor
->update_group (group
);
621 // If CLOBBER comes before NEIGHBOR, insert CLOBBER to NEIGHBOR's left,
622 // otherwise insert CLOBBER to NEIGHBOR's right.
623 clobber_info::splay_tree::insert_child (neighbor
, comparison
> 0, clobber
);
624 clobber
->set_group (group
);
626 // Insert the clobber into the function-wide list and update the
627 // bounds of the group.
630 insert_def_after (clobber
, neighbor
);
631 if (neighbor
== group
->last_clobber ())
632 group
->set_last_clobber (clobber
);
636 insert_def_before (clobber
, neighbor
);
637 if (neighbor
== group
->first_clobber ())
638 group
->set_first_clobber (clobber
);
642 // Remove CLOBBER from GROUP, given that GROUP contains other clobbers too.
643 // Also remove CLOBBER from the function's list of accesses to
644 // CLOBBER->resource ().
646 function_info::remove_clobber (clobber_info
*clobber
, clobber_group
*group
)
648 if (clobber
== group
->first_clobber ())
650 auto *new_first
= as_a
<clobber_info
*> (clobber
->next_def ());
651 group
->set_first_clobber (new_first
);
652 new_first
->update_group (group
);
654 else if (clobber
== group
->last_clobber ())
656 auto *new_last
= as_a
<clobber_info
*> (clobber
->prev_def ());
657 group
->set_last_clobber (new_last
);
658 new_last
->update_group (group
);
661 clobber_info
*replacement
= clobber_info::splay_tree::remove_node (clobber
);
662 if (clobber
== group
->m_clobber_tree
.root ())
664 group
->m_clobber_tree
= replacement
;
665 replacement
->update_group (group
);
667 clobber
->set_group (nullptr);
669 remove_def_from_list (clobber
);
672 // Add CLOBBER immediately before the first clobber in GROUP, given that
673 // CLOBBER is not currently part of any group.
675 function_info::prepend_clobber_to_group (clobber_info
*clobber
,
676 clobber_group
*group
)
678 clobber_info
*next
= group
->first_clobber ();
679 clobber_info::splay_tree::insert_child (next
, 0, clobber
);
680 group
->set_first_clobber (clobber
);
681 clobber
->set_group (group
);
684 // Add CLOBBER immediately after the last clobber in GROUP, given that
685 // CLOBBER is not currently part of any group.
687 function_info::append_clobber_to_group (clobber_info
*clobber
,
688 clobber_group
*group
)
690 clobber_info
*prev
= group
->last_clobber ();
691 clobber_info::splay_tree::insert_child (prev
, 1, clobber
);
692 group
->set_last_clobber (clobber
);
693 clobber
->set_group (group
);
696 // Put CLOBBER1 and CLOBBER2 into the same clobber_group, given that
697 // CLOBBER1 occurs immediately before CLOBBER2 and that the two clobbers
698 // are not currently in the same group. LAST is the last definition of
699 // the associated resource, and is where any splay tree is stored.
701 function_info::merge_clobber_groups (clobber_info
*clobber1
,
702 clobber_info
*clobber2
,
705 if (clobber1
->is_in_group () && clobber2
->is_in_group ())
707 clobber_group
*group1
= clobber1
->group ();
708 clobber_group
*group2
= clobber2
->group ();
709 gcc_checking_assert (clobber1
== group1
->last_clobber ()
710 && clobber2
== group2
->first_clobber ());
712 if (def_splay_tree tree
= last
->splay_root ())
714 // Remove GROUP2 from the splay tree.
715 int comparison
= lookup_def (tree
, clobber2
->insn ());
716 gcc_checking_assert (comparison
== 0);
718 last
->set_splay_root (tree
.root ());
721 // Splice the trees together.
722 group1
->m_clobber_tree
.splice_next_tree (group2
->m_clobber_tree
);
724 // Bring the two extremes of GROUP2 under GROUP1. Any other
725 // clobbers in the group are updated lazily on demand.
726 clobber2
->set_group (group1
);
727 group2
->last_clobber ()->set_group (group1
);
728 group1
->set_last_clobber (group2
->last_clobber ());
730 // Record that GROUP2 is no more.
731 group2
->set_first_clobber (nullptr);
732 group2
->set_last_clobber (nullptr);
733 group2
->m_clobber_tree
= nullptr;
737 // In this case there can be no active splay tree.
738 gcc_assert (!last
->splay_root ());
739 if (clobber2
->is_in_group ())
740 prepend_clobber_to_group (clobber1
, clobber2
->group ());
742 append_clobber_to_group (clobber2
, need_clobber_group (clobber1
));
746 // GROUP spans INSN, and INSN now sets the resource that GROUP clobbers.
747 // Split GROUP around INSN and return the clobber that comes immediately
750 function_info::split_clobber_group (clobber_group
*group
, insn_info
*insn
)
752 // Search for either the previous or next clobber in the group.
753 // The result is less than zero if CLOBBER should come before NEIGHBOR
754 // or greater than zero if CLOBBER should come after NEIGHBOR.
755 int comparison
= lookup_clobber (group
->m_clobber_tree
, insn
);
756 gcc_checking_assert (comparison
!= 0);
757 clobber_info
*neighbor
= group
->m_clobber_tree
.root ();
759 clobber_tree tree1
, tree2
;
764 // NEIGHBOR is the last clobber in what will become the first group.
766 tree2
= tree1
.split_after_root ();
768 next
= as_a
<clobber_info
*> (prev
->next_def ());
772 // NEIGHBOR is the first clobber in what will become the second group.
774 tree1
= tree2
.split_before_root ();
776 prev
= as_a
<clobber_info
*> (next
->prev_def ());
779 // Use GROUP to hold PREV and earlier clobbers. Create a new group for
781 clobber_info
*last_clobber
= group
->last_clobber ();
782 clobber_group
*group1
= group
;
783 clobber_group
*group2
= allocate
<clobber_group
> (next
);
785 // Finish setting up GROUP1, making sure that the roots and extremities
786 // have a correct group pointer. Leave the rest to be updated lazily.
787 group1
->set_last_clobber (prev
);
788 tree1
->set_group (group1
);
789 prev
->set_group (group1
);
791 // Finish setting up GROUP2, with the same approach as for GROUP1.
792 group2
->set_first_clobber (next
);
793 group2
->set_last_clobber (last_clobber
);
794 next
->set_group (group2
);
795 tree2
->set_group (group2
);
796 last_clobber
->set_group (group2
);
801 // Add DEF to the end of the function's list of definitions of
802 // DEF->resource (). There is known to be no associated splay tree yet.
804 function_info::append_def (def_info
*def
)
806 gcc_checking_assert (!def
->has_def_links ());
807 def_info
**head
= &m_defs
[def
->regno () + 1];
808 def_info
*first
= *head
;
811 // This is the only definition of the resource.
812 def
->set_last_def (def
);
817 def_info
*prev
= first
->last_def ();
818 gcc_checking_assert (!prev
->splay_root ());
820 // Maintain the invariant that two clobbers must not appear in
821 // neighboring nodes of the splay tree.
822 auto *clobber
= dyn_cast
<clobber_info
*> (def
);
823 auto *prev_clobber
= dyn_cast
<clobber_info
*> (prev
);
824 if (clobber
&& prev_clobber
)
825 append_clobber_to_group (clobber
, need_clobber_group (prev_clobber
));
827 prev
->set_next_def (def
);
828 def
->set_prev_def (prev
);
829 first
->set_last_def (def
);
832 // Add DEF to the function's list of definitions of DEF->resource ().
833 // Also insert it into the associated splay tree, if there is one.
834 // DEF is not currently part of the list and is not in the splay tree.
836 function_info::add_def (def_info
*def
)
838 gcc_checking_assert (!def
->has_def_links ()
840 && !def
->m_has_been_superceded
);
841 def_info
**head
= &m_defs
[def
->regno () + 1];
842 def_info
*first
= *head
;
845 // This is the only definition of the resource.
846 def
->set_last_def (def
);
851 def_info
*last
= first
->last_def ();
852 insn_info
*insn
= def
->insn ();
855 def_node
*root
= nullptr;
856 def_info
*prev
= nullptr;
857 def_info
*next
= nullptr;
858 if (*insn
> *last
->insn ())
860 // This definition comes after all other definitions.
862 if (def_splay_tree tree
= last
->splay_root ())
864 tree
.splay_max_node ();
866 last
->set_splay_root (root
);
870 else if (*insn
< *first
->insn ())
872 // This definition comes before all other definitions.
874 if (def_splay_tree tree
= last
->splay_root ())
876 tree
.splay_min_node ();
878 last
->set_splay_root (root
);
884 // Search the splay tree for an insertion point.
885 def_splay_tree tree
= need_def_splay_tree (last
);
886 comparison
= lookup_def (tree
, insn
);
888 last
->set_splay_root (root
);
890 // Deal with cases in which we found an overlapping live range.
893 auto *group
= as_a
<clobber_group
*> (tree
.root ());
894 if (auto *clobber
= dyn_cast
<clobber_info
*> (def
))
896 add_clobber (clobber
, group
);
899 prev
= split_clobber_group (group
, insn
);
900 next
= prev
->next_def ();
902 // COMPARISON is < 0 if DEF comes before ROOT or > 0 if DEF comes
904 else if (comparison
< 0)
906 next
= first_def (root
);
907 prev
= next
->prev_def ();
911 prev
= last_def (root
);
912 next
= prev
->next_def ();
916 // See if we should merge CLOBBER with a neighboring clobber.
917 auto *clobber
= dyn_cast
<clobber_info
*> (def
);
918 auto *prev_clobber
= safe_dyn_cast
<clobber_info
*> (prev
);
919 auto *next_clobber
= safe_dyn_cast
<clobber_info
*> (next
);
920 // We shouldn't have consecutive clobber_groups.
921 gcc_checking_assert (!(clobber
&& prev_clobber
&& next_clobber
));
922 if (clobber
&& prev_clobber
)
923 append_clobber_to_group (clobber
, need_clobber_group (prev_clobber
));
924 else if (clobber
&& next_clobber
)
925 prepend_clobber_to_group (clobber
, need_clobber_group (next_clobber
));
928 // If DEF comes before ROOT, insert DEF to ROOT's left,
929 // otherwise insert DEF to ROOT's right.
930 def_node
*node
= need_def_node (def
);
931 def_splay_tree::insert_child (root
, comparison
>= 0, node
);
934 insert_def_after (def
, prev
);
936 insert_def_before (def
, next
);
939 // Remove DEF from the function's list of definitions of DEF->resource ().
940 // Also remove DEF from the associated splay tree, if there is one.
942 function_info::remove_def (def_info
*def
)
944 def_info
**head
= &m_defs
[def
->regno () + 1];
945 def_info
*first
= *head
;
946 gcc_checking_assert (first
);
947 if (first
->is_last_def ())
949 // DEF is the only definition of the resource.
950 gcc_checking_assert (first
== def
);
952 def
->clear_def_links ();
956 // If CLOBBER belongs to a clobber_group that contains other clobbers
957 // too, then we need to update the clobber_group and the list, but any
958 // splay tree that contains the clobber_group is unaffected.
959 if (auto *clobber
= dyn_cast
<clobber_info
*> (def
))
960 if (clobber
->is_in_group ())
962 clobber_group
*group
= clobber
->group ();
963 if (group
->first_clobber () != group
->last_clobber ())
965 remove_clobber (clobber
, group
);
970 // If we've created a splay tree for this resource, remove the entry
972 def_info
*last
= first
->last_def ();
973 if (def_splay_tree tree
= last
->splay_root ())
975 int comparison
= lookup_def (tree
, def
->insn ());
976 gcc_checking_assert (comparison
== 0);
978 last
->set_splay_root (tree
.root ());
981 // If the definition came between two clobbers, merge them into a single
983 auto *prev_clobber
= safe_dyn_cast
<clobber_info
*> (def
->prev_def ());
984 auto *next_clobber
= safe_dyn_cast
<clobber_info
*> (def
->next_def ());
985 if (prev_clobber
&& next_clobber
)
986 merge_clobber_groups (prev_clobber
, next_clobber
, last
);
988 remove_def_from_list (def
);
991 // Require DEF to have a splay tree that contains all non-phi uses.
993 function_info::need_use_splay_tree (set_info
*def
)
995 if (!def
->m_use_tree
)
996 for (use_info
*use
: def
->all_insn_uses ())
998 auto *use_node
= allocate
<splay_tree_node
<use_info
*>> (use
);
999 def
->m_use_tree
.insert_max_node (use_node
);
1003 // Compare two instructions by their position in a use splay tree. Return >0
1004 // if INSN1 comes after INSN2, <0 if INSN1 comes before INSN2, or 0 if they are
1005 // the same instruction.
1007 compare_use_insns (insn_info
*insn1
, insn_info
*insn2
)
1009 // Debug instructions go after nondebug instructions.
1010 int diff
= insn1
->is_debug_insn () - insn2
->is_debug_insn ();
1013 return insn1
->compare_with (insn2
);
1016 // Search TREE for a use in INSN. If such a use exists, install it as
1017 // the root of TREE and return 0. Otherwise arbitrarily choose between:
1019 // (1) Installing the closest preceding use as the root and returning 1.
1020 // (2) Installing the closest following use as the root and returning -1.
1022 rtl_ssa::lookup_use (splay_tree
<use_info
*> &tree
, insn_info
*insn
)
1024 auto compare
= [&](splay_tree_node
<use_info
*> *node
)
1026 return compare_use_insns (insn
, node
->value ()->insn ());
1028 return tree
.lookup (compare
);
1031 // Add USE to USE->def ()'s list of uses. inserting USE immediately before
1032 // BEFORE. USE is not currently in the list.
1034 // This routine should not be used for inserting phi uses.
1036 function_info::insert_use_before (use_info
*use
, use_info
*before
)
1038 gcc_checking_assert (!use
->has_use_links () && use
->is_in_any_insn ());
1040 set_info
*def
= use
->def ();
1042 use
->copy_prev_from (before
);
1043 use
->set_next_use (before
);
1045 if (use_info
*prev
= use
->prev_use ())
1046 prev
->set_next_use (use
);
1048 use
->def ()->set_first_use (use
);
1050 before
->set_prev_use (use
);
1051 if (use
->is_in_nondebug_insn () && before
->is_in_debug_insn_or_phi ())
1052 def
->last_use ()->set_last_nondebug_insn_use (use
);
1054 gcc_checking_assert (use
->check_integrity () && before
->check_integrity ());
1057 // Add USE to USE->def ()'s list of uses. inserting USE immediately after
1058 // AFTER. USE is not currently in the list.
1060 // This routine should not be used for inserting phi uses.
1062 function_info::insert_use_after (use_info
*use
, use_info
*after
)
1064 set_info
*def
= use
->def ();
1065 gcc_checking_assert (after
->is_in_any_insn ()
1066 && !use
->has_use_links ()
1067 && use
->is_in_any_insn ());
1069 use
->set_prev_use (after
);
1070 use
->copy_next_from (after
);
1072 after
->set_next_use (use
);
1074 if (use_info
*next
= use
->next_use ())
1076 // The last node doesn't change, but we might need to update its
1077 // last_nondebug_insn_use record.
1078 if (use
->is_in_nondebug_insn () && next
->is_in_debug_insn_or_phi ())
1079 def
->last_use ()->set_last_nondebug_insn_use (use
);
1080 next
->set_prev_use (use
);
1084 // USE is now the last node.
1085 if (use
->is_in_nondebug_insn ())
1086 use
->set_last_nondebug_insn_use (use
);
1087 def
->first_use ()->set_last_use (use
);
1090 gcc_checking_assert (use
->check_integrity () && after
->check_integrity ());
1093 // If USE has a known definition, add USE to that definition's list of uses.
1094 // Also update the associated splay tree, if any.
1096 function_info::add_use (use_info
*use
)
1098 gcc_checking_assert (!use
->has_use_links ()
1100 && !use
->m_has_been_superceded
);
1102 set_info
*def
= use
->def ();
1106 use_info
*first
= def
->first_use ();
1109 // This is the only use of the definition.
1110 use
->set_last_use (use
);
1111 if (use
->is_in_nondebug_insn ())
1112 use
->set_last_nondebug_insn_use (use
);
1114 def
->set_first_use (use
);
1116 gcc_checking_assert (use
->check_integrity ());
1120 if (use
->is_in_phi ())
1122 // Add USE at the end of the list, as the new first phi.
1123 use_info
*last
= first
->last_use ();
1125 use
->set_prev_use (last
);
1126 use
->copy_next_from (last
);
1128 last
->set_next_use (use
);
1129 first
->set_last_use (use
);
1131 gcc_checking_assert (use
->check_integrity ());
1135 // If there is currently no splay tree for this definition, see if can
1136 // get away with a pure list-based update.
1137 insn_info
*insn
= use
->insn ();
1138 auto quick_path
= [&]()
1140 // Check if USE should come before all current uses.
1141 if (first
->is_in_phi () || compare_use_insns (insn
, first
->insn ()) < 0)
1143 insert_use_before (use
, first
);
1147 // Check if USE should come after all current uses in the same
1148 // subsequence (i.e. the list of nondebug insn uses or the list
1149 // of debug insn uses).
1150 use_info
*last
= first
->last_use ();
1151 if (use
->is_in_debug_insn ())
1153 if (last
->is_in_phi ())
1157 last
= last
->last_nondebug_insn_use ();
1159 if (compare_use_insns (insn
, last
->insn ()) > 0)
1161 insert_use_after (use
, last
);
1167 if (!def
->m_use_tree
&& quick_path ())
1170 // Search the splay tree for an insertion point. COMPARISON is less
1171 // than zero if USE should come before NEIGHBOR, or greater than zero
1172 // if USE should come after NEIGHBOR.
1173 need_use_splay_tree (def
);
1174 int comparison
= lookup_use (def
->m_use_tree
, insn
);
1175 gcc_checking_assert (comparison
!= 0);
1176 splay_tree_node
<use_info
*> *neighbor
= def
->m_use_tree
.root ();
1178 // If USE comes before NEIGHBOR, insert USE to NEIGHBOR's left,
1179 // otherwise insert USE to NEIGHBOR's right.
1180 auto *use_node
= allocate
<splay_tree_node
<use_info
*>> (use
);
1181 def
->m_use_tree
.insert_child (neighbor
, comparison
> 0, use_node
);
1183 insert_use_after (use
, neighbor
->value ());
1185 insert_use_before (use
, neighbor
->value ());
1188 // If USE has a known definition, remove USE from that definition's list
1189 // of uses. Also remove if it from the associated splay tree, if any.
1191 function_info::remove_use (use_info
*use
)
1193 set_info
*def
= use
->def ();
1197 // Remove USE from the splay tree.
1198 if (def
->m_use_tree
&& use
->is_in_any_insn ())
1200 int comparison
= lookup_use (def
->m_use_tree
, use
->insn ());
1201 gcc_checking_assert (comparison
== 0);
1202 def
->m_use_tree
.remove_root ();
1205 use_info
*prev
= use
->prev_use ();
1206 use_info
*next
= use
->next_use ();
1208 use_info
*first
= def
->first_use ();
1209 use_info
*last
= first
->last_use ();
1210 if (last
->last_nondebug_insn_use () == use
)
1211 last
->set_last_nondebug_insn_use (prev
);
1214 next
->copy_prev_from (use
);
1216 first
->set_last_use (prev
);
1219 prev
->copy_next_from (use
);
1221 def
->set_first_use (next
);
1223 use
->clear_use_links ();
1224 gcc_checking_assert ((!prev
|| prev
->check_integrity ())
1225 && (!next
|| next
->check_integrity ()));
1228 // Allocate a temporary clobber_info for register REGNO in insn INSN,
1229 // including it in the region of the obstack governed by WATERMARK.
1230 // Return a new def_array that contains OLD_DEFS and the new clobber.
1232 // OLD_DEFS is known not to define REGNO.
1234 function_info::insert_temp_clobber (obstack_watermark
&watermark
,
1235 insn_info
*insn
, unsigned int regno
,
1238 gcc_checking_assert (watermark
== &m_temp_obstack
);
1239 auto *clobber
= allocate_temp
<clobber_info
> (insn
, regno
);
1240 clobber
->m_is_temp
= true;
1241 return insert_access (watermark
, clobber
, old_defs
);
1244 // A subroutine of make_uses_available. Try to make USE's definition
1245 // available at the head of BB. WILL_BE_DEBUG_USE is true if the
1246 // definition will be used only in debug instructions.
1250 // - If the use would have the same def () as USE, return USE.
1252 // - If BB already has a degenerate phi for the same definition,
1253 // return a temporary use of that phi.
1255 // - Otherwise, the use would need a new degenerate phi. Allocate a
1256 // temporary phi and return a temporary use of it.
1258 // Return null on failure.
1260 function_info::make_use_available (use_info
*use
, bb_info
*bb
,
1261 bool will_be_debug_use
)
1263 set_info
*def
= use
->def ();
1267 if (is_single_dominating_def (def
))
1270 // FIXME: Deliberately limited for fwprop compatibility testing.
1271 basic_block cfg_bb
= bb
->cfg_bb ();
1272 bb_info
*use_bb
= use
->bb ();
1273 if (single_pred_p (cfg_bb
)
1274 && single_pred (cfg_bb
) == use_bb
->cfg_bb ()
1275 && remains_available_on_exit (def
, use_bb
))
1277 if (def
->ebb () == bb
->ebb () || will_be_debug_use
)
1280 resource_info resource
= use
->resource ();
1281 set_info
*ultimate_def
= look_through_degenerate_phi (def
);
1283 // See if there is already a (degenerate) phi for DEF.
1284 insn_info
*phi_insn
= bb
->ebb ()->phi_insn ();
1286 def_lookup dl
= find_def (resource
, phi_insn
);
1287 if (set_info
*set
= dl
.matching_set ())
1289 // There is an existing phi.
1290 phi
= as_a
<phi_info
*> (set
);
1291 gcc_checking_assert (phi
->input_value (0) == ultimate_def
);
1295 // Create a temporary placeholder phi. This will become
1296 // permanent if the change is later committed.
1297 phi
= allocate_temp
<phi_info
> (phi_insn
, resource
, 0);
1298 auto *input
= allocate_temp
<use_info
> (phi
, resource
, ultimate_def
);
1299 input
->m_is_temp
= true;
1300 phi
->m_is_temp
= true;
1301 phi
->make_degenerate (input
);
1302 if (def_info
*prev
= dl
.prev_def ())
1303 phi
->set_prev_def (prev
);
1304 if (def_info
*next
= dl
.next_def ())
1305 phi
->set_next_def (next
);
1308 // Create a temporary use of the phi at the head of the first
1309 // block, since we know for sure that it's available there.
1310 insn_info
*use_insn
= bb
->ebb ()->first_bb ()->head_insn ();
1311 auto *new_use
= allocate_temp
<use_info
> (use_insn
, resource
, phi
);
1312 new_use
->m_is_temp
= true;
1318 // See the comment above the declaration.
1320 function_info::make_uses_available (obstack_watermark
&watermark
,
1321 use_array uses
, bb_info
*bb
,
1322 bool will_be_debug_uses
)
1324 unsigned int num_uses
= uses
.size ();
1328 auto **new_uses
= XOBNEWVEC (watermark
, access_info
*, num_uses
);
1329 for (unsigned int i
= 0; i
< num_uses
; ++i
)
1331 use_info
*use
= make_use_available (uses
[i
], bb
, will_be_debug_uses
);
1333 return use_array (access_array::invalid ());
1336 return use_array (new_uses
, num_uses
);
1339 // Return true if ACCESS1 can represent ACCESS2 and if ACCESS2 can
1340 // represent ACCESS1.
1342 can_merge_accesses (access_info
*access1
, access_info
*access2
)
1344 if (access1
== access2
)
1347 auto *use1
= dyn_cast
<use_info
*> (access1
);
1348 auto *use2
= dyn_cast
<use_info
*> (access2
);
1349 return use1
&& use2
&& use1
->def () == use2
->def ();
1352 // See the comment above the declaration.
1354 rtl_ssa::merge_access_arrays_base (obstack_watermark
&watermark
,
1355 access_array accesses1
,
1356 access_array accesses2
)
1358 if (accesses1
.empty ())
1360 if (accesses2
.empty ())
1363 auto i1
= accesses1
.begin ();
1364 auto end1
= accesses1
.end ();
1365 auto i2
= accesses2
.begin ();
1366 auto end2
= accesses2
.end ();
1368 access_array_builder
builder (watermark
);
1369 builder
.reserve (accesses1
.size () + accesses2
.size ());
1371 while (i1
!= end1
&& i2
!= end2
)
1373 access_info
*access1
= *i1
;
1374 access_info
*access2
= *i2
;
1376 unsigned int regno1
= access1
->regno ();
1377 unsigned int regno2
= access2
->regno ();
1378 if (regno1
== regno2
)
1380 if (!can_merge_accesses (access1
, access2
))
1381 return access_array::invalid ();
1383 builder
.quick_push (access1
);
1387 else if (regno1
< regno2
)
1389 builder
.quick_push (access1
);
1394 builder
.quick_push (access2
);
1398 for (; i1
!= end1
; ++i1
)
1399 builder
.quick_push (*i1
);
1400 for (; i2
!= end2
; ++i2
)
1401 builder
.quick_push (*i2
);
1403 return builder
.finish ();
1406 // See the comment above the declaration.
1408 rtl_ssa::insert_access_base (obstack_watermark
&watermark
,
1409 access_info
*access1
, access_array accesses2
)
1411 access_array_builder
builder (watermark
);
1412 builder
.reserve (1 + accesses2
.size ());
1414 unsigned int regno1
= access1
->regno ();
1415 auto i2
= accesses2
.begin ();
1416 auto end2
= accesses2
.end ();
1419 access_info
*access2
= *i2
;
1421 unsigned int regno2
= access2
->regno ();
1422 if (regno1
== regno2
)
1424 if (!can_merge_accesses (access1
, access2
))
1425 return access_array::invalid ();
1427 builder
.quick_push (access1
);
1432 else if (regno1
< regno2
)
1434 builder
.quick_push (access1
);
1440 builder
.quick_push (access2
);
1445 builder
.quick_push (access1
);
1446 for (; i2
!= end2
; ++i2
)
1447 builder
.quick_push (*i2
);
1449 return builder
.finish ();
1452 // See the comment above the declaration.
1454 rtl_ssa::remove_note_accesses_base (obstack_watermark
&watermark
,
1455 access_array accesses
)
1457 for (access_info
*access
: accesses
)
1458 if (access
->only_occurs_in_notes ())
1460 access_array_builder
builder (watermark
);
1461 builder
.reserve (accesses
.size ());
1462 for (access_info
*access2
: accesses
)
1463 if (!access2
->only_occurs_in_notes ())
1464 builder
.quick_push (access2
);
1465 return builder
.finish ();
1470 // Print RESOURCE to PP.
1472 rtl_ssa::pp_resource (pretty_printer
*pp
, resource_info resource
)
1474 resource
.print (pp
);
1477 // Print ACCESS to PP. FLAGS is a bitmask of PP_ACCESS_* flags.
1479 rtl_ssa::pp_access (pretty_printer
*pp
, const access_info
*access
,
1483 pp_string (pp
, "<null>");
1484 else if (auto *phi
= dyn_cast
<const phi_info
*> (access
))
1485 phi
->print (pp
, flags
);
1486 else if (auto *set
= dyn_cast
<const set_info
*> (access
))
1487 set
->print (pp
, flags
);
1488 else if (auto *clobber
= dyn_cast
<const clobber_info
*> (access
))
1489 clobber
->print (pp
, flags
);
1490 else if (auto *use
= dyn_cast
<const use_info
*> (access
))
1491 use
->print (pp
, flags
);
1493 pp_string (pp
, "??? Unknown access");
1496 // Print ACCESSES to PP. FLAGS is a bitmask of PP_ACCESS_* flags.
1498 rtl_ssa::pp_accesses (pretty_printer
*pp
, access_array accesses
,
1501 if (accesses
.empty ())
1502 pp_string (pp
, "none");
1505 bool is_first
= true;
1506 for (access_info
*access
: accesses
)
1511 pp_newline_and_indent (pp
, 0);
1512 pp_access (pp
, access
, flags
);
1517 // Print NODE to PP.
1519 rtl_ssa::pp_def_node (pretty_printer
*pp
, const def_node
*node
)
1522 pp_string (pp
, "<null>");
1523 else if (auto *group
= dyn_cast
<const clobber_group
*> (node
))
1525 else if (auto *set
= dyn_cast
<const set_node
*> (node
))
1528 pp_string (pp
, "??? Unknown def node");
1533 rtl_ssa::pp_def_mux (pretty_printer
*pp
, def_mux mux
)
1535 if (auto *node
= mux
.dyn_cast
<def_node
*> ())
1536 pp_def_node (pp
, node
);
1538 pp_access (pp
, mux
.as_a
<def_info
*> ());
1543 rtl_ssa::pp_def_lookup (pretty_printer
*pp
, def_lookup dl
)
1545 pp_string (pp
, "comparison result of ");
1546 pp_decimal_int (pp
, dl
.comparison
);
1547 pp_string (pp
, " for ");
1548 pp_newline_and_indent (pp
, 0);
1549 pp_def_mux (pp
, dl
.mux
);
1552 // Dump RESOURCE to FILE.
1554 dump (FILE *file
, resource_info resource
)
1556 dump_using (file
, pp_resource
, resource
);
1559 // Dump ACCESS to FILE. FLAGS is a bitmask of PP_ACCESS_* flags.
1561 dump (FILE *file
, const access_info
*access
, unsigned int flags
)
1563 dump_using (file
, pp_access
, access
, flags
);
1566 // Dump ACCESSES to FILE. FLAGS is a bitmask of PP_ACCESS_* flags.
1568 dump (FILE *file
, access_array accesses
, unsigned int flags
)
1570 dump_using (file
, pp_accesses
, accesses
, flags
);
1573 // Print NODE to FILE.
1575 dump (FILE *file
, const def_node
*node
)
1577 dump_using (file
, pp_def_node
, node
);
1580 // Print MUX to FILE.
1582 dump (FILE *file
, def_mux mux
)
1584 dump_using (file
, pp_def_mux
, mux
);
1587 // Print RESULT to FILE.
1589 dump (FILE *file
, def_lookup result
)
1591 dump_using (file
, pp_def_lookup
, result
);
1594 // Debug interfaces to the dump routines above.
1595 void debug (const resource_info
&x
) { dump (stderr
, x
); }
1596 void debug (const access_info
*x
) { dump (stderr
, x
); }
1597 void debug (const access_array
&x
) { dump (stderr
, x
); }
1598 void debug (const def_node
*x
) { dump (stderr
, x
); }
1599 void debug (const def_mux
&x
) { dump (stderr
, x
); }
1600 void debug (const def_lookup
&x
) { dump (stderr
, x
); }