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 Free Software Foundation, Inc.
5 This file is part of GNU CC.
7 GNU CC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
12 GNU CC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GNU CC; see the file COPYING. If not, write to
19 the Free Software Foundation, 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA. */
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 "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 static int perhaps_ends_bb_p PARAMS ((rtx));
46 static int optimize_reg_copy_1 PARAMS ((rtx, rtx, rtx));
47 static void optimize_reg_copy_2 PARAMS ((rtx, rtx, rtx));
48 static void optimize_reg_copy_3 PARAMS ((rtx, rtx, rtx));
49 static rtx gen_add3_insn PARAMS ((rtx, rtx, rtx));
50 static void copy_src_to_dest PARAMS ((rtx, rtx, rtx, int));
51 static int *regmove_bb_head;
54 int with[MAX_RECOG_OPERANDS];
55 enum { READ, WRITE, READWRITE } use[MAX_RECOG_OPERANDS];
56 int commutative[MAX_RECOG_OPERANDS];
57 int early_clobber[MAX_RECOG_OPERANDS];
60 static rtx discover_flags_reg PARAMS ((void));
61 static void mark_flags_life_zones PARAMS ((rtx));
62 static void flags_set_1 PARAMS ((rtx, rtx, void *));
64 static int try_auto_increment PARAMS ((rtx, rtx, rtx, rtx, HOST_WIDE_INT, int));
65 static int find_matches PARAMS ((rtx, struct match *));
66 static void replace_in_call_usage PARAMS ((rtx *, int, rtx, rtx));
67 static int fixup_match_1 PARAMS ((rtx, rtx, rtx, rtx, rtx, int, int, int, FILE *))
69 static int reg_is_remote_constant_p PARAMS ((rtx, rtx, rtx));
70 static int stable_and_no_regs_but_for_p PARAMS ((rtx, rtx, rtx));
71 static int regclass_compatible_p PARAMS ((int, int));
72 static int replacement_quality PARAMS ((rtx));
73 static int fixup_match_2 PARAMS ((rtx, rtx, rtx, rtx, FILE *));
75 /* Return non-zero if registers with CLASS1 and CLASS2 can be merged without
76 causing too much register allocation problems. */
78 regclass_compatible_p (class0, class1)
81 return (class0 == class1
82 || (reg_class_subset_p (class0, class1)
83 && ! CLASS_LIKELY_SPILLED_P (class0))
84 || (reg_class_subset_p (class1, class0)
85 && ! CLASS_LIKELY_SPILLED_P (class1)));
88 /* Generate and return an insn body to add r1 and c,
89 storing the result in r0. */
91 gen_add3_insn (r0, r1, c)
94 int icode = (int) add_optab->handlers[(int) GET_MODE (r0)].insn_code;
96 if (icode == CODE_FOR_nothing
97 || ! ((*insn_data[icode].operand[0].predicate)
98 (r0, insn_data[icode].operand[0].mode))
99 || ! ((*insn_data[icode].operand[1].predicate)
100 (r1, insn_data[icode].operand[1].mode))
101 || ! ((*insn_data[icode].operand[2].predicate)
102 (c, insn_data[icode].operand[2].mode)))
105 return (GEN_FCN (icode) (r0, r1, c));
109 /* INC_INSN is an instruction that adds INCREMENT to REG.
110 Try to fold INC_INSN as a post/pre in/decrement into INSN.
111 Iff INC_INSN_SET is nonzero, inc_insn has a destination different from src.
112 Return nonzero for success. */
114 try_auto_increment (insn, inc_insn, inc_insn_set, reg, increment, pre)
115 rtx reg, insn, inc_insn ,inc_insn_set;
116 HOST_WIDE_INT increment;
119 enum rtx_code inc_code;
121 rtx pset = single_set (insn);
124 /* Can't use the size of SET_SRC, we might have something like
125 (sign_extend:SI (mem:QI ... */
126 rtx use = find_use_as_address (pset, reg, 0);
127 if (use != 0 && use != (rtx) 1)
129 int size = GET_MODE_SIZE (GET_MODE (use));
131 || (HAVE_POST_INCREMENT
132 && pre == 0 && (inc_code = POST_INC, increment == size))
133 || (HAVE_PRE_INCREMENT
134 && pre == 1 && (inc_code = PRE_INC, increment == size))
135 || (HAVE_POST_DECREMENT
136 && pre == 0 && (inc_code = POST_DEC, increment == -size))
137 || (HAVE_PRE_DECREMENT
138 && pre == 1 && (inc_code = PRE_DEC, increment == -size))
144 &SET_SRC (inc_insn_set),
145 XEXP (SET_SRC (inc_insn_set), 0), 1);
146 validate_change (insn, &XEXP (use, 0),
147 gen_rtx_fmt_e (inc_code, Pmode, reg), 1);
148 if (apply_change_group ())
150 /* If there is a REG_DEAD note on this insn, we must
151 change this not to REG_UNUSED meaning that the register
152 is set, but the value is dead. Failure to do so will
153 result in a sched1 abort -- when it recomputes lifetime
154 information, the number of REG_DEAD notes will have
156 rtx note = find_reg_note (insn, REG_DEAD, reg);
158 PUT_MODE (note, REG_UNUSED);
161 = gen_rtx_EXPR_LIST (REG_INC,
162 reg, REG_NOTES (insn));
165 PUT_CODE (inc_insn, NOTE);
166 NOTE_LINE_NUMBER (inc_insn) = NOTE_INSN_DELETED;
167 NOTE_SOURCE_FILE (inc_insn) = 0;
177 /* Determine if the pattern generated by add_optab has a clobber,
178 such as might be issued for a flags hard register. To make the
179 code elsewhere simpler, we handle cc0 in this same framework.
181 Return the register if one was discovered. Return NULL_RTX if
182 if no flags were found. Return pc_rtx if we got confused. */
185 discover_flags_reg ()
188 tmp = gen_rtx_REG (word_mode, 10000);
189 tmp = gen_add3_insn (tmp, tmp, GEN_INT (2));
191 /* If we get something that isn't a simple set, or a
192 [(set ..) (clobber ..)], this whole function will go wrong. */
193 if (GET_CODE (tmp) == SET)
195 else if (GET_CODE (tmp) == PARALLEL)
199 if (XVECLEN (tmp, 0) != 2)
201 tmp = XVECEXP (tmp, 0, 1);
202 if (GET_CODE (tmp) != CLOBBER)
206 /* Don't do anything foolish if the md wanted to clobber a
207 scratch or something. We only care about hard regs.
208 Moreover we don't like the notion of subregs of hard regs. */
209 if (GET_CODE (tmp) == SUBREG
210 && GET_CODE (SUBREG_REG (tmp)) == REG
211 && REGNO (SUBREG_REG (tmp)) < FIRST_PSEUDO_REGISTER)
213 found = (GET_CODE (tmp) == REG && REGNO (tmp) < FIRST_PSEUDO_REGISTER);
215 return (found ? tmp : NULL_RTX);
221 /* It is a tedious task identifying when the flags register is live and
222 when it is safe to optimize. Since we process the instruction stream
223 multiple times, locate and record these live zones by marking the
224 mode of the instructions --
226 QImode is used on the instruction at which the flags becomes live.
228 HImode is used within the range (exclusive) that the flags are
229 live. Thus the user of the flags is not marked.
231 All other instructions are cleared to VOIDmode. */
233 /* Used to communicate with flags_set_1. */
234 static rtx flags_set_1_rtx;
235 static int flags_set_1_set;
238 mark_flags_life_zones (flags)
246 /* If we found a flags register on a cc0 host, bail. */
247 if (flags == NULL_RTX)
249 else if (flags != cc0_rtx)
253 /* Simple cases first: if no flags, clear all modes. If confusing,
254 mark the entire function as being in a flags shadow. */
255 if (flags == NULL_RTX || flags == pc_rtx)
257 enum machine_mode mode = (flags ? HImode : VOIDmode);
259 for (insn = get_insns(); insn; insn = NEXT_INSN (insn))
260 PUT_MODE (insn, mode);
268 flags_regno = REGNO (flags);
269 flags_nregs = HARD_REGNO_NREGS (flags_regno, GET_MODE (flags));
271 flags_set_1_rtx = flags;
273 /* Process each basic block. */
274 for (block = n_basic_blocks - 1; block >= 0; block--)
279 insn = BLOCK_HEAD (block);
280 end = BLOCK_END (block);
282 /* Look out for the (unlikely) case of flags being live across
283 basic block boundaries. */
288 for (i = 0; i < flags_nregs; ++i)
289 live |= REGNO_REG_SET_P (BASIC_BLOCK (block)->global_live_at_start,
296 /* Process liveness in reverse order of importance --
297 alive, death, birth. This lets more important info
298 overwrite the mode of lesser info. */
303 /* In the cc0 case, death is not marked in reg notes,
304 but is instead the mere use of cc0 when it is alive. */
305 if (live && reg_mentioned_p (cc0_rtx, PATTERN (insn)))
308 /* In the hard reg case, we watch death notes. */
309 if (live && find_regno_note (insn, REG_DEAD, flags_regno))
312 PUT_MODE (insn, (live ? HImode : VOIDmode));
314 /* In either case, birth is denoted simply by it's presence
315 as the destination of a set. */
317 note_stores (PATTERN (insn), flags_set_1, NULL);
321 PUT_MODE (insn, QImode);
325 PUT_MODE (insn, (live ? HImode : VOIDmode));
329 insn = NEXT_INSN (insn);
334 /* A subroutine of mark_flags_life_zones, called through note_stores. */
337 flags_set_1 (x, pat, data)
339 void *data ATTRIBUTE_UNUSED;
341 if (GET_CODE (pat) == SET
342 && reg_overlap_mentioned_p (x, flags_set_1_rtx))
346 static int *regno_src_regno;
348 /* Indicate how good a choice REG (which appears as a source) is to replace
349 a destination register with. The higher the returned value, the better
350 the choice. The main objective is to avoid using a register that is
351 a candidate for tying to a hard register, since the output might in
352 turn be a candidate to be tied to a different hard register. */
354 replacement_quality(reg)
359 /* Bad if this isn't a register at all. */
360 if (GET_CODE (reg) != REG)
363 /* If this register is not meant to get a hard register,
364 it is a poor choice. */
365 if (REG_LIVE_LENGTH (REGNO (reg)) < 0)
368 src_regno = regno_src_regno[REGNO (reg)];
370 /* If it was not copied from another register, it is fine. */
374 /* Copied from a hard register? */
375 if (src_regno < FIRST_PSEUDO_REGISTER)
378 /* Copied from a pseudo register - not as bad as from a hard register,
379 yet still cumbersome, since the register live length will be lengthened
380 when the registers get tied. */
384 /* Return 1 if INSN might end a basic block. */
386 static int perhaps_ends_bb_p (insn)
389 switch (GET_CODE (insn))
393 /* These always end a basic block. */
397 /* A CALL_INSN might be the last insn of a basic block, if it is inside
398 an EH region or if there are nonlocal gotos. Note that this test is
399 very conservative. */
400 if (nonlocal_goto_handler_labels)
404 return can_throw_internal (insn);
408 /* INSN is a copy from SRC to DEST, both registers, and SRC does not die
411 Search forward to see if SRC dies before either it or DEST is modified,
412 but don't scan past the end of a basic block. If so, we can replace SRC
413 with DEST and let SRC die in INSN.
415 This will reduce the number of registers live in that range and may enable
416 DEST to be tied to SRC, thus often saving one register in addition to a
417 register-register copy. */
420 optimize_reg_copy_1 (insn, dest, src)
428 int sregno = REGNO (src);
429 int dregno = REGNO (dest);
431 /* We don't want to mess with hard regs if register classes are small. */
433 || (SMALL_REGISTER_CLASSES
434 && (sregno < FIRST_PSEUDO_REGISTER
435 || dregno < FIRST_PSEUDO_REGISTER))
436 /* We don't see all updates to SP if they are in an auto-inc memory
437 reference, so we must disallow this optimization on them. */
438 || sregno == STACK_POINTER_REGNUM || dregno == STACK_POINTER_REGNUM)
441 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
443 /* ??? We can't scan past the end of a basic block without updating
444 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
445 if (perhaps_ends_bb_p (p))
447 else if (! INSN_P (p))
450 if (reg_set_p (src, p) || reg_set_p (dest, p)
451 /* Don't change a USE of a register. */
452 || (GET_CODE (PATTERN (p)) == USE
453 && reg_overlap_mentioned_p (src, XEXP (PATTERN (p), 0))))
456 /* See if all of SRC dies in P. This test is slightly more
457 conservative than it needs to be. */
458 if ((note = find_regno_note (p, REG_DEAD, sregno)) != 0
459 && GET_MODE (XEXP (note, 0)) == GET_MODE (src))
467 /* We can do the optimization. Scan forward from INSN again,
468 replacing regs as we go. Set FAILED if a replacement can't
469 be done. In that case, we can't move the death note for SRC.
470 This should be rare. */
472 /* Set to stop at next insn. */
473 for (q = next_real_insn (insn);
474 q != next_real_insn (p);
475 q = next_real_insn (q))
477 if (reg_overlap_mentioned_p (src, PATTERN (q)))
479 /* If SRC is a hard register, we might miss some
480 overlapping registers with validate_replace_rtx,
481 so we would have to undo it. We can't if DEST is
482 present in the insn, so fail in that combination
484 if (sregno < FIRST_PSEUDO_REGISTER
485 && reg_mentioned_p (dest, PATTERN (q)))
488 /* Replace all uses and make sure that the register
489 isn't still present. */
490 else if (validate_replace_rtx (src, dest, q)
491 && (sregno >= FIRST_PSEUDO_REGISTER
492 || ! reg_overlap_mentioned_p (src,
497 validate_replace_rtx (dest, src, q);
502 /* For SREGNO, count the total number of insns scanned.
503 For DREGNO, count the total number of insns scanned after
504 passing the death note for DREGNO. */
509 /* If the insn in which SRC dies is a CALL_INSN, don't count it
510 as a call that has been crossed. Otherwise, count it. */
511 if (q != p && GET_CODE (q) == CALL_INSN)
513 /* Similarly, total calls for SREGNO, total calls beyond
514 the death note for DREGNO. */
520 /* If DEST dies here, remove the death note and save it for
521 later. Make sure ALL of DEST dies here; again, this is
522 overly conservative. */
524 && (dest_death = find_regno_note (q, REG_DEAD, dregno)) != 0)
526 if (GET_MODE (XEXP (dest_death, 0)) != GET_MODE (dest))
527 failed = 1, dest_death = 0;
529 remove_note (q, dest_death);
535 /* These counters need to be updated if and only if we are
536 going to move the REG_DEAD note. */
537 if (sregno >= FIRST_PSEUDO_REGISTER)
539 if (REG_LIVE_LENGTH (sregno) >= 0)
541 REG_LIVE_LENGTH (sregno) -= s_length;
542 /* REG_LIVE_LENGTH is only an approximation after
543 combine if sched is not run, so make sure that we
544 still have a reasonable value. */
545 if (REG_LIVE_LENGTH (sregno) < 2)
546 REG_LIVE_LENGTH (sregno) = 2;
549 REG_N_CALLS_CROSSED (sregno) -= s_n_calls;
552 /* Move death note of SRC from P to INSN. */
553 remove_note (p, note);
554 XEXP (note, 1) = REG_NOTES (insn);
555 REG_NOTES (insn) = note;
558 /* DEST is also dead if INSN has a REG_UNUSED note for DEST. */
560 && (dest_death = find_regno_note (insn, REG_UNUSED, dregno)))
562 PUT_REG_NOTE_KIND (dest_death, REG_DEAD);
563 remove_note (insn, dest_death);
566 /* Put death note of DEST on P if we saw it die. */
569 XEXP (dest_death, 1) = REG_NOTES (p);
570 REG_NOTES (p) = dest_death;
572 if (dregno >= FIRST_PSEUDO_REGISTER)
574 /* If and only if we are moving the death note for DREGNO,
575 then we need to update its counters. */
576 if (REG_LIVE_LENGTH (dregno) >= 0)
577 REG_LIVE_LENGTH (dregno) += d_length;
578 REG_N_CALLS_CROSSED (dregno) += d_n_calls;
585 /* If SRC is a hard register which is set or killed in some other
586 way, we can't do this optimization. */
587 else if (sregno < FIRST_PSEUDO_REGISTER
588 && dead_or_set_p (p, src))
594 /* INSN is a copy of SRC to DEST, in which SRC dies. See if we now have
595 a sequence of insns that modify DEST followed by an insn that sets
596 SRC to DEST in which DEST dies, with no prior modification of DEST.
597 (There is no need to check if the insns in between actually modify
598 DEST. We should not have cases where DEST is not modified, but
599 the optimization is safe if no such modification is detected.)
600 In that case, we can replace all uses of DEST, starting with INSN and
601 ending with the set of SRC to DEST, with SRC. We do not do this
602 optimization if a CALL_INSN is crossed unless SRC already crosses a
603 call or if DEST dies before the copy back to SRC.
605 It is assumed that DEST and SRC are pseudos; it is too complicated to do
606 this for hard registers since the substitutions we may make might fail. */
609 optimize_reg_copy_2 (insn, dest, src)
616 int sregno = REGNO (src);
617 int dregno = REGNO (dest);
619 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
621 /* ??? We can't scan past the end of a basic block without updating
622 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
623 if (perhaps_ends_bb_p (p))
625 else if (! INSN_P (p))
628 set = single_set (p);
629 if (set && SET_SRC (set) == dest && SET_DEST (set) == src
630 && find_reg_note (p, REG_DEAD, dest))
632 /* We can do the optimization. Scan forward from INSN again,
633 replacing regs as we go. */
635 /* Set to stop at next insn. */
636 for (q = insn; q != NEXT_INSN (p); q = NEXT_INSN (q))
639 if (reg_mentioned_p (dest, PATTERN (q)))
640 PATTERN (q) = replace_rtx (PATTERN (q), dest, src);
643 if (GET_CODE (q) == CALL_INSN)
645 REG_N_CALLS_CROSSED (dregno)--;
646 REG_N_CALLS_CROSSED (sregno)++;
650 remove_note (p, find_reg_note (p, REG_DEAD, dest));
651 REG_N_DEATHS (dregno)--;
652 remove_note (insn, find_reg_note (insn, REG_DEAD, src));
653 REG_N_DEATHS (sregno)--;
657 if (reg_set_p (src, p)
658 || find_reg_note (p, REG_DEAD, dest)
659 || (GET_CODE (p) == CALL_INSN && REG_N_CALLS_CROSSED (sregno) == 0))
663 /* INSN is a ZERO_EXTEND or SIGN_EXTEND of SRC to DEST.
664 Look if SRC dies there, and if it is only set once, by loading
665 it from memory. If so, try to encorporate the zero/sign extension
666 into the memory read, change SRC to the mode of DEST, and alter
667 the remaining accesses to use the appropriate SUBREG. This allows
668 SRC and DEST to be tied later. */
670 optimize_reg_copy_3 (insn, dest, src)
675 rtx src_reg = XEXP (src, 0);
676 int src_no = REGNO (src_reg);
677 int dst_no = REGNO (dest);
679 enum machine_mode old_mode;
681 if (src_no < FIRST_PSEUDO_REGISTER
682 || dst_no < FIRST_PSEUDO_REGISTER
683 || ! find_reg_note (insn, REG_DEAD, src_reg)
684 || REG_N_SETS (src_no) != 1)
686 for (p = PREV_INSN (insn); p && ! reg_set_p (src_reg, p); p = PREV_INSN (p))
687 /* ??? We can't scan past the end of a basic block without updating
688 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
689 if (perhaps_ends_bb_p (p))
695 if (! (set = single_set (p))
696 || GET_CODE (SET_SRC (set)) != MEM
697 || SET_DEST (set) != src_reg)
700 /* Be conserative: although this optimization is also valid for
701 volatile memory references, that could cause trouble in later passes. */
702 if (MEM_VOLATILE_P (SET_SRC (set)))
705 /* Do not use a SUBREG to truncate from one mode to another if truncation
707 if (GET_MODE_BITSIZE (GET_MODE (src_reg)) <= GET_MODE_BITSIZE (GET_MODE (src))
708 && !TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (GET_MODE (src)),
709 GET_MODE_BITSIZE (GET_MODE (src_reg))))
712 old_mode = GET_MODE (src_reg);
713 PUT_MODE (src_reg, GET_MODE (src));
714 XEXP (src, 0) = SET_SRC (set);
716 /* Include this change in the group so that it's easily undone if
717 one of the changes in the group is invalid. */
718 validate_change (p, &SET_SRC (set), src, 1);
720 /* Now walk forward making additional replacements. We want to be able
721 to undo all the changes if a later substitution fails. */
722 subreg = gen_lowpart_SUBREG (old_mode, src_reg);
723 while (p = NEXT_INSN (p), p != insn)
728 /* Make a tenative change. */
729 validate_replace_rtx_group (src_reg, subreg, p);
732 validate_replace_rtx_group (src, src_reg, insn);
734 /* Now see if all the changes are valid. */
735 if (! apply_change_group ())
737 /* One or more changes were no good. Back out everything. */
738 PUT_MODE (src_reg, old_mode);
739 XEXP (src, 0) = src_reg;
744 /* If we were not able to update the users of src to use dest directly, try
745 instead moving the value to dest directly before the operation. */
748 copy_src_to_dest (insn, src, dest, old_max_uid)
767 /* A REG_LIVE_LENGTH of -1 indicates the register is equivalent to a constant
768 or memory location and is used infrequently; a REG_LIVE_LENGTH of -2 is
769 parameter when there is no frame pointer that is not allocated a register.
770 For now, we just reject them, rather than incrementing the live length. */
772 if (GET_CODE (src) == REG
773 && REG_LIVE_LENGTH (REGNO (src)) > 0
774 && GET_CODE (dest) == REG
775 && !RTX_UNCHANGING_P (dest)
776 && REG_LIVE_LENGTH (REGNO (dest)) > 0
777 && (set = single_set (insn)) != NULL_RTX
778 && !reg_mentioned_p (dest, SET_SRC (set))
779 && GET_MODE (src) == GET_MODE (dest))
781 int old_num_regs = reg_rtx_no;
783 /* Generate the src->dest move. */
785 emit_move_insn (dest, src);
786 seq = gen_sequence ();
788 /* If this sequence uses new registers, we may not use it. */
789 if (old_num_regs != reg_rtx_no
790 || ! validate_replace_rtx (src, dest, insn))
792 /* We have to restore reg_rtx_no to its old value, lest
793 recompute_reg_usage will try to compute the usage of the
794 new regs, yet reg_n_info is not valid for them. */
795 reg_rtx_no = old_num_regs;
798 emit_insn_before (seq, insn);
799 move_insn = PREV_INSN (insn);
800 p_move_notes = ®_NOTES (move_insn);
801 p_insn_notes = ®_NOTES (insn);
803 /* Move any notes mentioning src to the move instruction */
804 for (link = REG_NOTES (insn); link != NULL_RTX; link = next)
806 next = XEXP (link, 1);
807 if (XEXP (link, 0) == src)
809 *p_move_notes = link;
810 p_move_notes = &XEXP (link, 1);
814 *p_insn_notes = link;
815 p_insn_notes = &XEXP (link, 1);
819 *p_move_notes = NULL_RTX;
820 *p_insn_notes = NULL_RTX;
822 /* Is the insn the head of a basic block? If so extend it */
823 insn_uid = INSN_UID (insn);
824 move_uid = INSN_UID (move_insn);
825 if (insn_uid < old_max_uid)
827 bb = regmove_bb_head[insn_uid];
830 BLOCK_HEAD (bb) = move_insn;
831 regmove_bb_head[insn_uid] = -1;
835 /* Update the various register tables. */
836 dest_regno = REGNO (dest);
837 REG_N_SETS (dest_regno) ++;
838 REG_LIVE_LENGTH (dest_regno)++;
839 if (REGNO_FIRST_UID (dest_regno) == insn_uid)
840 REGNO_FIRST_UID (dest_regno) = move_uid;
842 src_regno = REGNO (src);
843 if (! find_reg_note (move_insn, REG_DEAD, src))
844 REG_LIVE_LENGTH (src_regno)++;
846 if (REGNO_FIRST_UID (src_regno) == insn_uid)
847 REGNO_FIRST_UID (src_regno) = move_uid;
849 if (REGNO_LAST_UID (src_regno) == insn_uid)
850 REGNO_LAST_UID (src_regno) = move_uid;
852 if (REGNO_LAST_NOTE_UID (src_regno) == insn_uid)
853 REGNO_LAST_NOTE_UID (src_regno) = move_uid;
858 /* Return whether REG is set in only one location, and is set to a
859 constant, but is set in a different basic block from INSN (an
860 instructions which uses REG). In this case REG is equivalent to a
861 constant, and we don't want to break that equivalence, because that
862 may increase register pressure and make reload harder. If REG is
863 set in the same basic block as INSN, we don't worry about it,
864 because we'll probably need a register anyhow (??? but what if REG
865 is used in a different basic block as well as this one?). FIRST is
866 the first insn in the function. */
869 reg_is_remote_constant_p (reg, insn, first)
876 if (REG_N_SETS (REGNO (reg)) != 1)
879 /* Look for the set. */
880 for (p = LOG_LINKS (insn); p; p = XEXP (p, 1))
884 if (REG_NOTE_KIND (p) != 0)
886 s = single_set (XEXP (p, 0));
888 && GET_CODE (SET_DEST (s)) == REG
889 && REGNO (SET_DEST (s)) == REGNO (reg))
891 /* The register is set in the same basic block. */
896 for (p = first; p && p != insn; p = NEXT_INSN (p))
904 && GET_CODE (SET_DEST (s)) == REG
905 && REGNO (SET_DEST (s)) == REGNO (reg))
907 /* This is the instruction which sets REG. If there is a
908 REG_EQUAL note, then REG is equivalent to a constant. */
909 if (find_reg_note (p, REG_EQUAL, NULL_RTX))
918 /* INSN is adding a CONST_INT to a REG. We search backwards looking for
919 another add immediate instruction with the same source and dest registers,
920 and if we find one, we change INSN to an increment, and return 1. If
921 no changes are made, we return 0.
924 (set (reg100) (plus reg1 offset1))
926 (set (reg100) (plus reg1 offset2))
928 (set (reg100) (plus reg1 offset1))
930 (set (reg100) (plus reg100 offset2-offset1)) */
932 /* ??? What does this comment mean? */
933 /* cse disrupts preincrement / postdecrement squences when it finds a
934 hard register as ultimate source, like the frame pointer. */
937 fixup_match_2 (insn, dst, src, offset, regmove_dump_file)
938 rtx insn, dst, src, offset;
939 FILE *regmove_dump_file;
941 rtx p, dst_death = 0;
942 int length, num_calls = 0;
944 /* If SRC dies in INSN, we'd have to move the death note. This is
945 considered to be very unlikely, so we just skip the optimization
947 if (find_regno_note (insn, REG_DEAD, REGNO (src)))
950 /* Scan backward to find the first instruction that sets DST. */
952 for (length = 0, p = PREV_INSN (insn); p; p = PREV_INSN (p))
956 /* ??? We can't scan past the end of a basic block without updating
957 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
958 if (perhaps_ends_bb_p (p))
960 else if (! INSN_P (p))
963 if (find_regno_note (p, REG_DEAD, REGNO (dst)))
968 pset = single_set (p);
969 if (pset && SET_DEST (pset) == dst
970 && GET_CODE (SET_SRC (pset)) == PLUS
971 && XEXP (SET_SRC (pset), 0) == src
972 && GET_CODE (XEXP (SET_SRC (pset), 1)) == CONST_INT)
974 HOST_WIDE_INT newconst
975 = INTVAL (offset) - INTVAL (XEXP (SET_SRC (pset), 1));
976 rtx add = gen_add3_insn (dst, dst, GEN_INT (newconst));
978 if (add && validate_change (insn, &PATTERN (insn), add, 0))
980 /* Remove the death note for DST from DST_DEATH. */
983 remove_death (REGNO (dst), dst_death);
984 REG_LIVE_LENGTH (REGNO (dst)) += length;
985 REG_N_CALLS_CROSSED (REGNO (dst)) += num_calls;
988 if (regmove_dump_file)
989 fprintf (regmove_dump_file,
990 "Fixed operand of insn %d.\n",
994 for (p = PREV_INSN (insn); p; p = PREV_INSN (p))
996 if (GET_CODE (p) == CODE_LABEL
997 || GET_CODE (p) == JUMP_INSN)
1001 if (reg_overlap_mentioned_p (dst, PATTERN (p)))
1003 if (try_auto_increment (p, insn, 0, dst, newconst, 0))
1008 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
1010 if (GET_CODE (p) == CODE_LABEL
1011 || GET_CODE (p) == JUMP_INSN)
1015 if (reg_overlap_mentioned_p (dst, PATTERN (p)))
1017 try_auto_increment (p, insn, 0, dst, newconst, 1);
1026 if (reg_set_p (dst, PATTERN (p)))
1029 /* If we have passed a call instruction, and the
1030 pseudo-reg SRC is not already live across a call,
1031 then don't perform the optimization. */
1032 /* reg_set_p is overly conservative for CALL_INSNS, thinks that all
1033 hard regs are clobbered. Thus, we only use it for src for
1035 if (GET_CODE (p) == CALL_INSN)
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)))
1055 regmove_optimize (f, nregs, regmove_dump_file)
1058 FILE *regmove_dump_file;
1060 int old_max_uid = get_max_uid ();
1065 rtx copy_src, copy_dst;
1067 /* ??? Hack. Regmove doesn't examine the CFG, and gets mightily
1068 confused by non-call exceptions ending blocks. */
1069 if (flag_non_call_exceptions)
1072 /* Find out where a potential flags register is live, and so that we
1073 can supress some optimizations in those zones. */
1074 mark_flags_life_zones (discover_flags_reg ());
1076 regno_src_regno = (int *) xmalloc (sizeof *regno_src_regno * nregs);
1077 for (i = nregs; --i >= 0; ) regno_src_regno[i] = -1;
1079 regmove_bb_head = (int *) xmalloc (sizeof (int) * (old_max_uid + 1));
1080 for (i = old_max_uid; i >= 0; i--) regmove_bb_head[i] = -1;
1081 for (i = 0; i < n_basic_blocks; i++)
1082 regmove_bb_head[INSN_UID (BLOCK_HEAD (i))] = i;
1084 /* A forward/backward pass. Replace output operands with input operands. */
1086 for (pass = 0; pass <= 2; pass++)
1088 if (! flag_regmove && pass >= flag_expensive_optimizations)
1091 if (regmove_dump_file)
1092 fprintf (regmove_dump_file, "Starting %s pass...\n",
1093 pass ? "backward" : "forward");
1095 for (insn = pass ? get_last_insn () : f; insn;
1096 insn = pass ? PREV_INSN (insn) : NEXT_INSN (insn))
1099 int op_no, match_no;
1101 set = single_set (insn);
1105 if (flag_expensive_optimizations && ! pass
1106 && (GET_CODE (SET_SRC (set)) == SIGN_EXTEND
1107 || GET_CODE (SET_SRC (set)) == ZERO_EXTEND)
1108 && GET_CODE (XEXP (SET_SRC (set), 0)) == REG
1109 && GET_CODE (SET_DEST(set)) == REG)
1110 optimize_reg_copy_3 (insn, SET_DEST (set), SET_SRC (set));
1112 if (flag_expensive_optimizations && ! pass
1113 && GET_CODE (SET_SRC (set)) == REG
1114 && GET_CODE (SET_DEST(set)) == REG)
1116 /* If this is a register-register copy where SRC is not dead,
1117 see if we can optimize it. If this optimization succeeds,
1118 it will become a copy where SRC is dead. */
1119 if ((find_reg_note (insn, REG_DEAD, SET_SRC (set))
1120 || optimize_reg_copy_1 (insn, SET_DEST (set), SET_SRC (set)))
1121 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
1123 /* Similarly for a pseudo-pseudo copy when SRC is dead. */
1124 if (REGNO (SET_SRC (set)) >= FIRST_PSEUDO_REGISTER)
1125 optimize_reg_copy_2 (insn, SET_DEST (set), SET_SRC (set));
1126 if (regno_src_regno[REGNO (SET_DEST (set))] < 0
1127 && SET_SRC (set) != SET_DEST (set))
1129 int srcregno = REGNO (SET_SRC(set));
1130 if (regno_src_regno[srcregno] >= 0)
1131 srcregno = regno_src_regno[srcregno];
1132 regno_src_regno[REGNO (SET_DEST (set))] = srcregno;
1139 if (! find_matches (insn, &match))
1142 /* Now scan through the operands looking for a source operand
1143 which is supposed to match the destination operand.
1144 Then scan forward for an instruction which uses the dest
1146 If it dies there, then replace the dest in both operands with
1147 the source operand. */
1149 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1151 rtx src, dst, src_subreg;
1152 enum reg_class src_class, dst_class;
1154 match_no = match.with[op_no];
1156 /* Nothing to do if the two operands aren't supposed to match. */
1160 src = recog_data.operand[op_no];
1161 dst = recog_data.operand[match_no];
1163 if (GET_CODE (src) != REG)
1167 if (GET_CODE (dst) == SUBREG
1168 && GET_MODE_SIZE (GET_MODE (dst))
1169 >= GET_MODE_SIZE (GET_MODE (SUBREG_REG (dst))))
1172 = gen_rtx_SUBREG (GET_MODE (SUBREG_REG (dst)),
1173 src, SUBREG_BYTE (dst));
1174 dst = SUBREG_REG (dst);
1176 if (GET_CODE (dst) != REG
1177 || REGNO (dst) < FIRST_PSEUDO_REGISTER)
1180 if (REGNO (src) < FIRST_PSEUDO_REGISTER)
1182 if (match.commutative[op_no] < op_no)
1183 regno_src_regno[REGNO (dst)] = REGNO (src);
1187 if (REG_LIVE_LENGTH (REGNO (src)) < 0)
1190 /* op_no/src must be a read-only operand, and
1191 match_operand/dst must be a write-only operand. */
1192 if (match.use[op_no] != READ
1193 || match.use[match_no] != WRITE)
1196 if (match.early_clobber[match_no]
1197 && count_occurrences (PATTERN (insn), src, 0) > 1)
1200 /* Make sure match_operand is the destination. */
1201 if (recog_data.operand[match_no] != SET_DEST (set))
1204 /* If the operands already match, then there is nothing to do. */
1205 if (operands_match_p (src, dst))
1208 /* But in the commutative case, we might find a better match. */
1209 if (match.commutative[op_no] >= 0)
1211 rtx comm = recog_data.operand[match.commutative[op_no]];
1212 if (operands_match_p (comm, dst)
1213 && (replacement_quality (comm)
1214 >= replacement_quality (src)))
1218 src_class = reg_preferred_class (REGNO (src));
1219 dst_class = reg_preferred_class (REGNO (dst));
1220 if (! regclass_compatible_p (src_class, dst_class))
1223 if (fixup_match_1 (insn, set, src, src_subreg, dst, pass,
1231 /* A backward pass. Replace input operands with output operands. */
1233 if (regmove_dump_file)
1234 fprintf (regmove_dump_file, "Starting backward pass...\n");
1236 for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
1240 int op_no, match_no;
1243 if (! find_matches (insn, &match))
1246 /* Now scan through the operands looking for a destination operand
1247 which is supposed to match a source operand.
1248 Then scan backward for an instruction which sets the source
1249 operand. If safe, then replace the source operand with the
1250 dest operand in both instructions. */
1252 copy_src = NULL_RTX;
1253 copy_dst = NULL_RTX;
1254 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1256 rtx set, p, src, dst;
1257 rtx src_note, dst_note;
1259 enum reg_class src_class, dst_class;
1262 match_no = match.with[op_no];
1264 /* Nothing to do if the two operands aren't supposed to match. */
1268 dst = recog_data.operand[match_no];
1269 src = recog_data.operand[op_no];
1271 if (GET_CODE (src) != REG)
1274 if (GET_CODE (dst) != REG
1275 || REGNO (dst) < FIRST_PSEUDO_REGISTER
1276 || REG_LIVE_LENGTH (REGNO (dst)) < 0)
1279 /* If the operands already match, then there is nothing to do. */
1280 if (operands_match_p (src, dst))
1283 if (match.commutative[op_no] >= 0)
1285 rtx comm = recog_data.operand[match.commutative[op_no]];
1286 if (operands_match_p (comm, dst))
1290 set = single_set (insn);
1294 /* match_no/dst must be a write-only operand, and
1295 operand_operand/src must be a read-only operand. */
1296 if (match.use[op_no] != READ
1297 || match.use[match_no] != WRITE)
1300 if (match.early_clobber[match_no]
1301 && count_occurrences (PATTERN (insn), src, 0) > 1)
1304 /* Make sure match_no is the destination. */
1305 if (recog_data.operand[match_no] != SET_DEST (set))
1308 if (REGNO (src) < FIRST_PSEUDO_REGISTER)
1310 if (GET_CODE (SET_SRC (set)) == PLUS
1311 && GET_CODE (XEXP (SET_SRC (set), 1)) == CONST_INT
1312 && XEXP (SET_SRC (set), 0) == src
1313 && fixup_match_2 (insn, dst, src,
1314 XEXP (SET_SRC (set), 1),
1319 src_class = reg_preferred_class (REGNO (src));
1320 dst_class = reg_preferred_class (REGNO (dst));
1321 if (! regclass_compatible_p (src_class, dst_class))
1331 /* Can not modify an earlier insn to set dst if this insn
1332 uses an old value in the source. */
1333 if (reg_overlap_mentioned_p (dst, SET_SRC (set)))
1343 if (! (src_note = find_reg_note (insn, REG_DEAD, src)))
1354 /* If src is set once in a different basic block,
1355 and is set equal to a constant, then do not use
1356 it for this optimization, as this would make it
1357 no longer equivalent to a constant. */
1359 if (reg_is_remote_constant_p (src, insn, f))
1370 if (regmove_dump_file)
1371 fprintf (regmove_dump_file,
1372 "Could fix operand %d of insn %d matching operand %d.\n",
1373 op_no, INSN_UID (insn), match_no);
1375 /* Scan backward to find the first instruction that uses
1376 the input operand. If the operand is set here, then
1377 replace it in both instructions with match_no. */
1379 for (length = 0, p = PREV_INSN (insn); p; p = PREV_INSN (p))
1383 /* ??? We can't scan past the end of a basic block without
1384 updating the register lifetime info
1385 (REG_DEAD/basic_block_live_at_start). */
1386 if (perhaps_ends_bb_p (p))
1388 else if (! INSN_P (p))
1393 /* ??? See if all of SRC is set in P. This test is much
1394 more conservative than it needs to be. */
1395 pset = single_set (p);
1396 if (pset && SET_DEST (pset) == src)
1398 /* We use validate_replace_rtx, in case there
1399 are multiple identical source operands. All of
1400 them have to be changed at the same time. */
1401 if (validate_replace_rtx (src, dst, insn))
1403 if (validate_change (p, &SET_DEST (pset),
1408 /* Change all source operands back.
1409 This modifies the dst as a side-effect. */
1410 validate_replace_rtx (dst, src, insn);
1411 /* Now make sure the dst is right. */
1412 validate_change (insn,
1413 recog_data.operand_loc[match_no],
1420 if (reg_overlap_mentioned_p (src, PATTERN (p))
1421 || reg_overlap_mentioned_p (dst, PATTERN (p)))
1424 /* If we have passed a call instruction, and the
1425 pseudo-reg DST is not already live across a call,
1426 then don't perform the optimization. */
1427 if (GET_CODE (p) == CALL_INSN)
1431 if (REG_N_CALLS_CROSSED (REGNO (dst)) == 0)
1440 /* Remove the death note for SRC from INSN. */
1441 remove_note (insn, src_note);
1442 /* Move the death note for SRC to P if it is used
1444 if (reg_overlap_mentioned_p (src, PATTERN (p)))
1446 XEXP (src_note, 1) = REG_NOTES (p);
1447 REG_NOTES (p) = src_note;
1449 /* If there is a REG_DEAD note for DST on P, then remove
1450 it, because DST is now set there. */
1451 if ((dst_note = find_reg_note (p, REG_DEAD, dst)))
1452 remove_note (p, dst_note);
1454 dstno = REGNO (dst);
1455 srcno = REGNO (src);
1457 REG_N_SETS (dstno)++;
1458 REG_N_SETS (srcno)--;
1460 REG_N_CALLS_CROSSED (dstno) += num_calls;
1461 REG_N_CALLS_CROSSED (srcno) -= num_calls;
1463 REG_LIVE_LENGTH (dstno) += length;
1464 if (REG_LIVE_LENGTH (srcno) >= 0)
1466 REG_LIVE_LENGTH (srcno) -= length;
1467 /* REG_LIVE_LENGTH is only an approximation after
1468 combine if sched is not run, so make sure that we
1469 still have a reasonable value. */
1470 if (REG_LIVE_LENGTH (srcno) < 2)
1471 REG_LIVE_LENGTH (srcno) = 2;
1474 if (regmove_dump_file)
1475 fprintf (regmove_dump_file,
1476 "Fixed operand %d of insn %d matching operand %d.\n",
1477 op_no, INSN_UID (insn), match_no);
1483 /* If we weren't able to replace any of the alternatives, try an
1484 alternative appoach of copying the source to the destination. */
1485 if (!success && copy_src != NULL_RTX)
1486 copy_src_to_dest (insn, copy_src, copy_dst, old_max_uid);
1491 /* In fixup_match_1, some insns may have been inserted after basic block
1492 ends. Fix that here. */
1493 for (i = 0; i < n_basic_blocks; i++)
1495 rtx end = BLOCK_END (i);
1497 rtx next = NEXT_INSN (new);
1498 while (next != 0 && INSN_UID (next) >= old_max_uid
1499 && (i == n_basic_blocks - 1 || BLOCK_HEAD (i + 1) != next))
1500 new = next, next = NEXT_INSN (new);
1501 BLOCK_END (i) = new;
1506 free (regno_src_regno);
1507 free (regmove_bb_head);
1510 /* Returns nonzero if INSN's pattern has matching constraints for any operand.
1511 Returns 0 if INSN can't be recognized, or if the alternative can't be
1514 Initialize the info in MATCHP based on the constraints. */
1517 find_matches (insn, matchp)
1519 struct match *matchp;
1521 int likely_spilled[MAX_RECOG_OPERANDS];
1523 int any_matches = 0;
1525 extract_insn (insn);
1526 if (! constrain_operands (0))
1529 /* Must initialize this before main loop, because the code for
1530 the commutative case may set matches for operands other than
1532 for (op_no = recog_data.n_operands; --op_no >= 0; )
1533 matchp->with[op_no] = matchp->commutative[op_no] = -1;
1535 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1541 p = recog_data.constraints[op_no];
1543 likely_spilled[op_no] = 0;
1544 matchp->use[op_no] = READ;
1545 matchp->early_clobber[op_no] = 0;
1547 matchp->use[op_no] = WRITE;
1549 matchp->use[op_no] = READWRITE;
1551 for (;*p && i < which_alternative; p++)
1555 while ((c = *p++) != '\0' && c != ',')
1563 matchp->early_clobber[op_no] = 1;
1566 matchp->commutative[op_no] = op_no + 1;
1567 matchp->commutative[op_no + 1] = op_no;
1569 case '0': case '1': case '2': case '3': case '4':
1570 case '5': case '6': case '7': case '8': case '9':
1572 if (c < op_no && likely_spilled[(unsigned char) c])
1574 matchp->with[op_no] = c;
1576 if (matchp->commutative[op_no] >= 0)
1577 matchp->with[matchp->commutative[op_no]] = c;
1579 case 'a': case 'b': case 'c': case 'd': case 'e': case 'f': case 'h':
1580 case 'j': case 'k': case 'l': case 'p': case 'q': case 't': case 'u':
1581 case 'v': case 'w': case 'x': case 'y': case 'z': case 'A': case 'B':
1582 case 'C': case 'D': case 'W': case 'Y': case 'Z':
1583 if (CLASS_LIKELY_SPILLED_P (REG_CLASS_FROM_LETTER ((unsigned char)c)))
1584 likely_spilled[op_no] = 1;
1591 /* Try to replace all occurrences of DST_REG with SRC in LOC, that is
1592 assumed to be in INSN. */
1595 replace_in_call_usage (loc, dst_reg, src, insn)
1609 code = GET_CODE (x);
1612 if (REGNO (x) != dst_reg)
1615 validate_change (insn, loc, src, 1);
1620 /* Process each of our operands recursively. */
1621 fmt = GET_RTX_FORMAT (code);
1622 for (i = 0; i < GET_RTX_LENGTH (code); i++, fmt++)
1624 replace_in_call_usage (&XEXP (x, i), dst_reg, src, insn);
1625 else if (*fmt == 'E')
1626 for (j = 0; j < XVECLEN (x, i); j++)
1627 replace_in_call_usage (& XVECEXP (x, i, j), dst_reg, src, insn);
1630 /* Try to replace output operand DST in SET, with input operand SRC. SET is
1631 the only set in INSN. INSN has just been recognized and constrained.
1632 SRC is operand number OPERAND_NUMBER in INSN.
1633 DST is operand number MATCH_NUMBER in INSN.
1634 If BACKWARD is nonzero, we have been called in a backward pass.
1635 Return nonzero for success. */
1638 fixup_match_1 (insn, set, src, src_subreg, dst, backward, operand_number,
1639 match_number, regmove_dump_file)
1640 rtx insn, set, src, src_subreg, dst;
1641 int backward, operand_number, match_number;
1642 FILE *regmove_dump_file;
1645 rtx post_inc = 0, post_inc_set = 0, search_end = 0;
1647 int num_calls = 0, s_num_calls = 0;
1648 enum rtx_code code = NOTE;
1649 HOST_WIDE_INT insn_const = 0, newconst;
1650 rtx overlap = 0; /* need to move insn ? */
1651 rtx src_note = find_reg_note (insn, REG_DEAD, src), dst_note = NULL_RTX;
1652 int length, s_length;
1654 /* If SRC is marked as unchanging, we may not change it.
1655 ??? Maybe we could get better code by removing the unchanging bit
1656 instead, and changing it back if we don't succeed? */
1657 if (RTX_UNCHANGING_P (src))
1662 /* Look for (set (regX) (op regA constX))
1663 (set (regY) (op regA constY))
1665 (set (regA) (op regA constX)).
1666 (set (regY) (op regA constY-constX)).
1667 This works for add and shift operations, if
1668 regA is dead after or set by the second insn. */
1670 code = GET_CODE (SET_SRC (set));
1671 if ((code == PLUS || code == LSHIFTRT
1672 || code == ASHIFT || code == ASHIFTRT)
1673 && XEXP (SET_SRC (set), 0) == src
1674 && GET_CODE (XEXP (SET_SRC (set), 1)) == CONST_INT)
1675 insn_const = INTVAL (XEXP (SET_SRC (set), 1));
1676 else if (! stable_and_no_regs_but_for_p (SET_SRC (set), src, dst))
1679 /* We might find a src_note while scanning. */
1683 if (regmove_dump_file)
1684 fprintf (regmove_dump_file,
1685 "Could fix operand %d of insn %d matching operand %d.\n",
1686 operand_number, INSN_UID (insn), match_number);
1688 /* If SRC is equivalent to a constant set in a different basic block,
1689 then do not use it for this optimization. We want the equivalence
1690 so that if we have to reload this register, we can reload the
1691 constant, rather than extending the lifespan of the register. */
1692 if (reg_is_remote_constant_p (src, insn, get_insns ()))
1695 /* Scan forward to find the next instruction that
1696 uses the output operand. If the operand dies here,
1697 then replace it in both instructions with
1700 for (length = s_length = 0, p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
1702 if (GET_CODE (p) == CALL_INSN)
1703 replace_in_call_usage (& CALL_INSN_FUNCTION_USAGE (p),
1704 REGNO (dst), src, p);
1706 /* ??? We can't scan past the end of a basic block without updating
1707 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
1708 if (perhaps_ends_bb_p (p))
1710 else if (! INSN_P (p))
1717 if (reg_set_p (src, p) || reg_set_p (dst, p)
1718 || (GET_CODE (PATTERN (p)) == USE
1719 && reg_overlap_mentioned_p (src, XEXP (PATTERN (p), 0))))
1722 /* See if all of DST dies in P. This test is
1723 slightly more conservative than it needs to be. */
1724 if ((dst_note = find_regno_note (p, REG_DEAD, REGNO (dst)))
1725 && (GET_MODE (XEXP (dst_note, 0)) == GET_MODE (dst)))
1727 /* If we would be moving INSN, check that we won't move it
1728 into the shadow of a live a live flags register. */
1729 /* ??? We only try to move it in front of P, although
1730 we could move it anywhere between OVERLAP and P. */
1731 if (overlap && GET_MODE (PREV_INSN (p)) != VOIDmode)
1737 rtx set2 = NULL_RTX;
1739 /* If an optimization is done, the value of SRC while P
1740 is executed will be changed. Check that this is OK. */
1741 if (reg_overlap_mentioned_p (src, PATTERN (p)))
1743 for (q = p; q; q = NEXT_INSN (q))
1745 /* ??? We can't scan past the end of a basic block without
1746 updating the register lifetime info
1747 (REG_DEAD/basic_block_live_at_start). */
1748 if (perhaps_ends_bb_p (q))
1753 else if (! INSN_P (q))
1755 else if (reg_overlap_mentioned_p (src, PATTERN (q))
1756 || reg_set_p (src, q))
1760 set2 = single_set (q);
1761 if (! q || ! set2 || GET_CODE (SET_SRC (set2)) != code
1762 || XEXP (SET_SRC (set2), 0) != src
1763 || GET_CODE (XEXP (SET_SRC (set2), 1)) != CONST_INT
1764 || (SET_DEST (set2) != src
1765 && ! find_reg_note (q, REG_DEAD, src)))
1767 /* If this is a PLUS, we can still save a register by doing
1770 src -= insn_const; .
1771 This also gives opportunities for subsequent
1772 optimizations in the backward pass, so do it there. */
1773 if (code == PLUS && backward
1774 /* Don't do this if we can likely tie DST to SET_DEST
1775 of P later; we can't do this tying here if we got a
1777 && ! (dst_note && ! REG_N_CALLS_CROSSED (REGNO (dst))
1779 && GET_CODE (SET_DEST (single_set (p))) == REG
1780 && (REGNO (SET_DEST (single_set (p)))
1781 < FIRST_PSEUDO_REGISTER))
1782 /* We may only emit an insn directly after P if we
1783 are not in the shadow of a live flags register. */
1784 && GET_MODE (p) == VOIDmode)
1789 newconst = -insn_const;
1797 newconst = INTVAL (XEXP (SET_SRC (set2), 1)) - insn_const;
1798 /* Reject out of range shifts. */
1801 || ((unsigned HOST_WIDE_INT) newconst
1802 >= (GET_MODE_BITSIZE (GET_MODE
1803 (SET_SRC (set2)))))))
1808 if (SET_DEST (set2) != src)
1809 post_inc_set = set2;
1812 /* We use 1 as last argument to validate_change so that all
1813 changes are accepted or rejected together by apply_change_group
1814 when it is called by validate_replace_rtx . */
1815 validate_change (q, &XEXP (SET_SRC (set2), 1),
1816 GEN_INT (newconst), 1);
1818 validate_change (insn, recog_data.operand_loc[match_number], src, 1);
1819 if (validate_replace_rtx (dst, src_subreg, p))
1824 if (reg_overlap_mentioned_p (dst, PATTERN (p)))
1826 if (! src_note && reg_overlap_mentioned_p (src, PATTERN (p)))
1828 /* INSN was already checked to be movable wrt. the registers that it
1829 sets / uses when we found no REG_DEAD note for src on it, but it
1830 still might clobber the flags register. We'll have to check that
1831 we won't insert it into the shadow of a live flags register when
1832 we finally know where we are to move it. */
1834 src_note = find_reg_note (p, REG_DEAD, src);
1837 /* If we have passed a call instruction, and the pseudo-reg SRC is not
1838 already live across a call, then don't perform the optimization. */
1839 if (GET_CODE (p) == CALL_INSN)
1841 if (REG_N_CALLS_CROSSED (REGNO (src)) == 0)
1855 /* Remove the death note for DST from P. */
1856 remove_note (p, dst_note);
1859 post_inc = emit_insn_after (copy_rtx (PATTERN (insn)), p);
1860 if ((HAVE_PRE_INCREMENT || HAVE_PRE_DECREMENT)
1862 && try_auto_increment (search_end, post_inc, 0, src, newconst, 1))
1864 validate_change (insn, &XEXP (SET_SRC (set), 1), GEN_INT (insn_const), 0);
1865 REG_N_SETS (REGNO (src))++;
1866 REG_LIVE_LENGTH (REGNO (src))++;
1870 /* The lifetime of src and dest overlap,
1871 but we can change this by moving insn. */
1872 rtx pat = PATTERN (insn);
1874 remove_note (overlap, src_note);
1875 if ((HAVE_POST_INCREMENT || HAVE_POST_DECREMENT)
1877 && try_auto_increment (overlap, insn, 0, src, insn_const, 0))
1881 rtx notes = REG_NOTES (insn);
1883 emit_insn_after_with_line_notes (pat, PREV_INSN (p), insn);
1884 PUT_CODE (insn, NOTE);
1885 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
1886 NOTE_SOURCE_FILE (insn) = 0;
1887 /* emit_insn_after_with_line_notes has no
1888 return value, so search for the new insn. */
1890 while (! INSN_P (insn) || PATTERN (insn) != pat)
1891 insn = PREV_INSN (insn);
1893 REG_NOTES (insn) = notes;
1896 /* Sometimes we'd generate src = const; src += n;
1897 if so, replace the instruction that set src
1898 in the first place. */
1900 if (! overlap && (code == PLUS || code == MINUS))
1902 rtx note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
1903 rtx q, set2 = NULL_RTX;
1904 int num_calls2 = 0, s_length2 = 0;
1906 if (note && CONSTANT_P (XEXP (note, 0)))
1908 for (q = PREV_INSN (insn); q; q = PREV_INSN(q))
1910 /* ??? We can't scan past the end of a basic block without
1911 updating the register lifetime info
1912 (REG_DEAD/basic_block_live_at_start). */
1913 if (perhaps_ends_bb_p (q))
1918 else if (! INSN_P (q))
1922 if (reg_set_p (src, q))
1924 set2 = single_set (q);
1927 if (reg_overlap_mentioned_p (src, PATTERN (q)))
1932 if (GET_CODE (p) == CALL_INSN)
1935 if (q && set2 && SET_DEST (set2) == src && CONSTANT_P (SET_SRC (set2))
1936 && validate_change (insn, &SET_SRC (set), XEXP (note, 0), 0))
1939 NOTE_LINE_NUMBER (q) = NOTE_INSN_DELETED;
1940 NOTE_SOURCE_FILE (q) = 0;
1941 REG_N_SETS (REGNO (src))--;
1942 REG_N_CALLS_CROSSED (REGNO (src)) -= num_calls2;
1943 REG_LIVE_LENGTH (REGNO (src)) -= s_length2;
1949 if ((HAVE_PRE_INCREMENT || HAVE_PRE_DECREMENT)
1950 && (code == PLUS || code == MINUS) && insn_const
1951 && try_auto_increment (p, insn, 0, src, insn_const, 1))
1953 else if ((HAVE_POST_INCREMENT || HAVE_POST_DECREMENT)
1955 && try_auto_increment (p, post_inc, post_inc_set, src, newconst, 0))
1957 /* If post_inc still prevails, try to find an
1958 insn where it can be used as a pre-in/decrement.
1959 If code is MINUS, this was already tried. */
1960 if (post_inc && code == PLUS
1961 /* Check that newconst is likely to be usable
1962 in a pre-in/decrement before starting the search. */
1963 && ((HAVE_PRE_INCREMENT && newconst > 0 && newconst <= MOVE_MAX)
1964 || (HAVE_PRE_DECREMENT && newconst < 0 && newconst >= -MOVE_MAX))
1965 && exact_log2 (newconst))
1969 inc_dest = post_inc_set ? SET_DEST (post_inc_set) : src;
1970 for (q = post_inc; (q = NEXT_INSN (q)); )
1972 /* ??? We can't scan past the end of a basic block without updating
1973 the register lifetime info
1974 (REG_DEAD/basic_block_live_at_start). */
1975 if (perhaps_ends_bb_p (q))
1977 else if (! INSN_P (q))
1979 else if (src != inc_dest
1980 && (reg_overlap_mentioned_p (src, PATTERN (q))
1981 || reg_set_p (src, q)))
1983 else if (reg_set_p (inc_dest, q))
1985 else if (reg_overlap_mentioned_p (inc_dest, PATTERN (q)))
1987 try_auto_increment (q, post_inc,
1988 post_inc_set, inc_dest, newconst, 1);
1994 /* Move the death note for DST to INSN if it is used
1996 if (reg_overlap_mentioned_p (dst, PATTERN (insn)))
1998 XEXP (dst_note, 1) = REG_NOTES (insn);
1999 REG_NOTES (insn) = dst_note;
2004 /* Move the death note for SRC from INSN to P. */
2006 remove_note (insn, src_note);
2007 XEXP (src_note, 1) = REG_NOTES (p);
2008 REG_NOTES (p) = src_note;
2010 REG_N_CALLS_CROSSED (REGNO (src)) += s_num_calls;
2013 REG_N_SETS (REGNO (src))++;
2014 REG_N_SETS (REGNO (dst))--;
2016 REG_N_CALLS_CROSSED (REGNO (dst)) -= num_calls;
2018 REG_LIVE_LENGTH (REGNO (src)) += s_length;
2019 if (REG_LIVE_LENGTH (REGNO (dst)) >= 0)
2021 REG_LIVE_LENGTH (REGNO (dst)) -= length;
2022 /* REG_LIVE_LENGTH is only an approximation after
2023 combine if sched is not run, so make sure that we
2024 still have a reasonable value. */
2025 if (REG_LIVE_LENGTH (REGNO (dst)) < 2)
2026 REG_LIVE_LENGTH (REGNO (dst)) = 2;
2028 if (regmove_dump_file)
2029 fprintf (regmove_dump_file,
2030 "Fixed operand %d of insn %d matching operand %d.\n",
2031 operand_number, INSN_UID (insn), match_number);
2036 /* return nonzero if X is stable and mentions no regsiters but for
2037 mentioning SRC or mentioning / changing DST . If in doubt, presume
2039 The rationale is that we want to check if we can move an insn easily
2040 while just paying attention to SRC and DST. A register is considered
2041 stable if it has the RTX_UNCHANGING_P bit set, but that would still
2042 leave the burden to update REG_DEAD / REG_UNUSED notes, so we don't
2043 want any registers but SRC and DST. */
2045 stable_and_no_regs_but_for_p (x, src, dst)
2048 RTX_CODE code = GET_CODE (x);
2049 switch (GET_RTX_CLASS (code))
2051 case '<': case '1': case 'c': case '2': case 'b': case '3':
2054 const char *fmt = GET_RTX_FORMAT (code);
2055 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2057 && ! stable_and_no_regs_but_for_p (XEXP (x, i), src, dst))
2063 return x == src || x == dst;
2064 /* If this is a MEM, look inside - there might be a register hidden in
2065 the address of an unchanging MEM. */
2067 && ! stable_and_no_regs_but_for_p (XEXP (x, 0), src, dst))
2071 return ! rtx_unstable_p (x);
2075 /* Track stack adjustments and stack memory references. Attempt to
2076 reduce the number of stack adjustments by back-propogating across
2077 the memory references.
2079 This is intended primarily for use with targets that do not define
2080 ACCUMULATE_OUTGOING_ARGS. It is of significantly more value to
2081 targets that define PREFERRED_STACK_BOUNDARY more aligned than
2082 STACK_BOUNDARY (e.g. x86), or if not all registers can be pushed
2083 (e.g. x86 fp regs) which would ordinarily have to be implemented
2084 as a sub/mov pair due to restrictions in calls.c.
2086 Propogation stops when any of the insns that need adjusting are
2087 (a) no longer valid because we've exceeded their range, (b) a
2088 non-trivial push instruction, or (c) a call instruction.
2090 Restriction B is based on the assumption that push instructions
2091 are smaller or faster. If a port really wants to remove all
2092 pushes, it should have defined ACCUMULATE_OUTGOING_ARGS. The
2093 one exception that is made is for an add immediately followed
2096 /* This structure records stack memory references between stack adjusting
2101 HOST_WIDE_INT sp_offset;
2103 struct csa_memlist *next;
2106 static int stack_memref_p PARAMS ((rtx));
2107 static rtx single_set_for_csa PARAMS ((rtx));
2108 static void free_csa_memlist PARAMS ((struct csa_memlist *));
2109 static struct csa_memlist *record_one_stack_memref
2110 PARAMS ((rtx, rtx *, struct csa_memlist *));
2111 static int try_apply_stack_adjustment
2112 PARAMS ((rtx, struct csa_memlist *, HOST_WIDE_INT, HOST_WIDE_INT));
2113 static void combine_stack_adjustments_for_block PARAMS ((basic_block));
2114 static int record_stack_memrefs PARAMS ((rtx *, void *));
2117 /* Main entry point for stack adjustment combination. */
2120 combine_stack_adjustments ()
2124 for (i = 0; i < n_basic_blocks; ++i)
2125 combine_stack_adjustments_for_block (BASIC_BLOCK (i));
2128 /* Recognize a MEM of the form (sp) or (plus sp const). */
2134 if (GET_CODE (x) != MEM)
2138 if (x == stack_pointer_rtx)
2140 if (GET_CODE (x) == PLUS
2141 && XEXP (x, 0) == stack_pointer_rtx
2142 && GET_CODE (XEXP (x, 1)) == CONST_INT)
2148 /* Recognize either normal single_set or the hack in i386.md for
2149 tying fp and sp adjustments. */
2152 single_set_for_csa (insn)
2156 rtx tmp = single_set (insn);
2160 if (GET_CODE (insn) != INSN
2161 || GET_CODE (PATTERN (insn)) != PARALLEL)
2164 tmp = PATTERN (insn);
2165 if (GET_CODE (XVECEXP (tmp, 0, 0)) != SET)
2168 for (i = 1; i < XVECLEN (tmp, 0); ++i)
2170 rtx this = XVECEXP (tmp, 0, i);
2172 /* The special case is allowing a no-op set. */
2173 if (GET_CODE (this) == SET
2174 && SET_SRC (this) == SET_DEST (this))
2176 else if (GET_CODE (this) != CLOBBER
2177 && GET_CODE (this) != USE)
2181 return XVECEXP (tmp, 0, 0);
2184 /* Free the list of csa_memlist nodes. */
2187 free_csa_memlist (memlist)
2188 struct csa_memlist *memlist;
2190 struct csa_memlist *next;
2191 for (; memlist ; memlist = next)
2193 next = memlist->next;
2198 /* Create a new csa_memlist node from the given memory reference.
2199 It is already known that the memory is stack_memref_p. */
2201 static struct csa_memlist *
2202 record_one_stack_memref (insn, mem, next_memlist)
2204 struct csa_memlist *next_memlist;
2206 struct csa_memlist *ml;
2208 ml = (struct csa_memlist *) xmalloc (sizeof (*ml));
2210 if (XEXP (*mem, 0) == stack_pointer_rtx)
2213 ml->sp_offset = INTVAL (XEXP (XEXP (*mem, 0), 1));
2217 ml->next = next_memlist;
2222 /* Attempt to apply ADJUST to the stack adjusting insn INSN, as well
2223 as each of the memories in MEMLIST. Return true on success. */
2226 try_apply_stack_adjustment (insn, memlist, new_adjust, delta)
2228 struct csa_memlist *memlist;
2229 HOST_WIDE_INT new_adjust, delta;
2231 struct csa_memlist *ml;
2234 /* We know INSN matches single_set_for_csa, because that's what we
2235 recognized earlier. However, if INSN is not single_set, it is
2236 doing double duty as a barrier for frame pointer memory accesses,
2237 which we are not recording. Therefore, an adjust insn that is not
2238 single_set may not have a positive delta applied. */
2240 if (delta > 0 && ! single_set (insn))
2242 set = single_set_for_csa (insn);
2243 validate_change (insn, &XEXP (SET_SRC (set), 1), GEN_INT (new_adjust), 1);
2245 for (ml = memlist; ml ; ml = ml->next)
2247 HOST_WIDE_INT c = ml->sp_offset - delta;
2248 rtx new = gen_rtx_MEM (GET_MODE (*ml->mem),
2249 plus_constant (stack_pointer_rtx, c));
2251 /* Don't reference memory below the stack pointer. */
2258 MEM_COPY_ATTRIBUTES (new, *ml->mem);
2259 validate_change (ml->insn, ml->mem, new, 1);
2262 if (apply_change_group ())
2264 /* Succeeded. Update our knowledge of the memory references. */
2265 for (ml = memlist; ml ; ml = ml->next)
2266 ml->sp_offset -= delta;
2274 /* Called via for_each_rtx and used to record all stack memory references in
2275 the insn and discard all other stack pointer references. */
2276 struct record_stack_memrefs_data
2279 struct csa_memlist *memlist;
2283 record_stack_memrefs (xp, data)
2288 struct record_stack_memrefs_data *d =
2289 (struct record_stack_memrefs_data *) data;
2292 switch (GET_CODE (x))
2295 if (!reg_mentioned_p (stack_pointer_rtx, x))
2297 /* We are not able to handle correctly all possible memrefs containing
2298 stack pointer, so this check is neccesary. */
2299 if (stack_memref_p (x))
2301 d->memlist = record_one_stack_memref (d->insn, xp, d->memlist);
2306 /* ??? We want be able to handle non-memory stack pointer
2307 references later. For now just discard all insns refering to
2308 stack pointer outside mem expressions. We would probably
2309 want to teach validate_replace to simplify expressions first.
2311 We can't just compare with STACK_POINTER_RTX because the
2312 reference to the stack pointer might be in some other mode.
2313 In particular, an explict clobber in an asm statement will
2314 result in a QImode clober. */
2315 if (REGNO (x) == STACK_POINTER_REGNUM)
2324 /* Subroutine of combine_stack_adjustments, called for each basic block. */
2327 combine_stack_adjustments_for_block (bb)
2330 HOST_WIDE_INT last_sp_adjust = 0;
2331 rtx last_sp_set = NULL_RTX;
2332 struct csa_memlist *memlist = NULL;
2335 struct record_stack_memrefs_data data;
2337 for (insn = bb->head; ; insn = next)
2341 pending_delete = NULL_RTX;
2342 next = NEXT_INSN (insn);
2344 if (! INSN_P (insn))
2347 set = single_set_for_csa (insn);
2350 rtx dest = SET_DEST (set);
2351 rtx src = SET_SRC (set);
2353 /* Find constant additions to the stack pointer. */
2354 if (dest == stack_pointer_rtx
2355 && GET_CODE (src) == PLUS
2356 && XEXP (src, 0) == stack_pointer_rtx
2357 && GET_CODE (XEXP (src, 1)) == CONST_INT)
2359 HOST_WIDE_INT this_adjust = INTVAL (XEXP (src, 1));
2361 /* If we've not seen an adjustment previously, record
2362 it now and continue. */
2366 last_sp_adjust = this_adjust;
2370 /* If not all recorded memrefs can be adjusted, or the
2371 adjustment is now too large for a constant addition,
2372 we cannot merge the two stack adjustments. */
2373 if (! try_apply_stack_adjustment (last_sp_set, memlist,
2374 last_sp_adjust + this_adjust,
2377 free_csa_memlist (memlist);
2380 last_sp_adjust = this_adjust;
2385 pending_delete = insn;
2386 last_sp_adjust += this_adjust;
2388 /* If, by some accident, the adjustments cancel out,
2389 delete both insns and start from scratch. */
2390 if (last_sp_adjust == 0)
2392 if (last_sp_set == bb->head)
2393 bb->head = NEXT_INSN (last_sp_set);
2394 flow_delete_insn (last_sp_set);
2396 free_csa_memlist (memlist);
2398 last_sp_set = NULL_RTX;
2404 /* Find a predecrement of exactly the previous adjustment and
2405 turn it into a direct store. Obviously we can't do this if
2406 there were any intervening uses of the stack pointer. */
2408 && GET_CODE (dest) == MEM
2409 && ((GET_CODE (XEXP (dest, 0)) == PRE_DEC
2411 == (HOST_WIDE_INT) GET_MODE_SIZE (GET_MODE (dest))))
2412 || (GET_CODE (XEXP (dest, 0)) == PRE_MODIFY
2413 && GET_CODE (XEXP (XEXP (dest, 0), 1)) == PLUS
2414 && XEXP (XEXP (XEXP (dest, 0), 1), 0) == stack_pointer_rtx
2415 && (GET_CODE (XEXP (XEXP (XEXP (dest, 0), 1), 1))
2417 && (INTVAL (XEXP (XEXP (XEXP (dest, 0), 1), 1))
2418 == -last_sp_adjust)))
2419 && XEXP (XEXP (dest, 0), 0) == stack_pointer_rtx
2420 && ! reg_mentioned_p (stack_pointer_rtx, src)
2421 && memory_address_p (GET_MODE (dest), stack_pointer_rtx)
2422 && validate_change (insn, &SET_DEST (set),
2423 change_address (dest, VOIDmode,
2424 stack_pointer_rtx), 0))
2426 if (last_sp_set == bb->head)
2427 bb->head = NEXT_INSN (last_sp_set);
2428 flow_delete_insn (last_sp_set);
2430 free_csa_memlist (memlist);
2432 last_sp_set = NULL_RTX;
2439 data.memlist = memlist;
2440 if (GET_CODE (insn) != CALL_INSN && last_sp_set
2441 && !for_each_rtx (&PATTERN (insn), record_stack_memrefs, &data))
2443 memlist = data.memlist;
2446 memlist = data.memlist;
2448 /* Otherwise, we were not able to process the instruction.
2449 Do not continue collecting data across such a one. */
2451 && (GET_CODE (insn) == CALL_INSN
2452 || reg_mentioned_p (stack_pointer_rtx, PATTERN (insn))))
2454 free_csa_memlist (memlist);
2456 last_sp_set = NULL_RTX;
2461 if (insn == bb->end)
2465 flow_delete_insn (pending_delete);
2470 bb->end = PREV_INSN (pending_delete);
2471 flow_delete_insn (pending_delete);