1 /* Copy propagation on hard registers for the GNU compiler.
2 Copyright (C) 2000-2014 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"
26 #include "insn-config.h"
28 #include "addresses.h"
29 #include "hard-reg-set.h"
30 #include "basic-block.h"
40 #include "diagnostic-core.h"
42 #include "tree-pass.h"
46 /* The following code does forward propagation of hard register copies.
47 The object is to eliminate as many dependencies as possible, so that
48 we have the most scheduling freedom. As a side effect, we also clean
49 up some silly register allocation decisions made by reload. This
50 code may be obsoleted by a new register allocator. */
52 /* DEBUG_INSNs aren't changed right away, as doing so might extend the
53 lifetime of a register and get the DEBUG_INSN subsequently reset.
54 So they are queued instead, and updated only when the register is
55 used in some subsequent real insn before it is set. */
56 struct queued_debug_insn_change
58 struct queued_debug_insn_change
*next
;
64 /* For each register, we have a list of registers that contain the same
65 value. The OLDEST_REGNO field points to the head of the list, and
66 the NEXT_REGNO field runs through the list. The MODE field indicates
67 what mode the data is known to be in; this field is VOIDmode when the
68 register is not known to contain valid data. */
70 struct value_data_entry
72 enum machine_mode mode
;
73 unsigned int oldest_regno
;
74 unsigned int next_regno
;
75 struct queued_debug_insn_change
*debug_insn_changes
;
80 struct value_data_entry e
[FIRST_PSEUDO_REGISTER
];
81 unsigned int max_value_regs
;
82 unsigned int n_debug_insn_changes
;
85 static alloc_pool debug_insn_changes_pool
;
86 static bool skip_debug_insn_p
;
88 static void kill_value_one_regno (unsigned, struct value_data
*);
89 static void kill_value_regno (unsigned, unsigned, struct value_data
*);
90 static void kill_value (const_rtx
, struct value_data
*);
91 static void set_value_regno (unsigned, enum machine_mode
, struct value_data
*);
92 static void init_value_data (struct value_data
*);
93 static void kill_clobbered_value (rtx
, const_rtx
, void *);
94 static void kill_set_value (rtx
, const_rtx
, void *);
95 static void copy_value (rtx
, rtx
, struct value_data
*);
96 static bool mode_change_ok (enum machine_mode
, enum machine_mode
,
98 static rtx
maybe_mode_change (enum machine_mode
, enum machine_mode
,
99 enum machine_mode
, unsigned int, unsigned int);
100 static rtx
find_oldest_value_reg (enum reg_class
, rtx
, struct value_data
*);
101 static bool replace_oldest_value_reg (rtx
*, enum reg_class
, rtx_insn
*,
102 struct value_data
*);
103 static bool replace_oldest_value_addr (rtx
*, enum reg_class
,
104 enum machine_mode
, addr_space_t
,
105 rtx_insn
*, struct value_data
*);
106 static bool replace_oldest_value_mem (rtx
, rtx_insn
*, struct value_data
*);
107 static bool copyprop_hardreg_forward_1 (basic_block
, struct value_data
*);
108 extern void debug_value_data (struct value_data
*);
109 #ifdef ENABLE_CHECKING
110 static void validate_value_data (struct value_data
*);
113 /* Free all queued updates for DEBUG_INSNs that change some reg to
117 free_debug_insn_changes (struct value_data
*vd
, unsigned int regno
)
119 struct queued_debug_insn_change
*cur
, *next
;
120 for (cur
= vd
->e
[regno
].debug_insn_changes
; cur
; cur
= next
)
123 --vd
->n_debug_insn_changes
;
124 pool_free (debug_insn_changes_pool
, cur
);
126 vd
->e
[regno
].debug_insn_changes
= NULL
;
129 /* Kill register REGNO. This involves removing it from any value
130 lists, and resetting the value mode to VOIDmode. This is only a
131 helper function; it does not handle any hard registers overlapping
135 kill_value_one_regno (unsigned int regno
, struct value_data
*vd
)
137 unsigned int i
, next
;
139 if (vd
->e
[regno
].oldest_regno
!= regno
)
141 for (i
= vd
->e
[regno
].oldest_regno
;
142 vd
->e
[i
].next_regno
!= regno
;
143 i
= vd
->e
[i
].next_regno
)
145 vd
->e
[i
].next_regno
= vd
->e
[regno
].next_regno
;
147 else if ((next
= vd
->e
[regno
].next_regno
) != INVALID_REGNUM
)
149 for (i
= next
; i
!= INVALID_REGNUM
; i
= vd
->e
[i
].next_regno
)
150 vd
->e
[i
].oldest_regno
= next
;
153 vd
->e
[regno
].mode
= VOIDmode
;
154 vd
->e
[regno
].oldest_regno
= regno
;
155 vd
->e
[regno
].next_regno
= INVALID_REGNUM
;
156 if (vd
->e
[regno
].debug_insn_changes
)
157 free_debug_insn_changes (vd
, regno
);
159 #ifdef ENABLE_CHECKING
160 validate_value_data (vd
);
164 /* Kill the value in register REGNO for NREGS, and any other registers
165 whose values overlap. */
168 kill_value_regno (unsigned int regno
, unsigned int nregs
,
169 struct value_data
*vd
)
173 /* Kill the value we're told to kill. */
174 for (j
= 0; j
< nregs
; ++j
)
175 kill_value_one_regno (regno
+ j
, vd
);
177 /* Kill everything that overlapped what we're told to kill. */
178 if (regno
< vd
->max_value_regs
)
181 j
= regno
- vd
->max_value_regs
;
182 for (; j
< regno
; ++j
)
185 if (vd
->e
[j
].mode
== VOIDmode
)
187 n
= hard_regno_nregs
[j
][vd
->e
[j
].mode
];
189 for (i
= 0; i
< n
; ++i
)
190 kill_value_one_regno (j
+ i
, vd
);
194 /* Kill X. This is a convenience function wrapping kill_value_regno
195 so that we mind the mode the register is in. */
198 kill_value (const_rtx x
, struct value_data
*vd
)
200 if (GET_CODE (x
) == SUBREG
)
202 rtx tmp
= simplify_subreg (GET_MODE (x
), SUBREG_REG (x
),
203 GET_MODE (SUBREG_REG (x
)), SUBREG_BYTE (x
));
204 x
= tmp
? tmp
: SUBREG_REG (x
);
208 unsigned int regno
= REGNO (x
);
209 unsigned int n
= hard_regno_nregs
[regno
][GET_MODE (x
)];
211 kill_value_regno (regno
, n
, vd
);
215 /* Remember that REGNO is valid in MODE. */
218 set_value_regno (unsigned int regno
, enum machine_mode mode
,
219 struct value_data
*vd
)
223 vd
->e
[regno
].mode
= mode
;
225 nregs
= hard_regno_nregs
[regno
][mode
];
226 if (nregs
> vd
->max_value_regs
)
227 vd
->max_value_regs
= nregs
;
230 /* Initialize VD such that there are no known relationships between regs. */
233 init_value_data (struct value_data
*vd
)
236 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
238 vd
->e
[i
].mode
= VOIDmode
;
239 vd
->e
[i
].oldest_regno
= i
;
240 vd
->e
[i
].next_regno
= INVALID_REGNUM
;
241 vd
->e
[i
].debug_insn_changes
= NULL
;
243 vd
->max_value_regs
= 0;
244 vd
->n_debug_insn_changes
= 0;
247 /* Called through note_stores. If X is clobbered, kill its value. */
250 kill_clobbered_value (rtx x
, const_rtx set
, void *data
)
252 struct value_data
*const vd
= (struct value_data
*) data
;
253 if (GET_CODE (set
) == CLOBBER
)
257 /* A structure passed as data to kill_set_value through note_stores. */
258 struct kill_set_value_data
260 struct value_data
*vd
;
264 /* Called through note_stores. If X is set, not clobbered, kill its
265 current value and install it as the root of its own value list. */
268 kill_set_value (rtx x
, const_rtx set
, void *data
)
270 struct kill_set_value_data
*ksvd
= (struct kill_set_value_data
*) data
;
271 if (rtx_equal_p (x
, ksvd
->ignore_set_reg
))
273 if (GET_CODE (set
) != CLOBBER
)
275 kill_value (x
, ksvd
->vd
);
277 set_value_regno (REGNO (x
), GET_MODE (x
), ksvd
->vd
);
281 /* Kill any register used in X as the base of an auto-increment expression,
282 and install that register as the root of its own value list. */
285 kill_autoinc_value (rtx insn
, struct value_data
*vd
)
287 subrtx_iterator::array_type array
;
288 FOR_EACH_SUBRTX (iter
, array
, PATTERN (insn
), NONCONST
)
291 if (GET_RTX_CLASS (GET_CODE (x
)) == RTX_AUTOINC
)
295 set_value_regno (REGNO (x
), GET_MODE (x
), vd
);
296 iter
.skip_subrtxes ();
301 /* Assert that SRC has been copied to DEST. Adjust the data structures
302 to reflect that SRC contains an older copy of the shared value. */
305 copy_value (rtx dest
, rtx src
, struct value_data
*vd
)
307 unsigned int dr
= REGNO (dest
);
308 unsigned int sr
= REGNO (src
);
312 /* ??? At present, it's possible to see noop sets. It'd be nice if
313 this were cleaned up beforehand... */
317 /* Do not propagate copies to the stack pointer, as that can leave
318 memory accesses with no scheduling dependency on the stack update. */
319 if (dr
== STACK_POINTER_REGNUM
)
322 /* Likewise with the frame pointer, if we're using one. */
323 if (frame_pointer_needed
&& dr
== HARD_FRAME_POINTER_REGNUM
)
326 /* Do not propagate copies to fixed or global registers, patterns
327 can be relying to see particular fixed register or users can
328 expect the chosen global register in asm. */
329 if (fixed_regs
[dr
] || global_regs
[dr
])
332 /* If SRC and DEST overlap, don't record anything. */
333 dn
= hard_regno_nregs
[dr
][GET_MODE (dest
)];
334 sn
= hard_regno_nregs
[sr
][GET_MODE (dest
)];
335 if ((dr
> sr
&& dr
< sr
+ sn
)
336 || (sr
> dr
&& sr
< dr
+ dn
))
339 /* If SRC had no assigned mode (i.e. we didn't know it was live)
340 assign it now and assume the value came from an input argument
342 if (vd
->e
[sr
].mode
== VOIDmode
)
343 set_value_regno (sr
, vd
->e
[dr
].mode
, vd
);
345 /* If we are narrowing the input to a smaller number of hard regs,
346 and it is in big endian, we are really extracting a high part.
347 Since we generally associate a low part of a value with the value itself,
348 we must not do the same for the high part.
349 Note we can still get low parts for the same mode combination through
350 a two-step copy involving differently sized hard regs.
351 Assume hard regs fr* are 32 bits bits each, while r* are 64 bits each:
352 (set (reg:DI r0) (reg:DI fr0))
353 (set (reg:SI fr2) (reg:SI r0))
354 loads the low part of (reg:DI fr0) - i.e. fr1 - into fr2, while:
355 (set (reg:SI fr2) (reg:SI fr0))
356 loads the high part of (reg:DI fr0) into fr2.
358 We can't properly represent the latter case in our tables, so don't
359 record anything then. */
360 else if (sn
< (unsigned int) hard_regno_nregs
[sr
][vd
->e
[sr
].mode
]
361 && (GET_MODE_SIZE (vd
->e
[sr
].mode
) > UNITS_PER_WORD
362 ? WORDS_BIG_ENDIAN
: BYTES_BIG_ENDIAN
))
365 /* If SRC had been assigned a mode narrower than the copy, we can't
366 link DEST into the chain, because not all of the pieces of the
367 copy came from oldest_regno. */
368 else if (sn
> (unsigned int) hard_regno_nregs
[sr
][vd
->e
[sr
].mode
])
371 /* Link DR at the end of the value chain used by SR. */
373 vd
->e
[dr
].oldest_regno
= vd
->e
[sr
].oldest_regno
;
375 for (i
= sr
; vd
->e
[i
].next_regno
!= INVALID_REGNUM
; i
= vd
->e
[i
].next_regno
)
377 vd
->e
[i
].next_regno
= dr
;
379 #ifdef ENABLE_CHECKING
380 validate_value_data (vd
);
384 /* Return true if a mode change from ORIG to NEW is allowed for REGNO. */
387 mode_change_ok (enum machine_mode orig_mode
, enum machine_mode new_mode
,
388 unsigned int regno ATTRIBUTE_UNUSED
)
390 if (GET_MODE_SIZE (orig_mode
) < GET_MODE_SIZE (new_mode
))
393 #ifdef CANNOT_CHANGE_MODE_CLASS
394 return !REG_CANNOT_CHANGE_MODE_P (regno
, orig_mode
, new_mode
);
400 /* Register REGNO was originally set in ORIG_MODE. It - or a copy of it -
401 was copied in COPY_MODE to COPY_REGNO, and then COPY_REGNO was accessed
403 Return a NEW_MODE rtx for REGNO if that's OK, otherwise return NULL_RTX. */
406 maybe_mode_change (enum machine_mode orig_mode
, enum machine_mode copy_mode
,
407 enum machine_mode new_mode
, unsigned int regno
,
408 unsigned int copy_regno ATTRIBUTE_UNUSED
)
410 if (GET_MODE_SIZE (copy_mode
) < GET_MODE_SIZE (orig_mode
)
411 && GET_MODE_SIZE (copy_mode
) < GET_MODE_SIZE (new_mode
))
414 if (orig_mode
== new_mode
)
415 return gen_rtx_raw_REG (new_mode
, regno
);
416 else if (mode_change_ok (orig_mode
, new_mode
, regno
))
418 int copy_nregs
= hard_regno_nregs
[copy_regno
][copy_mode
];
419 int use_nregs
= hard_regno_nregs
[copy_regno
][new_mode
];
421 = GET_MODE_SIZE (copy_mode
) / copy_nregs
* (copy_nregs
- use_nregs
);
423 = GET_MODE_SIZE (orig_mode
) - GET_MODE_SIZE (new_mode
) - copy_offset
;
424 int byteoffset
= offset
% UNITS_PER_WORD
;
425 int wordoffset
= offset
- byteoffset
;
427 offset
= ((WORDS_BIG_ENDIAN
? wordoffset
: 0)
428 + (BYTES_BIG_ENDIAN
? byteoffset
: 0));
429 regno
+= subreg_regno_offset (regno
, orig_mode
, offset
, new_mode
);
430 if (HARD_REGNO_MODE_OK (regno
, new_mode
))
431 return gen_rtx_raw_REG (new_mode
, regno
);
436 /* Find the oldest copy of the value contained in REGNO that is in
437 register class CL and has mode MODE. If found, return an rtx
438 of that oldest register, otherwise return NULL. */
441 find_oldest_value_reg (enum reg_class cl
, rtx reg
, struct value_data
*vd
)
443 unsigned int regno
= REGNO (reg
);
444 enum machine_mode mode
= GET_MODE (reg
);
447 /* If we are accessing REG in some mode other that what we set it in,
448 make sure that the replacement is valid. In particular, consider
449 (set (reg:DI r11) (...))
450 (set (reg:SI r9) (reg:SI r11))
451 (set (reg:SI r10) (...))
452 (set (...) (reg:DI r9))
453 Replacing r9 with r11 is invalid. */
454 if (mode
!= vd
->e
[regno
].mode
)
456 if (hard_regno_nregs
[regno
][mode
]
457 > hard_regno_nregs
[regno
][vd
->e
[regno
].mode
])
461 for (i
= vd
->e
[regno
].oldest_regno
; i
!= regno
; i
= vd
->e
[i
].next_regno
)
463 enum machine_mode oldmode
= vd
->e
[i
].mode
;
466 if (!in_hard_reg_set_p (reg_class_contents
[cl
], mode
, i
))
469 new_rtx
= maybe_mode_change (oldmode
, vd
->e
[regno
].mode
, mode
, i
, regno
);
472 ORIGINAL_REGNO (new_rtx
) = ORIGINAL_REGNO (reg
);
473 REG_ATTRS (new_rtx
) = REG_ATTRS (reg
);
474 REG_POINTER (new_rtx
) = REG_POINTER (reg
);
482 /* If possible, replace the register at *LOC with the oldest register
483 in register class CL. Return true if successfully replaced. */
486 replace_oldest_value_reg (rtx
*loc
, enum reg_class cl
, rtx_insn
*insn
,
487 struct value_data
*vd
)
489 rtx new_rtx
= find_oldest_value_reg (cl
, *loc
, vd
);
490 if (new_rtx
&& (!DEBUG_INSN_P (insn
) || !skip_debug_insn_p
))
492 if (DEBUG_INSN_P (insn
))
494 struct queued_debug_insn_change
*change
;
497 fprintf (dump_file
, "debug_insn %u: queued replacing reg %u with %u\n",
498 INSN_UID (insn
), REGNO (*loc
), REGNO (new_rtx
));
500 change
= (struct queued_debug_insn_change
*)
501 pool_alloc (debug_insn_changes_pool
);
502 change
->next
= vd
->e
[REGNO (new_rtx
)].debug_insn_changes
;
505 change
->new_rtx
= new_rtx
;
506 vd
->e
[REGNO (new_rtx
)].debug_insn_changes
= change
;
507 ++vd
->n_debug_insn_changes
;
511 fprintf (dump_file
, "insn %u: replaced reg %u with %u\n",
512 INSN_UID (insn
), REGNO (*loc
), REGNO (new_rtx
));
514 validate_change (insn
, loc
, new_rtx
, 1);
520 /* Similar to replace_oldest_value_reg, but *LOC contains an address.
521 Adapted from find_reloads_address_1. CL is INDEX_REG_CLASS or
522 BASE_REG_CLASS depending on how the register is being considered. */
525 replace_oldest_value_addr (rtx
*loc
, enum reg_class cl
,
526 enum machine_mode mode
, addr_space_t as
,
527 rtx_insn
*insn
, struct value_data
*vd
)
530 RTX_CODE code
= GET_CODE (x
);
533 bool changed
= false;
538 if (DEBUG_INSN_P (insn
))
542 rtx orig_op0
= XEXP (x
, 0);
543 rtx orig_op1
= XEXP (x
, 1);
544 RTX_CODE code0
= GET_CODE (orig_op0
);
545 RTX_CODE code1
= GET_CODE (orig_op1
);
550 enum rtx_code index_code
= SCRATCH
;
552 if (GET_CODE (op0
) == SUBREG
)
554 op0
= SUBREG_REG (op0
);
555 code0
= GET_CODE (op0
);
558 if (GET_CODE (op1
) == SUBREG
)
560 op1
= SUBREG_REG (op1
);
561 code1
= GET_CODE (op1
);
564 if (code0
== MULT
|| code0
== SIGN_EXTEND
|| code0
== TRUNCATE
565 || code0
== ZERO_EXTEND
|| code1
== MEM
)
569 index_code
= GET_CODE (*locI
);
571 else if (code1
== MULT
|| code1
== SIGN_EXTEND
|| code1
== TRUNCATE
572 || code1
== ZERO_EXTEND
|| code0
== MEM
)
576 index_code
= GET_CODE (*locI
);
578 else if (code0
== CONST_INT
|| code0
== CONST
579 || code0
== SYMBOL_REF
|| code0
== LABEL_REF
)
582 index_code
= GET_CODE (XEXP (x
, 0));
584 else if (code1
== CONST_INT
|| code1
== CONST
585 || code1
== SYMBOL_REF
|| code1
== LABEL_REF
)
588 index_code
= GET_CODE (XEXP (x
, 1));
590 else if (code0
== REG
&& code1
== REG
)
593 unsigned regno0
= REGNO (op0
), regno1
= REGNO (op1
);
595 if (REGNO_OK_FOR_INDEX_P (regno1
)
596 && regno_ok_for_base_p (regno0
, mode
, as
, PLUS
, REG
))
598 else if (REGNO_OK_FOR_INDEX_P (regno0
)
599 && regno_ok_for_base_p (regno1
, mode
, as
, PLUS
, REG
))
601 else if (regno_ok_for_base_p (regno0
, mode
, as
, PLUS
, REG
)
602 || REGNO_OK_FOR_INDEX_P (regno1
))
604 else if (regno_ok_for_base_p (regno1
, mode
, as
, PLUS
, REG
))
609 locI
= &XEXP (x
, index_op
);
610 locB
= &XEXP (x
, !index_op
);
611 index_code
= GET_CODE (*locI
);
613 else if (code0
== REG
)
617 index_code
= GET_CODE (*locI
);
619 else if (code1
== REG
)
623 index_code
= GET_CODE (*locI
);
627 changed
|= replace_oldest_value_addr (locI
, INDEX_REG_CLASS
,
630 changed
|= replace_oldest_value_addr (locB
,
631 base_reg_class (mode
, as
, PLUS
,
646 return replace_oldest_value_mem (x
, insn
, vd
);
649 return replace_oldest_value_reg (loc
, cl
, insn
, vd
);
655 fmt
= GET_RTX_FORMAT (code
);
656 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
659 changed
|= replace_oldest_value_addr (&XEXP (x
, i
), cl
, mode
, as
,
661 else if (fmt
[i
] == 'E')
662 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
663 changed
|= replace_oldest_value_addr (&XVECEXP (x
, i
, j
), cl
,
670 /* Similar to replace_oldest_value_reg, but X contains a memory. */
673 replace_oldest_value_mem (rtx x
, rtx_insn
*insn
, struct value_data
*vd
)
677 if (DEBUG_INSN_P (insn
))
680 cl
= base_reg_class (GET_MODE (x
), MEM_ADDR_SPACE (x
), MEM
, SCRATCH
);
682 return replace_oldest_value_addr (&XEXP (x
, 0), cl
,
683 GET_MODE (x
), MEM_ADDR_SPACE (x
),
687 /* Apply all queued updates for DEBUG_INSNs that change some reg to
691 apply_debug_insn_changes (struct value_data
*vd
, unsigned int regno
)
693 struct queued_debug_insn_change
*change
;
694 rtx_insn
*last_insn
= vd
->e
[regno
].debug_insn_changes
->insn
;
696 for (change
= vd
->e
[regno
].debug_insn_changes
;
698 change
= change
->next
)
700 if (last_insn
!= change
->insn
)
702 apply_change_group ();
703 last_insn
= change
->insn
;
705 validate_change (change
->insn
, change
->loc
, change
->new_rtx
, 1);
707 apply_change_group ();
710 /* Called via note_uses, for all used registers in a real insn
711 apply DEBUG_INSN changes that change registers to the used
715 cprop_find_used_regs (rtx
*loc
, void *data
)
717 struct value_data
*const vd
= (struct value_data
*) data
;
718 subrtx_iterator::array_type array
;
719 FOR_EACH_SUBRTX (iter
, array
, *loc
, NONCONST
)
724 unsigned int regno
= REGNO (x
);
725 if (vd
->e
[regno
].debug_insn_changes
)
727 apply_debug_insn_changes (vd
, regno
);
728 free_debug_insn_changes (vd
, regno
);
734 /* Perform the forward copy propagation on basic block BB. */
737 copyprop_hardreg_forward_1 (basic_block bb
, struct value_data
*vd
)
739 bool anything_changed
= false;
742 for (insn
= BB_HEAD (bb
); ; insn
= NEXT_INSN (insn
))
744 int n_ops
, i
, predicated
;
745 bool is_asm
, any_replacements
;
748 bool replaced
[MAX_RECOG_OPERANDS
];
749 bool changed
= false;
750 struct kill_set_value_data ksvd
;
752 if (!NONDEBUG_INSN_P (insn
))
754 if (DEBUG_INSN_P (insn
))
756 rtx loc
= INSN_VAR_LOCATION_LOC (insn
);
757 if (!VAR_LOC_UNKNOWN_P (loc
))
758 replace_oldest_value_addr (&INSN_VAR_LOCATION_LOC (insn
),
759 ALL_REGS
, GET_MODE (loc
),
760 ADDR_SPACE_GENERIC
, insn
, vd
);
763 if (insn
== BB_END (bb
))
769 set
= single_set (insn
);
771 if (! constrain_operands (1))
772 fatal_insn_not_found (insn
);
773 preprocess_constraints (insn
);
774 const operand_alternative
*op_alt
= which_op_alt ();
775 n_ops
= recog_data
.n_operands
;
776 is_asm
= asm_noperands (PATTERN (insn
)) >= 0;
778 /* Simplify the code below by promoting OP_OUT to OP_INOUT
779 in predicated instructions. */
781 predicated
= GET_CODE (PATTERN (insn
)) == COND_EXEC
;
782 for (i
= 0; i
< n_ops
; ++i
)
784 int matches
= op_alt
[i
].matches
;
785 if (matches
>= 0 || op_alt
[i
].matched
>= 0
786 || (predicated
&& recog_data
.operand_type
[i
] == OP_OUT
))
787 recog_data
.operand_type
[i
] = OP_INOUT
;
790 /* Apply changes to earlier DEBUG_INSNs if possible. */
791 if (vd
->n_debug_insn_changes
)
792 note_uses (&PATTERN (insn
), cprop_find_used_regs
, vd
);
794 /* For each earlyclobber operand, zap the value data. */
795 for (i
= 0; i
< n_ops
; i
++)
796 if (op_alt
[i
].earlyclobber
)
797 kill_value (recog_data
.operand
[i
], vd
);
799 /* Within asms, a clobber cannot overlap inputs or outputs.
800 I wouldn't think this were true for regular insns, but
801 scan_rtx treats them like that... */
802 note_stores (PATTERN (insn
), kill_clobbered_value
, vd
);
804 /* Kill all auto-incremented values. */
805 /* ??? REG_INC is useless, since stack pushes aren't done that way. */
806 kill_autoinc_value (insn
, vd
);
808 /* Kill all early-clobbered operands. */
809 for (i
= 0; i
< n_ops
; i
++)
810 if (op_alt
[i
].earlyclobber
)
811 kill_value (recog_data
.operand
[i
], vd
);
813 /* If we have dead sets in the insn, then we need to note these as we
815 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
817 if (REG_NOTE_KIND (link
) == REG_UNUSED
)
819 kill_value (XEXP (link
, 0), vd
);
820 /* Furthermore, if the insn looked like a single-set,
821 but the dead store kills the source value of that
822 set, then we can no-longer use the plain move
823 special case below. */
825 && reg_overlap_mentioned_p (XEXP (link
, 0), SET_SRC (set
)))
830 /* Special-case plain move instructions, since we may well
831 be able to do the move from a different register class. */
832 if (set
&& REG_P (SET_SRC (set
)))
834 rtx src
= SET_SRC (set
);
835 unsigned int regno
= REGNO (src
);
836 enum machine_mode mode
= GET_MODE (src
);
840 /* If we are accessing SRC in some mode other that what we
841 set it in, make sure that the replacement is valid. */
842 if (mode
!= vd
->e
[regno
].mode
)
844 if (hard_regno_nregs
[regno
][mode
]
845 > hard_regno_nregs
[regno
][vd
->e
[regno
].mode
])
846 goto no_move_special_case
;
848 /* And likewise, if we are narrowing on big endian the transformation
850 if (hard_regno_nregs
[regno
][mode
]
851 < hard_regno_nregs
[regno
][vd
->e
[regno
].mode
]
852 && (GET_MODE_SIZE (vd
->e
[regno
].mode
) > UNITS_PER_WORD
853 ? WORDS_BIG_ENDIAN
: BYTES_BIG_ENDIAN
))
854 goto no_move_special_case
;
857 /* If the destination is also a register, try to find a source
858 register in the same class. */
859 if (REG_P (SET_DEST (set
)))
861 new_rtx
= find_oldest_value_reg (REGNO_REG_CLASS (regno
), src
, vd
);
862 if (new_rtx
&& validate_change (insn
, &SET_SRC (set
), new_rtx
, 0))
866 "insn %u: replaced reg %u with %u\n",
867 INSN_UID (insn
), regno
, REGNO (new_rtx
));
869 goto did_replacement
;
871 /* We need to re-extract as validate_change clobbers
874 if (! constrain_operands (1))
875 fatal_insn_not_found (insn
);
876 preprocess_constraints (insn
);
879 /* Otherwise, try all valid registers and see if its valid. */
880 for (i
= vd
->e
[regno
].oldest_regno
; i
!= regno
;
881 i
= vd
->e
[i
].next_regno
)
883 new_rtx
= maybe_mode_change (vd
->e
[i
].mode
, vd
->e
[regno
].mode
,
885 if (new_rtx
!= NULL_RTX
)
887 if (validate_change (insn
, &SET_SRC (set
), new_rtx
, 0))
889 ORIGINAL_REGNO (new_rtx
) = ORIGINAL_REGNO (src
);
890 REG_ATTRS (new_rtx
) = REG_ATTRS (src
);
891 REG_POINTER (new_rtx
) = REG_POINTER (src
);
894 "insn %u: replaced reg %u with %u\n",
895 INSN_UID (insn
), regno
, REGNO (new_rtx
));
897 goto did_replacement
;
899 /* We need to re-extract as validate_change clobbers
902 if (! constrain_operands (1))
903 fatal_insn_not_found (insn
);
904 preprocess_constraints (insn
);
908 no_move_special_case
:
910 any_replacements
= false;
912 /* For each input operand, replace a hard register with the
913 eldest live copy that's in an appropriate register class. */
914 for (i
= 0; i
< n_ops
; i
++)
918 /* Don't scan match_operand here, since we've no reg class
919 information to pass down. Any operands that we could
920 substitute in will be represented elsewhere. */
921 if (recog_data
.constraints
[i
][0] == '\0')
924 /* Don't replace in asms intentionally referencing hard regs. */
925 if (is_asm
&& REG_P (recog_data
.operand
[i
])
926 && (REGNO (recog_data
.operand
[i
])
927 == ORIGINAL_REGNO (recog_data
.operand
[i
])))
930 if (recog_data
.operand_type
[i
] == OP_IN
)
932 if (op_alt
[i
].is_address
)
934 = replace_oldest_value_addr (recog_data
.operand_loc
[i
],
935 alternative_class (op_alt
, i
),
936 VOIDmode
, ADDR_SPACE_GENERIC
,
938 else if (REG_P (recog_data
.operand
[i
]))
940 = replace_oldest_value_reg (recog_data
.operand_loc
[i
],
941 alternative_class (op_alt
, i
),
943 else if (MEM_P (recog_data
.operand
[i
]))
944 replaced
[i
] = replace_oldest_value_mem (recog_data
.operand
[i
],
947 else if (MEM_P (recog_data
.operand
[i
]))
948 replaced
[i
] = replace_oldest_value_mem (recog_data
.operand
[i
],
951 /* If we performed any replacement, update match_dups. */
957 new_rtx
= *recog_data
.operand_loc
[i
];
958 recog_data
.operand
[i
] = new_rtx
;
959 for (j
= 0; j
< recog_data
.n_dups
; j
++)
960 if (recog_data
.dup_num
[j
] == i
)
961 validate_unshare_change (insn
, recog_data
.dup_loc
[j
], new_rtx
, 1);
963 any_replacements
= true;
967 if (any_replacements
)
969 if (! apply_change_group ())
971 for (i
= 0; i
< n_ops
; i
++)
974 rtx old
= *recog_data
.operand_loc
[i
];
975 recog_data
.operand
[i
] = old
;
980 "insn %u: reg replacements not verified\n",
990 anything_changed
= true;
992 /* If something changed, perhaps further changes to earlier
993 DEBUG_INSNs can be applied. */
994 if (vd
->n_debug_insn_changes
)
995 note_uses (&PATTERN (insn
), cprop_find_used_regs
, vd
);
999 ksvd
.ignore_set_reg
= NULL_RTX
;
1001 /* Clobber call-clobbered registers. */
1004 unsigned int set_regno
= INVALID_REGNUM
;
1005 unsigned int set_nregs
= 0;
1009 for (exp
= CALL_INSN_FUNCTION_USAGE (insn
); exp
; exp
= XEXP (exp
, 1))
1011 rtx x
= XEXP (exp
, 0);
1012 if (GET_CODE (x
) == SET
)
1014 rtx dest
= SET_DEST (x
);
1015 kill_value (dest
, vd
);
1016 set_value_regno (REGNO (dest
), GET_MODE (dest
), vd
);
1017 copy_value (dest
, SET_SRC (x
), vd
);
1018 ksvd
.ignore_set_reg
= dest
;
1019 set_regno
= REGNO (dest
);
1021 = hard_regno_nregs
[set_regno
][GET_MODE (dest
)];
1026 for (regno
= 0; regno
< FIRST_PSEUDO_REGISTER
; regno
++)
1027 if ((TEST_HARD_REG_BIT (regs_invalidated_by_call
, regno
)
1028 || HARD_REGNO_CALL_PART_CLOBBERED (regno
, vd
->e
[regno
].mode
))
1029 && (regno
< set_regno
|| regno
>= set_regno
+ set_nregs
))
1030 kill_value_regno (regno
, 1, vd
);
1032 /* If SET was seen in CALL_INSN_FUNCTION_USAGE, and SET_SRC
1033 of the SET isn't in regs_invalidated_by_call hard reg set,
1034 but instead among CLOBBERs on the CALL_INSN, we could wrongly
1035 assume the value in it is still live. */
1036 if (ksvd
.ignore_set_reg
)
1038 note_stores (PATTERN (insn
), kill_clobbered_value
, vd
);
1039 for (exp
= CALL_INSN_FUNCTION_USAGE (insn
);
1041 exp
= XEXP (exp
, 1))
1043 rtx x
= XEXP (exp
, 0);
1044 if (GET_CODE (x
) == CLOBBER
)
1045 kill_value (SET_DEST (x
), vd
);
1051 && REG_P (SET_DEST (set
))
1052 && REG_P (SET_SRC (set
)));
1053 bool noop_p
= (copy_p
1054 && rtx_equal_p (SET_DEST (set
), SET_SRC (set
)));
1058 /* Notice stores. */
1059 note_stores (PATTERN (insn
), kill_set_value
, &ksvd
);
1061 /* Notice copies. */
1063 copy_value (SET_DEST (set
), SET_SRC (set
), vd
);
1066 if (insn
== BB_END (bb
))
1070 return anything_changed
;
1073 /* Dump the value chain data to stderr. */
1076 debug_value_data (struct value_data
*vd
)
1081 CLEAR_HARD_REG_SET (set
);
1083 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1084 if (vd
->e
[i
].oldest_regno
== i
)
1086 if (vd
->e
[i
].mode
== VOIDmode
)
1088 if (vd
->e
[i
].next_regno
!= INVALID_REGNUM
)
1089 fprintf (stderr
, "[%u] Bad next_regno for empty chain (%u)\n",
1090 i
, vd
->e
[i
].next_regno
);
1094 SET_HARD_REG_BIT (set
, i
);
1095 fprintf (stderr
, "[%u %s] ", i
, GET_MODE_NAME (vd
->e
[i
].mode
));
1097 for (j
= vd
->e
[i
].next_regno
;
1098 j
!= INVALID_REGNUM
;
1099 j
= vd
->e
[j
].next_regno
)
1101 if (TEST_HARD_REG_BIT (set
, j
))
1103 fprintf (stderr
, "[%u] Loop in regno chain\n", j
);
1107 if (vd
->e
[j
].oldest_regno
!= i
)
1109 fprintf (stderr
, "[%u] Bad oldest_regno (%u)\n",
1110 j
, vd
->e
[j
].oldest_regno
);
1113 SET_HARD_REG_BIT (set
, j
);
1114 fprintf (stderr
, "[%u %s] ", j
, GET_MODE_NAME (vd
->e
[j
].mode
));
1116 fputc ('\n', stderr
);
1119 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1120 if (! TEST_HARD_REG_BIT (set
, i
)
1121 && (vd
->e
[i
].mode
!= VOIDmode
1122 || vd
->e
[i
].oldest_regno
!= i
1123 || vd
->e
[i
].next_regno
!= INVALID_REGNUM
))
1124 fprintf (stderr
, "[%u] Non-empty reg in chain (%s %u %i)\n",
1125 i
, GET_MODE_NAME (vd
->e
[i
].mode
), vd
->e
[i
].oldest_regno
,
1126 vd
->e
[i
].next_regno
);
1129 /* Do copyprop_hardreg_forward_1 for a single basic block BB.
1130 DEBUG_INSN is skipped since we do not want to involve DF related
1131 staff as how it is handled in function pass_cprop_hardreg::execute.
1133 NOTE: Currently it is only used for shrink-wrap. Maybe extend it
1134 to handle DEBUG_INSN for other uses. */
1137 copyprop_hardreg_forward_bb_without_debug_insn (basic_block bb
)
1139 struct value_data
*vd
;
1140 vd
= XNEWVEC (struct value_data
, 1);
1141 init_value_data (vd
);
1143 skip_debug_insn_p
= true;
1144 copyprop_hardreg_forward_1 (bb
, vd
);
1146 skip_debug_insn_p
= false;
1149 #ifdef ENABLE_CHECKING
1151 validate_value_data (struct value_data
*vd
)
1156 CLEAR_HARD_REG_SET (set
);
1158 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1159 if (vd
->e
[i
].oldest_regno
== i
)
1161 if (vd
->e
[i
].mode
== VOIDmode
)
1163 if (vd
->e
[i
].next_regno
!= INVALID_REGNUM
)
1164 internal_error ("validate_value_data: [%u] Bad next_regno for empty chain (%u)",
1165 i
, vd
->e
[i
].next_regno
);
1169 SET_HARD_REG_BIT (set
, i
);
1171 for (j
= vd
->e
[i
].next_regno
;
1172 j
!= INVALID_REGNUM
;
1173 j
= vd
->e
[j
].next_regno
)
1175 if (TEST_HARD_REG_BIT (set
, j
))
1176 internal_error ("validate_value_data: Loop in regno chain (%u)",
1178 if (vd
->e
[j
].oldest_regno
!= i
)
1179 internal_error ("validate_value_data: [%u] Bad oldest_regno (%u)",
1180 j
, vd
->e
[j
].oldest_regno
);
1182 SET_HARD_REG_BIT (set
, j
);
1186 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1187 if (! TEST_HARD_REG_BIT (set
, i
)
1188 && (vd
->e
[i
].mode
!= VOIDmode
1189 || vd
->e
[i
].oldest_regno
!= i
1190 || vd
->e
[i
].next_regno
!= INVALID_REGNUM
))
1191 internal_error ("validate_value_data: [%u] Non-empty reg in chain (%s %u %i)",
1192 i
, GET_MODE_NAME (vd
->e
[i
].mode
), vd
->e
[i
].oldest_regno
,
1193 vd
->e
[i
].next_regno
);
1199 const pass_data pass_data_cprop_hardreg
=
1201 RTL_PASS
, /* type */
1202 "cprop_hardreg", /* name */
1203 OPTGROUP_NONE
, /* optinfo_flags */
1204 TV_CPROP_REGISTERS
, /* tv_id */
1205 0, /* properties_required */
1206 0, /* properties_provided */
1207 0, /* properties_destroyed */
1208 0, /* todo_flags_start */
1209 TODO_df_finish
, /* todo_flags_finish */
1212 class pass_cprop_hardreg
: public rtl_opt_pass
1215 pass_cprop_hardreg (gcc::context
*ctxt
)
1216 : rtl_opt_pass (pass_data_cprop_hardreg
, ctxt
)
1219 /* opt_pass methods: */
1220 virtual bool gate (function
*)
1222 return (optimize
> 0 && (flag_cprop_registers
));
1225 virtual unsigned int execute (function
*);
1227 }; // class pass_cprop_hardreg
1230 pass_cprop_hardreg::execute (function
*fun
)
1232 struct value_data
*all_vd
;
1235 bool analyze_called
= false;
1237 all_vd
= XNEWVEC (struct value_data
, last_basic_block_for_fn (fun
));
1239 visited
= sbitmap_alloc (last_basic_block_for_fn (fun
));
1240 bitmap_clear (visited
);
1242 if (MAY_HAVE_DEBUG_INSNS
)
1243 debug_insn_changes_pool
1244 = create_alloc_pool ("debug insn changes pool",
1245 sizeof (struct queued_debug_insn_change
), 256);
1247 FOR_EACH_BB_FN (bb
, fun
)
1249 bitmap_set_bit (visited
, bb
->index
);
1251 /* If a block has a single predecessor, that we've already
1252 processed, begin with the value data that was live at
1253 the end of the predecessor block. */
1254 /* ??? Ought to use more intelligent queuing of blocks. */
1255 if (single_pred_p (bb
)
1256 && bitmap_bit_p (visited
, single_pred (bb
)->index
)
1257 && ! (single_pred_edge (bb
)->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
)))
1259 all_vd
[bb
->index
] = all_vd
[single_pred (bb
)->index
];
1260 if (all_vd
[bb
->index
].n_debug_insn_changes
)
1264 for (regno
= 0; regno
< FIRST_PSEUDO_REGISTER
; regno
++)
1266 if (all_vd
[bb
->index
].e
[regno
].debug_insn_changes
)
1268 all_vd
[bb
->index
].e
[regno
].debug_insn_changes
= NULL
;
1269 if (--all_vd
[bb
->index
].n_debug_insn_changes
== 0)
1276 init_value_data (all_vd
+ bb
->index
);
1278 copyprop_hardreg_forward_1 (bb
, all_vd
+ bb
->index
);
1281 if (MAY_HAVE_DEBUG_INSNS
)
1283 FOR_EACH_BB_FN (bb
, fun
)
1284 if (bitmap_bit_p (visited
, bb
->index
)
1285 && all_vd
[bb
->index
].n_debug_insn_changes
)
1290 if (!analyze_called
)
1293 analyze_called
= true;
1295 live
= df_get_live_out (bb
);
1296 for (regno
= 0; regno
< FIRST_PSEUDO_REGISTER
; regno
++)
1297 if (all_vd
[bb
->index
].e
[regno
].debug_insn_changes
)
1299 if (REGNO_REG_SET_P (live
, regno
))
1300 apply_debug_insn_changes (all_vd
+ bb
->index
, regno
);
1301 if (all_vd
[bb
->index
].n_debug_insn_changes
== 0)
1306 free_alloc_pool (debug_insn_changes_pool
);
1309 sbitmap_free (visited
);
1317 make_pass_cprop_hardreg (gcc::context
*ctxt
)
1319 return new pass_cprop_hardreg (ctxt
);