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
);
54 int with
[MAX_RECOG_OPERANDS
];
55 enum { READ
, WRITE
, READWRITE
} use
[MAX_RECOG_OPERANDS
];
56 int commutative
[MAX_RECOG_OPERANDS
];
57 int early_clobber
[MAX_RECOG_OPERANDS
];
60 static int find_matches (rtx
, struct match
*);
61 static int fixup_match_2 (rtx
, rtx
, rtx
, rtx
);
63 /* Return nonzero if registers with CLASS1 and CLASS2 can be merged without
64 causing too much register allocation problems. */
66 regclass_compatible_p (enum reg_class class0
, enum reg_class class1
)
68 return (class0
== class1
69 || (reg_class_subset_p (class0
, class1
)
70 && ! CLASS_LIKELY_SPILLED_P (class0
))
71 || (reg_class_subset_p (class1
, class0
)
72 && ! CLASS_LIKELY_SPILLED_P (class1
)));
78 /* Find the place in the rtx X where REG is used as a memory address.
79 Return the MEM rtx that so uses it.
80 If PLUSCONST is nonzero, search instead for a memory address equivalent to
81 (plus REG (const_int PLUSCONST)).
83 If such an address does not appear, return 0.
84 If REG appears more than once, or is used other than in such an address,
88 find_use_as_address (rtx x
, rtx reg
, HOST_WIDE_INT plusconst
)
90 enum rtx_code code
= GET_CODE (x
);
91 const char * const fmt
= GET_RTX_FORMAT (code
);
96 if (code
== MEM
&& XEXP (x
, 0) == reg
&& plusconst
== 0)
99 if (code
== MEM
&& GET_CODE (XEXP (x
, 0)) == PLUS
100 && XEXP (XEXP (x
, 0), 0) == reg
101 && GET_CODE (XEXP (XEXP (x
, 0), 1)) == CONST_INT
102 && INTVAL (XEXP (XEXP (x
, 0), 1)) == plusconst
)
105 if (code
== SIGN_EXTRACT
|| code
== ZERO_EXTRACT
)
107 /* If REG occurs inside a MEM used in a bit-field reference,
108 that is unacceptable. */
109 if (find_use_as_address (XEXP (x
, 0), reg
, 0) != 0)
110 return (rtx
) (size_t) 1;
114 return (rtx
) (size_t) 1;
116 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
120 tem
= find_use_as_address (XEXP (x
, i
), reg
, plusconst
);
124 return (rtx
) (size_t) 1;
126 else if (fmt
[i
] == 'E')
129 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
131 tem
= find_use_as_address (XVECEXP (x
, i
, j
), reg
, plusconst
);
135 return (rtx
) (size_t) 1;
144 /* INC_INSN is an instruction that adds INCREMENT to REG.
145 Try to fold INC_INSN as a post/pre in/decrement into INSN.
146 Iff INC_INSN_SET is nonzero, inc_insn has a destination different from src.
147 Return nonzero for success. */
149 try_auto_increment (rtx insn
, rtx inc_insn
, rtx inc_insn_set
, rtx reg
,
150 HOST_WIDE_INT increment
, int pre
)
152 enum rtx_code inc_code
;
154 rtx pset
= single_set (insn
);
157 /* Can't use the size of SET_SRC, we might have something like
158 (sign_extend:SI (mem:QI ... */
159 rtx use
= find_use_as_address (pset
, reg
, 0);
160 if (use
!= 0 && use
!= (rtx
) (size_t) 1)
162 int size
= GET_MODE_SIZE (GET_MODE (use
));
164 || (HAVE_POST_INCREMENT
165 && pre
== 0 && (inc_code
= POST_INC
, increment
== size
))
166 || (HAVE_PRE_INCREMENT
167 && pre
== 1 && (inc_code
= PRE_INC
, increment
== size
))
168 || (HAVE_POST_DECREMENT
169 && pre
== 0 && (inc_code
= POST_DEC
, increment
== -size
))
170 || (HAVE_PRE_DECREMENT
171 && pre
== 1 && (inc_code
= PRE_DEC
, increment
== -size
))
177 &SET_SRC (inc_insn_set
),
178 XEXP (SET_SRC (inc_insn_set
), 0), 1);
179 validate_change (insn
, &XEXP (use
, 0),
180 gen_rtx_fmt_e (inc_code
, Pmode
, reg
), 1);
181 if (apply_change_group ())
183 /* If there is a REG_DEAD note on this insn, we must
184 change this not to REG_UNUSED meaning that the register
185 is set, but the value is dead. Failure to do so will
186 result in sched1 dying -- when it recomputes lifetime
187 information, the number of REG_DEAD notes will have
189 rtx note
= find_reg_note (insn
, REG_DEAD
, reg
);
191 PUT_MODE (note
, REG_UNUSED
);
193 add_reg_note (insn
, REG_INC
, reg
);
196 delete_insn (inc_insn
);
207 static int *regno_src_regno
;
209 /* INSN is a copy from SRC to DEST, both registers, and SRC does not die
212 Search forward to see if SRC dies before either it or DEST is modified,
213 but don't scan past the end of a basic block. If so, we can replace SRC
214 with DEST and let SRC die in INSN.
216 This will reduce the number of registers live in that range and may enable
217 DEST to be tied to SRC, thus often saving one register in addition to a
218 register-register copy. */
221 optimize_reg_copy_1 (rtx insn
, rtx dest
, rtx src
)
226 int sregno
= REGNO (src
);
227 int dregno
= REGNO (dest
);
228 basic_block bb
= BLOCK_FOR_INSN (insn
);
230 /* We don't want to mess with hard regs if register classes are small. */
232 || (SMALL_REGISTER_CLASSES
233 && (sregno
< FIRST_PSEUDO_REGISTER
234 || dregno
< FIRST_PSEUDO_REGISTER
))
235 /* We don't see all updates to SP if they are in an auto-inc memory
236 reference, so we must disallow this optimization on them. */
237 || sregno
== STACK_POINTER_REGNUM
|| dregno
== STACK_POINTER_REGNUM
)
240 for (p
= NEXT_INSN (insn
); p
; p
= NEXT_INSN (p
))
244 if (BLOCK_FOR_INSN (p
) != bb
)
247 if (reg_set_p (src
, p
) || reg_set_p (dest
, p
)
248 /* If SRC is an asm-declared register, it must not be replaced
249 in any asm. Unfortunately, the REG_EXPR tree for the asm
250 variable may be absent in the SRC rtx, so we can't check the
251 actual register declaration easily (the asm operand will have
252 it, though). To avoid complicating the test for a rare case,
253 we just don't perform register replacement for a hard reg
254 mentioned in an asm. */
255 || (sregno
< FIRST_PSEUDO_REGISTER
256 && asm_noperands (PATTERN (p
)) >= 0
257 && reg_overlap_mentioned_p (src
, PATTERN (p
)))
258 /* Don't change hard registers used by a call. */
259 || (CALL_P (p
) && sregno
< FIRST_PSEUDO_REGISTER
260 && find_reg_fusage (p
, USE
, src
))
261 /* Don't change a USE of a register. */
262 || (GET_CODE (PATTERN (p
)) == USE
263 && reg_overlap_mentioned_p (src
, XEXP (PATTERN (p
), 0))))
266 /* See if all of SRC dies in P. This test is slightly more
267 conservative than it needs to be. */
268 if ((note
= find_regno_note (p
, REG_DEAD
, sregno
)) != 0
269 && GET_MODE (XEXP (note
, 0)) == GET_MODE (src
))
276 int s_freq_calls
= 0;
277 int d_freq_calls
= 0;
279 /* We can do the optimization. Scan forward from INSN again,
280 replacing regs as we go. Set FAILED if a replacement can't
281 be done. In that case, we can't move the death note for SRC.
282 This should be rare. */
284 /* Set to stop at next insn. */
285 for (q
= next_real_insn (insn
);
286 q
!= next_real_insn (p
);
287 q
= next_real_insn (q
))
289 if (reg_overlap_mentioned_p (src
, PATTERN (q
)))
291 /* If SRC is a hard register, we might miss some
292 overlapping registers with validate_replace_rtx,
293 so we would have to undo it. We can't if DEST is
294 present in the insn, so fail in that combination
296 if (sregno
< FIRST_PSEUDO_REGISTER
297 && reg_mentioned_p (dest
, PATTERN (q
)))
300 /* Attempt to replace all uses. */
301 else if (!validate_replace_rtx (src
, dest
, q
))
304 /* If this succeeded, but some part of the register
305 is still present, undo the replacement. */
306 else if (sregno
< FIRST_PSEUDO_REGISTER
307 && reg_overlap_mentioned_p (src
, PATTERN (q
)))
309 validate_replace_rtx (dest
, src
, q
);
314 /* For SREGNO, count the total number of insns scanned.
315 For DREGNO, count the total number of insns scanned after
316 passing the death note for DREGNO. */
321 /* If the insn in which SRC dies is a CALL_INSN, don't count it
322 as a call that has been crossed. Otherwise, count it. */
323 if (q
!= p
&& CALL_P (q
))
325 /* Similarly, total calls for SREGNO, total calls beyond
326 the death note for DREGNO. */
328 s_freq_calls
+= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (q
));
332 d_freq_calls
+= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (q
));
336 /* If DEST dies here, remove the death note and save it for
337 later. Make sure ALL of DEST dies here; again, this is
338 overly conservative. */
340 && (dest_death
= find_regno_note (q
, REG_DEAD
, dregno
)) != 0)
342 if (GET_MODE (XEXP (dest_death
, 0)) != GET_MODE (dest
))
343 failed
= 1, dest_death
= 0;
345 remove_note (q
, dest_death
);
351 /* These counters need to be updated if and only if we are
352 going to move the REG_DEAD note. */
353 if (sregno
>= FIRST_PSEUDO_REGISTER
)
355 if (REG_LIVE_LENGTH (sregno
) >= 0)
357 REG_LIVE_LENGTH (sregno
) -= s_length
;
358 /* REG_LIVE_LENGTH is only an approximation after
359 combine if sched is not run, so make sure that we
360 still have a reasonable value. */
361 if (REG_LIVE_LENGTH (sregno
) < 2)
362 REG_LIVE_LENGTH (sregno
) = 2;
365 REG_N_CALLS_CROSSED (sregno
) -= s_n_calls
;
366 REG_FREQ_CALLS_CROSSED (sregno
) -= s_freq_calls
;
369 /* Move death note of SRC from P to INSN. */
370 remove_note (p
, note
);
371 XEXP (note
, 1) = REG_NOTES (insn
);
372 REG_NOTES (insn
) = note
;
375 /* DEST is also dead if INSN has a REG_UNUSED note for DEST. */
377 && (dest_death
= find_regno_note (insn
, REG_UNUSED
, dregno
)))
379 PUT_REG_NOTE_KIND (dest_death
, REG_DEAD
);
380 remove_note (insn
, dest_death
);
383 /* Put death note of DEST on P if we saw it die. */
386 XEXP (dest_death
, 1) = REG_NOTES (p
);
387 REG_NOTES (p
) = dest_death
;
389 if (dregno
>= FIRST_PSEUDO_REGISTER
)
391 /* If and only if we are moving the death note for DREGNO,
392 then we need to update its counters. */
393 if (REG_LIVE_LENGTH (dregno
) >= 0)
394 REG_LIVE_LENGTH (dregno
) += d_length
;
395 REG_N_CALLS_CROSSED (dregno
) += d_n_calls
;
396 REG_FREQ_CALLS_CROSSED (dregno
) += d_freq_calls
;
403 /* If SRC is a hard register which is set or killed in some other
404 way, we can't do this optimization. */
405 else if (sregno
< FIRST_PSEUDO_REGISTER
406 && dead_or_set_p (p
, src
))
412 /* INSN is a copy of SRC to DEST, in which SRC dies. See if we now have
413 a sequence of insns that modify DEST followed by an insn that sets
414 SRC to DEST in which DEST dies, with no prior modification of DEST.
415 (There is no need to check if the insns in between actually modify
416 DEST. We should not have cases where DEST is not modified, but
417 the optimization is safe if no such modification is detected.)
418 In that case, we can replace all uses of DEST, starting with INSN and
419 ending with the set of SRC to DEST, with SRC. We do not do this
420 optimization if a CALL_INSN is crossed unless SRC already crosses a
421 call or if DEST dies before the copy back to SRC.
423 It is assumed that DEST and SRC are pseudos; it is too complicated to do
424 this for hard registers since the substitutions we may make might fail. */
427 optimize_reg_copy_2 (rtx insn
, rtx dest
, rtx src
)
431 int sregno
= REGNO (src
);
432 int dregno
= REGNO (dest
);
433 basic_block bb
= BLOCK_FOR_INSN (insn
);
435 for (p
= NEXT_INSN (insn
); p
; p
= NEXT_INSN (p
))
439 if (BLOCK_FOR_INSN (p
) != bb
)
442 set
= single_set (p
);
443 if (set
&& SET_SRC (set
) == dest
&& SET_DEST (set
) == src
444 && find_reg_note (p
, REG_DEAD
, dest
))
446 /* We can do the optimization. Scan forward from INSN again,
447 replacing regs as we go. */
449 /* Set to stop at next insn. */
450 for (q
= insn
; q
!= NEXT_INSN (p
); q
= NEXT_INSN (q
))
453 if (reg_mentioned_p (dest
, PATTERN (q
)))
457 PATTERN (q
) = replace_rtx (PATTERN (q
), dest
, src
);
458 note
= FIND_REG_INC_NOTE (q
, dest
);
461 remove_note (q
, note
);
462 add_reg_note (q
, REG_INC
, src
);
469 int freq
= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (q
));
470 REG_N_CALLS_CROSSED (dregno
)--;
471 REG_N_CALLS_CROSSED (sregno
)++;
472 REG_FREQ_CALLS_CROSSED (dregno
) -= freq
;
473 REG_FREQ_CALLS_CROSSED (sregno
) += freq
;
477 remove_note (p
, find_reg_note (p
, REG_DEAD
, dest
));
478 REG_N_DEATHS (dregno
)--;
479 remove_note (insn
, find_reg_note (insn
, REG_DEAD
, src
));
480 REG_N_DEATHS (sregno
)--;
484 if (reg_set_p (src
, p
)
485 || find_reg_note (p
, REG_DEAD
, dest
)
486 || (CALL_P (p
) && REG_N_CALLS_CROSSED (sregno
) == 0))
491 /* INSN is a ZERO_EXTEND or SIGN_EXTEND of SRC to DEST.
492 Look if SRC dies there, and if it is only set once, by loading
493 it from memory. If so, try to incorporate the zero/sign extension
494 into the memory read, change SRC to the mode of DEST, and alter
495 the remaining accesses to use the appropriate SUBREG. This allows
496 SRC and DEST to be tied later. */
498 optimize_reg_copy_3 (rtx insn
, rtx dest
, rtx src
)
500 rtx src_reg
= XEXP (src
, 0);
501 int src_no
= REGNO (src_reg
);
502 int dst_no
= REGNO (dest
);
504 enum machine_mode old_mode
;
505 basic_block bb
= BLOCK_FOR_INSN (insn
);
507 if (src_no
< FIRST_PSEUDO_REGISTER
508 || dst_no
< FIRST_PSEUDO_REGISTER
509 || ! find_reg_note (insn
, REG_DEAD
, src_reg
)
510 || REG_N_DEATHS (src_no
) != 1
511 || REG_N_SETS (src_no
) != 1)
514 for (p
= PREV_INSN (insn
); p
&& ! reg_set_p (src_reg
, p
); p
= PREV_INSN (p
))
515 if (INSN_P (p
) && BLOCK_FOR_INSN (p
) != bb
)
518 if (! p
|| BLOCK_FOR_INSN (p
) != bb
)
521 if (! (set
= single_set (p
))
522 || !MEM_P (SET_SRC (set
))
523 /* If there's a REG_EQUIV note, this must be an insn that loads an
524 argument. Prefer keeping the note over doing this optimization. */
525 || find_reg_note (p
, REG_EQUIV
, NULL_RTX
)
526 || SET_DEST (set
) != src_reg
)
529 /* Be conservative: although this optimization is also valid for
530 volatile memory references, that could cause trouble in later passes. */
531 if (MEM_VOLATILE_P (SET_SRC (set
)))
534 /* Do not use a SUBREG to truncate from one mode to another if truncation
536 if (GET_MODE_BITSIZE (GET_MODE (src_reg
)) <= GET_MODE_BITSIZE (GET_MODE (src
))
537 && !TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (GET_MODE (src
)),
538 GET_MODE_BITSIZE (GET_MODE (src_reg
))))
541 old_mode
= GET_MODE (src_reg
);
542 PUT_MODE (src_reg
, GET_MODE (src
));
543 XEXP (src
, 0) = SET_SRC (set
);
545 /* Include this change in the group so that it's easily undone if
546 one of the changes in the group is invalid. */
547 validate_change (p
, &SET_SRC (set
), src
, 1);
549 /* Now walk forward making additional replacements. We want to be able
550 to undo all the changes if a later substitution fails. */
551 while (p
= NEXT_INSN (p
), p
!= insn
)
556 /* Make a tentative change. */
557 validate_replace_rtx_group (src_reg
,
558 gen_lowpart_SUBREG (old_mode
, src_reg
),
562 validate_replace_rtx_group (src
, src_reg
, insn
);
564 /* Now see if all the changes are valid. */
565 if (! apply_change_group ())
567 /* One or more changes were no good. Back out everything. */
568 PUT_MODE (src_reg
, old_mode
);
569 XEXP (src
, 0) = src_reg
;
573 rtx note
= find_reg_note (p
, REG_EQUAL
, NULL_RTX
);
575 remove_note (p
, note
);
580 /* If we were not able to update the users of src to use dest directly, try
581 instead moving the value to dest directly before the operation. */
584 copy_src_to_dest (rtx insn
, rtx src
, rtx dest
)
598 /* A REG_LIVE_LENGTH of -1 indicates the register is equivalent to a constant
599 or memory location and is used infrequently; a REG_LIVE_LENGTH of -2 is
600 parameter when there is no frame pointer that is not allocated a register.
601 For now, we just reject them, rather than incrementing the live length. */
604 && REG_LIVE_LENGTH (REGNO (src
)) > 0
606 && REG_LIVE_LENGTH (REGNO (dest
)) > 0
607 && (set
= single_set (insn
)) != NULL_RTX
608 && !reg_mentioned_p (dest
, SET_SRC (set
))
609 && GET_MODE (src
) == GET_MODE (dest
))
611 int old_num_regs
= reg_rtx_no
;
613 /* Generate the src->dest move. */
615 emit_move_insn (dest
, src
);
618 /* If this sequence uses new registers, we may not use it. */
619 if (old_num_regs
!= reg_rtx_no
620 || ! validate_replace_rtx (src
, dest
, insn
))
622 /* We have to restore reg_rtx_no to its old value, lest
623 recompute_reg_usage will try to compute the usage of the
624 new regs, yet reg_n_info is not valid for them. */
625 reg_rtx_no
= old_num_regs
;
628 emit_insn_before (seq
, insn
);
629 move_insn
= PREV_INSN (insn
);
630 p_move_notes
= ®_NOTES (move_insn
);
631 p_insn_notes
= ®_NOTES (insn
);
633 /* Move any notes mentioning src to the move instruction. */
634 for (link
= REG_NOTES (insn
); link
!= NULL_RTX
; link
= next
)
636 next
= XEXP (link
, 1);
637 if (XEXP (link
, 0) == src
)
639 *p_move_notes
= link
;
640 p_move_notes
= &XEXP (link
, 1);
644 *p_insn_notes
= link
;
645 p_insn_notes
= &XEXP (link
, 1);
649 *p_move_notes
= NULL_RTX
;
650 *p_insn_notes
= NULL_RTX
;
652 insn_uid
= INSN_UID (insn
);
653 move_uid
= INSN_UID (move_insn
);
655 /* Update the various register tables. */
656 dest_regno
= REGNO (dest
);
657 INC_REG_N_SETS (dest_regno
, 1);
658 REG_LIVE_LENGTH (dest_regno
)++;
659 src_regno
= REGNO (src
);
660 if (! find_reg_note (move_insn
, REG_DEAD
, src
))
661 REG_LIVE_LENGTH (src_regno
)++;
665 /* reg_set_in_bb[REGNO] points to basic block iff the register is set
666 only once in the given block and has REG_EQUAL note. */
668 static basic_block
*reg_set_in_bb
;
670 /* Size of reg_set_in_bb array. */
671 static unsigned int max_reg_computed
;
674 /* Return whether REG is set in only one location, and is set to a
675 constant, but is set in a different basic block from INSN (an
676 instructions which uses REG). In this case REG is equivalent to a
677 constant, and we don't want to break that equivalence, because that
678 may increase register pressure and make reload harder. If REG is
679 set in the same basic block as INSN, we don't worry about it,
680 because we'll probably need a register anyhow (??? but what if REG
681 is used in a different basic block as well as this one?). */
684 reg_is_remote_constant_p (rtx reg
, rtx insn
)
692 max_reg_computed
= max
= max_reg_num ();
693 reg_set_in_bb
= XCNEWVEC (basic_block
, max
);
703 /* This is the instruction which sets REG. If there is a
704 REG_EQUAL note, then REG is equivalent to a constant. */
706 && REG_P (SET_DEST (s
))
707 && REG_N_SETS (REGNO (SET_DEST (s
))) == 1
708 && find_reg_note (p
, REG_EQUAL
, NULL_RTX
))
709 reg_set_in_bb
[REGNO (SET_DEST (s
))] = bb
;
713 gcc_assert (REGNO (reg
) < max_reg_computed
);
714 if (reg_set_in_bb
[REGNO (reg
)] == NULL
)
716 return (reg_set_in_bb
[REGNO (reg
)] != BLOCK_FOR_INSN (insn
));
719 /* INSN is adding a CONST_INT to a REG. We search backwards looking for
720 another add immediate instruction with the same source and dest registers,
721 and if we find one, we change INSN to an increment, and return 1. If
722 no changes are made, we return 0.
725 (set (reg100) (plus reg1 offset1))
727 (set (reg100) (plus reg1 offset2))
729 (set (reg100) (plus reg1 offset1))
731 (set (reg100) (plus reg100 offset2-offset1)) */
733 /* ??? What does this comment mean? */
734 /* cse disrupts preincrement / postdecrement sequences when it finds a
735 hard register as ultimate source, like the frame pointer. */
738 fixup_match_2 (rtx insn
, rtx dst
, rtx src
, rtx offset
)
740 rtx p
, dst_death
= 0;
741 int length
, num_calls
= 0, freq_calls
= 0;
742 basic_block bb
= BLOCK_FOR_INSN (insn
);
744 /* If SRC dies in INSN, we'd have to move the death note. This is
745 considered to be very unlikely, so we just skip the optimization
747 if (find_regno_note (insn
, REG_DEAD
, REGNO (src
)))
750 /* Scan backward to find the first instruction that sets DST. */
752 for (length
= 0, p
= PREV_INSN (insn
); p
; p
= PREV_INSN (p
))
758 if (BLOCK_FOR_INSN (p
) != bb
)
761 if (find_regno_note (p
, REG_DEAD
, REGNO (dst
)))
766 pset
= single_set (p
);
767 if (pset
&& SET_DEST (pset
) == dst
768 && GET_CODE (SET_SRC (pset
)) == PLUS
769 && XEXP (SET_SRC (pset
), 0) == src
770 && GET_CODE (XEXP (SET_SRC (pset
), 1)) == CONST_INT
)
772 HOST_WIDE_INT newconst
773 = INTVAL (offset
) - INTVAL (XEXP (SET_SRC (pset
), 1));
774 rtx add
= gen_add3_insn (dst
, dst
, GEN_INT (newconst
));
776 if (add
&& validate_change (insn
, &PATTERN (insn
), add
, 0))
778 /* Remove the death note for DST from DST_DEATH. */
781 remove_death (REGNO (dst
), dst_death
);
782 REG_LIVE_LENGTH (REGNO (dst
)) += length
;
783 REG_N_CALLS_CROSSED (REGNO (dst
)) += num_calls
;
784 REG_FREQ_CALLS_CROSSED (REGNO (dst
)) += freq_calls
;
789 "Fixed operand of insn %d.\n",
793 for (p
= PREV_INSN (insn
); p
; p
= PREV_INSN (p
))
797 if (BLOCK_FOR_INSN (p
) != bb
)
799 if (reg_overlap_mentioned_p (dst
, PATTERN (p
)))
801 if (try_auto_increment (p
, insn
, 0, dst
, newconst
, 0))
806 for (p
= NEXT_INSN (insn
); p
; p
= NEXT_INSN (p
))
810 if (BLOCK_FOR_INSN (p
) != bb
)
812 if (reg_overlap_mentioned_p (dst
, PATTERN (p
)))
814 try_auto_increment (p
, insn
, 0, dst
, newconst
, 1);
823 if (reg_set_p (dst
, PATTERN (p
)))
826 /* If we have passed a call instruction, and the
827 pseudo-reg SRC is not already live across a call,
828 then don't perform the optimization. */
829 /* reg_set_p is overly conservative for CALL_INSNS, thinks that all
830 hard regs are clobbered. Thus, we only use it for src for
837 freq_calls
+= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (p
));
840 if (REG_N_CALLS_CROSSED (REGNO (src
)) == 0)
843 if (call_used_regs
[REGNO (dst
)]
844 || find_reg_fusage (p
, CLOBBER
, dst
))
847 else if (reg_set_p (src
, PATTERN (p
)))
854 /* A forward pass. Replace output operands with input operands. */
857 regmove_forward_pass (void)
862 if (! flag_expensive_optimizations
)
866 fprintf (dump_file
, "Starting forward pass...\n");
870 FOR_BB_INSNS (bb
, insn
)
872 rtx set
= single_set (insn
);
876 if ((GET_CODE (SET_SRC (set
)) == SIGN_EXTEND
877 || GET_CODE (SET_SRC (set
)) == ZERO_EXTEND
)
878 && REG_P (XEXP (SET_SRC (set
), 0))
879 && REG_P (SET_DEST (set
)))
880 optimize_reg_copy_3 (insn
, SET_DEST (set
), SET_SRC (set
));
882 if (REG_P (SET_SRC (set
))
883 && REG_P (SET_DEST (set
)))
885 /* If this is a register-register copy where SRC is not dead,
886 see if we can optimize it. If this optimization succeeds,
887 it will become a copy where SRC is dead. */
888 if ((find_reg_note (insn
, REG_DEAD
, SET_SRC (set
))
889 || optimize_reg_copy_1 (insn
, SET_DEST (set
), SET_SRC (set
)))
890 && REGNO (SET_DEST (set
)) >= FIRST_PSEUDO_REGISTER
)
892 /* Similarly for a pseudo-pseudo copy when SRC is dead. */
893 if (REGNO (SET_SRC (set
)) >= FIRST_PSEUDO_REGISTER
)
894 optimize_reg_copy_2 (insn
, SET_DEST (set
), SET_SRC (set
));
895 if (regno_src_regno
[REGNO (SET_DEST (set
))] < 0
896 && SET_SRC (set
) != SET_DEST (set
))
898 int srcregno
= REGNO (SET_SRC (set
));
899 if (regno_src_regno
[srcregno
] >= 0)
900 srcregno
= regno_src_regno
[srcregno
];
901 regno_src_regno
[REGNO (SET_DEST (set
))] = srcregno
;
909 /* A backward pass. Replace input operands with output operands. */
912 regmove_backward_pass (void)
918 fprintf (dump_file
, "Starting backward pass...\n");
920 FOR_EACH_BB_REVERSE (bb
)
922 /* ??? Use the safe iterator because fixup_match_2 can remove
923 insns via try_auto_increment. */
924 FOR_BB_INSNS_REVERSE_SAFE (bb
, insn
, prev
)
927 rtx copy_src
, copy_dst
;
934 if (! find_matches (insn
, &match
))
937 /* Now scan through the operands looking for a destination operand
938 which is supposed to match a source operand.
939 Then scan backward for an instruction which sets the source
940 operand. If safe, then replace the source operand with the
941 dest operand in both instructions. */
945 for (op_no
= 0; op_no
< recog_data
.n_operands
; op_no
++)
947 rtx set
, p
, src
, dst
;
948 rtx src_note
, dst_note
;
949 int num_calls
= 0, freq_calls
= 0;
950 enum reg_class src_class
, dst_class
;
953 match_no
= match
.with
[op_no
];
955 /* Nothing to do if the two operands aren't supposed to match. */
959 dst
= recog_data
.operand
[match_no
];
960 src
= recog_data
.operand
[op_no
];
966 || REGNO (dst
) < FIRST_PSEUDO_REGISTER
967 || REG_LIVE_LENGTH (REGNO (dst
)) < 0
968 || GET_MODE (src
) != GET_MODE (dst
))
971 /* If the operands already match, then there is nothing to do. */
972 if (operands_match_p (src
, dst
))
975 if (match
.commutative
[op_no
] >= 0)
977 rtx comm
= recog_data
.operand
[match
.commutative
[op_no
]];
978 if (operands_match_p (comm
, dst
))
982 set
= single_set (insn
);
986 /* Note that single_set ignores parts of a parallel set for
987 which one of the destinations is REG_UNUSED. We can't
988 handle that here, since we can wind up rewriting things
989 such that a single register is set twice within a single
991 if (reg_set_p (src
, insn
))
994 /* match_no/dst must be a write-only operand, and
995 operand_operand/src must be a read-only operand. */
996 if (match
.use
[op_no
] != READ
997 || match
.use
[match_no
] != WRITE
)
1000 if (match
.early_clobber
[match_no
]
1001 && count_occurrences (PATTERN (insn
), src
, 0) > 1)
1004 /* Make sure match_no is the destination. */
1005 if (recog_data
.operand
[match_no
] != SET_DEST (set
))
1008 if (REGNO (src
) < FIRST_PSEUDO_REGISTER
)
1010 if (GET_CODE (SET_SRC (set
)) == PLUS
1011 && GET_CODE (XEXP (SET_SRC (set
), 1)) == CONST_INT
1012 && XEXP (SET_SRC (set
), 0) == src
1013 && fixup_match_2 (insn
, dst
, src
,
1014 XEXP (SET_SRC (set
), 1)))
1018 src_class
= reg_preferred_class (REGNO (src
));
1019 dst_class
= reg_preferred_class (REGNO (dst
));
1021 if (! (src_note
= find_reg_note (insn
, REG_DEAD
, src
)))
1023 /* We used to force the copy here like in other cases, but
1024 it produces worse code, as it eliminates no copy
1025 instructions and the copy emitted will be produced by
1026 reload anyway. On patterns with multiple alternatives,
1027 there may be better solution available.
1029 In particular this change produced slower code for numeric
1035 if (! regclass_compatible_p (src_class
, dst_class
))
1045 /* Can not modify an earlier insn to set dst if this insn
1046 uses an old value in the source. */
1047 if (reg_overlap_mentioned_p (dst
, SET_SRC (set
)))
1057 /* If src is set once in a different basic block,
1058 and is set equal to a constant, then do not use
1059 it for this optimization, as this would make it
1060 no longer equivalent to a constant. */
1062 if (reg_is_remote_constant_p (src
, insn
))
1075 "Could fix operand %d of insn %d matching operand %d.\n",
1076 op_no
, INSN_UID (insn
), match_no
);
1078 /* Scan backward to find the first instruction that uses
1079 the input operand. If the operand is set here, then
1080 replace it in both instructions with match_no. */
1082 for (length
= 0, p
= PREV_INSN (insn
); p
; p
= PREV_INSN (p
))
1088 if (BLOCK_FOR_INSN (p
) != bb
)
1093 /* ??? See if all of SRC is set in P. This test is much
1094 more conservative than it needs to be. */
1095 pset
= single_set (p
);
1096 if (pset
&& SET_DEST (pset
) == src
)
1098 /* We use validate_replace_rtx, in case there
1099 are multiple identical source operands. All of
1100 them have to be changed at the same time. */
1101 if (validate_replace_rtx (src
, dst
, insn
))
1103 if (validate_change (p
, &SET_DEST (pset
),
1108 /* Change all source operands back.
1109 This modifies the dst as a side-effect. */
1110 validate_replace_rtx (dst
, src
, insn
);
1111 /* Now make sure the dst is right. */
1112 validate_change (insn
,
1113 recog_data
.operand_loc
[match_no
],
1120 /* We can't make this change if SRC is read or
1121 partially written in P, since we are going to
1122 eliminate SRC. We can't make this change
1123 if DST is mentioned at all in P,
1124 since we are going to change its value. */
1125 if (reg_overlap_mentioned_p (src
, PATTERN (p
))
1126 || reg_mentioned_p (dst
, PATTERN (p
)))
1129 /* If we have passed a call instruction, and the
1130 pseudo-reg DST is not already live across a call,
1131 then don't perform the optimization. */
1135 freq_calls
+= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (p
));
1137 if (REG_N_CALLS_CROSSED (REGNO (dst
)) == 0)
1146 /* Remove the death note for SRC from INSN. */
1147 remove_note (insn
, src_note
);
1148 /* Move the death note for SRC to P if it is used
1150 if (reg_overlap_mentioned_p (src
, PATTERN (p
)))
1152 XEXP (src_note
, 1) = REG_NOTES (p
);
1153 REG_NOTES (p
) = src_note
;
1155 /* If there is a REG_DEAD note for DST on P, then remove
1156 it, because DST is now set there. */
1157 if ((dst_note
= find_reg_note (p
, REG_DEAD
, dst
)))
1158 remove_note (p
, dst_note
);
1160 dstno
= REGNO (dst
);
1161 srcno
= REGNO (src
);
1163 INC_REG_N_SETS (dstno
, 1);
1164 INC_REG_N_SETS (srcno
, -1);
1166 REG_N_CALLS_CROSSED (dstno
) += num_calls
;
1167 REG_N_CALLS_CROSSED (srcno
) -= num_calls
;
1168 REG_FREQ_CALLS_CROSSED (dstno
) += freq_calls
;
1169 REG_FREQ_CALLS_CROSSED (srcno
) -= freq_calls
;
1171 REG_LIVE_LENGTH (dstno
) += length
;
1172 if (REG_LIVE_LENGTH (srcno
) >= 0)
1174 REG_LIVE_LENGTH (srcno
) -= length
;
1175 /* REG_LIVE_LENGTH is only an approximation after
1176 combine if sched is not run, so make sure that we
1177 still have a reasonable value. */
1178 if (REG_LIVE_LENGTH (srcno
) < 2)
1179 REG_LIVE_LENGTH (srcno
) = 2;
1184 "Fixed operand %d of insn %d matching operand %d.\n",
1185 op_no
, INSN_UID (insn
), match_no
);
1191 /* If we weren't able to replace any of the alternatives, try an
1192 alternative approach of copying the source to the destination. */
1193 if (!success
&& copy_src
!= NULL_RTX
)
1194 copy_src_to_dest (insn
, copy_src
, copy_dst
);
1199 /* Main entry for the register move optimization. */
1202 regmove_optimize (void)
1205 int nregs
= max_reg_num ();
1207 df_note_add_problem ();
1210 regstat_init_n_sets_and_refs ();
1211 regstat_compute_ri ();
1213 regno_src_regno
= XNEWVEC (int, nregs
);
1214 for (i
= nregs
; --i
>= 0; )
1215 regno_src_regno
[i
] = -1;
1217 /* A forward pass. Replace output operands with input operands. */
1218 regmove_forward_pass ();
1220 /* A backward pass. Replace input operands with output operands. */
1221 regmove_backward_pass ();
1224 free (regno_src_regno
);
1227 free (reg_set_in_bb
);
1228 reg_set_in_bb
= NULL
;
1230 regstat_free_n_sets_and_refs ();
1235 /* Returns nonzero if INSN's pattern has matching constraints for any operand.
1236 Returns 0 if INSN can't be recognized, or if the alternative can't be
1239 Initialize the info in MATCHP based on the constraints. */
1242 find_matches (rtx insn
, struct match
*matchp
)
1244 int likely_spilled
[MAX_RECOG_OPERANDS
];
1246 int any_matches
= 0;
1248 extract_insn (insn
);
1249 if (! constrain_operands (0))
1252 /* Must initialize this before main loop, because the code for
1253 the commutative case may set matches for operands other than
1255 for (op_no
= recog_data
.n_operands
; --op_no
>= 0; )
1256 matchp
->with
[op_no
] = matchp
->commutative
[op_no
] = -1;
1258 for (op_no
= 0; op_no
< recog_data
.n_operands
; op_no
++)
1264 p
= recog_data
.constraints
[op_no
];
1266 likely_spilled
[op_no
] = 0;
1267 matchp
->use
[op_no
] = READ
;
1268 matchp
->early_clobber
[op_no
] = 0;
1270 matchp
->use
[op_no
] = WRITE
;
1272 matchp
->use
[op_no
] = READWRITE
;
1274 for (;*p
&& i
< which_alternative
; p
++)
1278 while ((c
= *p
) != '\0' && c
!= ',')
1287 matchp
->early_clobber
[op_no
] = 1;
1290 matchp
->commutative
[op_no
] = op_no
+ 1;
1291 matchp
->commutative
[op_no
+ 1] = op_no
;
1294 case '0': case '1': case '2': case '3': case '4':
1295 case '5': case '6': case '7': case '8': case '9':
1298 unsigned long match_ul
= strtoul (p
, &end
, 10);
1299 int match
= match_ul
;
1303 if (match
< op_no
&& likely_spilled
[match
])
1305 matchp
->with
[op_no
] = match
;
1307 if (matchp
->commutative
[op_no
] >= 0)
1308 matchp
->with
[matchp
->commutative
[op_no
]] = match
;
1312 case 'a': case 'b': case 'c': case 'd': case 'e': case 'f': case 'h':
1313 case 'j': case 'k': case 'l': case 'p': case 'q': case 't': case 'u':
1314 case 'v': case 'w': case 'x': case 'y': case 'z': case 'A': case 'B':
1315 case 'C': case 'D': case 'W': case 'Y': case 'Z':
1316 if (CLASS_LIKELY_SPILLED_P (REG_CLASS_FROM_CONSTRAINT ((unsigned char) c
, p
) ))
1317 likely_spilled
[op_no
] = 1;
1320 p
+= CONSTRAINT_LEN (c
, p
);
1329 gate_handle_regmove (void)
1331 return (optimize
> 0 && flag_regmove
);
1335 struct rtl_opt_pass pass_regmove
=
1339 "regmove", /* name */
1340 gate_handle_regmove
, /* gate */
1341 regmove_optimize
, /* execute */
1344 0, /* static_pass_number */
1345 TV_REGMOVE
, /* tv_id */
1346 0, /* properties_required */
1347 0, /* properties_provided */
1348 0, /* properties_destroyed */
1349 0, /* todo_flags_start */
1350 TODO_df_finish
| TODO_verify_rtl_sharing
|
1352 TODO_ggc_collect
/* todo_flags_finish */