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 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"
40 #include "tree-pass.h"
45 struct du_chain
*next_chain
;
46 struct du_chain
*next_use
;
50 ENUM_BITFIELD(reg_class
) cl
: 16;
51 unsigned int need_caller_save_reg
:1;
52 unsigned int earlyclobber
:1;
58 terminate_overlapping_read
,
63 /* mark_access is for marking the destination regs in
64 REG_FRAME_RELATED_EXPR notes (as if they were read) so that the
65 note is updated properly. */
69 static const char * const scan_actions_name
[] =
72 "terminate_overlapping_read",
80 static struct obstack rename_obstack
;
82 static void do_replace (struct du_chain
*, int);
83 static void scan_rtx_reg (rtx
, rtx
*, enum reg_class
,
84 enum scan_actions
, enum op_type
, int);
85 static void scan_rtx_address (rtx
, rtx
*, enum reg_class
,
86 enum scan_actions
, enum machine_mode
);
87 static void scan_rtx (rtx
, rtx
*, enum reg_class
, enum scan_actions
,
89 static struct du_chain
*build_def_use (basic_block
);
90 static void dump_def_use_chain (struct du_chain
*);
91 static void note_sets (rtx
, const_rtx
, void *);
92 static void clear_dead_regs (HARD_REG_SET
*, enum reg_note
, rtx
);
93 static void merge_overlapping_regs (basic_block
, HARD_REG_SET
*,
96 /* Called through note_stores. Find sets of registers, and
97 record them in *DATA (which is actually a HARD_REG_SET *). */
100 note_sets (rtx x
, const_rtx set ATTRIBUTE_UNUSED
, void *data
)
102 HARD_REG_SET
*pset
= (HARD_REG_SET
*) data
;
104 if (GET_CODE (x
) == SUBREG
)
108 /* There must not be pseudos at this point. */
109 gcc_assert (HARD_REGISTER_P (x
));
110 add_to_hard_reg_set (pset
, GET_MODE (x
), REGNO (x
));
113 /* Clear all registers from *PSET for which a note of kind KIND can be found
114 in the list NOTES. */
117 clear_dead_regs (HARD_REG_SET
*pset
, enum reg_note kind
, rtx notes
)
120 for (note
= notes
; note
; note
= XEXP (note
, 1))
121 if (REG_NOTE_KIND (note
) == kind
&& REG_P (XEXP (note
, 0)))
123 rtx reg
= XEXP (note
, 0);
124 /* There must not be pseudos at this point. */
125 gcc_assert (HARD_REGISTER_P (reg
));
126 remove_from_hard_reg_set (pset
, GET_MODE (reg
), REGNO (reg
));
130 /* For a def-use chain CHAIN in basic block B, find which registers overlap
131 its lifetime and set the corresponding bits in *PSET. */
134 merge_overlapping_regs (basic_block b
, HARD_REG_SET
*pset
,
135 struct du_chain
*chain
)
137 struct du_chain
*t
= chain
;
141 REG_SET_TO_HARD_REG_SET (live
, df_get_live_in (b
));
145 /* Search forward until the next reference to the register to be
147 while (insn
!= t
->insn
)
151 clear_dead_regs (&live
, REG_DEAD
, REG_NOTES (insn
));
152 note_stores (PATTERN (insn
), note_sets
, (void *) &live
);
153 /* Only record currently live regs if we are inside the
156 IOR_HARD_REG_SET (*pset
, live
);
157 clear_dead_regs (&live
, REG_UNUSED
, REG_NOTES (insn
));
159 insn
= NEXT_INSN (insn
);
162 IOR_HARD_REG_SET (*pset
, live
);
164 /* For the last reference, also merge in all registers set in the
166 @@@ We only have take earlyclobbered sets into account. */
168 note_stores (PATTERN (insn
), note_sets
, (void *) pset
);
174 /* Perform register renaming on the current function. */
177 regrename_optimize (void)
179 int tick
[FIRST_PSEUDO_REGISTER
];
184 df_set_flags (DF_LR_RUN_DCE
);
185 df_note_add_problem ();
187 df_set_flags (DF_DEFER_INSN_RESCAN
);
189 memset (tick
, 0, sizeof tick
);
191 gcc_obstack_init (&rename_obstack
);
192 first_obj
= XOBNEWVAR (&rename_obstack
, char, 0);
196 struct du_chain
*all_chains
= 0;
197 HARD_REG_SET unavailable
;
198 HARD_REG_SET regs_seen
;
200 CLEAR_HARD_REG_SET (unavailable
);
203 fprintf (dump_file
, "\nBasic block %d:\n", bb
->index
);
205 all_chains
= build_def_use (bb
);
208 dump_def_use_chain (all_chains
);
210 CLEAR_HARD_REG_SET (unavailable
);
211 /* Don't clobber traceback for noreturn functions. */
212 if (frame_pointer_needed
)
214 add_to_hard_reg_set (&unavailable
, Pmode
, FRAME_POINTER_REGNUM
);
215 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
216 add_to_hard_reg_set (&unavailable
, Pmode
, HARD_FRAME_POINTER_REGNUM
);
220 CLEAR_HARD_REG_SET (regs_seen
);
223 int new_reg
, best_new_reg
;
225 struct du_chain
*this_du
= all_chains
;
226 struct du_chain
*tmp
, *last
;
227 HARD_REG_SET this_unavailable
;
228 int reg
= REGNO (*this_du
->loc
);
231 all_chains
= this_du
->next_chain
;
235 #if 0 /* This just disables optimization opportunities. */
236 /* Only rename once we've seen the reg more than once. */
237 if (! TEST_HARD_REG_BIT (regs_seen
, reg
))
239 SET_HARD_REG_BIT (regs_seen
, reg
);
244 if (fixed_regs
[reg
] || global_regs
[reg
]
245 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
246 || (frame_pointer_needed
&& reg
== HARD_FRAME_POINTER_REGNUM
)
248 || (frame_pointer_needed
&& reg
== FRAME_POINTER_REGNUM
)
253 COPY_HARD_REG_SET (this_unavailable
, unavailable
);
255 /* Find last entry on chain (which has the need_caller_save bit),
256 count number of uses, and narrow the set of registers we can
259 for (last
= this_du
; last
->next_use
; last
= last
->next_use
)
262 IOR_COMPL_HARD_REG_SET (this_unavailable
,
263 reg_class_contents
[last
->cl
]);
268 IOR_COMPL_HARD_REG_SET (this_unavailable
,
269 reg_class_contents
[last
->cl
]);
271 if (this_du
->need_caller_save_reg
)
272 IOR_HARD_REG_SET (this_unavailable
, call_used_reg_set
);
274 merge_overlapping_regs (bb
, &this_unavailable
, this_du
);
276 /* Now potential_regs is a reasonable approximation, let's
277 have a closer look at each register still in there. */
278 for (new_reg
= 0; new_reg
< FIRST_PSEUDO_REGISTER
; new_reg
++)
280 int nregs
= hard_regno_nregs
[new_reg
][GET_MODE (*this_du
->loc
)];
282 for (i
= nregs
- 1; i
>= 0; --i
)
283 if (TEST_HARD_REG_BIT (this_unavailable
, new_reg
+ i
)
284 || fixed_regs
[new_reg
+ i
]
285 || global_regs
[new_reg
+ i
]
286 /* Can't use regs which aren't saved by the prologue. */
287 || (! df_regs_ever_live_p (new_reg
+ i
)
288 && ! call_used_regs
[new_reg
+ i
])
289 #ifdef LEAF_REGISTERS
290 /* We can't use a non-leaf register if we're in a
292 || (current_function_is_leaf
293 && !LEAF_REGISTERS
[new_reg
+ i
])
295 #ifdef HARD_REGNO_RENAME_OK
296 || ! HARD_REGNO_RENAME_OK (reg
+ i
, new_reg
+ i
)
303 /* See whether it accepts all modes that occur in
304 definition and uses. */
305 for (tmp
= this_du
; tmp
; tmp
= tmp
->next_use
)
306 if (! HARD_REGNO_MODE_OK (new_reg
, GET_MODE (*tmp
->loc
))
307 || (tmp
->need_caller_save_reg
308 && ! (HARD_REGNO_CALL_PART_CLOBBERED
309 (reg
, GET_MODE (*tmp
->loc
)))
310 && (HARD_REGNO_CALL_PART_CLOBBERED
311 (new_reg
, GET_MODE (*tmp
->loc
)))))
315 if (tick
[best_new_reg
] > tick
[new_reg
])
316 best_new_reg
= new_reg
;
322 fprintf (dump_file
, "Register %s in insn %d",
323 reg_names
[reg
], INSN_UID (last
->insn
));
324 if (last
->need_caller_save_reg
)
325 fprintf (dump_file
, " crosses a call");
328 if (best_new_reg
== reg
)
330 tick
[reg
] = ++this_tick
;
332 fprintf (dump_file
, "; no available better choice\n");
336 do_replace (this_du
, best_new_reg
);
337 tick
[best_new_reg
] = ++this_tick
;
338 df_set_regs_ever_live (best_new_reg
, true);
341 fprintf (dump_file
, ", renamed as %s\n", reg_names
[best_new_reg
]);
344 obstack_free (&rename_obstack
, first_obj
);
347 obstack_free (&rename_obstack
, NULL
);
350 fputc ('\n', dump_file
);
354 do_replace (struct du_chain
*chain
, int reg
)
358 unsigned int regno
= ORIGINAL_REGNO (*chain
->loc
);
359 struct reg_attrs
* attr
= REG_ATTRS (*chain
->loc
);
361 *chain
->loc
= gen_raw_REG (GET_MODE (*chain
->loc
), reg
);
362 if (regno
>= FIRST_PSEUDO_REGISTER
)
363 ORIGINAL_REGNO (*chain
->loc
) = regno
;
364 REG_ATTRS (*chain
->loc
) = attr
;
365 df_insn_rescan (chain
->insn
);
366 chain
= chain
->next_use
;
371 static struct du_chain
*open_chains
;
372 static struct du_chain
*closed_chains
;
375 scan_rtx_reg (rtx insn
, rtx
*loc
, enum reg_class cl
,
376 enum scan_actions action
, enum op_type type
, int earlyclobber
)
380 enum machine_mode mode
= GET_MODE (x
);
381 int this_regno
= REGNO (x
);
382 int this_nregs
= hard_regno_nregs
[this_regno
][mode
];
384 if (action
== mark_write
)
388 struct du_chain
*this_du
= XOBNEW (&rename_obstack
, struct du_chain
);
389 this_du
->next_use
= 0;
390 this_du
->next_chain
= open_chains
;
392 this_du
->insn
= insn
;
394 this_du
->need_caller_save_reg
= 0;
395 this_du
->earlyclobber
= earlyclobber
;
396 open_chains
= this_du
;
401 if ((type
== OP_OUT
) != (action
== terminate_write
|| action
== mark_access
))
404 for (p
= &open_chains
; *p
;)
406 struct du_chain
*this_du
= *p
;
408 /* Check if the chain has been terminated if it has then skip to
411 This can happen when we've already appended the location to
412 the chain in Step 3, but are trying to hide in-out operands
413 from terminate_write in Step 5. */
415 if (*this_du
->loc
== cc0_rtx
)
416 p
= &this_du
->next_chain
;
419 int regno
= REGNO (*this_du
->loc
);
420 int nregs
= hard_regno_nregs
[regno
][GET_MODE (*this_du
->loc
)];
421 int exact_match
= (regno
== this_regno
&& nregs
== this_nregs
);
423 if (regno
+ nregs
<= this_regno
424 || this_regno
+ this_nregs
<= regno
)
426 p
= &this_du
->next_chain
;
430 if (action
== mark_read
|| action
== mark_access
)
432 gcc_assert (exact_match
);
434 /* ??? Class NO_REGS can happen if the md file makes use of
435 EXTRA_CONSTRAINTS to match registers. Which is arguably
436 wrong, but there we are. Since we know not what this may
437 be replaced with, terminate the chain. */
440 this_du
= XOBNEW (&rename_obstack
, struct du_chain
);
441 this_du
->next_use
= 0;
442 this_du
->next_chain
= (*p
)->next_chain
;
444 this_du
->insn
= insn
;
446 this_du
->need_caller_save_reg
= 0;
454 if (action
!= terminate_overlapping_read
|| ! exact_match
)
456 struct du_chain
*next
= this_du
->next_chain
;
458 /* Whether the terminated chain can be used for renaming
459 depends on the action and this being an exact match.
460 In either case, we remove this element from open_chains. */
462 if ((action
== terminate_dead
|| action
== terminate_write
)
465 this_du
->next_chain
= closed_chains
;
466 closed_chains
= this_du
;
469 "Closing chain %s at insn %d (%s)\n",
470 reg_names
[REGNO (*this_du
->loc
)], INSN_UID (insn
),
471 scan_actions_name
[(int) action
]);
477 "Discarding chain %s at insn %d (%s)\n",
478 reg_names
[REGNO (*this_du
->loc
)], INSN_UID (insn
),
479 scan_actions_name
[(int) action
]);
484 p
= &this_du
->next_chain
;
489 /* Adapted from find_reloads_address_1. CL is INDEX_REG_CLASS or
490 BASE_REG_CLASS depending on how the register is being considered. */
493 scan_rtx_address (rtx insn
, rtx
*loc
, enum reg_class cl
,
494 enum scan_actions action
, enum machine_mode mode
)
497 RTX_CODE code
= GET_CODE (x
);
501 if (action
== mark_write
|| action
== mark_access
)
508 rtx orig_op0
= XEXP (x
, 0);
509 rtx orig_op1
= XEXP (x
, 1);
510 RTX_CODE code0
= GET_CODE (orig_op0
);
511 RTX_CODE code1
= GET_CODE (orig_op1
);
516 enum rtx_code index_code
= SCRATCH
;
518 if (GET_CODE (op0
) == SUBREG
)
520 op0
= SUBREG_REG (op0
);
521 code0
= GET_CODE (op0
);
524 if (GET_CODE (op1
) == SUBREG
)
526 op1
= SUBREG_REG (op1
);
527 code1
= GET_CODE (op1
);
530 if (code0
== MULT
|| code0
== SIGN_EXTEND
|| code0
== TRUNCATE
531 || code0
== ZERO_EXTEND
|| code1
== MEM
)
535 index_code
= GET_CODE (*locI
);
537 else if (code1
== MULT
|| code1
== SIGN_EXTEND
|| code1
== TRUNCATE
538 || code1
== ZERO_EXTEND
|| code0
== MEM
)
542 index_code
= GET_CODE (*locI
);
544 else if (code0
== CONST_INT
|| code0
== CONST
545 || code0
== SYMBOL_REF
|| code0
== LABEL_REF
)
548 index_code
= GET_CODE (XEXP (x
, 0));
550 else if (code1
== CONST_INT
|| code1
== CONST
551 || code1
== SYMBOL_REF
|| code1
== LABEL_REF
)
554 index_code
= GET_CODE (XEXP (x
, 1));
556 else if (code0
== REG
&& code1
== REG
)
559 unsigned regno0
= REGNO (op0
), regno1
= REGNO (op1
);
561 if (REGNO_OK_FOR_INDEX_P (regno1
)
562 && regno_ok_for_base_p (regno0
, mode
, PLUS
, REG
))
564 else if (REGNO_OK_FOR_INDEX_P (regno0
)
565 && regno_ok_for_base_p (regno1
, mode
, PLUS
, REG
))
567 else if (regno_ok_for_base_p (regno0
, mode
, PLUS
, REG
)
568 || REGNO_OK_FOR_INDEX_P (regno1
))
570 else if (regno_ok_for_base_p (regno1
, mode
, PLUS
, REG
))
575 locI
= &XEXP (x
, index_op
);
576 locB
= &XEXP (x
, !index_op
);
577 index_code
= GET_CODE (*locI
);
579 else if (code0
== REG
)
583 index_code
= GET_CODE (*locI
);
585 else if (code1
== REG
)
589 index_code
= GET_CODE (*locI
);
593 scan_rtx_address (insn
, locI
, INDEX_REG_CLASS
, action
, mode
);
595 scan_rtx_address (insn
, locB
, base_reg_class (mode
, PLUS
, index_code
),
608 /* If the target doesn't claim to handle autoinc, this must be
609 something special, like a stack push. Kill this chain. */
610 action
= terminate_all_read
;
615 scan_rtx_address (insn
, &XEXP (x
, 0),
616 base_reg_class (GET_MODE (x
), MEM
, SCRATCH
), action
,
621 scan_rtx_reg (insn
, loc
, cl
, action
, OP_IN
, 0);
628 fmt
= GET_RTX_FORMAT (code
);
629 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
632 scan_rtx_address (insn
, &XEXP (x
, i
), cl
, action
, mode
);
633 else if (fmt
[i
] == 'E')
634 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
635 scan_rtx_address (insn
, &XVECEXP (x
, i
, j
), cl
, action
, mode
);
640 scan_rtx (rtx insn
, rtx
*loc
, enum reg_class cl
,
641 enum scan_actions action
, enum op_type type
, int earlyclobber
)
645 enum rtx_code code
= GET_CODE (x
);
663 scan_rtx_reg (insn
, loc
, cl
, action
, type
, earlyclobber
);
667 scan_rtx_address (insn
, &XEXP (x
, 0),
668 base_reg_class (GET_MODE (x
), MEM
, SCRATCH
), action
,
673 scan_rtx (insn
, &SET_SRC (x
), cl
, action
, OP_IN
, 0);
674 scan_rtx (insn
, &SET_DEST (x
), cl
, action
,
675 GET_CODE (PATTERN (insn
)) == COND_EXEC
? OP_INOUT
: OP_OUT
, 0);
678 case STRICT_LOW_PART
:
679 scan_rtx (insn
, &XEXP (x
, 0), cl
, action
, OP_INOUT
, earlyclobber
);
684 scan_rtx (insn
, &XEXP (x
, 0), cl
, action
,
685 type
== OP_IN
? OP_IN
: OP_INOUT
, earlyclobber
);
686 scan_rtx (insn
, &XEXP (x
, 1), cl
, action
, OP_IN
, 0);
687 scan_rtx (insn
, &XEXP (x
, 2), cl
, action
, OP_IN
, 0);
696 /* Should only happen inside MEM. */
700 scan_rtx (insn
, &SET_DEST (x
), cl
, action
,
701 GET_CODE (PATTERN (insn
)) == COND_EXEC
? OP_INOUT
: OP_OUT
, 0);
705 scan_rtx (insn
, &XEXP (x
, 0), cl
, action
, type
, 0);
707 scan_rtx (insn
, &XEXP (x
, 1), cl
, action
, type
, 0);
714 fmt
= GET_RTX_FORMAT (code
);
715 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
718 scan_rtx (insn
, &XEXP (x
, i
), cl
, action
, type
, 0);
719 else if (fmt
[i
] == 'E')
720 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
721 scan_rtx (insn
, &XVECEXP (x
, i
, j
), cl
, action
, type
, 0);
725 /* Build def/use chain. */
727 static struct du_chain
*
728 build_def_use (basic_block bb
)
732 open_chains
= closed_chains
= NULL
;
734 for (insn
= BB_HEAD (bb
); ; insn
= NEXT_INSN (insn
))
740 rtx old_operands
[MAX_RECOG_OPERANDS
];
741 rtx old_dups
[MAX_DUP_OPERANDS
];
746 /* Process the insn, determining its effect on the def-use
747 chains. We perform the following steps with the register
748 references in the insn:
749 (1) Any read that overlaps an open chain, but doesn't exactly
750 match, causes that chain to be closed. We can't deal
752 (2) Any read outside an operand causes any chain it overlaps
753 with to be closed, since we can't replace it.
754 (3) Any read inside an operand is added if there's already
755 an open chain for it.
756 (4) For any REG_DEAD note we find, close open chains that
758 (5) For any write we find, close open chains that overlap it.
759 (6) For any write we find in an operand, make a new chain.
760 (7) For any REG_UNUSED, close any chains we just opened. */
762 icode
= recog_memoized (insn
);
764 if (! constrain_operands (1))
765 fatal_insn_not_found (insn
);
766 preprocess_constraints ();
767 alt
= which_alternative
;
768 n_ops
= recog_data
.n_operands
;
770 /* Simplify the code below by rewriting things to reflect
771 matching constraints. Also promote OP_OUT to OP_INOUT
772 in predicated instructions. */
774 predicated
= GET_CODE (PATTERN (insn
)) == COND_EXEC
;
775 for (i
= 0; i
< n_ops
; ++i
)
777 int matches
= recog_op_alt
[i
][alt
].matches
;
779 recog_op_alt
[i
][alt
].cl
= recog_op_alt
[matches
][alt
].cl
;
780 if (matches
>= 0 || recog_op_alt
[i
][alt
].matched
>= 0
781 || (predicated
&& recog_data
.operand_type
[i
] == OP_OUT
))
782 recog_data
.operand_type
[i
] = OP_INOUT
;
785 /* Step 1: Close chains for which we have overlapping reads. */
786 for (i
= 0; i
< n_ops
; i
++)
787 scan_rtx (insn
, recog_data
.operand_loc
[i
],
788 NO_REGS
, terminate_overlapping_read
,
789 recog_data
.operand_type
[i
], 0);
791 /* Step 2: Close chains for which we have reads outside operands.
792 We do this by munging all operands into CC0, and closing
793 everything remaining. */
795 for (i
= 0; i
< n_ops
; i
++)
797 old_operands
[i
] = recog_data
.operand
[i
];
798 /* Don't squash match_operator or match_parallel here, since
799 we don't know that all of the contained registers are
800 reachable by proper operands. */
801 if (recog_data
.constraints
[i
][0] == '\0')
803 *recog_data
.operand_loc
[i
] = cc0_rtx
;
805 for (i
= 0; i
< recog_data
.n_dups
; i
++)
807 old_dups
[i
] = *recog_data
.dup_loc
[i
];
808 *recog_data
.dup_loc
[i
] = cc0_rtx
;
811 scan_rtx (insn
, &PATTERN (insn
), NO_REGS
, terminate_all_read
,
814 for (i
= 0; i
< recog_data
.n_dups
; i
++)
815 *recog_data
.dup_loc
[i
] = old_dups
[i
];
816 for (i
= 0; i
< n_ops
; i
++)
817 *recog_data
.operand_loc
[i
] = old_operands
[i
];
818 if (recog_data
.n_dups
)
819 df_insn_rescan (insn
);
821 /* Step 2B: Can't rename function call argument registers. */
822 if (CALL_P (insn
) && CALL_INSN_FUNCTION_USAGE (insn
))
823 scan_rtx (insn
, &CALL_INSN_FUNCTION_USAGE (insn
),
824 NO_REGS
, terminate_all_read
, OP_IN
, 0);
826 /* Step 2C: Can't rename asm operands that were originally
828 if (asm_noperands (PATTERN (insn
)) > 0)
829 for (i
= 0; i
< n_ops
; i
++)
831 rtx
*loc
= recog_data
.operand_loc
[i
];
835 && REGNO (op
) == ORIGINAL_REGNO (op
)
836 && (recog_data
.operand_type
[i
] == OP_IN
837 || recog_data
.operand_type
[i
] == OP_INOUT
))
838 scan_rtx (insn
, loc
, NO_REGS
, terminate_all_read
, OP_IN
, 0);
841 /* Step 3: Append to chains for reads inside operands. */
842 for (i
= 0; i
< n_ops
+ recog_data
.n_dups
; i
++)
844 int opn
= i
< n_ops
? i
: recog_data
.dup_num
[i
- n_ops
];
845 rtx
*loc
= (i
< n_ops
846 ? recog_data
.operand_loc
[opn
]
847 : recog_data
.dup_loc
[i
- n_ops
]);
848 enum reg_class cl
= recog_op_alt
[opn
][alt
].cl
;
849 enum op_type type
= recog_data
.operand_type
[opn
];
851 /* Don't scan match_operand here, since we've no reg class
852 information to pass down. Any operands that we could
853 substitute in will be represented elsewhere. */
854 if (recog_data
.constraints
[opn
][0] == '\0')
857 if (recog_op_alt
[opn
][alt
].is_address
)
858 scan_rtx_address (insn
, loc
, cl
, mark_read
, VOIDmode
);
860 scan_rtx (insn
, loc
, cl
, mark_read
, type
, 0);
863 /* Step 3B: Record updates for regs in REG_INC notes, and
864 source regs in REG_FRAME_RELATED_EXPR notes. */
865 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
866 if (REG_NOTE_KIND (note
) == REG_INC
867 || REG_NOTE_KIND (note
) == REG_FRAME_RELATED_EXPR
)
868 scan_rtx (insn
, &XEXP (note
, 0), ALL_REGS
, mark_read
,
871 /* Step 4: Close chains for registers that die here. */
872 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
873 if (REG_NOTE_KIND (note
) == REG_DEAD
)
874 scan_rtx (insn
, &XEXP (note
, 0), NO_REGS
, terminate_dead
,
877 /* Step 4B: If this is a call, any chain live at this point
878 requires a caller-saved reg. */
882 for (p
= open_chains
; p
; p
= p
->next_chain
)
883 p
->need_caller_save_reg
= 1;
886 /* Step 5: Close open chains that overlap writes. Similar to
887 step 2, we hide in-out operands, since we do not want to
888 close these chains. */
890 for (i
= 0; i
< n_ops
; i
++)
892 old_operands
[i
] = recog_data
.operand
[i
];
893 if (recog_data
.operand_type
[i
] == OP_INOUT
)
894 *recog_data
.operand_loc
[i
] = cc0_rtx
;
896 for (i
= 0; i
< recog_data
.n_dups
; i
++)
898 int opn
= recog_data
.dup_num
[i
];
899 old_dups
[i
] = *recog_data
.dup_loc
[i
];
900 if (recog_data
.operand_type
[opn
] == OP_INOUT
)
901 *recog_data
.dup_loc
[i
] = cc0_rtx
;
904 scan_rtx (insn
, &PATTERN (insn
), NO_REGS
, terminate_write
, OP_IN
, 0);
906 for (i
= 0; i
< recog_data
.n_dups
; i
++)
907 *recog_data
.dup_loc
[i
] = old_dups
[i
];
908 for (i
= 0; i
< n_ops
; i
++)
909 *recog_data
.operand_loc
[i
] = old_operands
[i
];
911 /* Step 6: Begin new chains for writes inside operands. */
912 /* ??? Many targets have output constraints on the SET_DEST
913 of a call insn, which is stupid, since these are certainly
914 ABI defined hard registers. Don't change calls at all.
915 Similarly take special care for asm statement that originally
916 referenced hard registers. */
917 if (asm_noperands (PATTERN (insn
)) > 0)
919 for (i
= 0; i
< n_ops
; i
++)
920 if (recog_data
.operand_type
[i
] == OP_OUT
)
922 rtx
*loc
= recog_data
.operand_loc
[i
];
924 enum reg_class cl
= recog_op_alt
[i
][alt
].cl
;
927 && REGNO (op
) == ORIGINAL_REGNO (op
))
930 scan_rtx (insn
, loc
, cl
, mark_write
, OP_OUT
,
931 recog_op_alt
[i
][alt
].earlyclobber
);
934 else if (!CALL_P (insn
))
935 for (i
= 0; i
< n_ops
+ recog_data
.n_dups
; i
++)
937 int opn
= i
< n_ops
? i
: recog_data
.dup_num
[i
- n_ops
];
938 rtx
*loc
= (i
< n_ops
939 ? recog_data
.operand_loc
[opn
]
940 : recog_data
.dup_loc
[i
- n_ops
]);
941 enum reg_class cl
= recog_op_alt
[opn
][alt
].cl
;
943 if (recog_data
.operand_type
[opn
] == OP_OUT
)
944 scan_rtx (insn
, loc
, cl
, mark_write
, OP_OUT
,
945 recog_op_alt
[opn
][alt
].earlyclobber
);
948 /* Step 6B: Record destination regs in REG_FRAME_RELATED_EXPR
950 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
951 if (REG_NOTE_KIND (note
) == REG_FRAME_RELATED_EXPR
)
952 scan_rtx (insn
, &XEXP (note
, 0), ALL_REGS
, mark_access
,
955 /* Step 7: Close chains for registers that were never
957 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
958 if (REG_NOTE_KIND (note
) == REG_UNUSED
)
959 scan_rtx (insn
, &XEXP (note
, 0), NO_REGS
, terminate_dead
,
962 if (insn
== BB_END (bb
))
966 /* Since we close every chain when we find a REG_DEAD note, anything that
967 is still open lives past the basic block, so it can't be renamed. */
968 return closed_chains
;
971 /* Dump all def/use chains in CHAINS to DUMP_FILE. They are
972 printed in reverse order as that's how we build them. */
975 dump_def_use_chain (struct du_chain
*chains
)
979 struct du_chain
*this_du
= chains
;
980 int r
= REGNO (*this_du
->loc
);
981 int nregs
= hard_regno_nregs
[r
][GET_MODE (*this_du
->loc
)];
982 fprintf (dump_file
, "Register %s (%d):", reg_names
[r
], nregs
);
985 fprintf (dump_file
, " %d [%s]", INSN_UID (this_du
->insn
),
986 reg_class_names
[this_du
->cl
]);
987 this_du
= this_du
->next_use
;
989 fprintf (dump_file
, "\n");
990 chains
= chains
->next_chain
;
994 /* The following code does forward propagation of hard register copies.
995 The object is to eliminate as many dependencies as possible, so that
996 we have the most scheduling freedom. As a side effect, we also clean
997 up some silly register allocation decisions made by reload. This
998 code may be obsoleted by a new register allocator. */
1000 /* For each register, we have a list of registers that contain the same
1001 value. The OLDEST_REGNO field points to the head of the list, and
1002 the NEXT_REGNO field runs through the list. The MODE field indicates
1003 what mode the data is known to be in; this field is VOIDmode when the
1004 register is not known to contain valid data. */
1006 struct value_data_entry
1008 enum machine_mode mode
;
1009 unsigned int oldest_regno
;
1010 unsigned int next_regno
;
1015 struct value_data_entry e
[FIRST_PSEUDO_REGISTER
];
1016 unsigned int max_value_regs
;
1019 static void kill_value_one_regno (unsigned, struct value_data
*);
1020 static void kill_value_regno (unsigned, unsigned, struct value_data
*);
1021 static void kill_value (rtx
, struct value_data
*);
1022 static void set_value_regno (unsigned, enum machine_mode
, struct value_data
*);
1023 static void init_value_data (struct value_data
*);
1024 static void kill_clobbered_value (rtx
, const_rtx
, void *);
1025 static void kill_set_value (rtx
, const_rtx
, void *);
1026 static int kill_autoinc_value (rtx
*, void *);
1027 static void copy_value (rtx
, rtx
, struct value_data
*);
1028 static bool mode_change_ok (enum machine_mode
, enum machine_mode
,
1030 static rtx
maybe_mode_change (enum machine_mode
, enum machine_mode
,
1031 enum machine_mode
, unsigned int, unsigned int);
1032 static rtx
find_oldest_value_reg (enum reg_class
, rtx
, struct value_data
*);
1033 static bool replace_oldest_value_reg (rtx
*, enum reg_class
, rtx
,
1034 struct value_data
*);
1035 static bool replace_oldest_value_addr (rtx
*, enum reg_class
,
1036 enum machine_mode
, rtx
,
1037 struct value_data
*);
1038 static bool replace_oldest_value_mem (rtx
, rtx
, struct value_data
*);
1039 static bool copyprop_hardreg_forward_1 (basic_block
, struct value_data
*);
1040 extern void debug_value_data (struct value_data
*);
1041 #ifdef ENABLE_CHECKING
1042 static void validate_value_data (struct value_data
*);
1045 /* Kill register REGNO. This involves removing it from any value
1046 lists, and resetting the value mode to VOIDmode. This is only a
1047 helper function; it does not handle any hard registers overlapping
1051 kill_value_one_regno (unsigned int regno
, struct value_data
*vd
)
1053 unsigned int i
, next
;
1055 if (vd
->e
[regno
].oldest_regno
!= regno
)
1057 for (i
= vd
->e
[regno
].oldest_regno
;
1058 vd
->e
[i
].next_regno
!= regno
;
1059 i
= vd
->e
[i
].next_regno
)
1061 vd
->e
[i
].next_regno
= vd
->e
[regno
].next_regno
;
1063 else if ((next
= vd
->e
[regno
].next_regno
) != INVALID_REGNUM
)
1065 for (i
= next
; i
!= INVALID_REGNUM
; i
= vd
->e
[i
].next_regno
)
1066 vd
->e
[i
].oldest_regno
= next
;
1069 vd
->e
[regno
].mode
= VOIDmode
;
1070 vd
->e
[regno
].oldest_regno
= regno
;
1071 vd
->e
[regno
].next_regno
= INVALID_REGNUM
;
1073 #ifdef ENABLE_CHECKING
1074 validate_value_data (vd
);
1078 /* Kill the value in register REGNO for NREGS, and any other registers
1079 whose values overlap. */
1082 kill_value_regno (unsigned int regno
, unsigned int nregs
,
1083 struct value_data
*vd
)
1087 /* Kill the value we're told to kill. */
1088 for (j
= 0; j
< nregs
; ++j
)
1089 kill_value_one_regno (regno
+ j
, vd
);
1091 /* Kill everything that overlapped what we're told to kill. */
1092 if (regno
< vd
->max_value_regs
)
1095 j
= regno
- vd
->max_value_regs
;
1096 for (; j
< regno
; ++j
)
1099 if (vd
->e
[j
].mode
== VOIDmode
)
1101 n
= hard_regno_nregs
[j
][vd
->e
[j
].mode
];
1103 for (i
= 0; i
< n
; ++i
)
1104 kill_value_one_regno (j
+ i
, vd
);
1108 /* Kill X. This is a convenience function wrapping kill_value_regno
1109 so that we mind the mode the register is in. */
1112 kill_value (rtx x
, struct value_data
*vd
)
1116 if (GET_CODE (x
) == SUBREG
)
1118 x
= simplify_subreg (GET_MODE (x
), SUBREG_REG (x
),
1119 GET_MODE (SUBREG_REG (x
)), SUBREG_BYTE (x
));
1121 x
= SUBREG_REG (orig_rtx
);
1125 unsigned int regno
= REGNO (x
);
1126 unsigned int n
= hard_regno_nregs
[regno
][GET_MODE (x
)];
1128 kill_value_regno (regno
, n
, vd
);
1132 /* Remember that REGNO is valid in MODE. */
1135 set_value_regno (unsigned int regno
, enum machine_mode mode
,
1136 struct value_data
*vd
)
1140 vd
->e
[regno
].mode
= mode
;
1142 nregs
= hard_regno_nregs
[regno
][mode
];
1143 if (nregs
> vd
->max_value_regs
)
1144 vd
->max_value_regs
= nregs
;
1147 /* Initialize VD such that there are no known relationships between regs. */
1150 init_value_data (struct value_data
*vd
)
1153 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1155 vd
->e
[i
].mode
= VOIDmode
;
1156 vd
->e
[i
].oldest_regno
= i
;
1157 vd
->e
[i
].next_regno
= INVALID_REGNUM
;
1159 vd
->max_value_regs
= 0;
1162 /* Called through note_stores. If X is clobbered, kill its value. */
1165 kill_clobbered_value (rtx x
, const_rtx set
, void *data
)
1167 struct value_data
*const vd
= (struct value_data
*) data
;
1168 if (GET_CODE (set
) == CLOBBER
)
1172 /* Called through note_stores. If X is set, not clobbered, kill its
1173 current value and install it as the root of its own value list. */
1176 kill_set_value (rtx x
, const_rtx set
, void *data
)
1178 struct value_data
*const vd
= (struct value_data
*) data
;
1179 if (GET_CODE (set
) != CLOBBER
)
1183 set_value_regno (REGNO (x
), GET_MODE (x
), vd
);
1187 /* Called through for_each_rtx. Kill any register used as the base of an
1188 auto-increment expression, and install that register as the root of its
1192 kill_autoinc_value (rtx
*px
, void *data
)
1195 struct value_data
*const vd
= (struct value_data
*) data
;
1197 if (GET_RTX_CLASS (GET_CODE (x
)) == RTX_AUTOINC
)
1201 set_value_regno (REGNO (x
), Pmode
, vd
);
1208 /* Assert that SRC has been copied to DEST. Adjust the data structures
1209 to reflect that SRC contains an older copy of the shared value. */
1212 copy_value (rtx dest
, rtx src
, struct value_data
*vd
)
1214 unsigned int dr
= REGNO (dest
);
1215 unsigned int sr
= REGNO (src
);
1216 unsigned int dn
, sn
;
1219 /* ??? At present, it's possible to see noop sets. It'd be nice if
1220 this were cleaned up beforehand... */
1224 /* Do not propagate copies to the stack pointer, as that can leave
1225 memory accesses with no scheduling dependency on the stack update. */
1226 if (dr
== STACK_POINTER_REGNUM
)
1229 /* Likewise with the frame pointer, if we're using one. */
1230 if (frame_pointer_needed
&& dr
== HARD_FRAME_POINTER_REGNUM
)
1233 /* Do not propagate copies to fixed or global registers, patterns
1234 can be relying to see particular fixed register or users can
1235 expect the chosen global register in asm. */
1236 if (fixed_regs
[dr
] || global_regs
[dr
])
1239 /* If SRC and DEST overlap, don't record anything. */
1240 dn
= hard_regno_nregs
[dr
][GET_MODE (dest
)];
1241 sn
= hard_regno_nregs
[sr
][GET_MODE (dest
)];
1242 if ((dr
> sr
&& dr
< sr
+ sn
)
1243 || (sr
> dr
&& sr
< dr
+ dn
))
1246 /* If SRC had no assigned mode (i.e. we didn't know it was live)
1247 assign it now and assume the value came from an input argument
1249 if (vd
->e
[sr
].mode
== VOIDmode
)
1250 set_value_regno (sr
, vd
->e
[dr
].mode
, vd
);
1252 /* If we are narrowing the input to a smaller number of hard regs,
1253 and it is in big endian, we are really extracting a high part.
1254 Since we generally associate a low part of a value with the value itself,
1255 we must not do the same for the high part.
1256 Note we can still get low parts for the same mode combination through
1257 a two-step copy involving differently sized hard regs.
1258 Assume hard regs fr* are 32 bits bits each, while r* are 64 bits each:
1259 (set (reg:DI r0) (reg:DI fr0))
1260 (set (reg:SI fr2) (reg:SI r0))
1261 loads the low part of (reg:DI fr0) - i.e. fr1 - into fr2, while:
1262 (set (reg:SI fr2) (reg:SI fr0))
1263 loads the high part of (reg:DI fr0) into fr2.
1265 We can't properly represent the latter case in our tables, so don't
1266 record anything then. */
1267 else if (sn
< (unsigned int) hard_regno_nregs
[sr
][vd
->e
[sr
].mode
]
1268 && (GET_MODE_SIZE (vd
->e
[sr
].mode
) > UNITS_PER_WORD
1269 ? WORDS_BIG_ENDIAN
: BYTES_BIG_ENDIAN
))
1272 /* If SRC had been assigned a mode narrower than the copy, we can't
1273 link DEST into the chain, because not all of the pieces of the
1274 copy came from oldest_regno. */
1275 else if (sn
> (unsigned int) hard_regno_nregs
[sr
][vd
->e
[sr
].mode
])
1278 /* Link DR at the end of the value chain used by SR. */
1280 vd
->e
[dr
].oldest_regno
= vd
->e
[sr
].oldest_regno
;
1282 for (i
= sr
; vd
->e
[i
].next_regno
!= INVALID_REGNUM
; i
= vd
->e
[i
].next_regno
)
1284 vd
->e
[i
].next_regno
= dr
;
1286 #ifdef ENABLE_CHECKING
1287 validate_value_data (vd
);
1291 /* Return true if a mode change from ORIG to NEW is allowed for REGNO. */
1294 mode_change_ok (enum machine_mode orig_mode
, enum machine_mode new_mode
,
1295 unsigned int regno ATTRIBUTE_UNUSED
)
1297 if (GET_MODE_SIZE (orig_mode
) < GET_MODE_SIZE (new_mode
))
1300 #ifdef CANNOT_CHANGE_MODE_CLASS
1301 return !REG_CANNOT_CHANGE_MODE_P (regno
, orig_mode
, new_mode
);
1307 /* Register REGNO was originally set in ORIG_MODE. It - or a copy of it -
1308 was copied in COPY_MODE to COPY_REGNO, and then COPY_REGNO was accessed
1310 Return a NEW_MODE rtx for REGNO if that's OK, otherwise return NULL_RTX. */
1313 maybe_mode_change (enum machine_mode orig_mode
, enum machine_mode copy_mode
,
1314 enum machine_mode new_mode
, unsigned int regno
,
1315 unsigned int copy_regno ATTRIBUTE_UNUSED
)
1317 if (GET_MODE_SIZE (copy_mode
) < GET_MODE_SIZE (orig_mode
)
1318 && GET_MODE_SIZE (copy_mode
) < GET_MODE_SIZE (new_mode
))
1321 if (orig_mode
== new_mode
)
1322 return gen_rtx_raw_REG (new_mode
, regno
);
1323 else if (mode_change_ok (orig_mode
, new_mode
, regno
))
1325 int copy_nregs
= hard_regno_nregs
[copy_regno
][copy_mode
];
1326 int use_nregs
= hard_regno_nregs
[copy_regno
][new_mode
];
1328 = GET_MODE_SIZE (copy_mode
) / copy_nregs
* (copy_nregs
- use_nregs
);
1330 = GET_MODE_SIZE (orig_mode
) - GET_MODE_SIZE (new_mode
) - copy_offset
;
1331 int byteoffset
= offset
% UNITS_PER_WORD
;
1332 int wordoffset
= offset
- byteoffset
;
1334 offset
= ((WORDS_BIG_ENDIAN
? wordoffset
: 0)
1335 + (BYTES_BIG_ENDIAN
? byteoffset
: 0));
1336 return gen_rtx_raw_REG (new_mode
,
1337 regno
+ subreg_regno_offset (regno
, orig_mode
,
1344 /* Find the oldest copy of the value contained in REGNO that is in
1345 register class CL and has mode MODE. If found, return an rtx
1346 of that oldest register, otherwise return NULL. */
1349 find_oldest_value_reg (enum reg_class cl
, rtx reg
, struct value_data
*vd
)
1351 unsigned int regno
= REGNO (reg
);
1352 enum machine_mode mode
= GET_MODE (reg
);
1355 /* If we are accessing REG in some mode other that what we set it in,
1356 make sure that the replacement is valid. In particular, consider
1357 (set (reg:DI r11) (...))
1358 (set (reg:SI r9) (reg:SI r11))
1359 (set (reg:SI r10) (...))
1360 (set (...) (reg:DI r9))
1361 Replacing r9 with r11 is invalid. */
1362 if (mode
!= vd
->e
[regno
].mode
)
1364 if (hard_regno_nregs
[regno
][mode
]
1365 > hard_regno_nregs
[regno
][vd
->e
[regno
].mode
])
1369 for (i
= vd
->e
[regno
].oldest_regno
; i
!= regno
; i
= vd
->e
[i
].next_regno
)
1371 enum machine_mode oldmode
= vd
->e
[i
].mode
;
1374 if (!in_hard_reg_set_p (reg_class_contents
[cl
], mode
, i
))
1377 new_rtx
= maybe_mode_change (oldmode
, vd
->e
[regno
].mode
, mode
, i
, regno
);
1380 ORIGINAL_REGNO (new_rtx
) = ORIGINAL_REGNO (reg
);
1381 REG_ATTRS (new_rtx
) = REG_ATTRS (reg
);
1389 /* If possible, replace the register at *LOC with the oldest register
1390 in register class CL. Return true if successfully replaced. */
1393 replace_oldest_value_reg (rtx
*loc
, enum reg_class cl
, rtx insn
,
1394 struct value_data
*vd
)
1396 rtx new_rtx
= find_oldest_value_reg (cl
, *loc
, vd
);
1400 fprintf (dump_file
, "insn %u: replaced reg %u with %u\n",
1401 INSN_UID (insn
), REGNO (*loc
), REGNO (new_rtx
));
1403 validate_change (insn
, loc
, new_rtx
, 1);
1409 /* Similar to replace_oldest_value_reg, but *LOC contains an address.
1410 Adapted from find_reloads_address_1. CL is INDEX_REG_CLASS or
1411 BASE_REG_CLASS depending on how the register is being considered. */
1414 replace_oldest_value_addr (rtx
*loc
, enum reg_class cl
,
1415 enum machine_mode mode
, rtx insn
,
1416 struct value_data
*vd
)
1419 RTX_CODE code
= GET_CODE (x
);
1422 bool changed
= false;
1428 rtx orig_op0
= XEXP (x
, 0);
1429 rtx orig_op1
= XEXP (x
, 1);
1430 RTX_CODE code0
= GET_CODE (orig_op0
);
1431 RTX_CODE code1
= GET_CODE (orig_op1
);
1436 enum rtx_code index_code
= SCRATCH
;
1438 if (GET_CODE (op0
) == SUBREG
)
1440 op0
= SUBREG_REG (op0
);
1441 code0
= GET_CODE (op0
);
1444 if (GET_CODE (op1
) == SUBREG
)
1446 op1
= SUBREG_REG (op1
);
1447 code1
= GET_CODE (op1
);
1450 if (code0
== MULT
|| code0
== SIGN_EXTEND
|| code0
== TRUNCATE
1451 || code0
== ZERO_EXTEND
|| code1
== MEM
)
1453 locI
= &XEXP (x
, 0);
1454 locB
= &XEXP (x
, 1);
1455 index_code
= GET_CODE (*locI
);
1457 else if (code1
== MULT
|| code1
== SIGN_EXTEND
|| code1
== TRUNCATE
1458 || code1
== ZERO_EXTEND
|| code0
== MEM
)
1460 locI
= &XEXP (x
, 1);
1461 locB
= &XEXP (x
, 0);
1462 index_code
= GET_CODE (*locI
);
1464 else if (code0
== CONST_INT
|| code0
== CONST
1465 || code0
== SYMBOL_REF
|| code0
== LABEL_REF
)
1467 locB
= &XEXP (x
, 1);
1468 index_code
= GET_CODE (XEXP (x
, 0));
1470 else if (code1
== CONST_INT
|| code1
== CONST
1471 || code1
== SYMBOL_REF
|| code1
== LABEL_REF
)
1473 locB
= &XEXP (x
, 0);
1474 index_code
= GET_CODE (XEXP (x
, 1));
1476 else if (code0
== REG
&& code1
== REG
)
1479 unsigned regno0
= REGNO (op0
), regno1
= REGNO (op1
);
1481 if (REGNO_OK_FOR_INDEX_P (regno1
)
1482 && regno_ok_for_base_p (regno0
, mode
, PLUS
, REG
))
1484 else if (REGNO_OK_FOR_INDEX_P (regno0
)
1485 && regno_ok_for_base_p (regno1
, mode
, PLUS
, REG
))
1487 else if (regno_ok_for_base_p (regno0
, mode
, PLUS
, REG
)
1488 || REGNO_OK_FOR_INDEX_P (regno1
))
1490 else if (regno_ok_for_base_p (regno1
, mode
, PLUS
, REG
))
1495 locI
= &XEXP (x
, index_op
);
1496 locB
= &XEXP (x
, !index_op
);
1497 index_code
= GET_CODE (*locI
);
1499 else if (code0
== REG
)
1501 locI
= &XEXP (x
, 0);
1502 locB
= &XEXP (x
, 1);
1503 index_code
= GET_CODE (*locI
);
1505 else if (code1
== REG
)
1507 locI
= &XEXP (x
, 1);
1508 locB
= &XEXP (x
, 0);
1509 index_code
= GET_CODE (*locI
);
1513 changed
|= replace_oldest_value_addr (locI
, INDEX_REG_CLASS
, mode
,
1516 changed
|= replace_oldest_value_addr (locB
,
1517 base_reg_class (mode
, PLUS
,
1532 return replace_oldest_value_mem (x
, insn
, vd
);
1535 return replace_oldest_value_reg (loc
, cl
, insn
, vd
);
1541 fmt
= GET_RTX_FORMAT (code
);
1542 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1545 changed
|= replace_oldest_value_addr (&XEXP (x
, i
), cl
, mode
,
1547 else if (fmt
[i
] == 'E')
1548 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
1549 changed
|= replace_oldest_value_addr (&XVECEXP (x
, i
, j
), cl
,
1556 /* Similar to replace_oldest_value_reg, but X contains a memory. */
1559 replace_oldest_value_mem (rtx x
, rtx insn
, struct value_data
*vd
)
1561 return replace_oldest_value_addr (&XEXP (x
, 0),
1562 base_reg_class (GET_MODE (x
), MEM
,
1564 GET_MODE (x
), insn
, vd
);
1567 /* Perform the forward copy propagation on basic block BB. */
1570 copyprop_hardreg_forward_1 (basic_block bb
, struct value_data
*vd
)
1572 bool changed
= false;
1575 for (insn
= BB_HEAD (bb
); ; insn
= NEXT_INSN (insn
))
1577 int n_ops
, i
, alt
, predicated
;
1578 bool is_asm
, any_replacements
;
1580 bool replaced
[MAX_RECOG_OPERANDS
];
1582 if (! INSN_P (insn
))
1584 if (insn
== BB_END (bb
))
1590 set
= single_set (insn
);
1591 extract_insn (insn
);
1592 if (! constrain_operands (1))
1593 fatal_insn_not_found (insn
);
1594 preprocess_constraints ();
1595 alt
= which_alternative
;
1596 n_ops
= recog_data
.n_operands
;
1597 is_asm
= asm_noperands (PATTERN (insn
)) >= 0;
1599 /* Simplify the code below by rewriting things to reflect
1600 matching constraints. Also promote OP_OUT to OP_INOUT
1601 in predicated instructions. */
1603 predicated
= GET_CODE (PATTERN (insn
)) == COND_EXEC
;
1604 for (i
= 0; i
< n_ops
; ++i
)
1606 int matches
= recog_op_alt
[i
][alt
].matches
;
1608 recog_op_alt
[i
][alt
].cl
= recog_op_alt
[matches
][alt
].cl
;
1609 if (matches
>= 0 || recog_op_alt
[i
][alt
].matched
>= 0
1610 || (predicated
&& recog_data
.operand_type
[i
] == OP_OUT
))
1611 recog_data
.operand_type
[i
] = OP_INOUT
;
1614 /* For each earlyclobber operand, zap the value data. */
1615 for (i
= 0; i
< n_ops
; i
++)
1616 if (recog_op_alt
[i
][alt
].earlyclobber
)
1617 kill_value (recog_data
.operand
[i
], vd
);
1619 /* Within asms, a clobber cannot overlap inputs or outputs.
1620 I wouldn't think this were true for regular insns, but
1621 scan_rtx treats them like that... */
1622 note_stores (PATTERN (insn
), kill_clobbered_value
, vd
);
1624 /* Kill all auto-incremented values. */
1625 /* ??? REG_INC is useless, since stack pushes aren't done that way. */
1626 for_each_rtx (&PATTERN (insn
), kill_autoinc_value
, vd
);
1628 /* Kill all early-clobbered operands. */
1629 for (i
= 0; i
< n_ops
; i
++)
1630 if (recog_op_alt
[i
][alt
].earlyclobber
)
1631 kill_value (recog_data
.operand
[i
], vd
);
1633 /* Special-case plain move instructions, since we may well
1634 be able to do the move from a different register class. */
1635 if (set
&& REG_P (SET_SRC (set
)))
1637 rtx src
= SET_SRC (set
);
1638 unsigned int regno
= REGNO (src
);
1639 enum machine_mode mode
= GET_MODE (src
);
1643 /* If we are accessing SRC in some mode other that what we
1644 set it in, make sure that the replacement is valid. */
1645 if (mode
!= vd
->e
[regno
].mode
)
1647 if (hard_regno_nregs
[regno
][mode
]
1648 > hard_regno_nregs
[regno
][vd
->e
[regno
].mode
])
1649 goto no_move_special_case
;
1652 /* If the destination is also a register, try to find a source
1653 register in the same class. */
1654 if (REG_P (SET_DEST (set
)))
1656 new_rtx
= find_oldest_value_reg (REGNO_REG_CLASS (regno
), src
, vd
);
1657 if (new_rtx
&& validate_change (insn
, &SET_SRC (set
), new_rtx
, 0))
1661 "insn %u: replaced reg %u with %u\n",
1662 INSN_UID (insn
), regno
, REGNO (new_rtx
));
1664 goto did_replacement
;
1668 /* Otherwise, try all valid registers and see if its valid. */
1669 for (i
= vd
->e
[regno
].oldest_regno
; i
!= regno
;
1670 i
= vd
->e
[i
].next_regno
)
1672 new_rtx
= maybe_mode_change (vd
->e
[i
].mode
, vd
->e
[regno
].mode
,
1674 if (new_rtx
!= NULL_RTX
)
1676 if (validate_change (insn
, &SET_SRC (set
), new_rtx
, 0))
1678 ORIGINAL_REGNO (new_rtx
) = ORIGINAL_REGNO (src
);
1679 REG_ATTRS (new_rtx
) = REG_ATTRS (src
);
1682 "insn %u: replaced reg %u with %u\n",
1683 INSN_UID (insn
), regno
, REGNO (new_rtx
));
1685 goto did_replacement
;
1690 no_move_special_case
:
1692 any_replacements
= false;
1694 /* For each input operand, replace a hard register with the
1695 eldest live copy that's in an appropriate register class. */
1696 for (i
= 0; i
< n_ops
; i
++)
1698 replaced
[i
] = false;
1700 /* Don't scan match_operand here, since we've no reg class
1701 information to pass down. Any operands that we could
1702 substitute in will be represented elsewhere. */
1703 if (recog_data
.constraints
[i
][0] == '\0')
1706 /* Don't replace in asms intentionally referencing hard regs. */
1707 if (is_asm
&& REG_P (recog_data
.operand
[i
])
1708 && (REGNO (recog_data
.operand
[i
])
1709 == ORIGINAL_REGNO (recog_data
.operand
[i
])))
1712 if (recog_data
.operand_type
[i
] == OP_IN
)
1714 if (recog_op_alt
[i
][alt
].is_address
)
1716 = replace_oldest_value_addr (recog_data
.operand_loc
[i
],
1717 recog_op_alt
[i
][alt
].cl
,
1718 VOIDmode
, insn
, vd
);
1719 else if (REG_P (recog_data
.operand
[i
]))
1721 = replace_oldest_value_reg (recog_data
.operand_loc
[i
],
1722 recog_op_alt
[i
][alt
].cl
,
1724 else if (MEM_P (recog_data
.operand
[i
]))
1725 replaced
[i
] = replace_oldest_value_mem (recog_data
.operand
[i
],
1728 else if (MEM_P (recog_data
.operand
[i
]))
1729 replaced
[i
] = replace_oldest_value_mem (recog_data
.operand
[i
],
1732 /* If we performed any replacement, update match_dups. */
1738 new_rtx
= *recog_data
.operand_loc
[i
];
1739 recog_data
.operand
[i
] = new_rtx
;
1740 for (j
= 0; j
< recog_data
.n_dups
; j
++)
1741 if (recog_data
.dup_num
[j
] == i
)
1742 validate_unshare_change (insn
, recog_data
.dup_loc
[j
], new_rtx
, 1);
1744 any_replacements
= true;
1748 if (any_replacements
)
1750 if (! apply_change_group ())
1752 for (i
= 0; i
< n_ops
; i
++)
1755 rtx old
= *recog_data
.operand_loc
[i
];
1756 recog_data
.operand
[i
] = old
;
1761 "insn %u: reg replacements not verified\n",
1769 /* Clobber call-clobbered registers. */
1771 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1772 if (TEST_HARD_REG_BIT (regs_invalidated_by_call
, i
))
1773 kill_value_regno (i
, 1, vd
);
1775 /* Notice stores. */
1776 note_stores (PATTERN (insn
), kill_set_value
, vd
);
1778 /* Notice copies. */
1779 if (set
&& REG_P (SET_DEST (set
)) && REG_P (SET_SRC (set
)))
1780 copy_value (SET_DEST (set
), SET_SRC (set
), vd
);
1782 if (insn
== BB_END (bb
))
1789 /* Main entry point for the forward copy propagation optimization. */
1792 copyprop_hardreg_forward (void)
1794 struct value_data
*all_vd
;
1798 all_vd
= XNEWVEC (struct value_data
, last_basic_block
);
1800 visited
= sbitmap_alloc (last_basic_block
);
1801 sbitmap_zero (visited
);
1805 SET_BIT (visited
, bb
->index
);
1807 /* If a block has a single predecessor, that we've already
1808 processed, begin with the value data that was live at
1809 the end of the predecessor block. */
1810 /* ??? Ought to use more intelligent queuing of blocks. */
1811 if (single_pred_p (bb
)
1812 && TEST_BIT (visited
, single_pred (bb
)->index
)
1813 && ! (single_pred_edge (bb
)->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
)))
1814 all_vd
[bb
->index
] = all_vd
[single_pred (bb
)->index
];
1816 init_value_data (all_vd
+ bb
->index
);
1818 copyprop_hardreg_forward_1 (bb
, all_vd
+ bb
->index
);
1821 sbitmap_free (visited
);
1825 /* Dump the value chain data to stderr. */
1828 debug_value_data (struct value_data
*vd
)
1833 CLEAR_HARD_REG_SET (set
);
1835 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1836 if (vd
->e
[i
].oldest_regno
== i
)
1838 if (vd
->e
[i
].mode
== VOIDmode
)
1840 if (vd
->e
[i
].next_regno
!= INVALID_REGNUM
)
1841 fprintf (stderr
, "[%u] Bad next_regno for empty chain (%u)\n",
1842 i
, vd
->e
[i
].next_regno
);
1846 SET_HARD_REG_BIT (set
, i
);
1847 fprintf (stderr
, "[%u %s] ", i
, GET_MODE_NAME (vd
->e
[i
].mode
));
1849 for (j
= vd
->e
[i
].next_regno
;
1850 j
!= INVALID_REGNUM
;
1851 j
= vd
->e
[j
].next_regno
)
1853 if (TEST_HARD_REG_BIT (set
, j
))
1855 fprintf (stderr
, "[%u] Loop in regno chain\n", j
);
1859 if (vd
->e
[j
].oldest_regno
!= i
)
1861 fprintf (stderr
, "[%u] Bad oldest_regno (%u)\n",
1862 j
, vd
->e
[j
].oldest_regno
);
1865 SET_HARD_REG_BIT (set
, j
);
1866 fprintf (stderr
, "[%u %s] ", j
, GET_MODE_NAME (vd
->e
[j
].mode
));
1868 fputc ('\n', stderr
);
1871 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1872 if (! TEST_HARD_REG_BIT (set
, i
)
1873 && (vd
->e
[i
].mode
!= VOIDmode
1874 || vd
->e
[i
].oldest_regno
!= i
1875 || vd
->e
[i
].next_regno
!= INVALID_REGNUM
))
1876 fprintf (stderr
, "[%u] Non-empty reg in chain (%s %u %i)\n",
1877 i
, GET_MODE_NAME (vd
->e
[i
].mode
), vd
->e
[i
].oldest_regno
,
1878 vd
->e
[i
].next_regno
);
1881 #ifdef ENABLE_CHECKING
1883 validate_value_data (struct value_data
*vd
)
1888 CLEAR_HARD_REG_SET (set
);
1890 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1891 if (vd
->e
[i
].oldest_regno
== i
)
1893 if (vd
->e
[i
].mode
== VOIDmode
)
1895 if (vd
->e
[i
].next_regno
!= INVALID_REGNUM
)
1896 internal_error ("validate_value_data: [%u] Bad next_regno for empty chain (%u)",
1897 i
, vd
->e
[i
].next_regno
);
1901 SET_HARD_REG_BIT (set
, i
);
1903 for (j
= vd
->e
[i
].next_regno
;
1904 j
!= INVALID_REGNUM
;
1905 j
= vd
->e
[j
].next_regno
)
1907 if (TEST_HARD_REG_BIT (set
, j
))
1908 internal_error ("validate_value_data: Loop in regno chain (%u)",
1910 if (vd
->e
[j
].oldest_regno
!= i
)
1911 internal_error ("validate_value_data: [%u] Bad oldest_regno (%u)",
1912 j
, vd
->e
[j
].oldest_regno
);
1914 SET_HARD_REG_BIT (set
, j
);
1918 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1919 if (! TEST_HARD_REG_BIT (set
, i
)
1920 && (vd
->e
[i
].mode
!= VOIDmode
1921 || vd
->e
[i
].oldest_regno
!= i
1922 || vd
->e
[i
].next_regno
!= INVALID_REGNUM
))
1923 internal_error ("validate_value_data: [%u] Non-empty reg in chain (%s %u %i)",
1924 i
, GET_MODE_NAME (vd
->e
[i
].mode
), vd
->e
[i
].oldest_regno
,
1925 vd
->e
[i
].next_regno
);
1930 gate_handle_regrename (void)
1932 return (optimize
> 0 && (flag_rename_registers
));
1936 /* Run the regrename and cprop passes. */
1938 rest_of_handle_regrename (void)
1940 regrename_optimize ();
1944 struct rtl_opt_pass pass_regrename
=
1949 gate_handle_regrename
, /* gate */
1950 rest_of_handle_regrename
, /* execute */
1953 0, /* static_pass_number */
1954 TV_RENAME_REGISTERS
, /* tv_id */
1955 0, /* properties_required */
1956 0, /* properties_provided */
1957 0, /* properties_destroyed */
1958 0, /* todo_flags_start */
1959 TODO_df_finish
| TODO_verify_rtl_sharing
|
1960 TODO_dump_func
/* todo_flags_finish */
1965 gate_handle_cprop (void)
1967 return (optimize
> 0 && (flag_cprop_registers
));
1971 /* Run the regrename and cprop passes. */
1973 rest_of_handle_cprop (void)
1975 copyprop_hardreg_forward ();
1979 struct rtl_opt_pass pass_cprop_hardreg
=
1983 "cprop_hardreg", /* name */
1984 gate_handle_cprop
, /* gate */
1985 rest_of_handle_cprop
, /* execute */
1988 0, /* static_pass_number */
1989 TV_RENAME_REGISTERS
, /* tv_id */
1990 0, /* properties_required */
1991 0, /* properties_provided */
1992 0, /* properties_destroyed */
1993 0, /* todo_flags_start */
1994 TODO_dump_func
| TODO_verify_rtl_sharing
/* todo_flags_finish */