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