]>
Commit | Line | Data |
---|---|---|
73b75827 | 1 | // RTL SSA routines for changing instructions -*- C++ -*- |
7adcbafe | 2 | // Copyright (C) 2020-2022 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 | #include "target.h" | |
32 | #include "predict.h" | |
33 | #include "memmodel.h" // Needed by emit-rtl.h | |
34 | #include "emit-rtl.h" | |
35 | #include "cfghooks.h" | |
36 | #include "cfgrtl.h" | |
37 | ||
38 | using namespace rtl_ssa; | |
39 | ||
40 | // See the comment above the declaration. | |
41 | void | |
42 | insn_change::print (pretty_printer *pp) const | |
43 | { | |
44 | if (m_is_deletion) | |
45 | { | |
46 | pp_string (pp, "deletion of "); | |
47 | pp_insn (pp, m_insn); | |
48 | } | |
49 | else | |
50 | { | |
51 | pp_string (pp, "change to "); | |
52 | pp_insn (pp, m_insn); | |
53 | pp_newline_and_indent (pp, 2); | |
54 | pp_string (pp, "~~~~~~~"); | |
55 | ||
56 | pp_newline_and_indent (pp, 0); | |
57 | pp_string (pp, "new cost: "); | |
58 | pp_decimal_int (pp, new_cost); | |
59 | ||
60 | pp_newline_and_indent (pp, 0); | |
61 | pp_string (pp, "new uses:"); | |
62 | pp_newline_and_indent (pp, 2); | |
63 | pp_accesses (pp, new_uses); | |
64 | pp_indentation (pp) -= 2; | |
65 | ||
66 | pp_newline_and_indent (pp, 0); | |
67 | pp_string (pp, "new defs:"); | |
68 | pp_newline_and_indent (pp, 2); | |
69 | pp_accesses (pp, new_defs); | |
70 | pp_indentation (pp) -= 2; | |
71 | ||
72 | pp_newline_and_indent (pp, 0); | |
73 | pp_string (pp, "first insert-after candidate: "); | |
74 | move_range.first->print_identifier_and_location (pp); | |
75 | ||
76 | pp_newline_and_indent (pp, 0); | |
77 | pp_string (pp, "last insert-after candidate: "); | |
78 | move_range.last->print_identifier_and_location (pp); | |
79 | } | |
80 | } | |
81 | ||
82 | // Return a copy of access_array ACCESSES, allocating it on the | |
83 | // temporary obstack. | |
84 | access_array | |
85 | function_info::temp_access_array (access_array accesses) | |
86 | { | |
87 | if (accesses.empty ()) | |
88 | return accesses; | |
89 | ||
90 | gcc_assert (obstack_object_size (&m_temp_obstack) == 0); | |
91 | obstack_grow (&m_temp_obstack, accesses.begin (), accesses.size_bytes ()); | |
92 | return { static_cast<access_info **> (obstack_finish (&m_temp_obstack)), | |
93 | accesses.size () }; | |
94 | } | |
95 | ||
96 | // See the comment above the declaration. | |
97 | bool | |
98 | function_info::verify_insn_changes (array_slice<insn_change *const> changes) | |
99 | { | |
100 | HARD_REG_SET defined_hard_regs, clobbered_hard_regs; | |
101 | CLEAR_HARD_REG_SET (defined_hard_regs); | |
102 | CLEAR_HARD_REG_SET (clobbered_hard_regs); | |
103 | ||
104 | insn_info *min_insn = m_first_insn; | |
105 | for (insn_change *change : changes) | |
106 | if (!change->is_deletion ()) | |
107 | { | |
108 | // Make sure that the changes can be kept in their current order | |
109 | // while honoring all of the move ranges. | |
110 | min_insn = later_insn (min_insn, change->move_range.first); | |
111 | while (min_insn != change->insn () && !can_insert_after (min_insn)) | |
112 | min_insn = min_insn->next_nondebug_insn (); | |
113 | if (*min_insn > *change->move_range.last) | |
114 | { | |
115 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
116 | fprintf (dump_file, "no viable insn position assignment\n"); | |
117 | return false; | |
118 | } | |
119 | ||
120 | // If recog introduced new clobbers of a register as part of | |
121 | // the matching process, make sure that they don't conflict | |
122 | // with any other new definitions or uses of the register. | |
123 | // (We have already checked that they don't conflict with | |
124 | // unchanging definitions and uses.) | |
125 | for (use_info *use : change->new_uses) | |
126 | { | |
127 | unsigned int regno = use->regno (); | |
128 | if (HARD_REGISTER_NUM_P (regno) | |
129 | && TEST_HARD_REG_BIT (clobbered_hard_regs, regno)) | |
130 | { | |
131 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
132 | fprintf (dump_file, "register %d would be clobbered" | |
133 | " while it is still live\n", regno); | |
134 | return false; | |
135 | } | |
136 | } | |
137 | for (def_info *def : change->new_defs) | |
138 | { | |
139 | unsigned int regno = def->regno (); | |
140 | if (HARD_REGISTER_NUM_P (regno)) | |
141 | { | |
142 | if (def->m_is_temp) | |
143 | { | |
144 | // This is a clobber introduced by recog. | |
145 | gcc_checking_assert (is_a<clobber_info *> (def)); | |
146 | if (TEST_HARD_REG_BIT (defined_hard_regs, regno)) | |
147 | { | |
148 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
149 | fprintf (dump_file, "conflicting definitions of" | |
150 | " register %d\n", regno); | |
151 | return false; | |
152 | } | |
153 | SET_HARD_REG_BIT (clobbered_hard_regs, regno); | |
154 | } | |
155 | else if (is_a<set_info *> (def)) | |
156 | { | |
157 | // REGNO now has a defined value. | |
158 | SET_HARD_REG_BIT (defined_hard_regs, regno); | |
159 | CLEAR_HARD_REG_BIT (clobbered_hard_regs, regno); | |
160 | } | |
161 | } | |
162 | } | |
163 | } | |
164 | return true; | |
165 | } | |
166 | ||
167 | // See the comment above the declaration. | |
168 | bool | |
169 | rtl_ssa::changes_are_worthwhile (array_slice<insn_change *const> changes, | |
170 | bool strict_p) | |
171 | { | |
172 | unsigned int old_cost = 0; | |
173 | unsigned int new_cost = 0; | |
174 | for (insn_change *change : changes) | |
175 | { | |
176 | old_cost += change->old_cost (); | |
177 | if (!change->is_deletion ()) | |
178 | { | |
179 | basic_block cfg_bb = change->bb ()->cfg_bb (); | |
180 | change->new_cost = insn_cost (change->rtl (), | |
181 | optimize_bb_for_speed_p (cfg_bb)); | |
182 | new_cost += change->new_cost; | |
183 | } | |
184 | } | |
185 | bool ok_p = (strict_p ? new_cost < old_cost : new_cost <= old_cost); | |
186 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
187 | { | |
188 | fprintf (dump_file, "original cost"); | |
189 | char sep = '='; | |
190 | for (const insn_change *change : changes) | |
191 | { | |
192 | fprintf (dump_file, " %c %d", sep, change->old_cost ()); | |
193 | sep = '+'; | |
194 | } | |
195 | fprintf (dump_file, ", replacement cost"); | |
196 | sep = '='; | |
197 | for (const insn_change *change : changes) | |
198 | if (!change->is_deletion ()) | |
199 | { | |
200 | fprintf (dump_file, " %c %d", sep, change->new_cost); | |
201 | sep = '+'; | |
202 | } | |
203 | fprintf (dump_file, "; %s\n", | |
204 | ok_p ? "keeping replacement" : "rejecting replacement"); | |
205 | } | |
206 | if (!ok_p) | |
207 | return false; | |
208 | ||
209 | return true; | |
210 | } | |
211 | ||
212 | // Update the REG_NOTES of INSN, whose pattern has just been changed. | |
213 | static void | |
214 | update_notes (rtx_insn *insn) | |
215 | { | |
216 | for (rtx *note_ptr = ®_NOTES (insn); *note_ptr; ) | |
217 | { | |
218 | rtx note = *note_ptr; | |
219 | bool keep_p = true; | |
220 | switch (REG_NOTE_KIND (note)) | |
221 | { | |
222 | case REG_EQUAL: | |
223 | case REG_EQUIV: | |
224 | case REG_NOALIAS: | |
225 | keep_p = (single_set (insn) != nullptr); | |
226 | break; | |
227 | ||
228 | case REG_UNUSED: | |
229 | case REG_DEAD: | |
230 | // These notes are stale. We'll recompute REG_UNUSED notes | |
231 | // after the update. | |
232 | keep_p = false; | |
233 | break; | |
234 | ||
235 | default: | |
236 | break; | |
237 | } | |
238 | if (keep_p) | |
239 | note_ptr = &XEXP (*note_ptr, 1); | |
240 | else | |
241 | { | |
242 | *note_ptr = XEXP (*note_ptr, 1); | |
243 | free_EXPR_LIST_node (note); | |
244 | } | |
245 | } | |
246 | } | |
247 | ||
248 | // Pick a location for CHANGE's instruction and return the instruction | |
249 | // after which it should be placed. | |
250 | static insn_info * | |
251 | choose_insn_placement (insn_change &change) | |
252 | { | |
253 | gcc_checking_assert (change.move_range); | |
254 | ||
255 | insn_info *insn = change.insn (); | |
256 | insn_info *first = change.move_range.first; | |
257 | insn_info *last = change.move_range.last; | |
258 | ||
259 | // Quick(ish) exit if there is only one possible choice. | |
260 | if (first == last) | |
261 | return first; | |
262 | if (first == insn->prev_nondebug_insn () && last == insn) | |
263 | return insn; | |
264 | ||
265 | // For now just use the closest valid choice to the original instruction. | |
266 | // If the register usage has changed significantly, it might instead be | |
267 | // better to try to take register pressure into account. | |
268 | insn_info *closest = change.move_range.clamp_insn_to_range (insn); | |
269 | while (closest != insn && !can_insert_after (closest)) | |
270 | closest = closest->next_nondebug_insn (); | |
271 | return closest; | |
272 | } | |
273 | ||
274 | // Record any changes related to CHANGE that need to be queued for later. | |
275 | void | |
276 | function_info::possibly_queue_changes (insn_change &change) | |
277 | { | |
278 | insn_info *insn = change.insn (); | |
279 | rtx_insn *rtl = insn->rtl (); | |
280 | ||
281 | // If the instruction could previously throw, we eventually need to call | |
282 | // purge_dead_edges to check whether things have changed. | |
283 | if (find_reg_note (rtl, REG_EH_REGION, nullptr)) | |
284 | bitmap_set_bit (m_need_to_purge_dead_edges, insn->bb ()->index ()); | |
285 | ||
286 | auto needs_pending_update = [&]() | |
287 | { | |
288 | // If an instruction became a no-op without the pass explicitly | |
289 | // deleting it, queue the deletion for later. Removing the | |
290 | // instruction on the fly would require an update to all instructions | |
291 | // that use the result of the move, which would be a potential source | |
292 | // of quadraticness. Also, definitions shouldn't disappear under | |
293 | // the pass's feet. | |
294 | if (INSN_CODE (rtl) == NOOP_MOVE_INSN_CODE) | |
295 | return true; | |
296 | ||
297 | // If any jumps got turned into unconditional jumps or nops, we need | |
298 | // to update the CFG accordingly. | |
299 | if (JUMP_P (rtl) | |
300 | && (returnjump_p (rtl) || any_uncondjump_p (rtl)) | |
301 | && !single_succ_p (insn->bb ()->cfg_bb ())) | |
302 | return true; | |
303 | ||
304 | // If a previously conditional trap now always fires, execution | |
305 | // terminates at that point. | |
306 | rtx pattern = PATTERN (rtl); | |
307 | if (GET_CODE (pattern) == TRAP_IF | |
308 | && XEXP (pattern, 0) == const1_rtx) | |
309 | return true; | |
310 | ||
311 | return false; | |
312 | }; | |
313 | ||
314 | if (needs_pending_update () | |
315 | && bitmap_set_bit (m_queued_insn_update_uids, insn->uid ())) | |
316 | { | |
317 | gcc_assert (!change.is_deletion ()); | |
318 | m_queued_insn_updates.safe_push (insn); | |
319 | } | |
320 | } | |
321 | ||
322 | // Remove the instruction described by CHANGE from the underlying RTL | |
323 | // and from the insn_info list. | |
324 | static void | |
325 | delete_insn (insn_change &change) | |
326 | { | |
327 | insn_info *insn = change.insn (); | |
328 | rtx_insn *rtl = change.rtl (); | |
329 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
330 | fprintf (dump_file, "deleting insn %d\n", insn->uid ()); | |
331 | set_insn_deleted (rtl); | |
332 | } | |
333 | ||
334 | // Move the RTL instruction associated with CHANGE so that it comes | |
335 | // immediately after AFTER. | |
336 | static void | |
337 | move_insn (insn_change &change, insn_info *after) | |
338 | { | |
339 | rtx_insn *rtl = change.rtl (); | |
340 | rtx_insn *after_rtl = after->rtl (); | |
341 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
342 | fprintf (dump_file, "moving insn %d after insn %d\n", | |
343 | INSN_UID (rtl), INSN_UID (after_rtl)); | |
344 | ||
345 | // At the moment we don't support moving instructions between EBBs, | |
346 | // but this would be worth adding if it's useful. | |
347 | insn_info *insn = change.insn (); | |
348 | gcc_assert (after->ebb () == insn->ebb ()); | |
349 | bb_info *bb = after->bb (); | |
350 | basic_block cfg_bb = bb->cfg_bb (); | |
351 | ||
352 | if (insn->bb () != bb) | |
353 | // Force DF to mark the old block as dirty. | |
354 | df_insn_delete (rtl); | |
355 | ::remove_insn (rtl); | |
356 | ::add_insn_after (rtl, after_rtl, cfg_bb); | |
357 | } | |
358 | ||
359 | // The instruction associated with CHANGE is being changed in-place. | |
360 | // Update the DF information for its new pattern. | |
361 | static void | |
362 | update_insn_in_place (insn_change &change) | |
363 | { | |
364 | insn_info *insn = change.insn (); | |
365 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
366 | fprintf (dump_file, "updating insn %d in-place\n", insn->uid ()); | |
367 | df_insn_rescan (change.rtl ()); | |
368 | } | |
369 | ||
370 | // Finalize the new list of definitions and uses in CHANGE, removing | |
371 | // any uses and definitions that are no longer needed, and converting | |
372 | // pending clobbers into actual definitions. | |
373 | void | |
374 | function_info::finalize_new_accesses (insn_change &change) | |
375 | { | |
376 | insn_info *insn = change.insn (); | |
377 | ||
378 | // Get a list of all the things that the instruction now references. | |
379 | vec_rtx_properties properties; | |
380 | properties.add_insn (insn->rtl (), true); | |
381 | ||
382 | // Build up the new list of definitions. | |
383 | for (rtx_obj_reference ref : properties.refs ()) | |
384 | if (ref.is_write ()) | |
385 | { | |
386 | def_info *def = find_access (change.new_defs, ref.regno); | |
387 | gcc_assert (def); | |
388 | if (def->m_is_temp) | |
389 | { | |
390 | // At present, the only temporary instruction definitions we | |
391 | // create are clobbers, such as those added during recog. | |
392 | gcc_assert (is_a<clobber_info *> (def)); | |
393 | def = allocate<clobber_info> (change.insn (), ref.regno); | |
394 | } | |
395 | else if (!def->m_has_been_superceded) | |
396 | { | |
397 | // This is a second or subsequent definition. | |
398 | // See function_info::record_def for a discussion of when | |
399 | // this can happen. | |
400 | def->record_reference (ref, false); | |
401 | continue; | |
402 | } | |
403 | else | |
404 | { | |
405 | def->m_has_been_superceded = false; | |
406 | ||
407 | // Clobbers can move around, so remove them from their current | |
408 | // position and them back in their final position. | |
409 | // | |
410 | // At the moment, we don't allow sets to move relative to other | |
411 | // definitions of the same resource, so we can leave those where | |
412 | // they are. It might be useful to relax this in future. | |
413 | // The main complication is that removing a set would potentially | |
414 | // fuse two adjoining clobber_groups, and adding the set back | |
415 | // would require the group to be split again. | |
416 | if (is_a<clobber_info *> (def)) | |
417 | remove_def (def); | |
418 | else if (ref.is_reg ()) | |
419 | def->set_mode (ref.mode); | |
420 | def->set_insn (insn); | |
421 | } | |
422 | def->record_reference (ref, true); | |
423 | m_temp_defs.safe_push (def); | |
424 | } | |
425 | ||
426 | // Also keep any explicitly-recorded call clobbers, which are deliberately | |
8a25be51 RS |
427 | // excluded from the vec_rtx_properties. Calls shouldn't move, so we can |
428 | // keep the definitions in their current position. | |
73b75827 RS |
429 | for (def_info *def : change.new_defs) |
430 | if (def->m_has_been_superceded && def->is_call_clobber ()) | |
431 | { | |
432 | def->m_has_been_superceded = false; | |
433 | def->set_insn (insn); | |
434 | m_temp_defs.safe_push (def); | |
435 | } | |
436 | ||
437 | // Install the new list of definitions in CHANGE. | |
438 | sort_accesses (m_temp_defs); | |
439 | access_array accesses = temp_access_array (m_temp_defs); | |
440 | change.new_defs = def_array (accesses); | |
441 | m_temp_defs.truncate (0); | |
442 | ||
443 | // Create temporary copies of use_infos that are already attached to | |
444 | // other insns, which could happen if the uses come from unchanging | |
445 | // insns or if they have been used by earlier changes. Doing this | |
446 | // makes it easier to detect multiple reads below. | |
447 | auto *unshared_uses_base = XOBNEWVEC (&m_temp_obstack, access_info *, | |
448 | change.new_uses.size ()); | |
449 | unsigned int i = 0; | |
450 | for (use_info *use : change.new_uses) | |
451 | { | |
452 | if (!use->m_has_been_superceded) | |
453 | { | |
454 | use = allocate_temp<use_info> (insn, use->resource (), use->def ()); | |
455 | use->m_has_been_superceded = true; | |
456 | use->m_is_temp = true; | |
457 | } | |
458 | unshared_uses_base[i++] = use; | |
459 | } | |
460 | auto unshared_uses = use_array (unshared_uses_base, change.new_uses.size ()); | |
461 | ||
462 | // Add (possibly temporary) uses to m_temp_uses for each resource. | |
463 | // If there are multiple references to the same resource, aggregate | |
464 | // information in the modes and flags. | |
465 | for (rtx_obj_reference ref : properties.refs ()) | |
466 | if (ref.is_read ()) | |
467 | { | |
468 | unsigned int regno = ref.regno; | |
469 | machine_mode mode = ref.is_reg () ? ref.mode : BLKmode; | |
470 | use_info *use = find_access (unshared_uses, ref.regno); | |
471 | gcc_assert (use); | |
472 | if (use->m_has_been_superceded) | |
473 | { | |
474 | // This is the first reference to the resource. | |
475 | bool is_temp = use->m_is_temp; | |
476 | *use = use_info (insn, resource_info { mode, regno }, use->def ()); | |
477 | use->m_is_temp = is_temp; | |
478 | use->record_reference (ref, true); | |
479 | m_temp_uses.safe_push (use); | |
480 | } | |
481 | else | |
482 | { | |
483 | // Record the mode of the largest use. The choice is arbitrary if | |
484 | // the instruction (unusually) references the same register in two | |
485 | // different but equal-sized modes. | |
486 | if (HARD_REGISTER_NUM_P (regno) | |
487 | && partial_subreg_p (use->mode (), mode)) | |
488 | use->set_mode (mode); | |
489 | use->record_reference (ref, false); | |
490 | } | |
491 | } | |
492 | ||
493 | // Replace any temporary uses and definitions with real ones. | |
494 | for (unsigned int i = 0; i < m_temp_uses.length (); ++i) | |
495 | { | |
496 | auto *use = as_a<use_info *> (m_temp_uses[i]); | |
497 | if (use->m_is_temp) | |
498 | { | |
499 | m_temp_uses[i] = use = allocate<use_info> (*use); | |
500 | use->m_is_temp = false; | |
501 | set_info *def = use->def (); | |
502 | // Handle cases in which the value was previously not used | |
503 | // within the block. | |
504 | if (def && def->m_is_temp) | |
505 | { | |
506 | phi_info *phi = as_a<phi_info *> (def); | |
507 | gcc_assert (phi->is_degenerate ()); | |
508 | phi = create_degenerate_phi (phi->ebb (), phi->input_value (0)); | |
509 | use->set_def (phi); | |
510 | } | |
511 | } | |
512 | } | |
513 | ||
514 | // Install the new list of definitions in CHANGE. | |
515 | sort_accesses (m_temp_uses); | |
516 | change.new_uses = use_array (temp_access_array (m_temp_uses)); | |
517 | m_temp_uses.truncate (0); | |
518 | ||
519 | // Record the new instruction-wide properties. | |
520 | insn->set_properties (properties); | |
521 | } | |
522 | ||
523 | // Copy information from CHANGE to its underlying insn_info, given that | |
524 | // the insn_info has already been placed appropriately. | |
525 | void | |
526 | function_info::apply_changes_to_insn (insn_change &change) | |
527 | { | |
528 | insn_info *insn = change.insn (); | |
529 | if (change.is_deletion ()) | |
530 | { | |
531 | insn->set_accesses (nullptr, 0, 0); | |
532 | return; | |
533 | } | |
534 | ||
535 | // Copy the cost. | |
536 | insn->set_cost (change.new_cost); | |
537 | ||
8a25be51 RS |
538 | // Add all clobbers. Sets and call clobbers never move relative to |
539 | // other definitions, so are OK as-is. | |
73b75827 | 540 | for (def_info *def : change.new_defs) |
8a25be51 | 541 | if (is_a<clobber_info *> (def) && !def->is_call_clobber ()) |
73b75827 RS |
542 | add_def (def); |
543 | ||
544 | // Add all uses, now that their position is final. | |
545 | for (use_info *use : change.new_uses) | |
546 | add_use (use); | |
547 | ||
548 | // Copy the uses and definitions. | |
549 | unsigned int num_defs = change.new_defs.size (); | |
550 | unsigned int num_uses = change.new_uses.size (); | |
551 | if (num_defs + num_uses <= insn->num_defs () + insn->num_uses ()) | |
552 | insn->copy_accesses (change.new_defs, change.new_uses); | |
553 | else | |
554 | { | |
555 | access_array_builder builder (&m_obstack); | |
556 | builder.reserve (num_defs + num_uses); | |
557 | ||
558 | for (def_info *def : change.new_defs) | |
559 | builder.quick_push (def); | |
560 | for (use_info *use : change.new_uses) | |
561 | builder.quick_push (use); | |
562 | ||
563 | insn->set_accesses (builder.finish ().begin (), num_defs, num_uses); | |
564 | } | |
565 | ||
566 | add_reg_unused_notes (insn); | |
567 | } | |
568 | ||
569 | // Add a temporary placeholder instruction after AFTER. | |
570 | insn_info * | |
571 | function_info::add_placeholder_after (insn_info *after) | |
572 | { | |
573 | insn_info *insn = allocate_temp<insn_info> (after->bb (), nullptr, -1); | |
574 | add_insn_after (insn, after); | |
575 | return insn; | |
576 | } | |
577 | ||
578 | // See the comment above the declaration. | |
579 | void | |
580 | function_info::change_insns (array_slice<insn_change *> changes) | |
581 | { | |
582 | auto watermark = temp_watermark (); | |
583 | ||
584 | insn_info *min_insn = m_first_insn; | |
585 | for (insn_change *change : changes) | |
586 | { | |
587 | // Tentatively mark all the old uses and definitions for deletion. | |
588 | for (use_info *use : change->old_uses ()) | |
589 | { | |
590 | use->m_has_been_superceded = true; | |
591 | remove_use (use); | |
592 | } | |
593 | for (def_info *def : change->old_defs ()) | |
594 | def->m_has_been_superceded = true; | |
595 | ||
596 | if (!change->is_deletion ()) | |
597 | { | |
598 | // Remove any notes that are no longer relevant. | |
599 | update_notes (change->rtl ()); | |
600 | ||
601 | // Make sure that the placement of this instruction would still | |
602 | // leave room for previous instructions. | |
603 | change->move_range = move_later_than (change->move_range, min_insn); | |
604 | if (!canonicalize_move_range (change->move_range, change->insn ())) | |
605 | // verify_insn_changes is supposed to make sure that this holds. | |
606 | gcc_unreachable (); | |
607 | min_insn = later_insn (min_insn, change->move_range.first); | |
608 | } | |
609 | } | |
610 | ||
611 | // Walk backwards through the changes, allocating specific positions | |
612 | // to each one. Update the underlying RTL and its associated DF | |
613 | // information. | |
614 | insn_info *following_insn = nullptr; | |
615 | auto_vec<insn_info *, 16> placeholders; | |
616 | placeholders.safe_grow_cleared (changes.size ()); | |
617 | for (unsigned int i = changes.size (); i-- > 0;) | |
618 | { | |
619 | insn_change &change = *changes[i]; | |
620 | insn_info *placeholder = nullptr; | |
621 | possibly_queue_changes (change); | |
622 | if (change.is_deletion ()) | |
623 | delete_insn (change); | |
624 | else | |
625 | { | |
626 | // Make sure that this instruction comes before later ones. | |
627 | if (following_insn) | |
628 | { | |
629 | change.move_range = move_earlier_than (change.move_range, | |
630 | following_insn); | |
631 | if (!canonicalize_move_range (change.move_range, | |
632 | change.insn ())) | |
633 | // verify_insn_changes is supposed to make sure that this | |
634 | // holds. | |
635 | gcc_unreachable (); | |
636 | } | |
637 | ||
638 | // Decide which instruction INSN should go after. | |
639 | insn_info *after = choose_insn_placement (change); | |
640 | ||
641 | // If INSN is moving, insert a placeholder insn_info at the | |
642 | // new location. We can't move INSN itself yet because it | |
643 | // might still be referenced by earlier move ranges. | |
644 | insn_info *insn = change.insn (); | |
645 | if (after == insn || after == insn->prev_nondebug_insn ()) | |
646 | { | |
647 | update_insn_in_place (change); | |
648 | following_insn = insn; | |
649 | } | |
650 | else | |
651 | { | |
652 | move_insn (change, after); | |
653 | placeholder = add_placeholder_after (after); | |
654 | following_insn = placeholder; | |
655 | } | |
656 | ||
657 | // Finalize the new list of accesses for the change. Don't install | |
658 | // them yet, so that we still have access to the old lists below. | |
659 | finalize_new_accesses (change); | |
660 | } | |
661 | placeholders[i] = placeholder; | |
662 | } | |
663 | ||
664 | // Remove all definitions that are no longer needed. After the above, | |
665 | // such definitions should no longer have any registered users. | |
666 | // | |
667 | // In particular, this means that consumers must handle debug | |
668 | // instructions before removing a set. | |
669 | for (insn_change *change : changes) | |
670 | for (def_info *def : change->old_defs ()) | |
671 | if (def->m_has_been_superceded) | |
672 | { | |
673 | auto *set = dyn_cast<set_info *> (def); | |
674 | gcc_assert (!set || !set->has_any_uses ()); | |
675 | remove_def (def); | |
676 | } | |
677 | ||
678 | // Move the insn_infos to their new locations. | |
679 | for (unsigned int i = 0; i < changes.size (); ++i) | |
680 | { | |
681 | insn_change &change = *changes[i]; | |
682 | insn_info *insn = change.insn (); | |
683 | if (change.is_deletion ()) | |
684 | remove_insn (insn); | |
685 | else if (insn_info *placeholder = placeholders[i]) | |
686 | { | |
687 | // Check if earlier movements turned a move into a no-op. | |
688 | if (placeholder->prev_nondebug_insn () == insn | |
689 | || placeholder->next_nondebug_insn () == insn) | |
690 | { | |
691 | remove_insn (placeholder); | |
692 | placeholders[i] = nullptr; | |
693 | } | |
694 | else | |
695 | { | |
696 | // Remove the placeholder first so that we have a wider range of | |
697 | // program points when inserting INSN. | |
698 | insn_info *after = placeholder->prev_any_insn (); | |
699 | remove_insn (insn); | |
700 | remove_insn (placeholder); | |
701 | insn->set_bb (after->bb ()); | |
702 | add_insn_after (insn, after); | |
703 | } | |
704 | } | |
705 | } | |
706 | ||
707 | // Finally apply the changes to the underlying insn_infos. | |
708 | for (insn_change *change : changes) | |
709 | apply_changes_to_insn (*change); | |
710 | } | |
711 | ||
712 | // See the comment above the declaration. | |
713 | void | |
714 | function_info::change_insn (insn_change &change) | |
715 | { | |
716 | insn_change *changes[] = { &change }; | |
717 | return change_insns (changes); | |
718 | } | |
719 | ||
720 | // Try to adjust CHANGE so that its pattern can include clobber rtx CLOBBER. | |
721 | // Return true on success. | |
722 | // | |
723 | // ADD_REGNO_CLOBBER is a specialization of function_info::add_regno_clobber | |
724 | // for a specific caller-provided predicate. | |
725 | static bool | |
726 | add_clobber (insn_change &change, add_regno_clobber_fn add_regno_clobber, | |
727 | rtx clobber) | |
728 | { | |
729 | rtx pat = PATTERN (change.rtl ()); | |
730 | gcc_assert (GET_CODE (clobber) == CLOBBER); | |
731 | rtx dest = XEXP (clobber, 0); | |
732 | if (GET_CODE (dest) == SCRATCH) | |
733 | { | |
734 | if (reload_completed) | |
735 | { | |
736 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
737 | { | |
738 | // ??? Maybe we could try to do some RA here? | |
739 | fprintf (dump_file, "instruction requires a scratch" | |
740 | " after reload:\n"); | |
741 | print_rtl_single (dump_file, pat); | |
742 | } | |
743 | return false; | |
744 | } | |
745 | return true; | |
746 | } | |
747 | ||
748 | gcc_assert (REG_P (dest)); | |
749 | for (unsigned int regno = REGNO (dest); regno != END_REGNO (dest); ++regno) | |
750 | if (!add_regno_clobber (change, regno)) | |
751 | { | |
752 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
753 | { | |
754 | fprintf (dump_file, "cannot clobber live register %d in:\n", | |
755 | regno); | |
756 | print_rtl_single (dump_file, pat); | |
757 | } | |
758 | return false; | |
759 | } | |
760 | return true; | |
761 | } | |
762 | ||
763 | // Try to recognize the new form of the insn associated with CHANGE, | |
764 | // adding any clobbers that are necessary to make the instruction match | |
765 | // an .md pattern. Return true on success. | |
766 | // | |
767 | // ADD_REGNO_CLOBBER is a specialization of function_info::add_regno_clobber | |
768 | // for a specific caller-provided predicate. | |
769 | static bool | |
770 | recog_level2 (insn_change &change, add_regno_clobber_fn add_regno_clobber) | |
771 | { | |
772 | insn_change_watermark insn_watermark; | |
773 | rtx_insn *rtl = change.rtl (); | |
774 | rtx pat = PATTERN (rtl); | |
775 | int num_clobbers = 0; | |
776 | int icode = -1; | |
777 | bool asm_p = asm_noperands (pat) >= 0; | |
778 | if (asm_p) | |
779 | { | |
780 | if (!check_asm_operands (pat)) | |
781 | { | |
782 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
783 | { | |
784 | fprintf (dump_file, "failed to match this asm instruction:\n"); | |
785 | print_rtl_single (dump_file, pat); | |
786 | } | |
787 | return false; | |
788 | } | |
789 | } | |
790 | else if (noop_move_p (rtl)) | |
791 | { | |
792 | INSN_CODE (rtl) = NOOP_MOVE_INSN_CODE; | |
793 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
794 | { | |
795 | fprintf (dump_file, "instruction becomes a no-op:\n"); | |
796 | print_rtl_single (dump_file, pat); | |
797 | } | |
798 | insn_watermark.keep (); | |
799 | return true; | |
800 | } | |
801 | else | |
802 | { | |
803 | icode = ::recog (pat, rtl, &num_clobbers); | |
804 | if (icode < 0) | |
805 | { | |
806 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
807 | { | |
808 | fprintf (dump_file, "failed to match this instruction:\n"); | |
809 | print_rtl_single (dump_file, pat); | |
810 | } | |
811 | return false; | |
812 | } | |
813 | } | |
814 | ||
815 | auto prev_new_defs = change.new_defs; | |
816 | auto prev_move_range = change.move_range; | |
817 | if (num_clobbers > 0) | |
818 | { | |
819 | // ??? It would be good to have a way of recycling the rtxes on failure, | |
820 | // but any attempt to cache old PARALLELs would at best be a half | |
821 | // measure, since add_clobbers would still generate fresh clobbers | |
822 | // each time. It would be better to have a more general recycling | |
823 | // mechanism that all rtx passes can use. | |
824 | rtvec newvec; | |
825 | int oldlen; | |
826 | if (GET_CODE (pat) == PARALLEL) | |
827 | { | |
828 | oldlen = XVECLEN (pat, 0); | |
829 | newvec = rtvec_alloc (num_clobbers + oldlen); | |
830 | for (int i = 0; i < oldlen; ++i) | |
831 | RTVEC_ELT (newvec, i) = XVECEXP (pat, 0, i); | |
832 | } | |
833 | else | |
834 | { | |
835 | oldlen = 1; | |
836 | newvec = rtvec_alloc (num_clobbers + oldlen); | |
837 | RTVEC_ELT (newvec, 0) = pat; | |
838 | } | |
839 | rtx newpat = gen_rtx_PARALLEL (VOIDmode, newvec); | |
840 | add_clobbers (newpat, icode); | |
841 | validate_change (rtl, &PATTERN (rtl), newpat, true); | |
842 | for (int i = 0; i < num_clobbers; ++i) | |
843 | if (!add_clobber (change, add_regno_clobber, | |
844 | XVECEXP (newpat, 0, oldlen + i))) | |
845 | { | |
846 | change.new_defs = prev_new_defs; | |
847 | change.move_range = prev_move_range; | |
848 | return false; | |
849 | } | |
850 | ||
851 | pat = newpat; | |
852 | } | |
853 | ||
854 | INSN_CODE (rtl) = icode; | |
855 | if (reload_completed) | |
856 | { | |
857 | extract_insn (rtl); | |
858 | if (!constrain_operands (1, get_preferred_alternatives (rtl))) | |
859 | { | |
860 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
861 | { | |
862 | if (asm_p) | |
863 | fprintf (dump_file, "asm does not match its constraints:\n"); | |
864 | else if (const char *name = get_insn_name (icode)) | |
865 | fprintf (dump_file, "instruction does not match the" | |
866 | " constraints for %s:\n", name); | |
867 | else | |
868 | fprintf (dump_file, "instruction does not match its" | |
869 | " constraints:\n"); | |
870 | print_rtl_single (dump_file, pat); | |
871 | } | |
872 | change.new_defs = prev_new_defs; | |
873 | change.move_range = prev_move_range; | |
874 | return false; | |
875 | } | |
876 | } | |
877 | ||
878 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
879 | { | |
880 | const char *name; | |
881 | if (!asm_p && (name = get_insn_name (icode))) | |
882 | fprintf (dump_file, "successfully matched this instruction " | |
883 | "to %s:\n", name); | |
884 | else | |
885 | fprintf (dump_file, "successfully matched this instruction:\n"); | |
886 | print_rtl_single (dump_file, pat); | |
887 | } | |
888 | ||
889 | insn_watermark.keep (); | |
890 | return true; | |
891 | } | |
892 | ||
893 | // Try to recognize the new form of the insn associated with CHANGE, | |
894 | // adding and removing clobbers as necessary to make the instruction | |
895 | // match an .md pattern. Return true on success, otherwise leave | |
896 | // CHANGE as it was on entry. | |
897 | // | |
898 | // ADD_REGNO_CLOBBER is a specialization of function_info::add_regno_clobber | |
899 | // for a specific caller-provided predicate. | |
900 | bool | |
901 | rtl_ssa::recog_internal (insn_change &change, | |
902 | add_regno_clobber_fn add_regno_clobber) | |
903 | { | |
904 | // Accept all changes to debug instructions. | |
905 | insn_info *insn = change.insn (); | |
906 | if (insn->is_debug_insn ()) | |
907 | return true; | |
908 | ||
909 | rtx_insn *rtl = insn->rtl (); | |
910 | rtx pat = PATTERN (rtl); | |
911 | if (GET_CODE (pat) == PARALLEL && asm_noperands (pat) < 0) | |
912 | { | |
913 | // Try to remove trailing (clobber (scratch)) rtxes, since the new form | |
914 | // of the instruction might not need those scratches. recog will add | |
915 | // back any that are needed. | |
916 | int len = XVECLEN (pat, 0); | |
917 | int new_len = len; | |
918 | while (new_len > 0 | |
919 | && GET_CODE (XVECEXP (pat, 0, new_len - 1)) == CLOBBER | |
920 | && GET_CODE (XEXP (XVECEXP (pat, 0, new_len - 1), 0)) == SCRATCH) | |
921 | new_len -= 1; | |
922 | ||
923 | int old_num_changes = num_validated_changes (); | |
924 | validate_change_xveclen (rtl, &PATTERN (rtl), new_len, true); | |
925 | if (recog_level2 (change, add_regno_clobber)) | |
926 | return true; | |
927 | cancel_changes (old_num_changes); | |
928 | ||
929 | // Try to remove all trailing clobbers. For example, a pattern that | |
930 | // used to clobber the flags might no longer need to do so. | |
931 | int prev_len = new_len; | |
932 | while (new_len > 0 | |
933 | && GET_CODE (XVECEXP (pat, 0, new_len - 1)) == CLOBBER) | |
934 | new_len -= 1; | |
935 | if (new_len != prev_len) | |
936 | { | |
937 | validate_change_xveclen (rtl, &PATTERN (rtl), new_len, true); | |
938 | if (recog_level2 (change, add_regno_clobber)) | |
939 | return true; | |
940 | cancel_changes (old_num_changes); | |
941 | } | |
942 | return false; | |
943 | } | |
944 | ||
945 | return recog_level2 (change, add_regno_clobber); | |
946 | } | |
947 | ||
948 | // See the comment above the declaration. | |
949 | bool | |
950 | function_info::perform_pending_updates () | |
951 | { | |
952 | bool changed_cfg = false; | |
953 | bool changed_jumps = false; | |
954 | for (insn_info *insn : m_queued_insn_updates) | |
955 | { | |
956 | rtx_insn *rtl = insn->rtl (); | |
957 | if (JUMP_P (rtl)) | |
958 | { | |
959 | if (INSN_CODE (rtl) == NOOP_MOVE_INSN_CODE) | |
960 | { | |
961 | ::delete_insn (rtl); | |
962 | bitmap_set_bit (m_need_to_purge_dead_edges, | |
963 | insn->bb ()->index ()); | |
964 | } | |
965 | else if (returnjump_p (rtl) || any_uncondjump_p (rtl)) | |
966 | { | |
967 | mark_jump_label (PATTERN (rtl), rtl, 0); | |
968 | update_cfg_for_uncondjump (rtl); | |
969 | changed_cfg = true; | |
970 | changed_jumps = true; | |
971 | } | |
972 | } | |
973 | else if (INSN_CODE (rtl) == NOOP_MOVE_INSN_CODE) | |
974 | ::delete_insn (rtl); | |
975 | else | |
976 | { | |
977 | rtx pattern = PATTERN (rtl); | |
978 | if (GET_CODE (pattern) == TRAP_IF | |
979 | && XEXP (pattern, 0) == const1_rtx) | |
980 | { | |
981 | remove_edge (split_block (BLOCK_FOR_INSN (rtl), rtl)); | |
982 | emit_barrier_after_bb (BLOCK_FOR_INSN (rtl)); | |
983 | changed_cfg = true; | |
984 | } | |
985 | } | |
986 | } | |
987 | ||
988 | unsigned int index; | |
989 | bitmap_iterator bi; | |
990 | EXECUTE_IF_SET_IN_BITMAP (m_need_to_purge_dead_edges, 0, index, bi) | |
991 | if (purge_dead_edges (BASIC_BLOCK_FOR_FN (m_fn, index))) | |
992 | changed_cfg = true; | |
993 | ||
994 | if (changed_jumps) | |
995 | // This uses its own timevar internally, so we don't need to push | |
996 | // one ourselves. | |
997 | rebuild_jump_labels (get_insns ()); | |
998 | ||
999 | bitmap_clear (m_need_to_purge_dead_edges); | |
1000 | bitmap_clear (m_queued_insn_update_uids); | |
1001 | m_queued_insn_updates.truncate (0); | |
1002 | ||
1003 | if (changed_cfg) | |
1004 | { | |
1005 | free_dominance_info (CDI_DOMINATORS); | |
1006 | free_dominance_info (CDI_POST_DOMINATORS); | |
1007 | } | |
1008 | ||
1009 | return changed_cfg; | |
1010 | } | |
1011 | ||
1012 | // Print a description of CHANGE to PP. | |
1013 | void | |
1014 | rtl_ssa::pp_insn_change (pretty_printer *pp, const insn_change &change) | |
1015 | { | |
1016 | change.print (pp); | |
1017 | } | |
1018 | ||
1019 | // Print a description of CHANGE to FILE. | |
1020 | void | |
1021 | dump (FILE *file, const insn_change &change) | |
1022 | { | |
1023 | dump_using (file, pp_insn_change, change); | |
1024 | } | |
1025 | ||
1026 | // Debug interface to the dump routine above. | |
1027 | void debug (const insn_change &x) { dump (stderr, x); } |