gcc/gensupport.c

   1 /* Support routines for the various generation passes.
   2    Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009,
   3    2010, Free Software Foundation, Inc.
   4
   5    This file is part of GCC.
   6
   7    GCC is free software; you can redistribute it and/or modify it
   8    under the terms of the GNU General Public License as published by
   9    the Free Software Foundation; either version 3, or (at your option)
  10    any later version.
  11
  12    GCC is distributed in the hope that it will be useful, but WITHOUT
  13    ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  14    or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
  15    License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with GCC; see the file COPYING3.  If not see
  19    <http://www.gnu.org/licenses/>.  */
  20
  21 #include "bconfig.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "rtl.h"
  26 #include "obstack.h"
  27 #include "errors.h"
  28 #include "hashtab.h"
  29 #include "read-md.h"
  30 #include "gensupport.h"
  31
  32
  33 /* In case some macros used by files we include need it, define this here.  */
  34 int target_flags;
  35
  36 int insn_elision = 1;
  37
  38 static struct obstack obstack;
  39 struct obstack *rtl_obstack = &obstack;
  40
  41 static int sequence_num;
  42
  43 static int predicable_default;
  44 static const char *predicable_true;
  45 static const char *predicable_false;
  46
  47 static htab_t condition_table;
  48
  49 /* We initially queue all patterns, process the define_insn and
  50    define_cond_exec patterns, then return them one at a time.  */
  51
  52 struct queue_elem
  53 {
  54   rtx data;
  55   const char *filename;
  56   int lineno;
  57   struct queue_elem *next;
  58   /* In a DEFINE_INSN that came from a DEFINE_INSN_AND_SPLIT, SPLIT
  59      points to the generated DEFINE_SPLIT.  */
  60   struct queue_elem *split;
  61 };
  62
  63 #define MNEMONIC_ATTR_NAME "mnemonic"
  64 #define MNEMONIC_HTAB_SIZE 1024
  65
  66 static struct queue_elem *define_attr_queue;
  67 static struct queue_elem **define_attr_tail = &define_attr_queue;
  68 static struct queue_elem *define_pred_queue;
  69 static struct queue_elem **define_pred_tail = &define_pred_queue;
  70 static struct queue_elem *define_insn_queue;
  71 static struct queue_elem **define_insn_tail = &define_insn_queue;
  72 static struct queue_elem *define_cond_exec_queue;
  73 static struct queue_elem **define_cond_exec_tail = &define_cond_exec_queue;
  74 static struct queue_elem *other_queue;
  75 static struct queue_elem **other_tail = &other_queue;
  76
  77 static struct queue_elem *queue_pattern (rtx, struct queue_elem ***,
  78                                          const char *, int);
  79
  80 static void remove_constraints (rtx);
  81 static void process_rtx (rtx, int);
  82
  83 static int is_predicable (struct queue_elem *);
  84 static void identify_predicable_attribute (void);
  85 static int n_alternatives (const char *);
  86 static void collect_insn_data (rtx, int *, int *);
  87 static rtx alter_predicate_for_insn (rtx, int, int, int);
  88 static const char *alter_test_for_insn (struct queue_elem *,
  89                                         struct queue_elem *);
  90 static char *shift_output_template (char *, const char *, int);
  91 static const char *alter_output_for_insn (struct queue_elem *,
  92                                           struct queue_elem *,
  93                                           int, int);
  94 static void process_one_cond_exec (struct queue_elem *);
  95 static void process_define_cond_exec (void);
  96 static void init_predicate_table (void);
  97 static void record_insn_name (int, const char *);
  98 \f
  99 /* Make a version of gen_rtx_CONST_INT so that GEN_INT can be used in
 100    the gensupport programs.  */
 101
 102 rtx
 103 gen_rtx_CONST_INT (enum machine_mode ARG_UNUSED (mode),
 104                    HOST_WIDE_INT arg)
 105 {
 106   rtx rt = rtx_alloc (CONST_INT);
 107
 108   XWINT (rt, 0) = arg;
 109   return rt;
 110 }
 111 \f
 112 /* Predicate handling.
 113
 114    We construct from the machine description a table mapping each
 115    predicate to a list of the rtl codes it can possibly match.  The
 116    function 'maybe_both_true' uses it to deduce that there are no
 117    expressions that can be matches by certain pairs of tree nodes.
 118    Also, if a predicate can match only one code, we can hardwire that
 119    code into the node testing the predicate.
 120
 121    Some predicates are flagged as special.  validate_pattern will not
 122    warn about modeless match_operand expressions if they have a
 123    special predicate.  Predicates that allow only constants are also
 124    treated as special, for this purpose.
 125
 126    validate_pattern will warn about predicates that allow non-lvalues
 127    when they appear in destination operands.
 128
 129    Calculating the set of rtx codes that can possibly be accepted by a
 130    predicate expression EXP requires a three-state logic: any given
 131    subexpression may definitively accept a code C (Y), definitively
 132    reject a code C (N), or may have an indeterminate effect (I).  N
 133    and I is N; Y or I is Y; Y and I, N or I are both I.  Here are full
 134    truth tables.
 135
 136      a b  a&b  a|b
 137      Y Y   Y    Y
 138      N Y   N    Y
 139      N N   N    N
 140      I Y   I    Y
 141      I N   N    I
 142      I I   I    I
 143
 144    We represent Y with 1, N with 0, I with 2.  If any code is left in
 145    an I state by the complete expression, we must assume that that
 146    code can be accepted.  */
 147
 148 #define N 0
 149 #define Y 1
 150 #define I 2
 151
 152 #define TRISTATE_AND(a,b)                       \
 153   ((a) == I ? ((b) == N ? N : I) :              \
 154    (b) == I ? ((a) == N ? N : I) :              \
 155    (a) && (b))
 156
 157 #define TRISTATE_OR(a,b)                        \
 158   ((a) == I ? ((b) == Y ? Y : I) :              \
 159    (b) == I ? ((a) == Y ? Y : I) :              \
 160    (a) || (b))
 161
 162 #define TRISTATE_NOT(a)                         \
 163   ((a) == I ? I : !(a))
 164
 165 /* 0 means no warning about that code yet, 1 means warned.  */
 166 static char did_you_mean_codes[NUM_RTX_CODE];
 167
 168 /* Recursively calculate the set of rtx codes accepted by the
 169    predicate expression EXP, writing the result to CODES.  LINENO is
 170    the line number on which the directive containing EXP appeared.  */
 171
 172 static void
 173 compute_predicate_codes (rtx exp, int lineno, char codes[NUM_RTX_CODE])
 174 {
 175   char op0_codes[NUM_RTX_CODE];
 176   char op1_codes[NUM_RTX_CODE];
 177   char op2_codes[NUM_RTX_CODE];
 178   int i;
 179
 180   switch (GET_CODE (exp))
 181     {
 182     case AND:
 183       compute_predicate_codes (XEXP (exp, 0), lineno, op0_codes);
 184       compute_predicate_codes (XEXP (exp, 1), lineno, op1_codes);
 185       for (i = 0; i < NUM_RTX_CODE; i++)
 186         codes[i] = TRISTATE_AND (op0_codes[i], op1_codes[i]);
 187       break;
 188
 189     case IOR:
 190       compute_predicate_codes (XEXP (exp, 0), lineno, op0_codes);
 191       compute_predicate_codes (XEXP (exp, 1), lineno, op1_codes);
 192       for (i = 0; i < NUM_RTX_CODE; i++)
 193         codes[i] = TRISTATE_OR (op0_codes[i], op1_codes[i]);
 194       break;
 195     case NOT:
 196       compute_predicate_codes (XEXP (exp, 0), lineno, op0_codes);
 197       for (i = 0; i < NUM_RTX_CODE; i++)
 198         codes[i] = TRISTATE_NOT (op0_codes[i]);
 199       break;
 200
 201     case IF_THEN_ELSE:
 202       /* a ? b : c  accepts the same codes as (a & b) | (!a & c).  */
 203       compute_predicate_codes (XEXP (exp, 0), lineno, op0_codes);
 204       compute_predicate_codes (XEXP (exp, 1), lineno, op1_codes);
 205       compute_predicate_codes (XEXP (exp, 2), lineno, op2_codes);
 206       for (i = 0; i < NUM_RTX_CODE; i++)
 207         codes[i] = TRISTATE_OR (TRISTATE_AND (op0_codes[i], op1_codes[i]),
 208                                 TRISTATE_AND (TRISTATE_NOT (op0_codes[i]),
 209                                               op2_codes[i]));
 210       break;
 211
 212     case MATCH_CODE:
 213       /* MATCH_CODE allows a specified list of codes.  However, if it
 214          does not apply to the top level of the expression, it does not
 215          constrain the set of codes for the top level.  */
 216       if (XSTR (exp, 1)[0] != '\0')
 217         {
 218           memset (codes, Y, NUM_RTX_CODE);
 219           break;
 220         }
 221
 222       memset (codes, N, NUM_RTX_CODE);
 223       {
 224         const char *next_code = XSTR (exp, 0);
 225         const char *code;
 226
 227         if (*next_code == '\0')
 228           {
 229             error_with_line (lineno, "empty match_code expression");
 230             break;
 231           }
 232
 233         while ((code = scan_comma_elt (&next_code)) != 0)
 234           {
 235             size_t n = next_code - code;
 236             int found_it = 0;
 237
 238             for (i = 0; i < NUM_RTX_CODE; i++)
 239               if (!strncmp (code, GET_RTX_NAME (i), n)
 240                   && GET_RTX_NAME (i)[n] == '\0')
 241                 {
 242                   codes[i] = Y;
 243                   found_it = 1;
 244                   break;
 245                 }
 246             if (!found_it)
 247               {
 248                 error_with_line (lineno,
 249                                  "match_code \"%.*s\" matches nothing",
 250                                  (int) n, code);
 251                 for (i = 0; i < NUM_RTX_CODE; i++)
 252                   if (!strncasecmp (code, GET_RTX_NAME (i), n)
 253                       && GET_RTX_NAME (i)[n] == '\0'
 254                       && !did_you_mean_codes[i])
 255                     {
 256                       did_you_mean_codes[i] = 1;
 257                       message_with_line (lineno, "(did you mean \"%s\"?)",
 258                                          GET_RTX_NAME (i));
 259                     }
 260               }
 261           }
 262       }
 263       break;
 264
 265     case MATCH_OPERAND:
 266       /* MATCH_OPERAND disallows the set of codes that the named predicate
 267          disallows, and is indeterminate for the codes that it does allow.  */
 268       {
 269         struct pred_data *p = lookup_predicate (XSTR (exp, 1));
 270         if (!p)
 271           {
 272             error_with_line (lineno, "reference to unknown predicate '%s'",
 273                              XSTR (exp, 1));
 274             break;
 275           }
 276         for (i = 0; i < NUM_RTX_CODE; i++)
 277           codes[i] = p->codes[i] ? I : N;
 278       }
 279       break;
 280
 281
 282     case MATCH_TEST:
 283       /* (match_test WHATEVER) is completely indeterminate.  */
 284       memset (codes, I, NUM_RTX_CODE);
 285       break;
 286
 287     default:
 288       error_with_line (lineno,
 289                        "'%s' cannot be used in a define_predicate expression",
 290                        GET_RTX_NAME (GET_CODE (exp)));
 291       memset (codes, I, NUM_RTX_CODE);
 292       break;
 293     }
 294 }
 295
 296 #undef TRISTATE_OR
 297 #undef TRISTATE_AND
 298 #undef TRISTATE_NOT
 299
 300 /* Return true if NAME is a valid predicate name.  */
 301
 302 static bool
 303 valid_predicate_name_p (const char *name)
 304 {
 305   const char *p;
 306
 307   if (!ISALPHA (name[0]) && name[0] != '_')
 308     return false;
 309   for (p = name + 1; *p; p++)
 310     if (!ISALNUM (*p) && *p != '_')
 311       return false;
 312   return true;
 313 }
 314
 315 /* Process define_predicate directive DESC, which appears on line number
 316    LINENO.  Compute the set of codes that can be matched, and record this
 317    as a known predicate.  */
 318
 319 static void
 320 process_define_predicate (rtx desc, int lineno)
 321 {
 322   struct pred_data *pred;
 323   char codes[NUM_RTX_CODE];
 324   int i;
 325
 326   if (!valid_predicate_name_p (XSTR (desc, 0)))
 327     {
 328       error_with_line (lineno,
 329                        "%s: predicate name must be a valid C function name",
 330                        XSTR (desc, 0));
 331       return;
 332     }
 333
 334   pred = XCNEW (struct pred_data);
 335   pred->name = XSTR (desc, 0);
 336   pred->exp = XEXP (desc, 1);
 337   pred->c_block = XSTR (desc, 2);
 338   if (GET_CODE (desc) == DEFINE_SPECIAL_PREDICATE)
 339     pred->special = true;
 340
 341   compute_predicate_codes (XEXP (desc, 1), lineno, codes);
 342
 343   for (i = 0; i < NUM_RTX_CODE; i++)
 344     if (codes[i] != N)
 345       add_predicate_code (pred, (enum rtx_code) i);
 346
 347   add_predicate (pred);
 348 }
 349 #undef I
 350 #undef N
 351 #undef Y
 352 \f
 353 /* Queue PATTERN on LIST_TAIL.  Return the address of the new queue
 354    element.  */
 355
 356 static struct queue_elem *
 357 queue_pattern (rtx pattern, struct queue_elem ***list_tail,
 358                const char *filename, int lineno)
 359 {
 360   struct queue_elem *e = XNEW(struct queue_elem);
 361   e->data = pattern;
 362   e->filename = filename;
 363   e->lineno = lineno;
 364   e->next = NULL;
 365   e->split = NULL;
 366   **list_tail = e;
 367   *list_tail = &e->next;
 368   return e;
 369 }
 370
 371 /* Recursively remove constraints from an rtx.  */
 372
 373 static void
 374 remove_constraints (rtx part)
 375 {
 376   int i, j;
 377   const char *format_ptr;
 378
 379   if (part == 0)
 380     return;
 381
 382   if (GET_CODE (part) == MATCH_OPERAND)
 383     XSTR (part, 2) = "";
 384   else if (GET_CODE (part) == MATCH_SCRATCH)
 385     XSTR (part, 1) = "";
 386
 387   format_ptr = GET_RTX_FORMAT (GET_CODE (part));
 388
 389   for (i = 0; i < GET_RTX_LENGTH (GET_CODE (part)); i++)
 390     switch (*format_ptr++)
 391       {
 392       case 'e':
 393       case 'u':
 394         remove_constraints (XEXP (part, i));
 395         break;
 396       case 'E':
 397         if (XVEC (part, i) != NULL)
 398           for (j = 0; j < XVECLEN (part, i); j++)
 399             remove_constraints (XVECEXP (part, i, j));
 400         break;
 401       }
 402 }
 403
 404 /* Process a top level rtx in some way, queuing as appropriate.  */
 405
 406 static void
 407 process_rtx (rtx desc, int lineno)
 408 {
 409   switch (GET_CODE (desc))
 410     {
 411     case DEFINE_INSN:
 412       queue_pattern (desc, &define_insn_tail, read_md_filename, lineno);
 413       break;
 414
 415     case DEFINE_COND_EXEC:
 416       queue_pattern (desc, &define_cond_exec_tail, read_md_filename, lineno);
 417       break;
 418
 419     case DEFINE_ATTR:
 420     case DEFINE_ENUM_ATTR:
 421       queue_pattern (desc, &define_attr_tail, read_md_filename, lineno);
 422       break;
 423
 424     case DEFINE_PREDICATE:
 425     case DEFINE_SPECIAL_PREDICATE:
 426       process_define_predicate (desc, lineno);
 427       /* Fall through.  */
 428
 429     case DEFINE_CONSTRAINT:
 430     case DEFINE_REGISTER_CONSTRAINT:
 431     case DEFINE_MEMORY_CONSTRAINT:
 432     case DEFINE_ADDRESS_CONSTRAINT:
 433       queue_pattern (desc, &define_pred_tail, read_md_filename, lineno);
 434       break;
 435
 436     case DEFINE_INSN_AND_SPLIT:
 437       {
 438         const char *split_cond;
 439         rtx split;
 440         rtvec attr;
 441         int i;
 442         struct queue_elem *insn_elem;
 443         struct queue_elem *split_elem;
 444
 445         /* Create a split with values from the insn_and_split.  */
 446         split = rtx_alloc (DEFINE_SPLIT);
 447
 448         i = XVECLEN (desc, 1);
 449         XVEC (split, 0) = rtvec_alloc (i);
 450         while (--i >= 0)
 451           {
 452             XVECEXP (split, 0, i) = copy_rtx (XVECEXP (desc, 1, i));
 453             remove_constraints (XVECEXP (split, 0, i));
 454           }
 455
 456         /* If the split condition starts with "&&", append it to the
 457            insn condition to create the new split condition.  */
 458         split_cond = XSTR (desc, 4);
 459         if (split_cond[0] == '&' && split_cond[1] == '&')
 460           {
 461             copy_md_ptr_loc (split_cond + 2, split_cond);
 462             split_cond = join_c_conditions (XSTR (desc, 2), split_cond + 2);
 463           }
 464         XSTR (split, 1) = split_cond;
 465         XVEC (split, 2) = XVEC (desc, 5);
 466         XSTR (split, 3) = XSTR (desc, 6);
 467
 468         /* Fix up the DEFINE_INSN.  */
 469         attr = XVEC (desc, 7);
 470         PUT_CODE (desc, DEFINE_INSN);
 471         XVEC (desc, 4) = attr;
 472
 473         /* Queue them.  */
 474         insn_elem
 475           = queue_pattern (desc, &define_insn_tail, read_md_filename,
 476                            lineno);
 477         split_elem
 478           = queue_pattern (split, &other_tail, read_md_filename, lineno);
 479         insn_elem->split = split_elem;
 480         break;
 481       }
 482
 483     default:
 484       queue_pattern (desc, &other_tail, read_md_filename, lineno);
 485       break;
 486     }
 487 }
 488 \f
 489 /* Return true if attribute PREDICABLE is true for ELEM, which holds
 490    a DEFINE_INSN.  */
 491
 492 static int
 493 is_predicable (struct queue_elem *elem)
 494 {
 495   rtvec vec = XVEC (elem->data, 4);
 496   const char *value;
 497   int i;
 498
 499   if (! vec)
 500     return predicable_default;
 501
 502   for (i = GET_NUM_ELEM (vec) - 1; i >= 0; --i)
 503     {
 504       rtx sub = RTVEC_ELT (vec, i);
 505       switch (GET_CODE (sub))
 506         {
 507         case SET_ATTR:
 508           if (strcmp (XSTR (sub, 0), "predicable") == 0)
 509             {
 510               value = XSTR (sub, 1);
 511               goto found;
 512             }
 513           break;
 514
 515         case SET_ATTR_ALTERNATIVE:
 516           if (strcmp (XSTR (sub, 0), "predicable") == 0)
 517             {
 518               error_with_line (elem->lineno,
 519                                "multiple alternatives for `predicable'");
 520               return 0;
 521             }
 522           break;
 523
 524         case SET:
 525           if (GET_CODE (SET_DEST (sub)) != ATTR
 526               || strcmp (XSTR (SET_DEST (sub), 0), "predicable") != 0)
 527             break;
 528           sub = SET_SRC (sub);
 529           if (GET_CODE (sub) == CONST_STRING)
 530             {
 531               value = XSTR (sub, 0);
 532               goto found;
 533             }
 534
 535           /* ??? It would be possible to handle this if we really tried.
 536              It's not easy though, and I'm not going to bother until it
 537              really proves necessary.  */
 538           error_with_line (elem->lineno,
 539                            "non-constant value for `predicable'");
 540           return 0;
 541
 542         default:
 543           gcc_unreachable ();
 544         }
 545     }
 546
 547   return predicable_default;
 548
 549  found:
 550   /* Verify that predicability does not vary on the alternative.  */
 551   /* ??? It should be possible to handle this by simply eliminating
 552      the non-predicable alternatives from the insn.  FRV would like
 553      to do this.  Delay this until we've got the basics solid.  */
 554   if (strchr (value, ',') != NULL)
 555     {
 556       error_with_line (elem->lineno, "multiple alternatives for `predicable'");
 557       return 0;
 558     }
 559
 560   /* Find out which value we're looking at.  */
 561   if (strcmp (value, predicable_true) == 0)
 562     return 1;
 563   if (strcmp (value, predicable_false) == 0)
 564     return 0;
 565
 566   error_with_line (elem->lineno,
 567                    "unknown value `%s' for `predicable' attribute", value);
 568   return 0;
 569 }
 570
 571 /* Examine the attribute "predicable"; discover its boolean values
 572    and its default.  */
 573
 574 static void
 575 identify_predicable_attribute (void)
 576 {
 577   struct queue_elem *elem;
 578   char *p_true, *p_false;
 579   const char *value;
 580
 581   /* Look for the DEFINE_ATTR for `predicable', which must exist.  */
 582   for (elem = define_attr_queue; elem ; elem = elem->next)
 583     if (strcmp (XSTR (elem->data, 0), "predicable") == 0)
 584       goto found;
 585
 586   error_with_line (define_cond_exec_queue->lineno,
 587                    "attribute `predicable' not defined");
 588   return;
 589
 590  found:
 591   value = XSTR (elem->data, 1);
 592   p_false = xstrdup (value);
 593   p_true = strchr (p_false, ',');
 594   if (p_true == NULL || strchr (++p_true, ',') != NULL)
 595     {
 596       error_with_line (elem->lineno, "attribute `predicable' is not a boolean");
 597       if (p_false)
 598         free (p_false);
 599       return;
 600     }
 601   p_true[-1] = '\0';
 602
 603   predicable_true = p_true;
 604   predicable_false = p_false;
 605
 606   switch (GET_CODE (XEXP (elem->data, 2)))
 607     {
 608     case CONST_STRING:
 609       value = XSTR (XEXP (elem->data, 2), 0);
 610       break;
 611
 612     case CONST:
 613       error_with_line (elem->lineno, "attribute `predicable' cannot be const");
 614       if (p_false)
 615         free (p_false);
 616       return;
 617
 618     default:
 619       error_with_line (elem->lineno,
 620                        "attribute `predicable' must have a constant default");
 621       if (p_false)
 622         free (p_false);
 623       return;
 624     }
 625
 626   if (strcmp (value, p_true) == 0)
 627     predicable_default = 1;
 628   else if (strcmp (value, p_false) == 0)
 629     predicable_default = 0;
 630   else
 631     {
 632       error_with_line (elem->lineno,
 633                        "unknown value `%s' for `predicable' attribute", value);
 634       if (p_false)
 635         free (p_false);
 636     }
 637 }
 638
 639 /* Return the number of alternatives in constraint S.  */
 640
 641 static int
 642 n_alternatives (const char *s)
 643 {
 644   int n = 1;
 645
 646   if (s)
 647     while (*s)
 648       n += (*s++ == ',');
 649
 650   return n;
 651 }
 652
 653 /* Determine how many alternatives there are in INSN, and how many
 654    operands.  */
 655
 656 static void
 657 collect_insn_data (rtx pattern, int *palt, int *pmax)
 658 {
 659   const char *fmt;
 660   enum rtx_code code;
 661   int i, j, len;
 662
 663   code = GET_CODE (pattern);
 664   switch (code)
 665     {
 666     case MATCH_OPERAND:
 667       i = n_alternatives (XSTR (pattern, 2));
 668       *palt = (i > *palt ? i : *palt);
 669       /* Fall through.  */
 670
 671     case MATCH_OPERATOR:
 672     case MATCH_SCRATCH:
 673     case MATCH_PARALLEL:
 674       i = XINT (pattern, 0);
 675       if (i > *pmax)
 676         *pmax = i;
 677       break;
 678
 679     default:
 680       break;
 681     }
 682
 683   fmt = GET_RTX_FORMAT (code);
 684   len = GET_RTX_LENGTH (code);
 685   for (i = 0; i < len; i++)
 686     {
 687       switch (fmt[i])
 688         {
 689         case 'e': case 'u':
 690           collect_insn_data (XEXP (pattern, i), palt, pmax);
 691           break;
 692
 693         case 'V':
 694           if (XVEC (pattern, i) == NULL)
 695             break;
 696           /* Fall through.  */
 697         case 'E':
 698           for (j = XVECLEN (pattern, i) - 1; j >= 0; --j)
 699             collect_insn_data (XVECEXP (pattern, i, j), palt, pmax);
 700           break;
 701
 702         case 'i': case 'w': case '0': case 's': case 'S': case 'T':
 703           break;
 704
 705         default:
 706           gcc_unreachable ();
 707         }
 708     }
 709 }
 710
 711 static rtx
 712 alter_predicate_for_insn (rtx pattern, int alt, int max_op, int lineno)
 713 {
 714   const char *fmt;
 715   enum rtx_code code;
 716   int i, j, len;
 717
 718   code = GET_CODE (pattern);
 719   switch (code)
 720     {
 721     case MATCH_OPERAND:
 722       {
 723         const char *c = XSTR (pattern, 2);
 724
 725         if (n_alternatives (c) != 1)
 726           {
 727             error_with_line (lineno, "too many alternatives for operand %d",
 728                              XINT (pattern, 0));
 729             return NULL;
 730           }
 731
 732         /* Replicate C as needed to fill out ALT alternatives.  */
 733         if (c && *c && alt > 1)
 734           {
 735             size_t c_len = strlen (c);
 736             size_t len = alt * (c_len + 1);
 737             char *new_c = XNEWVEC(char, len);
 738
 739             memcpy (new_c, c, c_len);
 740             for (i = 1; i < alt; ++i)
 741               {
 742                 new_c[i * (c_len + 1) - 1] = ',';
 743                 memcpy (&new_c[i * (c_len + 1)], c, c_len);
 744               }
 745             new_c[len - 1] = '\0';
 746             XSTR (pattern, 2) = new_c;
 747           }
 748       }
 749       /* Fall through.  */
 750
 751     case MATCH_OPERATOR:
 752     case MATCH_SCRATCH:
 753     case MATCH_PARALLEL:
 754       XINT (pattern, 0) += max_op;
 755       break;
 756
 757     default:
 758       break;
 759     }
 760
 761   fmt = GET_RTX_FORMAT (code);
 762   len = GET_RTX_LENGTH (code);
 763   for (i = 0; i < len; i++)
 764     {
 765       rtx r;
 766
 767       switch (fmt[i])
 768         {
 769         case 'e': case 'u':
 770           r = alter_predicate_for_insn (XEXP (pattern, i), alt,
 771                                         max_op, lineno);
 772           if (r == NULL)
 773             return r;
 774           break;
 775
 776         case 'E':
 777           for (j = XVECLEN (pattern, i) - 1; j >= 0; --j)
 778             {
 779               r = alter_predicate_for_insn (XVECEXP (pattern, i, j),
 780                                             alt, max_op, lineno);
 781               if (r == NULL)
 782                 return r;
 783             }
 784           break;
 785
 786         case 'i': case 'w': case '0': case 's':
 787           break;
 788
 789         default:
 790           gcc_unreachable ();
 791         }
 792     }
 793
 794   return pattern;
 795 }
 796
 797 static const char *
 798 alter_test_for_insn (struct queue_elem *ce_elem,
 799                      struct queue_elem *insn_elem)
 800 {
 801   return join_c_conditions (XSTR (ce_elem->data, 1),
 802                             XSTR (insn_elem->data, 2));
 803 }
 804
 805 /* Adjust all of the operand numbers in SRC to match the shift they'll
 806    get from an operand displacement of DISP.  Return a pointer after the
 807    adjusted string.  */
 808
 809 static char *
 810 shift_output_template (char *dest, const char *src, int disp)
 811 {
 812   while (*src)
 813     {
 814       char c = *src++;
 815       *dest++ = c;
 816       if (c == '%')
 817         {
 818           c = *src++;
 819           if (ISDIGIT ((unsigned char) c))
 820             c += disp;
 821           else if (ISALPHA (c))
 822             {
 823               *dest++ = c;
 824               c = *src++ + disp;
 825             }
 826           *dest++ = c;
 827         }
 828     }
 829
 830   return dest;
 831 }
 832
 833 static const char *
 834 alter_output_for_insn (struct queue_elem *ce_elem,
 835                        struct queue_elem *insn_elem,
 836                        int alt, int max_op)
 837 {
 838   const char *ce_out, *insn_out;
 839   char *result, *p;
 840   size_t len, ce_len, insn_len;
 841
 842   /* ??? Could coordinate with genoutput to not duplicate code here.  */
 843
 844   ce_out = XSTR (ce_elem->data, 2);
 845   insn_out = XTMPL (insn_elem->data, 3);
 846   if (!ce_out || *ce_out == '\0')
 847     return insn_out;
 848
 849   ce_len = strlen (ce_out);
 850   insn_len = strlen (insn_out);
 851
 852   if (*insn_out == '*')
 853     /* You must take care of the predicate yourself.  */
 854     return insn_out;
 855
 856   if (*insn_out == '@')
 857     {
 858       len = (ce_len + 1) * alt + insn_len + 1;
 859       p = result = XNEWVEC(char, len);
 860
 861       do
 862         {
 863           do
 864             *p++ = *insn_out++;
 865           while (ISSPACE ((unsigned char) *insn_out));
 866
 867           if (*insn_out != '#')
 868             {
 869               p = shift_output_template (p, ce_out, max_op);
 870               *p++ = ' ';
 871             }
 872
 873           do
 874             *p++ = *insn_out++;
 875           while (*insn_out && *insn_out != '\n');
 876         }
 877       while (*insn_out);
 878       *p = '\0';
 879     }
 880   else
 881     {
 882       len = ce_len + 1 + insn_len + 1;
 883       result = XNEWVEC (char, len);
 884
 885       p = shift_output_template (result, ce_out, max_op);
 886       *p++ = ' ';
 887       memcpy (p, insn_out, insn_len + 1);
 888     }
 889
 890   return result;
 891 }
 892
 893 /* Replicate insns as appropriate for the given DEFINE_COND_EXEC.  */
 894
 895 static void
 896 process_one_cond_exec (struct queue_elem *ce_elem)
 897 {
 898   struct queue_elem *insn_elem;
 899   for (insn_elem = define_insn_queue; insn_elem ; insn_elem = insn_elem->next)
 900     {
 901       int alternatives, max_operand;
 902       rtx pred, insn, pattern, split;
 903       char *new_name;
 904       int i;
 905
 906       if (! is_predicable (insn_elem))
 907         continue;
 908
 909       alternatives = 1;
 910       max_operand = -1;
 911       collect_insn_data (insn_elem->data, &alternatives, &max_operand);
 912       max_operand += 1;
 913
 914       if (XVECLEN (ce_elem->data, 0) != 1)
 915         {
 916           error_with_line (ce_elem->lineno, "too many patterns in predicate");
 917           return;
 918         }
 919
 920       pred = copy_rtx (XVECEXP (ce_elem->data, 0, 0));
 921       pred = alter_predicate_for_insn (pred, alternatives, max_operand,
 922                                        ce_elem->lineno);
 923       if (pred == NULL)
 924         return;
 925
 926       /* Construct a new pattern for the new insn.  */
 927       insn = copy_rtx (insn_elem->data);
 928       new_name = XNEWVAR (char, strlen XSTR (insn_elem->data, 0) + 4);
 929       sprintf (new_name, "*p %s", XSTR (insn_elem->data, 0));
 930       XSTR (insn, 0) = new_name;
 931       pattern = rtx_alloc (COND_EXEC);
 932       XEXP (pattern, 0) = pred;
 933       if (XVECLEN (insn, 1) == 1)
 934         {
 935           XEXP (pattern, 1) = XVECEXP (insn, 1, 0);
 936           XVECEXP (insn, 1, 0) = pattern;
 937           PUT_NUM_ELEM (XVEC (insn, 1), 1);
 938         }
 939       else
 940         {
 941           XEXP (pattern, 1) = rtx_alloc (PARALLEL);
 942           XVEC (XEXP (pattern, 1), 0) = XVEC (insn, 1);
 943           XVEC (insn, 1) = rtvec_alloc (1);
 944           XVECEXP (insn, 1, 0) = pattern;
 945         }
 946
 947       XSTR (insn, 2) = alter_test_for_insn (ce_elem, insn_elem);
 948       XTMPL (insn, 3) = alter_output_for_insn (ce_elem, insn_elem,
 949                                               alternatives, max_operand);
 950
 951       /* ??? Set `predicable' to false.  Not crucial since it's really
 952          only used here, and we won't reprocess this new pattern.  */
 953
 954       /* Put the new pattern on the `other' list so that it
 955          (a) is not reprocessed by other define_cond_exec patterns
 956          (b) appears after all normal define_insn patterns.
 957
 958          ??? B is debatable.  If one has normal insns that match
 959          cond_exec patterns, they will be preferred over these
 960          generated patterns.  Whether this matters in practice, or if
 961          it's a good thing, or whether we should thread these new
 962          patterns into the define_insn chain just after their generator
 963          is something we'll have to experiment with.  */
 964
 965       queue_pattern (insn, &other_tail, insn_elem->filename,
 966                      insn_elem->lineno);
 967
 968       if (!insn_elem->split)
 969         continue;
 970
 971       /* If the original insn came from a define_insn_and_split,
 972          generate a new split to handle the predicated insn.  */
 973       split = copy_rtx (insn_elem->split->data);
 974       /* Predicate the pattern matched by the split.  */
 975       pattern = rtx_alloc (COND_EXEC);
 976       XEXP (pattern, 0) = pred;
 977       if (XVECLEN (split, 0) == 1)
 978         {
 979           XEXP (pattern, 1) = XVECEXP (split, 0, 0);
 980           XVECEXP (split, 0, 0) = pattern;
 981           PUT_NUM_ELEM (XVEC (split, 0), 1);
 982         }
 983       else
 984         {
 985           XEXP (pattern, 1) = rtx_alloc (PARALLEL);
 986           XVEC (XEXP (pattern, 1), 0) = XVEC (split, 0);
 987           XVEC (split, 0) = rtvec_alloc (1);
 988           XVECEXP (split, 0, 0) = pattern;
 989         }
 990       /* Predicate all of the insns generated by the split.  */
 991       for (i = 0; i < XVECLEN (split, 2); i++)
 992         {
 993           pattern = rtx_alloc (COND_EXEC);
 994           XEXP (pattern, 0) = pred;
 995           XEXP (pattern, 1) = XVECEXP (split, 2, i);
 996           XVECEXP (split, 2, i) = pattern;
 997         }
 998       /* Add the new split to the queue.  */
 999       queue_pattern (split, &other_tail, read_md_filename,
1000                      insn_elem->split->lineno);
1001     }
1002 }
1003
1004 /* If we have any DEFINE_COND_EXEC patterns, expand the DEFINE_INSN
1005    patterns appropriately.  */
1006
1007 static void
1008 process_define_cond_exec (void)
1009 {
1010   struct queue_elem *elem;
1011
1012   identify_predicable_attribute ();
1013   if (have_error)
1014     return;
1015
1016   for (elem = define_cond_exec_queue; elem ; elem = elem->next)
1017     process_one_cond_exec (elem);
1018 }
1019 \f
1020 /* A read_md_files callback for reading an rtx.  */
1021
1022 static void
1023 rtx_handle_directive (int lineno, const char *rtx_name)
1024 {
1025   rtx queue, x;
1026
1027   if (read_rtx (rtx_name, &queue))
1028     for (x = queue; x; x = XEXP (x, 1))
1029       process_rtx (XEXP (x, 0), lineno);
1030 }
1031
1032 /* Comparison function for the mnemonic hash table.  */
1033
1034 static int
1035 htab_eq_string (const void *s1, const void *s2)
1036 {
1037   return strcmp ((const char*)s1, (const char*)s2) == 0;
1038 }
1039
1040 /* Add mnemonic STR with length LEN to the mnemonic hash table
1041    MNEMONIC_HTAB.  A trailing zero end character is appendend to STR
1042    and a permanent heap copy of STR is created.  */
1043
1044 static void
1045 add_mnemonic_string (htab_t mnemonic_htab, const char *str, int len)
1046 {
1047   char *new_str;
1048   void **slot;
1049   char *str_zero = (char*)alloca (len + 1);
1050
1051   memcpy (str_zero, str, len);
1052   str_zero[len] = '\0';
1053
1054   slot = htab_find_slot (mnemonic_htab, str_zero, INSERT);
1055
1056   if (*slot)
1057     return;
1058
1059   /* Not found; create a permanent copy and add it to the hash table.  */
1060   new_str = XNEWVAR (char, len + 1);
1061   memcpy (new_str, str_zero, len + 1);
1062   *slot = new_str;
1063 }
1064
1065 /* Scan INSN for mnemonic strings and add them to the mnemonic hash
1066    table in MNEMONIC_HTAB.
1067
1068    The mnemonics cannot be found if they are emitted using C code.
1069
1070    If a mnemonic string contains ';' or a newline the string assumed
1071    to consist of more than a single instruction.  The attribute value
1072    will then be set to the user defined default value.  */
1073
1074 static void
1075 gen_mnemonic_setattr (htab_t mnemonic_htab, rtx insn)
1076 {
1077   const char *template_code, *cp;
1078   int i;
1079   int vec_len;
1080   rtx set_attr;
1081   char *attr_name;
1082   rtvec new_vec;
1083
1084   template_code = XTMPL (insn, 3);
1085
1086   /* Skip patterns which use C code to emit the template.  */
1087   if (template_code[0] == '*')
1088     return;
1089
1090   if (template_code[0] == '@')
1091     cp = &template_code[1];
1092   else
1093     cp = &template_code[0];
1094
1095   for (i = 0; *cp; )
1096     {
1097       const char *ep, *sp;
1098       int size = 0;
1099
1100       while (ISSPACE (*cp))
1101         cp++;
1102
1103       for (ep = sp = cp; !IS_VSPACE (*ep) && *ep != '\0'; ++ep)
1104         if (!ISSPACE (*ep))
1105           sp = ep + 1;
1106
1107       if (i > 0)
1108         obstack_1grow (&string_obstack, ',');
1109
1110       while (cp < sp && ((*cp >= '0' && *cp <= '9')
1111                          || (*cp >= 'a' && *cp <= 'z')))
1112
1113         {
1114           obstack_1grow (&string_obstack, *cp);
1115           cp++;
1116           size++;
1117         }
1118
1119       while (cp < sp)
1120         {
1121           if (*cp == ';' || (*cp == '\\' && cp[1] == 'n'))
1122             {
1123               /* Don't set a value if there are more than one
1124                  instruction in the string.  */
1125               obstack_next_free (&string_obstack) =
1126                 obstack_next_free (&string_obstack) - size;
1127               size = 0;
1128
1129               cp = sp;
1130               break;
1131             }
1132           cp++;
1133         }
1134       if (size == 0)
1135         obstack_1grow (&string_obstack, '*');
1136       else
1137         add_mnemonic_string (mnemonic_htab,
1138                              obstack_next_free (&string_obstack) - size,
1139                              size);
1140       i++;
1141     }
1142
1143   /* An insn definition might emit an empty string.  */
1144   if (obstack_object_size (&string_obstack) == 0)
1145     return;
1146
1147   obstack_1grow (&string_obstack, '\0');
1148
1149   set_attr = rtx_alloc (SET_ATTR);
1150   XSTR (set_attr, 1) = XOBFINISH (&string_obstack, char *);
1151   attr_name = XNEWVAR (char, strlen (MNEMONIC_ATTR_NAME) + 1);
1152   strcpy (attr_name, MNEMONIC_ATTR_NAME);
1153   XSTR (set_attr, 0) = attr_name;
1154
1155   if (!XVEC (insn, 4))
1156     vec_len = 0;
1157   else
1158     vec_len = XVECLEN (insn, 4);
1159
1160   new_vec = rtvec_alloc (vec_len + 1);
1161   for (i = 0; i < vec_len; i++)
1162     RTVEC_ELT (new_vec, i) = XVECEXP (insn, 4, i);
1163   RTVEC_ELT (new_vec, vec_len) = set_attr;
1164   XVEC (insn, 4) = new_vec;
1165 }
1166
1167 /* This function is called for the elements in the mnemonic hashtable
1168    and generates a comma separated list of the mnemonics.  */
1169
1170 static int
1171 mnemonic_htab_callback (void **slot, void *info ATTRIBUTE_UNUSED)
1172 {
1173   obstack_grow (&string_obstack, (char*)*slot, strlen ((char*)*slot));
1174   obstack_1grow (&string_obstack, ',');
1175   return 1;
1176 }
1177
1178 /* Generate (set_attr "mnemonic" "..") RTXs and append them to every
1179    insn definition in case the back end requests it by defining the
1180    mnemonic attribute.  The values for the attribute will be extracted
1181    from the output patterns of the insn definitions as far as
1182    possible.  */
1183
1184 static void
1185 gen_mnemonic_attr (void)
1186 {
1187   struct queue_elem *elem;
1188   rtx mnemonic_attr = NULL;
1189   htab_t mnemonic_htab;
1190   const char *str, *p;
1191   int i;
1192
1193   if (have_error)
1194     return;
1195
1196   /* Look for the DEFINE_ATTR for `mnemonic'.  */
1197   for (elem = define_attr_queue; elem != *define_attr_tail; elem = elem->next)
1198     if (GET_CODE (elem->data) == DEFINE_ATTR
1199         && strcmp (XSTR (elem->data, 0), MNEMONIC_ATTR_NAME) == 0)
1200       {
1201         mnemonic_attr = elem->data;
1202         break;
1203       }
1204
1205   /* A (define_attr "mnemonic" "...") indicates that the back-end
1206      wants a mnemonic attribute to be generated.  */
1207   if (!mnemonic_attr)
1208     return;
1209
1210   mnemonic_htab = htab_create_alloc (MNEMONIC_HTAB_SIZE, htab_hash_string,
1211                                      htab_eq_string, 0, xcalloc, free);
1212
1213   for (elem = define_insn_queue; elem; elem = elem->next)
1214     {
1215       rtx insn = elem->data;
1216       bool found = false;
1217
1218       /* Check if the insn definition already has
1219          (set_attr "mnemonic" ...).  */
1220       if (XVEC (insn, 4))
1221         for (i = 0; i < XVECLEN (insn, 4); i++)
1222           if (strcmp (XSTR (XVECEXP (insn, 4, i), 0), MNEMONIC_ATTR_NAME) == 0)
1223             {
1224               found = true;
1225               break;
1226             }
1227
1228       if (!found)
1229         gen_mnemonic_setattr (mnemonic_htab, insn);
1230     }
1231
1232   /* Add the user defined values to the hash table.  */
1233   str = XSTR (mnemonic_attr, 1);
1234   while ((p = scan_comma_elt (&str)) != NULL)
1235     add_mnemonic_string (mnemonic_htab, p, str - p);
1236
1237   htab_traverse (mnemonic_htab, mnemonic_htab_callback, NULL);
1238
1239   /* Replace the last ',' with the zero end character.  */
1240   *((char *)obstack_next_free (&string_obstack) - 1) = '\0';
1241   XSTR (mnemonic_attr, 1) = XOBFINISH (&string_obstack, char *);
1242 }
1243
1244 /* The entry point for initializing the reader.  */
1245
1246 bool
1247 init_rtx_reader_args_cb (int argc, char **argv,
1248                          bool (*parse_opt) (const char *))
1249 {
1250   /* Prepare to read input.  */
1251   condition_table = htab_create (500, hash_c_test, cmp_c_test, NULL);
1252   init_predicate_table ();
1253   obstack_init (rtl_obstack);
1254   sequence_num = 0;
1255
1256   read_md_files (argc, argv, parse_opt, rtx_handle_directive);
1257
1258   /* Process define_cond_exec patterns.  */
1259   if (define_cond_exec_queue != NULL)
1260     process_define_cond_exec ();
1261
1262   if (define_attr_queue != NULL)
1263     gen_mnemonic_attr ();
1264
1265   return !have_error;
1266 }
1267
1268 /* Programs that don't have their own options can use this entry point
1269    instead.  */
1270 bool
1271 init_rtx_reader_args (int argc, char **argv)
1272 {
1273   return init_rtx_reader_args_cb (argc, argv, 0);
1274 }
1275 \f
1276 /* The entry point for reading a single rtx from an md file.  */
1277
1278 rtx
1279 read_md_rtx (int *lineno, int *seqnr)
1280 {
1281   struct queue_elem **queue, *elem;
1282   rtx desc;
1283
1284  discard:
1285
1286   /* Read all patterns from a given queue before moving on to the next.  */
1287   if (define_attr_queue != NULL)
1288     queue = &define_attr_queue;
1289   else if (define_pred_queue != NULL)
1290     queue = &define_pred_queue;
1291   else if (define_insn_queue != NULL)
1292     queue = &define_insn_queue;
1293   else if (other_queue != NULL)
1294     queue = &other_queue;
1295   else
1296     return NULL_RTX;
1297
1298   elem = *queue;
1299   *queue = elem->next;
1300   desc = elem->data;
1301   read_md_filename = elem->filename;
1302   *lineno = elem->lineno;
1303   *seqnr = sequence_num;
1304
1305   free (elem);
1306
1307   /* Discard insn patterns which we know can never match (because
1308      their C test is provably always false).  If insn_elision is
1309      false, our caller needs to see all the patterns.  Note that the
1310      elided patterns are never counted by the sequence numbering; it
1311      it is the caller's responsibility, when insn_elision is false, not
1312      to use elided pattern numbers for anything.  */
1313   switch (GET_CODE (desc))
1314     {
1315     case DEFINE_INSN:
1316     case DEFINE_EXPAND:
1317       if (maybe_eval_c_test (XSTR (desc, 2)) != 0)
1318         sequence_num++;
1319       else if (insn_elision)
1320         goto discard;
1321
1322       /* *seqnr is used here so the name table will match caller's
1323          idea of insn numbering, whether or not elision is active.  */
1324       record_insn_name (*seqnr, XSTR (desc, 0));
1325       break;
1326
1327     case DEFINE_SPLIT:
1328     case DEFINE_PEEPHOLE:
1329     case DEFINE_PEEPHOLE2:
1330       if (maybe_eval_c_test (XSTR (desc, 1)) != 0)
1331         sequence_num++;
1332       else if (insn_elision)
1333             goto discard;
1334       break;
1335
1336     default:
1337       break;
1338     }
1339
1340   return desc;
1341 }
1342
1343 /* Helper functions for insn elision.  */
1344
1345 /* Compute a hash function of a c_test structure, which is keyed
1346    by its ->expr field.  */
1347 hashval_t
1348 hash_c_test (const void *x)
1349 {
1350   const struct c_test *a = (const struct c_test *) x;
1351   const unsigned char *base, *s = (const unsigned char *) a->expr;
1352   hashval_t hash;
1353   unsigned char c;
1354   unsigned int len;
1355
1356   base = s;
1357   hash = 0;
1358
1359   while ((c = *s++) != '\0')
1360     {
1361       hash += c + (c << 17);
1362       hash ^= hash >> 2;
1363     }
1364
1365   len = s - base;
1366   hash += len + (len << 17);
1367   hash ^= hash >> 2;
1368
1369   return hash;
1370 }
1371
1372 /* Compare two c_test expression structures.  */
1373 int
1374 cmp_c_test (const void *x, const void *y)
1375 {
1376   const struct c_test *a = (const struct c_test *) x;
1377   const struct c_test *b = (const struct c_test *) y;
1378
1379   return !strcmp (a->expr, b->expr);
1380 }
1381
1382 /* Given a string representing a C test expression, look it up in the
1383    condition_table and report whether or not its value is known
1384    at compile time.  Returns a tristate: 1 for known true, 0 for
1385    known false, -1 for unknown.  */
1386 int
1387 maybe_eval_c_test (const char *expr)
1388 {
1389   const struct c_test *test;
1390   struct c_test dummy;
1391
1392   if (expr[0] == 0)
1393     return 1;
1394
1395   dummy.expr = expr;
1396   test = (const struct c_test *)htab_find (condition_table, &dummy);
1397   if (!test)
1398     return -1;
1399   return test->value;
1400 }
1401
1402 /* Record the C test expression EXPR in the condition_table, with
1403    value VAL.  Duplicates clobber previous entries.  */
1404
1405 void
1406 add_c_test (const char *expr, int value)
1407 {
1408   struct c_test *test;
1409
1410   if (expr[0] == 0)
1411     return;
1412
1413   test = XNEW (struct c_test);
1414   test->expr = expr;
1415   test->value = value;
1416
1417   *(htab_find_slot (condition_table, test, INSERT)) = test;
1418 }
1419
1420 /* For every C test, call CALLBACK with two arguments: a pointer to
1421    the condition structure and INFO.  Stops when CALLBACK returns zero.  */
1422 void
1423 traverse_c_tests (htab_trav callback, void *info)
1424 {
1425   if (condition_table)
1426     htab_traverse (condition_table, callback, info);
1427 }
1428
1429 /* Helper functions for define_predicate and define_special_predicate
1430    processing.  Shared between genrecog.c and genpreds.c.  */
1431
1432 static htab_t predicate_table;
1433 struct pred_data *first_predicate;
1434 static struct pred_data **last_predicate = &first_predicate;
1435
1436 static hashval_t
1437 hash_struct_pred_data (const void *ptr)
1438 {
1439   return htab_hash_string (((const struct pred_data *)ptr)->name);
1440 }
1441
1442 static int
1443 eq_struct_pred_data (const void *a, const void *b)
1444 {
1445   return !strcmp (((const struct pred_data *)a)->name,
1446                   ((const struct pred_data *)b)->name);
1447 }
1448
1449 struct pred_data *
1450 lookup_predicate (const char *name)
1451 {
1452   struct pred_data key;
1453   key.name = name;
1454   return (struct pred_data *) htab_find (predicate_table, &key);
1455 }
1456
1457 /* Record that predicate PRED can accept CODE.  */
1458
1459 void
1460 add_predicate_code (struct pred_data *pred, enum rtx_code code)
1461 {
1462   if (!pred->codes[code])
1463     {
1464       pred->num_codes++;
1465       pred->codes[code] = true;
1466
1467       if (GET_RTX_CLASS (code) != RTX_CONST_OBJ)
1468         pred->allows_non_const = true;
1469
1470       if (code != REG
1471           && code != SUBREG
1472           && code != MEM
1473           && code != CONCAT
1474           && code != PARALLEL
1475           && code != STRICT_LOW_PART)
1476         pred->allows_non_lvalue = true;
1477
1478       if (pred->num_codes == 1)
1479         pred->singleton = code;
1480       else if (pred->num_codes == 2)
1481         pred->singleton = UNKNOWN;
1482     }
1483 }
1484
1485 void
1486 add_predicate (struct pred_data *pred)
1487 {
1488   void **slot = htab_find_slot (predicate_table, pred, INSERT);
1489   if (*slot)
1490     {
1491       error ("duplicate predicate definition for '%s'", pred->name);
1492       return;
1493     }
1494   *slot = pred;
1495   *last_predicate = pred;
1496   last_predicate = &pred->next;
1497 }
1498
1499 /* This array gives the initial content of the predicate table.  It
1500    has entries for all predicates defined in recog.c.  */
1501
1502 struct std_pred_table
1503 {
1504   const char *name;
1505   bool special;
1506   bool allows_const_p;
1507   RTX_CODE codes[NUM_RTX_CODE];
1508 };
1509
1510 static const struct std_pred_table std_preds[] = {
1511   {"general_operand", false, true, {SUBREG, REG, MEM}},
1512   {"address_operand", true, true, {SUBREG, REG, MEM, PLUS, MINUS, MULT}},
1513   {"register_operand", false, false, {SUBREG, REG}},
1514   {"pmode_register_operand", true, false, {SUBREG, REG}},
1515   {"scratch_operand", false, false, {SCRATCH, REG}},
1516   {"immediate_operand", false, true, {UNKNOWN}},
1517   {"const_int_operand", false, false, {CONST_INT}},
1518   {"const_double_operand", false, false, {CONST_INT, CONST_DOUBLE}},
1519   {"nonimmediate_operand", false, false, {SUBREG, REG, MEM}},
1520   {"nonmemory_operand", false, true, {SUBREG, REG}},
1521   {"push_operand", false, false, {MEM}},
1522   {"pop_operand", false, false, {MEM}},
1523   {"memory_operand", false, false, {SUBREG, MEM}},
1524   {"indirect_operand", false, false, {SUBREG, MEM}},
1525   {"ordered_comparison_operator", false, false, {EQ, NE,
1526                                                  LE, LT, GE, GT,
1527                                                  LEU, LTU, GEU, GTU}},
1528   {"comparison_operator", false, false, {EQ, NE,
1529                                          LE, LT, GE, GT,
1530                                          LEU, LTU, GEU, GTU,
1531                                          UNORDERED, ORDERED,
1532                                          UNEQ, UNGE, UNGT,
1533                                          UNLE, UNLT, LTGT}}
1534 };
1535 #define NUM_KNOWN_STD_PREDS ARRAY_SIZE (std_preds)
1536
1537 /* Initialize the table of predicate definitions, starting with
1538    the information we have on generic predicates.  */
1539
1540 static void
1541 init_predicate_table (void)
1542 {
1543   size_t i, j;
1544   struct pred_data *pred;
1545
1546   predicate_table = htab_create_alloc (37, hash_struct_pred_data,
1547                                        eq_struct_pred_data, 0,
1548                                        xcalloc, free);
1549
1550   for (i = 0; i < NUM_KNOWN_STD_PREDS; i++)
1551     {
1552       pred = XCNEW (struct pred_data);
1553       pred->name = std_preds[i].name;
1554       pred->special = std_preds[i].special;
1555
1556       for (j = 0; std_preds[i].codes[j] != 0; j++)
1557         add_predicate_code (pred, std_preds[i].codes[j]);
1558
1559       if (std_preds[i].allows_const_p)
1560         for (j = 0; j < NUM_RTX_CODE; j++)
1561           if (GET_RTX_CLASS (j) == RTX_CONST_OBJ)
1562             add_predicate_code (pred, (enum rtx_code) j);
1563
1564       add_predicate (pred);
1565     }
1566 }
1567 \f
1568 /* These functions allow linkage with print-rtl.c.  Also, some generators
1569    like to annotate their output with insn names.  */
1570
1571 /* Holds an array of names indexed by insn_code_number.  */
1572 static char **insn_name_ptr = 0;
1573 static int insn_name_ptr_size = 0;
1574
1575 const char *
1576 get_insn_name (int code)
1577 {
1578   if (code < insn_name_ptr_size)
1579     return insn_name_ptr[code];
1580   else
1581     return NULL;
1582 }
1583
1584 static void
1585 record_insn_name (int code, const char *name)
1586 {
1587   static const char *last_real_name = "insn";
1588   static int last_real_code = 0;
1589   char *new_name;
1590
1591   if (insn_name_ptr_size <= code)
1592     {
1593       int new_size;
1594       new_size = (insn_name_ptr_size ? insn_name_ptr_size * 2 : 512);
1595       insn_name_ptr = XRESIZEVEC (char *, insn_name_ptr, new_size);
1596       memset (insn_name_ptr + insn_name_ptr_size, 0,
1597               sizeof(char *) * (new_size - insn_name_ptr_size));
1598       insn_name_ptr_size = new_size;
1599     }
1600
1601   if (!name || name[0] == '\0')
1602     {
1603       new_name = XNEWVAR (char, strlen (last_real_name) + 10);
1604       sprintf (new_name, "%s+%d", last_real_name, code - last_real_code);
1605     }
1606   else
1607     {
1608       last_real_name = new_name = xstrdup (name);
1609       last_real_code = code;
1610     }
1611
1612   insn_name_ptr[code] = new_name;
1613 }
1614 \f
1615 /* Make STATS describe the operands that appear in rtx X.  */
1616
1617 static void
1618 get_pattern_stats_1 (struct pattern_stats *stats, rtx x)
1619 {
1620   RTX_CODE code;
1621   int i;
1622   int len;
1623   const char *fmt;
1624
1625   if (x == NULL_RTX)
1626     return;
1627
1628   code = GET_CODE (x);
1629   switch (code)
1630     {
1631     case MATCH_OPERAND:
1632     case MATCH_OPERATOR:
1633     case MATCH_PARALLEL:
1634       stats->max_opno = MAX (stats->max_opno, XINT (x, 0));
1635       break;
1636
1637     case MATCH_DUP:
1638     case MATCH_OP_DUP:
1639     case MATCH_PAR_DUP:
1640       stats->num_dups++;
1641       stats->max_dup_opno = MAX (stats->max_dup_opno, XINT (x, 0));
1642       break;
1643
1644     case MATCH_SCRATCH:
1645       stats->max_scratch_opno = MAX (stats->max_scratch_opno, XINT (x, 0));
1646       break;
1647
1648     default:
1649       break;
1650     }
1651
1652   fmt = GET_RTX_FORMAT (code);
1653   len = GET_RTX_LENGTH (code);
1654   for (i = 0; i < len; i++)
1655     {
1656       if (fmt[i] == 'e' || fmt[i] == 'u')
1657         get_pattern_stats_1 (stats, XEXP (x, i));
1658       else if (fmt[i] == 'E')
1659         {
1660           int j;
1661           for (j = 0; j < XVECLEN (x, i); j++)
1662             get_pattern_stats_1 (stats, XVECEXP (x, i, j));
1663         }
1664     }
1665 }
1666
1667 /* Make STATS describe the operands that appear in instruction pattern
1668    PATTERN.  */
1669
1670 void
1671 get_pattern_stats (struct pattern_stats *stats, rtvec pattern)
1672 {
1673   int i, len;
1674
1675   stats->max_opno = -1;
1676   stats->max_dup_opno = -1;
1677   stats->max_scratch_opno = -1;
1678   stats->num_dups = 0;
1679
1680   len = GET_NUM_ELEM (pattern);
1681   for (i = 0; i < len; i++)
1682     get_pattern_stats_1 (stats, RTVEC_ELT (pattern, i));
1683
1684   stats->num_generator_args = stats->max_opno + 1;
1685   stats->num_insn_operands = MAX (stats->max_opno,
1686                                   stats->max_scratch_opno) + 1;
1687   stats->num_operand_vars = MAX (stats->max_opno,
1688                                   MAX (stats->max_dup_opno,
1689                                        stats->max_scratch_opno)) + 1;
1690 }