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 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 "insn-flags.h"
41 #include "basic-block.h"
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 int fixup_match_1 PARAMS ((rtx, rtx, rtx, rtx, rtx, int, int, int, FILE *))
66 static int reg_is_remote_constant_p PARAMS ((rtx, rtx, rtx));
67 static int stable_and_no_regs_but_for_p PARAMS ((rtx, rtx, rtx));
68 static int regclass_compatible_p PARAMS ((int, int));
69 static int replacement_quality PARAMS ((rtx));
70 static int fixup_match_2 PARAMS ((rtx, rtx, rtx, rtx, FILE *));
72 /* Return non-zero if registers with CLASS1 and CLASS2 can be merged without
73 causing too much register allocation problems. */
75 regclass_compatible_p (class0, class1)
78 return (class0 == class1
79 || (reg_class_subset_p (class0, class1)
80 && ! CLASS_LIKELY_SPILLED_P (class0))
81 || (reg_class_subset_p (class1, class0)
82 && ! CLASS_LIKELY_SPILLED_P (class1)));
85 /* Generate and return an insn body to add r1 and c,
86 storing the result in r0. */
88 gen_add3_insn (r0, r1, c)
91 int icode = (int) add_optab->handlers[(int) GET_MODE (r0)].insn_code;
93 if (icode == CODE_FOR_nothing
94 || ! ((*insn_data[icode].operand[0].predicate)
95 (r0, insn_data[icode].operand[0].mode))
96 || ! ((*insn_data[icode].operand[1].predicate)
97 (r1, insn_data[icode].operand[1].mode))
98 || ! ((*insn_data[icode].operand[2].predicate)
99 (c, insn_data[icode].operand[2].mode)))
102 return (GEN_FCN (icode) (r0, r1, c));
106 /* INC_INSN is an instruction that adds INCREMENT to REG.
107 Try to fold INC_INSN as a post/pre in/decrement into INSN.
108 Iff INC_INSN_SET is nonzero, inc_insn has a destination different from src.
109 Return nonzero for success. */
111 try_auto_increment (insn, inc_insn, inc_insn_set, reg, increment, pre)
112 rtx reg, insn, inc_insn ,inc_insn_set;
113 HOST_WIDE_INT increment;
116 enum rtx_code inc_code;
118 rtx pset = single_set (insn);
121 /* Can't use the size of SET_SRC, we might have something like
122 (sign_extend:SI (mem:QI ... */
123 rtx use = find_use_as_address (pset, reg, 0);
124 if (use != 0 && use != (rtx) 1)
126 int size = GET_MODE_SIZE (GET_MODE (use));
128 || (HAVE_POST_INCREMENT
129 && pre == 0 && (inc_code = POST_INC, increment == size))
130 || (HAVE_PRE_INCREMENT
131 && pre == 1 && (inc_code = PRE_INC, increment == size))
132 || (HAVE_POST_DECREMENT
133 && pre == 0 && (inc_code = POST_DEC, increment == -size))
134 || (HAVE_PRE_DECREMENT
135 && pre == 1 && (inc_code = PRE_DEC, increment == -size))
141 &SET_SRC (inc_insn_set),
142 XEXP (SET_SRC (inc_insn_set), 0), 1);
143 validate_change (insn, &XEXP (use, 0),
144 gen_rtx_fmt_e (inc_code, Pmode, reg), 1);
145 if (apply_change_group ())
148 = gen_rtx_EXPR_LIST (REG_INC,
149 reg, REG_NOTES (insn));
152 PUT_CODE (inc_insn, NOTE);
153 NOTE_LINE_NUMBER (inc_insn) = NOTE_INSN_DELETED;
154 NOTE_SOURCE_FILE (inc_insn) = 0;
164 /* Determine if the pattern generated by add_optab has a clobber,
165 such as might be issued for a flags hard register. To make the
166 code elsewhere simpler, we handle cc0 in this same framework.
168 Return the register if one was discovered. Return NULL_RTX if
169 if no flags were found. Return pc_rtx if we got confused. */
172 discover_flags_reg ()
175 tmp = gen_rtx_REG (word_mode, 10000);
176 tmp = gen_add3_insn (tmp, tmp, GEN_INT (2));
178 /* If we get something that isn't a simple set, or a
179 [(set ..) (clobber ..)], this whole function will go wrong. */
180 if (GET_CODE (tmp) == SET)
182 else if (GET_CODE (tmp) == PARALLEL)
186 if (XVECLEN (tmp, 0) != 2)
188 tmp = XVECEXP (tmp, 0, 1);
189 if (GET_CODE (tmp) != CLOBBER)
193 /* Don't do anything foolish if the md wanted to clobber a
194 scratch or something. We only care about hard regs.
195 Moreover we don't like the notion of subregs of hard regs. */
196 if (GET_CODE (tmp) == SUBREG
197 && GET_CODE (SUBREG_REG (tmp)) == REG
198 && REGNO (SUBREG_REG (tmp)) < FIRST_PSEUDO_REGISTER)
200 found = (GET_CODE (tmp) == REG && REGNO (tmp) < FIRST_PSEUDO_REGISTER);
202 return (found ? tmp : NULL_RTX);
208 /* It is a tedious task identifying when the flags register is live and
209 when it is safe to optimize. Since we process the instruction stream
210 multiple times, locate and record these live zones by marking the
211 mode of the instructions --
213 QImode is used on the instruction at which the flags becomes live.
215 HImode is used within the range (exclusive) that the flags are
216 live. Thus the user of the flags is not marked.
218 All other instructions are cleared to VOIDmode. */
220 /* Used to communicate with flags_set_1. */
221 static rtx flags_set_1_rtx;
222 static int flags_set_1_set;
225 mark_flags_life_zones (flags)
233 /* If we found a flags register on a cc0 host, bail. */
234 if (flags == NULL_RTX)
236 else if (flags != cc0_rtx)
240 /* Simple cases first: if no flags, clear all modes. If confusing,
241 mark the entire function as being in a flags shadow. */
242 if (flags == NULL_RTX || flags == pc_rtx)
244 enum machine_mode mode = (flags ? HImode : VOIDmode);
246 for (insn = get_insns(); insn; insn = NEXT_INSN (insn))
247 PUT_MODE (insn, mode);
255 flags_regno = REGNO (flags);
256 flags_nregs = HARD_REGNO_NREGS (flags_regno, GET_MODE (flags));
258 flags_set_1_rtx = flags;
260 /* Process each basic block. */
261 for (block = n_basic_blocks - 1; block >= 0; block--)
266 insn = BLOCK_HEAD (block);
267 end = BLOCK_END (block);
269 /* Look out for the (unlikely) case of flags being live across
270 basic block boundaries. */
275 for (i = 0; i < flags_nregs; ++i)
276 live |= REGNO_REG_SET_P (BASIC_BLOCK (block)->global_live_at_start,
283 /* Process liveness in reverse order of importance --
284 alive, death, birth. This lets more important info
285 overwrite the mode of lesser info. */
290 /* In the cc0 case, death is not marked in reg notes,
291 but is instead the mere use of cc0 when it is alive. */
292 if (live && reg_mentioned_p (cc0_rtx, PATTERN (insn)))
295 /* In the hard reg case, we watch death notes. */
296 if (live && find_regno_note (insn, REG_DEAD, flags_regno))
299 PUT_MODE (insn, (live ? HImode : VOIDmode));
301 /* In either case, birth is denoted simply by it's presence
302 as the destination of a set. */
304 note_stores (PATTERN (insn), flags_set_1, NULL);
308 PUT_MODE (insn, QImode);
312 PUT_MODE (insn, (live ? HImode : VOIDmode));
316 insn = NEXT_INSN (insn);
321 /* A subroutine of mark_flags_life_zones, called through note_stores. */
324 flags_set_1 (x, pat, data)
326 void *data ATTRIBUTE_UNUSED;
328 if (GET_CODE (pat) == SET
329 && reg_overlap_mentioned_p (x, flags_set_1_rtx))
333 static int *regno_src_regno;
335 /* Indicate how good a choice REG (which appears as a source) is to replace
336 a destination register with. The higher the returned value, the better
337 the choice. The main objective is to avoid using a register that is
338 a candidate for tying to a hard register, since the output might in
339 turn be a candidate to be tied to a different hard register. */
341 replacement_quality(reg)
346 /* Bad if this isn't a register at all. */
347 if (GET_CODE (reg) != REG)
350 /* If this register is not meant to get a hard register,
351 it is a poor choice. */
352 if (REG_LIVE_LENGTH (REGNO (reg)) < 0)
355 src_regno = regno_src_regno[REGNO (reg)];
357 /* If it was not copied from another register, it is fine. */
361 /* Copied from a hard register? */
362 if (src_regno < FIRST_PSEUDO_REGISTER)
365 /* Copied from a pseudo register - not as bad as from a hard register,
366 yet still cumbersome, since the register live length will be lengthened
367 when the registers get tied. */
371 /* INSN is a copy from SRC to DEST, both registers, and SRC does not die
374 Search forward to see if SRC dies before either it or DEST is modified,
375 but don't scan past the end of a basic block. If so, we can replace SRC
376 with DEST and let SRC die in INSN.
378 This will reduce the number of registers live in that range and may enable
379 DEST to be tied to SRC, thus often saving one register in addition to a
380 register-register copy. */
383 optimize_reg_copy_1 (insn, dest, src)
391 int sregno = REGNO (src);
392 int dregno = REGNO (dest);
394 /* We don't want to mess with hard regs if register classes are small. */
396 || (SMALL_REGISTER_CLASSES
397 && (sregno < FIRST_PSEUDO_REGISTER
398 || dregno < FIRST_PSEUDO_REGISTER))
399 /* We don't see all updates to SP if they are in an auto-inc memory
400 reference, so we must disallow this optimization on them. */
401 || sregno == STACK_POINTER_REGNUM || dregno == STACK_POINTER_REGNUM)
404 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
406 if (GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN)
409 /* ??? We can't scan past the end of a basic block without updating
410 the register lifetime info (REG_DEAD/basic_block_live_at_start).
411 A CALL_INSN might be the last insn of a basic block, if it is inside
412 an EH region. There is no easy way to tell, so we just always break
413 when we see a CALL_INSN if flag_exceptions is nonzero. */
414 if (flag_exceptions && GET_CODE (p) == CALL_INSN)
420 if (reg_set_p (src, p) || reg_set_p (dest, p)
421 /* Don't change a USE of a register. */
422 || (GET_CODE (PATTERN (p)) == USE
423 && reg_overlap_mentioned_p (src, XEXP (PATTERN (p), 0))))
426 /* See if all of SRC dies in P. This test is slightly more
427 conservative than it needs to be. */
428 if ((note = find_regno_note (p, REG_DEAD, sregno)) != 0
429 && GET_MODE (XEXP (note, 0)) == GET_MODE (src))
437 /* We can do the optimization. Scan forward from INSN again,
438 replacing regs as we go. Set FAILED if a replacement can't
439 be done. In that case, we can't move the death note for SRC.
440 This should be rare. */
442 /* Set to stop at next insn. */
443 for (q = next_real_insn (insn);
444 q != next_real_insn (p);
445 q = next_real_insn (q))
447 if (reg_overlap_mentioned_p (src, PATTERN (q)))
449 /* If SRC is a hard register, we might miss some
450 overlapping registers with validate_replace_rtx,
451 so we would have to undo it. We can't if DEST is
452 present in the insn, so fail in that combination
454 if (sregno < FIRST_PSEUDO_REGISTER
455 && reg_mentioned_p (dest, PATTERN (q)))
458 /* Replace all uses and make sure that the register
459 isn't still present. */
460 else if (validate_replace_rtx (src, dest, q)
461 && (sregno >= FIRST_PSEUDO_REGISTER
462 || ! reg_overlap_mentioned_p (src,
467 validate_replace_rtx (dest, src, q);
472 /* For SREGNO, count the total number of insns scanned.
473 For DREGNO, count the total number of insns scanned after
474 passing the death note for DREGNO. */
479 /* If the insn in which SRC dies is a CALL_INSN, don't count it
480 as a call that has been crossed. Otherwise, count it. */
481 if (q != p && GET_CODE (q) == CALL_INSN)
483 /* Similarly, total calls for SREGNO, total calls beyond
484 the death note for DREGNO. */
490 /* If DEST dies here, remove the death note and save it for
491 later. Make sure ALL of DEST dies here; again, this is
492 overly conservative. */
494 && (dest_death = find_regno_note (q, REG_DEAD, dregno)) != 0)
496 if (GET_MODE (XEXP (dest_death, 0)) != GET_MODE (dest))
497 failed = 1, dest_death = 0;
499 remove_note (q, dest_death);
505 /* These counters need to be updated if and only if we are
506 going to move the REG_DEAD note. */
507 if (sregno >= FIRST_PSEUDO_REGISTER)
509 if (REG_LIVE_LENGTH (sregno) >= 0)
511 REG_LIVE_LENGTH (sregno) -= s_length;
512 /* REG_LIVE_LENGTH is only an approximation after
513 combine if sched is not run, so make sure that we
514 still have a reasonable value. */
515 if (REG_LIVE_LENGTH (sregno) < 2)
516 REG_LIVE_LENGTH (sregno) = 2;
519 REG_N_CALLS_CROSSED (sregno) -= s_n_calls;
522 /* Move death note of SRC from P to INSN. */
523 remove_note (p, note);
524 XEXP (note, 1) = REG_NOTES (insn);
525 REG_NOTES (insn) = note;
528 /* DEST is also dead if INSN has a REG_UNUSED note for DEST. */
530 && (dest_death = find_regno_note (insn, REG_UNUSED, dregno)))
532 PUT_REG_NOTE_KIND (dest_death, REG_DEAD);
533 remove_note (insn, dest_death);
536 /* Put death note of DEST on P if we saw it die. */
539 XEXP (dest_death, 1) = REG_NOTES (p);
540 REG_NOTES (p) = dest_death;
542 if (dregno >= FIRST_PSEUDO_REGISTER)
544 /* If and only if we are moving the death note for DREGNO,
545 then we need to update its counters. */
546 if (REG_LIVE_LENGTH (dregno) >= 0)
547 REG_LIVE_LENGTH (dregno) += d_length;
548 REG_N_CALLS_CROSSED (dregno) += d_n_calls;
555 /* If SRC is a hard register which is set or killed in some other
556 way, we can't do this optimization. */
557 else if (sregno < FIRST_PSEUDO_REGISTER
558 && dead_or_set_p (p, src))
564 /* INSN is a copy of SRC to DEST, in which SRC dies. See if we now have
565 a sequence of insns that modify DEST followed by an insn that sets
566 SRC to DEST in which DEST dies, with no prior modification of DEST.
567 (There is no need to check if the insns in between actually modify
568 DEST. We should not have cases where DEST is not modified, but
569 the optimization is safe if no such modification is detected.)
570 In that case, we can replace all uses of DEST, starting with INSN and
571 ending with the set of SRC to DEST, with SRC. We do not do this
572 optimization if a CALL_INSN is crossed unless SRC already crosses a
573 call or if DEST dies before the copy back to SRC.
575 It is assumed that DEST and SRC are pseudos; it is too complicated to do
576 this for hard registers since the substitutions we may make might fail. */
579 optimize_reg_copy_2 (insn, dest, src)
586 int sregno = REGNO (src);
587 int dregno = REGNO (dest);
589 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
591 if (GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN)
594 /* ??? We can't scan past the end of a basic block without updating
595 the register lifetime info (REG_DEAD/basic_block_live_at_start).
596 A CALL_INSN might be the last insn of a basic block, if it is inside
597 an EH region. There is no easy way to tell, so we just always break
598 when we see a CALL_INSN if flag_exceptions is nonzero. */
599 if (flag_exceptions && GET_CODE (p) == CALL_INSN)
605 set = single_set (p);
606 if (set && SET_SRC (set) == dest && SET_DEST (set) == src
607 && find_reg_note (p, REG_DEAD, dest))
609 /* We can do the optimization. Scan forward from INSN again,
610 replacing regs as we go. */
612 /* Set to stop at next insn. */
613 for (q = insn; q != NEXT_INSN (p); q = NEXT_INSN (q))
616 if (reg_mentioned_p (dest, PATTERN (q)))
617 PATTERN (q) = replace_rtx (PATTERN (q), dest, src);
620 if (GET_CODE (q) == CALL_INSN)
622 REG_N_CALLS_CROSSED (dregno)--;
623 REG_N_CALLS_CROSSED (sregno)++;
627 remove_note (p, find_reg_note (p, REG_DEAD, dest));
628 REG_N_DEATHS (dregno)--;
629 remove_note (insn, find_reg_note (insn, REG_DEAD, src));
630 REG_N_DEATHS (sregno)--;
634 if (reg_set_p (src, p)
635 || find_reg_note (p, REG_DEAD, dest)
636 || (GET_CODE (p) == CALL_INSN && REG_N_CALLS_CROSSED (sregno) == 0))
640 /* INSN is a ZERO_EXTEND or SIGN_EXTEND of SRC to DEST.
641 Look if SRC dies there, and if it is only set once, by loading
642 it from memory. If so, try to encorporate the zero/sign extension
643 into the memory read, change SRC to the mode of DEST, and alter
644 the remaining accesses to use the appropriate SUBREG. This allows
645 SRC and DEST to be tied later. */
647 optimize_reg_copy_3 (insn, dest, src)
652 rtx src_reg = XEXP (src, 0);
653 int src_no = REGNO (src_reg);
654 int dst_no = REGNO (dest);
656 enum machine_mode old_mode;
658 if (src_no < FIRST_PSEUDO_REGISTER
659 || dst_no < FIRST_PSEUDO_REGISTER
660 || ! find_reg_note (insn, REG_DEAD, src_reg)
661 || REG_N_SETS (src_no) != 1)
663 for (p = PREV_INSN (insn); p && ! reg_set_p (src_reg, p); p = PREV_INSN (p))
665 if (GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN)
668 /* ??? We can't scan past the end of a basic block without updating
669 the register lifetime info (REG_DEAD/basic_block_live_at_start).
670 A CALL_INSN might be the last insn of a basic block, if it is inside
671 an EH region. There is no easy way to tell, so we just always break
672 when we see a CALL_INSN if flag_exceptions is nonzero. */
673 if (flag_exceptions && GET_CODE (p) == CALL_INSN)
682 if (! (set = single_set (p))
683 || GET_CODE (SET_SRC (set)) != MEM
684 || SET_DEST (set) != src_reg)
687 /* Be conserative: although this optimization is also valid for
688 volatile memory references, that could cause trouble in later passes. */
689 if (MEM_VOLATILE_P (SET_SRC (set)))
692 /* Do not use a SUBREG to truncate from one mode to another if truncation
694 if (GET_MODE_BITSIZE (GET_MODE (src_reg)) <= GET_MODE_BITSIZE (GET_MODE (src))
695 && !TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (GET_MODE (src)),
696 GET_MODE_BITSIZE (GET_MODE (src_reg))))
699 old_mode = GET_MODE (src_reg);
700 PUT_MODE (src_reg, GET_MODE (src));
701 XEXP (src, 0) = SET_SRC (set);
703 /* Include this change in the group so that it's easily undone if
704 one of the changes in the group is invalid. */
705 validate_change (p, &SET_SRC (set), src, 1);
707 /* Now walk forward making additional replacements. We want to be able
708 to undo all the changes if a later substitution fails. */
709 subreg = gen_rtx_SUBREG (old_mode, src_reg, 0);
710 while (p = NEXT_INSN (p), p != insn)
715 /* Make a tenative change. */
716 validate_replace_rtx_group (src_reg, subreg, p);
719 validate_replace_rtx_group (src, src_reg, insn);
721 /* Now see if all the changes are valid. */
722 if (! apply_change_group ())
724 /* One or more changes were no good. Back out everything. */
725 PUT_MODE (src_reg, old_mode);
726 XEXP (src, 0) = src_reg;
731 /* If we were not able to update the users of src to use dest directly, try
732 instead moving the value to dest directly before the operation. */
735 copy_src_to_dest (insn, src, dest, old_max_uid)
754 /* A REG_LIVE_LENGTH of -1 indicates the register is equivalent to a constant
755 or memory location and is used infrequently; a REG_LIVE_LENGTH of -2 is
756 parameter when there is no frame pointer that is not allocated a register.
757 For now, we just reject them, rather than incrementing the live length. */
759 if (GET_CODE (src) == REG
760 && REG_LIVE_LENGTH (REGNO (src)) > 0
761 && GET_CODE (dest) == REG
762 && !RTX_UNCHANGING_P (dest)
763 && REG_LIVE_LENGTH (REGNO (dest)) > 0
764 && (set = single_set (insn)) != NULL_RTX
765 && !reg_mentioned_p (dest, SET_SRC (set))
766 && GET_MODE (src) == GET_MODE (dest))
768 int old_num_regs = reg_rtx_no;
770 /* Generate the src->dest move. */
772 emit_move_insn (dest, src);
773 seq = gen_sequence ();
775 /* If this sequence uses new registers, we may not use it. */
776 if (old_num_regs != reg_rtx_no
777 || ! validate_replace_rtx (src, dest, insn))
779 /* We have to restore reg_rtx_no to its old value, lest
780 recompute_reg_usage will try to compute the usage of the
781 new regs, yet reg_n_info is not valid for them. */
782 reg_rtx_no = old_num_regs;
785 emit_insn_before (seq, insn);
786 move_insn = PREV_INSN (insn);
787 p_move_notes = ®_NOTES (move_insn);
788 p_insn_notes = ®_NOTES (insn);
790 /* Move any notes mentioning src to the move instruction */
791 for (link = REG_NOTES (insn); link != NULL_RTX; link = next)
793 next = XEXP (link, 1);
794 if (XEXP (link, 0) == src)
796 *p_move_notes = link;
797 p_move_notes = &XEXP (link, 1);
801 *p_insn_notes = link;
802 p_insn_notes = &XEXP (link, 1);
806 *p_move_notes = NULL_RTX;
807 *p_insn_notes = NULL_RTX;
809 /* Is the insn the head of a basic block? If so extend it */
810 insn_uid = INSN_UID (insn);
811 move_uid = INSN_UID (move_insn);
812 if (insn_uid < old_max_uid)
814 bb = regmove_bb_head[insn_uid];
817 BLOCK_HEAD (bb) = move_insn;
818 regmove_bb_head[insn_uid] = -1;
822 /* Update the various register tables. */
823 dest_regno = REGNO (dest);
824 REG_N_SETS (dest_regno) ++;
825 REG_LIVE_LENGTH (dest_regno)++;
826 if (REGNO_FIRST_UID (dest_regno) == insn_uid)
827 REGNO_FIRST_UID (dest_regno) = move_uid;
829 src_regno = REGNO (src);
830 if (! find_reg_note (move_insn, REG_DEAD, src))
831 REG_LIVE_LENGTH (src_regno)++;
833 if (REGNO_FIRST_UID (src_regno) == insn_uid)
834 REGNO_FIRST_UID (src_regno) = move_uid;
836 if (REGNO_LAST_UID (src_regno) == insn_uid)
837 REGNO_LAST_UID (src_regno) = move_uid;
839 if (REGNO_LAST_NOTE_UID (src_regno) == insn_uid)
840 REGNO_LAST_NOTE_UID (src_regno) = move_uid;
845 /* Return whether REG is set in only one location, and is set to a
846 constant, but is set in a different basic block from INSN (an
847 instructions which uses REG). In this case REG is equivalent to a
848 constant, and we don't want to break that equivalence, because that
849 may increase register pressure and make reload harder. If REG is
850 set in the same basic block as INSN, we don't worry about it,
851 because we'll probably need a register anyhow (??? but what if REG
852 is used in a different basic block as well as this one?). FIRST is
853 the first insn in the function. */
856 reg_is_remote_constant_p (reg, insn, first)
863 if (REG_N_SETS (REGNO (reg)) != 1)
866 /* Look for the set. */
867 for (p = LOG_LINKS (insn); p; p = XEXP (p, 1))
871 if (REG_NOTE_KIND (p) != 0)
873 s = single_set (XEXP (p, 0));
875 && GET_CODE (SET_DEST (s)) == REG
876 && REGNO (SET_DEST (s)) == REGNO (reg))
878 /* The register is set in the same basic block. */
883 for (p = first; p && p != insn; p = NEXT_INSN (p))
891 && GET_CODE (SET_DEST (s)) == REG
892 && REGNO (SET_DEST (s)) == REGNO (reg))
894 /* This is the instruction which sets REG. If there is a
895 REG_EQUAL note, then REG is equivalent to a constant. */
896 if (find_reg_note (p, REG_EQUAL, NULL_RTX))
905 /* INSN is adding a CONST_INT to a REG. We search backwards looking for
906 another add immediate instruction with the same source and dest registers,
907 and if we find one, we change INSN to an increment, and return 1. If
908 no changes are made, we return 0.
911 (set (reg100) (plus reg1 offset1))
913 (set (reg100) (plus reg1 offset2))
915 (set (reg100) (plus reg1 offset1))
917 (set (reg100) (plus reg100 offset2-offset1)) */
919 /* ??? What does this comment mean? */
920 /* cse disrupts preincrement / postdecrement squences when it finds a
921 hard register as ultimate source, like the frame pointer. */
924 fixup_match_2 (insn, dst, src, offset, regmove_dump_file)
925 rtx insn, dst, src, offset;
926 FILE *regmove_dump_file;
928 rtx p, dst_death = 0;
929 int length, num_calls = 0;
931 /* If SRC dies in INSN, we'd have to move the death note. This is
932 considered to be very unlikely, so we just skip the optimization
934 if (find_regno_note (insn, REG_DEAD, REGNO (src)))
937 /* Scan backward to find the first instruction that sets DST. */
939 for (length = 0, p = PREV_INSN (insn); p; p = PREV_INSN (p))
943 if (GET_CODE (p) == CODE_LABEL
944 || GET_CODE (p) == JUMP_INSN)
947 /* ??? We can't scan past the end of a basic block without updating
948 the register lifetime info (REG_DEAD/basic_block_live_at_start).
949 A CALL_INSN might be the last insn of a basic block, if it is inside
950 an EH region. There is no easy way to tell, so we just always break
951 when we see a CALL_INSN if flag_exceptions is nonzero. */
952 if (flag_exceptions && GET_CODE (p) == CALL_INSN)
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)))
1050 regmove_optimize (f, nregs, regmove_dump_file)
1053 FILE *regmove_dump_file;
1055 int old_max_uid = get_max_uid ();
1060 rtx copy_src, copy_dst;
1062 /* Find out where a potential flags register is live, and so that we
1063 can supress some optimizations in those zones. */
1064 mark_flags_life_zones (discover_flags_reg ());
1066 regno_src_regno = (int *) xmalloc (sizeof *regno_src_regno * nregs);
1067 for (i = nregs; --i >= 0; ) regno_src_regno[i] = -1;
1069 regmove_bb_head = (int *) xmalloc (sizeof (int) * (old_max_uid + 1));
1070 for (i = old_max_uid; i >= 0; i--) regmove_bb_head[i] = -1;
1071 for (i = 0; i < n_basic_blocks; i++)
1072 regmove_bb_head[INSN_UID (BLOCK_HEAD (i))] = i;
1074 /* A forward/backward pass. Replace output operands with input operands. */
1076 for (pass = 0; pass <= 2; pass++)
1078 if (! flag_regmove && pass >= flag_expensive_optimizations)
1081 if (regmove_dump_file)
1082 fprintf (regmove_dump_file, "Starting %s pass...\n",
1083 pass ? "backward" : "forward");
1085 for (insn = pass ? get_last_insn () : f; insn;
1086 insn = pass ? PREV_INSN (insn) : NEXT_INSN (insn))
1089 int op_no, match_no;
1091 set = single_set (insn);
1095 if (flag_expensive_optimizations && ! pass
1096 && (GET_CODE (SET_SRC (set)) == SIGN_EXTEND
1097 || GET_CODE (SET_SRC (set)) == ZERO_EXTEND)
1098 && GET_CODE (XEXP (SET_SRC (set), 0)) == REG
1099 && GET_CODE (SET_DEST(set)) == REG)
1100 optimize_reg_copy_3 (insn, SET_DEST (set), SET_SRC (set));
1102 if (flag_expensive_optimizations && ! pass
1103 && GET_CODE (SET_SRC (set)) == REG
1104 && GET_CODE (SET_DEST(set)) == REG)
1106 /* If this is a register-register copy where SRC is not dead,
1107 see if we can optimize it. If this optimization succeeds,
1108 it will become a copy where SRC is dead. */
1109 if ((find_reg_note (insn, REG_DEAD, SET_SRC (set))
1110 || optimize_reg_copy_1 (insn, SET_DEST (set), SET_SRC (set)))
1111 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
1113 /* Similarly for a pseudo-pseudo copy when SRC is dead. */
1114 if (REGNO (SET_SRC (set)) >= FIRST_PSEUDO_REGISTER)
1115 optimize_reg_copy_2 (insn, SET_DEST (set), SET_SRC (set));
1116 if (regno_src_regno[REGNO (SET_DEST (set))] < 0
1117 && SET_SRC (set) != SET_DEST (set))
1119 int srcregno = REGNO (SET_SRC(set));
1120 if (regno_src_regno[srcregno] >= 0)
1121 srcregno = regno_src_regno[srcregno];
1122 regno_src_regno[REGNO (SET_DEST (set))] = srcregno;
1129 if (! find_matches (insn, &match))
1132 /* Now scan through the operands looking for a source operand
1133 which is supposed to match the destination operand.
1134 Then scan forward for an instruction which uses the dest
1136 If it dies there, then replace the dest in both operands with
1137 the source operand. */
1139 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1141 rtx src, dst, src_subreg;
1142 enum reg_class src_class, dst_class;
1144 match_no = match.with[op_no];
1146 /* Nothing to do if the two operands aren't supposed to match. */
1150 src = recog_data.operand[op_no];
1151 dst = recog_data.operand[match_no];
1153 if (GET_CODE (src) != REG)
1157 if (GET_CODE (dst) == SUBREG
1158 && GET_MODE_SIZE (GET_MODE (dst))
1159 >= GET_MODE_SIZE (GET_MODE (SUBREG_REG (dst))))
1162 = gen_rtx_SUBREG (GET_MODE (SUBREG_REG (dst)),
1163 src, SUBREG_WORD (dst));
1164 dst = SUBREG_REG (dst);
1166 if (GET_CODE (dst) != REG
1167 || REGNO (dst) < FIRST_PSEUDO_REGISTER)
1170 if (REGNO (src) < FIRST_PSEUDO_REGISTER)
1172 if (match.commutative[op_no] < op_no)
1173 regno_src_regno[REGNO (dst)] = REGNO (src);
1177 if (REG_LIVE_LENGTH (REGNO (src)) < 0)
1180 /* op_no/src must be a read-only operand, and
1181 match_operand/dst must be a write-only operand. */
1182 if (match.use[op_no] != READ
1183 || match.use[match_no] != WRITE)
1186 if (match.early_clobber[match_no]
1187 && count_occurrences (PATTERN (insn), src, 0) > 1)
1190 /* Make sure match_operand is the destination. */
1191 if (recog_data.operand[match_no] != SET_DEST (set))
1194 /* If the operands already match, then there is nothing to do. */
1195 if (operands_match_p (src, dst))
1198 /* But in the commutative case, we might find a better match. */
1199 if (match.commutative[op_no] >= 0)
1201 rtx comm = recog_data.operand[match.commutative[op_no]];
1202 if (operands_match_p (comm, dst)
1203 && (replacement_quality (comm)
1204 >= replacement_quality (src)))
1208 src_class = reg_preferred_class (REGNO (src));
1209 dst_class = reg_preferred_class (REGNO (dst));
1210 if (! regclass_compatible_p (src_class, dst_class))
1213 if (fixup_match_1 (insn, set, src, src_subreg, dst, pass,
1221 /* A backward pass. Replace input operands with output operands. */
1223 if (regmove_dump_file)
1224 fprintf (regmove_dump_file, "Starting backward pass...\n");
1226 for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
1230 int op_no, match_no;
1233 if (! find_matches (insn, &match))
1236 /* Now scan through the operands looking for a destination operand
1237 which is supposed to match a source operand.
1238 Then scan backward for an instruction which sets the source
1239 operand. If safe, then replace the source operand with the
1240 dest operand in both instructions. */
1242 copy_src = NULL_RTX;
1243 copy_dst = NULL_RTX;
1244 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1246 rtx set, p, src, dst;
1247 rtx src_note, dst_note;
1249 enum reg_class src_class, dst_class;
1252 match_no = match.with[op_no];
1254 /* Nothing to do if the two operands aren't supposed to match. */
1258 dst = recog_data.operand[match_no];
1259 src = recog_data.operand[op_no];
1261 if (GET_CODE (src) != REG)
1264 if (GET_CODE (dst) != REG
1265 || REGNO (dst) < FIRST_PSEUDO_REGISTER
1266 || REG_LIVE_LENGTH (REGNO (dst)) < 0)
1269 /* If the operands already match, then there is nothing to do. */
1270 if (operands_match_p (src, dst))
1273 if (match.commutative[op_no] >= 0)
1275 rtx comm = recog_data.operand[match.commutative[op_no]];
1276 if (operands_match_p (comm, dst))
1280 set = single_set (insn);
1284 /* match_no/dst must be a write-only operand, and
1285 operand_operand/src must be a read-only operand. */
1286 if (match.use[op_no] != READ
1287 || match.use[match_no] != WRITE)
1290 if (match.early_clobber[match_no]
1291 && count_occurrences (PATTERN (insn), src, 0) > 1)
1294 /* Make sure match_no is the destination. */
1295 if (recog_data.operand[match_no] != SET_DEST (set))
1298 if (REGNO (src) < FIRST_PSEUDO_REGISTER)
1300 if (GET_CODE (SET_SRC (set)) == PLUS
1301 && GET_CODE (XEXP (SET_SRC (set), 1)) == CONST_INT
1302 && XEXP (SET_SRC (set), 0) == src
1303 && fixup_match_2 (insn, dst, src,
1304 XEXP (SET_SRC (set), 1),
1309 src_class = reg_preferred_class (REGNO (src));
1310 dst_class = reg_preferred_class (REGNO (dst));
1311 if (! regclass_compatible_p (src_class, dst_class))
1321 /* Can not modify an earlier insn to set dst if this insn
1322 uses an old value in the source. */
1323 if (reg_overlap_mentioned_p (dst, SET_SRC (set)))
1333 if (! (src_note = find_reg_note (insn, REG_DEAD, src)))
1344 /* If src is set once in a different basic block,
1345 and is set equal to a constant, then do not use
1346 it for this optimization, as this would make it
1347 no longer equivalent to a constant. */
1349 if (reg_is_remote_constant_p (src, insn, f))
1360 if (regmove_dump_file)
1361 fprintf (regmove_dump_file,
1362 "Could fix operand %d of insn %d matching operand %d.\n",
1363 op_no, INSN_UID (insn), match_no);
1365 /* Scan backward to find the first instruction that uses
1366 the input operand. If the operand is set here, then
1367 replace it in both instructions with match_no. */
1369 for (length = 0, p = PREV_INSN (insn); p; p = PREV_INSN (p))
1373 if (GET_CODE (p) == CODE_LABEL
1374 || GET_CODE (p) == JUMP_INSN)
1377 /* ??? We can't scan past the end of a basic block without
1378 updating the register lifetime info
1379 (REG_DEAD/basic_block_live_at_start).
1380 A CALL_INSN might be the last insn of a basic block, if
1381 it is inside an EH region. There is no easy way to tell,
1382 so we just always break when we see a CALL_INSN if
1383 flag_exceptions is nonzero. */
1384 if (flag_exceptions && GET_CODE (p) == CALL_INSN)
1392 /* ??? See if all of SRC is set in P. This test is much
1393 more conservative than it needs to be. */
1394 pset = single_set (p);
1395 if (pset && SET_DEST (pset) == src)
1397 /* We use validate_replace_rtx, in case there
1398 are multiple identical source operands. All of
1399 them have to be changed at the same time. */
1400 if (validate_replace_rtx (src, dst, insn))
1402 if (validate_change (p, &SET_DEST (pset),
1407 /* Change all source operands back.
1408 This modifies the dst as a side-effect. */
1409 validate_replace_rtx (dst, src, insn);
1410 /* Now make sure the dst is right. */
1411 validate_change (insn,
1412 recog_data.operand_loc[match_no],
1419 if (reg_overlap_mentioned_p (src, PATTERN (p))
1420 || reg_overlap_mentioned_p (dst, PATTERN (p)))
1423 /* If we have passed a call instruction, and the
1424 pseudo-reg DST is not already live across a call,
1425 then don't perform the optimization. */
1426 if (GET_CODE (p) == CALL_INSN)
1430 if (REG_N_CALLS_CROSSED (REGNO (dst)) == 0)
1439 /* Remove the death note for SRC from INSN. */
1440 remove_note (insn, src_note);
1441 /* Move the death note for SRC to P if it is used
1443 if (reg_overlap_mentioned_p (src, PATTERN (p)))
1445 XEXP (src_note, 1) = REG_NOTES (p);
1446 REG_NOTES (p) = src_note;
1448 /* If there is a REG_DEAD note for DST on P, then remove
1449 it, because DST is now set there. */
1450 if ((dst_note = find_reg_note (p, REG_DEAD, dst)))
1451 remove_note (p, dst_note);
1453 dstno = REGNO (dst);
1454 srcno = REGNO (src);
1456 REG_N_SETS (dstno)++;
1457 REG_N_SETS (srcno)--;
1459 REG_N_CALLS_CROSSED (dstno) += num_calls;
1460 REG_N_CALLS_CROSSED (srcno) -= num_calls;
1462 REG_LIVE_LENGTH (dstno) += length;
1463 if (REG_LIVE_LENGTH (srcno) >= 0)
1465 REG_LIVE_LENGTH (srcno) -= length;
1466 /* REG_LIVE_LENGTH is only an approximation after
1467 combine if sched is not run, so make sure that we
1468 still have a reasonable value. */
1469 if (REG_LIVE_LENGTH (srcno) < 2)
1470 REG_LIVE_LENGTH (srcno) = 2;
1473 if (regmove_dump_file)
1474 fprintf (regmove_dump_file,
1475 "Fixed operand %d of insn %d matching operand %d.\n",
1476 op_no, INSN_UID (insn), match_no);
1482 /* If we weren't able to replace any of the alternatives, try an
1483 alternative appoach of copying the source to the destination. */
1484 if (!success && copy_src != NULL_RTX)
1485 copy_src_to_dest (insn, copy_src, copy_dst, old_max_uid);
1490 /* In fixup_match_1, some insns may have been inserted after basic block
1491 ends. Fix that here. */
1492 for (i = 0; i < n_basic_blocks; i++)
1494 rtx end = BLOCK_END (i);
1496 rtx next = NEXT_INSN (new);
1497 while (next != 0 && INSN_UID (next) >= old_max_uid
1498 && (i == n_basic_blocks - 1 || BLOCK_HEAD (i + 1) != next))
1499 new = next, next = NEXT_INSN (new);
1500 BLOCK_END (i) = new;
1505 free (regno_src_regno);
1506 free (regmove_bb_head);
1509 /* Returns nonzero if INSN's pattern has matching constraints for any operand.
1510 Returns 0 if INSN can't be recognized, or if the alternative can't be
1513 Initialize the info in MATCHP based on the constraints. */
1516 find_matches (insn, matchp)
1518 struct match *matchp;
1520 int likely_spilled[MAX_RECOG_OPERANDS];
1522 int any_matches = 0;
1524 extract_insn (insn);
1525 if (! constrain_operands (0))
1528 /* Must initialize this before main loop, because the code for
1529 the commutative case may set matches for operands other than
1531 for (op_no = recog_data.n_operands; --op_no >= 0; )
1532 matchp->with[op_no] = matchp->commutative[op_no] = -1;
1534 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1540 p = recog_data.constraints[op_no];
1542 likely_spilled[op_no] = 0;
1543 matchp->use[op_no] = READ;
1544 matchp->early_clobber[op_no] = 0;
1546 matchp->use[op_no] = WRITE;
1548 matchp->use[op_no] = READWRITE;
1550 for (;*p && i < which_alternative; p++)
1554 while ((c = *p++) != '\0' && c != ',')
1562 matchp->early_clobber[op_no] = 1;
1565 matchp->commutative[op_no] = op_no + 1;
1566 matchp->commutative[op_no + 1] = op_no;
1568 case '0': case '1': case '2': case '3': case '4':
1569 case '5': case '6': case '7': case '8': case '9':
1571 if (c < op_no && likely_spilled[(unsigned char) c])
1573 matchp->with[op_no] = c;
1575 if (matchp->commutative[op_no] >= 0)
1576 matchp->with[matchp->commutative[op_no]] = c;
1578 case 'a': case 'b': case 'c': case 'd': case 'e': case 'f': case 'h':
1579 case 'j': case 'k': case 'l': case 'p': case 'q': case 't': case 'u':
1580 case 'v': case 'w': case 'x': case 'y': case 'z': case 'A': case 'B':
1581 case 'C': case 'D': case 'W': case 'Y': case 'Z':
1582 if (CLASS_LIKELY_SPILLED_P (REG_CLASS_FROM_LETTER ((unsigned char)c)))
1583 likely_spilled[op_no] = 1;
1590 /* Try to replace output operand DST in SET, with input operand SRC. SET is
1591 the only set in INSN. INSN has just been recognized and constrained.
1592 SRC is operand number OPERAND_NUMBER in INSN.
1593 DST is operand number MATCH_NUMBER in INSN.
1594 If BACKWARD is nonzero, we have been called in a backward pass.
1595 Return nonzero for success. */
1597 fixup_match_1 (insn, set, src, src_subreg, dst, backward, operand_number,
1598 match_number, regmove_dump_file)
1599 rtx insn, set, src, src_subreg, dst;
1600 int backward, operand_number, match_number;
1601 FILE *regmove_dump_file;
1604 rtx post_inc = 0, post_inc_set = 0, search_end = 0;
1606 int num_calls = 0, s_num_calls = 0;
1607 enum rtx_code code = NOTE;
1608 HOST_WIDE_INT insn_const = 0, newconst;
1609 rtx overlap = 0; /* need to move insn ? */
1610 rtx src_note = find_reg_note (insn, REG_DEAD, src), dst_note = NULL_RTX;
1611 int length, s_length;
1613 /* If SRC is marked as unchanging, we may not change it.
1614 ??? Maybe we could get better code by removing the unchanging bit
1615 instead, and changing it back if we don't succeed? */
1616 if (RTX_UNCHANGING_P (src))
1621 /* Look for (set (regX) (op regA constX))
1622 (set (regY) (op regA constY))
1624 (set (regA) (op regA constX)).
1625 (set (regY) (op regA constY-constX)).
1626 This works for add and shift operations, if
1627 regA is dead after or set by the second insn. */
1629 code = GET_CODE (SET_SRC (set));
1630 if ((code == PLUS || code == LSHIFTRT
1631 || code == ASHIFT || code == ASHIFTRT)
1632 && XEXP (SET_SRC (set), 0) == src
1633 && GET_CODE (XEXP (SET_SRC (set), 1)) == CONST_INT)
1634 insn_const = INTVAL (XEXP (SET_SRC (set), 1));
1635 else if (! stable_and_no_regs_but_for_p (SET_SRC (set), src, dst))
1638 /* We might find a src_note while scanning. */
1642 if (regmove_dump_file)
1643 fprintf (regmove_dump_file,
1644 "Could fix operand %d of insn %d matching operand %d.\n",
1645 operand_number, INSN_UID (insn), match_number);
1647 /* If SRC is equivalent to a constant set in a different basic block,
1648 then do not use it for this optimization. We want the equivalence
1649 so that if we have to reload this register, we can reload the
1650 constant, rather than extending the lifespan of the register. */
1651 if (reg_is_remote_constant_p (src, insn, get_insns ()))
1654 /* Scan forward to find the next instruction that
1655 uses the output operand. If the operand dies here,
1656 then replace it in both instructions with
1659 for (length = s_length = 0, p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
1661 if (GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN)
1664 /* ??? We can't scan past the end of a basic block without updating
1665 the register lifetime info (REG_DEAD/basic_block_live_at_start).
1666 A CALL_INSN might be the last insn of a basic block, if it is
1667 inside an EH region. There is no easy way to tell, so we just
1668 always break when we see a CALL_INSN if flag_exceptions is nonzero. */
1669 if (flag_exceptions && GET_CODE (p) == CALL_INSN)
1679 if (reg_set_p (src, p) || reg_set_p (dst, p)
1680 || (GET_CODE (PATTERN (p)) == USE
1681 && reg_overlap_mentioned_p (src, XEXP (PATTERN (p), 0))))
1684 /* See if all of DST dies in P. This test is
1685 slightly more conservative than it needs to be. */
1686 if ((dst_note = find_regno_note (p, REG_DEAD, REGNO (dst)))
1687 && (GET_MODE (XEXP (dst_note, 0)) == GET_MODE (dst)))
1689 /* If we would be moving INSN, check that we won't move it
1690 into the shadow of a live a live flags register. */
1691 /* ??? We only try to move it in front of P, although
1692 we could move it anywhere between OVERLAP and P. */
1693 if (overlap && GET_MODE (PREV_INSN (p)) != VOIDmode)
1699 rtx set2 = NULL_RTX;
1701 /* If an optimization is done, the value of SRC while P
1702 is executed will be changed. Check that this is OK. */
1703 if (reg_overlap_mentioned_p (src, PATTERN (p)))
1705 for (q = p; q; q = NEXT_INSN (q))
1707 if (GET_CODE (q) == CODE_LABEL || GET_CODE (q) == JUMP_INSN)
1713 /* ??? We can't scan past the end of a basic block without
1714 updating the register lifetime info
1715 (REG_DEAD/basic_block_live_at_start).
1716 A CALL_INSN might be the last insn of a basic block, if
1717 it is inside an EH region. There is no easy way to tell,
1718 so we just always break when we see a CALL_INSN if
1719 flag_exceptions is nonzero. */
1720 if (flag_exceptions && GET_CODE (q) == CALL_INSN)
1728 if (reg_overlap_mentioned_p (src, PATTERN (q))
1729 || reg_set_p (src, q))
1733 set2 = single_set (q);
1734 if (! q || ! set2 || GET_CODE (SET_SRC (set2)) != code
1735 || XEXP (SET_SRC (set2), 0) != src
1736 || GET_CODE (XEXP (SET_SRC (set2), 1)) != CONST_INT
1737 || (SET_DEST (set2) != src
1738 && ! find_reg_note (q, REG_DEAD, src)))
1740 /* If this is a PLUS, we can still save a register by doing
1743 src -= insn_const; .
1744 This also gives opportunities for subsequent
1745 optimizations in the backward pass, so do it there. */
1746 if (code == PLUS && backward
1747 /* Don't do this if we can likely tie DST to SET_DEST
1748 of P later; we can't do this tying here if we got a
1750 && ! (dst_note && ! REG_N_CALLS_CROSSED (REGNO (dst))
1752 && GET_CODE (SET_DEST (single_set (p))) == REG
1753 && (REGNO (SET_DEST (single_set (p)))
1754 < FIRST_PSEUDO_REGISTER))
1755 /* We may only emit an insn directly after P if we
1756 are not in the shadow of a live flags register. */
1757 && GET_MODE (p) == VOIDmode)
1762 newconst = -insn_const;
1770 newconst = INTVAL (XEXP (SET_SRC (set2), 1)) - insn_const;
1771 /* Reject out of range shifts. */
1775 >= GET_MODE_BITSIZE (GET_MODE (SET_SRC (set2))))))
1780 if (SET_DEST (set2) != src)
1781 post_inc_set = set2;
1784 /* We use 1 as last argument to validate_change so that all
1785 changes are accepted or rejected together by apply_change_group
1786 when it is called by validate_replace_rtx . */
1787 validate_change (q, &XEXP (SET_SRC (set2), 1),
1788 GEN_INT (newconst), 1);
1790 validate_change (insn, recog_data.operand_loc[match_number], src, 1);
1791 if (validate_replace_rtx (dst, src_subreg, p))
1796 if (reg_overlap_mentioned_p (dst, PATTERN (p)))
1798 if (! src_note && reg_overlap_mentioned_p (src, PATTERN (p)))
1800 /* INSN was already checked to be movable wrt. the registers that it
1801 sets / uses when we found no REG_DEAD note for src on it, but it
1802 still might clobber the flags register. We'll have to check that
1803 we won't insert it into the shadow of a live flags register when
1804 we finally know where we are to move it. */
1806 src_note = find_reg_note (p, REG_DEAD, src);
1809 /* If we have passed a call instruction, and the pseudo-reg SRC is not
1810 already live across a call, then don't perform the optimization. */
1811 if (GET_CODE (p) == CALL_INSN)
1813 if (REG_N_CALLS_CROSSED (REGNO (src)) == 0)
1827 /* Remove the death note for DST from P. */
1828 remove_note (p, dst_note);
1831 post_inc = emit_insn_after (copy_rtx (PATTERN (insn)), p);
1832 if ((HAVE_PRE_INCREMENT || HAVE_PRE_DECREMENT)
1834 && try_auto_increment (search_end, post_inc, 0, src, newconst, 1))
1836 validate_change (insn, &XEXP (SET_SRC (set), 1), GEN_INT (insn_const), 0);
1837 REG_N_SETS (REGNO (src))++;
1838 REG_LIVE_LENGTH (REGNO (src))++;
1842 /* The lifetime of src and dest overlap,
1843 but we can change this by moving insn. */
1844 rtx pat = PATTERN (insn);
1846 remove_note (overlap, src_note);
1847 if ((HAVE_POST_INCREMENT || HAVE_POST_DECREMENT)
1849 && try_auto_increment (overlap, insn, 0, src, insn_const, 0))
1853 rtx notes = REG_NOTES (insn);
1855 emit_insn_after_with_line_notes (pat, PREV_INSN (p), insn);
1856 PUT_CODE (insn, NOTE);
1857 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
1858 NOTE_SOURCE_FILE (insn) = 0;
1859 /* emit_insn_after_with_line_notes has no
1860 return value, so search for the new insn. */
1862 while (! INSN_P (insn) || PATTERN (insn) != pat)
1863 insn = PREV_INSN (insn);
1865 REG_NOTES (insn) = notes;
1868 /* Sometimes we'd generate src = const; src += n;
1869 if so, replace the instruction that set src
1870 in the first place. */
1872 if (! overlap && (code == PLUS || code == MINUS))
1874 rtx note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
1875 rtx q, set2 = NULL_RTX;
1876 int num_calls2 = 0, s_length2 = 0;
1878 if (note && CONSTANT_P (XEXP (note, 0)))
1880 for (q = PREV_INSN (insn); q; q = PREV_INSN(q))
1882 if (GET_CODE (q) == CODE_LABEL || GET_CODE (q) == JUMP_INSN)
1888 /* ??? We can't scan past the end of a basic block without
1889 updating the register lifetime info
1890 (REG_DEAD/basic_block_live_at_start).
1891 A CALL_INSN might be the last insn of a basic block, if
1892 it is inside an EH region. There is no easy way to tell,
1893 so we just always break when we see a CALL_INSN if
1894 flag_exceptions is nonzero. */
1895 if (flag_exceptions && GET_CODE (q) == CALL_INSN)
1904 if (reg_set_p (src, q))
1906 set2 = single_set (q);
1909 if (reg_overlap_mentioned_p (src, PATTERN (q)))
1914 if (GET_CODE (p) == CALL_INSN)
1917 if (q && set2 && SET_DEST (set2) == src && CONSTANT_P (SET_SRC (set2))
1918 && validate_change (insn, &SET_SRC (set), XEXP (note, 0), 0))
1921 NOTE_LINE_NUMBER (q) = NOTE_INSN_DELETED;
1922 NOTE_SOURCE_FILE (q) = 0;
1923 REG_N_SETS (REGNO (src))--;
1924 REG_N_CALLS_CROSSED (REGNO (src)) -= num_calls2;
1925 REG_LIVE_LENGTH (REGNO (src)) -= s_length2;
1931 if ((HAVE_PRE_INCREMENT || HAVE_PRE_DECREMENT)
1932 && (code == PLUS || code == MINUS) && insn_const
1933 && try_auto_increment (p, insn, 0, src, insn_const, 1))
1935 else if ((HAVE_POST_INCREMENT || HAVE_POST_DECREMENT)
1937 && try_auto_increment (p, post_inc, post_inc_set, src, newconst, 0))
1939 /* If post_inc still prevails, try to find an
1940 insn where it can be used as a pre-in/decrement.
1941 If code is MINUS, this was already tried. */
1942 if (post_inc && code == PLUS
1943 /* Check that newconst is likely to be usable
1944 in a pre-in/decrement before starting the search. */
1945 && ((HAVE_PRE_INCREMENT && newconst > 0 && newconst <= MOVE_MAX)
1946 || (HAVE_PRE_DECREMENT && newconst < 0 && newconst >= -MOVE_MAX))
1947 && exact_log2 (newconst))
1951 inc_dest = post_inc_set ? SET_DEST (post_inc_set) : src;
1952 for (q = post_inc; (q = NEXT_INSN (q)); )
1954 if (GET_CODE (q) == CODE_LABEL || GET_CODE (q) == JUMP_INSN)
1957 /* ??? We can't scan past the end of a basic block without updating
1958 the register lifetime info (REG_DEAD/basic_block_live_at_start).
1959 A CALL_INSN might be the last insn of a basic block, if it
1960 is inside an EH region. There is no easy way to tell so we
1961 just always break when we see a CALL_INSN if flag_exceptions
1963 if (flag_exceptions && GET_CODE (q) == CALL_INSN)
1968 if (src != inc_dest && (reg_overlap_mentioned_p (src, PATTERN (q))
1969 || reg_set_p (src, q)))
1971 if (reg_set_p (inc_dest, q))
1973 if (reg_overlap_mentioned_p (inc_dest, PATTERN (q)))
1975 try_auto_increment (q, post_inc,
1976 post_inc_set, inc_dest, newconst, 1);
1981 /* Move the death note for DST to INSN if it is used
1983 if (reg_overlap_mentioned_p (dst, PATTERN (insn)))
1985 XEXP (dst_note, 1) = REG_NOTES (insn);
1986 REG_NOTES (insn) = dst_note;
1991 /* Move the death note for SRC from INSN to P. */
1993 remove_note (insn, src_note);
1994 XEXP (src_note, 1) = REG_NOTES (p);
1995 REG_NOTES (p) = src_note;
1997 REG_N_CALLS_CROSSED (REGNO (src)) += s_num_calls;
2000 REG_N_SETS (REGNO (src))++;
2001 REG_N_SETS (REGNO (dst))--;
2003 REG_N_CALLS_CROSSED (REGNO (dst)) -= num_calls;
2005 REG_LIVE_LENGTH (REGNO (src)) += s_length;
2006 if (REG_LIVE_LENGTH (REGNO (dst)) >= 0)
2008 REG_LIVE_LENGTH (REGNO (dst)) -= length;
2009 /* REG_LIVE_LENGTH is only an approximation after
2010 combine if sched is not run, so make sure that we
2011 still have a reasonable value. */
2012 if (REG_LIVE_LENGTH (REGNO (dst)) < 2)
2013 REG_LIVE_LENGTH (REGNO (dst)) = 2;
2015 if (regmove_dump_file)
2016 fprintf (regmove_dump_file,
2017 "Fixed operand %d of insn %d matching operand %d.\n",
2018 operand_number, INSN_UID (insn), match_number);
2023 /* return nonzero if X is stable and mentions no regsiters but for
2024 mentioning SRC or mentioning / changing DST . If in doubt, presume
2026 The rationale is that we want to check if we can move an insn easily
2027 while just paying attention to SRC and DST. A register is considered
2028 stable if it has the RTX_UNCHANGING_P bit set, but that would still
2029 leave the burden to update REG_DEAD / REG_UNUSED notes, so we don't
2030 want any registers but SRC and DST. */
2032 stable_and_no_regs_but_for_p (x, src, dst)
2035 RTX_CODE code = GET_CODE (x);
2036 switch (GET_RTX_CLASS (code))
2038 case '<': case '1': case 'c': case '2': case 'b': case '3':
2041 const char *fmt = GET_RTX_FORMAT (code);
2042 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2044 && ! stable_and_no_regs_but_for_p (XEXP (x, i), src, dst))
2050 return x == src || x == dst;
2051 /* If this is a MEM, look inside - there might be a register hidden in
2052 the address of an unchanging MEM. */
2054 && ! stable_and_no_regs_but_for_p (XEXP (x, 0), src, dst))
2058 return ! rtx_unstable_p (x);
2062 /* Track stack adjustments and stack memory references. Attempt to
2063 reduce the number of stack adjustments by back-propogating across
2064 the memory references.
2066 This is intended primarily for use with targets that do not define
2067 ACCUMULATE_OUTGOING_ARGS. It is of significantly more value to
2068 targets that define PREFERRED_STACK_BOUNDARY more aligned than
2069 STACK_BOUNDARY (e.g. x86), or if not all registers can be pushed
2070 (e.g. x86 fp regs) which would ordinarily have to be implemented
2071 as a sub/mov pair due to restrictions in calls.c.
2073 Propogation stops when any of the insns that need adjusting are
2074 (a) no longer valid because we've exceeded their range, (b) a
2075 non-trivial push instruction, or (c) a call instruction.
2077 Restriction B is based on the assumption that push instructions
2078 are smaller or faster. If a port really wants to remove all
2079 pushes, it should have defined ACCUMULATE_OUTGOING_ARGS. The
2080 one exception that is made is for an add immediately followed
2083 /* This structure records stack memory references between stack adjusting
2088 HOST_WIDE_INT sp_offset;
2090 struct csa_memlist *next;
2093 static int stack_memref_p PARAMS ((rtx));
2094 static rtx single_set_for_csa PARAMS ((rtx));
2095 static void free_csa_memlist PARAMS ((struct csa_memlist *));
2096 static struct csa_memlist *record_one_stack_memref
2097 PARAMS ((rtx, rtx *, struct csa_memlist *));
2098 static int try_apply_stack_adjustment
2099 PARAMS ((rtx, struct csa_memlist *, HOST_WIDE_INT, HOST_WIDE_INT));
2100 static void combine_stack_adjustments_for_block PARAMS ((basic_block));
2101 static int record_stack_memrefs PARAMS ((rtx *, void *));
2104 /* Main entry point for stack adjustment combination. */
2107 combine_stack_adjustments ()
2111 for (i = 0; i < n_basic_blocks; ++i)
2112 combine_stack_adjustments_for_block (BASIC_BLOCK (i));
2115 /* Recognize a MEM of the form (sp) or (plus sp const). */
2121 if (GET_CODE (x) != MEM)
2125 if (x == stack_pointer_rtx)
2127 if (GET_CODE (x) == PLUS
2128 && XEXP (x, 0) == stack_pointer_rtx
2129 && GET_CODE (XEXP (x, 1)) == CONST_INT)
2135 /* Recognize either normal single_set or the hack in i386.md for
2136 tying fp and sp adjustments. */
2139 single_set_for_csa (insn)
2143 rtx tmp = single_set (insn);
2147 if (GET_CODE (insn) != INSN
2148 || GET_CODE (PATTERN (insn)) != PARALLEL)
2151 tmp = PATTERN (insn);
2152 if (GET_CODE (XVECEXP (tmp, 0, 0)) != SET)
2155 for (i = 1; i < XVECLEN (tmp, 0); ++i)
2157 rtx this = XVECEXP (tmp, 0, i);
2159 /* The special case is allowing a no-op set. */
2160 if (GET_CODE (this) == SET
2161 && SET_SRC (this) == SET_DEST (this))
2163 else if (GET_CODE (this) != CLOBBER
2164 && GET_CODE (this) != USE)
2168 return XVECEXP (tmp, 0, 0);
2171 /* Free the list of csa_memlist nodes. */
2174 free_csa_memlist (memlist)
2175 struct csa_memlist *memlist;
2177 struct csa_memlist *next;
2178 for (; memlist ; memlist = next)
2180 next = memlist->next;
2185 /* Create a new csa_memlist node from the given memory reference.
2186 It is already known that the memory is stack_memref_p. */
2188 static struct csa_memlist *
2189 record_one_stack_memref (insn, mem, next_memlist)
2191 struct csa_memlist *next_memlist;
2193 struct csa_memlist *ml;
2195 ml = (struct csa_memlist *) xmalloc (sizeof (*ml));
2197 if (XEXP (*mem, 0) == stack_pointer_rtx)
2200 ml->sp_offset = INTVAL (XEXP (XEXP (*mem, 0), 1));
2204 ml->next = next_memlist;
2209 /* Attempt to apply ADJUST to the stack adjusting insn INSN, as well
2210 as each of the memories in MEMLIST. Return true on success. */
2213 try_apply_stack_adjustment (insn, memlist, new_adjust, delta)
2215 struct csa_memlist *memlist;
2216 HOST_WIDE_INT new_adjust, delta;
2218 struct csa_memlist *ml;
2221 /* We know INSN matches single_set_for_csa, because that's what we
2222 recognized earlier. However, if INSN is not single_set, it is
2223 doing double duty as a barrier for frame pointer memory accesses,
2224 which we are not recording. Therefore, an adjust insn that is not
2225 single_set may not have a positive delta applied. */
2227 if (delta > 0 && ! single_set (insn))
2229 set = single_set_for_csa (insn);
2230 validate_change (insn, &XEXP (SET_SRC (set), 1), GEN_INT (new_adjust), 1);
2232 for (ml = memlist; ml ; ml = ml->next)
2234 HOST_WIDE_INT c = ml->sp_offset - delta;
2235 rtx new = gen_rtx_MEM (GET_MODE (*ml->mem),
2236 plus_constant (stack_pointer_rtx, c));
2238 /* Don't reference memory below the stack pointer. */
2245 MEM_COPY_ATTRIBUTES (new, *ml->mem);
2246 validate_change (ml->insn, ml->mem, new, 1);
2249 if (apply_change_group ())
2251 /* Succeeded. Update our knowledge of the memory references. */
2252 for (ml = memlist; ml ; ml = ml->next)
2253 ml->sp_offset -= delta;
2261 /* Called via for_each_rtx and used to record all stack memory references in
2262 the insn and discard all other stack pointer references. */
2263 struct record_stack_memrefs_data
2266 struct csa_memlist *memlist;
2270 record_stack_memrefs (xp, data)
2275 struct record_stack_memrefs_data *d =
2276 (struct record_stack_memrefs_data *) data;
2279 switch (GET_CODE (x))
2282 if (!reg_mentioned_p (stack_pointer_rtx, x))
2284 /* We are not able to handle correctly all possible memrefs containing
2285 stack pointer, so this check is neccesary. */
2286 if (stack_memref_p (x))
2288 d->memlist = record_one_stack_memref (d->insn, xp, d->memlist);
2293 /* ??? We want be able to handle non-memory stack pointer references
2294 later. For now just discard all insns refering to stack pointer
2295 outside mem expressions. We would probably want to teach
2296 validate_replace to simplify expressions first. */
2297 if (x == stack_pointer_rtx)
2306 /* Subroutine of combine_stack_adjustments, called for each basic block. */
2309 combine_stack_adjustments_for_block (bb)
2312 HOST_WIDE_INT last_sp_adjust = 0;
2313 rtx last_sp_set = NULL_RTX;
2314 struct csa_memlist *memlist = NULL;
2317 struct record_stack_memrefs_data data;
2319 for (insn = bb->head; ; insn = next)
2323 pending_delete = NULL_RTX;
2324 next = NEXT_INSN (insn);
2326 if (! INSN_P (insn))
2329 set = single_set_for_csa (insn);
2332 rtx dest = SET_DEST (set);
2333 rtx src = SET_SRC (set);
2335 /* Find constant additions to the stack pointer. */
2336 if (dest == stack_pointer_rtx
2337 && GET_CODE (src) == PLUS
2338 && XEXP (src, 0) == stack_pointer_rtx
2339 && GET_CODE (XEXP (src, 1)) == CONST_INT)
2341 HOST_WIDE_INT this_adjust = INTVAL (XEXP (src, 1));
2343 /* If we've not seen an adjustment previously, record
2344 it now and continue. */
2348 last_sp_adjust = this_adjust;
2352 /* If not all recorded memrefs can be adjusted, or the
2353 adjustment is now too large for a constant addition,
2354 we cannot merge the two stack adjustments. */
2355 if (! try_apply_stack_adjustment (last_sp_set, memlist,
2356 last_sp_adjust + this_adjust,
2359 free_csa_memlist (memlist);
2362 last_sp_adjust = this_adjust;
2367 pending_delete = insn;
2368 last_sp_adjust += this_adjust;
2370 /* If, by some accident, the adjustments cancel out,
2371 delete both insns and start from scratch. */
2372 if (last_sp_adjust == 0)
2374 if (last_sp_set == bb->head)
2375 bb->head = NEXT_INSN (last_sp_set);
2376 flow_delete_insn (last_sp_set);
2378 free_csa_memlist (memlist);
2380 last_sp_set = NULL_RTX;
2386 /* Find a predecrement of exactly the previous adjustment and
2387 turn it into a direct store. Obviously we can't do this if
2388 there were any intervening uses of the stack pointer. */
2390 && last_sp_adjust == GET_MODE_SIZE (GET_MODE (dest))
2391 && GET_CODE (dest) == MEM
2392 && GET_CODE (XEXP (dest, 0)) == PRE_DEC
2393 && XEXP (XEXP (dest, 0), 0) == stack_pointer_rtx
2394 && ! reg_mentioned_p (stack_pointer_rtx, src)
2395 && memory_address_p (GET_MODE (dest), stack_pointer_rtx)
2396 && validate_change (insn, &SET_DEST (set),
2397 change_address (dest, VOIDmode,
2398 stack_pointer_rtx), 0))
2400 if (last_sp_set == bb->head)
2401 bb->head = NEXT_INSN (last_sp_set);
2402 flow_delete_insn (last_sp_set);
2404 free_csa_memlist (memlist);
2406 last_sp_set = NULL_RTX;
2413 data.memlist = memlist;
2414 if (GET_CODE (insn) != CALL_INSN && last_sp_set
2415 && !for_each_rtx (&PATTERN (insn), record_stack_memrefs, &data))
2417 memlist = data.memlist;
2420 memlist = data.memlist;
2422 /* Otherwise, we were not able to process the instruction.
2423 Do not continue collecting data across such a one. */
2425 && (GET_CODE (insn) == CALL_INSN
2426 || reg_mentioned_p (stack_pointer_rtx, PATTERN (insn))))
2428 free_csa_memlist (memlist);
2430 last_sp_set = NULL_RTX;
2435 if (insn == bb->end)
2439 flow_delete_insn (pending_delete);
2444 bb->end = PREV_INSN (pending_delete);
2445 flow_delete_insn (pending_delete);