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