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 | |
32 | using 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. |
36 | clobber_group * |
37 | clobber_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. |
77 | void |
78 | resource_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. |
91 | void |
92 | resource_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. |
124 | void |
125 | resource_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. |
133 | void |
134 | access_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. |
144 | void |
145 | access_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. |
175 | inline bool |
176 | use_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. |
208 | void |
209 | use_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. |
218 | void |
219 | use_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. |
231 | void |
232 | use_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. |
262 | void |
263 | def_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. |
272 | void |
273 | def_info::print_location (pretty_printer *pp) const |
274 | { |
275 | insn ()->print_identifier_and_location (pp); |
276 | } |
277 | |
278 | // See the comment above the declaration. |
279 | void |
280 | clobber_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. |
297 | void |
298 | set_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. |
332 | void |
333 | set_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. |
350 | void |
351 | phi_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. |
390 | void |
391 | set_node::print (pretty_printer *pp) const |
392 | { |
393 | pp_access (pp, first_def ()); |
394 | } |
395 | |
396 | // See the comment above the declaration. |
397 | clobber_info * |
398 | clobber_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. |
408 | clobber_info * |
409 | clobber_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. |
419 | void |
420 | clobber_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. |
441 | def_info * |
442 | def_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. |
454 | def_info * |
455 | def_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. |
468 | clobber_group * |
469 | function_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. |
479 | def_node * |
480 | function_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. |
493 | def_splay_tree |
494 | function_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. |
525 | int |
526 | rtl_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. |
544 | int |
545 | rtl_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. |
557 | def_lookup |
558 | function_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. |
592 | void |
593 | function_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. |
613 | void |
614 | function_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 (). |
633 | void |
634 | function_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. |
655 | void |
656 | function_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 (). |
693 | void |
694 | function_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. |
722 | void |
723 | function_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. |
734 | void |
735 | function_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. |
748 | void |
749 | function_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. |
800 | clobber_info * |
801 | function_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. |
857 | void |
858 | function_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. |
889 | void |
890 | function_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. |
995 | void |
996 | function_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. |
1046 | void |
1047 | function_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. |
1060 | static inline int |
1061 | compare_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. |
1075 | int |
1076 | rtl_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. |
1089 | void |
1090 | function_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. |
1115 | void |
1116 | function_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. |
1149 | void |
1150 | function_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 | |
1242 | void |
1243 | function_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. |
1252 | void |
1253 | function_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. |
1295 | def_array |
1296 | function_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. |
1307 | bool |
1308 | function_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. |
1334 | bool |
1335 | function_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. |
1373 | use_info * |
1374 | function_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. |
1439 | use_array |
1440 | function_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 | |
1459 | set_info * |
1460 | function_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 | |
1469 | use_info * |
1470 | function_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. |
1481 | static bool |
1482 | can_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. |
1493 | access_array |
1494 | rtl_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. |
1547 | access_array |
1548 | rtl_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. |
1593 | use_array |
1594 | rtl_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. |
1606 | access_array |
1607 | rtl_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. |
1622 | bool |
1623 | rtl_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. |
1650 | bool |
1651 | rtl_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. |
1672 | void |
1673 | rtl_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. |
1679 | void |
1680 | rtl_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. |
1698 | void |
1699 | rtl_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. |
1719 | void |
1720 | rtl_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. |
1733 | void |
1734 | rtl_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. |
1743 | void |
1744 | rtl_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. |
1754 | void |
1755 | dump (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. |
1761 | void |
1762 | dump (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. |
1768 | void |
1769 | dump (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. |
1775 | void |
1776 | dump (FILE *file, const def_node *node) |
1777 | { |
1778 | dump_using (file, printer: pp_def_node, args: node); |
1779 | } |
1780 | |
1781 | // Print MUX to FILE. |
1782 | void |
1783 | dump (FILE *file, def_mux mux) |
1784 | { |
1785 | dump_using (file, printer: pp_def_mux, args: mux); |
1786 | } |
1787 | |
1788 | // Print RESULT to FILE. |
1789 | void |
1790 | dump (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. |
1796 | void debug (const resource_info &x) { dump (stderr, resource: x); } |
1797 | void debug (const access_info *x) { dump (stderr, access: x); } |
1798 | void debug (const access_array &x) { dump (stderr, accesses: x); } |
1799 | void debug (const def_node *x) { dump (stderr, node: x); } |
1800 | void debug (const def_mux &x) { dump (stderr, mux: x); } |
1801 | void debug (const def_lookup &x) { dump (stderr, result: x); } |
1802 | |