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
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 rtx
discover_flags_reg (void);
62 static void mark_flags_life_zones (rtx
);
63 static void flags_set_1 (rtx
, const_rtx
, void *);
65 static int find_matches (rtx
, struct match
*);
66 static int regclass_compatible_p (int, int);
67 static int fixup_match_2 (rtx
, rtx
, rtx
, rtx
);
69 /* Return nonzero if registers with CLASS1 and CLASS2 can be merged without
70 causing too much register allocation problems. */
72 regclass_compatible_p (int class0
, int class1
)
74 return (class0
== class1
75 || (reg_class_subset_p (class0
, class1
)
76 && ! CLASS_LIKELY_SPILLED_P (class0
))
77 || (reg_class_subset_p (class1
, class0
)
78 && ! CLASS_LIKELY_SPILLED_P (class1
)));
82 /* Determine if the pattern generated by add_optab has a clobber,
83 such as might be issued for a flags hard register. To make the
84 code elsewhere simpler, we handle cc0 in this same framework.
86 Return the register if one was discovered. Return NULL_RTX if
87 if no flags were found. Return pc_rtx if we got confused. */
90 discover_flags_reg (void)
93 tmp
= gen_rtx_REG (word_mode
, 10000);
94 tmp
= gen_add3_insn (tmp
, tmp
, const2_rtx
);
96 /* If we get something that isn't a simple set, or a
97 [(set ..) (clobber ..)], this whole function will go wrong. */
98 if (GET_CODE (tmp
) == SET
)
100 else if (GET_CODE (tmp
) == PARALLEL
)
104 if (XVECLEN (tmp
, 0) != 2)
106 tmp
= XVECEXP (tmp
, 0, 1);
107 if (GET_CODE (tmp
) != CLOBBER
)
111 /* Don't do anything foolish if the md wanted to clobber a
112 scratch or something. We only care about hard regs.
113 Moreover we don't like the notion of subregs of hard regs. */
114 if (GET_CODE (tmp
) == SUBREG
115 && REG_P (SUBREG_REG (tmp
))
116 && REGNO (SUBREG_REG (tmp
)) < FIRST_PSEUDO_REGISTER
)
118 found
= (REG_P (tmp
) && REGNO (tmp
) < FIRST_PSEUDO_REGISTER
);
120 return (found
? tmp
: NULL_RTX
);
126 /* It is a tedious task identifying when the flags register is live and
127 when it is safe to optimize. Since we process the instruction stream
128 multiple times, locate and record these live zones by marking the
129 mode of the instructions --
131 QImode is used on the instruction at which the flags becomes live.
133 HImode is used within the range (exclusive) that the flags are
134 live. Thus the user of the flags is not marked.
136 All other instructions are cleared to VOIDmode. */
138 /* Used to communicate with flags_set_1. */
139 static rtx flags_set_1_rtx
;
140 static int flags_set_1_set
;
143 mark_flags_life_zones (rtx flags
)
150 /* If we found a flags register on a cc0 host, bail. */
151 if (flags
== NULL_RTX
)
153 else if (flags
!= cc0_rtx
)
157 /* Simple cases first: if no flags, clear all modes. If confusing,
158 mark the entire function as being in a flags shadow. */
159 if (flags
== NULL_RTX
|| flags
== pc_rtx
)
161 enum machine_mode mode
= (flags
? HImode
: VOIDmode
);
163 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
164 PUT_MODE (insn
, mode
);
172 flags_regno
= REGNO (flags
);
173 flags_nregs
= hard_regno_nregs
[flags_regno
][GET_MODE (flags
)];
175 flags_set_1_rtx
= flags
;
177 /* Process each basic block. */
178 FOR_EACH_BB_REVERSE (block
)
183 insn
= BB_HEAD (block
);
184 end
= BB_END (block
);
186 /* Look out for the (unlikely) case of flags being live across
187 basic block boundaries. */
192 for (i
= 0; i
< flags_nregs
; ++i
)
193 live
|= REGNO_REG_SET_P (df_get_live_in (block
), flags_regno
+ i
);
199 /* Process liveness in reverse order of importance --
200 alive, death, birth. This lets more important info
201 overwrite the mode of lesser info. */
206 /* In the cc0 case, death is not marked in reg notes,
207 but is instead the mere use of cc0 when it is alive. */
208 if (live
&& reg_mentioned_p (cc0_rtx
, PATTERN (insn
)))
211 /* In the hard reg case, we watch death notes. */
212 if (live
&& find_regno_note (insn
, REG_DEAD
, flags_regno
))
215 PUT_MODE (insn
, (live
? HImode
: VOIDmode
));
217 /* In either case, birth is denoted simply by its presence
218 as the destination of a set. */
220 note_stores (PATTERN (insn
), flags_set_1
, NULL
);
224 PUT_MODE (insn
, QImode
);
228 PUT_MODE (insn
, (live
? HImode
: VOIDmode
));
232 insn
= NEXT_INSN (insn
);
237 /* A subroutine of mark_flags_life_zones, called through note_stores. */
240 flags_set_1 (rtx x
, const_rtx pat
, void *data ATTRIBUTE_UNUSED
)
242 if (GET_CODE (pat
) == SET
243 && reg_overlap_mentioned_p (x
, flags_set_1_rtx
))
249 /* Find the place in the rtx X where REG is used as a memory address.
250 Return the MEM rtx that so uses it.
251 If PLUSCONST is nonzero, search instead for a memory address equivalent to
252 (plus REG (const_int PLUSCONST)).
254 If such an address does not appear, return 0.
255 If REG appears more than once, or is used other than in such an address,
259 find_use_as_address (rtx x
, rtx reg
, HOST_WIDE_INT plusconst
)
261 enum rtx_code code
= GET_CODE (x
);
262 const char * const fmt
= GET_RTX_FORMAT (code
);
267 if (code
== MEM
&& XEXP (x
, 0) == reg
&& plusconst
== 0)
270 if (code
== MEM
&& GET_CODE (XEXP (x
, 0)) == PLUS
271 && XEXP (XEXP (x
, 0), 0) == reg
272 && GET_CODE (XEXP (XEXP (x
, 0), 1)) == CONST_INT
273 && INTVAL (XEXP (XEXP (x
, 0), 1)) == plusconst
)
276 if (code
== SIGN_EXTRACT
|| code
== ZERO_EXTRACT
)
278 /* If REG occurs inside a MEM used in a bit-field reference,
279 that is unacceptable. */
280 if (find_use_as_address (XEXP (x
, 0), reg
, 0) != 0)
281 return (rtx
) (size_t) 1;
285 return (rtx
) (size_t) 1;
287 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
291 tem
= find_use_as_address (XEXP (x
, i
), reg
, plusconst
);
295 return (rtx
) (size_t) 1;
297 else if (fmt
[i
] == 'E')
300 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
302 tem
= find_use_as_address (XVECEXP (x
, i
, j
), reg
, plusconst
);
306 return (rtx
) (size_t) 1;
315 /* INC_INSN is an instruction that adds INCREMENT to REG.
316 Try to fold INC_INSN as a post/pre in/decrement into INSN.
317 Iff INC_INSN_SET is nonzero, inc_insn has a destination different from src.
318 Return nonzero for success. */
320 try_auto_increment (rtx insn
, rtx inc_insn
, rtx inc_insn_set
, rtx reg
,
321 HOST_WIDE_INT increment
, int pre
)
323 enum rtx_code inc_code
;
325 rtx pset
= single_set (insn
);
328 /* Can't use the size of SET_SRC, we might have something like
329 (sign_extend:SI (mem:QI ... */
330 rtx use
= find_use_as_address (pset
, reg
, 0);
331 if (use
!= 0 && use
!= (rtx
) (size_t) 1)
333 int size
= GET_MODE_SIZE (GET_MODE (use
));
335 || (HAVE_POST_INCREMENT
336 && pre
== 0 && (inc_code
= POST_INC
, increment
== size
))
337 || (HAVE_PRE_INCREMENT
338 && pre
== 1 && (inc_code
= PRE_INC
, increment
== size
))
339 || (HAVE_POST_DECREMENT
340 && pre
== 0 && (inc_code
= POST_DEC
, increment
== -size
))
341 || (HAVE_PRE_DECREMENT
342 && pre
== 1 && (inc_code
= PRE_DEC
, increment
== -size
))
348 &SET_SRC (inc_insn_set
),
349 XEXP (SET_SRC (inc_insn_set
), 0), 1);
350 validate_change (insn
, &XEXP (use
, 0),
351 gen_rtx_fmt_e (inc_code
, Pmode
, reg
), 1);
352 if (apply_change_group ())
354 /* If there is a REG_DEAD note on this insn, we must
355 change this not to REG_UNUSED meaning that the register
356 is set, but the value is dead. Failure to do so will
357 result in sched1 dying -- when it recomputes lifetime
358 information, the number of REG_DEAD notes will have
360 rtx note
= find_reg_note (insn
, REG_DEAD
, reg
);
362 PUT_MODE (note
, REG_UNUSED
);
364 add_reg_note (insn
, REG_INC
, reg
);
367 delete_insn (inc_insn
);
378 static int *regno_src_regno
;
381 /* Return 1 if INSN might end a basic block. */
383 static int perhaps_ends_bb_p (rtx insn
)
385 switch (GET_CODE (insn
))
389 /* These always end a basic block. */
393 /* A CALL_INSN might be the last insn of a basic block, if it is inside
394 an EH region or if there are nonlocal gotos. Note that this test is
395 very conservative. */
396 if (nonlocal_goto_handler_labels
)
400 return can_throw_internal (insn
);
404 /* INSN is a copy from SRC to DEST, both registers, and SRC does not die
407 Search forward to see if SRC dies before either it or DEST is modified,
408 but don't scan past the end of a basic block. If so, we can replace SRC
409 with DEST and let SRC die in INSN.
411 This will reduce the number of registers live in that range and may enable
412 DEST to be tied to SRC, thus often saving one register in addition to a
413 register-register copy. */
416 optimize_reg_copy_1 (rtx insn
, rtx dest
, rtx src
)
421 int sregno
= REGNO (src
);
422 int dregno
= REGNO (dest
);
424 /* We don't want to mess with hard regs if register classes are small. */
426 || (SMALL_REGISTER_CLASSES
427 && (sregno
< FIRST_PSEUDO_REGISTER
428 || dregno
< FIRST_PSEUDO_REGISTER
))
429 /* We don't see all updates to SP if they are in an auto-inc memory
430 reference, so we must disallow this optimization on them. */
431 || sregno
== STACK_POINTER_REGNUM
|| dregno
== STACK_POINTER_REGNUM
)
434 for (p
= NEXT_INSN (insn
); p
; p
= NEXT_INSN (p
))
436 /* ??? We can't scan past the end of a basic block without updating
437 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
438 if (perhaps_ends_bb_p (p
))
440 else if (! INSN_P (p
))
443 if (reg_set_p (src
, p
) || reg_set_p (dest
, p
)
444 /* If SRC is an asm-declared register, it must not be replaced
445 in any asm. Unfortunately, the REG_EXPR tree for the asm
446 variable may be absent in the SRC rtx, so we can't check the
447 actual register declaration easily (the asm operand will have
448 it, though). To avoid complicating the test for a rare case,
449 we just don't perform register replacement for a hard reg
450 mentioned in an asm. */
451 || (sregno
< FIRST_PSEUDO_REGISTER
452 && asm_noperands (PATTERN (p
)) >= 0
453 && reg_overlap_mentioned_p (src
, PATTERN (p
)))
454 /* Don't change hard registers used by a call. */
455 || (CALL_P (p
) && sregno
< FIRST_PSEUDO_REGISTER
456 && find_reg_fusage (p
, USE
, src
))
457 /* Don't change a USE of a register. */
458 || (GET_CODE (PATTERN (p
)) == USE
459 && reg_overlap_mentioned_p (src
, XEXP (PATTERN (p
), 0))))
462 /* See if all of SRC dies in P. This test is slightly more
463 conservative than it needs to be. */
464 if ((note
= find_regno_note (p
, REG_DEAD
, sregno
)) != 0
465 && GET_MODE (XEXP (note
, 0)) == GET_MODE (src
))
472 int s_freq_calls
= 0;
473 int d_freq_calls
= 0;
475 /* We can do the optimization. Scan forward from INSN again,
476 replacing regs as we go. Set FAILED if a replacement can't
477 be done. In that case, we can't move the death note for SRC.
478 This should be rare. */
480 /* Set to stop at next insn. */
481 for (q
= next_real_insn (insn
);
482 q
!= next_real_insn (p
);
483 q
= next_real_insn (q
))
485 if (reg_overlap_mentioned_p (src
, PATTERN (q
)))
487 /* If SRC is a hard register, we might miss some
488 overlapping registers with validate_replace_rtx,
489 so we would have to undo it. We can't if DEST is
490 present in the insn, so fail in that combination
492 if (sregno
< FIRST_PSEUDO_REGISTER
493 && reg_mentioned_p (dest
, PATTERN (q
)))
496 /* Attempt to replace all uses. */
497 else if (!validate_replace_rtx (src
, dest
, q
))
500 /* If this succeeded, but some part of the register
501 is still present, undo the replacement. */
502 else if (sregno
< FIRST_PSEUDO_REGISTER
503 && reg_overlap_mentioned_p (src
, PATTERN (q
)))
505 validate_replace_rtx (dest
, src
, q
);
510 /* For SREGNO, count the total number of insns scanned.
511 For DREGNO, count the total number of insns scanned after
512 passing the death note for DREGNO. */
517 /* If the insn in which SRC dies is a CALL_INSN, don't count it
518 as a call that has been crossed. Otherwise, count it. */
519 if (q
!= p
&& CALL_P (q
))
521 /* Similarly, total calls for SREGNO, total calls beyond
522 the death note for DREGNO. */
524 s_freq_calls
+= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (q
));
528 d_freq_calls
+= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (q
));
532 /* If DEST dies here, remove the death note and save it for
533 later. Make sure ALL of DEST dies here; again, this is
534 overly conservative. */
536 && (dest_death
= find_regno_note (q
, REG_DEAD
, dregno
)) != 0)
538 if (GET_MODE (XEXP (dest_death
, 0)) != GET_MODE (dest
))
539 failed
= 1, dest_death
= 0;
541 remove_note (q
, dest_death
);
547 /* These counters need to be updated if and only if we are
548 going to move the REG_DEAD note. */
549 if (sregno
>= FIRST_PSEUDO_REGISTER
)
551 if (REG_LIVE_LENGTH (sregno
) >= 0)
553 REG_LIVE_LENGTH (sregno
) -= s_length
;
554 /* REG_LIVE_LENGTH is only an approximation after
555 combine if sched is not run, so make sure that we
556 still have a reasonable value. */
557 if (REG_LIVE_LENGTH (sregno
) < 2)
558 REG_LIVE_LENGTH (sregno
) = 2;
561 REG_N_CALLS_CROSSED (sregno
) -= s_n_calls
;
562 REG_FREQ_CALLS_CROSSED (sregno
) -= s_freq_calls
;
565 /* Move death note of SRC from P to INSN. */
566 remove_note (p
, note
);
567 XEXP (note
, 1) = REG_NOTES (insn
);
568 REG_NOTES (insn
) = note
;
571 /* DEST is also dead if INSN has a REG_UNUSED note for DEST. */
573 && (dest_death
= find_regno_note (insn
, REG_UNUSED
, dregno
)))
575 PUT_REG_NOTE_KIND (dest_death
, REG_DEAD
);
576 remove_note (insn
, dest_death
);
579 /* Put death note of DEST on P if we saw it die. */
582 XEXP (dest_death
, 1) = REG_NOTES (p
);
583 REG_NOTES (p
) = dest_death
;
585 if (dregno
>= FIRST_PSEUDO_REGISTER
)
587 /* If and only if we are moving the death note for DREGNO,
588 then we need to update its counters. */
589 if (REG_LIVE_LENGTH (dregno
) >= 0)
590 REG_LIVE_LENGTH (dregno
) += d_length
;
591 REG_N_CALLS_CROSSED (dregno
) += d_n_calls
;
592 REG_FREQ_CALLS_CROSSED (dregno
) += d_freq_calls
;
599 /* If SRC is a hard register which is set or killed in some other
600 way, we can't do this optimization. */
601 else if (sregno
< FIRST_PSEUDO_REGISTER
602 && dead_or_set_p (p
, src
))
608 /* INSN is a copy of SRC to DEST, in which SRC dies. See if we now have
609 a sequence of insns that modify DEST followed by an insn that sets
610 SRC to DEST in which DEST dies, with no prior modification of DEST.
611 (There is no need to check if the insns in between actually modify
612 DEST. We should not have cases where DEST is not modified, but
613 the optimization is safe if no such modification is detected.)
614 In that case, we can replace all uses of DEST, starting with INSN and
615 ending with the set of SRC to DEST, with SRC. We do not do this
616 optimization if a CALL_INSN is crossed unless SRC already crosses a
617 call or if DEST dies before the copy back to SRC.
619 It is assumed that DEST and SRC are pseudos; it is too complicated to do
620 this for hard registers since the substitutions we may make might fail. */
623 optimize_reg_copy_2 (rtx insn
, rtx dest
, rtx src
)
627 int sregno
= REGNO (src
);
628 int dregno
= REGNO (dest
);
630 for (p
= NEXT_INSN (insn
); p
; p
= NEXT_INSN (p
))
632 /* ??? We can't scan past the end of a basic block without updating
633 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
634 if (perhaps_ends_bb_p (p
))
636 else if (! INSN_P (p
))
639 set
= single_set (p
);
640 if (set
&& SET_SRC (set
) == dest
&& SET_DEST (set
) == src
641 && find_reg_note (p
, REG_DEAD
, dest
))
643 /* We can do the optimization. Scan forward from INSN again,
644 replacing regs as we go. */
646 /* Set to stop at next insn. */
647 for (q
= insn
; q
!= NEXT_INSN (p
); q
= NEXT_INSN (q
))
650 if (reg_mentioned_p (dest
, PATTERN (q
)))
654 PATTERN (q
) = replace_rtx (PATTERN (q
), dest
, src
);
655 note
= FIND_REG_INC_NOTE (q
, dest
);
658 remove_note (q
, note
);
659 add_reg_note (q
, REG_INC
, src
);
666 int freq
= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (q
));
667 REG_N_CALLS_CROSSED (dregno
)--;
668 REG_N_CALLS_CROSSED (sregno
)++;
669 REG_FREQ_CALLS_CROSSED (dregno
) -= freq
;
670 REG_FREQ_CALLS_CROSSED (sregno
) += freq
;
674 remove_note (p
, find_reg_note (p
, REG_DEAD
, dest
));
675 REG_N_DEATHS (dregno
)--;
676 remove_note (insn
, find_reg_note (insn
, REG_DEAD
, src
));
677 REG_N_DEATHS (sregno
)--;
681 if (reg_set_p (src
, p
)
682 || find_reg_note (p
, REG_DEAD
, dest
)
683 || (CALL_P (p
) && REG_N_CALLS_CROSSED (sregno
) == 0))
688 /* INSN is a ZERO_EXTEND or SIGN_EXTEND of SRC to DEST.
689 Look if SRC dies there, and if it is only set once, by loading
690 it from memory. If so, try to incorporate the zero/sign extension
691 into the memory read, change SRC to the mode of DEST, and alter
692 the remaining accesses to use the appropriate SUBREG. This allows
693 SRC and DEST to be tied later. */
695 optimize_reg_copy_3 (rtx insn
, rtx dest
, rtx src
)
697 rtx src_reg
= XEXP (src
, 0);
698 int src_no
= REGNO (src_reg
);
699 int dst_no
= REGNO (dest
);
701 enum machine_mode old_mode
;
703 if (src_no
< FIRST_PSEUDO_REGISTER
704 || dst_no
< FIRST_PSEUDO_REGISTER
705 || ! find_reg_note (insn
, REG_DEAD
, src_reg
)
706 || REG_N_DEATHS (src_no
) != 1
707 || REG_N_SETS (src_no
) != 1)
709 for (p
= PREV_INSN (insn
); p
&& ! reg_set_p (src_reg
, p
); p
= PREV_INSN (p
))
710 /* ??? We can't scan past the end of a basic block without updating
711 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
712 if (perhaps_ends_bb_p (p
))
718 if (! (set
= single_set (p
))
719 || !MEM_P (SET_SRC (set
))
720 /* If there's a REG_EQUIV note, this must be an insn that loads an
721 argument. Prefer keeping the note over doing this optimization. */
722 || find_reg_note (p
, REG_EQUIV
, NULL_RTX
)
723 || SET_DEST (set
) != src_reg
)
726 /* Be conservative: although this optimization is also valid for
727 volatile memory references, that could cause trouble in later passes. */
728 if (MEM_VOLATILE_P (SET_SRC (set
)))
731 /* Do not use a SUBREG to truncate from one mode to another if truncation
733 if (GET_MODE_BITSIZE (GET_MODE (src_reg
)) <= GET_MODE_BITSIZE (GET_MODE (src
))
734 && !TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (GET_MODE (src
)),
735 GET_MODE_BITSIZE (GET_MODE (src_reg
))))
738 old_mode
= GET_MODE (src_reg
);
739 PUT_MODE (src_reg
, GET_MODE (src
));
740 XEXP (src
, 0) = SET_SRC (set
);
742 /* Include this change in the group so that it's easily undone if
743 one of the changes in the group is invalid. */
744 validate_change (p
, &SET_SRC (set
), src
, 1);
746 /* Now walk forward making additional replacements. We want to be able
747 to undo all the changes if a later substitution fails. */
748 while (p
= NEXT_INSN (p
), p
!= insn
)
753 /* Make a tentative change. */
754 validate_replace_rtx_group (src_reg
,
755 gen_lowpart_SUBREG (old_mode
, src_reg
),
759 validate_replace_rtx_group (src
, src_reg
, insn
);
761 /* Now see if all the changes are valid. */
762 if (! apply_change_group ())
764 /* One or more changes were no good. Back out everything. */
765 PUT_MODE (src_reg
, old_mode
);
766 XEXP (src
, 0) = src_reg
;
770 rtx note
= find_reg_note (p
, REG_EQUAL
, NULL_RTX
);
772 remove_note (p
, note
);
777 /* If we were not able to update the users of src to use dest directly, try
778 instead moving the value to dest directly before the operation. */
781 copy_src_to_dest (rtx insn
, rtx src
, rtx dest
)
795 /* A REG_LIVE_LENGTH of -1 indicates the register is equivalent to a constant
796 or memory location and is used infrequently; a REG_LIVE_LENGTH of -2 is
797 parameter when there is no frame pointer that is not allocated a register.
798 For now, we just reject them, rather than incrementing the live length. */
801 && REG_LIVE_LENGTH (REGNO (src
)) > 0
803 && REG_LIVE_LENGTH (REGNO (dest
)) > 0
804 && (set
= single_set (insn
)) != NULL_RTX
805 && !reg_mentioned_p (dest
, SET_SRC (set
))
806 && GET_MODE (src
) == GET_MODE (dest
))
808 int old_num_regs
= reg_rtx_no
;
810 /* Generate the src->dest move. */
812 emit_move_insn (dest
, src
);
815 /* If this sequence uses new registers, we may not use it. */
816 if (old_num_regs
!= reg_rtx_no
817 || ! validate_replace_rtx (src
, dest
, insn
))
819 /* We have to restore reg_rtx_no to its old value, lest
820 recompute_reg_usage will try to compute the usage of the
821 new regs, yet reg_n_info is not valid for them. */
822 reg_rtx_no
= old_num_regs
;
825 emit_insn_before (seq
, insn
);
826 move_insn
= PREV_INSN (insn
);
827 p_move_notes
= ®_NOTES (move_insn
);
828 p_insn_notes
= ®_NOTES (insn
);
830 /* Move any notes mentioning src to the move instruction. */
831 for (link
= REG_NOTES (insn
); link
!= NULL_RTX
; link
= next
)
833 next
= XEXP (link
, 1);
834 if (XEXP (link
, 0) == src
)
836 *p_move_notes
= link
;
837 p_move_notes
= &XEXP (link
, 1);
841 *p_insn_notes
= link
;
842 p_insn_notes
= &XEXP (link
, 1);
846 *p_move_notes
= NULL_RTX
;
847 *p_insn_notes
= NULL_RTX
;
849 insn_uid
= INSN_UID (insn
);
850 move_uid
= INSN_UID (move_insn
);
852 /* Update the various register tables. */
853 dest_regno
= REGNO (dest
);
854 INC_REG_N_SETS (dest_regno
, 1);
855 REG_LIVE_LENGTH (dest_regno
)++;
856 src_regno
= REGNO (src
);
857 if (! find_reg_note (move_insn
, REG_DEAD
, src
))
858 REG_LIVE_LENGTH (src_regno
)++;
862 /* reg_set_in_bb[REGNO] points to basic block iff the register is set
863 only once in the given block and has REG_EQUAL note. */
865 static basic_block
*reg_set_in_bb
;
867 /* Size of reg_set_in_bb array. */
868 static unsigned int max_reg_computed
;
871 /* Return whether REG is set in only one location, and is set to a
872 constant, but is set in a different basic block from INSN (an
873 instructions which uses REG). In this case REG is equivalent to a
874 constant, and we don't want to break that equivalence, because that
875 may increase register pressure and make reload harder. If REG is
876 set in the same basic block as INSN, we don't worry about it,
877 because we'll probably need a register anyhow (??? but what if REG
878 is used in a different basic block as well as this one?). */
881 reg_is_remote_constant_p (rtx reg
, rtx insn
)
889 max_reg_computed
= max
= max_reg_num ();
890 reg_set_in_bb
= XCNEWVEC (basic_block
, max
);
900 /* This is the instruction which sets REG. If there is a
901 REG_EQUAL note, then REG is equivalent to a constant. */
903 && REG_P (SET_DEST (s
))
904 && REG_N_SETS (REGNO (SET_DEST (s
))) == 1
905 && find_reg_note (p
, REG_EQUAL
, NULL_RTX
))
906 reg_set_in_bb
[REGNO (SET_DEST (s
))] = bb
;
910 gcc_assert (REGNO (reg
) < max_reg_computed
);
911 if (reg_set_in_bb
[REGNO (reg
)] == NULL
)
913 return (reg_set_in_bb
[REGNO (reg
)] != BLOCK_FOR_INSN (insn
));
916 /* INSN is adding a CONST_INT to a REG. We search backwards looking for
917 another add immediate instruction with the same source and dest registers,
918 and if we find one, we change INSN to an increment, and return 1. If
919 no changes are made, we return 0.
922 (set (reg100) (plus reg1 offset1))
924 (set (reg100) (plus reg1 offset2))
926 (set (reg100) (plus reg1 offset1))
928 (set (reg100) (plus reg100 offset2-offset1)) */
930 /* ??? What does this comment mean? */
931 /* cse disrupts preincrement / postdecrement sequences when it finds a
932 hard register as ultimate source, like the frame pointer. */
935 fixup_match_2 (rtx insn
, rtx dst
, rtx src
, rtx offset
)
937 rtx p
, dst_death
= 0;
938 int length
, num_calls
= 0, freq_calls
= 0;
940 /* If SRC dies in INSN, we'd have to move the death note. This is
941 considered to be very unlikely, so we just skip the optimization
943 if (find_regno_note (insn
, REG_DEAD
, REGNO (src
)))
946 /* Scan backward to find the first instruction that sets DST. */
948 for (length
= 0, p
= PREV_INSN (insn
); p
; p
= PREV_INSN (p
))
952 /* ??? We can't scan past the end of a basic block without updating
953 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
954 if (perhaps_ends_bb_p (p
))
956 else if (! INSN_P (p
))
959 if (find_regno_note (p
, REG_DEAD
, REGNO (dst
)))
964 pset
= single_set (p
);
965 if (pset
&& SET_DEST (pset
) == dst
966 && GET_CODE (SET_SRC (pset
)) == PLUS
967 && XEXP (SET_SRC (pset
), 0) == src
968 && GET_CODE (XEXP (SET_SRC (pset
), 1)) == CONST_INT
)
970 HOST_WIDE_INT newconst
971 = INTVAL (offset
) - INTVAL (XEXP (SET_SRC (pset
), 1));
972 rtx add
= gen_add3_insn (dst
, dst
, GEN_INT (newconst
));
974 if (add
&& validate_change (insn
, &PATTERN (insn
), add
, 0))
976 /* Remove the death note for DST from DST_DEATH. */
979 remove_death (REGNO (dst
), dst_death
);
980 REG_LIVE_LENGTH (REGNO (dst
)) += length
;
981 REG_N_CALLS_CROSSED (REGNO (dst
)) += num_calls
;
982 REG_FREQ_CALLS_CROSSED (REGNO (dst
)) += freq_calls
;
987 "Fixed operand of insn %d.\n",
991 for (p
= PREV_INSN (insn
); p
; p
= PREV_INSN (p
))
998 if (reg_overlap_mentioned_p (dst
, PATTERN (p
)))
1000 if (try_auto_increment (p
, insn
, 0, dst
, newconst
, 0))
1005 for (p
= NEXT_INSN (insn
); p
; p
= NEXT_INSN (p
))
1012 if (reg_overlap_mentioned_p (dst
, PATTERN (p
)))
1014 try_auto_increment (p
, insn
, 0, dst
, newconst
, 1);
1023 if (reg_set_p (dst
, PATTERN (p
)))
1026 /* If we have passed a call instruction, and the
1027 pseudo-reg SRC is not already live across a call,
1028 then don't perform the optimization. */
1029 /* reg_set_p is overly conservative for CALL_INSNS, thinks that all
1030 hard regs are clobbered. Thus, we only use it for src for
1037 freq_calls
+= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (p
));
1040 if (REG_N_CALLS_CROSSED (REGNO (src
)) == 0)
1043 if (call_used_regs
[REGNO (dst
)]
1044 || find_reg_fusage (p
, CLOBBER
, dst
))
1047 else if (reg_set_p (src
, PATTERN (p
)))
1054 /* Main entry for the register move optimization.
1055 F is the first instruction.
1056 NREGS is one plus the highest pseudo-reg number used in the instruction.
1057 REGMOVE_DUMP_FILE is a stream for output of a trace of actions taken
1058 (or 0 if none should be output). */
1061 regmove_optimize (rtx f
, int nregs
)
1067 rtx copy_src
, copy_dst
;
1069 /* ??? Hack. Regmove doesn't examine the CFG, and gets mightily
1070 confused by non-call exceptions ending blocks. */
1071 if (flag_non_call_exceptions
)
1074 df_note_add_problem ();
1077 regstat_init_n_sets_and_refs ();
1078 regstat_compute_ri ();
1080 /* Find out where a potential flags register is live, and so that we
1081 can suppress some optimizations in those zones. */
1082 mark_flags_life_zones (discover_flags_reg ());
1084 regno_src_regno
= XNEWVEC (int, nregs
);
1085 for (i
= nregs
; --i
>= 0; )
1086 regno_src_regno
[i
] = -1;
1088 /* A forward/backward pass. Replace output operands with input operands. */
1090 for (pass
= 0; pass
<= 2; pass
++)
1092 /* We need fewer optimizations for IRA. */
1093 if (! flag_regmove
&& pass
>= flag_expensive_optimizations
)
1097 fprintf (dump_file
, "Starting %s pass...\n",
1098 pass
? "backward" : "forward");
1100 for (insn
= pass
? get_last_insn () : f
; insn
;
1101 insn
= pass
? PREV_INSN (insn
) : NEXT_INSN (insn
))
1105 set
= single_set (insn
);
1109 if (flag_expensive_optimizations
&& ! pass
1110 && (GET_CODE (SET_SRC (set
)) == SIGN_EXTEND
1111 || GET_CODE (SET_SRC (set
)) == ZERO_EXTEND
)
1112 && REG_P (XEXP (SET_SRC (set
), 0))
1113 && REG_P (SET_DEST (set
)))
1114 optimize_reg_copy_3 (insn
, SET_DEST (set
), SET_SRC (set
));
1116 if (flag_expensive_optimizations
&& ! pass
1117 && REG_P (SET_SRC (set
))
1118 && REG_P (SET_DEST (set
)))
1120 /* If this is a register-register copy where SRC is not dead,
1121 see if we can optimize it. If this optimization succeeds,
1122 it will become a copy where SRC is dead. */
1123 if ((find_reg_note (insn
, REG_DEAD
, SET_SRC (set
))
1124 || optimize_reg_copy_1 (insn
, SET_DEST (set
), SET_SRC (set
)))
1125 && REGNO (SET_DEST (set
)) >= FIRST_PSEUDO_REGISTER
)
1127 /* Similarly for a pseudo-pseudo copy when SRC is dead. */
1128 if (REGNO (SET_SRC (set
)) >= FIRST_PSEUDO_REGISTER
)
1129 optimize_reg_copy_2 (insn
, SET_DEST (set
), SET_SRC (set
));
1130 if (regno_src_regno
[REGNO (SET_DEST (set
))] < 0
1131 && SET_SRC (set
) != SET_DEST (set
))
1133 int srcregno
= REGNO (SET_SRC (set
));
1134 if (regno_src_regno
[srcregno
] >= 0)
1135 srcregno
= regno_src_regno
[srcregno
];
1136 regno_src_regno
[REGNO (SET_DEST (set
))] = srcregno
;
1143 /* A backward pass. Replace input operands with output operands. */
1146 fprintf (dump_file
, "Starting backward pass...\n");
1148 for (insn
= get_last_insn (); insn
; insn
= PREV_INSN (insn
))
1152 int op_no
, match_no
;
1155 if (! find_matches (insn
, &match
))
1158 /* Now scan through the operands looking for a destination operand
1159 which is supposed to match a source operand.
1160 Then scan backward for an instruction which sets the source
1161 operand. If safe, then replace the source operand with the
1162 dest operand in both instructions. */
1164 copy_src
= NULL_RTX
;
1165 copy_dst
= NULL_RTX
;
1166 for (op_no
= 0; op_no
< recog_data
.n_operands
; op_no
++)
1168 rtx set
, p
, src
, dst
;
1169 rtx src_note
, dst_note
;
1170 int num_calls
= 0, freq_calls
= 0;
1171 enum reg_class src_class
, dst_class
;
1174 match_no
= match
.with
[op_no
];
1176 /* Nothing to do if the two operands aren't supposed to match. */
1180 dst
= recog_data
.operand
[match_no
];
1181 src
= recog_data
.operand
[op_no
];
1187 || REGNO (dst
) < FIRST_PSEUDO_REGISTER
1188 || REG_LIVE_LENGTH (REGNO (dst
)) < 0
1189 || GET_MODE (src
) != GET_MODE (dst
))
1192 /* If the operands already match, then there is nothing to do. */
1193 if (operands_match_p (src
, dst
))
1196 if (match
.commutative
[op_no
] >= 0)
1198 rtx comm
= recog_data
.operand
[match
.commutative
[op_no
]];
1199 if (operands_match_p (comm
, dst
))
1203 set
= single_set (insn
);
1207 /* Note that single_set ignores parts of a parallel set for
1208 which one of the destinations is REG_UNUSED. We can't
1209 handle that here, since we can wind up rewriting things
1210 such that a single register is set twice within a single
1212 if (reg_set_p (src
, insn
))
1215 /* match_no/dst must be a write-only operand, and
1216 operand_operand/src must be a read-only operand. */
1217 if (match
.use
[op_no
] != READ
1218 || match
.use
[match_no
] != WRITE
)
1221 if (match
.early_clobber
[match_no
]
1222 && count_occurrences (PATTERN (insn
), src
, 0) > 1)
1225 /* Make sure match_no is the destination. */
1226 if (recog_data
.operand
[match_no
] != SET_DEST (set
))
1229 if (REGNO (src
) < FIRST_PSEUDO_REGISTER
)
1231 if (GET_CODE (SET_SRC (set
)) == PLUS
1232 && GET_CODE (XEXP (SET_SRC (set
), 1)) == CONST_INT
1233 && XEXP (SET_SRC (set
), 0) == src
1234 && fixup_match_2 (insn
, dst
, src
,
1235 XEXP (SET_SRC (set
), 1)))
1239 src_class
= reg_preferred_class (REGNO (src
));
1240 dst_class
= reg_preferred_class (REGNO (dst
));
1242 if (! (src_note
= find_reg_note (insn
, REG_DEAD
, src
)))
1244 /* We used to force the copy here like in other cases, but
1245 it produces worse code, as it eliminates no copy
1246 instructions and the copy emitted will be produced by
1247 reload anyway. On patterns with multiple alternatives,
1248 there may be better solution available.
1250 In particular this change produced slower code for numeric
1256 if (! regclass_compatible_p (src_class
, dst_class
))
1266 /* Can not modify an earlier insn to set dst if this insn
1267 uses an old value in the source. */
1268 if (reg_overlap_mentioned_p (dst
, SET_SRC (set
)))
1278 /* If src is set once in a different basic block,
1279 and is set equal to a constant, then do not use
1280 it for this optimization, as this would make it
1281 no longer equivalent to a constant. */
1283 if (reg_is_remote_constant_p (src
, insn
))
1296 "Could fix operand %d of insn %d matching operand %d.\n",
1297 op_no
, INSN_UID (insn
), match_no
);
1299 /* Scan backward to find the first instruction that uses
1300 the input operand. If the operand is set here, then
1301 replace it in both instructions with match_no. */
1303 for (length
= 0, p
= PREV_INSN (insn
); p
; p
= PREV_INSN (p
))
1307 /* ??? We can't scan past the end of a basic block without
1308 updating the register lifetime info
1309 (REG_DEAD/basic_block_live_at_start). */
1310 if (perhaps_ends_bb_p (p
))
1312 else if (! INSN_P (p
))
1317 /* ??? See if all of SRC is set in P. This test is much
1318 more conservative than it needs to be. */
1319 pset
= single_set (p
);
1320 if (pset
&& SET_DEST (pset
) == src
)
1322 /* We use validate_replace_rtx, in case there
1323 are multiple identical source operands. All of
1324 them have to be changed at the same time. */
1325 if (validate_replace_rtx (src
, dst
, insn
))
1327 if (validate_change (p
, &SET_DEST (pset
),
1332 /* Change all source operands back.
1333 This modifies the dst as a side-effect. */
1334 validate_replace_rtx (dst
, src
, insn
);
1335 /* Now make sure the dst is right. */
1336 validate_change (insn
,
1337 recog_data
.operand_loc
[match_no
],
1344 /* We can't make this change if SRC is read or
1345 partially written in P, since we are going to
1346 eliminate SRC. We can't make this change
1347 if DST is mentioned at all in P,
1348 since we are going to change its value. */
1349 if (reg_overlap_mentioned_p (src
, PATTERN (p
))
1350 || reg_mentioned_p (dst
, PATTERN (p
)))
1353 /* If we have passed a call instruction, and the
1354 pseudo-reg DST is not already live across a call,
1355 then don't perform the optimization. */
1359 freq_calls
+= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (p
));
1361 if (REG_N_CALLS_CROSSED (REGNO (dst
)) == 0)
1370 /* Remove the death note for SRC from INSN. */
1371 remove_note (insn
, src_note
);
1372 /* Move the death note for SRC to P if it is used
1374 if (reg_overlap_mentioned_p (src
, PATTERN (p
)))
1376 XEXP (src_note
, 1) = REG_NOTES (p
);
1377 REG_NOTES (p
) = src_note
;
1379 /* If there is a REG_DEAD note for DST on P, then remove
1380 it, because DST is now set there. */
1381 if ((dst_note
= find_reg_note (p
, REG_DEAD
, dst
)))
1382 remove_note (p
, dst_note
);
1384 dstno
= REGNO (dst
);
1385 srcno
= REGNO (src
);
1387 INC_REG_N_SETS (dstno
, 1);
1388 INC_REG_N_SETS (srcno
, -1);
1390 REG_N_CALLS_CROSSED (dstno
) += num_calls
;
1391 REG_N_CALLS_CROSSED (srcno
) -= num_calls
;
1392 REG_FREQ_CALLS_CROSSED (dstno
) += freq_calls
;
1393 REG_FREQ_CALLS_CROSSED (srcno
) -= freq_calls
;
1395 REG_LIVE_LENGTH (dstno
) += length
;
1396 if (REG_LIVE_LENGTH (srcno
) >= 0)
1398 REG_LIVE_LENGTH (srcno
) -= length
;
1399 /* REG_LIVE_LENGTH is only an approximation after
1400 combine if sched is not run, so make sure that we
1401 still have a reasonable value. */
1402 if (REG_LIVE_LENGTH (srcno
) < 2)
1403 REG_LIVE_LENGTH (srcno
) = 2;
1408 "Fixed operand %d of insn %d matching operand %d.\n",
1409 op_no
, INSN_UID (insn
), match_no
);
1415 /* If we weren't able to replace any of the alternatives, try an
1416 alternative approach of copying the source to the destination. */
1417 if (!success
&& copy_src
!= NULL_RTX
)
1418 copy_src_to_dest (insn
, copy_src
, copy_dst
);
1424 free (regno_src_regno
);
1427 free (reg_set_in_bb
);
1428 reg_set_in_bb
= NULL
;
1430 regstat_free_n_sets_and_refs ();
1434 /* Returns nonzero if INSN's pattern has matching constraints for any operand.
1435 Returns 0 if INSN can't be recognized, or if the alternative can't be
1438 Initialize the info in MATCHP based on the constraints. */
1441 find_matches (rtx insn
, struct match
*matchp
)
1443 int likely_spilled
[MAX_RECOG_OPERANDS
];
1445 int any_matches
= 0;
1447 extract_insn (insn
);
1448 if (! constrain_operands (0))
1451 /* Must initialize this before main loop, because the code for
1452 the commutative case may set matches for operands other than
1454 for (op_no
= recog_data
.n_operands
; --op_no
>= 0; )
1455 matchp
->with
[op_no
] = matchp
->commutative
[op_no
] = -1;
1457 for (op_no
= 0; op_no
< recog_data
.n_operands
; op_no
++)
1463 p
= recog_data
.constraints
[op_no
];
1465 likely_spilled
[op_no
] = 0;
1466 matchp
->use
[op_no
] = READ
;
1467 matchp
->early_clobber
[op_no
] = 0;
1469 matchp
->use
[op_no
] = WRITE
;
1471 matchp
->use
[op_no
] = READWRITE
;
1473 for (;*p
&& i
< which_alternative
; p
++)
1477 while ((c
= *p
) != '\0' && c
!= ',')
1486 matchp
->early_clobber
[op_no
] = 1;
1489 matchp
->commutative
[op_no
] = op_no
+ 1;
1490 matchp
->commutative
[op_no
+ 1] = op_no
;
1493 case '0': case '1': case '2': case '3': case '4':
1494 case '5': case '6': case '7': case '8': case '9':
1497 unsigned long match_ul
= strtoul (p
, &end
, 10);
1498 int match
= match_ul
;
1502 if (match
< op_no
&& likely_spilled
[match
])
1504 matchp
->with
[op_no
] = match
;
1506 if (matchp
->commutative
[op_no
] >= 0)
1507 matchp
->with
[matchp
->commutative
[op_no
]] = match
;
1511 case 'a': case 'b': case 'c': case 'd': case 'e': case 'f': case 'h':
1512 case 'j': case 'k': case 'l': case 'p': case 'q': case 't': case 'u':
1513 case 'v': case 'w': case 'x': case 'y': case 'z': case 'A': case 'B':
1514 case 'C': case 'D': case 'W': case 'Y': case 'Z':
1515 if (CLASS_LIKELY_SPILLED_P (REG_CLASS_FROM_CONSTRAINT ((unsigned char) c
, p
) ))
1516 likely_spilled
[op_no
] = 1;
1519 p
+= CONSTRAINT_LEN (c
, p
);
1528 gate_handle_regmove (void)
1530 return (optimize
> 0 && flag_regmove
);
1533 /* Register allocation pre-pass, to reduce number of moves necessary
1534 for two-address machines. */
1536 rest_of_handle_regmove (void)
1538 regmove_optimize (get_insns (), max_reg_num ());
1542 struct rtl_opt_pass pass_regmove
=
1546 "regmove", /* name */
1547 gate_handle_regmove
, /* gate */
1548 rest_of_handle_regmove
, /* execute */
1551 0, /* static_pass_number */
1552 TV_REGMOVE
, /* tv_id */
1553 0, /* properties_required */
1554 0, /* properties_provided */
1555 0, /* properties_destroyed */
1556 0, /* todo_flags_start */
1557 TODO_df_finish
| TODO_verify_rtl_sharing
|
1559 TODO_ggc_collect
/* todo_flags_finish */