1 /* Copy propagation on hard registers for the GNU compiler.
2 Copyright (C) 2000-2019 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
;
241 gcc_assert (GET_CODE (set
) != CLOBBER_HIGH
|| REG_P (x
));
243 if (GET_CODE (set
) == CLOBBER
244 || (GET_CODE (set
) == CLOBBER_HIGH
245 && reg_is_clobbered_by_clobber_high (x
, XEXP (set
, 0))))
249 /* A structure passed as data to kill_set_value through note_stores. */
250 struct kill_set_value_data
252 struct value_data
*vd
;
256 /* Called through note_stores. If X is set, not clobbered, kill its
257 current value and install it as the root of its own value list. */
260 kill_set_value (rtx x
, const_rtx set
, void *data
)
262 struct kill_set_value_data
*ksvd
= (struct kill_set_value_data
*) data
;
263 if (rtx_equal_p (x
, ksvd
->ignore_set_reg
))
266 gcc_assert (GET_CODE (set
) != CLOBBER_HIGH
|| REG_P (x
));
267 if (GET_CODE (set
) != CLOBBER
&& GET_CODE (set
) != CLOBBER_HIGH
)
269 kill_value (x
, ksvd
->vd
);
271 set_value_regno (REGNO (x
), GET_MODE (x
), ksvd
->vd
);
275 /* Kill any register used in X as the base of an auto-increment expression,
276 and install that register as the root of its own value list. */
279 kill_autoinc_value (rtx_insn
*insn
, struct value_data
*vd
)
281 subrtx_iterator::array_type array
;
282 FOR_EACH_SUBRTX (iter
, array
, PATTERN (insn
), NONCONST
)
285 if (GET_RTX_CLASS (GET_CODE (x
)) == RTX_AUTOINC
)
289 set_value_regno (REGNO (x
), GET_MODE (x
), vd
);
290 iter
.skip_subrtxes ();
295 /* Assert that SRC has been copied to DEST. Adjust the data structures
296 to reflect that SRC contains an older copy of the shared value. */
299 copy_value (rtx dest
, rtx src
, struct value_data
*vd
)
301 unsigned int dr
= REGNO (dest
);
302 unsigned int sr
= REGNO (src
);
306 /* ??? At present, it's possible to see noop sets. It'd be nice if
307 this were cleaned up beforehand... */
311 /* Do not propagate copies to the stack pointer, as that can leave
312 memory accesses with no scheduling dependency on the stack update. */
313 if (dr
== STACK_POINTER_REGNUM
)
316 /* Likewise with the frame pointer, if we're using one. */
317 if (frame_pointer_needed
&& dr
== HARD_FRAME_POINTER_REGNUM
)
320 /* Do not propagate copies to fixed or global registers, patterns
321 can be relying to see particular fixed register or users can
322 expect the chosen global register in asm. */
323 if (fixed_regs
[dr
] || global_regs
[dr
])
326 /* If SRC and DEST overlap, don't record anything. */
327 dn
= REG_NREGS (dest
);
328 sn
= REG_NREGS (src
);
329 if ((dr
> sr
&& dr
< sr
+ sn
)
330 || (sr
> dr
&& sr
< dr
+ dn
))
333 /* If SRC had no assigned mode (i.e. we didn't know it was live)
334 assign it now and assume the value came from an input argument
336 if (vd
->e
[sr
].mode
== VOIDmode
)
337 set_value_regno (sr
, vd
->e
[dr
].mode
, vd
);
339 /* If we are narrowing the input to a smaller number of hard regs,
340 and it is in big endian, we are really extracting a high part.
341 Since we generally associate a low part of a value with the value itself,
342 we must not do the same for the high part.
343 Note we can still get low parts for the same mode combination through
344 a two-step copy involving differently sized hard regs.
345 Assume hard regs fr* are 32 bits each, while r* are 64 bits each:
346 (set (reg:DI r0) (reg:DI fr0))
347 (set (reg:SI fr2) (reg:SI r0))
348 loads the low part of (reg:DI fr0) - i.e. fr1 - into fr2, while:
349 (set (reg:SI fr2) (reg:SI fr0))
350 loads the high part of (reg:DI fr0) into fr2.
352 We can't properly represent the latter case in our tables, so don't
353 record anything then. */
354 else if (sn
< hard_regno_nregs (sr
, vd
->e
[sr
].mode
)
355 && maybe_ne (subreg_lowpart_offset (GET_MODE (dest
),
356 vd
->e
[sr
].mode
), 0U))
359 /* If SRC had been assigned a mode narrower than the copy, we can't
360 link DEST into the chain, because not all of the pieces of the
361 copy came from oldest_regno. */
362 else if (sn
> hard_regno_nregs (sr
, vd
->e
[sr
].mode
))
365 /* Link DR at the end of the value chain used by SR. */
367 vd
->e
[dr
].oldest_regno
= vd
->e
[sr
].oldest_regno
;
369 for (i
= sr
; vd
->e
[i
].next_regno
!= INVALID_REGNUM
; i
= vd
->e
[i
].next_regno
)
371 vd
->e
[i
].next_regno
= dr
;
374 validate_value_data (vd
);
377 /* Return true if a mode change from ORIG to NEW is allowed for REGNO. */
380 mode_change_ok (machine_mode orig_mode
, machine_mode new_mode
,
381 unsigned int regno ATTRIBUTE_UNUSED
)
383 if (partial_subreg_p (orig_mode
, new_mode
))
386 return REG_CAN_CHANGE_MODE_P (regno
, orig_mode
, new_mode
);
389 /* Register REGNO was originally set in ORIG_MODE. It - or a copy of it -
390 was copied in COPY_MODE to COPY_REGNO, and then COPY_REGNO was accessed
392 Return a NEW_MODE rtx for REGNO if that's OK, otherwise return NULL_RTX. */
395 maybe_mode_change (machine_mode orig_mode
, machine_mode copy_mode
,
396 machine_mode new_mode
, unsigned int regno
,
397 unsigned int copy_regno ATTRIBUTE_UNUSED
)
399 if (partial_subreg_p (copy_mode
, orig_mode
)
400 && partial_subreg_p (copy_mode
, new_mode
))
403 /* Avoid creating multiple copies of the stack pointer. Some ports
404 assume there is one and only one stack pointer.
406 It's unclear if we need to do the same for other special registers. */
407 if (regno
== STACK_POINTER_REGNUM
)
410 if (orig_mode
== new_mode
)
411 return gen_raw_REG (new_mode
, regno
);
412 else if (mode_change_ok (orig_mode
, new_mode
, regno
))
414 int copy_nregs
= hard_regno_nregs (copy_regno
, copy_mode
);
415 int use_nregs
= hard_regno_nregs (copy_regno
, new_mode
);
416 poly_uint64 bytes_per_reg
;
417 if (!can_div_trunc_p (GET_MODE_SIZE (copy_mode
),
418 copy_nregs
, &bytes_per_reg
))
420 poly_uint64 copy_offset
= bytes_per_reg
* (copy_nregs
- use_nregs
);
422 = subreg_size_lowpart_offset (GET_MODE_SIZE (new_mode
) + copy_offset
,
423 GET_MODE_SIZE (orig_mode
));
424 regno
+= subreg_regno_offset (regno
, orig_mode
, offset
, new_mode
);
425 if (targetm
.hard_regno_mode_ok (regno
, new_mode
))
426 return gen_raw_REG (new_mode
, regno
);
431 /* Find the oldest copy of the value contained in REGNO that is in
432 register class CL and has mode MODE. If found, return an rtx
433 of that oldest register, otherwise return NULL. */
436 find_oldest_value_reg (enum reg_class cl
, rtx reg
, struct value_data
*vd
)
438 unsigned int regno
= REGNO (reg
);
439 machine_mode mode
= GET_MODE (reg
);
442 gcc_assert (regno
< FIRST_PSEUDO_REGISTER
);
444 /* If we are accessing REG in some mode other that what we set it in,
445 make sure that the replacement is valid. In particular, consider
446 (set (reg:DI r11) (...))
447 (set (reg:SI r9) (reg:SI r11))
448 (set (reg:SI r10) (...))
449 (set (...) (reg:DI r9))
450 Replacing r9 with r11 is invalid. */
451 if (mode
!= vd
->e
[regno
].mode
452 && REG_NREGS (reg
) > hard_regno_nregs (regno
, vd
->e
[regno
].mode
))
455 for (i
= vd
->e
[regno
].oldest_regno
; i
!= regno
; i
= vd
->e
[i
].next_regno
)
457 machine_mode oldmode
= vd
->e
[i
].mode
;
460 if (!in_hard_reg_set_p (reg_class_contents
[cl
], mode
, i
))
463 new_rtx
= maybe_mode_change (oldmode
, vd
->e
[regno
].mode
, mode
, i
, regno
);
466 ORIGINAL_REGNO (new_rtx
) = ORIGINAL_REGNO (reg
);
467 REG_ATTRS (new_rtx
) = REG_ATTRS (reg
);
468 REG_POINTER (new_rtx
) = REG_POINTER (reg
);
476 /* If possible, replace the register at *LOC with the oldest register
477 in register class CL. Return true if successfully replaced. */
480 replace_oldest_value_reg (rtx
*loc
, enum reg_class cl
, rtx_insn
*insn
,
481 struct value_data
*vd
)
483 rtx new_rtx
= find_oldest_value_reg (cl
, *loc
, vd
);
484 if (new_rtx
&& (!DEBUG_INSN_P (insn
) || !skip_debug_insn_p
))
486 if (DEBUG_INSN_P (insn
))
488 struct queued_debug_insn_change
*change
;
491 fprintf (dump_file
, "debug_insn %u: queued replacing reg %u with %u\n",
492 INSN_UID (insn
), REGNO (*loc
), REGNO (new_rtx
));
494 change
= queued_debug_insn_change_pool
.allocate ();
495 change
->next
= vd
->e
[REGNO (new_rtx
)].debug_insn_changes
;
498 change
->new_rtx
= new_rtx
;
499 vd
->e
[REGNO (new_rtx
)].debug_insn_changes
= change
;
500 ++vd
->n_debug_insn_changes
;
504 fprintf (dump_file
, "insn %u: replaced reg %u with %u\n",
505 INSN_UID (insn
), REGNO (*loc
), REGNO (new_rtx
));
507 validate_change (insn
, loc
, new_rtx
, 1);
513 /* Similar to replace_oldest_value_reg, but *LOC contains an address.
514 Adapted from find_reloads_address_1. CL is INDEX_REG_CLASS or
515 BASE_REG_CLASS depending on how the register is being considered. */
518 replace_oldest_value_addr (rtx
*loc
, enum reg_class cl
,
519 machine_mode mode
, addr_space_t as
,
520 rtx_insn
*insn
, struct value_data
*vd
)
523 RTX_CODE code
= GET_CODE (x
);
526 bool changed
= false;
531 if (DEBUG_INSN_P (insn
))
535 rtx orig_op0
= XEXP (x
, 0);
536 rtx orig_op1
= XEXP (x
, 1);
537 RTX_CODE code0
= GET_CODE (orig_op0
);
538 RTX_CODE code1
= GET_CODE (orig_op1
);
543 enum rtx_code index_code
= SCRATCH
;
545 if (GET_CODE (op0
) == SUBREG
)
547 op0
= SUBREG_REG (op0
);
548 code0
= GET_CODE (op0
);
551 if (GET_CODE (op1
) == SUBREG
)
553 op1
= SUBREG_REG (op1
);
554 code1
= GET_CODE (op1
);
557 if (code0
== MULT
|| code0
== SIGN_EXTEND
|| code0
== TRUNCATE
558 || code0
== ZERO_EXTEND
|| code1
== MEM
)
562 index_code
= GET_CODE (*locI
);
564 else if (code1
== MULT
|| code1
== SIGN_EXTEND
|| code1
== TRUNCATE
565 || code1
== ZERO_EXTEND
|| code0
== MEM
)
569 index_code
= GET_CODE (*locI
);
571 else if (code0
== CONST_INT
|| code0
== CONST
572 || code0
== SYMBOL_REF
|| code0
== LABEL_REF
)
575 index_code
= GET_CODE (XEXP (x
, 0));
577 else if (code1
== CONST_INT
|| code1
== CONST
578 || code1
== SYMBOL_REF
|| code1
== LABEL_REF
)
581 index_code
= GET_CODE (XEXP (x
, 1));
583 else if (code0
== REG
&& code1
== REG
)
586 unsigned regno0
= REGNO (op0
), regno1
= REGNO (op1
);
588 if (REGNO_OK_FOR_INDEX_P (regno1
)
589 && regno_ok_for_base_p (regno0
, mode
, as
, PLUS
, REG
))
591 else if (REGNO_OK_FOR_INDEX_P (regno0
)
592 && regno_ok_for_base_p (regno1
, mode
, as
, PLUS
, REG
))
594 else if (regno_ok_for_base_p (regno0
, mode
, as
, PLUS
, REG
)
595 || REGNO_OK_FOR_INDEX_P (regno1
))
597 else if (regno_ok_for_base_p (regno1
, mode
, as
, PLUS
, REG
))
602 locI
= &XEXP (x
, index_op
);
603 locB
= &XEXP (x
, !index_op
);
604 index_code
= GET_CODE (*locI
);
606 else if (code0
== REG
)
610 index_code
= GET_CODE (*locI
);
612 else if (code1
== REG
)
616 index_code
= GET_CODE (*locI
);
620 changed
|= replace_oldest_value_addr (locI
, INDEX_REG_CLASS
,
623 changed
|= replace_oldest_value_addr (locB
,
624 base_reg_class (mode
, as
, PLUS
,
639 return replace_oldest_value_mem (x
, insn
, vd
);
642 return replace_oldest_value_reg (loc
, cl
, insn
, vd
);
648 fmt
= GET_RTX_FORMAT (code
);
649 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
652 changed
|= replace_oldest_value_addr (&XEXP (x
, i
), cl
, mode
, as
,
654 else if (fmt
[i
] == 'E')
655 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
656 changed
|= replace_oldest_value_addr (&XVECEXP (x
, i
, j
), cl
,
663 /* Similar to replace_oldest_value_reg, but X contains a memory. */
666 replace_oldest_value_mem (rtx x
, rtx_insn
*insn
, struct value_data
*vd
)
670 if (DEBUG_INSN_P (insn
))
673 cl
= base_reg_class (GET_MODE (x
), MEM_ADDR_SPACE (x
), MEM
, SCRATCH
);
675 return replace_oldest_value_addr (&XEXP (x
, 0), cl
,
676 GET_MODE (x
), MEM_ADDR_SPACE (x
),
680 /* Apply all queued updates for DEBUG_INSNs that change some reg to
684 apply_debug_insn_changes (struct value_data
*vd
, unsigned int regno
)
686 struct queued_debug_insn_change
*change
;
687 rtx_insn
*last_insn
= vd
->e
[regno
].debug_insn_changes
->insn
;
689 for (change
= vd
->e
[regno
].debug_insn_changes
;
691 change
= change
->next
)
693 if (last_insn
!= change
->insn
)
695 apply_change_group ();
696 last_insn
= change
->insn
;
698 validate_change (change
->insn
, change
->loc
, change
->new_rtx
, 1);
700 apply_change_group ();
703 /* Called via note_uses, for all used registers in a real insn
704 apply DEBUG_INSN changes that change registers to the used
708 cprop_find_used_regs (rtx
*loc
, void *data
)
710 struct value_data
*const vd
= (struct value_data
*) data
;
711 subrtx_iterator::array_type array
;
712 FOR_EACH_SUBRTX (iter
, array
, *loc
, NONCONST
)
717 unsigned int regno
= REGNO (x
);
718 if (vd
->e
[regno
].debug_insn_changes
)
720 apply_debug_insn_changes (vd
, regno
);
721 free_debug_insn_changes (vd
, regno
);
727 /* Apply clobbers of INSN in PATTERN and C_I_F_U to value_data VD. */
730 kill_clobbered_values (rtx_insn
*insn
, struct value_data
*vd
)
732 note_stores (insn
, kill_clobbered_value
, vd
);
735 /* Perform the forward copy propagation on basic block BB. */
738 copyprop_hardreg_forward_1 (basic_block bb
, struct value_data
*vd
)
740 bool anything_changed
= false;
741 rtx_insn
*insn
, *next
;
743 for (insn
= BB_HEAD (bb
); ; insn
= next
)
745 int n_ops
, i
, predicated
;
746 bool is_asm
, any_replacements
;
749 bool changed
= false;
750 struct kill_set_value_data ksvd
;
752 next
= NEXT_INSN (insn
);
753 if (!NONDEBUG_INSN_P (insn
))
755 if (DEBUG_BIND_INSN_P (insn
))
757 rtx loc
= INSN_VAR_LOCATION_LOC (insn
);
758 if (!VAR_LOC_UNKNOWN_P (loc
))
759 replace_oldest_value_addr (&INSN_VAR_LOCATION_LOC (insn
),
760 ALL_REGS
, GET_MODE (loc
),
761 ADDR_SPACE_GENERIC
, insn
, vd
);
764 if (insn
== BB_END (bb
))
770 set
= single_set (insn
);
772 /* Detect noop sets and remove them before processing side effects. */
773 if (set
&& REG_P (SET_DEST (set
)) && REG_P (SET_SRC (set
)))
775 unsigned int regno
= REGNO (SET_SRC (set
));
776 rtx r1
= find_oldest_value_reg (REGNO_REG_CLASS (regno
),
778 rtx r2
= find_oldest_value_reg (REGNO_REG_CLASS (regno
),
780 if (rtx_equal_p (r1
? r1
: SET_DEST (set
), r2
? r2
: SET_SRC (set
)))
782 bool last
= insn
== BB_END (bb
);
790 /* Detect obviously dead sets (via REG_UNUSED notes) and remove them. */
792 && !RTX_FRAME_RELATED_P (insn
)
794 && find_reg_note (insn
, REG_UNUSED
, SET_DEST (set
))
795 && !side_effects_p (SET_SRC (set
))
796 && !side_effects_p (SET_DEST (set
)))
798 bool last
= insn
== BB_END (bb
);
806 extract_constrain_insn (insn
);
807 preprocess_constraints (insn
);
808 const operand_alternative
*op_alt
= which_op_alt ();
809 n_ops
= recog_data
.n_operands
;
810 is_asm
= asm_noperands (PATTERN (insn
)) >= 0;
812 /* Simplify the code below by promoting OP_OUT to OP_INOUT
813 in predicated instructions. */
815 predicated
= GET_CODE (PATTERN (insn
)) == COND_EXEC
;
816 for (i
= 0; i
< n_ops
; ++i
)
818 int matches
= op_alt
[i
].matches
;
819 if (matches
>= 0 || op_alt
[i
].matched
>= 0
820 || (predicated
&& recog_data
.operand_type
[i
] == OP_OUT
))
821 recog_data
.operand_type
[i
] = OP_INOUT
;
824 /* Apply changes to earlier DEBUG_INSNs if possible. */
825 if (vd
->n_debug_insn_changes
)
826 note_uses (&PATTERN (insn
), cprop_find_used_regs
, vd
);
828 /* For each earlyclobber operand, zap the value data. */
829 for (i
= 0; i
< n_ops
; i
++)
830 if (op_alt
[i
].earlyclobber
)
831 kill_value (recog_data
.operand
[i
], vd
);
833 /* Within asms, a clobber cannot overlap inputs or outputs.
834 I wouldn't think this were true for regular insns, but
835 scan_rtx treats them like that... */
836 kill_clobbered_values (insn
, vd
);
838 /* Kill all auto-incremented values. */
839 /* ??? REG_INC is useless, since stack pushes aren't done that way. */
840 kill_autoinc_value (insn
, vd
);
842 /* Kill all early-clobbered operands. */
843 for (i
= 0; i
< n_ops
; i
++)
844 if (op_alt
[i
].earlyclobber
)
845 kill_value (recog_data
.operand
[i
], vd
);
847 /* If we have dead sets in the insn, then we need to note these as we
849 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
851 if (REG_NOTE_KIND (link
) == REG_UNUSED
)
853 kill_value (XEXP (link
, 0), vd
);
854 /* Furthermore, if the insn looked like a single-set,
855 but the dead store kills the source value of that
856 set, then we can no-longer use the plain move
857 special case below. */
859 && reg_overlap_mentioned_p (XEXP (link
, 0), SET_SRC (set
)))
863 /* We need to keep CFI info correct, and the same on all paths,
864 so we cannot normally replace the registers REG_CFA_REGISTER
866 if (REG_NOTE_KIND (link
) == REG_CFA_REGISTER
)
867 goto did_replacement
;
870 /* Special-case plain move instructions, since we may well
871 be able to do the move from a different register class. */
872 if (set
&& REG_P (SET_SRC (set
)))
874 rtx src
= SET_SRC (set
);
875 unsigned int regno
= REGNO (src
);
876 machine_mode mode
= GET_MODE (src
);
880 /* If we are accessing SRC in some mode other that what we
881 set it in, make sure that the replacement is valid. */
882 if (mode
!= vd
->e
[regno
].mode
)
885 > hard_regno_nregs (regno
, vd
->e
[regno
].mode
))
886 goto no_move_special_case
;
888 /* And likewise, if we are narrowing on big endian the transformation
890 if (REG_NREGS (src
) < hard_regno_nregs (regno
, vd
->e
[regno
].mode
)
891 && maybe_ne (subreg_lowpart_offset (mode
,
892 vd
->e
[regno
].mode
), 0U))
893 goto no_move_special_case
;
896 /* If the destination is also a register, try to find a source
897 register in the same class. */
898 if (REG_P (SET_DEST (set
)))
900 new_rtx
= find_oldest_value_reg (REGNO_REG_CLASS (regno
),
903 if (new_rtx
&& validate_change (insn
, &SET_SRC (set
), new_rtx
, 0))
907 "insn %u: replaced reg %u with %u\n",
908 INSN_UID (insn
), regno
, REGNO (new_rtx
));
910 goto did_replacement
;
912 /* We need to re-extract as validate_change clobbers
914 extract_constrain_insn (insn
);
915 preprocess_constraints (insn
);
918 /* Otherwise, try all valid registers and see if its valid. */
919 for (i
= vd
->e
[regno
].oldest_regno
; i
!= regno
;
920 i
= vd
->e
[i
].next_regno
)
922 new_rtx
= maybe_mode_change (vd
->e
[i
].mode
, vd
->e
[regno
].mode
,
924 if (new_rtx
!= NULL_RTX
)
926 if (validate_change (insn
, &SET_SRC (set
), new_rtx
, 0))
928 ORIGINAL_REGNO (new_rtx
) = ORIGINAL_REGNO (src
);
929 REG_ATTRS (new_rtx
) = REG_ATTRS (src
);
930 REG_POINTER (new_rtx
) = REG_POINTER (src
);
933 "insn %u: replaced reg %u with %u\n",
934 INSN_UID (insn
), regno
, REGNO (new_rtx
));
936 goto did_replacement
;
938 /* We need to re-extract as validate_change clobbers
940 extract_constrain_insn (insn
);
941 preprocess_constraints (insn
);
945 no_move_special_case
:
947 any_replacements
= false;
949 /* For each input operand, replace a hard register with the
950 eldest live copy that's in an appropriate register class. */
951 for (i
= 0; i
< n_ops
; i
++)
953 bool replaced
= false;
955 /* Don't scan match_operand here, since we've no reg class
956 information to pass down. Any operands that we could
957 substitute in will be represented elsewhere. */
958 if (recog_data
.constraints
[i
][0] == '\0')
961 /* Don't replace in asms intentionally referencing hard regs. */
962 if (is_asm
&& REG_P (recog_data
.operand
[i
])
963 && (REGNO (recog_data
.operand
[i
])
964 == ORIGINAL_REGNO (recog_data
.operand
[i
])))
967 if (recog_data
.operand_type
[i
] == OP_IN
)
969 if (op_alt
[i
].is_address
)
971 = replace_oldest_value_addr (recog_data
.operand_loc
[i
],
972 alternative_class (op_alt
, i
),
973 VOIDmode
, ADDR_SPACE_GENERIC
,
975 else if (REG_P (recog_data
.operand
[i
]))
977 = replace_oldest_value_reg (recog_data
.operand_loc
[i
],
978 alternative_class (op_alt
, i
),
980 else if (MEM_P (recog_data
.operand
[i
]))
981 replaced
= replace_oldest_value_mem (recog_data
.operand
[i
],
984 else if (MEM_P (recog_data
.operand
[i
]))
985 replaced
= replace_oldest_value_mem (recog_data
.operand
[i
],
988 /* If we performed any replacement, update match_dups. */
994 new_rtx
= *recog_data
.operand_loc
[i
];
995 recog_data
.operand
[i
] = new_rtx
;
996 for (j
= 0; j
< recog_data
.n_dups
; j
++)
997 if (recog_data
.dup_num
[j
] == i
)
998 validate_unshare_change (insn
, recog_data
.dup_loc
[j
], new_rtx
, 1);
1000 any_replacements
= true;
1004 if (any_replacements
)
1006 if (! apply_change_group ())
1010 "insn %u: reg replacements not verified\n",
1020 anything_changed
= true;
1022 /* If something changed, perhaps further changes to earlier
1023 DEBUG_INSNs can be applied. */
1024 if (vd
->n_debug_insn_changes
)
1025 note_uses (&PATTERN (insn
), cprop_find_used_regs
, vd
);
1026 df_insn_rescan (insn
);
1030 ksvd
.ignore_set_reg
= NULL_RTX
;
1032 /* Clobber call-clobbered registers. */
1035 unsigned int set_regno
= INVALID_REGNUM
;
1036 unsigned int set_nregs
= 0;
1040 for (exp
= CALL_INSN_FUNCTION_USAGE (insn
); exp
; exp
= XEXP (exp
, 1))
1042 rtx x
= XEXP (exp
, 0);
1043 if (GET_CODE (x
) == SET
)
1045 rtx dest
= SET_DEST (x
);
1046 kill_value (dest
, vd
);
1047 set_value_regno (REGNO (dest
), GET_MODE (dest
), vd
);
1048 copy_value (dest
, SET_SRC (x
), vd
);
1049 ksvd
.ignore_set_reg
= dest
;
1050 set_regno
= REGNO (dest
);
1051 set_nregs
= REG_NREGS (dest
);
1056 function_abi callee_abi
= insn_callee_abi (insn
);
1057 for (regno
= 0; regno
< FIRST_PSEUDO_REGISTER
; regno
++)
1058 if (vd
->e
[regno
].mode
!= VOIDmode
1059 && callee_abi
.clobbers_reg_p (vd
->e
[regno
].mode
, regno
)
1060 && (regno
< set_regno
|| regno
>= set_regno
+ set_nregs
))
1061 kill_value_regno (regno
, 1, vd
);
1063 /* If SET was seen in CALL_INSN_FUNCTION_USAGE, and SET_SRC
1064 of the SET isn't clobbered by CALLEE_ABI, but instead among
1065 CLOBBERs on the CALL_INSN, we could wrongly assume the
1066 value in it is still live. */
1067 if (ksvd
.ignore_set_reg
)
1068 kill_clobbered_values (insn
, vd
);
1072 && REG_P (SET_DEST (set
))
1073 && REG_P (SET_SRC (set
)));
1074 bool noop_p
= (copy_p
1075 && rtx_equal_p (SET_DEST (set
), SET_SRC (set
)));
1077 /* If a noop move is using narrower mode than we have recorded,
1078 we need to either remove the noop move, or kill_set_value. */
1080 && partial_subreg_p (GET_MODE (SET_DEST (set
)),
1081 vd
->e
[REGNO (SET_DEST (set
))].mode
))
1083 if (noop_move_p (insn
))
1085 bool last
= insn
== BB_END (bb
);
1096 /* Notice stores. */
1097 note_stores (insn
, kill_set_value
, &ksvd
);
1099 /* Notice copies. */
1102 df_insn_rescan (insn
);
1103 copy_value (SET_DEST (set
), SET_SRC (set
), vd
);
1107 if (insn
== BB_END (bb
))
1111 return anything_changed
;
1114 /* Dump the value chain data to stderr. */
1117 debug_value_data (struct value_data
*vd
)
1122 CLEAR_HARD_REG_SET (set
);
1124 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1125 if (vd
->e
[i
].oldest_regno
== i
)
1127 if (vd
->e
[i
].mode
== VOIDmode
)
1129 if (vd
->e
[i
].next_regno
!= INVALID_REGNUM
)
1130 fprintf (stderr
, "[%u] Bad next_regno for empty chain (%u)\n",
1131 i
, vd
->e
[i
].next_regno
);
1135 SET_HARD_REG_BIT (set
, i
);
1136 fprintf (stderr
, "[%u %s] ", i
, GET_MODE_NAME (vd
->e
[i
].mode
));
1138 for (j
= vd
->e
[i
].next_regno
;
1139 j
!= INVALID_REGNUM
;
1140 j
= vd
->e
[j
].next_regno
)
1142 if (TEST_HARD_REG_BIT (set
, j
))
1144 fprintf (stderr
, "[%u] Loop in regno chain\n", j
);
1148 if (vd
->e
[j
].oldest_regno
!= i
)
1150 fprintf (stderr
, "[%u] Bad oldest_regno (%u)\n",
1151 j
, vd
->e
[j
].oldest_regno
);
1154 SET_HARD_REG_BIT (set
, j
);
1155 fprintf (stderr
, "[%u %s] ", j
, GET_MODE_NAME (vd
->e
[j
].mode
));
1157 fputc ('\n', stderr
);
1160 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1161 if (! TEST_HARD_REG_BIT (set
, i
)
1162 && (vd
->e
[i
].mode
!= VOIDmode
1163 || vd
->e
[i
].oldest_regno
!= i
1164 || vd
->e
[i
].next_regno
!= INVALID_REGNUM
))
1165 fprintf (stderr
, "[%u] Non-empty reg in chain (%s %u %i)\n",
1166 i
, GET_MODE_NAME (vd
->e
[i
].mode
), vd
->e
[i
].oldest_regno
,
1167 vd
->e
[i
].next_regno
);
1170 /* Do copyprop_hardreg_forward_1 for a single basic block BB.
1171 DEBUG_INSN is skipped since we do not want to involve DF related
1172 staff as how it is handled in function pass_cprop_hardreg::execute.
1174 NOTE: Currently it is only used for shrink-wrap. Maybe extend it
1175 to handle DEBUG_INSN for other uses. */
1178 copyprop_hardreg_forward_bb_without_debug_insn (basic_block bb
)
1180 struct value_data
*vd
;
1181 vd
= XNEWVEC (struct value_data
, 1);
1182 init_value_data (vd
);
1184 skip_debug_insn_p
= true;
1185 copyprop_hardreg_forward_1 (bb
, vd
);
1187 skip_debug_insn_p
= false;
1191 validate_value_data (struct value_data
*vd
)
1196 CLEAR_HARD_REG_SET (set
);
1198 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1199 if (vd
->e
[i
].oldest_regno
== i
)
1201 if (vd
->e
[i
].mode
== VOIDmode
)
1203 if (vd
->e
[i
].next_regno
!= INVALID_REGNUM
)
1204 internal_error ("%qs: [%u] bad %<next_regno%> for empty chain (%u)",
1205 __func__
, i
, vd
->e
[i
].next_regno
);
1209 SET_HARD_REG_BIT (set
, i
);
1211 for (j
= vd
->e
[i
].next_regno
;
1212 j
!= INVALID_REGNUM
;
1213 j
= vd
->e
[j
].next_regno
)
1215 if (TEST_HARD_REG_BIT (set
, j
))
1216 internal_error ("%qs: loop in %<next_regno%> chain (%u)",
1218 if (vd
->e
[j
].oldest_regno
!= i
)
1219 internal_error ("%qs: [%u] bad %<oldest_regno%> (%u)",
1220 __func__
, j
, vd
->e
[j
].oldest_regno
);
1222 SET_HARD_REG_BIT (set
, j
);
1226 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1227 if (! TEST_HARD_REG_BIT (set
, i
)
1228 && (vd
->e
[i
].mode
!= VOIDmode
1229 || vd
->e
[i
].oldest_regno
!= i
1230 || vd
->e
[i
].next_regno
!= INVALID_REGNUM
))
1231 internal_error ("%qs: [%u] non-empty register in chain (%s %u %i)",
1233 GET_MODE_NAME (vd
->e
[i
].mode
), vd
->e
[i
].oldest_regno
,
1234 vd
->e
[i
].next_regno
);
1240 const pass_data pass_data_cprop_hardreg
=
1242 RTL_PASS
, /* type */
1243 "cprop_hardreg", /* name */
1244 OPTGROUP_NONE
, /* optinfo_flags */
1245 TV_CPROP_REGISTERS
, /* tv_id */
1246 0, /* properties_required */
1247 0, /* properties_provided */
1248 0, /* properties_destroyed */
1249 0, /* todo_flags_start */
1250 TODO_df_finish
, /* todo_flags_finish */
1253 class pass_cprop_hardreg
: public rtl_opt_pass
1256 pass_cprop_hardreg (gcc::context
*ctxt
)
1257 : rtl_opt_pass (pass_data_cprop_hardreg
, ctxt
)
1260 /* opt_pass methods: */
1261 virtual bool gate (function
*)
1263 return (optimize
> 0 && (flag_cprop_registers
));
1266 virtual unsigned int execute (function
*);
1268 }; // class pass_cprop_hardreg
1271 cprop_hardreg_bb (basic_block bb
, struct value_data
*all_vd
, sbitmap visited
)
1273 bitmap_set_bit (visited
, bb
->index
);
1275 /* If a block has a single predecessor, that we've already
1276 processed, begin with the value data that was live at
1277 the end of the predecessor block. */
1278 /* ??? Ought to use more intelligent queuing of blocks. */
1279 if (single_pred_p (bb
)
1280 && bitmap_bit_p (visited
, single_pred (bb
)->index
)
1281 && ! (single_pred_edge (bb
)->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
)))
1283 all_vd
[bb
->index
] = all_vd
[single_pred (bb
)->index
];
1284 if (all_vd
[bb
->index
].n_debug_insn_changes
)
1288 for (regno
= 0; regno
< FIRST_PSEUDO_REGISTER
; regno
++)
1290 if (all_vd
[bb
->index
].e
[regno
].debug_insn_changes
)
1292 struct queued_debug_insn_change
*cur
;
1293 for (cur
= all_vd
[bb
->index
].e
[regno
].debug_insn_changes
;
1294 cur
; cur
= cur
->next
)
1295 --all_vd
[bb
->index
].n_debug_insn_changes
;
1296 all_vd
[bb
->index
].e
[regno
].debug_insn_changes
= NULL
;
1297 if (all_vd
[bb
->index
].n_debug_insn_changes
== 0)
1304 init_value_data (all_vd
+ bb
->index
);
1306 return copyprop_hardreg_forward_1 (bb
, all_vd
+ bb
->index
);
1310 cprop_hardreg_debug (function
*fun
, struct value_data
*all_vd
)
1314 FOR_EACH_BB_FN (bb
, fun
)
1315 if (all_vd
[bb
->index
].n_debug_insn_changes
)
1320 live
= df_get_live_out (bb
);
1321 for (regno
= 0; regno
< FIRST_PSEUDO_REGISTER
; regno
++)
1322 if (all_vd
[bb
->index
].e
[regno
].debug_insn_changes
)
1324 if (REGNO_REG_SET_P (live
, regno
))
1325 apply_debug_insn_changes (all_vd
+ bb
->index
, regno
);
1327 struct queued_debug_insn_change
*cur
;
1328 for (cur
= all_vd
[bb
->index
].e
[regno
].debug_insn_changes
;
1329 cur
; cur
= cur
->next
)
1330 --all_vd
[bb
->index
].n_debug_insn_changes
;
1331 all_vd
[bb
->index
].e
[regno
].debug_insn_changes
= NULL
;
1332 if (all_vd
[bb
->index
].n_debug_insn_changes
== 0)
1337 queued_debug_insn_change_pool
.release ();
1341 pass_cprop_hardreg::execute (function
*fun
)
1343 struct value_data
*all_vd
;
1346 all_vd
= XNEWVEC (struct value_data
, last_basic_block_for_fn (fun
));
1348 auto_sbitmap
visited (last_basic_block_for_fn (fun
));
1349 bitmap_clear (visited
);
1351 auto_vec
<int> worklist
;
1352 bool any_debug_changes
= false;
1354 /* We need accurate notes. Earlier passes such as if-conversion may
1355 leave notes in an inconsistent state. */
1356 df_note_add_problem ();
1359 /* It is tempting to set DF_LR_RUN_DCE, but DCE may choose to delete
1360 an insn and this pass would not have visibility into the removal.
1361 This pass would then potentially use the source of that
1362 INSN for propagation purposes, generating invalid code.
1364 So we just ask for updated notes and handle trivial deletions
1365 within this pass where we can update this passes internal
1366 data structures appropriately. */
1367 df_set_flags (DF_DEFER_INSN_RESCAN
);
1369 FOR_EACH_BB_FN (bb
, fun
)
1371 if (cprop_hardreg_bb (bb
, all_vd
, visited
))
1372 worklist
.safe_push (bb
->index
);
1373 if (all_vd
[bb
->index
].n_debug_insn_changes
)
1374 any_debug_changes
= true;
1377 /* We must call df_analyze here unconditionally to ensure that the
1378 REG_UNUSED and REG_DEAD notes are consistent with and without -g. */
1381 if (MAY_HAVE_DEBUG_BIND_INSNS
&& any_debug_changes
)
1382 cprop_hardreg_debug (fun
, all_vd
);
1384 /* Second pass if we've changed anything, only for the bbs where we have
1385 changed anything though. */
1386 if (!worklist
.is_empty ())
1391 any_debug_changes
= false;
1392 bitmap_clear (visited
);
1393 FOR_EACH_VEC_ELT (worklist
, i
, index
)
1395 bb
= BASIC_BLOCK_FOR_FN (fun
, index
);
1396 cprop_hardreg_bb (bb
, all_vd
, visited
);
1397 if (all_vd
[bb
->index
].n_debug_insn_changes
)
1398 any_debug_changes
= true;
1402 if (MAY_HAVE_DEBUG_BIND_INSNS
&& any_debug_changes
)
1403 cprop_hardreg_debug (fun
, all_vd
);
1413 make_pass_cprop_hardreg (gcc::context
*ctxt
)
1415 return new pass_cprop_hardreg (ctxt
);