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