gcc/gensupport.c

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