Merge branch 'vendor/GCC47'
[dragonfly.git] / contrib / gcc-4.7 / gcc / recog.c
1 /* Subroutines used by or related to instruction recognition.
2    Copyright (C) 1987, 1988, 1991, 1992, 1993, 1994, 1995, 1996, 1997, 1998
3    1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
4    Free Software Foundation, Inc.
5
6 This file is part of GCC.
7
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
11 version.
12
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
16 for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3.  If not see
20 <http://www.gnu.org/licenses/>.  */
21
22
23 #include "config.h"
24 #include "system.h"
25 #include "coretypes.h"
26 #include "tm.h"
27 #include "rtl-error.h"
28 #include "tm_p.h"
29 #include "insn-config.h"
30 #include "insn-attr.h"
31 #include "hard-reg-set.h"
32 #include "recog.h"
33 #include "regs.h"
34 #include "addresses.h"
35 #include "expr.h"
36 #include "function.h"
37 #include "flags.h"
38 #include "basic-block.h"
39 #include "output.h"
40 #include "reload.h"
41 #include "target.h"
42 #include "timevar.h"
43 #include "tree-pass.h"
44 #include "df.h"
45
46 #ifndef STACK_PUSH_CODE
47 #ifdef STACK_GROWS_DOWNWARD
48 #define STACK_PUSH_CODE PRE_DEC
49 #else
50 #define STACK_PUSH_CODE PRE_INC
51 #endif
52 #endif
53
54 #ifndef STACK_POP_CODE
55 #ifdef STACK_GROWS_DOWNWARD
56 #define STACK_POP_CODE POST_INC
57 #else
58 #define STACK_POP_CODE POST_DEC
59 #endif
60 #endif
61
62 #ifndef HAVE_ATTR_enabled
63 static inline bool
64 get_attr_enabled (rtx insn ATTRIBUTE_UNUSED)
65 {
66   return true;
67 }
68 #endif
69
70 static void validate_replace_rtx_1 (rtx *, rtx, rtx, rtx, bool);
71 static void validate_replace_src_1 (rtx *, void *);
72 static rtx split_insn (rtx);
73
74 /* Nonzero means allow operands to be volatile.
75    This should be 0 if you are generating rtl, such as if you are calling
76    the functions in optabs.c and expmed.c (most of the time).
77    This should be 1 if all valid insns need to be recognized,
78    such as in reginfo.c and final.c and reload.c.
79
80    init_recog and init_recog_no_volatile are responsible for setting this.  */
81
82 int volatile_ok;
83
84 struct recog_data recog_data;
85
86 /* Contains a vector of operand_alternative structures for every operand.
87    Set up by preprocess_constraints.  */
88 struct operand_alternative recog_op_alt[MAX_RECOG_OPERANDS][MAX_RECOG_ALTERNATIVES];
89
90 /* On return from `constrain_operands', indicate which alternative
91    was satisfied.  */
92
93 int which_alternative;
94
95 /* Nonzero after end of reload pass.
96    Set to 1 or 0 by toplev.c.
97    Controls the significance of (SUBREG (MEM)).  */
98
99 int reload_completed;
100
101 /* Nonzero after thread_prologue_and_epilogue_insns has run.  */
102 int epilogue_completed;
103
104 /* Initialize data used by the function `recog'.
105    This must be called once in the compilation of a function
106    before any insn recognition may be done in the function.  */
107
108 void
109 init_recog_no_volatile (void)
110 {
111   volatile_ok = 0;
112 }
113
114 void
115 init_recog (void)
116 {
117   volatile_ok = 1;
118 }
119
120 \f
121 /* Return true if labels in asm operands BODY are LABEL_REFs.  */
122
123 static bool
124 asm_labels_ok (rtx body)
125 {
126   rtx asmop;
127   int i;
128
129   asmop = extract_asm_operands (body);
130   if (asmop == NULL_RTX)
131     return true;
132
133   for (i = 0; i < ASM_OPERANDS_LABEL_LENGTH (asmop); i++)
134     if (GET_CODE (ASM_OPERANDS_LABEL (asmop, i)) != LABEL_REF)
135       return false;
136
137   return true;
138 }
139
140 /* Check that X is an insn-body for an `asm' with operands
141    and that the operands mentioned in it are legitimate.  */
142
143 int
144 check_asm_operands (rtx x)
145 {
146   int noperands;
147   rtx *operands;
148   const char **constraints;
149   int i;
150
151   if (!asm_labels_ok (x))
152     return 0;
153
154   /* Post-reload, be more strict with things.  */
155   if (reload_completed)
156     {
157       /* ??? Doh!  We've not got the wrapping insn.  Cook one up.  */
158       extract_insn (make_insn_raw (x));
159       constrain_operands (1);
160       return which_alternative >= 0;
161     }
162
163   noperands = asm_noperands (x);
164   if (noperands < 0)
165     return 0;
166   if (noperands == 0)
167     return 1;
168
169   operands = XALLOCAVEC (rtx, noperands);
170   constraints = XALLOCAVEC (const char *, noperands);
171
172   decode_asm_operands (x, operands, NULL, constraints, NULL, NULL);
173
174   for (i = 0; i < noperands; i++)
175     {
176       const char *c = constraints[i];
177       if (c[0] == '%')
178         c++;
179       if (! asm_operand_ok (operands[i], c, constraints))
180         return 0;
181     }
182
183   return 1;
184 }
185 \f
186 /* Static data for the next two routines.  */
187
188 typedef struct change_t
189 {
190   rtx object;
191   int old_code;
192   rtx *loc;
193   rtx old;
194   bool unshare;
195 } change_t;
196
197 static change_t *changes;
198 static int changes_allocated;
199
200 static int num_changes = 0;
201
202 /* Validate a proposed change to OBJECT.  LOC is the location in the rtl
203    at which NEW_RTX will be placed.  If OBJECT is zero, no validation is done,
204    the change is simply made.
205
206    Two types of objects are supported:  If OBJECT is a MEM, memory_address_p
207    will be called with the address and mode as parameters.  If OBJECT is
208    an INSN, CALL_INSN, or JUMP_INSN, the insn will be re-recognized with
209    the change in place.
210
211    IN_GROUP is nonzero if this is part of a group of changes that must be
212    performed as a group.  In that case, the changes will be stored.  The
213    function `apply_change_group' will validate and apply the changes.
214
215    If IN_GROUP is zero, this is a single change.  Try to recognize the insn
216    or validate the memory reference with the change applied.  If the result
217    is not valid for the machine, suppress the change and return zero.
218    Otherwise, perform the change and return 1.  */
219
220 static bool
221 validate_change_1 (rtx object, rtx *loc, rtx new_rtx, bool in_group, bool unshare)
222 {
223   rtx old = *loc;
224
225   if (old == new_rtx || rtx_equal_p (old, new_rtx))
226     return 1;
227
228   gcc_assert (in_group != 0 || num_changes == 0);
229
230   *loc = new_rtx;
231
232   /* Save the information describing this change.  */
233   if (num_changes >= changes_allocated)
234     {
235       if (changes_allocated == 0)
236         /* This value allows for repeated substitutions inside complex
237            indexed addresses, or changes in up to 5 insns.  */
238         changes_allocated = MAX_RECOG_OPERANDS * 5;
239       else
240         changes_allocated *= 2;
241
242       changes = XRESIZEVEC (change_t, changes, changes_allocated);
243     }
244
245   changes[num_changes].object = object;
246   changes[num_changes].loc = loc;
247   changes[num_changes].old = old;
248   changes[num_changes].unshare = unshare;
249
250   if (object && !MEM_P (object))
251     {
252       /* Set INSN_CODE to force rerecognition of insn.  Save old code in
253          case invalid.  */
254       changes[num_changes].old_code = INSN_CODE (object);
255       INSN_CODE (object) = -1;
256     }
257
258   num_changes++;
259
260   /* If we are making a group of changes, return 1.  Otherwise, validate the
261      change group we made.  */
262
263   if (in_group)
264     return 1;
265   else
266     return apply_change_group ();
267 }
268
269 /* Wrapper for validate_change_1 without the UNSHARE argument defaulting
270    UNSHARE to false.  */
271
272 bool
273 validate_change (rtx object, rtx *loc, rtx new_rtx, bool in_group)
274 {
275   return validate_change_1 (object, loc, new_rtx, in_group, false);
276 }
277
278 /* Wrapper for validate_change_1 without the UNSHARE argument defaulting
279    UNSHARE to true.  */
280
281 bool
282 validate_unshare_change (rtx object, rtx *loc, rtx new_rtx, bool in_group)
283 {
284   return validate_change_1 (object, loc, new_rtx, in_group, true);
285 }
286
287
288 /* Keep X canonicalized if some changes have made it non-canonical; only
289    modifies the operands of X, not (for example) its code.  Simplifications
290    are not the job of this routine.
291
292    Return true if anything was changed.  */
293 bool
294 canonicalize_change_group (rtx insn, rtx x)
295 {
296   if (COMMUTATIVE_P (x)
297       && swap_commutative_operands_p (XEXP (x, 0), XEXP (x, 1)))
298     {
299       /* Oops, the caller has made X no longer canonical.
300          Let's redo the changes in the correct order.  */
301       rtx tem = XEXP (x, 0);
302       validate_unshare_change (insn, &XEXP (x, 0), XEXP (x, 1), 1);
303       validate_unshare_change (insn, &XEXP (x, 1), tem, 1);
304       return true;
305     }
306   else
307     return false;
308 }
309
310
311 /* This subroutine of apply_change_group verifies whether the changes to INSN
312    were valid; i.e. whether INSN can still be recognized.  */
313
314 int
315 insn_invalid_p (rtx insn)
316 {
317   rtx pat = PATTERN (insn);
318   int num_clobbers = 0;
319   /* If we are before reload and the pattern is a SET, see if we can add
320      clobbers.  */
321   int icode = recog (pat, insn,
322                      (GET_CODE (pat) == SET
323                       && ! reload_completed && ! reload_in_progress)
324                      ? &num_clobbers : 0);
325   int is_asm = icode < 0 && asm_noperands (PATTERN (insn)) >= 0;
326
327
328   /* If this is an asm and the operand aren't legal, then fail.  Likewise if
329      this is not an asm and the insn wasn't recognized.  */
330   if ((is_asm && ! check_asm_operands (PATTERN (insn)))
331       || (!is_asm && icode < 0))
332     return 1;
333
334   /* If we have to add CLOBBERs, fail if we have to add ones that reference
335      hard registers since our callers can't know if they are live or not.
336      Otherwise, add them.  */
337   if (num_clobbers > 0)
338     {
339       rtx newpat;
340
341       if (added_clobbers_hard_reg_p (icode))
342         return 1;
343
344       newpat = gen_rtx_PARALLEL (VOIDmode, rtvec_alloc (num_clobbers + 1));
345       XVECEXP (newpat, 0, 0) = pat;
346       add_clobbers (newpat, icode);
347       PATTERN (insn) = pat = newpat;
348     }
349
350   /* After reload, verify that all constraints are satisfied.  */
351   if (reload_completed)
352     {
353       extract_insn (insn);
354
355       if (! constrain_operands (1))
356         return 1;
357     }
358
359   INSN_CODE (insn) = icode;
360   return 0;
361 }
362
363 /* Return number of changes made and not validated yet.  */
364 int
365 num_changes_pending (void)
366 {
367   return num_changes;
368 }
369
370 /* Tentatively apply the changes numbered NUM and up.
371    Return 1 if all changes are valid, zero otherwise.  */
372
373 int
374 verify_changes (int num)
375 {
376   int i;
377   rtx last_validated = NULL_RTX;
378
379   /* The changes have been applied and all INSN_CODEs have been reset to force
380      rerecognition.
381
382      The changes are valid if we aren't given an object, or if we are
383      given a MEM and it still is a valid address, or if this is in insn
384      and it is recognized.  In the latter case, if reload has completed,
385      we also require that the operands meet the constraints for
386      the insn.  */
387
388   for (i = num; i < num_changes; i++)
389     {
390       rtx object = changes[i].object;
391
392       /* If there is no object to test or if it is the same as the one we
393          already tested, ignore it.  */
394       if (object == 0 || object == last_validated)
395         continue;
396
397       if (MEM_P (object))
398         {
399           if (! memory_address_addr_space_p (GET_MODE (object),
400                                              XEXP (object, 0),
401                                              MEM_ADDR_SPACE (object)))
402             break;
403         }
404       else if (REG_P (changes[i].old)
405                && asm_noperands (PATTERN (object)) > 0
406                && REG_EXPR (changes[i].old) != NULL_TREE
407                && DECL_ASSEMBLER_NAME_SET_P (REG_EXPR (changes[i].old))
408                && DECL_REGISTER (REG_EXPR (changes[i].old)))
409         {
410           /* Don't allow changes of hard register operands to inline
411              assemblies if they have been defined as register asm ("x").  */
412           break;
413         }
414       else if (DEBUG_INSN_P (object))
415         continue;
416       else if (insn_invalid_p (object))
417         {
418           rtx pat = PATTERN (object);
419
420           /* Perhaps we couldn't recognize the insn because there were
421              extra CLOBBERs at the end.  If so, try to re-recognize
422              without the last CLOBBER (later iterations will cause each of
423              them to be eliminated, in turn).  But don't do this if we
424              have an ASM_OPERAND.  */
425           if (GET_CODE (pat) == PARALLEL
426               && GET_CODE (XVECEXP (pat, 0, XVECLEN (pat, 0) - 1)) == CLOBBER
427               && asm_noperands (PATTERN (object)) < 0)
428             {
429               rtx newpat;
430
431               if (XVECLEN (pat, 0) == 2)
432                 newpat = XVECEXP (pat, 0, 0);
433               else
434                 {
435                   int j;
436
437                   newpat
438                     = gen_rtx_PARALLEL (VOIDmode,
439                                         rtvec_alloc (XVECLEN (pat, 0) - 1));
440                   for (j = 0; j < XVECLEN (newpat, 0); j++)
441                     XVECEXP (newpat, 0, j) = XVECEXP (pat, 0, j);
442                 }
443
444               /* Add a new change to this group to replace the pattern
445                  with this new pattern.  Then consider this change
446                  as having succeeded.  The change we added will
447                  cause the entire call to fail if things remain invalid.
448
449                  Note that this can lose if a later change than the one
450                  we are processing specified &XVECEXP (PATTERN (object), 0, X)
451                  but this shouldn't occur.  */
452
453               validate_change (object, &PATTERN (object), newpat, 1);
454               continue;
455             }
456           else if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER
457                    || GET_CODE (pat) == VAR_LOCATION)
458             /* If this insn is a CLOBBER or USE, it is always valid, but is
459                never recognized.  */
460             continue;
461           else
462             break;
463         }
464       last_validated = object;
465     }
466
467   return (i == num_changes);
468 }
469
470 /* A group of changes has previously been issued with validate_change
471    and verified with verify_changes.  Call df_insn_rescan for each of
472    the insn changed and clear num_changes.  */
473
474 void
475 confirm_change_group (void)
476 {
477   int i;
478   rtx last_object = NULL;
479
480   for (i = 0; i < num_changes; i++)
481     {
482       rtx object = changes[i].object;
483
484       if (changes[i].unshare)
485         *changes[i].loc = copy_rtx (*changes[i].loc);
486
487       /* Avoid unnecessary rescanning when multiple changes to same instruction
488          are made.  */
489       if (object)
490         {
491           if (object != last_object && last_object && INSN_P (last_object))
492             df_insn_rescan (last_object);
493           last_object = object;
494         }
495     }
496
497   if (last_object && INSN_P (last_object))
498     df_insn_rescan (last_object);
499   num_changes = 0;
500 }
501
502 /* Apply a group of changes previously issued with `validate_change'.
503    If all changes are valid, call confirm_change_group and return 1,
504    otherwise, call cancel_changes and return 0.  */
505
506 int
507 apply_change_group (void)
508 {
509   if (verify_changes (0))
510     {
511       confirm_change_group ();
512       return 1;
513     }
514   else
515     {
516       cancel_changes (0);
517       return 0;
518     }
519 }
520
521
522 /* Return the number of changes so far in the current group.  */
523
524 int
525 num_validated_changes (void)
526 {
527   return num_changes;
528 }
529
530 /* Retract the changes numbered NUM and up.  */
531
532 void
533 cancel_changes (int num)
534 {
535   int i;
536
537   /* Back out all the changes.  Do this in the opposite order in which
538      they were made.  */
539   for (i = num_changes - 1; i >= num; i--)
540     {
541       *changes[i].loc = changes[i].old;
542       if (changes[i].object && !MEM_P (changes[i].object))
543         INSN_CODE (changes[i].object) = changes[i].old_code;
544     }
545   num_changes = num;
546 }
547
548 /* A subroutine of validate_replace_rtx_1 that tries to simplify the resulting
549    rtx.  */
550
551 static void
552 simplify_while_replacing (rtx *loc, rtx to, rtx object,
553                           enum machine_mode op0_mode)
554 {
555   rtx x = *loc;
556   enum rtx_code code = GET_CODE (x);
557   rtx new_rtx;
558
559   if (SWAPPABLE_OPERANDS_P (x)
560       && swap_commutative_operands_p (XEXP (x, 0), XEXP (x, 1)))
561     {
562       validate_unshare_change (object, loc,
563                                gen_rtx_fmt_ee (COMMUTATIVE_ARITH_P (x) ? code
564                                                : swap_condition (code),
565                                                GET_MODE (x), XEXP (x, 1),
566                                                XEXP (x, 0)), 1);
567       x = *loc;
568       code = GET_CODE (x);
569     }
570
571   switch (code)
572     {
573     case PLUS:
574       /* If we have a PLUS whose second operand is now a CONST_INT, use
575          simplify_gen_binary to try to simplify it.
576          ??? We may want later to remove this, once simplification is
577          separated from this function.  */
578       if (CONST_INT_P (XEXP (x, 1)) && XEXP (x, 1) == to)
579         validate_change (object, loc,
580                          simplify_gen_binary
581                          (PLUS, GET_MODE (x), XEXP (x, 0), XEXP (x, 1)), 1);
582       break;
583     case MINUS:
584       if (CONST_INT_P (XEXP (x, 1))
585           || GET_CODE (XEXP (x, 1)) == CONST_DOUBLE)
586         validate_change (object, loc,
587                          simplify_gen_binary
588                          (PLUS, GET_MODE (x), XEXP (x, 0),
589                           simplify_gen_unary (NEG,
590                                               GET_MODE (x), XEXP (x, 1),
591                                               GET_MODE (x))), 1);
592       break;
593     case ZERO_EXTEND:
594     case SIGN_EXTEND:
595       if (GET_MODE (XEXP (x, 0)) == VOIDmode)
596         {
597           new_rtx = simplify_gen_unary (code, GET_MODE (x), XEXP (x, 0),
598                                     op0_mode);
599           /* If any of the above failed, substitute in something that
600              we know won't be recognized.  */
601           if (!new_rtx)
602             new_rtx = gen_rtx_CLOBBER (GET_MODE (x), const0_rtx);
603           validate_change (object, loc, new_rtx, 1);
604         }
605       break;
606     case SUBREG:
607       /* All subregs possible to simplify should be simplified.  */
608       new_rtx = simplify_subreg (GET_MODE (x), SUBREG_REG (x), op0_mode,
609                              SUBREG_BYTE (x));
610
611       /* Subregs of VOIDmode operands are incorrect.  */
612       if (!new_rtx && GET_MODE (SUBREG_REG (x)) == VOIDmode)
613         new_rtx = gen_rtx_CLOBBER (GET_MODE (x), const0_rtx);
614       if (new_rtx)
615         validate_change (object, loc, new_rtx, 1);
616       break;
617     case ZERO_EXTRACT:
618     case SIGN_EXTRACT:
619       /* If we are replacing a register with memory, try to change the memory
620          to be the mode required for memory in extract operations (this isn't
621          likely to be an insertion operation; if it was, nothing bad will
622          happen, we might just fail in some cases).  */
623
624       if (MEM_P (XEXP (x, 0))
625           && CONST_INT_P (XEXP (x, 1))
626           && CONST_INT_P (XEXP (x, 2))
627           && !mode_dependent_address_p (XEXP (XEXP (x, 0), 0))
628           && !MEM_VOLATILE_P (XEXP (x, 0)))
629         {
630           enum machine_mode wanted_mode = VOIDmode;
631           enum machine_mode is_mode = GET_MODE (XEXP (x, 0));
632           int pos = INTVAL (XEXP (x, 2));
633
634           if (GET_CODE (x) == ZERO_EXTRACT)
635             {
636               enum machine_mode new_mode
637                 = mode_for_extraction (EP_extzv, 1);
638               if (new_mode != MAX_MACHINE_MODE)
639                 wanted_mode = new_mode;
640             }
641           else if (GET_CODE (x) == SIGN_EXTRACT)
642             {
643               enum machine_mode new_mode
644                 = mode_for_extraction (EP_extv, 1);
645               if (new_mode != MAX_MACHINE_MODE)
646                 wanted_mode = new_mode;
647             }
648
649           /* If we have a narrower mode, we can do something.  */
650           if (wanted_mode != VOIDmode
651               && GET_MODE_SIZE (wanted_mode) < GET_MODE_SIZE (is_mode))
652             {
653               int offset = pos / BITS_PER_UNIT;
654               rtx newmem;
655
656               /* If the bytes and bits are counted differently, we
657                  must adjust the offset.  */
658               if (BYTES_BIG_ENDIAN != BITS_BIG_ENDIAN)
659                 offset =
660                   (GET_MODE_SIZE (is_mode) - GET_MODE_SIZE (wanted_mode) -
661                    offset);
662
663               gcc_assert (GET_MODE_PRECISION (wanted_mode)
664                           == GET_MODE_BITSIZE (wanted_mode));
665               pos %= GET_MODE_BITSIZE (wanted_mode);
666
667               newmem = adjust_address_nv (XEXP (x, 0), wanted_mode, offset);
668
669               validate_change (object, &XEXP (x, 2), GEN_INT (pos), 1);
670               validate_change (object, &XEXP (x, 0), newmem, 1);
671             }
672         }
673
674       break;
675
676     default:
677       break;
678     }
679 }
680
681 /* Replace every occurrence of FROM in X with TO.  Mark each change with
682    validate_change passing OBJECT.  */
683
684 static void
685 validate_replace_rtx_1 (rtx *loc, rtx from, rtx to, rtx object,
686                         bool simplify)
687 {
688   int i, j;
689   const char *fmt;
690   rtx x = *loc;
691   enum rtx_code code;
692   enum machine_mode op0_mode = VOIDmode;
693   int prev_changes = num_changes;
694
695   if (!x)
696     return;
697
698   code = GET_CODE (x);
699   fmt = GET_RTX_FORMAT (code);
700   if (fmt[0] == 'e')
701     op0_mode = GET_MODE (XEXP (x, 0));
702
703   /* X matches FROM if it is the same rtx or they are both referring to the
704      same register in the same mode.  Avoid calling rtx_equal_p unless the
705      operands look similar.  */
706
707   if (x == from
708       || (REG_P (x) && REG_P (from)
709           && GET_MODE (x) == GET_MODE (from)
710           && REGNO (x) == REGNO (from))
711       || (GET_CODE (x) == GET_CODE (from) && GET_MODE (x) == GET_MODE (from)
712           && rtx_equal_p (x, from)))
713     {
714       validate_unshare_change (object, loc, to, 1);
715       return;
716     }
717
718   /* Call ourself recursively to perform the replacements.
719      We must not replace inside already replaced expression, otherwise we
720      get infinite recursion for replacements like (reg X)->(subreg (reg X))
721      done by regmove, so we must special case shared ASM_OPERANDS.  */
722
723   if (GET_CODE (x) == PARALLEL)
724     {
725       for (j = XVECLEN (x, 0) - 1; j >= 0; j--)
726         {
727           if (j && GET_CODE (XVECEXP (x, 0, j)) == SET
728               && GET_CODE (SET_SRC (XVECEXP (x, 0, j))) == ASM_OPERANDS)
729             {
730               /* Verify that operands are really shared.  */
731               gcc_assert (ASM_OPERANDS_INPUT_VEC (SET_SRC (XVECEXP (x, 0, 0)))
732                           == ASM_OPERANDS_INPUT_VEC (SET_SRC (XVECEXP
733                                                               (x, 0, j))));
734               validate_replace_rtx_1 (&SET_DEST (XVECEXP (x, 0, j)),
735                                       from, to, object, simplify);
736             }
737           else
738             validate_replace_rtx_1 (&XVECEXP (x, 0, j), from, to, object,
739                                     simplify);
740         }
741     }
742   else
743     for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
744       {
745         if (fmt[i] == 'e')
746           validate_replace_rtx_1 (&XEXP (x, i), from, to, object, simplify);
747         else if (fmt[i] == 'E')
748           for (j = XVECLEN (x, i) - 1; j >= 0; j--)
749             validate_replace_rtx_1 (&XVECEXP (x, i, j), from, to, object,
750                                     simplify);
751       }
752
753   /* If we didn't substitute, there is nothing more to do.  */
754   if (num_changes == prev_changes)
755     return;
756
757   /* Allow substituted expression to have different mode.  This is used by
758      regmove to change mode of pseudo register.  */
759   if (fmt[0] == 'e' && GET_MODE (XEXP (x, 0)) != VOIDmode)
760     op0_mode = GET_MODE (XEXP (x, 0));
761
762   /* Do changes needed to keep rtx consistent.  Don't do any other
763      simplifications, as it is not our job.  */
764   if (simplify)
765     simplify_while_replacing (loc, to, object, op0_mode);
766 }
767
768 /* Try replacing every occurrence of FROM in subexpression LOC of INSN
769    with TO.  After all changes have been made, validate by seeing
770    if INSN is still valid.  */
771
772 int
773 validate_replace_rtx_subexp (rtx from, rtx to, rtx insn, rtx *loc)
774 {
775   validate_replace_rtx_1 (loc, from, to, insn, true);
776   return apply_change_group ();
777 }
778
779 /* Try replacing every occurrence of FROM in INSN with TO.  After all
780    changes have been made, validate by seeing if INSN is still valid.  */
781
782 int
783 validate_replace_rtx (rtx from, rtx to, rtx insn)
784 {
785   validate_replace_rtx_1 (&PATTERN (insn), from, to, insn, true);
786   return apply_change_group ();
787 }
788
789 /* Try replacing every occurrence of FROM in WHERE with TO.  Assume that WHERE
790    is a part of INSN.  After all changes have been made, validate by seeing if
791    INSN is still valid.
792    validate_replace_rtx (from, to, insn) is equivalent to
793    validate_replace_rtx_part (from, to, &PATTERN (insn), insn).  */
794
795 int
796 validate_replace_rtx_part (rtx from, rtx to, rtx *where, rtx insn)
797 {
798   validate_replace_rtx_1 (where, from, to, insn, true);
799   return apply_change_group ();
800 }
801
802 /* Same as above, but do not simplify rtx afterwards.  */
803 int
804 validate_replace_rtx_part_nosimplify (rtx from, rtx to, rtx *where,
805                                       rtx insn)
806 {
807   validate_replace_rtx_1 (where, from, to, insn, false);
808   return apply_change_group ();
809
810 }
811
812 /* Try replacing every occurrence of FROM in INSN with TO.  This also
813    will replace in REG_EQUAL and REG_EQUIV notes.  */
814
815 void
816 validate_replace_rtx_group (rtx from, rtx to, rtx insn)
817 {
818   rtx note;
819   validate_replace_rtx_1 (&PATTERN (insn), from, to, insn, true);
820   for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
821     if (REG_NOTE_KIND (note) == REG_EQUAL
822         || REG_NOTE_KIND (note) == REG_EQUIV)
823       validate_replace_rtx_1 (&XEXP (note, 0), from, to, insn, true);
824 }
825
826 /* Function called by note_uses to replace used subexpressions.  */
827 struct validate_replace_src_data
828 {
829   rtx from;                     /* Old RTX */
830   rtx to;                       /* New RTX */
831   rtx insn;                     /* Insn in which substitution is occurring.  */
832 };
833
834 static void
835 validate_replace_src_1 (rtx *x, void *data)
836 {
837   struct validate_replace_src_data *d
838     = (struct validate_replace_src_data *) data;
839
840   validate_replace_rtx_1 (x, d->from, d->to, d->insn, true);
841 }
842
843 /* Try replacing every occurrence of FROM in INSN with TO, avoiding
844    SET_DESTs.  */
845
846 void
847 validate_replace_src_group (rtx from, rtx to, rtx insn)
848 {
849   struct validate_replace_src_data d;
850
851   d.from = from;
852   d.to = to;
853   d.insn = insn;
854   note_uses (&PATTERN (insn), validate_replace_src_1, &d);
855 }
856
857 /* Try simplify INSN.
858    Invoke simplify_rtx () on every SET_SRC and SET_DEST inside the INSN's
859    pattern and return true if something was simplified.  */
860
861 bool
862 validate_simplify_insn (rtx insn)
863 {
864   int i;
865   rtx pat = NULL;
866   rtx newpat = NULL;
867
868   pat = PATTERN (insn);
869
870   if (GET_CODE (pat) == SET)
871     {
872       newpat = simplify_rtx (SET_SRC (pat));
873       if (newpat && !rtx_equal_p (SET_SRC (pat), newpat))
874         validate_change (insn, &SET_SRC (pat), newpat, 1);
875       newpat = simplify_rtx (SET_DEST (pat));
876       if (newpat && !rtx_equal_p (SET_DEST (pat), newpat))
877         validate_change (insn, &SET_DEST (pat), newpat, 1);
878     }
879   else if (GET_CODE (pat) == PARALLEL)
880     for (i = 0; i < XVECLEN (pat, 0); i++)
881       {
882         rtx s = XVECEXP (pat, 0, i);
883
884         if (GET_CODE (XVECEXP (pat, 0, i)) == SET)
885           {
886             newpat = simplify_rtx (SET_SRC (s));
887             if (newpat && !rtx_equal_p (SET_SRC (s), newpat))
888               validate_change (insn, &SET_SRC (s), newpat, 1);
889             newpat = simplify_rtx (SET_DEST (s));
890             if (newpat && !rtx_equal_p (SET_DEST (s), newpat))
891               validate_change (insn, &SET_DEST (s), newpat, 1);
892           }
893       }
894   return ((num_changes_pending () > 0) && (apply_change_group () > 0));
895 }
896 \f
897 #ifdef HAVE_cc0
898 /* Return 1 if the insn using CC0 set by INSN does not contain
899    any ordered tests applied to the condition codes.
900    EQ and NE tests do not count.  */
901
902 int
903 next_insn_tests_no_inequality (rtx insn)
904 {
905   rtx next = next_cc0_user (insn);
906
907   /* If there is no next insn, we have to take the conservative choice.  */
908   if (next == 0)
909     return 0;
910
911   return (INSN_P (next)
912           && ! inequality_comparisons_p (PATTERN (next)));
913 }
914 #endif
915 \f
916 /* Return 1 if OP is a valid general operand for machine mode MODE.
917    This is either a register reference, a memory reference,
918    or a constant.  In the case of a memory reference, the address
919    is checked for general validity for the target machine.
920
921    Register and memory references must have mode MODE in order to be valid,
922    but some constants have no machine mode and are valid for any mode.
923
924    If MODE is VOIDmode, OP is checked for validity for whatever mode
925    it has.
926
927    The main use of this function is as a predicate in match_operand
928    expressions in the machine description.  */
929
930 int
931 general_operand (rtx op, enum machine_mode mode)
932 {
933   enum rtx_code code = GET_CODE (op);
934
935   if (mode == VOIDmode)
936     mode = GET_MODE (op);
937
938   /* Don't accept CONST_INT or anything similar
939      if the caller wants something floating.  */
940   if (GET_MODE (op) == VOIDmode && mode != VOIDmode
941       && GET_MODE_CLASS (mode) != MODE_INT
942       && GET_MODE_CLASS (mode) != MODE_PARTIAL_INT)
943     return 0;
944
945   if (CONST_INT_P (op)
946       && mode != VOIDmode
947       && trunc_int_for_mode (INTVAL (op), mode) != INTVAL (op))
948     return 0;
949
950   if (CONSTANT_P (op))
951     return ((GET_MODE (op) == VOIDmode || GET_MODE (op) == mode
952              || mode == VOIDmode)
953             && (! flag_pic || LEGITIMATE_PIC_OPERAND_P (op))
954             && targetm.legitimate_constant_p (mode == VOIDmode
955                                               ? GET_MODE (op)
956                                               : mode, op));
957
958   /* Except for certain constants with VOIDmode, already checked for,
959      OP's mode must match MODE if MODE specifies a mode.  */
960
961   if (GET_MODE (op) != mode)
962     return 0;
963
964   if (code == SUBREG)
965     {
966       rtx sub = SUBREG_REG (op);
967
968 #ifdef INSN_SCHEDULING
969       /* On machines that have insn scheduling, we want all memory
970          reference to be explicit, so outlaw paradoxical SUBREGs.
971          However, we must allow them after reload so that they can
972          get cleaned up by cleanup_subreg_operands.  */
973       if (!reload_completed && MEM_P (sub)
974           && GET_MODE_SIZE (mode) > GET_MODE_SIZE (GET_MODE (sub)))
975         return 0;
976 #endif
977       /* Avoid memories with nonzero SUBREG_BYTE, as offsetting the memory
978          may result in incorrect reference.  We should simplify all valid
979          subregs of MEM anyway.  But allow this after reload because we
980          might be called from cleanup_subreg_operands.
981
982          ??? This is a kludge.  */
983       if (!reload_completed && SUBREG_BYTE (op) != 0
984           && MEM_P (sub))
985         return 0;
986
987       /* FLOAT_MODE subregs can't be paradoxical.  Combine will occasionally
988          create such rtl, and we must reject it.  */
989       if (SCALAR_FLOAT_MODE_P (GET_MODE (op))
990           && GET_MODE_SIZE (GET_MODE (op)) > GET_MODE_SIZE (GET_MODE (sub)))
991         return 0;
992
993       op = sub;
994       code = GET_CODE (op);
995     }
996
997   if (code == REG)
998     return (REGNO (op) >= FIRST_PSEUDO_REGISTER
999             || in_hard_reg_set_p (operand_reg_set, GET_MODE (op), REGNO (op)));
1000
1001   if (code == MEM)
1002     {
1003       rtx y = XEXP (op, 0);
1004
1005       if (! volatile_ok && MEM_VOLATILE_P (op))
1006         return 0;
1007
1008       /* Use the mem's mode, since it will be reloaded thus.  */
1009       if (memory_address_addr_space_p (GET_MODE (op), y, MEM_ADDR_SPACE (op)))
1010         return 1;
1011     }
1012
1013   return 0;
1014 }
1015 \f
1016 /* Return 1 if OP is a valid memory address for a memory reference
1017    of mode MODE.
1018
1019    The main use of this function is as a predicate in match_operand
1020    expressions in the machine description.  */
1021
1022 int
1023 address_operand (rtx op, enum machine_mode mode)
1024 {
1025   return memory_address_p (mode, op);
1026 }
1027
1028 /* Return 1 if OP is a register reference of mode MODE.
1029    If MODE is VOIDmode, accept a register in any mode.
1030
1031    The main use of this function is as a predicate in match_operand
1032    expressions in the machine description.  */
1033
1034 int
1035 register_operand (rtx op, enum machine_mode mode)
1036 {
1037   if (GET_MODE (op) != mode && mode != VOIDmode)
1038     return 0;
1039
1040   if (GET_CODE (op) == SUBREG)
1041     {
1042       rtx sub = SUBREG_REG (op);
1043
1044       /* Before reload, we can allow (SUBREG (MEM...)) as a register operand
1045          because it is guaranteed to be reloaded into one.
1046          Just make sure the MEM is valid in itself.
1047          (Ideally, (SUBREG (MEM)...) should not exist after reload,
1048          but currently it does result from (SUBREG (REG)...) where the
1049          reg went on the stack.)  */
1050       if (! reload_completed && MEM_P (sub))
1051         return general_operand (op, mode);
1052
1053 #ifdef CANNOT_CHANGE_MODE_CLASS
1054       if (REG_P (sub)
1055           && REGNO (sub) < FIRST_PSEUDO_REGISTER
1056           && REG_CANNOT_CHANGE_MODE_P (REGNO (sub), GET_MODE (sub), mode)
1057           && GET_MODE_CLASS (GET_MODE (sub)) != MODE_COMPLEX_INT
1058           && GET_MODE_CLASS (GET_MODE (sub)) != MODE_COMPLEX_FLOAT)
1059         return 0;
1060 #endif
1061
1062       /* FLOAT_MODE subregs can't be paradoxical.  Combine will occasionally
1063          create such rtl, and we must reject it.  */
1064       if (SCALAR_FLOAT_MODE_P (GET_MODE (op))
1065           && GET_MODE_SIZE (GET_MODE (op)) > GET_MODE_SIZE (GET_MODE (sub)))
1066         return 0;
1067
1068       op = sub;
1069     }
1070
1071   return (REG_P (op)
1072           && (REGNO (op) >= FIRST_PSEUDO_REGISTER
1073               || in_hard_reg_set_p (operand_reg_set,
1074                                     GET_MODE (op), REGNO (op))));
1075 }
1076
1077 /* Return 1 for a register in Pmode; ignore the tested mode.  */
1078
1079 int
1080 pmode_register_operand (rtx op, enum machine_mode mode ATTRIBUTE_UNUSED)
1081 {
1082   return register_operand (op, Pmode);
1083 }
1084
1085 /* Return 1 if OP should match a MATCH_SCRATCH, i.e., if it is a SCRATCH
1086    or a hard register.  */
1087
1088 int
1089 scratch_operand (rtx op, enum machine_mode mode)
1090 {
1091   if (GET_MODE (op) != mode && mode != VOIDmode)
1092     return 0;
1093
1094   return (GET_CODE (op) == SCRATCH
1095           || (REG_P (op)
1096               && REGNO (op) < FIRST_PSEUDO_REGISTER));
1097 }
1098
1099 /* Return 1 if OP is a valid immediate operand for mode MODE.
1100
1101    The main use of this function is as a predicate in match_operand
1102    expressions in the machine description.  */
1103
1104 int
1105 immediate_operand (rtx op, enum machine_mode mode)
1106 {
1107   /* Don't accept CONST_INT or anything similar
1108      if the caller wants something floating.  */
1109   if (GET_MODE (op) == VOIDmode && mode != VOIDmode
1110       && GET_MODE_CLASS (mode) != MODE_INT
1111       && GET_MODE_CLASS (mode) != MODE_PARTIAL_INT)
1112     return 0;
1113
1114   if (CONST_INT_P (op)
1115       && mode != VOIDmode
1116       && trunc_int_for_mode (INTVAL (op), mode) != INTVAL (op))
1117     return 0;
1118
1119   return (CONSTANT_P (op)
1120           && (GET_MODE (op) == mode || mode == VOIDmode
1121               || GET_MODE (op) == VOIDmode)
1122           && (! flag_pic || LEGITIMATE_PIC_OPERAND_P (op))
1123           && targetm.legitimate_constant_p (mode == VOIDmode
1124                                             ? GET_MODE (op)
1125                                             : mode, op));
1126 }
1127
1128 /* Returns 1 if OP is an operand that is a CONST_INT.  */
1129
1130 int
1131 const_int_operand (rtx op, enum machine_mode mode)
1132 {
1133   if (!CONST_INT_P (op))
1134     return 0;
1135
1136   if (mode != VOIDmode
1137       && trunc_int_for_mode (INTVAL (op), mode) != INTVAL (op))
1138     return 0;
1139
1140   return 1;
1141 }
1142
1143 /* Returns 1 if OP is an operand that is a constant integer or constant
1144    floating-point number.  */
1145
1146 int
1147 const_double_operand (rtx op, enum machine_mode mode)
1148 {
1149   /* Don't accept CONST_INT or anything similar
1150      if the caller wants something floating.  */
1151   if (GET_MODE (op) == VOIDmode && mode != VOIDmode
1152       && GET_MODE_CLASS (mode) != MODE_INT
1153       && GET_MODE_CLASS (mode) != MODE_PARTIAL_INT)
1154     return 0;
1155
1156   return ((GET_CODE (op) == CONST_DOUBLE || CONST_INT_P (op))
1157           && (mode == VOIDmode || GET_MODE (op) == mode
1158               || GET_MODE (op) == VOIDmode));
1159 }
1160
1161 /* Return 1 if OP is a general operand that is not an immediate operand.  */
1162
1163 int
1164 nonimmediate_operand (rtx op, enum machine_mode mode)
1165 {
1166   return (general_operand (op, mode) && ! CONSTANT_P (op));
1167 }
1168
1169 /* Return 1 if OP is a register reference or immediate value of mode MODE.  */
1170
1171 int
1172 nonmemory_operand (rtx op, enum machine_mode mode)
1173 {
1174   if (CONSTANT_P (op))
1175     return immediate_operand (op, mode);
1176
1177   if (GET_MODE (op) != mode && mode != VOIDmode)
1178     return 0;
1179
1180   if (GET_CODE (op) == SUBREG)
1181     {
1182       /* Before reload, we can allow (SUBREG (MEM...)) as a register operand
1183          because it is guaranteed to be reloaded into one.
1184          Just make sure the MEM is valid in itself.
1185          (Ideally, (SUBREG (MEM)...) should not exist after reload,
1186          but currently it does result from (SUBREG (REG)...) where the
1187          reg went on the stack.)  */
1188       if (! reload_completed && MEM_P (SUBREG_REG (op)))
1189         return general_operand (op, mode);
1190       op = SUBREG_REG (op);
1191     }
1192
1193   return (REG_P (op)
1194           && (REGNO (op) >= FIRST_PSEUDO_REGISTER
1195               || in_hard_reg_set_p (operand_reg_set,
1196                                     GET_MODE (op), REGNO (op))));
1197 }
1198
1199 /* Return 1 if OP is a valid operand that stands for pushing a
1200    value of mode MODE onto the stack.
1201
1202    The main use of this function is as a predicate in match_operand
1203    expressions in the machine description.  */
1204
1205 int
1206 push_operand (rtx op, enum machine_mode mode)
1207 {
1208   unsigned int rounded_size = GET_MODE_SIZE (mode);
1209
1210 #ifdef PUSH_ROUNDING
1211   rounded_size = PUSH_ROUNDING (rounded_size);
1212 #endif
1213
1214   if (!MEM_P (op))
1215     return 0;
1216
1217   if (mode != VOIDmode && GET_MODE (op) != mode)
1218     return 0;
1219
1220   op = XEXP (op, 0);
1221
1222   if (rounded_size == GET_MODE_SIZE (mode))
1223     {
1224       if (GET_CODE (op) != STACK_PUSH_CODE)
1225         return 0;
1226     }
1227   else
1228     {
1229       if (GET_CODE (op) != PRE_MODIFY
1230           || GET_CODE (XEXP (op, 1)) != PLUS
1231           || XEXP (XEXP (op, 1), 0) != XEXP (op, 0)
1232           || !CONST_INT_P (XEXP (XEXP (op, 1), 1))
1233 #ifdef STACK_GROWS_DOWNWARD
1234           || INTVAL (XEXP (XEXP (op, 1), 1)) != - (int) rounded_size
1235 #else
1236           || INTVAL (XEXP (XEXP (op, 1), 1)) != (int) rounded_size
1237 #endif
1238           )
1239         return 0;
1240     }
1241
1242   return XEXP (op, 0) == stack_pointer_rtx;
1243 }
1244
1245 /* Return 1 if OP is a valid operand that stands for popping a
1246    value of mode MODE off the stack.
1247
1248    The main use of this function is as a predicate in match_operand
1249    expressions in the machine description.  */
1250
1251 int
1252 pop_operand (rtx op, enum machine_mode mode)
1253 {
1254   if (!MEM_P (op))
1255     return 0;
1256
1257   if (mode != VOIDmode && GET_MODE (op) != mode)
1258     return 0;
1259
1260   op = XEXP (op, 0);
1261
1262   if (GET_CODE (op) != STACK_POP_CODE)
1263     return 0;
1264
1265   return XEXP (op, 0) == stack_pointer_rtx;
1266 }
1267
1268 /* Return 1 if ADDR is a valid memory address
1269    for mode MODE in address space AS.  */
1270
1271 int
1272 memory_address_addr_space_p (enum machine_mode mode ATTRIBUTE_UNUSED,
1273                              rtx addr, addr_space_t as)
1274 {
1275 #ifdef GO_IF_LEGITIMATE_ADDRESS
1276   gcc_assert (ADDR_SPACE_GENERIC_P (as));
1277   GO_IF_LEGITIMATE_ADDRESS (mode, addr, win);
1278   return 0;
1279
1280  win:
1281   return 1;
1282 #else
1283   return targetm.addr_space.legitimate_address_p (mode, addr, 0, as);
1284 #endif
1285 }
1286
1287 /* Return 1 if OP is a valid memory reference with mode MODE,
1288    including a valid address.
1289
1290    The main use of this function is as a predicate in match_operand
1291    expressions in the machine description.  */
1292
1293 int
1294 memory_operand (rtx op, enum machine_mode mode)
1295 {
1296   rtx inner;
1297
1298   if (! reload_completed)
1299     /* Note that no SUBREG is a memory operand before end of reload pass,
1300        because (SUBREG (MEM...)) forces reloading into a register.  */
1301     return MEM_P (op) && general_operand (op, mode);
1302
1303   if (mode != VOIDmode && GET_MODE (op) != mode)
1304     return 0;
1305
1306   inner = op;
1307   if (GET_CODE (inner) == SUBREG)
1308     inner = SUBREG_REG (inner);
1309
1310   return (MEM_P (inner) && general_operand (op, mode));
1311 }
1312
1313 /* Return 1 if OP is a valid indirect memory reference with mode MODE;
1314    that is, a memory reference whose address is a general_operand.  */
1315
1316 int
1317 indirect_operand (rtx op, enum machine_mode mode)
1318 {
1319   /* Before reload, a SUBREG isn't in memory (see memory_operand, above).  */
1320   if (! reload_completed
1321       && GET_CODE (op) == SUBREG && MEM_P (SUBREG_REG (op)))
1322     {
1323       int offset = SUBREG_BYTE (op);
1324       rtx inner = SUBREG_REG (op);
1325
1326       if (mode != VOIDmode && GET_MODE (op) != mode)
1327         return 0;
1328
1329       /* The only way that we can have a general_operand as the resulting
1330          address is if OFFSET is zero and the address already is an operand
1331          or if the address is (plus Y (const_int -OFFSET)) and Y is an
1332          operand.  */
1333
1334       return ((offset == 0 && general_operand (XEXP (inner, 0), Pmode))
1335               || (GET_CODE (XEXP (inner, 0)) == PLUS
1336                   && CONST_INT_P (XEXP (XEXP (inner, 0), 1))
1337                   && INTVAL (XEXP (XEXP (inner, 0), 1)) == -offset
1338                   && general_operand (XEXP (XEXP (inner, 0), 0), Pmode)));
1339     }
1340
1341   return (MEM_P (op)
1342           && memory_operand (op, mode)
1343           && general_operand (XEXP (op, 0), Pmode));
1344 }
1345
1346 /* Return 1 if this is an ordered comparison operator (not including
1347    ORDERED and UNORDERED).  */
1348
1349 int
1350 ordered_comparison_operator (rtx op, enum machine_mode mode)
1351 {
1352   if (mode != VOIDmode && GET_MODE (op) != mode)
1353     return false;
1354   switch (GET_CODE (op))
1355     {
1356     case EQ:
1357     case NE:
1358     case LT:
1359     case LTU:
1360     case LE:
1361     case LEU:
1362     case GT:
1363     case GTU:
1364     case GE:
1365     case GEU:
1366       return true;
1367     default:
1368       return false;
1369     }
1370 }
1371
1372 /* Return 1 if this is a comparison operator.  This allows the use of
1373    MATCH_OPERATOR to recognize all the branch insns.  */
1374
1375 int
1376 comparison_operator (rtx op, enum machine_mode mode)
1377 {
1378   return ((mode == VOIDmode || GET_MODE (op) == mode)
1379           && COMPARISON_P (op));
1380 }
1381 \f
1382 /* If BODY is an insn body that uses ASM_OPERANDS, return it.  */
1383
1384 rtx
1385 extract_asm_operands (rtx body)
1386 {
1387   rtx tmp;
1388   switch (GET_CODE (body))
1389     {
1390     case ASM_OPERANDS:
1391       return body;
1392
1393     case SET:
1394       /* Single output operand: BODY is (set OUTPUT (asm_operands ...)).  */
1395       tmp = SET_SRC (body);
1396       if (GET_CODE (tmp) == ASM_OPERANDS)
1397         return tmp;
1398       break;
1399
1400     case PARALLEL:
1401       tmp = XVECEXP (body, 0, 0);
1402       if (GET_CODE (tmp) == ASM_OPERANDS)
1403         return tmp;
1404       if (GET_CODE (tmp) == SET)
1405         {
1406           tmp = SET_SRC (tmp);
1407           if (GET_CODE (tmp) == ASM_OPERANDS)
1408             return tmp;
1409         }
1410       break;
1411
1412     default:
1413       break;
1414     }
1415   return NULL;
1416 }
1417
1418 /* If BODY is an insn body that uses ASM_OPERANDS,
1419    return the number of operands (both input and output) in the insn.
1420    Otherwise return -1.  */
1421
1422 int
1423 asm_noperands (const_rtx body)
1424 {
1425   rtx asm_op = extract_asm_operands (CONST_CAST_RTX (body));
1426   int n_sets = 0;
1427
1428   if (asm_op == NULL)
1429     return -1;
1430
1431   if (GET_CODE (body) == SET)
1432     n_sets = 1;
1433   else if (GET_CODE (body) == PARALLEL)
1434     {
1435       int i;
1436       if (GET_CODE (XVECEXP (body, 0, 0)) == SET)
1437         {
1438           /* Multiple output operands, or 1 output plus some clobbers:
1439              body is
1440              [(set OUTPUT (asm_operands ...))... (clobber (reg ...))...].  */
1441           /* Count backwards through CLOBBERs to determine number of SETs.  */
1442           for (i = XVECLEN (body, 0); i > 0; i--)
1443             {
1444               if (GET_CODE (XVECEXP (body, 0, i - 1)) == SET)
1445                 break;
1446               if (GET_CODE (XVECEXP (body, 0, i - 1)) != CLOBBER)
1447                 return -1;
1448             }
1449
1450           /* N_SETS is now number of output operands.  */
1451           n_sets = i;
1452
1453           /* Verify that all the SETs we have
1454              came from a single original asm_operands insn
1455              (so that invalid combinations are blocked).  */
1456           for (i = 0; i < n_sets; i++)
1457             {
1458               rtx elt = XVECEXP (body, 0, i);
1459               if (GET_CODE (elt) != SET)
1460                 return -1;
1461               if (GET_CODE (SET_SRC (elt)) != ASM_OPERANDS)
1462                 return -1;
1463               /* If these ASM_OPERANDS rtx's came from different original insns
1464                  then they aren't allowed together.  */
1465               if (ASM_OPERANDS_INPUT_VEC (SET_SRC (elt))
1466                   != ASM_OPERANDS_INPUT_VEC (asm_op))
1467                 return -1;
1468             }
1469         }
1470       else
1471         {
1472           /* 0 outputs, but some clobbers:
1473              body is [(asm_operands ...) (clobber (reg ...))...].  */
1474           /* Make sure all the other parallel things really are clobbers.  */
1475           for (i = XVECLEN (body, 0) - 1; i > 0; i--)
1476             if (GET_CODE (XVECEXP (body, 0, i)) != CLOBBER)
1477               return -1;
1478         }
1479     }
1480
1481   return (ASM_OPERANDS_INPUT_LENGTH (asm_op)
1482           + ASM_OPERANDS_LABEL_LENGTH (asm_op) + n_sets);
1483 }
1484
1485 /* Assuming BODY is an insn body that uses ASM_OPERANDS,
1486    copy its operands (both input and output) into the vector OPERANDS,
1487    the locations of the operands within the insn into the vector OPERAND_LOCS,
1488    and the constraints for the operands into CONSTRAINTS.
1489    Write the modes of the operands into MODES.
1490    Return the assembler-template.
1491
1492    If MODES, OPERAND_LOCS, CONSTRAINTS or OPERANDS is 0,
1493    we don't store that info.  */
1494
1495 const char *
1496 decode_asm_operands (rtx body, rtx *operands, rtx **operand_locs,
1497                      const char **constraints, enum machine_mode *modes,
1498                      location_t *loc)
1499 {
1500   int nbase = 0, n, i;
1501   rtx asmop;
1502
1503   switch (GET_CODE (body))
1504     {
1505     case ASM_OPERANDS:
1506       /* Zero output asm: BODY is (asm_operands ...).  */
1507       asmop = body;
1508       break;
1509
1510     case SET:
1511       /* Single output asm: BODY is (set OUTPUT (asm_operands ...)).  */
1512       asmop = SET_SRC (body);
1513
1514       /* The output is in the SET.
1515          Its constraint is in the ASM_OPERANDS itself.  */
1516       if (operands)
1517         operands[0] = SET_DEST (body);
1518       if (operand_locs)
1519         operand_locs[0] = &SET_DEST (body);
1520       if (constraints)
1521         constraints[0] = ASM_OPERANDS_OUTPUT_CONSTRAINT (asmop);
1522       if (modes)
1523         modes[0] = GET_MODE (SET_DEST (body));
1524       nbase = 1;
1525       break;
1526
1527     case PARALLEL:
1528       {
1529         int nparallel = XVECLEN (body, 0); /* Includes CLOBBERs.  */
1530
1531         asmop = XVECEXP (body, 0, 0);
1532         if (GET_CODE (asmop) == SET)
1533           {
1534             asmop = SET_SRC (asmop);
1535
1536             /* At least one output, plus some CLOBBERs.  The outputs are in
1537                the SETs.  Their constraints are in the ASM_OPERANDS itself.  */
1538             for (i = 0; i < nparallel; i++)
1539               {
1540                 if (GET_CODE (XVECEXP (body, 0, i)) == CLOBBER)
1541                   break;                /* Past last SET */
1542                 if (operands)
1543                   operands[i] = SET_DEST (XVECEXP (body, 0, i));
1544                 if (operand_locs)
1545                   operand_locs[i] = &SET_DEST (XVECEXP (body, 0, i));
1546                 if (constraints)
1547                   constraints[i] = XSTR (SET_SRC (XVECEXP (body, 0, i)), 1);
1548                 if (modes)
1549                   modes[i] = GET_MODE (SET_DEST (XVECEXP (body, 0, i)));
1550               }
1551             nbase = i;
1552           }
1553         break;
1554       }
1555
1556     default:
1557       gcc_unreachable ();
1558     }
1559
1560   n = ASM_OPERANDS_INPUT_LENGTH (asmop);
1561   for (i = 0; i < n; i++)
1562     {
1563       if (operand_locs)
1564         operand_locs[nbase + i] = &ASM_OPERANDS_INPUT (asmop, i);
1565       if (operands)
1566         operands[nbase + i] = ASM_OPERANDS_INPUT (asmop, i);
1567       if (constraints)
1568         constraints[nbase + i] = ASM_OPERANDS_INPUT_CONSTRAINT (asmop, i);
1569       if (modes)
1570         modes[nbase + i] = ASM_OPERANDS_INPUT_MODE (asmop, i);
1571     }
1572   nbase += n;
1573
1574   n = ASM_OPERANDS_LABEL_LENGTH (asmop);
1575   for (i = 0; i < n; i++)
1576     {
1577       if (operand_locs)
1578         operand_locs[nbase + i] = &ASM_OPERANDS_LABEL (asmop, i);
1579       if (operands)
1580         operands[nbase + i] = ASM_OPERANDS_LABEL (asmop, i);
1581       if (constraints)
1582         constraints[nbase + i] = "";
1583       if (modes)
1584         modes[nbase + i] = Pmode;
1585     }
1586
1587   if (loc)
1588     *loc = ASM_OPERANDS_SOURCE_LOCATION (asmop);
1589
1590   return ASM_OPERANDS_TEMPLATE (asmop);
1591 }
1592
1593 /* Check if an asm_operand matches its constraints.
1594    Return > 0 if ok, = 0 if bad, < 0 if inconclusive.  */
1595
1596 int
1597 asm_operand_ok (rtx op, const char *constraint, const char **constraints)
1598 {
1599   int result = 0;
1600 #ifdef AUTO_INC_DEC
1601   bool incdec_ok = false;
1602 #endif
1603
1604   /* Use constrain_operands after reload.  */
1605   gcc_assert (!reload_completed);
1606
1607   /* Empty constraint string is the same as "X,...,X", i.e. X for as
1608      many alternatives as required to match the other operands.  */
1609   if (*constraint == '\0')
1610     result = 1;
1611
1612   while (*constraint)
1613     {
1614       char c = *constraint;
1615       int len;
1616       switch (c)
1617         {
1618         case ',':
1619           constraint++;
1620           continue;
1621         case '=':
1622         case '+':
1623         case '*':
1624         case '%':
1625         case '!':
1626         case '#':
1627         case '&':
1628         case '?':
1629           break;
1630
1631         case '0': case '1': case '2': case '3': case '4':
1632         case '5': case '6': case '7': case '8': case '9':
1633           /* If caller provided constraints pointer, look up
1634              the maching constraint.  Otherwise, our caller should have
1635              given us the proper matching constraint, but we can't
1636              actually fail the check if they didn't.  Indicate that
1637              results are inconclusive.  */
1638           if (constraints)
1639             {
1640               char *end;
1641               unsigned long match;
1642
1643               match = strtoul (constraint, &end, 10);
1644               if (!result)
1645                 result = asm_operand_ok (op, constraints[match], NULL);
1646               constraint = (const char *) end;
1647             }
1648           else
1649             {
1650               do
1651                 constraint++;
1652               while (ISDIGIT (*constraint));
1653               if (! result)
1654                 result = -1;
1655             }
1656           continue;
1657
1658         case 'p':
1659           if (address_operand (op, VOIDmode))
1660             result = 1;
1661           break;
1662
1663         case TARGET_MEM_CONSTRAINT:
1664         case 'V': /* non-offsettable */
1665           if (memory_operand (op, VOIDmode))
1666             result = 1;
1667           break;
1668
1669         case 'o': /* offsettable */
1670           if (offsettable_nonstrict_memref_p (op))
1671             result = 1;
1672           break;
1673
1674         case '<':
1675           /* ??? Before auto-inc-dec, auto inc/dec insns are not supposed to exist,
1676              excepting those that expand_call created.  Further, on some
1677              machines which do not have generalized auto inc/dec, an inc/dec
1678              is not a memory_operand.
1679
1680              Match any memory and hope things are resolved after reload.  */
1681
1682           if (MEM_P (op)
1683               && (1
1684                   || GET_CODE (XEXP (op, 0)) == PRE_DEC
1685                   || GET_CODE (XEXP (op, 0)) == POST_DEC))
1686             result = 1;
1687 #ifdef AUTO_INC_DEC
1688           incdec_ok = true;
1689 #endif
1690           break;
1691
1692         case '>':
1693           if (MEM_P (op)
1694               && (1
1695                   || GET_CODE (XEXP (op, 0)) == PRE_INC
1696                   || GET_CODE (XEXP (op, 0)) == POST_INC))
1697             result = 1;
1698 #ifdef AUTO_INC_DEC
1699           incdec_ok = true;
1700 #endif
1701           break;
1702
1703         case 'E':
1704         case 'F':
1705           if (GET_CODE (op) == CONST_DOUBLE
1706               || (GET_CODE (op) == CONST_VECTOR
1707                   && GET_MODE_CLASS (GET_MODE (op)) == MODE_VECTOR_FLOAT))
1708             result = 1;
1709           break;
1710
1711         case 'G':
1712           if (GET_CODE (op) == CONST_DOUBLE
1713               && CONST_DOUBLE_OK_FOR_CONSTRAINT_P (op, 'G', constraint))
1714             result = 1;
1715           break;
1716         case 'H':
1717           if (GET_CODE (op) == CONST_DOUBLE
1718               && CONST_DOUBLE_OK_FOR_CONSTRAINT_P (op, 'H', constraint))
1719             result = 1;
1720           break;
1721
1722         case 's':
1723           if (CONST_INT_P (op)
1724               || (GET_CODE (op) == CONST_DOUBLE
1725                   && GET_MODE (op) == VOIDmode))
1726             break;
1727           /* Fall through.  */
1728
1729         case 'i':
1730           if (CONSTANT_P (op) && (! flag_pic || LEGITIMATE_PIC_OPERAND_P (op)))
1731             result = 1;
1732           break;
1733
1734         case 'n':
1735           if (CONST_INT_P (op)
1736               || (GET_CODE (op) == CONST_DOUBLE
1737                   && GET_MODE (op) == VOIDmode))
1738             result = 1;
1739           break;
1740
1741         case 'I':
1742           if (CONST_INT_P (op)
1743               && CONST_OK_FOR_CONSTRAINT_P (INTVAL (op), 'I', constraint))
1744             result = 1;
1745           break;
1746         case 'J':
1747           if (CONST_INT_P (op)
1748               && CONST_OK_FOR_CONSTRAINT_P (INTVAL (op), 'J', constraint))
1749             result = 1;
1750           break;
1751         case 'K':
1752           if (CONST_INT_P (op)
1753               && CONST_OK_FOR_CONSTRAINT_P (INTVAL (op), 'K', constraint))
1754             result = 1;
1755           break;
1756         case 'L':
1757           if (CONST_INT_P (op)
1758               && CONST_OK_FOR_CONSTRAINT_P (INTVAL (op), 'L', constraint))
1759             result = 1;
1760           break;
1761         case 'M':
1762           if (CONST_INT_P (op)
1763               && CONST_OK_FOR_CONSTRAINT_P (INTVAL (op), 'M', constraint))
1764             result = 1;
1765           break;
1766         case 'N':
1767           if (CONST_INT_P (op)
1768               && CONST_OK_FOR_CONSTRAINT_P (INTVAL (op), 'N', constraint))
1769             result = 1;
1770           break;
1771         case 'O':
1772           if (CONST_INT_P (op)
1773               && CONST_OK_FOR_CONSTRAINT_P (INTVAL (op), 'O', constraint))
1774             result = 1;
1775           break;
1776         case 'P':
1777           if (CONST_INT_P (op)
1778               && CONST_OK_FOR_CONSTRAINT_P (INTVAL (op), 'P', constraint))
1779             result = 1;
1780           break;
1781
1782         case 'X':
1783           result = 1;
1784           break;
1785
1786         case 'g':
1787           if (general_operand (op, VOIDmode))
1788             result = 1;
1789           break;
1790
1791         default:
1792           /* For all other letters, we first check for a register class,
1793              otherwise it is an EXTRA_CONSTRAINT.  */
1794           if (REG_CLASS_FROM_CONSTRAINT (c, constraint) != NO_REGS)
1795             {
1796             case 'r':
1797               if (GET_MODE (op) == BLKmode)
1798                 break;
1799               if (register_operand (op, VOIDmode))
1800                 result = 1;
1801             }
1802 #ifdef EXTRA_CONSTRAINT_STR
1803           else if (EXTRA_MEMORY_CONSTRAINT (c, constraint))
1804             /* Every memory operand can be reloaded to fit.  */
1805             result = result || memory_operand (op, VOIDmode);
1806           else if (EXTRA_ADDRESS_CONSTRAINT (c, constraint))
1807             /* Every address operand can be reloaded to fit.  */
1808             result = result || address_operand (op, VOIDmode);
1809           else if (EXTRA_CONSTRAINT_STR (op, c, constraint))
1810             result = 1;
1811 #endif
1812           break;
1813         }
1814       len = CONSTRAINT_LEN (c, constraint);
1815       do
1816         constraint++;
1817       while (--len && *constraint);
1818       if (len)
1819         return 0;
1820     }
1821
1822 #ifdef AUTO_INC_DEC
1823   /* For operands without < or > constraints reject side-effects.  */
1824   if (!incdec_ok && result && MEM_P (op))
1825     switch (GET_CODE (XEXP (op, 0)))
1826       {
1827       case PRE_INC:
1828       case POST_INC:
1829       case PRE_DEC:
1830       case POST_DEC:
1831       case PRE_MODIFY:
1832       case POST_MODIFY:
1833         return 0;
1834       default:
1835         break;
1836       }
1837 #endif
1838
1839   return result;
1840 }
1841 \f
1842 /* Given an rtx *P, if it is a sum containing an integer constant term,
1843    return the location (type rtx *) of the pointer to that constant term.
1844    Otherwise, return a null pointer.  */
1845
1846 rtx *
1847 find_constant_term_loc (rtx *p)
1848 {
1849   rtx *tem;
1850   enum rtx_code code = GET_CODE (*p);
1851
1852   /* If *P IS such a constant term, P is its location.  */
1853
1854   if (code == CONST_INT || code == SYMBOL_REF || code == LABEL_REF
1855       || code == CONST)
1856     return p;
1857
1858   /* Otherwise, if not a sum, it has no constant term.  */
1859
1860   if (GET_CODE (*p) != PLUS)
1861     return 0;
1862
1863   /* If one of the summands is constant, return its location.  */
1864
1865   if (XEXP (*p, 0) && CONSTANT_P (XEXP (*p, 0))
1866       && XEXP (*p, 1) && CONSTANT_P (XEXP (*p, 1)))
1867     return p;
1868
1869   /* Otherwise, check each summand for containing a constant term.  */
1870
1871   if (XEXP (*p, 0) != 0)
1872     {
1873       tem = find_constant_term_loc (&XEXP (*p, 0));
1874       if (tem != 0)
1875         return tem;
1876     }
1877
1878   if (XEXP (*p, 1) != 0)
1879     {
1880       tem = find_constant_term_loc (&XEXP (*p, 1));
1881       if (tem != 0)
1882         return tem;
1883     }
1884
1885   return 0;
1886 }
1887 \f
1888 /* Return 1 if OP is a memory reference
1889    whose address contains no side effects
1890    and remains valid after the addition
1891    of a positive integer less than the
1892    size of the object being referenced.
1893
1894    We assume that the original address is valid and do not check it.
1895
1896    This uses strict_memory_address_p as a subroutine, so
1897    don't use it before reload.  */
1898
1899 int
1900 offsettable_memref_p (rtx op)
1901 {
1902   return ((MEM_P (op))
1903           && offsettable_address_addr_space_p (1, GET_MODE (op), XEXP (op, 0),
1904                                                MEM_ADDR_SPACE (op)));
1905 }
1906
1907 /* Similar, but don't require a strictly valid mem ref:
1908    consider pseudo-regs valid as index or base regs.  */
1909
1910 int
1911 offsettable_nonstrict_memref_p (rtx op)
1912 {
1913   return ((MEM_P (op))
1914           && offsettable_address_addr_space_p (0, GET_MODE (op), XEXP (op, 0),
1915                                                MEM_ADDR_SPACE (op)));
1916 }
1917
1918 /* Return 1 if Y is a memory address which contains no side effects
1919    and would remain valid for address space AS after the addition of
1920    a positive integer less than the size of that mode.
1921
1922    We assume that the original address is valid and do not check it.
1923    We do check that it is valid for narrower modes.
1924
1925    If STRICTP is nonzero, we require a strictly valid address,
1926    for the sake of use in reload.c.  */
1927
1928 int
1929 offsettable_address_addr_space_p (int strictp, enum machine_mode mode, rtx y,
1930                                   addr_space_t as)
1931 {
1932   enum rtx_code ycode = GET_CODE (y);
1933   rtx z;
1934   rtx y1 = y;
1935   rtx *y2;
1936   int (*addressp) (enum machine_mode, rtx, addr_space_t) =
1937     (strictp ? strict_memory_address_addr_space_p
1938              : memory_address_addr_space_p);
1939   unsigned int mode_sz = GET_MODE_SIZE (mode);
1940
1941   if (CONSTANT_ADDRESS_P (y))
1942     return 1;
1943
1944   /* Adjusting an offsettable address involves changing to a narrower mode.
1945      Make sure that's OK.  */
1946
1947   if (mode_dependent_address_p (y))
1948     return 0;
1949
1950   /* ??? How much offset does an offsettable BLKmode reference need?
1951      Clearly that depends on the situation in which it's being used.
1952      However, the current situation in which we test 0xffffffff is
1953      less than ideal.  Caveat user.  */
1954   if (mode_sz == 0)
1955     mode_sz = BIGGEST_ALIGNMENT / BITS_PER_UNIT;
1956
1957   /* If the expression contains a constant term,
1958      see if it remains valid when max possible offset is added.  */
1959
1960   if ((ycode == PLUS) && (y2 = find_constant_term_loc (&y1)))
1961     {
1962       int good;
1963
1964       y1 = *y2;
1965       *y2 = plus_constant (*y2, mode_sz - 1);
1966       /* Use QImode because an odd displacement may be automatically invalid
1967          for any wider mode.  But it should be valid for a single byte.  */
1968       good = (*addressp) (QImode, y, as);
1969
1970       /* In any case, restore old contents of memory.  */
1971       *y2 = y1;
1972       return good;
1973     }
1974
1975   if (GET_RTX_CLASS (ycode) == RTX_AUTOINC)
1976     return 0;
1977
1978   /* The offset added here is chosen as the maximum offset that
1979      any instruction could need to add when operating on something
1980      of the specified mode.  We assume that if Y and Y+c are
1981      valid addresses then so is Y+d for all 0<d<c.  adjust_address will
1982      go inside a LO_SUM here, so we do so as well.  */
1983   if (GET_CODE (y) == LO_SUM
1984       && mode != BLKmode
1985       && mode_sz <= GET_MODE_ALIGNMENT (mode) / BITS_PER_UNIT)
1986     z = gen_rtx_LO_SUM (GET_MODE (y), XEXP (y, 0),
1987                         plus_constant (XEXP (y, 1), mode_sz - 1));
1988   else
1989     z = plus_constant (y, mode_sz - 1);
1990
1991   /* Use QImode because an odd displacement may be automatically invalid
1992      for any wider mode.  But it should be valid for a single byte.  */
1993   return (*addressp) (QImode, z, as);
1994 }
1995
1996 /* Return 1 if ADDR is an address-expression whose effect depends
1997    on the mode of the memory reference it is used in.
1998
1999    Autoincrement addressing is a typical example of mode-dependence
2000    because the amount of the increment depends on the mode.  */
2001
2002 bool
2003 mode_dependent_address_p (rtx addr)
2004 {
2005   /* Auto-increment addressing with anything other than post_modify
2006      or pre_modify always introduces a mode dependency.  Catch such
2007      cases now instead of deferring to the target.  */
2008   if (GET_CODE (addr) == PRE_INC
2009       || GET_CODE (addr) == POST_INC
2010       || GET_CODE (addr) == PRE_DEC
2011       || GET_CODE (addr) == POST_DEC)
2012     return true;
2013
2014   return targetm.mode_dependent_address_p (addr);
2015 }
2016 \f
2017 /* Like extract_insn, but save insn extracted and don't extract again, when
2018    called again for the same insn expecting that recog_data still contain the
2019    valid information.  This is used primary by gen_attr infrastructure that
2020    often does extract insn again and again.  */
2021 void
2022 extract_insn_cached (rtx insn)
2023 {
2024   if (recog_data.insn == insn && INSN_CODE (insn) >= 0)
2025     return;
2026   extract_insn (insn);
2027   recog_data.insn = insn;
2028 }
2029
2030 /* Do cached extract_insn, constrain_operands and complain about failures.
2031    Used by insn_attrtab.  */
2032 void
2033 extract_constrain_insn_cached (rtx insn)
2034 {
2035   extract_insn_cached (insn);
2036   if (which_alternative == -1
2037       && !constrain_operands (reload_completed))
2038     fatal_insn_not_found (insn);
2039 }
2040
2041 /* Do cached constrain_operands and complain about failures.  */
2042 int
2043 constrain_operands_cached (int strict)
2044 {
2045   if (which_alternative == -1)
2046     return constrain_operands (strict);
2047   else
2048     return 1;
2049 }
2050 \f
2051 /* Analyze INSN and fill in recog_data.  */
2052
2053 void
2054 extract_insn (rtx insn)
2055 {
2056   int i;
2057   int icode;
2058   int noperands;
2059   rtx body = PATTERN (insn);
2060
2061   recog_data.n_operands = 0;
2062   recog_data.n_alternatives = 0;
2063   recog_data.n_dups = 0;
2064   recog_data.is_asm = false;
2065
2066   switch (GET_CODE (body))
2067     {
2068     case USE:
2069     case CLOBBER:
2070     case ASM_INPUT:
2071     case ADDR_VEC:
2072     case ADDR_DIFF_VEC:
2073     case VAR_LOCATION:
2074       return;
2075
2076     case SET:
2077       if (GET_CODE (SET_SRC (body)) == ASM_OPERANDS)
2078         goto asm_insn;
2079       else
2080         goto normal_insn;
2081     case PARALLEL:
2082       if ((GET_CODE (XVECEXP (body, 0, 0)) == SET
2083            && GET_CODE (SET_SRC (XVECEXP (body, 0, 0))) == ASM_OPERANDS)
2084           || GET_CODE (XVECEXP (body, 0, 0)) == ASM_OPERANDS)
2085         goto asm_insn;
2086       else
2087         goto normal_insn;
2088     case ASM_OPERANDS:
2089     asm_insn:
2090       recog_data.n_operands = noperands = asm_noperands (body);
2091       if (noperands >= 0)
2092         {
2093           /* This insn is an `asm' with operands.  */
2094
2095           /* expand_asm_operands makes sure there aren't too many operands.  */
2096           gcc_assert (noperands <= MAX_RECOG_OPERANDS);
2097
2098           /* Now get the operand values and constraints out of the insn.  */
2099           decode_asm_operands (body, recog_data.operand,
2100                                recog_data.operand_loc,
2101                                recog_data.constraints,
2102                                recog_data.operand_mode, NULL);
2103           memset (recog_data.is_operator, 0, sizeof recog_data.is_operator);
2104           if (noperands > 0)
2105             {
2106               const char *p =  recog_data.constraints[0];
2107               recog_data.n_alternatives = 1;
2108               while (*p)
2109                 recog_data.n_alternatives += (*p++ == ',');
2110             }
2111           recog_data.is_asm = true;
2112           break;
2113         }
2114       fatal_insn_not_found (insn);
2115
2116     default:
2117     normal_insn:
2118       /* Ordinary insn: recognize it, get the operands via insn_extract
2119          and get the constraints.  */
2120
2121       icode = recog_memoized (insn);
2122       if (icode < 0)
2123         fatal_insn_not_found (insn);
2124
2125       recog_data.n_operands = noperands = insn_data[icode].n_operands;
2126       recog_data.n_alternatives = insn_data[icode].n_alternatives;
2127       recog_data.n_dups = insn_data[icode].n_dups;
2128
2129       insn_extract (insn);
2130
2131       for (i = 0; i < noperands; i++)
2132         {
2133           recog_data.constraints[i] = insn_data[icode].operand[i].constraint;
2134           recog_data.is_operator[i] = insn_data[icode].operand[i].is_operator;
2135           recog_data.operand_mode[i] = insn_data[icode].operand[i].mode;
2136           /* VOIDmode match_operands gets mode from their real operand.  */
2137           if (recog_data.operand_mode[i] == VOIDmode)
2138             recog_data.operand_mode[i] = GET_MODE (recog_data.operand[i]);
2139         }
2140     }
2141   for (i = 0; i < noperands; i++)
2142     recog_data.operand_type[i]
2143       = (recog_data.constraints[i][0] == '=' ? OP_OUT
2144          : recog_data.constraints[i][0] == '+' ? OP_INOUT
2145          : OP_IN);
2146
2147   gcc_assert (recog_data.n_alternatives <= MAX_RECOG_ALTERNATIVES);
2148
2149   if (INSN_CODE (insn) < 0)
2150     for (i = 0; i < recog_data.n_alternatives; i++)
2151       recog_data.alternative_enabled_p[i] = true;
2152   else
2153     {
2154       recog_data.insn = insn;
2155       for (i = 0; i < recog_data.n_alternatives; i++)
2156         {
2157           which_alternative = i;
2158           recog_data.alternative_enabled_p[i] = get_attr_enabled (insn);
2159         }
2160     }
2161
2162   recog_data.insn = NULL;
2163   which_alternative = -1;
2164 }
2165
2166 /* After calling extract_insn, you can use this function to extract some
2167    information from the constraint strings into a more usable form.
2168    The collected data is stored in recog_op_alt.  */
2169 void
2170 preprocess_constraints (void)
2171 {
2172   int i;
2173
2174   for (i = 0; i < recog_data.n_operands; i++)
2175     memset (recog_op_alt[i], 0, (recog_data.n_alternatives
2176                                  * sizeof (struct operand_alternative)));
2177
2178   for (i = 0; i < recog_data.n_operands; i++)
2179     {
2180       int j;
2181       struct operand_alternative *op_alt;
2182       const char *p = recog_data.constraints[i];
2183
2184       op_alt = recog_op_alt[i];
2185
2186       for (j = 0; j < recog_data.n_alternatives; j++)
2187         {
2188           op_alt[j].cl = NO_REGS;
2189           op_alt[j].constraint = p;
2190           op_alt[j].matches = -1;
2191           op_alt[j].matched = -1;
2192
2193           if (!recog_data.alternative_enabled_p[j])
2194             {
2195               p = skip_alternative (p);
2196               continue;
2197             }
2198
2199           if (*p == '\0' || *p == ',')
2200             {
2201               op_alt[j].anything_ok = 1;
2202               continue;
2203             }
2204
2205           for (;;)
2206             {
2207               char c = *p;
2208               if (c == '#')
2209                 do
2210                   c = *++p;
2211                 while (c != ',' && c != '\0');
2212               if (c == ',' || c == '\0')
2213                 {
2214                   p++;
2215                   break;
2216                 }
2217
2218               switch (c)
2219                 {
2220                 case '=': case '+': case '*': case '%':
2221                 case 'E': case 'F': case 'G': case 'H':
2222                 case 's': case 'i': case 'n':
2223                 case 'I': case 'J': case 'K': case 'L':
2224                 case 'M': case 'N': case 'O': case 'P':
2225                   /* These don't say anything we care about.  */
2226                   break;
2227
2228                 case '?':
2229                   op_alt[j].reject += 6;
2230                   break;
2231                 case '!':
2232                   op_alt[j].reject += 600;
2233                   break;
2234                 case '&':
2235                   op_alt[j].earlyclobber = 1;
2236                   break;
2237
2238                 case '0': case '1': case '2': case '3': case '4':
2239                 case '5': case '6': case '7': case '8': case '9':
2240                   {
2241                     char *end;
2242                     op_alt[j].matches = strtoul (p, &end, 10);
2243                     recog_op_alt[op_alt[j].matches][j].matched = i;
2244                     p = end;
2245                   }
2246                   continue;
2247
2248                 case TARGET_MEM_CONSTRAINT:
2249                   op_alt[j].memory_ok = 1;
2250                   break;
2251                 case '<':
2252                   op_alt[j].decmem_ok = 1;
2253                   break;
2254                 case '>':
2255                   op_alt[j].incmem_ok = 1;
2256                   break;
2257                 case 'V':
2258                   op_alt[j].nonoffmem_ok = 1;
2259                   break;
2260                 case 'o':
2261                   op_alt[j].offmem_ok = 1;
2262                   break;
2263                 case 'X':
2264                   op_alt[j].anything_ok = 1;
2265                   break;
2266
2267                 case 'p':
2268                   op_alt[j].is_address = 1;
2269                   op_alt[j].cl = reg_class_subunion[(int) op_alt[j].cl]
2270                       [(int) base_reg_class (VOIDmode, ADDR_SPACE_GENERIC,
2271                                              ADDRESS, SCRATCH)];
2272                   break;
2273
2274                 case 'g':
2275                 case 'r':
2276                   op_alt[j].cl =
2277                    reg_class_subunion[(int) op_alt[j].cl][(int) GENERAL_REGS];
2278                   break;
2279
2280                 default:
2281                   if (EXTRA_MEMORY_CONSTRAINT (c, p))
2282                     {
2283                       op_alt[j].memory_ok = 1;
2284                       break;
2285                     }
2286                   if (EXTRA_ADDRESS_CONSTRAINT (c, p))
2287                     {
2288                       op_alt[j].is_address = 1;
2289                       op_alt[j].cl
2290                         = (reg_class_subunion
2291                            [(int) op_alt[j].cl]
2292                            [(int) base_reg_class (VOIDmode, ADDR_SPACE_GENERIC,
2293                                                   ADDRESS, SCRATCH)]);
2294                       break;
2295                     }
2296
2297                   op_alt[j].cl
2298                     = (reg_class_subunion
2299                        [(int) op_alt[j].cl]
2300                        [(int) REG_CLASS_FROM_CONSTRAINT ((unsigned char) c, p)]);
2301                   break;
2302                 }
2303               p += CONSTRAINT_LEN (c, p);
2304             }
2305         }
2306     }
2307 }
2308
2309 /* Check the operands of an insn against the insn's operand constraints
2310    and return 1 if they are valid.
2311    The information about the insn's operands, constraints, operand modes
2312    etc. is obtained from the global variables set up by extract_insn.
2313
2314    WHICH_ALTERNATIVE is set to a number which indicates which
2315    alternative of constraints was matched: 0 for the first alternative,
2316    1 for the next, etc.
2317
2318    In addition, when two operands are required to match
2319    and it happens that the output operand is (reg) while the
2320    input operand is --(reg) or ++(reg) (a pre-inc or pre-dec),
2321    make the output operand look like the input.
2322    This is because the output operand is the one the template will print.
2323
2324    This is used in final, just before printing the assembler code and by
2325    the routines that determine an insn's attribute.
2326
2327    If STRICT is a positive nonzero value, it means that we have been
2328    called after reload has been completed.  In that case, we must
2329    do all checks strictly.  If it is zero, it means that we have been called
2330    before reload has completed.  In that case, we first try to see if we can
2331    find an alternative that matches strictly.  If not, we try again, this
2332    time assuming that reload will fix up the insn.  This provides a "best
2333    guess" for the alternative and is used to compute attributes of insns prior
2334    to reload.  A negative value of STRICT is used for this internal call.  */
2335
2336 struct funny_match
2337 {
2338   int this_op, other;
2339 };
2340
2341 int
2342 constrain_operands (int strict)
2343 {
2344   const char *constraints[MAX_RECOG_OPERANDS];
2345   int matching_operands[MAX_RECOG_OPERANDS];
2346   int earlyclobber[MAX_RECOG_OPERANDS];
2347   int c;
2348
2349   struct funny_match funny_match[MAX_RECOG_OPERANDS];
2350   int funny_match_index;
2351
2352   which_alternative = 0;
2353   if (recog_data.n_operands == 0 || recog_data.n_alternatives == 0)
2354     return 1;
2355
2356   for (c = 0; c < recog_data.n_operands; c++)
2357     {
2358       constraints[c] = recog_data.constraints[c];
2359       matching_operands[c] = -1;
2360     }
2361
2362   do
2363     {
2364       int seen_earlyclobber_at = -1;
2365       int opno;
2366       int lose = 0;
2367       funny_match_index = 0;
2368
2369       if (!recog_data.alternative_enabled_p[which_alternative])
2370         {
2371           int i;
2372
2373           for (i = 0; i < recog_data.n_operands; i++)
2374             constraints[i] = skip_alternative (constraints[i]);
2375
2376           which_alternative++;
2377           continue;
2378         }
2379
2380       for (opno = 0; opno < recog_data.n_operands; opno++)
2381         {
2382           rtx op = recog_data.operand[opno];
2383           enum machine_mode mode = GET_MODE (op);
2384           const char *p = constraints[opno];
2385           int offset = 0;
2386           int win = 0;
2387           int val;
2388           int len;
2389
2390           earlyclobber[opno] = 0;
2391
2392           /* A unary operator may be accepted by the predicate, but it
2393              is irrelevant for matching constraints.  */
2394           if (UNARY_P (op))
2395             op = XEXP (op, 0);
2396
2397           if (GET_CODE (op) == SUBREG)
2398             {
2399               if (REG_P (SUBREG_REG (op))
2400                   && REGNO (SUBREG_REG (op)) < FIRST_PSEUDO_REGISTER)
2401                 offset = subreg_regno_offset (REGNO (SUBREG_REG (op)),
2402                                               GET_MODE (SUBREG_REG (op)),
2403                                               SUBREG_BYTE (op),
2404                                               GET_MODE (op));
2405               op = SUBREG_REG (op);
2406             }
2407
2408           /* An empty constraint or empty alternative
2409              allows anything which matched the pattern.  */
2410           if (*p == 0 || *p == ',')
2411             win = 1;
2412
2413           do
2414             switch (c = *p, len = CONSTRAINT_LEN (c, p), c)
2415               {
2416               case '\0':
2417                 len = 0;
2418                 break;
2419               case ',':
2420                 c = '\0';
2421                 break;
2422
2423               case '?':  case '!': case '*':  case '%':
2424               case '=':  case '+':
2425                 break;
2426
2427               case '#':
2428                 /* Ignore rest of this alternative as far as
2429                    constraint checking is concerned.  */
2430                 do
2431                   p++;
2432                 while (*p && *p != ',');
2433                 len = 0;
2434                 break;
2435
2436               case '&':
2437                 earlyclobber[opno] = 1;
2438                 if (seen_earlyclobber_at < 0)
2439                   seen_earlyclobber_at = opno;
2440                 break;
2441
2442               case '0':  case '1':  case '2':  case '3':  case '4':
2443               case '5':  case '6':  case '7':  case '8':  case '9':
2444                 {
2445                   /* This operand must be the same as a previous one.
2446                      This kind of constraint is used for instructions such
2447                      as add when they take only two operands.
2448
2449                      Note that the lower-numbered operand is passed first.
2450
2451                      If we are not testing strictly, assume that this
2452                      constraint will be satisfied.  */
2453
2454                   char *end;
2455                   int match;
2456
2457                   match = strtoul (p, &end, 10);
2458                   p = end;
2459
2460                   if (strict < 0)
2461                     val = 1;
2462                   else
2463                     {
2464                       rtx op1 = recog_data.operand[match];
2465                       rtx op2 = recog_data.operand[opno];
2466
2467                       /* A unary operator may be accepted by the predicate,
2468                          but it is irrelevant for matching constraints.  */
2469                       if (UNARY_P (op1))
2470                         op1 = XEXP (op1, 0);
2471                       if (UNARY_P (op2))
2472                         op2 = XEXP (op2, 0);
2473
2474                       val = operands_match_p (op1, op2);
2475                     }
2476
2477                   matching_operands[opno] = match;
2478                   matching_operands[match] = opno;
2479
2480                   if (val != 0)
2481                     win = 1;
2482
2483                   /* If output is *x and input is *--x, arrange later
2484                      to change the output to *--x as well, since the
2485                      output op is the one that will be printed.  */
2486                   if (val == 2 && strict > 0)
2487                     {
2488                       funny_match[funny_match_index].this_op = opno;
2489                       funny_match[funny_match_index++].other = match;
2490                     }
2491                 }
2492                 len = 0;
2493                 break;
2494
2495               case 'p':
2496                 /* p is used for address_operands.  When we are called by
2497                    gen_reload, no one will have checked that the address is
2498                    strictly valid, i.e., that all pseudos requiring hard regs
2499                    have gotten them.  */
2500                 if (strict <= 0
2501                     || (strict_memory_address_p (recog_data.operand_mode[opno],
2502                                                  op)))
2503                   win = 1;
2504                 break;
2505
2506                 /* No need to check general_operand again;
2507                    it was done in insn-recog.c.  Well, except that reload
2508                    doesn't check the validity of its replacements, but
2509                    that should only matter when there's a bug.  */
2510               case 'g':
2511                 /* Anything goes unless it is a REG and really has a hard reg
2512                    but the hard reg is not in the class GENERAL_REGS.  */
2513                 if (REG_P (op))
2514                   {
2515                     if (strict < 0
2516                         || GENERAL_REGS == ALL_REGS
2517                         || (reload_in_progress
2518                             && REGNO (op) >= FIRST_PSEUDO_REGISTER)
2519                         || reg_fits_class_p (op, GENERAL_REGS, offset, mode))
2520                       win = 1;
2521                   }
2522                 else if (strict < 0 || general_operand (op, mode))
2523                   win = 1;
2524                 break;
2525
2526               case 'X':
2527                 /* This is used for a MATCH_SCRATCH in the cases when
2528                    we don't actually need anything.  So anything goes
2529                    any time.  */
2530                 win = 1;
2531                 break;
2532
2533               case TARGET_MEM_CONSTRAINT:
2534                 /* Memory operands must be valid, to the extent
2535                    required by STRICT.  */
2536                 if (MEM_P (op))
2537                   {
2538                     if (strict > 0
2539                         && !strict_memory_address_addr_space_p
2540                              (GET_MODE (op), XEXP (op, 0),
2541                               MEM_ADDR_SPACE (op)))
2542                       break;
2543                     if (strict == 0
2544                         && !memory_address_addr_space_p
2545                              (GET_MODE (op), XEXP (op, 0),
2546                               MEM_ADDR_SPACE (op)))
2547                       break;
2548                     win = 1;
2549                   }
2550                 /* Before reload, accept what reload can turn into mem.  */
2551                 else if (strict < 0 && CONSTANT_P (op))
2552                   win = 1;
2553                 /* During reload, accept a pseudo  */
2554                 else if (reload_in_progress && REG_P (op)
2555                          && REGNO (op) >= FIRST_PSEUDO_REGISTER)
2556                   win = 1;
2557                 break;
2558
2559               case '<':
2560                 if (MEM_P (op)
2561                     && (GET_CODE (XEXP (op, 0)) == PRE_DEC
2562                         || GET_CODE (XEXP (op, 0)) == POST_DEC))
2563                   win = 1;
2564                 break;
2565
2566               case '>':
2567                 if (MEM_P (op)
2568                     && (GET_CODE (XEXP (op, 0)) == PRE_INC
2569                         || GET_CODE (XEXP (op, 0)) == POST_INC))
2570                   win = 1;
2571                 break;
2572
2573               case 'E':
2574               case 'F':
2575                 if (GET_CODE (op) == CONST_DOUBLE
2576                     || (GET_CODE (op) == CONST_VECTOR
2577                         && GET_MODE_CLASS (GET_MODE (op)) == MODE_VECTOR_FLOAT))
2578                   win = 1;
2579                 break;
2580
2581               case 'G':
2582               case 'H':
2583                 if (GET_CODE (op) == CONST_DOUBLE
2584                     && CONST_DOUBLE_OK_FOR_CONSTRAINT_P (op, c, p))
2585                   win = 1;
2586                 break;
2587
2588               case 's':
2589                 if (CONST_INT_P (op)
2590                     || (GET_CODE (op) == CONST_DOUBLE
2591                         && GET_MODE (op) == VOIDmode))
2592                   break;
2593               case 'i':
2594                 if (CONSTANT_P (op))
2595                   win = 1;
2596                 break;
2597
2598               case 'n':
2599                 if (CONST_INT_P (op)
2600                     || (GET_CODE (op) == CONST_DOUBLE
2601                         && GET_MODE (op) == VOIDmode))
2602                   win = 1;
2603                 break;
2604
2605               case 'I':
2606               case 'J':
2607               case 'K':
2608               case 'L':
2609               case 'M':
2610               case 'N':
2611               case 'O':
2612               case 'P':
2613                 if (CONST_INT_P (op)
2614                     && CONST_OK_FOR_CONSTRAINT_P (INTVAL (op), c, p))
2615                   win = 1;
2616                 break;
2617
2618               case 'V':
2619                 if (MEM_P (op)
2620                     && ((strict > 0 && ! offsettable_memref_p (op))
2621                         || (strict < 0
2622                             && !(CONSTANT_P (op) || MEM_P (op)))
2623                         || (reload_in_progress
2624                             && !(REG_P (op)
2625                                  && REGNO (op) >= FIRST_PSEUDO_REGISTER))))
2626                   win = 1;
2627                 break;
2628
2629               case 'o':
2630                 if ((strict > 0 && offsettable_memref_p (op))
2631                     || (strict == 0 && offsettable_nonstrict_memref_p (op))
2632                     /* Before reload, accept what reload can handle.  */
2633                     || (strict < 0
2634                         && (CONSTANT_P (op) || MEM_P (op)))
2635                     /* During reload, accept a pseudo  */
2636                     || (reload_in_progress && REG_P (op)
2637                         && REGNO (op) >= FIRST_PSEUDO_REGISTER))
2638                   win = 1;
2639                 break;
2640
2641               default:
2642                 {
2643                   enum reg_class cl;
2644
2645                   cl = (c == 'r'
2646                            ? GENERAL_REGS : REG_CLASS_FROM_CONSTRAINT (c, p));
2647                   if (cl != NO_REGS)
2648                     {
2649                       if (strict < 0
2650                           || (strict == 0
2651                               && REG_P (op)
2652                               && REGNO (op) >= FIRST_PSEUDO_REGISTER)
2653                           || (strict == 0 && GET_CODE (op) == SCRATCH)
2654                           || (REG_P (op)
2655                               && reg_fits_class_p (op, cl, offset, mode)))
2656                         win = 1;
2657                     }
2658 #ifdef EXTRA_CONSTRAINT_STR
2659                   else if (EXTRA_CONSTRAINT_STR (op, c, p))
2660                     win = 1;
2661
2662                   else if (EXTRA_MEMORY_CONSTRAINT (c, p)
2663                            /* Every memory operand can be reloaded to fit.  */
2664                            && ((strict < 0 && MEM_P (op))
2665                                /* Before reload, accept what reload can turn
2666                                   into mem.  */
2667                                || (strict < 0 && CONSTANT_P (op))
2668                                /* During reload, accept a pseudo  */
2669                                || (reload_in_progress && REG_P (op)
2670                                    && REGNO (op) >= FIRST_PSEUDO_REGISTER)))
2671                     win = 1;
2672                   else if (EXTRA_ADDRESS_CONSTRAINT (c, p)
2673                            /* Every address operand can be reloaded to fit.  */
2674                            && strict < 0)
2675                     win = 1;
2676                   /* Cater to architectures like IA-64 that define extra memory
2677                      constraints without using define_memory_constraint.  */
2678                   else if (reload_in_progress
2679                            && REG_P (op)
2680                            && REGNO (op) >= FIRST_PSEUDO_REGISTER
2681                            && reg_renumber[REGNO (op)] < 0
2682                            && reg_equiv_mem (REGNO (op)) != 0
2683                            && EXTRA_CONSTRAINT_STR
2684                               (reg_equiv_mem (REGNO (op)), c, p))
2685                     win = 1;
2686 #endif
2687                   break;
2688                 }
2689               }
2690           while (p += len, c);
2691
2692           constraints[opno] = p;
2693           /* If this operand did not win somehow,
2694              this alternative loses.  */
2695           if (! win)
2696             lose = 1;
2697         }
2698       /* This alternative won; the operands are ok.
2699          Change whichever operands this alternative says to change.  */
2700       if (! lose)
2701         {
2702           int opno, eopno;
2703
2704           /* See if any earlyclobber operand conflicts with some other
2705              operand.  */
2706
2707           if (strict > 0  && seen_earlyclobber_at >= 0)
2708             for (eopno = seen_earlyclobber_at;
2709                  eopno < recog_data.n_operands;
2710                  eopno++)
2711               /* Ignore earlyclobber operands now in memory,
2712                  because we would often report failure when we have
2713                  two memory operands, one of which was formerly a REG.  */
2714               if (earlyclobber[eopno]
2715                   && REG_P (recog_data.operand[eopno]))
2716                 for (opno = 0; opno < recog_data.n_operands; opno++)
2717                   if ((MEM_P (recog_data.operand[opno])
2718                        || recog_data.operand_type[opno] != OP_OUT)
2719                       && opno != eopno
2720                       /* Ignore things like match_operator operands.  */
2721                       && *recog_data.constraints[opno] != 0
2722                       && ! (matching_operands[opno] == eopno
2723                             && operands_match_p (recog_data.operand[opno],
2724                                                  recog_data.operand[eopno]))
2725                       && ! safe_from_earlyclobber (recog_data.operand[opno],
2726                                                    recog_data.operand[eopno]))
2727                     lose = 1;
2728
2729           if (! lose)
2730             {
2731               while (--funny_match_index >= 0)
2732                 {
2733                   recog_data.operand[funny_match[funny_match_index].other]
2734                     = recog_data.operand[funny_match[funny_match_index].this_op];
2735                 }
2736
2737 #ifdef AUTO_INC_DEC
2738               /* For operands without < or > constraints reject side-effects.  */
2739               if (recog_data.is_asm)
2740                 {
2741                   for (opno = 0; opno < recog_data.n_operands; opno++)
2742                     if (MEM_P (recog_data.operand[opno]))
2743                       switch (GET_CODE (XEXP (recog_data.operand[opno], 0)))
2744                         {
2745                         case PRE_INC:
2746                         case POST_INC:
2747                         case PRE_DEC:
2748                         case POST_DEC:
2749                         case PRE_MODIFY:
2750                         case POST_MODIFY:
2751                           if (strchr (recog_data.constraints[opno], '<') == NULL
2752                               && strchr (recog_data.constraints[opno], '>')
2753                                  == NULL)
2754                             return 0;
2755                           break;
2756                         default:
2757                           break;
2758                         }
2759                 }
2760 #endif
2761               return 1;
2762             }
2763         }
2764
2765       which_alternative++;
2766     }
2767   while (which_alternative < recog_data.n_alternatives);
2768
2769   which_alternative = -1;
2770   /* If we are about to reject this, but we are not to test strictly,
2771      try a very loose test.  Only return failure if it fails also.  */
2772   if (strict == 0)
2773     return constrain_operands (-1);
2774   else
2775     return 0;
2776 }
2777
2778 /* Return true iff OPERAND (assumed to be a REG rtx)
2779    is a hard reg in class CLASS when its regno is offset by OFFSET
2780    and changed to mode MODE.
2781    If REG occupies multiple hard regs, all of them must be in CLASS.  */
2782
2783 bool
2784 reg_fits_class_p (const_rtx operand, reg_class_t cl, int offset,
2785                   enum machine_mode mode)
2786 {
2787   int regno = REGNO (operand);
2788
2789   if (cl == NO_REGS)
2790     return false;
2791
2792   return (HARD_REGISTER_NUM_P (regno)
2793           && in_hard_reg_set_p (reg_class_contents[(int) cl],
2794                                 mode, regno + offset));
2795 }
2796 \f
2797 /* Split single instruction.  Helper function for split_all_insns and
2798    split_all_insns_noflow.  Return last insn in the sequence if successful,
2799    or NULL if unsuccessful.  */
2800
2801 static rtx
2802 split_insn (rtx insn)
2803 {
2804   /* Split insns here to get max fine-grain parallelism.  */
2805   rtx first = PREV_INSN (insn);
2806   rtx last = try_split (PATTERN (insn), insn, 1);
2807   rtx insn_set, last_set, note;
2808
2809   if (last == insn)
2810     return NULL_RTX;
2811
2812   /* If the original instruction was a single set that was known to be
2813      equivalent to a constant, see if we can say the same about the last
2814      instruction in the split sequence.  The two instructions must set
2815      the same destination.  */
2816   insn_set = single_set (insn);
2817   if (insn_set)
2818     {
2819       last_set = single_set (last);
2820       if (last_set && rtx_equal_p (SET_DEST (last_set), SET_DEST (insn_set)))
2821         {
2822           note = find_reg_equal_equiv_note (insn);
2823           if (note && CONSTANT_P (XEXP (note, 0)))
2824             set_unique_reg_note (last, REG_EQUAL, XEXP (note, 0));
2825           else if (CONSTANT_P (SET_SRC (insn_set)))
2826             set_unique_reg_note (last, REG_EQUAL, SET_SRC (insn_set));
2827         }
2828     }
2829
2830   /* try_split returns the NOTE that INSN became.  */
2831   SET_INSN_DELETED (insn);
2832
2833   /* ??? Coddle to md files that generate subregs in post-reload
2834      splitters instead of computing the proper hard register.  */
2835   if (reload_completed && first != last)
2836     {
2837       first = NEXT_INSN (first);
2838       for (;;)
2839         {
2840           if (INSN_P (first))
2841             cleanup_subreg_operands (first);
2842           if (first == last)
2843             break;
2844           first = NEXT_INSN (first);
2845         }
2846     }
2847
2848   return last;
2849 }
2850
2851 /* Split all insns in the function.  If UPD_LIFE, update life info after.  */
2852
2853 void
2854 split_all_insns (void)
2855 {
2856   sbitmap blocks;
2857   bool changed;
2858   basic_block bb;
2859
2860   blocks = sbitmap_alloc (last_basic_block);
2861   sbitmap_zero (blocks);
2862   changed = false;
2863
2864   FOR_EACH_BB_REVERSE (bb)
2865     {
2866       rtx insn, next;
2867       bool finish = false;
2868
2869       rtl_profile_for_bb (bb);
2870       for (insn = BB_HEAD (bb); !finish ; insn = next)
2871         {
2872           /* Can't use `next_real_insn' because that might go across
2873              CODE_LABELS and short-out basic blocks.  */
2874           next = NEXT_INSN (insn);
2875           finish = (insn == BB_END (bb));
2876           if (INSN_P (insn))
2877             {
2878               rtx set = single_set (insn);
2879
2880               /* Don't split no-op move insns.  These should silently
2881                  disappear later in final.  Splitting such insns would
2882                  break the code that handles LIBCALL blocks.  */
2883               if (set && set_noop_p (set))
2884                 {
2885                   /* Nops get in the way while scheduling, so delete them
2886                      now if register allocation has already been done.  It
2887                      is too risky to try to do this before register
2888                      allocation, and there are unlikely to be very many
2889                      nops then anyways.  */
2890                   if (reload_completed)
2891                       delete_insn_and_edges (insn);
2892                 }
2893               else
2894                 {
2895                   if (split_insn (insn))
2896                     {
2897                       SET_BIT (blocks, bb->index);
2898                       changed = true;
2899                     }
2900                 }
2901             }
2902         }
2903     }
2904
2905   default_rtl_profile ();
2906   if (changed)
2907     find_many_sub_basic_blocks (blocks);
2908
2909 #ifdef ENABLE_CHECKING
2910   verify_flow_info ();
2911 #endif
2912
2913   sbitmap_free (blocks);
2914 }
2915
2916 /* Same as split_all_insns, but do not expect CFG to be available.
2917    Used by machine dependent reorg passes.  */
2918
2919 unsigned int
2920 split_all_insns_noflow (void)
2921 {
2922   rtx next, insn;
2923
2924   for (insn = get_insns (); insn; insn = next)
2925     {
2926       next = NEXT_INSN (insn);
2927       if (INSN_P (insn))
2928         {
2929           /* Don't split no-op move insns.  These should silently
2930              disappear later in final.  Splitting such insns would
2931              break the code that handles LIBCALL blocks.  */
2932           rtx set = single_set (insn);
2933           if (set && set_noop_p (set))
2934             {
2935               /* Nops get in the way while scheduling, so delete them
2936                  now if register allocation has already been done.  It
2937                  is too risky to try to do this before register
2938                  allocation, and there are unlikely to be very many
2939                  nops then anyways.
2940
2941                  ??? Should we use delete_insn when the CFG isn't valid?  */
2942               if (reload_completed)
2943                 delete_insn_and_edges (insn);
2944             }
2945           else
2946             split_insn (insn);
2947         }
2948     }
2949   return 0;
2950 }
2951 \f
2952 #ifdef HAVE_peephole2
2953 struct peep2_insn_data
2954 {
2955   rtx insn;
2956   regset live_before;
2957 };
2958
2959 static struct peep2_insn_data peep2_insn_data[MAX_INSNS_PER_PEEP2 + 1];
2960 static int peep2_current;
2961
2962 static bool peep2_do_rebuild_jump_labels;
2963 static bool peep2_do_cleanup_cfg;
2964
2965 /* The number of instructions available to match a peep2.  */
2966 int peep2_current_count;
2967
2968 /* A non-insn marker indicating the last insn of the block.
2969    The live_before regset for this element is correct, indicating
2970    DF_LIVE_OUT for the block.  */
2971 #define PEEP2_EOB       pc_rtx
2972
2973 /* Wrap N to fit into the peep2_insn_data buffer.  */
2974
2975 static int
2976 peep2_buf_position (int n)
2977 {
2978   if (n >= MAX_INSNS_PER_PEEP2 + 1)
2979     n -= MAX_INSNS_PER_PEEP2 + 1;
2980   return n;
2981 }
2982
2983 /* Return the Nth non-note insn after `current', or return NULL_RTX if it
2984    does not exist.  Used by the recognizer to find the next insn to match
2985    in a multi-insn pattern.  */
2986
2987 rtx
2988 peep2_next_insn (int n)
2989 {
2990   gcc_assert (n <= peep2_current_count);
2991
2992   n = peep2_buf_position (peep2_current + n);
2993
2994   return peep2_insn_data[n].insn;
2995 }
2996
2997 /* Return true if REGNO is dead before the Nth non-note insn
2998    after `current'.  */
2999
3000 int
3001 peep2_regno_dead_p (int ofs, int regno)
3002 {
3003   gcc_assert (ofs < MAX_INSNS_PER_PEEP2 + 1);
3004
3005   ofs = peep2_buf_position (peep2_current + ofs);
3006
3007   gcc_assert (peep2_insn_data[ofs].insn != NULL_RTX);
3008
3009   return ! REGNO_REG_SET_P (peep2_insn_data[ofs].live_before, regno);
3010 }
3011
3012 /* Similarly for a REG.  */
3013
3014 int
3015 peep2_reg_dead_p (int ofs, rtx reg)
3016 {
3017   int regno, n;
3018
3019   gcc_assert (ofs < MAX_INSNS_PER_PEEP2 + 1);
3020
3021   ofs = peep2_buf_position (peep2_current + ofs);
3022
3023   gcc_assert (peep2_insn_data[ofs].insn != NULL_RTX);
3024
3025   regno = REGNO (reg);
3026   n = hard_regno_nregs[regno][GET_MODE (reg)];
3027   while (--n >= 0)
3028     if (REGNO_REG_SET_P (peep2_insn_data[ofs].live_before, regno + n))
3029       return 0;
3030   return 1;
3031 }
3032
3033 /* Regno offset to be used in the register search.  */
3034 static int search_ofs;
3035
3036 /* Try to find a hard register of mode MODE, matching the register class in
3037    CLASS_STR, which is available at the beginning of insn CURRENT_INSN and
3038    remains available until the end of LAST_INSN.  LAST_INSN may be NULL_RTX,
3039    in which case the only condition is that the register must be available
3040    before CURRENT_INSN.
3041    Registers that already have bits set in REG_SET will not be considered.
3042
3043    If an appropriate register is available, it will be returned and the
3044    corresponding bit(s) in REG_SET will be set; otherwise, NULL_RTX is
3045    returned.  */
3046
3047 rtx
3048 peep2_find_free_register (int from, int to, const char *class_str,
3049                           enum machine_mode mode, HARD_REG_SET *reg_set)
3050 {
3051   enum reg_class cl;
3052   HARD_REG_SET live;
3053   df_ref *def_rec;
3054   int i;
3055
3056   gcc_assert (from < MAX_INSNS_PER_PEEP2 + 1);
3057   gcc_assert (to < MAX_INSNS_PER_PEEP2 + 1);
3058
3059   from = peep2_buf_position (peep2_current + from);
3060   to = peep2_buf_position (peep2_current + to);
3061
3062   gcc_assert (peep2_insn_data[from].insn != NULL_RTX);
3063   REG_SET_TO_HARD_REG_SET (live, peep2_insn_data[from].live_before);
3064
3065   while (from != to)
3066     {
3067       gcc_assert (peep2_insn_data[from].insn != NULL_RTX);
3068
3069       /* Don't use registers set or clobbered by the insn.  */
3070       for (def_rec = DF_INSN_DEFS (peep2_insn_data[from].insn);
3071            *def_rec; def_rec++)
3072         SET_HARD_REG_BIT (live, DF_REF_REGNO (*def_rec));
3073
3074       from = peep2_buf_position (from + 1);
3075     }
3076
3077   cl = (class_str[0] == 'r' ? GENERAL_REGS
3078            : REG_CLASS_FROM_CONSTRAINT (class_str[0], class_str));
3079
3080   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3081     {
3082       int raw_regno, regno, success, j;
3083
3084       /* Distribute the free registers as much as possible.  */
3085       raw_regno = search_ofs + i;
3086       if (raw_regno >= FIRST_PSEUDO_REGISTER)
3087         raw_regno -= FIRST_PSEUDO_REGISTER;
3088 #ifdef REG_ALLOC_ORDER
3089       regno = reg_alloc_order[raw_regno];
3090 #else
3091       regno = raw_regno;
3092 #endif
3093
3094       /* Don't allocate fixed registers.  */
3095       if (fixed_regs[regno])
3096         continue;
3097       /* Don't allocate global registers.  */
3098       if (global_regs[regno])
3099         continue;
3100       /* Make sure the register is of the right class.  */
3101       if (! TEST_HARD_REG_BIT (reg_class_contents[cl], regno))
3102         continue;
3103       /* And can support the mode we need.  */
3104       if (! HARD_REGNO_MODE_OK (regno, mode))
3105         continue;
3106       /* And that we don't create an extra save/restore.  */
3107       if (! call_used_regs[regno] && ! df_regs_ever_live_p (regno))
3108         continue;
3109       if (! targetm.hard_regno_scratch_ok (regno))
3110         continue;
3111
3112       /* And we don't clobber traceback for noreturn functions.  */
3113       if ((regno == FRAME_POINTER_REGNUM || regno == HARD_FRAME_POINTER_REGNUM)
3114           && (! reload_completed || frame_pointer_needed))
3115         continue;
3116
3117       success = 1;
3118       for (j = hard_regno_nregs[regno][mode] - 1; j >= 0; j--)
3119         {
3120           if (TEST_HARD_REG_BIT (*reg_set, regno + j)
3121               || TEST_HARD_REG_BIT (live, regno + j))
3122             {
3123               success = 0;
3124               break;
3125             }
3126         }
3127       if (success)
3128         {
3129           add_to_hard_reg_set (reg_set, mode, regno);
3130
3131           /* Start the next search with the next register.  */
3132           if (++raw_regno >= FIRST_PSEUDO_REGISTER)
3133             raw_regno = 0;
3134           search_ofs = raw_regno;
3135
3136           return gen_rtx_REG (mode, regno);
3137         }
3138     }
3139
3140   search_ofs = 0;
3141   return NULL_RTX;
3142 }
3143
3144 /* Forget all currently tracked instructions, only remember current
3145    LIVE regset.  */
3146
3147 static void
3148 peep2_reinit_state (regset live)
3149 {
3150   int i;
3151
3152   /* Indicate that all slots except the last holds invalid data.  */
3153   for (i = 0; i < MAX_INSNS_PER_PEEP2; ++i)
3154     peep2_insn_data[i].insn = NULL_RTX;
3155   peep2_current_count = 0;
3156
3157   /* Indicate that the last slot contains live_after data.  */
3158   peep2_insn_data[MAX_INSNS_PER_PEEP2].insn = PEEP2_EOB;
3159   peep2_current = MAX_INSNS_PER_PEEP2;
3160
3161   COPY_REG_SET (peep2_insn_data[MAX_INSNS_PER_PEEP2].live_before, live);
3162 }
3163
3164 /* While scanning basic block BB, we found a match of length MATCH_LEN,
3165    starting at INSN.  Perform the replacement, removing the old insns and
3166    replacing them with ATTEMPT.  Returns the last insn emitted, or NULL
3167    if the replacement is rejected.  */
3168
3169 static rtx
3170 peep2_attempt (basic_block bb, rtx insn, int match_len, rtx attempt)
3171 {
3172   int i;
3173   rtx last, eh_note, as_note, before_try, x;
3174   rtx old_insn, new_insn;
3175   bool was_call = false;
3176
3177   /* If we are splitting an RTX_FRAME_RELATED_P insn, do not allow it to
3178      match more than one insn, or to be split into more than one insn.  */
3179   old_insn = peep2_insn_data[peep2_current].insn;
3180   if (RTX_FRAME_RELATED_P (old_insn))
3181     {
3182       bool any_note = false;
3183       rtx note;
3184
3185       if (match_len != 0)
3186         return NULL;
3187
3188       /* Look for one "active" insn.  I.e. ignore any "clobber" insns that
3189          may be in the stream for the purpose of register allocation.  */
3190       if (active_insn_p (attempt))
3191         new_insn = attempt;
3192       else
3193         new_insn = next_active_insn (attempt);
3194       if (next_active_insn (new_insn))
3195         return NULL;
3196
3197       /* We have a 1-1 replacement.  Copy over any frame-related info.  */
3198       RTX_FRAME_RELATED_P (new_insn) = 1;
3199
3200       /* Allow the backend to fill in a note during the split.  */
3201       for (note = REG_NOTES (new_insn); note ; note = XEXP (note, 1))
3202         switch (REG_NOTE_KIND (note))
3203           {
3204           case REG_FRAME_RELATED_EXPR:
3205           case REG_CFA_DEF_CFA:
3206           case REG_CFA_ADJUST_CFA:
3207           case REG_CFA_OFFSET:
3208           case REG_CFA_REGISTER:
3209           case REG_CFA_EXPRESSION:
3210           case REG_CFA_RESTORE:
3211           case REG_CFA_SET_VDRAP:
3212             any_note = true;
3213             break;
3214           default:
3215             break;
3216           }
3217
3218       /* If the backend didn't supply a note, copy one over.  */
3219       if (!any_note)
3220         for (note = REG_NOTES (old_insn); note ; note = XEXP (note, 1))
3221           switch (REG_NOTE_KIND (note))
3222             {
3223             case REG_FRAME_RELATED_EXPR:
3224             case REG_CFA_DEF_CFA:
3225             case REG_CFA_ADJUST_CFA:
3226             case REG_CFA_OFFSET:
3227             case REG_CFA_REGISTER:
3228             case REG_CFA_EXPRESSION:
3229             case REG_CFA_RESTORE:
3230             case REG_CFA_SET_VDRAP:
3231               add_reg_note (new_insn, REG_NOTE_KIND (note), XEXP (note, 0));
3232               any_note = true;
3233               break;
3234             default:
3235               break;
3236             }
3237
3238       /* If there still isn't a note, make sure the unwind info sees the
3239          same expression as before the split.  */
3240       if (!any_note)
3241         {
3242           rtx old_set, new_set;
3243
3244           /* The old insn had better have been simple, or annotated.  */
3245           old_set = single_set (old_insn);
3246           gcc_assert (old_set != NULL);
3247
3248           new_set = single_set (new_insn);
3249           if (!new_set || !rtx_equal_p (new_set, old_set))
3250             add_reg_note (new_insn, REG_FRAME_RELATED_EXPR, old_set);
3251         }
3252
3253       /* Copy prologue/epilogue status.  This is required in order to keep
3254          proper placement of EPILOGUE_BEG and the DW_CFA_remember_state.  */
3255       maybe_copy_prologue_epilogue_insn (old_insn, new_insn);
3256     }
3257
3258   /* If we are splitting a CALL_INSN, look for the CALL_INSN
3259      in SEQ and copy our CALL_INSN_FUNCTION_USAGE and other
3260      cfg-related call notes.  */
3261   for (i = 0; i <= match_len; ++i)
3262     {
3263       int j;
3264       rtx note;
3265
3266       j = peep2_buf_position (peep2_current + i);
3267       old_insn = peep2_insn_data[j].insn;
3268       if (!CALL_P (old_insn))
3269         continue;
3270       was_call = true;
3271
3272       new_insn = attempt;
3273       while (new_insn != NULL_RTX)
3274         {
3275           if (CALL_P (new_insn))
3276             break;
3277           new_insn = NEXT_INSN (new_insn);
3278         }
3279
3280       gcc_assert (new_insn != NULL_RTX);
3281
3282       CALL_INSN_FUNCTION_USAGE (new_insn)
3283         = CALL_INSN_FUNCTION_USAGE (old_insn);
3284
3285       for (note = REG_NOTES (old_insn);
3286            note;
3287            note = XEXP (note, 1))
3288         switch (REG_NOTE_KIND (note))
3289           {
3290           case REG_NORETURN:
3291           case REG_SETJMP:
3292           case REG_TM:
3293             add_reg_note (new_insn, REG_NOTE_KIND (note),
3294                           XEXP (note, 0));
3295             break;
3296           default:
3297             /* Discard all other reg notes.  */
3298             break;
3299           }
3300
3301       /* Croak if there is another call in the sequence.  */
3302       while (++i <= match_len)
3303         {
3304           j = peep2_buf_position (peep2_current + i);
3305           old_insn = peep2_insn_data[j].insn;
3306           gcc_assert (!CALL_P (old_insn));
3307         }
3308       break;
3309     }
3310
3311   /* If we matched any instruction that had a REG_ARGS_SIZE, then
3312      move those notes over to the new sequence.  */
3313   as_note = NULL;
3314   for (i = match_len; i >= 0; --i)
3315     {
3316       int j = peep2_buf_position (peep2_current + i);
3317       old_insn = peep2_insn_data[j].insn;
3318
3319       as_note = find_reg_note (old_insn, REG_ARGS_SIZE, NULL);
3320       if (as_note)
3321         break;
3322     }
3323
3324   i = peep2_buf_position (peep2_current + match_len);
3325   eh_note = find_reg_note (peep2_insn_data[i].insn, REG_EH_REGION, NULL_RTX);
3326
3327   /* Replace the old sequence with the new.  */
3328   last = emit_insn_after_setloc (attempt,
3329                                  peep2_insn_data[i].insn,
3330                                  INSN_LOCATOR (peep2_insn_data[i].insn));
3331   before_try = PREV_INSN (insn);
3332   delete_insn_chain (insn, peep2_insn_data[i].insn, false);
3333
3334   /* Re-insert the EH_REGION notes.  */
3335   if (eh_note || (was_call && nonlocal_goto_handler_labels))
3336     {
3337       edge eh_edge;
3338       edge_iterator ei;
3339
3340       FOR_EACH_EDGE (eh_edge, ei, bb->succs)
3341         if (eh_edge->flags & (EDGE_EH | EDGE_ABNORMAL_CALL))
3342           break;
3343
3344       if (eh_note)
3345         copy_reg_eh_region_note_backward (eh_note, last, before_try);
3346
3347       if (eh_edge)
3348         for (x = last; x != before_try; x = PREV_INSN (x))
3349           if (x != BB_END (bb)
3350               && (can_throw_internal (x)
3351                   || can_nonlocal_goto (x)))
3352             {
3353               edge nfte, nehe;
3354               int flags;
3355
3356               nfte = split_block (bb, x);
3357               flags = (eh_edge->flags
3358                        & (EDGE_EH | EDGE_ABNORMAL));
3359               if (CALL_P (x))
3360                 flags |= EDGE_ABNORMAL_CALL;
3361               nehe = make_edge (nfte->src, eh_edge->dest,
3362                                 flags);
3363
3364               nehe->probability = eh_edge->probability;
3365               nfte->probability
3366                 = REG_BR_PROB_BASE - nehe->probability;
3367
3368               peep2_do_cleanup_cfg |= purge_dead_edges (nfte->dest);
3369               bb = nfte->src;
3370               eh_edge = nehe;
3371             }
3372
3373       /* Converting possibly trapping insn to non-trapping is
3374          possible.  Zap dummy outgoing edges.  */
3375       peep2_do_cleanup_cfg |= purge_dead_edges (bb);
3376     }
3377
3378   /* Re-insert the ARGS_SIZE notes.  */
3379   if (as_note)
3380     fixup_args_size_notes (before_try, last, INTVAL (XEXP (as_note, 0)));
3381
3382   /* If we generated a jump instruction, it won't have
3383      JUMP_LABEL set.  Recompute after we're done.  */
3384   for (x = last; x != before_try; x = PREV_INSN (x))
3385     if (JUMP_P (x))
3386       {
3387         peep2_do_rebuild_jump_labels = true;
3388         break;
3389       }
3390
3391   return last;
3392 }
3393
3394 /* After performing a replacement in basic block BB, fix up the life
3395    information in our buffer.  LAST is the last of the insns that we
3396    emitted as a replacement.  PREV is the insn before the start of
3397    the replacement.  MATCH_LEN is the number of instructions that were
3398    matched, and which now need to be replaced in the buffer.  */
3399
3400 static void
3401 peep2_update_life (basic_block bb, int match_len, rtx last, rtx prev)
3402 {
3403   int i = peep2_buf_position (peep2_current + match_len + 1);
3404   rtx x;
3405   regset_head live;
3406
3407   INIT_REG_SET (&live);
3408   COPY_REG_SET (&live, peep2_insn_data[i].live_before);
3409
3410   gcc_assert (peep2_current_count >= match_len + 1);
3411   peep2_current_count -= match_len + 1;
3412
3413   x = last;
3414   do
3415     {
3416       if (INSN_P (x))
3417         {
3418           df_insn_rescan (x);
3419           if (peep2_current_count < MAX_INSNS_PER_PEEP2)
3420             {
3421               peep2_current_count++;
3422               if (--i < 0)
3423                 i = MAX_INSNS_PER_PEEP2;
3424               peep2_insn_data[i].insn = x;
3425               df_simulate_one_insn_backwards (bb, x, &live);
3426               COPY_REG_SET (peep2_insn_data[i].live_before, &live);
3427             }
3428         }
3429       x = PREV_INSN (x);
3430     }
3431   while (x != prev);
3432   CLEAR_REG_SET (&live);
3433
3434   peep2_current = i;
3435 }
3436
3437 /* Add INSN, which is in BB, at the end of the peep2 insn buffer if possible.
3438    Return true if we added it, false otherwise.  The caller will try to match
3439    peepholes against the buffer if we return false; otherwise it will try to
3440    add more instructions to the buffer.  */
3441
3442 static bool
3443 peep2_fill_buffer (basic_block bb, rtx insn, regset live)
3444 {
3445   int pos;
3446
3447   /* Once we have filled the maximum number of insns the buffer can hold,
3448      allow the caller to match the insns against peepholes.  We wait until
3449      the buffer is full in case the target has similar peepholes of different
3450      length; we always want to match the longest if possible.  */
3451   if (peep2_current_count == MAX_INSNS_PER_PEEP2)
3452     return false;
3453
3454   /* If an insn has RTX_FRAME_RELATED_P set, do not allow it to be matched with
3455      any other pattern, lest it change the semantics of the frame info.  */
3456   if (RTX_FRAME_RELATED_P (insn))
3457     {
3458       /* Let the buffer drain first.  */
3459       if (peep2_current_count > 0)
3460         return false;
3461       /* Now the insn will be the only thing in the buffer.  */
3462     }
3463
3464   pos = peep2_buf_position (peep2_current + peep2_current_count);
3465   peep2_insn_data[pos].insn = insn;
3466   COPY_REG_SET (peep2_insn_data[pos].live_before, live);
3467   peep2_current_count++;
3468
3469   df_simulate_one_insn_forwards (bb, insn, live);
3470   return true;
3471 }
3472
3473 /* Perform the peephole2 optimization pass.  */
3474
3475 static void
3476 peephole2_optimize (void)
3477 {
3478   rtx insn;
3479   bitmap live;
3480   int i;
3481   basic_block bb;
3482
3483   peep2_do_cleanup_cfg = false;
3484   peep2_do_rebuild_jump_labels = false;
3485
3486   df_set_flags (DF_LR_RUN_DCE);
3487   df_note_add_problem ();
3488   df_analyze ();
3489
3490   /* Initialize the regsets we're going to use.  */
3491   for (i = 0; i < MAX_INSNS_PER_PEEP2 + 1; ++i)
3492     peep2_insn_data[i].live_before = BITMAP_ALLOC (&reg_obstack);
3493   search_ofs = 0;
3494   live = BITMAP_ALLOC (&reg_obstack);
3495
3496   FOR_EACH_BB_REVERSE (bb)
3497     {
3498       bool past_end = false;
3499       int pos;
3500
3501       rtl_profile_for_bb (bb);
3502
3503       /* Start up propagation.  */
3504       bitmap_copy (live, DF_LR_IN (bb));
3505       df_simulate_initialize_forwards (bb, live);
3506       peep2_reinit_state (live);
3507
3508       insn = BB_HEAD (bb);
3509       for (;;)
3510         {
3511           rtx attempt, head;
3512           int match_len;
3513
3514           if (!past_end && !NONDEBUG_INSN_P (insn))
3515             {
3516             next_insn:
3517               insn = NEXT_INSN (insn);
3518               if (insn == NEXT_INSN (BB_END (bb)))
3519                 past_end = true;
3520               continue;
3521             }
3522           if (!past_end && peep2_fill_buffer (bb, insn, live))
3523             goto next_insn;
3524
3525           /* If we did not fill an empty buffer, it signals the end of the
3526              block.  */
3527           if (peep2_current_count == 0)
3528             break;
3529
3530           /* The buffer filled to the current maximum, so try to match.  */
3531
3532           pos = peep2_buf_position (peep2_current + peep2_current_count);
3533           peep2_insn_data[pos].insn = PEEP2_EOB;
3534           COPY_REG_SET (peep2_insn_data[pos].live_before, live);
3535
3536           /* Match the peephole.  */
3537           head = peep2_insn_data[peep2_current].insn;
3538           attempt = peephole2_insns (PATTERN (head), head, &match_len);
3539           if (attempt != NULL)
3540             {
3541               rtx last = peep2_attempt (bb, head, match_len, attempt);
3542               if (last)
3543                 {
3544                   peep2_update_life (bb, match_len, last, PREV_INSN (attempt));
3545                   continue;
3546                 }
3547             }
3548
3549           /* No match: advance the buffer by one insn.  */
3550           peep2_current = peep2_buf_position (peep2_current + 1);
3551           peep2_current_count--;
3552         }
3553     }
3554
3555   default_rtl_profile ();
3556   for (i = 0; i < MAX_INSNS_PER_PEEP2 + 1; ++i)
3557     BITMAP_FREE (peep2_insn_data[i].live_before);
3558   BITMAP_FREE (live);
3559   if (peep2_do_rebuild_jump_labels)
3560     rebuild_jump_labels (get_insns ());
3561 }
3562 #endif /* HAVE_peephole2 */
3563
3564 /* Common predicates for use with define_bypass.  */
3565
3566 /* True if the dependency between OUT_INSN and IN_INSN is on the store
3567    data not the address operand(s) of the store.  IN_INSN and OUT_INSN
3568    must be either a single_set or a PARALLEL with SETs inside.  */
3569
3570 int
3571 store_data_bypass_p (rtx out_insn, rtx in_insn)
3572 {
3573   rtx out_set, in_set;
3574   rtx out_pat, in_pat;
3575   rtx out_exp, in_exp;
3576   int i, j;
3577
3578   in_set = single_set (in_insn);
3579   if (in_set)
3580     {
3581       if (!MEM_P (SET_DEST (in_set)))
3582         return false;
3583
3584       out_set = single_set (out_insn);
3585       if (out_set)
3586         {
3587           if (reg_mentioned_p (SET_DEST (out_set), SET_DEST (in_set)))
3588             return false;
3589         }
3590       else
3591         {
3592           out_pat = PATTERN (out_insn);
3593
3594           if (GET_CODE (out_pat) != PARALLEL)
3595             return false;
3596
3597           for (i = 0; i < XVECLEN (out_pat, 0); i++)
3598           {
3599             out_exp = XVECEXP (out_pat, 0, i);
3600
3601             if (GET_CODE (out_exp) == CLOBBER)
3602               continue;
3603
3604             gcc_assert (GET_CODE (out_exp) == SET);
3605
3606             if (reg_mentioned_p (SET_DEST (out_exp), SET_DEST (in_set)))
3607               return false;
3608           }
3609       }
3610     }
3611   else
3612     {
3613       in_pat = PATTERN (in_insn);
3614       gcc_assert (GET_CODE (in_pat) == PARALLEL);
3615
3616       for (i = 0; i < XVECLEN (in_pat, 0); i++)
3617         {
3618           in_exp = XVECEXP (in_pat, 0, i);
3619
3620           if (GET_CODE (in_exp) == CLOBBER)
3621             continue;
3622
3623           gcc_assert (GET_CODE (in_exp) == SET);
3624
3625           if (!MEM_P (SET_DEST (in_exp)))
3626             return false;
3627
3628           out_set = single_set (out_insn);
3629           if (out_set)
3630             {
3631               if (reg_mentioned_p (SET_DEST (out_set), SET_DEST (in_exp)))
3632                 return false;
3633             }
3634           else
3635             {
3636               out_pat = PATTERN (out_insn);
3637               gcc_assert (GET_CODE (out_pat) == PARALLEL);
3638
3639               for (j = 0; j < XVECLEN (out_pat, 0); j++)
3640                 {
3641                   out_exp = XVECEXP (out_pat, 0, j);
3642
3643                   if (GET_CODE (out_exp) == CLOBBER)
3644                     continue;
3645
3646                   gcc_assert (GET_CODE (out_exp) == SET);
3647
3648                   if (reg_mentioned_p (SET_DEST (out_exp), SET_DEST (in_exp)))
3649                     return false;
3650                 }
3651             }
3652         }
3653     }
3654
3655   return true;
3656 }
3657
3658 /* True if the dependency between OUT_INSN and IN_INSN is in the IF_THEN_ELSE
3659    condition, and not the THEN or ELSE branch.  OUT_INSN may be either a single
3660    or multiple set; IN_INSN should be single_set for truth, but for convenience
3661    of insn categorization may be any JUMP or CALL insn.  */
3662
3663 int
3664 if_test_bypass_p (rtx out_insn, rtx in_insn)
3665 {
3666   rtx out_set, in_set;
3667
3668   in_set = single_set (in_insn);
3669   if (! in_set)
3670     {
3671       gcc_assert (JUMP_P (in_insn) || CALL_P (in_insn));
3672       return false;
3673     }
3674
3675   if (GET_CODE (SET_SRC (in_set)) != IF_THEN_ELSE)
3676     return false;
3677   in_set = SET_SRC (in_set);
3678
3679   out_set = single_set (out_insn);
3680   if (out_set)
3681     {
3682       if (reg_mentioned_p (SET_DEST (out_set), XEXP (in_set, 1))
3683           || reg_mentioned_p (SET_DEST (out_set), XEXP (in_set, 2)))
3684         return false;
3685     }
3686   else
3687     {
3688       rtx out_pat;
3689       int i;
3690
3691       out_pat = PATTERN (out_insn);
3692       gcc_assert (GET_CODE (out_pat) == PARALLEL);
3693
3694       for (i = 0; i < XVECLEN (out_pat, 0); i++)
3695         {
3696           rtx exp = XVECEXP (out_pat, 0, i);
3697
3698           if (GET_CODE (exp) == CLOBBER)
3699             continue;
3700
3701           gcc_assert (GET_CODE (exp) == SET);
3702
3703           if (reg_mentioned_p (SET_DEST (out_set), XEXP (in_set, 1))
3704               || reg_mentioned_p (SET_DEST (out_set), XEXP (in_set, 2)))
3705             return false;
3706         }
3707     }
3708
3709   return true;
3710 }
3711 \f
3712 static bool
3713 gate_handle_peephole2 (void)
3714 {
3715   return (optimize > 0 && flag_peephole2);
3716 }
3717
3718 static unsigned int
3719 rest_of_handle_peephole2 (void)
3720 {
3721 #ifdef HAVE_peephole2
3722   peephole2_optimize ();
3723 #endif
3724   return 0;
3725 }
3726
3727 struct rtl_opt_pass pass_peephole2 =
3728 {
3729  {
3730   RTL_PASS,
3731   "peephole2",                          /* name */
3732   gate_handle_peephole2,                /* gate */
3733   rest_of_handle_peephole2,             /* execute */
3734   NULL,                                 /* sub */
3735   NULL,                                 /* next */
3736   0,                                    /* static_pass_number */
3737   TV_PEEPHOLE2,                         /* tv_id */
3738   0,                                    /* properties_required */
3739   0,                                    /* properties_provided */
3740   0,                                    /* properties_destroyed */
3741   0,                                    /* todo_flags_start */
3742   TODO_df_finish | TODO_verify_rtl_sharing |
3743   0                                    /* todo_flags_finish */
3744  }
3745 };
3746
3747 static unsigned int
3748 rest_of_handle_split_all_insns (void)
3749 {
3750   split_all_insns ();
3751   return 0;
3752 }
3753
3754 struct rtl_opt_pass pass_split_all_insns =
3755 {
3756  {
3757   RTL_PASS,
3758   "split1",                             /* name */
3759   NULL,                                 /* gate */
3760   rest_of_handle_split_all_insns,       /* execute */
3761   NULL,                                 /* sub */
3762   NULL,                                 /* next */
3763   0,                                    /* static_pass_number */
3764   TV_NONE,                              /* tv_id */
3765   0,                                    /* properties_required */
3766   0,                                    /* properties_provided */
3767   0,                                    /* properties_destroyed */
3768   0,                                    /* todo_flags_start */
3769   0                                     /* todo_flags_finish */
3770  }
3771 };
3772
3773 static unsigned int
3774 rest_of_handle_split_after_reload (void)
3775 {
3776   /* If optimizing, then go ahead and split insns now.  */
3777 #ifndef STACK_REGS
3778   if (optimize > 0)
3779 #endif
3780     split_all_insns ();
3781   return 0;
3782 }
3783
3784 struct rtl_opt_pass pass_split_after_reload =
3785 {
3786  {
3787   RTL_PASS,
3788   "split2",                             /* name */
3789   NULL,                                 /* gate */
3790   rest_of_handle_split_after_reload,    /* execute */
3791   NULL,                                 /* sub */
3792   NULL,                                 /* next */
3793   0,                                    /* static_pass_number */
3794   TV_NONE,                              /* tv_id */
3795   0,                                    /* properties_required */
3796   0,                                    /* properties_provided */
3797   0,                                    /* properties_destroyed */
3798   0,                                    /* todo_flags_start */
3799   0                                     /* todo_flags_finish */
3800  }
3801 };
3802
3803 static bool
3804 gate_handle_split_before_regstack (void)
3805 {
3806 #if defined (HAVE_ATTR_length) && defined (STACK_REGS)
3807   /* If flow2 creates new instructions which need splitting
3808      and scheduling after reload is not done, they might not be
3809      split until final which doesn't allow splitting
3810      if HAVE_ATTR_length.  */
3811 # ifdef INSN_SCHEDULING
3812   return (optimize && !flag_schedule_insns_after_reload);
3813 # else
3814   return (optimize);
3815 # endif
3816 #else
3817   return 0;
3818 #endif
3819 }
3820
3821 static unsigned int
3822 rest_of_handle_split_before_regstack (void)
3823 {
3824   split_all_insns ();
3825   return 0;
3826 }
3827
3828 struct rtl_opt_pass pass_split_before_regstack =
3829 {
3830  {
3831   RTL_PASS,
3832   "split3",                             /* name */
3833   gate_handle_split_before_regstack,    /* gate */
3834   rest_of_handle_split_before_regstack, /* execute */
3835   NULL,                                 /* sub */
3836   NULL,                                 /* next */
3837   0,                                    /* static_pass_number */
3838   TV_NONE,                              /* tv_id */
3839   0,                                    /* properties_required */
3840   0,                                    /* properties_provided */
3841   0,                                    /* properties_destroyed */
3842   0,                                    /* todo_flags_start */
3843   0                                     /* todo_flags_finish */
3844  }
3845 };
3846
3847 static bool
3848 gate_handle_split_before_sched2 (void)
3849 {
3850 #ifdef INSN_SCHEDULING
3851   return optimize > 0 && flag_schedule_insns_after_reload;
3852 #else
3853   return 0;
3854 #endif
3855 }
3856
3857 static unsigned int
3858 rest_of_handle_split_before_sched2 (void)
3859 {
3860 #ifdef INSN_SCHEDULING
3861   split_all_insns ();
3862 #endif
3863   return 0;
3864 }
3865
3866 struct rtl_opt_pass pass_split_before_sched2 =
3867 {
3868  {
3869   RTL_PASS,
3870   "split4",                             /* name */
3871   gate_handle_split_before_sched2,      /* gate */
3872   rest_of_handle_split_before_sched2,   /* execute */
3873   NULL,                                 /* sub */
3874   NULL,                                 /* next */
3875   0,                                    /* static_pass_number */
3876   TV_NONE,                              /* tv_id */
3877   0,                                    /* properties_required */
3878   0,                                    /* properties_provided */
3879   0,                                    /* properties_destroyed */
3880   0,                                    /* todo_flags_start */
3881   TODO_verify_flow                      /* todo_flags_finish */
3882  }
3883 };
3884
3885 /* The placement of the splitting that we do for shorten_branches
3886    depends on whether regstack is used by the target or not.  */
3887 static bool
3888 gate_do_final_split (void)
3889 {
3890 #if defined (HAVE_ATTR_length) && !defined (STACK_REGS)
3891   return 1;
3892 #else
3893   return 0;
3894 #endif
3895 }
3896
3897 struct rtl_opt_pass pass_split_for_shorten_branches =
3898 {
3899  {
3900   RTL_PASS,
3901   "split5",                             /* name */
3902   gate_do_final_split,                  /* gate */
3903   split_all_insns_noflow,               /* execute */
3904   NULL,                                 /* sub */
3905   NULL,                                 /* next */
3906   0,                                    /* static_pass_number */
3907   TV_NONE,                              /* tv_id */
3908   0,                                    /* properties_required */
3909   0,                                    /* properties_provided */
3910   0,                                    /* properties_destroyed */
3911   0,                                    /* todo_flags_start */
3912   TODO_verify_rtl_sharing               /* todo_flags_finish */
3913  }
3914 };