1// RTL SSA routines for changing instructions -*- C++ -*-
2// Copyright (C) 2020-2024 Free Software Foundation, Inc.
3//
4// This file is part of GCC.
5//
6// GCC is free software; you can redistribute it and/or modify it under
7// the terms of the GNU General Public License as published by the Free
8// Software Foundation; either version 3, or (at your option) any later
9// version.
10//
11// GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12// WARRANTY; without even the implied warranty of MERCHANTABILITY or
13// FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14// for more details.
15//
16// You should have received a copy of the GNU General Public License
17// along with GCC; see the file COPYING3. If not see
18// <http://www.gnu.org/licenses/>.
19
20#define INCLUDE_ALGORITHM
21#define INCLUDE_FUNCTIONAL
22#include "config.h"
23#include "system.h"
24#include "coretypes.h"
25#include "backend.h"
26#include "rtl.h"
27#include "df.h"
28#include "rtl-ssa.h"
29#include "rtl-ssa/internals.h"
30#include "rtl-ssa/internals.inl"
31#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#include "sreal.h"
38
39using namespace rtl_ssa;
40
41// See the comment above the declaration.
42void
43insn_change::print (pretty_printer *pp) const
44{
45 if (m_is_deletion)
46 {
47 pp_string (pp, "deletion of ");
48 pp_insn (pp, m_insn);
49 }
50 else
51 {
52 pp_string (pp, "change to ");
53 pp_insn (pp, m_insn);
54 pp_newline_and_indent (pp, 2);
55 pp_string (pp, "~~~~~~~");
56
57 pp_newline_and_indent (pp, 0);
58 pp_string (pp, "new cost: ");
59 pp_decimal_int (pp, new_cost);
60
61 pp_newline_and_indent (pp, 0);
62 pp_string (pp, "new uses:");
63 pp_newline_and_indent (pp, 2);
64 pp_accesses (pp, new_uses);
65 pp_indentation (pp) -= 2;
66
67 pp_newline_and_indent (pp, 0);
68 pp_string (pp, "new defs:");
69 pp_newline_and_indent (pp, 2);
70 pp_accesses (pp, new_defs);
71 pp_indentation (pp) -= 2;
72
73 pp_newline_and_indent (pp, 0);
74 pp_string (pp, "first insert-after candidate: ");
75 move_range.first->print_identifier_and_location (pp);
76
77 pp_newline_and_indent (pp, 0);
78 pp_string (pp, "last insert-after candidate: ");
79 move_range.last->print_identifier_and_location (pp);
80 }
81}
82
83// Return a copy of access_array ACCESSES, allocating it on the
84// temporary obstack.
85access_array
86function_info::temp_access_array (access_array accesses)
87{
88 if (accesses.empty ())
89 return accesses;
90
91 gcc_assert (obstack_object_size (&m_temp_obstack) == 0);
92 obstack_grow (&m_temp_obstack, accesses.begin (), accesses.size_bytes ());
93 return { static_cast<access_info **> (obstack_finish (&m_temp_obstack)),
94 accesses.size () };
95}
96
97// See the comment above the declaration.
98bool
99function_info::verify_insn_changes (array_slice<insn_change *const> changes)
100{
101 HARD_REG_SET defined_hard_regs, clobbered_hard_regs;
102 CLEAR_HARD_REG_SET (set&: defined_hard_regs);
103 CLEAR_HARD_REG_SET (set&: clobbered_hard_regs);
104
105 insn_info *min_insn = m_first_insn;
106 for (insn_change *change : changes)
107 if (!change->is_deletion ())
108 {
109 // Make sure that the changes can be kept in their current order
110 // while honoring all of the move ranges.
111 min_insn = later_insn (insn1: min_insn, insn2: change->move_range.first);
112 while (min_insn != change->insn () && !can_insert_after (insn: min_insn))
113 min_insn = min_insn->next_nondebug_insn ();
114 if (*min_insn > *change->move_range.last)
115 {
116 if (dump_file && (dump_flags & TDF_DETAILS))
117 fprintf (stream: dump_file, format: "no viable insn position assignment\n");
118 return false;
119 }
120
121 // If recog introduced new clobbers of a register as part of
122 // the matching process, make sure that they don't conflict
123 // with any other new definitions or uses of the register.
124 // (We have already checked that they don't conflict with
125 // unchanging definitions and uses.)
126 for (use_info *use : change->new_uses)
127 {
128 unsigned int regno = use->regno ();
129 if (HARD_REGISTER_NUM_P (regno)
130 && TEST_HARD_REG_BIT (set: clobbered_hard_regs, bit: regno))
131 {
132 if (dump_file && (dump_flags & TDF_DETAILS))
133 fprintf (stream: dump_file, format: "register %d would be clobbered"
134 " while it is still live\n", regno);
135 return false;
136 }
137 }
138 for (def_info *def : change->new_defs)
139 {
140 unsigned int regno = def->regno ();
141 if (HARD_REGISTER_NUM_P (regno))
142 {
143 if (def->m_is_temp)
144 {
145 // This is a clobber introduced by recog.
146 gcc_checking_assert (is_a<clobber_info *> (def));
147 if (TEST_HARD_REG_BIT (set: defined_hard_regs, bit: regno))
148 {
149 if (dump_file && (dump_flags & TDF_DETAILS))
150 fprintf (stream: dump_file, format: "conflicting definitions of"
151 " register %d\n", regno);
152 return false;
153 }
154 SET_HARD_REG_BIT (set&: clobbered_hard_regs, bit: regno);
155 }
156 else if (is_a<set_info *> (p: def))
157 {
158 // REGNO now has a defined value.
159 SET_HARD_REG_BIT (set&: defined_hard_regs, bit: regno);
160 CLEAR_HARD_REG_BIT (set&: clobbered_hard_regs, bit: regno);
161 }
162 }
163 }
164 }
165 return true;
166}
167
168// See the comment above the declaration.
169bool
170rtl_ssa::changes_are_worthwhile (array_slice<insn_change *const> changes,
171 bool strict_p)
172{
173 unsigned int old_cost = 0;
174 unsigned int new_cost = 0;
175 sreal weighted_old_cost = 0;
176 sreal weighted_new_cost = 0;
177 auto entry_count = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count;
178 for (insn_change *change : changes)
179 {
180 old_cost += change->old_cost ();
181 basic_block cfg_bb = change->bb ()->cfg_bb ();
182 bool for_speed = optimize_bb_for_speed_p (cfg_bb);
183 if (for_speed)
184 weighted_old_cost += (cfg_bb->count.to_sreal_scale (in: entry_count)
185 * change->old_cost ());
186 if (!change->is_deletion ())
187 {
188 change->new_cost = insn_cost (change->rtl (), for_speed);
189 new_cost += change->new_cost;
190 if (for_speed)
191 weighted_new_cost += (cfg_bb->count.to_sreal_scale (in: entry_count)
192 * change->new_cost);
193 }
194 }
195 bool ok_p;
196 if (weighted_new_cost != weighted_old_cost)
197 ok_p = weighted_new_cost < weighted_old_cost;
198 else if (strict_p)
199 ok_p = new_cost < old_cost;
200 else
201 ok_p = new_cost <= old_cost;
202 if (dump_file && (dump_flags & TDF_DETAILS))
203 {
204 fprintf (stream: dump_file, format: "original cost");
205 char sep = '=';
206 for (const insn_change *change : changes)
207 {
208 fprintf (stream: dump_file, format: " %c %d", sep, change->old_cost ());
209 sep = '+';
210 }
211 if (weighted_old_cost != 0)
212 fprintf (stream: dump_file, format: " (weighted: %f)", weighted_old_cost.to_double ());
213 fprintf (stream: dump_file, format: ", replacement cost");
214 sep = '=';
215 for (const insn_change *change : changes)
216 if (!change->is_deletion ())
217 {
218 fprintf (stream: dump_file, format: " %c %d", sep, change->new_cost);
219 sep = '+';
220 }
221 if (weighted_new_cost != 0)
222 fprintf (stream: dump_file, format: " (weighted: %f)", weighted_new_cost.to_double ());
223 fprintf (stream: dump_file, format: "; %s\n",
224 ok_p ? "keeping replacement" : "rejecting replacement");
225 }
226 if (!ok_p)
227 return false;
228
229 return true;
230}
231
232// SET has been deleted. Clean up all remaining uses. Such uses are
233// either dead phis or now-redundant live-out uses.
234void
235function_info::process_uses_of_deleted_def (set_info *set)
236{
237 if (!set->has_any_uses ())
238 return;
239
240 auto *use = *set->all_uses ().begin ();
241 do
242 {
243 auto *next_use = use->next_use ();
244 if (use->is_in_phi ())
245 {
246 // This call will not recurse.
247 process_uses_of_deleted_def (set: use->phi ());
248 delete_phi (use->phi ());
249 }
250 else
251 {
252 gcc_assert (use->is_live_out_use ());
253 remove_use (use);
254 }
255 use = next_use;
256 }
257 while (use);
258 gcc_assert (!set->has_any_uses ());
259}
260
261// Update the REG_NOTES of INSN, whose pattern has just been changed.
262static void
263update_notes (rtx_insn *insn)
264{
265 for (rtx *note_ptr = &REG_NOTES (insn); *note_ptr; )
266 {
267 rtx note = *note_ptr;
268 bool keep_p = true;
269 switch (REG_NOTE_KIND (note))
270 {
271 case REG_EQUAL:
272 case REG_EQUIV:
273 case REG_NOALIAS:
274 keep_p = (single_set (insn) != nullptr);
275 break;
276
277 case REG_UNUSED:
278 case REG_DEAD:
279 // These notes are stale. We'll recompute REG_UNUSED notes
280 // after the update.
281 keep_p = false;
282 break;
283
284 default:
285 break;
286 }
287 if (keep_p)
288 note_ptr = &XEXP (*note_ptr, 1);
289 else
290 {
291 *note_ptr = XEXP (*note_ptr, 1);
292 free_EXPR_LIST_node (note);
293 }
294 }
295}
296
297// Pick a location for CHANGE's instruction and return the instruction
298// after which it should be placed.
299static insn_info *
300choose_insn_placement (insn_change &change)
301{
302 gcc_checking_assert (change.move_range);
303
304 insn_info *insn = change.insn ();
305 insn_info *first = change.move_range.first;
306 insn_info *last = change.move_range.last;
307
308 // Quick(ish) exit if there is only one possible choice.
309 if (first == last)
310 return first;
311 if (first == insn->prev_nondebug_insn () && last == insn)
312 return insn;
313
314 // For now just use the closest valid choice to the original instruction.
315 // If the register usage has changed significantly, it might instead be
316 // better to try to take register pressure into account.
317 insn_info *closest = change.move_range.clamp_insn_to_range (insn);
318 while (closest != insn && !can_insert_after (insn: closest))
319 closest = closest->next_nondebug_insn ();
320 return closest;
321}
322
323// Record any changes related to CHANGE that need to be queued for later.
324void
325function_info::possibly_queue_changes (insn_change &change)
326{
327 insn_info *insn = change.insn ();
328 rtx_insn *rtl = insn->rtl ();
329
330 // If the instruction could previously throw, we eventually need to call
331 // purge_dead_edges to check whether things have changed.
332 if (find_reg_note (rtl, REG_EH_REGION, nullptr))
333 bitmap_set_bit (m_need_to_purge_dead_edges, insn->bb ()->index ());
334
335 auto needs_pending_update = [&]()
336 {
337 // If an instruction became a no-op without the pass explicitly
338 // deleting it, queue the deletion for later. Removing the
339 // instruction on the fly would require an update to all instructions
340 // that use the result of the move, which would be a potential source
341 // of quadraticness. Also, definitions shouldn't disappear under
342 // the pass's feet.
343 if (INSN_CODE (rtl) == NOOP_MOVE_INSN_CODE)
344 return true;
345
346 // If any jumps got turned into unconditional jumps or nops, we need
347 // to update the CFG accordingly.
348 if (JUMP_P (rtl)
349 && (returnjump_p (rtl) || any_uncondjump_p (rtl))
350 && !single_succ_p (bb: insn->bb ()->cfg_bb ()))
351 return true;
352
353 // If a previously conditional trap now always fires, execution
354 // terminates at that point.
355 rtx pattern = PATTERN (insn: rtl);
356 if (GET_CODE (pattern) == TRAP_IF
357 && XEXP (pattern, 0) == const1_rtx)
358 return true;
359
360 return false;
361 };
362
363 if (needs_pending_update ()
364 && bitmap_set_bit (m_queued_insn_update_uids, insn->uid ()))
365 {
366 gcc_assert (!change.is_deletion ());
367 m_queued_insn_updates.safe_push (obj: insn);
368 }
369}
370
371// Remove the instruction described by CHANGE from the underlying RTL
372// and from the insn_info list.
373static void
374delete_insn (insn_change &change)
375{
376 insn_info *insn = change.insn ();
377 rtx_insn *rtl = change.rtl ();
378 if (dump_file && (dump_flags & TDF_DETAILS))
379 fprintf (stream: dump_file, format: "deleting insn %d\n", insn->uid ());
380 set_insn_deleted (rtl);
381}
382
383// Move the RTL instruction associated with CHANGE so that it comes
384// immediately after AFTER.
385static void
386move_insn (insn_change &change, insn_info *after)
387{
388 rtx_insn *rtl = change.rtl ();
389 rtx_insn *after_rtl = after->rtl ();
390 if (dump_file && (dump_flags & TDF_DETAILS))
391 fprintf (stream: dump_file, format: "moving insn %d after insn %d\n",
392 INSN_UID (insn: rtl), INSN_UID (insn: after_rtl));
393
394 // At the moment we don't support moving instructions between EBBs,
395 // but this would be worth adding if it's useful.
396 insn_info *insn = change.insn ();
397
398 bb_info *bb = after->bb ();
399 basic_block cfg_bb = bb->cfg_bb ();
400
401 if (!insn->is_temporary ())
402 {
403 gcc_assert (after->ebb () == insn->ebb ());
404
405 if (insn->bb () != bb)
406 // Force DF to mark the old block as dirty.
407 df_insn_delete (rtl);
408 ::remove_insn (rtl);
409 }
410
411 ::add_insn_after (rtl, after_rtl, cfg_bb);
412}
413
414// The instruction associated with CHANGE is being changed in-place.
415// Update the DF information for its new pattern.
416static void
417update_insn_in_place (insn_change &change)
418{
419 insn_info *insn = change.insn ();
420 if (dump_file && (dump_flags & TDF_DETAILS))
421 fprintf (stream: dump_file, format: "updating insn %d in-place\n", insn->uid ());
422 df_insn_rescan (change.rtl ());
423}
424
425// Finalize the new list of definitions and uses in CHANGE, removing
426// any uses and definitions that are no longer needed, and converting
427// pending clobbers into actual definitions.
428//
429// POS gives the final position of INSN, which hasn't yet been moved into
430// place. Keep track of any newly-created set_infos being added with this
431// change by adding them to NEW_SETS.
432void
433function_info::finalize_new_accesses (insn_change &change, insn_info *pos,
434 hash_set<def_info *> &new_sets)
435{
436 insn_info *insn = change.insn ();
437
438 // Get a list of all the things that the instruction now references.
439 vec_rtx_properties properties;
440 properties.add_insn (insn: insn->rtl (), include_notes: true);
441
442 // Build up the new list of definitions.
443 for (rtx_obj_reference ref : properties.refs ())
444 if (ref.is_write ())
445 {
446 def_info *def = find_access (accesses: change.new_defs, regno: ref.regno);
447 gcc_assert (def);
448
449 if (def->m_is_temp && is_a<set_info *> (p: def) && def->last_def ())
450 {
451 // For temporary sets being added with this change, we keep track of
452 // the corresponding permanent def using the last_def link.
453 //
454 // So if we have one of these, follow it to get the permanent def.
455 def = def->last_def ();
456 gcc_assert (!def->m_is_temp && !def->m_has_been_superceded);
457 }
458
459 if (def->m_is_temp)
460 {
461 if (is_a<clobber_info *> (p: def))
462 def = allocate<clobber_info> (args: change.insn (), args: ref.regno);
463 else if (is_a<set_info *> (p: def))
464 {
465 // Install the permanent set in the last_def link of the
466 // temporary def. This allows us to find the permanent def
467 // later in case we see a second write to the same resource.
468 def_info *perm_def = allocate<set_info> (args: change.insn (),
469 args: def->resource ());
470
471 // Keep track of the new set so we remember to add it to the
472 // def chain later.
473 if (new_sets.add (k: perm_def))
474 gcc_unreachable (); // We shouldn't see duplicates here.
475
476 def->set_last_def (perm_def);
477 def = perm_def;
478 }
479 else
480 gcc_unreachable ();
481 }
482 else if (!def->m_has_been_superceded)
483 {
484 // This is a second or subsequent definition.
485 // See function_info::record_def for a discussion of when
486 // this can happen.
487 def->record_reference (ref, is_first: false);
488 continue;
489 }
490 else
491 {
492 def->m_has_been_superceded = false;
493
494 // Clobbers can move around, so remove them from their current
495 // position and them back in their final position.
496 //
497 // At the moment, we don't allow sets to move relative to other
498 // definitions of the same resource, so we can leave those where
499 // they are. It might be useful to relax this in future.
500 // The main complication is that removing a set would potentially
501 // fuse two adjoining clobber_groups, and adding the set back
502 // would require the group to be split again.
503 if (is_a<clobber_info *> (p: def))
504 remove_def (def);
505 else if (ref.is_reg ())
506 def->set_mode (ref.mode);
507 def->set_insn (insn);
508 }
509 def->record_reference (ref, is_first: true);
510 m_temp_defs.safe_push (obj: def);
511 }
512
513 // Also keep any explicitly-recorded call clobbers, which are deliberately
514 // excluded from the vec_rtx_properties. Calls shouldn't move, so we can
515 // keep the definitions in their current position.
516 //
517 // If the change describes a set of memory, but the pattern doesn't
518 // reference memory, keep the set anyway. This can happen if the
519 // old pattern was a parallel that contained a memory clobber, and if
520 // the new pattern was recognized without that clobber. Keeping the
521 // set avoids a linear-complexity update to the set's users.
522 //
523 // ??? We could queue an update so that these bogus clobbers are
524 // removed later.
525 for (def_info *def : change.new_defs)
526 if (def->m_has_been_superceded
527 && (def->is_call_clobber () || def->is_mem ()))
528 {
529 def->m_has_been_superceded = false;
530 def->set_insn (insn);
531 m_temp_defs.safe_push (obj: def);
532 }
533
534 // Install the new list of definitions in CHANGE.
535 sort_accesses (container&: m_temp_defs);
536 access_array accesses = temp_access_array (accesses: m_temp_defs);
537 change.new_defs = def_array (accesses);
538 m_temp_defs.truncate (size: 0);
539
540 // Create temporary copies of use_infos that are already attached to
541 // other insns, which could happen if the uses come from unchanging
542 // insns or if they have been used by earlier changes. Doing this
543 // makes it easier to detect multiple reads below.
544 auto *unshared_uses_base = XOBNEWVEC (&m_temp_obstack, access_info *,
545 change.new_uses.size ());
546 unsigned int i = 0;
547 for (use_info *use : change.new_uses)
548 {
549 if (!use->m_has_been_superceded)
550 {
551 use = allocate_temp<use_info> (args: insn, args: use->resource (), args: use->def ());
552 use->m_has_been_superceded = true;
553 use->m_is_temp = true;
554 }
555 unshared_uses_base[i++] = use;
556 }
557 auto unshared_uses = use_array (unshared_uses_base, change.new_uses.size ());
558
559 // Add (possibly temporary) uses to m_temp_uses for each resource.
560 // If there are multiple references to the same resource, aggregate
561 // information in the modes and flags.
562 use_info *mem_use = nullptr;
563 for (rtx_obj_reference ref : properties.refs ())
564 if (ref.is_read ())
565 {
566 unsigned int regno = ref.regno;
567 machine_mode mode = ref.is_reg () ? ref.mode : BLKmode;
568 use_info *use = find_access (accesses: unshared_uses, regno: ref.regno);
569 if (!use)
570 {
571 // For now, we only support inferring uses of mem.
572 gcc_assert (regno == MEM_REGNO);
573
574 if (mem_use)
575 {
576 mem_use->record_reference (ref, is_first: false);
577 continue;
578 }
579
580 resource_info resource { .mode: mode, .regno: regno };
581 auto def = find_def (resource, insn: pos).prev_def (insn: pos);
582 auto set = safe_dyn_cast <set_info *> (p: def);
583 gcc_assert (set);
584 mem_use = allocate<use_info> (args: insn, args: resource, args: set);
585 mem_use->record_reference (ref, is_first: true);
586 m_temp_uses.safe_push (obj: mem_use);
587 continue;
588 }
589
590 if (use->m_has_been_superceded)
591 {
592 // This is the first reference to the resource.
593 bool is_temp = use->m_is_temp;
594 *use = use_info (insn, resource_info { .mode: mode, .regno: regno }, use->def ());
595 use->m_is_temp = is_temp;
596 use->record_reference (ref, is_first: true);
597 m_temp_uses.safe_push (obj: use);
598 }
599 else
600 {
601 // Record the mode of the largest use. The choice is arbitrary if
602 // the instruction (unusually) references the same register in two
603 // different but equal-sized modes.
604 if (HARD_REGISTER_NUM_P (regno)
605 && partial_subreg_p (outermode: use->mode (), innermode: mode))
606 use->set_mode (mode);
607 use->record_reference (ref, is_first: false);
608 }
609 }
610
611 // Replace any temporary uses and definitions with real ones.
612 for (unsigned int i = 0; i < m_temp_uses.length (); ++i)
613 {
614 auto *use = as_a<use_info *> (p: m_temp_uses[i]);
615 if (use->m_is_temp)
616 {
617 m_temp_uses[i] = use = allocate<use_info> (args: *use);
618 use->m_is_temp = false;
619 set_info *def = use->def ();
620 if (!def || !def->m_is_temp)
621 continue;
622
623 if (auto phi = dyn_cast<phi_info *> (p: def))
624 {
625 // Handle cases in which the value was previously not used
626 // within the block.
627 gcc_assert (phi->is_degenerate ());
628 phi = create_degenerate_phi (phi->ebb (), phi->input_value (i: 0));
629 use->set_def (phi);
630 }
631 else
632 {
633 // The temporary def may also be a set added with this change, in
634 // which case the permanent set is stored in the last_def link,
635 // and we need to update the use to refer to the permanent set.
636 gcc_assert (is_a<set_info *> (def));
637 auto perm_set = as_a<set_info *> (p: def->last_def ());
638 gcc_assert (!perm_set->is_temporary ());
639 use->set_def (perm_set);
640 }
641 }
642 }
643
644 // Install the new list of uses in CHANGE.
645 sort_accesses (container&: m_temp_uses);
646 change.new_uses = use_array (temp_access_array (accesses: m_temp_uses));
647 m_temp_uses.truncate (size: 0);
648
649 // Record the new instruction-wide properties.
650 insn->set_properties (properties);
651}
652
653// Copy information from CHANGE to its underlying insn_info, given that
654// the insn_info has already been placed appropriately. NEW_SETS contains the
655// new set_infos that are being added as part of this change (as opposed to
656// being moved or repurposed from existing instructions).
657void
658function_info::apply_changes_to_insn (insn_change &change,
659 hash_set<def_info *> &new_sets)
660{
661 insn_info *insn = change.insn ();
662 if (change.is_deletion ())
663 {
664 insn->set_accesses (accesses: nullptr, num_defs: 0, num_uses: 0);
665 return;
666 }
667
668 // Copy the cost.
669 insn->set_cost (change.new_cost);
670
671 // Add all clobbers and newly-created sets. Existing sets and call
672 // clobbers never move relative to other definitions, so are OK as-is.
673 for (def_info *def : change.new_defs)
674 if ((is_a<clobber_info *> (p: def) && !def->is_call_clobber ())
675 || (is_a<set_info *> (p: def) && new_sets.contains (k: def)))
676 add_def (def);
677
678 // Add all uses, now that their position is final.
679 for (use_info *use : change.new_uses)
680 add_use (use);
681
682 // Copy the uses and definitions.
683 unsigned int num_defs = change.new_defs.size ();
684 unsigned int num_uses = change.new_uses.size ();
685 if (num_defs + num_uses <= insn->num_defs () + insn->num_uses ())
686 insn->copy_accesses (defs: change.new_defs, uses: change.new_uses);
687 else
688 {
689 access_array_builder builder (&m_obstack);
690 builder.reserve (num_accesses: num_defs + num_uses);
691
692 for (def_info *def : change.new_defs)
693 builder.quick_push (access: def);
694 for (use_info *use : change.new_uses)
695 builder.quick_push (access: use);
696
697 insn->set_accesses (accesses: builder.finish ().begin (), num_defs, num_uses);
698 }
699
700 insn->m_is_temp = false;
701}
702
703// Add a temporary placeholder instruction after AFTER.
704insn_info *
705function_info::add_placeholder_after (insn_info *after)
706{
707 insn_info *insn = allocate_temp<insn_info> (args: after->bb (), args: nullptr, args: -1);
708 add_insn_after (insn, after);
709 return insn;
710}
711
712// See the comment above the declaration.
713void
714function_info::change_insns (array_slice<insn_change *> changes)
715{
716 auto watermark = temp_watermark ();
717
718 insn_info *min_insn = m_first_insn;
719 for (insn_change *change : changes)
720 {
721 // Tentatively mark all the old uses and definitions for deletion.
722 for (use_info *use : change->old_uses ())
723 {
724 use->m_has_been_superceded = true;
725 remove_use (use);
726 }
727 for (def_info *def : change->old_defs ())
728 def->m_has_been_superceded = true;
729
730 if (!change->is_deletion ())
731 {
732 // Remove any notes that are no longer relevant.
733 if (!change->insn ()->m_is_temp)
734 update_notes (insn: change->rtl ());
735
736 // Make sure that the placement of this instruction would still
737 // leave room for previous instructions.
738 change->move_range = move_later_than (range: change->move_range, insn: min_insn);
739 if (!canonicalize_move_range (move_range&: change->move_range, insn: change->insn ()))
740 // verify_insn_changes is supposed to make sure that this holds.
741 gcc_unreachable ();
742 min_insn = later_insn (insn1: min_insn, insn2: change->move_range.first);
743
744 if (change->insn ()->m_is_temp)
745 {
746 change->m_insn = allocate<insn_info> (args: change->insn ()->bb (),
747 args: change->rtl (),
748 args: change->insn_uid ());
749
750 // Set the flag again so subsequent logic is aware.
751 // It will be cleared later on.
752 change->m_insn->m_is_temp = true;
753 }
754 }
755 }
756
757 // Walk backwards through the changes, allocating specific positions
758 // to each one. Update the underlying RTL and its associated DF
759 // information.
760 insn_info *following_insn = nullptr;
761 auto_vec<insn_info *, 16> placeholders;
762 placeholders.safe_grow_cleared (len: changes.size ());
763 for (unsigned int i = changes.size (); i-- > 0;)
764 {
765 insn_change &change = *changes[i];
766 insn_info *placeholder = nullptr;
767 possibly_queue_changes (change);
768 if (change.is_deletion ())
769 delete_insn (change);
770 else
771 {
772 // Make sure that this instruction comes before later ones.
773 if (following_insn)
774 {
775 change.move_range = move_earlier_than (range: change.move_range,
776 insn: following_insn);
777 if (!canonicalize_move_range (move_range&: change.move_range,
778 insn: change.insn ()))
779 // verify_insn_changes is supposed to make sure that this
780 // holds.
781 gcc_unreachable ();
782 }
783
784 // Decide which instruction INSN should go after.
785 insn_info *after = choose_insn_placement (change);
786
787 // If INSN is moving, insert a placeholder insn_info at the
788 // new location. We can't move INSN itself yet because it
789 // might still be referenced by earlier move ranges.
790 insn_info *insn = change.insn ();
791 if (after == insn || after == insn->prev_nondebug_insn ())
792 {
793 update_insn_in_place (change);
794 following_insn = insn;
795 }
796 else
797 {
798 move_insn (change, after);
799 placeholder = add_placeholder_after (after);
800 following_insn = placeholder;
801 }
802 }
803 placeholders[i] = placeholder;
804 }
805
806 // We need to keep track of newly-added sets as these need adding to
807 // the def chain later.
808 hash_set<def_info *> new_sets;
809
810 // Finalize the new list of accesses for each change. Don't install them yet,
811 // so that we still have access to the old lists below.
812 //
813 // Note that we do this forwards instead of in the backwards loop above so
814 // that any new defs being inserted are processed before new uses of those
815 // defs, so that the (initially) temporary uses referring to temporary defs
816 // can be easily updated to become permanent uses referring to permanent defs.
817 for (unsigned i = 0; i < changes.size (); i++)
818 {
819 insn_change &change = *changes[i];
820 insn_info *placeholder = placeholders[i];
821 if (!change.is_deletion ())
822 finalize_new_accesses (change,
823 pos: placeholder ? placeholder : change.insn (),
824 new_sets);
825 }
826
827 // Remove all definitions that are no longer needed. After the above,
828 // the only uses of such definitions should be dead phis and now-redundant
829 // live-out uses.
830 //
831 // In particular, this means that consumers must handle debug
832 // instructions before removing a set.
833 for (insn_change *change : changes)
834 for (def_info *def : change->old_defs ())
835 if (def->m_has_been_superceded)
836 {
837 auto *set = dyn_cast<set_info *> (p: def);
838 if (set && set->has_any_uses ())
839 process_uses_of_deleted_def (set);
840 remove_def (def);
841 }
842
843 // Move the insn_infos to their new locations.
844 for (unsigned int i = 0; i < changes.size (); ++i)
845 {
846 insn_change &change = *changes[i];
847 insn_info *insn = change.insn ();
848 if (change.is_deletion ())
849 {
850 if (rtx_insn *rtl = insn->rtl ())
851 ::remove_insn (rtl); // Remove the underlying RTL insn.
852 remove_insn (insn);
853 }
854 else if (insn_info *placeholder = placeholders[i])
855 {
856 // Check if earlier movements turned a move into a no-op.
857 if (placeholder->prev_nondebug_insn () == insn
858 || placeholder->next_nondebug_insn () == insn)
859 {
860 remove_insn (placeholder);
861 placeholders[i] = nullptr;
862 }
863 else
864 {
865 // Remove the placeholder first so that we have a wider range of
866 // program points when inserting INSN.
867 insn_info *after = placeholder->prev_any_insn ();
868 if (!insn->is_temporary ())
869 remove_insn (insn);
870 remove_insn (placeholder);
871 insn->set_bb (after->bb ());
872 add_insn_after (insn, after);
873 }
874 }
875 }
876
877 // Apply the changes to the underlying insn_infos.
878 for (insn_change *change : changes)
879 apply_changes_to_insn (change&: *change, new_sets);
880
881 // Now that the insns and accesses are up to date, add any REG_UNUSED notes.
882 for (insn_change *change : changes)
883 if (!change->is_deletion ())
884 add_reg_unused_notes (change->insn ());
885}
886
887// See the comment above the declaration.
888void
889function_info::change_insn (insn_change &change)
890{
891 insn_change *changes[] = { &change };
892 return change_insns (changes);
893}
894
895// Try to adjust CHANGE so that its pattern can include clobber rtx CLOBBER.
896// Return true on success.
897//
898// ADD_REGNO_CLOBBER is a specialization of function_info::add_regno_clobber
899// for a specific caller-provided predicate.
900static bool
901add_clobber (insn_change &change, add_regno_clobber_fn add_regno_clobber,
902 rtx clobber)
903{
904 rtx pat = PATTERN (insn: change.rtl ());
905 gcc_assert (GET_CODE (clobber) == CLOBBER);
906 rtx dest = XEXP (clobber, 0);
907 if (GET_CODE (dest) == SCRATCH)
908 {
909 if (reload_completed)
910 {
911 if (dump_file && (dump_flags & TDF_DETAILS))
912 {
913 // ??? Maybe we could try to do some RA here?
914 fprintf (stream: dump_file, format: "instruction requires a scratch"
915 " after reload:\n");
916 print_rtl_single (dump_file, pat);
917 }
918 return false;
919 }
920 return true;
921 }
922
923 gcc_assert (REG_P (dest));
924 for (unsigned int regno = REGNO (dest); regno != END_REGNO (x: dest); ++regno)
925 if (!add_regno_clobber (change, regno))
926 {
927 if (dump_file && (dump_flags & TDF_DETAILS))
928 {
929 fprintf (stream: dump_file, format: "cannot clobber live register %d in:\n",
930 regno);
931 print_rtl_single (dump_file, pat);
932 }
933 return false;
934 }
935 return true;
936}
937
938// Try to recognize the new form of the insn associated with CHANGE,
939// adding any clobbers that are necessary to make the instruction match
940// an .md pattern. Return true on success.
941//
942// ADD_REGNO_CLOBBER is a specialization of function_info::add_regno_clobber
943// for a specific caller-provided predicate.
944static bool
945recog_level2 (insn_change &change, add_regno_clobber_fn add_regno_clobber)
946{
947 insn_change_watermark insn_watermark;
948 rtx_insn *rtl = change.rtl ();
949 rtx pat = PATTERN (insn: rtl);
950 int num_clobbers = 0;
951 int icode = -1;
952 bool asm_p = asm_noperands (pat) >= 0;
953 if (asm_p)
954 {
955 if (!check_asm_operands (pat))
956 {
957 if (dump_file && (dump_flags & TDF_DETAILS))
958 {
959 fprintf (stream: dump_file, format: "failed to match this asm instruction:\n");
960 print_rtl_single (dump_file, pat);
961 }
962 return false;
963 }
964 }
965 else if (noop_move_p (rtl))
966 {
967 INSN_CODE (rtl) = NOOP_MOVE_INSN_CODE;
968 if (dump_file && (dump_flags & TDF_DETAILS))
969 {
970 fprintf (stream: dump_file, format: "instruction becomes a no-op:\n");
971 print_rtl_single (dump_file, pat);
972 }
973 insn_watermark.keep ();
974 return true;
975 }
976 else
977 {
978 icode = ::recog (pat, rtl, &num_clobbers);
979 if (icode < 0)
980 {
981 if (dump_file && (dump_flags & TDF_DETAILS))
982 {
983 fprintf (stream: dump_file, format: "failed to match this instruction:\n");
984 print_rtl_single (dump_file, pat);
985 }
986 return false;
987 }
988 }
989
990 auto prev_new_defs = change.new_defs;
991 auto prev_move_range = change.move_range;
992 if (num_clobbers > 0)
993 {
994 // ??? It would be good to have a way of recycling the rtxes on failure,
995 // but any attempt to cache old PARALLELs would at best be a half
996 // measure, since add_clobbers would still generate fresh clobbers
997 // each time. It would be better to have a more general recycling
998 // mechanism that all rtx passes can use.
999 rtvec newvec;
1000 int oldlen;
1001 if (GET_CODE (pat) == PARALLEL)
1002 {
1003 oldlen = XVECLEN (pat, 0);
1004 newvec = rtvec_alloc (num_clobbers + oldlen);
1005 for (int i = 0; i < oldlen; ++i)
1006 RTVEC_ELT (newvec, i) = XVECEXP (pat, 0, i);
1007 }
1008 else
1009 {
1010 oldlen = 1;
1011 newvec = rtvec_alloc (num_clobbers + oldlen);
1012 RTVEC_ELT (newvec, 0) = pat;
1013 }
1014 rtx newpat = gen_rtx_PARALLEL (VOIDmode, newvec);
1015 add_clobbers (newpat, icode);
1016 validate_change (rtl, &PATTERN (insn: rtl), newpat, true);
1017 for (int i = 0; i < num_clobbers; ++i)
1018 if (!add_clobber (change, add_regno_clobber,
1019 XVECEXP (newpat, 0, oldlen + i)))
1020 {
1021 change.new_defs = prev_new_defs;
1022 change.move_range = prev_move_range;
1023 return false;
1024 }
1025
1026 pat = newpat;
1027 }
1028
1029 // check_asm_operands checks the constraints after RA, so we don't
1030 // need to do it again.
1031 INSN_CODE (rtl) = icode;
1032 if (reload_completed && !asm_p)
1033 {
1034 extract_insn (rtl);
1035 if (!constrain_operands (1, get_preferred_alternatives (rtl)))
1036 {
1037 if (dump_file && (dump_flags & TDF_DETAILS))
1038 {
1039 if (asm_p)
1040 fprintf (stream: dump_file, format: "asm does not match its constraints:\n");
1041 else if (const char *name = get_insn_name (icode))
1042 fprintf (stream: dump_file, format: "instruction does not match the"
1043 " constraints for %s:\n", name);
1044 else
1045 fprintf (stream: dump_file, format: "instruction does not match its"
1046 " constraints:\n");
1047 print_rtl_single (dump_file, pat);
1048 }
1049 change.new_defs = prev_new_defs;
1050 change.move_range = prev_move_range;
1051 return false;
1052 }
1053 }
1054
1055 if (dump_file && (dump_flags & TDF_DETAILS))
1056 {
1057 const char *name;
1058 if (!asm_p && (name = get_insn_name (icode)))
1059 fprintf (stream: dump_file, format: "successfully matched this instruction "
1060 "to %s:\n", name);
1061 else
1062 fprintf (stream: dump_file, format: "successfully matched this instruction:\n");
1063 print_rtl_single (dump_file, pat);
1064 }
1065
1066 insn_watermark.keep ();
1067 return true;
1068}
1069
1070// Try to recognize the new form of the insn associated with CHANGE,
1071// adding and removing clobbers as necessary to make the instruction
1072// match an .md pattern. Return true on success, otherwise leave
1073// CHANGE as it was on entry.
1074//
1075// ADD_REGNO_CLOBBER is a specialization of function_info::add_regno_clobber
1076// for a specific caller-provided predicate.
1077bool
1078rtl_ssa::recog_internal (insn_change &change,
1079 add_regno_clobber_fn add_regno_clobber)
1080{
1081 // Accept all changes to debug instructions.
1082 insn_info *insn = change.insn ();
1083 if (insn->is_debug_insn ())
1084 return true;
1085
1086 rtx_insn *rtl = insn->rtl ();
1087 rtx pat = PATTERN (insn: rtl);
1088 if (GET_CODE (pat) == PARALLEL && asm_noperands (pat) < 0)
1089 {
1090 // Try to remove trailing (clobber (scratch)) rtxes, since the new form
1091 // of the instruction might not need those scratches. recog will add
1092 // back any that are needed.
1093 int len = XVECLEN (pat, 0);
1094 int new_len = len;
1095 while (new_len > 0
1096 && GET_CODE (XVECEXP (pat, 0, new_len - 1)) == CLOBBER
1097 && GET_CODE (XEXP (XVECEXP (pat, 0, new_len - 1), 0)) == SCRATCH)
1098 new_len -= 1;
1099
1100 int old_num_changes = num_validated_changes ();
1101 validate_change_xveclen (rtl, &PATTERN (insn: rtl), new_len, true);
1102 if (recog_level2 (change, add_regno_clobber))
1103 return true;
1104 cancel_changes (old_num_changes);
1105
1106 // Try to remove all trailing clobbers. For example, a pattern that
1107 // used to clobber the flags might no longer need to do so.
1108 int prev_len = new_len;
1109 while (new_len > 0
1110 && GET_CODE (XVECEXP (pat, 0, new_len - 1)) == CLOBBER)
1111 new_len -= 1;
1112 if (new_len != prev_len)
1113 {
1114 validate_change_xveclen (rtl, &PATTERN (insn: rtl), new_len, true);
1115 if (recog_level2 (change, add_regno_clobber))
1116 return true;
1117 cancel_changes (old_num_changes);
1118 }
1119 return false;
1120 }
1121
1122 return recog_level2 (change, add_regno_clobber);
1123}
1124
1125// See the comment above the declaration.
1126bool
1127function_info::perform_pending_updates ()
1128{
1129 bool changed_cfg = false;
1130 bool changed_jumps = false;
1131 for (insn_info *insn : m_queued_insn_updates)
1132 {
1133 rtx_insn *rtl = insn->rtl ();
1134 if (NOTE_P (rtl))
1135 // The insn was later optimized away, typically to a NOTE_INSN_DELETED.
1136 ;
1137 else if (JUMP_P (rtl))
1138 {
1139 if (INSN_CODE (rtl) == NOOP_MOVE_INSN_CODE)
1140 {
1141 ::delete_insn (rtl);
1142 bitmap_set_bit (m_need_to_purge_dead_edges,
1143 insn->bb ()->index ());
1144 }
1145 else if (returnjump_p (rtl) || any_uncondjump_p (rtl))
1146 {
1147 mark_jump_label (PATTERN (insn: rtl), rtl, 0);
1148 update_cfg_for_uncondjump (rtl);
1149 changed_cfg = true;
1150 changed_jumps = true;
1151 }
1152 }
1153 else if (INSN_CODE (rtl) == NOOP_MOVE_INSN_CODE)
1154 ::delete_insn (rtl);
1155 else
1156 {
1157 rtx pattern = PATTERN (insn: rtl);
1158 if (GET_CODE (pattern) == TRAP_IF
1159 && XEXP (pattern, 0) == const1_rtx)
1160 {
1161 remove_edge (split_block (BLOCK_FOR_INSN (insn: rtl), rtl));
1162 emit_barrier_after_bb (bb: BLOCK_FOR_INSN (insn: rtl));
1163 changed_cfg = true;
1164 }
1165 }
1166 }
1167
1168 unsigned int index;
1169 bitmap_iterator bi;
1170 EXECUTE_IF_SET_IN_BITMAP (m_need_to_purge_dead_edges, 0, index, bi)
1171 if (purge_dead_edges (BASIC_BLOCK_FOR_FN (m_fn, index)))
1172 changed_cfg = true;
1173
1174 if (changed_jumps)
1175 // This uses its own timevar internally, so we don't need to push
1176 // one ourselves.
1177 rebuild_jump_labels (get_insns ());
1178
1179 bitmap_clear (m_need_to_purge_dead_edges);
1180 bitmap_clear (m_queued_insn_update_uids);
1181 m_queued_insn_updates.truncate (size: 0);
1182
1183 if (changed_cfg)
1184 {
1185 free_dominance_info (CDI_DOMINATORS);
1186 free_dominance_info (CDI_POST_DOMINATORS);
1187 }
1188
1189 return changed_cfg;
1190}
1191
1192insn_info *
1193function_info::create_insn (obstack_watermark &watermark,
1194 rtx_code insn_code,
1195 rtx pat)
1196{
1197 rtx_insn *rti = nullptr;
1198
1199 // TODO: extend, move in to emit-rtl.cc.
1200 switch (insn_code)
1201 {
1202 case INSN:
1203 rti = make_insn_raw (pat);
1204 break;
1205 default:
1206 gcc_unreachable ();
1207 }
1208
1209 auto insn = change_alloc<insn_info> (wm&: watermark, args: nullptr, args: rti, args: INSN_UID (insn: rti));
1210 insn->m_is_temp = true;
1211 return insn;
1212}
1213
1214// Print a description of CHANGE to PP.
1215void
1216rtl_ssa::pp_insn_change (pretty_printer *pp, const insn_change &change)
1217{
1218 change.print (pp);
1219}
1220
1221// Print a description of CHANGE to FILE.
1222void
1223dump (FILE *file, const insn_change &change)
1224{
1225 dump_using (file, printer: pp_insn_change, args: change);
1226}
1227
1228// Debug interface to the dump routine above.
1229void debug (const insn_change &x) { dump (stderr, change: x); }
1230

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