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