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