gcc/genrecog.c

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