Merge branch 'vendor/GCC50' - gcc 5.0 snapshot 1 FEB 2015
[dragonfly.git] / contrib / gcc-5.0 / gcc / genrecog.c
1 /* Generate code from machine description to recognize rtl as insns.
2    Copyright (C) 1987-2015 Free Software Foundation, Inc.
3
4    This file is part of GCC.
5
6    GCC is free software; you can redistribute it and/or modify it
7    under the terms of the GNU General Public License as published by
8    the Free Software Foundation; either version 3, or (at your option)
9    any later version.
10
11    GCC is distributed in the hope that it will be useful, but WITHOUT
12    ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
13    or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
14    License for more details.
15
16    You should have received a copy of the GNU General Public License
17    along with GCC; see the file COPYING3.  If not see
18    <http://www.gnu.org/licenses/>.  */
19
20
21 /* This program is used to produce insn-recog.c, which contains a
22    function called `recog' plus its subroutines.  These functions
23    contain a decision tree that recognizes whether an rtx, the
24    argument given to recog, is a valid instruction.
25
26    recog returns -1 if the rtx is not valid.  If the rtx is valid,
27    recog returns a nonnegative number which is the insn code number
28    for the pattern that matched.  This is the same as the order in the
29    machine description of the entry that matched.  This number can be
30    used as an index into various insn_* tables, such as insn_template,
31    insn_outfun, and insn_n_operands (found in insn-output.c).
32
33    The third argument to recog is an optional pointer to an int.  If
34    present, recog will accept a pattern if it matches except for
35    missing CLOBBER expressions at the end.  In that case, the value
36    pointed to by the optional pointer will be set to the number of
37    CLOBBERs that need to be added (it should be initialized to zero by
38    the caller).  If it is set nonzero, the caller should allocate a
39    PARALLEL of the appropriate size, copy the initial entries, and
40    call add_clobbers (found in insn-emit.c) to fill in the CLOBBERs.
41
42    This program also generates the function `split_insns', which
43    returns 0 if the rtl could not be split, or it returns the split
44    rtl as an INSN list.
45
46    This program also generates the function `peephole2_insns', which
47    returns 0 if the rtl could not be matched.  If there was a match,
48    the new rtl is returned in an INSN list, and LAST_INSN will point
49    to the last recognized insn in the old sequence.  */
50
51 #include "bconfig.h"
52 #include "system.h"
53 #include "coretypes.h"
54 #include "tm.h"
55 #include "rtl.h"
56 #include "errors.h"
57 #include "read-md.h"
58 #include "gensupport.h"
59
60 #define OUTPUT_LABEL(INDENT_STRING, LABEL_NUMBER) \
61   printf ("%sL%d: ATTRIBUTE_UNUSED_LABEL\n", (INDENT_STRING), (LABEL_NUMBER))
62
63 /* Ways of obtaining an rtx to be tested.  */
64 enum position_type {
65   /* PATTERN (peep2_next_insn (ARG)).  */
66   POS_PEEP2_INSN,
67
68   /* XEXP (BASE, ARG).  */
69   POS_XEXP,
70
71   /* XVECEXP (BASE, 0, ARG).  */
72   POS_XVECEXP0
73 };
74
75 /* The position of an rtx relative to X0.  Each useful position is
76    represented by exactly one instance of this structure.  */
77 struct position
78 {
79   /* The parent rtx.  This is the root position for POS_PEEP2_INSNs.  */
80   struct position *base;
81
82   /* A position with the same BASE and TYPE, but with the next value
83      of ARG.  */
84   struct position *next;
85
86   /* A list of all POS_XEXP positions that use this one as their base,
87      chained by NEXT fields.  The first entry represents XEXP (this, 0),
88      the second represents XEXP (this, 1), and so on.  */
89   struct position *xexps;
90
91   /* A list of POS_XVECEXP0 positions that use this one as their base,
92      chained by NEXT fields.  The first entry represents XVECEXP (this, 0, 0),
93      the second represents XVECEXP (this, 0, 1), and so on.  */
94   struct position *xvecexp0s;
95
96   /* The type of position.  */
97   enum position_type type;
98
99   /* The argument to TYPE (shown as ARG in the position_type comments).  */
100   int arg;
101
102   /* The depth of this position, with 0 as the root.  */
103   int depth;
104 };
105
106 /* A listhead of decision trees.  The alternatives to a node are kept
107    in a doubly-linked list so we can easily add nodes to the proper
108    place when merging.  */
109
110 struct decision_head
111 {
112   struct decision *first;
113   struct decision *last;
114 };
115
116 /* These types are roughly in the order in which we'd like to test them.  */
117 enum decision_type
118 {
119   DT_num_insns,
120   DT_mode, DT_code, DT_veclen,
121   DT_elt_zero_int, DT_elt_one_int, DT_elt_zero_wide, DT_elt_zero_wide_safe,
122   DT_const_int,
123   DT_veclen_ge, DT_dup, DT_pred, DT_c_test,
124   DT_accept_op, DT_accept_insn
125 };
126
127 /* A single test.  The two accept types aren't tests per-se, but
128    their equality (or lack thereof) does affect tree merging so
129    it is convenient to keep them here.  */
130
131 struct decision_test
132 {
133   /* A linked list through the tests attached to a node.  */
134   struct decision_test *next;
135
136   enum decision_type type;
137
138   union
139   {
140     int num_insns;              /* Number if insn in a define_peephole2.  */
141     machine_mode mode;  /* Machine mode of node.  */
142     RTX_CODE code;              /* Code to test.  */
143
144     struct
145     {
146       const char *name;         /* Predicate to call.  */
147       const struct pred_data *data;
148                                 /* Optimization hints for this predicate.  */
149       machine_mode mode;        /* Machine mode for node.  */
150     } pred;
151
152     const char *c_test;         /* Additional test to perform.  */
153     int veclen;                 /* Length of vector.  */
154     int dup;                    /* Number of operand to compare against.  */
155     HOST_WIDE_INT intval;       /* Value for XINT for XWINT.  */
156     int opno;                   /* Operand number matched.  */
157
158     struct {
159       int code_number;          /* Insn number matched.  */
160       int lineno;               /* Line number of the insn.  */
161       int num_clobbers_to_add;  /* Number of CLOBBERs to be added.  */
162     } insn;
163   } u;
164 };
165
166 /* Data structure for decision tree for recognizing legitimate insns.  */
167
168 struct decision
169 {
170   struct decision_head success; /* Nodes to test on success.  */
171   struct decision *next;        /* Node to test on failure.  */
172   struct decision *prev;        /* Node whose failure tests us.  */
173   struct decision *afterward;   /* Node to test on success,
174                                    but failure of successor nodes.  */
175
176   struct position *position;    /* Position in pattern.  */
177
178   struct decision_test *tests;  /* The tests for this node.  */
179
180   int number;                   /* Node number, used for labels */
181   int subroutine_number;        /* Number of subroutine this node starts */
182   int need_label;               /* Label needs to be output.  */
183 };
184
185 #define SUBROUTINE_THRESHOLD    100
186
187 static int next_subroutine_number;
188
189 /* We can write three types of subroutines: One for insn recognition,
190    one to split insns, and one for peephole-type optimizations.  This
191    defines which type is being written.  */
192
193 enum routine_type {
194   RECOG, SPLIT, PEEPHOLE2
195 };
196
197 #define IS_SPLIT(X) ((X) != RECOG)
198
199 /* Next available node number for tree nodes.  */
200
201 static int next_number;
202
203 /* Next number to use as an insn_code.  */
204
205 static int next_insn_code;
206
207 /* Record the highest depth we ever have so we know how many variables to
208    allocate in each subroutine we make.  */
209
210 static int max_depth;
211
212 /* The line number of the start of the pattern currently being processed.  */
213 static int pattern_lineno;
214
215 /* The root position (x0).  */
216 static struct position root_pos;
217
218 /* A list of all POS_PEEP2_INSNs.  The entry for insn 0 is the root position,
219    since we are given that instruction's pattern as x0.  */
220 static struct position *peep2_insn_pos_list = &root_pos;
221 \f
222 extern void debug_decision
223   (struct decision *);
224 extern void debug_decision_list
225   (struct decision *);
226 \f
227 /* Return a position with the given BASE, TYPE and ARG.  NEXT_PTR
228    points to where the unique object that represents the position
229    should be stored.  Create the object if it doesn't already exist,
230    otherwise reuse the object that is already there.  */
231
232 static struct position *
233 next_position (struct position **next_ptr, struct position *base,
234                enum position_type type, int arg)
235 {
236   struct position *pos;
237
238   pos = *next_ptr;
239   if (!pos)
240     {
241       pos = XCNEW (struct position);
242       pos->base = base;
243       pos->type = type;
244       pos->arg = arg;
245       pos->depth = base->depth + 1;
246       *next_ptr = pos;
247     }
248   return pos;
249 }
250
251 /* Compare positions POS1 and POS2 lexicographically.  */
252
253 static int
254 compare_positions (struct position *pos1, struct position *pos2)
255 {
256   int diff;
257
258   diff = pos1->depth - pos2->depth;
259   if (diff < 0)
260     do
261       pos2 = pos2->base;
262     while (pos1->depth != pos2->depth);
263   else if (diff > 0)
264     do
265       pos1 = pos1->base;
266     while (pos1->depth != pos2->depth);
267   while (pos1 != pos2)
268     {
269       diff = (int) pos1->type - (int) pos2->type;
270       if (diff == 0)
271         diff = pos1->arg - pos2->arg;
272       pos1 = pos1->base;
273       pos2 = pos2->base;
274     }
275   return diff;
276 }
277
278 /* Create a new node in sequence after LAST.  */
279
280 static struct decision *
281 new_decision (struct position *pos, struct decision_head *last)
282 {
283   struct decision *new_decision = XCNEW (struct decision);
284
285   new_decision->success = *last;
286   new_decision->position = pos;
287   new_decision->number = next_number++;
288
289   last->first = last->last = new_decision;
290   return new_decision;
291 }
292
293 /* Create a new test and link it in at PLACE.  */
294
295 static struct decision_test *
296 new_decision_test (enum decision_type type, struct decision_test ***pplace)
297 {
298   struct decision_test **place = *pplace;
299   struct decision_test *test;
300
301   test = XNEW (struct decision_test);
302   test->next = *place;
303   test->type = type;
304   *place = test;
305
306   place = &test->next;
307   *pplace = place;
308
309   return test;
310 }
311
312 /* Search for and return operand N, stop when reaching node STOP.  */
313
314 static rtx
315 find_operand (rtx pattern, int n, rtx stop)
316 {
317   const char *fmt;
318   RTX_CODE code;
319   int i, j, len;
320   rtx r;
321
322   if (pattern == stop)
323     return stop;
324
325   code = GET_CODE (pattern);
326   if ((code == MATCH_SCRATCH
327        || code == MATCH_OPERAND
328        || code == MATCH_OPERATOR
329        || code == MATCH_PARALLEL)
330       && XINT (pattern, 0) == n)
331     return pattern;
332
333   fmt = GET_RTX_FORMAT (code);
334   len = GET_RTX_LENGTH (code);
335   for (i = 0; i < len; i++)
336     {
337       switch (fmt[i])
338         {
339         case 'e': case 'u':
340           if ((r = find_operand (XEXP (pattern, i), n, stop)) != NULL_RTX)
341             return r;
342           break;
343
344         case 'V':
345           if (! XVEC (pattern, i))
346             break;
347           /* Fall through.  */
348
349         case 'E':
350           for (j = 0; j < XVECLEN (pattern, i); j++)
351             if ((r = find_operand (XVECEXP (pattern, i, j), n, stop))
352                 != NULL_RTX)
353               return r;
354           break;
355
356         case 'i': case 'w': case '0': case 's':
357           break;
358
359         default:
360           gcc_unreachable ();
361         }
362     }
363
364   return NULL;
365 }
366
367 /* Search for and return operand M, such that it has a matching
368    constraint for operand N.  */
369
370 static rtx
371 find_matching_operand (rtx pattern, int n)
372 {
373   const char *fmt;
374   RTX_CODE code;
375   int i, j, len;
376   rtx r;
377
378   code = GET_CODE (pattern);
379   if (code == MATCH_OPERAND
380       && (XSTR (pattern, 2)[0] == '0' + n
381           || (XSTR (pattern, 2)[0] == '%'
382               && XSTR (pattern, 2)[1] == '0' + n)))
383     return pattern;
384
385   fmt = GET_RTX_FORMAT (code);
386   len = GET_RTX_LENGTH (code);
387   for (i = 0; i < len; i++)
388     {
389       switch (fmt[i])
390         {
391         case 'e': case 'u':
392           if ((r = find_matching_operand (XEXP (pattern, i), n)))
393             return r;
394           break;
395
396         case 'V':
397           if (! XVEC (pattern, i))
398             break;
399           /* Fall through.  */
400
401         case 'E':
402           for (j = 0; j < XVECLEN (pattern, i); j++)
403             if ((r = find_matching_operand (XVECEXP (pattern, i, j), n)))
404               return r;
405           break;
406
407         case 'i': case 'w': case '0': case 's':
408           break;
409
410         default:
411           gcc_unreachable ();
412         }
413     }
414
415   return NULL;
416 }
417
418 /* In DEFINE_EXPAND, DEFINE_SPLIT, and DEFINE_PEEPHOLE2, we
419    don't use the MATCH_OPERAND constraint, only the predicate.
420    This is confusing to folks doing new ports, so help them
421    not make the mistake.  */
422
423 static bool
424 constraints_supported_in_insn_p (rtx insn)
425 {
426   return !(GET_CODE (insn) == DEFINE_EXPAND
427            || GET_CODE (insn) == DEFINE_SPLIT
428            || GET_CODE (insn) == DEFINE_PEEPHOLE2);
429 }
430
431 /* Check for various errors in patterns.  SET is nonnull for a destination,
432    and is the complete set pattern.  SET_CODE is '=' for normal sets, and
433    '+' within a context that requires in-out constraints.  */
434
435 static void
436 validate_pattern (rtx pattern, rtx insn, rtx set, int set_code)
437 {
438   const char *fmt;
439   RTX_CODE code;
440   size_t i, len;
441   int j;
442
443   code = GET_CODE (pattern);
444   switch (code)
445     {
446     case MATCH_SCRATCH:
447       {
448         const char constraints0 = XSTR (pattern, 1)[0];
449
450         if (!constraints_supported_in_insn_p (insn))
451           {
452             if (constraints0)
453               {
454                 error_with_line (pattern_lineno,
455                                  "constraints not supported in %s",
456                                  rtx_name[GET_CODE (insn)]);
457               }
458             return;
459           }
460
461         /* If a MATCH_SCRATCH is used in a context requiring an write-only
462            or read/write register, validate that.  */
463         if (set_code == '='
464             && constraints0
465             && constraints0 != '='
466             && constraints0 != '+')
467           {
468             error_with_line (pattern_lineno,
469                              "operand %d missing output reload",
470                              XINT (pattern, 0));
471           }
472         return;
473       }
474     case MATCH_DUP:
475     case MATCH_OP_DUP:
476     case MATCH_PAR_DUP:
477       if (find_operand (insn, XINT (pattern, 0), pattern) == pattern)
478         error_with_line (pattern_lineno,
479                          "operand %i duplicated before defined",
480                          XINT (pattern, 0));
481       break;
482     case MATCH_OPERAND:
483     case MATCH_OPERATOR:
484       {
485         const char *pred_name = XSTR (pattern, 1);
486         const struct pred_data *pred;
487         const char *c_test;
488
489         if (GET_CODE (insn) == DEFINE_INSN)
490           c_test = XSTR (insn, 2);
491         else
492           c_test = XSTR (insn, 1);
493
494         if (pred_name[0] != 0)
495           {
496             pred = lookup_predicate (pred_name);
497             if (!pred)
498               error_with_line (pattern_lineno, "unknown predicate '%s'",
499                                pred_name);
500           }
501         else
502           pred = 0;
503
504         if (code == MATCH_OPERAND)
505           {
506             const char constraints0 = XSTR (pattern, 2)[0];
507
508             if (!constraints_supported_in_insn_p (insn))
509               {
510                 if (constraints0)
511                   {
512                     error_with_line (pattern_lineno,
513                                      "constraints not supported in %s",
514                                      rtx_name[GET_CODE (insn)]);
515                   }
516               }
517
518             /* A MATCH_OPERAND that is a SET should have an output reload.  */
519             else if (set && constraints0)
520               {
521                 if (set_code == '+')
522                   {
523                     if (constraints0 == '+')
524                       ;
525                     /* If we've only got an output reload for this operand,
526                        we'd better have a matching input operand.  */
527                     else if (constraints0 == '='
528                              && find_matching_operand (insn, XINT (pattern, 0)))
529                       ;
530                     else
531                       error_with_line (pattern_lineno,
532                                        "operand %d missing in-out reload",
533                                        XINT (pattern, 0));
534                   }
535                 else if (constraints0 != '=' && constraints0 != '+')
536                   error_with_line (pattern_lineno,
537                                    "operand %d missing output reload",
538                                    XINT (pattern, 0));
539               }
540           }
541
542         /* Allowing non-lvalues in destinations -- particularly CONST_INT --
543            while not likely to occur at runtime, results in less efficient
544            code from insn-recog.c.  */
545         if (set && pred && pred->allows_non_lvalue)
546           error_with_line (pattern_lineno,
547                            "destination operand %d allows non-lvalue",
548                            XINT (pattern, 0));
549
550         /* A modeless MATCH_OPERAND can be handy when we can check for
551            multiple modes in the c_test.  In most other cases, it is a
552            mistake.  Only DEFINE_INSN is eligible, since SPLIT and
553            PEEP2 can FAIL within the output pattern.  Exclude special
554            predicates, which check the mode themselves.  Also exclude
555            predicates that allow only constants.  Exclude the SET_DEST
556            of a call instruction, as that is a common idiom.  */
557
558         if (GET_MODE (pattern) == VOIDmode
559             && code == MATCH_OPERAND
560             && GET_CODE (insn) == DEFINE_INSN
561             && pred
562             && !pred->special
563             && pred->allows_non_const
564             && strstr (c_test, "operands") == NULL
565             && ! (set
566                   && GET_CODE (set) == SET
567                   && GET_CODE (SET_SRC (set)) == CALL))
568           message_with_line (pattern_lineno,
569                              "warning: operand %d missing mode?",
570                              XINT (pattern, 0));
571         return;
572       }
573
574     case SET:
575       {
576         machine_mode dmode, smode;
577         rtx dest, src;
578
579         dest = SET_DEST (pattern);
580         src = SET_SRC (pattern);
581
582         /* STRICT_LOW_PART is a wrapper.  Its argument is the real
583            destination, and it's mode should match the source.  */
584         if (GET_CODE (dest) == STRICT_LOW_PART)
585           dest = XEXP (dest, 0);
586
587         /* Find the referent for a DUP.  */
588
589         if (GET_CODE (dest) == MATCH_DUP
590             || GET_CODE (dest) == MATCH_OP_DUP
591             || GET_CODE (dest) == MATCH_PAR_DUP)
592           dest = find_operand (insn, XINT (dest, 0), NULL);
593
594         if (GET_CODE (src) == MATCH_DUP
595             || GET_CODE (src) == MATCH_OP_DUP
596             || GET_CODE (src) == MATCH_PAR_DUP)
597           src = find_operand (insn, XINT (src, 0), NULL);
598
599         dmode = GET_MODE (dest);
600         smode = GET_MODE (src);
601
602         /* The mode of an ADDRESS_OPERAND is the mode of the memory
603            reference, not the mode of the address.  */
604         if (GET_CODE (src) == MATCH_OPERAND
605             && ! strcmp (XSTR (src, 1), "address_operand"))
606           ;
607
608         /* The operands of a SET must have the same mode unless one
609            is VOIDmode.  */
610         else if (dmode != VOIDmode && smode != VOIDmode && dmode != smode)
611           error_with_line (pattern_lineno,
612                            "mode mismatch in set: %smode vs %smode",
613                            GET_MODE_NAME (dmode), GET_MODE_NAME (smode));
614
615         /* If only one of the operands is VOIDmode, and PC or CC0 is
616            not involved, it's probably a mistake.  */
617         else if (dmode != smode
618                  && GET_CODE (dest) != PC
619                  && GET_CODE (dest) != CC0
620                  && GET_CODE (src) != PC
621                  && GET_CODE (src) != CC0
622                  && !CONST_INT_P (src)
623                  && !CONST_WIDE_INT_P (src)
624                  && GET_CODE (src) != CALL)
625           {
626             const char *which;
627             which = (dmode == VOIDmode ? "destination" : "source");
628             message_with_line (pattern_lineno,
629                                "warning: %s missing a mode?", which);
630           }
631
632         if (dest != SET_DEST (pattern))
633           validate_pattern (dest, insn, pattern, '=');
634         validate_pattern (SET_DEST (pattern), insn, pattern, '=');
635         validate_pattern (SET_SRC (pattern), insn, NULL_RTX, 0);
636         return;
637       }
638
639     case CLOBBER:
640       validate_pattern (SET_DEST (pattern), insn, pattern, '=');
641       return;
642
643     case ZERO_EXTRACT:
644       validate_pattern (XEXP (pattern, 0), insn, set, set ? '+' : 0);
645       validate_pattern (XEXP (pattern, 1), insn, NULL_RTX, 0);
646       validate_pattern (XEXP (pattern, 2), insn, NULL_RTX, 0);
647       return;
648
649     case STRICT_LOW_PART:
650       validate_pattern (XEXP (pattern, 0), insn, set, set ? '+' : 0);
651       return;
652
653     case LABEL_REF:
654       if (GET_MODE (LABEL_REF_LABEL (pattern)) != VOIDmode)
655         error_with_line (pattern_lineno,
656                          "operand to label_ref %smode not VOIDmode",
657                          GET_MODE_NAME (GET_MODE (LABEL_REF_LABEL (pattern))));
658       break;
659
660     default:
661       break;
662     }
663
664   fmt = GET_RTX_FORMAT (code);
665   len = GET_RTX_LENGTH (code);
666   for (i = 0; i < len; i++)
667     {
668       switch (fmt[i])
669         {
670         case 'e': case 'u':
671           validate_pattern (XEXP (pattern, i), insn, NULL_RTX, 0);
672           break;
673
674         case 'E':
675           for (j = 0; j < XVECLEN (pattern, i); j++)
676             validate_pattern (XVECEXP (pattern, i, j), insn, NULL_RTX, 0);
677           break;
678
679         case 'i': case 'w': case '0': case 's':
680           break;
681
682         default:
683           gcc_unreachable ();
684         }
685     }
686 }
687
688 /* Create a chain of nodes to verify that an rtl expression matches
689    PATTERN.
690
691    LAST is a pointer to the listhead in the previous node in the chain (or
692    in the calling function, for the first node).
693
694    POSITION is the current position in the insn.
695
696    INSN_TYPE is the type of insn for which we are emitting code.
697
698    A pointer to the final node in the chain is returned.  */
699
700 static struct decision *
701 add_to_sequence (rtx pattern, struct decision_head *last,
702                  struct position *pos, enum routine_type insn_type, int top)
703 {
704   RTX_CODE code;
705   struct decision *this_decision, *sub;
706   struct decision_test *test;
707   struct decision_test **place;
708   struct position *subpos, **subpos_ptr;
709   size_t i;
710   const char *fmt;
711   int len;
712   machine_mode mode;
713   enum position_type pos_type;
714
715   if (pos->depth > max_depth)
716     max_depth = pos->depth;
717
718   sub = this_decision = new_decision (pos, last);
719   place = &this_decision->tests;
720
721   mode = GET_MODE (pattern);
722   code = GET_CODE (pattern);
723
724   switch (code)
725     {
726     case PARALLEL:
727       /* Toplevel peephole pattern.  */
728       if (insn_type == PEEPHOLE2 && top)
729         {
730           int num_insns;
731
732           /* Check we have sufficient insns.  This avoids complications
733              because we then know peep2_next_insn never fails.  */
734           num_insns = XVECLEN (pattern, 0);
735           if (num_insns > 1)
736             {
737               test = new_decision_test (DT_num_insns, &place);
738               test->u.num_insns = num_insns;
739               last = &sub->success;
740             }
741           else
742             {
743               /* We don't need the node we just created -- unlink it.  */
744               last->first = last->last = NULL;
745             }
746
747           subpos_ptr = &peep2_insn_pos_list;
748           for (i = 0; i < (size_t) XVECLEN (pattern, 0); i++)
749             {
750               subpos = next_position (subpos_ptr, &root_pos,
751                                       POS_PEEP2_INSN, i);
752               sub = add_to_sequence (XVECEXP (pattern, 0, i),
753                                      last, subpos, insn_type, 0);
754               last = &sub->success;
755               subpos_ptr = &subpos->next;
756             }
757           goto ret;
758         }
759
760       /* Else nothing special.  */
761       break;
762
763     case MATCH_PARALLEL:
764       /* The explicit patterns within a match_parallel enforce a minimum
765          length on the vector.  The match_parallel predicate may allow
766          for more elements.  We do need to check for this minimum here
767          or the code generated to match the internals may reference data
768          beyond the end of the vector.  */
769       test = new_decision_test (DT_veclen_ge, &place);
770       test->u.veclen = XVECLEN (pattern, 2);
771       /* Fall through.  */
772
773     case MATCH_OPERAND:
774     case MATCH_SCRATCH:
775     case MATCH_OPERATOR:
776       {
777         RTX_CODE was_code = code;
778         const char *pred_name;
779         bool allows_const_int = true;
780
781         if (code == MATCH_SCRATCH)
782           {
783             pred_name = "scratch_operand";
784             code = UNKNOWN;
785           }
786         else
787           {
788             pred_name = XSTR (pattern, 1);
789             if (code == MATCH_PARALLEL)
790               code = PARALLEL;
791             else
792               code = UNKNOWN;
793           }
794
795         if (pred_name[0] != 0)
796           {
797             const struct pred_data *pred;
798
799             test = new_decision_test (DT_pred, &place);
800             test->u.pred.name = pred_name;
801             test->u.pred.mode = mode;
802
803             /* See if we know about this predicate.
804                If we do, remember it for use below.
805
806                We can optimize the generated code a little if either
807                (a) the predicate only accepts one code, or (b) the
808                predicate does not allow CONST_INT or CONST_WIDE_INT,
809                in which case it can match only if the modes match.  */
810             pred = lookup_predicate (pred_name);
811             if (pred)
812               {
813                 test->u.pred.data = pred;
814                 allows_const_int = (pred->codes[CONST_INT]
815                                     || pred->codes[CONST_WIDE_INT]);
816                 if (was_code == MATCH_PARALLEL
817                     && pred->singleton != PARALLEL)
818                   error_with_line (pattern_lineno,
819                                    "predicate '%s' used in match_parallel "
820                                    "does not allow only PARALLEL", pred->name);
821                 else
822                   code = pred->singleton;
823               }
824             else
825               error_with_line (pattern_lineno,
826                                "unknown predicate '%s' in '%s' expression",
827                                pred_name, GET_RTX_NAME (was_code));
828           }
829
830         /* Can't enforce a mode if we allow const_int.  */
831         if (allows_const_int)
832           mode = VOIDmode;
833
834         /* Accept the operand, i.e. record it in `operands'.  */
835         test = new_decision_test (DT_accept_op, &place);
836         test->u.opno = XINT (pattern, 0);
837
838         if (was_code == MATCH_OPERATOR || was_code == MATCH_PARALLEL)
839           {
840             if (was_code == MATCH_OPERATOR)
841               {
842                 pos_type = POS_XEXP;
843                 subpos_ptr = &pos->xexps;
844               }
845             else
846               {
847                 pos_type = POS_XVECEXP0;
848                 subpos_ptr = &pos->xvecexp0s;
849               }
850             for (i = 0; i < (size_t) XVECLEN (pattern, 2); i++)
851               {
852                 subpos = next_position (subpos_ptr, pos, pos_type, i);
853                 sub = add_to_sequence (XVECEXP (pattern, 2, i),
854                                        &sub->success, subpos, insn_type, 0);
855                 subpos_ptr = &subpos->next;
856               }
857           }
858         goto fini;
859       }
860
861     case MATCH_OP_DUP:
862       code = UNKNOWN;
863
864       test = new_decision_test (DT_dup, &place);
865       test->u.dup = XINT (pattern, 0);
866
867       test = new_decision_test (DT_accept_op, &place);
868       test->u.opno = XINT (pattern, 0);
869
870       subpos_ptr = &pos->xexps;
871       for (i = 0; i < (size_t) XVECLEN (pattern, 1); i++)
872         {
873           subpos = next_position (subpos_ptr, pos, POS_XEXP, i);
874           sub = add_to_sequence (XVECEXP (pattern, 1, i),
875                                  &sub->success, subpos, insn_type, 0);
876           subpos_ptr = &subpos->next;
877         }
878       goto fini;
879
880     case MATCH_DUP:
881     case MATCH_PAR_DUP:
882       code = UNKNOWN;
883
884       test = new_decision_test (DT_dup, &place);
885       test->u.dup = XINT (pattern, 0);
886       goto fini;
887
888     default:
889       break;
890     }
891
892   fmt = GET_RTX_FORMAT (code);
893   len = GET_RTX_LENGTH (code);
894
895   /* Do tests against the current node first.  */
896   for (i = 0; i < (size_t) len; i++)
897     {
898       if (fmt[i] == 'i')
899         {
900           gcc_assert (i < 2);
901
902           if (!i)
903             {
904               test = new_decision_test (DT_elt_zero_int, &place);
905               test->u.intval = XINT (pattern, i);
906             }
907           else
908             {
909               test = new_decision_test (DT_elt_one_int, &place);
910               test->u.intval = XINT (pattern, i);
911             }
912         }
913       else if (fmt[i] == 'w')
914         {
915           /* If this value actually fits in an int, we can use a switch
916              statement here, so indicate that.  */
917           enum decision_type type
918             = ((int) XWINT (pattern, i) == XWINT (pattern, i))
919               ? DT_elt_zero_wide_safe : DT_elt_zero_wide;
920
921           gcc_assert (!i);
922
923           test = new_decision_test (type, &place);
924           test->u.intval = XWINT (pattern, i);
925         }
926       else if (fmt[i] == 'E')
927         {
928           gcc_assert (!i);
929
930           test = new_decision_test (DT_veclen, &place);
931           test->u.veclen = XVECLEN (pattern, i);
932         }
933     }
934
935   /* Now test our sub-patterns.  */
936   subpos_ptr = &pos->xexps;
937   for (i = 0; i < (size_t) len; i++)
938     {
939       subpos = next_position (subpos_ptr, pos, POS_XEXP, i);
940       switch (fmt[i])
941         {
942         case 'e': case 'u':
943           sub = add_to_sequence (XEXP (pattern, i), &sub->success,
944                                  subpos, insn_type, 0);
945           break;
946
947         case 'E':
948           {
949             struct position *subpos2, **subpos2_ptr;
950             int j;
951
952             subpos2_ptr = &pos->xvecexp0s;
953             for (j = 0; j < XVECLEN (pattern, i); j++)
954               {
955                 subpos2 = next_position (subpos2_ptr, pos, POS_XVECEXP0, j);
956                 sub = add_to_sequence (XVECEXP (pattern, i, j),
957                                        &sub->success, subpos2, insn_type, 0);
958                 subpos2_ptr = &subpos2->next;
959               }
960             break;
961           }
962
963         case 'i': case 'w':
964           /* Handled above.  */
965           break;
966         case '0':
967           break;
968
969         default:
970           gcc_unreachable ();
971         }
972       subpos_ptr = &subpos->next;
973     }
974
975  fini:
976   /* Insert nodes testing mode and code, if they're still relevant,
977      before any of the nodes we may have added above.  */
978   if (code != UNKNOWN)
979     {
980       place = &this_decision->tests;
981       test = new_decision_test (DT_code, &place);
982       test->u.code = code;
983     }
984
985   if (mode != VOIDmode)
986     {
987       place = &this_decision->tests;
988       test = new_decision_test (DT_mode, &place);
989       test->u.mode = mode;
990     }
991
992   /* If we didn't insert any tests or accept nodes, hork.  */
993   gcc_assert (this_decision->tests);
994
995  ret:
996   return sub;
997 }
998 \f
999 /* A subroutine of maybe_both_true; examines only one test.
1000    Returns > 0 for "definitely both true" and < 0 for "maybe both true".  */
1001
1002 static int
1003 maybe_both_true_2 (struct decision_test *d1, struct decision_test *d2)
1004 {
1005   if (d1->type == d2->type)
1006     {
1007       switch (d1->type)
1008         {
1009         case DT_num_insns:
1010           if (d1->u.num_insns == d2->u.num_insns)
1011             return 1;
1012           else
1013             return -1;
1014
1015         case DT_mode:
1016           return d1->u.mode == d2->u.mode;
1017
1018         case DT_code:
1019           return d1->u.code == d2->u.code;
1020
1021         case DT_veclen:
1022           return d1->u.veclen == d2->u.veclen;
1023
1024         case DT_elt_zero_int:
1025         case DT_elt_one_int:
1026         case DT_elt_zero_wide:
1027         case DT_elt_zero_wide_safe:
1028           return d1->u.intval == d2->u.intval;
1029
1030         default:
1031           break;
1032         }
1033     }
1034
1035   /* If either has a predicate that we know something about, set
1036      things up so that D1 is the one that always has a known
1037      predicate.  Then see if they have any codes in common.  */
1038
1039   if (d1->type == DT_pred || d2->type == DT_pred)
1040     {
1041       if (d2->type == DT_pred)
1042         {
1043           struct decision_test *tmp;
1044           tmp = d1, d1 = d2, d2 = tmp;
1045         }
1046
1047       /* If D2 tests a mode, see if it matches D1.  */
1048       if (d1->u.pred.mode != VOIDmode)
1049         {
1050           if (d2->type == DT_mode)
1051             {
1052               if (d1->u.pred.mode != d2->u.mode
1053                   /* The mode of an address_operand predicate is the
1054                      mode of the memory, not the operand.  It can only
1055                      be used for testing the predicate, so we must
1056                      ignore it here.  */
1057                   && strcmp (d1->u.pred.name, "address_operand") != 0)
1058                 return 0;
1059             }
1060           /* Don't check two predicate modes here, because if both predicates
1061              accept CONST_INT, then both can still be true even if the modes
1062              are different.  If they don't accept CONST_INT, there will be a
1063              separate DT_mode that will make maybe_both_true_1 return 0.  */
1064         }
1065
1066       if (d1->u.pred.data)
1067         {
1068           /* If D2 tests a code, see if it is in the list of valid
1069              codes for D1's predicate.  */
1070           if (d2->type == DT_code)
1071             {
1072               if (!d1->u.pred.data->codes[d2->u.code])
1073                 return 0;
1074             }
1075
1076           /* Otherwise see if the predicates have any codes in common.  */
1077           else if (d2->type == DT_pred && d2->u.pred.data)
1078             {
1079               bool common = false;
1080               int c;
1081
1082               for (c = 0; c < NUM_RTX_CODE; c++)
1083                 if (d1->u.pred.data->codes[c] && d2->u.pred.data->codes[c])
1084                   {
1085                     common = true;
1086                     break;
1087                   }
1088
1089               if (!common)
1090                 return 0;
1091             }
1092         }
1093     }
1094
1095   /* Tests vs veclen may be known when strict equality is involved.  */
1096   if (d1->type == DT_veclen && d2->type == DT_veclen_ge)
1097     return d1->u.veclen >= d2->u.veclen;
1098   if (d1->type == DT_veclen_ge && d2->type == DT_veclen)
1099     return d2->u.veclen >= d1->u.veclen;
1100
1101   return -1;
1102 }
1103
1104 /* A subroutine of maybe_both_true; examines all the tests for a given node.
1105    Returns > 0 for "definitely both true" and < 0 for "maybe both true".  */
1106
1107 static int
1108 maybe_both_true_1 (struct decision_test *d1, struct decision_test *d2)
1109 {
1110   struct decision_test *t1, *t2;
1111
1112   /* A match_operand with no predicate can match anything.  Recognize
1113      this by the existence of a lone DT_accept_op test.  */
1114   if (d1->type == DT_accept_op || d2->type == DT_accept_op)
1115     return 1;
1116
1117   /* Eliminate pairs of tests while they can exactly match.  */
1118   while (d1 && d2 && d1->type == d2->type)
1119     {
1120       if (maybe_both_true_2 (d1, d2) == 0)
1121         return 0;
1122       d1 = d1->next, d2 = d2->next;
1123     }
1124
1125   /* After that, consider all pairs.  */
1126   for (t1 = d1; t1 ; t1 = t1->next)
1127     for (t2 = d2; t2 ; t2 = t2->next)
1128       if (maybe_both_true_2 (t1, t2) == 0)
1129         return 0;
1130
1131   return -1;
1132 }
1133
1134 /* Return 0 if we can prove that there is no RTL that can match both
1135    D1 and D2.  Otherwise, return 1 (it may be that there is an RTL that
1136    can match both or just that we couldn't prove there wasn't such an RTL).
1137
1138    TOPLEVEL is nonzero if we are to only look at the top level and not
1139    recursively descend.  */
1140
1141 static int
1142 maybe_both_true (struct decision *d1, struct decision *d2,
1143                  int toplevel)
1144 {
1145   struct decision *p1, *p2;
1146   int cmp;
1147
1148   /* Don't compare strings on the different positions in insn.  Doing so
1149      is incorrect and results in false matches from constructs like
1150
1151         [(set (subreg:HI (match_operand:SI "register_operand" "r") 0)
1152               (subreg:HI (match_operand:SI "register_operand" "r") 0))]
1153      vs
1154         [(set (match_operand:HI "register_operand" "r")
1155               (match_operand:HI "register_operand" "r"))]
1156
1157      If we are presented with such, we are recursing through the remainder
1158      of a node's success nodes (from the loop at the end of this function).
1159      Skip forward until we come to a position that matches.
1160
1161      Due to the way positions are constructed, we know that iterating
1162      forward from the lexically lower position will run into the lexically
1163      higher position and not the other way around.  This saves a bit
1164      of effort.  */
1165
1166   cmp = compare_positions (d1->position, d2->position);
1167   if (cmp != 0)
1168     {
1169       gcc_assert (!toplevel);
1170
1171       /* If the d2->position was lexically lower, swap.  */
1172       if (cmp > 0)
1173         p1 = d1, d1 = d2, d2 = p1;
1174
1175       if (d1->success.first == 0)
1176         return 1;
1177       for (p1 = d1->success.first; p1; p1 = p1->next)
1178         if (maybe_both_true (p1, d2, 0))
1179           return 1;
1180
1181       return 0;
1182     }
1183
1184   /* Test the current level.  */
1185   cmp = maybe_both_true_1 (d1->tests, d2->tests);
1186   if (cmp >= 0)
1187     return cmp;
1188
1189   /* We can't prove that D1 and D2 cannot both be true.  If we are only
1190      to check the top level, return 1.  Otherwise, see if we can prove
1191      that all choices in both successors are mutually exclusive.  If
1192      either does not have any successors, we can't prove they can't both
1193      be true.  */
1194
1195   if (toplevel || d1->success.first == 0 || d2->success.first == 0)
1196     return 1;
1197
1198   for (p1 = d1->success.first; p1; p1 = p1->next)
1199     for (p2 = d2->success.first; p2; p2 = p2->next)
1200       if (maybe_both_true (p1, p2, 0))
1201         return 1;
1202
1203   return 0;
1204 }
1205
1206 /* A subroutine of nodes_identical.  Examine two tests for equivalence.  */
1207
1208 static int
1209 nodes_identical_1 (struct decision_test *d1, struct decision_test *d2)
1210 {
1211   switch (d1->type)
1212     {
1213     case DT_num_insns:
1214       return d1->u.num_insns == d2->u.num_insns;
1215
1216     case DT_mode:
1217       return d1->u.mode == d2->u.mode;
1218
1219     case DT_code:
1220       return d1->u.code == d2->u.code;
1221
1222     case DT_pred:
1223       return (d1->u.pred.mode == d2->u.pred.mode
1224               && strcmp (d1->u.pred.name, d2->u.pred.name) == 0);
1225
1226     case DT_c_test:
1227       return strcmp (d1->u.c_test, d2->u.c_test) == 0;
1228
1229     case DT_veclen:
1230     case DT_veclen_ge:
1231       return d1->u.veclen == d2->u.veclen;
1232
1233     case DT_dup:
1234       return d1->u.dup == d2->u.dup;
1235
1236     case DT_elt_zero_int:
1237     case DT_elt_one_int:
1238     case DT_elt_zero_wide:
1239     case DT_elt_zero_wide_safe:
1240       return d1->u.intval == d2->u.intval;
1241
1242     case DT_accept_op:
1243       return d1->u.opno == d2->u.opno;
1244
1245     case DT_accept_insn:
1246       /* Differences will be handled in merge_accept_insn.  */
1247       return 1;
1248
1249     default:
1250       gcc_unreachable ();
1251     }
1252 }
1253
1254 /* True iff the two nodes are identical (on one level only).  Due
1255    to the way these lists are constructed, we shouldn't have to
1256    consider different orderings on the tests.  */
1257
1258 static int
1259 nodes_identical (struct decision *d1, struct decision *d2)
1260 {
1261   struct decision_test *t1, *t2;
1262
1263   for (t1 = d1->tests, t2 = d2->tests; t1 && t2; t1 = t1->next, t2 = t2->next)
1264     {
1265       if (t1->type != t2->type)
1266         return 0;
1267       if (! nodes_identical_1 (t1, t2))
1268         return 0;
1269     }
1270
1271   /* For success, they should now both be null.  */
1272   if (t1 != t2)
1273     return 0;
1274
1275   /* Check that their subnodes are at the same position, as any one set
1276      of sibling decisions must be at the same position.  Allowing this
1277      requires complications to find_afterward and when change_state is
1278      invoked.  */
1279   if (d1->success.first
1280       && d2->success.first
1281       && d1->success.first->position != d2->success.first->position)
1282     return 0;
1283
1284   return 1;
1285 }
1286
1287 /* A subroutine of merge_trees; given two nodes that have been declared
1288    identical, cope with two insn accept states.  If they differ in the
1289    number of clobbers, then the conflict was created by make_insn_sequence
1290    and we can drop the with-clobbers version on the floor.  If both
1291    nodes have no additional clobbers, we have found an ambiguity in the
1292    source machine description.  */
1293
1294 static void
1295 merge_accept_insn (struct decision *oldd, struct decision *addd)
1296 {
1297   struct decision_test *old, *add;
1298
1299   for (old = oldd->tests; old; old = old->next)
1300     if (old->type == DT_accept_insn)
1301       break;
1302   if (old == NULL)
1303     return;
1304
1305   for (add = addd->tests; add; add = add->next)
1306     if (add->type == DT_accept_insn)
1307       break;
1308   if (add == NULL)
1309     return;
1310
1311   /* If one node is for a normal insn and the second is for the base
1312      insn with clobbers stripped off, the second node should be ignored.  */
1313
1314   if (old->u.insn.num_clobbers_to_add == 0
1315       && add->u.insn.num_clobbers_to_add > 0)
1316     {
1317       /* Nothing to do here.  */
1318     }
1319   else if (old->u.insn.num_clobbers_to_add > 0
1320            && add->u.insn.num_clobbers_to_add == 0)
1321     {
1322       /* In this case, replace OLD with ADD.  */
1323       old->u.insn = add->u.insn;
1324     }
1325   else
1326     {
1327       error_with_line (add->u.insn.lineno, "`%s' matches `%s'",
1328                        get_insn_name (add->u.insn.code_number),
1329                        get_insn_name (old->u.insn.code_number));
1330       message_with_line (old->u.insn.lineno, "previous definition of `%s'",
1331                          get_insn_name (old->u.insn.code_number));
1332     }
1333 }
1334
1335 /* Merge two decision trees OLDH and ADDH, modifying OLDH destructively.  */
1336
1337 static void
1338 merge_trees (struct decision_head *oldh, struct decision_head *addh)
1339 {
1340   struct decision *next, *add;
1341
1342   if (addh->first == 0)
1343     return;
1344   if (oldh->first == 0)
1345     {
1346       *oldh = *addh;
1347       return;
1348     }
1349
1350   /* Trying to merge bits at different positions isn't possible.  */
1351   gcc_assert (oldh->first->position == addh->first->position);
1352
1353   for (add = addh->first; add ; add = next)
1354     {
1355       struct decision *old, *insert_before = NULL;
1356
1357       next = add->next;
1358
1359       /* The semantics of pattern matching state that the tests are
1360          done in the order given in the MD file so that if an insn
1361          matches two patterns, the first one will be used.  However,
1362          in practice, most, if not all, patterns are unambiguous so
1363          that their order is independent.  In that case, we can merge
1364          identical tests and group all similar modes and codes together.
1365
1366          Scan starting from the end of OLDH until we reach a point
1367          where we reach the head of the list or where we pass a
1368          pattern that could also be true if NEW is true.  If we find
1369          an identical pattern, we can merge them.  Also, record the
1370          last node that tests the same code and mode and the last one
1371          that tests just the same mode.
1372
1373          If we have no match, place NEW after the closest match we found.  */
1374
1375       for (old = oldh->last; old; old = old->prev)
1376         {
1377           if (nodes_identical (old, add))
1378             {
1379               merge_accept_insn (old, add);
1380               merge_trees (&old->success, &add->success);
1381               goto merged_nodes;
1382             }
1383
1384           if (maybe_both_true (old, add, 0))
1385             break;
1386
1387           /* Insert the nodes in DT test type order, which is roughly
1388              how expensive/important the test is.  Given that the tests
1389              are also ordered within the list, examining the first is
1390              sufficient.  */
1391           if ((int) add->tests->type < (int) old->tests->type)
1392             insert_before = old;
1393         }
1394
1395       if (insert_before == NULL)
1396         {
1397           add->next = NULL;
1398           add->prev = oldh->last;
1399           oldh->last->next = add;
1400           oldh->last = add;
1401         }
1402       else
1403         {
1404           if ((add->prev = insert_before->prev) != NULL)
1405             add->prev->next = add;
1406           else
1407             oldh->first = add;
1408           add->next = insert_before;
1409           insert_before->prev = add;
1410         }
1411
1412     merged_nodes:;
1413     }
1414 }
1415 \f
1416 /* Walk the tree looking for sub-nodes that perform common tests.
1417    Factor out the common test into a new node.  This enables us
1418    (depending on the test type) to emit switch statements later.  */
1419
1420 static void
1421 factor_tests (struct decision_head *head)
1422 {
1423   struct decision *first, *next;
1424
1425   for (first = head->first; first && first->next; first = next)
1426     {
1427       enum decision_type type;
1428       struct decision *new_dec, *old_last;
1429
1430       type = first->tests->type;
1431       next = first->next;
1432
1433       /* Want at least two compatible sequential nodes.  */
1434       if (next->tests->type != type)
1435         continue;
1436
1437       /* Don't want all node types, just those we can turn into
1438          switch statements.  */
1439       if (type != DT_mode
1440           && type != DT_code
1441           && type != DT_veclen
1442           && type != DT_elt_zero_int
1443           && type != DT_elt_one_int
1444           && type != DT_elt_zero_wide_safe)
1445         continue;
1446
1447       /* If we'd been performing more than one test, create a new node
1448          below our first test.  */
1449       if (first->tests->next != NULL)
1450         {
1451           new_dec = new_decision (first->position, &first->success);
1452           new_dec->tests = first->tests->next;
1453           first->tests->next = NULL;
1454         }
1455
1456       /* Crop the node tree off after our first test.  */
1457       first->next = NULL;
1458       old_last = head->last;
1459       head->last = first;
1460
1461       /* For each compatible test, adjust to perform only one test in
1462          the top level node, then merge the node back into the tree.  */
1463       do
1464         {
1465           struct decision_head h;
1466
1467           if (next->tests->next != NULL)
1468             {
1469               new_dec = new_decision (next->position, &next->success);
1470               new_dec->tests = next->tests->next;
1471               next->tests->next = NULL;
1472             }
1473           new_dec = next;
1474           next = next->next;
1475           new_dec->next = NULL;
1476           h.first = h.last = new_dec;
1477
1478           merge_trees (head, &h);
1479         }
1480       while (next && next->tests->type == type);
1481
1482       /* After we run out of compatible tests, graft the remaining nodes
1483          back onto the tree.  */
1484       if (next)
1485         {
1486           next->prev = head->last;
1487           head->last->next = next;
1488           head->last = old_last;
1489         }
1490     }
1491
1492   /* Recurse.  */
1493   for (first = head->first; first; first = first->next)
1494     factor_tests (&first->success);
1495 }
1496
1497 /* After factoring, try to simplify the tests on any one node.
1498    Tests that are useful for switch statements are recognizable
1499    by having only a single test on a node -- we'll be manipulating
1500    nodes with multiple tests:
1501
1502    If we have mode tests or code tests that are redundant with
1503    predicates, remove them.  */
1504
1505 static void
1506 simplify_tests (struct decision_head *head)
1507 {
1508   struct decision *tree;
1509
1510   for (tree = head->first; tree; tree = tree->next)
1511     {
1512       struct decision_test *a, *b;
1513
1514       a = tree->tests;
1515       b = a->next;
1516       if (b == NULL)
1517         continue;
1518
1519       /* Find a predicate node.  */
1520       while (b && b->type != DT_pred)
1521         b = b->next;
1522       if (b)
1523         {
1524           /* Due to how these tests are constructed, we don't even need
1525              to check that the mode and code are compatible -- they were
1526              generated from the predicate in the first place.  */
1527           while (a->type == DT_mode || a->type == DT_code)
1528             a = a->next;
1529           tree->tests = a;
1530         }
1531     }
1532
1533   /* Recurse.  */
1534   for (tree = head->first; tree; tree = tree->next)
1535     simplify_tests (&tree->success);
1536 }
1537
1538 /* Count the number of subnodes of HEAD.  If the number is high enough,
1539    make the first node in HEAD start a separate subroutine in the C code
1540    that is generated.  */
1541
1542 static int
1543 break_out_subroutines (struct decision_head *head, int initial)
1544 {
1545   int size = 0;
1546   struct decision *sub;
1547
1548   for (sub = head->first; sub; sub = sub->next)
1549     size += 1 + break_out_subroutines (&sub->success, 0);
1550
1551   if (size > SUBROUTINE_THRESHOLD && ! initial)
1552     {
1553       head->first->subroutine_number = ++next_subroutine_number;
1554       size = 1;
1555     }
1556   return size;
1557 }
1558
1559 /* For each node p, find the next alternative that might be true
1560    when p is true.  */
1561
1562 static void
1563 find_afterward (struct decision_head *head, struct decision *real_afterward)
1564 {
1565   struct decision *p, *q, *afterward;
1566
1567   /* We can't propagate alternatives across subroutine boundaries.
1568      This is not incorrect, merely a minor optimization loss.  */
1569
1570   p = head->first;
1571   afterward = (p->subroutine_number > 0 ? NULL : real_afterward);
1572
1573   for ( ; p ; p = p->next)
1574     {
1575       /* Find the next node that might be true if this one fails.  */
1576       for (q = p->next; q ; q = q->next)
1577         if (maybe_both_true (p, q, 1))
1578           break;
1579
1580       /* If we reached the end of the list without finding one,
1581          use the incoming afterward position.  */
1582       if (!q)
1583         q = afterward;
1584       p->afterward = q;
1585       if (q)
1586         q->need_label = 1;
1587     }
1588
1589   /* Recurse.  */
1590   for (p = head->first; p ; p = p->next)
1591     if (p->success.first)
1592       find_afterward (&p->success, p->afterward);
1593
1594   /* When we are generating a subroutine, record the real afterward
1595      position in the first node where write_tree can find it, and we
1596      can do the right thing at the subroutine call site.  */
1597   p = head->first;
1598   if (p->subroutine_number > 0)
1599     p->afterward = real_afterward;
1600 }
1601 \f
1602 /* Assuming that the state of argument is denoted by OLDPOS, take whatever
1603    actions are necessary to move to NEWPOS.  If we fail to move to the
1604    new state, branch to node AFTERWARD if nonzero, otherwise return.
1605
1606    Failure to move to the new state can only occur if we are trying to
1607    match multiple insns and we try to step past the end of the stream.  */
1608
1609 static void
1610 change_state (struct position *oldpos, struct position *newpos,
1611               const char *indent)
1612 {
1613   while (oldpos->depth > newpos->depth)
1614     oldpos = oldpos->base;
1615
1616   if (oldpos != newpos)
1617     switch (newpos->type)
1618       {
1619       case POS_PEEP2_INSN:
1620         printf ("%stem = peep2_next_insn (%d);\n", indent, newpos->arg);
1621         printf ("%sx%d = PATTERN (tem);\n", indent, newpos->depth);
1622         break;
1623
1624       case POS_XEXP:
1625         change_state (oldpos, newpos->base, indent);
1626         printf ("%sx%d = XEXP (x%d, %d);\n",
1627                 indent, newpos->depth, newpos->depth - 1, newpos->arg);
1628         break;
1629
1630       case POS_XVECEXP0:
1631         change_state (oldpos, newpos->base, indent);
1632         printf ("%sx%d = XVECEXP (x%d, 0, %d);\n",
1633                 indent, newpos->depth, newpos->depth - 1, newpos->arg);
1634         break;
1635     }
1636 }
1637 \f
1638 /* Print the enumerator constant for CODE -- the upcase version of
1639    the name.  */
1640
1641 static void
1642 print_code (enum rtx_code code)
1643 {
1644   const char *p;
1645   for (p = GET_RTX_NAME (code); *p; p++)
1646     putchar (TOUPPER (*p));
1647 }
1648
1649 /* Emit code to cross an afterward link -- change state and branch.  */
1650
1651 static void
1652 write_afterward (struct decision *start, struct decision *afterward,
1653                  const char *indent)
1654 {
1655   if (!afterward || start->subroutine_number > 0)
1656     printf ("%sgoto ret0;\n", indent);
1657   else
1658     {
1659       change_state (start->position, afterward->position, indent);
1660       printf ("%sgoto L%d;\n", indent, afterward->number);
1661     }
1662 }
1663
1664 /* Emit a HOST_WIDE_INT as an integer constant expression.  We need to take
1665    special care to avoid "decimal constant is so large that it is unsigned"
1666    warnings in the resulting code.  */
1667
1668 static void
1669 print_host_wide_int (HOST_WIDE_INT val)
1670 {
1671   HOST_WIDE_INT min = (unsigned HOST_WIDE_INT)1 << (HOST_BITS_PER_WIDE_INT-1);
1672   if (val == min)
1673     printf ("(" HOST_WIDE_INT_PRINT_DEC_C "-1)", val + 1);
1674   else
1675     printf (HOST_WIDE_INT_PRINT_DEC_C, val);
1676 }
1677
1678 /* Emit a switch statement, if possible, for an initial sequence of
1679    nodes at START.  Return the first node yet untested.  */
1680
1681 static struct decision *
1682 write_switch (struct decision *start, int depth)
1683 {
1684   struct decision *p = start;
1685   enum decision_type type = p->tests->type;
1686   struct decision *needs_label = NULL;
1687
1688   /* If we have two or more nodes in sequence that test the same one
1689      thing, we may be able to use a switch statement.  */
1690
1691   if (!p->next
1692       || p->tests->next
1693       || p->next->tests->type != type
1694       || p->next->tests->next
1695       || nodes_identical_1 (p->tests, p->next->tests))
1696     return p;
1697
1698   /* DT_code is special in that we can do interesting things with
1699      known predicates at the same time.  */
1700   if (type == DT_code)
1701     {
1702       char codemap[NUM_RTX_CODE];
1703       struct decision *ret;
1704       RTX_CODE code;
1705
1706       memset (codemap, 0, sizeof (codemap));
1707
1708       printf ("  switch (GET_CODE (x%d))\n    {\n", depth);
1709       code = p->tests->u.code;
1710       do
1711         {
1712           if (p != start && p->need_label && needs_label == NULL)
1713             needs_label = p;
1714
1715           printf ("    case ");
1716           print_code (code);
1717           printf (":\n      goto L%d;\n", p->success.first->number);
1718           p->success.first->need_label = 1;
1719
1720           codemap[code] = 1;
1721           p = p->next;
1722         }
1723       while (p
1724              && ! p->tests->next
1725              && p->tests->type == DT_code
1726              && ! codemap[code = p->tests->u.code]);
1727
1728       /* If P is testing a predicate that we know about and we haven't
1729          seen any of the codes that are valid for the predicate, we can
1730          write a series of "case" statement, one for each possible code.
1731          Since we are already in a switch, these redundant tests are very
1732          cheap and will reduce the number of predicates called.  */
1733
1734       /* Note that while we write out cases for these predicates here,
1735          we don't actually write the test here, as it gets kinda messy.
1736          It is trivial to leave this to later by telling our caller that
1737          we only processed the CODE tests.  */
1738       if (needs_label != NULL)
1739         ret = needs_label;
1740       else
1741         ret = p;
1742
1743       while (p && p->tests->type == DT_pred && p->tests->u.pred.data)
1744         {
1745           const struct pred_data *data = p->tests->u.pred.data;
1746           int c;
1747
1748           for (c = 0; c < NUM_RTX_CODE; c++)
1749             if (codemap[c] && data->codes[c])
1750               goto pred_done;
1751
1752           for (c = 0; c < NUM_RTX_CODE; c++)
1753             if (data->codes[c])
1754               {
1755                 fputs ("    case ", stdout);
1756                 print_code ((enum rtx_code) c);
1757                 fputs (":\n", stdout);
1758                 codemap[c] = 1;
1759               }
1760
1761           printf ("      goto L%d;\n", p->number);
1762           p->need_label = 1;
1763           p = p->next;
1764         }
1765
1766     pred_done:
1767       /* Make the default case skip the predicates we managed to match.  */
1768
1769       printf ("    default:\n");
1770       if (p != ret)
1771         {
1772           if (p)
1773             {
1774               printf ("      goto L%d;\n", p->number);
1775               p->need_label = 1;
1776             }
1777           else
1778             write_afterward (start, start->afterward, "      ");
1779         }
1780       else
1781         printf ("     break;\n");
1782       printf ("   }\n");
1783
1784       return ret;
1785     }
1786   else if (type == DT_mode
1787            || type == DT_veclen
1788            || type == DT_elt_zero_int
1789            || type == DT_elt_one_int
1790            || type == DT_elt_zero_wide_safe)
1791     {
1792       const char *indent = "";
1793
1794       /* We cast switch parameter to integer, so we must ensure that the value
1795          fits.  */
1796       if (type == DT_elt_zero_wide_safe)
1797         {
1798           indent = "  ";
1799           printf ("  if ((int) XWINT (x%d, 0) == XWINT (x%d, 0))\n",
1800                   depth, depth);
1801         }
1802       printf ("%s  switch (", indent);
1803       switch (type)
1804         {
1805         case DT_mode:
1806           printf ("GET_MODE (x%d)", depth);
1807           break;
1808         case DT_veclen:
1809           printf ("XVECLEN (x%d, 0)", depth);
1810           break;
1811         case DT_elt_zero_int:
1812           printf ("XINT (x%d, 0)", depth);
1813           break;
1814         case DT_elt_one_int:
1815           printf ("XINT (x%d, 1)", depth);
1816           break;
1817         case DT_elt_zero_wide_safe:
1818           /* Convert result of XWINT to int for portability since some C
1819              compilers won't do it and some will.  */
1820           printf ("(int) XWINT (x%d, 0)", depth);
1821           break;
1822         default:
1823           gcc_unreachable ();
1824         }
1825       printf (")\n%s    {\n", indent);
1826
1827       do
1828         {
1829           /* Merge trees will not unify identical nodes if their
1830              sub-nodes are at different levels.  Thus we must check
1831              for duplicate cases.  */
1832           struct decision *q;
1833           for (q = start; q != p; q = q->next)
1834             if (nodes_identical_1 (p->tests, q->tests))
1835               goto case_done;
1836
1837           if (p != start && p->need_label && needs_label == NULL)
1838             needs_label = p;
1839
1840           printf ("%s    case ", indent);
1841           switch (type)
1842             {
1843             case DT_mode:
1844               printf ("%smode", GET_MODE_NAME (p->tests->u.mode));
1845               break;
1846             case DT_veclen:
1847               printf ("%d", p->tests->u.veclen);
1848               break;
1849             case DT_elt_zero_int:
1850             case DT_elt_one_int:
1851             case DT_elt_zero_wide:
1852             case DT_elt_zero_wide_safe:
1853               print_host_wide_int (p->tests->u.intval);
1854               break;
1855             default:
1856               gcc_unreachable ();
1857             }
1858           printf (":\n%s      goto L%d;\n", indent, p->success.first->number);
1859           p->success.first->need_label = 1;
1860
1861           p = p->next;
1862         }
1863       while (p && p->tests->type == type && !p->tests->next);
1864
1865     case_done:
1866       printf ("%s    default:\n%s      break;\n%s    }\n",
1867               indent, indent, indent);
1868
1869       return needs_label != NULL ? needs_label : p;
1870     }
1871   else
1872     {
1873       /* None of the other tests are amenable.  */
1874       return p;
1875     }
1876 }
1877
1878 /* Emit code for one test.  */
1879
1880 static void
1881 write_cond (struct decision_test *p, int depth,
1882             enum routine_type subroutine_type)
1883 {
1884   switch (p->type)
1885     {
1886     case DT_num_insns:
1887       printf ("peep2_current_count >= %d", p->u.num_insns);
1888       break;
1889
1890     case DT_mode:
1891       printf ("GET_MODE (x%d) == %smode", depth, GET_MODE_NAME (p->u.mode));
1892       break;
1893
1894     case DT_code:
1895       printf ("GET_CODE (x%d) == ", depth);
1896       print_code (p->u.code);
1897       break;
1898
1899     case DT_veclen:
1900       printf ("XVECLEN (x%d, 0) == %d", depth, p->u.veclen);
1901       break;
1902
1903     case DT_elt_zero_int:
1904       printf ("XINT (x%d, 0) == %d", depth, (int) p->u.intval);
1905       break;
1906
1907     case DT_elt_one_int:
1908       printf ("XINT (x%d, 1) == %d", depth, (int) p->u.intval);
1909       break;
1910
1911     case DT_elt_zero_wide:
1912     case DT_elt_zero_wide_safe:
1913       printf ("XWINT (x%d, 0) == ", depth);
1914       print_host_wide_int (p->u.intval);
1915       break;
1916
1917     case DT_const_int:
1918       printf ("x%d == const_int_rtx[MAX_SAVED_CONST_INT + (%d)]",
1919               depth, (int) p->u.intval);
1920       break;
1921
1922     case DT_veclen_ge:
1923       printf ("XVECLEN (x%d, 0) >= %d", depth, p->u.veclen);
1924       break;
1925
1926     case DT_dup:
1927       printf ("rtx_equal_p (x%d, operands[%d])", depth, p->u.dup);
1928       break;
1929
1930     case DT_pred:
1931       printf ("%s (x%d, %smode)", p->u.pred.name, depth,
1932               GET_MODE_NAME (p->u.pred.mode));
1933       break;
1934
1935     case DT_c_test:
1936       print_c_condition (p->u.c_test);
1937       break;
1938
1939     case DT_accept_insn:
1940       gcc_assert (subroutine_type == RECOG);
1941       gcc_assert (p->u.insn.num_clobbers_to_add);
1942       printf ("pnum_clobbers != NULL");
1943       break;
1944
1945     default:
1946       gcc_unreachable ();
1947     }
1948 }
1949
1950 /* Emit code for one action.  The previous tests have succeeded;
1951    TEST is the last of the chain.  In the normal case we simply
1952    perform a state change.  For the `accept' tests we must do more work.  */
1953
1954 static void
1955 write_action (struct decision *p, struct decision_test *test,
1956               int depth, int uncond, struct decision *success,
1957               enum routine_type subroutine_type)
1958 {
1959   const char *indent;
1960   int want_close = 0;
1961
1962   if (uncond)
1963     indent = "  ";
1964   else if (test->type == DT_accept_op || test->type == DT_accept_insn)
1965     {
1966       fputs ("    {\n", stdout);
1967       indent = "      ";
1968       want_close = 1;
1969     }
1970   else
1971     indent = "    ";
1972
1973   if (test->type == DT_accept_op)
1974     {
1975       printf ("%soperands[%d] = x%d;\n", indent, test->u.opno, depth);
1976
1977       /* Only allow DT_accept_insn to follow.  */
1978       if (test->next)
1979         {
1980           test = test->next;
1981           gcc_assert (test->type == DT_accept_insn);
1982         }
1983     }
1984
1985   /* Sanity check that we're now at the end of the list of tests.  */
1986   gcc_assert (!test->next);
1987
1988   if (test->type == DT_accept_insn)
1989     {
1990       switch (subroutine_type)
1991         {
1992         case RECOG:
1993           if (test->u.insn.num_clobbers_to_add != 0)
1994             printf ("%s*pnum_clobbers = %d;\n",
1995                     indent, test->u.insn.num_clobbers_to_add);
1996           printf ("%sreturn %d;  /* %s */\n", indent,
1997                   test->u.insn.code_number,
1998                   get_insn_name (test->u.insn.code_number));
1999           break;
2000
2001         case SPLIT:
2002           printf ("%sreturn gen_split_%d (insn, operands);\n",
2003                   indent, test->u.insn.code_number);
2004           break;
2005
2006         case PEEPHOLE2:
2007           {
2008             int match_len = 0;
2009             struct position *pos;
2010
2011             for (pos = p->position; pos; pos = pos->base)
2012               if (pos->type == POS_PEEP2_INSN)
2013                 {
2014                   match_len = pos->arg;
2015                   break;
2016                 }
2017             printf ("%s*_pmatch_len = %d;\n", indent, match_len);
2018             printf ("%stem = gen_peephole2_%d (insn, operands);\n",
2019                     indent, test->u.insn.code_number);
2020             printf ("%sif (tem != 0)\n%s  return tem;\n", indent, indent);
2021           }
2022           break;
2023
2024         default:
2025           gcc_unreachable ();
2026         }
2027     }
2028   else
2029     {
2030       printf ("%sgoto L%d;\n", indent, success->number);
2031       success->need_label = 1;
2032     }
2033
2034   if (want_close)
2035     fputs ("    }\n", stdout);
2036 }
2037
2038 /* Return 1 if the test is always true and has no fallthru path.  Return -1
2039    if the test does have a fallthru path, but requires that the condition be
2040    terminated.  Otherwise return 0 for a normal test.  */
2041 /* ??? is_unconditional is a stupid name for a tri-state function.  */
2042
2043 static int
2044 is_unconditional (struct decision_test *t, enum routine_type subroutine_type)
2045 {
2046   if (t->type == DT_accept_op)
2047     return 1;
2048
2049   if (t->type == DT_accept_insn)
2050     {
2051       switch (subroutine_type)
2052         {
2053         case RECOG:
2054           return (t->u.insn.num_clobbers_to_add == 0);
2055         case SPLIT:
2056           return 1;
2057         case PEEPHOLE2:
2058           return -1;
2059         default:
2060           gcc_unreachable ();
2061         }
2062     }
2063
2064   return 0;
2065 }
2066
2067 /* Emit code for one node -- the conditional and the accompanying action.
2068    Return true if there is no fallthru path.  */
2069
2070 static int
2071 write_node (struct decision *p, int depth,
2072             enum routine_type subroutine_type)
2073 {
2074   struct decision_test *test, *last_test;
2075   int uncond;
2076
2077   /* Scan the tests and simplify comparisons against small
2078      constants.  */
2079   for (test = p->tests; test; test = test->next)
2080     {
2081       if (test->type == DT_code
2082           && test->u.code == CONST_INT
2083           && test->next
2084           && test->next->type == DT_elt_zero_wide_safe
2085           && -MAX_SAVED_CONST_INT <= test->next->u.intval
2086           && test->next->u.intval <= MAX_SAVED_CONST_INT)
2087         {
2088           test->type = DT_const_int;
2089           test->u.intval = test->next->u.intval;
2090           test->next = test->next->next;
2091         }
2092     }
2093
2094   last_test = test = p->tests;
2095   uncond = is_unconditional (test, subroutine_type);
2096   if (uncond == 0)
2097     {
2098       printf ("  if (");
2099       write_cond (test, depth, subroutine_type);
2100
2101       while ((test = test->next) != NULL)
2102         {
2103           last_test = test;
2104           if (is_unconditional (test, subroutine_type))
2105             break;
2106
2107           printf ("\n      && ");
2108           write_cond (test, depth, subroutine_type);
2109         }
2110
2111       printf (")\n");
2112     }
2113
2114   write_action (p, last_test, depth, uncond, p->success.first, subroutine_type);
2115
2116   return uncond > 0;
2117 }
2118
2119 /* Emit code for all of the sibling nodes of HEAD.  */
2120
2121 static void
2122 write_tree_1 (struct decision_head *head, int depth,
2123               enum routine_type subroutine_type)
2124 {
2125   struct decision *p, *next;
2126   int uncond = 0;
2127
2128   for (p = head->first; p ; p = next)
2129     {
2130       /* The label for the first element was printed in write_tree.  */
2131       if (p != head->first && p->need_label)
2132         OUTPUT_LABEL (" ", p->number);
2133
2134       /* Attempt to write a switch statement for a whole sequence.  */
2135       next = write_switch (p, depth);
2136       if (p != next)
2137         uncond = 0;
2138       else
2139         {
2140           /* Failed -- fall back and write one node.  */
2141           uncond = write_node (p, depth, subroutine_type);
2142           next = p->next;
2143         }
2144     }
2145
2146   /* Finished with this chain.  Close a fallthru path by branching
2147      to the afterward node.  */
2148   if (! uncond)
2149     write_afterward (head->last, head->last->afterward, "  ");
2150 }
2151
2152 /* Write out the decision tree starting at HEAD.  PREVPOS is the
2153    position at the node that branched to this node.  */
2154
2155 static void
2156 write_tree (struct decision_head *head, struct position *prevpos,
2157             enum routine_type type, int initial)
2158 {
2159   struct decision *p = head->first;
2160
2161   putchar ('\n');
2162   if (p->need_label)
2163     OUTPUT_LABEL (" ", p->number);
2164
2165   if (! initial && p->subroutine_number > 0)
2166     {
2167       static const char * const name_prefix[] = {
2168           "recog", "split", "peephole2"
2169       };
2170
2171       static const char * const call_suffix[] = {
2172           ", pnum_clobbers", "", ", _pmatch_len"
2173       };
2174
2175       /* This node has been broken out into a separate subroutine.
2176          Call it, test the result, and branch accordingly.  */
2177
2178       if (p->afterward)
2179         {
2180           printf ("  tem = %s_%d (x0, insn%s);\n",
2181                   name_prefix[type], p->subroutine_number, call_suffix[type]);
2182           if (IS_SPLIT (type))
2183             printf ("  if (tem != 0)\n    return tem;\n");
2184           else
2185             printf ("  if (tem >= 0)\n    return tem;\n");
2186
2187           change_state (p->position, p->afterward->position, "  ");
2188           printf ("  goto L%d;\n", p->afterward->number);
2189         }
2190       else
2191         {
2192           printf ("  return %s_%d (x0, insn%s);\n",
2193                   name_prefix[type], p->subroutine_number, call_suffix[type]);
2194         }
2195     }
2196   else
2197     {
2198       change_state (prevpos, p->position, "  ");
2199       write_tree_1 (head, p->position->depth, type);
2200
2201       for (p = head->first; p; p = p->next)
2202         if (p->success.first)
2203           write_tree (&p->success, p->position, type, 0);
2204     }
2205 }
2206
2207 /* Write out a subroutine of type TYPE to do comparisons starting at
2208    node TREE.  */
2209
2210 static void
2211 write_subroutine (struct decision_head *head, enum routine_type type)
2212 {
2213   int subfunction = head->first ? head->first->subroutine_number : 0;
2214   const char *s_or_e;
2215   char extension[32];
2216   int i;
2217   const char *insn_param;
2218
2219   s_or_e = subfunction ? "static " : "";
2220
2221   if (subfunction)
2222     sprintf (extension, "_%d", subfunction);
2223   else if (type == RECOG)
2224     extension[0] = '\0';
2225   else
2226     strcpy (extension, "_insns");
2227
2228   /* For now, the top-level functions take a plain "rtx", and perform a
2229      checked cast to "rtx_insn *" for use throughout the rest of the
2230      function and the code it calls.  */
2231   insn_param = subfunction ? "rtx_insn *insn" : "rtx uncast_insn";
2232
2233   switch (type)
2234     {
2235     case RECOG:
2236       printf ("%sint\n\
2237 recog%s (rtx x0 ATTRIBUTE_UNUSED,\n\t%s ATTRIBUTE_UNUSED,\n\tint *pnum_clobbers ATTRIBUTE_UNUSED)\n",
2238               s_or_e, extension, insn_param);
2239       break;
2240     case SPLIT:
2241       printf ("%srtx\n\
2242 split%s (rtx x0 ATTRIBUTE_UNUSED, %s ATTRIBUTE_UNUSED)\n",
2243               s_or_e, extension, insn_param);
2244       break;
2245     case PEEPHOLE2:
2246       printf ("%srtx\n\
2247 peephole2%s (rtx x0 ATTRIBUTE_UNUSED,\n\t%s ATTRIBUTE_UNUSED,\n\tint *_pmatch_len ATTRIBUTE_UNUSED)\n",
2248               s_or_e, extension, insn_param);
2249       break;
2250     }
2251
2252   printf ("{\n  rtx * const operands ATTRIBUTE_UNUSED = &recog_data.operand[0];\n");
2253   for (i = 1; i <= max_depth; i++)
2254     printf ("  rtx x%d ATTRIBUTE_UNUSED;\n", i);
2255
2256   printf ("  %s tem ATTRIBUTE_UNUSED;\n", IS_SPLIT (type) ? "rtx" : "int");
2257
2258   if (!subfunction)
2259     printf ("  recog_data.insn = NULL_RTX;\n");
2260
2261   /* For now add the downcast to rtx_insn *, at the top of each top-level
2262      function.  */
2263   if (!subfunction)
2264     {
2265       printf ("  rtx_insn *insn ATTRIBUTE_UNUSED;\n");
2266       printf ("  insn = safe_as_a <rtx_insn *> (uncast_insn);\n");
2267     }
2268
2269   if (head->first)
2270     write_tree (head, &root_pos, type, 1);
2271   else
2272     printf ("  goto ret0;\n");
2273
2274   printf (" ret0:\n  return %d;\n}\n\n", IS_SPLIT (type) ? 0 : -1);
2275 }
2276
2277 /* In break_out_subroutines, we discovered the boundaries for the
2278    subroutines, but did not write them out.  Do so now.  */
2279
2280 static void
2281 write_subroutines (struct decision_head *head, enum routine_type type)
2282 {
2283   struct decision *p;
2284
2285   for (p = head->first; p ; p = p->next)
2286     if (p->success.first)
2287       write_subroutines (&p->success, type);
2288
2289   if (head->first->subroutine_number > 0)
2290     write_subroutine (head, type);
2291 }
2292
2293 /* Begin the output file.  */
2294
2295 static void
2296 write_header (void)
2297 {
2298   puts ("\
2299 /* Generated automatically by the program `genrecog' from the target\n\
2300    machine description file.  */\n\
2301 \n\
2302 #include \"config.h\"\n\
2303 #include \"system.h\"\n\
2304 #include \"coretypes.h\"\n\
2305 #include \"tm.h\"\n\
2306 #include \"rtl.h\"\n\
2307 #include \"tm_p.h\"\n\
2308 #include \"hashtab.h\"\n\
2309 #include \"hash-set.h\"\n\
2310 #include \"vec.h\"\n\
2311 #include \"machmode.h\"\n\
2312 #include \"hard-reg-set.h\"\n\
2313 #include \"input.h\"\n\
2314 #include \"function.h\"\n\
2315 #include \"insn-config.h\"\n\
2316 #include \"recog.h\"\n\
2317 #include \"output.h\"\n\
2318 #include \"flags.h\"\n\
2319 #include \"hard-reg-set.h\"\n\
2320 #include \"predict.h\"\n\
2321 #include \"basic-block.h\"\n\
2322 #include \"resource.h\"\n\
2323 #include \"diagnostic-core.h\"\n\
2324 #include \"reload.h\"\n\
2325 #include \"regs.h\"\n\
2326 #include \"tm-constrs.h\"\n\
2327 #include \"predict.h\"\n\
2328 \n");
2329
2330   puts ("\n\
2331 /* `recog' contains a decision tree that recognizes whether the rtx\n\
2332    X0 is a valid instruction.\n\
2333 \n\
2334    recog returns -1 if the rtx is not valid.  If the rtx is valid, recog\n\
2335    returns a nonnegative number which is the insn code number for the\n\
2336    pattern that matched.  This is the same as the order in the machine\n\
2337    description of the entry that matched.  This number can be used as an\n\
2338    index into `insn_data' and other tables.\n");
2339   puts ("\
2340    The third argument to recog is an optional pointer to an int.  If\n\
2341    present, recog will accept a pattern if it matches except for missing\n\
2342    CLOBBER expressions at the end.  In that case, the value pointed to by\n\
2343    the optional pointer will be set to the number of CLOBBERs that need\n\
2344    to be added (it should be initialized to zero by the caller).  If it");
2345   puts ("\
2346    is set nonzero, the caller should allocate a PARALLEL of the\n\
2347    appropriate size, copy the initial entries, and call add_clobbers\n\
2348    (found in insn-emit.c) to fill in the CLOBBERs.\n\
2349 ");
2350
2351   puts ("\n\
2352    The function split_insns returns 0 if the rtl could not\n\
2353    be split or the split rtl as an INSN list if it can be.\n\
2354 \n\
2355    The function peephole2_insns returns 0 if the rtl could not\n\
2356    be matched. If there was a match, the new rtl is returned in an INSN list,\n\
2357    and LAST_INSN will point to the last recognized insn in the old sequence.\n\
2358 */\n\n");
2359 }
2360
2361 \f
2362 /* Construct and return a sequence of decisions
2363    that will recognize INSN.
2364
2365    TYPE says what type of routine we are recognizing (RECOG or SPLIT).  */
2366
2367 static struct decision_head
2368 make_insn_sequence (rtx insn, enum routine_type type)
2369 {
2370   rtx x;
2371   const char *c_test = XSTR (insn, type == RECOG ? 2 : 1);
2372   int truth = maybe_eval_c_test (c_test);
2373   struct decision *last;
2374   struct decision_test *test, **place;
2375   struct decision_head head;
2376   struct position *c_test_pos, **pos_ptr;
2377
2378   /* We should never see an insn whose C test is false at compile time.  */
2379   gcc_assert (truth);
2380
2381   c_test_pos = &root_pos;
2382   if (type == PEEPHOLE2)
2383     {
2384       int i, j;
2385
2386       /* peephole2 gets special treatment:
2387          - X always gets an outer parallel even if it's only one entry
2388          - we remove all traces of outer-level match_scratch and match_dup
2389            expressions here.  */
2390       x = rtx_alloc (PARALLEL);
2391       PUT_MODE (x, VOIDmode);
2392       XVEC (x, 0) = rtvec_alloc (XVECLEN (insn, 0));
2393       pos_ptr = &peep2_insn_pos_list;
2394       for (i = j = 0; i < XVECLEN (insn, 0); i++)
2395         {
2396           rtx tmp = XVECEXP (insn, 0, i);
2397           if (GET_CODE (tmp) != MATCH_SCRATCH && GET_CODE (tmp) != MATCH_DUP)
2398             {
2399               c_test_pos = next_position (pos_ptr, &root_pos,
2400                                           POS_PEEP2_INSN, j);
2401               XVECEXP (x, 0, j) = tmp;
2402               j++;
2403               pos_ptr = &c_test_pos->next;
2404             }
2405         }
2406       XVECLEN (x, 0) = j;
2407     }
2408   else if (XVECLEN (insn, type == RECOG) == 1)
2409     x = XVECEXP (insn, type == RECOG, 0);
2410   else
2411     {
2412       x = rtx_alloc (PARALLEL);
2413       XVEC (x, 0) = XVEC (insn, type == RECOG);
2414       PUT_MODE (x, VOIDmode);
2415     }
2416
2417   validate_pattern (x, insn, NULL_RTX, 0);
2418
2419   memset (&head, 0, sizeof (head));
2420   last = add_to_sequence (x, &head, &root_pos, type, 1);
2421
2422   /* Find the end of the test chain on the last node.  */
2423   for (test = last->tests; test->next; test = test->next)
2424     continue;
2425   place = &test->next;
2426
2427   /* Skip the C test if it's known to be true at compile time.  */
2428   if (truth == -1)
2429     {
2430       /* Need a new node if we have another test to add.  */
2431       if (test->type == DT_accept_op)
2432         {
2433           last = new_decision (c_test_pos, &last->success);
2434           place = &last->tests;
2435         }
2436       test = new_decision_test (DT_c_test, &place);
2437       test->u.c_test = c_test;
2438     }
2439
2440   test = new_decision_test (DT_accept_insn, &place);
2441   test->u.insn.code_number = next_insn_code;
2442   test->u.insn.lineno = pattern_lineno;
2443   test->u.insn.num_clobbers_to_add = 0;
2444
2445   switch (type)
2446     {
2447     case RECOG:
2448       /* If this is a DEFINE_INSN and X is a PARALLEL, see if it ends
2449          with a group of CLOBBERs of (hard) registers or MATCH_SCRATCHes.
2450          If so, set up to recognize the pattern without these CLOBBERs.  */
2451
2452       if (GET_CODE (x) == PARALLEL)
2453         {
2454           int i;
2455
2456           /* Find the last non-clobber in the parallel.  */
2457           for (i = XVECLEN (x, 0); i > 0; i--)
2458             {
2459               rtx y = XVECEXP (x, 0, i - 1);
2460               if (GET_CODE (y) != CLOBBER
2461                   || (!REG_P (XEXP (y, 0))
2462                       && GET_CODE (XEXP (y, 0)) != MATCH_SCRATCH))
2463                 break;
2464             }
2465
2466           if (i != XVECLEN (x, 0))
2467             {
2468               rtx new_rtx;
2469               struct decision_head clobber_head;
2470
2471               /* Build a similar insn without the clobbers.  */
2472               if (i == 1)
2473                 new_rtx = XVECEXP (x, 0, 0);
2474               else
2475                 {
2476                   int j;
2477
2478                   new_rtx = rtx_alloc (PARALLEL);
2479                   XVEC (new_rtx, 0) = rtvec_alloc (i);
2480                   for (j = i - 1; j >= 0; j--)
2481                     XVECEXP (new_rtx, 0, j) = XVECEXP (x, 0, j);
2482                 }
2483
2484               /* Recognize it.  */
2485               memset (&clobber_head, 0, sizeof (clobber_head));
2486               last = add_to_sequence (new_rtx, &clobber_head, &root_pos,
2487                                       type, 1);
2488
2489               /* Find the end of the test chain on the last node.  */
2490               for (test = last->tests; test->next; test = test->next)
2491                 continue;
2492
2493               /* We definitely have a new test to add -- create a new
2494                  node if needed.  */
2495               place = &test->next;
2496               if (test->type == DT_accept_op)
2497                 {
2498                   last = new_decision (&root_pos, &last->success);
2499                   place = &last->tests;
2500                 }
2501
2502               /* Skip the C test if it's known to be true at compile
2503                  time.  */
2504               if (truth == -1)
2505                 {
2506                   test = new_decision_test (DT_c_test, &place);
2507                   test->u.c_test = c_test;
2508                 }
2509
2510               test = new_decision_test (DT_accept_insn, &place);
2511               test->u.insn.code_number = next_insn_code;
2512               test->u.insn.lineno = pattern_lineno;
2513               test->u.insn.num_clobbers_to_add = XVECLEN (x, 0) - i;
2514
2515               merge_trees (&head, &clobber_head);
2516             }
2517         }
2518       break;
2519
2520     case SPLIT:
2521       /* Define the subroutine we will call below and emit in genemit.  */
2522       printf ("extern rtx gen_split_%d (rtx_insn *, rtx *);\n", next_insn_code);
2523       break;
2524
2525     case PEEPHOLE2:
2526       /* Define the subroutine we will call below and emit in genemit.  */
2527       printf ("extern rtx gen_peephole2_%d (rtx_insn *, rtx *);\n",
2528               next_insn_code);
2529       break;
2530     }
2531
2532   return head;
2533 }
2534
2535 static void
2536 process_tree (struct decision_head *head, enum routine_type subroutine_type)
2537 {
2538   if (head->first == NULL)
2539     {
2540       /* We can elide peephole2_insns, but not recog or split_insns.  */
2541       if (subroutine_type == PEEPHOLE2)
2542         return;
2543     }
2544   else
2545     {
2546       factor_tests (head);
2547
2548       next_subroutine_number = 0;
2549       break_out_subroutines (head, 1);
2550       find_afterward (head, NULL);
2551
2552       /* We run this after find_afterward, because find_afterward needs
2553          the redundant DT_mode tests on predicates to determine whether
2554          two tests can both be true or not.  */
2555       simplify_tests (head);
2556
2557       write_subroutines (head, subroutine_type);
2558     }
2559
2560   write_subroutine (head, subroutine_type);
2561 }
2562 \f
2563 extern int main (int, char **);
2564
2565 int
2566 main (int argc, char **argv)
2567 {
2568   rtx desc;
2569   struct decision_head recog_tree, split_tree, peephole2_tree, h;
2570
2571   progname = "genrecog";
2572
2573   memset (&recog_tree, 0, sizeof recog_tree);
2574   memset (&split_tree, 0, sizeof split_tree);
2575   memset (&peephole2_tree, 0, sizeof peephole2_tree);
2576
2577   if (!init_rtx_reader_args (argc, argv))
2578     return (FATAL_EXIT_CODE);
2579
2580   next_insn_code = 0;
2581
2582   write_header ();
2583
2584   /* Read the machine description.  */
2585
2586   while (1)
2587     {
2588       desc = read_md_rtx (&pattern_lineno, &next_insn_code);
2589       if (desc == NULL)
2590         break;
2591
2592       switch (GET_CODE (desc))
2593         {
2594         case DEFINE_INSN:
2595           h = make_insn_sequence (desc, RECOG);
2596           merge_trees (&recog_tree, &h);
2597           break;
2598
2599         case DEFINE_SPLIT:
2600           h = make_insn_sequence (desc, SPLIT);
2601           merge_trees (&split_tree, &h);
2602           break;
2603
2604         case DEFINE_PEEPHOLE2:
2605           h = make_insn_sequence (desc, PEEPHOLE2);
2606           merge_trees (&peephole2_tree, &h);
2607
2608         default:
2609           /* do nothing */;
2610         }
2611     }
2612
2613   if (have_error)
2614     return FATAL_EXIT_CODE;
2615
2616   puts ("\n\n");
2617
2618   process_tree (&recog_tree, RECOG);
2619   process_tree (&split_tree, SPLIT);
2620   process_tree (&peephole2_tree, PEEPHOLE2);
2621
2622   fflush (stdout);
2623   return (ferror (stdout) != 0 ? FATAL_EXIT_CODE : SUCCESS_EXIT_CODE);
2624 }
2625 \f
2626 static void
2627 debug_decision_2 (struct decision_test *test)
2628 {
2629   switch (test->type)
2630     {
2631     case DT_num_insns:
2632       fprintf (stderr, "num_insns=%d", test->u.num_insns);
2633       break;
2634     case DT_mode:
2635       fprintf (stderr, "mode=%s", GET_MODE_NAME (test->u.mode));
2636       break;
2637     case DT_code:
2638       fprintf (stderr, "code=%s", GET_RTX_NAME (test->u.code));
2639       break;
2640     case DT_veclen:
2641       fprintf (stderr, "veclen=%d", test->u.veclen);
2642       break;
2643     case DT_elt_zero_int:
2644       fprintf (stderr, "elt0_i=%d", (int) test->u.intval);
2645       break;
2646     case DT_elt_one_int:
2647       fprintf (stderr, "elt1_i=%d", (int) test->u.intval);
2648       break;
2649     case DT_elt_zero_wide:
2650       fprintf (stderr, "elt0_w=" HOST_WIDE_INT_PRINT_DEC, test->u.intval);
2651       break;
2652     case DT_elt_zero_wide_safe:
2653       fprintf (stderr, "elt0_ws=" HOST_WIDE_INT_PRINT_DEC, test->u.intval);
2654       break;
2655     case DT_veclen_ge:
2656       fprintf (stderr, "veclen>=%d", test->u.veclen);
2657       break;
2658     case DT_dup:
2659       fprintf (stderr, "dup=%d", test->u.dup);
2660       break;
2661     case DT_pred:
2662       fprintf (stderr, "pred=(%s,%s)",
2663                test->u.pred.name, GET_MODE_NAME (test->u.pred.mode));
2664       break;
2665     case DT_c_test:
2666       {
2667         char sub[16+4];
2668         strncpy (sub, test->u.c_test, sizeof (sub));
2669         memcpy (sub+16, "...", 4);
2670         fprintf (stderr, "c_test=\"%s\"", sub);
2671       }
2672       break;
2673     case DT_accept_op:
2674       fprintf (stderr, "A_op=%d", test->u.opno);
2675       break;
2676     case DT_accept_insn:
2677       fprintf (stderr, "A_insn=(%d,%d)",
2678                test->u.insn.code_number, test->u.insn.num_clobbers_to_add);
2679       break;
2680
2681     default:
2682       gcc_unreachable ();
2683     }
2684 }
2685
2686 static void
2687 debug_decision_1 (struct decision *d, int indent)
2688 {
2689   int i;
2690   struct decision_test *test;
2691
2692   if (d == NULL)
2693     {
2694       for (i = 0; i < indent; ++i)
2695         putc (' ', stderr);
2696       fputs ("(nil)\n", stderr);
2697       return;
2698     }
2699
2700   for (i = 0; i < indent; ++i)
2701     putc (' ', stderr);
2702
2703   putc ('{', stderr);
2704   test = d->tests;
2705   if (test)
2706     {
2707       debug_decision_2 (test);
2708       while ((test = test->next) != NULL)
2709         {
2710           fputs (" + ", stderr);
2711           debug_decision_2 (test);
2712         }
2713     }
2714   fprintf (stderr, "} %d n %d a %d\n", d->number,
2715            (d->next ? d->next->number : -1),
2716            (d->afterward ? d->afterward->number : -1));
2717 }
2718
2719 static void
2720 debug_decision_0 (struct decision *d, int indent, int maxdepth)
2721 {
2722   struct decision *n;
2723   int i;
2724
2725   if (maxdepth < 0)
2726     return;
2727   if (d == NULL)
2728     {
2729       for (i = 0; i < indent; ++i)
2730         putc (' ', stderr);
2731       fputs ("(nil)\n", stderr);
2732       return;
2733     }
2734
2735   debug_decision_1 (d, indent);
2736   for (n = d->success.first; n ; n = n->next)
2737     debug_decision_0 (n, indent + 2, maxdepth - 1);
2738 }
2739
2740 DEBUG_FUNCTION void
2741 debug_decision (struct decision *d)
2742 {
2743   debug_decision_0 (d, 0, 1000000);
2744 }
2745
2746 DEBUG_FUNCTION void
2747 debug_decision_list (struct decision *d)
2748 {
2749   while (d)
2750     {
2751       debug_decision_0 (d, 0, 0);
2752       d = d->next;
2753     }
2754 }