gcc/genrecog.c

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