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 as an INSN list.
  47
  48    This program also generates the function `peephole2_insns', which
  49    returns 0 if the rtl could not be matched.  If there was a match,
  50    the new rtl is returned in an INSN list, and LAST_INSN will point
  51    to the last recognized insn in the old sequence.  */
  52
  53 #include "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_C, 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_C, 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 as an INSN list 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 an INSN list,\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   int truth = maybe_eval_c_test (c_test);
2456   struct decision *last;
2457   struct decision_test *test, **place;
2458   struct decision_head head;
2459   char c_test_pos[2];
2460
2461   /* We should never see an insn whose C test is false at compile time.  */
2462   if (truth == 0)
2463     abort ();
2464
2465   record_insn_name (next_insn_code, (type == RECOG ? XSTR (insn, 0) : NULL));
2466
2467   c_test_pos[0] = '\0';
2468   if (type == PEEPHOLE2)
2469     {
2470       int i, j;
2471
2472       /* peephole2 gets special treatment:
2473          - X always gets an outer parallel even if it's only one entry
2474          - we remove all traces of outer-level match_scratch and match_dup
2475            expressions here.  */
2476       x = rtx_alloc (PARALLEL);
2477       PUT_MODE (x, VOIDmode);
2478       XVEC (x, 0) = rtvec_alloc (XVECLEN (insn, 0));
2479       for (i = j = 0; i < XVECLEN (insn, 0); i++)
2480         {
2481           rtx tmp = XVECEXP (insn, 0, i);
2482           if (GET_CODE (tmp) != MATCH_SCRATCH && GET_CODE (tmp) != MATCH_DUP)
2483             {
2484               XVECEXP (x, 0, j) = tmp;
2485               j++;
2486             }
2487         }
2488       XVECLEN (x, 0) = j;
2489
2490       c_test_pos[0] = 'A' + j - 1;
2491       c_test_pos[1] = '\0';
2492     }
2493   else if (XVECLEN (insn, type == RECOG) == 1)
2494     x = XVECEXP (insn, type == RECOG, 0);
2495   else
2496     {
2497       x = rtx_alloc (PARALLEL);
2498       XVEC (x, 0) = XVEC (insn, type == RECOG);
2499       PUT_MODE (x, VOIDmode);
2500     }
2501
2502   validate_pattern (x, insn, NULL_RTX, 0);
2503
2504   memset(&head, 0, sizeof(head));
2505   last = add_to_sequence (x, &head, "", type, 1);
2506
2507   /* Find the end of the test chain on the last node.  */
2508   for (test = last->tests; test->next; test = test->next)
2509     continue;
2510   place = &test->next;
2511
2512   /* Skip the C test if it's known to be true at compile time.  */
2513   if (truth == -1)
2514     {
2515       /* Need a new node if we have another test to add.  */
2516       if (test->type == DT_accept_op)
2517         {
2518           last = new_decision (c_test_pos, &last->success);
2519           place = &last->tests;
2520         }
2521       test = new_decision_test (DT_c_test, &place);
2522       test->u.c_test = c_test;
2523     }
2524
2525   test = new_decision_test (DT_accept_insn, &place);
2526   test->u.insn.code_number = next_insn_code;
2527   test->u.insn.lineno = pattern_lineno;
2528   test->u.insn.num_clobbers_to_add = 0;
2529
2530   switch (type)
2531     {
2532     case RECOG:
2533       /* If this is an DEFINE_INSN and X is a PARALLEL, see if it ends
2534          with a group of CLOBBERs of (hard) registers or MATCH_SCRATCHes.
2535          If so, set up to recognize the pattern without these CLOBBERs.  */
2536
2537       if (GET_CODE (x) == PARALLEL)
2538         {
2539           int i;
2540
2541           /* Find the last non-clobber in the parallel.  */
2542           for (i = XVECLEN (x, 0); i > 0; i--)
2543             {
2544               rtx y = XVECEXP (x, 0, i - 1);
2545               if (GET_CODE (y) != CLOBBER
2546                   || (GET_CODE (XEXP (y, 0)) != REG
2547                       && GET_CODE (XEXP (y, 0)) != MATCH_SCRATCH))
2548                 break;
2549             }
2550
2551           if (i != XVECLEN (x, 0))
2552             {
2553               rtx new;
2554               struct decision_head clobber_head;
2555
2556               /* Build a similar insn without the clobbers.  */
2557               if (i == 1)
2558                 new = XVECEXP (x, 0, 0);
2559               else
2560                 {
2561                   int j;
2562
2563                   new = rtx_alloc (PARALLEL);
2564                   XVEC (new, 0) = rtvec_alloc (i);
2565                   for (j = i - 1; j >= 0; j--)
2566                     XVECEXP (new, 0, j) = XVECEXP (x, 0, j);
2567                 }
2568
2569               /* Recognize it.  */
2570               memset (&clobber_head, 0, sizeof(clobber_head));
2571               last = add_to_sequence (new, &clobber_head, "", type, 1);
2572
2573               /* Find the end of the test chain on the last node.  */
2574               for (test = last->tests; test->next; test = test->next)
2575                 continue;
2576
2577               /* We definitely have a new test to add -- create a new
2578                  node if needed.  */
2579               place = &test->next;
2580               if (test->type == DT_accept_op)
2581                 {
2582                   last = new_decision ("", &last->success);
2583                   place = &last->tests;
2584                 }
2585
2586               /* Skip the C test if it's known to be true at compile
2587                  time.  */
2588               if (truth == -1)
2589                 {
2590                   test = new_decision_test (DT_c_test, &place);
2591                   test->u.c_test = c_test;
2592                 }
2593
2594               test = new_decision_test (DT_accept_insn, &place);
2595               test->u.insn.code_number = next_insn_code;
2596               test->u.insn.lineno = pattern_lineno;
2597               test->u.insn.num_clobbers_to_add = XVECLEN (x, 0) - i;
2598
2599               merge_trees (&head, &clobber_head);
2600             }
2601         }
2602       break;
2603
2604     case SPLIT:
2605       /* Define the subroutine we will call below and emit in genemit.  */
2606       printf ("extern rtx gen_split_%d PARAMS ((rtx *));\n", next_insn_code);
2607       break;
2608
2609     case PEEPHOLE2:
2610       /* Define the subroutine we will call below and emit in genemit.  */
2611       printf ("extern rtx gen_peephole2_%d PARAMS ((rtx, rtx *));\n",
2612               next_insn_code);
2613       break;
2614     }
2615
2616   return head;
2617 }
2618
2619 static void
2620 process_tree (head, subroutine_type)
2621      struct decision_head *head;
2622      enum routine_type subroutine_type;
2623 {
2624   if (head->first == NULL)
2625     {
2626       /* We can elide peephole2_insns, but not recog or split_insns.  */
2627       if (subroutine_type == PEEPHOLE2)
2628         return;
2629     }
2630   else
2631     {
2632       factor_tests (head);
2633
2634       next_subroutine_number = 0;
2635       break_out_subroutines (head, 1);
2636       find_afterward (head, NULL);
2637
2638       /* We run this after find_afterward, because find_afterward needs
2639          the redundant DT_mode tests on predicates to determine whether
2640          two tests can both be true or not.  */
2641       simplify_tests(head);
2642
2643       write_subroutines (head, subroutine_type);
2644     }
2645
2646   write_subroutine (head, subroutine_type);
2647 }
2648 \f
2649 extern int main PARAMS ((int, char **));
2650
2651 int
2652 main (argc, argv)
2653      int argc;
2654      char **argv;
2655 {
2656   rtx desc;
2657   struct decision_head recog_tree, split_tree, peephole2_tree, h;
2658
2659   progname = "genrecog";
2660
2661   memset (&recog_tree, 0, sizeof recog_tree);
2662   memset (&split_tree, 0, sizeof split_tree);
2663   memset (&peephole2_tree, 0, sizeof peephole2_tree);
2664
2665   if (argc <= 1)
2666     fatal ("no input file name");
2667
2668   if (init_md_reader_args (argc, argv) != SUCCESS_EXIT_CODE)
2669     return (FATAL_EXIT_CODE);
2670
2671   next_insn_code = 0;
2672   next_index = 0;
2673
2674   write_header ();
2675
2676   /* Read the machine description.  */
2677
2678   while (1)
2679     {
2680       desc = read_md_rtx (&pattern_lineno, &next_insn_code);
2681       if (desc == NULL)
2682         break;
2683
2684       if (GET_CODE (desc) == DEFINE_INSN)
2685         {
2686           h = make_insn_sequence (desc, RECOG);
2687           merge_trees (&recog_tree, &h);
2688         }
2689       else if (GET_CODE (desc) == DEFINE_SPLIT)
2690         {
2691           h = make_insn_sequence (desc, SPLIT);
2692           merge_trees (&split_tree, &h);
2693         }
2694       else if (GET_CODE (desc) == DEFINE_PEEPHOLE2)
2695         {
2696           h = make_insn_sequence (desc, PEEPHOLE2);
2697           merge_trees (&peephole2_tree, &h);
2698         }
2699
2700       next_index++;
2701     }
2702
2703   if (error_count)
2704     return FATAL_EXIT_CODE;
2705
2706   puts ("\n\n");
2707
2708   process_tree (&recog_tree, RECOG);
2709   process_tree (&split_tree, SPLIT);
2710   process_tree (&peephole2_tree, PEEPHOLE2);
2711
2712   fflush (stdout);
2713   return (ferror (stdout) != 0 ? FATAL_EXIT_CODE : SUCCESS_EXIT_CODE);
2714 }
2715 \f
2716 /* Define this so we can link with print-rtl.o to get debug_rtx function.  */
2717 const char *
2718 get_insn_name (code)
2719      int code;
2720 {
2721   if (code < insn_name_ptr_size)
2722     return insn_name_ptr[code];
2723   else
2724     return NULL;
2725 }
2726
2727 static void
2728 record_insn_name (code, name)
2729      int code;
2730      const char *name;
2731 {
2732   static const char *last_real_name = "insn";
2733   static int last_real_code = 0;
2734   char *new;
2735
2736   if (insn_name_ptr_size <= code)
2737     {
2738       int new_size;
2739       new_size = (insn_name_ptr_size ? insn_name_ptr_size * 2 : 512);
2740       insn_name_ptr =
2741         (char **) xrealloc (insn_name_ptr, sizeof(char *) * new_size);
2742       memset (insn_name_ptr + insn_name_ptr_size, 0,
2743               sizeof(char *) * (new_size - insn_name_ptr_size));
2744       insn_name_ptr_size = new_size;
2745     }
2746
2747   if (!name || name[0] == '\0')
2748     {
2749       new = xmalloc (strlen (last_real_name) + 10);
2750       sprintf (new, "%s+%d", last_real_name, code - last_real_code);
2751     }
2752   else
2753     {
2754       last_real_name = new = xstrdup (name);
2755       last_real_code = code;
2756     }
2757
2758   insn_name_ptr[code] = new;
2759 }
2760 \f
2761 static void
2762 debug_decision_2 (test)
2763      struct decision_test *test;
2764 {
2765   switch (test->type)
2766     {
2767     case DT_mode:
2768       fprintf (stderr, "mode=%s", GET_MODE_NAME (test->u.mode));
2769       break;
2770     case DT_code:
2771       fprintf (stderr, "code=%s", GET_RTX_NAME (test->u.code));
2772       break;
2773     case DT_veclen:
2774       fprintf (stderr, "veclen=%d", test->u.veclen);
2775       break;
2776     case DT_elt_zero_int:
2777       fprintf (stderr, "elt0_i=%d", (int) test->u.intval);
2778       break;
2779     case DT_elt_one_int:
2780       fprintf (stderr, "elt1_i=%d", (int) test->u.intval);
2781       break;
2782     case DT_elt_zero_wide:
2783       fprintf (stderr, "elt0_w=");
2784       fprintf (stderr, HOST_WIDE_INT_PRINT_DEC, test->u.intval);
2785       break;
2786     case DT_elt_zero_wide_safe:
2787       fprintf (stderr, "elt0_ws=");
2788       fprintf (stderr, HOST_WIDE_INT_PRINT_DEC, test->u.intval);
2789       break;
2790     case DT_veclen_ge:
2791       fprintf (stderr, "veclen>=%d", test->u.veclen);
2792       break;
2793     case DT_dup:
2794       fprintf (stderr, "dup=%d", test->u.dup);
2795       break;
2796     case DT_pred:
2797       fprintf (stderr, "pred=(%s,%s)",
2798                test->u.pred.name, GET_MODE_NAME(test->u.pred.mode));
2799       break;
2800     case DT_c_test:
2801       {
2802         char sub[16+4];
2803         strncpy (sub, test->u.c_test, sizeof(sub));
2804         memcpy (sub+16, "...", 4);
2805         fprintf (stderr, "c_test=\"%s\"", sub);
2806       }
2807       break;
2808     case DT_accept_op:
2809       fprintf (stderr, "A_op=%d", test->u.opno);
2810       break;
2811     case DT_accept_insn:
2812       fprintf (stderr, "A_insn=(%d,%d)",
2813                test->u.insn.code_number, test->u.insn.num_clobbers_to_add);
2814       break;
2815
2816     default:
2817       abort ();
2818     }
2819 }
2820
2821 static void
2822 debug_decision_1 (d, indent)
2823      struct decision *d;
2824      int indent;
2825 {
2826   int i;
2827   struct decision_test *test;
2828
2829   if (d == NULL)
2830     {
2831       for (i = 0; i < indent; ++i)
2832         putc (' ', stderr);
2833       fputs ("(nil)\n", stderr);
2834       return;
2835     }
2836
2837   for (i = 0; i < indent; ++i)
2838     putc (' ', stderr);
2839
2840   putc ('{', stderr);
2841   test = d->tests;
2842   if (test)
2843     {
2844       debug_decision_2 (test);
2845       while ((test = test->next) != NULL)
2846         {
2847           fputs (" + ", stderr);
2848           debug_decision_2 (test);
2849         }
2850     }
2851   fprintf (stderr, "} %d n %d a %d\n", d->number,
2852            (d->next ? d->next->number : -1),
2853            (d->afterward ? d->afterward->number : -1));
2854 }
2855
2856 static void
2857 debug_decision_0 (d, indent, maxdepth)
2858      struct decision *d;
2859      int indent, maxdepth;
2860 {
2861   struct decision *n;
2862   int i;
2863
2864   if (maxdepth < 0)
2865     return;
2866   if (d == NULL)
2867     {
2868       for (i = 0; i < indent; ++i)
2869         putc (' ', stderr);
2870       fputs ("(nil)\n", stderr);
2871       return;
2872     }
2873
2874   debug_decision_1 (d, indent);
2875   for (n = d->success.first; n ; n = n->next)
2876     debug_decision_0 (n, indent + 2, maxdepth - 1);
2877 }
2878
2879 void
2880 debug_decision (d)
2881      struct decision *d;
2882 {
2883   debug_decision_0 (d, 0, 1000000);
2884 }
2885
2886 void
2887 debug_decision_list (d)
2888      struct decision *d;
2889 {
2890   while (d)
2891     {
2892       debug_decision_0 (d, 0, 0);
2893       d = d->next;
2894     }
2895 }