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 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)
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 (insn)
366 switch (GET_CODE (insn))
370 /* These always end a basic block. */
374 /* A CALL_INSN might be the last insn of a basic block, if it is inside
375 an EH region or if there are nonlocal gotos. Note that this test is
376 very conservative. */
377 if (nonlocal_goto_handler_labels)
381 return can_throw_internal (insn);
385 /* INSN is a copy from SRC to DEST, both registers, and SRC does not die
388 Search forward to see if SRC dies before either it or DEST is modified,
389 but don't scan past the end of a basic block. If so, we can replace SRC
390 with DEST and let SRC die in INSN.
392 This will reduce the number of registers live in that range and may enable
393 DEST to be tied to SRC, thus often saving one register in addition to a
394 register-register copy. */
397 optimize_reg_copy_1 (rtx insn, rtx dest, rtx src)
402 int sregno = REGNO (src);
403 int dregno = REGNO (dest);
405 /* We don't want to mess with hard regs if register classes are small. */
407 || (SMALL_REGISTER_CLASSES
408 && (sregno < FIRST_PSEUDO_REGISTER
409 || dregno < FIRST_PSEUDO_REGISTER))
410 /* We don't see all updates to SP if they are in an auto-inc memory
411 reference, so we must disallow this optimization on them. */
412 || sregno == STACK_POINTER_REGNUM || dregno == STACK_POINTER_REGNUM)
415 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
417 /* ??? We can't scan past the end of a basic block without updating
418 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
419 if (perhaps_ends_bb_p (p))
421 else if (! INSN_P (p))
424 if (reg_set_p (src, p) || reg_set_p (dest, p)
425 /* If SRC is an asm-declared register, it must not be replaced
426 in any asm. Unfortunately, the REG_EXPR tree for the asm
427 variable may be absent in the SRC rtx, so we can't check the
428 actual register declaration easily (the asm operand will have
429 it, though). To avoid complicating the test for a rare case,
430 we just don't perform register replacement for a hard reg
431 mentioned in an asm. */
432 || (sregno < FIRST_PSEUDO_REGISTER
433 && asm_noperands (PATTERN (p)) >= 0
434 && reg_overlap_mentioned_p (src, PATTERN (p)))
435 /* Don't change a USE of a register. */
436 || (GET_CODE (PATTERN (p)) == USE
437 && reg_overlap_mentioned_p (src, XEXP (PATTERN (p), 0))))
440 /* See if all of SRC dies in P. This test is slightly more
441 conservative than it needs to be. */
442 if ((note = find_regno_note (p, REG_DEAD, sregno)) != 0
443 && GET_MODE (XEXP (note, 0)) == GET_MODE (src))
451 /* We can do the optimization. Scan forward from INSN again,
452 replacing regs as we go. Set FAILED if a replacement can't
453 be done. In that case, we can't move the death note for SRC.
454 This should be rare. */
456 /* Set to stop at next insn. */
457 for (q = next_real_insn (insn);
458 q != next_real_insn (p);
459 q = next_real_insn (q))
461 if (reg_overlap_mentioned_p (src, PATTERN (q)))
463 /* If SRC is a hard register, we might miss some
464 overlapping registers with validate_replace_rtx,
465 so we would have to undo it. We can't if DEST is
466 present in the insn, so fail in that combination
468 if (sregno < FIRST_PSEUDO_REGISTER
469 && reg_mentioned_p (dest, PATTERN (q)))
472 /* Replace all uses and make sure that the register
473 isn't still present. */
474 else if (validate_replace_rtx (src, dest, q)
475 && (sregno >= FIRST_PSEUDO_REGISTER
476 || ! reg_overlap_mentioned_p (src,
481 validate_replace_rtx (dest, src, q);
486 /* For SREGNO, count the total number of insns scanned.
487 For DREGNO, count the total number of insns scanned after
488 passing the death note for DREGNO. */
493 /* If the insn in which SRC dies is a CALL_INSN, don't count it
494 as a call that has been crossed. Otherwise, count it. */
495 if (q != p && GET_CODE (q) == CALL_INSN)
497 /* Similarly, total calls for SREGNO, total calls beyond
498 the death note for DREGNO. */
504 /* If DEST dies here, remove the death note and save it for
505 later. Make sure ALL of DEST dies here; again, this is
506 overly conservative. */
508 && (dest_death = find_regno_note (q, REG_DEAD, dregno)) != 0)
510 if (GET_MODE (XEXP (dest_death, 0)) != GET_MODE (dest))
511 failed = 1, dest_death = 0;
513 remove_note (q, dest_death);
519 /* These counters need to be updated if and only if we are
520 going to move the REG_DEAD note. */
521 if (sregno >= FIRST_PSEUDO_REGISTER)
523 if (REG_LIVE_LENGTH (sregno) >= 0)
525 REG_LIVE_LENGTH (sregno) -= s_length;
526 /* REG_LIVE_LENGTH is only an approximation after
527 combine if sched is not run, so make sure that we
528 still have a reasonable value. */
529 if (REG_LIVE_LENGTH (sregno) < 2)
530 REG_LIVE_LENGTH (sregno) = 2;
533 REG_N_CALLS_CROSSED (sregno) -= s_n_calls;
536 /* Move death note of SRC from P to INSN. */
537 remove_note (p, note);
538 XEXP (note, 1) = REG_NOTES (insn);
539 REG_NOTES (insn) = note;
542 /* DEST is also dead if INSN has a REG_UNUSED note for DEST. */
544 && (dest_death = find_regno_note (insn, REG_UNUSED, dregno)))
546 PUT_REG_NOTE_KIND (dest_death, REG_DEAD);
547 remove_note (insn, dest_death);
550 /* Put death note of DEST on P if we saw it die. */
553 XEXP (dest_death, 1) = REG_NOTES (p);
554 REG_NOTES (p) = dest_death;
556 if (dregno >= FIRST_PSEUDO_REGISTER)
558 /* If and only if we are moving the death note for DREGNO,
559 then we need to update its counters. */
560 if (REG_LIVE_LENGTH (dregno) >= 0)
561 REG_LIVE_LENGTH (dregno) += d_length;
562 REG_N_CALLS_CROSSED (dregno) += d_n_calls;
569 /* If SRC is a hard register which is set or killed in some other
570 way, we can't do this optimization. */
571 else if (sregno < FIRST_PSEUDO_REGISTER
572 && dead_or_set_p (p, src))
578 /* INSN is a copy of SRC to DEST, in which SRC dies. See if we now have
579 a sequence of insns that modify DEST followed by an insn that sets
580 SRC to DEST in which DEST dies, with no prior modification of DEST.
581 (There is no need to check if the insns in between actually modify
582 DEST. We should not have cases where DEST is not modified, but
583 the optimization is safe if no such modification is detected.)
584 In that case, we can replace all uses of DEST, starting with INSN and
585 ending with the set of SRC to DEST, with SRC. We do not do this
586 optimization if a CALL_INSN is crossed unless SRC already crosses a
587 call or if DEST dies before the copy back to SRC.
589 It is assumed that DEST and SRC are pseudos; it is too complicated to do
590 this for hard registers since the substitutions we may make might fail. */
593 optimize_reg_copy_2 (rtx insn, rtx dest, rtx src)
597 int sregno = REGNO (src);
598 int dregno = REGNO (dest);
600 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
602 /* ??? We can't scan past the end of a basic block without updating
603 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
604 if (perhaps_ends_bb_p (p))
606 else if (! INSN_P (p))
609 set = single_set (p);
610 if (set && SET_SRC (set) == dest && SET_DEST (set) == src
611 && find_reg_note (p, REG_DEAD, dest))
613 /* We can do the optimization. Scan forward from INSN again,
614 replacing regs as we go. */
616 /* Set to stop at next insn. */
617 for (q = insn; q != NEXT_INSN (p); q = NEXT_INSN (q))
620 if (reg_mentioned_p (dest, PATTERN (q)))
621 PATTERN (q) = replace_rtx (PATTERN (q), dest, src);
624 if (GET_CODE (q) == CALL_INSN)
626 REG_N_CALLS_CROSSED (dregno)--;
627 REG_N_CALLS_CROSSED (sregno)++;
631 remove_note (p, find_reg_note (p, REG_DEAD, dest));
632 REG_N_DEATHS (dregno)--;
633 remove_note (insn, find_reg_note (insn, REG_DEAD, src));
634 REG_N_DEATHS (sregno)--;
638 if (reg_set_p (src, p)
639 || find_reg_note (p, REG_DEAD, dest)
640 || (GET_CODE (p) == CALL_INSN && REG_N_CALLS_CROSSED (sregno) == 0))
644 /* INSN is a ZERO_EXTEND or SIGN_EXTEND of SRC to DEST.
645 Look if SRC dies there, and if it is only set once, by loading
646 it from memory. If so, try to incorporate the zero/sign extension
647 into the memory read, change SRC to the mode of DEST, and alter
648 the remaining accesses to use the appropriate SUBREG. This allows
649 SRC and DEST to be tied later. */
651 optimize_reg_copy_3 (rtx insn, rtx dest, rtx src)
653 rtx src_reg = XEXP (src, 0);
654 int src_no = REGNO (src_reg);
655 int dst_no = REGNO (dest);
657 enum machine_mode old_mode;
659 if (src_no < FIRST_PSEUDO_REGISTER
660 || dst_no < FIRST_PSEUDO_REGISTER
661 || ! find_reg_note (insn, REG_DEAD, src_reg)
662 || REG_N_DEATHS (src_no) != 1
663 || REG_N_SETS (src_no) != 1)
665 for (p = PREV_INSN (insn); p && ! reg_set_p (src_reg, p); p = PREV_INSN (p))
666 /* ??? We can't scan past the end of a basic block without updating
667 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
668 if (perhaps_ends_bb_p (p))
674 if (! (set = single_set (p))
675 || GET_CODE (SET_SRC (set)) != MEM
676 /* If there's a REG_EQUIV note, this must be an insn that loads an
677 argument. Prefer keeping the note over doing this optimization. */
678 || find_reg_note (p, REG_EQUIV, NULL_RTX)
679 || SET_DEST (set) != src_reg)
682 /* Be conservative: although this optimization is also valid for
683 volatile memory references, that could cause trouble in later passes. */
684 if (MEM_VOLATILE_P (SET_SRC (set)))
687 /* Do not use a SUBREG to truncate from one mode to another if truncation
689 if (GET_MODE_BITSIZE (GET_MODE (src_reg)) <= GET_MODE_BITSIZE (GET_MODE (src))
690 && !TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (GET_MODE (src)),
691 GET_MODE_BITSIZE (GET_MODE (src_reg))))
694 old_mode = GET_MODE (src_reg);
695 PUT_MODE (src_reg, GET_MODE (src));
696 XEXP (src, 0) = SET_SRC (set);
698 /* Include this change in the group so that it's easily undone if
699 one of the changes in the group is invalid. */
700 validate_change (p, &SET_SRC (set), src, 1);
702 /* Now walk forward making additional replacements. We want to be able
703 to undo all the changes if a later substitution fails. */
704 subreg = gen_lowpart_SUBREG (old_mode, src_reg);
705 while (p = NEXT_INSN (p), p != insn)
710 /* Make a tenative change. */
711 validate_replace_rtx_group (src_reg, subreg, p);
714 validate_replace_rtx_group (src, src_reg, insn);
716 /* Now see if all the changes are valid. */
717 if (! apply_change_group ())
719 /* One or more changes were no good. Back out everything. */
720 PUT_MODE (src_reg, old_mode);
721 XEXP (src, 0) = src_reg;
725 rtx note = find_reg_note (p, REG_EQUAL, NULL_RTX);
727 remove_note (p, note);
732 /* If we were not able to update the users of src to use dest directly, try
733 instead moving the value to dest directly before the operation. */
736 copy_src_to_dest (rtx insn, rtx src, rtx dest, int old_max_uid)
751 /* A REG_LIVE_LENGTH of -1 indicates the register is equivalent to a constant
752 or memory location and is used infrequently; a REG_LIVE_LENGTH of -2 is
753 parameter when there is no frame pointer that is not allocated a register.
754 For now, we just reject them, rather than incrementing the live length. */
756 if (GET_CODE (src) == REG
757 && REG_LIVE_LENGTH (REGNO (src)) > 0
758 && GET_CODE (dest) == REG
759 && !RTX_UNCHANGING_P (dest)
760 && REG_LIVE_LENGTH (REGNO (dest)) > 0
761 && (set = single_set (insn)) != NULL_RTX
762 && !reg_mentioned_p (dest, SET_SRC (set))
763 && GET_MODE (src) == GET_MODE (dest))
765 int old_num_regs = reg_rtx_no;
767 /* Generate the src->dest move. */
769 emit_move_insn (dest, src);
772 /* If this sequence uses new registers, we may not use it. */
773 if (old_num_regs != reg_rtx_no
774 || ! validate_replace_rtx (src, dest, insn))
776 /* We have to restore reg_rtx_no to its old value, lest
777 recompute_reg_usage will try to compute the usage of the
778 new regs, yet reg_n_info is not valid for them. */
779 reg_rtx_no = old_num_regs;
782 emit_insn_before (seq, insn);
783 move_insn = PREV_INSN (insn);
784 p_move_notes = ®_NOTES (move_insn);
785 p_insn_notes = ®_NOTES (insn);
787 /* Move any notes mentioning src to the move instruction. */
788 for (link = REG_NOTES (insn); link != NULL_RTX; link = next)
790 next = XEXP (link, 1);
791 if (XEXP (link, 0) == src)
793 *p_move_notes = link;
794 p_move_notes = &XEXP (link, 1);
798 *p_insn_notes = link;
799 p_insn_notes = &XEXP (link, 1);
803 *p_move_notes = NULL_RTX;
804 *p_insn_notes = NULL_RTX;
806 /* Is the insn the head of a basic block? If so extend it. */
807 insn_uid = INSN_UID (insn);
808 move_uid = INSN_UID (move_insn);
809 if (insn_uid < old_max_uid)
811 bb = regmove_bb_head[insn_uid];
814 BLOCK_HEAD (bb) = move_insn;
815 regmove_bb_head[insn_uid] = -1;
819 /* Update the various register tables. */
820 dest_regno = REGNO (dest);
821 REG_N_SETS (dest_regno) ++;
822 REG_LIVE_LENGTH (dest_regno)++;
823 if (REGNO_FIRST_UID (dest_regno) == insn_uid)
824 REGNO_FIRST_UID (dest_regno) = move_uid;
826 src_regno = REGNO (src);
827 if (! find_reg_note (move_insn, REG_DEAD, src))
828 REG_LIVE_LENGTH (src_regno)++;
830 if (REGNO_FIRST_UID (src_regno) == insn_uid)
831 REGNO_FIRST_UID (src_regno) = move_uid;
833 if (REGNO_LAST_UID (src_regno) == insn_uid)
834 REGNO_LAST_UID (src_regno) = move_uid;
836 if (REGNO_LAST_NOTE_UID (src_regno) == insn_uid)
837 REGNO_LAST_NOTE_UID (src_regno) = move_uid;
842 /* Return whether REG is set in only one location, and is set to a
843 constant, but is set in a different basic block from INSN (an
844 instructions which uses REG). In this case REG is equivalent to a
845 constant, and we don't want to break that equivalence, because that
846 may increase register pressure and make reload harder. If REG is
847 set in the same basic block as INSN, we don't worry about it,
848 because we'll probably need a register anyhow (??? but what if REG
849 is used in a different basic block as well as this one?). FIRST is
850 the first insn in the function. */
853 reg_is_remote_constant_p (rtx reg, rtx insn, rtx first)
857 if (REG_N_SETS (REGNO (reg)) != 1)
860 /* Look for the set. */
861 for (p = LOG_LINKS (insn); p; p = XEXP (p, 1))
865 if (REG_NOTE_KIND (p) != 0)
867 s = single_set (XEXP (p, 0));
869 && GET_CODE (SET_DEST (s)) == REG
870 && REGNO (SET_DEST (s)) == REGNO (reg))
872 /* The register is set in the same basic block. */
877 for (p = first; p && p != insn; p = NEXT_INSN (p))
885 && GET_CODE (SET_DEST (s)) == REG
886 && REGNO (SET_DEST (s)) == REGNO (reg))
888 /* This is the instruction which sets REG. If there is a
889 REG_EQUAL note, then REG is equivalent to a constant. */
890 if (find_reg_note (p, REG_EQUAL, NULL_RTX))
899 /* INSN is adding a CONST_INT to a REG. We search backwards looking for
900 another add immediate instruction with the same source and dest registers,
901 and if we find one, we change INSN to an increment, and return 1. If
902 no changes are made, we return 0.
905 (set (reg100) (plus reg1 offset1))
907 (set (reg100) (plus reg1 offset2))
909 (set (reg100) (plus reg1 offset1))
911 (set (reg100) (plus reg100 offset2-offset1)) */
913 /* ??? What does this comment mean? */
914 /* cse disrupts preincrement / postdecrement sequences when it finds a
915 hard register as ultimate source, like the frame pointer. */
918 fixup_match_2 (rtx insn, rtx dst, rtx src, rtx offset, FILE *regmove_dump_file)
920 rtx p, dst_death = 0;
921 int length, num_calls = 0;
923 /* If SRC dies in INSN, we'd have to move the death note. This is
924 considered to be very unlikely, so we just skip the optimization
926 if (find_regno_note (insn, REG_DEAD, REGNO (src)))
929 /* Scan backward to find the first instruction that sets DST. */
931 for (length = 0, p = PREV_INSN (insn); p; p = PREV_INSN (p))
935 /* ??? We can't scan past the end of a basic block without updating
936 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
937 if (perhaps_ends_bb_p (p))
939 else if (! INSN_P (p))
942 if (find_regno_note (p, REG_DEAD, REGNO (dst)))
947 pset = single_set (p);
948 if (pset && SET_DEST (pset) == dst
949 && GET_CODE (SET_SRC (pset)) == PLUS
950 && XEXP (SET_SRC (pset), 0) == src
951 && GET_CODE (XEXP (SET_SRC (pset), 1)) == CONST_INT)
953 HOST_WIDE_INT newconst
954 = INTVAL (offset) - INTVAL (XEXP (SET_SRC (pset), 1));
955 rtx add = gen_add3_insn (dst, dst, GEN_INT (newconst));
957 if (add && validate_change (insn, &PATTERN (insn), add, 0))
959 /* Remove the death note for DST from DST_DEATH. */
962 remove_death (REGNO (dst), dst_death);
963 REG_LIVE_LENGTH (REGNO (dst)) += length;
964 REG_N_CALLS_CROSSED (REGNO (dst)) += num_calls;
967 if (regmove_dump_file)
968 fprintf (regmove_dump_file,
969 "Fixed operand of insn %d.\n",
973 for (p = PREV_INSN (insn); p; p = PREV_INSN (p))
975 if (GET_CODE (p) == CODE_LABEL
976 || GET_CODE (p) == JUMP_INSN)
980 if (reg_overlap_mentioned_p (dst, PATTERN (p)))
982 if (try_auto_increment (p, insn, 0, dst, newconst, 0))
987 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
989 if (GET_CODE (p) == CODE_LABEL
990 || GET_CODE (p) == JUMP_INSN)
994 if (reg_overlap_mentioned_p (dst, PATTERN (p)))
996 try_auto_increment (p, insn, 0, dst, newconst, 1);
1005 if (reg_set_p (dst, PATTERN (p)))
1008 /* If we have passed a call instruction, and the
1009 pseudo-reg SRC is not already live across a call,
1010 then don't perform the optimization. */
1011 /* reg_set_p is overly conservative for CALL_INSNS, thinks that all
1012 hard regs are clobbered. Thus, we only use it for src for
1014 if (GET_CODE (p) == CALL_INSN)
1019 if (REG_N_CALLS_CROSSED (REGNO (src)) == 0)
1022 if (call_used_regs [REGNO (dst)]
1023 || find_reg_fusage (p, CLOBBER, dst))
1026 else if (reg_set_p (src, PATTERN (p)))
1033 /* Main entry for the register move optimization.
1034 F is the first instruction.
1035 NREGS is one plus the highest pseudo-reg number used in the instruction.
1036 REGMOVE_DUMP_FILE is a stream for output of a trace of actions taken
1037 (or 0 if none should be output). */
1040 regmove_optimize (rtx f, int nregs, FILE *regmove_dump_file)
1042 int old_max_uid = get_max_uid ();
1047 rtx copy_src, copy_dst;
1050 /* ??? Hack. Regmove doesn't examine the CFG, and gets mightily
1051 confused by non-call exceptions ending blocks. */
1052 if (flag_non_call_exceptions)
1055 /* Find out where a potential flags register is live, and so that we
1056 can suppress some optimizations in those zones. */
1057 mark_flags_life_zones (discover_flags_reg ());
1059 regno_src_regno = (int *) xmalloc (sizeof *regno_src_regno * nregs);
1060 for (i = nregs; --i >= 0; ) regno_src_regno[i] = -1;
1062 regmove_bb_head = (int *) xmalloc (sizeof (int) * (old_max_uid + 1));
1063 for (i = old_max_uid; i >= 0; i--) regmove_bb_head[i] = -1;
1065 regmove_bb_head[INSN_UID (bb->head)] = bb->index;
1067 /* A forward/backward pass. Replace output operands with input operands. */
1069 for (pass = 0; pass <= 2; pass++)
1071 if (! flag_regmove && pass >= flag_expensive_optimizations)
1074 if (regmove_dump_file)
1075 fprintf (regmove_dump_file, "Starting %s pass...\n",
1076 pass ? "backward" : "forward");
1078 for (insn = pass ? get_last_insn () : f; insn;
1079 insn = pass ? PREV_INSN (insn) : NEXT_INSN (insn))
1082 int op_no, match_no;
1084 set = single_set (insn);
1088 if (flag_expensive_optimizations && ! pass
1089 && (GET_CODE (SET_SRC (set)) == SIGN_EXTEND
1090 || GET_CODE (SET_SRC (set)) == ZERO_EXTEND)
1091 && GET_CODE (XEXP (SET_SRC (set), 0)) == REG
1092 && GET_CODE (SET_DEST (set)) == REG)
1093 optimize_reg_copy_3 (insn, SET_DEST (set), SET_SRC (set));
1095 if (flag_expensive_optimizations && ! pass
1096 && GET_CODE (SET_SRC (set)) == REG
1097 && GET_CODE (SET_DEST (set)) == REG)
1099 /* If this is a register-register copy where SRC is not dead,
1100 see if we can optimize it. If this optimization succeeds,
1101 it will become a copy where SRC is dead. */
1102 if ((find_reg_note (insn, REG_DEAD, SET_SRC (set))
1103 || optimize_reg_copy_1 (insn, SET_DEST (set), SET_SRC (set)))
1104 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
1106 /* Similarly for a pseudo-pseudo copy when SRC is dead. */
1107 if (REGNO (SET_SRC (set)) >= FIRST_PSEUDO_REGISTER)
1108 optimize_reg_copy_2 (insn, SET_DEST (set), SET_SRC (set));
1109 if (regno_src_regno[REGNO (SET_DEST (set))] < 0
1110 && SET_SRC (set) != SET_DEST (set))
1112 int srcregno = REGNO (SET_SRC (set));
1113 if (regno_src_regno[srcregno] >= 0)
1114 srcregno = regno_src_regno[srcregno];
1115 regno_src_regno[REGNO (SET_DEST (set))] = srcregno;
1122 if (! find_matches (insn, &match))
1125 /* Now scan through the operands looking for a source operand
1126 which is supposed to match the destination operand.
1127 Then scan forward for an instruction which uses the dest
1129 If it dies there, then replace the dest in both operands with
1130 the source operand. */
1132 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1134 rtx src, dst, src_subreg;
1135 enum reg_class src_class, dst_class;
1137 match_no = match.with[op_no];
1139 /* Nothing to do if the two operands aren't supposed to match. */
1143 src = recog_data.operand[op_no];
1144 dst = recog_data.operand[match_no];
1146 if (GET_CODE (src) != REG)
1150 if (GET_CODE (dst) == SUBREG
1151 && GET_MODE_SIZE (GET_MODE (dst))
1152 >= GET_MODE_SIZE (GET_MODE (SUBREG_REG (dst))))
1155 = gen_rtx_SUBREG (GET_MODE (SUBREG_REG (dst)),
1156 src, SUBREG_BYTE (dst));
1157 dst = SUBREG_REG (dst);
1159 if (GET_CODE (dst) != REG
1160 || REGNO (dst) < FIRST_PSEUDO_REGISTER)
1163 if (REGNO (src) < FIRST_PSEUDO_REGISTER)
1165 if (match.commutative[op_no] < op_no)
1166 regno_src_regno[REGNO (dst)] = REGNO (src);
1170 if (REG_LIVE_LENGTH (REGNO (src)) < 0)
1173 /* op_no/src must be a read-only operand, and
1174 match_operand/dst must be a write-only operand. */
1175 if (match.use[op_no] != READ
1176 || match.use[match_no] != WRITE)
1179 if (match.early_clobber[match_no]
1180 && count_occurrences (PATTERN (insn), src, 0) > 1)
1183 /* Make sure match_operand is the destination. */
1184 if (recog_data.operand[match_no] != SET_DEST (set))
1187 /* If the operands already match, then there is nothing to do. */
1188 if (operands_match_p (src, dst))
1191 /* But in the commutative case, we might find a better match. */
1192 if (match.commutative[op_no] >= 0)
1194 rtx comm = recog_data.operand[match.commutative[op_no]];
1195 if (operands_match_p (comm, dst)
1196 && (replacement_quality (comm)
1197 >= replacement_quality (src)))
1201 src_class = reg_preferred_class (REGNO (src));
1202 dst_class = reg_preferred_class (REGNO (dst));
1203 if (! regclass_compatible_p (src_class, dst_class))
1206 if (GET_MODE (src) != GET_MODE (dst))
1209 if (fixup_match_1 (insn, set, src, src_subreg, dst, pass,
1217 /* A backward pass. Replace input operands with output operands. */
1219 if (regmove_dump_file)
1220 fprintf (regmove_dump_file, "Starting backward pass...\n");
1222 for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
1226 int op_no, match_no;
1229 if (! find_matches (insn, &match))
1232 /* Now scan through the operands looking for a destination operand
1233 which is supposed to match a source operand.
1234 Then scan backward for an instruction which sets the source
1235 operand. If safe, then replace the source operand with the
1236 dest operand in both instructions. */
1238 copy_src = NULL_RTX;
1239 copy_dst = NULL_RTX;
1240 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1242 rtx set, p, src, dst;
1243 rtx src_note, dst_note;
1245 enum reg_class src_class, dst_class;
1248 match_no = match.with[op_no];
1250 /* Nothing to do if the two operands aren't supposed to match. */
1254 dst = recog_data.operand[match_no];
1255 src = recog_data.operand[op_no];
1257 if (GET_CODE (src) != REG)
1260 if (GET_CODE (dst) != REG
1261 || REGNO (dst) < FIRST_PSEUDO_REGISTER
1262 || REG_LIVE_LENGTH (REGNO (dst)) < 0
1263 || RTX_UNCHANGING_P (dst)
1264 || GET_MODE (src) != GET_MODE (dst))
1267 /* If the operands already match, then there is nothing to do. */
1268 if (operands_match_p (src, dst))
1271 if (match.commutative[op_no] >= 0)
1273 rtx comm = recog_data.operand[match.commutative[op_no]];
1274 if (operands_match_p (comm, dst))
1278 set = single_set (insn);
1282 /* Note that single_set ignores parts of a parallel set for
1283 which one of the destinations is REG_UNUSED. We can't
1284 handle that here, since we can wind up rewriting things
1285 such that a single register is set twice within a single
1287 if (reg_set_p (src, insn))
1290 /* match_no/dst must be a write-only operand, and
1291 operand_operand/src must be a read-only operand. */
1292 if (match.use[op_no] != READ
1293 || match.use[match_no] != WRITE)
1296 if (match.early_clobber[match_no]
1297 && count_occurrences (PATTERN (insn), src, 0) > 1)
1300 /* Make sure match_no is the destination. */
1301 if (recog_data.operand[match_no] != SET_DEST (set))
1304 if (REGNO (src) < FIRST_PSEUDO_REGISTER)
1306 if (GET_CODE (SET_SRC (set)) == PLUS
1307 && GET_CODE (XEXP (SET_SRC (set), 1)) == CONST_INT
1308 && XEXP (SET_SRC (set), 0) == src
1309 && fixup_match_2 (insn, dst, src,
1310 XEXP (SET_SRC (set), 1),
1315 src_class = reg_preferred_class (REGNO (src));
1316 dst_class = reg_preferred_class (REGNO (dst));
1318 if (! (src_note = find_reg_note (insn, REG_DEAD, src)))
1320 /* We used to force the copy here like in other cases, but
1321 it produces worse code, as it eliminates no copy
1322 instructions and the copy emitted will be produced by
1323 reload anyway. On patterns with multiple alternatives,
1324 there may be better solution available.
1326 In particular this change produced slower code for numeric
1332 if (! regclass_compatible_p (src_class, dst_class))
1342 /* Can not modify an earlier insn to set dst if this insn
1343 uses an old value in the source. */
1344 if (reg_overlap_mentioned_p (dst, SET_SRC (set)))
1354 /* If src is set once in a different basic block,
1355 and is set equal to a constant, then do not use
1356 it for this optimization, as this would make it
1357 no longer equivalent to a constant. */
1359 if (reg_is_remote_constant_p (src, insn, f))
1370 if (regmove_dump_file)
1371 fprintf (regmove_dump_file,
1372 "Could fix operand %d of insn %d matching operand %d.\n",
1373 op_no, INSN_UID (insn), match_no);
1375 /* Scan backward to find the first instruction that uses
1376 the input operand. If the operand is set here, then
1377 replace it in both instructions with match_no. */
1379 for (length = 0, p = PREV_INSN (insn); p; p = PREV_INSN (p))
1383 /* ??? We can't scan past the end of a basic block without
1384 updating the register lifetime info
1385 (REG_DEAD/basic_block_live_at_start). */
1386 if (perhaps_ends_bb_p (p))
1388 else if (! INSN_P (p))
1393 /* ??? See if all of SRC is set in P. This test is much
1394 more conservative than it needs to be. */
1395 pset = single_set (p);
1396 if (pset && SET_DEST (pset) == src)
1398 /* We use validate_replace_rtx, in case there
1399 are multiple identical source operands. All of
1400 them have to be changed at the same time. */
1401 if (validate_replace_rtx (src, dst, insn))
1403 if (validate_change (p, &SET_DEST (pset),
1408 /* Change all source operands back.
1409 This modifies the dst as a side-effect. */
1410 validate_replace_rtx (dst, src, insn);
1411 /* Now make sure the dst is right. */
1412 validate_change (insn,
1413 recog_data.operand_loc[match_no],
1420 if (reg_overlap_mentioned_p (src, PATTERN (p))
1421 || reg_overlap_mentioned_p (dst, PATTERN (p)))
1424 /* If we have passed a call instruction, and the
1425 pseudo-reg DST is not already live across a call,
1426 then don't perform the optimization. */
1427 if (GET_CODE (p) == CALL_INSN)
1431 if (REG_N_CALLS_CROSSED (REGNO (dst)) == 0)
1440 /* Remove the death note for SRC from INSN. */
1441 remove_note (insn, src_note);
1442 /* Move the death note for SRC to P if it is used
1444 if (reg_overlap_mentioned_p (src, PATTERN (p)))
1446 XEXP (src_note, 1) = REG_NOTES (p);
1447 REG_NOTES (p) = src_note;
1449 /* If there is a REG_DEAD note for DST on P, then remove
1450 it, because DST is now set there. */
1451 if ((dst_note = find_reg_note (p, REG_DEAD, dst)))
1452 remove_note (p, dst_note);
1454 dstno = REGNO (dst);
1455 srcno = REGNO (src);
1457 REG_N_SETS (dstno)++;
1458 REG_N_SETS (srcno)--;
1460 REG_N_CALLS_CROSSED (dstno) += num_calls;
1461 REG_N_CALLS_CROSSED (srcno) -= num_calls;
1463 REG_LIVE_LENGTH (dstno) += length;
1464 if (REG_LIVE_LENGTH (srcno) >= 0)
1466 REG_LIVE_LENGTH (srcno) -= length;
1467 /* REG_LIVE_LENGTH is only an approximation after
1468 combine if sched is not run, so make sure that we
1469 still have a reasonable value. */
1470 if (REG_LIVE_LENGTH (srcno) < 2)
1471 REG_LIVE_LENGTH (srcno) = 2;
1474 if (regmove_dump_file)
1475 fprintf (regmove_dump_file,
1476 "Fixed operand %d of insn %d matching operand %d.\n",
1477 op_no, INSN_UID (insn), match_no);
1483 /* If we weren't able to replace any of the alternatives, try an
1484 alternative approach of copying the source to the destination. */
1485 if (!success && copy_src != NULL_RTX)
1486 copy_src_to_dest (insn, copy_src, copy_dst, old_max_uid);
1491 /* In fixup_match_1, some insns may have been inserted after basic block
1492 ends. Fix that here. */
1497 rtx next = NEXT_INSN (new);
1498 while (next != 0 && INSN_UID (next) >= old_max_uid
1499 && (bb->next_bb == EXIT_BLOCK_PTR || bb->next_bb->head != next))
1500 new = next, next = NEXT_INSN (new);
1506 free (regno_src_regno);
1507 free (regmove_bb_head);
1510 /* Returns nonzero if INSN's pattern has matching constraints for any operand.
1511 Returns 0 if INSN can't be recognized, or if the alternative can't be
1514 Initialize the info in MATCHP based on the constraints. */
1517 find_matches (rtx insn, struct match *matchp)
1519 int likely_spilled[MAX_RECOG_OPERANDS];
1521 int any_matches = 0;
1523 extract_insn (insn);
1524 if (! constrain_operands (0))
1527 /* Must initialize this before main loop, because the code for
1528 the commutative case may set matches for operands other than
1530 for (op_no = recog_data.n_operands; --op_no >= 0; )
1531 matchp->with[op_no] = matchp->commutative[op_no] = -1;
1533 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1539 p = recog_data.constraints[op_no];
1541 likely_spilled[op_no] = 0;
1542 matchp->use[op_no] = READ;
1543 matchp->early_clobber[op_no] = 0;
1545 matchp->use[op_no] = WRITE;
1547 matchp->use[op_no] = READWRITE;
1549 for (;*p && i < which_alternative; p++)
1553 while ((c = *p) != '\0' && c != ',')
1562 matchp->early_clobber[op_no] = 1;
1565 matchp->commutative[op_no] = op_no + 1;
1566 matchp->commutative[op_no + 1] = op_no;
1569 case '0': case '1': case '2': case '3': case '4':
1570 case '5': case '6': case '7': case '8': case '9':
1573 unsigned long match_ul = strtoul (p, &end, 10);
1574 int match = match_ul;
1578 if (match < op_no && likely_spilled[match])
1580 matchp->with[op_no] = match;
1582 if (matchp->commutative[op_no] >= 0)
1583 matchp->with[matchp->commutative[op_no]] = match;
1587 case 'a': case 'b': case 'c': case 'd': case 'e': case 'f': case 'h':
1588 case 'j': case 'k': case 'l': case 'p': case 'q': case 't': case 'u':
1589 case 'v': case 'w': case 'x': case 'y': case 'z': case 'A': case 'B':
1590 case 'C': case 'D': case 'W': case 'Y': case 'Z':
1591 if (CLASS_LIKELY_SPILLED_P (REG_CLASS_FROM_CONSTRAINT ((unsigned char) c, p) ))
1592 likely_spilled[op_no] = 1;
1595 p += CONSTRAINT_LEN (c, p);
1601 /* Try to replace all occurrences of DST_REG with SRC in LOC, that is
1602 assumed to be in INSN. */
1605 replace_in_call_usage (rtx *loc, unsigned int dst_reg, rtx src, rtx insn)
1615 code = GET_CODE (x);
1618 if (REGNO (x) != dst_reg)
1621 validate_change (insn, loc, src, 1);
1626 /* Process each of our operands recursively. */
1627 fmt = GET_RTX_FORMAT (code);
1628 for (i = 0; i < GET_RTX_LENGTH (code); i++, fmt++)
1630 replace_in_call_usage (&XEXP (x, i), dst_reg, src, insn);
1631 else if (*fmt == 'E')
1632 for (j = 0; j < XVECLEN (x, i); j++)
1633 replace_in_call_usage (& XVECEXP (x, i, j), dst_reg, src, insn);
1636 /* Try to replace output operand DST in SET, with input operand SRC. SET is
1637 the only set in INSN. INSN has just been recognized and constrained.
1638 SRC is operand number OPERAND_NUMBER in INSN.
1639 DST is operand number MATCH_NUMBER in INSN.
1640 If BACKWARD is nonzero, we have been called in a backward pass.
1641 Return nonzero for success. */
1644 fixup_match_1 (rtx insn, rtx set, rtx src, rtx src_subreg, rtx dst,
1645 int backward, int operand_number, int match_number,
1646 FILE *regmove_dump_file)
1649 rtx post_inc = 0, post_inc_set = 0, search_end = 0;
1651 int num_calls = 0, s_num_calls = 0;
1652 enum rtx_code code = NOTE;
1653 HOST_WIDE_INT insn_const = 0, newconst = 0;
1654 rtx overlap = 0; /* need to move insn ? */
1655 rtx src_note = find_reg_note (insn, REG_DEAD, src), dst_note = NULL_RTX;
1656 int length, s_length;
1658 /* If SRC is marked as unchanging, we may not change it.
1659 ??? Maybe we could get better code by removing the unchanging bit
1660 instead, and changing it back if we don't succeed? */
1661 if (RTX_UNCHANGING_P (src))
1666 /* Look for (set (regX) (op regA constX))
1667 (set (regY) (op regA constY))
1669 (set (regA) (op regA constX)).
1670 (set (regY) (op regA constY-constX)).
1671 This works for add and shift operations, if
1672 regA is dead after or set by the second insn. */
1674 code = GET_CODE (SET_SRC (set));
1675 if ((code == PLUS || code == LSHIFTRT
1676 || code == ASHIFT || code == ASHIFTRT)
1677 && XEXP (SET_SRC (set), 0) == src
1678 && GET_CODE (XEXP (SET_SRC (set), 1)) == CONST_INT)
1679 insn_const = INTVAL (XEXP (SET_SRC (set), 1));
1680 else if (! stable_and_no_regs_but_for_p (SET_SRC (set), src, dst))
1683 /* We might find a src_note while scanning. */
1687 if (regmove_dump_file)
1688 fprintf (regmove_dump_file,
1689 "Could fix operand %d of insn %d matching operand %d.\n",
1690 operand_number, INSN_UID (insn), match_number);
1692 /* If SRC is equivalent to a constant set in a different basic block,
1693 then do not use it for this optimization. We want the equivalence
1694 so that if we have to reload this register, we can reload the
1695 constant, rather than extending the lifespan of the register. */
1696 if (reg_is_remote_constant_p (src, insn, get_insns ()))
1699 /* Scan forward to find the next instruction that
1700 uses the output operand. If the operand dies here,
1701 then replace it in both instructions with
1704 for (length = s_length = 0, p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
1706 if (GET_CODE (p) == CALL_INSN)
1707 replace_in_call_usage (& CALL_INSN_FUNCTION_USAGE (p),
1708 REGNO (dst), src, p);
1710 /* ??? We can't scan past the end of a basic block without updating
1711 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
1712 if (perhaps_ends_bb_p (p))
1714 else if (! INSN_P (p))
1721 if (reg_set_p (src, p) || reg_set_p (dst, p)
1722 || (GET_CODE (PATTERN (p)) == USE
1723 && reg_overlap_mentioned_p (src, XEXP (PATTERN (p), 0))))
1726 /* See if all of DST dies in P. This test is
1727 slightly more conservative than it needs to be. */
1728 if ((dst_note = find_regno_note (p, REG_DEAD, REGNO (dst)))
1729 && (GET_MODE (XEXP (dst_note, 0)) == GET_MODE (dst)))
1731 /* If we would be moving INSN, check that we won't move it
1732 into the shadow of a live a live flags register. */
1733 /* ??? We only try to move it in front of P, although
1734 we could move it anywhere between OVERLAP and P. */
1735 if (overlap && GET_MODE (PREV_INSN (p)) != VOIDmode)
1741 rtx set2 = NULL_RTX;
1743 /* If an optimization is done, the value of SRC while P
1744 is executed will be changed. Check that this is OK. */
1745 if (reg_overlap_mentioned_p (src, PATTERN (p)))
1747 for (q = p; q; q = NEXT_INSN (q))
1749 /* ??? We can't scan past the end of a basic block without
1750 updating the register lifetime info
1751 (REG_DEAD/basic_block_live_at_start). */
1752 if (perhaps_ends_bb_p (q))
1757 else if (! INSN_P (q))
1759 else if (reg_overlap_mentioned_p (src, PATTERN (q))
1760 || reg_set_p (src, q))
1764 set2 = single_set (q);
1765 if (! q || ! set2 || GET_CODE (SET_SRC (set2)) != code
1766 || XEXP (SET_SRC (set2), 0) != src
1767 || GET_CODE (XEXP (SET_SRC (set2), 1)) != CONST_INT
1768 || (SET_DEST (set2) != src
1769 && ! find_reg_note (q, REG_DEAD, src)))
1771 /* If this is a PLUS, we can still save a register by doing
1774 src -= insn_const; .
1775 This also gives opportunities for subsequent
1776 optimizations in the backward pass, so do it there. */
1777 if (code == PLUS && backward
1778 /* Don't do this if we can likely tie DST to SET_DEST
1779 of P later; we can't do this tying here if we got a
1781 && ! (dst_note && ! REG_N_CALLS_CROSSED (REGNO (dst))
1783 && GET_CODE (SET_DEST (single_set (p))) == REG
1784 && (REGNO (SET_DEST (single_set (p)))
1785 < FIRST_PSEUDO_REGISTER))
1786 /* We may only emit an insn directly after P if we
1787 are not in the shadow of a live flags register. */
1788 && GET_MODE (p) == VOIDmode)
1793 newconst = -insn_const;
1801 newconst = INTVAL (XEXP (SET_SRC (set2), 1)) - insn_const;
1802 /* Reject out of range shifts. */
1805 || ((unsigned HOST_WIDE_INT) newconst
1806 >= (GET_MODE_BITSIZE (GET_MODE
1807 (SET_SRC (set2)))))))
1812 if (SET_DEST (set2) != src)
1813 post_inc_set = set2;
1816 /* We use 1 as last argument to validate_change so that all
1817 changes are accepted or rejected together by apply_change_group
1818 when it is called by validate_replace_rtx . */
1819 validate_change (q, &XEXP (SET_SRC (set2), 1),
1820 GEN_INT (newconst), 1);
1822 validate_change (insn, recog_data.operand_loc[match_number], src, 1);
1823 if (validate_replace_rtx (dst, src_subreg, p))
1828 if (reg_overlap_mentioned_p (dst, PATTERN (p)))
1830 if (! src_note && reg_overlap_mentioned_p (src, PATTERN (p)))
1832 /* INSN was already checked to be movable wrt. the registers that it
1833 sets / uses when we found no REG_DEAD note for src on it, but it
1834 still might clobber the flags register. We'll have to check that
1835 we won't insert it into the shadow of a live flags register when
1836 we finally know where we are to move it. */
1838 src_note = find_reg_note (p, REG_DEAD, src);
1841 /* If we have passed a call instruction, and the pseudo-reg SRC is not
1842 already live across a call, then don't perform the optimization. */
1843 if (GET_CODE (p) == CALL_INSN)
1845 if (REG_N_CALLS_CROSSED (REGNO (src)) == 0)
1859 /* Remove the death note for DST from P. */
1860 remove_note (p, dst_note);
1863 post_inc = emit_insn_after (copy_rtx (PATTERN (insn)), p);
1864 if ((HAVE_PRE_INCREMENT || HAVE_PRE_DECREMENT)
1866 && try_auto_increment (search_end, post_inc, 0, src, newconst, 1))
1868 validate_change (insn, &XEXP (SET_SRC (set), 1), GEN_INT (insn_const), 0);
1869 REG_N_SETS (REGNO (src))++;
1870 REG_LIVE_LENGTH (REGNO (src))++;
1874 /* The lifetime of src and dest overlap,
1875 but we can change this by moving insn. */
1876 rtx pat = PATTERN (insn);
1878 remove_note (overlap, src_note);
1879 if ((HAVE_POST_INCREMENT || HAVE_POST_DECREMENT)
1881 && try_auto_increment (overlap, insn, 0, src, insn_const, 0))
1885 rtx notes = REG_NOTES (insn);
1887 emit_insn_after_with_line_notes (pat, PREV_INSN (p), insn);
1889 /* emit_insn_after_with_line_notes has no
1890 return value, so search for the new insn. */
1892 while (! INSN_P (insn) || PATTERN (insn) != pat)
1893 insn = PREV_INSN (insn);
1895 REG_NOTES (insn) = notes;
1898 /* Sometimes we'd generate src = const; src += n;
1899 if so, replace the instruction that set src
1900 in the first place. */
1902 if (! overlap && (code == PLUS || code == MINUS))
1904 rtx note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
1905 rtx q, set2 = NULL_RTX;
1906 int num_calls2 = 0, s_length2 = 0;
1908 if (note && CONSTANT_P (XEXP (note, 0)))
1910 for (q = PREV_INSN (insn); q; q = PREV_INSN (q))
1912 /* ??? We can't scan past the end of a basic block without
1913 updating the register lifetime info
1914 (REG_DEAD/basic_block_live_at_start). */
1915 if (perhaps_ends_bb_p (q))
1920 else if (! INSN_P (q))
1924 if (reg_set_p (src, q))
1926 set2 = single_set (q);
1929 if (reg_overlap_mentioned_p (src, PATTERN (q)))
1934 if (GET_CODE (p) == CALL_INSN)
1937 if (q && set2 && SET_DEST (set2) == src && CONSTANT_P (SET_SRC (set2))
1938 && validate_change (insn, &SET_SRC (set), XEXP (note, 0), 0))
1941 REG_N_SETS (REGNO (src))--;
1942 REG_N_CALLS_CROSSED (REGNO (src)) -= num_calls2;
1943 REG_LIVE_LENGTH (REGNO (src)) -= s_length2;
1949 if ((HAVE_PRE_INCREMENT || HAVE_PRE_DECREMENT)
1950 && (code == PLUS || code == MINUS) && insn_const
1951 && try_auto_increment (p, insn, 0, src, insn_const, 1))
1953 else if ((HAVE_POST_INCREMENT || HAVE_POST_DECREMENT)
1955 && try_auto_increment (p, post_inc, post_inc_set, src, newconst, 0))
1957 /* If post_inc still prevails, try to find an
1958 insn where it can be used as a pre-in/decrement.
1959 If code is MINUS, this was already tried. */
1960 if (post_inc && code == PLUS
1961 /* Check that newconst is likely to be usable
1962 in a pre-in/decrement before starting the search. */
1963 && ((HAVE_PRE_INCREMENT && newconst > 0 && newconst <= MOVE_MAX)
1964 || (HAVE_PRE_DECREMENT && newconst < 0 && newconst >= -MOVE_MAX))
1965 && exact_log2 (newconst))
1969 inc_dest = post_inc_set ? SET_DEST (post_inc_set) : src;
1970 for (q = post_inc; (q = NEXT_INSN (q)); )
1972 /* ??? We can't scan past the end of a basic block without updating
1973 the register lifetime info
1974 (REG_DEAD/basic_block_live_at_start). */
1975 if (perhaps_ends_bb_p (q))
1977 else if (! INSN_P (q))
1979 else if (src != inc_dest
1980 && (reg_overlap_mentioned_p (src, PATTERN (q))
1981 || reg_set_p (src, q)))
1983 else if (reg_set_p (inc_dest, q))
1985 else if (reg_overlap_mentioned_p (inc_dest, PATTERN (q)))
1987 try_auto_increment (q, post_inc,
1988 post_inc_set, inc_dest, newconst, 1);
1994 /* Move the death note for DST to INSN if it is used
1996 if (reg_overlap_mentioned_p (dst, PATTERN (insn)))
1998 XEXP (dst_note, 1) = REG_NOTES (insn);
1999 REG_NOTES (insn) = dst_note;
2004 /* Move the death note for SRC from INSN to P. */
2006 remove_note (insn, src_note);
2007 XEXP (src_note, 1) = REG_NOTES (p);
2008 REG_NOTES (p) = src_note;
2010 REG_N_CALLS_CROSSED (REGNO (src)) += s_num_calls;
2013 REG_N_SETS (REGNO (src))++;
2014 REG_N_SETS (REGNO (dst))--;
2016 REG_N_CALLS_CROSSED (REGNO (dst)) -= num_calls;
2018 REG_LIVE_LENGTH (REGNO (src)) += s_length;
2019 if (REG_LIVE_LENGTH (REGNO (dst)) >= 0)
2021 REG_LIVE_LENGTH (REGNO (dst)) -= length;
2022 /* REG_LIVE_LENGTH is only an approximation after
2023 combine if sched is not run, so make sure that we
2024 still have a reasonable value. */
2025 if (REG_LIVE_LENGTH (REGNO (dst)) < 2)
2026 REG_LIVE_LENGTH (REGNO (dst)) = 2;
2028 if (regmove_dump_file)
2029 fprintf (regmove_dump_file,
2030 "Fixed operand %d of insn %d matching operand %d.\n",
2031 operand_number, INSN_UID (insn), match_number);
2036 /* return nonzero if X is stable and mentions no registers but for
2037 mentioning SRC or mentioning / changing DST . If in doubt, presume
2039 The rationale is that we want to check if we can move an insn easily
2040 while just paying attention to SRC and DST. A register is considered
2041 stable if it has the RTX_UNCHANGING_P bit set, but that would still
2042 leave the burden to update REG_DEAD / REG_UNUSED notes, so we don't
2043 want any registers but SRC and DST. */
2045 stable_and_no_regs_but_for_p (rtx x, rtx src, rtx dst)
2047 RTX_CODE code = GET_CODE (x);
2048 switch (GET_RTX_CLASS (code))
2050 case '<': case '1': case 'c': case '2': case 'b': case '3':
2053 const char *fmt = GET_RTX_FORMAT (code);
2054 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2056 && ! stable_and_no_regs_but_for_p (XEXP (x, i), src, dst))
2062 return x == src || x == dst;
2063 /* If this is a MEM, look inside - there might be a register hidden in
2064 the address of an unchanging MEM. */
2066 && ! stable_and_no_regs_but_for_p (XEXP (x, 0), src, dst))
2070 return ! rtx_unstable_p (x);
2074 /* Track stack adjustments and stack memory references. Attempt to
2075 reduce the number of stack adjustments by back-propagating across
2076 the memory references.
2078 This is intended primarily for use with targets that do not define
2079 ACCUMULATE_OUTGOING_ARGS. It is of significantly more value to
2080 targets that define PREFERRED_STACK_BOUNDARY more aligned than
2081 STACK_BOUNDARY (e.g. x86), or if not all registers can be pushed
2082 (e.g. x86 fp regs) which would ordinarily have to be implemented
2083 as a sub/mov pair due to restrictions in calls.c.
2085 Propagation stops when any of the insns that need adjusting are
2086 (a) no longer valid because we've exceeded their range, (b) a
2087 non-trivial push instruction, or (c) a call instruction.
2089 Restriction B is based on the assumption that push instructions
2090 are smaller or faster. If a port really wants to remove all
2091 pushes, it should have defined ACCUMULATE_OUTGOING_ARGS. The
2092 one exception that is made is for an add immediately followed
2095 /* This structure records stack memory references between stack adjusting
2100 HOST_WIDE_INT sp_offset;
2102 struct csa_memlist *next;
2105 static int stack_memref_p (rtx);
2106 static rtx single_set_for_csa (rtx);
2107 static void free_csa_memlist (struct csa_memlist *);
2108 static struct csa_memlist *record_one_stack_memref (rtx, rtx *,
2109 struct csa_memlist *);
2110 static int try_apply_stack_adjustment (rtx, struct csa_memlist *,
2111 HOST_WIDE_INT, HOST_WIDE_INT);
2112 static void combine_stack_adjustments_for_block (basic_block);
2113 static int record_stack_memrefs (rtx *, void *);
2116 /* Main entry point for stack adjustment combination. */
2119 combine_stack_adjustments (void)
2124 combine_stack_adjustments_for_block (bb);
2127 /* Recognize a MEM of the form (sp) or (plus sp const). */
2130 stack_memref_p (rtx x)
2132 if (GET_CODE (x) != MEM)
2136 if (x == stack_pointer_rtx)
2138 if (GET_CODE (x) == PLUS
2139 && XEXP (x, 0) == stack_pointer_rtx
2140 && GET_CODE (XEXP (x, 1)) == CONST_INT)
2146 /* Recognize either normal single_set or the hack in i386.md for
2147 tying fp and sp adjustments. */
2150 single_set_for_csa (rtx insn)
2153 rtx tmp = single_set (insn);
2157 if (GET_CODE (insn) != INSN
2158 || GET_CODE (PATTERN (insn)) != PARALLEL)
2161 tmp = PATTERN (insn);
2162 if (GET_CODE (XVECEXP (tmp, 0, 0)) != SET)
2165 for (i = 1; i < XVECLEN (tmp, 0); ++i)
2167 rtx this = XVECEXP (tmp, 0, i);
2169 /* The special case is allowing a no-op set. */
2170 if (GET_CODE (this) == SET
2171 && SET_SRC (this) == SET_DEST (this))
2173 else if (GET_CODE (this) != CLOBBER
2174 && GET_CODE (this) != USE)
2178 return XVECEXP (tmp, 0, 0);
2181 /* Free the list of csa_memlist nodes. */
2184 free_csa_memlist (struct csa_memlist *memlist)
2186 struct csa_memlist *next;
2187 for (; memlist ; memlist = next)
2189 next = memlist->next;
2194 /* Create a new csa_memlist node from the given memory reference.
2195 It is already known that the memory is stack_memref_p. */
2197 static struct csa_memlist *
2198 record_one_stack_memref (rtx insn, rtx *mem, struct csa_memlist *next_memlist)
2200 struct csa_memlist *ml;
2202 ml = (struct csa_memlist *) xmalloc (sizeof (*ml));
2204 if (XEXP (*mem, 0) == stack_pointer_rtx)
2207 ml->sp_offset = INTVAL (XEXP (XEXP (*mem, 0), 1));
2211 ml->next = next_memlist;
2216 /* Attempt to apply ADJUST to the stack adjusting insn INSN, as well
2217 as each of the memories in MEMLIST. Return true on success. */
2220 try_apply_stack_adjustment (rtx insn, struct csa_memlist *memlist, HOST_WIDE_INT new_adjust,
2221 HOST_WIDE_INT delta)
2223 struct csa_memlist *ml;
2226 set = single_set_for_csa (insn);
2227 validate_change (insn, &XEXP (SET_SRC (set), 1), GEN_INT (new_adjust), 1);
2229 for (ml = memlist; ml ; ml = ml->next)
2232 replace_equiv_address_nv (*ml->mem,
2233 plus_constant (stack_pointer_rtx,
2234 ml->sp_offset - delta)), 1);
2236 if (apply_change_group ())
2238 /* Succeeded. Update our knowledge of the memory references. */
2239 for (ml = memlist; ml ; ml = ml->next)
2240 ml->sp_offset -= delta;
2248 /* Called via for_each_rtx and used to record all stack memory references in
2249 the insn and discard all other stack pointer references. */
2250 struct record_stack_memrefs_data
2253 struct csa_memlist *memlist;
2257 record_stack_memrefs (rtx *xp, void *data)
2260 struct record_stack_memrefs_data *d =
2261 (struct record_stack_memrefs_data *) data;
2264 switch (GET_CODE (x))
2267 if (!reg_mentioned_p (stack_pointer_rtx, x))
2269 /* We are not able to handle correctly all possible memrefs containing
2270 stack pointer, so this check is necessary. */
2271 if (stack_memref_p (x))
2273 d->memlist = record_one_stack_memref (d->insn, xp, d->memlist);
2278 /* ??? We want be able to handle non-memory stack pointer
2279 references later. For now just discard all insns referring to
2280 stack pointer outside mem expressions. We would probably
2281 want to teach validate_replace to simplify expressions first.
2283 We can't just compare with STACK_POINTER_RTX because the
2284 reference to the stack pointer might be in some other mode.
2285 In particular, an explicit clobber in an asm statement will
2286 result in a QImode clobber. */
2287 if (REGNO (x) == STACK_POINTER_REGNUM)
2296 /* Subroutine of combine_stack_adjustments, called for each basic block. */
2299 combine_stack_adjustments_for_block (basic_block bb)
2301 HOST_WIDE_INT last_sp_adjust = 0;
2302 rtx last_sp_set = NULL_RTX;
2303 struct csa_memlist *memlist = NULL;
2304 rtx insn, next, set;
2305 struct record_stack_memrefs_data data;
2306 bool end_of_block = false;
2308 for (insn = bb->head; !end_of_block ; insn = next)
2310 end_of_block = insn == bb->end;
2311 next = NEXT_INSN (insn);
2313 if (! INSN_P (insn))
2316 set = single_set_for_csa (insn);
2319 rtx dest = SET_DEST (set);
2320 rtx src = SET_SRC (set);
2322 /* Find constant additions to the stack pointer. */
2323 if (dest == stack_pointer_rtx
2324 && GET_CODE (src) == PLUS
2325 && XEXP (src, 0) == stack_pointer_rtx
2326 && GET_CODE (XEXP (src, 1)) == CONST_INT)
2328 HOST_WIDE_INT this_adjust = INTVAL (XEXP (src, 1));
2330 /* If we've not seen an adjustment previously, record
2331 it now and continue. */
2335 last_sp_adjust = this_adjust;
2339 /* If not all recorded memrefs can be adjusted, or the
2340 adjustment is now too large for a constant addition,
2341 we cannot merge the two stack adjustments.
2343 Also we need to be careful to not move stack pointer
2344 such that we create stack accesses outside the allocated
2345 area. We can combine an allocation into the first insn,
2346 or a deallocation into the second insn. We can not
2347 combine an allocation followed by a deallocation.
2349 The only somewhat frequent occurrence of the later is when
2350 a function allocates a stack frame but does not use it.
2351 For this case, we would need to analyze rtl stream to be
2352 sure that allocated area is really unused. This means not
2353 only checking the memory references, but also all registers
2354 or global memory references possibly containing a stack
2357 Perhaps the best way to address this problem is to teach
2358 gcc not to allocate stack for objects never used. */
2360 /* Combine an allocation into the first instruction. */
2361 if (STACK_GROWS_DOWNWARD ? this_adjust <= 0 : this_adjust >= 0)
2363 if (try_apply_stack_adjustment (last_sp_set, memlist,
2364 last_sp_adjust + this_adjust,
2369 last_sp_adjust += this_adjust;
2374 /* Otherwise we have a deallocation. Do not combine with
2375 a previous allocation. Combine into the second insn. */
2376 else if (STACK_GROWS_DOWNWARD
2377 ? last_sp_adjust >= 0 : last_sp_adjust <= 0)
2379 if (try_apply_stack_adjustment (insn, memlist,
2380 last_sp_adjust + this_adjust,
2384 delete_insn (last_sp_set);
2386 last_sp_adjust += this_adjust;
2387 free_csa_memlist (memlist);
2393 /* Combination failed. Restart processing from here. If
2394 deallocation+allocation conspired to cancel, we can
2395 delete the old deallocation insn. */
2396 if (last_sp_set && last_sp_adjust == 0)
2398 free_csa_memlist (memlist);
2401 last_sp_adjust = this_adjust;
2405 /* Find a predecrement of exactly the previous adjustment and
2406 turn it into a direct store. Obviously we can't do this if
2407 there were any intervening uses of the stack pointer. */
2409 && GET_CODE (dest) == MEM
2410 && ((GET_CODE (XEXP (dest, 0)) == PRE_DEC
2412 == (HOST_WIDE_INT) GET_MODE_SIZE (GET_MODE (dest))))
2413 || (GET_CODE (XEXP (dest, 0)) == PRE_MODIFY
2414 && GET_CODE (XEXP (XEXP (dest, 0), 1)) == PLUS
2415 && XEXP (XEXP (XEXP (dest, 0), 1), 0) == stack_pointer_rtx
2416 && (GET_CODE (XEXP (XEXP (XEXP (dest, 0), 1), 1))
2418 && (INTVAL (XEXP (XEXP (XEXP (dest, 0), 1), 1))
2419 == -last_sp_adjust)))
2420 && XEXP (XEXP (dest, 0), 0) == stack_pointer_rtx
2421 && ! reg_mentioned_p (stack_pointer_rtx, src)
2422 && memory_address_p (GET_MODE (dest), stack_pointer_rtx)
2423 && validate_change (insn, &SET_DEST (set),
2424 replace_equiv_address (dest,
2428 delete_insn (last_sp_set);
2429 free_csa_memlist (memlist);
2431 last_sp_set = NULL_RTX;
2438 data.memlist = memlist;
2439 if (GET_CODE (insn) != CALL_INSN && last_sp_set
2440 && !for_each_rtx (&PATTERN (insn), record_stack_memrefs, &data))
2442 memlist = data.memlist;
2445 memlist = data.memlist;
2447 /* Otherwise, we were not able to process the instruction.
2448 Do not continue collecting data across such a one. */
2450 && (GET_CODE (insn) == CALL_INSN
2451 || reg_mentioned_p (stack_pointer_rtx, PATTERN (insn))))
2453 if (last_sp_set && last_sp_adjust == 0)
2454 delete_insn (last_sp_set);
2455 free_csa_memlist (memlist);
2457 last_sp_set = NULL_RTX;
2462 if (last_sp_set && last_sp_adjust == 0)
2463 delete_insn (last_sp_set);
OSDN Git Service
