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 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 "rtl.h" /* stdio.h must precede rtl.h for FFS. */
32 #include "insn-config.h"
36 #include "hard-reg-set.h"
40 #include "basic-block.h"
46 /* Turn STACK_GROWS_DOWNWARD into a boolean. */
47 #ifdef STACK_GROWS_DOWNWARD
48 #undef STACK_GROWS_DOWNWARD
49 #define STACK_GROWS_DOWNWARD 1
51 #define STACK_GROWS_DOWNWARD 0
54 static int perhaps_ends_bb_p PARAMS ((rtx));
55 static int optimize_reg_copy_1 PARAMS ((rtx, rtx, rtx));
56 static void optimize_reg_copy_2 PARAMS ((rtx, rtx, rtx));
57 static void optimize_reg_copy_3 PARAMS ((rtx, rtx, rtx));
58 static void copy_src_to_dest PARAMS ((rtx, rtx, rtx, int));
59 static int *regmove_bb_head;
62 int with[MAX_RECOG_OPERANDS];
63 enum { READ, WRITE, READWRITE } use[MAX_RECOG_OPERANDS];
64 int commutative[MAX_RECOG_OPERANDS];
65 int early_clobber[MAX_RECOG_OPERANDS];
68 static rtx discover_flags_reg PARAMS ((void));
69 static void mark_flags_life_zones PARAMS ((rtx));
70 static void flags_set_1 PARAMS ((rtx, rtx, void *));
72 static int try_auto_increment PARAMS ((rtx, rtx, rtx, rtx, HOST_WIDE_INT, int));
73 static int find_matches PARAMS ((rtx, struct match *));
74 static void replace_in_call_usage PARAMS ((rtx *, unsigned int, rtx, rtx));
75 static int fixup_match_1 PARAMS ((rtx, rtx, rtx, rtx, rtx, int, int, int, FILE *))
77 static int reg_is_remote_constant_p PARAMS ((rtx, rtx, rtx));
78 static int stable_and_no_regs_but_for_p PARAMS ((rtx, rtx, rtx));
79 static int regclass_compatible_p PARAMS ((int, int));
80 static int replacement_quality PARAMS ((rtx));
81 static int fixup_match_2 PARAMS ((rtx, rtx, rtx, rtx, FILE *));
83 /* Return non-zero if registers with CLASS1 and CLASS2 can be merged without
84 causing too much register allocation problems. */
86 regclass_compatible_p (class0, 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 (insn, inc_insn, inc_insn_set, reg, increment, pre)
102 rtx reg, insn, inc_insn ,inc_insn_set;
103 HOST_WIDE_INT increment;
106 enum rtx_code inc_code;
108 rtx pset = single_set (insn);
111 /* Can't use the size of SET_SRC, we might have something like
112 (sign_extend:SI (mem:QI ... */
113 rtx use = find_use_as_address (pset, reg, 0);
114 if (use != 0 && use != (rtx) (size_t) 1)
116 int size = GET_MODE_SIZE (GET_MODE (use));
118 || (HAVE_POST_INCREMENT
119 && pre == 0 && (inc_code = POST_INC, increment == size))
120 || (HAVE_PRE_INCREMENT
121 && pre == 1 && (inc_code = PRE_INC, increment == size))
122 || (HAVE_POST_DECREMENT
123 && pre == 0 && (inc_code = POST_DEC, increment == -size))
124 || (HAVE_PRE_DECREMENT
125 && pre == 1 && (inc_code = PRE_DEC, increment == -size))
131 &SET_SRC (inc_insn_set),
132 XEXP (SET_SRC (inc_insn_set), 0), 1);
133 validate_change (insn, &XEXP (use, 0),
134 gen_rtx_fmt_e (inc_code, Pmode, reg), 1);
135 if (apply_change_group ())
137 /* If there is a REG_DEAD note on this insn, we must
138 change this not to REG_UNUSED meaning that the register
139 is set, but the value is dead. Failure to do so will
140 result in a sched1 abort -- when it recomputes lifetime
141 information, the number of REG_DEAD notes will have
143 rtx note = find_reg_note (insn, REG_DEAD, reg);
145 PUT_MODE (note, REG_UNUSED);
148 = gen_rtx_EXPR_LIST (REG_INC,
149 reg, REG_NOTES (insn));
151 delete_insn (inc_insn);
160 /* Determine if the pattern generated by add_optab has a clobber,
161 such as might be issued for a flags hard register. To make the
162 code elsewhere simpler, we handle cc0 in this same framework.
164 Return the register if one was discovered. Return NULL_RTX if
165 if no flags were found. Return pc_rtx if we got confused. */
168 discover_flags_reg ()
171 tmp = gen_rtx_REG (word_mode, 10000);
172 tmp = gen_add3_insn (tmp, tmp, GEN_INT (2));
174 /* If we get something that isn't a simple set, or a
175 [(set ..) (clobber ..)], this whole function will go wrong. */
176 if (GET_CODE (tmp) == SET)
178 else if (GET_CODE (tmp) == PARALLEL)
182 if (XVECLEN (tmp, 0) != 2)
184 tmp = XVECEXP (tmp, 0, 1);
185 if (GET_CODE (tmp) != CLOBBER)
189 /* Don't do anything foolish if the md wanted to clobber a
190 scratch or something. We only care about hard regs.
191 Moreover we don't like the notion of subregs of hard regs. */
192 if (GET_CODE (tmp) == SUBREG
193 && GET_CODE (SUBREG_REG (tmp)) == REG
194 && REGNO (SUBREG_REG (tmp)) < FIRST_PSEUDO_REGISTER)
196 found = (GET_CODE (tmp) == REG && REGNO (tmp) < FIRST_PSEUDO_REGISTER);
198 return (found ? tmp : NULL_RTX);
204 /* It is a tedious task identifying when the flags register is live and
205 when it is safe to optimize. Since we process the instruction stream
206 multiple times, locate and record these live zones by marking the
207 mode of the instructions --
209 QImode is used on the instruction at which the flags becomes live.
211 HImode is used within the range (exclusive) that the flags are
212 live. Thus the user of the flags is not marked.
214 All other instructions are cleared to VOIDmode. */
216 /* Used to communicate with flags_set_1. */
217 static rtx flags_set_1_rtx;
218 static int flags_set_1_set;
221 mark_flags_life_zones (flags)
229 /* If we found a flags register on a cc0 host, bail. */
230 if (flags == NULL_RTX)
232 else if (flags != cc0_rtx)
236 /* Simple cases first: if no flags, clear all modes. If confusing,
237 mark the entire function as being in a flags shadow. */
238 if (flags == NULL_RTX || flags == pc_rtx)
240 enum machine_mode mode = (flags ? HImode : VOIDmode);
242 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
243 PUT_MODE (insn, mode);
251 flags_regno = REGNO (flags);
252 flags_nregs = HARD_REGNO_NREGS (flags_regno, GET_MODE (flags));
254 flags_set_1_rtx = flags;
256 /* Process each basic block. */
257 FOR_EACH_BB_REVERSE (block)
265 /* Look out for the (unlikely) case of flags being live across
266 basic block boundaries. */
271 for (i = 0; i < flags_nregs; ++i)
272 live |= REGNO_REG_SET_P (block->global_live_at_start,
279 /* Process liveness in reverse order of importance --
280 alive, death, birth. This lets more important info
281 overwrite the mode of lesser info. */
286 /* In the cc0 case, death is not marked in reg notes,
287 but is instead the mere use of cc0 when it is alive. */
288 if (live && reg_mentioned_p (cc0_rtx, PATTERN (insn)))
291 /* In the hard reg case, we watch death notes. */
292 if (live && find_regno_note (insn, REG_DEAD, flags_regno))
295 PUT_MODE (insn, (live ? HImode : VOIDmode));
297 /* In either case, birth is denoted simply by it's presence
298 as the destination of a set. */
300 note_stores (PATTERN (insn), flags_set_1, NULL);
304 PUT_MODE (insn, QImode);
308 PUT_MODE (insn, (live ? HImode : VOIDmode));
312 insn = NEXT_INSN (insn);
317 /* A subroutine of mark_flags_life_zones, called through note_stores. */
320 flags_set_1 (x, pat, data)
322 void *data ATTRIBUTE_UNUSED;
324 if (GET_CODE (pat) == SET
325 && reg_overlap_mentioned_p (x, flags_set_1_rtx))
329 static int *regno_src_regno;
331 /* Indicate how good a choice REG (which appears as a source) is to replace
332 a destination register with. The higher the returned value, the better
333 the choice. The main objective is to avoid using a register that is
334 a candidate for tying to a hard register, since the output might in
335 turn be a candidate to be tied to a different hard register. */
337 replacement_quality (reg)
342 /* Bad if this isn't a register at all. */
343 if (GET_CODE (reg) != REG)
346 /* If this register is not meant to get a hard register,
347 it is a poor choice. */
348 if (REG_LIVE_LENGTH (REGNO (reg)) < 0)
351 src_regno = regno_src_regno[REGNO (reg)];
353 /* If it was not copied from another register, it is fine. */
357 /* Copied from a hard register? */
358 if (src_regno < FIRST_PSEUDO_REGISTER)
361 /* Copied from a pseudo register - not as bad as from a hard register,
362 yet still cumbersome, since the register live length will be lengthened
363 when the registers get tied. */
367 /* Return 1 if INSN might end a basic block. */
369 static int perhaps_ends_bb_p (insn)
372 switch (GET_CODE (insn))
376 /* These always end a basic block. */
380 /* A CALL_INSN might be the last insn of a basic block, if it is inside
381 an EH region or if there are nonlocal gotos. Note that this test is
382 very conservative. */
383 if (nonlocal_goto_handler_labels)
387 return can_throw_internal (insn);
391 /* INSN is a copy from SRC to DEST, both registers, and SRC does not die
394 Search forward to see if SRC dies before either it or DEST is modified,
395 but don't scan past the end of a basic block. If so, we can replace SRC
396 with DEST and let SRC die in INSN.
398 This will reduce the number of registers live in that range and may enable
399 DEST to be tied to SRC, thus often saving one register in addition to a
400 register-register copy. */
403 optimize_reg_copy_1 (insn, dest, src)
411 int sregno = REGNO (src);
412 int dregno = REGNO (dest);
414 /* We don't want to mess with hard regs if register classes are small. */
416 || (SMALL_REGISTER_CLASSES
417 && (sregno < FIRST_PSEUDO_REGISTER
418 || dregno < FIRST_PSEUDO_REGISTER))
419 /* We don't see all updates to SP if they are in an auto-inc memory
420 reference, so we must disallow this optimization on them. */
421 || sregno == STACK_POINTER_REGNUM || dregno == STACK_POINTER_REGNUM)
424 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
426 /* ??? We can't scan past the end of a basic block without updating
427 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
428 if (perhaps_ends_bb_p (p))
430 else if (! INSN_P (p))
433 if (reg_set_p (src, p) || reg_set_p (dest, p)
434 /* Don't change a USE of a register. */
435 || (GET_CODE (PATTERN (p)) == USE
436 && reg_overlap_mentioned_p (src, XEXP (PATTERN (p), 0))))
439 /* See if all of SRC dies in P. This test is slightly more
440 conservative than it needs to be. */
441 if ((note = find_regno_note (p, REG_DEAD, sregno)) != 0
442 && GET_MODE (XEXP (note, 0)) == GET_MODE (src))
450 /* We can do the optimization. Scan forward from INSN again,
451 replacing regs as we go. Set FAILED if a replacement can't
452 be done. In that case, we can't move the death note for SRC.
453 This should be rare. */
455 /* Set to stop at next insn. */
456 for (q = next_real_insn (insn);
457 q != next_real_insn (p);
458 q = next_real_insn (q))
460 if (reg_overlap_mentioned_p (src, PATTERN (q)))
462 /* If SRC is a hard register, we might miss some
463 overlapping registers with validate_replace_rtx,
464 so we would have to undo it. We can't if DEST is
465 present in the insn, so fail in that combination
467 if (sregno < FIRST_PSEUDO_REGISTER
468 && reg_mentioned_p (dest, PATTERN (q)))
471 /* Replace all uses and make sure that the register
472 isn't still present. */
473 else if (validate_replace_rtx (src, dest, q)
474 && (sregno >= FIRST_PSEUDO_REGISTER
475 || ! reg_overlap_mentioned_p (src,
480 validate_replace_rtx (dest, src, q);
485 /* For SREGNO, count the total number of insns scanned.
486 For DREGNO, count the total number of insns scanned after
487 passing the death note for DREGNO. */
492 /* If the insn in which SRC dies is a CALL_INSN, don't count it
493 as a call that has been crossed. Otherwise, count it. */
494 if (q != p && GET_CODE (q) == CALL_INSN)
496 /* Similarly, total calls for SREGNO, total calls beyond
497 the death note for DREGNO. */
503 /* If DEST dies here, remove the death note and save it for
504 later. Make sure ALL of DEST dies here; again, this is
505 overly conservative. */
507 && (dest_death = find_regno_note (q, REG_DEAD, dregno)) != 0)
509 if (GET_MODE (XEXP (dest_death, 0)) != GET_MODE (dest))
510 failed = 1, dest_death = 0;
512 remove_note (q, dest_death);
518 /* These counters need to be updated if and only if we are
519 going to move the REG_DEAD note. */
520 if (sregno >= FIRST_PSEUDO_REGISTER)
522 if (REG_LIVE_LENGTH (sregno) >= 0)
524 REG_LIVE_LENGTH (sregno) -= s_length;
525 /* REG_LIVE_LENGTH is only an approximation after
526 combine if sched is not run, so make sure that we
527 still have a reasonable value. */
528 if (REG_LIVE_LENGTH (sregno) < 2)
529 REG_LIVE_LENGTH (sregno) = 2;
532 REG_N_CALLS_CROSSED (sregno) -= s_n_calls;
535 /* Move death note of SRC from P to INSN. */
536 remove_note (p, note);
537 XEXP (note, 1) = REG_NOTES (insn);
538 REG_NOTES (insn) = note;
541 /* DEST is also dead if INSN has a REG_UNUSED note for DEST. */
543 && (dest_death = find_regno_note (insn, REG_UNUSED, dregno)))
545 PUT_REG_NOTE_KIND (dest_death, REG_DEAD);
546 remove_note (insn, dest_death);
549 /* Put death note of DEST on P if we saw it die. */
552 XEXP (dest_death, 1) = REG_NOTES (p);
553 REG_NOTES (p) = dest_death;
555 if (dregno >= FIRST_PSEUDO_REGISTER)
557 /* If and only if we are moving the death note for DREGNO,
558 then we need to update its counters. */
559 if (REG_LIVE_LENGTH (dregno) >= 0)
560 REG_LIVE_LENGTH (dregno) += d_length;
561 REG_N_CALLS_CROSSED (dregno) += d_n_calls;
568 /* If SRC is a hard register which is set or killed in some other
569 way, we can't do this optimization. */
570 else if (sregno < FIRST_PSEUDO_REGISTER
571 && dead_or_set_p (p, src))
577 /* INSN is a copy of SRC to DEST, in which SRC dies. See if we now have
578 a sequence of insns that modify DEST followed by an insn that sets
579 SRC to DEST in which DEST dies, with no prior modification of DEST.
580 (There is no need to check if the insns in between actually modify
581 DEST. We should not have cases where DEST is not modified, but
582 the optimization is safe if no such modification is detected.)
583 In that case, we can replace all uses of DEST, starting with INSN and
584 ending with the set of SRC to DEST, with SRC. We do not do this
585 optimization if a CALL_INSN is crossed unless SRC already crosses a
586 call or if DEST dies before the copy back to SRC.
588 It is assumed that DEST and SRC are pseudos; it is too complicated to do
589 this for hard registers since the substitutions we may make might fail. */
592 optimize_reg_copy_2 (insn, dest, 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);
626 if (GET_CODE (q) == CALL_INSN)
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 || (GET_CODE (p) == CALL_INSN && 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 encorporate 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 (insn, dest, src)
658 rtx src_reg = XEXP (src, 0);
659 int src_no = REGNO (src_reg);
660 int dst_no = REGNO (dest);
662 enum machine_mode old_mode;
664 if (src_no < FIRST_PSEUDO_REGISTER
665 || dst_no < FIRST_PSEUDO_REGISTER
666 || ! find_reg_note (insn, REG_DEAD, src_reg)
667 || REG_N_SETS (src_no) != 1)
669 for (p = PREV_INSN (insn); p && ! reg_set_p (src_reg, p); p = PREV_INSN (p))
670 /* ??? We can't scan past the end of a basic block without updating
671 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
672 if (perhaps_ends_bb_p (p))
678 if (! (set = single_set (p))
679 || GET_CODE (SET_SRC (set)) != MEM
680 /* If there's a REG_EQUIV note, this must be an insn that loads an
681 argument. Prefer keeping the note over doing this optimization. */
682 || find_reg_note (p, REG_EQUIV, NULL_RTX)
683 || SET_DEST (set) != src_reg)
686 /* Be conserative: although this optimization is also valid for
687 volatile memory references, that could cause trouble in later passes. */
688 if (MEM_VOLATILE_P (SET_SRC (set)))
691 /* Do not use a SUBREG to truncate from one mode to another if truncation
693 if (GET_MODE_BITSIZE (GET_MODE (src_reg)) <= GET_MODE_BITSIZE (GET_MODE (src))
694 && !TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (GET_MODE (src)),
695 GET_MODE_BITSIZE (GET_MODE (src_reg))))
698 old_mode = GET_MODE (src_reg);
699 PUT_MODE (src_reg, GET_MODE (src));
700 XEXP (src, 0) = SET_SRC (set);
702 /* Include this change in the group so that it's easily undone if
703 one of the changes in the group is invalid. */
704 validate_change (p, &SET_SRC (set), src, 1);
706 /* Now walk forward making additional replacements. We want to be able
707 to undo all the changes if a later substitution fails. */
708 subreg = gen_lowpart_SUBREG (old_mode, src_reg);
709 while (p = NEXT_INSN (p), p != insn)
714 /* Make a tenative change. */
715 validate_replace_rtx_group (src_reg, subreg, p);
718 validate_replace_rtx_group (src, src_reg, insn);
720 /* Now see if all the changes are valid. */
721 if (! apply_change_group ())
723 /* One or more changes were no good. Back out everything. */
724 PUT_MODE (src_reg, old_mode);
725 XEXP (src, 0) = src_reg;
729 rtx note = find_reg_note (p, REG_EQUAL, NULL_RTX);
731 remove_note (p, note);
736 /* If we were not able to update the users of src to use dest directly, try
737 instead moving the value to dest directly before the operation. */
740 copy_src_to_dest (insn, src, dest, old_max_uid)
759 /* A REG_LIVE_LENGTH of -1 indicates the register is equivalent to a constant
760 or memory location and is used infrequently; a REG_LIVE_LENGTH of -2 is
761 parameter when there is no frame pointer that is not allocated a register.
762 For now, we just reject them, rather than incrementing the live length. */
764 if (GET_CODE (src) == REG
765 && REG_LIVE_LENGTH (REGNO (src)) > 0
766 && GET_CODE (dest) == REG
767 && !RTX_UNCHANGING_P (dest)
768 && REG_LIVE_LENGTH (REGNO (dest)) > 0
769 && (set = single_set (insn)) != NULL_RTX
770 && !reg_mentioned_p (dest, SET_SRC (set))
771 && GET_MODE (src) == GET_MODE (dest))
773 int old_num_regs = reg_rtx_no;
775 /* Generate the src->dest move. */
777 emit_move_insn (dest, src);
780 /* If this sequence uses new registers, we may not use it. */
781 if (old_num_regs != reg_rtx_no
782 || ! validate_replace_rtx (src, dest, insn))
784 /* We have to restore reg_rtx_no to its old value, lest
785 recompute_reg_usage will try to compute the usage of the
786 new regs, yet reg_n_info is not valid for them. */
787 reg_rtx_no = old_num_regs;
790 emit_insn_before (seq, insn);
791 move_insn = PREV_INSN (insn);
792 p_move_notes = ®_NOTES (move_insn);
793 p_insn_notes = ®_NOTES (insn);
795 /* Move any notes mentioning src to the move instruction */
796 for (link = REG_NOTES (insn); link != NULL_RTX; link = next)
798 next = XEXP (link, 1);
799 if (XEXP (link, 0) == src)
801 *p_move_notes = link;
802 p_move_notes = &XEXP (link, 1);
806 *p_insn_notes = link;
807 p_insn_notes = &XEXP (link, 1);
811 *p_move_notes = NULL_RTX;
812 *p_insn_notes = NULL_RTX;
814 /* Is the insn the head of a basic block? If so extend it */
815 insn_uid = INSN_UID (insn);
816 move_uid = INSN_UID (move_insn);
817 if (insn_uid < old_max_uid)
819 bb = regmove_bb_head[insn_uid];
822 BLOCK_HEAD (bb) = move_insn;
823 regmove_bb_head[insn_uid] = -1;
827 /* Update the various register tables. */
828 dest_regno = REGNO (dest);
829 REG_N_SETS (dest_regno) ++;
830 REG_LIVE_LENGTH (dest_regno)++;
831 if (REGNO_FIRST_UID (dest_regno) == insn_uid)
832 REGNO_FIRST_UID (dest_regno) = move_uid;
834 src_regno = REGNO (src);
835 if (! find_reg_note (move_insn, REG_DEAD, src))
836 REG_LIVE_LENGTH (src_regno)++;
838 if (REGNO_FIRST_UID (src_regno) == insn_uid)
839 REGNO_FIRST_UID (src_regno) = move_uid;
841 if (REGNO_LAST_UID (src_regno) == insn_uid)
842 REGNO_LAST_UID (src_regno) = move_uid;
844 if (REGNO_LAST_NOTE_UID (src_regno) == insn_uid)
845 REGNO_LAST_NOTE_UID (src_regno) = move_uid;
850 /* Return whether REG is set in only one location, and is set to a
851 constant, but is set in a different basic block from INSN (an
852 instructions which uses REG). In this case REG is equivalent to a
853 constant, and we don't want to break that equivalence, because that
854 may increase register pressure and make reload harder. If REG is
855 set in the same basic block as INSN, we don't worry about it,
856 because we'll probably need a register anyhow (??? but what if REG
857 is used in a different basic block as well as this one?). FIRST is
858 the first insn in the function. */
861 reg_is_remote_constant_p (reg, insn, first)
868 if (REG_N_SETS (REGNO (reg)) != 1)
871 /* Look for the set. */
872 for (p = LOG_LINKS (insn); p; p = XEXP (p, 1))
876 if (REG_NOTE_KIND (p) != 0)
878 s = single_set (XEXP (p, 0));
880 && GET_CODE (SET_DEST (s)) == REG
881 && REGNO (SET_DEST (s)) == REGNO (reg))
883 /* The register is set in the same basic block. */
888 for (p = first; p && p != insn; p = NEXT_INSN (p))
896 && GET_CODE (SET_DEST (s)) == REG
897 && REGNO (SET_DEST (s)) == REGNO (reg))
899 /* This is the instruction which sets REG. If there is a
900 REG_EQUAL note, then REG is equivalent to a constant. */
901 if (find_reg_note (p, REG_EQUAL, NULL_RTX))
910 /* INSN is adding a CONST_INT to a REG. We search backwards looking for
911 another add immediate instruction with the same source and dest registers,
912 and if we find one, we change INSN to an increment, and return 1. If
913 no changes are made, we return 0.
916 (set (reg100) (plus reg1 offset1))
918 (set (reg100) (plus reg1 offset2))
920 (set (reg100) (plus reg1 offset1))
922 (set (reg100) (plus reg100 offset2-offset1)) */
924 /* ??? What does this comment mean? */
925 /* cse disrupts preincrement / postdecrement squences when it finds a
926 hard register as ultimate source, like the frame pointer. */
929 fixup_match_2 (insn, dst, src, offset, regmove_dump_file)
930 rtx insn, dst, src, offset;
931 FILE *regmove_dump_file;
933 rtx p, dst_death = 0;
934 int length, num_calls = 0;
936 /* If SRC dies in INSN, we'd have to move the death note. This is
937 considered to be very unlikely, so we just skip the optimization
939 if (find_regno_note (insn, REG_DEAD, REGNO (src)))
942 /* Scan backward to find the first instruction that sets DST. */
944 for (length = 0, p = PREV_INSN (insn); p; p = PREV_INSN (p))
948 /* ??? We can't scan past the end of a basic block without updating
949 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
950 if (perhaps_ends_bb_p (p))
952 else if (! INSN_P (p))
955 if (find_regno_note (p, REG_DEAD, REGNO (dst)))
960 pset = single_set (p);
961 if (pset && SET_DEST (pset) == dst
962 && GET_CODE (SET_SRC (pset)) == PLUS
963 && XEXP (SET_SRC (pset), 0) == src
964 && GET_CODE (XEXP (SET_SRC (pset), 1)) == CONST_INT)
966 HOST_WIDE_INT newconst
967 = INTVAL (offset) - INTVAL (XEXP (SET_SRC (pset), 1));
968 rtx add = gen_add3_insn (dst, dst, GEN_INT (newconst));
970 if (add && validate_change (insn, &PATTERN (insn), add, 0))
972 /* Remove the death note for DST from DST_DEATH. */
975 remove_death (REGNO (dst), dst_death);
976 REG_LIVE_LENGTH (REGNO (dst)) += length;
977 REG_N_CALLS_CROSSED (REGNO (dst)) += num_calls;
980 if (regmove_dump_file)
981 fprintf (regmove_dump_file,
982 "Fixed operand of insn %d.\n",
986 for (p = PREV_INSN (insn); p; p = PREV_INSN (p))
988 if (GET_CODE (p) == CODE_LABEL
989 || GET_CODE (p) == JUMP_INSN)
993 if (reg_overlap_mentioned_p (dst, PATTERN (p)))
995 if (try_auto_increment (p, insn, 0, dst, newconst, 0))
1000 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
1002 if (GET_CODE (p) == CODE_LABEL
1003 || GET_CODE (p) == JUMP_INSN)
1007 if (reg_overlap_mentioned_p (dst, PATTERN (p)))
1009 try_auto_increment (p, insn, 0, dst, newconst, 1);
1018 if (reg_set_p (dst, PATTERN (p)))
1021 /* If we have passed a call instruction, and the
1022 pseudo-reg SRC is not already live across a call,
1023 then don't perform the optimization. */
1024 /* reg_set_p is overly conservative for CALL_INSNS, thinks that all
1025 hard regs are clobbered. Thus, we only use it for src for
1027 if (GET_CODE (p) == CALL_INSN)
1032 if (REG_N_CALLS_CROSSED (REGNO (src)) == 0)
1035 if (call_used_regs [REGNO (dst)]
1036 || find_reg_fusage (p, CLOBBER, dst))
1039 else if (reg_set_p (src, PATTERN (p)))
1046 /* Main entry for the register move optimization.
1047 F is the first instruction.
1048 NREGS is one plus the highest pseudo-reg number used in the instruction.
1049 REGMOVE_DUMP_FILE is a stream for output of a trace of actions taken
1050 (or 0 if none should be output). */
1053 regmove_optimize (f, nregs, regmove_dump_file)
1056 FILE *regmove_dump_file;
1058 int old_max_uid = get_max_uid ();
1063 rtx copy_src, copy_dst;
1066 /* ??? Hack. Regmove doesn't examine the CFG, and gets mightily
1067 confused by non-call exceptions ending blocks. */
1068 if (flag_non_call_exceptions)
1071 /* Find out where a potential flags register is live, and so that we
1072 can supress some optimizations in those zones. */
1073 mark_flags_life_zones (discover_flags_reg ());
1075 regno_src_regno = (int *) xmalloc (sizeof *regno_src_regno * nregs);
1076 for (i = nregs; --i >= 0; ) regno_src_regno[i] = -1;
1078 regmove_bb_head = (int *) xmalloc (sizeof (int) * (old_max_uid + 1));
1079 for (i = old_max_uid; i >= 0; i--) regmove_bb_head[i] = -1;
1081 regmove_bb_head[INSN_UID (bb->head)] = bb->index;
1083 /* A forward/backward pass. Replace output operands with input operands. */
1085 for (pass = 0; pass <= 2; pass++)
1087 if (! flag_regmove && pass >= flag_expensive_optimizations)
1090 if (regmove_dump_file)
1091 fprintf (regmove_dump_file, "Starting %s pass...\n",
1092 pass ? "backward" : "forward");
1094 for (insn = pass ? get_last_insn () : f; insn;
1095 insn = pass ? PREV_INSN (insn) : NEXT_INSN (insn))
1098 int op_no, match_no;
1100 set = single_set (insn);
1104 if (flag_expensive_optimizations && ! pass
1105 && (GET_CODE (SET_SRC (set)) == SIGN_EXTEND
1106 || GET_CODE (SET_SRC (set)) == ZERO_EXTEND)
1107 && GET_CODE (XEXP (SET_SRC (set), 0)) == REG
1108 && GET_CODE (SET_DEST (set)) == REG)
1109 optimize_reg_copy_3 (insn, SET_DEST (set), SET_SRC (set));
1111 if (flag_expensive_optimizations && ! pass
1112 && GET_CODE (SET_SRC (set)) == REG
1113 && GET_CODE (SET_DEST (set)) == REG)
1115 /* If this is a register-register copy where SRC is not dead,
1116 see if we can optimize it. If this optimization succeeds,
1117 it will become a copy where SRC is dead. */
1118 if ((find_reg_note (insn, REG_DEAD, SET_SRC (set))
1119 || optimize_reg_copy_1 (insn, SET_DEST (set), SET_SRC (set)))
1120 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
1122 /* Similarly for a pseudo-pseudo copy when SRC is dead. */
1123 if (REGNO (SET_SRC (set)) >= FIRST_PSEUDO_REGISTER)
1124 optimize_reg_copy_2 (insn, SET_DEST (set), SET_SRC (set));
1125 if (regno_src_regno[REGNO (SET_DEST (set))] < 0
1126 && SET_SRC (set) != SET_DEST (set))
1128 int srcregno = REGNO (SET_SRC (set));
1129 if (regno_src_regno[srcregno] >= 0)
1130 srcregno = regno_src_regno[srcregno];
1131 regno_src_regno[REGNO (SET_DEST (set))] = srcregno;
1138 if (! find_matches (insn, &match))
1141 /* Now scan through the operands looking for a source operand
1142 which is supposed to match the destination operand.
1143 Then scan forward for an instruction which uses the dest
1145 If it dies there, then replace the dest in both operands with
1146 the source operand. */
1148 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1150 rtx src, dst, src_subreg;
1151 enum reg_class src_class, dst_class;
1153 match_no = match.with[op_no];
1155 /* Nothing to do if the two operands aren't supposed to match. */
1159 src = recog_data.operand[op_no];
1160 dst = recog_data.operand[match_no];
1162 if (GET_CODE (src) != REG)
1166 if (GET_CODE (dst) == SUBREG
1167 && GET_MODE_SIZE (GET_MODE (dst))
1168 >= GET_MODE_SIZE (GET_MODE (SUBREG_REG (dst))))
1171 = gen_rtx_SUBREG (GET_MODE (SUBREG_REG (dst)),
1172 src, SUBREG_BYTE (dst));
1173 dst = SUBREG_REG (dst);
1175 if (GET_CODE (dst) != REG
1176 || REGNO (dst) < FIRST_PSEUDO_REGISTER)
1179 if (REGNO (src) < FIRST_PSEUDO_REGISTER)
1181 if (match.commutative[op_no] < op_no)
1182 regno_src_regno[REGNO (dst)] = REGNO (src);
1186 if (REG_LIVE_LENGTH (REGNO (src)) < 0)
1189 /* op_no/src must be a read-only operand, and
1190 match_operand/dst must be a write-only operand. */
1191 if (match.use[op_no] != READ
1192 || match.use[match_no] != WRITE)
1195 if (match.early_clobber[match_no]
1196 && count_occurrences (PATTERN (insn), src, 0) > 1)
1199 /* Make sure match_operand is the destination. */
1200 if (recog_data.operand[match_no] != SET_DEST (set))
1203 /* If the operands already match, then there is nothing to do. */
1204 if (operands_match_p (src, dst))
1207 /* But in the commutative case, we might find a better match. */
1208 if (match.commutative[op_no] >= 0)
1210 rtx comm = recog_data.operand[match.commutative[op_no]];
1211 if (operands_match_p (comm, dst)
1212 && (replacement_quality (comm)
1213 >= replacement_quality (src)))
1217 src_class = reg_preferred_class (REGNO (src));
1218 dst_class = reg_preferred_class (REGNO (dst));
1219 if (! regclass_compatible_p (src_class, dst_class))
1222 if (GET_MODE (src) != GET_MODE (dst))
1225 if (fixup_match_1 (insn, set, src, src_subreg, dst, pass,
1233 /* A backward pass. Replace input operands with output operands. */
1235 if (regmove_dump_file)
1236 fprintf (regmove_dump_file, "Starting backward pass...\n");
1238 for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
1242 int op_no, match_no;
1245 if (! find_matches (insn, &match))
1248 /* Now scan through the operands looking for a destination operand
1249 which is supposed to match a source operand.
1250 Then scan backward for an instruction which sets the source
1251 operand. If safe, then replace the source operand with the
1252 dest operand in both instructions. */
1254 copy_src = NULL_RTX;
1255 copy_dst = NULL_RTX;
1256 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1258 rtx set, p, src, dst;
1259 rtx src_note, dst_note;
1261 enum reg_class src_class, dst_class;
1264 match_no = match.with[op_no];
1266 /* Nothing to do if the two operands aren't supposed to match. */
1270 dst = recog_data.operand[match_no];
1271 src = recog_data.operand[op_no];
1273 if (GET_CODE (src) != REG)
1276 if (GET_CODE (dst) != REG
1277 || REGNO (dst) < FIRST_PSEUDO_REGISTER
1278 || REG_LIVE_LENGTH (REGNO (dst)) < 0
1279 || RTX_UNCHANGING_P (dst))
1282 /* If the operands already match, then there is nothing to do. */
1283 if (operands_match_p (src, dst))
1286 if (match.commutative[op_no] >= 0)
1288 rtx comm = recog_data.operand[match.commutative[op_no]];
1289 if (operands_match_p (comm, dst))
1293 set = single_set (insn);
1297 /* Note that single_set ignores parts of a parallel set for
1298 which one of the destinations is REG_UNUSED. We can't
1299 handle that here, since we can wind up rewriting things
1300 such that a single register is set twice within a single
1302 if (reg_set_p (src, insn))
1305 /* match_no/dst must be a write-only operand, and
1306 operand_operand/src must be a read-only operand. */
1307 if (match.use[op_no] != READ
1308 || match.use[match_no] != WRITE)
1311 if (match.early_clobber[match_no]
1312 && count_occurrences (PATTERN (insn), src, 0) > 1)
1315 /* Make sure match_no is the destination. */
1316 if (recog_data.operand[match_no] != SET_DEST (set))
1319 if (REGNO (src) < FIRST_PSEUDO_REGISTER)
1321 if (GET_CODE (SET_SRC (set)) == PLUS
1322 && GET_CODE (XEXP (SET_SRC (set), 1)) == CONST_INT
1323 && XEXP (SET_SRC (set), 0) == src
1324 && fixup_match_2 (insn, dst, src,
1325 XEXP (SET_SRC (set), 1),
1330 src_class = reg_preferred_class (REGNO (src));
1331 dst_class = reg_preferred_class (REGNO (dst));
1333 if (! (src_note = find_reg_note (insn, REG_DEAD, src)))
1335 /* We used to force the copy here like in other cases, but
1336 it produces worse code, as it eliminates no copy
1337 instructions and the copy emitted will be produced by
1338 reload anyway. On patterns with multiple alternatives,
1339 there may be better sollution availble.
1341 In particular this change produced slower code for numeric
1347 if (! regclass_compatible_p (src_class, dst_class))
1357 /* Can not modify an earlier insn to set dst if this insn
1358 uses an old value in the source. */
1359 if (reg_overlap_mentioned_p (dst, SET_SRC (set)))
1369 /* If src is set once in a different basic block,
1370 and is set equal to a constant, then do not use
1371 it for this optimization, as this would make it
1372 no longer equivalent to a constant. */
1374 if (reg_is_remote_constant_p (src, insn, f))
1385 if (regmove_dump_file)
1386 fprintf (regmove_dump_file,
1387 "Could fix operand %d of insn %d matching operand %d.\n",
1388 op_no, INSN_UID (insn), match_no);
1390 /* Scan backward to find the first instruction that uses
1391 the input operand. If the operand is set here, then
1392 replace it in both instructions with match_no. */
1394 for (length = 0, p = PREV_INSN (insn); p; p = PREV_INSN (p))
1398 /* ??? We can't scan past the end of a basic block without
1399 updating the register lifetime info
1400 (REG_DEAD/basic_block_live_at_start). */
1401 if (perhaps_ends_bb_p (p))
1403 else if (! INSN_P (p))
1408 /* ??? See if all of SRC is set in P. This test is much
1409 more conservative than it needs to be. */
1410 pset = single_set (p);
1411 if (pset && SET_DEST (pset) == src)
1413 /* We use validate_replace_rtx, in case there
1414 are multiple identical source operands. All of
1415 them have to be changed at the same time. */
1416 if (validate_replace_rtx (src, dst, insn))
1418 if (validate_change (p, &SET_DEST (pset),
1423 /* Change all source operands back.
1424 This modifies the dst as a side-effect. */
1425 validate_replace_rtx (dst, src, insn);
1426 /* Now make sure the dst is right. */
1427 validate_change (insn,
1428 recog_data.operand_loc[match_no],
1435 if (reg_overlap_mentioned_p (src, PATTERN (p))
1436 || reg_overlap_mentioned_p (dst, PATTERN (p)))
1439 /* If we have passed a call instruction, and the
1440 pseudo-reg DST is not already live across a call,
1441 then don't perform the optimization. */
1442 if (GET_CODE (p) == CALL_INSN)
1446 if (REG_N_CALLS_CROSSED (REGNO (dst)) == 0)
1455 /* Remove the death note for SRC from INSN. */
1456 remove_note (insn, src_note);
1457 /* Move the death note for SRC to P if it is used
1459 if (reg_overlap_mentioned_p (src, PATTERN (p)))
1461 XEXP (src_note, 1) = REG_NOTES (p);
1462 REG_NOTES (p) = src_note;
1464 /* If there is a REG_DEAD note for DST on P, then remove
1465 it, because DST is now set there. */
1466 if ((dst_note = find_reg_note (p, REG_DEAD, dst)))
1467 remove_note (p, dst_note);
1469 dstno = REGNO (dst);
1470 srcno = REGNO (src);
1472 REG_N_SETS (dstno)++;
1473 REG_N_SETS (srcno)--;
1475 REG_N_CALLS_CROSSED (dstno) += num_calls;
1476 REG_N_CALLS_CROSSED (srcno) -= num_calls;
1478 REG_LIVE_LENGTH (dstno) += length;
1479 if (REG_LIVE_LENGTH (srcno) >= 0)
1481 REG_LIVE_LENGTH (srcno) -= length;
1482 /* REG_LIVE_LENGTH is only an approximation after
1483 combine if sched is not run, so make sure that we
1484 still have a reasonable value. */
1485 if (REG_LIVE_LENGTH (srcno) < 2)
1486 REG_LIVE_LENGTH (srcno) = 2;
1489 if (regmove_dump_file)
1490 fprintf (regmove_dump_file,
1491 "Fixed operand %d of insn %d matching operand %d.\n",
1492 op_no, INSN_UID (insn), match_no);
1498 /* If we weren't able to replace any of the alternatives, try an
1499 alternative appoach of copying the source to the destination. */
1500 if (!success && copy_src != NULL_RTX)
1501 copy_src_to_dest (insn, copy_src, copy_dst, old_max_uid);
1506 /* In fixup_match_1, some insns may have been inserted after basic block
1507 ends. Fix that here. */
1512 rtx next = NEXT_INSN (new);
1513 while (next != 0 && INSN_UID (next) >= old_max_uid
1514 && (bb->next_bb == EXIT_BLOCK_PTR || bb->next_bb->head != next))
1515 new = next, next = NEXT_INSN (new);
1521 free (regno_src_regno);
1522 free (regmove_bb_head);
1525 /* Returns nonzero if INSN's pattern has matching constraints for any operand.
1526 Returns 0 if INSN can't be recognized, or if the alternative can't be
1529 Initialize the info in MATCHP based on the constraints. */
1532 find_matches (insn, matchp)
1534 struct match *matchp;
1536 int likely_spilled[MAX_RECOG_OPERANDS];
1538 int any_matches = 0;
1540 extract_insn (insn);
1541 if (! constrain_operands (0))
1544 /* Must initialize this before main loop, because the code for
1545 the commutative case may set matches for operands other than
1547 for (op_no = recog_data.n_operands; --op_no >= 0; )
1548 matchp->with[op_no] = matchp->commutative[op_no] = -1;
1550 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1556 p = recog_data.constraints[op_no];
1558 likely_spilled[op_no] = 0;
1559 matchp->use[op_no] = READ;
1560 matchp->early_clobber[op_no] = 0;
1562 matchp->use[op_no] = WRITE;
1564 matchp->use[op_no] = READWRITE;
1566 for (;*p && i < which_alternative; p++)
1570 while ((c = *p++) != '\0' && c != ',')
1578 matchp->early_clobber[op_no] = 1;
1581 matchp->commutative[op_no] = op_no + 1;
1582 matchp->commutative[op_no + 1] = op_no;
1585 case '0': case '1': case '2': case '3': case '4':
1586 case '5': case '6': case '7': case '8': case '9':
1589 unsigned long match_ul = strtoul (p - 1, &end, 10);
1590 int match = match_ul;
1594 if (match < op_no && likely_spilled[match])
1596 matchp->with[op_no] = match;
1598 if (matchp->commutative[op_no] >= 0)
1599 matchp->with[matchp->commutative[op_no]] = match;
1603 case 'a': case 'b': case 'c': case 'd': case 'e': case 'f': case 'h':
1604 case 'j': case 'k': case 'l': case 'p': case 'q': case 't': case 'u':
1605 case 'v': case 'w': case 'x': case 'y': case 'z': case 'A': case 'B':
1606 case 'C': case 'D': case 'W': case 'Y': case 'Z':
1607 if (CLASS_LIKELY_SPILLED_P (REG_CLASS_FROM_LETTER ((unsigned char) c)))
1608 likely_spilled[op_no] = 1;
1615 /* Try to replace all occurrences of DST_REG with SRC in LOC, that is
1616 assumed to be in INSN. */
1619 replace_in_call_usage (loc, dst_reg, src, insn)
1621 unsigned int dst_reg;
1633 code = GET_CODE (x);
1636 if (REGNO (x) != dst_reg)
1639 validate_change (insn, loc, src, 1);
1644 /* Process each of our operands recursively. */
1645 fmt = GET_RTX_FORMAT (code);
1646 for (i = 0; i < GET_RTX_LENGTH (code); i++, fmt++)
1648 replace_in_call_usage (&XEXP (x, i), dst_reg, src, insn);
1649 else if (*fmt == 'E')
1650 for (j = 0; j < XVECLEN (x, i); j++)
1651 replace_in_call_usage (& XVECEXP (x, i, j), dst_reg, src, insn);
1654 /* Try to replace output operand DST in SET, with input operand SRC. SET is
1655 the only set in INSN. INSN has just been recognized and constrained.
1656 SRC is operand number OPERAND_NUMBER in INSN.
1657 DST is operand number MATCH_NUMBER in INSN.
1658 If BACKWARD is nonzero, we have been called in a backward pass.
1659 Return nonzero for success. */
1662 fixup_match_1 (insn, set, src, src_subreg, dst, backward, operand_number,
1663 match_number, regmove_dump_file)
1664 rtx insn, set, src, src_subreg, dst;
1665 int backward, operand_number, match_number;
1666 FILE *regmove_dump_file;
1669 rtx post_inc = 0, post_inc_set = 0, search_end = 0;
1671 int num_calls = 0, s_num_calls = 0;
1672 enum rtx_code code = NOTE;
1673 HOST_WIDE_INT insn_const = 0, newconst;
1674 rtx overlap = 0; /* need to move insn ? */
1675 rtx src_note = find_reg_note (insn, REG_DEAD, src), dst_note = NULL_RTX;
1676 int length, s_length;
1678 /* If SRC is marked as unchanging, we may not change it.
1679 ??? Maybe we could get better code by removing the unchanging bit
1680 instead, and changing it back if we don't succeed? */
1681 if (RTX_UNCHANGING_P (src))
1686 /* Look for (set (regX) (op regA constX))
1687 (set (regY) (op regA constY))
1689 (set (regA) (op regA constX)).
1690 (set (regY) (op regA constY-constX)).
1691 This works for add and shift operations, if
1692 regA is dead after or set by the second insn. */
1694 code = GET_CODE (SET_SRC (set));
1695 if ((code == PLUS || code == LSHIFTRT
1696 || code == ASHIFT || code == ASHIFTRT)
1697 && XEXP (SET_SRC (set), 0) == src
1698 && GET_CODE (XEXP (SET_SRC (set), 1)) == CONST_INT)
1699 insn_const = INTVAL (XEXP (SET_SRC (set), 1));
1700 else if (! stable_and_no_regs_but_for_p (SET_SRC (set), src, dst))
1703 /* We might find a src_note while scanning. */
1707 if (regmove_dump_file)
1708 fprintf (regmove_dump_file,
1709 "Could fix operand %d of insn %d matching operand %d.\n",
1710 operand_number, INSN_UID (insn), match_number);
1712 /* If SRC is equivalent to a constant set in a different basic block,
1713 then do not use it for this optimization. We want the equivalence
1714 so that if we have to reload this register, we can reload the
1715 constant, rather than extending the lifespan of the register. */
1716 if (reg_is_remote_constant_p (src, insn, get_insns ()))
1719 /* Scan forward to find the next instruction that
1720 uses the output operand. If the operand dies here,
1721 then replace it in both instructions with
1724 for (length = s_length = 0, p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
1726 if (GET_CODE (p) == CALL_INSN)
1727 replace_in_call_usage (& CALL_INSN_FUNCTION_USAGE (p),
1728 REGNO (dst), src, p);
1730 /* ??? We can't scan past the end of a basic block without updating
1731 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
1732 if (perhaps_ends_bb_p (p))
1734 else if (! INSN_P (p))
1741 if (reg_set_p (src, p) || reg_set_p (dst, p)
1742 || (GET_CODE (PATTERN (p)) == USE
1743 && reg_overlap_mentioned_p (src, XEXP (PATTERN (p), 0))))
1746 /* See if all of DST dies in P. This test is
1747 slightly more conservative than it needs to be. */
1748 if ((dst_note = find_regno_note (p, REG_DEAD, REGNO (dst)))
1749 && (GET_MODE (XEXP (dst_note, 0)) == GET_MODE (dst)))
1751 /* If we would be moving INSN, check that we won't move it
1752 into the shadow of a live a live flags register. */
1753 /* ??? We only try to move it in front of P, although
1754 we could move it anywhere between OVERLAP and P. */
1755 if (overlap && GET_MODE (PREV_INSN (p)) != VOIDmode)
1761 rtx set2 = NULL_RTX;
1763 /* If an optimization is done, the value of SRC while P
1764 is executed will be changed. Check that this is OK. */
1765 if (reg_overlap_mentioned_p (src, PATTERN (p)))
1767 for (q = p; q; q = NEXT_INSN (q))
1769 /* ??? We can't scan past the end of a basic block without
1770 updating the register lifetime info
1771 (REG_DEAD/basic_block_live_at_start). */
1772 if (perhaps_ends_bb_p (q))
1777 else if (! INSN_P (q))
1779 else if (reg_overlap_mentioned_p (src, PATTERN (q))
1780 || reg_set_p (src, q))
1784 set2 = single_set (q);
1785 if (! q || ! set2 || GET_CODE (SET_SRC (set2)) != code
1786 || XEXP (SET_SRC (set2), 0) != src
1787 || GET_CODE (XEXP (SET_SRC (set2), 1)) != CONST_INT
1788 || (SET_DEST (set2) != src
1789 && ! find_reg_note (q, REG_DEAD, src)))
1791 /* If this is a PLUS, we can still save a register by doing
1794 src -= insn_const; .
1795 This also gives opportunities for subsequent
1796 optimizations in the backward pass, so do it there. */
1797 if (code == PLUS && backward
1798 /* Don't do this if we can likely tie DST to SET_DEST
1799 of P later; we can't do this tying here if we got a
1801 && ! (dst_note && ! REG_N_CALLS_CROSSED (REGNO (dst))
1803 && GET_CODE (SET_DEST (single_set (p))) == REG
1804 && (REGNO (SET_DEST (single_set (p)))
1805 < FIRST_PSEUDO_REGISTER))
1806 /* We may only emit an insn directly after P if we
1807 are not in the shadow of a live flags register. */
1808 && GET_MODE (p) == VOIDmode)
1813 newconst = -insn_const;
1821 newconst = INTVAL (XEXP (SET_SRC (set2), 1)) - insn_const;
1822 /* Reject out of range shifts. */
1825 || ((unsigned HOST_WIDE_INT) newconst
1826 >= (GET_MODE_BITSIZE (GET_MODE
1827 (SET_SRC (set2)))))))
1832 if (SET_DEST (set2) != src)
1833 post_inc_set = set2;
1836 /* We use 1 as last argument to validate_change so that all
1837 changes are accepted or rejected together by apply_change_group
1838 when it is called by validate_replace_rtx . */
1839 validate_change (q, &XEXP (SET_SRC (set2), 1),
1840 GEN_INT (newconst), 1);
1842 validate_change (insn, recog_data.operand_loc[match_number], src, 1);
1843 if (validate_replace_rtx (dst, src_subreg, p))
1848 if (reg_overlap_mentioned_p (dst, PATTERN (p)))
1850 if (! src_note && reg_overlap_mentioned_p (src, PATTERN (p)))
1852 /* INSN was already checked to be movable wrt. the registers that it
1853 sets / uses when we found no REG_DEAD note for src on it, but it
1854 still might clobber the flags register. We'll have to check that
1855 we won't insert it into the shadow of a live flags register when
1856 we finally know where we are to move it. */
1858 src_note = find_reg_note (p, REG_DEAD, src);
1861 /* If we have passed a call instruction, and the pseudo-reg SRC is not
1862 already live across a call, then don't perform the optimization. */
1863 if (GET_CODE (p) == CALL_INSN)
1865 if (REG_N_CALLS_CROSSED (REGNO (src)) == 0)
1879 /* Remove the death note for DST from P. */
1880 remove_note (p, dst_note);
1883 post_inc = emit_insn_after (copy_rtx (PATTERN (insn)), p);
1884 if ((HAVE_PRE_INCREMENT || HAVE_PRE_DECREMENT)
1886 && try_auto_increment (search_end, post_inc, 0, src, newconst, 1))
1888 validate_change (insn, &XEXP (SET_SRC (set), 1), GEN_INT (insn_const), 0);
1889 REG_N_SETS (REGNO (src))++;
1890 REG_LIVE_LENGTH (REGNO (src))++;
1894 /* The lifetime of src and dest overlap,
1895 but we can change this by moving insn. */
1896 rtx pat = PATTERN (insn);
1898 remove_note (overlap, src_note);
1899 if ((HAVE_POST_INCREMENT || HAVE_POST_DECREMENT)
1901 && try_auto_increment (overlap, insn, 0, src, insn_const, 0))
1905 rtx notes = REG_NOTES (insn);
1907 emit_insn_after_with_line_notes (pat, PREV_INSN (p), insn);
1909 /* emit_insn_after_with_line_notes has no
1910 return value, so search for the new insn. */
1912 while (! INSN_P (insn) || PATTERN (insn) != pat)
1913 insn = PREV_INSN (insn);
1915 REG_NOTES (insn) = notes;
1918 /* Sometimes we'd generate src = const; src += n;
1919 if so, replace the instruction that set src
1920 in the first place. */
1922 if (! overlap && (code == PLUS || code == MINUS))
1924 rtx note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
1925 rtx q, set2 = NULL_RTX;
1926 int num_calls2 = 0, s_length2 = 0;
1928 if (note && CONSTANT_P (XEXP (note, 0)))
1930 for (q = PREV_INSN (insn); q; q = PREV_INSN (q))
1932 /* ??? We can't scan past the end of a basic block without
1933 updating the register lifetime info
1934 (REG_DEAD/basic_block_live_at_start). */
1935 if (perhaps_ends_bb_p (q))
1940 else if (! INSN_P (q))
1944 if (reg_set_p (src, q))
1946 set2 = single_set (q);
1949 if (reg_overlap_mentioned_p (src, PATTERN (q)))
1954 if (GET_CODE (p) == CALL_INSN)
1957 if (q && set2 && SET_DEST (set2) == src && CONSTANT_P (SET_SRC (set2))
1958 && validate_change (insn, &SET_SRC (set), XEXP (note, 0), 0))
1961 REG_N_SETS (REGNO (src))--;
1962 REG_N_CALLS_CROSSED (REGNO (src)) -= num_calls2;
1963 REG_LIVE_LENGTH (REGNO (src)) -= s_length2;
1969 if ((HAVE_PRE_INCREMENT || HAVE_PRE_DECREMENT)
1970 && (code == PLUS || code == MINUS) && insn_const
1971 && try_auto_increment (p, insn, 0, src, insn_const, 1))
1973 else if ((HAVE_POST_INCREMENT || HAVE_POST_DECREMENT)
1975 && try_auto_increment (p, post_inc, post_inc_set, src, newconst, 0))
1977 /* If post_inc still prevails, try to find an
1978 insn where it can be used as a pre-in/decrement.
1979 If code is MINUS, this was already tried. */
1980 if (post_inc && code == PLUS
1981 /* Check that newconst is likely to be usable
1982 in a pre-in/decrement before starting the search. */
1983 && ((HAVE_PRE_INCREMENT && newconst > 0 && newconst <= MOVE_MAX)
1984 || (HAVE_PRE_DECREMENT && newconst < 0 && newconst >= -MOVE_MAX))
1985 && exact_log2 (newconst))
1989 inc_dest = post_inc_set ? SET_DEST (post_inc_set) : src;
1990 for (q = post_inc; (q = NEXT_INSN (q)); )
1992 /* ??? We can't scan past the end of a basic block without updating
1993 the register lifetime info
1994 (REG_DEAD/basic_block_live_at_start). */
1995 if (perhaps_ends_bb_p (q))
1997 else if (! INSN_P (q))
1999 else if (src != inc_dest
2000 && (reg_overlap_mentioned_p (src, PATTERN (q))
2001 || reg_set_p (src, q)))
2003 else if (reg_set_p (inc_dest, q))
2005 else if (reg_overlap_mentioned_p (inc_dest, PATTERN (q)))
2007 try_auto_increment (q, post_inc,
2008 post_inc_set, inc_dest, newconst, 1);
2014 /* Move the death note for DST to INSN if it is used
2016 if (reg_overlap_mentioned_p (dst, PATTERN (insn)))
2018 XEXP (dst_note, 1) = REG_NOTES (insn);
2019 REG_NOTES (insn) = dst_note;
2024 /* Move the death note for SRC from INSN to P. */
2026 remove_note (insn, src_note);
2027 XEXP (src_note, 1) = REG_NOTES (p);
2028 REG_NOTES (p) = src_note;
2030 REG_N_CALLS_CROSSED (REGNO (src)) += s_num_calls;
2033 REG_N_SETS (REGNO (src))++;
2034 REG_N_SETS (REGNO (dst))--;
2036 REG_N_CALLS_CROSSED (REGNO (dst)) -= num_calls;
2038 REG_LIVE_LENGTH (REGNO (src)) += s_length;
2039 if (REG_LIVE_LENGTH (REGNO (dst)) >= 0)
2041 REG_LIVE_LENGTH (REGNO (dst)) -= length;
2042 /* REG_LIVE_LENGTH is only an approximation after
2043 combine if sched is not run, so make sure that we
2044 still have a reasonable value. */
2045 if (REG_LIVE_LENGTH (REGNO (dst)) < 2)
2046 REG_LIVE_LENGTH (REGNO (dst)) = 2;
2048 if (regmove_dump_file)
2049 fprintf (regmove_dump_file,
2050 "Fixed operand %d of insn %d matching operand %d.\n",
2051 operand_number, INSN_UID (insn), match_number);
2056 /* return nonzero if X is stable and mentions no regsiters but for
2057 mentioning SRC or mentioning / changing DST . If in doubt, presume
2059 The rationale is that we want to check if we can move an insn easily
2060 while just paying attention to SRC and DST. A register is considered
2061 stable if it has the RTX_UNCHANGING_P bit set, but that would still
2062 leave the burden to update REG_DEAD / REG_UNUSED notes, so we don't
2063 want any registers but SRC and DST. */
2065 stable_and_no_regs_but_for_p (x, src, dst)
2068 RTX_CODE code = GET_CODE (x);
2069 switch (GET_RTX_CLASS (code))
2071 case '<': case '1': case 'c': case '2': case 'b': case '3':
2074 const char *fmt = GET_RTX_FORMAT (code);
2075 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2077 && ! stable_and_no_regs_but_for_p (XEXP (x, i), src, dst))
2083 return x == src || x == dst;
2084 /* If this is a MEM, look inside - there might be a register hidden in
2085 the address of an unchanging MEM. */
2087 && ! stable_and_no_regs_but_for_p (XEXP (x, 0), src, dst))
2091 return ! rtx_unstable_p (x);
2095 /* Track stack adjustments and stack memory references. Attempt to
2096 reduce the number of stack adjustments by back-propagating across
2097 the memory references.
2099 This is intended primarily for use with targets that do not define
2100 ACCUMULATE_OUTGOING_ARGS. It is of significantly more value to
2101 targets that define PREFERRED_STACK_BOUNDARY more aligned than
2102 STACK_BOUNDARY (e.g. x86), or if not all registers can be pushed
2103 (e.g. x86 fp regs) which would ordinarily have to be implemented
2104 as a sub/mov pair due to restrictions in calls.c.
2106 Propagation stops when any of the insns that need adjusting are
2107 (a) no longer valid because we've exceeded their range, (b) a
2108 non-trivial push instruction, or (c) a call instruction.
2110 Restriction B is based on the assumption that push instructions
2111 are smaller or faster. If a port really wants to remove all
2112 pushes, it should have defined ACCUMULATE_OUTGOING_ARGS. The
2113 one exception that is made is for an add immediately followed
2116 /* This structure records stack memory references between stack adjusting
2121 HOST_WIDE_INT sp_offset;
2123 struct csa_memlist *next;
2126 static int stack_memref_p PARAMS ((rtx));
2127 static rtx single_set_for_csa PARAMS ((rtx));
2128 static void free_csa_memlist PARAMS ((struct csa_memlist *));
2129 static struct csa_memlist *record_one_stack_memref
2130 PARAMS ((rtx, rtx *, struct csa_memlist *));
2131 static int try_apply_stack_adjustment
2132 PARAMS ((rtx, struct csa_memlist *, HOST_WIDE_INT, HOST_WIDE_INT));
2133 static void combine_stack_adjustments_for_block PARAMS ((basic_block));
2134 static int record_stack_memrefs PARAMS ((rtx *, void *));
2137 /* Main entry point for stack adjustment combination. */
2140 combine_stack_adjustments ()
2145 combine_stack_adjustments_for_block (bb);
2148 /* Recognize a MEM of the form (sp) or (plus sp const). */
2154 if (GET_CODE (x) != MEM)
2158 if (x == stack_pointer_rtx)
2160 if (GET_CODE (x) == PLUS
2161 && XEXP (x, 0) == stack_pointer_rtx
2162 && GET_CODE (XEXP (x, 1)) == CONST_INT)
2168 /* Recognize either normal single_set or the hack in i386.md for
2169 tying fp and sp adjustments. */
2172 single_set_for_csa (insn)
2176 rtx tmp = single_set (insn);
2180 if (GET_CODE (insn) != INSN
2181 || GET_CODE (PATTERN (insn)) != PARALLEL)
2184 tmp = PATTERN (insn);
2185 if (GET_CODE (XVECEXP (tmp, 0, 0)) != SET)
2188 for (i = 1; i < XVECLEN (tmp, 0); ++i)
2190 rtx this = XVECEXP (tmp, 0, i);
2192 /* The special case is allowing a no-op set. */
2193 if (GET_CODE (this) == SET
2194 && SET_SRC (this) == SET_DEST (this))
2196 else if (GET_CODE (this) != CLOBBER
2197 && GET_CODE (this) != USE)
2201 return XVECEXP (tmp, 0, 0);
2204 /* Free the list of csa_memlist nodes. */
2207 free_csa_memlist (memlist)
2208 struct csa_memlist *memlist;
2210 struct csa_memlist *next;
2211 for (; memlist ; memlist = next)
2213 next = memlist->next;
2218 /* Create a new csa_memlist node from the given memory reference.
2219 It is already known that the memory is stack_memref_p. */
2221 static struct csa_memlist *
2222 record_one_stack_memref (insn, mem, next_memlist)
2224 struct csa_memlist *next_memlist;
2226 struct csa_memlist *ml;
2228 ml = (struct csa_memlist *) xmalloc (sizeof (*ml));
2230 if (XEXP (*mem, 0) == stack_pointer_rtx)
2233 ml->sp_offset = INTVAL (XEXP (XEXP (*mem, 0), 1));
2237 ml->next = next_memlist;
2242 /* Attempt to apply ADJUST to the stack adjusting insn INSN, as well
2243 as each of the memories in MEMLIST. Return true on success. */
2246 try_apply_stack_adjustment (insn, memlist, new_adjust, delta)
2248 struct csa_memlist *memlist;
2249 HOST_WIDE_INT new_adjust, delta;
2251 struct csa_memlist *ml;
2254 set = single_set_for_csa (insn);
2255 validate_change (insn, &XEXP (SET_SRC (set), 1), GEN_INT (new_adjust), 1);
2257 for (ml = memlist; ml ; ml = ml->next)
2260 replace_equiv_address_nv (*ml->mem,
2261 plus_constant (stack_pointer_rtx,
2262 ml->sp_offset - delta)), 1);
2264 if (apply_change_group ())
2266 /* Succeeded. Update our knowledge of the memory references. */
2267 for (ml = memlist; ml ; ml = ml->next)
2268 ml->sp_offset -= delta;
2276 /* Called via for_each_rtx and used to record all stack memory references in
2277 the insn and discard all other stack pointer references. */
2278 struct record_stack_memrefs_data
2281 struct csa_memlist *memlist;
2285 record_stack_memrefs (xp, data)
2290 struct record_stack_memrefs_data *d =
2291 (struct record_stack_memrefs_data *) data;
2294 switch (GET_CODE (x))
2297 if (!reg_mentioned_p (stack_pointer_rtx, x))
2299 /* We are not able to handle correctly all possible memrefs containing
2300 stack pointer, so this check is necessary. */
2301 if (stack_memref_p (x))
2303 d->memlist = record_one_stack_memref (d->insn, xp, d->memlist);
2308 /* ??? We want be able to handle non-memory stack pointer
2309 references later. For now just discard all insns refering to
2310 stack pointer outside mem expressions. We would probably
2311 want to teach validate_replace to simplify expressions first.
2313 We can't just compare with STACK_POINTER_RTX because the
2314 reference to the stack pointer might be in some other mode.
2315 In particular, an explict clobber in an asm statement will
2316 result in a QImode clober. */
2317 if (REGNO (x) == STACK_POINTER_REGNUM)
2326 /* Subroutine of combine_stack_adjustments, called for each basic block. */
2329 combine_stack_adjustments_for_block (bb)
2332 HOST_WIDE_INT last_sp_adjust = 0;
2333 rtx last_sp_set = NULL_RTX;
2334 struct csa_memlist *memlist = NULL;
2335 rtx insn, next, set;
2336 struct record_stack_memrefs_data data;
2337 bool end_of_block = false;
2339 for (insn = bb->head; !end_of_block ; insn = next)
2341 end_of_block = insn == bb->end;
2342 next = NEXT_INSN (insn);
2344 if (! INSN_P (insn))
2347 set = single_set_for_csa (insn);
2350 rtx dest = SET_DEST (set);
2351 rtx src = SET_SRC (set);
2353 /* Find constant additions to the stack pointer. */
2354 if (dest == stack_pointer_rtx
2355 && GET_CODE (src) == PLUS
2356 && XEXP (src, 0) == stack_pointer_rtx
2357 && GET_CODE (XEXP (src, 1)) == CONST_INT)
2359 HOST_WIDE_INT this_adjust = INTVAL (XEXP (src, 1));
2361 /* If we've not seen an adjustment previously, record
2362 it now and continue. */
2366 last_sp_adjust = this_adjust;
2370 /* If not all recorded memrefs can be adjusted, or the
2371 adjustment is now too large for a constant addition,
2372 we cannot merge the two stack adjustments.
2374 Also we need to be carefull to not move stack pointer
2375 such that we create stack accesses outside the allocated
2376 area. We can combine an allocation into the first insn,
2377 or a deallocation into the second insn. We can not
2378 combine an allocation followed by a deallocation.
2380 The only somewhat frequent occurrence of the later is when
2381 a function allocates a stack frame but does not use it.
2382 For this case, we would need to analyze rtl stream to be
2383 sure that allocated area is really unused. This means not
2384 only checking the memory references, but also all registers
2385 or global memory references possibly containing a stack
2388 Perhaps the best way to address this problem is to teach
2389 gcc not to allocate stack for objects never used. */
2391 /* Combine an allocation into the first instruction. */
2392 if (STACK_GROWS_DOWNWARD ? this_adjust <= 0 : this_adjust >= 0)
2394 if (try_apply_stack_adjustment (last_sp_set, memlist,
2395 last_sp_adjust + this_adjust,
2400 last_sp_adjust += this_adjust;
2405 /* Otherwise we have a deallocation. Do not combine with
2406 a previous allocation. Combine into the second insn. */
2407 else if (STACK_GROWS_DOWNWARD
2408 ? last_sp_adjust >= 0 : last_sp_adjust <= 0)
2410 if (try_apply_stack_adjustment (insn, memlist,
2411 last_sp_adjust + this_adjust,
2415 delete_insn (last_sp_set);
2417 last_sp_adjust += this_adjust;
2418 free_csa_memlist (memlist);
2424 /* Combination failed. Restart processing from here. If
2425 deallocation+allocation conspired to cancel, we can
2426 delete the old deallocation insn. */
2427 if (last_sp_set && last_sp_adjust == 0)
2429 free_csa_memlist (memlist);
2432 last_sp_adjust = this_adjust;
2436 /* Find a predecrement of exactly the previous adjustment and
2437 turn it into a direct store. Obviously we can't do this if
2438 there were any intervening uses of the stack pointer. */
2440 && GET_CODE (dest) == MEM
2441 && ((GET_CODE (XEXP (dest, 0)) == PRE_DEC
2443 == (HOST_WIDE_INT) GET_MODE_SIZE (GET_MODE (dest))))
2444 || (GET_CODE (XEXP (dest, 0)) == PRE_MODIFY
2445 && GET_CODE (XEXP (XEXP (dest, 0), 1)) == PLUS
2446 && XEXP (XEXP (XEXP (dest, 0), 1), 0) == stack_pointer_rtx
2447 && (GET_CODE (XEXP (XEXP (XEXP (dest, 0), 1), 1))
2449 && (INTVAL (XEXP (XEXP (XEXP (dest, 0), 1), 1))
2450 == -last_sp_adjust)))
2451 && XEXP (XEXP (dest, 0), 0) == stack_pointer_rtx
2452 && ! reg_mentioned_p (stack_pointer_rtx, src)
2453 && memory_address_p (GET_MODE (dest), stack_pointer_rtx)
2454 && validate_change (insn, &SET_DEST (set),
2455 replace_equiv_address (dest,
2459 delete_insn (last_sp_set);
2460 free_csa_memlist (memlist);
2462 last_sp_set = NULL_RTX;
2469 data.memlist = memlist;
2470 if (GET_CODE (insn) != CALL_INSN && last_sp_set
2471 && !for_each_rtx (&PATTERN (insn), record_stack_memrefs, &data))
2473 memlist = data.memlist;
2476 memlist = data.memlist;
2478 /* Otherwise, we were not able to process the instruction.
2479 Do not continue collecting data across such a one. */
2481 && (GET_CODE (insn) == CALL_INSN
2482 || reg_mentioned_p (stack_pointer_rtx, PATTERN (insn))))
2484 if (last_sp_set && last_sp_adjust == 0)
2485 delete_insn (last_sp_set);
2486 free_csa_memlist (memlist);
2488 last_sp_set = NULL_RTX;
2493 if (last_sp_set && last_sp_adjust == 0)
2494 delete_insn (last_sp_set);
OSDN Git Service
