OSDN Git Service

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