1 /* Move registers around to reduce number of move instructions needed.
2 Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3 1999, 2000, 2001, 2002 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
23 /* This module looks for cases where matching constraints would force
24 an instruction to need a reload, and this reload would be a register
25 to register move. It then attempts to change the registers used by the
26 instruction to avoid the move instruction. */
30 #include "coretypes.h"
32 #include "rtl.h" /* stdio.h must precede rtl.h for FFS. */
34 #include "insn-config.h"
38 #include "hard-reg-set.h"
42 #include "basic-block.h"
48 /* Turn STACK_GROWS_DOWNWARD into a boolean. */
49 #ifdef STACK_GROWS_DOWNWARD
50 #undef STACK_GROWS_DOWNWARD
51 #define STACK_GROWS_DOWNWARD 1
53 #define STACK_GROWS_DOWNWARD 0
56 static int perhaps_ends_bb_p PARAMS ((rtx));
57 static int optimize_reg_copy_1 PARAMS ((rtx, rtx, rtx));
58 static void optimize_reg_copy_2 PARAMS ((rtx, rtx, rtx));
59 static void optimize_reg_copy_3 PARAMS ((rtx, rtx, rtx));
60 static void copy_src_to_dest PARAMS ((rtx, rtx, rtx, int));
61 static int *regmove_bb_head;
64 int with[MAX_RECOG_OPERANDS];
65 enum { READ, WRITE, READWRITE } use[MAX_RECOG_OPERANDS];
66 int commutative[MAX_RECOG_OPERANDS];
67 int early_clobber[MAX_RECOG_OPERANDS];
70 static rtx discover_flags_reg PARAMS ((void));
71 static void mark_flags_life_zones PARAMS ((rtx));
72 static void flags_set_1 PARAMS ((rtx, rtx, void *));
74 static int try_auto_increment PARAMS ((rtx, rtx, rtx, rtx, HOST_WIDE_INT, int));
75 static int find_matches PARAMS ((rtx, struct match *));
76 static void replace_in_call_usage PARAMS ((rtx *, unsigned int, rtx, rtx));
77 static int fixup_match_1 PARAMS ((rtx, rtx, rtx, rtx, rtx, int, int, int, FILE *))
79 static int reg_is_remote_constant_p PARAMS ((rtx, rtx, rtx));
80 static int stable_and_no_regs_but_for_p PARAMS ((rtx, rtx, rtx));
81 static int regclass_compatible_p PARAMS ((int, int));
82 static int replacement_quality PARAMS ((rtx));
83 static int fixup_match_2 PARAMS ((rtx, rtx, rtx, rtx, FILE *));
85 /* Return nonzero if registers with CLASS1 and CLASS2 can be merged without
86 causing too much register allocation problems. */
88 regclass_compatible_p (class0, class1)
91 return (class0 == class1
92 || (reg_class_subset_p (class0, class1)
93 && ! CLASS_LIKELY_SPILLED_P (class0))
94 || (reg_class_subset_p (class1, class0)
95 && ! CLASS_LIKELY_SPILLED_P (class1)));
98 /* INC_INSN is an instruction that adds INCREMENT to REG.
99 Try to fold INC_INSN as a post/pre in/decrement into INSN.
100 Iff INC_INSN_SET is nonzero, inc_insn has a destination different from src.
101 Return nonzero for success. */
103 try_auto_increment (insn, inc_insn, inc_insn_set, reg, increment, pre)
104 rtx reg, insn, inc_insn ,inc_insn_set;
105 HOST_WIDE_INT increment;
108 enum rtx_code inc_code;
110 rtx pset = single_set (insn);
113 /* Can't use the size of SET_SRC, we might have something like
114 (sign_extend:SI (mem:QI ... */
115 rtx use = find_use_as_address (pset, reg, 0);
116 if (use != 0 && use != (rtx) (size_t) 1)
118 int size = GET_MODE_SIZE (GET_MODE (use));
120 || (HAVE_POST_INCREMENT
121 && pre == 0 && (inc_code = POST_INC, increment == size))
122 || (HAVE_PRE_INCREMENT
123 && pre == 1 && (inc_code = PRE_INC, increment == size))
124 || (HAVE_POST_DECREMENT
125 && pre == 0 && (inc_code = POST_DEC, increment == -size))
126 || (HAVE_PRE_DECREMENT
127 && pre == 1 && (inc_code = PRE_DEC, increment == -size))
133 &SET_SRC (inc_insn_set),
134 XEXP (SET_SRC (inc_insn_set), 0), 1);
135 validate_change (insn, &XEXP (use, 0),
136 gen_rtx_fmt_e (inc_code, Pmode, reg), 1);
137 if (apply_change_group ())
139 /* If there is a REG_DEAD note on this insn, we must
140 change this not to REG_UNUSED meaning that the register
141 is set, but the value is dead. Failure to do so will
142 result in a sched1 abort -- when it recomputes lifetime
143 information, the number of REG_DEAD notes will have
145 rtx note = find_reg_note (insn, REG_DEAD, reg);
147 PUT_MODE (note, REG_UNUSED);
150 = gen_rtx_EXPR_LIST (REG_INC,
151 reg, REG_NOTES (insn));
153 delete_insn (inc_insn);
162 /* Determine if the pattern generated by add_optab has a clobber,
163 such as might be issued for a flags hard register. To make the
164 code elsewhere simpler, we handle cc0 in this same framework.
166 Return the register if one was discovered. Return NULL_RTX if
167 if no flags were found. Return pc_rtx if we got confused. */
170 discover_flags_reg ()
173 tmp = gen_rtx_REG (word_mode, 10000);
174 tmp = gen_add3_insn (tmp, tmp, GEN_INT (2));
176 /* If we get something that isn't a simple set, or a
177 [(set ..) (clobber ..)], this whole function will go wrong. */
178 if (GET_CODE (tmp) == SET)
180 else if (GET_CODE (tmp) == PARALLEL)
184 if (XVECLEN (tmp, 0) != 2)
186 tmp = XVECEXP (tmp, 0, 1);
187 if (GET_CODE (tmp) != CLOBBER)
191 /* Don't do anything foolish if the md wanted to clobber a
192 scratch or something. We only care about hard regs.
193 Moreover we don't like the notion of subregs of hard regs. */
194 if (GET_CODE (tmp) == SUBREG
195 && GET_CODE (SUBREG_REG (tmp)) == REG
196 && REGNO (SUBREG_REG (tmp)) < FIRST_PSEUDO_REGISTER)
198 found = (GET_CODE (tmp) == REG && REGNO (tmp) < FIRST_PSEUDO_REGISTER);
200 return (found ? tmp : NULL_RTX);
206 /* It is a tedious task identifying when the flags register is live and
207 when it is safe to optimize. Since we process the instruction stream
208 multiple times, locate and record these live zones by marking the
209 mode of the instructions --
211 QImode is used on the instruction at which the flags becomes live.
213 HImode is used within the range (exclusive) that the flags are
214 live. Thus the user of the flags is not marked.
216 All other instructions are cleared to VOIDmode. */
218 /* Used to communicate with flags_set_1. */
219 static rtx flags_set_1_rtx;
220 static int flags_set_1_set;
223 mark_flags_life_zones (flags)
231 /* If we found a flags register on a cc0 host, bail. */
232 if (flags == NULL_RTX)
234 else if (flags != cc0_rtx)
238 /* Simple cases first: if no flags, clear all modes. If confusing,
239 mark the entire function as being in a flags shadow. */
240 if (flags == NULL_RTX || flags == pc_rtx)
242 enum machine_mode mode = (flags ? HImode : VOIDmode);
244 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
245 PUT_MODE (insn, mode);
253 flags_regno = REGNO (flags);
254 flags_nregs = HARD_REGNO_NREGS (flags_regno, GET_MODE (flags));
256 flags_set_1_rtx = flags;
258 /* Process each basic block. */
259 FOR_EACH_BB_REVERSE (block)
267 /* Look out for the (unlikely) case of flags being live across
268 basic block boundaries. */
273 for (i = 0; i < flags_nregs; ++i)
274 live |= REGNO_REG_SET_P (block->global_live_at_start,
281 /* Process liveness in reverse order of importance --
282 alive, death, birth. This lets more important info
283 overwrite the mode of lesser info. */
288 /* In the cc0 case, death is not marked in reg notes,
289 but is instead the mere use of cc0 when it is alive. */
290 if (live && reg_mentioned_p (cc0_rtx, PATTERN (insn)))
293 /* In the hard reg case, we watch death notes. */
294 if (live && find_regno_note (insn, REG_DEAD, flags_regno))
297 PUT_MODE (insn, (live ? HImode : VOIDmode));
299 /* In either case, birth is denoted simply by it's presence
300 as the destination of a set. */
302 note_stores (PATTERN (insn), flags_set_1, NULL);
306 PUT_MODE (insn, QImode);
310 PUT_MODE (insn, (live ? HImode : VOIDmode));
314 insn = NEXT_INSN (insn);
319 /* A subroutine of mark_flags_life_zones, called through note_stores. */
322 flags_set_1 (x, pat, data)
324 void *data ATTRIBUTE_UNUSED;
326 if (GET_CODE (pat) == SET
327 && reg_overlap_mentioned_p (x, flags_set_1_rtx))
331 static int *regno_src_regno;
333 /* Indicate how good a choice REG (which appears as a source) is to replace
334 a destination register with. The higher the returned value, the better
335 the choice. The main objective is to avoid using a register that is
336 a candidate for tying to a hard register, since the output might in
337 turn be a candidate to be tied to a different hard register. */
339 replacement_quality (reg)
344 /* Bad if this isn't a register at all. */
345 if (GET_CODE (reg) != REG)
348 /* If this register is not meant to get a hard register,
349 it is a poor choice. */
350 if (REG_LIVE_LENGTH (REGNO (reg)) < 0)
353 src_regno = regno_src_regno[REGNO (reg)];
355 /* If it was not copied from another register, it is fine. */
359 /* Copied from a hard register? */
360 if (src_regno < FIRST_PSEUDO_REGISTER)
363 /* Copied from a pseudo register - not as bad as from a hard register,
364 yet still cumbersome, since the register live length will be lengthened
365 when the registers get tied. */
369 /* Return 1 if INSN might end a basic block. */
371 static int perhaps_ends_bb_p (insn)
374 switch (GET_CODE (insn))
378 /* These always end a basic block. */
382 /* A CALL_INSN might be the last insn of a basic block, if it is inside
383 an EH region or if there are nonlocal gotos. Note that this test is
384 very conservative. */
385 if (nonlocal_goto_handler_labels)
389 return can_throw_internal (insn);
393 /* INSN is a copy from SRC to DEST, both registers, and SRC does not die
396 Search forward to see if SRC dies before either it or DEST is modified,
397 but don't scan past the end of a basic block. If so, we can replace SRC
398 with DEST and let SRC die in INSN.
400 This will reduce the number of registers live in that range and may enable
401 DEST to be tied to SRC, thus often saving one register in addition to a
402 register-register copy. */
405 optimize_reg_copy_1 (insn, dest, src)
413 int sregno = REGNO (src);
414 int dregno = REGNO (dest);
416 /* We don't want to mess with hard regs if register classes are small. */
418 || (SMALL_REGISTER_CLASSES
419 && (sregno < FIRST_PSEUDO_REGISTER
420 || dregno < FIRST_PSEUDO_REGISTER))
421 /* We don't see all updates to SP if they are in an auto-inc memory
422 reference, so we must disallow this optimization on them. */
423 || sregno == STACK_POINTER_REGNUM || dregno == STACK_POINTER_REGNUM)
426 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
428 /* ??? We can't scan past the end of a basic block without updating
429 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
430 if (perhaps_ends_bb_p (p))
432 else if (! INSN_P (p))
435 if (reg_set_p (src, p) || reg_set_p (dest, p)
436 /* Don't change a USE of a register. */
437 || (GET_CODE (PATTERN (p)) == USE
438 && reg_overlap_mentioned_p (src, XEXP (PATTERN (p), 0))))
441 /* See if all of SRC dies in P. This test is slightly more
442 conservative than it needs to be. */
443 if ((note = find_regno_note (p, REG_DEAD, sregno)) != 0
444 && GET_MODE (XEXP (note, 0)) == GET_MODE (src))
452 /* We can do the optimization. Scan forward from INSN again,
453 replacing regs as we go. Set FAILED if a replacement can't
454 be done. In that case, we can't move the death note for SRC.
455 This should be rare. */
457 /* Set to stop at next insn. */
458 for (q = next_real_insn (insn);
459 q != next_real_insn (p);
460 q = next_real_insn (q))
462 if (reg_overlap_mentioned_p (src, PATTERN (q)))
464 /* If SRC is a hard register, we might miss some
465 overlapping registers with validate_replace_rtx,
466 so we would have to undo it. We can't if DEST is
467 present in the insn, so fail in that combination
469 if (sregno < FIRST_PSEUDO_REGISTER
470 && reg_mentioned_p (dest, PATTERN (q)))
473 /* Replace all uses and make sure that the register
474 isn't still present. */
475 else if (validate_replace_rtx (src, dest, q)
476 && (sregno >= FIRST_PSEUDO_REGISTER
477 || ! reg_overlap_mentioned_p (src,
482 validate_replace_rtx (dest, src, q);
487 /* For SREGNO, count the total number of insns scanned.
488 For DREGNO, count the total number of insns scanned after
489 passing the death note for DREGNO. */
494 /* If the insn in which SRC dies is a CALL_INSN, don't count it
495 as a call that has been crossed. Otherwise, count it. */
496 if (q != p && GET_CODE (q) == CALL_INSN)
498 /* Similarly, total calls for SREGNO, total calls beyond
499 the death note for DREGNO. */
505 /* If DEST dies here, remove the death note and save it for
506 later. Make sure ALL of DEST dies here; again, this is
507 overly conservative. */
509 && (dest_death = find_regno_note (q, REG_DEAD, dregno)) != 0)
511 if (GET_MODE (XEXP (dest_death, 0)) != GET_MODE (dest))
512 failed = 1, dest_death = 0;
514 remove_note (q, dest_death);
520 /* These counters need to be updated if and only if we are
521 going to move the REG_DEAD note. */
522 if (sregno >= FIRST_PSEUDO_REGISTER)
524 if (REG_LIVE_LENGTH (sregno) >= 0)
526 REG_LIVE_LENGTH (sregno) -= s_length;
527 /* REG_LIVE_LENGTH is only an approximation after
528 combine if sched is not run, so make sure that we
529 still have a reasonable value. */
530 if (REG_LIVE_LENGTH (sregno) < 2)
531 REG_LIVE_LENGTH (sregno) = 2;
534 REG_N_CALLS_CROSSED (sregno) -= s_n_calls;
537 /* Move death note of SRC from P to INSN. */
538 remove_note (p, note);
539 XEXP (note, 1) = REG_NOTES (insn);
540 REG_NOTES (insn) = note;
543 /* DEST is also dead if INSN has a REG_UNUSED note for DEST. */
545 && (dest_death = find_regno_note (insn, REG_UNUSED, dregno)))
547 PUT_REG_NOTE_KIND (dest_death, REG_DEAD);
548 remove_note (insn, dest_death);
551 /* Put death note of DEST on P if we saw it die. */
554 XEXP (dest_death, 1) = REG_NOTES (p);
555 REG_NOTES (p) = dest_death;
557 if (dregno >= FIRST_PSEUDO_REGISTER)
559 /* If and only if we are moving the death note for DREGNO,
560 then we need to update its counters. */
561 if (REG_LIVE_LENGTH (dregno) >= 0)
562 REG_LIVE_LENGTH (dregno) += d_length;
563 REG_N_CALLS_CROSSED (dregno) += d_n_calls;
570 /* If SRC is a hard register which is set or killed in some other
571 way, we can't do this optimization. */
572 else if (sregno < FIRST_PSEUDO_REGISTER
573 && dead_or_set_p (p, src))
579 /* INSN is a copy of SRC to DEST, in which SRC dies. See if we now have
580 a sequence of insns that modify DEST followed by an insn that sets
581 SRC to DEST in which DEST dies, with no prior modification of DEST.
582 (There is no need to check if the insns in between actually modify
583 DEST. We should not have cases where DEST is not modified, but
584 the optimization is safe if no such modification is detected.)
585 In that case, we can replace all uses of DEST, starting with INSN and
586 ending with the set of SRC to DEST, with SRC. We do not do this
587 optimization if a CALL_INSN is crossed unless SRC already crosses a
588 call or if DEST dies before the copy back to SRC.
590 It is assumed that DEST and SRC are pseudos; it is too complicated to do
591 this for hard registers since the substitutions we may make might fail. */
594 optimize_reg_copy_2 (insn, dest, src)
601 int sregno = REGNO (src);
602 int dregno = REGNO (dest);
604 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
606 /* ??? We can't scan past the end of a basic block without updating
607 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
608 if (perhaps_ends_bb_p (p))
610 else if (! INSN_P (p))
613 set = single_set (p);
614 if (set && SET_SRC (set) == dest && SET_DEST (set) == src
615 && find_reg_note (p, REG_DEAD, dest))
617 /* We can do the optimization. Scan forward from INSN again,
618 replacing regs as we go. */
620 /* Set to stop at next insn. */
621 for (q = insn; q != NEXT_INSN (p); q = NEXT_INSN (q))
624 if (reg_mentioned_p (dest, PATTERN (q)))
625 PATTERN (q) = replace_rtx (PATTERN (q), dest, src);
628 if (GET_CODE (q) == CALL_INSN)
630 REG_N_CALLS_CROSSED (dregno)--;
631 REG_N_CALLS_CROSSED (sregno)++;
635 remove_note (p, find_reg_note (p, REG_DEAD, dest));
636 REG_N_DEATHS (dregno)--;
637 remove_note (insn, find_reg_note (insn, REG_DEAD, src));
638 REG_N_DEATHS (sregno)--;
642 if (reg_set_p (src, p)
643 || find_reg_note (p, REG_DEAD, dest)
644 || (GET_CODE (p) == CALL_INSN && REG_N_CALLS_CROSSED (sregno) == 0))
648 /* INSN is a ZERO_EXTEND or SIGN_EXTEND of SRC to DEST.
649 Look if SRC dies there, and if it is only set once, by loading
650 it from memory. If so, try to encorporate the zero/sign extension
651 into the memory read, change SRC to the mode of DEST, and alter
652 the remaining accesses to use the appropriate SUBREG. This allows
653 SRC and DEST to be tied later. */
655 optimize_reg_copy_3 (insn, dest, src)
660 rtx src_reg = XEXP (src, 0);
661 int src_no = REGNO (src_reg);
662 int dst_no = REGNO (dest);
664 enum machine_mode old_mode;
666 if (src_no < FIRST_PSEUDO_REGISTER
667 || dst_no < FIRST_PSEUDO_REGISTER
668 || ! find_reg_note (insn, REG_DEAD, src_reg)
669 || REG_N_DEATHS (src_no) != 1
670 || REG_N_SETS (src_no) != 1)
672 for (p = PREV_INSN (insn); p && ! reg_set_p (src_reg, p); p = PREV_INSN (p))
673 /* ??? We can't scan past the end of a basic block without updating
674 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
675 if (perhaps_ends_bb_p (p))
681 if (! (set = single_set (p))
682 || GET_CODE (SET_SRC (set)) != MEM
683 /* If there's a REG_EQUIV note, this must be an insn that loads an
684 argument. Prefer keeping the note over doing this optimization. */
685 || find_reg_note (p, REG_EQUIV, NULL_RTX)
686 || SET_DEST (set) != src_reg)
689 /* Be conservative: although this optimization is also valid for
690 volatile memory references, that could cause trouble in later passes. */
691 if (MEM_VOLATILE_P (SET_SRC (set)))
694 /* Do not use a SUBREG to truncate from one mode to another if truncation
696 if (GET_MODE_BITSIZE (GET_MODE (src_reg)) <= GET_MODE_BITSIZE (GET_MODE (src))
697 && !TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (GET_MODE (src)),
698 GET_MODE_BITSIZE (GET_MODE (src_reg))))
701 old_mode = GET_MODE (src_reg);
702 PUT_MODE (src_reg, GET_MODE (src));
703 XEXP (src, 0) = SET_SRC (set);
705 /* Include this change in the group so that it's easily undone if
706 one of the changes in the group is invalid. */
707 validate_change (p, &SET_SRC (set), src, 1);
709 /* Now walk forward making additional replacements. We want to be able
710 to undo all the changes if a later substitution fails. */
711 subreg = gen_lowpart_SUBREG (old_mode, src_reg);
712 while (p = NEXT_INSN (p), p != insn)
717 /* Make a tenative change. */
718 validate_replace_rtx_group (src_reg, subreg, p);
721 validate_replace_rtx_group (src, src_reg, insn);
723 /* Now see if all the changes are valid. */
724 if (! apply_change_group ())
726 /* One or more changes were no good. Back out everything. */
727 PUT_MODE (src_reg, old_mode);
728 XEXP (src, 0) = src_reg;
732 rtx note = find_reg_note (p, REG_EQUAL, NULL_RTX);
734 remove_note (p, note);
739 /* If we were not able to update the users of src to use dest directly, try
740 instead moving the value to dest directly before the operation. */
743 copy_src_to_dest (insn, src, dest, old_max_uid)
762 /* A REG_LIVE_LENGTH of -1 indicates the register is equivalent to a constant
763 or memory location and is used infrequently; a REG_LIVE_LENGTH of -2 is
764 parameter when there is no frame pointer that is not allocated a register.
765 For now, we just reject them, rather than incrementing the live length. */
767 if (GET_CODE (src) == REG
768 && REG_LIVE_LENGTH (REGNO (src)) > 0
769 && GET_CODE (dest) == REG
770 && !RTX_UNCHANGING_P (dest)
771 && REG_LIVE_LENGTH (REGNO (dest)) > 0
772 && (set = single_set (insn)) != NULL_RTX
773 && !reg_mentioned_p (dest, SET_SRC (set))
774 && GET_MODE (src) == GET_MODE (dest))
776 int old_num_regs = reg_rtx_no;
778 /* Generate the src->dest move. */
780 emit_move_insn (dest, src);
783 /* If this sequence uses new registers, we may not use it. */
784 if (old_num_regs != reg_rtx_no
785 || ! validate_replace_rtx (src, dest, insn))
787 /* We have to restore reg_rtx_no to its old value, lest
788 recompute_reg_usage will try to compute the usage of the
789 new regs, yet reg_n_info is not valid for them. */
790 reg_rtx_no = old_num_regs;
793 emit_insn_before (seq, insn);
794 move_insn = PREV_INSN (insn);
795 p_move_notes = ®_NOTES (move_insn);
796 p_insn_notes = ®_NOTES (insn);
798 /* Move any notes mentioning src to the move instruction. */
799 for (link = REG_NOTES (insn); link != NULL_RTX; link = next)
801 next = XEXP (link, 1);
802 if (XEXP (link, 0) == src)
804 *p_move_notes = link;
805 p_move_notes = &XEXP (link, 1);
809 *p_insn_notes = link;
810 p_insn_notes = &XEXP (link, 1);
814 *p_move_notes = NULL_RTX;
815 *p_insn_notes = NULL_RTX;
817 /* Is the insn the head of a basic block? If so extend it. */
818 insn_uid = INSN_UID (insn);
819 move_uid = INSN_UID (move_insn);
820 if (insn_uid < old_max_uid)
822 bb = regmove_bb_head[insn_uid];
825 BLOCK_HEAD (bb) = move_insn;
826 regmove_bb_head[insn_uid] = -1;
830 /* Update the various register tables. */
831 dest_regno = REGNO (dest);
832 REG_N_SETS (dest_regno) ++;
833 REG_LIVE_LENGTH (dest_regno)++;
834 if (REGNO_FIRST_UID (dest_regno) == insn_uid)
835 REGNO_FIRST_UID (dest_regno) = move_uid;
837 src_regno = REGNO (src);
838 if (! find_reg_note (move_insn, REG_DEAD, src))
839 REG_LIVE_LENGTH (src_regno)++;
841 if (REGNO_FIRST_UID (src_regno) == insn_uid)
842 REGNO_FIRST_UID (src_regno) = move_uid;
844 if (REGNO_LAST_UID (src_regno) == insn_uid)
845 REGNO_LAST_UID (src_regno) = move_uid;
847 if (REGNO_LAST_NOTE_UID (src_regno) == insn_uid)
848 REGNO_LAST_NOTE_UID (src_regno) = move_uid;
853 /* Return whether REG is set in only one location, and is set to a
854 constant, but is set in a different basic block from INSN (an
855 instructions which uses REG). In this case REG is equivalent to a
856 constant, and we don't want to break that equivalence, because that
857 may increase register pressure and make reload harder. If REG is
858 set in the same basic block as INSN, we don't worry about it,
859 because we'll probably need a register anyhow (??? but what if REG
860 is used in a different basic block as well as this one?). FIRST is
861 the first insn in the function. */
864 reg_is_remote_constant_p (reg, insn, first)
871 if (REG_N_SETS (REGNO (reg)) != 1)
874 /* Look for the set. */
875 for (p = LOG_LINKS (insn); p; p = XEXP (p, 1))
879 if (REG_NOTE_KIND (p) != 0)
881 s = single_set (XEXP (p, 0));
883 && GET_CODE (SET_DEST (s)) == REG
884 && REGNO (SET_DEST (s)) == REGNO (reg))
886 /* The register is set in the same basic block. */
891 for (p = first; p && p != insn; p = NEXT_INSN (p))
899 && GET_CODE (SET_DEST (s)) == REG
900 && REGNO (SET_DEST (s)) == REGNO (reg))
902 /* This is the instruction which sets REG. If there is a
903 REG_EQUAL note, then REG is equivalent to a constant. */
904 if (find_reg_note (p, REG_EQUAL, NULL_RTX))
913 /* INSN is adding a CONST_INT to a REG. We search backwards looking for
914 another add immediate instruction with the same source and dest registers,
915 and if we find one, we change INSN to an increment, and return 1. If
916 no changes are made, we return 0.
919 (set (reg100) (plus reg1 offset1))
921 (set (reg100) (plus reg1 offset2))
923 (set (reg100) (plus reg1 offset1))
925 (set (reg100) (plus reg100 offset2-offset1)) */
927 /* ??? What does this comment mean? */
928 /* cse disrupts preincrement / postdecrement sequences when it finds a
929 hard register as ultimate source, like the frame pointer. */
932 fixup_match_2 (insn, dst, src, offset, regmove_dump_file)
933 rtx insn, dst, src, offset;
934 FILE *regmove_dump_file;
936 rtx p, dst_death = 0;
937 int length, num_calls = 0;
939 /* If SRC dies in INSN, we'd have to move the death note. This is
940 considered to be very unlikely, so we just skip the optimization
942 if (find_regno_note (insn, REG_DEAD, REGNO (src)))
945 /* Scan backward to find the first instruction that sets DST. */
947 for (length = 0, p = PREV_INSN (insn); p; p = PREV_INSN (p))
951 /* ??? We can't scan past the end of a basic block without updating
952 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
953 if (perhaps_ends_bb_p (p))
955 else if (! INSN_P (p))
958 if (find_regno_note (p, REG_DEAD, REGNO (dst)))
963 pset = single_set (p);
964 if (pset && SET_DEST (pset) == dst
965 && GET_CODE (SET_SRC (pset)) == PLUS
966 && XEXP (SET_SRC (pset), 0) == src
967 && GET_CODE (XEXP (SET_SRC (pset), 1)) == CONST_INT)
969 HOST_WIDE_INT newconst
970 = INTVAL (offset) - INTVAL (XEXP (SET_SRC (pset), 1));
971 rtx add = gen_add3_insn (dst, dst, GEN_INT (newconst));
973 if (add && validate_change (insn, &PATTERN (insn), add, 0))
975 /* Remove the death note for DST from DST_DEATH. */
978 remove_death (REGNO (dst), dst_death);
979 REG_LIVE_LENGTH (REGNO (dst)) += length;
980 REG_N_CALLS_CROSSED (REGNO (dst)) += num_calls;
983 if (regmove_dump_file)
984 fprintf (regmove_dump_file,
985 "Fixed operand of insn %d.\n",
989 for (p = PREV_INSN (insn); p; p = PREV_INSN (p))
991 if (GET_CODE (p) == CODE_LABEL
992 || GET_CODE (p) == JUMP_INSN)
996 if (reg_overlap_mentioned_p (dst, PATTERN (p)))
998 if (try_auto_increment (p, insn, 0, dst, newconst, 0))
1003 for (p = NEXT_INSN (insn); p; p = NEXT_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 try_auto_increment (p, insn, 0, dst, newconst, 1);
1021 if (reg_set_p (dst, PATTERN (p)))
1024 /* If we have passed a call instruction, and the
1025 pseudo-reg SRC is not already live across a call,
1026 then don't perform the optimization. */
1027 /* reg_set_p is overly conservative for CALL_INSNS, thinks that all
1028 hard regs are clobbered. Thus, we only use it for src for
1030 if (GET_CODE (p) == CALL_INSN)
1035 if (REG_N_CALLS_CROSSED (REGNO (src)) == 0)
1038 if (call_used_regs [REGNO (dst)]
1039 || find_reg_fusage (p, CLOBBER, dst))
1042 else if (reg_set_p (src, PATTERN (p)))
1049 /* Main entry for the register move optimization.
1050 F is the first instruction.
1051 NREGS is one plus the highest pseudo-reg number used in the instruction.
1052 REGMOVE_DUMP_FILE is a stream for output of a trace of actions taken
1053 (or 0 if none should be output). */
1056 regmove_optimize (f, nregs, regmove_dump_file)
1059 FILE *regmove_dump_file;
1061 int old_max_uid = get_max_uid ();
1066 rtx copy_src, copy_dst;
1069 /* ??? Hack. Regmove doesn't examine the CFG, and gets mightily
1070 confused by non-call exceptions ending blocks. */
1071 if (flag_non_call_exceptions)
1074 /* Find out where a potential flags register is live, and so that we
1075 can suppress some optimizations in those zones. */
1076 mark_flags_life_zones (discover_flags_reg ());
1078 regno_src_regno = (int *) xmalloc (sizeof *regno_src_regno * nregs);
1079 for (i = nregs; --i >= 0; ) regno_src_regno[i] = -1;
1081 regmove_bb_head = (int *) xmalloc (sizeof (int) * (old_max_uid + 1));
1082 for (i = old_max_uid; i >= 0; i--) regmove_bb_head[i] = -1;
1084 regmove_bb_head[INSN_UID (bb->head)] = bb->index;
1086 /* A forward/backward pass. Replace output operands with input operands. */
1088 for (pass = 0; pass <= 2; pass++)
1090 if (! flag_regmove && pass >= flag_expensive_optimizations)
1093 if (regmove_dump_file)
1094 fprintf (regmove_dump_file, "Starting %s pass...\n",
1095 pass ? "backward" : "forward");
1097 for (insn = pass ? get_last_insn () : f; insn;
1098 insn = pass ? PREV_INSN (insn) : NEXT_INSN (insn))
1101 int op_no, match_no;
1103 set = single_set (insn);
1107 if (flag_expensive_optimizations && ! pass
1108 && (GET_CODE (SET_SRC (set)) == SIGN_EXTEND
1109 || GET_CODE (SET_SRC (set)) == ZERO_EXTEND)
1110 && GET_CODE (XEXP (SET_SRC (set), 0)) == REG
1111 && GET_CODE (SET_DEST (set)) == REG)
1112 optimize_reg_copy_3 (insn, SET_DEST (set), SET_SRC (set));
1114 if (flag_expensive_optimizations && ! pass
1115 && GET_CODE (SET_SRC (set)) == REG
1116 && GET_CODE (SET_DEST (set)) == REG)
1118 /* If this is a register-register copy where SRC is not dead,
1119 see if we can optimize it. If this optimization succeeds,
1120 it will become a copy where SRC is dead. */
1121 if ((find_reg_note (insn, REG_DEAD, SET_SRC (set))
1122 || optimize_reg_copy_1 (insn, SET_DEST (set), SET_SRC (set)))
1123 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
1125 /* Similarly for a pseudo-pseudo copy when SRC is dead. */
1126 if (REGNO (SET_SRC (set)) >= FIRST_PSEUDO_REGISTER)
1127 optimize_reg_copy_2 (insn, SET_DEST (set), SET_SRC (set));
1128 if (regno_src_regno[REGNO (SET_DEST (set))] < 0
1129 && SET_SRC (set) != SET_DEST (set))
1131 int srcregno = REGNO (SET_SRC (set));
1132 if (regno_src_regno[srcregno] >= 0)
1133 srcregno = regno_src_regno[srcregno];
1134 regno_src_regno[REGNO (SET_DEST (set))] = srcregno;
1141 if (! find_matches (insn, &match))
1144 /* Now scan through the operands looking for a source operand
1145 which is supposed to match the destination operand.
1146 Then scan forward for an instruction which uses the dest
1148 If it dies there, then replace the dest in both operands with
1149 the source operand. */
1151 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1153 rtx src, dst, src_subreg;
1154 enum reg_class src_class, dst_class;
1156 match_no = match.with[op_no];
1158 /* Nothing to do if the two operands aren't supposed to match. */
1162 src = recog_data.operand[op_no];
1163 dst = recog_data.operand[match_no];
1165 if (GET_CODE (src) != REG)
1169 if (GET_CODE (dst) == SUBREG
1170 && GET_MODE_SIZE (GET_MODE (dst))
1171 >= GET_MODE_SIZE (GET_MODE (SUBREG_REG (dst))))
1174 = gen_rtx_SUBREG (GET_MODE (SUBREG_REG (dst)),
1175 src, SUBREG_BYTE (dst));
1176 dst = SUBREG_REG (dst);
1178 if (GET_CODE (dst) != REG
1179 || REGNO (dst) < FIRST_PSEUDO_REGISTER)
1182 if (REGNO (src) < FIRST_PSEUDO_REGISTER)
1184 if (match.commutative[op_no] < op_no)
1185 regno_src_regno[REGNO (dst)] = REGNO (src);
1189 if (REG_LIVE_LENGTH (REGNO (src)) < 0)
1192 /* op_no/src must be a read-only operand, and
1193 match_operand/dst must be a write-only operand. */
1194 if (match.use[op_no] != READ
1195 || match.use[match_no] != WRITE)
1198 if (match.early_clobber[match_no]
1199 && count_occurrences (PATTERN (insn), src, 0) > 1)
1202 /* Make sure match_operand is the destination. */
1203 if (recog_data.operand[match_no] != SET_DEST (set))
1206 /* If the operands already match, then there is nothing to do. */
1207 if (operands_match_p (src, dst))
1210 /* But in the commutative case, we might find a better match. */
1211 if (match.commutative[op_no] >= 0)
1213 rtx comm = recog_data.operand[match.commutative[op_no]];
1214 if (operands_match_p (comm, dst)
1215 && (replacement_quality (comm)
1216 >= replacement_quality (src)))
1220 src_class = reg_preferred_class (REGNO (src));
1221 dst_class = reg_preferred_class (REGNO (dst));
1222 if (! regclass_compatible_p (src_class, dst_class))
1225 if (GET_MODE (src) != GET_MODE (dst))
1228 if (fixup_match_1 (insn, set, src, src_subreg, dst, pass,
1236 /* A backward pass. Replace input operands with output operands. */
1238 if (regmove_dump_file)
1239 fprintf (regmove_dump_file, "Starting backward pass...\n");
1241 for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
1245 int op_no, match_no;
1248 if (! find_matches (insn, &match))
1251 /* Now scan through the operands looking for a destination operand
1252 which is supposed to match a source operand.
1253 Then scan backward for an instruction which sets the source
1254 operand. If safe, then replace the source operand with the
1255 dest operand in both instructions. */
1257 copy_src = NULL_RTX;
1258 copy_dst = NULL_RTX;
1259 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1261 rtx set, p, src, dst;
1262 rtx src_note, dst_note;
1264 enum reg_class src_class, dst_class;
1267 match_no = match.with[op_no];
1269 /* Nothing to do if the two operands aren't supposed to match. */
1273 dst = recog_data.operand[match_no];
1274 src = recog_data.operand[op_no];
1276 if (GET_CODE (src) != REG)
1279 if (GET_CODE (dst) != REG
1280 || REGNO (dst) < FIRST_PSEUDO_REGISTER
1281 || REG_LIVE_LENGTH (REGNO (dst)) < 0
1282 || RTX_UNCHANGING_P (dst))
1285 /* If the operands already match, then there is nothing to do. */
1286 if (operands_match_p (src, dst))
1289 if (match.commutative[op_no] >= 0)
1291 rtx comm = recog_data.operand[match.commutative[op_no]];
1292 if (operands_match_p (comm, dst))
1296 set = single_set (insn);
1300 /* Note that single_set ignores parts of a parallel set for
1301 which one of the destinations is REG_UNUSED. We can't
1302 handle that here, since we can wind up rewriting things
1303 such that a single register is set twice within a single
1305 if (reg_set_p (src, insn))
1308 /* match_no/dst must be a write-only operand, and
1309 operand_operand/src must be a read-only operand. */
1310 if (match.use[op_no] != READ
1311 || match.use[match_no] != WRITE)
1314 if (match.early_clobber[match_no]
1315 && count_occurrences (PATTERN (insn), src, 0) > 1)
1318 /* Make sure match_no is the destination. */
1319 if (recog_data.operand[match_no] != SET_DEST (set))
1322 if (REGNO (src) < FIRST_PSEUDO_REGISTER)
1324 if (GET_CODE (SET_SRC (set)) == PLUS
1325 && GET_CODE (XEXP (SET_SRC (set), 1)) == CONST_INT
1326 && XEXP (SET_SRC (set), 0) == src
1327 && fixup_match_2 (insn, dst, src,
1328 XEXP (SET_SRC (set), 1),
1333 src_class = reg_preferred_class (REGNO (src));
1334 dst_class = reg_preferred_class (REGNO (dst));
1336 if (! (src_note = find_reg_note (insn, REG_DEAD, src)))
1338 /* We used to force the copy here like in other cases, but
1339 it produces worse code, as it eliminates no copy
1340 instructions and the copy emitted will be produced by
1341 reload anyway. On patterns with multiple alternatives,
1342 there may be better solution available.
1344 In particular this change produced slower code for numeric
1350 if (! regclass_compatible_p (src_class, dst_class))
1360 /* Can not modify an earlier insn to set dst if this insn
1361 uses an old value in the source. */
1362 if (reg_overlap_mentioned_p (dst, SET_SRC (set)))
1372 /* If src is set once in a different basic block,
1373 and is set equal to a constant, then do not use
1374 it for this optimization, as this would make it
1375 no longer equivalent to a constant. */
1377 if (reg_is_remote_constant_p (src, insn, f))
1388 if (regmove_dump_file)
1389 fprintf (regmove_dump_file,
1390 "Could fix operand %d of insn %d matching operand %d.\n",
1391 op_no, INSN_UID (insn), match_no);
1393 /* Scan backward to find the first instruction that uses
1394 the input operand. If the operand is set here, then
1395 replace it in both instructions with match_no. */
1397 for (length = 0, p = PREV_INSN (insn); p; p = PREV_INSN (p))
1401 /* ??? We can't scan past the end of a basic block without
1402 updating the register lifetime info
1403 (REG_DEAD/basic_block_live_at_start). */
1404 if (perhaps_ends_bb_p (p))
1406 else if (! INSN_P (p))
1411 /* ??? See if all of SRC is set in P. This test is much
1412 more conservative than it needs to be. */
1413 pset = single_set (p);
1414 if (pset && SET_DEST (pset) == src)
1416 /* We use validate_replace_rtx, in case there
1417 are multiple identical source operands. All of
1418 them have to be changed at the same time. */
1419 if (validate_replace_rtx (src, dst, insn))
1421 if (validate_change (p, &SET_DEST (pset),
1426 /* Change all source operands back.
1427 This modifies the dst as a side-effect. */
1428 validate_replace_rtx (dst, src, insn);
1429 /* Now make sure the dst is right. */
1430 validate_change (insn,
1431 recog_data.operand_loc[match_no],
1438 if (reg_overlap_mentioned_p (src, PATTERN (p))
1439 || reg_overlap_mentioned_p (dst, PATTERN (p)))
1442 /* If we have passed a call instruction, and the
1443 pseudo-reg DST is not already live across a call,
1444 then don't perform the optimization. */
1445 if (GET_CODE (p) == CALL_INSN)
1449 if (REG_N_CALLS_CROSSED (REGNO (dst)) == 0)
1458 /* Remove the death note for SRC from INSN. */
1459 remove_note (insn, src_note);
1460 /* Move the death note for SRC to P if it is used
1462 if (reg_overlap_mentioned_p (src, PATTERN (p)))
1464 XEXP (src_note, 1) = REG_NOTES (p);
1465 REG_NOTES (p) = src_note;
1467 /* If there is a REG_DEAD note for DST on P, then remove
1468 it, because DST is now set there. */
1469 if ((dst_note = find_reg_note (p, REG_DEAD, dst)))
1470 remove_note (p, dst_note);
1472 dstno = REGNO (dst);
1473 srcno = REGNO (src);
1475 REG_N_SETS (dstno)++;
1476 REG_N_SETS (srcno)--;
1478 REG_N_CALLS_CROSSED (dstno) += num_calls;
1479 REG_N_CALLS_CROSSED (srcno) -= num_calls;
1481 REG_LIVE_LENGTH (dstno) += length;
1482 if (REG_LIVE_LENGTH (srcno) >= 0)
1484 REG_LIVE_LENGTH (srcno) -= length;
1485 /* REG_LIVE_LENGTH is only an approximation after
1486 combine if sched is not run, so make sure that we
1487 still have a reasonable value. */
1488 if (REG_LIVE_LENGTH (srcno) < 2)
1489 REG_LIVE_LENGTH (srcno) = 2;
1492 if (regmove_dump_file)
1493 fprintf (regmove_dump_file,
1494 "Fixed operand %d of insn %d matching operand %d.\n",
1495 op_no, INSN_UID (insn), match_no);
1501 /* If we weren't able to replace any of the alternatives, try an
1502 alternative approach of copying the source to the destination. */
1503 if (!success && copy_src != NULL_RTX)
1504 copy_src_to_dest (insn, copy_src, copy_dst, old_max_uid);
1509 /* In fixup_match_1, some insns may have been inserted after basic block
1510 ends. Fix that here. */
1515 rtx next = NEXT_INSN (new);
1516 while (next != 0 && INSN_UID (next) >= old_max_uid
1517 && (bb->next_bb == EXIT_BLOCK_PTR || bb->next_bb->head != next))
1518 new = next, next = NEXT_INSN (new);
1524 free (regno_src_regno);
1525 free (regmove_bb_head);
1528 /* Returns nonzero if INSN's pattern has matching constraints for any operand.
1529 Returns 0 if INSN can't be recognized, or if the alternative can't be
1532 Initialize the info in MATCHP based on the constraints. */
1535 find_matches (insn, matchp)
1537 struct match *matchp;
1539 int likely_spilled[MAX_RECOG_OPERANDS];
1541 int any_matches = 0;
1543 extract_insn (insn);
1544 if (! constrain_operands (0))
1547 /* Must initialize this before main loop, because the code for
1548 the commutative case may set matches for operands other than
1550 for (op_no = recog_data.n_operands; --op_no >= 0; )
1551 matchp->with[op_no] = matchp->commutative[op_no] = -1;
1553 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1559 p = recog_data.constraints[op_no];
1561 likely_spilled[op_no] = 0;
1562 matchp->use[op_no] = READ;
1563 matchp->early_clobber[op_no] = 0;
1565 matchp->use[op_no] = WRITE;
1567 matchp->use[op_no] = READWRITE;
1569 for (;*p && i < which_alternative; p++)
1573 while ((c = *p) != '\0' && c != ',')
1582 matchp->early_clobber[op_no] = 1;
1585 matchp->commutative[op_no] = op_no + 1;
1586 matchp->commutative[op_no + 1] = op_no;
1589 case '0': case '1': case '2': case '3': case '4':
1590 case '5': case '6': case '7': case '8': case '9':
1593 unsigned long match_ul = strtoul (p, &end, 10);
1594 int match = match_ul;
1598 if (match < op_no && likely_spilled[match])
1600 matchp->with[op_no] = match;
1602 if (matchp->commutative[op_no] >= 0)
1603 matchp->with[matchp->commutative[op_no]] = match;
1607 case 'a': case 'b': case 'c': case 'd': case 'e': case 'f': case 'h':
1608 case 'j': case 'k': case 'l': case 'p': case 'q': case 't': case 'u':
1609 case 'v': case 'w': case 'x': case 'y': case 'z': case 'A': case 'B':
1610 case 'C': case 'D': case 'W': case 'Y': case 'Z':
1611 if (CLASS_LIKELY_SPILLED_P (REG_CLASS_FROM_CONSTRAINT ((unsigned char) c, p) ))
1612 likely_spilled[op_no] = 1;
1615 p += CONSTRAINT_LEN (c, p);
1621 /* Try to replace all occurrences of DST_REG with SRC in LOC, that is
1622 assumed to be in INSN. */
1625 replace_in_call_usage (loc, dst_reg, src, insn)
1627 unsigned int dst_reg;
1639 code = GET_CODE (x);
1642 if (REGNO (x) != dst_reg)
1645 validate_change (insn, loc, src, 1);
1650 /* Process each of our operands recursively. */
1651 fmt = GET_RTX_FORMAT (code);
1652 for (i = 0; i < GET_RTX_LENGTH (code); i++, fmt++)
1654 replace_in_call_usage (&XEXP (x, i), dst_reg, src, insn);
1655 else if (*fmt == 'E')
1656 for (j = 0; j < XVECLEN (x, i); j++)
1657 replace_in_call_usage (& XVECEXP (x, i, j), dst_reg, src, insn);
1660 /* Try to replace output operand DST in SET, with input operand SRC. SET is
1661 the only set in INSN. INSN has just been recognized and constrained.
1662 SRC is operand number OPERAND_NUMBER in INSN.
1663 DST is operand number MATCH_NUMBER in INSN.
1664 If BACKWARD is nonzero, we have been called in a backward pass.
1665 Return nonzero for success. */
1668 fixup_match_1 (insn, set, src, src_subreg, dst, backward, operand_number,
1669 match_number, regmove_dump_file)
1670 rtx insn, set, src, src_subreg, dst;
1671 int backward, operand_number, match_number;
1672 FILE *regmove_dump_file;
1675 rtx post_inc = 0, post_inc_set = 0, search_end = 0;
1677 int num_calls = 0, s_num_calls = 0;
1678 enum rtx_code code = NOTE;
1679 HOST_WIDE_INT insn_const = 0, newconst;
1680 rtx overlap = 0; /* need to move insn ? */
1681 rtx src_note = find_reg_note (insn, REG_DEAD, src), dst_note = NULL_RTX;
1682 int length, s_length;
1684 /* If SRC is marked as unchanging, we may not change it.
1685 ??? Maybe we could get better code by removing the unchanging bit
1686 instead, and changing it back if we don't succeed? */
1687 if (RTX_UNCHANGING_P (src))
1692 /* Look for (set (regX) (op regA constX))
1693 (set (regY) (op regA constY))
1695 (set (regA) (op regA constX)).
1696 (set (regY) (op regA constY-constX)).
1697 This works for add and shift operations, if
1698 regA is dead after or set by the second insn. */
1700 code = GET_CODE (SET_SRC (set));
1701 if ((code == PLUS || code == LSHIFTRT
1702 || code == ASHIFT || code == ASHIFTRT)
1703 && XEXP (SET_SRC (set), 0) == src
1704 && GET_CODE (XEXP (SET_SRC (set), 1)) == CONST_INT)
1705 insn_const = INTVAL (XEXP (SET_SRC (set), 1));
1706 else if (! stable_and_no_regs_but_for_p (SET_SRC (set), src, dst))
1709 /* We might find a src_note while scanning. */
1713 if (regmove_dump_file)
1714 fprintf (regmove_dump_file,
1715 "Could fix operand %d of insn %d matching operand %d.\n",
1716 operand_number, INSN_UID (insn), match_number);
1718 /* If SRC is equivalent to a constant set in a different basic block,
1719 then do not use it for this optimization. We want the equivalence
1720 so that if we have to reload this register, we can reload the
1721 constant, rather than extending the lifespan of the register. */
1722 if (reg_is_remote_constant_p (src, insn, get_insns ()))
1725 /* Scan forward to find the next instruction that
1726 uses the output operand. If the operand dies here,
1727 then replace it in both instructions with
1730 for (length = s_length = 0, p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
1732 if (GET_CODE (p) == CALL_INSN)
1733 replace_in_call_usage (& CALL_INSN_FUNCTION_USAGE (p),
1734 REGNO (dst), src, p);
1736 /* ??? We can't scan past the end of a basic block without updating
1737 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
1738 if (perhaps_ends_bb_p (p))
1740 else if (! INSN_P (p))
1747 if (reg_set_p (src, p) || reg_set_p (dst, p)
1748 || (GET_CODE (PATTERN (p)) == USE
1749 && reg_overlap_mentioned_p (src, XEXP (PATTERN (p), 0))))
1752 /* See if all of DST dies in P. This test is
1753 slightly more conservative than it needs to be. */
1754 if ((dst_note = find_regno_note (p, REG_DEAD, REGNO (dst)))
1755 && (GET_MODE (XEXP (dst_note, 0)) == GET_MODE (dst)))
1757 /* If we would be moving INSN, check that we won't move it
1758 into the shadow of a live a live flags register. */
1759 /* ??? We only try to move it in front of P, although
1760 we could move it anywhere between OVERLAP and P. */
1761 if (overlap && GET_MODE (PREV_INSN (p)) != VOIDmode)
1767 rtx set2 = NULL_RTX;
1769 /* If an optimization is done, the value of SRC while P
1770 is executed will be changed. Check that this is OK. */
1771 if (reg_overlap_mentioned_p (src, PATTERN (p)))
1773 for (q = p; q; q = NEXT_INSN (q))
1775 /* ??? We can't scan past the end of a basic block without
1776 updating the register lifetime info
1777 (REG_DEAD/basic_block_live_at_start). */
1778 if (perhaps_ends_bb_p (q))
1783 else if (! INSN_P (q))
1785 else if (reg_overlap_mentioned_p (src, PATTERN (q))
1786 || reg_set_p (src, q))
1790 set2 = single_set (q);
1791 if (! q || ! set2 || GET_CODE (SET_SRC (set2)) != code
1792 || XEXP (SET_SRC (set2), 0) != src
1793 || GET_CODE (XEXP (SET_SRC (set2), 1)) != CONST_INT
1794 || (SET_DEST (set2) != src
1795 && ! find_reg_note (q, REG_DEAD, src)))
1797 /* If this is a PLUS, we can still save a register by doing
1800 src -= insn_const; .
1801 This also gives opportunities for subsequent
1802 optimizations in the backward pass, so do it there. */
1803 if (code == PLUS && backward
1804 /* Don't do this if we can likely tie DST to SET_DEST
1805 of P later; we can't do this tying here if we got a
1807 && ! (dst_note && ! REG_N_CALLS_CROSSED (REGNO (dst))
1809 && GET_CODE (SET_DEST (single_set (p))) == REG
1810 && (REGNO (SET_DEST (single_set (p)))
1811 < FIRST_PSEUDO_REGISTER))
1812 /* We may only emit an insn directly after P if we
1813 are not in the shadow of a live flags register. */
1814 && GET_MODE (p) == VOIDmode)
1819 newconst = -insn_const;
1827 newconst = INTVAL (XEXP (SET_SRC (set2), 1)) - insn_const;
1828 /* Reject out of range shifts. */
1831 || ((unsigned HOST_WIDE_INT) newconst
1832 >= (GET_MODE_BITSIZE (GET_MODE
1833 (SET_SRC (set2)))))))
1838 if (SET_DEST (set2) != src)
1839 post_inc_set = set2;
1842 /* We use 1 as last argument to validate_change so that all
1843 changes are accepted or rejected together by apply_change_group
1844 when it is called by validate_replace_rtx . */
1845 validate_change (q, &XEXP (SET_SRC (set2), 1),
1846 GEN_INT (newconst), 1);
1848 validate_change (insn, recog_data.operand_loc[match_number], src, 1);
1849 if (validate_replace_rtx (dst, src_subreg, p))
1854 if (reg_overlap_mentioned_p (dst, PATTERN (p)))
1856 if (! src_note && reg_overlap_mentioned_p (src, PATTERN (p)))
1858 /* INSN was already checked to be movable wrt. the registers that it
1859 sets / uses when we found no REG_DEAD note for src on it, but it
1860 still might clobber the flags register. We'll have to check that
1861 we won't insert it into the shadow of a live flags register when
1862 we finally know where we are to move it. */
1864 src_note = find_reg_note (p, REG_DEAD, src);
1867 /* If we have passed a call instruction, and the pseudo-reg SRC is not
1868 already live across a call, then don't perform the optimization. */
1869 if (GET_CODE (p) == CALL_INSN)
1871 if (REG_N_CALLS_CROSSED (REGNO (src)) == 0)
1885 /* Remove the death note for DST from P. */
1886 remove_note (p, dst_note);
1889 post_inc = emit_insn_after (copy_rtx (PATTERN (insn)), p);
1890 if ((HAVE_PRE_INCREMENT || HAVE_PRE_DECREMENT)
1892 && try_auto_increment (search_end, post_inc, 0, src, newconst, 1))
1894 validate_change (insn, &XEXP (SET_SRC (set), 1), GEN_INT (insn_const), 0);
1895 REG_N_SETS (REGNO (src))++;
1896 REG_LIVE_LENGTH (REGNO (src))++;
1900 /* The lifetime of src and dest overlap,
1901 but we can change this by moving insn. */
1902 rtx pat = PATTERN (insn);
1904 remove_note (overlap, src_note);
1905 if ((HAVE_POST_INCREMENT || HAVE_POST_DECREMENT)
1907 && try_auto_increment (overlap, insn, 0, src, insn_const, 0))
1911 rtx notes = REG_NOTES (insn);
1913 emit_insn_after_with_line_notes (pat, PREV_INSN (p), insn);
1915 /* emit_insn_after_with_line_notes has no
1916 return value, so search for the new insn. */
1918 while (! INSN_P (insn) || PATTERN (insn) != pat)
1919 insn = PREV_INSN (insn);
1921 REG_NOTES (insn) = notes;
1924 /* Sometimes we'd generate src = const; src += n;
1925 if so, replace the instruction that set src
1926 in the first place. */
1928 if (! overlap && (code == PLUS || code == MINUS))
1930 rtx note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
1931 rtx q, set2 = NULL_RTX;
1932 int num_calls2 = 0, s_length2 = 0;
1934 if (note && CONSTANT_P (XEXP (note, 0)))
1936 for (q = PREV_INSN (insn); q; q = PREV_INSN (q))
1938 /* ??? We can't scan past the end of a basic block without
1939 updating the register lifetime info
1940 (REG_DEAD/basic_block_live_at_start). */
1941 if (perhaps_ends_bb_p (q))
1946 else if (! INSN_P (q))
1950 if (reg_set_p (src, q))
1952 set2 = single_set (q);
1955 if (reg_overlap_mentioned_p (src, PATTERN (q)))
1960 if (GET_CODE (p) == CALL_INSN)
1963 if (q && set2 && SET_DEST (set2) == src && CONSTANT_P (SET_SRC (set2))
1964 && validate_change (insn, &SET_SRC (set), XEXP (note, 0), 0))
1967 REG_N_SETS (REGNO (src))--;
1968 REG_N_CALLS_CROSSED (REGNO (src)) -= num_calls2;
1969 REG_LIVE_LENGTH (REGNO (src)) -= s_length2;
1975 if ((HAVE_PRE_INCREMENT || HAVE_PRE_DECREMENT)
1976 && (code == PLUS || code == MINUS) && insn_const
1977 && try_auto_increment (p, insn, 0, src, insn_const, 1))
1979 else if ((HAVE_POST_INCREMENT || HAVE_POST_DECREMENT)
1981 && try_auto_increment (p, post_inc, post_inc_set, src, newconst, 0))
1983 /* If post_inc still prevails, try to find an
1984 insn where it can be used as a pre-in/decrement.
1985 If code is MINUS, this was already tried. */
1986 if (post_inc && code == PLUS
1987 /* Check that newconst is likely to be usable
1988 in a pre-in/decrement before starting the search. */
1989 && ((HAVE_PRE_INCREMENT && newconst > 0 && newconst <= MOVE_MAX)
1990 || (HAVE_PRE_DECREMENT && newconst < 0 && newconst >= -MOVE_MAX))
1991 && exact_log2 (newconst))
1995 inc_dest = post_inc_set ? SET_DEST (post_inc_set) : src;
1996 for (q = post_inc; (q = NEXT_INSN (q)); )
1998 /* ??? We can't scan past the end of a basic block without updating
1999 the register lifetime info
2000 (REG_DEAD/basic_block_live_at_start). */
2001 if (perhaps_ends_bb_p (q))
2003 else if (! INSN_P (q))
2005 else if (src != inc_dest
2006 && (reg_overlap_mentioned_p (src, PATTERN (q))
2007 || reg_set_p (src, q)))
2009 else if (reg_set_p (inc_dest, q))
2011 else if (reg_overlap_mentioned_p (inc_dest, PATTERN (q)))
2013 try_auto_increment (q, post_inc,
2014 post_inc_set, inc_dest, newconst, 1);
2020 /* Move the death note for DST to INSN if it is used
2022 if (reg_overlap_mentioned_p (dst, PATTERN (insn)))
2024 XEXP (dst_note, 1) = REG_NOTES (insn);
2025 REG_NOTES (insn) = dst_note;
2030 /* Move the death note for SRC from INSN to P. */
2032 remove_note (insn, src_note);
2033 XEXP (src_note, 1) = REG_NOTES (p);
2034 REG_NOTES (p) = src_note;
2036 REG_N_CALLS_CROSSED (REGNO (src)) += s_num_calls;
2039 REG_N_SETS (REGNO (src))++;
2040 REG_N_SETS (REGNO (dst))--;
2042 REG_N_CALLS_CROSSED (REGNO (dst)) -= num_calls;
2044 REG_LIVE_LENGTH (REGNO (src)) += s_length;
2045 if (REG_LIVE_LENGTH (REGNO (dst)) >= 0)
2047 REG_LIVE_LENGTH (REGNO (dst)) -= length;
2048 /* REG_LIVE_LENGTH is only an approximation after
2049 combine if sched is not run, so make sure that we
2050 still have a reasonable value. */
2051 if (REG_LIVE_LENGTH (REGNO (dst)) < 2)
2052 REG_LIVE_LENGTH (REGNO (dst)) = 2;
2054 if (regmove_dump_file)
2055 fprintf (regmove_dump_file,
2056 "Fixed operand %d of insn %d matching operand %d.\n",
2057 operand_number, INSN_UID (insn), match_number);
2062 /* return nonzero if X is stable and mentions no regsiters but for
2063 mentioning SRC or mentioning / changing DST . If in doubt, presume
2065 The rationale is that we want to check if we can move an insn easily
2066 while just paying attention to SRC and DST. A register is considered
2067 stable if it has the RTX_UNCHANGING_P bit set, but that would still
2068 leave the burden to update REG_DEAD / REG_UNUSED notes, so we don't
2069 want any registers but SRC and DST. */
2071 stable_and_no_regs_but_for_p (x, src, dst)
2074 RTX_CODE code = GET_CODE (x);
2075 switch (GET_RTX_CLASS (code))
2077 case '<': case '1': case 'c': case '2': case 'b': case '3':
2080 const char *fmt = GET_RTX_FORMAT (code);
2081 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2083 && ! stable_and_no_regs_but_for_p (XEXP (x, i), src, dst))
2089 return x == src || x == dst;
2090 /* If this is a MEM, look inside - there might be a register hidden in
2091 the address of an unchanging MEM. */
2093 && ! stable_and_no_regs_but_for_p (XEXP (x, 0), src, dst))
2097 return ! rtx_unstable_p (x);
2101 /* Track stack adjustments and stack memory references. Attempt to
2102 reduce the number of stack adjustments by back-propagating across
2103 the memory references.
2105 This is intended primarily for use with targets that do not define
2106 ACCUMULATE_OUTGOING_ARGS. It is of significantly more value to
2107 targets that define PREFERRED_STACK_BOUNDARY more aligned than
2108 STACK_BOUNDARY (e.g. x86), or if not all registers can be pushed
2109 (e.g. x86 fp regs) which would ordinarily have to be implemented
2110 as a sub/mov pair due to restrictions in calls.c.
2112 Propagation stops when any of the insns that need adjusting are
2113 (a) no longer valid because we've exceeded their range, (b) a
2114 non-trivial push instruction, or (c) a call instruction.
2116 Restriction B is based on the assumption that push instructions
2117 are smaller or faster. If a port really wants to remove all
2118 pushes, it should have defined ACCUMULATE_OUTGOING_ARGS. The
2119 one exception that is made is for an add immediately followed
2122 /* This structure records stack memory references between stack adjusting
2127 HOST_WIDE_INT sp_offset;
2129 struct csa_memlist *next;
2132 static int stack_memref_p PARAMS ((rtx));
2133 static rtx single_set_for_csa PARAMS ((rtx));
2134 static void free_csa_memlist PARAMS ((struct csa_memlist *));
2135 static struct csa_memlist *record_one_stack_memref
2136 PARAMS ((rtx, rtx *, struct csa_memlist *));
2137 static int try_apply_stack_adjustment
2138 PARAMS ((rtx, struct csa_memlist *, HOST_WIDE_INT, HOST_WIDE_INT));
2139 static void combine_stack_adjustments_for_block PARAMS ((basic_block));
2140 static int record_stack_memrefs PARAMS ((rtx *, void *));
2143 /* Main entry point for stack adjustment combination. */
2146 combine_stack_adjustments ()
2151 combine_stack_adjustments_for_block (bb);
2154 /* Recognize a MEM of the form (sp) or (plus sp const). */
2160 if (GET_CODE (x) != MEM)
2164 if (x == stack_pointer_rtx)
2166 if (GET_CODE (x) == PLUS
2167 && XEXP (x, 0) == stack_pointer_rtx
2168 && GET_CODE (XEXP (x, 1)) == CONST_INT)
2174 /* Recognize either normal single_set or the hack in i386.md for
2175 tying fp and sp adjustments. */
2178 single_set_for_csa (insn)
2182 rtx tmp = single_set (insn);
2186 if (GET_CODE (insn) != INSN
2187 || GET_CODE (PATTERN (insn)) != PARALLEL)
2190 tmp = PATTERN (insn);
2191 if (GET_CODE (XVECEXP (tmp, 0, 0)) != SET)
2194 for (i = 1; i < XVECLEN (tmp, 0); ++i)
2196 rtx this = XVECEXP (tmp, 0, i);
2198 /* The special case is allowing a no-op set. */
2199 if (GET_CODE (this) == SET
2200 && SET_SRC (this) == SET_DEST (this))
2202 else if (GET_CODE (this) != CLOBBER
2203 && GET_CODE (this) != USE)
2207 return XVECEXP (tmp, 0, 0);
2210 /* Free the list of csa_memlist nodes. */
2213 free_csa_memlist (memlist)
2214 struct csa_memlist *memlist;
2216 struct csa_memlist *next;
2217 for (; memlist ; memlist = next)
2219 next = memlist->next;
2224 /* Create a new csa_memlist node from the given memory reference.
2225 It is already known that the memory is stack_memref_p. */
2227 static struct csa_memlist *
2228 record_one_stack_memref (insn, mem, next_memlist)
2230 struct csa_memlist *next_memlist;
2232 struct csa_memlist *ml;
2234 ml = (struct csa_memlist *) xmalloc (sizeof (*ml));
2236 if (XEXP (*mem, 0) == stack_pointer_rtx)
2239 ml->sp_offset = INTVAL (XEXP (XEXP (*mem, 0), 1));
2243 ml->next = next_memlist;
2248 /* Attempt to apply ADJUST to the stack adjusting insn INSN, as well
2249 as each of the memories in MEMLIST. Return true on success. */
2252 try_apply_stack_adjustment (insn, memlist, new_adjust, delta)
2254 struct csa_memlist *memlist;
2255 HOST_WIDE_INT new_adjust, delta;
2257 struct csa_memlist *ml;
2260 set = single_set_for_csa (insn);
2261 validate_change (insn, &XEXP (SET_SRC (set), 1), GEN_INT (new_adjust), 1);
2263 for (ml = memlist; ml ; ml = ml->next)
2266 replace_equiv_address_nv (*ml->mem,
2267 plus_constant (stack_pointer_rtx,
2268 ml->sp_offset - delta)), 1);
2270 if (apply_change_group ())
2272 /* Succeeded. Update our knowledge of the memory references. */
2273 for (ml = memlist; ml ; ml = ml->next)
2274 ml->sp_offset -= delta;
2282 /* Called via for_each_rtx and used to record all stack memory references in
2283 the insn and discard all other stack pointer references. */
2284 struct record_stack_memrefs_data
2287 struct csa_memlist *memlist;
2291 record_stack_memrefs (xp, data)
2296 struct record_stack_memrefs_data *d =
2297 (struct record_stack_memrefs_data *) data;
2300 switch (GET_CODE (x))
2303 if (!reg_mentioned_p (stack_pointer_rtx, x))
2305 /* We are not able to handle correctly all possible memrefs containing
2306 stack pointer, so this check is necessary. */
2307 if (stack_memref_p (x))
2309 d->memlist = record_one_stack_memref (d->insn, xp, d->memlist);
2314 /* ??? We want be able to handle non-memory stack pointer
2315 references later. For now just discard all insns refering to
2316 stack pointer outside mem expressions. We would probably
2317 want to teach validate_replace to simplify expressions first.
2319 We can't just compare with STACK_POINTER_RTX because the
2320 reference to the stack pointer might be in some other mode.
2321 In particular, an explicit clobber in an asm statement will
2322 result in a QImode clober. */
2323 if (REGNO (x) == STACK_POINTER_REGNUM)
2332 /* Subroutine of combine_stack_adjustments, called for each basic block. */
2335 combine_stack_adjustments_for_block (bb)
2338 HOST_WIDE_INT last_sp_adjust = 0;
2339 rtx last_sp_set = NULL_RTX;
2340 struct csa_memlist *memlist = NULL;
2341 rtx insn, next, set;
2342 struct record_stack_memrefs_data data;
2343 bool end_of_block = false;
2345 for (insn = bb->head; !end_of_block ; insn = next)
2347 end_of_block = insn == bb->end;
2348 next = NEXT_INSN (insn);
2350 if (! INSN_P (insn))
2353 set = single_set_for_csa (insn);
2356 rtx dest = SET_DEST (set);
2357 rtx src = SET_SRC (set);
2359 /* Find constant additions to the stack pointer. */
2360 if (dest == stack_pointer_rtx
2361 && GET_CODE (src) == PLUS
2362 && XEXP (src, 0) == stack_pointer_rtx
2363 && GET_CODE (XEXP (src, 1)) == CONST_INT)
2365 HOST_WIDE_INT this_adjust = INTVAL (XEXP (src, 1));
2367 /* If we've not seen an adjustment previously, record
2368 it now and continue. */
2372 last_sp_adjust = this_adjust;
2376 /* If not all recorded memrefs can be adjusted, or the
2377 adjustment is now too large for a constant addition,
2378 we cannot merge the two stack adjustments.
2380 Also we need to be careful to not move stack pointer
2381 such that we create stack accesses outside the allocated
2382 area. We can combine an allocation into the first insn,
2383 or a deallocation into the second insn. We can not
2384 combine an allocation followed by a deallocation.
2386 The only somewhat frequent occurrence of the later is when
2387 a function allocates a stack frame but does not use it.
2388 For this case, we would need to analyze rtl stream to be
2389 sure that allocated area is really unused. This means not
2390 only checking the memory references, but also all registers
2391 or global memory references possibly containing a stack
2394 Perhaps the best way to address this problem is to teach
2395 gcc not to allocate stack for objects never used. */
2397 /* Combine an allocation into the first instruction. */
2398 if (STACK_GROWS_DOWNWARD ? this_adjust <= 0 : this_adjust >= 0)
2400 if (try_apply_stack_adjustment (last_sp_set, memlist,
2401 last_sp_adjust + this_adjust,
2406 last_sp_adjust += this_adjust;
2411 /* Otherwise we have a deallocation. Do not combine with
2412 a previous allocation. Combine into the second insn. */
2413 else if (STACK_GROWS_DOWNWARD
2414 ? last_sp_adjust >= 0 : last_sp_adjust <= 0)
2416 if (try_apply_stack_adjustment (insn, memlist,
2417 last_sp_adjust + this_adjust,
2421 delete_insn (last_sp_set);
2423 last_sp_adjust += this_adjust;
2424 free_csa_memlist (memlist);
2430 /* Combination failed. Restart processing from here. If
2431 deallocation+allocation conspired to cancel, we can
2432 delete the old deallocation insn. */
2433 if (last_sp_set && last_sp_adjust == 0)
2435 free_csa_memlist (memlist);
2438 last_sp_adjust = this_adjust;
2442 /* Find a predecrement of exactly the previous adjustment and
2443 turn it into a direct store. Obviously we can't do this if
2444 there were any intervening uses of the stack pointer. */
2446 && GET_CODE (dest) == MEM
2447 && ((GET_CODE (XEXP (dest, 0)) == PRE_DEC
2449 == (HOST_WIDE_INT) GET_MODE_SIZE (GET_MODE (dest))))
2450 || (GET_CODE (XEXP (dest, 0)) == PRE_MODIFY
2451 && GET_CODE (XEXP (XEXP (dest, 0), 1)) == PLUS
2452 && XEXP (XEXP (XEXP (dest, 0), 1), 0) == stack_pointer_rtx
2453 && (GET_CODE (XEXP (XEXP (XEXP (dest, 0), 1), 1))
2455 && (INTVAL (XEXP (XEXP (XEXP (dest, 0), 1), 1))
2456 == -last_sp_adjust)))
2457 && XEXP (XEXP (dest, 0), 0) == stack_pointer_rtx
2458 && ! reg_mentioned_p (stack_pointer_rtx, src)
2459 && memory_address_p (GET_MODE (dest), stack_pointer_rtx)
2460 && validate_change (insn, &SET_DEST (set),
2461 replace_equiv_address (dest,
2465 delete_insn (last_sp_set);
2466 free_csa_memlist (memlist);
2468 last_sp_set = NULL_RTX;
2475 data.memlist = memlist;
2476 if (GET_CODE (insn) != CALL_INSN && last_sp_set
2477 && !for_each_rtx (&PATTERN (insn), record_stack_memrefs, &data))
2479 memlist = data.memlist;
2482 memlist = data.memlist;
2484 /* Otherwise, we were not able to process the instruction.
2485 Do not continue collecting data across such a one. */
2487 && (GET_CODE (insn) == CALL_INSN
2488 || reg_mentioned_p (stack_pointer_rtx, PATTERN (insn))))
2490 if (last_sp_set && last_sp_adjust == 0)
2491 delete_insn (last_sp_set);
2492 free_csa_memlist (memlist);
2494 last_sp_set = NULL_RTX;
2499 if (last_sp_set && last_sp_adjust == 0)
2500 delete_insn (last_sp_set);
OSDN Git Service
