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       free (p_false);
 598       return;
 599     }
 600   p_true[-1] = '\0';
 601
 602   predicable_true = p_true;
 603   predicable_false = p_false;
 604
 605   switch (GET_CODE (XEXP (elem->data, 2)))
 606     {
 607     case CONST_STRING:
 608       value = XSTR (XEXP (elem->data, 2), 0);
 609       break;
 610
 611     case CONST:
 612       error_with_line (elem->lineno, "attribute `predicable' cannot be const");
 613       free (p_false);
 614       return;
 615
 616     default:
 617       error_with_line (elem->lineno,
 618                        "attribute `predicable' must have a constant default");
 619       free (p_false);
 620       return;
 621     }
 622
 623   if (strcmp (value, p_true) == 0)
 624     predicable_default = 1;
 625   else if (strcmp (value, p_false) == 0)
 626     predicable_default = 0;
 627   else
 628     {
 629       error_with_line (elem->lineno,
 630                        "unknown value `%s' for `predicable' attribute", value);
 631       free (p_false);
 632     }
 633 }
 634
 635 /* Return the number of alternatives in constraint S.  */
 636
 637 static int
 638 n_alternatives (const char *s)
 639 {
 640   int n = 1;
 641
 642   if (s)
 643     while (*s)
 644       n += (*s++ == ',');
 645
 646   return n;
 647 }
 648
 649 /* Determine how many alternatives there are in INSN, and how many
 650    operands.  */
 651
 652 static void
 653 collect_insn_data (rtx pattern, int *palt, int *pmax)
 654 {
 655   const char *fmt;
 656   enum rtx_code code;
 657   int i, j, len;
 658
 659   code = GET_CODE (pattern);
 660   switch (code)
 661     {
 662     case MATCH_OPERAND:
 663       i = n_alternatives (XSTR (pattern, 2));
 664       *palt = (i > *palt ? i : *palt);
 665       /* Fall through.  */
 666
 667     case MATCH_OPERATOR:
 668     case MATCH_SCRATCH:
 669     case MATCH_PARALLEL:
 670       i = XINT (pattern, 0);
 671       if (i > *pmax)
 672         *pmax = i;
 673       break;
 674
 675     default:
 676       break;
 677     }
 678
 679   fmt = GET_RTX_FORMAT (code);
 680   len = GET_RTX_LENGTH (code);
 681   for (i = 0; i < len; i++)
 682     {
 683       switch (fmt[i])
 684         {
 685         case 'e': case 'u':
 686           collect_insn_data (XEXP (pattern, i), palt, pmax);
 687           break;
 688
 689         case 'V':
 690           if (XVEC (pattern, i) == NULL)
 691             break;
 692           /* Fall through.  */
 693         case 'E':
 694           for (j = XVECLEN (pattern, i) - 1; j >= 0; --j)
 695             collect_insn_data (XVECEXP (pattern, i, j), palt, pmax);
 696           break;
 697
 698         case 'i': case 'w': case '0': case 's': case 'S': case 'T':
 699           break;
 700
 701         default:
 702           gcc_unreachable ();
 703         }
 704     }
 705 }
 706
 707 static rtx
 708 alter_predicate_for_insn (rtx pattern, int alt, int max_op, int lineno)
 709 {
 710   const char *fmt;
 711   enum rtx_code code;
 712   int i, j, len;
 713
 714   code = GET_CODE (pattern);
 715   switch (code)
 716     {
 717     case MATCH_OPERAND:
 718       {
 719         const char *c = XSTR (pattern, 2);
 720
 721         if (n_alternatives (c) != 1)
 722           {
 723             error_with_line (lineno, "too many alternatives for operand %d",
 724                              XINT (pattern, 0));
 725             return NULL;
 726           }
 727
 728         /* Replicate C as needed to fill out ALT alternatives.  */
 729         if (c && *c && alt > 1)
 730           {
 731             size_t c_len = strlen (c);
 732             size_t len = alt * (c_len + 1);
 733             char *new_c = XNEWVEC(char, len);
 734
 735             memcpy (new_c, c, c_len);
 736             for (i = 1; i < alt; ++i)
 737               {
 738                 new_c[i * (c_len + 1) - 1] = ',';
 739                 memcpy (&new_c[i * (c_len + 1)], c, c_len);
 740               }
 741             new_c[len - 1] = '\0';
 742             XSTR (pattern, 2) = new_c;
 743           }
 744       }
 745       /* Fall through.  */
 746
 747     case MATCH_OPERATOR:
 748     case MATCH_SCRATCH:
 749     case MATCH_PARALLEL:
 750       XINT (pattern, 0) += max_op;
 751       break;
 752
 753     default:
 754       break;
 755     }
 756
 757   fmt = GET_RTX_FORMAT (code);
 758   len = GET_RTX_LENGTH (code);
 759   for (i = 0; i < len; i++)
 760     {
 761       rtx r;
 762
 763       switch (fmt[i])
 764         {
 765         case 'e': case 'u':
 766           r = alter_predicate_for_insn (XEXP (pattern, i), alt,
 767                                         max_op, lineno);
 768           if (r == NULL)
 769             return r;
 770           break;
 771
 772         case 'E':
 773           for (j = XVECLEN (pattern, i) - 1; j >= 0; --j)
 774             {
 775               r = alter_predicate_for_insn (XVECEXP (pattern, i, j),
 776                                             alt, max_op, lineno);
 777               if (r == NULL)
 778                 return r;
 779             }
 780           break;
 781
 782         case 'i': case 'w': case '0': case 's':
 783           break;
 784
 785         default:
 786           gcc_unreachable ();
 787         }
 788     }
 789
 790   return pattern;
 791 }
 792
 793 static const char *
 794 alter_test_for_insn (struct queue_elem *ce_elem,
 795                      struct queue_elem *insn_elem)
 796 {
 797   return join_c_conditions (XSTR (ce_elem->data, 1),
 798                             XSTR (insn_elem->data, 2));
 799 }
 800
 801 /* Adjust all of the operand numbers in SRC to match the shift they'll
 802    get from an operand displacement of DISP.  Return a pointer after the
 803    adjusted string.  */
 804
 805 static char *
 806 shift_output_template (char *dest, const char *src, int disp)
 807 {
 808   while (*src)
 809     {
 810       char c = *src++;
 811       *dest++ = c;
 812       if (c == '%')
 813         {
 814           c = *src++;
 815           if (ISDIGIT ((unsigned char) c))
 816             c += disp;
 817           else if (ISALPHA (c))
 818             {
 819               *dest++ = c;
 820               c = *src++ + disp;
 821             }
 822           *dest++ = c;
 823         }
 824     }
 825
 826   return dest;
 827 }
 828
 829 static const char *
 830 alter_output_for_insn (struct queue_elem *ce_elem,
 831                        struct queue_elem *insn_elem,
 832                        int alt, int max_op)
 833 {
 834   const char *ce_out, *insn_out;
 835   char *result, *p;
 836   size_t len, ce_len, insn_len;
 837
 838   /* ??? Could coordinate with genoutput to not duplicate code here.  */
 839
 840   ce_out = XSTR (ce_elem->data, 2);
 841   insn_out = XTMPL (insn_elem->data, 3);
 842   if (!ce_out || *ce_out == '\0')
 843     return insn_out;
 844
 845   ce_len = strlen (ce_out);
 846   insn_len = strlen (insn_out);
 847
 848   if (*insn_out == '*')
 849     /* You must take care of the predicate yourself.  */
 850     return insn_out;
 851
 852   if (*insn_out == '@')
 853     {
 854       len = (ce_len + 1) * alt + insn_len + 1;
 855       p = result = XNEWVEC(char, len);
 856
 857       do
 858         {
 859           do
 860             *p++ = *insn_out++;
 861           while (ISSPACE ((unsigned char) *insn_out));
 862
 863           if (*insn_out != '#')
 864             {
 865               p = shift_output_template (p, ce_out, max_op);
 866               *p++ = ' ';
 867             }
 868
 869           do
 870             *p++ = *insn_out++;
 871           while (*insn_out && *insn_out != '\n');
 872         }
 873       while (*insn_out);
 874       *p = '\0';
 875     }
 876   else
 877     {
 878       len = ce_len + 1 + insn_len + 1;
 879       result = XNEWVEC (char, len);
 880
 881       p = shift_output_template (result, ce_out, max_op);
 882       *p++ = ' ';
 883       memcpy (p, insn_out, insn_len + 1);
 884     }
 885
 886   return result;
 887 }
 888
 889 /* Replicate insns as appropriate for the given DEFINE_COND_EXEC.  */
 890
 891 static void
 892 process_one_cond_exec (struct queue_elem *ce_elem)
 893 {
 894   struct queue_elem *insn_elem;
 895   for (insn_elem = define_insn_queue; insn_elem ; insn_elem = insn_elem->next)
 896     {
 897       int alternatives, max_operand;
 898       rtx pred, insn, pattern, split;
 899       char *new_name;
 900       int i;
 901
 902       if (! is_predicable (insn_elem))
 903         continue;
 904
 905       alternatives = 1;
 906       max_operand = -1;
 907       collect_insn_data (insn_elem->data, &alternatives, &max_operand);
 908       max_operand += 1;
 909
 910       if (XVECLEN (ce_elem->data, 0) != 1)
 911         {
 912           error_with_line (ce_elem->lineno, "too many patterns in predicate");
 913           return;
 914         }
 915
 916       pred = copy_rtx (XVECEXP (ce_elem->data, 0, 0));
 917       pred = alter_predicate_for_insn (pred, alternatives, max_operand,
 918                                        ce_elem->lineno);
 919       if (pred == NULL)
 920         return;
 921
 922       /* Construct a new pattern for the new insn.  */
 923       insn = copy_rtx (insn_elem->data);
 924       new_name = XNEWVAR (char, strlen XSTR (insn_elem->data, 0) + 4);
 925       sprintf (new_name, "*p %s", XSTR (insn_elem->data, 0));
 926       XSTR (insn, 0) = new_name;
 927       pattern = rtx_alloc (COND_EXEC);
 928       XEXP (pattern, 0) = pred;
 929       if (XVECLEN (insn, 1) == 1)
 930         {
 931           XEXP (pattern, 1) = XVECEXP (insn, 1, 0);
 932           XVECEXP (insn, 1, 0) = pattern;
 933           PUT_NUM_ELEM (XVEC (insn, 1), 1);
 934         }
 935       else
 936         {
 937           XEXP (pattern, 1) = rtx_alloc (PARALLEL);
 938           XVEC (XEXP (pattern, 1), 0) = XVEC (insn, 1);
 939           XVEC (insn, 1) = rtvec_alloc (1);
 940           XVECEXP (insn, 1, 0) = pattern;
 941         }
 942
 943       XSTR (insn, 2) = alter_test_for_insn (ce_elem, insn_elem);
 944       XTMPL (insn, 3) = alter_output_for_insn (ce_elem, insn_elem,
 945                                               alternatives, max_operand);
 946
 947       /* ??? Set `predicable' to false.  Not crucial since it's really
 948          only used here, and we won't reprocess this new pattern.  */
 949
 950       /* Put the new pattern on the `other' list so that it
 951          (a) is not reprocessed by other define_cond_exec patterns
 952          (b) appears after all normal define_insn patterns.
 953
 954          ??? B is debatable.  If one has normal insns that match
 955          cond_exec patterns, they will be preferred over these
 956          generated patterns.  Whether this matters in practice, or if
 957          it's a good thing, or whether we should thread these new
 958          patterns into the define_insn chain just after their generator
 959          is something we'll have to experiment with.  */
 960
 961       queue_pattern (insn, &other_tail, insn_elem->filename,
 962                      insn_elem->lineno);
 963
 964       if (!insn_elem->split)
 965         continue;
 966
 967       /* If the original insn came from a define_insn_and_split,
 968          generate a new split to handle the predicated insn.  */
 969       split = copy_rtx (insn_elem->split->data);
 970       /* Predicate the pattern matched by the split.  */
 971       pattern = rtx_alloc (COND_EXEC);
 972       XEXP (pattern, 0) = pred;
 973       if (XVECLEN (split, 0) == 1)
 974         {
 975           XEXP (pattern, 1) = XVECEXP (split, 0, 0);
 976           XVECEXP (split, 0, 0) = pattern;
 977           PUT_NUM_ELEM (XVEC (split, 0), 1);
 978         }
 979       else
 980         {
 981           XEXP (pattern, 1) = rtx_alloc (PARALLEL);
 982           XVEC (XEXP (pattern, 1), 0) = XVEC (split, 0);
 983           XVEC (split, 0) = rtvec_alloc (1);
 984           XVECEXP (split, 0, 0) = pattern;
 985         }
 986       /* Predicate all of the insns generated by the split.  */
 987       for (i = 0; i < XVECLEN (split, 2); i++)
 988         {
 989           pattern = rtx_alloc (COND_EXEC);
 990           XEXP (pattern, 0) = pred;
 991           XEXP (pattern, 1) = XVECEXP (split, 2, i);
 992           XVECEXP (split, 2, i) = pattern;
 993         }
 994       /* Add the new split to the queue.  */
 995       queue_pattern (split, &other_tail, read_md_filename,
 996                      insn_elem->split->lineno);
 997     }
 998 }
 999
1000 /* If we have any DEFINE_COND_EXEC patterns, expand the DEFINE_INSN
1001    patterns appropriately.  */
1002
1003 static void
1004 process_define_cond_exec (void)
1005 {
1006   struct queue_elem *elem;
1007
1008   identify_predicable_attribute ();
1009   if (have_error)
1010     return;
1011
1012   for (elem = define_cond_exec_queue; elem ; elem = elem->next)
1013     process_one_cond_exec (elem);
1014 }
1015 \f
1016 /* A read_md_files callback for reading an rtx.  */
1017
1018 static void
1019 rtx_handle_directive (int lineno, const char *rtx_name)
1020 {
1021   rtx queue, x;
1022
1023   if (read_rtx (rtx_name, &queue))
1024     for (x = queue; x; x = XEXP (x, 1))
1025       process_rtx (XEXP (x, 0), lineno);
1026 }
1027
1028 /* Comparison function for the mnemonic hash table.  */
1029
1030 static int
1031 htab_eq_string (const void *s1, const void *s2)
1032 {
1033   return strcmp ((const char*)s1, (const char*)s2) == 0;
1034 }
1035
1036 /* Add mnemonic STR with length LEN to the mnemonic hash table
1037    MNEMONIC_HTAB.  A trailing zero end character is appendend to STR
1038    and a permanent heap copy of STR is created.  */
1039
1040 static void
1041 add_mnemonic_string (htab_t mnemonic_htab, const char *str, int len)
1042 {
1043   char *new_str;
1044   void **slot;
1045   char *str_zero = (char*)alloca (len + 1);
1046
1047   memcpy (str_zero, str, len);
1048   str_zero[len] = '\0';
1049
1050   slot = htab_find_slot (mnemonic_htab, str_zero, INSERT);
1051
1052   if (*slot)
1053     return;
1054
1055   /* Not found; create a permanent copy and add it to the hash table.  */
1056   new_str = XNEWVAR (char, len + 1);
1057   memcpy (new_str, str_zero, len + 1);
1058   *slot = new_str;
1059 }
1060
1061 /* Scan INSN for mnemonic strings and add them to the mnemonic hash
1062    table in MNEMONIC_HTAB.
1063
1064    The mnemonics cannot be found if they are emitted using C code.
1065
1066    If a mnemonic string contains ';' or a newline the string assumed
1067    to consist of more than a single instruction.  The attribute value
1068    will then be set to the user defined default value.  */
1069
1070 static void
1071 gen_mnemonic_setattr (htab_t mnemonic_htab, rtx insn)
1072 {
1073   const char *template_code, *cp;
1074   int i;
1075   int vec_len;
1076   rtx set_attr;
1077   char *attr_name;
1078   rtvec new_vec;
1079
1080   template_code = XTMPL (insn, 3);
1081
1082   /* Skip patterns which use C code to emit the template.  */
1083   if (template_code[0] == '*')
1084     return;
1085
1086   if (template_code[0] == '@')
1087     cp = &template_code[1];
1088   else
1089     cp = &template_code[0];
1090
1091   for (i = 0; *cp; )
1092     {
1093       const char *ep, *sp;
1094       int size = 0;
1095
1096       while (ISSPACE (*cp))
1097         cp++;
1098
1099       for (ep = sp = cp; !IS_VSPACE (*ep) && *ep != '\0'; ++ep)
1100         if (!ISSPACE (*ep))
1101           sp = ep + 1;
1102
1103       if (i > 0)
1104         obstack_1grow (&string_obstack, ',');
1105
1106       while (cp < sp && ((*cp >= '0' && *cp <= '9')
1107                          || (*cp >= 'a' && *cp <= 'z')))
1108
1109         {
1110           obstack_1grow (&string_obstack, *cp);
1111           cp++;
1112           size++;
1113         }
1114
1115       while (cp < sp)
1116         {
1117           if (*cp == ';' || (*cp == '\\' && cp[1] == 'n'))
1118             {
1119               /* Don't set a value if there are more than one
1120                  instruction in the string.  */
1121               obstack_next_free (&string_obstack) =
1122                 obstack_next_free (&string_obstack) - size;
1123               size = 0;
1124
1125               cp = sp;
1126               break;
1127             }
1128           cp++;
1129         }
1130       if (size == 0)
1131         obstack_1grow (&string_obstack, '*');
1132       else
1133         add_mnemonic_string (mnemonic_htab,
1134                              obstack_next_free (&string_obstack) - size,
1135                              size);
1136       i++;
1137     }
1138
1139   /* An insn definition might emit an empty string.  */
1140   if (obstack_object_size (&string_obstack) == 0)
1141     return;
1142
1143   obstack_1grow (&string_obstack, '\0');
1144
1145   set_attr = rtx_alloc (SET_ATTR);
1146   XSTR (set_attr, 1) = XOBFINISH (&string_obstack, char *);
1147   attr_name = XNEWVAR (char, strlen (MNEMONIC_ATTR_NAME) + 1);
1148   strcpy (attr_name, MNEMONIC_ATTR_NAME);
1149   XSTR (set_attr, 0) = attr_name;
1150
1151   if (!XVEC (insn, 4))
1152     vec_len = 0;
1153   else
1154     vec_len = XVECLEN (insn, 4);
1155
1156   new_vec = rtvec_alloc (vec_len + 1);
1157   for (i = 0; i < vec_len; i++)
1158     RTVEC_ELT (new_vec, i) = XVECEXP (insn, 4, i);
1159   RTVEC_ELT (new_vec, vec_len) = set_attr;
1160   XVEC (insn, 4) = new_vec;
1161 }
1162
1163 /* This function is called for the elements in the mnemonic hashtable
1164    and generates a comma separated list of the mnemonics.  */
1165
1166 static int
1167 mnemonic_htab_callback (void **slot, void *info ATTRIBUTE_UNUSED)
1168 {
1169   obstack_grow (&string_obstack, (char*)*slot, strlen ((char*)*slot));
1170   obstack_1grow (&string_obstack, ',');
1171   return 1;
1172 }
1173
1174 /* Generate (set_attr "mnemonic" "..") RTXs and append them to every
1175    insn definition in case the back end requests it by defining the
1176    mnemonic attribute.  The values for the attribute will be extracted
1177    from the output patterns of the insn definitions as far as
1178    possible.  */
1179
1180 static void
1181 gen_mnemonic_attr (void)
1182 {
1183   struct queue_elem *elem;
1184   rtx mnemonic_attr = NULL;
1185   htab_t mnemonic_htab;
1186   const char *str, *p;
1187   int i;
1188
1189   if (have_error)
1190     return;
1191
1192   /* Look for the DEFINE_ATTR for `mnemonic'.  */
1193   for (elem = define_attr_queue; elem != *define_attr_tail; elem = elem->next)
1194     if (GET_CODE (elem->data) == DEFINE_ATTR
1195         && strcmp (XSTR (elem->data, 0), MNEMONIC_ATTR_NAME) == 0)
1196       {
1197         mnemonic_attr = elem->data;
1198         break;
1199       }
1200
1201   /* A (define_attr "mnemonic" "...") indicates that the back-end
1202      wants a mnemonic attribute to be generated.  */
1203   if (!mnemonic_attr)
1204     return;
1205
1206   mnemonic_htab = htab_create_alloc (MNEMONIC_HTAB_SIZE, htab_hash_string,
1207                                      htab_eq_string, 0, xcalloc, free);
1208
1209   for (elem = define_insn_queue; elem; elem = elem->next)
1210     {
1211       rtx insn = elem->data;
1212       bool found = false;
1213
1214       /* Check if the insn definition already has
1215          (set_attr "mnemonic" ...).  */
1216       if (XVEC (insn, 4))
1217         for (i = 0; i < XVECLEN (insn, 4); i++)
1218           if (strcmp (XSTR (XVECEXP (insn, 4, i), 0), MNEMONIC_ATTR_NAME) == 0)
1219             {
1220               found = true;
1221               break;
1222             }
1223
1224       if (!found)
1225         gen_mnemonic_setattr (mnemonic_htab, insn);
1226     }
1227
1228   /* Add the user defined values to the hash table.  */
1229   str = XSTR (mnemonic_attr, 1);
1230   while ((p = scan_comma_elt (&str)) != NULL)
1231     add_mnemonic_string (mnemonic_htab, p, str - p);
1232
1233   htab_traverse (mnemonic_htab, mnemonic_htab_callback, NULL);
1234
1235   /* Replace the last ',' with the zero end character.  */
1236   *((char *)obstack_next_free (&string_obstack) - 1) = '\0';
1237   XSTR (mnemonic_attr, 1) = XOBFINISH (&string_obstack, char *);
1238 }
1239
1240 /* The entry point for initializing the reader.  */
1241
1242 bool
1243 init_rtx_reader_args_cb (int argc, char **argv,
1244                          bool (*parse_opt) (const char *))
1245 {
1246   /* Prepare to read input.  */
1247   condition_table = htab_create (500, hash_c_test, cmp_c_test, NULL);
1248   init_predicate_table ();
1249   obstack_init (rtl_obstack);
1250   sequence_num = 0;
1251
1252   read_md_files (argc, argv, parse_opt, rtx_handle_directive);
1253
1254   /* Process define_cond_exec patterns.  */
1255   if (define_cond_exec_queue != NULL)
1256     process_define_cond_exec ();
1257
1258   if (define_attr_queue != NULL)
1259     gen_mnemonic_attr ();
1260
1261   return !have_error;
1262 }
1263
1264 /* Programs that don't have their own options can use this entry point
1265    instead.  */
1266 bool
1267 init_rtx_reader_args (int argc, char **argv)
1268 {
1269   return init_rtx_reader_args_cb (argc, argv, 0);
1270 }
1271 \f
1272 /* The entry point for reading a single rtx from an md file.  */
1273
1274 rtx
1275 read_md_rtx (int *lineno, int *seqnr)
1276 {
1277   struct queue_elem **queue, *elem;
1278   rtx desc;
1279
1280  discard:
1281
1282   /* Read all patterns from a given queue before moving on to the next.  */
1283   if (define_attr_queue != NULL)
1284     queue = &define_attr_queue;
1285   else if (define_pred_queue != NULL)
1286     queue = &define_pred_queue;
1287   else if (define_insn_queue != NULL)
1288     queue = &define_insn_queue;
1289   else if (other_queue != NULL)
1290     queue = &other_queue;
1291   else
1292     return NULL_RTX;
1293
1294   elem = *queue;
1295   *queue = elem->next;
1296   desc = elem->data;
1297   read_md_filename = elem->filename;
1298   *lineno = elem->lineno;
1299   *seqnr = sequence_num;
1300
1301   free (elem);
1302
1303   /* Discard insn patterns which we know can never match (because
1304      their C test is provably always false).  If insn_elision is
1305      false, our caller needs to see all the patterns.  Note that the
1306      elided patterns are never counted by the sequence numbering; it
1307      is the caller's responsibility, when insn_elision is false, not
1308      to use elided pattern numbers for anything.  */
1309   switch (GET_CODE (desc))
1310     {
1311     case DEFINE_INSN:
1312     case DEFINE_EXPAND:
1313       if (maybe_eval_c_test (XSTR (desc, 2)) != 0)
1314         sequence_num++;
1315       else if (insn_elision)
1316         goto discard;
1317
1318       /* *seqnr is used here so the name table will match caller's
1319          idea of insn numbering, whether or not elision is active.  */
1320       record_insn_name (*seqnr, XSTR (desc, 0));
1321       break;
1322
1323     case DEFINE_SPLIT:
1324     case DEFINE_PEEPHOLE:
1325     case DEFINE_PEEPHOLE2:
1326       if (maybe_eval_c_test (XSTR (desc, 1)) != 0)
1327         sequence_num++;
1328       else if (insn_elision)
1329             goto discard;
1330       break;
1331
1332     default:
1333       break;
1334     }
1335
1336   return desc;
1337 }
1338
1339 /* Helper functions for insn elision.  */
1340
1341 /* Compute a hash function of a c_test structure, which is keyed
1342    by its ->expr field.  */
1343 hashval_t
1344 hash_c_test (const void *x)
1345 {
1346   const struct c_test *a = (const struct c_test *) x;
1347   const unsigned char *base, *s = (const unsigned char *) a->expr;
1348   hashval_t hash;
1349   unsigned char c;
1350   unsigned int len;
1351
1352   base = s;
1353   hash = 0;
1354
1355   while ((c = *s++) != '\0')
1356     {
1357       hash += c + (c << 17);
1358       hash ^= hash >> 2;
1359     }
1360
1361   len = s - base;
1362   hash += len + (len << 17);
1363   hash ^= hash >> 2;
1364
1365   return hash;
1366 }
1367
1368 /* Compare two c_test expression structures.  */
1369 int
1370 cmp_c_test (const void *x, const void *y)
1371 {
1372   const struct c_test *a = (const struct c_test *) x;
1373   const struct c_test *b = (const struct c_test *) y;
1374
1375   return !strcmp (a->expr, b->expr);
1376 }
1377
1378 /* Given a string representing a C test expression, look it up in the
1379    condition_table and report whether or not its value is known
1380    at compile time.  Returns a tristate: 1 for known true, 0 for
1381    known false, -1 for unknown.  */
1382 int
1383 maybe_eval_c_test (const char *expr)
1384 {
1385   const struct c_test *test;
1386   struct c_test dummy;
1387
1388   if (expr[0] == 0)
1389     return 1;
1390
1391   dummy.expr = expr;
1392   test = (const struct c_test *)htab_find (condition_table, &dummy);
1393   if (!test)
1394     return -1;
1395   return test->value;
1396 }
1397
1398 /* Record the C test expression EXPR in the condition_table, with
1399    value VAL.  Duplicates clobber previous entries.  */
1400
1401 void
1402 add_c_test (const char *expr, int value)
1403 {
1404   struct c_test *test;
1405
1406   if (expr[0] == 0)
1407     return;
1408
1409   test = XNEW (struct c_test);
1410   test->expr = expr;
1411   test->value = value;
1412
1413   *(htab_find_slot (condition_table, test, INSERT)) = test;
1414 }
1415
1416 /* For every C test, call CALLBACK with two arguments: a pointer to
1417    the condition structure and INFO.  Stops when CALLBACK returns zero.  */
1418 void
1419 traverse_c_tests (htab_trav callback, void *info)
1420 {
1421   if (condition_table)
1422     htab_traverse (condition_table, callback, info);
1423 }
1424
1425 /* Helper functions for define_predicate and define_special_predicate
1426    processing.  Shared between genrecog.c and genpreds.c.  */
1427
1428 static htab_t predicate_table;
1429 struct pred_data *first_predicate;
1430 static struct pred_data **last_predicate = &first_predicate;
1431
1432 static hashval_t
1433 hash_struct_pred_data (const void *ptr)
1434 {
1435   return htab_hash_string (((const struct pred_data *)ptr)->name);
1436 }
1437
1438 static int
1439 eq_struct_pred_data (const void *a, const void *b)
1440 {
1441   return !strcmp (((const struct pred_data *)a)->name,
1442                   ((const struct pred_data *)b)->name);
1443 }
1444
1445 struct pred_data *
1446 lookup_predicate (const char *name)
1447 {
1448   struct pred_data key;
1449   key.name = name;
1450   return (struct pred_data *) htab_find (predicate_table, &key);
1451 }
1452
1453 /* Record that predicate PRED can accept CODE.  */
1454
1455 void
1456 add_predicate_code (struct pred_data *pred, enum rtx_code code)
1457 {
1458   if (!pred->codes[code])
1459     {
1460       pred->num_codes++;
1461       pred->codes[code] = true;
1462
1463       if (GET_RTX_CLASS (code) != RTX_CONST_OBJ)
1464         pred->allows_non_const = true;
1465
1466       if (code != REG
1467           && code != SUBREG
1468           && code != MEM
1469           && code != CONCAT
1470           && code != PARALLEL
1471           && code != STRICT_LOW_PART)
1472         pred->allows_non_lvalue = true;
1473
1474       if (pred->num_codes == 1)
1475         pred->singleton = code;
1476       else if (pred->num_codes == 2)
1477         pred->singleton = UNKNOWN;
1478     }
1479 }
1480
1481 void
1482 add_predicate (struct pred_data *pred)
1483 {
1484   void **slot = htab_find_slot (predicate_table, pred, INSERT);
1485   if (*slot)
1486     {
1487       error ("duplicate predicate definition for '%s'", pred->name);
1488       return;
1489     }
1490   *slot = pred;
1491   *last_predicate = pred;
1492   last_predicate = &pred->next;
1493 }
1494
1495 /* This array gives the initial content of the predicate table.  It
1496    has entries for all predicates defined in recog.c.  */
1497
1498 struct std_pred_table
1499 {
1500   const char *name;
1501   bool special;
1502   bool allows_const_p;
1503   RTX_CODE codes[NUM_RTX_CODE];
1504 };
1505
1506 static const struct std_pred_table std_preds[] = {
1507   {"general_operand", false, true, {SUBREG, REG, MEM}},
1508   {"address_operand", true, true, {SUBREG, REG, MEM, PLUS, MINUS, MULT}},
1509   {"register_operand", false, false, {SUBREG, REG}},
1510   {"pmode_register_operand", true, false, {SUBREG, REG}},
1511   {"scratch_operand", false, false, {SCRATCH, REG}},
1512   {"immediate_operand", false, true, {UNKNOWN}},
1513   {"const_int_operand", false, false, {CONST_INT}},
1514   {"const_double_operand", false, false, {CONST_INT, CONST_DOUBLE}},
1515   {"nonimmediate_operand", false, false, {SUBREG, REG, MEM}},
1516   {"nonmemory_operand", false, true, {SUBREG, REG}},
1517   {"push_operand", false, false, {MEM}},
1518   {"pop_operand", false, false, {MEM}},
1519   {"memory_operand", false, false, {SUBREG, MEM}},
1520   {"indirect_operand", false, false, {SUBREG, MEM}},
1521   {"ordered_comparison_operator", false, false, {EQ, NE,
1522                                                  LE, LT, GE, GT,
1523                                                  LEU, LTU, GEU, GTU}},
1524   {"comparison_operator", false, false, {EQ, NE,
1525                                          LE, LT, GE, GT,
1526                                          LEU, LTU, GEU, GTU,
1527                                          UNORDERED, ORDERED,
1528                                          UNEQ, UNGE, UNGT,
1529                                          UNLE, UNLT, LTGT}}
1530 };
1531 #define NUM_KNOWN_STD_PREDS ARRAY_SIZE (std_preds)
1532
1533 /* Initialize the table of predicate definitions, starting with
1534    the information we have on generic predicates.  */
1535
1536 static void
1537 init_predicate_table (void)
1538 {
1539   size_t i, j;
1540   struct pred_data *pred;
1541
1542   predicate_table = htab_create_alloc (37, hash_struct_pred_data,
1543                                        eq_struct_pred_data, 0,
1544                                        xcalloc, free);
1545
1546   for (i = 0; i < NUM_KNOWN_STD_PREDS; i++)
1547     {
1548       pred = XCNEW (struct pred_data);
1549       pred->name = std_preds[i].name;
1550       pred->special = std_preds[i].special;
1551
1552       for (j = 0; std_preds[i].codes[j] != 0; j++)
1553         add_predicate_code (pred, std_preds[i].codes[j]);
1554
1555       if (std_preds[i].allows_const_p)
1556         for (j = 0; j < NUM_RTX_CODE; j++)
1557           if (GET_RTX_CLASS (j) == RTX_CONST_OBJ)
1558             add_predicate_code (pred, (enum rtx_code) j);
1559
1560       add_predicate (pred);
1561     }
1562 }
1563 \f
1564 /* These functions allow linkage with print-rtl.c.  Also, some generators
1565    like to annotate their output with insn names.  */
1566
1567 /* Holds an array of names indexed by insn_code_number.  */
1568 static char **insn_name_ptr = 0;
1569 static int insn_name_ptr_size = 0;
1570
1571 const char *
1572 get_insn_name (int code)
1573 {
1574   if (code < insn_name_ptr_size)
1575     return insn_name_ptr[code];
1576   else
1577     return NULL;
1578 }
1579
1580 static void
1581 record_insn_name (int code, const char *name)
1582 {
1583   static const char *last_real_name = "insn";
1584   static int last_real_code = 0;
1585   char *new_name;
1586
1587   if (insn_name_ptr_size <= code)
1588     {
1589       int new_size;
1590       new_size = (insn_name_ptr_size ? insn_name_ptr_size * 2 : 512);
1591       insn_name_ptr = XRESIZEVEC (char *, insn_name_ptr, new_size);
1592       memset (insn_name_ptr + insn_name_ptr_size, 0,
1593               sizeof(char *) * (new_size - insn_name_ptr_size));
1594       insn_name_ptr_size = new_size;
1595     }
1596
1597   if (!name || name[0] == '\0')
1598     {
1599       new_name = XNEWVAR (char, strlen (last_real_name) + 10);
1600       sprintf (new_name, "%s+%d", last_real_name, code - last_real_code);
1601     }
1602   else
1603     {
1604       last_real_name = new_name = xstrdup (name);
1605       last_real_code = code;
1606     }
1607
1608   insn_name_ptr[code] = new_name;
1609 }
1610 \f
1611 /* Make STATS describe the operands that appear in rtx X.  */
1612
1613 static void
1614 get_pattern_stats_1 (struct pattern_stats *stats, rtx x)
1615 {
1616   RTX_CODE code;
1617   int i;
1618   int len;
1619   const char *fmt;
1620
1621   if (x == NULL_RTX)
1622     return;
1623
1624   code = GET_CODE (x);
1625   switch (code)
1626     {
1627     case MATCH_OPERAND:
1628     case MATCH_OPERATOR:
1629     case MATCH_PARALLEL:
1630       stats->max_opno = MAX (stats->max_opno, XINT (x, 0));
1631       break;
1632
1633     case MATCH_DUP:
1634     case MATCH_OP_DUP:
1635     case MATCH_PAR_DUP:
1636       stats->num_dups++;
1637       stats->max_dup_opno = MAX (stats->max_dup_opno, XINT (x, 0));
1638       break;
1639
1640     case MATCH_SCRATCH:
1641       stats->max_scratch_opno = MAX (stats->max_scratch_opno, XINT (x, 0));
1642       break;
1643
1644     default:
1645       break;
1646     }
1647
1648   fmt = GET_RTX_FORMAT (code);
1649   len = GET_RTX_LENGTH (code);
1650   for (i = 0; i < len; i++)
1651     {
1652       if (fmt[i] == 'e' || fmt[i] == 'u')
1653         get_pattern_stats_1 (stats, XEXP (x, i));
1654       else if (fmt[i] == 'E')
1655         {
1656           int j;
1657           for (j = 0; j < XVECLEN (x, i); j++)
1658             get_pattern_stats_1 (stats, XVECEXP (x, i, j));
1659         }
1660     }
1661 }
1662
1663 /* Make STATS describe the operands that appear in instruction pattern
1664    PATTERN.  */
1665
1666 void
1667 get_pattern_stats (struct pattern_stats *stats, rtvec pattern)
1668 {
1669   int i, len;
1670
1671   stats->max_opno = -1;
1672   stats->max_dup_opno = -1;
1673   stats->max_scratch_opno = -1;
1674   stats->num_dups = 0;
1675
1676   len = GET_NUM_ELEM (pattern);
1677   for (i = 0; i < len; i++)
1678     get_pattern_stats_1 (stats, RTVEC_ELT (pattern, i));
1679
1680   stats->num_generator_args = stats->max_opno + 1;
1681   stats->num_insn_operands = MAX (stats->max_opno,
1682                                   stats->max_scratch_opno) + 1;
1683   stats->num_operand_vars = MAX (stats->max_opno,
1684                                   MAX (stats->max_dup_opno,
1685                                        stats->max_scratch_opno)) + 1;
1686 }