]>
Commit | Line | Data |
---|---|---|
73b75827 | 1 | // Implementation of access-related functions for RTL SSA -*- C++ -*- |
83ffe9cd | 2 | // Copyright (C) 2020-2023 Free Software Foundation, Inc. |
73b75827 RS |
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" | |
abe07a74 | 29 | #include "rtl-ssa/internals.h" |
73b75827 RS |
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 (this, nullptr, | |
51 | 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 (tmp, sizeof (tmp), "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 (), 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, 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, m_use_tree.root (), 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 | ||
4a3073f0 RS |
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 *> (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 *> (tree.root ()->next_def ()); | |
415 | return tree.root (); | |
416 | } | |
417 | ||
73b75827 RS |
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, print_clobber); | |
437 | pp_indentation (pp) -= 4; | |
438 | } | |
439 | ||
4a3073f0 RS |
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 *> (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 *> (node)) | |
460 | if (clobber_info *clobber = group->next_clobber (insn)) | |
461 | return clobber; | |
462 | ||
463 | return first_def_of_next_group (); | |
464 | } | |
465 | ||
73b75827 RS |
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> (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 *> (def)) | |
483 | return need_clobber_group (clobber); | |
484 | return allocate<set_node> (as_a<set_info *> (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 (last); | |
501 | def_node *parent = root; | |
502 | while (def_info *prev = first_def (parent)->prev_def ()) | |
503 | { | |
504 | def_node *node = need_def_node (prev); | |
505 | def_splay_tree::insert_child (parent, 0, 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 (go_left, 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 (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 { nullptr, -1 }; | |
565 | ||
566 | // See whether the first node matches. | |
567 | auto first_result = clobber_group_or_single_def (first); | |
568 | if (*insn <= *last_def (first_result)->insn ()) | |
569 | { | |
570 | int comparison = (*insn >= *first->insn () ? 0 : -1); | |
571 | return { first_result, 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 (last); | |
577 | if (*insn >= *first_def (last_result)->insn ()) | |
578 | { | |
579 | int comparison = (*insn <= *last->insn () ? 0 : 1); | |
580 | return { last_result, 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 { tree.root (), 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 (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 (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 (def); | |
641 | else | |
642 | m_defs[def->regno () + 1]->set_last_def (prev); | |
643 | ||
644 | if (prev) | |
645 | prev->copy_next_from (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 (group->m_clobber_tree, 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 (neighbor, comparison > 0, 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 (clobber, neighbor); | |
679 | if (neighbor == group->last_clobber ()) | |
680 | group->set_last_clobber (clobber); | |
681 | } | |
682 | else | |
683 | { | |
684 | insert_def_before (clobber, 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 *> (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 *> (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 (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 (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 (next, 0, 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 (prev, 1, 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, 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 (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 (clobber1, clobber2->group ()); | |
789 | else | |
790 | append_clobber_to_group (clobber2, need_clobber_group (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 | clobber_info * | |
798 | function_info::split_clobber_group (clobber_group *group, insn_info *insn) | |
799 | { | |
800 | // Search for either the previous or next clobber in the group. | |
801 | // The result is less than zero if CLOBBER should come before NEIGHBOR | |
802 | // or greater than zero if CLOBBER should come after NEIGHBOR. | |
803 | int comparison = lookup_clobber (group->m_clobber_tree, insn); | |
804 | gcc_checking_assert (comparison != 0); | |
805 | clobber_info *neighbor = group->m_clobber_tree.root (); | |
806 | ||
807 | clobber_tree tree1, tree2; | |
808 | clobber_info *prev; | |
809 | clobber_info *next; | |
810 | if (comparison > 0) | |
811 | { | |
812 | // NEIGHBOR is the last clobber in what will become the first group. | |
813 | tree1 = neighbor; | |
814 | tree2 = tree1.split_after_root (); | |
815 | prev = neighbor; | |
816 | next = as_a<clobber_info *> (prev->next_def ()); | |
817 | } | |
818 | else | |
819 | { | |
820 | // NEIGHBOR is the first clobber in what will become the second group. | |
821 | tree2 = neighbor; | |
822 | tree1 = tree2.split_before_root (); | |
823 | next = neighbor; | |
824 | prev = as_a<clobber_info *> (next->prev_def ()); | |
825 | } | |
826 | ||
827 | // Use GROUP to hold PREV and earlier clobbers. Create a new group for | |
828 | // NEXT onwards. | |
829 | clobber_info *last_clobber = group->last_clobber (); | |
830 | clobber_group *group1 = group; | |
831 | clobber_group *group2 = allocate<clobber_group> (next); | |
832 | ||
833 | // Finish setting up GROUP1, making sure that the roots and extremities | |
834 | // have a correct group pointer. Leave the rest to be updated lazily. | |
835 | group1->set_last_clobber (prev); | |
836 | tree1->set_group (group1); | |
837 | prev->set_group (group1); | |
838 | ||
839 | // Finish setting up GROUP2, with the same approach as for GROUP1. | |
840 | group2->set_first_clobber (next); | |
841 | group2->set_last_clobber (last_clobber); | |
842 | next->set_group (group2); | |
843 | tree2->set_group (group2); | |
844 | last_clobber->set_group (group2); | |
845 | ||
846 | return prev; | |
847 | } | |
848 | ||
849 | // Add DEF to the end of the function's list of definitions of | |
850 | // DEF->resource (). There is known to be no associated splay tree yet. | |
851 | void | |
852 | function_info::append_def (def_info *def) | |
853 | { | |
854 | gcc_checking_assert (!def->has_def_links ()); | |
855 | def_info **head = &m_defs[def->regno () + 1]; | |
856 | def_info *first = *head; | |
857 | if (!first) | |
858 | { | |
859 | // This is the only definition of the resource. | |
860 | def->set_last_def (def); | |
861 | *head = def; | |
862 | return; | |
863 | } | |
864 | ||
865 | def_info *prev = first->last_def (); | |
866 | gcc_checking_assert (!prev->splay_root ()); | |
867 | ||
868 | // Maintain the invariant that two clobbers must not appear in | |
869 | // neighboring nodes of the splay tree. | |
870 | auto *clobber = dyn_cast<clobber_info *> (def); | |
871 | auto *prev_clobber = dyn_cast<clobber_info *> (prev); | |
872 | if (clobber && prev_clobber) | |
873 | append_clobber_to_group (clobber, need_clobber_group (prev_clobber)); | |
874 | ||
875 | prev->set_next_def (def); | |
876 | def->set_prev_def (prev); | |
877 | first->set_last_def (def); | |
878 | } | |
879 | ||
880 | // Add DEF to the function's list of definitions of DEF->resource (). | |
881 | // Also insert it into the associated splay tree, if there is one. | |
882 | // DEF is not currently part of the list and is not in the splay tree. | |
883 | void | |
884 | function_info::add_def (def_info *def) | |
885 | { | |
886 | gcc_checking_assert (!def->has_def_links () | |
887 | && !def->m_is_temp | |
888 | && !def->m_has_been_superceded); | |
889 | def_info **head = &m_defs[def->regno () + 1]; | |
890 | def_info *first = *head; | |
891 | if (!first) | |
892 | { | |
893 | // This is the only definition of the resource. | |
894 | def->set_last_def (def); | |
895 | *head = def; | |
896 | return; | |
897 | } | |
898 | ||
899 | def_info *last = first->last_def (); | |
900 | insn_info *insn = def->insn (); | |
901 | ||
902 | int comparison; | |
903 | def_node *root = nullptr; | |
904 | def_info *prev = nullptr; | |
905 | def_info *next = nullptr; | |
906 | if (*insn > *last->insn ()) | |
907 | { | |
908 | // This definition comes after all other definitions. | |
909 | comparison = 1; | |
910 | if (def_splay_tree tree = last->splay_root ()) | |
911 | { | |
912 | tree.splay_max_node (); | |
913 | root = tree.root (); | |
914 | last->set_splay_root (root); | |
915 | } | |
916 | prev = last; | |
917 | } | |
918 | else if (*insn < *first->insn ()) | |
919 | { | |
920 | // This definition comes before all other definitions. | |
921 | comparison = -1; | |
922 | if (def_splay_tree tree = last->splay_root ()) | |
923 | { | |
924 | tree.splay_min_node (); | |
925 | root = tree.root (); | |
926 | last->set_splay_root (root); | |
927 | } | |
928 | next = first; | |
929 | } | |
930 | else | |
931 | { | |
932 | // Search the splay tree for an insertion point. | |
933 | def_splay_tree tree = need_def_splay_tree (last); | |
934 | comparison = lookup_def (tree, insn); | |
935 | root = tree.root (); | |
936 | last->set_splay_root (root); | |
937 | ||
938 | // Deal with cases in which we found an overlapping live range. | |
939 | if (comparison == 0) | |
940 | { | |
941 | auto *group = as_a<clobber_group *> (tree.root ()); | |
942 | if (auto *clobber = dyn_cast<clobber_info *> (def)) | |
943 | { | |
944 | add_clobber (clobber, group); | |
945 | return; | |
946 | } | |
947 | prev = split_clobber_group (group, insn); | |
948 | next = prev->next_def (); | |
949 | } | |
950 | // COMPARISON is < 0 if DEF comes before ROOT or > 0 if DEF comes | |
951 | // after ROOT. | |
952 | else if (comparison < 0) | |
953 | { | |
954 | next = first_def (root); | |
955 | prev = next->prev_def (); | |
956 | } | |
957 | else | |
958 | { | |
959 | prev = last_def (root); | |
960 | next = prev->next_def (); | |
961 | } | |
962 | } | |
963 | ||
964 | // See if we should merge CLOBBER with a neighboring clobber. | |
965 | auto *clobber = dyn_cast<clobber_info *> (def); | |
966 | auto *prev_clobber = safe_dyn_cast<clobber_info *> (prev); | |
967 | auto *next_clobber = safe_dyn_cast<clobber_info *> (next); | |
968 | // We shouldn't have consecutive clobber_groups. | |
969 | gcc_checking_assert (!(clobber && prev_clobber && next_clobber)); | |
970 | if (clobber && prev_clobber) | |
971 | append_clobber_to_group (clobber, need_clobber_group (prev_clobber)); | |
972 | else if (clobber && next_clobber) | |
973 | prepend_clobber_to_group (clobber, need_clobber_group (next_clobber)); | |
974 | else if (root) | |
975 | { | |
976 | // If DEF comes before ROOT, insert DEF to ROOT's left, | |
977 | // otherwise insert DEF to ROOT's right. | |
978 | def_node *node = need_def_node (def); | |
979 | def_splay_tree::insert_child (root, comparison >= 0, node); | |
980 | } | |
981 | if (prev) | |
982 | insert_def_after (def, prev); | |
983 | else | |
984 | insert_def_before (def, next); | |
985 | } | |
986 | ||
987 | // Remove DEF from the function's list of definitions of DEF->resource (). | |
988 | // Also remove DEF from the associated splay tree, if there is one. | |
989 | void | |
990 | function_info::remove_def (def_info *def) | |
991 | { | |
992 | def_info **head = &m_defs[def->regno () + 1]; | |
993 | def_info *first = *head; | |
994 | gcc_checking_assert (first); | |
995 | if (first->is_last_def ()) | |
996 | { | |
997 | // DEF is the only definition of the resource. | |
998 | gcc_checking_assert (first == def); | |
999 | *head = nullptr; | |
1000 | def->clear_def_links (); | |
1001 | return; | |
1002 | } | |
1003 | ||
1004 | // If CLOBBER belongs to a clobber_group that contains other clobbers | |
1005 | // too, then we need to update the clobber_group and the list, but any | |
1006 | // splay tree that contains the clobber_group is unaffected. | |
1007 | if (auto *clobber = dyn_cast<clobber_info *> (def)) | |
1008 | if (clobber->is_in_group ()) | |
1009 | { | |
1010 | clobber_group *group = clobber->group (); | |
1011 | if (group->first_clobber () != group->last_clobber ()) | |
1012 | { | |
1013 | remove_clobber (clobber, group); | |
1014 | return; | |
1015 | } | |
1016 | } | |
1017 | ||
1018 | // If we've created a splay tree for this resource, remove the entry | |
1019 | // for DEF. | |
1020 | def_info *last = first->last_def (); | |
1021 | if (def_splay_tree tree = last->splay_root ()) | |
1022 | { | |
1023 | int comparison = lookup_def (tree, def->insn ()); | |
1024 | gcc_checking_assert (comparison == 0); | |
1025 | tree.remove_root (); | |
1026 | last->set_splay_root (tree.root ()); | |
1027 | } | |
1028 | ||
1029 | // If the definition came between two clobbers, merge them into a single | |
1030 | // group. | |
1031 | auto *prev_clobber = safe_dyn_cast<clobber_info *> (def->prev_def ()); | |
1032 | auto *next_clobber = safe_dyn_cast<clobber_info *> (def->next_def ()); | |
1033 | if (prev_clobber && next_clobber) | |
1034 | merge_clobber_groups (prev_clobber, next_clobber, last); | |
1035 | ||
1036 | remove_def_from_list (def); | |
1037 | } | |
1038 | ||
1039 | // Require DEF to have a splay tree that contains all non-phi uses. | |
1040 | void | |
1041 | function_info::need_use_splay_tree (set_info *def) | |
1042 | { | |
1043 | if (!def->m_use_tree) | |
1044 | for (use_info *use : def->all_insn_uses ()) | |
1045 | { | |
1046 | auto *use_node = allocate<splay_tree_node<use_info *>> (use); | |
1047 | def->m_use_tree.insert_max_node (use_node); | |
1048 | } | |
1049 | } | |
1050 | ||
1051 | // Compare two instructions by their position in a use splay tree. Return >0 | |
1052 | // if INSN1 comes after INSN2, <0 if INSN1 comes before INSN2, or 0 if they are | |
1053 | // the same instruction. | |
1054 | static inline int | |
1055 | compare_use_insns (insn_info *insn1, insn_info *insn2) | |
1056 | { | |
1057 | // Debug instructions go after nondebug instructions. | |
1058 | int diff = insn1->is_debug_insn () - insn2->is_debug_insn (); | |
1059 | if (diff != 0) | |
1060 | return diff; | |
1061 | return insn1->compare_with (insn2); | |
1062 | } | |
1063 | ||
1064 | // Search TREE for a use in INSN. If such a use exists, install it as | |
1065 | // the root of TREE and return 0. Otherwise arbitrarily choose between: | |
1066 | // | |
1067 | // (1) Installing the closest preceding use as the root and returning 1. | |
1068 | // (2) Installing the closest following use as the root and returning -1. | |
1069 | int | |
1070 | rtl_ssa::lookup_use (splay_tree<use_info *> &tree, insn_info *insn) | |
1071 | { | |
1072 | auto compare = [&](splay_tree_node<use_info *> *node) | |
1073 | { | |
1074 | return compare_use_insns (insn, node->value ()->insn ()); | |
1075 | }; | |
1076 | return tree.lookup (compare); | |
1077 | } | |
1078 | ||
1079 | // Add USE to USE->def ()'s list of uses. inserting USE immediately before | |
1080 | // BEFORE. USE is not currently in the list. | |
1081 | // | |
1082 | // This routine should not be used for inserting phi uses. | |
1083 | void | |
1084 | function_info::insert_use_before (use_info *use, use_info *before) | |
1085 | { | |
1086 | gcc_checking_assert (!use->has_use_links () && use->is_in_any_insn ()); | |
1087 | ||
1088 | set_info *def = use->def (); | |
1089 | ||
1090 | use->copy_prev_from (before); | |
1091 | use->set_next_use (before); | |
1092 | ||
1093 | if (use_info *prev = use->prev_use ()) | |
1094 | prev->set_next_use (use); | |
1095 | else | |
1096 | use->def ()->set_first_use (use); | |
1097 | ||
1098 | before->set_prev_use (use); | |
1099 | if (use->is_in_nondebug_insn () && before->is_in_debug_insn_or_phi ()) | |
1100 | def->last_use ()->set_last_nondebug_insn_use (use); | |
1101 | ||
1102 | gcc_checking_assert (use->check_integrity () && before->check_integrity ()); | |
1103 | } | |
1104 | ||
1105 | // Add USE to USE->def ()'s list of uses. inserting USE immediately after | |
1106 | // AFTER. USE is not currently in the list. | |
1107 | // | |
1108 | // This routine should not be used for inserting phi uses. | |
1109 | void | |
1110 | function_info::insert_use_after (use_info *use, use_info *after) | |
1111 | { | |
1112 | set_info *def = use->def (); | |
1113 | gcc_checking_assert (after->is_in_any_insn () | |
1114 | && !use->has_use_links () | |
1115 | && use->is_in_any_insn ()); | |
1116 | ||
1117 | use->set_prev_use (after); | |
1118 | use->copy_next_from (after); | |
1119 | ||
1120 | after->set_next_use (use); | |
1121 | ||
1122 | if (use_info *next = use->next_use ()) | |
1123 | { | |
1124 | // The last node doesn't change, but we might need to update its | |
1125 | // last_nondebug_insn_use record. | |
1126 | if (use->is_in_nondebug_insn () && next->is_in_debug_insn_or_phi ()) | |
1127 | def->last_use ()->set_last_nondebug_insn_use (use); | |
1128 | next->set_prev_use (use); | |
1129 | } | |
1130 | else | |
1131 | { | |
1132 | // USE is now the last node. | |
1133 | if (use->is_in_nondebug_insn ()) | |
1134 | use->set_last_nondebug_insn_use (use); | |
1135 | def->first_use ()->set_last_use (use); | |
1136 | } | |
1137 | ||
1138 | gcc_checking_assert (use->check_integrity () && after->check_integrity ()); | |
1139 | } | |
1140 | ||
1141 | // If USE has a known definition, add USE to that definition's list of uses. | |
1142 | // Also update the associated splay tree, if any. | |
1143 | void | |
1144 | function_info::add_use (use_info *use) | |
1145 | { | |
1146 | gcc_checking_assert (!use->has_use_links () | |
1147 | && !use->m_is_temp | |
1148 | && !use->m_has_been_superceded); | |
1149 | ||
1150 | set_info *def = use->def (); | |
1151 | if (!def) | |
1152 | return; | |
1153 | ||
1154 | use_info *first = def->first_use (); | |
1155 | if (!first) | |
1156 | { | |
1157 | // This is the only use of the definition. | |
1158 | use->set_last_use (use); | |
1159 | if (use->is_in_nondebug_insn ()) | |
1160 | use->set_last_nondebug_insn_use (use); | |
1161 | ||
1162 | def->set_first_use (use); | |
1163 | ||
1164 | gcc_checking_assert (use->check_integrity ()); | |
1165 | return; | |
1166 | } | |
1167 | ||
1168 | if (use->is_in_phi ()) | |
1169 | { | |
1170 | // Add USE at the end of the list, as the new first phi. | |
1171 | use_info *last = first->last_use (); | |
1172 | ||
1173 | use->set_prev_use (last); | |
1174 | use->copy_next_from (last); | |
1175 | ||
1176 | last->set_next_use (use); | |
1177 | first->set_last_use (use); | |
1178 | ||
1179 | gcc_checking_assert (use->check_integrity ()); | |
1180 | return; | |
1181 | } | |
1182 | ||
1183 | // If there is currently no splay tree for this definition, see if can | |
1184 | // get away with a pure list-based update. | |
1185 | insn_info *insn = use->insn (); | |
1186 | auto quick_path = [&]() | |
1187 | { | |
1188 | // Check if USE should come before all current uses. | |
1189 | if (first->is_in_phi () || compare_use_insns (insn, first->insn ()) < 0) | |
1190 | { | |
1191 | insert_use_before (use, first); | |
1192 | return true; | |
1193 | } | |
1194 | ||
1195 | // Check if USE should come after all current uses in the same | |
1196 | // subsequence (i.e. the list of nondebug insn uses or the list | |
1197 | // of debug insn uses). | |
1198 | use_info *last = first->last_use (); | |
1199 | if (use->is_in_debug_insn ()) | |
1200 | { | |
1201 | if (last->is_in_phi ()) | |
1202 | return false; | |
1203 | } | |
1204 | else | |
1205 | last = last->last_nondebug_insn_use (); | |
1206 | ||
1207 | if (compare_use_insns (insn, last->insn ()) > 0) | |
1208 | { | |
1209 | insert_use_after (use, last); | |
1210 | return true; | |
1211 | } | |
1212 | ||
1213 | return false; | |
1214 | }; | |
1215 | if (!def->m_use_tree && quick_path ()) | |
1216 | return; | |
1217 | ||
1218 | // Search the splay tree for an insertion point. COMPARISON is less | |
1219 | // than zero if USE should come before NEIGHBOR, or greater than zero | |
1220 | // if USE should come after NEIGHBOR. | |
1221 | need_use_splay_tree (def); | |
1222 | int comparison = lookup_use (def->m_use_tree, insn); | |
1223 | gcc_checking_assert (comparison != 0); | |
1224 | splay_tree_node<use_info *> *neighbor = def->m_use_tree.root (); | |
1225 | ||
1226 | // If USE comes before NEIGHBOR, insert USE to NEIGHBOR's left, | |
1227 | // otherwise insert USE to NEIGHBOR's right. | |
1228 | auto *use_node = allocate<splay_tree_node<use_info *>> (use); | |
1229 | def->m_use_tree.insert_child (neighbor, comparison > 0, use_node); | |
1230 | if (comparison > 0) | |
1231 | insert_use_after (use, neighbor->value ()); | |
1232 | else | |
1233 | insert_use_before (use, neighbor->value ()); | |
1234 | } | |
1235 | ||
1236 | // If USE has a known definition, remove USE from that definition's list | |
1237 | // of uses. Also remove if it from the associated splay tree, if any. | |
1238 | void | |
1239 | function_info::remove_use (use_info *use) | |
1240 | { | |
1241 | set_info *def = use->def (); | |
1242 | if (!def) | |
1243 | return; | |
1244 | ||
1245 | // Remove USE from the splay tree. | |
1246 | if (def->m_use_tree && use->is_in_any_insn ()) | |
1247 | { | |
1248 | int comparison = lookup_use (def->m_use_tree, use->insn ()); | |
1249 | gcc_checking_assert (comparison == 0); | |
1250 | def->m_use_tree.remove_root (); | |
1251 | } | |
1252 | ||
1253 | use_info *prev = use->prev_use (); | |
1254 | use_info *next = use->next_use (); | |
1255 | ||
1256 | use_info *first = def->first_use (); | |
1257 | use_info *last = first->last_use (); | |
1258 | if (last->last_nondebug_insn_use () == use) | |
1259 | last->set_last_nondebug_insn_use (prev); | |
1260 | ||
1261 | if (next) | |
1262 | next->copy_prev_from (use); | |
1263 | else | |
1264 | first->set_last_use (prev); | |
1265 | ||
1266 | if (prev) | |
1267 | prev->copy_next_from (use); | |
1268 | else | |
1269 | def->set_first_use (next); | |
1270 | ||
1271 | use->clear_use_links (); | |
1272 | gcc_checking_assert ((!prev || prev->check_integrity ()) | |
1273 | && (!next || next->check_integrity ())); | |
1274 | } | |
1275 | ||
1276 | // Allocate a temporary clobber_info for register REGNO in insn INSN, | |
1277 | // including it in the region of the obstack governed by WATERMARK. | |
1278 | // Return a new def_array that contains OLD_DEFS and the new clobber. | |
1279 | // | |
1280 | // OLD_DEFS is known not to define REGNO. | |
1281 | def_array | |
1282 | function_info::insert_temp_clobber (obstack_watermark &watermark, | |
1283 | insn_info *insn, unsigned int regno, | |
1284 | def_array old_defs) | |
1285 | { | |
1286 | gcc_checking_assert (watermark == &m_temp_obstack); | |
1287 | auto *clobber = allocate_temp<clobber_info> (insn, regno); | |
1288 | clobber->m_is_temp = true; | |
1289 | return insert_access (watermark, clobber, old_defs); | |
1290 | } | |
1291 | ||
1292 | // A subroutine of make_uses_available. Try to make USE's definition | |
c97351c0 RS |
1293 | // available at the head of BB. WILL_BE_DEBUG_USE is true if the |
1294 | // definition will be used only in debug instructions. | |
1295 | // | |
1296 | // On success: | |
73b75827 RS |
1297 | // |
1298 | // - If the use would have the same def () as USE, return USE. | |
1299 | // | |
1300 | // - If BB already has a degenerate phi for the same definition, | |
1301 | // return a temporary use of that phi. | |
1302 | // | |
1303 | // - Otherwise, the use would need a new degenerate phi. Allocate a | |
1304 | // temporary phi and return a temporary use of it. | |
1305 | // | |
1306 | // Return null on failure. | |
1307 | use_info * | |
c97351c0 RS |
1308 | function_info::make_use_available (use_info *use, bb_info *bb, |
1309 | bool will_be_debug_use) | |
73b75827 RS |
1310 | { |
1311 | set_info *def = use->def (); | |
1312 | if (!def) | |
1313 | return use; | |
1314 | ||
1315 | if (is_single_dominating_def (def)) | |
1316 | return use; | |
1317 | ||
1318 | // FIXME: Deliberately limited for fwprop compatibility testing. | |
1319 | basic_block cfg_bb = bb->cfg_bb (); | |
1320 | bb_info *use_bb = use->bb (); | |
1321 | if (single_pred_p (cfg_bb) | |
1322 | && single_pred (cfg_bb) == use_bb->cfg_bb () | |
1323 | && remains_available_on_exit (def, use_bb)) | |
1324 | { | |
c97351c0 | 1325 | if (def->ebb () == bb->ebb () || will_be_debug_use) |
73b75827 RS |
1326 | return use; |
1327 | ||
1328 | resource_info resource = use->resource (); | |
1329 | set_info *ultimate_def = look_through_degenerate_phi (def); | |
1330 | ||
1331 | // See if there is already a (degenerate) phi for DEF. | |
1332 | insn_info *phi_insn = bb->ebb ()->phi_insn (); | |
1333 | phi_info *phi; | |
1334 | def_lookup dl = find_def (resource, phi_insn); | |
1335 | if (set_info *set = dl.matching_set ()) | |
1336 | { | |
1337 | // There is an existing phi. | |
1338 | phi = as_a<phi_info *> (set); | |
1339 | gcc_checking_assert (phi->input_value (0) == ultimate_def); | |
1340 | } | |
1341 | else | |
1342 | { | |
1343 | // Create a temporary placeholder phi. This will become | |
1344 | // permanent if the change is later committed. | |
1345 | phi = allocate_temp<phi_info> (phi_insn, resource, 0); | |
adfee3c4 | 1346 | auto *input = allocate_temp<use_info> (phi, resource, ultimate_def); |
73b75827 RS |
1347 | input->m_is_temp = true; |
1348 | phi->m_is_temp = true; | |
1349 | phi->make_degenerate (input); | |
4a3073f0 | 1350 | if (def_info *prev = dl.prev_def (phi_insn)) |
73b75827 | 1351 | phi->set_prev_def (prev); |
4a3073f0 | 1352 | if (def_info *next = dl.next_def (phi_insn)) |
73b75827 RS |
1353 | phi->set_next_def (next); |
1354 | } | |
1355 | ||
1356 | // Create a temporary use of the phi at the head of the first | |
1357 | // block, since we know for sure that it's available there. | |
1358 | insn_info *use_insn = bb->ebb ()->first_bb ()->head_insn (); | |
1359 | auto *new_use = allocate_temp<use_info> (use_insn, resource, phi); | |
1360 | new_use->m_is_temp = true; | |
1361 | return new_use; | |
1362 | } | |
1363 | return nullptr; | |
1364 | } | |
1365 | ||
1366 | // See the comment above the declaration. | |
1367 | use_array | |
1368 | function_info::make_uses_available (obstack_watermark &watermark, | |
c97351c0 RS |
1369 | use_array uses, bb_info *bb, |
1370 | bool will_be_debug_uses) | |
73b75827 RS |
1371 | { |
1372 | unsigned int num_uses = uses.size (); | |
1373 | if (num_uses == 0) | |
1374 | return uses; | |
1375 | ||
1376 | auto **new_uses = XOBNEWVEC (watermark, access_info *, num_uses); | |
1377 | for (unsigned int i = 0; i < num_uses; ++i) | |
1378 | { | |
c97351c0 | 1379 | use_info *use = make_use_available (uses[i], bb, will_be_debug_uses); |
73b75827 RS |
1380 | if (!use) |
1381 | return use_array (access_array::invalid ()); | |
1382 | new_uses[i] = use; | |
1383 | } | |
1384 | return use_array (new_uses, num_uses); | |
1385 | } | |
1386 | ||
1387 | // Return true if ACCESS1 can represent ACCESS2 and if ACCESS2 can | |
1388 | // represent ACCESS1. | |
1389 | static bool | |
1390 | can_merge_accesses (access_info *access1, access_info *access2) | |
1391 | { | |
1392 | if (access1 == access2) | |
1393 | return true; | |
1394 | ||
1395 | auto *use1 = dyn_cast<use_info *> (access1); | |
1396 | auto *use2 = dyn_cast<use_info *> (access2); | |
1397 | return use1 && use2 && use1->def () == use2->def (); | |
1398 | } | |
1399 | ||
1400 | // See the comment above the declaration. | |
1401 | access_array | |
1402 | rtl_ssa::merge_access_arrays_base (obstack_watermark &watermark, | |
1403 | access_array accesses1, | |
1404 | access_array accesses2) | |
1405 | { | |
1406 | if (accesses1.empty ()) | |
1407 | return accesses2; | |
1408 | if (accesses2.empty ()) | |
1409 | return accesses1; | |
1410 | ||
1411 | auto i1 = accesses1.begin (); | |
1412 | auto end1 = accesses1.end (); | |
1413 | auto i2 = accesses2.begin (); | |
1414 | auto end2 = accesses2.end (); | |
1415 | ||
1416 | access_array_builder builder (watermark); | |
1417 | builder.reserve (accesses1.size () + accesses2.size ()); | |
1418 | ||
1419 | while (i1 != end1 && i2 != end2) | |
1420 | { | |
1421 | access_info *access1 = *i1; | |
1422 | access_info *access2 = *i2; | |
1423 | ||
1424 | unsigned int regno1 = access1->regno (); | |
1425 | unsigned int regno2 = access2->regno (); | |
1426 | if (regno1 == regno2) | |
1427 | { | |
1428 | if (!can_merge_accesses (access1, access2)) | |
1429 | return access_array::invalid (); | |
1430 | ||
1431 | builder.quick_push (access1); | |
1432 | ++i1; | |
1433 | ++i2; | |
1434 | } | |
1435 | else if (regno1 < regno2) | |
1436 | { | |
1437 | builder.quick_push (access1); | |
1438 | ++i1; | |
1439 | } | |
1440 | else | |
1441 | { | |
1442 | builder.quick_push (access2); | |
1443 | ++i2; | |
1444 | } | |
1445 | } | |
1446 | for (; i1 != end1; ++i1) | |
1447 | builder.quick_push (*i1); | |
1448 | for (; i2 != end2; ++i2) | |
1449 | builder.quick_push (*i2); | |
1450 | ||
1451 | return builder.finish (); | |
1452 | } | |
1453 | ||
1454 | // See the comment above the declaration. | |
1455 | access_array | |
1456 | rtl_ssa::insert_access_base (obstack_watermark &watermark, | |
1457 | access_info *access1, access_array accesses2) | |
1458 | { | |
1459 | access_array_builder builder (watermark); | |
1460 | builder.reserve (1 + accesses2.size ()); | |
1461 | ||
1462 | unsigned int regno1 = access1->regno (); | |
1463 | auto i2 = accesses2.begin (); | |
1464 | auto end2 = accesses2.end (); | |
1465 | while (i2 != end2) | |
1466 | { | |
1467 | access_info *access2 = *i2; | |
1468 | ||
1469 | unsigned int regno2 = access2->regno (); | |
1470 | if (regno1 == regno2) | |
1471 | { | |
1472 | if (!can_merge_accesses (access1, access2)) | |
1473 | return access_array::invalid (); | |
1474 | ||
1475 | builder.quick_push (access1); | |
1476 | access1 = nullptr; | |
1477 | ++i2; | |
1478 | break; | |
1479 | } | |
1480 | else if (regno1 < regno2) | |
1481 | { | |
1482 | builder.quick_push (access1); | |
1483 | access1 = nullptr; | |
1484 | break; | |
1485 | } | |
1486 | else | |
1487 | { | |
1488 | builder.quick_push (access2); | |
1489 | ++i2; | |
1490 | } | |
1491 | } | |
1492 | if (access1) | |
1493 | builder.quick_push (access1); | |
1494 | for (; i2 != end2; ++i2) | |
1495 | builder.quick_push (*i2); | |
1496 | ||
1497 | return builder.finish (); | |
1498 | } | |
1499 | ||
1500 | // See the comment above the declaration. | |
1501 | access_array | |
1502 | rtl_ssa::remove_note_accesses_base (obstack_watermark &watermark, | |
1503 | access_array accesses) | |
1504 | { | |
1505 | for (access_info *access : accesses) | |
1506 | if (access->only_occurs_in_notes ()) | |
1507 | { | |
1508 | access_array_builder builder (watermark); | |
1509 | builder.reserve (accesses.size ()); | |
1510 | for (access_info *access2 : accesses) | |
1511 | if (!access2->only_occurs_in_notes ()) | |
1512 | builder.quick_push (access2); | |
1513 | return builder.finish (); | |
1514 | } | |
1515 | return accesses; | |
1516 | } | |
1517 | ||
1518 | // Print RESOURCE to PP. | |
1519 | void | |
1520 | rtl_ssa::pp_resource (pretty_printer *pp, resource_info resource) | |
1521 | { | |
1522 | resource.print (pp); | |
1523 | } | |
1524 | ||
1525 | // Print ACCESS to PP. FLAGS is a bitmask of PP_ACCESS_* flags. | |
1526 | void | |
1527 | rtl_ssa::pp_access (pretty_printer *pp, const access_info *access, | |
1528 | unsigned int flags) | |
1529 | { | |
1530 | if (!access) | |
1531 | pp_string (pp, "<null>"); | |
1532 | else if (auto *phi = dyn_cast<const phi_info *> (access)) | |
1533 | phi->print (pp, flags); | |
1534 | else if (auto *set = dyn_cast<const set_info *> (access)) | |
1535 | set->print (pp, flags); | |
1536 | else if (auto *clobber = dyn_cast<const clobber_info *> (access)) | |
1537 | clobber->print (pp, flags); | |
1538 | else if (auto *use = dyn_cast<const use_info *> (access)) | |
1539 | use->print (pp, flags); | |
1540 | else | |
1541 | pp_string (pp, "??? Unknown access"); | |
1542 | } | |
1543 | ||
1544 | // Print ACCESSES to PP. FLAGS is a bitmask of PP_ACCESS_* flags. | |
1545 | void | |
1546 | rtl_ssa::pp_accesses (pretty_printer *pp, access_array accesses, | |
1547 | unsigned int flags) | |
1548 | { | |
1549 | if (accesses.empty ()) | |
1550 | pp_string (pp, "none"); | |
1551 | else | |
1552 | { | |
1553 | bool is_first = true; | |
1554 | for (access_info *access : accesses) | |
1555 | { | |
1556 | if (is_first) | |
1557 | is_first = false; | |
1558 | else | |
1559 | pp_newline_and_indent (pp, 0); | |
1560 | pp_access (pp, access, flags); | |
1561 | } | |
1562 | } | |
1563 | } | |
1564 | ||
1565 | // Print NODE to PP. | |
1566 | void | |
1567 | rtl_ssa::pp_def_node (pretty_printer *pp, const def_node *node) | |
1568 | { | |
1569 | if (!node) | |
1570 | pp_string (pp, "<null>"); | |
1571 | else if (auto *group = dyn_cast<const clobber_group *> (node)) | |
1572 | group->print (pp); | |
1573 | else if (auto *set = dyn_cast<const set_node *> (node)) | |
1574 | set->print (pp); | |
1575 | else | |
1576 | pp_string (pp, "??? Unknown def node"); | |
1577 | } | |
1578 | ||
1579 | // Print MUX to PP. | |
1580 | void | |
1581 | rtl_ssa::pp_def_mux (pretty_printer *pp, def_mux mux) | |
1582 | { | |
1583 | if (auto *node = mux.dyn_cast<def_node *> ()) | |
1584 | pp_def_node (pp, node); | |
1585 | else | |
1586 | pp_access (pp, mux.as_a<def_info *> ()); | |
1587 | } | |
1588 | ||
1589 | // Print DL to PP. | |
1590 | void | |
1591 | rtl_ssa::pp_def_lookup (pretty_printer *pp, def_lookup dl) | |
1592 | { | |
1593 | pp_string (pp, "comparison result of "); | |
1594 | pp_decimal_int (pp, dl.comparison); | |
1595 | pp_string (pp, " for "); | |
1596 | pp_newline_and_indent (pp, 0); | |
1597 | pp_def_mux (pp, dl.mux); | |
1598 | } | |
1599 | ||
1600 | // Dump RESOURCE to FILE. | |
1601 | void | |
1602 | dump (FILE *file, resource_info resource) | |
1603 | { | |
1604 | dump_using (file, pp_resource, resource); | |
1605 | } | |
1606 | ||
1607 | // Dump ACCESS to FILE. FLAGS is a bitmask of PP_ACCESS_* flags. | |
1608 | void | |
1609 | dump (FILE *file, const access_info *access, unsigned int flags) | |
1610 | { | |
1611 | dump_using (file, pp_access, access, flags); | |
1612 | } | |
1613 | ||
1614 | // Dump ACCESSES to FILE. FLAGS is a bitmask of PP_ACCESS_* flags. | |
1615 | void | |
1616 | dump (FILE *file, access_array accesses, unsigned int flags) | |
1617 | { | |
1618 | dump_using (file, pp_accesses, accesses, flags); | |
1619 | } | |
1620 | ||
1621 | // Print NODE to FILE. | |
1622 | void | |
1623 | dump (FILE *file, const def_node *node) | |
1624 | { | |
1625 | dump_using (file, pp_def_node, node); | |
1626 | } | |
1627 | ||
1628 | // Print MUX to FILE. | |
1629 | void | |
1630 | dump (FILE *file, def_mux mux) | |
1631 | { | |
1632 | dump_using (file, pp_def_mux, mux); | |
1633 | } | |
1634 | ||
1635 | // Print RESULT to FILE. | |
1636 | void | |
1637 | dump (FILE *file, def_lookup result) | |
1638 | { | |
1639 | dump_using (file, pp_def_lookup, result); | |
1640 | } | |
1641 | ||
1642 | // Debug interfaces to the dump routines above. | |
1643 | void debug (const resource_info &x) { dump (stderr, x); } | |
1644 | void debug (const access_info *x) { dump (stderr, x); } | |
1645 | void debug (const access_array &x) { dump (stderr, x); } | |
1646 | void debug (const def_node *x) { dump (stderr, x); } | |
1647 | void debug (const def_mux &x) { dump (stderr, x); } | |
1648 | void debug (const def_lookup &x) { dump (stderr, x); } |