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