contrib/gcc-3.4/gcc/genrecog.c

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