gcc/genrecog.c

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