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 perhaps_ends_bb_p (rtx
);
49 static int optimize_reg_copy_1 (rtx
, rtx
, rtx
);
50 static void optimize_reg_copy_2 (rtx
, rtx
, rtx
);
51 static void optimize_reg_copy_3 (rtx
, rtx
, rtx
);
52 static void copy_src_to_dest (rtx
, rtx
, rtx
);
55 int with
[MAX_RECOG_OPERANDS
];
56 enum { READ
, WRITE
, READWRITE
} use
[MAX_RECOG_OPERANDS
];
57 int commutative
[MAX_RECOG_OPERANDS
];
58 int early_clobber
[MAX_RECOG_OPERANDS
];
61 static int find_matches (rtx
, struct match
*);
62 static int regclass_compatible_p (int, int);
63 static int fixup_match_2 (rtx
, rtx
, rtx
, rtx
);
65 /* Return nonzero if registers with CLASS1 and CLASS2 can be merged without
66 causing too much register allocation problems. */
68 regclass_compatible_p (int class0
, int class1
)
70 return (class0
== class1
71 || (reg_class_subset_p (class0
, class1
)
72 && ! CLASS_LIKELY_SPILLED_P (class0
))
73 || (reg_class_subset_p (class1
, class0
)
74 && ! CLASS_LIKELY_SPILLED_P (class1
)));
80 /* Find the place in the rtx X where REG is used as a memory address.
81 Return the MEM rtx that so uses it.
82 If PLUSCONST is nonzero, search instead for a memory address equivalent to
83 (plus REG (const_int PLUSCONST)).
85 If such an address does not appear, return 0.
86 If REG appears more than once, or is used other than in such an address,
90 find_use_as_address (rtx x
, rtx reg
, HOST_WIDE_INT plusconst
)
92 enum rtx_code code
= GET_CODE (x
);
93 const char * const fmt
= GET_RTX_FORMAT (code
);
98 if (code
== MEM
&& XEXP (x
, 0) == reg
&& plusconst
== 0)
101 if (code
== MEM
&& GET_CODE (XEXP (x
, 0)) == PLUS
102 && XEXP (XEXP (x
, 0), 0) == reg
103 && GET_CODE (XEXP (XEXP (x
, 0), 1)) == CONST_INT
104 && INTVAL (XEXP (XEXP (x
, 0), 1)) == plusconst
)
107 if (code
== SIGN_EXTRACT
|| code
== ZERO_EXTRACT
)
109 /* If REG occurs inside a MEM used in a bit-field reference,
110 that is unacceptable. */
111 if (find_use_as_address (XEXP (x
, 0), reg
, 0) != 0)
112 return (rtx
) (size_t) 1;
116 return (rtx
) (size_t) 1;
118 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
122 tem
= find_use_as_address (XEXP (x
, i
), reg
, plusconst
);
126 return (rtx
) (size_t) 1;
128 else if (fmt
[i
] == 'E')
131 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
133 tem
= find_use_as_address (XVECEXP (x
, i
, j
), reg
, plusconst
);
137 return (rtx
) (size_t) 1;
146 /* INC_INSN is an instruction that adds INCREMENT to REG.
147 Try to fold INC_INSN as a post/pre in/decrement into INSN.
148 Iff INC_INSN_SET is nonzero, inc_insn has a destination different from src.
149 Return nonzero for success. */
151 try_auto_increment (rtx insn
, rtx inc_insn
, rtx inc_insn_set
, rtx reg
,
152 HOST_WIDE_INT increment
, int pre
)
154 enum rtx_code inc_code
;
156 rtx pset
= single_set (insn
);
159 /* Can't use the size of SET_SRC, we might have something like
160 (sign_extend:SI (mem:QI ... */
161 rtx use
= find_use_as_address (pset
, reg
, 0);
162 if (use
!= 0 && use
!= (rtx
) (size_t) 1)
164 int size
= GET_MODE_SIZE (GET_MODE (use
));
166 || (HAVE_POST_INCREMENT
167 && pre
== 0 && (inc_code
= POST_INC
, increment
== size
))
168 || (HAVE_PRE_INCREMENT
169 && pre
== 1 && (inc_code
= PRE_INC
, increment
== size
))
170 || (HAVE_POST_DECREMENT
171 && pre
== 0 && (inc_code
= POST_DEC
, increment
== -size
))
172 || (HAVE_PRE_DECREMENT
173 && pre
== 1 && (inc_code
= PRE_DEC
, increment
== -size
))
179 &SET_SRC (inc_insn_set
),
180 XEXP (SET_SRC (inc_insn_set
), 0), 1);
181 validate_change (insn
, &XEXP (use
, 0),
182 gen_rtx_fmt_e (inc_code
, Pmode
, reg
), 1);
183 if (apply_change_group ())
185 /* If there is a REG_DEAD note on this insn, we must
186 change this not to REG_UNUSED meaning that the register
187 is set, but the value is dead. Failure to do so will
188 result in sched1 dying -- when it recomputes lifetime
189 information, the number of REG_DEAD notes will have
191 rtx note
= find_reg_note (insn
, REG_DEAD
, reg
);
193 PUT_MODE (note
, REG_UNUSED
);
195 add_reg_note (insn
, REG_INC
, reg
);
198 delete_insn (inc_insn
);
209 static int *regno_src_regno
;
212 /* Return 1 if INSN might end a basic block. */
214 static int perhaps_ends_bb_p (rtx insn
)
216 switch (GET_CODE (insn
))
220 /* These always end a basic block. */
224 /* A CALL_INSN might be the last insn of a basic block, if it is inside
225 an EH region or if there are nonlocal gotos. Note that this test is
226 very conservative. */
227 if (nonlocal_goto_handler_labels
)
231 return can_throw_internal (insn
);
235 /* INSN is a copy from SRC to DEST, both registers, and SRC does not die
238 Search forward to see if SRC dies before either it or DEST is modified,
239 but don't scan past the end of a basic block. If so, we can replace SRC
240 with DEST and let SRC die in INSN.
242 This will reduce the number of registers live in that range and may enable
243 DEST to be tied to SRC, thus often saving one register in addition to a
244 register-register copy. */
247 optimize_reg_copy_1 (rtx insn
, rtx dest
, rtx src
)
252 int sregno
= REGNO (src
);
253 int dregno
= REGNO (dest
);
255 /* We don't want to mess with hard regs if register classes are small. */
257 || (SMALL_REGISTER_CLASSES
258 && (sregno
< FIRST_PSEUDO_REGISTER
259 || dregno
< FIRST_PSEUDO_REGISTER
))
260 /* We don't see all updates to SP if they are in an auto-inc memory
261 reference, so we must disallow this optimization on them. */
262 || sregno
== STACK_POINTER_REGNUM
|| dregno
== STACK_POINTER_REGNUM
)
265 for (p
= NEXT_INSN (insn
); p
; p
= NEXT_INSN (p
))
267 /* ??? We can't scan past the end of a basic block without updating
268 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
269 if (perhaps_ends_bb_p (p
))
271 else if (! INSN_P (p
))
274 if (reg_set_p (src
, p
) || reg_set_p (dest
, p
)
275 /* If SRC is an asm-declared register, it must not be replaced
276 in any asm. Unfortunately, the REG_EXPR tree for the asm
277 variable may be absent in the SRC rtx, so we can't check the
278 actual register declaration easily (the asm operand will have
279 it, though). To avoid complicating the test for a rare case,
280 we just don't perform register replacement for a hard reg
281 mentioned in an asm. */
282 || (sregno
< FIRST_PSEUDO_REGISTER
283 && asm_noperands (PATTERN (p
)) >= 0
284 && reg_overlap_mentioned_p (src
, PATTERN (p
)))
285 /* Don't change hard registers used by a call. */
286 || (CALL_P (p
) && sregno
< FIRST_PSEUDO_REGISTER
287 && find_reg_fusage (p
, USE
, src
))
288 /* Don't change a USE of a register. */
289 || (GET_CODE (PATTERN (p
)) == USE
290 && reg_overlap_mentioned_p (src
, XEXP (PATTERN (p
), 0))))
293 /* See if all of SRC dies in P. This test is slightly more
294 conservative than it needs to be. */
295 if ((note
= find_regno_note (p
, REG_DEAD
, sregno
)) != 0
296 && GET_MODE (XEXP (note
, 0)) == GET_MODE (src
))
303 int s_freq_calls
= 0;
304 int d_freq_calls
= 0;
306 /* We can do the optimization. Scan forward from INSN again,
307 replacing regs as we go. Set FAILED if a replacement can't
308 be done. In that case, we can't move the death note for SRC.
309 This should be rare. */
311 /* Set to stop at next insn. */
312 for (q
= next_real_insn (insn
);
313 q
!= next_real_insn (p
);
314 q
= next_real_insn (q
))
316 if (reg_overlap_mentioned_p (src
, PATTERN (q
)))
318 /* If SRC is a hard register, we might miss some
319 overlapping registers with validate_replace_rtx,
320 so we would have to undo it. We can't if DEST is
321 present in the insn, so fail in that combination
323 if (sregno
< FIRST_PSEUDO_REGISTER
324 && reg_mentioned_p (dest
, PATTERN (q
)))
327 /* Attempt to replace all uses. */
328 else if (!validate_replace_rtx (src
, dest
, q
))
331 /* If this succeeded, but some part of the register
332 is still present, undo the replacement. */
333 else if (sregno
< FIRST_PSEUDO_REGISTER
334 && reg_overlap_mentioned_p (src
, PATTERN (q
)))
336 validate_replace_rtx (dest
, src
, q
);
341 /* For SREGNO, count the total number of insns scanned.
342 For DREGNO, count the total number of insns scanned after
343 passing the death note for DREGNO. */
348 /* If the insn in which SRC dies is a CALL_INSN, don't count it
349 as a call that has been crossed. Otherwise, count it. */
350 if (q
!= p
&& CALL_P (q
))
352 /* Similarly, total calls for SREGNO, total calls beyond
353 the death note for DREGNO. */
355 s_freq_calls
+= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (q
));
359 d_freq_calls
+= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (q
));
363 /* If DEST dies here, remove the death note and save it for
364 later. Make sure ALL of DEST dies here; again, this is
365 overly conservative. */
367 && (dest_death
= find_regno_note (q
, REG_DEAD
, dregno
)) != 0)
369 if (GET_MODE (XEXP (dest_death
, 0)) != GET_MODE (dest
))
370 failed
= 1, dest_death
= 0;
372 remove_note (q
, dest_death
);
378 /* These counters need to be updated if and only if we are
379 going to move the REG_DEAD note. */
380 if (sregno
>= FIRST_PSEUDO_REGISTER
)
382 if (REG_LIVE_LENGTH (sregno
) >= 0)
384 REG_LIVE_LENGTH (sregno
) -= s_length
;
385 /* REG_LIVE_LENGTH is only an approximation after
386 combine if sched is not run, so make sure that we
387 still have a reasonable value. */
388 if (REG_LIVE_LENGTH (sregno
) < 2)
389 REG_LIVE_LENGTH (sregno
) = 2;
392 REG_N_CALLS_CROSSED (sregno
) -= s_n_calls
;
393 REG_FREQ_CALLS_CROSSED (sregno
) -= s_freq_calls
;
396 /* Move death note of SRC from P to INSN. */
397 remove_note (p
, note
);
398 XEXP (note
, 1) = REG_NOTES (insn
);
399 REG_NOTES (insn
) = note
;
402 /* DEST is also dead if INSN has a REG_UNUSED note for DEST. */
404 && (dest_death
= find_regno_note (insn
, REG_UNUSED
, dregno
)))
406 PUT_REG_NOTE_KIND (dest_death
, REG_DEAD
);
407 remove_note (insn
, dest_death
);
410 /* Put death note of DEST on P if we saw it die. */
413 XEXP (dest_death
, 1) = REG_NOTES (p
);
414 REG_NOTES (p
) = dest_death
;
416 if (dregno
>= FIRST_PSEUDO_REGISTER
)
418 /* If and only if we are moving the death note for DREGNO,
419 then we need to update its counters. */
420 if (REG_LIVE_LENGTH (dregno
) >= 0)
421 REG_LIVE_LENGTH (dregno
) += d_length
;
422 REG_N_CALLS_CROSSED (dregno
) += d_n_calls
;
423 REG_FREQ_CALLS_CROSSED (dregno
) += d_freq_calls
;
430 /* If SRC is a hard register which is set or killed in some other
431 way, we can't do this optimization. */
432 else if (sregno
< FIRST_PSEUDO_REGISTER
433 && dead_or_set_p (p
, src
))
439 /* INSN is a copy of SRC to DEST, in which SRC dies. See if we now have
440 a sequence of insns that modify DEST followed by an insn that sets
441 SRC to DEST in which DEST dies, with no prior modification of DEST.
442 (There is no need to check if the insns in between actually modify
443 DEST. We should not have cases where DEST is not modified, but
444 the optimization is safe if no such modification is detected.)
445 In that case, we can replace all uses of DEST, starting with INSN and
446 ending with the set of SRC to DEST, with SRC. We do not do this
447 optimization if a CALL_INSN is crossed unless SRC already crosses a
448 call or if DEST dies before the copy back to SRC.
450 It is assumed that DEST and SRC are pseudos; it is too complicated to do
451 this for hard registers since the substitutions we may make might fail. */
454 optimize_reg_copy_2 (rtx insn
, rtx dest
, rtx src
)
458 int sregno
= REGNO (src
);
459 int dregno
= REGNO (dest
);
461 for (p
= NEXT_INSN (insn
); p
; p
= NEXT_INSN (p
))
463 /* ??? We can't scan past the end of a basic block without updating
464 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
465 if (perhaps_ends_bb_p (p
))
467 else if (! INSN_P (p
))
470 set
= single_set (p
);
471 if (set
&& SET_SRC (set
) == dest
&& SET_DEST (set
) == src
472 && find_reg_note (p
, REG_DEAD
, dest
))
474 /* We can do the optimization. Scan forward from INSN again,
475 replacing regs as we go. */
477 /* Set to stop at next insn. */
478 for (q
= insn
; q
!= NEXT_INSN (p
); q
= NEXT_INSN (q
))
481 if (reg_mentioned_p (dest
, PATTERN (q
)))
485 PATTERN (q
) = replace_rtx (PATTERN (q
), dest
, src
);
486 note
= FIND_REG_INC_NOTE (q
, dest
);
489 remove_note (q
, note
);
490 add_reg_note (q
, REG_INC
, src
);
497 int freq
= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (q
));
498 REG_N_CALLS_CROSSED (dregno
)--;
499 REG_N_CALLS_CROSSED (sregno
)++;
500 REG_FREQ_CALLS_CROSSED (dregno
) -= freq
;
501 REG_FREQ_CALLS_CROSSED (sregno
) += freq
;
505 remove_note (p
, find_reg_note (p
, REG_DEAD
, dest
));
506 REG_N_DEATHS (dregno
)--;
507 remove_note (insn
, find_reg_note (insn
, REG_DEAD
, src
));
508 REG_N_DEATHS (sregno
)--;
512 if (reg_set_p (src
, p
)
513 || find_reg_note (p
, REG_DEAD
, dest
)
514 || (CALL_P (p
) && REG_N_CALLS_CROSSED (sregno
) == 0))
519 /* INSN is a ZERO_EXTEND or SIGN_EXTEND of SRC to DEST.
520 Look if SRC dies there, and if it is only set once, by loading
521 it from memory. If so, try to incorporate the zero/sign extension
522 into the memory read, change SRC to the mode of DEST, and alter
523 the remaining accesses to use the appropriate SUBREG. This allows
524 SRC and DEST to be tied later. */
526 optimize_reg_copy_3 (rtx insn
, rtx dest
, rtx src
)
528 rtx src_reg
= XEXP (src
, 0);
529 int src_no
= REGNO (src_reg
);
530 int dst_no
= REGNO (dest
);
532 enum machine_mode old_mode
;
534 if (src_no
< FIRST_PSEUDO_REGISTER
535 || dst_no
< FIRST_PSEUDO_REGISTER
536 || ! find_reg_note (insn
, REG_DEAD
, src_reg
)
537 || REG_N_DEATHS (src_no
) != 1
538 || REG_N_SETS (src_no
) != 1)
540 for (p
= PREV_INSN (insn
); p
&& ! reg_set_p (src_reg
, p
); p
= PREV_INSN (p
))
541 /* ??? We can't scan past the end of a basic block without updating
542 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
543 if (perhaps_ends_bb_p (p
))
549 if (! (set
= single_set (p
))
550 || !MEM_P (SET_SRC (set
))
551 /* If there's a REG_EQUIV note, this must be an insn that loads an
552 argument. Prefer keeping the note over doing this optimization. */
553 || find_reg_note (p
, REG_EQUIV
, NULL_RTX
)
554 || SET_DEST (set
) != src_reg
)
557 /* Be conservative: although this optimization is also valid for
558 volatile memory references, that could cause trouble in later passes. */
559 if (MEM_VOLATILE_P (SET_SRC (set
)))
562 /* Do not use a SUBREG to truncate from one mode to another if truncation
564 if (GET_MODE_BITSIZE (GET_MODE (src_reg
)) <= GET_MODE_BITSIZE (GET_MODE (src
))
565 && !TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (GET_MODE (src
)),
566 GET_MODE_BITSIZE (GET_MODE (src_reg
))))
569 old_mode
= GET_MODE (src_reg
);
570 PUT_MODE (src_reg
, GET_MODE (src
));
571 XEXP (src
, 0) = SET_SRC (set
);
573 /* Include this change in the group so that it's easily undone if
574 one of the changes in the group is invalid. */
575 validate_change (p
, &SET_SRC (set
), src
, 1);
577 /* Now walk forward making additional replacements. We want to be able
578 to undo all the changes if a later substitution fails. */
579 while (p
= NEXT_INSN (p
), p
!= insn
)
584 /* Make a tentative change. */
585 validate_replace_rtx_group (src_reg
,
586 gen_lowpart_SUBREG (old_mode
, src_reg
),
590 validate_replace_rtx_group (src
, src_reg
, insn
);
592 /* Now see if all the changes are valid. */
593 if (! apply_change_group ())
595 /* One or more changes were no good. Back out everything. */
596 PUT_MODE (src_reg
, old_mode
);
597 XEXP (src
, 0) = src_reg
;
601 rtx note
= find_reg_note (p
, REG_EQUAL
, NULL_RTX
);
603 remove_note (p
, note
);
608 /* If we were not able to update the users of src to use dest directly, try
609 instead moving the value to dest directly before the operation. */
612 copy_src_to_dest (rtx insn
, rtx src
, rtx dest
)
626 /* A REG_LIVE_LENGTH of -1 indicates the register is equivalent to a constant
627 or memory location and is used infrequently; a REG_LIVE_LENGTH of -2 is
628 parameter when there is no frame pointer that is not allocated a register.
629 For now, we just reject them, rather than incrementing the live length. */
632 && REG_LIVE_LENGTH (REGNO (src
)) > 0
634 && REG_LIVE_LENGTH (REGNO (dest
)) > 0
635 && (set
= single_set (insn
)) != NULL_RTX
636 && !reg_mentioned_p (dest
, SET_SRC (set
))
637 && GET_MODE (src
) == GET_MODE (dest
))
639 int old_num_regs
= reg_rtx_no
;
641 /* Generate the src->dest move. */
643 emit_move_insn (dest
, src
);
646 /* If this sequence uses new registers, we may not use it. */
647 if (old_num_regs
!= reg_rtx_no
648 || ! validate_replace_rtx (src
, dest
, insn
))
650 /* We have to restore reg_rtx_no to its old value, lest
651 recompute_reg_usage will try to compute the usage of the
652 new regs, yet reg_n_info is not valid for them. */
653 reg_rtx_no
= old_num_regs
;
656 emit_insn_before (seq
, insn
);
657 move_insn
= PREV_INSN (insn
);
658 p_move_notes
= ®_NOTES (move_insn
);
659 p_insn_notes
= ®_NOTES (insn
);
661 /* Move any notes mentioning src to the move instruction. */
662 for (link
= REG_NOTES (insn
); link
!= NULL_RTX
; link
= next
)
664 next
= XEXP (link
, 1);
665 if (XEXP (link
, 0) == src
)
667 *p_move_notes
= link
;
668 p_move_notes
= &XEXP (link
, 1);
672 *p_insn_notes
= link
;
673 p_insn_notes
= &XEXP (link
, 1);
677 *p_move_notes
= NULL_RTX
;
678 *p_insn_notes
= NULL_RTX
;
680 insn_uid
= INSN_UID (insn
);
681 move_uid
= INSN_UID (move_insn
);
683 /* Update the various register tables. */
684 dest_regno
= REGNO (dest
);
685 INC_REG_N_SETS (dest_regno
, 1);
686 REG_LIVE_LENGTH (dest_regno
)++;
687 src_regno
= REGNO (src
);
688 if (! find_reg_note (move_insn
, REG_DEAD
, src
))
689 REG_LIVE_LENGTH (src_regno
)++;
693 /* reg_set_in_bb[REGNO] points to basic block iff the register is set
694 only once in the given block and has REG_EQUAL note. */
696 static basic_block
*reg_set_in_bb
;
698 /* Size of reg_set_in_bb array. */
699 static unsigned int max_reg_computed
;
702 /* Return whether REG is set in only one location, and is set to a
703 constant, but is set in a different basic block from INSN (an
704 instructions which uses REG). In this case REG is equivalent to a
705 constant, and we don't want to break that equivalence, because that
706 may increase register pressure and make reload harder. If REG is
707 set in the same basic block as INSN, we don't worry about it,
708 because we'll probably need a register anyhow (??? but what if REG
709 is used in a different basic block as well as this one?). */
712 reg_is_remote_constant_p (rtx reg
, rtx insn
)
720 max_reg_computed
= max
= max_reg_num ();
721 reg_set_in_bb
= XCNEWVEC (basic_block
, max
);
731 /* This is the instruction which sets REG. If there is a
732 REG_EQUAL note, then REG is equivalent to a constant. */
734 && REG_P (SET_DEST (s
))
735 && REG_N_SETS (REGNO (SET_DEST (s
))) == 1
736 && find_reg_note (p
, REG_EQUAL
, NULL_RTX
))
737 reg_set_in_bb
[REGNO (SET_DEST (s
))] = bb
;
741 gcc_assert (REGNO (reg
) < max_reg_computed
);
742 if (reg_set_in_bb
[REGNO (reg
)] == NULL
)
744 return (reg_set_in_bb
[REGNO (reg
)] != BLOCK_FOR_INSN (insn
));
747 /* INSN is adding a CONST_INT to a REG. We search backwards looking for
748 another add immediate instruction with the same source and dest registers,
749 and if we find one, we change INSN to an increment, and return 1. If
750 no changes are made, we return 0.
753 (set (reg100) (plus reg1 offset1))
755 (set (reg100) (plus reg1 offset2))
757 (set (reg100) (plus reg1 offset1))
759 (set (reg100) (plus reg100 offset2-offset1)) */
761 /* ??? What does this comment mean? */
762 /* cse disrupts preincrement / postdecrement sequences when it finds a
763 hard register as ultimate source, like the frame pointer. */
766 fixup_match_2 (rtx insn
, rtx dst
, rtx src
, rtx offset
)
768 rtx p
, dst_death
= 0;
769 int length
, num_calls
= 0, freq_calls
= 0;
771 /* If SRC dies in INSN, we'd have to move the death note. This is
772 considered to be very unlikely, so we just skip the optimization
774 if (find_regno_note (insn
, REG_DEAD
, REGNO (src
)))
777 /* Scan backward to find the first instruction that sets DST. */
779 for (length
= 0, p
= PREV_INSN (insn
); p
; p
= PREV_INSN (p
))
783 /* ??? We can't scan past the end of a basic block without updating
784 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
785 if (perhaps_ends_bb_p (p
))
787 else if (! INSN_P (p
))
790 if (find_regno_note (p
, REG_DEAD
, REGNO (dst
)))
795 pset
= single_set (p
);
796 if (pset
&& SET_DEST (pset
) == dst
797 && GET_CODE (SET_SRC (pset
)) == PLUS
798 && XEXP (SET_SRC (pset
), 0) == src
799 && GET_CODE (XEXP (SET_SRC (pset
), 1)) == CONST_INT
)
801 HOST_WIDE_INT newconst
802 = INTVAL (offset
) - INTVAL (XEXP (SET_SRC (pset
), 1));
803 rtx add
= gen_add3_insn (dst
, dst
, GEN_INT (newconst
));
805 if (add
&& validate_change (insn
, &PATTERN (insn
), add
, 0))
807 /* Remove the death note for DST from DST_DEATH. */
810 remove_death (REGNO (dst
), dst_death
);
811 REG_LIVE_LENGTH (REGNO (dst
)) += length
;
812 REG_N_CALLS_CROSSED (REGNO (dst
)) += num_calls
;
813 REG_FREQ_CALLS_CROSSED (REGNO (dst
)) += freq_calls
;
818 "Fixed operand of insn %d.\n",
822 for (p
= PREV_INSN (insn
); p
; p
= PREV_INSN (p
))
829 if (reg_overlap_mentioned_p (dst
, PATTERN (p
)))
831 if (try_auto_increment (p
, insn
, 0, dst
, newconst
, 0))
836 for (p
= NEXT_INSN (insn
); p
; p
= NEXT_INSN (p
))
843 if (reg_overlap_mentioned_p (dst
, PATTERN (p
)))
845 try_auto_increment (p
, insn
, 0, dst
, newconst
, 1);
854 if (reg_set_p (dst
, PATTERN (p
)))
857 /* If we have passed a call instruction, and the
858 pseudo-reg SRC is not already live across a call,
859 then don't perform the optimization. */
860 /* reg_set_p is overly conservative for CALL_INSNS, thinks that all
861 hard regs are clobbered. Thus, we only use it for src for
868 freq_calls
+= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (p
));
871 if (REG_N_CALLS_CROSSED (REGNO (src
)) == 0)
874 if (call_used_regs
[REGNO (dst
)]
875 || find_reg_fusage (p
, CLOBBER
, dst
))
878 else if (reg_set_p (src
, PATTERN (p
)))
885 /* Main entry for the register move optimization.
886 F is the first instruction.
887 NREGS is one plus the highest pseudo-reg number used in the instruction.
888 REGMOVE_DUMP_FILE is a stream for output of a trace of actions taken
889 (or 0 if none should be output). */
892 regmove_optimize (rtx f
, int nregs
)
898 rtx copy_src
, copy_dst
;
900 /* ??? Hack. Regmove doesn't examine the CFG, and gets mightily
901 confused by non-call exceptions ending blocks. */
902 if (flag_non_call_exceptions
)
905 df_note_add_problem ();
908 regstat_init_n_sets_and_refs ();
909 regstat_compute_ri ();
911 regno_src_regno
= XNEWVEC (int, nregs
);
912 for (i
= nregs
; --i
>= 0; )
913 regno_src_regno
[i
] = -1;
915 /* A forward/backward pass. Replace output operands with input operands. */
917 for (pass
= 0; pass
<= 2; pass
++)
919 if (! flag_regmove
&& pass
>= flag_expensive_optimizations
)
923 fprintf (dump_file
, "Starting %s pass...\n",
924 pass
? "backward" : "forward");
926 for (insn
= pass
? get_last_insn () : f
; insn
;
927 insn
= pass
? PREV_INSN (insn
) : NEXT_INSN (insn
))
931 set
= single_set (insn
);
935 if (flag_expensive_optimizations
&& ! pass
936 && (GET_CODE (SET_SRC (set
)) == SIGN_EXTEND
937 || GET_CODE (SET_SRC (set
)) == ZERO_EXTEND
)
938 && REG_P (XEXP (SET_SRC (set
), 0))
939 && REG_P (SET_DEST (set
)))
940 optimize_reg_copy_3 (insn
, SET_DEST (set
), SET_SRC (set
));
942 if (flag_expensive_optimizations
&& ! pass
943 && REG_P (SET_SRC (set
))
944 && REG_P (SET_DEST (set
)))
946 /* If this is a register-register copy where SRC is not dead,
947 see if we can optimize it. If this optimization succeeds,
948 it will become a copy where SRC is dead. */
949 if ((find_reg_note (insn
, REG_DEAD
, SET_SRC (set
))
950 || optimize_reg_copy_1 (insn
, SET_DEST (set
), SET_SRC (set
)))
951 && REGNO (SET_DEST (set
)) >= FIRST_PSEUDO_REGISTER
)
953 /* Similarly for a pseudo-pseudo copy when SRC is dead. */
954 if (REGNO (SET_SRC (set
)) >= FIRST_PSEUDO_REGISTER
)
955 optimize_reg_copy_2 (insn
, SET_DEST (set
), SET_SRC (set
));
956 if (regno_src_regno
[REGNO (SET_DEST (set
))] < 0
957 && SET_SRC (set
) != SET_DEST (set
))
959 int srcregno
= REGNO (SET_SRC (set
));
960 if (regno_src_regno
[srcregno
] >= 0)
961 srcregno
= regno_src_regno
[srcregno
];
962 regno_src_regno
[REGNO (SET_DEST (set
))] = srcregno
;
969 /* A backward pass. Replace input operands with output operands. */
972 fprintf (dump_file
, "Starting backward pass...\n");
974 for (insn
= get_last_insn (); insn
; insn
= PREV_INSN (insn
))
981 if (! find_matches (insn
, &match
))
984 /* Now scan through the operands looking for a destination operand
985 which is supposed to match a source operand.
986 Then scan backward for an instruction which sets the source
987 operand. If safe, then replace the source operand with the
988 dest operand in both instructions. */
992 for (op_no
= 0; op_no
< recog_data
.n_operands
; op_no
++)
994 rtx set
, p
, src
, dst
;
995 rtx src_note
, dst_note
;
996 int num_calls
= 0, freq_calls
= 0;
997 enum reg_class src_class
, dst_class
;
1000 match_no
= match
.with
[op_no
];
1002 /* Nothing to do if the two operands aren't supposed to match. */
1006 dst
= recog_data
.operand
[match_no
];
1007 src
= recog_data
.operand
[op_no
];
1013 || REGNO (dst
) < FIRST_PSEUDO_REGISTER
1014 || REG_LIVE_LENGTH (REGNO (dst
)) < 0
1015 || GET_MODE (src
) != GET_MODE (dst
))
1018 /* If the operands already match, then there is nothing to do. */
1019 if (operands_match_p (src
, dst
))
1022 if (match
.commutative
[op_no
] >= 0)
1024 rtx comm
= recog_data
.operand
[match
.commutative
[op_no
]];
1025 if (operands_match_p (comm
, dst
))
1029 set
= single_set (insn
);
1033 /* Note that single_set ignores parts of a parallel set for
1034 which one of the destinations is REG_UNUSED. We can't
1035 handle that here, since we can wind up rewriting things
1036 such that a single register is set twice within a single
1038 if (reg_set_p (src
, insn
))
1041 /* match_no/dst must be a write-only operand, and
1042 operand_operand/src must be a read-only operand. */
1043 if (match
.use
[op_no
] != READ
1044 || match
.use
[match_no
] != WRITE
)
1047 if (match
.early_clobber
[match_no
]
1048 && count_occurrences (PATTERN (insn
), src
, 0) > 1)
1051 /* Make sure match_no is the destination. */
1052 if (recog_data
.operand
[match_no
] != SET_DEST (set
))
1055 if (REGNO (src
) < FIRST_PSEUDO_REGISTER
)
1057 if (GET_CODE (SET_SRC (set
)) == PLUS
1058 && GET_CODE (XEXP (SET_SRC (set
), 1)) == CONST_INT
1059 && XEXP (SET_SRC (set
), 0) == src
1060 && fixup_match_2 (insn
, dst
, src
,
1061 XEXP (SET_SRC (set
), 1)))
1065 src_class
= reg_preferred_class (REGNO (src
));
1066 dst_class
= reg_preferred_class (REGNO (dst
));
1068 if (! (src_note
= find_reg_note (insn
, REG_DEAD
, src
)))
1070 /* We used to force the copy here like in other cases, but
1071 it produces worse code, as it eliminates no copy
1072 instructions and the copy emitted will be produced by
1073 reload anyway. On patterns with multiple alternatives,
1074 there may be better solution available.
1076 In particular this change produced slower code for numeric
1082 if (! regclass_compatible_p (src_class
, dst_class
))
1092 /* Can not modify an earlier insn to set dst if this insn
1093 uses an old value in the source. */
1094 if (reg_overlap_mentioned_p (dst
, SET_SRC (set
)))
1104 /* If src is set once in a different basic block,
1105 and is set equal to a constant, then do not use
1106 it for this optimization, as this would make it
1107 no longer equivalent to a constant. */
1109 if (reg_is_remote_constant_p (src
, insn
))
1122 "Could fix operand %d of insn %d matching operand %d.\n",
1123 op_no
, INSN_UID (insn
), match_no
);
1125 /* Scan backward to find the first instruction that uses
1126 the input operand. If the operand is set here, then
1127 replace it in both instructions with match_no. */
1129 for (length
= 0, p
= PREV_INSN (insn
); p
; p
= PREV_INSN (p
))
1133 /* ??? We can't scan past the end of a basic block without
1134 updating the register lifetime info
1135 (REG_DEAD/basic_block_live_at_start). */
1136 if (perhaps_ends_bb_p (p
))
1138 else if (! INSN_P (p
))
1143 /* ??? See if all of SRC is set in P. This test is much
1144 more conservative than it needs to be. */
1145 pset
= single_set (p
);
1146 if (pset
&& SET_DEST (pset
) == src
)
1148 /* We use validate_replace_rtx, in case there
1149 are multiple identical source operands. All of
1150 them have to be changed at the same time. */
1151 if (validate_replace_rtx (src
, dst
, insn
))
1153 if (validate_change (p
, &SET_DEST (pset
),
1158 /* Change all source operands back.
1159 This modifies the dst as a side-effect. */
1160 validate_replace_rtx (dst
, src
, insn
);
1161 /* Now make sure the dst is right. */
1162 validate_change (insn
,
1163 recog_data
.operand_loc
[match_no
],
1170 /* We can't make this change if SRC is read or
1171 partially written in P, since we are going to
1172 eliminate SRC. We can't make this change
1173 if DST is mentioned at all in P,
1174 since we are going to change its value. */
1175 if (reg_overlap_mentioned_p (src
, PATTERN (p
))
1176 || reg_mentioned_p (dst
, PATTERN (p
)))
1179 /* If we have passed a call instruction, and the
1180 pseudo-reg DST is not already live across a call,
1181 then don't perform the optimization. */
1185 freq_calls
+= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (p
));
1187 if (REG_N_CALLS_CROSSED (REGNO (dst
)) == 0)
1196 /* Remove the death note for SRC from INSN. */
1197 remove_note (insn
, src_note
);
1198 /* Move the death note for SRC to P if it is used
1200 if (reg_overlap_mentioned_p (src
, PATTERN (p
)))
1202 XEXP (src_note
, 1) = REG_NOTES (p
);
1203 REG_NOTES (p
) = src_note
;
1205 /* If there is a REG_DEAD note for DST on P, then remove
1206 it, because DST is now set there. */
1207 if ((dst_note
= find_reg_note (p
, REG_DEAD
, dst
)))
1208 remove_note (p
, dst_note
);
1210 dstno
= REGNO (dst
);
1211 srcno
= REGNO (src
);
1213 INC_REG_N_SETS (dstno
, 1);
1214 INC_REG_N_SETS (srcno
, -1);
1216 REG_N_CALLS_CROSSED (dstno
) += num_calls
;
1217 REG_N_CALLS_CROSSED (srcno
) -= num_calls
;
1218 REG_FREQ_CALLS_CROSSED (dstno
) += freq_calls
;
1219 REG_FREQ_CALLS_CROSSED (srcno
) -= freq_calls
;
1221 REG_LIVE_LENGTH (dstno
) += length
;
1222 if (REG_LIVE_LENGTH (srcno
) >= 0)
1224 REG_LIVE_LENGTH (srcno
) -= length
;
1225 /* REG_LIVE_LENGTH is only an approximation after
1226 combine if sched is not run, so make sure that we
1227 still have a reasonable value. */
1228 if (REG_LIVE_LENGTH (srcno
) < 2)
1229 REG_LIVE_LENGTH (srcno
) = 2;
1234 "Fixed operand %d of insn %d matching operand %d.\n",
1235 op_no
, INSN_UID (insn
), match_no
);
1241 /* If we weren't able to replace any of the alternatives, try an
1242 alternative approach of copying the source to the destination. */
1243 if (!success
&& copy_src
!= NULL_RTX
)
1244 copy_src_to_dest (insn
, copy_src
, copy_dst
);
1250 free (regno_src_regno
);
1253 free (reg_set_in_bb
);
1254 reg_set_in_bb
= NULL
;
1256 regstat_free_n_sets_and_refs ();
1260 /* Returns nonzero if INSN's pattern has matching constraints for any operand.
1261 Returns 0 if INSN can't be recognized, or if the alternative can't be
1264 Initialize the info in MATCHP based on the constraints. */
1267 find_matches (rtx insn
, struct match
*matchp
)
1269 int likely_spilled
[MAX_RECOG_OPERANDS
];
1271 int any_matches
= 0;
1273 extract_insn (insn
);
1274 if (! constrain_operands (0))
1277 /* Must initialize this before main loop, because the code for
1278 the commutative case may set matches for operands other than
1280 for (op_no
= recog_data
.n_operands
; --op_no
>= 0; )
1281 matchp
->with
[op_no
] = matchp
->commutative
[op_no
] = -1;
1283 for (op_no
= 0; op_no
< recog_data
.n_operands
; op_no
++)
1289 p
= recog_data
.constraints
[op_no
];
1291 likely_spilled
[op_no
] = 0;
1292 matchp
->use
[op_no
] = READ
;
1293 matchp
->early_clobber
[op_no
] = 0;
1295 matchp
->use
[op_no
] = WRITE
;
1297 matchp
->use
[op_no
] = READWRITE
;
1299 for (;*p
&& i
< which_alternative
; p
++)
1303 while ((c
= *p
) != '\0' && c
!= ',')
1312 matchp
->early_clobber
[op_no
] = 1;
1315 matchp
->commutative
[op_no
] = op_no
+ 1;
1316 matchp
->commutative
[op_no
+ 1] = op_no
;
1319 case '0': case '1': case '2': case '3': case '4':
1320 case '5': case '6': case '7': case '8': case '9':
1323 unsigned long match_ul
= strtoul (p
, &end
, 10);
1324 int match
= match_ul
;
1328 if (match
< op_no
&& likely_spilled
[match
])
1330 matchp
->with
[op_no
] = match
;
1332 if (matchp
->commutative
[op_no
] >= 0)
1333 matchp
->with
[matchp
->commutative
[op_no
]] = match
;
1337 case 'a': case 'b': case 'c': case 'd': case 'e': case 'f': case 'h':
1338 case 'j': case 'k': case 'l': case 'p': case 'q': case 't': case 'u':
1339 case 'v': case 'w': case 'x': case 'y': case 'z': case 'A': case 'B':
1340 case 'C': case 'D': case 'W': case 'Y': case 'Z':
1341 if (CLASS_LIKELY_SPILLED_P (REG_CLASS_FROM_CONSTRAINT ((unsigned char) c
, p
) ))
1342 likely_spilled
[op_no
] = 1;
1345 p
+= CONSTRAINT_LEN (c
, p
);
1354 gate_handle_regmove (void)
1356 return (optimize
> 0 && flag_regmove
);
1359 /* Register allocation pre-pass, to reduce number of moves necessary
1360 for two-address machines. */
1362 rest_of_handle_regmove (void)
1364 regmove_optimize (get_insns (), max_reg_num ());
1368 struct rtl_opt_pass pass_regmove
=
1372 "regmove", /* name */
1373 gate_handle_regmove
, /* gate */
1374 rest_of_handle_regmove
, /* execute */
1377 0, /* static_pass_number */
1378 TV_REGMOVE
, /* tv_id */
1379 0, /* properties_required */
1380 0, /* properties_provided */
1381 0, /* properties_destroyed */
1382 0, /* todo_flags_start */
1383 TODO_df_finish
| TODO_verify_rtl_sharing
|
1385 TODO_ggc_collect
/* todo_flags_finish */