gcc/genrecog.c

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