1 /* Register renaming for the GNU compiler.
2 Copyright (C) 2000, 2001, 2002 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
27 #include "insn-config.h"
29 #include "hard-reg-set.h"
30 #include "basic-block.h"
39 #define obstack_chunk_alloc xmalloc
40 #define obstack_chunk_free free
42 #ifndef REGNO_MODE_OK_FOR_BASE_P
43 #define REGNO_MODE_OK_FOR_BASE_P(REGNO, MODE) REGNO_OK_FOR_BASE_P (REGNO)
46 #ifndef REG_MODE_OK_FOR_BASE_P
47 #define REG_MODE_OK_FOR_BASE_P(REGNO, MODE) REG_OK_FOR_BASE_P (REGNO)
50 static const char *const reg_class_names
[] = REG_CLASS_NAMES
;
54 struct du_chain
*next_chain
;
55 struct du_chain
*next_use
;
60 unsigned int need_caller_save_reg
:1;
61 unsigned int earlyclobber
:1;
67 terminate_overlapping_read
,
74 static const char * const scan_actions_name
[] =
77 "terminate_overlapping_read",
84 static struct obstack rename_obstack
;
86 static void do_replace
PARAMS ((struct du_chain
*, int));
87 static void scan_rtx_reg
PARAMS ((rtx
, rtx
*, enum reg_class
,
88 enum scan_actions
, enum op_type
, int));
89 static void scan_rtx_address
PARAMS ((rtx
, rtx
*, enum reg_class
,
90 enum scan_actions
, enum machine_mode
));
91 static void scan_rtx
PARAMS ((rtx
, rtx
*, enum reg_class
,
92 enum scan_actions
, enum op_type
, int));
93 static struct du_chain
*build_def_use
PARAMS ((basic_block
));
94 static void dump_def_use_chain
PARAMS ((struct du_chain
*));
95 static void note_sets
PARAMS ((rtx
, rtx
, void *));
96 static void clear_dead_regs
PARAMS ((HARD_REG_SET
*, enum machine_mode
, rtx
));
97 static void merge_overlapping_regs
PARAMS ((basic_block
, HARD_REG_SET
*,
100 /* Called through note_stores from update_life. Find sets of registers, and
101 record them in *DATA (which is actually a HARD_REG_SET *). */
104 note_sets (x
, set
, data
)
106 rtx set ATTRIBUTE_UNUSED
;
109 HARD_REG_SET
*pset
= (HARD_REG_SET
*) data
;
112 if (GET_CODE (x
) != REG
)
115 nregs
= HARD_REGNO_NREGS (regno
, GET_MODE (x
));
117 /* There must not be pseudos at this point. */
118 if (regno
+ nregs
> FIRST_PSEUDO_REGISTER
)
122 SET_HARD_REG_BIT (*pset
, regno
+ nregs
);
125 /* Clear all registers from *PSET for which a note of kind KIND can be found
126 in the list NOTES. */
129 clear_dead_regs (pset
, kind
, notes
)
131 enum machine_mode kind
;
135 for (note
= notes
; note
; note
= XEXP (note
, 1))
136 if (REG_NOTE_KIND (note
) == kind
&& REG_P (XEXP (note
, 0)))
138 rtx reg
= XEXP (note
, 0);
139 unsigned int regno
= REGNO (reg
);
140 int nregs
= HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
142 /* There must not be pseudos at this point. */
143 if (regno
+ nregs
> FIRST_PSEUDO_REGISTER
)
147 CLEAR_HARD_REG_BIT (*pset
, regno
+ nregs
);
151 /* For a def-use chain CHAIN in basic block B, find which registers overlap
152 its lifetime and set the corresponding bits in *PSET. */
155 merge_overlapping_regs (b
, pset
, chain
)
158 struct du_chain
*chain
;
160 struct du_chain
*t
= chain
;
164 REG_SET_TO_HARD_REG_SET (live
, b
->global_live_at_start
);
168 /* Search forward until the next reference to the register to be
170 while (insn
!= t
->insn
)
174 clear_dead_regs (&live
, REG_DEAD
, REG_NOTES (insn
));
175 note_stores (PATTERN (insn
), note_sets
, (void *) &live
);
176 /* Only record currently live regs if we are inside the
179 IOR_HARD_REG_SET (*pset
, live
);
180 clear_dead_regs (&live
, REG_UNUSED
, REG_NOTES (insn
));
182 insn
= NEXT_INSN (insn
);
185 IOR_HARD_REG_SET (*pset
, live
);
187 /* For the last reference, also merge in all registers set in the
189 @@@ We only have take earlyclobbered sets into account. */
191 note_stores (PATTERN (insn
), note_sets
, (void *) pset
);
197 /* Perform register renaming on the current function. */
200 regrename_optimize ()
202 int tick
[FIRST_PSEUDO_REGISTER
];
207 memset (tick
, 0, sizeof tick
);
209 gcc_obstack_init (&rename_obstack
);
210 first_obj
= (char *) obstack_alloc (&rename_obstack
, 0);
214 struct du_chain
*all_chains
= 0;
215 HARD_REG_SET unavailable
;
216 HARD_REG_SET regs_seen
;
218 CLEAR_HARD_REG_SET (unavailable
);
221 fprintf (rtl_dump_file
, "\nBasic block %d:\n", bb
->index
);
223 all_chains
= build_def_use (bb
);
226 dump_def_use_chain (all_chains
);
228 CLEAR_HARD_REG_SET (unavailable
);
229 /* Don't clobber traceback for noreturn functions. */
230 if (frame_pointer_needed
)
234 for (i
= HARD_REGNO_NREGS (FRAME_POINTER_REGNUM
, Pmode
); i
--;)
235 SET_HARD_REG_BIT (unavailable
, FRAME_POINTER_REGNUM
+ i
);
237 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
238 for (i
= HARD_REGNO_NREGS (HARD_FRAME_POINTER_REGNUM
, Pmode
); i
--;)
239 SET_HARD_REG_BIT (unavailable
, HARD_FRAME_POINTER_REGNUM
+ i
);
243 CLEAR_HARD_REG_SET (regs_seen
);
246 int new_reg
, best_new_reg
= -1;
248 struct du_chain
*this = all_chains
;
249 struct du_chain
*tmp
, *last
;
250 HARD_REG_SET this_unavailable
;
251 int reg
= REGNO (*this->loc
);
254 all_chains
= this->next_chain
;
256 #if 0 /* This just disables optimization opportunities. */
257 /* Only rename once we've seen the reg more than once. */
258 if (! TEST_HARD_REG_BIT (regs_seen
, reg
))
260 SET_HARD_REG_BIT (regs_seen
, reg
);
265 if (fixed_regs
[reg
] || global_regs
[reg
]
266 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
267 || (frame_pointer_needed
&& reg
== HARD_FRAME_POINTER_REGNUM
)
269 || (frame_pointer_needed
&& reg
== FRAME_POINTER_REGNUM
)
274 COPY_HARD_REG_SET (this_unavailable
, unavailable
);
276 /* Find last entry on chain (which has the need_caller_save bit),
277 count number of uses, and narrow the set of registers we can
280 for (last
= this; last
->next_use
; last
= last
->next_use
)
283 IOR_COMPL_HARD_REG_SET (this_unavailable
,
284 reg_class_contents
[last
->class]);
289 IOR_COMPL_HARD_REG_SET (this_unavailable
,
290 reg_class_contents
[last
->class]);
292 if (this->need_caller_save_reg
)
293 IOR_HARD_REG_SET (this_unavailable
, call_used_reg_set
);
295 merge_overlapping_regs (bb
, &this_unavailable
, this);
297 /* Now potential_regs is a reasonable approximation, let's
298 have a closer look at each register still in there. */
299 for (new_reg
= 0; new_reg
< FIRST_PSEUDO_REGISTER
; new_reg
++)
301 int nregs
= HARD_REGNO_NREGS (new_reg
, GET_MODE (*this->loc
));
303 for (i
= nregs
- 1; i
>= 0; --i
)
304 if (TEST_HARD_REG_BIT (this_unavailable
, new_reg
+ i
)
305 || fixed_regs
[new_reg
+ i
]
306 || global_regs
[new_reg
+ i
]
307 /* Can't use regs which aren't saved by the prologue. */
308 || (! regs_ever_live
[new_reg
+ i
]
309 && ! call_used_regs
[new_reg
+ i
])
310 #ifdef LEAF_REGISTERS
311 /* We can't use a non-leaf register if we're in a
313 || (current_function_is_leaf
314 && !LEAF_REGISTERS
[new_reg
+ i
])
316 #ifdef HARD_REGNO_RENAME_OK
317 || ! HARD_REGNO_RENAME_OK (reg
+ i
, new_reg
+ i
)
324 /* See whether it accepts all modes that occur in
325 definition and uses. */
326 for (tmp
= this; tmp
; tmp
= tmp
->next_use
)
327 if (! HARD_REGNO_MODE_OK (new_reg
, GET_MODE (*tmp
->loc
))
328 || (tmp
->need_caller_save_reg
329 && ! (HARD_REGNO_CALL_PART_CLOBBERED
330 (reg
, GET_MODE (*tmp
->loc
)))
331 && (HARD_REGNO_CALL_PART_CLOBBERED
332 (new_reg
, GET_MODE (*tmp
->loc
)))))
336 if (best_new_reg
== -1
337 || tick
[best_new_reg
] > tick
[new_reg
])
338 best_new_reg
= new_reg
;
344 fprintf (rtl_dump_file
, "Register %s in insn %d",
345 reg_names
[reg
], INSN_UID (last
->insn
));
346 if (last
->need_caller_save_reg
)
347 fprintf (rtl_dump_file
, " crosses a call");
350 if (best_new_reg
== -1)
353 fprintf (rtl_dump_file
, "; no available registers\n");
357 do_replace (this, best_new_reg
);
358 tick
[best_new_reg
] = this_tick
++;
361 fprintf (rtl_dump_file
, ", renamed as %s\n", reg_names
[best_new_reg
]);
364 obstack_free (&rename_obstack
, first_obj
);
367 obstack_free (&rename_obstack
, NULL
);
370 fputc ('\n', rtl_dump_file
);
372 count_or_remove_death_notes (NULL
, 1);
373 update_life_info (NULL
, UPDATE_LIFE_LOCAL
,
374 PROP_REG_INFO
| PROP_DEATH_NOTES
);
378 do_replace (chain
, reg
)
379 struct du_chain
*chain
;
384 unsigned int regno
= ORIGINAL_REGNO (*chain
->loc
);
385 *chain
->loc
= gen_raw_REG (GET_MODE (*chain
->loc
), reg
);
386 if (regno
>= FIRST_PSEUDO_REGISTER
)
387 ORIGINAL_REGNO (*chain
->loc
) = regno
;
388 chain
= chain
->next_use
;
393 static struct du_chain
*open_chains
;
394 static struct du_chain
*closed_chains
;
397 scan_rtx_reg (insn
, loc
, class, action
, type
, earlyclobber
)
400 enum reg_class
class;
401 enum scan_actions action
;
407 enum machine_mode mode
= GET_MODE (x
);
408 int this_regno
= REGNO (x
);
409 int this_nregs
= HARD_REGNO_NREGS (this_regno
, mode
);
411 if (action
== mark_write
)
415 struct du_chain
*this = (struct du_chain
*)
416 obstack_alloc (&rename_obstack
, sizeof (struct du_chain
));
418 this->next_chain
= open_chains
;
422 this->need_caller_save_reg
= 0;
423 this->earlyclobber
= earlyclobber
;
429 if ((type
== OP_OUT
&& action
!= terminate_write
)
430 || (type
!= OP_OUT
&& action
== terminate_write
))
433 for (p
= &open_chains
; *p
;)
435 struct du_chain
*this = *p
;
437 /* Check if the chain has been terminated if it has then skip to
440 This can happen when we've already appended the location to
441 the chain in Step 3, but are trying to hide in-out operands
442 from terminate_write in Step 5. */
444 if (*this->loc
== cc0_rtx
)
445 p
= &this->next_chain
;
448 int regno
= REGNO (*this->loc
);
449 int nregs
= HARD_REGNO_NREGS (regno
, GET_MODE (*this->loc
));
450 int exact_match
= (regno
== this_regno
&& nregs
== this_nregs
);
452 if (regno
+ nregs
<= this_regno
453 || this_regno
+ this_nregs
<= regno
)
455 p
= &this->next_chain
;
459 if (action
== mark_read
)
464 /* ??? Class NO_REGS can happen if the md file makes use of
465 EXTRA_CONSTRAINTS to match registers. Which is arguably
466 wrong, but there we are. Since we know not what this may
467 be replaced with, terminate the chain. */
468 if (class != NO_REGS
)
470 this = (struct du_chain
*)
471 obstack_alloc (&rename_obstack
, sizeof (struct du_chain
));
473 this->next_chain
= (*p
)->next_chain
;
477 this->need_caller_save_reg
= 0;
485 if (action
!= terminate_overlapping_read
|| ! exact_match
)
487 struct du_chain
*next
= this->next_chain
;
489 /* Whether the terminated chain can be used for renaming
490 depends on the action and this being an exact match.
491 In either case, we remove this element from open_chains. */
493 if ((action
== terminate_dead
|| action
== terminate_write
)
496 this->next_chain
= closed_chains
;
497 closed_chains
= this;
499 fprintf (rtl_dump_file
,
500 "Closing chain %s at insn %d (%s)\n",
501 reg_names
[REGNO (*this->loc
)], INSN_UID (insn
),
502 scan_actions_name
[(int) action
]);
507 fprintf (rtl_dump_file
,
508 "Discarding chain %s at insn %d (%s)\n",
509 reg_names
[REGNO (*this->loc
)], INSN_UID (insn
),
510 scan_actions_name
[(int) action
]);
515 p
= &this->next_chain
;
520 /* Adapted from find_reloads_address_1. CLASS is INDEX_REG_CLASS or
521 BASE_REG_CLASS depending on how the register is being considered. */
524 scan_rtx_address (insn
, loc
, class, action
, mode
)
527 enum reg_class
class;
528 enum scan_actions action
;
529 enum machine_mode mode
;
532 RTX_CODE code
= GET_CODE (x
);
536 if (action
== mark_write
)
543 rtx orig_op0
= XEXP (x
, 0);
544 rtx orig_op1
= XEXP (x
, 1);
545 RTX_CODE code0
= GET_CODE (orig_op0
);
546 RTX_CODE code1
= GET_CODE (orig_op1
);
552 if (GET_CODE (op0
) == SUBREG
)
554 op0
= SUBREG_REG (op0
);
555 code0
= GET_CODE (op0
);
558 if (GET_CODE (op1
) == SUBREG
)
560 op1
= SUBREG_REG (op1
);
561 code1
= GET_CODE (op1
);
564 if (code0
== MULT
|| code0
== SIGN_EXTEND
|| code0
== TRUNCATE
565 || code0
== ZERO_EXTEND
|| code1
== MEM
)
570 else if (code1
== MULT
|| code1
== SIGN_EXTEND
|| code1
== TRUNCATE
571 || code1
== ZERO_EXTEND
|| code0
== MEM
)
576 else if (code0
== CONST_INT
|| code0
== CONST
577 || code0
== SYMBOL_REF
|| code0
== LABEL_REF
)
579 else if (code1
== CONST_INT
|| code1
== CONST
580 || code1
== SYMBOL_REF
|| code1
== LABEL_REF
)
582 else if (code0
== REG
&& code1
== REG
)
586 if (REG_OK_FOR_INDEX_P (op0
)
587 && REG_MODE_OK_FOR_BASE_P (op1
, mode
))
589 else if (REG_OK_FOR_INDEX_P (op1
)
590 && REG_MODE_OK_FOR_BASE_P (op0
, mode
))
592 else if (REG_MODE_OK_FOR_BASE_P (op1
, mode
))
594 else if (REG_MODE_OK_FOR_BASE_P (op0
, mode
))
596 else if (REG_OK_FOR_INDEX_P (op1
))
601 locI
= &XEXP (x
, index_op
);
602 locB
= &XEXP (x
, !index_op
);
604 else if (code0
== REG
)
609 else if (code1
== REG
)
616 scan_rtx_address (insn
, locI
, INDEX_REG_CLASS
, action
, mode
);
618 scan_rtx_address (insn
, locB
, MODE_BASE_REG_CLASS (mode
), action
, mode
);
629 /* If the target doesn't claim to handle autoinc, this must be
630 something special, like a stack push. Kill this chain. */
631 action
= terminate_all_read
;
636 scan_rtx_address (insn
, &XEXP (x
, 0),
637 MODE_BASE_REG_CLASS (GET_MODE (x
)), action
,
642 scan_rtx_reg (insn
, loc
, class, action
, OP_IN
, 0);
649 fmt
= GET_RTX_FORMAT (code
);
650 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
653 scan_rtx_address (insn
, &XEXP (x
, i
), class, action
, mode
);
654 else if (fmt
[i
] == 'E')
655 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
656 scan_rtx_address (insn
, &XVECEXP (x
, i
, j
), class, action
, mode
);
661 scan_rtx (insn
, loc
, class, action
, type
, earlyclobber
)
664 enum reg_class
class;
665 enum scan_actions action
;
671 enum rtx_code code
= GET_CODE (x
);
688 scan_rtx_reg (insn
, loc
, class, action
, type
, earlyclobber
);
692 scan_rtx_address (insn
, &XEXP (x
, 0),
693 MODE_BASE_REG_CLASS (GET_MODE (x
)), action
,
698 scan_rtx (insn
, &SET_SRC (x
), class, action
, OP_IN
, 0);
699 scan_rtx (insn
, &SET_DEST (x
), class, action
, OP_OUT
, 0);
702 case STRICT_LOW_PART
:
703 scan_rtx (insn
, &XEXP (x
, 0), class, action
, OP_INOUT
, earlyclobber
);
708 scan_rtx (insn
, &XEXP (x
, 0), class, action
,
709 type
== OP_IN
? OP_IN
: OP_INOUT
, earlyclobber
);
710 scan_rtx (insn
, &XEXP (x
, 1), class, action
, OP_IN
, 0);
711 scan_rtx (insn
, &XEXP (x
, 2), class, action
, OP_IN
, 0);
720 /* Should only happen inside MEM. */
724 scan_rtx (insn
, &SET_DEST (x
), class, action
, OP_OUT
, 1);
728 scan_rtx (insn
, &XEXP (x
, 0), class, action
, type
, 0);
730 scan_rtx (insn
, &XEXP (x
, 1), class, action
, type
, 0);
737 fmt
= GET_RTX_FORMAT (code
);
738 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
741 scan_rtx (insn
, &XEXP (x
, i
), class, action
, type
, 0);
742 else if (fmt
[i
] == 'E')
743 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
744 scan_rtx (insn
, &XVECEXP (x
, i
, j
), class, action
, type
, 0);
748 /* Build def/use chain */
750 static struct du_chain
*
756 open_chains
= closed_chains
= NULL
;
758 for (insn
= bb
->head
; ; insn
= NEXT_INSN (insn
))
764 rtx old_operands
[MAX_RECOG_OPERANDS
];
765 rtx old_dups
[MAX_DUP_OPERANDS
];
770 /* Process the insn, determining its effect on the def-use
771 chains. We perform the following steps with the register
772 references in the insn:
773 (1) Any read that overlaps an open chain, but doesn't exactly
774 match, causes that chain to be closed. We can't deal
776 (2) Any read outside an operand causes any chain it overlaps
777 with to be closed, since we can't replace it.
778 (3) Any read inside an operand is added if there's already
779 an open chain for it.
780 (4) For any REG_DEAD note we find, close open chains that
782 (5) For any write we find, close open chains that overlap it.
783 (6) For any write we find in an operand, make a new chain.
784 (7) For any REG_UNUSED, close any chains we just opened. */
786 icode
= recog_memoized (insn
);
788 if (! constrain_operands (1))
789 fatal_insn_not_found (insn
);
790 preprocess_constraints ();
791 alt
= which_alternative
;
792 n_ops
= recog_data
.n_operands
;
794 /* Simplify the code below by rewriting things to reflect
795 matching constraints. Also promote OP_OUT to OP_INOUT
796 in predicated instructions. */
798 predicated
= GET_CODE (PATTERN (insn
)) == COND_EXEC
;
799 for (i
= 0; i
< n_ops
; ++i
)
801 int matches
= recog_op_alt
[i
][alt
].matches
;
803 recog_op_alt
[i
][alt
].class = recog_op_alt
[matches
][alt
].class;
804 if (matches
>= 0 || recog_op_alt
[i
][alt
].matched
>= 0
805 || (predicated
&& recog_data
.operand_type
[i
] == OP_OUT
))
806 recog_data
.operand_type
[i
] = OP_INOUT
;
809 /* Step 1: Close chains for which we have overlapping reads. */
810 for (i
= 0; i
< n_ops
; i
++)
811 scan_rtx (insn
, recog_data
.operand_loc
[i
],
812 NO_REGS
, terminate_overlapping_read
,
813 recog_data
.operand_type
[i
], 0);
815 /* Step 2: Close chains for which we have reads outside operands.
816 We do this by munging all operands into CC0, and closing
817 everything remaining. */
819 for (i
= 0; i
< n_ops
; i
++)
821 old_operands
[i
] = recog_data
.operand
[i
];
822 /* Don't squash match_operator or match_parallel here, since
823 we don't know that all of the contained registers are
824 reachable by proper operands. */
825 if (recog_data
.constraints
[i
][0] == '\0')
827 *recog_data
.operand_loc
[i
] = cc0_rtx
;
829 for (i
= 0; i
< recog_data
.n_dups
; i
++)
831 int dup_num
= recog_data
.dup_num
[i
];
833 old_dups
[i
] = *recog_data
.dup_loc
[i
];
834 *recog_data
.dup_loc
[i
] = cc0_rtx
;
836 /* For match_dup of match_operator or match_parallel, share
837 them, so that we don't miss changes in the dup. */
839 && insn_data
[icode
].operand
[dup_num
].eliminable
== 0)
840 old_dups
[i
] = recog_data
.operand
[dup_num
];
843 scan_rtx (insn
, &PATTERN (insn
), NO_REGS
, terminate_all_read
,
846 for (i
= 0; i
< recog_data
.n_dups
; i
++)
847 *recog_data
.dup_loc
[i
] = old_dups
[i
];
848 for (i
= 0; i
< n_ops
; i
++)
849 *recog_data
.operand_loc
[i
] = old_operands
[i
];
851 /* Step 2B: Can't rename function call argument registers. */
852 if (GET_CODE (insn
) == CALL_INSN
&& CALL_INSN_FUNCTION_USAGE (insn
))
853 scan_rtx (insn
, &CALL_INSN_FUNCTION_USAGE (insn
),
854 NO_REGS
, terminate_all_read
, OP_IN
, 0);
856 /* Step 2C: Can't rename asm operands that were originally
858 if (asm_noperands (PATTERN (insn
)) > 0)
859 for (i
= 0; i
< n_ops
; i
++)
861 rtx
*loc
= recog_data
.operand_loc
[i
];
864 if (GET_CODE (op
) == REG
865 && REGNO (op
) == ORIGINAL_REGNO (op
)
866 && (recog_data
.operand_type
[i
] == OP_IN
867 || recog_data
.operand_type
[i
] == OP_INOUT
))
868 scan_rtx (insn
, loc
, NO_REGS
, terminate_all_read
, OP_IN
, 0);
871 /* Step 3: Append to chains for reads inside operands. */
872 for (i
= 0; i
< n_ops
+ recog_data
.n_dups
; i
++)
874 int opn
= i
< n_ops
? i
: recog_data
.dup_num
[i
- n_ops
];
875 rtx
*loc
= (i
< n_ops
876 ? recog_data
.operand_loc
[opn
]
877 : recog_data
.dup_loc
[i
- n_ops
]);
878 enum reg_class
class = recog_op_alt
[opn
][alt
].class;
879 enum op_type type
= recog_data
.operand_type
[opn
];
881 /* Don't scan match_operand here, since we've no reg class
882 information to pass down. Any operands that we could
883 substitute in will be represented elsewhere. */
884 if (recog_data
.constraints
[opn
][0] == '\0')
887 if (recog_op_alt
[opn
][alt
].is_address
)
888 scan_rtx_address (insn
, loc
, class, mark_read
, VOIDmode
);
890 scan_rtx (insn
, loc
, class, mark_read
, type
, 0);
893 /* Step 4: Close chains for registers that die here.
894 Also record updates for REG_INC notes. */
895 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
897 if (REG_NOTE_KIND (note
) == REG_DEAD
)
898 scan_rtx (insn
, &XEXP (note
, 0), NO_REGS
, terminate_dead
,
900 else if (REG_NOTE_KIND (note
) == REG_INC
)
901 scan_rtx (insn
, &XEXP (note
, 0), ALL_REGS
, mark_read
,
905 /* Step 4B: If this is a call, any chain live at this point
906 requires a caller-saved reg. */
907 if (GET_CODE (insn
) == CALL_INSN
)
910 for (p
= open_chains
; p
; p
= p
->next_chain
)
911 p
->need_caller_save_reg
= 1;
914 /* Step 5: Close open chains that overlap writes. Similar to
915 step 2, we hide in-out operands, since we do not want to
916 close these chains. */
918 for (i
= 0; i
< n_ops
; i
++)
920 old_operands
[i
] = recog_data
.operand
[i
];
921 if (recog_data
.operand_type
[i
] == OP_INOUT
)
922 *recog_data
.operand_loc
[i
] = cc0_rtx
;
924 for (i
= 0; i
< recog_data
.n_dups
; i
++)
926 int opn
= recog_data
.dup_num
[i
];
927 old_dups
[i
] = *recog_data
.dup_loc
[i
];
928 if (recog_data
.operand_type
[opn
] == OP_INOUT
)
929 *recog_data
.dup_loc
[i
] = cc0_rtx
;
932 scan_rtx (insn
, &PATTERN (insn
), NO_REGS
, terminate_write
, OP_IN
, 0);
934 for (i
= 0; i
< recog_data
.n_dups
; i
++)
935 *recog_data
.dup_loc
[i
] = old_dups
[i
];
936 for (i
= 0; i
< n_ops
; i
++)
937 *recog_data
.operand_loc
[i
] = old_operands
[i
];
939 /* Step 6: Begin new chains for writes inside operands. */
940 /* ??? Many targets have output constraints on the SET_DEST
941 of a call insn, which is stupid, since these are certainly
942 ABI defined hard registers. Don't change calls at all.
943 Similarly take special care for asm statement that originally
944 referenced hard registers. */
945 if (asm_noperands (PATTERN (insn
)) > 0)
947 for (i
= 0; i
< n_ops
; i
++)
948 if (recog_data
.operand_type
[i
] == OP_OUT
)
950 rtx
*loc
= recog_data
.operand_loc
[i
];
952 enum reg_class
class = recog_op_alt
[i
][alt
].class;
954 if (GET_CODE (op
) == REG
955 && REGNO (op
) == ORIGINAL_REGNO (op
))
958 scan_rtx (insn
, loc
, class, mark_write
, OP_OUT
,
959 recog_op_alt
[i
][alt
].earlyclobber
);
962 else if (GET_CODE (insn
) != CALL_INSN
)
963 for (i
= 0; i
< n_ops
+ recog_data
.n_dups
; i
++)
965 int opn
= i
< n_ops
? i
: recog_data
.dup_num
[i
- n_ops
];
966 rtx
*loc
= (i
< n_ops
967 ? recog_data
.operand_loc
[opn
]
968 : recog_data
.dup_loc
[i
- n_ops
]);
969 enum reg_class
class = recog_op_alt
[opn
][alt
].class;
971 if (recog_data
.operand_type
[opn
] == OP_OUT
)
972 scan_rtx (insn
, loc
, class, mark_write
, OP_OUT
,
973 recog_op_alt
[opn
][alt
].earlyclobber
);
976 /* Step 7: Close chains for registers that were never
978 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
979 if (REG_NOTE_KIND (note
) == REG_UNUSED
)
980 scan_rtx (insn
, &XEXP (note
, 0), NO_REGS
, terminate_dead
,
987 /* Since we close every chain when we find a REG_DEAD note, anything that
988 is still open lives past the basic block, so it can't be renamed. */
989 return closed_chains
;
992 /* Dump all def/use chains in CHAINS to RTL_DUMP_FILE. They are
993 printed in reverse order as that's how we build them. */
996 dump_def_use_chain (chains
)
997 struct du_chain
*chains
;
1001 struct du_chain
*this = chains
;
1002 int r
= REGNO (*this->loc
);
1003 int nregs
= HARD_REGNO_NREGS (r
, GET_MODE (*this->loc
));
1004 fprintf (rtl_dump_file
, "Register %s (%d):", reg_names
[r
], nregs
);
1007 fprintf (rtl_dump_file
, " %d [%s]", INSN_UID (this->insn
),
1008 reg_class_names
[this->class]);
1009 this = this->next_use
;
1011 fprintf (rtl_dump_file
, "\n");
1012 chains
= chains
->next_chain
;
1016 /* The following code does forward propagation of hard register copies.
1017 The object is to eliminate as many dependencies as possible, so that
1018 we have the most scheduling freedom. As a side effect, we also clean
1019 up some silly register allocation decisions made by reload. This
1020 code may be obsoleted by a new register allocator. */
1022 /* For each register, we have a list of registers that contain the same
1023 value. The OLDEST_REGNO field points to the head of the list, and
1024 the NEXT_REGNO field runs through the list. The MODE field indicates
1025 what mode the data is known to be in; this field is VOIDmode when the
1026 register is not known to contain valid data. */
1028 struct value_data_entry
1030 enum machine_mode mode
;
1031 unsigned int oldest_regno
;
1032 unsigned int next_regno
;
1037 struct value_data_entry e
[FIRST_PSEUDO_REGISTER
];
1038 unsigned int max_value_regs
;
1041 static void kill_value_regno
PARAMS ((unsigned, struct value_data
*));
1042 static void kill_value
PARAMS ((rtx
, struct value_data
*));
1043 static void set_value_regno
PARAMS ((unsigned, enum machine_mode
,
1044 struct value_data
*));
1045 static void init_value_data
PARAMS ((struct value_data
*));
1046 static void kill_clobbered_value
PARAMS ((rtx
, rtx
, void *));
1047 static void kill_set_value
PARAMS ((rtx
, rtx
, void *));
1048 static int kill_autoinc_value
PARAMS ((rtx
*, void *));
1049 static void copy_value
PARAMS ((rtx
, rtx
, struct value_data
*));
1050 static bool mode_change_ok
PARAMS ((enum machine_mode
, enum machine_mode
,
1052 static rtx maybe_mode_change
PARAMS ((enum machine_mode
, enum machine_mode
,
1053 enum machine_mode
, unsigned int,
1055 static rtx find_oldest_value_reg
PARAMS ((enum reg_class
, rtx
,
1056 struct value_data
*));
1057 static bool replace_oldest_value_reg
PARAMS ((rtx
*, enum reg_class
, rtx
,
1058 struct value_data
*));
1059 static bool replace_oldest_value_addr
PARAMS ((rtx
*, enum reg_class
,
1060 enum machine_mode
, rtx
,
1061 struct value_data
*));
1062 static bool replace_oldest_value_mem
PARAMS ((rtx
, rtx
, struct value_data
*));
1063 static bool copyprop_hardreg_forward_1
PARAMS ((basic_block
,
1064 struct value_data
*));
1065 extern void debug_value_data
PARAMS ((struct value_data
*));
1066 #ifdef ENABLE_CHECKING
1067 static void validate_value_data
PARAMS ((struct value_data
*));
1070 /* Kill register REGNO. This involves removing it from any value lists,
1071 and resetting the value mode to VOIDmode. */
1074 kill_value_regno (regno
, vd
)
1076 struct value_data
*vd
;
1078 unsigned int i
, next
;
1080 if (vd
->e
[regno
].oldest_regno
!= regno
)
1082 for (i
= vd
->e
[regno
].oldest_regno
;
1083 vd
->e
[i
].next_regno
!= regno
;
1084 i
= vd
->e
[i
].next_regno
)
1086 vd
->e
[i
].next_regno
= vd
->e
[regno
].next_regno
;
1088 else if ((next
= vd
->e
[regno
].next_regno
) != INVALID_REGNUM
)
1090 for (i
= next
; i
!= INVALID_REGNUM
; i
= vd
->e
[i
].next_regno
)
1091 vd
->e
[i
].oldest_regno
= next
;
1094 vd
->e
[regno
].mode
= VOIDmode
;
1095 vd
->e
[regno
].oldest_regno
= regno
;
1096 vd
->e
[regno
].next_regno
= INVALID_REGNUM
;
1098 #ifdef ENABLE_CHECKING
1099 validate_value_data (vd
);
1103 /* Kill X. This is a convenience function for kill_value_regno
1104 so that we mind the mode the register is in. */
1109 struct value_data
*vd
;
1111 /* SUBREGS are supposed to have been eliminated by now. But some
1112 ports, e.g. i386 sse, use them to smuggle vector type information
1113 through to instruction selection. Each such SUBREG should simplify,
1114 so if we get a NULL we've done something wrong elsewhere. */
1116 if (GET_CODE (x
) == SUBREG
)
1117 x
= simplify_subreg (GET_MODE (x
), SUBREG_REG (x
),
1118 GET_MODE (SUBREG_REG (x
)), SUBREG_BYTE (x
));
1121 unsigned int regno
= REGNO (x
);
1122 unsigned int n
= HARD_REGNO_NREGS (regno
, GET_MODE (x
));
1125 /* Kill the value we're told to kill. */
1126 for (i
= 0; i
< n
; ++i
)
1127 kill_value_regno (regno
+ i
, vd
);
1129 /* Kill everything that overlapped what we're told to kill. */
1130 if (regno
< vd
->max_value_regs
)
1133 j
= regno
- vd
->max_value_regs
;
1134 for (; j
< regno
; ++j
)
1136 if (vd
->e
[j
].mode
== VOIDmode
)
1138 n
= HARD_REGNO_NREGS (j
, vd
->e
[j
].mode
);
1140 for (i
= 0; i
< n
; ++i
)
1141 kill_value_regno (j
+ i
, vd
);
1146 /* Remember that REGNO is valid in MODE. */
1149 set_value_regno (regno
, mode
, vd
)
1151 enum machine_mode mode
;
1152 struct value_data
*vd
;
1156 vd
->e
[regno
].mode
= mode
;
1158 nregs
= HARD_REGNO_NREGS (regno
, mode
);
1159 if (nregs
> vd
->max_value_regs
)
1160 vd
->max_value_regs
= nregs
;
1163 /* Initialize VD such that there are no known relationships between regs. */
1166 init_value_data (vd
)
1167 struct value_data
*vd
;
1170 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1172 vd
->e
[i
].mode
= VOIDmode
;
1173 vd
->e
[i
].oldest_regno
= i
;
1174 vd
->e
[i
].next_regno
= INVALID_REGNUM
;
1176 vd
->max_value_regs
= 0;
1179 /* Called through note_stores. If X is clobbered, kill its value. */
1182 kill_clobbered_value (x
, set
, data
)
1187 struct value_data
*vd
= data
;
1188 if (GET_CODE (set
) == CLOBBER
)
1192 /* Called through note_stores. If X is set, not clobbered, kill its
1193 current value and install it as the root of its own value list. */
1196 kill_set_value (x
, set
, data
)
1201 struct value_data
*vd
= data
;
1202 if (GET_CODE (set
) != CLOBBER
)
1206 set_value_regno (REGNO (x
), GET_MODE (x
), vd
);
1210 /* Called through for_each_rtx. Kill any register used as the base of an
1211 auto-increment expression, and install that register as the root of its
1215 kill_autoinc_value (px
, data
)
1220 struct value_data
*vd
= data
;
1222 if (GET_RTX_CLASS (GET_CODE (x
)) == 'a')
1226 set_value_regno (REGNO (x
), Pmode
, vd
);
1233 /* Assert that SRC has been copied to DEST. Adjust the data structures
1234 to reflect that SRC contains an older copy of the shared value. */
1237 copy_value (dest
, src
, vd
)
1240 struct value_data
*vd
;
1242 unsigned int dr
= REGNO (dest
);
1243 unsigned int sr
= REGNO (src
);
1244 unsigned int dn
, sn
;
1247 /* ??? At present, it's possible to see noop sets. It'd be nice if
1248 this were cleaned up beforehand... */
1252 /* Do not propagate copies to the stack pointer, as that can leave
1253 memory accesses with no scheduling dependancy on the stack update. */
1254 if (dr
== STACK_POINTER_REGNUM
)
1257 /* Likewise with the frame pointer, if we're using one. */
1258 if (frame_pointer_needed
&& dr
== HARD_FRAME_POINTER_REGNUM
)
1261 /* If SRC and DEST overlap, don't record anything. */
1262 dn
= HARD_REGNO_NREGS (dr
, GET_MODE (dest
));
1263 sn
= HARD_REGNO_NREGS (sr
, GET_MODE (dest
));
1264 if ((dr
> sr
&& dr
< sr
+ sn
)
1265 || (sr
> dr
&& sr
< dr
+ dn
))
1268 /* If SRC had no assigned mode (i.e. we didn't know it was live)
1269 assign it now and assume the value came from an input argument
1271 if (vd
->e
[sr
].mode
== VOIDmode
)
1272 set_value_regno (sr
, vd
->e
[dr
].mode
, vd
);
1274 /* If we are narrowing the the input to a smaller number of hard regs,
1275 and it is in big endian, we are really extracting a high part.
1276 Since we generally associate a low part of a value with the value itself,
1277 we must not do the same for the high part.
1278 Note we can still get low parts for the same mode combination through
1279 a two-step copy involving differently sized hard regs.
1280 Assume hard regs fr* are 32 bits bits each, while r* are 64 bits each:
1281 (set (reg:DI r0) (reg:DI fr0))
1282 (set (reg:SI fr2) (reg:SI r0))
1283 loads the low part of (reg:DI fr0) - i.e. fr1 - into fr2, while:
1284 (set (reg:SI fr2) (reg:SI fr0))
1285 loads the high part of (reg:DI fr0) into fr2.
1287 We can't properly represent the latter case in our tables, so don't
1288 record anything then. */
1289 else if (sn
< (unsigned int) HARD_REGNO_NREGS (sr
, vd
->e
[sr
].mode
)
1290 && (GET_MODE_SIZE (vd
->e
[sr
].mode
) > UNITS_PER_WORD
1291 ? WORDS_BIG_ENDIAN
: BYTES_BIG_ENDIAN
))
1294 /* If SRC had been assigned a mode narrower than the copy, we can't
1295 link DEST into the chain, because not all of the pieces of the
1296 copy came from oldest_regno. */
1297 else if (sn
> (unsigned int) HARD_REGNO_NREGS (sr
, vd
->e
[sr
].mode
))
1300 /* Link DR at the end of the value chain used by SR. */
1302 vd
->e
[dr
].oldest_regno
= vd
->e
[sr
].oldest_regno
;
1304 for (i
= sr
; vd
->e
[i
].next_regno
!= INVALID_REGNUM
; i
= vd
->e
[i
].next_regno
)
1306 vd
->e
[i
].next_regno
= dr
;
1308 #ifdef ENABLE_CHECKING
1309 validate_value_data (vd
);
1313 /* Return true if a mode change from ORIG to NEW is allowed for REGNO. */
1316 mode_change_ok (orig_mode
, new_mode
, regno
)
1317 enum machine_mode orig_mode
, new_mode
;
1318 unsigned int regno ATTRIBUTE_UNUSED
;
1320 if (GET_MODE_SIZE (orig_mode
) < GET_MODE_SIZE (new_mode
))
1323 #ifdef CLASS_CANNOT_CHANGE_MODE
1324 if (TEST_HARD_REG_BIT (reg_class_contents
[CLASS_CANNOT_CHANGE_MODE
], regno
)
1325 && CLASS_CANNOT_CHANGE_MODE_P (orig_mode
, new_mode
))
1332 /* Register REGNO was originally set in ORIG_MODE. It - or a copy of it -
1333 was copied in COPY_MODE to COPY_REGNO, and then COPY_REGNO was accessed
1335 Return a NEW_MODE rtx for REGNO if that's OK, otherwise return NULL_RTX. */
1338 maybe_mode_change (orig_mode
, copy_mode
, new_mode
, regno
, copy_regno
)
1339 enum machine_mode orig_mode
, copy_mode
, new_mode
;
1340 unsigned int regno
, copy_regno
;
1342 if (orig_mode
== new_mode
)
1343 return gen_rtx_raw_REG (new_mode
, regno
);
1344 else if (mode_change_ok (orig_mode
, new_mode
, regno
))
1346 int copy_nregs
= HARD_REGNO_NREGS (copy_regno
, copy_mode
);
1347 int use_nregs
= HARD_REGNO_NREGS (copy_regno
, new_mode
);
1349 = GET_MODE_SIZE (copy_mode
) / copy_nregs
* (copy_nregs
- use_nregs
);
1351 = GET_MODE_SIZE (orig_mode
) - GET_MODE_SIZE (new_mode
) - copy_offset
;
1352 int byteoffset
= offset
% UNITS_PER_WORD
;
1353 int wordoffset
= offset
- byteoffset
;
1355 offset
= ((WORDS_BIG_ENDIAN
? wordoffset
: 0)
1356 + (BYTES_BIG_ENDIAN
? byteoffset
: 0));
1357 return gen_rtx_raw_REG (new_mode
,
1358 regno
+ subreg_regno_offset (regno
, orig_mode
,
1365 /* Find the oldest copy of the value contained in REGNO that is in
1366 register class CLASS and has mode MODE. If found, return an rtx
1367 of that oldest register, otherwise return NULL. */
1370 find_oldest_value_reg (class, reg
, vd
)
1371 enum reg_class
class;
1373 struct value_data
*vd
;
1375 unsigned int regno
= REGNO (reg
);
1376 enum machine_mode mode
= GET_MODE (reg
);
1379 /* If we are accessing REG in some mode other that what we set it in,
1380 make sure that the replacement is valid. In particular, consider
1381 (set (reg:DI r11) (...))
1382 (set (reg:SI r9) (reg:SI r11))
1383 (set (reg:SI r10) (...))
1384 (set (...) (reg:DI r9))
1385 Replacing r9 with r11 is invalid. */
1386 if (mode
!= vd
->e
[regno
].mode
)
1388 if (HARD_REGNO_NREGS (regno
, mode
)
1389 > HARD_REGNO_NREGS (regno
, vd
->e
[regno
].mode
))
1393 for (i
= vd
->e
[regno
].oldest_regno
; i
!= regno
; i
= vd
->e
[i
].next_regno
)
1395 enum machine_mode oldmode
= vd
->e
[i
].mode
;
1398 if (TEST_HARD_REG_BIT (reg_class_contents
[class], i
)
1399 && (new = maybe_mode_change (oldmode
, vd
->e
[regno
].mode
, mode
, i
,
1402 ORIGINAL_REGNO (new) = ORIGINAL_REGNO (reg
);
1410 /* If possible, replace the register at *LOC with the oldest register
1411 in register class CLASS. Return true if successfully replaced. */
1414 replace_oldest_value_reg (loc
, class, insn
, vd
)
1416 enum reg_class
class;
1418 struct value_data
*vd
;
1420 rtx
new = find_oldest_value_reg (class, *loc
, vd
);
1424 fprintf (rtl_dump_file
, "insn %u: replaced reg %u with %u\n",
1425 INSN_UID (insn
), REGNO (*loc
), REGNO (new));
1433 /* Similar to replace_oldest_value_reg, but *LOC contains an address.
1434 Adapted from find_reloads_address_1. CLASS is INDEX_REG_CLASS or
1435 BASE_REG_CLASS depending on how the register is being considered. */
1438 replace_oldest_value_addr (loc
, class, mode
, insn
, vd
)
1440 enum reg_class
class;
1441 enum machine_mode mode
;
1443 struct value_data
*vd
;
1446 RTX_CODE code
= GET_CODE (x
);
1449 bool changed
= false;
1455 rtx orig_op0
= XEXP (x
, 0);
1456 rtx orig_op1
= XEXP (x
, 1);
1457 RTX_CODE code0
= GET_CODE (orig_op0
);
1458 RTX_CODE code1
= GET_CODE (orig_op1
);
1464 if (GET_CODE (op0
) == SUBREG
)
1466 op0
= SUBREG_REG (op0
);
1467 code0
= GET_CODE (op0
);
1470 if (GET_CODE (op1
) == SUBREG
)
1472 op1
= SUBREG_REG (op1
);
1473 code1
= GET_CODE (op1
);
1476 if (code0
== MULT
|| code0
== SIGN_EXTEND
|| code0
== TRUNCATE
1477 || code0
== ZERO_EXTEND
|| code1
== MEM
)
1479 locI
= &XEXP (x
, 0);
1480 locB
= &XEXP (x
, 1);
1482 else if (code1
== MULT
|| code1
== SIGN_EXTEND
|| code1
== TRUNCATE
1483 || code1
== ZERO_EXTEND
|| code0
== MEM
)
1485 locI
= &XEXP (x
, 1);
1486 locB
= &XEXP (x
, 0);
1488 else if (code0
== CONST_INT
|| code0
== CONST
1489 || code0
== SYMBOL_REF
|| code0
== LABEL_REF
)
1490 locB
= &XEXP (x
, 1);
1491 else if (code1
== CONST_INT
|| code1
== CONST
1492 || code1
== SYMBOL_REF
|| code1
== LABEL_REF
)
1493 locB
= &XEXP (x
, 0);
1494 else if (code0
== REG
&& code1
== REG
)
1498 if (REG_OK_FOR_INDEX_P (op0
)
1499 && REG_MODE_OK_FOR_BASE_P (op1
, mode
))
1501 else if (REG_OK_FOR_INDEX_P (op1
)
1502 && REG_MODE_OK_FOR_BASE_P (op0
, mode
))
1504 else if (REG_MODE_OK_FOR_BASE_P (op1
, mode
))
1506 else if (REG_MODE_OK_FOR_BASE_P (op0
, mode
))
1508 else if (REG_OK_FOR_INDEX_P (op1
))
1513 locI
= &XEXP (x
, index_op
);
1514 locB
= &XEXP (x
, !index_op
);
1516 else if (code0
== REG
)
1518 locI
= &XEXP (x
, 0);
1519 locB
= &XEXP (x
, 1);
1521 else if (code1
== REG
)
1523 locI
= &XEXP (x
, 1);
1524 locB
= &XEXP (x
, 0);
1528 changed
|= replace_oldest_value_addr (locI
, INDEX_REG_CLASS
, mode
,
1531 changed
|= replace_oldest_value_addr (locB
,
1532 MODE_BASE_REG_CLASS (mode
),
1546 return replace_oldest_value_mem (x
, insn
, vd
);
1549 return replace_oldest_value_reg (loc
, class, insn
, vd
);
1555 fmt
= GET_RTX_FORMAT (code
);
1556 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1559 changed
|= replace_oldest_value_addr (&XEXP (x
, i
), class, mode
,
1561 else if (fmt
[i
] == 'E')
1562 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
1563 changed
|= replace_oldest_value_addr (&XVECEXP (x
, i
, j
), class,
1570 /* Similar to replace_oldest_value_reg, but X contains a memory. */
1573 replace_oldest_value_mem (x
, insn
, vd
)
1576 struct value_data
*vd
;
1578 return replace_oldest_value_addr (&XEXP (x
, 0),
1579 MODE_BASE_REG_CLASS (GET_MODE (x
)),
1580 GET_MODE (x
), insn
, vd
);
1583 /* Perform the forward copy propagation on basic block BB. */
1586 copyprop_hardreg_forward_1 (bb
, vd
)
1588 struct value_data
*vd
;
1590 bool changed
= false;
1593 for (insn
= bb
->head
; ; insn
= NEXT_INSN (insn
))
1595 int n_ops
, i
, alt
, predicated
;
1599 if (! INSN_P (insn
))
1601 if (insn
== bb
->end
)
1607 set
= single_set (insn
);
1608 extract_insn (insn
);
1609 if (! constrain_operands (1))
1610 fatal_insn_not_found (insn
);
1611 preprocess_constraints ();
1612 alt
= which_alternative
;
1613 n_ops
= recog_data
.n_operands
;
1614 is_asm
= asm_noperands (PATTERN (insn
)) >= 0;
1616 /* Simplify the code below by rewriting things to reflect
1617 matching constraints. Also promote OP_OUT to OP_INOUT
1618 in predicated instructions. */
1620 predicated
= GET_CODE (PATTERN (insn
)) == COND_EXEC
;
1621 for (i
= 0; i
< n_ops
; ++i
)
1623 int matches
= recog_op_alt
[i
][alt
].matches
;
1625 recog_op_alt
[i
][alt
].class = recog_op_alt
[matches
][alt
].class;
1626 if (matches
>= 0 || recog_op_alt
[i
][alt
].matched
>= 0
1627 || (predicated
&& recog_data
.operand_type
[i
] == OP_OUT
))
1628 recog_data
.operand_type
[i
] = OP_INOUT
;
1631 /* For each earlyclobber operand, zap the value data. */
1632 for (i
= 0; i
< n_ops
; i
++)
1633 if (recog_op_alt
[i
][alt
].earlyclobber
)
1634 kill_value (recog_data
.operand
[i
], vd
);
1636 /* Within asms, a clobber cannot overlap inputs or outputs.
1637 I wouldn't think this were true for regular insns, but
1638 scan_rtx treats them like that... */
1639 note_stores (PATTERN (insn
), kill_clobbered_value
, vd
);
1641 /* Kill all auto-incremented values. */
1642 /* ??? REG_INC is useless, since stack pushes aren't done that way. */
1643 for_each_rtx (&PATTERN (insn
), kill_autoinc_value
, vd
);
1645 /* Kill all early-clobbered operands. */
1646 for (i
= 0; i
< n_ops
; i
++)
1647 if (recog_op_alt
[i
][alt
].earlyclobber
)
1648 kill_value (recog_data
.operand
[i
], vd
);
1650 /* Special-case plain move instructions, since we may well
1651 be able to do the move from a different register class. */
1652 if (set
&& REG_P (SET_SRC (set
)))
1654 rtx src
= SET_SRC (set
);
1655 unsigned int regno
= REGNO (src
);
1656 enum machine_mode mode
= GET_MODE (src
);
1660 /* If we are accessing SRC in some mode other that what we
1661 set it in, make sure that the replacement is valid. */
1662 if (mode
!= vd
->e
[regno
].mode
)
1664 if (HARD_REGNO_NREGS (regno
, mode
)
1665 > HARD_REGNO_NREGS (regno
, vd
->e
[regno
].mode
))
1666 goto no_move_special_case
;
1669 /* If the destination is also a register, try to find a source
1670 register in the same class. */
1671 if (REG_P (SET_DEST (set
)))
1673 new = find_oldest_value_reg (REGNO_REG_CLASS (regno
), src
, vd
);
1674 if (new && validate_change (insn
, &SET_SRC (set
), new, 0))
1677 fprintf (rtl_dump_file
,
1678 "insn %u: replaced reg %u with %u\n",
1679 INSN_UID (insn
), regno
, REGNO (new));
1681 goto did_replacement
;
1685 /* Otherwise, try all valid registers and see if its valid. */
1686 for (i
= vd
->e
[regno
].oldest_regno
; i
!= regno
;
1687 i
= vd
->e
[i
].next_regno
)
1689 new = maybe_mode_change (vd
->e
[i
].mode
, vd
->e
[regno
].mode
,
1691 if (new != NULL_RTX
)
1693 if (validate_change (insn
, &SET_SRC (set
), new, 0))
1695 ORIGINAL_REGNO (new) = ORIGINAL_REGNO (src
);
1697 fprintf (rtl_dump_file
,
1698 "insn %u: replaced reg %u with %u\n",
1699 INSN_UID (insn
), regno
, REGNO (new));
1701 goto did_replacement
;
1706 no_move_special_case
:
1708 /* For each input operand, replace a hard register with the
1709 eldest live copy that's in an appropriate register class. */
1710 for (i
= 0; i
< n_ops
; i
++)
1712 bool replaced
= false;
1714 /* Don't scan match_operand here, since we've no reg class
1715 information to pass down. Any operands that we could
1716 substitute in will be represented elsewhere. */
1717 if (recog_data
.constraints
[i
][0] == '\0')
1720 /* Don't replace in asms intentionally referencing hard regs. */
1721 if (is_asm
&& GET_CODE (recog_data
.operand
[i
]) == REG
1722 && (REGNO (recog_data
.operand
[i
])
1723 == ORIGINAL_REGNO (recog_data
.operand
[i
])))
1726 if (recog_data
.operand_type
[i
] == OP_IN
)
1728 if (recog_op_alt
[i
][alt
].is_address
)
1730 = replace_oldest_value_addr (recog_data
.operand_loc
[i
],
1731 recog_op_alt
[i
][alt
].class,
1732 VOIDmode
, insn
, vd
);
1733 else if (REG_P (recog_data
.operand
[i
]))
1735 = replace_oldest_value_reg (recog_data
.operand_loc
[i
],
1736 recog_op_alt
[i
][alt
].class,
1738 else if (GET_CODE (recog_data
.operand
[i
]) == MEM
)
1739 replaced
= replace_oldest_value_mem (recog_data
.operand
[i
],
1742 else if (GET_CODE (recog_data
.operand
[i
]) == MEM
)
1743 replaced
= replace_oldest_value_mem (recog_data
.operand
[i
],
1746 /* If we performed any replacement, update match_dups. */
1754 new = *recog_data
.operand_loc
[i
];
1755 recog_data
.operand
[i
] = new;
1756 for (j
= 0; j
< recog_data
.n_dups
; j
++)
1757 if (recog_data
.dup_num
[j
] == i
)
1758 *recog_data
.dup_loc
[j
] = new;
1763 /* Clobber call-clobbered registers. */
1764 if (GET_CODE (insn
) == CALL_INSN
)
1765 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1766 if (TEST_HARD_REG_BIT (regs_invalidated_by_call
, i
))
1767 kill_value_regno (i
, vd
);
1769 /* Notice stores. */
1770 note_stores (PATTERN (insn
), kill_set_value
, vd
);
1772 /* Notice copies. */
1773 if (set
&& REG_P (SET_DEST (set
)) && REG_P (SET_SRC (set
)))
1774 copy_value (SET_DEST (set
), SET_SRC (set
), vd
);
1776 if (insn
== bb
->end
)
1783 /* Main entry point for the forward copy propagation optimization. */
1786 copyprop_hardreg_forward ()
1788 struct value_data
*all_vd
;
1790 basic_block bb
, bbp
;
1792 need_refresh
= false;
1794 all_vd
= xmalloc (sizeof (struct value_data
) * last_basic_block
);
1798 /* If a block has a single predecessor, that we've already
1799 processed, begin with the value data that was live at
1800 the end of the predecessor block. */
1801 /* ??? Ought to use more intelligent queueing of blocks. */
1803 for (bbp
= bb
; bbp
&& bbp
!= bb
->pred
->src
; bbp
= bbp
->prev_bb
);
1805 && ! bb
->pred
->pred_next
1806 && ! (bb
->pred
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
1807 && bb
->pred
->src
!= ENTRY_BLOCK_PTR
1809 all_vd
[bb
->index
] = all_vd
[bb
->pred
->src
->index
];
1811 init_value_data (all_vd
+ bb
->index
);
1813 if (copyprop_hardreg_forward_1 (bb
, all_vd
+ bb
->index
))
1814 need_refresh
= true;
1820 fputs ("\n\n", rtl_dump_file
);
1822 /* ??? Irritatingly, delete_noop_moves does not take a set of blocks
1823 to scan, so we have to do a life update with no initial set of
1824 blocks Just In Case. */
1825 delete_noop_moves (get_insns ());
1826 update_life_info (NULL
, UPDATE_LIFE_GLOBAL_RM_NOTES
,
1828 | PROP_SCAN_DEAD_CODE
1829 | PROP_KILL_DEAD_CODE
);
1835 /* Dump the value chain data to stderr. */
1838 debug_value_data (vd
)
1839 struct value_data
*vd
;
1844 CLEAR_HARD_REG_SET (set
);
1846 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1847 if (vd
->e
[i
].oldest_regno
== i
)
1849 if (vd
->e
[i
].mode
== VOIDmode
)
1851 if (vd
->e
[i
].next_regno
!= INVALID_REGNUM
)
1852 fprintf (stderr
, "[%u] Bad next_regno for empty chain (%u)\n",
1853 i
, vd
->e
[i
].next_regno
);
1857 SET_HARD_REG_BIT (set
, i
);
1858 fprintf (stderr
, "[%u %s] ", i
, GET_MODE_NAME (vd
->e
[i
].mode
));
1860 for (j
= vd
->e
[i
].next_regno
;
1861 j
!= INVALID_REGNUM
;
1862 j
= vd
->e
[j
].next_regno
)
1864 if (TEST_HARD_REG_BIT (set
, j
))
1866 fprintf (stderr
, "[%u] Loop in regno chain\n", j
);
1870 if (vd
->e
[j
].oldest_regno
!= i
)
1872 fprintf (stderr
, "[%u] Bad oldest_regno (%u)\n",
1873 j
, vd
->e
[j
].oldest_regno
);
1876 SET_HARD_REG_BIT (set
, j
);
1877 fprintf (stderr
, "[%u %s] ", j
, GET_MODE_NAME (vd
->e
[j
].mode
));
1879 fputc ('\n', stderr
);
1882 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1883 if (! TEST_HARD_REG_BIT (set
, i
)
1884 && (vd
->e
[i
].mode
!= VOIDmode
1885 || vd
->e
[i
].oldest_regno
!= i
1886 || vd
->e
[i
].next_regno
!= INVALID_REGNUM
))
1887 fprintf (stderr
, "[%u] Non-empty reg in chain (%s %u %i)\n",
1888 i
, GET_MODE_NAME (vd
->e
[i
].mode
), vd
->e
[i
].oldest_regno
,
1889 vd
->e
[i
].next_regno
);
1892 #ifdef ENABLE_CHECKING
1894 validate_value_data (vd
)
1895 struct value_data
*vd
;
1900 CLEAR_HARD_REG_SET (set
);
1902 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1903 if (vd
->e
[i
].oldest_regno
== i
)
1905 if (vd
->e
[i
].mode
== VOIDmode
)
1907 if (vd
->e
[i
].next_regno
!= INVALID_REGNUM
)
1908 internal_error ("validate_value_data: [%u] Bad next_regno for empty chain (%u)",
1909 i
, vd
->e
[i
].next_regno
);
1913 SET_HARD_REG_BIT (set
, i
);
1915 for (j
= vd
->e
[i
].next_regno
;
1916 j
!= INVALID_REGNUM
;
1917 j
= vd
->e
[j
].next_regno
)
1919 if (TEST_HARD_REG_BIT (set
, j
))
1920 internal_error ("validate_value_data: Loop in regno chain (%u)",
1922 if (vd
->e
[j
].oldest_regno
!= i
)
1923 internal_error ("validate_value_data: [%u] Bad oldest_regno (%u)",
1924 j
, vd
->e
[j
].oldest_regno
);
1926 SET_HARD_REG_BIT (set
, j
);
1930 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
1931 if (! TEST_HARD_REG_BIT (set
, i
)
1932 && (vd
->e
[i
].mode
!= VOIDmode
1933 || vd
->e
[i
].oldest_regno
!= i
1934 || vd
->e
[i
].next_regno
!= INVALID_REGNUM
))
1935 internal_error ("validate_value_data: [%u] Non-empty reg in chain (%s %u %i)",
1936 i
, GET_MODE_NAME (vd
->e
[i
].mode
), vd
->e
[i
].oldest_regno
,
1937 vd
->e
[i
].next_regno
);