gcc/genrecog.cc

   1 /* Generate code from machine description to recognize rtl as insns.
   2    Copyright (C) 1987-2022 Free Software Foundation, Inc.
   3
   4    This file is part of GCC.
   5
   6    GCC is free software; you can redistribute it and/or modify it
   7    under the terms of the GNU General Public License as published by
   8    the Free Software Foundation; either version 3, or (at your option)
   9    any later version.
  10
  11    GCC is distributed in the hope that it will be useful, but WITHOUT
  12    ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  13    or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
  14    License for more details.
  15
  16    You should have received a copy of the GNU General Public License
  17    along with GCC; see the file COPYING3.  If not see
  18    <http://www.gnu.org/licenses/>.  */
  19
  20
  21 /* This program is used to produce insn-recog.cc, which contains a
  22    function called `recog' plus its subroutines.  These functions
  23    contain a decision tree that recognizes whether an rtx, the
  24    argument given to recog, is a valid instruction.
  25
  26    recog returns -1 if the rtx is not valid.  If the rtx is valid,
  27    recog returns a nonnegative number which is the insn code number
  28    for the pattern that matched.  This is the same as the order in the
  29    machine description of the entry that matched.  This number can be
  30    used as an index into various insn_* tables, such as insn_template,
  31    insn_outfun, and insn_n_operands (found in insn-output.cc).
  32
  33    The third argument to recog is an optional pointer to an int.  If
  34    present, recog will accept a pattern if it matches except for
  35    missing CLOBBER expressions at the end.  In that case, the value
  36    pointed to by the optional pointer will be set to the number of
  37    CLOBBERs that need to be added (it should be initialized to zero by
  38    the caller).  If it is set nonzero, the caller should allocate a
  39    PARALLEL of the appropriate size, copy the initial entries, and
  40    call add_clobbers (found in insn-emit.cc) to fill in the CLOBBERs.
  41
  42    This program also generates the function `split_insns', which
  43    returns 0 if the rtl could not be split, or it returns the split
  44    rtl as an INSN list.
  45
  46    This program also generates the function `peephole2_insns', which
  47    returns 0 if the rtl could not be matched.  If there was a match,
  48    the new rtl is returned in an INSN list, and LAST_INSN will point
  49    to the last recognized insn in the old sequence.
  50
  51
  52    At a high level, the algorithm used in this file is as follows:
  53
  54    1. Build up a decision tree for each routine, using the following
  55       approach to matching an rtx:
  56
  57       - First determine the "shape" of the rtx, based on GET_CODE,
  58         XVECLEN and XINT.  This phase examines SET_SRCs before SET_DESTs
  59         since SET_SRCs tend to be more distinctive.  It examines other
  60         operands in numerical order, since the canonicalization rules
  61         prefer putting complex operands of commutative operators first.
  62
  63       - Next check modes and predicates.  This phase examines all
  64         operands in numerical order, even for SETs, since the mode of a
  65         SET_DEST is exact while the mode of a SET_SRC can be VOIDmode
  66         for constant integers.
  67
  68       - Next check match_dups.
  69
  70       - Finally check the C condition and (where appropriate) pnum_clobbers.
  71
  72    2. Try to optimize the tree by removing redundant tests, CSEing tests,
  73       folding tests together, etc.
  74
  75    3. Look for common subtrees and split them out into "pattern" routines.
  76       These common subtrees can be identical or they can differ in mode,
  77       code, or integer (usually an UNSPEC or UNSPEC_VOLATILE code).
  78       In the latter case the users of the pattern routine pass the
  79       appropriate mode, etc., as argument.  For example, if two patterns
  80       contain:
  81
  82          (plus:SI (match_operand:SI 1 "register_operand")
  83                   (match_operand:SI 2 "register_operand"))
  84
  85       we can split the associated matching code out into a subroutine.
  86       If a pattern contains:
  87
  88          (minus:DI (match_operand:DI 1 "register_operand")
  89                    (match_operand:DI 2 "register_operand"))
  90
  91       then we can consider using the same matching routine for both
  92       the plus and minus expressions, passing PLUS and SImode in the
  93       former case and MINUS and DImode in the latter case.
  94
  95       The main aim of this phase is to reduce the compile time of the
  96       insn-recog.cc code and to reduce the amount of object code in
  97       insn-recog.o.
  98
  99    4. Split the matching trees into functions, trying to limit the
 100       size of each function to a sensible amount.
 101
 102       Again, the main aim of this phase is to reduce the compile time
 103       of insn-recog.cc.  (It doesn't help with the size of insn-recog.o.)
 104
 105    5. Write out C++ code for each function.  */
 106
 107 #include "bconfig.h"
 108 #define INCLUDE_ALGORITHM
 109 #include "system.h"
 110 #include "coretypes.h"
 111 #include "tm.h"
 112 #include "rtl.h"
 113 #include "errors.h"
 114 #include "read-md.h"
 115 #include "gensupport.h"
 116
 117 #undef GENERATOR_FILE
 118 enum true_rtx_doe {
 119 #define DEF_RTL_EXPR(ENUM, NAME, FORMAT, CLASS) TRUE_##ENUM,
 120 #include "rtl.def"
 121 #undef DEF_RTL_EXPR
 122   FIRST_GENERATOR_RTX_CODE
 123 };
 124 #define NUM_TRUE_RTX_CODE ((int) FIRST_GENERATOR_RTX_CODE)
 125 #define GENERATOR_FILE 1
 126
 127 /* Debugging variables to control which optimizations are performed.
 128    Note that disabling merge_states_p leads to very large output.  */
 129 static const bool merge_states_p = true;
 130 static const bool collapse_optional_decisions_p = true;
 131 static const bool cse_tests_p = true;
 132 static const bool simplify_tests_p = true;
 133 static const bool use_operand_variables_p = true;
 134 static const bool use_subroutines_p = true;
 135 static const bool use_pattern_routines_p = true;
 136
 137 /* Whether to add comments for optional tests that we decided to keep.
 138    Can be useful when debugging the generator itself but is noise when
 139    debugging the generated code.  */
 140 static const bool mark_optional_transitions_p = false;
 141
 142 /* Whether pattern routines should calculate positions relative to their
 143    rtx parameter rather than use absolute positions.  This e.g. allows
 144    a pattern routine to be shared between a plain SET and a PARALLEL
 145    that includes a SET.
 146
 147    In principle it sounds like this should be useful, especially for
 148    recog_for_combine, where the plain SET form is generated automatically
 149    from a PARALLEL of a single SET and some CLOBBERs.  In practice it doesn't
 150    seem to help much and leads to slightly bigger object files.  */
 151 static const bool relative_patterns_p = false;
 152
 153 /* Whether pattern routines should be allowed to test whether pnum_clobbers
 154    is null.  This requires passing pnum_clobbers around as a parameter.  */
 155 static const bool pattern_have_num_clobbers_p = true;
 156
 157 /* Whether pattern routines should be allowed to test .md file C conditions.
 158    This requires passing insn around as a parameter, in case the C
 159    condition refers to it.  In practice this tends to lead to bigger
 160    object files.  */
 161 static const bool pattern_c_test_p = false;
 162
 163 /* Whether to require each parameter passed to a pattern routine to be
 164    unique.  Disabling this check for example allows unary operators with
 165    matching modes (like NEG) and unary operators with mismatched modes
 166    (like ZERO_EXTEND) to be matched by a single pattern.  However, we then
 167    often have cases where the same value is passed too many times.  */
 168 static const bool force_unique_params_p = true;
 169
 170 /* The maximum (approximate) depth of block nesting that an individual
 171    routine or subroutine should have.  This limit is about keeping the
 172    output readable rather than reducing compile time.  */
 173 static const unsigned int MAX_DEPTH = 6;
 174
 175 /* The minimum number of pseudo-statements that a state must have before
 176    we split it out into a subroutine.  */
 177 static const unsigned int MIN_NUM_STATEMENTS = 5;
 178
 179 /* The number of pseudo-statements a state can have before we consider
 180    splitting out substates into subroutines.  This limit is about avoiding
 181    compile-time problems with very big functions (and also about keeping
 182    functions within --param optimization limits, etc.).  */
 183 static const unsigned int MAX_NUM_STATEMENTS = 200;
 184
 185 /* The minimum number of pseudo-statements that can be used in a pattern
 186    routine.  */
 187 static const unsigned int MIN_COMBINE_COST = 4;
 188
 189 /* The maximum number of arguments that a pattern routine can have.
 190    The idea is to prevent one pattern getting a ridiculous number of
 191    arguments when it would be more beneficial to have a separate pattern
 192    routine instead.  */
 193 static const unsigned int MAX_PATTERN_PARAMS = 5;
 194
 195 /* The maximum operand number plus one.  */
 196 int num_operands;
 197
 198 /* Ways of obtaining an rtx to be tested.  */
 199 enum position_type {
 200   /* PATTERN (peep2_next_insn (ARG)).  */
 201   POS_PEEP2_INSN,
 202
 203   /* XEXP (BASE, ARG).  */
 204   POS_XEXP,
 205
 206   /* XVECEXP (BASE, 0, ARG).  */
 207   POS_XVECEXP0
 208 };
 209
 210 /* The position of an rtx relative to X0.  Each useful position is
 211    represented by exactly one instance of this structure.  */
 212 struct position
 213 {
 214   /* The parent rtx.  This is the root position for POS_PEEP2_INSNs.  */
 215   struct position *base;
 216
 217   /* A position with the same BASE and TYPE, but with the next value
 218      of ARG.  */
 219   struct position *next;
 220
 221   /* A list of all POS_XEXP positions that use this one as their base,
 222      chained by NEXT fields.  The first entry represents XEXP (this, 0),
 223      the second represents XEXP (this, 1), and so on.  */
 224   struct position *xexps;
 225
 226   /* A list of POS_XVECEXP0 positions that use this one as their base,
 227      chained by NEXT fields.  The first entry represents XVECEXP (this, 0, 0),
 228      the second represents XVECEXP (this, 0, 1), and so on.  */
 229   struct position *xvecexp0s;
 230
 231   /* The type of position.  */
 232   enum position_type type;
 233
 234   /* The argument to TYPE (shown as ARG in the position_type comments).  */
 235   int arg;
 236
 237   /* The instruction to which the position belongs.  */
 238   unsigned int insn_id;
 239
 240   /* The depth of this position relative to the instruction pattern.
 241      E.g. if the instruction pattern is a SET, the SET itself has a
 242      depth of 0 while the SET_DEST and SET_SRC have depths of 1.  */
 243   unsigned int depth;
 244
 245   /* A unique identifier for this position.  */
 246   unsigned int id;
 247 };
 248
 249 enum routine_type {
 250   SUBPATTERN, RECOG, SPLIT, PEEPHOLE2
 251 };
 252
 253 /* The root position (x0).  */
 254 static struct position root_pos;
 255
 256 /* The number of positions created.  Also one higher than the maximum
 257    position id.  */
 258 static unsigned int num_positions = 1;
 259
 260 /* A list of all POS_PEEP2_INSNs.  The entry for insn 0 is the root position,
 261    since we are given that instruction's pattern as x0.  */
 262 static struct position *peep2_insn_pos_list = &root_pos;
 263 \f
 264 /* Return a position with the given BASE, TYPE and ARG.  NEXT_PTR
 265    points to where the unique object that represents the position
 266    should be stored.  Create the object if it doesn't already exist,
 267    otherwise reuse the object that is already there.  */
 268
 269 static struct position *
 270 next_position (struct position **next_ptr, struct position *base,
 271                enum position_type type, int arg)
 272 {
 273   struct position *pos;
 274
 275   pos = *next_ptr;
 276   if (!pos)
 277     {
 278       pos = XCNEW (struct position);
 279       pos->type = type;
 280       pos->arg = arg;
 281       if (type == POS_PEEP2_INSN)
 282         {
 283           pos->base = 0;
 284           pos->insn_id = arg;
 285           pos->depth = base->depth;
 286         }
 287       else
 288         {
 289           pos->base = base;
 290           pos->insn_id = base->insn_id;
 291           pos->depth = base->depth + 1;
 292         }
 293       pos->id = num_positions++;
 294       *next_ptr = pos;
 295     }
 296   return pos;
 297 }
 298
 299 /* Compare positions POS1 and POS2 lexicographically.  */
 300
 301 static int
 302 compare_positions (struct position *pos1, struct position *pos2)
 303 {
 304   int diff;
 305
 306   diff = pos1->depth - pos2->depth;
 307   if (diff < 0)
 308     do
 309       pos2 = pos2->base;
 310     while (pos1->depth != pos2->depth);
 311   else if (diff > 0)
 312     do
 313       pos1 = pos1->base;
 314     while (pos1->depth != pos2->depth);
 315   while (pos1 != pos2)
 316     {
 317       diff = (int) pos1->type - (int) pos2->type;
 318       if (diff == 0)
 319         diff = pos1->arg - pos2->arg;
 320       pos1 = pos1->base;
 321       pos2 = pos2->base;
 322     }
 323   return diff;
 324 }
 325
 326 /* Return the most deeply-nested position that is common to both
 327    POS1 and POS2.  If the positions are from different instructions,
 328    return the one with the lowest insn_id.  */
 329
 330 static struct position *
 331 common_position (struct position *pos1, struct position *pos2)
 332 {
 333   if (pos1->insn_id != pos2->insn_id)
 334     return pos1->insn_id < pos2->insn_id ? pos1 : pos2;
 335   if (pos1->depth > pos2->depth)
 336     std::swap (pos1, pos2);
 337   while (pos1->depth != pos2->depth)
 338     pos2 = pos2->base;
 339   while (pos1 != pos2)
 340     {
 341       pos1 = pos1->base;
 342       pos2 = pos2->base;
 343     }
 344   return pos1;
 345 }
 346 \f
 347 /* Search for and return operand N, stop when reaching node STOP.  */
 348
 349 static rtx
 350 find_operand (rtx pattern, int n, rtx stop)
 351 {
 352   const char *fmt;
 353   RTX_CODE code;
 354   int i, j, len;
 355   rtx r;
 356
 357   if (pattern == stop)
 358     return stop;
 359
 360   code = GET_CODE (pattern);
 361   if ((code == MATCH_SCRATCH
 362        || code == MATCH_OPERAND
 363        || code == MATCH_OPERATOR
 364        || code == MATCH_PARALLEL)
 365       && XINT (pattern, 0) == n)
 366     return pattern;
 367
 368   fmt = GET_RTX_FORMAT (code);
 369   len = GET_RTX_LENGTH (code);
 370   for (i = 0; i < len; i++)
 371     {
 372       switch (fmt[i])
 373         {
 374         case 'e': case 'u':
 375           if ((r = find_operand (XEXP (pattern, i), n, stop)) != NULL_RTX)
 376             return r;
 377           break;
 378
 379         case 'V':
 380           if (! XVEC (pattern, i))
 381             break;
 382           /* Fall through.  */
 383
 384         case 'E':
 385           for (j = 0; j < XVECLEN (pattern, i); j++)
 386             if ((r = find_operand (XVECEXP (pattern, i, j), n, stop))
 387                 != NULL_RTX)
 388               return r;
 389           break;
 390
 391         case 'r': case 'p': case 'i': case 'w': case '0': case 's':
 392           break;
 393
 394         default:
 395           gcc_unreachable ();
 396         }
 397     }
 398
 399   return NULL;
 400 }
 401
 402 /* Search for and return operand M, such that it has a matching
 403    constraint for operand N.  */
 404
 405 static rtx
 406 find_matching_operand (rtx pattern, int n)
 407 {
 408   const char *fmt;
 409   RTX_CODE code;
 410   int i, j, len;
 411   rtx r;
 412
 413   code = GET_CODE (pattern);
 414   if (code == MATCH_OPERAND
 415       && (XSTR (pattern, 2)[0] == '0' + n
 416           || (XSTR (pattern, 2)[0] == '%'
 417               && XSTR (pattern, 2)[1] == '0' + n)))
 418     return pattern;
 419
 420   fmt = GET_RTX_FORMAT (code);
 421   len = GET_RTX_LENGTH (code);
 422   for (i = 0; i < len; i++)
 423     {
 424       switch (fmt[i])
 425         {
 426         case 'e': case 'u':
 427           if ((r = find_matching_operand (XEXP (pattern, i), n)))
 428             return r;
 429           break;
 430
 431         case 'V':
 432           if (! XVEC (pattern, i))
 433             break;
 434           /* Fall through.  */
 435
 436         case 'E':
 437           for (j = 0; j < XVECLEN (pattern, i); j++)
 438             if ((r = find_matching_operand (XVECEXP (pattern, i, j), n)))
 439               return r;
 440           break;
 441
 442         case 'r': case 'p': case 'i': case 'w': case '0': case 's':
 443           break;
 444
 445         default:
 446           gcc_unreachable ();
 447         }
 448     }
 449
 450   return NULL;
 451 }
 452
 453 /* In DEFINE_EXPAND, DEFINE_SPLIT, and DEFINE_PEEPHOLE2, we
 454    don't use the MATCH_OPERAND constraint, only the predicate.
 455    This is confusing to folks doing new ports, so help them
 456    not make the mistake.  */
 457
 458 static bool
 459 constraints_supported_in_insn_p (rtx insn)
 460 {
 461   return !(GET_CODE (insn) == DEFINE_EXPAND
 462            || GET_CODE (insn) == DEFINE_SPLIT
 463            || GET_CODE (insn) == DEFINE_PEEPHOLE2);
 464 }
 465
 466 /* Return the name of the predicate matched by MATCH_RTX.  */
 467
 468 static const char *
 469 predicate_name (rtx match_rtx)
 470 {
 471   if (GET_CODE (match_rtx) == MATCH_SCRATCH)
 472     return "scratch_operand";
 473   else
 474     return XSTR (match_rtx, 1);
 475 }
 476
 477 /* Return true if OPERAND is a MATCH_OPERAND using a special predicate
 478    function.  */
 479
 480 static bool
 481 special_predicate_operand_p (rtx operand)
 482 {
 483   if (GET_CODE (operand) == MATCH_OPERAND)
 484     {
 485       const char *pred_name = predicate_name (operand);
 486       if (pred_name[0] != 0)
 487         {
 488           const struct pred_data *pred;
 489
 490           pred = lookup_predicate (pred_name);
 491           return pred != NULL && pred->special;
 492         }
 493     }
 494
 495   return false;
 496 }
 497
 498 /* Check for various errors in PATTERN, which is part of INFO.
 499    SET is nonnull for a destination, and is the complete set pattern.
 500    SET_CODE is '=' for normal sets, and '+' within a context that
 501    requires in-out constraints.  */
 502
 503 static void
 504 validate_pattern (rtx pattern, md_rtx_info *info, rtx set, int set_code)
 505 {
 506   const char *fmt;
 507   RTX_CODE code;
 508   size_t i, len;
 509   int j;
 510
 511   code = GET_CODE (pattern);
 512   switch (code)
 513     {
 514     case MATCH_SCRATCH:
 515       {
 516         const char constraints0 = XSTR (pattern, 1)[0];
 517
 518         if (!constraints_supported_in_insn_p (info->def))
 519           {
 520             if (constraints0)
 521               {
 522                 error_at (info->loc, "constraints not supported in %s",
 523                           GET_RTX_NAME (GET_CODE (info->def)));
 524               }
 525             return;
 526           }
 527
 528         /* If a MATCH_SCRATCH is used in a context requiring an write-only
 529            or read/write register, validate that.  */
 530         if (set_code == '='
 531             && constraints0
 532             && constraints0 != '='
 533             && constraints0 != '+')
 534           {
 535             error_at (info->loc, "operand %d missing output reload",
 536                       XINT (pattern, 0));
 537           }
 538         return;
 539       }
 540     case MATCH_DUP:
 541     case MATCH_OP_DUP:
 542     case MATCH_PAR_DUP:
 543       if (find_operand (info->def, XINT (pattern, 0), pattern) == pattern)
 544         error_at (info->loc, "operand %i duplicated before defined",
 545                   XINT (pattern, 0));
 546       break;
 547     case MATCH_OPERAND:
 548     case MATCH_OPERATOR:
 549       {
 550         const char *pred_name = XSTR (pattern, 1);
 551         const struct pred_data *pred;
 552         const char *c_test;
 553
 554         c_test = get_c_test (info->def);
 555
 556         if (pred_name[0] != 0)
 557           {
 558             pred = lookup_predicate (pred_name);
 559             if (!pred)
 560               error_at (info->loc, "unknown predicate '%s'", pred_name);
 561           }
 562         else
 563           pred = 0;
 564
 565         if (code == MATCH_OPERAND)
 566           {
 567             const char *constraints = XSTR (pattern, 2);
 568             const char constraints0 = constraints[0];
 569
 570             if (!constraints_supported_in_insn_p (info->def))
 571               {
 572                 if (constraints0)
 573                   {
 574                     error_at (info->loc, "constraints not supported in %s",
 575                               GET_RTX_NAME (GET_CODE (info->def)));
 576                   }
 577               }
 578
 579             /* A MATCH_OPERAND that is a SET should have an output reload.  */
 580             else if (set && constraints0)
 581               {
 582                 if (set_code == '+')
 583                   {
 584                     if (constraints0 == '+')
 585                       ;
 586                     /* If we've only got an output reload for this operand,
 587                        we'd better have a matching input operand.  */
 588                     else if (constraints0 == '='
 589                              && find_matching_operand (info->def,
 590                                                        XINT (pattern, 0)))
 591                       ;
 592                     else
 593                       error_at (info->loc, "operand %d missing in-out reload",
 594                                 XINT (pattern, 0));
 595                   }
 596                 else if (constraints0 != '=' && constraints0 != '+')
 597                   error_at (info->loc, "operand %d missing output reload",
 598                             XINT (pattern, 0));
 599               }
 600
 601             /* For matching constraint in MATCH_OPERAND, the digit must be a
 602                smaller number than the number of the operand that uses it in the
 603                constraint.  */
 604             while (1)
 605               {
 606                 while (constraints[0]
 607                        && (constraints[0] == ' ' || constraints[0] == ','))
 608                   constraints++;
 609                 if (!constraints[0])
 610                   break;
 611
 612                 if (constraints[0] >= '0' && constraints[0] <= '9')
 613                   {
 614                     int val;
 615
 616                     sscanf (constraints, "%d", &val);
 617                     if (val >= XINT (pattern, 0))
 618                       error_at (info->loc, "constraint digit %d is not"
 619                                 " smaller than operand %d",
 620                                 val, XINT (pattern, 0));
 621                   }
 622
 623                 while (constraints[0] && constraints[0] != ',')
 624                   constraints++;
 625               }
 626           }
 627
 628         /* Allowing non-lvalues in destinations -- particularly CONST_INT --
 629            while not likely to occur at runtime, results in less efficient
 630            code from insn-recog.cc.  */
 631         if (set && pred && pred->allows_non_lvalue)
 632           error_at (info->loc, "destination operand %d allows non-lvalue",
 633                     XINT (pattern, 0));
 634
 635         /* A modeless MATCH_OPERAND can be handy when we can check for
 636            multiple modes in the c_test.  In most other cases, it is a
 637            mistake.  Only DEFINE_INSN is eligible, since SPLIT and
 638            PEEP2 can FAIL within the output pattern.  Exclude special
 639            predicates, which check the mode themselves.  Also exclude
 640            predicates that allow only constants.  Exclude the SET_DEST
 641            of a call instruction, as that is a common idiom.  */
 642
 643         if (GET_MODE (pattern) == VOIDmode
 644             && code == MATCH_OPERAND
 645             && GET_CODE (info->def) == DEFINE_INSN
 646             && pred
 647             && !pred->special
 648             && pred->allows_non_const
 649             && strstr (c_test, "operands") == NULL
 650             && ! (set
 651                   && GET_CODE (set) == SET
 652                   && GET_CODE (SET_SRC (set)) == CALL))
 653           message_at (info->loc, "warning: operand %d missing mode?",
 654                       XINT (pattern, 0));
 655         return;
 656       }
 657
 658     case SET:
 659       {
 660         machine_mode dmode, smode;
 661         rtx dest, src;
 662
 663         dest = SET_DEST (pattern);
 664         src = SET_SRC (pattern);
 665
 666         /* STRICT_LOW_PART is a wrapper.  Its argument is the real
 667            destination, and it's mode should match the source.  */
 668         if (GET_CODE (dest) == STRICT_LOW_PART)
 669           dest = XEXP (dest, 0);
 670
 671         /* Find the referent for a DUP.  */
 672
 673         if (GET_CODE (dest) == MATCH_DUP
 674             || GET_CODE (dest) == MATCH_OP_DUP
 675             || GET_CODE (dest) == MATCH_PAR_DUP)
 676           dest = find_operand (info->def, XINT (dest, 0), NULL);
 677
 678         if (GET_CODE (src) == MATCH_DUP
 679             || GET_CODE (src) == MATCH_OP_DUP
 680             || GET_CODE (src) == MATCH_PAR_DUP)
 681           src = find_operand (info->def, XINT (src, 0), NULL);
 682
 683         dmode = GET_MODE (dest);
 684         smode = GET_MODE (src);
 685
 686         /* Mode checking is not performed for special predicates.  */
 687         if (special_predicate_operand_p (src)
 688             || special_predicate_operand_p (dest))
 689           ;
 690
 691         /* The operands of a SET must have the same mode unless one
 692            is VOIDmode.  */
 693         else if (dmode != VOIDmode && smode != VOIDmode && dmode != smode)
 694           error_at (info->loc, "mode mismatch in set: %smode vs %smode",
 695                     GET_MODE_NAME (dmode), GET_MODE_NAME (smode));
 696
 697         /* If only one of the operands is VOIDmode, and PC is not involved,
 698            it's probably a mistake.  */
 699         else if (dmode != smode
 700                  && GET_CODE (dest) != PC
 701                  && GET_CODE (src) != PC
 702                  && !CONST_INT_P (src)
 703                  && !CONST_WIDE_INT_P (src)
 704                  && GET_CODE (src) != CALL)
 705           {
 706             const char *which;
 707             which = (dmode == VOIDmode ? "destination" : "source");
 708             message_at (info->loc, "warning: %s missing a mode?", which);
 709           }
 710
 711         if (dest != SET_DEST (pattern))
 712           validate_pattern (dest, info, pattern, '=');
 713         validate_pattern (SET_DEST (pattern), info, pattern, '=');
 714         validate_pattern (SET_SRC (pattern), info, NULL_RTX, 0);
 715         return;
 716       }
 717
 718     case CLOBBER:
 719       validate_pattern (SET_DEST (pattern), info, pattern, '=');
 720       return;
 721
 722     case ZERO_EXTRACT:
 723       validate_pattern (XEXP (pattern, 0), info, set, set ? '+' : 0);
 724       validate_pattern (XEXP (pattern, 1), info, NULL_RTX, 0);
 725       validate_pattern (XEXP (pattern, 2), info, NULL_RTX, 0);
 726       return;
 727
 728     case STRICT_LOW_PART:
 729       validate_pattern (XEXP (pattern, 0), info, set, set ? '+' : 0);
 730       return;
 731
 732     case LABEL_REF:
 733       if (GET_MODE (XEXP (pattern, 0)) != VOIDmode)
 734         error_at (info->loc, "operand to label_ref %smode not VOIDmode",
 735                   GET_MODE_NAME (GET_MODE (XEXP (pattern, 0))));
 736       break;
 737
 738     case VEC_SELECT:
 739       if (GET_MODE (pattern) != VOIDmode)
 740         {
 741           machine_mode mode = GET_MODE (pattern);
 742           machine_mode imode = GET_MODE (XEXP (pattern, 0));
 743           machine_mode emode
 744             = VECTOR_MODE_P (mode) ? GET_MODE_INNER (mode) : mode;
 745           if (GET_CODE (XEXP (pattern, 1)) == PARALLEL)
 746             {
 747               int expected = 1;
 748               unsigned int nelems;
 749               if (VECTOR_MODE_P (mode)
 750                   && !GET_MODE_NUNITS (mode).is_constant (&expected))
 751                 error_at (info->loc,
 752                           "vec_select with variable-sized mode %s",
 753                           GET_MODE_NAME (mode));
 754               else if (XVECLEN (XEXP (pattern, 1), 0) != expected)
 755                 error_at (info->loc,
 756                           "vec_select parallel with %d elements, expected %d",
 757                           XVECLEN (XEXP (pattern, 1), 0), expected);
 758               else if (VECTOR_MODE_P (imode)
 759                        && GET_MODE_NUNITS (imode).is_constant (&nelems))
 760                 {
 761                   int i;
 762                   for (i = 0; i < expected; ++i)
 763                     if (CONST_INT_P (XVECEXP (XEXP (pattern, 1), 0, i))
 764                         && (UINTVAL (XVECEXP (XEXP (pattern, 1), 0, i))
 765                             >= nelems))
 766                       error_at (info->loc,
 767                                 "out of bounds selector %u in vec_select, "
 768                                 "expected at most %u",
 769                                 (unsigned)
 770                                 UINTVAL (XVECEXP (XEXP (pattern, 1), 0, i)),
 771                                 nelems - 1);
 772                 }
 773             }
 774           if (imode != VOIDmode && !VECTOR_MODE_P (imode))
 775             error_at (info->loc, "%smode of first vec_select operand is not a "
 776                                  "vector mode", GET_MODE_NAME (imode));
 777           else if (imode != VOIDmode && GET_MODE_INNER (imode) != emode)
 778             error_at (info->loc, "element mode mismatch between vec_select "
 779                                  "%smode and its operand %smode",
 780                       GET_MODE_NAME (emode),
 781                       GET_MODE_NAME (GET_MODE_INNER (imode)));
 782         }
 783       break;
 784
 785     default:
 786       break;
 787     }
 788
 789   fmt = GET_RTX_FORMAT (code);
 790   len = GET_RTX_LENGTH (code);
 791   for (i = 0; i < len; i++)
 792     {
 793       switch (fmt[i])
 794         {
 795         case 'e': case 'u':
 796           validate_pattern (XEXP (pattern, i), info, NULL_RTX, 0);
 797           break;
 798
 799         case 'E':
 800           for (j = 0; j < XVECLEN (pattern, i); j++)
 801             validate_pattern (XVECEXP (pattern, i, j), info, NULL_RTX, 0);
 802           break;
 803
 804         case 'r': case 'p': case 'i': case 'w': case '0': case 's':
 805           break;
 806
 807         default:
 808           gcc_unreachable ();
 809         }
 810     }
 811 }
 812 \f
 813 /* Simple list structure for items of type T, for use when being part
 814    of a list is an inherent property of T.  T must have members equivalent
 815    to "T *prev, *next;" and a function "void set_parent (list_head <T> *)"
 816    to set the parent list.  */
 817 template <typename T>
 818 class list_head
 819 {
 820 public:
 821   /* A range of linked items.  */
 822   class range
 823   {
 824   public:
 825     range (T *);
 826     range (T *, T *);
 827
 828     T *start, *end;
 829     void set_parent (list_head *);
 830   };
 831
 832   list_head ();
 833   range release ();
 834   void push_back (range);
 835   range remove (range);
 836   void replace (range, range);
 837   T *singleton () const;
 838
 839   T *first, *last;
 840 };
 841
 842 /* Create a range [START_IN, START_IN].  */
 843
 844 template <typename T>
 845 list_head <T>::range::range (T *start_in) : start (start_in), end (start_in) {}
 846
 847 /* Create a range [START_IN, END_IN], linked by next and prev fields.  */
 848
 849 template <typename T>
 850 list_head <T>::range::range (T *start_in, T *end_in)
 851   : start (start_in), end (end_in) {}
 852
 853 template <typename T>
 854 void
 855 list_head <T>::range::set_parent (list_head <T> *owner)
 856 {
 857   for (T *item = start; item != end; item = item->next)
 858     item->set_parent (owner);
 859   end->set_parent (owner);
 860 }
 861
 862 template <typename T>
 863 list_head <T>::list_head () : first (0), last (0) {}
 864
 865 /* Add R to the end of the list.  */
 866
 867 template <typename T>
 868 void
 869 list_head <T>::push_back (range r)
 870 {
 871   if (last)
 872     last->next = r.start;
 873   else
 874     first = r.start;
 875   r.start->prev = last;
 876   last = r.end;
 877   r.set_parent (this);
 878 }
 879
 880 /* Remove R from the list.  R remains valid and can be inserted into
 881    other lists.  */
 882
 883 template <typename T>
 884 typename list_head <T>::range
 885 list_head <T>::remove (range r)
 886 {
 887   if (r.start->prev)
 888     r.start->prev->next = r.end->next;
 889   else
 890     first = r.end->next;
 891   if (r.end->next)
 892     r.end->next->prev = r.start->prev;
 893   else
 894     last = r.start->prev;
 895   r.start->prev = 0;
 896   r.end->next = 0;
 897   r.set_parent (0);
 898   return r;
 899 }
 900
 901 /* Replace OLDR with NEWR.  OLDR remains valid and can be inserted into
 902    other lists.  */
 903
 904 template <typename T>
 905 void
 906 list_head <T>::replace (range oldr, range newr)
 907 {
 908   newr.start->prev = oldr.start->prev;
 909   newr.end->next = oldr.end->next;
 910
 911   oldr.start->prev = 0;
 912   oldr.end->next = 0;
 913   oldr.set_parent (0);
 914
 915   if (newr.start->prev)
 916     newr.start->prev->next = newr.start;
 917   else
 918     first = newr.start;
 919   if (newr.end->next)
 920     newr.end->next->prev = newr.end;
 921   else
 922     last = newr.end;
 923   newr.set_parent (this);
 924 }
 925
 926 /* Empty the list and return the previous contents as a range that can
 927    be inserted into other lists.  */
 928
 929 template <typename T>
 930 typename list_head <T>::range
 931 list_head <T>::release ()
 932 {
 933   range r (first, last);
 934   first = 0;
 935   last = 0;
 936   r.set_parent (0);
 937   return r;
 938 }
 939
 940 /* If the list contains a single item, return that item, otherwise return
 941    null.  */
 942
 943 template <typename T>
 944 T *
 945 list_head <T>::singleton () const
 946 {
 947   return first == last ? first : 0;
 948 }
 949 \f
 950 class state;
 951
 952 /* Describes a possible successful return from a routine.  */
 953 struct acceptance_type
 954 {
 955   /* The type of routine we're returning from.  */
 956   routine_type type : 16;
 957
 958   /* True if this structure only really represents a partial match,
 959      and if we must call a subroutine of type TYPE to complete the match.
 960      In this case we'll call the subroutine and, if it succeeds, return
 961      whatever the subroutine returned.
 962
 963      False if this structure presents a full match.  */
 964   unsigned int partial_p : 1;
 965
 966   union
 967   {
 968     /* If PARTIAL_P, this is the number of the subroutine to call.  */
 969     int subroutine_id;
 970
 971     /* Valid if !PARTIAL_P.  */
 972     struct
 973     {
 974       /* The identifier of the matching pattern.  For SUBPATTERNs this
 975          value belongs to an ad-hoc routine-specific enum.  For the
 976          others it's the number of an .md file pattern.  */
 977       int code;
 978       union
 979       {
 980         /* For RECOG, the number of clobbers that must be added to the
 981            pattern in order for it to match CODE.  */
 982         int num_clobbers;
 983
 984         /* For PEEPHOLE2, the number of additional instructions that were
 985            included in the optimization.  */
 986         int match_len;
 987       } u;
 988     } full;
 989   } u;
 990 };
 991
 992 bool
 993 operator == (const acceptance_type &a, const acceptance_type &b)
 994 {
 995   if (a.partial_p != b.partial_p)
 996     return false;
 997   if (a.partial_p)
 998     return a.u.subroutine_id == b.u.subroutine_id;
 999   else
1000     return a.u.full.code == b.u.full.code;
1001 }
1002
1003 bool
1004 operator != (const acceptance_type &a, const acceptance_type &b)
1005 {
1006   return !operator == (a, b);
1007 }
1008
1009 /* Represents a parameter to a pattern routine.  */
1010 class parameter
1011 {
1012 public:
1013   /* The C type of parameter.  */
1014   enum type_enum {
1015     /* Represents an invalid parameter.  */
1016     UNSET,
1017
1018     /* A machine_mode parameter.  */
1019     MODE,
1020
1021     /* An rtx_code parameter.  */
1022     CODE,
1023
1024     /* An int parameter.  */
1025     INT,
1026
1027     /* An unsigned int parameter.  */
1028     UINT,
1029
1030     /* A HOST_WIDE_INT parameter.  */
1031     WIDE_INT
1032   };
1033
1034   parameter ();
1035   parameter (type_enum, bool, uint64_t);
1036
1037   /* The type of the parameter.  */
1038   type_enum type;
1039
1040   /* True if the value passed is variable, false if it is constant.  */
1041   bool is_param;
1042
1043   /* If IS_PARAM, this is the number of the variable passed, for an "i%d"
1044      format string.  If !IS_PARAM, this is the constant value passed.  */
1045   uint64_t value;
1046 };
1047
1048 parameter::parameter ()
1049   : type (UNSET), is_param (false), value (0) {}
1050
1051 parameter::parameter (type_enum type_in, bool is_param_in, uint64_t value_in)
1052   : type (type_in), is_param (is_param_in), value (value_in) {}
1053
1054 bool
1055 operator == (const parameter &param1, const parameter &param2)
1056 {
1057   return (param1.type == param2.type
1058           && param1.is_param == param2.is_param
1059           && param1.value == param2.value);
1060 }
1061
1062 bool
1063 operator != (const parameter &param1, const parameter &param2)
1064 {
1065   return !operator == (param1, param2);
1066 }
1067
1068 /* Represents a routine that matches a partial rtx pattern, returning
1069    an ad-hoc enum value on success and -1 on failure.  The routine can
1070    be used by any subroutine type.  The match can be parameterized by
1071    things like mode, code and UNSPEC number.  */
1072 class pattern_routine
1073 {
1074 public:
1075   /* The state that implements the pattern.  */
1076   state *s;
1077
1078   /* The deepest root position from which S can access all the rtxes it needs.
1079      This is NULL if the pattern doesn't need an rtx input, usually because
1080      all matching is done on operands[] instead.  */
1081   position *pos;
1082
1083   /* A unique identifier for the routine.  */
1084   unsigned int pattern_id;
1085
1086   /* True if the routine takes pnum_clobbers as argument.  */
1087   bool pnum_clobbers_p;
1088
1089   /* True if the routine takes the enclosing instruction as argument.  */
1090   bool insn_p;
1091
1092   /* The types of the other parameters to the routine, if any.  */
1093   auto_vec <parameter::type_enum, MAX_PATTERN_PARAMS> param_types;
1094 };
1095
1096 /* All defined patterns.  */
1097 static vec <pattern_routine *> patterns;
1098
1099 /* Represents one use of a pattern routine.  */
1100 class pattern_use
1101 {
1102 public:
1103   /* The pattern routine to use.  */
1104   pattern_routine *routine;
1105
1106   /* The values to pass as parameters.  This vector has the same length
1107      as ROUTINE->PARAM_TYPES.  */
1108   auto_vec <parameter, MAX_PATTERN_PARAMS> params;
1109 };
1110
1111 /* Represents a test performed by a decision.  */
1112 class rtx_test
1113 {
1114 public:
1115   rtx_test ();
1116
1117   /* The types of test that can be performed.  Most of them take as input
1118      an rtx X.  Some also take as input a transition label LABEL; the others
1119      are booleans for which the transition label is always "true".
1120
1121      The order of the enum isn't important.  */
1122   enum kind_enum {
1123     /* Check GET_CODE (X) == LABEL.  */
1124     CODE,
1125
1126     /* Check GET_MODE (X) == LABEL.  */
1127     MODE,
1128
1129     /* Check REGNO (X) == LABEL.  */
1130     REGNO_FIELD,
1131
1132     /* Check known_eq (SUBREG_BYTE (X), LABEL).  */
1133     SUBREG_FIELD,
1134
1135     /* Check XINT (X, u.opno) == LABEL.  */
1136     INT_FIELD,
1137
1138     /* Check XWINT (X, u.opno) == LABEL.  */
1139     WIDE_INT_FIELD,
1140
1141     /* Check XVECLEN (X, 0) == LABEL.  */
1142     VECLEN,
1143
1144     /* Check peep2_current_count >= u.min_len.  */
1145     PEEP2_COUNT,
1146
1147     /* Check XVECLEN (X, 0) >= u.min_len.  */
1148     VECLEN_GE,
1149
1150     /* Check whether X is a cached const_int with value u.integer.  */
1151     SAVED_CONST_INT,
1152
1153     /* Check u.predicate.data (X, u.predicate.mode).  */
1154     PREDICATE,
1155
1156     /* Check rtx_equal_p (X, operands[u.opno]).  */
1157     DUPLICATE,
1158
1159     /* Check whether X matches pattern u.pattern.  */
1160     PATTERN,
1161
1162     /* Check whether pnum_clobbers is nonnull (RECOG only).  */
1163     HAVE_NUM_CLOBBERS,
1164
1165     /* Check whether general C test u.string holds.  In general the condition
1166        needs access to "insn" and the full operand list.  */
1167     C_TEST,
1168
1169     /* Execute operands[u.opno] = X.  (Always succeeds.)  */
1170     SET_OP,
1171
1172     /* Accept u.acceptance.  Always succeeds for SUBPATTERN, RECOG and SPLIT.
1173        May fail for PEEPHOLE2 if the define_peephole2 C code executes FAIL.  */
1174     ACCEPT
1175   };
1176
1177   /* The position of rtx X in the above description, relative to the
1178      incoming instruction "insn".  The position is null if the test
1179      doesn't take an X as input.  */
1180   position *pos;
1181
1182   /* Which element of operands[] already contains POS, or -1 if no element
1183      is known to hold POS.  */
1184   int pos_operand;
1185
1186   /* The type of test and its parameters, as described above.  */
1187   kind_enum kind;
1188   union
1189   {
1190     int opno;
1191     int min_len;
1192     struct
1193     {
1194       bool is_param;
1195       int value;
1196     } integer;
1197     struct
1198     {
1199       const struct pred_data *data;
1200       /* True if the mode is taken from a machine_mode parameter
1201          to the routine rather than a constant machine_mode.  If true,
1202          MODE is the number of the parameter (for an "i%d" format string),
1203          otherwise it is the mode itself.  */
1204       bool mode_is_param;
1205       unsigned int mode;
1206     } predicate;
1207     pattern_use *pattern;
1208     const char *string;
1209     acceptance_type acceptance;
1210   } u;
1211
1212   static rtx_test code (position *);
1213   static rtx_test mode (position *);
1214   static rtx_test regno_field (position *);
1215   static rtx_test subreg_field (position *);
1216   static rtx_test int_field (position *, int);
1217   static rtx_test wide_int_field (position *, int);
1218   static rtx_test veclen (position *);
1219   static rtx_test peep2_count (int);
1220   static rtx_test veclen_ge (position *, int);
1221   static rtx_test predicate (position *, const pred_data *, machine_mode);
1222   static rtx_test duplicate (position *, int);
1223   static rtx_test pattern (position *, pattern_use *);
1224   static rtx_test have_num_clobbers ();
1225   static rtx_test c_test (const char *);
1226   static rtx_test set_op (position *, int);
1227   static rtx_test accept (const acceptance_type &);
1228
1229   bool terminal_p () const;
1230   bool single_outcome_p () const;
1231
1232 private:
1233   rtx_test (position *, kind_enum);
1234 };
1235
1236 rtx_test::rtx_test () {}
1237
1238 rtx_test::rtx_test (position *pos_in, kind_enum kind_in)
1239   : pos (pos_in), pos_operand (-1), kind (kind_in) {}
1240
1241 rtx_test
1242 rtx_test::code (position *pos)
1243 {
1244   return rtx_test (pos, rtx_test::CODE);
1245 }
1246
1247 rtx_test
1248 rtx_test::mode (position *pos)
1249 {
1250   return rtx_test (pos, rtx_test::MODE);
1251 }
1252
1253 rtx_test
1254 rtx_test::regno_field (position *pos)
1255 {
1256   rtx_test res (pos, rtx_test::REGNO_FIELD);
1257   return res;
1258 }
1259
1260 rtx_test
1261 rtx_test::subreg_field (position *pos)
1262 {
1263   rtx_test res (pos, rtx_test::SUBREG_FIELD);
1264   return res;
1265 }
1266
1267 rtx_test
1268 rtx_test::int_field (position *pos, int opno)
1269 {
1270   rtx_test res (pos, rtx_test::INT_FIELD);
1271   res.u.opno = opno;
1272   return res;
1273 }
1274
1275 rtx_test
1276 rtx_test::wide_int_field (position *pos, int opno)
1277 {
1278   rtx_test res (pos, rtx_test::WIDE_INT_FIELD);
1279   res.u.opno = opno;
1280   return res;
1281 }
1282
1283 rtx_test
1284 rtx_test::veclen (position *pos)
1285 {
1286   return rtx_test (pos, rtx_test::VECLEN);
1287 }
1288
1289 rtx_test
1290 rtx_test::peep2_count (int min_len)
1291 {
1292   rtx_test res (0, rtx_test::PEEP2_COUNT);
1293   res.u.min_len = min_len;
1294   return res;
1295 }
1296
1297 rtx_test
1298 rtx_test::veclen_ge (position *pos, int min_len)
1299 {
1300   rtx_test res (pos, rtx_test::VECLEN_GE);
1301   res.u.min_len = min_len;
1302   return res;
1303 }
1304
1305 rtx_test
1306 rtx_test::predicate (position *pos, const struct pred_data *data,
1307                      machine_mode mode)
1308 {
1309   rtx_test res (pos, rtx_test::PREDICATE);
1310   res.u.predicate.data = data;
1311   res.u.predicate.mode_is_param = false;
1312   res.u.predicate.mode = mode;
1313   return res;
1314 }
1315
1316 rtx_test
1317 rtx_test::duplicate (position *pos, int opno)
1318 {
1319   rtx_test res (pos, rtx_test::DUPLICATE);
1320   res.u.opno = opno;
1321   return res;
1322 }
1323
1324 rtx_test
1325 rtx_test::pattern (position *pos, pattern_use *pattern)
1326 {
1327   rtx_test res (pos, rtx_test::PATTERN);
1328   res.u.pattern = pattern;
1329   return res;
1330 }
1331
1332 rtx_test
1333 rtx_test::have_num_clobbers ()
1334 {
1335   return rtx_test (0, rtx_test::HAVE_NUM_CLOBBERS);
1336 }
1337
1338 rtx_test
1339 rtx_test::c_test (const char *string)
1340 {
1341   rtx_test res (0, rtx_test::C_TEST);
1342   res.u.string = string;
1343   return res;
1344 }
1345
1346 rtx_test
1347 rtx_test::set_op (position *pos, int opno)
1348 {
1349   rtx_test res (pos, rtx_test::SET_OP);
1350   res.u.opno = opno;
1351   return res;
1352 }
1353
1354 rtx_test
1355 rtx_test::accept (const acceptance_type &acceptance)
1356 {
1357   rtx_test res (0, rtx_test::ACCEPT);
1358   res.u.acceptance = acceptance;
1359   return res;
1360 }
1361
1362 /* Return true if the test represents an unconditionally successful match.  */
1363
1364 bool
1365 rtx_test::terminal_p () const
1366 {
1367   return kind == rtx_test::ACCEPT && u.acceptance.type != PEEPHOLE2;
1368 }
1369
1370 /* Return true if the test is a boolean that is always true.  */
1371
1372 bool
1373 rtx_test::single_outcome_p () const
1374 {
1375   return terminal_p () || kind == rtx_test::SET_OP;
1376 }
1377
1378 bool
1379 operator == (const rtx_test &a, const rtx_test &b)
1380 {
1381   if (a.pos != b.pos || a.kind != b.kind)
1382     return false;
1383   switch (a.kind)
1384     {
1385     case rtx_test::CODE:
1386     case rtx_test::MODE:
1387     case rtx_test::REGNO_FIELD:
1388     case rtx_test::SUBREG_FIELD:
1389     case rtx_test::VECLEN:
1390     case rtx_test::HAVE_NUM_CLOBBERS:
1391       return true;
1392
1393     case rtx_test::PEEP2_COUNT:
1394     case rtx_test::VECLEN_GE:
1395       return a.u.min_len == b.u.min_len;
1396
1397     case rtx_test::INT_FIELD:
1398     case rtx_test::WIDE_INT_FIELD:
1399     case rtx_test::DUPLICATE:
1400     case rtx_test::SET_OP:
1401       return a.u.opno == b.u.opno;
1402
1403     case rtx_test::SAVED_CONST_INT:
1404       return (a.u.integer.is_param == b.u.integer.is_param
1405               && a.u.integer.value == b.u.integer.value);
1406
1407     case rtx_test::PREDICATE:
1408       return (a.u.predicate.data == b.u.predicate.data
1409               && a.u.predicate.mode_is_param == b.u.predicate.mode_is_param
1410               && a.u.predicate.mode == b.u.predicate.mode);
1411
1412     case rtx_test::PATTERN:
1413       return (a.u.pattern->routine == b.u.pattern->routine
1414               && a.u.pattern->params == b.u.pattern->params);
1415
1416     case rtx_test::C_TEST:
1417       return strcmp (a.u.string, b.u.string) == 0;
1418
1419     case rtx_test::ACCEPT:
1420       return a.u.acceptance == b.u.acceptance;
1421     }
1422   gcc_unreachable ();
1423 }
1424
1425 bool
1426 operator != (const rtx_test &a, const rtx_test &b)
1427 {
1428   return !operator == (a, b);
1429 }
1430
1431 /* A simple set of transition labels.  Most transitions have a singleton
1432    label, so try to make that case as efficient as possible.  */
1433 class int_set : public auto_vec <uint64_t, 1>
1434 {
1435 public:
1436   typedef uint64_t *iterator;
1437
1438   int_set ();
1439   int_set (uint64_t);
1440   int_set (const int_set &);
1441
1442   int_set &operator = (const int_set &);
1443
1444   iterator begin ();
1445   iterator end ();
1446 };
1447
1448 int_set::int_set () : auto_vec<uint64_t, 1> () {}
1449
1450 int_set::int_set (uint64_t label) :
1451   auto_vec<uint64_t, 1> ()
1452 {
1453   safe_push (label);
1454 }
1455
1456 int_set::int_set (const int_set &other) :
1457   auto_vec<uint64_t, 1> ()
1458 {
1459   safe_splice (other);
1460 }
1461
1462 int_set &
1463 int_set::operator = (const int_set &other)
1464 {
1465   truncate (0);
1466   safe_splice (other);
1467   return *this;
1468 }
1469
1470 int_set::iterator
1471 int_set::begin ()
1472 {
1473   return address ();
1474 }
1475
1476 int_set::iterator
1477 int_set::end ()
1478 {
1479   return address () + length ();
1480 }
1481
1482 bool
1483 operator == (const int_set &a, const int_set &b)
1484 {
1485   if (a.length () != b.length ())
1486     return false;
1487   for (unsigned int i = 0; i < a.length (); ++i)
1488     if (a[i] != b[i])
1489       return false;
1490   return true;
1491 }
1492
1493 bool
1494 operator != (const int_set &a, const int_set &b)
1495 {
1496   return !operator == (a, b);
1497 }
1498
1499 class decision;
1500
1501 /* Represents a transition between states, dependent on the result of
1502    a test T.  */
1503 class transition
1504 {
1505 public:
1506   transition (const int_set &, state *, bool);
1507
1508   void set_parent (list_head <transition> *);
1509
1510   /* Links to other transitions for T.  Always null for boolean tests.  */
1511   transition *prev, *next;
1512
1513   /* The transition should be taken when T has one of these values.
1514      E.g. for rtx_test::CODE this is a set of codes, while for booleans like
1515      rtx_test::PREDICATE it is always a singleton "true".  The labels are
1516      sorted in ascending order.  */
1517   int_set labels;
1518
1519   /* The source decision.  */
1520   decision *from;
1521
1522   /* The target state.  */
1523   state *to;
1524
1525   /* True if TO would function correctly even if TEST wasn't performed.
1526      E.g. it isn't necessary to check whether GET_MODE (x1) is SImode
1527      before calling register_operand (x1, SImode), since register_operand
1528      performs its own mode check.  However, checking GET_MODE can be a cheap
1529      way of disambiguating SImode and DImode register operands.  */
1530   bool optional;
1531
1532   /* True if LABELS contains parameter numbers rather than constants.
1533      E.g. if this is true for a rtx_test::CODE, the label is the number
1534      of an rtx_code parameter rather than an rtx_code itself.
1535      LABELS is always a singleton when this variable is true.  */
1536   bool is_param;
1537 };
1538
1539 /* Represents a test and the action that should be taken on the result.
1540    If a transition exists for the test outcome, the machine switches
1541    to the transition's target state.  If no suitable transition exists,
1542    the machine either falls through to the next decision or, if there are no
1543    more decisions to try, fails the match.  */
1544 class decision : public list_head <transition>
1545 {
1546 public:
1547   decision (const rtx_test &);
1548
1549   void set_parent (list_head <decision> *s);
1550   bool if_statement_p (uint64_t * = 0) const;
1551
1552   /* The state to which this decision belongs.  */
1553   state *s;
1554
1555   /* Links to other decisions in the same state.  */
1556   decision *prev, *next;
1557
1558   /* The test to perform.  */
1559   rtx_test test;
1560 };
1561
1562 /* Represents one machine state.  For each state the machine tries a list
1563    of decisions, in order, and acts on the first match.  It fails without
1564    further backtracking if no decisions match.  */
1565 class state : public list_head <decision>
1566 {
1567 public:
1568   void set_parent (list_head <state> *) {}
1569 };
1570
1571 transition::transition (const int_set &labels_in, state *to_in,
1572                         bool optional_in)
1573   : prev (0), next (0), labels (labels_in), from (0), to (to_in),
1574     optional (optional_in), is_param (false) {}
1575
1576 /* Set the source decision of the transition.  */
1577
1578 void
1579 transition::set_parent (list_head <transition> *from_in)
1580 {
1581   from = static_cast <decision *> (from_in);
1582 }
1583
1584 decision::decision (const rtx_test &test_in)
1585   : prev (0), next (0), test (test_in) {}
1586
1587 /* Set the state to which this decision belongs.  */
1588
1589 void
1590 decision::set_parent (list_head <decision> *s_in)
1591 {
1592   s = static_cast <state *> (s_in);
1593 }
1594
1595 /* Return true if the decision has a single transition with a single label.
1596    If so, return the label in *LABEL if nonnull.  */
1597
1598 inline bool
1599 decision::if_statement_p (uint64_t *label) const
1600 {
1601   if (singleton () && first->labels.length () == 1)
1602     {
1603       if (label)
1604         *label = first->labels[0];
1605       return true;
1606     }
1607   return false;
1608 }
1609
1610 /* Add to FROM a decision that performs TEST and has a single transition
1611    TRANS.  */
1612
1613 static void
1614 add_decision (state *from, const rtx_test &test, transition *trans)
1615 {
1616   decision *d = new decision (test);
1617   from->push_back (d);
1618   d->push_back (trans);
1619 }
1620
1621 /* Add a transition from FROM to a new, empty state that is taken
1622    when TEST == LABELS.  OPTIONAL says whether the new transition
1623    should be optional.  Return the new state.  */
1624
1625 static state *
1626 add_decision (state *from, const rtx_test &test, int_set labels, bool optional)
1627 {
1628   state *to = new state;
1629   add_decision (from, test, new transition (labels, to, optional));
1630   return to;
1631 }
1632
1633 /* Insert a decision before decisions R to make them dependent on
1634    TEST == LABELS.  OPTIONAL says whether the new transition should be
1635    optional.  */
1636
1637 static decision *
1638 insert_decision_before (state::range r, const rtx_test &test,
1639                         const int_set &labels, bool optional)
1640 {
1641   decision *newd = new decision (test);
1642   state *news = new state;
1643   newd->push_back (new transition (labels, news, optional));
1644   r.start->s->replace (r, newd);
1645   news->push_back (r);
1646   return newd;
1647 }
1648
1649 /* Remove any optional transitions from S that turned out not to be useful.  */
1650
1651 static void
1652 collapse_optional_decisions (state *s)
1653 {
1654   decision *d = s->first;
1655   while (d)
1656     {
1657       decision *next = d->next;
1658       for (transition *trans = d->first; trans; trans = trans->next)
1659         collapse_optional_decisions (trans->to);
1660       /* A decision with a single optional transition doesn't help
1661          partition the potential matches and so is unlikely to be
1662          worthwhile.  In particular, if the decision that performs the
1663          test is the last in the state, the best it could do is reject
1664          an invalid pattern slightly earlier.  If instead the decision
1665          is not the last in the state, the condition it tests could hold
1666          even for the later decisions in the state.  The best it can do
1667          is save work in some cases where only the later decisions can
1668          succeed.
1669
1670          In both cases the optional transition would add extra work to
1671          successful matches when the tested condition holds.  */
1672       if (transition *trans = d->singleton ())
1673         if (trans->optional)
1674           s->replace (d, trans->to->release ());
1675       d = next;
1676     }
1677 }
1678
1679 /* Try to squash several separate tests into simpler ones.  */
1680
1681 static void
1682 simplify_tests (state *s)
1683 {
1684   for (decision *d = s->first; d; d = d->next)
1685     {
1686       uint64_t label;
1687       /* Convert checks for GET_CODE (x) == CONST_INT and XWINT (x, 0) == N
1688          into checks for const_int_rtx[N'], if N is suitably small.  */
1689       if (d->test.kind == rtx_test::CODE
1690           && d->if_statement_p (&label)
1691           && label == CONST_INT)
1692         if (decision *second = d->first->to->singleton ())
1693           if (d->test.pos == second->test.pos
1694               && second->test.kind == rtx_test::WIDE_INT_FIELD
1695               && second->test.u.opno == 0
1696               && second->if_statement_p (&label)
1697               && IN_RANGE (int64_t (label),
1698                            -MAX_SAVED_CONST_INT, MAX_SAVED_CONST_INT))
1699             {
1700               d->test.kind = rtx_test::SAVED_CONST_INT;
1701               d->test.u.integer.is_param = false;
1702               d->test.u.integer.value = label;
1703               d->replace (d->first, second->release ());
1704               d->first->labels[0] = true;
1705             }
1706       /* If we have a CODE test followed by a PREDICATE test, rely on
1707          the predicate to test the code.
1708
1709          This case exists for match_operators.  We initially treat the
1710          CODE test for a match_operator as non-optional so that we can
1711          safely move down to its operands.  It may turn out that all
1712          paths that reach that code test require the same predicate
1713          to be true.  cse_tests will then put the predicate test in
1714          series with the code test.  */
1715       if (d->test.kind == rtx_test::CODE)
1716         if (transition *trans = d->singleton ())
1717           {
1718             state *s = trans->to;
1719             while (decision *d2 = s->singleton ())
1720               {
1721                 if (d->test.pos != d2->test.pos)
1722                   break;
1723                 transition *trans2 = d2->singleton ();
1724                 if (!trans2)
1725                   break;
1726                 if (d2->test.kind == rtx_test::PREDICATE)
1727                   {
1728                     d->test = d2->test;
1729                     trans->labels = int_set (true);
1730                     s->replace (d2, trans2->to->release ());
1731                     break;
1732                   }
1733                 s = trans2->to;
1734               }
1735           }
1736       for (transition *trans = d->first; trans; trans = trans->next)
1737         simplify_tests (trans->to);
1738     }
1739 }
1740
1741 /* Return true if all successful returns passing through D require the
1742    condition tested by COMMON to be true.
1743
1744    When returning true, add all transitions like COMMON in D to WHERE.
1745    WHERE may contain a partial result on failure.  */
1746
1747 static bool
1748 common_test_p (decision *d, transition *common, vec <transition *> *where)
1749 {
1750   if (d->test.kind == rtx_test::ACCEPT)
1751     /* We found a successful return that didn't require COMMON.  */
1752     return false;
1753   if (d->test == common->from->test)
1754     {
1755       transition *trans = d->singleton ();
1756       if (!trans
1757           || trans->optional != common->optional
1758           || trans->labels != common->labels)
1759         return false;
1760       where->safe_push (trans);
1761       return true;
1762     }
1763   for (transition *trans = d->first; trans; trans = trans->next)
1764     for (decision *subd = trans->to->first; subd; subd = subd->next)
1765       if (!common_test_p (subd, common, where))
1766         return false;
1767   return true;
1768 }
1769
1770 /* Indicates that we have tested GET_CODE (X) for a particular rtx X.  */
1771 const unsigned char TESTED_CODE = 1;
1772
1773 /* Indicates that we have tested XVECLEN (X, 0) for a particular rtx X.  */
1774 const unsigned char TESTED_VECLEN = 2;
1775
1776 /* Represents a set of conditions that are known to hold.  */
1777 class known_conditions
1778 {
1779 public:
1780   /* A mask of TESTED_ values for each position, indexed by the position's
1781      id field.  */
1782   auto_vec <unsigned char> position_tests;
1783
1784   /* Index N says whether operands[N] has been set.  */
1785   auto_vec <bool> set_operands;
1786
1787   /* A guranteed lower bound on the value of peep2_current_count.  */
1788   int peep2_count;
1789 };
1790
1791 /* Return true if TEST can safely be performed at D, where
1792    the conditions in KC hold.  TEST is known to occur along the
1793    first path from D (i.e. always following the first transition
1794    of the first decision).  Any intervening tests can be used as
1795    negative proof that hoisting isn't safe, but only KC can be used
1796    as positive proof.  */
1797
1798 static bool
1799 safe_to_hoist_p (decision *d, const rtx_test &test, known_conditions *kc)
1800 {
1801   switch (test.kind)
1802     {
1803     case rtx_test::C_TEST:
1804       /* In general, C tests require everything else to have been
1805          verified and all operands to have been set up.  */
1806       return false;
1807
1808     case rtx_test::ACCEPT:
1809       /* Don't accept something before all conditions have been tested.  */
1810       return false;
1811
1812     case rtx_test::PREDICATE:
1813       /* Don't move a predicate over a test for VECLEN_GE, since the
1814          predicate used in a match_parallel can legitimately expect the
1815          length to be checked first.  */
1816       for (decision *subd = d;
1817            subd->test != test;
1818            subd = subd->first->to->first)
1819         if (subd->test.pos == test.pos
1820             && subd->test.kind == rtx_test::VECLEN_GE)
1821           return false;
1822       goto any_rtx;
1823
1824     case rtx_test::DUPLICATE:
1825       /* Don't test for a match_dup until the associated operand has
1826          been set.  */
1827       if (!kc->set_operands[test.u.opno])
1828         return false;
1829       goto any_rtx;
1830
1831     case rtx_test::CODE:
1832     case rtx_test::MODE:
1833     case rtx_test::SAVED_CONST_INT:
1834     case rtx_test::SET_OP:
1835     any_rtx:
1836       /* Check whether it is safe to access the rtx under test.  */
1837       switch (test.pos->type)
1838         {
1839         case POS_PEEP2_INSN:
1840           return test.pos->arg < kc->peep2_count;
1841
1842         case POS_XEXP:
1843           return kc->position_tests[test.pos->base->id] & TESTED_CODE;
1844
1845         case POS_XVECEXP0:
1846           return kc->position_tests[test.pos->base->id] & TESTED_VECLEN;
1847         }
1848       gcc_unreachable ();
1849
1850     case rtx_test::REGNO_FIELD:
1851     case rtx_test::SUBREG_FIELD:
1852     case rtx_test::INT_FIELD:
1853     case rtx_test::WIDE_INT_FIELD:
1854     case rtx_test::VECLEN:
1855     case rtx_test::VECLEN_GE:
1856       /* These tests access a specific part of an rtx, so are only safe
1857          once we know what the rtx is.  */
1858       return kc->position_tests[test.pos->id] & TESTED_CODE;
1859
1860     case rtx_test::PEEP2_COUNT:
1861     case rtx_test::HAVE_NUM_CLOBBERS:
1862       /* These tests can be performed anywhere.  */
1863       return true;
1864
1865     case rtx_test::PATTERN:
1866       gcc_unreachable ();
1867     }
1868   gcc_unreachable ();
1869 }
1870
1871 /* Look for a transition that is taken by all successful returns from a range
1872    of decisions starting at OUTER and that would be better performed by
1873    OUTER's state instead.  On success, store all instances of that transition
1874    in WHERE and return the last decision in the range.  The range could
1875    just be OUTER, or it could include later decisions as well.
1876
1877    WITH_POSITION_P is true if only tests with position POS should be tried,
1878    false if any test should be tried.  WORTHWHILE_SINGLE_P is true if the
1879    result is useful even when the range contains just a single decision
1880    with a single transition.  KC are the conditions that are known to
1881    hold at OUTER.  */
1882
1883 static decision *
1884 find_common_test (decision *outer, bool with_position_p,
1885                   position *pos, bool worthwhile_single_p,
1886                   known_conditions *kc, vec <transition *> *where)
1887 {
1888   /* After this, WORTHWHILE_SINGLE_P indicates whether a range that contains
1889      just a single decision is useful, regardless of the number of
1890      transitions it has.  */
1891   if (!outer->singleton ())
1892     worthwhile_single_p = true;
1893   /* Quick exit if we don't have enough decisions to form a worthwhile
1894      range.  */
1895   if (!worthwhile_single_p && !outer->next)
1896     return 0;
1897   /* Follow the first chain down, as one example of a path that needs
1898      to contain the common test.  */
1899   for (decision *d = outer; d; d = d->first->to->first)
1900     {
1901       transition *trans = d->singleton ();
1902       if (trans
1903           && (!with_position_p || d->test.pos == pos)
1904           && safe_to_hoist_p (outer, d->test, kc))
1905         {
1906           if (common_test_p (outer, trans, where))
1907             {
1908               if (!outer->next)
1909                 /* We checked above whether the move is worthwhile.  */
1910                 return outer;
1911               /* See how many decisions in OUTER's chain could reuse
1912                  the same test.  */
1913               decision *outer_end = outer;
1914               do
1915                 {
1916                   unsigned int length = where->length ();
1917                   if (!common_test_p (outer_end->next, trans, where))
1918                     {
1919                       where->truncate (length);
1920                       break;
1921                     }
1922                   outer_end = outer_end->next;
1923                 }
1924               while (outer_end->next);
1925               /* It is worth moving TRANS if it can be shared by more than
1926                  one decision.  */
1927               if (outer_end != outer || worthwhile_single_p)
1928                 return outer_end;
1929             }
1930           where->truncate (0);
1931         }
1932     }
1933   return 0;
1934 }
1935
1936 /* Try to promote common subtests in S to a single, shared decision.
1937    Also try to bunch tests for the same position together.  POS is the
1938    position of the rtx tested before reaching S.  KC are the conditions
1939    that are known to hold on entry to S.  */
1940
1941 static void
1942 cse_tests (position *pos, state *s, known_conditions *kc)
1943 {
1944   for (decision *d = s->first; d; d = d->next)
1945     {
1946       auto_vec <transition *, 16> where;
1947       if (d->test.pos)
1948         {
1949           /* Try to find conditions that don't depend on a particular rtx,
1950              such as pnum_clobbers != NULL or peep2_current_count >= X.
1951              It's usually better to check these conditions as soon as
1952              possible, so the change is worthwhile even if there is
1953              only one copy of the test.  */
1954           decision *endd = find_common_test (d, true, 0, true, kc, &where);
1955           if (!endd && d->test.pos != pos)
1956             /* Try to find other conditions related to position POS
1957                before moving to the new position.  Again, this is
1958                worthwhile even if there is only one copy of the test,
1959                since it means that fewer position variables are live
1960                at a given time.  */
1961             endd = find_common_test (d, true, pos, true, kc, &where);
1962           if (!endd)
1963             /* Try to find any condition that is used more than once.  */
1964             endd = find_common_test (d, false, 0, false, kc, &where);
1965           if (endd)
1966             {
1967               transition *common = where[0];
1968               /* Replace [D, ENDD] with a test like COMMON.  We'll recurse
1969                  on the common test and see the original D again next time.  */
1970               d = insert_decision_before (state::range (d, endd),
1971                                           common->from->test,
1972                                           common->labels,
1973                                           common->optional);
1974               /* Remove the old tests.  */
1975               while (!where.is_empty ())
1976                 {
1977                   transition *trans = where.pop ();
1978                   trans->from->s->replace (trans->from, trans->to->release ());
1979                 }
1980             }
1981         }
1982
1983       /* Make sure that safe_to_hoist_p isn't being overly conservative.
1984          It should realize that D's test is safe in the current
1985          environment.  */
1986       gcc_assert (d->test.kind == rtx_test::C_TEST
1987                   || d->test.kind == rtx_test::ACCEPT
1988                   || safe_to_hoist_p (d, d->test, kc));
1989
1990       /* D won't be changed any further by the current optimization.
1991          Recurse with the state temporarily updated to include D.  */
1992       int prev = 0;
1993       switch (d->test.kind)
1994         {
1995         case rtx_test::CODE:
1996           prev = kc->position_tests[d->test.pos->id];
1997           kc->position_tests[d->test.pos->id] |= TESTED_CODE;
1998           break;
1999
2000         case rtx_test::VECLEN:
2001         case rtx_test::VECLEN_GE:
2002           prev = kc->position_tests[d->test.pos->id];
2003           kc->position_tests[d->test.pos->id] |= TESTED_VECLEN;
2004           break;
2005
2006         case rtx_test::SET_OP:
2007           prev = kc->set_operands[d->test.u.opno];
2008           gcc_assert (!prev);
2009           kc->set_operands[d->test.u.opno] = true;
2010           break;
2011
2012         case rtx_test::PEEP2_COUNT:
2013           prev = kc->peep2_count;
2014           kc->peep2_count = MAX (prev, d->test.u.min_len);
2015           break;
2016
2017         default:
2018           break;
2019         }
2020       for (transition *trans = d->first; trans; trans = trans->next)
2021         cse_tests (d->test.pos ? d->test.pos : pos, trans->to, kc);
2022       switch (d->test.kind)
2023         {
2024         case rtx_test::CODE:
2025         case rtx_test::VECLEN:
2026         case rtx_test::VECLEN_GE:
2027           kc->position_tests[d->test.pos->id] = prev;
2028           break;
2029
2030         case rtx_test::SET_OP:
2031           kc->set_operands[d->test.u.opno] = prev;
2032           break;
2033
2034         case rtx_test::PEEP2_COUNT:
2035           kc->peep2_count = prev;
2036           break;
2037
2038         default:
2039           break;
2040         }
2041     }
2042 }
2043
2044 /* Return the type of value that can be used to parameterize test KIND,
2045    or parameter::UNSET if none.  */
2046
2047 parameter::type_enum
2048 transition_parameter_type (rtx_test::kind_enum kind)
2049 {
2050   switch (kind)
2051     {
2052     case rtx_test::CODE:
2053       return parameter::CODE;
2054
2055     case rtx_test::MODE:
2056       return parameter::MODE;
2057
2058     case rtx_test::REGNO_FIELD:
2059     case rtx_test::SUBREG_FIELD:
2060       return parameter::UINT;
2061
2062     case rtx_test::INT_FIELD:
2063     case rtx_test::VECLEN:
2064     case rtx_test::PATTERN:
2065       return parameter::INT;
2066
2067     case rtx_test::WIDE_INT_FIELD:
2068       return parameter::WIDE_INT;
2069
2070     case rtx_test::PEEP2_COUNT:
2071     case rtx_test::VECLEN_GE:
2072     case rtx_test::SAVED_CONST_INT:
2073     case rtx_test::PREDICATE:
2074     case rtx_test::DUPLICATE:
2075     case rtx_test::HAVE_NUM_CLOBBERS:
2076     case rtx_test::C_TEST:
2077     case rtx_test::SET_OP:
2078     case rtx_test::ACCEPT:
2079       return parameter::UNSET;
2080     }
2081   gcc_unreachable ();
2082 }
2083
2084 /* Initialize the pos_operand fields of each state reachable from S.
2085    If OPERAND_POS[ID] >= 0, the position with id ID is stored in
2086    operands[OPERAND_POS[ID]] on entry to S.  */
2087
2088 static void
2089 find_operand_positions (state *s, vec <int> &operand_pos)
2090 {
2091   for (decision *d = s->first; d; d = d->next)
2092     {
2093       int this_operand = (d->test.pos ? operand_pos[d->test.pos->id] : -1);
2094       if (this_operand >= 0)
2095         d->test.pos_operand = this_operand;
2096       if (d->test.kind == rtx_test::SET_OP)
2097         operand_pos[d->test.pos->id] = d->test.u.opno;
2098       for (transition *trans = d->first; trans; trans = trans->next)
2099         find_operand_positions (trans->to, operand_pos);
2100       if (d->test.kind == rtx_test::SET_OP)
2101         operand_pos[d->test.pos->id] = this_operand;
2102     }
2103 }
2104
2105 /* Statistics about a matching routine.  */
2106 class stats
2107 {
2108 public:
2109   stats ();
2110
2111   /* The total number of decisions in the routine, excluding trivial
2112      ones that never fail.  */
2113   unsigned int num_decisions;
2114
2115   /* The number of non-trivial decisions on the longest path through
2116      the routine, and the return value that contributes most to that
2117      long path.  */
2118   unsigned int longest_path;
2119   int longest_path_code;
2120
2121   /* The maximum number of times that a single call to the routine
2122      can backtrack, and the value returned at the end of that path.
2123      "Backtracking" here means failing one decision in state and
2124      going onto to the next.  */
2125   unsigned int longest_backtrack;
2126   int longest_backtrack_code;
2127 };
2128
2129 stats::stats ()
2130   : num_decisions (0), longest_path (0), longest_path_code (-1),
2131     longest_backtrack (0), longest_backtrack_code (-1) {}
2132
2133 /* Return statistics about S.  */
2134
2135 static stats
2136 get_stats (state *s)
2137 {
2138   stats for_s;
2139   unsigned int longest_path = 0;
2140   for (decision *d = s->first; d; d = d->next)
2141     {
2142       /* Work out the statistics for D.  */
2143       stats for_d;
2144       for (transition *trans = d->first; trans; trans = trans->next)
2145         {
2146           stats for_trans = get_stats (trans->to);
2147           for_d.num_decisions += for_trans.num_decisions;
2148           /* Each transition is mutually-exclusive, so just pick the
2149              longest of the individual paths.  */
2150           if (for_d.longest_path <= for_trans.longest_path)
2151             {
2152               for_d.longest_path = for_trans.longest_path;
2153               for_d.longest_path_code = for_trans.longest_path_code;
2154             }
2155           /* Likewise for backtracking.  */
2156           if (for_d.longest_backtrack <= for_trans.longest_backtrack)
2157             {
2158               for_d.longest_backtrack = for_trans.longest_backtrack;
2159               for_d.longest_backtrack_code = for_trans.longest_backtrack_code;
2160             }
2161         }
2162
2163       /* Account for D's test in its statistics.  */
2164       if (!d->test.single_outcome_p ())
2165         {
2166           for_d.num_decisions += 1;
2167           for_d.longest_path += 1;
2168         }
2169       if (d->test.kind == rtx_test::ACCEPT)
2170         {
2171           for_d.longest_path_code = d->test.u.acceptance.u.full.code;
2172           for_d.longest_backtrack_code = d->test.u.acceptance.u.full.code;
2173         }
2174
2175       /* Keep a running count of the number of backtracks.  */
2176       if (d->prev)
2177         for_s.longest_backtrack += 1;
2178
2179       /* Accumulate D's statistics into S's.  */
2180       for_s.num_decisions += for_d.num_decisions;
2181       for_s.longest_path += for_d.longest_path;
2182       for_s.longest_backtrack += for_d.longest_backtrack;
2183
2184       /* Use the code from the decision with the longest individual path,
2185          since that's more likely to be useful if trying to make the
2186          path shorter.  In the event of a tie, pick the later decision,
2187          since that's closer to the end of the path.  */
2188       if (longest_path <= for_d.longest_path)
2189         {
2190           longest_path = for_d.longest_path;
2191           for_s.longest_path_code = for_d.longest_path_code;
2192         }
2193
2194       /* Later decisions in a state are necessarily in a longer backtrack
2195          than earlier decisions.  */
2196       for_s.longest_backtrack_code = for_d.longest_backtrack_code;
2197     }
2198   return for_s;
2199 }
2200
2201 /* Optimize ROOT.  Use TYPE to describe ROOT in status messages.  */
2202
2203 static void
2204 optimize_subroutine_group (const char *type, state *root)
2205 {
2206   /* Remove optional transitions that turned out not to be worthwhile.  */
2207   if (collapse_optional_decisions_p)
2208     collapse_optional_decisions (root);
2209
2210   /* Try to remove duplicated tests and to rearrange tests into a more
2211      logical order.  */
2212   if (cse_tests_p)
2213     {
2214       known_conditions kc;
2215       kc.position_tests.safe_grow_cleared (num_positions, true);
2216       kc.set_operands.safe_grow_cleared (num_operands, true);
2217       kc.peep2_count = 1;
2218       cse_tests (&root_pos, root, &kc);
2219     }
2220
2221   /* Try to simplify two or more tests into one.  */
2222   if (simplify_tests_p)
2223     simplify_tests (root);
2224
2225   /* Try to use operands[] instead of xN variables.  */
2226   if (use_operand_variables_p)
2227     {
2228       auto_vec <int> operand_pos (num_positions);
2229       for (unsigned int i = 0; i < num_positions; ++i)
2230         operand_pos.quick_push (-1);
2231       find_operand_positions (root, operand_pos);
2232     }
2233
2234   /* Print a summary of the new state.  */
2235   stats st = get_stats (root);
2236   fprintf (stderr, "Statistics for %s:\n", type);
2237   fprintf (stderr, "  Number of decisions: %6d\n", st.num_decisions);
2238   fprintf (stderr, "  longest path:        %6d (code: %6d)\n",
2239            st.longest_path, st.longest_path_code);
2240   fprintf (stderr, "  longest backtrack:   %6d (code: %6d)\n",
2241            st.longest_backtrack, st.longest_backtrack_code);
2242 }
2243
2244 class merge_pattern_info;
2245
2246 /* Represents a transition from one pattern to another.  */
2247 class merge_pattern_transition
2248 {
2249 public:
2250   merge_pattern_transition (merge_pattern_info *);
2251
2252   /* The target pattern.  */
2253   merge_pattern_info *to;
2254
2255   /* The parameters that the source pattern passes to the target pattern.
2256      "parameter (TYPE, true, I)" represents parameter I of the source
2257      pattern.  */
2258   auto_vec <parameter, MAX_PATTERN_PARAMS> params;
2259 };
2260
2261 merge_pattern_transition::merge_pattern_transition (merge_pattern_info *to_in)
2262   : to (to_in)
2263 {
2264 }
2265
2266 /* Represents a pattern that can might match several states.  The pattern
2267    may replace parts of the test with a parameter value.  It may also
2268    replace transition labels with parameters.  */
2269 class merge_pattern_info
2270 {
2271 public:
2272   merge_pattern_info (unsigned int);
2273
2274   /* If PARAM_TEST_P, the state's singleton test should be generalized
2275      to use the runtime value of PARAMS[PARAM_TEST].  */
2276   unsigned int param_test : 8;
2277
2278   /* If PARAM_TRANSITION_P, the state's single transition label should
2279      be replaced by the runtime value of PARAMS[PARAM_TRANSITION].  */
2280   unsigned int param_transition : 8;
2281
2282   /* True if we have decided to generalize the root decision's test,
2283      as per PARAM_TEST.  */
2284   unsigned int param_test_p : 1;
2285
2286   /* Likewise for the root decision's transition, as per PARAM_TRANSITION.  */
2287   unsigned int param_transition_p : 1;
2288
2289   /* True if the contents of the structure are completely filled in.  */
2290   unsigned int complete_p : 1;
2291
2292   /* The number of pseudo-statements in the pattern.  Used to decide
2293      whether it's big enough to break out into a subroutine.  */
2294   unsigned int num_statements;
2295
2296   /* The number of states that use this pattern.  */
2297   unsigned int num_users;
2298
2299   /* The number of distinct success values that the pattern returns.  */
2300   unsigned int num_results;
2301
2302   /* This array has one element for each runtime parameter to the pattern.
2303      PARAMS[I] gives the default value of parameter I, which is always
2304      constant.
2305
2306      These default parameters are used in cases where we match the
2307      pattern against some state S1, then add more parameters while
2308      matching against some state S2.  S1 is then left passing fewer
2309      parameters than S2.  The array gives us enough informatino to
2310      construct a full parameter list for S1 (see update_parameters).
2311
2312      If we decide to create a subroutine for this pattern,
2313      PARAMS[I].type determines the C type of parameter I.  */
2314   auto_vec <parameter, MAX_PATTERN_PARAMS> params;
2315
2316   /* All states that match this pattern must have the same number of
2317      transitions.  TRANSITIONS[I] describes the subpattern for transition
2318      number I; it is null if transition I represents a successful return
2319      from the pattern.  */
2320   auto_vec <merge_pattern_transition *, 1> transitions;
2321
2322   /* The routine associated with the pattern, or null if we haven't generated
2323      one yet.  */
2324   pattern_routine *routine;
2325 };
2326
2327 merge_pattern_info::merge_pattern_info (unsigned int num_transitions)
2328   : param_test (0),
2329     param_transition (0),
2330     param_test_p (false),
2331     param_transition_p (false),
2332     complete_p (false),
2333     num_statements (0),
2334     num_users (0),
2335     num_results (0),
2336     routine (0)
2337 {
2338   transitions.safe_grow_cleared (num_transitions, true);
2339 }
2340
2341 /* Describes one way of matching a particular state to a particular
2342    pattern.  */
2343 class merge_state_result
2344 {
2345 public:
2346   merge_state_result (merge_pattern_info *, position *, merge_state_result *);
2347
2348   /* A pattern that matches the state.  */
2349   merge_pattern_info *pattern;
2350
2351   /* If we decide to use this match and create a subroutine for PATTERN,
2352      the state should pass the rtx at position ROOT to the pattern's
2353      rtx parameter.  A null root means that the pattern doesn't need
2354      an rtx parameter; all the rtxes it matches come from elsewhere.  */
2355   position *root;
2356
2357   /* The parameters that should be passed to PATTERN for this state.
2358      If the array is shorter than PATTERN->params, the missing entries
2359      should be taken from the corresponding element of PATTERN->params.  */
2360   auto_vec <parameter, MAX_PATTERN_PARAMS> params;
2361
2362   /* An earlier match for the same state, or null if none.  Patterns
2363      matched by earlier entries are smaller than PATTERN.  */
2364   merge_state_result *prev;
2365 };
2366
2367 merge_state_result::merge_state_result (merge_pattern_info *pattern_in,
2368                                         position *root_in,
2369                                         merge_state_result *prev_in)
2370   : pattern (pattern_in), root (root_in), prev (prev_in)
2371 {}
2372
2373 /* Information about a state, used while trying to match it against
2374    a pattern.  */
2375 class merge_state_info
2376 {
2377 public:
2378   merge_state_info (state *);
2379
2380   /* The state itself.  */
2381   state *s;
2382
2383   /* Index I gives information about the target of transition I.  */
2384   merge_state_info *to_states;
2385
2386   /* The number of transitions in S.  */
2387   unsigned int num_transitions;
2388
2389   /* True if the state has been deleted in favor of a call to a
2390      pattern routine.  */
2391   bool merged_p;
2392
2393   /* The previous state that might be a merge candidate for S, or null
2394      if no previous states could be merged with S.  */
2395   merge_state_info *prev_same_test;
2396
2397   /* A list of pattern matches for this state.  */
2398   merge_state_result *res;
2399 };
2400
2401 merge_state_info::merge_state_info (state *s_in)
2402   : s (s_in),
2403     to_states (0),
2404     num_transitions (0),
2405     merged_p (false),
2406     prev_same_test (0),
2407     res (0) {}
2408
2409 /* True if PAT would be useful as a subroutine.  */
2410
2411 static bool
2412 useful_pattern_p (merge_pattern_info *pat)
2413 {
2414   return pat->num_statements >= MIN_COMBINE_COST;
2415 }
2416
2417 /* PAT2 is a subpattern of PAT1.  Return true if PAT2 should be inlined
2418    into PAT1's C routine.  */
2419
2420 static bool
2421 same_pattern_p (merge_pattern_info *pat1, merge_pattern_info *pat2)
2422 {
2423   return pat1->num_users == pat2->num_users || !useful_pattern_p (pat2);
2424 }
2425
2426 /* PAT was previously matched against SINFO based on tentative matches
2427    for the target states of SINFO's state.  Return true if the match
2428    still holds; that is, if the target states of SINFO's state still
2429    match the corresponding transitions of PAT.  */
2430
2431 static bool
2432 valid_result_p (merge_pattern_info *pat, merge_state_info *sinfo)
2433 {
2434   for (unsigned int j = 0; j < sinfo->num_transitions; ++j)
2435     if (merge_pattern_transition *ptrans = pat->transitions[j])
2436       {
2437         merge_state_result *to_res = sinfo->to_states[j].res;
2438         if (!to_res || to_res->pattern != ptrans->to)
2439           return false;
2440       }
2441   return true;
2442 }
2443
2444 /* Remove any matches that are no longer valid from the head of SINFO's
2445    list of matches.  */
2446
2447 static void
2448 prune_invalid_results (merge_state_info *sinfo)
2449 {
2450   while (sinfo->res && !valid_result_p (sinfo->res->pattern, sinfo))
2451     {
2452       sinfo->res = sinfo->res->prev;
2453       gcc_assert (sinfo->res);
2454     }
2455 }
2456
2457 /* Return true if PAT represents the biggest posssible match for SINFO;
2458    that is, if the next action of SINFO's state on return from PAT will
2459    be something that cannot be merged with any other state.  */
2460
2461 static bool
2462 complete_result_p (merge_pattern_info *pat, merge_state_info *sinfo)
2463 {
2464   for (unsigned int j = 0; j < sinfo->num_transitions; ++j)
2465     if (sinfo->to_states[j].res && !pat->transitions[j])
2466       return false;
2467   return true;
2468 }
2469
2470 /* Update TO for any parameters that have been added to FROM since TO
2471    was last set.  The extra parameters in FROM will be constants or
2472    instructions to duplicate earlier parameters.  */
2473
2474 static void
2475 update_parameters (vec <parameter> &to, const vec <parameter> &from)
2476 {
2477   for (unsigned int i = to.length (); i < from.length (); ++i)
2478     to.quick_push (from[i]);
2479 }
2480
2481 /* Return true if A and B can be tested by a single test.  If the test
2482    can be parameterised, store the parameter value for A in *PARAMA and
2483    the parameter value for B in *PARAMB, otherwise leave PARAMA and
2484    PARAMB alone.  */
2485
2486 static bool
2487 compatible_tests_p (const rtx_test &a, const rtx_test &b,
2488                     parameter *parama, parameter *paramb)
2489 {
2490   if (a.kind != b.kind)
2491     return false;
2492   switch (a.kind)
2493     {
2494     case rtx_test::PREDICATE:
2495       if (a.u.predicate.data != b.u.predicate.data)
2496         return false;
2497       *parama = parameter (parameter::MODE, false, a.u.predicate.mode);
2498       *paramb = parameter (parameter::MODE, false, b.u.predicate.mode);
2499       return true;
2500
2501     case rtx_test::SAVED_CONST_INT:
2502       *parama = parameter (parameter::INT, false, a.u.integer.value);
2503       *paramb = parameter (parameter::INT, false, b.u.integer.value);
2504       return true;
2505
2506     default:
2507       return a == b;
2508     }
2509 }
2510
2511 /* PARAMS is an array of the parameters that a state is going to pass
2512    to a pattern routine.  It is still incomplete; index I has a kind of
2513    parameter::UNSET if we don't yet know what the state will pass
2514    as parameter I.  Try to make parameter ID equal VALUE, returning
2515    true on success.  */
2516
2517 static bool
2518 set_parameter (vec <parameter> &params, unsigned int id,
2519                const parameter &value)
2520 {
2521   if (params[id].type == parameter::UNSET)
2522     {
2523       if (force_unique_params_p)
2524         for (unsigned int i = 0; i < params.length (); ++i)
2525           if (params[i] == value)
2526             return false;
2527       params[id] = value;
2528       return true;
2529     }
2530   return params[id] == value;
2531 }
2532
2533 /* PARAMS2 is the "params" array for a pattern and PARAMS1 is the
2534    set of parameters that a particular state is going to pass to
2535    that pattern.
2536
2537    Try to extend PARAMS1 and PARAMS2 so that there is a parameter
2538    that is equal to PARAM1 for the state and has a default value of
2539    PARAM2.  Parameters beginning at START were added as part of the
2540    same match and so may be reused.  */
2541
2542 static bool
2543 add_parameter (vec <parameter> &params1, vec <parameter> &params2,
2544                const parameter &param1, const parameter &param2,
2545                unsigned int start, unsigned int *res)
2546 {
2547   gcc_assert (params1.length () == params2.length ());
2548   gcc_assert (!param1.is_param && !param2.is_param);
2549
2550   for (unsigned int i = start; i < params2.length (); ++i)
2551     if (params1[i] == param1 && params2[i] == param2)
2552       {
2553         *res = i;
2554         return true;
2555       }
2556
2557   if (force_unique_params_p)
2558     for (unsigned int i = 0; i < params2.length (); ++i)
2559       if (params1[i] == param1 || params2[i] == param2)
2560         return false;
2561
2562   if (params2.length () >= MAX_PATTERN_PARAMS)
2563     return false;
2564
2565   *res = params2.length ();
2566   params1.quick_push (param1);
2567   params2.quick_push (param2);
2568   return true;
2569 }
2570
2571 /* If *ROOTA is nonnull, return true if the same sequence of steps are
2572    required to reach A from *ROOTA as to reach B from ROOTB.  If *ROOTA
2573    is null, update it if necessary in order to make the condition hold.  */
2574
2575 static bool
2576 merge_relative_positions (position **roota, position *a,
2577                           position *rootb, position *b)
2578 {
2579   if (!relative_patterns_p)
2580     {
2581       if (a != b)
2582         return false;
2583       if (!*roota)
2584         {
2585           *roota = rootb;
2586           return true;
2587         }
2588       return *roota == rootb;
2589     }
2590   /* If B does not belong to the same instruction as ROOTB, we don't
2591      start with ROOTB but instead start with a call to peep2_next_insn.
2592      In that case the sequences for B and A are identical iff B and A
2593      are themselves identical.  */
2594   if (rootb->insn_id != b->insn_id)
2595     return a == b;
2596   while (rootb != b)
2597     {
2598       if (!a || b->type != a->type || b->arg != a->arg)
2599         return false;
2600       b = b->base;
2601       a = a->base;
2602     }
2603   if (!*roota)
2604     *roota = a;
2605   return *roota == a;
2606 }
2607
2608 /* A hasher of states that treats two states as "equal" if they might be
2609    merged (but trying to be more discriminating than "return true").  */
2610 struct test_pattern_hasher : nofree_ptr_hash <merge_state_info>
2611 {
2612   static inline hashval_t hash (const value_type &);
2613   static inline bool equal (const value_type &, const compare_type &);
2614 };
2615
2616 hashval_t
2617 test_pattern_hasher::hash (merge_state_info *const &sinfo)
2618 {
2619   inchash::hash h;
2620   decision *d = sinfo->s->singleton ();
2621   h.add_int (d->test.pos_operand + 1);
2622   if (!relative_patterns_p)
2623     h.add_int (d->test.pos ? d->test.pos->id + 1 : 0);
2624   h.add_int (d->test.kind);
2625   h.add_int (sinfo->num_transitions);
2626   return h.end ();
2627 }
2628
2629 bool
2630 test_pattern_hasher::equal (merge_state_info *const &sinfo1,
2631                             merge_state_info *const &sinfo2)
2632 {
2633   decision *d1 = sinfo1->s->singleton ();
2634   decision *d2 = sinfo2->s->singleton ();
2635   gcc_assert (d1 && d2);
2636
2637   parameter new_param1, new_param2;
2638   return (d1->test.pos_operand == d2->test.pos_operand
2639           && (relative_patterns_p || d1->test.pos == d2->test.pos)
2640           && compatible_tests_p (d1->test, d2->test, &new_param1, &new_param2)
2641           && sinfo1->num_transitions == sinfo2->num_transitions);
2642 }
2643
2644 /* Try to make the state described by SINFO1 use the same pattern as the
2645    state described by SINFO2.  Return true on success.
2646
2647    SINFO1 and SINFO2 are known to have the same hash value.  */
2648
2649 static bool
2650 merge_patterns (merge_state_info *sinfo1, merge_state_info *sinfo2)
2651 {
2652   merge_state_result *res2 = sinfo2->res;
2653   merge_pattern_info *pat = res2->pattern;
2654
2655   /* Write to temporary arrays while matching, in case we have to abort
2656      half way through.  */
2657   auto_vec <parameter, MAX_PATTERN_PARAMS> params1;
2658   auto_vec <parameter, MAX_PATTERN_PARAMS> params2;
2659   params1.quick_grow_cleared (pat->params.length ());
2660   params2.splice (pat->params);
2661   unsigned int start_param = params2.length ();
2662
2663   /* An array for recording changes to PAT->transitions[?].params.
2664      All changes involve replacing a constant parameter with some
2665      PAT->params[N], where N is the second element of the pending_param.  */
2666   typedef std::pair <parameter *, unsigned int> pending_param;
2667   auto_vec <pending_param, 32> pending_params;
2668
2669   decision *d1 = sinfo1->s->singleton ();
2670   decision *d2 = sinfo2->s->singleton ();
2671   gcc_assert (d1 && d2);
2672
2673   /* If D2 tests a position, SINFO1's root relative to D1 is the same
2674      as SINFO2's root relative to D2.  */
2675   position *root1 = 0;
2676   position *root2 = res2->root;
2677   if (d2->test.pos_operand < 0
2678       && d1->test.pos
2679       && !merge_relative_positions (&root1, d1->test.pos,
2680                                     root2, d2->test.pos))
2681     return false;
2682
2683   /* Check whether the patterns have the same shape.  */
2684   unsigned int num_transitions = sinfo1->num_transitions;
2685   gcc_assert (num_transitions == sinfo2->num_transitions);
2686   for (unsigned int i = 0; i < num_transitions; ++i)
2687     if (merge_pattern_transition *ptrans = pat->transitions[i])
2688       {
2689         merge_state_result *to1_res = sinfo1->to_states[i].res;
2690         merge_state_result *to2_res = sinfo2->to_states[i].res;
2691         merge_pattern_info *to_pat = ptrans->to;
2692         gcc_assert (to2_res && to2_res->pattern == to_pat);
2693         if (!to1_res || to1_res->pattern != to_pat)
2694           return false;
2695         if (to2_res->root
2696             && !merge_relative_positions (&root1, to1_res->root,
2697                                           root2, to2_res->root))
2698           return false;
2699         /* Match the parameters that TO1_RES passes to TO_PAT with the
2700            parameters that PAT passes to TO_PAT.  */
2701         update_parameters (to1_res->params, to_pat->params);
2702         for (unsigned int j = 0; j < to1_res->params.length (); ++j)
2703           {
2704             const parameter &param1 = to1_res->params[j];
2705             const parameter &param2 = ptrans->params[j];
2706             gcc_assert (!param1.is_param);
2707             if (param2.is_param)
2708               {
2709                 if (!set_parameter (params1, param2.value, param1))
2710                   return false;
2711               }
2712             else if (param1 != param2)
2713               {
2714                 unsigned int id;
2715                 if (!add_parameter (params1, params2,
2716                                     param1, param2, start_param, &id))
2717                   return false;
2718                 /* Record that PAT should now pass parameter ID to TO_PAT,
2719                    instead of the current contents of *PARAM2.  We only
2720                    make the change if the rest of the match succeeds.  */
2721                 pending_params.safe_push
2722                   (pending_param (&ptrans->params[j], id));
2723               }
2724           }
2725       }
2726
2727   unsigned int param_test = pat->param_test;
2728   unsigned int param_transition = pat->param_transition;
2729   bool param_test_p = pat->param_test_p;
2730   bool param_transition_p = pat->param_transition_p;
2731
2732   /* If the tests don't match exactly, try to parameterize them.  */
2733   parameter new_param1, new_param2;
2734   if (!compatible_tests_p (d1->test, d2->test, &new_param1, &new_param2))
2735     gcc_unreachable ();
2736   if (new_param1.type != parameter::UNSET)
2737     {
2738       /* If the test has not already been parameterized, all existing
2739          matches use constant NEW_PARAM2.  */
2740       if (param_test_p)
2741         {
2742           if (!set_parameter (params1, param_test, new_param1))
2743             return false;
2744         }
2745       else if (new_param1 != new_param2)
2746         {
2747           if (!add_parameter (params1, params2, new_param1, new_param2,
2748                               start_param, &param_test))
2749             return false;
2750           param_test_p = true;
2751         }
2752     }
2753
2754   /* Match the transitions.  */
2755   transition *trans1 = d1->first;
2756   transition *trans2 = d2->first;
2757   for (unsigned int i = 0; i < num_transitions; ++i)
2758     {
2759       if (param_transition_p || trans1->labels != trans2->labels)
2760         {
2761           /* We can only generalize a single transition with a single
2762              label.  */
2763           if (num_transitions != 1
2764               || trans1->labels.length () != 1
2765               || trans2->labels.length () != 1)
2766             return false;
2767
2768           /* Although we can match wide-int fields, in practice it leads
2769              to some odd results for const_vectors.  We end up
2770              parameterizing the first N const_ints of the vector
2771              and then (once we reach the maximum number of parameters)
2772              we go on to match the other elements exactly.  */
2773           if (d1->test.kind == rtx_test::WIDE_INT_FIELD)
2774             return false;
2775
2776           /* See whether the label has a generalizable type.  */
2777           parameter::type_enum param_type
2778             = transition_parameter_type (d1->test.kind);
2779           if (param_type == parameter::UNSET)
2780             return false;
2781
2782           /* Match the labels using parameters.  */
2783           new_param1 = parameter (param_type, false, trans1->labels[0]);
2784           if (param_transition_p)
2785             {
2786               if (!set_parameter (params1, param_transition, new_param1))
2787                 return false;
2788             }
2789           else
2790             {
2791               new_param2 = parameter (param_type, false, trans2->labels[0]);
2792               if (!add_parameter (params1, params2, new_param1, new_param2,
2793                                   start_param, &param_transition))
2794                 return false;
2795               param_transition_p = true;
2796             }
2797         }
2798       trans1 = trans1->next;
2799       trans2 = trans2->next;
2800     }
2801
2802   /* Set any unset parameters to their default values.  This occurs if some
2803      other state needed something to be parameterized in order to match SINFO2,
2804      but SINFO1 on its own does not.  */
2805   for (unsigned int i = 0; i < params1.length (); ++i)
2806     if (params1[i].type == parameter::UNSET)
2807       params1[i] = params2[i];
2808
2809   /* The match was successful.  Commit all pending changes to PAT.  */
2810   update_parameters (pat->params, params2);
2811   {
2812     pending_param *pp;
2813     unsigned int i;
2814     FOR_EACH_VEC_ELT (pending_params, i, pp)
2815       *pp->first = parameter (pp->first->type, true, pp->second);
2816   }
2817   pat->param_test = param_test;
2818   pat->param_transition = param_transition;
2819   pat->param_test_p = param_test_p;
2820   pat->param_transition_p = param_transition_p;
2821
2822   /* Record the match of SINFO1.  */
2823   merge_state_result *new_res1 = new merge_state_result (pat, root1,
2824                                                          sinfo1->res);
2825   new_res1->params.splice (params1);
2826   sinfo1->res = new_res1;
2827   return true;
2828 }
2829
2830 /* The number of states that were removed by calling pattern routines.  */
2831 static unsigned int pattern_use_states;
2832
2833 /* The number of states used while defining pattern routines.  */
2834 static unsigned int pattern_def_states;
2835
2836 /* Information used while constructing a use or definition of a pattern
2837    routine.  */
2838 struct create_pattern_info
2839 {
2840   /* The routine itself.  */
2841   pattern_routine *routine;
2842
2843   /* The first unclaimed return value for this particular use or definition.
2844      We walk the substates of uses and definitions in the same order
2845      so each return value always refers to the same position within
2846      the pattern.  */
2847   unsigned int next_result;
2848 };
2849
2850 static void populate_pattern_routine (create_pattern_info *,
2851                                       merge_state_info *, state *,
2852                                       const vec <parameter> &);
2853
2854 /* SINFO matches a pattern for which we've decided to create a C routine.
2855    Return a decision that performs a call to the pattern routine,
2856    but leave the caller to add the transitions to it.  Initialize CPI
2857    for this purpose.  Also create a definition for the pattern routine,
2858    if it doesn't already have one.
2859
2860    PARAMS are the parameters that SINFO passes to its pattern.  */
2861
2862 static decision *
2863 init_pattern_use (create_pattern_info *cpi, merge_state_info *sinfo,
2864                   const vec <parameter> &params)
2865 {
2866   state *s = sinfo->s;
2867   merge_state_result *res = sinfo->res;
2868   merge_pattern_info *pat = res->pattern;
2869   cpi->routine = pat->routine;
2870   if (!cpi->routine)
2871     {
2872       /* We haven't defined the pattern routine yet, so create
2873          a definition now.  */
2874       pattern_routine *routine = new pattern_routine;
2875       pat->routine = routine;
2876       cpi->routine = routine;
2877       routine->s = new state;
2878       routine->insn_p = false;
2879       routine->pnum_clobbers_p = false;
2880
2881       /* Create an "idempotent" mapping of parameter I to parameter I.
2882          Also record the C type of each parameter to the routine.  */
2883       auto_vec <parameter, MAX_PATTERN_PARAMS> def_params;
2884       for (unsigned int i = 0; i < pat->params.length (); ++i)
2885         {
2886           def_params.quick_push (parameter (pat->params[i].type, true, i));
2887           routine->param_types.quick_push (pat->params[i].type);
2888         }
2889
2890       /* Any of the states that match the pattern could be used to
2891          create the routine definition.  We might as well use SINFO
2892          since it's already to hand.  This means that all positions
2893          in the definition will be relative to RES->root.  */
2894       routine->pos = res->root;
2895       cpi->next_result = 0;
2896       populate_pattern_routine (cpi, sinfo, routine->s, def_params);
2897       gcc_assert (cpi->next_result == pat->num_results);
2898
2899       /* Add the routine to the global list, after the subroutines
2900          that it calls.  */
2901       routine->pattern_id = patterns.length ();
2902       patterns.safe_push (routine);
2903     }
2904
2905   /* Create a decision to call the routine, passing PARAMS to it.  */
2906   pattern_use *use = new pattern_use;
2907   use->routine = pat->routine;
2908   use->params.splice (params);
2909   decision *d = new decision (rtx_test::pattern (res->root, use));
2910
2911   /* If the original decision could use an element of operands[] instead
2912      of an rtx variable, try to transfer it to the new decision.  */
2913   if (s->first->test.pos && res->root == s->first->test.pos)
2914     d->test.pos_operand = s->first->test.pos_operand;
2915
2916   cpi->next_result = 0;
2917   return d;
2918 }
2919
2920 /* Make S return the next unclaimed pattern routine result for CPI.  */
2921
2922 static void
2923 add_pattern_acceptance (create_pattern_info *cpi, state *s)
2924 {
2925   acceptance_type acceptance;
2926   acceptance.type = SUBPATTERN;
2927   acceptance.partial_p = false;
2928   acceptance.u.full.code = cpi->next_result;
2929   add_decision (s, rtx_test::accept (acceptance), true, false);
2930   cpi->next_result += 1;
2931 }
2932
2933 /* Initialize new empty state NEWS so that it implements SINFO's pattern
2934    (here referred to as "P").  P may be the top level of a pattern routine
2935    or a subpattern that should be inlined into its parent pattern's routine
2936    (as per same_pattern_p).  The choice of SINFO for a top-level pattern is
2937    arbitrary; it could be any of the states that use P.  The choice for
2938    subpatterns follows the choice for the parent pattern.
2939
2940    PARAMS gives the value of each parameter to P in terms of the parameters
2941    to the top-level pattern.  If P itself is the top level pattern, PARAMS[I]
2942    is always "parameter (TYPE, true, I)".  */
2943
2944 static void
2945 populate_pattern_routine (create_pattern_info *cpi, merge_state_info *sinfo,
2946                           state *news, const vec <parameter> &params)
2947 {
2948   pattern_def_states += 1;
2949
2950   decision *d = sinfo->s->singleton ();
2951   merge_pattern_info *pat = sinfo->res->pattern;
2952   pattern_routine *routine = cpi->routine;
2953
2954   /* Create a copy of D's test for the pattern routine and generalize it
2955      as appropriate.  */
2956   decision *newd = new decision (d->test);
2957   gcc_assert (newd->test.pos_operand >= 0
2958               || !newd->test.pos
2959               || common_position (newd->test.pos,
2960                                   routine->pos) == routine->pos);
2961   if (pat->param_test_p)
2962     {
2963       const parameter &param = params[pat->param_test];
2964       switch (newd->test.kind)
2965         {
2966         case rtx_test::PREDICATE:
2967           newd->test.u.predicate.mode_is_param = param.is_param;
2968           newd->test.u.predicate.mode = param.value;
2969           break;
2970
2971         case rtx_test::SAVED_CONST_INT:
2972           newd->test.u.integer.is_param = param.is_param;
2973           newd->test.u.integer.value = param.value;
2974           break;
2975
2976         default:
2977           gcc_unreachable ();
2978           break;
2979         }
2980     }
2981   if (d->test.kind == rtx_test::C_TEST)
2982     routine->insn_p = true;
2983   else if (d->test.kind == rtx_test::HAVE_NUM_CLOBBERS)
2984     routine->pnum_clobbers_p = true;
2985   news->push_back (newd);
2986
2987   /* Fill in the transitions of NEWD.  */
2988   unsigned int i = 0;
2989   for (transition *trans = d->first; trans; trans = trans->next)
2990     {
2991       /* Create a new state to act as the target of the new transition.  */
2992       state *to_news = new state;
2993       if (merge_pattern_transition *ptrans = pat->transitions[i])
2994         {
2995           /* The pattern hasn't finished matching yet.  Get the target
2996              pattern and the corresponding target state of SINFO.  */
2997           merge_pattern_info *to_pat = ptrans->to;
2998           merge_state_info *to = sinfo->to_states + i;
2999           gcc_assert (to->res->pattern == to_pat);
3000           gcc_assert (ptrans->params.length () == to_pat->params.length ());
3001
3002           /* Express the parameters to TO_PAT in terms of the parameters
3003              to the top-level pattern.  */
3004           auto_vec <parameter, MAX_PATTERN_PARAMS> to_params;
3005           for (unsigned int j = 0; j < ptrans->params.length (); ++j)
3006             {
3007               const parameter &param = ptrans->params[j];
3008               to_params.quick_push (param.is_param
3009                                     ? params[param.value]
3010                                     : param);
3011             }
3012
3013           if (same_pattern_p (pat, to_pat))
3014             /* TO_PAT is part of the current routine, so just recurse.  */
3015             populate_pattern_routine (cpi, to, to_news, to_params);
3016           else
3017             {
3018               /* TO_PAT should be matched by calling a separate routine.  */
3019               create_pattern_info sub_cpi;
3020               decision *subd = init_pattern_use (&sub_cpi, to, to_params);
3021               routine->insn_p |= sub_cpi.routine->insn_p;
3022               routine->pnum_clobbers_p |= sub_cpi.routine->pnum_clobbers_p;
3023
3024               /* Add the pattern routine call to the new target state.  */
3025               to_news->push_back (subd);
3026
3027               /* Add a transition for each successful call result.  */
3028               for (unsigned int j = 0; j < to_pat->num_results; ++j)
3029                 {
3030                   state *res = new state;
3031                   add_pattern_acceptance (cpi, res);
3032                   subd->push_back (new transition (j, res, false));
3033                 }
3034             }
3035         }
3036       else
3037         /* This transition corresponds to a successful match.  */
3038         add_pattern_acceptance (cpi, to_news);
3039
3040       /* Create the transition itself, generalizing as necessary.  */
3041       transition *new_trans = new transition (trans->labels, to_news,
3042                                               trans->optional);
3043       if (pat->param_transition_p)
3044         {
3045           const parameter &param = params[pat->param_transition];
3046           new_trans->is_param = param.is_param;
3047           new_trans->labels[0] = param.value;
3048         }
3049       newd->push_back (new_trans);
3050       i += 1;
3051     }
3052 }
3053
3054 /* USE is a decision that calls a pattern routine and SINFO is part of the
3055    original state tree that the call is supposed to replace.  Add the
3056    transitions for SINFO and its substates to USE.  */
3057
3058 static void
3059 populate_pattern_use (create_pattern_info *cpi, decision *use,
3060                       merge_state_info *sinfo)
3061 {
3062   pattern_use_states += 1;
3063   gcc_assert (!sinfo->merged_p);
3064   sinfo->merged_p = true;
3065   merge_state_result *res = sinfo->res;
3066   merge_pattern_info *pat = res->pattern;
3067   decision *d = sinfo->s->singleton ();
3068   unsigned int i = 0;
3069   for (transition *trans = d->first; trans; trans = trans->next)
3070     {
3071       if (pat->transitions[i])
3072         /* The target state is also part of the pattern.  */
3073         populate_pattern_use (cpi, use, sinfo->to_states + i);
3074       else
3075         {
3076           /* The transition corresponds to a successful return from the
3077              pattern routine.  */
3078           use->push_back (new transition (cpi->next_result, trans->to, false));
3079           cpi->next_result += 1;
3080         }
3081       i += 1;
3082     }
3083 }
3084
3085 /* We have decided to replace SINFO's state with a call to a pattern
3086    routine.  Make the change, creating a definition of the pattern routine
3087    if it doesn't have one already.  */
3088
3089 static void
3090 use_pattern (merge_state_info *sinfo)
3091 {
3092   merge_state_result *res = sinfo->res;
3093   merge_pattern_info *pat = res->pattern;
3094   state *s = sinfo->s;
3095
3096   /* The pattern may have acquired new parameters after it was matched
3097      against SINFO.  Update the parameters that SINFO passes accordingly.  */
3098   update_parameters (res->params, pat->params);
3099
3100   create_pattern_info cpi;
3101   decision *d = init_pattern_use (&cpi, sinfo, res->params);
3102   populate_pattern_use (&cpi, d, sinfo);
3103   s->release ();
3104   s->push_back (d);
3105 }
3106
3107 /* Look through the state trees in STATES for common patterns and
3108    split them into subroutines.  */
3109
3110 static void
3111 split_out_patterns (vec <merge_state_info> &states)
3112 {
3113   unsigned int first_transition = states.length ();
3114   hash_table <test_pattern_hasher> hashtab (128);
3115   /* Stage 1: Create an order in which parent states come before their child
3116      states and in which sibling states are at consecutive locations.
3117      Having consecutive sibling states allows merge_state_info to have
3118      a single to_states pointer.  */
3119   for (unsigned int i = 0; i < states.length (); ++i)
3120     for (decision *d = states[i].s->first; d; d = d->next)
3121       for (transition *trans = d->first; trans; trans = trans->next)
3122         {
3123           states.safe_push (trans->to);
3124           states[i].num_transitions += 1;
3125         }
3126   /* Stage 2: Now that the addresses are stable, set up the to_states
3127      pointers.  Look for states that might be merged and enter them
3128      into the hash table.  */
3129   for (unsigned int i = 0; i < states.length (); ++i)
3130     {
3131       merge_state_info *sinfo = &states[i];
3132       if (sinfo->num_transitions)
3133         {
3134           sinfo->to_states = &states[first_transition];
3135           first_transition += sinfo->num_transitions;
3136         }
3137       /* For simplicity, we only try to merge states that have a single
3138          decision.  This is in any case the best we can do for peephole2,
3139          since whether a peephole2 ACCEPT succeeds or not depends on the
3140          specific peephole2 pattern (which is unique to each ACCEPT
3141          and so couldn't be shared between states).  */
3142       if (decision *d = sinfo->s->singleton ())
3143         /* ACCEPT states are unique, so don't even try to merge them.  */
3144         if (d->test.kind != rtx_test::ACCEPT
3145             && (pattern_have_num_clobbers_p
3146                 || d->test.kind != rtx_test::HAVE_NUM_CLOBBERS)
3147             && (pattern_c_test_p
3148                 || d->test.kind != rtx_test::C_TEST))
3149           {
3150             merge_state_info **slot = hashtab.find_slot (sinfo, INSERT);
3151             sinfo->prev_same_test = *slot;
3152             *slot = sinfo;
3153           }
3154     }
3155   /* Stage 3: Walk backwards through the list of states and try to merge
3156      them.  This is a greedy, bottom-up match; parent nodes can only start
3157      a new leaf pattern if they fail to match when combined with all child
3158      nodes that have matching patterns.
3159
3160      For each state we keep a list of potential matches, with each
3161      potential match being larger (and deeper) than the next match in
3162      the list.  The final element in the list is a leaf pattern that
3163      matches just a single state.
3164
3165      Each candidate pattern created in this loop is unique -- it won't
3166      have been seen by an earlier iteration.  We try to match each pattern
3167      with every state that appears earlier in STATES.
3168
3169      Because the patterns created in the loop are unique, any state
3170      that already has a match must have a final potential match that
3171      is different from any new leaf pattern.  Therefore, when matching
3172      leaf patterns, we need only consider states whose list of matches
3173      is empty.
3174
3175      The non-leaf patterns that we try are as deep as possible
3176      and are an extension of the state's previous best candidate match (PB).
3177      We need only consider states whose current potential match is also PB;
3178      any states that don't match as much as PB cannnot match the new pattern,
3179      while any states that already match more than PB must be different from
3180      the new pattern.  */
3181   for (unsigned int i2 = states.length (); i2-- > 0; )
3182     {
3183       merge_state_info *sinfo2 = &states[i2];
3184
3185       /* Enforce the bottom-upness of the match: remove matches with later
3186          states if SINFO2's child states ended up finding a better match.  */
3187       prune_invalid_results (sinfo2);
3188
3189       /* Do nothing if the state doesn't match a later one and if there are
3190          no earlier states it could match.  */
3191       if (!sinfo2->res && !sinfo2->prev_same_test)
3192         continue;
3193
3194       merge_state_result *res2 = sinfo2->res;
3195       decision *d2 = sinfo2->s->singleton ();
3196       position *root2 = (d2->test.pos_operand < 0 ? d2->test.pos : 0);
3197       unsigned int num_transitions = sinfo2->num_transitions;
3198
3199       /* If RES2 is null then SINFO2's test in isolation has not been seen
3200          before.  First try matching that on its own.  */
3201       if (!res2)
3202         {
3203           merge_pattern_info *new_pat
3204             = new merge_pattern_info (num_transitions);
3205           merge_state_result *new_res2
3206             = new merge_state_result (new_pat, root2, res2);
3207           sinfo2->res = new_res2;
3208
3209           new_pat->num_statements = !d2->test.single_outcome_p ();
3210           new_pat->num_results = num_transitions;
3211           bool matched_p = false;
3212           /* Look for states that don't currently match anything but
3213              can be made to match SINFO2 on its own.  */
3214           for (merge_state_info *sinfo1 = sinfo2->prev_same_test; sinfo1;
3215                sinfo1 = sinfo1->prev_same_test)
3216             if (!sinfo1->res && merge_patterns (sinfo1, sinfo2))
3217               matched_p = true;
3218           if (!matched_p)
3219             {
3220               /* No other states match.  */
3221               sinfo2->res = res2;
3222               delete new_pat;
3223               delete new_res2;
3224               continue;
3225             }
3226           else
3227             res2 = new_res2;
3228         }
3229
3230       /* Keep the existing pattern if it's as good as anything we'd
3231          create for SINFO2.  */
3232       if (complete_result_p (res2->pattern, sinfo2))
3233         {
3234           res2->pattern->num_users += 1;
3235           continue;
3236         }
3237
3238       /* Create a new pattern for SINFO2.  */
3239       merge_pattern_info *new_pat = new merge_pattern_info (num_transitions);
3240       merge_state_result *new_res2
3241         = new merge_state_result (new_pat, root2, res2);
3242       sinfo2->res = new_res2;
3243
3244       /* Fill in details about the pattern.  */
3245       new_pat->num_statements = !d2->test.single_outcome_p ();
3246       new_pat->num_results = 0;
3247       for (unsigned int j = 0; j < num_transitions; ++j)
3248         if (merge_state_result *to_res = sinfo2->to_states[j].res)
3249           {
3250             /* Count the target state as part of this pattern.
3251                First update the root position so that it can reach
3252                the target state's root.  */
3253             if (to_res->root)
3254               {
3255                 if (new_res2->root)
3256                   new_res2->root = common_position (new_res2->root,
3257                                                     to_res->root);
3258                 else
3259                   new_res2->root = to_res->root;
3260               }
3261             merge_pattern_info *to_pat = to_res->pattern;
3262             merge_pattern_transition *ptrans
3263               = new merge_pattern_transition (to_pat);
3264
3265             /* TO_PAT may have acquired more parameters when matching
3266                states earlier in STATES than TO_RES's, but the list is
3267                now final.  Make sure that TO_RES is up to date.  */
3268             update_parameters (to_res->params, to_pat->params);
3269
3270             /* Start out by assuming that every user of NEW_PAT will
3271                want to pass the same (constant) parameters as TO_RES.  */
3272             update_parameters (ptrans->params, to_res->params);
3273
3274             new_pat->transitions[j] = ptrans;
3275             new_pat->num_statements += to_pat->num_statements;
3276             new_pat->num_results += to_pat->num_results;
3277           }
3278         else
3279           /* The target state doesn't match anything and so is not part
3280              of the pattern.  */
3281           new_pat->num_results += 1;
3282
3283       /* See if any earlier states that match RES2's pattern also match
3284          NEW_PAT.  */
3285       bool matched_p = false;
3286       for (merge_state_info *sinfo1 = sinfo2->prev_same_test; sinfo1;
3287            sinfo1 = sinfo1->prev_same_test)
3288         {
3289           prune_invalid_results (sinfo1);
3290           if (sinfo1->res
3291               && sinfo1->res->pattern == res2->pattern
3292               && merge_patterns (sinfo1, sinfo2))
3293             matched_p = true;
3294         }
3295       if (!matched_p)
3296         {
3297           /* Nothing else matches NEW_PAT, so go back to the previous
3298              pattern (possibly just a single-state one).  */
3299           sinfo2->res = res2;
3300           delete new_pat;
3301           delete new_res2;
3302         }
3303       /* Assume that SINFO2 will use RES.  At this point we don't know
3304          whether earlier states that match the same pattern will use
3305          that match or a different one.  */
3306       sinfo2->res->pattern->num_users += 1;
3307     }
3308   /* Step 4: Finalize the choice of pattern for each state, ignoring
3309      patterns that were only used once.  Update each pattern's size
3310      so that it doesn't include subpatterns that are going to be split
3311      out into subroutines.  */
3312   for (unsigned int i = 0; i < states.length (); ++i)
3313     {
3314       merge_state_info *sinfo = &states[i];
3315       merge_state_result *res = sinfo->res;
3316       /* Wind past patterns that are only used by SINFO.  */
3317       while (res && res->pattern->num_users == 1)
3318         {
3319           res = res->prev;
3320           sinfo->res = res;
3321           if (res)
3322             res->pattern->num_users += 1;
3323         }
3324       if (!res)
3325         continue;
3326
3327       /* We have a shared pattern and are now committed to the match.  */
3328       merge_pattern_info *pat = res->pattern;
3329       gcc_assert (valid_result_p (pat, sinfo));
3330
3331       if (!pat->complete_p)
3332         {
3333           /* Look for subpatterns that are going to be split out and remove
3334              them from the number of statements.  */
3335           for (unsigned int j = 0; j < sinfo->num_transitions; ++j)
3336             if (merge_pattern_transition *ptrans = pat->transitions[j])
3337               {
3338                 merge_pattern_info *to_pat = ptrans->to;
3339                 if (!same_pattern_p (pat, to_pat))
3340                   pat->num_statements -= to_pat->num_statements;
3341               }
3342           pat->complete_p = true;
3343         }
3344     }
3345   /* Step 5: Split out the patterns.  */
3346   for (unsigned int i = 0; i < states.length (); ++i)
3347     {
3348       merge_state_info *sinfo = &states[i];
3349       merge_state_result *res = sinfo->res;
3350       if (!sinfo->merged_p && res && useful_pattern_p (res->pattern))
3351         use_pattern (sinfo);
3352     }
3353   fprintf (stderr, "Shared %d out of %d states by creating %d new states,"
3354            " saving %d\n",
3355            pattern_use_states, states.length (), pattern_def_states,
3356            pattern_use_states - pattern_def_states);
3357 }
3358
3359 /* Information about a state tree that we're considering splitting into a
3360    subroutine.  */
3361 struct state_size
3362 {
3363   /* The number of pseudo-statements in the state tree.  */
3364   unsigned int num_statements;
3365
3366   /* The approximate number of nested "if" and "switch" statements that
3367      would be required if control could fall through to a later state.  */
3368   unsigned int depth;
3369 };
3370
3371 /* Pairs a transition with information about its target state.  */
3372 typedef std::pair <transition *, state_size> subroutine_candidate;
3373
3374 /* Sort two subroutine_candidates so that the one with the largest
3375    number of statements comes last.  */
3376
3377 static int
3378 subroutine_candidate_cmp (const void *a, const void *b)
3379 {
3380   return int (((const subroutine_candidate *) a)->second.num_statements
3381               - ((const subroutine_candidate *) b)->second.num_statements);
3382 }
3383
3384 /* Turn S into a subroutine of type TYPE and add it to PROCS.  Return a new
3385    state that performs a subroutine call to S.  */
3386
3387 static state *
3388 create_subroutine (routine_type type, state *s, vec <state *> &procs)
3389 {
3390   procs.safe_push (s);
3391   acceptance_type acceptance;
3392   acceptance.type = type;
3393   acceptance.partial_p = true;
3394   acceptance.u.subroutine_id = procs.length ();
3395   state *news = new state;
3396   add_decision (news, rtx_test::accept (acceptance), true, false);
3397   return news;
3398 }
3399
3400 /* Walk state tree S, of type TYPE, and look for subtrees that would be
3401    better split into subroutines.  Accumulate all such subroutines in PROCS.
3402    Return the size of the new state tree (excluding subroutines).  */
3403
3404 static state_size
3405 find_subroutines (routine_type type, state *s, vec <state *> &procs)
3406 {
3407   auto_vec <subroutine_candidate, 16> candidates;
3408   state_size size;
3409   size.num_statements = 0;
3410   size.depth = 0;
3411   for (decision *d = s->first; d; d = d->next)
3412     {
3413       if (!d->test.single_outcome_p ())
3414         size.num_statements += 1;
3415       for (transition *trans = d->first; trans; trans = trans->next)
3416         {
3417           /* Keep chains of simple decisions together if we know that no
3418              change of position is required.  We'll output this chain as a
3419              single "if" statement, so it counts as a single nesting level.  */
3420           if (d->test.pos && d->if_statement_p ())
3421             for (;;)
3422               {
3423                 decision *newd = trans->to->singleton ();
3424                 if (!newd
3425                     || (newd->test.pos
3426                         && newd->test.pos_operand < 0
3427                         && newd->test.pos != d->test.pos)
3428                     || !newd->if_statement_p ())
3429                   break;
3430                 if (!newd->test.single_outcome_p ())
3431                   size.num_statements += 1;
3432                 trans = newd->singleton ();
3433                 if (newd->test.kind == rtx_test::SET_OP
3434                     || newd->test.kind == rtx_test::ACCEPT)
3435                   break;
3436               }
3437           /* The target of TRANS is a subroutine candidate.  First recurse
3438              on it to see how big it is after subroutines have been
3439              split out.  */
3440           state_size to_size = find_subroutines (type, trans->to, procs);
3441           if (d->next && to_size.depth > MAX_DEPTH)
3442             /* Keeping the target state in the same routine would lead
3443                to an excessive nesting of "if" and "switch" statements.
3444                Split it out into a subroutine so that it can use
3445                inverted tests that return early on failure.  */
3446             trans->to = create_subroutine (type, trans->to, procs);
3447           else
3448             {
3449               size.num_statements += to_size.num_statements;
3450               if (to_size.num_statements < MIN_NUM_STATEMENTS)
3451                 /* The target state is too small to be worth splitting.
3452                    Keep it in the same routine as S.  */
3453                 size.depth = MAX (size.depth, to_size.depth);
3454               else
3455                 /* Assume for now that we'll keep the target state in the
3456                    same routine as S, but record it as a subroutine candidate
3457                    if S grows too big.  */
3458                 candidates.safe_push (subroutine_candidate (trans, to_size));
3459             }
3460         }
3461     }
3462   if (size.num_statements > MAX_NUM_STATEMENTS)
3463     {
3464       /* S is too big.  Sort the subroutine candidates so that bigger ones
3465          are nearer the end.  */
3466       candidates.qsort (subroutine_candidate_cmp);
3467       while (!candidates.is_empty ()
3468              && size.num_statements > MAX_NUM_STATEMENTS)
3469         {
3470           /* Peel off a candidate and force it into a subroutine.  */
3471           subroutine_candidate cand = candidates.pop ();
3472           size.num_statements -= cand.second.num_statements;
3473           cand.first->to = create_subroutine (type, cand.first->to, procs);
3474         }
3475     }
3476   /* Update the depth for subroutine candidates that we decided not to
3477      split out.  */
3478   for (unsigned int i = 0; i < candidates.length (); ++i)
3479     size.depth = MAX (size.depth, candidates[i].second.depth);
3480   size.depth += 1;
3481   return size;
3482 }
3483
3484 /* Return true if, for all X, PRED (X, MODE) implies that X has mode MODE.  */
3485
3486 static bool
3487 safe_predicate_mode (const struct pred_data *pred, machine_mode mode)
3488 {
3489   /* Scalar integer constants have VOIDmode.  */
3490   if (GET_MODE_CLASS (mode) == MODE_INT
3491       && (pred->codes[CONST_INT]
3492           || pred->codes[CONST_DOUBLE]
3493           || pred->codes[CONST_WIDE_INT]
3494           || pred->codes[LABEL_REF]))
3495     return false;
3496
3497   return !pred->special && mode != VOIDmode;
3498 }
3499
3500 /* Fill CODES with the set of codes that could be matched by PRED.  */
3501
3502 static void
3503 get_predicate_codes (const struct pred_data *pred, int_set *codes)
3504 {
3505   for (int i = 0; i < NUM_TRUE_RTX_CODE; ++i)
3506     if (!pred || pred->codes[i])
3507       codes->safe_push (i);
3508 }
3509
3510 /* Return true if the first path through D1 tests the same thing as D2.  */
3511
3512 static bool
3513 has_same_test_p (decision *d1, decision *d2)
3514 {
3515   do
3516     {
3517       if (d1->test == d2->test)
3518         return true;
3519       d1 = d1->first->to->first;
3520     }
3521   while (d1);
3522   return false;
3523 }
3524
3525 /* Return true if D1 and D2 cannot match the same rtx.  All states reachable
3526    from D2 have single decisions and all those decisions have single
3527    transitions.  */
3528
3529 static bool
3530 mutually_exclusive_p (decision *d1, decision *d2)
3531 {
3532   /* If one path through D1 fails to test the same thing as D2, assume
3533      that D2's test could be true for D1 and look for a later, more useful,
3534      test.  This isn't as expensive as it looks in practice.  */
3535   while (!has_same_test_p (d1, d2))
3536     {
3537       d2 = d2->singleton ()->to->singleton ();
3538       if (!d2)
3539         return false;
3540     }
3541   if (d1->test == d2->test)
3542     {
3543       /* Look for any transitions from D1 that have the same labels as
3544          the transition from D2.  */
3545       transition *trans2 = d2->singleton ();
3546       for (transition *trans1 = d1->first; trans1; trans1 = trans1->next)
3547         {
3548           int_set::iterator i1 = trans1->labels.begin ();
3549           int_set::iterator end1 = trans1->labels.end ();
3550           int_set::iterator i2 = trans2->labels.begin ();
3551           int_set::iterator end2 = trans2->labels.end ();
3552           while (i1 != end1 && i2 != end2)
3553             if (*i1 < *i2)
3554               ++i1;
3555             else if (*i2 < *i1)
3556               ++i2;
3557             else
3558               {
3559                 /* TRANS1 has some labels in common with TRANS2.  Assume
3560                    that D1 and D2 could match the same rtx if the target
3561                    of TRANS1 could match the same rtx as D2.  */
3562                 for (decision *subd1 = trans1->to->first;
3563                      subd1; subd1 = subd1->next)
3564                   if (!mutually_exclusive_p (subd1, d2))
3565                     return false;
3566                 break;
3567               }
3568         }
3569       return true;
3570     }
3571   for (transition *trans1 = d1->first; trans1; trans1 = trans1->next)
3572     for (decision *subd1 = trans1->to->first; subd1; subd1 = subd1->next)
3573       if (!mutually_exclusive_p (subd1, d2))
3574         return false;
3575   return true;
3576 }
3577
3578 /* Try to merge S2's decision into D1, given that they have the same test.
3579    Fail only if EXCLUDE is nonnull and the new transition would have the
3580    same labels as *EXCLUDE.  When returning true, set *NEXT_S1, *NEXT_S2
3581    and *NEXT_EXCLUDE as for merge_into_state_1, or set *NEXT_S2 to null
3582    if the merge is complete.  */
3583
3584 static bool
3585 merge_into_decision (decision *d1, state *s2, const int_set *exclude,
3586                      state **next_s1, state **next_s2,
3587                      const int_set **next_exclude)
3588 {
3589   decision *d2 = s2->singleton ();
3590   transition *trans2 = d2->singleton ();
3591
3592   /* Get a list of the transitions that intersect TRANS2.  */
3593   auto_vec <transition *, 32> intersecting;
3594   for (transition *trans1 = d1->first; trans1; trans1 = trans1->next)
3595     {
3596       int_set::iterator i1 = trans1->labels.begin ();
3597       int_set::iterator end1 = trans1->labels.end ();
3598       int_set::iterator i2 = trans2->labels.begin ();
3599       int_set::iterator end2 = trans2->labels.end ();
3600       bool trans1_is_subset = true;
3601       bool trans2_is_subset = true;
3602       bool intersect_p = false;
3603       while (i1 != end1 && i2 != end2)
3604         if (*i1 < *i2)
3605           {
3606             trans1_is_subset = false;
3607             ++i1;
3608           }
3609         else if (*i2 < *i1)
3610           {
3611             trans2_is_subset = false;
3612             ++i2;
3613           }
3614         else
3615           {
3616             intersect_p = true;
3617             ++i1;
3618             ++i2;
3619           }
3620       if (i1 != end1)
3621         trans1_is_subset = false;
3622       if (i2 != end2)
3623         trans2_is_subset = false;
3624       if (trans1_is_subset && trans2_is_subset)
3625         {
3626           /* There's already a transition that matches exactly.
3627              Merge the target states.  */
3628           trans1->optional &= trans2->optional;
3629           *next_s1 = trans1->to;
3630           *next_s2 = trans2->to;
3631           *next_exclude = 0;
3632           return true;
3633         }
3634       if (trans2_is_subset)
3635         {
3636           /* TRANS1 has all the labels that TRANS2 needs.  Merge S2 into
3637              the target of TRANS1, but (to avoid infinite recursion)
3638              make sure that we don't end up creating another transition
3639              like TRANS1.  */
3640           *next_s1 = trans1->to;
3641           *next_s2 = s2;
3642           *next_exclude = &trans1->labels;
3643           return true;
3644         }
3645       if (intersect_p)
3646         intersecting.safe_push (trans1);
3647     }
3648
3649   if (intersecting.is_empty ())
3650     {
3651       /* No existing labels intersect the new ones.  We can just add
3652          TRANS2 itself.  */
3653       d1->push_back (d2->release ());
3654       *next_s1 = 0;
3655       *next_s2 = 0;
3656       *next_exclude = 0;
3657       return true;
3658     }
3659
3660   /* Take the union of the labels in INTERSECTING and TRANS2.  Store the
3661      result in COMBINED and use NEXT as a temporary.  */
3662   int_set tmp1 = trans2->labels, tmp2;
3663   int_set *combined = &tmp1, *next = &tmp2;
3664   for (unsigned int i = 0; i < intersecting.length (); ++i)
3665     {
3666       transition *trans1 = intersecting[i];
3667       next->truncate (0);
3668       next->safe_grow (trans1->labels.length () + combined->length (), true);
3669       int_set::iterator end
3670         = std::set_union (trans1->labels.begin (), trans1->labels.end (),
3671                           combined->begin (), combined->end (),
3672                           next->begin ());
3673       next->truncate (end - next->begin ());
3674       std::swap (next, combined);
3675     }
3676
3677   /* Stop now if we've been told not to create a transition with these
3678      labels.  */
3679   if (exclude && *combined == *exclude)
3680     return false;
3681
3682   /* Get the transition that should carry the new labels.  */
3683   transition *new_trans = intersecting[0];
3684   if (intersecting.length () == 1)
3685     {
3686       /* We're merging with one existing transition whose labels are a
3687          subset of those required.  If both transitions are optional,
3688          we can just expand the set of labels so that it's suitable
3689          for both transitions.  It isn't worth preserving the original
3690          transitions since we know that they can't be merged; we would
3691          need to backtrack to S2 if TRANS1->to fails.  In contrast,
3692          we might be able to merge the targets of the transitions
3693          without any backtracking.
3694
3695          If instead the existing transition is not optional, ensure that
3696          all target decisions are suitably protected.  Some decisions
3697          might already have a more specific requirement than NEW_TRANS,
3698          in which case there's no point testing NEW_TRANS as well.  E.g. this
3699          would have happened if a test for an (eq ...) rtx had been
3700          added to a decision that tested whether the code is suitable
3701          for comparison_operator.  The original comparison_operator
3702          transition would have been non-optional and the (eq ...) test
3703          would be performed by a second decision in the target of that
3704          transition.
3705
3706          The remaining case -- keeping the original optional transition
3707          when adding a non-optional TRANS2 -- is a wash.  Preserving
3708          the optional transition only helps if we later merge another
3709          state S3 that is mutually exclusive with S2 and whose labels
3710          belong to *COMBINED - TRANS1->labels.  We can then test the
3711          original NEW_TRANS and S3 in the same decision.  We keep the
3712          optional transition around for that case, but it occurs very
3713          rarely.  */
3714       gcc_assert (new_trans->labels != *combined);
3715       if (!new_trans->optional || !trans2->optional)
3716         {
3717           decision *start = 0;
3718           for (decision *end = new_trans->to->first; end; end = end->next)
3719             {
3720               if (!start && end->test != d1->test)
3721                 /* END belongs to a range of decisions that need to be
3722                    protected by NEW_TRANS.  */
3723                 start = end;
3724               if (start && (!end->next || end->next->test == d1->test))
3725                 {
3726                   /* Protect [START, END] with NEW_TRANS.  The decisions
3727                      move to NEW_S and NEW_D becomes part of NEW_TRANS->to.  */
3728                   state *new_s = new state;
3729                   decision *new_d = new decision (d1->test);
3730                   new_d->push_back (new transition (new_trans->labels, new_s,
3731                                                     new_trans->optional));
3732                   state::range r (start, end);
3733                   new_trans->to->replace (r, new_d);
3734                   new_s->push_back (r);
3735
3736                   /* Continue with an empty range.  */
3737                   start = 0;
3738
3739                   /* Continue from the decision after NEW_D.  */
3740                   end = new_d;
3741                 }
3742             }
3743         }
3744       new_trans->optional = true;
3745       new_trans->labels = *combined;
3746     }
3747   else
3748     {
3749       /* We're merging more than one existing transition together.
3750          Those transitions are successfully dividing the matching space
3751          and so we want to preserve them, even if they're optional.
3752
3753          Create a new transition with the union set of labels and make
3754          it go to a state that has the original transitions.  */
3755       decision *new_d = new decision (d1->test);
3756       for (unsigned int i = 0; i < intersecting.length (); ++i)
3757         new_d->push_back (d1->remove (intersecting[i]));
3758
3759       state *new_s = new state;
3760       new_s->push_back (new_d);
3761
3762       new_trans = new transition (*combined, new_s, true);
3763       d1->push_back (new_trans);
3764     }
3765
3766   /* We now have an optional transition with labels *COMBINED.  Decide
3767      whether we can use it as TRANS2 or whether we need to merge S2
3768      into the target of NEW_TRANS.  */
3769   gcc_assert (new_trans->optional);
3770   if (new_trans->labels == trans2->labels)
3771     {
3772       /* NEW_TRANS matches TRANS2.  Just merge the target states.  */
3773       new_trans->optional = trans2->optional;
3774       *next_s1 = new_trans->to;
3775       *next_s2 = trans2->to;
3776       *next_exclude = 0;
3777     }
3778   else
3779     {
3780       /* Try to merge TRANS2 into the target of the overlapping transition,
3781          but (to prevent infinite recursion or excessive redundancy) without
3782          creating another transition of the same type.  */
3783       *next_s1 = new_trans->to;
3784       *next_s2 = s2;
3785       *next_exclude = &new_trans->labels;
3786     }
3787   return true;
3788 }
3789
3790 /* Make progress in merging S2 into S1, given that each state in S2
3791    has a single decision.  If EXCLUDE is nonnull, avoid creating a new
3792    transition with the same test as S2's decision and with the labels
3793    in *EXCLUDE.
3794
3795    Return true if there is still work to do.  When returning true,
3796    set *NEXT_S1, *NEXT_S2 and *NEXT_EXCLUDE to the values that
3797    S1, S2 and EXCLUDE should have next time round.
3798
3799    If S1 and S2 both match a particular rtx, give priority to S1.  */
3800
3801 static bool
3802 merge_into_state_1 (state *s1, state *s2, const int_set *exclude,
3803                     state **next_s1, state **next_s2,
3804                     const int_set **next_exclude)
3805 {
3806   decision *d2 = s2->singleton ();
3807   if (decision *d1 = s1->last)
3808     {
3809       if (d1->test.terminal_p ())
3810         /* D1 is an unconditional return, so S2 can never match.  This can
3811            sometimes be a bug in the .md description, but might also happen
3812            if genconditions forces some conditions to true for certain
3813            configurations.  */
3814         return false;
3815
3816       /* Go backwards through the decisions in S1, stopping once we find one
3817          that could match the same thing as S2.  */
3818       while (d1->prev && mutually_exclusive_p (d1, d2))
3819         d1 = d1->prev;
3820
3821       /* Search forwards from that point, merging D2 into the first
3822          decision we can.  */
3823       for (; d1; d1 = d1->next)
3824         {
3825           /* If S2 performs some optional tests before testing the same thing
3826              as D1, those tests do not help to distinguish D1 and S2, so it's
3827              better to drop them.  Search through such optional decisions
3828              until we find something that tests the same thing as D1.  */
3829           state *sub_s2 = s2;
3830           for (;;)
3831             {
3832               decision *sub_d2 = sub_s2->singleton ();
3833               if (d1->test == sub_d2->test)
3834                 {
3835                   /* Only apply EXCLUDE if we're testing the same thing
3836                      as D2.  */
3837                   const int_set *sub_exclude = (d2 == sub_d2 ? exclude : 0);
3838
3839                   /* Try to merge SUB_S2 into D1.  This can only fail if
3840                      it would involve creating a new transition with
3841                      labels SUB_EXCLUDE.  */
3842                   if (merge_into_decision (d1, sub_s2, sub_exclude,
3843                                            next_s1, next_s2, next_exclude))
3844                     return *next_s2 != 0;
3845
3846                   /* Can't merge with D1; try a later decision.  */
3847                   break;
3848                 }
3849               transition *sub_trans2 = sub_d2->singleton ();
3850               if (!sub_trans2->optional)
3851                 /* Can't merge with D1; try a later decision.  */
3852                 break;
3853               sub_s2 = sub_trans2->to;
3854             }
3855         }
3856     }
3857
3858   /* We can't merge D2 with any existing decision.  Just add it to the end.  */
3859   s1->push_back (s2->release ());
3860   return false;
3861 }
3862
3863 /* Merge S2 into S1.  If they both match a particular rtx, give
3864    priority to S1.  Each state in S2 has a single decision.  */
3865
3866 static void
3867 merge_into_state (state *s1, state *s2)
3868 {
3869   const int_set *exclude = 0;
3870   while (s2 && merge_into_state_1 (s1, s2, exclude, &s1, &s2, &exclude))
3871     continue;
3872 }
3873
3874 /* Pairs a pattern that needs to be matched with the rtx position at
3875    which the pattern should occur.  */
3876 class pattern_pos {
3877 public:
3878   pattern_pos () {}
3879   pattern_pos (rtx, position *);
3880
3881   rtx pattern;
3882   position *pos;
3883 };
3884
3885 pattern_pos::pattern_pos (rtx pattern_in, position *pos_in)
3886   : pattern (pattern_in), pos (pos_in)
3887 {}
3888
3889 /* Compare entries according to their depth-first order.  There shouldn't
3890    be two entries at the same position.  */
3891
3892 bool
3893 operator < (const pattern_pos &e1, const pattern_pos &e2)
3894 {
3895   int diff = compare_positions (e1.pos, e2.pos);
3896   gcc_assert (diff != 0 || e1.pattern == e2.pattern);
3897   return diff < 0;
3898 }
3899
3900 /* Add new decisions to S that check whether the rtx at position POS
3901    matches PATTERN.  Return the state that is reached in that case.
3902    TOP_PATTERN is the overall pattern, as passed to match_pattern_1.  */
3903
3904 static state *
3905 match_pattern_2 (state *s, md_rtx_info *info, position *pos, rtx pattern)
3906 {
3907   auto_vec <pattern_pos, 32> worklist;
3908   auto_vec <pattern_pos, 32> pred_and_mode_tests;
3909   auto_vec <pattern_pos, 32> dup_tests;
3910
3911   worklist.safe_push (pattern_pos (pattern, pos));
3912   while (!worklist.is_empty ())
3913     {
3914       pattern_pos next = worklist.pop ();
3915       pattern = next.pattern;
3916       pos = next.pos;
3917       unsigned int reverse_s = worklist.length ();
3918
3919       enum rtx_code code = GET_CODE (pattern);
3920       switch (code)
3921         {
3922         case MATCH_OP_DUP:
3923         case MATCH_DUP:
3924         case MATCH_PAR_DUP:
3925           /* Add a test that the rtx matches the earlier one, but only
3926              after the structure and predicates have been checked.  */
3927           dup_tests.safe_push (pattern_pos (pattern, pos));
3928
3929           /* Use the same code check as the original operand.  */
3930           pattern = find_operand (info->def, XINT (pattern, 0), NULL_RTX);
3931           /* Fall through.  */
3932
3933         case MATCH_PARALLEL:
3934         case MATCH_OPERAND:
3935         case MATCH_SCRATCH:
3936         case MATCH_OPERATOR:
3937           {
3938             const char *pred_name = predicate_name (pattern);
3939             const struct pred_data *pred = 0;
3940             if (pred_name[0] != 0)
3941               {
3942                 pred = lookup_predicate (pred_name);
3943                 /* Only report errors once per rtx.  */
3944                 if (code == GET_CODE (pattern))
3945                   {
3946                     if (!pred)
3947                       error_at (info->loc, "unknown predicate '%s' used in %s",
3948                                 pred_name, GET_RTX_NAME (code));
3949                     else if (code == MATCH_PARALLEL
3950                              && pred->singleton != PARALLEL)
3951                       error_at (info->loc, "predicate '%s' used in"
3952                                 " match_parallel does not allow only PARALLEL",
3953                                 pred->name);
3954                   }
3955               }
3956
3957             if (code == MATCH_PARALLEL || code == MATCH_PAR_DUP)
3958               {
3959                 /* Check that we have a parallel with enough elements.  */
3960                 s = add_decision (s, rtx_test::code (pos), PARALLEL, false);
3961                 int min_len = XVECLEN (pattern, 2);
3962                 s = add_decision (s, rtx_test::veclen_ge (pos, min_len),
3963                                   true, false);
3964               }
3965             else
3966               {
3967                 /* Check that the rtx has one of codes accepted by the
3968                    predicate.  This is necessary when matching suboperands
3969                    of a MATCH_OPERATOR or MATCH_OP_DUP, since we can't
3970                    call XEXP (X, N) without checking that X has at least
3971                    N+1 operands.  */
3972                 int_set codes;
3973                 get_predicate_codes (pred, &codes);
3974                 bool need_codes = (pred
3975                                    && (code == MATCH_OPERATOR
3976                                        || code == MATCH_OP_DUP));
3977                 s = add_decision (s, rtx_test::code (pos), codes, !need_codes);
3978               }
3979
3980             /* Postpone the predicate check until we've checked the rest
3981                of the rtx structure.  */
3982             if (code == GET_CODE (pattern))
3983               pred_and_mode_tests.safe_push (pattern_pos (pattern, pos));
3984
3985             /* If we need to match suboperands, add them to the worklist.  */
3986             if (code == MATCH_OPERATOR || code == MATCH_PARALLEL)
3987               {
3988                 position **subpos_ptr;
3989                 enum position_type pos_type;
3990                 int i;
3991                 if (code == MATCH_OPERATOR || code == MATCH_OP_DUP)
3992                   {
3993                     pos_type = POS_XEXP;
3994                     subpos_ptr = &pos->xexps;
3995                     i = (code == MATCH_OPERATOR ? 2 : 1);
3996                   }
3997                 else
3998                   {
3999                     pos_type = POS_XVECEXP0;
4000                     subpos_ptr = &pos->xvecexp0s;
4001                     i = 2;
4002                   }
4003                 for (int j = 0; j < XVECLEN (pattern, i); ++j)
4004                   {
4005                     position *subpos = next_position (subpos_ptr, pos,
4006                                                       pos_type, j);
4007                     worklist.safe_push (pattern_pos (XVECEXP (pattern, i, j),
4008                                                subpos));
4009                     subpos_ptr = &subpos->next;
4010                   }
4011               }
4012             break;
4013           }
4014
4015         default:
4016           {
4017             /* Check that the rtx has the right code.  */
4018             s = add_decision (s, rtx_test::code (pos), code, false);
4019
4020             /* Queue a test for the mode if one is specified.  */
4021             if (GET_MODE (pattern) != VOIDmode)
4022               pred_and_mode_tests.safe_push (pattern_pos (pattern, pos));
4023
4024             /* Push subrtxes onto the worklist.  Match nonrtx operands now.  */
4025             const char *fmt = GET_RTX_FORMAT (code);
4026             position **subpos_ptr = &pos->xexps;
4027             for (size_t i = 0; fmt[i]; ++i)
4028               {
4029                 position *subpos = next_position (subpos_ptr, pos,
4030                                                   POS_XEXP, i);
4031                 switch (fmt[i])
4032                   {
4033                   case 'e': case 'u':
4034                     worklist.safe_push (pattern_pos (XEXP (pattern, i),
4035                                                      subpos));
4036                     break;
4037
4038                   case 'E':
4039                     {
4040                       /* Make sure the vector has the right number of
4041                          elements.  */
4042                       int length = XVECLEN (pattern, i);
4043                       s = add_decision (s, rtx_test::veclen (pos),
4044                                         length, false);
4045
4046                       position **subpos2_ptr = &pos->xvecexp0s;
4047                       for (int j = 0; j < length; j++)
4048                         {
4049                           position *subpos2 = next_position (subpos2_ptr, pos,
4050                                                              POS_XVECEXP0, j);
4051                           rtx x = XVECEXP (pattern, i, j);
4052                           worklist.safe_push (pattern_pos (x, subpos2));
4053                           subpos2_ptr = &subpos2->next;
4054                         }
4055                       break;
4056                     }
4057
4058                   case 'i':
4059                     /* Make sure that XINT (X, I) has the right value.  */
4060                     s = add_decision (s, rtx_test::int_field (pos, i),
4061                                       XINT (pattern, i), false);
4062                     break;
4063
4064                   case 'r':
4065                     /* Make sure that REGNO (X) has the right value.  */
4066                     gcc_assert (i == 0);
4067                     s = add_decision (s, rtx_test::regno_field (pos),
4068                                       REGNO (pattern), false);
4069                     break;
4070
4071                   case 'w':
4072                     /* Make sure that XWINT (X, I) has the right value.  */
4073                     s = add_decision (s, rtx_test::wide_int_field (pos, i),
4074                                       XWINT (pattern, 0), false);
4075                     break;
4076
4077                   case 'p':
4078                     /* We don't have a way of parsing polynomial offsets yet,
4079                        and hopefully never will.  */
4080                     s = add_decision (s, rtx_test::subreg_field (pos),
4081                                       SUBREG_BYTE (pattern).to_constant (),
4082                                       false);
4083                     break;
4084
4085                   case '0':
4086                     break;
4087
4088                   default:
4089                     gcc_unreachable ();
4090                   }
4091                 subpos_ptr = &subpos->next;
4092               }
4093           }
4094           break;
4095         }
4096       /* Operands are pushed onto the worklist so that later indices are
4097          nearer the top.  That's what we want for SETs, since a SET_SRC
4098          is a better discriminator than a SET_DEST.  In other cases it's
4099          usually better to match earlier indices first.  This is especially
4100          true of PARALLELs, where the first element tends to be the most
4101          individual.  It's also true for commutative operators, where the
4102          canonicalization rules say that the more complex operand should
4103          come first.  */
4104       if (code != SET && worklist.length () > reverse_s)
4105         std::reverse (&worklist[0] + reverse_s,
4106                       &worklist[0] + worklist.length ());
4107     }
4108
4109   /* Sort the predicate and mode tests so that they're in depth-first order.
4110      The main goal of this is to put SET_SRC match_operands after SET_DEST
4111      match_operands and after mode checks for the enclosing SET_SRC operators
4112      (such as the mode of a PLUS in an addition instruction).  The latter
4113      two types of test can determine the mode exactly, whereas a SET_SRC
4114      match_operand often has to cope with the possibility of the operand
4115      being a modeless constant integer.  E.g. something that matches
4116      register_operand (x, SImode) never matches register_operand (x, DImode),
4117      but a const_int that matches immediate_operand (x, SImode) also matches
4118      immediate_operand (x, DImode).  The register_operand cases can therefore
4119      be distinguished by a switch on the mode, but the immediate_operand
4120      cases can't.  */
4121   if (pred_and_mode_tests.length () > 1)
4122     std::sort (&pred_and_mode_tests[0],
4123                &pred_and_mode_tests[0] + pred_and_mode_tests.length ());
4124
4125   /* Add the mode and predicate tests.  */
4126   pattern_pos *e;
4127   unsigned int i;
4128   FOR_EACH_VEC_ELT (pred_and_mode_tests, i, e)
4129     {
4130       switch (GET_CODE (e->pattern))
4131         {
4132         case MATCH_PARALLEL:
4133         case MATCH_OPERAND:
4134         case MATCH_SCRATCH:
4135         case MATCH_OPERATOR:
4136           {
4137             int opno = XINT (e->pattern, 0);
4138             num_operands = MAX (num_operands, opno + 1);
4139             const char *pred_name = predicate_name (e->pattern);
4140             if (pred_name[0])
4141               {
4142                 const struct pred_data *pred = lookup_predicate (pred_name);
4143                 /* Check the mode first, to distinguish things like SImode
4144                    and DImode register_operands, as described above.  */
4145                 machine_mode mode = GET_MODE (e->pattern);
4146                 if (pred && safe_predicate_mode (pred, mode))
4147                   s = add_decision (s, rtx_test::mode (e->pos), mode, true);
4148
4149                 /* Assign to operands[] first, so that the rtx usually doesn't
4150                    need to be live across the call to the predicate.
4151
4152                    This shouldn't cause a problem with dirtying the page,
4153                    since we fully expect to assign to operands[] at some point,
4154                    and since the caller usually writes to other parts of
4155                    recog_data anyway.  */
4156                 s = add_decision (s, rtx_test::set_op (e->pos, opno),
4157                                   true, false);
4158                 s = add_decision (s, rtx_test::predicate (e->pos, pred, mode),
4159                                   true, false);
4160               }
4161             else
4162               /* Historically we've ignored the mode when there's no
4163                  predicate.  Just set up operands[] unconditionally.  */
4164               s = add_decision (s, rtx_test::set_op (e->pos, opno),
4165                                 true, false);
4166             break;
4167           }
4168
4169         default:
4170           s = add_decision (s, rtx_test::mode (e->pos),
4171                             GET_MODE (e->pattern), false);
4172           break;
4173         }
4174     }
4175
4176   /* Finally add rtx_equal_p checks for duplicated operands.  */
4177   FOR_EACH_VEC_ELT (dup_tests, i, e)
4178     s = add_decision (s, rtx_test::duplicate (e->pos, XINT (e->pattern, 0)),
4179                       true, false);
4180   return s;
4181 }
4182
4183 /* Add new decisions to S that make it return ACCEPTANCE if:
4184
4185    (1) the rtx doesn't match anything already matched by S
4186    (2) the rtx matches TOP_PATTERN and
4187    (3) the C test required by INFO->def is true
4188
4189    For peephole2, TOP_PATTERN is a SEQUENCE of the instruction patterns
4190    to match, otherwise it is a single instruction pattern.  */
4191
4192 static void
4193 match_pattern_1 (state *s, md_rtx_info *info, rtx pattern,
4194                  acceptance_type acceptance)
4195 {
4196   if (acceptance.type == PEEPHOLE2)
4197     {
4198       /* Match each individual instruction.  */
4199       position **subpos_ptr = &peep2_insn_pos_list;
4200       int count = 0;
4201       for (int i = 0; i < XVECLEN (pattern, 0); ++i)
4202         {
4203           rtx x = XVECEXP (pattern, 0, i);
4204           position *subpos = next_position (subpos_ptr, &root_pos,
4205                                             POS_PEEP2_INSN, count);
4206           if (count > 0)
4207             s = add_decision (s, rtx_test::peep2_count (count + 1),
4208                               true, false);
4209           s = match_pattern_2 (s, info, subpos, x);
4210           subpos_ptr = &subpos->next;
4211           count += 1;
4212         }
4213       acceptance.u.full.u.match_len = count - 1;
4214     }
4215   else
4216     {
4217       /* Make the rtx itself.  */
4218       s = match_pattern_2 (s, info, &root_pos, pattern);
4219
4220       /* If the match is only valid when extra clobbers are added,
4221          make sure we're able to pass that information to the caller.  */
4222       if (acceptance.type == RECOG && acceptance.u.full.u.num_clobbers)
4223         s = add_decision (s, rtx_test::have_num_clobbers (), true, false);
4224     }
4225
4226   /* Make sure that the C test is true.  */
4227   const char *c_test = get_c_test (info->def);
4228   if (maybe_eval_c_test (c_test) != 1)
4229     s = add_decision (s, rtx_test::c_test (c_test), true, false);
4230
4231   /* Accept the pattern.  */
4232   add_decision (s, rtx_test::accept (acceptance), true, false);
4233 }
4234
4235 /* Like match_pattern_1, but (if merge_states_p) try to merge the
4236    decisions with what's already in S, to reduce the amount of
4237    backtracking.  */
4238
4239 static void
4240 match_pattern (state *s, md_rtx_info *info, rtx pattern,
4241                acceptance_type acceptance)
4242 {
4243   if (merge_states_p)
4244     {
4245       state root;
4246       /* Add the decisions to a fresh state and then merge the full tree
4247          into the existing one.  */
4248       match_pattern_1 (&root, info, pattern, acceptance);
4249       merge_into_state (s, &root);
4250     }
4251   else
4252     match_pattern_1 (s, info, pattern, acceptance);
4253 }
4254
4255 /* Begin the output file.  */
4256
4257 static void
4258 write_header (void)
4259 {
4260   puts ("\
4261 /* Generated automatically by the program `genrecog' from the target\n\
4262    machine description file.  */\n\
4263 \n\
4264 #define IN_TARGET_CODE 1\n\
4265 \n\
4266 #include \"config.h\"\n\
4267 #include \"system.h\"\n\
4268 #include \"coretypes.h\"\n\
4269 #include \"backend.h\"\n\
4270 #include \"predict.h\"\n\
4271 #include \"rtl.h\"\n\
4272 #include \"memmodel.h\"\n\
4273 #include \"tm_p.h\"\n\
4274 #include \"emit-rtl.h\"\n\
4275 #include \"insn-config.h\"\n\
4276 #include \"recog.h\"\n\
4277 #include \"output.h\"\n\
4278 #include \"flags.h\"\n\
4279 #include \"df.h\"\n\
4280 #include \"resource.h\"\n\
4281 #include \"diagnostic-core.h\"\n\
4282 #include \"reload.h\"\n\
4283 #include \"regs.h\"\n\
4284 #include \"tm-constrs.h\"\n\
4285 \n");
4286
4287   puts ("\n\
4288 /* `recog' contains a decision tree that recognizes whether the rtx\n\
4289    X0 is a valid instruction.\n\
4290 \n\
4291    recog returns -1 if the rtx is not valid.  If the rtx is valid, recog\n\
4292    returns a nonnegative number which is the insn code number for the\n\
4293    pattern that matched.  This is the same as the order in the machine\n\
4294    description of the entry that matched.  This number can be used as an\n\
4295    index into `insn_data' and other tables.\n");
4296   puts ("\
4297    The third parameter to recog is an optional pointer to an int.  If\n\
4298    present, recog will accept a pattern if it matches except for missing\n\
4299    CLOBBER expressions at the end.  In that case, the value pointed to by\n\
4300    the optional pointer will be set to the number of CLOBBERs that need\n\
4301    to be added (it should be initialized to zero by the caller).  If it");
4302   puts ("\
4303    is set nonzero, the caller should allocate a PARALLEL of the\n\
4304    appropriate size, copy the initial entries, and call add_clobbers\n\
4305    (found in insn-emit.cc) to fill in the CLOBBERs.\n\
4306 ");
4307
4308   puts ("\n\
4309    The function split_insns returns 0 if the rtl could not\n\
4310    be split or the split rtl as an INSN list if it can be.\n\
4311 \n\
4312    The function peephole2_insns returns 0 if the rtl could not\n\
4313    be matched. If there was a match, the new rtl is returned in an INSN list,\n\
4314    and LAST_INSN will point to the last recognized insn in the old sequence.\n\
4315 */\n\n");
4316 }
4317
4318 /* Return the C type of a parameter with type TYPE.  */
4319
4320 static const char *
4321 parameter_type_string (parameter::type_enum type)
4322 {
4323   switch (type)
4324     {
4325     case parameter::UNSET:
4326       break;
4327
4328     case parameter::CODE:
4329       return "rtx_code";
4330
4331     case parameter::MODE:
4332       return "machine_mode";
4333
4334     case parameter::INT:
4335       return "int";
4336
4337     case parameter::UINT:
4338       return "unsigned int";
4339
4340     case parameter::WIDE_INT:
4341       return "HOST_WIDE_INT";
4342     }
4343   gcc_unreachable ();
4344 }
4345
4346 /* Return true if ACCEPTANCE requires only a single C statement even in
4347    a backtracking context.  */
4348
4349 static bool
4350 single_statement_p (const acceptance_type &acceptance)
4351 {
4352   if (acceptance.partial_p)
4353     /* We need to handle failures of the subroutine.  */
4354     return false;
4355   switch (acceptance.type)
4356     {
4357     case SUBPATTERN:
4358     case SPLIT:
4359       return true;
4360
4361     case RECOG:
4362       /* False if we need to assign to pnum_clobbers.  */
4363       return acceptance.u.full.u.num_clobbers == 0;
4364
4365     case PEEPHOLE2:
4366       /* We need to assign to pmatch_len_ and handle null returns from the
4367          peephole2 routine.  */
4368       return false;
4369     }
4370   gcc_unreachable ();
4371 }
4372
4373 /* Return the C failure value for a routine of type TYPE.  */
4374
4375 static const char *
4376 get_failure_return (routine_type type)
4377 {
4378   switch (type)
4379     {
4380     case SUBPATTERN:
4381     case RECOG:
4382       return "-1";
4383
4384     case SPLIT:
4385     case PEEPHOLE2:
4386       return "NULL";
4387     }
4388   gcc_unreachable ();
4389 }
4390
4391 /* Indicates whether a block of code always returns or whether it can fall
4392    through.  */
4393
4394 enum exit_state {
4395   ES_RETURNED,
4396   ES_FALLTHROUGH
4397 };
4398
4399 /* Information used while writing out code.  */
4400
4401 class output_state
4402 {
4403 public:
4404   /* The type of routine that we're generating.  */
4405   routine_type type;
4406
4407   /* Maps position ids to xN variable numbers.  The entry is only valid if
4408      it is less than the length of VAR_TO_ID, but this holds for every position
4409      tested by a state when writing out that state.  */
4410   auto_vec <unsigned int> id_to_var;
4411
4412   /* Maps xN variable numbers to position ids.  */
4413   auto_vec <unsigned int> var_to_id;
4414
4415   /* Index N is true if variable xN has already been set.  */
4416   auto_vec <bool> seen_vars;
4417 };
4418
4419 /* Return true if D is a call to a pattern routine and if there is some X
4420    such that the transition for pattern result N goes to a successful return
4421    with code X+N.  When returning true, set *BASE_OUT to this X and *COUNT_OUT
4422    to the number of return values.  (We know that every PATTERN decision has
4423    a transition for every successful return.)  */
4424
4425 static bool
4426 terminal_pattern_p (decision *d, unsigned int *base_out,
4427                     unsigned int *count_out)
4428 {
4429   if (d->test.kind != rtx_test::PATTERN)
4430     return false;
4431   unsigned int base = 0;
4432   unsigned int count = 0;
4433   for (transition *trans = d->first; trans; trans = trans->next)
4434     {
4435       if (trans->is_param || trans->labels.length () != 1)
4436         return false;
4437       decision *subd = trans->to->singleton ();
4438       if (!subd || subd->test.kind != rtx_test::ACCEPT)
4439         return false;
4440       unsigned int this_base = (subd->test.u.acceptance.u.full.code
4441                                 - trans->labels[0]);
4442       if (trans == d->first)
4443         base = this_base;
4444       else if (base != this_base)
4445         return false;
4446       count += 1;
4447     }
4448   *base_out = base;
4449   *count_out = count;
4450   return true;
4451 }
4452
4453 /* Return true if TEST doesn't test an rtx or if the rtx it tests is
4454    already available in state OS.  */
4455
4456 static bool
4457 test_position_available_p (output_state *os, const rtx_test &test)
4458 {
4459   return (!test.pos
4460           || test.pos_operand >= 0
4461           || os->seen_vars[os->id_to_var[test.pos->id]]);
4462 }
4463
4464 /* Like printf, but print INDENT spaces at the beginning.  */
4465
4466 static void ATTRIBUTE_PRINTF_2
4467 printf_indent (unsigned int indent, const char *format, ...)
4468 {
4469   va_list ap;
4470   va_start (ap, format);
4471   printf ("%*s", indent, "");
4472   vprintf (format, ap);
4473   va_end (ap);
4474 }
4475
4476 /* Emit code to initialize the variable associated with POS, if it isn't
4477    already valid in state OS.  Indent each line by INDENT spaces.  Update
4478    OS with the new state.  */
4479
4480 static void
4481 change_state (output_state *os, position *pos, unsigned int indent)
4482 {
4483   unsigned int var = os->id_to_var[pos->id];
4484   gcc_assert (var < os->var_to_id.length () && os->var_to_id[var] == pos->id);
4485   if (os->seen_vars[var])
4486     return;
4487   switch (pos->type)
4488     {
4489     case POS_PEEP2_INSN:
4490       printf_indent (indent, "x%d = PATTERN (peep2_next_insn (%d));\n",
4491                      var, pos->arg);
4492       break;
4493
4494     case POS_XEXP:
4495       change_state (os, pos->base, indent);
4496       printf_indent (indent, "x%d = XEXP (x%d, %d);\n",
4497                      var, os->id_to_var[pos->base->id], pos->arg);
4498       break;
4499
4500     case POS_XVECEXP0:
4501       change_state (os, pos->base, indent);
4502       printf_indent (indent, "x%d = XVECEXP (x%d, 0, %d);\n",
4503                      var, os->id_to_var[pos->base->id], pos->arg);
4504       break;
4505     }
4506   os->seen_vars[var] = true;
4507 }
4508
4509 /* Print the enumerator constant for CODE -- the upcase version of
4510    the name.  */
4511
4512 static void
4513 print_code (enum rtx_code code)
4514 {
4515   const char *p;
4516   for (p = GET_RTX_NAME (code); *p; p++)
4517     putchar (TOUPPER (*p));
4518 }
4519
4520 /* Emit a uint64_t as an integer constant expression.  We need to take
4521    special care to avoid "decimal constant is so large that it is unsigned"
4522    warnings in the resulting code.  */
4523
4524 static void
4525 print_host_wide_int (uint64_t val)
4526 {
4527   uint64_t min = uint64_t (1) << (HOST_BITS_PER_WIDE_INT - 1);
4528   if (val == min)
4529     printf ("(" HOST_WIDE_INT_PRINT_DEC_C " - 1)", val + 1);
4530   else
4531     printf (HOST_WIDE_INT_PRINT_DEC_C, val);
4532 }
4533
4534 /* Print the C expression for actual parameter PARAM.  */
4535
4536 static void
4537 print_parameter_value (const parameter &param)
4538 {
4539   if (param.is_param)
4540     printf ("i%d", (int) param.value + 1);
4541   else
4542     switch (param.type)
4543       {
4544       case parameter::UNSET:
4545         gcc_unreachable ();
4546         break;
4547
4548       case parameter::CODE:
4549         print_code ((enum rtx_code) param.value);
4550         break;
4551
4552       case parameter::MODE:
4553         printf ("E_%smode", GET_MODE_NAME ((machine_mode) param.value));
4554         break;
4555
4556       case parameter::INT:
4557         printf ("%d", (int) param.value);
4558         break;
4559
4560       case parameter::UINT:
4561         printf ("%u", (unsigned int) param.value);
4562         break;
4563
4564       case parameter::WIDE_INT:
4565         print_host_wide_int (param.value);
4566         break;
4567       }
4568 }
4569
4570 /* Print the C expression for the rtx tested by TEST.  */
4571
4572 static void
4573 print_test_rtx (output_state *os, const rtx_test &test)
4574 {
4575   if (test.pos_operand >= 0)
4576     printf ("operands[%d]", test.pos_operand);
4577   else
4578     printf ("x%d", os->id_to_var[test.pos->id]);
4579 }
4580
4581 /* Print the C expression for non-boolean test TEST.  */
4582
4583 static void
4584 print_nonbool_test (output_state *os, const rtx_test &test)
4585 {
4586   switch (test.kind)
4587     {
4588     case rtx_test::CODE:
4589       printf ("GET_CODE (");
4590       print_test_rtx (os, test);
4591       printf (")");
4592       break;
4593
4594     case rtx_test::MODE:
4595       printf ("GET_MODE (");
4596       print_test_rtx (os, test);
4597       printf (")");
4598       break;
4599
4600     case rtx_test::VECLEN:
4601       printf ("XVECLEN (");
4602       print_test_rtx (os, test);
4603       printf (", 0)");
4604       break;
4605
4606     case rtx_test::INT_FIELD:
4607       printf ("XINT (");
4608       print_test_rtx (os, test);
4609       printf (", %d)", test.u.opno);
4610       break;
4611
4612     case rtx_test::REGNO_FIELD:
4613       printf ("REGNO (");
4614       print_test_rtx (os, test);
4615       printf (")");
4616       break;
4617
4618     case rtx_test::SUBREG_FIELD:
4619       printf ("SUBREG_BYTE (");
4620       print_test_rtx (os, test);
4621       printf (")");
4622       break;
4623
4624     case rtx_test::WIDE_INT_FIELD:
4625       printf ("XWINT (");
4626       print_test_rtx (os, test);
4627       printf (", %d)", test.u.opno);
4628       break;
4629
4630     case rtx_test::PATTERN:
4631       {
4632         pattern_routine *routine = test.u.pattern->routine;
4633         printf ("pattern%d (", routine->pattern_id);
4634         const char *sep = "";
4635         if (test.pos)
4636           {
4637             print_test_rtx (os, test);
4638             sep = ", ";
4639           }
4640         if (routine->insn_p)
4641           {
4642             printf ("%sinsn", sep);
4643             sep = ", ";
4644           }
4645         if (routine->pnum_clobbers_p)
4646           {
4647             printf ("%spnum_clobbers", sep);
4648             sep = ", ";
4649           }
4650         for (unsigned int i = 0; i < test.u.pattern->params.length (); ++i)
4651           {
4652             fputs (sep, stdout);
4653             print_parameter_value (test.u.pattern->params[i]);
4654             sep = ", ";
4655           }
4656         printf (")");
4657         break;
4658       }
4659
4660     case rtx_test::PEEP2_COUNT:
4661     case rtx_test::VECLEN_GE:
4662     case rtx_test::SAVED_CONST_INT:
4663     case rtx_test::DUPLICATE:
4664     case rtx_test::PREDICATE:
4665     case rtx_test::SET_OP:
4666     case rtx_test::HAVE_NUM_CLOBBERS:
4667     case rtx_test::C_TEST:
4668     case rtx_test::ACCEPT:
4669       gcc_unreachable ();
4670     }
4671 }
4672
4673 /* IS_PARAM and LABEL are taken from a transition whose source
4674    decision performs TEST.  Print the C code for the label.  */
4675
4676 static void
4677 print_label_value (const rtx_test &test, bool is_param, uint64_t value)
4678 {
4679   print_parameter_value (parameter (transition_parameter_type (test.kind),
4680                                     is_param, value));
4681 }
4682
4683 /* If IS_PARAM, print code to compare TEST with the C variable i<VALUE+1>.
4684    If !IS_PARAM, print code to compare TEST with the C constant VALUE.
4685    Test for inequality if INVERT_P, otherwise test for equality.  */
4686
4687 static void
4688 print_test (output_state *os, const rtx_test &test, bool is_param,
4689             uint64_t value, bool invert_p)
4690 {
4691   switch (test.kind)
4692     {
4693       /* Handle the non-boolean TESTs.  */
4694     case rtx_test::CODE:
4695     case rtx_test::MODE:
4696     case rtx_test::VECLEN:
4697     case rtx_test::REGNO_FIELD:
4698     case rtx_test::INT_FIELD:
4699     case rtx_test::WIDE_INT_FIELD:
4700     case rtx_test::PATTERN:
4701       print_nonbool_test (os, test);
4702       printf (" %s ", invert_p ? "!=" : "==");
4703       print_label_value (test, is_param, value);
4704       break;
4705
4706     case rtx_test::SUBREG_FIELD:
4707       printf ("%s (", invert_p ? "maybe_ne" : "known_eq");
4708       print_nonbool_test (os, test);
4709       printf (", ");
4710       print_label_value (test, is_param, value);
4711       printf (")");
4712       break;
4713
4714     case rtx_test::SAVED_CONST_INT:
4715       gcc_assert (!is_param && value == 1);
4716       print_test_rtx (os, test);
4717       printf (" %s const_int_rtx[MAX_SAVED_CONST_INT + ",
4718               invert_p ? "!=" : "==");
4719       print_parameter_value (parameter (parameter::INT,
4720                                         test.u.integer.is_param,
4721                                         test.u.integer.value));
4722       printf ("]");
4723       break;
4724
4725     case rtx_test::PEEP2_COUNT:
4726       gcc_assert (!is_param && value == 1);
4727       printf ("peep2_current_count %s %d", invert_p ? "<" : ">=",
4728               test.u.min_len);
4729       break;
4730
4731     case rtx_test::VECLEN_GE:
4732       gcc_assert (!is_param && value == 1);
4733       printf ("XVECLEN (");
4734       print_test_rtx (os, test);
4735       printf (", 0) %s %d", invert_p ? "<" : ">=", test.u.min_len);
4736       break;
4737
4738     case rtx_test::PREDICATE:
4739       gcc_assert (!is_param && value == 1);
4740       printf ("%s%s (", invert_p ? "!" : "", test.u.predicate.data->name);
4741       print_test_rtx (os, test);
4742       printf (", ");
4743       print_parameter_value (parameter (parameter::MODE,
4744                                         test.u.predicate.mode_is_param,
4745                                         test.u.predicate.mode));
4746       printf (")");
4747       break;
4748
4749     case rtx_test::DUPLICATE:
4750       gcc_assert (!is_param && value == 1);
4751       printf ("%srtx_equal_p (", invert_p ? "!" : "");
4752       print_test_rtx (os, test);
4753       printf (", operands[%d])", test.u.opno);
4754       break;
4755
4756     case rtx_test::HAVE_NUM_CLOBBERS:
4757       gcc_assert (!is_param && value == 1);
4758       printf ("pnum_clobbers %s NULL", invert_p ? "==" : "!=");
4759       break;
4760
4761     case rtx_test::C_TEST:
4762       gcc_assert (!is_param && value == 1);
4763       if (invert_p)
4764         printf ("!");
4765       rtx_reader_ptr->print_c_condition (test.u.string);
4766       break;
4767
4768     case rtx_test::ACCEPT:
4769     case rtx_test::SET_OP:
4770       gcc_unreachable ();
4771     }
4772 }
4773
4774 static exit_state print_decision (output_state *, decision *,
4775                                   unsigned int, bool);
4776
4777 /* Print code to perform S, indent each line by INDENT spaces.
4778    IS_FINAL is true if there are no fallback decisions to test on failure;
4779    if the state fails then the entire routine fails.  */
4780
4781 static exit_state
4782 print_state (output_state *os, state *s, unsigned int indent, bool is_final)
4783 {
4784   exit_state es = ES_FALLTHROUGH;
4785   for (decision *d = s->first; d; d = d->next)
4786     es = print_decision (os, d, indent, is_final && !d->next);
4787   if (es != ES_RETURNED && is_final)
4788     {
4789       printf_indent (indent, "return %s;\n", get_failure_return (os->type));
4790       es = ES_RETURNED;
4791     }
4792   return es;
4793 }
4794
4795 /* Print the code for subroutine call ACCEPTANCE (for which partial_p
4796    is known to be true).  Return the C condition that indicates a successful
4797    match.  */
4798
4799 static const char *
4800 print_subroutine_call (const acceptance_type &acceptance)
4801 {
4802   switch (acceptance.type)
4803     {
4804     case SUBPATTERN:
4805       gcc_unreachable ();
4806
4807     case RECOG:
4808       printf ("recog_%d (x1, insn, pnum_clobbers)",
4809               acceptance.u.subroutine_id);
4810       return ">= 0";
4811
4812     case SPLIT:
4813       printf ("split_%d (x1, insn)", acceptance.u.subroutine_id);
4814       return "!= NULL_RTX";
4815
4816     case PEEPHOLE2:
4817       printf ("peephole2_%d (x1, insn, pmatch_len_)",
4818               acceptance.u.subroutine_id);
4819       return "!= NULL_RTX";
4820     }
4821   gcc_unreachable ();
4822 }
4823
4824 /* Print code for the successful match described by ACCEPTANCE.
4825    INDENT and IS_FINAL are as for print_state.  */
4826
4827 static exit_state
4828 print_acceptance (const acceptance_type &acceptance, unsigned int indent,
4829                   bool is_final)
4830 {
4831   if (acceptance.partial_p)
4832     {
4833       /* Defer the rest of the match to a subroutine.  */
4834       if (is_final)
4835         {
4836           printf_indent (indent, "return ");
4837           print_subroutine_call (acceptance);
4838           printf (";\n");
4839           return ES_RETURNED;
4840         }
4841       else
4842         {
4843           printf_indent (indent, "res = ");
4844           const char *res_test = print_subroutine_call (acceptance);
4845           printf (";\n");
4846           printf_indent (indent, "if (res %s)\n", res_test);
4847           printf_indent (indent + 2, "return res;\n");
4848           return ES_FALLTHROUGH;
4849         }
4850     }
4851   switch (acceptance.type)
4852     {
4853     case SUBPATTERN:
4854       printf_indent (indent, "return %d;\n", acceptance.u.full.code);
4855       return ES_RETURNED;
4856
4857     case RECOG:
4858       if (acceptance.u.full.u.num_clobbers != 0)
4859         printf_indent (indent, "*pnum_clobbers = %d;\n",
4860                        acceptance.u.full.u.num_clobbers);
4861       printf_indent (indent, "return %d; /* %s */\n", acceptance.u.full.code,
4862                      get_insn_name (acceptance.u.full.code));
4863       return ES_RETURNED;
4864
4865     case SPLIT:
4866       printf_indent (indent, "return gen_split_%d (insn, operands);\n",
4867                      acceptance.u.full.code);
4868       return ES_RETURNED;
4869
4870     case PEEPHOLE2:
4871       printf_indent (indent, "*pmatch_len_ = %d;\n",
4872                      acceptance.u.full.u.match_len);
4873       if (is_final)
4874         {
4875           printf_indent (indent, "return gen_peephole2_%d (insn, operands);\n",
4876                          acceptance.u.full.code);
4877           return ES_RETURNED;
4878         }
4879       else
4880         {
4881           printf_indent (indent, "res = gen_peephole2_%d (insn, operands);\n",
4882                          acceptance.u.full.code);
4883           printf_indent (indent, "if (res != NULL_RTX)\n");
4884           printf_indent (indent + 2, "return res;\n");
4885           return ES_FALLTHROUGH;
4886         }
4887     }
4888   gcc_unreachable ();
4889 }
4890
4891 /* Print code to perform D.  INDENT and IS_FINAL are as for print_state.  */
4892
4893 static exit_state
4894 print_decision (output_state *os, decision *d, unsigned int indent,
4895                 bool is_final)
4896 {
4897   uint64_t label;
4898   unsigned int base, count;
4899
4900   /* Make sure the rtx under test is available either in operands[] or
4901      in an xN variable.  */
4902   if (d->test.pos && d->test.pos_operand < 0)
4903     change_state (os, d->test.pos, indent);
4904
4905   /* Look for cases where a pattern routine P1 calls another pattern routine
4906      P2 and where P1 returns X + BASE whenever P2 returns X.  If IS_FINAL
4907      is true and BASE is zero we can simply use:
4908
4909         return patternN (...);
4910
4911      Otherwise we can use:
4912
4913         res = patternN (...);
4914         if (res >= 0)
4915           return res + BASE;
4916
4917      However, if BASE is nonzero and patternN only returns 0 or -1,
4918      the usual "return BASE;" is better than "return res + BASE;".
4919      If BASE is zero, "return res;" should be better than "return 0;",
4920      since no assignment to the return register is required.  */
4921   if (os->type == SUBPATTERN
4922       && terminal_pattern_p (d, &base, &count)
4923       && (base == 0 || count > 1))
4924     {
4925       if (is_final && base == 0)
4926         {
4927           printf_indent (indent, "return ");
4928           print_nonbool_test (os, d->test);
4929           printf ("; /* [-1, %d] */\n", count - 1);
4930           return ES_RETURNED;
4931         }
4932       else
4933         {
4934           printf_indent (indent, "res = ");
4935           print_nonbool_test (os, d->test);
4936           printf (";\n");
4937           printf_indent (indent, "if (res >= 0)\n");
4938           printf_indent (indent + 2, "return res");
4939           if (base != 0)
4940             printf (" + %d", base);
4941           printf ("; /* [%d, %d] */\n", base, base + count - 1);
4942           return ES_FALLTHROUGH;
4943         }
4944     }
4945   else if (d->test.kind == rtx_test::ACCEPT)
4946     return print_acceptance (d->test.u.acceptance, indent, is_final);
4947   else if (d->test.kind == rtx_test::SET_OP)
4948     {
4949       printf_indent (indent, "operands[%d] = ", d->test.u.opno);
4950       print_test_rtx (os, d->test);
4951       printf (";\n");
4952       return print_state (os, d->singleton ()->to, indent, is_final);
4953     }
4954   /* Handle decisions with a single transition and a single transition
4955      label.  */
4956   else if (d->if_statement_p (&label))
4957     {
4958       transition *trans = d->singleton ();
4959       if (mark_optional_transitions_p && trans->optional)
4960         printf_indent (indent, "/* OPTIONAL IF */\n");
4961
4962       /* Print the condition associated with TRANS.  Invert it if IS_FINAL,
4963          so that we return immediately on failure and fall through on
4964          success.  */
4965       printf_indent (indent, "if (");
4966       print_test (os, d->test, trans->is_param, label, is_final);
4967
4968       /* Look for following states that would be handled by this code
4969          on recursion.  If they don't need any preparatory statements,
4970          include them in the current "if" statement rather than creating
4971          a new one.  */
4972       for (;;)
4973         {
4974           d = trans->to->singleton ();
4975           if (!d
4976               || d->test.kind == rtx_test::ACCEPT
4977               || d->test.kind == rtx_test::SET_OP
4978               || !d->if_statement_p (&label)
4979               || !test_position_available_p (os, d->test))
4980             break;
4981           trans = d->first;
4982           printf ("\n");
4983           if (mark_optional_transitions_p && trans->optional)
4984             printf_indent (indent + 4, "/* OPTIONAL IF */\n");
4985           printf_indent (indent + 4, "%s ", is_final ? "||" : "&&");
4986           print_test (os, d->test, trans->is_param, label, is_final);
4987         }
4988       printf (")\n");
4989
4990       /* Print the conditional code with INDENT + 2 and the fallthrough
4991          code with indent INDENT.  */
4992       state *to = trans->to;
4993       if (is_final)
4994         {
4995           /* We inverted the condition above, so return failure in the
4996              "if" body and fall through to the target of the transition.  */
4997           printf_indent (indent + 2, "return %s;\n",
4998                          get_failure_return (os->type));
4999           return print_state (os, to, indent, is_final);
5000         }
5001       else if (to->singleton ()
5002                && to->first->test.kind == rtx_test::ACCEPT
5003                && single_statement_p (to->first->test.u.acceptance))
5004         {
5005           /* The target of the transition is a simple "return" statement.
5006              It doesn't need any braces and doesn't fall through.  */
5007           if (print_acceptance (to->first->test.u.acceptance,
5008                                 indent + 2, true) != ES_RETURNED)
5009             gcc_unreachable ();
5010           return ES_FALLTHROUGH;
5011         }
5012       else
5013         {
5014           /* The general case.  Output code for the target of the transition
5015              in braces.  This will not invalidate any of the xN variables
5016              that are already valid, but we mustn't rely on any that are
5017              set by the "if" body.  */
5018           auto_vec <bool, 32> old_seen;
5019           old_seen.safe_splice (os->seen_vars);
5020
5021           printf_indent (indent + 2, "{\n");
5022           print_state (os, trans->to, indent + 4, is_final);
5023           printf_indent (indent + 2, "}\n");
5024
5025           os->seen_vars.truncate (0);
5026           os->seen_vars.splice (old_seen);
5027           return ES_FALLTHROUGH;
5028         }
5029     }
5030   else
5031     {
5032       /* Output the decision as a switch statement.  */
5033       printf_indent (indent, "switch (");
5034       print_nonbool_test (os, d->test);
5035       printf (")\n");
5036
5037       /* Each case statement starts with the same set of valid variables.
5038          These are also the only variables will be valid on fallthrough.  */
5039       auto_vec <bool, 32> old_seen;
5040       old_seen.safe_splice (os->seen_vars);
5041
5042       printf_indent (indent + 2, "{\n");
5043       for (transition *trans = d->first; trans; trans = trans->next)
5044         {
5045           gcc_assert (!trans->is_param);
5046           if (mark_optional_transitions_p && trans->optional)
5047             printf_indent (indent + 2, "/* OPTIONAL CASE */\n");
5048           for (int_set::iterator j = trans->labels.begin ();
5049                j != trans->labels.end (); ++j)
5050             {
5051               printf_indent (indent + 2, "case ");
5052               print_label_value (d->test, trans->is_param, *j);
5053               printf (":\n");
5054             }
5055           if (print_state (os, trans->to, indent + 4, is_final))
5056             {
5057               /* The state can fall through.  Add an explicit break.  */
5058               gcc_assert (!is_final);
5059               printf_indent (indent + 4, "break;\n");
5060             }
5061           printf ("\n");
5062
5063           /* Restore the original set of valid variables.  */
5064           os->seen_vars.truncate (0);
5065           os->seen_vars.splice (old_seen);
5066         }
5067       /* Add a default case.  */
5068       printf_indent (indent + 2, "default:\n");
5069       if (is_final)
5070         printf_indent (indent + 4, "return %s;\n",
5071                        get_failure_return (os->type));
5072       else
5073         printf_indent (indent + 4, "break;\n");
5074       printf_indent (indent + 2, "}\n");
5075       return is_final ? ES_RETURNED : ES_FALLTHROUGH;
5076     }
5077 }
5078
5079 /* Make sure that OS has a position variable for POS.  ROOT_P is true if
5080    POS is the root position for the routine.  */
5081
5082 static void
5083 assign_position_var (output_state *os, position *pos, bool root_p)
5084 {
5085   unsigned int idx = os->id_to_var[pos->id];
5086   if (idx < os->var_to_id.length () && os->var_to_id[idx] == pos->id)
5087     return;
5088   if (!root_p && pos->type != POS_PEEP2_INSN)
5089     assign_position_var (os, pos->base, false);
5090   os->id_to_var[pos->id] = os->var_to_id.length ();
5091   os->var_to_id.safe_push (pos->id);
5092 }
5093
5094 /* Make sure that OS has the position variables required by S.  */
5095
5096 static void
5097 assign_position_vars (output_state *os, state *s)
5098 {
5099   for (decision *d = s->first; d; d = d->next)
5100     {
5101       /* Positions associated with operands can be read from the
5102          operands[] array.  */
5103       if (d->test.pos && d->test.pos_operand < 0)
5104         assign_position_var (os, d->test.pos, false);
5105       for (transition *trans = d->first; trans; trans = trans->next)
5106         assign_position_vars (os, trans->to);
5107     }
5108 }
5109
5110 /* Print the open brace and variable definitions for a routine that
5111    implements S.  ROOT is the deepest rtx from which S can access all
5112    relevant parts of the first instruction it matches.  Initialize OS
5113    so that every relevant position has an rtx variable xN and so that
5114    only ROOT's variable has a valid value.  */
5115
5116 static void
5117 print_subroutine_start (output_state *os, state *s, position *root)
5118 {
5119   printf ("{\n  rtx * const operands ATTRIBUTE_UNUSED"
5120           " = &recog_data.operand[0];\n");
5121   os->var_to_id.truncate (0);
5122   os->seen_vars.truncate (0);
5123   if (root)
5124     {
5125       /* Create a fake entry for position 0 so that an id_to_var of 0
5126          is always invalid.  This also makes the xN variables naturally
5127          1-based rather than 0-based.  */
5128       os->var_to_id.safe_push (num_positions);
5129
5130       /* Associate ROOT with x1.  */
5131       assign_position_var (os, root, true);
5132
5133       /* Assign xN variables to all other relevant positions.  */
5134       assign_position_vars (os, s);
5135
5136       /* Output the variable declarations (except for ROOT's, which is
5137          passed in as a parameter).  */
5138       unsigned int num_vars = os->var_to_id.length ();
5139       if (num_vars > 2)
5140         {
5141           for (unsigned int i = 2; i < num_vars; ++i)
5142             /* Print 8 rtx variables to a line.  */
5143             printf ("%s x%d",
5144                     i == 2 ? "  rtx" : (i - 2) % 8 == 0 ? ";\n  rtx" : ",", i);
5145           printf (";\n");
5146         }
5147
5148       /* Say that x1 is valid and the rest aren't.  */
5149       os->seen_vars.safe_grow_cleared (num_vars, true);
5150       os->seen_vars[1] = true;
5151     }
5152   if (os->type == SUBPATTERN || os->type == RECOG)
5153     printf ("  int res ATTRIBUTE_UNUSED;\n");
5154   else
5155     printf ("  rtx_insn *res ATTRIBUTE_UNUSED;\n");
5156 }
5157
5158 /* Output the definition of pattern routine ROUTINE.  */
5159
5160 static void
5161 print_pattern (output_state *os, pattern_routine *routine)
5162 {
5163   printf ("\nstatic int\npattern%d (", routine->pattern_id);
5164   const char *sep = "";
5165   /* Add the top-level rtx parameter, if any.  */
5166   if (routine->pos)
5167     {
5168       printf ("%srtx x1", sep);
5169       sep = ", ";
5170     }
5171   /* Add the optional parameters.  */
5172   if (routine->insn_p)
5173     {
5174       /* We can't easily tell whether a C condition actually reads INSN,
5175          so add an ATTRIBUTE_UNUSED just in case.  */
5176       printf ("%srtx_insn *insn ATTRIBUTE_UNUSED", sep);
5177       sep = ", ";
5178     }
5179   if (routine->pnum_clobbers_p)
5180     {
5181       printf ("%sint *pnum_clobbers", sep);
5182       sep = ", ";
5183     }
5184   /* Add the "i" parameters.  */
5185   for (unsigned int i = 0; i < routine->param_types.length (); ++i)
5186     {
5187       printf ("%s%s i%d", sep,
5188               parameter_type_string (routine->param_types[i]), i + 1);
5189       sep = ", ";
5190     }
5191   printf (")\n");
5192   os->type = SUBPATTERN;
5193   print_subroutine_start (os, routine->s, routine->pos);
5194   print_state (os, routine->s, 2, true);
5195   printf ("}\n");
5196 }
5197
5198 /* Output a routine of type TYPE that implements S.  PROC_ID is the
5199    number of the subroutine associated with S, or 0 if S is the main
5200    routine.  */
5201
5202 static void
5203 print_subroutine (output_state *os, state *s, int proc_id)
5204 {
5205   printf ("\n");
5206   switch (os->type)
5207     {
5208     case SUBPATTERN:
5209       gcc_unreachable ();
5210
5211     case RECOG:
5212       if (proc_id)
5213         printf ("static int\nrecog_%d", proc_id);
5214       else
5215         printf ("int\nrecog");
5216       printf (" (rtx x1 ATTRIBUTE_UNUSED,\n"
5217               "\trtx_insn *insn ATTRIBUTE_UNUSED,\n"
5218               "\tint *pnum_clobbers ATTRIBUTE_UNUSED)\n");
5219       break;
5220
5221     case SPLIT:
5222       if (proc_id)
5223         printf ("static rtx_insn *\nsplit_%d", proc_id);
5224       else
5225         printf ("rtx_insn *\nsplit_insns");
5226       printf (" (rtx x1 ATTRIBUTE_UNUSED, rtx_insn *insn ATTRIBUTE_UNUSED)\n");
5227       break;
5228
5229     case PEEPHOLE2:
5230       if (proc_id)
5231         printf ("static rtx_insn *\npeephole2_%d", proc_id);
5232       else
5233         printf ("rtx_insn *\npeephole2_insns");
5234       printf (" (rtx x1 ATTRIBUTE_UNUSED,\n"
5235               "\trtx_insn *insn ATTRIBUTE_UNUSED,\n"
5236               "\tint *pmatch_len_ ATTRIBUTE_UNUSED)\n");
5237       break;
5238     }
5239   print_subroutine_start (os, s, &root_pos);
5240   if (proc_id == 0)
5241     {
5242       printf ("  recog_data.insn = NULL;\n");
5243     }
5244   print_state (os, s, 2, true);
5245   printf ("}\n");
5246 }
5247
5248 /* Print out a routine of type TYPE that performs ROOT.  */
5249
5250 static void
5251 print_subroutine_group (output_state *os, routine_type type, state *root)
5252 {
5253   os->type = type;
5254   if (use_subroutines_p)
5255     {
5256       /* Split ROOT up into smaller pieces, both for readability and to
5257          help the compiler.  */
5258       auto_vec <state *> subroutines;
5259       find_subroutines (type, root, subroutines);
5260
5261       /* Output the subroutines (but not ROOT itself).  */
5262       unsigned int i;
5263       state *s;
5264       FOR_EACH_VEC_ELT (subroutines, i, s)
5265         print_subroutine (os, s, i + 1);
5266     }
5267   /* Output the main routine.  */
5268   print_subroutine (os, root, 0);
5269 }
5270
5271 /* Return the rtx pattern for the list of rtxes in a define_peephole2.  */
5272
5273 static rtx
5274 get_peephole2_pattern (md_rtx_info *info)
5275 {
5276   int i, j;
5277   rtvec vec = XVEC (info->def, 0);
5278   rtx pattern = rtx_alloc (SEQUENCE);
5279   XVEC (pattern, 0) = rtvec_alloc (GET_NUM_ELEM (vec));
5280   for (i = j = 0; i < GET_NUM_ELEM (vec); i++)
5281     {
5282       rtx x = RTVEC_ELT (vec, i);
5283       /* Ignore scratch register requirements.  */
5284       if (GET_CODE (x) != MATCH_SCRATCH && GET_CODE (x) != MATCH_DUP)
5285         {
5286           XVECEXP (pattern, 0, j) = x;
5287           j++;
5288         }
5289     }
5290   XVECLEN (pattern, 0) = j;
5291   if (j == 0)
5292     error_at (info->loc, "empty define_peephole2");
5293   return pattern;
5294 }
5295
5296 /* Return true if *PATTERN_PTR is a PARALLEL in which at least one trailing
5297    rtx can be added automatically by add_clobbers.  If so, update
5298    *ACCEPTANCE_PTR so that its num_clobbers field contains the number
5299    of such trailing rtxes and update *PATTERN_PTR so that it contains
5300    the pattern without those rtxes.  */
5301
5302 static bool
5303 remove_clobbers (acceptance_type *acceptance_ptr, rtx *pattern_ptr)
5304 {
5305   int i;
5306   rtx new_pattern;
5307
5308   /* Find the last non-clobber in the parallel.  */
5309   rtx pattern = *pattern_ptr;
5310   for (i = XVECLEN (pattern, 0); i > 0; i--)
5311     {
5312       rtx x = XVECEXP (pattern, 0, i - 1);
5313       if (GET_CODE (x) != CLOBBER
5314           || (!REG_P (XEXP (x, 0))
5315               && GET_CODE (XEXP (x, 0)) != MATCH_SCRATCH))
5316         break;
5317     }
5318
5319   if (i == XVECLEN (pattern, 0))
5320     return false;
5321
5322   /* Build a similar insn without the clobbers.  */
5323   if (i == 1)
5324     new_pattern = XVECEXP (pattern, 0, 0);
5325   else
5326     {
5327       new_pattern = rtx_alloc (PARALLEL);
5328       XVEC (new_pattern, 0) = rtvec_alloc (i);
5329       for (int j = 0; j < i; ++j)
5330         XVECEXP (new_pattern, 0, j) = XVECEXP (pattern, 0, j);
5331     }
5332
5333   /* Recognize it.  */
5334   acceptance_ptr->u.full.u.num_clobbers = XVECLEN (pattern, 0) - i;
5335   *pattern_ptr = new_pattern;
5336   return true;
5337 }
5338
5339 int
5340 main (int argc, const char **argv)
5341 {
5342   state insn_root, split_root, peephole2_root;
5343
5344   progname = "genrecog";
5345
5346   if (!init_rtx_reader_args (argc, argv))
5347     return (FATAL_EXIT_CODE);
5348
5349   write_header ();
5350
5351   /* Read the machine description.  */
5352
5353   md_rtx_info info;
5354   while (read_md_rtx (&info))
5355     {
5356       rtx def = info.def;
5357
5358       acceptance_type acceptance;
5359       acceptance.partial_p = false;
5360       acceptance.u.full.code = info.index;
5361
5362       rtx pattern;
5363       switch (GET_CODE (def))
5364         {
5365         case DEFINE_INSN:
5366           {
5367             /* Match the instruction in the original .md form.  */
5368             acceptance.type = RECOG;
5369             acceptance.u.full.u.num_clobbers = 0;
5370             pattern = add_implicit_parallel (XVEC (def, 1));
5371             validate_pattern (pattern, &info, NULL_RTX, 0);
5372             match_pattern (&insn_root, &info, pattern, acceptance);
5373
5374             /* If the pattern is a PARALLEL with trailing CLOBBERs,
5375                allow recog_for_combine to match without the clobbers.  */
5376             if (GET_CODE (pattern) == PARALLEL
5377                 && remove_clobbers (&acceptance, &pattern))
5378               match_pattern (&insn_root, &info, pattern, acceptance);
5379             break;
5380           }
5381
5382         case DEFINE_SPLIT:
5383           acceptance.type = SPLIT;
5384           pattern = add_implicit_parallel (XVEC (def, 0));
5385           validate_pattern (pattern, &info, NULL_RTX, 0);
5386           match_pattern (&split_root, &info, pattern, acceptance);
5387
5388           /* Declare the gen_split routine that we'll call if the
5389              pattern matches.  The definition comes from insn-emit.cc.  */
5390           printf ("extern rtx_insn *gen_split_%d (rtx_insn *, rtx *);\n",
5391                   info.index);
5392           break;
5393
5394         case DEFINE_PEEPHOLE2:
5395           acceptance.type = PEEPHOLE2;
5396           pattern = get_peephole2_pattern (&info);
5397           validate_pattern (pattern, &info, NULL_RTX, 0);
5398           match_pattern (&peephole2_root, &info, pattern, acceptance);
5399
5400           /* Declare the gen_peephole2 routine that we'll call if the
5401              pattern matches.  The definition comes from insn-emit.cc.  */
5402           printf ("extern rtx_insn *gen_peephole2_%d (rtx_insn *, rtx *);\n",
5403                   info.index);
5404           break;
5405
5406         default:
5407           /* do nothing */;
5408         }
5409     }
5410
5411   if (have_error)
5412     return FATAL_EXIT_CODE;
5413
5414   puts ("\n\n");
5415
5416   /* Optimize each routine in turn.  */
5417   optimize_subroutine_group ("recog", &insn_root);
5418   optimize_subroutine_group ("split_insns", &split_root);
5419   optimize_subroutine_group ("peephole2_insns", &peephole2_root);
5420
5421   output_state os;
5422   os.id_to_var.safe_grow_cleared (num_positions, true);
5423
5424   if (use_pattern_routines_p)
5425     {
5426       /* Look for common patterns and split them out into subroutines.  */
5427       auto_vec <merge_state_info> states;
5428       states.safe_push (&insn_root);
5429       states.safe_push (&split_root);
5430       states.safe_push (&peephole2_root);
5431       split_out_patterns (states);
5432
5433       /* Print out the routines that we just created.  */
5434       unsigned int i;
5435       pattern_routine *routine;
5436       FOR_EACH_VEC_ELT (patterns, i, routine)
5437         print_pattern (&os, routine);
5438     }
5439
5440   /* Print out the matching routines.  */
5441   print_subroutine_group (&os, RECOG, &insn_root);
5442   print_subroutine_group (&os, SPLIT, &split_root);
5443   print_subroutine_group (&os, PEEPHOLE2, &peephole2_root);
5444
5445   fflush (stdout);
5446   return (ferror (stdout) != 0 ? FATAL_EXIT_CODE : SUCCESS_EXIT_CODE);
5447 }