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