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"
43 static int perhaps_ends_bb_p PARAMS ((rtx));
44 static int optimize_reg_copy_1 PARAMS ((rtx, rtx, rtx));
45 static void optimize_reg_copy_2 PARAMS ((rtx, rtx, rtx));
46 static void optimize_reg_copy_3 PARAMS ((rtx, rtx, rtx));
47 static rtx gen_add3_insn PARAMS ((rtx, rtx, rtx));
48 static void copy_src_to_dest PARAMS ((rtx, rtx, rtx, int));
49 static int *regmove_bb_head;
52 int with[MAX_RECOG_OPERANDS];
53 enum { READ, WRITE, READWRITE } use[MAX_RECOG_OPERANDS];
54 int commutative[MAX_RECOG_OPERANDS];
55 int early_clobber[MAX_RECOG_OPERANDS];
58 static rtx discover_flags_reg PARAMS ((void));
59 static void mark_flags_life_zones PARAMS ((rtx));
60 static void flags_set_1 PARAMS ((rtx, rtx, void *));
62 static int try_auto_increment PARAMS ((rtx, rtx, rtx, rtx, HOST_WIDE_INT, int));
63 static int find_matches PARAMS ((rtx, struct match *));
64 static void replace_in_call_usage PARAMS ((rtx *, int, rtx, rtx));
65 static int fixup_match_1 PARAMS ((rtx, rtx, rtx, rtx, rtx, int, int, int, FILE *))
67 static int reg_is_remote_constant_p PARAMS ((rtx, rtx, rtx));
68 static int stable_and_no_regs_but_for_p PARAMS ((rtx, rtx, rtx));
69 static int regclass_compatible_p PARAMS ((int, int));
70 static int replacement_quality PARAMS ((rtx));
71 static int fixup_match_2 PARAMS ((rtx, rtx, rtx, rtx, FILE *));
73 /* Return non-zero if registers with CLASS1 and CLASS2 can be merged without
74 causing too much register allocation problems. */
76 regclass_compatible_p (class0, class1)
79 return (class0 == class1
80 || (reg_class_subset_p (class0, class1)
81 && ! CLASS_LIKELY_SPILLED_P (class0))
82 || (reg_class_subset_p (class1, class0)
83 && ! CLASS_LIKELY_SPILLED_P (class1)));
86 /* Generate and return an insn body to add r1 and c,
87 storing the result in r0. */
89 gen_add3_insn (r0, r1, c)
92 int icode = (int) add_optab->handlers[(int) GET_MODE (r0)].insn_code;
94 if (icode == CODE_FOR_nothing
95 || ! ((*insn_data[icode].operand[0].predicate)
96 (r0, insn_data[icode].operand[0].mode))
97 || ! ((*insn_data[icode].operand[1].predicate)
98 (r1, insn_data[icode].operand[1].mode))
99 || ! ((*insn_data[icode].operand[2].predicate)
100 (c, insn_data[icode].operand[2].mode)))
103 return (GEN_FCN (icode) (r0, r1, c));
107 /* INC_INSN is an instruction that adds INCREMENT to REG.
108 Try to fold INC_INSN as a post/pre in/decrement into INSN.
109 Iff INC_INSN_SET is nonzero, inc_insn has a destination different from src.
110 Return nonzero for success. */
112 try_auto_increment (insn, inc_insn, inc_insn_set, reg, increment, pre)
113 rtx reg, insn, inc_insn ,inc_insn_set;
114 HOST_WIDE_INT increment;
117 enum rtx_code inc_code;
119 rtx pset = single_set (insn);
122 /* Can't use the size of SET_SRC, we might have something like
123 (sign_extend:SI (mem:QI ... */
124 rtx use = find_use_as_address (pset, reg, 0);
125 if (use != 0 && use != (rtx) 1)
127 int size = GET_MODE_SIZE (GET_MODE (use));
129 || (HAVE_POST_INCREMENT
130 && pre == 0 && (inc_code = POST_INC, increment == size))
131 || (HAVE_PRE_INCREMENT
132 && pre == 1 && (inc_code = PRE_INC, increment == size))
133 || (HAVE_POST_DECREMENT
134 && pre == 0 && (inc_code = POST_DEC, increment == -size))
135 || (HAVE_PRE_DECREMENT
136 && pre == 1 && (inc_code = PRE_DEC, increment == -size))
142 &SET_SRC (inc_insn_set),
143 XEXP (SET_SRC (inc_insn_set), 0), 1);
144 validate_change (insn, &XEXP (use, 0),
145 gen_rtx_fmt_e (inc_code, Pmode, reg), 1);
146 if (apply_change_group ())
148 /* If there is a REG_DEAD note on this insn, we must
149 change this not to REG_UNUSED meaning that the register
150 is set, but the value is dead. Failure to do so will
151 result in a sched1 abort -- when it recomputes lifetime
152 information, the number of REG_DEAD notes will have
154 rtx note = find_reg_note (insn, REG_DEAD, reg);
156 PUT_MODE (note, REG_UNUSED);
159 = gen_rtx_EXPR_LIST (REG_INC,
160 reg, REG_NOTES (insn));
163 PUT_CODE (inc_insn, NOTE);
164 NOTE_LINE_NUMBER (inc_insn) = NOTE_INSN_DELETED;
165 NOTE_SOURCE_FILE (inc_insn) = 0;
175 /* Determine if the pattern generated by add_optab has a clobber,
176 such as might be issued for a flags hard register. To make the
177 code elsewhere simpler, we handle cc0 in this same framework.
179 Return the register if one was discovered. Return NULL_RTX if
180 if no flags were found. Return pc_rtx if we got confused. */
183 discover_flags_reg ()
186 tmp = gen_rtx_REG (word_mode, 10000);
187 tmp = gen_add3_insn (tmp, tmp, GEN_INT (2));
189 /* If we get something that isn't a simple set, or a
190 [(set ..) (clobber ..)], this whole function will go wrong. */
191 if (GET_CODE (tmp) == SET)
193 else if (GET_CODE (tmp) == PARALLEL)
197 if (XVECLEN (tmp, 0) != 2)
199 tmp = XVECEXP (tmp, 0, 1);
200 if (GET_CODE (tmp) != CLOBBER)
204 /* Don't do anything foolish if the md wanted to clobber a
205 scratch or something. We only care about hard regs.
206 Moreover we don't like the notion of subregs of hard regs. */
207 if (GET_CODE (tmp) == SUBREG
208 && GET_CODE (SUBREG_REG (tmp)) == REG
209 && REGNO (SUBREG_REG (tmp)) < FIRST_PSEUDO_REGISTER)
211 found = (GET_CODE (tmp) == REG && REGNO (tmp) < FIRST_PSEUDO_REGISTER);
213 return (found ? tmp : NULL_RTX);
219 /* It is a tedious task identifying when the flags register is live and
220 when it is safe to optimize. Since we process the instruction stream
221 multiple times, locate and record these live zones by marking the
222 mode of the instructions --
224 QImode is used on the instruction at which the flags becomes live.
226 HImode is used within the range (exclusive) that the flags are
227 live. Thus the user of the flags is not marked.
229 All other instructions are cleared to VOIDmode. */
231 /* Used to communicate with flags_set_1. */
232 static rtx flags_set_1_rtx;
233 static int flags_set_1_set;
236 mark_flags_life_zones (flags)
244 /* If we found a flags register on a cc0 host, bail. */
245 if (flags == NULL_RTX)
247 else if (flags != cc0_rtx)
251 /* Simple cases first: if no flags, clear all modes. If confusing,
252 mark the entire function as being in a flags shadow. */
253 if (flags == NULL_RTX || flags == pc_rtx)
255 enum machine_mode mode = (flags ? HImode : VOIDmode);
257 for (insn = get_insns(); insn; insn = NEXT_INSN (insn))
258 PUT_MODE (insn, mode);
266 flags_regno = REGNO (flags);
267 flags_nregs = HARD_REGNO_NREGS (flags_regno, GET_MODE (flags));
269 flags_set_1_rtx = flags;
271 /* Process each basic block. */
272 for (block = n_basic_blocks - 1; block >= 0; block--)
277 insn = BLOCK_HEAD (block);
278 end = BLOCK_END (block);
280 /* Look out for the (unlikely) case of flags being live across
281 basic block boundaries. */
286 for (i = 0; i < flags_nregs; ++i)
287 live |= REGNO_REG_SET_P (BASIC_BLOCK (block)->global_live_at_start,
294 /* Process liveness in reverse order of importance --
295 alive, death, birth. This lets more important info
296 overwrite the mode of lesser info. */
301 /* In the cc0 case, death is not marked in reg notes,
302 but is instead the mere use of cc0 when it is alive. */
303 if (live && reg_mentioned_p (cc0_rtx, PATTERN (insn)))
306 /* In the hard reg case, we watch death notes. */
307 if (live && find_regno_note (insn, REG_DEAD, flags_regno))
310 PUT_MODE (insn, (live ? HImode : VOIDmode));
312 /* In either case, birth is denoted simply by it's presence
313 as the destination of a set. */
315 note_stores (PATTERN (insn), flags_set_1, NULL);
319 PUT_MODE (insn, QImode);
323 PUT_MODE (insn, (live ? HImode : VOIDmode));
327 insn = NEXT_INSN (insn);
332 /* A subroutine of mark_flags_life_zones, called through note_stores. */
335 flags_set_1 (x, pat, data)
337 void *data ATTRIBUTE_UNUSED;
339 if (GET_CODE (pat) == SET
340 && reg_overlap_mentioned_p (x, flags_set_1_rtx))
344 static int *regno_src_regno;
346 /* Indicate how good a choice REG (which appears as a source) is to replace
347 a destination register with. The higher the returned value, the better
348 the choice. The main objective is to avoid using a register that is
349 a candidate for tying to a hard register, since the output might in
350 turn be a candidate to be tied to a different hard register. */
352 replacement_quality(reg)
357 /* Bad if this isn't a register at all. */
358 if (GET_CODE (reg) != REG)
361 /* If this register is not meant to get a hard register,
362 it is a poor choice. */
363 if (REG_LIVE_LENGTH (REGNO (reg)) < 0)
366 src_regno = regno_src_regno[REGNO (reg)];
368 /* If it was not copied from another register, it is fine. */
372 /* Copied from a hard register? */
373 if (src_regno < FIRST_PSEUDO_REGISTER)
376 /* Copied from a pseudo register - not as bad as from a hard register,
377 yet still cumbersome, since the register live length will be lengthened
378 when the registers get tied. */
382 /* Return 1 if INSN might end a basic block. */
384 static int perhaps_ends_bb_p (insn)
387 switch (GET_CODE (insn))
391 /* These always end a basic block. */
395 /* A CALL_INSN might be the last insn of a basic block, if it is inside
396 an EH region or if there are nonlocal gotos. Note that this test is
397 very conservative. */
398 return flag_exceptions || nonlocal_goto_handler_labels;
401 /* All others never end a basic block. */
406 /* INSN is a copy from SRC to DEST, both registers, and SRC does not die
409 Search forward to see if SRC dies before either it or DEST is modified,
410 but don't scan past the end of a basic block. If so, we can replace SRC
411 with DEST and let SRC die in INSN.
413 This will reduce the number of registers live in that range and may enable
414 DEST to be tied to SRC, thus often saving one register in addition to a
415 register-register copy. */
418 optimize_reg_copy_1 (insn, dest, src)
426 int sregno = REGNO (src);
427 int dregno = REGNO (dest);
429 /* We don't want to mess with hard regs if register classes are small. */
431 || (SMALL_REGISTER_CLASSES
432 && (sregno < FIRST_PSEUDO_REGISTER
433 || dregno < FIRST_PSEUDO_REGISTER))
434 /* We don't see all updates to SP if they are in an auto-inc memory
435 reference, so we must disallow this optimization on them. */
436 || sregno == STACK_POINTER_REGNUM || dregno == STACK_POINTER_REGNUM)
439 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
441 /* ??? We can't scan past the end of a basic block without updating
442 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
443 if (perhaps_ends_bb_p (p))
445 else if (! INSN_P (p))
448 if (reg_set_p (src, p) || reg_set_p (dest, p)
449 /* Don't change a USE of a register. */
450 || (GET_CODE (PATTERN (p)) == USE
451 && reg_overlap_mentioned_p (src, XEXP (PATTERN (p), 0))))
454 /* See if all of SRC dies in P. This test is slightly more
455 conservative than it needs to be. */
456 if ((note = find_regno_note (p, REG_DEAD, sregno)) != 0
457 && GET_MODE (XEXP (note, 0)) == GET_MODE (src))
465 /* We can do the optimization. Scan forward from INSN again,
466 replacing regs as we go. Set FAILED if a replacement can't
467 be done. In that case, we can't move the death note for SRC.
468 This should be rare. */
470 /* Set to stop at next insn. */
471 for (q = next_real_insn (insn);
472 q != next_real_insn (p);
473 q = next_real_insn (q))
475 if (reg_overlap_mentioned_p (src, PATTERN (q)))
477 /* If SRC is a hard register, we might miss some
478 overlapping registers with validate_replace_rtx,
479 so we would have to undo it. We can't if DEST is
480 present in the insn, so fail in that combination
482 if (sregno < FIRST_PSEUDO_REGISTER
483 && reg_mentioned_p (dest, PATTERN (q)))
486 /* Replace all uses and make sure that the register
487 isn't still present. */
488 else if (validate_replace_rtx (src, dest, q)
489 && (sregno >= FIRST_PSEUDO_REGISTER
490 || ! reg_overlap_mentioned_p (src,
495 validate_replace_rtx (dest, src, q);
500 /* For SREGNO, count the total number of insns scanned.
501 For DREGNO, count the total number of insns scanned after
502 passing the death note for DREGNO. */
507 /* If the insn in which SRC dies is a CALL_INSN, don't count it
508 as a call that has been crossed. Otherwise, count it. */
509 if (q != p && GET_CODE (q) == CALL_INSN)
511 /* Similarly, total calls for SREGNO, total calls beyond
512 the death note for DREGNO. */
518 /* If DEST dies here, remove the death note and save it for
519 later. Make sure ALL of DEST dies here; again, this is
520 overly conservative. */
522 && (dest_death = find_regno_note (q, REG_DEAD, dregno)) != 0)
524 if (GET_MODE (XEXP (dest_death, 0)) != GET_MODE (dest))
525 failed = 1, dest_death = 0;
527 remove_note (q, dest_death);
533 /* These counters need to be updated if and only if we are
534 going to move the REG_DEAD note. */
535 if (sregno >= FIRST_PSEUDO_REGISTER)
537 if (REG_LIVE_LENGTH (sregno) >= 0)
539 REG_LIVE_LENGTH (sregno) -= s_length;
540 /* REG_LIVE_LENGTH is only an approximation after
541 combine if sched is not run, so make sure that we
542 still have a reasonable value. */
543 if (REG_LIVE_LENGTH (sregno) < 2)
544 REG_LIVE_LENGTH (sregno) = 2;
547 REG_N_CALLS_CROSSED (sregno) -= s_n_calls;
550 /* Move death note of SRC from P to INSN. */
551 remove_note (p, note);
552 XEXP (note, 1) = REG_NOTES (insn);
553 REG_NOTES (insn) = note;
556 /* DEST is also dead if INSN has a REG_UNUSED note for DEST. */
558 && (dest_death = find_regno_note (insn, REG_UNUSED, dregno)))
560 PUT_REG_NOTE_KIND (dest_death, REG_DEAD);
561 remove_note (insn, dest_death);
564 /* Put death note of DEST on P if we saw it die. */
567 XEXP (dest_death, 1) = REG_NOTES (p);
568 REG_NOTES (p) = dest_death;
570 if (dregno >= FIRST_PSEUDO_REGISTER)
572 /* If and only if we are moving the death note for DREGNO,
573 then we need to update its counters. */
574 if (REG_LIVE_LENGTH (dregno) >= 0)
575 REG_LIVE_LENGTH (dregno) += d_length;
576 REG_N_CALLS_CROSSED (dregno) += d_n_calls;
583 /* If SRC is a hard register which is set or killed in some other
584 way, we can't do this optimization. */
585 else if (sregno < FIRST_PSEUDO_REGISTER
586 && dead_or_set_p (p, src))
592 /* INSN is a copy of SRC to DEST, in which SRC dies. See if we now have
593 a sequence of insns that modify DEST followed by an insn that sets
594 SRC to DEST in which DEST dies, with no prior modification of DEST.
595 (There is no need to check if the insns in between actually modify
596 DEST. We should not have cases where DEST is not modified, but
597 the optimization is safe if no such modification is detected.)
598 In that case, we can replace all uses of DEST, starting with INSN and
599 ending with the set of SRC to DEST, with SRC. We do not do this
600 optimization if a CALL_INSN is crossed unless SRC already crosses a
601 call or if DEST dies before the copy back to SRC.
603 It is assumed that DEST and SRC are pseudos; it is too complicated to do
604 this for hard registers since the substitutions we may make might fail. */
607 optimize_reg_copy_2 (insn, dest, src)
614 int sregno = REGNO (src);
615 int dregno = REGNO (dest);
617 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
619 /* ??? We can't scan past the end of a basic block without updating
620 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
621 if (perhaps_ends_bb_p (p))
623 else if (! INSN_P (p))
626 set = single_set (p);
627 if (set && SET_SRC (set) == dest && SET_DEST (set) == src
628 && find_reg_note (p, REG_DEAD, dest))
630 /* We can do the optimization. Scan forward from INSN again,
631 replacing regs as we go. */
633 /* Set to stop at next insn. */
634 for (q = insn; q != NEXT_INSN (p); q = NEXT_INSN (q))
637 if (reg_mentioned_p (dest, PATTERN (q)))
638 PATTERN (q) = replace_rtx (PATTERN (q), dest, src);
641 if (GET_CODE (q) == CALL_INSN)
643 REG_N_CALLS_CROSSED (dregno)--;
644 REG_N_CALLS_CROSSED (sregno)++;
648 remove_note (p, find_reg_note (p, REG_DEAD, dest));
649 REG_N_DEATHS (dregno)--;
650 remove_note (insn, find_reg_note (insn, REG_DEAD, src));
651 REG_N_DEATHS (sregno)--;
655 if (reg_set_p (src, p)
656 || find_reg_note (p, REG_DEAD, dest)
657 || (GET_CODE (p) == CALL_INSN && REG_N_CALLS_CROSSED (sregno) == 0))
661 /* INSN is a ZERO_EXTEND or SIGN_EXTEND of SRC to DEST.
662 Look if SRC dies there, and if it is only set once, by loading
663 it from memory. If so, try to encorporate the zero/sign extension
664 into the memory read, change SRC to the mode of DEST, and alter
665 the remaining accesses to use the appropriate SUBREG. This allows
666 SRC and DEST to be tied later. */
668 optimize_reg_copy_3 (insn, dest, src)
673 rtx src_reg = XEXP (src, 0);
674 int src_no = REGNO (src_reg);
675 int dst_no = REGNO (dest);
677 enum machine_mode old_mode;
679 if (src_no < FIRST_PSEUDO_REGISTER
680 || dst_no < FIRST_PSEUDO_REGISTER
681 || ! find_reg_note (insn, REG_DEAD, src_reg)
682 || REG_N_SETS (src_no) != 1)
684 for (p = PREV_INSN (insn); p && ! reg_set_p (src_reg, p); p = PREV_INSN (p))
685 /* ??? We can't scan past the end of a basic block without updating
686 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
687 if (perhaps_ends_bb_p (p))
693 if (! (set = single_set (p))
694 || GET_CODE (SET_SRC (set)) != MEM
695 || SET_DEST (set) != src_reg)
698 /* Be conserative: although this optimization is also valid for
699 volatile memory references, that could cause trouble in later passes. */
700 if (MEM_VOLATILE_P (SET_SRC (set)))
703 /* Do not use a SUBREG to truncate from one mode to another if truncation
705 if (GET_MODE_BITSIZE (GET_MODE (src_reg)) <= GET_MODE_BITSIZE (GET_MODE (src))
706 && !TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (GET_MODE (src)),
707 GET_MODE_BITSIZE (GET_MODE (src_reg))))
710 old_mode = GET_MODE (src_reg);
711 PUT_MODE (src_reg, GET_MODE (src));
712 XEXP (src, 0) = SET_SRC (set);
714 /* Include this change in the group so that it's easily undone if
715 one of the changes in the group is invalid. */
716 validate_change (p, &SET_SRC (set), src, 1);
718 /* Now walk forward making additional replacements. We want to be able
719 to undo all the changes if a later substitution fails. */
720 subreg = gen_rtx_SUBREG (old_mode, src_reg, 0);
721 while (p = NEXT_INSN (p), p != insn)
726 /* Make a tenative change. */
727 validate_replace_rtx_group (src_reg, subreg, p);
730 validate_replace_rtx_group (src, src_reg, insn);
732 /* Now see if all the changes are valid. */
733 if (! apply_change_group ())
735 /* One or more changes were no good. Back out everything. */
736 PUT_MODE (src_reg, old_mode);
737 XEXP (src, 0) = src_reg;
742 /* If we were not able to update the users of src to use dest directly, try
743 instead moving the value to dest directly before the operation. */
746 copy_src_to_dest (insn, src, dest, old_max_uid)
765 /* A REG_LIVE_LENGTH of -1 indicates the register is equivalent to a constant
766 or memory location and is used infrequently; a REG_LIVE_LENGTH of -2 is
767 parameter when there is no frame pointer that is not allocated a register.
768 For now, we just reject them, rather than incrementing the live length. */
770 if (GET_CODE (src) == REG
771 && REG_LIVE_LENGTH (REGNO (src)) > 0
772 && GET_CODE (dest) == REG
773 && !RTX_UNCHANGING_P (dest)
774 && REG_LIVE_LENGTH (REGNO (dest)) > 0
775 && (set = single_set (insn)) != NULL_RTX
776 && !reg_mentioned_p (dest, SET_SRC (set))
777 && GET_MODE (src) == GET_MODE (dest))
779 int old_num_regs = reg_rtx_no;
781 /* Generate the src->dest move. */
783 emit_move_insn (dest, src);
784 seq = gen_sequence ();
786 /* If this sequence uses new registers, we may not use it. */
787 if (old_num_regs != reg_rtx_no
788 || ! validate_replace_rtx (src, dest, insn))
790 /* We have to restore reg_rtx_no to its old value, lest
791 recompute_reg_usage will try to compute the usage of the
792 new regs, yet reg_n_info is not valid for them. */
793 reg_rtx_no = old_num_regs;
796 emit_insn_before (seq, insn);
797 move_insn = PREV_INSN (insn);
798 p_move_notes = ®_NOTES (move_insn);
799 p_insn_notes = ®_NOTES (insn);
801 /* Move any notes mentioning src to the move instruction */
802 for (link = REG_NOTES (insn); link != NULL_RTX; link = next)
804 next = XEXP (link, 1);
805 if (XEXP (link, 0) == src)
807 *p_move_notes = link;
808 p_move_notes = &XEXP (link, 1);
812 *p_insn_notes = link;
813 p_insn_notes = &XEXP (link, 1);
817 *p_move_notes = NULL_RTX;
818 *p_insn_notes = NULL_RTX;
820 /* Is the insn the head of a basic block? If so extend it */
821 insn_uid = INSN_UID (insn);
822 move_uid = INSN_UID (move_insn);
823 if (insn_uid < old_max_uid)
825 bb = regmove_bb_head[insn_uid];
828 BLOCK_HEAD (bb) = move_insn;
829 regmove_bb_head[insn_uid] = -1;
833 /* Update the various register tables. */
834 dest_regno = REGNO (dest);
835 REG_N_SETS (dest_regno) ++;
836 REG_LIVE_LENGTH (dest_regno)++;
837 if (REGNO_FIRST_UID (dest_regno) == insn_uid)
838 REGNO_FIRST_UID (dest_regno) = move_uid;
840 src_regno = REGNO (src);
841 if (! find_reg_note (move_insn, REG_DEAD, src))
842 REG_LIVE_LENGTH (src_regno)++;
844 if (REGNO_FIRST_UID (src_regno) == insn_uid)
845 REGNO_FIRST_UID (src_regno) = move_uid;
847 if (REGNO_LAST_UID (src_regno) == insn_uid)
848 REGNO_LAST_UID (src_regno) = move_uid;
850 if (REGNO_LAST_NOTE_UID (src_regno) == insn_uid)
851 REGNO_LAST_NOTE_UID (src_regno) = move_uid;
856 /* Return whether REG is set in only one location, and is set to a
857 constant, but is set in a different basic block from INSN (an
858 instructions which uses REG). In this case REG is equivalent to a
859 constant, and we don't want to break that equivalence, because that
860 may increase register pressure and make reload harder. If REG is
861 set in the same basic block as INSN, we don't worry about it,
862 because we'll probably need a register anyhow (??? but what if REG
863 is used in a different basic block as well as this one?). FIRST is
864 the first insn in the function. */
867 reg_is_remote_constant_p (reg, insn, first)
874 if (REG_N_SETS (REGNO (reg)) != 1)
877 /* Look for the set. */
878 for (p = LOG_LINKS (insn); p; p = XEXP (p, 1))
882 if (REG_NOTE_KIND (p) != 0)
884 s = single_set (XEXP (p, 0));
886 && GET_CODE (SET_DEST (s)) == REG
887 && REGNO (SET_DEST (s)) == REGNO (reg))
889 /* The register is set in the same basic block. */
894 for (p = first; p && p != insn; p = NEXT_INSN (p))
902 && GET_CODE (SET_DEST (s)) == REG
903 && REGNO (SET_DEST (s)) == REGNO (reg))
905 /* This is the instruction which sets REG. If there is a
906 REG_EQUAL note, then REG is equivalent to a constant. */
907 if (find_reg_note (p, REG_EQUAL, NULL_RTX))
916 /* INSN is adding a CONST_INT to a REG. We search backwards looking for
917 another add immediate instruction with the same source and dest registers,
918 and if we find one, we change INSN to an increment, and return 1. If
919 no changes are made, we return 0.
922 (set (reg100) (plus reg1 offset1))
924 (set (reg100) (plus reg1 offset2))
926 (set (reg100) (plus reg1 offset1))
928 (set (reg100) (plus reg100 offset2-offset1)) */
930 /* ??? What does this comment mean? */
931 /* cse disrupts preincrement / postdecrement squences when it finds a
932 hard register as ultimate source, like the frame pointer. */
935 fixup_match_2 (insn, dst, src, offset, regmove_dump_file)
936 rtx insn, dst, src, offset;
937 FILE *regmove_dump_file;
939 rtx p, dst_death = 0;
940 int length, num_calls = 0;
942 /* If SRC dies in INSN, we'd have to move the death note. This is
943 considered to be very unlikely, so we just skip the optimization
945 if (find_regno_note (insn, REG_DEAD, REGNO (src)))
948 /* Scan backward to find the first instruction that sets DST. */
950 for (length = 0, p = PREV_INSN (insn); p; p = PREV_INSN (p))
954 /* ??? We can't scan past the end of a basic block without updating
955 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
956 if (perhaps_ends_bb_p (p))
958 else if (! INSN_P (p))
961 if (find_regno_note (p, REG_DEAD, REGNO (dst)))
966 pset = single_set (p);
967 if (pset && SET_DEST (pset) == dst
968 && GET_CODE (SET_SRC (pset)) == PLUS
969 && XEXP (SET_SRC (pset), 0) == src
970 && GET_CODE (XEXP (SET_SRC (pset), 1)) == CONST_INT)
972 HOST_WIDE_INT newconst
973 = INTVAL (offset) - INTVAL (XEXP (SET_SRC (pset), 1));
974 rtx add = gen_add3_insn (dst, dst, GEN_INT (newconst));
976 if (add && validate_change (insn, &PATTERN (insn), add, 0))
978 /* Remove the death note for DST from DST_DEATH. */
981 remove_death (REGNO (dst), dst_death);
982 REG_LIVE_LENGTH (REGNO (dst)) += length;
983 REG_N_CALLS_CROSSED (REGNO (dst)) += num_calls;
986 if (regmove_dump_file)
987 fprintf (regmove_dump_file,
988 "Fixed operand of insn %d.\n",
992 for (p = PREV_INSN (insn); p; p = PREV_INSN (p))
994 if (GET_CODE (p) == CODE_LABEL
995 || GET_CODE (p) == JUMP_INSN)
999 if (reg_overlap_mentioned_p (dst, PATTERN (p)))
1001 if (try_auto_increment (p, insn, 0, dst, newconst, 0))
1006 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
1008 if (GET_CODE (p) == CODE_LABEL
1009 || GET_CODE (p) == JUMP_INSN)
1013 if (reg_overlap_mentioned_p (dst, PATTERN (p)))
1015 try_auto_increment (p, insn, 0, dst, newconst, 1);
1024 if (reg_set_p (dst, PATTERN (p)))
1027 /* If we have passed a call instruction, and the
1028 pseudo-reg SRC is not already live across a call,
1029 then don't perform the optimization. */
1030 /* reg_set_p is overly conservative for CALL_INSNS, thinks that all
1031 hard regs are clobbered. Thus, we only use it for src for
1033 if (GET_CODE (p) == CALL_INSN)
1038 if (REG_N_CALLS_CROSSED (REGNO (src)) == 0)
1041 if (call_used_regs [REGNO (dst)]
1042 || find_reg_fusage (p, CLOBBER, dst))
1045 else if (reg_set_p (src, PATTERN (p)))
1053 regmove_optimize (f, nregs, regmove_dump_file)
1056 FILE *regmove_dump_file;
1058 int old_max_uid = get_max_uid ();
1063 rtx copy_src, copy_dst;
1065 /* Find out where a potential flags register is live, and so that we
1066 can supress some optimizations in those zones. */
1067 mark_flags_life_zones (discover_flags_reg ());
1069 regno_src_regno = (int *) xmalloc (sizeof *regno_src_regno * nregs);
1070 for (i = nregs; --i >= 0; ) regno_src_regno[i] = -1;
1072 regmove_bb_head = (int *) xmalloc (sizeof (int) * (old_max_uid + 1));
1073 for (i = old_max_uid; i >= 0; i--) regmove_bb_head[i] = -1;
1074 for (i = 0; i < n_basic_blocks; i++)
1075 regmove_bb_head[INSN_UID (BLOCK_HEAD (i))] = i;
1077 /* A forward/backward pass. Replace output operands with input operands. */
1079 for (pass = 0; pass <= 2; pass++)
1081 if (! flag_regmove && pass >= flag_expensive_optimizations)
1084 if (regmove_dump_file)
1085 fprintf (regmove_dump_file, "Starting %s pass...\n",
1086 pass ? "backward" : "forward");
1088 for (insn = pass ? get_last_insn () : f; insn;
1089 insn = pass ? PREV_INSN (insn) : NEXT_INSN (insn))
1092 int op_no, match_no;
1094 set = single_set (insn);
1098 if (flag_expensive_optimizations && ! pass
1099 && (GET_CODE (SET_SRC (set)) == SIGN_EXTEND
1100 || GET_CODE (SET_SRC (set)) == ZERO_EXTEND)
1101 && GET_CODE (XEXP (SET_SRC (set), 0)) == REG
1102 && GET_CODE (SET_DEST(set)) == REG)
1103 optimize_reg_copy_3 (insn, SET_DEST (set), SET_SRC (set));
1105 if (flag_expensive_optimizations && ! pass
1106 && GET_CODE (SET_SRC (set)) == REG
1107 && GET_CODE (SET_DEST(set)) == REG)
1109 /* If this is a register-register copy where SRC is not dead,
1110 see if we can optimize it. If this optimization succeeds,
1111 it will become a copy where SRC is dead. */
1112 if ((find_reg_note (insn, REG_DEAD, SET_SRC (set))
1113 || optimize_reg_copy_1 (insn, SET_DEST (set), SET_SRC (set)))
1114 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
1116 /* Similarly for a pseudo-pseudo copy when SRC is dead. */
1117 if (REGNO (SET_SRC (set)) >= FIRST_PSEUDO_REGISTER)
1118 optimize_reg_copy_2 (insn, SET_DEST (set), SET_SRC (set));
1119 if (regno_src_regno[REGNO (SET_DEST (set))] < 0
1120 && SET_SRC (set) != SET_DEST (set))
1122 int srcregno = REGNO (SET_SRC(set));
1123 if (regno_src_regno[srcregno] >= 0)
1124 srcregno = regno_src_regno[srcregno];
1125 regno_src_regno[REGNO (SET_DEST (set))] = srcregno;
1132 if (! find_matches (insn, &match))
1135 /* Now scan through the operands looking for a source operand
1136 which is supposed to match the destination operand.
1137 Then scan forward for an instruction which uses the dest
1139 If it dies there, then replace the dest in both operands with
1140 the source operand. */
1142 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1144 rtx src, dst, src_subreg;
1145 enum reg_class src_class, dst_class;
1147 match_no = match.with[op_no];
1149 /* Nothing to do if the two operands aren't supposed to match. */
1153 src = recog_data.operand[op_no];
1154 dst = recog_data.operand[match_no];
1156 if (GET_CODE (src) != REG)
1160 if (GET_CODE (dst) == SUBREG
1161 && GET_MODE_SIZE (GET_MODE (dst))
1162 >= GET_MODE_SIZE (GET_MODE (SUBREG_REG (dst))))
1165 = gen_rtx_SUBREG (GET_MODE (SUBREG_REG (dst)),
1166 src, SUBREG_WORD (dst));
1167 dst = SUBREG_REG (dst);
1169 if (GET_CODE (dst) != REG
1170 || REGNO (dst) < FIRST_PSEUDO_REGISTER)
1173 if (REGNO (src) < FIRST_PSEUDO_REGISTER)
1175 if (match.commutative[op_no] < op_no)
1176 regno_src_regno[REGNO (dst)] = REGNO (src);
1180 if (REG_LIVE_LENGTH (REGNO (src)) < 0)
1183 /* op_no/src must be a read-only operand, and
1184 match_operand/dst must be a write-only operand. */
1185 if (match.use[op_no] != READ
1186 || match.use[match_no] != WRITE)
1189 if (match.early_clobber[match_no]
1190 && count_occurrences (PATTERN (insn), src, 0) > 1)
1193 /* Make sure match_operand is the destination. */
1194 if (recog_data.operand[match_no] != SET_DEST (set))
1197 /* If the operands already match, then there is nothing to do. */
1198 if (operands_match_p (src, dst))
1201 /* But in the commutative case, we might find a better match. */
1202 if (match.commutative[op_no] >= 0)
1204 rtx comm = recog_data.operand[match.commutative[op_no]];
1205 if (operands_match_p (comm, dst)
1206 && (replacement_quality (comm)
1207 >= replacement_quality (src)))
1211 src_class = reg_preferred_class (REGNO (src));
1212 dst_class = reg_preferred_class (REGNO (dst));
1213 if (! regclass_compatible_p (src_class, dst_class))
1216 if (fixup_match_1 (insn, set, src, src_subreg, dst, pass,
1224 /* A backward pass. Replace input operands with output operands. */
1226 if (regmove_dump_file)
1227 fprintf (regmove_dump_file, "Starting backward pass...\n");
1229 for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
1233 int op_no, match_no;
1236 if (! find_matches (insn, &match))
1239 /* Now scan through the operands looking for a destination operand
1240 which is supposed to match a source operand.
1241 Then scan backward for an instruction which sets the source
1242 operand. If safe, then replace the source operand with the
1243 dest operand in both instructions. */
1245 copy_src = NULL_RTX;
1246 copy_dst = NULL_RTX;
1247 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1249 rtx set, p, src, dst;
1250 rtx src_note, dst_note;
1252 enum reg_class src_class, dst_class;
1255 match_no = match.with[op_no];
1257 /* Nothing to do if the two operands aren't supposed to match. */
1261 dst = recog_data.operand[match_no];
1262 src = recog_data.operand[op_no];
1264 if (GET_CODE (src) != REG)
1267 if (GET_CODE (dst) != REG
1268 || REGNO (dst) < FIRST_PSEUDO_REGISTER
1269 || REG_LIVE_LENGTH (REGNO (dst)) < 0)
1272 /* If the operands already match, then there is nothing to do. */
1273 if (operands_match_p (src, dst))
1276 if (match.commutative[op_no] >= 0)
1278 rtx comm = recog_data.operand[match.commutative[op_no]];
1279 if (operands_match_p (comm, dst))
1283 set = single_set (insn);
1287 /* match_no/dst must be a write-only operand, and
1288 operand_operand/src must be a read-only operand. */
1289 if (match.use[op_no] != READ
1290 || match.use[match_no] != WRITE)
1293 if (match.early_clobber[match_no]
1294 && count_occurrences (PATTERN (insn), src, 0) > 1)
1297 /* Make sure match_no is the destination. */
1298 if (recog_data.operand[match_no] != SET_DEST (set))
1301 if (REGNO (src) < FIRST_PSEUDO_REGISTER)
1303 if (GET_CODE (SET_SRC (set)) == PLUS
1304 && GET_CODE (XEXP (SET_SRC (set), 1)) == CONST_INT
1305 && XEXP (SET_SRC (set), 0) == src
1306 && fixup_match_2 (insn, dst, src,
1307 XEXP (SET_SRC (set), 1),
1312 src_class = reg_preferred_class (REGNO (src));
1313 dst_class = reg_preferred_class (REGNO (dst));
1314 if (! regclass_compatible_p (src_class, dst_class))
1324 /* Can not modify an earlier insn to set dst if this insn
1325 uses an old value in the source. */
1326 if (reg_overlap_mentioned_p (dst, SET_SRC (set)))
1336 if (! (src_note = find_reg_note (insn, REG_DEAD, src)))
1347 /* If src is set once in a different basic block,
1348 and is set equal to a constant, then do not use
1349 it for this optimization, as this would make it
1350 no longer equivalent to a constant. */
1352 if (reg_is_remote_constant_p (src, insn, f))
1363 if (regmove_dump_file)
1364 fprintf (regmove_dump_file,
1365 "Could fix operand %d of insn %d matching operand %d.\n",
1366 op_no, INSN_UID (insn), match_no);
1368 /* Scan backward to find the first instruction that uses
1369 the input operand. If the operand is set here, then
1370 replace it in both instructions with match_no. */
1372 for (length = 0, p = PREV_INSN (insn); p; p = PREV_INSN (p))
1376 /* ??? We can't scan past the end of a basic block without
1377 updating the register lifetime info
1378 (REG_DEAD/basic_block_live_at_start). */
1379 if (perhaps_ends_bb_p (p))
1381 else if (! INSN_P (p))
1386 /* ??? See if all of SRC is set in P. This test is much
1387 more conservative than it needs to be. */
1388 pset = single_set (p);
1389 if (pset && SET_DEST (pset) == src)
1391 /* We use validate_replace_rtx, in case there
1392 are multiple identical source operands. All of
1393 them have to be changed at the same time. */
1394 if (validate_replace_rtx (src, dst, insn))
1396 if (validate_change (p, &SET_DEST (pset),
1401 /* Change all source operands back.
1402 This modifies the dst as a side-effect. */
1403 validate_replace_rtx (dst, src, insn);
1404 /* Now make sure the dst is right. */
1405 validate_change (insn,
1406 recog_data.operand_loc[match_no],
1413 if (reg_overlap_mentioned_p (src, PATTERN (p))
1414 || reg_overlap_mentioned_p (dst, PATTERN (p)))
1417 /* If we have passed a call instruction, and the
1418 pseudo-reg DST is not already live across a call,
1419 then don't perform the optimization. */
1420 if (GET_CODE (p) == CALL_INSN)
1424 if (REG_N_CALLS_CROSSED (REGNO (dst)) == 0)
1433 /* Remove the death note for SRC from INSN. */
1434 remove_note (insn, src_note);
1435 /* Move the death note for SRC to P if it is used
1437 if (reg_overlap_mentioned_p (src, PATTERN (p)))
1439 XEXP (src_note, 1) = REG_NOTES (p);
1440 REG_NOTES (p) = src_note;
1442 /* If there is a REG_DEAD note for DST on P, then remove
1443 it, because DST is now set there. */
1444 if ((dst_note = find_reg_note (p, REG_DEAD, dst)))
1445 remove_note (p, dst_note);
1447 dstno = REGNO (dst);
1448 srcno = REGNO (src);
1450 REG_N_SETS (dstno)++;
1451 REG_N_SETS (srcno)--;
1453 REG_N_CALLS_CROSSED (dstno) += num_calls;
1454 REG_N_CALLS_CROSSED (srcno) -= num_calls;
1456 REG_LIVE_LENGTH (dstno) += length;
1457 if (REG_LIVE_LENGTH (srcno) >= 0)
1459 REG_LIVE_LENGTH (srcno) -= length;
1460 /* REG_LIVE_LENGTH is only an approximation after
1461 combine if sched is not run, so make sure that we
1462 still have a reasonable value. */
1463 if (REG_LIVE_LENGTH (srcno) < 2)
1464 REG_LIVE_LENGTH (srcno) = 2;
1467 if (regmove_dump_file)
1468 fprintf (regmove_dump_file,
1469 "Fixed operand %d of insn %d matching operand %d.\n",
1470 op_no, INSN_UID (insn), match_no);
1476 /* If we weren't able to replace any of the alternatives, try an
1477 alternative appoach of copying the source to the destination. */
1478 if (!success && copy_src != NULL_RTX)
1479 copy_src_to_dest (insn, copy_src, copy_dst, old_max_uid);
1484 /* In fixup_match_1, some insns may have been inserted after basic block
1485 ends. Fix that here. */
1486 for (i = 0; i < n_basic_blocks; i++)
1488 rtx end = BLOCK_END (i);
1490 rtx next = NEXT_INSN (new);
1491 while (next != 0 && INSN_UID (next) >= old_max_uid
1492 && (i == n_basic_blocks - 1 || BLOCK_HEAD (i + 1) != next))
1493 new = next, next = NEXT_INSN (new);
1494 BLOCK_END (i) = new;
1499 free (regno_src_regno);
1500 free (regmove_bb_head);
1503 /* Returns nonzero if INSN's pattern has matching constraints for any operand.
1504 Returns 0 if INSN can't be recognized, or if the alternative can't be
1507 Initialize the info in MATCHP based on the constraints. */
1510 find_matches (insn, matchp)
1512 struct match *matchp;
1514 int likely_spilled[MAX_RECOG_OPERANDS];
1516 int any_matches = 0;
1518 extract_insn (insn);
1519 if (! constrain_operands (0))
1522 /* Must initialize this before main loop, because the code for
1523 the commutative case may set matches for operands other than
1525 for (op_no = recog_data.n_operands; --op_no >= 0; )
1526 matchp->with[op_no] = matchp->commutative[op_no] = -1;
1528 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1534 p = recog_data.constraints[op_no];
1536 likely_spilled[op_no] = 0;
1537 matchp->use[op_no] = READ;
1538 matchp->early_clobber[op_no] = 0;
1540 matchp->use[op_no] = WRITE;
1542 matchp->use[op_no] = READWRITE;
1544 for (;*p && i < which_alternative; p++)
1548 while ((c = *p++) != '\0' && c != ',')
1556 matchp->early_clobber[op_no] = 1;
1559 matchp->commutative[op_no] = op_no + 1;
1560 matchp->commutative[op_no + 1] = op_no;
1562 case '0': case '1': case '2': case '3': case '4':
1563 case '5': case '6': case '7': case '8': case '9':
1565 if (c < op_no && likely_spilled[(unsigned char) c])
1567 matchp->with[op_no] = c;
1569 if (matchp->commutative[op_no] >= 0)
1570 matchp->with[matchp->commutative[op_no]] = c;
1572 case 'a': case 'b': case 'c': case 'd': case 'e': case 'f': case 'h':
1573 case 'j': case 'k': case 'l': case 'p': case 'q': case 't': case 'u':
1574 case 'v': case 'w': case 'x': case 'y': case 'z': case 'A': case 'B':
1575 case 'C': case 'D': case 'W': case 'Y': case 'Z':
1576 if (CLASS_LIKELY_SPILLED_P (REG_CLASS_FROM_LETTER ((unsigned char)c)))
1577 likely_spilled[op_no] = 1;
1584 /* Try to replace all occurrences of DST_REG with SRC in LOC, that is
1585 assumed to be in INSN. */
1588 replace_in_call_usage (loc, dst_reg, src, insn)
1602 code = GET_CODE (x);
1605 if (REGNO (x) != dst_reg)
1608 validate_change (insn, loc, src, 1);
1613 /* Process each of our operands recursively. */
1614 fmt = GET_RTX_FORMAT (code);
1615 for (i = 0; i < GET_RTX_LENGTH (code); i++, fmt++)
1617 replace_in_call_usage (&XEXP (x, i), dst_reg, src, insn);
1618 else if (*fmt == 'E')
1619 for (j = 0; j < XVECLEN (x, i); j++)
1620 replace_in_call_usage (& XVECEXP (x, i, j), dst_reg, src, insn);
1623 /* Try to replace output operand DST in SET, with input operand SRC. SET is
1624 the only set in INSN. INSN has just been recognized and constrained.
1625 SRC is operand number OPERAND_NUMBER in INSN.
1626 DST is operand number MATCH_NUMBER in INSN.
1627 If BACKWARD is nonzero, we have been called in a backward pass.
1628 Return nonzero for success. */
1631 fixup_match_1 (insn, set, src, src_subreg, dst, backward, operand_number,
1632 match_number, regmove_dump_file)
1633 rtx insn, set, src, src_subreg, dst;
1634 int backward, operand_number, match_number;
1635 FILE *regmove_dump_file;
1638 rtx post_inc = 0, post_inc_set = 0, search_end = 0;
1640 int num_calls = 0, s_num_calls = 0;
1641 enum rtx_code code = NOTE;
1642 HOST_WIDE_INT insn_const = 0, newconst;
1643 rtx overlap = 0; /* need to move insn ? */
1644 rtx src_note = find_reg_note (insn, REG_DEAD, src), dst_note = NULL_RTX;
1645 int length, s_length;
1647 /* If SRC is marked as unchanging, we may not change it.
1648 ??? Maybe we could get better code by removing the unchanging bit
1649 instead, and changing it back if we don't succeed? */
1650 if (RTX_UNCHANGING_P (src))
1655 /* Look for (set (regX) (op regA constX))
1656 (set (regY) (op regA constY))
1658 (set (regA) (op regA constX)).
1659 (set (regY) (op regA constY-constX)).
1660 This works for add and shift operations, if
1661 regA is dead after or set by the second insn. */
1663 code = GET_CODE (SET_SRC (set));
1664 if ((code == PLUS || code == LSHIFTRT
1665 || code == ASHIFT || code == ASHIFTRT)
1666 && XEXP (SET_SRC (set), 0) == src
1667 && GET_CODE (XEXP (SET_SRC (set), 1)) == CONST_INT)
1668 insn_const = INTVAL (XEXP (SET_SRC (set), 1));
1669 else if (! stable_and_no_regs_but_for_p (SET_SRC (set), src, dst))
1672 /* We might find a src_note while scanning. */
1676 if (regmove_dump_file)
1677 fprintf (regmove_dump_file,
1678 "Could fix operand %d of insn %d matching operand %d.\n",
1679 operand_number, INSN_UID (insn), match_number);
1681 /* If SRC is equivalent to a constant set in a different basic block,
1682 then do not use it for this optimization. We want the equivalence
1683 so that if we have to reload this register, we can reload the
1684 constant, rather than extending the lifespan of the register. */
1685 if (reg_is_remote_constant_p (src, insn, get_insns ()))
1688 /* Scan forward to find the next instruction that
1689 uses the output operand. If the operand dies here,
1690 then replace it in both instructions with
1693 for (length = s_length = 0, p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
1695 if (GET_CODE (p) == CALL_INSN)
1696 replace_in_call_usage (& CALL_INSN_FUNCTION_USAGE (p),
1697 REGNO (dst), src, p);
1699 /* ??? We can't scan past the end of a basic block without updating
1700 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
1701 if (perhaps_ends_bb_p (p))
1703 else if (! INSN_P (p))
1710 if (reg_set_p (src, p) || reg_set_p (dst, p)
1711 || (GET_CODE (PATTERN (p)) == USE
1712 && reg_overlap_mentioned_p (src, XEXP (PATTERN (p), 0))))
1715 /* See if all of DST dies in P. This test is
1716 slightly more conservative than it needs to be. */
1717 if ((dst_note = find_regno_note (p, REG_DEAD, REGNO (dst)))
1718 && (GET_MODE (XEXP (dst_note, 0)) == GET_MODE (dst)))
1720 /* If we would be moving INSN, check that we won't move it
1721 into the shadow of a live a live flags register. */
1722 /* ??? We only try to move it in front of P, although
1723 we could move it anywhere between OVERLAP and P. */
1724 if (overlap && GET_MODE (PREV_INSN (p)) != VOIDmode)
1730 rtx set2 = NULL_RTX;
1732 /* If an optimization is done, the value of SRC while P
1733 is executed will be changed. Check that this is OK. */
1734 if (reg_overlap_mentioned_p (src, PATTERN (p)))
1736 for (q = p; q; q = NEXT_INSN (q))
1738 /* ??? We can't scan past the end of a basic block without
1739 updating the register lifetime info
1740 (REG_DEAD/basic_block_live_at_start). */
1741 if (perhaps_ends_bb_p (q))
1746 else if (! INSN_P (q))
1748 else if (reg_overlap_mentioned_p (src, PATTERN (q))
1749 || reg_set_p (src, q))
1753 set2 = single_set (q);
1754 if (! q || ! set2 || GET_CODE (SET_SRC (set2)) != code
1755 || XEXP (SET_SRC (set2), 0) != src
1756 || GET_CODE (XEXP (SET_SRC (set2), 1)) != CONST_INT
1757 || (SET_DEST (set2) != src
1758 && ! find_reg_note (q, REG_DEAD, src)))
1760 /* If this is a PLUS, we can still save a register by doing
1763 src -= insn_const; .
1764 This also gives opportunities for subsequent
1765 optimizations in the backward pass, so do it there. */
1766 if (code == PLUS && backward
1767 /* Don't do this if we can likely tie DST to SET_DEST
1768 of P later; we can't do this tying here if we got a
1770 && ! (dst_note && ! REG_N_CALLS_CROSSED (REGNO (dst))
1772 && GET_CODE (SET_DEST (single_set (p))) == REG
1773 && (REGNO (SET_DEST (single_set (p)))
1774 < FIRST_PSEUDO_REGISTER))
1775 /* We may only emit an insn directly after P if we
1776 are not in the shadow of a live flags register. */
1777 && GET_MODE (p) == VOIDmode)
1782 newconst = -insn_const;
1790 newconst = INTVAL (XEXP (SET_SRC (set2), 1)) - insn_const;
1791 /* Reject out of range shifts. */
1794 || ((unsigned HOST_WIDE_INT) newconst
1795 >= (GET_MODE_BITSIZE (GET_MODE
1796 (SET_SRC (set2)))))))
1801 if (SET_DEST (set2) != src)
1802 post_inc_set = set2;
1805 /* We use 1 as last argument to validate_change so that all
1806 changes are accepted or rejected together by apply_change_group
1807 when it is called by validate_replace_rtx . */
1808 validate_change (q, &XEXP (SET_SRC (set2), 1),
1809 GEN_INT (newconst), 1);
1811 validate_change (insn, recog_data.operand_loc[match_number], src, 1);
1812 if (validate_replace_rtx (dst, src_subreg, p))
1817 if (reg_overlap_mentioned_p (dst, PATTERN (p)))
1819 if (! src_note && reg_overlap_mentioned_p (src, PATTERN (p)))
1821 /* INSN was already checked to be movable wrt. the registers that it
1822 sets / uses when we found no REG_DEAD note for src on it, but it
1823 still might clobber the flags register. We'll have to check that
1824 we won't insert it into the shadow of a live flags register when
1825 we finally know where we are to move it. */
1827 src_note = find_reg_note (p, REG_DEAD, src);
1830 /* If we have passed a call instruction, and the pseudo-reg SRC is not
1831 already live across a call, then don't perform the optimization. */
1832 if (GET_CODE (p) == CALL_INSN)
1834 if (REG_N_CALLS_CROSSED (REGNO (src)) == 0)
1848 /* Remove the death note for DST from P. */
1849 remove_note (p, dst_note);
1852 post_inc = emit_insn_after (copy_rtx (PATTERN (insn)), p);
1853 if ((HAVE_PRE_INCREMENT || HAVE_PRE_DECREMENT)
1855 && try_auto_increment (search_end, post_inc, 0, src, newconst, 1))
1857 validate_change (insn, &XEXP (SET_SRC (set), 1), GEN_INT (insn_const), 0);
1858 REG_N_SETS (REGNO (src))++;
1859 REG_LIVE_LENGTH (REGNO (src))++;
1863 /* The lifetime of src and dest overlap,
1864 but we can change this by moving insn. */
1865 rtx pat = PATTERN (insn);
1867 remove_note (overlap, src_note);
1868 if ((HAVE_POST_INCREMENT || HAVE_POST_DECREMENT)
1870 && try_auto_increment (overlap, insn, 0, src, insn_const, 0))
1874 rtx notes = REG_NOTES (insn);
1876 emit_insn_after_with_line_notes (pat, PREV_INSN (p), insn);
1877 PUT_CODE (insn, NOTE);
1878 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
1879 NOTE_SOURCE_FILE (insn) = 0;
1880 /* emit_insn_after_with_line_notes has no
1881 return value, so search for the new insn. */
1883 while (! INSN_P (insn) || PATTERN (insn) != pat)
1884 insn = PREV_INSN (insn);
1886 REG_NOTES (insn) = notes;
1889 /* Sometimes we'd generate src = const; src += n;
1890 if so, replace the instruction that set src
1891 in the first place. */
1893 if (! overlap && (code == PLUS || code == MINUS))
1895 rtx note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
1896 rtx q, set2 = NULL_RTX;
1897 int num_calls2 = 0, s_length2 = 0;
1899 if (note && CONSTANT_P (XEXP (note, 0)))
1901 for (q = PREV_INSN (insn); q; q = PREV_INSN(q))
1903 /* ??? We can't scan past the end of a basic block without
1904 updating the register lifetime info
1905 (REG_DEAD/basic_block_live_at_start). */
1906 if (perhaps_ends_bb_p (q))
1911 else if (! INSN_P (q))
1915 if (reg_set_p (src, q))
1917 set2 = single_set (q);
1920 if (reg_overlap_mentioned_p (src, PATTERN (q)))
1925 if (GET_CODE (p) == CALL_INSN)
1928 if (q && set2 && SET_DEST (set2) == src && CONSTANT_P (SET_SRC (set2))
1929 && validate_change (insn, &SET_SRC (set), XEXP (note, 0), 0))
1932 NOTE_LINE_NUMBER (q) = NOTE_INSN_DELETED;
1933 NOTE_SOURCE_FILE (q) = 0;
1934 REG_N_SETS (REGNO (src))--;
1935 REG_N_CALLS_CROSSED (REGNO (src)) -= num_calls2;
1936 REG_LIVE_LENGTH (REGNO (src)) -= s_length2;
1942 if ((HAVE_PRE_INCREMENT || HAVE_PRE_DECREMENT)
1943 && (code == PLUS || code == MINUS) && insn_const
1944 && try_auto_increment (p, insn, 0, src, insn_const, 1))
1946 else if ((HAVE_POST_INCREMENT || HAVE_POST_DECREMENT)
1948 && try_auto_increment (p, post_inc, post_inc_set, src, newconst, 0))
1950 /* If post_inc still prevails, try to find an
1951 insn where it can be used as a pre-in/decrement.
1952 If code is MINUS, this was already tried. */
1953 if (post_inc && code == PLUS
1954 /* Check that newconst is likely to be usable
1955 in a pre-in/decrement before starting the search. */
1956 && ((HAVE_PRE_INCREMENT && newconst > 0 && newconst <= MOVE_MAX)
1957 || (HAVE_PRE_DECREMENT && newconst < 0 && newconst >= -MOVE_MAX))
1958 && exact_log2 (newconst))
1962 inc_dest = post_inc_set ? SET_DEST (post_inc_set) : src;
1963 for (q = post_inc; (q = NEXT_INSN (q)); )
1965 /* ??? We can't scan past the end of a basic block without updating
1966 the register lifetime info
1967 (REG_DEAD/basic_block_live_at_start). */
1968 if (perhaps_ends_bb_p (q))
1970 else if (! INSN_P (q))
1972 else if (src != inc_dest
1973 && (reg_overlap_mentioned_p (src, PATTERN (q))
1974 || reg_set_p (src, q)))
1976 else if (reg_set_p (inc_dest, q))
1978 else if (reg_overlap_mentioned_p (inc_dest, PATTERN (q)))
1980 try_auto_increment (q, post_inc,
1981 post_inc_set, inc_dest, newconst, 1);
1987 /* Move the death note for DST to INSN if it is used
1989 if (reg_overlap_mentioned_p (dst, PATTERN (insn)))
1991 XEXP (dst_note, 1) = REG_NOTES (insn);
1992 REG_NOTES (insn) = dst_note;
1997 /* Move the death note for SRC from INSN to P. */
1999 remove_note (insn, src_note);
2000 XEXP (src_note, 1) = REG_NOTES (p);
2001 REG_NOTES (p) = src_note;
2003 REG_N_CALLS_CROSSED (REGNO (src)) += s_num_calls;
2006 REG_N_SETS (REGNO (src))++;
2007 REG_N_SETS (REGNO (dst))--;
2009 REG_N_CALLS_CROSSED (REGNO (dst)) -= num_calls;
2011 REG_LIVE_LENGTH (REGNO (src)) += s_length;
2012 if (REG_LIVE_LENGTH (REGNO (dst)) >= 0)
2014 REG_LIVE_LENGTH (REGNO (dst)) -= length;
2015 /* REG_LIVE_LENGTH is only an approximation after
2016 combine if sched is not run, so make sure that we
2017 still have a reasonable value. */
2018 if (REG_LIVE_LENGTH (REGNO (dst)) < 2)
2019 REG_LIVE_LENGTH (REGNO (dst)) = 2;
2021 if (regmove_dump_file)
2022 fprintf (regmove_dump_file,
2023 "Fixed operand %d of insn %d matching operand %d.\n",
2024 operand_number, INSN_UID (insn), match_number);
2029 /* return nonzero if X is stable and mentions no regsiters but for
2030 mentioning SRC or mentioning / changing DST . If in doubt, presume
2032 The rationale is that we want to check if we can move an insn easily
2033 while just paying attention to SRC and DST. A register is considered
2034 stable if it has the RTX_UNCHANGING_P bit set, but that would still
2035 leave the burden to update REG_DEAD / REG_UNUSED notes, so we don't
2036 want any registers but SRC and DST. */
2038 stable_and_no_regs_but_for_p (x, src, dst)
2041 RTX_CODE code = GET_CODE (x);
2042 switch (GET_RTX_CLASS (code))
2044 case '<': case '1': case 'c': case '2': case 'b': case '3':
2047 const char *fmt = GET_RTX_FORMAT (code);
2048 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2050 && ! stable_and_no_regs_but_for_p (XEXP (x, i), src, dst))
2056 return x == src || x == dst;
2057 /* If this is a MEM, look inside - there might be a register hidden in
2058 the address of an unchanging MEM. */
2060 && ! stable_and_no_regs_but_for_p (XEXP (x, 0), src, dst))
2064 return ! rtx_unstable_p (x);
2068 /* Track stack adjustments and stack memory references. Attempt to
2069 reduce the number of stack adjustments by back-propogating across
2070 the memory references.
2072 This is intended primarily for use with targets that do not define
2073 ACCUMULATE_OUTGOING_ARGS. It is of significantly more value to
2074 targets that define PREFERRED_STACK_BOUNDARY more aligned than
2075 STACK_BOUNDARY (e.g. x86), or if not all registers can be pushed
2076 (e.g. x86 fp regs) which would ordinarily have to be implemented
2077 as a sub/mov pair due to restrictions in calls.c.
2079 Propogation stops when any of the insns that need adjusting are
2080 (a) no longer valid because we've exceeded their range, (b) a
2081 non-trivial push instruction, or (c) a call instruction.
2083 Restriction B is based on the assumption that push instructions
2084 are smaller or faster. If a port really wants to remove all
2085 pushes, it should have defined ACCUMULATE_OUTGOING_ARGS. The
2086 one exception that is made is for an add immediately followed
2089 /* This structure records stack memory references between stack adjusting
2094 HOST_WIDE_INT sp_offset;
2096 struct csa_memlist *next;
2099 static int stack_memref_p PARAMS ((rtx));
2100 static rtx single_set_for_csa PARAMS ((rtx));
2101 static void free_csa_memlist PARAMS ((struct csa_memlist *));
2102 static struct csa_memlist *record_one_stack_memref
2103 PARAMS ((rtx, rtx *, struct csa_memlist *));
2104 static int try_apply_stack_adjustment
2105 PARAMS ((rtx, struct csa_memlist *, HOST_WIDE_INT, HOST_WIDE_INT));
2106 static void combine_stack_adjustments_for_block PARAMS ((basic_block));
2107 static int record_stack_memrefs PARAMS ((rtx *, void *));
2110 /* Main entry point for stack adjustment combination. */
2113 combine_stack_adjustments ()
2117 for (i = 0; i < n_basic_blocks; ++i)
2118 combine_stack_adjustments_for_block (BASIC_BLOCK (i));
2121 /* Recognize a MEM of the form (sp) or (plus sp const). */
2127 if (GET_CODE (x) != MEM)
2131 if (x == stack_pointer_rtx)
2133 if (GET_CODE (x) == PLUS
2134 && XEXP (x, 0) == stack_pointer_rtx
2135 && GET_CODE (XEXP (x, 1)) == CONST_INT)
2141 /* Recognize either normal single_set or the hack in i386.md for
2142 tying fp and sp adjustments. */
2145 single_set_for_csa (insn)
2149 rtx tmp = single_set (insn);
2153 if (GET_CODE (insn) != INSN
2154 || GET_CODE (PATTERN (insn)) != PARALLEL)
2157 tmp = PATTERN (insn);
2158 if (GET_CODE (XVECEXP (tmp, 0, 0)) != SET)
2161 for (i = 1; i < XVECLEN (tmp, 0); ++i)
2163 rtx this = XVECEXP (tmp, 0, i);
2165 /* The special case is allowing a no-op set. */
2166 if (GET_CODE (this) == SET
2167 && SET_SRC (this) == SET_DEST (this))
2169 else if (GET_CODE (this) != CLOBBER
2170 && GET_CODE (this) != USE)
2174 return XVECEXP (tmp, 0, 0);
2177 /* Free the list of csa_memlist nodes. */
2180 free_csa_memlist (memlist)
2181 struct csa_memlist *memlist;
2183 struct csa_memlist *next;
2184 for (; memlist ; memlist = next)
2186 next = memlist->next;
2191 /* Create a new csa_memlist node from the given memory reference.
2192 It is already known that the memory is stack_memref_p. */
2194 static struct csa_memlist *
2195 record_one_stack_memref (insn, mem, next_memlist)
2197 struct csa_memlist *next_memlist;
2199 struct csa_memlist *ml;
2201 ml = (struct csa_memlist *) xmalloc (sizeof (*ml));
2203 if (XEXP (*mem, 0) == stack_pointer_rtx)
2206 ml->sp_offset = INTVAL (XEXP (XEXP (*mem, 0), 1));
2210 ml->next = next_memlist;
2215 /* Attempt to apply ADJUST to the stack adjusting insn INSN, as well
2216 as each of the memories in MEMLIST. Return true on success. */
2219 try_apply_stack_adjustment (insn, memlist, new_adjust, delta)
2221 struct csa_memlist *memlist;
2222 HOST_WIDE_INT new_adjust, delta;
2224 struct csa_memlist *ml;
2227 /* We know INSN matches single_set_for_csa, because that's what we
2228 recognized earlier. However, if INSN is not single_set, it is
2229 doing double duty as a barrier for frame pointer memory accesses,
2230 which we are not recording. Therefore, an adjust insn that is not
2231 single_set may not have a positive delta applied. */
2233 if (delta > 0 && ! single_set (insn))
2235 set = single_set_for_csa (insn);
2236 validate_change (insn, &XEXP (SET_SRC (set), 1), GEN_INT (new_adjust), 1);
2238 for (ml = memlist; ml ; ml = ml->next)
2240 HOST_WIDE_INT c = ml->sp_offset - delta;
2241 rtx new = gen_rtx_MEM (GET_MODE (*ml->mem),
2242 plus_constant (stack_pointer_rtx, c));
2244 /* Don't reference memory below the stack pointer. */
2251 MEM_COPY_ATTRIBUTES (new, *ml->mem);
2252 validate_change (ml->insn, ml->mem, new, 1);
2255 if (apply_change_group ())
2257 /* Succeeded. Update our knowledge of the memory references. */
2258 for (ml = memlist; ml ; ml = ml->next)
2259 ml->sp_offset -= delta;
2267 /* Called via for_each_rtx and used to record all stack memory references in
2268 the insn and discard all other stack pointer references. */
2269 struct record_stack_memrefs_data
2272 struct csa_memlist *memlist;
2276 record_stack_memrefs (xp, data)
2281 struct record_stack_memrefs_data *d =
2282 (struct record_stack_memrefs_data *) data;
2285 switch (GET_CODE (x))
2288 if (!reg_mentioned_p (stack_pointer_rtx, x))
2290 /* We are not able to handle correctly all possible memrefs containing
2291 stack pointer, so this check is neccesary. */
2292 if (stack_memref_p (x))
2294 d->memlist = record_one_stack_memref (d->insn, xp, d->memlist);
2299 /* ??? We want be able to handle non-memory stack pointer references
2300 later. For now just discard all insns refering to stack pointer
2301 outside mem expressions. We would probably want to teach
2302 validate_replace to simplify expressions first. */
2303 if (x == stack_pointer_rtx)
2312 /* Subroutine of combine_stack_adjustments, called for each basic block. */
2315 combine_stack_adjustments_for_block (bb)
2318 HOST_WIDE_INT last_sp_adjust = 0;
2319 rtx last_sp_set = NULL_RTX;
2320 struct csa_memlist *memlist = NULL;
2323 struct record_stack_memrefs_data data;
2325 for (insn = bb->head; ; insn = next)
2329 pending_delete = NULL_RTX;
2330 next = NEXT_INSN (insn);
2332 if (! INSN_P (insn))
2335 set = single_set_for_csa (insn);
2338 rtx dest = SET_DEST (set);
2339 rtx src = SET_SRC (set);
2341 /* Find constant additions to the stack pointer. */
2342 if (dest == stack_pointer_rtx
2343 && GET_CODE (src) == PLUS
2344 && XEXP (src, 0) == stack_pointer_rtx
2345 && GET_CODE (XEXP (src, 1)) == CONST_INT)
2347 HOST_WIDE_INT this_adjust = INTVAL (XEXP (src, 1));
2349 /* If we've not seen an adjustment previously, record
2350 it now and continue. */
2354 last_sp_adjust = this_adjust;
2358 /* If not all recorded memrefs can be adjusted, or the
2359 adjustment is now too large for a constant addition,
2360 we cannot merge the two stack adjustments. */
2361 if (! try_apply_stack_adjustment (last_sp_set, memlist,
2362 last_sp_adjust + this_adjust,
2365 free_csa_memlist (memlist);
2368 last_sp_adjust = this_adjust;
2373 pending_delete = insn;
2374 last_sp_adjust += this_adjust;
2376 /* If, by some accident, the adjustments cancel out,
2377 delete both insns and start from scratch. */
2378 if (last_sp_adjust == 0)
2380 if (last_sp_set == bb->head)
2381 bb->head = NEXT_INSN (last_sp_set);
2382 flow_delete_insn (last_sp_set);
2384 free_csa_memlist (memlist);
2386 last_sp_set = NULL_RTX;
2392 /* Find a predecrement of exactly the previous adjustment and
2393 turn it into a direct store. Obviously we can't do this if
2394 there were any intervening uses of the stack pointer. */
2396 && GET_CODE (dest) == MEM
2397 && ((GET_CODE (XEXP (dest, 0)) == PRE_DEC
2399 == (HOST_WIDE_INT) GET_MODE_SIZE (GET_MODE (dest))))
2400 || (GET_CODE (XEXP (dest, 0)) == PRE_MODIFY
2401 && GET_CODE (XEXP (XEXP (dest, 0), 1)) == PLUS
2402 && XEXP (XEXP (XEXP (dest, 0), 1), 0) == stack_pointer_rtx
2403 && (GET_CODE (XEXP (XEXP (XEXP (dest, 0), 1), 1))
2405 && (INTVAL (XEXP (XEXP (XEXP (dest, 0), 1), 1))
2406 == -last_sp_adjust)))
2407 && XEXP (XEXP (dest, 0), 0) == stack_pointer_rtx
2408 && ! reg_mentioned_p (stack_pointer_rtx, src)
2409 && memory_address_p (GET_MODE (dest), stack_pointer_rtx)
2410 && validate_change (insn, &SET_DEST (set),
2411 change_address (dest, VOIDmode,
2412 stack_pointer_rtx), 0))
2414 if (last_sp_set == bb->head)
2415 bb->head = NEXT_INSN (last_sp_set);
2416 flow_delete_insn (last_sp_set);
2418 free_csa_memlist (memlist);
2420 last_sp_set = NULL_RTX;
2427 data.memlist = memlist;
2428 if (GET_CODE (insn) != CALL_INSN && last_sp_set
2429 && !for_each_rtx (&PATTERN (insn), record_stack_memrefs, &data))
2431 memlist = data.memlist;
2434 memlist = data.memlist;
2436 /* Otherwise, we were not able to process the instruction.
2437 Do not continue collecting data across such a one. */
2439 && (GET_CODE (insn) == CALL_INSN
2440 || reg_mentioned_p (stack_pointer_rtx, PATTERN (insn))))
2442 free_csa_memlist (memlist);
2444 last_sp_set = NULL_RTX;
2449 if (insn == bb->end)
2453 flow_delete_insn (pending_delete);
2458 bb->end = PREV_INSN (pending_delete);
2459 flow_delete_insn (pending_delete);