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
25 #include "coretypes.h"
29 #include "insn-config.h"
31 #include "hard-reg-set.h"
32 #include "basic-block.h"
41 #ifndef REG_MODE_OK_FOR_BASE_P
42 #define REG_MODE_OK_FOR_BASE_P(REGNO, MODE) REG_OK_FOR_BASE_P (REGNO)
45 static const char *const reg_class_names
[] = REG_CLASS_NAMES
;
49 struct du_chain
*next_chain
;
50 struct du_chain
*next_use
;
54 ENUM_BITFIELD(reg_class
) class : 16;
55 unsigned int need_caller_save_reg
:1;
56 unsigned int earlyclobber
:1;
62 terminate_overlapping_read
,
69 static const char * const scan_actions_name
[] =
72 "terminate_overlapping_read",
79 static struct obstack rename_obstack
;
81 static void do_replace (struct du_chain
*, int);
82 static void scan_rtx_reg (rtx
, rtx
*, enum reg_class
,
83 enum scan_actions
, enum op_type
, int);
84 static void scan_rtx_address (rtx
, rtx
*, enum reg_class
,
85 enum scan_actions
, enum machine_mode
);
86 static void scan_rtx (rtx
, rtx
*, enum reg_class
, enum scan_actions
,
88 static struct du_chain
*build_def_use (basic_block
);
89 static void dump_def_use_chain (struct du_chain
*);
90 static void note_sets (rtx
, rtx
, void *);
91 static void clear_dead_regs (HARD_REG_SET
*, enum machine_mode
, rtx
);
92 static void merge_overlapping_regs (basic_block
, HARD_REG_SET
*,
95 /* Called through note_stores from update_life. Find sets of registers, and
96 record them in *DATA (which is actually a HARD_REG_SET *). */
99 note_sets (rtx x
, rtx set ATTRIBUTE_UNUSED
, void *data
)
101 HARD_REG_SET
*pset
= (HARD_REG_SET
*) data
;
104 if (GET_CODE (x
) != REG
)
107 nregs
= hard_regno_nregs
[regno
][GET_MODE (x
)];
109 /* There must not be pseudos at this point. */
110 if (regno
+ nregs
> FIRST_PSEUDO_REGISTER
)
114 SET_HARD_REG_BIT (*pset
, regno
+ nregs
);
117 /* Clear all registers from *PSET for which a note of kind KIND can be found
118 in the list NOTES. */
121 clear_dead_regs (HARD_REG_SET
*pset
, enum machine_mode kind
, rtx notes
)
124 for (note
= notes
; note
; note
= XEXP (note
, 1))
125 if (REG_NOTE_KIND (note
) == kind
&& REG_P (XEXP (note
, 0)))
127 rtx reg
= XEXP (note
, 0);
128 unsigned int regno
= REGNO (reg
);
129 int nregs
= hard_regno_nregs
[regno
][GET_MODE (reg
)];
131 /* There must not be pseudos at this point. */
132 if (regno
+ nregs
> FIRST_PSEUDO_REGISTER
)
136 CLEAR_HARD_REG_BIT (*pset
, regno
+ nregs
);
140 /* For a def-use chain CHAIN in basic block B, find which registers overlap
141 its lifetime and set the corresponding bits in *PSET. */
144 merge_overlapping_regs (basic_block b
, HARD_REG_SET
*pset
,
145 struct du_chain
*chain
)
147 struct du_chain
*t
= chain
;
151 REG_SET_TO_HARD_REG_SET (live
, b
->global_live_at_start
);
155 /* Search forward until the next reference to the register to be
157 while (insn
!= t
->insn
)
161 clear_dead_regs (&live
, REG_DEAD
, REG_NOTES (insn
));
162 note_stores (PATTERN (insn
), note_sets
, (void *) &live
);
163 /* Only record currently live regs if we are inside the
166 IOR_HARD_REG_SET (*pset
, live
);
167 clear_dead_regs (&live
, REG_UNUSED
, REG_NOTES (insn
));
169 insn
= NEXT_INSN (insn
);
172 IOR_HARD_REG_SET (*pset
, live
);
174 /* For the last reference, also merge in all registers set in the
176 @@@ We only have take earlyclobbered sets into account. */
178 note_stores (PATTERN (insn
), note_sets
, (void *) pset
);
184 /* Perform register renaming on the current function. */
187 regrename_optimize (void)
189 int tick
[FIRST_PSEUDO_REGISTER
];
194 memset (tick
, 0, sizeof tick
);
196 gcc_obstack_init (&rename_obstack
);
197 first_obj
= obstack_alloc (&rename_obstack
, 0);
201 struct du_chain
*all_chains
= 0;
202 HARD_REG_SET unavailable
;
203 HARD_REG_SET regs_seen
;
205 CLEAR_HARD_REG_SET (unavailable
);
208 fprintf (dump_file
, "\nBasic block %d:\n", bb
->index
);
210 all_chains
= build_def_use (bb
);
213 dump_def_use_chain (all_chains
);
215 CLEAR_HARD_REG_SET (unavailable
);
216 /* Don't clobber traceback for noreturn functions. */
217 if (frame_pointer_needed
)
221 for (i
= hard_regno_nregs
[FRAME_POINTER_REGNUM
][Pmode
]; i
--;)
222 SET_HARD_REG_BIT (unavailable
, FRAME_POINTER_REGNUM
+ i
);
224 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
225 for (i
= hard_regno_nregs
[HARD_FRAME_POINTER_REGNUM
][Pmode
]; i
--;)
226 SET_HARD_REG_BIT (unavailable
, HARD_FRAME_POINTER_REGNUM
+ i
);
230 CLEAR_HARD_REG_SET (regs_seen
);
233 int new_reg
, best_new_reg
;
235 struct du_chain
*this = all_chains
;
236 struct du_chain
*tmp
, *last
;
237 HARD_REG_SET this_unavailable
;
238 int reg
= REGNO (*this->loc
);
241 all_chains
= this->next_chain
;
245 #if 0 /* This just disables optimization opportunities. */
246 /* Only rename once we've seen the reg more than once. */
247 if (! TEST_HARD_REG_BIT (regs_seen
, reg
))
249 SET_HARD_REG_BIT (regs_seen
, reg
);
254 if (fixed_regs
[reg
] || global_regs
[reg
]
255 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
256 || (frame_pointer_needed
&& reg
== HARD_FRAME_POINTER_REGNUM
)
258 || (frame_pointer_needed
&& reg
== FRAME_POINTER_REGNUM
)
263 COPY_HARD_REG_SET (this_unavailable
, unavailable
);
265 /* Find last entry on chain (which has the need_caller_save bit),
266 count number of uses, and narrow the set of registers we can
269 for (last
= this; last
->next_use
; last
= last
->next_use
)
272 IOR_COMPL_HARD_REG_SET (this_unavailable
,
273 reg_class_contents
[last
->class]);
278 IOR_COMPL_HARD_REG_SET (this_unavailable
,
279 reg_class_contents
[last
->class]);
281 if (this->need_caller_save_reg
)
282 IOR_HARD_REG_SET (this_unavailable
, call_used_reg_set
);
284 merge_overlapping_regs (bb
, &this_unavailable
, this);
286 /* Now potential_regs is a reasonable approximation, let's
287 have a closer look at each register still in there. */
288 for (new_reg
= 0; new_reg
< FIRST_PSEUDO_REGISTER
; new_reg
++)
290 int nregs
= hard_regno_nregs
[new_reg
][GET_MODE (*this->loc
)];
292 for (i
= nregs
- 1; i
>= 0; --i
)
293 if (TEST_HARD_REG_BIT (this_unavailable
, new_reg
+ i
)
294 || fixed_regs
[new_reg
+ i
]
295 || global_regs
[new_reg
+ i
]
296 /* Can't use regs which aren't saved by the prologue. */
297 || (! regs_ever_live
[new_reg
+ i
]
298 && ! call_used_regs
[new_reg
+ i
])
299 #ifdef LEAF_REGISTERS
300 /* We can't use a non-leaf register if we're in a
302 || (current_function_is_leaf
303 && !LEAF_REGISTERS
[new_reg
+ i
])
305 #ifdef HARD_REGNO_RENAME_OK
306 || ! HARD_REGNO_RENAME_OK (reg
+ i
, new_reg
+ i
)
313 /* See whether it accepts all modes that occur in
314 definition and uses. */
315 for (tmp
= this; tmp
; tmp
= tmp
->next_use
)
316 if (! HARD_REGNO_MODE_OK (new_reg
, GET_MODE (*tmp
->loc
))
317 || (tmp
->need_caller_save_reg
318 && ! (HARD_REGNO_CALL_PART_CLOBBERED
319 (reg
, GET_MODE (*tmp
->loc
)))
320 && (HARD_REGNO_CALL_PART_CLOBBERED
321 (new_reg
, GET_MODE (*tmp
->loc
)))))
325 if (tick
[best_new_reg
] > tick
[new_reg
])
326 best_new_reg
= new_reg
;
332 fprintf (dump_file
, "Register %s in insn %d",
333 reg_names
[reg
], INSN_UID (last
->insn
));
334 if (last
->need_caller_save_reg
)
335 fprintf (dump_file
, " crosses a call");
338 if (best_new_reg
== reg
)
340 tick
[reg
] = ++this_tick
;
342 fprintf (dump_file
, "; no available better choice\n");
346 do_replace (this, best_new_reg
);
347 tick
[best_new_reg
] = ++this_tick
;
350 fprintf (dump_file
, ", renamed as %s\n", reg_names
[best_new_reg
]);
353 obstack_free (&rename_obstack
, first_obj
);
356 obstack_free (&rename_obstack
, NULL
);
359 fputc ('\n', dump_file
);
361 count_or_remove_death_notes (NULL
, 1);
362 update_life_info (NULL
, UPDATE_LIFE_LOCAL
,
367 do_replace (struct du_chain
*chain
, int reg
)
371 unsigned int regno
= ORIGINAL_REGNO (*chain
->loc
);
372 struct reg_attrs
* attr
= REG_ATTRS (*chain
->loc
);
374 *chain
->loc
= gen_raw_REG (GET_MODE (*chain
->loc
), reg
);
375 if (regno
>= FIRST_PSEUDO_REGISTER
)
376 ORIGINAL_REGNO (*chain
->loc
) = regno
;
377 REG_ATTRS (*chain
->loc
) = attr
;
378 chain
= chain
->next_use
;
383 static struct du_chain
*open_chains
;
384 static struct du_chain
*closed_chains
;
387 scan_rtx_reg (rtx insn
, rtx
*loc
, enum reg_class
class,
388 enum scan_actions action
, enum op_type type
, int earlyclobber
)
392 enum machine_mode mode
= GET_MODE (x
);
393 int this_regno
= REGNO (x
);
394 int this_nregs
= hard_regno_nregs
[this_regno
][mode
];
396 if (action
== mark_write
)
400 struct du_chain
*this
401 = obstack_alloc (&rename_obstack
, sizeof (struct du_chain
));
403 this->next_chain
= open_chains
;
407 this->need_caller_save_reg
= 0;
408 this->earlyclobber
= earlyclobber
;
414 if ((type
== OP_OUT
&& action
!= terminate_write
)
415 || (type
!= OP_OUT
&& action
== terminate_write
))
418 for (p
= &open_chains
; *p
;)
420 struct du_chain
*this = *p
;
422 /* Check if the chain has been terminated if it has then skip to
425 This can happen when we've already appended the location to
426 the chain in Step 3, but are trying to hide in-out operands
427 from terminate_write in Step 5. */
429 if (*this->loc
== cc0_rtx
)
430 p
= &this->next_chain
;
433 int regno
= REGNO (*this->loc
);
434 int nregs
= hard_regno_nregs
[regno
][GET_MODE (*this->loc
)];
435 int exact_match
= (regno
== this_regno
&& nregs
== this_nregs
);
437 if (regno
+ nregs
<= this_regno
438 || this_regno
+ this_nregs
<= regno
)
440 p
= &this->next_chain
;
444 if (action
== mark_read
)
449 /* ??? Class NO_REGS can happen if the md file makes use of
450 EXTRA_CONSTRAINTS to match registers. Which is arguably
451 wrong, but there we are. Since we know not what this may
452 be replaced with, terminate the chain. */
453 if (class != NO_REGS
)
455 this = obstack_alloc (&rename_obstack
, sizeof (struct du_chain
));
457 this->next_chain
= (*p
)->next_chain
;
461 this->need_caller_save_reg
= 0;
469 if (action
!= terminate_overlapping_read
|| ! exact_match
)
471 struct du_chain
*next
= this->next_chain
;
473 /* Whether the terminated chain can be used for renaming
474 depends on the action and this being an exact match.
475 In either case, we remove this element from open_chains. */
477 if ((action
== terminate_dead
|| action
== terminate_write
)
480 this->next_chain
= closed_chains
;
481 closed_chains
= this;
484 "Closing chain %s at insn %d (%s)\n",
485 reg_names
[REGNO (*this->loc
)], INSN_UID (insn
),
486 scan_actions_name
[(int) action
]);
492 "Discarding chain %s at insn %d (%s)\n",
493 reg_names
[REGNO (*this->loc
)], INSN_UID (insn
),
494 scan_actions_name
[(int) action
]);
499 p
= &this->next_chain
;
504 /* Adapted from find_reloads_address_1. CLASS is INDEX_REG_CLASS or
505 BASE_REG_CLASS depending on how the register is being considered. */
508 scan_rtx_address (rtx insn
, rtx
*loc
, enum reg_class
class,
509 enum scan_actions action
, enum machine_mode mode
)
512 RTX_CODE code
= GET_CODE (x
);
516 if (action
== mark_write
)
523 rtx orig_op0
= XEXP (x
, 0);
524 rtx orig_op1
= XEXP (x
, 1);
525 RTX_CODE code0
= GET_CODE (orig_op0
);
526 RTX_CODE code1
= GET_CODE (orig_op1
);
532 if (GET_CODE (op0
) == SUBREG
)
534 op0
= SUBREG_REG (op0
);
535 code0
= GET_CODE (op0
);
538 if (GET_CODE (op1
) == SUBREG
)
540 op1
= SUBREG_REG (op1
);
541 code1
= GET_CODE (op1
);
544 if (code0
== MULT
|| code0
== SIGN_EXTEND
|| code0
== TRUNCATE
545 || code0
== ZERO_EXTEND
|| code1
== MEM
)
550 else if (code1
== MULT
|| code1
== SIGN_EXTEND
|| code1
== TRUNCATE
551 || code1
== ZERO_EXTEND
|| code0
== MEM
)
556 else if (code0
== CONST_INT
|| code0
== CONST
557 || code0
== SYMBOL_REF
|| code0
== LABEL_REF
)
559 else if (code1
== CONST_INT
|| code1
== CONST
560 || code1
== SYMBOL_REF
|| code1
== LABEL_REF
)
562 else if (code0
== REG
&& code1
== REG
)
566 if (REG_OK_FOR_INDEX_P (op0
)
567 && REG_MODE_OK_FOR_BASE_P (op1
, mode
))
569 else if (REG_OK_FOR_INDEX_P (op1
)
570 && REG_MODE_OK_FOR_BASE_P (op0
, mode
))
572 else if (REG_MODE_OK_FOR_BASE_P (op1
, mode
))
574 else if (REG_MODE_OK_FOR_BASE_P (op0
, mode
))
576 else if (REG_OK_FOR_INDEX_P (op1
))
581 locI
= &XEXP (x
, index_op
);
582 locB
= &XEXP (x
, !index_op
);
584 else if (code0
== REG
)
589 else if (code1
== REG
)
596 scan_rtx_address (insn
, locI
, INDEX_REG_CLASS
, action
, mode
);
598 scan_rtx_address (insn
, locB
, MODE_BASE_REG_CLASS (mode
), action
, mode
);
609 /* If the target doesn't claim to handle autoinc, this must be
610 something special, like a stack push. Kill this chain. */
611 action
= terminate_all_read
;
616 scan_rtx_address (insn
, &XEXP (x
, 0),
617 MODE_BASE_REG_CLASS (GET_MODE (x
)), action
,
622 scan_rtx_reg (insn
, loc
, class, action
, OP_IN
, 0);
629 fmt
= GET_RTX_FORMAT (code
);
630 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
633 scan_rtx_address (insn
, &XEXP (x
, i
), class, action
, mode
);
634 else if (fmt
[i
] == 'E')
635 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
636 scan_rtx_address (insn
, &XVECEXP (x
, i
, j
), class, action
, mode
);
641 scan_rtx (rtx insn
, rtx
*loc
, enum reg_class
class,
642 enum scan_actions action
, enum op_type type
, int earlyclobber
)
646 enum rtx_code code
= GET_CODE (x
);
663 scan_rtx_reg (insn
, loc
, class, action
, type
, earlyclobber
);
667 scan_rtx_address (insn
, &XEXP (x
, 0),
668 MODE_BASE_REG_CLASS (GET_MODE (x
)), action
,
673 scan_rtx (insn
, &SET_SRC (x
), class, action
, OP_IN
, 0);
674 scan_rtx (insn
, &SET_DEST (x
), class, action
, OP_OUT
, 0);
677 case STRICT_LOW_PART
:
678 scan_rtx (insn
, &XEXP (x
, 0), class, action
, OP_INOUT
, earlyclobber
);
683 scan_rtx (insn
, &XEXP (x
, 0), class, action
,
684 type
== OP_IN
? OP_IN
: OP_INOUT
, earlyclobber
);
685 scan_rtx (insn
, &XEXP (x
, 1), class, action
, OP_IN
, 0);
686 scan_rtx (insn
, &XEXP (x
, 2), class, action
, OP_IN
, 0);
695 /* Should only happen inside MEM. */
699 scan_rtx (insn
, &SET_DEST (x
), class, action
, OP_OUT
, 1);
703 scan_rtx (insn
, &XEXP (x
, 0), class, action
, type
, 0);
705 scan_rtx (insn
, &XEXP (x
, 1), class, action
, type
, 0);
712 fmt
= GET_RTX_FORMAT (code
);
713 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
716 scan_rtx (insn
, &XEXP (x
, i
), class, action
, type
, 0);
717 else if (fmt
[i
] == 'E')
718 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
719 scan_rtx (insn
, &XVECEXP (x
, i
, j
), class, action
, type
, 0);
723 /* Build def/use chain. */
725 static struct du_chain
*
726 build_def_use (basic_block bb
)
730 open_chains
= closed_chains
= NULL
;
732 for (insn
= BB_HEAD (bb
); ; insn
= NEXT_INSN (insn
))
738 rtx old_operands
[MAX_RECOG_OPERANDS
];
739 rtx old_dups
[MAX_DUP_OPERANDS
];
744 /* Process the insn, determining its effect on the def-use
745 chains. We perform the following steps with the register
746 references in the insn:
747 (1) Any read that overlaps an open chain, but doesn't exactly
748 match, causes that chain to be closed. We can't deal
750 (2) Any read outside an operand causes any chain it overlaps
751 with to be closed, since we can't replace it.
752 (3) Any read inside an operand is added if there's already
753 an open chain for it.
754 (4) For any REG_DEAD note we find, close open chains that
756 (5) For any write we find, close open chains that overlap it.
757 (6) For any write we find in an operand, make a new chain.
758 (7) For any REG_UNUSED, close any chains we just opened. */
760 icode
= recog_memoized (insn
);
762 if (! constrain_operands (1))
763 fatal_insn_not_found (insn
);
764 preprocess_constraints ();
765 alt
= which_alternative
;
766 n_ops
= recog_data
.n_operands
;
768 /* Simplify the code below by rewriting things to reflect
769 matching constraints. Also promote OP_OUT to OP_INOUT
770 in predicated instructions. */
772 predicated
= GET_CODE (PATTERN (insn
)) == COND_EXEC
;
773 for (i
= 0; i
< n_ops
; ++i
)
775 int matches
= recog_op_alt
[i
][alt
].matches
;
777 recog_op_alt
[i
][alt
].class = recog_op_alt
[matches
][alt
].class;
778 if (matches
>= 0 || recog_op_alt
[i
][alt
].matched
>= 0
779 || (predicated
&& recog_data
.operand_type
[i
] == OP_OUT
))
780 recog_data
.operand_type
[i
] = OP_INOUT
;
783 /* Step 1: Close chains for which we have overlapping reads. */
784 for (i
= 0; i
< n_ops
; i
++)
785 scan_rtx (insn
, recog_data
.operand_loc
[i
],
786 NO_REGS
, terminate_overlapping_read
,
787 recog_data
.operand_type
[i
], 0);
789 /* Step 2: Close chains for which we have reads outside operands.
790 We do this by munging all operands into CC0, and closing
791 everything remaining. */
793 for (i
= 0; i
< n_ops
; i
++)
795 old_operands
[i
] = recog_data
.operand
[i
];
796 /* Don't squash match_operator or match_parallel here, since
797 we don't know that all of the contained registers are
798 reachable by proper operands. */
799 if (recog_data
.constraints
[i
][0] == '\0')
801 *recog_data
.operand_loc
[i
] = cc0_rtx
;
803 for (i
= 0; i
< recog_data
.n_dups
; i
++)
805 int dup_num
= recog_data
.dup_num
[i
];
807 old_dups
[i
] = *recog_data
.dup_loc
[i
];
808 *recog_data
.dup_loc
[i
] = cc0_rtx
;
810 /* For match_dup of match_operator or match_parallel, share
811 them, so that we don't miss changes in the dup. */
813 && insn_data
[icode
].operand
[dup_num
].eliminable
== 0)
814 old_dups
[i
] = recog_data
.operand
[dup_num
];
817 scan_rtx (insn
, &PATTERN (insn
), NO_REGS
, terminate_all_read
,
820 for (i
= 0; i
< recog_data
.n_dups
; i
++)
821 *recog_data
.dup_loc
[i
] = old_dups
[i
];
822 for (i
= 0; i
< n_ops
; i
++)
823 *recog_data
.operand_loc
[i
] = old_operands
[i
];
825 /* Step 2B: Can't rename function call argument registers. */
826 if (GET_CODE (insn
) == CALL_INSN
&& CALL_INSN_FUNCTION_USAGE (insn
))
827 scan_rtx (insn
, &CALL_INSN_FUNCTION_USAGE (insn
),
828 NO_REGS
, terminate_all_read
, OP_IN
, 0);
830 /* Step 2C: Can't rename asm operands that were originally
832 if (asm_noperands (PATTERN (insn
)) > 0)
833 for (i
= 0; i
< n_ops
; i
++)
835 rtx
*loc
= recog_data
.operand_loc
[i
];
838 if (GET_CODE (op
) == REG
839 && REGNO (op
) == ORIGINAL_REGNO (op
)
840 && (recog_data
.operand_type
[i
] == OP_IN
841 || recog_data
.operand_type
[i
] == OP_INOUT
))
842 scan_rtx (insn
, loc
, NO_REGS
, terminate_all_read
, OP_IN
, 0);
845 /* Step 3: Append to chains for reads inside operands. */
846 for (i
= 0; i
< n_ops
+ recog_data
.n_dups
; i
++)
848 int opn
= i
< n_ops
? i
: recog_data
.dup_num
[i
- n_ops
];
849 rtx
*loc
= (i
< n_ops
850 ? recog_data
.operand_loc
[opn
]
851 : recog_data
.dup_loc
[i
- n_ops
]);
852 enum reg_class
class = recog_op_alt
[opn
][alt
].class;
853 enum op_type type
= recog_data
.operand_type
[opn
];
855 /* Don't scan match_operand here, since we've no reg class
856 information to pass down. Any operands that we could
857 substitute in will be represented elsewhere. */
858 if (recog_data
.constraints
[opn
][0] == '\0')
861 if (recog_op_alt
[opn
][alt
].is_address
)
862 scan_rtx_address (insn
, loc
, class, mark_read
, VOIDmode
);
864 scan_rtx (insn
, loc
, class, mark_read
, type
, 0);
867 /* Step 4: Close chains for registers that die here.
868 Also record updates for REG_INC notes. */
869 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
871 if (REG_NOTE_KIND (note
) == REG_DEAD
)
872 scan_rtx (insn
, &XEXP (note
, 0), NO_REGS
, terminate_dead
,
874 else if (REG_NOTE_KIND (note
) == REG_INC
)
875 scan_rtx (insn
, &XEXP (note
, 0), ALL_REGS
, mark_read
,
879 /* Step 4B: If this is a call, any chain live at this point
880 requires a caller-saved reg. */
881 if (GET_CODE (insn
) == CALL_INSN
)
884 for (p
= open_chains
; p
; p
= p
->next_chain
)
885 p
->need_caller_save_reg
= 1;
888 /* Step 5: Close open chains that overlap writes. Similar to
889 step 2, we hide in-out operands, since we do not want to
890 close these chains. */
892 for (i
= 0; i
< n_ops
; i
++)
894 old_operands
[i
] = recog_data
.operand
[i
];
895 if (recog_data
.operand_type
[i
] == OP_INOUT
)
896 *recog_data
.operand_loc
[i
] = cc0_rtx
;
898 for (i
= 0; i
< recog_data
.n_dups
; i
++)
900 int opn
= recog_data
.dup_num
[i
];
901 old_dups
[i
] = *recog_data
.dup_loc
[i
];
902 if (recog_data
.operand_type
[opn
] == OP_INOUT
)
903 *recog_data
.dup_loc
[i
] = cc0_rtx
;
906 scan_rtx (insn
, &PATTERN (insn
), NO_REGS
, terminate_write
, OP_IN
, 0);
908 for (i
= 0; i
< recog_data
.n_dups
; i
++)
909 *recog_data
.dup_loc
[i
] = old_dups
[i
];
910 for (i
= 0; i
< n_ops
; i
++)
911 *recog_data
.operand_loc
[i
] = old_operands
[i
];
913 /* Step 6: Begin new chains for writes inside operands. */
914 /* ??? Many targets have output constraints on the SET_DEST
915 of a call insn, which is stupid, since these are certainly
916 ABI defined hard registers. Don't change calls at all.
917 Similarly take special care for asm statement that originally
918 referenced hard registers. */
919 if (asm_noperands (PATTERN (insn
)) > 0)
921 for (i
= 0; i
< n_ops
; i
++)
922 if (recog_data
.operand_type
[i
] == OP_OUT
)
924 rtx
*loc
= recog_data
.operand_loc
[i
];
926 enum reg_class
class = recog_op_alt
[i
][alt
].class;
928 if (GET_CODE (op
) == REG
929 && REGNO (op
) == ORIGINAL_REGNO (op
))
932 scan_rtx (insn
, loc
, class, mark_write
, OP_OUT
,
933 recog_op_alt
[i
][alt
].earlyclobber
);
936 else if (GET_CODE (insn
) != CALL_INSN
)
937 for (i
= 0; i
< n_ops
+ recog_data
.n_dups
; i
++)
939 int opn
= i
< n_ops
? i
: recog_data
.dup_num
[i
- n_ops
];
940 rtx
*loc
= (i
< n_ops
941 ? recog_data
.operand_loc
[opn
]
942 : recog_data
.dup_loc
[i
- n_ops
]);
943 enum reg_class
class = recog_op_alt
[opn
][alt
].class;
945 if (recog_data
.operand_type
[opn
] == OP_OUT
)
946 scan_rtx (insn
, loc
, class, mark_write
, OP_OUT
,
947 recog_op_alt
[opn
][alt
].earlyclobber
);
950 /* Step 7: Close chains for registers that were never
952 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
953 if (REG_NOTE_KIND (note
) == REG_UNUSED
)
954 scan_rtx (insn
, &XEXP (note
, 0), NO_REGS
, terminate_dead
,
957 if (insn
== BB_END (bb
))
961 /* Since we close every chain when we find a REG_DEAD note, anything that
962 is still open lives past the basic block, so it can't be renamed. */
963 return closed_chains
;
966 /* Dump all def/use chains in CHAINS to DUMP_FILE. They are
967 printed in reverse order as that's how we build them. */
970 dump_def_use_chain (struct du_chain
*chains
)
974 struct du_chain
*this = chains
;
975 int r
= REGNO (*this->loc
);
976 int nregs
= hard_regno_nregs
[r
][GET_MODE (*this->loc
)];
977 fprintf (dump_file
, "Register %s (%d):", reg_names
[r
], nregs
);
980 fprintf (dump_file
, " %d [%s]", INSN_UID (this->insn
),
981 reg_class_names
[this->class]);
982 this = this->next_use
;
984 fprintf (dump_file
, "\n");
985 chains
= chains
->next_chain
;
989 /* The following code does forward propagation of hard register copies.
990 The object is to eliminate as many dependencies as possible, so that
991 we have the most scheduling freedom. As a side effect, we also clean
992 up some silly register allocation decisions made by reload. This
993 code may be obsoleted by a new register allocator. */
995 /* For each register, we have a list of registers that contain the same
996 value. The OLDEST_REGNO field points to the head of the list, and
997 the NEXT_REGNO field runs through the list. The MODE field indicates
998 what mode the data is known to be in; this field is VOIDmode when the
999 register is not known to contain valid data. */
1001 struct value_data_entry
1003 enum machine_mode mode
;
1004 unsigned int oldest_regno
;
1005 unsigned int next_regno
;
1010 struct value_data_entry e
[FIRST_PSEUDO_REGISTER
];
1011 unsigned int max_value_regs
;
1014 static void kill_value_regno (unsigned, struct value_data
*);
1015 static void kill_value (rtx
, struct value_data
*);
1016 static void set_value_regno (unsigned, enum machine_mode
, struct value_data
*);
1017 static void init_value_data (struct value_data
*);
1018 static void kill_clobbered_value (rtx
, rtx
, void *);
1019 static void kill_set_value (rtx
, rtx
, void *);
1020 static int kill_autoinc_value (rtx
*, void *);
1021 static void copy_value (rtx
, rtx
, struct value_data
*);
1022 static bool mode_change_ok (enum machine_mode
, enum machine_mode
,
1024 static rtx
maybe_mode_change (enum machine_mode
, enum machine_mode
,
1025 enum machine_mode
, unsigned int, unsigned int);
1026 static rtx
find_oldest_value_reg (enum reg_class
, rtx
, struct value_data
*);
1027 static bool replace_oldest_value_reg (rtx
*, enum reg_class
, rtx
,
1028 struct value_data
*);
1029 static bool replace_oldest_value_addr (rtx
*, enum reg_class
,
1030 enum machine_mode
, rtx
,
1031 struct value_data
*);
1032 static bool replace_oldest_value_mem (rtx
, rtx
, struct value_data
*);
1033 static bool copyprop_hardreg_forward_1 (basic_block
, struct value_data
*);
1034 extern void debug_value_data (struct value_data
*);
1035 #ifdef ENABLE_CHECKING
1036 static void validate_value_data (struct value_data
*);
1039 /* Kill register REGNO. This involves removing it from any value lists,
1040 and resetting the value mode to VOIDmode. */
1043 kill_value_regno (unsigned int regno
, struct value_data
*vd
)
1045 unsigned int i
, next
;
1047 if (vd
->e
[regno
].oldest_regno
!= regno
)
1049 for (i
= vd
->e
[regno
].oldest_regno
;
1050 vd
->e
[i
].next_regno
!= regno
;
1051 i
= vd
->e
[i
].next_regno
)
1053 vd
->e
[i
].next_regno
= vd
->e
[regno
].next_regno
;
1055 else if ((next
= vd
->e
[regno
].next_regno
) != INVALID_REGNUM
)
1057 for (i
= next
; i
!= INVALID_REGNUM
; i
= vd
->e
[i
].next_regno
)
1058 vd
->e
[i
].oldest_regno
= next
;
1061 vd
->e
[regno
].mode
= VOIDmode
;
1062 vd
->e
[regno
].oldest_regno
= regno
;
1063 vd
->e
[regno
].next_regno
= INVALID_REGNUM
;
1065 #ifdef ENABLE_CHECKING
1066 validate_value_data (vd
);
1070 /* Kill X. This is a convenience function for kill_value_regno
1071 so that we mind the mode the register is in. */
1074 kill_value (rtx x
, struct value_data
*vd
)
1076 /* SUBREGS are supposed to have been eliminated by now. But some
1077 ports, e.g. i386 sse, use them to smuggle vector type information
1078 through to instruction selection. Each such SUBREG should simplify,
1079 so if we get a NULL we've done something wrong elsewhere. */
1081 if (GET_CODE (x
) == SUBREG
)
1082 x
= simplify_subreg (GET_MODE (x
), SUBREG_REG (x
),
1083 GET_MODE (SUBREG_REG (x
)), SUBREG_BYTE (x
));
1086 unsigned int regno
= REGNO (x
);
1087 unsigned int n
= hard_regno_nregs
[regno
][GET_MODE (x
)];
1090 /* Kill the value we're told to kill. */
1091 for (i
= 0; i
< n
; ++i
)
1092 kill_value_regno (regno
+ i
, vd
);
1094 /* Kill everything that overlapped what we're told to kill. */
1095 if (regno
< vd
->max_value_regs
)
1098 j
= regno
- vd
->max_value_regs
;
1099 for (; j
< regno
; ++j
)
1101 if (vd
->e
[j
].mode
== VOIDmode
)
1103 n
= hard_regno_nregs
[j
][vd
->e
[j
].mode
];
1105 for (i
= 0; i
< n
; ++i
)
1106 kill_value_regno (j
+ i
, vd
);
1111 /* Remember that REGNO is valid in MODE. */
1114 set_value_regno (unsigned int regno
, enum machine_mode mode
,
1115 struct value_data
*vd
)
1119 vd
->e
[regno
].mode
= mode
;
1121 nregs
= hard_regno_nregs
[regno
][mode
];
1122 if (nregs
> vd
->max_value_regs
)
1123 vd
->max_value_regs
= nregs
;
1126 /* Initialize VD such that there are no known relationships between regs. */
1129 init_value_data (struct value_data
*vd
)
1132 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1134 vd
->e
[i
].mode
= VOIDmode
;
1135 vd
->e
[i
].oldest_regno
= i
;
1136 vd
->e
[i
].next_regno
= INVALID_REGNUM
;
1138 vd
->max_value_regs
= 0;
1141 /* Called through note_stores. If X is clobbered, kill its value. */
1144 kill_clobbered_value (rtx x
, rtx set
, void *data
)
1146 struct value_data
*vd
= data
;
1147 if (GET_CODE (set
) == CLOBBER
)
1151 /* Called through note_stores. If X is set, not clobbered, kill its
1152 current value and install it as the root of its own value list. */
1155 kill_set_value (rtx x
, rtx set
, void *data
)
1157 struct value_data
*vd
= data
;
1158 if (GET_CODE (set
) != CLOBBER
)
1162 set_value_regno (REGNO (x
), GET_MODE (x
), vd
);
1166 /* Called through for_each_rtx. Kill any register used as the base of an
1167 auto-increment expression, and install that register as the root of its
1171 kill_autoinc_value (rtx
*px
, void *data
)
1174 struct value_data
*vd
= data
;
1176 if (GET_RTX_CLASS (GET_CODE (x
)) == RTX_AUTOINC
)
1180 set_value_regno (REGNO (x
), Pmode
, vd
);
1187 /* Assert that SRC has been copied to DEST. Adjust the data structures
1188 to reflect that SRC contains an older copy of the shared value. */
1191 copy_value (rtx dest
, rtx src
, struct value_data
*vd
)
1193 unsigned int dr
= REGNO (dest
);
1194 unsigned int sr
= REGNO (src
);
1195 unsigned int dn
, sn
;
1198 /* ??? At present, it's possible to see noop sets. It'd be nice if
1199 this were cleaned up beforehand... */
1203 /* Do not propagate copies to the stack pointer, as that can leave
1204 memory accesses with no scheduling dependency on the stack update. */
1205 if (dr
== STACK_POINTER_REGNUM
)
1208 /* Likewise with the frame pointer, if we're using one. */
1209 if (frame_pointer_needed
&& dr
== HARD_FRAME_POINTER_REGNUM
)
1212 /* If SRC and DEST overlap, don't record anything. */
1213 dn
= hard_regno_nregs
[dr
][GET_MODE (dest
)];
1214 sn
= hard_regno_nregs
[sr
][GET_MODE (dest
)];
1215 if ((dr
> sr
&& dr
< sr
+ sn
)
1216 || (sr
> dr
&& sr
< dr
+ dn
))
1219 /* If SRC had no assigned mode (i.e. we didn't know it was live)
1220 assign it now and assume the value came from an input argument
1222 if (vd
->e
[sr
].mode
== VOIDmode
)
1223 set_value_regno (sr
, vd
->e
[dr
].mode
, vd
);
1225 /* If we are narrowing the input to a smaller number of hard regs,
1226 and it is in big endian, we are really extracting a high part.
1227 Since we generally associate a low part of a value with the value itself,
1228 we must not do the same for the high part.
1229 Note we can still get low parts for the same mode combination through
1230 a two-step copy involving differently sized hard regs.
1231 Assume hard regs fr* are 32 bits bits each, while r* are 64 bits each:
1232 (set (reg:DI r0) (reg:DI fr0))
1233 (set (reg:SI fr2) (reg:SI r0))
1234 loads the low part of (reg:DI fr0) - i.e. fr1 - into fr2, while:
1235 (set (reg:SI fr2) (reg:SI fr0))
1236 loads the high part of (reg:DI fr0) into fr2.
1238 We can't properly represent the latter case in our tables, so don't
1239 record anything then. */
1240 else if (sn
< (unsigned int) hard_regno_nregs
[sr
][vd
->e
[sr
].mode
]
1241 && (GET_MODE_SIZE (vd
->e
[sr
].mode
) > UNITS_PER_WORD
1242 ? WORDS_BIG_ENDIAN
: BYTES_BIG_ENDIAN
))
1245 /* If SRC had been assigned a mode narrower than the copy, we can't
1246 link DEST into the chain, because not all of the pieces of the
1247 copy came from oldest_regno. */
1248 else if (sn
> (unsigned int) hard_regno_nregs
[sr
][vd
->e
[sr
].mode
])
1251 /* Link DR at the end of the value chain used by SR. */
1253 vd
->e
[dr
].oldest_regno
= vd
->e
[sr
].oldest_regno
;
1255 for (i
= sr
; vd
->e
[i
].next_regno
!= INVALID_REGNUM
; i
= vd
->e
[i
].next_regno
)
1257 vd
->e
[i
].next_regno
= dr
;
1259 #ifdef ENABLE_CHECKING
1260 validate_value_data (vd
);
1264 /* Return true if a mode change from ORIG to NEW is allowed for REGNO. */
1267 mode_change_ok (enum machine_mode orig_mode
, enum machine_mode new_mode
,
1268 unsigned int regno ATTRIBUTE_UNUSED
)
1270 if (GET_MODE_SIZE (orig_mode
) < GET_MODE_SIZE (new_mode
))
1273 #ifdef CANNOT_CHANGE_MODE_CLASS
1274 return !REG_CANNOT_CHANGE_MODE_P (regno
, orig_mode
, new_mode
);
1280 /* Register REGNO was originally set in ORIG_MODE. It - or a copy of it -
1281 was copied in COPY_MODE to COPY_REGNO, and then COPY_REGNO was accessed
1283 Return a NEW_MODE rtx for REGNO if that's OK, otherwise return NULL_RTX. */
1286 maybe_mode_change (enum machine_mode orig_mode
, enum machine_mode copy_mode
,
1287 enum machine_mode new_mode
, unsigned int regno
,
1288 unsigned int copy_regno ATTRIBUTE_UNUSED
)
1290 if (orig_mode
== new_mode
)
1291 return gen_rtx_raw_REG (new_mode
, regno
);
1292 else if (mode_change_ok (orig_mode
, new_mode
, regno
))
1294 int copy_nregs
= hard_regno_nregs
[copy_regno
][copy_mode
];
1295 int use_nregs
= hard_regno_nregs
[copy_regno
][new_mode
];
1297 = GET_MODE_SIZE (copy_mode
) / copy_nregs
* (copy_nregs
- use_nregs
);
1299 = GET_MODE_SIZE (orig_mode
) - GET_MODE_SIZE (new_mode
) - copy_offset
;
1300 int byteoffset
= offset
% UNITS_PER_WORD
;
1301 int wordoffset
= offset
- byteoffset
;
1303 offset
= ((WORDS_BIG_ENDIAN
? wordoffset
: 0)
1304 + (BYTES_BIG_ENDIAN
? byteoffset
: 0));
1305 return gen_rtx_raw_REG (new_mode
,
1306 regno
+ subreg_regno_offset (regno
, orig_mode
,
1313 /* Find the oldest copy of the value contained in REGNO that is in
1314 register class CLASS and has mode MODE. If found, return an rtx
1315 of that oldest register, otherwise return NULL. */
1318 find_oldest_value_reg (enum reg_class
class, rtx reg
, struct value_data
*vd
)
1320 unsigned int regno
= REGNO (reg
);
1321 enum machine_mode mode
= GET_MODE (reg
);
1324 /* If we are accessing REG in some mode other that what we set it in,
1325 make sure that the replacement is valid. In particular, consider
1326 (set (reg:DI r11) (...))
1327 (set (reg:SI r9) (reg:SI r11))
1328 (set (reg:SI r10) (...))
1329 (set (...) (reg:DI r9))
1330 Replacing r9 with r11 is invalid. */
1331 if (mode
!= vd
->e
[regno
].mode
)
1333 if (hard_regno_nregs
[regno
][mode
]
1334 > hard_regno_nregs
[regno
][vd
->e
[regno
].mode
])
1338 for (i
= vd
->e
[regno
].oldest_regno
; i
!= regno
; i
= vd
->e
[i
].next_regno
)
1340 enum machine_mode oldmode
= vd
->e
[i
].mode
;
1344 for (last
= i
; last
< i
+ hard_regno_nregs
[i
][mode
]; last
++)
1345 if (!TEST_HARD_REG_BIT (reg_class_contents
[class], last
))
1348 new = maybe_mode_change (oldmode
, vd
->e
[regno
].mode
, mode
, i
, regno
);
1351 ORIGINAL_REGNO (new) = ORIGINAL_REGNO (reg
);
1352 REG_ATTRS (new) = REG_ATTRS (reg
);
1360 /* If possible, replace the register at *LOC with the oldest register
1361 in register class CLASS. Return true if successfully replaced. */
1364 replace_oldest_value_reg (rtx
*loc
, enum reg_class
class, rtx insn
,
1365 struct value_data
*vd
)
1367 rtx
new = find_oldest_value_reg (class, *loc
, vd
);
1371 fprintf (dump_file
, "insn %u: replaced reg %u with %u\n",
1372 INSN_UID (insn
), REGNO (*loc
), REGNO (new));
1380 /* Similar to replace_oldest_value_reg, but *LOC contains an address.
1381 Adapted from find_reloads_address_1. CLASS is INDEX_REG_CLASS or
1382 BASE_REG_CLASS depending on how the register is being considered. */
1385 replace_oldest_value_addr (rtx
*loc
, enum reg_class
class,
1386 enum machine_mode mode
, rtx insn
,
1387 struct value_data
*vd
)
1390 RTX_CODE code
= GET_CODE (x
);
1393 bool changed
= false;
1399 rtx orig_op0
= XEXP (x
, 0);
1400 rtx orig_op1
= XEXP (x
, 1);
1401 RTX_CODE code0
= GET_CODE (orig_op0
);
1402 RTX_CODE code1
= GET_CODE (orig_op1
);
1408 if (GET_CODE (op0
) == SUBREG
)
1410 op0
= SUBREG_REG (op0
);
1411 code0
= GET_CODE (op0
);
1414 if (GET_CODE (op1
) == SUBREG
)
1416 op1
= SUBREG_REG (op1
);
1417 code1
= GET_CODE (op1
);
1420 if (code0
== MULT
|| code0
== SIGN_EXTEND
|| code0
== TRUNCATE
1421 || code0
== ZERO_EXTEND
|| code1
== MEM
)
1423 locI
= &XEXP (x
, 0);
1424 locB
= &XEXP (x
, 1);
1426 else if (code1
== MULT
|| code1
== SIGN_EXTEND
|| code1
== TRUNCATE
1427 || code1
== ZERO_EXTEND
|| code0
== MEM
)
1429 locI
= &XEXP (x
, 1);
1430 locB
= &XEXP (x
, 0);
1432 else if (code0
== CONST_INT
|| code0
== CONST
1433 || code0
== SYMBOL_REF
|| code0
== LABEL_REF
)
1434 locB
= &XEXP (x
, 1);
1435 else if (code1
== CONST_INT
|| code1
== CONST
1436 || code1
== SYMBOL_REF
|| code1
== LABEL_REF
)
1437 locB
= &XEXP (x
, 0);
1438 else if (code0
== REG
&& code1
== REG
)
1442 if (REG_OK_FOR_INDEX_P (op0
)
1443 && REG_MODE_OK_FOR_BASE_P (op1
, mode
))
1445 else if (REG_OK_FOR_INDEX_P (op1
)
1446 && REG_MODE_OK_FOR_BASE_P (op0
, mode
))
1448 else if (REG_MODE_OK_FOR_BASE_P (op1
, mode
))
1450 else if (REG_MODE_OK_FOR_BASE_P (op0
, mode
))
1452 else if (REG_OK_FOR_INDEX_P (op1
))
1457 locI
= &XEXP (x
, index_op
);
1458 locB
= &XEXP (x
, !index_op
);
1460 else if (code0
== REG
)
1462 locI
= &XEXP (x
, 0);
1463 locB
= &XEXP (x
, 1);
1465 else if (code1
== REG
)
1467 locI
= &XEXP (x
, 1);
1468 locB
= &XEXP (x
, 0);
1472 changed
|= replace_oldest_value_addr (locI
, INDEX_REG_CLASS
, mode
,
1475 changed
|= replace_oldest_value_addr (locB
,
1476 MODE_BASE_REG_CLASS (mode
),
1490 return replace_oldest_value_mem (x
, insn
, vd
);
1493 return replace_oldest_value_reg (loc
, class, insn
, vd
);
1499 fmt
= GET_RTX_FORMAT (code
);
1500 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1503 changed
|= replace_oldest_value_addr (&XEXP (x
, i
), class, mode
,
1505 else if (fmt
[i
] == 'E')
1506 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
1507 changed
|= replace_oldest_value_addr (&XVECEXP (x
, i
, j
), class,
1514 /* Similar to replace_oldest_value_reg, but X contains a memory. */
1517 replace_oldest_value_mem (rtx x
, rtx insn
, struct value_data
*vd
)
1519 return replace_oldest_value_addr (&XEXP (x
, 0),
1520 MODE_BASE_REG_CLASS (GET_MODE (x
)),
1521 GET_MODE (x
), insn
, vd
);
1524 /* Perform the forward copy propagation on basic block BB. */
1527 copyprop_hardreg_forward_1 (basic_block bb
, struct value_data
*vd
)
1529 bool changed
= false;
1532 for (insn
= BB_HEAD (bb
); ; insn
= NEXT_INSN (insn
))
1534 int n_ops
, i
, alt
, predicated
;
1538 if (! INSN_P (insn
))
1540 if (insn
== BB_END (bb
))
1546 set
= single_set (insn
);
1547 extract_insn (insn
);
1548 if (! constrain_operands (1))
1549 fatal_insn_not_found (insn
);
1550 preprocess_constraints ();
1551 alt
= which_alternative
;
1552 n_ops
= recog_data
.n_operands
;
1553 is_asm
= asm_noperands (PATTERN (insn
)) >= 0;
1555 /* Simplify the code below by rewriting things to reflect
1556 matching constraints. Also promote OP_OUT to OP_INOUT
1557 in predicated instructions. */
1559 predicated
= GET_CODE (PATTERN (insn
)) == COND_EXEC
;
1560 for (i
= 0; i
< n_ops
; ++i
)
1562 int matches
= recog_op_alt
[i
][alt
].matches
;
1564 recog_op_alt
[i
][alt
].class = recog_op_alt
[matches
][alt
].class;
1565 if (matches
>= 0 || recog_op_alt
[i
][alt
].matched
>= 0
1566 || (predicated
&& recog_data
.operand_type
[i
] == OP_OUT
))
1567 recog_data
.operand_type
[i
] = OP_INOUT
;
1570 /* For each earlyclobber operand, zap the value data. */
1571 for (i
= 0; i
< n_ops
; i
++)
1572 if (recog_op_alt
[i
][alt
].earlyclobber
)
1573 kill_value (recog_data
.operand
[i
], vd
);
1575 /* Within asms, a clobber cannot overlap inputs or outputs.
1576 I wouldn't think this were true for regular insns, but
1577 scan_rtx treats them like that... */
1578 note_stores (PATTERN (insn
), kill_clobbered_value
, vd
);
1580 /* Kill all auto-incremented values. */
1581 /* ??? REG_INC is useless, since stack pushes aren't done that way. */
1582 for_each_rtx (&PATTERN (insn
), kill_autoinc_value
, vd
);
1584 /* Kill all early-clobbered operands. */
1585 for (i
= 0; i
< n_ops
; i
++)
1586 if (recog_op_alt
[i
][alt
].earlyclobber
)
1587 kill_value (recog_data
.operand
[i
], vd
);
1589 /* Special-case plain move instructions, since we may well
1590 be able to do the move from a different register class. */
1591 if (set
&& REG_P (SET_SRC (set
)))
1593 rtx src
= SET_SRC (set
);
1594 unsigned int regno
= REGNO (src
);
1595 enum machine_mode mode
= GET_MODE (src
);
1599 /* If we are accessing SRC in some mode other that what we
1600 set it in, make sure that the replacement is valid. */
1601 if (mode
!= vd
->e
[regno
].mode
)
1603 if (hard_regno_nregs
[regno
][mode
]
1604 > hard_regno_nregs
[regno
][vd
->e
[regno
].mode
])
1605 goto no_move_special_case
;
1608 /* If the destination is also a register, try to find a source
1609 register in the same class. */
1610 if (REG_P (SET_DEST (set
)))
1612 new = find_oldest_value_reg (REGNO_REG_CLASS (regno
), src
, vd
);
1613 if (new && validate_change (insn
, &SET_SRC (set
), new, 0))
1617 "insn %u: replaced reg %u with %u\n",
1618 INSN_UID (insn
), regno
, REGNO (new));
1620 goto did_replacement
;
1624 /* Otherwise, try all valid registers and see if its valid. */
1625 for (i
= vd
->e
[regno
].oldest_regno
; i
!= regno
;
1626 i
= vd
->e
[i
].next_regno
)
1628 new = maybe_mode_change (vd
->e
[i
].mode
, vd
->e
[regno
].mode
,
1630 if (new != NULL_RTX
)
1632 if (validate_change (insn
, &SET_SRC (set
), new, 0))
1634 ORIGINAL_REGNO (new) = ORIGINAL_REGNO (src
);
1635 REG_ATTRS (new) = REG_ATTRS (src
);
1638 "insn %u: replaced reg %u with %u\n",
1639 INSN_UID (insn
), regno
, REGNO (new));
1641 goto did_replacement
;
1646 no_move_special_case
:
1648 /* For each input operand, replace a hard register with the
1649 eldest live copy that's in an appropriate register class. */
1650 for (i
= 0; i
< n_ops
; i
++)
1652 bool replaced
= false;
1654 /* Don't scan match_operand here, since we've no reg class
1655 information to pass down. Any operands that we could
1656 substitute in will be represented elsewhere. */
1657 if (recog_data
.constraints
[i
][0] == '\0')
1660 /* Don't replace in asms intentionally referencing hard regs. */
1661 if (is_asm
&& GET_CODE (recog_data
.operand
[i
]) == REG
1662 && (REGNO (recog_data
.operand
[i
])
1663 == ORIGINAL_REGNO (recog_data
.operand
[i
])))
1666 if (recog_data
.operand_type
[i
] == OP_IN
)
1668 if (recog_op_alt
[i
][alt
].is_address
)
1670 = replace_oldest_value_addr (recog_data
.operand_loc
[i
],
1671 recog_op_alt
[i
][alt
].class,
1672 VOIDmode
, insn
, vd
);
1673 else if (REG_P (recog_data
.operand
[i
]))
1675 = replace_oldest_value_reg (recog_data
.operand_loc
[i
],
1676 recog_op_alt
[i
][alt
].class,
1678 else if (GET_CODE (recog_data
.operand
[i
]) == MEM
)
1679 replaced
= replace_oldest_value_mem (recog_data
.operand
[i
],
1682 else if (GET_CODE (recog_data
.operand
[i
]) == MEM
)
1683 replaced
= replace_oldest_value_mem (recog_data
.operand
[i
],
1686 /* If we performed any replacement, update match_dups. */
1694 new = *recog_data
.operand_loc
[i
];
1695 recog_data
.operand
[i
] = new;
1696 for (j
= 0; j
< recog_data
.n_dups
; j
++)
1697 if (recog_data
.dup_num
[j
] == i
)
1698 *recog_data
.dup_loc
[j
] = new;
1703 /* Clobber call-clobbered registers. */
1704 if (GET_CODE (insn
) == CALL_INSN
)
1705 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1706 if (TEST_HARD_REG_BIT (regs_invalidated_by_call
, i
))
1707 kill_value_regno (i
, vd
);
1709 /* Notice stores. */
1710 note_stores (PATTERN (insn
), kill_set_value
, vd
);
1712 /* Notice copies. */
1713 if (set
&& REG_P (SET_DEST (set
)) && REG_P (SET_SRC (set
)))
1714 copy_value (SET_DEST (set
), SET_SRC (set
), vd
);
1716 if (insn
== BB_END (bb
))
1723 /* Main entry point for the forward copy propagation optimization. */
1726 copyprop_hardreg_forward (void)
1728 struct value_data
*all_vd
;
1730 basic_block bb
, bbp
= 0;
1732 need_refresh
= false;
1734 all_vd
= xmalloc (sizeof (struct value_data
) * last_basic_block
);
1738 /* If a block has a single predecessor, that we've already
1739 processed, begin with the value data that was live at
1740 the end of the predecessor block. */
1741 /* ??? Ought to use more intelligent queuing of blocks. */
1743 for (bbp
= bb
; bbp
&& bbp
!= bb
->pred
->src
; bbp
= bbp
->prev_bb
);
1745 && ! bb
->pred
->pred_next
1746 && ! (bb
->pred
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
1747 && bb
->pred
->src
!= ENTRY_BLOCK_PTR
1749 all_vd
[bb
->index
] = all_vd
[bb
->pred
->src
->index
];
1751 init_value_data (all_vd
+ bb
->index
);
1753 if (copyprop_hardreg_forward_1 (bb
, all_vd
+ bb
->index
))
1754 need_refresh
= true;
1760 fputs ("\n\n", dump_file
);
1762 /* ??? Irritatingly, delete_noop_moves does not take a set of blocks
1763 to scan, so we have to do a life update with no initial set of
1764 blocks Just In Case. */
1765 delete_noop_moves (get_insns ());
1766 update_life_info (NULL
, UPDATE_LIFE_GLOBAL_RM_NOTES
,
1768 | PROP_SCAN_DEAD_CODE
1769 | PROP_KILL_DEAD_CODE
);
1775 /* Dump the value chain data to stderr. */
1778 debug_value_data (struct value_data
*vd
)
1783 CLEAR_HARD_REG_SET (set
);
1785 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1786 if (vd
->e
[i
].oldest_regno
== i
)
1788 if (vd
->e
[i
].mode
== VOIDmode
)
1790 if (vd
->e
[i
].next_regno
!= INVALID_REGNUM
)
1791 fprintf (stderr
, "[%u] Bad next_regno for empty chain (%u)\n",
1792 i
, vd
->e
[i
].next_regno
);
1796 SET_HARD_REG_BIT (set
, i
);
1797 fprintf (stderr
, "[%u %s] ", i
, GET_MODE_NAME (vd
->e
[i
].mode
));
1799 for (j
= vd
->e
[i
].next_regno
;
1800 j
!= INVALID_REGNUM
;
1801 j
= vd
->e
[j
].next_regno
)
1803 if (TEST_HARD_REG_BIT (set
, j
))
1805 fprintf (stderr
, "[%u] Loop in regno chain\n", j
);
1809 if (vd
->e
[j
].oldest_regno
!= i
)
1811 fprintf (stderr
, "[%u] Bad oldest_regno (%u)\n",
1812 j
, vd
->e
[j
].oldest_regno
);
1815 SET_HARD_REG_BIT (set
, j
);
1816 fprintf (stderr
, "[%u %s] ", j
, GET_MODE_NAME (vd
->e
[j
].mode
));
1818 fputc ('\n', stderr
);
1821 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1822 if (! TEST_HARD_REG_BIT (set
, i
)
1823 && (vd
->e
[i
].mode
!= VOIDmode
1824 || vd
->e
[i
].oldest_regno
!= i
1825 || vd
->e
[i
].next_regno
!= INVALID_REGNUM
))
1826 fprintf (stderr
, "[%u] Non-empty reg in chain (%s %u %i)\n",
1827 i
, GET_MODE_NAME (vd
->e
[i
].mode
), vd
->e
[i
].oldest_regno
,
1828 vd
->e
[i
].next_regno
);
1831 #ifdef ENABLE_CHECKING
1833 validate_value_data (struct value_data
*vd
)
1838 CLEAR_HARD_REG_SET (set
);
1840 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1841 if (vd
->e
[i
].oldest_regno
== i
)
1843 if (vd
->e
[i
].mode
== VOIDmode
)
1845 if (vd
->e
[i
].next_regno
!= INVALID_REGNUM
)
1846 internal_error ("validate_value_data: [%u] Bad next_regno for empty chain (%u)",
1847 i
, vd
->e
[i
].next_regno
);
1851 SET_HARD_REG_BIT (set
, i
);
1853 for (j
= vd
->e
[i
].next_regno
;
1854 j
!= INVALID_REGNUM
;
1855 j
= vd
->e
[j
].next_regno
)
1857 if (TEST_HARD_REG_BIT (set
, j
))
1858 internal_error ("validate_value_data: Loop in regno chain (%u)",
1860 if (vd
->e
[j
].oldest_regno
!= i
)
1861 internal_error ("validate_value_data: [%u] Bad oldest_regno (%u)",
1862 j
, vd
->e
[j
].oldest_regno
);
1864 SET_HARD_REG_BIT (set
, j
);
1868 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1869 if (! TEST_HARD_REG_BIT (set
, i
)
1870 && (vd
->e
[i
].mode
!= VOIDmode
1871 || vd
->e
[i
].oldest_regno
!= i
1872 || vd
->e
[i
].next_regno
!= INVALID_REGNUM
))
1873 internal_error ("validate_value_data: [%u] Non-empty reg in chain (%s %u %i)",
1874 i
, GET_MODE_NAME (vd
->e
[i
].mode
), vd
->e
[i
].oldest_regno
,
1875 vd
->e
[i
].next_regno
);