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"
46 /* Turn STACK_GROWS_DOWNWARD into a boolean. */
47 #ifdef STACK_GROWS_DOWNWARD
48 #undef STACK_GROWS_DOWNWARD
49 #define STACK_GROWS_DOWNWARD 1
51 #define STACK_GROWS_DOWNWARD 0
54 static int perhaps_ends_bb_p PARAMS ((rtx));
55 static int optimize_reg_copy_1 PARAMS ((rtx, rtx, rtx));
56 static void optimize_reg_copy_2 PARAMS ((rtx, rtx, rtx));
57 static void optimize_reg_copy_3 PARAMS ((rtx, rtx, rtx));
58 static rtx gen_add3_insn PARAMS ((rtx, rtx, rtx));
59 static void copy_src_to_dest PARAMS ((rtx, rtx, rtx, int));
60 static int *regmove_bb_head;
63 int with[MAX_RECOG_OPERANDS];
64 enum { READ, WRITE, READWRITE } use[MAX_RECOG_OPERANDS];
65 int commutative[MAX_RECOG_OPERANDS];
66 int early_clobber[MAX_RECOG_OPERANDS];
69 static rtx discover_flags_reg PARAMS ((void));
70 static void mark_flags_life_zones PARAMS ((rtx));
71 static void flags_set_1 PARAMS ((rtx, rtx, void *));
73 static int try_auto_increment PARAMS ((rtx, rtx, rtx, rtx, HOST_WIDE_INT, int));
74 static int find_matches PARAMS ((rtx, struct match *));
75 static void replace_in_call_usage PARAMS ((rtx *, int, rtx, rtx));
76 static int fixup_match_1 PARAMS ((rtx, rtx, rtx, rtx, rtx, int, int, int, FILE *))
78 static int reg_is_remote_constant_p PARAMS ((rtx, rtx, rtx));
79 static int stable_and_no_regs_but_for_p PARAMS ((rtx, rtx, rtx));
80 static int regclass_compatible_p PARAMS ((int, int));
81 static int replacement_quality PARAMS ((rtx));
82 static int fixup_match_2 PARAMS ((rtx, rtx, rtx, rtx, FILE *));
84 /* Return non-zero if registers with CLASS1 and CLASS2 can be merged without
85 causing too much register allocation problems. */
87 regclass_compatible_p (class0, class1)
90 return (class0 == class1
91 || (reg_class_subset_p (class0, class1)
92 && ! CLASS_LIKELY_SPILLED_P (class0))
93 || (reg_class_subset_p (class1, class0)
94 && ! CLASS_LIKELY_SPILLED_P (class1)));
97 /* Generate and return an insn body to add r1 and c,
98 storing the result in r0. */
100 gen_add3_insn (r0, r1, c)
103 int icode = (int) add_optab->handlers[(int) GET_MODE (r0)].insn_code;
105 if (icode == CODE_FOR_nothing
106 || ! ((*insn_data[icode].operand[0].predicate)
107 (r0, insn_data[icode].operand[0].mode))
108 || ! ((*insn_data[icode].operand[1].predicate)
109 (r1, insn_data[icode].operand[1].mode))
110 || ! ((*insn_data[icode].operand[2].predicate)
111 (c, insn_data[icode].operand[2].mode)))
114 return (GEN_FCN (icode) (r0, r1, c));
118 /* INC_INSN is an instruction that adds INCREMENT to REG.
119 Try to fold INC_INSN as a post/pre in/decrement into INSN.
120 Iff INC_INSN_SET is nonzero, inc_insn has a destination different from src.
121 Return nonzero for success. */
123 try_auto_increment (insn, inc_insn, inc_insn_set, reg, increment, pre)
124 rtx reg, insn, inc_insn ,inc_insn_set;
125 HOST_WIDE_INT increment;
128 enum rtx_code inc_code;
130 rtx pset = single_set (insn);
133 /* Can't use the size of SET_SRC, we might have something like
134 (sign_extend:SI (mem:QI ... */
135 rtx use = find_use_as_address (pset, reg, 0);
136 if (use != 0 && use != (rtx) 1)
138 int size = GET_MODE_SIZE (GET_MODE (use));
140 || (HAVE_POST_INCREMENT
141 && pre == 0 && (inc_code = POST_INC, increment == size))
142 || (HAVE_PRE_INCREMENT
143 && pre == 1 && (inc_code = PRE_INC, increment == size))
144 || (HAVE_POST_DECREMENT
145 && pre == 0 && (inc_code = POST_DEC, increment == -size))
146 || (HAVE_PRE_DECREMENT
147 && pre == 1 && (inc_code = PRE_DEC, increment == -size))
153 &SET_SRC (inc_insn_set),
154 XEXP (SET_SRC (inc_insn_set), 0), 1);
155 validate_change (insn, &XEXP (use, 0),
156 gen_rtx_fmt_e (inc_code, Pmode, reg), 1);
157 if (apply_change_group ())
159 /* If there is a REG_DEAD note on this insn, we must
160 change this not to REG_UNUSED meaning that the register
161 is set, but the value is dead. Failure to do so will
162 result in a sched1 abort -- when it recomputes lifetime
163 information, the number of REG_DEAD notes will have
165 rtx note = find_reg_note (insn, REG_DEAD, reg);
167 PUT_MODE (note, REG_UNUSED);
170 = gen_rtx_EXPR_LIST (REG_INC,
171 reg, REG_NOTES (insn));
174 PUT_CODE (inc_insn, NOTE);
175 NOTE_LINE_NUMBER (inc_insn) = NOTE_INSN_DELETED;
176 NOTE_SOURCE_FILE (inc_insn) = 0;
186 /* Determine if the pattern generated by add_optab has a clobber,
187 such as might be issued for a flags hard register. To make the
188 code elsewhere simpler, we handle cc0 in this same framework.
190 Return the register if one was discovered. Return NULL_RTX if
191 if no flags were found. Return pc_rtx if we got confused. */
194 discover_flags_reg ()
197 tmp = gen_rtx_REG (word_mode, 10000);
198 tmp = gen_add3_insn (tmp, tmp, GEN_INT (2));
200 /* If we get something that isn't a simple set, or a
201 [(set ..) (clobber ..)], this whole function will go wrong. */
202 if (GET_CODE (tmp) == SET)
204 else if (GET_CODE (tmp) == PARALLEL)
208 if (XVECLEN (tmp, 0) != 2)
210 tmp = XVECEXP (tmp, 0, 1);
211 if (GET_CODE (tmp) != CLOBBER)
215 /* Don't do anything foolish if the md wanted to clobber a
216 scratch or something. We only care about hard regs.
217 Moreover we don't like the notion of subregs of hard regs. */
218 if (GET_CODE (tmp) == SUBREG
219 && GET_CODE (SUBREG_REG (tmp)) == REG
220 && REGNO (SUBREG_REG (tmp)) < FIRST_PSEUDO_REGISTER)
222 found = (GET_CODE (tmp) == REG && REGNO (tmp) < FIRST_PSEUDO_REGISTER);
224 return (found ? tmp : NULL_RTX);
230 /* It is a tedious task identifying when the flags register is live and
231 when it is safe to optimize. Since we process the instruction stream
232 multiple times, locate and record these live zones by marking the
233 mode of the instructions --
235 QImode is used on the instruction at which the flags becomes live.
237 HImode is used within the range (exclusive) that the flags are
238 live. Thus the user of the flags is not marked.
240 All other instructions are cleared to VOIDmode. */
242 /* Used to communicate with flags_set_1. */
243 static rtx flags_set_1_rtx;
244 static int flags_set_1_set;
247 mark_flags_life_zones (flags)
255 /* If we found a flags register on a cc0 host, bail. */
256 if (flags == NULL_RTX)
258 else if (flags != cc0_rtx)
262 /* Simple cases first: if no flags, clear all modes. If confusing,
263 mark the entire function as being in a flags shadow. */
264 if (flags == NULL_RTX || flags == pc_rtx)
266 enum machine_mode mode = (flags ? HImode : VOIDmode);
268 for (insn = get_insns(); insn; insn = NEXT_INSN (insn))
269 PUT_MODE (insn, mode);
277 flags_regno = REGNO (flags);
278 flags_nregs = HARD_REGNO_NREGS (flags_regno, GET_MODE (flags));
280 flags_set_1_rtx = flags;
282 /* Process each basic block. */
283 for (block = n_basic_blocks - 1; block >= 0; block--)
288 insn = BLOCK_HEAD (block);
289 end = BLOCK_END (block);
291 /* Look out for the (unlikely) case of flags being live across
292 basic block boundaries. */
297 for (i = 0; i < flags_nregs; ++i)
298 live |= REGNO_REG_SET_P (BASIC_BLOCK (block)->global_live_at_start,
305 /* Process liveness in reverse order of importance --
306 alive, death, birth. This lets more important info
307 overwrite the mode of lesser info. */
312 /* In the cc0 case, death is not marked in reg notes,
313 but is instead the mere use of cc0 when it is alive. */
314 if (live && reg_mentioned_p (cc0_rtx, PATTERN (insn)))
317 /* In the hard reg case, we watch death notes. */
318 if (live && find_regno_note (insn, REG_DEAD, flags_regno))
321 PUT_MODE (insn, (live ? HImode : VOIDmode));
323 /* In either case, birth is denoted simply by it's presence
324 as the destination of a set. */
326 note_stores (PATTERN (insn), flags_set_1, NULL);
330 PUT_MODE (insn, QImode);
334 PUT_MODE (insn, (live ? HImode : VOIDmode));
338 insn = NEXT_INSN (insn);
343 /* A subroutine of mark_flags_life_zones, called through note_stores. */
346 flags_set_1 (x, pat, data)
348 void *data ATTRIBUTE_UNUSED;
350 if (GET_CODE (pat) == SET
351 && reg_overlap_mentioned_p (x, flags_set_1_rtx))
355 static int *regno_src_regno;
357 /* Indicate how good a choice REG (which appears as a source) is to replace
358 a destination register with. The higher the returned value, the better
359 the choice. The main objective is to avoid using a register that is
360 a candidate for tying to a hard register, since the output might in
361 turn be a candidate to be tied to a different hard register. */
363 replacement_quality(reg)
368 /* Bad if this isn't a register at all. */
369 if (GET_CODE (reg) != REG)
372 /* If this register is not meant to get a hard register,
373 it is a poor choice. */
374 if (REG_LIVE_LENGTH (REGNO (reg)) < 0)
377 src_regno = regno_src_regno[REGNO (reg)];
379 /* If it was not copied from another register, it is fine. */
383 /* Copied from a hard register? */
384 if (src_regno < FIRST_PSEUDO_REGISTER)
387 /* Copied from a pseudo register - not as bad as from a hard register,
388 yet still cumbersome, since the register live length will be lengthened
389 when the registers get tied. */
393 /* Return 1 if INSN might end a basic block. */
395 static int perhaps_ends_bb_p (insn)
398 switch (GET_CODE (insn))
402 /* These always end a basic block. */
406 /* A CALL_INSN might be the last insn of a basic block, if it is inside
407 an EH region or if there are nonlocal gotos. Note that this test is
408 very conservative. */
409 if (nonlocal_goto_handler_labels)
413 return can_throw_internal (insn);
417 /* INSN is a copy from SRC to DEST, both registers, and SRC does not die
420 Search forward to see if SRC dies before either it or DEST is modified,
421 but don't scan past the end of a basic block. If so, we can replace SRC
422 with DEST and let SRC die in INSN.
424 This will reduce the number of registers live in that range and may enable
425 DEST to be tied to SRC, thus often saving one register in addition to a
426 register-register copy. */
429 optimize_reg_copy_1 (insn, dest, src)
437 int sregno = REGNO (src);
438 int dregno = REGNO (dest);
440 /* We don't want to mess with hard regs if register classes are small. */
442 || (SMALL_REGISTER_CLASSES
443 && (sregno < FIRST_PSEUDO_REGISTER
444 || dregno < FIRST_PSEUDO_REGISTER))
445 /* We don't see all updates to SP if they are in an auto-inc memory
446 reference, so we must disallow this optimization on them. */
447 || sregno == STACK_POINTER_REGNUM || dregno == STACK_POINTER_REGNUM)
450 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
452 /* ??? We can't scan past the end of a basic block without updating
453 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
454 if (perhaps_ends_bb_p (p))
456 else if (! INSN_P (p))
459 if (reg_set_p (src, p) || reg_set_p (dest, p)
460 /* Don't change a USE of a register. */
461 || (GET_CODE (PATTERN (p)) == USE
462 && reg_overlap_mentioned_p (src, XEXP (PATTERN (p), 0))))
465 /* See if all of SRC dies in P. This test is slightly more
466 conservative than it needs to be. */
467 if ((note = find_regno_note (p, REG_DEAD, sregno)) != 0
468 && GET_MODE (XEXP (note, 0)) == GET_MODE (src))
476 /* We can do the optimization. Scan forward from INSN again,
477 replacing regs as we go. Set FAILED if a replacement can't
478 be done. In that case, we can't move the death note for SRC.
479 This should be rare. */
481 /* Set to stop at next insn. */
482 for (q = next_real_insn (insn);
483 q != next_real_insn (p);
484 q = next_real_insn (q))
486 if (reg_overlap_mentioned_p (src, PATTERN (q)))
488 /* If SRC is a hard register, we might miss some
489 overlapping registers with validate_replace_rtx,
490 so we would have to undo it. We can't if DEST is
491 present in the insn, so fail in that combination
493 if (sregno < FIRST_PSEUDO_REGISTER
494 && reg_mentioned_p (dest, PATTERN (q)))
497 /* Replace all uses and make sure that the register
498 isn't still present. */
499 else if (validate_replace_rtx (src, dest, q)
500 && (sregno >= FIRST_PSEUDO_REGISTER
501 || ! reg_overlap_mentioned_p (src,
506 validate_replace_rtx (dest, src, q);
511 /* For SREGNO, count the total number of insns scanned.
512 For DREGNO, count the total number of insns scanned after
513 passing the death note for DREGNO. */
518 /* If the insn in which SRC dies is a CALL_INSN, don't count it
519 as a call that has been crossed. Otherwise, count it. */
520 if (q != p && GET_CODE (q) == CALL_INSN)
522 /* Similarly, total calls for SREGNO, total calls beyond
523 the death note for DREGNO. */
529 /* If DEST dies here, remove the death note and save it for
530 later. Make sure ALL of DEST dies here; again, this is
531 overly conservative. */
533 && (dest_death = find_regno_note (q, REG_DEAD, dregno)) != 0)
535 if (GET_MODE (XEXP (dest_death, 0)) != GET_MODE (dest))
536 failed = 1, dest_death = 0;
538 remove_note (q, dest_death);
544 /* These counters need to be updated if and only if we are
545 going to move the REG_DEAD note. */
546 if (sregno >= FIRST_PSEUDO_REGISTER)
548 if (REG_LIVE_LENGTH (sregno) >= 0)
550 REG_LIVE_LENGTH (sregno) -= s_length;
551 /* REG_LIVE_LENGTH is only an approximation after
552 combine if sched is not run, so make sure that we
553 still have a reasonable value. */
554 if (REG_LIVE_LENGTH (sregno) < 2)
555 REG_LIVE_LENGTH (sregno) = 2;
558 REG_N_CALLS_CROSSED (sregno) -= s_n_calls;
561 /* Move death note of SRC from P to INSN. */
562 remove_note (p, note);
563 XEXP (note, 1) = REG_NOTES (insn);
564 REG_NOTES (insn) = note;
567 /* DEST is also dead if INSN has a REG_UNUSED note for DEST. */
569 && (dest_death = find_regno_note (insn, REG_UNUSED, dregno)))
571 PUT_REG_NOTE_KIND (dest_death, REG_DEAD);
572 remove_note (insn, dest_death);
575 /* Put death note of DEST on P if we saw it die. */
578 XEXP (dest_death, 1) = REG_NOTES (p);
579 REG_NOTES (p) = dest_death;
581 if (dregno >= FIRST_PSEUDO_REGISTER)
583 /* If and only if we are moving the death note for DREGNO,
584 then we need to update its counters. */
585 if (REG_LIVE_LENGTH (dregno) >= 0)
586 REG_LIVE_LENGTH (dregno) += d_length;
587 REG_N_CALLS_CROSSED (dregno) += d_n_calls;
594 /* If SRC is a hard register which is set or killed in some other
595 way, we can't do this optimization. */
596 else if (sregno < FIRST_PSEUDO_REGISTER
597 && dead_or_set_p (p, src))
603 /* INSN is a copy of SRC to DEST, in which SRC dies. See if we now have
604 a sequence of insns that modify DEST followed by an insn that sets
605 SRC to DEST in which DEST dies, with no prior modification of DEST.
606 (There is no need to check if the insns in between actually modify
607 DEST. We should not have cases where DEST is not modified, but
608 the optimization is safe if no such modification is detected.)
609 In that case, we can replace all uses of DEST, starting with INSN and
610 ending with the set of SRC to DEST, with SRC. We do not do this
611 optimization if a CALL_INSN is crossed unless SRC already crosses a
612 call or if DEST dies before the copy back to SRC.
614 It is assumed that DEST and SRC are pseudos; it is too complicated to do
615 this for hard registers since the substitutions we may make might fail. */
618 optimize_reg_copy_2 (insn, dest, src)
625 int sregno = REGNO (src);
626 int dregno = REGNO (dest);
628 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
630 /* ??? We can't scan past the end of a basic block without updating
631 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
632 if (perhaps_ends_bb_p (p))
634 else if (! INSN_P (p))
637 set = single_set (p);
638 if (set && SET_SRC (set) == dest && SET_DEST (set) == src
639 && find_reg_note (p, REG_DEAD, dest))
641 /* We can do the optimization. Scan forward from INSN again,
642 replacing regs as we go. */
644 /* Set to stop at next insn. */
645 for (q = insn; q != NEXT_INSN (p); q = NEXT_INSN (q))
648 if (reg_mentioned_p (dest, PATTERN (q)))
649 PATTERN (q) = replace_rtx (PATTERN (q), dest, src);
652 if (GET_CODE (q) == CALL_INSN)
654 REG_N_CALLS_CROSSED (dregno)--;
655 REG_N_CALLS_CROSSED (sregno)++;
659 remove_note (p, find_reg_note (p, REG_DEAD, dest));
660 REG_N_DEATHS (dregno)--;
661 remove_note (insn, find_reg_note (insn, REG_DEAD, src));
662 REG_N_DEATHS (sregno)--;
666 if (reg_set_p (src, p)
667 || find_reg_note (p, REG_DEAD, dest)
668 || (GET_CODE (p) == CALL_INSN && REG_N_CALLS_CROSSED (sregno) == 0))
672 /* INSN is a ZERO_EXTEND or SIGN_EXTEND of SRC to DEST.
673 Look if SRC dies there, and if it is only set once, by loading
674 it from memory. If so, try to encorporate the zero/sign extension
675 into the memory read, change SRC to the mode of DEST, and alter
676 the remaining accesses to use the appropriate SUBREG. This allows
677 SRC and DEST to be tied later. */
679 optimize_reg_copy_3 (insn, dest, src)
684 rtx src_reg = XEXP (src, 0);
685 int src_no = REGNO (src_reg);
686 int dst_no = REGNO (dest);
688 enum machine_mode old_mode;
690 if (src_no < FIRST_PSEUDO_REGISTER
691 || dst_no < FIRST_PSEUDO_REGISTER
692 || ! find_reg_note (insn, REG_DEAD, src_reg)
693 || REG_N_SETS (src_no) != 1)
695 for (p = PREV_INSN (insn); p && ! reg_set_p (src_reg, p); p = PREV_INSN (p))
696 /* ??? We can't scan past the end of a basic block without updating
697 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
698 if (perhaps_ends_bb_p (p))
704 if (! (set = single_set (p))
705 || GET_CODE (SET_SRC (set)) != MEM
706 || SET_DEST (set) != src_reg)
709 /* Be conserative: although this optimization is also valid for
710 volatile memory references, that could cause trouble in later passes. */
711 if (MEM_VOLATILE_P (SET_SRC (set)))
714 /* Do not use a SUBREG to truncate from one mode to another if truncation
716 if (GET_MODE_BITSIZE (GET_MODE (src_reg)) <= GET_MODE_BITSIZE (GET_MODE (src))
717 && !TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (GET_MODE (src)),
718 GET_MODE_BITSIZE (GET_MODE (src_reg))))
721 old_mode = GET_MODE (src_reg);
722 PUT_MODE (src_reg, GET_MODE (src));
723 XEXP (src, 0) = SET_SRC (set);
725 /* Include this change in the group so that it's easily undone if
726 one of the changes in the group is invalid. */
727 validate_change (p, &SET_SRC (set), src, 1);
729 /* Now walk forward making additional replacements. We want to be able
730 to undo all the changes if a later substitution fails. */
731 subreg = gen_lowpart_SUBREG (old_mode, src_reg);
732 while (p = NEXT_INSN (p), p != insn)
737 /* Make a tenative change. */
738 validate_replace_rtx_group (src_reg, subreg, p);
741 validate_replace_rtx_group (src, src_reg, insn);
743 /* Now see if all the changes are valid. */
744 if (! apply_change_group ())
746 /* One or more changes were no good. Back out everything. */
747 PUT_MODE (src_reg, old_mode);
748 XEXP (src, 0) = src_reg;
753 /* If we were not able to update the users of src to use dest directly, try
754 instead moving the value to dest directly before the operation. */
757 copy_src_to_dest (insn, src, dest, old_max_uid)
776 /* A REG_LIVE_LENGTH of -1 indicates the register is equivalent to a constant
777 or memory location and is used infrequently; a REG_LIVE_LENGTH of -2 is
778 parameter when there is no frame pointer that is not allocated a register.
779 For now, we just reject them, rather than incrementing the live length. */
781 if (GET_CODE (src) == REG
782 && REG_LIVE_LENGTH (REGNO (src)) > 0
783 && GET_CODE (dest) == REG
784 && !RTX_UNCHANGING_P (dest)
785 && REG_LIVE_LENGTH (REGNO (dest)) > 0
786 && (set = single_set (insn)) != NULL_RTX
787 && !reg_mentioned_p (dest, SET_SRC (set))
788 && GET_MODE (src) == GET_MODE (dest))
790 int old_num_regs = reg_rtx_no;
792 /* Generate the src->dest move. */
794 emit_move_insn (dest, src);
795 seq = gen_sequence ();
797 /* If this sequence uses new registers, we may not use it. */
798 if (old_num_regs != reg_rtx_no
799 || ! validate_replace_rtx (src, dest, insn))
801 /* We have to restore reg_rtx_no to its old value, lest
802 recompute_reg_usage will try to compute the usage of the
803 new regs, yet reg_n_info is not valid for them. */
804 reg_rtx_no = old_num_regs;
807 emit_insn_before (seq, insn);
808 move_insn = PREV_INSN (insn);
809 p_move_notes = ®_NOTES (move_insn);
810 p_insn_notes = ®_NOTES (insn);
812 /* Move any notes mentioning src to the move instruction */
813 for (link = REG_NOTES (insn); link != NULL_RTX; link = next)
815 next = XEXP (link, 1);
816 if (XEXP (link, 0) == src)
818 *p_move_notes = link;
819 p_move_notes = &XEXP (link, 1);
823 *p_insn_notes = link;
824 p_insn_notes = &XEXP (link, 1);
828 *p_move_notes = NULL_RTX;
829 *p_insn_notes = NULL_RTX;
831 /* Is the insn the head of a basic block? If so extend it */
832 insn_uid = INSN_UID (insn);
833 move_uid = INSN_UID (move_insn);
834 if (insn_uid < old_max_uid)
836 bb = regmove_bb_head[insn_uid];
839 BLOCK_HEAD (bb) = move_insn;
840 regmove_bb_head[insn_uid] = -1;
844 /* Update the various register tables. */
845 dest_regno = REGNO (dest);
846 REG_N_SETS (dest_regno) ++;
847 REG_LIVE_LENGTH (dest_regno)++;
848 if (REGNO_FIRST_UID (dest_regno) == insn_uid)
849 REGNO_FIRST_UID (dest_regno) = move_uid;
851 src_regno = REGNO (src);
852 if (! find_reg_note (move_insn, REG_DEAD, src))
853 REG_LIVE_LENGTH (src_regno)++;
855 if (REGNO_FIRST_UID (src_regno) == insn_uid)
856 REGNO_FIRST_UID (src_regno) = move_uid;
858 if (REGNO_LAST_UID (src_regno) == insn_uid)
859 REGNO_LAST_UID (src_regno) = move_uid;
861 if (REGNO_LAST_NOTE_UID (src_regno) == insn_uid)
862 REGNO_LAST_NOTE_UID (src_regno) = move_uid;
867 /* Return whether REG is set in only one location, and is set to a
868 constant, but is set in a different basic block from INSN (an
869 instructions which uses REG). In this case REG is equivalent to a
870 constant, and we don't want to break that equivalence, because that
871 may increase register pressure and make reload harder. If REG is
872 set in the same basic block as INSN, we don't worry about it,
873 because we'll probably need a register anyhow (??? but what if REG
874 is used in a different basic block as well as this one?). FIRST is
875 the first insn in the function. */
878 reg_is_remote_constant_p (reg, insn, first)
885 if (REG_N_SETS (REGNO (reg)) != 1)
888 /* Look for the set. */
889 for (p = LOG_LINKS (insn); p; p = XEXP (p, 1))
893 if (REG_NOTE_KIND (p) != 0)
895 s = single_set (XEXP (p, 0));
897 && GET_CODE (SET_DEST (s)) == REG
898 && REGNO (SET_DEST (s)) == REGNO (reg))
900 /* The register is set in the same basic block. */
905 for (p = first; p && p != insn; p = NEXT_INSN (p))
913 && GET_CODE (SET_DEST (s)) == REG
914 && REGNO (SET_DEST (s)) == REGNO (reg))
916 /* This is the instruction which sets REG. If there is a
917 REG_EQUAL note, then REG is equivalent to a constant. */
918 if (find_reg_note (p, REG_EQUAL, NULL_RTX))
927 /* INSN is adding a CONST_INT to a REG. We search backwards looking for
928 another add immediate instruction with the same source and dest registers,
929 and if we find one, we change INSN to an increment, and return 1. If
930 no changes are made, we return 0.
933 (set (reg100) (plus reg1 offset1))
935 (set (reg100) (plus reg1 offset2))
937 (set (reg100) (plus reg1 offset1))
939 (set (reg100) (plus reg100 offset2-offset1)) */
941 /* ??? What does this comment mean? */
942 /* cse disrupts preincrement / postdecrement squences when it finds a
943 hard register as ultimate source, like the frame pointer. */
946 fixup_match_2 (insn, dst, src, offset, regmove_dump_file)
947 rtx insn, dst, src, offset;
948 FILE *regmove_dump_file;
950 rtx p, dst_death = 0;
951 int length, num_calls = 0;
953 /* If SRC dies in INSN, we'd have to move the death note. This is
954 considered to be very unlikely, so we just skip the optimization
956 if (find_regno_note (insn, REG_DEAD, REGNO (src)))
959 /* Scan backward to find the first instruction that sets DST. */
961 for (length = 0, p = PREV_INSN (insn); p; p = PREV_INSN (p))
965 /* ??? We can't scan past the end of a basic block without updating
966 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
967 if (perhaps_ends_bb_p (p))
969 else if (! INSN_P (p))
972 if (find_regno_note (p, REG_DEAD, REGNO (dst)))
977 pset = single_set (p);
978 if (pset && SET_DEST (pset) == dst
979 && GET_CODE (SET_SRC (pset)) == PLUS
980 && XEXP (SET_SRC (pset), 0) == src
981 && GET_CODE (XEXP (SET_SRC (pset), 1)) == CONST_INT)
983 HOST_WIDE_INT newconst
984 = INTVAL (offset) - INTVAL (XEXP (SET_SRC (pset), 1));
985 rtx add = gen_add3_insn (dst, dst, GEN_INT (newconst));
987 if (add && validate_change (insn, &PATTERN (insn), add, 0))
989 /* Remove the death note for DST from DST_DEATH. */
992 remove_death (REGNO (dst), dst_death);
993 REG_LIVE_LENGTH (REGNO (dst)) += length;
994 REG_N_CALLS_CROSSED (REGNO (dst)) += num_calls;
997 if (regmove_dump_file)
998 fprintf (regmove_dump_file,
999 "Fixed operand of insn %d.\n",
1003 for (p = PREV_INSN (insn); p; p = PREV_INSN (p))
1005 if (GET_CODE (p) == CODE_LABEL
1006 || GET_CODE (p) == JUMP_INSN)
1010 if (reg_overlap_mentioned_p (dst, PATTERN (p)))
1012 if (try_auto_increment (p, insn, 0, dst, newconst, 0))
1017 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
1019 if (GET_CODE (p) == CODE_LABEL
1020 || GET_CODE (p) == JUMP_INSN)
1024 if (reg_overlap_mentioned_p (dst, PATTERN (p)))
1026 try_auto_increment (p, insn, 0, dst, newconst, 1);
1035 if (reg_set_p (dst, PATTERN (p)))
1038 /* If we have passed a call instruction, and the
1039 pseudo-reg SRC is not already live across a call,
1040 then don't perform the optimization. */
1041 /* reg_set_p is overly conservative for CALL_INSNS, thinks that all
1042 hard regs are clobbered. Thus, we only use it for src for
1044 if (GET_CODE (p) == CALL_INSN)
1049 if (REG_N_CALLS_CROSSED (REGNO (src)) == 0)
1052 if (call_used_regs [REGNO (dst)]
1053 || find_reg_fusage (p, CLOBBER, dst))
1056 else if (reg_set_p (src, PATTERN (p)))
1064 regmove_optimize (f, nregs, regmove_dump_file)
1067 FILE *regmove_dump_file;
1069 int old_max_uid = get_max_uid ();
1074 rtx copy_src, copy_dst;
1076 /* ??? Hack. Regmove doesn't examine the CFG, and gets mightily
1077 confused by non-call exceptions ending blocks. */
1078 if (flag_non_call_exceptions)
1081 /* Find out where a potential flags register is live, and so that we
1082 can supress some optimizations in those zones. */
1083 mark_flags_life_zones (discover_flags_reg ());
1085 regno_src_regno = (int *) xmalloc (sizeof *regno_src_regno * nregs);
1086 for (i = nregs; --i >= 0; ) regno_src_regno[i] = -1;
1088 regmove_bb_head = (int *) xmalloc (sizeof (int) * (old_max_uid + 1));
1089 for (i = old_max_uid; i >= 0; i--) regmove_bb_head[i] = -1;
1090 for (i = 0; i < n_basic_blocks; i++)
1091 regmove_bb_head[INSN_UID (BLOCK_HEAD (i))] = i;
1093 /* A forward/backward pass. Replace output operands with input operands. */
1095 for (pass = 0; pass <= 2; pass++)
1097 if (! flag_regmove && pass >= flag_expensive_optimizations)
1100 if (regmove_dump_file)
1101 fprintf (regmove_dump_file, "Starting %s pass...\n",
1102 pass ? "backward" : "forward");
1104 for (insn = pass ? get_last_insn () : f; insn;
1105 insn = pass ? PREV_INSN (insn) : NEXT_INSN (insn))
1108 int op_no, match_no;
1110 set = single_set (insn);
1114 if (flag_expensive_optimizations && ! pass
1115 && (GET_CODE (SET_SRC (set)) == SIGN_EXTEND
1116 || GET_CODE (SET_SRC (set)) == ZERO_EXTEND)
1117 && GET_CODE (XEXP (SET_SRC (set), 0)) == REG
1118 && GET_CODE (SET_DEST(set)) == REG)
1119 optimize_reg_copy_3 (insn, SET_DEST (set), SET_SRC (set));
1121 if (flag_expensive_optimizations && ! pass
1122 && GET_CODE (SET_SRC (set)) == REG
1123 && GET_CODE (SET_DEST(set)) == REG)
1125 /* If this is a register-register copy where SRC is not dead,
1126 see if we can optimize it. If this optimization succeeds,
1127 it will become a copy where SRC is dead. */
1128 if ((find_reg_note (insn, REG_DEAD, SET_SRC (set))
1129 || optimize_reg_copy_1 (insn, SET_DEST (set), SET_SRC (set)))
1130 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
1132 /* Similarly for a pseudo-pseudo copy when SRC is dead. */
1133 if (REGNO (SET_SRC (set)) >= FIRST_PSEUDO_REGISTER)
1134 optimize_reg_copy_2 (insn, SET_DEST (set), SET_SRC (set));
1135 if (regno_src_regno[REGNO (SET_DEST (set))] < 0
1136 && SET_SRC (set) != SET_DEST (set))
1138 int srcregno = REGNO (SET_SRC(set));
1139 if (regno_src_regno[srcregno] >= 0)
1140 srcregno = regno_src_regno[srcregno];
1141 regno_src_regno[REGNO (SET_DEST (set))] = srcregno;
1148 if (! find_matches (insn, &match))
1151 /* Now scan through the operands looking for a source operand
1152 which is supposed to match the destination operand.
1153 Then scan forward for an instruction which uses the dest
1155 If it dies there, then replace the dest in both operands with
1156 the source operand. */
1158 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1160 rtx src, dst, src_subreg;
1161 enum reg_class src_class, dst_class;
1163 match_no = match.with[op_no];
1165 /* Nothing to do if the two operands aren't supposed to match. */
1169 src = recog_data.operand[op_no];
1170 dst = recog_data.operand[match_no];
1172 if (GET_CODE (src) != REG)
1176 if (GET_CODE (dst) == SUBREG
1177 && GET_MODE_SIZE (GET_MODE (dst))
1178 >= GET_MODE_SIZE (GET_MODE (SUBREG_REG (dst))))
1181 = gen_rtx_SUBREG (GET_MODE (SUBREG_REG (dst)),
1182 src, SUBREG_BYTE (dst));
1183 dst = SUBREG_REG (dst);
1185 if (GET_CODE (dst) != REG
1186 || REGNO (dst) < FIRST_PSEUDO_REGISTER)
1189 if (REGNO (src) < FIRST_PSEUDO_REGISTER)
1191 if (match.commutative[op_no] < op_no)
1192 regno_src_regno[REGNO (dst)] = REGNO (src);
1196 if (REG_LIVE_LENGTH (REGNO (src)) < 0)
1199 /* op_no/src must be a read-only operand, and
1200 match_operand/dst must be a write-only operand. */
1201 if (match.use[op_no] != READ
1202 || match.use[match_no] != WRITE)
1205 if (match.early_clobber[match_no]
1206 && count_occurrences (PATTERN (insn), src, 0) > 1)
1209 /* Make sure match_operand is the destination. */
1210 if (recog_data.operand[match_no] != SET_DEST (set))
1213 /* If the operands already match, then there is nothing to do. */
1214 if (operands_match_p (src, dst))
1217 /* But in the commutative case, we might find a better match. */
1218 if (match.commutative[op_no] >= 0)
1220 rtx comm = recog_data.operand[match.commutative[op_no]];
1221 if (operands_match_p (comm, dst)
1222 && (replacement_quality (comm)
1223 >= replacement_quality (src)))
1227 src_class = reg_preferred_class (REGNO (src));
1228 dst_class = reg_preferred_class (REGNO (dst));
1229 if (! regclass_compatible_p (src_class, dst_class))
1232 if (fixup_match_1 (insn, set, src, src_subreg, dst, pass,
1240 /* A backward pass. Replace input operands with output operands. */
1242 if (regmove_dump_file)
1243 fprintf (regmove_dump_file, "Starting backward pass...\n");
1245 for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
1249 int op_no, match_no;
1252 if (! find_matches (insn, &match))
1255 /* Now scan through the operands looking for a destination operand
1256 which is supposed to match a source operand.
1257 Then scan backward for an instruction which sets the source
1258 operand. If safe, then replace the source operand with the
1259 dest operand in both instructions. */
1261 copy_src = NULL_RTX;
1262 copy_dst = NULL_RTX;
1263 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1265 rtx set, p, src, dst;
1266 rtx src_note, dst_note;
1268 enum reg_class src_class, dst_class;
1271 match_no = match.with[op_no];
1273 /* Nothing to do if the two operands aren't supposed to match. */
1277 dst = recog_data.operand[match_no];
1278 src = recog_data.operand[op_no];
1280 if (GET_CODE (src) != REG)
1283 if (GET_CODE (dst) != REG
1284 || REGNO (dst) < FIRST_PSEUDO_REGISTER
1285 || REG_LIVE_LENGTH (REGNO (dst)) < 0)
1288 /* If the operands already match, then there is nothing to do. */
1289 if (operands_match_p (src, dst))
1292 if (match.commutative[op_no] >= 0)
1294 rtx comm = recog_data.operand[match.commutative[op_no]];
1295 if (operands_match_p (comm, dst))
1299 set = single_set (insn);
1303 /* match_no/dst must be a write-only operand, and
1304 operand_operand/src must be a read-only operand. */
1305 if (match.use[op_no] != READ
1306 || match.use[match_no] != WRITE)
1309 if (match.early_clobber[match_no]
1310 && count_occurrences (PATTERN (insn), src, 0) > 1)
1313 /* Make sure match_no is the destination. */
1314 if (recog_data.operand[match_no] != SET_DEST (set))
1317 if (REGNO (src) < FIRST_PSEUDO_REGISTER)
1319 if (GET_CODE (SET_SRC (set)) == PLUS
1320 && GET_CODE (XEXP (SET_SRC (set), 1)) == CONST_INT
1321 && XEXP (SET_SRC (set), 0) == src
1322 && fixup_match_2 (insn, dst, src,
1323 XEXP (SET_SRC (set), 1),
1328 src_class = reg_preferred_class (REGNO (src));
1329 dst_class = reg_preferred_class (REGNO (dst));
1330 if (! regclass_compatible_p (src_class, dst_class))
1340 /* Can not modify an earlier insn to set dst if this insn
1341 uses an old value in the source. */
1342 if (reg_overlap_mentioned_p (dst, SET_SRC (set)))
1352 if (! (src_note = find_reg_note (insn, REG_DEAD, src)))
1363 /* If src is set once in a different basic block,
1364 and is set equal to a constant, then do not use
1365 it for this optimization, as this would make it
1366 no longer equivalent to a constant. */
1368 if (reg_is_remote_constant_p (src, insn, f))
1379 if (regmove_dump_file)
1380 fprintf (regmove_dump_file,
1381 "Could fix operand %d of insn %d matching operand %d.\n",
1382 op_no, INSN_UID (insn), match_no);
1384 /* Scan backward to find the first instruction that uses
1385 the input operand. If the operand is set here, then
1386 replace it in both instructions with match_no. */
1388 for (length = 0, p = PREV_INSN (insn); p; p = PREV_INSN (p))
1392 /* ??? We can't scan past the end of a basic block without
1393 updating the register lifetime info
1394 (REG_DEAD/basic_block_live_at_start). */
1395 if (perhaps_ends_bb_p (p))
1397 else if (! INSN_P (p))
1402 /* ??? See if all of SRC is set in P. This test is much
1403 more conservative than it needs to be. */
1404 pset = single_set (p);
1405 if (pset && SET_DEST (pset) == src)
1407 /* We use validate_replace_rtx, in case there
1408 are multiple identical source operands. All of
1409 them have to be changed at the same time. */
1410 if (validate_replace_rtx (src, dst, insn))
1412 if (validate_change (p, &SET_DEST (pset),
1417 /* Change all source operands back.
1418 This modifies the dst as a side-effect. */
1419 validate_replace_rtx (dst, src, insn);
1420 /* Now make sure the dst is right. */
1421 validate_change (insn,
1422 recog_data.operand_loc[match_no],
1429 if (reg_overlap_mentioned_p (src, PATTERN (p))
1430 || reg_overlap_mentioned_p (dst, PATTERN (p)))
1433 /* If we have passed a call instruction, and the
1434 pseudo-reg DST is not already live across a call,
1435 then don't perform the optimization. */
1436 if (GET_CODE (p) == CALL_INSN)
1440 if (REG_N_CALLS_CROSSED (REGNO (dst)) == 0)
1449 /* Remove the death note for SRC from INSN. */
1450 remove_note (insn, src_note);
1451 /* Move the death note for SRC to P if it is used
1453 if (reg_overlap_mentioned_p (src, PATTERN (p)))
1455 XEXP (src_note, 1) = REG_NOTES (p);
1456 REG_NOTES (p) = src_note;
1458 /* If there is a REG_DEAD note for DST on P, then remove
1459 it, because DST is now set there. */
1460 if ((dst_note = find_reg_note (p, REG_DEAD, dst)))
1461 remove_note (p, dst_note);
1463 dstno = REGNO (dst);
1464 srcno = REGNO (src);
1466 REG_N_SETS (dstno)++;
1467 REG_N_SETS (srcno)--;
1469 REG_N_CALLS_CROSSED (dstno) += num_calls;
1470 REG_N_CALLS_CROSSED (srcno) -= num_calls;
1472 REG_LIVE_LENGTH (dstno) += length;
1473 if (REG_LIVE_LENGTH (srcno) >= 0)
1475 REG_LIVE_LENGTH (srcno) -= length;
1476 /* REG_LIVE_LENGTH is only an approximation after
1477 combine if sched is not run, so make sure that we
1478 still have a reasonable value. */
1479 if (REG_LIVE_LENGTH (srcno) < 2)
1480 REG_LIVE_LENGTH (srcno) = 2;
1483 if (regmove_dump_file)
1484 fprintf (regmove_dump_file,
1485 "Fixed operand %d of insn %d matching operand %d.\n",
1486 op_no, INSN_UID (insn), match_no);
1492 /* If we weren't able to replace any of the alternatives, try an
1493 alternative appoach of copying the source to the destination. */
1494 if (!success && copy_src != NULL_RTX)
1495 copy_src_to_dest (insn, copy_src, copy_dst, old_max_uid);
1500 /* In fixup_match_1, some insns may have been inserted after basic block
1501 ends. Fix that here. */
1502 for (i = 0; i < n_basic_blocks; i++)
1504 rtx end = BLOCK_END (i);
1506 rtx next = NEXT_INSN (new);
1507 while (next != 0 && INSN_UID (next) >= old_max_uid
1508 && (i == n_basic_blocks - 1 || BLOCK_HEAD (i + 1) != next))
1509 new = next, next = NEXT_INSN (new);
1510 BLOCK_END (i) = new;
1515 free (regno_src_regno);
1516 free (regmove_bb_head);
1519 /* Returns nonzero if INSN's pattern has matching constraints for any operand.
1520 Returns 0 if INSN can't be recognized, or if the alternative can't be
1523 Initialize the info in MATCHP based on the constraints. */
1526 find_matches (insn, matchp)
1528 struct match *matchp;
1530 int likely_spilled[MAX_RECOG_OPERANDS];
1532 int any_matches = 0;
1534 extract_insn (insn);
1535 if (! constrain_operands (0))
1538 /* Must initialize this before main loop, because the code for
1539 the commutative case may set matches for operands other than
1541 for (op_no = recog_data.n_operands; --op_no >= 0; )
1542 matchp->with[op_no] = matchp->commutative[op_no] = -1;
1544 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1550 p = recog_data.constraints[op_no];
1552 likely_spilled[op_no] = 0;
1553 matchp->use[op_no] = READ;
1554 matchp->early_clobber[op_no] = 0;
1556 matchp->use[op_no] = WRITE;
1558 matchp->use[op_no] = READWRITE;
1560 for (;*p && i < which_alternative; p++)
1564 while ((c = *p++) != '\0' && c != ',')
1572 matchp->early_clobber[op_no] = 1;
1575 matchp->commutative[op_no] = op_no + 1;
1576 matchp->commutative[op_no + 1] = op_no;
1578 case '0': case '1': case '2': case '3': case '4':
1579 case '5': case '6': case '7': case '8': case '9':
1581 if (c < op_no && likely_spilled[(unsigned char) c])
1583 matchp->with[op_no] = c;
1585 if (matchp->commutative[op_no] >= 0)
1586 matchp->with[matchp->commutative[op_no]] = c;
1588 case 'a': case 'b': case 'c': case 'd': case 'e': case 'f': case 'h':
1589 case 'j': case 'k': case 'l': case 'p': case 'q': case 't': case 'u':
1590 case 'v': case 'w': case 'x': case 'y': case 'z': case 'A': case 'B':
1591 case 'C': case 'D': case 'W': case 'Y': case 'Z':
1592 if (CLASS_LIKELY_SPILLED_P (REG_CLASS_FROM_LETTER ((unsigned char)c)))
1593 likely_spilled[op_no] = 1;
1600 /* Try to replace all occurrences of DST_REG with SRC in LOC, that is
1601 assumed to be in INSN. */
1604 replace_in_call_usage (loc, dst_reg, src, insn)
1618 code = GET_CODE (x);
1621 if (REGNO (x) != dst_reg)
1624 validate_change (insn, loc, src, 1);
1629 /* Process each of our operands recursively. */
1630 fmt = GET_RTX_FORMAT (code);
1631 for (i = 0; i < GET_RTX_LENGTH (code); i++, fmt++)
1633 replace_in_call_usage (&XEXP (x, i), dst_reg, src, insn);
1634 else if (*fmt == 'E')
1635 for (j = 0; j < XVECLEN (x, i); j++)
1636 replace_in_call_usage (& XVECEXP (x, i, j), dst_reg, src, insn);
1639 /* Try to replace output operand DST in SET, with input operand SRC. SET is
1640 the only set in INSN. INSN has just been recognized and constrained.
1641 SRC is operand number OPERAND_NUMBER in INSN.
1642 DST is operand number MATCH_NUMBER in INSN.
1643 If BACKWARD is nonzero, we have been called in a backward pass.
1644 Return nonzero for success. */
1647 fixup_match_1 (insn, set, src, src_subreg, dst, backward, operand_number,
1648 match_number, regmove_dump_file)
1649 rtx insn, set, src, src_subreg, dst;
1650 int backward, operand_number, match_number;
1651 FILE *regmove_dump_file;
1654 rtx post_inc = 0, post_inc_set = 0, search_end = 0;
1656 int num_calls = 0, s_num_calls = 0;
1657 enum rtx_code code = NOTE;
1658 HOST_WIDE_INT insn_const = 0, newconst;
1659 rtx overlap = 0; /* need to move insn ? */
1660 rtx src_note = find_reg_note (insn, REG_DEAD, src), dst_note = NULL_RTX;
1661 int length, s_length;
1663 /* If SRC is marked as unchanging, we may not change it.
1664 ??? Maybe we could get better code by removing the unchanging bit
1665 instead, and changing it back if we don't succeed? */
1666 if (RTX_UNCHANGING_P (src))
1671 /* Look for (set (regX) (op regA constX))
1672 (set (regY) (op regA constY))
1674 (set (regA) (op regA constX)).
1675 (set (regY) (op regA constY-constX)).
1676 This works for add and shift operations, if
1677 regA is dead after or set by the second insn. */
1679 code = GET_CODE (SET_SRC (set));
1680 if ((code == PLUS || code == LSHIFTRT
1681 || code == ASHIFT || code == ASHIFTRT)
1682 && XEXP (SET_SRC (set), 0) == src
1683 && GET_CODE (XEXP (SET_SRC (set), 1)) == CONST_INT)
1684 insn_const = INTVAL (XEXP (SET_SRC (set), 1));
1685 else if (! stable_and_no_regs_but_for_p (SET_SRC (set), src, dst))
1688 /* We might find a src_note while scanning. */
1692 if (regmove_dump_file)
1693 fprintf (regmove_dump_file,
1694 "Could fix operand %d of insn %d matching operand %d.\n",
1695 operand_number, INSN_UID (insn), match_number);
1697 /* If SRC is equivalent to a constant set in a different basic block,
1698 then do not use it for this optimization. We want the equivalence
1699 so that if we have to reload this register, we can reload the
1700 constant, rather than extending the lifespan of the register. */
1701 if (reg_is_remote_constant_p (src, insn, get_insns ()))
1704 /* Scan forward to find the next instruction that
1705 uses the output operand. If the operand dies here,
1706 then replace it in both instructions with
1709 for (length = s_length = 0, p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
1711 if (GET_CODE (p) == CALL_INSN)
1712 replace_in_call_usage (& CALL_INSN_FUNCTION_USAGE (p),
1713 REGNO (dst), src, p);
1715 /* ??? We can't scan past the end of a basic block without updating
1716 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
1717 if (perhaps_ends_bb_p (p))
1719 else if (! INSN_P (p))
1726 if (reg_set_p (src, p) || reg_set_p (dst, p)
1727 || (GET_CODE (PATTERN (p)) == USE
1728 && reg_overlap_mentioned_p (src, XEXP (PATTERN (p), 0))))
1731 /* See if all of DST dies in P. This test is
1732 slightly more conservative than it needs to be. */
1733 if ((dst_note = find_regno_note (p, REG_DEAD, REGNO (dst)))
1734 && (GET_MODE (XEXP (dst_note, 0)) == GET_MODE (dst)))
1736 /* If we would be moving INSN, check that we won't move it
1737 into the shadow of a live a live flags register. */
1738 /* ??? We only try to move it in front of P, although
1739 we could move it anywhere between OVERLAP and P. */
1740 if (overlap && GET_MODE (PREV_INSN (p)) != VOIDmode)
1746 rtx set2 = NULL_RTX;
1748 /* If an optimization is done, the value of SRC while P
1749 is executed will be changed. Check that this is OK. */
1750 if (reg_overlap_mentioned_p (src, PATTERN (p)))
1752 for (q = p; q; q = NEXT_INSN (q))
1754 /* ??? We can't scan past the end of a basic block without
1755 updating the register lifetime info
1756 (REG_DEAD/basic_block_live_at_start). */
1757 if (perhaps_ends_bb_p (q))
1762 else if (! INSN_P (q))
1764 else if (reg_overlap_mentioned_p (src, PATTERN (q))
1765 || reg_set_p (src, q))
1769 set2 = single_set (q);
1770 if (! q || ! set2 || GET_CODE (SET_SRC (set2)) != code
1771 || XEXP (SET_SRC (set2), 0) != src
1772 || GET_CODE (XEXP (SET_SRC (set2), 1)) != CONST_INT
1773 || (SET_DEST (set2) != src
1774 && ! find_reg_note (q, REG_DEAD, src)))
1776 /* If this is a PLUS, we can still save a register by doing
1779 src -= insn_const; .
1780 This also gives opportunities for subsequent
1781 optimizations in the backward pass, so do it there. */
1782 if (code == PLUS && backward
1783 /* Don't do this if we can likely tie DST to SET_DEST
1784 of P later; we can't do this tying here if we got a
1786 && ! (dst_note && ! REG_N_CALLS_CROSSED (REGNO (dst))
1788 && GET_CODE (SET_DEST (single_set (p))) == REG
1789 && (REGNO (SET_DEST (single_set (p)))
1790 < FIRST_PSEUDO_REGISTER))
1791 /* We may only emit an insn directly after P if we
1792 are not in the shadow of a live flags register. */
1793 && GET_MODE (p) == VOIDmode)
1798 newconst = -insn_const;
1806 newconst = INTVAL (XEXP (SET_SRC (set2), 1)) - insn_const;
1807 /* Reject out of range shifts. */
1810 || ((unsigned HOST_WIDE_INT) newconst
1811 >= (GET_MODE_BITSIZE (GET_MODE
1812 (SET_SRC (set2)))))))
1817 if (SET_DEST (set2) != src)
1818 post_inc_set = set2;
1821 /* We use 1 as last argument to validate_change so that all
1822 changes are accepted or rejected together by apply_change_group
1823 when it is called by validate_replace_rtx . */
1824 validate_change (q, &XEXP (SET_SRC (set2), 1),
1825 GEN_INT (newconst), 1);
1827 validate_change (insn, recog_data.operand_loc[match_number], src, 1);
1828 if (validate_replace_rtx (dst, src_subreg, p))
1833 if (reg_overlap_mentioned_p (dst, PATTERN (p)))
1835 if (! src_note && reg_overlap_mentioned_p (src, PATTERN (p)))
1837 /* INSN was already checked to be movable wrt. the registers that it
1838 sets / uses when we found no REG_DEAD note for src on it, but it
1839 still might clobber the flags register. We'll have to check that
1840 we won't insert it into the shadow of a live flags register when
1841 we finally know where we are to move it. */
1843 src_note = find_reg_note (p, REG_DEAD, src);
1846 /* If we have passed a call instruction, and the pseudo-reg SRC is not
1847 already live across a call, then don't perform the optimization. */
1848 if (GET_CODE (p) == CALL_INSN)
1850 if (REG_N_CALLS_CROSSED (REGNO (src)) == 0)
1864 /* Remove the death note for DST from P. */
1865 remove_note (p, dst_note);
1868 post_inc = emit_insn_after (copy_rtx (PATTERN (insn)), p);
1869 if ((HAVE_PRE_INCREMENT || HAVE_PRE_DECREMENT)
1871 && try_auto_increment (search_end, post_inc, 0, src, newconst, 1))
1873 validate_change (insn, &XEXP (SET_SRC (set), 1), GEN_INT (insn_const), 0);
1874 REG_N_SETS (REGNO (src))++;
1875 REG_LIVE_LENGTH (REGNO (src))++;
1879 /* The lifetime of src and dest overlap,
1880 but we can change this by moving insn. */
1881 rtx pat = PATTERN (insn);
1883 remove_note (overlap, src_note);
1884 if ((HAVE_POST_INCREMENT || HAVE_POST_DECREMENT)
1886 && try_auto_increment (overlap, insn, 0, src, insn_const, 0))
1890 rtx notes = REG_NOTES (insn);
1892 emit_insn_after_with_line_notes (pat, PREV_INSN (p), insn);
1893 PUT_CODE (insn, NOTE);
1894 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
1895 NOTE_SOURCE_FILE (insn) = 0;
1896 /* emit_insn_after_with_line_notes has no
1897 return value, so search for the new insn. */
1899 while (! INSN_P (insn) || PATTERN (insn) != pat)
1900 insn = PREV_INSN (insn);
1902 REG_NOTES (insn) = notes;
1905 /* Sometimes we'd generate src = const; src += n;
1906 if so, replace the instruction that set src
1907 in the first place. */
1909 if (! overlap && (code == PLUS || code == MINUS))
1911 rtx note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
1912 rtx q, set2 = NULL_RTX;
1913 int num_calls2 = 0, s_length2 = 0;
1915 if (note && CONSTANT_P (XEXP (note, 0)))
1917 for (q = PREV_INSN (insn); q; q = PREV_INSN(q))
1919 /* ??? We can't scan past the end of a basic block without
1920 updating the register lifetime info
1921 (REG_DEAD/basic_block_live_at_start). */
1922 if (perhaps_ends_bb_p (q))
1927 else if (! INSN_P (q))
1931 if (reg_set_p (src, q))
1933 set2 = single_set (q);
1936 if (reg_overlap_mentioned_p (src, PATTERN (q)))
1941 if (GET_CODE (p) == CALL_INSN)
1944 if (q && set2 && SET_DEST (set2) == src && CONSTANT_P (SET_SRC (set2))
1945 && validate_change (insn, &SET_SRC (set), XEXP (note, 0), 0))
1948 NOTE_LINE_NUMBER (q) = NOTE_INSN_DELETED;
1949 NOTE_SOURCE_FILE (q) = 0;
1950 REG_N_SETS (REGNO (src))--;
1951 REG_N_CALLS_CROSSED (REGNO (src)) -= num_calls2;
1952 REG_LIVE_LENGTH (REGNO (src)) -= s_length2;
1958 if ((HAVE_PRE_INCREMENT || HAVE_PRE_DECREMENT)
1959 && (code == PLUS || code == MINUS) && insn_const
1960 && try_auto_increment (p, insn, 0, src, insn_const, 1))
1962 else if ((HAVE_POST_INCREMENT || HAVE_POST_DECREMENT)
1964 && try_auto_increment (p, post_inc, post_inc_set, src, newconst, 0))
1966 /* If post_inc still prevails, try to find an
1967 insn where it can be used as a pre-in/decrement.
1968 If code is MINUS, this was already tried. */
1969 if (post_inc && code == PLUS
1970 /* Check that newconst is likely to be usable
1971 in a pre-in/decrement before starting the search. */
1972 && ((HAVE_PRE_INCREMENT && newconst > 0 && newconst <= MOVE_MAX)
1973 || (HAVE_PRE_DECREMENT && newconst < 0 && newconst >= -MOVE_MAX))
1974 && exact_log2 (newconst))
1978 inc_dest = post_inc_set ? SET_DEST (post_inc_set) : src;
1979 for (q = post_inc; (q = NEXT_INSN (q)); )
1981 /* ??? We can't scan past the end of a basic block without updating
1982 the register lifetime info
1983 (REG_DEAD/basic_block_live_at_start). */
1984 if (perhaps_ends_bb_p (q))
1986 else if (! INSN_P (q))
1988 else if (src != inc_dest
1989 && (reg_overlap_mentioned_p (src, PATTERN (q))
1990 || reg_set_p (src, q)))
1992 else if (reg_set_p (inc_dest, q))
1994 else if (reg_overlap_mentioned_p (inc_dest, PATTERN (q)))
1996 try_auto_increment (q, post_inc,
1997 post_inc_set, inc_dest, newconst, 1);
2003 /* Move the death note for DST to INSN if it is used
2005 if (reg_overlap_mentioned_p (dst, PATTERN (insn)))
2007 XEXP (dst_note, 1) = REG_NOTES (insn);
2008 REG_NOTES (insn) = dst_note;
2013 /* Move the death note for SRC from INSN to P. */
2015 remove_note (insn, src_note);
2016 XEXP (src_note, 1) = REG_NOTES (p);
2017 REG_NOTES (p) = src_note;
2019 REG_N_CALLS_CROSSED (REGNO (src)) += s_num_calls;
2022 REG_N_SETS (REGNO (src))++;
2023 REG_N_SETS (REGNO (dst))--;
2025 REG_N_CALLS_CROSSED (REGNO (dst)) -= num_calls;
2027 REG_LIVE_LENGTH (REGNO (src)) += s_length;
2028 if (REG_LIVE_LENGTH (REGNO (dst)) >= 0)
2030 REG_LIVE_LENGTH (REGNO (dst)) -= length;
2031 /* REG_LIVE_LENGTH is only an approximation after
2032 combine if sched is not run, so make sure that we
2033 still have a reasonable value. */
2034 if (REG_LIVE_LENGTH (REGNO (dst)) < 2)
2035 REG_LIVE_LENGTH (REGNO (dst)) = 2;
2037 if (regmove_dump_file)
2038 fprintf (regmove_dump_file,
2039 "Fixed operand %d of insn %d matching operand %d.\n",
2040 operand_number, INSN_UID (insn), match_number);
2045 /* return nonzero if X is stable and mentions no regsiters but for
2046 mentioning SRC or mentioning / changing DST . If in doubt, presume
2048 The rationale is that we want to check if we can move an insn easily
2049 while just paying attention to SRC and DST. A register is considered
2050 stable if it has the RTX_UNCHANGING_P bit set, but that would still
2051 leave the burden to update REG_DEAD / REG_UNUSED notes, so we don't
2052 want any registers but SRC and DST. */
2054 stable_and_no_regs_but_for_p (x, src, dst)
2057 RTX_CODE code = GET_CODE (x);
2058 switch (GET_RTX_CLASS (code))
2060 case '<': case '1': case 'c': case '2': case 'b': case '3':
2063 const char *fmt = GET_RTX_FORMAT (code);
2064 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2066 && ! stable_and_no_regs_but_for_p (XEXP (x, i), src, dst))
2072 return x == src || x == dst;
2073 /* If this is a MEM, look inside - there might be a register hidden in
2074 the address of an unchanging MEM. */
2076 && ! stable_and_no_regs_but_for_p (XEXP (x, 0), src, dst))
2080 return ! rtx_unstable_p (x);
2084 /* Track stack adjustments and stack memory references. Attempt to
2085 reduce the number of stack adjustments by back-propogating across
2086 the memory references.
2088 This is intended primarily for use with targets that do not define
2089 ACCUMULATE_OUTGOING_ARGS. It is of significantly more value to
2090 targets that define PREFERRED_STACK_BOUNDARY more aligned than
2091 STACK_BOUNDARY (e.g. x86), or if not all registers can be pushed
2092 (e.g. x86 fp regs) which would ordinarily have to be implemented
2093 as a sub/mov pair due to restrictions in calls.c.
2095 Propogation stops when any of the insns that need adjusting are
2096 (a) no longer valid because we've exceeded their range, (b) a
2097 non-trivial push instruction, or (c) a call instruction.
2099 Restriction B is based on the assumption that push instructions
2100 are smaller or faster. If a port really wants to remove all
2101 pushes, it should have defined ACCUMULATE_OUTGOING_ARGS. The
2102 one exception that is made is for an add immediately followed
2105 /* This structure records stack memory references between stack adjusting
2110 HOST_WIDE_INT sp_offset;
2112 struct csa_memlist *next;
2115 static int stack_memref_p PARAMS ((rtx));
2116 static rtx single_set_for_csa PARAMS ((rtx));
2117 static void free_csa_memlist PARAMS ((struct csa_memlist *));
2118 static struct csa_memlist *record_one_stack_memref
2119 PARAMS ((rtx, rtx *, struct csa_memlist *));
2120 static int try_apply_stack_adjustment
2121 PARAMS ((rtx, struct csa_memlist *, HOST_WIDE_INT, HOST_WIDE_INT));
2122 static void combine_stack_adjustments_for_block PARAMS ((basic_block));
2123 static int record_stack_memrefs PARAMS ((rtx *, void *));
2126 /* Main entry point for stack adjustment combination. */
2129 combine_stack_adjustments ()
2133 for (i = 0; i < n_basic_blocks; ++i)
2134 combine_stack_adjustments_for_block (BASIC_BLOCK (i));
2137 /* Recognize a MEM of the form (sp) or (plus sp const). */
2143 if (GET_CODE (x) != MEM)
2147 if (x == stack_pointer_rtx)
2149 if (GET_CODE (x) == PLUS
2150 && XEXP (x, 0) == stack_pointer_rtx
2151 && GET_CODE (XEXP (x, 1)) == CONST_INT)
2157 /* Recognize either normal single_set or the hack in i386.md for
2158 tying fp and sp adjustments. */
2161 single_set_for_csa (insn)
2165 rtx tmp = single_set (insn);
2169 if (GET_CODE (insn) != INSN
2170 || GET_CODE (PATTERN (insn)) != PARALLEL)
2173 tmp = PATTERN (insn);
2174 if (GET_CODE (XVECEXP (tmp, 0, 0)) != SET)
2177 for (i = 1; i < XVECLEN (tmp, 0); ++i)
2179 rtx this = XVECEXP (tmp, 0, i);
2181 /* The special case is allowing a no-op set. */
2182 if (GET_CODE (this) == SET
2183 && SET_SRC (this) == SET_DEST (this))
2185 else if (GET_CODE (this) != CLOBBER
2186 && GET_CODE (this) != USE)
2190 return XVECEXP (tmp, 0, 0);
2193 /* Free the list of csa_memlist nodes. */
2196 free_csa_memlist (memlist)
2197 struct csa_memlist *memlist;
2199 struct csa_memlist *next;
2200 for (; memlist ; memlist = next)
2202 next = memlist->next;
2207 /* Create a new csa_memlist node from the given memory reference.
2208 It is already known that the memory is stack_memref_p. */
2210 static struct csa_memlist *
2211 record_one_stack_memref (insn, mem, next_memlist)
2213 struct csa_memlist *next_memlist;
2215 struct csa_memlist *ml;
2217 ml = (struct csa_memlist *) xmalloc (sizeof (*ml));
2219 if (XEXP (*mem, 0) == stack_pointer_rtx)
2222 ml->sp_offset = INTVAL (XEXP (XEXP (*mem, 0), 1));
2226 ml->next = next_memlist;
2231 /* Attempt to apply ADJUST to the stack adjusting insn INSN, as well
2232 as each of the memories in MEMLIST. Return true on success. */
2235 try_apply_stack_adjustment (insn, memlist, new_adjust, delta)
2237 struct csa_memlist *memlist;
2238 HOST_WIDE_INT new_adjust, delta;
2240 struct csa_memlist *ml;
2243 set = single_set_for_csa (insn);
2244 validate_change (insn, &XEXP (SET_SRC (set), 1), GEN_INT (new_adjust), 1);
2246 for (ml = memlist; ml ; ml = ml->next)
2248 HOST_WIDE_INT c = ml->sp_offset - delta;
2249 rtx new = gen_rtx_MEM (GET_MODE (*ml->mem),
2250 plus_constant (stack_pointer_rtx, c));
2252 MEM_COPY_ATTRIBUTES (new, *ml->mem);
2253 validate_change (ml->insn, ml->mem, new, 1);
2256 if (apply_change_group ())
2258 /* Succeeded. Update our knowledge of the memory references. */
2259 for (ml = memlist; ml ; ml = ml->next)
2260 ml->sp_offset -= delta;
2268 /* Called via for_each_rtx and used to record all stack memory references in
2269 the insn and discard all other stack pointer references. */
2270 struct record_stack_memrefs_data
2273 struct csa_memlist *memlist;
2277 record_stack_memrefs (xp, data)
2282 struct record_stack_memrefs_data *d =
2283 (struct record_stack_memrefs_data *) data;
2286 switch (GET_CODE (x))
2289 if (!reg_mentioned_p (stack_pointer_rtx, x))
2291 /* We are not able to handle correctly all possible memrefs containing
2292 stack pointer, so this check is neccesary. */
2293 if (stack_memref_p (x))
2295 d->memlist = record_one_stack_memref (d->insn, xp, d->memlist);
2300 /* ??? We want be able to handle non-memory stack pointer
2301 references later. For now just discard all insns refering to
2302 stack pointer outside mem expressions. We would probably
2303 want to teach validate_replace to simplify expressions first.
2305 We can't just compare with STACK_POINTER_RTX because the
2306 reference to the stack pointer might be in some other mode.
2307 In particular, an explict clobber in an asm statement will
2308 result in a QImode clober. */
2309 if (REGNO (x) == STACK_POINTER_REGNUM)
2318 /* Subroutine of combine_stack_adjustments, called for each basic block. */
2321 combine_stack_adjustments_for_block (bb)
2324 HOST_WIDE_INT last_sp_adjust = 0;
2325 rtx last_sp_set = NULL_RTX;
2326 struct csa_memlist *memlist = NULL;
2329 struct record_stack_memrefs_data data;
2331 for (insn = bb->head; ; insn = next)
2335 pending_delete = NULL_RTX;
2336 next = NEXT_INSN (insn);
2338 if (! INSN_P (insn))
2341 set = single_set_for_csa (insn);
2344 rtx dest = SET_DEST (set);
2345 rtx src = SET_SRC (set);
2347 /* Find constant additions to the stack pointer. */
2348 if (dest == stack_pointer_rtx
2349 && GET_CODE (src) == PLUS
2350 && XEXP (src, 0) == stack_pointer_rtx
2351 && GET_CODE (XEXP (src, 1)) == CONST_INT)
2353 HOST_WIDE_INT this_adjust = INTVAL (XEXP (src, 1));
2355 /* If we've not seen an adjustment previously, record
2356 it now and continue. */
2360 last_sp_adjust = this_adjust;
2364 /* If not all recorded memrefs can be adjusted, or the
2365 adjustment is now too large for a constant addition,
2366 we cannot merge the two stack adjustments.
2368 Also we need to be carefull to not move stack pointer
2369 such that we create stack accesses outside the allocated
2370 area. We can combine an allocation into the first insn,
2371 or a deallocation into the second insn. We can not
2372 combine an allocation followed by a deallocation.
2374 The only somewhat frequent ocurrence of the later is when
2375 a function allocates a stack frame but does not use it.
2376 For this case, we would need to analyze rtl stream to be
2377 sure that allocated area is really unused. This means not
2378 only checking the memory references, but also all registers
2379 or global memory references possibly containing a stack
2382 Perhaps the best way to address this problem is to teach
2383 gcc not to allocate stack for objects never used. */
2385 /* Combine an allocation into the first instruction. */
2386 if (STACK_GROWS_DOWNWARD ? this_adjust <= 0 : this_adjust >= 0)
2388 if (try_apply_stack_adjustment (last_sp_set, memlist,
2389 last_sp_adjust + this_adjust,
2393 pending_delete = insn;
2394 last_sp_adjust += this_adjust;
2399 /* Otherwise we have a deallocation. Do not combine with
2400 a previous allocation. Combine into the second insn. */
2401 else if (STACK_GROWS_DOWNWARD
2402 ? last_sp_adjust >= 0 : last_sp_adjust <= 0)
2404 if (try_apply_stack_adjustment (insn, memlist,
2405 last_sp_adjust + this_adjust,
2409 flow_delete_insn (last_sp_set);
2411 last_sp_adjust += this_adjust;
2412 free_csa_memlist (memlist);
2418 /* Combination failed. Restart processing from here. */
2419 free_csa_memlist (memlist);
2422 last_sp_adjust = this_adjust;
2426 /* Find a predecrement of exactly the previous adjustment and
2427 turn it into a direct store. Obviously we can't do this if
2428 there were any intervening uses of the stack pointer. */
2430 && GET_CODE (dest) == MEM
2431 && ((GET_CODE (XEXP (dest, 0)) == PRE_DEC
2433 == (HOST_WIDE_INT) GET_MODE_SIZE (GET_MODE (dest))))
2434 || (GET_CODE (XEXP (dest, 0)) == PRE_MODIFY
2435 && GET_CODE (XEXP (XEXP (dest, 0), 1)) == PLUS
2436 && XEXP (XEXP (XEXP (dest, 0), 1), 0) == stack_pointer_rtx
2437 && (GET_CODE (XEXP (XEXP (XEXP (dest, 0), 1), 1))
2439 && (INTVAL (XEXP (XEXP (XEXP (dest, 0), 1), 1))
2440 == -last_sp_adjust)))
2441 && XEXP (XEXP (dest, 0), 0) == stack_pointer_rtx
2442 && ! reg_mentioned_p (stack_pointer_rtx, src)
2443 && memory_address_p (GET_MODE (dest), stack_pointer_rtx)
2444 && validate_change (insn, &SET_DEST (set),
2445 change_address (dest, VOIDmode,
2446 stack_pointer_rtx), 0))
2448 if (last_sp_set == bb->head)
2449 bb->head = NEXT_INSN (last_sp_set);
2450 flow_delete_insn (last_sp_set);
2452 free_csa_memlist (memlist);
2454 last_sp_set = NULL_RTX;
2461 data.memlist = memlist;
2462 if (GET_CODE (insn) != CALL_INSN && last_sp_set
2463 && !for_each_rtx (&PATTERN (insn), record_stack_memrefs, &data))
2465 memlist = data.memlist;
2468 memlist = data.memlist;
2470 /* Otherwise, we were not able to process the instruction.
2471 Do not continue collecting data across such a one. */
2473 && (GET_CODE (insn) == CALL_INSN
2474 || reg_mentioned_p (stack_pointer_rtx, PATTERN (insn))))
2476 free_csa_memlist (memlist);
2478 last_sp_set = NULL_RTX;
2483 if (insn == bb->end)
2487 flow_delete_insn (pending_delete);
2492 bb->end = PREV_INSN (pending_delete);
2493 flow_delete_insn (pending_delete);