1 /* Copy propagation on hard registers for the GNU compiler.
2 Copyright (C) 2000-2021 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
)
427 if (orig_mode
== new_mode
)
428 return gen_raw_REG (new_mode
, regno
);
429 else if (mode_change_ok (orig_mode
, new_mode
, regno
))
431 int copy_nregs
= hard_regno_nregs (copy_regno
, copy_mode
);
432 int use_nregs
= hard_regno_nregs (copy_regno
, new_mode
);
433 poly_uint64 bytes_per_reg
;
434 if (!can_div_trunc_p (GET_MODE_SIZE (copy_mode
),
435 copy_nregs
, &bytes_per_reg
))
437 poly_uint64 copy_offset
= bytes_per_reg
* (copy_nregs
- use_nregs
);
439 = subreg_size_lowpart_offset (GET_MODE_SIZE (new_mode
) + copy_offset
,
440 GET_MODE_SIZE (orig_mode
));
441 regno
+= subreg_regno_offset (regno
, orig_mode
, offset
, new_mode
);
442 if (targetm
.hard_regno_mode_ok (regno
, new_mode
))
443 return gen_raw_REG (new_mode
, regno
);
448 /* Find the oldest copy of the value contained in REGNO that is in
449 register class CL and has mode MODE. If found, return an rtx
450 of that oldest register, otherwise return NULL. */
453 find_oldest_value_reg (enum reg_class cl
, rtx reg
, struct value_data
*vd
)
455 unsigned int regno
= REGNO (reg
);
456 machine_mode mode
= GET_MODE (reg
);
459 gcc_assert (regno
< FIRST_PSEUDO_REGISTER
);
461 /* If we are accessing REG in some mode other that what we set it in,
462 make sure that the replacement is valid. In particular, consider
463 (set (reg:DI r11) (...))
464 (set (reg:SI r9) (reg:SI r11))
465 (set (reg:SI r10) (...))
466 (set (...) (reg:DI r9))
467 Replacing r9 with r11 is invalid. */
468 if (mode
!= vd
->e
[regno
].mode
469 && (REG_NREGS (reg
) > hard_regno_nregs (regno
, vd
->e
[regno
].mode
)
470 || !REG_CAN_CHANGE_MODE_P (regno
, mode
, vd
->e
[regno
].mode
)))
473 for (i
= vd
->e
[regno
].oldest_regno
; i
!= regno
; i
= vd
->e
[i
].next_regno
)
475 machine_mode oldmode
= vd
->e
[i
].mode
;
478 if (!in_hard_reg_set_p (reg_class_contents
[cl
], mode
, i
))
481 new_rtx
= maybe_mode_change (oldmode
, vd
->e
[regno
].mode
, mode
, i
, regno
);
484 ORIGINAL_REGNO (new_rtx
) = ORIGINAL_REGNO (reg
);
485 REG_ATTRS (new_rtx
) = REG_ATTRS (reg
);
486 REG_POINTER (new_rtx
) = REG_POINTER (reg
);
494 /* If possible, replace the register at *LOC with the oldest register
495 in register class CL. Return true if successfully replaced. */
498 replace_oldest_value_reg (rtx
*loc
, enum reg_class cl
, rtx_insn
*insn
,
499 struct value_data
*vd
)
501 rtx new_rtx
= find_oldest_value_reg (cl
, *loc
, vd
);
502 if (new_rtx
&& (!DEBUG_INSN_P (insn
) || !skip_debug_insn_p
))
504 if (DEBUG_INSN_P (insn
))
506 struct queued_debug_insn_change
*change
;
509 fprintf (dump_file
, "debug_insn %u: queued replacing reg %u with %u\n",
510 INSN_UID (insn
), REGNO (*loc
), REGNO (new_rtx
));
512 change
= queued_debug_insn_change_pool
.allocate ();
513 change
->next
= vd
->e
[REGNO (new_rtx
)].debug_insn_changes
;
516 change
->new_rtx
= new_rtx
;
517 vd
->e
[REGNO (new_rtx
)].debug_insn_changes
= change
;
518 ++vd
->n_debug_insn_changes
;
522 fprintf (dump_file
, "insn %u: replaced reg %u with %u\n",
523 INSN_UID (insn
), REGNO (*loc
), REGNO (new_rtx
));
525 validate_change (insn
, loc
, new_rtx
, 1);
531 /* Similar to replace_oldest_value_reg, but *LOC contains an address.
532 Adapted from find_reloads_address_1. CL is INDEX_REG_CLASS or
533 BASE_REG_CLASS depending on how the register is being considered. */
536 replace_oldest_value_addr (rtx
*loc
, enum reg_class cl
,
537 machine_mode mode
, addr_space_t as
,
538 rtx_insn
*insn
, struct value_data
*vd
)
541 RTX_CODE code
= GET_CODE (x
);
544 bool changed
= false;
549 if (DEBUG_INSN_P (insn
))
553 rtx orig_op0
= XEXP (x
, 0);
554 rtx orig_op1
= XEXP (x
, 1);
555 RTX_CODE code0
= GET_CODE (orig_op0
);
556 RTX_CODE code1
= GET_CODE (orig_op1
);
561 enum rtx_code index_code
= SCRATCH
;
563 if (GET_CODE (op0
) == SUBREG
)
565 op0
= SUBREG_REG (op0
);
566 code0
= GET_CODE (op0
);
569 if (GET_CODE (op1
) == SUBREG
)
571 op1
= SUBREG_REG (op1
);
572 code1
= GET_CODE (op1
);
575 if (code0
== MULT
|| code0
== SIGN_EXTEND
|| code0
== TRUNCATE
576 || code0
== ZERO_EXTEND
|| code1
== MEM
)
580 index_code
= GET_CODE (*locI
);
582 else if (code1
== MULT
|| code1
== SIGN_EXTEND
|| code1
== TRUNCATE
583 || code1
== ZERO_EXTEND
|| code0
== MEM
)
587 index_code
= GET_CODE (*locI
);
589 else if (code0
== CONST_INT
|| code0
== CONST
590 || code0
== SYMBOL_REF
|| code0
== LABEL_REF
)
593 index_code
= GET_CODE (XEXP (x
, 0));
595 else if (code1
== CONST_INT
|| code1
== CONST
596 || code1
== SYMBOL_REF
|| code1
== LABEL_REF
)
599 index_code
= GET_CODE (XEXP (x
, 1));
601 else if (code0
== REG
&& code1
== REG
)
604 unsigned regno0
= REGNO (op0
), regno1
= REGNO (op1
);
606 if (REGNO_OK_FOR_INDEX_P (regno1
)
607 && regno_ok_for_base_p (regno0
, mode
, as
, PLUS
, REG
))
609 else if (REGNO_OK_FOR_INDEX_P (regno0
)
610 && regno_ok_for_base_p (regno1
, mode
, as
, PLUS
, REG
))
612 else if (regno_ok_for_base_p (regno0
, mode
, as
, PLUS
, REG
)
613 || REGNO_OK_FOR_INDEX_P (regno1
))
615 else if (regno_ok_for_base_p (regno1
, mode
, as
, PLUS
, REG
))
620 locI
= &XEXP (x
, index_op
);
621 locB
= &XEXP (x
, !index_op
);
622 index_code
= GET_CODE (*locI
);
624 else if (code0
== REG
)
628 index_code
= GET_CODE (*locI
);
630 else if (code1
== REG
)
634 index_code
= GET_CODE (*locI
);
638 changed
|= replace_oldest_value_addr (locI
, INDEX_REG_CLASS
,
641 changed
|= replace_oldest_value_addr (locB
,
642 base_reg_class (mode
, as
, PLUS
,
657 return replace_oldest_value_mem (x
, insn
, vd
);
660 return replace_oldest_value_reg (loc
, cl
, insn
, vd
);
666 fmt
= GET_RTX_FORMAT (code
);
667 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
670 changed
|= replace_oldest_value_addr (&XEXP (x
, i
), cl
, mode
, as
,
672 else if (fmt
[i
] == 'E')
673 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
674 changed
|= replace_oldest_value_addr (&XVECEXP (x
, i
, j
), cl
,
681 /* Similar to replace_oldest_value_reg, but X contains a memory. */
684 replace_oldest_value_mem (rtx x
, rtx_insn
*insn
, struct value_data
*vd
)
688 if (DEBUG_INSN_P (insn
))
691 cl
= base_reg_class (GET_MODE (x
), MEM_ADDR_SPACE (x
), MEM
, SCRATCH
);
693 return replace_oldest_value_addr (&XEXP (x
, 0), cl
,
694 GET_MODE (x
), MEM_ADDR_SPACE (x
),
698 /* Apply all queued updates for DEBUG_INSNs that change some reg to
702 apply_debug_insn_changes (struct value_data
*vd
, unsigned int regno
)
704 struct queued_debug_insn_change
*change
;
705 rtx_insn
*last_insn
= vd
->e
[regno
].debug_insn_changes
->insn
;
707 for (change
= vd
->e
[regno
].debug_insn_changes
;
709 change
= change
->next
)
711 if (last_insn
!= change
->insn
)
713 apply_change_group ();
714 last_insn
= change
->insn
;
716 validate_change (change
->insn
, change
->loc
, change
->new_rtx
, 1);
718 apply_change_group ();
721 /* Called via note_uses, for all used registers in a real insn
722 apply DEBUG_INSN changes that change registers to the used
726 cprop_find_used_regs (rtx
*loc
, void *data
)
728 struct value_data
*const vd
= (struct value_data
*) data
;
729 subrtx_iterator::array_type array
;
730 FOR_EACH_SUBRTX (iter
, array
, *loc
, NONCONST
)
735 unsigned int regno
= REGNO (x
);
736 if (vd
->e
[regno
].debug_insn_changes
)
738 apply_debug_insn_changes (vd
, regno
);
739 free_debug_insn_changes (vd
, regno
);
745 /* Apply clobbers of INSN in PATTERN and C_I_F_U to value_data VD. */
748 kill_clobbered_values (rtx_insn
*insn
, struct value_data
*vd
)
750 note_stores (insn
, kill_clobbered_value
, vd
);
753 /* Perform the forward copy propagation on basic block BB. */
756 copyprop_hardreg_forward_1 (basic_block bb
, struct value_data
*vd
)
758 bool anything_changed
= false;
759 rtx_insn
*insn
, *next
;
761 for (insn
= BB_HEAD (bb
); ; insn
= next
)
763 int n_ops
, i
, predicated
;
764 bool is_asm
, any_replacements
;
767 bool changed
= false;
768 struct kill_set_value_data ksvd
;
770 next
= NEXT_INSN (insn
);
771 if (!NONDEBUG_INSN_P (insn
))
773 if (DEBUG_BIND_INSN_P (insn
))
775 rtx loc
= INSN_VAR_LOCATION_LOC (insn
);
776 if (!VAR_LOC_UNKNOWN_P (loc
))
777 replace_oldest_value_addr (&INSN_VAR_LOCATION_LOC (insn
),
778 ALL_REGS
, GET_MODE (loc
),
779 ADDR_SPACE_GENERIC
, insn
, vd
);
782 if (insn
== BB_END (bb
))
788 set
= single_set (insn
);
790 /* Detect noop sets and remove them before processing side effects. */
791 if (set
&& REG_P (SET_DEST (set
)) && REG_P (SET_SRC (set
)))
793 unsigned int regno
= REGNO (SET_SRC (set
));
794 rtx r1
= find_oldest_value_reg (REGNO_REG_CLASS (regno
),
796 rtx r2
= find_oldest_value_reg (REGNO_REG_CLASS (regno
),
798 if (rtx_equal_p (r1
? r1
: SET_DEST (set
), r2
? r2
: SET_SRC (set
)))
800 bool last
= insn
== BB_END (bb
);
808 /* Detect obviously dead sets (via REG_UNUSED notes) and remove them. */
810 && !RTX_FRAME_RELATED_P (insn
)
811 && NONJUMP_INSN_P (insn
)
813 && find_reg_note (insn
, REG_UNUSED
, SET_DEST (set
))
814 && !side_effects_p (SET_SRC (set
))
815 && !side_effects_p (SET_DEST (set
)))
817 bool last
= insn
== BB_END (bb
);
825 extract_constrain_insn (insn
);
826 preprocess_constraints (insn
);
827 const operand_alternative
*op_alt
= which_op_alt ();
828 n_ops
= recog_data
.n_operands
;
829 is_asm
= asm_noperands (PATTERN (insn
)) >= 0;
831 /* Simplify the code below by promoting OP_OUT to OP_INOUT
832 in predicated instructions. */
834 predicated
= GET_CODE (PATTERN (insn
)) == COND_EXEC
;
835 for (i
= 0; i
< n_ops
; ++i
)
837 int matches
= op_alt
[i
].matches
;
838 if (matches
>= 0 || op_alt
[i
].matched
>= 0
839 || (predicated
&& recog_data
.operand_type
[i
] == OP_OUT
))
840 recog_data
.operand_type
[i
] = OP_INOUT
;
843 /* Apply changes to earlier DEBUG_INSNs if possible. */
844 if (vd
->n_debug_insn_changes
)
845 note_uses (&PATTERN (insn
), cprop_find_used_regs
, vd
);
847 /* For each earlyclobber operand, zap the value data. */
848 for (i
= 0; i
< n_ops
; i
++)
849 if (op_alt
[i
].earlyclobber
)
850 kill_value (recog_data
.operand
[i
], vd
);
852 /* Within asms, a clobber cannot overlap inputs or outputs.
853 I wouldn't think this were true for regular insns, but
854 scan_rtx treats them like that... */
855 kill_clobbered_values (insn
, vd
);
857 /* Kill all auto-incremented values. */
858 /* ??? REG_INC is useless, since stack pushes aren't done that way. */
859 kill_autoinc_value (insn
, vd
);
861 /* Kill all early-clobbered operands. */
862 for (i
= 0; i
< n_ops
; i
++)
863 if (op_alt
[i
].earlyclobber
)
864 kill_value (recog_data
.operand
[i
], vd
);
866 /* If we have dead sets in the insn, then we need to note these as we
868 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
870 if (REG_NOTE_KIND (link
) == REG_UNUSED
)
872 kill_value (XEXP (link
, 0), vd
);
873 /* Furthermore, if the insn looked like a single-set,
874 but the dead store kills the source value of that
875 set, then we can no-longer use the plain move
876 special case below. */
878 && reg_overlap_mentioned_p (XEXP (link
, 0), SET_SRC (set
)))
882 /* We need to keep CFI info correct, and the same on all paths,
883 so we cannot normally replace the registers REG_CFA_REGISTER
885 if (REG_NOTE_KIND (link
) == REG_CFA_REGISTER
)
886 goto did_replacement
;
889 /* Special-case plain move instructions, since we may well
890 be able to do the move from a different register class. */
891 if (set
&& REG_P (SET_SRC (set
)))
893 rtx src
= SET_SRC (set
);
894 unsigned int regno
= REGNO (src
);
895 machine_mode mode
= GET_MODE (src
);
899 /* If we are accessing SRC in some mode other that what we
900 set it in, make sure that the replacement is valid. */
901 if (mode
!= vd
->e
[regno
].mode
)
904 > hard_regno_nregs (regno
, vd
->e
[regno
].mode
))
905 goto no_move_special_case
;
907 /* And likewise, if we are narrowing on big endian the transformation
909 if (REG_NREGS (src
) < hard_regno_nregs (regno
, vd
->e
[regno
].mode
)
910 && maybe_ne (subreg_lowpart_offset (mode
,
911 vd
->e
[regno
].mode
), 0U))
912 goto no_move_special_case
;
915 /* If the destination is also a register, try to find a source
916 register in the same class. */
917 if (REG_P (SET_DEST (set
)))
919 new_rtx
= find_oldest_value_reg (REGNO_REG_CLASS (regno
),
922 if (new_rtx
&& validate_change (insn
, &SET_SRC (set
), new_rtx
, 0))
926 "insn %u: replaced reg %u with %u\n",
927 INSN_UID (insn
), regno
, REGNO (new_rtx
));
929 goto did_replacement
;
931 /* We need to re-extract as validate_change clobbers
933 extract_constrain_insn (insn
);
934 preprocess_constraints (insn
);
937 /* Otherwise, try all valid registers and see if its valid. */
938 for (i
= vd
->e
[regno
].oldest_regno
; i
!= regno
;
939 i
= vd
->e
[i
].next_regno
)
941 new_rtx
= maybe_mode_change (vd
->e
[i
].mode
, vd
->e
[regno
].mode
,
943 if (new_rtx
!= NULL_RTX
)
945 if (validate_change (insn
, &SET_SRC (set
), new_rtx
, 0))
947 ORIGINAL_REGNO (new_rtx
) = ORIGINAL_REGNO (src
);
948 REG_ATTRS (new_rtx
) = REG_ATTRS (src
);
949 REG_POINTER (new_rtx
) = REG_POINTER (src
);
952 "insn %u: replaced reg %u with %u\n",
953 INSN_UID (insn
), regno
, REGNO (new_rtx
));
955 goto did_replacement
;
957 /* We need to re-extract as validate_change clobbers
959 extract_constrain_insn (insn
);
960 preprocess_constraints (insn
);
964 no_move_special_case
:
966 any_replacements
= false;
968 /* For each input operand, replace a hard register with the
969 eldest live copy that's in an appropriate register class. */
970 for (i
= 0; i
< n_ops
; i
++)
972 bool replaced
= false;
974 /* Don't scan match_operand here, since we've no reg class
975 information to pass down. Any operands that we could
976 substitute in will be represented elsewhere. */
977 if (recog_data
.constraints
[i
][0] == '\0')
980 /* Don't replace in asms intentionally referencing hard regs. */
981 if (is_asm
&& REG_P (recog_data
.operand
[i
])
982 && (REGNO (recog_data
.operand
[i
])
983 == ORIGINAL_REGNO (recog_data
.operand
[i
])))
986 if (recog_data
.operand_type
[i
] == OP_IN
)
988 if (op_alt
[i
].is_address
)
990 = replace_oldest_value_addr (recog_data
.operand_loc
[i
],
991 alternative_class (op_alt
, i
),
992 VOIDmode
, ADDR_SPACE_GENERIC
,
994 else if (REG_P (recog_data
.operand
[i
]))
996 = replace_oldest_value_reg (recog_data
.operand_loc
[i
],
997 alternative_class (op_alt
, i
),
999 else if (MEM_P (recog_data
.operand
[i
]))
1000 replaced
= replace_oldest_value_mem (recog_data
.operand
[i
],
1003 else if (MEM_P (recog_data
.operand
[i
]))
1004 replaced
= replace_oldest_value_mem (recog_data
.operand
[i
],
1007 /* If we performed any replacement, update match_dups. */
1013 new_rtx
= *recog_data
.operand_loc
[i
];
1014 recog_data
.operand
[i
] = new_rtx
;
1015 for (j
= 0; j
< recog_data
.n_dups
; j
++)
1016 if (recog_data
.dup_num
[j
] == i
)
1017 validate_unshare_change (insn
, recog_data
.dup_loc
[j
], new_rtx
, 1);
1019 any_replacements
= true;
1023 if (any_replacements
)
1025 if (! apply_change_group ())
1029 "insn %u: reg replacements not verified\n",
1039 anything_changed
= true;
1041 /* If something changed, perhaps further changes to earlier
1042 DEBUG_INSNs can be applied. */
1043 if (vd
->n_debug_insn_changes
)
1044 note_uses (&PATTERN (insn
), cprop_find_used_regs
, vd
);
1045 df_insn_rescan (insn
);
1049 ksvd
.ignore_set_reg
= NULL_RTX
;
1051 /* Clobber call-clobbered registers. */
1054 unsigned int set_regno
= INVALID_REGNUM
;
1055 unsigned int set_nregs
= 0;
1059 for (exp
= CALL_INSN_FUNCTION_USAGE (insn
); exp
; exp
= XEXP (exp
, 1))
1061 rtx x
= XEXP (exp
, 0);
1062 if (GET_CODE (x
) == SET
)
1064 rtx dest
= SET_DEST (x
);
1065 kill_value (dest
, vd
);
1066 set_value_regno (REGNO (dest
), GET_MODE (dest
), vd
);
1067 copy_value (dest
, SET_SRC (x
), vd
);
1068 ksvd
.ignore_set_reg
= dest
;
1069 set_regno
= REGNO (dest
);
1070 set_nregs
= REG_NREGS (dest
);
1075 function_abi callee_abi
= insn_callee_abi (insn
);
1076 for (regno
= 0; regno
< FIRST_PSEUDO_REGISTER
; regno
++)
1077 if (vd
->e
[regno
].mode
!= VOIDmode
1078 && callee_abi
.clobbers_reg_p (vd
->e
[regno
].mode
, regno
)
1079 && (regno
< set_regno
|| regno
>= set_regno
+ set_nregs
))
1080 kill_value_regno (regno
, 1, vd
);
1082 /* If SET was seen in CALL_INSN_FUNCTION_USAGE, and SET_SRC
1083 of the SET isn't clobbered by CALLEE_ABI, but instead among
1084 CLOBBERs on the CALL_INSN, we could wrongly assume the
1085 value in it is still live. */
1086 if (ksvd
.ignore_set_reg
)
1087 kill_clobbered_values (insn
, vd
);
1091 && REG_P (SET_DEST (set
))
1092 && REG_P (SET_SRC (set
)));
1093 bool noop_p
= (copy_p
1094 && rtx_equal_p (SET_DEST (set
), SET_SRC (set
)));
1096 /* If a noop move is using narrower mode than we have recorded,
1097 we need to either remove the noop move, or kill_set_value. */
1099 && partial_subreg_p (GET_MODE (SET_DEST (set
)),
1100 vd
->e
[REGNO (SET_DEST (set
))].mode
))
1102 if (noop_move_p (insn
))
1104 bool last
= insn
== BB_END (bb
);
1115 /* Notice stores. */
1116 note_stores (insn
, kill_set_value
, &ksvd
);
1118 /* Notice copies. */
1121 df_insn_rescan (insn
);
1122 copy_value (SET_DEST (set
), SET_SRC (set
), vd
);
1126 if (insn
== BB_END (bb
))
1130 return anything_changed
;
1133 /* Dump the value chain data to stderr. */
1136 debug_value_data (struct value_data
*vd
)
1141 CLEAR_HARD_REG_SET (set
);
1143 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1144 if (vd
->e
[i
].oldest_regno
== i
)
1146 if (vd
->e
[i
].mode
== VOIDmode
)
1148 if (vd
->e
[i
].next_regno
!= INVALID_REGNUM
)
1149 fprintf (stderr
, "[%u] Bad next_regno for empty chain (%u)\n",
1150 i
, vd
->e
[i
].next_regno
);
1154 SET_HARD_REG_BIT (set
, i
);
1155 fprintf (stderr
, "[%u %s] ", i
, GET_MODE_NAME (vd
->e
[i
].mode
));
1157 for (j
= vd
->e
[i
].next_regno
;
1158 j
!= INVALID_REGNUM
;
1159 j
= vd
->e
[j
].next_regno
)
1161 if (TEST_HARD_REG_BIT (set
, j
))
1163 fprintf (stderr
, "[%u] Loop in regno chain\n", j
);
1167 if (vd
->e
[j
].oldest_regno
!= i
)
1169 fprintf (stderr
, "[%u] Bad oldest_regno (%u)\n",
1170 j
, vd
->e
[j
].oldest_regno
);
1173 SET_HARD_REG_BIT (set
, j
);
1174 fprintf (stderr
, "[%u %s] ", j
, GET_MODE_NAME (vd
->e
[j
].mode
));
1176 fputc ('\n', stderr
);
1179 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1180 if (! TEST_HARD_REG_BIT (set
, i
)
1181 && (vd
->e
[i
].mode
!= VOIDmode
1182 || vd
->e
[i
].oldest_regno
!= i
1183 || vd
->e
[i
].next_regno
!= INVALID_REGNUM
))
1184 fprintf (stderr
, "[%u] Non-empty reg in chain (%s %u %i)\n",
1185 i
, GET_MODE_NAME (vd
->e
[i
].mode
), vd
->e
[i
].oldest_regno
,
1186 vd
->e
[i
].next_regno
);
1189 /* Do copyprop_hardreg_forward_1 for a single basic block BB.
1190 DEBUG_INSN is skipped since we do not want to involve DF related
1191 staff as how it is handled in function pass_cprop_hardreg::execute.
1193 NOTE: Currently it is only used for shrink-wrap. Maybe extend it
1194 to handle DEBUG_INSN for other uses. */
1197 copyprop_hardreg_forward_bb_without_debug_insn (basic_block bb
)
1199 struct value_data
*vd
;
1200 vd
= XNEWVEC (struct value_data
, 1);
1201 init_value_data (vd
);
1203 skip_debug_insn_p
= true;
1204 copyprop_hardreg_forward_1 (bb
, vd
);
1206 skip_debug_insn_p
= false;
1210 validate_value_data (struct value_data
*vd
)
1215 CLEAR_HARD_REG_SET (set
);
1217 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1218 if (vd
->e
[i
].oldest_regno
== i
)
1220 if (vd
->e
[i
].mode
== VOIDmode
)
1222 if (vd
->e
[i
].next_regno
!= INVALID_REGNUM
)
1223 internal_error ("%qs: [%u] bad %<next_regno%> for empty chain (%u)",
1224 __func__
, i
, vd
->e
[i
].next_regno
);
1228 SET_HARD_REG_BIT (set
, i
);
1230 for (j
= vd
->e
[i
].next_regno
;
1231 j
!= INVALID_REGNUM
;
1232 j
= vd
->e
[j
].next_regno
)
1234 if (TEST_HARD_REG_BIT (set
, j
))
1235 internal_error ("%qs: loop in %<next_regno%> chain (%u)",
1237 if (vd
->e
[j
].oldest_regno
!= i
)
1238 internal_error ("%qs: [%u] bad %<oldest_regno%> (%u)",
1239 __func__
, j
, vd
->e
[j
].oldest_regno
);
1241 SET_HARD_REG_BIT (set
, j
);
1245 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1246 if (! TEST_HARD_REG_BIT (set
, i
)
1247 && (vd
->e
[i
].mode
!= VOIDmode
1248 || vd
->e
[i
].oldest_regno
!= i
1249 || vd
->e
[i
].next_regno
!= INVALID_REGNUM
))
1250 internal_error ("%qs: [%u] non-empty register in chain (%s %u %i)",
1252 GET_MODE_NAME (vd
->e
[i
].mode
), vd
->e
[i
].oldest_regno
,
1253 vd
->e
[i
].next_regno
);
1259 const pass_data pass_data_cprop_hardreg
=
1261 RTL_PASS
, /* type */
1262 "cprop_hardreg", /* name */
1263 OPTGROUP_NONE
, /* optinfo_flags */
1264 TV_CPROP_REGISTERS
, /* tv_id */
1265 0, /* properties_required */
1266 0, /* properties_provided */
1267 0, /* properties_destroyed */
1268 0, /* todo_flags_start */
1269 TODO_df_finish
, /* todo_flags_finish */
1272 class pass_cprop_hardreg
: public rtl_opt_pass
1275 pass_cprop_hardreg (gcc::context
*ctxt
)
1276 : rtl_opt_pass (pass_data_cprop_hardreg
, ctxt
)
1279 /* opt_pass methods: */
1280 virtual bool gate (function
*)
1282 return (optimize
> 0 && (flag_cprop_registers
));
1285 virtual unsigned int execute (function
*);
1287 }; // class pass_cprop_hardreg
1290 cprop_hardreg_bb (basic_block bb
, struct value_data
*all_vd
, sbitmap visited
)
1292 bitmap_set_bit (visited
, bb
->index
);
1294 /* If a block has a single predecessor, that we've already
1295 processed, begin with the value data that was live at
1296 the end of the predecessor block. */
1297 /* ??? Ought to use more intelligent queuing of blocks. */
1298 if (single_pred_p (bb
)
1299 && bitmap_bit_p (visited
, single_pred (bb
)->index
)
1300 && ! (single_pred_edge (bb
)->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
)))
1302 all_vd
[bb
->index
] = all_vd
[single_pred (bb
)->index
];
1303 if (all_vd
[bb
->index
].n_debug_insn_changes
)
1307 for (regno
= 0; regno
< FIRST_PSEUDO_REGISTER
; regno
++)
1309 if (all_vd
[bb
->index
].e
[regno
].debug_insn_changes
)
1311 struct queued_debug_insn_change
*cur
;
1312 for (cur
= all_vd
[bb
->index
].e
[regno
].debug_insn_changes
;
1313 cur
; cur
= cur
->next
)
1314 --all_vd
[bb
->index
].n_debug_insn_changes
;
1315 all_vd
[bb
->index
].e
[regno
].debug_insn_changes
= NULL
;
1316 if (all_vd
[bb
->index
].n_debug_insn_changes
== 0)
1323 init_value_data (all_vd
+ bb
->index
);
1325 return copyprop_hardreg_forward_1 (bb
, all_vd
+ bb
->index
);
1329 cprop_hardreg_debug (function
*fun
, struct value_data
*all_vd
)
1333 FOR_EACH_BB_FN (bb
, fun
)
1334 if (all_vd
[bb
->index
].n_debug_insn_changes
)
1339 live
= df_get_live_out (bb
);
1340 for (regno
= 0; regno
< FIRST_PSEUDO_REGISTER
; regno
++)
1341 if (all_vd
[bb
->index
].e
[regno
].debug_insn_changes
)
1343 if (REGNO_REG_SET_P (live
, regno
))
1344 apply_debug_insn_changes (all_vd
+ bb
->index
, regno
);
1346 struct queued_debug_insn_change
*cur
;
1347 for (cur
= all_vd
[bb
->index
].e
[regno
].debug_insn_changes
;
1348 cur
; cur
= cur
->next
)
1349 --all_vd
[bb
->index
].n_debug_insn_changes
;
1350 all_vd
[bb
->index
].e
[regno
].debug_insn_changes
= NULL
;
1351 if (all_vd
[bb
->index
].n_debug_insn_changes
== 0)
1356 queued_debug_insn_change_pool
.release ();
1360 pass_cprop_hardreg::execute (function
*fun
)
1362 struct value_data
*all_vd
;
1365 all_vd
= XNEWVEC (struct value_data
, last_basic_block_for_fn (fun
));
1367 auto_sbitmap
visited (last_basic_block_for_fn (fun
));
1368 bitmap_clear (visited
);
1370 auto_vec
<int> worklist
;
1371 bool any_debug_changes
= false;
1373 /* We need accurate notes. Earlier passes such as if-conversion may
1374 leave notes in an inconsistent state. */
1375 df_note_add_problem ();
1378 /* It is tempting to set DF_LR_RUN_DCE, but DCE may choose to delete
1379 an insn and this pass would not have visibility into the removal.
1380 This pass would then potentially use the source of that
1381 INSN for propagation purposes, generating invalid code.
1383 So we just ask for updated notes and handle trivial deletions
1384 within this pass where we can update this passes internal
1385 data structures appropriately. */
1386 df_set_flags (DF_DEFER_INSN_RESCAN
);
1388 FOR_EACH_BB_FN (bb
, fun
)
1390 if (cprop_hardreg_bb (bb
, all_vd
, visited
))
1391 worklist
.safe_push (bb
->index
);
1392 if (all_vd
[bb
->index
].n_debug_insn_changes
)
1393 any_debug_changes
= true;
1396 /* We must call df_analyze here unconditionally to ensure that the
1397 REG_UNUSED and REG_DEAD notes are consistent with and without -g. */
1400 if (MAY_HAVE_DEBUG_BIND_INSNS
&& any_debug_changes
)
1401 cprop_hardreg_debug (fun
, all_vd
);
1403 /* Second pass if we've changed anything, only for the bbs where we have
1404 changed anything though. */
1405 if (!worklist
.is_empty ())
1410 any_debug_changes
= false;
1411 bitmap_clear (visited
);
1412 FOR_EACH_VEC_ELT (worklist
, i
, index
)
1414 bb
= BASIC_BLOCK_FOR_FN (fun
, index
);
1415 cprop_hardreg_bb (bb
, all_vd
, visited
);
1416 if (all_vd
[bb
->index
].n_debug_insn_changes
)
1417 any_debug_changes
= true;
1421 if (MAY_HAVE_DEBUG_BIND_INSNS
&& any_debug_changes
)
1422 cprop_hardreg_debug (fun
, all_vd
);
1432 make_pass_cprop_hardreg (gcc::context
*ctxt
)
1434 return new pass_cprop_hardreg (ctxt
);