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