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