1 /* Copy propagation on hard registers for the GNU compiler.
2 Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009,
3 2010 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
14 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
15 License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
27 #include "insn-config.h"
29 #include "addresses.h"
30 #include "hard-reg-set.h"
31 #include "basic-block.h"
37 #include "diagnostic-core.h"
40 #include "tree-pass.h"
43 /* The following code does forward propagation of hard register copies.
44 The object is to eliminate as many dependencies as possible, so that
45 we have the most scheduling freedom. As a side effect, we also clean
46 up some silly register allocation decisions made by reload. This
47 code may be obsoleted by a new register allocator. */
49 /* DEBUG_INSNs aren't changed right away, as doing so might extend the
50 lifetime of a register and get the DEBUG_INSN subsequently reset.
51 So they are queued instead, and updated only when the register is
52 used in some subsequent real insn before it is set. */
53 struct queued_debug_insn_change
55 struct queued_debug_insn_change
*next
;
61 /* For each register, we have a list of registers that contain the same
62 value. The OLDEST_REGNO field points to the head of the list, and
63 the NEXT_REGNO field runs through the list. The MODE field indicates
64 what mode the data is known to be in; this field is VOIDmode when the
65 register is not known to contain valid data. */
67 struct value_data_entry
69 enum machine_mode mode
;
70 unsigned int oldest_regno
;
71 unsigned int next_regno
;
72 struct queued_debug_insn_change
*debug_insn_changes
;
77 struct value_data_entry e
[FIRST_PSEUDO_REGISTER
];
78 unsigned int max_value_regs
;
79 unsigned int n_debug_insn_changes
;
82 static alloc_pool debug_insn_changes_pool
;
84 static void kill_value_one_regno (unsigned, struct value_data
*);
85 static void kill_value_regno (unsigned, unsigned, struct value_data
*);
86 static void kill_value (rtx
, struct value_data
*);
87 static void set_value_regno (unsigned, enum machine_mode
, struct value_data
*);
88 static void init_value_data (struct value_data
*);
89 static void kill_clobbered_value (rtx
, const_rtx
, void *);
90 static void kill_set_value (rtx
, const_rtx
, void *);
91 static int kill_autoinc_value (rtx
*, void *);
92 static void copy_value (rtx
, rtx
, struct value_data
*);
93 static bool mode_change_ok (enum machine_mode
, enum machine_mode
,
95 static rtx
maybe_mode_change (enum machine_mode
, enum machine_mode
,
96 enum machine_mode
, unsigned int, unsigned int);
97 static rtx
find_oldest_value_reg (enum reg_class
, rtx
, struct value_data
*);
98 static bool replace_oldest_value_reg (rtx
*, enum reg_class
, rtx
,
100 static bool replace_oldest_value_addr (rtx
*, enum reg_class
,
101 enum machine_mode
, rtx
,
102 struct value_data
*);
103 static bool replace_oldest_value_mem (rtx
, rtx
, struct value_data
*);
104 static bool copyprop_hardreg_forward_1 (basic_block
, struct value_data
*);
105 extern void debug_value_data (struct value_data
*);
106 #ifdef ENABLE_CHECKING
107 static void validate_value_data (struct value_data
*);
110 /* Free all queued updates for DEBUG_INSNs that change some reg to
114 free_debug_insn_changes (struct value_data
*vd
, unsigned int regno
)
116 struct queued_debug_insn_change
*cur
, *next
;
117 for (cur
= vd
->e
[regno
].debug_insn_changes
; cur
; cur
= next
)
120 --vd
->n_debug_insn_changes
;
121 pool_free (debug_insn_changes_pool
, cur
);
123 vd
->e
[regno
].debug_insn_changes
= NULL
;
126 /* Kill register REGNO. This involves removing it from any value
127 lists, and resetting the value mode to VOIDmode. This is only a
128 helper function; it does not handle any hard registers overlapping
132 kill_value_one_regno (unsigned int regno
, struct value_data
*vd
)
134 unsigned int i
, next
;
136 if (vd
->e
[regno
].oldest_regno
!= regno
)
138 for (i
= vd
->e
[regno
].oldest_regno
;
139 vd
->e
[i
].next_regno
!= regno
;
140 i
= vd
->e
[i
].next_regno
)
142 vd
->e
[i
].next_regno
= vd
->e
[regno
].next_regno
;
144 else if ((next
= vd
->e
[regno
].next_regno
) != INVALID_REGNUM
)
146 for (i
= next
; i
!= INVALID_REGNUM
; i
= vd
->e
[i
].next_regno
)
147 vd
->e
[i
].oldest_regno
= next
;
150 vd
->e
[regno
].mode
= VOIDmode
;
151 vd
->e
[regno
].oldest_regno
= regno
;
152 vd
->e
[regno
].next_regno
= INVALID_REGNUM
;
153 if (vd
->e
[regno
].debug_insn_changes
)
154 free_debug_insn_changes (vd
, regno
);
156 #ifdef ENABLE_CHECKING
157 validate_value_data (vd
);
161 /* Kill the value in register REGNO for NREGS, and any other registers
162 whose values overlap. */
165 kill_value_regno (unsigned int regno
, unsigned int nregs
,
166 struct value_data
*vd
)
170 /* Kill the value we're told to kill. */
171 for (j
= 0; j
< nregs
; ++j
)
172 kill_value_one_regno (regno
+ j
, vd
);
174 /* Kill everything that overlapped what we're told to kill. */
175 if (regno
< vd
->max_value_regs
)
178 j
= regno
- vd
->max_value_regs
;
179 for (; j
< regno
; ++j
)
182 if (vd
->e
[j
].mode
== VOIDmode
)
184 n
= hard_regno_nregs
[j
][vd
->e
[j
].mode
];
186 for (i
= 0; i
< n
; ++i
)
187 kill_value_one_regno (j
+ i
, vd
);
191 /* Kill X. This is a convenience function wrapping kill_value_regno
192 so that we mind the mode the register is in. */
195 kill_value (rtx x
, struct value_data
*vd
)
199 if (GET_CODE (x
) == SUBREG
)
201 x
= simplify_subreg (GET_MODE (x
), SUBREG_REG (x
),
202 GET_MODE (SUBREG_REG (x
)), SUBREG_BYTE (x
));
204 x
= SUBREG_REG (orig_rtx
);
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 /* Called through note_stores. If X is set, not clobbered, kill its
258 current value and install it as the root of its own value list. */
261 kill_set_value (rtx x
, const_rtx set
, void *data
)
263 struct value_data
*const vd
= (struct value_data
*) data
;
264 if (GET_CODE (set
) != CLOBBER
)
268 set_value_regno (REGNO (x
), GET_MODE (x
), vd
);
272 /* Called through for_each_rtx. Kill any register used as the base of an
273 auto-increment expression, and install that register as the root of its
277 kill_autoinc_value (rtx
*px
, void *data
)
280 struct value_data
*const vd
= (struct value_data
*) data
;
282 if (GET_RTX_CLASS (GET_CODE (x
)) == RTX_AUTOINC
)
286 set_value_regno (REGNO (x
), GET_MODE (x
), vd
);
293 /* Assert that SRC has been copied to DEST. Adjust the data structures
294 to reflect that SRC contains an older copy of the shared value. */
297 copy_value (rtx dest
, rtx src
, struct value_data
*vd
)
299 unsigned int dr
= REGNO (dest
);
300 unsigned int sr
= REGNO (src
);
304 /* ??? At present, it's possible to see noop sets. It'd be nice if
305 this were cleaned up beforehand... */
309 /* Do not propagate copies to the stack pointer, as that can leave
310 memory accesses with no scheduling dependency on the stack update. */
311 if (dr
== STACK_POINTER_REGNUM
)
314 /* Likewise with the frame pointer, if we're using one. */
315 if (frame_pointer_needed
&& dr
== HARD_FRAME_POINTER_REGNUM
)
318 /* Do not propagate copies to fixed or global registers, patterns
319 can be relying to see particular fixed register or users can
320 expect the chosen global register in asm. */
321 if (fixed_regs
[dr
] || global_regs
[dr
])
324 /* If SRC and DEST overlap, don't record anything. */
325 dn
= hard_regno_nregs
[dr
][GET_MODE (dest
)];
326 sn
= hard_regno_nregs
[sr
][GET_MODE (dest
)];
327 if ((dr
> sr
&& dr
< sr
+ sn
)
328 || (sr
> dr
&& sr
< dr
+ dn
))
331 /* If SRC had no assigned mode (i.e. we didn't know it was live)
332 assign it now and assume the value came from an input argument
334 if (vd
->e
[sr
].mode
== VOIDmode
)
335 set_value_regno (sr
, vd
->e
[dr
].mode
, vd
);
337 /* If we are narrowing the input to a smaller number of hard regs,
338 and it is in big endian, we are really extracting a high part.
339 Since we generally associate a low part of a value with the value itself,
340 we must not do the same for the high part.
341 Note we can still get low parts for the same mode combination through
342 a two-step copy involving differently sized hard regs.
343 Assume hard regs fr* are 32 bits bits each, while r* are 64 bits each:
344 (set (reg:DI r0) (reg:DI fr0))
345 (set (reg:SI fr2) (reg:SI r0))
346 loads the low part of (reg:DI fr0) - i.e. fr1 - into fr2, while:
347 (set (reg:SI fr2) (reg:SI fr0))
348 loads the high part of (reg:DI fr0) into fr2.
350 We can't properly represent the latter case in our tables, so don't
351 record anything then. */
352 else if (sn
< (unsigned int) hard_regno_nregs
[sr
][vd
->e
[sr
].mode
]
353 && (GET_MODE_SIZE (vd
->e
[sr
].mode
) > UNITS_PER_WORD
354 ? WORDS_BIG_ENDIAN
: BYTES_BIG_ENDIAN
))
357 /* If SRC had been assigned a mode narrower than the copy, we can't
358 link DEST into the chain, because not all of the pieces of the
359 copy came from oldest_regno. */
360 else if (sn
> (unsigned int) hard_regno_nregs
[sr
][vd
->e
[sr
].mode
])
363 /* Link DR at the end of the value chain used by SR. */
365 vd
->e
[dr
].oldest_regno
= vd
->e
[sr
].oldest_regno
;
367 for (i
= sr
; vd
->e
[i
].next_regno
!= INVALID_REGNUM
; i
= vd
->e
[i
].next_regno
)
369 vd
->e
[i
].next_regno
= dr
;
371 #ifdef ENABLE_CHECKING
372 validate_value_data (vd
);
376 /* Return true if a mode change from ORIG to NEW is allowed for REGNO. */
379 mode_change_ok (enum machine_mode orig_mode
, enum machine_mode new_mode
,
380 unsigned int regno ATTRIBUTE_UNUSED
)
382 if (GET_MODE_SIZE (orig_mode
) < GET_MODE_SIZE (new_mode
))
385 #ifdef CANNOT_CHANGE_MODE_CLASS
386 return !REG_CANNOT_CHANGE_MODE_P (regno
, orig_mode
, new_mode
);
392 /* Register REGNO was originally set in ORIG_MODE. It - or a copy of it -
393 was copied in COPY_MODE to COPY_REGNO, and then COPY_REGNO was accessed
395 Return a NEW_MODE rtx for REGNO if that's OK, otherwise return NULL_RTX. */
398 maybe_mode_change (enum machine_mode orig_mode
, enum machine_mode copy_mode
,
399 enum machine_mode new_mode
, unsigned int regno
,
400 unsigned int copy_regno ATTRIBUTE_UNUSED
)
402 if (GET_MODE_SIZE (copy_mode
) < GET_MODE_SIZE (orig_mode
)
403 && GET_MODE_SIZE (copy_mode
) < GET_MODE_SIZE (new_mode
))
406 if (orig_mode
== new_mode
)
407 return gen_rtx_raw_REG (new_mode
, regno
);
408 else if (mode_change_ok (orig_mode
, new_mode
, regno
))
410 int copy_nregs
= hard_regno_nregs
[copy_regno
][copy_mode
];
411 int use_nregs
= hard_regno_nregs
[copy_regno
][new_mode
];
413 = GET_MODE_SIZE (copy_mode
) / copy_nregs
* (copy_nregs
- use_nregs
);
415 = GET_MODE_SIZE (orig_mode
) - GET_MODE_SIZE (new_mode
) - copy_offset
;
416 int byteoffset
= offset
% UNITS_PER_WORD
;
417 int wordoffset
= offset
- byteoffset
;
419 offset
= ((WORDS_BIG_ENDIAN
? wordoffset
: 0)
420 + (BYTES_BIG_ENDIAN
? byteoffset
: 0));
421 regno
+= subreg_regno_offset (regno
, orig_mode
, offset
, new_mode
);
422 if (HARD_REGNO_MODE_OK (regno
, new_mode
))
423 return gen_rtx_raw_REG (new_mode
, regno
);
428 /* Find the oldest copy of the value contained in REGNO that is in
429 register class CL and has mode MODE. If found, return an rtx
430 of that oldest register, otherwise return NULL. */
433 find_oldest_value_reg (enum reg_class cl
, rtx reg
, struct value_data
*vd
)
435 unsigned int regno
= REGNO (reg
);
436 enum machine_mode mode
= GET_MODE (reg
);
439 /* If we are accessing REG in some mode other that what we set it in,
440 make sure that the replacement is valid. In particular, consider
441 (set (reg:DI r11) (...))
442 (set (reg:SI r9) (reg:SI r11))
443 (set (reg:SI r10) (...))
444 (set (...) (reg:DI r9))
445 Replacing r9 with r11 is invalid. */
446 if (mode
!= vd
->e
[regno
].mode
)
448 if (hard_regno_nregs
[regno
][mode
]
449 > hard_regno_nregs
[regno
][vd
->e
[regno
].mode
])
453 for (i
= vd
->e
[regno
].oldest_regno
; i
!= regno
; i
= vd
->e
[i
].next_regno
)
455 enum machine_mode oldmode
= vd
->e
[i
].mode
;
458 if (!in_hard_reg_set_p (reg_class_contents
[cl
], mode
, i
))
461 new_rtx
= maybe_mode_change (oldmode
, vd
->e
[regno
].mode
, mode
, i
, regno
);
464 ORIGINAL_REGNO (new_rtx
) = ORIGINAL_REGNO (reg
);
465 REG_ATTRS (new_rtx
) = REG_ATTRS (reg
);
466 REG_POINTER (new_rtx
) = REG_POINTER (reg
);
474 /* If possible, replace the register at *LOC with the oldest register
475 in register class CL. Return true if successfully replaced. */
478 replace_oldest_value_reg (rtx
*loc
, enum reg_class cl
, rtx insn
,
479 struct value_data
*vd
)
481 rtx new_rtx
= find_oldest_value_reg (cl
, *loc
, vd
);
484 if (DEBUG_INSN_P (insn
))
486 struct queued_debug_insn_change
*change
;
489 fprintf (dump_file
, "debug_insn %u: queued replacing reg %u with %u\n",
490 INSN_UID (insn
), REGNO (*loc
), REGNO (new_rtx
));
492 change
= (struct queued_debug_insn_change
*)
493 pool_alloc (debug_insn_changes_pool
);
494 change
->next
= vd
->e
[REGNO (new_rtx
)].debug_insn_changes
;
497 change
->new_rtx
= new_rtx
;
498 vd
->e
[REGNO (new_rtx
)].debug_insn_changes
= change
;
499 ++vd
->n_debug_insn_changes
;
503 fprintf (dump_file
, "insn %u: replaced reg %u with %u\n",
504 INSN_UID (insn
), REGNO (*loc
), REGNO (new_rtx
));
506 validate_change (insn
, loc
, new_rtx
, 1);
512 /* Similar to replace_oldest_value_reg, but *LOC contains an address.
513 Adapted from find_reloads_address_1. CL is INDEX_REG_CLASS or
514 BASE_REG_CLASS depending on how the register is being considered. */
517 replace_oldest_value_addr (rtx
*loc
, enum reg_class cl
,
518 enum machine_mode mode
, rtx insn
,
519 struct value_data
*vd
)
522 RTX_CODE code
= GET_CODE (x
);
525 bool changed
= false;
530 if (DEBUG_INSN_P (insn
))
534 rtx orig_op0
= XEXP (x
, 0);
535 rtx orig_op1
= XEXP (x
, 1);
536 RTX_CODE code0
= GET_CODE (orig_op0
);
537 RTX_CODE code1
= GET_CODE (orig_op1
);
542 enum rtx_code index_code
= SCRATCH
;
544 if (GET_CODE (op0
) == SUBREG
)
546 op0
= SUBREG_REG (op0
);
547 code0
= GET_CODE (op0
);
550 if (GET_CODE (op1
) == SUBREG
)
552 op1
= SUBREG_REG (op1
);
553 code1
= GET_CODE (op1
);
556 if (code0
== MULT
|| code0
== SIGN_EXTEND
|| code0
== TRUNCATE
557 || code0
== ZERO_EXTEND
|| code1
== MEM
)
561 index_code
= GET_CODE (*locI
);
563 else if (code1
== MULT
|| code1
== SIGN_EXTEND
|| code1
== TRUNCATE
564 || code1
== ZERO_EXTEND
|| code0
== MEM
)
568 index_code
= GET_CODE (*locI
);
570 else if (code0
== CONST_INT
|| code0
== CONST
571 || code0
== SYMBOL_REF
|| code0
== LABEL_REF
)
574 index_code
= GET_CODE (XEXP (x
, 0));
576 else if (code1
== CONST_INT
|| code1
== CONST
577 || code1
== SYMBOL_REF
|| code1
== LABEL_REF
)
580 index_code
= GET_CODE (XEXP (x
, 1));
582 else if (code0
== REG
&& code1
== REG
)
585 unsigned regno0
= REGNO (op0
), regno1
= REGNO (op1
);
587 if (REGNO_OK_FOR_INDEX_P (regno1
)
588 && regno_ok_for_base_p (regno0
, mode
, PLUS
, REG
))
590 else if (REGNO_OK_FOR_INDEX_P (regno0
)
591 && regno_ok_for_base_p (regno1
, mode
, PLUS
, REG
))
593 else if (regno_ok_for_base_p (regno0
, mode
, PLUS
, REG
)
594 || REGNO_OK_FOR_INDEX_P (regno1
))
596 else if (regno_ok_for_base_p (regno1
, mode
, PLUS
, REG
))
601 locI
= &XEXP (x
, index_op
);
602 locB
= &XEXP (x
, !index_op
);
603 index_code
= GET_CODE (*locI
);
605 else if (code0
== REG
)
609 index_code
= GET_CODE (*locI
);
611 else if (code1
== REG
)
615 index_code
= GET_CODE (*locI
);
619 changed
|= replace_oldest_value_addr (locI
, INDEX_REG_CLASS
, mode
,
622 changed
|= replace_oldest_value_addr (locB
,
623 base_reg_class (mode
, PLUS
,
638 return replace_oldest_value_mem (x
, insn
, vd
);
641 return replace_oldest_value_reg (loc
, cl
, insn
, vd
);
647 fmt
= GET_RTX_FORMAT (code
);
648 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
651 changed
|= replace_oldest_value_addr (&XEXP (x
, i
), cl
, mode
,
653 else if (fmt
[i
] == 'E')
654 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
655 changed
|= replace_oldest_value_addr (&XVECEXP (x
, i
, j
), cl
,
662 /* Similar to replace_oldest_value_reg, but X contains a memory. */
665 replace_oldest_value_mem (rtx x
, rtx insn
, struct value_data
*vd
)
669 if (DEBUG_INSN_P (insn
))
672 cl
= base_reg_class (GET_MODE (x
), MEM
, SCRATCH
);
674 return replace_oldest_value_addr (&XEXP (x
, 0), cl
,
675 GET_MODE (x
), insn
, vd
);
678 /* Apply all queued updates for DEBUG_INSNs that change some reg to
682 apply_debug_insn_changes (struct value_data
*vd
, unsigned int regno
)
684 struct queued_debug_insn_change
*change
;
685 rtx last_insn
= vd
->e
[regno
].debug_insn_changes
->insn
;
687 for (change
= vd
->e
[regno
].debug_insn_changes
;
689 change
= change
->next
)
691 if (last_insn
!= change
->insn
)
693 apply_change_group ();
694 last_insn
= change
->insn
;
696 validate_change (change
->insn
, change
->loc
, change
->new_rtx
, 1);
698 apply_change_group ();
701 /* Called via for_each_rtx, for all used registers in a real
702 insn apply DEBUG_INSN changes that change registers to the
706 cprop_find_used_regs_1 (rtx
*loc
, void *data
)
710 struct value_data
*vd
= (struct value_data
*) data
;
711 if (vd
->e
[REGNO (*loc
)].debug_insn_changes
)
713 apply_debug_insn_changes (vd
, REGNO (*loc
));
714 free_debug_insn_changes (vd
, REGNO (*loc
));
720 /* Called via note_uses, for all used registers in a real insn
721 apply DEBUG_INSN changes that change registers to the used
725 cprop_find_used_regs (rtx
*loc
, void *vd
)
727 for_each_rtx (loc
, cprop_find_used_regs_1
, vd
);
730 /* Perform the forward copy propagation on basic block BB. */
733 copyprop_hardreg_forward_1 (basic_block bb
, struct value_data
*vd
)
735 bool anything_changed
= false;
738 for (insn
= BB_HEAD (bb
); ; insn
= NEXT_INSN (insn
))
740 int n_ops
, i
, alt
, predicated
;
741 bool is_asm
, any_replacements
;
743 bool replaced
[MAX_RECOG_OPERANDS
];
744 bool changed
= false;
746 if (!NONDEBUG_INSN_P (insn
))
748 if (DEBUG_INSN_P (insn
))
750 rtx loc
= INSN_VAR_LOCATION_LOC (insn
);
751 if (!VAR_LOC_UNKNOWN_P (loc
))
752 replace_oldest_value_addr (&INSN_VAR_LOCATION_LOC (insn
),
753 ALL_REGS
, GET_MODE (loc
),
757 if (insn
== BB_END (bb
))
763 set
= single_set (insn
);
765 if (! constrain_operands (1))
766 fatal_insn_not_found (insn
);
767 preprocess_constraints ();
768 alt
= which_alternative
;
769 n_ops
= recog_data
.n_operands
;
770 is_asm
= asm_noperands (PATTERN (insn
)) >= 0;
772 /* Simplify the code below by rewriting things to reflect
773 matching constraints. Also promote OP_OUT to OP_INOUT
774 in predicated instructions. */
776 predicated
= GET_CODE (PATTERN (insn
)) == COND_EXEC
;
777 for (i
= 0; i
< n_ops
; ++i
)
779 int matches
= recog_op_alt
[i
][alt
].matches
;
781 recog_op_alt
[i
][alt
].cl
= recog_op_alt
[matches
][alt
].cl
;
782 if (matches
>= 0 || recog_op_alt
[i
][alt
].matched
>= 0
783 || (predicated
&& recog_data
.operand_type
[i
] == OP_OUT
))
784 recog_data
.operand_type
[i
] = OP_INOUT
;
787 /* Apply changes to earlier DEBUG_INSNs if possible. */
788 if (vd
->n_debug_insn_changes
)
789 note_uses (&PATTERN (insn
), cprop_find_used_regs
, vd
);
791 /* For each earlyclobber operand, zap the value data. */
792 for (i
= 0; i
< n_ops
; i
++)
793 if (recog_op_alt
[i
][alt
].earlyclobber
)
794 kill_value (recog_data
.operand
[i
], vd
);
796 /* Within asms, a clobber cannot overlap inputs or outputs.
797 I wouldn't think this were true for regular insns, but
798 scan_rtx treats them like that... */
799 note_stores (PATTERN (insn
), kill_clobbered_value
, vd
);
801 /* Kill all auto-incremented values. */
802 /* ??? REG_INC is useless, since stack pushes aren't done that way. */
803 for_each_rtx (&PATTERN (insn
), kill_autoinc_value
, vd
);
805 /* Kill all early-clobbered operands. */
806 for (i
= 0; i
< n_ops
; i
++)
807 if (recog_op_alt
[i
][alt
].earlyclobber
)
808 kill_value (recog_data
.operand
[i
], vd
);
810 /* Special-case plain move instructions, since we may well
811 be able to do the move from a different register class. */
812 if (set
&& REG_P (SET_SRC (set
)))
814 rtx src
= SET_SRC (set
);
815 unsigned int regno
= REGNO (src
);
816 enum machine_mode mode
= GET_MODE (src
);
820 /* If we are accessing SRC in some mode other that what we
821 set it in, make sure that the replacement is valid. */
822 if (mode
!= vd
->e
[regno
].mode
)
824 if (hard_regno_nregs
[regno
][mode
]
825 > hard_regno_nregs
[regno
][vd
->e
[regno
].mode
])
826 goto no_move_special_case
;
829 /* If the destination is also a register, try to find a source
830 register in the same class. */
831 if (REG_P (SET_DEST (set
)))
833 new_rtx
= find_oldest_value_reg (REGNO_REG_CLASS (regno
), src
, vd
);
834 if (new_rtx
&& validate_change (insn
, &SET_SRC (set
), new_rtx
, 0))
838 "insn %u: replaced reg %u with %u\n",
839 INSN_UID (insn
), regno
, REGNO (new_rtx
));
841 goto did_replacement
;
843 /* We need to re-extract as validate_change clobbers
846 if (! constrain_operands (1))
847 fatal_insn_not_found (insn
);
848 preprocess_constraints ();
851 /* Otherwise, try all valid registers and see if its valid. */
852 for (i
= vd
->e
[regno
].oldest_regno
; i
!= regno
;
853 i
= vd
->e
[i
].next_regno
)
855 new_rtx
= maybe_mode_change (vd
->e
[i
].mode
, vd
->e
[regno
].mode
,
857 if (new_rtx
!= NULL_RTX
)
859 if (validate_change (insn
, &SET_SRC (set
), new_rtx
, 0))
861 ORIGINAL_REGNO (new_rtx
) = ORIGINAL_REGNO (src
);
862 REG_ATTRS (new_rtx
) = REG_ATTRS (src
);
863 REG_POINTER (new_rtx
) = REG_POINTER (src
);
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 ();
880 no_move_special_case
:
882 any_replacements
= false;
884 /* For each input operand, replace a hard register with the
885 eldest live copy that's in an appropriate register class. */
886 for (i
= 0; i
< n_ops
; i
++)
890 /* Don't scan match_operand here, since we've no reg class
891 information to pass down. Any operands that we could
892 substitute in will be represented elsewhere. */
893 if (recog_data
.constraints
[i
][0] == '\0')
896 /* Don't replace in asms intentionally referencing hard regs. */
897 if (is_asm
&& REG_P (recog_data
.operand
[i
])
898 && (REGNO (recog_data
.operand
[i
])
899 == ORIGINAL_REGNO (recog_data
.operand
[i
])))
902 if (recog_data
.operand_type
[i
] == OP_IN
)
904 if (recog_op_alt
[i
][alt
].is_address
)
906 = replace_oldest_value_addr (recog_data
.operand_loc
[i
],
907 recog_op_alt
[i
][alt
].cl
,
909 else if (REG_P (recog_data
.operand
[i
]))
911 = replace_oldest_value_reg (recog_data
.operand_loc
[i
],
912 recog_op_alt
[i
][alt
].cl
,
914 else if (MEM_P (recog_data
.operand
[i
]))
915 replaced
[i
] = replace_oldest_value_mem (recog_data
.operand
[i
],
918 else if (MEM_P (recog_data
.operand
[i
]))
919 replaced
[i
] = replace_oldest_value_mem (recog_data
.operand
[i
],
922 /* If we performed any replacement, update match_dups. */
928 new_rtx
= *recog_data
.operand_loc
[i
];
929 recog_data
.operand
[i
] = new_rtx
;
930 for (j
= 0; j
< recog_data
.n_dups
; j
++)
931 if (recog_data
.dup_num
[j
] == i
)
932 validate_unshare_change (insn
, recog_data
.dup_loc
[j
], new_rtx
, 1);
934 any_replacements
= true;
938 if (any_replacements
)
940 if (! apply_change_group ())
942 for (i
= 0; i
< n_ops
; i
++)
945 rtx old
= *recog_data
.operand_loc
[i
];
946 recog_data
.operand
[i
] = old
;
951 "insn %u: reg replacements not verified\n",
961 anything_changed
= true;
963 /* If something changed, perhaps further changes to earlier
964 DEBUG_INSNs can be applied. */
965 if (vd
->n_debug_insn_changes
)
966 note_uses (&PATTERN (insn
), cprop_find_used_regs
, vd
);
969 /* Clobber call-clobbered registers. */
971 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
972 if (TEST_HARD_REG_BIT (regs_invalidated_by_call
, i
))
973 kill_value_regno (i
, 1, vd
);
976 note_stores (PATTERN (insn
), kill_set_value
, vd
);
979 if (set
&& REG_P (SET_DEST (set
)) && REG_P (SET_SRC (set
)))
980 copy_value (SET_DEST (set
), SET_SRC (set
), vd
);
982 if (insn
== BB_END (bb
))
986 return anything_changed
;
989 /* Main entry point for the forward copy propagation optimization. */
992 copyprop_hardreg_forward (void)
994 struct value_data
*all_vd
;
997 bool analyze_called
= false;
999 all_vd
= XNEWVEC (struct value_data
, last_basic_block
);
1001 visited
= sbitmap_alloc (last_basic_block
);
1002 sbitmap_zero (visited
);
1004 if (MAY_HAVE_DEBUG_INSNS
)
1005 debug_insn_changes_pool
1006 = create_alloc_pool ("debug insn changes pool",
1007 sizeof (struct queued_debug_insn_change
), 256);
1011 SET_BIT (visited
, bb
->index
);
1013 /* If a block has a single predecessor, that we've already
1014 processed, begin with the value data that was live at
1015 the end of the predecessor block. */
1016 /* ??? Ought to use more intelligent queuing of blocks. */
1017 if (single_pred_p (bb
)
1018 && TEST_BIT (visited
, single_pred (bb
)->index
)
1019 && ! (single_pred_edge (bb
)->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
)))
1021 all_vd
[bb
->index
] = all_vd
[single_pred (bb
)->index
];
1022 if (all_vd
[bb
->index
].n_debug_insn_changes
)
1026 for (regno
= 0; regno
< FIRST_PSEUDO_REGISTER
; regno
++)
1028 if (all_vd
[bb
->index
].e
[regno
].debug_insn_changes
)
1030 all_vd
[bb
->index
].e
[regno
].debug_insn_changes
= NULL
;
1031 if (--all_vd
[bb
->index
].n_debug_insn_changes
== 0)
1038 init_value_data (all_vd
+ bb
->index
);
1040 copyprop_hardreg_forward_1 (bb
, all_vd
+ bb
->index
);
1043 if (MAY_HAVE_DEBUG_INSNS
)
1046 if (TEST_BIT (visited
, bb
->index
)
1047 && all_vd
[bb
->index
].n_debug_insn_changes
)
1052 if (!analyze_called
)
1055 analyze_called
= true;
1057 live
= df_get_live_out (bb
);
1058 for (regno
= 0; regno
< FIRST_PSEUDO_REGISTER
; regno
++)
1059 if (all_vd
[bb
->index
].e
[regno
].debug_insn_changes
)
1061 if (REGNO_REG_SET_P (live
, regno
))
1062 apply_debug_insn_changes (all_vd
+ bb
->index
, regno
);
1063 if (all_vd
[bb
->index
].n_debug_insn_changes
== 0)
1068 free_alloc_pool (debug_insn_changes_pool
);
1071 sbitmap_free (visited
);
1076 /* Dump the value chain data to stderr. */
1079 debug_value_data (struct value_data
*vd
)
1084 CLEAR_HARD_REG_SET (set
);
1086 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1087 if (vd
->e
[i
].oldest_regno
== i
)
1089 if (vd
->e
[i
].mode
== VOIDmode
)
1091 if (vd
->e
[i
].next_regno
!= INVALID_REGNUM
)
1092 fprintf (stderr
, "[%u] Bad next_regno for empty chain (%u)\n",
1093 i
, vd
->e
[i
].next_regno
);
1097 SET_HARD_REG_BIT (set
, i
);
1098 fprintf (stderr
, "[%u %s] ", i
, GET_MODE_NAME (vd
->e
[i
].mode
));
1100 for (j
= vd
->e
[i
].next_regno
;
1101 j
!= INVALID_REGNUM
;
1102 j
= vd
->e
[j
].next_regno
)
1104 if (TEST_HARD_REG_BIT (set
, j
))
1106 fprintf (stderr
, "[%u] Loop in regno chain\n", j
);
1110 if (vd
->e
[j
].oldest_regno
!= i
)
1112 fprintf (stderr
, "[%u] Bad oldest_regno (%u)\n",
1113 j
, vd
->e
[j
].oldest_regno
);
1116 SET_HARD_REG_BIT (set
, j
);
1117 fprintf (stderr
, "[%u %s] ", j
, GET_MODE_NAME (vd
->e
[j
].mode
));
1119 fputc ('\n', stderr
);
1122 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1123 if (! TEST_HARD_REG_BIT (set
, i
)
1124 && (vd
->e
[i
].mode
!= VOIDmode
1125 || vd
->e
[i
].oldest_regno
!= i
1126 || vd
->e
[i
].next_regno
!= INVALID_REGNUM
))
1127 fprintf (stderr
, "[%u] Non-empty reg in chain (%s %u %i)\n",
1128 i
, GET_MODE_NAME (vd
->e
[i
].mode
), vd
->e
[i
].oldest_regno
,
1129 vd
->e
[i
].next_regno
);
1132 #ifdef ENABLE_CHECKING
1134 validate_value_data (struct value_data
*vd
)
1139 CLEAR_HARD_REG_SET (set
);
1141 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1142 if (vd
->e
[i
].oldest_regno
== i
)
1144 if (vd
->e
[i
].mode
== VOIDmode
)
1146 if (vd
->e
[i
].next_regno
!= INVALID_REGNUM
)
1147 internal_error ("validate_value_data: [%u] Bad next_regno for empty chain (%u)",
1148 i
, vd
->e
[i
].next_regno
);
1152 SET_HARD_REG_BIT (set
, i
);
1154 for (j
= vd
->e
[i
].next_regno
;
1155 j
!= INVALID_REGNUM
;
1156 j
= vd
->e
[j
].next_regno
)
1158 if (TEST_HARD_REG_BIT (set
, j
))
1159 internal_error ("validate_value_data: Loop in regno chain (%u)",
1161 if (vd
->e
[j
].oldest_regno
!= i
)
1162 internal_error ("validate_value_data: [%u] Bad oldest_regno (%u)",
1163 j
, vd
->e
[j
].oldest_regno
);
1165 SET_HARD_REG_BIT (set
, j
);
1169 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1170 if (! TEST_HARD_REG_BIT (set
, i
)
1171 && (vd
->e
[i
].mode
!= VOIDmode
1172 || vd
->e
[i
].oldest_regno
!= i
1173 || vd
->e
[i
].next_regno
!= INVALID_REGNUM
))
1174 internal_error ("validate_value_data: [%u] Non-empty reg in chain (%s %u %i)",
1175 i
, GET_MODE_NAME (vd
->e
[i
].mode
), vd
->e
[i
].oldest_regno
,
1176 vd
->e
[i
].next_regno
);
1181 gate_handle_cprop (void)
1183 return (optimize
> 0 && (flag_cprop_registers
));
1187 struct rtl_opt_pass pass_cprop_hardreg
=
1191 "cprop_hardreg", /* name */
1192 gate_handle_cprop
, /* gate */
1193 copyprop_hardreg_forward
, /* execute */
1196 0, /* static_pass_number */
1197 TV_CPROP_REGISTERS
, /* tv_id */
1198 0, /* properties_required */
1199 0, /* properties_provided */
1200 0, /* properties_destroyed */
1201 0, /* todo_flags_start */
1203 | TODO_verify_rtl_sharing
/* todo_flags_finish */