gcc/gensupport.c

   1 /* Support routines for the various generation passes.
   2    Copyright (C) 2000-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 #include "bconfig.h"
  21 #include "system.h"
  22 #include "coretypes.h"
  23 #include "tm.h"
  24 #include "rtl.h"
  25 #include "obstack.h"
  26 #include "errors.h"
  27 #include "read-md.h"
  28 #include "gensupport.h"
  29 #include "vec.h"
  30
  31 #define MAX_OPERANDS 40
  32
  33 static rtx operand_data[MAX_OPERANDS];
  34 static rtx match_operand_entries_in_pattern[MAX_OPERANDS];
  35 static char used_operands_numbers[MAX_OPERANDS];
  36
  37
  38 /* In case some macros used by files we include need it, define this here.  */
  39 int target_flags;
  40
  41 int insn_elision = 1;
  42
  43 static struct obstack obstack;
  44 struct obstack *rtl_obstack = &obstack;
  45
  46 /* Counter for named patterns and INSN_CODEs.  */
  47 static int insn_sequence_num;
  48
  49 /* Counter for define_splits.  */
  50 static int split_sequence_num;
  51
  52 /* Counter for define_peephole2s.  */
  53 static int peephole2_sequence_num;
  54
  55 static int predicable_default;
  56 static const char *predicable_true;
  57 static const char *predicable_false;
  58
  59 static const char *subst_true = "yes";
  60 static const char *subst_false = "no";
  61
  62 static htab_t condition_table;
  63
  64 /* We initially queue all patterns, process the define_insn,
  65    define_cond_exec and define_subst patterns, then return
  66    them one at a time.  */
  67
  68 struct queue_elem
  69 {
  70   rtx data;
  71   file_location loc;
  72   struct queue_elem *next;
  73   /* In a DEFINE_INSN that came from a DEFINE_INSN_AND_SPLIT, SPLIT
  74      points to the generated DEFINE_SPLIT.  */
  75   struct queue_elem *split;
  76 };
  77
  78 #define MNEMONIC_ATTR_NAME "mnemonic"
  79 #define MNEMONIC_HTAB_SIZE 1024
  80
  81 static struct queue_elem *define_attr_queue;
  82 static struct queue_elem **define_attr_tail = &define_attr_queue;
  83 static struct queue_elem *define_pred_queue;
  84 static struct queue_elem **define_pred_tail = &define_pred_queue;
  85 static struct queue_elem *define_insn_queue;
  86 static struct queue_elem **define_insn_tail = &define_insn_queue;
  87 static struct queue_elem *define_cond_exec_queue;
  88 static struct queue_elem **define_cond_exec_tail = &define_cond_exec_queue;
  89 static struct queue_elem *define_subst_queue;
  90 static struct queue_elem **define_subst_tail = &define_subst_queue;
  91 static struct queue_elem *other_queue;
  92 static struct queue_elem **other_tail = &other_queue;
  93 static struct queue_elem *define_subst_attr_queue;
  94 static struct queue_elem **define_subst_attr_tail = &define_subst_attr_queue;
  95
  96 /* Mapping from DEFINE_* rtxes to their location in the source file.  */
  97 static hash_map <rtx, file_location> *rtx_locs;
  98
  99 static void remove_constraints (rtx);
 100
 101 static int is_predicable (struct queue_elem *);
 102 static void identify_predicable_attribute (void);
 103 static int n_alternatives (const char *);
 104 static void collect_insn_data (rtx, int *, int *);
 105 static const char *alter_test_for_insn (struct queue_elem *,
 106                                         struct queue_elem *);
 107 static char *shift_output_template (char *, const char *, int);
 108 static const char *alter_output_for_insn (struct queue_elem *,
 109                                           struct queue_elem *,
 110                                           int, int);
 111 static void process_one_cond_exec (struct queue_elem *);
 112 static void process_define_cond_exec (void);
 113 static void init_predicate_table (void);
 114 static void record_insn_name (int, const char *);
 115
 116 static bool has_subst_attribute (struct queue_elem *, struct queue_elem *);
 117 static const char * alter_output_for_subst_insn (rtx, int);
 118 static void alter_attrs_for_subst_insn (struct queue_elem *, int);
 119 static void process_substs_on_one_elem (struct queue_elem *,
 120                                         struct queue_elem *);
 121 static rtx subst_dup (rtx, int, int);
 122 static void process_define_subst (void);
 123
 124 static const char * duplicate_alternatives (const char *, int);
 125 static const char * duplicate_each_alternative (const char * str, int n_dup);
 126
 127 typedef const char * (*constraints_handler_t) (const char *, int);
 128 static rtx alter_constraints (rtx, int, constraints_handler_t);
 129 static rtx adjust_operands_numbers (rtx);
 130 static rtx replace_duplicating_operands_in_pattern (rtx);
 131 \f
 132 /* Make a version of gen_rtx_CONST_INT so that GEN_INT can be used in
 133    the gensupport programs.  */
 134
 135 rtx
 136 gen_rtx_CONST_INT (machine_mode ARG_UNUSED (mode),
 137                    HOST_WIDE_INT arg)
 138 {
 139   rtx rt = rtx_alloc (CONST_INT);
 140
 141   XWINT (rt, 0) = arg;
 142   return rt;
 143 }
 144
 145 /* Return the rtx pattern specified by the list of rtxes in a
 146    define_insn or define_split.  */
 147
 148 rtx
 149 add_implicit_parallel (rtvec vec)
 150 {
 151   if (GET_NUM_ELEM (vec) == 1)
 152     return RTVEC_ELT (vec, 0);
 153   else
 154     {
 155       rtx pattern = rtx_alloc (PARALLEL);
 156       XVEC (pattern, 0) = vec;
 157       return pattern;
 158     }
 159 }
 160 \f
 161 /* Predicate handling.
 162
 163    We construct from the machine description a table mapping each
 164    predicate to a list of the rtl codes it can possibly match.  The
 165    function 'maybe_both_true' uses it to deduce that there are no
 166    expressions that can be matches by certain pairs of tree nodes.
 167    Also, if a predicate can match only one code, we can hardwire that
 168    code into the node testing the predicate.
 169
 170    Some predicates are flagged as special.  validate_pattern will not
 171    warn about modeless match_operand expressions if they have a
 172    special predicate.  Predicates that allow only constants are also
 173    treated as special, for this purpose.
 174
 175    validate_pattern will warn about predicates that allow non-lvalues
 176    when they appear in destination operands.
 177
 178    Calculating the set of rtx codes that can possibly be accepted by a
 179    predicate expression EXP requires a three-state logic: any given
 180    subexpression may definitively accept a code C (Y), definitively
 181    reject a code C (N), or may have an indeterminate effect (I).  N
 182    and I is N; Y or I is Y; Y and I, N or I are both I.  Here are full
 183    truth tables.
 184
 185      a b  a&b  a|b
 186      Y Y   Y    Y
 187      N Y   N    Y
 188      N N   N    N
 189      I Y   I    Y
 190      I N   N    I
 191      I I   I    I
 192
 193    We represent Y with 1, N with 0, I with 2.  If any code is left in
 194    an I state by the complete expression, we must assume that that
 195    code can be accepted.  */
 196
 197 #define N 0
 198 #define Y 1
 199 #define I 2
 200
 201 #define TRISTATE_AND(a,b)                       \
 202   ((a) == I ? ((b) == N ? N : I) :              \
 203    (b) == I ? ((a) == N ? N : I) :              \
 204    (a) && (b))
 205
 206 #define TRISTATE_OR(a,b)                        \
 207   ((a) == I ? ((b) == Y ? Y : I) :              \
 208    (b) == I ? ((a) == Y ? Y : I) :              \
 209    (a) || (b))
 210
 211 #define TRISTATE_NOT(a)                         \
 212   ((a) == I ? I : !(a))
 213
 214 /* 0 means no warning about that code yet, 1 means warned.  */
 215 static char did_you_mean_codes[NUM_RTX_CODE];
 216
 217 /* Recursively calculate the set of rtx codes accepted by the
 218    predicate expression EXP, writing the result to CODES.  LOC is
 219    the .md file location of the directive containing EXP.  */
 220
 221 void
 222 compute_test_codes (rtx exp, file_location loc, char *codes)
 223 {
 224   char op0_codes[NUM_RTX_CODE];
 225   char op1_codes[NUM_RTX_CODE];
 226   char op2_codes[NUM_RTX_CODE];
 227   int i;
 228
 229   switch (GET_CODE (exp))
 230     {
 231     case AND:
 232       compute_test_codes (XEXP (exp, 0), loc, op0_codes);
 233       compute_test_codes (XEXP (exp, 1), loc, op1_codes);
 234       for (i = 0; i < NUM_RTX_CODE; i++)
 235         codes[i] = TRISTATE_AND (op0_codes[i], op1_codes[i]);
 236       break;
 237
 238     case IOR:
 239       compute_test_codes (XEXP (exp, 0), loc, op0_codes);
 240       compute_test_codes (XEXP (exp, 1), loc, op1_codes);
 241       for (i = 0; i < NUM_RTX_CODE; i++)
 242         codes[i] = TRISTATE_OR (op0_codes[i], op1_codes[i]);
 243       break;
 244     case NOT:
 245       compute_test_codes (XEXP (exp, 0), loc, op0_codes);
 246       for (i = 0; i < NUM_RTX_CODE; i++)
 247         codes[i] = TRISTATE_NOT (op0_codes[i]);
 248       break;
 249
 250     case IF_THEN_ELSE:
 251       /* a ? b : c  accepts the same codes as (a & b) | (!a & c).  */
 252       compute_test_codes (XEXP (exp, 0), loc, op0_codes);
 253       compute_test_codes (XEXP (exp, 1), loc, op1_codes);
 254       compute_test_codes (XEXP (exp, 2), loc, op2_codes);
 255       for (i = 0; i < NUM_RTX_CODE; i++)
 256         codes[i] = TRISTATE_OR (TRISTATE_AND (op0_codes[i], op1_codes[i]),
 257                                 TRISTATE_AND (TRISTATE_NOT (op0_codes[i]),
 258                                               op2_codes[i]));
 259       break;
 260
 261     case MATCH_CODE:
 262       /* MATCH_CODE allows a specified list of codes.  However, if it
 263          does not apply to the top level of the expression, it does not
 264          constrain the set of codes for the top level.  */
 265       if (XSTR (exp, 1)[0] != '\0')
 266         {
 267           memset (codes, Y, NUM_RTX_CODE);
 268           break;
 269         }
 270
 271       memset (codes, N, NUM_RTX_CODE);
 272       {
 273         const char *next_code = XSTR (exp, 0);
 274         const char *code;
 275
 276         if (*next_code == '\0')
 277           {
 278             error_at (loc, "empty match_code expression");
 279             break;
 280           }
 281
 282         while ((code = scan_comma_elt (&next_code)) != 0)
 283           {
 284             size_t n = next_code - code;
 285             int found_it = 0;
 286
 287             for (i = 0; i < NUM_RTX_CODE; i++)
 288               if (!strncmp (code, GET_RTX_NAME (i), n)
 289                   && GET_RTX_NAME (i)[n] == '\0')
 290                 {
 291                   codes[i] = Y;
 292                   found_it = 1;
 293                   break;
 294                 }
 295             if (!found_it)
 296               {
 297                 error_at (loc, "match_code \"%.*s\" matches nothing",
 298                           (int) n, code);
 299                 for (i = 0; i < NUM_RTX_CODE; i++)
 300                   if (!strncasecmp (code, GET_RTX_NAME (i), n)
 301                       && GET_RTX_NAME (i)[n] == '\0'
 302                       && !did_you_mean_codes[i])
 303                     {
 304                       did_you_mean_codes[i] = 1;
 305                       message_at (loc, "(did you mean \"%s\"?)",
 306                                   GET_RTX_NAME (i));
 307                     }
 308               }
 309           }
 310       }
 311       break;
 312
 313     case MATCH_OPERAND:
 314       /* MATCH_OPERAND disallows the set of codes that the named predicate
 315          disallows, and is indeterminate for the codes that it does allow.  */
 316       {
 317         struct pred_data *p = lookup_predicate (XSTR (exp, 1));
 318         if (!p)
 319           {
 320             error_at (loc, "reference to unknown predicate '%s'",
 321                       XSTR (exp, 1));
 322             break;
 323           }
 324         for (i = 0; i < NUM_RTX_CODE; i++)
 325           codes[i] = p->codes[i] ? I : N;
 326       }
 327       break;
 328
 329
 330     case MATCH_TEST:
 331       /* (match_test WHATEVER) is completely indeterminate.  */
 332       memset (codes, I, NUM_RTX_CODE);
 333       break;
 334
 335     default:
 336       error_at (loc, "'%s' cannot be used in predicates or constraints",
 337                 GET_RTX_NAME (GET_CODE (exp)));
 338       memset (codes, I, NUM_RTX_CODE);
 339       break;
 340     }
 341 }
 342
 343 #undef TRISTATE_OR
 344 #undef TRISTATE_AND
 345 #undef TRISTATE_NOT
 346
 347 /* Return true if NAME is a valid predicate name.  */
 348
 349 static bool
 350 valid_predicate_name_p (const char *name)
 351 {
 352   const char *p;
 353
 354   if (!ISALPHA (name[0]) && name[0] != '_')
 355     return false;
 356   for (p = name + 1; *p; p++)
 357     if (!ISALNUM (*p) && *p != '_')
 358       return false;
 359   return true;
 360 }
 361
 362 /* Process define_predicate directive DESC, which appears at location LOC.
 363    Compute the set of codes that can be matched, and record this as a known
 364    predicate.  */
 365
 366 static void
 367 process_define_predicate (rtx desc, file_location loc)
 368 {
 369   struct pred_data *pred;
 370   char codes[NUM_RTX_CODE];
 371   int i;
 372
 373   if (!valid_predicate_name_p (XSTR (desc, 0)))
 374     {
 375       error_at (loc, "%s: predicate name must be a valid C function name",
 376                 XSTR (desc, 0));
 377       return;
 378     }
 379
 380   pred = XCNEW (struct pred_data);
 381   pred->name = XSTR (desc, 0);
 382   pred->exp = XEXP (desc, 1);
 383   pred->c_block = XSTR (desc, 2);
 384   if (GET_CODE (desc) == DEFINE_SPECIAL_PREDICATE)
 385     pred->special = true;
 386
 387   compute_test_codes (XEXP (desc, 1), loc, codes);
 388
 389   for (i = 0; i < NUM_RTX_CODE; i++)
 390     if (codes[i] != N)
 391       add_predicate_code (pred, (enum rtx_code) i);
 392
 393   add_predicate (pred);
 394 }
 395 #undef I
 396 #undef N
 397 #undef Y
 398 \f
 399 /* Queue PATTERN on LIST_TAIL.  Return the address of the new queue
 400    element.  */
 401
 402 static struct queue_elem *
 403 queue_pattern (rtx pattern, struct queue_elem ***list_tail,
 404                file_location loc)
 405 {
 406   struct queue_elem *e = XNEW (struct queue_elem);
 407   e->data = pattern;
 408   e->loc = loc;
 409   e->next = NULL;
 410   e->split = NULL;
 411   **list_tail = e;
 412   *list_tail = &e->next;
 413   return e;
 414 }
 415
 416 /* Remove element ELEM from QUEUE.  */
 417 static void
 418 remove_from_queue (struct queue_elem *elem, struct queue_elem **queue)
 419 {
 420   struct queue_elem *prev, *e;
 421   prev = NULL;
 422   for (e = *queue; e ; e = e->next)
 423     {
 424       if (e == elem)
 425         break;
 426       prev = e;
 427     }
 428   if (e == NULL)
 429     return;
 430
 431   if (prev)
 432     prev->next = elem->next;
 433   else
 434     *queue = elem->next;
 435 }
 436
 437 /* Build a define_attr for an binary attribute with name NAME and
 438    possible values "yes" and "no", and queue it.  */
 439 static void
 440 add_define_attr (const char *name)
 441 {
 442   struct queue_elem *e = XNEW (struct queue_elem);
 443   rtx t1 = rtx_alloc (DEFINE_ATTR);
 444   XSTR (t1, 0) = name;
 445   XSTR (t1, 1) = "no,yes";
 446   XEXP (t1, 2) = rtx_alloc (CONST_STRING);
 447   XSTR (XEXP (t1, 2), 0) = "yes";
 448   e->data = t1;
 449   e->loc = file_location ("built-in", -1);
 450   e->next = define_attr_queue;
 451   define_attr_queue = e;
 452
 453 }
 454
 455 /* Recursively remove constraints from an rtx.  */
 456
 457 static void
 458 remove_constraints (rtx part)
 459 {
 460   int i, j;
 461   const char *format_ptr;
 462
 463   if (part == 0)
 464     return;
 465
 466   if (GET_CODE (part) == MATCH_OPERAND)
 467     XSTR (part, 2) = "";
 468   else if (GET_CODE (part) == MATCH_SCRATCH)
 469     XSTR (part, 1) = "";
 470
 471   format_ptr = GET_RTX_FORMAT (GET_CODE (part));
 472
 473   for (i = 0; i < GET_RTX_LENGTH (GET_CODE (part)); i++)
 474     switch (*format_ptr++)
 475       {
 476       case 'e':
 477       case 'u':
 478         remove_constraints (XEXP (part, i));
 479         break;
 480       case 'E':
 481         if (XVEC (part, i) != NULL)
 482           for (j = 0; j < XVECLEN (part, i); j++)
 483             remove_constraints (XVECEXP (part, i, j));
 484         break;
 485       }
 486 }
 487
 488 /* Process a top level rtx in some way, queuing as appropriate.  */
 489
 490 static void
 491 process_rtx (rtx desc, file_location loc)
 492 {
 493   switch (GET_CODE (desc))
 494     {
 495     case DEFINE_INSN:
 496       queue_pattern (desc, &define_insn_tail, loc);
 497       break;
 498
 499     case DEFINE_COND_EXEC:
 500       queue_pattern (desc, &define_cond_exec_tail, loc);
 501       break;
 502
 503     case DEFINE_SUBST:
 504       queue_pattern (desc, &define_subst_tail, loc);
 505       break;
 506
 507     case DEFINE_SUBST_ATTR:
 508       queue_pattern (desc, &define_subst_attr_tail, loc);
 509       break;
 510
 511     case DEFINE_ATTR:
 512     case DEFINE_ENUM_ATTR:
 513       queue_pattern (desc, &define_attr_tail, loc);
 514       break;
 515
 516     case DEFINE_PREDICATE:
 517     case DEFINE_SPECIAL_PREDICATE:
 518       process_define_predicate (desc, loc);
 519       /* Fall through.  */
 520
 521     case DEFINE_CONSTRAINT:
 522     case DEFINE_REGISTER_CONSTRAINT:
 523     case DEFINE_MEMORY_CONSTRAINT:
 524     case DEFINE_ADDRESS_CONSTRAINT:
 525       queue_pattern (desc, &define_pred_tail, loc);
 526       break;
 527
 528     case DEFINE_INSN_AND_SPLIT:
 529       {
 530         const char *split_cond;
 531         rtx split;
 532         rtvec attr;
 533         int i;
 534         struct queue_elem *insn_elem;
 535         struct queue_elem *split_elem;
 536
 537         /* Create a split with values from the insn_and_split.  */
 538         split = rtx_alloc (DEFINE_SPLIT);
 539
 540         i = XVECLEN (desc, 1);
 541         XVEC (split, 0) = rtvec_alloc (i);
 542         while (--i >= 0)
 543           {
 544             XVECEXP (split, 0, i) = copy_rtx (XVECEXP (desc, 1, i));
 545             remove_constraints (XVECEXP (split, 0, i));
 546           }
 547
 548         /* If the split condition starts with "&&", append it to the
 549            insn condition to create the new split condition.  */
 550         split_cond = XSTR (desc, 4);
 551         if (split_cond[0] == '&' && split_cond[1] == '&')
 552           {
 553             copy_md_ptr_loc (split_cond + 2, split_cond);
 554             split_cond = join_c_conditions (XSTR (desc, 2), split_cond + 2);
 555           }
 556         XSTR (split, 1) = split_cond;
 557         XVEC (split, 2) = XVEC (desc, 5);
 558         XSTR (split, 3) = XSTR (desc, 6);
 559
 560         /* Fix up the DEFINE_INSN.  */
 561         attr = XVEC (desc, 7);
 562         PUT_CODE (desc, DEFINE_INSN);
 563         XVEC (desc, 4) = attr;
 564
 565         /* Queue them.  */
 566         insn_elem = queue_pattern (desc, &define_insn_tail, loc);
 567         split_elem = queue_pattern (split, &other_tail, loc);
 568         insn_elem->split = split_elem;
 569         break;
 570       }
 571
 572     default:
 573       queue_pattern (desc, &other_tail, loc);
 574       break;
 575     }
 576 }
 577 \f
 578 /* Return true if attribute PREDICABLE is true for ELEM, which holds
 579    a DEFINE_INSN.  */
 580
 581 static int
 582 is_predicable (struct queue_elem *elem)
 583 {
 584   rtvec vec = XVEC (elem->data, 4);
 585   const char *value;
 586   int i;
 587
 588   if (! vec)
 589     return predicable_default;
 590
 591   for (i = GET_NUM_ELEM (vec) - 1; i >= 0; --i)
 592     {
 593       rtx sub = RTVEC_ELT (vec, i);
 594       switch (GET_CODE (sub))
 595         {
 596         case SET_ATTR:
 597           if (strcmp (XSTR (sub, 0), "predicable") == 0)
 598             {
 599               value = XSTR (sub, 1);
 600               goto found;
 601             }
 602           break;
 603
 604         case SET_ATTR_ALTERNATIVE:
 605           if (strcmp (XSTR (sub, 0), "predicable") == 0)
 606             {
 607               error_at (elem->loc, "multiple alternatives for `predicable'");
 608               return 0;
 609             }
 610           break;
 611
 612         case SET:
 613           if (GET_CODE (SET_DEST (sub)) != ATTR
 614               || strcmp (XSTR (SET_DEST (sub), 0), "predicable") != 0)
 615             break;
 616           sub = SET_SRC (sub);
 617           if (GET_CODE (sub) == CONST_STRING)
 618             {
 619               value = XSTR (sub, 0);
 620               goto found;
 621             }
 622
 623           /* ??? It would be possible to handle this if we really tried.
 624              It's not easy though, and I'm not going to bother until it
 625              really proves necessary.  */
 626           error_at (elem->loc, "non-constant value for `predicable'");
 627           return 0;
 628
 629         default:
 630           gcc_unreachable ();
 631         }
 632     }
 633
 634   return predicable_default;
 635
 636  found:
 637   /* Find out which value we're looking at.  Multiple alternatives means at
 638      least one is predicable.  */
 639   if (strchr (value, ',') != NULL)
 640     return 1;
 641   if (strcmp (value, predicable_true) == 0)
 642     return 1;
 643   if (strcmp (value, predicable_false) == 0)
 644     return 0;
 645
 646   error_at (elem->loc, "unknown value `%s' for `predicable' attribute", value);
 647   return 0;
 648 }
 649
 650 /* Find attribute SUBST in ELEM and assign NEW_VALUE to it.  */
 651 static void
 652 change_subst_attribute (struct queue_elem *elem,
 653                         struct queue_elem *subst_elem,
 654                         const char *new_value)
 655 {
 656   rtvec attrs_vec = XVEC (elem->data, 4);
 657   const char *subst_name = XSTR (subst_elem->data, 0);
 658   int i;
 659
 660   if (! attrs_vec)
 661     return;
 662
 663   for (i = GET_NUM_ELEM (attrs_vec) - 1; i >= 0; --i)
 664     {
 665       rtx cur_attr = RTVEC_ELT (attrs_vec, i);
 666       if (GET_CODE (cur_attr) != SET_ATTR)
 667         continue;
 668       if (strcmp (XSTR (cur_attr, 0), subst_name) == 0)
 669         {
 670           XSTR (cur_attr, 1) = new_value;
 671           return;
 672         }
 673     }
 674 }
 675
 676 /* Return true if ELEM has the attribute with the name of DEFINE_SUBST
 677    represented by SUBST_ELEM and this attribute has value SUBST_TRUE.
 678    DEFINE_SUBST isn't applied to patterns without such attribute.  In other
 679    words, we suppose the default value of the attribute to be 'no' since it is
 680    always generated automaticaly in read-rtl.c.  */
 681 static bool
 682 has_subst_attribute (struct queue_elem *elem, struct queue_elem *subst_elem)
 683 {
 684   rtvec attrs_vec = XVEC (elem->data, 4);
 685   const char *value, *subst_name = XSTR (subst_elem->data, 0);
 686   int i;
 687
 688   if (! attrs_vec)
 689     return false;
 690
 691   for (i = GET_NUM_ELEM (attrs_vec) - 1; i >= 0; --i)
 692     {
 693       rtx cur_attr = RTVEC_ELT (attrs_vec, i);
 694       switch (GET_CODE (cur_attr))
 695         {
 696         case SET_ATTR:
 697           if (strcmp (XSTR (cur_attr, 0), subst_name) == 0)
 698             {
 699               value = XSTR (cur_attr, 1);
 700               goto found;
 701             }
 702           break;
 703
 704         case SET:
 705           if (GET_CODE (SET_DEST (cur_attr)) != ATTR
 706               || strcmp (XSTR (SET_DEST (cur_attr), 0), subst_name) != 0)
 707             break;
 708           cur_attr = SET_SRC (cur_attr);
 709           if (GET_CODE (cur_attr) == CONST_STRING)
 710             {
 711               value = XSTR (cur_attr, 0);
 712               goto found;
 713             }
 714
 715           /* Only (set_attr "subst" "yes/no") and
 716                   (set (attr "subst" (const_string "yes/no")))
 717              are currently allowed.  */
 718           error_at (elem->loc, "unsupported value for `%s'", subst_name);
 719           return false;
 720
 721         case SET_ATTR_ALTERNATIVE:
 722           error_at (elem->loc,
 723                     "%s: `set_attr_alternative' is unsupported by "
 724                     "`define_subst'", XSTR (elem->data, 0));
 725           return false;
 726
 727
 728         default:
 729           gcc_unreachable ();
 730         }
 731     }
 732
 733   return false;
 734
 735  found:
 736   if (strcmp (value, subst_true) == 0)
 737     return true;
 738   if (strcmp (value, subst_false) == 0)
 739     return false;
 740
 741   error_at (elem->loc, "unknown value `%s' for `%s' attribute",
 742             value, subst_name);
 743   return false;
 744 }
 745
 746 /* Compare RTL-template of original define_insn X to input RTL-template of
 747    define_subst PT.  Return 1 if the templates match, 0 otherwise.
 748    During the comparison, the routine also fills global_array OPERAND_DATA.  */
 749 static bool
 750 subst_pattern_match (rtx x, rtx pt, file_location loc)
 751 {
 752   RTX_CODE code, code_pt;
 753   int i, j, len;
 754   const char *fmt, *pred_name;
 755
 756   code = GET_CODE (x);
 757   code_pt = GET_CODE (pt);
 758
 759   if (code_pt == MATCH_OPERAND)
 760     {
 761       /* MATCH_DUP, and MATCH_OP_DUP don't have a specified mode, so we
 762          always accept them.  */
 763       if (GET_MODE (pt) != VOIDmode && GET_MODE (x) != GET_MODE (pt)
 764           && (code != MATCH_DUP && code != MATCH_OP_DUP))
 765         return false; /* Modes don't match.  */
 766
 767       if (code == MATCH_OPERAND)
 768         {
 769           pred_name = XSTR (pt, 1);
 770           if (pred_name[0] != 0)
 771             {
 772               const struct pred_data *pred_pt = lookup_predicate (pred_name);
 773               if (!pred_pt || pred_pt != lookup_predicate (XSTR (x, 1)))
 774                 return false; /* Predicates don't match.  */
 775             }
 776         }
 777
 778       gcc_assert (XINT (pt, 0) >= 0 && XINT (pt, 0) < MAX_OPERANDS);
 779       operand_data[XINT (pt, 0)] = x;
 780       return true;
 781     }
 782
 783   if (code_pt == MATCH_OPERATOR)
 784     {
 785       int x_vecexp_pos = -1;
 786
 787       /* Compare modes.  */
 788       if (GET_MODE (pt) != VOIDmode && GET_MODE (x) != GET_MODE (pt))
 789         return false;
 790
 791       /* In case X is also match_operator, compare predicates.  */
 792       if (code == MATCH_OPERATOR)
 793         {
 794           pred_name = XSTR (pt, 1);
 795           if (pred_name[0] != 0)
 796             {
 797               const struct pred_data *pred_pt = lookup_predicate (pred_name);
 798               if (!pred_pt || pred_pt != lookup_predicate (XSTR (x, 1)))
 799                 return false;
 800             }
 801         }
 802
 803       /* Compare operands.
 804          MATCH_OPERATOR in input template could match in original template
 805          either 1) MATCH_OPERAND, 2) UNSPEC, 3) ordinary operation (like PLUS).
 806          In the first case operands are at (XVECEXP (x, 2, j)), in the second
 807          - at (XVECEXP (x, 0, j)), in the last one - (XEXP (x, j)).
 808          X_VECEXP_POS variable shows, where to look for these operands.  */
 809       if (code == UNSPEC
 810           || code == UNSPEC_VOLATILE)
 811         x_vecexp_pos = 0;
 812       else if (code == MATCH_OPERATOR)
 813         x_vecexp_pos = 2;
 814       else
 815         x_vecexp_pos = -1;
 816
 817       /* MATCH_OPERATOR or UNSPEC case.  */
 818       if (x_vecexp_pos >= 0)
 819         {
 820           /* Compare operands number in X and PT.  */
 821           if (XVECLEN (x, x_vecexp_pos) != XVECLEN (pt, 2))
 822             return false;
 823           for (j = 0; j < XVECLEN (pt, 2); j++)
 824             if (!subst_pattern_match (XVECEXP (x, x_vecexp_pos, j),
 825                                       XVECEXP (pt, 2, j), loc))
 826               return false;
 827         }
 828
 829       /* Ordinary operator.  */
 830       else
 831         {
 832           /* Compare operands number in X and PT.
 833              We count operands differently for X and PT since we compare
 834              an operator (with operands directly in RTX) and MATCH_OPERATOR
 835              (that has a vector with operands).  */
 836           if (GET_RTX_LENGTH (code) != XVECLEN (pt, 2))
 837             return false;
 838           for (j = 0; j < XVECLEN (pt, 2); j++)
 839             if (!subst_pattern_match (XEXP (x, j), XVECEXP (pt, 2, j), loc))
 840               return false;
 841         }
 842
 843       /* Store the operand to OPERAND_DATA array.  */
 844       gcc_assert (XINT (pt, 0) >= 0 && XINT (pt, 0) < MAX_OPERANDS);
 845       operand_data[XINT (pt, 0)] = x;
 846       return true;
 847     }
 848
 849   if (code_pt == MATCH_PAR_DUP
 850       || code_pt == MATCH_DUP
 851       || code_pt == MATCH_OP_DUP
 852       || code_pt == MATCH_SCRATCH
 853       || code_pt == MATCH_PARALLEL)
 854     {
 855       /* Currently interface for these constructions isn't defined -
 856          probably they aren't needed in input template of define_subst at all.
 857          So, for now their usage in define_subst is forbidden.  */
 858       error_at (loc, "%s cannot be used in define_subst",
 859                 GET_RTX_NAME (code_pt));
 860     }
 861
 862   gcc_assert (code != MATCH_PAR_DUP
 863       && code_pt != MATCH_DUP
 864       && code_pt != MATCH_OP_DUP
 865       && code_pt != MATCH_SCRATCH
 866       && code_pt != MATCH_PARALLEL
 867       && code_pt != MATCH_OPERAND
 868       && code_pt != MATCH_OPERATOR);
 869   /* If PT is none of the handled above, then we match only expressions with
 870      the same code in X.  */
 871   if (code != code_pt)
 872     return false;
 873
 874   fmt = GET_RTX_FORMAT (code_pt);
 875   len = GET_RTX_LENGTH (code_pt);
 876
 877   for (i = 0; i < len; i++)
 878     {
 879       if (fmt[i] == '0')
 880         break;
 881
 882       switch (fmt[i])
 883         {
 884         case 'i': case 'r': case 'w': case 's':
 885           continue;
 886
 887         case 'e': case 'u':
 888           if (!subst_pattern_match (XEXP (x, i), XEXP (pt, i), loc))
 889             return false;
 890           break;
 891         case 'E':
 892           {
 893             if (XVECLEN (x, i) != XVECLEN (pt, i))
 894               return false;
 895             for (j = 0; j < XVECLEN (pt, i); j++)
 896               if (!subst_pattern_match (XVECEXP (x, i, j),
 897                                         XVECEXP (pt, i, j), loc))
 898                 return false;
 899             break;
 900           }
 901         default:
 902           gcc_unreachable ();
 903         }
 904     }
 905
 906   return true;
 907 }
 908
 909 /* Examine the attribute "predicable"; discover its boolean values
 910    and its default.  */
 911
 912 static void
 913 identify_predicable_attribute (void)
 914 {
 915   struct queue_elem *elem;
 916   char *p_true, *p_false;
 917   const char *value;
 918
 919   /* Look for the DEFINE_ATTR for `predicable', which must exist.  */
 920   for (elem = define_attr_queue; elem ; elem = elem->next)
 921     if (strcmp (XSTR (elem->data, 0), "predicable") == 0)
 922       goto found;
 923
 924   error_at (define_cond_exec_queue->loc,
 925             "attribute `predicable' not defined");
 926   return;
 927
 928  found:
 929   value = XSTR (elem->data, 1);
 930   p_false = xstrdup (value);
 931   p_true = strchr (p_false, ',');
 932   if (p_true == NULL || strchr (++p_true, ',') != NULL)
 933     {
 934       error_at (elem->loc, "attribute `predicable' is not a boolean");
 935       free (p_false);
 936       return;
 937     }
 938   p_true[-1] = '\0';
 939
 940   predicable_true = p_true;
 941   predicable_false = p_false;
 942
 943   switch (GET_CODE (XEXP (elem->data, 2)))
 944     {
 945     case CONST_STRING:
 946       value = XSTR (XEXP (elem->data, 2), 0);
 947       break;
 948
 949     case CONST:
 950       error_at (elem->loc, "attribute `predicable' cannot be const");
 951       free (p_false);
 952       return;
 953
 954     default:
 955       error_at (elem->loc,
 956                 "attribute `predicable' must have a constant default");
 957       free (p_false);
 958       return;
 959     }
 960
 961   if (strcmp (value, p_true) == 0)
 962     predicable_default = 1;
 963   else if (strcmp (value, p_false) == 0)
 964     predicable_default = 0;
 965   else
 966     {
 967       error_at (elem->loc, "unknown value `%s' for `predicable' attribute",
 968                 value);
 969       free (p_false);
 970     }
 971 }
 972
 973 /* Return the number of alternatives in constraint S.  */
 974
 975 static int
 976 n_alternatives (const char *s)
 977 {
 978   int n = 1;
 979
 980   if (s)
 981     while (*s)
 982       n += (*s++ == ',');
 983
 984   return n;
 985 }
 986
 987 /* The routine scans rtl PATTERN, find match_operand in it and counts
 988    number of alternatives.  If PATTERN contains several match_operands
 989    with different number of alternatives, error is emitted, and the
 990    routine returns 0.  If all match_operands in PATTERN have the same
 991    number of alternatives, it's stored in N_ALT, and the routine returns 1.
 992    LOC is the location of PATTERN, for error reporting.  */
 993 static int
 994 get_alternatives_number (rtx pattern, int *n_alt, file_location loc)
 995 {
 996   const char *fmt;
 997   enum rtx_code code;
 998   int i, j, len;
 999
1000   if (!n_alt)
1001     return 0;
1002
1003   code = GET_CODE (pattern);
1004   switch (code)
1005     {
1006     case MATCH_OPERAND:
1007       i = n_alternatives (XSTR (pattern, 2));
1008       /* n_alternatives returns 1 if constraint string is empty -
1009          here we fix it up.  */
1010       if (!*(XSTR (pattern, 2)))
1011         i = 0;
1012       if (*n_alt <= 0)
1013         *n_alt = i;
1014
1015       else if (i && i != *n_alt)
1016         {
1017           error_at (loc, "wrong number of alternatives in operand %d",
1018                     XINT (pattern, 0));
1019           return 0;
1020         }
1021
1022     default:
1023       break;
1024     }
1025
1026   fmt = GET_RTX_FORMAT (code);
1027   len = GET_RTX_LENGTH (code);
1028   for (i = 0; i < len; i++)
1029     {
1030       switch (fmt[i])
1031         {
1032         case 'e': case 'u':
1033           if (!get_alternatives_number (XEXP (pattern, i), n_alt, loc))
1034             return 0;
1035           break;
1036
1037         case 'V':
1038           if (XVEC (pattern, i) == NULL)
1039             break;
1040
1041         case 'E':
1042           for (j = XVECLEN (pattern, i) - 1; j >= 0; --j)
1043             if (!get_alternatives_number (XVECEXP (pattern, i, j), n_alt, loc))
1044               return 0;
1045           break;
1046
1047         case 'i': case 'r': case 'w': case '0': case 's': case 'S': case 'T':
1048           break;
1049
1050         default:
1051           gcc_unreachable ();
1052         }
1053     }
1054     return 1;
1055 }
1056
1057 /* Determine how many alternatives there are in INSN, and how many
1058    operands.  */
1059
1060 static void
1061 collect_insn_data (rtx pattern, int *palt, int *pmax)
1062 {
1063   const char *fmt;
1064   enum rtx_code code;
1065   int i, j, len;
1066
1067   code = GET_CODE (pattern);
1068   switch (code)
1069     {
1070     case MATCH_OPERAND:
1071       i = n_alternatives (XSTR (pattern, 2));
1072       *palt = (i > *palt ? i : *palt);
1073       /* Fall through.  */
1074
1075     case MATCH_OPERATOR:
1076     case MATCH_SCRATCH:
1077     case MATCH_PARALLEL:
1078       i = XINT (pattern, 0);
1079       if (i > *pmax)
1080         *pmax = i;
1081       break;
1082
1083     default:
1084       break;
1085     }
1086
1087   fmt = GET_RTX_FORMAT (code);
1088   len = GET_RTX_LENGTH (code);
1089   for (i = 0; i < len; i++)
1090     {
1091       switch (fmt[i])
1092         {
1093         case 'e': case 'u':
1094           collect_insn_data (XEXP (pattern, i), palt, pmax);
1095           break;
1096
1097         case 'V':
1098           if (XVEC (pattern, i) == NULL)
1099             break;
1100           /* Fall through.  */
1101         case 'E':
1102           for (j = XVECLEN (pattern, i) - 1; j >= 0; --j)
1103             collect_insn_data (XVECEXP (pattern, i, j), palt, pmax);
1104           break;
1105
1106         case 'i': case 'r': case 'w': case '0': case 's': case 'S': case 'T':
1107           break;
1108
1109         default:
1110           gcc_unreachable ();
1111         }
1112     }
1113 }
1114
1115 static rtx
1116 alter_predicate_for_insn (rtx pattern, int alt, int max_op,
1117                           file_location loc)
1118 {
1119   const char *fmt;
1120   enum rtx_code code;
1121   int i, j, len;
1122
1123   code = GET_CODE (pattern);
1124   switch (code)
1125     {
1126     case MATCH_OPERAND:
1127       {
1128         const char *c = XSTR (pattern, 2);
1129
1130         if (n_alternatives (c) != 1)
1131           {
1132             error_at (loc, "too many alternatives for operand %d",
1133                       XINT (pattern, 0));
1134             return NULL;
1135           }
1136
1137         /* Replicate C as needed to fill out ALT alternatives.  */
1138         if (c && *c && alt > 1)
1139           {
1140             size_t c_len = strlen (c);
1141             size_t len = alt * (c_len + 1);
1142             char *new_c = XNEWVEC (char, len);
1143
1144             memcpy (new_c, c, c_len);
1145             for (i = 1; i < alt; ++i)
1146               {
1147                 new_c[i * (c_len + 1) - 1] = ',';
1148                 memcpy (&new_c[i * (c_len + 1)], c, c_len);
1149               }
1150             new_c[len - 1] = '\0';
1151             XSTR (pattern, 2) = new_c;
1152           }
1153       }
1154       /* Fall through.  */
1155
1156     case MATCH_OPERATOR:
1157     case MATCH_SCRATCH:
1158     case MATCH_PARALLEL:
1159       XINT (pattern, 0) += max_op;
1160       break;
1161
1162     default:
1163       break;
1164     }
1165
1166   fmt = GET_RTX_FORMAT (code);
1167   len = GET_RTX_LENGTH (code);
1168   for (i = 0; i < len; i++)
1169     {
1170       rtx r;
1171
1172       switch (fmt[i])
1173         {
1174         case 'e': case 'u':
1175           r = alter_predicate_for_insn (XEXP (pattern, i), alt, max_op, loc);
1176           if (r == NULL)
1177             return r;
1178           break;
1179
1180         case 'E':
1181           for (j = XVECLEN (pattern, i) - 1; j >= 0; --j)
1182             {
1183               r = alter_predicate_for_insn (XVECEXP (pattern, i, j),
1184                                             alt, max_op, loc);
1185               if (r == NULL)
1186                 return r;
1187             }
1188           break;
1189
1190         case 'i': case 'r': case 'w': case '0': case 's':
1191           break;
1192
1193         default:
1194           gcc_unreachable ();
1195         }
1196     }
1197
1198   return pattern;
1199 }
1200
1201 /* Duplicate constraints in PATTERN.  If pattern is from original
1202    rtl-template, we need to duplicate each alternative - for that we
1203    need to use duplicate_each_alternative () as a functor ALTER.
1204    If pattern is from output-pattern of define_subst, we need to
1205    duplicate constraints in another way - with duplicate_alternatives ().
1206    N_DUP is multiplication factor.  */
1207 static rtx
1208 alter_constraints (rtx pattern, int n_dup, constraints_handler_t alter)
1209 {
1210   const char *fmt;
1211   enum rtx_code code;
1212   int i, j, len;
1213
1214   code = GET_CODE (pattern);
1215   switch (code)
1216     {
1217     case MATCH_OPERAND:
1218       XSTR (pattern, 2) = alter (XSTR (pattern, 2), n_dup);
1219       break;
1220
1221     default:
1222       break;
1223     }
1224
1225   fmt = GET_RTX_FORMAT (code);
1226   len = GET_RTX_LENGTH (code);
1227   for (i = 0; i < len; i++)
1228     {
1229       rtx r;
1230
1231       switch (fmt[i])
1232         {
1233         case 'e': case 'u':
1234           r = alter_constraints (XEXP (pattern, i), n_dup, alter);
1235           if (r == NULL)
1236             return r;
1237           break;
1238
1239         case 'E':
1240           for (j = XVECLEN (pattern, i) - 1; j >= 0; --j)
1241             {
1242               r = alter_constraints (XVECEXP (pattern, i, j), n_dup, alter);
1243               if (r == NULL)
1244                 return r;
1245             }
1246           break;
1247
1248         case 'i': case 'r': case 'w': case '0': case 's':
1249           break;
1250
1251         default:
1252           break;
1253         }
1254     }
1255
1256   return pattern;
1257 }
1258
1259 static const char *
1260 alter_test_for_insn (struct queue_elem *ce_elem,
1261                      struct queue_elem *insn_elem)
1262 {
1263   return join_c_conditions (XSTR (ce_elem->data, 1),
1264                             XSTR (insn_elem->data, 2));
1265 }
1266
1267 /* Modify VAL, which is an attribute expression for the "enabled" attribute,
1268    to take "ce_enabled" into account.  Return the new expression.  */
1269 static rtx
1270 modify_attr_enabled_ce (rtx val)
1271 {
1272   rtx eq_attr, str;
1273   rtx ite;
1274   eq_attr = rtx_alloc (EQ_ATTR);
1275   ite = rtx_alloc (IF_THEN_ELSE);
1276   str = rtx_alloc (CONST_STRING);
1277
1278   XSTR (eq_attr, 0) = "ce_enabled";
1279   XSTR (eq_attr, 1) = "yes";
1280   XSTR (str, 0) = "no";
1281   XEXP (ite, 0) = eq_attr;
1282   XEXP (ite, 1) = val;
1283   XEXP (ite, 2) = str;
1284
1285   return ite;
1286 }
1287
1288 /* Alter the attribute vector of INSN, which is a COND_EXEC variant created
1289    from a define_insn pattern.  We must modify the "predicable" attribute
1290    to be named "ce_enabled", and also change any "enabled" attribute that's
1291    present so that it takes ce_enabled into account.
1292    We rely on the fact that INSN was created with copy_rtx, and modify data
1293    in-place.  */
1294
1295 static void
1296 alter_attrs_for_insn (rtx insn)
1297 {
1298   static bool global_changes_made = false;
1299   rtvec vec = XVEC (insn, 4);
1300   rtvec new_vec;
1301   rtx val, set;
1302   int num_elem;
1303   int predicable_idx = -1;
1304   int enabled_idx = -1;
1305   int i;
1306
1307   if (! vec)
1308     return;
1309
1310   num_elem = GET_NUM_ELEM (vec);
1311   for (i = num_elem - 1; i >= 0; --i)
1312     {
1313       rtx sub = RTVEC_ELT (vec, i);
1314       switch (GET_CODE (sub))
1315         {
1316         case SET_ATTR:
1317           if (strcmp (XSTR (sub, 0), "predicable") == 0)
1318             {
1319               predicable_idx = i;
1320               XSTR (sub, 0) = "ce_enabled";
1321             }
1322           else if (strcmp (XSTR (sub, 0), "enabled") == 0)
1323             {
1324               enabled_idx = i;
1325               XSTR (sub, 0) = "nonce_enabled";
1326             }
1327           break;
1328
1329         case SET_ATTR_ALTERNATIVE:
1330           if (strcmp (XSTR (sub, 0), "predicable") == 0)
1331             /* We already give an error elsewhere.  */
1332             return;
1333           else if (strcmp (XSTR (sub, 0), "enabled") == 0)
1334             {
1335               enabled_idx = i;
1336               XSTR (sub, 0) = "nonce_enabled";
1337             }
1338           break;
1339
1340         case SET:
1341           if (GET_CODE (SET_DEST (sub)) != ATTR)
1342             break;
1343           if (strcmp (XSTR (SET_DEST (sub), 0), "predicable") == 0)
1344             {
1345               sub = SET_SRC (sub);
1346               if (GET_CODE (sub) == CONST_STRING)
1347                 {
1348                   predicable_idx = i;
1349                   XSTR (sub, 0) = "ce_enabled";
1350                 }
1351               else
1352                 /* We already give an error elsewhere.  */
1353                 return;
1354               break;
1355             }
1356           if (strcmp (XSTR (SET_DEST (sub), 0), "enabled") == 0)
1357             {
1358               enabled_idx = i;
1359               XSTR (SET_DEST (sub), 0) = "nonce_enabled";
1360             }
1361           break;
1362
1363         default:
1364           gcc_unreachable ();
1365         }
1366     }
1367   if (predicable_idx == -1)
1368     return;
1369
1370   if (!global_changes_made)
1371     {
1372       struct queue_elem *elem;
1373
1374       global_changes_made = true;
1375       add_define_attr ("ce_enabled");
1376       add_define_attr ("nonce_enabled");
1377
1378       for (elem = define_attr_queue; elem ; elem = elem->next)
1379         if (strcmp (XSTR (elem->data, 0), "enabled") == 0)
1380           {
1381             XEXP (elem->data, 2)
1382               = modify_attr_enabled_ce (XEXP (elem->data, 2));
1383           }
1384     }
1385   if (enabled_idx == -1)
1386     return;
1387
1388   new_vec = rtvec_alloc (num_elem + 1);
1389   for (i = 0; i < num_elem; i++)
1390     RTVEC_ELT (new_vec, i) = RTVEC_ELT (vec, i);
1391   val = rtx_alloc (IF_THEN_ELSE);
1392   XEXP (val, 0) = rtx_alloc (EQ_ATTR);
1393   XEXP (val, 1) = rtx_alloc (CONST_STRING);
1394   XEXP (val, 2) = rtx_alloc (CONST_STRING);
1395   XSTR (XEXP (val, 0), 0) = "nonce_enabled";
1396   XSTR (XEXP (val, 0), 1) = "yes";
1397   XSTR (XEXP (val, 1), 0) = "yes";
1398   XSTR (XEXP (val, 2), 0) = "no";
1399   set = rtx_alloc (SET);
1400   SET_DEST (set) = rtx_alloc (ATTR);
1401   XSTR (SET_DEST (set), 0) = "enabled";
1402   SET_SRC (set) = modify_attr_enabled_ce (val);
1403   RTVEC_ELT (new_vec, i) = set;
1404   XVEC (insn, 4) = new_vec;
1405 }
1406
1407 /* As number of constraints is changed after define_subst, we need to
1408    process attributes as well - we need to duplicate them the same way
1409    that we duplicated constraints in original pattern
1410    ELEM is a queue element, containing our rtl-template,
1411    N_DUP - multiplication factor.  */
1412 static void
1413 alter_attrs_for_subst_insn (struct queue_elem * elem, int n_dup)
1414 {
1415   rtvec vec = XVEC (elem->data, 4);
1416   int num_elem;
1417   int i;
1418
1419   if (n_dup < 2 || ! vec)
1420     return;
1421
1422   num_elem = GET_NUM_ELEM (vec);
1423   for (i = num_elem - 1; i >= 0; --i)
1424     {
1425       rtx sub = RTVEC_ELT (vec, i);
1426       switch (GET_CODE (sub))
1427         {
1428         case SET_ATTR:
1429           if (strchr (XSTR (sub, 1), ',') != NULL)
1430             XSTR (sub, 1) = duplicate_alternatives (XSTR (sub, 1), n_dup);
1431             break;
1432
1433         case SET_ATTR_ALTERNATIVE:
1434         case SET:
1435           error_at (elem->loc,
1436                     "%s: `define_subst' does not support attributes "
1437                     "assigned by `set' and `set_attr_alternative'",
1438                     XSTR (elem->data, 0));
1439           return;
1440
1441         default:
1442           gcc_unreachable ();
1443         }
1444     }
1445 }
1446
1447 /* Adjust all of the operand numbers in SRC to match the shift they'll
1448    get from an operand displacement of DISP.  Return a pointer after the
1449    adjusted string.  */
1450
1451 static char *
1452 shift_output_template (char *dest, const char *src, int disp)
1453 {
1454   while (*src)
1455     {
1456       char c = *src++;
1457       *dest++ = c;
1458       if (c == '%')
1459         {
1460           c = *src++;
1461           if (ISDIGIT ((unsigned char) c))
1462             c += disp;
1463           else if (ISALPHA (c))
1464             {
1465               *dest++ = c;
1466               c = *src++ + disp;
1467             }
1468           *dest++ = c;
1469         }
1470     }
1471
1472   return dest;
1473 }
1474
1475 static const char *
1476 alter_output_for_insn (struct queue_elem *ce_elem,
1477                        struct queue_elem *insn_elem,
1478                        int alt, int max_op)
1479 {
1480   const char *ce_out, *insn_out;
1481   char *result, *p;
1482   size_t len, ce_len, insn_len;
1483
1484   /* ??? Could coordinate with genoutput to not duplicate code here.  */
1485
1486   ce_out = XSTR (ce_elem->data, 2);
1487   insn_out = XTMPL (insn_elem->data, 3);
1488   if (!ce_out || *ce_out == '\0')
1489     return insn_out;
1490
1491   ce_len = strlen (ce_out);
1492   insn_len = strlen (insn_out);
1493
1494   if (*insn_out == '*')
1495     /* You must take care of the predicate yourself.  */
1496     return insn_out;
1497
1498   if (*insn_out == '@')
1499     {
1500       len = (ce_len + 1) * alt + insn_len + 1;
1501       p = result = XNEWVEC (char, len);
1502
1503       do
1504         {
1505           do
1506             *p++ = *insn_out++;
1507           while (ISSPACE ((unsigned char) *insn_out));
1508
1509           if (*insn_out != '#')
1510             {
1511               p = shift_output_template (p, ce_out, max_op);
1512               *p++ = ' ';
1513             }
1514
1515           do
1516             *p++ = *insn_out++;
1517           while (*insn_out && *insn_out != '\n');
1518         }
1519       while (*insn_out);
1520       *p = '\0';
1521     }
1522   else
1523     {
1524       len = ce_len + 1 + insn_len + 1;
1525       result = XNEWVEC (char, len);
1526
1527       p = shift_output_template (result, ce_out, max_op);
1528       *p++ = ' ';
1529       memcpy (p, insn_out, insn_len + 1);
1530     }
1531
1532   return result;
1533 }
1534
1535 /* From string STR "a,b,c" produce "a,b,c,a,b,c,a,b,c", i.e. original
1536    string, duplicated N_DUP times.  */
1537
1538 static const char *
1539 duplicate_alternatives (const char * str, int n_dup)
1540 {
1541   int i, len, new_len;
1542   char *result, *sp;
1543   const char *cp;
1544
1545   if (n_dup < 2)
1546     return str;
1547
1548   while (ISSPACE (*str))
1549     str++;
1550
1551   if (*str == '\0')
1552     return str;
1553
1554   cp = str;
1555   len = strlen (str);
1556   new_len = (len + 1) * n_dup;
1557
1558   sp = result = XNEWVEC (char, new_len);
1559
1560   /* Global modifier characters mustn't be duplicated: skip if found.  */
1561   if (*cp == '=' || *cp == '+' || *cp == '%')
1562     {
1563       *sp++ = *cp++;
1564       len--;
1565     }
1566
1567   /* Copy original constraints N_DUP times.  */
1568   for (i = 0; i < n_dup; i++, sp += len+1)
1569     {
1570       memcpy (sp, cp, len);
1571       *(sp+len) = (i == n_dup - 1) ? '\0' : ',';
1572     }
1573
1574   return result;
1575 }
1576
1577 /* From string STR "a,b,c" produce "a,a,a,b,b,b,c,c,c", i.e. string where
1578    each alternative from the original string is duplicated N_DUP times.  */
1579 static const char *
1580 duplicate_each_alternative (const char * str, int n_dup)
1581 {
1582   int i, len, new_len;
1583   char *result, *sp, *ep, *cp;
1584
1585   if (n_dup < 2)
1586     return str;
1587
1588   while (ISSPACE (*str))
1589     str++;
1590
1591   if (*str == '\0')
1592     return str;
1593
1594   cp = xstrdup (str);
1595
1596   new_len = (strlen (cp) + 1) * n_dup;
1597
1598   sp = result = XNEWVEC (char, new_len);
1599
1600   /* Global modifier characters mustn't be duplicated: skip if found.  */
1601   if (*cp == '=' || *cp == '+' || *cp == '%')
1602       *sp++ = *cp++;
1603
1604   do
1605     {
1606       if ((ep = strchr (cp, ',')) != NULL)
1607         *ep++ = '\0';
1608       len = strlen (cp);
1609
1610       /* Copy a constraint N_DUP times.  */
1611       for (i = 0; i < n_dup; i++, sp += len + 1)
1612         {
1613           memcpy (sp, cp, len);
1614           *(sp+len) = (ep == NULL && i == n_dup - 1) ? '\0' : ',';
1615         }
1616
1617       cp = ep;
1618     }
1619   while (cp != NULL);
1620
1621   return result;
1622 }
1623
1624 /* Alter the output of INSN whose pattern was modified by
1625    DEFINE_SUBST.  We must replicate output strings according
1626    to the new number of alternatives ALT in substituted pattern.
1627    If ALT equals 1, output has one alternative or defined by C
1628    code, then output is returned without any changes.  */
1629
1630 static const char *
1631 alter_output_for_subst_insn (rtx insn, int alt)
1632 {
1633   const char *insn_out, *sp ;
1634   char *old_out, *new_out, *cp;
1635   int i, j, new_len;
1636
1637   insn_out = XTMPL (insn, 3);
1638
1639   if (alt < 2 || *insn_out == '*' || *insn_out != '@')
1640     return insn_out;
1641
1642   old_out = XNEWVEC (char, strlen (insn_out)),
1643   sp = insn_out;
1644
1645   while (ISSPACE (*sp) || *sp == '@')
1646     sp++;
1647
1648   for (i = 0; *sp;)
1649     old_out[i++] = *sp++;
1650
1651   new_len = alt * (i + 1) + 1;
1652
1653   new_out = XNEWVEC (char, new_len);
1654   new_out[0] = '@';
1655
1656   for (j = 0, cp = new_out + 1; j < alt; j++, cp += i + 1)
1657     {
1658       memcpy (cp, old_out, i);
1659       *(cp+i) = (j == alt - 1) ? '\0' : '\n';
1660     }
1661
1662   return new_out;
1663 }
1664
1665 /* Replicate insns as appropriate for the given DEFINE_COND_EXEC.  */
1666
1667 static void
1668 process_one_cond_exec (struct queue_elem *ce_elem)
1669 {
1670   struct queue_elem *insn_elem;
1671   for (insn_elem = define_insn_queue; insn_elem ; insn_elem = insn_elem->next)
1672     {
1673       int alternatives, max_operand;
1674       rtx pred, insn, pattern, split;
1675       char *new_name;
1676       int i;
1677
1678       if (! is_predicable (insn_elem))
1679         continue;
1680
1681       alternatives = 1;
1682       max_operand = -1;
1683       collect_insn_data (insn_elem->data, &alternatives, &max_operand);
1684       max_operand += 1;
1685
1686       if (XVECLEN (ce_elem->data, 0) != 1)
1687         {
1688           error_at (ce_elem->loc, "too many patterns in predicate");
1689           return;
1690         }
1691
1692       pred = copy_rtx (XVECEXP (ce_elem->data, 0, 0));
1693       pred = alter_predicate_for_insn (pred, alternatives, max_operand,
1694                                        ce_elem->loc);
1695       if (pred == NULL)
1696         return;
1697
1698       /* Construct a new pattern for the new insn.  */
1699       insn = copy_rtx (insn_elem->data);
1700       new_name = XNEWVAR (char, strlen XSTR (insn_elem->data, 0) + 4);
1701       sprintf (new_name, "*p %s", XSTR (insn_elem->data, 0));
1702       XSTR (insn, 0) = new_name;
1703       pattern = rtx_alloc (COND_EXEC);
1704       XEXP (pattern, 0) = pred;
1705       XEXP (pattern, 1) = add_implicit_parallel (XVEC (insn, 1));
1706       XVEC (insn, 1) = rtvec_alloc (1);
1707       XVECEXP (insn, 1, 0) = pattern;
1708
1709        if (XVEC (ce_elem->data, 3) != NULL)
1710         {
1711           rtvec attributes = rtvec_alloc (XVECLEN (insn, 4)
1712                                           + XVECLEN (ce_elem->data, 3));
1713           int i = 0;
1714           int j = 0;
1715           for (i = 0; i < XVECLEN (insn, 4); i++)
1716             RTVEC_ELT (attributes, i) = XVECEXP (insn, 4, i);
1717
1718           for (j = 0; j < XVECLEN (ce_elem->data, 3); j++, i++)
1719             RTVEC_ELT (attributes, i) = XVECEXP (ce_elem->data, 3, j);
1720
1721           XVEC (insn, 4) = attributes;
1722         }
1723
1724       XSTR (insn, 2) = alter_test_for_insn (ce_elem, insn_elem);
1725       XTMPL (insn, 3) = alter_output_for_insn (ce_elem, insn_elem,
1726                                               alternatives, max_operand);
1727       alter_attrs_for_insn (insn);
1728
1729       /* Put the new pattern on the `other' list so that it
1730          (a) is not reprocessed by other define_cond_exec patterns
1731          (b) appears after all normal define_insn patterns.
1732
1733          ??? B is debatable.  If one has normal insns that match
1734          cond_exec patterns, they will be preferred over these
1735          generated patterns.  Whether this matters in practice, or if
1736          it's a good thing, or whether we should thread these new
1737          patterns into the define_insn chain just after their generator
1738          is something we'll have to experiment with.  */
1739
1740       queue_pattern (insn, &other_tail, insn_elem->loc);
1741
1742       if (!insn_elem->split)
1743         continue;
1744
1745       /* If the original insn came from a define_insn_and_split,
1746          generate a new split to handle the predicated insn.  */
1747       split = copy_rtx (insn_elem->split->data);
1748       /* Predicate the pattern matched by the split.  */
1749       pattern = rtx_alloc (COND_EXEC);
1750       XEXP (pattern, 0) = pred;
1751       XEXP (pattern, 1) = add_implicit_parallel (XVEC (split, 0));
1752       XVEC (split, 0) = rtvec_alloc (1);
1753       XVECEXP (split, 0, 0) = pattern;
1754
1755       /* Predicate all of the insns generated by the split.  */
1756       for (i = 0; i < XVECLEN (split, 2); i++)
1757         {
1758           pattern = rtx_alloc (COND_EXEC);
1759           XEXP (pattern, 0) = pred;
1760           XEXP (pattern, 1) = XVECEXP (split, 2, i);
1761           XVECEXP (split, 2, i) = pattern;
1762         }
1763       /* Add the new split to the queue.  */
1764       queue_pattern (split, &other_tail, insn_elem->split->loc);
1765     }
1766 }
1767
1768 /* Try to apply define_substs to the given ELEM.
1769    Only define_substs, specified via attributes would be applied.
1770    If attribute, requiring define_subst, is set, but no define_subst
1771    was applied, ELEM would be deleted.  */
1772
1773 static void
1774 process_substs_on_one_elem (struct queue_elem *elem,
1775                             struct queue_elem *queue)
1776 {
1777   struct queue_elem *subst_elem;
1778   int i, j, patterns_match;
1779
1780   for (subst_elem = define_subst_queue;
1781        subst_elem; subst_elem = subst_elem->next)
1782     {
1783       int alternatives, alternatives_subst;
1784       rtx subst_pattern;
1785       rtvec subst_pattern_vec;
1786
1787       if (!has_subst_attribute (elem, subst_elem))
1788         continue;
1789
1790       /* Compare original rtl-pattern from define_insn with input
1791          pattern from define_subst.
1792          Also, check if numbers of alternatives are the same in all
1793          match_operands.  */
1794       if (XVECLEN (elem->data, 1) != XVECLEN (subst_elem->data, 1))
1795         continue;
1796       patterns_match = 1;
1797       alternatives = -1;
1798       alternatives_subst = -1;
1799       for (j = 0; j < XVECLEN (elem->data, 1); j++)
1800         {
1801           if (!subst_pattern_match (XVECEXP (elem->data, 1, j),
1802                                     XVECEXP (subst_elem->data, 1, j),
1803                                     subst_elem->loc))
1804             {
1805               patterns_match = 0;
1806               break;
1807             }
1808
1809           if (!get_alternatives_number (XVECEXP (elem->data, 1, j),
1810                                         &alternatives, subst_elem->loc))
1811             {
1812               patterns_match = 0;
1813               break;
1814             }
1815         }
1816
1817       /* Check if numbers of alternatives are the same in all
1818          match_operands in output template of define_subst.  */
1819       for (j = 0; j < XVECLEN (subst_elem->data, 3); j++)
1820         {
1821           if (!get_alternatives_number (XVECEXP (subst_elem->data, 3, j),
1822                                         &alternatives_subst,
1823                                         subst_elem->loc))
1824             {
1825               patterns_match = 0;
1826               break;
1827             }
1828         }
1829
1830       if (!patterns_match)
1831         continue;
1832
1833       /* Clear array in which we save occupied indexes of operands.  */
1834       memset (used_operands_numbers, 0, sizeof (used_operands_numbers));
1835
1836       /* Create a pattern, based on the output one from define_subst.  */
1837       subst_pattern_vec = rtvec_alloc (XVECLEN (subst_elem->data, 3));
1838       for (j = 0; j < XVECLEN (subst_elem->data, 3); j++)
1839         {
1840           subst_pattern = copy_rtx (XVECEXP (subst_elem->data, 3, j));
1841
1842           /* Duplicate constraints in substitute-pattern.  */
1843           subst_pattern = alter_constraints (subst_pattern, alternatives,
1844                                              duplicate_each_alternative);
1845
1846           subst_pattern = adjust_operands_numbers (subst_pattern);
1847
1848           /* Substitute match_dup and match_op_dup in the new pattern and
1849              duplicate constraints.  */
1850           subst_pattern = subst_dup (subst_pattern, alternatives,
1851                                      alternatives_subst);
1852
1853           replace_duplicating_operands_in_pattern (subst_pattern);
1854
1855           /* We don't need any constraints in DEFINE_EXPAND.  */
1856           if (GET_CODE (elem->data) == DEFINE_EXPAND)
1857             remove_constraints (subst_pattern);
1858
1859           RTVEC_ELT (subst_pattern_vec, j) = subst_pattern;
1860         }
1861       XVEC (elem->data, 1) = subst_pattern_vec;
1862
1863       for (i = 0; i < MAX_OPERANDS; i++)
1864           match_operand_entries_in_pattern[i] = NULL;
1865
1866       if (GET_CODE (elem->data) == DEFINE_INSN)
1867         {
1868           XTMPL (elem->data, 3) =
1869             alter_output_for_subst_insn (elem->data, alternatives_subst);
1870           alter_attrs_for_subst_insn (elem, alternatives_subst);
1871         }
1872
1873       /* Recalculate condition, joining conditions from original and
1874          DEFINE_SUBST input patterns.  */
1875       XSTR (elem->data, 2) = join_c_conditions (XSTR (subst_elem->data, 2),
1876                                                 XSTR (elem->data, 2));
1877       /* Mark that subst was applied by changing attribute from "yes"
1878          to "no".  */
1879       change_subst_attribute (elem, subst_elem, subst_false);
1880     }
1881
1882   /* If ELEM contains a subst attribute with value "yes", then we
1883      expected that a subst would be applied, but it wasn't - so,
1884      we need to remove that elementto avoid duplicating.  */
1885   for (subst_elem = define_subst_queue;
1886        subst_elem; subst_elem = subst_elem->next)
1887     {
1888       if (has_subst_attribute (elem, subst_elem))
1889         {
1890           remove_from_queue (elem, &queue);
1891           return;
1892         }
1893     }
1894 }
1895
1896 /* This is a subroutine of mark_operands_used_in_match_dup.
1897    This routine is marks all MATCH_OPERANDs inside PATTERN as occupied.  */
1898 static void
1899 mark_operands_from_match_dup (rtx pattern)
1900 {
1901   const char *fmt;
1902   int i, j, len, opno;
1903
1904   if (GET_CODE (pattern) == MATCH_OPERAND
1905       || GET_CODE (pattern) == MATCH_OPERATOR
1906       || GET_CODE (pattern) == MATCH_PARALLEL)
1907     {
1908       opno = XINT (pattern, 0);
1909       gcc_assert (opno >= 0 && opno < MAX_OPERANDS);
1910       used_operands_numbers [opno] = 1;
1911     }
1912   fmt = GET_RTX_FORMAT (GET_CODE (pattern));
1913   len = GET_RTX_LENGTH (GET_CODE (pattern));
1914   for (i = 0; i < len; i++)
1915     {
1916       switch (fmt[i])
1917         {
1918         case 'e': case 'u':
1919           mark_operands_from_match_dup (XEXP (pattern, i));
1920           break;
1921         case 'E':
1922           for (j = XVECLEN (pattern, i) - 1; j >= 0; --j)
1923             mark_operands_from_match_dup (XVECEXP (pattern, i, j));
1924           break;
1925         }
1926     }
1927 }
1928
1929 /* This is a subroutine of adjust_operands_numbers.
1930    It goes through all expressions in PATTERN and when MATCH_DUP is
1931    met, all MATCH_OPERANDs inside it is marked as occupied.  The
1932    process of marking is done by routin mark_operands_from_match_dup.  */
1933 static void
1934 mark_operands_used_in_match_dup (rtx pattern)
1935 {
1936   const char *fmt;
1937   int i, j, len, opno;
1938
1939   if (GET_CODE (pattern) == MATCH_DUP)
1940     {
1941       opno = XINT (pattern, 0);
1942       gcc_assert (opno >= 0 && opno < MAX_OPERANDS);
1943       mark_operands_from_match_dup (operand_data[opno]);
1944       return;
1945     }
1946   fmt = GET_RTX_FORMAT (GET_CODE (pattern));
1947   len = GET_RTX_LENGTH (GET_CODE (pattern));
1948   for (i = 0; i < len; i++)
1949     {
1950       switch (fmt[i])
1951         {
1952         case 'e': case 'u':
1953           mark_operands_used_in_match_dup (XEXP (pattern, i));
1954           break;
1955         case 'E':
1956           for (j = XVECLEN (pattern, i) - 1; j >= 0; --j)
1957             mark_operands_used_in_match_dup (XVECEXP (pattern, i, j));
1958           break;
1959         }
1960     }
1961 }
1962
1963 /* This is subroutine of renumerate_operands_in_pattern.
1964    It finds first not-occupied operand-index.  */
1965 static int
1966 find_first_unused_number_of_operand ()
1967 {
1968   int i;
1969   for (i = 0; i < MAX_OPERANDS; i++)
1970     if (!used_operands_numbers[i])
1971       return i;
1972   return MAX_OPERANDS;
1973 }
1974
1975 /* This is subroutine of adjust_operands_numbers.
1976    It visits all expressions in PATTERN and assigns not-occupied
1977    operand indexes to MATCH_OPERANDs and MATCH_OPERATORs of this
1978    PATTERN.  */
1979 static void
1980 renumerate_operands_in_pattern (rtx pattern)
1981 {
1982   const char *fmt;
1983   enum rtx_code code;
1984   int i, j, len, new_opno;
1985   code = GET_CODE (pattern);
1986
1987   if (code == MATCH_OPERAND
1988       || code == MATCH_OPERATOR)
1989     {
1990       new_opno = find_first_unused_number_of_operand ();
1991       gcc_assert (new_opno >= 0 && new_opno < MAX_OPERANDS);
1992       XINT (pattern, 0) = new_opno;
1993       used_operands_numbers [new_opno] = 1;
1994     }
1995
1996   fmt = GET_RTX_FORMAT (GET_CODE (pattern));
1997   len = GET_RTX_LENGTH (GET_CODE (pattern));
1998   for (i = 0; i < len; i++)
1999     {
2000       switch (fmt[i])
2001         {
2002         case 'e': case 'u':
2003           renumerate_operands_in_pattern (XEXP (pattern, i));
2004           break;
2005         case 'E':
2006           for (j = XVECLEN (pattern, i) - 1; j >= 0; --j)
2007             renumerate_operands_in_pattern (XVECEXP (pattern, i, j));
2008           break;
2009         }
2010     }
2011 }
2012
2013 /* If output pattern of define_subst contains MATCH_DUP, then this
2014    expression would be replaced with the pattern, matched with
2015    MATCH_OPERAND from input pattern.  This pattern could contain any
2016    number of MATCH_OPERANDs, MATCH_OPERATORs etc., so it's possible
2017    that a MATCH_OPERAND from output_pattern (if any) would have the
2018    same number, as MATCH_OPERAND from copied pattern.  To avoid such
2019    indexes overlapping, we assign new indexes to MATCH_OPERANDs,
2020    laying in the output pattern outside of MATCH_DUPs.  */
2021 static rtx
2022 adjust_operands_numbers (rtx pattern)
2023 {
2024   mark_operands_used_in_match_dup (pattern);
2025
2026   renumerate_operands_in_pattern (pattern);
2027
2028   return pattern;
2029 }
2030
2031 /* Generate RTL expression
2032    (match_dup OPNO)
2033    */
2034 static rtx
2035 generate_match_dup (int opno)
2036 {
2037   rtx return_rtx = rtx_alloc (MATCH_DUP);
2038   PUT_CODE (return_rtx, MATCH_DUP);
2039   XINT (return_rtx, 0) = opno;
2040   return return_rtx;
2041 }
2042
2043 /* This routine checks all match_operands in PATTERN and if some of
2044    have the same index, it replaces all of them except the first one  to
2045    match_dup.
2046    Usually, match_operands with the same indexes are forbidden, but
2047    after define_subst copy an RTL-expression from original template,
2048    indexes of existed and just-copied match_operands could coincide.
2049    To fix it, we replace one of them with match_dup.  */
2050 static rtx
2051 replace_duplicating_operands_in_pattern (rtx pattern)
2052 {
2053   const char *fmt;
2054   int i, j, len, opno;
2055   rtx mdup;
2056
2057   if (GET_CODE (pattern) == MATCH_OPERAND)
2058     {
2059       opno = XINT (pattern, 0);
2060       gcc_assert (opno >= 0 && opno < MAX_OPERANDS);
2061       if (match_operand_entries_in_pattern[opno] == NULL)
2062         {
2063           match_operand_entries_in_pattern[opno] = pattern;
2064           return NULL;
2065         }
2066       else
2067         {
2068           /* Compare predicates before replacing with match_dup.  */
2069           if (strcmp (XSTR (pattern, 1),
2070                       XSTR (match_operand_entries_in_pattern[opno], 1)))
2071             {
2072               error ("duplicated match_operands with different predicates were"
2073                      " found.");
2074               return NULL;
2075             }
2076           return generate_match_dup (opno);
2077         }
2078     }
2079   fmt = GET_RTX_FORMAT (GET_CODE (pattern));
2080   len = GET_RTX_LENGTH (GET_CODE (pattern));
2081   for (i = 0; i < len; i++)
2082     {
2083       switch (fmt[i])
2084         {
2085         case 'e': case 'u':
2086           mdup = replace_duplicating_operands_in_pattern (XEXP (pattern, i));
2087           if (mdup)
2088             XEXP (pattern, i) = mdup;
2089           break;
2090         case 'E':
2091           for (j = XVECLEN (pattern, i) - 1; j >= 0; --j)
2092             {
2093               mdup =
2094                 replace_duplicating_operands_in_pattern (XVECEXP
2095                                                          (pattern, i, j));
2096               if (mdup)
2097                 XVECEXP (pattern, i, j) = mdup;
2098             }
2099           break;
2100         }
2101     }
2102   return NULL;
2103 }
2104
2105 /* The routine modifies given input PATTERN of define_subst, replacing
2106    MATCH_DUP and MATCH_OP_DUP with operands from define_insn original
2107    pattern, whose operands are stored in OPERAND_DATA array.
2108    It also duplicates constraints in operands - constraints from
2109    define_insn operands are duplicated N_SUBST_ALT times, constraints
2110    from define_subst operands are duplicated N_ALT times.
2111    After the duplication, returned output rtl-pattern contains every
2112    combination of input constraints Vs constraints from define_subst
2113    output.  */
2114 static rtx
2115 subst_dup (rtx pattern, int n_alt, int n_subst_alt)
2116 {
2117   const char *fmt;
2118   enum rtx_code code;
2119   int i, j, len, opno;
2120
2121   code = GET_CODE (pattern);
2122   switch (code)
2123     {
2124     case MATCH_DUP:
2125     case MATCH_OP_DUP:
2126       opno = XINT (pattern, 0);
2127
2128       gcc_assert (opno >= 0 && opno < MAX_OPERANDS);
2129
2130       if (operand_data[opno])
2131         {
2132           pattern = copy_rtx (operand_data[opno]);
2133
2134           /* Duplicate constraints.  */
2135           pattern = alter_constraints (pattern, n_subst_alt,
2136                                        duplicate_alternatives);
2137         }
2138       break;
2139
2140     default:
2141       break;
2142     }
2143
2144   fmt = GET_RTX_FORMAT (GET_CODE (pattern));
2145   len = GET_RTX_LENGTH (GET_CODE (pattern));
2146   for (i = 0; i < len; i++)
2147     {
2148       switch (fmt[i])
2149         {
2150         case 'e': case 'u':
2151           if (code != MATCH_DUP && code != MATCH_OP_DUP)
2152             XEXP (pattern, i) = subst_dup (XEXP (pattern, i),
2153                                            n_alt, n_subst_alt);
2154           break;
2155         case 'V':
2156           if (XVEC (pattern, i) == NULL)
2157             break;
2158         case 'E':
2159           if (code != MATCH_DUP && code != MATCH_OP_DUP)
2160             for (j = XVECLEN (pattern, i) - 1; j >= 0; --j)
2161               XVECEXP (pattern, i, j) = subst_dup (XVECEXP (pattern, i, j),
2162                                                    n_alt, n_subst_alt);
2163           break;
2164
2165         case 'i': case 'r': case 'w': case '0': case 's': case 'S': case 'T':
2166           break;
2167
2168         default:
2169           gcc_unreachable ();
2170         }
2171     }
2172   return pattern;
2173 }
2174
2175 /* If we have any DEFINE_COND_EXEC patterns, expand the DEFINE_INSN
2176    patterns appropriately.  */
2177
2178 static void
2179 process_define_cond_exec (void)
2180 {
2181   struct queue_elem *elem;
2182
2183   identify_predicable_attribute ();
2184   if (have_error)
2185     return;
2186
2187   for (elem = define_cond_exec_queue; elem ; elem = elem->next)
2188     process_one_cond_exec (elem);
2189 }
2190
2191 /* If we have any DEFINE_SUBST patterns, expand DEFINE_INSN and
2192    DEFINE_EXPAND patterns appropriately.  */
2193
2194 static void
2195 process_define_subst (void)
2196 {
2197   struct queue_elem *elem, *elem_attr;
2198
2199   /* Check if each define_subst has corresponding define_subst_attr.  */
2200   for (elem = define_subst_queue; elem ; elem = elem->next)
2201     {
2202       for (elem_attr = define_subst_attr_queue;
2203            elem_attr;
2204            elem_attr = elem_attr->next)
2205         if (strcmp (XSTR (elem->data, 0), XSTR (elem_attr->data, 1)) == 0)
2206             goto found;
2207
2208       error_at (elem->loc,
2209                 "%s: `define_subst' must have at least one "
2210                 "corresponding `define_subst_attr'",
2211                 XSTR (elem->data, 0));
2212       return;
2213
2214       found:
2215         continue;
2216     }
2217
2218   for (elem = define_insn_queue; elem ; elem = elem->next)
2219     process_substs_on_one_elem (elem, define_insn_queue);
2220   for (elem = other_queue; elem ; elem = elem->next)
2221     {
2222       if (GET_CODE (elem->data) != DEFINE_EXPAND)
2223         continue;
2224       process_substs_on_one_elem (elem, other_queue);
2225     }
2226 }
2227 \f
2228 /* A read_md_files callback for reading an rtx.  */
2229
2230 static void
2231 rtx_handle_directive (file_location loc, const char *rtx_name)
2232 {
2233   auto_vec<rtx, 32> subrtxs;
2234   if (!read_rtx (rtx_name, &subrtxs))
2235     return;
2236
2237   rtx x;
2238   unsigned int i;
2239   FOR_EACH_VEC_ELT (subrtxs, i, x)
2240     process_rtx (x, loc);
2241 }
2242
2243 /* Comparison function for the mnemonic hash table.  */
2244
2245 static int
2246 htab_eq_string (const void *s1, const void *s2)
2247 {
2248   return strcmp ((const char*)s1, (const char*)s2) == 0;
2249 }
2250
2251 /* Add mnemonic STR with length LEN to the mnemonic hash table
2252    MNEMONIC_HTAB.  A trailing zero end character is appendend to STR
2253    and a permanent heap copy of STR is created.  */
2254
2255 static void
2256 add_mnemonic_string (htab_t mnemonic_htab, const char *str, int len)
2257 {
2258   char *new_str;
2259   void **slot;
2260   char *str_zero = (char*)alloca (len + 1);
2261
2262   memcpy (str_zero, str, len);
2263   str_zero[len] = '\0';
2264
2265   slot = htab_find_slot (mnemonic_htab, str_zero, INSERT);
2266
2267   if (*slot)
2268     return;
2269
2270   /* Not found; create a permanent copy and add it to the hash table.  */
2271   new_str = XNEWVAR (char, len + 1);
2272   memcpy (new_str, str_zero, len + 1);
2273   *slot = new_str;
2274 }
2275
2276 /* Scan INSN for mnemonic strings and add them to the mnemonic hash
2277    table in MNEMONIC_HTAB.
2278
2279    The mnemonics cannot be found if they are emitted using C code.
2280
2281    If a mnemonic string contains ';' or a newline the string assumed
2282    to consist of more than a single instruction.  The attribute value
2283    will then be set to the user defined default value.  */
2284
2285 static void
2286 gen_mnemonic_setattr (htab_t mnemonic_htab, rtx insn)
2287 {
2288   const char *template_code, *cp;
2289   int i;
2290   int vec_len;
2291   rtx set_attr;
2292   char *attr_name;
2293   rtvec new_vec;
2294
2295   template_code = XTMPL (insn, 3);
2296
2297   /* Skip patterns which use C code to emit the template.  */
2298   if (template_code[0] == '*')
2299     return;
2300
2301   if (template_code[0] == '@')
2302     cp = &template_code[1];
2303   else
2304     cp = &template_code[0];
2305
2306   for (i = 0; *cp; )
2307     {
2308       const char *ep, *sp;
2309       int size = 0;
2310
2311       while (ISSPACE (*cp))
2312         cp++;
2313
2314       for (ep = sp = cp; !IS_VSPACE (*ep) && *ep != '\0'; ++ep)
2315         if (!ISSPACE (*ep))
2316           sp = ep + 1;
2317
2318       if (i > 0)
2319         obstack_1grow (&string_obstack, ',');
2320
2321       while (cp < sp && ((*cp >= '0' && *cp <= '9')
2322                          || (*cp >= 'a' && *cp <= 'z')))
2323
2324         {
2325           obstack_1grow (&string_obstack, *cp);
2326           cp++;
2327           size++;
2328         }
2329
2330       while (cp < sp)
2331         {
2332           if (*cp == ';' || (*cp == '\\' && cp[1] == 'n'))
2333             {
2334               /* Don't set a value if there are more than one
2335                  instruction in the string.  */
2336               obstack_next_free (&string_obstack) =
2337                 obstack_next_free (&string_obstack) - size;
2338               size = 0;
2339
2340               cp = sp;
2341               break;
2342             }
2343           cp++;
2344         }
2345       if (size == 0)
2346         obstack_1grow (&string_obstack, '*');
2347       else
2348         add_mnemonic_string (mnemonic_htab,
2349                              obstack_next_free (&string_obstack) - size,
2350                              size);
2351       i++;
2352     }
2353
2354   /* An insn definition might emit an empty string.  */
2355   if (obstack_object_size (&string_obstack) == 0)
2356     return;
2357
2358   obstack_1grow (&string_obstack, '\0');
2359
2360   set_attr = rtx_alloc (SET_ATTR);
2361   XSTR (set_attr, 1) = XOBFINISH (&string_obstack, char *);
2362   attr_name = XNEWVAR (char, strlen (MNEMONIC_ATTR_NAME) + 1);
2363   strcpy (attr_name, MNEMONIC_ATTR_NAME);
2364   XSTR (set_attr, 0) = attr_name;
2365
2366   if (!XVEC (insn, 4))
2367     vec_len = 0;
2368   else
2369     vec_len = XVECLEN (insn, 4);
2370
2371   new_vec = rtvec_alloc (vec_len + 1);
2372   for (i = 0; i < vec_len; i++)
2373     RTVEC_ELT (new_vec, i) = XVECEXP (insn, 4, i);
2374   RTVEC_ELT (new_vec, vec_len) = set_attr;
2375   XVEC (insn, 4) = new_vec;
2376 }
2377
2378 /* This function is called for the elements in the mnemonic hashtable
2379    and generates a comma separated list of the mnemonics.  */
2380
2381 static int
2382 mnemonic_htab_callback (void **slot, void *info ATTRIBUTE_UNUSED)
2383 {
2384   obstack_grow (&string_obstack, (char*)*slot, strlen ((char*)*slot));
2385   obstack_1grow (&string_obstack, ',');
2386   return 1;
2387 }
2388
2389 /* Generate (set_attr "mnemonic" "..") RTXs and append them to every
2390    insn definition in case the back end requests it by defining the
2391    mnemonic attribute.  The values for the attribute will be extracted
2392    from the output patterns of the insn definitions as far as
2393    possible.  */
2394
2395 static void
2396 gen_mnemonic_attr (void)
2397 {
2398   struct queue_elem *elem;
2399   rtx mnemonic_attr = NULL;
2400   htab_t mnemonic_htab;
2401   const char *str, *p;
2402   int i;
2403
2404   if (have_error)
2405     return;
2406
2407   /* Look for the DEFINE_ATTR for `mnemonic'.  */
2408   for (elem = define_attr_queue; elem != *define_attr_tail; elem = elem->next)
2409     if (GET_CODE (elem->data) == DEFINE_ATTR
2410         && strcmp (XSTR (elem->data, 0), MNEMONIC_ATTR_NAME) == 0)
2411       {
2412         mnemonic_attr = elem->data;
2413         break;
2414       }
2415
2416   /* A (define_attr "mnemonic" "...") indicates that the back-end
2417      wants a mnemonic attribute to be generated.  */
2418   if (!mnemonic_attr)
2419     return;
2420
2421   mnemonic_htab = htab_create_alloc (MNEMONIC_HTAB_SIZE, htab_hash_string,
2422                                      htab_eq_string, 0, xcalloc, free);
2423
2424   for (elem = define_insn_queue; elem; elem = elem->next)
2425     {
2426       rtx insn = elem->data;
2427       bool found = false;
2428
2429       /* Check if the insn definition already has
2430          (set_attr "mnemonic" ...) or (set (attr "mnemonic") ...).  */
2431       if (XVEC (insn, 4))
2432         for (i = 0; i < XVECLEN (insn, 4); i++)
2433           {
2434             rtx set_attr = XVECEXP (insn, 4, i);
2435
2436             switch (GET_CODE (set_attr))
2437               {
2438               case SET_ATTR:
2439               case SET_ATTR_ALTERNATIVE:
2440                 if (strcmp (XSTR (set_attr, 0), MNEMONIC_ATTR_NAME) == 0)
2441                   found = true;
2442                 break;
2443               case SET:
2444                 if (GET_CODE (SET_DEST (set_attr)) == ATTR
2445                     && strcmp (XSTR (SET_DEST (set_attr), 0),
2446                                MNEMONIC_ATTR_NAME) == 0)
2447                   found = true;
2448                 break;
2449               default:
2450                 break;
2451               }
2452           }
2453
2454       if (!found)
2455         gen_mnemonic_setattr (mnemonic_htab, insn);
2456     }
2457
2458   /* Add the user defined values to the hash table.  */
2459   str = XSTR (mnemonic_attr, 1);
2460   while ((p = scan_comma_elt (&str)) != NULL)
2461     add_mnemonic_string (mnemonic_htab, p, str - p);
2462
2463   htab_traverse (mnemonic_htab, mnemonic_htab_callback, NULL);
2464
2465   /* Replace the last ',' with the zero end character.  */
2466   *((char *)obstack_next_free (&string_obstack) - 1) = '\0';
2467   XSTR (mnemonic_attr, 1) = XOBFINISH (&string_obstack, char *);
2468 }
2469
2470 /* Check if there are DEFINE_ATTRs with the same name.  */
2471 static void
2472 check_define_attr_duplicates ()
2473 {
2474   struct queue_elem *elem;
2475   htab_t attr_htab;
2476   char * attr_name;
2477   void **slot;
2478
2479   attr_htab = htab_create (500, htab_hash_string, htab_eq_string, NULL);
2480
2481   for (elem = define_attr_queue; elem; elem = elem->next)
2482     {
2483       attr_name = xstrdup (XSTR (elem->data, 0));
2484
2485       slot = htab_find_slot (attr_htab, attr_name, INSERT);
2486
2487       /* Duplicate.  */
2488       if (*slot)
2489         {
2490           error_at (elem->loc, "redefinition of attribute '%s'", attr_name);
2491           htab_delete (attr_htab);
2492           return;
2493         }
2494
2495       *slot = attr_name;
2496     }
2497
2498   htab_delete (attr_htab);
2499 }
2500
2501 /* The entry point for initializing the reader.  */
2502
2503 bool
2504 init_rtx_reader_args_cb (int argc, char **argv,
2505                          bool (*parse_opt) (const char *))
2506 {
2507   /* Prepare to read input.  */
2508   condition_table = htab_create (500, hash_c_test, cmp_c_test, NULL);
2509   init_predicate_table ();
2510   obstack_init (rtl_obstack);
2511
2512   /* Start at 1, to make 0 available for CODE_FOR_nothing.  */
2513   insn_sequence_num = 1;
2514
2515   /* These sequences are not used as indices, so can start at 1 also.  */
2516   split_sequence_num = 1;
2517   peephole2_sequence_num = 1;
2518
2519   read_md_files (argc, argv, parse_opt, rtx_handle_directive);
2520
2521   if (define_attr_queue != NULL)
2522     check_define_attr_duplicates ();
2523
2524   /* Process define_cond_exec patterns.  */
2525   if (define_cond_exec_queue != NULL)
2526     process_define_cond_exec ();
2527
2528   /* Process define_subst patterns.  */
2529   if (define_subst_queue != NULL)
2530     process_define_subst ();
2531
2532   if (define_attr_queue != NULL)
2533     gen_mnemonic_attr ();
2534
2535   return !have_error;
2536 }
2537
2538 /* Programs that don't have their own options can use this entry point
2539    instead.  */
2540 bool
2541 init_rtx_reader_args (int argc, char **argv)
2542 {
2543   return init_rtx_reader_args_cb (argc, argv, 0);
2544 }
2545 \f
2546 /* Try to read a single rtx from the file.  Return true on success,
2547    describing it in *INFO.  */
2548
2549 bool
2550 read_md_rtx (md_rtx_info *info)
2551 {
2552   int truth, *counter;
2553   rtx def;
2554
2555   /* Discard insn patterns which we know can never match (because
2556      their C test is provably always false).  If insn_elision is
2557      false, our caller needs to see all the patterns.  Note that the
2558      elided patterns are never counted by the sequence numbering; it
2559      is the caller's responsibility, when insn_elision is false, not
2560      to use elided pattern numbers for anything.  */
2561   do
2562     {
2563       struct queue_elem **queue, *elem;
2564
2565       /* Read all patterns from a given queue before moving on to the next.  */
2566       if (define_attr_queue != NULL)
2567         queue = &define_attr_queue;
2568       else if (define_pred_queue != NULL)
2569         queue = &define_pred_queue;
2570       else if (define_insn_queue != NULL)
2571         queue = &define_insn_queue;
2572       else if (other_queue != NULL)
2573         queue = &other_queue;
2574       else
2575         return false;
2576
2577       elem = *queue;
2578       *queue = elem->next;
2579       def = elem->data;
2580       info->def = def;
2581       info->loc = elem->loc;
2582       free (elem);
2583
2584       truth = maybe_eval_c_test (get_c_test (def));
2585     }
2586   while (truth == 0 && insn_elision);
2587
2588   /* Perform code-specific processing and pick the appropriate sequence
2589      number counter.  */
2590   switch (GET_CODE (def))
2591     {
2592     case DEFINE_INSN:
2593     case DEFINE_EXPAND:
2594       /* insn_sequence_num is used here so the name table will match caller's
2595          idea of insn numbering, whether or not elision is active.  */
2596       record_insn_name (insn_sequence_num, XSTR (def, 0));
2597
2598       /* Fall through.  */
2599     case DEFINE_PEEPHOLE:
2600       counter = &insn_sequence_num;
2601       break;
2602
2603     case DEFINE_SPLIT:
2604       counter = &split_sequence_num;
2605       break;
2606
2607     case DEFINE_PEEPHOLE2:
2608       counter = &peephole2_sequence_num;
2609       break;
2610
2611     default:
2612       counter = NULL;
2613       break;
2614     }
2615
2616   if (counter)
2617     {
2618       info->index = *counter;
2619       if (truth != 0)
2620         *counter += 1;
2621     }
2622   else
2623     info->index = -1;
2624
2625   if (!rtx_locs)
2626     rtx_locs = new hash_map <rtx, file_location>;
2627   rtx_locs->put (info->def, info->loc);
2628
2629   return true;
2630 }
2631
2632 /* Return the file location of DEFINE_* rtx X, which was previously
2633    returned by read_md_rtx.  */
2634 file_location
2635 get_file_location (rtx x)
2636 {
2637   gcc_assert (rtx_locs);
2638   file_location *entry = rtx_locs->get (x);
2639   gcc_assert (entry);
2640   return *entry;
2641 }
2642
2643 /* Return the number of possible INSN_CODEs.  Only meaningful once the
2644    whole file has been processed.  */
2645 unsigned int
2646 get_num_insn_codes ()
2647 {
2648   return insn_sequence_num;
2649 }
2650
2651 /* Return the C test that says whether definition rtx DEF can be used,
2652    or "" if it can be used unconditionally.  */
2653
2654 const char *
2655 get_c_test (rtx x)
2656 {
2657   switch (GET_CODE (x))
2658     {
2659     case DEFINE_INSN:
2660     case DEFINE_EXPAND:
2661     case DEFINE_SUBST:
2662       return XSTR (x, 2);
2663
2664     case DEFINE_SPLIT:
2665     case DEFINE_PEEPHOLE:
2666     case DEFINE_PEEPHOLE2:
2667       return XSTR (x, 1);
2668
2669     default:
2670       return "";
2671     }
2672 }
2673
2674 /* Helper functions for insn elision.  */
2675
2676 /* Compute a hash function of a c_test structure, which is keyed
2677    by its ->expr field.  */
2678 hashval_t
2679 hash_c_test (const void *x)
2680 {
2681   const struct c_test *a = (const struct c_test *) x;
2682   const unsigned char *base, *s = (const unsigned char *) a->expr;
2683   hashval_t hash;
2684   unsigned char c;
2685   unsigned int len;
2686
2687   base = s;
2688   hash = 0;
2689
2690   while ((c = *s++) != '\0')
2691     {
2692       hash += c + (c << 17);
2693       hash ^= hash >> 2;
2694     }
2695
2696   len = s - base;
2697   hash += len + (len << 17);
2698   hash ^= hash >> 2;
2699
2700   return hash;
2701 }
2702
2703 /* Compare two c_test expression structures.  */
2704 int
2705 cmp_c_test (const void *x, const void *y)
2706 {
2707   const struct c_test *a = (const struct c_test *) x;
2708   const struct c_test *b = (const struct c_test *) y;
2709
2710   return !strcmp (a->expr, b->expr);
2711 }
2712
2713 /* Given a string representing a C test expression, look it up in the
2714    condition_table and report whether or not its value is known
2715    at compile time.  Returns a tristate: 1 for known true, 0 for
2716    known false, -1 for unknown.  */
2717 int
2718 maybe_eval_c_test (const char *expr)
2719 {
2720   const struct c_test *test;
2721   struct c_test dummy;
2722
2723   if (expr[0] == 0)
2724     return 1;
2725
2726   dummy.expr = expr;
2727   test = (const struct c_test *)htab_find (condition_table, &dummy);
2728   if (!test)
2729     return -1;
2730   return test->value;
2731 }
2732
2733 /* Record the C test expression EXPR in the condition_table, with
2734    value VAL.  Duplicates clobber previous entries.  */
2735
2736 void
2737 add_c_test (const char *expr, int value)
2738 {
2739   struct c_test *test;
2740
2741   if (expr[0] == 0)
2742     return;
2743
2744   test = XNEW (struct c_test);
2745   test->expr = expr;
2746   test->value = value;
2747
2748   *(htab_find_slot (condition_table, test, INSERT)) = test;
2749 }
2750
2751 /* For every C test, call CALLBACK with two arguments: a pointer to
2752    the condition structure and INFO.  Stops when CALLBACK returns zero.  */
2753 void
2754 traverse_c_tests (htab_trav callback, void *info)
2755 {
2756   if (condition_table)
2757     htab_traverse (condition_table, callback, info);
2758 }
2759
2760 /* Helper functions for define_predicate and define_special_predicate
2761    processing.  Shared between genrecog.c and genpreds.c.  */
2762
2763 static htab_t predicate_table;
2764 struct pred_data *first_predicate;
2765 static struct pred_data **last_predicate = &first_predicate;
2766
2767 static hashval_t
2768 hash_struct_pred_data (const void *ptr)
2769 {
2770   return htab_hash_string (((const struct pred_data *)ptr)->name);
2771 }
2772
2773 static int
2774 eq_struct_pred_data (const void *a, const void *b)
2775 {
2776   return !strcmp (((const struct pred_data *)a)->name,
2777                   ((const struct pred_data *)b)->name);
2778 }
2779
2780 struct pred_data *
2781 lookup_predicate (const char *name)
2782 {
2783   struct pred_data key;
2784   key.name = name;
2785   return (struct pred_data *) htab_find (predicate_table, &key);
2786 }
2787
2788 /* Record that predicate PRED can accept CODE.  */
2789
2790 void
2791 add_predicate_code (struct pred_data *pred, enum rtx_code code)
2792 {
2793   if (!pred->codes[code])
2794     {
2795       pred->num_codes++;
2796       pred->codes[code] = true;
2797
2798       if (GET_RTX_CLASS (code) != RTX_CONST_OBJ)
2799         pred->allows_non_const = true;
2800
2801       if (code != REG
2802           && code != SUBREG
2803           && code != MEM
2804           && code != CONCAT
2805           && code != PARALLEL
2806           && code != STRICT_LOW_PART
2807           && code != SCRATCH)
2808         pred->allows_non_lvalue = true;
2809
2810       if (pred->num_codes == 1)
2811         pred->singleton = code;
2812       else if (pred->num_codes == 2)
2813         pred->singleton = UNKNOWN;
2814     }
2815 }
2816
2817 void
2818 add_predicate (struct pred_data *pred)
2819 {
2820   void **slot = htab_find_slot (predicate_table, pred, INSERT);
2821   if (*slot)
2822     {
2823       error ("duplicate predicate definition for '%s'", pred->name);
2824       return;
2825     }
2826   *slot = pred;
2827   *last_predicate = pred;
2828   last_predicate = &pred->next;
2829 }
2830
2831 /* This array gives the initial content of the predicate table.  It
2832    has entries for all predicates defined in recog.c.  */
2833
2834 struct std_pred_table
2835 {
2836   const char *name;
2837   bool special;
2838   bool allows_const_p;
2839   RTX_CODE codes[NUM_RTX_CODE];
2840 };
2841
2842 static const struct std_pred_table std_preds[] = {
2843   {"general_operand", false, true, {SUBREG, REG, MEM}},
2844   {"address_operand", true, true, {SUBREG, REG, MEM, PLUS, MINUS, MULT,
2845                                    ZERO_EXTEND, SIGN_EXTEND, AND}},
2846   {"register_operand", false, false, {SUBREG, REG}},
2847   {"pmode_register_operand", true, false, {SUBREG, REG}},
2848   {"scratch_operand", false, false, {SCRATCH, REG}},
2849   {"immediate_operand", false, true, {UNKNOWN}},
2850   {"const_int_operand", false, false, {CONST_INT}},
2851 #if TARGET_SUPPORTS_WIDE_INT
2852   {"const_scalar_int_operand", false, false, {CONST_INT, CONST_WIDE_INT}},
2853   {"const_double_operand", false, false, {CONST_DOUBLE}},
2854 #else
2855   {"const_double_operand", false, false, {CONST_INT, CONST_DOUBLE}},
2856 #endif
2857   {"nonimmediate_operand", false, false, {SUBREG, REG, MEM}},
2858   {"nonmemory_operand", false, true, {SUBREG, REG}},
2859   {"push_operand", false, false, {MEM}},
2860   {"pop_operand", false, false, {MEM}},
2861   {"memory_operand", false, false, {SUBREG, MEM}},
2862   {"indirect_operand", false, false, {SUBREG, MEM}},
2863   {"ordered_comparison_operator", false, false, {EQ, NE,
2864                                                  LE, LT, GE, GT,
2865                                                  LEU, LTU, GEU, GTU}},
2866   {"comparison_operator", false, false, {EQ, NE,
2867                                          LE, LT, GE, GT,
2868                                          LEU, LTU, GEU, GTU,
2869                                          UNORDERED, ORDERED,
2870                                          UNEQ, UNGE, UNGT,
2871                                          UNLE, UNLT, LTGT}}
2872 };
2873 #define NUM_KNOWN_STD_PREDS ARRAY_SIZE (std_preds)
2874
2875 /* Initialize the table of predicate definitions, starting with
2876    the information we have on generic predicates.  */
2877
2878 static void
2879 init_predicate_table (void)
2880 {
2881   size_t i, j;
2882   struct pred_data *pred;
2883
2884   predicate_table = htab_create_alloc (37, hash_struct_pred_data,
2885                                        eq_struct_pred_data, 0,
2886                                        xcalloc, free);
2887
2888   for (i = 0; i < NUM_KNOWN_STD_PREDS; i++)
2889     {
2890       pred = XCNEW (struct pred_data);
2891       pred->name = std_preds[i].name;
2892       pred->special = std_preds[i].special;
2893
2894       for (j = 0; std_preds[i].codes[j] != 0; j++)
2895         add_predicate_code (pred, std_preds[i].codes[j]);
2896
2897       if (std_preds[i].allows_const_p)
2898         for (j = 0; j < NUM_RTX_CODE; j++)
2899           if (GET_RTX_CLASS (j) == RTX_CONST_OBJ)
2900             add_predicate_code (pred, (enum rtx_code) j);
2901
2902       add_predicate (pred);
2903     }
2904 }
2905 \f
2906 /* These functions allow linkage with print-rtl.c.  Also, some generators
2907    like to annotate their output with insn names.  */
2908
2909 /* Holds an array of names indexed by insn_code_number.  */
2910 static char **insn_name_ptr = 0;
2911 static int insn_name_ptr_size = 0;
2912
2913 const char *
2914 get_insn_name (int code)
2915 {
2916   if (code < insn_name_ptr_size)
2917     return insn_name_ptr[code];
2918   else
2919     return NULL;
2920 }
2921
2922 static void
2923 record_insn_name (int code, const char *name)
2924 {
2925   static const char *last_real_name = "insn";
2926   static int last_real_code = 0;
2927   char *new_name;
2928
2929   if (insn_name_ptr_size <= code)
2930     {
2931       int new_size;
2932       new_size = (insn_name_ptr_size ? insn_name_ptr_size * 2 : 512);
2933       insn_name_ptr = XRESIZEVEC (char *, insn_name_ptr, new_size);
2934       memset (insn_name_ptr + insn_name_ptr_size, 0,
2935               sizeof (char *) * (new_size - insn_name_ptr_size));
2936       insn_name_ptr_size = new_size;
2937     }
2938
2939   if (!name || name[0] == '\0')
2940     {
2941       new_name = XNEWVAR (char, strlen (last_real_name) + 10);
2942       sprintf (new_name, "%s+%d", last_real_name, code - last_real_code);
2943     }
2944   else
2945     {
2946       last_real_name = new_name = xstrdup (name);
2947       last_real_code = code;
2948     }
2949
2950   insn_name_ptr[code] = new_name;
2951 }
2952 \f
2953 /* Make STATS describe the operands that appear in rtx X.  */
2954
2955 static void
2956 get_pattern_stats_1 (struct pattern_stats *stats, rtx x)
2957 {
2958   RTX_CODE code;
2959   int i;
2960   int len;
2961   const char *fmt;
2962
2963   if (x == NULL_RTX)
2964     return;
2965
2966   code = GET_CODE (x);
2967   switch (code)
2968     {
2969     case MATCH_OPERAND:
2970     case MATCH_OPERATOR:
2971     case MATCH_PARALLEL:
2972       stats->max_opno = MAX (stats->max_opno, XINT (x, 0));
2973       break;
2974
2975     case MATCH_DUP:
2976     case MATCH_OP_DUP:
2977     case MATCH_PAR_DUP:
2978       stats->num_dups++;
2979       stats->max_dup_opno = MAX (stats->max_dup_opno, XINT (x, 0));
2980       break;
2981
2982     case MATCH_SCRATCH:
2983       stats->max_scratch_opno = MAX (stats->max_scratch_opno, XINT (x, 0));
2984       break;
2985
2986     default:
2987       break;
2988     }
2989
2990   fmt = GET_RTX_FORMAT (code);
2991   len = GET_RTX_LENGTH (code);
2992   for (i = 0; i < len; i++)
2993     {
2994       if (fmt[i] == 'e' || fmt[i] == 'u')
2995         get_pattern_stats_1 (stats, XEXP (x, i));
2996       else if (fmt[i] == 'E')
2997         {
2998           int j;
2999           for (j = 0; j < XVECLEN (x, i); j++)
3000             get_pattern_stats_1 (stats, XVECEXP (x, i, j));
3001         }
3002     }
3003 }
3004
3005 /* Make STATS describe the operands that appear in instruction pattern
3006    PATTERN.  */
3007
3008 void
3009 get_pattern_stats (struct pattern_stats *stats, rtvec pattern)
3010 {
3011   int i, len;
3012
3013   stats->max_opno = -1;
3014   stats->max_dup_opno = -1;
3015   stats->max_scratch_opno = -1;
3016   stats->num_dups = 0;
3017
3018   len = GET_NUM_ELEM (pattern);
3019   for (i = 0; i < len; i++)
3020     get_pattern_stats_1 (stats, RTVEC_ELT (pattern, i));
3021
3022   stats->num_generator_args = stats->max_opno + 1;
3023   stats->num_insn_operands = MAX (stats->max_opno,
3024                                   stats->max_scratch_opno) + 1;
3025   stats->num_operand_vars = MAX (stats->max_opno,
3026                                   MAX (stats->max_dup_opno,
3027                                        stats->max_scratch_opno)) + 1;
3028 }
3029
3030 /* Return the emit_* function that should be used for pattern X, or NULL
3031    if we can't pick a particular type at compile time and should instead
3032    fall back to "emit".  */
3033
3034 const char *
3035 get_emit_function (rtx x)
3036 {
3037   switch (classify_insn (x))
3038     {
3039     case INSN:
3040       return "emit_insn";
3041
3042     case CALL_INSN:
3043       return "emit_call_insn";
3044
3045     case JUMP_INSN:
3046       return "emit_jump_insn";
3047
3048     case UNKNOWN:
3049       return NULL;
3050
3051     default:
3052       gcc_unreachable ();
3053     }
3054 }
3055
3056 /* Return true if we must emit a barrier after pattern X.  */
3057
3058 bool
3059 needs_barrier_p (rtx x)
3060 {
3061   return (GET_CODE (x) == SET
3062           && GET_CODE (SET_DEST (x)) == PC
3063           && GET_CODE (SET_SRC (x)) == LABEL_REF);
3064 }