1 /* Copy propagation on hard registers for the GNU compiler.
2 Copyright (C) 2000-2023 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 3, or (at your option)
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
13 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
14 License for more details.
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/>. */
22 #include "coretypes.h"
28 #include "insn-config.h"
32 #include "diagnostic-core.h"
33 #include "addresses.h"
34 #include "tree-pass.h"
38 #include "function-abi.h"
40 /* The following code does forward propagation of hard register copies.
41 The object is to eliminate as many dependencies as possible, so that
42 we have the most scheduling freedom. As a side effect, we also clean
43 up some silly register allocation decisions made by reload. This
44 code may be obsoleted by a new register allocator. */
46 /* DEBUG_INSNs aren't changed right away, as doing so might extend the
47 lifetime of a register and get the DEBUG_INSN subsequently reset.
48 So they are queued instead, and updated only when the register is
49 used in some subsequent real insn before it is set. */
50 struct queued_debug_insn_change
52 struct queued_debug_insn_change
*next
;
58 /* For each register, we have a list of registers that contain the same
59 value. The OLDEST_REGNO field points to the head of the list, and
60 the NEXT_REGNO field runs through the list. The MODE field indicates
61 what mode the data is known to be in; this field is VOIDmode when the
62 register is not known to contain valid data. */
64 struct value_data_entry
67 unsigned int oldest_regno
;
68 unsigned int next_regno
;
69 struct queued_debug_insn_change
*debug_insn_changes
;
74 struct value_data_entry e
[FIRST_PSEUDO_REGISTER
];
75 unsigned int max_value_regs
;
76 unsigned int n_debug_insn_changes
;
79 static object_allocator
<queued_debug_insn_change
> queued_debug_insn_change_pool
80 ("debug insn changes pool");
82 static bool skip_debug_insn_p
;
84 static void kill_value_one_regno (unsigned, struct value_data
*);
85 static void kill_value_regno (unsigned, unsigned, struct value_data
*);
86 static void kill_value (const_rtx
, struct value_data
*);
87 static void set_value_regno (unsigned, machine_mode
, struct value_data
*);
88 static void init_value_data (struct value_data
*);
89 static void kill_clobbered_value (rtx
, const_rtx
, void *);
90 static void kill_set_value (rtx
, const_rtx
, void *);
91 static void copy_value (rtx
, rtx
, struct value_data
*);
92 static bool mode_change_ok (machine_mode
, machine_mode
,
94 static rtx
maybe_mode_change (machine_mode
, machine_mode
,
95 machine_mode
, unsigned int, unsigned int);
96 static rtx
find_oldest_value_reg (enum reg_class
, rtx
, struct value_data
*);
97 static bool replace_oldest_value_reg (rtx
*, enum reg_class
, rtx_insn
*,
99 static bool replace_oldest_value_addr (rtx
*, enum reg_class
,
100 machine_mode
, addr_space_t
,
101 rtx_insn
*, struct value_data
*);
102 static bool replace_oldest_value_mem (rtx
, rtx_insn
*, struct value_data
*);
103 static bool copyprop_hardreg_forward_1 (basic_block
, struct value_data
*);
104 extern void debug_value_data (struct value_data
*);
105 static void validate_value_data (struct value_data
*);
107 /* Free all queued updates for DEBUG_INSNs that change some reg to
111 free_debug_insn_changes (struct value_data
*vd
, unsigned int regno
)
113 struct queued_debug_insn_change
*cur
, *next
;
114 for (cur
= vd
->e
[regno
].debug_insn_changes
; cur
; cur
= next
)
117 --vd
->n_debug_insn_changes
;
118 queued_debug_insn_change_pool
.remove (cur
);
120 vd
->e
[regno
].debug_insn_changes
= NULL
;
123 /* Kill register REGNO. This involves removing it from any value
124 lists, and resetting the value mode to VOIDmode. This is only a
125 helper function; it does not handle any hard registers overlapping
129 kill_value_one_regno (unsigned int regno
, struct value_data
*vd
)
131 unsigned int i
, next
;
133 if (vd
->e
[regno
].oldest_regno
!= regno
)
135 for (i
= vd
->e
[regno
].oldest_regno
;
136 vd
->e
[i
].next_regno
!= regno
;
137 i
= vd
->e
[i
].next_regno
)
139 vd
->e
[i
].next_regno
= vd
->e
[regno
].next_regno
;
141 else if ((next
= vd
->e
[regno
].next_regno
) != INVALID_REGNUM
)
143 for (i
= next
; i
!= INVALID_REGNUM
; i
= vd
->e
[i
].next_regno
)
144 vd
->e
[i
].oldest_regno
= next
;
147 vd
->e
[regno
].mode
= VOIDmode
;
148 vd
->e
[regno
].oldest_regno
= regno
;
149 vd
->e
[regno
].next_regno
= INVALID_REGNUM
;
150 if (vd
->e
[regno
].debug_insn_changes
)
151 free_debug_insn_changes (vd
, regno
);
154 validate_value_data (vd
);
157 /* Kill the value in register REGNO for NREGS, and any other registers
158 whose values overlap. */
161 kill_value_regno (unsigned int regno
, unsigned int nregs
,
162 struct value_data
*vd
)
166 /* Kill the value we're told to kill. */
167 for (j
= 0; j
< nregs
; ++j
)
168 kill_value_one_regno (regno
+ j
, vd
);
170 /* Kill everything that overlapped what we're told to kill. */
171 if (regno
< vd
->max_value_regs
)
174 j
= regno
- vd
->max_value_regs
;
175 for (; j
< regno
; ++j
)
178 if (vd
->e
[j
].mode
== VOIDmode
)
180 n
= hard_regno_nregs (j
, vd
->e
[j
].mode
);
182 for (i
= 0; i
< n
; ++i
)
183 kill_value_one_regno (j
+ i
, vd
);
187 /* Kill X. This is a convenience function wrapping kill_value_regno
188 so that we mind the mode the register is in. */
191 kill_value (const_rtx x
, struct value_data
*vd
)
193 if (GET_CODE (x
) == SUBREG
)
195 rtx tmp
= simplify_subreg (GET_MODE (x
), SUBREG_REG (x
),
196 GET_MODE (SUBREG_REG (x
)), SUBREG_BYTE (x
));
197 x
= tmp
? tmp
: SUBREG_REG (x
);
200 kill_value_regno (REGNO (x
), REG_NREGS (x
), vd
);
203 /* Remember that REGNO is valid in MODE. */
206 set_value_regno (unsigned int regno
, machine_mode mode
,
207 struct value_data
*vd
)
211 vd
->e
[regno
].mode
= mode
;
213 nregs
= hard_regno_nregs (regno
, mode
);
214 if (nregs
> vd
->max_value_regs
)
215 vd
->max_value_regs
= nregs
;
218 /* Initialize VD such that there are no known relationships between regs. */
221 init_value_data (struct value_data
*vd
)
224 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
226 vd
->e
[i
].mode
= VOIDmode
;
227 vd
->e
[i
].oldest_regno
= i
;
228 vd
->e
[i
].next_regno
= INVALID_REGNUM
;
229 vd
->e
[i
].debug_insn_changes
= NULL
;
231 vd
->max_value_regs
= 0;
232 vd
->n_debug_insn_changes
= 0;
235 /* Called through note_stores. If X is clobbered, kill its value. */
238 kill_clobbered_value (rtx x
, const_rtx set
, void *data
)
240 struct value_data
*const vd
= (struct value_data
*) data
;
242 if (GET_CODE (set
) == CLOBBER
)
246 /* A structure passed as data to kill_set_value through note_stores. */
247 struct kill_set_value_data
249 struct value_data
*vd
;
253 /* Called through note_stores. If X is set, not clobbered, kill its
254 current value and install it as the root of its own value list. */
257 kill_set_value (rtx x
, const_rtx set
, void *data
)
259 struct kill_set_value_data
*ksvd
= (struct kill_set_value_data
*) data
;
260 if (rtx_equal_p (x
, ksvd
->ignore_set_reg
))
263 if (GET_CODE (set
) != CLOBBER
)
265 kill_value (x
, ksvd
->vd
);
267 set_value_regno (REGNO (x
), GET_MODE (x
), ksvd
->vd
);
271 /* Kill any register used in X as the base of an auto-increment expression,
272 and install that register as the root of its own value list. */
275 kill_autoinc_value (rtx_insn
*insn
, struct value_data
*vd
)
277 subrtx_iterator::array_type array
;
278 FOR_EACH_SUBRTX (iter
, array
, PATTERN (insn
), NONCONST
)
281 if (GET_RTX_CLASS (GET_CODE (x
)) == RTX_AUTOINC
)
285 set_value_regno (REGNO (x
), GET_MODE (x
), vd
);
286 iter
.skip_subrtxes ();
291 /* Assert that SRC has been copied to DEST. Adjust the data structures
292 to reflect that SRC contains an older copy of the shared value. */
295 copy_value (rtx dest
, rtx src
, struct value_data
*vd
)
297 unsigned int dr
= REGNO (dest
);
298 unsigned int sr
= REGNO (src
);
302 /* ??? At present, it's possible to see noop sets. It'd be nice if
303 this were cleaned up beforehand... */
307 /* Do not propagate copies to the stack pointer, as that can leave
308 memory accesses with no scheduling dependency on the stack update. */
309 if (dr
== STACK_POINTER_REGNUM
)
312 /* Likewise with the frame pointer, if we're using one. */
313 if (frame_pointer_needed
&& dr
== HARD_FRAME_POINTER_REGNUM
)
316 /* Do not propagate copies to fixed or global registers, patterns
317 can be relying to see particular fixed register or users can
318 expect the chosen global register in asm. */
319 if (fixed_regs
[dr
] || global_regs
[dr
])
322 /* If SRC and DEST overlap, don't record anything. */
323 dn
= REG_NREGS (dest
);
324 sn
= REG_NREGS (src
);
325 if ((dr
> sr
&& dr
< sr
+ sn
)
326 || (sr
> dr
&& sr
< dr
+ dn
))
329 /* If SRC had no assigned mode (i.e. we didn't know it was live)
330 assign it now and assume the value came from an input argument
332 if (vd
->e
[sr
].mode
== VOIDmode
)
333 set_value_regno (sr
, vd
->e
[dr
].mode
, vd
);
335 /* If we are narrowing the input to a smaller number of hard regs,
336 and it is in big endian, we are really extracting a high part.
337 Since we generally associate a low part of a value with the value itself,
338 we must not do the same for the high part.
339 Note we can still get low parts for the same mode combination through
340 a two-step copy involving differently sized hard regs.
341 Assume hard regs fr* are 32 bits each, while r* are 64 bits each:
342 (set (reg:DI r0) (reg:DI fr0))
343 (set (reg:SI fr2) (reg:SI r0))
344 loads the low part of (reg:DI fr0) - i.e. fr1 - into fr2, while:
345 (set (reg:SI fr2) (reg:SI fr0))
346 loads the high part of (reg:DI fr0) into fr2.
348 We can't properly represent the latter case in our tables, so don't
349 record anything then. */
350 else if (sn
< hard_regno_nregs (sr
, vd
->e
[sr
].mode
)
351 && maybe_ne (subreg_lowpart_offset (GET_MODE (dest
),
352 vd
->e
[sr
].mode
), 0U))
355 /* If SRC had been assigned a mode narrower than the copy, we can't
356 link DEST into the chain, because not all of the pieces of the
357 copy came from oldest_regno. */
358 else if (sn
> hard_regno_nregs (sr
, vd
->e
[sr
].mode
))
361 /* If a narrower value is copied using wider mode, the upper bits
362 are undefined (could be e.g. a former paradoxical subreg). Signal
363 in that case we've only copied value using the narrower mode.
365 (set (reg:DI r14) (mem:DI ...))
366 (set (reg:QI si) (reg:QI r14))
367 (set (reg:DI bp) (reg:DI r14))
368 (set (reg:DI r14) (const_int ...))
369 (set (reg:DI dx) (reg:DI si))
370 (set (reg:DI si) (const_int ...))
371 (set (reg:DI dx) (reg:DI bp))
372 The last set is not redundant, while the low 8 bits of dx are already
373 equal to low 8 bits of bp, the other bits are undefined. */
374 else if (partial_subreg_p (vd
->e
[sr
].mode
, GET_MODE (src
)))
376 if (!REG_CAN_CHANGE_MODE_P (sr
, GET_MODE (src
), vd
->e
[sr
].mode
)
377 || !REG_CAN_CHANGE_MODE_P (dr
, vd
->e
[sr
].mode
, GET_MODE (dest
)))
379 set_value_regno (dr
, vd
->e
[sr
].mode
, vd
);
382 /* Link DR at the end of the value chain used by SR. */
384 vd
->e
[dr
].oldest_regno
= vd
->e
[sr
].oldest_regno
;
386 for (i
= sr
; vd
->e
[i
].next_regno
!= INVALID_REGNUM
; i
= vd
->e
[i
].next_regno
)
388 vd
->e
[i
].next_regno
= dr
;
391 validate_value_data (vd
);
394 /* Return true if a mode change from ORIG to NEW is allowed for REGNO. */
397 mode_change_ok (machine_mode orig_mode
, machine_mode new_mode
,
398 unsigned int regno ATTRIBUTE_UNUSED
)
400 if (partial_subreg_p (orig_mode
, new_mode
))
403 return REG_CAN_CHANGE_MODE_P (regno
, orig_mode
, new_mode
);
406 /* Register REGNO was originally set in ORIG_MODE. It - or a copy of it -
407 was copied in COPY_MODE to COPY_REGNO, and then COPY_REGNO was accessed
409 Return a NEW_MODE rtx for REGNO if that's OK, otherwise return NULL_RTX. */
412 maybe_mode_change (machine_mode orig_mode
, machine_mode copy_mode
,
413 machine_mode new_mode
, unsigned int regno
,
414 unsigned int copy_regno ATTRIBUTE_UNUSED
)
416 if (partial_subreg_p (copy_mode
, orig_mode
)
417 && partial_subreg_p (copy_mode
, new_mode
))
420 /* Avoid creating multiple copies of the stack pointer. Some ports
421 assume there is one and only one stack pointer.
423 It's unclear if we need to do the same for other special registers. */
424 if (regno
== STACK_POINTER_REGNUM
)
426 if (orig_mode
== new_mode
&& new_mode
== GET_MODE (stack_pointer_rtx
))
427 return stack_pointer_rtx
;
432 if (orig_mode
== new_mode
)
433 return gen_raw_REG (new_mode
, regno
);
434 else if (mode_change_ok (orig_mode
, new_mode
, regno
)
435 && mode_change_ok (copy_mode
, new_mode
, copy_regno
))
437 int copy_nregs
= hard_regno_nregs (copy_regno
, copy_mode
);
438 int use_nregs
= hard_regno_nregs (copy_regno
, new_mode
);
439 poly_uint64 bytes_per_reg
;
440 if (!can_div_trunc_p (GET_MODE_SIZE (copy_mode
),
441 copy_nregs
, &bytes_per_reg
))
443 poly_uint64 copy_offset
= bytes_per_reg
* (copy_nregs
- use_nregs
);
445 = subreg_size_lowpart_offset (GET_MODE_SIZE (new_mode
) + copy_offset
,
446 GET_MODE_SIZE (orig_mode
));
447 regno
+= subreg_regno_offset (regno
, orig_mode
, offset
, new_mode
);
448 if (targetm
.hard_regno_mode_ok (regno
, new_mode
))
449 return gen_raw_REG (new_mode
, regno
);
454 /* Helper function to copy attributes when replacing OLD_REG with NEW_REG.
455 If the changes required for NEW_REG are invalid return NULL_RTX, otherwise
456 return NEW_REG. This is intended to be used with maybe_mode_change. */
459 maybe_copy_reg_attrs (rtx new_reg
, rtx old_reg
)
461 if (new_reg
!= stack_pointer_rtx
)
463 /* NEW_REG is assumed to be a register copy resulting from
464 maybe_mode_change. */
465 ORIGINAL_REGNO (new_reg
) = ORIGINAL_REGNO (old_reg
);
466 REG_ATTRS (new_reg
) = REG_ATTRS (old_reg
);
467 REG_POINTER (new_reg
) = REG_POINTER (old_reg
);
469 else if (REG_POINTER (new_reg
) != REG_POINTER (old_reg
))
471 /* Only a single instance of STACK_POINTER_RTX must exist and we cannot
472 modify it. Allow propagation if REG_POINTER for OLD_REG matches and
473 don't touch ORIGINAL_REGNO and REG_ATTRS. */
479 /* Find the oldest copy of the value contained in REGNO that is in
480 register class CL and has mode MODE. If found, return an rtx
481 of that oldest register, otherwise return NULL. */
484 find_oldest_value_reg (enum reg_class cl
, rtx reg
, struct value_data
*vd
)
486 unsigned int regno
= REGNO (reg
);
487 machine_mode mode
= GET_MODE (reg
);
490 gcc_assert (regno
< FIRST_PSEUDO_REGISTER
);
492 /* If we are accessing REG in some mode other that what we set it in,
493 make sure that the replacement is valid. In particular, consider
494 (set (reg:DI r11) (...))
495 (set (reg:SI r9) (reg:SI r11))
496 (set (reg:SI r10) (...))
497 (set (...) (reg:DI r9))
498 Replacing r9 with r11 is invalid. */
499 if (mode
!= vd
->e
[regno
].mode
500 && (REG_NREGS (reg
) > hard_regno_nregs (regno
, vd
->e
[regno
].mode
)
501 || !REG_CAN_CHANGE_MODE_P (regno
, mode
, vd
->e
[regno
].mode
)))
504 for (i
= vd
->e
[regno
].oldest_regno
; i
!= regno
; i
= vd
->e
[i
].next_regno
)
506 machine_mode oldmode
= vd
->e
[i
].mode
;
509 if (!in_hard_reg_set_p (reg_class_contents
[cl
], mode
, i
))
512 new_rtx
= maybe_mode_change (oldmode
, vd
->e
[regno
].mode
, mode
, i
, regno
);
514 return maybe_copy_reg_attrs (new_rtx
, reg
);
520 /* If possible, replace the register at *LOC with the oldest register
521 in register class CL. Return true if successfully replaced. */
524 replace_oldest_value_reg (rtx
*loc
, enum reg_class cl
, rtx_insn
*insn
,
525 struct value_data
*vd
)
527 rtx new_rtx
= find_oldest_value_reg (cl
, *loc
, vd
);
528 if (new_rtx
&& (!DEBUG_INSN_P (insn
) || !skip_debug_insn_p
))
530 if (DEBUG_INSN_P (insn
))
532 struct queued_debug_insn_change
*change
;
535 fprintf (dump_file
, "debug_insn %u: queued replacing reg %u with %u\n",
536 INSN_UID (insn
), REGNO (*loc
), REGNO (new_rtx
));
538 change
= queued_debug_insn_change_pool
.allocate ();
539 change
->next
= vd
->e
[REGNO (new_rtx
)].debug_insn_changes
;
542 change
->new_rtx
= new_rtx
;
543 vd
->e
[REGNO (new_rtx
)].debug_insn_changes
= change
;
544 ++vd
->n_debug_insn_changes
;
548 fprintf (dump_file
, "insn %u: replaced reg %u with %u\n",
549 INSN_UID (insn
), REGNO (*loc
), REGNO (new_rtx
));
551 validate_change (insn
, loc
, new_rtx
, 1);
557 /* Similar to replace_oldest_value_reg, but *LOC contains an address.
558 Adapted from find_reloads_address_1. CL is INDEX_REG_CLASS or
559 BASE_REG_CLASS depending on how the register is being considered. */
562 replace_oldest_value_addr (rtx
*loc
, enum reg_class cl
,
563 machine_mode mode
, addr_space_t as
,
564 rtx_insn
*insn
, struct value_data
*vd
)
567 RTX_CODE code
= GET_CODE (x
);
570 bool changed
= false;
575 if (DEBUG_INSN_P (insn
))
579 rtx orig_op0
= XEXP (x
, 0);
580 rtx orig_op1
= XEXP (x
, 1);
581 RTX_CODE code0
= GET_CODE (orig_op0
);
582 RTX_CODE code1
= GET_CODE (orig_op1
);
587 enum rtx_code index_code
= SCRATCH
;
589 if (GET_CODE (op0
) == SUBREG
)
591 op0
= SUBREG_REG (op0
);
592 code0
= GET_CODE (op0
);
595 if (GET_CODE (op1
) == SUBREG
)
597 op1
= SUBREG_REG (op1
);
598 code1
= GET_CODE (op1
);
601 if (code0
== MULT
|| code0
== SIGN_EXTEND
|| code0
== TRUNCATE
602 || code0
== ZERO_EXTEND
|| code1
== MEM
)
606 index_code
= GET_CODE (*locI
);
608 else if (code1
== MULT
|| code1
== SIGN_EXTEND
|| code1
== TRUNCATE
609 || code1
== ZERO_EXTEND
|| code0
== MEM
)
613 index_code
= GET_CODE (*locI
);
615 else if (code0
== CONST_INT
|| code0
== CONST
616 || code0
== SYMBOL_REF
|| code0
== LABEL_REF
)
619 index_code
= GET_CODE (XEXP (x
, 0));
621 else if (code1
== CONST_INT
|| code1
== CONST
622 || code1
== SYMBOL_REF
|| code1
== LABEL_REF
)
625 index_code
= GET_CODE (XEXP (x
, 1));
627 else if (code0
== REG
&& code1
== REG
)
630 unsigned regno0
= REGNO (op0
), regno1
= REGNO (op1
);
632 if (REGNO_OK_FOR_INDEX_P (regno1
)
633 && regno_ok_for_base_p (regno0
, mode
, as
, PLUS
, REG
))
635 else if (REGNO_OK_FOR_INDEX_P (regno0
)
636 && regno_ok_for_base_p (regno1
, mode
, as
, PLUS
, REG
))
638 else if (regno_ok_for_base_p (regno0
, mode
, as
, PLUS
, REG
)
639 || REGNO_OK_FOR_INDEX_P (regno1
))
641 else if (regno_ok_for_base_p (regno1
, mode
, as
, PLUS
, REG
))
646 locI
= &XEXP (x
, index_op
);
647 locB
= &XEXP (x
, !index_op
);
648 index_code
= GET_CODE (*locI
);
650 else if (code0
== REG
)
654 index_code
= GET_CODE (*locI
);
656 else if (code1
== REG
)
660 index_code
= GET_CODE (*locI
);
664 changed
|= replace_oldest_value_addr (locI
, INDEX_REG_CLASS
,
667 changed
|= replace_oldest_value_addr (locB
,
668 base_reg_class (mode
, as
, PLUS
,
683 return replace_oldest_value_mem (x
, insn
, vd
);
686 return replace_oldest_value_reg (loc
, cl
, insn
, vd
);
692 fmt
= GET_RTX_FORMAT (code
);
693 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
696 changed
|= replace_oldest_value_addr (&XEXP (x
, i
), cl
, mode
, as
,
698 else if (fmt
[i
] == 'E')
699 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
700 changed
|= replace_oldest_value_addr (&XVECEXP (x
, i
, j
), cl
,
707 /* Similar to replace_oldest_value_reg, but X contains a memory. */
710 replace_oldest_value_mem (rtx x
, rtx_insn
*insn
, struct value_data
*vd
)
714 if (DEBUG_INSN_P (insn
))
717 cl
= base_reg_class (GET_MODE (x
), MEM_ADDR_SPACE (x
), MEM
, SCRATCH
);
719 return replace_oldest_value_addr (&XEXP (x
, 0), cl
,
720 GET_MODE (x
), MEM_ADDR_SPACE (x
),
724 /* Apply all queued updates for DEBUG_INSNs that change some reg to
728 apply_debug_insn_changes (struct value_data
*vd
, unsigned int regno
)
730 struct queued_debug_insn_change
*change
;
731 rtx_insn
*last_insn
= vd
->e
[regno
].debug_insn_changes
->insn
;
733 for (change
= vd
->e
[regno
].debug_insn_changes
;
735 change
= change
->next
)
737 if (last_insn
!= change
->insn
)
739 apply_change_group ();
740 last_insn
= change
->insn
;
742 validate_change (change
->insn
, change
->loc
, change
->new_rtx
, 1);
744 apply_change_group ();
747 /* Called via note_uses, for all used registers in a real insn
748 apply DEBUG_INSN changes that change registers to the used
752 cprop_find_used_regs (rtx
*loc
, void *data
)
754 struct value_data
*const vd
= (struct value_data
*) data
;
755 subrtx_iterator::array_type array
;
756 FOR_EACH_SUBRTX (iter
, array
, *loc
, NONCONST
)
761 unsigned int regno
= REGNO (x
);
762 if (vd
->e
[regno
].debug_insn_changes
)
764 apply_debug_insn_changes (vd
, regno
);
765 free_debug_insn_changes (vd
, regno
);
771 /* Apply clobbers of INSN in PATTERN and C_I_F_U to value_data VD. */
774 kill_clobbered_values (rtx_insn
*insn
, struct value_data
*vd
)
776 note_stores (insn
, kill_clobbered_value
, vd
);
779 /* Perform the forward copy propagation on basic block BB. */
782 copyprop_hardreg_forward_1 (basic_block bb
, struct value_data
*vd
)
784 bool anything_changed
= false;
785 rtx_insn
*insn
, *next
;
787 for (insn
= BB_HEAD (bb
); ; insn
= next
)
789 int n_ops
, i
, predicated
;
790 bool is_asm
, any_replacements
;
793 bool changed
= false;
794 struct kill_set_value_data ksvd
;
796 next
= NEXT_INSN (insn
);
797 if (!NONDEBUG_INSN_P (insn
))
799 if (DEBUG_BIND_INSN_P (insn
))
801 rtx loc
= INSN_VAR_LOCATION_LOC (insn
);
802 if (!VAR_LOC_UNKNOWN_P (loc
))
803 replace_oldest_value_addr (&INSN_VAR_LOCATION_LOC (insn
),
804 ALL_REGS
, GET_MODE (loc
),
805 ADDR_SPACE_GENERIC
, insn
, vd
);
808 if (insn
== BB_END (bb
))
814 set
= single_set (insn
);
816 /* Detect noop sets and remove them before processing side effects. */
817 if (set
&& REG_P (SET_DEST (set
)) && REG_P (SET_SRC (set
)))
819 unsigned int regno
= REGNO (SET_SRC (set
));
820 rtx r1
= find_oldest_value_reg (REGNO_REG_CLASS (regno
),
822 rtx r2
= find_oldest_value_reg (REGNO_REG_CLASS (regno
),
824 if (rtx_equal_p (r1
? r1
: SET_DEST (set
), r2
? r2
: SET_SRC (set
)))
826 bool last
= insn
== BB_END (bb
);
834 /* Detect obviously dead sets (via REG_UNUSED notes) and remove them. */
836 && !RTX_FRAME_RELATED_P (insn
)
837 && NONJUMP_INSN_P (insn
)
839 && find_reg_note (insn
, REG_UNUSED
, SET_DEST (set
))
840 && !side_effects_p (SET_SRC (set
))
841 && !side_effects_p (SET_DEST (set
)))
843 bool last
= insn
== BB_END (bb
);
851 extract_constrain_insn (insn
);
852 preprocess_constraints (insn
);
853 const operand_alternative
*op_alt
= which_op_alt ();
854 n_ops
= recog_data
.n_operands
;
855 is_asm
= asm_noperands (PATTERN (insn
)) >= 0;
857 /* Simplify the code below by promoting OP_OUT to OP_INOUT
858 in predicated instructions. */
860 predicated
= GET_CODE (PATTERN (insn
)) == COND_EXEC
;
861 for (i
= 0; i
< n_ops
; ++i
)
863 int matches
= op_alt
[i
].matches
;
864 if (matches
>= 0 || op_alt
[i
].matched
>= 0
865 || (predicated
&& recog_data
.operand_type
[i
] == OP_OUT
))
866 recog_data
.operand_type
[i
] = OP_INOUT
;
869 /* Apply changes to earlier DEBUG_INSNs if possible. */
870 if (vd
->n_debug_insn_changes
)
871 note_uses (&PATTERN (insn
), cprop_find_used_regs
, vd
);
873 /* For each earlyclobber operand, zap the value data. */
874 for (i
= 0; i
< n_ops
; i
++)
875 if (op_alt
[i
].earlyclobber
)
876 kill_value (recog_data
.operand
[i
], vd
);
878 /* Within asms, a clobber cannot overlap inputs or outputs.
879 I wouldn't think this were true for regular insns, but
880 scan_rtx treats them like that... */
881 kill_clobbered_values (insn
, vd
);
883 /* Kill all auto-incremented values. */
884 /* ??? REG_INC is useless, since stack pushes aren't done that way. */
885 kill_autoinc_value (insn
, vd
);
887 /* Kill all early-clobbered operands. */
888 for (i
= 0; i
< n_ops
; i
++)
889 if (op_alt
[i
].earlyclobber
)
890 kill_value (recog_data
.operand
[i
], vd
);
892 /* If we have dead sets in the insn, then we need to note these as we
894 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
896 if (REG_NOTE_KIND (link
) == REG_UNUSED
)
898 kill_value (XEXP (link
, 0), vd
);
899 /* Furthermore, if the insn looked like a single-set,
900 but the dead store kills the source value of that
901 set, then we can no-longer use the plain move
902 special case below. */
904 && reg_overlap_mentioned_p (XEXP (link
, 0), SET_SRC (set
)))
908 /* We need to keep CFI info correct, and the same on all paths,
909 so we cannot normally replace the registers REG_CFA_REGISTER
911 if (REG_NOTE_KIND (link
) == REG_CFA_REGISTER
)
912 goto did_replacement
;
915 /* Special-case plain move instructions, since we may well
916 be able to do the move from a different register class. */
917 if (set
&& REG_P (SET_SRC (set
)))
919 rtx src
= SET_SRC (set
);
920 rtx dest
= SET_DEST (set
);
921 unsigned int regno
= REGNO (src
);
922 machine_mode mode
= GET_MODE (src
);
926 /* If we are accessing SRC in some mode other that what we
927 set it in, make sure that the replacement is valid. */
928 if (mode
!= vd
->e
[regno
].mode
)
931 > hard_regno_nregs (regno
, vd
->e
[regno
].mode
))
932 goto no_move_special_case
;
934 /* And likewise, if we are narrowing on big endian the transformation
936 if (REG_NREGS (src
) < hard_regno_nregs (regno
, vd
->e
[regno
].mode
)
937 && maybe_ne (subreg_lowpart_offset (mode
,
938 vd
->e
[regno
].mode
), 0U))
939 goto no_move_special_case
;
942 /* If the destination is also a register, try to find a source
943 register in the same class. */
946 new_rtx
= find_oldest_value_reg (REGNO_REG_CLASS (regno
),
949 if (new_rtx
&& validate_change (insn
, &SET_SRC (set
), new_rtx
, 0))
953 "insn %u: replaced reg %u with %u\n",
954 INSN_UID (insn
), regno
, REGNO (new_rtx
));
956 goto did_replacement
;
958 /* We need to re-extract as validate_change clobbers
960 extract_constrain_insn (insn
);
961 preprocess_constraints (insn
);
964 /* Otherwise, try all valid registers and see if its valid. */
965 for (i
= vd
->e
[regno
].oldest_regno
; i
!= regno
;
966 i
= vd
->e
[i
].next_regno
)
968 new_rtx
= maybe_mode_change (vd
->e
[i
].mode
, vd
->e
[regno
].mode
,
970 if (new_rtx
!= NULL_RTX
)
972 /* Don't propagate for a more expensive reg-reg move. */
975 enum reg_class from
= REGNO_REG_CLASS (regno
);
976 enum reg_class to
= REGNO_REG_CLASS (REGNO (dest
));
977 enum reg_class new_from
= REGNO_REG_CLASS (i
);
978 unsigned int original_cost
979 = targetm
.register_move_cost (mode
, from
, to
);
980 unsigned int after_cost
981 = targetm
.register_move_cost (mode
, new_from
, to
);
982 if (after_cost
> original_cost
)
986 if (validate_change (insn
, &SET_SRC (set
), new_rtx
, 0))
988 if (maybe_copy_reg_attrs (new_rtx
, src
))
992 "insn %u: replaced reg %u with %u\n",
993 INSN_UID (insn
), regno
, REGNO (new_rtx
));
995 goto did_replacement
;
998 /* We need to re-extract as validate_change clobbers
1000 extract_constrain_insn (insn
);
1001 preprocess_constraints (insn
);
1005 no_move_special_case
:
1007 any_replacements
= false;
1009 /* For each input operand, replace a hard register with the
1010 eldest live copy that's in an appropriate register class. */
1011 for (i
= 0; i
< n_ops
; i
++)
1013 bool replaced
= false;
1015 /* Don't scan match_operand here, since we've no reg class
1016 information to pass down. Any operands that we could
1017 substitute in will be represented elsewhere. */
1018 if (recog_data
.constraints
[i
][0] == '\0')
1021 /* Don't replace in asms intentionally referencing hard regs. */
1022 if (is_asm
&& REG_P (recog_data
.operand
[i
])
1023 && (REGNO (recog_data
.operand
[i
])
1024 == ORIGINAL_REGNO (recog_data
.operand
[i
])))
1027 if (recog_data
.operand_type
[i
] == OP_IN
)
1029 if (op_alt
[i
].is_address
)
1031 = replace_oldest_value_addr (recog_data
.operand_loc
[i
],
1032 alternative_class (op_alt
, i
),
1033 VOIDmode
, ADDR_SPACE_GENERIC
,
1035 else if (REG_P (recog_data
.operand
[i
]))
1037 = replace_oldest_value_reg (recog_data
.operand_loc
[i
],
1038 alternative_class (op_alt
, i
),
1040 else if (MEM_P (recog_data
.operand
[i
]))
1041 replaced
= replace_oldest_value_mem (recog_data
.operand
[i
],
1044 else if (MEM_P (recog_data
.operand
[i
]))
1045 replaced
= replace_oldest_value_mem (recog_data
.operand
[i
],
1048 /* If we performed any replacement, update match_dups. */
1054 new_rtx
= *recog_data
.operand_loc
[i
];
1055 recog_data
.operand
[i
] = new_rtx
;
1056 for (j
= 0; j
< recog_data
.n_dups
; j
++)
1057 if (recog_data
.dup_num
[j
] == i
)
1058 validate_unshare_change (insn
, recog_data
.dup_loc
[j
], new_rtx
, 1);
1060 any_replacements
= true;
1064 if (any_replacements
)
1066 if (! apply_change_group ())
1070 "insn %u: reg replacements not verified\n",
1080 anything_changed
= true;
1082 /* If something changed, perhaps further changes to earlier
1083 DEBUG_INSNs can be applied. */
1084 if (vd
->n_debug_insn_changes
)
1085 note_uses (&PATTERN (insn
), cprop_find_used_regs
, vd
);
1086 df_insn_rescan (insn
);
1090 ksvd
.ignore_set_reg
= NULL_RTX
;
1092 /* Clobber call-clobbered registers. */
1095 unsigned int set_regno
= INVALID_REGNUM
;
1096 unsigned int set_nregs
= 0;
1100 for (exp
= CALL_INSN_FUNCTION_USAGE (insn
); exp
; exp
= XEXP (exp
, 1))
1102 rtx x
= XEXP (exp
, 0);
1103 if (GET_CODE (x
) == SET
)
1105 rtx dest
= SET_DEST (x
);
1106 kill_value (dest
, vd
);
1107 set_value_regno (REGNO (dest
), GET_MODE (dest
), vd
);
1108 copy_value (dest
, SET_SRC (x
), vd
);
1109 ksvd
.ignore_set_reg
= dest
;
1110 set_regno
= REGNO (dest
);
1111 set_nregs
= REG_NREGS (dest
);
1116 function_abi callee_abi
= insn_callee_abi (insn
);
1117 for (regno
= 0; regno
< FIRST_PSEUDO_REGISTER
; regno
++)
1118 if (vd
->e
[regno
].mode
!= VOIDmode
1119 && callee_abi
.clobbers_reg_p (vd
->e
[regno
].mode
, regno
)
1120 && (regno
< set_regno
|| regno
>= set_regno
+ set_nregs
))
1121 kill_value_regno (regno
, 1, vd
);
1123 /* If SET was seen in CALL_INSN_FUNCTION_USAGE, and SET_SRC
1124 of the SET isn't clobbered by CALLEE_ABI, but instead among
1125 CLOBBERs on the CALL_INSN, we could wrongly assume the
1126 value in it is still live. */
1127 if (ksvd
.ignore_set_reg
)
1128 kill_clobbered_values (insn
, vd
);
1132 && REG_P (SET_DEST (set
))
1133 && REG_P (SET_SRC (set
)));
1134 bool noop_p
= (copy_p
1135 && rtx_equal_p (SET_DEST (set
), SET_SRC (set
)));
1137 /* If a noop move is using narrower mode than we have recorded,
1138 we need to either remove the noop move, or kill_set_value. */
1140 && partial_subreg_p (GET_MODE (SET_DEST (set
)),
1141 vd
->e
[REGNO (SET_DEST (set
))].mode
))
1143 if (noop_move_p (insn
))
1145 bool last
= insn
== BB_END (bb
);
1156 /* Notice stores. */
1157 note_stores (insn
, kill_set_value
, &ksvd
);
1159 /* Notice copies. */
1162 df_insn_rescan (insn
);
1163 copy_value (SET_DEST (set
), SET_SRC (set
), vd
);
1167 if (insn
== BB_END (bb
))
1171 return anything_changed
;
1174 /* Dump the value chain data to stderr. */
1177 debug_value_data (struct value_data
*vd
)
1182 CLEAR_HARD_REG_SET (set
);
1184 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1185 if (vd
->e
[i
].oldest_regno
== i
)
1187 if (vd
->e
[i
].mode
== VOIDmode
)
1189 if (vd
->e
[i
].next_regno
!= INVALID_REGNUM
)
1190 fprintf (stderr
, "[%u] Bad next_regno for empty chain (%u)\n",
1191 i
, vd
->e
[i
].next_regno
);
1195 SET_HARD_REG_BIT (set
, i
);
1196 fprintf (stderr
, "[%u %s] ", i
, GET_MODE_NAME (vd
->e
[i
].mode
));
1198 for (j
= vd
->e
[i
].next_regno
;
1199 j
!= INVALID_REGNUM
;
1200 j
= vd
->e
[j
].next_regno
)
1202 if (TEST_HARD_REG_BIT (set
, j
))
1204 fprintf (stderr
, "[%u] Loop in regno chain\n", j
);
1208 if (vd
->e
[j
].oldest_regno
!= i
)
1210 fprintf (stderr
, "[%u] Bad oldest_regno (%u)\n",
1211 j
, vd
->e
[j
].oldest_regno
);
1214 SET_HARD_REG_BIT (set
, j
);
1215 fprintf (stderr
, "[%u %s] ", j
, GET_MODE_NAME (vd
->e
[j
].mode
));
1217 fputc ('\n', stderr
);
1220 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1221 if (! TEST_HARD_REG_BIT (set
, i
)
1222 && (vd
->e
[i
].mode
!= VOIDmode
1223 || vd
->e
[i
].oldest_regno
!= i
1224 || vd
->e
[i
].next_regno
!= INVALID_REGNUM
))
1225 fprintf (stderr
, "[%u] Non-empty reg in chain (%s %u %i)\n",
1226 i
, GET_MODE_NAME (vd
->e
[i
].mode
), vd
->e
[i
].oldest_regno
,
1227 vd
->e
[i
].next_regno
);
1230 /* Do copyprop_hardreg_forward_1 for a single basic block BB.
1231 DEBUG_INSN is skipped since we do not want to involve DF related
1232 staff as how it is handled in function pass_cprop_hardreg::execute.
1234 NOTE: Currently it is only used for shrink-wrap. Maybe extend it
1235 to handle DEBUG_INSN for other uses. */
1238 copyprop_hardreg_forward_bb_without_debug_insn (basic_block bb
)
1240 struct value_data
*vd
;
1241 vd
= XNEWVEC (struct value_data
, 1);
1242 init_value_data (vd
);
1244 skip_debug_insn_p
= true;
1245 copyprop_hardreg_forward_1 (bb
, vd
);
1247 skip_debug_insn_p
= false;
1251 validate_value_data (struct value_data
*vd
)
1256 CLEAR_HARD_REG_SET (set
);
1258 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1259 if (vd
->e
[i
].oldest_regno
== i
)
1261 if (vd
->e
[i
].mode
== VOIDmode
)
1263 if (vd
->e
[i
].next_regno
!= INVALID_REGNUM
)
1264 internal_error ("%qs: [%u] bad %<next_regno%> for empty chain (%u)",
1265 __func__
, i
, vd
->e
[i
].next_regno
);
1269 SET_HARD_REG_BIT (set
, i
);
1271 for (j
= vd
->e
[i
].next_regno
;
1272 j
!= INVALID_REGNUM
;
1273 j
= vd
->e
[j
].next_regno
)
1275 if (TEST_HARD_REG_BIT (set
, j
))
1276 internal_error ("%qs: loop in %<next_regno%> chain (%u)",
1278 if (vd
->e
[j
].oldest_regno
!= i
)
1279 internal_error ("%qs: [%u] bad %<oldest_regno%> (%u)",
1280 __func__
, j
, vd
->e
[j
].oldest_regno
);
1282 SET_HARD_REG_BIT (set
, j
);
1286 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1287 if (! TEST_HARD_REG_BIT (set
, i
)
1288 && (vd
->e
[i
].mode
!= VOIDmode
1289 || vd
->e
[i
].oldest_regno
!= i
1290 || vd
->e
[i
].next_regno
!= INVALID_REGNUM
))
1291 internal_error ("%qs: [%u] non-empty register in chain (%s %u %i)",
1293 GET_MODE_NAME (vd
->e
[i
].mode
), vd
->e
[i
].oldest_regno
,
1294 vd
->e
[i
].next_regno
);
1300 const pass_data pass_data_cprop_hardreg
=
1302 RTL_PASS
, /* type */
1303 "cprop_hardreg", /* name */
1304 OPTGROUP_NONE
, /* optinfo_flags */
1305 TV_CPROP_REGISTERS
, /* tv_id */
1306 0, /* properties_required */
1307 0, /* properties_provided */
1308 0, /* properties_destroyed */
1309 0, /* todo_flags_start */
1310 TODO_df_finish
, /* todo_flags_finish */
1313 class pass_cprop_hardreg
: public rtl_opt_pass
1316 pass_cprop_hardreg (gcc::context
*ctxt
)
1317 : rtl_opt_pass (pass_data_cprop_hardreg
, ctxt
)
1320 /* opt_pass methods: */
1321 bool gate (function
*) final override
1323 return (optimize
> 0 && (flag_cprop_registers
));
1326 unsigned int execute (function
*) final override
;
1328 }; // class pass_cprop_hardreg
1331 cprop_hardreg_bb (basic_block bb
, struct value_data
*all_vd
, sbitmap visited
)
1333 bitmap_set_bit (visited
, bb
->index
);
1335 /* If a block has a single predecessor, that we've already
1336 processed, begin with the value data that was live at
1337 the end of the predecessor block. */
1338 /* ??? Ought to use more intelligent queuing of blocks. */
1339 if (single_pred_p (bb
)
1340 && bitmap_bit_p (visited
, single_pred (bb
)->index
)
1341 && ! (single_pred_edge (bb
)->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
)))
1343 all_vd
[bb
->index
] = all_vd
[single_pred (bb
)->index
];
1344 if (all_vd
[bb
->index
].n_debug_insn_changes
)
1348 for (regno
= 0; regno
< FIRST_PSEUDO_REGISTER
; regno
++)
1350 if (all_vd
[bb
->index
].e
[regno
].debug_insn_changes
)
1352 struct queued_debug_insn_change
*cur
;
1353 for (cur
= all_vd
[bb
->index
].e
[regno
].debug_insn_changes
;
1354 cur
; cur
= cur
->next
)
1355 --all_vd
[bb
->index
].n_debug_insn_changes
;
1356 all_vd
[bb
->index
].e
[regno
].debug_insn_changes
= NULL
;
1357 if (all_vd
[bb
->index
].n_debug_insn_changes
== 0)
1364 init_value_data (all_vd
+ bb
->index
);
1366 return copyprop_hardreg_forward_1 (bb
, all_vd
+ bb
->index
);
1370 cprop_hardreg_debug (function
*fun
, struct value_data
*all_vd
)
1374 FOR_EACH_BB_FN (bb
, fun
)
1375 if (all_vd
[bb
->index
].n_debug_insn_changes
)
1380 live
= df_get_live_out (bb
);
1381 for (regno
= 0; regno
< FIRST_PSEUDO_REGISTER
; regno
++)
1382 if (all_vd
[bb
->index
].e
[regno
].debug_insn_changes
)
1384 if (REGNO_REG_SET_P (live
, regno
))
1385 apply_debug_insn_changes (all_vd
+ bb
->index
, regno
);
1387 struct queued_debug_insn_change
*cur
;
1388 for (cur
= all_vd
[bb
->index
].e
[regno
].debug_insn_changes
;
1389 cur
; cur
= cur
->next
)
1390 --all_vd
[bb
->index
].n_debug_insn_changes
;
1391 all_vd
[bb
->index
].e
[regno
].debug_insn_changes
= NULL
;
1392 if (all_vd
[bb
->index
].n_debug_insn_changes
== 0)
1397 queued_debug_insn_change_pool
.release ();
1401 pass_cprop_hardreg::execute (function
*fun
)
1403 struct value_data
*all_vd
;
1406 all_vd
= XNEWVEC (struct value_data
, last_basic_block_for_fn (fun
));
1408 auto_sbitmap
visited (last_basic_block_for_fn (fun
));
1409 bitmap_clear (visited
);
1411 auto_vec
<int> worklist1
, worklist2
;
1412 auto_vec
<int> *curr
= &worklist1
;
1413 auto_vec
<int> *next
= &worklist2
;
1414 bool any_debug_changes
= false;
1416 /* We need accurate notes. Earlier passes such as if-conversion may
1417 leave notes in an inconsistent state. */
1418 df_note_add_problem ();
1421 /* It is tempting to set DF_LR_RUN_DCE, but DCE may choose to delete
1422 an insn and this pass would not have visibility into the removal.
1423 This pass would then potentially use the source of that
1424 INSN for propagation purposes, generating invalid code.
1426 So we just ask for updated notes and handle trivial deletions
1427 within this pass where we can update this passes internal
1428 data structures appropriately. */
1429 df_set_flags (DF_DEFER_INSN_RESCAN
);
1431 FOR_EACH_BB_FN (bb
, fun
)
1433 if (cprop_hardreg_bb (bb
, all_vd
, visited
))
1434 curr
->safe_push (bb
->index
);
1435 if (all_vd
[bb
->index
].n_debug_insn_changes
)
1436 any_debug_changes
= true;
1439 /* We must call df_analyze here unconditionally to ensure that the
1440 REG_UNUSED and REG_DEAD notes are consistent with and without -g. */
1443 if (MAY_HAVE_DEBUG_BIND_INSNS
&& any_debug_changes
)
1444 cprop_hardreg_debug (fun
, all_vd
);
1446 /* Repeat pass up to PASSES times, but only processing basic blocks
1447 that have changed on the previous iteration. CURR points to the
1448 current worklist, and each iteration populates the NEXT worklist,
1449 swapping pointers after each cycle. */
1451 unsigned int passes
= optimize
> 1 ? 3 : 2;
1452 for (unsigned int pass
= 2; pass
<= passes
&& !curr
->is_empty (); pass
++)
1454 any_debug_changes
= false;
1455 bitmap_clear (visited
);
1457 for (int index
: *curr
)
1459 bb
= BASIC_BLOCK_FOR_FN (fun
, index
);
1460 if (cprop_hardreg_bb (bb
, all_vd
, visited
))
1461 next
->safe_push (bb
->index
);
1462 if (all_vd
[bb
->index
].n_debug_insn_changes
)
1463 any_debug_changes
= true;
1467 if (MAY_HAVE_DEBUG_BIND_INSNS
&& any_debug_changes
)
1468 cprop_hardreg_debug (fun
, all_vd
);
1469 std::swap (curr
, next
);
1479 make_pass_cprop_hardreg (gcc::context
*ctxt
)
1481 return new pass_cprop_hardreg (ctxt
);