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