1 /* Register renaming for the GNU compiler.
2 Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007
3 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 2, 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 COPYING. If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
24 #include "coretypes.h"
28 #include "insn-config.h"
30 #include "addresses.h"
31 #include "hard-reg-set.h"
32 #include "basic-block.h"
41 #include "tree-pass.h"
46 struct du_chain
*next_chain
;
47 struct du_chain
*next_use
;
51 ENUM_BITFIELD(reg_class
) cl
: 16;
52 unsigned int need_caller_save_reg
:1;
53 unsigned int earlyclobber
:1;
59 terminate_overlapping_read
,
64 /* mark_access is for marking the destination regs in
65 REG_FRAME_RELATED_EXPR notes (as if they were read) so that the
66 note is updated properly. */
70 static const char * const scan_actions_name
[] =
73 "terminate_overlapping_read",
81 static struct obstack rename_obstack
;
83 static void do_replace (struct du_chain
*, int);
84 static void scan_rtx_reg (rtx
, rtx
*, enum reg_class
,
85 enum scan_actions
, enum op_type
, int);
86 static void scan_rtx_address (rtx
, rtx
*, enum reg_class
,
87 enum scan_actions
, enum machine_mode
);
88 static void scan_rtx (rtx
, rtx
*, enum reg_class
, enum scan_actions
,
90 static struct du_chain
*build_def_use (basic_block
);
91 static void dump_def_use_chain (struct du_chain
*);
92 static void note_sets (rtx
, rtx
, void *);
93 static void clear_dead_regs (HARD_REG_SET
*, enum machine_mode
, rtx
);
94 static void merge_overlapping_regs (basic_block
, HARD_REG_SET
*,
97 /* Called through note_stores. Find sets of registers, and
98 record them in *DATA (which is actually a HARD_REG_SET *). */
101 note_sets (rtx x
, rtx set ATTRIBUTE_UNUSED
, void *data
)
103 HARD_REG_SET
*pset
= (HARD_REG_SET
*) data
;
105 if (GET_CODE (x
) == SUBREG
)
109 /* There must not be pseudos at this point. */
110 gcc_assert (HARD_REGISTER_P (x
));
111 add_to_hard_reg_set (pset
, GET_MODE (x
), REGNO (x
));
114 /* Clear all registers from *PSET for which a note of kind KIND can be found
115 in the list NOTES. */
118 clear_dead_regs (HARD_REG_SET
*pset
, enum machine_mode kind
, rtx notes
)
121 for (note
= notes
; note
; note
= XEXP (note
, 1))
122 if (REG_NOTE_KIND (note
) == kind
&& REG_P (XEXP (note
, 0)))
124 rtx reg
= XEXP (note
, 0);
125 /* There must not be pseudos at this point. */
126 gcc_assert (HARD_REGISTER_P (reg
));
127 remove_from_hard_reg_set (pset
, GET_MODE (reg
), REGNO (reg
));
131 /* For a def-use chain CHAIN in basic block B, find which registers overlap
132 its lifetime and set the corresponding bits in *PSET. */
135 merge_overlapping_regs (basic_block b
, HARD_REG_SET
*pset
,
136 struct du_chain
*chain
)
138 struct du_chain
*t
= chain
;
142 REG_SET_TO_HARD_REG_SET (live
, DF_LIVE_IN (b
));
146 /* Search forward until the next reference to the register to be
148 while (insn
!= t
->insn
)
152 clear_dead_regs (&live
, REG_DEAD
, REG_NOTES (insn
));
153 note_stores (PATTERN (insn
), note_sets
, (void *) &live
);
154 /* Only record currently live regs if we are inside the
157 IOR_HARD_REG_SET (*pset
, live
);
158 clear_dead_regs (&live
, REG_UNUSED
, REG_NOTES (insn
));
160 insn
= NEXT_INSN (insn
);
163 IOR_HARD_REG_SET (*pset
, live
);
165 /* For the last reference, also merge in all registers set in the
167 @@@ We only have take earlyclobbered sets into account. */
169 note_stores (PATTERN (insn
), note_sets
, (void *) pset
);
175 /* Perform register renaming on the current function. */
178 regrename_optimize (void)
180 int tick
[FIRST_PSEUDO_REGISTER
];
185 df_set_flags (DF_LR_RUN_DCE
);
186 df_note_add_problem ();
188 df_set_flags (DF_NO_INSN_RESCAN
);
190 memset (tick
, 0, sizeof tick
);
192 gcc_obstack_init (&rename_obstack
);
193 first_obj
= obstack_alloc (&rename_obstack
, 0);
197 struct du_chain
*all_chains
= 0;
198 HARD_REG_SET unavailable
;
199 HARD_REG_SET regs_seen
;
201 CLEAR_HARD_REG_SET (unavailable
);
204 fprintf (dump_file
, "\nBasic block %d:\n", bb
->index
);
206 all_chains
= build_def_use (bb
);
209 dump_def_use_chain (all_chains
);
211 CLEAR_HARD_REG_SET (unavailable
);
212 /* Don't clobber traceback for noreturn functions. */
213 if (frame_pointer_needed
)
215 add_to_hard_reg_set (&unavailable
, Pmode
, FRAME_POINTER_REGNUM
);
216 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
217 add_to_hard_reg_set (&unavailable
, Pmode
, HARD_FRAME_POINTER_REGNUM
);
221 CLEAR_HARD_REG_SET (regs_seen
);
224 int new_reg
, best_new_reg
;
226 struct du_chain
*this = all_chains
;
227 struct du_chain
*tmp
, *last
;
228 HARD_REG_SET this_unavailable
;
229 int reg
= REGNO (*this->loc
);
232 all_chains
= this->next_chain
;
236 #if 0 /* This just disables optimization opportunities. */
237 /* Only rename once we've seen the reg more than once. */
238 if (! TEST_HARD_REG_BIT (regs_seen
, reg
))
240 SET_HARD_REG_BIT (regs_seen
, reg
);
245 if (fixed_regs
[reg
] || global_regs
[reg
]
246 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
247 || (frame_pointer_needed
&& reg
== HARD_FRAME_POINTER_REGNUM
)
249 || (frame_pointer_needed
&& reg
== FRAME_POINTER_REGNUM
)
254 COPY_HARD_REG_SET (this_unavailable
, unavailable
);
256 /* Find last entry on chain (which has the need_caller_save bit),
257 count number of uses, and narrow the set of registers we can
260 for (last
= this; last
->next_use
; last
= last
->next_use
)
263 IOR_COMPL_HARD_REG_SET (this_unavailable
,
264 reg_class_contents
[last
->cl
]);
269 IOR_COMPL_HARD_REG_SET (this_unavailable
,
270 reg_class_contents
[last
->cl
]);
272 if (this->need_caller_save_reg
)
273 IOR_HARD_REG_SET (this_unavailable
, call_used_reg_set
);
275 merge_overlapping_regs (bb
, &this_unavailable
, this);
277 /* Now potential_regs is a reasonable approximation, let's
278 have a closer look at each register still in there. */
279 for (new_reg
= 0; new_reg
< FIRST_PSEUDO_REGISTER
; new_reg
++)
281 int nregs
= hard_regno_nregs
[new_reg
][GET_MODE (*this->loc
)];
283 for (i
= nregs
- 1; i
>= 0; --i
)
284 if (TEST_HARD_REG_BIT (this_unavailable
, new_reg
+ i
)
285 || fixed_regs
[new_reg
+ i
]
286 || global_regs
[new_reg
+ i
]
287 /* Can't use regs which aren't saved by the prologue. */
288 || (! df_regs_ever_live_p (new_reg
+ i
)
289 && ! call_used_regs
[new_reg
+ i
])
290 #ifdef LEAF_REGISTERS
291 /* We can't use a non-leaf register if we're in a
293 || (current_function_is_leaf
294 && !LEAF_REGISTERS
[new_reg
+ i
])
296 #ifdef HARD_REGNO_RENAME_OK
297 || ! HARD_REGNO_RENAME_OK (reg
+ i
, new_reg
+ i
)
304 /* See whether it accepts all modes that occur in
305 definition and uses. */
306 for (tmp
= this; tmp
; tmp
= tmp
->next_use
)
307 if (! HARD_REGNO_MODE_OK (new_reg
, GET_MODE (*tmp
->loc
))
308 || (tmp
->need_caller_save_reg
309 && ! (HARD_REGNO_CALL_PART_CLOBBERED
310 (reg
, GET_MODE (*tmp
->loc
)))
311 && (HARD_REGNO_CALL_PART_CLOBBERED
312 (new_reg
, GET_MODE (*tmp
->loc
)))))
316 if (tick
[best_new_reg
] > tick
[new_reg
])
317 best_new_reg
= new_reg
;
323 fprintf (dump_file
, "Register %s in insn %d",
324 reg_names
[reg
], INSN_UID (last
->insn
));
325 if (last
->need_caller_save_reg
)
326 fprintf (dump_file
, " crosses a call");
329 if (best_new_reg
== reg
)
331 tick
[reg
] = ++this_tick
;
333 fprintf (dump_file
, "; no available better choice\n");
337 do_replace (this, best_new_reg
);
338 tick
[best_new_reg
] = ++this_tick
;
339 df_set_regs_ever_live (best_new_reg
, true);
342 fprintf (dump_file
, ", renamed as %s\n", reg_names
[best_new_reg
]);
345 obstack_free (&rename_obstack
, first_obj
);
348 obstack_free (&rename_obstack
, NULL
);
349 df_clear_flags (DF_NO_INSN_RESCAN
);
350 df_insn_rescan_all ();
353 fputc ('\n', dump_file
);
357 do_replace (struct du_chain
*chain
, int reg
)
361 unsigned int regno
= ORIGINAL_REGNO (*chain
->loc
);
362 struct reg_attrs
* attr
= REG_ATTRS (*chain
->loc
);
364 *chain
->loc
= gen_raw_REG (GET_MODE (*chain
->loc
), reg
);
365 if (regno
>= FIRST_PSEUDO_REGISTER
)
366 ORIGINAL_REGNO (*chain
->loc
) = regno
;
367 REG_ATTRS (*chain
->loc
) = attr
;
368 chain
= chain
->next_use
;
373 static struct du_chain
*open_chains
;
374 static struct du_chain
*closed_chains
;
377 scan_rtx_reg (rtx insn
, rtx
*loc
, enum reg_class cl
,
378 enum scan_actions action
, enum op_type type
, int earlyclobber
)
382 enum machine_mode mode
= GET_MODE (x
);
383 int this_regno
= REGNO (x
);
384 int this_nregs
= hard_regno_nregs
[this_regno
][mode
];
386 if (action
== mark_write
)
390 struct du_chain
*this
391 = obstack_alloc (&rename_obstack
, sizeof (struct du_chain
));
393 this->next_chain
= open_chains
;
397 this->need_caller_save_reg
= 0;
398 this->earlyclobber
= earlyclobber
;
404 if ((type
== OP_OUT
) != (action
== terminate_write
|| action
== mark_access
))
407 for (p
= &open_chains
; *p
;)
409 struct du_chain
*this = *p
;
411 /* Check if the chain has been terminated if it has then skip to
414 This can happen when we've already appended the location to
415 the chain in Step 3, but are trying to hide in-out operands
416 from terminate_write in Step 5. */
418 if (*this->loc
== cc0_rtx
)
419 p
= &this->next_chain
;
422 int regno
= REGNO (*this->loc
);
423 int nregs
= hard_regno_nregs
[regno
][GET_MODE (*this->loc
)];
424 int exact_match
= (regno
== this_regno
&& nregs
== this_nregs
);
426 if (regno
+ nregs
<= this_regno
427 || this_regno
+ this_nregs
<= regno
)
429 p
= &this->next_chain
;
433 if (action
== mark_read
|| action
== mark_access
)
435 gcc_assert (exact_match
);
437 /* ??? Class NO_REGS can happen if the md file makes use of
438 EXTRA_CONSTRAINTS to match registers. Which is arguably
439 wrong, but there we are. Since we know not what this may
440 be replaced with, terminate the chain. */
443 this = obstack_alloc (&rename_obstack
, sizeof (struct du_chain
));
445 this->next_chain
= (*p
)->next_chain
;
449 this->need_caller_save_reg
= 0;
457 if (action
!= terminate_overlapping_read
|| ! exact_match
)
459 struct du_chain
*next
= this->next_chain
;
461 /* Whether the terminated chain can be used for renaming
462 depends on the action and this being an exact match.
463 In either case, we remove this element from open_chains. */
465 if ((action
== terminate_dead
|| action
== terminate_write
)
468 this->next_chain
= closed_chains
;
469 closed_chains
= this;
472 "Closing chain %s at insn %d (%s)\n",
473 reg_names
[REGNO (*this->loc
)], INSN_UID (insn
),
474 scan_actions_name
[(int) action
]);
480 "Discarding chain %s at insn %d (%s)\n",
481 reg_names
[REGNO (*this->loc
)], INSN_UID (insn
),
482 scan_actions_name
[(int) action
]);
487 p
= &this->next_chain
;
492 /* Adapted from find_reloads_address_1. CL is INDEX_REG_CLASS or
493 BASE_REG_CLASS depending on how the register is being considered. */
496 scan_rtx_address (rtx insn
, rtx
*loc
, enum reg_class cl
,
497 enum scan_actions action
, enum machine_mode mode
)
500 RTX_CODE code
= GET_CODE (x
);
504 if (action
== mark_write
|| action
== mark_access
)
511 rtx orig_op0
= XEXP (x
, 0);
512 rtx orig_op1
= XEXP (x
, 1);
513 RTX_CODE code0
= GET_CODE (orig_op0
);
514 RTX_CODE code1
= GET_CODE (orig_op1
);
519 enum rtx_code index_code
= SCRATCH
;
521 if (GET_CODE (op0
) == SUBREG
)
523 op0
= SUBREG_REG (op0
);
524 code0
= GET_CODE (op0
);
527 if (GET_CODE (op1
) == SUBREG
)
529 op1
= SUBREG_REG (op1
);
530 code1
= GET_CODE (op1
);
533 if (code0
== MULT
|| code0
== SIGN_EXTEND
|| code0
== TRUNCATE
534 || code0
== ZERO_EXTEND
|| code1
== MEM
)
538 index_code
= GET_CODE (*locI
);
540 else if (code1
== MULT
|| code1
== SIGN_EXTEND
|| code1
== TRUNCATE
541 || code1
== ZERO_EXTEND
|| code0
== MEM
)
545 index_code
= GET_CODE (*locI
);
547 else if (code0
== CONST_INT
|| code0
== CONST
548 || code0
== SYMBOL_REF
|| code0
== LABEL_REF
)
551 index_code
= GET_CODE (XEXP (x
, 0));
553 else if (code1
== CONST_INT
|| code1
== CONST
554 || code1
== SYMBOL_REF
|| code1
== LABEL_REF
)
557 index_code
= GET_CODE (XEXP (x
, 1));
559 else if (code0
== REG
&& code1
== REG
)
562 unsigned regno0
= REGNO (op0
), regno1
= REGNO (op1
);
564 if (REGNO_OK_FOR_INDEX_P (regno0
)
565 && regno_ok_for_base_p (regno1
, mode
, PLUS
, REG
))
567 else if (REGNO_OK_FOR_INDEX_P (regno1
)
568 && regno_ok_for_base_p (regno0
, mode
, PLUS
, REG
))
570 else if (regno_ok_for_base_p (regno1
, mode
, PLUS
, REG
))
572 else if (regno_ok_for_base_p (regno0
, mode
, PLUS
, REG
))
574 else if (REGNO_OK_FOR_INDEX_P (regno1
))
579 locI
= &XEXP (x
, index_op
);
580 locB
= &XEXP (x
, !index_op
);
581 index_code
= GET_CODE (*locI
);
583 else if (code0
== REG
)
587 index_code
= GET_CODE (*locI
);
589 else if (code1
== REG
)
593 index_code
= GET_CODE (*locI
);
597 scan_rtx_address (insn
, locI
, INDEX_REG_CLASS
, action
, mode
);
599 scan_rtx_address (insn
, locB
, base_reg_class (mode
, PLUS
, index_code
),
612 /* If the target doesn't claim to handle autoinc, this must be
613 something special, like a stack push. Kill this chain. */
614 action
= terminate_all_read
;
619 scan_rtx_address (insn
, &XEXP (x
, 0),
620 base_reg_class (GET_MODE (x
), MEM
, SCRATCH
), action
,
625 scan_rtx_reg (insn
, loc
, cl
, action
, OP_IN
, 0);
632 fmt
= GET_RTX_FORMAT (code
);
633 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
636 scan_rtx_address (insn
, &XEXP (x
, i
), cl
, action
, mode
);
637 else if (fmt
[i
] == 'E')
638 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
639 scan_rtx_address (insn
, &XVECEXP (x
, i
, j
), cl
, action
, mode
);
644 scan_rtx (rtx insn
, rtx
*loc
, enum reg_class cl
,
645 enum scan_actions action
, enum op_type type
, int earlyclobber
)
649 enum rtx_code code
= GET_CODE (x
);
666 scan_rtx_reg (insn
, loc
, cl
, action
, type
, earlyclobber
);
670 scan_rtx_address (insn
, &XEXP (x
, 0),
671 base_reg_class (GET_MODE (x
), MEM
, SCRATCH
), action
,
676 scan_rtx (insn
, &SET_SRC (x
), cl
, action
, OP_IN
, 0);
677 scan_rtx (insn
, &SET_DEST (x
), cl
, action
,
678 GET_CODE (PATTERN (insn
)) == COND_EXEC
? OP_INOUT
: OP_OUT
, 0);
681 case STRICT_LOW_PART
:
682 scan_rtx (insn
, &XEXP (x
, 0), cl
, action
, OP_INOUT
, earlyclobber
);
687 scan_rtx (insn
, &XEXP (x
, 0), cl
, action
,
688 type
== OP_IN
? OP_IN
: OP_INOUT
, earlyclobber
);
689 scan_rtx (insn
, &XEXP (x
, 1), cl
, action
, OP_IN
, 0);
690 scan_rtx (insn
, &XEXP (x
, 2), cl
, action
, OP_IN
, 0);
699 /* Should only happen inside MEM. */
703 scan_rtx (insn
, &SET_DEST (x
), cl
, action
,
704 GET_CODE (PATTERN (insn
)) == COND_EXEC
? OP_INOUT
: OP_OUT
, 0);
708 scan_rtx (insn
, &XEXP (x
, 0), cl
, action
, type
, 0);
710 scan_rtx (insn
, &XEXP (x
, 1), cl
, action
, type
, 0);
717 fmt
= GET_RTX_FORMAT (code
);
718 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
721 scan_rtx (insn
, &XEXP (x
, i
), cl
, action
, type
, 0);
722 else if (fmt
[i
] == 'E')
723 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
724 scan_rtx (insn
, &XVECEXP (x
, i
, j
), cl
, action
, type
, 0);
728 /* Build def/use chain. */
730 static struct du_chain
*
731 build_def_use (basic_block bb
)
735 open_chains
= closed_chains
= NULL
;
737 for (insn
= BB_HEAD (bb
); ; insn
= NEXT_INSN (insn
))
743 rtx old_operands
[MAX_RECOG_OPERANDS
];
744 rtx old_dups
[MAX_DUP_OPERANDS
];
749 /* Process the insn, determining its effect on the def-use
750 chains. We perform the following steps with the register
751 references in the insn:
752 (1) Any read that overlaps an open chain, but doesn't exactly
753 match, causes that chain to be closed. We can't deal
755 (2) Any read outside an operand causes any chain it overlaps
756 with to be closed, since we can't replace it.
757 (3) Any read inside an operand is added if there's already
758 an open chain for it.
759 (4) For any REG_DEAD note we find, close open chains that
761 (5) For any write we find, close open chains that overlap it.
762 (6) For any write we find in an operand, make a new chain.
763 (7) For any REG_UNUSED, close any chains we just opened. */
765 icode
= recog_memoized (insn
);
767 if (! constrain_operands (1))
768 fatal_insn_not_found (insn
);
769 preprocess_constraints ();
770 alt
= which_alternative
;
771 n_ops
= recog_data
.n_operands
;
773 /* Simplify the code below by rewriting things to reflect
774 matching constraints. Also promote OP_OUT to OP_INOUT
775 in predicated instructions. */
777 predicated
= GET_CODE (PATTERN (insn
)) == COND_EXEC
;
778 for (i
= 0; i
< n_ops
; ++i
)
780 int matches
= recog_op_alt
[i
][alt
].matches
;
782 recog_op_alt
[i
][alt
].cl
= recog_op_alt
[matches
][alt
].cl
;
783 if (matches
>= 0 || recog_op_alt
[i
][alt
].matched
>= 0
784 || (predicated
&& recog_data
.operand_type
[i
] == OP_OUT
))
785 recog_data
.operand_type
[i
] = OP_INOUT
;
788 /* Step 1: Close chains for which we have overlapping reads. */
789 for (i
= 0; i
< n_ops
; i
++)
790 scan_rtx (insn
, recog_data
.operand_loc
[i
],
791 NO_REGS
, terminate_overlapping_read
,
792 recog_data
.operand_type
[i
], 0);
794 /* Step 2: Close chains for which we have reads outside operands.
795 We do this by munging all operands into CC0, and closing
796 everything remaining. */
798 for (i
= 0; i
< n_ops
; i
++)
800 old_operands
[i
] = recog_data
.operand
[i
];
801 /* Don't squash match_operator or match_parallel here, since
802 we don't know that all of the contained registers are
803 reachable by proper operands. */
804 if (recog_data
.constraints
[i
][0] == '\0')
806 *recog_data
.operand_loc
[i
] = cc0_rtx
;
808 for (i
= 0; i
< recog_data
.n_dups
; i
++)
810 int dup_num
= recog_data
.dup_num
[i
];
812 old_dups
[i
] = *recog_data
.dup_loc
[i
];
813 *recog_data
.dup_loc
[i
] = cc0_rtx
;
815 /* For match_dup of match_operator or match_parallel, share
816 them, so that we don't miss changes in the dup. */
818 && insn_data
[icode
].operand
[dup_num
].eliminable
== 0)
819 old_dups
[i
] = recog_data
.operand
[dup_num
];
822 scan_rtx (insn
, &PATTERN (insn
), NO_REGS
, terminate_all_read
,
825 for (i
= 0; i
< recog_data
.n_dups
; i
++)
826 *recog_data
.dup_loc
[i
] = old_dups
[i
];
827 for (i
= 0; i
< n_ops
; i
++)
828 *recog_data
.operand_loc
[i
] = old_operands
[i
];
830 /* Step 2B: Can't rename function call argument registers. */
831 if (CALL_P (insn
) && CALL_INSN_FUNCTION_USAGE (insn
))
832 scan_rtx (insn
, &CALL_INSN_FUNCTION_USAGE (insn
),
833 NO_REGS
, terminate_all_read
, OP_IN
, 0);
835 /* Step 2C: Can't rename asm operands that were originally
837 if (asm_noperands (PATTERN (insn
)) > 0)
838 for (i
= 0; i
< n_ops
; i
++)
840 rtx
*loc
= recog_data
.operand_loc
[i
];
844 && REGNO (op
) == ORIGINAL_REGNO (op
)
845 && (recog_data
.operand_type
[i
] == OP_IN
846 || recog_data
.operand_type
[i
] == OP_INOUT
))
847 scan_rtx (insn
, loc
, NO_REGS
, terminate_all_read
, OP_IN
, 0);
850 /* Step 3: Append to chains for reads inside operands. */
851 for (i
= 0; i
< n_ops
+ recog_data
.n_dups
; i
++)
853 int opn
= i
< n_ops
? i
: recog_data
.dup_num
[i
- n_ops
];
854 rtx
*loc
= (i
< n_ops
855 ? recog_data
.operand_loc
[opn
]
856 : recog_data
.dup_loc
[i
- n_ops
]);
857 enum reg_class cl
= recog_op_alt
[opn
][alt
].cl
;
858 enum op_type type
= recog_data
.operand_type
[opn
];
860 /* Don't scan match_operand here, since we've no reg class
861 information to pass down. Any operands that we could
862 substitute in will be represented elsewhere. */
863 if (recog_data
.constraints
[opn
][0] == '\0')
866 if (recog_op_alt
[opn
][alt
].is_address
)
867 scan_rtx_address (insn
, loc
, cl
, mark_read
, VOIDmode
);
869 scan_rtx (insn
, loc
, cl
, mark_read
, type
, 0);
872 /* Step 3B: Record updates for regs in REG_INC notes, and
873 source regs in REG_FRAME_RELATED_EXPR notes. */
874 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
875 if (REG_NOTE_KIND (note
) == REG_INC
876 || REG_NOTE_KIND (note
) == REG_FRAME_RELATED_EXPR
)
877 scan_rtx (insn
, &XEXP (note
, 0), ALL_REGS
, mark_read
,
880 /* Step 4: Close chains for registers that die here. */
881 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
882 if (REG_NOTE_KIND (note
) == REG_DEAD
)
883 scan_rtx (insn
, &XEXP (note
, 0), NO_REGS
, terminate_dead
,
886 /* Step 4B: If this is a call, any chain live at this point
887 requires a caller-saved reg. */
891 for (p
= open_chains
; p
; p
= p
->next_chain
)
892 p
->need_caller_save_reg
= 1;
895 /* Step 5: Close open chains that overlap writes. Similar to
896 step 2, we hide in-out operands, since we do not want to
897 close these chains. */
899 for (i
= 0; i
< n_ops
; i
++)
901 old_operands
[i
] = recog_data
.operand
[i
];
902 if (recog_data
.operand_type
[i
] == OP_INOUT
)
903 *recog_data
.operand_loc
[i
] = cc0_rtx
;
905 for (i
= 0; i
< recog_data
.n_dups
; i
++)
907 int opn
= recog_data
.dup_num
[i
];
908 old_dups
[i
] = *recog_data
.dup_loc
[i
];
909 if (recog_data
.operand_type
[opn
] == OP_INOUT
)
910 *recog_data
.dup_loc
[i
] = cc0_rtx
;
913 scan_rtx (insn
, &PATTERN (insn
), NO_REGS
, terminate_write
, OP_IN
, 0);
915 for (i
= 0; i
< recog_data
.n_dups
; i
++)
916 *recog_data
.dup_loc
[i
] = old_dups
[i
];
917 for (i
= 0; i
< n_ops
; i
++)
918 *recog_data
.operand_loc
[i
] = old_operands
[i
];
920 /* Step 6: Begin new chains for writes inside operands. */
921 /* ??? Many targets have output constraints on the SET_DEST
922 of a call insn, which is stupid, since these are certainly
923 ABI defined hard registers. Don't change calls at all.
924 Similarly take special care for asm statement that originally
925 referenced hard registers. */
926 if (asm_noperands (PATTERN (insn
)) > 0)
928 for (i
= 0; i
< n_ops
; i
++)
929 if (recog_data
.operand_type
[i
] == OP_OUT
)
931 rtx
*loc
= recog_data
.operand_loc
[i
];
933 enum reg_class cl
= recog_op_alt
[i
][alt
].cl
;
936 && REGNO (op
) == ORIGINAL_REGNO (op
))
939 scan_rtx (insn
, loc
, cl
, mark_write
, OP_OUT
,
940 recog_op_alt
[i
][alt
].earlyclobber
);
943 else if (!CALL_P (insn
))
944 for (i
= 0; i
< n_ops
+ recog_data
.n_dups
; i
++)
946 int opn
= i
< n_ops
? i
: recog_data
.dup_num
[i
- n_ops
];
947 rtx
*loc
= (i
< n_ops
948 ? recog_data
.operand_loc
[opn
]
949 : recog_data
.dup_loc
[i
- n_ops
]);
950 enum reg_class cl
= recog_op_alt
[opn
][alt
].cl
;
952 if (recog_data
.operand_type
[opn
] == OP_OUT
)
953 scan_rtx (insn
, loc
, cl
, mark_write
, OP_OUT
,
954 recog_op_alt
[opn
][alt
].earlyclobber
);
957 /* Step 6B: Record destination regs in REG_FRAME_RELATED_EXPR
959 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
960 if (REG_NOTE_KIND (note
) == REG_FRAME_RELATED_EXPR
)
961 scan_rtx (insn
, &XEXP (note
, 0), ALL_REGS
, mark_access
,
964 /* Step 7: Close chains for registers that were never
966 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
967 if (REG_NOTE_KIND (note
) == REG_UNUSED
)
968 scan_rtx (insn
, &XEXP (note
, 0), NO_REGS
, terminate_dead
,
971 if (insn
== BB_END (bb
))
975 /* Since we close every chain when we find a REG_DEAD note, anything that
976 is still open lives past the basic block, so it can't be renamed. */
977 return closed_chains
;
980 /* Dump all def/use chains in CHAINS to DUMP_FILE. They are
981 printed in reverse order as that's how we build them. */
984 dump_def_use_chain (struct du_chain
*chains
)
988 struct du_chain
*this = chains
;
989 int r
= REGNO (*this->loc
);
990 int nregs
= hard_regno_nregs
[r
][GET_MODE (*this->loc
)];
991 fprintf (dump_file
, "Register %s (%d):", reg_names
[r
], nregs
);
994 fprintf (dump_file
, " %d [%s]", INSN_UID (this->insn
),
995 reg_class_names
[this->cl
]);
996 this = this->next_use
;
998 fprintf (dump_file
, "\n");
999 chains
= chains
->next_chain
;
1003 /* The following code does forward propagation of hard register copies.
1004 The object is to eliminate as many dependencies as possible, so that
1005 we have the most scheduling freedom. As a side effect, we also clean
1006 up some silly register allocation decisions made by reload. This
1007 code may be obsoleted by a new register allocator. */
1009 /* For each register, we have a list of registers that contain the same
1010 value. The OLDEST_REGNO field points to the head of the list, and
1011 the NEXT_REGNO field runs through the list. The MODE field indicates
1012 what mode the data is known to be in; this field is VOIDmode when the
1013 register is not known to contain valid data. */
1015 struct value_data_entry
1017 enum machine_mode mode
;
1018 unsigned int oldest_regno
;
1019 unsigned int next_regno
;
1024 struct value_data_entry e
[FIRST_PSEUDO_REGISTER
];
1025 unsigned int max_value_regs
;
1028 static void kill_value_one_regno (unsigned, struct value_data
*);
1029 static void kill_value_regno (unsigned, unsigned, struct value_data
*);
1030 static void kill_value (rtx
, struct value_data
*);
1031 static void set_value_regno (unsigned, enum machine_mode
, struct value_data
*);
1032 static void init_value_data (struct value_data
*);
1033 static void kill_clobbered_value (rtx
, rtx
, void *);
1034 static void kill_set_value (rtx
, rtx
, void *);
1035 static int kill_autoinc_value (rtx
*, void *);
1036 static void copy_value (rtx
, rtx
, struct value_data
*);
1037 static bool mode_change_ok (enum machine_mode
, enum machine_mode
,
1039 static rtx
maybe_mode_change (enum machine_mode
, enum machine_mode
,
1040 enum machine_mode
, unsigned int, unsigned int);
1041 static rtx
find_oldest_value_reg (enum reg_class
, rtx
, struct value_data
*);
1042 static bool replace_oldest_value_reg (rtx
*, enum reg_class
, rtx
,
1043 struct value_data
*);
1044 static bool replace_oldest_value_addr (rtx
*, enum reg_class
,
1045 enum machine_mode
, rtx
,
1046 struct value_data
*);
1047 static bool replace_oldest_value_mem (rtx
, rtx
, struct value_data
*);
1048 static bool copyprop_hardreg_forward_1 (basic_block
, struct value_data
*);
1049 extern void debug_value_data (struct value_data
*);
1050 #ifdef ENABLE_CHECKING
1051 static void validate_value_data (struct value_data
*);
1054 /* Kill register REGNO. This involves removing it from any value
1055 lists, and resetting the value mode to VOIDmode. This is only a
1056 helper function; it does not handle any hard registers overlapping
1060 kill_value_one_regno (unsigned int regno
, struct value_data
*vd
)
1062 unsigned int i
, next
;
1064 if (vd
->e
[regno
].oldest_regno
!= regno
)
1066 for (i
= vd
->e
[regno
].oldest_regno
;
1067 vd
->e
[i
].next_regno
!= regno
;
1068 i
= vd
->e
[i
].next_regno
)
1070 vd
->e
[i
].next_regno
= vd
->e
[regno
].next_regno
;
1072 else if ((next
= vd
->e
[regno
].next_regno
) != INVALID_REGNUM
)
1074 for (i
= next
; i
!= INVALID_REGNUM
; i
= vd
->e
[i
].next_regno
)
1075 vd
->e
[i
].oldest_regno
= next
;
1078 vd
->e
[regno
].mode
= VOIDmode
;
1079 vd
->e
[regno
].oldest_regno
= regno
;
1080 vd
->e
[regno
].next_regno
= INVALID_REGNUM
;
1082 #ifdef ENABLE_CHECKING
1083 validate_value_data (vd
);
1087 /* Kill the value in register REGNO for NREGS, and any other registers
1088 whose values overlap. */
1091 kill_value_regno (unsigned int regno
, unsigned int nregs
,
1092 struct value_data
*vd
)
1096 /* Kill the value we're told to kill. */
1097 for (j
= 0; j
< nregs
; ++j
)
1098 kill_value_one_regno (regno
+ j
, vd
);
1100 /* Kill everything that overlapped what we're told to kill. */
1101 if (regno
< vd
->max_value_regs
)
1104 j
= regno
- vd
->max_value_regs
;
1105 for (; j
< regno
; ++j
)
1108 if (vd
->e
[j
].mode
== VOIDmode
)
1110 n
= hard_regno_nregs
[j
][vd
->e
[j
].mode
];
1112 for (i
= 0; i
< n
; ++i
)
1113 kill_value_one_regno (j
+ i
, vd
);
1117 /* Kill X. This is a convenience function wrapping kill_value_regno
1118 so that we mind the mode the register is in. */
1121 kill_value (rtx x
, struct value_data
*vd
)
1125 if (GET_CODE (x
) == SUBREG
)
1127 x
= simplify_subreg (GET_MODE (x
), SUBREG_REG (x
),
1128 GET_MODE (SUBREG_REG (x
)), SUBREG_BYTE (x
));
1130 x
= SUBREG_REG (orig_rtx
);
1134 unsigned int regno
= REGNO (x
);
1135 unsigned int n
= hard_regno_nregs
[regno
][GET_MODE (x
)];
1137 kill_value_regno (regno
, n
, vd
);
1141 /* Remember that REGNO is valid in MODE. */
1144 set_value_regno (unsigned int regno
, enum machine_mode mode
,
1145 struct value_data
*vd
)
1149 vd
->e
[regno
].mode
= mode
;
1151 nregs
= hard_regno_nregs
[regno
][mode
];
1152 if (nregs
> vd
->max_value_regs
)
1153 vd
->max_value_regs
= nregs
;
1156 /* Initialize VD such that there are no known relationships between regs. */
1159 init_value_data (struct value_data
*vd
)
1162 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1164 vd
->e
[i
].mode
= VOIDmode
;
1165 vd
->e
[i
].oldest_regno
= i
;
1166 vd
->e
[i
].next_regno
= INVALID_REGNUM
;
1168 vd
->max_value_regs
= 0;
1171 /* Called through note_stores. If X is clobbered, kill its value. */
1174 kill_clobbered_value (rtx x
, rtx set
, void *data
)
1176 struct value_data
*vd
= data
;
1177 if (GET_CODE (set
) == CLOBBER
)
1181 /* Called through note_stores. If X is set, not clobbered, kill its
1182 current value and install it as the root of its own value list. */
1185 kill_set_value (rtx x
, rtx set
, void *data
)
1187 struct value_data
*vd
= data
;
1188 if (GET_CODE (set
) != CLOBBER
)
1192 set_value_regno (REGNO (x
), GET_MODE (x
), vd
);
1196 /* Called through for_each_rtx. Kill any register used as the base of an
1197 auto-increment expression, and install that register as the root of its
1201 kill_autoinc_value (rtx
*px
, void *data
)
1204 struct value_data
*vd
= data
;
1206 if (GET_RTX_CLASS (GET_CODE (x
)) == RTX_AUTOINC
)
1210 set_value_regno (REGNO (x
), Pmode
, vd
);
1217 /* Assert that SRC has been copied to DEST. Adjust the data structures
1218 to reflect that SRC contains an older copy of the shared value. */
1221 copy_value (rtx dest
, rtx src
, struct value_data
*vd
)
1223 unsigned int dr
= REGNO (dest
);
1224 unsigned int sr
= REGNO (src
);
1225 unsigned int dn
, sn
;
1228 /* ??? At present, it's possible to see noop sets. It'd be nice if
1229 this were cleaned up beforehand... */
1233 /* Do not propagate copies to the stack pointer, as that can leave
1234 memory accesses with no scheduling dependency on the stack update. */
1235 if (dr
== STACK_POINTER_REGNUM
)
1238 /* Likewise with the frame pointer, if we're using one. */
1239 if (frame_pointer_needed
&& dr
== HARD_FRAME_POINTER_REGNUM
)
1242 /* Do not propagate copies to fixed or global registers, patterns
1243 can be relying to see particular fixed register or users can
1244 expect the chosen global register in asm. */
1245 if (fixed_regs
[dr
] || global_regs
[dr
])
1248 /* If SRC and DEST overlap, don't record anything. */
1249 dn
= hard_regno_nregs
[dr
][GET_MODE (dest
)];
1250 sn
= hard_regno_nregs
[sr
][GET_MODE (dest
)];
1251 if ((dr
> sr
&& dr
< sr
+ sn
)
1252 || (sr
> dr
&& sr
< dr
+ dn
))
1255 /* If SRC had no assigned mode (i.e. we didn't know it was live)
1256 assign it now and assume the value came from an input argument
1258 if (vd
->e
[sr
].mode
== VOIDmode
)
1259 set_value_regno (sr
, vd
->e
[dr
].mode
, vd
);
1261 /* If we are narrowing the input to a smaller number of hard regs,
1262 and it is in big endian, we are really extracting a high part.
1263 Since we generally associate a low part of a value with the value itself,
1264 we must not do the same for the high part.
1265 Note we can still get low parts for the same mode combination through
1266 a two-step copy involving differently sized hard regs.
1267 Assume hard regs fr* are 32 bits bits each, while r* are 64 bits each:
1268 (set (reg:DI r0) (reg:DI fr0))
1269 (set (reg:SI fr2) (reg:SI r0))
1270 loads the low part of (reg:DI fr0) - i.e. fr1 - into fr2, while:
1271 (set (reg:SI fr2) (reg:SI fr0))
1272 loads the high part of (reg:DI fr0) into fr2.
1274 We can't properly represent the latter case in our tables, so don't
1275 record anything then. */
1276 else if (sn
< (unsigned int) hard_regno_nregs
[sr
][vd
->e
[sr
].mode
]
1277 && (GET_MODE_SIZE (vd
->e
[sr
].mode
) > UNITS_PER_WORD
1278 ? WORDS_BIG_ENDIAN
: BYTES_BIG_ENDIAN
))
1281 /* If SRC had been assigned a mode narrower than the copy, we can't
1282 link DEST into the chain, because not all of the pieces of the
1283 copy came from oldest_regno. */
1284 else if (sn
> (unsigned int) hard_regno_nregs
[sr
][vd
->e
[sr
].mode
])
1287 /* Link DR at the end of the value chain used by SR. */
1289 vd
->e
[dr
].oldest_regno
= vd
->e
[sr
].oldest_regno
;
1291 for (i
= sr
; vd
->e
[i
].next_regno
!= INVALID_REGNUM
; i
= vd
->e
[i
].next_regno
)
1293 vd
->e
[i
].next_regno
= dr
;
1295 #ifdef ENABLE_CHECKING
1296 validate_value_data (vd
);
1300 /* Return true if a mode change from ORIG to NEW is allowed for REGNO. */
1303 mode_change_ok (enum machine_mode orig_mode
, enum machine_mode new_mode
,
1304 unsigned int regno ATTRIBUTE_UNUSED
)
1306 if (GET_MODE_SIZE (orig_mode
) < GET_MODE_SIZE (new_mode
))
1309 #ifdef CANNOT_CHANGE_MODE_CLASS
1310 return !REG_CANNOT_CHANGE_MODE_P (regno
, orig_mode
, new_mode
);
1316 /* Register REGNO was originally set in ORIG_MODE. It - or a copy of it -
1317 was copied in COPY_MODE to COPY_REGNO, and then COPY_REGNO was accessed
1319 Return a NEW_MODE rtx for REGNO if that's OK, otherwise return NULL_RTX. */
1322 maybe_mode_change (enum machine_mode orig_mode
, enum machine_mode copy_mode
,
1323 enum machine_mode new_mode
, unsigned int regno
,
1324 unsigned int copy_regno ATTRIBUTE_UNUSED
)
1326 if (orig_mode
== new_mode
)
1327 return gen_rtx_raw_REG (new_mode
, regno
);
1328 else if (mode_change_ok (orig_mode
, new_mode
, regno
))
1330 int copy_nregs
= hard_regno_nregs
[copy_regno
][copy_mode
];
1331 int use_nregs
= hard_regno_nregs
[copy_regno
][new_mode
];
1333 = GET_MODE_SIZE (copy_mode
) / copy_nregs
* (copy_nregs
- use_nregs
);
1335 = GET_MODE_SIZE (orig_mode
) - GET_MODE_SIZE (new_mode
) - copy_offset
;
1336 int byteoffset
= offset
% UNITS_PER_WORD
;
1337 int wordoffset
= offset
- byteoffset
;
1339 offset
= ((WORDS_BIG_ENDIAN
? wordoffset
: 0)
1340 + (BYTES_BIG_ENDIAN
? byteoffset
: 0));
1341 return gen_rtx_raw_REG (new_mode
,
1342 regno
+ subreg_regno_offset (regno
, orig_mode
,
1349 /* Find the oldest copy of the value contained in REGNO that is in
1350 register class CL and has mode MODE. If found, return an rtx
1351 of that oldest register, otherwise return NULL. */
1354 find_oldest_value_reg (enum reg_class cl
, rtx reg
, struct value_data
*vd
)
1356 unsigned int regno
= REGNO (reg
);
1357 enum machine_mode mode
= GET_MODE (reg
);
1360 /* If we are accessing REG in some mode other that what we set it in,
1361 make sure that the replacement is valid. In particular, consider
1362 (set (reg:DI r11) (...))
1363 (set (reg:SI r9) (reg:SI r11))
1364 (set (reg:SI r10) (...))
1365 (set (...) (reg:DI r9))
1366 Replacing r9 with r11 is invalid. */
1367 if (mode
!= vd
->e
[regno
].mode
)
1369 if (hard_regno_nregs
[regno
][mode
]
1370 > hard_regno_nregs
[regno
][vd
->e
[regno
].mode
])
1374 for (i
= vd
->e
[regno
].oldest_regno
; i
!= regno
; i
= vd
->e
[i
].next_regno
)
1376 enum machine_mode oldmode
= vd
->e
[i
].mode
;
1379 if (!in_hard_reg_set_p (reg_class_contents
[cl
], mode
, i
))
1382 new = maybe_mode_change (oldmode
, vd
->e
[regno
].mode
, mode
, i
, regno
);
1385 ORIGINAL_REGNO (new) = ORIGINAL_REGNO (reg
);
1386 REG_ATTRS (new) = REG_ATTRS (reg
);
1394 /* If possible, replace the register at *LOC with the oldest register
1395 in register class CL. Return true if successfully replaced. */
1398 replace_oldest_value_reg (rtx
*loc
, enum reg_class cl
, rtx insn
,
1399 struct value_data
*vd
)
1401 rtx
new = find_oldest_value_reg (cl
, *loc
, vd
);
1405 fprintf (dump_file
, "insn %u: replaced reg %u with %u\n",
1406 INSN_UID (insn
), REGNO (*loc
), REGNO (new));
1408 validate_change (insn
, loc
, new, 1);
1414 /* Similar to replace_oldest_value_reg, but *LOC contains an address.
1415 Adapted from find_reloads_address_1. CL is INDEX_REG_CLASS or
1416 BASE_REG_CLASS depending on how the register is being considered. */
1419 replace_oldest_value_addr (rtx
*loc
, enum reg_class cl
,
1420 enum machine_mode mode
, rtx insn
,
1421 struct value_data
*vd
)
1424 RTX_CODE code
= GET_CODE (x
);
1427 bool changed
= false;
1433 rtx orig_op0
= XEXP (x
, 0);
1434 rtx orig_op1
= XEXP (x
, 1);
1435 RTX_CODE code0
= GET_CODE (orig_op0
);
1436 RTX_CODE code1
= GET_CODE (orig_op1
);
1441 enum rtx_code index_code
= SCRATCH
;
1443 if (GET_CODE (op0
) == SUBREG
)
1445 op0
= SUBREG_REG (op0
);
1446 code0
= GET_CODE (op0
);
1449 if (GET_CODE (op1
) == SUBREG
)
1451 op1
= SUBREG_REG (op1
);
1452 code1
= GET_CODE (op1
);
1455 if (code0
== MULT
|| code0
== SIGN_EXTEND
|| code0
== TRUNCATE
1456 || code0
== ZERO_EXTEND
|| code1
== MEM
)
1458 locI
= &XEXP (x
, 0);
1459 locB
= &XEXP (x
, 1);
1460 index_code
= GET_CODE (*locI
);
1462 else if (code1
== MULT
|| code1
== SIGN_EXTEND
|| code1
== TRUNCATE
1463 || code1
== ZERO_EXTEND
|| code0
== MEM
)
1465 locI
= &XEXP (x
, 1);
1466 locB
= &XEXP (x
, 0);
1467 index_code
= GET_CODE (*locI
);
1469 else if (code0
== CONST_INT
|| code0
== CONST
1470 || code0
== SYMBOL_REF
|| code0
== LABEL_REF
)
1472 locB
= &XEXP (x
, 1);
1473 index_code
= GET_CODE (XEXP (x
, 0));
1475 else if (code1
== CONST_INT
|| code1
== CONST
1476 || code1
== SYMBOL_REF
|| code1
== LABEL_REF
)
1478 locB
= &XEXP (x
, 0);
1479 index_code
= GET_CODE (XEXP (x
, 1));
1481 else if (code0
== REG
&& code1
== REG
)
1484 unsigned regno0
= REGNO (op0
), regno1
= REGNO (op1
);
1486 if (REGNO_OK_FOR_INDEX_P (regno0
)
1487 && regno_ok_for_base_p (regno1
, mode
, PLUS
, REG
))
1489 else if (REGNO_OK_FOR_INDEX_P (regno1
)
1490 && regno_ok_for_base_p (regno0
, mode
, PLUS
, REG
))
1492 else if (regno_ok_for_base_p (regno1
, mode
, PLUS
, REG
))
1494 else if (regno_ok_for_base_p (regno0
, mode
, PLUS
, REG
))
1496 else if (REGNO_OK_FOR_INDEX_P (regno1
))
1501 locI
= &XEXP (x
, index_op
);
1502 locB
= &XEXP (x
, !index_op
);
1503 index_code
= GET_CODE (*locI
);
1505 else if (code0
== REG
)
1507 locI
= &XEXP (x
, 0);
1508 locB
= &XEXP (x
, 1);
1509 index_code
= GET_CODE (*locI
);
1511 else if (code1
== REG
)
1513 locI
= &XEXP (x
, 1);
1514 locB
= &XEXP (x
, 0);
1515 index_code
= GET_CODE (*locI
);
1519 changed
|= replace_oldest_value_addr (locI
, INDEX_REG_CLASS
, mode
,
1522 changed
|= replace_oldest_value_addr (locB
,
1523 base_reg_class (mode
, PLUS
,
1538 return replace_oldest_value_mem (x
, insn
, vd
);
1541 return replace_oldest_value_reg (loc
, cl
, insn
, vd
);
1547 fmt
= GET_RTX_FORMAT (code
);
1548 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1551 changed
|= replace_oldest_value_addr (&XEXP (x
, i
), cl
, mode
,
1553 else if (fmt
[i
] == 'E')
1554 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
1555 changed
|= replace_oldest_value_addr (&XVECEXP (x
, i
, j
), cl
,
1562 /* Similar to replace_oldest_value_reg, but X contains a memory. */
1565 replace_oldest_value_mem (rtx x
, rtx insn
, struct value_data
*vd
)
1567 return replace_oldest_value_addr (&XEXP (x
, 0),
1568 base_reg_class (GET_MODE (x
), MEM
,
1570 GET_MODE (x
), insn
, vd
);
1573 /* Perform the forward copy propagation on basic block BB. */
1576 copyprop_hardreg_forward_1 (basic_block bb
, struct value_data
*vd
)
1578 bool changed
= false;
1581 for (insn
= BB_HEAD (bb
); ; insn
= NEXT_INSN (insn
))
1583 int n_ops
, i
, alt
, predicated
;
1584 bool is_asm
, any_replacements
;
1586 bool replaced
[MAX_RECOG_OPERANDS
];
1588 if (! INSN_P (insn
))
1590 if (insn
== BB_END (bb
))
1596 set
= single_set (insn
);
1597 extract_insn (insn
);
1598 if (! constrain_operands (1))
1599 fatal_insn_not_found (insn
);
1600 preprocess_constraints ();
1601 alt
= which_alternative
;
1602 n_ops
= recog_data
.n_operands
;
1603 is_asm
= asm_noperands (PATTERN (insn
)) >= 0;
1605 /* Simplify the code below by rewriting things to reflect
1606 matching constraints. Also promote OP_OUT to OP_INOUT
1607 in predicated instructions. */
1609 predicated
= GET_CODE (PATTERN (insn
)) == COND_EXEC
;
1610 for (i
= 0; i
< n_ops
; ++i
)
1612 int matches
= recog_op_alt
[i
][alt
].matches
;
1614 recog_op_alt
[i
][alt
].cl
= recog_op_alt
[matches
][alt
].cl
;
1615 if (matches
>= 0 || recog_op_alt
[i
][alt
].matched
>= 0
1616 || (predicated
&& recog_data
.operand_type
[i
] == OP_OUT
))
1617 recog_data
.operand_type
[i
] = OP_INOUT
;
1620 /* For each earlyclobber operand, zap the value data. */
1621 for (i
= 0; i
< n_ops
; i
++)
1622 if (recog_op_alt
[i
][alt
].earlyclobber
)
1623 kill_value (recog_data
.operand
[i
], vd
);
1625 /* Within asms, a clobber cannot overlap inputs or outputs.
1626 I wouldn't think this were true for regular insns, but
1627 scan_rtx treats them like that... */
1628 note_stores (PATTERN (insn
), kill_clobbered_value
, vd
);
1630 /* Kill all auto-incremented values. */
1631 /* ??? REG_INC is useless, since stack pushes aren't done that way. */
1632 for_each_rtx (&PATTERN (insn
), kill_autoinc_value
, vd
);
1634 /* Kill all early-clobbered operands. */
1635 for (i
= 0; i
< n_ops
; i
++)
1636 if (recog_op_alt
[i
][alt
].earlyclobber
)
1637 kill_value (recog_data
.operand
[i
], vd
);
1639 /* Special-case plain move instructions, since we may well
1640 be able to do the move from a different register class. */
1641 if (set
&& REG_P (SET_SRC (set
)))
1643 rtx src
= SET_SRC (set
);
1644 unsigned int regno
= REGNO (src
);
1645 enum machine_mode mode
= GET_MODE (src
);
1649 /* If we are accessing SRC in some mode other that what we
1650 set it in, make sure that the replacement is valid. */
1651 if (mode
!= vd
->e
[regno
].mode
)
1653 if (hard_regno_nregs
[regno
][mode
]
1654 > hard_regno_nregs
[regno
][vd
->e
[regno
].mode
])
1655 goto no_move_special_case
;
1658 /* If the destination is also a register, try to find a source
1659 register in the same class. */
1660 if (REG_P (SET_DEST (set
)))
1662 new = find_oldest_value_reg (REGNO_REG_CLASS (regno
), src
, vd
);
1663 if (new && validate_change (insn
, &SET_SRC (set
), new, 0))
1667 "insn %u: replaced reg %u with %u\n",
1668 INSN_UID (insn
), regno
, REGNO (new));
1670 goto did_replacement
;
1674 /* Otherwise, try all valid registers and see if its valid. */
1675 for (i
= vd
->e
[regno
].oldest_regno
; i
!= regno
;
1676 i
= vd
->e
[i
].next_regno
)
1678 new = maybe_mode_change (vd
->e
[i
].mode
, vd
->e
[regno
].mode
,
1680 if (new != NULL_RTX
)
1682 if (validate_change (insn
, &SET_SRC (set
), new, 0))
1684 ORIGINAL_REGNO (new) = ORIGINAL_REGNO (src
);
1685 REG_ATTRS (new) = REG_ATTRS (src
);
1688 "insn %u: replaced reg %u with %u\n",
1689 INSN_UID (insn
), regno
, REGNO (new));
1691 goto did_replacement
;
1696 no_move_special_case
:
1698 any_replacements
= false;
1700 /* For each input operand, replace a hard register with the
1701 eldest live copy that's in an appropriate register class. */
1702 for (i
= 0; i
< n_ops
; i
++)
1704 replaced
[i
] = false;
1706 /* Don't scan match_operand here, since we've no reg class
1707 information to pass down. Any operands that we could
1708 substitute in will be represented elsewhere. */
1709 if (recog_data
.constraints
[i
][0] == '\0')
1712 /* Don't replace in asms intentionally referencing hard regs. */
1713 if (is_asm
&& REG_P (recog_data
.operand
[i
])
1714 && (REGNO (recog_data
.operand
[i
])
1715 == ORIGINAL_REGNO (recog_data
.operand
[i
])))
1718 if (recog_data
.operand_type
[i
] == OP_IN
)
1720 if (recog_op_alt
[i
][alt
].is_address
)
1722 = replace_oldest_value_addr (recog_data
.operand_loc
[i
],
1723 recog_op_alt
[i
][alt
].cl
,
1724 VOIDmode
, insn
, vd
);
1725 else if (REG_P (recog_data
.operand
[i
]))
1727 = replace_oldest_value_reg (recog_data
.operand_loc
[i
],
1728 recog_op_alt
[i
][alt
].cl
,
1730 else if (MEM_P (recog_data
.operand
[i
]))
1731 replaced
[i
] = replace_oldest_value_mem (recog_data
.operand
[i
],
1734 else if (MEM_P (recog_data
.operand
[i
]))
1735 replaced
[i
] = replace_oldest_value_mem (recog_data
.operand
[i
],
1738 /* If we performed any replacement, update match_dups. */
1744 new = *recog_data
.operand_loc
[i
];
1745 recog_data
.operand
[i
] = new;
1746 for (j
= 0; j
< recog_data
.n_dups
; j
++)
1747 if (recog_data
.dup_num
[j
] == i
)
1748 validate_change (insn
, recog_data
.dup_loc
[j
], new, 1);
1750 any_replacements
= true;
1754 if (any_replacements
)
1756 if (! apply_change_group ())
1758 for (i
= 0; i
< n_ops
; i
++)
1761 rtx old
= *recog_data
.operand_loc
[i
];
1762 recog_data
.operand
[i
] = old
;
1767 "insn %u: reg replacements not verified\n",
1775 /* Clobber call-clobbered registers. */
1777 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1778 if (TEST_HARD_REG_BIT (regs_invalidated_by_call
, i
))
1779 kill_value_regno (i
, 1, vd
);
1781 /* Notice stores. */
1782 note_stores (PATTERN (insn
), kill_set_value
, vd
);
1784 /* Notice copies. */
1785 if (set
&& REG_P (SET_DEST (set
)) && REG_P (SET_SRC (set
)))
1786 copy_value (SET_DEST (set
), SET_SRC (set
), vd
);
1788 if (insn
== BB_END (bb
))
1795 /* Main entry point for the forward copy propagation optimization. */
1798 copyprop_hardreg_forward (void)
1800 struct value_data
*all_vd
;
1804 all_vd
= XNEWVEC (struct value_data
, last_basic_block
);
1806 visited
= sbitmap_alloc (last_basic_block
);
1807 sbitmap_zero (visited
);
1811 SET_BIT (visited
, bb
->index
);
1813 /* If a block has a single predecessor, that we've already
1814 processed, begin with the value data that was live at
1815 the end of the predecessor block. */
1816 /* ??? Ought to use more intelligent queuing of blocks. */
1817 if (single_pred_p (bb
)
1818 && TEST_BIT (visited
, single_pred (bb
)->index
)
1819 && ! (single_pred_edge (bb
)->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
)))
1820 all_vd
[bb
->index
] = all_vd
[single_pred (bb
)->index
];
1822 init_value_data (all_vd
+ bb
->index
);
1824 copyprop_hardreg_forward_1 (bb
, all_vd
+ bb
->index
);
1827 sbitmap_free (visited
);
1831 /* Dump the value chain data to stderr. */
1834 debug_value_data (struct value_data
*vd
)
1839 CLEAR_HARD_REG_SET (set
);
1841 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1842 if (vd
->e
[i
].oldest_regno
== i
)
1844 if (vd
->e
[i
].mode
== VOIDmode
)
1846 if (vd
->e
[i
].next_regno
!= INVALID_REGNUM
)
1847 fprintf (stderr
, "[%u] Bad next_regno for empty chain (%u)\n",
1848 i
, vd
->e
[i
].next_regno
);
1852 SET_HARD_REG_BIT (set
, i
);
1853 fprintf (stderr
, "[%u %s] ", i
, GET_MODE_NAME (vd
->e
[i
].mode
));
1855 for (j
= vd
->e
[i
].next_regno
;
1856 j
!= INVALID_REGNUM
;
1857 j
= vd
->e
[j
].next_regno
)
1859 if (TEST_HARD_REG_BIT (set
, j
))
1861 fprintf (stderr
, "[%u] Loop in regno chain\n", j
);
1865 if (vd
->e
[j
].oldest_regno
!= i
)
1867 fprintf (stderr
, "[%u] Bad oldest_regno (%u)\n",
1868 j
, vd
->e
[j
].oldest_regno
);
1871 SET_HARD_REG_BIT (set
, j
);
1872 fprintf (stderr
, "[%u %s] ", j
, GET_MODE_NAME (vd
->e
[j
].mode
));
1874 fputc ('\n', stderr
);
1877 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1878 if (! TEST_HARD_REG_BIT (set
, i
)
1879 && (vd
->e
[i
].mode
!= VOIDmode
1880 || vd
->e
[i
].oldest_regno
!= i
1881 || vd
->e
[i
].next_regno
!= INVALID_REGNUM
))
1882 fprintf (stderr
, "[%u] Non-empty reg in chain (%s %u %i)\n",
1883 i
, GET_MODE_NAME (vd
->e
[i
].mode
), vd
->e
[i
].oldest_regno
,
1884 vd
->e
[i
].next_regno
);
1887 #ifdef ENABLE_CHECKING
1889 validate_value_data (struct value_data
*vd
)
1894 CLEAR_HARD_REG_SET (set
);
1896 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1897 if (vd
->e
[i
].oldest_regno
== i
)
1899 if (vd
->e
[i
].mode
== VOIDmode
)
1901 if (vd
->e
[i
].next_regno
!= INVALID_REGNUM
)
1902 internal_error ("validate_value_data: [%u] Bad next_regno for empty chain (%u)",
1903 i
, vd
->e
[i
].next_regno
);
1907 SET_HARD_REG_BIT (set
, i
);
1909 for (j
= vd
->e
[i
].next_regno
;
1910 j
!= INVALID_REGNUM
;
1911 j
= vd
->e
[j
].next_regno
)
1913 if (TEST_HARD_REG_BIT (set
, j
))
1914 internal_error ("validate_value_data: Loop in regno chain (%u)",
1916 if (vd
->e
[j
].oldest_regno
!= i
)
1917 internal_error ("validate_value_data: [%u] Bad oldest_regno (%u)",
1918 j
, vd
->e
[j
].oldest_regno
);
1920 SET_HARD_REG_BIT (set
, j
);
1924 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1925 if (! TEST_HARD_REG_BIT (set
, i
)
1926 && (vd
->e
[i
].mode
!= VOIDmode
1927 || vd
->e
[i
].oldest_regno
!= i
1928 || vd
->e
[i
].next_regno
!= INVALID_REGNUM
))
1929 internal_error ("validate_value_data: [%u] Non-empty reg in chain (%s %u %i)",
1930 i
, GET_MODE_NAME (vd
->e
[i
].mode
), vd
->e
[i
].oldest_regno
,
1931 vd
->e
[i
].next_regno
);
1936 gate_handle_regrename (void)
1938 return (optimize
> 0 && (flag_rename_registers
));
1942 /* Run the regrename and cprop passes. */
1944 rest_of_handle_regrename (void)
1946 regrename_optimize ();
1950 struct tree_opt_pass pass_regrename
=
1953 gate_handle_regrename
, /* gate */
1954 rest_of_handle_regrename
, /* execute */
1957 0, /* static_pass_number */
1958 TV_RENAME_REGISTERS
, /* tv_id */
1959 0, /* properties_required */
1960 0, /* properties_provided */
1961 0, /* properties_destroyed */
1962 0, /* todo_flags_start */
1964 TODO_dump_func
, /* todo_flags_finish */
1969 gate_handle_cprop (void)
1971 return (optimize
> 0 && (flag_cprop_registers
));
1975 /* Run the regrename and cprop passes. */
1977 rest_of_handle_cprop (void)
1979 copyprop_hardreg_forward ();
1983 struct tree_opt_pass pass_cprop_hardreg
=
1985 "cprop_hardreg", /* name */
1986 gate_handle_cprop
, /* gate */
1987 rest_of_handle_cprop
, /* execute */
1990 0, /* static_pass_number */
1991 TV_RENAME_REGISTERS
, /* tv_id */
1992 0, /* properties_required */
1993 0, /* properties_provided */
1994 0, /* properties_destroyed */
1995 0, /* todo_flags_start */
1996 TODO_dump_func
, /* todo_flags_finish */