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 /* We can't make this change if SRC is read or
1433 partially written in P, since we are going to
1434 eliminate SRC. We can't make this change
1435 if DST is mentioned at all in P,
1436 since we are going to change its value. */
1437 if (reg_overlap_mentioned_p (src, PATTERN (p))
1438 || reg_mentioned_p (dst, PATTERN (p)))
1441 /* If we have passed a call instruction, and the
1442 pseudo-reg DST is not already live across a call,
1443 then don't perform the optimization. */
1448 if (REG_N_CALLS_CROSSED (REGNO (dst)) == 0)
1457 /* Remove the death note for SRC from INSN. */
1458 remove_note (insn, src_note);
1459 /* Move the death note for SRC to P if it is used
1461 if (reg_overlap_mentioned_p (src, PATTERN (p)))
1463 XEXP (src_note, 1) = REG_NOTES (p);
1464 REG_NOTES (p) = src_note;
1466 /* If there is a REG_DEAD note for DST on P, then remove
1467 it, because DST is now set there. */
1468 if ((dst_note = find_reg_note (p, REG_DEAD, dst)))
1469 remove_note (p, dst_note);
1471 dstno = REGNO (dst);
1472 srcno = REGNO (src);
1474 REG_N_SETS (dstno)++;
1475 REG_N_SETS (srcno)--;
1477 REG_N_CALLS_CROSSED (dstno) += num_calls;
1478 REG_N_CALLS_CROSSED (srcno) -= num_calls;
1480 REG_LIVE_LENGTH (dstno) += length;
1481 if (REG_LIVE_LENGTH (srcno) >= 0)
1483 REG_LIVE_LENGTH (srcno) -= length;
1484 /* REG_LIVE_LENGTH is only an approximation after
1485 combine if sched is not run, so make sure that we
1486 still have a reasonable value. */
1487 if (REG_LIVE_LENGTH (srcno) < 2)
1488 REG_LIVE_LENGTH (srcno) = 2;
1493 "Fixed operand %d of insn %d matching operand %d.\n",
1494 op_no, INSN_UID (insn), match_no);
1500 /* If we weren't able to replace any of the alternatives, try an
1501 alternative approach of copying the source to the destination. */
1502 if (!success && copy_src != NULL_RTX)
1503 copy_src_to_dest (insn, copy_src, copy_dst, old_max_uid);
1508 /* In fixup_match_1, some insns may have been inserted after basic block
1509 ends. Fix that here. */
1512 rtx end = BB_END (bb);
1514 rtx next = NEXT_INSN (new);
1515 while (next != 0 && INSN_UID (next) >= old_max_uid
1516 && (bb->next_bb == EXIT_BLOCK_PTR || BB_HEAD (bb->next_bb) != next))
1517 new = next, next = NEXT_INSN (new);
1523 free (regno_src_regno);
1524 free (regmove_bb_head);
1527 free (reg_set_in_bb);
1528 reg_set_in_bb = NULL;
1532 /* Returns nonzero if INSN's pattern has matching constraints for any operand.
1533 Returns 0 if INSN can't be recognized, or if the alternative can't be
1536 Initialize the info in MATCHP based on the constraints. */
1539 find_matches (rtx insn, struct match *matchp)
1541 int likely_spilled[MAX_RECOG_OPERANDS];
1543 int any_matches = 0;
1545 extract_insn (insn);
1546 if (! constrain_operands (0))
1549 /* Must initialize this before main loop, because the code for
1550 the commutative case may set matches for operands other than
1552 for (op_no = recog_data.n_operands; --op_no >= 0; )
1553 matchp->with[op_no] = matchp->commutative[op_no] = -1;
1555 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1561 p = recog_data.constraints[op_no];
1563 likely_spilled[op_no] = 0;
1564 matchp->use[op_no] = READ;
1565 matchp->early_clobber[op_no] = 0;
1567 matchp->use[op_no] = WRITE;
1569 matchp->use[op_no] = READWRITE;
1571 for (;*p && i < which_alternative; p++)
1575 while ((c = *p) != '\0' && c != ',')
1584 matchp->early_clobber[op_no] = 1;
1587 matchp->commutative[op_no] = op_no + 1;
1588 matchp->commutative[op_no + 1] = op_no;
1591 case '0': case '1': case '2': case '3': case '4':
1592 case '5': case '6': case '7': case '8': case '9':
1595 unsigned long match_ul = strtoul (p, &end, 10);
1596 int match = match_ul;
1600 if (match < op_no && likely_spilled[match])
1602 matchp->with[op_no] = match;
1604 if (matchp->commutative[op_no] >= 0)
1605 matchp->with[matchp->commutative[op_no]] = match;
1609 case 'a': case 'b': case 'c': case 'd': case 'e': case 'f': case 'h':
1610 case 'j': case 'k': case 'l': case 'p': case 'q': case 't': case 'u':
1611 case 'v': case 'w': case 'x': case 'y': case 'z': case 'A': case 'B':
1612 case 'C': case 'D': case 'W': case 'Y': case 'Z':
1613 if (CLASS_LIKELY_SPILLED_P (REG_CLASS_FROM_CONSTRAINT ((unsigned char) c, p) ))
1614 likely_spilled[op_no] = 1;
1617 p += CONSTRAINT_LEN (c, p);
1623 /* Try to replace all occurrences of DST_REG with SRC in LOC, that is
1624 assumed to be in INSN. */
1627 replace_in_call_usage (rtx *loc, unsigned int dst_reg, rtx src, rtx insn)
1637 code = GET_CODE (x);
1640 if (REGNO (x) != dst_reg)
1643 validate_change (insn, loc, src, 1);
1648 /* Process each of our operands recursively. */
1649 fmt = GET_RTX_FORMAT (code);
1650 for (i = 0; i < GET_RTX_LENGTH (code); i++, fmt++)
1652 replace_in_call_usage (&XEXP (x, i), dst_reg, src, insn);
1653 else if (*fmt == 'E')
1654 for (j = 0; j < XVECLEN (x, i); j++)
1655 replace_in_call_usage (& XVECEXP (x, i, j), dst_reg, src, insn);
1658 /* Try to replace output operand DST in SET, with input operand SRC. SET is
1659 the only set in INSN. INSN has just been recognized and constrained.
1660 SRC is operand number OPERAND_NUMBER in INSN.
1661 DST is operand number MATCH_NUMBER in INSN.
1662 If BACKWARD is nonzero, we have been called in a backward pass.
1663 Return nonzero for success. */
1666 fixup_match_1 (rtx insn, rtx set, rtx src, rtx src_subreg, rtx dst,
1667 int backward, int operand_number, int match_number)
1670 rtx post_inc = 0, post_inc_set = 0, search_end = 0;
1672 int num_calls = 0, s_num_calls = 0;
1673 enum rtx_code code = NOTE;
1674 HOST_WIDE_INT insn_const = 0, newconst = 0;
1675 rtx overlap = 0; /* need to move insn ? */
1676 rtx src_note = find_reg_note (insn, REG_DEAD, src), dst_note = NULL_RTX;
1677 int length, s_length;
1681 /* Look for (set (regX) (op regA constX))
1682 (set (regY) (op regA constY))
1684 (set (regA) (op regA constX)).
1685 (set (regY) (op regA constY-constX)).
1686 This works for add and shift operations, if
1687 regA is dead after or set by the second insn. */
1689 code = GET_CODE (SET_SRC (set));
1690 if ((code == PLUS || code == LSHIFTRT
1691 || code == ASHIFT || code == ASHIFTRT)
1692 && XEXP (SET_SRC (set), 0) == src
1693 && GET_CODE (XEXP (SET_SRC (set), 1)) == CONST_INT)
1694 insn_const = INTVAL (XEXP (SET_SRC (set), 1));
1695 else if (! stable_and_no_regs_but_for_p (SET_SRC (set), src, dst))
1698 /* We might find a src_note while scanning. */
1704 "Could fix operand %d of insn %d matching operand %d.\n",
1705 operand_number, INSN_UID (insn), match_number);
1707 /* If SRC is equivalent to a constant set in a different basic block,
1708 then do not use it for this optimization. We want the equivalence
1709 so that if we have to reload this register, we can reload the
1710 constant, rather than extending the lifespan of the register. */
1711 if (reg_is_remote_constant_p (src, insn))
1714 /* Scan forward to find the next instruction that
1715 uses the output operand. If the operand dies here,
1716 then replace it in both instructions with
1719 for (length = s_length = 0, p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
1722 replace_in_call_usage (& CALL_INSN_FUNCTION_USAGE (p),
1723 REGNO (dst), src, p);
1725 /* ??? We can't scan past the end of a basic block without updating
1726 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
1727 if (perhaps_ends_bb_p (p))
1729 else if (! INSN_P (p))
1736 if (reg_set_p (src, p) || reg_set_p (dst, p)
1737 || (GET_CODE (PATTERN (p)) == USE
1738 && reg_overlap_mentioned_p (src, XEXP (PATTERN (p), 0))))
1741 /* See if all of DST dies in P. This test is
1742 slightly more conservative than it needs to be. */
1743 if ((dst_note = find_regno_note (p, REG_DEAD, REGNO (dst)))
1744 && (GET_MODE (XEXP (dst_note, 0)) == GET_MODE (dst)))
1746 /* If we would be moving INSN, check that we won't move it
1747 into the shadow of a live a live flags register. */
1748 /* ??? We only try to move it in front of P, although
1749 we could move it anywhere between OVERLAP and P. */
1750 if (overlap && GET_MODE (PREV_INSN (p)) != VOIDmode)
1756 rtx set2 = NULL_RTX;
1758 /* If an optimization is done, the value of SRC while P
1759 is executed will be changed. Check that this is OK. */
1760 if (reg_overlap_mentioned_p (src, PATTERN (p)))
1762 for (q = p; q; q = NEXT_INSN (q))
1764 /* ??? We can't scan past the end of a basic block without
1765 updating the register lifetime info
1766 (REG_DEAD/basic_block_live_at_start). */
1767 if (perhaps_ends_bb_p (q))
1772 else if (! INSN_P (q))
1774 else if (reg_overlap_mentioned_p (src, PATTERN (q))
1775 || reg_set_p (src, q))
1779 set2 = single_set (q);
1780 if (! q || ! set2 || GET_CODE (SET_SRC (set2)) != code
1781 || XEXP (SET_SRC (set2), 0) != src
1782 || GET_CODE (XEXP (SET_SRC (set2), 1)) != CONST_INT
1783 || (SET_DEST (set2) != src
1784 && ! find_reg_note (q, REG_DEAD, src)))
1786 /* If this is a PLUS, we can still save a register by doing
1789 src -= insn_const; .
1790 This also gives opportunities for subsequent
1791 optimizations in the backward pass, so do it there. */
1792 if (code == PLUS && backward
1793 /* Don't do this if we can likely tie DST to SET_DEST
1794 of P later; we can't do this tying here if we got a
1796 && ! (dst_note && ! REG_N_CALLS_CROSSED (REGNO (dst))
1798 && REG_P (SET_DEST (single_set (p)))
1799 && (REGNO (SET_DEST (single_set (p)))
1800 < FIRST_PSEUDO_REGISTER))
1801 /* We may only emit an insn directly after P if we
1802 are not in the shadow of a live flags register. */
1803 && GET_MODE (p) == VOIDmode)
1808 newconst = -insn_const;
1816 newconst = INTVAL (XEXP (SET_SRC (set2), 1)) - insn_const;
1817 /* Reject out of range shifts. */
1820 || ((unsigned HOST_WIDE_INT) newconst
1821 >= (GET_MODE_BITSIZE (GET_MODE
1822 (SET_SRC (set2)))))))
1827 if (SET_DEST (set2) != src)
1828 post_inc_set = set2;
1831 /* We use 1 as last argument to validate_change so that all
1832 changes are accepted or rejected together by apply_change_group
1833 when it is called by validate_replace_rtx . */
1834 validate_change (q, &XEXP (SET_SRC (set2), 1),
1835 GEN_INT (newconst), 1);
1837 validate_change (insn, recog_data.operand_loc[match_number], src, 1);
1838 if (validate_replace_rtx (dst, src_subreg, p))
1843 if (reg_overlap_mentioned_p (dst, PATTERN (p)))
1845 if (! src_note && reg_overlap_mentioned_p (src, PATTERN (p)))
1847 /* INSN was already checked to be movable wrt. the registers that it
1848 sets / uses when we found no REG_DEAD note for src on it, but it
1849 still might clobber the flags register. We'll have to check that
1850 we won't insert it into the shadow of a live flags register when
1851 we finally know where we are to move it. */
1853 src_note = find_reg_note (p, REG_DEAD, src);
1856 /* If we have passed a call instruction, and the pseudo-reg SRC is not
1857 already live across a call, then don't perform the optimization. */
1860 if (REG_N_CALLS_CROSSED (REGNO (src)) == 0)
1874 /* Remove the death note for DST from P. */
1875 remove_note (p, dst_note);
1878 post_inc = emit_insn_after (copy_rtx (PATTERN (insn)), p);
1879 if ((HAVE_PRE_INCREMENT || HAVE_PRE_DECREMENT)
1881 && try_auto_increment (search_end, post_inc, 0, src, newconst, 1))
1883 validate_change (insn, &XEXP (SET_SRC (set), 1), GEN_INT (insn_const), 0);
1884 REG_N_SETS (REGNO (src))++;
1885 REG_LIVE_LENGTH (REGNO (src))++;
1889 /* The lifetime of src and dest overlap,
1890 but we can change this by moving insn. */
1891 rtx pat = PATTERN (insn);
1893 remove_note (overlap, src_note);
1894 if ((HAVE_POST_INCREMENT || HAVE_POST_DECREMENT)
1896 && try_auto_increment (overlap, insn, 0, src, insn_const, 0))
1900 rtx notes = REG_NOTES (insn);
1902 p = emit_insn_after_setloc (pat, PREV_INSN (p), INSN_LOCATOR (insn));
1904 REG_NOTES (p) = notes;
1907 /* Sometimes we'd generate src = const; src += n;
1908 if so, replace the instruction that set src
1909 in the first place. */
1911 if (! overlap && (code == PLUS || code == MINUS))
1913 rtx note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
1914 rtx q, set2 = NULL_RTX;
1915 int num_calls2 = 0, s_length2 = 0;
1917 if (note && CONSTANT_P (XEXP (note, 0)))
1919 for (q = PREV_INSN (insn); q; q = PREV_INSN (q))
1921 /* ??? We can't scan past the end of a basic block without
1922 updating the register lifetime info
1923 (REG_DEAD/basic_block_live_at_start). */
1924 if (perhaps_ends_bb_p (q))
1929 else if (! INSN_P (q))
1933 if (reg_set_p (src, q))
1935 set2 = single_set (q);
1938 if (reg_overlap_mentioned_p (src, PATTERN (q)))
1946 if (q && set2 && SET_DEST (set2) == src && CONSTANT_P (SET_SRC (set2))
1947 && validate_change (insn, &SET_SRC (set), XEXP (note, 0), 0))
1950 REG_N_SETS (REGNO (src))--;
1951 REG_N_CALLS_CROSSED (REGNO (src)) -= num_calls2;
1952 REG_LIVE_LENGTH (REGNO (src)) -= s_length2;
1958 if ((HAVE_PRE_INCREMENT || HAVE_PRE_DECREMENT)
1959 && (code == PLUS || code == MINUS) && insn_const
1960 && try_auto_increment (p, insn, 0, src, insn_const, 1))
1962 else if ((HAVE_POST_INCREMENT || HAVE_POST_DECREMENT)
1964 && try_auto_increment (p, post_inc, post_inc_set, src, newconst, 0))
1966 /* If post_inc still prevails, try to find an
1967 insn where it can be used as a pre-in/decrement.
1968 If code is MINUS, this was already tried. */
1969 if (post_inc && code == PLUS
1970 /* Check that newconst is likely to be usable
1971 in a pre-in/decrement before starting the search. */
1972 && ((HAVE_PRE_INCREMENT && newconst > 0 && newconst <= MOVE_MAX)
1973 || (HAVE_PRE_DECREMENT && newconst < 0 && newconst >= -MOVE_MAX))
1974 && exact_log2 (newconst))
1978 inc_dest = post_inc_set ? SET_DEST (post_inc_set) : src;
1979 for (q = post_inc; (q = NEXT_INSN (q)); )
1981 /* ??? We can't scan past the end of a basic block without updating
1982 the register lifetime info
1983 (REG_DEAD/basic_block_live_at_start). */
1984 if (perhaps_ends_bb_p (q))
1986 else if (! INSN_P (q))
1988 else if (src != inc_dest
1989 && (reg_overlap_mentioned_p (src, PATTERN (q))
1990 || reg_set_p (src, q)))
1992 else if (reg_set_p (inc_dest, q))
1994 else if (reg_overlap_mentioned_p (inc_dest, PATTERN (q)))
1996 try_auto_increment (q, post_inc,
1997 post_inc_set, inc_dest, newconst, 1);
2003 /* Move the death note for DST to INSN if it is used
2005 if (reg_overlap_mentioned_p (dst, PATTERN (insn)))
2007 XEXP (dst_note, 1) = REG_NOTES (insn);
2008 REG_NOTES (insn) = dst_note;
2013 /* Move the death note for SRC from INSN to P. */
2015 remove_note (insn, src_note);
2016 XEXP (src_note, 1) = REG_NOTES (p);
2017 REG_NOTES (p) = src_note;
2019 REG_N_CALLS_CROSSED (REGNO (src)) += s_num_calls;
2022 REG_N_SETS (REGNO (src))++;
2023 REG_N_SETS (REGNO (dst))--;
2025 REG_N_CALLS_CROSSED (REGNO (dst)) -= num_calls;
2027 REG_LIVE_LENGTH (REGNO (src)) += s_length;
2028 if (REG_LIVE_LENGTH (REGNO (dst)) >= 0)
2030 REG_LIVE_LENGTH (REGNO (dst)) -= length;
2031 /* REG_LIVE_LENGTH is only an approximation after
2032 combine if sched is not run, so make sure that we
2033 still have a reasonable value. */
2034 if (REG_LIVE_LENGTH (REGNO (dst)) < 2)
2035 REG_LIVE_LENGTH (REGNO (dst)) = 2;
2039 "Fixed operand %d of insn %d matching operand %d.\n",
2040 operand_number, INSN_UID (insn), match_number);
2045 /* Return nonzero if X is stable and mentions no registers but for
2046 mentioning SRC or mentioning / changing DST . If in doubt, presume
2048 The rationale is that we want to check if we can move an insn easily
2049 while just paying attention to SRC and DST. */
2051 stable_and_no_regs_but_for_p (rtx x, rtx src, rtx dst)
2053 RTX_CODE code = GET_CODE (x);
2054 switch (GET_RTX_CLASS (code))
2058 case RTX_COMM_ARITH:
2060 case RTX_COMM_COMPARE:
2062 case RTX_BITFIELD_OPS:
2065 const char *fmt = GET_RTX_FORMAT (code);
2066 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2068 && ! stable_and_no_regs_but_for_p (XEXP (x, i), src, dst))
2074 return x == src || x == dst;
2075 /* If this is a MEM, look inside - there might be a register hidden in
2076 the address of an unchanging MEM. */
2078 && ! stable_and_no_regs_but_for_p (XEXP (x, 0), src, dst))
2082 return ! rtx_unstable_p (x);
2086 /* Track stack adjustments and stack memory references. Attempt to
2087 reduce the number of stack adjustments by back-propagating across
2088 the memory references.
2090 This is intended primarily for use with targets that do not define
2091 ACCUMULATE_OUTGOING_ARGS. It is of significantly more value to
2092 targets that define PREFERRED_STACK_BOUNDARY more aligned than
2093 STACK_BOUNDARY (e.g. x86), or if not all registers can be pushed
2094 (e.g. x86 fp regs) which would ordinarily have to be implemented
2095 as a sub/mov pair due to restrictions in calls.c.
2097 Propagation stops when any of the insns that need adjusting are
2098 (a) no longer valid because we've exceeded their range, (b) a
2099 non-trivial push instruction, or (c) a call instruction.
2101 Restriction B is based on the assumption that push instructions
2102 are smaller or faster. If a port really wants to remove all
2103 pushes, it should have defined ACCUMULATE_OUTGOING_ARGS. The
2104 one exception that is made is for an add immediately followed
2107 /* This structure records stack memory references between stack adjusting
2112 HOST_WIDE_INT sp_offset;
2114 struct csa_memlist *next;
2117 static int stack_memref_p (rtx);
2118 static rtx single_set_for_csa (rtx);
2119 static void free_csa_memlist (struct csa_memlist *);
2120 static struct csa_memlist *record_one_stack_memref (rtx, rtx *,
2121 struct csa_memlist *);
2122 static int try_apply_stack_adjustment (rtx, struct csa_memlist *,
2123 HOST_WIDE_INT, HOST_WIDE_INT);
2124 static void combine_stack_adjustments_for_block (basic_block);
2125 static int record_stack_memrefs (rtx *, void *);
2128 /* Main entry point for stack adjustment combination. */
2131 combine_stack_adjustments (void)
2136 combine_stack_adjustments_for_block (bb);
2139 /* Recognize a MEM of the form (sp) or (plus sp const). */
2142 stack_memref_p (rtx x)
2148 if (x == stack_pointer_rtx)
2150 if (GET_CODE (x) == PLUS
2151 && XEXP (x, 0) == stack_pointer_rtx
2152 && GET_CODE (XEXP (x, 1)) == CONST_INT)
2158 /* Recognize either normal single_set or the hack in i386.md for
2159 tying fp and sp adjustments. */
2162 single_set_for_csa (rtx insn)
2165 rtx tmp = single_set (insn);
2169 if (!NONJUMP_INSN_P (insn)
2170 || GET_CODE (PATTERN (insn)) != PARALLEL)
2173 tmp = PATTERN (insn);
2174 if (GET_CODE (XVECEXP (tmp, 0, 0)) != SET)
2177 for (i = 1; i < XVECLEN (tmp, 0); ++i)
2179 rtx this = XVECEXP (tmp, 0, i);
2181 /* The special case is allowing a no-op set. */
2182 if (GET_CODE (this) == SET
2183 && SET_SRC (this) == SET_DEST (this))
2185 else if (GET_CODE (this) != CLOBBER
2186 && GET_CODE (this) != USE)
2190 return XVECEXP (tmp, 0, 0);
2193 /* Free the list of csa_memlist nodes. */
2196 free_csa_memlist (struct csa_memlist *memlist)
2198 struct csa_memlist *next;
2199 for (; memlist ; memlist = next)
2201 next = memlist->next;
2206 /* Create a new csa_memlist node from the given memory reference.
2207 It is already known that the memory is stack_memref_p. */
2209 static struct csa_memlist *
2210 record_one_stack_memref (rtx insn, rtx *mem, struct csa_memlist *next_memlist)
2212 struct csa_memlist *ml;
2214 ml = XNEW (struct csa_memlist);
2216 if (XEXP (*mem, 0) == stack_pointer_rtx)
2219 ml->sp_offset = INTVAL (XEXP (XEXP (*mem, 0), 1));
2223 ml->next = next_memlist;
2228 /* Attempt to apply ADJUST to the stack adjusting insn INSN, as well
2229 as each of the memories in MEMLIST. Return true on success. */
2232 try_apply_stack_adjustment (rtx insn, struct csa_memlist *memlist, HOST_WIDE_INT new_adjust,
2233 HOST_WIDE_INT delta)
2235 struct csa_memlist *ml;
2238 set = single_set_for_csa (insn);
2239 validate_change (insn, &XEXP (SET_SRC (set), 1), GEN_INT (new_adjust), 1);
2241 for (ml = memlist; ml ; ml = ml->next)
2244 replace_equiv_address_nv (*ml->mem,
2245 plus_constant (stack_pointer_rtx,
2246 ml->sp_offset - delta)), 1);
2248 if (apply_change_group ())
2250 /* Succeeded. Update our knowledge of the memory references. */
2251 for (ml = memlist; ml ; ml = ml->next)
2252 ml->sp_offset -= delta;
2260 /* Called via for_each_rtx and used to record all stack memory references in
2261 the insn and discard all other stack pointer references. */
2262 struct record_stack_memrefs_data
2265 struct csa_memlist *memlist;
2269 record_stack_memrefs (rtx *xp, void *data)
2272 struct record_stack_memrefs_data *d =
2273 (struct record_stack_memrefs_data *) data;
2276 switch (GET_CODE (x))
2279 if (!reg_mentioned_p (stack_pointer_rtx, x))
2281 /* We are not able to handle correctly all possible memrefs containing
2282 stack pointer, so this check is necessary. */
2283 if (stack_memref_p (x))
2285 d->memlist = record_one_stack_memref (d->insn, xp, d->memlist);
2290 /* ??? We want be able to handle non-memory stack pointer
2291 references later. For now just discard all insns referring to
2292 stack pointer outside mem expressions. We would probably
2293 want to teach validate_replace to simplify expressions first.
2295 We can't just compare with STACK_POINTER_RTX because the
2296 reference to the stack pointer might be in some other mode.
2297 In particular, an explicit clobber in an asm statement will
2298 result in a QImode clobber. */
2299 if (REGNO (x) == STACK_POINTER_REGNUM)
2308 /* Subroutine of combine_stack_adjustments, called for each basic block. */
2311 combine_stack_adjustments_for_block (basic_block bb)
2313 HOST_WIDE_INT last_sp_adjust = 0;
2314 rtx last_sp_set = NULL_RTX;
2315 struct csa_memlist *memlist = NULL;
2316 rtx insn, next, set;
2317 struct record_stack_memrefs_data data;
2318 bool end_of_block = false;
2320 for (insn = BB_HEAD (bb); !end_of_block ; insn = next)
2322 end_of_block = insn == BB_END (bb);
2323 next = NEXT_INSN (insn);
2325 if (! INSN_P (insn))
2328 set = single_set_for_csa (insn);
2331 rtx dest = SET_DEST (set);
2332 rtx src = SET_SRC (set);
2334 /* Find constant additions to the stack pointer. */
2335 if (dest == stack_pointer_rtx
2336 && GET_CODE (src) == PLUS
2337 && XEXP (src, 0) == stack_pointer_rtx
2338 && GET_CODE (XEXP (src, 1)) == CONST_INT)
2340 HOST_WIDE_INT this_adjust = INTVAL (XEXP (src, 1));
2342 /* If we've not seen an adjustment previously, record
2343 it now and continue. */
2347 last_sp_adjust = this_adjust;
2351 /* If not all recorded memrefs can be adjusted, or the
2352 adjustment is now too large for a constant addition,
2353 we cannot merge the two stack adjustments.
2355 Also we need to be careful to not move stack pointer
2356 such that we create stack accesses outside the allocated
2357 area. We can combine an allocation into the first insn,
2358 or a deallocation into the second insn. We can not
2359 combine an allocation followed by a deallocation.
2361 The only somewhat frequent occurrence of the later is when
2362 a function allocates a stack frame but does not use it.
2363 For this case, we would need to analyze rtl stream to be
2364 sure that allocated area is really unused. This means not
2365 only checking the memory references, but also all registers
2366 or global memory references possibly containing a stack
2369 Perhaps the best way to address this problem is to teach
2370 gcc not to allocate stack for objects never used. */
2372 /* Combine an allocation into the first instruction. */
2373 if (STACK_GROWS_DOWNWARD ? this_adjust <= 0 : this_adjust >= 0)
2375 if (try_apply_stack_adjustment (last_sp_set, memlist,
2376 last_sp_adjust + this_adjust,
2381 last_sp_adjust += this_adjust;
2386 /* Otherwise we have a deallocation. Do not combine with
2387 a previous allocation. Combine into the second insn. */
2388 else if (STACK_GROWS_DOWNWARD
2389 ? last_sp_adjust >= 0 : last_sp_adjust <= 0)
2391 if (try_apply_stack_adjustment (insn, memlist,
2392 last_sp_adjust + this_adjust,
2396 delete_insn (last_sp_set);
2398 last_sp_adjust += this_adjust;
2399 free_csa_memlist (memlist);
2405 /* Combination failed. Restart processing from here. If
2406 deallocation+allocation conspired to cancel, we can
2407 delete the old deallocation insn. */
2408 if (last_sp_set && last_sp_adjust == 0)
2410 free_csa_memlist (memlist);
2413 last_sp_adjust = this_adjust;
2417 /* Find a predecrement of exactly the previous adjustment and
2418 turn it into a direct store. Obviously we can't do this if
2419 there were any intervening uses of the stack pointer. */
2422 && ((GET_CODE (XEXP (dest, 0)) == PRE_DEC
2424 == (HOST_WIDE_INT) GET_MODE_SIZE (GET_MODE (dest))))
2425 || (GET_CODE (XEXP (dest, 0)) == PRE_MODIFY
2426 && GET_CODE (XEXP (XEXP (dest, 0), 1)) == PLUS
2427 && XEXP (XEXP (XEXP (dest, 0), 1), 0) == stack_pointer_rtx
2428 && (GET_CODE (XEXP (XEXP (XEXP (dest, 0), 1), 1))
2430 && (INTVAL (XEXP (XEXP (XEXP (dest, 0), 1), 1))
2431 == -last_sp_adjust)))
2432 && XEXP (XEXP (dest, 0), 0) == stack_pointer_rtx
2433 && ! reg_mentioned_p (stack_pointer_rtx, src)
2434 && memory_address_p (GET_MODE (dest), stack_pointer_rtx)
2435 && validate_change (insn, &SET_DEST (set),
2436 replace_equiv_address (dest,
2440 delete_insn (last_sp_set);
2441 free_csa_memlist (memlist);
2443 last_sp_set = NULL_RTX;
2450 data.memlist = memlist;
2451 if (!CALL_P (insn) && last_sp_set
2452 && !for_each_rtx (&PATTERN (insn), record_stack_memrefs, &data))
2454 memlist = data.memlist;
2457 memlist = data.memlist;
2459 /* Otherwise, we were not able to process the instruction.
2460 Do not continue collecting data across such a one. */
2463 || reg_mentioned_p (stack_pointer_rtx, PATTERN (insn))))
2465 if (last_sp_set && last_sp_adjust == 0)
2466 delete_insn (last_sp_set);
2467 free_csa_memlist (memlist);
2469 last_sp_set = NULL_RTX;
2474 if (last_sp_set && last_sp_adjust == 0)
2475 delete_insn (last_sp_set);
2478 free_csa_memlist (memlist);
2482 gate_handle_regmove (void)
2484 return (optimize > 0 && flag_regmove);
2488 /* Register allocation pre-pass, to reduce number of moves necessary
2489 for two-address machines. */
2491 rest_of_handle_regmove (void)
2493 regmove_optimize (get_insns (), max_reg_num ());
2494 cleanup_cfg (CLEANUP_EXPENSIVE | CLEANUP_UPDATE_LIFE);
2498 struct tree_opt_pass pass_regmove =
2500 "regmove", /* name */
2501 gate_handle_regmove, /* gate */
2502 rest_of_handle_regmove, /* execute */
2505 0, /* static_pass_number */
2506 TV_REGMOVE, /* tv_id */
2507 0, /* properties_required */
2508 0, /* properties_provided */
2509 0, /* properties_destroyed */
2510 0, /* todo_flags_start */
2512 TODO_ggc_collect, /* todo_flags_finish */
2518 gate_handle_stack_adjustments (void)
2520 return (optimize > 0);
2524 rest_of_handle_stack_adjustments (void)
2526 life_analysis (PROP_POSTRELOAD);
2527 cleanup_cfg (CLEANUP_EXPENSIVE | CLEANUP_UPDATE_LIFE
2528 | (flag_crossjumping ? CLEANUP_CROSSJUMP : 0));
2530 /* This is kind of a heuristic. We need to run combine_stack_adjustments
2531 even for machines with possibly nonzero RETURN_POPS_ARGS
2532 and ACCUMULATE_OUTGOING_ARGS. We expect that only ports having
2533 push instructions will have popping returns. */
2534 #ifndef PUSH_ROUNDING
2535 if (!ACCUMULATE_OUTGOING_ARGS)
2537 combine_stack_adjustments ();
2541 struct tree_opt_pass pass_stack_adjustments =
2544 gate_handle_stack_adjustments, /* gate */
2545 rest_of_handle_stack_adjustments, /* execute */
2548 0, /* static_pass_number */
2550 0, /* properties_required */
2551 0, /* properties_provided */
2552 0, /* properties_destroyed */
2553 0, /* todo_flags_start */
2555 TODO_ggc_collect, /* todo_flags_finish */
OSDN Git Service
