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"
35 #include "diagnostic-core.h"
37 #include "tree-pass.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
66 enum machine_mode mode
;
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 alloc_pool debug_insn_changes_pool
;
81 static void kill_value_one_regno (unsigned, struct value_data
*);
82 static void kill_value_regno (unsigned, unsigned, struct value_data
*);
83 static void kill_value (rtx
, struct value_data
*);
84 static void set_value_regno (unsigned, enum machine_mode
, struct value_data
*);
85 static void init_value_data (struct value_data
*);
86 static void kill_clobbered_value (rtx
, const_rtx
, void *);
87 static void kill_set_value (rtx
, const_rtx
, void *);
88 static int kill_autoinc_value (rtx
*, void *);
89 static void copy_value (rtx
, rtx
, struct value_data
*);
90 static bool mode_change_ok (enum machine_mode
, enum machine_mode
,
92 static rtx
maybe_mode_change (enum machine_mode
, enum machine_mode
,
93 enum machine_mode
, unsigned int, unsigned int);
94 static rtx
find_oldest_value_reg (enum reg_class
, rtx
, struct value_data
*);
95 static bool replace_oldest_value_reg (rtx
*, enum reg_class
, rtx
,
97 static bool replace_oldest_value_addr (rtx
*, enum reg_class
,
98 enum machine_mode
, addr_space_t
, rtx
,
100 static bool replace_oldest_value_mem (rtx
, rtx
, struct value_data
*);
101 static bool copyprop_hardreg_forward_1 (basic_block
, struct value_data
*);
102 extern void debug_value_data (struct value_data
*);
103 #ifdef ENABLE_CHECKING
104 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 pool_free (debug_insn_changes_pool
, 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
);
153 #ifdef ENABLE_CHECKING
154 validate_value_data (vd
);
158 /* Kill the value in register REGNO for NREGS, and any other registers
159 whose values overlap. */
162 kill_value_regno (unsigned int regno
, unsigned int nregs
,
163 struct value_data
*vd
)
167 /* Kill the value we're told to kill. */
168 for (j
= 0; j
< nregs
; ++j
)
169 kill_value_one_regno (regno
+ j
, vd
);
171 /* Kill everything that overlapped what we're told to kill. */
172 if (regno
< vd
->max_value_regs
)
175 j
= regno
- vd
->max_value_regs
;
176 for (; j
< regno
; ++j
)
179 if (vd
->e
[j
].mode
== VOIDmode
)
181 n
= hard_regno_nregs
[j
][vd
->e
[j
].mode
];
183 for (i
= 0; i
< n
; ++i
)
184 kill_value_one_regno (j
+ i
, vd
);
188 /* Kill X. This is a convenience function wrapping kill_value_regno
189 so that we mind the mode the register is in. */
192 kill_value (rtx x
, struct value_data
*vd
)
196 if (GET_CODE (x
) == SUBREG
)
198 x
= simplify_subreg (GET_MODE (x
), SUBREG_REG (x
),
199 GET_MODE (SUBREG_REG (x
)), SUBREG_BYTE (x
));
201 x
= SUBREG_REG (orig_rtx
);
205 unsigned int regno
= REGNO (x
);
206 unsigned int n
= hard_regno_nregs
[regno
][GET_MODE (x
)];
208 kill_value_regno (regno
, n
, vd
);
212 /* Remember that REGNO is valid in MODE. */
215 set_value_regno (unsigned int regno
, enum machine_mode mode
,
216 struct value_data
*vd
)
220 vd
->e
[regno
].mode
= mode
;
222 nregs
= hard_regno_nregs
[regno
][mode
];
223 if (nregs
> vd
->max_value_regs
)
224 vd
->max_value_regs
= nregs
;
227 /* Initialize VD such that there are no known relationships between regs. */
230 init_value_data (struct value_data
*vd
)
233 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
235 vd
->e
[i
].mode
= VOIDmode
;
236 vd
->e
[i
].oldest_regno
= i
;
237 vd
->e
[i
].next_regno
= INVALID_REGNUM
;
238 vd
->e
[i
].debug_insn_changes
= NULL
;
240 vd
->max_value_regs
= 0;
241 vd
->n_debug_insn_changes
= 0;
244 /* Called through note_stores. If X is clobbered, kill its value. */
247 kill_clobbered_value (rtx x
, const_rtx set
, void *data
)
249 struct value_data
*const vd
= (struct value_data
*) data
;
250 if (GET_CODE (set
) == CLOBBER
)
254 /* A structure passed as data to kill_set_value through note_stores. */
255 struct kill_set_value_data
257 struct value_data
*vd
;
261 /* Called through note_stores. If X is set, not clobbered, kill its
262 current value and install it as the root of its own value list. */
265 kill_set_value (rtx x
, const_rtx set
, void *data
)
267 struct kill_set_value_data
*ksvd
= (struct kill_set_value_data
*) data
;
268 if (rtx_equal_p (x
, ksvd
->ignore_set_reg
))
270 if (GET_CODE (set
) != CLOBBER
)
272 kill_value (x
, ksvd
->vd
);
274 set_value_regno (REGNO (x
), GET_MODE (x
), ksvd
->vd
);
278 /* Called through for_each_rtx. Kill any register used as the base of an
279 auto-increment expression, and install that register as the root of its
283 kill_autoinc_value (rtx
*px
, void *data
)
286 struct value_data
*const vd
= (struct value_data
*) data
;
288 if (GET_RTX_CLASS (GET_CODE (x
)) == RTX_AUTOINC
)
292 set_value_regno (REGNO (x
), GET_MODE (x
), vd
);
299 /* Assert that SRC has been copied to DEST. Adjust the data structures
300 to reflect that SRC contains an older copy of the shared value. */
303 copy_value (rtx dest
, rtx src
, struct value_data
*vd
)
305 unsigned int dr
= REGNO (dest
);
306 unsigned int sr
= REGNO (src
);
310 /* ??? At present, it's possible to see noop sets. It'd be nice if
311 this were cleaned up beforehand... */
315 /* Do not propagate copies to the stack pointer, as that can leave
316 memory accesses with no scheduling dependency on the stack update. */
317 if (dr
== STACK_POINTER_REGNUM
)
320 /* Likewise with the frame pointer, if we're using one. */
321 if (frame_pointer_needed
&& dr
== HARD_FRAME_POINTER_REGNUM
)
324 /* Do not propagate copies to fixed or global registers, patterns
325 can be relying to see particular fixed register or users can
326 expect the chosen global register in asm. */
327 if (fixed_regs
[dr
] || global_regs
[dr
])
330 /* If SRC and DEST overlap, don't record anything. */
331 dn
= hard_regno_nregs
[dr
][GET_MODE (dest
)];
332 sn
= hard_regno_nregs
[sr
][GET_MODE (dest
)];
333 if ((dr
> sr
&& dr
< sr
+ sn
)
334 || (sr
> dr
&& sr
< dr
+ dn
))
337 /* If SRC had no assigned mode (i.e. we didn't know it was live)
338 assign it now and assume the value came from an input argument
340 if (vd
->e
[sr
].mode
== VOIDmode
)
341 set_value_regno (sr
, vd
->e
[dr
].mode
, vd
);
343 /* If we are narrowing the input to a smaller number of hard regs,
344 and it is in big endian, we are really extracting a high part.
345 Since we generally associate a low part of a value with the value itself,
346 we must not do the same for the high part.
347 Note we can still get low parts for the same mode combination through
348 a two-step copy involving differently sized hard regs.
349 Assume hard regs fr* are 32 bits bits each, while r* are 64 bits each:
350 (set (reg:DI r0) (reg:DI fr0))
351 (set (reg:SI fr2) (reg:SI r0))
352 loads the low part of (reg:DI fr0) - i.e. fr1 - into fr2, while:
353 (set (reg:SI fr2) (reg:SI fr0))
354 loads the high part of (reg:DI fr0) into fr2.
356 We can't properly represent the latter case in our tables, so don't
357 record anything then. */
358 else if (sn
< (unsigned int) hard_regno_nregs
[sr
][vd
->e
[sr
].mode
]
359 && (GET_MODE_SIZE (vd
->e
[sr
].mode
) > UNITS_PER_WORD
360 ? WORDS_BIG_ENDIAN
: BYTES_BIG_ENDIAN
))
363 /* If SRC had been assigned a mode narrower than the copy, we can't
364 link DEST into the chain, because not all of the pieces of the
365 copy came from oldest_regno. */
366 else if (sn
> (unsigned int) hard_regno_nregs
[sr
][vd
->e
[sr
].mode
])
369 /* Link DR at the end of the value chain used by SR. */
371 vd
->e
[dr
].oldest_regno
= vd
->e
[sr
].oldest_regno
;
373 for (i
= sr
; vd
->e
[i
].next_regno
!= INVALID_REGNUM
; i
= vd
->e
[i
].next_regno
)
375 vd
->e
[i
].next_regno
= dr
;
377 #ifdef ENABLE_CHECKING
378 validate_value_data (vd
);
382 /* Return true if a mode change from ORIG to NEW is allowed for REGNO. */
385 mode_change_ok (enum machine_mode orig_mode
, enum machine_mode new_mode
,
386 unsigned int regno ATTRIBUTE_UNUSED
)
388 if (GET_MODE_SIZE (orig_mode
) < GET_MODE_SIZE (new_mode
))
391 #ifdef CANNOT_CHANGE_MODE_CLASS
392 return !REG_CANNOT_CHANGE_MODE_P (regno
, orig_mode
, new_mode
);
398 /* Register REGNO was originally set in ORIG_MODE. It - or a copy of it -
399 was copied in COPY_MODE to COPY_REGNO, and then COPY_REGNO was accessed
401 Return a NEW_MODE rtx for REGNO if that's OK, otherwise return NULL_RTX. */
404 maybe_mode_change (enum machine_mode orig_mode
, enum machine_mode copy_mode
,
405 enum machine_mode new_mode
, unsigned int regno
,
406 unsigned int copy_regno ATTRIBUTE_UNUSED
)
408 if (GET_MODE_SIZE (copy_mode
) < GET_MODE_SIZE (orig_mode
)
409 && GET_MODE_SIZE (copy_mode
) < GET_MODE_SIZE (new_mode
))
412 if (orig_mode
== new_mode
)
413 return gen_rtx_raw_REG (new_mode
, regno
);
414 else if (mode_change_ok (orig_mode
, new_mode
, regno
))
416 int copy_nregs
= hard_regno_nregs
[copy_regno
][copy_mode
];
417 int use_nregs
= hard_regno_nregs
[copy_regno
][new_mode
];
419 = GET_MODE_SIZE (copy_mode
) / copy_nregs
* (copy_nregs
- use_nregs
);
421 = GET_MODE_SIZE (orig_mode
) - GET_MODE_SIZE (new_mode
) - copy_offset
;
422 int byteoffset
= offset
% UNITS_PER_WORD
;
423 int wordoffset
= offset
- byteoffset
;
425 offset
= ((WORDS_BIG_ENDIAN
? wordoffset
: 0)
426 + (BYTES_BIG_ENDIAN
? byteoffset
: 0));
427 regno
+= subreg_regno_offset (regno
, orig_mode
, offset
, new_mode
);
428 if (HARD_REGNO_MODE_OK (regno
, new_mode
))
429 return gen_rtx_raw_REG (new_mode
, regno
);
434 /* Find the oldest copy of the value contained in REGNO that is in
435 register class CL and has mode MODE. If found, return an rtx
436 of that oldest register, otherwise return NULL. */
439 find_oldest_value_reg (enum reg_class cl
, rtx reg
, struct value_data
*vd
)
441 unsigned int regno
= REGNO (reg
);
442 enum machine_mode mode
= GET_MODE (reg
);
445 /* If we are accessing REG in some mode other that what we set it in,
446 make sure that the replacement is valid. In particular, consider
447 (set (reg:DI r11) (...))
448 (set (reg:SI r9) (reg:SI r11))
449 (set (reg:SI r10) (...))
450 (set (...) (reg:DI r9))
451 Replacing r9 with r11 is invalid. */
452 if (mode
!= vd
->e
[regno
].mode
)
454 if (hard_regno_nregs
[regno
][mode
]
455 > hard_regno_nregs
[regno
][vd
->e
[regno
].mode
])
459 for (i
= vd
->e
[regno
].oldest_regno
; i
!= regno
; i
= vd
->e
[i
].next_regno
)
461 enum machine_mode oldmode
= vd
->e
[i
].mode
;
464 if (!in_hard_reg_set_p (reg_class_contents
[cl
], mode
, i
))
467 new_rtx
= maybe_mode_change (oldmode
, vd
->e
[regno
].mode
, mode
, i
, regno
);
470 ORIGINAL_REGNO (new_rtx
) = ORIGINAL_REGNO (reg
);
471 REG_ATTRS (new_rtx
) = REG_ATTRS (reg
);
472 REG_POINTER (new_rtx
) = REG_POINTER (reg
);
480 /* If possible, replace the register at *LOC with the oldest register
481 in register class CL. Return true if successfully replaced. */
484 replace_oldest_value_reg (rtx
*loc
, enum reg_class cl
, rtx insn
,
485 struct value_data
*vd
)
487 rtx new_rtx
= find_oldest_value_reg (cl
, *loc
, vd
);
490 if (DEBUG_INSN_P (insn
))
492 struct queued_debug_insn_change
*change
;
495 fprintf (dump_file
, "debug_insn %u: queued replacing reg %u with %u\n",
496 INSN_UID (insn
), REGNO (*loc
), REGNO (new_rtx
));
498 change
= (struct queued_debug_insn_change
*)
499 pool_alloc (debug_insn_changes_pool
);
500 change
->next
= vd
->e
[REGNO (new_rtx
)].debug_insn_changes
;
503 change
->new_rtx
= new_rtx
;
504 vd
->e
[REGNO (new_rtx
)].debug_insn_changes
= change
;
505 ++vd
->n_debug_insn_changes
;
509 fprintf (dump_file
, "insn %u: replaced reg %u with %u\n",
510 INSN_UID (insn
), REGNO (*loc
), REGNO (new_rtx
));
512 validate_change (insn
, loc
, new_rtx
, 1);
518 /* Similar to replace_oldest_value_reg, but *LOC contains an address.
519 Adapted from find_reloads_address_1. CL is INDEX_REG_CLASS or
520 BASE_REG_CLASS depending on how the register is being considered. */
523 replace_oldest_value_addr (rtx
*loc
, enum reg_class cl
,
524 enum machine_mode mode
, addr_space_t as
,
525 rtx insn
, struct value_data
*vd
)
528 RTX_CODE code
= GET_CODE (x
);
531 bool changed
= false;
536 if (DEBUG_INSN_P (insn
))
540 rtx orig_op0
= XEXP (x
, 0);
541 rtx orig_op1
= XEXP (x
, 1);
542 RTX_CODE code0
= GET_CODE (orig_op0
);
543 RTX_CODE code1
= GET_CODE (orig_op1
);
548 enum rtx_code index_code
= SCRATCH
;
550 if (GET_CODE (op0
) == SUBREG
)
552 op0
= SUBREG_REG (op0
);
553 code0
= GET_CODE (op0
);
556 if (GET_CODE (op1
) == SUBREG
)
558 op1
= SUBREG_REG (op1
);
559 code1
= GET_CODE (op1
);
562 if (code0
== MULT
|| code0
== SIGN_EXTEND
|| code0
== TRUNCATE
563 || code0
== ZERO_EXTEND
|| code1
== MEM
)
567 index_code
= GET_CODE (*locI
);
569 else if (code1
== MULT
|| code1
== SIGN_EXTEND
|| code1
== TRUNCATE
570 || code1
== ZERO_EXTEND
|| code0
== MEM
)
574 index_code
= GET_CODE (*locI
);
576 else if (code0
== CONST_INT
|| code0
== CONST
577 || code0
== SYMBOL_REF
|| code0
== LABEL_REF
)
580 index_code
= GET_CODE (XEXP (x
, 0));
582 else if (code1
== CONST_INT
|| code1
== CONST
583 || code1
== SYMBOL_REF
|| code1
== LABEL_REF
)
586 index_code
= GET_CODE (XEXP (x
, 1));
588 else if (code0
== REG
&& code1
== REG
)
591 unsigned regno0
= REGNO (op0
), regno1
= REGNO (op1
);
593 if (REGNO_OK_FOR_INDEX_P (regno1
)
594 && regno_ok_for_base_p (regno0
, mode
, as
, PLUS
, REG
))
596 else if (REGNO_OK_FOR_INDEX_P (regno0
)
597 && regno_ok_for_base_p (regno1
, mode
, as
, PLUS
, REG
))
599 else if (regno_ok_for_base_p (regno0
, mode
, as
, PLUS
, REG
)
600 || REGNO_OK_FOR_INDEX_P (regno1
))
602 else if (regno_ok_for_base_p (regno1
, mode
, as
, PLUS
, REG
))
607 locI
= &XEXP (x
, index_op
);
608 locB
= &XEXP (x
, !index_op
);
609 index_code
= GET_CODE (*locI
);
611 else if (code0
== REG
)
615 index_code
= GET_CODE (*locI
);
617 else if (code1
== REG
)
621 index_code
= GET_CODE (*locI
);
625 changed
|= replace_oldest_value_addr (locI
, INDEX_REG_CLASS
,
628 changed
|= replace_oldest_value_addr (locB
,
629 base_reg_class (mode
, as
, PLUS
,
644 return replace_oldest_value_mem (x
, insn
, vd
);
647 return replace_oldest_value_reg (loc
, cl
, insn
, vd
);
653 fmt
= GET_RTX_FORMAT (code
);
654 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
657 changed
|= replace_oldest_value_addr (&XEXP (x
, i
), cl
, mode
, as
,
659 else if (fmt
[i
] == 'E')
660 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
661 changed
|= replace_oldest_value_addr (&XVECEXP (x
, i
, j
), cl
,
668 /* Similar to replace_oldest_value_reg, but X contains a memory. */
671 replace_oldest_value_mem (rtx x
, rtx insn
, struct value_data
*vd
)
675 if (DEBUG_INSN_P (insn
))
678 cl
= base_reg_class (GET_MODE (x
), MEM_ADDR_SPACE (x
), MEM
, SCRATCH
);
680 return replace_oldest_value_addr (&XEXP (x
, 0), cl
,
681 GET_MODE (x
), MEM_ADDR_SPACE (x
),
685 /* Apply all queued updates for DEBUG_INSNs that change some reg to
689 apply_debug_insn_changes (struct value_data
*vd
, unsigned int regno
)
691 struct queued_debug_insn_change
*change
;
692 rtx last_insn
= vd
->e
[regno
].debug_insn_changes
->insn
;
694 for (change
= vd
->e
[regno
].debug_insn_changes
;
696 change
= change
->next
)
698 if (last_insn
!= change
->insn
)
700 apply_change_group ();
701 last_insn
= change
->insn
;
703 validate_change (change
->insn
, change
->loc
, change
->new_rtx
, 1);
705 apply_change_group ();
708 /* Called via for_each_rtx, for all used registers in a real
709 insn apply DEBUG_INSN changes that change registers to the
713 cprop_find_used_regs_1 (rtx
*loc
, void *data
)
717 struct value_data
*vd
= (struct value_data
*) data
;
718 if (vd
->e
[REGNO (*loc
)].debug_insn_changes
)
720 apply_debug_insn_changes (vd
, REGNO (*loc
));
721 free_debug_insn_changes (vd
, REGNO (*loc
));
727 /* Called via note_uses, for all used registers in a real insn
728 apply DEBUG_INSN changes that change registers to the used
732 cprop_find_used_regs (rtx
*loc
, void *vd
)
734 for_each_rtx (loc
, cprop_find_used_regs_1
, vd
);
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
, alt
, 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
);
774 if (! constrain_operands (1))
775 fatal_insn_not_found (insn
);
776 preprocess_constraints ();
777 alt
= which_alternative
;
778 n_ops
= recog_data
.n_operands
;
779 is_asm
= asm_noperands (PATTERN (insn
)) >= 0;
781 /* Simplify the code below by rewriting things to reflect
782 matching constraints. Also promote OP_OUT to OP_INOUT
783 in predicated instructions. */
785 predicated
= GET_CODE (PATTERN (insn
)) == COND_EXEC
;
786 for (i
= 0; i
< n_ops
; ++i
)
788 int matches
= recog_op_alt
[i
][alt
].matches
;
790 recog_op_alt
[i
][alt
].cl
= recog_op_alt
[matches
][alt
].cl
;
791 if (matches
>= 0 || recog_op_alt
[i
][alt
].matched
>= 0
792 || (predicated
&& recog_data
.operand_type
[i
] == OP_OUT
))
793 recog_data
.operand_type
[i
] = OP_INOUT
;
796 /* Apply changes to earlier DEBUG_INSNs if possible. */
797 if (vd
->n_debug_insn_changes
)
798 note_uses (&PATTERN (insn
), cprop_find_used_regs
, vd
);
800 /* For each earlyclobber operand, zap the value data. */
801 for (i
= 0; i
< n_ops
; i
++)
802 if (recog_op_alt
[i
][alt
].earlyclobber
)
803 kill_value (recog_data
.operand
[i
], vd
);
805 /* Within asms, a clobber cannot overlap inputs or outputs.
806 I wouldn't think this were true for regular insns, but
807 scan_rtx treats them like that... */
808 note_stores (PATTERN (insn
), kill_clobbered_value
, vd
);
810 /* Kill all auto-incremented values. */
811 /* ??? REG_INC is useless, since stack pushes aren't done that way. */
812 for_each_rtx (&PATTERN (insn
), kill_autoinc_value
, vd
);
814 /* Kill all early-clobbered operands. */
815 for (i
= 0; i
< n_ops
; i
++)
816 if (recog_op_alt
[i
][alt
].earlyclobber
)
817 kill_value (recog_data
.operand
[i
], vd
);
819 /* If we have dead sets in the insn, then we need to note these as we
821 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
823 if (REG_NOTE_KIND (link
) == REG_UNUSED
)
825 kill_value (XEXP (link
, 0), vd
);
826 /* Furthermore, if the insn looked like a single-set,
827 but the dead store kills the source value of that
828 set, then we can no-longer use the plain move
829 special case below. */
831 && reg_overlap_mentioned_p (XEXP (link
, 0), SET_SRC (set
)))
836 /* Special-case plain move instructions, since we may well
837 be able to do the move from a different register class. */
838 if (set
&& REG_P (SET_SRC (set
)))
840 rtx src
= SET_SRC (set
);
841 unsigned int regno
= REGNO (src
);
842 enum machine_mode mode
= GET_MODE (src
);
846 /* If we are accessing SRC in some mode other that what we
847 set it in, make sure that the replacement is valid. */
848 if (mode
!= vd
->e
[regno
].mode
)
850 if (hard_regno_nregs
[regno
][mode
]
851 > hard_regno_nregs
[regno
][vd
->e
[regno
].mode
])
852 goto no_move_special_case
;
854 /* And likewise, if we are narrowing on big endian the transformation
856 if (hard_regno_nregs
[regno
][mode
]
857 < hard_regno_nregs
[regno
][vd
->e
[regno
].mode
]
858 && (GET_MODE_SIZE (vd
->e
[regno
].mode
) > UNITS_PER_WORD
859 ? WORDS_BIG_ENDIAN
: BYTES_BIG_ENDIAN
))
860 goto no_move_special_case
;
863 /* If the destination is also a register, try to find a source
864 register in the same class. */
865 if (REG_P (SET_DEST (set
)))
867 new_rtx
= find_oldest_value_reg (REGNO_REG_CLASS (regno
), src
, vd
);
868 if (new_rtx
&& validate_change (insn
, &SET_SRC (set
), new_rtx
, 0))
872 "insn %u: replaced reg %u with %u\n",
873 INSN_UID (insn
), regno
, REGNO (new_rtx
));
875 goto did_replacement
;
877 /* We need to re-extract as validate_change clobbers
880 if (! constrain_operands (1))
881 fatal_insn_not_found (insn
);
882 preprocess_constraints ();
885 /* Otherwise, try all valid registers and see if its valid. */
886 for (i
= vd
->e
[regno
].oldest_regno
; i
!= regno
;
887 i
= vd
->e
[i
].next_regno
)
889 new_rtx
= maybe_mode_change (vd
->e
[i
].mode
, vd
->e
[regno
].mode
,
891 if (new_rtx
!= NULL_RTX
)
893 if (validate_change (insn
, &SET_SRC (set
), new_rtx
, 0))
895 ORIGINAL_REGNO (new_rtx
) = ORIGINAL_REGNO (src
);
896 REG_ATTRS (new_rtx
) = REG_ATTRS (src
);
897 REG_POINTER (new_rtx
) = REG_POINTER (src
);
900 "insn %u: replaced reg %u with %u\n",
901 INSN_UID (insn
), regno
, REGNO (new_rtx
));
903 goto did_replacement
;
905 /* We need to re-extract as validate_change clobbers
908 if (! constrain_operands (1))
909 fatal_insn_not_found (insn
);
910 preprocess_constraints ();
914 no_move_special_case
:
916 any_replacements
= false;
918 /* For each input operand, replace a hard register with the
919 eldest live copy that's in an appropriate register class. */
920 for (i
= 0; i
< n_ops
; i
++)
924 /* Don't scan match_operand here, since we've no reg class
925 information to pass down. Any operands that we could
926 substitute in will be represented elsewhere. */
927 if (recog_data
.constraints
[i
][0] == '\0')
930 /* Don't replace in asms intentionally referencing hard regs. */
931 if (is_asm
&& REG_P (recog_data
.operand
[i
])
932 && (REGNO (recog_data
.operand
[i
])
933 == ORIGINAL_REGNO (recog_data
.operand
[i
])))
936 if (recog_data
.operand_type
[i
] == OP_IN
)
938 if (recog_op_alt
[i
][alt
].is_address
)
940 = replace_oldest_value_addr (recog_data
.operand_loc
[i
],
941 recog_op_alt
[i
][alt
].cl
,
942 VOIDmode
, ADDR_SPACE_GENERIC
,
944 else if (REG_P (recog_data
.operand
[i
]))
946 = replace_oldest_value_reg (recog_data
.operand_loc
[i
],
947 recog_op_alt
[i
][alt
].cl
,
949 else if (MEM_P (recog_data
.operand
[i
]))
950 replaced
[i
] = replace_oldest_value_mem (recog_data
.operand
[i
],
953 else if (MEM_P (recog_data
.operand
[i
]))
954 replaced
[i
] = replace_oldest_value_mem (recog_data
.operand
[i
],
957 /* If we performed any replacement, update match_dups. */
963 new_rtx
= *recog_data
.operand_loc
[i
];
964 recog_data
.operand
[i
] = new_rtx
;
965 for (j
= 0; j
< recog_data
.n_dups
; j
++)
966 if (recog_data
.dup_num
[j
] == i
)
967 validate_unshare_change (insn
, recog_data
.dup_loc
[j
], new_rtx
, 1);
969 any_replacements
= true;
973 if (any_replacements
)
975 if (! apply_change_group ())
977 for (i
= 0; i
< n_ops
; i
++)
980 rtx old
= *recog_data
.operand_loc
[i
];
981 recog_data
.operand
[i
] = old
;
986 "insn %u: reg replacements not verified\n",
996 anything_changed
= true;
998 /* If something changed, perhaps further changes to earlier
999 DEBUG_INSNs can be applied. */
1000 if (vd
->n_debug_insn_changes
)
1001 note_uses (&PATTERN (insn
), cprop_find_used_regs
, vd
);
1005 ksvd
.ignore_set_reg
= NULL_RTX
;
1007 /* Clobber call-clobbered registers. */
1010 unsigned int set_regno
= INVALID_REGNUM
;
1011 unsigned int set_nregs
= 0;
1015 for (exp
= CALL_INSN_FUNCTION_USAGE (insn
); exp
; exp
= XEXP (exp
, 1))
1017 rtx x
= XEXP (exp
, 0);
1018 if (GET_CODE (x
) == SET
)
1020 rtx dest
= SET_DEST (x
);
1021 kill_value (dest
, vd
);
1022 set_value_regno (REGNO (dest
), GET_MODE (dest
), vd
);
1023 copy_value (dest
, SET_SRC (x
), vd
);
1024 ksvd
.ignore_set_reg
= dest
;
1025 set_regno
= REGNO (dest
);
1027 = hard_regno_nregs
[set_regno
][GET_MODE (dest
)];
1032 for (regno
= 0; regno
< FIRST_PSEUDO_REGISTER
; regno
++)
1033 if ((TEST_HARD_REG_BIT (regs_invalidated_by_call
, regno
)
1034 || HARD_REGNO_CALL_PART_CLOBBERED (regno
, vd
->e
[regno
].mode
))
1035 && (regno
< set_regno
|| regno
>= set_regno
+ set_nregs
))
1036 kill_value_regno (regno
, 1, vd
);
1038 /* If SET was seen in CALL_INSN_FUNCTION_USAGE, and SET_SRC
1039 of the SET isn't in regs_invalidated_by_call hard reg set,
1040 but instead among CLOBBERs on the CALL_INSN, we could wrongly
1041 assume the value in it is still live. */
1042 if (ksvd
.ignore_set_reg
)
1044 note_stores (PATTERN (insn
), kill_clobbered_value
, vd
);
1045 for (exp
= CALL_INSN_FUNCTION_USAGE (insn
);
1047 exp
= XEXP (exp
, 1))
1049 rtx x
= XEXP (exp
, 0);
1050 if (GET_CODE (x
) == CLOBBER
)
1051 kill_value (SET_DEST (x
), vd
);
1056 /* Notice stores. */
1057 note_stores (PATTERN (insn
), kill_set_value
, &ksvd
);
1059 /* Notice copies. */
1060 if (set
&& REG_P (SET_DEST (set
)) && REG_P (SET_SRC (set
)))
1061 copy_value (SET_DEST (set
), SET_SRC (set
), vd
);
1063 if (insn
== BB_END (bb
))
1067 return anything_changed
;
1070 /* Main entry point for the forward copy propagation optimization. */
1073 copyprop_hardreg_forward (void)
1075 struct value_data
*all_vd
;
1078 bool analyze_called
= false;
1080 all_vd
= XNEWVEC (struct value_data
, last_basic_block_for_fn (cfun
));
1082 visited
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
1083 bitmap_clear (visited
);
1085 if (MAY_HAVE_DEBUG_INSNS
)
1086 debug_insn_changes_pool
1087 = create_alloc_pool ("debug insn changes pool",
1088 sizeof (struct queued_debug_insn_change
), 256);
1090 FOR_EACH_BB_FN (bb
, cfun
)
1092 bitmap_set_bit (visited
, bb
->index
);
1094 /* If a block has a single predecessor, that we've already
1095 processed, begin with the value data that was live at
1096 the end of the predecessor block. */
1097 /* ??? Ought to use more intelligent queuing of blocks. */
1098 if (single_pred_p (bb
)
1099 && bitmap_bit_p (visited
, single_pred (bb
)->index
)
1100 && ! (single_pred_edge (bb
)->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
)))
1102 all_vd
[bb
->index
] = all_vd
[single_pred (bb
)->index
];
1103 if (all_vd
[bb
->index
].n_debug_insn_changes
)
1107 for (regno
= 0; regno
< FIRST_PSEUDO_REGISTER
; regno
++)
1109 if (all_vd
[bb
->index
].e
[regno
].debug_insn_changes
)
1111 all_vd
[bb
->index
].e
[regno
].debug_insn_changes
= NULL
;
1112 if (--all_vd
[bb
->index
].n_debug_insn_changes
== 0)
1119 init_value_data (all_vd
+ bb
->index
);
1121 copyprop_hardreg_forward_1 (bb
, all_vd
+ bb
->index
);
1124 if (MAY_HAVE_DEBUG_INSNS
)
1126 FOR_EACH_BB_FN (bb
, cfun
)
1127 if (bitmap_bit_p (visited
, bb
->index
)
1128 && all_vd
[bb
->index
].n_debug_insn_changes
)
1133 if (!analyze_called
)
1136 analyze_called
= true;
1138 live
= df_get_live_out (bb
);
1139 for (regno
= 0; regno
< FIRST_PSEUDO_REGISTER
; regno
++)
1140 if (all_vd
[bb
->index
].e
[regno
].debug_insn_changes
)
1142 if (REGNO_REG_SET_P (live
, regno
))
1143 apply_debug_insn_changes (all_vd
+ bb
->index
, regno
);
1144 if (all_vd
[bb
->index
].n_debug_insn_changes
== 0)
1149 free_alloc_pool (debug_insn_changes_pool
);
1152 sbitmap_free (visited
);
1157 /* Dump the value chain data to stderr. */
1160 debug_value_data (struct value_data
*vd
)
1165 CLEAR_HARD_REG_SET (set
);
1167 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1168 if (vd
->e
[i
].oldest_regno
== i
)
1170 if (vd
->e
[i
].mode
== VOIDmode
)
1172 if (vd
->e
[i
].next_regno
!= INVALID_REGNUM
)
1173 fprintf (stderr
, "[%u] Bad next_regno for empty chain (%u)\n",
1174 i
, vd
->e
[i
].next_regno
);
1178 SET_HARD_REG_BIT (set
, i
);
1179 fprintf (stderr
, "[%u %s] ", i
, GET_MODE_NAME (vd
->e
[i
].mode
));
1181 for (j
= vd
->e
[i
].next_regno
;
1182 j
!= INVALID_REGNUM
;
1183 j
= vd
->e
[j
].next_regno
)
1185 if (TEST_HARD_REG_BIT (set
, j
))
1187 fprintf (stderr
, "[%u] Loop in regno chain\n", j
);
1191 if (vd
->e
[j
].oldest_regno
!= i
)
1193 fprintf (stderr
, "[%u] Bad oldest_regno (%u)\n",
1194 j
, vd
->e
[j
].oldest_regno
);
1197 SET_HARD_REG_BIT (set
, j
);
1198 fprintf (stderr
, "[%u %s] ", j
, GET_MODE_NAME (vd
->e
[j
].mode
));
1200 fputc ('\n', stderr
);
1203 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1204 if (! TEST_HARD_REG_BIT (set
, i
)
1205 && (vd
->e
[i
].mode
!= VOIDmode
1206 || vd
->e
[i
].oldest_regno
!= i
1207 || vd
->e
[i
].next_regno
!= INVALID_REGNUM
))
1208 fprintf (stderr
, "[%u] Non-empty reg in chain (%s %u %i)\n",
1209 i
, GET_MODE_NAME (vd
->e
[i
].mode
), vd
->e
[i
].oldest_regno
,
1210 vd
->e
[i
].next_regno
);
1213 #ifdef ENABLE_CHECKING
1215 validate_value_data (struct value_data
*vd
)
1220 CLEAR_HARD_REG_SET (set
);
1222 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1223 if (vd
->e
[i
].oldest_regno
== i
)
1225 if (vd
->e
[i
].mode
== VOIDmode
)
1227 if (vd
->e
[i
].next_regno
!= INVALID_REGNUM
)
1228 internal_error ("validate_value_data: [%u] Bad next_regno for empty chain (%u)",
1229 i
, vd
->e
[i
].next_regno
);
1233 SET_HARD_REG_BIT (set
, i
);
1235 for (j
= vd
->e
[i
].next_regno
;
1236 j
!= INVALID_REGNUM
;
1237 j
= vd
->e
[j
].next_regno
)
1239 if (TEST_HARD_REG_BIT (set
, j
))
1240 internal_error ("validate_value_data: Loop in regno chain (%u)",
1242 if (vd
->e
[j
].oldest_regno
!= i
)
1243 internal_error ("validate_value_data: [%u] Bad oldest_regno (%u)",
1244 j
, vd
->e
[j
].oldest_regno
);
1246 SET_HARD_REG_BIT (set
, j
);
1250 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1251 if (! TEST_HARD_REG_BIT (set
, i
)
1252 && (vd
->e
[i
].mode
!= VOIDmode
1253 || vd
->e
[i
].oldest_regno
!= i
1254 || vd
->e
[i
].next_regno
!= INVALID_REGNUM
))
1255 internal_error ("validate_value_data: [%u] Non-empty reg in chain (%s %u %i)",
1256 i
, GET_MODE_NAME (vd
->e
[i
].mode
), vd
->e
[i
].oldest_regno
,
1257 vd
->e
[i
].next_regno
);
1262 gate_handle_cprop (void)
1264 return (optimize
> 0 && (flag_cprop_registers
));
1270 const pass_data pass_data_cprop_hardreg
=
1272 RTL_PASS
, /* type */
1273 "cprop_hardreg", /* name */
1274 OPTGROUP_NONE
, /* optinfo_flags */
1275 true, /* has_gate */
1276 true, /* has_execute */
1277 TV_CPROP_REGISTERS
, /* tv_id */
1278 0, /* properties_required */
1279 0, /* properties_provided */
1280 0, /* properties_destroyed */
1281 0, /* todo_flags_start */
1282 ( TODO_df_finish
| TODO_verify_rtl_sharing
), /* todo_flags_finish */
1285 class pass_cprop_hardreg
: public rtl_opt_pass
1288 pass_cprop_hardreg (gcc::context
*ctxt
)
1289 : rtl_opt_pass (pass_data_cprop_hardreg
, ctxt
)
1292 /* opt_pass methods: */
1293 bool gate () { return gate_handle_cprop (); }
1294 unsigned int execute () { return copyprop_hardreg_forward (); }
1296 }; // class pass_cprop_hardreg
1301 make_pass_cprop_hardreg (gcc::context
*ctxt
)
1303 return new pass_cprop_hardreg (ctxt
);