gcc/genrecog.c

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