1// Implementation of access-related functions for RTL SSA -*- C++ -*-
2// Copyright (C) 2020-2024 Free Software Foundation, Inc.
3//
4// This file is part of GCC.
5//
6// GCC is free software; you can redistribute it and/or modify it under
7// the terms of the GNU General Public License as published by the Free
8// Software Foundation; either version 3, or (at your option) any later
9// version.
10//
11// GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12// WARRANTY; without even the implied warranty of MERCHANTABILITY or
13// FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14// for more details.
15//
16// You should have received a copy of the GNU General Public License
17// along with GCC; see the file COPYING3. If not see
18// <http://www.gnu.org/licenses/>.
19
20#define INCLUDE_ALGORITHM
21#define INCLUDE_FUNCTIONAL
22#include "config.h"
23#include "system.h"
24#include "coretypes.h"
25#include "backend.h"
26#include "rtl.h"
27#include "df.h"
28#include "rtl-ssa.h"
29#include "rtl-ssa/internals.h"
30#include "rtl-ssa/internals.inl"
31
32using namespace rtl_ssa;
33
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.
36clobber_group *
37clobber_info::recompute_group ()
38{
39 using splay_tree = clobber_info::splay_tree;
40
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
44 // as the root.
45 clobber_info *cursor = m_parent;
46 auto find_group = [](clobber_info *node, unsigned int)
47 {
48 return node->m_group->has_been_superceded () ? nullptr : node->m_group;
49 };
50 clobber_group *group = splay_tree::splay_and_search (node: this, default_result: nullptr,
51 predicate: find_group);
52 gcc_checking_assert (m_parent);
53
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.
57 //
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)
62 cursor = this;
63
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)
67 {
68 cursor->m_group = group;
69 cursor = cursor->m_parent;
70 }
71
72 gcc_checking_assert (m_group == group);
73 return group;
74}
75
76// See the comment above the declaration.
77void
78resource_info::print_identifier (pretty_printer *pp) const
79{
80 if (is_mem ())
81 pp_string (pp, "mem");
82 else
83 {
84 char tmp[3 * sizeof (regno) + 2];
85 snprintf (s: tmp, maxlen: sizeof (tmp), format: "r%d", regno);
86 pp_string (pp, tmp);
87 }
88}
89
90// See the comment above the declaration.
91void
92resource_info::print_context (pretty_printer *pp) const
93{
94 if (HARD_REGISTER_NUM_P (regno))
95 {
96 if (const char *name = reg_names[regno])
97 {
98 pp_space (pp);
99 pp_left_paren (pp);
100 pp_string (pp, name);
101 if (mode != E_BLKmode)
102 {
103 pp_colon (pp);
104 pp_string (pp, GET_MODE_NAME (mode));
105 }
106 pp_right_paren (pp);
107 }
108 }
109 else if (is_reg ())
110 {
111 pp_space (pp);
112 pp_left_paren (pp);
113 if (mode != E_BLKmode)
114 {
115 pp_string (pp, GET_MODE_NAME (mode));
116 pp_space (pp);
117 }
118 pp_string (pp, "pseudo");
119 pp_right_paren (pp);
120 }
121}
122
123// See the comment above the declaration.
124void
125resource_info::print (pretty_printer *pp) const
126{
127 print_identifier (pp);
128 print_context (pp);
129}
130
131// Some properties can naturally be described using adjectives that attach
132// to nouns like "use" or "definition". Print such adjectives to PP.
133void
134access_info::print_prefix_flags (pretty_printer *pp) const
135{
136 if (m_is_temp)
137 pp_string (pp, "temporary ");
138 if (m_has_been_superceded)
139 pp_string (pp, "superceded ");
140}
141
142// Print properties not handled by print_prefix_flags to PP, putting
143// each property on a new line indented by two extra spaces.
144void
145access_info::print_properties_on_new_lines (pretty_printer *pp) const
146{
147 if (m_is_pre_post_modify)
148 {
149 pp_newline_and_indent (pp, 2);
150 pp_string (pp, "set by a pre/post-modify");
151 pp_indentation (pp) -= 2;
152 }
153 if (m_includes_address_uses)
154 {
155 pp_newline_and_indent (pp, 2);
156 pp_string (pp, "appears inside an address");
157 pp_indentation (pp) -= 2;
158 }
159 if (m_includes_read_writes)
160 {
161 pp_newline_and_indent (pp, 2);
162 pp_string (pp, "appears in a read/write context");
163 pp_indentation (pp) -= 2;
164 }
165 if (m_includes_subregs)
166 {
167 pp_newline_and_indent (pp, 2);
168 pp_string (pp, "appears inside a subreg");
169 pp_indentation (pp) -= 2;
170 }
171}
172
173// Return true if there are no known issues with the integrity of the
174// link information.
175inline bool
176use_info::check_integrity ()
177{
178 auto subsequence_id = [](use_info *use)
179 {
180 if (use->is_in_nondebug_insn ())
181 return 1;
182 if (use->is_in_debug_insn ())
183 return 2;
184 return 3;
185 };
186
187 use_info *prev = prev_use ();
188 use_info *next = next_use ();
189
190 if (prev && subsequence_id (prev) > subsequence_id (this))
191 return false;
192 if (next && subsequence_id (next) < subsequence_id (this))
193 return false;
194 if (m_is_last_nondebug_insn_use != calculate_is_last_nondebug_insn_use ())
195 return false;
196
197 if (!prev && last_use ()->next_use ())
198 return false;
199 if (!next)
200 if (use_info *use = last_nondebug_insn_use ())
201 if (!use->m_is_last_nondebug_insn_use)
202 return false;
203
204 return true;
205}
206
207// See the comment above the declaration.
208void
209use_info::print_location (pretty_printer *pp) const
210{
211 if (is_in_phi ())
212 pp_access (pp, phi (), flags: PP_ACCESS_INCLUDE_LOCATION);
213 else
214 insn ()->print_identifier_and_location (pp);
215}
216
217// See the comment above the declaration.
218void
219use_info::print_def (pretty_printer *pp) const
220{
221 if (const set_info *set = def ())
222 pp_access (pp, set, flags: 0);
223 else
224 {
225 pp_string (pp, "undefined ");
226 resource ().print (pp);
227 }
228}
229
230// See the comment above the declaration.
231void
232use_info::print (pretty_printer *pp, unsigned int flags) const
233{
234 print_prefix_flags (pp);
235
236 const set_info *set = def ();
237 if (set && set->mode () != mode ())
238 {
239 pp_string (pp, GET_MODE_NAME (mode ()));
240 pp_space (pp);
241 }
242
243 pp_string (pp, "use of ");
244 print_def (pp);
245 if (flags & PP_ACCESS_INCLUDE_LOCATION)
246 {
247 pp_string (pp, " by ");
248 print_location (pp);
249 }
250 if (set && (flags & PP_ACCESS_INCLUDE_LINKS))
251 {
252 pp_newline_and_indent (pp, 2);
253 pp_string (pp, "defined in ");
254 set->insn ()->print_location (pp);
255 pp_indentation (pp) -= 2;
256 }
257 if (flags & PP_ACCESS_INCLUDE_PROPERTIES)
258 print_properties_on_new_lines (pp);
259}
260
261// See the comment above the declaration.
262void
263def_info::print_identifier (pretty_printer *pp) const
264{
265 resource ().print_identifier (pp);
266 pp_colon (pp);
267 insn ()->print_identifier (pp);
268 resource ().print_context (pp);
269}
270
271// See the comment above the declaration.
272void
273def_info::print_location (pretty_printer *pp) const
274{
275 insn ()->print_identifier_and_location (pp);
276}
277
278// See the comment above the declaration.
279void
280clobber_info::print (pretty_printer *pp, unsigned int flags) const
281{
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)
288 {
289 pp_string (pp, " in ");
290 insn ()->print_location (pp);
291 }
292 if (flags & PP_ACCESS_INCLUDE_PROPERTIES)
293 print_properties_on_new_lines (pp);
294}
295
296// See the comment above the declaration.
297void
298set_info::print_uses_on_new_lines (pretty_printer *pp) const
299{
300 for (const use_info *use : all_uses ())
301 {
302 pp_newline_and_indent (pp, 2);
303 if (use->is_live_out_use ())
304 {
305 pp_string (pp, "live out from ");
306 use->insn ()->print_location (pp);
307 }
308 else
309 {
310 pp_string (pp, "used by ");
311 use->print_location (pp);
312 }
313 pp_indentation (pp) -= 2;
314 }
315 if (m_use_tree)
316 {
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)
322 {
323 pp_string (pp, "use by ");
324 node->value ()->print_location (pp);
325 };
326 m_use_tree.print (pp, node: m_use_tree.root (), printer: print_use);
327 pp_indentation (pp) -= 4;
328 }
329}
330
331// See the comment above the declaration.
332void
333set_info::print (pretty_printer *pp, unsigned int flags) const
334{
335 print_prefix_flags (pp);
336 pp_string (pp, "set ");
337 print_identifier (pp);
338 if (flags & PP_ACCESS_INCLUDE_LOCATION)
339 {
340 pp_string (pp, " in ");
341 insn ()->print_location (pp);
342 }
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);
347}
348
349// See the comment above the declaration.
350void
351phi_info::print (pretty_printer *pp, unsigned int flags) const
352{
353 print_prefix_flags (pp);
354 pp_string (pp, "phi node ");
355 print_identifier (pp);
356 if (flags & PP_ACCESS_INCLUDE_LOCATION)
357 {
358 pp_string (pp, " in ");
359 insn ()->print_location (pp);
360 }
361
362 if (flags & PP_ACCESS_INCLUDE_PROPERTIES)
363 print_properties_on_new_lines (pp);
364
365 if (flags & PP_ACCESS_INCLUDE_LINKS)
366 {
367 basic_block cfg_bb = bb ()->cfg_bb ();
368 pp_newline_and_indent (pp, 2);
369 pp_string (pp, "inputs:");
370 unsigned int i = 0;
371 for (const use_info *input : inputs ())
372 {
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);
377 pp_colon (pp);
378 pp_space (pp);
379 input->print_def (pp);
380 pp_indentation (pp) -= 2;
381 i += 1;
382 }
383 pp_indentation (pp) -= 2;
384
385 print_uses_on_new_lines (pp);
386 }
387}
388
389// See the comment above the declaration.
390void
391set_node::print (pretty_printer *pp) const
392{
393 pp_access (pp, first_def ());
394}
395
396// See the comment above the declaration.
397clobber_info *
398clobber_group::prev_clobber (insn_info *insn) const
399{
400 auto &tree = const_cast<clobber_tree &> (m_clobber_tree);
401 int comparison = lookup_clobber (tree, insn);
402 if (comparison <= 0)
403 return dyn_cast<clobber_info *> (p: tree.root ()->prev_def ());
404 return tree.root ();
405}
406
407// See the comment above the declaration.
408clobber_info *
409clobber_group::next_clobber (insn_info *insn) const
410{
411 auto &tree = const_cast<clobber_tree &> (m_clobber_tree);
412 int comparison = lookup_clobber (tree, insn);
413 if (comparison >= 0)
414 return dyn_cast<clobber_info *> (p: tree.root ()->next_def ());
415 return tree.root ();
416}
417
418// See the comment above the declaration.
419void
420clobber_group::print (pretty_printer *pp) const
421{
422 auto print_clobber = [](pretty_printer *pp, const def_info *clobber)
423 {
424 pp_access (pp, clobber);
425 };
426 pp_string (pp, "grouped clobber");
427 for (const def_info *clobber : clobbers ())
428 {
429 pp_newline_and_indent (pp, 2);
430 print_clobber (pp, clobber);
431 pp_indentation (pp) -= 2;
432 }
433 pp_newline_and_indent (pp, 2);
434 pp_string (pp, "splay tree");
435 pp_newline_and_indent (pp, 2);
436 m_clobber_tree.print (pp, printer: print_clobber);
437 pp_indentation (pp) -= 4;
438}
439
440// See the comment above the declaration.
441def_info *
442def_lookup::prev_def (insn_info *insn) const
443{
444 if (mux && comparison == 0)
445 if (auto *node = mux.dyn_cast<def_node *> ())
446 if (auto *group = dyn_cast<clobber_group *> (p: node))
447 if (clobber_info *clobber = group->prev_clobber (insn))
448 return clobber;
449
450 return last_def_of_prev_group ();
451}
452
453// See the comment above the declaration.
454def_info *
455def_lookup::next_def (insn_info *insn) const
456{
457 if (mux && comparison == 0)
458 if (auto *node = mux.dyn_cast<def_node *> ())
459 if (auto *group = dyn_cast<clobber_group *> (p: node))
460 if (clobber_info *clobber = group->next_clobber (insn))
461 return clobber;
462
463 return first_def_of_next_group ();
464}
465
466// Return a clobber_group for CLOBBER, creating one if CLOBBER doesn't
467// already belong to a group.
468clobber_group *
469function_info::need_clobber_group (clobber_info *clobber)
470{
471 if (clobber->is_in_group ())
472 return clobber->group ();
473 return allocate<clobber_group> (args: clobber);
474}
475
476// Return a def_node for inserting DEF into the associated resource's
477// splay tree. Use a clobber_group if DEF is a clobber and a set_node
478// otherwise.
479def_node *
480function_info::need_def_node (def_info *def)
481{
482 if (auto *clobber = dyn_cast<clobber_info *> (p: def))
483 return need_clobber_group (clobber);
484 return allocate<set_node> (args: as_a<set_info *> (p: def));
485}
486
487// LAST is the last thing to define LAST->resource (), and is where any
488// splay tree root for LAST->resource () is stored. Require such a splay tree
489// to exist, creating a new one if necessary. Return the root of the tree.
490//
491// The caller must call LAST->set_splay_root after it has finished with
492// the splay tree.
493def_splay_tree
494function_info::need_def_splay_tree (def_info *last)
495{
496 if (def_node *root = last->splay_root ())
497 return root;
498
499 // Use a left-spine rooted at the last node.
500 def_node *root = need_def_node (def: last);
501 def_node *parent = root;
502 while (def_info *prev = first_def (node: parent)->prev_def ())
503 {
504 def_node *node = need_def_node (def: prev);
505 def_splay_tree::insert_child (node: parent, index: 0, child: node);
506 parent = node;
507 }
508 return root;
509}
510
511// Search TREE for either:
512//
513// - a set_info at INSN or
514// - a clobber_group whose range includes INSN
515//
516// If such a node exists, install it as the root of TREE and return 0.
517// Otherwise arbitrarily choose between:
518//
519// (1) Installing the closest preceding node as the root and returning 1.
520// (2) Installing the closest following node as the root and returning -1.
521//
522// Note that this routine should not be used to check whether INSN
523// itself defines a resource; that can be checked more cheaply using
524// find_access_index.
525int
526rtl_ssa::lookup_def (def_splay_tree &tree, insn_info *insn)
527{
528 auto go_left = [&](def_node *node)
529 {
530 return *insn < *first_def (node)->insn ();
531 };
532 auto go_right = [&](def_node *node)
533 {
534 return *insn > *last_def (node)->insn ();
535 };
536 return tree.lookup (want_something_smaller: go_left, want_something_bigger: go_right);
537}
538
539// Search TREE for a clobber in INSN. If such a clobber exists, install
540// it as the root of TREE and return 0. Otherwise arbitrarily choose between:
541//
542// (1) Installing the closest preceding clobber as the root and returning 1.
543// (2) Installing the closest following clobber as the root and returning -1.
544int
545rtl_ssa::lookup_clobber (clobber_tree &tree, insn_info *insn)
546{
547 auto compare = [&](clobber_info *clobber)
548 {
549 return insn->compare_with (other: clobber->insn ());
550 };
551 return tree.lookup (compare);
552}
553
554// Search for a definition of RESOURCE at INSN and return the result of
555// the search as a def_lookup. See the comment above the class for more
556// details.
557def_lookup
558function_info::find_def (resource_info resource, insn_info *insn)
559{
560 def_info *first = m_defs[resource.regno + 1];
561 if (!first)
562 // There are no nodes. The comparison result is pretty meaningless
563 // in this case.
564 return { .mux: nullptr, .comparison: -1 };
565
566 // See whether the first node matches.
567 auto first_result = clobber_group_or_single_def (def: first);
568 if (*insn <= *last_def (mux: first_result)->insn ())
569 {
570 int comparison = (*insn >= *first->insn () ? 0 : -1);
571 return { .mux: first_result, .comparison: comparison };
572 }
573
574 // See whether the last node matches.
575 def_info *last = first->last_def ();
576 auto last_result = clobber_group_or_single_def (def: last);
577 if (*insn >= *first_def (mux: last_result)->insn ())
578 {
579 int comparison = (*insn <= *last->insn () ? 0 : 1);
580 return { .mux: last_result, .comparison: comparison };
581 }
582
583 // Resort to using a splay tree to search for the result.
584 def_splay_tree tree = need_def_splay_tree (last);
585 int comparison = lookup_def (tree, insn);
586 last->set_splay_root (tree.root ());
587 return { .mux: tree.root (), .comparison: comparison };
588}
589
590// Add DEF to the function's list of definitions of DEF->resource (),
591// inserting DEF immediately before BEFORE. DEF is not currently in the list.
592void
593function_info::insert_def_before (def_info *def, def_info *before)
594{
595 gcc_checking_assert (!def->has_def_links ()
596 && *before->insn () > *def->insn ());
597
598 def->copy_prev_from (other: before);
599 if (def_info *prev = def->prev_def ())
600 {
601 gcc_checking_assert (*prev->insn () < *def->insn ());
602 prev->set_next_def (def);
603 }
604 else
605 m_defs[def->regno () + 1] = def;
606
607 def->set_next_def (before);
608 before->set_prev_def (def);
609}
610
611// Add DEF to the function's list of definitions of DEF->resource (),
612// inserting DEF immediately after AFTER. DEF is not currently in the list.
613void
614function_info::insert_def_after (def_info *def, def_info *after)
615{
616 gcc_checking_assert (!def->has_def_links ()
617 && *after->insn () < *def->insn ());
618
619 def->copy_next_from (other: after);
620 if (def_info *next = def->next_def ())
621 {
622 gcc_checking_assert (*next->insn () > *def->insn ());
623 next->set_prev_def (def);
624 }
625 else
626 m_defs[def->regno () + 1]->set_last_def (def);
627
628 def->set_prev_def (after);
629 after->set_next_def (def);
630}
631
632// Remove DEF from the function's list of definitions of DEF->resource ().
633void
634function_info::remove_def_from_list (def_info *def)
635{
636 def_info *prev = def->prev_def ();
637 def_info *next = def->next_def ();
638
639 if (next)
640 next->copy_prev_from (other: def);
641 else
642 m_defs[def->regno () + 1]->set_last_def (prev);
643
644 if (prev)
645 prev->copy_next_from (other: def);
646 else
647 m_defs[def->regno () + 1] = next;
648
649 def->clear_def_links ();
650}
651
652// Add CLOBBER to GROUP and insert it into the function's list of
653// accesses to CLOBBER->resource (). CLOBBER is not currently part
654// of an active group and is not currently in the list.
655void
656function_info::add_clobber (clobber_info *clobber, clobber_group *group)
657{
658 // Search for either the previous or next clobber in the group.
659 // The result is less than zero if CLOBBER should come before NEIGHBOR
660 // or greater than zero if CLOBBER should come after NEIGHBOR.
661 int comparison = lookup_clobber (tree&: group->m_clobber_tree, insn: clobber->insn ());
662 gcc_checking_assert (comparison != 0);
663 clobber_info *neighbor = group->m_clobber_tree.root ();
664
665 // Since HEIGHBOR is now the root of the splay tree, its group needs
666 // to be up-to-date.
667 neighbor->update_group (group);
668
669 // If CLOBBER comes before NEIGHBOR, insert CLOBBER to NEIGHBOR's left,
670 // otherwise insert CLOBBER to NEIGHBOR's right.
671 clobber_info::splay_tree::insert_child (node: neighbor, index: comparison > 0, child: clobber);
672 clobber->set_group (group);
673
674 // Insert the clobber into the function-wide list and update the
675 // bounds of the group.
676 if (comparison > 0)
677 {
678 insert_def_after (def: clobber, after: neighbor);
679 if (neighbor == group->last_clobber ())
680 group->set_last_clobber (clobber);
681 }
682 else
683 {
684 insert_def_before (def: clobber, before: neighbor);
685 if (neighbor == group->first_clobber ())
686 group->set_first_clobber (clobber);
687 }
688}
689
690// Remove CLOBBER from GROUP, given that GROUP contains other clobbers too.
691// Also remove CLOBBER from the function's list of accesses to
692// CLOBBER->resource ().
693void
694function_info::remove_clobber (clobber_info *clobber, clobber_group *group)
695{
696 if (clobber == group->first_clobber ())
697 {
698 auto *new_first = as_a<clobber_info *> (p: clobber->next_def ());
699 group->set_first_clobber (new_first);
700 new_first->update_group (group);
701 }
702 else if (clobber == group->last_clobber ())
703 {
704 auto *new_last = as_a<clobber_info *> (p: clobber->prev_def ());
705 group->set_last_clobber (new_last);
706 new_last->update_group (group);
707 }
708
709 clobber_info *replacement = clobber_info::splay_tree::remove_node (node: clobber);
710 if (clobber == group->m_clobber_tree.root ())
711 {
712 group->m_clobber_tree = replacement;
713 replacement->update_group (group);
714 }
715 clobber->set_group (nullptr);
716
717 remove_def_from_list (def: clobber);
718}
719
720// Add CLOBBER immediately before the first clobber in GROUP, given that
721// CLOBBER is not currently part of any group.
722void
723function_info::prepend_clobber_to_group (clobber_info *clobber,
724 clobber_group *group)
725{
726 clobber_info *next = group->first_clobber ();
727 clobber_info::splay_tree::insert_child (node: next, index: 0, child: clobber);
728 group->set_first_clobber (clobber);
729 clobber->set_group (group);
730}
731
732// Add CLOBBER immediately after the last clobber in GROUP, given that
733// CLOBBER is not currently part of any group.
734void
735function_info::append_clobber_to_group (clobber_info *clobber,
736 clobber_group *group)
737{
738 clobber_info *prev = group->last_clobber ();
739 clobber_info::splay_tree::insert_child (node: prev, index: 1, child: clobber);
740 group->set_last_clobber (clobber);
741 clobber->set_group (group);
742}
743
744// Put CLOBBER1 and CLOBBER2 into the same clobber_group, given that
745// CLOBBER1 occurs immediately before CLOBBER2 and that the two clobbers
746// are not currently in the same group. LAST is the last definition of
747// the associated resource, and is where any splay tree is stored.
748void
749function_info::merge_clobber_groups (clobber_info *clobber1,
750 clobber_info *clobber2,
751 def_info *last)
752{
753 if (clobber1->is_in_group () && clobber2->is_in_group ())
754 {
755 clobber_group *group1 = clobber1->group ();
756 clobber_group *group2 = clobber2->group ();
757 gcc_checking_assert (clobber1 == group1->last_clobber ()
758 && clobber2 == group2->first_clobber ());
759
760 if (def_splay_tree tree = last->splay_root ())
761 {
762 // Remove GROUP2 from the splay tree.
763 int comparison = lookup_def (tree, insn: clobber2->insn ());
764 gcc_checking_assert (comparison == 0);
765 tree.remove_root ();
766 last->set_splay_root (tree.root ());
767 }
768
769 // Splice the trees together.
770 group1->m_clobber_tree.splice_next_tree (next_tree: group2->m_clobber_tree);
771
772 // Bring the two extremes of GROUP2 under GROUP1. Any other
773 // clobbers in the group are updated lazily on demand.
774 clobber2->set_group (group1);
775 group2->last_clobber ()->set_group (group1);
776 group1->set_last_clobber (group2->last_clobber ());
777
778 // Record that GROUP2 is no more.
779 group2->set_first_clobber (nullptr);
780 group2->set_last_clobber (nullptr);
781 group2->m_clobber_tree = nullptr;
782 }
783 else
784 {
785 // In this case there can be no active splay tree.
786 gcc_assert (!last->splay_root ());
787 if (clobber2->is_in_group ())
788 prepend_clobber_to_group (clobber: clobber1, group: clobber2->group ());
789 else
790 append_clobber_to_group (clobber: clobber2, group: need_clobber_group (clobber: clobber1));
791 }
792}
793
794// GROUP spans INSN, and INSN now sets the resource that GROUP clobbers.
795// Split GROUP around INSN and return the clobber that comes immediately
796// before INSN.
797//
798// The resource that GROUP clobbers is known to have an associated
799// splay tree.
800clobber_info *
801function_info::split_clobber_group (clobber_group *group, insn_info *insn)
802{
803 // Search for either the previous or next clobber in the group.
804 // The result is less than zero if CLOBBER should come before NEIGHBOR
805 // or greater than zero if CLOBBER should come after NEIGHBOR.
806 clobber_tree &tree1 = group->m_clobber_tree;
807 int comparison = lookup_clobber (tree&: tree1, insn);
808 gcc_checking_assert (comparison != 0);
809 clobber_info *neighbor = tree1.root ();
810
811 clobber_tree tree2;
812 clobber_info *prev;
813 clobber_info *next;
814 if (comparison > 0)
815 {
816 // NEIGHBOR is the last clobber in what will become the first group.
817 tree2 = tree1.split_after_root ();
818 prev = neighbor;
819 next = as_a<clobber_info *> (p: prev->next_def ());
820 }
821 else
822 {
823 // NEIGHBOR is the first clobber in what will become the second group.
824 tree2 = neighbor;
825 tree1 = tree2.split_before_root ();
826 next = neighbor;
827 prev = as_a<clobber_info *> (p: next->prev_def ());
828 }
829
830 // Use GROUP to hold PREV and earlier clobbers. Create a new group for
831 // NEXT onwards.
832 clobber_info *last_clobber = group->last_clobber ();
833 clobber_group *group1 = group;
834 clobber_group *group2 = allocate<clobber_group> (args: next);
835
836 // Finish setting up GROUP1, making sure that the roots and extremities
837 // have a correct group pointer. Leave the rest to be updated lazily.
838 group1->set_last_clobber (prev);
839 tree1->set_group (group1);
840 prev->set_group (group1);
841
842 // Finish setting up GROUP2, with the same approach as for GROUP1.
843 group2->set_first_clobber (next);
844 group2->set_last_clobber (last_clobber);
845 next->set_group (group2);
846 tree2->set_group (group2);
847 last_clobber->set_group (group2);
848
849 // Insert GROUP2 into the splay tree as an immediate successor of GROUP1.
850 def_splay_tree::insert_child (node: group1, index: 1, child: group2);
851
852 return prev;
853}
854
855// Add DEF to the end of the function's list of definitions of
856// DEF->resource (). There is known to be no associated splay tree yet.
857void
858function_info::append_def (def_info *def)
859{
860 gcc_checking_assert (!def->has_def_links ());
861 def_info **head = &m_defs[def->regno () + 1];
862 def_info *first = *head;
863 if (!first)
864 {
865 // This is the only definition of the resource.
866 def->set_last_def (def);
867 *head = def;
868 return;
869 }
870
871 def_info *prev = first->last_def ();
872 gcc_checking_assert (!prev->splay_root ());
873
874 // Maintain the invariant that two clobbers must not appear in
875 // neighboring nodes of the splay tree.
876 auto *clobber = dyn_cast<clobber_info *> (p: def);
877 auto *prev_clobber = dyn_cast<clobber_info *> (p: prev);
878 if (clobber && prev_clobber)
879 append_clobber_to_group (clobber, group: need_clobber_group (clobber: prev_clobber));
880
881 prev->set_next_def (def);
882 def->set_prev_def (prev);
883 first->set_last_def (def);
884}
885
886// Add DEF to the function's list of definitions of DEF->resource ().
887// Also insert it into the associated splay tree, if there is one.
888// DEF is not currently part of the list and is not in the splay tree.
889void
890function_info::add_def (def_info *def)
891{
892 gcc_checking_assert (!def->has_def_links ()
893 && !def->m_is_temp
894 && !def->m_has_been_superceded);
895 def_info **head = &m_defs[def->regno () + 1];
896 def_info *first = *head;
897 if (!first)
898 {
899 // This is the only definition of the resource.
900 def->set_last_def (def);
901 *head = def;
902 return;
903 }
904
905 def_info *last = first->last_def ();
906 insn_info *insn = def->insn ();
907
908 int comparison;
909 def_node *root = nullptr;
910 def_info *prev = nullptr;
911 def_info *next = nullptr;
912 if (*insn > *last->insn ())
913 {
914 // This definition comes after all other definitions.
915 comparison = 1;
916 if (def_splay_tree tree = last->splay_root ())
917 {
918 tree.splay_max_node ();
919 root = tree.root ();
920 last->set_splay_root (root);
921 }
922 prev = last;
923 }
924 else if (*insn < *first->insn ())
925 {
926 // This definition comes before all other definitions.
927 comparison = -1;
928 if (def_splay_tree tree = last->splay_root ())
929 {
930 tree.splay_min_node ();
931 root = tree.root ();
932 last->set_splay_root (root);
933 }
934 next = first;
935 }
936 else
937 {
938 // Search the splay tree for an insertion point.
939 def_splay_tree tree = need_def_splay_tree (last);
940 comparison = lookup_def (tree, insn);
941 root = tree.root ();
942 last->set_splay_root (root);
943
944 // Deal with cases in which we found an overlapping live range.
945 if (comparison == 0)
946 {
947 auto *group = as_a<clobber_group *> (p: tree.root ());
948 if (auto *clobber = dyn_cast<clobber_info *> (p: def))
949 {
950 add_clobber (clobber, group);
951 return;
952 }
953 prev = split_clobber_group (group, insn);
954 next = prev->next_def ();
955 }
956 // COMPARISON is < 0 if DEF comes before ROOT or > 0 if DEF comes
957 // after ROOT.
958 else if (comparison < 0)
959 {
960 next = first_def (node: root);
961 prev = next->prev_def ();
962 }
963 else
964 {
965 prev = last_def (node: root);
966 next = prev->next_def ();
967 }
968 }
969
970 // See if we should merge CLOBBER with a neighboring clobber.
971 auto *clobber = dyn_cast<clobber_info *> (p: def);
972 auto *prev_clobber = safe_dyn_cast<clobber_info *> (p: prev);
973 auto *next_clobber = safe_dyn_cast<clobber_info *> (p: next);
974 // We shouldn't have consecutive clobber_groups.
975 gcc_checking_assert (!(clobber && prev_clobber && next_clobber));
976 if (clobber && prev_clobber)
977 append_clobber_to_group (clobber, group: need_clobber_group (clobber: prev_clobber));
978 else if (clobber && next_clobber)
979 prepend_clobber_to_group (clobber, group: need_clobber_group (clobber: next_clobber));
980 else if (root)
981 {
982 // If DEF comes before ROOT, insert DEF to ROOT's left,
983 // otherwise insert DEF to ROOT's right.
984 def_node *node = need_def_node (def);
985 def_splay_tree::insert_child (node: root, index: comparison >= 0, child: node);
986 }
987 if (prev)
988 insert_def_after (def, after: prev);
989 else
990 insert_def_before (def, before: next);
991}
992
993// Remove DEF from the function's list of definitions of DEF->resource ().
994// Also remove DEF from the associated splay tree, if there is one.
995void
996function_info::remove_def (def_info *def)
997{
998 def_info **head = &m_defs[def->regno () + 1];
999 def_info *first = *head;
1000 gcc_checking_assert (first);
1001 if (first->is_last_def ())
1002 {
1003 // DEF is the only definition of the resource.
1004 gcc_checking_assert (first == def);
1005 *head = nullptr;
1006 def->clear_def_links ();
1007 return;
1008 }
1009
1010 // If CLOBBER belongs to a clobber_group that contains other clobbers
1011 // too, then we need to update the clobber_group and the list, but any
1012 // splay tree that contains the clobber_group is unaffected.
1013 if (auto *clobber = dyn_cast<clobber_info *> (p: def))
1014 if (clobber->is_in_group ())
1015 {
1016 clobber_group *group = clobber->group ();
1017 if (group->first_clobber () != group->last_clobber ())
1018 {
1019 remove_clobber (clobber, group);
1020 return;
1021 }
1022 }
1023
1024 // If we've created a splay tree for this resource, remove the entry
1025 // for DEF.
1026 def_info *last = first->last_def ();
1027 if (def_splay_tree tree = last->splay_root ())
1028 {
1029 int comparison = lookup_def (tree, insn: def->insn ());
1030 gcc_checking_assert (comparison == 0);
1031 tree.remove_root ();
1032 last->set_splay_root (tree.root ());
1033 }
1034
1035 // If the definition came between two clobbers, merge them into a single
1036 // group.
1037 auto *prev_clobber = safe_dyn_cast<clobber_info *> (p: def->prev_def ());
1038 auto *next_clobber = safe_dyn_cast<clobber_info *> (p: def->next_def ());
1039 if (prev_clobber && next_clobber)
1040 merge_clobber_groups (clobber1: prev_clobber, clobber2: next_clobber, last);
1041
1042 remove_def_from_list (def);
1043}
1044
1045// Require DEF to have a splay tree that contains all non-phi uses.
1046void
1047function_info::need_use_splay_tree (set_info *def)
1048{
1049 if (!def->m_use_tree)
1050 for (use_info *use : def->all_insn_uses ())
1051 {
1052 auto *use_node = allocate<splay_tree_node<use_info *>> (args: use);
1053 def->m_use_tree.insert_max_node (new_node: use_node);
1054 }
1055}
1056
1057// Compare two instructions by their position in a use splay tree. Return >0
1058// if INSN1 comes after INSN2, <0 if INSN1 comes before INSN2, or 0 if they are
1059// the same instruction.
1060static inline int
1061compare_use_insns (insn_info *insn1, insn_info *insn2)
1062{
1063 // Debug instructions go after nondebug instructions.
1064 int diff = insn1->is_debug_insn () - insn2->is_debug_insn ();
1065 if (diff != 0)
1066 return diff;
1067 return insn1->compare_with (other: insn2);
1068}
1069
1070// Search TREE for a use in INSN. If such a use exists, install it as
1071// the root of TREE and return 0. Otherwise arbitrarily choose between:
1072//
1073// (1) Installing the closest preceding use as the root and returning 1.
1074// (2) Installing the closest following use as the root and returning -1.
1075int
1076rtl_ssa::lookup_use (splay_tree<use_info *> &tree, insn_info *insn)
1077{
1078 auto compare = [&](splay_tree_node<use_info *> *node)
1079 {
1080 return compare_use_insns (insn1: insn, insn2: node->value ()->insn ());
1081 };
1082 return tree.lookup (compare);
1083}
1084
1085// Add USE to USE->def ()'s list of uses. inserting USE immediately before
1086// BEFORE. USE is not currently in the list.
1087//
1088// This routine should not be used for inserting phi uses.
1089void
1090function_info::insert_use_before (use_info *use, use_info *before)
1091{
1092 gcc_checking_assert (!use->has_use_links () && use->is_in_any_insn ());
1093
1094 set_info *def = use->def ();
1095
1096 use->copy_prev_from (other: before);
1097 use->set_next_use (before);
1098
1099 if (use_info *prev = use->prev_use ())
1100 prev->set_next_use (use);
1101 else
1102 use->def ()->set_first_use (use);
1103
1104 before->set_prev_use (use);
1105 if (use->is_in_nondebug_insn () && before->is_in_debug_insn_or_phi ())
1106 def->last_use ()->set_last_nondebug_insn_use (use);
1107
1108 gcc_checking_assert (use->check_integrity () && before->check_integrity ());
1109}
1110
1111// Add USE to USE->def ()'s list of uses. inserting USE immediately after
1112// AFTER. USE is not currently in the list.
1113//
1114// This routine should not be used for inserting phi uses.
1115void
1116function_info::insert_use_after (use_info *use, use_info *after)
1117{
1118 set_info *def = use->def ();
1119 gcc_checking_assert (after->is_in_any_insn ()
1120 && !use->has_use_links ()
1121 && use->is_in_any_insn ());
1122
1123 use->set_prev_use (after);
1124 use->copy_next_from (other: after);
1125
1126 after->set_next_use (use);
1127
1128 if (use_info *next = use->next_use ())
1129 {
1130 // The last node doesn't change, but we might need to update its
1131 // last_nondebug_insn_use record.
1132 if (use->is_in_nondebug_insn () && next->is_in_debug_insn_or_phi ())
1133 def->last_use ()->set_last_nondebug_insn_use (use);
1134 next->set_prev_use (use);
1135 }
1136 else
1137 {
1138 // USE is now the last node.
1139 if (use->is_in_nondebug_insn ())
1140 use->set_last_nondebug_insn_use (use);
1141 def->first_use ()->set_last_use (use);
1142 }
1143
1144 gcc_checking_assert (use->check_integrity () && after->check_integrity ());
1145}
1146
1147// If USE has a known definition, add USE to that definition's list of uses.
1148// Also update the associated splay tree, if any.
1149void
1150function_info::add_use (use_info *use)
1151{
1152 gcc_checking_assert (!use->has_use_links ()
1153 && !use->m_is_temp
1154 && !use->m_has_been_superceded);
1155
1156 set_info *def = use->def ();
1157 if (!def)
1158 return;
1159
1160 use_info *first = def->first_use ();
1161 if (!first)
1162 {
1163 // This is the only use of the definition.
1164 use->set_last_use (use);
1165 if (use->is_in_nondebug_insn ())
1166 use->set_last_nondebug_insn_use (use);
1167
1168 def->set_first_use (use);
1169
1170 gcc_checking_assert (use->check_integrity ());
1171 return;
1172 }
1173
1174 if (use->is_in_phi ())
1175 {
1176 // Add USE at the end of the list, as the new first phi.
1177 use_info *last = first->last_use ();
1178
1179 use->set_prev_use (last);
1180 use->copy_next_from (other: last);
1181
1182 last->set_next_use (use);
1183 first->set_last_use (use);
1184
1185 gcc_checking_assert (use->check_integrity ());
1186 return;
1187 }
1188
1189 // If there is currently no splay tree for this definition, see if can
1190 // get away with a pure list-based update.
1191 insn_info *insn = use->insn ();
1192 auto quick_path = [&]()
1193 {
1194 // Check if USE should come before all current uses.
1195 if (first->is_in_phi () || compare_use_insns (insn1: insn, insn2: first->insn ()) < 0)
1196 {
1197 insert_use_before (use, before: first);
1198 return true;
1199 }
1200
1201 // Check if USE should come after all current uses in the same
1202 // subsequence (i.e. the list of nondebug insn uses or the list
1203 // of debug insn uses).
1204 use_info *last = first->last_use ();
1205 if (use->is_in_debug_insn ())
1206 {
1207 if (last->is_in_phi ())
1208 return false;
1209 }
1210 else
1211 last = last->last_nondebug_insn_use ();
1212
1213 if (compare_use_insns (insn1: insn, insn2: last->insn ()) > 0)
1214 {
1215 insert_use_after (use, after: last);
1216 return true;
1217 }
1218
1219 return false;
1220 };
1221 if (!def->m_use_tree && quick_path ())
1222 return;
1223
1224 // Search the splay tree for an insertion point. COMPARISON is less
1225 // than zero if USE should come before NEIGHBOR, or greater than zero
1226 // if USE should come after NEIGHBOR.
1227 need_use_splay_tree (def);
1228 int comparison = lookup_use (tree&: def->m_use_tree, insn);
1229 gcc_checking_assert (comparison != 0);
1230 splay_tree_node<use_info *> *neighbor = def->m_use_tree.root ();
1231
1232 // If USE comes before NEIGHBOR, insert USE to NEIGHBOR's left,
1233 // otherwise insert USE to NEIGHBOR's right.
1234 auto *use_node = allocate<splay_tree_node<use_info *>> (args: use);
1235 def->m_use_tree.insert_child (node: neighbor, index: comparison > 0, child: use_node);
1236 if (comparison > 0)
1237 insert_use_after (use, after: neighbor->value ());
1238 else
1239 insert_use_before (use, before: neighbor->value ());
1240}
1241
1242void
1243function_info::reparent_use (use_info *use, set_info *new_def)
1244{
1245 remove_use (use);
1246 use->set_def (new_def);
1247 add_use (use);
1248}
1249
1250// If USE has a known definition, remove USE from that definition's list
1251// of uses. Also remove if it from the associated splay tree, if any.
1252void
1253function_info::remove_use (use_info *use)
1254{
1255 set_info *def = use->def ();
1256 if (!def)
1257 return;
1258
1259 // Remove USE from the splay tree.
1260 if (def->m_use_tree && use->is_in_any_insn ())
1261 {
1262 int comparison = lookup_use (tree&: def->m_use_tree, insn: use->insn ());
1263 gcc_checking_assert (comparison == 0);
1264 def->m_use_tree.remove_root ();
1265 }
1266
1267 use_info *prev = use->prev_use ();
1268 use_info *next = use->next_use ();
1269
1270 use_info *first = def->first_use ();
1271 use_info *last = first->last_use ();
1272 if (last->last_nondebug_insn_use () == use)
1273 last->set_last_nondebug_insn_use (prev);
1274
1275 if (next)
1276 next->copy_prev_from (other: use);
1277 else
1278 first->set_last_use (prev);
1279
1280 if (prev)
1281 prev->copy_next_from (other: use);
1282 else
1283 def->set_first_use (next);
1284
1285 use->clear_use_links ();
1286 gcc_checking_assert ((!prev || prev->check_integrity ())
1287 && (!next || next->check_integrity ()));
1288}
1289
1290// Allocate a temporary clobber_info for register REGNO in insn INSN,
1291// including it in the region of the obstack governed by WATERMARK.
1292// Return a new def_array that contains OLD_DEFS and the new clobber.
1293//
1294// OLD_DEFS is known not to define REGNO.
1295def_array
1296function_info::insert_temp_clobber (obstack_watermark &watermark,
1297 insn_info *insn, unsigned int regno,
1298 def_array old_defs)
1299{
1300 gcc_checking_assert (watermark == &m_temp_obstack);
1301 auto *clobber = allocate_temp<clobber_info> (args: insn, args: regno);
1302 clobber->m_is_temp = true;
1303 return insert_access (watermark, access1: clobber, accesses2: old_defs);
1304}
1305
1306// See the comment above the declaration.
1307bool
1308function_info::remains_available_at_insn (const set_info *set,
1309 insn_info *insn)
1310{
1311 auto *ebb = set->ebb ();
1312 gcc_checking_assert (ebb == insn->ebb ());
1313
1314 def_info *next_def = set->next_def ();
1315 if (next_def && *next_def->insn () < *insn)
1316 return false;
1317
1318 if (HARD_REGISTER_NUM_P (set->regno ())
1319 && TEST_HARD_REG_BIT (set: m_clobbered_by_calls, bit: set->regno ()))
1320 for (ebb_call_clobbers_info *call_group : ebb->call_clobbers ())
1321 {
1322 if (!call_group->clobbers (resource: set->resource ()))
1323 continue;
1324
1325 insn_info *call_insn = next_call_clobbers (tree&: *call_group, insn);
1326 if (call_insn && *call_insn < *insn)
1327 return false;
1328 }
1329
1330 return true;
1331}
1332
1333// See the comment above the declaration.
1334bool
1335function_info::remains_available_on_exit (const set_info *set, bb_info *bb)
1336{
1337 if (HARD_REGISTER_NUM_P (set->regno ())
1338 && TEST_HARD_REG_BIT (set: m_clobbered_by_calls, bit: set->regno ()))
1339 {
1340 insn_info *search_insn = (set->bb () == bb
1341 ? set->insn ()
1342 : bb->head_insn ());
1343 for (ebb_call_clobbers_info *call_group : bb->ebb ()->call_clobbers ())
1344 {
1345 if (!call_group->clobbers (resource: set->resource ()))
1346 continue;
1347
1348 insn_info *insn = next_call_clobbers (tree&: *call_group, insn: search_insn);
1349 if (insn && insn->bb () == bb)
1350 return false;
1351 }
1352 }
1353
1354 return (set->is_last_def ()
1355 || *set->next_def ()->insn () > *bb->end_insn ());
1356}
1357
1358// A subroutine of make_uses_available. Try to make USE's definition
1359// available at the head of BB. WILL_BE_DEBUG_USE is true if the
1360// definition will be used only in debug instructions.
1361//
1362// On success:
1363//
1364// - If the use would have the same def () as USE, return USE.
1365//
1366// - If BB already has a degenerate phi for the same definition,
1367// return a temporary use of that phi.
1368//
1369// - Otherwise, the use would need a new degenerate phi. Allocate a
1370// temporary phi and return a temporary use of it.
1371//
1372// Return null on failure.
1373use_info *
1374function_info::make_use_available (use_info *use, bb_info *bb,
1375 bool will_be_debug_use)
1376{
1377 set_info *def = use->def ();
1378 if (!def)
1379 return use;
1380
1381 if (is_single_dominating_def (set: def))
1382 return use;
1383
1384 if (def->ebb () == bb->ebb ())
1385 {
1386 if (remains_available_at_insn (set: def, insn: bb->head_insn ()))
1387 return use;
1388 return nullptr;
1389 }
1390
1391 basic_block cfg_bb = bb->cfg_bb ();
1392 bb_info *use_bb = use->bb ();
1393 if (single_pred_p (bb: cfg_bb)
1394 && single_pred (bb: cfg_bb) == use_bb->cfg_bb ()
1395 && remains_available_on_exit (set: def, bb: use_bb))
1396 {
1397 if (will_be_debug_use)
1398 return use;
1399
1400 resource_info resource = use->resource ();
1401 set_info *ultimate_def = look_through_degenerate_phi (access: def);
1402
1403 // See if there is already a (degenerate) phi for DEF.
1404 insn_info *phi_insn = bb->ebb ()->phi_insn ();
1405 phi_info *phi;
1406 def_lookup dl = find_def (resource, insn: phi_insn);
1407 if (set_info *set = dl.matching_set ())
1408 {
1409 // There is an existing phi.
1410 phi = as_a<phi_info *> (p: set);
1411 gcc_checking_assert (phi->input_value (0) == ultimate_def);
1412 }
1413 else
1414 {
1415 // Create a temporary placeholder phi. This will become
1416 // permanent if the change is later committed.
1417 phi = allocate_temp<phi_info> (args: phi_insn, args: resource, args: 0);
1418 auto *input = allocate_temp<use_info> (args: phi, args: resource, args: ultimate_def);
1419 input->m_is_temp = true;
1420 phi->m_is_temp = true;
1421 phi->make_degenerate (input);
1422 if (def_info *prev = dl.prev_def (insn: phi_insn))
1423 phi->set_prev_def (prev);
1424 if (def_info *next = dl.next_def (insn: phi_insn))
1425 phi->set_next_def (next);
1426 }
1427
1428 // Create a temporary use of the phi at the head of the first
1429 // block, since we know for sure that it's available there.
1430 insn_info *use_insn = bb->ebb ()->first_bb ()->head_insn ();
1431 auto *new_use = allocate_temp<use_info> (args: use_insn, args: resource, args: phi);
1432 new_use->m_is_temp = true;
1433 return new_use;
1434 }
1435 return nullptr;
1436}
1437
1438// See the comment above the declaration.
1439use_array
1440function_info::make_uses_available (obstack_watermark &watermark,
1441 use_array uses, bb_info *bb,
1442 bool will_be_debug_uses)
1443{
1444 unsigned int num_uses = uses.size ();
1445 if (num_uses == 0)
1446 return uses;
1447
1448 auto **new_uses = XOBNEWVEC (watermark, access_info *, num_uses);
1449 for (unsigned int i = 0; i < num_uses; ++i)
1450 {
1451 use_info *use = make_use_available (use: uses[i], bb, will_be_debug_use: will_be_debug_uses);
1452 if (!use)
1453 return use_array (access_array::invalid ());
1454 new_uses[i] = use;
1455 }
1456 return use_array (new_uses, num_uses);
1457}
1458
1459set_info *
1460function_info::create_set (obstack_watermark &watermark,
1461 insn_info *insn,
1462 resource_info resource)
1463{
1464 auto set = change_alloc<set_info> (wm&: watermark, args: insn, args: resource);
1465 set->m_is_temp = true;
1466 return set;
1467}
1468
1469use_info *
1470function_info::create_use (obstack_watermark &watermark,
1471 insn_info *insn,
1472 set_info *set)
1473{
1474 auto use = change_alloc<use_info> (wm&: watermark, args: insn, args: set->resource (), args: set);
1475 use->m_is_temp = true;
1476 return use;
1477}
1478
1479// Return true if ACCESS1 can represent ACCESS2 and if ACCESS2 can
1480// represent ACCESS1.
1481static bool
1482can_merge_accesses (access_info *access1, access_info *access2)
1483{
1484 if (access1 == access2)
1485 return true;
1486
1487 auto *use1 = dyn_cast<use_info *> (p: access1);
1488 auto *use2 = dyn_cast<use_info *> (p: access2);
1489 return use1 && use2 && use1->def () == use2->def ();
1490}
1491
1492// See the comment above the declaration.
1493access_array
1494rtl_ssa::merge_access_arrays_base (obstack_watermark &watermark,
1495 access_array accesses1,
1496 access_array accesses2)
1497{
1498 if (accesses1.empty ())
1499 return accesses2;
1500 if (accesses2.empty ())
1501 return accesses1;
1502
1503 auto i1 = accesses1.begin ();
1504 auto end1 = accesses1.end ();
1505 auto i2 = accesses2.begin ();
1506 auto end2 = accesses2.end ();
1507
1508 access_array_builder builder (watermark);
1509 builder.reserve (num_accesses: accesses1.size () + accesses2.size ());
1510
1511 while (i1 != end1 && i2 != end2)
1512 {
1513 access_info *access1 = *i1;
1514 access_info *access2 = *i2;
1515
1516 unsigned int regno1 = access1->regno ();
1517 unsigned int regno2 = access2->regno ();
1518 if (regno1 == regno2)
1519 {
1520 if (!can_merge_accesses (access1, access2))
1521 return access_array::invalid ();
1522
1523 builder.quick_push (access: access1);
1524 ++i1;
1525 ++i2;
1526 }
1527 else if (regno1 < regno2)
1528 {
1529 builder.quick_push (access: access1);
1530 ++i1;
1531 }
1532 else
1533 {
1534 builder.quick_push (access: access2);
1535 ++i2;
1536 }
1537 }
1538 for (; i1 != end1; ++i1)
1539 builder.quick_push (access: *i1);
1540 for (; i2 != end2; ++i2)
1541 builder.quick_push (access: *i2);
1542
1543 return builder.finish ();
1544}
1545
1546// See the comment above the declaration.
1547access_array
1548rtl_ssa::insert_access_base (obstack_watermark &watermark,
1549 access_info *access1, access_array accesses2)
1550{
1551 access_array_builder builder (watermark);
1552 builder.reserve (num_accesses: 1 + accesses2.size ());
1553
1554 unsigned int regno1 = access1->regno ();
1555 auto i2 = accesses2.begin ();
1556 auto end2 = accesses2.end ();
1557 while (i2 != end2)
1558 {
1559 access_info *access2 = *i2;
1560
1561 unsigned int regno2 = access2->regno ();
1562 if (regno1 == regno2)
1563 {
1564 if (!can_merge_accesses (access1, access2))
1565 return access_array::invalid ();
1566
1567 builder.quick_push (access: access1);
1568 access1 = nullptr;
1569 ++i2;
1570 break;
1571 }
1572 else if (regno1 < regno2)
1573 {
1574 builder.quick_push (access: access1);
1575 access1 = nullptr;
1576 break;
1577 }
1578 else
1579 {
1580 builder.quick_push (access: access2);
1581 ++i2;
1582 }
1583 }
1584 if (access1)
1585 builder.quick_push (access: access1);
1586 for (; i2 != end2; ++i2)
1587 builder.quick_push (access: *i2);
1588
1589 return builder.finish ();
1590}
1591
1592// See the comment above the declaration.
1593use_array
1594rtl_ssa::remove_uses_of_def (obstack_watermark &watermark, use_array uses,
1595 def_info *def)
1596{
1597 access_array_builder uses_builder (watermark);
1598 uses_builder.reserve (num_accesses: uses.size ());
1599 for (use_info *use : uses)
1600 if (use->def () != def)
1601 uses_builder.quick_push (access: use);
1602 return use_array (uses_builder.finish ());
1603}
1604
1605// See the comment above the declaration.
1606access_array
1607rtl_ssa::remove_note_accesses_base (obstack_watermark &watermark,
1608 access_array accesses)
1609{
1610 auto predicate = [](access_info *a) {
1611 return !a->only_occurs_in_notes ();
1612 };
1613
1614 for (access_info *access : accesses)
1615 if (access->only_occurs_in_notes ())
1616 return filter_accesses (watermark, accesses, predicate);
1617
1618 return accesses;
1619}
1620
1621// See the comment above the declaration.
1622bool
1623rtl_ssa::accesses_reference_same_resource (access_array accesses1,
1624 access_array accesses2)
1625{
1626 auto i1 = accesses1.begin ();
1627 auto end1 = accesses1.end ();
1628 auto i2 = accesses2.begin ();
1629 auto end2 = accesses2.end ();
1630
1631 while (i1 != end1 && i2 != end2)
1632 {
1633 access_info *access1 = *i1;
1634 access_info *access2 = *i2;
1635
1636 unsigned int regno1 = access1->regno ();
1637 unsigned int regno2 = access2->regno ();
1638 if (regno1 == regno2)
1639 return true;
1640
1641 if (regno1 < regno2)
1642 ++i1;
1643 else
1644 ++i2;
1645 }
1646 return false;
1647}
1648
1649// See the comment above the declaration.
1650bool
1651rtl_ssa::insn_clobbers_resources (insn_info *insn, access_array accesses)
1652{
1653 if (accesses_reference_same_resource (accesses1: insn->defs (), accesses2: accesses))
1654 return true;
1655
1656 if (insn->is_call () && accesses_include_hard_registers (accesses))
1657 {
1658 function_abi abi = insn_callee_abi (insn->rtl ());
1659 for (const access_info *access : accesses)
1660 {
1661 if (!HARD_REGISTER_NUM_P (access->regno ()))
1662 break;
1663 if (abi.clobbers_reg_p (mode: access->mode (), regno: access->regno ()))
1664 return true;
1665 }
1666 }
1667
1668 return false;
1669}
1670
1671// Print RESOURCE to PP.
1672void
1673rtl_ssa::pp_resource (pretty_printer *pp, resource_info resource)
1674{
1675 resource.print (pp);
1676}
1677
1678// Print ACCESS to PP. FLAGS is a bitmask of PP_ACCESS_* flags.
1679void
1680rtl_ssa::pp_access (pretty_printer *pp, const access_info *access,
1681 unsigned int flags)
1682{
1683 if (!access)
1684 pp_string (pp, "<null>");
1685 else if (auto *phi = dyn_cast<const phi_info *> (p: access))
1686 phi->print (pp, flags);
1687 else if (auto *set = dyn_cast<const set_info *> (p: access))
1688 set->print (pp, flags);
1689 else if (auto *clobber = dyn_cast<const clobber_info *> (p: access))
1690 clobber->print (pp, flags);
1691 else if (auto *use = dyn_cast<const use_info *> (p: access))
1692 use->print (pp, flags);
1693 else
1694 pp_string (pp, "??? Unknown access");
1695}
1696
1697// Print ACCESSES to PP. FLAGS is a bitmask of PP_ACCESS_* flags.
1698void
1699rtl_ssa::pp_accesses (pretty_printer *pp, access_array accesses,
1700 unsigned int flags)
1701{
1702 if (accesses.empty ())
1703 pp_string (pp, "none");
1704 else
1705 {
1706 bool is_first = true;
1707 for (access_info *access : accesses)
1708 {
1709 if (is_first)
1710 is_first = false;
1711 else
1712 pp_newline_and_indent (pp, 0);
1713 pp_access (pp, access, flags);
1714 }
1715 }
1716}
1717
1718// Print NODE to PP.
1719void
1720rtl_ssa::pp_def_node (pretty_printer *pp, const def_node *node)
1721{
1722 if (!node)
1723 pp_string (pp, "<null>");
1724 else if (auto *group = dyn_cast<const clobber_group *> (p: node))
1725 group->print (pp);
1726 else if (auto *set = dyn_cast<const set_node *> (p: node))
1727 set->print (pp);
1728 else
1729 pp_string (pp, "??? Unknown def node");
1730}
1731
1732// Print MUX to PP.
1733void
1734rtl_ssa::pp_def_mux (pretty_printer *pp, def_mux mux)
1735{
1736 if (auto *node = mux.dyn_cast<def_node *> ())
1737 pp_def_node (pp, node);
1738 else
1739 pp_access (pp, access: mux.as_a<def_info *> ());
1740}
1741
1742// Print DL to PP.
1743void
1744rtl_ssa::pp_def_lookup (pretty_printer *pp, def_lookup dl)
1745{
1746 pp_string (pp, "comparison result of ");
1747 pp_decimal_int (pp, dl.comparison);
1748 pp_string (pp, " for ");
1749 pp_newline_and_indent (pp, 0);
1750 pp_def_mux (pp, mux: dl.mux);
1751}
1752
1753// Dump RESOURCE to FILE.
1754void
1755dump (FILE *file, resource_info resource)
1756{
1757 dump_using (file, printer: pp_resource, args: resource);
1758}
1759
1760// Dump ACCESS to FILE. FLAGS is a bitmask of PP_ACCESS_* flags.
1761void
1762dump (FILE *file, const access_info *access, unsigned int flags)
1763{
1764 dump_using (file, printer: pp_access, args: access, args: flags);
1765}
1766
1767// Dump ACCESSES to FILE. FLAGS is a bitmask of PP_ACCESS_* flags.
1768void
1769dump (FILE *file, access_array accesses, unsigned int flags)
1770{
1771 dump_using (file, printer: pp_accesses, args: accesses, args: flags);
1772}
1773
1774// Print NODE to FILE.
1775void
1776dump (FILE *file, const def_node *node)
1777{
1778 dump_using (file, printer: pp_def_node, args: node);
1779}
1780
1781// Print MUX to FILE.
1782void
1783dump (FILE *file, def_mux mux)
1784{
1785 dump_using (file, printer: pp_def_mux, args: mux);
1786}
1787
1788// Print RESULT to FILE.
1789void
1790dump (FILE *file, def_lookup result)
1791{
1792 dump_using (file, printer: pp_def_lookup, args: result);
1793}
1794
1795// Debug interfaces to the dump routines above.
1796void debug (const resource_info &x) { dump (stderr, resource: x); }
1797void debug (const access_info *x) { dump (stderr, access: x); }
1798void debug (const access_array &x) { dump (stderr, accesses: x); }
1799void debug (const def_node *x) { dump (stderr, node: x); }
1800void debug (const def_mux &x) { dump (stderr, mux: x); }
1801void debug (const def_lookup &x) { dump (stderr, result: x); }
1802

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