OSDN Git Service

fc563b64fe7d38c5d231dc51b098b805c505d218
[pf3gnuchains/gcc-fork.git] / gcc / struct-equiv.c
1 /* Control flow optimization code for GNU compiler.
2    Copyright (C) 1987, 1988, 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 /* Try to match two basic blocks - or their ends - for structural equivalence.
23    We scan the blocks from their ends backwards, and expect that insns are
24    identical, except for certain cases involving registers.  A mismatch
25    We scan the blocks from their ends backwards, hoping to find a match, I.e.
26    insns are identical, except for certain cases involving registers.  A
27    mismatch between register number RX (used in block X) and RY (used in the
28    same way in block Y) can be handled in one of the following cases:
29    1. RX and RY are local to their respective blocks; they are set there and
30       die there.  If so, they can effectively be ignored.
31    2. RX and RY die in their blocks, but live at the start.  If any path
32       gets redirected through X instead of Y, the caller must emit
33       compensation code to move RY to RX.  If there are overlapping inputs,
34       the function resolve_input_conflict ensures that this can be done.
35       Information about these registers are tracked in the X_LOCAL, Y_LOCAL,
36       LOCAL_COUNT and LOCAL_RVALUE fields.
37    3. RX and RY live throughout their blocks, including the start and the end.
38       Either RX and RY must be identical, or we have to replace all uses in
39       block X with a new pseudo, which is stored in the INPUT_REG field.  The
40       caller can then use block X instead of block Y by copying RY to the new
41       pseudo.
42
43    The main entry point to this file is struct_equiv_block_eq.  This function
44    uses a struct equiv_info to accept some of its inputs, to keep track of its
45    internal state, to pass down to its helper functions, and to communicate
46    some of the results back to the caller.
47
48    Most scans will result in a failure to match a sufficient number of insns
49    to make any optimization worth while, therefore the process is geared more
50    to quick scanning rather than the ability to exactly backtrack when we
51    find a mismatch.  The information gathered is still meaningful to make a
52    preliminary decision if we want to do an optimization, we might only
53    slightly overestimate the number of matchable insns, and underestimate
54    the number of inputs an miss an input conflict.  Sufficient information
55    is gathered so that when we make another pass, we won't have to backtrack
56    at the same point.
57    Another issue is that information in memory atttributes and/or REG_NOTES
58    might have to be merged or discarded to make a valid match.  We don't want
59    to discard such information when we are not certain that we want to merge
60    the two (partial) blocks.
61    For these reasons, struct_equiv_block_eq has to be called first with the
62    STRUCT_EQUIV_START bit set in the mode parameter.  This will calculate the
63    number of matched insns and the number and types of inputs.  If the
64    need_rerun field is set, the results are only tentative, and the caller
65    has to call again with STRUCT_EQUIV_RERUN till need_rerun is false in
66    order to get a reliable match.
67    To install the changes necessary for the match, the function has to be
68    called again with STRUCT_EQUIV_FINAL.
69
70    While scanning an insn, we process first all the SET_DESTs, then the
71    SET_SRCes, then the REG_NOTES, in order to keep the register liveness
72    information consistent.
73    If we were to mix up the order for sources / destinations in an insn where
74    a source is also a destination, we'd end up being mistaken to think that
75    the register is not live in the preceding insn.  */
76
77 #include "config.h"
78 #include "system.h"
79 #include "coretypes.h"
80 #include "tm.h"
81 #include "rtl.h"
82 #include "regs.h"
83 #include "output.h"
84 #include "insn-config.h"
85 #include "flags.h"
86 #include "recog.h"
87 #include "tm_p.h"
88 #include "target.h"
89 #include "emit-rtl.h"
90 #include "reload.h"
91
92 static void merge_memattrs (rtx, rtx);
93 static bool set_dest_equiv_p (rtx x, rtx y, struct equiv_info *info);
94 static bool set_dest_addr_equiv_p (rtx x, rtx y, struct equiv_info *info);
95 static void find_dying_inputs (struct equiv_info *info);
96 static bool resolve_input_conflict (struct equiv_info *info);
97
98 /* After reload, some moves, as indicated by SECONDARY_RELOAD_CLASS and
99    SECONDARY_MEMORY_NEEDED, cannot be done directly.  For our purposes, we
100    consider them impossible to generate after reload (even though some
101    might be synthesized when you throw enough code at them).
102    Since we don't know while procesing a cross-jump if a local register
103    that is currently live will eventually be live and thus be an input,
104    we keep track of potential inputs that would require an impossible move
105    by using a prohibitively high cost for them.
106    This number, multiplied with the larger of STRUCT_EQUIV_MAX_LOCAL and
107    FIRST_PSEUDO_REGISTER, must fit in the input_cost field of
108    struct equiv_info.  */
109 #define IMPOSSIBLE_MOVE_FACTOR 20000
110
111 \f
112
113 /* Removes the memory attributes of MEM expression
114    if they are not equal.  */
115
116 void
117 merge_memattrs (rtx x, rtx y)
118 {
119   int i;
120   int j;
121   enum rtx_code code;
122   const char *fmt;
123
124   if (x == y)
125     return;
126   if (x == 0 || y == 0)
127     return;
128
129   code = GET_CODE (x);
130
131   if (code != GET_CODE (y))
132     return;
133
134   if (GET_MODE (x) != GET_MODE (y))
135     return;
136
137   if (code == MEM && MEM_ATTRS (x) != MEM_ATTRS (y))
138     {
139       if (! MEM_ATTRS (x))
140         MEM_ATTRS (y) = 0;
141       else if (! MEM_ATTRS (y))
142         MEM_ATTRS (x) = 0;
143       else
144         {
145           rtx mem_size;
146
147           if (MEM_ALIAS_SET (x) != MEM_ALIAS_SET (y))
148             {
149               set_mem_alias_set (x, 0);
150               set_mem_alias_set (y, 0);
151             }
152
153           if (! mem_expr_equal_p (MEM_EXPR (x), MEM_EXPR (y)))
154             {
155               set_mem_expr (x, 0);
156               set_mem_expr (y, 0);
157               set_mem_offset (x, 0);
158               set_mem_offset (y, 0);
159             }
160           else if (MEM_OFFSET (x) != MEM_OFFSET (y))
161             {
162               set_mem_offset (x, 0);
163               set_mem_offset (y, 0);
164             }
165
166           if (!MEM_SIZE (x))
167             mem_size = NULL_RTX;
168           else if (!MEM_SIZE (y))
169             mem_size = NULL_RTX;
170           else
171             mem_size = GEN_INT (MAX (INTVAL (MEM_SIZE (x)),
172                                      INTVAL (MEM_SIZE (y))));
173           set_mem_size (x, mem_size);
174           set_mem_size (y, mem_size);
175
176           set_mem_align (x, MIN (MEM_ALIGN (x), MEM_ALIGN (y)));
177           set_mem_align (y, MEM_ALIGN (x));
178         }
179     }
180
181   fmt = GET_RTX_FORMAT (code);
182   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
183     {
184       switch (fmt[i])
185         {
186         case 'E':
187           /* Two vectors must have the same length.  */
188           if (XVECLEN (x, i) != XVECLEN (y, i))
189             return;
190
191           for (j = 0; j < XVECLEN (x, i); j++)
192             merge_memattrs (XVECEXP (x, i, j), XVECEXP (y, i, j));
193
194           break;
195
196         case 'e':
197           merge_memattrs (XEXP (x, i), XEXP (y, i));
198         }
199     }
200   return;
201 }
202
203 /* In SET, assign the bit for the register number of REG the value VALUE.
204    If REG is a hard register, do so for all its consituent registers.
205    Return the number of registers that have become included (as a positive
206    number) or excluded (as a negative number).  */
207 static int
208 assign_reg_reg_set (regset set, rtx reg, int value)
209 {
210   unsigned regno = REGNO (reg);
211   int nregs, i, old;
212
213   if (regno >= FIRST_PSEUDO_REGISTER)
214     {
215       gcc_assert (!reload_completed);
216       nregs = 1;
217     }
218   else
219     nregs = hard_regno_nregs[regno][GET_MODE (reg)];
220   for (old = 0, i = nregs; --i >= 0; regno++)
221     {
222       if ((value != 0) == REGNO_REG_SET_P (set, regno))
223         continue;
224       if (value)
225         old++, SET_REGNO_REG_SET (set, regno);
226       else
227         old--, CLEAR_REGNO_REG_SET (set, regno);
228     }
229   return old;
230 }
231
232 /* Record state about current inputs / local registers / liveness
233    in *P.  */
234 static inline void
235 struct_equiv_make_checkpoint (struct struct_equiv_checkpoint *p,
236                               struct equiv_info *info)
237 {
238   *p = info->cur;
239 }
240
241 /* Call struct_equiv_make_checkpoint (P, INFO) if the current partial block
242    is suitable to split off - i.e. there is no dangling cc0 user - and
243    if the current cost of the common instructions, minus the cost for
244    setting up the inputs, is higher than what has been recorded before
245    in CHECKPOINT[N].  Also, if we do so, confirm or cancel any pending
246    changes.  */
247 static void
248 struct_equiv_improve_checkpoint (struct struct_equiv_checkpoint *p,
249                                  struct equiv_info *info)
250 {
251 #ifdef HAVE_cc0
252   if (reg_mentioned_p (cc0_rtx, info->x_start) && !sets_cc0_p (info->x_start))
253     return;
254 #endif
255   if (info->cur.input_count >= IMPOSSIBLE_MOVE_FACTOR)
256     return;
257   if (info->input_cost >= 0
258       ? (COSTS_N_INSNS(info->cur.ninsns - p->ninsns)
259          > info->input_cost * (info->cur.input_count - p->input_count))
260       : info->cur.ninsns > p->ninsns && !info->cur.input_count)
261     {
262       if (info->check_input_conflict && ! resolve_input_conflict (info))
263         return;
264       /* We have a profitable set of changes.  If this is the final pass,
265          commit them now.  Otherwise, we don't know yet if we can make any
266          change, so put the old code back for now.  */
267       if (info->mode & STRUCT_EQUIV_FINAL)
268         confirm_change_group ();
269       else
270         cancel_changes (0);
271       struct_equiv_make_checkpoint (p, info);
272     }
273 }
274
275 /* Restore state about current inputs / local registers / liveness
276    from P.  */
277 static void
278 struct_equiv_restore_checkpoint (struct struct_equiv_checkpoint *p,
279                                  struct equiv_info *info)
280 {
281   info->cur.ninsns = p->ninsns;
282   info->cur.x_start = p->x_start;
283   info->cur.y_start = p->y_start;
284   info->cur.input_count = p->input_count;
285   info->cur.input_valid = p->input_valid;
286   while (info->cur.local_count > p->local_count)
287     {
288       info->cur.local_count--;
289       info->cur.version--;
290       if (REGNO_REG_SET_P (info->x_local_live,
291                            REGNO (info->x_local[info->cur.local_count])))
292         {
293           assign_reg_reg_set (info->x_local_live,
294                               info->x_local[info->cur.local_count], 0);
295           assign_reg_reg_set (info->y_local_live,
296                               info->y_local[info->cur.local_count], 0);
297           info->cur.version--;
298         }
299     }
300   if (info->cur.version != p->version)
301     info->need_rerun = true;
302 }
303
304
305 /* Update register liveness to reflect that X is now life (if rvalue is
306    nonzero) or dead (if rvalue is zero) in INFO->x_block, and likewise Y
307    in INFO->y_block.  Return the number of registers the liveness of which
308    changed in each block (as a negative number if registers became dead).  */
309 static int
310 note_local_live (struct equiv_info *info, rtx x, rtx y, int rvalue)
311 {
312   int x_change = assign_reg_reg_set (info->x_local_live, x, rvalue);
313   int y_change = assign_reg_reg_set (info->y_local_live, y, rvalue);
314
315   gcc_assert (x_change == y_change);
316   if (y_change)
317     {
318       if (reload_completed)
319         {
320           unsigned x_regno ATTRIBUTE_UNUSED = REGNO (x);
321           unsigned y_regno = REGNO (y);
322           enum machine_mode x_mode = GET_MODE (x);
323
324           if (secondary_reload_class (0, REGNO_REG_CLASS (y_regno), x_mode, x)
325               != NO_REGS
326 #ifdef SECONDARY_MEMORY_NEEDED
327               || SECONDARY_MEMORY_NEEDED (REGNO_REG_CLASS (y_regno),
328                                           REGNO_REG_CLASS (x_regno), x_mode)
329 #endif
330               )
331           y_change *= IMPOSSIBLE_MOVE_FACTOR;
332         }
333       info->cur.input_count += y_change;
334       info->cur.version++;
335     }
336   return x_change;
337 }
338
339 /* Check if *XP is equivalent to Y.  Until an an unreconcilable difference is
340    found, use in-group changes with validate_change on *XP to make register
341    assignments agree.  It is the (not necessarily direct) callers
342    responsibility to verify / confirm / cancel these changes, as appropriate.
343    RVALUE indicates if the processed piece of rtl is used as a destination, in
344    which case we can't have different registers being an input.  Returns
345    nonzero if the two blocks have been identified as equivalent, zero otherwise.
346    RVALUE == 0: destination
347    RVALUE == 1: source
348    RVALUE == -1: source, ignore SET_DEST of SET / clobber.  */
349 bool
350 rtx_equiv_p (rtx *xp, rtx y, int rvalue, struct equiv_info *info)
351 {
352   rtx x = *xp;
353   enum rtx_code code;
354   int length;
355   const char *format;
356   int i;
357
358   if (!y || !x)
359     return x == y;
360   code = GET_CODE (y);
361   if (code != REG && x == y)
362     return true;
363   if (GET_CODE (x) != code
364       || GET_MODE (x) != GET_MODE (y))
365     return false;
366
367   /* ??? could extend to allow CONST_INT inputs.  */
368   switch (code)
369     {
370     case REG:
371       {
372         unsigned x_regno = REGNO (x);
373         unsigned y_regno = REGNO (y);
374         int x_common_live, y_common_live;
375
376         if (reload_completed
377             && (x_regno >= FIRST_PSEUDO_REGISTER
378                 || y_regno >= FIRST_PSEUDO_REGISTER))
379           {
380             /* We should only see this in REG_NOTEs.  */
381             gcc_assert (!info->live_update);
382             /* Returning false will cause us to remove the notes.  */
383             return false;
384           }
385 #ifdef STACK_REGS
386         /* After reg-stack, can only accept literal matches of stack regs.  */
387         if (info->mode & CLEANUP_POST_REGSTACK
388             && (IN_RANGE (x_regno, FIRST_STACK_REG, LAST_STACK_REG)
389                 || IN_RANGE (y_regno, FIRST_STACK_REG, LAST_STACK_REG)))
390           return x_regno == y_regno;
391 #endif
392
393         /* If the register is a locally live one in one block, the
394            corresponding one must be locally live in the other, too, and
395            match of identical regnos doesn't apply.  */
396         if (REGNO_REG_SET_P (info->x_local_live, x_regno))
397           {
398             if (!REGNO_REG_SET_P (info->y_local_live, y_regno))
399               return false;
400           }
401         else if (REGNO_REG_SET_P (info->y_local_live, y_regno))
402           return false;
403         else if (x_regno == y_regno)
404           {
405             if (!rvalue && info->cur.input_valid
406                 && (reg_overlap_mentioned_p (x, info->x_input)
407                     || reg_overlap_mentioned_p (x, info->y_input)))
408               return false;
409
410             /* Update liveness information.  */
411             if (info->live_update
412                 && assign_reg_reg_set (info->common_live, x, rvalue))
413               info->cur.version++;
414
415             return true;
416           }
417
418         x_common_live = REGNO_REG_SET_P (info->common_live, x_regno);
419         y_common_live = REGNO_REG_SET_P (info->common_live, y_regno);
420         if (x_common_live != y_common_live)
421           return false;
422         else if (x_common_live)
423           {
424             if (! rvalue || info->input_cost < 0 || no_new_pseudos)
425               return false;
426             /* If info->live_update is not set, we are processing notes.
427                We then allow a match with x_input / y_input found in a
428                previous pass.  */
429             if (info->live_update && !info->cur.input_valid)
430               {
431                 info->cur.input_valid = true;
432                 info->x_input = x;
433                 info->y_input = y;
434                 info->cur.input_count += optimize_size ? 2 : 1;
435                 if (info->input_reg
436                     && GET_MODE (info->input_reg) != GET_MODE (info->x_input))
437                   info->input_reg = NULL_RTX;
438                 if (!info->input_reg)
439                   info->input_reg = gen_reg_rtx (GET_MODE (info->x_input));
440               }
441             else if ((info->live_update
442                       ? ! info->cur.input_valid : ! info->x_input)
443                      || ! rtx_equal_p (x, info->x_input)
444                      || ! rtx_equal_p (y, info->y_input))
445               return false;
446             validate_change (info->cur.x_start, xp, info->input_reg, 1);
447           }
448         else
449           {
450             int x_nregs = (x_regno >= FIRST_PSEUDO_REGISTER
451                            ? 1 : hard_regno_nregs[x_regno][GET_MODE (x)]);
452             int y_nregs = (y_regno >= FIRST_PSEUDO_REGISTER
453                            ? 1 : hard_regno_nregs[y_regno][GET_MODE (y)]);
454             int size = GET_MODE_SIZE (GET_MODE (x));
455             enum machine_mode x_mode = GET_MODE (x);
456             unsigned x_regno_i, y_regno_i;
457             int x_nregs_i, y_nregs_i, size_i;
458             int local_count = info->cur.local_count;
459
460             /* This might be a register local to each block.  See if we have
461                it already registered.  */
462             for (i = local_count - 1; i >= 0; i--)
463               {
464                 x_regno_i = REGNO (info->x_local[i]);
465                 x_nregs_i = (x_regno_i >= FIRST_PSEUDO_REGISTER
466                              ? 1 : hard_regno_nregs[x_regno_i][GET_MODE (x)]);
467                 y_regno_i = REGNO (info->y_local[i]);
468                 y_nregs_i = (y_regno_i >= FIRST_PSEUDO_REGISTER
469                              ? 1 : hard_regno_nregs[y_regno_i][GET_MODE (y)]);
470                 size_i = GET_MODE_SIZE (GET_MODE (info->x_local[i]));
471
472                 /* If we have a new pair of registers that is wider than an
473                    old pair and enclosing it with matching offsets,
474                    remove the old pair.  If we find a matching, wider, old
475                    pair, use the old one.  If the width is the same, use the
476                    old one if the modes match, but the new if they don't.
477                    We don't want to get too fancy with subreg_regno_offset
478                    here, so we just test two straightforwad cases each.  */
479                 if (info->live_update
480                     && (x_mode != GET_MODE (info->x_local[i])
481                         ? size >= size_i : size > size_i))
482                   {
483                     /* If the new pair is fully enclosing a matching
484                        existing pair, remove the old one.  N.B. because
485                        we are removing one entry here, the check below
486                        if we have space for a new entry will succeed.  */
487                     if ((x_regno <= x_regno_i
488                          && x_regno + x_nregs >= x_regno_i + x_nregs_i
489                          && x_nregs == y_nregs && x_nregs_i == y_nregs_i
490                          && x_regno - x_regno_i == y_regno - y_regno_i)
491                         || (x_regno == x_regno_i && y_regno == y_regno_i
492                             && x_nregs >= x_nregs_i && y_nregs >= y_nregs_i))
493                       {
494                         info->cur.local_count = --local_count;
495                         info->x_local[i] = info->x_local[local_count];
496                         info->y_local[i] = info->y_local[local_count];
497                         continue;
498                       }
499                   }
500                 else
501                   {
502
503                     /* If the new pair is fully enclosed within a matching
504                        existing pair, succeed.  */
505                     if (x_regno >= x_regno_i
506                         && x_regno + x_nregs <= x_regno_i + x_nregs_i
507                         && x_nregs == y_nregs && x_nregs_i == y_nregs_i
508                         && x_regno - x_regno_i == y_regno - y_regno_i)
509                       break;
510                     if (x_regno == x_regno_i && y_regno == y_regno_i
511                         && x_nregs <= x_nregs_i && y_nregs <= y_nregs_i)
512                       break;
513                 }
514
515                 /* Any other overlap causes a match failure.  */
516                 if (x_regno + x_nregs > x_regno_i
517                     && x_regno_i + x_nregs_i > x_regno)
518                   return false;
519                 if (y_regno + y_nregs > y_regno_i
520                     && y_regno_i + y_nregs_i > y_regno)
521                   return false;
522               }
523             if (i < 0)
524               {
525                 /* Not found.  Create a new entry if possible.  */
526                 if (!info->live_update
527                     || info->cur.local_count >= STRUCT_EQUIV_MAX_LOCAL)
528                   return false;
529                 info->x_local[info->cur.local_count] = x;
530                 info->y_local[info->cur.local_count] = y;
531                 info->cur.local_count++;
532                 info->cur.version++;
533               }
534             note_local_live (info, x, y, rvalue);
535           }
536         return true;
537       }
538     case SET:
539       gcc_assert (rvalue < 0);
540       /* Ignore the destinations role as a destination.  Still, we have
541          to consider input registers embedded in the addresses of a MEM.
542          N.B., we process the rvalue aspect of STRICT_LOW_PART /
543          ZERO_EXTEND / SIGN_EXTEND along with their lvalue aspect.  */
544       if(!set_dest_addr_equiv_p (SET_DEST (x), SET_DEST (y), info))
545         return false;
546       /* Process source.  */
547       return rtx_equiv_p (&SET_SRC (x), SET_SRC (y), 1, info);
548     case PRE_MODIFY:
549       /* Process destination.  */
550       if (!rtx_equiv_p (&XEXP (x, 0), XEXP (y, 0), 0, info))
551         return false;
552       /* Process source.  */
553       return rtx_equiv_p (&XEXP (x, 1), XEXP (y, 1), 1, info);
554     case POST_MODIFY:
555       {
556         rtx x_dest0, x_dest1;
557
558         /* Process destination.  */
559         x_dest0 = XEXP (x, 0);
560         gcc_assert (REG_P (x_dest0));
561         if (!rtx_equiv_p (&XEXP (x, 0), XEXP (y, 0), 0, info))
562           return false;
563         x_dest1 = XEXP (x, 0);
564         /* validate_change might have changed the destination.  Put it back
565            so that we can do a valid source match.  */
566         XEXP (x, 0) = x_dest0;
567         if (!rtx_equiv_p (&XEXP (x, 1), XEXP (y, 1), 0, info))
568           return false;
569         gcc_assert (x_dest1 == XEXP (x, 0));
570         /* Process source.  */
571         return rtx_equiv_p (&XEXP (x, 1), XEXP (y, 1), 1, info);
572       if (!rtx_equiv_p (&XEXP(x, 0), XEXP (y, 0), 0, info))
573         return false;
574       /* Process both subexpressions as inputs.  */
575       break;
576       }
577     case CLOBBER:
578       gcc_assert (rvalue < 0);
579       return true;
580     /* Some special forms are also rvalues when they appear in lvalue
581        positions.  However, we must ont try to match a register after we
582        have already altered it with validate_change, consider the rvalue
583        aspect while we process the lvalue.  */
584     case STRICT_LOW_PART:
585     case ZERO_EXTEND:
586     case SIGN_EXTEND:
587       {
588         rtx x_inner, y_inner;
589         enum rtx_code code;
590         int change;
591
592         if (rvalue)
593           break;
594         x_inner = XEXP (x, 0);
595         y_inner = XEXP (y, 0);
596         if (GET_MODE (x_inner) != GET_MODE (y_inner))
597           return false;
598         code = GET_CODE (x_inner);
599         if (code != GET_CODE (y_inner))
600           return false;
601         /* The address of a MEM is an input that will be processed during
602            rvalue == -1 processing.  */
603         if (code == SUBREG)
604           {
605             if (SUBREG_BYTE (x_inner) != SUBREG_BYTE (y_inner))
606               return false;
607             x = x_inner;
608             x_inner = SUBREG_REG (x_inner);
609             y_inner = SUBREG_REG (y_inner);
610             if (GET_MODE (x_inner) != GET_MODE (y_inner))
611               return false;
612             code = GET_CODE (x_inner);
613             if (code != GET_CODE (y_inner))
614               return false;
615           }
616         if (code == MEM)
617           return true;
618         gcc_assert (code == REG);
619         if (! rtx_equiv_p (&XEXP (x, 0), y_inner, rvalue, info))
620           return false;
621         if (REGNO (x_inner) == REGNO (y_inner))
622           {
623             change = assign_reg_reg_set (info->common_live, x_inner, 1);
624             info->cur.version++;
625           }
626         else
627           change = note_local_live (info, x_inner, y_inner, 1);
628         gcc_assert (change);
629         return true;
630       }
631     /* The AUTO_INC / POST_MODIFY / PRE_MODIFY sets are modelled to take
632        place during input processing, however, that is benign, since they
633        are paired with reads.  */
634     case MEM:
635       return !rvalue || rtx_equiv_p (&XEXP (x, 0), XEXP (y, 0), rvalue, info);
636     case POST_INC: case POST_DEC: case PRE_INC: case PRE_DEC:
637       return (rtx_equiv_p (&XEXP (x, 0), XEXP (y, 0), 0, info)
638               && rtx_equiv_p (&XEXP (x, 0), XEXP (y, 0), 1, info));
639     case PARALLEL:
640       /* If this is a top-level PATTERN PARALLEL, we expect the caller to 
641          have handled the SET_DESTs.  A complex or vector PARALLEL can be
642          identified by having a mode.  */
643       gcc_assert (rvalue < 0 || GET_MODE (x) != VOIDmode);
644       break;
645     case LABEL_REF:
646       /* Check special tablejump match case.  */
647       if (XEXP (y, 0) == info->y_label)
648         return (XEXP (x, 0) == info->x_label);
649       /* We can't assume nonlocal labels have their following insns yet.  */
650       if (LABEL_REF_NONLOCAL_P (x) || LABEL_REF_NONLOCAL_P (y))
651         return XEXP (x, 0) == XEXP (y, 0);
652
653       /* Two label-refs are equivalent if they point at labels
654          in the same position in the instruction stream.  */
655       return (next_real_insn (XEXP (x, 0))
656               == next_real_insn (XEXP (y, 0)));
657     case SYMBOL_REF:
658       return XSTR (x, 0) == XSTR (y, 0);
659     /* Some rtl is guaranteed to be shared, or unique;  If we didn't match
660        EQ equality above, they aren't the same.  */
661     case CONST_INT:
662     case CODE_LABEL:
663       return false;
664     default:
665       break;
666     }
667
668   /* For commutative operations, the RTX match if the operands match in any
669      order.  */
670   if (targetm.commutative_p (x, UNKNOWN))
671     return ((rtx_equiv_p (&XEXP (x, 0), XEXP (y, 0), rvalue, info)
672              && rtx_equiv_p (&XEXP (x, 1), XEXP (y, 1), rvalue, info))
673             || (rtx_equiv_p (&XEXP (x, 0), XEXP (y, 1), rvalue, info)
674                 && rtx_equiv_p (&XEXP (x, 1), XEXP (y, 0), rvalue, info)));
675
676   /* Process subexpressions - this is similar to rtx_equal_p.  */
677   length = GET_RTX_LENGTH (code);
678   format = GET_RTX_FORMAT (code);
679
680   for (i = 0; i < length; ++i)
681     {
682       switch (format[i])
683         {
684         case 'w':
685           if (XWINT (x, i) != XWINT (y, i))
686             return false;
687           break;
688         case 'n':
689         case 'i':
690           if (XINT (x, i) != XINT (y, i))
691             return false;
692           break;
693         case 'V':
694         case 'E':
695           if (XVECLEN (x, i) != XVECLEN (y, i))
696             return false;
697           if (XVEC (x, i) != 0)
698             {
699               int j;
700               for (j = 0; j < XVECLEN (x, i); ++j)
701                 {
702                   if (! rtx_equiv_p (&XVECEXP (x, i, j), XVECEXP (y, i, j),
703                                      rvalue, info))
704                     return false;
705                 }
706             }
707           break;
708         case 'e':
709           if (! rtx_equiv_p (&XEXP (x, i), XEXP (y, i), rvalue, info))
710             return false;
711           break;
712         case 'S':
713         case 's':
714           if ((XSTR (x, i) || XSTR (y, i))
715               && (! XSTR (x, i) || ! XSTR (y, i)
716                   || strcmp (XSTR (x, i), XSTR (y, i))))
717             return false;
718           break;
719         case 'u':
720           /* These are just backpointers, so they don't matter.  */
721           break;
722         case '0':
723         case 't':
724           break;
725           /* It is believed that rtx's at this level will never
726              contain anything but integers and other rtx's,
727              except for within LABEL_REFs and SYMBOL_REFs.  */
728         default:
729           gcc_unreachable ();
730         }
731     }
732   return true;
733 }
734
735 /* Do only the rtx_equiv_p SET_DEST processing for SETs and CLOBBERs.
736    Since we are scanning backwards, this the first step in processing each
737    insn.  Return true for success.  */
738 static bool
739 set_dest_equiv_p (rtx x, rtx y, struct equiv_info *info)
740 {
741   if (!x || !y)
742     return x == y;
743   if (GET_CODE (x) != GET_CODE (y))
744     return false;
745   else if (GET_CODE (x) == SET || GET_CODE (x) == CLOBBER)
746     return rtx_equiv_p (&XEXP (x, 0), XEXP (y, 0), 0, info);
747   else if (GET_CODE (x) == PARALLEL)
748     {
749       int j;
750
751       if (XVECLEN (x, 0) != XVECLEN (y, 0))
752         return false;
753       for (j = 0; j < XVECLEN (x, 0); ++j)
754         {
755           rtx xe = XVECEXP (x, 0, j);
756           rtx ye = XVECEXP (y, 0, j);
757
758           if (GET_CODE (xe) != GET_CODE (ye))
759             return false;
760           if ((GET_CODE (xe) == SET || GET_CODE (xe) == CLOBBER)
761               && ! rtx_equiv_p (&XEXP (xe, 0), XEXP (ye, 0), 0, info))
762             return false;
763         }
764     }
765   return true;
766 }
767
768 /* Process MEMs in SET_DEST destinations.  We must not process this together
769    with REG SET_DESTs, but must do it separately, lest when we see
770    [(set (reg:SI foo) (bar))
771     (set (mem:SI (reg:SI foo) (baz)))]
772    struct_equiv_block_eq could get confused to assume that (reg:SI foo)
773    is not live before this instruction.  */
774 static bool
775 set_dest_addr_equiv_p (rtx x, rtx y, struct equiv_info *info)
776 {
777   enum rtx_code code = GET_CODE (x);
778   int length;
779   const char *format;
780   int i;
781
782   if (code != GET_CODE (y))
783     return false;
784   if (code == MEM)
785     return rtx_equiv_p (&XEXP (x, 0), XEXP (y, 0), 1, info);
786
787   /* Process subexpressions.  */
788   length = GET_RTX_LENGTH (code);
789   format = GET_RTX_FORMAT (code);
790
791   for (i = 0; i < length; ++i)
792     {
793       switch (format[i])
794         {
795         case 'V':
796         case 'E':
797           if (XVECLEN (x, i) != XVECLEN (y, i))
798             return false;
799           if (XVEC (x, i) != 0)
800             {
801               int j;
802               for (j = 0; j < XVECLEN (x, i); ++j)
803                 {
804                   if (! set_dest_addr_equiv_p (XVECEXP (x, i, j),
805                                                XVECEXP (y, i, j), info))
806                     return false;
807                 }
808             }
809           break;
810         case 'e':
811           if (! set_dest_addr_equiv_p (XEXP (x, i), XEXP (y, i), info))
812             return false;
813           break;
814         default:
815           break;
816         }
817     }
818   return true;
819 }
820
821 /* Check if the set of REG_DEAD notes attached to I1 and I2 allows us to
822    go ahead with merging I1 and I2, which otherwise look fine.
823    Inputs / local registers for the inputs of I1 and I2 have already been
824    set up.  */
825 static bool
826 death_notes_match_p (rtx i1 ATTRIBUTE_UNUSED, rtx i2 ATTRIBUTE_UNUSED,
827                      struct equiv_info *info ATTRIBUTE_UNUSED)
828 {
829 #ifdef STACK_REGS
830   /* If cross_jump_death_matters is not 0, the insn's mode
831      indicates whether or not the insn contains any stack-like regs.  */
832
833   if ((info->mode & CLEANUP_POST_REGSTACK) && stack_regs_mentioned (i1))
834     {
835       /* If register stack conversion has already been done, then
836          death notes must also be compared before it is certain that
837          the two instruction streams match.  */
838
839       rtx note;
840       HARD_REG_SET i1_regset, i2_regset;
841
842       CLEAR_HARD_REG_SET (i1_regset);
843       CLEAR_HARD_REG_SET (i2_regset);
844
845       for (note = REG_NOTES (i1); note; note = XEXP (note, 1))
846         if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0)))
847           SET_HARD_REG_BIT (i1_regset, REGNO (XEXP (note, 0)));
848
849       for (note = REG_NOTES (i2); note; note = XEXP (note, 1))
850         if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0)))
851           {
852             unsigned regno = REGNO (XEXP (note, 0));
853             int i;
854
855             for (i = info->cur.local_count - 1; i >= 0; i--)
856               if (regno == REGNO (info->y_local[i]))
857                 {
858                   regno = REGNO (info->x_local[i]);
859                   break;
860                 }
861             SET_HARD_REG_BIT (i2_regset, regno);
862           }
863
864       GO_IF_HARD_REG_EQUAL (i1_regset, i2_regset, done);
865
866       return false;
867
868     done:
869       ;
870     }
871 #endif
872   return true;
873 }
874
875 /* Return true if I1 and I2 are equivalent and thus can be crossjumped.  */
876
877 bool
878 insns_match_p (rtx i1, rtx i2, struct equiv_info *info)
879 {
880   int rvalue_change_start;
881   struct struct_equiv_checkpoint before_rvalue_change;
882
883   /* Verify that I1 and I2 are equivalent.  */
884   if (GET_CODE (i1) != GET_CODE (i2))
885     return false;
886
887   info->cur.x_start = i1;
888   info->cur.y_start = i2;
889
890   /* If this is a CALL_INSN, compare register usage information.
891      If we don't check this on stack register machines, the two
892      CALL_INSNs might be merged leaving reg-stack.c with mismatching
893      numbers of stack registers in the same basic block.
894      If we don't check this on machines with delay slots, a delay slot may
895      be filled that clobbers a parameter expected by the subroutine.
896
897      ??? We take the simple route for now and assume that if they're
898      equal, they were constructed identically.  */
899
900   if (CALL_P (i1))
901     {
902       if (SIBLING_CALL_P (i1) != SIBLING_CALL_P (i2)
903           || ! set_dest_equiv_p (PATTERN (i1), PATTERN (i2), info)
904           || ! set_dest_equiv_p (CALL_INSN_FUNCTION_USAGE (i1),
905                                  CALL_INSN_FUNCTION_USAGE (i2), info)
906           || ! rtx_equiv_p (&CALL_INSN_FUNCTION_USAGE (i1),
907                             CALL_INSN_FUNCTION_USAGE (i2), -1, info))
908         {
909           cancel_changes (0);
910           return false;
911         }
912     }
913   else if (INSN_P (i1))
914     {
915       if (! set_dest_equiv_p (PATTERN (i1), PATTERN (i2), info))
916         {
917           cancel_changes (0);
918           return false;
919         }
920     }
921   rvalue_change_start = num_validated_changes ();
922   struct_equiv_make_checkpoint (&before_rvalue_change, info);
923   /* Check death_notes_match_p *after* the inputs have been processed,
924      so that local inputs will already have been set up.  */
925   if (! INSN_P (i1)
926       || (!bitmap_bit_p (info->equiv_used, info->cur.ninsns)
927           && rtx_equiv_p (&PATTERN (i1), PATTERN (i2), -1, info)
928           && death_notes_match_p (i1, i2, info)
929           && verify_changes (0)))
930     return true;
931
932   /* Do not do EQUIV substitution after reload.  First, we're undoing the
933      work of reload_cse.  Second, we may be undoing the work of the post-
934      reload splitting pass.  */
935   /* ??? Possibly add a new phase switch variable that can be used by
936      targets to disallow the troublesome insns after splitting.  */
937   if (!reload_completed)
938     {
939       rtx equiv1, equiv2;
940
941       cancel_changes (rvalue_change_start);
942       struct_equiv_restore_checkpoint (&before_rvalue_change, info);
943
944       /* The following code helps take care of G++ cleanups.  */
945       equiv1 = find_reg_equal_equiv_note (i1);
946       equiv2 = find_reg_equal_equiv_note (i2);
947       if (equiv1 && equiv2
948           /* If the equivalences are not to a constant, they may
949              reference pseudos that no longer exist, so we can't
950              use them.  */
951           && (! reload_completed
952               || (CONSTANT_P (XEXP (equiv1, 0))
953                   && rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))))
954         {
955           rtx s1 = single_set (i1);
956           rtx s2 = single_set (i2);
957
958           if (s1 != 0 && s2 != 0)
959             {
960               validate_change (i1, &SET_SRC (s1), XEXP (equiv1, 0), 1);
961               validate_change (i2, &SET_SRC (s2), XEXP (equiv2, 0), 1);
962               /* Only inspecting the new SET_SRC is not good enough,
963                  because there may also be bare USEs in a single_set
964                  PARALLEL.  */
965               if (rtx_equiv_p (&PATTERN (i1), PATTERN (i2), -1, info)
966                   && death_notes_match_p (i1, i2, info)
967                   && verify_changes (0))
968                 {
969                   /* Mark this insn so that we'll use the equivalence in
970                      all subsequent passes.  */
971                   bitmap_set_bit (info->equiv_used, info->cur.ninsns);
972                   return true;
973                 }
974             }
975         }
976     }
977
978   cancel_changes (0);
979   return false;
980 }
981
982 /* Set up mode and register information in INFO.  Return true for success.  */
983 bool
984 struct_equiv_init (int mode, struct equiv_info *info)
985 {
986   if ((info->x_block->flags | info->y_block->flags) & BB_DIRTY)
987     update_life_info_in_dirty_blocks (UPDATE_LIFE_GLOBAL_RM_NOTES,
988                                       (PROP_DEATH_NOTES
989                                        | ((mode & CLEANUP_POST_REGSTACK)
990                                           ? PROP_POST_REGSTACK : 0)));
991   if (!REG_SET_EQUAL_P (info->x_block->il.rtl->global_live_at_end,
992                         info->y_block->il.rtl->global_live_at_end))
993     {
994 #ifdef STACK_REGS
995       unsigned rn;
996
997       if (!(mode & CLEANUP_POST_REGSTACK))
998         return false;
999       /* After reg-stack.  Remove bogus live info about stack regs.  N.B.
1000          these regs are not necessarily all dead - we swap random bogosity
1001          against constant bogosity.  However, clearing these bits at
1002          least makes the regsets comparable.  */
1003       for (rn = FIRST_STACK_REG; rn <= LAST_STACK_REG; rn++)
1004         {
1005           CLEAR_REGNO_REG_SET (info->x_block->il.rtl->global_live_at_end, rn);
1006           CLEAR_REGNO_REG_SET (info->y_block->il.rtl->global_live_at_end, rn);
1007         }
1008       if (!REG_SET_EQUAL_P (info->x_block->il.rtl->global_live_at_end,
1009                             info->y_block->il.rtl->global_live_at_end))
1010 #endif
1011         return false;
1012     }
1013   info->mode = mode;
1014   if (mode & STRUCT_EQUIV_START)
1015     {
1016       info->x_input = info->y_input = info->input_reg = NULL_RTX;
1017       info->equiv_used = ALLOC_REG_SET (&reg_obstack);
1018       info->check_input_conflict = false;
1019     }
1020   info->had_input_conflict = false;
1021   info->cur.ninsns = info->cur.version = 0;
1022   info->cur.local_count = info->cur.input_count = 0;
1023   info->cur.x_start = info->cur.y_start = NULL_RTX;
1024   info->x_label = info->y_label = NULL_RTX;
1025   info->need_rerun = false;
1026   info->live_update = true;
1027   info->cur.input_valid = false;
1028   info->common_live = ALLOC_REG_SET (&reg_obstack);
1029   info->x_local_live = ALLOC_REG_SET (&reg_obstack);
1030   info->y_local_live = ALLOC_REG_SET (&reg_obstack);
1031   COPY_REG_SET (info->common_live, info->x_block->il.rtl->global_live_at_end);
1032   struct_equiv_make_checkpoint (&info->best_match, info);
1033   return true;
1034 }
1035
1036 /* Insns XI and YI have been matched.  Merge memory attributes and reg
1037    notes.  */
1038 static void
1039 struct_equiv_merge (rtx xi, rtx yi, struct equiv_info *info)
1040 {
1041   rtx equiv1, equiv2;
1042
1043   merge_memattrs (xi, yi);
1044
1045   /* If the merged insns have different REG_EQUAL notes, then
1046      remove them.  */
1047   info->live_update = false;
1048   equiv1 = find_reg_equal_equiv_note (xi);
1049   equiv2 = find_reg_equal_equiv_note (yi);
1050   if (equiv1 && !equiv2)
1051     remove_note (xi, equiv1);
1052   else if (!equiv1 && equiv2)
1053     remove_note (yi, equiv2);
1054   else if (equiv1 && equiv2
1055          && !rtx_equiv_p (&XEXP (equiv1, 0), XEXP (equiv2, 0),
1056                            1, info))
1057     {
1058       remove_note (xi, equiv1);
1059       remove_note (yi, equiv2);
1060     }
1061   info->live_update = true;
1062 }
1063
1064 /* Return number of matched insns.
1065    This function must be called up to three times for a successful cross-jump
1066    match:
1067    first to find out which instructions do match.  While trying to match
1068    another instruction that doesn't match, we destroy information in info
1069    about the actual inputs.  So if there have been any before the last
1070    match attempt, we need to call this function again to recompute the
1071    actual inputs up to the actual start of the matching sequence.
1072    When we are then satisfied that the cross-jump is worthwhile, we
1073    call this function a third time to make any changes needed to make the
1074    sequences match: apply equivalences, remove non-matching
1075    notes and merge memory attributes.  */
1076 int
1077 struct_equiv_block_eq (int mode, struct equiv_info *info)
1078 {
1079   rtx x_stop, y_stop;
1080   rtx xi, yi;
1081   int i;
1082
1083   if (mode & STRUCT_EQUIV_START)
1084     {
1085       x_stop = BB_HEAD (info->x_block);
1086       y_stop = BB_HEAD (info->y_block);
1087       if (!x_stop || !y_stop)
1088         return 0;
1089     }
1090   else
1091     {
1092       x_stop = info->cur.x_start;
1093       y_stop = info->cur.y_start;
1094     }
1095   if (!struct_equiv_init (mode, info))
1096     gcc_unreachable ();
1097
1098   /* Skip simple jumps at the end of the blocks.  Complex jumps still
1099      need to be compared for equivalence, which we'll do below.  */
1100
1101   xi = BB_END (info->x_block);
1102   if (onlyjump_p (xi)
1103       || (returnjump_p (xi) && !side_effects_p (PATTERN (xi))))
1104     {
1105       info->cur.x_start = xi;
1106       xi = PREV_INSN (xi);
1107     }
1108
1109   yi = BB_END (info->y_block);
1110   if (onlyjump_p (yi)
1111       || (returnjump_p (yi) && !side_effects_p (PATTERN (yi))))
1112     {
1113       info->cur.y_start = yi;
1114       /* Count everything except for unconditional jump as insn.  */
1115       /* ??? Is it right to count unconditional jumps with a clobber?
1116          Should we count conditional returns?  */
1117       if (!simplejump_p (yi) && !returnjump_p (yi) && info->cur.x_start)
1118         info->cur.ninsns++;
1119       yi = PREV_INSN (yi);
1120     }
1121
1122   if (mode & STRUCT_EQUIV_MATCH_JUMPS)
1123     {
1124       /* The caller is expected to have comapred the jumps already, but we
1125          need to match them again to get any local registers and inputs.  */
1126       gcc_assert (!info->cur.x_start == !info->cur.y_start);
1127       if (info->cur.x_start)
1128         {
1129           if (any_condjump_p (info->cur.x_start)
1130               ? !condjump_equiv_p (info, false)
1131               : !insns_match_p (info->cur.x_start, info->cur.y_start, info))
1132             gcc_unreachable ();
1133         }
1134       else if (any_condjump_p (xi) && any_condjump_p (yi))
1135         {
1136           info->cur.x_start = xi;
1137           info->cur.y_start = yi;
1138           xi = PREV_INSN (xi);
1139           yi = PREV_INSN (yi);
1140           info->cur.ninsns++;
1141           if (!condjump_equiv_p (info, false))
1142             gcc_unreachable ();
1143         }
1144       if (info->cur.x_start && info->mode & STRUCT_EQUIV_FINAL)
1145         struct_equiv_merge (info->cur.x_start, info->cur.y_start, info);
1146     }
1147
1148   struct_equiv_improve_checkpoint (&info->best_match, info);
1149   info->x_end = xi;
1150   info->y_end = yi;
1151   if (info->cur.x_start != x_stop)
1152     for (;;)
1153       {
1154         /* Ignore notes.  */
1155         while (!INSN_P (xi) && xi != x_stop)
1156           xi = PREV_INSN (xi);
1157
1158         while (!INSN_P (yi) && yi != y_stop)
1159           yi = PREV_INSN (yi);
1160
1161         if (!insns_match_p (xi, yi, info))
1162           break;
1163         if (INSN_P (xi))
1164           {
1165             if (info->mode & STRUCT_EQUIV_FINAL)
1166               struct_equiv_merge (xi, yi, info);
1167             info->cur.ninsns++;
1168             struct_equiv_improve_checkpoint (&info->best_match, info);
1169           }
1170         if (xi == x_stop || yi == y_stop)
1171           {
1172             /* If we reached the start of at least one of the blocks, but
1173                best_match hasn't been advanced back to the first valid insn
1174                yet, represent the increased benefit of completing the block
1175                as an increased instruction count.  */
1176             if (info->best_match.x_start != info->cur.x_start
1177                 && (xi == BB_HEAD (info->x_block)
1178                     || yi == BB_HEAD (info->y_block)))
1179               {
1180                 info->cur.ninsns++;
1181                 struct_equiv_improve_checkpoint (&info->best_match, info);
1182                 info->cur.ninsns--;
1183                 if (info->best_match.ninsns > info->cur.ninsns)
1184                   info->best_match.ninsns = info->cur.ninsns;
1185               }
1186             break;
1187           }
1188         xi = PREV_INSN (xi);
1189         yi = PREV_INSN (yi);
1190       }
1191
1192   /* If we failed to match an insn, but had some changes registered from
1193      trying to make the insns match, we need to cancel these changes now.  */
1194   cancel_changes (0);
1195   /* Restore to best_match to get the sequence with the best known-so-far
1196      cost-benefit difference.  */
1197   struct_equiv_restore_checkpoint (&info->best_match, info);
1198
1199   /* Include preceding notes and labels in the cross-jump / if-conversion.
1200      One, this may bring us to the head of the blocks.
1201      Two, it keeps line number notes as matched as may be.  */
1202   if (info->cur.ninsns)
1203     {
1204       xi = info->cur.x_start;
1205       yi = info->cur.y_start;
1206       while (xi != x_stop && !INSN_P (PREV_INSN (xi)))
1207         xi = PREV_INSN (xi);
1208
1209       while (yi != y_stop && !INSN_P (PREV_INSN (yi)))
1210         yi = PREV_INSN (yi);
1211
1212       info->cur.x_start = xi;
1213       info->cur.y_start = yi;
1214     }
1215
1216   if (!info->cur.input_valid)
1217     info->x_input = info->y_input = info->input_reg = NULL_RTX;
1218   if (!info->need_rerun)
1219     {
1220       find_dying_inputs (info);
1221       if (info->mode & STRUCT_EQUIV_FINAL)
1222         {
1223           if (info->check_input_conflict && ! resolve_input_conflict (info))
1224             gcc_unreachable ();
1225         }
1226       else
1227         {
1228           bool input_conflict = info->had_input_conflict;
1229
1230           if (!input_conflict
1231               && info->dying_inputs > 1
1232               && bitmap_intersect_p (info->x_local_live, info->y_local_live))
1233             {
1234               regset_head clobbered_regs;
1235
1236               INIT_REG_SET (&clobbered_regs);
1237               for (i = 0; i < info->cur.local_count; i++)
1238                 {
1239                   if (assign_reg_reg_set (&clobbered_regs, info->y_local[i], 0))
1240                     {
1241                       input_conflict = true;
1242                       break;
1243                     }
1244                   assign_reg_reg_set (&clobbered_regs, info->x_local[i], 1);
1245                 }
1246               CLEAR_REG_SET (&clobbered_regs);
1247             }
1248           if (input_conflict && !info->check_input_conflict)
1249             info->need_rerun = true;
1250           info->check_input_conflict = input_conflict;
1251         }
1252     }
1253
1254   if (info->mode & STRUCT_EQUIV_NEED_FULL_BLOCK
1255       && (info->cur.x_start != x_stop || info->cur.y_start != y_stop))
1256     return 0;
1257   return info->cur.ninsns;
1258 }
1259
1260 /* For each local register, set info->local_rvalue to true iff the register
1261    is a dying input.  Store the total number of these in info->dying_inputs.  */
1262 static void
1263 find_dying_inputs (struct equiv_info *info)
1264 {
1265   int i;
1266
1267   info->dying_inputs = 0;
1268   for (i = info->cur.local_count-1; i >=0; i--)
1269     {
1270       rtx x = info->x_local[i];
1271       unsigned regno = REGNO (x);
1272       int nregs = (regno >= FIRST_PSEUDO_REGISTER
1273                    ? 1 : hard_regno_nregs[regno][GET_MODE (x)]);
1274
1275       for (info->local_rvalue[i] = false; nregs >= 0; regno++, --nregs)
1276         if (REGNO_REG_SET_P (info->x_local_live, regno))
1277           {
1278             info->dying_inputs++;
1279             info->local_rvalue[i] = true;
1280             break;
1281           }
1282     }
1283 }
1284
1285 /* For each local register that is a dying input, y_local[i] will be
1286    copied to x_local[i].  We'll do this in ascending order.  Try to
1287    re-order the locals to avoid conflicts like r3 = r2; r4 = r3; .
1288    Return true iff the re-ordering is successful, or not necessary.  */
1289 static bool
1290 resolve_input_conflict (struct equiv_info *info)
1291 {
1292   int i, j, end;
1293   int nswaps = 0;
1294   rtx save_x_local[STRUCT_EQUIV_MAX_LOCAL];
1295   rtx save_y_local[STRUCT_EQUIV_MAX_LOCAL];
1296
1297   find_dying_inputs (info);
1298   if (info->dying_inputs <= 1)
1299     return true;
1300   memcpy (save_x_local, info->x_local, sizeof save_x_local);
1301   memcpy (save_y_local, info->y_local, sizeof save_y_local);
1302   end = info->cur.local_count - 1;
1303   for (i = 0; i <= end; i++)
1304     {
1305       /* Cycle detection with regsets is expensive, so we just check that
1306          we don't exceed the maximum number of swaps needed in the acyclic
1307          case.  */
1308       int max_swaps = end - i;
1309
1310       /* Check if x_local[i] will be clobbered.  */
1311       if (!info->local_rvalue[i])
1312         continue;
1313       /* Check if any later value needs to be copied earlier.  */
1314       for (j = i + 1; j <= end; j++)
1315         {
1316           rtx tmp;
1317
1318           if (!info->local_rvalue[j])
1319             continue;
1320           if (!reg_overlap_mentioned_p (info->x_local[i], info->y_local[j]))
1321             continue;
1322           if (--max_swaps < 0)
1323             {
1324               memcpy (info->x_local, save_x_local, sizeof save_x_local);
1325               memcpy (info->y_local, save_y_local, sizeof save_y_local);
1326               return false;
1327             }
1328           nswaps++;
1329           tmp = info->x_local[i];
1330           info->x_local[i] = info->x_local[j];
1331           info->x_local[j] = tmp;
1332           tmp = info->y_local[i];
1333           info->y_local[i] = info->y_local[j];
1334           info->y_local[j] = tmp;
1335           j = i;
1336         }
1337     }
1338   info->had_input_conflict = true;
1339   if (dump_file && nswaps)
1340     fprintf (dump_file, "Resolved input conflict, %d %s.\n",
1341              nswaps, nswaps == 1 ? "swap" : "swaps");
1342   return true;
1343 }