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