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