Daily bump.
[official-gcc.git] / gcc / regmove.c
blob182973fb38a7aafa586be83dd2ac976982de0cb0
1 /* Move registers around to reduce number of move instructions needed.
2 Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3 1999, 2000, 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
10 version.
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
15 for more details.
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
20 02111-1307, USA. */
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. */
28 #include "config.h"
29 #include "system.h"
30 #include "coretypes.h"
31 #include "tm.h"
32 #include "rtl.h" /* stdio.h must precede rtl.h for FFS. */
33 #include "tm_p.h"
34 #include "insn-config.h"
35 #include "recog.h"
36 #include "output.h"
37 #include "regs.h"
38 #include "hard-reg-set.h"
39 #include "flags.h"
40 #include "function.h"
41 #include "expr.h"
42 #include "basic-block.h"
43 #include "except.h"
44 #include "toplev.h"
45 #include "reload.h"
48 /* Turn STACK_GROWS_DOWNWARD into a boolean. */
49 #ifdef STACK_GROWS_DOWNWARD
50 #undef STACK_GROWS_DOWNWARD
51 #define STACK_GROWS_DOWNWARD 1
52 #else
53 #define STACK_GROWS_DOWNWARD 0
54 #endif
56 static int perhaps_ends_bb_p (rtx);
57 static int optimize_reg_copy_1 (rtx, rtx, rtx);
58 static void optimize_reg_copy_2 (rtx, rtx, rtx);
59 static void optimize_reg_copy_3 (rtx, rtx, rtx);
60 static void copy_src_to_dest (rtx, rtx, rtx, int);
61 static int *regmove_bb_head;
63 struct match {
64 int with[MAX_RECOG_OPERANDS];
65 enum { READ, WRITE, READWRITE } use[MAX_RECOG_OPERANDS];
66 int commutative[MAX_RECOG_OPERANDS];
67 int early_clobber[MAX_RECOG_OPERANDS];
70 static rtx discover_flags_reg (void);
71 static void mark_flags_life_zones (rtx);
72 static void flags_set_1 (rtx, rtx, void *);
74 static int try_auto_increment (rtx, rtx, rtx, rtx, HOST_WIDE_INT, int);
75 static int find_matches (rtx, struct match *);
76 static void replace_in_call_usage (rtx *, unsigned int, rtx, rtx);
77 static int fixup_match_1 (rtx, rtx, rtx, rtx, rtx, int, int, int, FILE *);
78 static int reg_is_remote_constant_p (rtx, rtx, rtx);
79 static int stable_and_no_regs_but_for_p (rtx, rtx, rtx);
80 static int regclass_compatible_p (int, int);
81 static int replacement_quality (rtx);
82 static int fixup_match_2 (rtx, rtx, rtx, rtx, FILE *);
84 /* Return nonzero if registers with CLASS1 and CLASS2 can be merged without
85 causing too much register allocation problems. */
86 static int
87 regclass_compatible_p (int class0, int class1)
89 return (class0 == class1
90 || (reg_class_subset_p (class0, class1)
91 && ! CLASS_LIKELY_SPILLED_P (class0))
92 || (reg_class_subset_p (class1, class0)
93 && ! CLASS_LIKELY_SPILLED_P (class1)));
96 /* INC_INSN is an instruction that adds INCREMENT to REG.
97 Try to fold INC_INSN as a post/pre in/decrement into INSN.
98 Iff INC_INSN_SET is nonzero, inc_insn has a destination different from src.
99 Return nonzero for success. */
100 static int
101 try_auto_increment (rtx insn, rtx inc_insn, rtx inc_insn_set, rtx reg,
102 HOST_WIDE_INT increment, int pre)
104 enum rtx_code inc_code;
106 rtx pset = single_set (insn);
107 if (pset)
109 /* Can't use the size of SET_SRC, we might have something like
110 (sign_extend:SI (mem:QI ... */
111 rtx use = find_use_as_address (pset, reg, 0);
112 if (use != 0 && use != (rtx) (size_t) 1)
114 int size = GET_MODE_SIZE (GET_MODE (use));
115 if (0
116 || (HAVE_POST_INCREMENT
117 && pre == 0 && (inc_code = POST_INC, increment == size))
118 || (HAVE_PRE_INCREMENT
119 && pre == 1 && (inc_code = PRE_INC, increment == size))
120 || (HAVE_POST_DECREMENT
121 && pre == 0 && (inc_code = POST_DEC, increment == -size))
122 || (HAVE_PRE_DECREMENT
123 && pre == 1 && (inc_code = PRE_DEC, increment == -size))
126 if (inc_insn_set)
127 validate_change
128 (inc_insn,
129 &SET_SRC (inc_insn_set),
130 XEXP (SET_SRC (inc_insn_set), 0), 1);
131 validate_change (insn, &XEXP (use, 0),
132 gen_rtx_fmt_e (inc_code, Pmode, reg), 1);
133 if (apply_change_group ())
135 /* If there is a REG_DEAD note on this insn, we must
136 change this not to REG_UNUSED meaning that the register
137 is set, but the value is dead. Failure to do so will
138 result in a sched1 abort -- when it recomputes lifetime
139 information, the number of REG_DEAD notes will have
140 changed. */
141 rtx note = find_reg_note (insn, REG_DEAD, reg);
142 if (note)
143 PUT_MODE (note, REG_UNUSED);
145 REG_NOTES (insn)
146 = gen_rtx_EXPR_LIST (REG_INC,
147 reg, REG_NOTES (insn));
148 if (! inc_insn_set)
149 delete_insn (inc_insn);
150 return 1;
155 return 0;
158 /* Determine if the pattern generated by add_optab has a clobber,
159 such as might be issued for a flags hard register. To make the
160 code elsewhere simpler, we handle cc0 in this same framework.
162 Return the register if one was discovered. Return NULL_RTX if
163 if no flags were found. Return pc_rtx if we got confused. */
165 static rtx
166 discover_flags_reg (void)
168 rtx tmp;
169 tmp = gen_rtx_REG (word_mode, 10000);
170 tmp = gen_add3_insn (tmp, tmp, const2_rtx);
172 /* If we get something that isn't a simple set, or a
173 [(set ..) (clobber ..)], this whole function will go wrong. */
174 if (GET_CODE (tmp) == SET)
175 return NULL_RTX;
176 else if (GET_CODE (tmp) == PARALLEL)
178 int found;
180 if (XVECLEN (tmp, 0) != 2)
181 return pc_rtx;
182 tmp = XVECEXP (tmp, 0, 1);
183 if (GET_CODE (tmp) != CLOBBER)
184 return pc_rtx;
185 tmp = XEXP (tmp, 0);
187 /* Don't do anything foolish if the md wanted to clobber a
188 scratch or something. We only care about hard regs.
189 Moreover we don't like the notion of subregs of hard regs. */
190 if (GET_CODE (tmp) == SUBREG
191 && REG_P (SUBREG_REG (tmp))
192 && REGNO (SUBREG_REG (tmp)) < FIRST_PSEUDO_REGISTER)
193 return pc_rtx;
194 found = (REG_P (tmp) && REGNO (tmp) < FIRST_PSEUDO_REGISTER);
196 return (found ? tmp : NULL_RTX);
199 return pc_rtx;
202 /* It is a tedious task identifying when the flags register is live and
203 when it is safe to optimize. Since we process the instruction stream
204 multiple times, locate and record these live zones by marking the
205 mode of the instructions --
207 QImode is used on the instruction at which the flags becomes live.
209 HImode is used within the range (exclusive) that the flags are
210 live. Thus the user of the flags is not marked.
212 All other instructions are cleared to VOIDmode. */
214 /* Used to communicate with flags_set_1. */
215 static rtx flags_set_1_rtx;
216 static int flags_set_1_set;
218 static void
219 mark_flags_life_zones (rtx flags)
221 int flags_regno;
222 int flags_nregs;
223 basic_block block;
225 #ifdef HAVE_cc0
226 /* If we found a flags register on a cc0 host, bail. */
227 if (flags == NULL_RTX)
228 flags = cc0_rtx;
229 else if (flags != cc0_rtx)
230 flags = pc_rtx;
231 #endif
233 /* Simple cases first: if no flags, clear all modes. If confusing,
234 mark the entire function as being in a flags shadow. */
235 if (flags == NULL_RTX || flags == pc_rtx)
237 enum machine_mode mode = (flags ? HImode : VOIDmode);
238 rtx insn;
239 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
240 PUT_MODE (insn, mode);
241 return;
244 #ifdef HAVE_cc0
245 flags_regno = -1;
246 flags_nregs = 1;
247 #else
248 flags_regno = REGNO (flags);
249 flags_nregs = hard_regno_nregs[flags_regno][GET_MODE (flags)];
250 #endif
251 flags_set_1_rtx = flags;
253 /* Process each basic block. */
254 FOR_EACH_BB_REVERSE (block)
256 rtx insn, end;
257 int live;
259 insn = BB_HEAD (block);
260 end = BB_END (block);
262 /* Look out for the (unlikely) case of flags being live across
263 basic block boundaries. */
264 live = 0;
265 #ifndef HAVE_cc0
267 int i;
268 for (i = 0; i < flags_nregs; ++i)
269 live |= REGNO_REG_SET_P (block->global_live_at_start,
270 flags_regno + i);
272 #endif
274 while (1)
276 /* Process liveness in reverse order of importance --
277 alive, death, birth. This lets more important info
278 overwrite the mode of lesser info. */
280 if (INSN_P (insn))
282 #ifdef HAVE_cc0
283 /* In the cc0 case, death is not marked in reg notes,
284 but is instead the mere use of cc0 when it is alive. */
285 if (live && reg_mentioned_p (cc0_rtx, PATTERN (insn)))
286 live = 0;
287 #else
288 /* In the hard reg case, we watch death notes. */
289 if (live && find_regno_note (insn, REG_DEAD, flags_regno))
290 live = 0;
291 #endif
292 PUT_MODE (insn, (live ? HImode : VOIDmode));
294 /* In either case, birth is denoted simply by its presence
295 as the destination of a set. */
296 flags_set_1_set = 0;
297 note_stores (PATTERN (insn), flags_set_1, NULL);
298 if (flags_set_1_set)
300 live = 1;
301 PUT_MODE (insn, QImode);
304 else
305 PUT_MODE (insn, (live ? HImode : VOIDmode));
307 if (insn == end)
308 break;
309 insn = NEXT_INSN (insn);
314 /* A subroutine of mark_flags_life_zones, called through note_stores. */
316 static void
317 flags_set_1 (rtx x, rtx pat, void *data ATTRIBUTE_UNUSED)
319 if (GET_CODE (pat) == SET
320 && reg_overlap_mentioned_p (x, flags_set_1_rtx))
321 flags_set_1_set = 1;
324 static int *regno_src_regno;
326 /* Indicate how good a choice REG (which appears as a source) is to replace
327 a destination register with. The higher the returned value, the better
328 the choice. The main objective is to avoid using a register that is
329 a candidate for tying to a hard register, since the output might in
330 turn be a candidate to be tied to a different hard register. */
331 static int
332 replacement_quality (rtx reg)
334 int src_regno;
336 /* Bad if this isn't a register at all. */
337 if (!REG_P (reg))
338 return 0;
340 /* If this register is not meant to get a hard register,
341 it is a poor choice. */
342 if (REG_LIVE_LENGTH (REGNO (reg)) < 0)
343 return 0;
345 src_regno = regno_src_regno[REGNO (reg)];
347 /* If it was not copied from another register, it is fine. */
348 if (src_regno < 0)
349 return 3;
351 /* Copied from a hard register? */
352 if (src_regno < FIRST_PSEUDO_REGISTER)
353 return 1;
355 /* Copied from a pseudo register - not as bad as from a hard register,
356 yet still cumbersome, since the register live length will be lengthened
357 when the registers get tied. */
358 return 2;
361 /* Return 1 if INSN might end a basic block. */
363 static int perhaps_ends_bb_p (rtx insn)
365 switch (GET_CODE (insn))
367 case CODE_LABEL:
368 case JUMP_INSN:
369 /* These always end a basic block. */
370 return 1;
372 case CALL_INSN:
373 /* A CALL_INSN might be the last insn of a basic block, if it is inside
374 an EH region or if there are nonlocal gotos. Note that this test is
375 very conservative. */
376 if (nonlocal_goto_handler_labels)
377 return 1;
378 /* Fall through. */
379 default:
380 return can_throw_internal (insn);
384 /* INSN is a copy from SRC to DEST, both registers, and SRC does not die
385 in INSN.
387 Search forward to see if SRC dies before either it or DEST is modified,
388 but don't scan past the end of a basic block. If so, we can replace SRC
389 with DEST and let SRC die in INSN.
391 This will reduce the number of registers live in that range and may enable
392 DEST to be tied to SRC, thus often saving one register in addition to a
393 register-register copy. */
395 static int
396 optimize_reg_copy_1 (rtx insn, rtx dest, rtx src)
398 rtx p, q;
399 rtx note;
400 rtx dest_death = 0;
401 int sregno = REGNO (src);
402 int dregno = REGNO (dest);
404 /* We don't want to mess with hard regs if register classes are small. */
405 if (sregno == dregno
406 || (SMALL_REGISTER_CLASSES
407 && (sregno < FIRST_PSEUDO_REGISTER
408 || dregno < FIRST_PSEUDO_REGISTER))
409 /* We don't see all updates to SP if they are in an auto-inc memory
410 reference, so we must disallow this optimization on them. */
411 || sregno == STACK_POINTER_REGNUM || dregno == STACK_POINTER_REGNUM)
412 return 0;
414 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
416 /* ??? We can't scan past the end of a basic block without updating
417 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
418 if (perhaps_ends_bb_p (p))
419 break;
420 else if (! INSN_P (p))
421 continue;
423 if (reg_set_p (src, p) || reg_set_p (dest, p)
424 /* If SRC is an asm-declared register, it must not be replaced
425 in any asm. Unfortunately, the REG_EXPR tree for the asm
426 variable may be absent in the SRC rtx, so we can't check the
427 actual register declaration easily (the asm operand will have
428 it, though). To avoid complicating the test for a rare case,
429 we just don't perform register replacement for a hard reg
430 mentioned in an asm. */
431 || (sregno < FIRST_PSEUDO_REGISTER
432 && asm_noperands (PATTERN (p)) >= 0
433 && reg_overlap_mentioned_p (src, PATTERN (p)))
434 /* Don't change hard registers used by a call. */
435 || (CALL_P (p) && sregno < FIRST_PSEUDO_REGISTER
436 && find_reg_fusage (p, USE, src))
437 /* Don't change a USE of a register. */
438 || (GET_CODE (PATTERN (p)) == USE
439 && reg_overlap_mentioned_p (src, XEXP (PATTERN (p), 0))))
440 break;
442 /* See if all of SRC dies in P. This test is slightly more
443 conservative than it needs to be. */
444 if ((note = find_regno_note (p, REG_DEAD, sregno)) != 0
445 && GET_MODE (XEXP (note, 0)) == GET_MODE (src))
447 int failed = 0;
448 int d_length = 0;
449 int s_length = 0;
450 int d_n_calls = 0;
451 int s_n_calls = 0;
453 /* We can do the optimization. Scan forward from INSN again,
454 replacing regs as we go. Set FAILED if a replacement can't
455 be done. In that case, we can't move the death note for SRC.
456 This should be rare. */
458 /* Set to stop at next insn. */
459 for (q = next_real_insn (insn);
460 q != next_real_insn (p);
461 q = next_real_insn (q))
463 if (reg_overlap_mentioned_p (src, PATTERN (q)))
465 /* If SRC is a hard register, we might miss some
466 overlapping registers with validate_replace_rtx,
467 so we would have to undo it. We can't if DEST is
468 present in the insn, so fail in that combination
469 of cases. */
470 if (sregno < FIRST_PSEUDO_REGISTER
471 && reg_mentioned_p (dest, PATTERN (q)))
472 failed = 1;
474 /* Replace all uses and make sure that the register
475 isn't still present. */
476 else if (validate_replace_rtx (src, dest, q)
477 && (sregno >= FIRST_PSEUDO_REGISTER
478 || ! reg_overlap_mentioned_p (src,
479 PATTERN (q))))
481 else
483 validate_replace_rtx (dest, src, q);
484 failed = 1;
488 /* For SREGNO, count the total number of insns scanned.
489 For DREGNO, count the total number of insns scanned after
490 passing the death note for DREGNO. */
491 s_length++;
492 if (dest_death)
493 d_length++;
495 /* If the insn in which SRC dies is a CALL_INSN, don't count it
496 as a call that has been crossed. Otherwise, count it. */
497 if (q != p && CALL_P (q))
499 /* Similarly, total calls for SREGNO, total calls beyond
500 the death note for DREGNO. */
501 s_n_calls++;
502 if (dest_death)
503 d_n_calls++;
506 /* If DEST dies here, remove the death note and save it for
507 later. Make sure ALL of DEST dies here; again, this is
508 overly conservative. */
509 if (dest_death == 0
510 && (dest_death = find_regno_note (q, REG_DEAD, dregno)) != 0)
512 if (GET_MODE (XEXP (dest_death, 0)) != GET_MODE (dest))
513 failed = 1, dest_death = 0;
514 else
515 remove_note (q, dest_death);
519 if (! failed)
521 /* These counters need to be updated if and only if we are
522 going to move the REG_DEAD note. */
523 if (sregno >= FIRST_PSEUDO_REGISTER)
525 if (REG_LIVE_LENGTH (sregno) >= 0)
527 REG_LIVE_LENGTH (sregno) -= s_length;
528 /* REG_LIVE_LENGTH is only an approximation after
529 combine if sched is not run, so make sure that we
530 still have a reasonable value. */
531 if (REG_LIVE_LENGTH (sregno) < 2)
532 REG_LIVE_LENGTH (sregno) = 2;
535 REG_N_CALLS_CROSSED (sregno) -= s_n_calls;
538 /* Move death note of SRC from P to INSN. */
539 remove_note (p, note);
540 XEXP (note, 1) = REG_NOTES (insn);
541 REG_NOTES (insn) = note;
544 /* DEST is also dead if INSN has a REG_UNUSED note for DEST. */
545 if (! dest_death
546 && (dest_death = find_regno_note (insn, REG_UNUSED, dregno)))
548 PUT_REG_NOTE_KIND (dest_death, REG_DEAD);
549 remove_note (insn, dest_death);
552 /* Put death note of DEST on P if we saw it die. */
553 if (dest_death)
555 XEXP (dest_death, 1) = REG_NOTES (p);
556 REG_NOTES (p) = dest_death;
558 if (dregno >= FIRST_PSEUDO_REGISTER)
560 /* If and only if we are moving the death note for DREGNO,
561 then we need to update its counters. */
562 if (REG_LIVE_LENGTH (dregno) >= 0)
563 REG_LIVE_LENGTH (dregno) += d_length;
564 REG_N_CALLS_CROSSED (dregno) += d_n_calls;
568 return ! failed;
571 /* If SRC is a hard register which is set or killed in some other
572 way, we can't do this optimization. */
573 else if (sregno < FIRST_PSEUDO_REGISTER
574 && dead_or_set_p (p, src))
575 break;
577 return 0;
580 /* INSN is a copy of SRC to DEST, in which SRC dies. See if we now have
581 a sequence of insns that modify DEST followed by an insn that sets
582 SRC to DEST in which DEST dies, with no prior modification of DEST.
583 (There is no need to check if the insns in between actually modify
584 DEST. We should not have cases where DEST is not modified, but
585 the optimization is safe if no such modification is detected.)
586 In that case, we can replace all uses of DEST, starting with INSN and
587 ending with the set of SRC to DEST, with SRC. We do not do this
588 optimization if a CALL_INSN is crossed unless SRC already crosses a
589 call or if DEST dies before the copy back to SRC.
591 It is assumed that DEST and SRC are pseudos; it is too complicated to do
592 this for hard registers since the substitutions we may make might fail. */
594 static void
595 optimize_reg_copy_2 (rtx insn, rtx dest, rtx src)
597 rtx p, q;
598 rtx set;
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))
607 break;
608 else if (! INSN_P (p))
609 continue;
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))
620 if (INSN_P (q))
622 if (reg_mentioned_p (dest, PATTERN (q)))
623 PATTERN (q) = replace_rtx (PATTERN (q), dest, src);
626 if (CALL_P (q))
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)--;
637 return;
640 if (reg_set_p (src, p)
641 || find_reg_note (p, REG_DEAD, dest)
642 || (CALL_P (p) && REG_N_CALLS_CROSSED (sregno) == 0))
643 break;
646 /* INSN is a ZERO_EXTEND or SIGN_EXTEND of SRC to DEST.
647 Look if SRC dies there, and if it is only set once, by loading
648 it from memory. If so, try to incorporate the zero/sign extension
649 into the memory read, change SRC to the mode of DEST, and alter
650 the remaining accesses to use the appropriate SUBREG. This allows
651 SRC and DEST to be tied later. */
652 static void
653 optimize_reg_copy_3 (rtx insn, rtx dest, rtx src)
655 rtx src_reg = XEXP (src, 0);
656 int src_no = REGNO (src_reg);
657 int dst_no = REGNO (dest);
658 rtx p, set;
659 enum machine_mode old_mode;
661 if (src_no < FIRST_PSEUDO_REGISTER
662 || dst_no < FIRST_PSEUDO_REGISTER
663 || ! find_reg_note (insn, REG_DEAD, src_reg)
664 || REG_N_DEATHS (src_no) != 1
665 || REG_N_SETS (src_no) != 1)
666 return;
667 for (p = PREV_INSN (insn); p && ! reg_set_p (src_reg, p); p = PREV_INSN (p))
668 /* ??? We can't scan past the end of a basic block without updating
669 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
670 if (perhaps_ends_bb_p (p))
671 break;
673 if (! p)
674 return;
676 if (! (set = single_set (p))
677 || !MEM_P (SET_SRC (set))
678 /* If there's a REG_EQUIV note, this must be an insn that loads an
679 argument. Prefer keeping the note over doing this optimization. */
680 || find_reg_note (p, REG_EQUIV, NULL_RTX)
681 || SET_DEST (set) != src_reg)
682 return;
684 /* Be conservative: although this optimization is also valid for
685 volatile memory references, that could cause trouble in later passes. */
686 if (MEM_VOLATILE_P (SET_SRC (set)))
687 return;
689 /* Do not use a SUBREG to truncate from one mode to another if truncation
690 is not a nop. */
691 if (GET_MODE_BITSIZE (GET_MODE (src_reg)) <= GET_MODE_BITSIZE (GET_MODE (src))
692 && !TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (GET_MODE (src)),
693 GET_MODE_BITSIZE (GET_MODE (src_reg))))
694 return;
696 old_mode = GET_MODE (src_reg);
697 PUT_MODE (src_reg, GET_MODE (src));
698 XEXP (src, 0) = SET_SRC (set);
700 /* Include this change in the group so that it's easily undone if
701 one of the changes in the group is invalid. */
702 validate_change (p, &SET_SRC (set), src, 1);
704 /* Now walk forward making additional replacements. We want to be able
705 to undo all the changes if a later substitution fails. */
706 while (p = NEXT_INSN (p), p != insn)
708 if (! INSN_P (p))
709 continue;
711 /* Make a tentative change. */
712 validate_replace_rtx_group (src_reg,
713 gen_lowpart_SUBREG (old_mode, src_reg),
717 validate_replace_rtx_group (src, src_reg, insn);
719 /* Now see if all the changes are valid. */
720 if (! apply_change_group ())
722 /* One or more changes were no good. Back out everything. */
723 PUT_MODE (src_reg, old_mode);
724 XEXP (src, 0) = src_reg;
726 else
728 rtx note = find_reg_note (p, REG_EQUAL, NULL_RTX);
729 if (note)
730 remove_note (p, note);
735 /* If we were not able to update the users of src to use dest directly, try
736 instead moving the value to dest directly before the operation. */
738 static void
739 copy_src_to_dest (rtx insn, rtx src, rtx dest, int old_max_uid)
741 rtx seq;
742 rtx link;
743 rtx next;
744 rtx set;
745 rtx move_insn;
746 rtx *p_insn_notes;
747 rtx *p_move_notes;
748 int src_regno;
749 int dest_regno;
750 int bb;
751 int insn_uid;
752 int move_uid;
754 /* A REG_LIVE_LENGTH of -1 indicates the register is equivalent to a constant
755 or memory location and is used infrequently; a REG_LIVE_LENGTH of -2 is
756 parameter when there is no frame pointer that is not allocated a register.
757 For now, we just reject them, rather than incrementing the live length. */
759 if (REG_P (src)
760 && REG_LIVE_LENGTH (REGNO (src)) > 0
761 && REG_P (dest)
762 && REG_LIVE_LENGTH (REGNO (dest)) > 0
763 && (set = single_set (insn)) != NULL_RTX
764 && !reg_mentioned_p (dest, SET_SRC (set))
765 && GET_MODE (src) == GET_MODE (dest))
767 int old_num_regs = reg_rtx_no;
769 /* Generate the src->dest move. */
770 start_sequence ();
771 emit_move_insn (dest, src);
772 seq = get_insns ();
773 end_sequence ();
774 /* If this sequence uses new registers, we may not use it. */
775 if (old_num_regs != reg_rtx_no
776 || ! validate_replace_rtx (src, dest, insn))
778 /* We have to restore reg_rtx_no to its old value, lest
779 recompute_reg_usage will try to compute the usage of the
780 new regs, yet reg_n_info is not valid for them. */
781 reg_rtx_no = old_num_regs;
782 return;
784 emit_insn_before (seq, insn);
785 move_insn = PREV_INSN (insn);
786 p_move_notes = &REG_NOTES (move_insn);
787 p_insn_notes = &REG_NOTES (insn);
789 /* Move any notes mentioning src to the move instruction. */
790 for (link = REG_NOTES (insn); link != NULL_RTX; link = next)
792 next = XEXP (link, 1);
793 if (XEXP (link, 0) == src)
795 *p_move_notes = link;
796 p_move_notes = &XEXP (link, 1);
798 else
800 *p_insn_notes = link;
801 p_insn_notes = &XEXP (link, 1);
805 *p_move_notes = NULL_RTX;
806 *p_insn_notes = NULL_RTX;
808 /* Is the insn the head of a basic block? If so extend it. */
809 insn_uid = INSN_UID (insn);
810 move_uid = INSN_UID (move_insn);
811 if (insn_uid < old_max_uid)
813 bb = regmove_bb_head[insn_uid];
814 if (bb >= 0)
816 BB_HEAD (BASIC_BLOCK (bb)) = move_insn;
817 regmove_bb_head[insn_uid] = -1;
821 /* Update the various register tables. */
822 dest_regno = REGNO (dest);
823 REG_N_SETS (dest_regno) ++;
824 REG_LIVE_LENGTH (dest_regno)++;
825 if (REGNO_FIRST_UID (dest_regno) == insn_uid)
826 REGNO_FIRST_UID (dest_regno) = move_uid;
828 src_regno = REGNO (src);
829 if (! find_reg_note (move_insn, REG_DEAD, src))
830 REG_LIVE_LENGTH (src_regno)++;
832 if (REGNO_FIRST_UID (src_regno) == insn_uid)
833 REGNO_FIRST_UID (src_regno) = move_uid;
835 if (REGNO_LAST_UID (src_regno) == insn_uid)
836 REGNO_LAST_UID (src_regno) = move_uid;
841 /* Return whether REG is set in only one location, and is set to a
842 constant, but is set in a different basic block from INSN (an
843 instructions which uses REG). In this case REG is equivalent to a
844 constant, and we don't want to break that equivalence, because that
845 may increase register pressure and make reload harder. If REG is
846 set in the same basic block as INSN, we don't worry about it,
847 because we'll probably need a register anyhow (??? but what if REG
848 is used in a different basic block as well as this one?). FIRST is
849 the first insn in the function. */
851 static int
852 reg_is_remote_constant_p (rtx reg, rtx insn, rtx first)
854 rtx p;
856 if (REG_N_SETS (REGNO (reg)) != 1)
857 return 0;
859 /* Look for the set. */
860 for (p = LOG_LINKS (insn); p; p = XEXP (p, 1))
862 rtx s;
864 if (REG_NOTE_KIND (p) != 0)
865 continue;
866 s = single_set (XEXP (p, 0));
867 if (s != 0
868 && REG_P (SET_DEST (s))
869 && REGNO (SET_DEST (s)) == REGNO (reg))
871 /* The register is set in the same basic block. */
872 return 0;
876 for (p = first; p && p != insn; p = NEXT_INSN (p))
878 rtx s;
880 if (! INSN_P (p))
881 continue;
882 s = single_set (p);
883 if (s != 0
884 && REG_P (SET_DEST (s))
885 && REGNO (SET_DEST (s)) == REGNO (reg))
887 /* This is the instruction which sets REG. If there is a
888 REG_EQUAL note, then REG is equivalent to a constant. */
889 if (find_reg_note (p, REG_EQUAL, NULL_RTX))
890 return 1;
891 return 0;
895 return 0;
898 /* INSN is adding a CONST_INT to a REG. We search backwards looking for
899 another add immediate instruction with the same source and dest registers,
900 and if we find one, we change INSN to an increment, and return 1. If
901 no changes are made, we return 0.
903 This changes
904 (set (reg100) (plus reg1 offset1))
906 (set (reg100) (plus reg1 offset2))
908 (set (reg100) (plus reg1 offset1))
910 (set (reg100) (plus reg100 offset2-offset1)) */
912 /* ??? What does this comment mean? */
913 /* cse disrupts preincrement / postdecrement sequences when it finds a
914 hard register as ultimate source, like the frame pointer. */
916 static int
917 fixup_match_2 (rtx insn, rtx dst, rtx src, rtx offset, FILE *regmove_dump_file)
919 rtx p, dst_death = 0;
920 int length, num_calls = 0;
922 /* If SRC dies in INSN, we'd have to move the death note. This is
923 considered to be very unlikely, so we just skip the optimization
924 in this case. */
925 if (find_regno_note (insn, REG_DEAD, REGNO (src)))
926 return 0;
928 /* Scan backward to find the first instruction that sets DST. */
930 for (length = 0, p = PREV_INSN (insn); p; p = PREV_INSN (p))
932 rtx pset;
934 /* ??? We can't scan past the end of a basic block without updating
935 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
936 if (perhaps_ends_bb_p (p))
937 break;
938 else if (! INSN_P (p))
939 continue;
941 if (find_regno_note (p, REG_DEAD, REGNO (dst)))
942 dst_death = p;
943 if (! dst_death)
944 length++;
946 pset = single_set (p);
947 if (pset && SET_DEST (pset) == dst
948 && GET_CODE (SET_SRC (pset)) == PLUS
949 && XEXP (SET_SRC (pset), 0) == src
950 && GET_CODE (XEXP (SET_SRC (pset), 1)) == CONST_INT)
952 HOST_WIDE_INT newconst
953 = INTVAL (offset) - INTVAL (XEXP (SET_SRC (pset), 1));
954 rtx add = gen_add3_insn (dst, dst, GEN_INT (newconst));
956 if (add && validate_change (insn, &PATTERN (insn), add, 0))
958 /* Remove the death note for DST from DST_DEATH. */
959 if (dst_death)
961 remove_death (REGNO (dst), dst_death);
962 REG_LIVE_LENGTH (REGNO (dst)) += length;
963 REG_N_CALLS_CROSSED (REGNO (dst)) += num_calls;
966 if (regmove_dump_file)
967 fprintf (regmove_dump_file,
968 "Fixed operand of insn %d.\n",
969 INSN_UID (insn));
971 #ifdef AUTO_INC_DEC
972 for (p = PREV_INSN (insn); p; p = PREV_INSN (p))
974 if (LABEL_P (p)
975 || JUMP_P (p))
976 break;
977 if (! INSN_P (p))
978 continue;
979 if (reg_overlap_mentioned_p (dst, PATTERN (p)))
981 if (try_auto_increment (p, insn, 0, dst, newconst, 0))
982 return 1;
983 break;
986 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
988 if (LABEL_P (p)
989 || JUMP_P (p))
990 break;
991 if (! INSN_P (p))
992 continue;
993 if (reg_overlap_mentioned_p (dst, PATTERN (p)))
995 try_auto_increment (p, insn, 0, dst, newconst, 1);
996 break;
999 #endif
1000 return 1;
1004 if (reg_set_p (dst, PATTERN (p)))
1005 break;
1007 /* If we have passed a call instruction, and the
1008 pseudo-reg SRC is not already live across a call,
1009 then don't perform the optimization. */
1010 /* reg_set_p is overly conservative for CALL_INSNS, thinks that all
1011 hard regs are clobbered. Thus, we only use it for src for
1012 non-call insns. */
1013 if (CALL_P (p))
1015 if (! dst_death)
1016 num_calls++;
1018 if (REG_N_CALLS_CROSSED (REGNO (src)) == 0)
1019 break;
1021 if (call_used_regs [REGNO (dst)]
1022 || find_reg_fusage (p, CLOBBER, dst))
1023 break;
1025 else if (reg_set_p (src, PATTERN (p)))
1026 break;
1029 return 0;
1032 /* Main entry for the register move optimization.
1033 F is the first instruction.
1034 NREGS is one plus the highest pseudo-reg number used in the instruction.
1035 REGMOVE_DUMP_FILE is a stream for output of a trace of actions taken
1036 (or 0 if none should be output). */
1038 void
1039 regmove_optimize (rtx f, int nregs, FILE *regmove_dump_file)
1041 int old_max_uid = get_max_uid ();
1042 rtx insn;
1043 struct match match;
1044 int pass;
1045 int i;
1046 rtx copy_src, copy_dst;
1047 basic_block bb;
1049 /* ??? Hack. Regmove doesn't examine the CFG, and gets mightily
1050 confused by non-call exceptions ending blocks. */
1051 if (flag_non_call_exceptions)
1052 return;
1054 /* Find out where a potential flags register is live, and so that we
1055 can suppress some optimizations in those zones. */
1056 mark_flags_life_zones (discover_flags_reg ());
1058 regno_src_regno = xmalloc (sizeof *regno_src_regno * nregs);
1059 for (i = nregs; --i >= 0; ) regno_src_regno[i] = -1;
1061 regmove_bb_head = xmalloc (sizeof (int) * (old_max_uid + 1));
1062 for (i = old_max_uid; i >= 0; i--) regmove_bb_head[i] = -1;
1063 FOR_EACH_BB (bb)
1064 regmove_bb_head[INSN_UID (BB_HEAD (bb))] = bb->index;
1066 /* A forward/backward pass. Replace output operands with input operands. */
1068 for (pass = 0; pass <= 2; pass++)
1070 if (! flag_regmove && pass >= flag_expensive_optimizations)
1071 goto done;
1073 if (regmove_dump_file)
1074 fprintf (regmove_dump_file, "Starting %s pass...\n",
1075 pass ? "backward" : "forward");
1077 for (insn = pass ? get_last_insn () : f; insn;
1078 insn = pass ? PREV_INSN (insn) : NEXT_INSN (insn))
1080 rtx set;
1081 int op_no, match_no;
1083 set = single_set (insn);
1084 if (! set)
1085 continue;
1087 if (flag_expensive_optimizations && ! pass
1088 && (GET_CODE (SET_SRC (set)) == SIGN_EXTEND
1089 || GET_CODE (SET_SRC (set)) == ZERO_EXTEND)
1090 && REG_P (XEXP (SET_SRC (set), 0))
1091 && REG_P (SET_DEST (set)))
1092 optimize_reg_copy_3 (insn, SET_DEST (set), SET_SRC (set));
1094 if (flag_expensive_optimizations && ! pass
1095 && REG_P (SET_SRC (set))
1096 && REG_P (SET_DEST (set)))
1098 /* If this is a register-register copy where SRC is not dead,
1099 see if we can optimize it. If this optimization succeeds,
1100 it will become a copy where SRC is dead. */
1101 if ((find_reg_note (insn, REG_DEAD, SET_SRC (set))
1102 || optimize_reg_copy_1 (insn, SET_DEST (set), SET_SRC (set)))
1103 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
1105 /* Similarly for a pseudo-pseudo copy when SRC is dead. */
1106 if (REGNO (SET_SRC (set)) >= FIRST_PSEUDO_REGISTER)
1107 optimize_reg_copy_2 (insn, SET_DEST (set), SET_SRC (set));
1108 if (regno_src_regno[REGNO (SET_DEST (set))] < 0
1109 && SET_SRC (set) != SET_DEST (set))
1111 int srcregno = REGNO (SET_SRC (set));
1112 if (regno_src_regno[srcregno] >= 0)
1113 srcregno = regno_src_regno[srcregno];
1114 regno_src_regno[REGNO (SET_DEST (set))] = srcregno;
1118 if (! flag_regmove)
1119 continue;
1121 if (! find_matches (insn, &match))
1122 continue;
1124 /* Now scan through the operands looking for a source operand
1125 which is supposed to match the destination operand.
1126 Then scan forward for an instruction which uses the dest
1127 operand.
1128 If it dies there, then replace the dest in both operands with
1129 the source operand. */
1131 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1133 rtx src, dst, src_subreg;
1134 enum reg_class src_class, dst_class;
1136 match_no = match.with[op_no];
1138 /* Nothing to do if the two operands aren't supposed to match. */
1139 if (match_no < 0)
1140 continue;
1142 src = recog_data.operand[op_no];
1143 dst = recog_data.operand[match_no];
1145 if (!REG_P (src))
1146 continue;
1148 src_subreg = src;
1149 if (GET_CODE (dst) == SUBREG
1150 && GET_MODE_SIZE (GET_MODE (dst))
1151 >= GET_MODE_SIZE (GET_MODE (SUBREG_REG (dst))))
1153 dst = SUBREG_REG (dst);
1154 src_subreg = lowpart_subreg (GET_MODE (dst),
1155 src, GET_MODE (src));
1156 if (!src_subreg)
1157 continue;
1159 if (!REG_P (dst)
1160 || REGNO (dst) < FIRST_PSEUDO_REGISTER)
1161 continue;
1163 if (REGNO (src) < FIRST_PSEUDO_REGISTER)
1165 if (match.commutative[op_no] < op_no)
1166 regno_src_regno[REGNO (dst)] = REGNO (src);
1167 continue;
1170 if (REG_LIVE_LENGTH (REGNO (src)) < 0)
1171 continue;
1173 /* op_no/src must be a read-only operand, and
1174 match_operand/dst must be a write-only operand. */
1175 if (match.use[op_no] != READ
1176 || match.use[match_no] != WRITE)
1177 continue;
1179 if (match.early_clobber[match_no]
1180 && count_occurrences (PATTERN (insn), src, 0) > 1)
1181 continue;
1183 /* Make sure match_operand is the destination. */
1184 if (recog_data.operand[match_no] != SET_DEST (set))
1185 continue;
1187 /* If the operands already match, then there is nothing to do. */
1188 if (operands_match_p (src, dst))
1189 continue;
1191 /* But in the commutative case, we might find a better match. */
1192 if (match.commutative[op_no] >= 0)
1194 rtx comm = recog_data.operand[match.commutative[op_no]];
1195 if (operands_match_p (comm, dst)
1196 && (replacement_quality (comm)
1197 >= replacement_quality (src)))
1198 continue;
1201 src_class = reg_preferred_class (REGNO (src));
1202 dst_class = reg_preferred_class (REGNO (dst));
1203 if (! regclass_compatible_p (src_class, dst_class))
1204 continue;
1206 if (GET_MODE (src) != GET_MODE (dst))
1207 continue;
1209 if (fixup_match_1 (insn, set, src, src_subreg, dst, pass,
1210 op_no, match_no,
1211 regmove_dump_file))
1212 break;
1217 /* A backward pass. Replace input operands with output operands. */
1219 if (regmove_dump_file)
1220 fprintf (regmove_dump_file, "Starting backward pass...\n");
1222 for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
1224 if (INSN_P (insn))
1226 int op_no, match_no;
1227 int success = 0;
1229 if (! find_matches (insn, &match))
1230 continue;
1232 /* Now scan through the operands looking for a destination operand
1233 which is supposed to match a source operand.
1234 Then scan backward for an instruction which sets the source
1235 operand. If safe, then replace the source operand with the
1236 dest operand in both instructions. */
1238 copy_src = NULL_RTX;
1239 copy_dst = NULL_RTX;
1240 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1242 rtx set, p, src, dst;
1243 rtx src_note, dst_note;
1244 int num_calls = 0;
1245 enum reg_class src_class, dst_class;
1246 int length;
1248 match_no = match.with[op_no];
1250 /* Nothing to do if the two operands aren't supposed to match. */
1251 if (match_no < 0)
1252 continue;
1254 dst = recog_data.operand[match_no];
1255 src = recog_data.operand[op_no];
1257 if (!REG_P (src))
1258 continue;
1260 if (!REG_P (dst)
1261 || REGNO (dst) < FIRST_PSEUDO_REGISTER
1262 || REG_LIVE_LENGTH (REGNO (dst)) < 0
1263 || GET_MODE (src) != GET_MODE (dst))
1264 continue;
1266 /* If the operands already match, then there is nothing to do. */
1267 if (operands_match_p (src, dst))
1268 continue;
1270 if (match.commutative[op_no] >= 0)
1272 rtx comm = recog_data.operand[match.commutative[op_no]];
1273 if (operands_match_p (comm, dst))
1274 continue;
1277 set = single_set (insn);
1278 if (! set)
1279 continue;
1281 /* Note that single_set ignores parts of a parallel set for
1282 which one of the destinations is REG_UNUSED. We can't
1283 handle that here, since we can wind up rewriting things
1284 such that a single register is set twice within a single
1285 parallel. */
1286 if (reg_set_p (src, insn))
1287 continue;
1289 /* match_no/dst must be a write-only operand, and
1290 operand_operand/src must be a read-only operand. */
1291 if (match.use[op_no] != READ
1292 || match.use[match_no] != WRITE)
1293 continue;
1295 if (match.early_clobber[match_no]
1296 && count_occurrences (PATTERN (insn), src, 0) > 1)
1297 continue;
1299 /* Make sure match_no is the destination. */
1300 if (recog_data.operand[match_no] != SET_DEST (set))
1301 continue;
1303 if (REGNO (src) < FIRST_PSEUDO_REGISTER)
1305 if (GET_CODE (SET_SRC (set)) == PLUS
1306 && GET_CODE (XEXP (SET_SRC (set), 1)) == CONST_INT
1307 && XEXP (SET_SRC (set), 0) == src
1308 && fixup_match_2 (insn, dst, src,
1309 XEXP (SET_SRC (set), 1),
1310 regmove_dump_file))
1311 break;
1312 continue;
1314 src_class = reg_preferred_class (REGNO (src));
1315 dst_class = reg_preferred_class (REGNO (dst));
1317 if (! (src_note = find_reg_note (insn, REG_DEAD, src)))
1319 /* We used to force the copy here like in other cases, but
1320 it produces worse code, as it eliminates no copy
1321 instructions and the copy emitted will be produced by
1322 reload anyway. On patterns with multiple alternatives,
1323 there may be better solution available.
1325 In particular this change produced slower code for numeric
1326 i387 programs. */
1328 continue;
1331 if (! regclass_compatible_p (src_class, dst_class))
1333 if (!copy_src)
1335 copy_src = src;
1336 copy_dst = dst;
1338 continue;
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)))
1345 if (!copy_src)
1347 copy_src = src;
1348 copy_dst = dst;
1350 continue;
1353 /* If src is set once in a different basic block,
1354 and is set equal to a constant, then do not use
1355 it for this optimization, as this would make it
1356 no longer equivalent to a constant. */
1358 if (reg_is_remote_constant_p (src, insn, f))
1360 if (!copy_src)
1362 copy_src = src;
1363 copy_dst = dst;
1365 continue;
1369 if (regmove_dump_file)
1370 fprintf (regmove_dump_file,
1371 "Could fix operand %d of insn %d matching operand %d.\n",
1372 op_no, INSN_UID (insn), match_no);
1374 /* Scan backward to find the first instruction that uses
1375 the input operand. If the operand is set here, then
1376 replace it in both instructions with match_no. */
1378 for (length = 0, p = PREV_INSN (insn); p; p = PREV_INSN (p))
1380 rtx pset;
1382 /* ??? We can't scan past the end of a basic block without
1383 updating the register lifetime info
1384 (REG_DEAD/basic_block_live_at_start). */
1385 if (perhaps_ends_bb_p (p))
1386 break;
1387 else if (! INSN_P (p))
1388 continue;
1390 length++;
1392 /* ??? See if all of SRC is set in P. This test is much
1393 more conservative than it needs to be. */
1394 pset = single_set (p);
1395 if (pset && SET_DEST (pset) == src)
1397 /* We use validate_replace_rtx, in case there
1398 are multiple identical source operands. All of
1399 them have to be changed at the same time. */
1400 if (validate_replace_rtx (src, dst, insn))
1402 if (validate_change (p, &SET_DEST (pset),
1403 dst, 0))
1404 success = 1;
1405 else
1407 /* Change all source operands back.
1408 This modifies the dst as a side-effect. */
1409 validate_replace_rtx (dst, src, insn);
1410 /* Now make sure the dst is right. */
1411 validate_change (insn,
1412 recog_data.operand_loc[match_no],
1413 dst, 0);
1416 break;
1419 if (reg_overlap_mentioned_p (src, PATTERN (p))
1420 || reg_overlap_mentioned_p (dst, PATTERN (p)))
1421 break;
1423 /* If we have passed a call instruction, and the
1424 pseudo-reg DST is not already live across a call,
1425 then don't perform the optimization. */
1426 if (CALL_P (p))
1428 num_calls++;
1430 if (REG_N_CALLS_CROSSED (REGNO (dst)) == 0)
1431 break;
1435 if (success)
1437 int dstno, srcno;
1439 /* Remove the death note for SRC from INSN. */
1440 remove_note (insn, src_note);
1441 /* Move the death note for SRC to P if it is used
1442 there. */
1443 if (reg_overlap_mentioned_p (src, PATTERN (p)))
1445 XEXP (src_note, 1) = REG_NOTES (p);
1446 REG_NOTES (p) = src_note;
1448 /* If there is a REG_DEAD note for DST on P, then remove
1449 it, because DST is now set there. */
1450 if ((dst_note = find_reg_note (p, REG_DEAD, dst)))
1451 remove_note (p, dst_note);
1453 dstno = REGNO (dst);
1454 srcno = REGNO (src);
1456 REG_N_SETS (dstno)++;
1457 REG_N_SETS (srcno)--;
1459 REG_N_CALLS_CROSSED (dstno) += num_calls;
1460 REG_N_CALLS_CROSSED (srcno) -= num_calls;
1462 REG_LIVE_LENGTH (dstno) += length;
1463 if (REG_LIVE_LENGTH (srcno) >= 0)
1465 REG_LIVE_LENGTH (srcno) -= length;
1466 /* REG_LIVE_LENGTH is only an approximation after
1467 combine if sched is not run, so make sure that we
1468 still have a reasonable value. */
1469 if (REG_LIVE_LENGTH (srcno) < 2)
1470 REG_LIVE_LENGTH (srcno) = 2;
1473 if (regmove_dump_file)
1474 fprintf (regmove_dump_file,
1475 "Fixed operand %d of insn %d matching operand %d.\n",
1476 op_no, INSN_UID (insn), match_no);
1478 break;
1482 /* If we weren't able to replace any of the alternatives, try an
1483 alternative approach of copying the source to the destination. */
1484 if (!success && copy_src != NULL_RTX)
1485 copy_src_to_dest (insn, copy_src, copy_dst, old_max_uid);
1490 /* In fixup_match_1, some insns may have been inserted after basic block
1491 ends. Fix that here. */
1492 FOR_EACH_BB (bb)
1494 rtx end = BB_END (bb);
1495 rtx new = end;
1496 rtx next = NEXT_INSN (new);
1497 while (next != 0 && INSN_UID (next) >= old_max_uid
1498 && (bb->next_bb == EXIT_BLOCK_PTR || BB_HEAD (bb->next_bb) != next))
1499 new = next, next = NEXT_INSN (new);
1500 BB_END (bb) = new;
1503 done:
1504 /* Clean up. */
1505 free (regno_src_regno);
1506 free (regmove_bb_head);
1509 /* Returns nonzero if INSN's pattern has matching constraints for any operand.
1510 Returns 0 if INSN can't be recognized, or if the alternative can't be
1511 determined.
1513 Initialize the info in MATCHP based on the constraints. */
1515 static int
1516 find_matches (rtx insn, struct match *matchp)
1518 int likely_spilled[MAX_RECOG_OPERANDS];
1519 int op_no;
1520 int any_matches = 0;
1522 extract_insn (insn);
1523 if (! constrain_operands (0))
1524 return 0;
1526 /* Must initialize this before main loop, because the code for
1527 the commutative case may set matches for operands other than
1528 the current one. */
1529 for (op_no = recog_data.n_operands; --op_no >= 0; )
1530 matchp->with[op_no] = matchp->commutative[op_no] = -1;
1532 for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1534 const char *p;
1535 char c;
1536 int i = 0;
1538 p = recog_data.constraints[op_no];
1540 likely_spilled[op_no] = 0;
1541 matchp->use[op_no] = READ;
1542 matchp->early_clobber[op_no] = 0;
1543 if (*p == '=')
1544 matchp->use[op_no] = WRITE;
1545 else if (*p == '+')
1546 matchp->use[op_no] = READWRITE;
1548 for (;*p && i < which_alternative; p++)
1549 if (*p == ',')
1550 i++;
1552 while ((c = *p) != '\0' && c != ',')
1554 switch (c)
1556 case '=':
1557 break;
1558 case '+':
1559 break;
1560 case '&':
1561 matchp->early_clobber[op_no] = 1;
1562 break;
1563 case '%':
1564 matchp->commutative[op_no] = op_no + 1;
1565 matchp->commutative[op_no + 1] = op_no;
1566 break;
1568 case '0': case '1': case '2': case '3': case '4':
1569 case '5': case '6': case '7': case '8': case '9':
1571 char *end;
1572 unsigned long match_ul = strtoul (p, &end, 10);
1573 int match = match_ul;
1575 p = end;
1577 if (match < op_no && likely_spilled[match])
1578 continue;
1579 matchp->with[op_no] = match;
1580 any_matches = 1;
1581 if (matchp->commutative[op_no] >= 0)
1582 matchp->with[matchp->commutative[op_no]] = match;
1584 continue;
1586 case 'a': case 'b': case 'c': case 'd': case 'e': case 'f': case 'h':
1587 case 'j': case 'k': case 'l': case 'p': case 'q': case 't': case 'u':
1588 case 'v': case 'w': case 'x': case 'y': case 'z': case 'A': case 'B':
1589 case 'C': case 'D': case 'W': case 'Y': case 'Z':
1590 if (CLASS_LIKELY_SPILLED_P (REG_CLASS_FROM_CONSTRAINT ((unsigned char) c, p) ))
1591 likely_spilled[op_no] = 1;
1592 break;
1594 p += CONSTRAINT_LEN (c, p);
1597 return any_matches;
1600 /* Try to replace all occurrences of DST_REG with SRC in LOC, that is
1601 assumed to be in INSN. */
1603 static void
1604 replace_in_call_usage (rtx *loc, unsigned int dst_reg, rtx src, rtx insn)
1606 rtx x = *loc;
1607 enum rtx_code code;
1608 const char *fmt;
1609 int i, j;
1611 if (! x)
1612 return;
1614 code = GET_CODE (x);
1615 if (code == REG)
1617 if (REGNO (x) != dst_reg)
1618 return;
1620 validate_change (insn, loc, src, 1);
1622 return;
1625 /* Process each of our operands recursively. */
1626 fmt = GET_RTX_FORMAT (code);
1627 for (i = 0; i < GET_RTX_LENGTH (code); i++, fmt++)
1628 if (*fmt == 'e')
1629 replace_in_call_usage (&XEXP (x, i), dst_reg, src, insn);
1630 else if (*fmt == 'E')
1631 for (j = 0; j < XVECLEN (x, i); j++)
1632 replace_in_call_usage (& XVECEXP (x, i, j), dst_reg, src, insn);
1635 /* Try to replace output operand DST in SET, with input operand SRC. SET is
1636 the only set in INSN. INSN has just been recognized and constrained.
1637 SRC is operand number OPERAND_NUMBER in INSN.
1638 DST is operand number MATCH_NUMBER in INSN.
1639 If BACKWARD is nonzero, we have been called in a backward pass.
1640 Return nonzero for success. */
1642 static int
1643 fixup_match_1 (rtx insn, rtx set, rtx src, rtx src_subreg, rtx dst,
1644 int backward, int operand_number, int match_number,
1645 FILE *regmove_dump_file)
1647 rtx p;
1648 rtx post_inc = 0, post_inc_set = 0, search_end = 0;
1649 int success = 0;
1650 int num_calls = 0, s_num_calls = 0;
1651 enum rtx_code code = NOTE;
1652 HOST_WIDE_INT insn_const = 0, newconst = 0;
1653 rtx overlap = 0; /* need to move insn ? */
1654 rtx src_note = find_reg_note (insn, REG_DEAD, src), dst_note = NULL_RTX;
1655 int length, s_length;
1657 if (! src_note)
1659 /* Look for (set (regX) (op regA constX))
1660 (set (regY) (op regA constY))
1661 and change that to
1662 (set (regA) (op regA constX)).
1663 (set (regY) (op regA constY-constX)).
1664 This works for add and shift operations, if
1665 regA is dead after or set by the second insn. */
1667 code = GET_CODE (SET_SRC (set));
1668 if ((code == PLUS || code == LSHIFTRT
1669 || code == ASHIFT || code == ASHIFTRT)
1670 && XEXP (SET_SRC (set), 0) == src
1671 && GET_CODE (XEXP (SET_SRC (set), 1)) == CONST_INT)
1672 insn_const = INTVAL (XEXP (SET_SRC (set), 1));
1673 else if (! stable_and_no_regs_but_for_p (SET_SRC (set), src, dst))
1674 return 0;
1675 else
1676 /* We might find a src_note while scanning. */
1677 code = NOTE;
1680 if (regmove_dump_file)
1681 fprintf (regmove_dump_file,
1682 "Could fix operand %d of insn %d matching operand %d.\n",
1683 operand_number, INSN_UID (insn), match_number);
1685 /* If SRC is equivalent to a constant set in a different basic block,
1686 then do not use it for this optimization. We want the equivalence
1687 so that if we have to reload this register, we can reload the
1688 constant, rather than extending the lifespan of the register. */
1689 if (reg_is_remote_constant_p (src, insn, get_insns ()))
1690 return 0;
1692 /* Scan forward to find the next instruction that
1693 uses the output operand. If the operand dies here,
1694 then replace it in both instructions with
1695 operand_number. */
1697 for (length = s_length = 0, p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
1699 if (CALL_P (p))
1700 replace_in_call_usage (& CALL_INSN_FUNCTION_USAGE (p),
1701 REGNO (dst), src, p);
1703 /* ??? We can't scan past the end of a basic block without updating
1704 the register lifetime info (REG_DEAD/basic_block_live_at_start). */
1705 if (perhaps_ends_bb_p (p))
1706 break;
1707 else if (! INSN_P (p))
1708 continue;
1710 length++;
1711 if (src_note)
1712 s_length++;
1714 if (reg_set_p (src, p) || reg_set_p (dst, p)
1715 || (GET_CODE (PATTERN (p)) == USE
1716 && reg_overlap_mentioned_p (src, XEXP (PATTERN (p), 0))))
1717 break;
1719 /* See if all of DST dies in P. This test is
1720 slightly more conservative than it needs to be. */
1721 if ((dst_note = find_regno_note (p, REG_DEAD, REGNO (dst)))
1722 && (GET_MODE (XEXP (dst_note, 0)) == GET_MODE (dst)))
1724 /* If we would be moving INSN, check that we won't move it
1725 into the shadow of a live a live flags register. */
1726 /* ??? We only try to move it in front of P, although
1727 we could move it anywhere between OVERLAP and P. */
1728 if (overlap && GET_MODE (PREV_INSN (p)) != VOIDmode)
1729 break;
1731 if (! src_note)
1733 rtx q;
1734 rtx set2 = NULL_RTX;
1736 /* If an optimization is done, the value of SRC while P
1737 is executed will be changed. Check that this is OK. */
1738 if (reg_overlap_mentioned_p (src, PATTERN (p)))
1739 break;
1740 for (q = p; q; q = NEXT_INSN (q))
1742 /* ??? We can't scan past the end of a basic block without
1743 updating the register lifetime info
1744 (REG_DEAD/basic_block_live_at_start). */
1745 if (perhaps_ends_bb_p (q))
1747 q = 0;
1748 break;
1750 else if (! INSN_P (q))
1751 continue;
1752 else if (reg_overlap_mentioned_p (src, PATTERN (q))
1753 || reg_set_p (src, q))
1754 break;
1756 if (q)
1757 set2 = single_set (q);
1758 if (! q || ! set2 || GET_CODE (SET_SRC (set2)) != code
1759 || XEXP (SET_SRC (set2), 0) != src
1760 || GET_CODE (XEXP (SET_SRC (set2), 1)) != CONST_INT
1761 || (SET_DEST (set2) != src
1762 && ! find_reg_note (q, REG_DEAD, src)))
1764 /* If this is a PLUS, we can still save a register by doing
1765 src += insn_const;
1767 src -= insn_const; .
1768 This also gives opportunities for subsequent
1769 optimizations in the backward pass, so do it there. */
1770 if (code == PLUS && backward
1771 /* Don't do this if we can likely tie DST to SET_DEST
1772 of P later; we can't do this tying here if we got a
1773 hard register. */
1774 && ! (dst_note && ! REG_N_CALLS_CROSSED (REGNO (dst))
1775 && single_set (p)
1776 && REG_P (SET_DEST (single_set (p)))
1777 && (REGNO (SET_DEST (single_set (p)))
1778 < FIRST_PSEUDO_REGISTER))
1779 /* We may only emit an insn directly after P if we
1780 are not in the shadow of a live flags register. */
1781 && GET_MODE (p) == VOIDmode)
1783 search_end = q;
1784 q = insn;
1785 set2 = set;
1786 newconst = -insn_const;
1787 code = MINUS;
1789 else
1790 break;
1792 else
1794 newconst = INTVAL (XEXP (SET_SRC (set2), 1)) - insn_const;
1795 /* Reject out of range shifts. */
1796 if (code != PLUS
1797 && (newconst < 0
1798 || ((unsigned HOST_WIDE_INT) newconst
1799 >= (GET_MODE_BITSIZE (GET_MODE
1800 (SET_SRC (set2)))))))
1801 break;
1802 if (code == PLUS)
1804 post_inc = q;
1805 if (SET_DEST (set2) != src)
1806 post_inc_set = set2;
1809 /* We use 1 as last argument to validate_change so that all
1810 changes are accepted or rejected together by apply_change_group
1811 when it is called by validate_replace_rtx . */
1812 validate_change (q, &XEXP (SET_SRC (set2), 1),
1813 GEN_INT (newconst), 1);
1815 validate_change (insn, recog_data.operand_loc[match_number], src, 1);
1816 if (validate_replace_rtx (dst, src_subreg, p))
1817 success = 1;
1818 break;
1821 if (reg_overlap_mentioned_p (dst, PATTERN (p)))
1822 break;
1823 if (! src_note && reg_overlap_mentioned_p (src, PATTERN (p)))
1825 /* INSN was already checked to be movable wrt. the registers that it
1826 sets / uses when we found no REG_DEAD note for src on it, but it
1827 still might clobber the flags register. We'll have to check that
1828 we won't insert it into the shadow of a live flags register when
1829 we finally know where we are to move it. */
1830 overlap = p;
1831 src_note = find_reg_note (p, REG_DEAD, src);
1834 /* If we have passed a call instruction, and the pseudo-reg SRC is not
1835 already live across a call, then don't perform the optimization. */
1836 if (CALL_P (p))
1838 if (REG_N_CALLS_CROSSED (REGNO (src)) == 0)
1839 break;
1841 num_calls++;
1843 if (src_note)
1844 s_num_calls++;
1849 if (! success)
1850 return 0;
1852 /* Remove the death note for DST from P. */
1853 remove_note (p, dst_note);
1854 if (code == MINUS)
1856 post_inc = emit_insn_after (copy_rtx (PATTERN (insn)), p);
1857 if ((HAVE_PRE_INCREMENT || HAVE_PRE_DECREMENT)
1858 && search_end
1859 && try_auto_increment (search_end, post_inc, 0, src, newconst, 1))
1860 post_inc = 0;
1861 validate_change (insn, &XEXP (SET_SRC (set), 1), GEN_INT (insn_const), 0);
1862 REG_N_SETS (REGNO (src))++;
1863 REG_LIVE_LENGTH (REGNO (src))++;
1865 if (overlap)
1867 /* The lifetime of src and dest overlap,
1868 but we can change this by moving insn. */
1869 rtx pat = PATTERN (insn);
1870 if (src_note)
1871 remove_note (overlap, src_note);
1872 if ((HAVE_POST_INCREMENT || HAVE_POST_DECREMENT)
1873 && code == PLUS
1874 && try_auto_increment (overlap, insn, 0, src, insn_const, 0))
1875 insn = overlap;
1876 else
1878 rtx notes = REG_NOTES (insn);
1880 emit_insn_after_with_line_notes (pat, PREV_INSN (p), insn);
1881 delete_insn (insn);
1882 /* emit_insn_after_with_line_notes has no
1883 return value, so search for the new insn. */
1884 insn = p;
1885 while (! INSN_P (insn) || PATTERN (insn) != pat)
1886 insn = PREV_INSN (insn);
1888 REG_NOTES (insn) = notes;
1891 /* Sometimes we'd generate src = const; src += n;
1892 if so, replace the instruction that set src
1893 in the first place. */
1895 if (! overlap && (code == PLUS || code == MINUS))
1897 rtx note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
1898 rtx q, set2 = NULL_RTX;
1899 int num_calls2 = 0, s_length2 = 0;
1901 if (note && CONSTANT_P (XEXP (note, 0)))
1903 for (q = PREV_INSN (insn); q; q = PREV_INSN (q))
1905 /* ??? We can't scan past the end of a basic block without
1906 updating the register lifetime info
1907 (REG_DEAD/basic_block_live_at_start). */
1908 if (perhaps_ends_bb_p (q))
1910 q = 0;
1911 break;
1913 else if (! INSN_P (q))
1914 continue;
1916 s_length2++;
1917 if (reg_set_p (src, q))
1919 set2 = single_set (q);
1920 break;
1922 if (reg_overlap_mentioned_p (src, PATTERN (q)))
1924 q = 0;
1925 break;
1927 if (CALL_P (p))
1928 num_calls2++;
1930 if (q && set2 && SET_DEST (set2) == src && CONSTANT_P (SET_SRC (set2))
1931 && validate_change (insn, &SET_SRC (set), XEXP (note, 0), 0))
1933 delete_insn (q);
1934 REG_N_SETS (REGNO (src))--;
1935 REG_N_CALLS_CROSSED (REGNO (src)) -= num_calls2;
1936 REG_LIVE_LENGTH (REGNO (src)) -= s_length2;
1937 insn_const = 0;
1942 if ((HAVE_PRE_INCREMENT || HAVE_PRE_DECREMENT)
1943 && (code == PLUS || code == MINUS) && insn_const
1944 && try_auto_increment (p, insn, 0, src, insn_const, 1))
1945 insn = p;
1946 else if ((HAVE_POST_INCREMENT || HAVE_POST_DECREMENT)
1947 && post_inc
1948 && try_auto_increment (p, post_inc, post_inc_set, src, newconst, 0))
1949 post_inc = 0;
1950 /* If post_inc still prevails, try to find an
1951 insn where it can be used as a pre-in/decrement.
1952 If code is MINUS, this was already tried. */
1953 if (post_inc && code == PLUS
1954 /* Check that newconst is likely to be usable
1955 in a pre-in/decrement before starting the search. */
1956 && ((HAVE_PRE_INCREMENT && newconst > 0 && newconst <= MOVE_MAX)
1957 || (HAVE_PRE_DECREMENT && newconst < 0 && newconst >= -MOVE_MAX))
1958 && exact_log2 (newconst))
1960 rtx q, inc_dest;
1962 inc_dest = post_inc_set ? SET_DEST (post_inc_set) : src;
1963 for (q = post_inc; (q = NEXT_INSN (q)); )
1965 /* ??? We can't scan past the end of a basic block without updating
1966 the register lifetime info
1967 (REG_DEAD/basic_block_live_at_start). */
1968 if (perhaps_ends_bb_p (q))
1969 break;
1970 else if (! INSN_P (q))
1971 continue;
1972 else if (src != inc_dest
1973 && (reg_overlap_mentioned_p (src, PATTERN (q))
1974 || reg_set_p (src, q)))
1975 break;
1976 else if (reg_set_p (inc_dest, q))
1977 break;
1978 else if (reg_overlap_mentioned_p (inc_dest, PATTERN (q)))
1980 try_auto_increment (q, post_inc,
1981 post_inc_set, inc_dest, newconst, 1);
1982 break;
1987 /* Move the death note for DST to INSN if it is used
1988 there. */
1989 if (reg_overlap_mentioned_p (dst, PATTERN (insn)))
1991 XEXP (dst_note, 1) = REG_NOTES (insn);
1992 REG_NOTES (insn) = dst_note;
1995 if (src_note)
1997 /* Move the death note for SRC from INSN to P. */
1998 if (! overlap)
1999 remove_note (insn, src_note);
2000 XEXP (src_note, 1) = REG_NOTES (p);
2001 REG_NOTES (p) = src_note;
2003 REG_N_CALLS_CROSSED (REGNO (src)) += s_num_calls;
2006 REG_N_SETS (REGNO (src))++;
2007 REG_N_SETS (REGNO (dst))--;
2009 REG_N_CALLS_CROSSED (REGNO (dst)) -= num_calls;
2011 REG_LIVE_LENGTH (REGNO (src)) += s_length;
2012 if (REG_LIVE_LENGTH (REGNO (dst)) >= 0)
2014 REG_LIVE_LENGTH (REGNO (dst)) -= length;
2015 /* REG_LIVE_LENGTH is only an approximation after
2016 combine if sched is not run, so make sure that we
2017 still have a reasonable value. */
2018 if (REG_LIVE_LENGTH (REGNO (dst)) < 2)
2019 REG_LIVE_LENGTH (REGNO (dst)) = 2;
2021 if (regmove_dump_file)
2022 fprintf (regmove_dump_file,
2023 "Fixed operand %d of insn %d matching operand %d.\n",
2024 operand_number, INSN_UID (insn), match_number);
2025 return 1;
2029 /* Return nonzero if X is stable and mentions no registers but for
2030 mentioning SRC or mentioning / changing DST . If in doubt, presume
2031 it is unstable.
2032 The rationale is that we want to check if we can move an insn easily
2033 while just paying attention to SRC and DST. */
2034 static int
2035 stable_and_no_regs_but_for_p (rtx x, rtx src, rtx dst)
2037 RTX_CODE code = GET_CODE (x);
2038 switch (GET_RTX_CLASS (code))
2040 case RTX_UNARY:
2041 case RTX_BIN_ARITH:
2042 case RTX_COMM_ARITH:
2043 case RTX_COMPARE:
2044 case RTX_COMM_COMPARE:
2045 case RTX_TERNARY:
2046 case RTX_BITFIELD_OPS:
2048 int i;
2049 const char *fmt = GET_RTX_FORMAT (code);
2050 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2051 if (fmt[i] == 'e'
2052 && ! stable_and_no_regs_but_for_p (XEXP (x, i), src, dst))
2053 return 0;
2054 return 1;
2056 case RTX_OBJ:
2057 if (code == REG)
2058 return x == src || x == dst;
2059 /* If this is a MEM, look inside - there might be a register hidden in
2060 the address of an unchanging MEM. */
2061 if (code == MEM
2062 && ! stable_and_no_regs_but_for_p (XEXP (x, 0), src, dst))
2063 return 0;
2064 /* Fall through. */
2065 default:
2066 return ! rtx_unstable_p (x);
2070 /* Track stack adjustments and stack memory references. Attempt to
2071 reduce the number of stack adjustments by back-propagating across
2072 the memory references.
2074 This is intended primarily for use with targets that do not define
2075 ACCUMULATE_OUTGOING_ARGS. It is of significantly more value to
2076 targets that define PREFERRED_STACK_BOUNDARY more aligned than
2077 STACK_BOUNDARY (e.g. x86), or if not all registers can be pushed
2078 (e.g. x86 fp regs) which would ordinarily have to be implemented
2079 as a sub/mov pair due to restrictions in calls.c.
2081 Propagation stops when any of the insns that need adjusting are
2082 (a) no longer valid because we've exceeded their range, (b) a
2083 non-trivial push instruction, or (c) a call instruction.
2085 Restriction B is based on the assumption that push instructions
2086 are smaller or faster. If a port really wants to remove all
2087 pushes, it should have defined ACCUMULATE_OUTGOING_ARGS. The
2088 one exception that is made is for an add immediately followed
2089 by a push. */
2091 /* This structure records stack memory references between stack adjusting
2092 instructions. */
2094 struct csa_memlist
2096 HOST_WIDE_INT sp_offset;
2097 rtx insn, *mem;
2098 struct csa_memlist *next;
2101 static int stack_memref_p (rtx);
2102 static rtx single_set_for_csa (rtx);
2103 static void free_csa_memlist (struct csa_memlist *);
2104 static struct csa_memlist *record_one_stack_memref (rtx, rtx *,
2105 struct csa_memlist *);
2106 static int try_apply_stack_adjustment (rtx, struct csa_memlist *,
2107 HOST_WIDE_INT, HOST_WIDE_INT);
2108 static void combine_stack_adjustments_for_block (basic_block);
2109 static int record_stack_memrefs (rtx *, void *);
2112 /* Main entry point for stack adjustment combination. */
2114 void
2115 combine_stack_adjustments (void)
2117 basic_block bb;
2119 FOR_EACH_BB (bb)
2120 combine_stack_adjustments_for_block (bb);
2123 /* Recognize a MEM of the form (sp) or (plus sp const). */
2125 static int
2126 stack_memref_p (rtx x)
2128 if (!MEM_P (x))
2129 return 0;
2130 x = XEXP (x, 0);
2132 if (x == stack_pointer_rtx)
2133 return 1;
2134 if (GET_CODE (x) == PLUS
2135 && XEXP (x, 0) == stack_pointer_rtx
2136 && GET_CODE (XEXP (x, 1)) == CONST_INT)
2137 return 1;
2139 return 0;
2142 /* Recognize either normal single_set or the hack in i386.md for
2143 tying fp and sp adjustments. */
2145 static rtx
2146 single_set_for_csa (rtx insn)
2148 int i;
2149 rtx tmp = single_set (insn);
2150 if (tmp)
2151 return tmp;
2153 if (!NONJUMP_INSN_P (insn)
2154 || GET_CODE (PATTERN (insn)) != PARALLEL)
2155 return NULL_RTX;
2157 tmp = PATTERN (insn);
2158 if (GET_CODE (XVECEXP (tmp, 0, 0)) != SET)
2159 return NULL_RTX;
2161 for (i = 1; i < XVECLEN (tmp, 0); ++i)
2163 rtx this = XVECEXP (tmp, 0, i);
2165 /* The special case is allowing a no-op set. */
2166 if (GET_CODE (this) == SET
2167 && SET_SRC (this) == SET_DEST (this))
2169 else if (GET_CODE (this) != CLOBBER
2170 && GET_CODE (this) != USE)
2171 return NULL_RTX;
2174 return XVECEXP (tmp, 0, 0);
2177 /* Free the list of csa_memlist nodes. */
2179 static void
2180 free_csa_memlist (struct csa_memlist *memlist)
2182 struct csa_memlist *next;
2183 for (; memlist ; memlist = next)
2185 next = memlist->next;
2186 free (memlist);
2190 /* Create a new csa_memlist node from the given memory reference.
2191 It is already known that the memory is stack_memref_p. */
2193 static struct csa_memlist *
2194 record_one_stack_memref (rtx insn, rtx *mem, struct csa_memlist *next_memlist)
2196 struct csa_memlist *ml;
2198 ml = xmalloc (sizeof (*ml));
2200 if (XEXP (*mem, 0) == stack_pointer_rtx)
2201 ml->sp_offset = 0;
2202 else
2203 ml->sp_offset = INTVAL (XEXP (XEXP (*mem, 0), 1));
2205 ml->insn = insn;
2206 ml->mem = mem;
2207 ml->next = next_memlist;
2209 return ml;
2212 /* Attempt to apply ADJUST to the stack adjusting insn INSN, as well
2213 as each of the memories in MEMLIST. Return true on success. */
2215 static int
2216 try_apply_stack_adjustment (rtx insn, struct csa_memlist *memlist, HOST_WIDE_INT new_adjust,
2217 HOST_WIDE_INT delta)
2219 struct csa_memlist *ml;
2220 rtx set;
2222 set = single_set_for_csa (insn);
2223 validate_change (insn, &XEXP (SET_SRC (set), 1), GEN_INT (new_adjust), 1);
2225 for (ml = memlist; ml ; ml = ml->next)
2226 validate_change
2227 (ml->insn, ml->mem,
2228 replace_equiv_address_nv (*ml->mem,
2229 plus_constant (stack_pointer_rtx,
2230 ml->sp_offset - delta)), 1);
2232 if (apply_change_group ())
2234 /* Succeeded. Update our knowledge of the memory references. */
2235 for (ml = memlist; ml ; ml = ml->next)
2236 ml->sp_offset -= delta;
2238 return 1;
2240 else
2241 return 0;
2244 /* Called via for_each_rtx and used to record all stack memory references in
2245 the insn and discard all other stack pointer references. */
2246 struct record_stack_memrefs_data
2248 rtx insn;
2249 struct csa_memlist *memlist;
2252 static int
2253 record_stack_memrefs (rtx *xp, void *data)
2255 rtx x = *xp;
2256 struct record_stack_memrefs_data *d =
2257 (struct record_stack_memrefs_data *) data;
2258 if (!x)
2259 return 0;
2260 switch (GET_CODE (x))
2262 case MEM:
2263 if (!reg_mentioned_p (stack_pointer_rtx, x))
2264 return -1;
2265 /* We are not able to handle correctly all possible memrefs containing
2266 stack pointer, so this check is necessary. */
2267 if (stack_memref_p (x))
2269 d->memlist = record_one_stack_memref (d->insn, xp, d->memlist);
2270 return -1;
2272 return 1;
2273 case REG:
2274 /* ??? We want be able to handle non-memory stack pointer
2275 references later. For now just discard all insns referring to
2276 stack pointer outside mem expressions. We would probably
2277 want to teach validate_replace to simplify expressions first.
2279 We can't just compare with STACK_POINTER_RTX because the
2280 reference to the stack pointer might be in some other mode.
2281 In particular, an explicit clobber in an asm statement will
2282 result in a QImode clobber. */
2283 if (REGNO (x) == STACK_POINTER_REGNUM)
2284 return 1;
2285 break;
2286 default:
2287 break;
2289 return 0;
2292 /* Subroutine of combine_stack_adjustments, called for each basic block. */
2294 static void
2295 combine_stack_adjustments_for_block (basic_block bb)
2297 HOST_WIDE_INT last_sp_adjust = 0;
2298 rtx last_sp_set = NULL_RTX;
2299 struct csa_memlist *memlist = NULL;
2300 rtx insn, next, set;
2301 struct record_stack_memrefs_data data;
2302 bool end_of_block = false;
2304 for (insn = BB_HEAD (bb); !end_of_block ; insn = next)
2306 end_of_block = insn == BB_END (bb);
2307 next = NEXT_INSN (insn);
2309 if (! INSN_P (insn))
2310 continue;
2312 set = single_set_for_csa (insn);
2313 if (set)
2315 rtx dest = SET_DEST (set);
2316 rtx src = SET_SRC (set);
2318 /* Find constant additions to the stack pointer. */
2319 if (dest == stack_pointer_rtx
2320 && GET_CODE (src) == PLUS
2321 && XEXP (src, 0) == stack_pointer_rtx
2322 && GET_CODE (XEXP (src, 1)) == CONST_INT)
2324 HOST_WIDE_INT this_adjust = INTVAL (XEXP (src, 1));
2326 /* If we've not seen an adjustment previously, record
2327 it now and continue. */
2328 if (! last_sp_set)
2330 last_sp_set = insn;
2331 last_sp_adjust = this_adjust;
2332 continue;
2335 /* If not all recorded memrefs can be adjusted, or the
2336 adjustment is now too large for a constant addition,
2337 we cannot merge the two stack adjustments.
2339 Also we need to be careful to not move stack pointer
2340 such that we create stack accesses outside the allocated
2341 area. We can combine an allocation into the first insn,
2342 or a deallocation into the second insn. We can not
2343 combine an allocation followed by a deallocation.
2345 The only somewhat frequent occurrence of the later is when
2346 a function allocates a stack frame but does not use it.
2347 For this case, we would need to analyze rtl stream to be
2348 sure that allocated area is really unused. This means not
2349 only checking the memory references, but also all registers
2350 or global memory references possibly containing a stack
2351 frame address.
2353 Perhaps the best way to address this problem is to teach
2354 gcc not to allocate stack for objects never used. */
2356 /* Combine an allocation into the first instruction. */
2357 if (STACK_GROWS_DOWNWARD ? this_adjust <= 0 : this_adjust >= 0)
2359 if (try_apply_stack_adjustment (last_sp_set, memlist,
2360 last_sp_adjust + this_adjust,
2361 this_adjust))
2363 /* It worked! */
2364 delete_insn (insn);
2365 last_sp_adjust += this_adjust;
2366 continue;
2370 /* Otherwise we have a deallocation. Do not combine with
2371 a previous allocation. Combine into the second insn. */
2372 else if (STACK_GROWS_DOWNWARD
2373 ? last_sp_adjust >= 0 : last_sp_adjust <= 0)
2375 if (try_apply_stack_adjustment (insn, memlist,
2376 last_sp_adjust + this_adjust,
2377 -last_sp_adjust))
2379 /* It worked! */
2380 delete_insn (last_sp_set);
2381 last_sp_set = insn;
2382 last_sp_adjust += this_adjust;
2383 free_csa_memlist (memlist);
2384 memlist = NULL;
2385 continue;
2389 /* Combination failed. Restart processing from here. If
2390 deallocation+allocation conspired to cancel, we can
2391 delete the old deallocation insn. */
2392 if (last_sp_set && last_sp_adjust == 0)
2393 delete_insn (insn);
2394 free_csa_memlist (memlist);
2395 memlist = NULL;
2396 last_sp_set = insn;
2397 last_sp_adjust = this_adjust;
2398 continue;
2401 /* Find a predecrement of exactly the previous adjustment and
2402 turn it into a direct store. Obviously we can't do this if
2403 there were any intervening uses of the stack pointer. */
2404 if (memlist == NULL
2405 && MEM_P (dest)
2406 && ((GET_CODE (XEXP (dest, 0)) == PRE_DEC
2407 && (last_sp_adjust
2408 == (HOST_WIDE_INT) GET_MODE_SIZE (GET_MODE (dest))))
2409 || (GET_CODE (XEXP (dest, 0)) == PRE_MODIFY
2410 && GET_CODE (XEXP (XEXP (dest, 0), 1)) == PLUS
2411 && XEXP (XEXP (XEXP (dest, 0), 1), 0) == stack_pointer_rtx
2412 && (GET_CODE (XEXP (XEXP (XEXP (dest, 0), 1), 1))
2413 == CONST_INT)
2414 && (INTVAL (XEXP (XEXP (XEXP (dest, 0), 1), 1))
2415 == -last_sp_adjust)))
2416 && XEXP (XEXP (dest, 0), 0) == stack_pointer_rtx
2417 && ! reg_mentioned_p (stack_pointer_rtx, src)
2418 && memory_address_p (GET_MODE (dest), stack_pointer_rtx)
2419 && validate_change (insn, &SET_DEST (set),
2420 replace_equiv_address (dest,
2421 stack_pointer_rtx),
2424 delete_insn (last_sp_set);
2425 free_csa_memlist (memlist);
2426 memlist = NULL;
2427 last_sp_set = NULL_RTX;
2428 last_sp_adjust = 0;
2429 continue;
2433 data.insn = insn;
2434 data.memlist = memlist;
2435 if (!CALL_P (insn) && last_sp_set
2436 && !for_each_rtx (&PATTERN (insn), record_stack_memrefs, &data))
2438 memlist = data.memlist;
2439 continue;
2441 memlist = data.memlist;
2443 /* Otherwise, we were not able to process the instruction.
2444 Do not continue collecting data across such a one. */
2445 if (last_sp_set
2446 && (CALL_P (insn)
2447 || reg_mentioned_p (stack_pointer_rtx, PATTERN (insn))))
2449 if (last_sp_set && last_sp_adjust == 0)
2450 delete_insn (last_sp_set);
2451 free_csa_memlist (memlist);
2452 memlist = NULL;
2453 last_sp_set = NULL_RTX;
2454 last_sp_adjust = 0;
2458 if (last_sp_set && last_sp_adjust == 0)
2459 delete_insn (last_sp_set);
2461 if (memlist)
2462 free_csa_memlist (memlist);