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_NO_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
);
348 df_clear_flags (DF_NO_INSN_RESCAN
);
349 df_insn_rescan_all ();
352 fputc ('\n', dump_file
);
356 do_replace (struct du_chain
*chain
, int reg
)
360 unsigned int regno
= ORIGINAL_REGNO (*chain
->loc
);
361 struct reg_attrs
* attr
= REG_ATTRS (*chain
->loc
);
363 *chain
->loc
= gen_raw_REG (GET_MODE (*chain
->loc
), reg
);
364 if (regno
>= FIRST_PSEUDO_REGISTER
)
365 ORIGINAL_REGNO (*chain
->loc
) = regno
;
366 REG_ATTRS (*chain
->loc
) = attr
;
367 chain
= chain
->next_use
;
372 static struct du_chain
*open_chains
;
373 static struct du_chain
*closed_chains
;
376 scan_rtx_reg (rtx insn
, rtx
*loc
, enum reg_class cl
,
377 enum scan_actions action
, enum op_type type
, int earlyclobber
)
381 enum machine_mode mode
= GET_MODE (x
);
382 int this_regno
= REGNO (x
);
383 int this_nregs
= hard_regno_nregs
[this_regno
][mode
];
385 if (action
== mark_write
)
389 struct du_chain
*this
390 = obstack_alloc (&rename_obstack
, sizeof (struct du_chain
));
392 this->next_chain
= open_chains
;
396 this->need_caller_save_reg
= 0;
397 this->earlyclobber
= earlyclobber
;
403 if ((type
== OP_OUT
) != (action
== terminate_write
|| action
== mark_access
))
406 for (p
= &open_chains
; *p
;)
408 struct du_chain
*this = *p
;
410 /* Check if the chain has been terminated if it has then skip to
413 This can happen when we've already appended the location to
414 the chain in Step 3, but are trying to hide in-out operands
415 from terminate_write in Step 5. */
417 if (*this->loc
== cc0_rtx
)
418 p
= &this->next_chain
;
421 int regno
= REGNO (*this->loc
);
422 int nregs
= hard_regno_nregs
[regno
][GET_MODE (*this->loc
)];
423 int exact_match
= (regno
== this_regno
&& nregs
== this_nregs
);
425 if (regno
+ nregs
<= this_regno
426 || this_regno
+ this_nregs
<= regno
)
428 p
= &this->next_chain
;
432 if (action
== mark_read
|| action
== mark_access
)
434 gcc_assert (exact_match
);
436 /* ??? Class NO_REGS can happen if the md file makes use of
437 EXTRA_CONSTRAINTS to match registers. Which is arguably
438 wrong, but there we are. Since we know not what this may
439 be replaced with, terminate the chain. */
442 this = obstack_alloc (&rename_obstack
, sizeof (struct du_chain
));
444 this->next_chain
= (*p
)->next_chain
;
448 this->need_caller_save_reg
= 0;
456 if (action
!= terminate_overlapping_read
|| ! exact_match
)
458 struct du_chain
*next
= this->next_chain
;
460 /* Whether the terminated chain can be used for renaming
461 depends on the action and this being an exact match.
462 In either case, we remove this element from open_chains. */
464 if ((action
== terminate_dead
|| action
== terminate_write
)
467 this->next_chain
= closed_chains
;
468 closed_chains
= this;
471 "Closing chain %s at insn %d (%s)\n",
472 reg_names
[REGNO (*this->loc
)], INSN_UID (insn
),
473 scan_actions_name
[(int) action
]);
479 "Discarding chain %s at insn %d (%s)\n",
480 reg_names
[REGNO (*this->loc
)], INSN_UID (insn
),
481 scan_actions_name
[(int) action
]);
486 p
= &this->next_chain
;
491 /* Adapted from find_reloads_address_1. CL is INDEX_REG_CLASS or
492 BASE_REG_CLASS depending on how the register is being considered. */
495 scan_rtx_address (rtx insn
, rtx
*loc
, enum reg_class cl
,
496 enum scan_actions action
, enum machine_mode mode
)
499 RTX_CODE code
= GET_CODE (x
);
503 if (action
== mark_write
|| action
== mark_access
)
510 rtx orig_op0
= XEXP (x
, 0);
511 rtx orig_op1
= XEXP (x
, 1);
512 RTX_CODE code0
= GET_CODE (orig_op0
);
513 RTX_CODE code1
= GET_CODE (orig_op1
);
518 enum rtx_code index_code
= SCRATCH
;
520 if (GET_CODE (op0
) == SUBREG
)
522 op0
= SUBREG_REG (op0
);
523 code0
= GET_CODE (op0
);
526 if (GET_CODE (op1
) == SUBREG
)
528 op1
= SUBREG_REG (op1
);
529 code1
= GET_CODE (op1
);
532 if (code0
== MULT
|| code0
== SIGN_EXTEND
|| code0
== TRUNCATE
533 || code0
== ZERO_EXTEND
|| code1
== MEM
)
537 index_code
= GET_CODE (*locI
);
539 else if (code1
== MULT
|| code1
== SIGN_EXTEND
|| code1
== TRUNCATE
540 || code1
== ZERO_EXTEND
|| code0
== MEM
)
544 index_code
= GET_CODE (*locI
);
546 else if (code0
== CONST_INT
|| code0
== CONST
547 || code0
== SYMBOL_REF
|| code0
== LABEL_REF
)
550 index_code
= GET_CODE (XEXP (x
, 0));
552 else if (code1
== CONST_INT
|| code1
== CONST
553 || code1
== SYMBOL_REF
|| code1
== LABEL_REF
)
556 index_code
= GET_CODE (XEXP (x
, 1));
558 else if (code0
== REG
&& code1
== REG
)
561 unsigned regno0
= REGNO (op0
), regno1
= REGNO (op1
);
563 if (REGNO_OK_FOR_INDEX_P (regno0
)
564 && regno_ok_for_base_p (regno1
, mode
, PLUS
, REG
))
566 else if (REGNO_OK_FOR_INDEX_P (regno1
)
567 && regno_ok_for_base_p (regno0
, mode
, PLUS
, REG
))
569 else if (regno_ok_for_base_p (regno1
, mode
, PLUS
, REG
))
571 else if (regno_ok_for_base_p (regno0
, mode
, PLUS
, REG
))
573 else if (REGNO_OK_FOR_INDEX_P (regno1
))
578 locI
= &XEXP (x
, index_op
);
579 locB
= &XEXP (x
, !index_op
);
580 index_code
= GET_CODE (*locI
);
582 else if (code0
== REG
)
586 index_code
= GET_CODE (*locI
);
588 else if (code1
== REG
)
592 index_code
= GET_CODE (*locI
);
596 scan_rtx_address (insn
, locI
, INDEX_REG_CLASS
, action
, mode
);
598 scan_rtx_address (insn
, locB
, base_reg_class (mode
, PLUS
, index_code
),
611 /* If the target doesn't claim to handle autoinc, this must be
612 something special, like a stack push. Kill this chain. */
613 action
= terminate_all_read
;
618 scan_rtx_address (insn
, &XEXP (x
, 0),
619 base_reg_class (GET_MODE (x
), MEM
, SCRATCH
), action
,
624 scan_rtx_reg (insn
, loc
, cl
, action
, OP_IN
, 0);
631 fmt
= GET_RTX_FORMAT (code
);
632 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
635 scan_rtx_address (insn
, &XEXP (x
, i
), cl
, action
, mode
);
636 else if (fmt
[i
] == 'E')
637 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
638 scan_rtx_address (insn
, &XVECEXP (x
, i
, j
), cl
, action
, mode
);
643 scan_rtx (rtx insn
, rtx
*loc
, enum reg_class cl
,
644 enum scan_actions action
, enum op_type type
, int earlyclobber
)
648 enum rtx_code code
= GET_CODE (x
);
666 scan_rtx_reg (insn
, loc
, cl
, action
, type
, earlyclobber
);
670 scan_rtx_address (insn
, &XEXP (x
, 0),
671 base_reg_class (GET_MODE (x
), MEM
, SCRATCH
), action
,
676 scan_rtx (insn
, &SET_SRC (x
), cl
, action
, OP_IN
, 0);
677 scan_rtx (insn
, &SET_DEST (x
), cl
, action
,
678 GET_CODE (PATTERN (insn
)) == COND_EXEC
? OP_INOUT
: OP_OUT
, 0);
681 case STRICT_LOW_PART
:
682 scan_rtx (insn
, &XEXP (x
, 0), cl
, action
, OP_INOUT
, earlyclobber
);
687 scan_rtx (insn
, &XEXP (x
, 0), cl
, action
,
688 type
== OP_IN
? OP_IN
: OP_INOUT
, earlyclobber
);
689 scan_rtx (insn
, &XEXP (x
, 1), cl
, action
, OP_IN
, 0);
690 scan_rtx (insn
, &XEXP (x
, 2), cl
, action
, OP_IN
, 0);
699 /* Should only happen inside MEM. */
703 scan_rtx (insn
, &SET_DEST (x
), cl
, action
,
704 GET_CODE (PATTERN (insn
)) == COND_EXEC
? OP_INOUT
: OP_OUT
, 0);
708 scan_rtx (insn
, &XEXP (x
, 0), cl
, action
, type
, 0);
710 scan_rtx (insn
, &XEXP (x
, 1), cl
, action
, type
, 0);
717 fmt
= GET_RTX_FORMAT (code
);
718 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
721 scan_rtx (insn
, &XEXP (x
, i
), cl
, action
, type
, 0);
722 else if (fmt
[i
] == 'E')
723 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
724 scan_rtx (insn
, &XVECEXP (x
, i
, j
), cl
, action
, type
, 0);
728 /* Build def/use chain. */
730 static struct du_chain
*
731 build_def_use (basic_block bb
)
735 open_chains
= closed_chains
= NULL
;
737 for (insn
= BB_HEAD (bb
); ; insn
= NEXT_INSN (insn
))
743 rtx old_operands
[MAX_RECOG_OPERANDS
];
744 rtx old_dups
[MAX_DUP_OPERANDS
];
749 /* Process the insn, determining its effect on the def-use
750 chains. We perform the following steps with the register
751 references in the insn:
752 (1) Any read that overlaps an open chain, but doesn't exactly
753 match, causes that chain to be closed. We can't deal
755 (2) Any read outside an operand causes any chain it overlaps
756 with to be closed, since we can't replace it.
757 (3) Any read inside an operand is added if there's already
758 an open chain for it.
759 (4) For any REG_DEAD note we find, close open chains that
761 (5) For any write we find, close open chains that overlap it.
762 (6) For any write we find in an operand, make a new chain.
763 (7) For any REG_UNUSED, close any chains we just opened. */
765 icode
= recog_memoized (insn
);
767 if (! constrain_operands (1))
768 fatal_insn_not_found (insn
);
769 preprocess_constraints ();
770 alt
= which_alternative
;
771 n_ops
= recog_data
.n_operands
;
773 /* Simplify the code below by rewriting things to reflect
774 matching constraints. Also promote OP_OUT to OP_INOUT
775 in predicated instructions. */
777 predicated
= GET_CODE (PATTERN (insn
)) == COND_EXEC
;
778 for (i
= 0; i
< n_ops
; ++i
)
780 int matches
= recog_op_alt
[i
][alt
].matches
;
782 recog_op_alt
[i
][alt
].cl
= recog_op_alt
[matches
][alt
].cl
;
783 if (matches
>= 0 || recog_op_alt
[i
][alt
].matched
>= 0
784 || (predicated
&& recog_data
.operand_type
[i
] == OP_OUT
))
785 recog_data
.operand_type
[i
] = OP_INOUT
;
788 /* Step 1: Close chains for which we have overlapping reads. */
789 for (i
= 0; i
< n_ops
; i
++)
790 scan_rtx (insn
, recog_data
.operand_loc
[i
],
791 NO_REGS
, terminate_overlapping_read
,
792 recog_data
.operand_type
[i
], 0);
794 /* Step 2: Close chains for which we have reads outside operands.
795 We do this by munging all operands into CC0, and closing
796 everything remaining. */
798 for (i
= 0; i
< n_ops
; i
++)
800 old_operands
[i
] = recog_data
.operand
[i
];
801 /* Don't squash match_operator or match_parallel here, since
802 we don't know that all of the contained registers are
803 reachable by proper operands. */
804 if (recog_data
.constraints
[i
][0] == '\0')
806 *recog_data
.operand_loc
[i
] = cc0_rtx
;
808 for (i
= 0; i
< recog_data
.n_dups
; i
++)
810 old_dups
[i
] = *recog_data
.dup_loc
[i
];
811 *recog_data
.dup_loc
[i
] = cc0_rtx
;
814 scan_rtx (insn
, &PATTERN (insn
), NO_REGS
, terminate_all_read
,
817 for (i
= 0; i
< recog_data
.n_dups
; i
++)
818 *recog_data
.dup_loc
[i
] = old_dups
[i
];
819 for (i
= 0; i
< n_ops
; i
++)
820 *recog_data
.operand_loc
[i
] = old_operands
[i
];
822 /* Step 2B: Can't rename function call argument registers. */
823 if (CALL_P (insn
) && CALL_INSN_FUNCTION_USAGE (insn
))
824 scan_rtx (insn
, &CALL_INSN_FUNCTION_USAGE (insn
),
825 NO_REGS
, terminate_all_read
, OP_IN
, 0);
827 /* Step 2C: Can't rename asm operands that were originally
829 if (asm_noperands (PATTERN (insn
)) > 0)
830 for (i
= 0; i
< n_ops
; i
++)
832 rtx
*loc
= recog_data
.operand_loc
[i
];
836 && REGNO (op
) == ORIGINAL_REGNO (op
)
837 && (recog_data
.operand_type
[i
] == OP_IN
838 || recog_data
.operand_type
[i
] == OP_INOUT
))
839 scan_rtx (insn
, loc
, NO_REGS
, terminate_all_read
, OP_IN
, 0);
842 /* Step 3: Append to chains for reads inside operands. */
843 for (i
= 0; i
< n_ops
+ recog_data
.n_dups
; i
++)
845 int opn
= i
< n_ops
? i
: recog_data
.dup_num
[i
- n_ops
];
846 rtx
*loc
= (i
< n_ops
847 ? recog_data
.operand_loc
[opn
]
848 : recog_data
.dup_loc
[i
- n_ops
]);
849 enum reg_class cl
= recog_op_alt
[opn
][alt
].cl
;
850 enum op_type type
= recog_data
.operand_type
[opn
];
852 /* Don't scan match_operand here, since we've no reg class
853 information to pass down. Any operands that we could
854 substitute in will be represented elsewhere. */
855 if (recog_data
.constraints
[opn
][0] == '\0')
858 if (recog_op_alt
[opn
][alt
].is_address
)
859 scan_rtx_address (insn
, loc
, cl
, mark_read
, VOIDmode
);
861 scan_rtx (insn
, loc
, cl
, mark_read
, type
, 0);
864 /* Step 3B: Record updates for regs in REG_INC notes, and
865 source regs in REG_FRAME_RELATED_EXPR notes. */
866 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
867 if (REG_NOTE_KIND (note
) == REG_INC
868 || REG_NOTE_KIND (note
) == REG_FRAME_RELATED_EXPR
)
869 scan_rtx (insn
, &XEXP (note
, 0), ALL_REGS
, mark_read
,
872 /* Step 4: Close chains for registers that die here. */
873 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
874 if (REG_NOTE_KIND (note
) == REG_DEAD
)
875 scan_rtx (insn
, &XEXP (note
, 0), NO_REGS
, terminate_dead
,
878 /* Step 4B: If this is a call, any chain live at this point
879 requires a caller-saved reg. */
883 for (p
= open_chains
; p
; p
= p
->next_chain
)
884 p
->need_caller_save_reg
= 1;
887 /* Step 5: Close open chains that overlap writes. Similar to
888 step 2, we hide in-out operands, since we do not want to
889 close these chains. */
891 for (i
= 0; i
< n_ops
; i
++)
893 old_operands
[i
] = recog_data
.operand
[i
];
894 if (recog_data
.operand_type
[i
] == OP_INOUT
)
895 *recog_data
.operand_loc
[i
] = cc0_rtx
;
897 for (i
= 0; i
< recog_data
.n_dups
; i
++)
899 int opn
= recog_data
.dup_num
[i
];
900 old_dups
[i
] = *recog_data
.dup_loc
[i
];
901 if (recog_data
.operand_type
[opn
] == OP_INOUT
)
902 *recog_data
.dup_loc
[i
] = cc0_rtx
;
905 scan_rtx (insn
, &PATTERN (insn
), NO_REGS
, terminate_write
, OP_IN
, 0);
907 for (i
= 0; i
< recog_data
.n_dups
; i
++)
908 *recog_data
.dup_loc
[i
] = old_dups
[i
];
909 for (i
= 0; i
< n_ops
; i
++)
910 *recog_data
.operand_loc
[i
] = old_operands
[i
];
912 /* Step 6: Begin new chains for writes inside operands. */
913 /* ??? Many targets have output constraints on the SET_DEST
914 of a call insn, which is stupid, since these are certainly
915 ABI defined hard registers. Don't change calls at all.
916 Similarly take special care for asm statement that originally
917 referenced hard registers. */
918 if (asm_noperands (PATTERN (insn
)) > 0)
920 for (i
= 0; i
< n_ops
; i
++)
921 if (recog_data
.operand_type
[i
] == OP_OUT
)
923 rtx
*loc
= recog_data
.operand_loc
[i
];
925 enum reg_class cl
= recog_op_alt
[i
][alt
].cl
;
928 && REGNO (op
) == ORIGINAL_REGNO (op
))
931 scan_rtx (insn
, loc
, cl
, mark_write
, OP_OUT
,
932 recog_op_alt
[i
][alt
].earlyclobber
);
935 else if (!CALL_P (insn
))
936 for (i
= 0; i
< n_ops
+ recog_data
.n_dups
; i
++)
938 int opn
= i
< n_ops
? i
: recog_data
.dup_num
[i
- n_ops
];
939 rtx
*loc
= (i
< n_ops
940 ? recog_data
.operand_loc
[opn
]
941 : recog_data
.dup_loc
[i
- n_ops
]);
942 enum reg_class cl
= recog_op_alt
[opn
][alt
].cl
;
944 if (recog_data
.operand_type
[opn
] == OP_OUT
)
945 scan_rtx (insn
, loc
, cl
, mark_write
, OP_OUT
,
946 recog_op_alt
[opn
][alt
].earlyclobber
);
949 /* Step 6B: Record destination regs in REG_FRAME_RELATED_EXPR
951 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
952 if (REG_NOTE_KIND (note
) == REG_FRAME_RELATED_EXPR
)
953 scan_rtx (insn
, &XEXP (note
, 0), ALL_REGS
, mark_access
,
956 /* Step 7: Close chains for registers that were never
958 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
959 if (REG_NOTE_KIND (note
) == REG_UNUSED
)
960 scan_rtx (insn
, &XEXP (note
, 0), NO_REGS
, terminate_dead
,
963 if (insn
== BB_END (bb
))
967 /* Since we close every chain when we find a REG_DEAD note, anything that
968 is still open lives past the basic block, so it can't be renamed. */
969 return closed_chains
;
972 /* Dump all def/use chains in CHAINS to DUMP_FILE. They are
973 printed in reverse order as that's how we build them. */
976 dump_def_use_chain (struct du_chain
*chains
)
980 struct du_chain
*this = chains
;
981 int r
= REGNO (*this->loc
);
982 int nregs
= hard_regno_nregs
[r
][GET_MODE (*this->loc
)];
983 fprintf (dump_file
, "Register %s (%d):", reg_names
[r
], nregs
);
986 fprintf (dump_file
, " %d [%s]", INSN_UID (this->insn
),
987 reg_class_names
[this->cl
]);
988 this = this->next_use
;
990 fprintf (dump_file
, "\n");
991 chains
= chains
->next_chain
;
995 /* The following code does forward propagation of hard register copies.
996 The object is to eliminate as many dependencies as possible, so that
997 we have the most scheduling freedom. As a side effect, we also clean
998 up some silly register allocation decisions made by reload. This
999 code may be obsoleted by a new register allocator. */
1001 /* For each register, we have a list of registers that contain the same
1002 value. The OLDEST_REGNO field points to the head of the list, and
1003 the NEXT_REGNO field runs through the list. The MODE field indicates
1004 what mode the data is known to be in; this field is VOIDmode when the
1005 register is not known to contain valid data. */
1007 struct value_data_entry
1009 enum machine_mode mode
;
1010 unsigned int oldest_regno
;
1011 unsigned int next_regno
;
1016 struct value_data_entry e
[FIRST_PSEUDO_REGISTER
];
1017 unsigned int max_value_regs
;
1020 static void kill_value_one_regno (unsigned, struct value_data
*);
1021 static void kill_value_regno (unsigned, unsigned, struct value_data
*);
1022 static void kill_value (rtx
, struct value_data
*);
1023 static void set_value_regno (unsigned, enum machine_mode
, struct value_data
*);
1024 static void init_value_data (struct value_data
*);
1025 static void kill_clobbered_value (rtx
, const_rtx
, void *);
1026 static void kill_set_value (rtx
, const_rtx
, void *);
1027 static int kill_autoinc_value (rtx
*, void *);
1028 static void copy_value (rtx
, rtx
, struct value_data
*);
1029 static bool mode_change_ok (enum machine_mode
, enum machine_mode
,
1031 static rtx
maybe_mode_change (enum machine_mode
, enum machine_mode
,
1032 enum machine_mode
, unsigned int, unsigned int);
1033 static rtx
find_oldest_value_reg (enum reg_class
, rtx
, struct value_data
*);
1034 static bool replace_oldest_value_reg (rtx
*, enum reg_class
, rtx
,
1035 struct value_data
*);
1036 static bool replace_oldest_value_addr (rtx
*, enum reg_class
,
1037 enum machine_mode
, rtx
,
1038 struct value_data
*);
1039 static bool replace_oldest_value_mem (rtx
, rtx
, struct value_data
*);
1040 static bool copyprop_hardreg_forward_1 (basic_block
, struct value_data
*);
1041 extern void debug_value_data (struct value_data
*);
1042 #ifdef ENABLE_CHECKING
1043 static void validate_value_data (struct value_data
*);
1046 /* Kill register REGNO. This involves removing it from any value
1047 lists, and resetting the value mode to VOIDmode. This is only a
1048 helper function; it does not handle any hard registers overlapping
1052 kill_value_one_regno (unsigned int regno
, struct value_data
*vd
)
1054 unsigned int i
, next
;
1056 if (vd
->e
[regno
].oldest_regno
!= regno
)
1058 for (i
= vd
->e
[regno
].oldest_regno
;
1059 vd
->e
[i
].next_regno
!= regno
;
1060 i
= vd
->e
[i
].next_regno
)
1062 vd
->e
[i
].next_regno
= vd
->e
[regno
].next_regno
;
1064 else if ((next
= vd
->e
[regno
].next_regno
) != INVALID_REGNUM
)
1066 for (i
= next
; i
!= INVALID_REGNUM
; i
= vd
->e
[i
].next_regno
)
1067 vd
->e
[i
].oldest_regno
= next
;
1070 vd
->e
[regno
].mode
= VOIDmode
;
1071 vd
->e
[regno
].oldest_regno
= regno
;
1072 vd
->e
[regno
].next_regno
= INVALID_REGNUM
;
1074 #ifdef ENABLE_CHECKING
1075 validate_value_data (vd
);
1079 /* Kill the value in register REGNO for NREGS, and any other registers
1080 whose values overlap. */
1083 kill_value_regno (unsigned int regno
, unsigned int nregs
,
1084 struct value_data
*vd
)
1088 /* Kill the value we're told to kill. */
1089 for (j
= 0; j
< nregs
; ++j
)
1090 kill_value_one_regno (regno
+ j
, vd
);
1092 /* Kill everything that overlapped what we're told to kill. */
1093 if (regno
< vd
->max_value_regs
)
1096 j
= regno
- vd
->max_value_regs
;
1097 for (; j
< regno
; ++j
)
1100 if (vd
->e
[j
].mode
== VOIDmode
)
1102 n
= hard_regno_nregs
[j
][vd
->e
[j
].mode
];
1104 for (i
= 0; i
< n
; ++i
)
1105 kill_value_one_regno (j
+ i
, vd
);
1109 /* Kill X. This is a convenience function wrapping kill_value_regno
1110 so that we mind the mode the register is in. */
1113 kill_value (rtx x
, struct value_data
*vd
)
1117 if (GET_CODE (x
) == SUBREG
)
1119 x
= simplify_subreg (GET_MODE (x
), SUBREG_REG (x
),
1120 GET_MODE (SUBREG_REG (x
)), SUBREG_BYTE (x
));
1122 x
= SUBREG_REG (orig_rtx
);
1126 unsigned int regno
= REGNO (x
);
1127 unsigned int n
= hard_regno_nregs
[regno
][GET_MODE (x
)];
1129 kill_value_regno (regno
, n
, vd
);
1133 /* Remember that REGNO is valid in MODE. */
1136 set_value_regno (unsigned int regno
, enum machine_mode mode
,
1137 struct value_data
*vd
)
1141 vd
->e
[regno
].mode
= mode
;
1143 nregs
= hard_regno_nregs
[regno
][mode
];
1144 if (nregs
> vd
->max_value_regs
)
1145 vd
->max_value_regs
= nregs
;
1148 /* Initialize VD such that there are no known relationships between regs. */
1151 init_value_data (struct value_data
*vd
)
1154 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1156 vd
->e
[i
].mode
= VOIDmode
;
1157 vd
->e
[i
].oldest_regno
= i
;
1158 vd
->e
[i
].next_regno
= INVALID_REGNUM
;
1160 vd
->max_value_regs
= 0;
1163 /* Called through note_stores. If X is clobbered, kill its value. */
1166 kill_clobbered_value (rtx x
, const_rtx set
, void *data
)
1168 struct value_data
*vd
= data
;
1169 if (GET_CODE (set
) == CLOBBER
)
1173 /* Called through note_stores. If X is set, not clobbered, kill its
1174 current value and install it as the root of its own value list. */
1177 kill_set_value (rtx x
, const_rtx set
, void *data
)
1179 struct value_data
*vd
= data
;
1180 if (GET_CODE (set
) != CLOBBER
)
1184 set_value_regno (REGNO (x
), GET_MODE (x
), vd
);
1188 /* Called through for_each_rtx. Kill any register used as the base of an
1189 auto-increment expression, and install that register as the root of its
1193 kill_autoinc_value (rtx
*px
, void *data
)
1196 struct value_data
*vd
= data
;
1198 if (GET_RTX_CLASS (GET_CODE (x
)) == RTX_AUTOINC
)
1202 set_value_regno (REGNO (x
), Pmode
, vd
);
1209 /* Assert that SRC has been copied to DEST. Adjust the data structures
1210 to reflect that SRC contains an older copy of the shared value. */
1213 copy_value (rtx dest
, rtx src
, struct value_data
*vd
)
1215 unsigned int dr
= REGNO (dest
);
1216 unsigned int sr
= REGNO (src
);
1217 unsigned int dn
, sn
;
1220 /* ??? At present, it's possible to see noop sets. It'd be nice if
1221 this were cleaned up beforehand... */
1225 /* Do not propagate copies to the stack pointer, as that can leave
1226 memory accesses with no scheduling dependency on the stack update. */
1227 if (dr
== STACK_POINTER_REGNUM
)
1230 /* Likewise with the frame pointer, if we're using one. */
1231 if (frame_pointer_needed
&& dr
== HARD_FRAME_POINTER_REGNUM
)
1234 /* Do not propagate copies to fixed or global registers, patterns
1235 can be relying to see particular fixed register or users can
1236 expect the chosen global register in asm. */
1237 if (fixed_regs
[dr
] || global_regs
[dr
])
1240 /* If SRC and DEST overlap, don't record anything. */
1241 dn
= hard_regno_nregs
[dr
][GET_MODE (dest
)];
1242 sn
= hard_regno_nregs
[sr
][GET_MODE (dest
)];
1243 if ((dr
> sr
&& dr
< sr
+ sn
)
1244 || (sr
> dr
&& sr
< dr
+ dn
))
1247 /* If SRC had no assigned mode (i.e. we didn't know it was live)
1248 assign it now and assume the value came from an input argument
1250 if (vd
->e
[sr
].mode
== VOIDmode
)
1251 set_value_regno (sr
, vd
->e
[dr
].mode
, vd
);
1253 /* If we are narrowing the input to a smaller number of hard regs,
1254 and it is in big endian, we are really extracting a high part.
1255 Since we generally associate a low part of a value with the value itself,
1256 we must not do the same for the high part.
1257 Note we can still get low parts for the same mode combination through
1258 a two-step copy involving differently sized hard regs.
1259 Assume hard regs fr* are 32 bits bits each, while r* are 64 bits each:
1260 (set (reg:DI r0) (reg:DI fr0))
1261 (set (reg:SI fr2) (reg:SI r0))
1262 loads the low part of (reg:DI fr0) - i.e. fr1 - into fr2, while:
1263 (set (reg:SI fr2) (reg:SI fr0))
1264 loads the high part of (reg:DI fr0) into fr2.
1266 We can't properly represent the latter case in our tables, so don't
1267 record anything then. */
1268 else if (sn
< (unsigned int) hard_regno_nregs
[sr
][vd
->e
[sr
].mode
]
1269 && (GET_MODE_SIZE (vd
->e
[sr
].mode
) > UNITS_PER_WORD
1270 ? WORDS_BIG_ENDIAN
: BYTES_BIG_ENDIAN
))
1273 /* If SRC had been assigned a mode narrower than the copy, we can't
1274 link DEST into the chain, because not all of the pieces of the
1275 copy came from oldest_regno. */
1276 else if (sn
> (unsigned int) hard_regno_nregs
[sr
][vd
->e
[sr
].mode
])
1279 /* Link DR at the end of the value chain used by SR. */
1281 vd
->e
[dr
].oldest_regno
= vd
->e
[sr
].oldest_regno
;
1283 for (i
= sr
; vd
->e
[i
].next_regno
!= INVALID_REGNUM
; i
= vd
->e
[i
].next_regno
)
1285 vd
->e
[i
].next_regno
= dr
;
1287 #ifdef ENABLE_CHECKING
1288 validate_value_data (vd
);
1292 /* Return true if a mode change from ORIG to NEW is allowed for REGNO. */
1295 mode_change_ok (enum machine_mode orig_mode
, enum machine_mode new_mode
,
1296 unsigned int regno ATTRIBUTE_UNUSED
)
1298 if (GET_MODE_SIZE (orig_mode
) < GET_MODE_SIZE (new_mode
))
1301 #ifdef CANNOT_CHANGE_MODE_CLASS
1302 return !REG_CANNOT_CHANGE_MODE_P (regno
, orig_mode
, new_mode
);
1308 /* Register REGNO was originally set in ORIG_MODE. It - or a copy of it -
1309 was copied in COPY_MODE to COPY_REGNO, and then COPY_REGNO was accessed
1311 Return a NEW_MODE rtx for REGNO if that's OK, otherwise return NULL_RTX. */
1314 maybe_mode_change (enum machine_mode orig_mode
, enum machine_mode copy_mode
,
1315 enum machine_mode new_mode
, unsigned int regno
,
1316 unsigned int copy_regno ATTRIBUTE_UNUSED
)
1318 if (orig_mode
== new_mode
)
1319 return gen_rtx_raw_REG (new_mode
, regno
);
1320 else if (mode_change_ok (orig_mode
, new_mode
, regno
))
1322 int copy_nregs
= hard_regno_nregs
[copy_regno
][copy_mode
];
1323 int use_nregs
= hard_regno_nregs
[copy_regno
][new_mode
];
1325 = GET_MODE_SIZE (copy_mode
) / copy_nregs
* (copy_nregs
- use_nregs
);
1327 = GET_MODE_SIZE (orig_mode
) - GET_MODE_SIZE (new_mode
) - copy_offset
;
1328 int byteoffset
= offset
% UNITS_PER_WORD
;
1329 int wordoffset
= offset
- byteoffset
;
1331 offset
= ((WORDS_BIG_ENDIAN
? wordoffset
: 0)
1332 + (BYTES_BIG_ENDIAN
? byteoffset
: 0));
1333 return gen_rtx_raw_REG (new_mode
,
1334 regno
+ subreg_regno_offset (regno
, orig_mode
,
1341 /* Find the oldest copy of the value contained in REGNO that is in
1342 register class CL and has mode MODE. If found, return an rtx
1343 of that oldest register, otherwise return NULL. */
1346 find_oldest_value_reg (enum reg_class cl
, rtx reg
, struct value_data
*vd
)
1348 unsigned int regno
= REGNO (reg
);
1349 enum machine_mode mode
= GET_MODE (reg
);
1352 /* If we are accessing REG in some mode other that what we set it in,
1353 make sure that the replacement is valid. In particular, consider
1354 (set (reg:DI r11) (...))
1355 (set (reg:SI r9) (reg:SI r11))
1356 (set (reg:SI r10) (...))
1357 (set (...) (reg:DI r9))
1358 Replacing r9 with r11 is invalid. */
1359 if (mode
!= vd
->e
[regno
].mode
)
1361 if (hard_regno_nregs
[regno
][mode
]
1362 > hard_regno_nregs
[regno
][vd
->e
[regno
].mode
])
1366 for (i
= vd
->e
[regno
].oldest_regno
; i
!= regno
; i
= vd
->e
[i
].next_regno
)
1368 enum machine_mode oldmode
= vd
->e
[i
].mode
;
1371 if (!in_hard_reg_set_p (reg_class_contents
[cl
], mode
, i
))
1374 new = maybe_mode_change (oldmode
, vd
->e
[regno
].mode
, mode
, i
, regno
);
1377 ORIGINAL_REGNO (new) = ORIGINAL_REGNO (reg
);
1378 REG_ATTRS (new) = REG_ATTRS (reg
);
1386 /* If possible, replace the register at *LOC with the oldest register
1387 in register class CL. Return true if successfully replaced. */
1390 replace_oldest_value_reg (rtx
*loc
, enum reg_class cl
, rtx insn
,
1391 struct value_data
*vd
)
1393 rtx
new = find_oldest_value_reg (cl
, *loc
, vd
);
1397 fprintf (dump_file
, "insn %u: replaced reg %u with %u\n",
1398 INSN_UID (insn
), REGNO (*loc
), REGNO (new));
1400 validate_change (insn
, loc
, new, 1);
1406 /* Similar to replace_oldest_value_reg, but *LOC contains an address.
1407 Adapted from find_reloads_address_1. CL is INDEX_REG_CLASS or
1408 BASE_REG_CLASS depending on how the register is being considered. */
1411 replace_oldest_value_addr (rtx
*loc
, enum reg_class cl
,
1412 enum machine_mode mode
, rtx insn
,
1413 struct value_data
*vd
)
1416 RTX_CODE code
= GET_CODE (x
);
1419 bool changed
= false;
1425 rtx orig_op0
= XEXP (x
, 0);
1426 rtx orig_op1
= XEXP (x
, 1);
1427 RTX_CODE code0
= GET_CODE (orig_op0
);
1428 RTX_CODE code1
= GET_CODE (orig_op1
);
1433 enum rtx_code index_code
= SCRATCH
;
1435 if (GET_CODE (op0
) == SUBREG
)
1437 op0
= SUBREG_REG (op0
);
1438 code0
= GET_CODE (op0
);
1441 if (GET_CODE (op1
) == SUBREG
)
1443 op1
= SUBREG_REG (op1
);
1444 code1
= GET_CODE (op1
);
1447 if (code0
== MULT
|| code0
== SIGN_EXTEND
|| code0
== TRUNCATE
1448 || code0
== ZERO_EXTEND
|| code1
== MEM
)
1450 locI
= &XEXP (x
, 0);
1451 locB
= &XEXP (x
, 1);
1452 index_code
= GET_CODE (*locI
);
1454 else if (code1
== MULT
|| code1
== SIGN_EXTEND
|| code1
== TRUNCATE
1455 || code1
== ZERO_EXTEND
|| code0
== MEM
)
1457 locI
= &XEXP (x
, 1);
1458 locB
= &XEXP (x
, 0);
1459 index_code
= GET_CODE (*locI
);
1461 else if (code0
== CONST_INT
|| code0
== CONST
1462 || code0
== SYMBOL_REF
|| code0
== LABEL_REF
)
1464 locB
= &XEXP (x
, 1);
1465 index_code
= GET_CODE (XEXP (x
, 0));
1467 else if (code1
== CONST_INT
|| code1
== CONST
1468 || code1
== SYMBOL_REF
|| code1
== LABEL_REF
)
1470 locB
= &XEXP (x
, 0);
1471 index_code
= GET_CODE (XEXP (x
, 1));
1473 else if (code0
== REG
&& code1
== REG
)
1476 unsigned regno0
= REGNO (op0
), regno1
= REGNO (op1
);
1478 if (REGNO_OK_FOR_INDEX_P (regno0
)
1479 && regno_ok_for_base_p (regno1
, mode
, PLUS
, REG
))
1481 else if (REGNO_OK_FOR_INDEX_P (regno1
)
1482 && regno_ok_for_base_p (regno0
, mode
, PLUS
, REG
))
1484 else if (regno_ok_for_base_p (regno1
, mode
, PLUS
, REG
))
1486 else if (regno_ok_for_base_p (regno0
, mode
, PLUS
, REG
))
1488 else if (REGNO_OK_FOR_INDEX_P (regno1
))
1493 locI
= &XEXP (x
, index_op
);
1494 locB
= &XEXP (x
, !index_op
);
1495 index_code
= GET_CODE (*locI
);
1497 else if (code0
== REG
)
1499 locI
= &XEXP (x
, 0);
1500 locB
= &XEXP (x
, 1);
1501 index_code
= GET_CODE (*locI
);
1503 else if (code1
== REG
)
1505 locI
= &XEXP (x
, 1);
1506 locB
= &XEXP (x
, 0);
1507 index_code
= GET_CODE (*locI
);
1511 changed
|= replace_oldest_value_addr (locI
, INDEX_REG_CLASS
, mode
,
1514 changed
|= replace_oldest_value_addr (locB
,
1515 base_reg_class (mode
, PLUS
,
1530 return replace_oldest_value_mem (x
, insn
, vd
);
1533 return replace_oldest_value_reg (loc
, cl
, insn
, vd
);
1539 fmt
= GET_RTX_FORMAT (code
);
1540 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1543 changed
|= replace_oldest_value_addr (&XEXP (x
, i
), cl
, mode
,
1545 else if (fmt
[i
] == 'E')
1546 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
1547 changed
|= replace_oldest_value_addr (&XVECEXP (x
, i
, j
), cl
,
1554 /* Similar to replace_oldest_value_reg, but X contains a memory. */
1557 replace_oldest_value_mem (rtx x
, rtx insn
, struct value_data
*vd
)
1559 return replace_oldest_value_addr (&XEXP (x
, 0),
1560 base_reg_class (GET_MODE (x
), MEM
,
1562 GET_MODE (x
), insn
, vd
);
1565 /* Perform the forward copy propagation on basic block BB. */
1568 copyprop_hardreg_forward_1 (basic_block bb
, struct value_data
*vd
)
1570 bool changed
= false;
1573 for (insn
= BB_HEAD (bb
); ; insn
= NEXT_INSN (insn
))
1575 int n_ops
, i
, alt
, predicated
;
1576 bool is_asm
, any_replacements
;
1578 bool replaced
[MAX_RECOG_OPERANDS
];
1580 if (! INSN_P (insn
))
1582 if (insn
== BB_END (bb
))
1588 set
= single_set (insn
);
1589 extract_insn (insn
);
1590 if (! constrain_operands (1))
1591 fatal_insn_not_found (insn
);
1592 preprocess_constraints ();
1593 alt
= which_alternative
;
1594 n_ops
= recog_data
.n_operands
;
1595 is_asm
= asm_noperands (PATTERN (insn
)) >= 0;
1597 /* Simplify the code below by rewriting things to reflect
1598 matching constraints. Also promote OP_OUT to OP_INOUT
1599 in predicated instructions. */
1601 predicated
= GET_CODE (PATTERN (insn
)) == COND_EXEC
;
1602 for (i
= 0; i
< n_ops
; ++i
)
1604 int matches
= recog_op_alt
[i
][alt
].matches
;
1606 recog_op_alt
[i
][alt
].cl
= recog_op_alt
[matches
][alt
].cl
;
1607 if (matches
>= 0 || recog_op_alt
[i
][alt
].matched
>= 0
1608 || (predicated
&& recog_data
.operand_type
[i
] == OP_OUT
))
1609 recog_data
.operand_type
[i
] = OP_INOUT
;
1612 /* For each earlyclobber operand, zap the value data. */
1613 for (i
= 0; i
< n_ops
; i
++)
1614 if (recog_op_alt
[i
][alt
].earlyclobber
)
1615 kill_value (recog_data
.operand
[i
], vd
);
1617 /* Within asms, a clobber cannot overlap inputs or outputs.
1618 I wouldn't think this were true for regular insns, but
1619 scan_rtx treats them like that... */
1620 note_stores (PATTERN (insn
), kill_clobbered_value
, vd
);
1622 /* Kill all auto-incremented values. */
1623 /* ??? REG_INC is useless, since stack pushes aren't done that way. */
1624 for_each_rtx (&PATTERN (insn
), kill_autoinc_value
, vd
);
1626 /* Kill all early-clobbered operands. */
1627 for (i
= 0; i
< n_ops
; i
++)
1628 if (recog_op_alt
[i
][alt
].earlyclobber
)
1629 kill_value (recog_data
.operand
[i
], vd
);
1631 /* Special-case plain move instructions, since we may well
1632 be able to do the move from a different register class. */
1633 if (set
&& REG_P (SET_SRC (set
)))
1635 rtx src
= SET_SRC (set
);
1636 unsigned int regno
= REGNO (src
);
1637 enum machine_mode mode
= GET_MODE (src
);
1641 /* If we are accessing SRC in some mode other that what we
1642 set it in, make sure that the replacement is valid. */
1643 if (mode
!= vd
->e
[regno
].mode
)
1645 if (hard_regno_nregs
[regno
][mode
]
1646 > hard_regno_nregs
[regno
][vd
->e
[regno
].mode
])
1647 goto no_move_special_case
;
1650 /* If the destination is also a register, try to find a source
1651 register in the same class. */
1652 if (REG_P (SET_DEST (set
)))
1654 new = find_oldest_value_reg (REGNO_REG_CLASS (regno
), src
, vd
);
1655 if (new && validate_change (insn
, &SET_SRC (set
), new, 0))
1659 "insn %u: replaced reg %u with %u\n",
1660 INSN_UID (insn
), regno
, REGNO (new));
1662 goto did_replacement
;
1666 /* Otherwise, try all valid registers and see if its valid. */
1667 for (i
= vd
->e
[regno
].oldest_regno
; i
!= regno
;
1668 i
= vd
->e
[i
].next_regno
)
1670 new = maybe_mode_change (vd
->e
[i
].mode
, vd
->e
[regno
].mode
,
1672 if (new != NULL_RTX
)
1674 if (validate_change (insn
, &SET_SRC (set
), new, 0))
1676 ORIGINAL_REGNO (new) = ORIGINAL_REGNO (src
);
1677 REG_ATTRS (new) = REG_ATTRS (src
);
1680 "insn %u: replaced reg %u with %u\n",
1681 INSN_UID (insn
), regno
, REGNO (new));
1683 goto did_replacement
;
1688 no_move_special_case
:
1690 any_replacements
= false;
1692 /* For each input operand, replace a hard register with the
1693 eldest live copy that's in an appropriate register class. */
1694 for (i
= 0; i
< n_ops
; i
++)
1696 replaced
[i
] = false;
1698 /* Don't scan match_operand here, since we've no reg class
1699 information to pass down. Any operands that we could
1700 substitute in will be represented elsewhere. */
1701 if (recog_data
.constraints
[i
][0] == '\0')
1704 /* Don't replace in asms intentionally referencing hard regs. */
1705 if (is_asm
&& REG_P (recog_data
.operand
[i
])
1706 && (REGNO (recog_data
.operand
[i
])
1707 == ORIGINAL_REGNO (recog_data
.operand
[i
])))
1710 if (recog_data
.operand_type
[i
] == OP_IN
)
1712 if (recog_op_alt
[i
][alt
].is_address
)
1714 = replace_oldest_value_addr (recog_data
.operand_loc
[i
],
1715 recog_op_alt
[i
][alt
].cl
,
1716 VOIDmode
, insn
, vd
);
1717 else if (REG_P (recog_data
.operand
[i
]))
1719 = replace_oldest_value_reg (recog_data
.operand_loc
[i
],
1720 recog_op_alt
[i
][alt
].cl
,
1722 else if (MEM_P (recog_data
.operand
[i
]))
1723 replaced
[i
] = replace_oldest_value_mem (recog_data
.operand
[i
],
1726 else if (MEM_P (recog_data
.operand
[i
]))
1727 replaced
[i
] = replace_oldest_value_mem (recog_data
.operand
[i
],
1730 /* If we performed any replacement, update match_dups. */
1736 new = *recog_data
.operand_loc
[i
];
1737 recog_data
.operand
[i
] = new;
1738 for (j
= 0; j
< recog_data
.n_dups
; j
++)
1739 if (recog_data
.dup_num
[j
] == i
)
1740 validate_unshare_change (insn
, recog_data
.dup_loc
[j
], new, 1);
1742 any_replacements
= true;
1746 if (any_replacements
)
1748 if (! apply_change_group ())
1750 for (i
= 0; i
< n_ops
; i
++)
1753 rtx old
= *recog_data
.operand_loc
[i
];
1754 recog_data
.operand
[i
] = old
;
1759 "insn %u: reg replacements not verified\n",
1767 /* Clobber call-clobbered registers. */
1769 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1770 if (TEST_HARD_REG_BIT (regs_invalidated_by_call
, i
))
1771 kill_value_regno (i
, 1, vd
);
1773 /* Notice stores. */
1774 note_stores (PATTERN (insn
), kill_set_value
, vd
);
1776 /* Notice copies. */
1777 if (set
&& REG_P (SET_DEST (set
)) && REG_P (SET_SRC (set
)))
1778 copy_value (SET_DEST (set
), SET_SRC (set
), vd
);
1780 if (insn
== BB_END (bb
))
1787 /* Main entry point for the forward copy propagation optimization. */
1790 copyprop_hardreg_forward (void)
1792 struct value_data
*all_vd
;
1796 all_vd
= XNEWVEC (struct value_data
, last_basic_block
);
1798 visited
= sbitmap_alloc (last_basic_block
);
1799 sbitmap_zero (visited
);
1803 SET_BIT (visited
, bb
->index
);
1805 /* If a block has a single predecessor, that we've already
1806 processed, begin with the value data that was live at
1807 the end of the predecessor block. */
1808 /* ??? Ought to use more intelligent queuing of blocks. */
1809 if (single_pred_p (bb
)
1810 && TEST_BIT (visited
, single_pred (bb
)->index
)
1811 && ! (single_pred_edge (bb
)->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
)))
1812 all_vd
[bb
->index
] = all_vd
[single_pred (bb
)->index
];
1814 init_value_data (all_vd
+ bb
->index
);
1816 copyprop_hardreg_forward_1 (bb
, all_vd
+ bb
->index
);
1819 sbitmap_free (visited
);
1823 /* Dump the value chain data to stderr. */
1826 debug_value_data (struct value_data
*vd
)
1831 CLEAR_HARD_REG_SET (set
);
1833 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1834 if (vd
->e
[i
].oldest_regno
== i
)
1836 if (vd
->e
[i
].mode
== VOIDmode
)
1838 if (vd
->e
[i
].next_regno
!= INVALID_REGNUM
)
1839 fprintf (stderr
, "[%u] Bad next_regno for empty chain (%u)\n",
1840 i
, vd
->e
[i
].next_regno
);
1844 SET_HARD_REG_BIT (set
, i
);
1845 fprintf (stderr
, "[%u %s] ", i
, GET_MODE_NAME (vd
->e
[i
].mode
));
1847 for (j
= vd
->e
[i
].next_regno
;
1848 j
!= INVALID_REGNUM
;
1849 j
= vd
->e
[j
].next_regno
)
1851 if (TEST_HARD_REG_BIT (set
, j
))
1853 fprintf (stderr
, "[%u] Loop in regno chain\n", j
);
1857 if (vd
->e
[j
].oldest_regno
!= i
)
1859 fprintf (stderr
, "[%u] Bad oldest_regno (%u)\n",
1860 j
, vd
->e
[j
].oldest_regno
);
1863 SET_HARD_REG_BIT (set
, j
);
1864 fprintf (stderr
, "[%u %s] ", j
, GET_MODE_NAME (vd
->e
[j
].mode
));
1866 fputc ('\n', stderr
);
1869 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1870 if (! TEST_HARD_REG_BIT (set
, i
)
1871 && (vd
->e
[i
].mode
!= VOIDmode
1872 || vd
->e
[i
].oldest_regno
!= i
1873 || vd
->e
[i
].next_regno
!= INVALID_REGNUM
))
1874 fprintf (stderr
, "[%u] Non-empty reg in chain (%s %u %i)\n",
1875 i
, GET_MODE_NAME (vd
->e
[i
].mode
), vd
->e
[i
].oldest_regno
,
1876 vd
->e
[i
].next_regno
);
1879 #ifdef ENABLE_CHECKING
1881 validate_value_data (struct value_data
*vd
)
1886 CLEAR_HARD_REG_SET (set
);
1888 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1889 if (vd
->e
[i
].oldest_regno
== i
)
1891 if (vd
->e
[i
].mode
== VOIDmode
)
1893 if (vd
->e
[i
].next_regno
!= INVALID_REGNUM
)
1894 internal_error ("validate_value_data: [%u] Bad next_regno for empty chain (%u)",
1895 i
, vd
->e
[i
].next_regno
);
1899 SET_HARD_REG_BIT (set
, i
);
1901 for (j
= vd
->e
[i
].next_regno
;
1902 j
!= INVALID_REGNUM
;
1903 j
= vd
->e
[j
].next_regno
)
1905 if (TEST_HARD_REG_BIT (set
, j
))
1906 internal_error ("validate_value_data: Loop in regno chain (%u)",
1908 if (vd
->e
[j
].oldest_regno
!= i
)
1909 internal_error ("validate_value_data: [%u] Bad oldest_regno (%u)",
1910 j
, vd
->e
[j
].oldest_regno
);
1912 SET_HARD_REG_BIT (set
, j
);
1916 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1917 if (! TEST_HARD_REG_BIT (set
, i
)
1918 && (vd
->e
[i
].mode
!= VOIDmode
1919 || vd
->e
[i
].oldest_regno
!= i
1920 || vd
->e
[i
].next_regno
!= INVALID_REGNUM
))
1921 internal_error ("validate_value_data: [%u] Non-empty reg in chain (%s %u %i)",
1922 i
, GET_MODE_NAME (vd
->e
[i
].mode
), vd
->e
[i
].oldest_regno
,
1923 vd
->e
[i
].next_regno
);
1928 gate_handle_regrename (void)
1930 return (optimize
> 0 && (flag_rename_registers
));
1934 /* Run the regrename and cprop passes. */
1936 rest_of_handle_regrename (void)
1938 regrename_optimize ();
1942 struct tree_opt_pass pass_regrename
=
1945 gate_handle_regrename
, /* gate */
1946 rest_of_handle_regrename
, /* execute */
1949 0, /* static_pass_number */
1950 TV_RENAME_REGISTERS
, /* tv_id */
1951 0, /* properties_required */
1952 0, /* properties_provided */
1953 0, /* properties_destroyed */
1954 0, /* todo_flags_start */
1956 TODO_dump_func
, /* todo_flags_finish */
1961 gate_handle_cprop (void)
1963 return (optimize
> 0 && (flag_cprop_registers
));
1967 /* Run the regrename and cprop passes. */
1969 rest_of_handle_cprop (void)
1971 copyprop_hardreg_forward ();
1975 struct tree_opt_pass pass_cprop_hardreg
=
1977 "cprop_hardreg", /* name */
1978 gate_handle_cprop
, /* gate */
1979 rest_of_handle_cprop
, /* execute */
1982 0, /* static_pass_number */
1983 TV_RENAME_REGISTERS
, /* tv_id */
1984 0, /* properties_required */
1985 0, /* properties_provided */
1986 0, /* properties_destroyed */
1987 0, /* todo_flags_start */
1988 TODO_dump_func
, /* todo_flags_finish */