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 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
23 /* This module looks for cases where matching constraints would force
24 an instruction to need a reload, and this reload would be a register
25 to register move. It then attempts to change the registers used by the
26 instruction to avoid the move instruction. */
30 #include "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"
48 /* Turn STACK_GROWS_DOWNWARD into a boolean. */
49 #ifdef STACK_GROWS_DOWNWARD
50 #undef STACK_GROWS_DOWNWARD
51 #define STACK_GROWS_DOWNWARD 1
53 #define STACK_GROWS_DOWNWARD 0
56 static int perhaps_ends_bb_p (rtx);
57 static int optimize_reg_copy_1 (rtx, rtx, rtx);
58 static void optimize_reg_copy_2 (rtx, rtx, rtx);
59 static void optimize_reg_copy_3 (rtx, rtx, rtx);
60 static void copy_src_to_dest (rtx, rtx, rtx, int);
61 static int *regmove_bb_head;
64 int with[MAX_RECOG_OPERANDS];
65 enum { READ, WRITE, READWRITE } use[MAX_RECOG_OPERANDS];
66 int commutative[MAX_RECOG_OPERANDS];
67 int early_clobber[MAX_RECOG_OPERANDS];
70 static rtx discover_flags_reg (void);
71 static void mark_flags_life_zones (rtx);
72 static void flags_set_1 (rtx, rtx, void *);
74 static int try_auto_increment (rtx, rtx, rtx, rtx, HOST_WIDE_INT, int);
75 static int find_matches (rtx, struct match *);
76 static void replace_in_call_usage (rtx *, unsigned int, rtx, rtx);
77 static int fixup_match_1 (rtx, rtx, rtx, rtx, rtx, int, int, int, FILE *);
78 static int reg_is_remote_constant_p (rtx, rtx, rtx);
79 static int stable_and_no_regs_but_for_p (rtx, rtx, rtx);
80 static int regclass_compatible_p (int, int);
81 static int replacement_quality (rtx);
82 static int fixup_match_2 (rtx, rtx, rtx, rtx, FILE *);
84 /* Return nonzero if registers with CLASS1 and CLASS2 can be merged without
85 causing too much register allocation problems. */
87 regclass_compatible_p (int class0, int class1)
89 return (class0 == class1
90 || (reg_class_subset_p (class0, class1)
91 && ! CLASS_LIKELY_SPILLED_P (class0))
92 || (reg_class_subset_p (class1, class0)
93 && ! CLASS_LIKELY_SPILLED_P (class1)));
96 /* INC_INSN is an instruction that adds INCREMENT to REG.
97 Try to fold INC_INSN as a post/pre in/decrement into INSN.
98 Iff INC_INSN_SET is nonzero, inc_insn has a destination different from src.
99 Return nonzero for success. */
101 try_auto_increment (rtx insn, rtx inc_insn, rtx inc_insn_set, rtx reg,
102 HOST_WIDE_INT increment, int pre)
104 enum rtx_code inc_code;
106 rtx pset = single_set (insn);
109 /* Can't use the size of SET_SRC, we might have something like
110 (sign_extend:SI (mem:QI ... */
111 rtx use = find_use_as_address (pset, reg, 0);
112 if (use != 0 && use != (rtx) (size_t) 1)
114 int size = GET_MODE_SIZE (GET_MODE (use));
116 || (HAVE_POST_INCREMENT
117 && pre == 0 && (inc_code = POST_INC, increment == size))
118 || (HAVE_PRE_INCREMENT
119 && pre == 1 && (inc_code = PRE_INC, increment == size))
120 || (HAVE_POST_DECREMENT
121 && pre == 0 && (inc_code = POST_DEC, increment == -size))
122 || (HAVE_PRE_DECREMENT
123 && pre == 1 && (inc_code = PRE_DEC, increment == -size))
129 &SET_SRC (inc_insn_set),
130 XEXP (SET_SRC (inc_insn_set), 0), 1);
131 validate_change (insn, &XEXP (use, 0),
132 gen_rtx_fmt_e (inc_code, Pmode, reg), 1);
133 if (apply_change_group ())
135 /* If there is a REG_DEAD note on this insn, we must
136 change this not to REG_UNUSED meaning that the register
137 is set, but the value is dead. Failure to do so will
138 result in a sched1 abort -- when it recomputes lifetime
139 information, the number of REG_DEAD notes will have
141 rtx note = find_reg_note (insn, REG_DEAD, reg);
143 PUT_MODE (note, REG_UNUSED);
146 = gen_rtx_EXPR_LIST (REG_INC,
147 reg, REG_NOTES (insn));
149 delete_insn (inc_insn);
158 /* Determine if the pattern generated by add_optab has a clobber,
159 such as might be issued for a flags hard register. To make the
160 code elsewhere simpler, we handle cc0 in this same framework.
162 Return the register if one was discovered. Return NULL_RTX if
163 if no flags were found. Return pc_rtx if we got confused. */
166 discover_flags_reg (void)
169 tmp = gen_rtx_REG (word_mode, 10000);
170 tmp = gen_add3_insn (tmp, tmp, GEN_INT (2));
172 /* If we get something that isn't a simple set, or a
173 [(set ..) (clobber ..)], this whole function will go wrong. */
174 if (GET_CODE (tmp) == SET)
176 else if (GET_CODE (tmp) == PARALLEL)
180 if (XVECLEN (tmp, 0) != 2)
182 tmp = XVECEXP (tmp, 0, 1);
183 if (GET_CODE (tmp) != CLOBBER)
187 /* Don't do anything foolish if the md wanted to clobber a
188 scratch or something. We only care about hard regs.
189 Moreover we don't like the notion of subregs of hard regs. */
190 if (GET_CODE (tmp) == SUBREG
191 && GET_CODE (SUBREG_REG (tmp)) == REG
192 && REGNO (SUBREG_REG (tmp)) < FIRST_PSEUDO_REGISTER)
194 found = (GET_CODE (tmp) == REG && REGNO (tmp) < FIRST_PSEUDO_REGISTER);
196 return (found ? tmp : NULL_RTX);
202 /* It is a tedious task identifying when the flags register is live and
203 when it is safe to optimize. Since we process the instruction stream
204 multiple times, locate and record these live zones by marking the
205 mode of the instructions --
207 QImode is used on the instruction at which the flags becomes live.
209 HImode is used within the range (exclusive) that the flags are
210 live. Thus the user of the flags is not marked.
212 All other instructions are cleared to VOIDmode. */
214 /* Used to communicate with flags_set_1. */
215 static rtx flags_set_1_rtx;
216 static int flags_set_1_set;
219 mark_flags_life_zones (rtx flags)
226 /* If we found a flags register on a cc0 host, bail. */
227 if (flags == NULL_RTX)
229 else if (flags != cc0_rtx)
233 /* Simple cases first: if no flags, clear all modes. If confusing,
234 mark the entire function as being in a flags shadow. */
235 if (flags == NULL_RTX || flags == pc_rtx)
237 enum machine_mode mode = (flags ? HImode : VOIDmode);
239 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
240 PUT_MODE (insn, mode);
248 flags_regno = REGNO (flags);
249 flags_nregs = HARD_REGNO_NREGS (flags_regno, GET_MODE (flags));
251 flags_set_1_rtx = flags;
253 /* Process each basic block. */
254 FOR_EACH_BB_REVERSE (block)
259 insn = BB_HEAD (block);
260 end = BB_END (block);
262 /* Look out for the (unlikely) case of flags being live across
263 basic block boundaries. */
268 for (i = 0; i < flags_nregs; ++i)
269 live |= REGNO_REG_SET_P (block->global_live_at_start,
276 /* Process liveness in reverse order of importance --
277 alive, death, birth. This lets more important info
278 overwrite the mode of lesser info. */
283 /* In the cc0 case, death is not marked in reg notes,
284 but is instead the mere use of cc0 when it is alive. */
285 if (live && reg_mentioned_p (cc0_rtx, PATTERN (insn)))
288 /* In the hard reg case, we watch death notes. */
289 if (live && find_regno_note (insn, REG_DEAD, flags_regno))
292 PUT_MODE (insn, (live ? HImode : VOIDmode));
294 /* In either case, birth is denoted simply by it's presence
295 as the destination of a set. */
297 note_stores (PATTERN (insn), flags_set_1, NULL);
301 PUT_MODE (insn, QImode);
305 PUT_MODE (insn, (live ? HImode : VOIDmode));
309 insn = NEXT_INSN (insn);
314 /* A subroutine of mark_flags_life_zones, called through note_stores. */
317 flags_set_1 (rtx x, rtx pat, void *data ATTRIBUTE_UNUSED)
319 if (GET_CODE (pat) == SET
320 && reg_overlap_mentioned_p (x, flags_set_1_rtx))
324 static int *regno_src_regno;
326 /* Indicate how good a choice REG (which appears as a source) is to replace
327 a destination register with. The higher the returned value, the better
328 the choice. The main objective is to avoid using a register that is
329 a candidate for tying to a hard register, since the output might in
330 turn be a candidate to be tied to a different hard register. */
332 replacement_quality (rtx reg)
336 /* Bad if this isn't a register at all. */
337 if (GET_CODE (reg) != REG)
340 /* If this register is not meant to get a hard register,
341 it is a poor choice. */
342 if (REG_LIVE_LENGTH (REGNO (reg)) < 0)
345 src_regno = regno_src_regno[REGNO (reg)];
347 /* If it was not copied from another register, it is fine. */
351 /* Copied from a hard register? */
352 if (src_regno < FIRST_PSEUDO_REGISTER)
355 /* Copied from a pseudo register - not as bad as from a hard register,
356 yet still cumbersome, since the register live length will be lengthened
357 when the registers get tied. */
361 /* Return 1 if INSN might end a basic block. */
363 static int perhaps_ends_bb_p (rtx insn)
365 switch (GET_CODE (insn))
369 /* These always end a basic block. */
373 /* A CALL_INSN might be the last insn of a basic block, if it is inside
374 an EH region or if there are nonlocal gotos. Note that this test is
375 very conservative. */
376 if (nonlocal_goto_handler_labels)
380 return can_throw_internal (insn);
384 /* INSN is a copy from SRC to DEST, both registers, and SRC does not die
387 Search forward to see if SRC dies before either it or DEST is modified,
388 but don't scan past the end of a basic block. If so, we can replace SRC
389 with DEST and let SRC die in INSN.
391 This will reduce the number of registers live in that range and may enable
392 DEST to be tied to SRC, thus often saving one register in addition to a
393 register-register copy. */
396 optimize_reg_copy_1 (rtx insn, rtx dest, rtx src)
401 int sregno = REGNO (src);
402 int dregno = REGNO (dest);
404 /* We don't want to mess with hard regs if register classes are small. */
406 || (SMALL_REGISTER_CLASSES
407 && (sregno < FIRST_PSEUDO_REGISTER
408 || dregno < FIRST_PSEUDO_REGISTER))
409 /* We don't see all updates to SP if they are in an auto-inc memory
410 reference, so we must disallow this optimization on them. */
411 || sregno == STACK_POINTER_REGNUM || dregno == STACK_POINTER_REGNUM)
414 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
416 /* ??? We can't scan past the end of a basic block without updating
417 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
418 if (perhaps_ends_bb_p (p))
420 else if (! INSN_P (p))
423 if (reg_set_p (src, p) || reg_set_p (dest, p)
424 /* If SRC is an asm-declared register, it must not be replaced
425 in any asm. Unfortunately, the REG_EXPR tree for the asm
426 variable may be absent in the SRC rtx, so we can't check the
427 actual register declaration easily (the asm operand will have
428 it, though). To avoid complicating the test for a rare case,
429 we just don't perform register replacement for a hard reg
430 mentioned in an asm. */
431 || (sregno < FIRST_PSEUDO_REGISTER
432 && asm_noperands (PATTERN (p)) >= 0
433 && reg_overlap_mentioned_p (src, PATTERN (p)))
434 /* Don't change a USE of a register. */
435 || (GET_CODE (PATTERN (p)) == USE
436 && reg_overlap_mentioned_p (src, XEXP (PATTERN (p), 0))))
439 /* See if all of SRC dies in P. This test is slightly more
440 conservative than it needs to be. */
441 if ((note = find_regno_note (p, REG_DEAD, sregno)) != 0
442 && GET_MODE (XEXP (note, 0)) == GET_MODE (src))
450 /* We can do the optimization. Scan forward from INSN again,
451 replacing regs as we go. Set FAILED if a replacement can't
452 be done. In that case, we can't move the death note for SRC.
453 This should be rare. */
455 /* Set to stop at next insn. */
456 for (q = next_real_insn (insn);
457 q != next_real_insn (p);
458 q = next_real_insn (q))
460 if (reg_overlap_mentioned_p (src, PATTERN (q)))
462 /* If SRC is a hard register, we might miss some
463 overlapping registers with validate_replace_rtx,
464 so we would have to undo it. We can't if DEST is
465 present in the insn, so fail in that combination
467 if (sregno < FIRST_PSEUDO_REGISTER
468 && reg_mentioned_p (dest, PATTERN (q)))
471 /* Replace all uses and make sure that the register
472 isn't still present. */
473 else if (validate_replace_rtx (src, dest, q)
474 && (sregno >= FIRST_PSEUDO_REGISTER
475 || ! reg_overlap_mentioned_p (src,
480 validate_replace_rtx (dest, src, q);
485 /* For SREGNO, count the total number of insns scanned.
486 For DREGNO, count the total number of insns scanned after
487 passing the death note for DREGNO. */
492 /* If the insn in which SRC dies is a CALL_INSN, don't count it
493 as a call that has been crossed. Otherwise, count it. */
494 if (q != p && GET_CODE (q) == CALL_INSN)
496 /* Similarly, total calls for SREGNO, total calls beyond
497 the death note for DREGNO. */
503 /* If DEST dies here, remove the death note and save it for
504 later. Make sure ALL of DEST dies here; again, this is
505 overly conservative. */
507 && (dest_death = find_regno_note (q, REG_DEAD, dregno)) != 0)
509 if (GET_MODE (XEXP (dest_death, 0)) != GET_MODE (dest))
510 failed = 1, dest_death = 0;
512 remove_note (q, dest_death);
518 /* These counters need to be updated if and only if we are
519 going to move the REG_DEAD note. */
520 if (sregno >= FIRST_PSEUDO_REGISTER)
522 if (REG_LIVE_LENGTH (sregno) >= 0)
524 REG_LIVE_LENGTH (sregno) -= s_length;
525 /* REG_LIVE_LENGTH is only an approximation after
526 combine if sched is not run, so make sure that we
527 still have a reasonable value. */
528 if (REG_LIVE_LENGTH (sregno) < 2)
529 REG_LIVE_LENGTH (sregno) = 2;
532 REG_N_CALLS_CROSSED (sregno) -= s_n_calls;
535 /* Move death note of SRC from P to INSN. */
536 remove_note (p, note);
537 XEXP (note, 1) = REG_NOTES (insn);
538 REG_NOTES (insn) = note;
541 /* DEST is also dead if INSN has a REG_UNUSED note for DEST. */
543 && (dest_death = find_regno_note (insn, REG_UNUSED, dregno)))
545 PUT_REG_NOTE_KIND (dest_death, REG_DEAD);
546 remove_note (insn, dest_death);
549 /* Put death note of DEST on P if we saw it die. */
552 XEXP (dest_death, 1) = REG_NOTES (p);
553 REG_NOTES (p) = dest_death;
555 if (dregno >= FIRST_PSEUDO_REGISTER)
557 /* If and only if we are moving the death note for DREGNO,
558 then we need to update its counters. */
559 if (REG_LIVE_LENGTH (dregno) >= 0)
560 REG_LIVE_LENGTH (dregno) += d_length;
561 REG_N_CALLS_CROSSED (dregno) += d_n_calls;
568 /* If SRC is a hard register which is set or killed in some other
569 way, we can't do this optimization. */
570 else if (sregno < FIRST_PSEUDO_REGISTER
571 && dead_or_set_p (p, src))
577 /* INSN is a copy of SRC to DEST, in which SRC dies. See if we now have
578 a sequence of insns that modify DEST followed by an insn that sets
579 SRC to DEST in which DEST dies, with no prior modification of DEST.
580 (There is no need to check if the insns in between actually modify
581 DEST. We should not have cases where DEST is not modified, but
582 the optimization is safe if no such modification is detected.)
583 In that case, we can replace all uses of DEST, starting with INSN and
584 ending with the set of SRC to DEST, with SRC. We do not do this
585 optimization if a CALL_INSN is crossed unless SRC already crosses a
586 call or if DEST dies before the copy back to SRC.
588 It is assumed that DEST and SRC are pseudos; it is too complicated to do
589 this for hard registers since the substitutions we may make might fail. */
592 optimize_reg_copy_2 (rtx insn, rtx dest, rtx src)
596 int sregno = REGNO (src);
597 int dregno = REGNO (dest);
599 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
601 /* ??? We can't scan past the end of a basic block without updating
602 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
603 if (perhaps_ends_bb_p (p))
605 else if (! INSN_P (p))
608 set = single_set (p);
609 if (set && SET_SRC (set) == dest && SET_DEST (set) == src
610 && find_reg_note (p, REG_DEAD, dest))
612 /* We can do the optimization. Scan forward from INSN again,
613 replacing regs as we go. */
615 /* Set to stop at next insn. */
616 for (q = insn; q != NEXT_INSN (p); q = NEXT_INSN (q))
619 if (reg_mentioned_p (dest, PATTERN (q)))
620 PATTERN (q) = replace_rtx (PATTERN (q), dest, src);
623 if (GET_CODE (q) == CALL_INSN)
625 REG_N_CALLS_CROSSED (dregno)--;
626 REG_N_CALLS_CROSSED (sregno)++;
630 remove_note (p, find_reg_note (p, REG_DEAD, dest));
631 REG_N_DEATHS (dregno)--;
632 remove_note (insn, find_reg_note (insn, REG_DEAD, src));
633 REG_N_DEATHS (sregno)--;
637 if (reg_set_p (src, p)
638 || find_reg_note (p, REG_DEAD, dest)
639 || (GET_CODE (p) == CALL_INSN && REG_N_CALLS_CROSSED (sregno) == 0))
643 /* INSN is a ZERO_EXTEND or SIGN_EXTEND of SRC to DEST.
644 Look if SRC dies there, and if it is only set once, by loading
645 it from memory. If so, try to incorporate the zero/sign extension
646 into the memory read, change SRC to the mode of DEST, and alter
647 the remaining accesses to use the appropriate SUBREG. This allows
648 SRC and DEST to be tied later. */
650 optimize_reg_copy_3 (rtx insn, rtx dest, rtx src)
652 rtx src_reg = XEXP (src, 0);
653 int src_no = REGNO (src_reg);
654 int dst_no = REGNO (dest);
656 enum machine_mode old_mode;
658 if (src_no < FIRST_PSEUDO_REGISTER
659 || dst_no < FIRST_PSEUDO_REGISTER
660 || ! find_reg_note (insn, REG_DEAD, src_reg)
661 || REG_N_DEATHS (src_no) != 1
662 || REG_N_SETS (src_no) != 1)
664 for (p = PREV_INSN (insn); p && ! reg_set_p (src_reg, p); p = PREV_INSN (p))
665 /* ??? We can't scan past the end of a basic block without updating
666 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
667 if (perhaps_ends_bb_p (p))
673 if (! (set = single_set (p))
674 || GET_CODE (SET_SRC (set)) != MEM
675 /* If there's a REG_EQUIV note, this must be an insn that loads an
676 argument. Prefer keeping the note over doing this optimization. */
677 || find_reg_note (p, REG_EQUIV, NULL_RTX)
678 || SET_DEST (set) != src_reg)
681 /* Be conservative: although this optimization is also valid for
682 volatile memory references, that could cause trouble in later passes. */
683 if (MEM_VOLATILE_P (SET_SRC (set)))
686 /* Do not use a SUBREG to truncate from one mode to another if truncation
688 if (GET_MODE_BITSIZE (GET_MODE (src_reg)) <= GET_MODE_BITSIZE (GET_MODE (src))
689 && !TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (GET_MODE (src)),
690 GET_MODE_BITSIZE (GET_MODE (src_reg))))
693 old_mode = GET_MODE (src_reg);
694 PUT_MODE (src_reg, GET_MODE (src));
695 XEXP (src, 0) = SET_SRC (set);
697 /* Include this change in the group so that it's easily undone if
698 one of the changes in the group is invalid. */
699 validate_change (p, &SET_SRC (set), src, 1);
701 /* Now walk forward making additional replacements. We want to be able
702 to undo all the changes if a later substitution fails. */
703 subreg = gen_lowpart_SUBREG (old_mode, src_reg);
704 while (p = NEXT_INSN (p), p != insn)
709 /* Make a tentative change. */
710 validate_replace_rtx_group (src_reg, subreg, p);
713 validate_replace_rtx_group (src, src_reg, insn);
715 /* Now see if all the changes are valid. */
716 if (! apply_change_group ())
718 /* One or more changes were no good. Back out everything. */
719 PUT_MODE (src_reg, old_mode);
720 XEXP (src, 0) = src_reg;
724 rtx note = find_reg_note (p, REG_EQUAL, NULL_RTX);
726 remove_note (p, note);
731 /* If we were not able to update the users of src to use dest directly, try
732 instead moving the value to dest directly before the operation. */
735 copy_src_to_dest (rtx insn, rtx src, rtx dest, int old_max_uid)
750 /* A REG_LIVE_LENGTH of -1 indicates the register is equivalent to a constant
751 or memory location and is used infrequently; a REG_LIVE_LENGTH of -2 is
752 parameter when there is no frame pointer that is not allocated a register.
753 For now, we just reject them, rather than incrementing the live length. */
755 if (GET_CODE (src) == REG
756 && REG_LIVE_LENGTH (REGNO (src)) > 0
757 && GET_CODE (dest) == REG
758 && !RTX_UNCHANGING_P (dest)
759 && REG_LIVE_LENGTH (REGNO (dest)) > 0
760 && (set = single_set (insn)) != NULL_RTX
761 && !reg_mentioned_p (dest, SET_SRC (set))
762 && GET_MODE (src) == GET_MODE (dest))
764 int old_num_regs = reg_rtx_no;
766 /* Generate the src->dest move. */
768 emit_move_insn (dest, src);
771 /* If this sequence uses new registers, we may not use it. */
772 if (old_num_regs != reg_rtx_no
773 || ! validate_replace_rtx (src, dest, insn))
775 /* We have to restore reg_rtx_no to its old value, lest
776 recompute_reg_usage will try to compute the usage of the
777 new regs, yet reg_n_info is not valid for them. */
778 reg_rtx_no = old_num_regs;
781 emit_insn_before (seq, insn);
782 move_insn = PREV_INSN (insn);
783 p_move_notes = ®_NOTES (move_insn);
784 p_insn_notes = ®_NOTES (insn);
786 /* Move any notes mentioning src to the move instruction. */
787 for (link = REG_NOTES (insn); link != NULL_RTX; link = next)
789 next = XEXP (link, 1);
790 if (XEXP (link, 0) == src)
792 *p_move_notes = link;
793 p_move_notes = &XEXP (link, 1);
797 *p_insn_notes = link;
798 p_insn_notes = &XEXP (link, 1);
802 *p_move_notes = NULL_RTX;
803 *p_insn_notes = NULL_RTX;
805 /* Is the insn the head of a basic block? If so extend it. */
806 insn_uid = INSN_UID (insn);
807 move_uid = INSN_UID (move_insn);
808 if (insn_uid < old_max_uid)
810 bb = regmove_bb_head[insn_uid];
813 BB_HEAD (BASIC_BLOCK (bb)) = move_insn;
814 regmove_bb_head[insn_uid] = -1;
818 /* Update the various register tables. */
819 dest_regno = REGNO (dest);
820 REG_N_SETS (dest_regno) ++;
821 REG_LIVE_LENGTH (dest_regno)++;
822 if (REGNO_FIRST_UID (dest_regno) == insn_uid)
823 REGNO_FIRST_UID (dest_regno) = move_uid;
825 src_regno = REGNO (src);
826 if (! find_reg_note (move_insn, REG_DEAD, src))
827 REG_LIVE_LENGTH (src_regno)++;
829 if (REGNO_FIRST_UID (src_regno) == insn_uid)
830 REGNO_FIRST_UID (src_regno) = move_uid;
832 if (REGNO_LAST_UID (src_regno) == insn_uid)
833 REGNO_LAST_UID (src_regno) = move_uid;
835 if (REGNO_LAST_NOTE_UID (src_regno) == insn_uid)
836 REGNO_LAST_NOTE_UID (src_regno) = move_uid;
841 /* Return whether REG is set in only one location, and is set to a
842 constant, but is set in a different basic block from INSN (an
843 instructions which uses REG). In this case REG is equivalent to a
844 constant, and we don't want to break that equivalence, because that
845 may increase register pressure and make reload harder. If REG is
846 set in the same basic block as INSN, we don't worry about it,
847 because we'll probably need a register anyhow (??? but what if REG
848 is used in a different basic block as well as this one?). FIRST is
849 the first insn in the function. */
852 reg_is_remote_constant_p (rtx reg, rtx insn, rtx first)
856 if (REG_N_SETS (REGNO (reg)) != 1)
859 /* Look for the set. */
860 for (p = LOG_LINKS (insn); p; p = XEXP (p, 1))
864 if (REG_NOTE_KIND (p) != 0)
866 s = single_set (XEXP (p, 0));
868 && GET_CODE (SET_DEST (s)) == REG
869 && REGNO (SET_DEST (s)) == REGNO (reg))
871 /* The register is set in the same basic block. */
876 for (p = first; p && p != insn; p = NEXT_INSN (p))
884 && GET_CODE (SET_DEST (s)) == REG
885 && REGNO (SET_DEST (s)) == REGNO (reg))
887 /* This is the instruction which sets REG. If there is a
888 REG_EQUAL note, then REG is equivalent to a constant. */
889 if (find_reg_note (p, REG_EQUAL, NULL_RTX))
898 /* INSN is adding a CONST_INT to a REG. We search backwards looking for
899 another add immediate instruction with the same source and dest registers,
900 and if we find one, we change INSN to an increment, and return 1. If
901 no changes are made, we return 0.
904 (set (reg100) (plus reg1 offset1))
906 (set (reg100) (plus reg1 offset2))
908 (set (reg100) (plus reg1 offset1))
910 (set (reg100) (plus reg100 offset2-offset1)) */
912 /* ??? What does this comment mean? */
913 /* cse disrupts preincrement / postdecrement sequences when it finds a
914 hard register as ultimate source, like the frame pointer. */
917 fixup_match_2 (rtx insn, rtx dst, rtx src, rtx offset, FILE *regmove_dump_file)
919 rtx p, dst_death = 0;
920 int length, num_calls = 0;
922 /* If SRC dies in INSN, we'd have to move the death note. This is
923 considered to be very unlikely, so we just skip the optimization
925 if (find_regno_note (insn, REG_DEAD, REGNO (src)))
928 /* Scan backward to find the first instruction that sets DST. */
930 for (length = 0, p = PREV_INSN (insn); p; p = PREV_INSN (p))
934 /* ??? We can't scan past the end of a basic block without updating
935 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
936 if (perhaps_ends_bb_p (p))
938 else if (! INSN_P (p))
941 if (find_regno_note (p, REG_DEAD, REGNO (dst)))
946 pset = single_set (p);
947 if (pset && SET_DEST (pset) == dst
948 && GET_CODE (SET_SRC (pset)) == PLUS
949 && XEXP (SET_SRC (pset), 0) == src
950 && GET_CODE (XEXP (SET_SRC (pset), 1)) == CONST_INT)
952 HOST_WIDE_INT newconst
953 = INTVAL (offset) - INTVAL (XEXP (SET_SRC (pset), 1));
954 rtx add = gen_add3_insn (dst, dst, GEN_INT (newconst));
956 if (add && validate_change (insn, &PATTERN (insn), add, 0))
958 /* Remove the death note for DST from DST_DEATH. */
961 remove_death (REGNO (dst), dst_death);
962 REG_LIVE_LENGTH (REGNO (dst)) += length;
963 REG_N_CALLS_CROSSED (REGNO (dst)) += num_calls;
966 if (regmove_dump_file)
967 fprintf (regmove_dump_file,
968 "Fixed operand of insn %d.\n",
972 for (p = PREV_INSN (insn); p; p = PREV_INSN (p))
974 if (GET_CODE (p) == CODE_LABEL
975 || GET_CODE (p) == JUMP_INSN)
979 if (reg_overlap_mentioned_p (dst, PATTERN (p)))
981 if (try_auto_increment (p, insn, 0, dst, newconst, 0))
986 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
988 if (GET_CODE (p) == CODE_LABEL
989 || GET_CODE (p) == JUMP_INSN)
993 if (reg_overlap_mentioned_p (dst, PATTERN (p)))
995 try_auto_increment (p, insn, 0, dst, newconst, 1);
1004 if (reg_set_p (dst, PATTERN (p)))
1007 /* If we have passed a call instruction, and the
1008 pseudo-reg SRC is not already live across a call,
1009 then don't perform the optimization. */
1010 /* reg_set_p is overly conservative for CALL_INSNS, thinks that all
1011 hard regs are clobbered. Thus, we only use it for src for
1013 if (GET_CODE (p) == CALL_INSN)
1018 if (REG_N_CALLS_CROSSED (REGNO (src)) == 0)
1021 if (call_used_regs [REGNO (dst)]
1022 || find_reg_fusage (p, CLOBBER, dst))
1025 else if (reg_set_p (src, PATTERN (p)))
1032 /* Main entry for the register move optimization.
1033 F is the first instruction.
1034 NREGS is one plus the highest pseudo-reg number used in the instruction.
1035 REGMOVE_DUMP_FILE is a stream for output of a trace of actions taken
1036 (or 0 if none should be output). */
1039 regmove_optimize (rtx f, int nregs, FILE *regmove_dump_file)
1041 int old_max_uid = get_max_uid ();
1046 rtx copy_src, copy_dst;
1049 /* ??? Hack. Regmove doesn't examine the CFG, and gets mightily
1050 confused by non-call exceptions ending blocks. */
1051 if (flag_non_call_exceptions)
1054 /* Find out where a potential flags register is live, and so that we
1055 can suppress some optimizations in those zones. */
1056 mark_flags_life_zones (discover_flags_reg ());
1058 regno_src_regno = xmalloc (sizeof *regno_src_regno * nregs);
1059 for (i = nregs; --i >= 0; ) regno_src_regno[i] = -1;
1061 regmove_bb_head = xmalloc (sizeof (int) * (old_max_uid + 1));
1062 for (i = old_max_uid; i >= 0; i--) regmove_bb_head[i] = -1;
1064 regmove_bb_head[INSN_UID (BB_HEAD (bb))] = bb->index;
1066 /* A forward/backward pass. Replace output operands with input operands. */
1068 for (pass = 0; pass <= 2; pass++)
1070 if (! flag_regmove && pass >= flag_expensive_optimizations)
1073 if (regmove_dump_file)
1074 fprintf (regmove_dump_file, "Starting %s pass...\n",
1075 pass ? "backward" : "forward");
1077 for (insn = pass ? get_last_insn () : f; insn;
1078 insn = pass ? PREV_INSN (insn) : NEXT_INSN (insn))
1081 int op_no, match_no;
1083 set = single_set (insn);
1087 if (flag_expensive_optimizations && ! pass
1088 && (GET_CODE (SET_SRC (set)) == SIGN_EXTEND
1089 || GET_CODE (SET_SRC (set)) == ZERO_EXTEND)
1090 && GET_CODE (XEXP (SET_SRC (set), 0)) == REG
1091 && GET_CODE (SET_DEST (set)) == REG)
1092 optimize_reg_copy_3 (insn, SET_DEST (set), SET_SRC (set));
1094 if (flag_expensive_optimizations && ! pass
1095 && GET_CODE (SET_SRC (set)) == REG
1096 && GET_CODE (SET_DEST (set)) == REG)
1098 /* If this is a register-register copy where SRC is not dead,
1099 see if we can optimize it. If this optimization succeeds,
1100 it will become a copy where SRC is dead. */
1101 if ((find_reg_note (insn, REG_DEAD, SET_SRC (set))
1102 || optimize_reg_copy_1 (insn, SET_DEST (set), SET_SRC (set)))
1103 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
1105 /* Similarly for a pseudo-pseudo copy when SRC is dead. */
1106 if (REGNO (SET_SRC (set)) >= FIRST_PSEUDO_REGISTER)
1107 optimize_reg_copy_2 (insn, SET_DEST (set), SET_SRC (set));
1108 if (regno_src_regno[REGNO (SET_DEST (set))] < 0
1109 && SET_SRC (set) != SET_DEST (set))
1111 int srcregno = REGNO (SET_SRC (set));
1112 if (regno_src_regno[srcregno] >= 0)
1113 srcregno = regno_src_regno[srcregno];
1114 regno_src_regno[REGNO (SET_DEST (set))] = srcregno;
1121 if (! find_matches (insn, &match))
1124 /* Now scan through the operands looking for a source operand
1125 which is supposed to match the destination operand.
1126 Then scan forward for an instruction which uses the dest
1128 If it dies there, then replace the dest in both operands with
1129 the source operand. */
1131 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1133 rtx src, dst, src_subreg;
1134 enum reg_class src_class, dst_class;
1136 match_no = match.with[op_no];
1138 /* Nothing to do if the two operands aren't supposed to match. */
1142 src = recog_data.operand[op_no];
1143 dst = recog_data.operand[match_no];
1145 if (GET_CODE (src) != REG)
1149 if (GET_CODE (dst) == SUBREG
1150 && GET_MODE_SIZE (GET_MODE (dst))
1151 >= GET_MODE_SIZE (GET_MODE (SUBREG_REG (dst))))
1154 = gen_rtx_SUBREG (GET_MODE (SUBREG_REG (dst)),
1155 src, SUBREG_BYTE (dst));
1156 dst = SUBREG_REG (dst);
1158 if (GET_CODE (dst) != REG
1159 || REGNO (dst) < FIRST_PSEUDO_REGISTER)
1162 if (REGNO (src) < FIRST_PSEUDO_REGISTER)
1164 if (match.commutative[op_no] < op_no)
1165 regno_src_regno[REGNO (dst)] = REGNO (src);
1169 if (REG_LIVE_LENGTH (REGNO (src)) < 0)
1172 /* op_no/src must be a read-only operand, and
1173 match_operand/dst must be a write-only operand. */
1174 if (match.use[op_no] != READ
1175 || match.use[match_no] != WRITE)
1178 if (match.early_clobber[match_no]
1179 && count_occurrences (PATTERN (insn), src, 0) > 1)
1182 /* Make sure match_operand is the destination. */
1183 if (recog_data.operand[match_no] != SET_DEST (set))
1186 /* If the operands already match, then there is nothing to do. */
1187 if (operands_match_p (src, dst))
1190 /* But in the commutative case, we might find a better match. */
1191 if (match.commutative[op_no] >= 0)
1193 rtx comm = recog_data.operand[match.commutative[op_no]];
1194 if (operands_match_p (comm, dst)
1195 && (replacement_quality (comm)
1196 >= replacement_quality (src)))
1200 src_class = reg_preferred_class (REGNO (src));
1201 dst_class = reg_preferred_class (REGNO (dst));
1202 if (! regclass_compatible_p (src_class, dst_class))
1205 if (GET_MODE (src) != GET_MODE (dst))
1208 if (fixup_match_1 (insn, set, src, src_subreg, dst, pass,
1216 /* A backward pass. Replace input operands with output operands. */
1218 if (regmove_dump_file)
1219 fprintf (regmove_dump_file, "Starting backward pass...\n");
1221 for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
1225 int op_no, match_no;
1228 if (! find_matches (insn, &match))
1231 /* Now scan through the operands looking for a destination operand
1232 which is supposed to match a source operand.
1233 Then scan backward for an instruction which sets the source
1234 operand. If safe, then replace the source operand with the
1235 dest operand in both instructions. */
1237 copy_src = NULL_RTX;
1238 copy_dst = NULL_RTX;
1239 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1241 rtx set, p, src, dst;
1242 rtx src_note, dst_note;
1244 enum reg_class src_class, dst_class;
1247 match_no = match.with[op_no];
1249 /* Nothing to do if the two operands aren't supposed to match. */
1253 dst = recog_data.operand[match_no];
1254 src = recog_data.operand[op_no];
1256 if (GET_CODE (src) != REG)
1259 if (GET_CODE (dst) != REG
1260 || REGNO (dst) < FIRST_PSEUDO_REGISTER
1261 || REG_LIVE_LENGTH (REGNO (dst)) < 0
1262 || RTX_UNCHANGING_P (dst)
1263 || GET_MODE (src) != GET_MODE (dst))
1266 /* If the operands already match, then there is nothing to do. */
1267 if (operands_match_p (src, dst))
1270 if (match.commutative[op_no] >= 0)
1272 rtx comm = recog_data.operand[match.commutative[op_no]];
1273 if (operands_match_p (comm, dst))
1277 set = single_set (insn);
1281 /* Note that single_set ignores parts of a parallel set for
1282 which one of the destinations is REG_UNUSED. We can't
1283 handle that here, since we can wind up rewriting things
1284 such that a single register is set twice within a single
1286 if (reg_set_p (src, insn))
1289 /* match_no/dst must be a write-only operand, and
1290 operand_operand/src must be a read-only operand. */
1291 if (match.use[op_no] != READ
1292 || match.use[match_no] != WRITE)
1295 if (match.early_clobber[match_no]
1296 && count_occurrences (PATTERN (insn), src, 0) > 1)
1299 /* Make sure match_no is the destination. */
1300 if (recog_data.operand[match_no] != SET_DEST (set))
1303 if (REGNO (src) < FIRST_PSEUDO_REGISTER)
1305 if (GET_CODE (SET_SRC (set)) == PLUS
1306 && GET_CODE (XEXP (SET_SRC (set), 1)) == CONST_INT
1307 && XEXP (SET_SRC (set), 0) == src
1308 && fixup_match_2 (insn, dst, src,
1309 XEXP (SET_SRC (set), 1),
1314 src_class = reg_preferred_class (REGNO (src));
1315 dst_class = reg_preferred_class (REGNO (dst));
1317 if (! (src_note = find_reg_note (insn, REG_DEAD, src)))
1319 /* We used to force the copy here like in other cases, but
1320 it produces worse code, as it eliminates no copy
1321 instructions and the copy emitted will be produced by
1322 reload anyway. On patterns with multiple alternatives,
1323 there may be better solution available.
1325 In particular this change produced slower code for numeric
1331 if (! regclass_compatible_p (src_class, dst_class))
1341 /* Can not modify an earlier insn to set dst if this insn
1342 uses an old value in the source. */
1343 if (reg_overlap_mentioned_p (dst, SET_SRC (set)))
1353 /* If src is set once in a different basic block,
1354 and is set equal to a constant, then do not use
1355 it for this optimization, as this would make it
1356 no longer equivalent to a constant. */
1358 if (reg_is_remote_constant_p (src, insn, f))
1369 if (regmove_dump_file)
1370 fprintf (regmove_dump_file,
1371 "Could fix operand %d of insn %d matching operand %d.\n",
1372 op_no, INSN_UID (insn), match_no);
1374 /* Scan backward to find the first instruction that uses
1375 the input operand. If the operand is set here, then
1376 replace it in both instructions with match_no. */
1378 for (length = 0, p = PREV_INSN (insn); p; p = PREV_INSN (p))
1382 /* ??? We can't scan past the end of a basic block without
1383 updating the register lifetime info
1384 (REG_DEAD/basic_block_live_at_start). */
1385 if (perhaps_ends_bb_p (p))
1387 else if (! INSN_P (p))
1392 /* ??? See if all of SRC is set in P. This test is much
1393 more conservative than it needs to be. */
1394 pset = single_set (p);
1395 if (pset && SET_DEST (pset) == src)
1397 /* We use validate_replace_rtx, in case there
1398 are multiple identical source operands. All of
1399 them have to be changed at the same time. */
1400 if (validate_replace_rtx (src, dst, insn))
1402 if (validate_change (p, &SET_DEST (pset),
1407 /* Change all source operands back.
1408 This modifies the dst as a side-effect. */
1409 validate_replace_rtx (dst, src, insn);
1410 /* Now make sure the dst is right. */
1411 validate_change (insn,
1412 recog_data.operand_loc[match_no],
1419 if (reg_overlap_mentioned_p (src, PATTERN (p))
1420 || reg_overlap_mentioned_p (dst, PATTERN (p)))
1423 /* If we have passed a call instruction, and the
1424 pseudo-reg DST is not already live across a call,
1425 then don't perform the optimization. */
1426 if (GET_CODE (p) == CALL_INSN)
1430 if (REG_N_CALLS_CROSSED (REGNO (dst)) == 0)
1439 /* Remove the death note for SRC from INSN. */
1440 remove_note (insn, src_note);
1441 /* Move the death note for SRC to P if it is used
1443 if (reg_overlap_mentioned_p (src, PATTERN (p)))
1445 XEXP (src_note, 1) = REG_NOTES (p);
1446 REG_NOTES (p) = src_note;
1448 /* If there is a REG_DEAD note for DST on P, then remove
1449 it, because DST is now set there. */
1450 if ((dst_note = find_reg_note (p, REG_DEAD, dst)))
1451 remove_note (p, dst_note);
1453 dstno = REGNO (dst);
1454 srcno = REGNO (src);
1456 REG_N_SETS (dstno)++;
1457 REG_N_SETS (srcno)--;
1459 REG_N_CALLS_CROSSED (dstno) += num_calls;
1460 REG_N_CALLS_CROSSED (srcno) -= num_calls;
1462 REG_LIVE_LENGTH (dstno) += length;
1463 if (REG_LIVE_LENGTH (srcno) >= 0)
1465 REG_LIVE_LENGTH (srcno) -= length;
1466 /* REG_LIVE_LENGTH is only an approximation after
1467 combine if sched is not run, so make sure that we
1468 still have a reasonable value. */
1469 if (REG_LIVE_LENGTH (srcno) < 2)
1470 REG_LIVE_LENGTH (srcno) = 2;
1473 if (regmove_dump_file)
1474 fprintf (regmove_dump_file,
1475 "Fixed operand %d of insn %d matching operand %d.\n",
1476 op_no, INSN_UID (insn), match_no);
1482 /* If we weren't able to replace any of the alternatives, try an
1483 alternative approach of copying the source to the destination. */
1484 if (!success && copy_src != NULL_RTX)
1485 copy_src_to_dest (insn, copy_src, copy_dst, old_max_uid);
1490 /* In fixup_match_1, some insns may have been inserted after basic block
1491 ends. Fix that here. */
1494 rtx end = BB_END (bb);
1496 rtx next = NEXT_INSN (new);
1497 while (next != 0 && INSN_UID (next) >= old_max_uid
1498 && (bb->next_bb == EXIT_BLOCK_PTR || BB_HEAD (bb->next_bb) != next))
1499 new = next, next = NEXT_INSN (new);
1505 free (regno_src_regno);
1506 free (regmove_bb_head);
1509 /* Returns nonzero if INSN's pattern has matching constraints for any operand.
1510 Returns 0 if INSN can't be recognized, or if the alternative can't be
1513 Initialize the info in MATCHP based on the constraints. */
1516 find_matches (rtx insn, struct match *matchp)
1518 int likely_spilled[MAX_RECOG_OPERANDS];
1520 int any_matches = 0;
1522 extract_insn (insn);
1523 if (! constrain_operands (0))
1526 /* Must initialize this before main loop, because the code for
1527 the commutative case may set matches for operands other than
1529 for (op_no = recog_data.n_operands; --op_no >= 0; )
1530 matchp->with[op_no] = matchp->commutative[op_no] = -1;
1532 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1538 p = recog_data.constraints[op_no];
1540 likely_spilled[op_no] = 0;
1541 matchp->use[op_no] = READ;
1542 matchp->early_clobber[op_no] = 0;
1544 matchp->use[op_no] = WRITE;
1546 matchp->use[op_no] = READWRITE;
1548 for (;*p && i < which_alternative; p++)
1552 while ((c = *p) != '\0' && c != ',')
1561 matchp->early_clobber[op_no] = 1;
1564 matchp->commutative[op_no] = op_no + 1;
1565 matchp->commutative[op_no + 1] = op_no;
1568 case '0': case '1': case '2': case '3': case '4':
1569 case '5': case '6': case '7': case '8': case '9':
1572 unsigned long match_ul = strtoul (p, &end, 10);
1573 int match = match_ul;
1577 if (match < op_no && likely_spilled[match])
1579 matchp->with[op_no] = match;
1581 if (matchp->commutative[op_no] >= 0)
1582 matchp->with[matchp->commutative[op_no]] = match;
1586 case 'a': case 'b': case 'c': case 'd': case 'e': case 'f': case 'h':
1587 case 'j': case 'k': case 'l': case 'p': case 'q': case 't': case 'u':
1588 case 'v': case 'w': case 'x': case 'y': case 'z': case 'A': case 'B':
1589 case 'C': case 'D': case 'W': case 'Y': case 'Z':
1590 if (CLASS_LIKELY_SPILLED_P (REG_CLASS_FROM_CONSTRAINT ((unsigned char) c, p) ))
1591 likely_spilled[op_no] = 1;
1594 p += CONSTRAINT_LEN (c, p);
1600 /* Try to replace all occurrences of DST_REG with SRC in LOC, that is
1601 assumed to be in INSN. */
1604 replace_in_call_usage (rtx *loc, unsigned int dst_reg, rtx src, rtx insn)
1614 code = GET_CODE (x);
1617 if (REGNO (x) != dst_reg)
1620 validate_change (insn, loc, src, 1);
1625 /* Process each of our operands recursively. */
1626 fmt = GET_RTX_FORMAT (code);
1627 for (i = 0; i < GET_RTX_LENGTH (code); i++, fmt++)
1629 replace_in_call_usage (&XEXP (x, i), dst_reg, src, insn);
1630 else if (*fmt == 'E')
1631 for (j = 0; j < XVECLEN (x, i); j++)
1632 replace_in_call_usage (& XVECEXP (x, i, j), dst_reg, src, insn);
1635 /* Try to replace output operand DST in SET, with input operand SRC. SET is
1636 the only set in INSN. INSN has just been recognized and constrained.
1637 SRC is operand number OPERAND_NUMBER in INSN.
1638 DST is operand number MATCH_NUMBER in INSN.
1639 If BACKWARD is nonzero, we have been called in a backward pass.
1640 Return nonzero for success. */
1643 fixup_match_1 (rtx insn, rtx set, rtx src, rtx src_subreg, rtx dst,
1644 int backward, int operand_number, int match_number,
1645 FILE *regmove_dump_file)
1648 rtx post_inc = 0, post_inc_set = 0, search_end = 0;
1650 int num_calls = 0, s_num_calls = 0;
1651 enum rtx_code code = NOTE;
1652 HOST_WIDE_INT insn_const = 0, newconst = 0;
1653 rtx overlap = 0; /* need to move insn ? */
1654 rtx src_note = find_reg_note (insn, REG_DEAD, src), dst_note = NULL_RTX;
1655 int length, s_length;
1657 /* If SRC is marked as unchanging, we may not change it.
1658 ??? Maybe we could get better code by removing the unchanging bit
1659 instead, and changing it back if we don't succeed? */
1660 if (RTX_UNCHANGING_P (src))
1665 /* Look for (set (regX) (op regA constX))
1666 (set (regY) (op regA constY))
1668 (set (regA) (op regA constX)).
1669 (set (regY) (op regA constY-constX)).
1670 This works for add and shift operations, if
1671 regA is dead after or set by the second insn. */
1673 code = GET_CODE (SET_SRC (set));
1674 if ((code == PLUS || code == LSHIFTRT
1675 || code == ASHIFT || code == ASHIFTRT)
1676 && XEXP (SET_SRC (set), 0) == src
1677 && GET_CODE (XEXP (SET_SRC (set), 1)) == CONST_INT)
1678 insn_const = INTVAL (XEXP (SET_SRC (set), 1));
1679 else if (! stable_and_no_regs_but_for_p (SET_SRC (set), src, dst))
1682 /* We might find a src_note while scanning. */
1686 if (regmove_dump_file)
1687 fprintf (regmove_dump_file,
1688 "Could fix operand %d of insn %d matching operand %d.\n",
1689 operand_number, INSN_UID (insn), match_number);
1691 /* If SRC is equivalent to a constant set in a different basic block,
1692 then do not use it for this optimization. We want the equivalence
1693 so that if we have to reload this register, we can reload the
1694 constant, rather than extending the lifespan of the register. */
1695 if (reg_is_remote_constant_p (src, insn, get_insns ()))
1698 /* Scan forward to find the next instruction that
1699 uses the output operand. If the operand dies here,
1700 then replace it in both instructions with
1703 for (length = s_length = 0, p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
1705 if (GET_CODE (p) == CALL_INSN)
1706 replace_in_call_usage (& CALL_INSN_FUNCTION_USAGE (p),
1707 REGNO (dst), src, p);
1709 /* ??? We can't scan past the end of a basic block without updating
1710 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
1711 if (perhaps_ends_bb_p (p))
1713 else if (! INSN_P (p))
1720 if (reg_set_p (src, p) || reg_set_p (dst, p)
1721 || (GET_CODE (PATTERN (p)) == USE
1722 && reg_overlap_mentioned_p (src, XEXP (PATTERN (p), 0))))
1725 /* See if all of DST dies in P. This test is
1726 slightly more conservative than it needs to be. */
1727 if ((dst_note = find_regno_note (p, REG_DEAD, REGNO (dst)))
1728 && (GET_MODE (XEXP (dst_note, 0)) == GET_MODE (dst)))
1730 /* If we would be moving INSN, check that we won't move it
1731 into the shadow of a live a live flags register. */
1732 /* ??? We only try to move it in front of P, although
1733 we could move it anywhere between OVERLAP and P. */
1734 if (overlap && GET_MODE (PREV_INSN (p)) != VOIDmode)
1740 rtx set2 = NULL_RTX;
1742 /* If an optimization is done, the value of SRC while P
1743 is executed will be changed. Check that this is OK. */
1744 if (reg_overlap_mentioned_p (src, PATTERN (p)))
1746 for (q = p; q; q = NEXT_INSN (q))
1748 /* ??? We can't scan past the end of a basic block without
1749 updating the register lifetime info
1750 (REG_DEAD/basic_block_live_at_start). */
1751 if (perhaps_ends_bb_p (q))
1756 else if (! INSN_P (q))
1758 else if (reg_overlap_mentioned_p (src, PATTERN (q))
1759 || reg_set_p (src, q))
1763 set2 = single_set (q);
1764 if (! q || ! set2 || GET_CODE (SET_SRC (set2)) != code
1765 || XEXP (SET_SRC (set2), 0) != src
1766 || GET_CODE (XEXP (SET_SRC (set2), 1)) != CONST_INT
1767 || (SET_DEST (set2) != src
1768 && ! find_reg_note (q, REG_DEAD, src)))
1770 /* If this is a PLUS, we can still save a register by doing
1773 src -= insn_const; .
1774 This also gives opportunities for subsequent
1775 optimizations in the backward pass, so do it there. */
1776 if (code == PLUS && backward
1777 /* Don't do this if we can likely tie DST to SET_DEST
1778 of P later; we can't do this tying here if we got a
1780 && ! (dst_note && ! REG_N_CALLS_CROSSED (REGNO (dst))
1782 && GET_CODE (SET_DEST (single_set (p))) == REG
1783 && (REGNO (SET_DEST (single_set (p)))
1784 < FIRST_PSEUDO_REGISTER))
1785 /* We may only emit an insn directly after P if we
1786 are not in the shadow of a live flags register. */
1787 && GET_MODE (p) == VOIDmode)
1792 newconst = -insn_const;
1800 newconst = INTVAL (XEXP (SET_SRC (set2), 1)) - insn_const;
1801 /* Reject out of range shifts. */
1804 || ((unsigned HOST_WIDE_INT) newconst
1805 >= (GET_MODE_BITSIZE (GET_MODE
1806 (SET_SRC (set2)))))))
1811 if (SET_DEST (set2) != src)
1812 post_inc_set = set2;
1815 /* We use 1 as last argument to validate_change so that all
1816 changes are accepted or rejected together by apply_change_group
1817 when it is called by validate_replace_rtx . */
1818 validate_change (q, &XEXP (SET_SRC (set2), 1),
1819 GEN_INT (newconst), 1);
1821 validate_change (insn, recog_data.operand_loc[match_number], src, 1);
1822 if (validate_replace_rtx (dst, src_subreg, p))
1827 if (reg_overlap_mentioned_p (dst, PATTERN (p)))
1829 if (! src_note && reg_overlap_mentioned_p (src, PATTERN (p)))
1831 /* INSN was already checked to be movable wrt. the registers that it
1832 sets / uses when we found no REG_DEAD note for src on it, but it
1833 still might clobber the flags register. We'll have to check that
1834 we won't insert it into the shadow of a live flags register when
1835 we finally know where we are to move it. */
1837 src_note = find_reg_note (p, REG_DEAD, src);
1840 /* If we have passed a call instruction, and the pseudo-reg SRC is not
1841 already live across a call, then don't perform the optimization. */
1842 if (GET_CODE (p) == CALL_INSN)
1844 if (REG_N_CALLS_CROSSED (REGNO (src)) == 0)
1858 /* Remove the death note for DST from P. */
1859 remove_note (p, dst_note);
1862 post_inc = emit_insn_after (copy_rtx (PATTERN (insn)), p);
1863 if ((HAVE_PRE_INCREMENT || HAVE_PRE_DECREMENT)
1865 && try_auto_increment (search_end, post_inc, 0, src, newconst, 1))
1867 validate_change (insn, &XEXP (SET_SRC (set), 1), GEN_INT (insn_const), 0);
1868 REG_N_SETS (REGNO (src))++;
1869 REG_LIVE_LENGTH (REGNO (src))++;
1873 /* The lifetime of src and dest overlap,
1874 but we can change this by moving insn. */
1875 rtx pat = PATTERN (insn);
1877 remove_note (overlap, src_note);
1878 if ((HAVE_POST_INCREMENT || HAVE_POST_DECREMENT)
1880 && try_auto_increment (overlap, insn, 0, src, insn_const, 0))
1884 rtx notes = REG_NOTES (insn);
1886 emit_insn_after_with_line_notes (pat, PREV_INSN (p), insn);
1888 /* emit_insn_after_with_line_notes has no
1889 return value, so search for the new insn. */
1891 while (! INSN_P (insn) || PATTERN (insn) != pat)
1892 insn = PREV_INSN (insn);
1894 REG_NOTES (insn) = notes;
1897 /* Sometimes we'd generate src = const; src += n;
1898 if so, replace the instruction that set src
1899 in the first place. */
1901 if (! overlap && (code == PLUS || code == MINUS))
1903 rtx note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
1904 rtx q, set2 = NULL_RTX;
1905 int num_calls2 = 0, s_length2 = 0;
1907 if (note && CONSTANT_P (XEXP (note, 0)))
1909 for (q = PREV_INSN (insn); q; q = PREV_INSN (q))
1911 /* ??? We can't scan past the end of a basic block without
1912 updating the register lifetime info
1913 (REG_DEAD/basic_block_live_at_start). */
1914 if (perhaps_ends_bb_p (q))
1919 else if (! INSN_P (q))
1923 if (reg_set_p (src, q))
1925 set2 = single_set (q);
1928 if (reg_overlap_mentioned_p (src, PATTERN (q)))
1933 if (GET_CODE (p) == CALL_INSN)
1936 if (q && set2 && SET_DEST (set2) == src && CONSTANT_P (SET_SRC (set2))
1937 && validate_change (insn, &SET_SRC (set), XEXP (note, 0), 0))
1940 REG_N_SETS (REGNO (src))--;
1941 REG_N_CALLS_CROSSED (REGNO (src)) -= num_calls2;
1942 REG_LIVE_LENGTH (REGNO (src)) -= s_length2;
1948 if ((HAVE_PRE_INCREMENT || HAVE_PRE_DECREMENT)
1949 && (code == PLUS || code == MINUS) && insn_const
1950 && try_auto_increment (p, insn, 0, src, insn_const, 1))
1952 else if ((HAVE_POST_INCREMENT || HAVE_POST_DECREMENT)
1954 && try_auto_increment (p, post_inc, post_inc_set, src, newconst, 0))
1956 /* If post_inc still prevails, try to find an
1957 insn where it can be used as a pre-in/decrement.
1958 If code is MINUS, this was already tried. */
1959 if (post_inc && code == PLUS
1960 /* Check that newconst is likely to be usable
1961 in a pre-in/decrement before starting the search. */
1962 && ((HAVE_PRE_INCREMENT && newconst > 0 && newconst <= MOVE_MAX)
1963 || (HAVE_PRE_DECREMENT && newconst < 0 && newconst >= -MOVE_MAX))
1964 && exact_log2 (newconst))
1968 inc_dest = post_inc_set ? SET_DEST (post_inc_set) : src;
1969 for (q = post_inc; (q = NEXT_INSN (q)); )
1971 /* ??? We can't scan past the end of a basic block without updating
1972 the register lifetime info
1973 (REG_DEAD/basic_block_live_at_start). */
1974 if (perhaps_ends_bb_p (q))
1976 else if (! INSN_P (q))
1978 else if (src != inc_dest
1979 && (reg_overlap_mentioned_p (src, PATTERN (q))
1980 || reg_set_p (src, q)))
1982 else if (reg_set_p (inc_dest, q))
1984 else if (reg_overlap_mentioned_p (inc_dest, PATTERN (q)))
1986 try_auto_increment (q, post_inc,
1987 post_inc_set, inc_dest, newconst, 1);
1993 /* Move the death note for DST to INSN if it is used
1995 if (reg_overlap_mentioned_p (dst, PATTERN (insn)))
1997 XEXP (dst_note, 1) = REG_NOTES (insn);
1998 REG_NOTES (insn) = dst_note;
2003 /* Move the death note for SRC from INSN to P. */
2005 remove_note (insn, src_note);
2006 XEXP (src_note, 1) = REG_NOTES (p);
2007 REG_NOTES (p) = src_note;
2009 REG_N_CALLS_CROSSED (REGNO (src)) += s_num_calls;
2012 REG_N_SETS (REGNO (src))++;
2013 REG_N_SETS (REGNO (dst))--;
2015 REG_N_CALLS_CROSSED (REGNO (dst)) -= num_calls;
2017 REG_LIVE_LENGTH (REGNO (src)) += s_length;
2018 if (REG_LIVE_LENGTH (REGNO (dst)) >= 0)
2020 REG_LIVE_LENGTH (REGNO (dst)) -= length;
2021 /* REG_LIVE_LENGTH is only an approximation after
2022 combine if sched is not run, so make sure that we
2023 still have a reasonable value. */
2024 if (REG_LIVE_LENGTH (REGNO (dst)) < 2)
2025 REG_LIVE_LENGTH (REGNO (dst)) = 2;
2027 if (regmove_dump_file)
2028 fprintf (regmove_dump_file,
2029 "Fixed operand %d of insn %d matching operand %d.\n",
2030 operand_number, INSN_UID (insn), match_number);
2035 /* Return nonzero if X is stable and mentions no registers but for
2036 mentioning SRC or mentioning / changing DST . If in doubt, presume
2038 The rationale is that we want to check if we can move an insn easily
2039 while just paying attention to SRC and DST. A register is considered
2040 stable if it has the RTX_UNCHANGING_P bit set, but that would still
2041 leave the burden to update REG_DEAD / REG_UNUSED notes, so we don't
2042 want any registers but SRC and DST. */
2044 stable_and_no_regs_but_for_p (rtx x, rtx src, rtx dst)
2046 RTX_CODE code = GET_CODE (x);
2047 switch (GET_RTX_CLASS (code))
2049 case '<': case '1': case 'c': case '2': case 'b': case '3':
2052 const char *fmt = GET_RTX_FORMAT (code);
2053 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2055 && ! stable_and_no_regs_but_for_p (XEXP (x, i), src, dst))
2061 return x == src || x == dst;
2062 /* If this is a MEM, look inside - there might be a register hidden in
2063 the address of an unchanging MEM. */
2065 && ! stable_and_no_regs_but_for_p (XEXP (x, 0), src, dst))
2069 return ! rtx_unstable_p (x);
2073 /* Track stack adjustments and stack memory references. Attempt to
2074 reduce the number of stack adjustments by back-propagating across
2075 the memory references.
2077 This is intended primarily for use with targets that do not define
2078 ACCUMULATE_OUTGOING_ARGS. It is of significantly more value to
2079 targets that define PREFERRED_STACK_BOUNDARY more aligned than
2080 STACK_BOUNDARY (e.g. x86), or if not all registers can be pushed
2081 (e.g. x86 fp regs) which would ordinarily have to be implemented
2082 as a sub/mov pair due to restrictions in calls.c.
2084 Propagation stops when any of the insns that need adjusting are
2085 (a) no longer valid because we've exceeded their range, (b) a
2086 non-trivial push instruction, or (c) a call instruction.
2088 Restriction B is based on the assumption that push instructions
2089 are smaller or faster. If a port really wants to remove all
2090 pushes, it should have defined ACCUMULATE_OUTGOING_ARGS. The
2091 one exception that is made is for an add immediately followed
2094 /* This structure records stack memory references between stack adjusting
2099 HOST_WIDE_INT sp_offset;
2101 struct csa_memlist *next;
2104 static int stack_memref_p (rtx);
2105 static rtx single_set_for_csa (rtx);
2106 static void free_csa_memlist (struct csa_memlist *);
2107 static struct csa_memlist *record_one_stack_memref (rtx, rtx *,
2108 struct csa_memlist *);
2109 static int try_apply_stack_adjustment (rtx, struct csa_memlist *,
2110 HOST_WIDE_INT, HOST_WIDE_INT);
2111 static void combine_stack_adjustments_for_block (basic_block);
2112 static int record_stack_memrefs (rtx *, void *);
2115 /* Main entry point for stack adjustment combination. */
2118 combine_stack_adjustments (void)
2123 combine_stack_adjustments_for_block (bb);
2126 /* Recognize a MEM of the form (sp) or (plus sp const). */
2129 stack_memref_p (rtx x)
2131 if (GET_CODE (x) != MEM)
2135 if (x == stack_pointer_rtx)
2137 if (GET_CODE (x) == PLUS
2138 && XEXP (x, 0) == stack_pointer_rtx
2139 && GET_CODE (XEXP (x, 1)) == CONST_INT)
2145 /* Recognize either normal single_set or the hack in i386.md for
2146 tying fp and sp adjustments. */
2149 single_set_for_csa (rtx insn)
2152 rtx tmp = single_set (insn);
2156 if (GET_CODE (insn) != INSN
2157 || GET_CODE (PATTERN (insn)) != PARALLEL)
2160 tmp = PATTERN (insn);
2161 if (GET_CODE (XVECEXP (tmp, 0, 0)) != SET)
2164 for (i = 1; i < XVECLEN (tmp, 0); ++i)
2166 rtx this = XVECEXP (tmp, 0, i);
2168 /* The special case is allowing a no-op set. */
2169 if (GET_CODE (this) == SET
2170 && SET_SRC (this) == SET_DEST (this))
2172 else if (GET_CODE (this) != CLOBBER
2173 && GET_CODE (this) != USE)
2177 return XVECEXP (tmp, 0, 0);
2180 /* Free the list of csa_memlist nodes. */
2183 free_csa_memlist (struct csa_memlist *memlist)
2185 struct csa_memlist *next;
2186 for (; memlist ; memlist = next)
2188 next = memlist->next;
2193 /* Create a new csa_memlist node from the given memory reference.
2194 It is already known that the memory is stack_memref_p. */
2196 static struct csa_memlist *
2197 record_one_stack_memref (rtx insn, rtx *mem, struct csa_memlist *next_memlist)
2199 struct csa_memlist *ml;
2201 ml = xmalloc (sizeof (*ml));
2203 if (XEXP (*mem, 0) == stack_pointer_rtx)
2206 ml->sp_offset = INTVAL (XEXP (XEXP (*mem, 0), 1));
2210 ml->next = next_memlist;
2215 /* Attempt to apply ADJUST to the stack adjusting insn INSN, as well
2216 as each of the memories in MEMLIST. Return true on success. */
2219 try_apply_stack_adjustment (rtx insn, struct csa_memlist *memlist, HOST_WIDE_INT new_adjust,
2220 HOST_WIDE_INT delta)
2222 struct csa_memlist *ml;
2225 set = single_set_for_csa (insn);
2226 validate_change (insn, &XEXP (SET_SRC (set), 1), GEN_INT (new_adjust), 1);
2228 for (ml = memlist; ml ; ml = ml->next)
2231 replace_equiv_address_nv (*ml->mem,
2232 plus_constant (stack_pointer_rtx,
2233 ml->sp_offset - delta)), 1);
2235 if (apply_change_group ())
2237 /* Succeeded. Update our knowledge of the memory references. */
2238 for (ml = memlist; ml ; ml = ml->next)
2239 ml->sp_offset -= delta;
2247 /* Called via for_each_rtx and used to record all stack memory references in
2248 the insn and discard all other stack pointer references. */
2249 struct record_stack_memrefs_data
2252 struct csa_memlist *memlist;
2256 record_stack_memrefs (rtx *xp, void *data)
2259 struct record_stack_memrefs_data *d =
2260 (struct record_stack_memrefs_data *) data;
2263 switch (GET_CODE (x))
2266 if (!reg_mentioned_p (stack_pointer_rtx, x))
2268 /* We are not able to handle correctly all possible memrefs containing
2269 stack pointer, so this check is necessary. */
2270 if (stack_memref_p (x))
2272 d->memlist = record_one_stack_memref (d->insn, xp, d->memlist);
2277 /* ??? We want be able to handle non-memory stack pointer
2278 references later. For now just discard all insns referring to
2279 stack pointer outside mem expressions. We would probably
2280 want to teach validate_replace to simplify expressions first.
2282 We can't just compare with STACK_POINTER_RTX because the
2283 reference to the stack pointer might be in some other mode.
2284 In particular, an explicit clobber in an asm statement will
2285 result in a QImode clobber. */
2286 if (REGNO (x) == STACK_POINTER_REGNUM)
2295 /* Subroutine of combine_stack_adjustments, called for each basic block. */
2298 combine_stack_adjustments_for_block (basic_block bb)
2300 HOST_WIDE_INT last_sp_adjust = 0;
2301 rtx last_sp_set = NULL_RTX;
2302 struct csa_memlist *memlist = NULL;
2303 rtx insn, next, set;
2304 struct record_stack_memrefs_data data;
2305 bool end_of_block = false;
2307 for (insn = BB_HEAD (bb); !end_of_block ; insn = next)
2309 end_of_block = insn == BB_END (bb);
2310 next = NEXT_INSN (insn);
2312 if (! INSN_P (insn))
2315 set = single_set_for_csa (insn);
2318 rtx dest = SET_DEST (set);
2319 rtx src = SET_SRC (set);
2321 /* Find constant additions to the stack pointer. */
2322 if (dest == stack_pointer_rtx
2323 && GET_CODE (src) == PLUS
2324 && XEXP (src, 0) == stack_pointer_rtx
2325 && GET_CODE (XEXP (src, 1)) == CONST_INT)
2327 HOST_WIDE_INT this_adjust = INTVAL (XEXP (src, 1));
2329 /* If we've not seen an adjustment previously, record
2330 it now and continue. */
2334 last_sp_adjust = this_adjust;
2338 /* If not all recorded memrefs can be adjusted, or the
2339 adjustment is now too large for a constant addition,
2340 we cannot merge the two stack adjustments.
2342 Also we need to be careful to not move stack pointer
2343 such that we create stack accesses outside the allocated
2344 area. We can combine an allocation into the first insn,
2345 or a deallocation into the second insn. We can not
2346 combine an allocation followed by a deallocation.
2348 The only somewhat frequent occurrence of the later is when
2349 a function allocates a stack frame but does not use it.
2350 For this case, we would need to analyze rtl stream to be
2351 sure that allocated area is really unused. This means not
2352 only checking the memory references, but also all registers
2353 or global memory references possibly containing a stack
2356 Perhaps the best way to address this problem is to teach
2357 gcc not to allocate stack for objects never used. */
2359 /* Combine an allocation into the first instruction. */
2360 if (STACK_GROWS_DOWNWARD ? this_adjust <= 0 : this_adjust >= 0)
2362 if (try_apply_stack_adjustment (last_sp_set, memlist,
2363 last_sp_adjust + this_adjust,
2368 last_sp_adjust += this_adjust;
2373 /* Otherwise we have a deallocation. Do not combine with
2374 a previous allocation. Combine into the second insn. */
2375 else if (STACK_GROWS_DOWNWARD
2376 ? last_sp_adjust >= 0 : last_sp_adjust <= 0)
2378 if (try_apply_stack_adjustment (insn, memlist,
2379 last_sp_adjust + this_adjust,
2383 delete_insn (last_sp_set);
2385 last_sp_adjust += this_adjust;
2386 free_csa_memlist (memlist);
2392 /* Combination failed. Restart processing from here. If
2393 deallocation+allocation conspired to cancel, we can
2394 delete the old deallocation insn. */
2395 if (last_sp_set && last_sp_adjust == 0)
2397 free_csa_memlist (memlist);
2400 last_sp_adjust = this_adjust;
2404 /* Find a predecrement of exactly the previous adjustment and
2405 turn it into a direct store. Obviously we can't do this if
2406 there were any intervening uses of the stack pointer. */
2408 && GET_CODE (dest) == MEM
2409 && ((GET_CODE (XEXP (dest, 0)) == PRE_DEC
2411 == (HOST_WIDE_INT) GET_MODE_SIZE (GET_MODE (dest))))
2412 || (GET_CODE (XEXP (dest, 0)) == PRE_MODIFY
2413 && GET_CODE (XEXP (XEXP (dest, 0), 1)) == PLUS
2414 && XEXP (XEXP (XEXP (dest, 0), 1), 0) == stack_pointer_rtx
2415 && (GET_CODE (XEXP (XEXP (XEXP (dest, 0), 1), 1))
2417 && (INTVAL (XEXP (XEXP (XEXP (dest, 0), 1), 1))
2418 == -last_sp_adjust)))
2419 && XEXP (XEXP (dest, 0), 0) == stack_pointer_rtx
2420 && ! reg_mentioned_p (stack_pointer_rtx, src)
2421 && memory_address_p (GET_MODE (dest), stack_pointer_rtx)
2422 && validate_change (insn, &SET_DEST (set),
2423 replace_equiv_address (dest,
2427 delete_insn (last_sp_set);
2428 free_csa_memlist (memlist);
2430 last_sp_set = NULL_RTX;
2437 data.memlist = memlist;
2438 if (GET_CODE (insn) != CALL_INSN && last_sp_set
2439 && !for_each_rtx (&PATTERN (insn), record_stack_memrefs, &data))
2441 memlist = data.memlist;
2444 memlist = data.memlist;
2446 /* Otherwise, we were not able to process the instruction.
2447 Do not continue collecting data across such a one. */
2449 && (GET_CODE (insn) == CALL_INSN
2450 || reg_mentioned_p (stack_pointer_rtx, PATTERN (insn))))
2452 if (last_sp_set && last_sp_adjust == 0)
2453 delete_insn (last_sp_set);
2454 free_csa_memlist (memlist);
2456 last_sp_set = NULL_RTX;
2461 if (last_sp_set && last_sp_adjust == 0)
2462 delete_insn (last_sp_set);
projects / dragonfly.git / blob