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, 2003, 2004, 2005 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, 51 Franklin Street, Fifth Floor, 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 "coretypes.h"
32 #include "rtl.h" /* stdio.h must precede rtl.h for FFS. */
34 #include "insn-config.h"
38 #include "hard-reg-set.h"
42 #include "basic-block.h"
47 #include "tree-pass.h"
50 /* Turn STACK_GROWS_DOWNWARD into a boolean. */
51 #ifdef STACK_GROWS_DOWNWARD
52 #undef STACK_GROWS_DOWNWARD
53 #define STACK_GROWS_DOWNWARD 1
55 #define STACK_GROWS_DOWNWARD 0
58 static int perhaps_ends_bb_p (rtx);
59 static int optimize_reg_copy_1 (rtx, rtx, rtx);
60 static void optimize_reg_copy_2 (rtx, rtx, rtx);
61 static void optimize_reg_copy_3 (rtx, rtx, rtx);
62 static void copy_src_to_dest (rtx, rtx, rtx, int);
63 static int *regmove_bb_head;
66 int with[MAX_RECOG_OPERANDS];
67 enum { READ, WRITE, READWRITE } use[MAX_RECOG_OPERANDS];
68 int commutative[MAX_RECOG_OPERANDS];
69 int early_clobber[MAX_RECOG_OPERANDS];
72 static rtx discover_flags_reg (void);
73 static void mark_flags_life_zones (rtx);
74 static void flags_set_1 (rtx, rtx, void *);
76 static int try_auto_increment (rtx, rtx, rtx, rtx, HOST_WIDE_INT, int);
77 static int find_matches (rtx, struct match *);
78 static void replace_in_call_usage (rtx *, unsigned int, rtx, rtx);
79 static int fixup_match_1 (rtx, rtx, rtx, rtx, rtx, int, int, int);
80 static int stable_and_no_regs_but_for_p (rtx, rtx, rtx);
81 static int regclass_compatible_p (int, int);
82 static int replacement_quality (rtx);
83 static int fixup_match_2 (rtx, rtx, rtx, rtx);
85 /* Return nonzero if registers with CLASS1 and CLASS2 can be merged without
86 causing too much register allocation problems. */
88 regclass_compatible_p (int class0, int class1)
90 return (class0 == class1
91 || (reg_class_subset_p (class0, class1)
92 && ! CLASS_LIKELY_SPILLED_P (class0))
93 || (reg_class_subset_p (class1, class0)
94 && ! CLASS_LIKELY_SPILLED_P (class1)));
97 /* INC_INSN is an instruction that adds INCREMENT to REG.
98 Try to fold INC_INSN as a post/pre in/decrement into INSN.
99 Iff INC_INSN_SET is nonzero, inc_insn has a destination different from src.
100 Return nonzero for success. */
102 try_auto_increment (rtx insn, rtx inc_insn, rtx inc_insn_set, rtx reg,
103 HOST_WIDE_INT increment, int pre)
105 enum rtx_code inc_code;
107 rtx pset = single_set (insn);
110 /* Can't use the size of SET_SRC, we might have something like
111 (sign_extend:SI (mem:QI ... */
112 rtx use = find_use_as_address (pset, reg, 0);
113 if (use != 0 && use != (rtx) (size_t) 1)
115 int size = GET_MODE_SIZE (GET_MODE (use));
117 || (HAVE_POST_INCREMENT
118 && pre == 0 && (inc_code = POST_INC, increment == size))
119 || (HAVE_PRE_INCREMENT
120 && pre == 1 && (inc_code = PRE_INC, increment == size))
121 || (HAVE_POST_DECREMENT
122 && pre == 0 && (inc_code = POST_DEC, increment == -size))
123 || (HAVE_PRE_DECREMENT
124 && pre == 1 && (inc_code = PRE_DEC, increment == -size))
130 &SET_SRC (inc_insn_set),
131 XEXP (SET_SRC (inc_insn_set), 0), 1);
132 validate_change (insn, &XEXP (use, 0),
133 gen_rtx_fmt_e (inc_code, Pmode, reg), 1);
134 if (apply_change_group ())
136 /* If there is a REG_DEAD note on this insn, we must
137 change this not to REG_UNUSED meaning that the register
138 is set, but the value is dead. Failure to do so will
139 result in a sched1 dieing -- when it recomputes lifetime
140 information, the number of REG_DEAD notes will have
142 rtx note = find_reg_note (insn, REG_DEAD, reg);
144 PUT_MODE (note, REG_UNUSED);
147 = gen_rtx_EXPR_LIST (REG_INC,
148 reg, REG_NOTES (insn));
150 delete_insn (inc_insn);
159 /* Determine if the pattern generated by add_optab has a clobber,
160 such as might be issued for a flags hard register. To make the
161 code elsewhere simpler, we handle cc0 in this same framework.
163 Return the register if one was discovered. Return NULL_RTX if
164 if no flags were found. Return pc_rtx if we got confused. */
167 discover_flags_reg (void)
170 tmp = gen_rtx_REG (word_mode, 10000);
171 tmp = gen_add3_insn (tmp, tmp, const2_rtx);
173 /* If we get something that isn't a simple set, or a
174 [(set ..) (clobber ..)], this whole function will go wrong. */
175 if (GET_CODE (tmp) == SET)
177 else if (GET_CODE (tmp) == PARALLEL)
181 if (XVECLEN (tmp, 0) != 2)
183 tmp = XVECEXP (tmp, 0, 1);
184 if (GET_CODE (tmp) != CLOBBER)
188 /* Don't do anything foolish if the md wanted to clobber a
189 scratch or something. We only care about hard regs.
190 Moreover we don't like the notion of subregs of hard regs. */
191 if (GET_CODE (tmp) == SUBREG
192 && REG_P (SUBREG_REG (tmp))
193 && REGNO (SUBREG_REG (tmp)) < FIRST_PSEUDO_REGISTER)
195 found = (REG_P (tmp) && REGNO (tmp) < FIRST_PSEUDO_REGISTER);
197 return (found ? tmp : NULL_RTX);
203 /* It is a tedious task identifying when the flags register is live and
204 when it is safe to optimize. Since we process the instruction stream
205 multiple times, locate and record these live zones by marking the
206 mode of the instructions --
208 QImode is used on the instruction at which the flags becomes live.
210 HImode is used within the range (exclusive) that the flags are
211 live. Thus the user of the flags is not marked.
213 All other instructions are cleared to VOIDmode. */
215 /* Used to communicate with flags_set_1. */
216 static rtx flags_set_1_rtx;
217 static int flags_set_1_set;
220 mark_flags_life_zones (rtx flags)
227 /* If we found a flags register on a cc0 host, bail. */
228 if (flags == NULL_RTX)
230 else if (flags != cc0_rtx)
234 /* Simple cases first: if no flags, clear all modes. If confusing,
235 mark the entire function as being in a flags shadow. */
236 if (flags == NULL_RTX || flags == pc_rtx)
238 enum machine_mode mode = (flags ? HImode : VOIDmode);
240 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
241 PUT_MODE (insn, mode);
249 flags_regno = REGNO (flags);
250 flags_nregs = hard_regno_nregs[flags_regno][GET_MODE (flags)];
252 flags_set_1_rtx = flags;
254 /* Process each basic block. */
255 FOR_EACH_BB_REVERSE (block)
260 insn = BB_HEAD (block);
261 end = BB_END (block);
263 /* Look out for the (unlikely) case of flags being live across
264 basic block boundaries. */
269 for (i = 0; i < flags_nregs; ++i)
270 live |= REGNO_REG_SET_P (block->il.rtl->global_live_at_start,
277 /* Process liveness in reverse order of importance --
278 alive, death, birth. This lets more important info
279 overwrite the mode of lesser info. */
284 /* In the cc0 case, death is not marked in reg notes,
285 but is instead the mere use of cc0 when it is alive. */
286 if (live && reg_mentioned_p (cc0_rtx, PATTERN (insn)))
289 /* In the hard reg case, we watch death notes. */
290 if (live && find_regno_note (insn, REG_DEAD, flags_regno))
293 PUT_MODE (insn, (live ? HImode : VOIDmode));
295 /* In either case, birth is denoted simply by its presence
296 as the destination of a set. */
298 note_stores (PATTERN (insn), flags_set_1, NULL);
302 PUT_MODE (insn, QImode);
306 PUT_MODE (insn, (live ? HImode : VOIDmode));
310 insn = NEXT_INSN (insn);
315 /* A subroutine of mark_flags_life_zones, called through note_stores. */
318 flags_set_1 (rtx x, rtx pat, void *data ATTRIBUTE_UNUSED)
320 if (GET_CODE (pat) == SET
321 && reg_overlap_mentioned_p (x, flags_set_1_rtx))
325 static int *regno_src_regno;
327 /* Indicate how good a choice REG (which appears as a source) is to replace
328 a destination register with. The higher the returned value, the better
329 the choice. The main objective is to avoid using a register that is
330 a candidate for tying to a hard register, since the output might in
331 turn be a candidate to be tied to a different hard register. */
333 replacement_quality (rtx reg)
337 /* Bad if this isn't a register at all. */
341 /* If this register is not meant to get a hard register,
342 it is a poor choice. */
343 if (REG_LIVE_LENGTH (REGNO (reg)) < 0)
346 src_regno = regno_src_regno[REGNO (reg)];
348 /* If it was not copied from another register, it is fine. */
352 /* Copied from a hard register? */
353 if (src_regno < FIRST_PSEUDO_REGISTER)
356 /* Copied from a pseudo register - not as bad as from a hard register,
357 yet still cumbersome, since the register live length will be lengthened
358 when the registers get tied. */
362 /* Return 1 if INSN might end a basic block. */
364 static int perhaps_ends_bb_p (rtx insn)
366 switch (GET_CODE (insn))
370 /* These always end a basic block. */
374 /* A CALL_INSN might be the last insn of a basic block, if it is inside
375 an EH region or if there are nonlocal gotos. Note that this test is
376 very conservative. */
377 if (nonlocal_goto_handler_labels)
381 return can_throw_internal (insn);
385 /* INSN is a copy from SRC to DEST, both registers, and SRC does not die
388 Search forward to see if SRC dies before either it or DEST is modified,
389 but don't scan past the end of a basic block. If so, we can replace SRC
390 with DEST and let SRC die in INSN.
392 This will reduce the number of registers live in that range and may enable
393 DEST to be tied to SRC, thus often saving one register in addition to a
394 register-register copy. */
397 optimize_reg_copy_1 (rtx insn, rtx dest, rtx src)
402 int sregno = REGNO (src);
403 int dregno = REGNO (dest);
405 /* We don't want to mess with hard regs if register classes are small. */
407 || (SMALL_REGISTER_CLASSES
408 && (sregno < FIRST_PSEUDO_REGISTER
409 || dregno < FIRST_PSEUDO_REGISTER))
410 /* We don't see all updates to SP if they are in an auto-inc memory
411 reference, so we must disallow this optimization on them. */
412 || sregno == STACK_POINTER_REGNUM || dregno == STACK_POINTER_REGNUM)
415 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
417 /* ??? We can't scan past the end of a basic block without updating
418 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
419 if (perhaps_ends_bb_p (p))
421 else if (! INSN_P (p))
424 if (reg_set_p (src, p) || reg_set_p (dest, p)
425 /* If SRC is an asm-declared register, it must not be replaced
426 in any asm. Unfortunately, the REG_EXPR tree for the asm
427 variable may be absent in the SRC rtx, so we can't check the
428 actual register declaration easily (the asm operand will have
429 it, though). To avoid complicating the test for a rare case,
430 we just don't perform register replacement for a hard reg
431 mentioned in an asm. */
432 || (sregno < FIRST_PSEUDO_REGISTER
433 && asm_noperands (PATTERN (p)) >= 0
434 && reg_overlap_mentioned_p (src, PATTERN (p)))
435 /* Don't change hard registers used by a call. */
436 || (CALL_P (p) && sregno < FIRST_PSEUDO_REGISTER
437 && find_reg_fusage (p, USE, src))
438 /* Don't change a USE of a register. */
439 || (GET_CODE (PATTERN (p)) == USE
440 && reg_overlap_mentioned_p (src, XEXP (PATTERN (p), 0))))
443 /* See if all of SRC dies in P. This test is slightly more
444 conservative than it needs to be. */
445 if ((note = find_regno_note (p, REG_DEAD, sregno)) != 0
446 && GET_MODE (XEXP (note, 0)) == GET_MODE (src))
454 /* We can do the optimization. Scan forward from INSN again,
455 replacing regs as we go. Set FAILED if a replacement can't
456 be done. In that case, we can't move the death note for SRC.
457 This should be rare. */
459 /* Set to stop at next insn. */
460 for (q = next_real_insn (insn);
461 q != next_real_insn (p);
462 q = next_real_insn (q))
464 if (reg_overlap_mentioned_p (src, PATTERN (q)))
466 /* If SRC is a hard register, we might miss some
467 overlapping registers with validate_replace_rtx,
468 so we would have to undo it. We can't if DEST is
469 present in the insn, so fail in that combination
471 if (sregno < FIRST_PSEUDO_REGISTER
472 && reg_mentioned_p (dest, PATTERN (q)))
475 /* Replace all uses and make sure that the register
476 isn't still present. */
477 else if (validate_replace_rtx (src, dest, q)
478 && (sregno >= FIRST_PSEUDO_REGISTER
479 || ! reg_overlap_mentioned_p (src,
484 validate_replace_rtx (dest, src, q);
489 /* For SREGNO, count the total number of insns scanned.
490 For DREGNO, count the total number of insns scanned after
491 passing the death note for DREGNO. */
496 /* If the insn in which SRC dies is a CALL_INSN, don't count it
497 as a call that has been crossed. Otherwise, count it. */
498 if (q != p && CALL_P (q))
500 /* Similarly, total calls for SREGNO, total calls beyond
501 the death note for DREGNO. */
507 /* If DEST dies here, remove the death note and save it for
508 later. Make sure ALL of DEST dies here; again, this is
509 overly conservative. */
511 && (dest_death = find_regno_note (q, REG_DEAD, dregno)) != 0)
513 if (GET_MODE (XEXP (dest_death, 0)) != GET_MODE (dest))
514 failed = 1, dest_death = 0;
516 remove_note (q, dest_death);
522 /* These counters need to be updated if and only if we are
523 going to move the REG_DEAD note. */
524 if (sregno >= FIRST_PSEUDO_REGISTER)
526 if (REG_LIVE_LENGTH (sregno) >= 0)
528 REG_LIVE_LENGTH (sregno) -= s_length;
529 /* REG_LIVE_LENGTH is only an approximation after
530 combine if sched is not run, so make sure that we
531 still have a reasonable value. */
532 if (REG_LIVE_LENGTH (sregno) < 2)
533 REG_LIVE_LENGTH (sregno) = 2;
536 REG_N_CALLS_CROSSED (sregno) -= s_n_calls;
539 /* Move death note of SRC from P to INSN. */
540 remove_note (p, note);
541 XEXP (note, 1) = REG_NOTES (insn);
542 REG_NOTES (insn) = note;
545 /* DEST is also dead if INSN has a REG_UNUSED note for DEST. */
547 && (dest_death = find_regno_note (insn, REG_UNUSED, dregno)))
549 PUT_REG_NOTE_KIND (dest_death, REG_DEAD);
550 remove_note (insn, dest_death);
553 /* Put death note of DEST on P if we saw it die. */
556 XEXP (dest_death, 1) = REG_NOTES (p);
557 REG_NOTES (p) = dest_death;
559 if (dregno >= FIRST_PSEUDO_REGISTER)
561 /* If and only if we are moving the death note for DREGNO,
562 then we need to update its counters. */
563 if (REG_LIVE_LENGTH (dregno) >= 0)
564 REG_LIVE_LENGTH (dregno) += d_length;
565 REG_N_CALLS_CROSSED (dregno) += d_n_calls;
572 /* If SRC is a hard register which is set or killed in some other
573 way, we can't do this optimization. */
574 else if (sregno < FIRST_PSEUDO_REGISTER
575 && dead_or_set_p (p, src))
581 /* INSN is a copy of SRC to DEST, in which SRC dies. See if we now have
582 a sequence of insns that modify DEST followed by an insn that sets
583 SRC to DEST in which DEST dies, with no prior modification of DEST.
584 (There is no need to check if the insns in between actually modify
585 DEST. We should not have cases where DEST is not modified, but
586 the optimization is safe if no such modification is detected.)
587 In that case, we can replace all uses of DEST, starting with INSN and
588 ending with the set of SRC to DEST, with SRC. We do not do this
589 optimization if a CALL_INSN is crossed unless SRC already crosses a
590 call or if DEST dies before the copy back to SRC.
592 It is assumed that DEST and SRC are pseudos; it is too complicated to do
593 this for hard registers since the substitutions we may make might fail. */
596 optimize_reg_copy_2 (rtx insn, rtx dest, rtx src)
600 int sregno = REGNO (src);
601 int dregno = REGNO (dest);
603 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
605 /* ??? We can't scan past the end of a basic block without updating
606 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
607 if (perhaps_ends_bb_p (p))
609 else if (! INSN_P (p))
612 set = single_set (p);
613 if (set && SET_SRC (set) == dest && SET_DEST (set) == src
614 && find_reg_note (p, REG_DEAD, dest))
616 /* We can do the optimization. Scan forward from INSN again,
617 replacing regs as we go. */
619 /* Set to stop at next insn. */
620 for (q = insn; q != NEXT_INSN (p); q = NEXT_INSN (q))
623 if (reg_mentioned_p (dest, PATTERN (q)))
624 PATTERN (q) = replace_rtx (PATTERN (q), dest, src);
629 REG_N_CALLS_CROSSED (dregno)--;
630 REG_N_CALLS_CROSSED (sregno)++;
634 remove_note (p, find_reg_note (p, REG_DEAD, dest));
635 REG_N_DEATHS (dregno)--;
636 remove_note (insn, find_reg_note (insn, REG_DEAD, src));
637 REG_N_DEATHS (sregno)--;
641 if (reg_set_p (src, p)
642 || find_reg_note (p, REG_DEAD, dest)
643 || (CALL_P (p) && REG_N_CALLS_CROSSED (sregno) == 0))
647 /* INSN is a ZERO_EXTEND or SIGN_EXTEND of SRC to DEST.
648 Look if SRC dies there, and if it is only set once, by loading
649 it from memory. If so, try to incorporate the zero/sign extension
650 into the memory read, change SRC to the mode of DEST, and alter
651 the remaining accesses to use the appropriate SUBREG. This allows
652 SRC and DEST to be tied later. */
654 optimize_reg_copy_3 (rtx insn, rtx dest, rtx src)
656 rtx src_reg = XEXP (src, 0);
657 int src_no = REGNO (src_reg);
658 int dst_no = REGNO (dest);
660 enum machine_mode old_mode;
662 if (src_no < FIRST_PSEUDO_REGISTER
663 || dst_no < FIRST_PSEUDO_REGISTER
664 || ! find_reg_note (insn, REG_DEAD, src_reg)
665 || REG_N_DEATHS (src_no) != 1
666 || REG_N_SETS (src_no) != 1)
668 for (p = PREV_INSN (insn); p && ! reg_set_p (src_reg, p); p = PREV_INSN (p))
669 /* ??? We can't scan past the end of a basic block without updating
670 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
671 if (perhaps_ends_bb_p (p))
677 if (! (set = single_set (p))
678 || !MEM_P (SET_SRC (set))
679 /* If there's a REG_EQUIV note, this must be an insn that loads an
680 argument. Prefer keeping the note over doing this optimization. */
681 || find_reg_note (p, REG_EQUIV, NULL_RTX)
682 || SET_DEST (set) != src_reg)
685 /* Be conservative: although this optimization is also valid for
686 volatile memory references, that could cause trouble in later passes. */
687 if (MEM_VOLATILE_P (SET_SRC (set)))
690 /* Do not use a SUBREG to truncate from one mode to another if truncation
692 if (GET_MODE_BITSIZE (GET_MODE (src_reg)) <= GET_MODE_BITSIZE (GET_MODE (src))
693 && !TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (GET_MODE (src)),
694 GET_MODE_BITSIZE (GET_MODE (src_reg))))
697 old_mode = GET_MODE (src_reg);
698 PUT_MODE (src_reg, GET_MODE (src));
699 XEXP (src, 0) = SET_SRC (set);
701 /* Include this change in the group so that it's easily undone if
702 one of the changes in the group is invalid. */
703 validate_change (p, &SET_SRC (set), src, 1);
705 /* Now walk forward making additional replacements. We want to be able
706 to undo all the changes if a later substitution fails. */
707 while (p = NEXT_INSN (p), p != insn)
712 /* Make a tentative change. */
713 validate_replace_rtx_group (src_reg,
714 gen_lowpart_SUBREG (old_mode, src_reg),
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 (rtx insn, rtx src, rtx dest, int old_max_uid)
755 /* A REG_LIVE_LENGTH of -1 indicates the register is equivalent to a constant
756 or memory location and is used infrequently; a REG_LIVE_LENGTH of -2 is
757 parameter when there is no frame pointer that is not allocated a register.
758 For now, we just reject them, rather than incrementing the live length. */
761 && REG_LIVE_LENGTH (REGNO (src)) > 0
763 && REG_LIVE_LENGTH (REGNO (dest)) > 0
764 && (set = single_set (insn)) != NULL_RTX
765 && !reg_mentioned_p (dest, SET_SRC (set))
766 && GET_MODE (src) == GET_MODE (dest))
768 int old_num_regs = reg_rtx_no;
770 /* Generate the src->dest move. */
772 emit_move_insn (dest, src);
775 /* If this sequence uses new registers, we may not use it. */
776 if (old_num_regs != reg_rtx_no
777 || ! validate_replace_rtx (src, dest, insn))
779 /* We have to restore reg_rtx_no to its old value, lest
780 recompute_reg_usage will try to compute the usage of the
781 new regs, yet reg_n_info is not valid for them. */
782 reg_rtx_no = old_num_regs;
785 emit_insn_before (seq, insn);
786 move_insn = PREV_INSN (insn);
787 p_move_notes = ®_NOTES (move_insn);
788 p_insn_notes = ®_NOTES (insn);
790 /* Move any notes mentioning src to the move instruction. */
791 for (link = REG_NOTES (insn); link != NULL_RTX; link = next)
793 next = XEXP (link, 1);
794 if (XEXP (link, 0) == src)
796 *p_move_notes = link;
797 p_move_notes = &XEXP (link, 1);
801 *p_insn_notes = link;
802 p_insn_notes = &XEXP (link, 1);
806 *p_move_notes = NULL_RTX;
807 *p_insn_notes = NULL_RTX;
809 /* Is the insn the head of a basic block? If so extend it. */
810 insn_uid = INSN_UID (insn);
811 move_uid = INSN_UID (move_insn);
812 if (insn_uid < old_max_uid)
814 bb = regmove_bb_head[insn_uid];
817 BB_HEAD (BASIC_BLOCK (bb)) = move_insn;
818 regmove_bb_head[insn_uid] = -1;
822 /* Update the various register tables. */
823 dest_regno = REGNO (dest);
824 REG_N_SETS (dest_regno) ++;
825 REG_LIVE_LENGTH (dest_regno)++;
826 if (REGNO_FIRST_UID (dest_regno) == insn_uid)
827 REGNO_FIRST_UID (dest_regno) = move_uid;
829 src_regno = REGNO (src);
830 if (! find_reg_note (move_insn, REG_DEAD, src))
831 REG_LIVE_LENGTH (src_regno)++;
833 if (REGNO_FIRST_UID (src_regno) == insn_uid)
834 REGNO_FIRST_UID (src_regno) = move_uid;
836 if (REGNO_LAST_UID (src_regno) == insn_uid)
837 REGNO_LAST_UID (src_regno) = move_uid;
841 /* reg_set_in_bb[REGNO] points to basic block iff the register is set
842 only once in the given block and has REG_EQUAL note. */
844 basic_block *reg_set_in_bb;
846 /* Size of reg_set_in_bb array. */
847 static unsigned int max_reg_computed;
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 (rtx reg, rtx insn)
869 max_reg_computed = max = max_reg_num ();
870 reg_set_in_bb = xcalloc (max, sizeof (*reg_set_in_bb));
873 for (p = BB_HEAD (bb); p != NEXT_INSN (BB_END (bb));
881 /* This is the instruction which sets REG. If there is a
882 REG_EQUAL note, then REG is equivalent to a constant. */
884 && REG_P (SET_DEST (s))
885 && REG_N_SETS (REGNO (SET_DEST (s))) == 1
886 && find_reg_note (p, REG_EQUAL, NULL_RTX))
887 reg_set_in_bb[REGNO (SET_DEST (s))] = bb;
890 gcc_assert (REGNO (reg) < max_reg_computed);
891 if (reg_set_in_bb[REGNO (reg)] == NULL)
893 if (reg_set_in_bb[REGNO (reg)] != BLOCK_FOR_INSN (insn))
895 /* Look for the set. */
896 for (p = BB_HEAD (BLOCK_FOR_INSN (insn)); p != insn; p = NEXT_INSN (p))
904 && REG_P (SET_DEST (s)) && REGNO (SET_DEST (s)) == REGNO (reg))
906 /* The register is set in the same basic block. */
913 /* INSN is adding a CONST_INT to a REG. We search backwards looking for
914 another add immediate instruction with the same source and dest registers,
915 and if we find one, we change INSN to an increment, and return 1. If
916 no changes are made, we return 0.
919 (set (reg100) (plus reg1 offset1))
921 (set (reg100) (plus reg1 offset2))
923 (set (reg100) (plus reg1 offset1))
925 (set (reg100) (plus reg100 offset2-offset1)) */
927 /* ??? What does this comment mean? */
928 /* cse disrupts preincrement / postdecrement sequences when it finds a
929 hard register as ultimate source, like the frame pointer. */
932 fixup_match_2 (rtx insn, rtx dst, rtx src, rtx offset)
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;
983 "Fixed operand of insn %d.\n",
987 for (p = PREV_INSN (insn); p; p = PREV_INSN (p))
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))
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
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 (rtx f, int nregs)
1056 int old_max_uid = get_max_uid ();
1061 rtx copy_src, copy_dst;
1064 /* ??? Hack. Regmove doesn't examine the CFG, and gets mightily
1065 confused by non-call exceptions ending blocks. */
1066 if (flag_non_call_exceptions)
1069 /* Find out where a potential flags register is live, and so that we
1070 can suppress some optimizations in those zones. */
1071 mark_flags_life_zones (discover_flags_reg ());
1073 regno_src_regno = XNEWVEC (int, nregs);
1074 for (i = nregs; --i >= 0; ) regno_src_regno[i] = -1;
1076 regmove_bb_head = XNEWVEC (int, old_max_uid + 1);
1077 for (i = old_max_uid; i >= 0; i--) regmove_bb_head[i] = -1;
1079 regmove_bb_head[INSN_UID (BB_HEAD (bb))] = bb->index;
1081 /* A forward/backward pass. Replace output operands with input operands. */
1083 for (pass = 0; pass <= 2; pass++)
1085 if (! flag_regmove && pass >= flag_expensive_optimizations)
1089 fprintf (dump_file, "Starting %s pass...\n",
1090 pass ? "backward" : "forward");
1092 for (insn = pass ? get_last_insn () : f; insn;
1093 insn = pass ? PREV_INSN (insn) : NEXT_INSN (insn))
1096 int op_no, match_no;
1098 set = single_set (insn);
1102 if (flag_expensive_optimizations && ! pass
1103 && (GET_CODE (SET_SRC (set)) == SIGN_EXTEND
1104 || GET_CODE (SET_SRC (set)) == ZERO_EXTEND)
1105 && REG_P (XEXP (SET_SRC (set), 0))
1106 && REG_P (SET_DEST (set)))
1107 optimize_reg_copy_3 (insn, SET_DEST (set), SET_SRC (set));
1109 if (flag_expensive_optimizations && ! pass
1110 && REG_P (SET_SRC (set))
1111 && REG_P (SET_DEST (set)))
1113 /* If this is a register-register copy where SRC is not dead,
1114 see if we can optimize it. If this optimization succeeds,
1115 it will become a copy where SRC is dead. */
1116 if ((find_reg_note (insn, REG_DEAD, SET_SRC (set))
1117 || optimize_reg_copy_1 (insn, SET_DEST (set), SET_SRC (set)))
1118 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
1120 /* Similarly for a pseudo-pseudo copy when SRC is dead. */
1121 if (REGNO (SET_SRC (set)) >= FIRST_PSEUDO_REGISTER)
1122 optimize_reg_copy_2 (insn, SET_DEST (set), SET_SRC (set));
1123 if (regno_src_regno[REGNO (SET_DEST (set))] < 0
1124 && SET_SRC (set) != SET_DEST (set))
1126 int srcregno = REGNO (SET_SRC (set));
1127 if (regno_src_regno[srcregno] >= 0)
1128 srcregno = regno_src_regno[srcregno];
1129 regno_src_regno[REGNO (SET_DEST (set))] = srcregno;
1136 if (! find_matches (insn, &match))
1139 /* Now scan through the operands looking for a source operand
1140 which is supposed to match the destination operand.
1141 Then scan forward for an instruction which uses the dest
1143 If it dies there, then replace the dest in both operands with
1144 the source operand. */
1146 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1148 rtx src, dst, src_subreg;
1149 enum reg_class src_class, dst_class;
1151 match_no = match.with[op_no];
1153 /* Nothing to do if the two operands aren't supposed to match. */
1157 src = recog_data.operand[op_no];
1158 dst = recog_data.operand[match_no];
1164 if (GET_CODE (dst) == SUBREG
1165 && GET_MODE_SIZE (GET_MODE (dst))
1166 >= GET_MODE_SIZE (GET_MODE (SUBREG_REG (dst))))
1168 dst = SUBREG_REG (dst);
1169 src_subreg = lowpart_subreg (GET_MODE (dst),
1170 src, GET_MODE (src));
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,
1231 /* A backward pass. Replace input operands with output operands. */
1234 fprintf (dump_file, "Starting backward pass...\n");
1236 for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
1240 int op_no, match_no;
1243 if (! find_matches (insn, &match))
1246 /* Now scan through the operands looking for a destination operand
1247 which is supposed to match a source operand.
1248 Then scan backward for an instruction which sets the source
1249 operand. If safe, then replace the source operand with the
1250 dest operand in both instructions. */
1252 copy_src = NULL_RTX;
1253 copy_dst = NULL_RTX;
1254 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1256 rtx set, p, src, dst;
1257 rtx src_note, dst_note;
1259 enum reg_class src_class, dst_class;
1262 match_no = match.with[op_no];
1264 /* Nothing to do if the two operands aren't supposed to match. */
1268 dst = recog_data.operand[match_no];
1269 src = recog_data.operand[op_no];
1275 || REGNO (dst) < FIRST_PSEUDO_REGISTER
1276 || REG_LIVE_LENGTH (REGNO (dst)) < 0
1277 || GET_MODE (src) != GET_MODE (dst))
1280 /* If the operands already match, then there is nothing to do. */
1281 if (operands_match_p (src, dst))
1284 if (match.commutative[op_no] >= 0)
1286 rtx comm = recog_data.operand[match.commutative[op_no]];
1287 if (operands_match_p (comm, dst))
1291 set = single_set (insn);
1295 /* Note that single_set ignores parts of a parallel set for
1296 which one of the destinations is REG_UNUSED. We can't
1297 handle that here, since we can wind up rewriting things
1298 such that a single register is set twice within a single
1300 if (reg_set_p (src, insn))
1303 /* match_no/dst must be a write-only operand, and
1304 operand_operand/src must be a read-only operand. */
1305 if (match.use[op_no] != READ
1306 || match.use[match_no] != WRITE)
1309 if (match.early_clobber[match_no]
1310 && count_occurrences (PATTERN (insn), src, 0) > 1)
1313 /* Make sure match_no is the destination. */
1314 if (recog_data.operand[match_no] != SET_DEST (set))
1317 if (REGNO (src) < FIRST_PSEUDO_REGISTER)
1319 if (GET_CODE (SET_SRC (set)) == PLUS
1320 && GET_CODE (XEXP (SET_SRC (set), 1)) == CONST_INT
1321 && XEXP (SET_SRC (set), 0) == src
1322 && fixup_match_2 (insn, dst, src,
1323 XEXP (SET_SRC (set), 1)))
1327 src_class = reg_preferred_class (REGNO (src));
1328 dst_class = reg_preferred_class (REGNO (dst));
1330 if (! (src_note = find_reg_note (insn, REG_DEAD, src)))
1332 /* We used to force the copy here like in other cases, but
1333 it produces worse code, as it eliminates no copy
1334 instructions and the copy emitted will be produced by
1335 reload anyway. On patterns with multiple alternatives,
1336 there may be better solution available.
1338 In particular this change produced slower code for numeric
1344 if (! regclass_compatible_p (src_class, dst_class))
1354 /* Can not modify an earlier insn to set dst if this insn
1355 uses an old value in the source. */
1356 if (reg_overlap_mentioned_p (dst, SET_SRC (set)))
1366 /* If src is set once in a different basic block,
1367 and is set equal to a constant, then do not use
1368 it for this optimization, as this would make it
1369 no longer equivalent to a constant. */
1371 if (reg_is_remote_constant_p (src, insn))
1384 "Could fix operand %d of insn %d matching operand %d.\n",
1385 op_no, INSN_UID (insn), match_no);
1387 /* Scan backward to find the first instruction that uses
1388 the input operand. If the operand is set here, then
1389 replace it in both instructions with match_no. */
1391 for (length = 0, p = PREV_INSN (insn); p; p = PREV_INSN (p))
1395 /* ??? We can't scan past the end of a basic block without
1396 updating the register lifetime info
1397 (REG_DEAD/basic_block_live_at_start). */
1398 if (perhaps_ends_bb_p (p))
1400 else if (! INSN_P (p))
1405 /* ??? See if all of SRC is set in P. This test is much
1406 more conservative than it needs to be. */
1407 pset = single_set (p);
1408 if (pset && SET_DEST (pset) == src)
1410 /* We use validate_replace_rtx, in case there
1411 are multiple identical source operands. All of
1412 them have to be changed at the same time. */
1413 if (validate_replace_rtx (src, dst, insn))
1415 if (validate_change (p, &SET_DEST (pset),
1420 /* Change all source operands back.
1421 This modifies the dst as a side-effect. */
1422 validate_replace_rtx (dst, src, insn);
1423 /* Now make sure the dst is right. */
1424 validate_change (insn,
1425 recog_data.operand_loc[match_no],
1432 if (reg_overlap_mentioned_p (src, PATTERN (p))
1433 || reg_overlap_mentioned_p (dst, PATTERN (p)))
1436 /* If we have passed a call instruction, and the
1437 pseudo-reg DST is not already live across a call,
1438 then don't perform the optimization. */
1443 if (REG_N_CALLS_CROSSED (REGNO (dst)) == 0)
1452 /* Remove the death note for SRC from INSN. */
1453 remove_note (insn, src_note);
1454 /* Move the death note for SRC to P if it is used
1456 if (reg_overlap_mentioned_p (src, PATTERN (p)))
1458 XEXP (src_note, 1) = REG_NOTES (p);
1459 REG_NOTES (p) = src_note;
1461 /* If there is a REG_DEAD note for DST on P, then remove
1462 it, because DST is now set there. */
1463 if ((dst_note = find_reg_note (p, REG_DEAD, dst)))
1464 remove_note (p, dst_note);
1466 dstno = REGNO (dst);
1467 srcno = REGNO (src);
1469 REG_N_SETS (dstno)++;
1470 REG_N_SETS (srcno)--;
1472 REG_N_CALLS_CROSSED (dstno) += num_calls;
1473 REG_N_CALLS_CROSSED (srcno) -= num_calls;
1475 REG_LIVE_LENGTH (dstno) += length;
1476 if (REG_LIVE_LENGTH (srcno) >= 0)
1478 REG_LIVE_LENGTH (srcno) -= length;
1479 /* REG_LIVE_LENGTH is only an approximation after
1480 combine if sched is not run, so make sure that we
1481 still have a reasonable value. */
1482 if (REG_LIVE_LENGTH (srcno) < 2)
1483 REG_LIVE_LENGTH (srcno) = 2;
1488 "Fixed operand %d of insn %d matching operand %d.\n",
1489 op_no, INSN_UID (insn), match_no);
1495 /* If we weren't able to replace any of the alternatives, try an
1496 alternative approach of copying the source to the destination. */
1497 if (!success && copy_src != NULL_RTX)
1498 copy_src_to_dest (insn, copy_src, copy_dst, old_max_uid);
1503 /* In fixup_match_1, some insns may have been inserted after basic block
1504 ends. Fix that here. */
1507 rtx end = BB_END (bb);
1509 rtx next = NEXT_INSN (new);
1510 while (next != 0 && INSN_UID (next) >= old_max_uid
1511 && (bb->next_bb == EXIT_BLOCK_PTR || BB_HEAD (bb->next_bb) != next))
1512 new = next, next = NEXT_INSN (new);
1518 free (regno_src_regno);
1519 free (regmove_bb_head);
1522 free (reg_set_in_bb);
1523 reg_set_in_bb = NULL;
1527 /* Returns nonzero if INSN's pattern has matching constraints for any operand.
1528 Returns 0 if INSN can't be recognized, or if the alternative can't be
1531 Initialize the info in MATCHP based on the constraints. */
1534 find_matches (rtx insn, struct match *matchp)
1536 int likely_spilled[MAX_RECOG_OPERANDS];
1538 int any_matches = 0;
1540 extract_insn (insn);
1541 if (! constrain_operands (0))
1544 /* Must initialize this before main loop, because the code for
1545 the commutative case may set matches for operands other than
1547 for (op_no = recog_data.n_operands; --op_no >= 0; )
1548 matchp->with[op_no] = matchp->commutative[op_no] = -1;
1550 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1556 p = recog_data.constraints[op_no];
1558 likely_spilled[op_no] = 0;
1559 matchp->use[op_no] = READ;
1560 matchp->early_clobber[op_no] = 0;
1562 matchp->use[op_no] = WRITE;
1564 matchp->use[op_no] = READWRITE;
1566 for (;*p && i < which_alternative; p++)
1570 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, &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_CONSTRAINT ((unsigned char) c, p) ))
1609 likely_spilled[op_no] = 1;
1612 p += CONSTRAINT_LEN (c, p);
1618 /* Try to replace all occurrences of DST_REG with SRC in LOC, that is
1619 assumed to be in INSN. */
1622 replace_in_call_usage (rtx *loc, unsigned int dst_reg, rtx src, rtx insn)
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 (rtx insn, rtx set, rtx src, rtx src_subreg, rtx dst,
1662 int backward, int operand_number, int match_number)
1665 rtx post_inc = 0, post_inc_set = 0, search_end = 0;
1667 int num_calls = 0, s_num_calls = 0;
1668 enum rtx_code code = NOTE;
1669 HOST_WIDE_INT insn_const = 0, newconst = 0;
1670 rtx overlap = 0; /* need to move insn ? */
1671 rtx src_note = find_reg_note (insn, REG_DEAD, src), dst_note = NULL_RTX;
1672 int length, s_length;
1676 /* Look for (set (regX) (op regA constX))
1677 (set (regY) (op regA constY))
1679 (set (regA) (op regA constX)).
1680 (set (regY) (op regA constY-constX)).
1681 This works for add and shift operations, if
1682 regA is dead after or set by the second insn. */
1684 code = GET_CODE (SET_SRC (set));
1685 if ((code == PLUS || code == LSHIFTRT
1686 || code == ASHIFT || code == ASHIFTRT)
1687 && XEXP (SET_SRC (set), 0) == src
1688 && GET_CODE (XEXP (SET_SRC (set), 1)) == CONST_INT)
1689 insn_const = INTVAL (XEXP (SET_SRC (set), 1));
1690 else if (! stable_and_no_regs_but_for_p (SET_SRC (set), src, dst))
1693 /* We might find a src_note while scanning. */
1699 "Could fix operand %d of insn %d matching operand %d.\n",
1700 operand_number, INSN_UID (insn), match_number);
1702 /* If SRC is equivalent to a constant set in a different basic block,
1703 then do not use it for this optimization. We want the equivalence
1704 so that if we have to reload this register, we can reload the
1705 constant, rather than extending the lifespan of the register. */
1706 if (reg_is_remote_constant_p (src, insn))
1709 /* Scan forward to find the next instruction that
1710 uses the output operand. If the operand dies here,
1711 then replace it in both instructions with
1714 for (length = s_length = 0, p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
1717 replace_in_call_usage (& CALL_INSN_FUNCTION_USAGE (p),
1718 REGNO (dst), src, p);
1720 /* ??? We can't scan past the end of a basic block without updating
1721 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
1722 if (perhaps_ends_bb_p (p))
1724 else if (! INSN_P (p))
1731 if (reg_set_p (src, p) || reg_set_p (dst, p)
1732 || (GET_CODE (PATTERN (p)) == USE
1733 && reg_overlap_mentioned_p (src, XEXP (PATTERN (p), 0))))
1736 /* See if all of DST dies in P. This test is
1737 slightly more conservative than it needs to be. */
1738 if ((dst_note = find_regno_note (p, REG_DEAD, REGNO (dst)))
1739 && (GET_MODE (XEXP (dst_note, 0)) == GET_MODE (dst)))
1741 /* If we would be moving INSN, check that we won't move it
1742 into the shadow of a live a live flags register. */
1743 /* ??? We only try to move it in front of P, although
1744 we could move it anywhere between OVERLAP and P. */
1745 if (overlap && GET_MODE (PREV_INSN (p)) != VOIDmode)
1751 rtx set2 = NULL_RTX;
1753 /* If an optimization is done, the value of SRC while P
1754 is executed will be changed. Check that this is OK. */
1755 if (reg_overlap_mentioned_p (src, PATTERN (p)))
1757 for (q = p; q; q = NEXT_INSN (q))
1759 /* ??? We can't scan past the end of a basic block without
1760 updating the register lifetime info
1761 (REG_DEAD/basic_block_live_at_start). */
1762 if (perhaps_ends_bb_p (q))
1767 else if (! INSN_P (q))
1769 else if (reg_overlap_mentioned_p (src, PATTERN (q))
1770 || reg_set_p (src, q))
1774 set2 = single_set (q);
1775 if (! q || ! set2 || GET_CODE (SET_SRC (set2)) != code
1776 || XEXP (SET_SRC (set2), 0) != src
1777 || GET_CODE (XEXP (SET_SRC (set2), 1)) != CONST_INT
1778 || (SET_DEST (set2) != src
1779 && ! find_reg_note (q, REG_DEAD, src)))
1781 /* If this is a PLUS, we can still save a register by doing
1784 src -= insn_const; .
1785 This also gives opportunities for subsequent
1786 optimizations in the backward pass, so do it there. */
1787 if (code == PLUS && backward
1788 /* Don't do this if we can likely tie DST to SET_DEST
1789 of P later; we can't do this tying here if we got a
1791 && ! (dst_note && ! REG_N_CALLS_CROSSED (REGNO (dst))
1793 && REG_P (SET_DEST (single_set (p)))
1794 && (REGNO (SET_DEST (single_set (p)))
1795 < FIRST_PSEUDO_REGISTER))
1796 /* We may only emit an insn directly after P if we
1797 are not in the shadow of a live flags register. */
1798 && GET_MODE (p) == VOIDmode)
1803 newconst = -insn_const;
1811 newconst = INTVAL (XEXP (SET_SRC (set2), 1)) - insn_const;
1812 /* Reject out of range shifts. */
1815 || ((unsigned HOST_WIDE_INT) newconst
1816 >= (GET_MODE_BITSIZE (GET_MODE
1817 (SET_SRC (set2)))))))
1822 if (SET_DEST (set2) != src)
1823 post_inc_set = set2;
1826 /* We use 1 as last argument to validate_change so that all
1827 changes are accepted or rejected together by apply_change_group
1828 when it is called by validate_replace_rtx . */
1829 validate_change (q, &XEXP (SET_SRC (set2), 1),
1830 GEN_INT (newconst), 1);
1832 validate_change (insn, recog_data.operand_loc[match_number], src, 1);
1833 if (validate_replace_rtx (dst, src_subreg, p))
1838 if (reg_overlap_mentioned_p (dst, PATTERN (p)))
1840 if (! src_note && reg_overlap_mentioned_p (src, PATTERN (p)))
1842 /* INSN was already checked to be movable wrt. the registers that it
1843 sets / uses when we found no REG_DEAD note for src on it, but it
1844 still might clobber the flags register. We'll have to check that
1845 we won't insert it into the shadow of a live flags register when
1846 we finally know where we are to move it. */
1848 src_note = find_reg_note (p, REG_DEAD, src);
1851 /* If we have passed a call instruction, and the pseudo-reg SRC is not
1852 already live across a call, then don't perform the optimization. */
1855 if (REG_N_CALLS_CROSSED (REGNO (src)) == 0)
1869 /* Remove the death note for DST from P. */
1870 remove_note (p, dst_note);
1873 post_inc = emit_insn_after (copy_rtx (PATTERN (insn)), p);
1874 if ((HAVE_PRE_INCREMENT || HAVE_PRE_DECREMENT)
1876 && try_auto_increment (search_end, post_inc, 0, src, newconst, 1))
1878 validate_change (insn, &XEXP (SET_SRC (set), 1), GEN_INT (insn_const), 0);
1879 REG_N_SETS (REGNO (src))++;
1880 REG_LIVE_LENGTH (REGNO (src))++;
1884 /* The lifetime of src and dest overlap,
1885 but we can change this by moving insn. */
1886 rtx pat = PATTERN (insn);
1888 remove_note (overlap, src_note);
1889 if ((HAVE_POST_INCREMENT || HAVE_POST_DECREMENT)
1891 && try_auto_increment (overlap, insn, 0, src, insn_const, 0))
1895 rtx notes = REG_NOTES (insn);
1897 p = emit_insn_after_setloc (pat, PREV_INSN (p), INSN_LOCATOR (insn));
1899 REG_NOTES (p) = notes;
1902 /* Sometimes we'd generate src = const; src += n;
1903 if so, replace the instruction that set src
1904 in the first place. */
1906 if (! overlap && (code == PLUS || code == MINUS))
1908 rtx note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
1909 rtx q, set2 = NULL_RTX;
1910 int num_calls2 = 0, s_length2 = 0;
1912 if (note && CONSTANT_P (XEXP (note, 0)))
1914 for (q = PREV_INSN (insn); q; q = PREV_INSN (q))
1916 /* ??? We can't scan past the end of a basic block without
1917 updating the register lifetime info
1918 (REG_DEAD/basic_block_live_at_start). */
1919 if (perhaps_ends_bb_p (q))
1924 else if (! INSN_P (q))
1928 if (reg_set_p (src, q))
1930 set2 = single_set (q);
1933 if (reg_overlap_mentioned_p (src, PATTERN (q)))
1941 if (q && set2 && SET_DEST (set2) == src && CONSTANT_P (SET_SRC (set2))
1942 && validate_change (insn, &SET_SRC (set), XEXP (note, 0), 0))
1945 REG_N_SETS (REGNO (src))--;
1946 REG_N_CALLS_CROSSED (REGNO (src)) -= num_calls2;
1947 REG_LIVE_LENGTH (REGNO (src)) -= s_length2;
1953 if ((HAVE_PRE_INCREMENT || HAVE_PRE_DECREMENT)
1954 && (code == PLUS || code == MINUS) && insn_const
1955 && try_auto_increment (p, insn, 0, src, insn_const, 1))
1957 else if ((HAVE_POST_INCREMENT || HAVE_POST_DECREMENT)
1959 && try_auto_increment (p, post_inc, post_inc_set, src, newconst, 0))
1961 /* If post_inc still prevails, try to find an
1962 insn where it can be used as a pre-in/decrement.
1963 If code is MINUS, this was already tried. */
1964 if (post_inc && code == PLUS
1965 /* Check that newconst is likely to be usable
1966 in a pre-in/decrement before starting the search. */
1967 && ((HAVE_PRE_INCREMENT && newconst > 0 && newconst <= MOVE_MAX)
1968 || (HAVE_PRE_DECREMENT && newconst < 0 && newconst >= -MOVE_MAX))
1969 && exact_log2 (newconst))
1973 inc_dest = post_inc_set ? SET_DEST (post_inc_set) : src;
1974 for (q = post_inc; (q = NEXT_INSN (q)); )
1976 /* ??? We can't scan past the end of a basic block without updating
1977 the register lifetime info
1978 (REG_DEAD/basic_block_live_at_start). */
1979 if (perhaps_ends_bb_p (q))
1981 else if (! INSN_P (q))
1983 else if (src != inc_dest
1984 && (reg_overlap_mentioned_p (src, PATTERN (q))
1985 || reg_set_p (src, q)))
1987 else if (reg_set_p (inc_dest, q))
1989 else if (reg_overlap_mentioned_p (inc_dest, PATTERN (q)))
1991 try_auto_increment (q, post_inc,
1992 post_inc_set, inc_dest, newconst, 1);
1998 /* Move the death note for DST to INSN if it is used
2000 if (reg_overlap_mentioned_p (dst, PATTERN (insn)))
2002 XEXP (dst_note, 1) = REG_NOTES (insn);
2003 REG_NOTES (insn) = dst_note;
2008 /* Move the death note for SRC from INSN to P. */
2010 remove_note (insn, src_note);
2011 XEXP (src_note, 1) = REG_NOTES (p);
2012 REG_NOTES (p) = src_note;
2014 REG_N_CALLS_CROSSED (REGNO (src)) += s_num_calls;
2017 REG_N_SETS (REGNO (src))++;
2018 REG_N_SETS (REGNO (dst))--;
2020 REG_N_CALLS_CROSSED (REGNO (dst)) -= num_calls;
2022 REG_LIVE_LENGTH (REGNO (src)) += s_length;
2023 if (REG_LIVE_LENGTH (REGNO (dst)) >= 0)
2025 REG_LIVE_LENGTH (REGNO (dst)) -= length;
2026 /* REG_LIVE_LENGTH is only an approximation after
2027 combine if sched is not run, so make sure that we
2028 still have a reasonable value. */
2029 if (REG_LIVE_LENGTH (REGNO (dst)) < 2)
2030 REG_LIVE_LENGTH (REGNO (dst)) = 2;
2034 "Fixed operand %d of insn %d matching operand %d.\n",
2035 operand_number, INSN_UID (insn), match_number);
2040 /* Return nonzero if X is stable and mentions no registers but for
2041 mentioning SRC or mentioning / changing DST . If in doubt, presume
2043 The rationale is that we want to check if we can move an insn easily
2044 while just paying attention to SRC and DST. */
2046 stable_and_no_regs_but_for_p (rtx x, rtx src, rtx dst)
2048 RTX_CODE code = GET_CODE (x);
2049 switch (GET_RTX_CLASS (code))
2053 case RTX_COMM_ARITH:
2055 case RTX_COMM_COMPARE:
2057 case RTX_BITFIELD_OPS:
2060 const char *fmt = GET_RTX_FORMAT (code);
2061 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2063 && ! stable_and_no_regs_but_for_p (XEXP (x, i), src, dst))
2069 return x == src || x == dst;
2070 /* If this is a MEM, look inside - there might be a register hidden in
2071 the address of an unchanging MEM. */
2073 && ! stable_and_no_regs_but_for_p (XEXP (x, 0), src, dst))
2077 return ! rtx_unstable_p (x);
2081 /* Track stack adjustments and stack memory references. Attempt to
2082 reduce the number of stack adjustments by back-propagating across
2083 the memory references.
2085 This is intended primarily for use with targets that do not define
2086 ACCUMULATE_OUTGOING_ARGS. It is of significantly more value to
2087 targets that define PREFERRED_STACK_BOUNDARY more aligned than
2088 STACK_BOUNDARY (e.g. x86), or if not all registers can be pushed
2089 (e.g. x86 fp regs) which would ordinarily have to be implemented
2090 as a sub/mov pair due to restrictions in calls.c.
2092 Propagation stops when any of the insns that need adjusting are
2093 (a) no longer valid because we've exceeded their range, (b) a
2094 non-trivial push instruction, or (c) a call instruction.
2096 Restriction B is based on the assumption that push instructions
2097 are smaller or faster. If a port really wants to remove all
2098 pushes, it should have defined ACCUMULATE_OUTGOING_ARGS. The
2099 one exception that is made is for an add immediately followed
2102 /* This structure records stack memory references between stack adjusting
2107 HOST_WIDE_INT sp_offset;
2109 struct csa_memlist *next;
2112 static int stack_memref_p (rtx);
2113 static rtx single_set_for_csa (rtx);
2114 static void free_csa_memlist (struct csa_memlist *);
2115 static struct csa_memlist *record_one_stack_memref (rtx, rtx *,
2116 struct csa_memlist *);
2117 static int try_apply_stack_adjustment (rtx, struct csa_memlist *,
2118 HOST_WIDE_INT, HOST_WIDE_INT);
2119 static void combine_stack_adjustments_for_block (basic_block);
2120 static int record_stack_memrefs (rtx *, void *);
2123 /* Main entry point for stack adjustment combination. */
2126 combine_stack_adjustments (void)
2131 combine_stack_adjustments_for_block (bb);
2134 /* Recognize a MEM of the form (sp) or (plus sp const). */
2137 stack_memref_p (rtx x)
2143 if (x == stack_pointer_rtx)
2145 if (GET_CODE (x) == PLUS
2146 && XEXP (x, 0) == stack_pointer_rtx
2147 && GET_CODE (XEXP (x, 1)) == CONST_INT)
2153 /* Recognize either normal single_set or the hack in i386.md for
2154 tying fp and sp adjustments. */
2157 single_set_for_csa (rtx insn)
2160 rtx tmp = single_set (insn);
2164 if (!NONJUMP_INSN_P (insn)
2165 || GET_CODE (PATTERN (insn)) != PARALLEL)
2168 tmp = PATTERN (insn);
2169 if (GET_CODE (XVECEXP (tmp, 0, 0)) != SET)
2172 for (i = 1; i < XVECLEN (tmp, 0); ++i)
2174 rtx this = XVECEXP (tmp, 0, i);
2176 /* The special case is allowing a no-op set. */
2177 if (GET_CODE (this) == SET
2178 && SET_SRC (this) == SET_DEST (this))
2180 else if (GET_CODE (this) != CLOBBER
2181 && GET_CODE (this) != USE)
2185 return XVECEXP (tmp, 0, 0);
2188 /* Free the list of csa_memlist nodes. */
2191 free_csa_memlist (struct csa_memlist *memlist)
2193 struct csa_memlist *next;
2194 for (; memlist ; memlist = next)
2196 next = memlist->next;
2201 /* Create a new csa_memlist node from the given memory reference.
2202 It is already known that the memory is stack_memref_p. */
2204 static struct csa_memlist *
2205 record_one_stack_memref (rtx insn, rtx *mem, struct csa_memlist *next_memlist)
2207 struct csa_memlist *ml;
2209 ml = XNEW (struct csa_memlist);
2211 if (XEXP (*mem, 0) == stack_pointer_rtx)
2214 ml->sp_offset = INTVAL (XEXP (XEXP (*mem, 0), 1));
2218 ml->next = next_memlist;
2223 /* Attempt to apply ADJUST to the stack adjusting insn INSN, as well
2224 as each of the memories in MEMLIST. Return true on success. */
2227 try_apply_stack_adjustment (rtx insn, struct csa_memlist *memlist, HOST_WIDE_INT new_adjust,
2228 HOST_WIDE_INT delta)
2230 struct csa_memlist *ml;
2233 set = single_set_for_csa (insn);
2234 validate_change (insn, &XEXP (SET_SRC (set), 1), GEN_INT (new_adjust), 1);
2236 for (ml = memlist; ml ; ml = ml->next)
2239 replace_equiv_address_nv (*ml->mem,
2240 plus_constant (stack_pointer_rtx,
2241 ml->sp_offset - delta)), 1);
2243 if (apply_change_group ())
2245 /* Succeeded. Update our knowledge of the memory references. */
2246 for (ml = memlist; ml ; ml = ml->next)
2247 ml->sp_offset -= delta;
2255 /* Called via for_each_rtx and used to record all stack memory references in
2256 the insn and discard all other stack pointer references. */
2257 struct record_stack_memrefs_data
2260 struct csa_memlist *memlist;
2264 record_stack_memrefs (rtx *xp, void *data)
2267 struct record_stack_memrefs_data *d =
2268 (struct record_stack_memrefs_data *) data;
2271 switch (GET_CODE (x))
2274 if (!reg_mentioned_p (stack_pointer_rtx, x))
2276 /* We are not able to handle correctly all possible memrefs containing
2277 stack pointer, so this check is necessary. */
2278 if (stack_memref_p (x))
2280 d->memlist = record_one_stack_memref (d->insn, xp, d->memlist);
2285 /* ??? We want be able to handle non-memory stack pointer
2286 references later. For now just discard all insns referring to
2287 stack pointer outside mem expressions. We would probably
2288 want to teach validate_replace to simplify expressions first.
2290 We can't just compare with STACK_POINTER_RTX because the
2291 reference to the stack pointer might be in some other mode.
2292 In particular, an explicit clobber in an asm statement will
2293 result in a QImode clobber. */
2294 if (REGNO (x) == STACK_POINTER_REGNUM)
2303 /* Subroutine of combine_stack_adjustments, called for each basic block. */
2306 combine_stack_adjustments_for_block (basic_block bb)
2308 HOST_WIDE_INT last_sp_adjust = 0;
2309 rtx last_sp_set = NULL_RTX;
2310 struct csa_memlist *memlist = NULL;
2311 rtx insn, next, set;
2312 struct record_stack_memrefs_data data;
2313 bool end_of_block = false;
2315 for (insn = BB_HEAD (bb); !end_of_block ; insn = next)
2317 end_of_block = insn == BB_END (bb);
2318 next = NEXT_INSN (insn);
2320 if (! INSN_P (insn))
2323 set = single_set_for_csa (insn);
2326 rtx dest = SET_DEST (set);
2327 rtx src = SET_SRC (set);
2329 /* Find constant additions to the stack pointer. */
2330 if (dest == stack_pointer_rtx
2331 && GET_CODE (src) == PLUS
2332 && XEXP (src, 0) == stack_pointer_rtx
2333 && GET_CODE (XEXP (src, 1)) == CONST_INT)
2335 HOST_WIDE_INT this_adjust = INTVAL (XEXP (src, 1));
2337 /* If we've not seen an adjustment previously, record
2338 it now and continue. */
2342 last_sp_adjust = this_adjust;
2346 /* If not all recorded memrefs can be adjusted, or the
2347 adjustment is now too large for a constant addition,
2348 we cannot merge the two stack adjustments.
2350 Also we need to be careful to not move stack pointer
2351 such that we create stack accesses outside the allocated
2352 area. We can combine an allocation into the first insn,
2353 or a deallocation into the second insn. We can not
2354 combine an allocation followed by a deallocation.
2356 The only somewhat frequent occurrence of the later is when
2357 a function allocates a stack frame but does not use it.
2358 For this case, we would need to analyze rtl stream to be
2359 sure that allocated area is really unused. This means not
2360 only checking the memory references, but also all registers
2361 or global memory references possibly containing a stack
2364 Perhaps the best way to address this problem is to teach
2365 gcc not to allocate stack for objects never used. */
2367 /* Combine an allocation into the first instruction. */
2368 if (STACK_GROWS_DOWNWARD ? this_adjust <= 0 : this_adjust >= 0)
2370 if (try_apply_stack_adjustment (last_sp_set, memlist,
2371 last_sp_adjust + this_adjust,
2376 last_sp_adjust += this_adjust;
2381 /* Otherwise we have a deallocation. Do not combine with
2382 a previous allocation. Combine into the second insn. */
2383 else if (STACK_GROWS_DOWNWARD
2384 ? last_sp_adjust >= 0 : last_sp_adjust <= 0)
2386 if (try_apply_stack_adjustment (insn, memlist,
2387 last_sp_adjust + this_adjust,
2391 delete_insn (last_sp_set);
2393 last_sp_adjust += this_adjust;
2394 free_csa_memlist (memlist);
2400 /* Combination failed. Restart processing from here. If
2401 deallocation+allocation conspired to cancel, we can
2402 delete the old deallocation insn. */
2403 if (last_sp_set && last_sp_adjust == 0)
2405 free_csa_memlist (memlist);
2408 last_sp_adjust = this_adjust;
2412 /* Find a predecrement of exactly the previous adjustment and
2413 turn it into a direct store. Obviously we can't do this if
2414 there were any intervening uses of the stack pointer. */
2417 && ((GET_CODE (XEXP (dest, 0)) == PRE_DEC
2419 == (HOST_WIDE_INT) GET_MODE_SIZE (GET_MODE (dest))))
2420 || (GET_CODE (XEXP (dest, 0)) == PRE_MODIFY
2421 && GET_CODE (XEXP (XEXP (dest, 0), 1)) == PLUS
2422 && XEXP (XEXP (XEXP (dest, 0), 1), 0) == stack_pointer_rtx
2423 && (GET_CODE (XEXP (XEXP (XEXP (dest, 0), 1), 1))
2425 && (INTVAL (XEXP (XEXP (XEXP (dest, 0), 1), 1))
2426 == -last_sp_adjust)))
2427 && XEXP (XEXP (dest, 0), 0) == stack_pointer_rtx
2428 && ! reg_mentioned_p (stack_pointer_rtx, src)
2429 && memory_address_p (GET_MODE (dest), stack_pointer_rtx)
2430 && validate_change (insn, &SET_DEST (set),
2431 replace_equiv_address (dest,
2435 delete_insn (last_sp_set);
2436 free_csa_memlist (memlist);
2438 last_sp_set = NULL_RTX;
2445 data.memlist = memlist;
2446 if (!CALL_P (insn) && last_sp_set
2447 && !for_each_rtx (&PATTERN (insn), record_stack_memrefs, &data))
2449 memlist = data.memlist;
2452 memlist = data.memlist;
2454 /* Otherwise, we were not able to process the instruction.
2455 Do not continue collecting data across such a one. */
2458 || reg_mentioned_p (stack_pointer_rtx, PATTERN (insn))))
2460 if (last_sp_set && last_sp_adjust == 0)
2461 delete_insn (last_sp_set);
2462 free_csa_memlist (memlist);
2464 last_sp_set = NULL_RTX;
2469 if (last_sp_set && last_sp_adjust == 0)
2470 delete_insn (last_sp_set);
2473 free_csa_memlist (memlist);
2477 gate_handle_regmove (void)
2479 return (optimize > 0 && flag_regmove);
2483 /* Register allocation pre-pass, to reduce number of moves necessary
2484 for two-address machines. */
2486 rest_of_handle_regmove (void)
2488 regmove_optimize (get_insns (), max_reg_num ());
2489 cleanup_cfg (CLEANUP_EXPENSIVE | CLEANUP_UPDATE_LIFE);
2493 struct tree_opt_pass pass_regmove =
2495 "regmove", /* name */
2496 gate_handle_regmove, /* gate */
2497 rest_of_handle_regmove, /* execute */
2500 0, /* static_pass_number */
2501 TV_REGMOVE, /* tv_id */
2502 0, /* properties_required */
2503 0, /* properties_provided */
2504 0, /* properties_destroyed */
2505 0, /* todo_flags_start */
2507 TODO_ggc_collect, /* todo_flags_finish */
2513 gate_handle_stack_adjustments (void)
2515 return (optimize > 0);
2519 rest_of_handle_stack_adjustments (void)
2521 life_analysis (PROP_POSTRELOAD);
2522 cleanup_cfg (CLEANUP_EXPENSIVE | CLEANUP_UPDATE_LIFE
2523 | (flag_crossjumping ? CLEANUP_CROSSJUMP : 0));
2525 /* This is kind of a heuristic. We need to run combine_stack_adjustments
2526 even for machines with possibly nonzero RETURN_POPS_ARGS
2527 and ACCUMULATE_OUTGOING_ARGS. We expect that only ports having
2528 push instructions will have popping returns. */
2529 #ifndef PUSH_ROUNDING
2530 if (!ACCUMULATE_OUTGOING_ARGS)
2532 combine_stack_adjustments ();
2536 struct tree_opt_pass pass_stack_adjustments =
2539 gate_handle_stack_adjustments, /* gate */
2540 rest_of_handle_stack_adjustments, /* execute */
2543 0, /* static_pass_number */
2545 0, /* properties_required */
2546 0, /* properties_provided */
2547 0, /* properties_destroyed */
2548 0, /* todo_flags_start */
2550 TODO_ggc_collect, /* todo_flags_finish */
OSDN Git Service
