1 /* Register renaming for the GNU compiler.
2 Copyright (C) 2000, 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
13 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
14 License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING. If not, write to the Free
18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
23 #include "coretypes.h"
27 #include "insn-config.h"
29 #include "hard-reg-set.h"
30 #include "basic-block.h"
39 static const char *const reg_class_names
[] = REG_CLASS_NAMES
;
43 struct du_chain
*next_chain
;
44 struct du_chain
*next_use
;
48 ENUM_BITFIELD(reg_class
) cl
: 16;
49 unsigned int need_caller_save_reg
:1;
50 unsigned int earlyclobber
:1;
56 terminate_overlapping_read
,
63 static const char * const scan_actions_name
[] =
66 "terminate_overlapping_read",
73 static struct obstack rename_obstack
;
75 static void do_replace (struct du_chain
*, int);
76 static void scan_rtx_reg (rtx
, rtx
*, enum reg_class
,
77 enum scan_actions
, enum op_type
, int);
78 static void scan_rtx_address (rtx
, rtx
*, enum reg_class
,
79 enum scan_actions
, enum machine_mode
);
80 static void scan_rtx (rtx
, rtx
*, enum reg_class
, enum scan_actions
,
82 static struct du_chain
*build_def_use (basic_block
);
83 static void dump_def_use_chain (struct du_chain
*);
84 static void note_sets (rtx
, rtx
, void *);
85 static void clear_dead_regs (HARD_REG_SET
*, enum machine_mode
, rtx
);
86 static void merge_overlapping_regs (basic_block
, HARD_REG_SET
*,
89 /* Called through note_stores from update_life. Find sets of registers, and
90 record them in *DATA (which is actually a HARD_REG_SET *). */
93 note_sets (rtx x
, rtx set ATTRIBUTE_UNUSED
, void *data
)
95 HARD_REG_SET
*pset
= (HARD_REG_SET
*) data
;
101 nregs
= hard_regno_nregs
[regno
][GET_MODE (x
)];
103 /* There must not be pseudos at this point. */
104 gcc_assert (regno
+ nregs
<= FIRST_PSEUDO_REGISTER
);
107 SET_HARD_REG_BIT (*pset
, regno
+ nregs
);
110 /* Clear all registers from *PSET for which a note of kind KIND can be found
111 in the list NOTES. */
114 clear_dead_regs (HARD_REG_SET
*pset
, enum machine_mode kind
, rtx notes
)
117 for (note
= notes
; note
; note
= XEXP (note
, 1))
118 if (REG_NOTE_KIND (note
) == kind
&& REG_P (XEXP (note
, 0)))
120 rtx reg
= XEXP (note
, 0);
121 unsigned int regno
= REGNO (reg
);
122 int nregs
= hard_regno_nregs
[regno
][GET_MODE (reg
)];
124 /* There must not be pseudos at this point. */
125 gcc_assert (regno
+ nregs
<= FIRST_PSEUDO_REGISTER
);
128 CLEAR_HARD_REG_BIT (*pset
, regno
+ nregs
);
132 /* For a def-use chain CHAIN in basic block B, find which registers overlap
133 its lifetime and set the corresponding bits in *PSET. */
136 merge_overlapping_regs (basic_block b
, HARD_REG_SET
*pset
,
137 struct du_chain
*chain
)
139 struct du_chain
*t
= chain
;
143 REG_SET_TO_HARD_REG_SET (live
, b
->global_live_at_start
);
147 /* Search forward until the next reference to the register to be
149 while (insn
!= t
->insn
)
153 clear_dead_regs (&live
, REG_DEAD
, REG_NOTES (insn
));
154 note_stores (PATTERN (insn
), note_sets
, (void *) &live
);
155 /* Only record currently live regs if we are inside the
158 IOR_HARD_REG_SET (*pset
, live
);
159 clear_dead_regs (&live
, REG_UNUSED
, REG_NOTES (insn
));
161 insn
= NEXT_INSN (insn
);
164 IOR_HARD_REG_SET (*pset
, live
);
166 /* For the last reference, also merge in all registers set in the
168 @@@ We only have take earlyclobbered sets into account. */
170 note_stores (PATTERN (insn
), note_sets
, (void *) pset
);
176 /* Perform register renaming on the current function. */
179 regrename_optimize (void)
181 int tick
[FIRST_PSEUDO_REGISTER
];
186 memset (tick
, 0, sizeof tick
);
188 gcc_obstack_init (&rename_obstack
);
189 first_obj
= obstack_alloc (&rename_obstack
, 0);
193 struct du_chain
*all_chains
= 0;
194 HARD_REG_SET unavailable
;
195 HARD_REG_SET regs_seen
;
197 CLEAR_HARD_REG_SET (unavailable
);
200 fprintf (dump_file
, "\nBasic block %d:\n", bb
->index
);
202 all_chains
= build_def_use (bb
);
205 dump_def_use_chain (all_chains
);
207 CLEAR_HARD_REG_SET (unavailable
);
208 /* Don't clobber traceback for noreturn functions. */
209 if (frame_pointer_needed
)
213 for (i
= hard_regno_nregs
[FRAME_POINTER_REGNUM
][Pmode
]; i
--;)
214 SET_HARD_REG_BIT (unavailable
, FRAME_POINTER_REGNUM
+ i
);
216 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
217 for (i
= hard_regno_nregs
[HARD_FRAME_POINTER_REGNUM
][Pmode
]; i
--;)
218 SET_HARD_REG_BIT (unavailable
, HARD_FRAME_POINTER_REGNUM
+ i
);
222 CLEAR_HARD_REG_SET (regs_seen
);
225 int new_reg
, best_new_reg
;
227 struct du_chain
*this = all_chains
;
228 struct du_chain
*tmp
, *last
;
229 HARD_REG_SET this_unavailable
;
230 int reg
= REGNO (*this->loc
);
233 all_chains
= this->next_chain
;
237 #if 0 /* This just disables optimization opportunities. */
238 /* Only rename once we've seen the reg more than once. */
239 if (! TEST_HARD_REG_BIT (regs_seen
, reg
))
241 SET_HARD_REG_BIT (regs_seen
, reg
);
246 if (fixed_regs
[reg
] || global_regs
[reg
]
247 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
248 || (frame_pointer_needed
&& reg
== HARD_FRAME_POINTER_REGNUM
)
250 || (frame_pointer_needed
&& reg
== FRAME_POINTER_REGNUM
)
255 COPY_HARD_REG_SET (this_unavailable
, unavailable
);
257 /* Find last entry on chain (which has the need_caller_save bit),
258 count number of uses, and narrow the set of registers we can
261 for (last
= this; last
->next_use
; last
= last
->next_use
)
264 IOR_COMPL_HARD_REG_SET (this_unavailable
,
265 reg_class_contents
[last
->cl
]);
270 IOR_COMPL_HARD_REG_SET (this_unavailable
,
271 reg_class_contents
[last
->cl
]);
273 if (this->need_caller_save_reg
)
274 IOR_HARD_REG_SET (this_unavailable
, call_used_reg_set
);
276 merge_overlapping_regs (bb
, &this_unavailable
, this);
278 /* Now potential_regs is a reasonable approximation, let's
279 have a closer look at each register still in there. */
280 for (new_reg
= 0; new_reg
< FIRST_PSEUDO_REGISTER
; new_reg
++)
282 int nregs
= hard_regno_nregs
[new_reg
][GET_MODE (*this->loc
)];
284 for (i
= nregs
- 1; i
>= 0; --i
)
285 if (TEST_HARD_REG_BIT (this_unavailable
, new_reg
+ i
)
286 || fixed_regs
[new_reg
+ i
]
287 || global_regs
[new_reg
+ i
]
288 /* Can't use regs which aren't saved by the prologue. */
289 || (! regs_ever_live
[new_reg
+ i
]
290 && ! call_used_regs
[new_reg
+ i
])
291 #ifdef LEAF_REGISTERS
292 /* We can't use a non-leaf register if we're in a
294 || (current_function_is_leaf
295 && !LEAF_REGISTERS
[new_reg
+ i
])
297 #ifdef HARD_REGNO_RENAME_OK
298 || ! HARD_REGNO_RENAME_OK (reg
+ i
, new_reg
+ i
)
305 /* See whether it accepts all modes that occur in
306 definition and uses. */
307 for (tmp
= this; tmp
; tmp
= tmp
->next_use
)
308 if (! HARD_REGNO_MODE_OK (new_reg
, GET_MODE (*tmp
->loc
))
309 || (tmp
->need_caller_save_reg
310 && ! (HARD_REGNO_CALL_PART_CLOBBERED
311 (reg
, GET_MODE (*tmp
->loc
)))
312 && (HARD_REGNO_CALL_PART_CLOBBERED
313 (new_reg
, GET_MODE (*tmp
->loc
)))))
317 if (tick
[best_new_reg
] > tick
[new_reg
])
318 best_new_reg
= new_reg
;
324 fprintf (dump_file
, "Register %s in insn %d",
325 reg_names
[reg
], INSN_UID (last
->insn
));
326 if (last
->need_caller_save_reg
)
327 fprintf (dump_file
, " crosses a call");
330 if (best_new_reg
== reg
)
332 tick
[reg
] = ++this_tick
;
334 fprintf (dump_file
, "; no available better choice\n");
338 do_replace (this, best_new_reg
);
339 tick
[best_new_reg
] = ++this_tick
;
340 regs_ever_live
[best_new_reg
] = 1;
343 fprintf (dump_file
, ", renamed as %s\n", reg_names
[best_new_reg
]);
346 obstack_free (&rename_obstack
, first_obj
);
349 obstack_free (&rename_obstack
, NULL
);
352 fputc ('\n', dump_file
);
354 count_or_remove_death_notes (NULL
, 1);
355 update_life_info (NULL
, UPDATE_LIFE_LOCAL
,
360 do_replace (struct du_chain
*chain
, int reg
)
364 unsigned int regno
= ORIGINAL_REGNO (*chain
->loc
);
365 struct reg_attrs
* attr
= REG_ATTRS (*chain
->loc
);
367 *chain
->loc
= gen_raw_REG (GET_MODE (*chain
->loc
), reg
);
368 if (regno
>= FIRST_PSEUDO_REGISTER
)
369 ORIGINAL_REGNO (*chain
->loc
) = regno
;
370 REG_ATTRS (*chain
->loc
) = attr
;
371 chain
= chain
->next_use
;
376 static struct du_chain
*open_chains
;
377 static struct du_chain
*closed_chains
;
380 scan_rtx_reg (rtx insn
, rtx
*loc
, enum reg_class cl
,
381 enum scan_actions action
, enum op_type type
, int earlyclobber
)
385 enum machine_mode mode
= GET_MODE (x
);
386 int this_regno
= REGNO (x
);
387 int this_nregs
= hard_regno_nregs
[this_regno
][mode
];
389 if (action
== mark_write
)
393 struct du_chain
*this
394 = obstack_alloc (&rename_obstack
, sizeof (struct du_chain
));
396 this->next_chain
= open_chains
;
400 this->need_caller_save_reg
= 0;
401 this->earlyclobber
= earlyclobber
;
407 if ((type
== OP_OUT
&& action
!= terminate_write
)
408 || (type
!= OP_OUT
&& action
== terminate_write
))
411 for (p
= &open_chains
; *p
;)
413 struct du_chain
*this = *p
;
415 /* Check if the chain has been terminated if it has then skip to
418 This can happen when we've already appended the location to
419 the chain in Step 3, but are trying to hide in-out operands
420 from terminate_write in Step 5. */
422 if (*this->loc
== cc0_rtx
)
423 p
= &this->next_chain
;
426 int regno
= REGNO (*this->loc
);
427 int nregs
= hard_regno_nregs
[regno
][GET_MODE (*this->loc
)];
428 int exact_match
= (regno
== this_regno
&& nregs
== this_nregs
);
430 if (regno
+ nregs
<= this_regno
431 || this_regno
+ this_nregs
<= regno
)
433 p
= &this->next_chain
;
437 if (action
== mark_read
)
439 gcc_assert (exact_match
);
441 /* ??? Class NO_REGS can happen if the md file makes use of
442 EXTRA_CONSTRAINTS to match registers. Which is arguably
443 wrong, but there we are. Since we know not what this may
444 be replaced with, terminate the chain. */
447 this = obstack_alloc (&rename_obstack
, sizeof (struct du_chain
));
449 this->next_chain
= (*p
)->next_chain
;
453 this->need_caller_save_reg
= 0;
461 if (action
!= terminate_overlapping_read
|| ! exact_match
)
463 struct du_chain
*next
= this->next_chain
;
465 /* Whether the terminated chain can be used for renaming
466 depends on the action and this being an exact match.
467 In either case, we remove this element from open_chains. */
469 if ((action
== terminate_dead
|| action
== terminate_write
)
472 this->next_chain
= closed_chains
;
473 closed_chains
= this;
476 "Closing chain %s at insn %d (%s)\n",
477 reg_names
[REGNO (*this->loc
)], INSN_UID (insn
),
478 scan_actions_name
[(int) action
]);
484 "Discarding chain %s at insn %d (%s)\n",
485 reg_names
[REGNO (*this->loc
)], INSN_UID (insn
),
486 scan_actions_name
[(int) action
]);
491 p
= &this->next_chain
;
496 /* Adapted from find_reloads_address_1. CL is INDEX_REG_CLASS or
497 BASE_REG_CLASS depending on how the register is being considered. */
500 scan_rtx_address (rtx insn
, rtx
*loc
, enum reg_class cl
,
501 enum scan_actions action
, enum machine_mode mode
)
504 RTX_CODE code
= GET_CODE (x
);
508 if (action
== mark_write
)
515 rtx orig_op0
= XEXP (x
, 0);
516 rtx orig_op1
= XEXP (x
, 1);
517 RTX_CODE code0
= GET_CODE (orig_op0
);
518 RTX_CODE code1
= GET_CODE (orig_op1
);
523 rtx
*locB_reg
= NULL
;
525 if (GET_CODE (op0
) == SUBREG
)
527 op0
= SUBREG_REG (op0
);
528 code0
= GET_CODE (op0
);
531 if (GET_CODE (op1
) == SUBREG
)
533 op1
= SUBREG_REG (op1
);
534 code1
= GET_CODE (op1
);
537 if (code0
== MULT
|| code0
== SIGN_EXTEND
|| code0
== TRUNCATE
538 || code0
== ZERO_EXTEND
|| code1
== MEM
)
543 else if (code1
== MULT
|| code1
== SIGN_EXTEND
|| code1
== TRUNCATE
544 || code1
== ZERO_EXTEND
|| code0
== MEM
)
549 else if (code0
== CONST_INT
|| code0
== CONST
550 || code0
== SYMBOL_REF
|| code0
== LABEL_REF
)
552 else if (code1
== CONST_INT
|| code1
== CONST
553 || code1
== SYMBOL_REF
|| code1
== LABEL_REF
)
555 else if (code0
== REG
&& code1
== REG
)
559 if (REG_OK_FOR_INDEX_P (op0
)
560 && REG_MODE_OK_FOR_REG_BASE_P (op1
, mode
))
562 else if (REG_OK_FOR_INDEX_P (op1
)
563 && REG_MODE_OK_FOR_REG_BASE_P (op0
, mode
))
565 else if (REG_MODE_OK_FOR_REG_BASE_P (op1
, mode
))
567 else if (REG_MODE_OK_FOR_REG_BASE_P (op0
, mode
))
569 else if (REG_OK_FOR_INDEX_P (op1
))
574 locI
= &XEXP (x
, index_op
);
575 locB_reg
= &XEXP (x
, !index_op
);
577 else if (code0
== REG
)
582 else if (code1
== REG
)
589 scan_rtx_address (insn
, locI
, INDEX_REG_CLASS
, action
, mode
);
591 scan_rtx_address (insn
, locB
, MODE_BASE_REG_CLASS (mode
), action
, mode
);
593 scan_rtx_address (insn
, locB_reg
, MODE_BASE_REG_REG_CLASS (mode
),
605 /* If the target doesn't claim to handle autoinc, this must be
606 something special, like a stack push. Kill this chain. */
607 action
= terminate_all_read
;
612 scan_rtx_address (insn
, &XEXP (x
, 0),
613 MODE_BASE_REG_CLASS (GET_MODE (x
)), action
,
618 scan_rtx_reg (insn
, loc
, cl
, action
, OP_IN
, 0);
625 fmt
= GET_RTX_FORMAT (code
);
626 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
629 scan_rtx_address (insn
, &XEXP (x
, i
), cl
, action
, mode
);
630 else if (fmt
[i
] == 'E')
631 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
632 scan_rtx_address (insn
, &XVECEXP (x
, i
, j
), cl
, action
, mode
);
637 scan_rtx (rtx insn
, rtx
*loc
, enum reg_class cl
,
638 enum scan_actions action
, enum op_type type
, int earlyclobber
)
642 enum rtx_code code
= GET_CODE (x
);
659 scan_rtx_reg (insn
, loc
, cl
, action
, type
, earlyclobber
);
663 scan_rtx_address (insn
, &XEXP (x
, 0),
664 MODE_BASE_REG_CLASS (GET_MODE (x
)), action
,
669 scan_rtx (insn
, &SET_SRC (x
), cl
, action
, OP_IN
, 0);
670 scan_rtx (insn
, &SET_DEST (x
), cl
, action
,
671 GET_CODE (PATTERN (insn
)) == COND_EXEC
? OP_INOUT
: OP_OUT
, 0);
674 case STRICT_LOW_PART
:
675 scan_rtx (insn
, &XEXP (x
, 0), cl
, action
, OP_INOUT
, earlyclobber
);
680 scan_rtx (insn
, &XEXP (x
, 0), cl
, action
,
681 type
== OP_IN
? OP_IN
: OP_INOUT
, earlyclobber
);
682 scan_rtx (insn
, &XEXP (x
, 1), cl
, action
, OP_IN
, 0);
683 scan_rtx (insn
, &XEXP (x
, 2), cl
, action
, OP_IN
, 0);
692 /* Should only happen inside MEM. */
696 scan_rtx (insn
, &SET_DEST (x
), cl
, action
,
697 GET_CODE (PATTERN (insn
)) == COND_EXEC
? OP_INOUT
: OP_OUT
, 0);
701 scan_rtx (insn
, &XEXP (x
, 0), cl
, action
, type
, 0);
703 scan_rtx (insn
, &XEXP (x
, 1), cl
, action
, type
, 0);
710 fmt
= GET_RTX_FORMAT (code
);
711 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
714 scan_rtx (insn
, &XEXP (x
, i
), cl
, action
, type
, 0);
715 else if (fmt
[i
] == 'E')
716 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
717 scan_rtx (insn
, &XVECEXP (x
, i
, j
), cl
, action
, type
, 0);
721 /* Build def/use chain. */
723 static struct du_chain
*
724 build_def_use (basic_block bb
)
728 open_chains
= closed_chains
= NULL
;
730 for (insn
= BB_HEAD (bb
); ; insn
= NEXT_INSN (insn
))
736 rtx old_operands
[MAX_RECOG_OPERANDS
];
737 rtx old_dups
[MAX_DUP_OPERANDS
];
742 /* Process the insn, determining its effect on the def-use
743 chains. We perform the following steps with the register
744 references in the insn:
745 (1) Any read that overlaps an open chain, but doesn't exactly
746 match, causes that chain to be closed. We can't deal
748 (2) Any read outside an operand causes any chain it overlaps
749 with to be closed, since we can't replace it.
750 (3) Any read inside an operand is added if there's already
751 an open chain for it.
752 (4) For any REG_DEAD note we find, close open chains that
754 (5) For any write we find, close open chains that overlap it.
755 (6) For any write we find in an operand, make a new chain.
756 (7) For any REG_UNUSED, close any chains we just opened. */
758 icode
= recog_memoized (insn
);
760 if (! constrain_operands (1))
761 fatal_insn_not_found (insn
);
762 preprocess_constraints ();
763 alt
= which_alternative
;
764 n_ops
= recog_data
.n_operands
;
766 /* Simplify the code below by rewriting things to reflect
767 matching constraints. Also promote OP_OUT to OP_INOUT
768 in predicated instructions. */
770 predicated
= GET_CODE (PATTERN (insn
)) == COND_EXEC
;
771 for (i
= 0; i
< n_ops
; ++i
)
773 int matches
= recog_op_alt
[i
][alt
].matches
;
775 recog_op_alt
[i
][alt
].cl
= recog_op_alt
[matches
][alt
].cl
;
776 if (matches
>= 0 || recog_op_alt
[i
][alt
].matched
>= 0
777 || (predicated
&& recog_data
.operand_type
[i
] == OP_OUT
))
778 recog_data
.operand_type
[i
] = OP_INOUT
;
781 /* Step 1: Close chains for which we have overlapping reads. */
782 for (i
= 0; i
< n_ops
; i
++)
783 scan_rtx (insn
, recog_data
.operand_loc
[i
],
784 NO_REGS
, terminate_overlapping_read
,
785 recog_data
.operand_type
[i
], 0);
787 /* Step 2: Close chains for which we have reads outside operands.
788 We do this by munging all operands into CC0, and closing
789 everything remaining. */
791 for (i
= 0; i
< n_ops
; i
++)
793 old_operands
[i
] = recog_data
.operand
[i
];
794 /* Don't squash match_operator or match_parallel here, since
795 we don't know that all of the contained registers are
796 reachable by proper operands. */
797 if (recog_data
.constraints
[i
][0] == '\0')
799 *recog_data
.operand_loc
[i
] = cc0_rtx
;
801 for (i
= 0; i
< recog_data
.n_dups
; i
++)
803 int dup_num
= recog_data
.dup_num
[i
];
805 old_dups
[i
] = *recog_data
.dup_loc
[i
];
806 *recog_data
.dup_loc
[i
] = cc0_rtx
;
808 /* For match_dup of match_operator or match_parallel, share
809 them, so that we don't miss changes in the dup. */
811 && insn_data
[icode
].operand
[dup_num
].eliminable
== 0)
812 old_dups
[i
] = recog_data
.operand
[dup_num
];
815 scan_rtx (insn
, &PATTERN (insn
), NO_REGS
, terminate_all_read
,
818 for (i
= 0; i
< recog_data
.n_dups
; i
++)
819 *recog_data
.dup_loc
[i
] = old_dups
[i
];
820 for (i
= 0; i
< n_ops
; i
++)
821 *recog_data
.operand_loc
[i
] = old_operands
[i
];
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 4: Close chains for registers that die here.
866 Also record updates for REG_INC notes. */
867 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
869 if (REG_NOTE_KIND (note
) == REG_DEAD
)
870 scan_rtx (insn
, &XEXP (note
, 0), NO_REGS
, terminate_dead
,
872 else if (REG_NOTE_KIND (note
) == REG_INC
)
873 scan_rtx (insn
, &XEXP (note
, 0), ALL_REGS
, mark_read
,
877 /* Step 4B: If this is a call, any chain live at this point
878 requires a caller-saved reg. */
882 for (p
= open_chains
; p
; p
= p
->next_chain
)
883 p
->need_caller_save_reg
= 1;
886 /* Step 5: Close open chains that overlap writes. Similar to
887 step 2, we hide in-out operands, since we do not want to
888 close these chains. */
890 for (i
= 0; i
< n_ops
; i
++)
892 old_operands
[i
] = recog_data
.operand
[i
];
893 if (recog_data
.operand_type
[i
] == OP_INOUT
)
894 *recog_data
.operand_loc
[i
] = cc0_rtx
;
896 for (i
= 0; i
< recog_data
.n_dups
; i
++)
898 int opn
= recog_data
.dup_num
[i
];
899 old_dups
[i
] = *recog_data
.dup_loc
[i
];
900 if (recog_data
.operand_type
[opn
] == OP_INOUT
)
901 *recog_data
.dup_loc
[i
] = cc0_rtx
;
904 scan_rtx (insn
, &PATTERN (insn
), NO_REGS
, terminate_write
, OP_IN
, 0);
906 for (i
= 0; i
< recog_data
.n_dups
; i
++)
907 *recog_data
.dup_loc
[i
] = old_dups
[i
];
908 for (i
= 0; i
< n_ops
; i
++)
909 *recog_data
.operand_loc
[i
] = old_operands
[i
];
911 /* Step 6: Begin new chains for writes inside operands. */
912 /* ??? Many targets have output constraints on the SET_DEST
913 of a call insn, which is stupid, since these are certainly
914 ABI defined hard registers. Don't change calls at all.
915 Similarly take special care for asm statement that originally
916 referenced hard registers. */
917 if (asm_noperands (PATTERN (insn
)) > 0)
919 for (i
= 0; i
< n_ops
; i
++)
920 if (recog_data
.operand_type
[i
] == OP_OUT
)
922 rtx
*loc
= recog_data
.operand_loc
[i
];
924 enum reg_class cl
= recog_op_alt
[i
][alt
].cl
;
927 && REGNO (op
) == ORIGINAL_REGNO (op
))
930 scan_rtx (insn
, loc
, cl
, mark_write
, OP_OUT
,
931 recog_op_alt
[i
][alt
].earlyclobber
);
934 else if (!CALL_P (insn
))
935 for (i
= 0; i
< n_ops
+ recog_data
.n_dups
; i
++)
937 int opn
= i
< n_ops
? i
: recog_data
.dup_num
[i
- n_ops
];
938 rtx
*loc
= (i
< n_ops
939 ? recog_data
.operand_loc
[opn
]
940 : recog_data
.dup_loc
[i
- n_ops
]);
941 enum reg_class cl
= recog_op_alt
[opn
][alt
].cl
;
943 if (recog_data
.operand_type
[opn
] == OP_OUT
)
944 scan_rtx (insn
, loc
, cl
, mark_write
, OP_OUT
,
945 recog_op_alt
[opn
][alt
].earlyclobber
);
948 /* Step 7: Close chains for registers that were never
950 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
951 if (REG_NOTE_KIND (note
) == REG_UNUSED
)
952 scan_rtx (insn
, &XEXP (note
, 0), NO_REGS
, terminate_dead
,
955 if (insn
== BB_END (bb
))
959 /* Since we close every chain when we find a REG_DEAD note, anything that
960 is still open lives past the basic block, so it can't be renamed. */
961 return closed_chains
;
964 /* Dump all def/use chains in CHAINS to DUMP_FILE. They are
965 printed in reverse order as that's how we build them. */
968 dump_def_use_chain (struct du_chain
*chains
)
972 struct du_chain
*this = chains
;
973 int r
= REGNO (*this->loc
);
974 int nregs
= hard_regno_nregs
[r
][GET_MODE (*this->loc
)];
975 fprintf (dump_file
, "Register %s (%d):", reg_names
[r
], nregs
);
978 fprintf (dump_file
, " %d [%s]", INSN_UID (this->insn
),
979 reg_class_names
[this->cl
]);
980 this = this->next_use
;
982 fprintf (dump_file
, "\n");
983 chains
= chains
->next_chain
;
987 /* The following code does forward propagation of hard register copies.
988 The object is to eliminate as many dependencies as possible, so that
989 we have the most scheduling freedom. As a side effect, we also clean
990 up some silly register allocation decisions made by reload. This
991 code may be obsoleted by a new register allocator. */
993 /* For each register, we have a list of registers that contain the same
994 value. The OLDEST_REGNO field points to the head of the list, and
995 the NEXT_REGNO field runs through the list. The MODE field indicates
996 what mode the data is known to be in; this field is VOIDmode when the
997 register is not known to contain valid data. */
999 struct value_data_entry
1001 enum machine_mode mode
;
1002 unsigned int oldest_regno
;
1003 unsigned int next_regno
;
1008 struct value_data_entry e
[FIRST_PSEUDO_REGISTER
];
1009 unsigned int max_value_regs
;
1012 static void kill_value_one_regno (unsigned, struct value_data
*);
1013 static void kill_value_regno (unsigned, unsigned, struct value_data
*);
1014 static void kill_value (rtx
, struct value_data
*);
1015 static void set_value_regno (unsigned, enum machine_mode
, struct value_data
*);
1016 static void init_value_data (struct value_data
*);
1017 static void kill_clobbered_value (rtx
, rtx
, void *);
1018 static void kill_set_value (rtx
, rtx
, void *);
1019 static int kill_autoinc_value (rtx
*, void *);
1020 static void copy_value (rtx
, rtx
, struct value_data
*);
1021 static bool mode_change_ok (enum machine_mode
, enum machine_mode
,
1023 static rtx
maybe_mode_change (enum machine_mode
, enum machine_mode
,
1024 enum machine_mode
, unsigned int, unsigned int);
1025 static rtx
find_oldest_value_reg (enum reg_class
, rtx
, struct value_data
*);
1026 static bool replace_oldest_value_reg (rtx
*, enum reg_class
, rtx
,
1027 struct value_data
*);
1028 static bool replace_oldest_value_addr (rtx
*, enum reg_class
,
1029 enum machine_mode
, rtx
,
1030 struct value_data
*);
1031 static bool replace_oldest_value_mem (rtx
, rtx
, struct value_data
*);
1032 static bool copyprop_hardreg_forward_1 (basic_block
, struct value_data
*);
1033 extern void debug_value_data (struct value_data
*);
1034 #ifdef ENABLE_CHECKING
1035 static void validate_value_data (struct value_data
*);
1038 /* Kill register REGNO. This involves removing it from any value
1039 lists, and resetting the value mode to VOIDmode. This is only a
1040 helper function; it does not handle any hard registers overlapping
1044 kill_value_one_regno (unsigned int regno
, struct value_data
*vd
)
1046 unsigned int i
, next
;
1048 if (vd
->e
[regno
].oldest_regno
!= regno
)
1050 for (i
= vd
->e
[regno
].oldest_regno
;
1051 vd
->e
[i
].next_regno
!= regno
;
1052 i
= vd
->e
[i
].next_regno
)
1054 vd
->e
[i
].next_regno
= vd
->e
[regno
].next_regno
;
1056 else if ((next
= vd
->e
[regno
].next_regno
) != INVALID_REGNUM
)
1058 for (i
= next
; i
!= INVALID_REGNUM
; i
= vd
->e
[i
].next_regno
)
1059 vd
->e
[i
].oldest_regno
= next
;
1062 vd
->e
[regno
].mode
= VOIDmode
;
1063 vd
->e
[regno
].oldest_regno
= regno
;
1064 vd
->e
[regno
].next_regno
= INVALID_REGNUM
;
1066 #ifdef ENABLE_CHECKING
1067 validate_value_data (vd
);
1071 /* Kill the value in register REGNO for NREGS, and any other registers
1072 whose values overlap. */
1075 kill_value_regno (unsigned int regno
, unsigned int nregs
,
1076 struct value_data
*vd
)
1080 /* Kill the value we're told to kill. */
1081 for (j
= 0; j
< nregs
; ++j
)
1082 kill_value_one_regno (regno
+ j
, vd
);
1084 /* Kill everything that overlapped what we're told to kill. */
1085 if (regno
< vd
->max_value_regs
)
1088 j
= regno
- vd
->max_value_regs
;
1089 for (; j
< regno
; ++j
)
1092 if (vd
->e
[j
].mode
== VOIDmode
)
1094 n
= hard_regno_nregs
[j
][vd
->e
[j
].mode
];
1096 for (i
= 0; i
< n
; ++i
)
1097 kill_value_one_regno (j
+ i
, vd
);
1101 /* Kill X. This is a convenience function wrapping kill_value_regno
1102 so that we mind the mode the register is in. */
1105 kill_value (rtx x
, struct value_data
*vd
)
1107 /* SUBREGS are supposed to have been eliminated by now. But some
1108 ports, e.g. i386 sse, use them to smuggle vector type information
1109 through to instruction selection. Each such SUBREG should simplify,
1110 so if we get a NULL we've done something wrong elsewhere. */
1112 if (GET_CODE (x
) == SUBREG
)
1113 x
= simplify_subreg (GET_MODE (x
), SUBREG_REG (x
),
1114 GET_MODE (SUBREG_REG (x
)), SUBREG_BYTE (x
));
1117 unsigned int regno
= REGNO (x
);
1118 unsigned int n
= hard_regno_nregs
[regno
][GET_MODE (x
)];
1120 kill_value_regno (regno
, n
, vd
);
1124 /* Remember that REGNO is valid in MODE. */
1127 set_value_regno (unsigned int regno
, enum machine_mode mode
,
1128 struct value_data
*vd
)
1132 vd
->e
[regno
].mode
= mode
;
1134 nregs
= hard_regno_nregs
[regno
][mode
];
1135 if (nregs
> vd
->max_value_regs
)
1136 vd
->max_value_regs
= nregs
;
1139 /* Initialize VD such that there are no known relationships between regs. */
1142 init_value_data (struct value_data
*vd
)
1145 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1147 vd
->e
[i
].mode
= VOIDmode
;
1148 vd
->e
[i
].oldest_regno
= i
;
1149 vd
->e
[i
].next_regno
= INVALID_REGNUM
;
1151 vd
->max_value_regs
= 0;
1154 /* Called through note_stores. If X is clobbered, kill its value. */
1157 kill_clobbered_value (rtx x
, rtx set
, void *data
)
1159 struct value_data
*vd
= data
;
1160 if (GET_CODE (set
) == CLOBBER
)
1164 /* Called through note_stores. If X is set, not clobbered, kill its
1165 current value and install it as the root of its own value list. */
1168 kill_set_value (rtx x
, rtx set
, void *data
)
1170 struct value_data
*vd
= data
;
1171 if (GET_CODE (set
) != CLOBBER
)
1175 set_value_regno (REGNO (x
), GET_MODE (x
), vd
);
1179 /* Called through for_each_rtx. Kill any register used as the base of an
1180 auto-increment expression, and install that register as the root of its
1184 kill_autoinc_value (rtx
*px
, void *data
)
1187 struct value_data
*vd
= data
;
1189 if (GET_RTX_CLASS (GET_CODE (x
)) == RTX_AUTOINC
)
1193 set_value_regno (REGNO (x
), Pmode
, vd
);
1200 /* Assert that SRC has been copied to DEST. Adjust the data structures
1201 to reflect that SRC contains an older copy of the shared value. */
1204 copy_value (rtx dest
, rtx src
, struct value_data
*vd
)
1206 unsigned int dr
= REGNO (dest
);
1207 unsigned int sr
= REGNO (src
);
1208 unsigned int dn
, sn
;
1211 /* ??? At present, it's possible to see noop sets. It'd be nice if
1212 this were cleaned up beforehand... */
1216 /* Do not propagate copies to the stack pointer, as that can leave
1217 memory accesses with no scheduling dependency on the stack update. */
1218 if (dr
== STACK_POINTER_REGNUM
)
1221 /* Likewise with the frame pointer, if we're using one. */
1222 if (frame_pointer_needed
&& dr
== HARD_FRAME_POINTER_REGNUM
)
1225 /* If SRC and DEST overlap, don't record anything. */
1226 dn
= hard_regno_nregs
[dr
][GET_MODE (dest
)];
1227 sn
= hard_regno_nregs
[sr
][GET_MODE (dest
)];
1228 if ((dr
> sr
&& dr
< sr
+ sn
)
1229 || (sr
> dr
&& sr
< dr
+ dn
))
1232 /* If SRC had no assigned mode (i.e. we didn't know it was live)
1233 assign it now and assume the value came from an input argument
1235 if (vd
->e
[sr
].mode
== VOIDmode
)
1236 set_value_regno (sr
, vd
->e
[dr
].mode
, vd
);
1238 /* If we are narrowing the input to a smaller number of hard regs,
1239 and it is in big endian, we are really extracting a high part.
1240 Since we generally associate a low part of a value with the value itself,
1241 we must not do the same for the high part.
1242 Note we can still get low parts for the same mode combination through
1243 a two-step copy involving differently sized hard regs.
1244 Assume hard regs fr* are 32 bits bits each, while r* are 64 bits each:
1245 (set (reg:DI r0) (reg:DI fr0))
1246 (set (reg:SI fr2) (reg:SI r0))
1247 loads the low part of (reg:DI fr0) - i.e. fr1 - into fr2, while:
1248 (set (reg:SI fr2) (reg:SI fr0))
1249 loads the high part of (reg:DI fr0) into fr2.
1251 We can't properly represent the latter case in our tables, so don't
1252 record anything then. */
1253 else if (sn
< (unsigned int) hard_regno_nregs
[sr
][vd
->e
[sr
].mode
]
1254 && (GET_MODE_SIZE (vd
->e
[sr
].mode
) > UNITS_PER_WORD
1255 ? WORDS_BIG_ENDIAN
: BYTES_BIG_ENDIAN
))
1258 /* If SRC had been assigned a mode narrower than the copy, we can't
1259 link DEST into the chain, because not all of the pieces of the
1260 copy came from oldest_regno. */
1261 else if (sn
> (unsigned int) hard_regno_nregs
[sr
][vd
->e
[sr
].mode
])
1264 /* Link DR at the end of the value chain used by SR. */
1266 vd
->e
[dr
].oldest_regno
= vd
->e
[sr
].oldest_regno
;
1268 for (i
= sr
; vd
->e
[i
].next_regno
!= INVALID_REGNUM
; i
= vd
->e
[i
].next_regno
)
1270 vd
->e
[i
].next_regno
= dr
;
1272 #ifdef ENABLE_CHECKING
1273 validate_value_data (vd
);
1277 /* Return true if a mode change from ORIG to NEW is allowed for REGNO. */
1280 mode_change_ok (enum machine_mode orig_mode
, enum machine_mode new_mode
,
1281 unsigned int regno ATTRIBUTE_UNUSED
)
1283 if (GET_MODE_SIZE (orig_mode
) < GET_MODE_SIZE (new_mode
))
1286 #ifdef CANNOT_CHANGE_MODE_CLASS
1287 return !REG_CANNOT_CHANGE_MODE_P (regno
, orig_mode
, new_mode
);
1293 /* Register REGNO was originally set in ORIG_MODE. It - or a copy of it -
1294 was copied in COPY_MODE to COPY_REGNO, and then COPY_REGNO was accessed
1296 Return a NEW_MODE rtx for REGNO if that's OK, otherwise return NULL_RTX. */
1299 maybe_mode_change (enum machine_mode orig_mode
, enum machine_mode copy_mode
,
1300 enum machine_mode new_mode
, unsigned int regno
,
1301 unsigned int copy_regno ATTRIBUTE_UNUSED
)
1303 if (orig_mode
== new_mode
)
1304 return gen_rtx_raw_REG (new_mode
, regno
);
1305 else if (mode_change_ok (orig_mode
, new_mode
, regno
))
1307 int copy_nregs
= hard_regno_nregs
[copy_regno
][copy_mode
];
1308 int use_nregs
= hard_regno_nregs
[copy_regno
][new_mode
];
1310 = GET_MODE_SIZE (copy_mode
) / copy_nregs
* (copy_nregs
- use_nregs
);
1312 = GET_MODE_SIZE (orig_mode
) - GET_MODE_SIZE (new_mode
) - copy_offset
;
1313 int byteoffset
= offset
% UNITS_PER_WORD
;
1314 int wordoffset
= offset
- byteoffset
;
1316 offset
= ((WORDS_BIG_ENDIAN
? wordoffset
: 0)
1317 + (BYTES_BIG_ENDIAN
? byteoffset
: 0));
1318 return gen_rtx_raw_REG (new_mode
,
1319 regno
+ subreg_regno_offset (regno
, orig_mode
,
1326 /* Find the oldest copy of the value contained in REGNO that is in
1327 register class CL and has mode MODE. If found, return an rtx
1328 of that oldest register, otherwise return NULL. */
1331 find_oldest_value_reg (enum reg_class cl
, rtx reg
, struct value_data
*vd
)
1333 unsigned int regno
= REGNO (reg
);
1334 enum machine_mode mode
= GET_MODE (reg
);
1337 /* If we are accessing REG in some mode other that what we set it in,
1338 make sure that the replacement is valid. In particular, consider
1339 (set (reg:DI r11) (...))
1340 (set (reg:SI r9) (reg:SI r11))
1341 (set (reg:SI r10) (...))
1342 (set (...) (reg:DI r9))
1343 Replacing r9 with r11 is invalid. */
1344 if (mode
!= vd
->e
[regno
].mode
)
1346 if (hard_regno_nregs
[regno
][mode
]
1347 > hard_regno_nregs
[regno
][vd
->e
[regno
].mode
])
1351 for (i
= vd
->e
[regno
].oldest_regno
; i
!= regno
; i
= vd
->e
[i
].next_regno
)
1353 enum machine_mode oldmode
= vd
->e
[i
].mode
;
1357 for (last
= i
; last
< i
+ hard_regno_nregs
[i
][mode
]; last
++)
1358 if (!TEST_HARD_REG_BIT (reg_class_contents
[cl
], last
))
1361 new = maybe_mode_change (oldmode
, vd
->e
[regno
].mode
, mode
, i
, regno
);
1364 ORIGINAL_REGNO (new) = ORIGINAL_REGNO (reg
);
1365 REG_ATTRS (new) = REG_ATTRS (reg
);
1373 /* If possible, replace the register at *LOC with the oldest register
1374 in register class CL. Return true if successfully replaced. */
1377 replace_oldest_value_reg (rtx
*loc
, enum reg_class cl
, rtx insn
,
1378 struct value_data
*vd
)
1380 rtx
new = find_oldest_value_reg (cl
, *loc
, vd
);
1384 fprintf (dump_file
, "insn %u: replaced reg %u with %u\n",
1385 INSN_UID (insn
), REGNO (*loc
), REGNO (new));
1393 /* Similar to replace_oldest_value_reg, but *LOC contains an address.
1394 Adapted from find_reloads_address_1. CL is INDEX_REG_CLASS or
1395 BASE_REG_CLASS depending on how the register is being considered. */
1398 replace_oldest_value_addr (rtx
*loc
, enum reg_class cl
,
1399 enum machine_mode mode
, rtx insn
,
1400 struct value_data
*vd
)
1403 RTX_CODE code
= GET_CODE (x
);
1406 bool changed
= false;
1412 rtx orig_op0
= XEXP (x
, 0);
1413 rtx orig_op1
= XEXP (x
, 1);
1414 RTX_CODE code0
= GET_CODE (orig_op0
);
1415 RTX_CODE code1
= GET_CODE (orig_op1
);
1420 rtx
*locB_reg
= NULL
;
1422 if (GET_CODE (op0
) == SUBREG
)
1424 op0
= SUBREG_REG (op0
);
1425 code0
= GET_CODE (op0
);
1428 if (GET_CODE (op1
) == SUBREG
)
1430 op1
= SUBREG_REG (op1
);
1431 code1
= GET_CODE (op1
);
1434 if (code0
== MULT
|| code0
== SIGN_EXTEND
|| code0
== TRUNCATE
1435 || code0
== ZERO_EXTEND
|| code1
== MEM
)
1437 locI
= &XEXP (x
, 0);
1438 locB
= &XEXP (x
, 1);
1440 else if (code1
== MULT
|| code1
== SIGN_EXTEND
|| code1
== TRUNCATE
1441 || code1
== ZERO_EXTEND
|| code0
== MEM
)
1443 locI
= &XEXP (x
, 1);
1444 locB
= &XEXP (x
, 0);
1446 else if (code0
== CONST_INT
|| code0
== CONST
1447 || code0
== SYMBOL_REF
|| code0
== LABEL_REF
)
1448 locB
= &XEXP (x
, 1);
1449 else if (code1
== CONST_INT
|| code1
== CONST
1450 || code1
== SYMBOL_REF
|| code1
== LABEL_REF
)
1451 locB
= &XEXP (x
, 0);
1452 else if (code0
== REG
&& code1
== REG
)
1456 if (REG_OK_FOR_INDEX_P (op0
)
1457 && REG_MODE_OK_FOR_REG_BASE_P (op1
, mode
))
1459 else if (REG_OK_FOR_INDEX_P (op1
)
1460 && REG_MODE_OK_FOR_REG_BASE_P (op0
, mode
))
1462 else if (REG_MODE_OK_FOR_REG_BASE_P (op1
, mode
))
1464 else if (REG_MODE_OK_FOR_REG_BASE_P (op0
, mode
))
1466 else if (REG_OK_FOR_INDEX_P (op1
))
1471 locI
= &XEXP (x
, index_op
);
1472 locB_reg
= &XEXP (x
, !index_op
);
1474 else if (code0
== REG
)
1476 locI
= &XEXP (x
, 0);
1477 locB
= &XEXP (x
, 1);
1479 else if (code1
== REG
)
1481 locI
= &XEXP (x
, 1);
1482 locB
= &XEXP (x
, 0);
1486 changed
|= replace_oldest_value_addr (locI
, INDEX_REG_CLASS
, mode
,
1489 changed
|= replace_oldest_value_addr (locB
,
1490 MODE_BASE_REG_CLASS (mode
),
1493 changed
|= replace_oldest_value_addr (locB_reg
,
1494 MODE_BASE_REG_REG_CLASS (mode
),
1508 return replace_oldest_value_mem (x
, insn
, vd
);
1511 return replace_oldest_value_reg (loc
, cl
, insn
, vd
);
1517 fmt
= GET_RTX_FORMAT (code
);
1518 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1521 changed
|= replace_oldest_value_addr (&XEXP (x
, i
), cl
, mode
,
1523 else if (fmt
[i
] == 'E')
1524 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
1525 changed
|= replace_oldest_value_addr (&XVECEXP (x
, i
, j
), cl
,
1532 /* Similar to replace_oldest_value_reg, but X contains a memory. */
1535 replace_oldest_value_mem (rtx x
, rtx insn
, struct value_data
*vd
)
1537 return replace_oldest_value_addr (&XEXP (x
, 0),
1538 MODE_BASE_REG_CLASS (GET_MODE (x
)),
1539 GET_MODE (x
), insn
, vd
);
1542 /* Perform the forward copy propagation on basic block BB. */
1545 copyprop_hardreg_forward_1 (basic_block bb
, struct value_data
*vd
)
1547 bool changed
= false;
1550 for (insn
= BB_HEAD (bb
); ; insn
= NEXT_INSN (insn
))
1552 int n_ops
, i
, alt
, predicated
;
1556 if (! INSN_P (insn
))
1558 if (insn
== BB_END (bb
))
1564 set
= single_set (insn
);
1565 extract_insn (insn
);
1566 if (! constrain_operands (1))
1567 fatal_insn_not_found (insn
);
1568 preprocess_constraints ();
1569 alt
= which_alternative
;
1570 n_ops
= recog_data
.n_operands
;
1571 is_asm
= asm_noperands (PATTERN (insn
)) >= 0;
1573 /* Simplify the code below by rewriting things to reflect
1574 matching constraints. Also promote OP_OUT to OP_INOUT
1575 in predicated instructions. */
1577 predicated
= GET_CODE (PATTERN (insn
)) == COND_EXEC
;
1578 for (i
= 0; i
< n_ops
; ++i
)
1580 int matches
= recog_op_alt
[i
][alt
].matches
;
1582 recog_op_alt
[i
][alt
].cl
= recog_op_alt
[matches
][alt
].cl
;
1583 if (matches
>= 0 || recog_op_alt
[i
][alt
].matched
>= 0
1584 || (predicated
&& recog_data
.operand_type
[i
] == OP_OUT
))
1585 recog_data
.operand_type
[i
] = OP_INOUT
;
1588 /* For each earlyclobber operand, zap the value data. */
1589 for (i
= 0; i
< n_ops
; i
++)
1590 if (recog_op_alt
[i
][alt
].earlyclobber
)
1591 kill_value (recog_data
.operand
[i
], vd
);
1593 /* Within asms, a clobber cannot overlap inputs or outputs.
1594 I wouldn't think this were true for regular insns, but
1595 scan_rtx treats them like that... */
1596 note_stores (PATTERN (insn
), kill_clobbered_value
, vd
);
1598 /* Kill all auto-incremented values. */
1599 /* ??? REG_INC is useless, since stack pushes aren't done that way. */
1600 for_each_rtx (&PATTERN (insn
), kill_autoinc_value
, vd
);
1602 /* Kill all early-clobbered operands. */
1603 for (i
= 0; i
< n_ops
; i
++)
1604 if (recog_op_alt
[i
][alt
].earlyclobber
)
1605 kill_value (recog_data
.operand
[i
], vd
);
1607 /* Special-case plain move instructions, since we may well
1608 be able to do the move from a different register class. */
1609 if (set
&& REG_P (SET_SRC (set
)))
1611 rtx src
= SET_SRC (set
);
1612 unsigned int regno
= REGNO (src
);
1613 enum machine_mode mode
= GET_MODE (src
);
1617 /* If we are accessing SRC in some mode other that what we
1618 set it in, make sure that the replacement is valid. */
1619 if (mode
!= vd
->e
[regno
].mode
)
1621 if (hard_regno_nregs
[regno
][mode
]
1622 > hard_regno_nregs
[regno
][vd
->e
[regno
].mode
])
1623 goto no_move_special_case
;
1626 /* If the destination is also a register, try to find a source
1627 register in the same class. */
1628 if (REG_P (SET_DEST (set
)))
1630 new = find_oldest_value_reg (REGNO_REG_CLASS (regno
), src
, vd
);
1631 if (new && validate_change (insn
, &SET_SRC (set
), new, 0))
1635 "insn %u: replaced reg %u with %u\n",
1636 INSN_UID (insn
), regno
, REGNO (new));
1638 goto did_replacement
;
1642 /* Otherwise, try all valid registers and see if its valid. */
1643 for (i
= vd
->e
[regno
].oldest_regno
; i
!= regno
;
1644 i
= vd
->e
[i
].next_regno
)
1646 new = maybe_mode_change (vd
->e
[i
].mode
, vd
->e
[regno
].mode
,
1648 if (new != NULL_RTX
)
1650 if (validate_change (insn
, &SET_SRC (set
), new, 0))
1652 ORIGINAL_REGNO (new) = ORIGINAL_REGNO (src
);
1653 REG_ATTRS (new) = REG_ATTRS (src
);
1656 "insn %u: replaced reg %u with %u\n",
1657 INSN_UID (insn
), regno
, REGNO (new));
1659 goto did_replacement
;
1664 no_move_special_case
:
1666 /* For each input operand, replace a hard register with the
1667 eldest live copy that's in an appropriate register class. */
1668 for (i
= 0; i
< n_ops
; i
++)
1670 bool replaced
= false;
1672 /* Don't scan match_operand here, since we've no reg class
1673 information to pass down. Any operands that we could
1674 substitute in will be represented elsewhere. */
1675 if (recog_data
.constraints
[i
][0] == '\0')
1678 /* Don't replace in asms intentionally referencing hard regs. */
1679 if (is_asm
&& REG_P (recog_data
.operand
[i
])
1680 && (REGNO (recog_data
.operand
[i
])
1681 == ORIGINAL_REGNO (recog_data
.operand
[i
])))
1684 if (recog_data
.operand_type
[i
] == OP_IN
)
1686 if (recog_op_alt
[i
][alt
].is_address
)
1688 = replace_oldest_value_addr (recog_data
.operand_loc
[i
],
1689 recog_op_alt
[i
][alt
].cl
,
1690 VOIDmode
, insn
, vd
);
1691 else if (REG_P (recog_data
.operand
[i
]))
1693 = replace_oldest_value_reg (recog_data
.operand_loc
[i
],
1694 recog_op_alt
[i
][alt
].cl
,
1696 else if (MEM_P (recog_data
.operand
[i
]))
1697 replaced
= replace_oldest_value_mem (recog_data
.operand
[i
],
1700 else if (MEM_P (recog_data
.operand
[i
]))
1701 replaced
= replace_oldest_value_mem (recog_data
.operand
[i
],
1704 /* If we performed any replacement, update match_dups. */
1712 new = *recog_data
.operand_loc
[i
];
1713 recog_data
.operand
[i
] = new;
1714 for (j
= 0; j
< recog_data
.n_dups
; j
++)
1715 if (recog_data
.dup_num
[j
] == i
)
1716 *recog_data
.dup_loc
[j
] = new;
1721 /* Clobber call-clobbered registers. */
1723 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1724 if (TEST_HARD_REG_BIT (regs_invalidated_by_call
, i
))
1725 kill_value_regno (i
, 1, vd
);
1727 /* Notice stores. */
1728 note_stores (PATTERN (insn
), kill_set_value
, vd
);
1730 /* Notice copies. */
1731 if (set
&& REG_P (SET_DEST (set
)) && REG_P (SET_SRC (set
)))
1732 copy_value (SET_DEST (set
), SET_SRC (set
), vd
);
1734 if (insn
== BB_END (bb
))
1741 /* Main entry point for the forward copy propagation optimization. */
1744 copyprop_hardreg_forward (void)
1746 struct value_data
*all_vd
;
1748 basic_block bb
, bbp
= 0;
1750 need_refresh
= false;
1752 all_vd
= xmalloc (sizeof (struct value_data
) * last_basic_block
);
1756 /* If a block has a single predecessor, that we've already
1757 processed, begin with the value data that was live at
1758 the end of the predecessor block. */
1759 /* ??? Ought to use more intelligent queuing of blocks. */
1760 if (EDGE_COUNT (bb
->preds
) > 0)
1761 for (bbp
= bb
; bbp
&& bbp
!= EDGE_PRED (bb
, 0)->src
; bbp
= bbp
->prev_bb
);
1762 if (EDGE_COUNT (bb
->preds
) == 1
1763 && ! (EDGE_PRED (bb
, 0)->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
1764 && EDGE_PRED (bb
, 0)->src
!= ENTRY_BLOCK_PTR
1766 all_vd
[bb
->index
] = all_vd
[EDGE_PRED (bb
, 0)->src
->index
];
1768 init_value_data (all_vd
+ bb
->index
);
1770 if (copyprop_hardreg_forward_1 (bb
, all_vd
+ bb
->index
))
1771 need_refresh
= true;
1777 fputs ("\n\n", dump_file
);
1779 /* ??? Irritatingly, delete_noop_moves does not take a set of blocks
1780 to scan, so we have to do a life update with no initial set of
1781 blocks Just In Case. */
1782 delete_noop_moves ();
1783 update_life_info (NULL
, UPDATE_LIFE_GLOBAL_RM_NOTES
,
1785 | PROP_SCAN_DEAD_CODE
1786 | PROP_KILL_DEAD_CODE
);
1792 /* Dump the value chain data to stderr. */
1795 debug_value_data (struct value_data
*vd
)
1800 CLEAR_HARD_REG_SET (set
);
1802 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1803 if (vd
->e
[i
].oldest_regno
== i
)
1805 if (vd
->e
[i
].mode
== VOIDmode
)
1807 if (vd
->e
[i
].next_regno
!= INVALID_REGNUM
)
1808 fprintf (stderr
, "[%u] Bad next_regno for empty chain (%u)\n",
1809 i
, vd
->e
[i
].next_regno
);
1813 SET_HARD_REG_BIT (set
, i
);
1814 fprintf (stderr
, "[%u %s] ", i
, GET_MODE_NAME (vd
->e
[i
].mode
));
1816 for (j
= vd
->e
[i
].next_regno
;
1817 j
!= INVALID_REGNUM
;
1818 j
= vd
->e
[j
].next_regno
)
1820 if (TEST_HARD_REG_BIT (set
, j
))
1822 fprintf (stderr
, "[%u] Loop in regno chain\n", j
);
1826 if (vd
->e
[j
].oldest_regno
!= i
)
1828 fprintf (stderr
, "[%u] Bad oldest_regno (%u)\n",
1829 j
, vd
->e
[j
].oldest_regno
);
1832 SET_HARD_REG_BIT (set
, j
);
1833 fprintf (stderr
, "[%u %s] ", j
, GET_MODE_NAME (vd
->e
[j
].mode
));
1835 fputc ('\n', stderr
);
1838 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1839 if (! TEST_HARD_REG_BIT (set
, i
)
1840 && (vd
->e
[i
].mode
!= VOIDmode
1841 || vd
->e
[i
].oldest_regno
!= i
1842 || vd
->e
[i
].next_regno
!= INVALID_REGNUM
))
1843 fprintf (stderr
, "[%u] Non-empty reg in chain (%s %u %i)\n",
1844 i
, GET_MODE_NAME (vd
->e
[i
].mode
), vd
->e
[i
].oldest_regno
,
1845 vd
->e
[i
].next_regno
);
1848 #ifdef ENABLE_CHECKING
1850 validate_value_data (struct value_data
*vd
)
1855 CLEAR_HARD_REG_SET (set
);
1857 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1858 if (vd
->e
[i
].oldest_regno
== i
)
1860 if (vd
->e
[i
].mode
== VOIDmode
)
1862 if (vd
->e
[i
].next_regno
!= INVALID_REGNUM
)
1863 internal_error ("validate_value_data: [%u] Bad next_regno for empty chain (%u)",
1864 i
, vd
->e
[i
].next_regno
);
1868 SET_HARD_REG_BIT (set
, i
);
1870 for (j
= vd
->e
[i
].next_regno
;
1871 j
!= INVALID_REGNUM
;
1872 j
= vd
->e
[j
].next_regno
)
1874 if (TEST_HARD_REG_BIT (set
, j
))
1875 internal_error ("validate_value_data: Loop in regno chain (%u)",
1877 if (vd
->e
[j
].oldest_regno
!= i
)
1878 internal_error ("validate_value_data: [%u] Bad oldest_regno (%u)",
1879 j
, vd
->e
[j
].oldest_regno
);
1881 SET_HARD_REG_BIT (set
, j
);
1885 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1886 if (! TEST_HARD_REG_BIT (set
, i
)
1887 && (vd
->e
[i
].mode
!= VOIDmode
1888 || vd
->e
[i
].oldest_regno
!= i
1889 || vd
->e
[i
].next_regno
!= INVALID_REGNUM
))
1890 internal_error ("validate_value_data: [%u] Non-empty reg in chain (%s %u %i)",
1891 i
, GET_MODE_NAME (vd
->e
[i
].mode
), vd
->e
[i
].oldest_regno
,
1892 vd
->e
[i
].next_regno
);