1 /* Move registers around to reduce number of move instructions needed.
2 Copyright (C) 1987, 88, 89, 92-98, 1999 Free Software Foundation, Inc.
4 This file is part of GNU CC.
6 GNU CC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 GNU CC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GNU CC; see the file COPYING. If not, write to
18 the Free Software Foundation, 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */
22 /* This module looks for cases where matching constraints would force
23 an instruction to need a reload, and this reload would be a register
24 to register move. It then attempts to change the registers used by the
25 instruction to avoid the move instruction. */
29 #include "rtl.h" /* stdio.h must precede rtl.h for FFS. */
31 #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 PROTO((rtx, rtx, rtx));
45 static void optimize_reg_copy_2 PROTO((rtx, rtx, rtx));
46 static void optimize_reg_copy_3 PROTO((rtx, rtx, rtx));
47 static rtx gen_add3_insn PROTO((rtx, rtx, rtx));
48 static void copy_src_to_dest PROTO((rtx, rtx, rtx, int, 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 PROTO((void));
59 static void mark_flags_life_zones PROTO((rtx));
60 static void flags_set_1 PROTO((rtx, rtx));
62 static int try_auto_increment PROTO((rtx, rtx, rtx, rtx, HOST_WIDE_INT, int));
63 static int find_matches PROTO((rtx, struct match *));
64 static int fixup_match_1 PROTO((rtx, rtx, rtx, rtx, rtx, int, int, int, FILE *))
66 static int reg_is_remote_constant_p PROTO((rtx, rtx, rtx));
67 static int stable_and_no_regs_but_for_p PROTO((rtx, rtx, rtx));
68 static int regclass_compatible_p PROTO((int, int));
69 static int loop_depth;
71 /* Return non-zero if registers with CLASS1 and CLASS2 can be merged without
72 causing too much register allocation problems. */
74 regclass_compatible_p (class0, class1)
77 return (class0 == class1
78 || (reg_class_subset_p (class0, class1)
79 && ! CLASS_LIKELY_SPILLED_P (class0))
80 || (reg_class_subset_p (class1, class0)
81 && ! CLASS_LIKELY_SPILLED_P (class1)));
84 /* Generate and return an insn body to add r1 and c,
85 storing the result in r0. */
87 gen_add3_insn (r0, r1, c)
90 int icode = (int) add_optab->handlers[(int) GET_MODE (r0)].insn_code;
92 if (icode == CODE_FOR_nothing
93 || ! ((*insn_data[icode].operand[0].predicate)
94 (r0, insn_data[icode].operand[0].mode))
95 || ! ((*insn_data[icode].operand[1].predicate)
96 (r1, insn_data[icode].operand[1].mode))
97 || ! ((*insn_data[icode].operand[2].predicate)
98 (c, insn_data[icode].operand[2].mode)))
101 return (GEN_FCN (icode) (r0, r1, c));
105 /* INC_INSN is an instruction that adds INCREMENT to REG.
106 Try to fold INC_INSN as a post/pre in/decrement into INSN.
107 Iff INC_INSN_SET is nonzero, inc_insn has a destination different from src.
108 Return nonzero for success. */
110 try_auto_increment (insn, inc_insn, inc_insn_set, reg, increment, pre)
111 rtx reg, insn, inc_insn ,inc_insn_set;
112 HOST_WIDE_INT increment;
115 enum rtx_code inc_code;
117 rtx pset = single_set (insn);
120 /* Can't use the size of SET_SRC, we might have something like
121 (sign_extend:SI (mem:QI ... */
122 rtx use = find_use_as_address (pset, reg, 0);
123 if (use != 0 && use != (rtx) 1)
125 int size = GET_MODE_SIZE (GET_MODE (use));
127 || (HAVE_POST_INCREMENT
128 && pre == 0 && (inc_code = POST_INC, increment == size))
129 || (HAVE_PRE_INCREMENT
130 && pre == 1 && (inc_code = PRE_INC, increment == size))
131 || (HAVE_POST_DECREMENT
132 && pre == 0 && (inc_code = POST_DEC, increment == -size))
133 || (HAVE_PRE_DECREMENT
134 && pre == 1 && (inc_code = PRE_DEC, increment == -size))
140 &SET_SRC (inc_insn_set),
141 XEXP (SET_SRC (inc_insn_set), 0), 1);
142 validate_change (insn, &XEXP (use, 0),
143 gen_rtx_fmt_e (inc_code, Pmode, reg), 1);
144 if (apply_change_group ())
147 = gen_rtx_EXPR_LIST (REG_INC,
148 reg, REG_NOTES (insn));
151 PUT_CODE (inc_insn, NOTE);
152 NOTE_LINE_NUMBER (inc_insn) = NOTE_INSN_DELETED;
153 NOTE_SOURCE_FILE (inc_insn) = 0;
163 /* Determine if the pattern generated by add_optab has a clobber,
164 such as might be issued for a flags hard register. To make the
165 code elsewhere simpler, we handle cc0 in this same framework.
167 Return the register if one was discovered. Return NULL_RTX if
168 if no flags were found. Return pc_rtx if we got confused. */
171 discover_flags_reg ()
174 tmp = gen_rtx_REG (word_mode, 10000);
175 tmp = gen_add3_insn (tmp, tmp, GEN_INT (2));
177 /* If we get something that isn't a simple set, or a
178 [(set ..) (clobber ..)], this whole function will go wrong. */
179 if (GET_CODE (tmp) == SET)
181 else if (GET_CODE (tmp) == PARALLEL)
185 if (XVECLEN (tmp, 0) != 2)
187 tmp = XVECEXP (tmp, 0, 1);
188 if (GET_CODE (tmp) != CLOBBER)
192 /* Don't do anything foolish if the md wanted to clobber a
193 scratch or something. We only care about hard regs.
194 Moreover we don't like the notion of subregs of hard regs. */
195 if (GET_CODE (tmp) == SUBREG
196 && GET_CODE (SUBREG_REG (tmp)) == REG
197 && REGNO (SUBREG_REG (tmp)) < FIRST_PSEUDO_REGISTER)
199 found = (GET_CODE (tmp) == REG && REGNO (tmp) < FIRST_PSEUDO_REGISTER);
201 return (found ? tmp : NULL_RTX);
207 /* It is a tedious task identifying when the flags register is live and
208 when it is safe to optimize. Since we process the instruction stream
209 multiple times, locate and record these live zones by marking the
210 mode of the instructions --
212 QImode is used on the instruction at which the flags becomes live.
214 HImode is used within the range (exclusive) that the flags are
215 live. Thus the user of the flags is not marked.
217 All other instructions are cleared to VOIDmode. */
219 /* Used to communicate with flags_set_1. */
220 static rtx flags_set_1_rtx;
221 static int flags_set_1_set;
224 mark_flags_life_zones (flags)
232 /* If we found a flags register on a cc0 host, bail. */
233 if (flags == NULL_RTX)
235 else if (flags != cc0_rtx)
239 /* Simple cases first: if no flags, clear all modes. If confusing,
240 mark the entire function as being in a flags shadow. */
241 if (flags == NULL_RTX || flags == pc_rtx)
243 enum machine_mode mode = (flags ? HImode : VOIDmode);
245 for (insn = get_insns(); insn; insn = NEXT_INSN (insn))
246 PUT_MODE (insn, mode);
254 flags_regno = REGNO (flags);
255 flags_nregs = HARD_REGNO_NREGS (flags_regno, GET_MODE (flags));
257 flags_set_1_rtx = flags;
259 /* Process each basic block. */
260 for (block = n_basic_blocks - 1; block >= 0; block--)
265 insn = BLOCK_HEAD (block);
266 end = BLOCK_END (block);
268 /* Look out for the (unlikely) case of flags being live across
269 basic block boundaries. */
274 for (i = 0; i < flags_nregs; ++i)
275 live |= REGNO_REG_SET_P (BASIC_BLOCK (block)->global_live_at_start,
282 /* Process liveness in reverse order of importance --
283 alive, death, birth. This lets more important info
284 overwrite the mode of lesser info. */
286 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
289 /* In the cc0 case, death is not marked in reg notes,
290 but is instead the mere use of cc0 when it is alive. */
291 if (live && reg_mentioned_p (cc0_rtx, PATTERN (insn)))
294 /* In the hard reg case, we watch death notes. */
295 if (live && find_regno_note (insn, REG_DEAD, flags_regno))
298 PUT_MODE (insn, (live ? HImode : VOIDmode));
300 /* In either case, birth is denoted simply by it's presence
301 as the destination of a set. */
303 note_stores (PATTERN (insn), flags_set_1);
307 PUT_MODE (insn, QImode);
311 PUT_MODE (insn, (live ? HImode : VOIDmode));
315 insn = NEXT_INSN (insn);
320 /* A subroutine of mark_flags_life_zones, called through note_stores. */
326 if (GET_CODE (pat) == SET
327 && reg_overlap_mentioned_p (x, flags_set_1_rtx))
331 static int *regno_src_regno;
333 /* Indicate how good a choice REG (which appears as a source) is to replace
334 a destination register with. The higher the returned value, the better
335 the choice. The main objective is to avoid using a register that is
336 a candidate for tying to a hard register, since the output might in
337 turn be a candidate to be tied to a different hard register. */
339 replacement_quality(reg)
344 /* Bad if this isn't a register at all. */
345 if (GET_CODE (reg) != REG)
348 /* If this register is not meant to get a hard register,
349 it is a poor choice. */
350 if (REG_LIVE_LENGTH (REGNO (reg)) < 0)
353 src_regno = regno_src_regno[REGNO (reg)];
355 /* If it was not copied from another register, it is fine. */
359 /* Copied from a hard register? */
360 if (src_regno < FIRST_PSEUDO_REGISTER)
363 /* Copied from a pseudo register - not as bad as from a hard register,
364 yet still cumbersome, since the register live length will be lengthened
365 when the registers get tied. */
369 /* INSN is a copy from SRC to DEST, both registers, and SRC does not die
372 Search forward to see if SRC dies before either it or DEST is modified,
373 but don't scan past the end of a basic block. If so, we can replace SRC
374 with DEST and let SRC die in INSN.
376 This will reduce the number of registers live in that range and may enable
377 DEST to be tied to SRC, thus often saving one register in addition to a
378 register-register copy. */
381 optimize_reg_copy_1 (insn, dest, src)
389 int sregno = REGNO (src);
390 int dregno = REGNO (dest);
392 /* We don't want to mess with hard regs if register classes are small. */
394 || (SMALL_REGISTER_CLASSES
395 && (sregno < FIRST_PSEUDO_REGISTER
396 || dregno < FIRST_PSEUDO_REGISTER))
397 /* We don't see all updates to SP if they are in an auto-inc memory
398 reference, so we must disallow this optimization on them. */
399 || sregno == STACK_POINTER_REGNUM || dregno == STACK_POINTER_REGNUM)
402 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
404 if (GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN
405 || (GET_CODE (p) == NOTE
406 && (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG
407 || NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END)))
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,
466 /* We assume that a register is used exactly once per
467 insn in the REG_N_REFS updates below. If this is not
468 correct, no great harm is done.
470 Since we do not know if we will change the lifetime of
471 SREGNO or DREGNO, we must not update REG_LIVE_LENGTH
472 or REG_N_CALLS_CROSSED at this time. */
473 if (sregno >= FIRST_PSEUDO_REGISTER)
474 REG_N_REFS (sregno) -= loop_depth;
476 if (dregno >= FIRST_PSEUDO_REGISTER)
477 REG_N_REFS (dregno) += loop_depth;
481 validate_replace_rtx (dest, src, q);
486 /* For SREGNO, count the total number of insns scanned.
487 For DREGNO, count the total number of insns scanned after
488 passing the death note for DREGNO. */
493 /* If the insn in which SRC dies is a CALL_INSN, don't count it
494 as a call that has been crossed. Otherwise, count it. */
495 if (q != p && GET_CODE (q) == CALL_INSN)
497 /* Similarly, total calls for SREGNO, total calls beyond
498 the death note for DREGNO. */
504 /* If DEST dies here, remove the death note and save it for
505 later. Make sure ALL of DEST dies here; again, this is
506 overly conservative. */
508 && (dest_death = find_regno_note (q, REG_DEAD, dregno)) != 0)
510 if (GET_MODE (XEXP (dest_death, 0)) != GET_MODE (dest))
511 failed = 1, dest_death = 0;
513 remove_note (q, dest_death);
519 /* These counters need to be updated if and only if we are
520 going to move the REG_DEAD note. */
521 if (sregno >= FIRST_PSEUDO_REGISTER)
523 if (REG_LIVE_LENGTH (sregno) >= 0)
525 REG_LIVE_LENGTH (sregno) -= s_length;
526 /* REG_LIVE_LENGTH is only an approximation after
527 combine if sched is not run, so make sure that we
528 still have a reasonable value. */
529 if (REG_LIVE_LENGTH (sregno) < 2)
530 REG_LIVE_LENGTH (sregno) = 2;
533 REG_N_CALLS_CROSSED (sregno) -= s_n_calls;
536 /* Move death note of SRC from P to INSN. */
537 remove_note (p, note);
538 XEXP (note, 1) = REG_NOTES (insn);
539 REG_NOTES (insn) = note;
542 /* Put death note of DEST on P if we saw it die. */
545 XEXP (dest_death, 1) = REG_NOTES (p);
546 REG_NOTES (p) = dest_death;
548 if (dregno >= FIRST_PSEUDO_REGISTER)
550 /* If and only if we are moving the death note for DREGNO,
551 then we need to update its counters. */
552 if (REG_LIVE_LENGTH (dregno) >= 0)
553 REG_LIVE_LENGTH (dregno) += d_length;
554 REG_N_CALLS_CROSSED (dregno) += d_n_calls;
561 /* If SRC is a hard register which is set or killed in some other
562 way, we can't do this optimization. */
563 else if (sregno < FIRST_PSEUDO_REGISTER
564 && dead_or_set_p (p, src))
570 /* INSN is a copy of SRC to DEST, in which SRC dies. See if we now have
571 a sequence of insns that modify DEST followed by an insn that sets
572 SRC to DEST in which DEST dies, with no prior modification of DEST.
573 (There is no need to check if the insns in between actually modify
574 DEST. We should not have cases where DEST is not modified, but
575 the optimization is safe if no such modification is detected.)
576 In that case, we can replace all uses of DEST, starting with INSN and
577 ending with the set of SRC to DEST, with SRC. We do not do this
578 optimization if a CALL_INSN is crossed unless SRC already crosses a
579 call or if DEST dies before the copy back to SRC.
581 It is assumed that DEST and SRC are pseudos; it is too complicated to do
582 this for hard registers since the substitutions we may make might fail. */
585 optimize_reg_copy_2 (insn, dest, src)
592 int sregno = REGNO (src);
593 int dregno = REGNO (dest);
595 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
597 if (GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN
598 || (GET_CODE (p) == NOTE
599 && (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG
600 || NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END)))
603 /* ??? We can't scan past the end of a basic block without updating
604 the register lifetime info (REG_DEAD/basic_block_live_at_start).
605 A CALL_INSN might be the last insn of a basic block, if it is inside
606 an EH region. There is no easy way to tell, so we just always break
607 when we see a CALL_INSN if flag_exceptions is nonzero. */
608 if (flag_exceptions && GET_CODE (p) == CALL_INSN)
611 if (GET_RTX_CLASS (GET_CODE (p)) != 'i')
614 set = single_set (p);
615 if (set && SET_SRC (set) == dest && SET_DEST (set) == src
616 && find_reg_note (p, REG_DEAD, dest))
618 /* We can do the optimization. Scan forward from INSN again,
619 replacing regs as we go. */
621 /* Set to stop at next insn. */
622 for (q = insn; q != NEXT_INSN (p); q = NEXT_INSN (q))
623 if (GET_RTX_CLASS (GET_CODE (q)) == 'i')
625 if (reg_mentioned_p (dest, PATTERN (q)))
627 PATTERN (q) = replace_rtx (PATTERN (q), dest, src);
629 /* We assume that a register is used exactly once per
630 insn in the updates below. If this is not correct,
631 no great harm is done. */
632 REG_N_REFS (dregno) -= loop_depth;
633 REG_N_REFS (sregno) += loop_depth;
637 if (GET_CODE (q) == CALL_INSN)
639 REG_N_CALLS_CROSSED (dregno)--;
640 REG_N_CALLS_CROSSED (sregno)++;
644 remove_note (p, find_reg_note (p, REG_DEAD, dest));
645 REG_N_DEATHS (dregno)--;
646 remove_note (insn, find_reg_note (insn, REG_DEAD, src));
647 REG_N_DEATHS (sregno)--;
651 if (reg_set_p (src, p)
652 || find_reg_note (p, REG_DEAD, dest)
653 || (GET_CODE (p) == CALL_INSN && REG_N_CALLS_CROSSED (sregno) == 0))
657 /* INSN is a ZERO_EXTEND or SIGN_EXTEND of SRC to DEST.
658 Look if SRC dies there, and if it is only set once, by loading
659 it from memory. If so, try to encorporate the zero/sign extension
660 into the memory read, change SRC to the mode of DEST, and alter
661 the remaining accesses to use the appropriate SUBREG. This allows
662 SRC and DEST to be tied later. */
664 optimize_reg_copy_3 (insn, dest, src)
669 rtx src_reg = XEXP (src, 0);
670 int src_no = REGNO (src_reg);
671 int dst_no = REGNO (dest);
673 enum machine_mode old_mode;
675 if (src_no < FIRST_PSEUDO_REGISTER
676 || dst_no < FIRST_PSEUDO_REGISTER
677 || ! find_reg_note (insn, REG_DEAD, src_reg)
678 || REG_N_SETS (src_no) != 1)
680 for (p = PREV_INSN (insn); ! reg_set_p (src_reg, p); p = PREV_INSN (p))
682 if (GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN
683 || (GET_CODE (p) == NOTE
684 && (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG
685 || NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END)))
688 /* ??? We can't scan past the end of a basic block without updating
689 the register lifetime info (REG_DEAD/basic_block_live_at_start).
690 A CALL_INSN might be the last insn of a basic block, if it is inside
691 an EH region. There is no easy way to tell, so we just always break
692 when we see a CALL_INSN if flag_exceptions is nonzero. */
693 if (flag_exceptions && GET_CODE (p) == CALL_INSN)
696 if (GET_RTX_CLASS (GET_CODE (p)) != 'i')
699 if (! (set = single_set (p))
700 || GET_CODE (SET_SRC (set)) != MEM
701 || SET_DEST (set) != src_reg)
704 /* Be conserative: although this optimization is also valid for
705 volatile memory references, that could cause trouble in later passes. */
706 if (MEM_VOLATILE_P (SET_SRC (set)))
709 /* Do not use a SUBREG to truncate from one mode to another if truncation
711 if (GET_MODE_BITSIZE (GET_MODE (src_reg)) <= GET_MODE_BITSIZE (GET_MODE (src))
712 && !TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (GET_MODE (src)),
713 GET_MODE_BITSIZE (GET_MODE (src_reg))))
716 old_mode = GET_MODE (src_reg);
717 PUT_MODE (src_reg, GET_MODE (src));
718 XEXP (src, 0) = SET_SRC (set);
720 /* Include this change in the group so that it's easily undone if
721 one of the changes in the group is invalid. */
722 validate_change (p, &SET_SRC (set), src, 1);
724 /* Now walk forward making additional replacements. We want to be able
725 to undo all the changes if a later substitution fails. */
726 subreg = gen_rtx_SUBREG (old_mode, src_reg, 0);
727 while (p = NEXT_INSN (p), p != insn)
729 if (GET_RTX_CLASS (GET_CODE (p)) != 'i')
732 /* Make a tenative change. */
733 validate_replace_rtx_group (src_reg, subreg, p);
736 validate_replace_rtx_group (src, src_reg, insn);
738 /* Now see if all the changes are valid. */
739 if (! apply_change_group ())
741 /* One or more changes were no good. Back out everything. */
742 PUT_MODE (src_reg, old_mode);
743 XEXP (src, 0) = src_reg;
748 /* If we were not able to update the users of src to use dest directly, try
749 instead moving the value to dest directly before the operation. */
752 copy_src_to_dest (insn, src, dest, loop_depth, old_max_uid)
772 /* A REG_LIVE_LENGTH of -1 indicates the register is equivalent to a constant
773 or memory location and is used infrequently; a REG_LIVE_LENGTH of -2 is
774 parameter when there is no frame pointer that is not allocated a register.
775 For now, we just reject them, rather than incrementing the live length. */
777 if (GET_CODE (src) == REG
778 && REG_LIVE_LENGTH (REGNO (src)) > 0
779 && GET_CODE (dest) == REG
780 && REG_LIVE_LENGTH (REGNO (dest)) > 0
781 && (set = single_set (insn)) != NULL_RTX
782 && !reg_mentioned_p (dest, SET_SRC (set))
783 && GET_MODE (src) == GET_MODE (dest))
785 int old_num_regs = reg_rtx_no;
787 /* Generate the src->dest move. */
789 emit_move_insn (dest, src);
790 seq = gen_sequence ();
792 /* If this sequence uses new registers, we may not use it. */
793 if (old_num_regs != reg_rtx_no
794 || ! validate_replace_rtx (src, dest, insn))
796 /* We have to restore reg_rtx_no to its old value, lest
797 recompute_reg_usage will try to compute the usage of the
798 new regs, yet reg_n_info is not valid for them. */
799 reg_rtx_no = old_num_regs;
802 emit_insn_before (seq, insn);
803 move_insn = PREV_INSN (insn);
804 p_move_notes = ®_NOTES (move_insn);
805 p_insn_notes = ®_NOTES (insn);
807 /* Move any notes mentioning src to the move instruction */
808 for (link = REG_NOTES (insn); link != NULL_RTX; link = next)
810 next = XEXP (link, 1);
811 if (XEXP (link, 0) == src)
813 *p_move_notes = link;
814 p_move_notes = &XEXP (link, 1);
818 *p_insn_notes = link;
819 p_insn_notes = &XEXP (link, 1);
823 *p_move_notes = NULL_RTX;
824 *p_insn_notes = NULL_RTX;
826 /* Is the insn the head of a basic block? If so extend it */
827 insn_uid = INSN_UID (insn);
828 move_uid = INSN_UID (move_insn);
829 if (insn_uid < old_max_uid)
831 bb = regmove_bb_head[insn_uid];
834 BLOCK_HEAD (bb) = move_insn;
835 regmove_bb_head[insn_uid] = -1;
839 /* Update the various register tables. */
840 dest_regno = REGNO (dest);
841 REG_N_SETS (dest_regno) += loop_depth;
842 REG_N_REFS (dest_regno) += loop_depth;
843 REG_LIVE_LENGTH (dest_regno)++;
844 if (REGNO_FIRST_UID (dest_regno) == insn_uid)
845 REGNO_FIRST_UID (dest_regno) = move_uid;
847 src_regno = REGNO (src);
848 if (! find_reg_note (move_insn, REG_DEAD, src))
849 REG_LIVE_LENGTH (src_regno)++;
851 if (REGNO_FIRST_UID (src_regno) == insn_uid)
852 REGNO_FIRST_UID (src_regno) = move_uid;
854 if (REGNO_LAST_UID (src_regno) == insn_uid)
855 REGNO_LAST_UID (src_regno) = move_uid;
857 if (REGNO_LAST_NOTE_UID (src_regno) == insn_uid)
858 REGNO_LAST_NOTE_UID (src_regno) = move_uid;
863 /* Return whether REG is set in only one location, and is set to a
864 constant, but is set in a different basic block from INSN (an
865 instructions which uses REG). In this case REG is equivalent to a
866 constant, and we don't want to break that equivalence, because that
867 may increase register pressure and make reload harder. If REG is
868 set in the same basic block as INSN, we don't worry about it,
869 because we'll probably need a register anyhow (??? but what if REG
870 is used in a different basic block as well as this one?). FIRST is
871 the first insn in the function. */
874 reg_is_remote_constant_p (reg, insn, first)
881 if (REG_N_SETS (REGNO (reg)) != 1)
884 /* Look for the set. */
885 for (p = LOG_LINKS (insn); p; p = XEXP (p, 1))
889 if (REG_NOTE_KIND (p) != 0)
891 s = single_set (XEXP (p, 0));
893 && GET_CODE (SET_DEST (s)) == REG
894 && REGNO (SET_DEST (s)) == REGNO (reg))
896 /* The register is set in the same basic block. */
901 for (p = first; p && p != insn; p = NEXT_INSN (p))
905 if (GET_RTX_CLASS (GET_CODE (p)) != 'i')
909 && GET_CODE (SET_DEST (s)) == REG
910 && REGNO (SET_DEST (s)) == REGNO (reg))
912 /* This is the instruction which sets REG. If there is a
913 REG_EQUAL note, then REG is equivalent to a constant. */
914 if (find_reg_note (p, REG_EQUAL, NULL_RTX))
923 /* INSN is adding a CONST_INT to a REG. We search backwards looking for
924 another add immediate instruction with the same source and dest registers,
925 and if we find one, we change INSN to an increment, and return 1. If
926 no changes are made, we return 0.
929 (set (reg100) (plus reg1 offset1))
931 (set (reg100) (plus reg1 offset2))
933 (set (reg100) (plus reg1 offset1))
935 (set (reg100) (plus reg100 offset2-offset1)) */
937 /* ??? What does this comment mean? */
938 /* cse disrupts preincrement / postdecrement squences when it finds a
939 hard register as ultimate source, like the frame pointer. */
942 fixup_match_2 (insn, dst, src, offset, regmove_dump_file)
943 rtx insn, dst, src, offset;
944 FILE *regmove_dump_file;
946 rtx p, dst_death = 0;
947 int length, num_calls = 0;
949 /* If SRC dies in INSN, we'd have to move the death note. This is
950 considered to be very unlikely, so we just skip the optimization
952 if (find_regno_note (insn, REG_DEAD, REGNO (src)))
955 /* Scan backward to find the first instruction that sets DST. */
957 for (length = 0, p = PREV_INSN (insn); p; p = PREV_INSN (p))
961 if (GET_CODE (p) == CODE_LABEL
962 || GET_CODE (p) == JUMP_INSN
963 || (GET_CODE (p) == NOTE
964 && (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG
965 || NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END)))
968 /* ??? We can't scan past the end of a basic block without updating
969 the register lifetime info (REG_DEAD/basic_block_live_at_start).
970 A CALL_INSN might be the last insn of a basic block, if it is inside
971 an EH region. There is no easy way to tell, so we just always break
972 when we see a CALL_INSN if flag_exceptions is nonzero. */
973 if (flag_exceptions && GET_CODE (p) == CALL_INSN)
976 if (GET_RTX_CLASS (GET_CODE (p)) != 'i')
979 if (find_regno_note (p, REG_DEAD, REGNO (dst)))
984 pset = single_set (p);
985 if (pset && SET_DEST (pset) == dst
986 && GET_CODE (SET_SRC (pset)) == PLUS
987 && XEXP (SET_SRC (pset), 0) == src
988 && GET_CODE (XEXP (SET_SRC (pset), 1)) == CONST_INT)
990 HOST_WIDE_INT newconst
991 = INTVAL (offset) - INTVAL (XEXP (SET_SRC (pset), 1));
992 rtx add = gen_add3_insn (dst, dst, GEN_INT (newconst));
994 if (add && validate_change (insn, &PATTERN (insn), add, 0))
996 /* Remove the death note for DST from DST_DEATH. */
999 remove_death (REGNO (dst), dst_death);
1000 REG_LIVE_LENGTH (REGNO (dst)) += length;
1001 REG_N_CALLS_CROSSED (REGNO (dst)) += num_calls;
1004 REG_N_REFS (REGNO (dst)) += loop_depth;
1005 REG_N_REFS (REGNO (src)) -= loop_depth;
1007 if (regmove_dump_file)
1008 fprintf (regmove_dump_file,
1009 "Fixed operand of insn %d.\n",
1013 for (p = PREV_INSN (insn); p; p = PREV_INSN (p))
1015 if (GET_CODE (p) == CODE_LABEL
1016 || GET_CODE (p) == JUMP_INSN
1017 || (GET_CODE (p) == NOTE
1018 && (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG
1019 || NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END)))
1021 if (GET_RTX_CLASS (GET_CODE (p)) != 'i')
1023 if (reg_overlap_mentioned_p (dst, PATTERN (p)))
1025 if (try_auto_increment (p, insn, 0, dst, newconst, 0))
1030 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
1032 if (GET_CODE (p) == CODE_LABEL
1033 || GET_CODE (p) == JUMP_INSN
1034 || (GET_CODE (p) == NOTE
1035 && (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG
1036 || NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END)))
1038 if (GET_RTX_CLASS (GET_CODE (p)) != 'i')
1040 if (reg_overlap_mentioned_p (dst, PATTERN (p)))
1042 try_auto_increment (p, insn, 0, dst, newconst, 1);
1051 if (reg_set_p (dst, PATTERN (p)))
1054 /* If we have passed a call instruction, and the
1055 pseudo-reg SRC is not already live across a call,
1056 then don't perform the optimization. */
1057 /* reg_set_p is overly conservative for CALL_INSNS, thinks that all
1058 hard regs are clobbered. Thus, we only use it for src for
1060 if (GET_CODE (p) == CALL_INSN)
1065 if (REG_N_CALLS_CROSSED (REGNO (src)) == 0)
1068 if (call_used_regs [REGNO (dst)]
1069 || find_reg_fusage (p, CLOBBER, dst))
1072 else if (reg_set_p (src, PATTERN (p)))
1080 regmove_optimize (f, nregs, regmove_dump_file)
1083 FILE *regmove_dump_file;
1085 int old_max_uid = get_max_uid ();
1090 rtx copy_src, copy_dst;
1092 /* Find out where a potential flags register is live, and so that we
1093 can supress some optimizations in those zones. */
1094 mark_flags_life_zones (discover_flags_reg ());
1096 regno_src_regno = (int *)alloca (sizeof *regno_src_regno * nregs);
1097 for (i = nregs; --i >= 0; ) regno_src_regno[i] = -1;
1099 regmove_bb_head = (int *)alloca (sizeof (int) * (old_max_uid + 1));
1100 for (i = old_max_uid; i >= 0; i--) regmove_bb_head[i] = -1;
1101 for (i = 0; i < n_basic_blocks; i++)
1102 regmove_bb_head[INSN_UID (BLOCK_HEAD (i))] = i;
1104 /* A forward/backward pass. Replace output operands with input operands. */
1108 for (pass = 0; pass <= 2; pass++)
1110 if (! flag_regmove && pass >= flag_expensive_optimizations)
1113 if (regmove_dump_file)
1114 fprintf (regmove_dump_file, "Starting %s pass...\n",
1115 pass ? "backward" : "forward");
1117 for (insn = pass ? get_last_insn () : f; insn;
1118 insn = pass ? PREV_INSN (insn) : NEXT_INSN (insn))
1121 int op_no, match_no;
1123 if (GET_CODE (insn) == NOTE)
1125 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
1127 else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
1131 set = single_set (insn);
1135 if (flag_expensive_optimizations && ! pass
1136 && (GET_CODE (SET_SRC (set)) == SIGN_EXTEND
1137 || GET_CODE (SET_SRC (set)) == ZERO_EXTEND)
1138 && GET_CODE (XEXP (SET_SRC (set), 0)) == REG
1139 && GET_CODE (SET_DEST(set)) == REG)
1140 optimize_reg_copy_3 (insn, SET_DEST (set), SET_SRC (set));
1142 if (flag_expensive_optimizations && ! pass
1143 && GET_CODE (SET_SRC (set)) == REG
1144 && GET_CODE (SET_DEST(set)) == REG)
1146 /* If this is a register-register copy where SRC is not dead,
1147 see if we can optimize it. If this optimization succeeds,
1148 it will become a copy where SRC is dead. */
1149 if ((find_reg_note (insn, REG_DEAD, SET_SRC (set))
1150 || optimize_reg_copy_1 (insn, SET_DEST (set), SET_SRC (set)))
1151 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
1153 /* Similarly for a pseudo-pseudo copy when SRC is dead. */
1154 if (REGNO (SET_SRC (set)) >= FIRST_PSEUDO_REGISTER)
1155 optimize_reg_copy_2 (insn, SET_DEST (set), SET_SRC (set));
1156 if (regno_src_regno[REGNO (SET_DEST (set))] < 0
1157 && SET_SRC (set) != SET_DEST (set))
1159 int srcregno = REGNO (SET_SRC(set));
1160 if (regno_src_regno[srcregno] >= 0)
1161 srcregno = regno_src_regno[srcregno];
1162 regno_src_regno[REGNO (SET_DEST (set))] = srcregno;
1169 if (! find_matches (insn, &match))
1172 /* Now scan through the operands looking for a source operand
1173 which is supposed to match the destination operand.
1174 Then scan forward for an instruction which uses the dest
1176 If it dies there, then replace the dest in both operands with
1177 the source operand. */
1179 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1181 rtx src, dst, src_subreg;
1182 enum reg_class src_class, dst_class;
1184 match_no = match.with[op_no];
1186 /* Nothing to do if the two operands aren't supposed to match. */
1190 src = recog_data.operand[op_no];
1191 dst = recog_data.operand[match_no];
1193 if (GET_CODE (src) != REG)
1197 if (GET_CODE (dst) == SUBREG
1198 && GET_MODE_SIZE (GET_MODE (dst))
1199 >= GET_MODE_SIZE (GET_MODE (SUBREG_REG (dst))))
1202 = gen_rtx_SUBREG (GET_MODE (SUBREG_REG (dst)),
1203 src, SUBREG_WORD (dst));
1204 dst = SUBREG_REG (dst);
1206 if (GET_CODE (dst) != REG
1207 || REGNO (dst) < FIRST_PSEUDO_REGISTER)
1210 if (REGNO (src) < FIRST_PSEUDO_REGISTER)
1212 if (match.commutative[op_no] < op_no)
1213 regno_src_regno[REGNO (dst)] = REGNO (src);
1217 if (REG_LIVE_LENGTH (REGNO (src)) < 0)
1220 /* op_no/src must be a read-only operand, and
1221 match_operand/dst must be a write-only operand. */
1222 if (match.use[op_no] != READ
1223 || match.use[match_no] != WRITE)
1226 if (match.early_clobber[match_no]
1227 && count_occurrences (PATTERN (insn), src) > 1)
1230 /* Make sure match_operand is the destination. */
1231 if (recog_data.operand[match_no] != SET_DEST (set))
1234 /* If the operands already match, then there is nothing to do. */
1235 if (operands_match_p (src, dst))
1238 /* But in the commutative case, we might find a better match. */
1239 if (match.commutative[op_no] >= 0)
1241 rtx comm = recog_data.operand[match.commutative[op_no]];
1242 if (operands_match_p (comm, dst)
1243 && (replacement_quality (comm)
1244 >= replacement_quality (src)))
1248 src_class = reg_preferred_class (REGNO (src));
1249 dst_class = reg_preferred_class (REGNO (dst));
1250 if (! regclass_compatible_p (src_class, dst_class))
1253 if (fixup_match_1 (insn, set, src, src_subreg, dst, pass,
1261 /* A backward pass. Replace input operands with output operands. */
1263 if (regmove_dump_file)
1264 fprintf (regmove_dump_file, "Starting backward pass...\n");
1268 for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
1270 if (GET_CODE (insn) == NOTE)
1272 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
1274 else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
1277 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
1279 int op_no, match_no;
1282 if (! find_matches (insn, &match))
1285 /* Now scan through the operands looking for a destination operand
1286 which is supposed to match a source operand.
1287 Then scan backward for an instruction which sets the source
1288 operand. If safe, then replace the source operand with the
1289 dest operand in both instructions. */
1291 copy_src = NULL_RTX;
1292 copy_dst = NULL_RTX;
1293 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1295 rtx set, p, src, dst;
1296 rtx src_note, dst_note;
1298 enum reg_class src_class, dst_class;
1301 match_no = match.with[op_no];
1303 /* Nothing to do if the two operands aren't supposed to match. */
1307 dst = recog_data.operand[match_no];
1308 src = recog_data.operand[op_no];
1310 if (GET_CODE (src) != REG)
1313 if (GET_CODE (dst) != REG
1314 || REGNO (dst) < FIRST_PSEUDO_REGISTER
1315 || REG_LIVE_LENGTH (REGNO (dst)) < 0)
1318 /* If the operands already match, then there is nothing to do. */
1319 if (operands_match_p (src, dst))
1322 if (match.commutative[op_no] >= 0)
1324 rtx comm = recog_data.operand[match.commutative[op_no]];
1325 if (operands_match_p (comm, dst))
1329 set = single_set (insn);
1333 /* match_no/dst must be a write-only operand, and
1334 operand_operand/src must be a read-only operand. */
1335 if (match.use[op_no] != READ
1336 || match.use[match_no] != WRITE)
1339 if (match.early_clobber[match_no]
1340 && count_occurrences (PATTERN (insn), src) > 1)
1343 /* Make sure match_no is the destination. */
1344 if (recog_data.operand[match_no] != SET_DEST (set))
1347 if (REGNO (src) < FIRST_PSEUDO_REGISTER)
1349 if (GET_CODE (SET_SRC (set)) == PLUS
1350 && GET_CODE (XEXP (SET_SRC (set), 1)) == CONST_INT
1351 && XEXP (SET_SRC (set), 0) == src
1352 && fixup_match_2 (insn, dst, src,
1353 XEXP (SET_SRC (set), 1),
1358 src_class = reg_preferred_class (REGNO (src));
1359 dst_class = reg_preferred_class (REGNO (dst));
1360 if (! regclass_compatible_p (src_class, dst_class))
1370 /* Can not modify an earlier insn to set dst if this insn
1371 uses an old value in the source. */
1372 if (reg_overlap_mentioned_p (dst, SET_SRC (set)))
1382 if (! (src_note = find_reg_note (insn, REG_DEAD, src)))
1393 /* If src is set once in a different basic block,
1394 and is set equal to a constant, then do not use
1395 it for this optimization, as this would make it
1396 no longer equivalent to a constant. */
1398 if (reg_is_remote_constant_p (src, insn, f))
1409 if (regmove_dump_file)
1410 fprintf (regmove_dump_file,
1411 "Could fix operand %d of insn %d matching operand %d.\n",
1412 op_no, INSN_UID (insn), match_no);
1414 /* Scan backward to find the first instruction that uses
1415 the input operand. If the operand is set here, then
1416 replace it in both instructions with match_no. */
1418 for (length = 0, p = PREV_INSN (insn); p; p = PREV_INSN (p))
1422 if (GET_CODE (p) == CODE_LABEL
1423 || GET_CODE (p) == JUMP_INSN
1424 || (GET_CODE (p) == NOTE
1425 && (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG
1426 || NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END)))
1429 /* ??? We can't scan past the end of a basic block without
1430 updating the register lifetime info
1431 (REG_DEAD/basic_block_live_at_start).
1432 A CALL_INSN might be the last insn of a basic block, if
1433 it is inside an EH region. There is no easy way to tell,
1434 so we just always break when we see a CALL_INSN if
1435 flag_exceptions is nonzero. */
1436 if (flag_exceptions && GET_CODE (p) == CALL_INSN)
1439 if (GET_RTX_CLASS (GET_CODE (p)) != 'i')
1444 /* ??? See if all of SRC is set in P. This test is much
1445 more conservative than it needs to be. */
1446 pset = single_set (p);
1447 if (pset && SET_DEST (pset) == src)
1449 /* We use validate_replace_rtx, in case there
1450 are multiple identical source operands. All of
1451 them have to be changed at the same time. */
1452 if (validate_replace_rtx (src, dst, insn))
1454 if (validate_change (p, &SET_DEST (pset),
1459 /* Change all source operands back.
1460 This modifies the dst as a side-effect. */
1461 validate_replace_rtx (dst, src, insn);
1462 /* Now make sure the dst is right. */
1463 validate_change (insn,
1464 recog_data.operand_loc[match_no],
1471 if (reg_overlap_mentioned_p (src, PATTERN (p))
1472 || reg_overlap_mentioned_p (dst, PATTERN (p)))
1475 /* If we have passed a call instruction, and the
1476 pseudo-reg DST is not already live across a call,
1477 then don't perform the optimization. */
1478 if (GET_CODE (p) == CALL_INSN)
1482 if (REG_N_CALLS_CROSSED (REGNO (dst)) == 0)
1491 /* Remove the death note for SRC from INSN. */
1492 remove_note (insn, src_note);
1493 /* Move the death note for SRC to P if it is used
1495 if (reg_overlap_mentioned_p (src, PATTERN (p)))
1497 XEXP (src_note, 1) = REG_NOTES (p);
1498 REG_NOTES (p) = src_note;
1500 /* If there is a REG_DEAD note for DST on P, then remove
1501 it, because DST is now set there. */
1502 if ((dst_note = find_reg_note (p, REG_DEAD, dst)))
1503 remove_note (p, dst_note);
1505 dstno = REGNO (dst);
1506 srcno = REGNO (src);
1508 REG_N_SETS (dstno)++;
1509 REG_N_SETS (srcno)--;
1511 REG_N_CALLS_CROSSED (dstno) += num_calls;
1512 REG_N_CALLS_CROSSED (srcno) -= num_calls;
1514 REG_LIVE_LENGTH (dstno) += length;
1515 if (REG_LIVE_LENGTH (srcno) >= 0)
1517 REG_LIVE_LENGTH (srcno) -= length;
1518 /* REG_LIVE_LENGTH is only an approximation after
1519 combine if sched is not run, so make sure that we
1520 still have a reasonable value. */
1521 if (REG_LIVE_LENGTH (srcno) < 2)
1522 REG_LIVE_LENGTH (srcno) = 2;
1525 /* We assume that a register is used exactly once per
1526 insn in the updates above. If this is not correct,
1527 no great harm is done. */
1529 REG_N_REFS (dstno) += 2 * loop_depth;
1530 REG_N_REFS (srcno) -= 2 * loop_depth;
1532 /* If that was the only time src was set,
1533 and src was not live at the start of the
1534 function, we know that we have no more
1535 references to src; clear REG_N_REFS so it
1536 won't make reload do any work. */
1537 if (REG_N_SETS (REGNO (src)) == 0
1538 && ! regno_uninitialized (REGNO (src)))
1539 REG_N_REFS (REGNO (src)) = 0;
1541 if (regmove_dump_file)
1542 fprintf (regmove_dump_file,
1543 "Fixed operand %d of insn %d matching operand %d.\n",
1544 op_no, INSN_UID (insn), match_no);
1550 /* If we weren't able to replace any of the alternatives, try an
1551 alternative appoach of copying the source to the destination. */
1552 if (!success && copy_src != NULL_RTX)
1553 copy_src_to_dest (insn, copy_src, copy_dst, loop_depth,
1559 /* In fixup_match_1, some insns may have been inserted after basic block
1560 ends. Fix that here. */
1561 for (i = 0; i < n_basic_blocks; i++)
1563 rtx end = BLOCK_END (i);
1565 rtx next = NEXT_INSN (new);
1566 while (next != 0 && INSN_UID (next) >= old_max_uid
1567 && (i == n_basic_blocks - 1 || BLOCK_HEAD (i + 1) != next))
1568 new = next, next = NEXT_INSN (new);
1569 BLOCK_END (i) = new;
1573 /* Returns nonzero if INSN's pattern has matching constraints for any operand.
1574 Returns 0 if INSN can't be recognized, or if the alternative can't be
1577 Initialize the info in MATCHP based on the constraints. */
1580 find_matches (insn, matchp)
1582 struct match *matchp;
1584 int likely_spilled[MAX_RECOG_OPERANDS];
1586 int any_matches = 0;
1588 extract_insn (insn);
1589 if (! constrain_operands (0))
1592 /* Must initialize this before main loop, because the code for
1593 the commutative case may set matches for operands other than
1595 for (op_no = recog_data.n_operands; --op_no >= 0; )
1596 matchp->with[op_no] = matchp->commutative[op_no] = -1;
1598 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1604 p = recog_data.constraints[op_no];
1606 likely_spilled[op_no] = 0;
1607 matchp->use[op_no] = READ;
1608 matchp->early_clobber[op_no] = 0;
1610 matchp->use[op_no] = WRITE;
1612 matchp->use[op_no] = READWRITE;
1614 for (;*p && i < which_alternative; p++)
1618 while ((c = *p++) != '\0' && c != ',')
1626 matchp->early_clobber[op_no] = 1;
1629 matchp->commutative[op_no] = op_no + 1;
1630 matchp->commutative[op_no + 1] = op_no;
1632 case '0': case '1': case '2': case '3': case '4':
1633 case '5': case '6': case '7': case '8': case '9':
1635 if (c < op_no && likely_spilled[(unsigned char) c])
1637 matchp->with[op_no] = c;
1639 if (matchp->commutative[op_no] >= 0)
1640 matchp->with[matchp->commutative[op_no]] = c;
1642 case 'a': case 'b': case 'c': case 'd': case 'e': case 'f': case 'h':
1643 case 'j': case 'k': case 'l': case 'p': case 'q': case 't': case 'u':
1644 case 'v': case 'w': case 'x': case 'y': case 'z': case 'A': case 'B':
1645 case 'C': case 'D': case 'W': case 'Y': case 'Z':
1646 if (CLASS_LIKELY_SPILLED_P (REG_CLASS_FROM_LETTER ((unsigned char)c)))
1647 likely_spilled[op_no] = 1;
1654 /* Try to replace output operand DST in SET, with input operand SRC. SET is
1655 the only set in INSN. INSN has just been recognized and constrained.
1656 SRC is operand number OPERAND_NUMBER in INSN.
1657 DST is operand number MATCH_NUMBER in INSN.
1658 If BACKWARD is nonzero, we have been called in a backward pass.
1659 Return nonzero for success. */
1661 fixup_match_1 (insn, set, src, src_subreg, dst, backward, operand_number,
1662 match_number, regmove_dump_file)
1663 rtx insn, set, src, src_subreg, dst;
1664 int backward, operand_number, match_number;
1665 FILE *regmove_dump_file;
1668 rtx post_inc = 0, post_inc_set = 0, search_end = 0;
1670 int num_calls = 0, s_num_calls = 0;
1671 enum rtx_code code = NOTE;
1672 HOST_WIDE_INT insn_const, newconst;
1673 rtx overlap = 0; /* need to move insn ? */
1674 rtx src_note = find_reg_note (insn, REG_DEAD, src), dst_note;
1675 int length, s_length, true_loop_depth;
1677 /* If SRC is marked as unchanging, we may not change it.
1678 ??? Maybe we could get better code by removing the unchanging bit
1679 instead, and changing it back if we don't succeed? */
1680 if (RTX_UNCHANGING_P (src))
1685 /* Look for (set (regX) (op regA constX))
1686 (set (regY) (op regA constY))
1688 (set (regA) (op regA constX)).
1689 (set (regY) (op regA constY-constX)).
1690 This works for add and shift operations, if
1691 regA is dead after or set by the second insn. */
1693 code = GET_CODE (SET_SRC (set));
1694 if ((code == PLUS || code == LSHIFTRT
1695 || code == ASHIFT || code == ASHIFTRT)
1696 && XEXP (SET_SRC (set), 0) == src
1697 && GET_CODE (XEXP (SET_SRC (set), 1)) == CONST_INT)
1698 insn_const = INTVAL (XEXP (SET_SRC (set), 1));
1699 else if (! stable_and_no_regs_but_for_p (SET_SRC (set), src, dst))
1702 /* We might find a src_note while scanning. */
1706 if (regmove_dump_file)
1707 fprintf (regmove_dump_file,
1708 "Could fix operand %d of insn %d matching operand %d.\n",
1709 operand_number, INSN_UID (insn), match_number);
1711 /* If SRC is equivalent to a constant set in a different basic block,
1712 then do not use it for this optimization. We want the equivalence
1713 so that if we have to reload this register, we can reload the
1714 constant, rather than extending the lifespan of the register. */
1715 if (reg_is_remote_constant_p (src, insn, get_insns ()))
1718 /* Scan forward to find the next instruction that
1719 uses the output operand. If the operand dies here,
1720 then replace it in both instructions with
1723 for (length = s_length = 0, p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
1725 if (GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN
1726 || (GET_CODE (p) == NOTE
1727 && (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG
1728 || NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END)))
1731 /* ??? We can't scan past the end of a basic block without updating
1732 the register lifetime info (REG_DEAD/basic_block_live_at_start).
1733 A CALL_INSN might be the last insn of a basic block, if it is
1734 inside an EH region. There is no easy way to tell, so we just
1735 always break when we see a CALL_INSN if flag_exceptions is nonzero. */
1736 if (flag_exceptions && GET_CODE (p) == CALL_INSN)
1739 if (GET_RTX_CLASS (GET_CODE (p)) != 'i')
1746 if (reg_set_p (src, p) || reg_set_p (dst, p)
1747 || (GET_CODE (PATTERN (p)) == USE
1748 && reg_overlap_mentioned_p (src, XEXP (PATTERN (p), 0))))
1751 /* See if all of DST dies in P. This test is
1752 slightly more conservative than it needs to be. */
1753 if ((dst_note = find_regno_note (p, REG_DEAD, REGNO (dst)))
1754 && (GET_MODE (XEXP (dst_note, 0)) == GET_MODE (dst)))
1756 /* If we would be moving INSN, check that we won't move it
1757 into the shadow of a live a live flags register. */
1758 /* ??? We only try to move it in front of P, although
1759 we could move it anywhere between OVERLAP and P. */
1760 if (overlap && GET_MODE (PREV_INSN (p)) != VOIDmode)
1768 /* If an optimization is done, the value of SRC while P
1769 is executed will be changed. Check that this is OK. */
1770 if (reg_overlap_mentioned_p (src, PATTERN (p)))
1772 for (q = p; q; q = NEXT_INSN (q))
1774 if (GET_CODE (q) == CODE_LABEL || GET_CODE (q) == JUMP_INSN
1775 || (GET_CODE (q) == NOTE
1776 && (NOTE_LINE_NUMBER (q) == NOTE_INSN_LOOP_BEG
1777 || NOTE_LINE_NUMBER (q) == NOTE_INSN_LOOP_END)))
1783 /* ??? We can't scan past the end of a basic block without
1784 updating the register lifetime info
1785 (REG_DEAD/basic_block_live_at_start).
1786 A CALL_INSN might be the last insn of a basic block, if
1787 it is inside an EH region. There is no easy way to tell,
1788 so we just always break when we see a CALL_INSN if
1789 flag_exceptions is nonzero. */
1790 if (flag_exceptions && GET_CODE (q) == CALL_INSN)
1796 if (GET_RTX_CLASS (GET_CODE (q)) != 'i')
1798 if (reg_overlap_mentioned_p (src, PATTERN (q))
1799 || reg_set_p (src, q))
1803 set2 = single_set (q);
1804 if (! q || ! set2 || GET_CODE (SET_SRC (set2)) != code
1805 || XEXP (SET_SRC (set2), 0) != src
1806 || GET_CODE (XEXP (SET_SRC (set2), 1)) != CONST_INT
1807 || (SET_DEST (set2) != src
1808 && ! find_reg_note (q, REG_DEAD, src)))
1810 /* If this is a PLUS, we can still save a register by doing
1813 src -= insn_const; .
1814 This also gives opportunities for subsequent
1815 optimizations in the backward pass, so do it there. */
1816 if (code == PLUS && backward
1817 /* Don't do this if we can likely tie DST to SET_DEST
1818 of P later; we can't do this tying here if we got a
1820 && ! (dst_note && ! REG_N_CALLS_CROSSED (REGNO (dst))
1822 && GET_CODE (SET_DEST (single_set (p))) == REG
1823 && (REGNO (SET_DEST (single_set (p)))
1824 < FIRST_PSEUDO_REGISTER))
1825 /* We may only emit an insn directly after P if we
1826 are not in the shadow of a live flags register. */
1827 && GET_MODE (p) == VOIDmode)
1832 newconst = -insn_const;
1840 newconst = INTVAL (XEXP (SET_SRC (set2), 1)) - insn_const;
1841 /* Reject out of range shifts. */
1845 >= GET_MODE_BITSIZE (GET_MODE (SET_SRC (set2))))))
1850 if (SET_DEST (set2) != src)
1851 post_inc_set = set2;
1854 /* We use 1 as last argument to validate_change so that all
1855 changes are accepted or rejected together by apply_change_group
1856 when it is called by validate_replace_rtx . */
1857 validate_change (q, &XEXP (SET_SRC (set2), 1),
1858 GEN_INT (newconst), 1);
1860 validate_change (insn, recog_data.operand_loc[match_number], src, 1);
1861 if (validate_replace_rtx (dst, src_subreg, p))
1866 if (reg_overlap_mentioned_p (dst, PATTERN (p)))
1868 if (! src_note && reg_overlap_mentioned_p (src, PATTERN (p)))
1870 /* INSN was already checked to be movable wrt. the registers that it
1871 sets / uses when we found no REG_DEAD note for src on it, but it
1872 still might clobber the flags register. We'll have to check that
1873 we won't insert it into the shadow of a live flags register when
1874 we finally know where we are to move it. */
1876 src_note = find_reg_note (p, REG_DEAD, src);
1879 /* If we have passed a call instruction, and the pseudo-reg SRC is not
1880 already live across a call, then don't perform the optimization. */
1881 if (GET_CODE (p) == CALL_INSN)
1883 if (REG_N_CALLS_CROSSED (REGNO (src)) == 0)
1897 true_loop_depth = backward ? 2 - loop_depth : loop_depth;
1899 /* Remove the death note for DST from P. */
1900 remove_note (p, dst_note);
1903 post_inc = emit_insn_after (copy_rtx (PATTERN (insn)), p);
1904 if ((HAVE_PRE_INCREMENT || HAVE_PRE_DECREMENT)
1906 && try_auto_increment (search_end, post_inc, 0, src, newconst, 1))
1908 validate_change (insn, &XEXP (SET_SRC (set), 1), GEN_INT (insn_const), 0);
1909 REG_N_SETS (REGNO (src))++;
1910 REG_N_REFS (REGNO (src)) += true_loop_depth;
1911 REG_LIVE_LENGTH (REGNO (src))++;
1915 /* The lifetime of src and dest overlap,
1916 but we can change this by moving insn. */
1917 rtx pat = PATTERN (insn);
1919 remove_note (overlap, src_note);
1920 if ((HAVE_POST_INCREMENT || HAVE_POST_DECREMENT)
1922 && try_auto_increment (overlap, insn, 0, src, insn_const, 0))
1926 rtx notes = REG_NOTES (insn);
1928 emit_insn_after_with_line_notes (pat, PREV_INSN (p), insn);
1929 PUT_CODE (insn, NOTE);
1930 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
1931 NOTE_SOURCE_FILE (insn) = 0;
1932 /* emit_insn_after_with_line_notes has no
1933 return value, so search for the new insn. */
1935 while (GET_RTX_CLASS (GET_CODE (insn)) != 'i'
1936 || PATTERN (insn) != pat)
1937 insn = PREV_INSN (insn);
1939 REG_NOTES (insn) = notes;
1942 /* Sometimes we'd generate src = const; src += n;
1943 if so, replace the instruction that set src
1944 in the first place. */
1946 if (! overlap && (code == PLUS || code == MINUS))
1948 rtx note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
1950 int num_calls2 = 0, s_length2 = 0;
1952 if (note && CONSTANT_P (XEXP (note, 0)))
1954 for (q = PREV_INSN (insn); q; q = PREV_INSN(q))
1956 if (GET_CODE (q) == CODE_LABEL || GET_CODE (q) == JUMP_INSN
1957 || (GET_CODE (q) == NOTE
1958 && (NOTE_LINE_NUMBER (q) == NOTE_INSN_LOOP_BEG
1959 || NOTE_LINE_NUMBER (q) == NOTE_INSN_LOOP_END)))
1965 /* ??? We can't scan past the end of a basic block without
1966 updating the register lifetime info
1967 (REG_DEAD/basic_block_live_at_start).
1968 A CALL_INSN might be the last insn of a basic block, if
1969 it is inside an EH region. There is no easy way to tell,
1970 so we just always break when we see a CALL_INSN if
1971 flag_exceptions is nonzero. */
1972 if (flag_exceptions && GET_CODE (q) == CALL_INSN)
1978 if (GET_RTX_CLASS (GET_CODE (q)) != 'i')
1981 if (reg_set_p (src, q))
1983 set2 = single_set (q);
1986 if (reg_overlap_mentioned_p (src, PATTERN (q)))
1991 if (GET_CODE (p) == CALL_INSN)
1994 if (q && set2 && SET_DEST (set2) == src && CONSTANT_P (SET_SRC (set2))
1995 && validate_change (insn, &SET_SRC (set), XEXP (note, 0), 0))
1998 NOTE_LINE_NUMBER (q) = NOTE_INSN_DELETED;
1999 NOTE_SOURCE_FILE (q) = 0;
2000 REG_N_SETS (REGNO (src))--;
2001 REG_N_CALLS_CROSSED (REGNO (src)) -= num_calls2;
2002 REG_N_REFS (REGNO (src)) -= true_loop_depth;
2003 REG_LIVE_LENGTH (REGNO (src)) -= s_length2;
2009 if ((HAVE_PRE_INCREMENT || HAVE_PRE_DECREMENT)
2010 && (code == PLUS || code == MINUS) && insn_const
2011 && try_auto_increment (p, insn, 0, src, insn_const, 1))
2013 else if ((HAVE_POST_INCREMENT || HAVE_POST_DECREMENT)
2015 && try_auto_increment (p, post_inc, post_inc_set, src, newconst, 0))
2017 /* If post_inc still prevails, try to find an
2018 insn where it can be used as a pre-in/decrement.
2019 If code is MINUS, this was already tried. */
2020 if (post_inc && code == PLUS
2021 /* Check that newconst is likely to be usable
2022 in a pre-in/decrement before starting the search. */
2023 && ((HAVE_PRE_INCREMENT && newconst > 0 && newconst <= MOVE_MAX)
2024 || (HAVE_PRE_DECREMENT && newconst < 0 && newconst >= -MOVE_MAX))
2025 && exact_log2 (newconst))
2029 inc_dest = post_inc_set ? SET_DEST (post_inc_set) : src;
2030 for (q = post_inc; (q = NEXT_INSN (q)); )
2032 if (GET_CODE (q) == CODE_LABEL || GET_CODE (q) == JUMP_INSN
2033 || (GET_CODE (q) == NOTE
2034 && (NOTE_LINE_NUMBER (q) == NOTE_INSN_LOOP_BEG
2035 || NOTE_LINE_NUMBER (q) == NOTE_INSN_LOOP_END)))
2038 /* ??? We can't scan past the end of a basic block without updating
2039 the register lifetime info (REG_DEAD/basic_block_live_at_start).
2040 A CALL_INSN might be the last insn of a basic block, if it
2041 is inside an EH region. There is no easy way to tell so we
2042 just always break when we see a CALL_INSN if flag_exceptions
2044 if (flag_exceptions && GET_CODE (q) == CALL_INSN)
2047 if (GET_RTX_CLASS (GET_CODE (q)) != 'i')
2049 if (src != inc_dest && (reg_overlap_mentioned_p (src, PATTERN (q))
2050 || reg_set_p (src, q)))
2052 if (reg_set_p (inc_dest, q))
2054 if (reg_overlap_mentioned_p (inc_dest, PATTERN (q)))
2056 try_auto_increment (q, post_inc,
2057 post_inc_set, inc_dest, newconst, 1);
2062 /* Move the death note for DST to INSN if it is used
2064 if (reg_overlap_mentioned_p (dst, PATTERN (insn)))
2066 XEXP (dst_note, 1) = REG_NOTES (insn);
2067 REG_NOTES (insn) = dst_note;
2072 /* Move the death note for SRC from INSN to P. */
2074 remove_note (insn, src_note);
2075 XEXP (src_note, 1) = REG_NOTES (p);
2076 REG_NOTES (p) = src_note;
2078 REG_N_CALLS_CROSSED (REGNO (src)) += s_num_calls;
2081 REG_N_SETS (REGNO (src))++;
2082 REG_N_SETS (REGNO (dst))--;
2084 REG_N_CALLS_CROSSED (REGNO (dst)) -= num_calls;
2086 REG_LIVE_LENGTH (REGNO (src)) += s_length;
2087 if (REG_LIVE_LENGTH (REGNO (dst)) >= 0)
2089 REG_LIVE_LENGTH (REGNO (dst)) -= length;
2090 /* REG_LIVE_LENGTH is only an approximation after
2091 combine if sched is not run, so make sure that we
2092 still have a reasonable value. */
2093 if (REG_LIVE_LENGTH (REGNO (dst)) < 2)
2094 REG_LIVE_LENGTH (REGNO (dst)) = 2;
2097 /* We assume that a register is used exactly once per
2098 insn in the updates above. If this is not correct,
2099 no great harm is done. */
2101 REG_N_REFS (REGNO (src)) += 2 * true_loop_depth;
2102 REG_N_REFS (REGNO (dst)) -= 2 * true_loop_depth;
2104 /* If that was the only time dst was set,
2105 and dst was not live at the start of the
2106 function, we know that we have no more
2107 references to dst; clear REG_N_REFS so it
2108 won't make reload do any work. */
2109 if (REG_N_SETS (REGNO (dst)) == 0
2110 && ! regno_uninitialized (REGNO (dst)))
2111 REG_N_REFS (REGNO (dst)) = 0;
2113 if (regmove_dump_file)
2114 fprintf (regmove_dump_file,
2115 "Fixed operand %d of insn %d matching operand %d.\n",
2116 operand_number, INSN_UID (insn), match_number);
2121 /* return nonzero if X is stable and mentions no regsiters but for
2122 mentioning SRC or mentioning / changing DST . If in doubt, presume
2124 The rationale is that we want to check if we can move an insn easily
2125 while just paying attention to SRC and DST. A register is considered
2126 stable if it has the RTX_UNCHANGING_P bit set, but that would still
2127 leave the burden to update REG_DEAD / REG_UNUSED notes, so we don't
2128 want any registers but SRC and DST. */
2130 stable_and_no_regs_but_for_p (x, src, dst)
2133 RTX_CODE code = GET_CODE (x);
2134 switch (GET_RTX_CLASS (code))
2136 case '<': case '1': case 'c': case '2': case 'b': case '3':
2139 const char *fmt = GET_RTX_FORMAT (code);
2140 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2142 && ! stable_and_no_regs_but_for_p (XEXP (x, i), src, dst))
2148 return x == src || x == dst;
2149 /* If this is a MEM, look inside - there might be a register hidden in
2150 the address of an unchanging MEM. */
2152 && ! stable_and_no_regs_but_for_p (XEXP (x, 0), src, dst))
2156 return ! rtx_unstable_p (x);