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, const2_rtx);
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 && REG_P (SUBREG_REG (tmp))
192 && REGNO (SUBREG_REG (tmp)) < FIRST_PSEUDO_REGISTER)
194 found = (REG_P (tmp) && 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 its 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. */
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 hard registers used by a call. */
435 || (CALL_P (p) && sregno < FIRST_PSEUDO_REGISTER
436 && find_reg_fusage (p, USE, src))
437 /* Don't change a USE of a register. */
438 || (GET_CODE (PATTERN (p)) == USE
439 && reg_overlap_mentioned_p (src, XEXP (PATTERN (p), 0))))
442 /* See if all of SRC dies in P. This test is slightly more
443 conservative than it needs to be. */
444 if ((note = find_regno_note (p, REG_DEAD, sregno)) != 0
445 && GET_MODE (XEXP (note, 0)) == GET_MODE (src))
453 /* We can do the optimization. Scan forward from INSN again,
454 replacing regs as we go. Set FAILED if a replacement can't
455 be done. In that case, we can't move the death note for SRC.
456 This should be rare. */
458 /* Set to stop at next insn. */
459 for (q = next_real_insn (insn);
460 q != next_real_insn (p);
461 q = next_real_insn (q))
463 if (reg_overlap_mentioned_p (src, PATTERN (q)))
465 /* If SRC is a hard register, we might miss some
466 overlapping registers with validate_replace_rtx,
467 so we would have to undo it. We can't if DEST is
468 present in the insn, so fail in that combination
470 if (sregno < FIRST_PSEUDO_REGISTER
471 && reg_mentioned_p (dest, PATTERN (q)))
474 /* Replace all uses and make sure that the register
475 isn't still present. */
476 else if (validate_replace_rtx (src, dest, q)
477 && (sregno >= FIRST_PSEUDO_REGISTER
478 || ! reg_overlap_mentioned_p (src,
483 validate_replace_rtx (dest, src, q);
488 /* For SREGNO, count the total number of insns scanned.
489 For DREGNO, count the total number of insns scanned after
490 passing the death note for DREGNO. */
495 /* If the insn in which SRC dies is a CALL_INSN, don't count it
496 as a call that has been crossed. Otherwise, count it. */
497 if (q != p && CALL_P (q))
499 /* Similarly, total calls for SREGNO, total calls beyond
500 the death note for DREGNO. */
506 /* If DEST dies here, remove the death note and save it for
507 later. Make sure ALL of DEST dies here; again, this is
508 overly conservative. */
510 && (dest_death = find_regno_note (q, REG_DEAD, dregno)) != 0)
512 if (GET_MODE (XEXP (dest_death, 0)) != GET_MODE (dest))
513 failed = 1, dest_death = 0;
515 remove_note (q, dest_death);
521 /* These counters need to be updated if and only if we are
522 going to move the REG_DEAD note. */
523 if (sregno >= FIRST_PSEUDO_REGISTER)
525 if (REG_LIVE_LENGTH (sregno) >= 0)
527 REG_LIVE_LENGTH (sregno) -= s_length;
528 /* REG_LIVE_LENGTH is only an approximation after
529 combine if sched is not run, so make sure that we
530 still have a reasonable value. */
531 if (REG_LIVE_LENGTH (sregno) < 2)
532 REG_LIVE_LENGTH (sregno) = 2;
535 REG_N_CALLS_CROSSED (sregno) -= s_n_calls;
538 /* Move death note of SRC from P to INSN. */
539 remove_note (p, note);
540 XEXP (note, 1) = REG_NOTES (insn);
541 REG_NOTES (insn) = note;
544 /* DEST is also dead if INSN has a REG_UNUSED note for DEST. */
546 && (dest_death = find_regno_note (insn, REG_UNUSED, dregno)))
548 PUT_REG_NOTE_KIND (dest_death, REG_DEAD);
549 remove_note (insn, dest_death);
552 /* Put death note of DEST on P if we saw it die. */
555 XEXP (dest_death, 1) = REG_NOTES (p);
556 REG_NOTES (p) = dest_death;
558 if (dregno >= FIRST_PSEUDO_REGISTER)
560 /* If and only if we are moving the death note for DREGNO,
561 then we need to update its counters. */
562 if (REG_LIVE_LENGTH (dregno) >= 0)
563 REG_LIVE_LENGTH (dregno) += d_length;
564 REG_N_CALLS_CROSSED (dregno) += d_n_calls;
571 /* If SRC is a hard register which is set or killed in some other
572 way, we can't do this optimization. */
573 else if (sregno < FIRST_PSEUDO_REGISTER
574 && dead_or_set_p (p, src))
580 /* INSN is a copy of SRC to DEST, in which SRC dies. See if we now have
581 a sequence of insns that modify DEST followed by an insn that sets
582 SRC to DEST in which DEST dies, with no prior modification of DEST.
583 (There is no need to check if the insns in between actually modify
584 DEST. We should not have cases where DEST is not modified, but
585 the optimization is safe if no such modification is detected.)
586 In that case, we can replace all uses of DEST, starting with INSN and
587 ending with the set of SRC to DEST, with SRC. We do not do this
588 optimization if a CALL_INSN is crossed unless SRC already crosses a
589 call or if DEST dies before the copy back to SRC.
591 It is assumed that DEST and SRC are pseudos; it is too complicated to do
592 this for hard registers since the substitutions we may make might fail. */
595 optimize_reg_copy_2 (rtx insn, rtx dest, rtx src)
599 int sregno = REGNO (src);
600 int dregno = REGNO (dest);
602 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
604 /* ??? We can't scan past the end of a basic block without updating
605 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
606 if (perhaps_ends_bb_p (p))
608 else if (! INSN_P (p))
611 set = single_set (p);
612 if (set && SET_SRC (set) == dest && SET_DEST (set) == src
613 && find_reg_note (p, REG_DEAD, dest))
615 /* We can do the optimization. Scan forward from INSN again,
616 replacing regs as we go. */
618 /* Set to stop at next insn. */
619 for (q = insn; q != NEXT_INSN (p); q = NEXT_INSN (q))
622 if (reg_mentioned_p (dest, PATTERN (q)))
623 PATTERN (q) = replace_rtx (PATTERN (q), dest, src);
628 REG_N_CALLS_CROSSED (dregno)--;
629 REG_N_CALLS_CROSSED (sregno)++;
633 remove_note (p, find_reg_note (p, REG_DEAD, dest));
634 REG_N_DEATHS (dregno)--;
635 remove_note (insn, find_reg_note (insn, REG_DEAD, src));
636 REG_N_DEATHS (sregno)--;
640 if (reg_set_p (src, p)
641 || find_reg_note (p, REG_DEAD, dest)
642 || (CALL_P (p) && REG_N_CALLS_CROSSED (sregno) == 0))
646 /* INSN is a ZERO_EXTEND or SIGN_EXTEND of SRC to DEST.
647 Look if SRC dies there, and if it is only set once, by loading
648 it from memory. If so, try to incorporate the zero/sign extension
649 into the memory read, change SRC to the mode of DEST, and alter
650 the remaining accesses to use the appropriate SUBREG. This allows
651 SRC and DEST to be tied later. */
653 optimize_reg_copy_3 (rtx insn, rtx dest, rtx src)
655 rtx src_reg = XEXP (src, 0);
656 int src_no = REGNO (src_reg);
657 int dst_no = REGNO (dest);
659 enum machine_mode old_mode;
661 if (src_no < FIRST_PSEUDO_REGISTER
662 || dst_no < FIRST_PSEUDO_REGISTER
663 || ! find_reg_note (insn, REG_DEAD, src_reg)
664 || REG_N_DEATHS (src_no) != 1
665 || REG_N_SETS (src_no) != 1)
667 for (p = PREV_INSN (insn); p && ! reg_set_p (src_reg, p); p = PREV_INSN (p))
668 /* ??? We can't scan past the end of a basic block without updating
669 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
670 if (perhaps_ends_bb_p (p))
676 if (! (set = single_set (p))
677 || !MEM_P (SET_SRC (set))
678 /* If there's a REG_EQUIV note, this must be an insn that loads an
679 argument. Prefer keeping the note over doing this optimization. */
680 || find_reg_note (p, REG_EQUIV, NULL_RTX)
681 || SET_DEST (set) != src_reg)
684 /* Be conservative: although this optimization is also valid for
685 volatile memory references, that could cause trouble in later passes. */
686 if (MEM_VOLATILE_P (SET_SRC (set)))
689 /* Do not use a SUBREG to truncate from one mode to another if truncation
691 if (GET_MODE_BITSIZE (GET_MODE (src_reg)) <= GET_MODE_BITSIZE (GET_MODE (src))
692 && !TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (GET_MODE (src)),
693 GET_MODE_BITSIZE (GET_MODE (src_reg))))
696 old_mode = GET_MODE (src_reg);
697 PUT_MODE (src_reg, GET_MODE (src));
698 XEXP (src, 0) = SET_SRC (set);
700 /* Include this change in the group so that it's easily undone if
701 one of the changes in the group is invalid. */
702 validate_change (p, &SET_SRC (set), src, 1);
704 /* Now walk forward making additional replacements. We want to be able
705 to undo all the changes if a later substitution fails. */
706 subreg = gen_lowpart_SUBREG (old_mode, src_reg);
707 while (p = NEXT_INSN (p), p != insn)
712 /* Make a tentative change. */
713 validate_replace_rtx_group (src_reg, subreg, p);
716 validate_replace_rtx_group (src, src_reg, insn);
718 /* Now see if all the changes are valid. */
719 if (! apply_change_group ())
721 /* One or more changes were no good. Back out everything. */
722 PUT_MODE (src_reg, old_mode);
723 XEXP (src, 0) = src_reg;
727 rtx note = find_reg_note (p, REG_EQUAL, NULL_RTX);
729 remove_note (p, note);
734 /* If we were not able to update the users of src to use dest directly, try
735 instead moving the value to dest directly before the operation. */
738 copy_src_to_dest (rtx insn, rtx src, rtx dest, int old_max_uid)
753 /* A REG_LIVE_LENGTH of -1 indicates the register is equivalent to a constant
754 or memory location and is used infrequently; a REG_LIVE_LENGTH of -2 is
755 parameter when there is no frame pointer that is not allocated a register.
756 For now, we just reject them, rather than incrementing the live length. */
759 && REG_LIVE_LENGTH (REGNO (src)) > 0
761 && !RTX_UNCHANGING_P (dest)
762 && REG_LIVE_LENGTH (REGNO (dest)) > 0
763 && (set = single_set (insn)) != NULL_RTX
764 && !reg_mentioned_p (dest, SET_SRC (set))
765 && GET_MODE (src) == GET_MODE (dest))
767 int old_num_regs = reg_rtx_no;
769 /* Generate the src->dest move. */
771 emit_move_insn (dest, src);
774 /* If this sequence uses new registers, we may not use it. */
775 if (old_num_regs != reg_rtx_no
776 || ! validate_replace_rtx (src, dest, insn))
778 /* We have to restore reg_rtx_no to its old value, lest
779 recompute_reg_usage will try to compute the usage of the
780 new regs, yet reg_n_info is not valid for them. */
781 reg_rtx_no = old_num_regs;
784 emit_insn_before (seq, insn);
785 move_insn = PREV_INSN (insn);
786 p_move_notes = ®_NOTES (move_insn);
787 p_insn_notes = ®_NOTES (insn);
789 /* Move any notes mentioning src to the move instruction. */
790 for (link = REG_NOTES (insn); link != NULL_RTX; link = next)
792 next = XEXP (link, 1);
793 if (XEXP (link, 0) == src)
795 *p_move_notes = link;
796 p_move_notes = &XEXP (link, 1);
800 *p_insn_notes = link;
801 p_insn_notes = &XEXP (link, 1);
805 *p_move_notes = NULL_RTX;
806 *p_insn_notes = NULL_RTX;
808 /* Is the insn the head of a basic block? If so extend it. */
809 insn_uid = INSN_UID (insn);
810 move_uid = INSN_UID (move_insn);
811 if (insn_uid < old_max_uid)
813 bb = regmove_bb_head[insn_uid];
816 BB_HEAD (BASIC_BLOCK (bb)) = move_insn;
817 regmove_bb_head[insn_uid] = -1;
821 /* Update the various register tables. */
822 dest_regno = REGNO (dest);
823 REG_N_SETS (dest_regno) ++;
824 REG_LIVE_LENGTH (dest_regno)++;
825 if (REGNO_FIRST_UID (dest_regno) == insn_uid)
826 REGNO_FIRST_UID (dest_regno) = move_uid;
828 src_regno = REGNO (src);
829 if (! find_reg_note (move_insn, REG_DEAD, src))
830 REG_LIVE_LENGTH (src_regno)++;
832 if (REGNO_FIRST_UID (src_regno) == insn_uid)
833 REGNO_FIRST_UID (src_regno) = move_uid;
835 if (REGNO_LAST_UID (src_regno) == insn_uid)
836 REGNO_LAST_UID (src_regno) = move_uid;
838 if (REGNO_LAST_NOTE_UID (src_regno) == insn_uid)
839 REGNO_LAST_NOTE_UID (src_regno) = move_uid;
844 /* Return whether REG is set in only one location, and is set to a
845 constant, but is set in a different basic block from INSN (an
846 instructions which uses REG). In this case REG is equivalent to a
847 constant, and we don't want to break that equivalence, because that
848 may increase register pressure and make reload harder. If REG is
849 set in the same basic block as INSN, we don't worry about it,
850 because we'll probably need a register anyhow (??? but what if REG
851 is used in a different basic block as well as this one?). FIRST is
852 the first insn in the function. */
855 reg_is_remote_constant_p (rtx reg, rtx insn, rtx first)
859 if (REG_N_SETS (REGNO (reg)) != 1)
862 /* Look for the set. */
863 for (p = LOG_LINKS (insn); p; p = XEXP (p, 1))
867 if (REG_NOTE_KIND (p) != 0)
869 s = single_set (XEXP (p, 0));
871 && REG_P (SET_DEST (s))
872 && REGNO (SET_DEST (s)) == REGNO (reg))
874 /* The register is set in the same basic block. */
879 for (p = first; p && p != insn; p = NEXT_INSN (p))
887 && REG_P (SET_DEST (s))
888 && REGNO (SET_DEST (s)) == REGNO (reg))
890 /* This is the instruction which sets REG. If there is a
891 REG_EQUAL note, then REG is equivalent to a constant. */
892 if (find_reg_note (p, REG_EQUAL, NULL_RTX))
901 /* INSN is adding a CONST_INT to a REG. We search backwards looking for
902 another add immediate instruction with the same source and dest registers,
903 and if we find one, we change INSN to an increment, and return 1. If
904 no changes are made, we return 0.
907 (set (reg100) (plus reg1 offset1))
909 (set (reg100) (plus reg1 offset2))
911 (set (reg100) (plus reg1 offset1))
913 (set (reg100) (plus reg100 offset2-offset1)) */
915 /* ??? What does this comment mean? */
916 /* cse disrupts preincrement / postdecrement sequences when it finds a
917 hard register as ultimate source, like the frame pointer. */
920 fixup_match_2 (rtx insn, rtx dst, rtx src, rtx offset, FILE *regmove_dump_file)
922 rtx p, dst_death = 0;
923 int length, num_calls = 0;
925 /* If SRC dies in INSN, we'd have to move the death note. This is
926 considered to be very unlikely, so we just skip the optimization
928 if (find_regno_note (insn, REG_DEAD, REGNO (src)))
931 /* Scan backward to find the first instruction that sets DST. */
933 for (length = 0, p = PREV_INSN (insn); p; p = PREV_INSN (p))
937 /* ??? We can't scan past the end of a basic block without updating
938 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
939 if (perhaps_ends_bb_p (p))
941 else if (! INSN_P (p))
944 if (find_regno_note (p, REG_DEAD, REGNO (dst)))
949 pset = single_set (p);
950 if (pset && SET_DEST (pset) == dst
951 && GET_CODE (SET_SRC (pset)) == PLUS
952 && XEXP (SET_SRC (pset), 0) == src
953 && GET_CODE (XEXP (SET_SRC (pset), 1)) == CONST_INT)
955 HOST_WIDE_INT newconst
956 = INTVAL (offset) - INTVAL (XEXP (SET_SRC (pset), 1));
957 rtx add = gen_add3_insn (dst, dst, GEN_INT (newconst));
959 if (add && validate_change (insn, &PATTERN (insn), add, 0))
961 /* Remove the death note for DST from DST_DEATH. */
964 remove_death (REGNO (dst), dst_death);
965 REG_LIVE_LENGTH (REGNO (dst)) += length;
966 REG_N_CALLS_CROSSED (REGNO (dst)) += num_calls;
969 if (regmove_dump_file)
970 fprintf (regmove_dump_file,
971 "Fixed operand of insn %d.\n",
975 for (p = PREV_INSN (insn); p; p = PREV_INSN (p))
982 if (reg_overlap_mentioned_p (dst, PATTERN (p)))
984 if (try_auto_increment (p, insn, 0, dst, newconst, 0))
989 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
996 if (reg_overlap_mentioned_p (dst, PATTERN (p)))
998 try_auto_increment (p, insn, 0, dst, newconst, 1);
1007 if (reg_set_p (dst, PATTERN (p)))
1010 /* If we have passed a call instruction, and the
1011 pseudo-reg SRC is not already live across a call,
1012 then don't perform the optimization. */
1013 /* reg_set_p is overly conservative for CALL_INSNS, thinks that all
1014 hard regs are clobbered. Thus, we only use it for src for
1021 if (REG_N_CALLS_CROSSED (REGNO (src)) == 0)
1024 if (call_used_regs [REGNO (dst)]
1025 || find_reg_fusage (p, CLOBBER, dst))
1028 else if (reg_set_p (src, PATTERN (p)))
1035 /* Main entry for the register move optimization.
1036 F is the first instruction.
1037 NREGS is one plus the highest pseudo-reg number used in the instruction.
1038 REGMOVE_DUMP_FILE is a stream for output of a trace of actions taken
1039 (or 0 if none should be output). */
1042 regmove_optimize (rtx f, int nregs, FILE *regmove_dump_file)
1044 int old_max_uid = get_max_uid ();
1049 rtx copy_src, copy_dst;
1052 /* ??? Hack. Regmove doesn't examine the CFG, and gets mightily
1053 confused by non-call exceptions ending blocks. */
1054 if (flag_non_call_exceptions)
1057 /* Find out where a potential flags register is live, and so that we
1058 can suppress some optimizations in those zones. */
1059 mark_flags_life_zones (discover_flags_reg ());
1061 regno_src_regno = xmalloc (sizeof *regno_src_regno * nregs);
1062 for (i = nregs; --i >= 0; ) regno_src_regno[i] = -1;
1064 regmove_bb_head = xmalloc (sizeof (int) * (old_max_uid + 1));
1065 for (i = old_max_uid; i >= 0; i--) regmove_bb_head[i] = -1;
1067 regmove_bb_head[INSN_UID (BB_HEAD (bb))] = bb->index;
1069 /* A forward/backward pass. Replace output operands with input operands. */
1071 for (pass = 0; pass <= 2; pass++)
1073 if (! flag_regmove && pass >= flag_expensive_optimizations)
1076 if (regmove_dump_file)
1077 fprintf (regmove_dump_file, "Starting %s pass...\n",
1078 pass ? "backward" : "forward");
1080 for (insn = pass ? get_last_insn () : f; insn;
1081 insn = pass ? PREV_INSN (insn) : NEXT_INSN (insn))
1084 int op_no, match_no;
1086 set = single_set (insn);
1090 if (flag_expensive_optimizations && ! pass
1091 && (GET_CODE (SET_SRC (set)) == SIGN_EXTEND
1092 || GET_CODE (SET_SRC (set)) == ZERO_EXTEND)
1093 && REG_P (XEXP (SET_SRC (set), 0))
1094 && REG_P (SET_DEST (set)))
1095 optimize_reg_copy_3 (insn, SET_DEST (set), SET_SRC (set));
1097 if (flag_expensive_optimizations && ! pass
1098 && REG_P (SET_SRC (set))
1099 && REG_P (SET_DEST (set)))
1101 /* If this is a register-register copy where SRC is not dead,
1102 see if we can optimize it. If this optimization succeeds,
1103 it will become a copy where SRC is dead. */
1104 if ((find_reg_note (insn, REG_DEAD, SET_SRC (set))
1105 || optimize_reg_copy_1 (insn, SET_DEST (set), SET_SRC (set)))
1106 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
1108 /* Similarly for a pseudo-pseudo copy when SRC is dead. */
1109 if (REGNO (SET_SRC (set)) >= FIRST_PSEUDO_REGISTER)
1110 optimize_reg_copy_2 (insn, SET_DEST (set), SET_SRC (set));
1111 if (regno_src_regno[REGNO (SET_DEST (set))] < 0
1112 && SET_SRC (set) != SET_DEST (set))
1114 int srcregno = REGNO (SET_SRC (set));
1115 if (regno_src_regno[srcregno] >= 0)
1116 srcregno = regno_src_regno[srcregno];
1117 regno_src_regno[REGNO (SET_DEST (set))] = srcregno;
1124 if (! find_matches (insn, &match))
1127 /* Now scan through the operands looking for a source operand
1128 which is supposed to match the destination operand.
1129 Then scan forward for an instruction which uses the dest
1131 If it dies there, then replace the dest in both operands with
1132 the source operand. */
1134 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1136 rtx src, dst, src_subreg;
1137 enum reg_class src_class, dst_class;
1139 match_no = match.with[op_no];
1141 /* Nothing to do if the two operands aren't supposed to match. */
1145 src = recog_data.operand[op_no];
1146 dst = recog_data.operand[match_no];
1152 if (GET_CODE (dst) == SUBREG
1153 && GET_MODE_SIZE (GET_MODE (dst))
1154 >= GET_MODE_SIZE (GET_MODE (SUBREG_REG (dst))))
1157 = gen_rtx_SUBREG (GET_MODE (SUBREG_REG (dst)),
1158 src, SUBREG_BYTE (dst));
1159 dst = SUBREG_REG (dst);
1162 || REGNO (dst) < FIRST_PSEUDO_REGISTER)
1165 if (REGNO (src) < FIRST_PSEUDO_REGISTER)
1167 if (match.commutative[op_no] < op_no)
1168 regno_src_regno[REGNO (dst)] = REGNO (src);
1172 if (REG_LIVE_LENGTH (REGNO (src)) < 0)
1175 /* op_no/src must be a read-only operand, and
1176 match_operand/dst must be a write-only operand. */
1177 if (match.use[op_no] != READ
1178 || match.use[match_no] != WRITE)
1181 if (match.early_clobber[match_no]
1182 && count_occurrences (PATTERN (insn), src, 0) > 1)
1185 /* Make sure match_operand is the destination. */
1186 if (recog_data.operand[match_no] != SET_DEST (set))
1189 /* If the operands already match, then there is nothing to do. */
1190 if (operands_match_p (src, dst))
1193 /* But in the commutative case, we might find a better match. */
1194 if (match.commutative[op_no] >= 0)
1196 rtx comm = recog_data.operand[match.commutative[op_no]];
1197 if (operands_match_p (comm, dst)
1198 && (replacement_quality (comm)
1199 >= replacement_quality (src)))
1203 src_class = reg_preferred_class (REGNO (src));
1204 dst_class = reg_preferred_class (REGNO (dst));
1205 if (! regclass_compatible_p (src_class, dst_class))
1208 if (GET_MODE (src) != GET_MODE (dst))
1211 if (fixup_match_1 (insn, set, src, src_subreg, dst, pass,
1219 /* A backward pass. Replace input operands with output operands. */
1221 if (regmove_dump_file)
1222 fprintf (regmove_dump_file, "Starting backward pass...\n");
1224 for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
1228 int op_no, match_no;
1231 if (! find_matches (insn, &match))
1234 /* Now scan through the operands looking for a destination operand
1235 which is supposed to match a source operand.
1236 Then scan backward for an instruction which sets the source
1237 operand. If safe, then replace the source operand with the
1238 dest operand in both instructions. */
1240 copy_src = NULL_RTX;
1241 copy_dst = NULL_RTX;
1242 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1244 rtx set, p, src, dst;
1245 rtx src_note, dst_note;
1247 enum reg_class src_class, dst_class;
1250 match_no = match.with[op_no];
1252 /* Nothing to do if the two operands aren't supposed to match. */
1256 dst = recog_data.operand[match_no];
1257 src = recog_data.operand[op_no];
1263 || REGNO (dst) < FIRST_PSEUDO_REGISTER
1264 || REG_LIVE_LENGTH (REGNO (dst)) < 0
1265 || RTX_UNCHANGING_P (dst)
1266 || GET_MODE (src) != GET_MODE (dst))
1269 /* If the operands already match, then there is nothing to do. */
1270 if (operands_match_p (src, dst))
1273 if (match.commutative[op_no] >= 0)
1275 rtx comm = recog_data.operand[match.commutative[op_no]];
1276 if (operands_match_p (comm, dst))
1280 set = single_set (insn);
1284 /* Note that single_set ignores parts of a parallel set for
1285 which one of the destinations is REG_UNUSED. We can't
1286 handle that here, since we can wind up rewriting things
1287 such that a single register is set twice within a single
1289 if (reg_set_p (src, insn))
1292 /* match_no/dst must be a write-only operand, and
1293 operand_operand/src must be a read-only operand. */
1294 if (match.use[op_no] != READ
1295 || match.use[match_no] != WRITE)
1298 if (match.early_clobber[match_no]
1299 && count_occurrences (PATTERN (insn), src, 0) > 1)
1302 /* Make sure match_no is the destination. */
1303 if (recog_data.operand[match_no] != SET_DEST (set))
1306 if (REGNO (src) < FIRST_PSEUDO_REGISTER)
1308 if (GET_CODE (SET_SRC (set)) == PLUS
1309 && GET_CODE (XEXP (SET_SRC (set), 1)) == CONST_INT
1310 && XEXP (SET_SRC (set), 0) == src
1311 && fixup_match_2 (insn, dst, src,
1312 XEXP (SET_SRC (set), 1),
1317 src_class = reg_preferred_class (REGNO (src));
1318 dst_class = reg_preferred_class (REGNO (dst));
1320 if (! (src_note = find_reg_note (insn, REG_DEAD, src)))
1322 /* We used to force the copy here like in other cases, but
1323 it produces worse code, as it eliminates no copy
1324 instructions and the copy emitted will be produced by
1325 reload anyway. On patterns with multiple alternatives,
1326 there may be better solution available.
1328 In particular this change produced slower code for numeric
1334 if (! regclass_compatible_p (src_class, dst_class))
1344 /* Can not modify an earlier insn to set dst if this insn
1345 uses an old value in the source. */
1346 if (reg_overlap_mentioned_p (dst, SET_SRC (set)))
1356 /* If src is set once in a different basic block,
1357 and is set equal to a constant, then do not use
1358 it for this optimization, as this would make it
1359 no longer equivalent to a constant. */
1361 if (reg_is_remote_constant_p (src, insn, f))
1372 if (regmove_dump_file)
1373 fprintf (regmove_dump_file,
1374 "Could fix operand %d of insn %d matching operand %d.\n",
1375 op_no, INSN_UID (insn), match_no);
1377 /* Scan backward to find the first instruction that uses
1378 the input operand. If the operand is set here, then
1379 replace it in both instructions with match_no. */
1381 for (length = 0, p = PREV_INSN (insn); p; p = PREV_INSN (p))
1385 /* ??? We can't scan past the end of a basic block without
1386 updating the register lifetime info
1387 (REG_DEAD/basic_block_live_at_start). */
1388 if (perhaps_ends_bb_p (p))
1390 else if (! INSN_P (p))
1395 /* ??? See if all of SRC is set in P. This test is much
1396 more conservative than it needs to be. */
1397 pset = single_set (p);
1398 if (pset && SET_DEST (pset) == src)
1400 /* We use validate_replace_rtx, in case there
1401 are multiple identical source operands. All of
1402 them have to be changed at the same time. */
1403 if (validate_replace_rtx (src, dst, insn))
1405 if (validate_change (p, &SET_DEST (pset),
1410 /* Change all source operands back.
1411 This modifies the dst as a side-effect. */
1412 validate_replace_rtx (dst, src, insn);
1413 /* Now make sure the dst is right. */
1414 validate_change (insn,
1415 recog_data.operand_loc[match_no],
1422 if (reg_overlap_mentioned_p (src, PATTERN (p))
1423 || reg_overlap_mentioned_p (dst, PATTERN (p)))
1426 /* If we have passed a call instruction, and the
1427 pseudo-reg DST is not already live across a call,
1428 then don't perform the optimization. */
1433 if (REG_N_CALLS_CROSSED (REGNO (dst)) == 0)
1442 /* Remove the death note for SRC from INSN. */
1443 remove_note (insn, src_note);
1444 /* Move the death note for SRC to P if it is used
1446 if (reg_overlap_mentioned_p (src, PATTERN (p)))
1448 XEXP (src_note, 1) = REG_NOTES (p);
1449 REG_NOTES (p) = src_note;
1451 /* If there is a REG_DEAD note for DST on P, then remove
1452 it, because DST is now set there. */
1453 if ((dst_note = find_reg_note (p, REG_DEAD, dst)))
1454 remove_note (p, dst_note);
1456 dstno = REGNO (dst);
1457 srcno = REGNO (src);
1459 REG_N_SETS (dstno)++;
1460 REG_N_SETS (srcno)--;
1462 REG_N_CALLS_CROSSED (dstno) += num_calls;
1463 REG_N_CALLS_CROSSED (srcno) -= num_calls;
1465 REG_LIVE_LENGTH (dstno) += length;
1466 if (REG_LIVE_LENGTH (srcno) >= 0)
1468 REG_LIVE_LENGTH (srcno) -= length;
1469 /* REG_LIVE_LENGTH is only an approximation after
1470 combine if sched is not run, so make sure that we
1471 still have a reasonable value. */
1472 if (REG_LIVE_LENGTH (srcno) < 2)
1473 REG_LIVE_LENGTH (srcno) = 2;
1476 if (regmove_dump_file)
1477 fprintf (regmove_dump_file,
1478 "Fixed operand %d of insn %d matching operand %d.\n",
1479 op_no, INSN_UID (insn), match_no);
1485 /* If we weren't able to replace any of the alternatives, try an
1486 alternative approach of copying the source to the destination. */
1487 if (!success && copy_src != NULL_RTX)
1488 copy_src_to_dest (insn, copy_src, copy_dst, old_max_uid);
1493 /* In fixup_match_1, some insns may have been inserted after basic block
1494 ends. Fix that here. */
1497 rtx end = BB_END (bb);
1499 rtx next = NEXT_INSN (new);
1500 while (next != 0 && INSN_UID (next) >= old_max_uid
1501 && (bb->next_bb == EXIT_BLOCK_PTR || BB_HEAD (bb->next_bb) != next))
1502 new = next, next = NEXT_INSN (new);
1508 free (regno_src_regno);
1509 free (regmove_bb_head);
1512 /* Returns nonzero if INSN's pattern has matching constraints for any operand.
1513 Returns 0 if INSN can't be recognized, or if the alternative can't be
1516 Initialize the info in MATCHP based on the constraints. */
1519 find_matches (rtx insn, struct match *matchp)
1521 int likely_spilled[MAX_RECOG_OPERANDS];
1523 int any_matches = 0;
1525 extract_insn (insn);
1526 if (! constrain_operands (0))
1529 /* Must initialize this before main loop, because the code for
1530 the commutative case may set matches for operands other than
1532 for (op_no = recog_data.n_operands; --op_no >= 0; )
1533 matchp->with[op_no] = matchp->commutative[op_no] = -1;
1535 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1541 p = recog_data.constraints[op_no];
1543 likely_spilled[op_no] = 0;
1544 matchp->use[op_no] = READ;
1545 matchp->early_clobber[op_no] = 0;
1547 matchp->use[op_no] = WRITE;
1549 matchp->use[op_no] = READWRITE;
1551 for (;*p && i < which_alternative; p++)
1555 while ((c = *p) != '\0' && c != ',')
1564 matchp->early_clobber[op_no] = 1;
1567 matchp->commutative[op_no] = op_no + 1;
1568 matchp->commutative[op_no + 1] = op_no;
1571 case '0': case '1': case '2': case '3': case '4':
1572 case '5': case '6': case '7': case '8': case '9':
1575 unsigned long match_ul = strtoul (p, &end, 10);
1576 int match = match_ul;
1580 if (match < op_no && likely_spilled[match])
1582 matchp->with[op_no] = match;
1584 if (matchp->commutative[op_no] >= 0)
1585 matchp->with[matchp->commutative[op_no]] = match;
1589 case 'a': case 'b': case 'c': case 'd': case 'e': case 'f': case 'h':
1590 case 'j': case 'k': case 'l': case 'p': case 'q': case 't': case 'u':
1591 case 'v': case 'w': case 'x': case 'y': case 'z': case 'A': case 'B':
1592 case 'C': case 'D': case 'W': case 'Y': case 'Z':
1593 if (CLASS_LIKELY_SPILLED_P (REG_CLASS_FROM_CONSTRAINT ((unsigned char) c, p) ))
1594 likely_spilled[op_no] = 1;
1597 p += CONSTRAINT_LEN (c, p);
1603 /* Try to replace all occurrences of DST_REG with SRC in LOC, that is
1604 assumed to be in INSN. */
1607 replace_in_call_usage (rtx *loc, unsigned int dst_reg, rtx src, rtx insn)
1617 code = GET_CODE (x);
1620 if (REGNO (x) != dst_reg)
1623 validate_change (insn, loc, src, 1);
1628 /* Process each of our operands recursively. */
1629 fmt = GET_RTX_FORMAT (code);
1630 for (i = 0; i < GET_RTX_LENGTH (code); i++, fmt++)
1632 replace_in_call_usage (&XEXP (x, i), dst_reg, src, insn);
1633 else if (*fmt == 'E')
1634 for (j = 0; j < XVECLEN (x, i); j++)
1635 replace_in_call_usage (& XVECEXP (x, i, j), dst_reg, src, insn);
1638 /* Try to replace output operand DST in SET, with input operand SRC. SET is
1639 the only set in INSN. INSN has just been recognized and constrained.
1640 SRC is operand number OPERAND_NUMBER in INSN.
1641 DST is operand number MATCH_NUMBER in INSN.
1642 If BACKWARD is nonzero, we have been called in a backward pass.
1643 Return nonzero for success. */
1646 fixup_match_1 (rtx insn, rtx set, rtx src, rtx src_subreg, rtx dst,
1647 int backward, int operand_number, int match_number,
1648 FILE *regmove_dump_file)
1651 rtx post_inc = 0, post_inc_set = 0, search_end = 0;
1653 int num_calls = 0, s_num_calls = 0;
1654 enum rtx_code code = NOTE;
1655 HOST_WIDE_INT insn_const = 0, newconst = 0;
1656 rtx overlap = 0; /* need to move insn ? */
1657 rtx src_note = find_reg_note (insn, REG_DEAD, src), dst_note = NULL_RTX;
1658 int length, s_length;
1660 /* If SRC is marked as unchanging, we may not change it.
1661 ??? Maybe we could get better code by removing the unchanging bit
1662 instead, and changing it back if we don't succeed? */
1663 if (RTX_UNCHANGING_P (src))
1668 /* Look for (set (regX) (op regA constX))
1669 (set (regY) (op regA constY))
1671 (set (regA) (op regA constX)).
1672 (set (regY) (op regA constY-constX)).
1673 This works for add and shift operations, if
1674 regA is dead after or set by the second insn. */
1676 code = GET_CODE (SET_SRC (set));
1677 if ((code == PLUS || code == LSHIFTRT
1678 || code == ASHIFT || code == ASHIFTRT)
1679 && XEXP (SET_SRC (set), 0) == src
1680 && GET_CODE (XEXP (SET_SRC (set), 1)) == CONST_INT)
1681 insn_const = INTVAL (XEXP (SET_SRC (set), 1));
1682 else if (! stable_and_no_regs_but_for_p (SET_SRC (set), src, dst))
1685 /* We might find a src_note while scanning. */
1689 if (regmove_dump_file)
1690 fprintf (regmove_dump_file,
1691 "Could fix operand %d of insn %d matching operand %d.\n",
1692 operand_number, INSN_UID (insn), match_number);
1694 /* If SRC is equivalent to a constant set in a different basic block,
1695 then do not use it for this optimization. We want the equivalence
1696 so that if we have to reload this register, we can reload the
1697 constant, rather than extending the lifespan of the register. */
1698 if (reg_is_remote_constant_p (src, insn, get_insns ()))
1701 /* Scan forward to find the next instruction that
1702 uses the output operand. If the operand dies here,
1703 then replace it in both instructions with
1706 for (length = s_length = 0, p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
1709 replace_in_call_usage (& CALL_INSN_FUNCTION_USAGE (p),
1710 REGNO (dst), src, p);
1712 /* ??? We can't scan past the end of a basic block without updating
1713 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
1714 if (perhaps_ends_bb_p (p))
1716 else if (! INSN_P (p))
1723 if (reg_set_p (src, p) || reg_set_p (dst, p)
1724 || (GET_CODE (PATTERN (p)) == USE
1725 && reg_overlap_mentioned_p (src, XEXP (PATTERN (p), 0))))
1728 /* See if all of DST dies in P. This test is
1729 slightly more conservative than it needs to be. */
1730 if ((dst_note = find_regno_note (p, REG_DEAD, REGNO (dst)))
1731 && (GET_MODE (XEXP (dst_note, 0)) == GET_MODE (dst)))
1733 /* If we would be moving INSN, check that we won't move it
1734 into the shadow of a live a live flags register. */
1735 /* ??? We only try to move it in front of P, although
1736 we could move it anywhere between OVERLAP and P. */
1737 if (overlap && GET_MODE (PREV_INSN (p)) != VOIDmode)
1743 rtx set2 = NULL_RTX;
1745 /* If an optimization is done, the value of SRC while P
1746 is executed will be changed. Check that this is OK. */
1747 if (reg_overlap_mentioned_p (src, PATTERN (p)))
1749 for (q = p; q; q = NEXT_INSN (q))
1751 /* ??? We can't scan past the end of a basic block without
1752 updating the register lifetime info
1753 (REG_DEAD/basic_block_live_at_start). */
1754 if (perhaps_ends_bb_p (q))
1759 else if (! INSN_P (q))
1761 else if (reg_overlap_mentioned_p (src, PATTERN (q))
1762 || reg_set_p (src, q))
1766 set2 = single_set (q);
1767 if (! q || ! set2 || GET_CODE (SET_SRC (set2)) != code
1768 || XEXP (SET_SRC (set2), 0) != src
1769 || GET_CODE (XEXP (SET_SRC (set2), 1)) != CONST_INT
1770 || (SET_DEST (set2) != src
1771 && ! find_reg_note (q, REG_DEAD, src)))
1773 /* If this is a PLUS, we can still save a register by doing
1776 src -= insn_const; .
1777 This also gives opportunities for subsequent
1778 optimizations in the backward pass, so do it there. */
1779 if (code == PLUS && backward
1780 /* Don't do this if we can likely tie DST to SET_DEST
1781 of P later; we can't do this tying here if we got a
1783 && ! (dst_note && ! REG_N_CALLS_CROSSED (REGNO (dst))
1785 && REG_P (SET_DEST (single_set (p)))
1786 && (REGNO (SET_DEST (single_set (p)))
1787 < FIRST_PSEUDO_REGISTER))
1788 /* We may only emit an insn directly after P if we
1789 are not in the shadow of a live flags register. */
1790 && GET_MODE (p) == VOIDmode)
1795 newconst = -insn_const;
1803 newconst = INTVAL (XEXP (SET_SRC (set2), 1)) - insn_const;
1804 /* Reject out of range shifts. */
1807 || ((unsigned HOST_WIDE_INT) newconst
1808 >= (GET_MODE_BITSIZE (GET_MODE
1809 (SET_SRC (set2)))))))
1814 if (SET_DEST (set2) != src)
1815 post_inc_set = set2;
1818 /* We use 1 as last argument to validate_change so that all
1819 changes are accepted or rejected together by apply_change_group
1820 when it is called by validate_replace_rtx . */
1821 validate_change (q, &XEXP (SET_SRC (set2), 1),
1822 GEN_INT (newconst), 1);
1824 validate_change (insn, recog_data.operand_loc[match_number], src, 1);
1825 if (validate_replace_rtx (dst, src_subreg, p))
1830 if (reg_overlap_mentioned_p (dst, PATTERN (p)))
1832 if (! src_note && reg_overlap_mentioned_p (src, PATTERN (p)))
1834 /* INSN was already checked to be movable wrt. the registers that it
1835 sets / uses when we found no REG_DEAD note for src on it, but it
1836 still might clobber the flags register. We'll have to check that
1837 we won't insert it into the shadow of a live flags register when
1838 we finally know where we are to move it. */
1840 src_note = find_reg_note (p, REG_DEAD, src);
1843 /* If we have passed a call instruction, and the pseudo-reg SRC is not
1844 already live across a call, then don't perform the optimization. */
1847 if (REG_N_CALLS_CROSSED (REGNO (src)) == 0)
1861 /* Remove the death note for DST from P. */
1862 remove_note (p, dst_note);
1865 post_inc = emit_insn_after (copy_rtx (PATTERN (insn)), p);
1866 if ((HAVE_PRE_INCREMENT || HAVE_PRE_DECREMENT)
1868 && try_auto_increment (search_end, post_inc, 0, src, newconst, 1))
1870 validate_change (insn, &XEXP (SET_SRC (set), 1), GEN_INT (insn_const), 0);
1871 REG_N_SETS (REGNO (src))++;
1872 REG_LIVE_LENGTH (REGNO (src))++;
1876 /* The lifetime of src and dest overlap,
1877 but we can change this by moving insn. */
1878 rtx pat = PATTERN (insn);
1880 remove_note (overlap, src_note);
1881 if ((HAVE_POST_INCREMENT || HAVE_POST_DECREMENT)
1883 && try_auto_increment (overlap, insn, 0, src, insn_const, 0))
1887 rtx notes = REG_NOTES (insn);
1889 emit_insn_after_with_line_notes (pat, PREV_INSN (p), insn);
1891 /* emit_insn_after_with_line_notes has no
1892 return value, so search for the new insn. */
1894 while (! INSN_P (insn) || PATTERN (insn) != pat)
1895 insn = PREV_INSN (insn);
1897 REG_NOTES (insn) = notes;
1900 /* Sometimes we'd generate src = const; src += n;
1901 if so, replace the instruction that set src
1902 in the first place. */
1904 if (! overlap && (code == PLUS || code == MINUS))
1906 rtx note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
1907 rtx q, set2 = NULL_RTX;
1908 int num_calls2 = 0, s_length2 = 0;
1910 if (note && CONSTANT_P (XEXP (note, 0)))
1912 for (q = PREV_INSN (insn); q; q = PREV_INSN (q))
1914 /* ??? We can't scan past the end of a basic block without
1915 updating the register lifetime info
1916 (REG_DEAD/basic_block_live_at_start). */
1917 if (perhaps_ends_bb_p (q))
1922 else if (! INSN_P (q))
1926 if (reg_set_p (src, q))
1928 set2 = single_set (q);
1931 if (reg_overlap_mentioned_p (src, PATTERN (q)))
1939 if (q && set2 && SET_DEST (set2) == src && CONSTANT_P (SET_SRC (set2))
1940 && validate_change (insn, &SET_SRC (set), XEXP (note, 0), 0))
1943 REG_N_SETS (REGNO (src))--;
1944 REG_N_CALLS_CROSSED (REGNO (src)) -= num_calls2;
1945 REG_LIVE_LENGTH (REGNO (src)) -= s_length2;
1951 if ((HAVE_PRE_INCREMENT || HAVE_PRE_DECREMENT)
1952 && (code == PLUS || code == MINUS) && insn_const
1953 && try_auto_increment (p, insn, 0, src, insn_const, 1))
1955 else if ((HAVE_POST_INCREMENT || HAVE_POST_DECREMENT)
1957 && try_auto_increment (p, post_inc, post_inc_set, src, newconst, 0))
1959 /* If post_inc still prevails, try to find an
1960 insn where it can be used as a pre-in/decrement.
1961 If code is MINUS, this was already tried. */
1962 if (post_inc && code == PLUS
1963 /* Check that newconst is likely to be usable
1964 in a pre-in/decrement before starting the search. */
1965 && ((HAVE_PRE_INCREMENT && newconst > 0 && newconst <= MOVE_MAX)
1966 || (HAVE_PRE_DECREMENT && newconst < 0 && newconst >= -MOVE_MAX))
1967 && exact_log2 (newconst))
1971 inc_dest = post_inc_set ? SET_DEST (post_inc_set) : src;
1972 for (q = post_inc; (q = NEXT_INSN (q)); )
1974 /* ??? We can't scan past the end of a basic block without updating
1975 the register lifetime info
1976 (REG_DEAD/basic_block_live_at_start). */
1977 if (perhaps_ends_bb_p (q))
1979 else if (! INSN_P (q))
1981 else if (src != inc_dest
1982 && (reg_overlap_mentioned_p (src, PATTERN (q))
1983 || reg_set_p (src, q)))
1985 else if (reg_set_p (inc_dest, q))
1987 else if (reg_overlap_mentioned_p (inc_dest, PATTERN (q)))
1989 try_auto_increment (q, post_inc,
1990 post_inc_set, inc_dest, newconst, 1);
1996 /* Move the death note for DST to INSN if it is used
1998 if (reg_overlap_mentioned_p (dst, PATTERN (insn)))
2000 XEXP (dst_note, 1) = REG_NOTES (insn);
2001 REG_NOTES (insn) = dst_note;
2006 /* Move the death note for SRC from INSN to P. */
2008 remove_note (insn, src_note);
2009 XEXP (src_note, 1) = REG_NOTES (p);
2010 REG_NOTES (p) = src_note;
2012 REG_N_CALLS_CROSSED (REGNO (src)) += s_num_calls;
2015 REG_N_SETS (REGNO (src))++;
2016 REG_N_SETS (REGNO (dst))--;
2018 REG_N_CALLS_CROSSED (REGNO (dst)) -= num_calls;
2020 REG_LIVE_LENGTH (REGNO (src)) += s_length;
2021 if (REG_LIVE_LENGTH (REGNO (dst)) >= 0)
2023 REG_LIVE_LENGTH (REGNO (dst)) -= length;
2024 /* REG_LIVE_LENGTH is only an approximation after
2025 combine if sched is not run, so make sure that we
2026 still have a reasonable value. */
2027 if (REG_LIVE_LENGTH (REGNO (dst)) < 2)
2028 REG_LIVE_LENGTH (REGNO (dst)) = 2;
2030 if (regmove_dump_file)
2031 fprintf (regmove_dump_file,
2032 "Fixed operand %d of insn %d matching operand %d.\n",
2033 operand_number, INSN_UID (insn), match_number);
2038 /* Return nonzero if X is stable and mentions no registers but for
2039 mentioning SRC or mentioning / changing DST . If in doubt, presume
2041 The rationale is that we want to check if we can move an insn easily
2042 while just paying attention to SRC and DST. A register is considered
2043 stable if it has the RTX_UNCHANGING_P bit set, but that would still
2044 leave the burden to update REG_DEAD / REG_UNUSED notes, so we don't
2045 want any registers but SRC and DST. */
2047 stable_and_no_regs_but_for_p (rtx x, rtx src, rtx dst)
2049 RTX_CODE code = GET_CODE (x);
2050 switch (GET_RTX_CLASS (code))
2054 case RTX_COMM_ARITH:
2056 case RTX_COMM_COMPARE:
2058 case RTX_BITFIELD_OPS:
2061 const char *fmt = GET_RTX_FORMAT (code);
2062 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2064 && ! stable_and_no_regs_but_for_p (XEXP (x, i), src, dst))
2070 return x == src || x == dst;
2071 /* If this is a MEM, look inside - there might be a register hidden in
2072 the address of an unchanging MEM. */
2074 && ! stable_and_no_regs_but_for_p (XEXP (x, 0), src, dst))
2078 return ! rtx_unstable_p (x);
2082 /* Track stack adjustments and stack memory references. Attempt to
2083 reduce the number of stack adjustments by back-propagating across
2084 the memory references.
2086 This is intended primarily for use with targets that do not define
2087 ACCUMULATE_OUTGOING_ARGS. It is of significantly more value to
2088 targets that define PREFERRED_STACK_BOUNDARY more aligned than
2089 STACK_BOUNDARY (e.g. x86), or if not all registers can be pushed
2090 (e.g. x86 fp regs) which would ordinarily have to be implemented
2091 as a sub/mov pair due to restrictions in calls.c.
2093 Propagation stops when any of the insns that need adjusting are
2094 (a) no longer valid because we've exceeded their range, (b) a
2095 non-trivial push instruction, or (c) a call instruction.
2097 Restriction B is based on the assumption that push instructions
2098 are smaller or faster. If a port really wants to remove all
2099 pushes, it should have defined ACCUMULATE_OUTGOING_ARGS. The
2100 one exception that is made is for an add immediately followed
2103 /* This structure records stack memory references between stack adjusting
2108 HOST_WIDE_INT sp_offset;
2110 struct csa_memlist *next;
2113 static int stack_memref_p (rtx);
2114 static rtx single_set_for_csa (rtx);
2115 static void free_csa_memlist (struct csa_memlist *);
2116 static struct csa_memlist *record_one_stack_memref (rtx, rtx *,
2117 struct csa_memlist *);
2118 static int try_apply_stack_adjustment (rtx, struct csa_memlist *,
2119 HOST_WIDE_INT, HOST_WIDE_INT);
2120 static void combine_stack_adjustments_for_block (basic_block);
2121 static int record_stack_memrefs (rtx *, void *);
2124 /* Main entry point for stack adjustment combination. */
2127 combine_stack_adjustments (void)
2132 combine_stack_adjustments_for_block (bb);
2135 /* Recognize a MEM of the form (sp) or (plus sp const). */
2138 stack_memref_p (rtx x)
2144 if (x == stack_pointer_rtx)
2146 if (GET_CODE (x) == PLUS
2147 && XEXP (x, 0) == stack_pointer_rtx
2148 && GET_CODE (XEXP (x, 1)) == CONST_INT)
2154 /* Recognize either normal single_set or the hack in i386.md for
2155 tying fp and sp adjustments. */
2158 single_set_for_csa (rtx insn)
2161 rtx tmp = single_set (insn);
2165 if (!NONJUMP_INSN_P (insn)
2166 || GET_CODE (PATTERN (insn)) != PARALLEL)
2169 tmp = PATTERN (insn);
2170 if (GET_CODE (XVECEXP (tmp, 0, 0)) != SET)
2173 for (i = 1; i < XVECLEN (tmp, 0); ++i)
2175 rtx this = XVECEXP (tmp, 0, i);
2177 /* The special case is allowing a no-op set. */
2178 if (GET_CODE (this) == SET
2179 && SET_SRC (this) == SET_DEST (this))
2181 else if (GET_CODE (this) != CLOBBER
2182 && GET_CODE (this) != USE)
2186 return XVECEXP (tmp, 0, 0);
2189 /* Free the list of csa_memlist nodes. */
2192 free_csa_memlist (struct csa_memlist *memlist)
2194 struct csa_memlist *next;
2195 for (; memlist ; memlist = next)
2197 next = memlist->next;
2202 /* Create a new csa_memlist node from the given memory reference.
2203 It is already known that the memory is stack_memref_p. */
2205 static struct csa_memlist *
2206 record_one_stack_memref (rtx insn, rtx *mem, struct csa_memlist *next_memlist)
2208 struct csa_memlist *ml;
2210 ml = xmalloc (sizeof (*ml));
2212 if (XEXP (*mem, 0) == stack_pointer_rtx)
2215 ml->sp_offset = INTVAL (XEXP (XEXP (*mem, 0), 1));
2219 ml->next = next_memlist;
2224 /* Attempt to apply ADJUST to the stack adjusting insn INSN, as well
2225 as each of the memories in MEMLIST. Return true on success. */
2228 try_apply_stack_adjustment (rtx insn, struct csa_memlist *memlist, HOST_WIDE_INT new_adjust,
2229 HOST_WIDE_INT delta)
2231 struct csa_memlist *ml;
2234 set = single_set_for_csa (insn);
2235 validate_change (insn, &XEXP (SET_SRC (set), 1), GEN_INT (new_adjust), 1);
2237 for (ml = memlist; ml ; ml = ml->next)
2240 replace_equiv_address_nv (*ml->mem,
2241 plus_constant (stack_pointer_rtx,
2242 ml->sp_offset - delta)), 1);
2244 if (apply_change_group ())
2246 /* Succeeded. Update our knowledge of the memory references. */
2247 for (ml = memlist; ml ; ml = ml->next)
2248 ml->sp_offset -= delta;
2256 /* Called via for_each_rtx and used to record all stack memory references in
2257 the insn and discard all other stack pointer references. */
2258 struct record_stack_memrefs_data
2261 struct csa_memlist *memlist;
2265 record_stack_memrefs (rtx *xp, void *data)
2268 struct record_stack_memrefs_data *d =
2269 (struct record_stack_memrefs_data *) data;
2272 switch (GET_CODE (x))
2275 if (!reg_mentioned_p (stack_pointer_rtx, x))
2277 /* We are not able to handle correctly all possible memrefs containing
2278 stack pointer, so this check is necessary. */
2279 if (stack_memref_p (x))
2281 d->memlist = record_one_stack_memref (d->insn, xp, d->memlist);
2286 /* ??? We want be able to handle non-memory stack pointer
2287 references later. For now just discard all insns referring to
2288 stack pointer outside mem expressions. We would probably
2289 want to teach validate_replace to simplify expressions first.
2291 We can't just compare with STACK_POINTER_RTX because the
2292 reference to the stack pointer might be in some other mode.
2293 In particular, an explicit clobber in an asm statement will
2294 result in a QImode clobber. */
2295 if (REGNO (x) == STACK_POINTER_REGNUM)
2304 /* Subroutine of combine_stack_adjustments, called for each basic block. */
2307 combine_stack_adjustments_for_block (basic_block bb)
2309 HOST_WIDE_INT last_sp_adjust = 0;
2310 rtx last_sp_set = NULL_RTX;
2311 struct csa_memlist *memlist = NULL;
2312 rtx insn, next, set;
2313 struct record_stack_memrefs_data data;
2314 bool end_of_block = false;
2316 for (insn = BB_HEAD (bb); !end_of_block ; insn = next)
2318 end_of_block = insn == BB_END (bb);
2319 next = NEXT_INSN (insn);
2321 if (! INSN_P (insn))
2324 set = single_set_for_csa (insn);
2327 rtx dest = SET_DEST (set);
2328 rtx src = SET_SRC (set);
2330 /* Find constant additions to the stack pointer. */
2331 if (dest == stack_pointer_rtx
2332 && GET_CODE (src) == PLUS
2333 && XEXP (src, 0) == stack_pointer_rtx
2334 && GET_CODE (XEXP (src, 1)) == CONST_INT)
2336 HOST_WIDE_INT this_adjust = INTVAL (XEXP (src, 1));
2338 /* If we've not seen an adjustment previously, record
2339 it now and continue. */
2343 last_sp_adjust = this_adjust;
2347 /* If not all recorded memrefs can be adjusted, or the
2348 adjustment is now too large for a constant addition,
2349 we cannot merge the two stack adjustments.
2351 Also we need to be careful to not move stack pointer
2352 such that we create stack accesses outside the allocated
2353 area. We can combine an allocation into the first insn,
2354 or a deallocation into the second insn. We can not
2355 combine an allocation followed by a deallocation.
2357 The only somewhat frequent occurrence of the later is when
2358 a function allocates a stack frame but does not use it.
2359 For this case, we would need to analyze rtl stream to be
2360 sure that allocated area is really unused. This means not
2361 only checking the memory references, but also all registers
2362 or global memory references possibly containing a stack
2365 Perhaps the best way to address this problem is to teach
2366 gcc not to allocate stack for objects never used. */
2368 /* Combine an allocation into the first instruction. */
2369 if (STACK_GROWS_DOWNWARD ? this_adjust <= 0 : this_adjust >= 0)
2371 if (try_apply_stack_adjustment (last_sp_set, memlist,
2372 last_sp_adjust + this_adjust,
2377 last_sp_adjust += this_adjust;
2382 /* Otherwise we have a deallocation. Do not combine with
2383 a previous allocation. Combine into the second insn. */
2384 else if (STACK_GROWS_DOWNWARD
2385 ? last_sp_adjust >= 0 : last_sp_adjust <= 0)
2387 if (try_apply_stack_adjustment (insn, memlist,
2388 last_sp_adjust + this_adjust,
2392 delete_insn (last_sp_set);
2394 last_sp_adjust += this_adjust;
2395 free_csa_memlist (memlist);
2401 /* Combination failed. Restart processing from here. If
2402 deallocation+allocation conspired to cancel, we can
2403 delete the old deallocation insn. */
2404 if (last_sp_set && last_sp_adjust == 0)
2406 free_csa_memlist (memlist);
2409 last_sp_adjust = this_adjust;
2413 /* Find a predecrement of exactly the previous adjustment and
2414 turn it into a direct store. Obviously we can't do this if
2415 there were any intervening uses of the stack pointer. */
2418 && ((GET_CODE (XEXP (dest, 0)) == PRE_DEC
2420 == (HOST_WIDE_INT) GET_MODE_SIZE (GET_MODE (dest))))
2421 || (GET_CODE (XEXP (dest, 0)) == PRE_MODIFY
2422 && GET_CODE (XEXP (XEXP (dest, 0), 1)) == PLUS
2423 && XEXP (XEXP (XEXP (dest, 0), 1), 0) == stack_pointer_rtx
2424 && (GET_CODE (XEXP (XEXP (XEXP (dest, 0), 1), 1))
2426 && (INTVAL (XEXP (XEXP (XEXP (dest, 0), 1), 1))
2427 == -last_sp_adjust)))
2428 && XEXP (XEXP (dest, 0), 0) == stack_pointer_rtx
2429 && ! reg_mentioned_p (stack_pointer_rtx, src)
2430 && memory_address_p (GET_MODE (dest), stack_pointer_rtx)
2431 && validate_change (insn, &SET_DEST (set),
2432 replace_equiv_address (dest,
2436 delete_insn (last_sp_set);
2437 free_csa_memlist (memlist);
2439 last_sp_set = NULL_RTX;
2446 data.memlist = memlist;
2447 if (!CALL_P (insn) && last_sp_set
2448 && !for_each_rtx (&PATTERN (insn), record_stack_memrefs, &data))
2450 memlist = data.memlist;
2453 memlist = data.memlist;
2455 /* Otherwise, we were not able to process the instruction.
2456 Do not continue collecting data across such a one. */
2459 || reg_mentioned_p (stack_pointer_rtx, PATTERN (insn))))
2461 if (last_sp_set && last_sp_adjust == 0)
2462 delete_insn (last_sp_set);
2463 free_csa_memlist (memlist);
2465 last_sp_set = NULL_RTX;
2470 if (last_sp_set && last_sp_adjust == 0)
2471 delete_insn (last_sp_set);
OSDN Git Service
