OSDN Git Service

06272e5e770625840a1fbd88c3e9e2e3050af9ef
[pf3gnuchains/gcc-fork.git] / gcc / regmove.c
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, 2005 Free Software Foundation, Inc.
4
5 This file is part of GCC.
6
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.
11
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.
16
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, 51 Franklin Street, Fifth Floor, Boston, MA
20 02110-1301, USA.  */
21
22
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.  */
27
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"
46 #include "timevar.h"
47 #include "tree-pass.h"
48
49
50 /* Turn STACK_GROWS_DOWNWARD into a boolean.  */
51 #ifdef STACK_GROWS_DOWNWARD
52 #undef STACK_GROWS_DOWNWARD
53 #define STACK_GROWS_DOWNWARD 1
54 #else
55 #define STACK_GROWS_DOWNWARD 0
56 #endif
57
58 static int perhaps_ends_bb_p (rtx);
59 static int optimize_reg_copy_1 (rtx, rtx, rtx);
60 static void optimize_reg_copy_2 (rtx, rtx, rtx);
61 static void optimize_reg_copy_3 (rtx, rtx, rtx);
62 static void copy_src_to_dest (rtx, rtx, rtx, int);
63 static int *regmove_bb_head;
64
65 struct match {
66   int with[MAX_RECOG_OPERANDS];
67   enum { READ, WRITE, READWRITE } use[MAX_RECOG_OPERANDS];
68   int commutative[MAX_RECOG_OPERANDS];
69   int early_clobber[MAX_RECOG_OPERANDS];
70 };
71
72 static rtx discover_flags_reg (void);
73 static void mark_flags_life_zones (rtx);
74 static void flags_set_1 (rtx, rtx, void *);
75
76 static int try_auto_increment (rtx, rtx, rtx, rtx, HOST_WIDE_INT, int);
77 static int find_matches (rtx, struct match *);
78 static void replace_in_call_usage (rtx *, unsigned int, rtx, rtx);
79 static int fixup_match_1 (rtx, rtx, rtx, rtx, rtx, int, int, int);
80 static int stable_and_no_regs_but_for_p (rtx, rtx, rtx);
81 static int regclass_compatible_p (int, int);
82 static int replacement_quality (rtx);
83 static int fixup_match_2 (rtx, rtx, rtx, rtx);
84
85 /* Return nonzero if registers with CLASS1 and CLASS2 can be merged without
86    causing too much register allocation problems.  */
87 static int
88 regclass_compatible_p (int class0, int class1)
89 {
90   return (class0 == class1
91           || (reg_class_subset_p (class0, class1)
92               && ! CLASS_LIKELY_SPILLED_P (class0))
93           || (reg_class_subset_p (class1, class0)
94               && ! CLASS_LIKELY_SPILLED_P (class1)));
95 }
96
97 /* INC_INSN is an instruction that adds INCREMENT to REG.
98    Try to fold INC_INSN as a post/pre in/decrement into INSN.
99    Iff INC_INSN_SET is nonzero, inc_insn has a destination different from src.
100    Return nonzero for success.  */
101 static int
102 try_auto_increment (rtx insn, rtx inc_insn, rtx inc_insn_set, rtx reg,
103                     HOST_WIDE_INT increment, int pre)
104 {
105   enum rtx_code inc_code;
106
107   rtx pset = single_set (insn);
108   if (pset)
109     {
110       /* Can't use the size of SET_SRC, we might have something like
111          (sign_extend:SI (mem:QI ...  */
112       rtx use = find_use_as_address (pset, reg, 0);
113       if (use != 0 && use != (rtx) (size_t) 1)
114         {
115           int size = GET_MODE_SIZE (GET_MODE (use));
116           if (0
117               || (HAVE_POST_INCREMENT
118                   && pre == 0 && (inc_code = POST_INC, increment == size))
119               || (HAVE_PRE_INCREMENT
120                   && pre == 1 && (inc_code = PRE_INC, increment == size))
121               || (HAVE_POST_DECREMENT
122                   && pre == 0 && (inc_code = POST_DEC, increment == -size))
123               || (HAVE_PRE_DECREMENT
124                   && pre == 1 && (inc_code = PRE_DEC, increment == -size))
125           )
126             {
127               if (inc_insn_set)
128                 validate_change
129                   (inc_insn,
130                    &SET_SRC (inc_insn_set),
131                    XEXP (SET_SRC (inc_insn_set), 0), 1);
132               validate_change (insn, &XEXP (use, 0),
133                                gen_rtx_fmt_e (inc_code, Pmode, reg), 1);
134               if (apply_change_group ())
135                 {
136                   /* If there is a REG_DEAD note on this insn, we must
137                      change this not to REG_UNUSED meaning that the register
138                      is set, but the value is dead.  Failure to do so will
139                      result in a sched1 dieing -- when it recomputes lifetime
140                      information, the number of REG_DEAD notes will have
141                      changed.  */
142                   rtx note = find_reg_note (insn, REG_DEAD, reg);
143                   if (note)
144                     PUT_MODE (note, REG_UNUSED);
145
146                   REG_NOTES (insn)
147                     = gen_rtx_EXPR_LIST (REG_INC,
148                                          reg, REG_NOTES (insn));
149                   if (! inc_insn_set)
150                     delete_insn (inc_insn);
151                   return 1;
152                 }
153             }
154         }
155     }
156   return 0;
157 }
158 \f
159 /* Determine if the pattern generated by add_optab has a clobber,
160    such as might be issued for a flags hard register.  To make the
161    code elsewhere simpler, we handle cc0 in this same framework.
162
163    Return the register if one was discovered.  Return NULL_RTX if
164    if no flags were found.  Return pc_rtx if we got confused.  */
165
166 static rtx
167 discover_flags_reg (void)
168 {
169   rtx tmp;
170   tmp = gen_rtx_REG (word_mode, 10000);
171   tmp = gen_add3_insn (tmp, tmp, const2_rtx);
172
173   /* If we get something that isn't a simple set, or a
174      [(set ..) (clobber ..)], this whole function will go wrong.  */
175   if (GET_CODE (tmp) == SET)
176     return NULL_RTX;
177   else if (GET_CODE (tmp) == PARALLEL)
178     {
179       int found;
180
181       if (XVECLEN (tmp, 0) != 2)
182         return pc_rtx;
183       tmp = XVECEXP (tmp, 0, 1);
184       if (GET_CODE (tmp) != CLOBBER)
185         return pc_rtx;
186       tmp = XEXP (tmp, 0);
187
188       /* Don't do anything foolish if the md wanted to clobber a
189          scratch or something.  We only care about hard regs.
190          Moreover we don't like the notion of subregs of hard regs.  */
191       if (GET_CODE (tmp) == SUBREG
192           && REG_P (SUBREG_REG (tmp))
193           && REGNO (SUBREG_REG (tmp)) < FIRST_PSEUDO_REGISTER)
194         return pc_rtx;
195       found = (REG_P (tmp) && REGNO (tmp) < FIRST_PSEUDO_REGISTER);
196
197       return (found ? tmp : NULL_RTX);
198     }
199
200   return pc_rtx;
201 }
202
203 /* It is a tedious task identifying when the flags register is live and
204    when it is safe to optimize.  Since we process the instruction stream
205    multiple times, locate and record these live zones by marking the
206    mode of the instructions --
207
208    QImode is used on the instruction at which the flags becomes live.
209
210    HImode is used within the range (exclusive) that the flags are
211    live.  Thus the user of the flags is not marked.
212
213    All other instructions are cleared to VOIDmode.  */
214
215 /* Used to communicate with flags_set_1.  */
216 static rtx flags_set_1_rtx;
217 static int flags_set_1_set;
218
219 static void
220 mark_flags_life_zones (rtx flags)
221 {
222   int flags_regno;
223   int flags_nregs;
224   basic_block block;
225
226 #ifdef HAVE_cc0
227   /* If we found a flags register on a cc0 host, bail.  */
228   if (flags == NULL_RTX)
229     flags = cc0_rtx;
230   else if (flags != cc0_rtx)
231     flags = pc_rtx;
232 #endif
233
234   /* Simple cases first: if no flags, clear all modes.  If confusing,
235      mark the entire function as being in a flags shadow.  */
236   if (flags == NULL_RTX || flags == pc_rtx)
237     {
238       enum machine_mode mode = (flags ? HImode : VOIDmode);
239       rtx insn;
240       for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
241         PUT_MODE (insn, mode);
242       return;
243     }
244
245 #ifdef HAVE_cc0
246   flags_regno = -1;
247   flags_nregs = 1;
248 #else
249   flags_regno = REGNO (flags);
250   flags_nregs = hard_regno_nregs[flags_regno][GET_MODE (flags)];
251 #endif
252   flags_set_1_rtx = flags;
253
254   /* Process each basic block.  */
255   FOR_EACH_BB_REVERSE (block)
256     {
257       rtx insn, end;
258       int live;
259
260       insn = BB_HEAD (block);
261       end = BB_END (block);
262
263       /* Look out for the (unlikely) case of flags being live across
264          basic block boundaries.  */
265       live = 0;
266 #ifndef HAVE_cc0
267       {
268         int i;
269         for (i = 0; i < flags_nregs; ++i)
270           live |= REGNO_REG_SET_P (block->il.rtl->global_live_at_start,
271                                    flags_regno + i);
272       }
273 #endif
274
275       while (1)
276         {
277           /* Process liveness in reverse order of importance --
278              alive, death, birth.  This lets more important info
279              overwrite the mode of lesser info.  */
280
281           if (INSN_P (insn))
282             {
283 #ifdef HAVE_cc0
284               /* In the cc0 case, death is not marked in reg notes,
285                  but is instead the mere use of cc0 when it is alive.  */
286               if (live && reg_mentioned_p (cc0_rtx, PATTERN (insn)))
287                 live = 0;
288 #else
289               /* In the hard reg case, we watch death notes.  */
290               if (live && find_regno_note (insn, REG_DEAD, flags_regno))
291                 live = 0;
292 #endif
293               PUT_MODE (insn, (live ? HImode : VOIDmode));
294
295               /* In either case, birth is denoted simply by its presence
296                  as the destination of a set.  */
297               flags_set_1_set = 0;
298               note_stores (PATTERN (insn), flags_set_1, NULL);
299               if (flags_set_1_set)
300                 {
301                   live = 1;
302                   PUT_MODE (insn, QImode);
303                 }
304             }
305           else
306             PUT_MODE (insn, (live ? HImode : VOIDmode));
307
308           if (insn == end)
309             break;
310           insn = NEXT_INSN (insn);
311         }
312     }
313 }
314
315 /* A subroutine of mark_flags_life_zones, called through note_stores.  */
316
317 static void
318 flags_set_1 (rtx x, rtx pat, void *data ATTRIBUTE_UNUSED)
319 {
320   if (GET_CODE (pat) == SET
321       && reg_overlap_mentioned_p (x, flags_set_1_rtx))
322     flags_set_1_set = 1;
323 }
324 \f
325 static int *regno_src_regno;
326
327 /* Indicate how good a choice REG (which appears as a source) is to replace
328    a destination register with.  The higher the returned value, the better
329    the choice.  The main objective is to avoid using a register that is
330    a candidate for tying to a hard register, since the output might in
331    turn be a candidate to be tied to a different hard register.  */
332 static int
333 replacement_quality (rtx reg)
334 {
335   int src_regno;
336
337   /* Bad if this isn't a register at all.  */
338   if (!REG_P (reg))
339     return 0;
340
341   /* If this register is not meant to get a hard register,
342      it is a poor choice.  */
343   if (REG_LIVE_LENGTH (REGNO (reg)) < 0)
344     return 0;
345
346   src_regno = regno_src_regno[REGNO (reg)];
347
348   /* If it was not copied from another register, it is fine.  */
349   if (src_regno < 0)
350     return 3;
351
352   /* Copied from a hard register?  */
353   if (src_regno < FIRST_PSEUDO_REGISTER)
354     return 1;
355
356   /* Copied from a pseudo register - not as bad as from a hard register,
357      yet still cumbersome, since the register live length will be lengthened
358      when the registers get tied.  */
359   return 2;
360 }
361 \f
362 /* Return 1 if INSN might end a basic block.  */
363
364 static int perhaps_ends_bb_p (rtx insn)
365 {
366   switch (GET_CODE (insn))
367     {
368     case CODE_LABEL:
369     case JUMP_INSN:
370       /* These always end a basic block.  */
371       return 1;
372
373     case CALL_INSN:
374       /* A CALL_INSN might be the last insn of a basic block, if it is inside
375          an EH region or if there are nonlocal gotos.  Note that this test is
376          very conservative.  */
377       if (nonlocal_goto_handler_labels)
378         return 1;
379       /* Fall through.  */
380     default:
381       return can_throw_internal (insn);
382     }
383 }
384 \f
385 /* INSN is a copy from SRC to DEST, both registers, and SRC does not die
386    in INSN.
387
388    Search forward to see if SRC dies before either it or DEST is modified,
389    but don't scan past the end of a basic block.  If so, we can replace SRC
390    with DEST and let SRC die in INSN.
391
392    This will reduce the number of registers live in that range and may enable
393    DEST to be tied to SRC, thus often saving one register in addition to a
394    register-register copy.  */
395
396 static int
397 optimize_reg_copy_1 (rtx insn, rtx dest, rtx src)
398 {
399   rtx p, q;
400   rtx note;
401   rtx dest_death = 0;
402   int sregno = REGNO (src);
403   int dregno = REGNO (dest);
404
405   /* We don't want to mess with hard regs if register classes are small.  */
406   if (sregno == dregno
407       || (SMALL_REGISTER_CLASSES
408           && (sregno < FIRST_PSEUDO_REGISTER
409               || dregno < FIRST_PSEUDO_REGISTER))
410       /* We don't see all updates to SP if they are in an auto-inc memory
411          reference, so we must disallow this optimization on them.  */
412       || sregno == STACK_POINTER_REGNUM || dregno == STACK_POINTER_REGNUM)
413     return 0;
414
415   for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
416     {
417       /* ??? We can't scan past the end of a basic block without updating
418          the register lifetime info (REG_DEAD/basic_block_live_at_start).  */
419       if (perhaps_ends_bb_p (p))
420         break;
421       else if (! INSN_P (p))
422         continue;
423
424       if (reg_set_p (src, p) || reg_set_p (dest, p)
425           /* If SRC is an asm-declared register, it must not be replaced
426              in any asm.  Unfortunately, the REG_EXPR tree for the asm
427              variable may be absent in the SRC rtx, so we can't check the
428              actual register declaration easily (the asm operand will have
429              it, though).  To avoid complicating the test for a rare case,
430              we just don't perform register replacement for a hard reg
431              mentioned in an asm.  */
432           || (sregno < FIRST_PSEUDO_REGISTER
433               && asm_noperands (PATTERN (p)) >= 0
434               && reg_overlap_mentioned_p (src, PATTERN (p)))
435           /* Don't change hard registers used by a call.  */
436           || (CALL_P (p) && sregno < FIRST_PSEUDO_REGISTER
437               && find_reg_fusage (p, USE, src))
438           /* Don't change a USE of a register.  */
439           || (GET_CODE (PATTERN (p)) == USE
440               && reg_overlap_mentioned_p (src, XEXP (PATTERN (p), 0))))
441         break;
442
443       /* See if all of SRC dies in P.  This test is slightly more
444          conservative than it needs to be.  */
445       if ((note = find_regno_note (p, REG_DEAD, sregno)) != 0
446           && GET_MODE (XEXP (note, 0)) == GET_MODE (src))
447         {
448           int failed = 0;
449           int d_length = 0;
450           int s_length = 0;
451           int d_n_calls = 0;
452           int s_n_calls = 0;
453
454           /* We can do the optimization.  Scan forward from INSN again,
455              replacing regs as we go.  Set FAILED if a replacement can't
456              be done.  In that case, we can't move the death note for SRC.
457              This should be rare.  */
458
459           /* Set to stop at next insn.  */
460           for (q = next_real_insn (insn);
461                q != next_real_insn (p);
462                q = next_real_insn (q))
463             {
464               if (reg_overlap_mentioned_p (src, PATTERN (q)))
465                 {
466                   /* If SRC is a hard register, we might miss some
467                      overlapping registers with validate_replace_rtx,
468                      so we would have to undo it.  We can't if DEST is
469                      present in the insn, so fail in that combination
470                      of cases.  */
471                   if (sregno < FIRST_PSEUDO_REGISTER
472                       && reg_mentioned_p (dest, PATTERN (q)))
473                     failed = 1;
474                   
475                   /* Attempt to replace all uses.  */
476                   else if (!validate_replace_rtx (src, dest, q))
477                     failed = 1;
478
479                   /* If this succeeded, but some part of the register
480                      is still present, undo the replacement.  */
481                   else if (sregno < FIRST_PSEUDO_REGISTER
482                            && reg_overlap_mentioned_p (src, PATTERN (q)))
483                     {
484                       validate_replace_rtx (dest, src, q);
485                       failed = 1;
486                     }
487                 }
488
489               /* For SREGNO, count the total number of insns scanned.
490                  For DREGNO, count the total number of insns scanned after
491                  passing the death note for DREGNO.  */
492               s_length++;
493               if (dest_death)
494                 d_length++;
495
496               /* If the insn in which SRC dies is a CALL_INSN, don't count it
497                  as a call that has been crossed.  Otherwise, count it.  */
498               if (q != p && CALL_P (q))
499                 {
500                   /* Similarly, total calls for SREGNO, total calls beyond
501                      the death note for DREGNO.  */
502                   s_n_calls++;
503                   if (dest_death)
504                     d_n_calls++;
505                 }
506
507               /* If DEST dies here, remove the death note and save it for
508                  later.  Make sure ALL of DEST dies here; again, this is
509                  overly conservative.  */
510               if (dest_death == 0
511                   && (dest_death = find_regno_note (q, REG_DEAD, dregno)) != 0)
512                 {
513                   if (GET_MODE (XEXP (dest_death, 0)) != GET_MODE (dest))
514                     failed = 1, dest_death = 0;
515                   else
516                     remove_note (q, dest_death);
517                 }
518             }
519
520           if (! failed)
521             {
522               /* These counters need to be updated if and only if we are
523                  going to move the REG_DEAD note.  */
524               if (sregno >= FIRST_PSEUDO_REGISTER)
525                 {
526                   if (REG_LIVE_LENGTH (sregno) >= 0)
527                     {
528                       REG_LIVE_LENGTH (sregno) -= s_length;
529                       /* REG_LIVE_LENGTH is only an approximation after
530                          combine if sched is not run, so make sure that we
531                          still have a reasonable value.  */
532                       if (REG_LIVE_LENGTH (sregno) < 2)
533                         REG_LIVE_LENGTH (sregno) = 2;
534                     }
535
536                   REG_N_CALLS_CROSSED (sregno) -= s_n_calls;
537                 }
538
539               /* Move death note of SRC from P to INSN.  */
540               remove_note (p, note);
541               XEXP (note, 1) = REG_NOTES (insn);
542               REG_NOTES (insn) = note;
543             }
544
545           /* DEST is also dead if INSN has a REG_UNUSED note for DEST.  */
546           if (! dest_death
547               && (dest_death = find_regno_note (insn, REG_UNUSED, dregno)))
548             {
549               PUT_REG_NOTE_KIND (dest_death, REG_DEAD);
550               remove_note (insn, dest_death);
551             }
552
553           /* Put death note of DEST on P if we saw it die.  */
554           if (dest_death)
555             {
556               XEXP (dest_death, 1) = REG_NOTES (p);
557               REG_NOTES (p) = dest_death;
558
559               if (dregno >= FIRST_PSEUDO_REGISTER)
560                 {
561                   /* If and only if we are moving the death note for DREGNO,
562                      then we need to update its counters.  */
563                   if (REG_LIVE_LENGTH (dregno) >= 0)
564                     REG_LIVE_LENGTH (dregno) += d_length;
565                   REG_N_CALLS_CROSSED (dregno) += d_n_calls;
566                 }
567             }
568
569           return ! failed;
570         }
571
572       /* If SRC is a hard register which is set or killed in some other
573          way, we can't do this optimization.  */
574       else if (sregno < FIRST_PSEUDO_REGISTER
575                && dead_or_set_p (p, src))
576         break;
577     }
578   return 0;
579 }
580 \f
581 /* INSN is a copy of SRC to DEST, in which SRC dies.  See if we now have
582    a sequence of insns that modify DEST followed by an insn that sets
583    SRC to DEST in which DEST dies, with no prior modification of DEST.
584    (There is no need to check if the insns in between actually modify
585    DEST.  We should not have cases where DEST is not modified, but
586    the optimization is safe if no such modification is detected.)
587    In that case, we can replace all uses of DEST, starting with INSN and
588    ending with the set of SRC to DEST, with SRC.  We do not do this
589    optimization if a CALL_INSN is crossed unless SRC already crosses a
590    call or if DEST dies before the copy back to SRC.
591
592    It is assumed that DEST and SRC are pseudos; it is too complicated to do
593    this for hard registers since the substitutions we may make might fail.  */
594
595 static void
596 optimize_reg_copy_2 (rtx insn, rtx dest, rtx src)
597 {
598   rtx p, q;
599   rtx set;
600   int sregno = REGNO (src);
601   int dregno = REGNO (dest);
602
603   for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
604     {
605       /* ??? We can't scan past the end of a basic block without updating
606          the register lifetime info (REG_DEAD/basic_block_live_at_start).  */
607       if (perhaps_ends_bb_p (p))
608         break;
609       else if (! INSN_P (p))
610         continue;
611
612       set = single_set (p);
613       if (set && SET_SRC (set) == dest && SET_DEST (set) == src
614           && find_reg_note (p, REG_DEAD, dest))
615         {
616           /* We can do the optimization.  Scan forward from INSN again,
617              replacing regs as we go.  */
618
619           /* Set to stop at next insn.  */
620           for (q = insn; q != NEXT_INSN (p); q = NEXT_INSN (q))
621             if (INSN_P (q))
622               {
623                 if (reg_mentioned_p (dest, PATTERN (q)))
624                   PATTERN (q) = replace_rtx (PATTERN (q), dest, src);
625
626
627               if (CALL_P (q))
628                 {
629                   REG_N_CALLS_CROSSED (dregno)--;
630                   REG_N_CALLS_CROSSED (sregno)++;
631                 }
632               }
633
634           remove_note (p, find_reg_note (p, REG_DEAD, dest));
635           REG_N_DEATHS (dregno)--;
636           remove_note (insn, find_reg_note (insn, REG_DEAD, src));
637           REG_N_DEATHS (sregno)--;
638           return;
639         }
640
641       if (reg_set_p (src, p)
642           || find_reg_note (p, REG_DEAD, dest)
643           || (CALL_P (p) && REG_N_CALLS_CROSSED (sregno) == 0))
644         break;
645     }
646 }
647 /* INSN is a ZERO_EXTEND or SIGN_EXTEND of SRC to DEST.
648    Look if SRC dies there, and if it is only set once, by loading
649    it from memory.  If so, try to incorporate the zero/sign extension
650    into the memory read, change SRC to the mode of DEST, and alter
651    the remaining accesses to use the appropriate SUBREG.  This allows
652    SRC and DEST to be tied later.  */
653 static void
654 optimize_reg_copy_3 (rtx insn, rtx dest, rtx src)
655 {
656   rtx src_reg = XEXP (src, 0);
657   int src_no = REGNO (src_reg);
658   int dst_no = REGNO (dest);
659   rtx p, set;
660   enum machine_mode old_mode;
661
662   if (src_no < FIRST_PSEUDO_REGISTER
663       || dst_no < FIRST_PSEUDO_REGISTER
664       || ! find_reg_note (insn, REG_DEAD, src_reg)
665       || REG_N_DEATHS (src_no) != 1
666       || REG_N_SETS (src_no) != 1)
667     return;
668   for (p = PREV_INSN (insn); p && ! reg_set_p (src_reg, p); p = PREV_INSN (p))
669     /* ??? We can't scan past the end of a basic block without updating
670        the register lifetime info (REG_DEAD/basic_block_live_at_start).  */
671     if (perhaps_ends_bb_p (p))
672       break;
673
674   if (! p)
675     return;
676
677   if (! (set = single_set (p))
678       || !MEM_P (SET_SRC (set))
679       /* If there's a REG_EQUIV note, this must be an insn that loads an
680          argument.  Prefer keeping the note over doing this optimization.  */
681       || find_reg_note (p, REG_EQUIV, NULL_RTX)
682       || SET_DEST (set) != src_reg)
683     return;
684
685   /* Be conservative: although this optimization is also valid for
686      volatile memory references, that could cause trouble in later passes.  */
687   if (MEM_VOLATILE_P (SET_SRC (set)))
688     return;
689
690   /* Do not use a SUBREG to truncate from one mode to another if truncation
691      is not a nop.  */
692   if (GET_MODE_BITSIZE (GET_MODE (src_reg)) <= GET_MODE_BITSIZE (GET_MODE (src))
693       && !TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (GET_MODE (src)),
694                                  GET_MODE_BITSIZE (GET_MODE (src_reg))))
695     return;
696
697   old_mode = GET_MODE (src_reg);
698   PUT_MODE (src_reg, GET_MODE (src));
699   XEXP (src, 0) = SET_SRC (set);
700
701   /* Include this change in the group so that it's easily undone if
702      one of the changes in the group is invalid.  */
703   validate_change (p, &SET_SRC (set), src, 1);
704
705   /* Now walk forward making additional replacements.  We want to be able
706      to undo all the changes if a later substitution fails.  */
707   while (p = NEXT_INSN (p), p != insn)
708     {
709       if (! INSN_P (p))
710         continue;
711
712       /* Make a tentative change.  */
713       validate_replace_rtx_group (src_reg,
714                                   gen_lowpart_SUBREG (old_mode, src_reg),
715                                   p);
716     }
717
718   validate_replace_rtx_group (src, src_reg, insn);
719
720   /* Now see if all the changes are valid.  */
721   if (! apply_change_group ())
722     {
723       /* One or more changes were no good.  Back out everything.  */
724       PUT_MODE (src_reg, old_mode);
725       XEXP (src, 0) = src_reg;
726     }
727   else
728     {
729       rtx note = find_reg_note (p, REG_EQUAL, NULL_RTX);
730       if (note)
731         remove_note (p, note);
732     }
733 }
734
735 \f
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.  */
738
739 static void
740 copy_src_to_dest (rtx insn, rtx src, rtx dest, int old_max_uid)
741 {
742   rtx seq;
743   rtx link;
744   rtx next;
745   rtx set;
746   rtx move_insn;
747   rtx *p_insn_notes;
748   rtx *p_move_notes;
749   int src_regno;
750   int dest_regno;
751   int bb;
752   int insn_uid;
753   int move_uid;
754
755   /* A REG_LIVE_LENGTH of -1 indicates the register is equivalent to a constant
756      or memory location and is used infrequently; a REG_LIVE_LENGTH of -2 is
757      parameter when there is no frame pointer that is not allocated a register.
758      For now, we just reject them, rather than incrementing the live length.  */
759
760   if (REG_P (src)
761       && REG_LIVE_LENGTH (REGNO (src)) > 0
762       && REG_P (dest)
763       && REG_LIVE_LENGTH (REGNO (dest)) > 0
764       && (set = single_set (insn)) != NULL_RTX
765       && !reg_mentioned_p (dest, SET_SRC (set))
766       && GET_MODE (src) == GET_MODE (dest))
767     {
768       int old_num_regs = reg_rtx_no;
769
770       /* Generate the src->dest move.  */
771       start_sequence ();
772       emit_move_insn (dest, src);
773       seq = get_insns ();
774       end_sequence ();
775       /* If this sequence uses new registers, we may not use it.  */
776       if (old_num_regs != reg_rtx_no
777           || ! validate_replace_rtx (src, dest, insn))
778         {
779           /* We have to restore reg_rtx_no to its old value, lest
780              recompute_reg_usage will try to compute the usage of the
781              new regs, yet reg_n_info is not valid for them.  */
782           reg_rtx_no = old_num_regs;
783           return;
784         }
785       emit_insn_before (seq, insn);
786       move_insn = PREV_INSN (insn);
787       p_move_notes = &REG_NOTES (move_insn);
788       p_insn_notes = &REG_NOTES (insn);
789
790       /* Move any notes mentioning src to the move instruction.  */
791       for (link = REG_NOTES (insn); link != NULL_RTX; link = next)
792         {
793           next = XEXP (link, 1);
794           if (XEXP (link, 0) == src)
795             {
796               *p_move_notes = link;
797               p_move_notes = &XEXP (link, 1);
798             }
799           else
800             {
801               *p_insn_notes = link;
802               p_insn_notes = &XEXP (link, 1);
803             }
804         }
805
806       *p_move_notes = NULL_RTX;
807       *p_insn_notes = NULL_RTX;
808
809       /* Is the insn the head of a basic block?  If so extend it.  */
810       insn_uid = INSN_UID (insn);
811       move_uid = INSN_UID (move_insn);
812       if (insn_uid < old_max_uid)
813         {
814           bb = regmove_bb_head[insn_uid];
815           if (bb >= 0)
816             {
817               BB_HEAD (BASIC_BLOCK (bb)) = move_insn;
818               regmove_bb_head[insn_uid] = -1;
819             }
820         }
821
822       /* Update the various register tables.  */
823       dest_regno = REGNO (dest);
824       REG_N_SETS (dest_regno) ++;
825       REG_LIVE_LENGTH (dest_regno)++;
826       if (REGNO_FIRST_UID (dest_regno) == insn_uid)
827         REGNO_FIRST_UID (dest_regno) = move_uid;
828
829       src_regno = REGNO (src);
830       if (! find_reg_note (move_insn, REG_DEAD, src))
831         REG_LIVE_LENGTH (src_regno)++;
832
833       if (REGNO_FIRST_UID (src_regno) == insn_uid)
834         REGNO_FIRST_UID (src_regno) = move_uid;
835
836       if (REGNO_LAST_UID (src_regno) == insn_uid)
837         REGNO_LAST_UID (src_regno) = move_uid;
838     }
839 }
840
841 /* reg_set_in_bb[REGNO] points to basic block iff the register is set
842    only once in the given block and has REG_EQUAL note.  */
843
844 basic_block *reg_set_in_bb;
845
846 /* Size of reg_set_in_bb array.  */
847 static unsigned int max_reg_computed;
848
849 \f
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.  */
859
860 static bool
861 reg_is_remote_constant_p (rtx reg, rtx insn)
862 {
863   basic_block bb;
864   rtx p;
865   int max;
866
867   if (!reg_set_in_bb)
868     {
869       max_reg_computed = max = max_reg_num ();
870       reg_set_in_bb = xcalloc (max, sizeof (*reg_set_in_bb));
871
872       FOR_EACH_BB (bb)
873         for (p = BB_HEAD (bb); p != NEXT_INSN (BB_END (bb));
874              p = NEXT_INSN (p))
875         {
876           rtx s;
877
878           if (!INSN_P (p))
879             continue;
880           s = single_set (p);
881           /* This is the instruction which sets REG.  If there is a
882              REG_EQUAL note, then REG is equivalent to a constant.  */
883           if (s != 0
884               && REG_P (SET_DEST (s))
885               && REG_N_SETS (REGNO (SET_DEST (s))) == 1
886               && find_reg_note (p, REG_EQUAL, NULL_RTX))
887             reg_set_in_bb[REGNO (SET_DEST (s))] = bb;
888         }
889     }
890   gcc_assert (REGNO (reg) < max_reg_computed);
891   if (reg_set_in_bb[REGNO (reg)] == NULL)
892     return false;
893   if (reg_set_in_bb[REGNO (reg)] != BLOCK_FOR_INSN (insn))
894     return true;
895   /* Look for the set.  */
896   for (p = BB_HEAD (BLOCK_FOR_INSN (insn)); p != insn; p = NEXT_INSN (p))
897     {
898       rtx s;
899
900       if (!INSN_P (p))
901         continue;
902       s = single_set (p);
903       if (s != 0
904           && REG_P (SET_DEST (s)) && REGNO (SET_DEST (s)) == REGNO (reg))
905         {
906           /* The register is set in the same basic block.  */
907           return false;
908         }
909     }
910   return true;
911 }
912
913 /* INSN is adding a CONST_INT to a REG.  We search backwards looking for
914    another add immediate instruction with the same source and dest registers,
915    and if we find one, we change INSN to an increment, and return 1.  If
916    no changes are made, we return 0.
917
918    This changes
919      (set (reg100) (plus reg1 offset1))
920      ...
921      (set (reg100) (plus reg1 offset2))
922    to
923      (set (reg100) (plus reg1 offset1))
924      ...
925      (set (reg100) (plus reg100 offset2-offset1))  */
926
927 /* ??? What does this comment mean?  */
928 /* cse disrupts preincrement / postdecrement sequences when it finds a
929    hard register as ultimate source, like the frame pointer.  */
930
931 static int
932 fixup_match_2 (rtx insn, rtx dst, rtx src, rtx offset)
933 {
934   rtx p, dst_death = 0;
935   int length, num_calls = 0;
936
937   /* If SRC dies in INSN, we'd have to move the death note.  This is
938      considered to be very unlikely, so we just skip the optimization
939      in this case.  */
940   if (find_regno_note (insn, REG_DEAD, REGNO (src)))
941     return 0;
942
943   /* Scan backward to find the first instruction that sets DST.  */
944
945   for (length = 0, p = PREV_INSN (insn); p; p = PREV_INSN (p))
946     {
947       rtx pset;
948
949       /* ??? We can't scan past the end of a basic block without updating
950          the register lifetime info (REG_DEAD/basic_block_live_at_start).  */
951       if (perhaps_ends_bb_p (p))
952         break;
953       else if (! INSN_P (p))
954         continue;
955
956       if (find_regno_note (p, REG_DEAD, REGNO (dst)))
957         dst_death = p;
958       if (! dst_death)
959         length++;
960
961       pset = single_set (p);
962       if (pset && SET_DEST (pset) == dst
963           && GET_CODE (SET_SRC (pset)) == PLUS
964           && XEXP (SET_SRC (pset), 0) == src
965           && GET_CODE (XEXP (SET_SRC (pset), 1)) == CONST_INT)
966         {
967           HOST_WIDE_INT newconst
968             = INTVAL (offset) - INTVAL (XEXP (SET_SRC (pset), 1));
969           rtx add = gen_add3_insn (dst, dst, GEN_INT (newconst));
970
971           if (add && validate_change (insn, &PATTERN (insn), add, 0))
972             {
973               /* Remove the death note for DST from DST_DEATH.  */
974               if (dst_death)
975                 {
976                   remove_death (REGNO (dst), dst_death);
977                   REG_LIVE_LENGTH (REGNO (dst)) += length;
978                   REG_N_CALLS_CROSSED (REGNO (dst)) += num_calls;
979                 }
980
981               if (dump_file)
982                 fprintf (dump_file,
983                          "Fixed operand of insn %d.\n",
984                           INSN_UID (insn));
985
986 #ifdef AUTO_INC_DEC
987               for (p = PREV_INSN (insn); p; p = PREV_INSN (p))
988                 {
989                   if (LABEL_P (p)
990                       || JUMP_P (p))
991                     break;
992                   if (! INSN_P (p))
993                     continue;
994                   if (reg_overlap_mentioned_p (dst, PATTERN (p)))
995                     {
996                       if (try_auto_increment (p, insn, 0, dst, newconst, 0))
997                         return 1;
998                       break;
999                     }
1000                 }
1001               for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
1002                 {
1003                   if (LABEL_P (p)
1004                       || JUMP_P (p))
1005                     break;
1006                   if (! INSN_P (p))
1007                     continue;
1008                   if (reg_overlap_mentioned_p (dst, PATTERN (p)))
1009                     {
1010                       try_auto_increment (p, insn, 0, dst, newconst, 1);
1011                       break;
1012                     }
1013                 }
1014 #endif
1015               return 1;
1016             }
1017         }
1018
1019       if (reg_set_p (dst, PATTERN (p)))
1020         break;
1021
1022       /* If we have passed a call instruction, and the
1023          pseudo-reg SRC is not already live across a call,
1024          then don't perform the optimization.  */
1025       /* reg_set_p is overly conservative for CALL_INSNS, thinks that all
1026          hard regs are clobbered.  Thus, we only use it for src for
1027          non-call insns.  */
1028       if (CALL_P (p))
1029         {
1030           if (! dst_death)
1031             num_calls++;
1032
1033           if (REG_N_CALLS_CROSSED (REGNO (src)) == 0)
1034             break;
1035
1036           if (call_used_regs [REGNO (dst)]
1037               || find_reg_fusage (p, CLOBBER, dst))
1038             break;
1039         }
1040       else if (reg_set_p (src, PATTERN (p)))
1041         break;
1042     }
1043
1044   return 0;
1045 }
1046
1047 /* Main entry for the register move optimization.
1048    F is the first instruction.
1049    NREGS is one plus the highest pseudo-reg number used in the instruction.
1050    REGMOVE_DUMP_FILE is a stream for output of a trace of actions taken
1051    (or 0 if none should be output).  */
1052
1053 static void
1054 regmove_optimize (rtx f, int nregs)
1055 {
1056   int old_max_uid = get_max_uid ();
1057   rtx insn;
1058   struct match match;
1059   int pass;
1060   int i;
1061   rtx copy_src, copy_dst;
1062   basic_block bb;
1063
1064   /* ??? Hack.  Regmove doesn't examine the CFG, and gets mightily
1065      confused by non-call exceptions ending blocks.  */
1066   if (flag_non_call_exceptions)
1067     return;
1068
1069   /* Find out where a potential flags register is live, and so that we
1070      can suppress some optimizations in those zones.  */
1071   mark_flags_life_zones (discover_flags_reg ());
1072
1073   regno_src_regno = XNEWVEC (int, nregs);
1074   for (i = nregs; --i >= 0; ) regno_src_regno[i] = -1;
1075
1076   regmove_bb_head = XNEWVEC (int, old_max_uid + 1);
1077   for (i = old_max_uid; i >= 0; i--) regmove_bb_head[i] = -1;
1078   FOR_EACH_BB (bb)
1079     regmove_bb_head[INSN_UID (BB_HEAD (bb))] = bb->index;
1080
1081   /* A forward/backward pass.  Replace output operands with input operands.  */
1082
1083   for (pass = 0; pass <= 2; pass++)
1084     {
1085       if (! flag_regmove && pass >= flag_expensive_optimizations)
1086         goto done;
1087
1088       if (dump_file)
1089         fprintf (dump_file, "Starting %s pass...\n",
1090                  pass ? "backward" : "forward");
1091
1092       for (insn = pass ? get_last_insn () : f; insn;
1093            insn = pass ? PREV_INSN (insn) : NEXT_INSN (insn))
1094         {
1095           rtx set;
1096           int op_no, match_no;
1097
1098           set = single_set (insn);
1099           if (! set)
1100             continue;
1101
1102           if (flag_expensive_optimizations && ! pass
1103               && (GET_CODE (SET_SRC (set)) == SIGN_EXTEND
1104                   || GET_CODE (SET_SRC (set)) == ZERO_EXTEND)
1105               && REG_P (XEXP (SET_SRC (set), 0))
1106               && REG_P (SET_DEST (set)))
1107             optimize_reg_copy_3 (insn, SET_DEST (set), SET_SRC (set));
1108
1109           if (flag_expensive_optimizations && ! pass
1110               && REG_P (SET_SRC (set))
1111               && REG_P (SET_DEST (set)))
1112             {
1113               /* If this is a register-register copy where SRC is not dead,
1114                  see if we can optimize it.  If this optimization succeeds,
1115                  it will become a copy where SRC is dead.  */
1116               if ((find_reg_note (insn, REG_DEAD, SET_SRC (set))
1117                    || optimize_reg_copy_1 (insn, SET_DEST (set), SET_SRC (set)))
1118                   && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
1119                 {
1120                   /* Similarly for a pseudo-pseudo copy when SRC is dead.  */
1121                   if (REGNO (SET_SRC (set)) >= FIRST_PSEUDO_REGISTER)
1122                     optimize_reg_copy_2 (insn, SET_DEST (set), SET_SRC (set));
1123                   if (regno_src_regno[REGNO (SET_DEST (set))] < 0
1124                       && SET_SRC (set) != SET_DEST (set))
1125                     {
1126                       int srcregno = REGNO (SET_SRC (set));
1127                       if (regno_src_regno[srcregno] >= 0)
1128                         srcregno = regno_src_regno[srcregno];
1129                       regno_src_regno[REGNO (SET_DEST (set))] = srcregno;
1130                     }
1131                 }
1132             }
1133           if (! flag_regmove)
1134             continue;
1135
1136           if (! find_matches (insn, &match))
1137             continue;
1138
1139           /* Now scan through the operands looking for a source operand
1140              which is supposed to match the destination operand.
1141              Then scan forward for an instruction which uses the dest
1142              operand.
1143              If it dies there, then replace the dest in both operands with
1144              the source operand.  */
1145
1146           for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1147             {
1148               rtx src, dst, src_subreg;
1149               enum reg_class src_class, dst_class;
1150
1151               match_no = match.with[op_no];
1152
1153               /* Nothing to do if the two operands aren't supposed to match.  */
1154               if (match_no < 0)
1155                 continue;
1156
1157               src = recog_data.operand[op_no];
1158               dst = recog_data.operand[match_no];
1159
1160               if (!REG_P (src))
1161                 continue;
1162
1163               src_subreg = src;
1164               if (GET_CODE (dst) == SUBREG
1165                   && GET_MODE_SIZE (GET_MODE (dst))
1166                      >= GET_MODE_SIZE (GET_MODE (SUBREG_REG (dst))))
1167                 {
1168                   dst = SUBREG_REG (dst);
1169                   src_subreg = lowpart_subreg (GET_MODE (dst),
1170                                                src, GET_MODE (src));
1171                   if (!src_subreg)
1172                     continue;
1173                 }
1174               if (!REG_P (dst)
1175                   || REGNO (dst) < FIRST_PSEUDO_REGISTER)
1176                 continue;
1177
1178               if (REGNO (src) < FIRST_PSEUDO_REGISTER)
1179                 {
1180                   if (match.commutative[op_no] < op_no)
1181                     regno_src_regno[REGNO (dst)] = REGNO (src);
1182                   continue;
1183                 }
1184
1185               if (REG_LIVE_LENGTH (REGNO (src)) < 0)
1186                 continue;
1187
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)
1192                 continue;
1193
1194               if (match.early_clobber[match_no]
1195                   && count_occurrences (PATTERN (insn), src, 0) > 1)
1196                 continue;
1197
1198               /* Make sure match_operand is the destination.  */
1199               if (recog_data.operand[match_no] != SET_DEST (set))
1200                 continue;
1201
1202               /* If the operands already match, then there is nothing to do.  */
1203               if (operands_match_p (src, dst))
1204                 continue;
1205
1206               /* But in the commutative case, we might find a better match.  */
1207               if (match.commutative[op_no] >= 0)
1208                 {
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)))
1213                     continue;
1214                 }
1215
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))
1219                 continue;
1220
1221               if (GET_MODE (src) != GET_MODE (dst))
1222                 continue;
1223
1224               if (fixup_match_1 (insn, set, src, src_subreg, dst, pass,
1225                                  op_no, match_no))
1226                 break;
1227             }
1228         }
1229     }
1230
1231   /* A backward pass.  Replace input operands with output operands.  */
1232
1233   if (dump_file)
1234     fprintf (dump_file, "Starting backward pass...\n");
1235
1236   for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
1237     {
1238       if (INSN_P (insn))
1239         {
1240           int op_no, match_no;
1241           int success = 0;
1242
1243           if (! find_matches (insn, &match))
1244             continue;
1245
1246           /* Now scan through the operands looking for a destination operand
1247              which is supposed to match a source operand.
1248              Then scan backward for an instruction which sets the source
1249              operand.  If safe, then replace the source operand with the
1250              dest operand in both instructions.  */
1251
1252           copy_src = NULL_RTX;
1253           copy_dst = NULL_RTX;
1254           for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1255             {
1256               rtx set, p, src, dst;
1257               rtx src_note, dst_note;
1258               int num_calls = 0;
1259               enum reg_class src_class, dst_class;
1260               int length;
1261
1262               match_no = match.with[op_no];
1263
1264               /* Nothing to do if the two operands aren't supposed to match.  */
1265               if (match_no < 0)
1266                 continue;
1267
1268               dst = recog_data.operand[match_no];
1269               src = recog_data.operand[op_no];
1270
1271               if (!REG_P (src))
1272                 continue;
1273
1274               if (!REG_P (dst)
1275                   || REGNO (dst) < FIRST_PSEUDO_REGISTER
1276                   || REG_LIVE_LENGTH (REGNO (dst)) < 0
1277                   || GET_MODE (src) != GET_MODE (dst))
1278                 continue;
1279
1280               /* If the operands already match, then there is nothing to do.  */
1281               if (operands_match_p (src, dst))
1282                 continue;
1283
1284               if (match.commutative[op_no] >= 0)
1285                 {
1286                   rtx comm = recog_data.operand[match.commutative[op_no]];
1287                   if (operands_match_p (comm, dst))
1288                     continue;
1289                 }
1290
1291               set = single_set (insn);
1292               if (! set)
1293                 continue;
1294
1295               /* Note that single_set ignores parts of a parallel set for
1296                  which one of the destinations is REG_UNUSED.  We can't
1297                  handle that here, since we can wind up rewriting things
1298                  such that a single register is set twice within a single
1299                  parallel.  */
1300               if (reg_set_p (src, insn))
1301                 continue;
1302
1303               /* match_no/dst must be a write-only operand, and
1304                  operand_operand/src must be a read-only operand.  */
1305               if (match.use[op_no] != READ
1306                   || match.use[match_no] != WRITE)
1307                 continue;
1308
1309               if (match.early_clobber[match_no]
1310                   && count_occurrences (PATTERN (insn), src, 0) > 1)
1311                 continue;
1312
1313               /* Make sure match_no is the destination.  */
1314               if (recog_data.operand[match_no] != SET_DEST (set))
1315                 continue;
1316
1317               if (REGNO (src) < FIRST_PSEUDO_REGISTER)
1318                 {
1319                   if (GET_CODE (SET_SRC (set)) == PLUS
1320                       && GET_CODE (XEXP (SET_SRC (set), 1)) == CONST_INT
1321                       && XEXP (SET_SRC (set), 0) == src
1322                       && fixup_match_2 (insn, dst, src,
1323                                         XEXP (SET_SRC (set), 1)))
1324                     break;
1325                   continue;
1326                 }
1327               src_class = reg_preferred_class (REGNO (src));
1328               dst_class = reg_preferred_class (REGNO (dst));
1329
1330               if (! (src_note = find_reg_note (insn, REG_DEAD, src)))
1331                 {
1332                   /* We used to force the copy here like in other cases, but
1333                      it produces worse code, as it eliminates no copy
1334                      instructions and the copy emitted will be produced by
1335                      reload anyway.  On patterns with multiple alternatives,
1336                      there may be better solution available.
1337
1338                      In particular this change produced slower code for numeric
1339                      i387 programs.  */
1340
1341                   continue;
1342                 }
1343
1344               if (! regclass_compatible_p (src_class, dst_class))
1345                 {
1346                   if (!copy_src)
1347                     {
1348                       copy_src = src;
1349                       copy_dst = dst;
1350                     }
1351                   continue;
1352                 }
1353
1354               /* Can not modify an earlier insn to set dst if this insn
1355                  uses an old value in the source.  */
1356               if (reg_overlap_mentioned_p (dst, SET_SRC (set)))
1357                 {
1358                   if (!copy_src)
1359                     {
1360                       copy_src = src;
1361                       copy_dst = dst;
1362                     }
1363                   continue;
1364                 }
1365
1366               /* If src is set once in a different basic block,
1367                  and is set equal to a constant, then do not use
1368                  it for this optimization, as this would make it
1369                  no longer equivalent to a constant.  */
1370
1371               if (reg_is_remote_constant_p (src, insn))
1372                 {
1373                   if (!copy_src)
1374                     {
1375                       copy_src = src;
1376                       copy_dst = dst;
1377                     }
1378                   continue;
1379                 }
1380
1381
1382               if (dump_file)
1383                 fprintf (dump_file,
1384                          "Could fix operand %d of insn %d matching operand %d.\n",
1385                          op_no, INSN_UID (insn), match_no);
1386
1387               /* Scan backward to find the first instruction that uses
1388                  the input operand.  If the operand is set here, then
1389                  replace it in both instructions with match_no.  */
1390
1391               for (length = 0, p = PREV_INSN (insn); p; p = PREV_INSN (p))
1392                 {
1393                   rtx pset;
1394
1395                   /* ??? We can't scan past the end of a basic block without
1396                      updating the register lifetime info
1397                      (REG_DEAD/basic_block_live_at_start).  */
1398                   if (perhaps_ends_bb_p (p))
1399                     break;
1400                   else if (! INSN_P (p))
1401                     continue;
1402
1403                   length++;
1404
1405                   /* ??? See if all of SRC is set in P.  This test is much
1406                      more conservative than it needs to be.  */
1407                   pset = single_set (p);
1408                   if (pset && SET_DEST (pset) == src)
1409                     {
1410                       /* We use validate_replace_rtx, in case there
1411                          are multiple identical source operands.  All of
1412                          them have to be changed at the same time.  */
1413                       if (validate_replace_rtx (src, dst, insn))
1414                         {
1415                           if (validate_change (p, &SET_DEST (pset),
1416                                                dst, 0))
1417                             success = 1;
1418                           else
1419                             {
1420                               /* Change all source operands back.
1421                                  This modifies the dst as a side-effect.  */
1422                               validate_replace_rtx (dst, src, insn);
1423                               /* Now make sure the dst is right.  */
1424                               validate_change (insn,
1425                                                recog_data.operand_loc[match_no],
1426                                                dst, 0);
1427                             }
1428                         }
1429                       break;
1430                     }
1431
1432                   /* We can't make this change if SRC is read or
1433                      partially written in P, since we are going to
1434                      eliminate SRC. We can't make this change 
1435                      if DST is mentioned at all in P,
1436                      since we are going to change its value.  */
1437                   if (reg_overlap_mentioned_p (src, PATTERN (p))
1438                       || reg_mentioned_p (dst, PATTERN (p)))
1439                     break;
1440
1441                   /* If we have passed a call instruction, and the
1442                      pseudo-reg DST is not already live across a call,
1443                      then don't perform the optimization.  */
1444                   if (CALL_P (p))
1445                     {
1446                       num_calls++;
1447
1448                       if (REG_N_CALLS_CROSSED (REGNO (dst)) == 0)
1449                         break;
1450                     }
1451                 }
1452
1453               if (success)
1454                 {
1455                   int dstno, srcno;
1456
1457                   /* Remove the death note for SRC from INSN.  */
1458                   remove_note (insn, src_note);
1459                   /* Move the death note for SRC to P if it is used
1460                      there.  */
1461                   if (reg_overlap_mentioned_p (src, PATTERN (p)))
1462                     {
1463                       XEXP (src_note, 1) = REG_NOTES (p);
1464                       REG_NOTES (p) = src_note;
1465                     }
1466                   /* If there is a REG_DEAD note for DST on P, then remove
1467                      it, because DST is now set there.  */
1468                   if ((dst_note = find_reg_note (p, REG_DEAD, dst)))
1469                     remove_note (p, dst_note);
1470
1471                   dstno = REGNO (dst);
1472                   srcno = REGNO (src);
1473
1474                   REG_N_SETS (dstno)++;
1475                   REG_N_SETS (srcno)--;
1476
1477                   REG_N_CALLS_CROSSED (dstno) += num_calls;
1478                   REG_N_CALLS_CROSSED (srcno) -= num_calls;
1479
1480                   REG_LIVE_LENGTH (dstno) += length;
1481                   if (REG_LIVE_LENGTH (srcno) >= 0)
1482                     {
1483                       REG_LIVE_LENGTH (srcno) -= length;
1484                       /* REG_LIVE_LENGTH is only an approximation after
1485                          combine if sched is not run, so make sure that we
1486                          still have a reasonable value.  */
1487                       if (REG_LIVE_LENGTH (srcno) < 2)
1488                         REG_LIVE_LENGTH (srcno) = 2;
1489                     }
1490
1491                   if (dump_file)
1492                     fprintf (dump_file,
1493                              "Fixed operand %d of insn %d matching operand %d.\n",
1494                              op_no, INSN_UID (insn), match_no);
1495
1496                   break;
1497                 }
1498             }
1499
1500           /* If we weren't able to replace any of the alternatives, try an
1501              alternative approach of copying the source to the destination.  */
1502           if (!success && copy_src != NULL_RTX)
1503             copy_src_to_dest (insn, copy_src, copy_dst, old_max_uid);
1504
1505         }
1506     }
1507
1508   /* In fixup_match_1, some insns may have been inserted after basic block
1509      ends.  Fix that here.  */
1510   FOR_EACH_BB (bb)
1511     {
1512       rtx end = BB_END (bb);
1513       rtx new = end;
1514       rtx next = NEXT_INSN (new);
1515       while (next != 0 && INSN_UID (next) >= old_max_uid
1516              && (bb->next_bb == EXIT_BLOCK_PTR || BB_HEAD (bb->next_bb) != next))
1517         new = next, next = NEXT_INSN (new);
1518       BB_END (bb) = new;
1519     }
1520
1521  done:
1522   /* Clean up.  */
1523   free (regno_src_regno);
1524   free (regmove_bb_head);
1525   if (reg_set_in_bb)
1526     {
1527       free (reg_set_in_bb);
1528       reg_set_in_bb = NULL;
1529     }
1530 }
1531
1532 /* Returns nonzero if INSN's pattern has matching constraints for any operand.
1533    Returns 0 if INSN can't be recognized, or if the alternative can't be
1534    determined.
1535
1536    Initialize the info in MATCHP based on the constraints.  */
1537
1538 static int
1539 find_matches (rtx insn, struct match *matchp)
1540 {
1541   int likely_spilled[MAX_RECOG_OPERANDS];
1542   int op_no;
1543   int any_matches = 0;
1544
1545   extract_insn (insn);
1546   if (! constrain_operands (0))
1547     return 0;
1548
1549   /* Must initialize this before main loop, because the code for
1550      the commutative case may set matches for operands other than
1551      the current one.  */
1552   for (op_no = recog_data.n_operands; --op_no >= 0; )
1553     matchp->with[op_no] = matchp->commutative[op_no] = -1;
1554
1555   for (op_no = 0; op_no < recog_data.n_operands; op_no++)
1556     {
1557       const char *p;
1558       char c;
1559       int i = 0;
1560
1561       p = recog_data.constraints[op_no];
1562
1563       likely_spilled[op_no] = 0;
1564       matchp->use[op_no] = READ;
1565       matchp->early_clobber[op_no] = 0;
1566       if (*p == '=')
1567         matchp->use[op_no] = WRITE;
1568       else if (*p == '+')
1569         matchp->use[op_no] = READWRITE;
1570
1571       for (;*p && i < which_alternative; p++)
1572         if (*p == ',')
1573           i++;
1574
1575       while ((c = *p) != '\0' && c != ',')
1576         {
1577           switch (c)
1578             {
1579             case '=':
1580               break;
1581             case '+':
1582               break;
1583             case '&':
1584               matchp->early_clobber[op_no] = 1;
1585               break;
1586             case '%':
1587               matchp->commutative[op_no] = op_no + 1;
1588               matchp->commutative[op_no + 1] = op_no;
1589               break;
1590
1591             case '0': case '1': case '2': case '3': case '4':
1592             case '5': case '6': case '7': case '8': case '9':
1593               {
1594                 char *end;
1595                 unsigned long match_ul = strtoul (p, &end, 10);
1596                 int match = match_ul;
1597
1598                 p = end;
1599
1600                 if (match < op_no && likely_spilled[match])
1601                   continue;
1602                 matchp->with[op_no] = match;
1603                 any_matches = 1;
1604                 if (matchp->commutative[op_no] >= 0)
1605                   matchp->with[matchp->commutative[op_no]] = match;
1606               }
1607             continue;
1608
1609           case 'a': case 'b': case 'c': case 'd': case 'e': case 'f': case 'h':
1610           case 'j': case 'k': case 'l': case 'p': case 'q': case 't': case 'u':
1611           case 'v': case 'w': case 'x': case 'y': case 'z': case 'A': case 'B':
1612           case 'C': case 'D': case 'W': case 'Y': case 'Z':
1613             if (CLASS_LIKELY_SPILLED_P (REG_CLASS_FROM_CONSTRAINT ((unsigned char) c, p) ))
1614               likely_spilled[op_no] = 1;
1615             break;
1616           }
1617           p += CONSTRAINT_LEN (c, p);
1618         }
1619     }
1620   return any_matches;
1621 }
1622
1623 /* Try to replace all occurrences of DST_REG with SRC in LOC, that is
1624    assumed to be in INSN.  */
1625
1626 static void
1627 replace_in_call_usage (rtx *loc, unsigned int dst_reg, rtx src, rtx insn)
1628 {
1629   rtx x = *loc;
1630   enum rtx_code code;
1631   const char *fmt;
1632   int i, j;
1633
1634   if (! x)
1635     return;
1636
1637   code = GET_CODE (x);
1638   if (code == REG)
1639     {
1640       if (REGNO (x) != dst_reg)
1641         return;
1642
1643       validate_change (insn, loc, src, 1);
1644
1645       return;
1646     }
1647
1648   /* Process each of our operands recursively.  */
1649   fmt = GET_RTX_FORMAT (code);
1650   for (i = 0; i < GET_RTX_LENGTH (code); i++, fmt++)
1651     if (*fmt == 'e')
1652       replace_in_call_usage (&XEXP (x, i), dst_reg, src, insn);
1653     else if (*fmt == 'E')
1654       for (j = 0; j < XVECLEN (x, i); j++)
1655         replace_in_call_usage (& XVECEXP (x, i, j), dst_reg, src, insn);
1656 }
1657
1658 /* Try to replace output operand DST in SET, with input operand SRC.  SET is
1659    the only set in INSN.  INSN has just been recognized and constrained.
1660    SRC is operand number OPERAND_NUMBER in INSN.
1661    DST is operand number MATCH_NUMBER in INSN.
1662    If BACKWARD is nonzero, we have been called in a backward pass.
1663    Return nonzero for success.  */
1664
1665 static int
1666 fixup_match_1 (rtx insn, rtx set, rtx src, rtx src_subreg, rtx dst,
1667                int backward, int operand_number, int match_number)
1668 {
1669   rtx p;
1670   rtx post_inc = 0, post_inc_set = 0, search_end = 0;
1671   int success = 0;
1672   int num_calls = 0, s_num_calls = 0;
1673   enum rtx_code code = NOTE;
1674   HOST_WIDE_INT insn_const = 0, newconst = 0;
1675   rtx overlap = 0; /* need to move insn ? */
1676   rtx src_note = find_reg_note (insn, REG_DEAD, src), dst_note = NULL_RTX;
1677   int length, s_length;
1678
1679   if (! src_note)
1680     {
1681       /* Look for (set (regX) (op regA constX))
1682                   (set (regY) (op regA constY))
1683          and change that to
1684                   (set (regA) (op regA constX)).
1685                   (set (regY) (op regA constY-constX)).
1686          This works for add and shift operations, if
1687          regA is dead after or set by the second insn.  */
1688
1689       code = GET_CODE (SET_SRC (set));
1690       if ((code == PLUS || code == LSHIFTRT
1691            || code == ASHIFT || code == ASHIFTRT)
1692           && XEXP (SET_SRC (set), 0) == src
1693           && GET_CODE (XEXP (SET_SRC (set), 1)) == CONST_INT)
1694         insn_const = INTVAL (XEXP (SET_SRC (set), 1));
1695       else if (! stable_and_no_regs_but_for_p (SET_SRC (set), src, dst))
1696         return 0;
1697       else
1698         /* We might find a src_note while scanning.  */
1699         code = NOTE;
1700     }
1701
1702   if (dump_file)
1703     fprintf (dump_file,
1704              "Could fix operand %d of insn %d matching operand %d.\n",
1705              operand_number, INSN_UID (insn), match_number);
1706
1707   /* If SRC is equivalent to a constant set in a different basic block,
1708      then do not use it for this optimization.  We want the equivalence
1709      so that if we have to reload this register, we can reload the
1710      constant, rather than extending the lifespan of the register.  */
1711   if (reg_is_remote_constant_p (src, insn))
1712     return 0;
1713
1714   /* Scan forward to find the next instruction that
1715      uses the output operand.  If the operand dies here,
1716      then replace it in both instructions with
1717      operand_number.  */
1718
1719   for (length = s_length = 0, p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
1720     {
1721       if (CALL_P (p))
1722         replace_in_call_usage (& CALL_INSN_FUNCTION_USAGE (p),
1723                                REGNO (dst), src, p);
1724
1725       /* ??? We can't scan past the end of a basic block without updating
1726          the register lifetime info (REG_DEAD/basic_block_live_at_start).  */
1727       if (perhaps_ends_bb_p (p))
1728         break;
1729       else if (! INSN_P (p))
1730         continue;
1731
1732       length++;
1733       if (src_note)
1734         s_length++;
1735
1736       if (reg_set_p (src, p) || reg_set_p (dst, p)
1737           || (GET_CODE (PATTERN (p)) == USE
1738               && reg_overlap_mentioned_p (src, XEXP (PATTERN (p), 0))))
1739         break;
1740
1741       /* See if all of DST dies in P.  This test is
1742          slightly more conservative than it needs to be.  */
1743       if ((dst_note = find_regno_note (p, REG_DEAD, REGNO (dst)))
1744           && (GET_MODE (XEXP (dst_note, 0)) == GET_MODE (dst)))
1745         {
1746           /* If we would be moving INSN, check that we won't move it
1747              into the shadow of a live a live flags register.  */
1748           /* ??? We only try to move it in front of P, although
1749                  we could move it anywhere between OVERLAP and P.  */
1750           if (overlap && GET_MODE (PREV_INSN (p)) != VOIDmode)
1751             break;
1752
1753           if (! src_note)
1754             {
1755               rtx q;
1756               rtx set2 = NULL_RTX;
1757
1758               /* If an optimization is done, the value of SRC while P
1759                  is executed will be changed.  Check that this is OK.  */
1760               if (reg_overlap_mentioned_p (src, PATTERN (p)))
1761                 break;
1762               for (q = p; q; q = NEXT_INSN (q))
1763                 {
1764                   /* ??? We can't scan past the end of a basic block without
1765                      updating the register lifetime info
1766                      (REG_DEAD/basic_block_live_at_start).  */
1767                   if (perhaps_ends_bb_p (q))
1768                     {
1769                       q = 0;
1770                       break;
1771                     }
1772                   else if (! INSN_P (q))
1773                     continue;
1774                   else if (reg_overlap_mentioned_p (src, PATTERN (q))
1775                            || reg_set_p (src, q))
1776                     break;
1777                 }
1778               if (q)
1779                 set2 = single_set (q);
1780               if (! q || ! set2 || GET_CODE (SET_SRC (set2)) != code
1781                   || XEXP (SET_SRC (set2), 0) != src
1782                   || GET_CODE (XEXP (SET_SRC (set2), 1)) != CONST_INT
1783                   || (SET_DEST (set2) != src
1784                       && ! find_reg_note (q, REG_DEAD, src)))
1785                 {
1786                   /* If this is a PLUS, we can still save a register by doing
1787                      src += insn_const;
1788                      P;
1789                      src -= insn_const; .
1790                      This also gives opportunities for subsequent
1791                      optimizations in the backward pass, so do it there.  */
1792                   if (code == PLUS && backward
1793                       /* Don't do this if we can likely tie DST to SET_DEST
1794                          of P later; we can't do this tying here if we got a
1795                          hard register.  */
1796                       && ! (dst_note && ! REG_N_CALLS_CROSSED (REGNO (dst))
1797                             && single_set (p)
1798                             && REG_P (SET_DEST (single_set (p)))
1799                             && (REGNO (SET_DEST (single_set (p)))
1800                                 < FIRST_PSEUDO_REGISTER))
1801                       /* We may only emit an insn directly after P if we
1802                          are not in the shadow of a live flags register.  */
1803                       && GET_MODE (p) == VOIDmode)
1804                     {
1805                       search_end = q;
1806                       q = insn;
1807                       set2 = set;
1808                       newconst = -insn_const;
1809                       code = MINUS;
1810                     }
1811                   else
1812                     break;
1813                 }
1814               else
1815                 {
1816                   newconst = INTVAL (XEXP (SET_SRC (set2), 1)) - insn_const;
1817                   /* Reject out of range shifts.  */
1818                   if (code != PLUS
1819                       && (newconst < 0
1820                           || ((unsigned HOST_WIDE_INT) newconst
1821                               >= (GET_MODE_BITSIZE (GET_MODE
1822                                                     (SET_SRC (set2)))))))
1823                     break;
1824                   if (code == PLUS)
1825                     {
1826                       post_inc = q;
1827                       if (SET_DEST (set2) != src)
1828                         post_inc_set = set2;
1829                     }
1830                 }
1831               /* We use 1 as last argument to validate_change so that all
1832                  changes are accepted or rejected together by apply_change_group
1833                  when it is called by validate_replace_rtx .  */
1834               validate_change (q, &XEXP (SET_SRC (set2), 1),
1835                                GEN_INT (newconst), 1);
1836             }
1837           validate_change (insn, recog_data.operand_loc[match_number], src, 1);
1838           if (validate_replace_rtx (dst, src_subreg, p))
1839             success = 1;
1840           break;
1841         }
1842
1843       if (reg_overlap_mentioned_p (dst, PATTERN (p)))
1844         break;
1845       if (! src_note && reg_overlap_mentioned_p (src, PATTERN (p)))
1846         {
1847           /* INSN was already checked to be movable wrt. the registers that it
1848              sets / uses when we found no REG_DEAD note for src on it, but it
1849              still might clobber the flags register.  We'll have to check that
1850              we won't insert it into the shadow of a live flags register when
1851              we finally know where we are to move it.  */
1852           overlap = p;
1853           src_note = find_reg_note (p, REG_DEAD, src);
1854         }
1855
1856       /* If we have passed a call instruction, and the pseudo-reg SRC is not
1857          already live across a call, then don't perform the optimization.  */
1858       if (CALL_P (p))
1859         {
1860           if (REG_N_CALLS_CROSSED (REGNO (src)) == 0)
1861             break;
1862
1863           num_calls++;
1864
1865           if (src_note)
1866             s_num_calls++;
1867
1868         }
1869     }
1870
1871   if (! success)
1872     return 0;
1873
1874   /* Remove the death note for DST from P.  */
1875   remove_note (p, dst_note);
1876   if (code == MINUS)
1877     {
1878       post_inc = emit_insn_after (copy_rtx (PATTERN (insn)), p);
1879       if ((HAVE_PRE_INCREMENT || HAVE_PRE_DECREMENT)
1880           && search_end
1881           && try_auto_increment (search_end, post_inc, 0, src, newconst, 1))
1882         post_inc = 0;
1883       validate_change (insn, &XEXP (SET_SRC (set), 1), GEN_INT (insn_const), 0);
1884       REG_N_SETS (REGNO (src))++;
1885       REG_LIVE_LENGTH (REGNO (src))++;
1886     }
1887   if (overlap)
1888     {
1889       /* The lifetime of src and dest overlap,
1890          but we can change this by moving insn.  */
1891       rtx pat = PATTERN (insn);
1892       if (src_note)
1893         remove_note (overlap, src_note);
1894       if ((HAVE_POST_INCREMENT || HAVE_POST_DECREMENT)
1895           && code == PLUS
1896           && try_auto_increment (overlap, insn, 0, src, insn_const, 0))
1897         insn = overlap;
1898       else
1899         {
1900           rtx notes = REG_NOTES (insn);
1901
1902           p = emit_insn_after_setloc (pat, PREV_INSN (p), INSN_LOCATOR (insn));
1903           delete_insn (insn);
1904           REG_NOTES (p) = notes;
1905         }
1906     }
1907   /* Sometimes we'd generate src = const; src += n;
1908      if so, replace the instruction that set src
1909      in the first place.  */
1910
1911   if (! overlap && (code == PLUS || code == MINUS))
1912     {
1913       rtx note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
1914       rtx q, set2 = NULL_RTX;
1915       int num_calls2 = 0, s_length2 = 0;
1916
1917       if (note && CONSTANT_P (XEXP (note, 0)))
1918         {
1919           for (q = PREV_INSN (insn); q; q = PREV_INSN (q))
1920             {
1921               /* ??? We can't scan past the end of a basic block without
1922                  updating the register lifetime info
1923                  (REG_DEAD/basic_block_live_at_start).  */
1924               if (perhaps_ends_bb_p (q))
1925                 {
1926                   q = 0;
1927                   break;
1928                 }
1929               else if (! INSN_P (q))
1930                 continue;
1931
1932               s_length2++;
1933               if (reg_set_p (src, q))
1934                 {
1935                   set2 = single_set (q);
1936                   break;
1937                 }
1938               if (reg_overlap_mentioned_p (src, PATTERN (q)))
1939                 {
1940                   q = 0;
1941                   break;
1942                 }
1943               if (CALL_P (p))
1944                 num_calls2++;
1945             }
1946           if (q && set2 && SET_DEST (set2) == src && CONSTANT_P (SET_SRC (set2))
1947               && validate_change (insn, &SET_SRC (set), XEXP (note, 0), 0))
1948             {
1949               delete_insn (q);
1950               REG_N_SETS (REGNO (src))--;
1951               REG_N_CALLS_CROSSED (REGNO (src)) -= num_calls2;
1952               REG_LIVE_LENGTH (REGNO (src)) -= s_length2;
1953               insn_const = 0;
1954             }
1955         }
1956     }
1957
1958   if ((HAVE_PRE_INCREMENT || HAVE_PRE_DECREMENT)
1959            && (code == PLUS || code == MINUS) && insn_const
1960            && try_auto_increment (p, insn, 0, src, insn_const, 1))
1961     insn = p;
1962   else if ((HAVE_POST_INCREMENT || HAVE_POST_DECREMENT)
1963            && post_inc
1964            && try_auto_increment (p, post_inc, post_inc_set, src, newconst, 0))
1965     post_inc = 0;
1966   /* If post_inc still prevails, try to find an
1967      insn where it can be used as a pre-in/decrement.
1968      If code is MINUS, this was already tried.  */
1969   if (post_inc && code == PLUS
1970   /* Check that newconst is likely to be usable
1971      in a pre-in/decrement before starting the search.  */
1972       && ((HAVE_PRE_INCREMENT && newconst > 0 && newconst <= MOVE_MAX)
1973           || (HAVE_PRE_DECREMENT && newconst < 0 && newconst >= -MOVE_MAX))
1974       && exact_log2 (newconst))
1975     {
1976       rtx q, inc_dest;
1977
1978       inc_dest = post_inc_set ? SET_DEST (post_inc_set) : src;
1979       for (q = post_inc; (q = NEXT_INSN (q)); )
1980         {
1981           /* ??? We can't scan past the end of a basic block without updating
1982              the register lifetime info
1983              (REG_DEAD/basic_block_live_at_start).  */
1984           if (perhaps_ends_bb_p (q))
1985             break;
1986           else if (! INSN_P (q))
1987             continue;
1988           else if (src != inc_dest
1989                    && (reg_overlap_mentioned_p (src, PATTERN (q))
1990                        || reg_set_p (src, q)))
1991             break;
1992           else if (reg_set_p (inc_dest, q))
1993             break;
1994           else if (reg_overlap_mentioned_p (inc_dest, PATTERN (q)))
1995             {
1996               try_auto_increment (q, post_inc,
1997                                   post_inc_set, inc_dest, newconst, 1);
1998               break;
1999             }
2000         }
2001     }
2002
2003   /* Move the death note for DST to INSN if it is used
2004      there.  */
2005   if (reg_overlap_mentioned_p (dst, PATTERN (insn)))
2006     {
2007       XEXP (dst_note, 1) = REG_NOTES (insn);
2008       REG_NOTES (insn) = dst_note;
2009     }
2010
2011   if (src_note)
2012     {
2013       /* Move the death note for SRC from INSN to P.  */
2014       if (! overlap)
2015         remove_note (insn, src_note);
2016       XEXP (src_note, 1) = REG_NOTES (p);
2017       REG_NOTES (p) = src_note;
2018
2019       REG_N_CALLS_CROSSED (REGNO (src)) += s_num_calls;
2020     }
2021
2022   REG_N_SETS (REGNO (src))++;
2023   REG_N_SETS (REGNO (dst))--;
2024
2025   REG_N_CALLS_CROSSED (REGNO (dst)) -= num_calls;
2026
2027   REG_LIVE_LENGTH (REGNO (src)) += s_length;
2028   if (REG_LIVE_LENGTH (REGNO (dst)) >= 0)
2029     {
2030       REG_LIVE_LENGTH (REGNO (dst)) -= length;
2031       /* REG_LIVE_LENGTH is only an approximation after
2032          combine if sched is not run, so make sure that we
2033          still have a reasonable value.  */
2034       if (REG_LIVE_LENGTH (REGNO (dst)) < 2)
2035         REG_LIVE_LENGTH (REGNO (dst)) = 2;
2036     }
2037   if (dump_file)
2038     fprintf (dump_file,
2039              "Fixed operand %d of insn %d matching operand %d.\n",
2040              operand_number, INSN_UID (insn), match_number);
2041   return 1;
2042 }
2043
2044
2045 /* Return nonzero if X is stable and mentions no registers but for
2046    mentioning SRC or mentioning / changing DST .  If in doubt, presume
2047    it is unstable.
2048    The rationale is that we want to check if we can move an insn easily
2049    while just paying attention to SRC and DST.  */
2050 static int
2051 stable_and_no_regs_but_for_p (rtx x, rtx src, rtx dst)
2052 {
2053   RTX_CODE code = GET_CODE (x);
2054   switch (GET_RTX_CLASS (code))
2055     {
2056     case RTX_UNARY:
2057     case RTX_BIN_ARITH:
2058     case RTX_COMM_ARITH:
2059     case RTX_COMPARE:
2060     case RTX_COMM_COMPARE:
2061     case RTX_TERNARY:
2062     case RTX_BITFIELD_OPS:
2063       {
2064         int i;
2065         const char *fmt = GET_RTX_FORMAT (code);
2066         for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2067           if (fmt[i] == 'e'
2068               && ! stable_and_no_regs_but_for_p (XEXP (x, i), src, dst))
2069               return 0;
2070         return 1;
2071       }
2072     case RTX_OBJ:
2073       if (code == REG)
2074         return x == src || x == dst;
2075       /* If this is a MEM, look inside - there might be a register hidden in
2076          the address of an unchanging MEM.  */
2077       if (code == MEM
2078           && ! stable_and_no_regs_but_for_p (XEXP (x, 0), src, dst))
2079         return 0;
2080       /* Fall through.  */
2081     default:
2082       return ! rtx_unstable_p (x);
2083     }
2084 }
2085 \f
2086 /* Track stack adjustments and stack memory references.  Attempt to
2087    reduce the number of stack adjustments by back-propagating across
2088    the memory references.
2089
2090    This is intended primarily for use with targets that do not define
2091    ACCUMULATE_OUTGOING_ARGS.  It is of significantly more value to
2092    targets that define PREFERRED_STACK_BOUNDARY more aligned than
2093    STACK_BOUNDARY (e.g. x86), or if not all registers can be pushed
2094    (e.g. x86 fp regs) which would ordinarily have to be implemented
2095    as a sub/mov pair due to restrictions in calls.c.
2096
2097    Propagation stops when any of the insns that need adjusting are
2098    (a) no longer valid because we've exceeded their range, (b) a
2099    non-trivial push instruction, or (c) a call instruction.
2100
2101    Restriction B is based on the assumption that push instructions
2102    are smaller or faster.  If a port really wants to remove all
2103    pushes, it should have defined ACCUMULATE_OUTGOING_ARGS.  The
2104    one exception that is made is for an add immediately followed
2105    by a push.  */
2106
2107 /* This structure records stack memory references between stack adjusting
2108    instructions.  */
2109
2110 struct csa_memlist
2111 {
2112   HOST_WIDE_INT sp_offset;
2113   rtx insn, *mem;
2114   struct csa_memlist *next;
2115 };
2116
2117 static int stack_memref_p (rtx);
2118 static rtx single_set_for_csa (rtx);
2119 static void free_csa_memlist (struct csa_memlist *);
2120 static struct csa_memlist *record_one_stack_memref (rtx, rtx *,
2121                                                     struct csa_memlist *);
2122 static int try_apply_stack_adjustment (rtx, struct csa_memlist *,
2123                                        HOST_WIDE_INT, HOST_WIDE_INT);
2124 static void combine_stack_adjustments_for_block (basic_block);
2125 static int record_stack_memrefs (rtx *, void *);
2126
2127
2128 /* Main entry point for stack adjustment combination.  */
2129
2130 static void
2131 combine_stack_adjustments (void)
2132 {
2133   basic_block bb;
2134
2135   FOR_EACH_BB (bb)
2136     combine_stack_adjustments_for_block (bb);
2137 }
2138
2139 /* Recognize a MEM of the form (sp) or (plus sp const).  */
2140
2141 static int
2142 stack_memref_p (rtx x)
2143 {
2144   if (!MEM_P (x))
2145     return 0;
2146   x = XEXP (x, 0);
2147
2148   if (x == stack_pointer_rtx)
2149     return 1;
2150   if (GET_CODE (x) == PLUS
2151       && XEXP (x, 0) == stack_pointer_rtx
2152       && GET_CODE (XEXP (x, 1)) == CONST_INT)
2153     return 1;
2154
2155   return 0;
2156 }
2157
2158 /* Recognize either normal single_set or the hack in i386.md for
2159    tying fp and sp adjustments.  */
2160
2161 static rtx
2162 single_set_for_csa (rtx insn)
2163 {
2164   int i;
2165   rtx tmp = single_set (insn);
2166   if (tmp)
2167     return tmp;
2168
2169   if (!NONJUMP_INSN_P (insn)
2170       || GET_CODE (PATTERN (insn)) != PARALLEL)
2171     return NULL_RTX;
2172
2173   tmp = PATTERN (insn);
2174   if (GET_CODE (XVECEXP (tmp, 0, 0)) != SET)
2175     return NULL_RTX;
2176
2177   for (i = 1; i < XVECLEN (tmp, 0); ++i)
2178     {
2179       rtx this = XVECEXP (tmp, 0, i);
2180
2181       /* The special case is allowing a no-op set.  */
2182       if (GET_CODE (this) == SET
2183           && SET_SRC (this) == SET_DEST (this))
2184         ;
2185       else if (GET_CODE (this) != CLOBBER
2186                && GET_CODE (this) != USE)
2187         return NULL_RTX;
2188     }
2189
2190   return XVECEXP (tmp, 0, 0);
2191 }
2192
2193 /* Free the list of csa_memlist nodes.  */
2194
2195 static void
2196 free_csa_memlist (struct csa_memlist *memlist)
2197 {
2198   struct csa_memlist *next;
2199   for (; memlist ; memlist = next)
2200     {
2201       next = memlist->next;
2202       free (memlist);
2203     }
2204 }
2205
2206 /* Create a new csa_memlist node from the given memory reference.
2207    It is already known that the memory is stack_memref_p.  */
2208
2209 static struct csa_memlist *
2210 record_one_stack_memref (rtx insn, rtx *mem, struct csa_memlist *next_memlist)
2211 {
2212   struct csa_memlist *ml;
2213
2214   ml = XNEW (struct csa_memlist);
2215
2216   if (XEXP (*mem, 0) == stack_pointer_rtx)
2217     ml->sp_offset = 0;
2218   else
2219     ml->sp_offset = INTVAL (XEXP (XEXP (*mem, 0), 1));
2220
2221   ml->insn = insn;
2222   ml->mem = mem;
2223   ml->next = next_memlist;
2224
2225   return ml;
2226 }
2227
2228 /* Attempt to apply ADJUST to the stack adjusting insn INSN, as well
2229    as each of the memories in MEMLIST.  Return true on success.  */
2230
2231 static int
2232 try_apply_stack_adjustment (rtx insn, struct csa_memlist *memlist, HOST_WIDE_INT new_adjust,
2233                             HOST_WIDE_INT delta)
2234 {
2235   struct csa_memlist *ml;
2236   rtx set;
2237
2238   set = single_set_for_csa (insn);
2239   validate_change (insn, &XEXP (SET_SRC (set), 1), GEN_INT (new_adjust), 1);
2240
2241   for (ml = memlist; ml ; ml = ml->next)
2242     validate_change
2243       (ml->insn, ml->mem,
2244        replace_equiv_address_nv (*ml->mem,
2245                                  plus_constant (stack_pointer_rtx,
2246                                                 ml->sp_offset - delta)), 1);
2247
2248   if (apply_change_group ())
2249     {
2250       /* Succeeded.  Update our knowledge of the memory references.  */
2251       for (ml = memlist; ml ; ml = ml->next)
2252         ml->sp_offset -= delta;
2253
2254       return 1;
2255     }
2256   else
2257     return 0;
2258 }
2259
2260 /* Called via for_each_rtx and used to record all stack memory references in
2261    the insn and discard all other stack pointer references.  */
2262 struct record_stack_memrefs_data
2263 {
2264   rtx insn;
2265   struct csa_memlist *memlist;
2266 };
2267
2268 static int
2269 record_stack_memrefs (rtx *xp, void *data)
2270 {
2271   rtx x = *xp;
2272   struct record_stack_memrefs_data *d =
2273     (struct record_stack_memrefs_data *) data;
2274   if (!x)
2275     return 0;
2276   switch (GET_CODE (x))
2277     {
2278     case MEM:
2279       if (!reg_mentioned_p (stack_pointer_rtx, x))
2280         return -1;
2281       /* We are not able to handle correctly all possible memrefs containing
2282          stack pointer, so this check is necessary.  */
2283       if (stack_memref_p (x))
2284         {
2285           d->memlist = record_one_stack_memref (d->insn, xp, d->memlist);
2286           return -1;
2287         }
2288       return 1;
2289     case REG:
2290       /* ??? We want be able to handle non-memory stack pointer
2291          references later.  For now just discard all insns referring to
2292          stack pointer outside mem expressions.  We would probably
2293          want to teach validate_replace to simplify expressions first.
2294
2295          We can't just compare with STACK_POINTER_RTX because the
2296          reference to the stack pointer might be in some other mode.
2297          In particular, an explicit clobber in an asm statement will
2298          result in a QImode clobber.  */
2299       if (REGNO (x) == STACK_POINTER_REGNUM)
2300         return 1;
2301       break;
2302     default:
2303       break;
2304     }
2305   return 0;
2306 }
2307
2308 /* Subroutine of combine_stack_adjustments, called for each basic block.  */
2309
2310 static void
2311 combine_stack_adjustments_for_block (basic_block bb)
2312 {
2313   HOST_WIDE_INT last_sp_adjust = 0;
2314   rtx last_sp_set = NULL_RTX;
2315   struct csa_memlist *memlist = NULL;
2316   rtx insn, next, set;
2317   struct record_stack_memrefs_data data;
2318   bool end_of_block = false;
2319
2320   for (insn = BB_HEAD (bb); !end_of_block ; insn = next)
2321     {
2322       end_of_block = insn == BB_END (bb);
2323       next = NEXT_INSN (insn);
2324
2325       if (! INSN_P (insn))
2326         continue;
2327
2328       set = single_set_for_csa (insn);
2329       if (set)
2330         {
2331           rtx dest = SET_DEST (set);
2332           rtx src = SET_SRC (set);
2333
2334           /* Find constant additions to the stack pointer.  */
2335           if (dest == stack_pointer_rtx
2336               && GET_CODE (src) == PLUS
2337               && XEXP (src, 0) == stack_pointer_rtx
2338               && GET_CODE (XEXP (src, 1)) == CONST_INT)
2339             {
2340               HOST_WIDE_INT this_adjust = INTVAL (XEXP (src, 1));
2341
2342               /* If we've not seen an adjustment previously, record
2343                  it now and continue.  */
2344               if (! last_sp_set)
2345                 {
2346                   last_sp_set = insn;
2347                   last_sp_adjust = this_adjust;
2348                   continue;
2349                 }
2350
2351               /* If not all recorded memrefs can be adjusted, or the
2352                  adjustment is now too large for a constant addition,
2353                  we cannot merge the two stack adjustments.
2354
2355                  Also we need to be careful to not move stack pointer
2356                  such that we create stack accesses outside the allocated
2357                  area.  We can combine an allocation into the first insn,
2358                  or a deallocation into the second insn.  We can not
2359                  combine an allocation followed by a deallocation.
2360
2361                  The only somewhat frequent occurrence of the later is when
2362                  a function allocates a stack frame but does not use it.
2363                  For this case, we would need to analyze rtl stream to be
2364                  sure that allocated area is really unused.  This means not
2365                  only checking the memory references, but also all registers
2366                  or global memory references possibly containing a stack
2367                  frame address.
2368
2369                  Perhaps the best way to address this problem is to teach
2370                  gcc not to allocate stack for objects never used.  */
2371
2372               /* Combine an allocation into the first instruction.  */
2373               if (STACK_GROWS_DOWNWARD ? this_adjust <= 0 : this_adjust >= 0)
2374                 {
2375                   if (try_apply_stack_adjustment (last_sp_set, memlist,
2376                                                   last_sp_adjust + this_adjust,
2377                                                   this_adjust))
2378                     {
2379                       /* It worked!  */
2380                       delete_insn (insn);
2381                       last_sp_adjust += this_adjust;
2382                       continue;
2383                     }
2384                 }
2385
2386               /* Otherwise we have a deallocation.  Do not combine with
2387                  a previous allocation.  Combine into the second insn.  */
2388               else if (STACK_GROWS_DOWNWARD
2389                        ? last_sp_adjust >= 0 : last_sp_adjust <= 0)
2390                 {
2391                   if (try_apply_stack_adjustment (insn, memlist,
2392                                                   last_sp_adjust + this_adjust,
2393                                                   -last_sp_adjust))
2394                     {
2395                       /* It worked!  */
2396                       delete_insn (last_sp_set);
2397                       last_sp_set = insn;
2398                       last_sp_adjust += this_adjust;
2399                       free_csa_memlist (memlist);
2400                       memlist = NULL;
2401                       continue;
2402                     }
2403                 }
2404
2405               /* Combination failed.  Restart processing from here.  If
2406                  deallocation+allocation conspired to cancel, we can
2407                  delete the old deallocation insn.  */
2408               if (last_sp_set && last_sp_adjust == 0)
2409                 delete_insn (insn);
2410               free_csa_memlist (memlist);
2411               memlist = NULL;
2412               last_sp_set = insn;
2413               last_sp_adjust = this_adjust;
2414               continue;
2415             }
2416
2417           /* Find a predecrement of exactly the previous adjustment and
2418              turn it into a direct store.  Obviously we can't do this if
2419              there were any intervening uses of the stack pointer.  */
2420           if (memlist == NULL
2421               && MEM_P (dest)
2422               && ((GET_CODE (XEXP (dest, 0)) == PRE_DEC
2423                    && (last_sp_adjust
2424                        == (HOST_WIDE_INT) GET_MODE_SIZE (GET_MODE (dest))))
2425                   || (GET_CODE (XEXP (dest, 0)) == PRE_MODIFY
2426                       && GET_CODE (XEXP (XEXP (dest, 0), 1)) == PLUS
2427                       && XEXP (XEXP (XEXP (dest, 0), 1), 0) == stack_pointer_rtx
2428                       && (GET_CODE (XEXP (XEXP (XEXP (dest, 0), 1), 1))
2429                           == CONST_INT)
2430                       && (INTVAL (XEXP (XEXP (XEXP (dest, 0), 1), 1))
2431                           == -last_sp_adjust)))
2432               && XEXP (XEXP (dest, 0), 0) == stack_pointer_rtx
2433               && ! reg_mentioned_p (stack_pointer_rtx, src)
2434               && memory_address_p (GET_MODE (dest), stack_pointer_rtx)
2435               && validate_change (insn, &SET_DEST (set),
2436                                   replace_equiv_address (dest,
2437                                                          stack_pointer_rtx),
2438                                   0))
2439             {
2440               delete_insn (last_sp_set);
2441               free_csa_memlist (memlist);
2442               memlist = NULL;
2443               last_sp_set = NULL_RTX;
2444               last_sp_adjust = 0;
2445               continue;
2446             }
2447         }
2448
2449       data.insn = insn;
2450       data.memlist = memlist;
2451       if (!CALL_P (insn) && last_sp_set
2452           && !for_each_rtx (&PATTERN (insn), record_stack_memrefs, &data))
2453         {
2454            memlist = data.memlist;
2455            continue;
2456         }
2457       memlist = data.memlist;
2458
2459       /* Otherwise, we were not able to process the instruction.
2460          Do not continue collecting data across such a one.  */
2461       if (last_sp_set
2462           && (CALL_P (insn)
2463               || reg_mentioned_p (stack_pointer_rtx, PATTERN (insn))))
2464         {
2465           if (last_sp_set && last_sp_adjust == 0)
2466             delete_insn (last_sp_set);
2467           free_csa_memlist (memlist);
2468           memlist = NULL;
2469           last_sp_set = NULL_RTX;
2470           last_sp_adjust = 0;
2471         }
2472     }
2473
2474   if (last_sp_set && last_sp_adjust == 0)
2475     delete_insn (last_sp_set);
2476
2477   if (memlist)
2478     free_csa_memlist (memlist);
2479 }
2480 \f
2481 static bool
2482 gate_handle_regmove (void)
2483 {
2484   return (optimize > 0 && flag_regmove);
2485 }
2486
2487
2488 /* Register allocation pre-pass, to reduce number of moves necessary
2489    for two-address machines.  */
2490 static unsigned int
2491 rest_of_handle_regmove (void)
2492 {
2493   regmove_optimize (get_insns (), max_reg_num ());
2494   cleanup_cfg (CLEANUP_EXPENSIVE | CLEANUP_UPDATE_LIFE);
2495   return 0;
2496 }
2497
2498 struct tree_opt_pass pass_regmove =
2499 {
2500   "regmove",                            /* name */
2501   gate_handle_regmove,                  /* gate */
2502   rest_of_handle_regmove,               /* execute */
2503   NULL,                                 /* sub */
2504   NULL,                                 /* next */
2505   0,                                    /* static_pass_number */
2506   TV_REGMOVE,                           /* tv_id */
2507   0,                                    /* properties_required */
2508   0,                                    /* properties_provided */
2509   0,                                    /* properties_destroyed */
2510   0,                                    /* todo_flags_start */
2511   TODO_dump_func |
2512   TODO_ggc_collect,                     /* todo_flags_finish */
2513   'N'                                   /* letter */
2514 };
2515
2516
2517 static bool
2518 gate_handle_stack_adjustments (void)
2519 {
2520   return (optimize > 0);
2521 }
2522
2523 static unsigned int
2524 rest_of_handle_stack_adjustments (void)
2525 {
2526   life_analysis (PROP_POSTRELOAD);
2527   cleanup_cfg (CLEANUP_EXPENSIVE | CLEANUP_UPDATE_LIFE
2528                | (flag_crossjumping ? CLEANUP_CROSSJUMP : 0));
2529
2530   /* This is kind of a heuristic.  We need to run combine_stack_adjustments
2531      even for machines with possibly nonzero RETURN_POPS_ARGS
2532      and ACCUMULATE_OUTGOING_ARGS.  We expect that only ports having
2533      push instructions will have popping returns.  */
2534 #ifndef PUSH_ROUNDING
2535   if (!ACCUMULATE_OUTGOING_ARGS)
2536 #endif
2537     combine_stack_adjustments ();
2538   return 0;
2539 }
2540
2541 struct tree_opt_pass pass_stack_adjustments =
2542 {
2543   "csa",                                /* name */
2544   gate_handle_stack_adjustments,        /* gate */
2545   rest_of_handle_stack_adjustments,     /* execute */
2546   NULL,                                 /* sub */
2547   NULL,                                 /* next */
2548   0,                                    /* static_pass_number */
2549   0,                                    /* tv_id */
2550   0,                                    /* properties_required */
2551   0,                                    /* properties_provided */
2552   0,                                    /* properties_destroyed */
2553   0,                                    /* todo_flags_start */
2554   TODO_dump_func |
2555   TODO_ggc_collect,                     /* todo_flags_finish */
2556   0                                     /* letter */
2557 };
2558