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 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) 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 (block = n_basic_blocks - 1; block >= 0; block--)
262 insn = BLOCK_HEAD (block);
263 end = BLOCK_END (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 (BASIC_BLOCK (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);
778 seq = gen_sequence ();
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;
1065 /* ??? Hack. Regmove doesn't examine the CFG, and gets mightily
1066 confused by non-call exceptions ending blocks. */
1067 if (flag_non_call_exceptions)
1070 /* Find out where a potential flags register is live, and so that we
1071 can supress some optimizations in those zones. */
1072 mark_flags_life_zones (discover_flags_reg ());
1074 regno_src_regno = (int *) xmalloc (sizeof *regno_src_regno * nregs);
1075 for (i = nregs; --i >= 0; ) regno_src_regno[i] = -1;
1077 regmove_bb_head = (int *) xmalloc (sizeof (int) * (old_max_uid + 1));
1078 for (i = old_max_uid; i >= 0; i--) regmove_bb_head[i] = -1;
1079 for (i = 0; i < n_basic_blocks; i++)
1080 regmove_bb_head[INSN_UID (BLOCK_HEAD (i))] = i;
1082 /* A forward/backward pass. Replace output operands with input operands. */
1084 for (pass = 0; pass <= 2; pass++)
1086 if (! flag_regmove && pass >= flag_expensive_optimizations)
1089 if (regmove_dump_file)
1090 fprintf (regmove_dump_file, "Starting %s pass...\n",
1091 pass ? "backward" : "forward");
1093 for (insn = pass ? get_last_insn () : f; insn;
1094 insn = pass ? PREV_INSN (insn) : NEXT_INSN (insn))
1097 int op_no, match_no;
1099 set = single_set (insn);
1103 if (flag_expensive_optimizations && ! pass
1104 && (GET_CODE (SET_SRC (set)) == SIGN_EXTEND
1105 || GET_CODE (SET_SRC (set)) == ZERO_EXTEND)
1106 && GET_CODE (XEXP (SET_SRC (set), 0)) == REG
1107 && GET_CODE (SET_DEST(set)) == REG)
1108 optimize_reg_copy_3 (insn, SET_DEST (set), SET_SRC (set));
1110 if (flag_expensive_optimizations && ! pass
1111 && GET_CODE (SET_SRC (set)) == REG
1112 && GET_CODE (SET_DEST(set)) == REG)
1114 /* If this is a register-register copy where SRC is not dead,
1115 see if we can optimize it. If this optimization succeeds,
1116 it will become a copy where SRC is dead. */
1117 if ((find_reg_note (insn, REG_DEAD, SET_SRC (set))
1118 || optimize_reg_copy_1 (insn, SET_DEST (set), SET_SRC (set)))
1119 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
1121 /* Similarly for a pseudo-pseudo copy when SRC is dead. */
1122 if (REGNO (SET_SRC (set)) >= FIRST_PSEUDO_REGISTER)
1123 optimize_reg_copy_2 (insn, SET_DEST (set), SET_SRC (set));
1124 if (regno_src_regno[REGNO (SET_DEST (set))] < 0
1125 && SET_SRC (set) != SET_DEST (set))
1127 int srcregno = REGNO (SET_SRC(set));
1128 if (regno_src_regno[srcregno] >= 0)
1129 srcregno = regno_src_regno[srcregno];
1130 regno_src_regno[REGNO (SET_DEST (set))] = srcregno;
1137 if (! find_matches (insn, &match))
1140 /* Now scan through the operands looking for a source operand
1141 which is supposed to match the destination operand.
1142 Then scan forward for an instruction which uses the dest
1144 If it dies there, then replace the dest in both operands with
1145 the source operand. */
1147 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1149 rtx src, dst, src_subreg;
1150 enum reg_class src_class, dst_class;
1152 match_no = match.with[op_no];
1154 /* Nothing to do if the two operands aren't supposed to match. */
1158 src = recog_data.operand[op_no];
1159 dst = recog_data.operand[match_no];
1161 if (GET_CODE (src) != REG)
1165 if (GET_CODE (dst) == SUBREG
1166 && GET_MODE_SIZE (GET_MODE (dst))
1167 >= GET_MODE_SIZE (GET_MODE (SUBREG_REG (dst))))
1170 = gen_rtx_SUBREG (GET_MODE (SUBREG_REG (dst)),
1171 src, SUBREG_BYTE (dst));
1172 dst = SUBREG_REG (dst);
1174 if (GET_CODE (dst) != REG
1175 || REGNO (dst) < FIRST_PSEUDO_REGISTER)
1178 if (REGNO (src) < FIRST_PSEUDO_REGISTER)
1180 if (match.commutative[op_no] < op_no)
1181 regno_src_regno[REGNO (dst)] = REGNO (src);
1185 if (REG_LIVE_LENGTH (REGNO (src)) < 0)
1188 /* op_no/src must be a read-only operand, and
1189 match_operand/dst must be a write-only operand. */
1190 if (match.use[op_no] != READ
1191 || match.use[match_no] != WRITE)
1194 if (match.early_clobber[match_no]
1195 && count_occurrences (PATTERN (insn), src, 0) > 1)
1198 /* Make sure match_operand is the destination. */
1199 if (recog_data.operand[match_no] != SET_DEST (set))
1202 /* If the operands already match, then there is nothing to do. */
1203 if (operands_match_p (src, dst))
1206 /* But in the commutative case, we might find a better match. */
1207 if (match.commutative[op_no] >= 0)
1209 rtx comm = recog_data.operand[match.commutative[op_no]];
1210 if (operands_match_p (comm, dst)
1211 && (replacement_quality (comm)
1212 >= replacement_quality (src)))
1216 src_class = reg_preferred_class (REGNO (src));
1217 dst_class = reg_preferred_class (REGNO (dst));
1218 if (! regclass_compatible_p (src_class, dst_class))
1221 if (GET_MODE (src) != GET_MODE (dst))
1224 if (fixup_match_1 (insn, set, src, src_subreg, dst, pass,
1232 /* A backward pass. Replace input operands with output operands. */
1234 if (regmove_dump_file)
1235 fprintf (regmove_dump_file, "Starting backward pass...\n");
1237 for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
1241 int op_no, match_no;
1244 if (! find_matches (insn, &match))
1247 /* Now scan through the operands looking for a destination operand
1248 which is supposed to match a source operand.
1249 Then scan backward for an instruction which sets the source
1250 operand. If safe, then replace the source operand with the
1251 dest operand in both instructions. */
1253 copy_src = NULL_RTX;
1254 copy_dst = NULL_RTX;
1255 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1257 rtx set, p, src, dst;
1258 rtx src_note, dst_note;
1260 enum reg_class src_class, dst_class;
1263 match_no = match.with[op_no];
1265 /* Nothing to do if the two operands aren't supposed to match. */
1269 dst = recog_data.operand[match_no];
1270 src = recog_data.operand[op_no];
1272 if (GET_CODE (src) != REG)
1275 if (GET_CODE (dst) != REG
1276 || REGNO (dst) < FIRST_PSEUDO_REGISTER
1277 || REG_LIVE_LENGTH (REGNO (dst)) < 0
1278 || RTX_UNCHANGING_P (dst))
1281 /* If the operands already match, then there is nothing to do. */
1282 if (operands_match_p (src, dst))
1285 if (match.commutative[op_no] >= 0)
1287 rtx comm = recog_data.operand[match.commutative[op_no]];
1288 if (operands_match_p (comm, dst))
1292 set = single_set (insn);
1296 /* Note that single_set ignores parts of a parallel set for
1297 which one of the destinations is REG_UNUSED. We can't
1298 handle that here, since we can wind up rewriting things
1299 such that a single register is set twice within a single
1301 if (reg_set_p (src, insn))
1304 /* match_no/dst must be a write-only operand, and
1305 operand_operand/src must be a read-only operand. */
1306 if (match.use[op_no] != READ
1307 || match.use[match_no] != WRITE)
1310 if (match.early_clobber[match_no]
1311 && count_occurrences (PATTERN (insn), src, 0) > 1)
1314 /* Make sure match_no is the destination. */
1315 if (recog_data.operand[match_no] != SET_DEST (set))
1318 if (REGNO (src) < FIRST_PSEUDO_REGISTER)
1320 if (GET_CODE (SET_SRC (set)) == PLUS
1321 && GET_CODE (XEXP (SET_SRC (set), 1)) == CONST_INT
1322 && XEXP (SET_SRC (set), 0) == src
1323 && fixup_match_2 (insn, dst, src,
1324 XEXP (SET_SRC (set), 1),
1329 src_class = reg_preferred_class (REGNO (src));
1330 dst_class = reg_preferred_class (REGNO (dst));
1331 if (! regclass_compatible_p (src_class, dst_class))
1341 /* Can not modify an earlier insn to set dst if this insn
1342 uses an old value in the source. */
1343 if (reg_overlap_mentioned_p (dst, SET_SRC (set)))
1353 if (! (src_note = find_reg_note (insn, REG_DEAD, src)))
1364 /* If src is set once in a different basic block,
1365 and is set equal to a constant, then do not use
1366 it for this optimization, as this would make it
1367 no longer equivalent to a constant. */
1369 if (reg_is_remote_constant_p (src, insn, f))
1380 if (regmove_dump_file)
1381 fprintf (regmove_dump_file,
1382 "Could fix operand %d of insn %d matching operand %d.\n",
1383 op_no, INSN_UID (insn), match_no);
1385 /* Scan backward to find the first instruction that uses
1386 the input operand. If the operand is set here, then
1387 replace it in both instructions with match_no. */
1389 for (length = 0, p = PREV_INSN (insn); p; p = PREV_INSN (p))
1393 /* ??? We can't scan past the end of a basic block without
1394 updating the register lifetime info
1395 (REG_DEAD/basic_block_live_at_start). */
1396 if (perhaps_ends_bb_p (p))
1398 else if (! INSN_P (p))
1403 /* ??? See if all of SRC is set in P. This test is much
1404 more conservative than it needs to be. */
1405 pset = single_set (p);
1406 if (pset && SET_DEST (pset) == src)
1408 /* We use validate_replace_rtx, in case there
1409 are multiple identical source operands. All of
1410 them have to be changed at the same time. */
1411 if (validate_replace_rtx (src, dst, insn))
1413 if (validate_change (p, &SET_DEST (pset),
1418 /* Change all source operands back.
1419 This modifies the dst as a side-effect. */
1420 validate_replace_rtx (dst, src, insn);
1421 /* Now make sure the dst is right. */
1422 validate_change (insn,
1423 recog_data.operand_loc[match_no],
1430 if (reg_overlap_mentioned_p (src, PATTERN (p))
1431 || reg_overlap_mentioned_p (dst, PATTERN (p)))
1434 /* If we have passed a call instruction, and the
1435 pseudo-reg DST is not already live across a call,
1436 then don't perform the optimization. */
1437 if (GET_CODE (p) == CALL_INSN)
1441 if (REG_N_CALLS_CROSSED (REGNO (dst)) == 0)
1450 /* Remove the death note for SRC from INSN. */
1451 remove_note (insn, src_note);
1452 /* Move the death note for SRC to P if it is used
1454 if (reg_overlap_mentioned_p (src, PATTERN (p)))
1456 XEXP (src_note, 1) = REG_NOTES (p);
1457 REG_NOTES (p) = src_note;
1459 /* If there is a REG_DEAD note for DST on P, then remove
1460 it, because DST is now set there. */
1461 if ((dst_note = find_reg_note (p, REG_DEAD, dst)))
1462 remove_note (p, dst_note);
1464 dstno = REGNO (dst);
1465 srcno = REGNO (src);
1467 REG_N_SETS (dstno)++;
1468 REG_N_SETS (srcno)--;
1470 REG_N_CALLS_CROSSED (dstno) += num_calls;
1471 REG_N_CALLS_CROSSED (srcno) -= num_calls;
1473 REG_LIVE_LENGTH (dstno) += length;
1474 if (REG_LIVE_LENGTH (srcno) >= 0)
1476 REG_LIVE_LENGTH (srcno) -= length;
1477 /* REG_LIVE_LENGTH is only an approximation after
1478 combine if sched is not run, so make sure that we
1479 still have a reasonable value. */
1480 if (REG_LIVE_LENGTH (srcno) < 2)
1481 REG_LIVE_LENGTH (srcno) = 2;
1484 if (regmove_dump_file)
1485 fprintf (regmove_dump_file,
1486 "Fixed operand %d of insn %d matching operand %d.\n",
1487 op_no, INSN_UID (insn), match_no);
1493 /* If we weren't able to replace any of the alternatives, try an
1494 alternative appoach of copying the source to the destination. */
1495 if (!success && copy_src != NULL_RTX)
1496 copy_src_to_dest (insn, copy_src, copy_dst, old_max_uid);
1501 /* In fixup_match_1, some insns may have been inserted after basic block
1502 ends. Fix that here. */
1503 for (i = 0; i < n_basic_blocks; i++)
1505 rtx end = BLOCK_END (i);
1507 rtx next = NEXT_INSN (new);
1508 while (next != 0 && INSN_UID (next) >= old_max_uid
1509 && (i == n_basic_blocks - 1 || BLOCK_HEAD (i + 1) != next))
1510 new = next, next = NEXT_INSN (new);
1511 BLOCK_END (i) = new;
1516 free (regno_src_regno);
1517 free (regmove_bb_head);
1520 /* Returns nonzero if INSN's pattern has matching constraints for any operand.
1521 Returns 0 if INSN can't be recognized, or if the alternative can't be
1524 Initialize the info in MATCHP based on the constraints. */
1527 find_matches (insn, matchp)
1529 struct match *matchp;
1531 int likely_spilled[MAX_RECOG_OPERANDS];
1533 int any_matches = 0;
1535 extract_insn (insn);
1536 if (! constrain_operands (0))
1539 /* Must initialize this before main loop, because the code for
1540 the commutative case may set matches for operands other than
1542 for (op_no = recog_data.n_operands; --op_no >= 0; )
1543 matchp->with[op_no] = matchp->commutative[op_no] = -1;
1545 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1551 p = recog_data.constraints[op_no];
1553 likely_spilled[op_no] = 0;
1554 matchp->use[op_no] = READ;
1555 matchp->early_clobber[op_no] = 0;
1557 matchp->use[op_no] = WRITE;
1559 matchp->use[op_no] = READWRITE;
1561 for (;*p && i < which_alternative; p++)
1565 while ((c = *p++) != '\0' && c != ',')
1573 matchp->early_clobber[op_no] = 1;
1576 matchp->commutative[op_no] = op_no + 1;
1577 matchp->commutative[op_no + 1] = op_no;
1580 case '0': case '1': case '2': case '3': case '4':
1581 case '5': case '6': case '7': case '8': case '9':
1584 unsigned long match = strtoul (p - 1, &end, 10);
1587 if (match < op_no && likely_spilled[match])
1589 matchp->with[op_no] = match;
1591 if (matchp->commutative[op_no] >= 0)
1592 matchp->with[matchp->commutative[op_no]] = match;
1596 case 'a': case 'b': case 'c': case 'd': case 'e': case 'f': case 'h':
1597 case 'j': case 'k': case 'l': case 'p': case 'q': case 't': case 'u':
1598 case 'v': case 'w': case 'x': case 'y': case 'z': case 'A': case 'B':
1599 case 'C': case 'D': case 'W': case 'Y': case 'Z':
1600 if (CLASS_LIKELY_SPILLED_P (REG_CLASS_FROM_LETTER ((unsigned char)c)))
1601 likely_spilled[op_no] = 1;
1608 /* Try to replace all occurrences of DST_REG with SRC in LOC, that is
1609 assumed to be in INSN. */
1612 replace_in_call_usage (loc, dst_reg, src, insn)
1614 unsigned int dst_reg;
1626 code = GET_CODE (x);
1629 if (REGNO (x) != dst_reg)
1632 validate_change (insn, loc, src, 1);
1637 /* Process each of our operands recursively. */
1638 fmt = GET_RTX_FORMAT (code);
1639 for (i = 0; i < GET_RTX_LENGTH (code); i++, fmt++)
1641 replace_in_call_usage (&XEXP (x, i), dst_reg, src, insn);
1642 else if (*fmt == 'E')
1643 for (j = 0; j < XVECLEN (x, i); j++)
1644 replace_in_call_usage (& XVECEXP (x, i, j), dst_reg, src, insn);
1647 /* Try to replace output operand DST in SET, with input operand SRC. SET is
1648 the only set in INSN. INSN has just been recognized and constrained.
1649 SRC is operand number OPERAND_NUMBER in INSN.
1650 DST is operand number MATCH_NUMBER in INSN.
1651 If BACKWARD is nonzero, we have been called in a backward pass.
1652 Return nonzero for success. */
1655 fixup_match_1 (insn, set, src, src_subreg, dst, backward, operand_number,
1656 match_number, regmove_dump_file)
1657 rtx insn, set, src, src_subreg, dst;
1658 int backward, operand_number, match_number;
1659 FILE *regmove_dump_file;
1662 rtx post_inc = 0, post_inc_set = 0, search_end = 0;
1664 int num_calls = 0, s_num_calls = 0;
1665 enum rtx_code code = NOTE;
1666 HOST_WIDE_INT insn_const = 0, newconst;
1667 rtx overlap = 0; /* need to move insn ? */
1668 rtx src_note = find_reg_note (insn, REG_DEAD, src), dst_note = NULL_RTX;
1669 int length, s_length;
1671 /* If SRC is marked as unchanging, we may not change it.
1672 ??? Maybe we could get better code by removing the unchanging bit
1673 instead, and changing it back if we don't succeed? */
1674 if (RTX_UNCHANGING_P (src))
1679 /* Look for (set (regX) (op regA constX))
1680 (set (regY) (op regA constY))
1682 (set (regA) (op regA constX)).
1683 (set (regY) (op regA constY-constX)).
1684 This works for add and shift operations, if
1685 regA is dead after or set by the second insn. */
1687 code = GET_CODE (SET_SRC (set));
1688 if ((code == PLUS || code == LSHIFTRT
1689 || code == ASHIFT || code == ASHIFTRT)
1690 && XEXP (SET_SRC (set), 0) == src
1691 && GET_CODE (XEXP (SET_SRC (set), 1)) == CONST_INT)
1692 insn_const = INTVAL (XEXP (SET_SRC (set), 1));
1693 else if (! stable_and_no_regs_but_for_p (SET_SRC (set), src, dst))
1696 /* We might find a src_note while scanning. */
1700 if (regmove_dump_file)
1701 fprintf (regmove_dump_file,
1702 "Could fix operand %d of insn %d matching operand %d.\n",
1703 operand_number, INSN_UID (insn), match_number);
1705 /* If SRC is equivalent to a constant set in a different basic block,
1706 then do not use it for this optimization. We want the equivalence
1707 so that if we have to reload this register, we can reload the
1708 constant, rather than extending the lifespan of the register. */
1709 if (reg_is_remote_constant_p (src, insn, get_insns ()))
1712 /* Scan forward to find the next instruction that
1713 uses the output operand. If the operand dies here,
1714 then replace it in both instructions with
1717 for (length = s_length = 0, p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
1719 if (GET_CODE (p) == CALL_INSN)
1720 replace_in_call_usage (& CALL_INSN_FUNCTION_USAGE (p),
1721 REGNO (dst), src, p);
1723 /* ??? We can't scan past the end of a basic block without updating
1724 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
1725 if (perhaps_ends_bb_p (p))
1727 else if (! INSN_P (p))
1734 if (reg_set_p (src, p) || reg_set_p (dst, p)
1735 || (GET_CODE (PATTERN (p)) == USE
1736 && reg_overlap_mentioned_p (src, XEXP (PATTERN (p), 0))))
1739 /* See if all of DST dies in P. This test is
1740 slightly more conservative than it needs to be. */
1741 if ((dst_note = find_regno_note (p, REG_DEAD, REGNO (dst)))
1742 && (GET_MODE (XEXP (dst_note, 0)) == GET_MODE (dst)))
1744 /* If we would be moving INSN, check that we won't move it
1745 into the shadow of a live a live flags register. */
1746 /* ??? We only try to move it in front of P, although
1747 we could move it anywhere between OVERLAP and P. */
1748 if (overlap && GET_MODE (PREV_INSN (p)) != VOIDmode)
1754 rtx set2 = NULL_RTX;
1756 /* If an optimization is done, the value of SRC while P
1757 is executed will be changed. Check that this is OK. */
1758 if (reg_overlap_mentioned_p (src, PATTERN (p)))
1760 for (q = p; q; q = NEXT_INSN (q))
1762 /* ??? We can't scan past the end of a basic block without
1763 updating the register lifetime info
1764 (REG_DEAD/basic_block_live_at_start). */
1765 if (perhaps_ends_bb_p (q))
1770 else if (! INSN_P (q))
1772 else if (reg_overlap_mentioned_p (src, PATTERN (q))
1773 || reg_set_p (src, q))
1777 set2 = single_set (q);
1778 if (! q || ! set2 || GET_CODE (SET_SRC (set2)) != code
1779 || XEXP (SET_SRC (set2), 0) != src
1780 || GET_CODE (XEXP (SET_SRC (set2), 1)) != CONST_INT
1781 || (SET_DEST (set2) != src
1782 && ! find_reg_note (q, REG_DEAD, src)))
1784 /* If this is a PLUS, we can still save a register by doing
1787 src -= insn_const; .
1788 This also gives opportunities for subsequent
1789 optimizations in the backward pass, so do it there. */
1790 if (code == PLUS && backward
1791 /* Don't do this if we can likely tie DST to SET_DEST
1792 of P later; we can't do this tying here if we got a
1794 && ! (dst_note && ! REG_N_CALLS_CROSSED (REGNO (dst))
1796 && GET_CODE (SET_DEST (single_set (p))) == REG
1797 && (REGNO (SET_DEST (single_set (p)))
1798 < FIRST_PSEUDO_REGISTER))
1799 /* We may only emit an insn directly after P if we
1800 are not in the shadow of a live flags register. */
1801 && GET_MODE (p) == VOIDmode)
1806 newconst = -insn_const;
1814 newconst = INTVAL (XEXP (SET_SRC (set2), 1)) - insn_const;
1815 /* Reject out of range shifts. */
1818 || ((unsigned HOST_WIDE_INT) newconst
1819 >= (GET_MODE_BITSIZE (GET_MODE
1820 (SET_SRC (set2)))))))
1825 if (SET_DEST (set2) != src)
1826 post_inc_set = set2;
1829 /* We use 1 as last argument to validate_change so that all
1830 changes are accepted or rejected together by apply_change_group
1831 when it is called by validate_replace_rtx . */
1832 validate_change (q, &XEXP (SET_SRC (set2), 1),
1833 GEN_INT (newconst), 1);
1835 validate_change (insn, recog_data.operand_loc[match_number], src, 1);
1836 if (validate_replace_rtx (dst, src_subreg, p))
1841 if (reg_overlap_mentioned_p (dst, PATTERN (p)))
1843 if (! src_note && reg_overlap_mentioned_p (src, PATTERN (p)))
1845 /* INSN was already checked to be movable wrt. the registers that it
1846 sets / uses when we found no REG_DEAD note for src on it, but it
1847 still might clobber the flags register. We'll have to check that
1848 we won't insert it into the shadow of a live flags register when
1849 we finally know where we are to move it. */
1851 src_note = find_reg_note (p, REG_DEAD, src);
1854 /* If we have passed a call instruction, and the pseudo-reg SRC is not
1855 already live across a call, then don't perform the optimization. */
1856 if (GET_CODE (p) == CALL_INSN)
1858 if (REG_N_CALLS_CROSSED (REGNO (src)) == 0)
1872 /* Remove the death note for DST from P. */
1873 remove_note (p, dst_note);
1876 post_inc = emit_insn_after (copy_rtx (PATTERN (insn)), p);
1877 if ((HAVE_PRE_INCREMENT || HAVE_PRE_DECREMENT)
1879 && try_auto_increment (search_end, post_inc, 0, src, newconst, 1))
1881 validate_change (insn, &XEXP (SET_SRC (set), 1), GEN_INT (insn_const), 0);
1882 REG_N_SETS (REGNO (src))++;
1883 REG_LIVE_LENGTH (REGNO (src))++;
1887 /* The lifetime of src and dest overlap,
1888 but we can change this by moving insn. */
1889 rtx pat = PATTERN (insn);
1891 remove_note (overlap, src_note);
1892 if ((HAVE_POST_INCREMENT || HAVE_POST_DECREMENT)
1894 && try_auto_increment (overlap, insn, 0, src, insn_const, 0))
1898 rtx notes = REG_NOTES (insn);
1900 emit_insn_after_with_line_notes (pat, PREV_INSN (p), insn);
1902 /* emit_insn_after_with_line_notes has no
1903 return value, so search for the new insn. */
1905 while (! INSN_P (insn) || PATTERN (insn) != pat)
1906 insn = PREV_INSN (insn);
1908 REG_NOTES (insn) = notes;
1911 /* Sometimes we'd generate src = const; src += n;
1912 if so, replace the instruction that set src
1913 in the first place. */
1915 if (! overlap && (code == PLUS || code == MINUS))
1917 rtx note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
1918 rtx q, set2 = NULL_RTX;
1919 int num_calls2 = 0, s_length2 = 0;
1921 if (note && CONSTANT_P (XEXP (note, 0)))
1923 for (q = PREV_INSN (insn); q; q = PREV_INSN(q))
1925 /* ??? We can't scan past the end of a basic block without
1926 updating the register lifetime info
1927 (REG_DEAD/basic_block_live_at_start). */
1928 if (perhaps_ends_bb_p (q))
1933 else if (! INSN_P (q))
1937 if (reg_set_p (src, q))
1939 set2 = single_set (q);
1942 if (reg_overlap_mentioned_p (src, PATTERN (q)))
1947 if (GET_CODE (p) == CALL_INSN)
1950 if (q && set2 && SET_DEST (set2) == src && CONSTANT_P (SET_SRC (set2))
1951 && validate_change (insn, &SET_SRC (set), XEXP (note, 0), 0))
1954 REG_N_SETS (REGNO (src))--;
1955 REG_N_CALLS_CROSSED (REGNO (src)) -= num_calls2;
1956 REG_LIVE_LENGTH (REGNO (src)) -= s_length2;
1962 if ((HAVE_PRE_INCREMENT || HAVE_PRE_DECREMENT)
1963 && (code == PLUS || code == MINUS) && insn_const
1964 && try_auto_increment (p, insn, 0, src, insn_const, 1))
1966 else if ((HAVE_POST_INCREMENT || HAVE_POST_DECREMENT)
1968 && try_auto_increment (p, post_inc, post_inc_set, src, newconst, 0))
1970 /* If post_inc still prevails, try to find an
1971 insn where it can be used as a pre-in/decrement.
1972 If code is MINUS, this was already tried. */
1973 if (post_inc && code == PLUS
1974 /* Check that newconst is likely to be usable
1975 in a pre-in/decrement before starting the search. */
1976 && ((HAVE_PRE_INCREMENT && newconst > 0 && newconst <= MOVE_MAX)
1977 || (HAVE_PRE_DECREMENT && newconst < 0 && newconst >= -MOVE_MAX))
1978 && exact_log2 (newconst))
1982 inc_dest = post_inc_set ? SET_DEST (post_inc_set) : src;
1983 for (q = post_inc; (q = NEXT_INSN (q)); )
1985 /* ??? We can't scan past the end of a basic block without updating
1986 the register lifetime info
1987 (REG_DEAD/basic_block_live_at_start). */
1988 if (perhaps_ends_bb_p (q))
1990 else if (! INSN_P (q))
1992 else if (src != inc_dest
1993 && (reg_overlap_mentioned_p (src, PATTERN (q))
1994 || reg_set_p (src, q)))
1996 else if (reg_set_p (inc_dest, q))
1998 else if (reg_overlap_mentioned_p (inc_dest, PATTERN (q)))
2000 try_auto_increment (q, post_inc,
2001 post_inc_set, inc_dest, newconst, 1);
2007 /* Move the death note for DST to INSN if it is used
2009 if (reg_overlap_mentioned_p (dst, PATTERN (insn)))
2011 XEXP (dst_note, 1) = REG_NOTES (insn);
2012 REG_NOTES (insn) = dst_note;
2017 /* Move the death note for SRC from INSN to P. */
2019 remove_note (insn, src_note);
2020 XEXP (src_note, 1) = REG_NOTES (p);
2021 REG_NOTES (p) = src_note;
2023 REG_N_CALLS_CROSSED (REGNO (src)) += s_num_calls;
2026 REG_N_SETS (REGNO (src))++;
2027 REG_N_SETS (REGNO (dst))--;
2029 REG_N_CALLS_CROSSED (REGNO (dst)) -= num_calls;
2031 REG_LIVE_LENGTH (REGNO (src)) += s_length;
2032 if (REG_LIVE_LENGTH (REGNO (dst)) >= 0)
2034 REG_LIVE_LENGTH (REGNO (dst)) -= length;
2035 /* REG_LIVE_LENGTH is only an approximation after
2036 combine if sched is not run, so make sure that we
2037 still have a reasonable value. */
2038 if (REG_LIVE_LENGTH (REGNO (dst)) < 2)
2039 REG_LIVE_LENGTH (REGNO (dst)) = 2;
2041 if (regmove_dump_file)
2042 fprintf (regmove_dump_file,
2043 "Fixed operand %d of insn %d matching operand %d.\n",
2044 operand_number, INSN_UID (insn), match_number);
2049 /* return nonzero if X is stable and mentions no regsiters but for
2050 mentioning SRC or mentioning / changing DST . If in doubt, presume
2052 The rationale is that we want to check if we can move an insn easily
2053 while just paying attention to SRC and DST. A register is considered
2054 stable if it has the RTX_UNCHANGING_P bit set, but that would still
2055 leave the burden to update REG_DEAD / REG_UNUSED notes, so we don't
2056 want any registers but SRC and DST. */
2058 stable_and_no_regs_but_for_p (x, src, dst)
2061 RTX_CODE code = GET_CODE (x);
2062 switch (GET_RTX_CLASS (code))
2064 case '<': case '1': case 'c': case '2': case 'b': case '3':
2067 const char *fmt = GET_RTX_FORMAT (code);
2068 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2070 && ! stable_and_no_regs_but_for_p (XEXP (x, i), src, dst))
2076 return x == src || x == dst;
2077 /* If this is a MEM, look inside - there might be a register hidden in
2078 the address of an unchanging MEM. */
2080 && ! stable_and_no_regs_but_for_p (XEXP (x, 0), src, dst))
2084 return ! rtx_unstable_p (x);
2088 /* Track stack adjustments and stack memory references. Attempt to
2089 reduce the number of stack adjustments by back-propagating across
2090 the memory references.
2092 This is intended primarily for use with targets that do not define
2093 ACCUMULATE_OUTGOING_ARGS. It is of significantly more value to
2094 targets that define PREFERRED_STACK_BOUNDARY more aligned than
2095 STACK_BOUNDARY (e.g. x86), or if not all registers can be pushed
2096 (e.g. x86 fp regs) which would ordinarily have to be implemented
2097 as a sub/mov pair due to restrictions in calls.c.
2099 Propagation stops when any of the insns that need adjusting are
2100 (a) no longer valid because we've exceeded their range, (b) a
2101 non-trivial push instruction, or (c) a call instruction.
2103 Restriction B is based on the assumption that push instructions
2104 are smaller or faster. If a port really wants to remove all
2105 pushes, it should have defined ACCUMULATE_OUTGOING_ARGS. The
2106 one exception that is made is for an add immediately followed
2109 /* This structure records stack memory references between stack adjusting
2114 HOST_WIDE_INT sp_offset;
2116 struct csa_memlist *next;
2119 static int stack_memref_p PARAMS ((rtx));
2120 static rtx single_set_for_csa PARAMS ((rtx));
2121 static void free_csa_memlist PARAMS ((struct csa_memlist *));
2122 static struct csa_memlist *record_one_stack_memref
2123 PARAMS ((rtx, rtx *, struct csa_memlist *));
2124 static int try_apply_stack_adjustment
2125 PARAMS ((rtx, struct csa_memlist *, HOST_WIDE_INT, HOST_WIDE_INT));
2126 static void combine_stack_adjustments_for_block PARAMS ((basic_block));
2127 static int record_stack_memrefs PARAMS ((rtx *, void *));
2130 /* Main entry point for stack adjustment combination. */
2133 combine_stack_adjustments ()
2137 for (i = 0; i < n_basic_blocks; ++i)
2138 combine_stack_adjustments_for_block (BASIC_BLOCK (i));
2141 /* Recognize a MEM of the form (sp) or (plus sp const). */
2147 if (GET_CODE (x) != MEM)
2151 if (x == stack_pointer_rtx)
2153 if (GET_CODE (x) == PLUS
2154 && XEXP (x, 0) == stack_pointer_rtx
2155 && GET_CODE (XEXP (x, 1)) == CONST_INT)
2161 /* Recognize either normal single_set or the hack in i386.md for
2162 tying fp and sp adjustments. */
2165 single_set_for_csa (insn)
2169 rtx tmp = single_set (insn);
2173 if (GET_CODE (insn) != INSN
2174 || GET_CODE (PATTERN (insn)) != PARALLEL)
2177 tmp = PATTERN (insn);
2178 if (GET_CODE (XVECEXP (tmp, 0, 0)) != SET)
2181 for (i = 1; i < XVECLEN (tmp, 0); ++i)
2183 rtx this = XVECEXP (tmp, 0, i);
2185 /* The special case is allowing a no-op set. */
2186 if (GET_CODE (this) == SET
2187 && SET_SRC (this) == SET_DEST (this))
2189 else if (GET_CODE (this) != CLOBBER
2190 && GET_CODE (this) != USE)
2194 return XVECEXP (tmp, 0, 0);
2197 /* Free the list of csa_memlist nodes. */
2200 free_csa_memlist (memlist)
2201 struct csa_memlist *memlist;
2203 struct csa_memlist *next;
2204 for (; memlist ; memlist = next)
2206 next = memlist->next;
2211 /* Create a new csa_memlist node from the given memory reference.
2212 It is already known that the memory is stack_memref_p. */
2214 static struct csa_memlist *
2215 record_one_stack_memref (insn, mem, next_memlist)
2217 struct csa_memlist *next_memlist;
2219 struct csa_memlist *ml;
2221 ml = (struct csa_memlist *) xmalloc (sizeof (*ml));
2223 if (XEXP (*mem, 0) == stack_pointer_rtx)
2226 ml->sp_offset = INTVAL (XEXP (XEXP (*mem, 0), 1));
2230 ml->next = next_memlist;
2235 /* Attempt to apply ADJUST to the stack adjusting insn INSN, as well
2236 as each of the memories in MEMLIST. Return true on success. */
2239 try_apply_stack_adjustment (insn, memlist, new_adjust, delta)
2241 struct csa_memlist *memlist;
2242 HOST_WIDE_INT new_adjust, delta;
2244 struct csa_memlist *ml;
2247 set = single_set_for_csa (insn);
2248 validate_change (insn, &XEXP (SET_SRC (set), 1), GEN_INT (new_adjust), 1);
2250 for (ml = memlist; ml ; ml = ml->next)
2253 replace_equiv_address_nv (*ml->mem,
2254 plus_constant (stack_pointer_rtx,
2255 ml->sp_offset - delta)), 1);
2257 if (apply_change_group ())
2259 /* Succeeded. Update our knowledge of the memory references. */
2260 for (ml = memlist; ml ; ml = ml->next)
2261 ml->sp_offset -= delta;
2269 /* Called via for_each_rtx and used to record all stack memory references in
2270 the insn and discard all other stack pointer references. */
2271 struct record_stack_memrefs_data
2274 struct csa_memlist *memlist;
2278 record_stack_memrefs (xp, data)
2283 struct record_stack_memrefs_data *d =
2284 (struct record_stack_memrefs_data *) data;
2287 switch (GET_CODE (x))
2290 if (!reg_mentioned_p (stack_pointer_rtx, x))
2292 /* We are not able to handle correctly all possible memrefs containing
2293 stack pointer, so this check is necessary. */
2294 if (stack_memref_p (x))
2296 d->memlist = record_one_stack_memref (d->insn, xp, d->memlist);
2301 /* ??? We want be able to handle non-memory stack pointer
2302 references later. For now just discard all insns refering to
2303 stack pointer outside mem expressions. We would probably
2304 want to teach validate_replace to simplify expressions first.
2306 We can't just compare with STACK_POINTER_RTX because the
2307 reference to the stack pointer might be in some other mode.
2308 In particular, an explict clobber in an asm statement will
2309 result in a QImode clober. */
2310 if (REGNO (x) == STACK_POINTER_REGNUM)
2319 /* Subroutine of combine_stack_adjustments, called for each basic block. */
2322 combine_stack_adjustments_for_block (bb)
2325 HOST_WIDE_INT last_sp_adjust = 0;
2326 rtx last_sp_set = NULL_RTX;
2327 struct csa_memlist *memlist = NULL;
2330 struct record_stack_memrefs_data data;
2332 for (insn = bb->head; ; insn = next)
2336 pending_delete = NULL_RTX;
2337 next = NEXT_INSN (insn);
2339 if (! INSN_P (insn))
2342 set = single_set_for_csa (insn);
2345 rtx dest = SET_DEST (set);
2346 rtx src = SET_SRC (set);
2348 /* Find constant additions to the stack pointer. */
2349 if (dest == stack_pointer_rtx
2350 && GET_CODE (src) == PLUS
2351 && XEXP (src, 0) == stack_pointer_rtx
2352 && GET_CODE (XEXP (src, 1)) == CONST_INT)
2354 HOST_WIDE_INT this_adjust = INTVAL (XEXP (src, 1));
2356 /* If we've not seen an adjustment previously, record
2357 it now and continue. */
2361 last_sp_adjust = this_adjust;
2365 /* If not all recorded memrefs can be adjusted, or the
2366 adjustment is now too large for a constant addition,
2367 we cannot merge the two stack adjustments.
2369 Also we need to be carefull to not move stack pointer
2370 such that we create stack accesses outside the allocated
2371 area. We can combine an allocation into the first insn,
2372 or a deallocation into the second insn. We can not
2373 combine an allocation followed by a deallocation.
2375 The only somewhat frequent occurrence of the later is when
2376 a function allocates a stack frame but does not use it.
2377 For this case, we would need to analyze rtl stream to be
2378 sure that allocated area is really unused. This means not
2379 only checking the memory references, but also all registers
2380 or global memory references possibly containing a stack
2383 Perhaps the best way to address this problem is to teach
2384 gcc not to allocate stack for objects never used. */
2386 /* Combine an allocation into the first instruction. */
2387 if (STACK_GROWS_DOWNWARD ? this_adjust <= 0 : this_adjust >= 0)
2389 if (try_apply_stack_adjustment (last_sp_set, memlist,
2390 last_sp_adjust + this_adjust,
2394 pending_delete = insn;
2395 last_sp_adjust += this_adjust;
2400 /* Otherwise we have a deallocation. Do not combine with
2401 a previous allocation. Combine into the second insn. */
2402 else if (STACK_GROWS_DOWNWARD
2403 ? last_sp_adjust >= 0 : last_sp_adjust <= 0)
2405 if (try_apply_stack_adjustment (insn, memlist,
2406 last_sp_adjust + this_adjust,
2410 delete_insn (last_sp_set);
2412 last_sp_adjust += this_adjust;
2413 free_csa_memlist (memlist);
2419 /* Combination failed. Restart processing from here. */
2420 free_csa_memlist (memlist);
2423 last_sp_adjust = this_adjust;
2427 /* Find a predecrement of exactly the previous adjustment and
2428 turn it into a direct store. Obviously we can't do this if
2429 there were any intervening uses of the stack pointer. */
2431 && GET_CODE (dest) == MEM
2432 && ((GET_CODE (XEXP (dest, 0)) == PRE_DEC
2434 == (HOST_WIDE_INT) GET_MODE_SIZE (GET_MODE (dest))))
2435 || (GET_CODE (XEXP (dest, 0)) == PRE_MODIFY
2436 && GET_CODE (XEXP (XEXP (dest, 0), 1)) == PLUS
2437 && XEXP (XEXP (XEXP (dest, 0), 1), 0) == stack_pointer_rtx
2438 && (GET_CODE (XEXP (XEXP (XEXP (dest, 0), 1), 1))
2440 && (INTVAL (XEXP (XEXP (XEXP (dest, 0), 1), 1))
2441 == -last_sp_adjust)))
2442 && XEXP (XEXP (dest, 0), 0) == stack_pointer_rtx
2443 && ! reg_mentioned_p (stack_pointer_rtx, src)
2444 && memory_address_p (GET_MODE (dest), stack_pointer_rtx)
2445 && validate_change (insn, &SET_DEST (set),
2446 replace_equiv_address (dest,
2450 if (last_sp_set == bb->head)
2451 bb->head = NEXT_INSN (last_sp_set);
2452 delete_insn (last_sp_set);
2454 free_csa_memlist (memlist);
2456 last_sp_set = NULL_RTX;
2463 data.memlist = memlist;
2464 if (GET_CODE (insn) != CALL_INSN && last_sp_set
2465 && !for_each_rtx (&PATTERN (insn), record_stack_memrefs, &data))
2467 memlist = data.memlist;
2470 memlist = data.memlist;
2472 /* Otherwise, we were not able to process the instruction.
2473 Do not continue collecting data across such a one. */
2475 && (GET_CODE (insn) == CALL_INSN
2476 || reg_mentioned_p (stack_pointer_rtx, PATTERN (insn))))
2478 free_csa_memlist (memlist);
2480 last_sp_set = NULL_RTX;
2485 if (insn == bb->end)
2489 delete_insn (pending_delete);
2493 delete_insn (pending_delete);
OSDN Git Service
