gcc/genrecog.c

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