1 /* Copy propagation on hard registers for the GNU compiler.
2 Copyright (C) 2000-2015 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"
37 #include "dominance.h"
39 #include "basic-block.h"
43 #include "diagnostic-core.h"
45 #include "tree-pass.h"
49 /* The following code does forward propagation of hard register copies.
50 The object is to eliminate as many dependencies as possible, so that
51 we have the most scheduling freedom. As a side effect, we also clean
52 up some silly register allocation decisions made by reload. This
53 code may be obsoleted by a new register allocator. */
55 /* DEBUG_INSNs aren't changed right away, as doing so might extend the
56 lifetime of a register and get the DEBUG_INSN subsequently reset.
57 So they are queued instead, and updated only when the register is
58 used in some subsequent real insn before it is set. */
59 struct queued_debug_insn_change
61 struct queued_debug_insn_change
*next
;
67 /* For each register, we have a list of registers that contain the same
68 value. The OLDEST_REGNO field points to the head of the list, and
69 the NEXT_REGNO field runs through the list. The MODE field indicates
70 what mode the data is known to be in; this field is VOIDmode when the
71 register is not known to contain valid data. */
73 struct value_data_entry
76 unsigned int oldest_regno
;
77 unsigned int next_regno
;
78 struct queued_debug_insn_change
*debug_insn_changes
;
83 struct value_data_entry e
[FIRST_PSEUDO_REGISTER
];
84 unsigned int max_value_regs
;
85 unsigned int n_debug_insn_changes
;
88 static alloc_pool debug_insn_changes_pool
;
89 static bool skip_debug_insn_p
;
91 static void kill_value_one_regno (unsigned, struct value_data
*);
92 static void kill_value_regno (unsigned, unsigned, struct value_data
*);
93 static void kill_value (const_rtx
, struct value_data
*);
94 static void set_value_regno (unsigned, machine_mode
, struct value_data
*);
95 static void init_value_data (struct value_data
*);
96 static void kill_clobbered_value (rtx
, const_rtx
, void *);
97 static void kill_set_value (rtx
, const_rtx
, void *);
98 static void copy_value (rtx
, rtx
, struct value_data
*);
99 static bool mode_change_ok (machine_mode
, machine_mode
,
101 static rtx
maybe_mode_change (machine_mode
, machine_mode
,
102 machine_mode
, unsigned int, unsigned int);
103 static rtx
find_oldest_value_reg (enum reg_class
, rtx
, struct value_data
*);
104 static bool replace_oldest_value_reg (rtx
*, enum reg_class
, rtx_insn
*,
105 struct value_data
*);
106 static bool replace_oldest_value_addr (rtx
*, enum reg_class
,
107 machine_mode
, addr_space_t
,
108 rtx_insn
*, struct value_data
*);
109 static bool replace_oldest_value_mem (rtx
, rtx_insn
*, struct value_data
*);
110 static bool copyprop_hardreg_forward_1 (basic_block
, struct value_data
*);
111 extern void debug_value_data (struct value_data
*);
112 #ifdef ENABLE_CHECKING
113 static void validate_value_data (struct value_data
*);
116 /* Free all queued updates for DEBUG_INSNs that change some reg to
120 free_debug_insn_changes (struct value_data
*vd
, unsigned int regno
)
122 struct queued_debug_insn_change
*cur
, *next
;
123 for (cur
= vd
->e
[regno
].debug_insn_changes
; cur
; cur
= next
)
126 --vd
->n_debug_insn_changes
;
127 pool_free (debug_insn_changes_pool
, cur
);
129 vd
->e
[regno
].debug_insn_changes
= NULL
;
132 /* Kill register REGNO. This involves removing it from any value
133 lists, and resetting the value mode to VOIDmode. This is only a
134 helper function; it does not handle any hard registers overlapping
138 kill_value_one_regno (unsigned int regno
, struct value_data
*vd
)
140 unsigned int i
, next
;
142 if (vd
->e
[regno
].oldest_regno
!= regno
)
144 for (i
= vd
->e
[regno
].oldest_regno
;
145 vd
->e
[i
].next_regno
!= regno
;
146 i
= vd
->e
[i
].next_regno
)
148 vd
->e
[i
].next_regno
= vd
->e
[regno
].next_regno
;
150 else if ((next
= vd
->e
[regno
].next_regno
) != INVALID_REGNUM
)
152 for (i
= next
; i
!= INVALID_REGNUM
; i
= vd
->e
[i
].next_regno
)
153 vd
->e
[i
].oldest_regno
= next
;
156 vd
->e
[regno
].mode
= VOIDmode
;
157 vd
->e
[regno
].oldest_regno
= regno
;
158 vd
->e
[regno
].next_regno
= INVALID_REGNUM
;
159 if (vd
->e
[regno
].debug_insn_changes
)
160 free_debug_insn_changes (vd
, regno
);
162 #ifdef ENABLE_CHECKING
163 validate_value_data (vd
);
167 /* Kill the value in register REGNO for NREGS, and any other registers
168 whose values overlap. */
171 kill_value_regno (unsigned int regno
, unsigned int nregs
,
172 struct value_data
*vd
)
176 /* Kill the value we're told to kill. */
177 for (j
= 0; j
< nregs
; ++j
)
178 kill_value_one_regno (regno
+ j
, vd
);
180 /* Kill everything that overlapped what we're told to kill. */
181 if (regno
< vd
->max_value_regs
)
184 j
= regno
- vd
->max_value_regs
;
185 for (; j
< regno
; ++j
)
188 if (vd
->e
[j
].mode
== VOIDmode
)
190 n
= hard_regno_nregs
[j
][vd
->e
[j
].mode
];
192 for (i
= 0; i
< n
; ++i
)
193 kill_value_one_regno (j
+ i
, vd
);
197 /* Kill X. This is a convenience function wrapping kill_value_regno
198 so that we mind the mode the register is in. */
201 kill_value (const_rtx x
, struct value_data
*vd
)
203 if (GET_CODE (x
) == SUBREG
)
205 rtx tmp
= simplify_subreg (GET_MODE (x
), SUBREG_REG (x
),
206 GET_MODE (SUBREG_REG (x
)), SUBREG_BYTE (x
));
207 x
= tmp
? tmp
: SUBREG_REG (x
);
211 unsigned int regno
= REGNO (x
);
212 unsigned int n
= hard_regno_nregs
[regno
][GET_MODE (x
)];
214 kill_value_regno (regno
, n
, vd
);
218 /* Remember that REGNO is valid in MODE. */
221 set_value_regno (unsigned int regno
, machine_mode mode
,
222 struct value_data
*vd
)
226 vd
->e
[regno
].mode
= mode
;
228 nregs
= hard_regno_nregs
[regno
][mode
];
229 if (nregs
> vd
->max_value_regs
)
230 vd
->max_value_regs
= nregs
;
233 /* Initialize VD such that there are no known relationships between regs. */
236 init_value_data (struct value_data
*vd
)
239 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
241 vd
->e
[i
].mode
= VOIDmode
;
242 vd
->e
[i
].oldest_regno
= i
;
243 vd
->e
[i
].next_regno
= INVALID_REGNUM
;
244 vd
->e
[i
].debug_insn_changes
= NULL
;
246 vd
->max_value_regs
= 0;
247 vd
->n_debug_insn_changes
= 0;
250 /* Called through note_stores. If X is clobbered, kill its value. */
253 kill_clobbered_value (rtx x
, const_rtx set
, void *data
)
255 struct value_data
*const vd
= (struct value_data
*) data
;
256 if (GET_CODE (set
) == CLOBBER
)
260 /* A structure passed as data to kill_set_value through note_stores. */
261 struct kill_set_value_data
263 struct value_data
*vd
;
267 /* Called through note_stores. If X is set, not clobbered, kill its
268 current value and install it as the root of its own value list. */
271 kill_set_value (rtx x
, const_rtx set
, void *data
)
273 struct kill_set_value_data
*ksvd
= (struct kill_set_value_data
*) data
;
274 if (rtx_equal_p (x
, ksvd
->ignore_set_reg
))
276 if (GET_CODE (set
) != CLOBBER
)
278 kill_value (x
, ksvd
->vd
);
280 set_value_regno (REGNO (x
), GET_MODE (x
), ksvd
->vd
);
284 /* Kill any register used in X as the base of an auto-increment expression,
285 and install that register as the root of its own value list. */
288 kill_autoinc_value (rtx insn
, struct value_data
*vd
)
290 subrtx_iterator::array_type array
;
291 FOR_EACH_SUBRTX (iter
, array
, PATTERN (insn
), NONCONST
)
294 if (GET_RTX_CLASS (GET_CODE (x
)) == RTX_AUTOINC
)
298 set_value_regno (REGNO (x
), GET_MODE (x
), vd
);
299 iter
.skip_subrtxes ();
304 /* Assert that SRC has been copied to DEST. Adjust the data structures
305 to reflect that SRC contains an older copy of the shared value. */
308 copy_value (rtx dest
, rtx src
, struct value_data
*vd
)
310 unsigned int dr
= REGNO (dest
);
311 unsigned int sr
= REGNO (src
);
315 /* ??? At present, it's possible to see noop sets. It'd be nice if
316 this were cleaned up beforehand... */
320 /* Do not propagate copies to the stack pointer, as that can leave
321 memory accesses with no scheduling dependency on the stack update. */
322 if (dr
== STACK_POINTER_REGNUM
)
325 /* Likewise with the frame pointer, if we're using one. */
326 if (frame_pointer_needed
&& dr
== HARD_FRAME_POINTER_REGNUM
)
329 /* Do not propagate copies to fixed or global registers, patterns
330 can be relying to see particular fixed register or users can
331 expect the chosen global register in asm. */
332 if (fixed_regs
[dr
] || global_regs
[dr
])
335 /* If SRC and DEST overlap, don't record anything. */
336 dn
= hard_regno_nregs
[dr
][GET_MODE (dest
)];
337 sn
= hard_regno_nregs
[sr
][GET_MODE (dest
)];
338 if ((dr
> sr
&& dr
< sr
+ sn
)
339 || (sr
> dr
&& sr
< dr
+ dn
))
342 /* If SRC had no assigned mode (i.e. we didn't know it was live)
343 assign it now and assume the value came from an input argument
345 if (vd
->e
[sr
].mode
== VOIDmode
)
346 set_value_regno (sr
, vd
->e
[dr
].mode
, vd
);
348 /* If we are narrowing the input to a smaller number of hard regs,
349 and it is in big endian, we are really extracting a high part.
350 Since we generally associate a low part of a value with the value itself,
351 we must not do the same for the high part.
352 Note we can still get low parts for the same mode combination through
353 a two-step copy involving differently sized hard regs.
354 Assume hard regs fr* are 32 bits bits each, while r* are 64 bits each:
355 (set (reg:DI r0) (reg:DI fr0))
356 (set (reg:SI fr2) (reg:SI r0))
357 loads the low part of (reg:DI fr0) - i.e. fr1 - into fr2, while:
358 (set (reg:SI fr2) (reg:SI fr0))
359 loads the high part of (reg:DI fr0) into fr2.
361 We can't properly represent the latter case in our tables, so don't
362 record anything then. */
363 else if (sn
< (unsigned int) hard_regno_nregs
[sr
][vd
->e
[sr
].mode
]
364 && (GET_MODE_SIZE (vd
->e
[sr
].mode
) > UNITS_PER_WORD
365 ? WORDS_BIG_ENDIAN
: BYTES_BIG_ENDIAN
))
368 /* If SRC had been assigned a mode narrower than the copy, we can't
369 link DEST into the chain, because not all of the pieces of the
370 copy came from oldest_regno. */
371 else if (sn
> (unsigned int) hard_regno_nregs
[sr
][vd
->e
[sr
].mode
])
374 /* Link DR at the end of the value chain used by SR. */
376 vd
->e
[dr
].oldest_regno
= vd
->e
[sr
].oldest_regno
;
378 for (i
= sr
; vd
->e
[i
].next_regno
!= INVALID_REGNUM
; i
= vd
->e
[i
].next_regno
)
380 vd
->e
[i
].next_regno
= dr
;
382 #ifdef ENABLE_CHECKING
383 validate_value_data (vd
);
387 /* Return true if a mode change from ORIG to NEW is allowed for REGNO. */
390 mode_change_ok (machine_mode orig_mode
, machine_mode new_mode
,
391 unsigned int regno ATTRIBUTE_UNUSED
)
393 if (GET_MODE_SIZE (orig_mode
) < GET_MODE_SIZE (new_mode
))
396 #ifdef CANNOT_CHANGE_MODE_CLASS
397 return !REG_CANNOT_CHANGE_MODE_P (regno
, orig_mode
, new_mode
);
403 /* Register REGNO was originally set in ORIG_MODE. It - or a copy of it -
404 was copied in COPY_MODE to COPY_REGNO, and then COPY_REGNO was accessed
406 Return a NEW_MODE rtx for REGNO if that's OK, otherwise return NULL_RTX. */
409 maybe_mode_change (machine_mode orig_mode
, machine_mode copy_mode
,
410 machine_mode new_mode
, unsigned int regno
,
411 unsigned int copy_regno ATTRIBUTE_UNUSED
)
413 if (GET_MODE_SIZE (copy_mode
) < GET_MODE_SIZE (orig_mode
)
414 && GET_MODE_SIZE (copy_mode
) < GET_MODE_SIZE (new_mode
))
417 if (orig_mode
== new_mode
)
418 return gen_rtx_raw_REG (new_mode
, regno
);
419 else if (mode_change_ok (orig_mode
, new_mode
, regno
))
421 int copy_nregs
= hard_regno_nregs
[copy_regno
][copy_mode
];
422 int use_nregs
= hard_regno_nregs
[copy_regno
][new_mode
];
424 = GET_MODE_SIZE (copy_mode
) / copy_nregs
* (copy_nregs
- use_nregs
);
426 = GET_MODE_SIZE (orig_mode
) - GET_MODE_SIZE (new_mode
) - copy_offset
;
427 int byteoffset
= offset
% UNITS_PER_WORD
;
428 int wordoffset
= offset
- byteoffset
;
430 offset
= ((WORDS_BIG_ENDIAN
? wordoffset
: 0)
431 + (BYTES_BIG_ENDIAN
? byteoffset
: 0));
432 regno
+= subreg_regno_offset (regno
, orig_mode
, offset
, new_mode
);
433 if (HARD_REGNO_MODE_OK (regno
, new_mode
))
434 return gen_rtx_raw_REG (new_mode
, regno
);
439 /* Find the oldest copy of the value contained in REGNO that is in
440 register class CL and has mode MODE. If found, return an rtx
441 of that oldest register, otherwise return NULL. */
444 find_oldest_value_reg (enum reg_class cl
, rtx reg
, struct value_data
*vd
)
446 unsigned int regno
= REGNO (reg
);
447 machine_mode mode
= GET_MODE (reg
);
450 /* If we are accessing REG in some mode other that what we set it in,
451 make sure that the replacement is valid. In particular, consider
452 (set (reg:DI r11) (...))
453 (set (reg:SI r9) (reg:SI r11))
454 (set (reg:SI r10) (...))
455 (set (...) (reg:DI r9))
456 Replacing r9 with r11 is invalid. */
457 if (mode
!= vd
->e
[regno
].mode
)
459 if (hard_regno_nregs
[regno
][mode
]
460 > hard_regno_nregs
[regno
][vd
->e
[regno
].mode
])
464 for (i
= vd
->e
[regno
].oldest_regno
; i
!= regno
; i
= vd
->e
[i
].next_regno
)
466 machine_mode oldmode
= vd
->e
[i
].mode
;
469 if (!in_hard_reg_set_p (reg_class_contents
[cl
], mode
, i
))
472 new_rtx
= maybe_mode_change (oldmode
, vd
->e
[regno
].mode
, mode
, i
, regno
);
475 ORIGINAL_REGNO (new_rtx
) = ORIGINAL_REGNO (reg
);
476 REG_ATTRS (new_rtx
) = REG_ATTRS (reg
);
477 REG_POINTER (new_rtx
) = REG_POINTER (reg
);
485 /* If possible, replace the register at *LOC with the oldest register
486 in register class CL. Return true if successfully replaced. */
489 replace_oldest_value_reg (rtx
*loc
, enum reg_class cl
, rtx_insn
*insn
,
490 struct value_data
*vd
)
492 rtx new_rtx
= find_oldest_value_reg (cl
, *loc
, vd
);
493 if (new_rtx
&& (!DEBUG_INSN_P (insn
) || !skip_debug_insn_p
))
495 if (DEBUG_INSN_P (insn
))
497 struct queued_debug_insn_change
*change
;
500 fprintf (dump_file
, "debug_insn %u: queued replacing reg %u with %u\n",
501 INSN_UID (insn
), REGNO (*loc
), REGNO (new_rtx
));
503 change
= (struct queued_debug_insn_change
*)
504 pool_alloc (debug_insn_changes_pool
);
505 change
->next
= vd
->e
[REGNO (new_rtx
)].debug_insn_changes
;
508 change
->new_rtx
= new_rtx
;
509 vd
->e
[REGNO (new_rtx
)].debug_insn_changes
= change
;
510 ++vd
->n_debug_insn_changes
;
514 fprintf (dump_file
, "insn %u: replaced reg %u with %u\n",
515 INSN_UID (insn
), REGNO (*loc
), REGNO (new_rtx
));
517 validate_change (insn
, loc
, new_rtx
, 1);
523 /* Similar to replace_oldest_value_reg, but *LOC contains an address.
524 Adapted from find_reloads_address_1. CL is INDEX_REG_CLASS or
525 BASE_REG_CLASS depending on how the register is being considered. */
528 replace_oldest_value_addr (rtx
*loc
, enum reg_class cl
,
529 machine_mode mode
, addr_space_t as
,
530 rtx_insn
*insn
, struct value_data
*vd
)
533 RTX_CODE code
= GET_CODE (x
);
536 bool changed
= false;
541 if (DEBUG_INSN_P (insn
))
545 rtx orig_op0
= XEXP (x
, 0);
546 rtx orig_op1
= XEXP (x
, 1);
547 RTX_CODE code0
= GET_CODE (orig_op0
);
548 RTX_CODE code1
= GET_CODE (orig_op1
);
553 enum rtx_code index_code
= SCRATCH
;
555 if (GET_CODE (op0
) == SUBREG
)
557 op0
= SUBREG_REG (op0
);
558 code0
= GET_CODE (op0
);
561 if (GET_CODE (op1
) == SUBREG
)
563 op1
= SUBREG_REG (op1
);
564 code1
= GET_CODE (op1
);
567 if (code0
== MULT
|| code0
== SIGN_EXTEND
|| code0
== TRUNCATE
568 || code0
== ZERO_EXTEND
|| code1
== MEM
)
572 index_code
= GET_CODE (*locI
);
574 else if (code1
== MULT
|| code1
== SIGN_EXTEND
|| code1
== TRUNCATE
575 || code1
== ZERO_EXTEND
|| code0
== MEM
)
579 index_code
= GET_CODE (*locI
);
581 else if (code0
== CONST_INT
|| code0
== CONST
582 || code0
== SYMBOL_REF
|| code0
== LABEL_REF
)
585 index_code
= GET_CODE (XEXP (x
, 0));
587 else if (code1
== CONST_INT
|| code1
== CONST
588 || code1
== SYMBOL_REF
|| code1
== LABEL_REF
)
591 index_code
= GET_CODE (XEXP (x
, 1));
593 else if (code0
== REG
&& code1
== REG
)
596 unsigned regno0
= REGNO (op0
), regno1
= REGNO (op1
);
598 if (REGNO_OK_FOR_INDEX_P (regno1
)
599 && regno_ok_for_base_p (regno0
, mode
, as
, PLUS
, REG
))
601 else if (REGNO_OK_FOR_INDEX_P (regno0
)
602 && regno_ok_for_base_p (regno1
, mode
, as
, PLUS
, REG
))
604 else if (regno_ok_for_base_p (regno0
, mode
, as
, PLUS
, REG
)
605 || REGNO_OK_FOR_INDEX_P (regno1
))
607 else if (regno_ok_for_base_p (regno1
, mode
, as
, PLUS
, REG
))
612 locI
= &XEXP (x
, index_op
);
613 locB
= &XEXP (x
, !index_op
);
614 index_code
= GET_CODE (*locI
);
616 else if (code0
== REG
)
620 index_code
= GET_CODE (*locI
);
622 else if (code1
== REG
)
626 index_code
= GET_CODE (*locI
);
630 changed
|= replace_oldest_value_addr (locI
, INDEX_REG_CLASS
,
633 changed
|= replace_oldest_value_addr (locB
,
634 base_reg_class (mode
, as
, PLUS
,
649 return replace_oldest_value_mem (x
, insn
, vd
);
652 return replace_oldest_value_reg (loc
, cl
, insn
, vd
);
658 fmt
= GET_RTX_FORMAT (code
);
659 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
662 changed
|= replace_oldest_value_addr (&XEXP (x
, i
), cl
, mode
, as
,
664 else if (fmt
[i
] == 'E')
665 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
666 changed
|= replace_oldest_value_addr (&XVECEXP (x
, i
, j
), cl
,
673 /* Similar to replace_oldest_value_reg, but X contains a memory. */
676 replace_oldest_value_mem (rtx x
, rtx_insn
*insn
, struct value_data
*vd
)
680 if (DEBUG_INSN_P (insn
))
683 cl
= base_reg_class (GET_MODE (x
), MEM_ADDR_SPACE (x
), MEM
, SCRATCH
);
685 return replace_oldest_value_addr (&XEXP (x
, 0), cl
,
686 GET_MODE (x
), MEM_ADDR_SPACE (x
),
690 /* Apply all queued updates for DEBUG_INSNs that change some reg to
694 apply_debug_insn_changes (struct value_data
*vd
, unsigned int regno
)
696 struct queued_debug_insn_change
*change
;
697 rtx_insn
*last_insn
= vd
->e
[regno
].debug_insn_changes
->insn
;
699 for (change
= vd
->e
[regno
].debug_insn_changes
;
701 change
= change
->next
)
703 if (last_insn
!= change
->insn
)
705 apply_change_group ();
706 last_insn
= change
->insn
;
708 validate_change (change
->insn
, change
->loc
, change
->new_rtx
, 1);
710 apply_change_group ();
713 /* Called via note_uses, for all used registers in a real insn
714 apply DEBUG_INSN changes that change registers to the used
718 cprop_find_used_regs (rtx
*loc
, void *data
)
720 struct value_data
*const vd
= (struct value_data
*) data
;
721 subrtx_iterator::array_type array
;
722 FOR_EACH_SUBRTX (iter
, array
, *loc
, NONCONST
)
727 unsigned int regno
= REGNO (x
);
728 if (vd
->e
[regno
].debug_insn_changes
)
730 apply_debug_insn_changes (vd
, regno
);
731 free_debug_insn_changes (vd
, regno
);
737 /* Perform the forward copy propagation on basic block BB. */
740 copyprop_hardreg_forward_1 (basic_block bb
, struct value_data
*vd
)
742 bool anything_changed
= false;
745 for (insn
= BB_HEAD (bb
); ; insn
= NEXT_INSN (insn
))
747 int n_ops
, i
, predicated
;
748 bool is_asm
, any_replacements
;
751 bool replaced
[MAX_RECOG_OPERANDS
];
752 bool changed
= false;
753 struct kill_set_value_data ksvd
;
755 if (!NONDEBUG_INSN_P (insn
))
757 if (DEBUG_INSN_P (insn
))
759 rtx loc
= INSN_VAR_LOCATION_LOC (insn
);
760 if (!VAR_LOC_UNKNOWN_P (loc
))
761 replace_oldest_value_addr (&INSN_VAR_LOCATION_LOC (insn
),
762 ALL_REGS
, GET_MODE (loc
),
763 ADDR_SPACE_GENERIC
, insn
, vd
);
766 if (insn
== BB_END (bb
))
772 set
= single_set (insn
);
773 extract_constrain_insn (insn
);
774 preprocess_constraints (insn
);
775 const operand_alternative
*op_alt
= which_op_alt ();
776 n_ops
= recog_data
.n_operands
;
777 is_asm
= asm_noperands (PATTERN (insn
)) >= 0;
779 /* Simplify the code below by promoting OP_OUT to OP_INOUT
780 in predicated instructions. */
782 predicated
= GET_CODE (PATTERN (insn
)) == COND_EXEC
;
783 for (i
= 0; i
< n_ops
; ++i
)
785 int matches
= op_alt
[i
].matches
;
786 if (matches
>= 0 || op_alt
[i
].matched
>= 0
787 || (predicated
&& recog_data
.operand_type
[i
] == OP_OUT
))
788 recog_data
.operand_type
[i
] = OP_INOUT
;
791 /* Apply changes to earlier DEBUG_INSNs if possible. */
792 if (vd
->n_debug_insn_changes
)
793 note_uses (&PATTERN (insn
), cprop_find_used_regs
, vd
);
795 /* For each earlyclobber operand, zap the value data. */
796 for (i
= 0; i
< n_ops
; i
++)
797 if (op_alt
[i
].earlyclobber
)
798 kill_value (recog_data
.operand
[i
], vd
);
800 /* Within asms, a clobber cannot overlap inputs or outputs.
801 I wouldn't think this were true for regular insns, but
802 scan_rtx treats them like that... */
803 note_stores (PATTERN (insn
), kill_clobbered_value
, vd
);
805 /* Kill all auto-incremented values. */
806 /* ??? REG_INC is useless, since stack pushes aren't done that way. */
807 kill_autoinc_value (insn
, vd
);
809 /* Kill all early-clobbered operands. */
810 for (i
= 0; i
< n_ops
; i
++)
811 if (op_alt
[i
].earlyclobber
)
812 kill_value (recog_data
.operand
[i
], vd
);
814 /* If we have dead sets in the insn, then we need to note these as we
816 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
818 if (REG_NOTE_KIND (link
) == REG_UNUSED
)
820 kill_value (XEXP (link
, 0), vd
);
821 /* Furthermore, if the insn looked like a single-set,
822 but the dead store kills the source value of that
823 set, then we can no-longer use the plain move
824 special case below. */
826 && reg_overlap_mentioned_p (XEXP (link
, 0), SET_SRC (set
)))
831 /* Special-case plain move instructions, since we may well
832 be able to do the move from a different register class. */
833 if (set
&& REG_P (SET_SRC (set
)))
835 rtx src
= SET_SRC (set
);
836 unsigned int regno
= REGNO (src
);
837 machine_mode mode
= GET_MODE (src
);
841 /* If we are accessing SRC in some mode other that what we
842 set it in, make sure that the replacement is valid. */
843 if (mode
!= vd
->e
[regno
].mode
)
845 if (hard_regno_nregs
[regno
][mode
]
846 > hard_regno_nregs
[regno
][vd
->e
[regno
].mode
])
847 goto no_move_special_case
;
849 /* And likewise, if we are narrowing on big endian the transformation
851 if (hard_regno_nregs
[regno
][mode
]
852 < hard_regno_nregs
[regno
][vd
->e
[regno
].mode
]
853 && (GET_MODE_SIZE (vd
->e
[regno
].mode
) > UNITS_PER_WORD
854 ? WORDS_BIG_ENDIAN
: BYTES_BIG_ENDIAN
))
855 goto no_move_special_case
;
858 /* If the destination is also a register, try to find a source
859 register in the same class. */
860 if (REG_P (SET_DEST (set
)))
862 new_rtx
= find_oldest_value_reg (REGNO_REG_CLASS (regno
), src
, vd
);
863 if (new_rtx
&& validate_change (insn
, &SET_SRC (set
), new_rtx
, 0))
867 "insn %u: replaced reg %u with %u\n",
868 INSN_UID (insn
), regno
, REGNO (new_rtx
));
870 goto did_replacement
;
872 /* We need to re-extract as validate_change clobbers
874 extract_constrain_insn (insn
);
875 preprocess_constraints (insn
);
878 /* Otherwise, try all valid registers and see if its valid. */
879 for (i
= vd
->e
[regno
].oldest_regno
; i
!= regno
;
880 i
= vd
->e
[i
].next_regno
)
882 new_rtx
= maybe_mode_change (vd
->e
[i
].mode
, vd
->e
[regno
].mode
,
884 if (new_rtx
!= NULL_RTX
)
886 if (validate_change (insn
, &SET_SRC (set
), new_rtx
, 0))
888 ORIGINAL_REGNO (new_rtx
) = ORIGINAL_REGNO (src
);
889 REG_ATTRS (new_rtx
) = REG_ATTRS (src
);
890 REG_POINTER (new_rtx
) = REG_POINTER (src
);
893 "insn %u: replaced reg %u with %u\n",
894 INSN_UID (insn
), regno
, REGNO (new_rtx
));
896 goto did_replacement
;
898 /* We need to re-extract as validate_change clobbers
900 extract_constrain_insn (insn
);
901 preprocess_constraints (insn
);
905 no_move_special_case
:
907 any_replacements
= false;
909 /* For each input operand, replace a hard register with the
910 eldest live copy that's in an appropriate register class. */
911 for (i
= 0; i
< n_ops
; i
++)
915 /* Don't scan match_operand here, since we've no reg class
916 information to pass down. Any operands that we could
917 substitute in will be represented elsewhere. */
918 if (recog_data
.constraints
[i
][0] == '\0')
921 /* Don't replace in asms intentionally referencing hard regs. */
922 if (is_asm
&& REG_P (recog_data
.operand
[i
])
923 && (REGNO (recog_data
.operand
[i
])
924 == ORIGINAL_REGNO (recog_data
.operand
[i
])))
927 if (recog_data
.operand_type
[i
] == OP_IN
)
929 if (op_alt
[i
].is_address
)
931 = replace_oldest_value_addr (recog_data
.operand_loc
[i
],
932 alternative_class (op_alt
, i
),
933 VOIDmode
, ADDR_SPACE_GENERIC
,
935 else if (REG_P (recog_data
.operand
[i
]))
937 = replace_oldest_value_reg (recog_data
.operand_loc
[i
],
938 alternative_class (op_alt
, i
),
940 else if (MEM_P (recog_data
.operand
[i
]))
941 replaced
[i
] = replace_oldest_value_mem (recog_data
.operand
[i
],
944 else if (MEM_P (recog_data
.operand
[i
]))
945 replaced
[i
] = replace_oldest_value_mem (recog_data
.operand
[i
],
948 /* If we performed any replacement, update match_dups. */
954 new_rtx
= *recog_data
.operand_loc
[i
];
955 recog_data
.operand
[i
] = new_rtx
;
956 for (j
= 0; j
< recog_data
.n_dups
; j
++)
957 if (recog_data
.dup_num
[j
] == i
)
958 validate_unshare_change (insn
, recog_data
.dup_loc
[j
], new_rtx
, 1);
960 any_replacements
= true;
964 if (any_replacements
)
966 if (! apply_change_group ())
968 for (i
= 0; i
< n_ops
; i
++)
971 rtx old
= *recog_data
.operand_loc
[i
];
972 recog_data
.operand
[i
] = old
;
977 "insn %u: reg replacements not verified\n",
987 anything_changed
= true;
989 /* If something changed, perhaps further changes to earlier
990 DEBUG_INSNs can be applied. */
991 if (vd
->n_debug_insn_changes
)
992 note_uses (&PATTERN (insn
), cprop_find_used_regs
, vd
);
996 ksvd
.ignore_set_reg
= NULL_RTX
;
998 /* Clobber call-clobbered registers. */
1001 unsigned int set_regno
= INVALID_REGNUM
;
1002 unsigned int set_nregs
= 0;
1005 HARD_REG_SET regs_invalidated_by_this_call
;
1007 for (exp
= CALL_INSN_FUNCTION_USAGE (insn
); exp
; exp
= XEXP (exp
, 1))
1009 rtx x
= XEXP (exp
, 0);
1010 if (GET_CODE (x
) == SET
)
1012 rtx dest
= SET_DEST (x
);
1013 kill_value (dest
, vd
);
1014 set_value_regno (REGNO (dest
), GET_MODE (dest
), vd
);
1015 copy_value (dest
, SET_SRC (x
), vd
);
1016 ksvd
.ignore_set_reg
= dest
;
1017 set_regno
= REGNO (dest
);
1019 = hard_regno_nregs
[set_regno
][GET_MODE (dest
)];
1024 get_call_reg_set_usage (insn
,
1025 ®s_invalidated_by_this_call
,
1026 regs_invalidated_by_call
);
1027 for (regno
= 0; regno
< FIRST_PSEUDO_REGISTER
; regno
++)
1028 if ((TEST_HARD_REG_BIT (regs_invalidated_by_this_call
, regno
)
1029 || HARD_REGNO_CALL_PART_CLOBBERED (regno
, vd
->e
[regno
].mode
))
1030 && (regno
< set_regno
|| regno
>= set_regno
+ set_nregs
))
1031 kill_value_regno (regno
, 1, vd
);
1033 /* If SET was seen in CALL_INSN_FUNCTION_USAGE, and SET_SRC
1034 of the SET isn't in regs_invalidated_by_call hard reg set,
1035 but instead among CLOBBERs on the CALL_INSN, we could wrongly
1036 assume the value in it is still live. */
1037 if (ksvd
.ignore_set_reg
)
1039 note_stores (PATTERN (insn
), kill_clobbered_value
, vd
);
1040 for (exp
= CALL_INSN_FUNCTION_USAGE (insn
);
1042 exp
= XEXP (exp
, 1))
1044 rtx x
= XEXP (exp
, 0);
1045 if (GET_CODE (x
) == CLOBBER
)
1046 kill_value (SET_DEST (x
), vd
);
1052 && REG_P (SET_DEST (set
))
1053 && REG_P (SET_SRC (set
)));
1054 bool noop_p
= (copy_p
1055 && rtx_equal_p (SET_DEST (set
), SET_SRC (set
)));
1059 /* Notice stores. */
1060 note_stores (PATTERN (insn
), kill_set_value
, &ksvd
);
1062 /* Notice copies. */
1064 copy_value (SET_DEST (set
), SET_SRC (set
), vd
);
1067 if (insn
== BB_END (bb
))
1071 return anything_changed
;
1074 /* Dump the value chain data to stderr. */
1077 debug_value_data (struct value_data
*vd
)
1082 CLEAR_HARD_REG_SET (set
);
1084 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1085 if (vd
->e
[i
].oldest_regno
== i
)
1087 if (vd
->e
[i
].mode
== VOIDmode
)
1089 if (vd
->e
[i
].next_regno
!= INVALID_REGNUM
)
1090 fprintf (stderr
, "[%u] Bad next_regno for empty chain (%u)\n",
1091 i
, vd
->e
[i
].next_regno
);
1095 SET_HARD_REG_BIT (set
, i
);
1096 fprintf (stderr
, "[%u %s] ", i
, GET_MODE_NAME (vd
->e
[i
].mode
));
1098 for (j
= vd
->e
[i
].next_regno
;
1099 j
!= INVALID_REGNUM
;
1100 j
= vd
->e
[j
].next_regno
)
1102 if (TEST_HARD_REG_BIT (set
, j
))
1104 fprintf (stderr
, "[%u] Loop in regno chain\n", j
);
1108 if (vd
->e
[j
].oldest_regno
!= i
)
1110 fprintf (stderr
, "[%u] Bad oldest_regno (%u)\n",
1111 j
, vd
->e
[j
].oldest_regno
);
1114 SET_HARD_REG_BIT (set
, j
);
1115 fprintf (stderr
, "[%u %s] ", j
, GET_MODE_NAME (vd
->e
[j
].mode
));
1117 fputc ('\n', stderr
);
1120 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1121 if (! TEST_HARD_REG_BIT (set
, i
)
1122 && (vd
->e
[i
].mode
!= VOIDmode
1123 || vd
->e
[i
].oldest_regno
!= i
1124 || vd
->e
[i
].next_regno
!= INVALID_REGNUM
))
1125 fprintf (stderr
, "[%u] Non-empty reg in chain (%s %u %i)\n",
1126 i
, GET_MODE_NAME (vd
->e
[i
].mode
), vd
->e
[i
].oldest_regno
,
1127 vd
->e
[i
].next_regno
);
1130 /* Do copyprop_hardreg_forward_1 for a single basic block BB.
1131 DEBUG_INSN is skipped since we do not want to involve DF related
1132 staff as how it is handled in function pass_cprop_hardreg::execute.
1134 NOTE: Currently it is only used for shrink-wrap. Maybe extend it
1135 to handle DEBUG_INSN for other uses. */
1138 copyprop_hardreg_forward_bb_without_debug_insn (basic_block bb
)
1140 struct value_data
*vd
;
1141 vd
= XNEWVEC (struct value_data
, 1);
1142 init_value_data (vd
);
1144 skip_debug_insn_p
= true;
1145 copyprop_hardreg_forward_1 (bb
, vd
);
1147 skip_debug_insn_p
= false;
1150 #ifdef ENABLE_CHECKING
1152 validate_value_data (struct value_data
*vd
)
1157 CLEAR_HARD_REG_SET (set
);
1159 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1160 if (vd
->e
[i
].oldest_regno
== i
)
1162 if (vd
->e
[i
].mode
== VOIDmode
)
1164 if (vd
->e
[i
].next_regno
!= INVALID_REGNUM
)
1165 internal_error ("validate_value_data: [%u] Bad next_regno for empty chain (%u)",
1166 i
, vd
->e
[i
].next_regno
);
1170 SET_HARD_REG_BIT (set
, i
);
1172 for (j
= vd
->e
[i
].next_regno
;
1173 j
!= INVALID_REGNUM
;
1174 j
= vd
->e
[j
].next_regno
)
1176 if (TEST_HARD_REG_BIT (set
, j
))
1177 internal_error ("validate_value_data: Loop in regno chain (%u)",
1179 if (vd
->e
[j
].oldest_regno
!= i
)
1180 internal_error ("validate_value_data: [%u] Bad oldest_regno (%u)",
1181 j
, vd
->e
[j
].oldest_regno
);
1183 SET_HARD_REG_BIT (set
, j
);
1187 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1188 if (! TEST_HARD_REG_BIT (set
, i
)
1189 && (vd
->e
[i
].mode
!= VOIDmode
1190 || vd
->e
[i
].oldest_regno
!= i
1191 || vd
->e
[i
].next_regno
!= INVALID_REGNUM
))
1192 internal_error ("validate_value_data: [%u] Non-empty reg in chain (%s %u %i)",
1193 i
, GET_MODE_NAME (vd
->e
[i
].mode
), vd
->e
[i
].oldest_regno
,
1194 vd
->e
[i
].next_regno
);
1200 const pass_data pass_data_cprop_hardreg
=
1202 RTL_PASS
, /* type */
1203 "cprop_hardreg", /* name */
1204 OPTGROUP_NONE
, /* optinfo_flags */
1205 TV_CPROP_REGISTERS
, /* tv_id */
1206 0, /* properties_required */
1207 0, /* properties_provided */
1208 0, /* properties_destroyed */
1209 0, /* todo_flags_start */
1210 TODO_df_finish
, /* todo_flags_finish */
1213 class pass_cprop_hardreg
: public rtl_opt_pass
1216 pass_cprop_hardreg (gcc::context
*ctxt
)
1217 : rtl_opt_pass (pass_data_cprop_hardreg
, ctxt
)
1220 /* opt_pass methods: */
1221 virtual bool gate (function
*)
1223 return (optimize
> 0 && (flag_cprop_registers
));
1226 virtual unsigned int execute (function
*);
1228 }; // class pass_cprop_hardreg
1231 pass_cprop_hardreg::execute (function
*fun
)
1233 struct value_data
*all_vd
;
1236 bool analyze_called
= false;
1238 all_vd
= XNEWVEC (struct value_data
, last_basic_block_for_fn (fun
));
1240 visited
= sbitmap_alloc (last_basic_block_for_fn (fun
));
1241 bitmap_clear (visited
);
1243 if (MAY_HAVE_DEBUG_INSNS
)
1244 debug_insn_changes_pool
1245 = create_alloc_pool ("debug insn changes pool",
1246 sizeof (struct queued_debug_insn_change
), 256);
1248 FOR_EACH_BB_FN (bb
, fun
)
1250 bitmap_set_bit (visited
, bb
->index
);
1252 /* If a block has a single predecessor, that we've already
1253 processed, begin with the value data that was live at
1254 the end of the predecessor block. */
1255 /* ??? Ought to use more intelligent queuing of blocks. */
1256 if (single_pred_p (bb
)
1257 && bitmap_bit_p (visited
, single_pred (bb
)->index
)
1258 && ! (single_pred_edge (bb
)->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
)))
1260 all_vd
[bb
->index
] = all_vd
[single_pred (bb
)->index
];
1261 if (all_vd
[bb
->index
].n_debug_insn_changes
)
1265 for (regno
= 0; regno
< FIRST_PSEUDO_REGISTER
; regno
++)
1267 if (all_vd
[bb
->index
].e
[regno
].debug_insn_changes
)
1269 all_vd
[bb
->index
].e
[regno
].debug_insn_changes
= NULL
;
1270 if (--all_vd
[bb
->index
].n_debug_insn_changes
== 0)
1277 init_value_data (all_vd
+ bb
->index
);
1279 copyprop_hardreg_forward_1 (bb
, all_vd
+ bb
->index
);
1282 if (MAY_HAVE_DEBUG_INSNS
)
1284 FOR_EACH_BB_FN (bb
, fun
)
1285 if (bitmap_bit_p (visited
, bb
->index
)
1286 && all_vd
[bb
->index
].n_debug_insn_changes
)
1291 if (!analyze_called
)
1294 analyze_called
= true;
1296 live
= df_get_live_out (bb
);
1297 for (regno
= 0; regno
< FIRST_PSEUDO_REGISTER
; regno
++)
1298 if (all_vd
[bb
->index
].e
[regno
].debug_insn_changes
)
1300 if (REGNO_REG_SET_P (live
, regno
))
1301 apply_debug_insn_changes (all_vd
+ bb
->index
, regno
);
1302 if (all_vd
[bb
->index
].n_debug_insn_changes
== 0)
1307 free_alloc_pool (debug_insn_changes_pool
);
1310 sbitmap_free (visited
);
1318 make_pass_cprop_hardreg (gcc::context
*ctxt
)
1320 return new pass_cprop_hardreg (ctxt
);