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"
37 #include "hard-reg-set.h"
41 #include "insn-flags.h"
42 #include "basic-block.h"
45 static int optimize_reg_copy_1 PARAMS ((rtx, rtx, rtx));
46 static void optimize_reg_copy_2 PARAMS ((rtx, rtx, rtx));
47 static void optimize_reg_copy_3 PARAMS ((rtx, rtx, rtx));
48 static rtx gen_add3_insn PARAMS ((rtx, rtx, rtx));
49 static void copy_src_to_dest PARAMS ((rtx, rtx, rtx, int));
50 static int *regmove_bb_head;
53 int with[MAX_RECOG_OPERANDS];
54 enum { READ, WRITE, READWRITE } use[MAX_RECOG_OPERANDS];
55 int commutative[MAX_RECOG_OPERANDS];
56 int early_clobber[MAX_RECOG_OPERANDS];
59 static rtx discover_flags_reg PARAMS ((void));
60 static void mark_flags_life_zones PARAMS ((rtx));
61 static void flags_set_1 PARAMS ((rtx, rtx, void *));
63 static int try_auto_increment PARAMS ((rtx, rtx, rtx, rtx, HOST_WIDE_INT, int));
64 static int find_matches PARAMS ((rtx, struct match *));
65 static int fixup_match_1 PARAMS ((rtx, rtx, rtx, rtx, rtx, int, int, int, FILE *))
67 static int reg_is_remote_constant_p PARAMS ((rtx, rtx, rtx));
68 static int stable_and_no_regs_but_for_p PARAMS ((rtx, rtx, rtx));
69 static int regclass_compatible_p PARAMS ((int, int));
70 static int replacement_quality PARAMS ((rtx));
71 static int fixup_match_2 PARAMS ((rtx, rtx, rtx, rtx, FILE *));
73 /* Return non-zero if registers with CLASS1 and CLASS2 can be merged without
74 causing too much register allocation problems. */
76 regclass_compatible_p (class0, class1)
79 return (class0 == class1
80 || (reg_class_subset_p (class0, class1)
81 && ! CLASS_LIKELY_SPILLED_P (class0))
82 || (reg_class_subset_p (class1, class0)
83 && ! CLASS_LIKELY_SPILLED_P (class1)));
86 /* Generate and return an insn body to add r1 and c,
87 storing the result in r0. */
89 gen_add3_insn (r0, r1, c)
92 int icode = (int) add_optab->handlers[(int) GET_MODE (r0)].insn_code;
94 if (icode == CODE_FOR_nothing
95 || ! ((*insn_data[icode].operand[0].predicate)
96 (r0, insn_data[icode].operand[0].mode))
97 || ! ((*insn_data[icode].operand[1].predicate)
98 (r1, insn_data[icode].operand[1].mode))
99 || ! ((*insn_data[icode].operand[2].predicate)
100 (c, insn_data[icode].operand[2].mode)))
103 return (GEN_FCN (icode) (r0, r1, c));
107 /* INC_INSN is an instruction that adds INCREMENT to REG.
108 Try to fold INC_INSN as a post/pre in/decrement into INSN.
109 Iff INC_INSN_SET is nonzero, inc_insn has a destination different from src.
110 Return nonzero for success. */
112 try_auto_increment (insn, inc_insn, inc_insn_set, reg, increment, pre)
113 rtx reg, insn, inc_insn ,inc_insn_set;
114 HOST_WIDE_INT increment;
117 enum rtx_code inc_code;
119 rtx pset = single_set (insn);
122 /* Can't use the size of SET_SRC, we might have something like
123 (sign_extend:SI (mem:QI ... */
124 rtx use = find_use_as_address (pset, reg, 0);
125 if (use != 0 && use != (rtx) 1)
127 int size = GET_MODE_SIZE (GET_MODE (use));
129 || (HAVE_POST_INCREMENT
130 && pre == 0 && (inc_code = POST_INC, increment == size))
131 || (HAVE_PRE_INCREMENT
132 && pre == 1 && (inc_code = PRE_INC, increment == size))
133 || (HAVE_POST_DECREMENT
134 && pre == 0 && (inc_code = POST_DEC, increment == -size))
135 || (HAVE_PRE_DECREMENT
136 && pre == 1 && (inc_code = PRE_DEC, increment == -size))
142 &SET_SRC (inc_insn_set),
143 XEXP (SET_SRC (inc_insn_set), 0), 1);
144 validate_change (insn, &XEXP (use, 0),
145 gen_rtx_fmt_e (inc_code, Pmode, reg), 1);
146 if (apply_change_group ())
149 = gen_rtx_EXPR_LIST (REG_INC,
150 reg, REG_NOTES (insn));
153 PUT_CODE (inc_insn, NOTE);
154 NOTE_LINE_NUMBER (inc_insn) = NOTE_INSN_DELETED;
155 NOTE_SOURCE_FILE (inc_insn) = 0;
165 /* Determine if the pattern generated by add_optab has a clobber,
166 such as might be issued for a flags hard register. To make the
167 code elsewhere simpler, we handle cc0 in this same framework.
169 Return the register if one was discovered. Return NULL_RTX if
170 if no flags were found. Return pc_rtx if we got confused. */
173 discover_flags_reg ()
176 tmp = gen_rtx_REG (word_mode, 10000);
177 tmp = gen_add3_insn (tmp, tmp, GEN_INT (2));
179 /* If we get something that isn't a simple set, or a
180 [(set ..) (clobber ..)], this whole function will go wrong. */
181 if (GET_CODE (tmp) == SET)
183 else if (GET_CODE (tmp) == PARALLEL)
187 if (XVECLEN (tmp, 0) != 2)
189 tmp = XVECEXP (tmp, 0, 1);
190 if (GET_CODE (tmp) != CLOBBER)
194 /* Don't do anything foolish if the md wanted to clobber a
195 scratch or something. We only care about hard regs.
196 Moreover we don't like the notion of subregs of hard regs. */
197 if (GET_CODE (tmp) == SUBREG
198 && GET_CODE (SUBREG_REG (tmp)) == REG
199 && REGNO (SUBREG_REG (tmp)) < FIRST_PSEUDO_REGISTER)
201 found = (GET_CODE (tmp) == REG && REGNO (tmp) < FIRST_PSEUDO_REGISTER);
203 return (found ? tmp : NULL_RTX);
209 /* It is a tedious task identifying when the flags register is live and
210 when it is safe to optimize. Since we process the instruction stream
211 multiple times, locate and record these live zones by marking the
212 mode of the instructions --
214 QImode is used on the instruction at which the flags becomes live.
216 HImode is used within the range (exclusive) that the flags are
217 live. Thus the user of the flags is not marked.
219 All other instructions are cleared to VOIDmode. */
221 /* Used to communicate with flags_set_1. */
222 static rtx flags_set_1_rtx;
223 static int flags_set_1_set;
226 mark_flags_life_zones (flags)
234 /* If we found a flags register on a cc0 host, bail. */
235 if (flags == NULL_RTX)
237 else if (flags != cc0_rtx)
241 /* Simple cases first: if no flags, clear all modes. If confusing,
242 mark the entire function as being in a flags shadow. */
243 if (flags == NULL_RTX || flags == pc_rtx)
245 enum machine_mode mode = (flags ? HImode : VOIDmode);
247 for (insn = get_insns(); insn; insn = NEXT_INSN (insn))
248 PUT_MODE (insn, mode);
256 flags_regno = REGNO (flags);
257 flags_nregs = HARD_REGNO_NREGS (flags_regno, GET_MODE (flags));
259 flags_set_1_rtx = flags;
261 /* Process each basic block. */
262 for (block = n_basic_blocks - 1; block >= 0; block--)
267 insn = BLOCK_HEAD (block);
268 end = BLOCK_END (block);
270 /* Look out for the (unlikely) case of flags being live across
271 basic block boundaries. */
276 for (i = 0; i < flags_nregs; ++i)
277 live |= REGNO_REG_SET_P (BASIC_BLOCK (block)->global_live_at_start,
284 /* Process liveness in reverse order of importance --
285 alive, death, birth. This lets more important info
286 overwrite the mode of lesser info. */
288 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
291 /* In the cc0 case, death is not marked in reg notes,
292 but is instead the mere use of cc0 when it is alive. */
293 if (live && reg_mentioned_p (cc0_rtx, PATTERN (insn)))
296 /* In the hard reg case, we watch death notes. */
297 if (live && find_regno_note (insn, REG_DEAD, flags_regno))
300 PUT_MODE (insn, (live ? HImode : VOIDmode));
302 /* In either case, birth is denoted simply by it's presence
303 as the destination of a set. */
305 note_stores (PATTERN (insn), flags_set_1, NULL);
309 PUT_MODE (insn, QImode);
313 PUT_MODE (insn, (live ? HImode : VOIDmode));
317 insn = NEXT_INSN (insn);
322 /* A subroutine of mark_flags_life_zones, called through note_stores. */
325 flags_set_1 (x, pat, data)
327 void *data ATTRIBUTE_UNUSED;
329 if (GET_CODE (pat) == SET
330 && reg_overlap_mentioned_p (x, flags_set_1_rtx))
334 static int *regno_src_regno;
336 /* Indicate how good a choice REG (which appears as a source) is to replace
337 a destination register with. The higher the returned value, the better
338 the choice. The main objective is to avoid using a register that is
339 a candidate for tying to a hard register, since the output might in
340 turn be a candidate to be tied to a different hard register. */
342 replacement_quality(reg)
347 /* Bad if this isn't a register at all. */
348 if (GET_CODE (reg) != REG)
351 /* If this register is not meant to get a hard register,
352 it is a poor choice. */
353 if (REG_LIVE_LENGTH (REGNO (reg)) < 0)
356 src_regno = regno_src_regno[REGNO (reg)];
358 /* If it was not copied from another register, it is fine. */
362 /* Copied from a hard register? */
363 if (src_regno < FIRST_PSEUDO_REGISTER)
366 /* Copied from a pseudo register - not as bad as from a hard register,
367 yet still cumbersome, since the register live length will be lengthened
368 when the registers get tied. */
372 /* INSN is a copy from SRC to DEST, both registers, and SRC does not die
375 Search forward to see if SRC dies before either it or DEST is modified,
376 but don't scan past the end of a basic block. If so, we can replace SRC
377 with DEST and let SRC die in INSN.
379 This will reduce the number of registers live in that range and may enable
380 DEST to be tied to SRC, thus often saving one register in addition to a
381 register-register copy. */
384 optimize_reg_copy_1 (insn, dest, src)
392 int sregno = REGNO (src);
393 int dregno = REGNO (dest);
395 /* We don't want to mess with hard regs if register classes are small. */
397 || (SMALL_REGISTER_CLASSES
398 && (sregno < FIRST_PSEUDO_REGISTER
399 || dregno < FIRST_PSEUDO_REGISTER))
400 /* We don't see all updates to SP if they are in an auto-inc memory
401 reference, so we must disallow this optimization on them. */
402 || sregno == STACK_POINTER_REGNUM || dregno == STACK_POINTER_REGNUM)
405 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
407 if (GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN)
410 /* ??? We can't scan past the end of a basic block without updating
411 the register lifetime info (REG_DEAD/basic_block_live_at_start).
412 A CALL_INSN might be the last insn of a basic block, if it is inside
413 an EH region. There is no easy way to tell, so we just always break
414 when we see a CALL_INSN if flag_exceptions is nonzero. */
415 if (flag_exceptions && GET_CODE (p) == CALL_INSN)
418 if (GET_RTX_CLASS (GET_CODE (p)) != 'i')
421 if (reg_set_p (src, p) || reg_set_p (dest, p)
422 /* Don't change a USE of a register. */
423 || (GET_CODE (PATTERN (p)) == USE
424 && reg_overlap_mentioned_p (src, XEXP (PATTERN (p), 0))))
427 /* See if all of SRC dies in P. This test is slightly more
428 conservative than it needs to be. */
429 if ((note = find_regno_note (p, REG_DEAD, sregno)) != 0
430 && GET_MODE (XEXP (note, 0)) == GET_MODE (src))
438 /* We can do the optimization. Scan forward from INSN again,
439 replacing regs as we go. Set FAILED if a replacement can't
440 be done. In that case, we can't move the death note for SRC.
441 This should be rare. */
443 /* Set to stop at next insn. */
444 for (q = next_real_insn (insn);
445 q != next_real_insn (p);
446 q = next_real_insn (q))
448 if (reg_overlap_mentioned_p (src, PATTERN (q)))
450 /* If SRC is a hard register, we might miss some
451 overlapping registers with validate_replace_rtx,
452 so we would have to undo it. We can't if DEST is
453 present in the insn, so fail in that combination
455 if (sregno < FIRST_PSEUDO_REGISTER
456 && reg_mentioned_p (dest, PATTERN (q)))
459 /* Replace all uses and make sure that the register
460 isn't still present. */
461 else if (validate_replace_rtx (src, dest, q)
462 && (sregno >= FIRST_PSEUDO_REGISTER
463 || ! reg_overlap_mentioned_p (src,
468 validate_replace_rtx (dest, src, q);
473 /* For SREGNO, count the total number of insns scanned.
474 For DREGNO, count the total number of insns scanned after
475 passing the death note for DREGNO. */
480 /* If the insn in which SRC dies is a CALL_INSN, don't count it
481 as a call that has been crossed. Otherwise, count it. */
482 if (q != p && GET_CODE (q) == CALL_INSN)
484 /* Similarly, total calls for SREGNO, total calls beyond
485 the death note for DREGNO. */
491 /* If DEST dies here, remove the death note and save it for
492 later. Make sure ALL of DEST dies here; again, this is
493 overly conservative. */
495 && (dest_death = find_regno_note (q, REG_DEAD, dregno)) != 0)
497 if (GET_MODE (XEXP (dest_death, 0)) != GET_MODE (dest))
498 failed = 1, dest_death = 0;
500 remove_note (q, dest_death);
506 /* These counters need to be updated if and only if we are
507 going to move the REG_DEAD note. */
508 if (sregno >= FIRST_PSEUDO_REGISTER)
510 if (REG_LIVE_LENGTH (sregno) >= 0)
512 REG_LIVE_LENGTH (sregno) -= s_length;
513 /* REG_LIVE_LENGTH is only an approximation after
514 combine if sched is not run, so make sure that we
515 still have a reasonable value. */
516 if (REG_LIVE_LENGTH (sregno) < 2)
517 REG_LIVE_LENGTH (sregno) = 2;
520 REG_N_CALLS_CROSSED (sregno) -= s_n_calls;
523 /* Move death note of SRC from P to INSN. */
524 remove_note (p, note);
525 XEXP (note, 1) = REG_NOTES (insn);
526 REG_NOTES (insn) = note;
529 /* DEST is also dead if INSN has a REG_UNUSED note for DEST. */
531 && (dest_death = find_regno_note (insn, REG_UNUSED, dregno)))
533 PUT_REG_NOTE_KIND (dest_death, REG_DEAD);
534 remove_note (insn, dest_death);
537 /* Put death note of DEST on P if we saw it die. */
540 XEXP (dest_death, 1) = REG_NOTES (p);
541 REG_NOTES (p) = dest_death;
543 if (dregno >= FIRST_PSEUDO_REGISTER)
545 /* If and only if we are moving the death note for DREGNO,
546 then we need to update its counters. */
547 if (REG_LIVE_LENGTH (dregno) >= 0)
548 REG_LIVE_LENGTH (dregno) += d_length;
549 REG_N_CALLS_CROSSED (dregno) += d_n_calls;
556 /* If SRC is a hard register which is set or killed in some other
557 way, we can't do this optimization. */
558 else if (sregno < FIRST_PSEUDO_REGISTER
559 && dead_or_set_p (p, src))
565 /* INSN is a copy of SRC to DEST, in which SRC dies. See if we now have
566 a sequence of insns that modify DEST followed by an insn that sets
567 SRC to DEST in which DEST dies, with no prior modification of DEST.
568 (There is no need to check if the insns in between actually modify
569 DEST. We should not have cases where DEST is not modified, but
570 the optimization is safe if no such modification is detected.)
571 In that case, we can replace all uses of DEST, starting with INSN and
572 ending with the set of SRC to DEST, with SRC. We do not do this
573 optimization if a CALL_INSN is crossed unless SRC already crosses a
574 call or if DEST dies before the copy back to SRC.
576 It is assumed that DEST and SRC are pseudos; it is too complicated to do
577 this for hard registers since the substitutions we may make might fail. */
580 optimize_reg_copy_2 (insn, dest, src)
587 int sregno = REGNO (src);
588 int dregno = REGNO (dest);
590 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
592 if (GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN)
595 /* ??? We can't scan past the end of a basic block without updating
596 the register lifetime info (REG_DEAD/basic_block_live_at_start).
597 A CALL_INSN might be the last insn of a basic block, if it is inside
598 an EH region. There is no easy way to tell, so we just always break
599 when we see a CALL_INSN if flag_exceptions is nonzero. */
600 if (flag_exceptions && GET_CODE (p) == CALL_INSN)
603 if (GET_RTX_CLASS (GET_CODE (p)) != 'i')
606 set = single_set (p);
607 if (set && SET_SRC (set) == dest && SET_DEST (set) == src
608 && find_reg_note (p, REG_DEAD, dest))
610 /* We can do the optimization. Scan forward from INSN again,
611 replacing regs as we go. */
613 /* Set to stop at next insn. */
614 for (q = insn; q != NEXT_INSN (p); q = NEXT_INSN (q))
615 if (GET_RTX_CLASS (GET_CODE (q)) == 'i')
617 if (reg_mentioned_p (dest, PATTERN (q)))
618 PATTERN (q) = replace_rtx (PATTERN (q), dest, src);
621 if (GET_CODE (q) == CALL_INSN)
623 REG_N_CALLS_CROSSED (dregno)--;
624 REG_N_CALLS_CROSSED (sregno)++;
628 remove_note (p, find_reg_note (p, REG_DEAD, dest));
629 REG_N_DEATHS (dregno)--;
630 remove_note (insn, find_reg_note (insn, REG_DEAD, src));
631 REG_N_DEATHS (sregno)--;
635 if (reg_set_p (src, p)
636 || find_reg_note (p, REG_DEAD, dest)
637 || (GET_CODE (p) == CALL_INSN && REG_N_CALLS_CROSSED (sregno) == 0))
641 /* INSN is a ZERO_EXTEND or SIGN_EXTEND of SRC to DEST.
642 Look if SRC dies there, and if it is only set once, by loading
643 it from memory. If so, try to encorporate the zero/sign extension
644 into the memory read, change SRC to the mode of DEST, and alter
645 the remaining accesses to use the appropriate SUBREG. This allows
646 SRC and DEST to be tied later. */
648 optimize_reg_copy_3 (insn, dest, src)
653 rtx src_reg = XEXP (src, 0);
654 int src_no = REGNO (src_reg);
655 int dst_no = REGNO (dest);
657 enum machine_mode old_mode;
659 if (src_no < FIRST_PSEUDO_REGISTER
660 || dst_no < FIRST_PSEUDO_REGISTER
661 || ! find_reg_note (insn, REG_DEAD, src_reg)
662 || REG_N_SETS (src_no) != 1)
664 for (p = PREV_INSN (insn); p && ! reg_set_p (src_reg, p); p = PREV_INSN (p))
666 if (GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN)
669 /* ??? We can't scan past the end of a basic block without updating
670 the register lifetime info (REG_DEAD/basic_block_live_at_start).
671 A CALL_INSN might be the last insn of a basic block, if it is inside
672 an EH region. There is no easy way to tell, so we just always break
673 when we see a CALL_INSN if flag_exceptions is nonzero. */
674 if (flag_exceptions && GET_CODE (p) == CALL_INSN)
677 if (GET_RTX_CLASS (GET_CODE (p)) != 'i')
683 if (! (set = single_set (p))
684 || GET_CODE (SET_SRC (set)) != MEM
685 || SET_DEST (set) != src_reg)
688 /* Be conserative: although this optimization is also valid for
689 volatile memory references, that could cause trouble in later passes. */
690 if (MEM_VOLATILE_P (SET_SRC (set)))
693 /* Do not use a SUBREG to truncate from one mode to another if truncation
695 if (GET_MODE_BITSIZE (GET_MODE (src_reg)) <= GET_MODE_BITSIZE (GET_MODE (src))
696 && !TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (GET_MODE (src)),
697 GET_MODE_BITSIZE (GET_MODE (src_reg))))
700 old_mode = GET_MODE (src_reg);
701 PUT_MODE (src_reg, GET_MODE (src));
702 XEXP (src, 0) = SET_SRC (set);
704 /* Include this change in the group so that it's easily undone if
705 one of the changes in the group is invalid. */
706 validate_change (p, &SET_SRC (set), src, 1);
708 /* Now walk forward making additional replacements. We want to be able
709 to undo all the changes if a later substitution fails. */
710 subreg = gen_rtx_SUBREG (old_mode, src_reg, 0);
711 while (p = NEXT_INSN (p), p != insn)
713 if (GET_RTX_CLASS (GET_CODE (p)) != 'i')
716 /* Make a tenative change. */
717 validate_replace_rtx_group (src_reg, subreg, p);
720 validate_replace_rtx_group (src, src_reg, insn);
722 /* Now see if all the changes are valid. */
723 if (! apply_change_group ())
725 /* One or more changes were no good. Back out everything. */
726 PUT_MODE (src_reg, old_mode);
727 XEXP (src, 0) = src_reg;
732 /* If we were not able to update the users of src to use dest directly, try
733 instead moving the value to dest directly before the operation. */
736 copy_src_to_dest (insn, src, dest, old_max_uid)
755 /* A REG_LIVE_LENGTH of -1 indicates the register is equivalent to a constant
756 or memory location and is used infrequently; a REG_LIVE_LENGTH of -2 is
757 parameter when there is no frame pointer that is not allocated a register.
758 For now, we just reject them, rather than incrementing the live length. */
760 if (GET_CODE (src) == REG
761 && REG_LIVE_LENGTH (REGNO (src)) > 0
762 && GET_CODE (dest) == REG
763 && !RTX_UNCHANGING_P (dest)
764 && REG_LIVE_LENGTH (REGNO (dest)) > 0
765 && (set = single_set (insn)) != NULL_RTX
766 && !reg_mentioned_p (dest, SET_SRC (set))
767 && GET_MODE (src) == GET_MODE (dest))
769 int old_num_regs = reg_rtx_no;
771 /* Generate the src->dest move. */
773 emit_move_insn (dest, src);
774 seq = gen_sequence ();
776 /* If this sequence uses new registers, we may not use it. */
777 if (old_num_regs != reg_rtx_no
778 || ! validate_replace_rtx (src, dest, insn))
780 /* We have to restore reg_rtx_no to its old value, lest
781 recompute_reg_usage will try to compute the usage of the
782 new regs, yet reg_n_info is not valid for them. */
783 reg_rtx_no = old_num_regs;
786 emit_insn_before (seq, insn);
787 move_insn = PREV_INSN (insn);
788 p_move_notes = ®_NOTES (move_insn);
789 p_insn_notes = ®_NOTES (insn);
791 /* Move any notes mentioning src to the move instruction */
792 for (link = REG_NOTES (insn); link != NULL_RTX; link = next)
794 next = XEXP (link, 1);
795 if (XEXP (link, 0) == src)
797 *p_move_notes = link;
798 p_move_notes = &XEXP (link, 1);
802 *p_insn_notes = link;
803 p_insn_notes = &XEXP (link, 1);
807 *p_move_notes = NULL_RTX;
808 *p_insn_notes = NULL_RTX;
810 /* Is the insn the head of a basic block? If so extend it */
811 insn_uid = INSN_UID (insn);
812 move_uid = INSN_UID (move_insn);
813 if (insn_uid < old_max_uid)
815 bb = regmove_bb_head[insn_uid];
818 BLOCK_HEAD (bb) = move_insn;
819 regmove_bb_head[insn_uid] = -1;
823 /* Update the various register tables. */
824 dest_regno = REGNO (dest);
825 REG_N_SETS (dest_regno) ++;
826 REG_LIVE_LENGTH (dest_regno)++;
827 if (REGNO_FIRST_UID (dest_regno) == insn_uid)
828 REGNO_FIRST_UID (dest_regno) = move_uid;
830 src_regno = REGNO (src);
831 if (! find_reg_note (move_insn, REG_DEAD, src))
832 REG_LIVE_LENGTH (src_regno)++;
834 if (REGNO_FIRST_UID (src_regno) == insn_uid)
835 REGNO_FIRST_UID (src_regno) = move_uid;
837 if (REGNO_LAST_UID (src_regno) == insn_uid)
838 REGNO_LAST_UID (src_regno) = move_uid;
840 if (REGNO_LAST_NOTE_UID (src_regno) == insn_uid)
841 REGNO_LAST_NOTE_UID (src_regno) = move_uid;
846 /* Return whether REG is set in only one location, and is set to a
847 constant, but is set in a different basic block from INSN (an
848 instructions which uses REG). In this case REG is equivalent to a
849 constant, and we don't want to break that equivalence, because that
850 may increase register pressure and make reload harder. If REG is
851 set in the same basic block as INSN, we don't worry about it,
852 because we'll probably need a register anyhow (??? but what if REG
853 is used in a different basic block as well as this one?). FIRST is
854 the first insn in the function. */
857 reg_is_remote_constant_p (reg, insn, first)
864 if (REG_N_SETS (REGNO (reg)) != 1)
867 /* Look for the set. */
868 for (p = LOG_LINKS (insn); p; p = XEXP (p, 1))
872 if (REG_NOTE_KIND (p) != 0)
874 s = single_set (XEXP (p, 0));
876 && GET_CODE (SET_DEST (s)) == REG
877 && REGNO (SET_DEST (s)) == REGNO (reg))
879 /* The register is set in the same basic block. */
884 for (p = first; p && p != insn; p = NEXT_INSN (p))
888 if (GET_RTX_CLASS (GET_CODE (p)) != 'i')
892 && GET_CODE (SET_DEST (s)) == REG
893 && REGNO (SET_DEST (s)) == REGNO (reg))
895 /* This is the instruction which sets REG. If there is a
896 REG_EQUAL note, then REG is equivalent to a constant. */
897 if (find_reg_note (p, REG_EQUAL, NULL_RTX))
906 /* INSN is adding a CONST_INT to a REG. We search backwards looking for
907 another add immediate instruction with the same source and dest registers,
908 and if we find one, we change INSN to an increment, and return 1. If
909 no changes are made, we return 0.
912 (set (reg100) (plus reg1 offset1))
914 (set (reg100) (plus reg1 offset2))
916 (set (reg100) (plus reg1 offset1))
918 (set (reg100) (plus reg100 offset2-offset1)) */
920 /* ??? What does this comment mean? */
921 /* cse disrupts preincrement / postdecrement squences when it finds a
922 hard register as ultimate source, like the frame pointer. */
925 fixup_match_2 (insn, dst, src, offset, regmove_dump_file)
926 rtx insn, dst, src, offset;
927 FILE *regmove_dump_file;
929 rtx p, dst_death = 0;
930 int length, num_calls = 0;
932 /* If SRC dies in INSN, we'd have to move the death note. This is
933 considered to be very unlikely, so we just skip the optimization
935 if (find_regno_note (insn, REG_DEAD, REGNO (src)))
938 /* Scan backward to find the first instruction that sets DST. */
940 for (length = 0, p = PREV_INSN (insn); p; p = PREV_INSN (p))
944 if (GET_CODE (p) == CODE_LABEL
945 || GET_CODE (p) == JUMP_INSN)
948 /* ??? We can't scan past the end of a basic block without updating
949 the register lifetime info (REG_DEAD/basic_block_live_at_start).
950 A CALL_INSN might be the last insn of a basic block, if it is inside
951 an EH region. There is no easy way to tell, so we just always break
952 when we see a CALL_INSN if flag_exceptions is nonzero. */
953 if (flag_exceptions && GET_CODE (p) == CALL_INSN)
956 if (GET_RTX_CLASS (GET_CODE (p)) != 'i')
959 if (find_regno_note (p, REG_DEAD, REGNO (dst)))
964 pset = single_set (p);
965 if (pset && SET_DEST (pset) == dst
966 && GET_CODE (SET_SRC (pset)) == PLUS
967 && XEXP (SET_SRC (pset), 0) == src
968 && GET_CODE (XEXP (SET_SRC (pset), 1)) == CONST_INT)
970 HOST_WIDE_INT newconst
971 = INTVAL (offset) - INTVAL (XEXP (SET_SRC (pset), 1));
972 rtx add = gen_add3_insn (dst, dst, GEN_INT (newconst));
974 if (add && validate_change (insn, &PATTERN (insn), add, 0))
976 /* Remove the death note for DST from DST_DEATH. */
979 remove_death (REGNO (dst), dst_death);
980 REG_LIVE_LENGTH (REGNO (dst)) += length;
981 REG_N_CALLS_CROSSED (REGNO (dst)) += num_calls;
984 if (regmove_dump_file)
985 fprintf (regmove_dump_file,
986 "Fixed operand of insn %d.\n",
990 for (p = PREV_INSN (insn); p; p = PREV_INSN (p))
992 if (GET_CODE (p) == CODE_LABEL
993 || GET_CODE (p) == JUMP_INSN)
995 if (GET_RTX_CLASS (GET_CODE (p)) != 'i')
997 if (reg_overlap_mentioned_p (dst, PATTERN (p)))
999 if (try_auto_increment (p, insn, 0, dst, newconst, 0))
1004 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
1006 if (GET_CODE (p) == CODE_LABEL
1007 || GET_CODE (p) == JUMP_INSN)
1009 if (GET_RTX_CLASS (GET_CODE (p)) != 'i')
1011 if (reg_overlap_mentioned_p (dst, PATTERN (p)))
1013 try_auto_increment (p, insn, 0, dst, newconst, 1);
1022 if (reg_set_p (dst, PATTERN (p)))
1025 /* If we have passed a call instruction, and the
1026 pseudo-reg SRC is not already live across a call,
1027 then don't perform the optimization. */
1028 /* reg_set_p is overly conservative for CALL_INSNS, thinks that all
1029 hard regs are clobbered. Thus, we only use it for src for
1031 if (GET_CODE (p) == CALL_INSN)
1036 if (REG_N_CALLS_CROSSED (REGNO (src)) == 0)
1039 if (call_used_regs [REGNO (dst)]
1040 || find_reg_fusage (p, CLOBBER, dst))
1043 else if (reg_set_p (src, PATTERN (p)))
1051 regmove_optimize (f, nregs, regmove_dump_file)
1054 FILE *regmove_dump_file;
1056 int old_max_uid = get_max_uid ();
1061 rtx copy_src, copy_dst;
1063 /* Find out where a potential flags register is live, and so that we
1064 can supress some optimizations in those zones. */
1065 mark_flags_life_zones (discover_flags_reg ());
1067 regno_src_regno = (int *) xmalloc (sizeof *regno_src_regno * nregs);
1068 for (i = nregs; --i >= 0; ) regno_src_regno[i] = -1;
1070 regmove_bb_head = (int *) xmalloc (sizeof (int) * (old_max_uid + 1));
1071 for (i = old_max_uid; i >= 0; i--) regmove_bb_head[i] = -1;
1072 for (i = 0; i < n_basic_blocks; i++)
1073 regmove_bb_head[INSN_UID (BLOCK_HEAD (i))] = i;
1075 /* A forward/backward pass. Replace output operands with input operands. */
1077 for (pass = 0; pass <= 2; pass++)
1079 if (! flag_regmove && pass >= flag_expensive_optimizations)
1082 if (regmove_dump_file)
1083 fprintf (regmove_dump_file, "Starting %s pass...\n",
1084 pass ? "backward" : "forward");
1086 for (insn = pass ? get_last_insn () : f; insn;
1087 insn = pass ? PREV_INSN (insn) : NEXT_INSN (insn))
1090 int op_no, match_no;
1092 set = single_set (insn);
1096 if (flag_expensive_optimizations && ! pass
1097 && (GET_CODE (SET_SRC (set)) == SIGN_EXTEND
1098 || GET_CODE (SET_SRC (set)) == ZERO_EXTEND)
1099 && GET_CODE (XEXP (SET_SRC (set), 0)) == REG
1100 && GET_CODE (SET_DEST(set)) == REG)
1101 optimize_reg_copy_3 (insn, SET_DEST (set), SET_SRC (set));
1103 if (flag_expensive_optimizations && ! pass
1104 && GET_CODE (SET_SRC (set)) == REG
1105 && GET_CODE (SET_DEST(set)) == REG)
1107 /* If this is a register-register copy where SRC is not dead,
1108 see if we can optimize it. If this optimization succeeds,
1109 it will become a copy where SRC is dead. */
1110 if ((find_reg_note (insn, REG_DEAD, SET_SRC (set))
1111 || optimize_reg_copy_1 (insn, SET_DEST (set), SET_SRC (set)))
1112 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
1114 /* Similarly for a pseudo-pseudo copy when SRC is dead. */
1115 if (REGNO (SET_SRC (set)) >= FIRST_PSEUDO_REGISTER)
1116 optimize_reg_copy_2 (insn, SET_DEST (set), SET_SRC (set));
1117 if (regno_src_regno[REGNO (SET_DEST (set))] < 0
1118 && SET_SRC (set) != SET_DEST (set))
1120 int srcregno = REGNO (SET_SRC(set));
1121 if (regno_src_regno[srcregno] >= 0)
1122 srcregno = regno_src_regno[srcregno];
1123 regno_src_regno[REGNO (SET_DEST (set))] = srcregno;
1130 if (! find_matches (insn, &match))
1133 /* Now scan through the operands looking for a source operand
1134 which is supposed to match the destination operand.
1135 Then scan forward for an instruction which uses the dest
1137 If it dies there, then replace the dest in both operands with
1138 the source operand. */
1140 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1142 rtx src, dst, src_subreg;
1143 enum reg_class src_class, dst_class;
1145 match_no = match.with[op_no];
1147 /* Nothing to do if the two operands aren't supposed to match. */
1151 src = recog_data.operand[op_no];
1152 dst = recog_data.operand[match_no];
1154 if (GET_CODE (src) != REG)
1158 if (GET_CODE (dst) == SUBREG
1159 && GET_MODE_SIZE (GET_MODE (dst))
1160 >= GET_MODE_SIZE (GET_MODE (SUBREG_REG (dst))))
1163 = gen_rtx_SUBREG (GET_MODE (SUBREG_REG (dst)),
1164 src, SUBREG_WORD (dst));
1165 dst = SUBREG_REG (dst);
1167 if (GET_CODE (dst) != REG
1168 || REGNO (dst) < FIRST_PSEUDO_REGISTER)
1171 if (REGNO (src) < FIRST_PSEUDO_REGISTER)
1173 if (match.commutative[op_no] < op_no)
1174 regno_src_regno[REGNO (dst)] = REGNO (src);
1178 if (REG_LIVE_LENGTH (REGNO (src)) < 0)
1181 /* op_no/src must be a read-only operand, and
1182 match_operand/dst must be a write-only operand. */
1183 if (match.use[op_no] != READ
1184 || match.use[match_no] != WRITE)
1187 if (match.early_clobber[match_no]
1188 && count_occurrences (PATTERN (insn), src) > 1)
1191 /* Make sure match_operand is the destination. */
1192 if (recog_data.operand[match_no] != SET_DEST (set))
1195 /* If the operands already match, then there is nothing to do. */
1196 if (operands_match_p (src, dst))
1199 /* But in the commutative case, we might find a better match. */
1200 if (match.commutative[op_no] >= 0)
1202 rtx comm = recog_data.operand[match.commutative[op_no]];
1203 if (operands_match_p (comm, dst)
1204 && (replacement_quality (comm)
1205 >= replacement_quality (src)))
1209 src_class = reg_preferred_class (REGNO (src));
1210 dst_class = reg_preferred_class (REGNO (dst));
1211 if (! regclass_compatible_p (src_class, dst_class))
1214 if (fixup_match_1 (insn, set, src, src_subreg, dst, pass,
1222 /* A backward pass. Replace input operands with output operands. */
1224 if (regmove_dump_file)
1225 fprintf (regmove_dump_file, "Starting backward pass...\n");
1227 for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
1229 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
1231 int op_no, match_no;
1234 if (! find_matches (insn, &match))
1237 /* Now scan through the operands looking for a destination operand
1238 which is supposed to match a source operand.
1239 Then scan backward for an instruction which sets the source
1240 operand. If safe, then replace the source operand with the
1241 dest operand in both instructions. */
1243 copy_src = NULL_RTX;
1244 copy_dst = NULL_RTX;
1245 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1247 rtx set, p, src, dst;
1248 rtx src_note, dst_note;
1250 enum reg_class src_class, dst_class;
1253 match_no = match.with[op_no];
1255 /* Nothing to do if the two operands aren't supposed to match. */
1259 dst = recog_data.operand[match_no];
1260 src = recog_data.operand[op_no];
1262 if (GET_CODE (src) != REG)
1265 if (GET_CODE (dst) != REG
1266 || REGNO (dst) < FIRST_PSEUDO_REGISTER
1267 || REG_LIVE_LENGTH (REGNO (dst)) < 0)
1270 /* If the operands already match, then there is nothing to do. */
1271 if (operands_match_p (src, dst))
1274 if (match.commutative[op_no] >= 0)
1276 rtx comm = recog_data.operand[match.commutative[op_no]];
1277 if (operands_match_p (comm, dst))
1281 set = single_set (insn);
1285 /* match_no/dst must be a write-only operand, and
1286 operand_operand/src must be a read-only operand. */
1287 if (match.use[op_no] != READ
1288 || match.use[match_no] != WRITE)
1291 if (match.early_clobber[match_no]
1292 && count_occurrences (PATTERN (insn), src) > 1)
1295 /* Make sure match_no is the destination. */
1296 if (recog_data.operand[match_no] != SET_DEST (set))
1299 if (REGNO (src) < FIRST_PSEUDO_REGISTER)
1301 if (GET_CODE (SET_SRC (set)) == PLUS
1302 && GET_CODE (XEXP (SET_SRC (set), 1)) == CONST_INT
1303 && XEXP (SET_SRC (set), 0) == src
1304 && fixup_match_2 (insn, dst, src,
1305 XEXP (SET_SRC (set), 1),
1310 src_class = reg_preferred_class (REGNO (src));
1311 dst_class = reg_preferred_class (REGNO (dst));
1312 if (! regclass_compatible_p (src_class, dst_class))
1322 /* Can not modify an earlier insn to set dst if this insn
1323 uses an old value in the source. */
1324 if (reg_overlap_mentioned_p (dst, SET_SRC (set)))
1334 if (! (src_note = find_reg_note (insn, REG_DEAD, src)))
1345 /* If src is set once in a different basic block,
1346 and is set equal to a constant, then do not use
1347 it for this optimization, as this would make it
1348 no longer equivalent to a constant. */
1350 if (reg_is_remote_constant_p (src, insn, f))
1361 if (regmove_dump_file)
1362 fprintf (regmove_dump_file,
1363 "Could fix operand %d of insn %d matching operand %d.\n",
1364 op_no, INSN_UID (insn), match_no);
1366 /* Scan backward to find the first instruction that uses
1367 the input operand. If the operand is set here, then
1368 replace it in both instructions with match_no. */
1370 for (length = 0, p = PREV_INSN (insn); p; p = PREV_INSN (p))
1374 if (GET_CODE (p) == CODE_LABEL
1375 || GET_CODE (p) == JUMP_INSN)
1378 /* ??? We can't scan past the end of a basic block without
1379 updating the register lifetime info
1380 (REG_DEAD/basic_block_live_at_start).
1381 A CALL_INSN might be the last insn of a basic block, if
1382 it is inside an EH region. There is no easy way to tell,
1383 so we just always break when we see a CALL_INSN if
1384 flag_exceptions is nonzero. */
1385 if (flag_exceptions && GET_CODE (p) == CALL_INSN)
1388 if (GET_RTX_CLASS (GET_CODE (p)) != 'i')
1393 /* ??? See if all of SRC is set in P. This test is much
1394 more conservative than it needs to be. */
1395 pset = single_set (p);
1396 if (pset && SET_DEST (pset) == src)
1398 /* We use validate_replace_rtx, in case there
1399 are multiple identical source operands. All of
1400 them have to be changed at the same time. */
1401 if (validate_replace_rtx (src, dst, insn))
1403 if (validate_change (p, &SET_DEST (pset),
1408 /* Change all source operands back.
1409 This modifies the dst as a side-effect. */
1410 validate_replace_rtx (dst, src, insn);
1411 /* Now make sure the dst is right. */
1412 validate_change (insn,
1413 recog_data.operand_loc[match_no],
1420 if (reg_overlap_mentioned_p (src, PATTERN (p))
1421 || reg_overlap_mentioned_p (dst, PATTERN (p)))
1424 /* If we have passed a call instruction, and the
1425 pseudo-reg DST is not already live across a call,
1426 then don't perform the optimization. */
1427 if (GET_CODE (p) == CALL_INSN)
1431 if (REG_N_CALLS_CROSSED (REGNO (dst)) == 0)
1440 /* Remove the death note for SRC from INSN. */
1441 remove_note (insn, src_note);
1442 /* Move the death note for SRC to P if it is used
1444 if (reg_overlap_mentioned_p (src, PATTERN (p)))
1446 XEXP (src_note, 1) = REG_NOTES (p);
1447 REG_NOTES (p) = src_note;
1449 /* If there is a REG_DEAD note for DST on P, then remove
1450 it, because DST is now set there. */
1451 if ((dst_note = find_reg_note (p, REG_DEAD, dst)))
1452 remove_note (p, dst_note);
1454 dstno = REGNO (dst);
1455 srcno = REGNO (src);
1457 REG_N_SETS (dstno)++;
1458 REG_N_SETS (srcno)--;
1460 REG_N_CALLS_CROSSED (dstno) += num_calls;
1461 REG_N_CALLS_CROSSED (srcno) -= num_calls;
1463 REG_LIVE_LENGTH (dstno) += length;
1464 if (REG_LIVE_LENGTH (srcno) >= 0)
1466 REG_LIVE_LENGTH (srcno) -= length;
1467 /* REG_LIVE_LENGTH is only an approximation after
1468 combine if sched is not run, so make sure that we
1469 still have a reasonable value. */
1470 if (REG_LIVE_LENGTH (srcno) < 2)
1471 REG_LIVE_LENGTH (srcno) = 2;
1474 if (regmove_dump_file)
1475 fprintf (regmove_dump_file,
1476 "Fixed operand %d of insn %d matching operand %d.\n",
1477 op_no, INSN_UID (insn), match_no);
1483 /* If we weren't able to replace any of the alternatives, try an
1484 alternative appoach of copying the source to the destination. */
1485 if (!success && copy_src != NULL_RTX)
1486 copy_src_to_dest (insn, copy_src, copy_dst, old_max_uid);
1491 /* In fixup_match_1, some insns may have been inserted after basic block
1492 ends. Fix that here. */
1493 for (i = 0; i < n_basic_blocks; i++)
1495 rtx end = BLOCK_END (i);
1497 rtx next = NEXT_INSN (new);
1498 while (next != 0 && INSN_UID (next) >= old_max_uid
1499 && (i == n_basic_blocks - 1 || BLOCK_HEAD (i + 1) != next))
1500 new = next, next = NEXT_INSN (new);
1501 BLOCK_END (i) = new;
1506 free (regno_src_regno);
1507 free (regmove_bb_head);
1510 /* Returns nonzero if INSN's pattern has matching constraints for any operand.
1511 Returns 0 if INSN can't be recognized, or if the alternative can't be
1514 Initialize the info in MATCHP based on the constraints. */
1517 find_matches (insn, matchp)
1519 struct match *matchp;
1521 int likely_spilled[MAX_RECOG_OPERANDS];
1523 int any_matches = 0;
1525 extract_insn (insn);
1526 if (! constrain_operands (0))
1529 /* Must initialize this before main loop, because the code for
1530 the commutative case may set matches for operands other than
1532 for (op_no = recog_data.n_operands; --op_no >= 0; )
1533 matchp->with[op_no] = matchp->commutative[op_no] = -1;
1535 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1541 p = recog_data.constraints[op_no];
1543 likely_spilled[op_no] = 0;
1544 matchp->use[op_no] = READ;
1545 matchp->early_clobber[op_no] = 0;
1547 matchp->use[op_no] = WRITE;
1549 matchp->use[op_no] = READWRITE;
1551 for (;*p && i < which_alternative; p++)
1555 while ((c = *p++) != '\0' && c != ',')
1563 matchp->early_clobber[op_no] = 1;
1566 matchp->commutative[op_no] = op_no + 1;
1567 matchp->commutative[op_no + 1] = op_no;
1569 case '0': case '1': case '2': case '3': case '4':
1570 case '5': case '6': case '7': case '8': case '9':
1572 if (c < op_no && likely_spilled[(unsigned char) c])
1574 matchp->with[op_no] = c;
1576 if (matchp->commutative[op_no] >= 0)
1577 matchp->with[matchp->commutative[op_no]] = c;
1579 case 'a': case 'b': case 'c': case 'd': case 'e': case 'f': case 'h':
1580 case 'j': case 'k': case 'l': case 'p': case 'q': case 't': case 'u':
1581 case 'v': case 'w': case 'x': case 'y': case 'z': case 'A': case 'B':
1582 case 'C': case 'D': case 'W': case 'Y': case 'Z':
1583 if (CLASS_LIKELY_SPILLED_P (REG_CLASS_FROM_LETTER ((unsigned char)c)))
1584 likely_spilled[op_no] = 1;
1591 /* Try to replace output operand DST in SET, with input operand SRC. SET is
1592 the only set in INSN. INSN has just been recognized and constrained.
1593 SRC is operand number OPERAND_NUMBER in INSN.
1594 DST is operand number MATCH_NUMBER in INSN.
1595 If BACKWARD is nonzero, we have been called in a backward pass.
1596 Return nonzero for success. */
1598 fixup_match_1 (insn, set, src, src_subreg, dst, backward, operand_number,
1599 match_number, regmove_dump_file)
1600 rtx insn, set, src, src_subreg, dst;
1601 int backward, operand_number, match_number;
1602 FILE *regmove_dump_file;
1605 rtx post_inc = 0, post_inc_set = 0, search_end = 0;
1607 int num_calls = 0, s_num_calls = 0;
1608 enum rtx_code code = NOTE;
1609 HOST_WIDE_INT insn_const = 0, newconst;
1610 rtx overlap = 0; /* need to move insn ? */
1611 rtx src_note = find_reg_note (insn, REG_DEAD, src), dst_note = NULL_RTX;
1612 int length, s_length;
1614 /* If SRC is marked as unchanging, we may not change it.
1615 ??? Maybe we could get better code by removing the unchanging bit
1616 instead, and changing it back if we don't succeed? */
1617 if (RTX_UNCHANGING_P (src))
1622 /* Look for (set (regX) (op regA constX))
1623 (set (regY) (op regA constY))
1625 (set (regA) (op regA constX)).
1626 (set (regY) (op regA constY-constX)).
1627 This works for add and shift operations, if
1628 regA is dead after or set by the second insn. */
1630 code = GET_CODE (SET_SRC (set));
1631 if ((code == PLUS || code == LSHIFTRT
1632 || code == ASHIFT || code == ASHIFTRT)
1633 && XEXP (SET_SRC (set), 0) == src
1634 && GET_CODE (XEXP (SET_SRC (set), 1)) == CONST_INT)
1635 insn_const = INTVAL (XEXP (SET_SRC (set), 1));
1636 else if (! stable_and_no_regs_but_for_p (SET_SRC (set), src, dst))
1639 /* We might find a src_note while scanning. */
1643 if (regmove_dump_file)
1644 fprintf (regmove_dump_file,
1645 "Could fix operand %d of insn %d matching operand %d.\n",
1646 operand_number, INSN_UID (insn), match_number);
1648 /* If SRC is equivalent to a constant set in a different basic block,
1649 then do not use it for this optimization. We want the equivalence
1650 so that if we have to reload this register, we can reload the
1651 constant, rather than extending the lifespan of the register. */
1652 if (reg_is_remote_constant_p (src, insn, get_insns ()))
1655 /* Scan forward to find the next instruction that
1656 uses the output operand. If the operand dies here,
1657 then replace it in both instructions with
1660 for (length = s_length = 0, p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
1662 if (GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN)
1665 /* ??? We can't scan past the end of a basic block without updating
1666 the register lifetime info (REG_DEAD/basic_block_live_at_start).
1667 A CALL_INSN might be the last insn of a basic block, if it is
1668 inside an EH region. There is no easy way to tell, so we just
1669 always break when we see a CALL_INSN if flag_exceptions is nonzero. */
1670 if (flag_exceptions && GET_CODE (p) == CALL_INSN)
1673 if (GET_RTX_CLASS (GET_CODE (p)) != 'i')
1680 if (reg_set_p (src, p) || reg_set_p (dst, p)
1681 || (GET_CODE (PATTERN (p)) == USE
1682 && reg_overlap_mentioned_p (src, XEXP (PATTERN (p), 0))))
1685 /* See if all of DST dies in P. This test is
1686 slightly more conservative than it needs to be. */
1687 if ((dst_note = find_regno_note (p, REG_DEAD, REGNO (dst)))
1688 && (GET_MODE (XEXP (dst_note, 0)) == GET_MODE (dst)))
1690 /* If we would be moving INSN, check that we won't move it
1691 into the shadow of a live a live flags register. */
1692 /* ??? We only try to move it in front of P, although
1693 we could move it anywhere between OVERLAP and P. */
1694 if (overlap && GET_MODE (PREV_INSN (p)) != VOIDmode)
1700 rtx set2 = NULL_RTX;
1702 /* If an optimization is done, the value of SRC while P
1703 is executed will be changed. Check that this is OK. */
1704 if (reg_overlap_mentioned_p (src, PATTERN (p)))
1706 for (q = p; q; q = NEXT_INSN (q))
1708 if (GET_CODE (q) == CODE_LABEL || GET_CODE (q) == JUMP_INSN)
1714 /* ??? We can't scan past the end of a basic block without
1715 updating the register lifetime info
1716 (REG_DEAD/basic_block_live_at_start).
1717 A CALL_INSN might be the last insn of a basic block, if
1718 it is inside an EH region. There is no easy way to tell,
1719 so we just always break when we see a CALL_INSN if
1720 flag_exceptions is nonzero. */
1721 if (flag_exceptions && GET_CODE (q) == CALL_INSN)
1727 if (GET_RTX_CLASS (GET_CODE (q)) != 'i')
1729 if (reg_overlap_mentioned_p (src, PATTERN (q))
1730 || reg_set_p (src, q))
1734 set2 = single_set (q);
1735 if (! q || ! set2 || GET_CODE (SET_SRC (set2)) != code
1736 || XEXP (SET_SRC (set2), 0) != src
1737 || GET_CODE (XEXP (SET_SRC (set2), 1)) != CONST_INT
1738 || (SET_DEST (set2) != src
1739 && ! find_reg_note (q, REG_DEAD, src)))
1741 /* If this is a PLUS, we can still save a register by doing
1744 src -= insn_const; .
1745 This also gives opportunities for subsequent
1746 optimizations in the backward pass, so do it there. */
1747 if (code == PLUS && backward
1748 /* Don't do this if we can likely tie DST to SET_DEST
1749 of P later; we can't do this tying here if we got a
1751 && ! (dst_note && ! REG_N_CALLS_CROSSED (REGNO (dst))
1753 && GET_CODE (SET_DEST (single_set (p))) == REG
1754 && (REGNO (SET_DEST (single_set (p)))
1755 < FIRST_PSEUDO_REGISTER))
1756 /* We may only emit an insn directly after P if we
1757 are not in the shadow of a live flags register. */
1758 && GET_MODE (p) == VOIDmode)
1763 newconst = -insn_const;
1771 newconst = INTVAL (XEXP (SET_SRC (set2), 1)) - insn_const;
1772 /* Reject out of range shifts. */
1776 >= GET_MODE_BITSIZE (GET_MODE (SET_SRC (set2))))))
1781 if (SET_DEST (set2) != src)
1782 post_inc_set = set2;
1785 /* We use 1 as last argument to validate_change so that all
1786 changes are accepted or rejected together by apply_change_group
1787 when it is called by validate_replace_rtx . */
1788 validate_change (q, &XEXP (SET_SRC (set2), 1),
1789 GEN_INT (newconst), 1);
1791 validate_change (insn, recog_data.operand_loc[match_number], src, 1);
1792 if (validate_replace_rtx (dst, src_subreg, p))
1797 if (reg_overlap_mentioned_p (dst, PATTERN (p)))
1799 if (! src_note && reg_overlap_mentioned_p (src, PATTERN (p)))
1801 /* INSN was already checked to be movable wrt. the registers that it
1802 sets / uses when we found no REG_DEAD note for src on it, but it
1803 still might clobber the flags register. We'll have to check that
1804 we won't insert it into the shadow of a live flags register when
1805 we finally know where we are to move it. */
1807 src_note = find_reg_note (p, REG_DEAD, src);
1810 /* If we have passed a call instruction, and the pseudo-reg SRC is not
1811 already live across a call, then don't perform the optimization. */
1812 if (GET_CODE (p) == CALL_INSN)
1814 if (REG_N_CALLS_CROSSED (REGNO (src)) == 0)
1828 /* Remove the death note for DST from P. */
1829 remove_note (p, dst_note);
1832 post_inc = emit_insn_after (copy_rtx (PATTERN (insn)), p);
1833 if ((HAVE_PRE_INCREMENT || HAVE_PRE_DECREMENT)
1835 && try_auto_increment (search_end, post_inc, 0, src, newconst, 1))
1837 validate_change (insn, &XEXP (SET_SRC (set), 1), GEN_INT (insn_const), 0);
1838 REG_N_SETS (REGNO (src))++;
1839 REG_LIVE_LENGTH (REGNO (src))++;
1843 /* The lifetime of src and dest overlap,
1844 but we can change this by moving insn. */
1845 rtx pat = PATTERN (insn);
1847 remove_note (overlap, src_note);
1848 if ((HAVE_POST_INCREMENT || HAVE_POST_DECREMENT)
1850 && try_auto_increment (overlap, insn, 0, src, insn_const, 0))
1854 rtx notes = REG_NOTES (insn);
1856 emit_insn_after_with_line_notes (pat, PREV_INSN (p), insn);
1857 PUT_CODE (insn, NOTE);
1858 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
1859 NOTE_SOURCE_FILE (insn) = 0;
1860 /* emit_insn_after_with_line_notes has no
1861 return value, so search for the new insn. */
1863 while (GET_RTX_CLASS (GET_CODE (insn)) != 'i'
1864 || PATTERN (insn) != pat)
1865 insn = PREV_INSN (insn);
1867 REG_NOTES (insn) = notes;
1870 /* Sometimes we'd generate src = const; src += n;
1871 if so, replace the instruction that set src
1872 in the first place. */
1874 if (! overlap && (code == PLUS || code == MINUS))
1876 rtx note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
1877 rtx q, set2 = NULL_RTX;
1878 int num_calls2 = 0, s_length2 = 0;
1880 if (note && CONSTANT_P (XEXP (note, 0)))
1882 for (q = PREV_INSN (insn); q; q = PREV_INSN(q))
1884 if (GET_CODE (q) == CODE_LABEL || GET_CODE (q) == JUMP_INSN)
1890 /* ??? We can't scan past the end of a basic block without
1891 updating the register lifetime info
1892 (REG_DEAD/basic_block_live_at_start).
1893 A CALL_INSN might be the last insn of a basic block, if
1894 it is inside an EH region. There is no easy way to tell,
1895 so we just always break when we see a CALL_INSN if
1896 flag_exceptions is nonzero. */
1897 if (flag_exceptions && GET_CODE (q) == CALL_INSN)
1903 if (GET_RTX_CLASS (GET_CODE (q)) != 'i')
1906 if (reg_set_p (src, q))
1908 set2 = single_set (q);
1911 if (reg_overlap_mentioned_p (src, PATTERN (q)))
1916 if (GET_CODE (p) == CALL_INSN)
1919 if (q && set2 && SET_DEST (set2) == src && CONSTANT_P (SET_SRC (set2))
1920 && validate_change (insn, &SET_SRC (set), XEXP (note, 0), 0))
1923 NOTE_LINE_NUMBER (q) = NOTE_INSN_DELETED;
1924 NOTE_SOURCE_FILE (q) = 0;
1925 REG_N_SETS (REGNO (src))--;
1926 REG_N_CALLS_CROSSED (REGNO (src)) -= num_calls2;
1927 REG_LIVE_LENGTH (REGNO (src)) -= s_length2;
1933 if ((HAVE_PRE_INCREMENT || HAVE_PRE_DECREMENT)
1934 && (code == PLUS || code == MINUS) && insn_const
1935 && try_auto_increment (p, insn, 0, src, insn_const, 1))
1937 else if ((HAVE_POST_INCREMENT || HAVE_POST_DECREMENT)
1939 && try_auto_increment (p, post_inc, post_inc_set, src, newconst, 0))
1941 /* If post_inc still prevails, try to find an
1942 insn where it can be used as a pre-in/decrement.
1943 If code is MINUS, this was already tried. */
1944 if (post_inc && code == PLUS
1945 /* Check that newconst is likely to be usable
1946 in a pre-in/decrement before starting the search. */
1947 && ((HAVE_PRE_INCREMENT && newconst > 0 && newconst <= MOVE_MAX)
1948 || (HAVE_PRE_DECREMENT && newconst < 0 && newconst >= -MOVE_MAX))
1949 && exact_log2 (newconst))
1953 inc_dest = post_inc_set ? SET_DEST (post_inc_set) : src;
1954 for (q = post_inc; (q = NEXT_INSN (q)); )
1956 if (GET_CODE (q) == CODE_LABEL || GET_CODE (q) == JUMP_INSN)
1959 /* ??? We can't scan past the end of a basic block without updating
1960 the register lifetime info (REG_DEAD/basic_block_live_at_start).
1961 A CALL_INSN might be the last insn of a basic block, if it
1962 is inside an EH region. There is no easy way to tell so we
1963 just always break when we see a CALL_INSN if flag_exceptions
1965 if (flag_exceptions && GET_CODE (q) == CALL_INSN)
1968 if (GET_RTX_CLASS (GET_CODE (q)) != 'i')
1970 if (src != inc_dest && (reg_overlap_mentioned_p (src, PATTERN (q))
1971 || reg_set_p (src, q)))
1973 if (reg_set_p (inc_dest, q))
1975 if (reg_overlap_mentioned_p (inc_dest, PATTERN (q)))
1977 try_auto_increment (q, post_inc,
1978 post_inc_set, inc_dest, newconst, 1);
1983 /* Move the death note for DST to INSN if it is used
1985 if (reg_overlap_mentioned_p (dst, PATTERN (insn)))
1987 XEXP (dst_note, 1) = REG_NOTES (insn);
1988 REG_NOTES (insn) = dst_note;
1993 /* Move the death note for SRC from INSN to P. */
1995 remove_note (insn, src_note);
1996 XEXP (src_note, 1) = REG_NOTES (p);
1997 REG_NOTES (p) = src_note;
1999 REG_N_CALLS_CROSSED (REGNO (src)) += s_num_calls;
2002 REG_N_SETS (REGNO (src))++;
2003 REG_N_SETS (REGNO (dst))--;
2005 REG_N_CALLS_CROSSED (REGNO (dst)) -= num_calls;
2007 REG_LIVE_LENGTH (REGNO (src)) += s_length;
2008 if (REG_LIVE_LENGTH (REGNO (dst)) >= 0)
2010 REG_LIVE_LENGTH (REGNO (dst)) -= length;
2011 /* REG_LIVE_LENGTH is only an approximation after
2012 combine if sched is not run, so make sure that we
2013 still have a reasonable value. */
2014 if (REG_LIVE_LENGTH (REGNO (dst)) < 2)
2015 REG_LIVE_LENGTH (REGNO (dst)) = 2;
2017 if (regmove_dump_file)
2018 fprintf (regmove_dump_file,
2019 "Fixed operand %d of insn %d matching operand %d.\n",
2020 operand_number, INSN_UID (insn), match_number);
2025 /* return nonzero if X is stable and mentions no regsiters but for
2026 mentioning SRC or mentioning / changing DST . If in doubt, presume
2028 The rationale is that we want to check if we can move an insn easily
2029 while just paying attention to SRC and DST. A register is considered
2030 stable if it has the RTX_UNCHANGING_P bit set, but that would still
2031 leave the burden to update REG_DEAD / REG_UNUSED notes, so we don't
2032 want any registers but SRC and DST. */
2034 stable_and_no_regs_but_for_p (x, src, dst)
2037 RTX_CODE code = GET_CODE (x);
2038 switch (GET_RTX_CLASS (code))
2040 case '<': case '1': case 'c': case '2': case 'b': case '3':
2043 const char *fmt = GET_RTX_FORMAT (code);
2044 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2046 && ! stable_and_no_regs_but_for_p (XEXP (x, i), src, dst))
2052 return x == src || x == dst;
2053 /* If this is a MEM, look inside - there might be a register hidden in
2054 the address of an unchanging MEM. */
2056 && ! stable_and_no_regs_but_for_p (XEXP (x, 0), src, dst))
2060 return ! rtx_unstable_p (x);
2064 /* Track stack adjustments and stack memory references. Attempt to
2065 reduce the number of stack adjustments by back-propogating across
2066 the memory references.
2068 This is intended primarily for use with targets that do not define
2069 ACCUMULATE_OUTGOING_ARGS. It is of significantly more value to
2070 targets that define PREFERRED_STACK_BOUNDARY more aligned than
2071 STACK_BOUNDARY (e.g. x86), or if not all registers can be pushed
2072 (e.g. x86 fp regs) which would ordinarily have to be implemented
2073 as a sub/mov pair due to restrictions in calls.c.
2075 Propogation stops when any of the insns that need adjusting are
2076 (a) no longer valid because we've exceeded their range, (b) a
2077 non-trivial push instruction, or (c) a call instruction.
2079 Restriction B is based on the assumption that push instructions
2080 are smaller or faster. If a port really wants to remove all
2081 pushes, it should have defined ACCUMULATE_OUTGOING_ARGS. The
2082 one exception that is made is for an add immediately followed
2085 /* This structure records stack memory references between stack adjusting
2090 HOST_WIDE_INT sp_offset;
2092 struct csa_memlist *next;
2095 static int stack_memref_p PARAMS ((rtx));
2096 static rtx single_set_for_csa PARAMS ((rtx));
2097 static void free_csa_memlist PARAMS ((struct csa_memlist *));
2098 static struct csa_memlist *record_one_stack_memref
2099 PARAMS ((rtx, rtx, struct csa_memlist *));
2100 static int try_apply_stack_adjustment
2101 PARAMS ((rtx, struct csa_memlist *, HOST_WIDE_INT, HOST_WIDE_INT));
2102 static void combine_stack_adjustments_for_block PARAMS ((basic_block));
2105 /* Main entry point for stack adjustment combination. */
2108 combine_stack_adjustments ()
2112 for (i = 0; i < n_basic_blocks; ++i)
2113 combine_stack_adjustments_for_block (BASIC_BLOCK (i));
2116 /* Recognize a MEM of the form (sp) or (plus sp const). */
2119 stack_memref_p (mem)
2122 return (GET_CODE (mem) == MEM
2123 && (XEXP (mem, 0) == stack_pointer_rtx
2124 || (GET_CODE (XEXP (mem, 0)) == PLUS
2125 && XEXP (XEXP (mem, 0), 0) == stack_pointer_rtx
2126 && GET_CODE (XEXP (XEXP (mem, 0), 0)) == CONST_INT)));
2129 /* Recognize either normal single_set or the hack in i386.md for
2130 tying fp and sp adjustments. */
2133 single_set_for_csa (insn)
2137 rtx tmp = single_set (insn);
2141 if (GET_CODE (insn) != INSN
2142 || GET_CODE (PATTERN (insn)) != PARALLEL)
2145 tmp = PATTERN (insn);
2146 if (GET_CODE (XVECEXP (tmp, 0, 0)) != SET)
2149 for (i = 1; i < XVECLEN (tmp, 0); ++i)
2151 rtx this = XVECEXP (tmp, 0, i);
2153 /* The special case is allowing a no-op set. */
2154 if (GET_CODE (this) == SET
2155 && SET_SRC (this) == SET_DEST (this))
2157 else if (GET_CODE (this) != CLOBBER
2158 && GET_CODE (this) != USE)
2162 return XVECEXP (tmp, 0, 0);
2165 /* Free the list of csa_memlist nodes. */
2168 free_csa_memlist (memlist)
2169 struct csa_memlist *memlist;
2171 struct csa_memlist *next;
2172 for (; memlist ; memlist = next)
2174 next = memlist->next;
2179 /* Create a new csa_memlist node from the given memory reference.
2180 It is already known that the memory is stack_memref_p. */
2182 static struct csa_memlist *
2183 record_one_stack_memref (insn, mem, next_memlist)
2185 struct csa_memlist *next_memlist;
2187 struct csa_memlist *ml;
2189 ml = (struct csa_memlist *) xmalloc (sizeof (*ml));
2191 if (XEXP (mem, 0) == stack_pointer_rtx)
2194 ml->sp_offset = INTVAL (XEXP (XEXP (mem, 0), 1));
2198 ml->next = next_memlist;
2203 /* Attempt to apply ADJUST to the stack adjusting insn INSN, as well
2204 as each of the memories in MEMLIST. Return true on success. */
2207 try_apply_stack_adjustment (insn, memlist, new_adjust, delta)
2209 struct csa_memlist *memlist;
2210 HOST_WIDE_INT new_adjust, delta;
2212 struct csa_memlist *ml;
2215 /* We know INSN matches single_set_for_csa, because that's what we
2216 recognized earlier. However, if INSN is not single_set, it is
2217 doing double duty as a barrier for frame pointer memory accesses,
2218 which we are not recording. Therefore, an adjust insn that is not
2219 single_set may not have a positive delta applied. */
2221 if (delta > 0 && ! single_set (insn))
2223 set = single_set_for_csa (insn);
2224 validate_change (insn, &XEXP (SET_SRC (set), 1), GEN_INT (new_adjust), 1);
2226 for (ml = memlist; ml ; ml = ml->next)
2228 HOST_WIDE_INT c = ml->sp_offset - delta;
2230 /* Don't reference memory below the stack pointer. */
2237 validate_change (ml->insn, &XEXP (ml->mem, 0),
2238 plus_constant (stack_pointer_rtx, c), 1);
2241 if (apply_change_group ())
2243 /* Succeeded. Update our knowledge of the memory references. */
2244 for (ml = memlist; ml ; ml = ml->next)
2245 ml->sp_offset -= delta;
2253 /* Subroutine of combine_stack_adjustments, called for each basic block. */
2256 combine_stack_adjustments_for_block (bb)
2259 HOST_WIDE_INT last_sp_adjust = 0;
2260 rtx last_sp_set = NULL_RTX;
2261 struct csa_memlist *memlist = NULL;
2265 for (insn = bb->head; ; insn = next)
2269 pending_delete = NULL_RTX;
2270 next = NEXT_INSN (insn);
2272 if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
2275 set = single_set_for_csa (insn);
2278 rtx dest = SET_DEST (set);
2279 rtx src = SET_SRC (set);
2281 /* Find constant additions to the stack pointer. */
2282 if (dest == stack_pointer_rtx
2283 && GET_CODE (src) == PLUS
2284 && XEXP (src, 0) == stack_pointer_rtx
2285 && GET_CODE (XEXP (src, 1)) == CONST_INT)
2287 HOST_WIDE_INT this_adjust = INTVAL (XEXP (src, 1));
2289 /* If we've not seen an adjustment previously, record
2290 it now and continue. */
2294 last_sp_adjust = this_adjust;
2298 /* If not all recorded memrefs can be adjusted, or the
2299 adjustment is now too large for a constant addition,
2300 we cannot merge the two stack adjustments. */
2301 if (! try_apply_stack_adjustment (last_sp_set, memlist,
2302 last_sp_adjust + this_adjust,
2305 free_csa_memlist (memlist);
2308 last_sp_adjust = this_adjust;
2313 pending_delete = insn;
2314 last_sp_adjust += this_adjust;
2316 /* If, by some accident, the adjustments cancel out,
2317 delete both insns and start from scratch. */
2318 if (last_sp_adjust == 0)
2320 if (last_sp_set == bb->head)
2321 bb->head = NEXT_INSN (last_sp_set);
2322 flow_delete_insn (last_sp_set);
2324 free_csa_memlist (memlist);
2326 last_sp_set = NULL_RTX;
2332 /* Find loads from stack memory and record them. */
2333 if (last_sp_set && stack_memref_p (src))
2335 memlist = record_one_stack_memref (insn, src, memlist);
2339 /* Find stores to stack memory and record them. */
2340 if (last_sp_set && stack_memref_p (dest))
2342 memlist = record_one_stack_memref (insn, dest, memlist);
2346 /* Find a predecrement of exactly the previous adjustment and
2347 turn it into a direct store. Obviously we can't do this if
2348 there were any intervening uses of the stack pointer. */
2350 && last_sp_adjust == GET_MODE_SIZE (GET_MODE (dest))
2351 && GET_CODE (dest) == MEM
2352 && GET_CODE (XEXP (dest, 0)) == PRE_DEC
2353 && XEXP (XEXP (dest, 0), 0) == stack_pointer_rtx
2354 && validate_change (insn, &SET_DEST (set),
2355 change_address (dest, VOIDmode,
2356 stack_pointer_rtx), 0))
2358 if (last_sp_set == bb->head)
2359 bb->head = NEXT_INSN (last_sp_set);
2360 flow_delete_insn (last_sp_set);
2362 free_csa_memlist (memlist);
2364 last_sp_set = NULL_RTX;
2370 /* Otherwise, we were not able to process the instruction.
2371 Do not continue collecting data across such a one. */
2373 && (GET_CODE (insn) == CALL_INSN
2374 || reg_mentioned_p (stack_pointer_rtx, PATTERN (insn))))
2376 free_csa_memlist (memlist);
2378 last_sp_set = NULL_RTX;
2383 if (insn == bb->end)
2387 flow_delete_insn (pending_delete);
2392 bb->end = PREV_INSN (pending_delete);
2393 flow_delete_insn (pending_delete);