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 machine_mode
, 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 machine_mode 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
= obstack_alloc (&rename_obstack
, 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 = all_chains
;
226 struct du_chain
*tmp
, *last
;
227 HARD_REG_SET this_unavailable
;
228 int reg
= REGNO (*this->loc
);
231 all_chains
= this->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; 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->need_caller_save_reg
)
272 IOR_HARD_REG_SET (this_unavailable
, call_used_reg_set
);
274 merge_overlapping_regs (bb
, &this_unavailable
, this);
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->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; 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, 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
389 = obstack_alloc (&rename_obstack
, sizeof (struct du_chain
));
391 this->next_chain
= open_chains
;
395 this->need_caller_save_reg
= 0;
396 this->earlyclobber
= earlyclobber
;
402 if ((type
== OP_OUT
) != (action
== terminate_write
|| action
== mark_access
))
405 for (p
= &open_chains
; *p
;)
407 struct du_chain
*this = *p
;
409 /* Check if the chain has been terminated if it has then skip to
412 This can happen when we've already appended the location to
413 the chain in Step 3, but are trying to hide in-out operands
414 from terminate_write in Step 5. */
416 if (*this->loc
== cc0_rtx
)
417 p
= &this->next_chain
;
420 int regno
= REGNO (*this->loc
);
421 int nregs
= hard_regno_nregs
[regno
][GET_MODE (*this->loc
)];
422 int exact_match
= (regno
== this_regno
&& nregs
== this_nregs
);
424 if (regno
+ nregs
<= this_regno
425 || this_regno
+ this_nregs
<= regno
)
427 p
= &this->next_chain
;
431 if (action
== mark_read
|| action
== mark_access
)
433 gcc_assert (exact_match
);
435 /* ??? Class NO_REGS can happen if the md file makes use of
436 EXTRA_CONSTRAINTS to match registers. Which is arguably
437 wrong, but there we are. Since we know not what this may
438 be replaced with, terminate the chain. */
441 this = obstack_alloc (&rename_obstack
, sizeof (struct du_chain
));
443 this->next_chain
= (*p
)->next_chain
;
447 this->need_caller_save_reg
= 0;
455 if (action
!= terminate_overlapping_read
|| ! exact_match
)
457 struct du_chain
*next
= this->next_chain
;
459 /* Whether the terminated chain can be used for renaming
460 depends on the action and this being an exact match.
461 In either case, we remove this element from open_chains. */
463 if ((action
== terminate_dead
|| action
== terminate_write
)
466 this->next_chain
= closed_chains
;
467 closed_chains
= this;
470 "Closing chain %s at insn %d (%s)\n",
471 reg_names
[REGNO (*this->loc
)], INSN_UID (insn
),
472 scan_actions_name
[(int) action
]);
478 "Discarding chain %s at insn %d (%s)\n",
479 reg_names
[REGNO (*this->loc
)], INSN_UID (insn
),
480 scan_actions_name
[(int) action
]);
485 p
= &this->next_chain
;
490 /* Adapted from find_reloads_address_1. CL is INDEX_REG_CLASS or
491 BASE_REG_CLASS depending on how the register is being considered. */
494 scan_rtx_address (rtx insn
, rtx
*loc
, enum reg_class cl
,
495 enum scan_actions action
, enum machine_mode mode
)
498 RTX_CODE code
= GET_CODE (x
);
502 if (action
== mark_write
|| action
== mark_access
)
509 rtx orig_op0
= XEXP (x
, 0);
510 rtx orig_op1
= XEXP (x
, 1);
511 RTX_CODE code0
= GET_CODE (orig_op0
);
512 RTX_CODE code1
= GET_CODE (orig_op1
);
517 enum rtx_code index_code
= SCRATCH
;
519 if (GET_CODE (op0
) == SUBREG
)
521 op0
= SUBREG_REG (op0
);
522 code0
= GET_CODE (op0
);
525 if (GET_CODE (op1
) == SUBREG
)
527 op1
= SUBREG_REG (op1
);
528 code1
= GET_CODE (op1
);
531 if (code0
== MULT
|| code0
== SIGN_EXTEND
|| code0
== TRUNCATE
532 || code0
== ZERO_EXTEND
|| code1
== MEM
)
536 index_code
= GET_CODE (*locI
);
538 else if (code1
== MULT
|| code1
== SIGN_EXTEND
|| code1
== TRUNCATE
539 || code1
== ZERO_EXTEND
|| code0
== MEM
)
543 index_code
= GET_CODE (*locI
);
545 else if (code0
== CONST_INT
|| code0
== CONST
546 || code0
== SYMBOL_REF
|| code0
== LABEL_REF
)
549 index_code
= GET_CODE (XEXP (x
, 0));
551 else if (code1
== CONST_INT
|| code1
== CONST
552 || code1
== SYMBOL_REF
|| code1
== LABEL_REF
)
555 index_code
= GET_CODE (XEXP (x
, 1));
557 else if (code0
== REG
&& code1
== REG
)
560 unsigned regno0
= REGNO (op0
), regno1
= REGNO (op1
);
562 if (REGNO_OK_FOR_INDEX_P (regno0
)
563 && regno_ok_for_base_p (regno1
, mode
, PLUS
, REG
))
565 else if (REGNO_OK_FOR_INDEX_P (regno1
)
566 && regno_ok_for_base_p (regno0
, mode
, PLUS
, REG
))
568 else if (regno_ok_for_base_p (regno1
, mode
, PLUS
, REG
))
570 else if (regno_ok_for_base_p (regno0
, mode
, PLUS
, REG
))
572 else if (REGNO_OK_FOR_INDEX_P (regno1
))
577 locI
= &XEXP (x
, index_op
);
578 locB
= &XEXP (x
, !index_op
);
579 index_code
= GET_CODE (*locI
);
581 else if (code0
== REG
)
585 index_code
= GET_CODE (*locI
);
587 else if (code1
== REG
)
591 index_code
= GET_CODE (*locI
);
595 scan_rtx_address (insn
, locI
, INDEX_REG_CLASS
, action
, mode
);
597 scan_rtx_address (insn
, locB
, base_reg_class (mode
, PLUS
, index_code
),
610 /* If the target doesn't claim to handle autoinc, this must be
611 something special, like a stack push. Kill this chain. */
612 action
= terminate_all_read
;
617 scan_rtx_address (insn
, &XEXP (x
, 0),
618 base_reg_class (GET_MODE (x
), MEM
, SCRATCH
), action
,
623 scan_rtx_reg (insn
, loc
, cl
, action
, OP_IN
, 0);
630 fmt
= GET_RTX_FORMAT (code
);
631 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
634 scan_rtx_address (insn
, &XEXP (x
, i
), cl
, action
, mode
);
635 else if (fmt
[i
] == 'E')
636 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
637 scan_rtx_address (insn
, &XVECEXP (x
, i
, j
), cl
, action
, mode
);
642 scan_rtx (rtx insn
, rtx
*loc
, enum reg_class cl
,
643 enum scan_actions action
, enum op_type type
, int earlyclobber
)
647 enum rtx_code code
= GET_CODE (x
);
665 scan_rtx_reg (insn
, loc
, cl
, action
, type
, earlyclobber
);
669 scan_rtx_address (insn
, &XEXP (x
, 0),
670 base_reg_class (GET_MODE (x
), MEM
, SCRATCH
), action
,
675 scan_rtx (insn
, &SET_SRC (x
), cl
, action
, OP_IN
, 0);
676 scan_rtx (insn
, &SET_DEST (x
), cl
, action
,
677 GET_CODE (PATTERN (insn
)) == COND_EXEC
? OP_INOUT
: OP_OUT
, 0);
680 case STRICT_LOW_PART
:
681 scan_rtx (insn
, &XEXP (x
, 0), cl
, action
, OP_INOUT
, earlyclobber
);
686 scan_rtx (insn
, &XEXP (x
, 0), cl
, action
,
687 type
== OP_IN
? OP_IN
: OP_INOUT
, earlyclobber
);
688 scan_rtx (insn
, &XEXP (x
, 1), cl
, action
, OP_IN
, 0);
689 scan_rtx (insn
, &XEXP (x
, 2), cl
, action
, OP_IN
, 0);
698 /* Should only happen inside MEM. */
702 scan_rtx (insn
, &SET_DEST (x
), cl
, action
,
703 GET_CODE (PATTERN (insn
)) == COND_EXEC
? OP_INOUT
: OP_OUT
, 0);
707 scan_rtx (insn
, &XEXP (x
, 0), cl
, action
, type
, 0);
709 scan_rtx (insn
, &XEXP (x
, 1), cl
, action
, type
, 0);
716 fmt
= GET_RTX_FORMAT (code
);
717 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
720 scan_rtx (insn
, &XEXP (x
, i
), cl
, action
, type
, 0);
721 else if (fmt
[i
] == 'E')
722 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
723 scan_rtx (insn
, &XVECEXP (x
, i
, j
), cl
, action
, type
, 0);
727 /* Build def/use chain. */
729 static struct du_chain
*
730 build_def_use (basic_block bb
)
734 open_chains
= closed_chains
= NULL
;
736 for (insn
= BB_HEAD (bb
); ; insn
= NEXT_INSN (insn
))
742 rtx old_operands
[MAX_RECOG_OPERANDS
];
743 rtx old_dups
[MAX_DUP_OPERANDS
];
748 /* Process the insn, determining its effect on the def-use
749 chains. We perform the following steps with the register
750 references in the insn:
751 (1) Any read that overlaps an open chain, but doesn't exactly
752 match, causes that chain to be closed. We can't deal
754 (2) Any read outside an operand causes any chain it overlaps
755 with to be closed, since we can't replace it.
756 (3) Any read inside an operand is added if there's already
757 an open chain for it.
758 (4) For any REG_DEAD note we find, close open chains that
760 (5) For any write we find, close open chains that overlap it.
761 (6) For any write we find in an operand, make a new chain.
762 (7) For any REG_UNUSED, close any chains we just opened. */
764 icode
= recog_memoized (insn
);
766 if (! constrain_operands (1))
767 fatal_insn_not_found (insn
);
768 preprocess_constraints ();
769 alt
= which_alternative
;
770 n_ops
= recog_data
.n_operands
;
772 /* Simplify the code below by rewriting things to reflect
773 matching constraints. Also promote OP_OUT to OP_INOUT
774 in predicated instructions. */
776 predicated
= GET_CODE (PATTERN (insn
)) == COND_EXEC
;
777 for (i
= 0; i
< n_ops
; ++i
)
779 int matches
= recog_op_alt
[i
][alt
].matches
;
781 recog_op_alt
[i
][alt
].cl
= recog_op_alt
[matches
][alt
].cl
;
782 if (matches
>= 0 || recog_op_alt
[i
][alt
].matched
>= 0
783 || (predicated
&& recog_data
.operand_type
[i
] == OP_OUT
))
784 recog_data
.operand_type
[i
] = OP_INOUT
;
787 /* Step 1: Close chains for which we have overlapping reads. */
788 for (i
= 0; i
< n_ops
; i
++)
789 scan_rtx (insn
, recog_data
.operand_loc
[i
],
790 NO_REGS
, terminate_overlapping_read
,
791 recog_data
.operand_type
[i
], 0);
793 /* Step 2: Close chains for which we have reads outside operands.
794 We do this by munging all operands into CC0, and closing
795 everything remaining. */
797 for (i
= 0; i
< n_ops
; i
++)
799 old_operands
[i
] = recog_data
.operand
[i
];
800 /* Don't squash match_operator or match_parallel here, since
801 we don't know that all of the contained registers are
802 reachable by proper operands. */
803 if (recog_data
.constraints
[i
][0] == '\0')
805 *recog_data
.operand_loc
[i
] = cc0_rtx
;
807 for (i
= 0; i
< recog_data
.n_dups
; i
++)
809 old_dups
[i
] = *recog_data
.dup_loc
[i
];
810 *recog_data
.dup_loc
[i
] = cc0_rtx
;
813 scan_rtx (insn
, &PATTERN (insn
), NO_REGS
, terminate_all_read
,
816 for (i
= 0; i
< recog_data
.n_dups
; i
++)
817 *recog_data
.dup_loc
[i
] = copy_rtx (old_dups
[i
]);
818 for (i
= 0; i
< n_ops
; i
++)
819 *recog_data
.operand_loc
[i
] = old_operands
[i
];
820 if (recog_data
.n_dups
)
821 df_insn_rescan (insn
);
823 /* Step 2B: Can't rename function call argument registers. */
824 if (CALL_P (insn
) && CALL_INSN_FUNCTION_USAGE (insn
))
825 scan_rtx (insn
, &CALL_INSN_FUNCTION_USAGE (insn
),
826 NO_REGS
, terminate_all_read
, OP_IN
, 0);
828 /* Step 2C: Can't rename asm operands that were originally
830 if (asm_noperands (PATTERN (insn
)) > 0)
831 for (i
= 0; i
< n_ops
; i
++)
833 rtx
*loc
= recog_data
.operand_loc
[i
];
837 && REGNO (op
) == ORIGINAL_REGNO (op
)
838 && (recog_data
.operand_type
[i
] == OP_IN
839 || recog_data
.operand_type
[i
] == OP_INOUT
))
840 scan_rtx (insn
, loc
, NO_REGS
, terminate_all_read
, OP_IN
, 0);
843 /* Step 3: Append to chains for reads inside operands. */
844 for (i
= 0; i
< n_ops
+ recog_data
.n_dups
; i
++)
846 int opn
= i
< n_ops
? i
: recog_data
.dup_num
[i
- n_ops
];
847 rtx
*loc
= (i
< n_ops
848 ? recog_data
.operand_loc
[opn
]
849 : recog_data
.dup_loc
[i
- n_ops
]);
850 enum reg_class cl
= recog_op_alt
[opn
][alt
].cl
;
851 enum op_type type
= recog_data
.operand_type
[opn
];
853 /* Don't scan match_operand here, since we've no reg class
854 information to pass down. Any operands that we could
855 substitute in will be represented elsewhere. */
856 if (recog_data
.constraints
[opn
][0] == '\0')
859 if (recog_op_alt
[opn
][alt
].is_address
)
860 scan_rtx_address (insn
, loc
, cl
, mark_read
, VOIDmode
);
862 scan_rtx (insn
, loc
, cl
, mark_read
, type
, 0);
865 /* Step 3B: Record updates for regs in REG_INC notes, and
866 source regs in REG_FRAME_RELATED_EXPR notes. */
867 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
868 if (REG_NOTE_KIND (note
) == REG_INC
869 || REG_NOTE_KIND (note
) == REG_FRAME_RELATED_EXPR
)
870 scan_rtx (insn
, &XEXP (note
, 0), ALL_REGS
, mark_read
,
873 /* Step 4: Close chains for registers that die here. */
874 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
875 if (REG_NOTE_KIND (note
) == REG_DEAD
)
876 scan_rtx (insn
, &XEXP (note
, 0), NO_REGS
, terminate_dead
,
879 /* Step 4B: If this is a call, any chain live at this point
880 requires a caller-saved reg. */
884 for (p
= open_chains
; p
; p
= p
->next_chain
)
885 p
->need_caller_save_reg
= 1;
888 /* Step 5: Close open chains that overlap writes. Similar to
889 step 2, we hide in-out operands, since we do not want to
890 close these chains. */
892 for (i
= 0; i
< n_ops
; i
++)
894 old_operands
[i
] = recog_data
.operand
[i
];
895 if (recog_data
.operand_type
[i
] == OP_INOUT
)
896 *recog_data
.operand_loc
[i
] = cc0_rtx
;
898 for (i
= 0; i
< recog_data
.n_dups
; i
++)
900 int opn
= recog_data
.dup_num
[i
];
901 old_dups
[i
] = *recog_data
.dup_loc
[i
];
902 if (recog_data
.operand_type
[opn
] == OP_INOUT
)
903 *recog_data
.dup_loc
[i
] = cc0_rtx
;
906 scan_rtx (insn
, &PATTERN (insn
), NO_REGS
, terminate_write
, OP_IN
, 0);
908 for (i
= 0; i
< recog_data
.n_dups
; i
++)
909 *recog_data
.dup_loc
[i
] = old_dups
[i
];
910 for (i
= 0; i
< n_ops
; i
++)
911 *recog_data
.operand_loc
[i
] = old_operands
[i
];
913 /* Step 6: Begin new chains for writes inside operands. */
914 /* ??? Many targets have output constraints on the SET_DEST
915 of a call insn, which is stupid, since these are certainly
916 ABI defined hard registers. Don't change calls at all.
917 Similarly take special care for asm statement that originally
918 referenced hard registers. */
919 if (asm_noperands (PATTERN (insn
)) > 0)
921 for (i
= 0; i
< n_ops
; i
++)
922 if (recog_data
.operand_type
[i
] == OP_OUT
)
924 rtx
*loc
= recog_data
.operand_loc
[i
];
926 enum reg_class cl
= recog_op_alt
[i
][alt
].cl
;
929 && REGNO (op
) == ORIGINAL_REGNO (op
))
932 scan_rtx (insn
, loc
, cl
, mark_write
, OP_OUT
,
933 recog_op_alt
[i
][alt
].earlyclobber
);
936 else if (!CALL_P (insn
))
937 for (i
= 0; i
< n_ops
+ recog_data
.n_dups
; i
++)
939 int opn
= i
< n_ops
? i
: recog_data
.dup_num
[i
- n_ops
];
940 rtx
*loc
= (i
< n_ops
941 ? recog_data
.operand_loc
[opn
]
942 : recog_data
.dup_loc
[i
- n_ops
]);
943 enum reg_class cl
= recog_op_alt
[opn
][alt
].cl
;
945 if (recog_data
.operand_type
[opn
] == OP_OUT
)
946 scan_rtx (insn
, loc
, cl
, mark_write
, OP_OUT
,
947 recog_op_alt
[opn
][alt
].earlyclobber
);
950 /* Step 6B: Record destination regs in REG_FRAME_RELATED_EXPR
952 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
953 if (REG_NOTE_KIND (note
) == REG_FRAME_RELATED_EXPR
)
954 scan_rtx (insn
, &XEXP (note
, 0), ALL_REGS
, mark_access
,
957 /* Step 7: Close chains for registers that were never
959 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
960 if (REG_NOTE_KIND (note
) == REG_UNUSED
)
961 scan_rtx (insn
, &XEXP (note
, 0), NO_REGS
, terminate_dead
,
964 if (insn
== BB_END (bb
))
968 /* Since we close every chain when we find a REG_DEAD note, anything that
969 is still open lives past the basic block, so it can't be renamed. */
970 return closed_chains
;
973 /* Dump all def/use chains in CHAINS to DUMP_FILE. They are
974 printed in reverse order as that's how we build them. */
977 dump_def_use_chain (struct du_chain
*chains
)
981 struct du_chain
*this = chains
;
982 int r
= REGNO (*this->loc
);
983 int nregs
= hard_regno_nregs
[r
][GET_MODE (*this->loc
)];
984 fprintf (dump_file
, "Register %s (%d):", reg_names
[r
], nregs
);
987 fprintf (dump_file
, " %d [%s]", INSN_UID (this->insn
),
988 reg_class_names
[this->cl
]);
989 this = this->next_use
;
991 fprintf (dump_file
, "\n");
992 chains
= chains
->next_chain
;
996 /* The following code does forward propagation of hard register copies.
997 The object is to eliminate as many dependencies as possible, so that
998 we have the most scheduling freedom. As a side effect, we also clean
999 up some silly register allocation decisions made by reload. This
1000 code may be obsoleted by a new register allocator. */
1002 /* For each register, we have a list of registers that contain the same
1003 value. The OLDEST_REGNO field points to the head of the list, and
1004 the NEXT_REGNO field runs through the list. The MODE field indicates
1005 what mode the data is known to be in; this field is VOIDmode when the
1006 register is not known to contain valid data. */
1008 struct value_data_entry
1010 enum machine_mode mode
;
1011 unsigned int oldest_regno
;
1012 unsigned int next_regno
;
1017 struct value_data_entry e
[FIRST_PSEUDO_REGISTER
];
1018 unsigned int max_value_regs
;
1021 static void kill_value_one_regno (unsigned, struct value_data
*);
1022 static void kill_value_regno (unsigned, unsigned, struct value_data
*);
1023 static void kill_value (rtx
, struct value_data
*);
1024 static void set_value_regno (unsigned, enum machine_mode
, struct value_data
*);
1025 static void init_value_data (struct value_data
*);
1026 static void kill_clobbered_value (rtx
, const_rtx
, void *);
1027 static void kill_set_value (rtx
, const_rtx
, void *);
1028 static int kill_autoinc_value (rtx
*, void *);
1029 static void copy_value (rtx
, rtx
, struct value_data
*);
1030 static bool mode_change_ok (enum machine_mode
, enum machine_mode
,
1032 static rtx
maybe_mode_change (enum machine_mode
, enum machine_mode
,
1033 enum machine_mode
, unsigned int, unsigned int);
1034 static rtx
find_oldest_value_reg (enum reg_class
, rtx
, struct value_data
*);
1035 static bool replace_oldest_value_reg (rtx
*, enum reg_class
, rtx
,
1036 struct value_data
*);
1037 static bool replace_oldest_value_addr (rtx
*, enum reg_class
,
1038 enum machine_mode
, rtx
,
1039 struct value_data
*);
1040 static bool replace_oldest_value_mem (rtx
, rtx
, struct value_data
*);
1041 static bool copyprop_hardreg_forward_1 (basic_block
, struct value_data
*);
1042 extern void debug_value_data (struct value_data
*);
1043 #ifdef ENABLE_CHECKING
1044 static void validate_value_data (struct value_data
*);
1047 /* Kill register REGNO. This involves removing it from any value
1048 lists, and resetting the value mode to VOIDmode. This is only a
1049 helper function; it does not handle any hard registers overlapping
1053 kill_value_one_regno (unsigned int regno
, struct value_data
*vd
)
1055 unsigned int i
, next
;
1057 if (vd
->e
[regno
].oldest_regno
!= regno
)
1059 for (i
= vd
->e
[regno
].oldest_regno
;
1060 vd
->e
[i
].next_regno
!= regno
;
1061 i
= vd
->e
[i
].next_regno
)
1063 vd
->e
[i
].next_regno
= vd
->e
[regno
].next_regno
;
1065 else if ((next
= vd
->e
[regno
].next_regno
) != INVALID_REGNUM
)
1067 for (i
= next
; i
!= INVALID_REGNUM
; i
= vd
->e
[i
].next_regno
)
1068 vd
->e
[i
].oldest_regno
= next
;
1071 vd
->e
[regno
].mode
= VOIDmode
;
1072 vd
->e
[regno
].oldest_regno
= regno
;
1073 vd
->e
[regno
].next_regno
= INVALID_REGNUM
;
1075 #ifdef ENABLE_CHECKING
1076 validate_value_data (vd
);
1080 /* Kill the value in register REGNO for NREGS, and any other registers
1081 whose values overlap. */
1084 kill_value_regno (unsigned int regno
, unsigned int nregs
,
1085 struct value_data
*vd
)
1089 /* Kill the value we're told to kill. */
1090 for (j
= 0; j
< nregs
; ++j
)
1091 kill_value_one_regno (regno
+ j
, vd
);
1093 /* Kill everything that overlapped what we're told to kill. */
1094 if (regno
< vd
->max_value_regs
)
1097 j
= regno
- vd
->max_value_regs
;
1098 for (; j
< regno
; ++j
)
1101 if (vd
->e
[j
].mode
== VOIDmode
)
1103 n
= hard_regno_nregs
[j
][vd
->e
[j
].mode
];
1105 for (i
= 0; i
< n
; ++i
)
1106 kill_value_one_regno (j
+ i
, vd
);
1110 /* Kill X. This is a convenience function wrapping kill_value_regno
1111 so that we mind the mode the register is in. */
1114 kill_value (rtx x
, struct value_data
*vd
)
1118 if (GET_CODE (x
) == SUBREG
)
1120 x
= simplify_subreg (GET_MODE (x
), SUBREG_REG (x
),
1121 GET_MODE (SUBREG_REG (x
)), SUBREG_BYTE (x
));
1123 x
= SUBREG_REG (orig_rtx
);
1127 unsigned int regno
= REGNO (x
);
1128 unsigned int n
= hard_regno_nregs
[regno
][GET_MODE (x
)];
1130 kill_value_regno (regno
, n
, vd
);
1134 /* Remember that REGNO is valid in MODE. */
1137 set_value_regno (unsigned int regno
, enum machine_mode mode
,
1138 struct value_data
*vd
)
1142 vd
->e
[regno
].mode
= mode
;
1144 nregs
= hard_regno_nregs
[regno
][mode
];
1145 if (nregs
> vd
->max_value_regs
)
1146 vd
->max_value_regs
= nregs
;
1149 /* Initialize VD such that there are no known relationships between regs. */
1152 init_value_data (struct value_data
*vd
)
1155 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1157 vd
->e
[i
].mode
= VOIDmode
;
1158 vd
->e
[i
].oldest_regno
= i
;
1159 vd
->e
[i
].next_regno
= INVALID_REGNUM
;
1161 vd
->max_value_regs
= 0;
1164 /* Called through note_stores. If X is clobbered, kill its value. */
1167 kill_clobbered_value (rtx x
, const_rtx set
, void *data
)
1169 struct value_data
*vd
= data
;
1170 if (GET_CODE (set
) == CLOBBER
)
1174 /* Called through note_stores. If X is set, not clobbered, kill its
1175 current value and install it as the root of its own value list. */
1178 kill_set_value (rtx x
, const_rtx set
, void *data
)
1180 struct value_data
*vd
= data
;
1181 if (GET_CODE (set
) != CLOBBER
)
1185 set_value_regno (REGNO (x
), GET_MODE (x
), vd
);
1189 /* Called through for_each_rtx. Kill any register used as the base of an
1190 auto-increment expression, and install that register as the root of its
1194 kill_autoinc_value (rtx
*px
, void *data
)
1197 struct value_data
*vd
= data
;
1199 if (GET_RTX_CLASS (GET_CODE (x
)) == RTX_AUTOINC
)
1203 set_value_regno (REGNO (x
), Pmode
, vd
);
1210 /* Assert that SRC has been copied to DEST. Adjust the data structures
1211 to reflect that SRC contains an older copy of the shared value. */
1214 copy_value (rtx dest
, rtx src
, struct value_data
*vd
)
1216 unsigned int dr
= REGNO (dest
);
1217 unsigned int sr
= REGNO (src
);
1218 unsigned int dn
, sn
;
1221 /* ??? At present, it's possible to see noop sets. It'd be nice if
1222 this were cleaned up beforehand... */
1226 /* Do not propagate copies to the stack pointer, as that can leave
1227 memory accesses with no scheduling dependency on the stack update. */
1228 if (dr
== STACK_POINTER_REGNUM
)
1231 /* Likewise with the frame pointer, if we're using one. */
1232 if (frame_pointer_needed
&& dr
== HARD_FRAME_POINTER_REGNUM
)
1235 /* Do not propagate copies to fixed or global registers, patterns
1236 can be relying to see particular fixed register or users can
1237 expect the chosen global register in asm. */
1238 if (fixed_regs
[dr
] || global_regs
[dr
])
1241 /* If SRC and DEST overlap, don't record anything. */
1242 dn
= hard_regno_nregs
[dr
][GET_MODE (dest
)];
1243 sn
= hard_regno_nregs
[sr
][GET_MODE (dest
)];
1244 if ((dr
> sr
&& dr
< sr
+ sn
)
1245 || (sr
> dr
&& sr
< dr
+ dn
))
1248 /* If SRC had no assigned mode (i.e. we didn't know it was live)
1249 assign it now and assume the value came from an input argument
1251 if (vd
->e
[sr
].mode
== VOIDmode
)
1252 set_value_regno (sr
, vd
->e
[dr
].mode
, vd
);
1254 /* If we are narrowing the input to a smaller number of hard regs,
1255 and it is in big endian, we are really extracting a high part.
1256 Since we generally associate a low part of a value with the value itself,
1257 we must not do the same for the high part.
1258 Note we can still get low parts for the same mode combination through
1259 a two-step copy involving differently sized hard regs.
1260 Assume hard regs fr* are 32 bits bits each, while r* are 64 bits each:
1261 (set (reg:DI r0) (reg:DI fr0))
1262 (set (reg:SI fr2) (reg:SI r0))
1263 loads the low part of (reg:DI fr0) - i.e. fr1 - into fr2, while:
1264 (set (reg:SI fr2) (reg:SI fr0))
1265 loads the high part of (reg:DI fr0) into fr2.
1267 We can't properly represent the latter case in our tables, so don't
1268 record anything then. */
1269 else if (sn
< (unsigned int) hard_regno_nregs
[sr
][vd
->e
[sr
].mode
]
1270 && (GET_MODE_SIZE (vd
->e
[sr
].mode
) > UNITS_PER_WORD
1271 ? WORDS_BIG_ENDIAN
: BYTES_BIG_ENDIAN
))
1274 /* If SRC had been assigned a mode narrower than the copy, we can't
1275 link DEST into the chain, because not all of the pieces of the
1276 copy came from oldest_regno. */
1277 else if (sn
> (unsigned int) hard_regno_nregs
[sr
][vd
->e
[sr
].mode
])
1280 /* Link DR at the end of the value chain used by SR. */
1282 vd
->e
[dr
].oldest_regno
= vd
->e
[sr
].oldest_regno
;
1284 for (i
= sr
; vd
->e
[i
].next_regno
!= INVALID_REGNUM
; i
= vd
->e
[i
].next_regno
)
1286 vd
->e
[i
].next_regno
= dr
;
1288 #ifdef ENABLE_CHECKING
1289 validate_value_data (vd
);
1293 /* Return true if a mode change from ORIG to NEW is allowed for REGNO. */
1296 mode_change_ok (enum machine_mode orig_mode
, enum machine_mode new_mode
,
1297 unsigned int regno ATTRIBUTE_UNUSED
)
1299 if (GET_MODE_SIZE (orig_mode
) < GET_MODE_SIZE (new_mode
))
1302 #ifdef CANNOT_CHANGE_MODE_CLASS
1303 return !REG_CANNOT_CHANGE_MODE_P (regno
, orig_mode
, new_mode
);
1309 /* Register REGNO was originally set in ORIG_MODE. It - or a copy of it -
1310 was copied in COPY_MODE to COPY_REGNO, and then COPY_REGNO was accessed
1312 Return a NEW_MODE rtx for REGNO if that's OK, otherwise return NULL_RTX. */
1315 maybe_mode_change (enum machine_mode orig_mode
, enum machine_mode copy_mode
,
1316 enum machine_mode new_mode
, unsigned int regno
,
1317 unsigned int copy_regno ATTRIBUTE_UNUSED
)
1319 if (orig_mode
== new_mode
)
1320 return gen_rtx_raw_REG (new_mode
, regno
);
1321 else if (mode_change_ok (orig_mode
, new_mode
, regno
))
1323 int copy_nregs
= hard_regno_nregs
[copy_regno
][copy_mode
];
1324 int use_nregs
= hard_regno_nregs
[copy_regno
][new_mode
];
1326 = GET_MODE_SIZE (copy_mode
) / copy_nregs
* (copy_nregs
- use_nregs
);
1328 = GET_MODE_SIZE (orig_mode
) - GET_MODE_SIZE (new_mode
) - copy_offset
;
1329 int byteoffset
= offset
% UNITS_PER_WORD
;
1330 int wordoffset
= offset
- byteoffset
;
1332 offset
= ((WORDS_BIG_ENDIAN
? wordoffset
: 0)
1333 + (BYTES_BIG_ENDIAN
? byteoffset
: 0));
1334 return gen_rtx_raw_REG (new_mode
,
1335 regno
+ subreg_regno_offset (regno
, orig_mode
,
1342 /* Find the oldest copy of the value contained in REGNO that is in
1343 register class CL and has mode MODE. If found, return an rtx
1344 of that oldest register, otherwise return NULL. */
1347 find_oldest_value_reg (enum reg_class cl
, rtx reg
, struct value_data
*vd
)
1349 unsigned int regno
= REGNO (reg
);
1350 enum machine_mode mode
= GET_MODE (reg
);
1353 /* If we are accessing REG in some mode other that what we set it in,
1354 make sure that the replacement is valid. In particular, consider
1355 (set (reg:DI r11) (...))
1356 (set (reg:SI r9) (reg:SI r11))
1357 (set (reg:SI r10) (...))
1358 (set (...) (reg:DI r9))
1359 Replacing r9 with r11 is invalid. */
1360 if (mode
!= vd
->e
[regno
].mode
)
1362 if (hard_regno_nregs
[regno
][mode
]
1363 > hard_regno_nregs
[regno
][vd
->e
[regno
].mode
])
1367 for (i
= vd
->e
[regno
].oldest_regno
; i
!= regno
; i
= vd
->e
[i
].next_regno
)
1369 enum machine_mode oldmode
= vd
->e
[i
].mode
;
1372 if (!in_hard_reg_set_p (reg_class_contents
[cl
], mode
, i
))
1375 new = maybe_mode_change (oldmode
, vd
->e
[regno
].mode
, mode
, i
, regno
);
1378 ORIGINAL_REGNO (new) = ORIGINAL_REGNO (reg
);
1379 REG_ATTRS (new) = REG_ATTRS (reg
);
1387 /* If possible, replace the register at *LOC with the oldest register
1388 in register class CL. Return true if successfully replaced. */
1391 replace_oldest_value_reg (rtx
*loc
, enum reg_class cl
, rtx insn
,
1392 struct value_data
*vd
)
1394 rtx
new = find_oldest_value_reg (cl
, *loc
, vd
);
1398 fprintf (dump_file
, "insn %u: replaced reg %u with %u\n",
1399 INSN_UID (insn
), REGNO (*loc
), REGNO (new));
1401 validate_change (insn
, loc
, new, 1);
1407 /* Similar to replace_oldest_value_reg, but *LOC contains an address.
1408 Adapted from find_reloads_address_1. CL is INDEX_REG_CLASS or
1409 BASE_REG_CLASS depending on how the register is being considered. */
1412 replace_oldest_value_addr (rtx
*loc
, enum reg_class cl
,
1413 enum machine_mode mode
, rtx insn
,
1414 struct value_data
*vd
)
1417 RTX_CODE code
= GET_CODE (x
);
1420 bool changed
= false;
1426 rtx orig_op0
= XEXP (x
, 0);
1427 rtx orig_op1
= XEXP (x
, 1);
1428 RTX_CODE code0
= GET_CODE (orig_op0
);
1429 RTX_CODE code1
= GET_CODE (orig_op1
);
1434 enum rtx_code index_code
= SCRATCH
;
1436 if (GET_CODE (op0
) == SUBREG
)
1438 op0
= SUBREG_REG (op0
);
1439 code0
= GET_CODE (op0
);
1442 if (GET_CODE (op1
) == SUBREG
)
1444 op1
= SUBREG_REG (op1
);
1445 code1
= GET_CODE (op1
);
1448 if (code0
== MULT
|| code0
== SIGN_EXTEND
|| code0
== TRUNCATE
1449 || code0
== ZERO_EXTEND
|| code1
== MEM
)
1451 locI
= &XEXP (x
, 0);
1452 locB
= &XEXP (x
, 1);
1453 index_code
= GET_CODE (*locI
);
1455 else if (code1
== MULT
|| code1
== SIGN_EXTEND
|| code1
== TRUNCATE
1456 || code1
== ZERO_EXTEND
|| code0
== MEM
)
1458 locI
= &XEXP (x
, 1);
1459 locB
= &XEXP (x
, 0);
1460 index_code
= GET_CODE (*locI
);
1462 else if (code0
== CONST_INT
|| code0
== CONST
1463 || code0
== SYMBOL_REF
|| code0
== LABEL_REF
)
1465 locB
= &XEXP (x
, 1);
1466 index_code
= GET_CODE (XEXP (x
, 0));
1468 else if (code1
== CONST_INT
|| code1
== CONST
1469 || code1
== SYMBOL_REF
|| code1
== LABEL_REF
)
1471 locB
= &XEXP (x
, 0);
1472 index_code
= GET_CODE (XEXP (x
, 1));
1474 else if (code0
== REG
&& code1
== REG
)
1477 unsigned regno0
= REGNO (op0
), regno1
= REGNO (op1
);
1479 if (REGNO_OK_FOR_INDEX_P (regno0
)
1480 && regno_ok_for_base_p (regno1
, mode
, PLUS
, REG
))
1482 else if (REGNO_OK_FOR_INDEX_P (regno1
)
1483 && regno_ok_for_base_p (regno0
, mode
, PLUS
, REG
))
1485 else if (regno_ok_for_base_p (regno1
, mode
, PLUS
, REG
))
1487 else if (regno_ok_for_base_p (regno0
, mode
, PLUS
, REG
))
1489 else if (REGNO_OK_FOR_INDEX_P (regno1
))
1494 locI
= &XEXP (x
, index_op
);
1495 locB
= &XEXP (x
, !index_op
);
1496 index_code
= GET_CODE (*locI
);
1498 else if (code0
== REG
)
1500 locI
= &XEXP (x
, 0);
1501 locB
= &XEXP (x
, 1);
1502 index_code
= GET_CODE (*locI
);
1504 else if (code1
== REG
)
1506 locI
= &XEXP (x
, 1);
1507 locB
= &XEXP (x
, 0);
1508 index_code
= GET_CODE (*locI
);
1512 changed
|= replace_oldest_value_addr (locI
, INDEX_REG_CLASS
, mode
,
1515 changed
|= replace_oldest_value_addr (locB
,
1516 base_reg_class (mode
, PLUS
,
1531 return replace_oldest_value_mem (x
, insn
, vd
);
1534 return replace_oldest_value_reg (loc
, cl
, insn
, vd
);
1540 fmt
= GET_RTX_FORMAT (code
);
1541 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1544 changed
|= replace_oldest_value_addr (&XEXP (x
, i
), cl
, mode
,
1546 else if (fmt
[i
] == 'E')
1547 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
1548 changed
|= replace_oldest_value_addr (&XVECEXP (x
, i
, j
), cl
,
1555 /* Similar to replace_oldest_value_reg, but X contains a memory. */
1558 replace_oldest_value_mem (rtx x
, rtx insn
, struct value_data
*vd
)
1560 return replace_oldest_value_addr (&XEXP (x
, 0),
1561 base_reg_class (GET_MODE (x
), MEM
,
1563 GET_MODE (x
), insn
, vd
);
1566 /* Perform the forward copy propagation on basic block BB. */
1569 copyprop_hardreg_forward_1 (basic_block bb
, struct value_data
*vd
)
1571 bool changed
= false;
1574 for (insn
= BB_HEAD (bb
); ; insn
= NEXT_INSN (insn
))
1576 int n_ops
, i
, alt
, predicated
;
1577 bool is_asm
, any_replacements
;
1579 bool replaced
[MAX_RECOG_OPERANDS
];
1581 if (! INSN_P (insn
))
1583 if (insn
== BB_END (bb
))
1589 set
= single_set (insn
);
1590 extract_insn (insn
);
1591 if (! constrain_operands (1))
1592 fatal_insn_not_found (insn
);
1593 preprocess_constraints ();
1594 alt
= which_alternative
;
1595 n_ops
= recog_data
.n_operands
;
1596 is_asm
= asm_noperands (PATTERN (insn
)) >= 0;
1598 /* Simplify the code below by rewriting things to reflect
1599 matching constraints. Also promote OP_OUT to OP_INOUT
1600 in predicated instructions. */
1602 predicated
= GET_CODE (PATTERN (insn
)) == COND_EXEC
;
1603 for (i
= 0; i
< n_ops
; ++i
)
1605 int matches
= recog_op_alt
[i
][alt
].matches
;
1607 recog_op_alt
[i
][alt
].cl
= recog_op_alt
[matches
][alt
].cl
;
1608 if (matches
>= 0 || recog_op_alt
[i
][alt
].matched
>= 0
1609 || (predicated
&& recog_data
.operand_type
[i
] == OP_OUT
))
1610 recog_data
.operand_type
[i
] = OP_INOUT
;
1613 /* For each earlyclobber operand, zap the value data. */
1614 for (i
= 0; i
< n_ops
; i
++)
1615 if (recog_op_alt
[i
][alt
].earlyclobber
)
1616 kill_value (recog_data
.operand
[i
], vd
);
1618 /* Within asms, a clobber cannot overlap inputs or outputs.
1619 I wouldn't think this were true for regular insns, but
1620 scan_rtx treats them like that... */
1621 note_stores (PATTERN (insn
), kill_clobbered_value
, vd
);
1623 /* Kill all auto-incremented values. */
1624 /* ??? REG_INC is useless, since stack pushes aren't done that way. */
1625 for_each_rtx (&PATTERN (insn
), kill_autoinc_value
, vd
);
1627 /* Kill all early-clobbered operands. */
1628 for (i
= 0; i
< n_ops
; i
++)
1629 if (recog_op_alt
[i
][alt
].earlyclobber
)
1630 kill_value (recog_data
.operand
[i
], vd
);
1632 /* Special-case plain move instructions, since we may well
1633 be able to do the move from a different register class. */
1634 if (set
&& REG_P (SET_SRC (set
)))
1636 rtx src
= SET_SRC (set
);
1637 unsigned int regno
= REGNO (src
);
1638 enum machine_mode mode
= GET_MODE (src
);
1642 /* If we are accessing SRC in some mode other that what we
1643 set it in, make sure that the replacement is valid. */
1644 if (mode
!= vd
->e
[regno
].mode
)
1646 if (hard_regno_nregs
[regno
][mode
]
1647 > hard_regno_nregs
[regno
][vd
->e
[regno
].mode
])
1648 goto no_move_special_case
;
1651 /* If the destination is also a register, try to find a source
1652 register in the same class. */
1653 if (REG_P (SET_DEST (set
)))
1655 new = find_oldest_value_reg (REGNO_REG_CLASS (regno
), src
, vd
);
1656 if (new && validate_change (insn
, &SET_SRC (set
), new, 0))
1660 "insn %u: replaced reg %u with %u\n",
1661 INSN_UID (insn
), regno
, REGNO (new));
1663 goto did_replacement
;
1667 /* Otherwise, try all valid registers and see if its valid. */
1668 for (i
= vd
->e
[regno
].oldest_regno
; i
!= regno
;
1669 i
= vd
->e
[i
].next_regno
)
1671 new = maybe_mode_change (vd
->e
[i
].mode
, vd
->e
[regno
].mode
,
1673 if (new != NULL_RTX
)
1675 if (validate_change (insn
, &SET_SRC (set
), new, 0))
1677 ORIGINAL_REGNO (new) = ORIGINAL_REGNO (src
);
1678 REG_ATTRS (new) = REG_ATTRS (src
);
1681 "insn %u: replaced reg %u with %u\n",
1682 INSN_UID (insn
), regno
, REGNO (new));
1684 goto did_replacement
;
1689 no_move_special_case
:
1691 any_replacements
= false;
1693 /* For each input operand, replace a hard register with the
1694 eldest live copy that's in an appropriate register class. */
1695 for (i
= 0; i
< n_ops
; i
++)
1697 replaced
[i
] = false;
1699 /* Don't scan match_operand here, since we've no reg class
1700 information to pass down. Any operands that we could
1701 substitute in will be represented elsewhere. */
1702 if (recog_data
.constraints
[i
][0] == '\0')
1705 /* Don't replace in asms intentionally referencing hard regs. */
1706 if (is_asm
&& REG_P (recog_data
.operand
[i
])
1707 && (REGNO (recog_data
.operand
[i
])
1708 == ORIGINAL_REGNO (recog_data
.operand
[i
])))
1711 if (recog_data
.operand_type
[i
] == OP_IN
)
1713 if (recog_op_alt
[i
][alt
].is_address
)
1715 = replace_oldest_value_addr (recog_data
.operand_loc
[i
],
1716 recog_op_alt
[i
][alt
].cl
,
1717 VOIDmode
, insn
, vd
);
1718 else if (REG_P (recog_data
.operand
[i
]))
1720 = replace_oldest_value_reg (recog_data
.operand_loc
[i
],
1721 recog_op_alt
[i
][alt
].cl
,
1723 else if (MEM_P (recog_data
.operand
[i
]))
1724 replaced
[i
] = replace_oldest_value_mem (recog_data
.operand
[i
],
1727 else if (MEM_P (recog_data
.operand
[i
]))
1728 replaced
[i
] = replace_oldest_value_mem (recog_data
.operand
[i
],
1731 /* If we performed any replacement, update match_dups. */
1737 new = *recog_data
.operand_loc
[i
];
1738 recog_data
.operand
[i
] = new;
1739 for (j
= 0; j
< recog_data
.n_dups
; j
++)
1740 if (recog_data
.dup_num
[j
] == i
)
1741 validate_unshare_change (insn
, recog_data
.dup_loc
[j
], new, 1);
1743 any_replacements
= true;
1747 if (any_replacements
)
1749 if (! apply_change_group ())
1751 for (i
= 0; i
< n_ops
; i
++)
1754 rtx old
= *recog_data
.operand_loc
[i
];
1755 recog_data
.operand
[i
] = old
;
1760 "insn %u: reg replacements not verified\n",
1768 /* Clobber call-clobbered registers. */
1770 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1771 if (TEST_HARD_REG_BIT (regs_invalidated_by_call
, i
))
1772 kill_value_regno (i
, 1, vd
);
1774 /* Notice stores. */
1775 note_stores (PATTERN (insn
), kill_set_value
, vd
);
1777 /* Notice copies. */
1778 if (set
&& REG_P (SET_DEST (set
)) && REG_P (SET_SRC (set
)))
1779 copy_value (SET_DEST (set
), SET_SRC (set
), vd
);
1781 if (insn
== BB_END (bb
))
1788 /* Main entry point for the forward copy propagation optimization. */
1791 copyprop_hardreg_forward (void)
1793 struct value_data
*all_vd
;
1797 all_vd
= XNEWVEC (struct value_data
, last_basic_block
);
1799 visited
= sbitmap_alloc (last_basic_block
);
1800 sbitmap_zero (visited
);
1804 SET_BIT (visited
, bb
->index
);
1806 /* If a block has a single predecessor, that we've already
1807 processed, begin with the value data that was live at
1808 the end of the predecessor block. */
1809 /* ??? Ought to use more intelligent queuing of blocks. */
1810 if (single_pred_p (bb
)
1811 && TEST_BIT (visited
, single_pred (bb
)->index
)
1812 && ! (single_pred_edge (bb
)->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
)))
1813 all_vd
[bb
->index
] = all_vd
[single_pred (bb
)->index
];
1815 init_value_data (all_vd
+ bb
->index
);
1817 copyprop_hardreg_forward_1 (bb
, all_vd
+ bb
->index
);
1820 sbitmap_free (visited
);
1824 /* Dump the value chain data to stderr. */
1827 debug_value_data (struct value_data
*vd
)
1832 CLEAR_HARD_REG_SET (set
);
1834 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1835 if (vd
->e
[i
].oldest_regno
== i
)
1837 if (vd
->e
[i
].mode
== VOIDmode
)
1839 if (vd
->e
[i
].next_regno
!= INVALID_REGNUM
)
1840 fprintf (stderr
, "[%u] Bad next_regno for empty chain (%u)\n",
1841 i
, vd
->e
[i
].next_regno
);
1845 SET_HARD_REG_BIT (set
, i
);
1846 fprintf (stderr
, "[%u %s] ", i
, GET_MODE_NAME (vd
->e
[i
].mode
));
1848 for (j
= vd
->e
[i
].next_regno
;
1849 j
!= INVALID_REGNUM
;
1850 j
= vd
->e
[j
].next_regno
)
1852 if (TEST_HARD_REG_BIT (set
, j
))
1854 fprintf (stderr
, "[%u] Loop in regno chain\n", j
);
1858 if (vd
->e
[j
].oldest_regno
!= i
)
1860 fprintf (stderr
, "[%u] Bad oldest_regno (%u)\n",
1861 j
, vd
->e
[j
].oldest_regno
);
1864 SET_HARD_REG_BIT (set
, j
);
1865 fprintf (stderr
, "[%u %s] ", j
, GET_MODE_NAME (vd
->e
[j
].mode
));
1867 fputc ('\n', stderr
);
1870 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1871 if (! TEST_HARD_REG_BIT (set
, i
)
1872 && (vd
->e
[i
].mode
!= VOIDmode
1873 || vd
->e
[i
].oldest_regno
!= i
1874 || vd
->e
[i
].next_regno
!= INVALID_REGNUM
))
1875 fprintf (stderr
, "[%u] Non-empty reg in chain (%s %u %i)\n",
1876 i
, GET_MODE_NAME (vd
->e
[i
].mode
), vd
->e
[i
].oldest_regno
,
1877 vd
->e
[i
].next_regno
);
1880 #ifdef ENABLE_CHECKING
1882 validate_value_data (struct value_data
*vd
)
1887 CLEAR_HARD_REG_SET (set
);
1889 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1890 if (vd
->e
[i
].oldest_regno
== i
)
1892 if (vd
->e
[i
].mode
== VOIDmode
)
1894 if (vd
->e
[i
].next_regno
!= INVALID_REGNUM
)
1895 internal_error ("validate_value_data: [%u] Bad next_regno for empty chain (%u)",
1896 i
, vd
->e
[i
].next_regno
);
1900 SET_HARD_REG_BIT (set
, i
);
1902 for (j
= vd
->e
[i
].next_regno
;
1903 j
!= INVALID_REGNUM
;
1904 j
= vd
->e
[j
].next_regno
)
1906 if (TEST_HARD_REG_BIT (set
, j
))
1907 internal_error ("validate_value_data: Loop in regno chain (%u)",
1909 if (vd
->e
[j
].oldest_regno
!= i
)
1910 internal_error ("validate_value_data: [%u] Bad oldest_regno (%u)",
1911 j
, vd
->e
[j
].oldest_regno
);
1913 SET_HARD_REG_BIT (set
, j
);
1917 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1918 if (! TEST_HARD_REG_BIT (set
, i
)
1919 && (vd
->e
[i
].mode
!= VOIDmode
1920 || vd
->e
[i
].oldest_regno
!= i
1921 || vd
->e
[i
].next_regno
!= INVALID_REGNUM
))
1922 internal_error ("validate_value_data: [%u] Non-empty reg in chain (%s %u %i)",
1923 i
, GET_MODE_NAME (vd
->e
[i
].mode
), vd
->e
[i
].oldest_regno
,
1924 vd
->e
[i
].next_regno
);
1929 gate_handle_regrename (void)
1931 return (optimize
> 0 && (flag_rename_registers
));
1935 /* Run the regrename and cprop passes. */
1937 rest_of_handle_regrename (void)
1939 regrename_optimize ();
1943 struct tree_opt_pass pass_regrename
=
1946 gate_handle_regrename
, /* gate */
1947 rest_of_handle_regrename
, /* execute */
1950 0, /* static_pass_number */
1951 TV_RENAME_REGISTERS
, /* tv_id */
1952 0, /* properties_required */
1953 0, /* properties_provided */
1954 0, /* properties_destroyed */
1955 0, /* todo_flags_start */
1956 TODO_df_finish
| TODO_verify_rtl_sharing
|
1957 TODO_dump_func
, /* todo_flags_finish */
1962 gate_handle_cprop (void)
1964 return (optimize
> 0 && (flag_cprop_registers
));
1968 /* Run the regrename and cprop passes. */
1970 rest_of_handle_cprop (void)
1972 copyprop_hardreg_forward ();
1976 struct tree_opt_pass pass_cprop_hardreg
=
1978 "cprop_hardreg", /* name */
1979 gate_handle_cprop
, /* gate */
1980 rest_of_handle_cprop
, /* execute */
1983 0, /* static_pass_number */
1984 TV_RENAME_REGISTERS
, /* tv_id */
1985 0, /* properties_required */
1986 0, /* properties_provided */
1987 0, /* properties_destroyed */
1988 0, /* todo_flags_start */
1989 TODO_dump_func
| TODO_verify_rtl_sharing
, /* todo_flags_finish */