OSDN Git Service

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