1 /* Move registers around to reduce number of move instructions needed.
2 Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997,
3 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
4 Free Software Foundation, Inc.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
23 /* This module makes some simple RTL code transformations which
24 improve the subsequent register allocation. */
28 #include "coretypes.h"
30 #include "rtl.h" /* stdio.h must precede rtl.h for FFS. */
32 #include "insn-config.h"
36 #include "hard-reg-set.h"
40 #include "basic-block.h"
45 #include "tree-pass.h"
48 static int optimize_reg_copy_1 (rtx
, rtx
, rtx
);
49 static void optimize_reg_copy_2 (rtx
, rtx
, rtx
);
50 static void optimize_reg_copy_3 (rtx
, rtx
, rtx
);
51 static void copy_src_to_dest (rtx
, rtx
, rtx
);
61 int with
[MAX_RECOG_OPERANDS
];
62 enum match_use use
[MAX_RECOG_OPERANDS
];
63 int commutative
[MAX_RECOG_OPERANDS
];
64 int early_clobber
[MAX_RECOG_OPERANDS
];
67 static int find_matches (rtx
, struct match
*);
68 static int fixup_match_2 (rtx
, rtx
, rtx
, rtx
);
70 /* Return nonzero if registers with CLASS1 and CLASS2 can be merged without
71 causing too much register allocation problems. */
73 regclass_compatible_p (enum reg_class class0
, enum reg_class class1
)
75 return (class0
== class1
76 || (reg_class_subset_p (class0
, class1
)
77 && ! CLASS_LIKELY_SPILLED_P (class0
))
78 || (reg_class_subset_p (class1
, class0
)
79 && ! CLASS_LIKELY_SPILLED_P (class1
)));
85 /* Find the place in the rtx X where REG is used as a memory address.
86 Return the MEM rtx that so uses it.
87 If PLUSCONST is nonzero, search instead for a memory address equivalent to
88 (plus REG (const_int PLUSCONST)).
90 If such an address does not appear, return 0.
91 If REG appears more than once, or is used other than in such an address,
95 find_use_as_address (rtx x
, rtx reg
, HOST_WIDE_INT plusconst
)
97 enum rtx_code code
= GET_CODE (x
);
98 const char * const fmt
= GET_RTX_FORMAT (code
);
103 if (code
== MEM
&& XEXP (x
, 0) == reg
&& plusconst
== 0)
106 if (code
== MEM
&& GET_CODE (XEXP (x
, 0)) == PLUS
107 && XEXP (XEXP (x
, 0), 0) == reg
108 && CONST_INT_P (XEXP (XEXP (x
, 0), 1))
109 && INTVAL (XEXP (XEXP (x
, 0), 1)) == plusconst
)
112 if (code
== SIGN_EXTRACT
|| code
== ZERO_EXTRACT
)
114 /* If REG occurs inside a MEM used in a bit-field reference,
115 that is unacceptable. */
116 if (find_use_as_address (XEXP (x
, 0), reg
, 0) != 0)
117 return (rtx
) (size_t) 1;
121 return (rtx
) (size_t) 1;
123 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
127 tem
= find_use_as_address (XEXP (x
, i
), reg
, plusconst
);
131 return (rtx
) (size_t) 1;
133 else if (fmt
[i
] == 'E')
136 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
138 tem
= find_use_as_address (XVECEXP (x
, i
, j
), reg
, plusconst
);
142 return (rtx
) (size_t) 1;
151 /* INC_INSN is an instruction that adds INCREMENT to REG.
152 Try to fold INC_INSN as a post/pre in/decrement into INSN.
153 Iff INC_INSN_SET is nonzero, inc_insn has a destination different from src.
154 Return nonzero for success. */
156 try_auto_increment (rtx insn
, rtx inc_insn
, rtx inc_insn_set
, rtx reg
,
157 HOST_WIDE_INT increment
, int pre
)
159 enum rtx_code inc_code
;
161 rtx pset
= single_set (insn
);
164 /* Can't use the size of SET_SRC, we might have something like
165 (sign_extend:SI (mem:QI ... */
166 rtx use
= find_use_as_address (pset
, reg
, 0);
167 if (use
!= 0 && use
!= (rtx
) (size_t) 1)
169 int size
= GET_MODE_SIZE (GET_MODE (use
));
171 || (HAVE_POST_INCREMENT
172 && pre
== 0 && (inc_code
= POST_INC
, increment
== size
))
173 || (HAVE_PRE_INCREMENT
174 && pre
== 1 && (inc_code
= PRE_INC
, increment
== size
))
175 || (HAVE_POST_DECREMENT
176 && pre
== 0 && (inc_code
= POST_DEC
, increment
== -size
))
177 || (HAVE_PRE_DECREMENT
178 && pre
== 1 && (inc_code
= PRE_DEC
, increment
== -size
))
184 &SET_SRC (inc_insn_set
),
185 XEXP (SET_SRC (inc_insn_set
), 0), 1);
186 validate_change (insn
, &XEXP (use
, 0),
187 gen_rtx_fmt_e (inc_code
, Pmode
, reg
), 1);
188 if (apply_change_group ())
190 /* If there is a REG_DEAD note on this insn, we must
191 change this not to REG_UNUSED meaning that the register
192 is set, but the value is dead. Failure to do so will
193 result in sched1 dying -- when it recomputes lifetime
194 information, the number of REG_DEAD notes will have
196 rtx note
= find_reg_note (insn
, REG_DEAD
, reg
);
198 PUT_REG_NOTE_KIND (note
, REG_UNUSED
);
200 add_reg_note (insn
, REG_INC
, reg
);
203 delete_insn (inc_insn
);
214 static int *regno_src_regno
;
216 /* INSN is a copy from SRC to DEST, both registers, and SRC does not die
219 Search forward to see if SRC dies before either it or DEST is modified,
220 but don't scan past the end of a basic block. If so, we can replace SRC
221 with DEST and let SRC die in INSN.
223 This will reduce the number of registers live in that range and may enable
224 DEST to be tied to SRC, thus often saving one register in addition to a
225 register-register copy. */
228 optimize_reg_copy_1 (rtx insn
, rtx dest
, rtx src
)
233 int sregno
= REGNO (src
);
234 int dregno
= REGNO (dest
);
235 basic_block bb
= BLOCK_FOR_INSN (insn
);
237 /* We don't want to mess with hard regs if register classes are small. */
239 || (SMALL_REGISTER_CLASSES
240 && (sregno
< FIRST_PSEUDO_REGISTER
241 || dregno
< FIRST_PSEUDO_REGISTER
))
242 /* We don't see all updates to SP if they are in an auto-inc memory
243 reference, so we must disallow this optimization on them. */
244 || sregno
== STACK_POINTER_REGNUM
|| dregno
== STACK_POINTER_REGNUM
)
247 for (p
= NEXT_INSN (insn
); p
; p
= NEXT_INSN (p
))
251 if (BLOCK_FOR_INSN (p
) != bb
)
254 if (reg_set_p (src
, p
) || reg_set_p (dest
, p
)
255 /* If SRC is an asm-declared register, it must not be replaced
256 in any asm. Unfortunately, the REG_EXPR tree for the asm
257 variable may be absent in the SRC rtx, so we can't check the
258 actual register declaration easily (the asm operand will have
259 it, though). To avoid complicating the test for a rare case,
260 we just don't perform register replacement for a hard reg
261 mentioned in an asm. */
262 || (sregno
< FIRST_PSEUDO_REGISTER
263 && asm_noperands (PATTERN (p
)) >= 0
264 && reg_overlap_mentioned_p (src
, PATTERN (p
)))
265 /* Don't change hard registers used by a call. */
266 || (CALL_P (p
) && sregno
< FIRST_PSEUDO_REGISTER
267 && find_reg_fusage (p
, USE
, src
))
268 /* Don't change a USE of a register. */
269 || (GET_CODE (PATTERN (p
)) == USE
270 && reg_overlap_mentioned_p (src
, XEXP (PATTERN (p
), 0))))
273 /* See if all of SRC dies in P. This test is slightly more
274 conservative than it needs to be. */
275 if ((note
= find_regno_note (p
, REG_DEAD
, sregno
)) != 0
276 && GET_MODE (XEXP (note
, 0)) == GET_MODE (src
))
283 int s_freq_calls
= 0;
284 int d_freq_calls
= 0;
286 /* We can do the optimization. Scan forward from INSN again,
287 replacing regs as we go. Set FAILED if a replacement can't
288 be done. In that case, we can't move the death note for SRC.
289 This should be rare. */
291 /* Set to stop at next insn. */
292 for (q
= next_real_insn (insn
);
293 q
!= next_real_insn (p
);
294 q
= next_real_insn (q
))
296 if (reg_overlap_mentioned_p (src
, PATTERN (q
)))
298 /* If SRC is a hard register, we might miss some
299 overlapping registers with validate_replace_rtx,
300 so we would have to undo it. We can't if DEST is
301 present in the insn, so fail in that combination
303 if (sregno
< FIRST_PSEUDO_REGISTER
304 && reg_mentioned_p (dest
, PATTERN (q
)))
307 /* Attempt to replace all uses. */
308 else if (!validate_replace_rtx (src
, dest
, q
))
311 /* If this succeeded, but some part of the register
312 is still present, undo the replacement. */
313 else if (sregno
< FIRST_PSEUDO_REGISTER
314 && reg_overlap_mentioned_p (src
, PATTERN (q
)))
316 validate_replace_rtx (dest
, src
, q
);
321 /* For SREGNO, count the total number of insns scanned.
322 For DREGNO, count the total number of insns scanned after
323 passing the death note for DREGNO. */
328 /* If the insn in which SRC dies is a CALL_INSN, don't count it
329 as a call that has been crossed. Otherwise, count it. */
330 if (q
!= p
&& CALL_P (q
))
332 /* Similarly, total calls for SREGNO, total calls beyond
333 the death note for DREGNO. */
335 s_freq_calls
+= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (q
));
339 d_freq_calls
+= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (q
));
343 /* If DEST dies here, remove the death note and save it for
344 later. Make sure ALL of DEST dies here; again, this is
345 overly conservative. */
347 && (dest_death
= find_regno_note (q
, REG_DEAD
, dregno
)) != 0)
349 if (GET_MODE (XEXP (dest_death
, 0)) != GET_MODE (dest
))
350 failed
= 1, dest_death
= 0;
352 remove_note (q
, dest_death
);
358 /* These counters need to be updated if and only if we are
359 going to move the REG_DEAD note. */
360 if (sregno
>= FIRST_PSEUDO_REGISTER
)
362 if (REG_LIVE_LENGTH (sregno
) >= 0)
364 REG_LIVE_LENGTH (sregno
) -= s_length
;
365 /* REG_LIVE_LENGTH is only an approximation after
366 combine if sched is not run, so make sure that we
367 still have a reasonable value. */
368 if (REG_LIVE_LENGTH (sregno
) < 2)
369 REG_LIVE_LENGTH (sregno
) = 2;
372 REG_N_CALLS_CROSSED (sregno
) -= s_n_calls
;
373 REG_FREQ_CALLS_CROSSED (sregno
) -= s_freq_calls
;
376 /* Move death note of SRC from P to INSN. */
377 remove_note (p
, note
);
378 XEXP (note
, 1) = REG_NOTES (insn
);
379 REG_NOTES (insn
) = note
;
382 /* DEST is also dead if INSN has a REG_UNUSED note for DEST. */
384 && (dest_death
= find_regno_note (insn
, REG_UNUSED
, dregno
)))
386 PUT_REG_NOTE_KIND (dest_death
, REG_DEAD
);
387 remove_note (insn
, dest_death
);
390 /* Put death note of DEST on P if we saw it die. */
393 XEXP (dest_death
, 1) = REG_NOTES (p
);
394 REG_NOTES (p
) = dest_death
;
396 if (dregno
>= FIRST_PSEUDO_REGISTER
)
398 /* If and only if we are moving the death note for DREGNO,
399 then we need to update its counters. */
400 if (REG_LIVE_LENGTH (dregno
) >= 0)
401 REG_LIVE_LENGTH (dregno
) += d_length
;
402 REG_N_CALLS_CROSSED (dregno
) += d_n_calls
;
403 REG_FREQ_CALLS_CROSSED (dregno
) += d_freq_calls
;
410 /* If SRC is a hard register which is set or killed in some other
411 way, we can't do this optimization. */
412 else if (sregno
< FIRST_PSEUDO_REGISTER
413 && dead_or_set_p (p
, src
))
419 /* INSN is a copy of SRC to DEST, in which SRC dies. See if we now have
420 a sequence of insns that modify DEST followed by an insn that sets
421 SRC to DEST in which DEST dies, with no prior modification of DEST.
422 (There is no need to check if the insns in between actually modify
423 DEST. We should not have cases where DEST is not modified, but
424 the optimization is safe if no such modification is detected.)
425 In that case, we can replace all uses of DEST, starting with INSN and
426 ending with the set of SRC to DEST, with SRC. We do not do this
427 optimization if a CALL_INSN is crossed unless SRC already crosses a
428 call or if DEST dies before the copy back to SRC.
430 It is assumed that DEST and SRC are pseudos; it is too complicated to do
431 this for hard registers since the substitutions we may make might fail. */
434 optimize_reg_copy_2 (rtx insn
, rtx dest
, rtx src
)
438 int sregno
= REGNO (src
);
439 int dregno
= REGNO (dest
);
440 basic_block bb
= BLOCK_FOR_INSN (insn
);
442 for (p
= NEXT_INSN (insn
); p
; p
= NEXT_INSN (p
))
446 if (BLOCK_FOR_INSN (p
) != bb
)
449 set
= single_set (p
);
450 if (set
&& SET_SRC (set
) == dest
&& SET_DEST (set
) == src
451 && find_reg_note (p
, REG_DEAD
, dest
))
453 /* We can do the optimization. Scan forward from INSN again,
454 replacing regs as we go. */
456 /* Set to stop at next insn. */
457 for (q
= insn
; q
!= NEXT_INSN (p
); q
= NEXT_INSN (q
))
460 if (reg_mentioned_p (dest
, PATTERN (q
)))
464 PATTERN (q
) = replace_rtx (PATTERN (q
), dest
, src
);
465 note
= FIND_REG_INC_NOTE (q
, dest
);
468 remove_note (q
, note
);
469 add_reg_note (q
, REG_INC
, src
);
476 int freq
= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (q
));
477 REG_N_CALLS_CROSSED (dregno
)--;
478 REG_N_CALLS_CROSSED (sregno
)++;
479 REG_FREQ_CALLS_CROSSED (dregno
) -= freq
;
480 REG_FREQ_CALLS_CROSSED (sregno
) += freq
;
484 remove_note (p
, find_reg_note (p
, REG_DEAD
, dest
));
485 REG_N_DEATHS (dregno
)--;
486 remove_note (insn
, find_reg_note (insn
, REG_DEAD
, src
));
487 REG_N_DEATHS (sregno
)--;
491 if (reg_set_p (src
, p
)
492 || find_reg_note (p
, REG_DEAD
, dest
)
493 || (CALL_P (p
) && REG_N_CALLS_CROSSED (sregno
) == 0))
498 /* INSN is a ZERO_EXTEND or SIGN_EXTEND of SRC to DEST.
499 Look if SRC dies there, and if it is only set once, by loading
500 it from memory. If so, try to incorporate the zero/sign extension
501 into the memory read, change SRC to the mode of DEST, and alter
502 the remaining accesses to use the appropriate SUBREG. This allows
503 SRC and DEST to be tied later. */
505 optimize_reg_copy_3 (rtx insn
, rtx dest
, rtx src
)
507 rtx src_reg
= XEXP (src
, 0);
508 int src_no
= REGNO (src_reg
);
509 int dst_no
= REGNO (dest
);
511 enum machine_mode old_mode
;
512 basic_block bb
= BLOCK_FOR_INSN (insn
);
514 if (src_no
< FIRST_PSEUDO_REGISTER
515 || dst_no
< FIRST_PSEUDO_REGISTER
516 || ! find_reg_note (insn
, REG_DEAD
, src_reg
)
517 || REG_N_DEATHS (src_no
) != 1
518 || REG_N_SETS (src_no
) != 1)
521 for (p
= PREV_INSN (insn
); p
&& ! reg_set_p (src_reg
, p
); p
= PREV_INSN (p
))
522 if (INSN_P (p
) && BLOCK_FOR_INSN (p
) != bb
)
525 if (! p
|| BLOCK_FOR_INSN (p
) != bb
)
528 if (! (set
= single_set (p
))
529 || !MEM_P (SET_SRC (set
))
530 /* If there's a REG_EQUIV note, this must be an insn that loads an
531 argument. Prefer keeping the note over doing this optimization. */
532 || find_reg_note (p
, REG_EQUIV
, NULL_RTX
)
533 || SET_DEST (set
) != src_reg
)
536 /* Be conservative: although this optimization is also valid for
537 volatile memory references, that could cause trouble in later passes. */
538 if (MEM_VOLATILE_P (SET_SRC (set
)))
541 /* Do not use a SUBREG to truncate from one mode to another if truncation
543 if (GET_MODE_BITSIZE (GET_MODE (src_reg
)) <= GET_MODE_BITSIZE (GET_MODE (src
))
544 && !TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (GET_MODE (src
)),
545 GET_MODE_BITSIZE (GET_MODE (src_reg
))))
548 old_mode
= GET_MODE (src_reg
);
549 PUT_MODE (src_reg
, GET_MODE (src
));
550 XEXP (src
, 0) = SET_SRC (set
);
552 /* Include this change in the group so that it's easily undone if
553 one of the changes in the group is invalid. */
554 validate_change (p
, &SET_SRC (set
), src
, 1);
556 /* Now walk forward making additional replacements. We want to be able
557 to undo all the changes if a later substitution fails. */
558 while (p
= NEXT_INSN (p
), p
!= insn
)
563 /* Make a tentative change. */
564 validate_replace_rtx_group (src_reg
,
565 gen_lowpart_SUBREG (old_mode
, src_reg
),
569 validate_replace_rtx_group (src
, src_reg
, insn
);
571 /* Now see if all the changes are valid. */
572 if (! apply_change_group ())
574 /* One or more changes were no good. Back out everything. */
575 PUT_MODE (src_reg
, old_mode
);
576 XEXP (src
, 0) = src_reg
;
580 rtx note
= find_reg_note (p
, REG_EQUAL
, NULL_RTX
);
582 remove_note (p
, note
);
587 /* If we were not able to update the users of src to use dest directly, try
588 instead moving the value to dest directly before the operation. */
591 copy_src_to_dest (rtx insn
, rtx src
, rtx dest
)
605 /* A REG_LIVE_LENGTH of -1 indicates the register is equivalent to a constant
606 or memory location and is used infrequently; a REG_LIVE_LENGTH of -2 is
607 parameter when there is no frame pointer that is not allocated a register.
608 For now, we just reject them, rather than incrementing the live length. */
611 && REG_LIVE_LENGTH (REGNO (src
)) > 0
613 && REG_LIVE_LENGTH (REGNO (dest
)) > 0
614 && (set
= single_set (insn
)) != NULL_RTX
615 && !reg_mentioned_p (dest
, SET_SRC (set
))
616 && GET_MODE (src
) == GET_MODE (dest
))
618 int old_num_regs
= reg_rtx_no
;
620 /* Generate the src->dest move. */
622 emit_move_insn (dest
, src
);
625 /* If this sequence uses new registers, we may not use it. */
626 if (old_num_regs
!= reg_rtx_no
627 || ! validate_replace_rtx (src
, dest
, insn
))
629 /* We have to restore reg_rtx_no to its old value, lest
630 recompute_reg_usage will try to compute the usage of the
631 new regs, yet reg_n_info is not valid for them. */
632 reg_rtx_no
= old_num_regs
;
635 emit_insn_before (seq
, insn
);
636 move_insn
= PREV_INSN (insn
);
637 p_move_notes
= ®_NOTES (move_insn
);
638 p_insn_notes
= ®_NOTES (insn
);
640 /* Move any notes mentioning src to the move instruction. */
641 for (link
= REG_NOTES (insn
); link
!= NULL_RTX
; link
= next
)
643 next
= XEXP (link
, 1);
644 if (XEXP (link
, 0) == src
)
646 *p_move_notes
= link
;
647 p_move_notes
= &XEXP (link
, 1);
651 *p_insn_notes
= link
;
652 p_insn_notes
= &XEXP (link
, 1);
656 *p_move_notes
= NULL_RTX
;
657 *p_insn_notes
= NULL_RTX
;
659 insn_uid
= INSN_UID (insn
);
660 move_uid
= INSN_UID (move_insn
);
662 /* Update the various register tables. */
663 dest_regno
= REGNO (dest
);
664 INC_REG_N_SETS (dest_regno
, 1);
665 REG_LIVE_LENGTH (dest_regno
)++;
666 src_regno
= REGNO (src
);
667 if (! find_reg_note (move_insn
, REG_DEAD
, src
))
668 REG_LIVE_LENGTH (src_regno
)++;
672 /* reg_set_in_bb[REGNO] points to basic block iff the register is set
673 only once in the given block and has REG_EQUAL note. */
675 static basic_block
*reg_set_in_bb
;
677 /* Size of reg_set_in_bb array. */
678 static unsigned int max_reg_computed
;
681 /* Return whether REG is set in only one location, and is set to a
682 constant, but is set in a different basic block from INSN (an
683 instructions which uses REG). In this case REG is equivalent to a
684 constant, and we don't want to break that equivalence, because that
685 may increase register pressure and make reload harder. If REG is
686 set in the same basic block as INSN, we don't worry about it,
687 because we'll probably need a register anyhow (??? but what if REG
688 is used in a different basic block as well as this one?). */
691 reg_is_remote_constant_p (rtx reg
, rtx insn
)
699 max_reg_computed
= max
= max_reg_num ();
700 reg_set_in_bb
= XCNEWVEC (basic_block
, max
);
710 /* This is the instruction which sets REG. If there is a
711 REG_EQUAL note, then REG is equivalent to a constant. */
713 && REG_P (SET_DEST (s
))
714 && REG_N_SETS (REGNO (SET_DEST (s
))) == 1
715 && find_reg_note (p
, REG_EQUAL
, NULL_RTX
))
716 reg_set_in_bb
[REGNO (SET_DEST (s
))] = bb
;
720 gcc_assert (REGNO (reg
) < max_reg_computed
);
721 if (reg_set_in_bb
[REGNO (reg
)] == NULL
)
723 return (reg_set_in_bb
[REGNO (reg
)] != BLOCK_FOR_INSN (insn
));
726 /* INSN is adding a CONST_INT to a REG. We search backwards looking for
727 another add immediate instruction with the same source and dest registers,
728 and if we find one, we change INSN to an increment, and return 1. If
729 no changes are made, we return 0.
732 (set (reg100) (plus reg1 offset1))
734 (set (reg100) (plus reg1 offset2))
736 (set (reg100) (plus reg1 offset1))
738 (set (reg100) (plus reg100 offset2-offset1)) */
740 /* ??? What does this comment mean? */
741 /* cse disrupts preincrement / postdecrement sequences when it finds a
742 hard register as ultimate source, like the frame pointer. */
745 fixup_match_2 (rtx insn
, rtx dst
, rtx src
, rtx offset
)
747 rtx p
, dst_death
= 0;
748 int length
, num_calls
= 0, freq_calls
= 0;
749 basic_block bb
= BLOCK_FOR_INSN (insn
);
751 /* If SRC dies in INSN, we'd have to move the death note. This is
752 considered to be very unlikely, so we just skip the optimization
754 if (find_regno_note (insn
, REG_DEAD
, REGNO (src
)))
757 /* Scan backward to find the first instruction that sets DST. */
759 for (length
= 0, p
= PREV_INSN (insn
); p
; p
= PREV_INSN (p
))
765 if (BLOCK_FOR_INSN (p
) != bb
)
768 if (find_regno_note (p
, REG_DEAD
, REGNO (dst
)))
773 pset
= single_set (p
);
774 if (pset
&& SET_DEST (pset
) == dst
775 && GET_CODE (SET_SRC (pset
)) == PLUS
776 && XEXP (SET_SRC (pset
), 0) == src
777 && CONST_INT_P (XEXP (SET_SRC (pset
), 1)))
779 HOST_WIDE_INT newconst
780 = INTVAL (offset
) - INTVAL (XEXP (SET_SRC (pset
), 1));
781 rtx add
= gen_add3_insn (dst
, dst
, GEN_INT (newconst
));
783 if (add
&& validate_change (insn
, &PATTERN (insn
), add
, 0))
785 /* Remove the death note for DST from DST_DEATH. */
788 remove_death (REGNO (dst
), dst_death
);
789 REG_LIVE_LENGTH (REGNO (dst
)) += length
;
790 REG_N_CALLS_CROSSED (REGNO (dst
)) += num_calls
;
791 REG_FREQ_CALLS_CROSSED (REGNO (dst
)) += freq_calls
;
796 "Fixed operand of insn %d.\n",
800 for (p
= PREV_INSN (insn
); p
; p
= PREV_INSN (p
))
804 if (BLOCK_FOR_INSN (p
) != bb
)
806 if (reg_overlap_mentioned_p (dst
, PATTERN (p
)))
808 if (try_auto_increment (p
, insn
, 0, dst
, newconst
, 0))
813 for (p
= NEXT_INSN (insn
); p
; p
= NEXT_INSN (p
))
817 if (BLOCK_FOR_INSN (p
) != bb
)
819 if (reg_overlap_mentioned_p (dst
, PATTERN (p
)))
821 try_auto_increment (p
, insn
, 0, dst
, newconst
, 1);
830 if (reg_set_p (dst
, PATTERN (p
)))
833 /* If we have passed a call instruction, and the
834 pseudo-reg SRC is not already live across a call,
835 then don't perform the optimization. */
836 /* reg_set_p is overly conservative for CALL_INSNS, thinks that all
837 hard regs are clobbered. Thus, we only use it for src for
844 freq_calls
+= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (p
));
847 if (REG_N_CALLS_CROSSED (REGNO (src
)) == 0)
850 if (call_used_regs
[REGNO (dst
)]
851 || find_reg_fusage (p
, CLOBBER
, dst
))
854 else if (reg_set_p (src
, PATTERN (p
)))
861 /* A forward pass. Replace output operands with input operands. */
864 regmove_forward_pass (void)
869 if (! flag_expensive_optimizations
)
873 fprintf (dump_file
, "Starting forward pass...\n");
877 FOR_BB_INSNS (bb
, insn
)
879 rtx set
= single_set (insn
);
883 if ((GET_CODE (SET_SRC (set
)) == SIGN_EXTEND
884 || GET_CODE (SET_SRC (set
)) == ZERO_EXTEND
)
885 && REG_P (XEXP (SET_SRC (set
), 0))
886 && REG_P (SET_DEST (set
)))
887 optimize_reg_copy_3 (insn
, SET_DEST (set
), SET_SRC (set
));
889 if (REG_P (SET_SRC (set
))
890 && REG_P (SET_DEST (set
)))
892 /* If this is a register-register copy where SRC is not dead,
893 see if we can optimize it. If this optimization succeeds,
894 it will become a copy where SRC is dead. */
895 if ((find_reg_note (insn
, REG_DEAD
, SET_SRC (set
))
896 || optimize_reg_copy_1 (insn
, SET_DEST (set
), SET_SRC (set
)))
897 && REGNO (SET_DEST (set
)) >= FIRST_PSEUDO_REGISTER
)
899 /* Similarly for a pseudo-pseudo copy when SRC is dead. */
900 if (REGNO (SET_SRC (set
)) >= FIRST_PSEUDO_REGISTER
)
901 optimize_reg_copy_2 (insn
, SET_DEST (set
), SET_SRC (set
));
902 if (regno_src_regno
[REGNO (SET_DEST (set
))] < 0
903 && SET_SRC (set
) != SET_DEST (set
))
905 int srcregno
= REGNO (SET_SRC (set
));
906 if (regno_src_regno
[srcregno
] >= 0)
907 srcregno
= regno_src_regno
[srcregno
];
908 regno_src_regno
[REGNO (SET_DEST (set
))] = srcregno
;
916 /* A backward pass. Replace input operands with output operands. */
919 regmove_backward_pass (void)
925 fprintf (dump_file
, "Starting backward pass...\n");
927 FOR_EACH_BB_REVERSE (bb
)
929 /* ??? Use the safe iterator because fixup_match_2 can remove
930 insns via try_auto_increment. */
931 FOR_BB_INSNS_REVERSE_SAFE (bb
, insn
, prev
)
934 rtx copy_src
, copy_dst
;
941 if (! find_matches (insn
, &match
))
944 /* Now scan through the operands looking for a destination operand
945 which is supposed to match a source operand.
946 Then scan backward for an instruction which sets the source
947 operand. If safe, then replace the source operand with the
948 dest operand in both instructions. */
952 for (op_no
= 0; op_no
< recog_data
.n_operands
; op_no
++)
954 rtx set
, p
, src
, dst
;
955 rtx src_note
, dst_note
;
956 int num_calls
= 0, freq_calls
= 0;
957 enum reg_class src_class
, dst_class
;
960 match_no
= match
.with
[op_no
];
962 /* Nothing to do if the two operands aren't supposed to match. */
966 dst
= recog_data
.operand
[match_no
];
967 src
= recog_data
.operand
[op_no
];
973 || REGNO (dst
) < FIRST_PSEUDO_REGISTER
974 || REG_LIVE_LENGTH (REGNO (dst
)) < 0
975 || GET_MODE (src
) != GET_MODE (dst
))
978 /* If the operands already match, then there is nothing to do. */
979 if (operands_match_p (src
, dst
))
982 if (match
.commutative
[op_no
] >= 0)
984 rtx comm
= recog_data
.operand
[match
.commutative
[op_no
]];
985 if (operands_match_p (comm
, dst
))
989 set
= single_set (insn
);
993 /* Note that single_set ignores parts of a parallel set for
994 which one of the destinations is REG_UNUSED. We can't
995 handle that here, since we can wind up rewriting things
996 such that a single register is set twice within a single
998 if (reg_set_p (src
, insn
))
1001 /* match_no/dst must be a write-only operand, and
1002 operand_operand/src must be a read-only operand. */
1003 if (match
.use
[op_no
] != READ
1004 || match
.use
[match_no
] != WRITE
)
1007 if (match
.early_clobber
[match_no
]
1008 && count_occurrences (PATTERN (insn
), src
, 0) > 1)
1011 /* Make sure match_no is the destination. */
1012 if (recog_data
.operand
[match_no
] != SET_DEST (set
))
1015 if (REGNO (src
) < FIRST_PSEUDO_REGISTER
)
1017 if (GET_CODE (SET_SRC (set
)) == PLUS
1018 && CONST_INT_P (XEXP (SET_SRC (set
), 1))
1019 && XEXP (SET_SRC (set
), 0) == src
1020 && fixup_match_2 (insn
, dst
, src
,
1021 XEXP (SET_SRC (set
), 1)))
1025 src_class
= reg_preferred_class (REGNO (src
));
1026 dst_class
= reg_preferred_class (REGNO (dst
));
1028 if (! (src_note
= find_reg_note (insn
, REG_DEAD
, src
)))
1030 /* We used to force the copy here like in other cases, but
1031 it produces worse code, as it eliminates no copy
1032 instructions and the copy emitted will be produced by
1033 reload anyway. On patterns with multiple alternatives,
1034 there may be better solution available.
1036 In particular this change produced slower code for numeric
1042 if (! regclass_compatible_p (src_class
, dst_class
))
1052 /* Can not modify an earlier insn to set dst if this insn
1053 uses an old value in the source. */
1054 if (reg_overlap_mentioned_p (dst
, SET_SRC (set
)))
1064 /* If src is set once in a different basic block,
1065 and is set equal to a constant, then do not use
1066 it for this optimization, as this would make it
1067 no longer equivalent to a constant. */
1069 if (reg_is_remote_constant_p (src
, insn
))
1082 "Could fix operand %d of insn %d matching operand %d.\n",
1083 op_no
, INSN_UID (insn
), match_no
);
1085 /* Scan backward to find the first instruction that uses
1086 the input operand. If the operand is set here, then
1087 replace it in both instructions with match_no. */
1089 for (length
= 0, p
= PREV_INSN (insn
); p
; p
= PREV_INSN (p
))
1095 if (BLOCK_FOR_INSN (p
) != bb
)
1100 /* ??? See if all of SRC is set in P. This test is much
1101 more conservative than it needs to be. */
1102 pset
= single_set (p
);
1103 if (pset
&& SET_DEST (pset
) == src
)
1105 /* We use validate_replace_rtx, in case there
1106 are multiple identical source operands. All of
1107 them have to be changed at the same time. */
1108 if (validate_replace_rtx (src
, dst
, insn
))
1110 if (validate_change (p
, &SET_DEST (pset
),
1115 /* Change all source operands back.
1116 This modifies the dst as a side-effect. */
1117 validate_replace_rtx (dst
, src
, insn
);
1118 /* Now make sure the dst is right. */
1119 validate_change (insn
,
1120 recog_data
.operand_loc
[match_no
],
1127 /* We can't make this change if SRC is read or
1128 partially written in P, since we are going to
1129 eliminate SRC. We can't make this change
1130 if DST is mentioned at all in P,
1131 since we are going to change its value. */
1132 if (reg_overlap_mentioned_p (src
, PATTERN (p
))
1133 || reg_mentioned_p (dst
, PATTERN (p
)))
1136 /* If we have passed a call instruction, and the
1137 pseudo-reg DST is not already live across a call,
1138 then don't perform the optimization. */
1142 freq_calls
+= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (p
));
1144 if (REG_N_CALLS_CROSSED (REGNO (dst
)) == 0)
1153 /* Remove the death note for SRC from INSN. */
1154 remove_note (insn
, src_note
);
1155 /* Move the death note for SRC to P if it is used
1157 if (reg_overlap_mentioned_p (src
, PATTERN (p
)))
1159 XEXP (src_note
, 1) = REG_NOTES (p
);
1160 REG_NOTES (p
) = src_note
;
1162 /* If there is a REG_DEAD note for DST on P, then remove
1163 it, because DST is now set there. */
1164 if ((dst_note
= find_reg_note (p
, REG_DEAD
, dst
)))
1165 remove_note (p
, dst_note
);
1167 dstno
= REGNO (dst
);
1168 srcno
= REGNO (src
);
1170 INC_REG_N_SETS (dstno
, 1);
1171 INC_REG_N_SETS (srcno
, -1);
1173 REG_N_CALLS_CROSSED (dstno
) += num_calls
;
1174 REG_N_CALLS_CROSSED (srcno
) -= num_calls
;
1175 REG_FREQ_CALLS_CROSSED (dstno
) += freq_calls
;
1176 REG_FREQ_CALLS_CROSSED (srcno
) -= freq_calls
;
1178 REG_LIVE_LENGTH (dstno
) += length
;
1179 if (REG_LIVE_LENGTH (srcno
) >= 0)
1181 REG_LIVE_LENGTH (srcno
) -= length
;
1182 /* REG_LIVE_LENGTH is only an approximation after
1183 combine if sched is not run, so make sure that we
1184 still have a reasonable value. */
1185 if (REG_LIVE_LENGTH (srcno
) < 2)
1186 REG_LIVE_LENGTH (srcno
) = 2;
1191 "Fixed operand %d of insn %d matching operand %d.\n",
1192 op_no
, INSN_UID (insn
), match_no
);
1198 /* If we weren't able to replace any of the alternatives, try an
1199 alternative approach of copying the source to the destination. */
1200 if (!success
&& copy_src
!= NULL_RTX
)
1201 copy_src_to_dest (insn
, copy_src
, copy_dst
);
1206 /* Main entry for the register move optimization. */
1209 regmove_optimize (void)
1212 int nregs
= max_reg_num ();
1214 df_note_add_problem ();
1217 regstat_init_n_sets_and_refs ();
1218 regstat_compute_ri ();
1220 regno_src_regno
= XNEWVEC (int, nregs
);
1221 for (i
= nregs
; --i
>= 0; )
1222 regno_src_regno
[i
] = -1;
1224 /* A forward pass. Replace output operands with input operands. */
1225 regmove_forward_pass ();
1227 /* A backward pass. Replace input operands with output operands. */
1228 regmove_backward_pass ();
1231 free (regno_src_regno
);
1234 free (reg_set_in_bb
);
1235 reg_set_in_bb
= NULL
;
1237 regstat_free_n_sets_and_refs ();
1242 /* Returns nonzero if INSN's pattern has matching constraints for any operand.
1243 Returns 0 if INSN can't be recognized, or if the alternative can't be
1246 Initialize the info in MATCHP based on the constraints. */
1249 find_matches (rtx insn
, struct match
*matchp
)
1251 int likely_spilled
[MAX_RECOG_OPERANDS
];
1253 int any_matches
= 0;
1255 extract_insn (insn
);
1256 if (! constrain_operands (0))
1259 /* Must initialize this before main loop, because the code for
1260 the commutative case may set matches for operands other than
1262 for (op_no
= recog_data
.n_operands
; --op_no
>= 0; )
1263 matchp
->with
[op_no
] = matchp
->commutative
[op_no
] = -1;
1265 for (op_no
= 0; op_no
< recog_data
.n_operands
; op_no
++)
1271 p
= recog_data
.constraints
[op_no
];
1273 likely_spilled
[op_no
] = 0;
1274 matchp
->use
[op_no
] = READ
;
1275 matchp
->early_clobber
[op_no
] = 0;
1277 matchp
->use
[op_no
] = WRITE
;
1279 matchp
->use
[op_no
] = READWRITE
;
1281 for (;*p
&& i
< which_alternative
; p
++)
1285 while ((c
= *p
) != '\0' && c
!= ',')
1294 matchp
->early_clobber
[op_no
] = 1;
1297 matchp
->commutative
[op_no
] = op_no
+ 1;
1298 matchp
->commutative
[op_no
+ 1] = op_no
;
1301 case '0': case '1': case '2': case '3': case '4':
1302 case '5': case '6': case '7': case '8': case '9':
1305 unsigned long match_ul
= strtoul (p
, &end
, 10);
1306 int match
= match_ul
;
1310 if (match
< op_no
&& likely_spilled
[match
])
1312 matchp
->with
[op_no
] = match
;
1314 if (matchp
->commutative
[op_no
] >= 0)
1315 matchp
->with
[matchp
->commutative
[op_no
]] = match
;
1319 case 'a': case 'b': case 'c': case 'd': case 'e': case 'f': case 'h':
1320 case 'j': case 'k': case 'l': case 'p': case 'q': case 't': case 'u':
1321 case 'v': case 'w': case 'x': case 'y': case 'z': case 'A': case 'B':
1322 case 'C': case 'D': case 'W': case 'Y': case 'Z':
1323 if (CLASS_LIKELY_SPILLED_P (REG_CLASS_FROM_CONSTRAINT ((unsigned char) c
, p
) ))
1324 likely_spilled
[op_no
] = 1;
1327 p
+= CONSTRAINT_LEN (c
, p
);
1336 gate_handle_regmove (void)
1338 return (optimize
> 0 && flag_regmove
);
1342 struct rtl_opt_pass pass_regmove
=
1346 "regmove", /* name */
1347 gate_handle_regmove
, /* gate */
1348 regmove_optimize
, /* execute */
1351 0, /* static_pass_number */
1352 TV_REGMOVE
, /* tv_id */
1353 0, /* properties_required */
1354 0, /* properties_provided */
1355 0, /* properties_destroyed */
1356 0, /* todo_flags_start */
1357 TODO_df_finish
| TODO_verify_rtl_sharing
|
1359 TODO_ggc_collect
/* todo_flags_finish */