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 non-zero 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 (block = n_basic_blocks - 1; block >= 0; block--)
262 insn = BLOCK_HEAD (block);
263 end = BLOCK_END (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 (BASIC_BLOCK (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_SETS (src_no) != 1)
669 for (p = PREV_INSN (insn); p && ! reg_set_p (src_reg, p); p = PREV_INSN (p))
670 /* ??? We can't scan past the end of a basic block without updating
671 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
672 if (perhaps_ends_bb_p (p))
678 if (! (set = single_set (p))
679 || GET_CODE (SET_SRC (set)) != MEM
680 /* If there's a REG_EQUIV note, this must be an insn that loads an
681 argument. Prefer keeping the note over doing this optimization. */
682 || find_reg_note (p, REG_EQUIV, NULL_RTX)
683 || SET_DEST (set) != src_reg)
686 /* Be conserative: although this optimization is also valid for
687 volatile memory references, that could cause trouble in later passes. */
688 if (MEM_VOLATILE_P (SET_SRC (set)))
691 /* Do not use a SUBREG to truncate from one mode to another if truncation
693 if (GET_MODE_BITSIZE (GET_MODE (src_reg)) <= GET_MODE_BITSIZE (GET_MODE (src))
694 && !TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (GET_MODE (src)),
695 GET_MODE_BITSIZE (GET_MODE (src_reg))))
698 old_mode = GET_MODE (src_reg);
699 PUT_MODE (src_reg, GET_MODE (src));
700 XEXP (src, 0) = SET_SRC (set);
702 /* Include this change in the group so that it's easily undone if
703 one of the changes in the group is invalid. */
704 validate_change (p, &SET_SRC (set), src, 1);
706 /* Now walk forward making additional replacements. We want to be able
707 to undo all the changes if a later substitution fails. */
708 subreg = gen_lowpart_SUBREG (old_mode, src_reg);
709 while (p = NEXT_INSN (p), p != insn)
714 /* Make a tenative change. */
715 validate_replace_rtx_group (src_reg, subreg, p);
718 validate_replace_rtx_group (src, src_reg, insn);
720 /* Now see if all the changes are valid. */
721 if (! apply_change_group ())
723 /* One or more changes were no good. Back out everything. */
724 PUT_MODE (src_reg, old_mode);
725 XEXP (src, 0) = src_reg;
729 rtx note = find_reg_note (p, REG_EQUAL, NULL_RTX);
731 remove_note (p, note);
736 /* If we were not able to update the users of src to use dest directly, try
737 instead moving the value to dest directly before the operation. */
740 copy_src_to_dest (insn, src, dest, old_max_uid)
759 /* A REG_LIVE_LENGTH of -1 indicates the register is equivalent to a constant
760 or memory location and is used infrequently; a REG_LIVE_LENGTH of -2 is
761 parameter when there is no frame pointer that is not allocated a register.
762 For now, we just reject them, rather than incrementing the live length. */
764 if (GET_CODE (src) == REG
765 && REG_LIVE_LENGTH (REGNO (src)) > 0
766 && GET_CODE (dest) == REG
767 && !RTX_UNCHANGING_P (dest)
768 && REG_LIVE_LENGTH (REGNO (dest)) > 0
769 && (set = single_set (insn)) != NULL_RTX
770 && !reg_mentioned_p (dest, SET_SRC (set))
771 && GET_MODE (src) == GET_MODE (dest))
773 int old_num_regs = reg_rtx_no;
775 /* Generate the src->dest move. */
777 emit_move_insn (dest, src);
778 seq = gen_sequence ();
780 /* If this sequence uses new registers, we may not use it. */
781 if (old_num_regs != reg_rtx_no
782 || ! validate_replace_rtx (src, dest, insn))
784 /* We have to restore reg_rtx_no to its old value, lest
785 recompute_reg_usage will try to compute the usage of the
786 new regs, yet reg_n_info is not valid for them. */
787 reg_rtx_no = old_num_regs;
790 emit_insn_before (seq, insn);
791 move_insn = PREV_INSN (insn);
792 p_move_notes = ®_NOTES (move_insn);
793 p_insn_notes = ®_NOTES (insn);
795 /* Move any notes mentioning src to the move instruction */
796 for (link = REG_NOTES (insn); link != NULL_RTX; link = next)
798 next = XEXP (link, 1);
799 if (XEXP (link, 0) == src)
801 *p_move_notes = link;
802 p_move_notes = &XEXP (link, 1);
806 *p_insn_notes = link;
807 p_insn_notes = &XEXP (link, 1);
811 *p_move_notes = NULL_RTX;
812 *p_insn_notes = NULL_RTX;
814 /* Is the insn the head of a basic block? If so extend it */
815 insn_uid = INSN_UID (insn);
816 move_uid = INSN_UID (move_insn);
817 if (insn_uid < old_max_uid)
819 bb = regmove_bb_head[insn_uid];
822 BLOCK_HEAD (bb) = move_insn;
823 regmove_bb_head[insn_uid] = -1;
827 /* Update the various register tables. */
828 dest_regno = REGNO (dest);
829 REG_N_SETS (dest_regno) ++;
830 REG_LIVE_LENGTH (dest_regno)++;
831 if (REGNO_FIRST_UID (dest_regno) == insn_uid)
832 REGNO_FIRST_UID (dest_regno) = move_uid;
834 src_regno = REGNO (src);
835 if (! find_reg_note (move_insn, REG_DEAD, src))
836 REG_LIVE_LENGTH (src_regno)++;
838 if (REGNO_FIRST_UID (src_regno) == insn_uid)
839 REGNO_FIRST_UID (src_regno) = move_uid;
841 if (REGNO_LAST_UID (src_regno) == insn_uid)
842 REGNO_LAST_UID (src_regno) = move_uid;
844 if (REGNO_LAST_NOTE_UID (src_regno) == insn_uid)
845 REGNO_LAST_NOTE_UID (src_regno) = move_uid;
850 /* Return whether REG is set in only one location, and is set to a
851 constant, but is set in a different basic block from INSN (an
852 instructions which uses REG). In this case REG is equivalent to a
853 constant, and we don't want to break that equivalence, because that
854 may increase register pressure and make reload harder. If REG is
855 set in the same basic block as INSN, we don't worry about it,
856 because we'll probably need a register anyhow (??? but what if REG
857 is used in a different basic block as well as this one?). FIRST is
858 the first insn in the function. */
861 reg_is_remote_constant_p (reg, insn, first)
868 if (REG_N_SETS (REGNO (reg)) != 1)
871 /* Look for the set. */
872 for (p = LOG_LINKS (insn); p; p = XEXP (p, 1))
876 if (REG_NOTE_KIND (p) != 0)
878 s = single_set (XEXP (p, 0));
880 && GET_CODE (SET_DEST (s)) == REG
881 && REGNO (SET_DEST (s)) == REGNO (reg))
883 /* The register is set in the same basic block. */
888 for (p = first; p && p != insn; p = NEXT_INSN (p))
896 && GET_CODE (SET_DEST (s)) == REG
897 && REGNO (SET_DEST (s)) == REGNO (reg))
899 /* This is the instruction which sets REG. If there is a
900 REG_EQUAL note, then REG is equivalent to a constant. */
901 if (find_reg_note (p, REG_EQUAL, NULL_RTX))
910 /* INSN is adding a CONST_INT to a REG. We search backwards looking for
911 another add immediate instruction with the same source and dest registers,
912 and if we find one, we change INSN to an increment, and return 1. If
913 no changes are made, we return 0.
916 (set (reg100) (plus reg1 offset1))
918 (set (reg100) (plus reg1 offset2))
920 (set (reg100) (plus reg1 offset1))
922 (set (reg100) (plus reg100 offset2-offset1)) */
924 /* ??? What does this comment mean? */
925 /* cse disrupts preincrement / postdecrement squences when it finds a
926 hard register as ultimate source, like the frame pointer. */
929 fixup_match_2 (insn, dst, src, offset, regmove_dump_file)
930 rtx insn, dst, src, offset;
931 FILE *regmove_dump_file;
933 rtx p, dst_death = 0;
934 int length, num_calls = 0;
936 /* If SRC dies in INSN, we'd have to move the death note. This is
937 considered to be very unlikely, so we just skip the optimization
939 if (find_regno_note (insn, REG_DEAD, REGNO (src)))
942 /* Scan backward to find the first instruction that sets DST. */
944 for (length = 0, p = PREV_INSN (insn); p; p = PREV_INSN (p))
948 /* ??? We can't scan past the end of a basic block without updating
949 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
950 if (perhaps_ends_bb_p (p))
952 else if (! INSN_P (p))
955 if (find_regno_note (p, REG_DEAD, REGNO (dst)))
960 pset = single_set (p);
961 if (pset && SET_DEST (pset) == dst
962 && GET_CODE (SET_SRC (pset)) == PLUS
963 && XEXP (SET_SRC (pset), 0) == src
964 && GET_CODE (XEXP (SET_SRC (pset), 1)) == CONST_INT)
966 HOST_WIDE_INT newconst
967 = INTVAL (offset) - INTVAL (XEXP (SET_SRC (pset), 1));
968 rtx add = gen_add3_insn (dst, dst, GEN_INT (newconst));
970 if (add && validate_change (insn, &PATTERN (insn), add, 0))
972 /* Remove the death note for DST from DST_DEATH. */
975 remove_death (REGNO (dst), dst_death);
976 REG_LIVE_LENGTH (REGNO (dst)) += length;
977 REG_N_CALLS_CROSSED (REGNO (dst)) += num_calls;
980 if (regmove_dump_file)
981 fprintf (regmove_dump_file,
982 "Fixed operand of insn %d.\n",
986 for (p = PREV_INSN (insn); p; p = PREV_INSN (p))
988 if (GET_CODE (p) == CODE_LABEL
989 || GET_CODE (p) == JUMP_INSN)
993 if (reg_overlap_mentioned_p (dst, PATTERN (p)))
995 if (try_auto_increment (p, insn, 0, dst, newconst, 0))
1000 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
1002 if (GET_CODE (p) == CODE_LABEL
1003 || GET_CODE (p) == JUMP_INSN)
1007 if (reg_overlap_mentioned_p (dst, PATTERN (p)))
1009 try_auto_increment (p, insn, 0, dst, newconst, 1);
1018 if (reg_set_p (dst, PATTERN (p)))
1021 /* If we have passed a call instruction, and the
1022 pseudo-reg SRC is not already live across a call,
1023 then don't perform the optimization. */
1024 /* reg_set_p is overly conservative for CALL_INSNS, thinks that all
1025 hard regs are clobbered. Thus, we only use it for src for
1027 if (GET_CODE (p) == CALL_INSN)
1032 if (REG_N_CALLS_CROSSED (REGNO (src)) == 0)
1035 if (call_used_regs [REGNO (dst)]
1036 || find_reg_fusage (p, CLOBBER, dst))
1039 else if (reg_set_p (src, PATTERN (p)))
1046 /* Main entry for the register move optimization.
1047 F is the first instruction.
1048 NREGS is one plus the highest pseudo-reg number used in the instruction.
1049 REGMOVE_DUMP_FILE is a stream for output of a trace of actions taken
1050 (or 0 if none should be output). */
1053 regmove_optimize (f, nregs, regmove_dump_file)
1056 FILE *regmove_dump_file;
1058 int old_max_uid = get_max_uid ();
1063 rtx copy_src, copy_dst;
1065 /* ??? Hack. Regmove doesn't examine the CFG, and gets mightily
1066 confused by non-call exceptions ending blocks. */
1067 if (flag_non_call_exceptions)
1070 /* Find out where a potential flags register is live, and so that we
1071 can supress some optimizations in those zones. */
1072 mark_flags_life_zones (discover_flags_reg ());
1074 regno_src_regno = (int *) xmalloc (sizeof *regno_src_regno * nregs);
1075 for (i = nregs; --i >= 0; ) regno_src_regno[i] = -1;
1077 regmove_bb_head = (int *) xmalloc (sizeof (int) * (old_max_uid + 1));
1078 for (i = old_max_uid; i >= 0; i--) regmove_bb_head[i] = -1;
1079 for (i = 0; i < n_basic_blocks; i++)
1080 regmove_bb_head[INSN_UID (BLOCK_HEAD (i))] = i;
1082 /* A forward/backward pass. Replace output operands with input operands. */
1084 for (pass = 0; pass <= 2; pass++)
1086 if (! flag_regmove && pass >= flag_expensive_optimizations)
1089 if (regmove_dump_file)
1090 fprintf (regmove_dump_file, "Starting %s pass...\n",
1091 pass ? "backward" : "forward");
1093 for (insn = pass ? get_last_insn () : f; insn;
1094 insn = pass ? PREV_INSN (insn) : NEXT_INSN (insn))
1097 int op_no, match_no;
1099 set = single_set (insn);
1103 if (flag_expensive_optimizations && ! pass
1104 && (GET_CODE (SET_SRC (set)) == SIGN_EXTEND
1105 || GET_CODE (SET_SRC (set)) == ZERO_EXTEND)
1106 && GET_CODE (XEXP (SET_SRC (set), 0)) == REG
1107 && GET_CODE (SET_DEST (set)) == REG)
1108 optimize_reg_copy_3 (insn, SET_DEST (set), SET_SRC (set));
1110 if (flag_expensive_optimizations && ! pass
1111 && GET_CODE (SET_SRC (set)) == REG
1112 && GET_CODE (SET_DEST (set)) == REG)
1114 /* If this is a register-register copy where SRC is not dead,
1115 see if we can optimize it. If this optimization succeeds,
1116 it will become a copy where SRC is dead. */
1117 if ((find_reg_note (insn, REG_DEAD, SET_SRC (set))
1118 || optimize_reg_copy_1 (insn, SET_DEST (set), SET_SRC (set)))
1119 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
1121 /* Similarly for a pseudo-pseudo copy when SRC is dead. */
1122 if (REGNO (SET_SRC (set)) >= FIRST_PSEUDO_REGISTER)
1123 optimize_reg_copy_2 (insn, SET_DEST (set), SET_SRC (set));
1124 if (regno_src_regno[REGNO (SET_DEST (set))] < 0
1125 && SET_SRC (set) != SET_DEST (set))
1127 int srcregno = REGNO (SET_SRC (set));
1128 if (regno_src_regno[srcregno] >= 0)
1129 srcregno = regno_src_regno[srcregno];
1130 regno_src_regno[REGNO (SET_DEST (set))] = srcregno;
1137 if (! find_matches (insn, &match))
1140 /* Now scan through the operands looking for a source operand
1141 which is supposed to match the destination operand.
1142 Then scan forward for an instruction which uses the dest
1144 If it dies there, then replace the dest in both operands with
1145 the source operand. */
1147 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1149 rtx src, dst, src_subreg;
1150 enum reg_class src_class, dst_class;
1152 match_no = match.with[op_no];
1154 /* Nothing to do if the two operands aren't supposed to match. */
1158 src = recog_data.operand[op_no];
1159 dst = recog_data.operand[match_no];
1161 if (GET_CODE (src) != REG)
1165 if (GET_CODE (dst) == SUBREG
1166 && GET_MODE_SIZE (GET_MODE (dst))
1167 >= GET_MODE_SIZE (GET_MODE (SUBREG_REG (dst))))
1170 = gen_rtx_SUBREG (GET_MODE (SUBREG_REG (dst)),
1171 src, SUBREG_BYTE (dst));
1172 dst = SUBREG_REG (dst);
1174 if (GET_CODE (dst) != REG
1175 || REGNO (dst) < FIRST_PSEUDO_REGISTER)
1178 if (REGNO (src) < FIRST_PSEUDO_REGISTER)
1180 if (match.commutative[op_no] < op_no)
1181 regno_src_regno[REGNO (dst)] = REGNO (src);
1185 if (REG_LIVE_LENGTH (REGNO (src)) < 0)
1188 /* op_no/src must be a read-only operand, and
1189 match_operand/dst must be a write-only operand. */
1190 if (match.use[op_no] != READ
1191 || match.use[match_no] != WRITE)
1194 if (match.early_clobber[match_no]
1195 && count_occurrences (PATTERN (insn), src, 0) > 1)
1198 /* Make sure match_operand is the destination. */
1199 if (recog_data.operand[match_no] != SET_DEST (set))
1202 /* If the operands already match, then there is nothing to do. */
1203 if (operands_match_p (src, dst))
1206 /* But in the commutative case, we might find a better match. */
1207 if (match.commutative[op_no] >= 0)
1209 rtx comm = recog_data.operand[match.commutative[op_no]];
1210 if (operands_match_p (comm, dst)
1211 && (replacement_quality (comm)
1212 >= replacement_quality (src)))
1216 src_class = reg_preferred_class (REGNO (src));
1217 dst_class = reg_preferred_class (REGNO (dst));
1218 if (! regclass_compatible_p (src_class, dst_class))
1221 if (GET_MODE (src) != GET_MODE (dst))
1224 if (fixup_match_1 (insn, set, src, src_subreg, dst, pass,
1232 /* A backward pass. Replace input operands with output operands. */
1234 if (regmove_dump_file)
1235 fprintf (regmove_dump_file, "Starting backward pass...\n");
1237 for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
1241 int op_no, match_no;
1244 if (! find_matches (insn, &match))
1247 /* Now scan through the operands looking for a destination operand
1248 which is supposed to match a source operand.
1249 Then scan backward for an instruction which sets the source
1250 operand. If safe, then replace the source operand with the
1251 dest operand in both instructions. */
1253 copy_src = NULL_RTX;
1254 copy_dst = NULL_RTX;
1255 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1257 rtx set, p, src, dst;
1258 rtx src_note, dst_note;
1260 enum reg_class src_class, dst_class;
1263 match_no = match.with[op_no];
1265 /* Nothing to do if the two operands aren't supposed to match. */
1269 dst = recog_data.operand[match_no];
1270 src = recog_data.operand[op_no];
1272 if (GET_CODE (src) != REG)
1275 if (GET_CODE (dst) != REG
1276 || REGNO (dst) < FIRST_PSEUDO_REGISTER
1277 || REG_LIVE_LENGTH (REGNO (dst)) < 0
1278 || RTX_UNCHANGING_P (dst))
1281 /* If the operands already match, then there is nothing to do. */
1282 if (operands_match_p (src, dst))
1285 if (match.commutative[op_no] >= 0)
1287 rtx comm = recog_data.operand[match.commutative[op_no]];
1288 if (operands_match_p (comm, dst))
1292 set = single_set (insn);
1296 /* Note that single_set ignores parts of a parallel set for
1297 which one of the destinations is REG_UNUSED. We can't
1298 handle that here, since we can wind up rewriting things
1299 such that a single register is set twice within a single
1301 if (reg_set_p (src, insn))
1304 /* match_no/dst must be a write-only operand, and
1305 operand_operand/src must be a read-only operand. */
1306 if (match.use[op_no] != READ
1307 || match.use[match_no] != WRITE)
1310 if (match.early_clobber[match_no]
1311 && count_occurrences (PATTERN (insn), src, 0) > 1)
1314 /* Make sure match_no is the destination. */
1315 if (recog_data.operand[match_no] != SET_DEST (set))
1318 if (REGNO (src) < FIRST_PSEUDO_REGISTER)
1320 if (GET_CODE (SET_SRC (set)) == PLUS
1321 && GET_CODE (XEXP (SET_SRC (set), 1)) == CONST_INT
1322 && XEXP (SET_SRC (set), 0) == src
1323 && fixup_match_2 (insn, dst, src,
1324 XEXP (SET_SRC (set), 1),
1329 src_class = reg_preferred_class (REGNO (src));
1330 dst_class = reg_preferred_class (REGNO (dst));
1332 if (! (src_note = find_reg_note (insn, REG_DEAD, src)))
1334 /* We used to force the copy here like in other cases, but
1335 it produces worse code, as it eliminates no copy
1336 instructions and the copy emitted will be produced by
1337 reload anyway. On patterns with multiple alternatives,
1338 there may be better sollution availble.
1340 In particular this change produced slower code for numeric
1346 if (! regclass_compatible_p (src_class, dst_class))
1356 /* Can not modify an earlier insn to set dst if this insn
1357 uses an old value in the source. */
1358 if (reg_overlap_mentioned_p (dst, SET_SRC (set)))
1368 /* If src is set once in a different basic block,
1369 and is set equal to a constant, then do not use
1370 it for this optimization, as this would make it
1371 no longer equivalent to a constant. */
1373 if (reg_is_remote_constant_p (src, insn, f))
1384 if (regmove_dump_file)
1385 fprintf (regmove_dump_file,
1386 "Could fix operand %d of insn %d matching operand %d.\n",
1387 op_no, INSN_UID (insn), match_no);
1389 /* Scan backward to find the first instruction that uses
1390 the input operand. If the operand is set here, then
1391 replace it in both instructions with match_no. */
1393 for (length = 0, p = PREV_INSN (insn); p; p = PREV_INSN (p))
1397 /* ??? We can't scan past the end of a basic block without
1398 updating the register lifetime info
1399 (REG_DEAD/basic_block_live_at_start). */
1400 if (perhaps_ends_bb_p (p))
1402 else if (! INSN_P (p))
1407 /* ??? See if all of SRC is set in P. This test is much
1408 more conservative than it needs to be. */
1409 pset = single_set (p);
1410 if (pset && SET_DEST (pset) == src)
1412 /* We use validate_replace_rtx, in case there
1413 are multiple identical source operands. All of
1414 them have to be changed at the same time. */
1415 if (validate_replace_rtx (src, dst, insn))
1417 if (validate_change (p, &SET_DEST (pset),
1422 /* Change all source operands back.
1423 This modifies the dst as a side-effect. */
1424 validate_replace_rtx (dst, src, insn);
1425 /* Now make sure the dst is right. */
1426 validate_change (insn,
1427 recog_data.operand_loc[match_no],
1434 if (reg_overlap_mentioned_p (src, PATTERN (p))
1435 || reg_overlap_mentioned_p (dst, PATTERN (p)))
1438 /* If we have passed a call instruction, and the
1439 pseudo-reg DST is not already live across a call,
1440 then don't perform the optimization. */
1441 if (GET_CODE (p) == CALL_INSN)
1445 if (REG_N_CALLS_CROSSED (REGNO (dst)) == 0)
1454 /* Remove the death note for SRC from INSN. */
1455 remove_note (insn, src_note);
1456 /* Move the death note for SRC to P if it is used
1458 if (reg_overlap_mentioned_p (src, PATTERN (p)))
1460 XEXP (src_note, 1) = REG_NOTES (p);
1461 REG_NOTES (p) = src_note;
1463 /* If there is a REG_DEAD note for DST on P, then remove
1464 it, because DST is now set there. */
1465 if ((dst_note = find_reg_note (p, REG_DEAD, dst)))
1466 remove_note (p, dst_note);
1468 dstno = REGNO (dst);
1469 srcno = REGNO (src);
1471 REG_N_SETS (dstno)++;
1472 REG_N_SETS (srcno)--;
1474 REG_N_CALLS_CROSSED (dstno) += num_calls;
1475 REG_N_CALLS_CROSSED (srcno) -= num_calls;
1477 REG_LIVE_LENGTH (dstno) += length;
1478 if (REG_LIVE_LENGTH (srcno) >= 0)
1480 REG_LIVE_LENGTH (srcno) -= length;
1481 /* REG_LIVE_LENGTH is only an approximation after
1482 combine if sched is not run, so make sure that we
1483 still have a reasonable value. */
1484 if (REG_LIVE_LENGTH (srcno) < 2)
1485 REG_LIVE_LENGTH (srcno) = 2;
1488 if (regmove_dump_file)
1489 fprintf (regmove_dump_file,
1490 "Fixed operand %d of insn %d matching operand %d.\n",
1491 op_no, INSN_UID (insn), match_no);
1497 /* If we weren't able to replace any of the alternatives, try an
1498 alternative appoach of copying the source to the destination. */
1499 if (!success && copy_src != NULL_RTX)
1500 copy_src_to_dest (insn, copy_src, copy_dst, old_max_uid);
1505 /* In fixup_match_1, some insns may have been inserted after basic block
1506 ends. Fix that here. */
1507 for (i = 0; i < n_basic_blocks; i++)
1509 rtx end = BLOCK_END (i);
1511 rtx next = NEXT_INSN (new);
1512 while (next != 0 && INSN_UID (next) >= old_max_uid
1513 && (i == n_basic_blocks - 1 || BLOCK_HEAD (i + 1) != next))
1514 new = next, next = NEXT_INSN (new);
1515 BLOCK_END (i) = new;
1520 free (regno_src_regno);
1521 free (regmove_bb_head);
1524 /* Returns nonzero if INSN's pattern has matching constraints for any operand.
1525 Returns 0 if INSN can't be recognized, or if the alternative can't be
1528 Initialize the info in MATCHP based on the constraints. */
1531 find_matches (insn, matchp)
1533 struct match *matchp;
1535 int likely_spilled[MAX_RECOG_OPERANDS];
1537 int any_matches = 0;
1539 extract_insn (insn);
1540 if (! constrain_operands (0))
1543 /* Must initialize this before main loop, because the code for
1544 the commutative case may set matches for operands other than
1546 for (op_no = recog_data.n_operands; --op_no >= 0; )
1547 matchp->with[op_no] = matchp->commutative[op_no] = -1;
1549 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1555 p = recog_data.constraints[op_no];
1557 likely_spilled[op_no] = 0;
1558 matchp->use[op_no] = READ;
1559 matchp->early_clobber[op_no] = 0;
1561 matchp->use[op_no] = WRITE;
1563 matchp->use[op_no] = READWRITE;
1565 for (;*p && i < which_alternative; p++)
1569 while ((c = *p++) != '\0' && c != ',')
1577 matchp->early_clobber[op_no] = 1;
1580 matchp->commutative[op_no] = op_no + 1;
1581 matchp->commutative[op_no + 1] = op_no;
1584 case '0': case '1': case '2': case '3': case '4':
1585 case '5': case '6': case '7': case '8': case '9':
1588 unsigned long match_ul = strtoul (p - 1, &end, 10);
1589 int match = match_ul;
1593 if (match < op_no && likely_spilled[match])
1595 matchp->with[op_no] = match;
1597 if (matchp->commutative[op_no] >= 0)
1598 matchp->with[matchp->commutative[op_no]] = match;
1602 case 'a': case 'b': case 'c': case 'd': case 'e': case 'f': case 'h':
1603 case 'j': case 'k': case 'l': case 'p': case 'q': case 't': case 'u':
1604 case 'v': case 'w': case 'x': case 'y': case 'z': case 'A': case 'B':
1605 case 'C': case 'D': case 'W': case 'Y': case 'Z':
1606 if (CLASS_LIKELY_SPILLED_P (REG_CLASS_FROM_LETTER ((unsigned char) c)))
1607 likely_spilled[op_no] = 1;
1614 /* Try to replace all occurrences of DST_REG with SRC in LOC, that is
1615 assumed to be in INSN. */
1618 replace_in_call_usage (loc, dst_reg, src, insn)
1620 unsigned int dst_reg;
1632 code = GET_CODE (x);
1635 if (REGNO (x) != dst_reg)
1638 validate_change (insn, loc, src, 1);
1643 /* Process each of our operands recursively. */
1644 fmt = GET_RTX_FORMAT (code);
1645 for (i = 0; i < GET_RTX_LENGTH (code); i++, fmt++)
1647 replace_in_call_usage (&XEXP (x, i), dst_reg, src, insn);
1648 else if (*fmt == 'E')
1649 for (j = 0; j < XVECLEN (x, i); j++)
1650 replace_in_call_usage (& XVECEXP (x, i, j), dst_reg, src, insn);
1653 /* Try to replace output operand DST in SET, with input operand SRC. SET is
1654 the only set in INSN. INSN has just been recognized and constrained.
1655 SRC is operand number OPERAND_NUMBER in INSN.
1656 DST is operand number MATCH_NUMBER in INSN.
1657 If BACKWARD is nonzero, we have been called in a backward pass.
1658 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 = 0, newconst;
1673 rtx overlap = 0; /* need to move insn ? */
1674 rtx src_note = find_reg_note (insn, REG_DEAD, src), dst_note = NULL_RTX;
1675 int length, s_length;
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) == CALL_INSN)
1726 replace_in_call_usage (& CALL_INSN_FUNCTION_USAGE (p),
1727 REGNO (dst), src, p);
1729 /* ??? We can't scan past the end of a basic block without updating
1730 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
1731 if (perhaps_ends_bb_p (p))
1733 else if (! INSN_P (p))
1740 if (reg_set_p (src, p) || reg_set_p (dst, p)
1741 || (GET_CODE (PATTERN (p)) == USE
1742 && reg_overlap_mentioned_p (src, XEXP (PATTERN (p), 0))))
1745 /* See if all of DST dies in P. This test is
1746 slightly more conservative than it needs to be. */
1747 if ((dst_note = find_regno_note (p, REG_DEAD, REGNO (dst)))
1748 && (GET_MODE (XEXP (dst_note, 0)) == GET_MODE (dst)))
1750 /* If we would be moving INSN, check that we won't move it
1751 into the shadow of a live a live flags register. */
1752 /* ??? We only try to move it in front of P, although
1753 we could move it anywhere between OVERLAP and P. */
1754 if (overlap && GET_MODE (PREV_INSN (p)) != VOIDmode)
1760 rtx set2 = NULL_RTX;
1762 /* If an optimization is done, the value of SRC while P
1763 is executed will be changed. Check that this is OK. */
1764 if (reg_overlap_mentioned_p (src, PATTERN (p)))
1766 for (q = p; q; q = NEXT_INSN (q))
1768 /* ??? We can't scan past the end of a basic block without
1769 updating the register lifetime info
1770 (REG_DEAD/basic_block_live_at_start). */
1771 if (perhaps_ends_bb_p (q))
1776 else if (! INSN_P (q))
1778 else if (reg_overlap_mentioned_p (src, PATTERN (q))
1779 || reg_set_p (src, q))
1783 set2 = single_set (q);
1784 if (! q || ! set2 || GET_CODE (SET_SRC (set2)) != code
1785 || XEXP (SET_SRC (set2), 0) != src
1786 || GET_CODE (XEXP (SET_SRC (set2), 1)) != CONST_INT
1787 || (SET_DEST (set2) != src
1788 && ! find_reg_note (q, REG_DEAD, src)))
1790 /* If this is a PLUS, we can still save a register by doing
1793 src -= insn_const; .
1794 This also gives opportunities for subsequent
1795 optimizations in the backward pass, so do it there. */
1796 if (code == PLUS && backward
1797 /* Don't do this if we can likely tie DST to SET_DEST
1798 of P later; we can't do this tying here if we got a
1800 && ! (dst_note && ! REG_N_CALLS_CROSSED (REGNO (dst))
1802 && GET_CODE (SET_DEST (single_set (p))) == REG
1803 && (REGNO (SET_DEST (single_set (p)))
1804 < FIRST_PSEUDO_REGISTER))
1805 /* We may only emit an insn directly after P if we
1806 are not in the shadow of a live flags register. */
1807 && GET_MODE (p) == VOIDmode)
1812 newconst = -insn_const;
1820 newconst = INTVAL (XEXP (SET_SRC (set2), 1)) - insn_const;
1821 /* Reject out of range shifts. */
1824 || ((unsigned HOST_WIDE_INT) newconst
1825 >= (GET_MODE_BITSIZE (GET_MODE
1826 (SET_SRC (set2)))))))
1831 if (SET_DEST (set2) != src)
1832 post_inc_set = set2;
1835 /* We use 1 as last argument to validate_change so that all
1836 changes are accepted or rejected together by apply_change_group
1837 when it is called by validate_replace_rtx . */
1838 validate_change (q, &XEXP (SET_SRC (set2), 1),
1839 GEN_INT (newconst), 1);
1841 validate_change (insn, recog_data.operand_loc[match_number], src, 1);
1842 if (validate_replace_rtx (dst, src_subreg, p))
1847 if (reg_overlap_mentioned_p (dst, PATTERN (p)))
1849 if (! src_note && reg_overlap_mentioned_p (src, PATTERN (p)))
1851 /* INSN was already checked to be movable wrt. the registers that it
1852 sets / uses when we found no REG_DEAD note for src on it, but it
1853 still might clobber the flags register. We'll have to check that
1854 we won't insert it into the shadow of a live flags register when
1855 we finally know where we are to move it. */
1857 src_note = find_reg_note (p, REG_DEAD, src);
1860 /* If we have passed a call instruction, and the pseudo-reg SRC is not
1861 already live across a call, then don't perform the optimization. */
1862 if (GET_CODE (p) == CALL_INSN)
1864 if (REG_N_CALLS_CROSSED (REGNO (src)) == 0)
1878 /* Remove the death note for DST from P. */
1879 remove_note (p, dst_note);
1882 post_inc = emit_insn_after (copy_rtx (PATTERN (insn)), p);
1883 if ((HAVE_PRE_INCREMENT || HAVE_PRE_DECREMENT)
1885 && try_auto_increment (search_end, post_inc, 0, src, newconst, 1))
1887 validate_change (insn, &XEXP (SET_SRC (set), 1), GEN_INT (insn_const), 0);
1888 REG_N_SETS (REGNO (src))++;
1889 REG_LIVE_LENGTH (REGNO (src))++;
1893 /* The lifetime of src and dest overlap,
1894 but we can change this by moving insn. */
1895 rtx pat = PATTERN (insn);
1897 remove_note (overlap, src_note);
1898 if ((HAVE_POST_INCREMENT || HAVE_POST_DECREMENT)
1900 && try_auto_increment (overlap, insn, 0, src, insn_const, 0))
1904 rtx notes = REG_NOTES (insn);
1906 emit_insn_after_with_line_notes (pat, PREV_INSN (p), insn);
1908 /* emit_insn_after_with_line_notes has no
1909 return value, so search for the new insn. */
1911 while (! INSN_P (insn) || PATTERN (insn) != pat)
1912 insn = PREV_INSN (insn);
1914 REG_NOTES (insn) = notes;
1917 /* Sometimes we'd generate src = const; src += n;
1918 if so, replace the instruction that set src
1919 in the first place. */
1921 if (! overlap && (code == PLUS || code == MINUS))
1923 rtx note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
1924 rtx q, set2 = NULL_RTX;
1925 int num_calls2 = 0, s_length2 = 0;
1927 if (note && CONSTANT_P (XEXP (note, 0)))
1929 for (q = PREV_INSN (insn); q; q = PREV_INSN (q))
1931 /* ??? We can't scan past the end of a basic block without
1932 updating the register lifetime info
1933 (REG_DEAD/basic_block_live_at_start). */
1934 if (perhaps_ends_bb_p (q))
1939 else if (! INSN_P (q))
1943 if (reg_set_p (src, q))
1945 set2 = single_set (q);
1948 if (reg_overlap_mentioned_p (src, PATTERN (q)))
1953 if (GET_CODE (p) == CALL_INSN)
1956 if (q && set2 && SET_DEST (set2) == src && CONSTANT_P (SET_SRC (set2))
1957 && validate_change (insn, &SET_SRC (set), XEXP (note, 0), 0))
1960 REG_N_SETS (REGNO (src))--;
1961 REG_N_CALLS_CROSSED (REGNO (src)) -= num_calls2;
1962 REG_LIVE_LENGTH (REGNO (src)) -= s_length2;
1968 if ((HAVE_PRE_INCREMENT || HAVE_PRE_DECREMENT)
1969 && (code == PLUS || code == MINUS) && insn_const
1970 && try_auto_increment (p, insn, 0, src, insn_const, 1))
1972 else if ((HAVE_POST_INCREMENT || HAVE_POST_DECREMENT)
1974 && try_auto_increment (p, post_inc, post_inc_set, src, newconst, 0))
1976 /* If post_inc still prevails, try to find an
1977 insn where it can be used as a pre-in/decrement.
1978 If code is MINUS, this was already tried. */
1979 if (post_inc && code == PLUS
1980 /* Check that newconst is likely to be usable
1981 in a pre-in/decrement before starting the search. */
1982 && ((HAVE_PRE_INCREMENT && newconst > 0 && newconst <= MOVE_MAX)
1983 || (HAVE_PRE_DECREMENT && newconst < 0 && newconst >= -MOVE_MAX))
1984 && exact_log2 (newconst))
1988 inc_dest = post_inc_set ? SET_DEST (post_inc_set) : src;
1989 for (q = post_inc; (q = NEXT_INSN (q)); )
1991 /* ??? We can't scan past the end of a basic block without updating
1992 the register lifetime info
1993 (REG_DEAD/basic_block_live_at_start). */
1994 if (perhaps_ends_bb_p (q))
1996 else if (! INSN_P (q))
1998 else if (src != inc_dest
1999 && (reg_overlap_mentioned_p (src, PATTERN (q))
2000 || reg_set_p (src, q)))
2002 else if (reg_set_p (inc_dest, q))
2004 else if (reg_overlap_mentioned_p (inc_dest, PATTERN (q)))
2006 try_auto_increment (q, post_inc,
2007 post_inc_set, inc_dest, newconst, 1);
2013 /* Move the death note for DST to INSN if it is used
2015 if (reg_overlap_mentioned_p (dst, PATTERN (insn)))
2017 XEXP (dst_note, 1) = REG_NOTES (insn);
2018 REG_NOTES (insn) = dst_note;
2023 /* Move the death note for SRC from INSN to P. */
2025 remove_note (insn, src_note);
2026 XEXP (src_note, 1) = REG_NOTES (p);
2027 REG_NOTES (p) = src_note;
2029 REG_N_CALLS_CROSSED (REGNO (src)) += s_num_calls;
2032 REG_N_SETS (REGNO (src))++;
2033 REG_N_SETS (REGNO (dst))--;
2035 REG_N_CALLS_CROSSED (REGNO (dst)) -= num_calls;
2037 REG_LIVE_LENGTH (REGNO (src)) += s_length;
2038 if (REG_LIVE_LENGTH (REGNO (dst)) >= 0)
2040 REG_LIVE_LENGTH (REGNO (dst)) -= length;
2041 /* REG_LIVE_LENGTH is only an approximation after
2042 combine if sched is not run, so make sure that we
2043 still have a reasonable value. */
2044 if (REG_LIVE_LENGTH (REGNO (dst)) < 2)
2045 REG_LIVE_LENGTH (REGNO (dst)) = 2;
2047 if (regmove_dump_file)
2048 fprintf (regmove_dump_file,
2049 "Fixed operand %d of insn %d matching operand %d.\n",
2050 operand_number, INSN_UID (insn), match_number);
2055 /* return nonzero if X is stable and mentions no regsiters but for
2056 mentioning SRC or mentioning / changing DST . If in doubt, presume
2058 The rationale is that we want to check if we can move an insn easily
2059 while just paying attention to SRC and DST. A register is considered
2060 stable if it has the RTX_UNCHANGING_P bit set, but that would still
2061 leave the burden to update REG_DEAD / REG_UNUSED notes, so we don't
2062 want any registers but SRC and DST. */
2064 stable_and_no_regs_but_for_p (x, src, dst)
2067 RTX_CODE code = GET_CODE (x);
2068 switch (GET_RTX_CLASS (code))
2070 case '<': case '1': case 'c': case '2': case 'b': case '3':
2073 const char *fmt = GET_RTX_FORMAT (code);
2074 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2076 && ! stable_and_no_regs_but_for_p (XEXP (x, i), src, dst))
2082 return x == src || x == dst;
2083 /* If this is a MEM, look inside - there might be a register hidden in
2084 the address of an unchanging MEM. */
2086 && ! stable_and_no_regs_but_for_p (XEXP (x, 0), src, dst))
2090 return ! rtx_unstable_p (x);
2094 /* Track stack adjustments and stack memory references. Attempt to
2095 reduce the number of stack adjustments by back-propagating across
2096 the memory references.
2098 This is intended primarily for use with targets that do not define
2099 ACCUMULATE_OUTGOING_ARGS. It is of significantly more value to
2100 targets that define PREFERRED_STACK_BOUNDARY more aligned than
2101 STACK_BOUNDARY (e.g. x86), or if not all registers can be pushed
2102 (e.g. x86 fp regs) which would ordinarily have to be implemented
2103 as a sub/mov pair due to restrictions in calls.c.
2105 Propagation stops when any of the insns that need adjusting are
2106 (a) no longer valid because we've exceeded their range, (b) a
2107 non-trivial push instruction, or (c) a call instruction.
2109 Restriction B is based on the assumption that push instructions
2110 are smaller or faster. If a port really wants to remove all
2111 pushes, it should have defined ACCUMULATE_OUTGOING_ARGS. The
2112 one exception that is made is for an add immediately followed
2115 /* This structure records stack memory references between stack adjusting
2120 HOST_WIDE_INT sp_offset;
2122 struct csa_memlist *next;
2125 static int stack_memref_p PARAMS ((rtx));
2126 static rtx single_set_for_csa PARAMS ((rtx));
2127 static void free_csa_memlist PARAMS ((struct csa_memlist *));
2128 static struct csa_memlist *record_one_stack_memref
2129 PARAMS ((rtx, rtx *, struct csa_memlist *));
2130 static int try_apply_stack_adjustment
2131 PARAMS ((rtx, struct csa_memlist *, HOST_WIDE_INT, HOST_WIDE_INT));
2132 static void combine_stack_adjustments_for_block PARAMS ((basic_block));
2133 static int record_stack_memrefs PARAMS ((rtx *, void *));
2136 /* Main entry point for stack adjustment combination. */
2139 combine_stack_adjustments ()
2143 for (i = 0; i < n_basic_blocks; ++i)
2144 combine_stack_adjustments_for_block (BASIC_BLOCK (i));
2147 /* Recognize a MEM of the form (sp) or (plus sp const). */
2153 if (GET_CODE (x) != MEM)
2157 if (x == stack_pointer_rtx)
2159 if (GET_CODE (x) == PLUS
2160 && XEXP (x, 0) == stack_pointer_rtx
2161 && GET_CODE (XEXP (x, 1)) == CONST_INT)
2167 /* Recognize either normal single_set or the hack in i386.md for
2168 tying fp and sp adjustments. */
2171 single_set_for_csa (insn)
2175 rtx tmp = single_set (insn);
2179 if (GET_CODE (insn) != INSN
2180 || GET_CODE (PATTERN (insn)) != PARALLEL)
2183 tmp = PATTERN (insn);
2184 if (GET_CODE (XVECEXP (tmp, 0, 0)) != SET)
2187 for (i = 1; i < XVECLEN (tmp, 0); ++i)
2189 rtx this = XVECEXP (tmp, 0, i);
2191 /* The special case is allowing a no-op set. */
2192 if (GET_CODE (this) == SET
2193 && SET_SRC (this) == SET_DEST (this))
2195 else if (GET_CODE (this) != CLOBBER
2196 && GET_CODE (this) != USE)
2200 return XVECEXP (tmp, 0, 0);
2203 /* Free the list of csa_memlist nodes. */
2206 free_csa_memlist (memlist)
2207 struct csa_memlist *memlist;
2209 struct csa_memlist *next;
2210 for (; memlist ; memlist = next)
2212 next = memlist->next;
2217 /* Create a new csa_memlist node from the given memory reference.
2218 It is already known that the memory is stack_memref_p. */
2220 static struct csa_memlist *
2221 record_one_stack_memref (insn, mem, next_memlist)
2223 struct csa_memlist *next_memlist;
2225 struct csa_memlist *ml;
2227 ml = (struct csa_memlist *) xmalloc (sizeof (*ml));
2229 if (XEXP (*mem, 0) == stack_pointer_rtx)
2232 ml->sp_offset = INTVAL (XEXP (XEXP (*mem, 0), 1));
2236 ml->next = next_memlist;
2241 /* Attempt to apply ADJUST to the stack adjusting insn INSN, as well
2242 as each of the memories in MEMLIST. Return true on success. */
2245 try_apply_stack_adjustment (insn, memlist, new_adjust, delta)
2247 struct csa_memlist *memlist;
2248 HOST_WIDE_INT new_adjust, delta;
2250 struct csa_memlist *ml;
2253 set = single_set_for_csa (insn);
2254 validate_change (insn, &XEXP (SET_SRC (set), 1), GEN_INT (new_adjust), 1);
2256 for (ml = memlist; ml ; ml = ml->next)
2259 replace_equiv_address_nv (*ml->mem,
2260 plus_constant (stack_pointer_rtx,
2261 ml->sp_offset - delta)), 1);
2263 if (apply_change_group ())
2265 /* Succeeded. Update our knowledge of the memory references. */
2266 for (ml = memlist; ml ; ml = ml->next)
2267 ml->sp_offset -= delta;
2275 /* Called via for_each_rtx and used to record all stack memory references in
2276 the insn and discard all other stack pointer references. */
2277 struct record_stack_memrefs_data
2280 struct csa_memlist *memlist;
2284 record_stack_memrefs (xp, data)
2289 struct record_stack_memrefs_data *d =
2290 (struct record_stack_memrefs_data *) data;
2293 switch (GET_CODE (x))
2296 if (!reg_mentioned_p (stack_pointer_rtx, x))
2298 /* We are not able to handle correctly all possible memrefs containing
2299 stack pointer, so this check is necessary. */
2300 if (stack_memref_p (x))
2302 d->memlist = record_one_stack_memref (d->insn, xp, d->memlist);
2307 /* ??? We want be able to handle non-memory stack pointer
2308 references later. For now just discard all insns refering to
2309 stack pointer outside mem expressions. We would probably
2310 want to teach validate_replace to simplify expressions first.
2312 We can't just compare with STACK_POINTER_RTX because the
2313 reference to the stack pointer might be in some other mode.
2314 In particular, an explict clobber in an asm statement will
2315 result in a QImode clober. */
2316 if (REGNO (x) == STACK_POINTER_REGNUM)
2325 /* Subroutine of combine_stack_adjustments, called for each basic block. */
2328 combine_stack_adjustments_for_block (bb)
2331 HOST_WIDE_INT last_sp_adjust = 0;
2332 rtx last_sp_set = NULL_RTX;
2333 struct csa_memlist *memlist = NULL;
2334 rtx insn, next, set;
2335 struct record_stack_memrefs_data data;
2336 bool end_of_block = false;
2338 for (insn = bb->head; !end_of_block ; insn = next)
2340 end_of_block = insn == bb->end;
2341 next = NEXT_INSN (insn);
2343 if (! INSN_P (insn))
2346 set = single_set_for_csa (insn);
2349 rtx dest = SET_DEST (set);
2350 rtx src = SET_SRC (set);
2352 /* Find constant additions to the stack pointer. */
2353 if (dest == stack_pointer_rtx
2354 && GET_CODE (src) == PLUS
2355 && XEXP (src, 0) == stack_pointer_rtx
2356 && GET_CODE (XEXP (src, 1)) == CONST_INT)
2358 HOST_WIDE_INT this_adjust = INTVAL (XEXP (src, 1));
2360 /* If we've not seen an adjustment previously, record
2361 it now and continue. */
2365 last_sp_adjust = this_adjust;
2369 /* If not all recorded memrefs can be adjusted, or the
2370 adjustment is now too large for a constant addition,
2371 we cannot merge the two stack adjustments.
2373 Also we need to be carefull to not move stack pointer
2374 such that we create stack accesses outside the allocated
2375 area. We can combine an allocation into the first insn,
2376 or a deallocation into the second insn. We can not
2377 combine an allocation followed by a deallocation.
2379 The only somewhat frequent occurrence of the later is when
2380 a function allocates a stack frame but does not use it.
2381 For this case, we would need to analyze rtl stream to be
2382 sure that allocated area is really unused. This means not
2383 only checking the memory references, but also all registers
2384 or global memory references possibly containing a stack
2387 Perhaps the best way to address this problem is to teach
2388 gcc not to allocate stack for objects never used. */
2390 /* Combine an allocation into the first instruction. */
2391 if (STACK_GROWS_DOWNWARD ? this_adjust <= 0 : this_adjust >= 0)
2393 if (try_apply_stack_adjustment (last_sp_set, memlist,
2394 last_sp_adjust + this_adjust,
2399 last_sp_adjust += this_adjust;
2404 /* Otherwise we have a deallocation. Do not combine with
2405 a previous allocation. Combine into the second insn. */
2406 else if (STACK_GROWS_DOWNWARD
2407 ? last_sp_adjust >= 0 : last_sp_adjust <= 0)
2409 if (try_apply_stack_adjustment (insn, memlist,
2410 last_sp_adjust + this_adjust,
2414 delete_insn (last_sp_set);
2416 last_sp_adjust += this_adjust;
2417 free_csa_memlist (memlist);
2423 /* Combination failed. Restart processing from here. If
2424 deallocation+allocation conspired to cancel, we can
2425 delete the old deallocation insn. */
2426 if (last_sp_set && last_sp_adjust == 0)
2428 free_csa_memlist (memlist);
2431 last_sp_adjust = this_adjust;
2435 /* Find a predecrement of exactly the previous adjustment and
2436 turn it into a direct store. Obviously we can't do this if
2437 there were any intervening uses of the stack pointer. */
2439 && GET_CODE (dest) == MEM
2440 && ((GET_CODE (XEXP (dest, 0)) == PRE_DEC
2442 == (HOST_WIDE_INT) GET_MODE_SIZE (GET_MODE (dest))))
2443 || (GET_CODE (XEXP (dest, 0)) == PRE_MODIFY
2444 && GET_CODE (XEXP (XEXP (dest, 0), 1)) == PLUS
2445 && XEXP (XEXP (XEXP (dest, 0), 1), 0) == stack_pointer_rtx
2446 && (GET_CODE (XEXP (XEXP (XEXP (dest, 0), 1), 1))
2448 && (INTVAL (XEXP (XEXP (XEXP (dest, 0), 1), 1))
2449 == -last_sp_adjust)))
2450 && XEXP (XEXP (dest, 0), 0) == stack_pointer_rtx
2451 && ! reg_mentioned_p (stack_pointer_rtx, src)
2452 && memory_address_p (GET_MODE (dest), stack_pointer_rtx)
2453 && validate_change (insn, &SET_DEST (set),
2454 replace_equiv_address (dest,
2458 delete_insn (last_sp_set);
2459 free_csa_memlist (memlist);
2461 last_sp_set = NULL_RTX;
2468 data.memlist = memlist;
2469 if (GET_CODE (insn) != CALL_INSN && last_sp_set
2470 && !for_each_rtx (&PATTERN (insn), record_stack_memrefs, &data))
2472 memlist = data.memlist;
2475 memlist = data.memlist;
2477 /* Otherwise, we were not able to process the instruction.
2478 Do not continue collecting data across such a one. */
2480 && (GET_CODE (insn) == CALL_INSN
2481 || reg_mentioned_p (stack_pointer_rtx, PATTERN (insn))))
2483 if (last_sp_set && last_sp_adjust == 0)
2484 delete_insn (last_sp_set);
2485 free_csa_memlist (memlist);
2487 last_sp_set = NULL_RTX;
2492 if (last_sp_set && last_sp_adjust == 0)
2493 delete_insn (last_sp_set);
OSDN Git Service
