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