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