1 /* Move registers around to reduce number of move instructions needed.
2 Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3 1999, 2000, 2001, 2002, 2003 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
23 /* This module looks for cases where matching constraints would force
24 an instruction to need a reload, and this reload would be a register
25 to register move. It then attempts to change the registers used by the
26 instruction to avoid the move instruction. */
30 #include "coretypes.h"
32 #include "rtl.h" /* stdio.h must precede rtl.h for FFS. */
34 #include "insn-config.h"
38 #include "hard-reg-set.h"
42 #include "basic-block.h"
48 /* Turn STACK_GROWS_DOWNWARD into a boolean. */
49 #ifdef STACK_GROWS_DOWNWARD
50 #undef STACK_GROWS_DOWNWARD
51 #define STACK_GROWS_DOWNWARD 1
53 #define STACK_GROWS_DOWNWARD 0
56 static int perhaps_ends_bb_p PARAMS ((rtx));
57 static int optimize_reg_copy_1 PARAMS ((rtx, rtx, rtx));
58 static void optimize_reg_copy_2 PARAMS ((rtx, rtx, rtx));
59 static void optimize_reg_copy_3 PARAMS ((rtx, rtx, rtx));
60 static void copy_src_to_dest PARAMS ((rtx, rtx, rtx, int));
61 static int *regmove_bb_head;
64 int with[MAX_RECOG_OPERANDS];
65 enum { READ, WRITE, READWRITE } use[MAX_RECOG_OPERANDS];
66 int commutative[MAX_RECOG_OPERANDS];
67 int early_clobber[MAX_RECOG_OPERANDS];
70 static rtx discover_flags_reg PARAMS ((void));
71 static void mark_flags_life_zones PARAMS ((rtx));
72 static void flags_set_1 PARAMS ((rtx, rtx, void *));
74 static int try_auto_increment PARAMS ((rtx, rtx, rtx, rtx, HOST_WIDE_INT, int));
75 static int find_matches PARAMS ((rtx, struct match *));
76 static void replace_in_call_usage PARAMS ((rtx *, unsigned int, rtx, rtx));
77 static int fixup_match_1 PARAMS ((rtx, rtx, rtx, rtx, rtx, int, int, int, FILE *))
79 static int reg_is_remote_constant_p PARAMS ((rtx, rtx, rtx));
80 static int stable_and_no_regs_but_for_p PARAMS ((rtx, rtx, rtx));
81 static int regclass_compatible_p PARAMS ((int, int));
82 static int replacement_quality PARAMS ((rtx));
83 static int fixup_match_2 PARAMS ((rtx, rtx, rtx, rtx, FILE *));
85 /* Return nonzero if registers with CLASS1 and CLASS2 can be merged without
86 causing too much register allocation problems. */
88 regclass_compatible_p (class0, class1)
91 return (class0 == class1
92 || (reg_class_subset_p (class0, class1)
93 && ! CLASS_LIKELY_SPILLED_P (class0))
94 || (reg_class_subset_p (class1, class0)
95 && ! CLASS_LIKELY_SPILLED_P (class1)));
98 /* INC_INSN is an instruction that adds INCREMENT to REG.
99 Try to fold INC_INSN as a post/pre in/decrement into INSN.
100 Iff INC_INSN_SET is nonzero, inc_insn has a destination different from src.
101 Return nonzero for success. */
103 try_auto_increment (insn, inc_insn, inc_insn_set, reg, increment, pre)
104 rtx reg, insn, inc_insn ,inc_insn_set;
105 HOST_WIDE_INT increment;
108 enum rtx_code inc_code;
110 rtx pset = single_set (insn);
113 /* Can't use the size of SET_SRC, we might have something like
114 (sign_extend:SI (mem:QI ... */
115 rtx use = find_use_as_address (pset, reg, 0);
116 if (use != 0 && use != (rtx) (size_t) 1)
118 int size = GET_MODE_SIZE (GET_MODE (use));
120 || (HAVE_POST_INCREMENT
121 && pre == 0 && (inc_code = POST_INC, increment == size))
122 || (HAVE_PRE_INCREMENT
123 && pre == 1 && (inc_code = PRE_INC, increment == size))
124 || (HAVE_POST_DECREMENT
125 && pre == 0 && (inc_code = POST_DEC, increment == -size))
126 || (HAVE_PRE_DECREMENT
127 && pre == 1 && (inc_code = PRE_DEC, increment == -size))
133 &SET_SRC (inc_insn_set),
134 XEXP (SET_SRC (inc_insn_set), 0), 1);
135 validate_change (insn, &XEXP (use, 0),
136 gen_rtx_fmt_e (inc_code, Pmode, reg), 1);
137 if (apply_change_group ())
139 /* If there is a REG_DEAD note on this insn, we must
140 change this not to REG_UNUSED meaning that the register
141 is set, but the value is dead. Failure to do so will
142 result in a sched1 abort -- when it recomputes lifetime
143 information, the number of REG_DEAD notes will have
145 rtx note = find_reg_note (insn, REG_DEAD, reg);
147 PUT_MODE (note, REG_UNUSED);
150 = gen_rtx_EXPR_LIST (REG_INC,
151 reg, REG_NOTES (insn));
153 delete_insn (inc_insn);
162 /* Determine if the pattern generated by add_optab has a clobber,
163 such as might be issued for a flags hard register. To make the
164 code elsewhere simpler, we handle cc0 in this same framework.
166 Return the register if one was discovered. Return NULL_RTX if
167 if no flags were found. Return pc_rtx if we got confused. */
170 discover_flags_reg ()
173 tmp = gen_rtx_REG (word_mode, 10000);
174 tmp = gen_add3_insn (tmp, tmp, GEN_INT (2));
176 /* If we get something that isn't a simple set, or a
177 [(set ..) (clobber ..)], this whole function will go wrong. */
178 if (GET_CODE (tmp) == SET)
180 else if (GET_CODE (tmp) == PARALLEL)
184 if (XVECLEN (tmp, 0) != 2)
186 tmp = XVECEXP (tmp, 0, 1);
187 if (GET_CODE (tmp) != CLOBBER)
191 /* Don't do anything foolish if the md wanted to clobber a
192 scratch or something. We only care about hard regs.
193 Moreover we don't like the notion of subregs of hard regs. */
194 if (GET_CODE (tmp) == SUBREG
195 && GET_CODE (SUBREG_REG (tmp)) == REG
196 && REGNO (SUBREG_REG (tmp)) < FIRST_PSEUDO_REGISTER)
198 found = (GET_CODE (tmp) == REG && REGNO (tmp) < FIRST_PSEUDO_REGISTER);
200 return (found ? tmp : NULL_RTX);
206 /* It is a tedious task identifying when the flags register is live and
207 when it is safe to optimize. Since we process the instruction stream
208 multiple times, locate and record these live zones by marking the
209 mode of the instructions --
211 QImode is used on the instruction at which the flags becomes live.
213 HImode is used within the range (exclusive) that the flags are
214 live. Thus the user of the flags is not marked.
216 All other instructions are cleared to VOIDmode. */
218 /* Used to communicate with flags_set_1. */
219 static rtx flags_set_1_rtx;
220 static int flags_set_1_set;
223 mark_flags_life_zones (flags)
231 /* If we found a flags register on a cc0 host, bail. */
232 if (flags == NULL_RTX)
234 else if (flags != cc0_rtx)
238 /* Simple cases first: if no flags, clear all modes. If confusing,
239 mark the entire function as being in a flags shadow. */
240 if (flags == NULL_RTX || flags == pc_rtx)
242 enum machine_mode mode = (flags ? HImode : VOIDmode);
244 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
245 PUT_MODE (insn, mode);
253 flags_regno = REGNO (flags);
254 flags_nregs = HARD_REGNO_NREGS (flags_regno, GET_MODE (flags));
256 flags_set_1_rtx = flags;
258 /* Process each basic block. */
259 FOR_EACH_BB_REVERSE (block)
267 /* Look out for the (unlikely) case of flags being live across
268 basic block boundaries. */
273 for (i = 0; i < flags_nregs; ++i)
274 live |= REGNO_REG_SET_P (block->global_live_at_start,
281 /* Process liveness in reverse order of importance --
282 alive, death, birth. This lets more important info
283 overwrite the mode of lesser info. */
288 /* In the cc0 case, death is not marked in reg notes,
289 but is instead the mere use of cc0 when it is alive. */
290 if (live && reg_mentioned_p (cc0_rtx, PATTERN (insn)))
293 /* In the hard reg case, we watch death notes. */
294 if (live && find_regno_note (insn, REG_DEAD, flags_regno))
297 PUT_MODE (insn, (live ? HImode : VOIDmode));
299 /* In either case, birth is denoted simply by it's presence
300 as the destination of a set. */
302 note_stores (PATTERN (insn), flags_set_1, NULL);
306 PUT_MODE (insn, QImode);
310 PUT_MODE (insn, (live ? HImode : VOIDmode));
314 insn = NEXT_INSN (insn);
319 /* A subroutine of mark_flags_life_zones, called through note_stores. */
322 flags_set_1 (x, pat, data)
324 void *data ATTRIBUTE_UNUSED;
326 if (GET_CODE (pat) == SET
327 && reg_overlap_mentioned_p (x, flags_set_1_rtx))
331 static int *regno_src_regno;
333 /* Indicate how good a choice REG (which appears as a source) is to replace
334 a destination register with. The higher the returned value, the better
335 the choice. The main objective is to avoid using a register that is
336 a candidate for tying to a hard register, since the output might in
337 turn be a candidate to be tied to a different hard register. */
339 replacement_quality (reg)
344 /* Bad if this isn't a register at all. */
345 if (GET_CODE (reg) != REG)
348 /* If this register is not meant to get a hard register,
349 it is a poor choice. */
350 if (REG_LIVE_LENGTH (REGNO (reg)) < 0)
353 src_regno = regno_src_regno[REGNO (reg)];
355 /* If it was not copied from another register, it is fine. */
359 /* Copied from a hard register? */
360 if (src_regno < FIRST_PSEUDO_REGISTER)
363 /* Copied from a pseudo register - not as bad as from a hard register,
364 yet still cumbersome, since the register live length will be lengthened
365 when the registers get tied. */
369 /* Return 1 if INSN might end a basic block. */
371 static int perhaps_ends_bb_p (insn)
374 switch (GET_CODE (insn))
378 /* These always end a basic block. */
382 /* A CALL_INSN might be the last insn of a basic block, if it is inside
383 an EH region or if there are nonlocal gotos. Note that this test is
384 very conservative. */
385 if (nonlocal_goto_handler_labels)
389 return can_throw_internal (insn);
393 /* INSN is a copy from SRC to DEST, both registers, and SRC does not die
396 Search forward to see if SRC dies before either it or DEST is modified,
397 but don't scan past the end of a basic block. If so, we can replace SRC
398 with DEST and let SRC die in INSN.
400 This will reduce the number of registers live in that range and may enable
401 DEST to be tied to SRC, thus often saving one register in addition to a
402 register-register copy. */
405 optimize_reg_copy_1 (insn, dest, src)
413 int sregno = REGNO (src);
414 int dregno = REGNO (dest);
416 /* We don't want to mess with hard regs if register classes are small. */
418 || (SMALL_REGISTER_CLASSES
419 && (sregno < FIRST_PSEUDO_REGISTER
420 || dregno < FIRST_PSEUDO_REGISTER))
421 /* We don't see all updates to SP if they are in an auto-inc memory
422 reference, so we must disallow this optimization on them. */
423 || sregno == STACK_POINTER_REGNUM || dregno == STACK_POINTER_REGNUM)
426 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
428 /* ??? We can't scan past the end of a basic block without updating
429 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
430 if (perhaps_ends_bb_p (p))
432 else if (! INSN_P (p))
435 if (reg_set_p (src, p) || reg_set_p (dest, p)
436 /* If SRC is an asm-declared register, it must not be replaced
437 in any asm. Unfortunately, the REG_EXPR tree for the asm
438 variable may be absent in the SRC rtx, so we can't check the
439 actual register declaration easily (the asm operand will have
440 it, though). To avoid complicating the test for a rare case,
441 we just don't perform register replacement for a hard reg
442 mentioned in an asm. */
443 || (sregno < FIRST_PSEUDO_REGISTER
444 && asm_noperands (PATTERN (p)) >= 0
445 && reg_overlap_mentioned_p (src, PATTERN (p)))
446 /* Don't change a USE of a register. */
447 || (GET_CODE (PATTERN (p)) == USE
448 && reg_overlap_mentioned_p (src, XEXP (PATTERN (p), 0))))
451 /* See if all of SRC dies in P. This test is slightly more
452 conservative than it needs to be. */
453 if ((note = find_regno_note (p, REG_DEAD, sregno)) != 0
454 && GET_MODE (XEXP (note, 0)) == GET_MODE (src))
462 /* We can do the optimization. Scan forward from INSN again,
463 replacing regs as we go. Set FAILED if a replacement can't
464 be done. In that case, we can't move the death note for SRC.
465 This should be rare. */
467 /* Set to stop at next insn. */
468 for (q = next_real_insn (insn);
469 q != next_real_insn (p);
470 q = next_real_insn (q))
472 if (reg_overlap_mentioned_p (src, PATTERN (q)))
474 /* If SRC is a hard register, we might miss some
475 overlapping registers with validate_replace_rtx,
476 so we would have to undo it. We can't if DEST is
477 present in the insn, so fail in that combination
479 if (sregno < FIRST_PSEUDO_REGISTER
480 && reg_mentioned_p (dest, PATTERN (q)))
483 /* Replace all uses and make sure that the register
484 isn't still present. */
485 else if (validate_replace_rtx (src, dest, q)
486 && (sregno >= FIRST_PSEUDO_REGISTER
487 || ! reg_overlap_mentioned_p (src,
492 validate_replace_rtx (dest, src, q);
497 /* For SREGNO, count the total number of insns scanned.
498 For DREGNO, count the total number of insns scanned after
499 passing the death note for DREGNO. */
504 /* If the insn in which SRC dies is a CALL_INSN, don't count it
505 as a call that has been crossed. Otherwise, count it. */
506 if (q != p && GET_CODE (q) == CALL_INSN)
508 /* Similarly, total calls for SREGNO, total calls beyond
509 the death note for DREGNO. */
515 /* If DEST dies here, remove the death note and save it for
516 later. Make sure ALL of DEST dies here; again, this is
517 overly conservative. */
519 && (dest_death = find_regno_note (q, REG_DEAD, dregno)) != 0)
521 if (GET_MODE (XEXP (dest_death, 0)) != GET_MODE (dest))
522 failed = 1, dest_death = 0;
524 remove_note (q, dest_death);
530 /* These counters need to be updated if and only if we are
531 going to move the REG_DEAD note. */
532 if (sregno >= FIRST_PSEUDO_REGISTER)
534 if (REG_LIVE_LENGTH (sregno) >= 0)
536 REG_LIVE_LENGTH (sregno) -= s_length;
537 /* REG_LIVE_LENGTH is only an approximation after
538 combine if sched is not run, so make sure that we
539 still have a reasonable value. */
540 if (REG_LIVE_LENGTH (sregno) < 2)
541 REG_LIVE_LENGTH (sregno) = 2;
544 REG_N_CALLS_CROSSED (sregno) -= s_n_calls;
547 /* Move death note of SRC from P to INSN. */
548 remove_note (p, note);
549 XEXP (note, 1) = REG_NOTES (insn);
550 REG_NOTES (insn) = note;
553 /* DEST is also dead if INSN has a REG_UNUSED note for DEST. */
555 && (dest_death = find_regno_note (insn, REG_UNUSED, dregno)))
557 PUT_REG_NOTE_KIND (dest_death, REG_DEAD);
558 remove_note (insn, dest_death);
561 /* Put death note of DEST on P if we saw it die. */
564 XEXP (dest_death, 1) = REG_NOTES (p);
565 REG_NOTES (p) = dest_death;
567 if (dregno >= FIRST_PSEUDO_REGISTER)
569 /* If and only if we are moving the death note for DREGNO,
570 then we need to update its counters. */
571 if (REG_LIVE_LENGTH (dregno) >= 0)
572 REG_LIVE_LENGTH (dregno) += d_length;
573 REG_N_CALLS_CROSSED (dregno) += d_n_calls;
580 /* If SRC is a hard register which is set or killed in some other
581 way, we can't do this optimization. */
582 else if (sregno < FIRST_PSEUDO_REGISTER
583 && dead_or_set_p (p, src))
589 /* INSN is a copy of SRC to DEST, in which SRC dies. See if we now have
590 a sequence of insns that modify DEST followed by an insn that sets
591 SRC to DEST in which DEST dies, with no prior modification of DEST.
592 (There is no need to check if the insns in between actually modify
593 DEST. We should not have cases where DEST is not modified, but
594 the optimization is safe if no such modification is detected.)
595 In that case, we can replace all uses of DEST, starting with INSN and
596 ending with the set of SRC to DEST, with SRC. We do not do this
597 optimization if a CALL_INSN is crossed unless SRC already crosses a
598 call or if DEST dies before the copy back to SRC.
600 It is assumed that DEST and SRC are pseudos; it is too complicated to do
601 this for hard registers since the substitutions we may make might fail. */
604 optimize_reg_copy_2 (insn, dest, src)
611 int sregno = REGNO (src);
612 int dregno = REGNO (dest);
614 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
616 /* ??? We can't scan past the end of a basic block without updating
617 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
618 if (perhaps_ends_bb_p (p))
620 else if (! INSN_P (p))
623 set = single_set (p);
624 if (set && SET_SRC (set) == dest && SET_DEST (set) == src
625 && find_reg_note (p, REG_DEAD, dest))
627 /* We can do the optimization. Scan forward from INSN again,
628 replacing regs as we go. */
630 /* Set to stop at next insn. */
631 for (q = insn; q != NEXT_INSN (p); q = NEXT_INSN (q))
634 if (reg_mentioned_p (dest, PATTERN (q)))
635 PATTERN (q) = replace_rtx (PATTERN (q), dest, src);
638 if (GET_CODE (q) == CALL_INSN)
640 REG_N_CALLS_CROSSED (dregno)--;
641 REG_N_CALLS_CROSSED (sregno)++;
645 remove_note (p, find_reg_note (p, REG_DEAD, dest));
646 REG_N_DEATHS (dregno)--;
647 remove_note (insn, find_reg_note (insn, REG_DEAD, src));
648 REG_N_DEATHS (sregno)--;
652 if (reg_set_p (src, p)
653 || find_reg_note (p, REG_DEAD, dest)
654 || (GET_CODE (p) == CALL_INSN && REG_N_CALLS_CROSSED (sregno) == 0))
658 /* INSN is a ZERO_EXTEND or SIGN_EXTEND of SRC to DEST.
659 Look if SRC dies there, and if it is only set once, by loading
660 it from memory. If so, try to incorporate the zero/sign extension
661 into the memory read, change SRC to the mode of DEST, and alter
662 the remaining accesses to use the appropriate SUBREG. This allows
663 SRC and DEST to be tied later. */
665 optimize_reg_copy_3 (insn, dest, src)
670 rtx src_reg = XEXP (src, 0);
671 int src_no = REGNO (src_reg);
672 int dst_no = REGNO (dest);
674 enum machine_mode old_mode;
676 if (src_no < FIRST_PSEUDO_REGISTER
677 || dst_no < FIRST_PSEUDO_REGISTER
678 || ! find_reg_note (insn, REG_DEAD, src_reg)
679 || REG_N_DEATHS (src_no) != 1
680 || REG_N_SETS (src_no) != 1)
682 for (p = PREV_INSN (insn); p && ! reg_set_p (src_reg, p); p = PREV_INSN (p))
683 /* ??? We can't scan past the end of a basic block without updating
684 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
685 if (perhaps_ends_bb_p (p))
691 if (! (set = single_set (p))
692 || GET_CODE (SET_SRC (set)) != MEM
693 /* If there's a REG_EQUIV note, this must be an insn that loads an
694 argument. Prefer keeping the note over doing this optimization. */
695 || find_reg_note (p, REG_EQUIV, NULL_RTX)
696 || SET_DEST (set) != src_reg)
699 /* Be conservative: although this optimization is also valid for
700 volatile memory references, that could cause trouble in later passes. */
701 if (MEM_VOLATILE_P (SET_SRC (set)))
704 /* Do not use a SUBREG to truncate from one mode to another if truncation
706 if (GET_MODE_BITSIZE (GET_MODE (src_reg)) <= GET_MODE_BITSIZE (GET_MODE (src))
707 && !TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (GET_MODE (src)),
708 GET_MODE_BITSIZE (GET_MODE (src_reg))))
711 old_mode = GET_MODE (src_reg);
712 PUT_MODE (src_reg, GET_MODE (src));
713 XEXP (src, 0) = SET_SRC (set);
715 /* Include this change in the group so that it's easily undone if
716 one of the changes in the group is invalid. */
717 validate_change (p, &SET_SRC (set), src, 1);
719 /* Now walk forward making additional replacements. We want to be able
720 to undo all the changes if a later substitution fails. */
721 subreg = gen_lowpart_SUBREG (old_mode, src_reg);
722 while (p = NEXT_INSN (p), p != insn)
727 /* Make a tenative change. */
728 validate_replace_rtx_group (src_reg, subreg, p);
731 validate_replace_rtx_group (src, src_reg, insn);
733 /* Now see if all the changes are valid. */
734 if (! apply_change_group ())
736 /* One or more changes were no good. Back out everything. */
737 PUT_MODE (src_reg, old_mode);
738 XEXP (src, 0) = src_reg;
742 rtx note = find_reg_note (p, REG_EQUAL, NULL_RTX);
744 remove_note (p, note);
749 /* If we were not able to update the users of src to use dest directly, try
750 instead moving the value to dest directly before the operation. */
753 copy_src_to_dest (insn, src, dest, old_max_uid)
772 /* A REG_LIVE_LENGTH of -1 indicates the register is equivalent to a constant
773 or memory location and is used infrequently; a REG_LIVE_LENGTH of -2 is
774 parameter when there is no frame pointer that is not allocated a register.
775 For now, we just reject them, rather than incrementing the live length. */
777 if (GET_CODE (src) == REG
778 && REG_LIVE_LENGTH (REGNO (src)) > 0
779 && GET_CODE (dest) == REG
780 && !RTX_UNCHANGING_P (dest)
781 && REG_LIVE_LENGTH (REGNO (dest)) > 0
782 && (set = single_set (insn)) != NULL_RTX
783 && !reg_mentioned_p (dest, SET_SRC (set))
784 && GET_MODE (src) == GET_MODE (dest))
786 int old_num_regs = reg_rtx_no;
788 /* Generate the src->dest move. */
790 emit_move_insn (dest, src);
793 /* If this sequence uses new registers, we may not use it. */
794 if (old_num_regs != reg_rtx_no
795 || ! validate_replace_rtx (src, dest, insn))
797 /* We have to restore reg_rtx_no to its old value, lest
798 recompute_reg_usage will try to compute the usage of the
799 new regs, yet reg_n_info is not valid for them. */
800 reg_rtx_no = old_num_regs;
803 emit_insn_before (seq, insn);
804 move_insn = PREV_INSN (insn);
805 p_move_notes = ®_NOTES (move_insn);
806 p_insn_notes = ®_NOTES (insn);
808 /* Move any notes mentioning src to the move instruction. */
809 for (link = REG_NOTES (insn); link != NULL_RTX; link = next)
811 next = XEXP (link, 1);
812 if (XEXP (link, 0) == src)
814 *p_move_notes = link;
815 p_move_notes = &XEXP (link, 1);
819 *p_insn_notes = link;
820 p_insn_notes = &XEXP (link, 1);
824 *p_move_notes = NULL_RTX;
825 *p_insn_notes = NULL_RTX;
827 /* Is the insn the head of a basic block? If so extend it. */
828 insn_uid = INSN_UID (insn);
829 move_uid = INSN_UID (move_insn);
830 if (insn_uid < old_max_uid)
832 bb = regmove_bb_head[insn_uid];
835 BLOCK_HEAD (bb) = move_insn;
836 regmove_bb_head[insn_uid] = -1;
840 /* Update the various register tables. */
841 dest_regno = REGNO (dest);
842 REG_N_SETS (dest_regno) ++;
843 REG_LIVE_LENGTH (dest_regno)++;
844 if (REGNO_FIRST_UID (dest_regno) == insn_uid)
845 REGNO_FIRST_UID (dest_regno) = move_uid;
847 src_regno = REGNO (src);
848 if (! find_reg_note (move_insn, REG_DEAD, src))
849 REG_LIVE_LENGTH (src_regno)++;
851 if (REGNO_FIRST_UID (src_regno) == insn_uid)
852 REGNO_FIRST_UID (src_regno) = move_uid;
854 if (REGNO_LAST_UID (src_regno) == insn_uid)
855 REGNO_LAST_UID (src_regno) = move_uid;
857 if (REGNO_LAST_NOTE_UID (src_regno) == insn_uid)
858 REGNO_LAST_NOTE_UID (src_regno) = move_uid;
863 /* Return whether REG is set in only one location, and is set to a
864 constant, but is set in a different basic block from INSN (an
865 instructions which uses REG). In this case REG is equivalent to a
866 constant, and we don't want to break that equivalence, because that
867 may increase register pressure and make reload harder. If REG is
868 set in the same basic block as INSN, we don't worry about it,
869 because we'll probably need a register anyhow (??? but what if REG
870 is used in a different basic block as well as this one?). FIRST is
871 the first insn in the function. */
874 reg_is_remote_constant_p (reg, insn, first)
881 if (REG_N_SETS (REGNO (reg)) != 1)
884 /* Look for the set. */
885 for (p = LOG_LINKS (insn); p; p = XEXP (p, 1))
889 if (REG_NOTE_KIND (p) != 0)
891 s = single_set (XEXP (p, 0));
893 && GET_CODE (SET_DEST (s)) == REG
894 && REGNO (SET_DEST (s)) == REGNO (reg))
896 /* The register is set in the same basic block. */
901 for (p = first; p && p != insn; p = NEXT_INSN (p))
909 && GET_CODE (SET_DEST (s)) == REG
910 && REGNO (SET_DEST (s)) == REGNO (reg))
912 /* This is the instruction which sets REG. If there is a
913 REG_EQUAL note, then REG is equivalent to a constant. */
914 if (find_reg_note (p, REG_EQUAL, NULL_RTX))
923 /* INSN is adding a CONST_INT to a REG. We search backwards looking for
924 another add immediate instruction with the same source and dest registers,
925 and if we find one, we change INSN to an increment, and return 1. If
926 no changes are made, we return 0.
929 (set (reg100) (plus reg1 offset1))
931 (set (reg100) (plus reg1 offset2))
933 (set (reg100) (plus reg1 offset1))
935 (set (reg100) (plus reg100 offset2-offset1)) */
937 /* ??? What does this comment mean? */
938 /* cse disrupts preincrement / postdecrement sequences when it finds a
939 hard register as ultimate source, like the frame pointer. */
942 fixup_match_2 (insn, dst, src, offset, regmove_dump_file)
943 rtx insn, dst, src, offset;
944 FILE *regmove_dump_file;
946 rtx p, dst_death = 0;
947 int length, num_calls = 0;
949 /* If SRC dies in INSN, we'd have to move the death note. This is
950 considered to be very unlikely, so we just skip the optimization
952 if (find_regno_note (insn, REG_DEAD, REGNO (src)))
955 /* Scan backward to find the first instruction that sets DST. */
957 for (length = 0, p = PREV_INSN (insn); p; p = PREV_INSN (p))
961 /* ??? We can't scan past the end of a basic block without updating
962 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
963 if (perhaps_ends_bb_p (p))
965 else if (! INSN_P (p))
968 if (find_regno_note (p, REG_DEAD, REGNO (dst)))
973 pset = single_set (p);
974 if (pset && SET_DEST (pset) == dst
975 && GET_CODE (SET_SRC (pset)) == PLUS
976 && XEXP (SET_SRC (pset), 0) == src
977 && GET_CODE (XEXP (SET_SRC (pset), 1)) == CONST_INT)
979 HOST_WIDE_INT newconst
980 = INTVAL (offset) - INTVAL (XEXP (SET_SRC (pset), 1));
981 rtx add = gen_add3_insn (dst, dst, GEN_INT (newconst));
983 if (add && validate_change (insn, &PATTERN (insn), add, 0))
985 /* Remove the death note for DST from DST_DEATH. */
988 remove_death (REGNO (dst), dst_death);
989 REG_LIVE_LENGTH (REGNO (dst)) += length;
990 REG_N_CALLS_CROSSED (REGNO (dst)) += num_calls;
993 if (regmove_dump_file)
994 fprintf (regmove_dump_file,
995 "Fixed operand of insn %d.\n",
999 for (p = PREV_INSN (insn); p; p = PREV_INSN (p))
1001 if (GET_CODE (p) == CODE_LABEL
1002 || GET_CODE (p) == JUMP_INSN)
1006 if (reg_overlap_mentioned_p (dst, PATTERN (p)))
1008 if (try_auto_increment (p, insn, 0, dst, newconst, 0))
1013 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
1015 if (GET_CODE (p) == CODE_LABEL
1016 || GET_CODE (p) == JUMP_INSN)
1020 if (reg_overlap_mentioned_p (dst, PATTERN (p)))
1022 try_auto_increment (p, insn, 0, dst, newconst, 1);
1031 if (reg_set_p (dst, PATTERN (p)))
1034 /* If we have passed a call instruction, and the
1035 pseudo-reg SRC is not already live across a call,
1036 then don't perform the optimization. */
1037 /* reg_set_p is overly conservative for CALL_INSNS, thinks that all
1038 hard regs are clobbered. Thus, we only use it for src for
1040 if (GET_CODE (p) == CALL_INSN)
1045 if (REG_N_CALLS_CROSSED (REGNO (src)) == 0)
1048 if (call_used_regs [REGNO (dst)]
1049 || find_reg_fusage (p, CLOBBER, dst))
1052 else if (reg_set_p (src, PATTERN (p)))
1059 /* Main entry for the register move optimization.
1060 F is the first instruction.
1061 NREGS is one plus the highest pseudo-reg number used in the instruction.
1062 REGMOVE_DUMP_FILE is a stream for output of a trace of actions taken
1063 (or 0 if none should be output). */
1066 regmove_optimize (f, nregs, regmove_dump_file)
1069 FILE *regmove_dump_file;
1071 int old_max_uid = get_max_uid ();
1076 rtx copy_src, copy_dst;
1079 /* ??? Hack. Regmove doesn't examine the CFG, and gets mightily
1080 confused by non-call exceptions ending blocks. */
1081 if (flag_non_call_exceptions)
1084 /* Find out where a potential flags register is live, and so that we
1085 can suppress some optimizations in those zones. */
1086 mark_flags_life_zones (discover_flags_reg ());
1088 regno_src_regno = (int *) xmalloc (sizeof *regno_src_regno * nregs);
1089 for (i = nregs; --i >= 0; ) regno_src_regno[i] = -1;
1091 regmove_bb_head = (int *) xmalloc (sizeof (int) * (old_max_uid + 1));
1092 for (i = old_max_uid; i >= 0; i--) regmove_bb_head[i] = -1;
1094 regmove_bb_head[INSN_UID (bb->head)] = bb->index;
1096 /* A forward/backward pass. Replace output operands with input operands. */
1098 for (pass = 0; pass <= 2; pass++)
1100 if (! flag_regmove && pass >= flag_expensive_optimizations)
1103 if (regmove_dump_file)
1104 fprintf (regmove_dump_file, "Starting %s pass...\n",
1105 pass ? "backward" : "forward");
1107 for (insn = pass ? get_last_insn () : f; insn;
1108 insn = pass ? PREV_INSN (insn) : NEXT_INSN (insn))
1111 int op_no, match_no;
1113 set = single_set (insn);
1117 if (flag_expensive_optimizations && ! pass
1118 && (GET_CODE (SET_SRC (set)) == SIGN_EXTEND
1119 || GET_CODE (SET_SRC (set)) == ZERO_EXTEND)
1120 && GET_CODE (XEXP (SET_SRC (set), 0)) == REG
1121 && GET_CODE (SET_DEST (set)) == REG)
1122 optimize_reg_copy_3 (insn, SET_DEST (set), SET_SRC (set));
1124 if (flag_expensive_optimizations && ! pass
1125 && GET_CODE (SET_SRC (set)) == REG
1126 && GET_CODE (SET_DEST (set)) == REG)
1128 /* If this is a register-register copy where SRC is not dead,
1129 see if we can optimize it. If this optimization succeeds,
1130 it will become a copy where SRC is dead. */
1131 if ((find_reg_note (insn, REG_DEAD, SET_SRC (set))
1132 || optimize_reg_copy_1 (insn, SET_DEST (set), SET_SRC (set)))
1133 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
1135 /* Similarly for a pseudo-pseudo copy when SRC is dead. */
1136 if (REGNO (SET_SRC (set)) >= FIRST_PSEUDO_REGISTER)
1137 optimize_reg_copy_2 (insn, SET_DEST (set), SET_SRC (set));
1138 if (regno_src_regno[REGNO (SET_DEST (set))] < 0
1139 && SET_SRC (set) != SET_DEST (set))
1141 int srcregno = REGNO (SET_SRC (set));
1142 if (regno_src_regno[srcregno] >= 0)
1143 srcregno = regno_src_regno[srcregno];
1144 regno_src_regno[REGNO (SET_DEST (set))] = srcregno;
1151 if (! find_matches (insn, &match))
1154 /* Now scan through the operands looking for a source operand
1155 which is supposed to match the destination operand.
1156 Then scan forward for an instruction which uses the dest
1158 If it dies there, then replace the dest in both operands with
1159 the source operand. */
1161 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1163 rtx src, dst, src_subreg;
1164 enum reg_class src_class, dst_class;
1166 match_no = match.with[op_no];
1168 /* Nothing to do if the two operands aren't supposed to match. */
1172 src = recog_data.operand[op_no];
1173 dst = recog_data.operand[match_no];
1175 if (GET_CODE (src) != REG)
1179 if (GET_CODE (dst) == SUBREG
1180 && GET_MODE_SIZE (GET_MODE (dst))
1181 >= GET_MODE_SIZE (GET_MODE (SUBREG_REG (dst))))
1184 = gen_rtx_SUBREG (GET_MODE (SUBREG_REG (dst)),
1185 src, SUBREG_BYTE (dst));
1186 dst = SUBREG_REG (dst);
1188 if (GET_CODE (dst) != REG
1189 || REGNO (dst) < FIRST_PSEUDO_REGISTER)
1192 if (REGNO (src) < FIRST_PSEUDO_REGISTER)
1194 if (match.commutative[op_no] < op_no)
1195 regno_src_regno[REGNO (dst)] = REGNO (src);
1199 if (REG_LIVE_LENGTH (REGNO (src)) < 0)
1202 /* op_no/src must be a read-only operand, and
1203 match_operand/dst must be a write-only operand. */
1204 if (match.use[op_no] != READ
1205 || match.use[match_no] != WRITE)
1208 if (match.early_clobber[match_no]
1209 && count_occurrences (PATTERN (insn), src, 0) > 1)
1212 /* Make sure match_operand is the destination. */
1213 if (recog_data.operand[match_no] != SET_DEST (set))
1216 /* If the operands already match, then there is nothing to do. */
1217 if (operands_match_p (src, dst))
1220 /* But in the commutative case, we might find a better match. */
1221 if (match.commutative[op_no] >= 0)
1223 rtx comm = recog_data.operand[match.commutative[op_no]];
1224 if (operands_match_p (comm, dst)
1225 && (replacement_quality (comm)
1226 >= replacement_quality (src)))
1230 src_class = reg_preferred_class (REGNO (src));
1231 dst_class = reg_preferred_class (REGNO (dst));
1232 if (! regclass_compatible_p (src_class, dst_class))
1235 if (GET_MODE (src) != GET_MODE (dst))
1238 if (fixup_match_1 (insn, set, src, src_subreg, dst, pass,
1246 /* A backward pass. Replace input operands with output operands. */
1248 if (regmove_dump_file)
1249 fprintf (regmove_dump_file, "Starting backward pass...\n");
1251 for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
1255 int op_no, match_no;
1258 if (! find_matches (insn, &match))
1261 /* Now scan through the operands looking for a destination operand
1262 which is supposed to match a source operand.
1263 Then scan backward for an instruction which sets the source
1264 operand. If safe, then replace the source operand with the
1265 dest operand in both instructions. */
1267 copy_src = NULL_RTX;
1268 copy_dst = NULL_RTX;
1269 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1271 rtx set, p, src, dst;
1272 rtx src_note, dst_note;
1274 enum reg_class src_class, dst_class;
1277 match_no = match.with[op_no];
1279 /* Nothing to do if the two operands aren't supposed to match. */
1283 dst = recog_data.operand[match_no];
1284 src = recog_data.operand[op_no];
1286 if (GET_CODE (src) != REG)
1289 if (GET_CODE (dst) != REG
1290 || REGNO (dst) < FIRST_PSEUDO_REGISTER
1291 || REG_LIVE_LENGTH (REGNO (dst)) < 0
1292 || RTX_UNCHANGING_P (dst)
1293 || GET_MODE (src) != GET_MODE (dst))
1296 /* If the operands already match, then there is nothing to do. */
1297 if (operands_match_p (src, dst))
1300 if (match.commutative[op_no] >= 0)
1302 rtx comm = recog_data.operand[match.commutative[op_no]];
1303 if (operands_match_p (comm, dst))
1307 set = single_set (insn);
1311 /* Note that single_set ignores parts of a parallel set for
1312 which one of the destinations is REG_UNUSED. We can't
1313 handle that here, since we can wind up rewriting things
1314 such that a single register is set twice within a single
1316 if (reg_set_p (src, insn))
1319 /* match_no/dst must be a write-only operand, and
1320 operand_operand/src must be a read-only operand. */
1321 if (match.use[op_no] != READ
1322 || match.use[match_no] != WRITE)
1325 if (match.early_clobber[match_no]
1326 && count_occurrences (PATTERN (insn), src, 0) > 1)
1329 /* Make sure match_no is the destination. */
1330 if (recog_data.operand[match_no] != SET_DEST (set))
1333 if (REGNO (src) < FIRST_PSEUDO_REGISTER)
1335 if (GET_CODE (SET_SRC (set)) == PLUS
1336 && GET_CODE (XEXP (SET_SRC (set), 1)) == CONST_INT
1337 && XEXP (SET_SRC (set), 0) == src
1338 && fixup_match_2 (insn, dst, src,
1339 XEXP (SET_SRC (set), 1),
1344 src_class = reg_preferred_class (REGNO (src));
1345 dst_class = reg_preferred_class (REGNO (dst));
1347 if (! (src_note = find_reg_note (insn, REG_DEAD, src)))
1349 /* We used to force the copy here like in other cases, but
1350 it produces worse code, as it eliminates no copy
1351 instructions and the copy emitted will be produced by
1352 reload anyway. On patterns with multiple alternatives,
1353 there may be better solution available.
1355 In particular this change produced slower code for numeric
1361 if (! regclass_compatible_p (src_class, dst_class))
1371 /* Can not modify an earlier insn to set dst if this insn
1372 uses an old value in the source. */
1373 if (reg_overlap_mentioned_p (dst, SET_SRC (set)))
1383 /* If src is set once in a different basic block,
1384 and is set equal to a constant, then do not use
1385 it for this optimization, as this would make it
1386 no longer equivalent to a constant. */
1388 if (reg_is_remote_constant_p (src, insn, f))
1399 if (regmove_dump_file)
1400 fprintf (regmove_dump_file,
1401 "Could fix operand %d of insn %d matching operand %d.\n",
1402 op_no, INSN_UID (insn), match_no);
1404 /* Scan backward to find the first instruction that uses
1405 the input operand. If the operand is set here, then
1406 replace it in both instructions with match_no. */
1408 for (length = 0, p = PREV_INSN (insn); p; p = PREV_INSN (p))
1412 /* ??? We can't scan past the end of a basic block without
1413 updating the register lifetime info
1414 (REG_DEAD/basic_block_live_at_start). */
1415 if (perhaps_ends_bb_p (p))
1417 else if (! INSN_P (p))
1422 /* ??? See if all of SRC is set in P. This test is much
1423 more conservative than it needs to be. */
1424 pset = single_set (p);
1425 if (pset && SET_DEST (pset) == src)
1427 /* We use validate_replace_rtx, in case there
1428 are multiple identical source operands. All of
1429 them have to be changed at the same time. */
1430 if (validate_replace_rtx (src, dst, insn))
1432 if (validate_change (p, &SET_DEST (pset),
1437 /* Change all source operands back.
1438 This modifies the dst as a side-effect. */
1439 validate_replace_rtx (dst, src, insn);
1440 /* Now make sure the dst is right. */
1441 validate_change (insn,
1442 recog_data.operand_loc[match_no],
1449 if (reg_overlap_mentioned_p (src, PATTERN (p))
1450 || reg_overlap_mentioned_p (dst, PATTERN (p)))
1453 /* If we have passed a call instruction, and the
1454 pseudo-reg DST is not already live across a call,
1455 then don't perform the optimization. */
1456 if (GET_CODE (p) == CALL_INSN)
1460 if (REG_N_CALLS_CROSSED (REGNO (dst)) == 0)
1469 /* Remove the death note for SRC from INSN. */
1470 remove_note (insn, src_note);
1471 /* Move the death note for SRC to P if it is used
1473 if (reg_overlap_mentioned_p (src, PATTERN (p)))
1475 XEXP (src_note, 1) = REG_NOTES (p);
1476 REG_NOTES (p) = src_note;
1478 /* If there is a REG_DEAD note for DST on P, then remove
1479 it, because DST is now set there. */
1480 if ((dst_note = find_reg_note (p, REG_DEAD, dst)))
1481 remove_note (p, dst_note);
1483 dstno = REGNO (dst);
1484 srcno = REGNO (src);
1486 REG_N_SETS (dstno)++;
1487 REG_N_SETS (srcno)--;
1489 REG_N_CALLS_CROSSED (dstno) += num_calls;
1490 REG_N_CALLS_CROSSED (srcno) -= num_calls;
1492 REG_LIVE_LENGTH (dstno) += length;
1493 if (REG_LIVE_LENGTH (srcno) >= 0)
1495 REG_LIVE_LENGTH (srcno) -= length;
1496 /* REG_LIVE_LENGTH is only an approximation after
1497 combine if sched is not run, so make sure that we
1498 still have a reasonable value. */
1499 if (REG_LIVE_LENGTH (srcno) < 2)
1500 REG_LIVE_LENGTH (srcno) = 2;
1503 if (regmove_dump_file)
1504 fprintf (regmove_dump_file,
1505 "Fixed operand %d of insn %d matching operand %d.\n",
1506 op_no, INSN_UID (insn), match_no);
1512 /* If we weren't able to replace any of the alternatives, try an
1513 alternative approach of copying the source to the destination. */
1514 if (!success && copy_src != NULL_RTX)
1515 copy_src_to_dest (insn, copy_src, copy_dst, old_max_uid);
1520 /* In fixup_match_1, some insns may have been inserted after basic block
1521 ends. Fix that here. */
1526 rtx next = NEXT_INSN (new);
1527 while (next != 0 && INSN_UID (next) >= old_max_uid
1528 && (bb->next_bb == EXIT_BLOCK_PTR || bb->next_bb->head != next))
1529 new = next, next = NEXT_INSN (new);
1535 free (regno_src_regno);
1536 free (regmove_bb_head);
1539 /* Returns nonzero if INSN's pattern has matching constraints for any operand.
1540 Returns 0 if INSN can't be recognized, or if the alternative can't be
1543 Initialize the info in MATCHP based on the constraints. */
1546 find_matches (insn, matchp)
1548 struct match *matchp;
1550 int likely_spilled[MAX_RECOG_OPERANDS];
1552 int any_matches = 0;
1554 extract_insn (insn);
1555 if (! constrain_operands (0))
1558 /* Must initialize this before main loop, because the code for
1559 the commutative case may set matches for operands other than
1561 for (op_no = recog_data.n_operands; --op_no >= 0; )
1562 matchp->with[op_no] = matchp->commutative[op_no] = -1;
1564 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1570 p = recog_data.constraints[op_no];
1572 likely_spilled[op_no] = 0;
1573 matchp->use[op_no] = READ;
1574 matchp->early_clobber[op_no] = 0;
1576 matchp->use[op_no] = WRITE;
1578 matchp->use[op_no] = READWRITE;
1580 for (;*p && i < which_alternative; p++)
1584 while ((c = *p) != '\0' && c != ',')
1593 matchp->early_clobber[op_no] = 1;
1596 matchp->commutative[op_no] = op_no + 1;
1597 matchp->commutative[op_no + 1] = op_no;
1600 case '0': case '1': case '2': case '3': case '4':
1601 case '5': case '6': case '7': case '8': case '9':
1604 unsigned long match_ul = strtoul (p, &end, 10);
1605 int match = match_ul;
1609 if (match < op_no && likely_spilled[match])
1611 matchp->with[op_no] = match;
1613 if (matchp->commutative[op_no] >= 0)
1614 matchp->with[matchp->commutative[op_no]] = match;
1618 case 'a': case 'b': case 'c': case 'd': case 'e': case 'f': case 'h':
1619 case 'j': case 'k': case 'l': case 'p': case 'q': case 't': case 'u':
1620 case 'v': case 'w': case 'x': case 'y': case 'z': case 'A': case 'B':
1621 case 'C': case 'D': case 'W': case 'Y': case 'Z':
1622 if (CLASS_LIKELY_SPILLED_P (REG_CLASS_FROM_CONSTRAINT ((unsigned char) c, p) ))
1623 likely_spilled[op_no] = 1;
1626 p += CONSTRAINT_LEN (c, p);
1632 /* Try to replace all occurrences of DST_REG with SRC in LOC, that is
1633 assumed to be in INSN. */
1636 replace_in_call_usage (loc, dst_reg, src, insn)
1638 unsigned int dst_reg;
1650 code = GET_CODE (x);
1653 if (REGNO (x) != dst_reg)
1656 validate_change (insn, loc, src, 1);
1661 /* Process each of our operands recursively. */
1662 fmt = GET_RTX_FORMAT (code);
1663 for (i = 0; i < GET_RTX_LENGTH (code); i++, fmt++)
1665 replace_in_call_usage (&XEXP (x, i), dst_reg, src, insn);
1666 else if (*fmt == 'E')
1667 for (j = 0; j < XVECLEN (x, i); j++)
1668 replace_in_call_usage (& XVECEXP (x, i, j), dst_reg, src, insn);
1671 /* Try to replace output operand DST in SET, with input operand SRC. SET is
1672 the only set in INSN. INSN has just been recognized and constrained.
1673 SRC is operand number OPERAND_NUMBER in INSN.
1674 DST is operand number MATCH_NUMBER in INSN.
1675 If BACKWARD is nonzero, we have been called in a backward pass.
1676 Return nonzero for success. */
1679 fixup_match_1 (insn, set, src, src_subreg, dst, backward, operand_number,
1680 match_number, regmove_dump_file)
1681 rtx insn, set, src, src_subreg, dst;
1682 int backward, operand_number, match_number;
1683 FILE *regmove_dump_file;
1686 rtx post_inc = 0, post_inc_set = 0, search_end = 0;
1688 int num_calls = 0, s_num_calls = 0;
1689 enum rtx_code code = NOTE;
1690 HOST_WIDE_INT insn_const = 0, newconst = 0;
1691 rtx overlap = 0; /* need to move insn ? */
1692 rtx src_note = find_reg_note (insn, REG_DEAD, src), dst_note = NULL_RTX;
1693 int length, s_length;
1695 /* If SRC is marked as unchanging, we may not change it.
1696 ??? Maybe we could get better code by removing the unchanging bit
1697 instead, and changing it back if we don't succeed? */
1698 if (RTX_UNCHANGING_P (src))
1703 /* Look for (set (regX) (op regA constX))
1704 (set (regY) (op regA constY))
1706 (set (regA) (op regA constX)).
1707 (set (regY) (op regA constY-constX)).
1708 This works for add and shift operations, if
1709 regA is dead after or set by the second insn. */
1711 code = GET_CODE (SET_SRC (set));
1712 if ((code == PLUS || code == LSHIFTRT
1713 || code == ASHIFT || code == ASHIFTRT)
1714 && XEXP (SET_SRC (set), 0) == src
1715 && GET_CODE (XEXP (SET_SRC (set), 1)) == CONST_INT)
1716 insn_const = INTVAL (XEXP (SET_SRC (set), 1));
1717 else if (! stable_and_no_regs_but_for_p (SET_SRC (set), src, dst))
1720 /* We might find a src_note while scanning. */
1724 if (regmove_dump_file)
1725 fprintf (regmove_dump_file,
1726 "Could fix operand %d of insn %d matching operand %d.\n",
1727 operand_number, INSN_UID (insn), match_number);
1729 /* If SRC is equivalent to a constant set in a different basic block,
1730 then do not use it for this optimization. We want the equivalence
1731 so that if we have to reload this register, we can reload the
1732 constant, rather than extending the lifespan of the register. */
1733 if (reg_is_remote_constant_p (src, insn, get_insns ()))
1736 /* Scan forward to find the next instruction that
1737 uses the output operand. If the operand dies here,
1738 then replace it in both instructions with
1741 for (length = s_length = 0, p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
1743 if (GET_CODE (p) == CALL_INSN)
1744 replace_in_call_usage (& CALL_INSN_FUNCTION_USAGE (p),
1745 REGNO (dst), src, p);
1747 /* ??? We can't scan past the end of a basic block without updating
1748 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
1749 if (perhaps_ends_bb_p (p))
1751 else if (! INSN_P (p))
1758 if (reg_set_p (src, p) || reg_set_p (dst, p)
1759 || (GET_CODE (PATTERN (p)) == USE
1760 && reg_overlap_mentioned_p (src, XEXP (PATTERN (p), 0))))
1763 /* See if all of DST dies in P. This test is
1764 slightly more conservative than it needs to be. */
1765 if ((dst_note = find_regno_note (p, REG_DEAD, REGNO (dst)))
1766 && (GET_MODE (XEXP (dst_note, 0)) == GET_MODE (dst)))
1768 /* If we would be moving INSN, check that we won't move it
1769 into the shadow of a live a live flags register. */
1770 /* ??? We only try to move it in front of P, although
1771 we could move it anywhere between OVERLAP and P. */
1772 if (overlap && GET_MODE (PREV_INSN (p)) != VOIDmode)
1778 rtx set2 = NULL_RTX;
1780 /* If an optimization is done, the value of SRC while P
1781 is executed will be changed. Check that this is OK. */
1782 if (reg_overlap_mentioned_p (src, PATTERN (p)))
1784 for (q = p; q; q = NEXT_INSN (q))
1786 /* ??? We can't scan past the end of a basic block without
1787 updating the register lifetime info
1788 (REG_DEAD/basic_block_live_at_start). */
1789 if (perhaps_ends_bb_p (q))
1794 else if (! INSN_P (q))
1796 else if (reg_overlap_mentioned_p (src, PATTERN (q))
1797 || reg_set_p (src, q))
1801 set2 = single_set (q);
1802 if (! q || ! set2 || GET_CODE (SET_SRC (set2)) != code
1803 || XEXP (SET_SRC (set2), 0) != src
1804 || GET_CODE (XEXP (SET_SRC (set2), 1)) != CONST_INT
1805 || (SET_DEST (set2) != src
1806 && ! find_reg_note (q, REG_DEAD, src)))
1808 /* If this is a PLUS, we can still save a register by doing
1811 src -= insn_const; .
1812 This also gives opportunities for subsequent
1813 optimizations in the backward pass, so do it there. */
1814 if (code == PLUS && backward
1815 /* Don't do this if we can likely tie DST to SET_DEST
1816 of P later; we can't do this tying here if we got a
1818 && ! (dst_note && ! REG_N_CALLS_CROSSED (REGNO (dst))
1820 && GET_CODE (SET_DEST (single_set (p))) == REG
1821 && (REGNO (SET_DEST (single_set (p)))
1822 < FIRST_PSEUDO_REGISTER))
1823 /* We may only emit an insn directly after P if we
1824 are not in the shadow of a live flags register. */
1825 && GET_MODE (p) == VOIDmode)
1830 newconst = -insn_const;
1838 newconst = INTVAL (XEXP (SET_SRC (set2), 1)) - insn_const;
1839 /* Reject out of range shifts. */
1842 || ((unsigned HOST_WIDE_INT) newconst
1843 >= (GET_MODE_BITSIZE (GET_MODE
1844 (SET_SRC (set2)))))))
1849 if (SET_DEST (set2) != src)
1850 post_inc_set = set2;
1853 /* We use 1 as last argument to validate_change so that all
1854 changes are accepted or rejected together by apply_change_group
1855 when it is called by validate_replace_rtx . */
1856 validate_change (q, &XEXP (SET_SRC (set2), 1),
1857 GEN_INT (newconst), 1);
1859 validate_change (insn, recog_data.operand_loc[match_number], src, 1);
1860 if (validate_replace_rtx (dst, src_subreg, p))
1865 if (reg_overlap_mentioned_p (dst, PATTERN (p)))
1867 if (! src_note && reg_overlap_mentioned_p (src, PATTERN (p)))
1869 /* INSN was already checked to be movable wrt. the registers that it
1870 sets / uses when we found no REG_DEAD note for src on it, but it
1871 still might clobber the flags register. We'll have to check that
1872 we won't insert it into the shadow of a live flags register when
1873 we finally know where we are to move it. */
1875 src_note = find_reg_note (p, REG_DEAD, src);
1878 /* If we have passed a call instruction, and the pseudo-reg SRC is not
1879 already live across a call, then don't perform the optimization. */
1880 if (GET_CODE (p) == CALL_INSN)
1882 if (REG_N_CALLS_CROSSED (REGNO (src)) == 0)
1896 /* Remove the death note for DST from P. */
1897 remove_note (p, dst_note);
1900 post_inc = emit_insn_after (copy_rtx (PATTERN (insn)), p);
1901 if ((HAVE_PRE_INCREMENT || HAVE_PRE_DECREMENT)
1903 && try_auto_increment (search_end, post_inc, 0, src, newconst, 1))
1905 validate_change (insn, &XEXP (SET_SRC (set), 1), GEN_INT (insn_const), 0);
1906 REG_N_SETS (REGNO (src))++;
1907 REG_LIVE_LENGTH (REGNO (src))++;
1911 /* The lifetime of src and dest overlap,
1912 but we can change this by moving insn. */
1913 rtx pat = PATTERN (insn);
1915 remove_note (overlap, src_note);
1916 if ((HAVE_POST_INCREMENT || HAVE_POST_DECREMENT)
1918 && try_auto_increment (overlap, insn, 0, src, insn_const, 0))
1922 rtx notes = REG_NOTES (insn);
1924 emit_insn_after_with_line_notes (pat, PREV_INSN (p), insn);
1926 /* emit_insn_after_with_line_notes has no
1927 return value, so search for the new insn. */
1929 while (! INSN_P (insn) || PATTERN (insn) != pat)
1930 insn = PREV_INSN (insn);
1932 REG_NOTES (insn) = notes;
1935 /* Sometimes we'd generate src = const; src += n;
1936 if so, replace the instruction that set src
1937 in the first place. */
1939 if (! overlap && (code == PLUS || code == MINUS))
1941 rtx note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
1942 rtx q, set2 = NULL_RTX;
1943 int num_calls2 = 0, s_length2 = 0;
1945 if (note && CONSTANT_P (XEXP (note, 0)))
1947 for (q = PREV_INSN (insn); q; q = PREV_INSN (q))
1949 /* ??? We can't scan past the end of a basic block without
1950 updating the register lifetime info
1951 (REG_DEAD/basic_block_live_at_start). */
1952 if (perhaps_ends_bb_p (q))
1957 else if (! INSN_P (q))
1961 if (reg_set_p (src, q))
1963 set2 = single_set (q);
1966 if (reg_overlap_mentioned_p (src, PATTERN (q)))
1971 if (GET_CODE (p) == CALL_INSN)
1974 if (q && set2 && SET_DEST (set2) == src && CONSTANT_P (SET_SRC (set2))
1975 && validate_change (insn, &SET_SRC (set), XEXP (note, 0), 0))
1978 REG_N_SETS (REGNO (src))--;
1979 REG_N_CALLS_CROSSED (REGNO (src)) -= num_calls2;
1980 REG_LIVE_LENGTH (REGNO (src)) -= s_length2;
1986 if ((HAVE_PRE_INCREMENT || HAVE_PRE_DECREMENT)
1987 && (code == PLUS || code == MINUS) && insn_const
1988 && try_auto_increment (p, insn, 0, src, insn_const, 1))
1990 else if ((HAVE_POST_INCREMENT || HAVE_POST_DECREMENT)
1992 && try_auto_increment (p, post_inc, post_inc_set, src, newconst, 0))
1994 /* If post_inc still prevails, try to find an
1995 insn where it can be used as a pre-in/decrement.
1996 If code is MINUS, this was already tried. */
1997 if (post_inc && code == PLUS
1998 /* Check that newconst is likely to be usable
1999 in a pre-in/decrement before starting the search. */
2000 && ((HAVE_PRE_INCREMENT && newconst > 0 && newconst <= MOVE_MAX)
2001 || (HAVE_PRE_DECREMENT && newconst < 0 && newconst >= -MOVE_MAX))
2002 && exact_log2 (newconst))
2006 inc_dest = post_inc_set ? SET_DEST (post_inc_set) : src;
2007 for (q = post_inc; (q = NEXT_INSN (q)); )
2009 /* ??? We can't scan past the end of a basic block without updating
2010 the register lifetime info
2011 (REG_DEAD/basic_block_live_at_start). */
2012 if (perhaps_ends_bb_p (q))
2014 else if (! INSN_P (q))
2016 else if (src != inc_dest
2017 && (reg_overlap_mentioned_p (src, PATTERN (q))
2018 || reg_set_p (src, q)))
2020 else if (reg_set_p (inc_dest, q))
2022 else if (reg_overlap_mentioned_p (inc_dest, PATTERN (q)))
2024 try_auto_increment (q, post_inc,
2025 post_inc_set, inc_dest, newconst, 1);
2031 /* Move the death note for DST to INSN if it is used
2033 if (reg_overlap_mentioned_p (dst, PATTERN (insn)))
2035 XEXP (dst_note, 1) = REG_NOTES (insn);
2036 REG_NOTES (insn) = dst_note;
2041 /* Move the death note for SRC from INSN to P. */
2043 remove_note (insn, src_note);
2044 XEXP (src_note, 1) = REG_NOTES (p);
2045 REG_NOTES (p) = src_note;
2047 REG_N_CALLS_CROSSED (REGNO (src)) += s_num_calls;
2050 REG_N_SETS (REGNO (src))++;
2051 REG_N_SETS (REGNO (dst))--;
2053 REG_N_CALLS_CROSSED (REGNO (dst)) -= num_calls;
2055 REG_LIVE_LENGTH (REGNO (src)) += s_length;
2056 if (REG_LIVE_LENGTH (REGNO (dst)) >= 0)
2058 REG_LIVE_LENGTH (REGNO (dst)) -= length;
2059 /* REG_LIVE_LENGTH is only an approximation after
2060 combine if sched is not run, so make sure that we
2061 still have a reasonable value. */
2062 if (REG_LIVE_LENGTH (REGNO (dst)) < 2)
2063 REG_LIVE_LENGTH (REGNO (dst)) = 2;
2065 if (regmove_dump_file)
2066 fprintf (regmove_dump_file,
2067 "Fixed operand %d of insn %d matching operand %d.\n",
2068 operand_number, INSN_UID (insn), match_number);
2073 /* return nonzero if X is stable and mentions no regsiters but for
2074 mentioning SRC or mentioning / changing DST . If in doubt, presume
2076 The rationale is that we want to check if we can move an insn easily
2077 while just paying attention to SRC and DST. A register is considered
2078 stable if it has the RTX_UNCHANGING_P bit set, but that would still
2079 leave the burden to update REG_DEAD / REG_UNUSED notes, so we don't
2080 want any registers but SRC and DST. */
2082 stable_and_no_regs_but_for_p (x, src, dst)
2085 RTX_CODE code = GET_CODE (x);
2086 switch (GET_RTX_CLASS (code))
2088 case '<': case '1': case 'c': case '2': case 'b': case '3':
2091 const char *fmt = GET_RTX_FORMAT (code);
2092 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2094 && ! stable_and_no_regs_but_for_p (XEXP (x, i), src, dst))
2100 return x == src || x == dst;
2101 /* If this is a MEM, look inside - there might be a register hidden in
2102 the address of an unchanging MEM. */
2104 && ! stable_and_no_regs_but_for_p (XEXP (x, 0), src, dst))
2108 return ! rtx_unstable_p (x);
2112 /* Track stack adjustments and stack memory references. Attempt to
2113 reduce the number of stack adjustments by back-propagating across
2114 the memory references.
2116 This is intended primarily for use with targets that do not define
2117 ACCUMULATE_OUTGOING_ARGS. It is of significantly more value to
2118 targets that define PREFERRED_STACK_BOUNDARY more aligned than
2119 STACK_BOUNDARY (e.g. x86), or if not all registers can be pushed
2120 (e.g. x86 fp regs) which would ordinarily have to be implemented
2121 as a sub/mov pair due to restrictions in calls.c.
2123 Propagation stops when any of the insns that need adjusting are
2124 (a) no longer valid because we've exceeded their range, (b) a
2125 non-trivial push instruction, or (c) a call instruction.
2127 Restriction B is based on the assumption that push instructions
2128 are smaller or faster. If a port really wants to remove all
2129 pushes, it should have defined ACCUMULATE_OUTGOING_ARGS. The
2130 one exception that is made is for an add immediately followed
2133 /* This structure records stack memory references between stack adjusting
2138 HOST_WIDE_INT sp_offset;
2140 struct csa_memlist *next;
2143 static int stack_memref_p PARAMS ((rtx));
2144 static rtx single_set_for_csa PARAMS ((rtx));
2145 static void free_csa_memlist PARAMS ((struct csa_memlist *));
2146 static struct csa_memlist *record_one_stack_memref
2147 PARAMS ((rtx, rtx *, struct csa_memlist *));
2148 static int try_apply_stack_adjustment
2149 PARAMS ((rtx, struct csa_memlist *, HOST_WIDE_INT, HOST_WIDE_INT));
2150 static void combine_stack_adjustments_for_block PARAMS ((basic_block));
2151 static int record_stack_memrefs PARAMS ((rtx *, void *));
2154 /* Main entry point for stack adjustment combination. */
2157 combine_stack_adjustments ()
2162 combine_stack_adjustments_for_block (bb);
2165 /* Recognize a MEM of the form (sp) or (plus sp const). */
2171 if (GET_CODE (x) != MEM)
2175 if (x == stack_pointer_rtx)
2177 if (GET_CODE (x) == PLUS
2178 && XEXP (x, 0) == stack_pointer_rtx
2179 && GET_CODE (XEXP (x, 1)) == CONST_INT)
2185 /* Recognize either normal single_set or the hack in i386.md for
2186 tying fp and sp adjustments. */
2189 single_set_for_csa (insn)
2193 rtx tmp = single_set (insn);
2197 if (GET_CODE (insn) != INSN
2198 || GET_CODE (PATTERN (insn)) != PARALLEL)
2201 tmp = PATTERN (insn);
2202 if (GET_CODE (XVECEXP (tmp, 0, 0)) != SET)
2205 for (i = 1; i < XVECLEN (tmp, 0); ++i)
2207 rtx this = XVECEXP (tmp, 0, i);
2209 /* The special case is allowing a no-op set. */
2210 if (GET_CODE (this) == SET
2211 && SET_SRC (this) == SET_DEST (this))
2213 else if (GET_CODE (this) != CLOBBER
2214 && GET_CODE (this) != USE)
2218 return XVECEXP (tmp, 0, 0);
2221 /* Free the list of csa_memlist nodes. */
2224 free_csa_memlist (memlist)
2225 struct csa_memlist *memlist;
2227 struct csa_memlist *next;
2228 for (; memlist ; memlist = next)
2230 next = memlist->next;
2235 /* Create a new csa_memlist node from the given memory reference.
2236 It is already known that the memory is stack_memref_p. */
2238 static struct csa_memlist *
2239 record_one_stack_memref (insn, mem, next_memlist)
2241 struct csa_memlist *next_memlist;
2243 struct csa_memlist *ml;
2245 ml = (struct csa_memlist *) xmalloc (sizeof (*ml));
2247 if (XEXP (*mem, 0) == stack_pointer_rtx)
2250 ml->sp_offset = INTVAL (XEXP (XEXP (*mem, 0), 1));
2254 ml->next = next_memlist;
2259 /* Attempt to apply ADJUST to the stack adjusting insn INSN, as well
2260 as each of the memories in MEMLIST. Return true on success. */
2263 try_apply_stack_adjustment (insn, memlist, new_adjust, delta)
2265 struct csa_memlist *memlist;
2266 HOST_WIDE_INT new_adjust, delta;
2268 struct csa_memlist *ml;
2271 set = single_set_for_csa (insn);
2272 validate_change (insn, &XEXP (SET_SRC (set), 1), GEN_INT (new_adjust), 1);
2274 for (ml = memlist; ml ; ml = ml->next)
2277 replace_equiv_address_nv (*ml->mem,
2278 plus_constant (stack_pointer_rtx,
2279 ml->sp_offset - delta)), 1);
2281 if (apply_change_group ())
2283 /* Succeeded. Update our knowledge of the memory references. */
2284 for (ml = memlist; ml ; ml = ml->next)
2285 ml->sp_offset -= delta;
2293 /* Called via for_each_rtx and used to record all stack memory references in
2294 the insn and discard all other stack pointer references. */
2295 struct record_stack_memrefs_data
2298 struct csa_memlist *memlist;
2302 record_stack_memrefs (xp, data)
2307 struct record_stack_memrefs_data *d =
2308 (struct record_stack_memrefs_data *) data;
2311 switch (GET_CODE (x))
2314 if (!reg_mentioned_p (stack_pointer_rtx, x))
2316 /* We are not able to handle correctly all possible memrefs containing
2317 stack pointer, so this check is necessary. */
2318 if (stack_memref_p (x))
2320 d->memlist = record_one_stack_memref (d->insn, xp, d->memlist);
2325 /* ??? We want be able to handle non-memory stack pointer
2326 references later. For now just discard all insns refering to
2327 stack pointer outside mem expressions. We would probably
2328 want to teach validate_replace to simplify expressions first.
2330 We can't just compare with STACK_POINTER_RTX because the
2331 reference to the stack pointer might be in some other mode.
2332 In particular, an explicit clobber in an asm statement will
2333 result in a QImode clober. */
2334 if (REGNO (x) == STACK_POINTER_REGNUM)
2343 /* Subroutine of combine_stack_adjustments, called for each basic block. */
2346 combine_stack_adjustments_for_block (bb)
2349 HOST_WIDE_INT last_sp_adjust = 0;
2350 rtx last_sp_set = NULL_RTX;
2351 struct csa_memlist *memlist = NULL;
2352 rtx insn, next, set;
2353 struct record_stack_memrefs_data data;
2354 bool end_of_block = false;
2356 for (insn = bb->head; !end_of_block ; insn = next)
2358 end_of_block = insn == bb->end;
2359 next = NEXT_INSN (insn);
2361 if (! INSN_P (insn))
2364 set = single_set_for_csa (insn);
2367 rtx dest = SET_DEST (set);
2368 rtx src = SET_SRC (set);
2370 /* Find constant additions to the stack pointer. */
2371 if (dest == stack_pointer_rtx
2372 && GET_CODE (src) == PLUS
2373 && XEXP (src, 0) == stack_pointer_rtx
2374 && GET_CODE (XEXP (src, 1)) == CONST_INT)
2376 HOST_WIDE_INT this_adjust = INTVAL (XEXP (src, 1));
2378 /* If we've not seen an adjustment previously, record
2379 it now and continue. */
2383 last_sp_adjust = this_adjust;
2387 /* If not all recorded memrefs can be adjusted, or the
2388 adjustment is now too large for a constant addition,
2389 we cannot merge the two stack adjustments.
2391 Also we need to be careful to not move stack pointer
2392 such that we create stack accesses outside the allocated
2393 area. We can combine an allocation into the first insn,
2394 or a deallocation into the second insn. We can not
2395 combine an allocation followed by a deallocation.
2397 The only somewhat frequent occurrence of the later is when
2398 a function allocates a stack frame but does not use it.
2399 For this case, we would need to analyze rtl stream to be
2400 sure that allocated area is really unused. This means not
2401 only checking the memory references, but also all registers
2402 or global memory references possibly containing a stack
2405 Perhaps the best way to address this problem is to teach
2406 gcc not to allocate stack for objects never used. */
2408 /* Combine an allocation into the first instruction. */
2409 if (STACK_GROWS_DOWNWARD ? this_adjust <= 0 : this_adjust >= 0)
2411 if (try_apply_stack_adjustment (last_sp_set, memlist,
2412 last_sp_adjust + this_adjust,
2417 last_sp_adjust += this_adjust;
2422 /* Otherwise we have a deallocation. Do not combine with
2423 a previous allocation. Combine into the second insn. */
2424 else if (STACK_GROWS_DOWNWARD
2425 ? last_sp_adjust >= 0 : last_sp_adjust <= 0)
2427 if (try_apply_stack_adjustment (insn, memlist,
2428 last_sp_adjust + this_adjust,
2432 delete_insn (last_sp_set);
2434 last_sp_adjust += this_adjust;
2435 free_csa_memlist (memlist);
2441 /* Combination failed. Restart processing from here. If
2442 deallocation+allocation conspired to cancel, we can
2443 delete the old deallocation insn. */
2444 if (last_sp_set && last_sp_adjust == 0)
2446 free_csa_memlist (memlist);
2449 last_sp_adjust = this_adjust;
2453 /* Find a predecrement of exactly the previous adjustment and
2454 turn it into a direct store. Obviously we can't do this if
2455 there were any intervening uses of the stack pointer. */
2457 && GET_CODE (dest) == MEM
2458 && ((GET_CODE (XEXP (dest, 0)) == PRE_DEC
2460 == (HOST_WIDE_INT) GET_MODE_SIZE (GET_MODE (dest))))
2461 || (GET_CODE (XEXP (dest, 0)) == PRE_MODIFY
2462 && GET_CODE (XEXP (XEXP (dest, 0), 1)) == PLUS
2463 && XEXP (XEXP (XEXP (dest, 0), 1), 0) == stack_pointer_rtx
2464 && (GET_CODE (XEXP (XEXP (XEXP (dest, 0), 1), 1))
2466 && (INTVAL (XEXP (XEXP (XEXP (dest, 0), 1), 1))
2467 == -last_sp_adjust)))
2468 && XEXP (XEXP (dest, 0), 0) == stack_pointer_rtx
2469 && ! reg_mentioned_p (stack_pointer_rtx, src)
2470 && memory_address_p (GET_MODE (dest), stack_pointer_rtx)
2471 && validate_change (insn, &SET_DEST (set),
2472 replace_equiv_address (dest,
2476 delete_insn (last_sp_set);
2477 free_csa_memlist (memlist);
2479 last_sp_set = NULL_RTX;
2486 data.memlist = memlist;
2487 if (GET_CODE (insn) != CALL_INSN && last_sp_set
2488 && !for_each_rtx (&PATTERN (insn), record_stack_memrefs, &data))
2490 memlist = data.memlist;
2493 memlist = data.memlist;
2495 /* Otherwise, we were not able to process the instruction.
2496 Do not continue collecting data across such a one. */
2498 && (GET_CODE (insn) == CALL_INSN
2499 || reg_mentioned_p (stack_pointer_rtx, PATTERN (insn))))
2501 if (last_sp_set && last_sp_adjust == 0)
2502 delete_insn (last_sp_set);
2503 free_csa_memlist (memlist);
2505 last_sp_set = NULL_RTX;
2510 if (last_sp_set && last_sp_adjust == 0)
2511 delete_insn (last_sp_set);