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 static struct queue_elem *define_attr_queue;
  64 static struct queue_elem **define_attr_tail = &define_attr_queue;
  65 static struct queue_elem *define_pred_queue;
  66 static struct queue_elem **define_pred_tail = &define_pred_queue;
  67 static struct queue_elem *define_insn_queue;
  68 static struct queue_elem **define_insn_tail = &define_insn_queue;
  69 static struct queue_elem *define_cond_exec_queue;
  70 static struct queue_elem **define_cond_exec_tail = &define_cond_exec_queue;
  71 static struct queue_elem *other_queue;
  72 static struct queue_elem **other_tail = &other_queue;
  73
  74 static struct queue_elem *queue_pattern (rtx, struct queue_elem ***,
  75                                          const char *, int);
  76
  77 static void remove_constraints (rtx);
  78 static void process_rtx (rtx, int);
  79
  80 static int is_predicable (struct queue_elem *);
  81 static void identify_predicable_attribute (void);
  82 static int n_alternatives (const char *);
  83 static void collect_insn_data (rtx, int *, int *);
  84 static rtx alter_predicate_for_insn (rtx, int, int, int);
  85 static const char *alter_test_for_insn (struct queue_elem *,
  86                                         struct queue_elem *);
  87 static char *shift_output_template (char *, const char *, int);
  88 static const char *alter_output_for_insn (struct queue_elem *,
  89                                           struct queue_elem *,
  90                                           int, int);
  91 static void process_one_cond_exec (struct queue_elem *);
  92 static void process_define_cond_exec (void);
  93 static void init_predicate_table (void);
  94 static void record_insn_name (int, const char *);
  95 \f
  96 /* Make a version of gen_rtx_CONST_INT so that GEN_INT can be used in
  97    the gensupport programs.  */
  98
  99 rtx
 100 gen_rtx_CONST_INT (enum machine_mode ARG_UNUSED (mode),
 101                    HOST_WIDE_INT arg)
 102 {
 103   rtx rt = rtx_alloc (CONST_INT);
 104
 105   XWINT (rt, 0) = arg;
 106   return rt;
 107 }
 108 \f
 109 /* Queue PATTERN on LIST_TAIL.  Return the address of the new queue
 110    element.  */
 111
 112 static struct queue_elem *
 113 queue_pattern (rtx pattern, struct queue_elem ***list_tail,
 114                const char *filename, int lineno)
 115 {
 116   struct queue_elem *e = XNEW(struct queue_elem);
 117   e->data = pattern;
 118   e->filename = filename;
 119   e->lineno = lineno;
 120   e->next = NULL;
 121   e->split = NULL;
 122   **list_tail = e;
 123   *list_tail = &e->next;
 124   return e;
 125 }
 126
 127 /* Recursively remove constraints from an rtx.  */
 128
 129 static void
 130 remove_constraints (rtx part)
 131 {
 132   int i, j;
 133   const char *format_ptr;
 134
 135   if (part == 0)
 136     return;
 137
 138   if (GET_CODE (part) == MATCH_OPERAND)
 139     XSTR (part, 2) = "";
 140   else if (GET_CODE (part) == MATCH_SCRATCH)
 141     XSTR (part, 1) = "";
 142
 143   format_ptr = GET_RTX_FORMAT (GET_CODE (part));
 144
 145   for (i = 0; i < GET_RTX_LENGTH (GET_CODE (part)); i++)
 146     switch (*format_ptr++)
 147       {
 148       case 'e':
 149       case 'u':
 150         remove_constraints (XEXP (part, i));
 151         break;
 152       case 'E':
 153         if (XVEC (part, i) != NULL)
 154           for (j = 0; j < XVECLEN (part, i); j++)
 155             remove_constraints (XVECEXP (part, i, j));
 156         break;
 157       }
 158 }
 159
 160 /* Process a top level rtx in some way, queuing as appropriate.  */
 161
 162 static void
 163 process_rtx (rtx desc, int lineno)
 164 {
 165   switch (GET_CODE (desc))
 166     {
 167     case DEFINE_INSN:
 168       queue_pattern (desc, &define_insn_tail, read_md_filename, lineno);
 169       break;
 170
 171     case DEFINE_COND_EXEC:
 172       queue_pattern (desc, &define_cond_exec_tail, read_md_filename, lineno);
 173       break;
 174
 175     case DEFINE_ATTR:
 176     case DEFINE_ENUM_ATTR:
 177       queue_pattern (desc, &define_attr_tail, read_md_filename, lineno);
 178       break;
 179
 180     case DEFINE_PREDICATE:
 181     case DEFINE_SPECIAL_PREDICATE:
 182     case DEFINE_CONSTRAINT:
 183     case DEFINE_REGISTER_CONSTRAINT:
 184     case DEFINE_MEMORY_CONSTRAINT:
 185     case DEFINE_ADDRESS_CONSTRAINT:
 186       queue_pattern (desc, &define_pred_tail, read_md_filename, lineno);
 187       break;
 188
 189     case DEFINE_INSN_AND_SPLIT:
 190       {
 191         const char *split_cond;
 192         rtx split;
 193         rtvec attr;
 194         int i;
 195         struct queue_elem *insn_elem;
 196         struct queue_elem *split_elem;
 197
 198         /* Create a split with values from the insn_and_split.  */
 199         split = rtx_alloc (DEFINE_SPLIT);
 200
 201         i = XVECLEN (desc, 1);
 202         XVEC (split, 0) = rtvec_alloc (i);
 203         while (--i >= 0)
 204           {
 205             XVECEXP (split, 0, i) = copy_rtx (XVECEXP (desc, 1, i));
 206             remove_constraints (XVECEXP (split, 0, i));
 207           }
 208
 209         /* If the split condition starts with "&&", append it to the
 210            insn condition to create the new split condition.  */
 211         split_cond = XSTR (desc, 4);
 212         if (split_cond[0] == '&' && split_cond[1] == '&')
 213           {
 214             copy_md_ptr_loc (split_cond + 2, split_cond);
 215             split_cond = join_c_conditions (XSTR (desc, 2), split_cond + 2);
 216           }
 217         XSTR (split, 1) = split_cond;
 218         XVEC (split, 2) = XVEC (desc, 5);
 219         XSTR (split, 3) = XSTR (desc, 6);
 220
 221         /* Fix up the DEFINE_INSN.  */
 222         attr = XVEC (desc, 7);
 223         PUT_CODE (desc, DEFINE_INSN);
 224         XVEC (desc, 4) = attr;
 225
 226         /* Queue them.  */
 227         insn_elem
 228           = queue_pattern (desc, &define_insn_tail, read_md_filename,
 229                            lineno);
 230         split_elem
 231           = queue_pattern (split, &other_tail, read_md_filename, lineno);
 232         insn_elem->split = split_elem;
 233         break;
 234       }
 235
 236     default:
 237       queue_pattern (desc, &other_tail, read_md_filename, lineno);
 238       break;
 239     }
 240 }
 241 \f
 242 /* Return true if attribute PREDICABLE is true for ELEM, which holds
 243    a DEFINE_INSN.  */
 244
 245 static int
 246 is_predicable (struct queue_elem *elem)
 247 {
 248   rtvec vec = XVEC (elem->data, 4);
 249   const char *value;
 250   int i;
 251
 252   if (! vec)
 253     return predicable_default;
 254
 255   for (i = GET_NUM_ELEM (vec) - 1; i >= 0; --i)
 256     {
 257       rtx sub = RTVEC_ELT (vec, i);
 258       switch (GET_CODE (sub))
 259         {
 260         case SET_ATTR:
 261           if (strcmp (XSTR (sub, 0), "predicable") == 0)
 262             {
 263               value = XSTR (sub, 1);
 264               goto found;
 265             }
 266           break;
 267
 268         case SET_ATTR_ALTERNATIVE:
 269           if (strcmp (XSTR (sub, 0), "predicable") == 0)
 270             {
 271               error_with_line (elem->lineno,
 272                                "multiple alternatives for `predicable'");
 273               return 0;
 274             }
 275           break;
 276
 277         case SET:
 278           if (GET_CODE (SET_DEST (sub)) != ATTR
 279               || strcmp (XSTR (SET_DEST (sub), 0), "predicable") != 0)
 280             break;
 281           sub = SET_SRC (sub);
 282           if (GET_CODE (sub) == CONST_STRING)
 283             {
 284               value = XSTR (sub, 0);
 285               goto found;
 286             }
 287
 288           /* ??? It would be possible to handle this if we really tried.
 289              It's not easy though, and I'm not going to bother until it
 290              really proves necessary.  */
 291           error_with_line (elem->lineno,
 292                            "non-constant value for `predicable'");
 293           return 0;
 294
 295         default:
 296           gcc_unreachable ();
 297         }
 298     }
 299
 300   return predicable_default;
 301
 302  found:
 303   /* Verify that predicability does not vary on the alternative.  */
 304   /* ??? It should be possible to handle this by simply eliminating
 305      the non-predicable alternatives from the insn.  FRV would like
 306      to do this.  Delay this until we've got the basics solid.  */
 307   if (strchr (value, ',') != NULL)
 308     {
 309       error_with_line (elem->lineno, "multiple alternatives for `predicable'");
 310       return 0;
 311     }
 312
 313   /* Find out which value we're looking at.  */
 314   if (strcmp (value, predicable_true) == 0)
 315     return 1;
 316   if (strcmp (value, predicable_false) == 0)
 317     return 0;
 318
 319   error_with_line (elem->lineno,
 320                    "unknown value `%s' for `predicable' attribute", value);
 321   return 0;
 322 }
 323
 324 /* Examine the attribute "predicable"; discover its boolean values
 325    and its default.  */
 326
 327 static void
 328 identify_predicable_attribute (void)
 329 {
 330   struct queue_elem *elem;
 331   char *p_true, *p_false;
 332   const char *value;
 333
 334   /* Look for the DEFINE_ATTR for `predicable', which must exist.  */
 335   for (elem = define_attr_queue; elem ; elem = elem->next)
 336     if (strcmp (XSTR (elem->data, 0), "predicable") == 0)
 337       goto found;
 338
 339   error_with_line (define_cond_exec_queue->lineno,
 340                    "attribute `predicable' not defined");
 341   return;
 342
 343  found:
 344   value = XSTR (elem->data, 1);
 345   p_false = xstrdup (value);
 346   p_true = strchr (p_false, ',');
 347   if (p_true == NULL || strchr (++p_true, ',') != NULL)
 348     {
 349       error_with_line (elem->lineno, "attribute `predicable' is not a boolean");
 350       if (p_false)
 351         free (p_false);
 352       return;
 353     }
 354   p_true[-1] = '\0';
 355
 356   predicable_true = p_true;
 357   predicable_false = p_false;
 358
 359   switch (GET_CODE (XEXP (elem->data, 2)))
 360     {
 361     case CONST_STRING:
 362       value = XSTR (XEXP (elem->data, 2), 0);
 363       break;
 364
 365     case CONST:
 366       error_with_line (elem->lineno, "attribute `predicable' cannot be const");
 367       if (p_false)
 368         free (p_false);
 369       return;
 370
 371     default:
 372       error_with_line (elem->lineno,
 373                        "attribute `predicable' must have a constant default");
 374       if (p_false)
 375         free (p_false);
 376       return;
 377     }
 378
 379   if (strcmp (value, p_true) == 0)
 380     predicable_default = 1;
 381   else if (strcmp (value, p_false) == 0)
 382     predicable_default = 0;
 383   else
 384     {
 385       error_with_line (elem->lineno,
 386                        "unknown value `%s' for `predicable' attribute", value);
 387       if (p_false)
 388         free (p_false);
 389     }
 390 }
 391
 392 /* Return the number of alternatives in constraint S.  */
 393
 394 static int
 395 n_alternatives (const char *s)
 396 {
 397   int n = 1;
 398
 399   if (s)
 400     while (*s)
 401       n += (*s++ == ',');
 402
 403   return n;
 404 }
 405
 406 /* Determine how many alternatives there are in INSN, and how many
 407    operands.  */
 408
 409 static void
 410 collect_insn_data (rtx pattern, int *palt, int *pmax)
 411 {
 412   const char *fmt;
 413   enum rtx_code code;
 414   int i, j, len;
 415
 416   code = GET_CODE (pattern);
 417   switch (code)
 418     {
 419     case MATCH_OPERAND:
 420       i = n_alternatives (XSTR (pattern, 2));
 421       *palt = (i > *palt ? i : *palt);
 422       /* Fall through.  */
 423
 424     case MATCH_OPERATOR:
 425     case MATCH_SCRATCH:
 426     case MATCH_PARALLEL:
 427       i = XINT (pattern, 0);
 428       if (i > *pmax)
 429         *pmax = i;
 430       break;
 431
 432     default:
 433       break;
 434     }
 435
 436   fmt = GET_RTX_FORMAT (code);
 437   len = GET_RTX_LENGTH (code);
 438   for (i = 0; i < len; i++)
 439     {
 440       switch (fmt[i])
 441         {
 442         case 'e': case 'u':
 443           collect_insn_data (XEXP (pattern, i), palt, pmax);
 444           break;
 445
 446         case 'V':
 447           if (XVEC (pattern, i) == NULL)
 448             break;
 449           /* Fall through.  */
 450         case 'E':
 451           for (j = XVECLEN (pattern, i) - 1; j >= 0; --j)
 452             collect_insn_data (XVECEXP (pattern, i, j), palt, pmax);
 453           break;
 454
 455         case 'i': case 'w': case '0': case 's': case 'S': case 'T':
 456           break;
 457
 458         default:
 459           gcc_unreachable ();
 460         }
 461     }
 462 }
 463
 464 static rtx
 465 alter_predicate_for_insn (rtx pattern, int alt, int max_op, int lineno)
 466 {
 467   const char *fmt;
 468   enum rtx_code code;
 469   int i, j, len;
 470
 471   code = GET_CODE (pattern);
 472   switch (code)
 473     {
 474     case MATCH_OPERAND:
 475       {
 476         const char *c = XSTR (pattern, 2);
 477
 478         if (n_alternatives (c) != 1)
 479           {
 480             error_with_line (lineno, "too many alternatives for operand %d",
 481                              XINT (pattern, 0));
 482             return NULL;
 483           }
 484
 485         /* Replicate C as needed to fill out ALT alternatives.  */
 486         if (c && *c && alt > 1)
 487           {
 488             size_t c_len = strlen (c);
 489             size_t len = alt * (c_len + 1);
 490             char *new_c = XNEWVEC(char, len);
 491
 492             memcpy (new_c, c, c_len);
 493             for (i = 1; i < alt; ++i)
 494               {
 495                 new_c[i * (c_len + 1) - 1] = ',';
 496                 memcpy (&new_c[i * (c_len + 1)], c, c_len);
 497               }
 498             new_c[len - 1] = '\0';
 499             XSTR (pattern, 2) = new_c;
 500           }
 501       }
 502       /* Fall through.  */
 503
 504     case MATCH_OPERATOR:
 505     case MATCH_SCRATCH:
 506     case MATCH_PARALLEL:
 507       XINT (pattern, 0) += max_op;
 508       break;
 509
 510     default:
 511       break;
 512     }
 513
 514   fmt = GET_RTX_FORMAT (code);
 515   len = GET_RTX_LENGTH (code);
 516   for (i = 0; i < len; i++)
 517     {
 518       rtx r;
 519
 520       switch (fmt[i])
 521         {
 522         case 'e': case 'u':
 523           r = alter_predicate_for_insn (XEXP (pattern, i), alt,
 524                                         max_op, lineno);
 525           if (r == NULL)
 526             return r;
 527           break;
 528
 529         case 'E':
 530           for (j = XVECLEN (pattern, i) - 1; j >= 0; --j)
 531             {
 532               r = alter_predicate_for_insn (XVECEXP (pattern, i, j),
 533                                             alt, max_op, lineno);
 534               if (r == NULL)
 535                 return r;
 536             }
 537           break;
 538
 539         case 'i': case 'w': case '0': case 's':
 540           break;
 541
 542         default:
 543           gcc_unreachable ();
 544         }
 545     }
 546
 547   return pattern;
 548 }
 549
 550 static const char *
 551 alter_test_for_insn (struct queue_elem *ce_elem,
 552                      struct queue_elem *insn_elem)
 553 {
 554   return join_c_conditions (XSTR (ce_elem->data, 1),
 555                             XSTR (insn_elem->data, 2));
 556 }
 557
 558 /* Adjust all of the operand numbers in SRC to match the shift they'll
 559    get from an operand displacement of DISP.  Return a pointer after the
 560    adjusted string.  */
 561
 562 static char *
 563 shift_output_template (char *dest, const char *src, int disp)
 564 {
 565   while (*src)
 566     {
 567       char c = *src++;
 568       *dest++ = c;
 569       if (c == '%')
 570         {
 571           c = *src++;
 572           if (ISDIGIT ((unsigned char) c))
 573             c += disp;
 574           else if (ISALPHA (c))
 575             {
 576               *dest++ = c;
 577               c = *src++ + disp;
 578             }
 579           *dest++ = c;
 580         }
 581     }
 582
 583   return dest;
 584 }
 585
 586 static const char *
 587 alter_output_for_insn (struct queue_elem *ce_elem,
 588                        struct queue_elem *insn_elem,
 589                        int alt, int max_op)
 590 {
 591   const char *ce_out, *insn_out;
 592   char *result, *p;
 593   size_t len, ce_len, insn_len;
 594
 595   /* ??? Could coordinate with genoutput to not duplicate code here.  */
 596
 597   ce_out = XSTR (ce_elem->data, 2);
 598   insn_out = XTMPL (insn_elem->data, 3);
 599   if (!ce_out || *ce_out == '\0')
 600     return insn_out;
 601
 602   ce_len = strlen (ce_out);
 603   insn_len = strlen (insn_out);
 604
 605   if (*insn_out == '*')
 606     /* You must take care of the predicate yourself.  */
 607     return insn_out;
 608
 609   if (*insn_out == '@')
 610     {
 611       len = (ce_len + 1) * alt + insn_len + 1;
 612       p = result = XNEWVEC(char, len);
 613
 614       do
 615         {
 616           do
 617             *p++ = *insn_out++;
 618           while (ISSPACE ((unsigned char) *insn_out));
 619
 620           if (*insn_out != '#')
 621             {
 622               p = shift_output_template (p, ce_out, max_op);
 623               *p++ = ' ';
 624             }
 625
 626           do
 627             *p++ = *insn_out++;
 628           while (*insn_out && *insn_out != '\n');
 629         }
 630       while (*insn_out);
 631       *p = '\0';
 632     }
 633   else
 634     {
 635       len = ce_len + 1 + insn_len + 1;
 636       result = XNEWVEC (char, len);
 637
 638       p = shift_output_template (result, ce_out, max_op);
 639       *p++ = ' ';
 640       memcpy (p, insn_out, insn_len + 1);
 641     }
 642
 643   return result;
 644 }
 645
 646 /* Replicate insns as appropriate for the given DEFINE_COND_EXEC.  */
 647
 648 static void
 649 process_one_cond_exec (struct queue_elem *ce_elem)
 650 {
 651   struct queue_elem *insn_elem;
 652   for (insn_elem = define_insn_queue; insn_elem ; insn_elem = insn_elem->next)
 653     {
 654       int alternatives, max_operand;
 655       rtx pred, insn, pattern, split;
 656       char *new_name;
 657       int i;
 658
 659       if (! is_predicable (insn_elem))
 660         continue;
 661
 662       alternatives = 1;
 663       max_operand = -1;
 664       collect_insn_data (insn_elem->data, &alternatives, &max_operand);
 665       max_operand += 1;
 666
 667       if (XVECLEN (ce_elem->data, 0) != 1)
 668         {
 669           error_with_line (ce_elem->lineno, "too many patterns in predicate");
 670           return;
 671         }
 672
 673       pred = copy_rtx (XVECEXP (ce_elem->data, 0, 0));
 674       pred = alter_predicate_for_insn (pred, alternatives, max_operand,
 675                                        ce_elem->lineno);
 676       if (pred == NULL)
 677         return;
 678
 679       /* Construct a new pattern for the new insn.  */
 680       insn = copy_rtx (insn_elem->data);
 681       new_name = XNEWVAR (char, strlen XSTR (insn_elem->data, 0) + 4);
 682       sprintf (new_name, "*p %s", XSTR (insn_elem->data, 0));
 683       XSTR (insn, 0) = new_name;
 684       pattern = rtx_alloc (COND_EXEC);
 685       XEXP (pattern, 0) = pred;
 686       if (XVECLEN (insn, 1) == 1)
 687         {
 688           XEXP (pattern, 1) = XVECEXP (insn, 1, 0);
 689           XVECEXP (insn, 1, 0) = pattern;
 690           PUT_NUM_ELEM (XVEC (insn, 1), 1);
 691         }
 692       else
 693         {
 694           XEXP (pattern, 1) = rtx_alloc (PARALLEL);
 695           XVEC (XEXP (pattern, 1), 0) = XVEC (insn, 1);
 696           XVEC (insn, 1) = rtvec_alloc (1);
 697           XVECEXP (insn, 1, 0) = pattern;
 698         }
 699
 700       XSTR (insn, 2) = alter_test_for_insn (ce_elem, insn_elem);
 701       XTMPL (insn, 3) = alter_output_for_insn (ce_elem, insn_elem,
 702                                               alternatives, max_operand);
 703
 704       /* ??? Set `predicable' to false.  Not crucial since it's really
 705          only used here, and we won't reprocess this new pattern.  */
 706
 707       /* Put the new pattern on the `other' list so that it
 708          (a) is not reprocessed by other define_cond_exec patterns
 709          (b) appears after all normal define_insn patterns.
 710
 711          ??? B is debatable.  If one has normal insns that match
 712          cond_exec patterns, they will be preferred over these
 713          generated patterns.  Whether this matters in practice, or if
 714          it's a good thing, or whether we should thread these new
 715          patterns into the define_insn chain just after their generator
 716          is something we'll have to experiment with.  */
 717
 718       queue_pattern (insn, &other_tail, insn_elem->filename,
 719                      insn_elem->lineno);
 720
 721       if (!insn_elem->split)
 722         continue;
 723
 724       /* If the original insn came from a define_insn_and_split,
 725          generate a new split to handle the predicated insn.  */
 726       split = copy_rtx (insn_elem->split->data);
 727       /* Predicate the pattern matched by the split.  */
 728       pattern = rtx_alloc (COND_EXEC);
 729       XEXP (pattern, 0) = pred;
 730       if (XVECLEN (split, 0) == 1)
 731         {
 732           XEXP (pattern, 1) = XVECEXP (split, 0, 0);
 733           XVECEXP (split, 0, 0) = pattern;
 734           PUT_NUM_ELEM (XVEC (split, 0), 1);
 735         }
 736       else
 737         {
 738           XEXP (pattern, 1) = rtx_alloc (PARALLEL);
 739           XVEC (XEXP (pattern, 1), 0) = XVEC (split, 0);
 740           XVEC (split, 0) = rtvec_alloc (1);
 741           XVECEXP (split, 0, 0) = pattern;
 742         }
 743       /* Predicate all of the insns generated by the split.  */
 744       for (i = 0; i < XVECLEN (split, 2); i++)
 745         {
 746           pattern = rtx_alloc (COND_EXEC);
 747           XEXP (pattern, 0) = pred;
 748           XEXP (pattern, 1) = XVECEXP (split, 2, i);
 749           XVECEXP (split, 2, i) = pattern;
 750         }
 751       /* Add the new split to the queue.  */
 752       queue_pattern (split, &other_tail, read_md_filename,
 753                      insn_elem->split->lineno);
 754     }
 755 }
 756
 757 /* If we have any DEFINE_COND_EXEC patterns, expand the DEFINE_INSN
 758    patterns appropriately.  */
 759
 760 static void
 761 process_define_cond_exec (void)
 762 {
 763   struct queue_elem *elem;
 764
 765   identify_predicable_attribute ();
 766   if (have_error)
 767     return;
 768
 769   for (elem = define_cond_exec_queue; elem ; elem = elem->next)
 770     process_one_cond_exec (elem);
 771 }
 772 \f
 773 /* A read_md_files callback for reading an rtx.  */
 774
 775 static void
 776 rtx_handle_directive (int lineno, const char *rtx_name)
 777 {
 778   rtx queue, x;
 779
 780   if (read_rtx (rtx_name, &queue))
 781     for (x = queue; x; x = XEXP (x, 1))
 782       process_rtx (XEXP (x, 0), lineno);
 783 }
 784
 785 /* The entry point for initializing the reader.  */
 786
 787 bool
 788 init_rtx_reader_args_cb (int argc, char **argv,
 789                          bool (*parse_opt) (const char *))
 790 {
 791   /* Prepare to read input.  */
 792   condition_table = htab_create (500, hash_c_test, cmp_c_test, NULL);
 793   init_predicate_table ();
 794   obstack_init (rtl_obstack);
 795   sequence_num = 0;
 796
 797   read_md_files (argc, argv, parse_opt, rtx_handle_directive);
 798
 799   /* Process define_cond_exec patterns.  */
 800   if (define_cond_exec_queue != NULL)
 801     process_define_cond_exec ();
 802
 803   return !have_error;
 804 }
 805
 806 /* Programs that don't have their own options can use this entry point
 807    instead.  */
 808 bool
 809 init_rtx_reader_args (int argc, char **argv)
 810 {
 811   return init_rtx_reader_args_cb (argc, argv, 0);
 812 }
 813 \f
 814 /* The entry point for reading a single rtx from an md file.  */
 815
 816 rtx
 817 read_md_rtx (int *lineno, int *seqnr)
 818 {
 819   struct queue_elem **queue, *elem;
 820   rtx desc;
 821
 822  discard:
 823
 824   /* Read all patterns from a given queue before moving on to the next.  */
 825   if (define_attr_queue != NULL)
 826     queue = &define_attr_queue;
 827   else if (define_pred_queue != NULL)
 828     queue = &define_pred_queue;
 829   else if (define_insn_queue != NULL)
 830     queue = &define_insn_queue;
 831   else if (other_queue != NULL)
 832     queue = &other_queue;
 833   else
 834     return NULL_RTX;
 835
 836   elem = *queue;
 837   *queue = elem->next;
 838   desc = elem->data;
 839   read_md_filename = elem->filename;
 840   *lineno = elem->lineno;
 841   *seqnr = sequence_num;
 842
 843   free (elem);
 844
 845   /* Discard insn patterns which we know can never match (because
 846      their C test is provably always false).  If insn_elision is
 847      false, our caller needs to see all the patterns.  Note that the
 848      elided patterns are never counted by the sequence numbering; it
 849      it is the caller's responsibility, when insn_elision is false, not
 850      to use elided pattern numbers for anything.  */
 851   switch (GET_CODE (desc))
 852     {
 853     case DEFINE_INSN:
 854     case DEFINE_EXPAND:
 855       if (maybe_eval_c_test (XSTR (desc, 2)) != 0)
 856         sequence_num++;
 857       else if (insn_elision)
 858         goto discard;
 859
 860       /* *seqnr is used here so the name table will match caller's
 861          idea of insn numbering, whether or not elision is active.  */
 862       record_insn_name (*seqnr, XSTR (desc, 0));
 863       break;
 864
 865     case DEFINE_SPLIT:
 866     case DEFINE_PEEPHOLE:
 867     case DEFINE_PEEPHOLE2:
 868       if (maybe_eval_c_test (XSTR (desc, 1)) != 0)
 869         sequence_num++;
 870       else if (insn_elision)
 871             goto discard;
 872       break;
 873
 874     default:
 875       break;
 876     }
 877
 878   return desc;
 879 }
 880
 881 /* Helper functions for insn elision.  */
 882
 883 /* Compute a hash function of a c_test structure, which is keyed
 884    by its ->expr field.  */
 885 hashval_t
 886 hash_c_test (const void *x)
 887 {
 888   const struct c_test *a = (const struct c_test *) x;
 889   const unsigned char *base, *s = (const unsigned char *) a->expr;
 890   hashval_t hash;
 891   unsigned char c;
 892   unsigned int len;
 893
 894   base = s;
 895   hash = 0;
 896
 897   while ((c = *s++) != '\0')
 898     {
 899       hash += c + (c << 17);
 900       hash ^= hash >> 2;
 901     }
 902
 903   len = s - base;
 904   hash += len + (len << 17);
 905   hash ^= hash >> 2;
 906
 907   return hash;
 908 }
 909
 910 /* Compare two c_test expression structures.  */
 911 int
 912 cmp_c_test (const void *x, const void *y)
 913 {
 914   const struct c_test *a = (const struct c_test *) x;
 915   const struct c_test *b = (const struct c_test *) y;
 916
 917   return !strcmp (a->expr, b->expr);
 918 }
 919
 920 /* Given a string representing a C test expression, look it up in the
 921    condition_table and report whether or not its value is known
 922    at compile time.  Returns a tristate: 1 for known true, 0 for
 923    known false, -1 for unknown.  */
 924 int
 925 maybe_eval_c_test (const char *expr)
 926 {
 927   const struct c_test *test;
 928   struct c_test dummy;
 929
 930   if (expr[0] == 0)
 931     return 1;
 932
 933   dummy.expr = expr;
 934   test = (const struct c_test *)htab_find (condition_table, &dummy);
 935   if (!test)
 936     return -1;
 937   return test->value;
 938 }
 939
 940 /* Record the C test expression EXPR in the condition_table, with
 941    value VAL.  Duplicates clobber previous entries.  */
 942
 943 void
 944 add_c_test (const char *expr, int value)
 945 {
 946   struct c_test *test;
 947
 948   if (expr[0] == 0)
 949     return;
 950
 951   test = XNEW (struct c_test);
 952   test->expr = expr;
 953   test->value = value;
 954
 955   *(htab_find_slot (condition_table, test, INSERT)) = test;
 956 }
 957
 958 /* For every C test, call CALLBACK with two arguments: a pointer to
 959    the condition structure and INFO.  Stops when CALLBACK returns zero.  */
 960 void
 961 traverse_c_tests (htab_trav callback, void *info)
 962 {
 963   if (condition_table)
 964     htab_traverse (condition_table, callback, info);
 965 }
 966
 967 /* Helper functions for define_predicate and define_special_predicate
 968    processing.  Shared between genrecog.c and genpreds.c.  */
 969
 970 static htab_t predicate_table;
 971 struct pred_data *first_predicate;
 972 static struct pred_data **last_predicate = &first_predicate;
 973
 974 static hashval_t
 975 hash_struct_pred_data (const void *ptr)
 976 {
 977   return htab_hash_string (((const struct pred_data *)ptr)->name);
 978 }
 979
 980 static int
 981 eq_struct_pred_data (const void *a, const void *b)
 982 {
 983   return !strcmp (((const struct pred_data *)a)->name,
 984                   ((const struct pred_data *)b)->name);
 985 }
 986
 987 struct pred_data *
 988 lookup_predicate (const char *name)
 989 {
 990   struct pred_data key;
 991   key.name = name;
 992   return (struct pred_data *) htab_find (predicate_table, &key);
 993 }
 994
 995 /* Record that predicate PRED can accept CODE.  */
 996
 997 void
 998 add_predicate_code (struct pred_data *pred, enum rtx_code code)
 999 {
1000   if (!pred->codes[code])
1001     {
1002       pred->num_codes++;
1003       pred->codes[code] = true;
1004
1005       if (GET_RTX_CLASS (code) != RTX_CONST_OBJ)
1006         pred->allows_non_const = true;
1007
1008       if (code != REG
1009           && code != SUBREG
1010           && code != MEM
1011           && code != CONCAT
1012           && code != PARALLEL
1013           && code != STRICT_LOW_PART)
1014         pred->allows_non_lvalue = true;
1015
1016       if (pred->num_codes == 1)
1017         pred->singleton = code;
1018       else if (pred->num_codes == 2)
1019         pred->singleton = UNKNOWN;
1020     }
1021 }
1022
1023 void
1024 add_predicate (struct pred_data *pred)
1025 {
1026   void **slot = htab_find_slot (predicate_table, pred, INSERT);
1027   if (*slot)
1028     {
1029       error ("duplicate predicate definition for '%s'", pred->name);
1030       return;
1031     }
1032   *slot = pred;
1033   *last_predicate = pred;
1034   last_predicate = &pred->next;
1035 }
1036
1037 /* This array gives the initial content of the predicate table.  It
1038    has entries for all predicates defined in recog.c.  */
1039
1040 struct std_pred_table
1041 {
1042   const char *name;
1043   bool special;
1044   bool allows_const_p;
1045   RTX_CODE codes[NUM_RTX_CODE];
1046 };
1047
1048 static const struct std_pred_table std_preds[] = {
1049   {"general_operand", false, true, {SUBREG, REG, MEM}},
1050   {"address_operand", true, true, {SUBREG, REG, MEM, PLUS, MINUS, MULT}},
1051   {"register_operand", false, false, {SUBREG, REG}},
1052   {"pmode_register_operand", true, false, {SUBREG, REG}},
1053   {"scratch_operand", false, false, {SCRATCH, REG}},
1054   {"immediate_operand", false, true, {UNKNOWN}},
1055   {"const_int_operand", false, false, {CONST_INT}},
1056   {"const_double_operand", false, false, {CONST_INT, CONST_DOUBLE}},
1057   {"nonimmediate_operand", false, false, {SUBREG, REG, MEM}},
1058   {"nonmemory_operand", false, true, {SUBREG, REG}},
1059   {"push_operand", false, false, {MEM}},
1060   {"pop_operand", false, false, {MEM}},
1061   {"memory_operand", false, false, {SUBREG, MEM}},
1062   {"indirect_operand", false, false, {SUBREG, MEM}},
1063   {"ordered_comparison_operator", false, false, {EQ, NE,
1064                                                  LE, LT, GE, GT,
1065                                                  LEU, LTU, GEU, GTU}},
1066   {"comparison_operator", false, false, {EQ, NE,
1067                                          LE, LT, GE, GT,
1068                                          LEU, LTU, GEU, GTU,
1069                                          UNORDERED, ORDERED,
1070                                          UNEQ, UNGE, UNGT,
1071                                          UNLE, UNLT, LTGT}}
1072 };
1073 #define NUM_KNOWN_STD_PREDS ARRAY_SIZE (std_preds)
1074
1075 /* Initialize the table of predicate definitions, starting with
1076    the information we have on generic predicates.  */
1077
1078 static void
1079 init_predicate_table (void)
1080 {
1081   size_t i, j;
1082   struct pred_data *pred;
1083
1084   predicate_table = htab_create_alloc (37, hash_struct_pred_data,
1085                                        eq_struct_pred_data, 0,
1086                                        xcalloc, free);
1087
1088   for (i = 0; i < NUM_KNOWN_STD_PREDS; i++)
1089     {
1090       pred = XCNEW (struct pred_data);
1091       pred->name = std_preds[i].name;
1092       pred->special = std_preds[i].special;
1093
1094       for (j = 0; std_preds[i].codes[j] != 0; j++)
1095         add_predicate_code (pred, std_preds[i].codes[j]);
1096
1097       if (std_preds[i].allows_const_p)
1098         for (j = 0; j < NUM_RTX_CODE; j++)
1099           if (GET_RTX_CLASS (j) == RTX_CONST_OBJ)
1100             add_predicate_code (pred, (enum rtx_code) j);
1101
1102       add_predicate (pred);
1103     }
1104 }
1105 \f
1106 /* These functions allow linkage with print-rtl.c.  Also, some generators
1107    like to annotate their output with insn names.  */
1108
1109 /* Holds an array of names indexed by insn_code_number.  */
1110 static char **insn_name_ptr = 0;
1111 static int insn_name_ptr_size = 0;
1112
1113 const char *
1114 get_insn_name (int code)
1115 {
1116   if (code < insn_name_ptr_size)
1117     return insn_name_ptr[code];
1118   else
1119     return NULL;
1120 }
1121
1122 static void
1123 record_insn_name (int code, const char *name)
1124 {
1125   static const char *last_real_name = "insn";
1126   static int last_real_code = 0;
1127   char *new_name;
1128
1129   if (insn_name_ptr_size <= code)
1130     {
1131       int new_size;
1132       new_size = (insn_name_ptr_size ? insn_name_ptr_size * 2 : 512);
1133       insn_name_ptr = XRESIZEVEC (char *, insn_name_ptr, new_size);
1134       memset (insn_name_ptr + insn_name_ptr_size, 0,
1135               sizeof(char *) * (new_size - insn_name_ptr_size));
1136       insn_name_ptr_size = new_size;
1137     }
1138
1139   if (!name || name[0] == '\0')
1140     {
1141       new_name = XNEWVAR (char, strlen (last_real_name) + 10);
1142       sprintf (new_name, "%s+%d", last_real_name, code - last_real_code);
1143     }
1144   else
1145     {
1146       last_real_name = new_name = xstrdup (name);
1147       last_real_code = code;
1148     }
1149
1150   insn_name_ptr[code] = new_name;
1151 }