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 the DEFINE_PEEPHOLE2 itself, otherwise
4084    it is the rtx pattern to match (PARALLEL, SET, etc.).  */
4085
4086 static void
4087 match_pattern_1 (state *s, rtx top_pattern, const char *c_test,
4088                  acceptance_type acceptance)
4089 {
4090   if (GET_CODE (top_pattern) == DEFINE_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           /* Ignore scratch register requirements.  */
4099           if (GET_CODE (x) != MATCH_SCRATCH && GET_CODE (x) != MATCH_DUP)
4100             {
4101               position *subpos = next_position (subpos_ptr, &root_pos,
4102                                                 POS_PEEP2_INSN, count);
4103               if (count > 0)
4104                 s = add_decision (s, rtx_test::peep2_count (count + 1),
4105                                   true, false);
4106               s = match_pattern_2 (s, top_pattern, subpos, x);
4107               subpos_ptr = &subpos->next;
4108               count += 1;
4109             }
4110         }
4111       acceptance.u.full.u.match_len = count - 1;
4112     }
4113   else
4114     {
4115       /* Make the rtx itself.  */
4116       s = match_pattern_2 (s, top_pattern, &root_pos, top_pattern);
4117
4118       /* If the match is only valid when extra clobbers are added,
4119          make sure we're able to pass that information to the caller.  */
4120       if (acceptance.type == RECOG && acceptance.u.full.u.num_clobbers)
4121         s = add_decision (s, rtx_test::have_num_clobbers (), true, false);
4122     }
4123
4124   /* Make sure that the C test is true.  */
4125   if (maybe_eval_c_test (c_test) != 1)
4126     s = add_decision (s, rtx_test::c_test (c_test), true, false);
4127
4128   /* Accept the pattern.  */
4129   add_decision (s, rtx_test::accept (acceptance), true, false);
4130 }
4131
4132 /* Like match_pattern_1, but (if merge_states_p) try to merge the
4133    decisions with what's already in S, to reduce the amount of
4134    backtracking.  */
4135
4136 static void
4137 match_pattern (state *s, rtx top_pattern, const char *c_test,
4138                acceptance_type acceptance)
4139 {
4140   if (merge_states_p)
4141     {
4142       state root;
4143       /* Add the decisions to a fresh state and then merge the full tree
4144          into the existing one.  */
4145       match_pattern_1 (&root, top_pattern, c_test, acceptance);
4146       merge_into_state (s, &root);
4147     }
4148   else
4149     match_pattern_1 (s, top_pattern, c_test, acceptance);
4150 }
4151
4152 /* Begin the output file.  */
4153
4154 static void
4155 write_header (void)
4156 {
4157   puts ("\
4158 /* Generated automatically by the program `genrecog' from the target\n\
4159    machine description file.  */\n\
4160 \n\
4161 #include \"config.h\"\n\
4162 #include \"system.h\"\n\
4163 #include \"coretypes.h\"\n\
4164 #include \"tm.h\"\n\
4165 #include \"rtl.h\"\n\
4166 #include \"tm_p.h\"\n\
4167 #include \"hashtab.h\"\n\
4168 #include \"hash-set.h\"\n\
4169 #include \"vec.h\"\n\
4170 #include \"machmode.h\"\n\
4171 #include \"hard-reg-set.h\"\n\
4172 #include \"input.h\"\n\
4173 #include \"function.h\"\n\
4174 #include \"insn-config.h\"\n\
4175 #include \"recog.h\"\n\
4176 #include \"output.h\"\n\
4177 #include \"flags.h\"\n\
4178 #include \"hard-reg-set.h\"\n\
4179 #include \"predict.h\"\n\
4180 #include \"basic-block.h\"\n\
4181 #include \"resource.h\"\n\
4182 #include \"diagnostic-core.h\"\n\
4183 #include \"reload.h\"\n\
4184 #include \"regs.h\"\n\
4185 #include \"tm-constrs.h\"\n\
4186 #include \"predict.h\"\n\
4187 \n");
4188
4189   puts ("\n\
4190 /* `recog' contains a decision tree that recognizes whether the rtx\n\
4191    X0 is a valid instruction.\n\
4192 \n\
4193    recog returns -1 if the rtx is not valid.  If the rtx is valid, recog\n\
4194    returns a nonnegative number which is the insn code number for the\n\
4195    pattern that matched.  This is the same as the order in the machine\n\
4196    description of the entry that matched.  This number can be used as an\n\
4197    index into `insn_data' and other tables.\n");
4198   puts ("\
4199    The third parameter to recog is an optional pointer to an int.  If\n\
4200    present, recog will accept a pattern if it matches except for missing\n\
4201    CLOBBER expressions at the end.  In that case, the value pointed to by\n\
4202    the optional pointer will be set to the number of CLOBBERs that need\n\
4203    to be added (it should be initialized to zero by the caller).  If it");
4204   puts ("\
4205    is set nonzero, the caller should allocate a PARALLEL of the\n\
4206    appropriate size, copy the initial entries, and call add_clobbers\n\
4207    (found in insn-emit.c) to fill in the CLOBBERs.\n\
4208 ");
4209
4210   puts ("\n\
4211    The function split_insns returns 0 if the rtl could not\n\
4212    be split or the split rtl as an INSN list if it can be.\n\
4213 \n\
4214    The function peephole2_insns returns 0 if the rtl could not\n\
4215    be matched. If there was a match, the new rtl is returned in an INSN list,\n\
4216    and LAST_INSN will point to the last recognized insn in the old sequence.\n\
4217 */\n\n");
4218 }
4219
4220 /* Return the C type of a parameter with type TYPE.  */
4221
4222 static const char *
4223 parameter_type_string (parameter::type_enum type)
4224 {
4225   switch (type)
4226     {
4227     case parameter::UNSET:
4228       break;
4229
4230     case parameter::CODE:
4231       return "rtx_code";
4232
4233     case parameter::MODE:
4234       return "machine_mode";
4235
4236     case parameter::INT:
4237       return "int";
4238
4239     case parameter::WIDE_INT:
4240       return "HOST_WIDE_INT";
4241     }
4242   gcc_unreachable ();
4243 }
4244
4245 /* Return true if ACCEPTANCE requires only a single C statement even in
4246    a backtracking context.  */
4247
4248 static bool
4249 single_statement_p (const acceptance_type &acceptance)
4250 {
4251   if (acceptance.partial_p)
4252     /* We need to handle failures of the subroutine.  */
4253     return false;
4254   switch (acceptance.type)
4255     {
4256     case SUBPATTERN:
4257     case SPLIT:
4258       return true;
4259
4260     case RECOG:
4261       /* False if we need to assign to pnum_clobbers.  */
4262       return acceptance.u.full.u.num_clobbers == 0;
4263
4264     case PEEPHOLE2:
4265       /* We need to assign to pmatch_len_ and handle null returns from the
4266          peephole2 routine.  */
4267       return false;
4268     }
4269   gcc_unreachable ();
4270 }
4271
4272 /* Return the C failure value for a routine of type TYPE.  */
4273
4274 static const char *
4275 get_failure_return (routine_type type)
4276 {
4277   switch (type)
4278     {
4279     case SUBPATTERN:
4280     case RECOG:
4281       return "-1";
4282
4283     case SPLIT:
4284     case PEEPHOLE2:
4285       return "NULL_RTX";
4286     }
4287   gcc_unreachable ();
4288 }
4289
4290 /* Indicates whether a block of code always returns or whether it can fall
4291    through.  */
4292
4293 enum exit_state {
4294   ES_RETURNED,
4295   ES_FALLTHROUGH
4296 };
4297
4298 /* Information used while writing out code.  */
4299
4300 struct output_state
4301 {
4302   /* The type of routine that we're generating.  */
4303   routine_type type;
4304
4305   /* Maps position ids to xN variable numbers.  The entry is only valid if
4306      it is less than the length of VAR_TO_ID, but this holds for every position
4307      tested by a state when writing out that state.  */
4308   auto_vec <unsigned int> id_to_var;
4309
4310   /* Maps xN variable numbers to position ids.  */
4311   auto_vec <unsigned int> var_to_id;
4312
4313   /* Index N is true if variable xN has already been set.  */
4314   auto_vec <bool> seen_vars;
4315 };
4316
4317 /* Return true if D is a call to a pattern routine and if there is some X
4318    such that the transition for pattern result N goes to a successful return
4319    with code X+N.  When returning true, set *BASE_OUT to this X and *COUNT_OUT
4320    to the number of return values.  (We know that every PATTERN decision has
4321    a transition for every successful return.)  */
4322
4323 static bool
4324 terminal_pattern_p (decision *d, unsigned int *base_out,
4325                     unsigned int *count_out)
4326 {
4327   if (d->test.kind != rtx_test::PATTERN)
4328     return false;
4329   unsigned int base = 0;
4330   unsigned int count = 0;
4331   for (transition *trans = d->first; trans; trans = trans->next)
4332     {
4333       if (trans->is_param || trans->labels.length () != 1)
4334         return false;
4335       decision *subd = trans->to->singleton ();
4336       if (!subd || subd->test.kind != rtx_test::ACCEPT)
4337         return false;
4338       unsigned int this_base = (subd->test.u.acceptance.u.full.code
4339                                 - trans->labels[0]);
4340       if (trans == d->first)
4341         base = this_base;
4342       else if (base != this_base)
4343         return false;
4344       count += 1;
4345     }
4346   *base_out = base;
4347   *count_out = count;
4348   return true;
4349 }
4350
4351 /* Return true if TEST doesn't test an rtx or if the rtx it tests is
4352    already available in state OS.  */
4353
4354 static bool
4355 test_position_available_p (output_state *os, const rtx_test &test)
4356 {
4357   return (!test.pos
4358           || test.pos_operand >= 0
4359           || os->seen_vars[os->id_to_var[test.pos->id]]);
4360 }
4361
4362 /* Like printf, but print INDENT spaces at the beginning.  */
4363
4364 static void ATTRIBUTE_PRINTF_2
4365 printf_indent (unsigned int indent, const char *format, ...)
4366 {
4367   va_list ap;
4368   va_start (ap, format);
4369   printf ("%*s", indent, "");
4370   vprintf (format, ap);
4371   va_end (ap);
4372 }
4373
4374 /* Emit code to initialize the variable associated with POS, if it isn't
4375    already valid in state OS.  Indent each line by INDENT spaces.  Update
4376    OS with the new state.  */
4377
4378 static void
4379 change_state (output_state *os, position *pos, unsigned int indent)
4380 {
4381   unsigned int var = os->id_to_var[pos->id];
4382   gcc_assert (var < os->var_to_id.length () && os->var_to_id[var] == pos->id);
4383   if (os->seen_vars[var])
4384     return;
4385   switch (pos->type)
4386     {
4387     case POS_PEEP2_INSN:
4388       printf_indent (indent, "x%d = PATTERN (peep2_next_insn (%d));\n",
4389                      var, pos->arg);
4390       break;
4391
4392     case POS_XEXP:
4393       change_state (os, pos->base, indent);
4394       printf_indent (indent, "x%d = XEXP (x%d, %d);\n",
4395                      var, os->id_to_var[pos->base->id], pos->arg);
4396       break;
4397
4398     case POS_XVECEXP0:
4399       change_state (os, pos->base, indent);
4400       printf_indent (indent, "x%d = XVECEXP (x%d, 0, %d);\n",
4401                      var, os->id_to_var[pos->base->id], pos->arg);
4402       break;
4403     }
4404   os->seen_vars[var] = true;
4405 }
4406
4407 /* Print the enumerator constant for CODE -- the upcase version of
4408    the name.  */
4409
4410 static void
4411 print_code (enum rtx_code code)
4412 {
4413   const char *p;
4414   for (p = GET_RTX_NAME (code); *p; p++)
4415     putchar (TOUPPER (*p));
4416 }
4417
4418 /* Emit a uint64_t as an integer constant expression.  We need to take
4419    special care to avoid "decimal constant is so large that it is unsigned"
4420    warnings in the resulting code.  */
4421
4422 static void
4423 print_host_wide_int (uint64_t val)
4424 {
4425   uint64_t min = uint64_t (1) << (HOST_BITS_PER_WIDE_INT - 1);
4426   if (val == min)
4427     printf ("(" HOST_WIDE_INT_PRINT_DEC_C " - 1)", val + 1);
4428   else
4429     printf (HOST_WIDE_INT_PRINT_DEC_C, val);
4430 }
4431
4432 /* Print the C expression for actual parameter PARAM.  */
4433
4434 static void
4435 print_parameter_value (const parameter &param)
4436 {
4437   if (param.is_param)
4438     printf ("i%d", (int) param.value + 1);
4439   else
4440     switch (param.type)
4441       {
4442       case parameter::UNSET:
4443         gcc_unreachable ();
4444         break;
4445
4446       case parameter::CODE:
4447         print_code ((enum rtx_code) param.value);
4448         break;
4449
4450       case parameter::MODE:
4451         printf ("%smode", GET_MODE_NAME ((machine_mode) param.value));
4452         break;
4453
4454       case parameter::INT:
4455         printf ("%d", (int) param.value);
4456         break;
4457
4458       case parameter::WIDE_INT:
4459         print_host_wide_int (param.value);
4460         break;
4461       }
4462 }
4463
4464 /* Print the C expression for the rtx tested by TEST.  */
4465
4466 static void
4467 print_test_rtx (output_state *os, const rtx_test &test)
4468 {
4469   if (test.pos_operand >= 0)
4470     printf ("operands[%d]", test.pos_operand);
4471   else
4472     printf ("x%d", os->id_to_var[test.pos->id]);
4473 }
4474
4475 /* Print the C expression for non-boolean test TEST.  */
4476
4477 static void
4478 print_nonbool_test (output_state *os, const rtx_test &test)
4479 {
4480   switch (test.kind)
4481     {
4482     case rtx_test::CODE:
4483       printf ("GET_CODE (");
4484       print_test_rtx (os, test);
4485       printf (")");
4486       break;
4487
4488     case rtx_test::MODE:
4489       printf ("GET_MODE (");
4490       print_test_rtx (os, test);
4491       printf (")");
4492       break;
4493
4494     case rtx_test::VECLEN:
4495       printf ("XVECLEN (");
4496       print_test_rtx (os, test);
4497       printf (", 0)");
4498       break;
4499
4500     case rtx_test::INT_FIELD:
4501       printf ("XINT (");
4502       print_test_rtx (os, test);
4503       printf (", %d)", test.u.opno);
4504       break;
4505
4506     case rtx_test::WIDE_INT_FIELD:
4507       printf ("XWINT (");
4508       print_test_rtx (os, test);
4509       printf (", %d)", test.u.opno);
4510       break;
4511
4512     case rtx_test::PATTERN:
4513       {
4514         pattern_routine *routine = test.u.pattern->routine;
4515         printf ("pattern%d (", routine->pattern_id);
4516         const char *sep = "";
4517         if (test.pos)
4518           {
4519             print_test_rtx (os, test);
4520             sep = ", ";
4521           }
4522         if (routine->insn_p)
4523           {
4524             printf ("%sinsn", sep);
4525             sep = ", ";
4526           }
4527         if (routine->pnum_clobbers_p)
4528           {
4529             printf ("%spnum_clobbers", sep);
4530             sep = ", ";
4531           }
4532         for (unsigned int i = 0; i < test.u.pattern->params.length (); ++i)
4533           {
4534             fputs (sep, stdout);
4535             print_parameter_value (test.u.pattern->params[i]);
4536             sep = ", ";
4537           }
4538         printf (")");
4539         break;
4540       }
4541
4542     case rtx_test::PEEP2_COUNT:
4543     case rtx_test::VECLEN_GE:
4544     case rtx_test::SAVED_CONST_INT:
4545     case rtx_test::DUPLICATE:
4546     case rtx_test::PREDICATE:
4547     case rtx_test::SET_OP:
4548     case rtx_test::HAVE_NUM_CLOBBERS:
4549     case rtx_test::C_TEST:
4550     case rtx_test::ACCEPT:
4551       gcc_unreachable ();
4552     }
4553 }
4554
4555 /* IS_PARAM and LABEL are taken from a transition whose source
4556    decision performs TEST.  Print the C code for the label.  */
4557
4558 static void
4559 print_label_value (const rtx_test &test, bool is_param, uint64_t value)
4560 {
4561   print_parameter_value (parameter (transition_parameter_type (test.kind),
4562                                     is_param, value));
4563 }
4564
4565 /* If IS_PARAM, print code to compare TEST with the C variable i<VALUE+1>.
4566    If !IS_PARAM, print code to compare TEST with the C constant VALUE.
4567    Test for inequality if INVERT_P, otherwise test for equality.  */
4568
4569 static void
4570 print_test (output_state *os, const rtx_test &test, bool is_param,
4571             uint64_t value, bool invert_p)
4572 {
4573   switch (test.kind)
4574     {
4575       /* Handle the non-boolean TESTs.  */
4576     case rtx_test::CODE:
4577     case rtx_test::MODE:
4578     case rtx_test::VECLEN:
4579     case rtx_test::INT_FIELD:
4580     case rtx_test::WIDE_INT_FIELD:
4581     case rtx_test::PATTERN:
4582       print_nonbool_test (os, test);
4583       printf (" %s ", invert_p ? "!=" : "==");
4584       print_label_value (test, is_param, value);
4585       break;
4586
4587     case rtx_test::SAVED_CONST_INT:
4588       gcc_assert (!is_param && value == 1);
4589       print_test_rtx (os, test);
4590       printf (" %s const_int_rtx[MAX_SAVED_CONST_INT + ",
4591               invert_p ? "!=" : "==");
4592       print_parameter_value (parameter (parameter::INT,
4593                                         test.u.integer.is_param,
4594                                         test.u.integer.value));
4595       printf ("]");
4596       break;
4597
4598     case rtx_test::PEEP2_COUNT:
4599       gcc_assert (!is_param && value == 1);
4600       printf ("peep2_current_count %s %d", invert_p ? "<" : ">=",
4601               test.u.min_len);
4602       break;
4603
4604     case rtx_test::VECLEN_GE:
4605       gcc_assert (!is_param && value == 1);
4606       printf ("XVECLEN (");
4607       print_test_rtx (os, test);
4608       printf (", 0) %s %d", invert_p ? "<" : ">=", test.u.min_len);
4609       break;
4610
4611     case rtx_test::PREDICATE:
4612       gcc_assert (!is_param && value == 1);
4613       printf ("%s%s (", invert_p ? "!" : "", test.u.predicate.data->name);
4614       print_test_rtx (os, test);
4615       printf (", ");
4616       print_parameter_value (parameter (parameter::MODE,
4617                                         test.u.predicate.mode_is_param,
4618                                         test.u.predicate.mode));
4619       printf (")");
4620       break;
4621
4622     case rtx_test::DUPLICATE:
4623       gcc_assert (!is_param && value == 1);
4624       printf ("%srtx_equal_p (", invert_p ? "!" : "");
4625       print_test_rtx (os, test);
4626       printf (", operands[%d])", test.u.opno);
4627       break;
4628
4629     case rtx_test::HAVE_NUM_CLOBBERS:
4630       gcc_assert (!is_param && value == 1);
4631       printf ("pnum_clobbers %s NULL", invert_p ? "==" : "!=");
4632       break;
4633
4634     case rtx_test::C_TEST:
4635       gcc_assert (!is_param && value == 1);
4636       if (invert_p)
4637         printf ("!");
4638       print_c_condition (test.u.string);
4639       break;
4640
4641     case rtx_test::ACCEPT:
4642     case rtx_test::SET_OP:
4643       gcc_unreachable ();
4644     }
4645 }
4646
4647 static exit_state print_decision (output_state *, decision *,
4648                                   unsigned int, bool);
4649
4650 /* Print code to perform S, indent each line by INDENT spaces.
4651    IS_FINAL is true if there are no fallback decisions to test on failure;
4652    if the state fails then the entire routine fails.  */
4653
4654 static exit_state
4655 print_state (output_state *os, state *s, unsigned int indent, bool is_final)
4656 {
4657   exit_state es = ES_FALLTHROUGH;
4658   for (decision *d = s->first; d; d = d->next)
4659     es = print_decision (os, d, indent, is_final && !d->next);
4660   if (es != ES_RETURNED && is_final)
4661     {
4662       printf_indent (indent, "return %s;\n", get_failure_return (os->type));
4663       es = ES_RETURNED;
4664     }
4665   return es;
4666 }
4667
4668 /* Print the code for subroutine call ACCEPTANCE (for which partial_p
4669    is known to be true).  Return the C condition that indicates a successful
4670    match.  */
4671
4672 static const char *
4673 print_subroutine_call (const acceptance_type &acceptance)
4674 {
4675   switch (acceptance.type)
4676     {
4677     case SUBPATTERN:
4678       gcc_unreachable ();
4679
4680     case RECOG:
4681       printf ("recog_%d (x1, insn, pnum_clobbers)",
4682               acceptance.u.subroutine_id);
4683       return ">= 0";
4684
4685     case SPLIT:
4686       printf ("split_%d (x1, insn)", acceptance.u.subroutine_id);
4687       return "!= NULL_RTX";
4688
4689     case PEEPHOLE2:
4690       printf ("peephole2_%d (x1, insn, pmatch_len_)",
4691               acceptance.u.subroutine_id);
4692       return "!= NULL_RTX";
4693     }
4694   gcc_unreachable ();
4695 }
4696
4697 /* Print code for the successful match described by ACCEPTANCE.
4698    INDENT and IS_FINAL are as for print_state.  */
4699
4700 static exit_state
4701 print_acceptance (const acceptance_type &acceptance, unsigned int indent,
4702                   bool is_final)
4703 {
4704   if (acceptance.partial_p)
4705     {
4706       /* Defer the rest of the match to a subroutine.  */
4707       if (is_final)
4708         {
4709           printf_indent (indent, "return ");
4710           print_subroutine_call (acceptance);
4711           printf (";\n");
4712           return ES_RETURNED;
4713         }
4714       else
4715         {
4716           printf_indent (indent, "res = ");
4717           const char *res_test = print_subroutine_call (acceptance);
4718           printf (";\n");
4719           printf_indent (indent, "if (res %s)\n", res_test);
4720           printf_indent (indent + 2, "return res;\n");
4721           return ES_FALLTHROUGH;
4722         }
4723     }
4724   switch (acceptance.type)
4725     {
4726     case SUBPATTERN:
4727       printf_indent (indent, "return %d;\n", acceptance.u.full.code);
4728       return ES_RETURNED;
4729
4730     case RECOG:
4731       if (acceptance.u.full.u.num_clobbers != 0)
4732         printf_indent (indent, "*pnum_clobbers = %d;\n",
4733                        acceptance.u.full.u.num_clobbers);
4734       printf_indent (indent, "return %d; /* %s */\n", acceptance.u.full.code,
4735                      get_insn_name (acceptance.u.full.code));
4736       return ES_RETURNED;
4737
4738     case SPLIT:
4739       printf_indent (indent, "return gen_split_%d (insn, operands);\n",
4740                      acceptance.u.full.code);
4741       return ES_RETURNED;
4742
4743     case PEEPHOLE2:
4744       printf_indent (indent, "*pmatch_len_ = %d;\n",
4745                      acceptance.u.full.u.match_len);
4746       if (is_final)
4747         {
4748           printf_indent (indent, "return gen_peephole2_%d (insn, operands);\n",
4749                          acceptance.u.full.code);
4750           return ES_RETURNED;
4751         }
4752       else
4753         {
4754           printf_indent (indent, "res = gen_peephole2_%d (insn, operands);\n",
4755                          acceptance.u.full.code);
4756           printf_indent (indent, "if (res != NULL_RTX)\n");
4757           printf_indent (indent + 2, "return res;\n");
4758           return ES_FALLTHROUGH;
4759         }
4760     }
4761   gcc_unreachable ();
4762 }
4763
4764 /* Print code to perform D.  INDENT and IS_FINAL are as for print_state.  */
4765
4766 static exit_state
4767 print_decision (output_state *os, decision *d, unsigned int indent,
4768                 bool is_final)
4769 {
4770   uint64_t label;
4771   unsigned int base, count;
4772
4773   /* Make sure the rtx under test is available either in operands[] or
4774      in an xN variable.  */
4775   if (d->test.pos && d->test.pos_operand < 0)
4776     change_state (os, d->test.pos, indent);
4777
4778   /* Look for cases where a pattern routine P1 calls another pattern routine
4779      P2 and where P1 returns X + BASE whenever P2 returns X.  If IS_FINAL
4780      is true and BASE is zero we can simply use:
4781
4782         return patternN (...);
4783
4784      Otherwise we can use:
4785
4786         res = patternN (...);
4787         if (res >= 0)
4788           return res + BASE;
4789
4790      However, if BASE is nonzero and patternN only returns 0 or -1,
4791      the usual "return BASE;" is better than "return res + BASE;".
4792      If BASE is zero, "return res;" should be better than "return 0;",
4793      since no assignment to the return register is required.  */
4794   if (os->type == SUBPATTERN
4795       && terminal_pattern_p (d, &base, &count)
4796       && (base == 0 || count > 1))
4797     {
4798       if (is_final && base == 0)
4799         {
4800           printf_indent (indent, "return ");
4801           print_nonbool_test (os, d->test);
4802           printf ("; /* [-1, %d] */\n", count - 1);
4803           return ES_RETURNED;
4804         }
4805       else
4806         {
4807           printf_indent (indent, "res = ");
4808           print_nonbool_test (os, d->test);
4809           printf (";\n");
4810           printf_indent (indent, "if (res >= 0)\n");
4811           printf_indent (indent + 2, "return res");
4812           if (base != 0)
4813             printf (" + %d", base);
4814           printf ("; /* [%d, %d] */\n", base, base + count - 1);
4815           return ES_FALLTHROUGH;
4816         }
4817     }
4818   else if (d->test.kind == rtx_test::ACCEPT)
4819     return print_acceptance (d->test.u.acceptance, indent, is_final);
4820   else if (d->test.kind == rtx_test::SET_OP)
4821     {
4822       printf_indent (indent, "operands[%d] = ", d->test.u.opno);
4823       print_test_rtx (os, d->test);
4824       printf (";\n");
4825       return print_state (os, d->singleton ()->to, indent, is_final);
4826     }
4827   /* Handle decisions with a single transition and a single transition
4828      label.  */
4829   else if (d->if_statement_p (&label))
4830     {
4831       transition *trans = d->singleton ();
4832       if (mark_optional_transitions_p && trans->optional)
4833         printf_indent (indent, "/* OPTIONAL IF */\n");
4834
4835       /* Print the condition associated with TRANS.  Invert it if IS_FINAL,
4836          so that we return immediately on failure and fall through on
4837          success.  */
4838       printf_indent (indent, "if (");
4839       print_test (os, d->test, trans->is_param, label, is_final);
4840
4841       /* Look for following states that would be handled by this code
4842          on recursion.  If they don't need any preparatory statements,
4843          include them in the current "if" statement rather than creating
4844          a new one.  */
4845       for (;;)
4846         {
4847           d = trans->to->singleton ();
4848           if (!d
4849               || d->test.kind == rtx_test::ACCEPT
4850               || d->test.kind == rtx_test::SET_OP
4851               || !d->if_statement_p (&label)
4852               || !test_position_available_p (os, d->test))
4853             break;
4854           trans = d->first;
4855           printf ("\n");
4856           if (mark_optional_transitions_p && trans->optional)
4857             printf_indent (indent + 4, "/* OPTIONAL IF */\n");
4858           printf_indent (indent + 4, "%s ", is_final ? "||" : "&&");
4859           print_test (os, d->test, trans->is_param, label, is_final);
4860         }
4861       printf (")\n");
4862
4863       /* Print the conditional code with INDENT + 2 and the fallthrough
4864          code with indent INDENT.  */
4865       state *to = trans->to;
4866       if (is_final)
4867         {
4868           /* We inverted the condition above, so return failure in the
4869              "if" body and fall through to the target of the transition.  */
4870           printf_indent (indent + 2, "return %s;\n",
4871                          get_failure_return (os->type));
4872           return print_state (os, to, indent, is_final);
4873         }
4874       else if (to->singleton ()
4875                && to->first->test.kind == rtx_test::ACCEPT
4876                && single_statement_p (to->first->test.u.acceptance))
4877         {
4878           /* The target of the transition is a simple "return" statement.
4879              It doesn't need any braces and doesn't fall through.  */
4880           if (print_acceptance (to->first->test.u.acceptance,
4881                                 indent + 2, true) != ES_RETURNED)
4882             gcc_unreachable ();
4883           return ES_FALLTHROUGH;
4884         }
4885       else
4886         {
4887           /* The general case.  Output code for the target of the transition
4888              in braces.  This will not invalidate any of the xN variables
4889              that are already valid, but we mustn't rely on any that are
4890              set by the "if" body.  */
4891           auto_vec <bool, 32> old_seen;
4892           old_seen.safe_splice (os->seen_vars);
4893
4894           printf_indent (indent + 2, "{\n");
4895           print_state (os, trans->to, indent + 4, is_final);
4896           printf_indent (indent + 2, "}\n");
4897
4898           os->seen_vars.truncate (0);
4899           os->seen_vars.splice (old_seen);
4900           return ES_FALLTHROUGH;
4901         }
4902     }
4903   else
4904     {
4905       /* Output the decision as a switch statement.  */
4906       printf_indent (indent, "switch (");
4907       print_nonbool_test (os, d->test);
4908       printf (")\n");
4909
4910       /* Each case statement starts with the same set of valid variables.
4911          These are also the only variables will be valid on fallthrough.  */
4912       auto_vec <bool, 32> old_seen;
4913       old_seen.safe_splice (os->seen_vars);
4914
4915       printf_indent (indent + 2, "{\n");
4916       for (transition *trans = d->first; trans; trans = trans->next)
4917         {
4918           gcc_assert (!trans->is_param);
4919           if (mark_optional_transitions_p && trans->optional)
4920             printf_indent (indent + 2, "/* OPTIONAL CASE */\n");
4921           for (int_set::iterator j = trans->labels.begin ();
4922                j != trans->labels.end (); ++j)
4923             {
4924               printf_indent (indent + 2, "case ");
4925               print_label_value (d->test, trans->is_param, *j);
4926               printf (":\n");
4927             }
4928           if (print_state (os, trans->to, indent + 4, is_final))
4929             {
4930               /* The state can fall through.  Add an explicit break.  */
4931               gcc_assert (!is_final);
4932               printf_indent (indent + 4, "break;\n");
4933             }
4934           printf ("\n");
4935
4936           /* Restore the original set of valid variables.  */
4937           os->seen_vars.truncate (0);
4938           os->seen_vars.splice (old_seen);
4939         }
4940       /* Add a default case.  */
4941       printf_indent (indent + 2, "default:\n");
4942       if (is_final)
4943         printf_indent (indent + 4, "return %s;\n",
4944                        get_failure_return (os->type));
4945       else
4946         printf_indent (indent + 4, "break;\n");
4947       printf_indent (indent + 2, "}\n");
4948       return is_final ? ES_RETURNED : ES_FALLTHROUGH;
4949     }
4950 }
4951
4952 /* Make sure that OS has a position variable for POS.  ROOT_P is true if
4953    POS is the root position for the routine.  */
4954
4955 static void
4956 assign_position_var (output_state *os, position *pos, bool root_p)
4957 {
4958   unsigned int idx = os->id_to_var[pos->id];
4959   if (idx < os->var_to_id.length () && os->var_to_id[idx] == pos->id)
4960     return;
4961   if (!root_p && pos->type != POS_PEEP2_INSN)
4962     assign_position_var (os, pos->base, false);
4963   os->id_to_var[pos->id] = os->var_to_id.length ();
4964   os->var_to_id.safe_push (pos->id);
4965 }
4966
4967 /* Make sure that OS has the position variables required by S.  */
4968
4969 static void
4970 assign_position_vars (output_state *os, state *s)
4971 {
4972   for (decision *d = s->first; d; d = d->next)
4973     {
4974       /* Positions associated with operands can be read from the
4975          operands[] array.  */
4976       if (d->test.pos && d->test.pos_operand < 0)
4977         assign_position_var (os, d->test.pos, false);
4978       for (transition *trans = d->first; trans; trans = trans->next)
4979         assign_position_vars (os, trans->to);
4980     }
4981 }
4982
4983 /* Print the open brace and variable definitions for a routine that
4984    implements S.  ROOT is the deepest rtx from which S can access all
4985    relevant parts of the first instruction it matches.  Initialize OS
4986    so that every relevant position has an rtx variable xN and so that
4987    only ROOT's variable has a valid value.  */
4988
4989 static void
4990 print_subroutine_start (output_state *os, state *s, position *root)
4991 {
4992   printf ("{\n  rtx * const operands ATTRIBUTE_UNUSED"
4993           " = &recog_data.operand[0];\n");
4994   os->var_to_id.truncate (0);
4995   os->seen_vars.truncate (0);
4996   if (root)
4997     {
4998       /* Create a fake entry for position 0 so that an id_to_var of 0
4999          is always invalid.  This also makes the xN variables naturally
5000          1-based rather than 0-based.  */
5001       os->var_to_id.safe_push (num_positions);
5002
5003       /* Associate ROOT with x1.  */
5004       assign_position_var (os, root, true);
5005
5006       /* Assign xN variables to all other relevant positions.  */
5007       assign_position_vars (os, s);
5008
5009       /* Output the variable declarations (except for ROOT's, which is
5010          passed in as a parameter).  */
5011       unsigned int num_vars = os->var_to_id.length ();
5012       if (num_vars > 2)
5013         {
5014           for (unsigned int i = 2; i < num_vars; ++i)
5015             /* Print 8 rtx variables to a line.  */
5016             printf ("%s x%d",
5017                     i == 2 ? "  rtx" : (i - 2) % 8 == 0 ? ";\n  rtx" : ",", i);
5018           printf (";\n");
5019         }
5020
5021       /* Say that x1 is valid and the rest aren't.  */
5022       os->seen_vars.safe_grow_cleared (num_vars);
5023       os->seen_vars[1] = true;
5024     }
5025   if (os->type == SUBPATTERN || os->type == RECOG)
5026     printf ("  int res ATTRIBUTE_UNUSED;\n");
5027   else
5028     printf ("  rtx res ATTRIBUTE_UNUSED;\n");
5029 }
5030
5031 /* Output the definition of pattern routine ROUTINE.  */
5032
5033 static void
5034 print_pattern (output_state *os, pattern_routine *routine)
5035 {
5036   printf ("\nstatic int\npattern%d (", routine->pattern_id);
5037   const char *sep = "";
5038   /* Add the top-level rtx parameter, if any.  */
5039   if (routine->pos)
5040     {
5041       printf ("%srtx x1", sep);
5042       sep = ", ";
5043     }
5044   /* Add the optional parameters.  */
5045   if (routine->insn_p)
5046     {
5047       /* We can't easily tell whether a C condition actually reads INSN,
5048          so add an ATTRIBUTE_UNUSED just in case.  */
5049       printf ("%srtx_insn *insn ATTRIBUTE_UNUSED", sep);
5050       sep = ", ";
5051     }
5052   if (routine->pnum_clobbers_p)
5053     {
5054       printf ("%sint *pnum_clobbers", sep);
5055       sep = ", ";
5056     }
5057   /* Add the "i" parameters.  */
5058   for (unsigned int i = 0; i < routine->param_types.length (); ++i)
5059     {
5060       printf ("%s%s i%d", sep,
5061               parameter_type_string (routine->param_types[i]), i + 1);
5062       sep = ", ";
5063     }
5064   printf (")\n");
5065   os->type = SUBPATTERN;
5066   print_subroutine_start (os, routine->s, routine->pos);
5067   print_state (os, routine->s, 2, true);
5068   printf ("}\n");
5069 }
5070
5071 /* Output a routine of type TYPE that implements S.  PROC_ID is the
5072    number of the subroutine associated with S, or 0 if S is the main
5073    routine.  */
5074
5075 static void
5076 print_subroutine (output_state *os, state *s, int proc_id)
5077 {
5078   /* For now, the top-level functions take a plain "rtx", and perform a
5079      checked cast to "rtx_insn *" for use throughout the rest of the
5080      function and the code it calls.  */
5081   const char *insn_param
5082     = proc_id > 0 ? "rtx_insn *insn" : "rtx uncast_insn";
5083   printf ("\n");
5084   switch (os->type)
5085     {
5086     case SUBPATTERN:
5087       gcc_unreachable ();
5088
5089     case RECOG:
5090       if (proc_id)
5091         printf ("static int\nrecog_%d", proc_id);
5092       else
5093         printf ("int\nrecog");
5094       printf (" (rtx x1 ATTRIBUTE_UNUSED,\n"
5095               "\t%s ATTRIBUTE_UNUSED,\n"
5096               "\tint *pnum_clobbers ATTRIBUTE_UNUSED)\n", insn_param);
5097       break;
5098
5099     case SPLIT:
5100       if (proc_id)
5101         printf ("static rtx\nsplit_%d", proc_id);
5102       else
5103         printf ("rtx\nsplit_insns");
5104       printf (" (rtx x1 ATTRIBUTE_UNUSED, %s ATTRIBUTE_UNUSED)\n",
5105               insn_param);
5106       break;
5107
5108     case PEEPHOLE2:
5109       if (proc_id)
5110         printf ("static rtx\npeephole2_%d", proc_id);
5111       else
5112         printf ("rtx\npeephole2_insns");
5113       printf (" (rtx x1 ATTRIBUTE_UNUSED,\n"
5114               "\t%s ATTRIBUTE_UNUSED,\n"
5115               "\tint *pmatch_len_ ATTRIBUTE_UNUSED)\n", insn_param);
5116       break;
5117     }
5118   print_subroutine_start (os, s, &root_pos);
5119   if (proc_id == 0)
5120     {
5121       printf ("  recog_data.insn = NULL_RTX;\n");
5122       printf ("  rtx_insn *insn ATTRIBUTE_UNUSED;\n");
5123       printf ("  insn = safe_as_a <rtx_insn *> (uncast_insn);\n");
5124     }
5125   print_state (os, s, 2, true);
5126   printf ("}\n");
5127 }
5128
5129 /* Print out a routine of type TYPE that performs ROOT.  */
5130
5131 static void
5132 print_subroutine_group (output_state *os, routine_type type, state *root)
5133 {
5134   os->type = type;
5135   if (use_subroutines_p)
5136     {
5137       /* Split ROOT up into smaller pieces, both for readability and to
5138          help the compiler.  */
5139       auto_vec <state *> subroutines;
5140       find_subroutines (type, root, subroutines);
5141
5142       /* Output the subroutines (but not ROOT itself).  */
5143       unsigned int i;
5144       state *s;
5145       FOR_EACH_VEC_ELT (subroutines, i, s)
5146         print_subroutine (os, s, i + 1);
5147     }
5148   /* Output the main routine.  */
5149   print_subroutine (os, root, 0);
5150 }
5151
5152 /* Return the rtx pattern specified by the list of rtxes in a
5153    define_insn or define_split.  */
5154
5155 static rtx
5156 add_implicit_parallel (rtvec vec)
5157 {
5158   if (GET_NUM_ELEM (vec) == 1)
5159     return RTVEC_ELT (vec, 0);
5160   else
5161     {
5162       rtx pattern = rtx_alloc (PARALLEL);
5163       XVEC (pattern, 0) = vec;
5164       return pattern;
5165     }
5166 }
5167
5168 /* Return true if *PATTERN_PTR is a PARALLEL in which at least one trailing
5169    rtx can be added automatically by add_clobbers.  If so, update
5170    *ACCEPTANCE_PTR so that its num_clobbers field contains the number
5171    of such trailing rtxes and update *PATTERN_PTR so that it contains
5172    the pattern without those rtxes.  */
5173
5174 static bool
5175 remove_clobbers (acceptance_type *acceptance_ptr, rtx *pattern_ptr)
5176 {
5177   int i;
5178   rtx new_pattern;
5179
5180   /* Find the last non-clobber in the parallel.  */
5181   rtx pattern = *pattern_ptr;
5182   for (i = XVECLEN (pattern, 0); i > 0; i--)
5183     {
5184       rtx x = XVECEXP (pattern, 0, i - 1);
5185       if (GET_CODE (x) != CLOBBER
5186           || (!REG_P (XEXP (x, 0))
5187               && GET_CODE (XEXP (x, 0)) != MATCH_SCRATCH))
5188         break;
5189     }
5190
5191   if (i == XVECLEN (pattern, 0))
5192     return false;
5193
5194   /* Build a similar insn without the clobbers.  */
5195   if (i == 1)
5196     new_pattern = XVECEXP (pattern, 0, 0);
5197   else
5198     {
5199       new_pattern = rtx_alloc (PARALLEL);
5200       XVEC (new_pattern, 0) = rtvec_alloc (i);
5201       for (int j = 0; j < i; ++j)
5202         XVECEXP (new_pattern, 0, j) = XVECEXP (pattern, 0, j);
5203     }
5204
5205   /* Recognize it.  */
5206   acceptance_ptr->u.full.u.num_clobbers = XVECLEN (pattern, 0) - i;
5207   *pattern_ptr = new_pattern;
5208   return true;
5209 }
5210
5211 int
5212 main (int argc, char **argv)
5213 {
5214   rtx desc;
5215   state insn_root, split_root, peephole2_root;
5216
5217   progname = "genrecog";
5218
5219   if (!init_rtx_reader_args (argc, argv))
5220     return (FATAL_EXIT_CODE);
5221
5222   next_insn_code = 0;
5223
5224   write_header ();
5225
5226   /* Read the machine description.  */
5227
5228   while (1)
5229     {
5230       desc = read_md_rtx (&pattern_lineno, &next_insn_code);
5231       if (desc == NULL)
5232         break;
5233
5234       rtx pattern;
5235
5236       acceptance_type acceptance;
5237       acceptance.partial_p = false;
5238       acceptance.u.full.code = next_insn_code;
5239
5240       switch (GET_CODE (desc))
5241         {
5242         case DEFINE_INSN:
5243           {
5244             /* Match the instruction in the original .md form.  */
5245             pattern = add_implicit_parallel (XVEC (desc, 1));
5246             acceptance.type = RECOG;
5247             acceptance.u.full.u.num_clobbers = 0;
5248             match_pattern (&insn_root, pattern, XSTR (desc, 2), acceptance);
5249
5250             /* If the pattern is a PARALLEL with trailing CLOBBERs,
5251                allow recog_for_combine to match without the clobbers.  */
5252             if (GET_CODE (pattern) == PARALLEL
5253                 && remove_clobbers (&acceptance, &pattern))
5254               match_pattern (&insn_root, pattern, XSTR (desc, 2), acceptance);
5255             break;
5256           }
5257
5258         case DEFINE_SPLIT:
5259           acceptance.type = SPLIT;
5260           pattern = add_implicit_parallel (XVEC (desc, 0));
5261           match_pattern (&split_root, pattern, XSTR (desc, 1), acceptance);
5262
5263           /* Declare the gen_split routine that we'll call if the
5264              pattern matches.  The definition comes from insn-emit.c.  */
5265           printf ("extern rtx gen_split_%d (rtx_insn *, rtx *);\n",
5266                   next_insn_code);
5267           break;
5268
5269         case DEFINE_PEEPHOLE2:
5270           acceptance.type = PEEPHOLE2;
5271           match_pattern (&peephole2_root, desc, XSTR (desc, 1), acceptance);
5272
5273           /* Declare the gen_peephole2 routine that we'll call if the
5274              pattern matches.  The definition comes from insn-emit.c.  */
5275           printf ("extern rtx gen_peephole2_%d (rtx_insn *, rtx *);\n",
5276                   next_insn_code);
5277           break;
5278
5279         default:
5280           /* do nothing */;
5281         }
5282     }
5283
5284   if (have_error)
5285     return FATAL_EXIT_CODE;
5286
5287   puts ("\n\n");
5288
5289   /* Optimize each routine in turn.  */
5290   optimize_subroutine_group ("recog", &insn_root);
5291   optimize_subroutine_group ("split_insns", &split_root);
5292   optimize_subroutine_group ("peephole2_insns", &peephole2_root);
5293
5294   output_state os;
5295   os.id_to_var.safe_grow_cleared (num_positions);
5296
5297   if (use_pattern_routines_p)
5298     {
5299       /* Look for common patterns and split them out into subroutines.  */
5300       auto_vec <merge_state_info> states;
5301       states.safe_push (&insn_root);
5302       states.safe_push (&split_root);
5303       states.safe_push (&peephole2_root);
5304       split_out_patterns (states);
5305
5306       /* Print out the routines that we just created.  */
5307       unsigned int i;
5308       pattern_routine *routine;
5309       FOR_EACH_VEC_ELT (patterns, i, routine)
5310         print_pattern (&os, routine);
5311     }
5312
5313   /* Print out the matching routines.  */
5314   print_subroutine_group (&os, RECOG, &insn_root);
5315   print_subroutine_group (&os, SPLIT, &split_root);
5316   print_subroutine_group (&os, PEEPHOLE2, &peephole2_root);
5317
5318   fflush (stdout);
5319   return (ferror (stdout) != 0 ? FATAL_EXIT_CODE : SUCCESS_EXIT_CODE);
5320 }