1 /* Move registers around to reduce number of move instructions needed.
2 Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3 1999, 2000, 2001, 2002 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
23 /* This module looks for cases where matching constraints would force
24 an instruction to need a reload, and this reload would be a register
25 to register move. It then attempts to change the registers used by the
26 instruction to avoid the move instruction. */
30 #include "rtl.h" /* stdio.h must precede rtl.h for FFS. */
32 #include "insn-config.h"
36 #include "hard-reg-set.h"
40 #include "basic-block.h"
46 /* Turn STACK_GROWS_DOWNWARD into a boolean. */
47 #ifdef STACK_GROWS_DOWNWARD
48 #undef STACK_GROWS_DOWNWARD
49 #define STACK_GROWS_DOWNWARD 1
51 #define STACK_GROWS_DOWNWARD 0
54 static int perhaps_ends_bb_p PARAMS ((rtx));
55 static int optimize_reg_copy_1 PARAMS ((rtx, rtx, rtx));
56 static void optimize_reg_copy_2 PARAMS ((rtx, rtx, rtx));
57 static void optimize_reg_copy_3 PARAMS ((rtx, rtx, rtx));
58 static void copy_src_to_dest PARAMS ((rtx, rtx, rtx, int));
59 static int *regmove_bb_head;
62 int with[MAX_RECOG_OPERANDS];
63 enum { READ, WRITE, READWRITE } use[MAX_RECOG_OPERANDS];
64 int commutative[MAX_RECOG_OPERANDS];
65 int early_clobber[MAX_RECOG_OPERANDS];
68 static rtx discover_flags_reg PARAMS ((void));
69 static void mark_flags_life_zones PARAMS ((rtx));
70 static void flags_set_1 PARAMS ((rtx, rtx, void *));
72 static int try_auto_increment PARAMS ((rtx, rtx, rtx, rtx, HOST_WIDE_INT, int));
73 static int find_matches PARAMS ((rtx, struct match *));
74 static void replace_in_call_usage PARAMS ((rtx *, unsigned int, rtx, rtx));
75 static int fixup_match_1 PARAMS ((rtx, rtx, rtx, rtx, rtx, int, int, int, FILE *))
77 static int reg_is_remote_constant_p PARAMS ((rtx, rtx, rtx));
78 static int stable_and_no_regs_but_for_p PARAMS ((rtx, rtx, rtx));
79 static int regclass_compatible_p PARAMS ((int, int));
80 static int replacement_quality PARAMS ((rtx));
81 static int fixup_match_2 PARAMS ((rtx, rtx, rtx, rtx, FILE *));
83 /* Return nonzero if registers with CLASS1 and CLASS2 can be merged without
84 causing too much register allocation problems. */
86 regclass_compatible_p (class0, class1)
89 return (class0 == class1
90 || (reg_class_subset_p (class0, class1)
91 && ! CLASS_LIKELY_SPILLED_P (class0))
92 || (reg_class_subset_p (class1, class0)
93 && ! CLASS_LIKELY_SPILLED_P (class1)));
96 /* INC_INSN is an instruction that adds INCREMENT to REG.
97 Try to fold INC_INSN as a post/pre in/decrement into INSN.
98 Iff INC_INSN_SET is nonzero, inc_insn has a destination different from src.
99 Return nonzero for success. */
101 try_auto_increment (insn, inc_insn, inc_insn_set, reg, increment, pre)
102 rtx reg, insn, inc_insn ,inc_insn_set;
103 HOST_WIDE_INT increment;
106 enum rtx_code inc_code;
108 rtx pset = single_set (insn);
111 /* Can't use the size of SET_SRC, we might have something like
112 (sign_extend:SI (mem:QI ... */
113 rtx use = find_use_as_address (pset, reg, 0);
114 if (use != 0 && use != (rtx) (size_t) 1)
116 int size = GET_MODE_SIZE (GET_MODE (use));
118 || (HAVE_POST_INCREMENT
119 && pre == 0 && (inc_code = POST_INC, increment == size))
120 || (HAVE_PRE_INCREMENT
121 && pre == 1 && (inc_code = PRE_INC, increment == size))
122 || (HAVE_POST_DECREMENT
123 && pre == 0 && (inc_code = POST_DEC, increment == -size))
124 || (HAVE_PRE_DECREMENT
125 && pre == 1 && (inc_code = PRE_DEC, increment == -size))
131 &SET_SRC (inc_insn_set),
132 XEXP (SET_SRC (inc_insn_set), 0), 1);
133 validate_change (insn, &XEXP (use, 0),
134 gen_rtx_fmt_e (inc_code, Pmode, reg), 1);
135 if (apply_change_group ())
137 /* If there is a REG_DEAD note on this insn, we must
138 change this not to REG_UNUSED meaning that the register
139 is set, but the value is dead. Failure to do so will
140 result in a sched1 abort -- when it recomputes lifetime
141 information, the number of REG_DEAD notes will have
143 rtx note = find_reg_note (insn, REG_DEAD, reg);
145 PUT_MODE (note, REG_UNUSED);
148 = gen_rtx_EXPR_LIST (REG_INC,
149 reg, REG_NOTES (insn));
151 delete_insn (inc_insn);
160 /* Determine if the pattern generated by add_optab has a clobber,
161 such as might be issued for a flags hard register. To make the
162 code elsewhere simpler, we handle cc0 in this same framework.
164 Return the register if one was discovered. Return NULL_RTX if
165 if no flags were found. Return pc_rtx if we got confused. */
168 discover_flags_reg ()
171 tmp = gen_rtx_REG (word_mode, 10000);
172 tmp = gen_add3_insn (tmp, tmp, GEN_INT (2));
174 /* If we get something that isn't a simple set, or a
175 [(set ..) (clobber ..)], this whole function will go wrong. */
176 if (GET_CODE (tmp) == SET)
178 else if (GET_CODE (tmp) == PARALLEL)
182 if (XVECLEN (tmp, 0) != 2)
184 tmp = XVECEXP (tmp, 0, 1);
185 if (GET_CODE (tmp) != CLOBBER)
189 /* Don't do anything foolish if the md wanted to clobber a
190 scratch or something. We only care about hard regs.
191 Moreover we don't like the notion of subregs of hard regs. */
192 if (GET_CODE (tmp) == SUBREG
193 && GET_CODE (SUBREG_REG (tmp)) == REG
194 && REGNO (SUBREG_REG (tmp)) < FIRST_PSEUDO_REGISTER)
196 found = (GET_CODE (tmp) == REG && REGNO (tmp) < FIRST_PSEUDO_REGISTER);
198 return (found ? tmp : NULL_RTX);
204 /* It is a tedious task identifying when the flags register is live and
205 when it is safe to optimize. Since we process the instruction stream
206 multiple times, locate and record these live zones by marking the
207 mode of the instructions --
209 QImode is used on the instruction at which the flags becomes live.
211 HImode is used within the range (exclusive) that the flags are
212 live. Thus the user of the flags is not marked.
214 All other instructions are cleared to VOIDmode. */
216 /* Used to communicate with flags_set_1. */
217 static rtx flags_set_1_rtx;
218 static int flags_set_1_set;
221 mark_flags_life_zones (flags)
229 /* If we found a flags register on a cc0 host, bail. */
230 if (flags == NULL_RTX)
232 else if (flags != cc0_rtx)
236 /* Simple cases first: if no flags, clear all modes. If confusing,
237 mark the entire function as being in a flags shadow. */
238 if (flags == NULL_RTX || flags == pc_rtx)
240 enum machine_mode mode = (flags ? HImode : VOIDmode);
242 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
243 PUT_MODE (insn, mode);
251 flags_regno = REGNO (flags);
252 flags_nregs = HARD_REGNO_NREGS (flags_regno, GET_MODE (flags));
254 flags_set_1_rtx = flags;
256 /* Process each basic block. */
257 FOR_EACH_BB_REVERSE (block)
265 /* Look out for the (unlikely) case of flags being live across
266 basic block boundaries. */
271 for (i = 0; i < flags_nregs; ++i)
272 live |= REGNO_REG_SET_P (block->global_live_at_start,
279 /* Process liveness in reverse order of importance --
280 alive, death, birth. This lets more important info
281 overwrite the mode of lesser info. */
286 /* In the cc0 case, death is not marked in reg notes,
287 but is instead the mere use of cc0 when it is alive. */
288 if (live && reg_mentioned_p (cc0_rtx, PATTERN (insn)))
291 /* In the hard reg case, we watch death notes. */
292 if (live && find_regno_note (insn, REG_DEAD, flags_regno))
295 PUT_MODE (insn, (live ? HImode : VOIDmode));
297 /* In either case, birth is denoted simply by it's presence
298 as the destination of a set. */
300 note_stores (PATTERN (insn), flags_set_1, NULL);
304 PUT_MODE (insn, QImode);
308 PUT_MODE (insn, (live ? HImode : VOIDmode));
312 insn = NEXT_INSN (insn);
317 /* A subroutine of mark_flags_life_zones, called through note_stores. */
320 flags_set_1 (x, pat, data)
322 void *data ATTRIBUTE_UNUSED;
324 if (GET_CODE (pat) == SET
325 && reg_overlap_mentioned_p (x, flags_set_1_rtx))
329 static int *regno_src_regno;
331 /* Indicate how good a choice REG (which appears as a source) is to replace
332 a destination register with. The higher the returned value, the better
333 the choice. The main objective is to avoid using a register that is
334 a candidate for tying to a hard register, since the output might in
335 turn be a candidate to be tied to a different hard register. */
337 replacement_quality (reg)
342 /* Bad if this isn't a register at all. */
343 if (GET_CODE (reg) != REG)
346 /* If this register is not meant to get a hard register,
347 it is a poor choice. */
348 if (REG_LIVE_LENGTH (REGNO (reg)) < 0)
351 src_regno = regno_src_regno[REGNO (reg)];
353 /* If it was not copied from another register, it is fine. */
357 /* Copied from a hard register? */
358 if (src_regno < FIRST_PSEUDO_REGISTER)
361 /* Copied from a pseudo register - not as bad as from a hard register,
362 yet still cumbersome, since the register live length will be lengthened
363 when the registers get tied. */
367 /* Return 1 if INSN might end a basic block. */
369 static int perhaps_ends_bb_p (insn)
372 switch (GET_CODE (insn))
376 /* These always end a basic block. */
380 /* A CALL_INSN might be the last insn of a basic block, if it is inside
381 an EH region or if there are nonlocal gotos. Note that this test is
382 very conservative. */
383 if (nonlocal_goto_handler_labels)
387 return can_throw_internal (insn);
391 /* INSN is a copy from SRC to DEST, both registers, and SRC does not die
394 Search forward to see if SRC dies before either it or DEST is modified,
395 but don't scan past the end of a basic block. If so, we can replace SRC
396 with DEST and let SRC die in INSN.
398 This will reduce the number of registers live in that range and may enable
399 DEST to be tied to SRC, thus often saving one register in addition to a
400 register-register copy. */
403 optimize_reg_copy_1 (insn, dest, src)
411 int sregno = REGNO (src);
412 int dregno = REGNO (dest);
414 /* We don't want to mess with hard regs if register classes are small. */
416 || (SMALL_REGISTER_CLASSES
417 && (sregno < FIRST_PSEUDO_REGISTER
418 || dregno < FIRST_PSEUDO_REGISTER))
419 /* We don't see all updates to SP if they are in an auto-inc memory
420 reference, so we must disallow this optimization on them. */
421 || sregno == STACK_POINTER_REGNUM || dregno == STACK_POINTER_REGNUM)
424 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
426 /* ??? We can't scan past the end of a basic block without updating
427 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
428 if (perhaps_ends_bb_p (p))
430 else if (! INSN_P (p))
433 if (reg_set_p (src, p) || reg_set_p (dest, p)
434 /* Don't change a USE of a register. */
435 || (GET_CODE (PATTERN (p)) == USE
436 && reg_overlap_mentioned_p (src, XEXP (PATTERN (p), 0))))
439 /* See if all of SRC dies in P. This test is slightly more
440 conservative than it needs to be. */
441 if ((note = find_regno_note (p, REG_DEAD, sregno)) != 0
442 && GET_MODE (XEXP (note, 0)) == GET_MODE (src))
450 /* We can do the optimization. Scan forward from INSN again,
451 replacing regs as we go. Set FAILED if a replacement can't
452 be done. In that case, we can't move the death note for SRC.
453 This should be rare. */
455 /* Set to stop at next insn. */
456 for (q = next_real_insn (insn);
457 q != next_real_insn (p);
458 q = next_real_insn (q))
460 if (reg_overlap_mentioned_p (src, PATTERN (q)))
462 /* If SRC is a hard register, we might miss some
463 overlapping registers with validate_replace_rtx,
464 so we would have to undo it. We can't if DEST is
465 present in the insn, so fail in that combination
467 if (sregno < FIRST_PSEUDO_REGISTER
468 && reg_mentioned_p (dest, PATTERN (q)))
471 /* Replace all uses and make sure that the register
472 isn't still present. */
473 else if (validate_replace_rtx (src, dest, q)
474 && (sregno >= FIRST_PSEUDO_REGISTER
475 || ! reg_overlap_mentioned_p (src,
480 validate_replace_rtx (dest, src, q);
485 /* For SREGNO, count the total number of insns scanned.
486 For DREGNO, count the total number of insns scanned after
487 passing the death note for DREGNO. */
492 /* If the insn in which SRC dies is a CALL_INSN, don't count it
493 as a call that has been crossed. Otherwise, count it. */
494 if (q != p && GET_CODE (q) == CALL_INSN)
496 /* Similarly, total calls for SREGNO, total calls beyond
497 the death note for DREGNO. */
503 /* If DEST dies here, remove the death note and save it for
504 later. Make sure ALL of DEST dies here; again, this is
505 overly conservative. */
507 && (dest_death = find_regno_note (q, REG_DEAD, dregno)) != 0)
509 if (GET_MODE (XEXP (dest_death, 0)) != GET_MODE (dest))
510 failed = 1, dest_death = 0;
512 remove_note (q, dest_death);
518 /* These counters need to be updated if and only if we are
519 going to move the REG_DEAD note. */
520 if (sregno >= FIRST_PSEUDO_REGISTER)
522 if (REG_LIVE_LENGTH (sregno) >= 0)
524 REG_LIVE_LENGTH (sregno) -= s_length;
525 /* REG_LIVE_LENGTH is only an approximation after
526 combine if sched is not run, so make sure that we
527 still have a reasonable value. */
528 if (REG_LIVE_LENGTH (sregno) < 2)
529 REG_LIVE_LENGTH (sregno) = 2;
532 REG_N_CALLS_CROSSED (sregno) -= s_n_calls;
535 /* Move death note of SRC from P to INSN. */
536 remove_note (p, note);
537 XEXP (note, 1) = REG_NOTES (insn);
538 REG_NOTES (insn) = note;
541 /* DEST is also dead if INSN has a REG_UNUSED note for DEST. */
543 && (dest_death = find_regno_note (insn, REG_UNUSED, dregno)))
545 PUT_REG_NOTE_KIND (dest_death, REG_DEAD);
546 remove_note (insn, dest_death);
549 /* Put death note of DEST on P if we saw it die. */
552 XEXP (dest_death, 1) = REG_NOTES (p);
553 REG_NOTES (p) = dest_death;
555 if (dregno >= FIRST_PSEUDO_REGISTER)
557 /* If and only if we are moving the death note for DREGNO,
558 then we need to update its counters. */
559 if (REG_LIVE_LENGTH (dregno) >= 0)
560 REG_LIVE_LENGTH (dregno) += d_length;
561 REG_N_CALLS_CROSSED (dregno) += d_n_calls;
568 /* If SRC is a hard register which is set or killed in some other
569 way, we can't do this optimization. */
570 else if (sregno < FIRST_PSEUDO_REGISTER
571 && dead_or_set_p (p, src))
577 /* INSN is a copy of SRC to DEST, in which SRC dies. See if we now have
578 a sequence of insns that modify DEST followed by an insn that sets
579 SRC to DEST in which DEST dies, with no prior modification of DEST.
580 (There is no need to check if the insns in between actually modify
581 DEST. We should not have cases where DEST is not modified, but
582 the optimization is safe if no such modification is detected.)
583 In that case, we can replace all uses of DEST, starting with INSN and
584 ending with the set of SRC to DEST, with SRC. We do not do this
585 optimization if a CALL_INSN is crossed unless SRC already crosses a
586 call or if DEST dies before the copy back to SRC.
588 It is assumed that DEST and SRC are pseudos; it is too complicated to do
589 this for hard registers since the substitutions we may make might fail. */
592 optimize_reg_copy_2 (insn, dest, src)
599 int sregno = REGNO (src);
600 int dregno = REGNO (dest);
602 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
604 /* ??? We can't scan past the end of a basic block without updating
605 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
606 if (perhaps_ends_bb_p (p))
608 else if (! INSN_P (p))
611 set = single_set (p);
612 if (set && SET_SRC (set) == dest && SET_DEST (set) == src
613 && find_reg_note (p, REG_DEAD, dest))
615 /* We can do the optimization. Scan forward from INSN again,
616 replacing regs as we go. */
618 /* Set to stop at next insn. */
619 for (q = insn; q != NEXT_INSN (p); q = NEXT_INSN (q))
622 if (reg_mentioned_p (dest, PATTERN (q)))
623 PATTERN (q) = replace_rtx (PATTERN (q), dest, src);
626 if (GET_CODE (q) == CALL_INSN)
628 REG_N_CALLS_CROSSED (dregno)--;
629 REG_N_CALLS_CROSSED (sregno)++;
633 remove_note (p, find_reg_note (p, REG_DEAD, dest));
634 REG_N_DEATHS (dregno)--;
635 remove_note (insn, find_reg_note (insn, REG_DEAD, src));
636 REG_N_DEATHS (sregno)--;
640 if (reg_set_p (src, p)
641 || find_reg_note (p, REG_DEAD, dest)
642 || (GET_CODE (p) == CALL_INSN && REG_N_CALLS_CROSSED (sregno) == 0))
646 /* INSN is a ZERO_EXTEND or SIGN_EXTEND of SRC to DEST.
647 Look if SRC dies there, and if it is only set once, by loading
648 it from memory. If so, try to encorporate the zero/sign extension
649 into the memory read, change SRC to the mode of DEST, and alter
650 the remaining accesses to use the appropriate SUBREG. This allows
651 SRC and DEST to be tied later. */
653 optimize_reg_copy_3 (insn, dest, src)
658 rtx src_reg = XEXP (src, 0);
659 int src_no = REGNO (src_reg);
660 int dst_no = REGNO (dest);
662 enum machine_mode old_mode;
664 if (src_no < FIRST_PSEUDO_REGISTER
665 || dst_no < FIRST_PSEUDO_REGISTER
666 || ! find_reg_note (insn, REG_DEAD, src_reg)
667 || REG_N_DEATHS (src_no) != 1
668 || REG_N_SETS (src_no) != 1)
670 for (p = PREV_INSN (insn); p && ! reg_set_p (src_reg, p); p = PREV_INSN (p))
671 /* ??? We can't scan past the end of a basic block without updating
672 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
673 if (perhaps_ends_bb_p (p))
679 if (! (set = single_set (p))
680 || GET_CODE (SET_SRC (set)) != MEM
681 /* If there's a REG_EQUIV note, this must be an insn that loads an
682 argument. Prefer keeping the note over doing this optimization. */
683 || find_reg_note (p, REG_EQUIV, NULL_RTX)
684 || SET_DEST (set) != src_reg)
687 /* Be conserative: although this optimization is also valid for
688 volatile memory references, that could cause trouble in later passes. */
689 if (MEM_VOLATILE_P (SET_SRC (set)))
692 /* Do not use a SUBREG to truncate from one mode to another if truncation
694 if (GET_MODE_BITSIZE (GET_MODE (src_reg)) <= GET_MODE_BITSIZE (GET_MODE (src))
695 && !TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (GET_MODE (src)),
696 GET_MODE_BITSIZE (GET_MODE (src_reg))))
699 old_mode = GET_MODE (src_reg);
700 PUT_MODE (src_reg, GET_MODE (src));
701 XEXP (src, 0) = SET_SRC (set);
703 /* Include this change in the group so that it's easily undone if
704 one of the changes in the group is invalid. */
705 validate_change (p, &SET_SRC (set), src, 1);
707 /* Now walk forward making additional replacements. We want to be able
708 to undo all the changes if a later substitution fails. */
709 subreg = gen_lowpart_SUBREG (old_mode, src_reg);
710 while (p = NEXT_INSN (p), p != insn)
715 /* Make a tenative change. */
716 validate_replace_rtx_group (src_reg, subreg, p);
719 validate_replace_rtx_group (src, src_reg, insn);
721 /* Now see if all the changes are valid. */
722 if (! apply_change_group ())
724 /* One or more changes were no good. Back out everything. */
725 PUT_MODE (src_reg, old_mode);
726 XEXP (src, 0) = src_reg;
730 rtx note = find_reg_note (p, REG_EQUAL, NULL_RTX);
732 remove_note (p, note);
737 /* If we were not able to update the users of src to use dest directly, try
738 instead moving the value to dest directly before the operation. */
741 copy_src_to_dest (insn, src, dest, old_max_uid)
760 /* A REG_LIVE_LENGTH of -1 indicates the register is equivalent to a constant
761 or memory location and is used infrequently; a REG_LIVE_LENGTH of -2 is
762 parameter when there is no frame pointer that is not allocated a register.
763 For now, we just reject them, rather than incrementing the live length. */
765 if (GET_CODE (src) == REG
766 && REG_LIVE_LENGTH (REGNO (src)) > 0
767 && GET_CODE (dest) == REG
768 && !RTX_UNCHANGING_P (dest)
769 && REG_LIVE_LENGTH (REGNO (dest)) > 0
770 && (set = single_set (insn)) != NULL_RTX
771 && !reg_mentioned_p (dest, SET_SRC (set))
772 && GET_MODE (src) == GET_MODE (dest))
774 int old_num_regs = reg_rtx_no;
776 /* Generate the src->dest move. */
778 emit_move_insn (dest, src);
781 /* If this sequence uses new registers, we may not use it. */
782 if (old_num_regs != reg_rtx_no
783 || ! validate_replace_rtx (src, dest, insn))
785 /* We have to restore reg_rtx_no to its old value, lest
786 recompute_reg_usage will try to compute the usage of the
787 new regs, yet reg_n_info is not valid for them. */
788 reg_rtx_no = old_num_regs;
791 emit_insn_before (seq, insn);
792 move_insn = PREV_INSN (insn);
793 p_move_notes = ®_NOTES (move_insn);
794 p_insn_notes = ®_NOTES (insn);
796 /* Move any notes mentioning src to the move instruction */
797 for (link = REG_NOTES (insn); link != NULL_RTX; link = next)
799 next = XEXP (link, 1);
800 if (XEXP (link, 0) == src)
802 *p_move_notes = link;
803 p_move_notes = &XEXP (link, 1);
807 *p_insn_notes = link;
808 p_insn_notes = &XEXP (link, 1);
812 *p_move_notes = NULL_RTX;
813 *p_insn_notes = NULL_RTX;
815 /* Is the insn the head of a basic block? If so extend it */
816 insn_uid = INSN_UID (insn);
817 move_uid = INSN_UID (move_insn);
818 if (insn_uid < old_max_uid)
820 bb = regmove_bb_head[insn_uid];
823 BLOCK_HEAD (bb) = move_insn;
824 regmove_bb_head[insn_uid] = -1;
828 /* Update the various register tables. */
829 dest_regno = REGNO (dest);
830 REG_N_SETS (dest_regno) ++;
831 REG_LIVE_LENGTH (dest_regno)++;
832 if (REGNO_FIRST_UID (dest_regno) == insn_uid)
833 REGNO_FIRST_UID (dest_regno) = move_uid;
835 src_regno = REGNO (src);
836 if (! find_reg_note (move_insn, REG_DEAD, src))
837 REG_LIVE_LENGTH (src_regno)++;
839 if (REGNO_FIRST_UID (src_regno) == insn_uid)
840 REGNO_FIRST_UID (src_regno) = move_uid;
842 if (REGNO_LAST_UID (src_regno) == insn_uid)
843 REGNO_LAST_UID (src_regno) = move_uid;
845 if (REGNO_LAST_NOTE_UID (src_regno) == insn_uid)
846 REGNO_LAST_NOTE_UID (src_regno) = move_uid;
851 /* Return whether REG is set in only one location, and is set to a
852 constant, but is set in a different basic block from INSN (an
853 instructions which uses REG). In this case REG is equivalent to a
854 constant, and we don't want to break that equivalence, because that
855 may increase register pressure and make reload harder. If REG is
856 set in the same basic block as INSN, we don't worry about it,
857 because we'll probably need a register anyhow (??? but what if REG
858 is used in a different basic block as well as this one?). FIRST is
859 the first insn in the function. */
862 reg_is_remote_constant_p (reg, insn, first)
869 if (REG_N_SETS (REGNO (reg)) != 1)
872 /* Look for the set. */
873 for (p = LOG_LINKS (insn); p; p = XEXP (p, 1))
877 if (REG_NOTE_KIND (p) != 0)
879 s = single_set (XEXP (p, 0));
881 && GET_CODE (SET_DEST (s)) == REG
882 && REGNO (SET_DEST (s)) == REGNO (reg))
884 /* The register is set in the same basic block. */
889 for (p = first; p && p != insn; p = NEXT_INSN (p))
897 && GET_CODE (SET_DEST (s)) == REG
898 && REGNO (SET_DEST (s)) == REGNO (reg))
900 /* This is the instruction which sets REG. If there is a
901 REG_EQUAL note, then REG is equivalent to a constant. */
902 if (find_reg_note (p, REG_EQUAL, NULL_RTX))
911 /* INSN is adding a CONST_INT to a REG. We search backwards looking for
912 another add immediate instruction with the same source and dest registers,
913 and if we find one, we change INSN to an increment, and return 1. If
914 no changes are made, we return 0.
917 (set (reg100) (plus reg1 offset1))
919 (set (reg100) (plus reg1 offset2))
921 (set (reg100) (plus reg1 offset1))
923 (set (reg100) (plus reg100 offset2-offset1)) */
925 /* ??? What does this comment mean? */
926 /* cse disrupts preincrement / postdecrement squences when it finds a
927 hard register as ultimate source, like the frame pointer. */
930 fixup_match_2 (insn, dst, src, offset, regmove_dump_file)
931 rtx insn, dst, src, offset;
932 FILE *regmove_dump_file;
934 rtx p, dst_death = 0;
935 int length, num_calls = 0;
937 /* If SRC dies in INSN, we'd have to move the death note. This is
938 considered to be very unlikely, so we just skip the optimization
940 if (find_regno_note (insn, REG_DEAD, REGNO (src)))
943 /* Scan backward to find the first instruction that sets DST. */
945 for (length = 0, p = PREV_INSN (insn); p; p = PREV_INSN (p))
949 /* ??? We can't scan past the end of a basic block without updating
950 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
951 if (perhaps_ends_bb_p (p))
953 else if (! INSN_P (p))
956 if (find_regno_note (p, REG_DEAD, REGNO (dst)))
961 pset = single_set (p);
962 if (pset && SET_DEST (pset) == dst
963 && GET_CODE (SET_SRC (pset)) == PLUS
964 && XEXP (SET_SRC (pset), 0) == src
965 && GET_CODE (XEXP (SET_SRC (pset), 1)) == CONST_INT)
967 HOST_WIDE_INT newconst
968 = INTVAL (offset) - INTVAL (XEXP (SET_SRC (pset), 1));
969 rtx add = gen_add3_insn (dst, dst, GEN_INT (newconst));
971 if (add && validate_change (insn, &PATTERN (insn), add, 0))
973 /* Remove the death note for DST from DST_DEATH. */
976 remove_death (REGNO (dst), dst_death);
977 REG_LIVE_LENGTH (REGNO (dst)) += length;
978 REG_N_CALLS_CROSSED (REGNO (dst)) += num_calls;
981 if (regmove_dump_file)
982 fprintf (regmove_dump_file,
983 "Fixed operand of insn %d.\n",
987 for (p = PREV_INSN (insn); p; p = PREV_INSN (p))
989 if (GET_CODE (p) == CODE_LABEL
990 || GET_CODE (p) == JUMP_INSN)
994 if (reg_overlap_mentioned_p (dst, PATTERN (p)))
996 if (try_auto_increment (p, insn, 0, dst, newconst, 0))
1001 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
1003 if (GET_CODE (p) == CODE_LABEL
1004 || GET_CODE (p) == JUMP_INSN)
1008 if (reg_overlap_mentioned_p (dst, PATTERN (p)))
1010 try_auto_increment (p, insn, 0, dst, newconst, 1);
1019 if (reg_set_p (dst, PATTERN (p)))
1022 /* If we have passed a call instruction, and the
1023 pseudo-reg SRC is not already live across a call,
1024 then don't perform the optimization. */
1025 /* reg_set_p is overly conservative for CALL_INSNS, thinks that all
1026 hard regs are clobbered. Thus, we only use it for src for
1028 if (GET_CODE (p) == CALL_INSN)
1033 if (REG_N_CALLS_CROSSED (REGNO (src)) == 0)
1036 if (call_used_regs [REGNO (dst)]
1037 || find_reg_fusage (p, CLOBBER, dst))
1040 else if (reg_set_p (src, PATTERN (p)))
1047 /* Main entry for the register move optimization.
1048 F is the first instruction.
1049 NREGS is one plus the highest pseudo-reg number used in the instruction.
1050 REGMOVE_DUMP_FILE is a stream for output of a trace of actions taken
1051 (or 0 if none should be output). */
1054 regmove_optimize (f, nregs, regmove_dump_file)
1057 FILE *regmove_dump_file;
1059 int old_max_uid = get_max_uid ();
1064 rtx copy_src, copy_dst;
1067 /* ??? Hack. Regmove doesn't examine the CFG, and gets mightily
1068 confused by non-call exceptions ending blocks. */
1069 if (flag_non_call_exceptions)
1072 /* Find out where a potential flags register is live, and so that we
1073 can supress some optimizations in those zones. */
1074 mark_flags_life_zones (discover_flags_reg ());
1076 regno_src_regno = (int *) xmalloc (sizeof *regno_src_regno * nregs);
1077 for (i = nregs; --i >= 0; ) regno_src_regno[i] = -1;
1079 regmove_bb_head = (int *) xmalloc (sizeof (int) * (old_max_uid + 1));
1080 for (i = old_max_uid; i >= 0; i--) regmove_bb_head[i] = -1;
1082 regmove_bb_head[INSN_UID (bb->head)] = bb->index;
1084 /* A forward/backward pass. Replace output operands with input operands. */
1086 for (pass = 0; pass <= 2; pass++)
1088 if (! flag_regmove && pass >= flag_expensive_optimizations)
1091 if (regmove_dump_file)
1092 fprintf (regmove_dump_file, "Starting %s pass...\n",
1093 pass ? "backward" : "forward");
1095 for (insn = pass ? get_last_insn () : f; insn;
1096 insn = pass ? PREV_INSN (insn) : NEXT_INSN (insn))
1099 int op_no, match_no;
1101 set = single_set (insn);
1105 if (flag_expensive_optimizations && ! pass
1106 && (GET_CODE (SET_SRC (set)) == SIGN_EXTEND
1107 || GET_CODE (SET_SRC (set)) == ZERO_EXTEND)
1108 && GET_CODE (XEXP (SET_SRC (set), 0)) == REG
1109 && GET_CODE (SET_DEST (set)) == REG)
1110 optimize_reg_copy_3 (insn, SET_DEST (set), SET_SRC (set));
1112 if (flag_expensive_optimizations && ! pass
1113 && GET_CODE (SET_SRC (set)) == REG
1114 && GET_CODE (SET_DEST (set)) == REG)
1116 /* If this is a register-register copy where SRC is not dead,
1117 see if we can optimize it. If this optimization succeeds,
1118 it will become a copy where SRC is dead. */
1119 if ((find_reg_note (insn, REG_DEAD, SET_SRC (set))
1120 || optimize_reg_copy_1 (insn, SET_DEST (set), SET_SRC (set)))
1121 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
1123 /* Similarly for a pseudo-pseudo copy when SRC is dead. */
1124 if (REGNO (SET_SRC (set)) >= FIRST_PSEUDO_REGISTER)
1125 optimize_reg_copy_2 (insn, SET_DEST (set), SET_SRC (set));
1126 if (regno_src_regno[REGNO (SET_DEST (set))] < 0
1127 && SET_SRC (set) != SET_DEST (set))
1129 int srcregno = REGNO (SET_SRC (set));
1130 if (regno_src_regno[srcregno] >= 0)
1131 srcregno = regno_src_regno[srcregno];
1132 regno_src_regno[REGNO (SET_DEST (set))] = srcregno;
1139 if (! find_matches (insn, &match))
1142 /* Now scan through the operands looking for a source operand
1143 which is supposed to match the destination operand.
1144 Then scan forward for an instruction which uses the dest
1146 If it dies there, then replace the dest in both operands with
1147 the source operand. */
1149 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1151 rtx src, dst, src_subreg;
1152 enum reg_class src_class, dst_class;
1154 match_no = match.with[op_no];
1156 /* Nothing to do if the two operands aren't supposed to match. */
1160 src = recog_data.operand[op_no];
1161 dst = recog_data.operand[match_no];
1163 if (GET_CODE (src) != REG)
1167 if (GET_CODE (dst) == SUBREG
1168 && GET_MODE_SIZE (GET_MODE (dst))
1169 >= GET_MODE_SIZE (GET_MODE (SUBREG_REG (dst))))
1172 = gen_rtx_SUBREG (GET_MODE (SUBREG_REG (dst)),
1173 src, SUBREG_BYTE (dst));
1174 dst = SUBREG_REG (dst);
1176 if (GET_CODE (dst) != REG
1177 || REGNO (dst) < FIRST_PSEUDO_REGISTER)
1180 if (REGNO (src) < FIRST_PSEUDO_REGISTER)
1182 if (match.commutative[op_no] < op_no)
1183 regno_src_regno[REGNO (dst)] = REGNO (src);
1187 if (REG_LIVE_LENGTH (REGNO (src)) < 0)
1190 /* op_no/src must be a read-only operand, and
1191 match_operand/dst must be a write-only operand. */
1192 if (match.use[op_no] != READ
1193 || match.use[match_no] != WRITE)
1196 if (match.early_clobber[match_no]
1197 && count_occurrences (PATTERN (insn), src, 0) > 1)
1200 /* Make sure match_operand is the destination. */
1201 if (recog_data.operand[match_no] != SET_DEST (set))
1204 /* If the operands already match, then there is nothing to do. */
1205 if (operands_match_p (src, dst))
1208 /* But in the commutative case, we might find a better match. */
1209 if (match.commutative[op_no] >= 0)
1211 rtx comm = recog_data.operand[match.commutative[op_no]];
1212 if (operands_match_p (comm, dst)
1213 && (replacement_quality (comm)
1214 >= replacement_quality (src)))
1218 src_class = reg_preferred_class (REGNO (src));
1219 dst_class = reg_preferred_class (REGNO (dst));
1220 if (! regclass_compatible_p (src_class, dst_class))
1223 if (GET_MODE (src) != GET_MODE (dst))
1226 if (fixup_match_1 (insn, set, src, src_subreg, dst, pass,
1234 /* A backward pass. Replace input operands with output operands. */
1236 if (regmove_dump_file)
1237 fprintf (regmove_dump_file, "Starting backward pass...\n");
1239 for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
1243 int op_no, match_no;
1246 if (! find_matches (insn, &match))
1249 /* Now scan through the operands looking for a destination operand
1250 which is supposed to match a source operand.
1251 Then scan backward for an instruction which sets the source
1252 operand. If safe, then replace the source operand with the
1253 dest operand in both instructions. */
1255 copy_src = NULL_RTX;
1256 copy_dst = NULL_RTX;
1257 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1259 rtx set, p, src, dst;
1260 rtx src_note, dst_note;
1262 enum reg_class src_class, dst_class;
1265 match_no = match.with[op_no];
1267 /* Nothing to do if the two operands aren't supposed to match. */
1271 dst = recog_data.operand[match_no];
1272 src = recog_data.operand[op_no];
1274 if (GET_CODE (src) != REG)
1277 if (GET_CODE (dst) != REG
1278 || REGNO (dst) < FIRST_PSEUDO_REGISTER
1279 || REG_LIVE_LENGTH (REGNO (dst)) < 0
1280 || RTX_UNCHANGING_P (dst))
1283 /* If the operands already match, then there is nothing to do. */
1284 if (operands_match_p (src, dst))
1287 if (match.commutative[op_no] >= 0)
1289 rtx comm = recog_data.operand[match.commutative[op_no]];
1290 if (operands_match_p (comm, dst))
1294 set = single_set (insn);
1298 /* Note that single_set ignores parts of a parallel set for
1299 which one of the destinations is REG_UNUSED. We can't
1300 handle that here, since we can wind up rewriting things
1301 such that a single register is set twice within a single
1303 if (reg_set_p (src, insn))
1306 /* match_no/dst must be a write-only operand, and
1307 operand_operand/src must be a read-only operand. */
1308 if (match.use[op_no] != READ
1309 || match.use[match_no] != WRITE)
1312 if (match.early_clobber[match_no]
1313 && count_occurrences (PATTERN (insn), src, 0) > 1)
1316 /* Make sure match_no is the destination. */
1317 if (recog_data.operand[match_no] != SET_DEST (set))
1320 if (REGNO (src) < FIRST_PSEUDO_REGISTER)
1322 if (GET_CODE (SET_SRC (set)) == PLUS
1323 && GET_CODE (XEXP (SET_SRC (set), 1)) == CONST_INT
1324 && XEXP (SET_SRC (set), 0) == src
1325 && fixup_match_2 (insn, dst, src,
1326 XEXP (SET_SRC (set), 1),
1331 src_class = reg_preferred_class (REGNO (src));
1332 dst_class = reg_preferred_class (REGNO (dst));
1334 if (! (src_note = find_reg_note (insn, REG_DEAD, src)))
1336 /* We used to force the copy here like in other cases, but
1337 it produces worse code, as it eliminates no copy
1338 instructions and the copy emitted will be produced by
1339 reload anyway. On patterns with multiple alternatives,
1340 there may be better sollution availble.
1342 In particular this change produced slower code for numeric
1348 if (! regclass_compatible_p (src_class, dst_class))
1358 /* Can not modify an earlier insn to set dst if this insn
1359 uses an old value in the source. */
1360 if (reg_overlap_mentioned_p (dst, SET_SRC (set)))
1370 /* If src is set once in a different basic block,
1371 and is set equal to a constant, then do not use
1372 it for this optimization, as this would make it
1373 no longer equivalent to a constant. */
1375 if (reg_is_remote_constant_p (src, insn, f))
1386 if (regmove_dump_file)
1387 fprintf (regmove_dump_file,
1388 "Could fix operand %d of insn %d matching operand %d.\n",
1389 op_no, INSN_UID (insn), match_no);
1391 /* Scan backward to find the first instruction that uses
1392 the input operand. If the operand is set here, then
1393 replace it in both instructions with match_no. */
1395 for (length = 0, p = PREV_INSN (insn); p; p = PREV_INSN (p))
1399 /* ??? We can't scan past the end of a basic block without
1400 updating the register lifetime info
1401 (REG_DEAD/basic_block_live_at_start). */
1402 if (perhaps_ends_bb_p (p))
1404 else if (! INSN_P (p))
1409 /* ??? See if all of SRC is set in P. This test is much
1410 more conservative than it needs to be. */
1411 pset = single_set (p);
1412 if (pset && SET_DEST (pset) == src)
1414 /* We use validate_replace_rtx, in case there
1415 are multiple identical source operands. All of
1416 them have to be changed at the same time. */
1417 if (validate_replace_rtx (src, dst, insn))
1419 if (validate_change (p, &SET_DEST (pset),
1424 /* Change all source operands back.
1425 This modifies the dst as a side-effect. */
1426 validate_replace_rtx (dst, src, insn);
1427 /* Now make sure the dst is right. */
1428 validate_change (insn,
1429 recog_data.operand_loc[match_no],
1436 if (reg_overlap_mentioned_p (src, PATTERN (p))
1437 || reg_overlap_mentioned_p (dst, PATTERN (p)))
1440 /* If we have passed a call instruction, and the
1441 pseudo-reg DST is not already live across a call,
1442 then don't perform the optimization. */
1443 if (GET_CODE (p) == CALL_INSN)
1447 if (REG_N_CALLS_CROSSED (REGNO (dst)) == 0)
1456 /* Remove the death note for SRC from INSN. */
1457 remove_note (insn, src_note);
1458 /* Move the death note for SRC to P if it is used
1460 if (reg_overlap_mentioned_p (src, PATTERN (p)))
1462 XEXP (src_note, 1) = REG_NOTES (p);
1463 REG_NOTES (p) = src_note;
1465 /* If there is a REG_DEAD note for DST on P, then remove
1466 it, because DST is now set there. */
1467 if ((dst_note = find_reg_note (p, REG_DEAD, dst)))
1468 remove_note (p, dst_note);
1470 dstno = REGNO (dst);
1471 srcno = REGNO (src);
1473 REG_N_SETS (dstno)++;
1474 REG_N_SETS (srcno)--;
1476 REG_N_CALLS_CROSSED (dstno) += num_calls;
1477 REG_N_CALLS_CROSSED (srcno) -= num_calls;
1479 REG_LIVE_LENGTH (dstno) += length;
1480 if (REG_LIVE_LENGTH (srcno) >= 0)
1482 REG_LIVE_LENGTH (srcno) -= length;
1483 /* REG_LIVE_LENGTH is only an approximation after
1484 combine if sched is not run, so make sure that we
1485 still have a reasonable value. */
1486 if (REG_LIVE_LENGTH (srcno) < 2)
1487 REG_LIVE_LENGTH (srcno) = 2;
1490 if (regmove_dump_file)
1491 fprintf (regmove_dump_file,
1492 "Fixed operand %d of insn %d matching operand %d.\n",
1493 op_no, INSN_UID (insn), match_no);
1499 /* If we weren't able to replace any of the alternatives, try an
1500 alternative appoach of copying the source to the destination. */
1501 if (!success && copy_src != NULL_RTX)
1502 copy_src_to_dest (insn, copy_src, copy_dst, old_max_uid);
1507 /* In fixup_match_1, some insns may have been inserted after basic block
1508 ends. Fix that here. */
1513 rtx next = NEXT_INSN (new);
1514 while (next != 0 && INSN_UID (next) >= old_max_uid
1515 && (bb->next_bb == EXIT_BLOCK_PTR || bb->next_bb->head != next))
1516 new = next, next = NEXT_INSN (new);
1522 free (regno_src_regno);
1523 free (regmove_bb_head);
1526 /* Returns nonzero if INSN's pattern has matching constraints for any operand.
1527 Returns 0 if INSN can't be recognized, or if the alternative can't be
1530 Initialize the info in MATCHP based on the constraints. */
1533 find_matches (insn, matchp)
1535 struct match *matchp;
1537 int likely_spilled[MAX_RECOG_OPERANDS];
1539 int any_matches = 0;
1541 extract_insn (insn);
1542 if (! constrain_operands (0))
1545 /* Must initialize this before main loop, because the code for
1546 the commutative case may set matches for operands other than
1548 for (op_no = recog_data.n_operands; --op_no >= 0; )
1549 matchp->with[op_no] = matchp->commutative[op_no] = -1;
1551 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1557 p = recog_data.constraints[op_no];
1559 likely_spilled[op_no] = 0;
1560 matchp->use[op_no] = READ;
1561 matchp->early_clobber[op_no] = 0;
1563 matchp->use[op_no] = WRITE;
1565 matchp->use[op_no] = READWRITE;
1567 for (;*p && i < which_alternative; p++)
1571 while ((c = *p++) != '\0' && c != ',')
1579 matchp->early_clobber[op_no] = 1;
1582 matchp->commutative[op_no] = op_no + 1;
1583 matchp->commutative[op_no + 1] = op_no;
1586 case '0': case '1': case '2': case '3': case '4':
1587 case '5': case '6': case '7': case '8': case '9':
1590 unsigned long match_ul = strtoul (p - 1, &end, 10);
1591 int match = match_ul;
1595 if (match < op_no && likely_spilled[match])
1597 matchp->with[op_no] = match;
1599 if (matchp->commutative[op_no] >= 0)
1600 matchp->with[matchp->commutative[op_no]] = match;
1604 case 'a': case 'b': case 'c': case 'd': case 'e': case 'f': case 'h':
1605 case 'j': case 'k': case 'l': case 'p': case 'q': case 't': case 'u':
1606 case 'v': case 'w': case 'x': case 'y': case 'z': case 'A': case 'B':
1607 case 'C': case 'D': case 'W': case 'Y': case 'Z':
1608 if (CLASS_LIKELY_SPILLED_P (REG_CLASS_FROM_LETTER ((unsigned char) c)))
1609 likely_spilled[op_no] = 1;
1616 /* Try to replace all occurrences of DST_REG with SRC in LOC, that is
1617 assumed to be in INSN. */
1620 replace_in_call_usage (loc, dst_reg, src, insn)
1622 unsigned int dst_reg;
1634 code = GET_CODE (x);
1637 if (REGNO (x) != dst_reg)
1640 validate_change (insn, loc, src, 1);
1645 /* Process each of our operands recursively. */
1646 fmt = GET_RTX_FORMAT (code);
1647 for (i = 0; i < GET_RTX_LENGTH (code); i++, fmt++)
1649 replace_in_call_usage (&XEXP (x, i), dst_reg, src, insn);
1650 else if (*fmt == 'E')
1651 for (j = 0; j < XVECLEN (x, i); j++)
1652 replace_in_call_usage (& XVECEXP (x, i, j), dst_reg, src, insn);
1655 /* Try to replace output operand DST in SET, with input operand SRC. SET is
1656 the only set in INSN. INSN has just been recognized and constrained.
1657 SRC is operand number OPERAND_NUMBER in INSN.
1658 DST is operand number MATCH_NUMBER in INSN.
1659 If BACKWARD is nonzero, we have been called in a backward pass.
1660 Return nonzero for success. */
1663 fixup_match_1 (insn, set, src, src_subreg, dst, backward, operand_number,
1664 match_number, regmove_dump_file)
1665 rtx insn, set, src, src_subreg, dst;
1666 int backward, operand_number, match_number;
1667 FILE *regmove_dump_file;
1670 rtx post_inc = 0, post_inc_set = 0, search_end = 0;
1672 int num_calls = 0, s_num_calls = 0;
1673 enum rtx_code code = NOTE;
1674 HOST_WIDE_INT insn_const = 0, newconst;
1675 rtx overlap = 0; /* need to move insn ? */
1676 rtx src_note = find_reg_note (insn, REG_DEAD, src), dst_note = NULL_RTX;
1677 int length, s_length;
1679 /* If SRC is marked as unchanging, we may not change it.
1680 ??? Maybe we could get better code by removing the unchanging bit
1681 instead, and changing it back if we don't succeed? */
1682 if (RTX_UNCHANGING_P (src))
1687 /* Look for (set (regX) (op regA constX))
1688 (set (regY) (op regA constY))
1690 (set (regA) (op regA constX)).
1691 (set (regY) (op regA constY-constX)).
1692 This works for add and shift operations, if
1693 regA is dead after or set by the second insn. */
1695 code = GET_CODE (SET_SRC (set));
1696 if ((code == PLUS || code == LSHIFTRT
1697 || code == ASHIFT || code == ASHIFTRT)
1698 && XEXP (SET_SRC (set), 0) == src
1699 && GET_CODE (XEXP (SET_SRC (set), 1)) == CONST_INT)
1700 insn_const = INTVAL (XEXP (SET_SRC (set), 1));
1701 else if (! stable_and_no_regs_but_for_p (SET_SRC (set), src, dst))
1704 /* We might find a src_note while scanning. */
1708 if (regmove_dump_file)
1709 fprintf (regmove_dump_file,
1710 "Could fix operand %d of insn %d matching operand %d.\n",
1711 operand_number, INSN_UID (insn), match_number);
1713 /* If SRC is equivalent to a constant set in a different basic block,
1714 then do not use it for this optimization. We want the equivalence
1715 so that if we have to reload this register, we can reload the
1716 constant, rather than extending the lifespan of the register. */
1717 if (reg_is_remote_constant_p (src, insn, get_insns ()))
1720 /* Scan forward to find the next instruction that
1721 uses the output operand. If the operand dies here,
1722 then replace it in both instructions with
1725 for (length = s_length = 0, p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
1727 if (GET_CODE (p) == CALL_INSN)
1728 replace_in_call_usage (& CALL_INSN_FUNCTION_USAGE (p),
1729 REGNO (dst), src, p);
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 if (perhaps_ends_bb_p (p))
1735 else if (! INSN_P (p))
1742 if (reg_set_p (src, p) || reg_set_p (dst, p)
1743 || (GET_CODE (PATTERN (p)) == USE
1744 && reg_overlap_mentioned_p (src, XEXP (PATTERN (p), 0))))
1747 /* See if all of DST dies in P. This test is
1748 slightly more conservative than it needs to be. */
1749 if ((dst_note = find_regno_note (p, REG_DEAD, REGNO (dst)))
1750 && (GET_MODE (XEXP (dst_note, 0)) == GET_MODE (dst)))
1752 /* If we would be moving INSN, check that we won't move it
1753 into the shadow of a live a live flags register. */
1754 /* ??? We only try to move it in front of P, although
1755 we could move it anywhere between OVERLAP and P. */
1756 if (overlap && GET_MODE (PREV_INSN (p)) != VOIDmode)
1762 rtx set2 = NULL_RTX;
1764 /* If an optimization is done, the value of SRC while P
1765 is executed will be changed. Check that this is OK. */
1766 if (reg_overlap_mentioned_p (src, PATTERN (p)))
1768 for (q = p; q; q = NEXT_INSN (q))
1770 /* ??? We can't scan past the end of a basic block without
1771 updating the register lifetime info
1772 (REG_DEAD/basic_block_live_at_start). */
1773 if (perhaps_ends_bb_p (q))
1778 else if (! INSN_P (q))
1780 else if (reg_overlap_mentioned_p (src, PATTERN (q))
1781 || reg_set_p (src, q))
1785 set2 = single_set (q);
1786 if (! q || ! set2 || GET_CODE (SET_SRC (set2)) != code
1787 || XEXP (SET_SRC (set2), 0) != src
1788 || GET_CODE (XEXP (SET_SRC (set2), 1)) != CONST_INT
1789 || (SET_DEST (set2) != src
1790 && ! find_reg_note (q, REG_DEAD, src)))
1792 /* If this is a PLUS, we can still save a register by doing
1795 src -= insn_const; .
1796 This also gives opportunities for subsequent
1797 optimizations in the backward pass, so do it there. */
1798 if (code == PLUS && backward
1799 /* Don't do this if we can likely tie DST to SET_DEST
1800 of P later; we can't do this tying here if we got a
1802 && ! (dst_note && ! REG_N_CALLS_CROSSED (REGNO (dst))
1804 && GET_CODE (SET_DEST (single_set (p))) == REG
1805 && (REGNO (SET_DEST (single_set (p)))
1806 < FIRST_PSEUDO_REGISTER))
1807 /* We may only emit an insn directly after P if we
1808 are not in the shadow of a live flags register. */
1809 && GET_MODE (p) == VOIDmode)
1814 newconst = -insn_const;
1822 newconst = INTVAL (XEXP (SET_SRC (set2), 1)) - insn_const;
1823 /* Reject out of range shifts. */
1826 || ((unsigned HOST_WIDE_INT) newconst
1827 >= (GET_MODE_BITSIZE (GET_MODE
1828 (SET_SRC (set2)))))))
1833 if (SET_DEST (set2) != src)
1834 post_inc_set = set2;
1837 /* We use 1 as last argument to validate_change so that all
1838 changes are accepted or rejected together by apply_change_group
1839 when it is called by validate_replace_rtx . */
1840 validate_change (q, &XEXP (SET_SRC (set2), 1),
1841 GEN_INT (newconst), 1);
1843 validate_change (insn, recog_data.operand_loc[match_number], src, 1);
1844 if (validate_replace_rtx (dst, src_subreg, p))
1849 if (reg_overlap_mentioned_p (dst, PATTERN (p)))
1851 if (! src_note && reg_overlap_mentioned_p (src, PATTERN (p)))
1853 /* INSN was already checked to be movable wrt. the registers that it
1854 sets / uses when we found no REG_DEAD note for src on it, but it
1855 still might clobber the flags register. We'll have to check that
1856 we won't insert it into the shadow of a live flags register when
1857 we finally know where we are to move it. */
1859 src_note = find_reg_note (p, REG_DEAD, src);
1862 /* If we have passed a call instruction, and the pseudo-reg SRC is not
1863 already live across a call, then don't perform the optimization. */
1864 if (GET_CODE (p) == CALL_INSN)
1866 if (REG_N_CALLS_CROSSED (REGNO (src)) == 0)
1880 /* Remove the death note for DST from P. */
1881 remove_note (p, dst_note);
1884 post_inc = emit_insn_after (copy_rtx (PATTERN (insn)), p);
1885 if ((HAVE_PRE_INCREMENT || HAVE_PRE_DECREMENT)
1887 && try_auto_increment (search_end, post_inc, 0, src, newconst, 1))
1889 validate_change (insn, &XEXP (SET_SRC (set), 1), GEN_INT (insn_const), 0);
1890 REG_N_SETS (REGNO (src))++;
1891 REG_LIVE_LENGTH (REGNO (src))++;
1895 /* The lifetime of src and dest overlap,
1896 but we can change this by moving insn. */
1897 rtx pat = PATTERN (insn);
1899 remove_note (overlap, src_note);
1900 if ((HAVE_POST_INCREMENT || HAVE_POST_DECREMENT)
1902 && try_auto_increment (overlap, insn, 0, src, insn_const, 0))
1906 rtx notes = REG_NOTES (insn);
1908 emit_insn_after_with_line_notes (pat, PREV_INSN (p), insn);
1910 /* emit_insn_after_with_line_notes has no
1911 return value, so search for the new insn. */
1913 while (! INSN_P (insn) || PATTERN (insn) != pat)
1914 insn = PREV_INSN (insn);
1916 REG_NOTES (insn) = notes;
1919 /* Sometimes we'd generate src = const; src += n;
1920 if so, replace the instruction that set src
1921 in the first place. */
1923 if (! overlap && (code == PLUS || code == MINUS))
1925 rtx note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
1926 rtx q, set2 = NULL_RTX;
1927 int num_calls2 = 0, s_length2 = 0;
1929 if (note && CONSTANT_P (XEXP (note, 0)))
1931 for (q = PREV_INSN (insn); q; q = PREV_INSN (q))
1933 /* ??? We can't scan past the end of a basic block without
1934 updating the register lifetime info
1935 (REG_DEAD/basic_block_live_at_start). */
1936 if (perhaps_ends_bb_p (q))
1941 else if (! INSN_P (q))
1945 if (reg_set_p (src, q))
1947 set2 = single_set (q);
1950 if (reg_overlap_mentioned_p (src, PATTERN (q)))
1955 if (GET_CODE (p) == CALL_INSN)
1958 if (q && set2 && SET_DEST (set2) == src && CONSTANT_P (SET_SRC (set2))
1959 && validate_change (insn, &SET_SRC (set), XEXP (note, 0), 0))
1962 REG_N_SETS (REGNO (src))--;
1963 REG_N_CALLS_CROSSED (REGNO (src)) -= num_calls2;
1964 REG_LIVE_LENGTH (REGNO (src)) -= s_length2;
1970 if ((HAVE_PRE_INCREMENT || HAVE_PRE_DECREMENT)
1971 && (code == PLUS || code == MINUS) && insn_const
1972 && try_auto_increment (p, insn, 0, src, insn_const, 1))
1974 else if ((HAVE_POST_INCREMENT || HAVE_POST_DECREMENT)
1976 && try_auto_increment (p, post_inc, post_inc_set, src, newconst, 0))
1978 /* If post_inc still prevails, try to find an
1979 insn where it can be used as a pre-in/decrement.
1980 If code is MINUS, this was already tried. */
1981 if (post_inc && code == PLUS
1982 /* Check that newconst is likely to be usable
1983 in a pre-in/decrement before starting the search. */
1984 && ((HAVE_PRE_INCREMENT && newconst > 0 && newconst <= MOVE_MAX)
1985 || (HAVE_PRE_DECREMENT && newconst < 0 && newconst >= -MOVE_MAX))
1986 && exact_log2 (newconst))
1990 inc_dest = post_inc_set ? SET_DEST (post_inc_set) : src;
1991 for (q = post_inc; (q = NEXT_INSN (q)); )
1993 /* ??? We can't scan past the end of a basic block without updating
1994 the register lifetime info
1995 (REG_DEAD/basic_block_live_at_start). */
1996 if (perhaps_ends_bb_p (q))
1998 else if (! INSN_P (q))
2000 else if (src != inc_dest
2001 && (reg_overlap_mentioned_p (src, PATTERN (q))
2002 || reg_set_p (src, q)))
2004 else if (reg_set_p (inc_dest, q))
2006 else if (reg_overlap_mentioned_p (inc_dest, PATTERN (q)))
2008 try_auto_increment (q, post_inc,
2009 post_inc_set, inc_dest, newconst, 1);
2015 /* Move the death note for DST to INSN if it is used
2017 if (reg_overlap_mentioned_p (dst, PATTERN (insn)))
2019 XEXP (dst_note, 1) = REG_NOTES (insn);
2020 REG_NOTES (insn) = dst_note;
2025 /* Move the death note for SRC from INSN to P. */
2027 remove_note (insn, src_note);
2028 XEXP (src_note, 1) = REG_NOTES (p);
2029 REG_NOTES (p) = src_note;
2031 REG_N_CALLS_CROSSED (REGNO (src)) += s_num_calls;
2034 REG_N_SETS (REGNO (src))++;
2035 REG_N_SETS (REGNO (dst))--;
2037 REG_N_CALLS_CROSSED (REGNO (dst)) -= num_calls;
2039 REG_LIVE_LENGTH (REGNO (src)) += s_length;
2040 if (REG_LIVE_LENGTH (REGNO (dst)) >= 0)
2042 REG_LIVE_LENGTH (REGNO (dst)) -= length;
2043 /* REG_LIVE_LENGTH is only an approximation after
2044 combine if sched is not run, so make sure that we
2045 still have a reasonable value. */
2046 if (REG_LIVE_LENGTH (REGNO (dst)) < 2)
2047 REG_LIVE_LENGTH (REGNO (dst)) = 2;
2049 if (regmove_dump_file)
2050 fprintf (regmove_dump_file,
2051 "Fixed operand %d of insn %d matching operand %d.\n",
2052 operand_number, INSN_UID (insn), match_number);
2057 /* return nonzero if X is stable and mentions no regsiters but for
2058 mentioning SRC or mentioning / changing DST . If in doubt, presume
2060 The rationale is that we want to check if we can move an insn easily
2061 while just paying attention to SRC and DST. A register is considered
2062 stable if it has the RTX_UNCHANGING_P bit set, but that would still
2063 leave the burden to update REG_DEAD / REG_UNUSED notes, so we don't
2064 want any registers but SRC and DST. */
2066 stable_and_no_regs_but_for_p (x, src, dst)
2069 RTX_CODE code = GET_CODE (x);
2070 switch (GET_RTX_CLASS (code))
2072 case '<': case '1': case 'c': case '2': case 'b': case '3':
2075 const char *fmt = GET_RTX_FORMAT (code);
2076 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2078 && ! stable_and_no_regs_but_for_p (XEXP (x, i), src, dst))
2084 return x == src || x == dst;
2085 /* If this is a MEM, look inside - there might be a register hidden in
2086 the address of an unchanging MEM. */
2088 && ! stable_and_no_regs_but_for_p (XEXP (x, 0), src, dst))
2092 return ! rtx_unstable_p (x);
2096 /* Track stack adjustments and stack memory references. Attempt to
2097 reduce the number of stack adjustments by back-propagating across
2098 the memory references.
2100 This is intended primarily for use with targets that do not define
2101 ACCUMULATE_OUTGOING_ARGS. It is of significantly more value to
2102 targets that define PREFERRED_STACK_BOUNDARY more aligned than
2103 STACK_BOUNDARY (e.g. x86), or if not all registers can be pushed
2104 (e.g. x86 fp regs) which would ordinarily have to be implemented
2105 as a sub/mov pair due to restrictions in calls.c.
2107 Propagation stops when any of the insns that need adjusting are
2108 (a) no longer valid because we've exceeded their range, (b) a
2109 non-trivial push instruction, or (c) a call instruction.
2111 Restriction B is based on the assumption that push instructions
2112 are smaller or faster. If a port really wants to remove all
2113 pushes, it should have defined ACCUMULATE_OUTGOING_ARGS. The
2114 one exception that is made is for an add immediately followed
2117 /* This structure records stack memory references between stack adjusting
2122 HOST_WIDE_INT sp_offset;
2124 struct csa_memlist *next;
2127 static int stack_memref_p PARAMS ((rtx));
2128 static rtx single_set_for_csa PARAMS ((rtx));
2129 static void free_csa_memlist PARAMS ((struct csa_memlist *));
2130 static struct csa_memlist *record_one_stack_memref
2131 PARAMS ((rtx, rtx *, struct csa_memlist *));
2132 static int try_apply_stack_adjustment
2133 PARAMS ((rtx, struct csa_memlist *, HOST_WIDE_INT, HOST_WIDE_INT));
2134 static void combine_stack_adjustments_for_block PARAMS ((basic_block));
2135 static int record_stack_memrefs PARAMS ((rtx *, void *));
2138 /* Main entry point for stack adjustment combination. */
2141 combine_stack_adjustments ()
2146 combine_stack_adjustments_for_block (bb);
2149 /* Recognize a MEM of the form (sp) or (plus sp const). */
2155 if (GET_CODE (x) != MEM)
2159 if (x == stack_pointer_rtx)
2161 if (GET_CODE (x) == PLUS
2162 && XEXP (x, 0) == stack_pointer_rtx
2163 && GET_CODE (XEXP (x, 1)) == CONST_INT)
2169 /* Recognize either normal single_set or the hack in i386.md for
2170 tying fp and sp adjustments. */
2173 single_set_for_csa (insn)
2177 rtx tmp = single_set (insn);
2181 if (GET_CODE (insn) != INSN
2182 || GET_CODE (PATTERN (insn)) != PARALLEL)
2185 tmp = PATTERN (insn);
2186 if (GET_CODE (XVECEXP (tmp, 0, 0)) != SET)
2189 for (i = 1; i < XVECLEN (tmp, 0); ++i)
2191 rtx this = XVECEXP (tmp, 0, i);
2193 /* The special case is allowing a no-op set. */
2194 if (GET_CODE (this) == SET
2195 && SET_SRC (this) == SET_DEST (this))
2197 else if (GET_CODE (this) != CLOBBER
2198 && GET_CODE (this) != USE)
2202 return XVECEXP (tmp, 0, 0);
2205 /* Free the list of csa_memlist nodes. */
2208 free_csa_memlist (memlist)
2209 struct csa_memlist *memlist;
2211 struct csa_memlist *next;
2212 for (; memlist ; memlist = next)
2214 next = memlist->next;
2219 /* Create a new csa_memlist node from the given memory reference.
2220 It is already known that the memory is stack_memref_p. */
2222 static struct csa_memlist *
2223 record_one_stack_memref (insn, mem, next_memlist)
2225 struct csa_memlist *next_memlist;
2227 struct csa_memlist *ml;
2229 ml = (struct csa_memlist *) xmalloc (sizeof (*ml));
2231 if (XEXP (*mem, 0) == stack_pointer_rtx)
2234 ml->sp_offset = INTVAL (XEXP (XEXP (*mem, 0), 1));
2238 ml->next = next_memlist;
2243 /* Attempt to apply ADJUST to the stack adjusting insn INSN, as well
2244 as each of the memories in MEMLIST. Return true on success. */
2247 try_apply_stack_adjustment (insn, memlist, new_adjust, delta)
2249 struct csa_memlist *memlist;
2250 HOST_WIDE_INT new_adjust, delta;
2252 struct csa_memlist *ml;
2255 set = single_set_for_csa (insn);
2256 validate_change (insn, &XEXP (SET_SRC (set), 1), GEN_INT (new_adjust), 1);
2258 for (ml = memlist; ml ; ml = ml->next)
2261 replace_equiv_address_nv (*ml->mem,
2262 plus_constant (stack_pointer_rtx,
2263 ml->sp_offset - delta)), 1);
2265 if (apply_change_group ())
2267 /* Succeeded. Update our knowledge of the memory references. */
2268 for (ml = memlist; ml ; ml = ml->next)
2269 ml->sp_offset -= delta;
2277 /* Called via for_each_rtx and used to record all stack memory references in
2278 the insn and discard all other stack pointer references. */
2279 struct record_stack_memrefs_data
2282 struct csa_memlist *memlist;
2286 record_stack_memrefs (xp, data)
2291 struct record_stack_memrefs_data *d =
2292 (struct record_stack_memrefs_data *) data;
2295 switch (GET_CODE (x))
2298 if (!reg_mentioned_p (stack_pointer_rtx, x))
2300 /* We are not able to handle correctly all possible memrefs containing
2301 stack pointer, so this check is necessary. */
2302 if (stack_memref_p (x))
2304 d->memlist = record_one_stack_memref (d->insn, xp, d->memlist);
2309 /* ??? We want be able to handle non-memory stack pointer
2310 references later. For now just discard all insns refering to
2311 stack pointer outside mem expressions. We would probably
2312 want to teach validate_replace to simplify expressions first.
2314 We can't just compare with STACK_POINTER_RTX because the
2315 reference to the stack pointer might be in some other mode.
2316 In particular, an explict clobber in an asm statement will
2317 result in a QImode clober. */
2318 if (REGNO (x) == STACK_POINTER_REGNUM)
2327 /* Subroutine of combine_stack_adjustments, called for each basic block. */
2330 combine_stack_adjustments_for_block (bb)
2333 HOST_WIDE_INT last_sp_adjust = 0;
2334 rtx last_sp_set = NULL_RTX;
2335 struct csa_memlist *memlist = NULL;
2336 rtx insn, next, set;
2337 struct record_stack_memrefs_data data;
2338 bool end_of_block = false;
2340 for (insn = bb->head; !end_of_block ; insn = next)
2342 end_of_block = insn == bb->end;
2343 next = NEXT_INSN (insn);
2345 if (! INSN_P (insn))
2348 set = single_set_for_csa (insn);
2351 rtx dest = SET_DEST (set);
2352 rtx src = SET_SRC (set);
2354 /* Find constant additions to the stack pointer. */
2355 if (dest == stack_pointer_rtx
2356 && GET_CODE (src) == PLUS
2357 && XEXP (src, 0) == stack_pointer_rtx
2358 && GET_CODE (XEXP (src, 1)) == CONST_INT)
2360 HOST_WIDE_INT this_adjust = INTVAL (XEXP (src, 1));
2362 /* If we've not seen an adjustment previously, record
2363 it now and continue. */
2367 last_sp_adjust = this_adjust;
2371 /* If not all recorded memrefs can be adjusted, or the
2372 adjustment is now too large for a constant addition,
2373 we cannot merge the two stack adjustments.
2375 Also we need to be carefull to not move stack pointer
2376 such that we create stack accesses outside the allocated
2377 area. We can combine an allocation into the first insn,
2378 or a deallocation into the second insn. We can not
2379 combine an allocation followed by a deallocation.
2381 The only somewhat frequent occurrence of the later is when
2382 a function allocates a stack frame but does not use it.
2383 For this case, we would need to analyze rtl stream to be
2384 sure that allocated area is really unused. This means not
2385 only checking the memory references, but also all registers
2386 or global memory references possibly containing a stack
2389 Perhaps the best way to address this problem is to teach
2390 gcc not to allocate stack for objects never used. */
2392 /* Combine an allocation into the first instruction. */
2393 if (STACK_GROWS_DOWNWARD ? this_adjust <= 0 : this_adjust >= 0)
2395 if (try_apply_stack_adjustment (last_sp_set, memlist,
2396 last_sp_adjust + this_adjust,
2401 last_sp_adjust += this_adjust;
2406 /* Otherwise we have a deallocation. Do not combine with
2407 a previous allocation. Combine into the second insn. */
2408 else if (STACK_GROWS_DOWNWARD
2409 ? last_sp_adjust >= 0 : last_sp_adjust <= 0)
2411 if (try_apply_stack_adjustment (insn, memlist,
2412 last_sp_adjust + this_adjust,
2416 delete_insn (last_sp_set);
2418 last_sp_adjust += this_adjust;
2419 free_csa_memlist (memlist);
2425 /* Combination failed. Restart processing from here. If
2426 deallocation+allocation conspired to cancel, we can
2427 delete the old deallocation insn. */
2428 if (last_sp_set && last_sp_adjust == 0)
2430 free_csa_memlist (memlist);
2433 last_sp_adjust = this_adjust;
2437 /* Find a predecrement of exactly the previous adjustment and
2438 turn it into a direct store. Obviously we can't do this if
2439 there were any intervening uses of the stack pointer. */
2441 && GET_CODE (dest) == MEM
2442 && ((GET_CODE (XEXP (dest, 0)) == PRE_DEC
2444 == (HOST_WIDE_INT) GET_MODE_SIZE (GET_MODE (dest))))
2445 || (GET_CODE (XEXP (dest, 0)) == PRE_MODIFY
2446 && GET_CODE (XEXP (XEXP (dest, 0), 1)) == PLUS
2447 && XEXP (XEXP (XEXP (dest, 0), 1), 0) == stack_pointer_rtx
2448 && (GET_CODE (XEXP (XEXP (XEXP (dest, 0), 1), 1))
2450 && (INTVAL (XEXP (XEXP (XEXP (dest, 0), 1), 1))
2451 == -last_sp_adjust)))
2452 && XEXP (XEXP (dest, 0), 0) == stack_pointer_rtx
2453 && ! reg_mentioned_p (stack_pointer_rtx, src)
2454 && memory_address_p (GET_MODE (dest), stack_pointer_rtx)
2455 && validate_change (insn, &SET_DEST (set),
2456 replace_equiv_address (dest,
2460 delete_insn (last_sp_set);
2461 free_csa_memlist (memlist);
2463 last_sp_set = NULL_RTX;
2470 data.memlist = memlist;
2471 if (GET_CODE (insn) != CALL_INSN && last_sp_set
2472 && !for_each_rtx (&PATTERN (insn), record_stack_memrefs, &data))
2474 memlist = data.memlist;
2477 memlist = data.memlist;
2479 /* Otherwise, we were not able to process the instruction.
2480 Do not continue collecting data across such a one. */
2482 && (GET_CODE (insn) == CALL_INSN
2483 || reg_mentioned_p (stack_pointer_rtx, PATTERN (insn))))
2485 if (last_sp_set && last_sp_adjust == 0)
2486 delete_insn (last_sp_set);
2487 free_csa_memlist (memlist);
2489 last_sp_set = NULL_RTX;
2494 if (last_sp_set && last_sp_adjust == 0)
2495 delete_insn (last_sp_set);
OSDN Git Service
