gcc/genattrtab.c

   1 /* Generate code from machine description to compute values of attributes.
   2    Copyright (C) 1991, 1993, 1994, 1995, 1996, 1997, 1998,
   3    1999, 2000, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
   4    Contributed by Richard Kenner (kenner@vlsi1.ultra.nyu.edu)
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 2, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING.  If not, write to the Free
  20 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  21 02110-1301, USA.  */
  22
  23 /* This program handles insn attributes and the DEFINE_DELAY and
  24    DEFINE_INSN_RESERVATION definitions.
  25
  26    It produces a series of functions named `get_attr_...', one for each insn
  27    attribute.  Each of these is given the rtx for an insn and returns a member
  28    of the enum for the attribute.
  29
  30    These subroutines have the form of a `switch' on the INSN_CODE (via
  31    `recog_memoized').  Each case either returns a constant attribute value
  32    or a value that depends on tests on other attributes, the form of
  33    operands, or some random C expression (encoded with a SYMBOL_REF
  34    expression).
  35
  36    If the attribute `alternative', or a random C expression is present,
  37    `constrain_operands' is called.  If either of these cases of a reference to
  38    an operand is found, `extract_insn' is called.
  39
  40    The special attribute `length' is also recognized.  For this operand,
  41    expressions involving the address of an operand or the current insn,
  42    (address (pc)), are valid.  In this case, an initial pass is made to
  43    set all lengths that do not depend on address.  Those that do are set to
  44    the maximum length.  Then each insn that depends on an address is checked
  45    and possibly has its length changed.  The process repeats until no further
  46    changed are made.  The resulting lengths are saved for use by
  47    `get_attr_length'.
  48
  49    A special form of DEFINE_ATTR, where the expression for default value is a
  50    CONST expression, indicates an attribute that is constant for a given run
  51    of the compiler.  The subroutine generated for these attributes has no
  52    parameters as it does not depend on any particular insn.  Constant
  53    attributes are typically used to specify which variety of processor is
  54    used.
  55
  56    Internal attributes are defined to handle DEFINE_DELAY and
  57    DEFINE_INSN_RESERVATION.  Special routines are output for these cases.
  58
  59    This program works by keeping a list of possible values for each attribute.
  60    These include the basic attribute choices, default values for attribute, and
  61    all derived quantities.
  62
  63    As the description file is read, the definition for each insn is saved in a
  64    `struct insn_def'.   When the file reading is complete, a `struct insn_ent'
  65    is created for each insn and chained to the corresponding attribute value,
  66    either that specified, or the default.
  67
  68    An optimization phase is then run.  This simplifies expressions for each
  69    insn.  EQ_ATTR tests are resolved, whenever possible, to a test that
  70    indicates when the attribute has the specified value for the insn.  This
  71    avoids recursive calls during compilation.
  72
  73    The strategy used when processing DEFINE_DELAY definitions is to create
  74    arbitrarily complex expressions and have the optimization simplify them.
  75
  76    Once optimization is complete, any required routines and definitions
  77    will be written.
  78
  79    An optimization that is not yet implemented is to hoist the constant
  80    expressions entirely out of the routines and definitions that are written.
  81    A way to do this is to iterate over all possible combinations of values
  82    for constant attributes and generate a set of functions for that given
  83    combination.  An initialization function would be written that evaluates
  84    the attributes and installs the corresponding set of routines and
  85    definitions (each would be accessed through a pointer).
  86
  87    We use the flags in an RTX as follows:
  88    `unchanging' (ATTR_IND_SIMPLIFIED_P): This rtx is fully simplified
  89       independent of the insn code.
  90    `in_struct' (ATTR_CURR_SIMPLIFIED_P): This rtx is fully simplified
  91       for the insn code currently being processed (see optimize_attrs).
  92    `return_val' (ATTR_PERMANENT_P): This rtx is permanent and unique
  93       (see attr_rtx).  */
  94
  95 #define ATTR_IND_SIMPLIFIED_P(RTX) (RTX_FLAG((RTX), unchanging))
  96 #define ATTR_CURR_SIMPLIFIED_P(RTX) (RTX_FLAG((RTX), in_struct))
  97 #define ATTR_PERMANENT_P(RTX) (RTX_FLAG((RTX), return_val))
  98
  99 #if 0
 100 #define strcmp_check(S1, S2) ((S1) == (S2)              \
 101                               ? 0                       \
 102                               : (gcc_assert (strcmp ((S1), (S2))), 1))
 103 #else
 104 #define strcmp_check(S1, S2) ((S1) != (S2))
 105 #endif
 106
 107 #include "bconfig.h"
 108 #include "system.h"
 109 #include "coretypes.h"
 110 #include "tm.h"
 111 #include "rtl.h"
 112 #include "gensupport.h"
 113 #include "obstack.h"
 114 #include "errors.h"
 115
 116 /* Flags for make_internal_attr's `special' parameter.  */
 117 #define ATTR_NONE               0
 118 #define ATTR_SPECIAL            (1 << 0)
 119
 120 static struct obstack obstack1, obstack2;
 121 static struct obstack *hash_obstack = &obstack1;
 122 static struct obstack *temp_obstack = &obstack2;
 123
 124 /* enough space to reserve for printing out ints */
 125 #define MAX_DIGITS (HOST_BITS_PER_INT * 3 / 10 + 3)
 126
 127 /* Define structures used to record attributes and values.  */
 128
 129 /* As each DEFINE_INSN, DEFINE_PEEPHOLE, or DEFINE_ASM_ATTRIBUTES is
 130    encountered, we store all the relevant information into a
 131    `struct insn_def'.  This is done to allow attribute definitions to occur
 132    anywhere in the file.  */
 133
 134 struct insn_def
 135 {
 136   struct insn_def *next;        /* Next insn in chain.  */
 137   rtx def;                      /* The DEFINE_...  */
 138   int insn_code;                /* Instruction number.  */
 139   int insn_index;               /* Expression numer in file, for errors.  */
 140   int lineno;                   /* Line number.  */
 141   int num_alternatives;         /* Number of alternatives.  */
 142   int vec_idx;                  /* Index of attribute vector in `def'.  */
 143 };
 144
 145 /* Once everything has been read in, we store in each attribute value a list
 146    of insn codes that have that value.  Here is the structure used for the
 147    list.  */
 148
 149 struct insn_ent
 150 {
 151   struct insn_ent *next;        /* Next in chain.  */
 152   struct insn_def *def;         /* Instruction definition.  */
 153 };
 154
 155 /* Each value of an attribute (either constant or computed) is assigned a
 156    structure which is used as the listhead of the insns that have that
 157    value.  */
 158
 159 struct attr_value
 160 {
 161   rtx value;                    /* Value of attribute.  */
 162   struct attr_value *next;      /* Next attribute value in chain.  */
 163   struct insn_ent *first_insn;  /* First insn with this value.  */
 164   int num_insns;                /* Number of insns with this value.  */
 165   int has_asm_insn;             /* True if this value used for `asm' insns */
 166 };
 167
 168 /* Structure for each attribute.  */
 169
 170 struct attr_desc
 171 {
 172   char *name;                   /* Name of attribute.  */
 173   struct attr_desc *next;       /* Next attribute.  */
 174   struct attr_value *first_value; /* First value of this attribute.  */
 175   struct attr_value *default_val; /* Default value for this attribute.  */
 176   int lineno : 24;              /* Line number.  */
 177   unsigned is_numeric   : 1;    /* Values of this attribute are numeric.  */
 178   unsigned is_const     : 1;    /* Attribute value constant for each run.  */
 179   unsigned is_special   : 1;    /* Don't call `write_attr_set'.  */
 180 };
 181
 182 /* Structure for each DEFINE_DELAY.  */
 183
 184 struct delay_desc
 185 {
 186   rtx def;                      /* DEFINE_DELAY expression.  */
 187   struct delay_desc *next;      /* Next DEFINE_DELAY.  */
 188   int num;                      /* Number of DEFINE_DELAY, starting at 1.  */
 189   int lineno;                   /* Line number.  */
 190 };
 191
 192 /* Listheads of above structures.  */
 193
 194 /* This one is indexed by the first character of the attribute name.  */
 195 #define MAX_ATTRS_INDEX 256
 196 static struct attr_desc *attrs[MAX_ATTRS_INDEX];
 197 static struct insn_def *defs;
 198 static struct delay_desc *delays;
 199
 200 /* Other variables.  */
 201
 202 static int insn_code_number;
 203 static int insn_index_number;
 204 static int got_define_asm_attributes;
 205 static int must_extract;
 206 static int must_constrain;
 207 static int address_used;
 208 static int length_used;
 209 static int num_delays;
 210 static int have_annul_true, have_annul_false;
 211 static int num_insn_ents;
 212
 213 /* Stores, for each insn code, the number of constraint alternatives.  */
 214
 215 static int *insn_n_alternatives;
 216
 217 /* Stores, for each insn code, a bitmap that has bits on for each possible
 218    alternative.  */
 219
 220 static int *insn_alternatives;
 221
 222 /* Used to simplify expressions.  */
 223
 224 static rtx true_rtx, false_rtx;
 225
 226 /* Used to reduce calls to `strcmp' */
 227
 228 static const char *alternative_name;
 229 static const char *length_str;
 230 static const char *delay_type_str;
 231 static const char *delay_1_0_str;
 232 static const char *num_delay_slots_str;
 233
 234 /* Simplify an expression.  Only call the routine if there is something to
 235    simplify.  */
 236 #define SIMPLIFY_TEST_EXP(EXP,INSN_CODE,INSN_INDEX)     \
 237   (ATTR_IND_SIMPLIFIED_P (EXP) || ATTR_CURR_SIMPLIFIED_P (EXP) ? (EXP)  \
 238    : simplify_test_exp (EXP, INSN_CODE, INSN_INDEX))
 239
 240 #define DEF_ATTR_STRING(S) (attr_string ((S), strlen (S)))
 241
 242 /* Forward declarations of functions used before their definitions, only.  */
 243 static char *attr_string           (const char *, int);
 244 static char *attr_printf           (unsigned int, const char *, ...)
 245   ATTRIBUTE_PRINTF_2;
 246 static rtx make_numeric_value      (int);
 247 static struct attr_desc *find_attr (const char **, int);
 248 static rtx mk_attr_alt             (int);
 249 static char *next_comma_elt        (const char **);
 250 static rtx insert_right_side       (enum rtx_code, rtx, rtx, int, int);
 251 static rtx copy_boolean            (rtx);
 252 static int compares_alternatives_p (rtx);
 253 static void make_internal_attr     (const char *, rtx, int);
 254 static void insert_insn_ent        (struct attr_value *, struct insn_ent *);
 255 static void walk_attr_value        (rtx);
 256 static int max_attr_value          (rtx, int*);
 257 static int min_attr_value          (rtx, int*);
 258 static int or_attr_value           (rtx, int*);
 259 static rtx simplify_test_exp       (rtx, int, int);
 260 static rtx simplify_test_exp_in_temp (rtx, int, int);
 261 static rtx copy_rtx_unchanging     (rtx);
 262 static bool attr_alt_subset_p      (rtx, rtx);
 263 static bool attr_alt_subset_of_compl_p (rtx, rtx);
 264 static void clear_struct_flag      (rtx);
 265 static void write_attr_valueq      (struct attr_desc *, const char *);
 266 static struct attr_value *find_most_used  (struct attr_desc *);
 267 static void write_attr_set         (struct attr_desc *, int, rtx,
 268                                     const char *, const char *, rtx,
 269                                     int, int);
 270 static void write_attr_case        (struct attr_desc *, struct attr_value *,
 271                                     int, const char *, const char *, int, rtx);
 272 static void write_attr_value       (struct attr_desc *, rtx);
 273 static void write_upcase           (const char *);
 274 static void write_indent           (int);
 275 static rtx identity_fn             (rtx);
 276 static rtx zero_fn                 (rtx);
 277 static rtx one_fn                  (rtx);
 278 static rtx max_fn                  (rtx);
 279 static rtx min_fn                  (rtx);
 280
 281 #define oballoc(size) obstack_alloc (hash_obstack, size)
 282
 283 /* Hash table for sharing RTL and strings.  */
 284
 285 /* Each hash table slot is a bucket containing a chain of these structures.
 286    Strings are given negative hash codes; RTL expressions are given positive
 287    hash codes.  */
 288
 289 struct attr_hash
 290 {
 291   struct attr_hash *next;       /* Next structure in the bucket.  */
 292   int hashcode;                 /* Hash code of this rtx or string.  */
 293   union
 294     {
 295       char *str;                /* The string (negative hash codes) */
 296       rtx rtl;                  /* or the RTL recorded here.  */
 297     } u;
 298 };
 299
 300 /* Now here is the hash table.  When recording an RTL, it is added to
 301    the slot whose index is the hash code mod the table size.  Note
 302    that the hash table is used for several kinds of RTL (see attr_rtx)
 303    and for strings.  While all these live in the same table, they are
 304    completely independent, and the hash code is computed differently
 305    for each.  */
 306
 307 #define RTL_HASH_SIZE 4093
 308 static struct attr_hash *attr_hash_table[RTL_HASH_SIZE];
 309
 310 /* Here is how primitive or already-shared RTL's hash
 311    codes are made.  */
 312 #define RTL_HASH(RTL) ((long) (RTL) & 0777777)
 313
 314 /* Add an entry to the hash table for RTL with hash code HASHCODE.  */
 315
 316 static void
 317 attr_hash_add_rtx (int hashcode, rtx rtl)
 318 {
 319   struct attr_hash *h;
 320
 321   h = obstack_alloc (hash_obstack, sizeof (struct attr_hash));
 322   h->hashcode = hashcode;
 323   h->u.rtl = rtl;
 324   h->next = attr_hash_table[hashcode % RTL_HASH_SIZE];
 325   attr_hash_table[hashcode % RTL_HASH_SIZE] = h;
 326 }
 327
 328 /* Add an entry to the hash table for STRING with hash code HASHCODE.  */
 329
 330 static void
 331 attr_hash_add_string (int hashcode, char *str)
 332 {
 333   struct attr_hash *h;
 334
 335   h = obstack_alloc (hash_obstack, sizeof (struct attr_hash));
 336   h->hashcode = -hashcode;
 337   h->u.str = str;
 338   h->next = attr_hash_table[hashcode % RTL_HASH_SIZE];
 339   attr_hash_table[hashcode % RTL_HASH_SIZE] = h;
 340 }
 341
 342 /* Generate an RTL expression, but avoid duplicates.
 343    Set the ATTR_PERMANENT_P flag for these permanent objects.
 344
 345    In some cases we cannot uniquify; then we return an ordinary
 346    impermanent rtx with ATTR_PERMANENT_P clear.
 347
 348    Args are as follows:
 349
 350    rtx attr_rtx (code, [element1, ..., elementn])  */
 351
 352 static rtx
 353 attr_rtx_1 (enum rtx_code code, va_list p)
 354 {
 355   rtx rt_val = NULL_RTX;/* RTX to return to caller...           */
 356   int hashcode;
 357   struct attr_hash *h;
 358   struct obstack *old_obstack = rtl_obstack;
 359
 360   /* For each of several cases, search the hash table for an existing entry.
 361      Use that entry if one is found; otherwise create a new RTL and add it
 362      to the table.  */
 363
 364   if (GET_RTX_CLASS (code) == RTX_UNARY)
 365     {
 366       rtx arg0 = va_arg (p, rtx);
 367
 368       /* A permanent object cannot point to impermanent ones.  */
 369       if (! ATTR_PERMANENT_P (arg0))
 370         {
 371           rt_val = rtx_alloc (code);
 372           XEXP (rt_val, 0) = arg0;
 373           return rt_val;
 374         }
 375
 376       hashcode = ((HOST_WIDE_INT) code + RTL_HASH (arg0));
 377       for (h = attr_hash_table[hashcode % RTL_HASH_SIZE]; h; h = h->next)
 378         if (h->hashcode == hashcode
 379             && GET_CODE (h->u.rtl) == code
 380             && XEXP (h->u.rtl, 0) == arg0)
 381           return h->u.rtl;
 382
 383       if (h == 0)
 384         {
 385           rtl_obstack = hash_obstack;
 386           rt_val = rtx_alloc (code);
 387           XEXP (rt_val, 0) = arg0;
 388         }
 389     }
 390   else if (GET_RTX_CLASS (code) == RTX_BIN_ARITH
 391            || GET_RTX_CLASS (code) == RTX_COMM_ARITH
 392            || GET_RTX_CLASS (code) == RTX_COMPARE
 393            || GET_RTX_CLASS (code) == RTX_COMM_COMPARE)
 394     {
 395       rtx arg0 = va_arg (p, rtx);
 396       rtx arg1 = va_arg (p, rtx);
 397
 398       /* A permanent object cannot point to impermanent ones.  */
 399       if (! ATTR_PERMANENT_P (arg0) || ! ATTR_PERMANENT_P (arg1))
 400         {
 401           rt_val = rtx_alloc (code);
 402           XEXP (rt_val, 0) = arg0;
 403           XEXP (rt_val, 1) = arg1;
 404           return rt_val;
 405         }
 406
 407       hashcode = ((HOST_WIDE_INT) code + RTL_HASH (arg0) + RTL_HASH (arg1));
 408       for (h = attr_hash_table[hashcode % RTL_HASH_SIZE]; h; h = h->next)
 409         if (h->hashcode == hashcode
 410             && GET_CODE (h->u.rtl) == code
 411             && XEXP (h->u.rtl, 0) == arg0
 412             && XEXP (h->u.rtl, 1) == arg1)
 413           return h->u.rtl;
 414
 415       if (h == 0)
 416         {
 417           rtl_obstack = hash_obstack;
 418           rt_val = rtx_alloc (code);
 419           XEXP (rt_val, 0) = arg0;
 420           XEXP (rt_val, 1) = arg1;
 421         }
 422     }
 423   else if (GET_RTX_LENGTH (code) == 1
 424            && GET_RTX_FORMAT (code)[0] == 's')
 425     {
 426       char *arg0 = va_arg (p, char *);
 427
 428       arg0 = DEF_ATTR_STRING (arg0);
 429
 430       hashcode = ((HOST_WIDE_INT) code + RTL_HASH (arg0));
 431       for (h = attr_hash_table[hashcode % RTL_HASH_SIZE]; h; h = h->next)
 432         if (h->hashcode == hashcode
 433             && GET_CODE (h->u.rtl) == code
 434             && XSTR (h->u.rtl, 0) == arg0)
 435           return h->u.rtl;
 436
 437       if (h == 0)
 438         {
 439           rtl_obstack = hash_obstack;
 440           rt_val = rtx_alloc (code);
 441           XSTR (rt_val, 0) = arg0;
 442         }
 443     }
 444   else if (GET_RTX_LENGTH (code) == 2
 445            && GET_RTX_FORMAT (code)[0] == 's'
 446            && GET_RTX_FORMAT (code)[1] == 's')
 447     {
 448       char *arg0 = va_arg (p, char *);
 449       char *arg1 = va_arg (p, char *);
 450
 451       hashcode = ((HOST_WIDE_INT) code + RTL_HASH (arg0) + RTL_HASH (arg1));
 452       for (h = attr_hash_table[hashcode % RTL_HASH_SIZE]; h; h = h->next)
 453         if (h->hashcode == hashcode
 454             && GET_CODE (h->u.rtl) == code
 455             && XSTR (h->u.rtl, 0) == arg0
 456             && XSTR (h->u.rtl, 1) == arg1)
 457           return h->u.rtl;
 458
 459       if (h == 0)
 460         {
 461           rtl_obstack = hash_obstack;
 462           rt_val = rtx_alloc (code);
 463           XSTR (rt_val, 0) = arg0;
 464           XSTR (rt_val, 1) = arg1;
 465         }
 466     }
 467   else if (code == CONST_INT)
 468     {
 469       HOST_WIDE_INT arg0 = va_arg (p, HOST_WIDE_INT);
 470       if (arg0 == 0)
 471         return false_rtx;
 472       else if (arg0 == 1)
 473         return true_rtx;
 474       else
 475         goto nohash;
 476     }
 477   else
 478     {
 479       int i;            /* Array indices...                     */
 480       const char *fmt;  /* Current rtx's format...              */
 481     nohash:
 482       rt_val = rtx_alloc (code);        /* Allocate the storage space.  */
 483
 484       fmt = GET_RTX_FORMAT (code);      /* Find the right format...  */
 485       for (i = 0; i < GET_RTX_LENGTH (code); i++)
 486         {
 487           switch (*fmt++)
 488             {
 489             case '0':           /* Unused field.  */
 490               break;
 491
 492             case 'i':           /* An integer?  */
 493               XINT (rt_val, i) = va_arg (p, int);
 494               break;
 495
 496             case 'w':           /* A wide integer? */
 497               XWINT (rt_val, i) = va_arg (p, HOST_WIDE_INT);
 498               break;
 499
 500             case 's':           /* A string?  */
 501               XSTR (rt_val, i) = va_arg (p, char *);
 502               break;
 503
 504             case 'e':           /* An expression?  */
 505             case 'u':           /* An insn?  Same except when printing.  */
 506               XEXP (rt_val, i) = va_arg (p, rtx);
 507               break;
 508
 509             case 'E':           /* An RTX vector?  */
 510               XVEC (rt_val, i) = va_arg (p, rtvec);
 511               break;
 512
 513             default:
 514               gcc_unreachable ();
 515             }
 516         }
 517       return rt_val;
 518     }
 519
 520   rtl_obstack = old_obstack;
 521   attr_hash_add_rtx (hashcode, rt_val);
 522   ATTR_PERMANENT_P (rt_val) = 1;
 523   return rt_val;
 524 }
 525
 526 static rtx
 527 attr_rtx (enum rtx_code code, ...)
 528 {
 529   rtx result;
 530   va_list p;
 531
 532   va_start (p, code);
 533   result = attr_rtx_1 (code, p);
 534   va_end (p);
 535   return result;
 536 }
 537
 538 /* Create a new string printed with the printf line arguments into a space
 539    of at most LEN bytes:
 540
 541    rtx attr_printf (len, format, [arg1, ..., argn])  */
 542
 543 static char *
 544 attr_printf (unsigned int len, const char *fmt, ...)
 545 {
 546   char str[256];
 547   va_list p;
 548
 549   va_start (p, fmt);
 550
 551   gcc_assert (len < sizeof str); /* Leave room for \0.  */
 552
 553   vsprintf (str, fmt, p);
 554   va_end (p);
 555
 556   return DEF_ATTR_STRING (str);
 557 }
 558
 559 static rtx
 560 attr_eq (const char *name, const char *value)
 561 {
 562   return attr_rtx (EQ_ATTR, DEF_ATTR_STRING (name), DEF_ATTR_STRING (value));
 563 }
 564
 565 static const char *
 566 attr_numeral (int n)
 567 {
 568   return XSTR (make_numeric_value (n), 0);
 569 }
 570
 571 /* Return a permanent (possibly shared) copy of a string STR (not assumed
 572    to be null terminated) with LEN bytes.  */
 573
 574 static char *
 575 attr_string (const char *str, int len)
 576 {
 577   struct attr_hash *h;
 578   int hashcode;
 579   int i;
 580   char *new_str;
 581
 582   /* Compute the hash code.  */
 583   hashcode = (len + 1) * 613 + (unsigned) str[0];
 584   for (i = 1; i < len; i += 2)
 585     hashcode = ((hashcode * 613) + (unsigned) str[i]);
 586   if (hashcode < 0)
 587     hashcode = -hashcode;
 588
 589   /* Search the table for the string.  */
 590   for (h = attr_hash_table[hashcode % RTL_HASH_SIZE]; h; h = h->next)
 591     if (h->hashcode == -hashcode && h->u.str[0] == str[0]
 592         && !strncmp (h->u.str, str, len))
 593       return h->u.str;                  /* <-- return if found.  */
 594
 595   /* Not found; create a permanent copy and add it to the hash table.  */
 596   new_str = obstack_alloc (hash_obstack, len + 1);
 597   memcpy (new_str, str, len);
 598   new_str[len] = '\0';
 599   attr_hash_add_string (hashcode, new_str);
 600
 601   return new_str;                       /* Return the new string.  */
 602 }
 603
 604 /* Check two rtx's for equality of contents,
 605    taking advantage of the fact that if both are hashed
 606    then they can't be equal unless they are the same object.  */
 607
 608 static int
 609 attr_equal_p (rtx x, rtx y)
 610 {
 611   return (x == y || (! (ATTR_PERMANENT_P (x) && ATTR_PERMANENT_P (y))
 612                      && rtx_equal_p (x, y)));
 613 }
 614
 615 /* Copy an attribute value expression,
 616    descending to all depths, but not copying any
 617    permanent hashed subexpressions.  */
 618
 619 static rtx
 620 attr_copy_rtx (rtx orig)
 621 {
 622   rtx copy;
 623   int i, j;
 624   RTX_CODE code;
 625   const char *format_ptr;
 626
 627   /* No need to copy a permanent object.  */
 628   if (ATTR_PERMANENT_P (orig))
 629     return orig;
 630
 631   code = GET_CODE (orig);
 632
 633   switch (code)
 634     {
 635     case REG:
 636     case CONST_INT:
 637     case CONST_DOUBLE:
 638     case CONST_VECTOR:
 639     case SYMBOL_REF:
 640     case CODE_LABEL:
 641     case PC:
 642     case CC0:
 643       return orig;
 644
 645     default:
 646       break;
 647     }
 648
 649   copy = rtx_alloc (code);
 650   PUT_MODE (copy, GET_MODE (orig));
 651   ATTR_IND_SIMPLIFIED_P (copy) = ATTR_IND_SIMPLIFIED_P (orig);
 652   ATTR_CURR_SIMPLIFIED_P (copy) = ATTR_CURR_SIMPLIFIED_P (orig);
 653   ATTR_PERMANENT_P (copy) = ATTR_PERMANENT_P (orig);
 654
 655   format_ptr = GET_RTX_FORMAT (GET_CODE (copy));
 656
 657   for (i = 0; i < GET_RTX_LENGTH (GET_CODE (copy)); i++)
 658     {
 659       switch (*format_ptr++)
 660         {
 661         case 'e':
 662           XEXP (copy, i) = XEXP (orig, i);
 663           if (XEXP (orig, i) != NULL)
 664             XEXP (copy, i) = attr_copy_rtx (XEXP (orig, i));
 665           break;
 666
 667         case 'E':
 668         case 'V':
 669           XVEC (copy, i) = XVEC (orig, i);
 670           if (XVEC (orig, i) != NULL)
 671             {
 672               XVEC (copy, i) = rtvec_alloc (XVECLEN (orig, i));
 673               for (j = 0; j < XVECLEN (copy, i); j++)
 674                 XVECEXP (copy, i, j) = attr_copy_rtx (XVECEXP (orig, i, j));
 675             }
 676           break;
 677
 678         case 'n':
 679         case 'i':
 680           XINT (copy, i) = XINT (orig, i);
 681           break;
 682
 683         case 'w':
 684           XWINT (copy, i) = XWINT (orig, i);
 685           break;
 686
 687         case 's':
 688         case 'S':
 689           XSTR (copy, i) = XSTR (orig, i);
 690           break;
 691
 692         default:
 693           gcc_unreachable ();
 694         }
 695     }
 696   return copy;
 697 }
 698
 699 /* Given a test expression for an attribute, ensure it is validly formed.
 700    IS_CONST indicates whether the expression is constant for each compiler
 701    run (a constant expression may not test any particular insn).
 702
 703    Convert (eq_attr "att" "a1,a2") to (ior (eq_attr ... ) (eq_attrq ..))
 704    and (eq_attr "att" "!a1") to (not (eq_attr "att" "a1")).  Do the latter
 705    test first so that (eq_attr "att" "!a1,a2,a3") works as expected.
 706
 707    Update the string address in EQ_ATTR expression to be the same used
 708    in the attribute (or `alternative_name') to speed up subsequent
 709    `find_attr' calls and eliminate most `strcmp' calls.
 710
 711    Return the new expression, if any.  */
 712
 713 static rtx
 714 check_attr_test (rtx exp, int is_const, int lineno)
 715 {
 716   struct attr_desc *attr;
 717   struct attr_value *av;
 718   const char *name_ptr, *p;
 719   rtx orexp, newexp;
 720
 721   switch (GET_CODE (exp))
 722     {
 723     case EQ_ATTR:
 724       /* Handle negation test.  */
 725       if (XSTR (exp, 1)[0] == '!')
 726         return check_attr_test (attr_rtx (NOT,
 727                                           attr_eq (XSTR (exp, 0),
 728                                                    &XSTR (exp, 1)[1])),
 729                                 is_const, lineno);
 730
 731       else if (n_comma_elts (XSTR (exp, 1)) == 1)
 732         {
 733           attr = find_attr (&XSTR (exp, 0), 0);
 734           if (attr == NULL)
 735             {
 736               if (! strcmp (XSTR (exp, 0), "alternative"))
 737                 return mk_attr_alt (1 << atoi (XSTR (exp, 1)));
 738               else
 739                 fatal ("unknown attribute `%s' in EQ_ATTR", XSTR (exp, 0));
 740             }
 741
 742           if (is_const && ! attr->is_const)
 743             fatal ("constant expression uses insn attribute `%s' in EQ_ATTR",
 744                    XSTR (exp, 0));
 745
 746           /* Copy this just to make it permanent,
 747              so expressions using it can be permanent too.  */
 748           exp = attr_eq (XSTR (exp, 0), XSTR (exp, 1));
 749
 750           /* It shouldn't be possible to simplify the value given to a
 751              constant attribute, so don't expand this until it's time to
 752              write the test expression.  */
 753           if (attr->is_const)
 754             ATTR_IND_SIMPLIFIED_P (exp) = 1;
 755
 756           if (attr->is_numeric)
 757             {
 758               for (p = XSTR (exp, 1); *p; p++)
 759                 if (! ISDIGIT (*p))
 760                   fatal ("attribute `%s' takes only numeric values",
 761                          XSTR (exp, 0));
 762             }
 763           else
 764             {
 765               for (av = attr->first_value; av; av = av->next)
 766                 if (GET_CODE (av->value) == CONST_STRING
 767                     && ! strcmp (XSTR (exp, 1), XSTR (av->value, 0)))
 768                   break;
 769
 770               if (av == NULL)
 771                 fatal ("unknown value `%s' for `%s' attribute",
 772                        XSTR (exp, 1), XSTR (exp, 0));
 773             }
 774         }
 775       else
 776         {
 777           if (! strcmp (XSTR (exp, 0), "alternative"))
 778             {
 779               int set = 0;
 780
 781               name_ptr = XSTR (exp, 1);
 782               while ((p = next_comma_elt (&name_ptr)) != NULL)
 783                 set |= 1 << atoi (p);
 784
 785               return mk_attr_alt (set);
 786             }
 787           else
 788             {
 789               /* Make an IOR tree of the possible values.  */
 790               orexp = false_rtx;
 791               name_ptr = XSTR (exp, 1);
 792               while ((p = next_comma_elt (&name_ptr)) != NULL)
 793                 {
 794                   newexp = attr_eq (XSTR (exp, 0), p);
 795                   orexp = insert_right_side (IOR, orexp, newexp, -2, -2);
 796                 }
 797
 798               return check_attr_test (orexp, is_const, lineno);
 799             }
 800         }
 801       break;
 802
 803     case ATTR_FLAG:
 804       break;
 805
 806     case CONST_INT:
 807       /* Either TRUE or FALSE.  */
 808       if (XWINT (exp, 0))
 809         return true_rtx;
 810       else
 811         return false_rtx;
 812
 813     case IOR:
 814     case AND:
 815       XEXP (exp, 0) = check_attr_test (XEXP (exp, 0), is_const, lineno);
 816       XEXP (exp, 1) = check_attr_test (XEXP (exp, 1), is_const, lineno);
 817       break;
 818
 819     case NOT:
 820       XEXP (exp, 0) = check_attr_test (XEXP (exp, 0), is_const, lineno);
 821       break;
 822
 823     case MATCH_OPERAND:
 824       if (is_const)
 825         fatal ("RTL operator \"%s\" not valid in constant attribute test",
 826                GET_RTX_NAME (GET_CODE (exp)));
 827       /* These cases can't be simplified.  */
 828       ATTR_IND_SIMPLIFIED_P (exp) = 1;
 829       break;
 830
 831     case LE:  case LT:  case GT:  case GE:
 832     case LEU: case LTU: case GTU: case GEU:
 833     case NE:  case EQ:
 834       if (GET_CODE (XEXP (exp, 0)) == SYMBOL_REF
 835           && GET_CODE (XEXP (exp, 1)) == SYMBOL_REF)
 836         exp = attr_rtx (GET_CODE (exp),
 837                         attr_rtx (SYMBOL_REF, XSTR (XEXP (exp, 0), 0)),
 838                         attr_rtx (SYMBOL_REF, XSTR (XEXP (exp, 1), 0)));
 839       /* These cases can't be simplified.  */
 840       ATTR_IND_SIMPLIFIED_P (exp) = 1;
 841       break;
 842
 843     case SYMBOL_REF:
 844       if (is_const)
 845         {
 846           /* These cases are valid for constant attributes, but can't be
 847              simplified.  */
 848           exp = attr_rtx (SYMBOL_REF, XSTR (exp, 0));
 849           ATTR_IND_SIMPLIFIED_P (exp) = 1;
 850           break;
 851         }
 852     default:
 853       fatal ("RTL operator \"%s\" not valid in attribute test",
 854              GET_RTX_NAME (GET_CODE (exp)));
 855     }
 856
 857   return exp;
 858 }
 859
 860 /* Given an expression, ensure that it is validly formed and that all named
 861    attribute values are valid for the given attribute.  Issue a fatal error
 862    if not.  If no attribute is specified, assume a numeric attribute.
 863
 864    Return a perhaps modified replacement expression for the value.  */
 865
 866 static rtx
 867 check_attr_value (rtx exp, struct attr_desc *attr)
 868 {
 869   struct attr_value *av;
 870   const char *p;
 871   int i;
 872
 873   switch (GET_CODE (exp))
 874     {
 875     case CONST_INT:
 876       if (attr && ! attr->is_numeric)
 877         {
 878           message_with_line (attr->lineno,
 879                              "CONST_INT not valid for non-numeric attribute %s",
 880                              attr->name);
 881           have_error = 1;
 882           break;
 883         }
 884
 885       if (INTVAL (exp) < 0)
 886         {
 887           message_with_line (attr->lineno,
 888                              "negative numeric value specified for attribute %s",
 889                              attr->name);
 890           have_error = 1;
 891           break;
 892         }
 893       break;
 894
 895     case CONST_STRING:
 896       if (! strcmp (XSTR (exp, 0), "*"))
 897         break;
 898
 899       if (attr == 0 || attr->is_numeric)
 900         {
 901           p = XSTR (exp, 0);
 902           for (; *p; p++)
 903             if (! ISDIGIT (*p))
 904               {
 905                 message_with_line (attr ? attr->lineno : 0,
 906                                    "non-numeric value for numeric attribute %s",
 907                                    attr ? attr->name : "internal");
 908                 have_error = 1;
 909                 break;
 910               }
 911           break;
 912         }
 913
 914       for (av = attr->first_value; av; av = av->next)
 915         if (GET_CODE (av->value) == CONST_STRING
 916             && ! strcmp (XSTR (av->value, 0), XSTR (exp, 0)))
 917           break;
 918
 919       if (av == NULL)
 920         {
 921           message_with_line (attr->lineno,
 922                              "unknown value `%s' for `%s' attribute",
 923                              XSTR (exp, 0), attr ? attr->name : "internal");
 924           have_error = 1;
 925         }
 926       break;
 927
 928     case IF_THEN_ELSE:
 929       XEXP (exp, 0) = check_attr_test (XEXP (exp, 0),
 930                                        attr ? attr->is_const : 0,
 931                                        attr ? attr->lineno : 0);
 932       XEXP (exp, 1) = check_attr_value (XEXP (exp, 1), attr);
 933       XEXP (exp, 2) = check_attr_value (XEXP (exp, 2), attr);
 934       break;
 935
 936     case PLUS:
 937     case MINUS:
 938     case MULT:
 939     case DIV:
 940     case MOD:
 941       if (attr && !attr->is_numeric)
 942         {
 943           message_with_line (attr->lineno,
 944                              "invalid operation `%s' for non-numeric attribute value",
 945                              GET_RTX_NAME (GET_CODE (exp)));
 946           have_error = 1;
 947           break;
 948         }
 949       /* Fall through.  */
 950
 951     case IOR:
 952     case AND:
 953       XEXP (exp, 0) = check_attr_value (XEXP (exp, 0), attr);
 954       XEXP (exp, 1) = check_attr_value (XEXP (exp, 1), attr);
 955       break;
 956
 957     case FFS:
 958     case CLZ:
 959     case CTZ:
 960     case POPCOUNT:
 961     case PARITY:
 962     case BSWAP:
 963       XEXP (exp, 0) = check_attr_value (XEXP (exp, 0), attr);
 964       break;
 965
 966     case COND:
 967       if (XVECLEN (exp, 0) % 2 != 0)
 968         {
 969           message_with_line (attr->lineno,
 970                              "first operand of COND must have even length");
 971           have_error = 1;
 972           break;
 973         }
 974
 975       for (i = 0; i < XVECLEN (exp, 0); i += 2)
 976         {
 977           XVECEXP (exp, 0, i) = check_attr_test (XVECEXP (exp, 0, i),
 978                                                  attr ? attr->is_const : 0,
 979                                                  attr ? attr->lineno : 0);
 980           XVECEXP (exp, 0, i + 1)
 981             = check_attr_value (XVECEXP (exp, 0, i + 1), attr);
 982         }
 983
 984       XEXP (exp, 1) = check_attr_value (XEXP (exp, 1), attr);
 985       break;
 986
 987     case ATTR:
 988       {
 989         struct attr_desc *attr2 = find_attr (&XSTR (exp, 0), 0);
 990         if (attr2 == NULL)
 991           {
 992             message_with_line (attr ? attr->lineno : 0,
 993                                "unknown attribute `%s' in ATTR",
 994                                XSTR (exp, 0));
 995             have_error = 1;
 996           }
 997         else if (attr && attr->is_const && ! attr2->is_const)
 998           {
 999             message_with_line (attr->lineno,
1000                 "non-constant attribute `%s' referenced from `%s'",
1001                 XSTR (exp, 0), attr->name);
1002             have_error = 1;
1003           }
1004         else if (attr
1005                  && attr->is_numeric != attr2->is_numeric)
1006           {
1007             message_with_line (attr->lineno,
1008                 "numeric attribute mismatch calling `%s' from `%s'",
1009                 XSTR (exp, 0), attr->name);
1010             have_error = 1;
1011           }
1012       }
1013       break;
1014
1015     case SYMBOL_REF:
1016       /* A constant SYMBOL_REF is valid as a constant attribute test and
1017          is expanded later by make_canonical into a COND.  In a non-constant
1018          attribute test, it is left be.  */
1019       return attr_rtx (SYMBOL_REF, XSTR (exp, 0));
1020
1021     default:
1022       message_with_line (attr ? attr->lineno : 0,
1023                          "invalid operation `%s' for attribute value",
1024                          GET_RTX_NAME (GET_CODE (exp)));
1025       have_error = 1;
1026       break;
1027     }
1028
1029   return exp;
1030 }
1031
1032 /* Given an SET_ATTR_ALTERNATIVE expression, convert to the canonical SET.
1033    It becomes a COND with each test being (eq_attr "alternative" "n") */
1034
1035 static rtx
1036 convert_set_attr_alternative (rtx exp, struct insn_def *id)
1037 {
1038   int num_alt = id->num_alternatives;
1039   rtx condexp;
1040   int i;
1041
1042   if (XVECLEN (exp, 1) != num_alt)
1043     {
1044       message_with_line (id->lineno,
1045                          "bad number of entries in SET_ATTR_ALTERNATIVE");
1046       have_error = 1;
1047       return NULL_RTX;
1048     }
1049
1050   /* Make a COND with all tests but the last.  Select the last value via the
1051      default.  */
1052   condexp = rtx_alloc (COND);
1053   XVEC (condexp, 0) = rtvec_alloc ((num_alt - 1) * 2);
1054
1055   for (i = 0; i < num_alt - 1; i++)
1056     {
1057       const char *p;
1058       p = attr_numeral (i);
1059
1060       XVECEXP (condexp, 0, 2 * i) = attr_eq (alternative_name, p);
1061       XVECEXP (condexp, 0, 2 * i + 1) = XVECEXP (exp, 1, i);
1062     }
1063
1064   XEXP (condexp, 1) = XVECEXP (exp, 1, i);
1065
1066   return attr_rtx (SET, attr_rtx (ATTR, XSTR (exp, 0)), condexp);
1067 }
1068
1069 /* Given a SET_ATTR, convert to the appropriate SET.  If a comma-separated
1070    list of values is given, convert to SET_ATTR_ALTERNATIVE first.  */
1071
1072 static rtx
1073 convert_set_attr (rtx exp, struct insn_def *id)
1074 {
1075   rtx newexp;
1076   const char *name_ptr;
1077   char *p;
1078   int n;
1079
1080   /* See how many alternative specified.  */
1081   n = n_comma_elts (XSTR (exp, 1));
1082   if (n == 1)
1083     return attr_rtx (SET,
1084                      attr_rtx (ATTR, XSTR (exp, 0)),
1085                      attr_rtx (CONST_STRING, XSTR (exp, 1)));
1086
1087   newexp = rtx_alloc (SET_ATTR_ALTERNATIVE);
1088   XSTR (newexp, 0) = XSTR (exp, 0);
1089   XVEC (newexp, 1) = rtvec_alloc (n);
1090
1091   /* Process each comma-separated name.  */
1092   name_ptr = XSTR (exp, 1);
1093   n = 0;
1094   while ((p = next_comma_elt (&name_ptr)) != NULL)
1095     XVECEXP (newexp, 1, n++) = attr_rtx (CONST_STRING, p);
1096
1097   return convert_set_attr_alternative (newexp, id);
1098 }
1099
1100 /* Scan all definitions, checking for validity.  Also, convert any SET_ATTR
1101    and SET_ATTR_ALTERNATIVE expressions to the corresponding SET
1102    expressions.  */
1103
1104 static void
1105 check_defs (void)
1106 {
1107   struct insn_def *id;
1108   struct attr_desc *attr;
1109   int i;
1110   rtx value;
1111
1112   for (id = defs; id; id = id->next)
1113     {
1114       if (XVEC (id->def, id->vec_idx) == NULL)
1115         continue;
1116
1117       for (i = 0; i < XVECLEN (id->def, id->vec_idx); i++)
1118         {
1119           value = XVECEXP (id->def, id->vec_idx, i);
1120           switch (GET_CODE (value))
1121             {
1122             case SET:
1123               if (GET_CODE (XEXP (value, 0)) != ATTR)
1124                 {
1125                   message_with_line (id->lineno, "bad attribute set");
1126                   have_error = 1;
1127                   value = NULL_RTX;
1128                 }
1129               break;
1130
1131             case SET_ATTR_ALTERNATIVE:
1132               value = convert_set_attr_alternative (value, id);
1133               break;
1134
1135             case SET_ATTR:
1136               value = convert_set_attr (value, id);
1137               break;
1138
1139             default:
1140               message_with_line (id->lineno, "invalid attribute code %s",
1141                                  GET_RTX_NAME (GET_CODE (value)));
1142               have_error = 1;
1143               value = NULL_RTX;
1144             }
1145           if (value == NULL_RTX)
1146             continue;
1147
1148           if ((attr = find_attr (&XSTR (XEXP (value, 0), 0), 0)) == NULL)
1149             {
1150               message_with_line (id->lineno, "unknown attribute %s",
1151                                  XSTR (XEXP (value, 0), 0));
1152               have_error = 1;
1153               continue;
1154             }
1155
1156           XVECEXP (id->def, id->vec_idx, i) = value;
1157           XEXP (value, 1) = check_attr_value (XEXP (value, 1), attr);
1158         }
1159     }
1160 }
1161
1162 /* Given a valid expression for an attribute value, remove any IF_THEN_ELSE
1163    expressions by converting them into a COND.  This removes cases from this
1164    program.  Also, replace an attribute value of "*" with the default attribute
1165    value.  */
1166
1167 static rtx
1168 make_canonical (struct attr_desc *attr, rtx exp)
1169 {
1170   int i;
1171   rtx newexp;
1172
1173   switch (GET_CODE (exp))
1174     {
1175     case CONST_INT:
1176       exp = make_numeric_value (INTVAL (exp));
1177       break;
1178
1179     case CONST_STRING:
1180       if (! strcmp (XSTR (exp, 0), "*"))
1181         {
1182           if (attr == 0 || attr->default_val == 0)
1183             fatal ("(attr_value \"*\") used in invalid context");
1184           exp = attr->default_val->value;
1185         }
1186       else
1187         XSTR (exp, 0) = DEF_ATTR_STRING (XSTR (exp, 0));
1188
1189       break;
1190
1191     case SYMBOL_REF:
1192       if (!attr->is_const || ATTR_IND_SIMPLIFIED_P (exp))
1193         break;
1194       /* The SYMBOL_REF is constant for a given run, so mark it as unchanging.
1195          This makes the COND something that won't be considered an arbitrary
1196          expression by walk_attr_value.  */
1197       ATTR_IND_SIMPLIFIED_P (exp) = 1;
1198       exp = check_attr_value (exp, attr);
1199       break;
1200
1201     case IF_THEN_ELSE:
1202       newexp = rtx_alloc (COND);
1203       XVEC (newexp, 0) = rtvec_alloc (2);
1204       XVECEXP (newexp, 0, 0) = XEXP (exp, 0);
1205       XVECEXP (newexp, 0, 1) = XEXP (exp, 1);
1206
1207       XEXP (newexp, 1) = XEXP (exp, 2);
1208
1209       exp = newexp;
1210       /* Fall through to COND case since this is now a COND.  */
1211
1212     case COND:
1213       {
1214         int allsame = 1;
1215         rtx defval;
1216
1217         /* First, check for degenerate COND.  */
1218         if (XVECLEN (exp, 0) == 0)
1219           return make_canonical (attr, XEXP (exp, 1));
1220         defval = XEXP (exp, 1) = make_canonical (attr, XEXP (exp, 1));
1221
1222         for (i = 0; i < XVECLEN (exp, 0); i += 2)
1223           {
1224             XVECEXP (exp, 0, i) = copy_boolean (XVECEXP (exp, 0, i));
1225             XVECEXP (exp, 0, i + 1)
1226               = make_canonical (attr, XVECEXP (exp, 0, i + 1));
1227             if (! rtx_equal_p (XVECEXP (exp, 0, i + 1), defval))
1228               allsame = 0;
1229           }
1230         if (allsame)
1231           return defval;
1232       }
1233       break;
1234
1235     default:
1236       break;
1237     }
1238
1239   return exp;
1240 }
1241
1242 static rtx
1243 copy_boolean (rtx exp)
1244 {
1245   if (GET_CODE (exp) == AND || GET_CODE (exp) == IOR)
1246     return attr_rtx (GET_CODE (exp), copy_boolean (XEXP (exp, 0)),
1247                      copy_boolean (XEXP (exp, 1)));
1248   if (GET_CODE (exp) == MATCH_OPERAND)
1249     {
1250       XSTR (exp, 1) = DEF_ATTR_STRING (XSTR (exp, 1));
1251       XSTR (exp, 2) = DEF_ATTR_STRING (XSTR (exp, 2));
1252     }
1253   else if (GET_CODE (exp) == EQ_ATTR)
1254     {
1255       XSTR (exp, 0) = DEF_ATTR_STRING (XSTR (exp, 0));
1256       XSTR (exp, 1) = DEF_ATTR_STRING (XSTR (exp, 1));
1257     }
1258
1259   return exp;
1260 }
1261
1262 /* Given a value and an attribute description, return a `struct attr_value *'
1263    that represents that value.  This is either an existing structure, if the
1264    value has been previously encountered, or a newly-created structure.
1265
1266    `insn_code' is the code of an insn whose attribute has the specified
1267    value (-2 if not processing an insn).  We ensure that all insns for
1268    a given value have the same number of alternatives if the value checks
1269    alternatives.  */
1270
1271 static struct attr_value *
1272 get_attr_value (rtx value, struct attr_desc *attr, int insn_code)
1273 {
1274   struct attr_value *av;
1275   int num_alt = 0;
1276
1277   value = make_canonical (attr, value);
1278   if (compares_alternatives_p (value))
1279     {
1280       if (insn_code < 0 || insn_alternatives == NULL)
1281         fatal ("(eq_attr \"alternatives\" ...) used in non-insn context");
1282       else
1283         num_alt = insn_alternatives[insn_code];
1284     }
1285
1286   for (av = attr->first_value; av; av = av->next)
1287     if (rtx_equal_p (value, av->value)
1288         && (num_alt == 0 || av->first_insn == NULL
1289             || insn_alternatives[av->first_insn->def->insn_code]))
1290       return av;
1291
1292   av = oballoc (sizeof (struct attr_value));
1293   av->value = value;
1294   av->next = attr->first_value;
1295   attr->first_value = av;
1296   av->first_insn = NULL;
1297   av->num_insns = 0;
1298   av->has_asm_insn = 0;
1299
1300   return av;
1301 }
1302
1303 /* After all DEFINE_DELAYs have been read in, create internal attributes
1304    to generate the required routines.
1305
1306    First, we compute the number of delay slots for each insn (as a COND of
1307    each of the test expressions in DEFINE_DELAYs).  Then, if more than one
1308    delay type is specified, we compute a similar function giving the
1309    DEFINE_DELAY ordinal for each insn.
1310
1311    Finally, for each [DEFINE_DELAY, slot #] pair, we compute an attribute that
1312    tells whether a given insn can be in that delay slot.
1313
1314    Normal attribute filling and optimization expands these to contain the
1315    information needed to handle delay slots.  */
1316
1317 static void
1318 expand_delays (void)
1319 {
1320   struct delay_desc *delay;
1321   rtx condexp;
1322   rtx newexp;
1323   int i;
1324   char *p;
1325
1326   /* First, generate data for `num_delay_slots' function.  */
1327
1328   condexp = rtx_alloc (COND);
1329   XVEC (condexp, 0) = rtvec_alloc (num_delays * 2);
1330   XEXP (condexp, 1) = make_numeric_value (0);
1331
1332   for (i = 0, delay = delays; delay; i += 2, delay = delay->next)
1333     {
1334       XVECEXP (condexp, 0, i) = XEXP (delay->def, 0);
1335       XVECEXP (condexp, 0, i + 1)
1336         = make_numeric_value (XVECLEN (delay->def, 1) / 3);
1337     }
1338
1339   make_internal_attr (num_delay_slots_str, condexp, ATTR_NONE);
1340
1341   /* If more than one delay type, do the same for computing the delay type.  */
1342   if (num_delays > 1)
1343     {
1344       condexp = rtx_alloc (COND);
1345       XVEC (condexp, 0) = rtvec_alloc (num_delays * 2);
1346       XEXP (condexp, 1) = make_numeric_value (0);
1347
1348       for (i = 0, delay = delays; delay; i += 2, delay = delay->next)
1349         {
1350           XVECEXP (condexp, 0, i) = XEXP (delay->def, 0);
1351           XVECEXP (condexp, 0, i + 1) = make_numeric_value (delay->num);
1352         }
1353
1354       make_internal_attr (delay_type_str, condexp, ATTR_SPECIAL);
1355     }
1356
1357   /* For each delay possibility and delay slot, compute an eligibility
1358      attribute for non-annulled insns and for each type of annulled (annul
1359      if true and annul if false).  */
1360   for (delay = delays; delay; delay = delay->next)
1361     {
1362       for (i = 0; i < XVECLEN (delay->def, 1); i += 3)
1363         {
1364           condexp = XVECEXP (delay->def, 1, i);
1365           if (condexp == 0)
1366             condexp = false_rtx;
1367           newexp = attr_rtx (IF_THEN_ELSE, condexp,
1368                              make_numeric_value (1), make_numeric_value (0));
1369
1370           p = attr_printf (sizeof "*delay__" + MAX_DIGITS * 2,
1371                            "*delay_%d_%d", delay->num, i / 3);
1372           make_internal_attr (p, newexp, ATTR_SPECIAL);
1373
1374           if (have_annul_true)
1375             {
1376               condexp = XVECEXP (delay->def, 1, i + 1);
1377               if (condexp == 0) condexp = false_rtx;
1378               newexp = attr_rtx (IF_THEN_ELSE, condexp,
1379                                  make_numeric_value (1),
1380                                  make_numeric_value (0));
1381               p = attr_printf (sizeof "*annul_true__" + MAX_DIGITS * 2,
1382                                "*annul_true_%d_%d", delay->num, i / 3);
1383               make_internal_attr (p, newexp, ATTR_SPECIAL);
1384             }
1385
1386           if (have_annul_false)
1387             {
1388               condexp = XVECEXP (delay->def, 1, i + 2);
1389               if (condexp == 0) condexp = false_rtx;
1390               newexp = attr_rtx (IF_THEN_ELSE, condexp,
1391                                  make_numeric_value (1),
1392                                  make_numeric_value (0));
1393               p = attr_printf (sizeof "*annul_false__" + MAX_DIGITS * 2,
1394                                "*annul_false_%d_%d", delay->num, i / 3);
1395               make_internal_attr (p, newexp, ATTR_SPECIAL);
1396             }
1397         }
1398     }
1399 }
1400
1401 /* Once all attributes and insns have been read and checked, we construct for
1402    each attribute value a list of all the insns that have that value for
1403    the attribute.  */
1404
1405 static void
1406 fill_attr (struct attr_desc *attr)
1407 {
1408   struct attr_value *av;
1409   struct insn_ent *ie;
1410   struct insn_def *id;
1411   int i;
1412   rtx value;
1413
1414   /* Don't fill constant attributes.  The value is independent of
1415      any particular insn.  */
1416   if (attr->is_const)
1417     return;
1418
1419   for (id = defs; id; id = id->next)
1420     {
1421       /* If no value is specified for this insn for this attribute, use the
1422          default.  */
1423       value = NULL;
1424       if (XVEC (id->def, id->vec_idx))
1425         for (i = 0; i < XVECLEN (id->def, id->vec_idx); i++)
1426           if (! strcmp_check (XSTR (XEXP (XVECEXP (id->def, id->vec_idx, i), 0), 0),
1427                               attr->name))
1428             value = XEXP (XVECEXP (id->def, id->vec_idx, i), 1);
1429
1430       if (value == NULL)
1431         av = attr->default_val;
1432       else
1433         av = get_attr_value (value, attr, id->insn_code);
1434
1435       ie = oballoc (sizeof (struct insn_ent));
1436       ie->def = id;
1437       insert_insn_ent (av, ie);
1438     }
1439 }
1440
1441 /* Given an expression EXP, see if it is a COND or IF_THEN_ELSE that has a
1442    test that checks relative positions of insns (uses MATCH_DUP or PC).
1443    If so, replace it with what is obtained by passing the expression to
1444    ADDRESS_FN.  If not but it is a COND or IF_THEN_ELSE, call this routine
1445    recursively on each value (including the default value).  Otherwise,
1446    return the value returned by NO_ADDRESS_FN applied to EXP.  */
1447
1448 static rtx
1449 substitute_address (rtx exp, rtx (*no_address_fn) (rtx),
1450                     rtx (*address_fn) (rtx))
1451 {
1452   int i;
1453   rtx newexp;
1454
1455   if (GET_CODE (exp) == COND)
1456     {
1457       /* See if any tests use addresses.  */
1458       address_used = 0;
1459       for (i = 0; i < XVECLEN (exp, 0); i += 2)
1460         walk_attr_value (XVECEXP (exp, 0, i));
1461
1462       if (address_used)
1463         return (*address_fn) (exp);
1464
1465       /* Make a new copy of this COND, replacing each element.  */
1466       newexp = rtx_alloc (COND);
1467       XVEC (newexp, 0) = rtvec_alloc (XVECLEN (exp, 0));
1468       for (i = 0; i < XVECLEN (exp, 0); i += 2)
1469         {
1470           XVECEXP (newexp, 0, i) = XVECEXP (exp, 0, i);
1471           XVECEXP (newexp, 0, i + 1)
1472             = substitute_address (XVECEXP (exp, 0, i + 1),
1473                                   no_address_fn, address_fn);
1474         }
1475
1476       XEXP (newexp, 1) = substitute_address (XEXP (exp, 1),
1477                                              no_address_fn, address_fn);
1478
1479       return newexp;
1480     }
1481
1482   else if (GET_CODE (exp) == IF_THEN_ELSE)
1483     {
1484       address_used = 0;
1485       walk_attr_value (XEXP (exp, 0));
1486       if (address_used)
1487         return (*address_fn) (exp);
1488
1489       return attr_rtx (IF_THEN_ELSE,
1490                        substitute_address (XEXP (exp, 0),
1491                                            no_address_fn, address_fn),
1492                        substitute_address (XEXP (exp, 1),
1493                                            no_address_fn, address_fn),
1494                        substitute_address (XEXP (exp, 2),
1495                                            no_address_fn, address_fn));
1496     }
1497
1498   return (*no_address_fn) (exp);
1499 }
1500
1501 /* Make new attributes from the `length' attribute.  The following are made,
1502    each corresponding to a function called from `shorten_branches' or
1503    `get_attr_length':
1504
1505    *insn_default_length         This is the length of the insn to be returned
1506                                 by `get_attr_length' before `shorten_branches'
1507                                 has been called.  In each case where the length
1508                                 depends on relative addresses, the largest
1509                                 possible is used.  This routine is also used
1510                                 to compute the initial size of the insn.
1511
1512    *insn_variable_length_p      This returns 1 if the insn's length depends
1513                                 on relative addresses, zero otherwise.
1514
1515    *insn_current_length         This is only called when it is known that the
1516                                 insn has a variable length and returns the
1517                                 current length, based on relative addresses.
1518   */
1519
1520 static void
1521 make_length_attrs (void)
1522 {
1523   static const char *new_names[] =
1524     {
1525       "*insn_default_length",
1526       "*insn_min_length",
1527       "*insn_variable_length_p",
1528       "*insn_current_length"
1529     };
1530   static rtx (*const no_address_fn[]) (rtx)
1531     = {identity_fn,identity_fn, zero_fn, zero_fn};
1532   static rtx (*const address_fn[]) (rtx)
1533     = {max_fn, min_fn, one_fn, identity_fn};
1534   size_t i;
1535   struct attr_desc *length_attr, *new_attr;
1536   struct attr_value *av, *new_av;
1537   struct insn_ent *ie, *new_ie;
1538
1539   /* See if length attribute is defined.  If so, it must be numeric.  Make
1540      it special so we don't output anything for it.  */
1541   length_attr = find_attr (&length_str, 0);
1542   if (length_attr == 0)
1543     return;
1544
1545   if (! length_attr->is_numeric)
1546     fatal ("length attribute must be numeric");
1547
1548   length_attr->is_const = 0;
1549   length_attr->is_special = 1;
1550
1551   /* Make each new attribute, in turn.  */
1552   for (i = 0; i < ARRAY_SIZE (new_names); i++)
1553     {
1554       make_internal_attr (new_names[i],
1555                           substitute_address (length_attr->default_val->value,
1556                                               no_address_fn[i], address_fn[i]),
1557                           ATTR_NONE);
1558       new_attr = find_attr (&new_names[i], 0);
1559       for (av = length_attr->first_value; av; av = av->next)
1560         for (ie = av->first_insn; ie; ie = ie->next)
1561           {
1562             new_av = get_attr_value (substitute_address (av->value,
1563                                                          no_address_fn[i],
1564                                                          address_fn[i]),
1565                                      new_attr, ie->def->insn_code);
1566             new_ie = oballoc (sizeof (struct insn_ent));
1567             new_ie->def = ie->def;
1568             insert_insn_ent (new_av, new_ie);
1569           }
1570     }
1571 }
1572
1573 /* Utility functions called from above routine.  */
1574
1575 static rtx
1576 identity_fn (rtx exp)
1577 {
1578   return exp;
1579 }
1580
1581 static rtx
1582 zero_fn (rtx exp ATTRIBUTE_UNUSED)
1583 {
1584   return make_numeric_value (0);
1585 }
1586
1587 static rtx
1588 one_fn (rtx exp ATTRIBUTE_UNUSED)
1589 {
1590   return make_numeric_value (1);
1591 }
1592
1593 static rtx
1594 max_fn (rtx exp)
1595 {
1596   int unknown;
1597   return make_numeric_value (max_attr_value (exp, &unknown));
1598 }
1599
1600 static rtx
1601 min_fn (rtx exp)
1602 {
1603   int unknown;
1604   return make_numeric_value (min_attr_value (exp, &unknown));
1605 }
1606
1607 static void
1608 write_length_unit_log (void)
1609 {
1610   struct attr_desc *length_attr = find_attr (&length_str, 0);
1611   struct attr_value *av;
1612   struct insn_ent *ie;
1613   unsigned int length_unit_log, length_or;
1614   int unknown = 0;
1615
1616   if (length_attr == 0)
1617     return;
1618   length_or = or_attr_value (length_attr->default_val->value, &unknown);
1619   for (av = length_attr->first_value; av; av = av->next)
1620     for (ie = av->first_insn; ie; ie = ie->next)
1621       length_or |= or_attr_value (av->value, &unknown);
1622
1623   if (unknown)
1624     length_unit_log = 0;
1625   else
1626     {
1627       length_or = ~length_or;
1628       for (length_unit_log = 0; length_or & 1; length_or >>= 1)
1629         length_unit_log++;
1630     }
1631   printf ("const int length_unit_log = %u;\n", length_unit_log);
1632 }
1633
1634 /* Take a COND expression and see if any of the conditions in it can be
1635    simplified.  If any are known true or known false for the particular insn
1636    code, the COND can be further simplified.
1637
1638    Also call ourselves on any COND operations that are values of this COND.
1639
1640    We do not modify EXP; rather, we make and return a new rtx.  */
1641
1642 static rtx
1643 simplify_cond (rtx exp, int insn_code, int insn_index)
1644 {
1645   int i, j;
1646   /* We store the desired contents here,
1647      then build a new expression if they don't match EXP.  */
1648   rtx defval = XEXP (exp, 1);
1649   rtx new_defval = XEXP (exp, 1);
1650   int len = XVECLEN (exp, 0);
1651   rtx *tests = XNEWVEC (rtx, len);
1652   int allsame = 1;
1653   rtx ret;
1654
1655   /* This lets us free all storage allocated below, if appropriate.  */
1656   obstack_finish (rtl_obstack);
1657
1658   memcpy (tests, XVEC (exp, 0)->elem, len * sizeof (rtx));
1659
1660   /* See if default value needs simplification.  */
1661   if (GET_CODE (defval) == COND)
1662     new_defval = simplify_cond (defval, insn_code, insn_index);
1663
1664   /* Simplify the subexpressions, and see what tests we can get rid of.  */
1665
1666   for (i = 0; i < len; i += 2)
1667     {
1668       rtx newtest, newval;
1669
1670       /* Simplify this test.  */
1671       newtest = simplify_test_exp_in_temp (tests[i], insn_code, insn_index);
1672       tests[i] = newtest;
1673
1674       newval = tests[i + 1];
1675       /* See if this value may need simplification.  */
1676       if (GET_CODE (newval) == COND)
1677         newval = simplify_cond (newval, insn_code, insn_index);
1678
1679       /* Look for ways to delete or combine this test.  */
1680       if (newtest == true_rtx)
1681         {
1682           /* If test is true, make this value the default
1683              and discard this + any following tests.  */
1684           len = i;
1685           defval = tests[i + 1];
1686           new_defval = newval;
1687         }
1688
1689       else if (newtest == false_rtx)
1690         {
1691           /* If test is false, discard it and its value.  */
1692           for (j = i; j < len - 2; j++)
1693             tests[j] = tests[j + 2];
1694           i -= 2;
1695           len -= 2;
1696         }
1697
1698       else if (i > 0 && attr_equal_p (newval, tests[i - 1]))
1699         {
1700           /* If this value and the value for the prev test are the same,
1701              merge the tests.  */
1702
1703           tests[i - 2]
1704             = insert_right_side (IOR, tests[i - 2], newtest,
1705                                  insn_code, insn_index);
1706
1707           /* Delete this test/value.  */
1708           for (j = i; j < len - 2; j++)
1709             tests[j] = tests[j + 2];
1710           len -= 2;
1711           i -= 2;
1712         }
1713
1714       else
1715         tests[i + 1] = newval;
1716     }
1717
1718   /* If the last test in a COND has the same value
1719      as the default value, that test isn't needed.  */
1720
1721   while (len > 0 && attr_equal_p (tests[len - 1], new_defval))
1722     len -= 2;
1723
1724   /* See if we changed anything.  */
1725   if (len != XVECLEN (exp, 0) || new_defval != XEXP (exp, 1))
1726     allsame = 0;
1727   else
1728     for (i = 0; i < len; i++)
1729       if (! attr_equal_p (tests[i], XVECEXP (exp, 0, i)))
1730         {
1731           allsame = 0;
1732           break;
1733         }
1734
1735   if (len == 0)
1736     {
1737       if (GET_CODE (defval) == COND)
1738         ret = simplify_cond (defval, insn_code, insn_index);
1739       else
1740         ret = defval;
1741     }
1742   else if (allsame)
1743     ret = exp;
1744   else
1745     {
1746       rtx newexp = rtx_alloc (COND);
1747
1748       XVEC (newexp, 0) = rtvec_alloc (len);
1749       memcpy (XVEC (newexp, 0)->elem, tests, len * sizeof (rtx));
1750       XEXP (newexp, 1) = new_defval;
1751       ret = newexp;
1752     }
1753   free (tests);
1754   return ret;
1755 }
1756
1757 /* Remove an insn entry from an attribute value.  */
1758
1759 static void
1760 remove_insn_ent (struct attr_value *av, struct insn_ent *ie)
1761 {
1762   struct insn_ent *previe;
1763
1764   if (av->first_insn == ie)
1765     av->first_insn = ie->next;
1766   else
1767     {
1768       for (previe = av->first_insn; previe->next != ie; previe = previe->next)
1769         ;
1770       previe->next = ie->next;
1771     }
1772
1773   av->num_insns--;
1774   if (ie->def->insn_code == -1)
1775     av->has_asm_insn = 0;
1776
1777   num_insn_ents--;
1778 }
1779
1780 /* Insert an insn entry in an attribute value list.  */
1781
1782 static void
1783 insert_insn_ent (struct attr_value *av, struct insn_ent *ie)
1784 {
1785   ie->next = av->first_insn;
1786   av->first_insn = ie;
1787   av->num_insns++;
1788   if (ie->def->insn_code == -1)
1789     av->has_asm_insn = 1;
1790
1791   num_insn_ents++;
1792 }
1793
1794 /* This is a utility routine to take an expression that is a tree of either
1795    AND or IOR expressions and insert a new term.  The new term will be
1796    inserted at the right side of the first node whose code does not match
1797    the root.  A new node will be created with the root's code.  Its left
1798    side will be the old right side and its right side will be the new
1799    term.
1800
1801    If the `term' is itself a tree, all its leaves will be inserted.  */
1802
1803 static rtx
1804 insert_right_side (enum rtx_code code, rtx exp, rtx term, int insn_code, int insn_index)
1805 {
1806   rtx newexp;
1807
1808   /* Avoid consing in some special cases.  */
1809   if (code == AND && term == true_rtx)
1810     return exp;
1811   if (code == AND && term == false_rtx)
1812     return false_rtx;
1813   if (code == AND && exp == true_rtx)
1814     return term;
1815   if (code == AND && exp == false_rtx)
1816     return false_rtx;
1817   if (code == IOR && term == true_rtx)
1818     return true_rtx;
1819   if (code == IOR && term == false_rtx)
1820     return exp;
1821   if (code == IOR && exp == true_rtx)
1822     return true_rtx;
1823   if (code == IOR && exp == false_rtx)
1824     return term;
1825   if (attr_equal_p (exp, term))
1826     return exp;
1827
1828   if (GET_CODE (term) == code)
1829     {
1830       exp = insert_right_side (code, exp, XEXP (term, 0),
1831                                insn_code, insn_index);
1832       exp = insert_right_side (code, exp, XEXP (term, 1),
1833                                insn_code, insn_index);
1834
1835       return exp;
1836     }
1837
1838   if (GET_CODE (exp) == code)
1839     {
1840       rtx new = insert_right_side (code, XEXP (exp, 1),
1841                                    term, insn_code, insn_index);
1842       if (new != XEXP (exp, 1))
1843         /* Make a copy of this expression and call recursively.  */
1844         newexp = attr_rtx (code, XEXP (exp, 0), new);
1845       else
1846         newexp = exp;
1847     }
1848   else
1849     {
1850       /* Insert the new term.  */
1851       newexp = attr_rtx (code, exp, term);
1852     }
1853
1854   return simplify_test_exp_in_temp (newexp, insn_code, insn_index);
1855 }
1856
1857 /* If we have an expression which AND's a bunch of
1858         (not (eq_attrq "alternative" "n"))
1859    terms, we may have covered all or all but one of the possible alternatives.
1860    If so, we can optimize.  Similarly for IOR's of EQ_ATTR.
1861
1862    This routine is passed an expression and either AND or IOR.  It returns a
1863    bitmask indicating which alternatives are mentioned within EXP.  */
1864
1865 static int
1866 compute_alternative_mask (rtx exp, enum rtx_code code)
1867 {
1868   const char *string;
1869   if (GET_CODE (exp) == code)
1870     return compute_alternative_mask (XEXP (exp, 0), code)
1871            | compute_alternative_mask (XEXP (exp, 1), code);
1872
1873   else if (code == AND && GET_CODE (exp) == NOT
1874            && GET_CODE (XEXP (exp, 0)) == EQ_ATTR
1875            && XSTR (XEXP (exp, 0), 0) == alternative_name)
1876     string = XSTR (XEXP (exp, 0), 1);
1877
1878   else if (code == IOR && GET_CODE (exp) == EQ_ATTR
1879            && XSTR (exp, 0) == alternative_name)
1880     string = XSTR (exp, 1);
1881
1882   else if (GET_CODE (exp) == EQ_ATTR_ALT)
1883     {
1884       if (code == AND && XINT (exp, 1))
1885         return XINT (exp, 0);
1886
1887       if (code == IOR && !XINT (exp, 1))
1888         return XINT (exp, 0);
1889
1890       return 0;
1891     }
1892   else
1893     return 0;
1894
1895   if (string[1] == 0)
1896     return 1 << (string[0] - '0');
1897   return 1 << atoi (string);
1898 }
1899
1900 /* Given I, a single-bit mask, return RTX to compare the `alternative'
1901    attribute with the value represented by that bit.  */
1902
1903 static rtx
1904 make_alternative_compare (int mask)
1905 {
1906   return mk_attr_alt (mask);
1907 }
1908
1909 /* If we are processing an (eq_attr "attr" "value") test, we find the value
1910    of "attr" for this insn code.  From that value, we can compute a test
1911    showing when the EQ_ATTR will be true.  This routine performs that
1912    computation.  If a test condition involves an address, we leave the EQ_ATTR
1913    intact because addresses are only valid for the `length' attribute.
1914
1915    EXP is the EQ_ATTR expression and VALUE is the value of that attribute
1916    for the insn corresponding to INSN_CODE and INSN_INDEX.  */
1917
1918 static rtx
1919 evaluate_eq_attr (rtx exp, rtx value, int insn_code, int insn_index)
1920 {
1921   rtx orexp, andexp;
1922   rtx right;
1923   rtx newexp;
1924   int i;
1925
1926   switch (GET_CODE (value))
1927     {
1928     case CONST_STRING:
1929       if (! strcmp_check (XSTR (value, 0), XSTR (exp, 1)))
1930         newexp = true_rtx;
1931       else
1932         newexp = false_rtx;
1933       break;
1934
1935     case SYMBOL_REF:
1936       {
1937         char *p;
1938         char string[256];
1939
1940         gcc_assert (GET_CODE (exp) == EQ_ATTR);
1941         gcc_assert (strlen (XSTR (exp, 0)) + strlen (XSTR (exp, 1)) + 2
1942                     <= 256);
1943
1944         strcpy (string, XSTR (exp, 0));
1945         strcat (string, "_");
1946         strcat (string, XSTR (exp, 1));
1947         for (p = string; *p; p++)
1948           *p = TOUPPER (*p);
1949
1950         newexp = attr_rtx (EQ, value,
1951                            attr_rtx (SYMBOL_REF,
1952                                      DEF_ATTR_STRING (string)));
1953         break;
1954       }
1955
1956     case COND:
1957       /* We construct an IOR of all the cases for which the
1958          requested attribute value is present.  Since we start with
1959          FALSE, if it is not present, FALSE will be returned.
1960
1961          Each case is the AND of the NOT's of the previous conditions with the
1962          current condition; in the default case the current condition is TRUE.
1963
1964          For each possible COND value, call ourselves recursively.
1965
1966          The extra TRUE and FALSE expressions will be eliminated by another
1967          call to the simplification routine.  */
1968
1969       orexp = false_rtx;
1970       andexp = true_rtx;
1971
1972       for (i = 0; i < XVECLEN (value, 0); i += 2)
1973         {
1974           rtx this = simplify_test_exp_in_temp (XVECEXP (value, 0, i),
1975                                                 insn_code, insn_index);
1976
1977           right = insert_right_side (AND, andexp, this,
1978                                      insn_code, insn_index);
1979           right = insert_right_side (AND, right,
1980                                      evaluate_eq_attr (exp,
1981                                                        XVECEXP (value, 0,
1982                                                                 i + 1),
1983                                                        insn_code, insn_index),
1984                                      insn_code, insn_index);
1985           orexp = insert_right_side (IOR, orexp, right,
1986                                      insn_code, insn_index);
1987
1988           /* Add this condition into the AND expression.  */
1989           newexp = attr_rtx (NOT, this);
1990           andexp = insert_right_side (AND, andexp, newexp,
1991                                       insn_code, insn_index);
1992         }
1993
1994       /* Handle the default case.  */
1995       right = insert_right_side (AND, andexp,
1996                                  evaluate_eq_attr (exp, XEXP (value, 1),
1997                                                    insn_code, insn_index),
1998                                  insn_code, insn_index);
1999       newexp = insert_right_side (IOR, orexp, right, insn_code, insn_index);
2000       break;
2001
2002     default:
2003       gcc_unreachable ();
2004     }
2005
2006   /* If uses an address, must return original expression.  But set the
2007      ATTR_IND_SIMPLIFIED_P bit so we don't try to simplify it again.  */
2008
2009   address_used = 0;
2010   walk_attr_value (newexp);
2011
2012   if (address_used)
2013     {
2014       if (! ATTR_IND_SIMPLIFIED_P (exp))
2015         return copy_rtx_unchanging (exp);
2016       return exp;
2017     }
2018   else
2019     return newexp;
2020 }
2021
2022 /* This routine is called when an AND of a term with a tree of AND's is
2023    encountered.  If the term or its complement is present in the tree, it
2024    can be replaced with TRUE or FALSE, respectively.
2025
2026    Note that (eq_attr "att" "v1") and (eq_attr "att" "v2") cannot both
2027    be true and hence are complementary.
2028
2029    There is one special case:  If we see
2030         (and (not (eq_attr "att" "v1"))
2031              (eq_attr "att" "v2"))
2032    this can be replaced by (eq_attr "att" "v2").  To do this we need to
2033    replace the term, not anything in the AND tree.  So we pass a pointer to
2034    the term.  */
2035
2036 static rtx
2037 simplify_and_tree (rtx exp, rtx *pterm, int insn_code, int insn_index)
2038 {
2039   rtx left, right;
2040   rtx newexp;
2041   rtx temp;
2042   int left_eliminates_term, right_eliminates_term;
2043
2044   if (GET_CODE (exp) == AND)
2045     {
2046       left  = simplify_and_tree (XEXP (exp, 0), pterm, insn_code, insn_index);
2047       right = simplify_and_tree (XEXP (exp, 1), pterm, insn_code, insn_index);
2048       if (left != XEXP (exp, 0) || right != XEXP (exp, 1))
2049         {
2050           newexp = attr_rtx (AND, left, right);
2051
2052           exp = simplify_test_exp_in_temp (newexp, insn_code, insn_index);
2053         }
2054     }
2055
2056   else if (GET_CODE (exp) == IOR)
2057     {
2058       /* For the IOR case, we do the same as above, except that we can
2059          only eliminate `term' if both sides of the IOR would do so.  */
2060       temp = *pterm;
2061       left = simplify_and_tree (XEXP (exp, 0), &temp, insn_code, insn_index);
2062       left_eliminates_term = (temp == true_rtx);
2063
2064       temp = *pterm;
2065       right = simplify_and_tree (XEXP (exp, 1), &temp, insn_code, insn_index);
2066       right_eliminates_term = (temp == true_rtx);
2067
2068       if (left_eliminates_term && right_eliminates_term)
2069         *pterm = true_rtx;
2070
2071       if (left != XEXP (exp, 0) || right != XEXP (exp, 1))
2072         {
2073           newexp = attr_rtx (IOR, left, right);
2074
2075           exp = simplify_test_exp_in_temp (newexp, insn_code, insn_index);
2076         }
2077     }
2078
2079   /* Check for simplifications.  Do some extra checking here since this
2080      routine is called so many times.  */
2081
2082   if (exp == *pterm)
2083     return true_rtx;
2084
2085   else if (GET_CODE (exp) == NOT && XEXP (exp, 0) == *pterm)
2086     return false_rtx;
2087
2088   else if (GET_CODE (*pterm) == NOT && exp == XEXP (*pterm, 0))
2089     return false_rtx;
2090
2091   else if (GET_CODE (exp) == EQ_ATTR_ALT && GET_CODE (*pterm) == EQ_ATTR_ALT)
2092     {
2093       if (attr_alt_subset_p (*pterm, exp))
2094         return true_rtx;
2095
2096       if (attr_alt_subset_of_compl_p (*pterm, exp))
2097         return false_rtx;
2098
2099       if (attr_alt_subset_p (exp, *pterm))
2100         *pterm = true_rtx;
2101
2102       return exp;
2103     }
2104
2105   else if (GET_CODE (exp) == EQ_ATTR && GET_CODE (*pterm) == EQ_ATTR)
2106     {
2107       if (XSTR (exp, 0) != XSTR (*pterm, 0))
2108         return exp;
2109
2110       if (! strcmp_check (XSTR (exp, 1), XSTR (*pterm, 1)))
2111         return true_rtx;
2112       else
2113         return false_rtx;
2114     }
2115
2116   else if (GET_CODE (*pterm) == EQ_ATTR && GET_CODE (exp) == NOT
2117            && GET_CODE (XEXP (exp, 0)) == EQ_ATTR)
2118     {
2119       if (XSTR (*pterm, 0) != XSTR (XEXP (exp, 0), 0))
2120         return exp;
2121
2122       if (! strcmp_check (XSTR (*pterm, 1), XSTR (XEXP (exp, 0), 1)))
2123         return false_rtx;
2124       else
2125         return true_rtx;
2126     }
2127
2128   else if (GET_CODE (exp) == EQ_ATTR && GET_CODE (*pterm) == NOT
2129            && GET_CODE (XEXP (*pterm, 0)) == EQ_ATTR)
2130     {
2131       if (XSTR (exp, 0) != XSTR (XEXP (*pterm, 0), 0))
2132         return exp;
2133
2134       if (! strcmp_check (XSTR (exp, 1), XSTR (XEXP (*pterm, 0), 1)))
2135         return false_rtx;
2136       else
2137         *pterm = true_rtx;
2138     }
2139
2140   else if (GET_CODE (exp) == NOT && GET_CODE (*pterm) == NOT)
2141     {
2142       if (attr_equal_p (XEXP (exp, 0), XEXP (*pterm, 0)))
2143         return true_rtx;
2144     }
2145
2146   else if (GET_CODE (exp) == NOT)
2147     {
2148       if (attr_equal_p (XEXP (exp, 0), *pterm))
2149         return false_rtx;
2150     }
2151
2152   else if (GET_CODE (*pterm) == NOT)
2153     {
2154       if (attr_equal_p (XEXP (*pterm, 0), exp))
2155         return false_rtx;
2156     }
2157
2158   else if (attr_equal_p (exp, *pterm))
2159     return true_rtx;
2160
2161   return exp;
2162 }
2163
2164 /* Similar to `simplify_and_tree', but for IOR trees.  */
2165
2166 static rtx
2167 simplify_or_tree (rtx exp, rtx *pterm, int insn_code, int insn_index)
2168 {
2169   rtx left, right;
2170   rtx newexp;
2171   rtx temp;
2172   int left_eliminates_term, right_eliminates_term;
2173
2174   if (GET_CODE (exp) == IOR)
2175     {
2176       left  = simplify_or_tree (XEXP (exp, 0), pterm, insn_code, insn_index);
2177       right = simplify_or_tree (XEXP (exp, 1), pterm, insn_code, insn_index);
2178       if (left != XEXP (exp, 0) || right != XEXP (exp, 1))
2179         {
2180           newexp = attr_rtx (GET_CODE (exp), left, right);
2181
2182           exp = simplify_test_exp_in_temp (newexp, insn_code, insn_index);
2183         }
2184     }
2185
2186   else if (GET_CODE (exp) == AND)
2187     {
2188       /* For the AND case, we do the same as above, except that we can
2189          only eliminate `term' if both sides of the AND would do so.  */
2190       temp = *pterm;
2191       left = simplify_or_tree (XEXP (exp, 0), &temp, insn_code, insn_index);
2192       left_eliminates_term = (temp == false_rtx);
2193
2194       temp = *pterm;
2195       right = simplify_or_tree (XEXP (exp, 1), &temp, insn_code, insn_index);
2196       right_eliminates_term = (temp == false_rtx);
2197
2198       if (left_eliminates_term && right_eliminates_term)
2199         *pterm = false_rtx;
2200
2201       if (left != XEXP (exp, 0) || right != XEXP (exp, 1))
2202         {
2203           newexp = attr_rtx (GET_CODE (exp), left, right);
2204
2205           exp = simplify_test_exp_in_temp (newexp, insn_code, insn_index);
2206         }
2207     }
2208
2209   if (attr_equal_p (exp, *pterm))
2210     return false_rtx;
2211
2212   else if (GET_CODE (exp) == NOT && attr_equal_p (XEXP (exp, 0), *pterm))
2213     return true_rtx;
2214
2215   else if (GET_CODE (*pterm) == NOT && attr_equal_p (XEXP (*pterm, 0), exp))
2216     return true_rtx;
2217
2218   else if (GET_CODE (*pterm) == EQ_ATTR && GET_CODE (exp) == NOT
2219            && GET_CODE (XEXP (exp, 0)) == EQ_ATTR
2220            && XSTR (*pterm, 0) == XSTR (XEXP (exp, 0), 0))
2221     *pterm = false_rtx;
2222
2223   else if (GET_CODE (exp) == EQ_ATTR && GET_CODE (*pterm) == NOT
2224            && GET_CODE (XEXP (*pterm, 0)) == EQ_ATTR
2225            && XSTR (exp, 0) == XSTR (XEXP (*pterm, 0), 0))
2226     return false_rtx;
2227
2228   return exp;
2229 }
2230
2231 /* Compute approximate cost of the expression.  Used to decide whether
2232    expression is cheap enough for inline.  */
2233 static int
2234 attr_rtx_cost (rtx x)
2235 {
2236   int cost = 0;
2237   enum rtx_code code;
2238   if (!x)
2239     return 0;
2240   code = GET_CODE (x);
2241   switch (code)
2242     {
2243     case MATCH_OPERAND:
2244       if (XSTR (x, 1)[0])
2245         return 10;
2246       else
2247         return 0;
2248
2249     case EQ_ATTR_ALT:
2250       return 0;
2251
2252     case EQ_ATTR:
2253       /* Alternatives don't result into function call.  */
2254       if (!strcmp_check (XSTR (x, 0), alternative_name))
2255         return 0;
2256       else
2257         return 5;
2258     default:
2259       {
2260         int i, j;
2261         const char *fmt = GET_RTX_FORMAT (code);
2262         for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2263           {
2264             switch (fmt[i])
2265               {
2266               case 'V':
2267               case 'E':
2268                 for (j = 0; j < XVECLEN (x, i); j++)
2269                   cost += attr_rtx_cost (XVECEXP (x, i, j));
2270                 break;
2271               case 'e':
2272                 cost += attr_rtx_cost (XEXP (x, i));
2273                 break;
2274               }
2275           }
2276       }
2277       break;
2278     }
2279   return cost;
2280 }
2281
2282 /* Simplify test expression and use temporary obstack in order to avoid
2283    memory bloat.  Use ATTR_IND_SIMPLIFIED to avoid unnecessary simplifications
2284    and avoid unnecessary copying if possible.  */
2285
2286 static rtx
2287 simplify_test_exp_in_temp (rtx exp, int insn_code, int insn_index)
2288 {
2289   rtx x;
2290   struct obstack *old;
2291   if (ATTR_IND_SIMPLIFIED_P (exp))
2292     return exp;
2293   old = rtl_obstack;
2294   rtl_obstack = temp_obstack;
2295   x = simplify_test_exp (exp, insn_code, insn_index);
2296   rtl_obstack = old;
2297   if (x == exp || rtl_obstack == temp_obstack)
2298     return x;
2299   return attr_copy_rtx (x);
2300 }
2301
2302 /* Returns true if S1 is a subset of S2.  */
2303
2304 static bool
2305 attr_alt_subset_p (rtx s1, rtx s2)
2306 {
2307   switch ((XINT (s1, 1) << 1) | XINT (s2, 1))
2308     {
2309     case (0 << 1) | 0:
2310       return !(XINT (s1, 0) &~ XINT (s2, 0));
2311
2312     case (0 << 1) | 1:
2313       return !(XINT (s1, 0) & XINT (s2, 0));
2314
2315     case (1 << 1) | 0:
2316       return false;
2317
2318     case (1 << 1) | 1:
2319       return !(XINT (s2, 0) &~ XINT (s1, 0));
2320
2321     default:
2322       gcc_unreachable ();
2323     }
2324 }
2325
2326 /* Returns true if S1 is a subset of complement of S2.  */
2327
2328 static bool
2329 attr_alt_subset_of_compl_p (rtx s1, rtx s2)
2330 {
2331   switch ((XINT (s1, 1) << 1) | XINT (s2, 1))
2332     {
2333     case (0 << 1) | 0:
2334       return !(XINT (s1, 0) & XINT (s2, 0));
2335
2336     case (0 << 1) | 1:
2337       return !(XINT (s1, 0) & ~XINT (s2, 0));
2338
2339     case (1 << 1) | 0:
2340       return !(XINT (s2, 0) &~ XINT (s1, 0));
2341
2342     case (1 << 1) | 1:
2343       return false;
2344
2345     default:
2346       gcc_unreachable ();
2347     }
2348 }
2349
2350 /* Return EQ_ATTR_ALT expression representing intersection of S1 and S2.  */
2351
2352 static rtx
2353 attr_alt_intersection (rtx s1, rtx s2)
2354 {
2355   rtx result = rtx_alloc (EQ_ATTR_ALT);
2356
2357   switch ((XINT (s1, 1) << 1) | XINT (s2, 1))
2358     {
2359     case (0 << 1) | 0:
2360       XINT (result, 0) = XINT (s1, 0) & XINT (s2, 0);
2361       break;
2362     case (0 << 1) | 1:
2363       XINT (result, 0) = XINT (s1, 0) & ~XINT (s2, 0);
2364       break;
2365     case (1 << 1) | 0:
2366       XINT (result, 0) = XINT (s2, 0) & ~XINT (s1, 0);
2367       break;
2368     case (1 << 1) | 1:
2369       XINT (result, 0) = XINT (s1, 0) | XINT (s2, 0);
2370       break;
2371     default:
2372       gcc_unreachable ();
2373     }
2374   XINT (result, 1) = XINT (s1, 1) & XINT (s2, 1);
2375
2376   return result;
2377 }
2378
2379 /* Return EQ_ATTR_ALT expression representing union of S1 and S2.  */
2380
2381 static rtx
2382 attr_alt_union (rtx s1, rtx s2)
2383 {
2384   rtx result = rtx_alloc (EQ_ATTR_ALT);
2385
2386   switch ((XINT (s1, 1) << 1) | XINT (s2, 1))
2387     {
2388     case (0 << 1) | 0:
2389       XINT (result, 0) = XINT (s1, 0) | XINT (s2, 0);
2390       break;
2391     case (0 << 1) | 1:
2392       XINT (result, 0) = XINT (s2, 0) & ~XINT (s1, 0);
2393       break;
2394     case (1 << 1) | 0:
2395       XINT (result, 0) = XINT (s1, 0) & ~XINT (s2, 0);
2396       break;
2397     case (1 << 1) | 1:
2398       XINT (result, 0) = XINT (s1, 0) & XINT (s2, 0);
2399       break;
2400     default:
2401       gcc_unreachable ();
2402     }
2403
2404   XINT (result, 1) = XINT (s1, 1) | XINT (s2, 1);
2405   return result;
2406 }
2407
2408 /* Return EQ_ATTR_ALT expression representing complement of S.  */
2409
2410 static rtx
2411 attr_alt_complement (rtx s)
2412 {
2413   rtx result = rtx_alloc (EQ_ATTR_ALT);
2414
2415   XINT (result, 0) = XINT (s, 0);
2416   XINT (result, 1) = 1 - XINT (s, 1);
2417
2418   return result;
2419 }
2420
2421 /* Return EQ_ATTR_ALT expression representing set containing elements set
2422    in E.  */
2423
2424 static rtx
2425 mk_attr_alt (int e)
2426 {
2427   rtx result = rtx_alloc (EQ_ATTR_ALT);
2428
2429   XINT (result, 0) = e;
2430   XINT (result, 1) = 0;
2431
2432   return result;
2433 }
2434
2435 /* Given an expression, see if it can be simplified for a particular insn
2436    code based on the values of other attributes being tested.  This can
2437    eliminate nested get_attr_... calls.
2438
2439    Note that if an endless recursion is specified in the patterns, the
2440    optimization will loop.  However, it will do so in precisely the cases where
2441    an infinite recursion loop could occur during compilation.  It's better that
2442    it occurs here!  */
2443
2444 static rtx
2445 simplify_test_exp (rtx exp, int insn_code, int insn_index)
2446 {
2447   rtx left, right;
2448   struct attr_desc *attr;
2449   struct attr_value *av;
2450   struct insn_ent *ie;
2451   int i;
2452   rtx newexp = exp;
2453   bool left_alt, right_alt;
2454
2455   /* Don't re-simplify something we already simplified.  */
2456   if (ATTR_IND_SIMPLIFIED_P (exp) || ATTR_CURR_SIMPLIFIED_P (exp))
2457     return exp;
2458
2459   switch (GET_CODE (exp))
2460     {
2461     case AND:
2462       left = SIMPLIFY_TEST_EXP (XEXP (exp, 0), insn_code, insn_index);
2463       if (left == false_rtx)
2464         return false_rtx;
2465       right = SIMPLIFY_TEST_EXP (XEXP (exp, 1), insn_code, insn_index);
2466       if (right == false_rtx)
2467         return false_rtx;
2468
2469       if (GET_CODE (left) == EQ_ATTR_ALT
2470           && GET_CODE (right) == EQ_ATTR_ALT)
2471         {
2472           exp = attr_alt_intersection (left, right);
2473           return simplify_test_exp (exp, insn_code, insn_index);
2474         }
2475
2476       /* If either side is an IOR and we have (eq_attr "alternative" ..")
2477          present on both sides, apply the distributive law since this will
2478          yield simplifications.  */
2479       if ((GET_CODE (left) == IOR || GET_CODE (right) == IOR)
2480           && compute_alternative_mask (left, IOR)
2481           && compute_alternative_mask (right, IOR))
2482         {
2483           if (GET_CODE (left) == IOR)
2484             {
2485               rtx tem = left;
2486               left = right;
2487               right = tem;
2488             }
2489
2490           newexp = attr_rtx (IOR,
2491                              attr_rtx (AND, left, XEXP (right, 0)),
2492                              attr_rtx (AND, left, XEXP (right, 1)));
2493
2494           return SIMPLIFY_TEST_EXP (newexp, insn_code, insn_index);
2495         }
2496
2497       /* Try with the term on both sides.  */
2498       right = simplify_and_tree (right, &left, insn_code, insn_index);
2499       if (left == XEXP (exp, 0) && right == XEXP (exp, 1))
2500         left = simplify_and_tree (left, &right, insn_code, insn_index);
2501
2502       if (left == false_rtx || right == false_rtx)
2503         return false_rtx;
2504       else if (left == true_rtx)
2505         {
2506           return right;
2507         }
2508       else if (right == true_rtx)
2509         {
2510           return left;
2511         }
2512       /* See if all or all but one of the insn's alternatives are specified
2513          in this tree.  Optimize if so.  */
2514
2515       if (GET_CODE (left) == NOT)
2516         left_alt = (GET_CODE (XEXP (left, 0)) == EQ_ATTR
2517                     && XSTR (XEXP (left, 0), 0) == alternative_name);
2518       else
2519         left_alt = (GET_CODE (left) == EQ_ATTR_ALT
2520                     && XINT (left, 1));
2521
2522       if (GET_CODE (right) == NOT)
2523         right_alt = (GET_CODE (XEXP (right, 0)) == EQ_ATTR
2524                      && XSTR (XEXP (right, 0), 0) == alternative_name);
2525       else
2526         right_alt = (GET_CODE (right) == EQ_ATTR_ALT
2527                      && XINT (right, 1));
2528
2529       if (insn_code >= 0
2530           && (GET_CODE (left) == AND
2531               || left_alt
2532               || GET_CODE (right) == AND
2533               || right_alt))
2534         {
2535           i = compute_alternative_mask (exp, AND);
2536           if (i & ~insn_alternatives[insn_code])
2537             fatal ("invalid alternative specified for pattern number %d",
2538                    insn_index);
2539
2540           /* If all alternatives are excluded, this is false.  */
2541           i ^= insn_alternatives[insn_code];
2542           if (i == 0)
2543             return false_rtx;
2544           else if ((i & (i - 1)) == 0 && insn_alternatives[insn_code] > 1)
2545             {
2546               /* If just one excluded, AND a comparison with that one to the
2547                  front of the tree.  The others will be eliminated by
2548                  optimization.  We do not want to do this if the insn has one
2549                  alternative and we have tested none of them!  */
2550               left = make_alternative_compare (i);
2551               right = simplify_and_tree (exp, &left, insn_code, insn_index);
2552               newexp = attr_rtx (AND, left, right);
2553
2554               return SIMPLIFY_TEST_EXP (newexp, insn_code, insn_index);
2555             }
2556         }
2557
2558       if (left != XEXP (exp, 0) || right != XEXP (exp, 1))
2559         {
2560           newexp = attr_rtx (AND, left, right);
2561           return SIMPLIFY_TEST_EXP (newexp, insn_code, insn_index);
2562         }
2563       break;
2564
2565     case IOR:
2566       left = SIMPLIFY_TEST_EXP (XEXP (exp, 0), insn_code, insn_index);
2567       if (left == true_rtx)
2568         return true_rtx;
2569       right = SIMPLIFY_TEST_EXP (XEXP (exp, 1), insn_code, insn_index);
2570       if (right == true_rtx)
2571         return true_rtx;
2572
2573       if (GET_CODE (left) == EQ_ATTR_ALT
2574           && GET_CODE (right) == EQ_ATTR_ALT)
2575         {
2576           exp = attr_alt_union (left, right);
2577           return simplify_test_exp (exp, insn_code, insn_index);
2578         }
2579
2580       right = simplify_or_tree (right, &left, insn_code, insn_index);
2581       if (left == XEXP (exp, 0) && right == XEXP (exp, 1))
2582         left = simplify_or_tree (left, &right, insn_code, insn_index);
2583
2584       if (right == true_rtx || left == true_rtx)
2585         return true_rtx;
2586       else if (left == false_rtx)
2587         {
2588           return right;
2589         }
2590       else if (right == false_rtx)
2591         {
2592           return left;
2593         }
2594
2595       /* Test for simple cases where the distributive law is useful.  I.e.,
2596             convert (ior (and (x) (y))
2597                          (and (x) (z)))
2598             to      (and (x)
2599                          (ior (y) (z)))
2600        */
2601
2602       else if (GET_CODE (left) == AND && GET_CODE (right) == AND
2603                && attr_equal_p (XEXP (left, 0), XEXP (right, 0)))
2604         {
2605           newexp = attr_rtx (IOR, XEXP (left, 1), XEXP (right, 1));
2606
2607           left = XEXP (left, 0);
2608           right = newexp;
2609           newexp = attr_rtx (AND, left, right);
2610           return SIMPLIFY_TEST_EXP (newexp, insn_code, insn_index);
2611         }
2612
2613       /* See if all or all but one of the insn's alternatives are specified
2614          in this tree.  Optimize if so.  */
2615
2616       else if (insn_code >= 0
2617                && (GET_CODE (left) == IOR
2618                    || (GET_CODE (left) == EQ_ATTR_ALT
2619                        && !XINT (left, 1))
2620                    || (GET_CODE (left) == EQ_ATTR
2621                        && XSTR (left, 0) == alternative_name)
2622                    || GET_CODE (right) == IOR
2623                    || (GET_CODE (right) == EQ_ATTR_ALT
2624                        && !XINT (right, 1))
2625                    || (GET_CODE (right) == EQ_ATTR
2626                        && XSTR (right, 0) == alternative_name)))
2627         {
2628           i = compute_alternative_mask (exp, IOR);
2629           if (i & ~insn_alternatives[insn_code])
2630             fatal ("invalid alternative specified for pattern number %d",
2631                    insn_index);
2632
2633           /* If all alternatives are included, this is true.  */
2634           i ^= insn_alternatives[insn_code];
2635           if (i == 0)
2636             return true_rtx;
2637           else if ((i & (i - 1)) == 0 && insn_alternatives[insn_code] > 1)
2638             {
2639               /* If just one excluded, IOR a comparison with that one to the
2640                  front of the tree.  The others will be eliminated by
2641                  optimization.  We do not want to do this if the insn has one
2642                  alternative and we have tested none of them!  */
2643               left = make_alternative_compare (i);
2644               right = simplify_and_tree (exp, &left, insn_code, insn_index);
2645               newexp = attr_rtx (IOR, attr_rtx (NOT, left), right);
2646
2647               return SIMPLIFY_TEST_EXP (newexp, insn_code, insn_index);
2648             }
2649         }
2650
2651       if (left != XEXP (exp, 0) || right != XEXP (exp, 1))
2652         {
2653           newexp = attr_rtx (IOR, left, right);
2654           return SIMPLIFY_TEST_EXP (newexp, insn_code, insn_index);
2655         }
2656       break;
2657
2658     case NOT:
2659       if (GET_CODE (XEXP (exp, 0)) == NOT)
2660         {
2661           left = SIMPLIFY_TEST_EXP (XEXP (XEXP (exp, 0), 0),
2662                                     insn_code, insn_index);
2663           return left;
2664         }
2665
2666       left = SIMPLIFY_TEST_EXP (XEXP (exp, 0), insn_code, insn_index);
2667       if (GET_CODE (left) == NOT)
2668         return XEXP (left, 0);
2669
2670       if (left == false_rtx)
2671         return true_rtx;
2672       if (left == true_rtx)
2673         return false_rtx;
2674
2675       if (GET_CODE (left) == EQ_ATTR_ALT)
2676         {
2677           exp = attr_alt_complement (left);
2678           return simplify_test_exp (exp, insn_code, insn_index);
2679         }
2680
2681       /* Try to apply De`Morgan's laws.  */
2682       if (GET_CODE (left) == IOR)
2683         {
2684           newexp = attr_rtx (AND,
2685                              attr_rtx (NOT, XEXP (left, 0)),
2686                              attr_rtx (NOT, XEXP (left, 1)));
2687
2688           newexp = SIMPLIFY_TEST_EXP (newexp, insn_code, insn_index);
2689         }
2690       else if (GET_CODE (left) == AND)
2691         {
2692           newexp = attr_rtx (IOR,
2693                              attr_rtx (NOT, XEXP (left, 0)),
2694                              attr_rtx (NOT, XEXP (left, 1)));
2695
2696           newexp = SIMPLIFY_TEST_EXP (newexp, insn_code, insn_index);
2697         }
2698       else if (left != XEXP (exp, 0))
2699         {
2700           newexp = attr_rtx (NOT, left);
2701         }
2702       break;
2703
2704     case EQ_ATTR_ALT:
2705       if (!XINT (exp, 0))
2706         return XINT (exp, 1) ? true_rtx : false_rtx;
2707       break;
2708
2709     case EQ_ATTR:
2710       if (XSTR (exp, 0) == alternative_name)
2711         {
2712           newexp = mk_attr_alt (1 << atoi (XSTR (exp, 1)));
2713           break;
2714         }
2715
2716       /* Look at the value for this insn code in the specified attribute.
2717          We normally can replace this comparison with the condition that
2718          would give this insn the values being tested for.  */
2719       if (insn_code >= 0
2720           && (attr = find_attr (&XSTR (exp, 0), 0)) != NULL)
2721         for (av = attr->first_value; av; av = av->next)
2722           for (ie = av->first_insn; ie; ie = ie->next)
2723             if (ie->def->insn_code == insn_code)
2724               {
2725                 rtx x;
2726                 x = evaluate_eq_attr (exp, av->value, insn_code, insn_index);
2727                 x = SIMPLIFY_TEST_EXP (x, insn_code, insn_index);
2728                 if (attr_rtx_cost(x) < 20)
2729                   return x;
2730               }
2731       break;
2732
2733     default:
2734       break;
2735     }
2736
2737   /* We have already simplified this expression.  Simplifying it again
2738      won't buy anything unless we weren't given a valid insn code
2739      to process (i.e., we are canonicalizing something.).  */
2740   if (insn_code != -2
2741       && ! ATTR_IND_SIMPLIFIED_P (newexp))
2742     return copy_rtx_unchanging (newexp);
2743
2744   return newexp;
2745 }
2746
2747 /* Optimize the attribute lists by seeing if we can determine conditional
2748    values from the known values of other attributes.  This will save subroutine
2749    calls during the compilation.  */
2750
2751 static void
2752 optimize_attrs (void)
2753 {
2754   struct attr_desc *attr;
2755   struct attr_value *av;
2756   struct insn_ent *ie;
2757   rtx newexp;
2758   int i;
2759   struct attr_value_list
2760   {
2761     struct attr_value *av;
2762     struct insn_ent *ie;
2763     struct attr_desc *attr;
2764     struct attr_value_list *next;
2765   };
2766   struct attr_value_list **insn_code_values;
2767   struct attr_value_list *ivbuf;
2768   struct attr_value_list *iv;
2769
2770   /* For each insn code, make a list of all the insn_ent's for it,
2771      for all values for all attributes.  */
2772
2773   if (num_insn_ents == 0)
2774     return;
2775
2776   /* Make 2 extra elements, for "code" values -2 and -1.  */
2777   insn_code_values = XCNEWVEC (struct attr_value_list *, insn_code_number + 2);
2778
2779   /* Offset the table address so we can index by -2 or -1.  */
2780   insn_code_values += 2;
2781
2782   iv = ivbuf = XNEWVEC (struct attr_value_list, num_insn_ents);
2783
2784   for (i = 0; i < MAX_ATTRS_INDEX; i++)
2785     for (attr = attrs[i]; attr; attr = attr->next)
2786       for (av = attr->first_value; av; av = av->next)
2787         for (ie = av->first_insn; ie; ie = ie->next)
2788           {
2789             iv->attr = attr;
2790             iv->av = av;
2791             iv->ie = ie;
2792             iv->next = insn_code_values[ie->def->insn_code];
2793             insn_code_values[ie->def->insn_code] = iv;
2794             iv++;
2795           }
2796
2797   /* Sanity check on num_insn_ents.  */
2798   gcc_assert (iv == ivbuf + num_insn_ents);
2799
2800   /* Process one insn code at a time.  */
2801   for (i = -2; i < insn_code_number; i++)
2802     {
2803       /* Clear the ATTR_CURR_SIMPLIFIED_P flag everywhere relevant.
2804          We use it to mean "already simplified for this insn".  */
2805       for (iv = insn_code_values[i]; iv; iv = iv->next)
2806         clear_struct_flag (iv->av->value);
2807
2808       for (iv = insn_code_values[i]; iv; iv = iv->next)
2809         {
2810           struct obstack *old = rtl_obstack;
2811
2812           attr = iv->attr;
2813           av = iv->av;
2814           ie = iv->ie;
2815           if (GET_CODE (av->value) != COND)
2816             continue;
2817
2818           rtl_obstack = temp_obstack;
2819           newexp = av->value;
2820           while (GET_CODE (newexp) == COND)
2821             {
2822               rtx newexp2 = simplify_cond (newexp, ie->def->insn_code,
2823                                            ie->def->insn_index);
2824               if (newexp2 == newexp)
2825                 break;
2826               newexp = newexp2;
2827             }
2828
2829           rtl_obstack = old;
2830           if (newexp != av->value)
2831             {
2832               newexp = attr_copy_rtx (newexp);
2833               remove_insn_ent (av, ie);
2834               av = get_attr_value (newexp, attr, ie->def->insn_code);
2835               iv->av = av;
2836               insert_insn_ent (av, ie);
2837             }
2838         }
2839     }
2840
2841   free (ivbuf);
2842   free (insn_code_values - 2);
2843 }
2844
2845 /* Clear the ATTR_CURR_SIMPLIFIED_P flag in EXP and its subexpressions.  */
2846
2847 static void
2848 clear_struct_flag (rtx x)
2849 {
2850   int i;
2851   int j;
2852   enum rtx_code code;
2853   const char *fmt;
2854
2855   ATTR_CURR_SIMPLIFIED_P (x) = 0;
2856   if (ATTR_IND_SIMPLIFIED_P (x))
2857     return;
2858
2859   code = GET_CODE (x);
2860
2861   switch (code)
2862     {
2863     case REG:
2864     case CONST_INT:
2865     case CONST_DOUBLE:
2866     case CONST_VECTOR:
2867     case SYMBOL_REF:
2868     case CODE_LABEL:
2869     case PC:
2870     case CC0:
2871     case EQ_ATTR:
2872     case ATTR_FLAG:
2873       return;
2874
2875     default:
2876       break;
2877     }
2878
2879   /* Compare the elements.  If any pair of corresponding elements
2880      fail to match, return 0 for the whole things.  */
2881
2882   fmt = GET_RTX_FORMAT (code);
2883   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2884     {
2885       switch (fmt[i])
2886         {
2887         case 'V':
2888         case 'E':
2889           for (j = 0; j < XVECLEN (x, i); j++)
2890             clear_struct_flag (XVECEXP (x, i, j));
2891           break;
2892
2893         case 'e':
2894           clear_struct_flag (XEXP (x, i));
2895           break;
2896         }
2897     }
2898 }
2899
2900 /* Create table entries for DEFINE_ATTR.  */
2901
2902 static void
2903 gen_attr (rtx exp, int lineno)
2904 {
2905   struct attr_desc *attr;
2906   struct attr_value *av;
2907   const char *name_ptr;
2908   char *p;
2909
2910   /* Make a new attribute structure.  Check for duplicate by looking at
2911      attr->default_val, since it is initialized by this routine.  */
2912   attr = find_attr (&XSTR (exp, 0), 1);
2913   if (attr->default_val)
2914     {
2915       message_with_line (lineno, "duplicate definition for attribute %s",
2916                          attr->name);
2917       message_with_line (attr->lineno, "previous definition");
2918       have_error = 1;
2919       return;
2920     }
2921   attr->lineno = lineno;
2922
2923   if (*XSTR (exp, 1) == '\0')
2924     attr->is_numeric = 1;
2925   else
2926     {
2927       name_ptr = XSTR (exp, 1);
2928       while ((p = next_comma_elt (&name_ptr)) != NULL)
2929         {
2930           av = oballoc (sizeof (struct attr_value));
2931           av->value = attr_rtx (CONST_STRING, p);
2932           av->next = attr->first_value;
2933           attr->first_value = av;
2934           av->first_insn = NULL;
2935           av->num_insns = 0;
2936           av->has_asm_insn = 0;
2937         }
2938     }
2939
2940   if (GET_CODE (XEXP (exp, 2)) == CONST)
2941     {
2942       attr->is_const = 1;
2943       if (attr->is_numeric)
2944         {
2945           message_with_line (lineno,
2946                              "constant attributes may not take numeric values");
2947           have_error = 1;
2948         }
2949
2950       /* Get rid of the CONST node.  It is allowed only at top-level.  */
2951       XEXP (exp, 2) = XEXP (XEXP (exp, 2), 0);
2952     }
2953
2954   if (! strcmp_check (attr->name, length_str) && ! attr->is_numeric)
2955     {
2956       message_with_line (lineno,
2957                          "`length' attribute must take numeric values");
2958       have_error = 1;
2959     }
2960
2961   /* Set up the default value.  */
2962   XEXP (exp, 2) = check_attr_value (XEXP (exp, 2), attr);
2963   attr->default_val = get_attr_value (XEXP (exp, 2), attr, -2);
2964 }
2965
2966 /* Given a pattern for DEFINE_PEEPHOLE or DEFINE_INSN, return the number of
2967    alternatives in the constraints.  Assume all MATCH_OPERANDs have the same
2968    number of alternatives as this should be checked elsewhere.  */
2969
2970 static int
2971 count_alternatives (rtx exp)
2972 {
2973   int i, j, n;
2974   const char *fmt;
2975
2976   if (GET_CODE (exp) == MATCH_OPERAND)
2977     return n_comma_elts (XSTR (exp, 2));
2978
2979   for (i = 0, fmt = GET_RTX_FORMAT (GET_CODE (exp));
2980        i < GET_RTX_LENGTH (GET_CODE (exp)); i++)
2981     switch (*fmt++)
2982       {
2983       case 'e':
2984       case 'u':
2985         n = count_alternatives (XEXP (exp, i));
2986         if (n)
2987           return n;
2988         break;
2989
2990       case 'E':
2991       case 'V':
2992         if (XVEC (exp, i) != NULL)
2993           for (j = 0; j < XVECLEN (exp, i); j++)
2994             {
2995               n = count_alternatives (XVECEXP (exp, i, j));
2996               if (n)
2997                 return n;
2998             }
2999       }
3000
3001   return 0;
3002 }
3003
3004 /* Returns nonzero if the given expression contains an EQ_ATTR with the
3005    `alternative' attribute.  */
3006
3007 static int
3008 compares_alternatives_p (rtx exp)
3009 {
3010   int i, j;
3011   const char *fmt;
3012
3013   if (GET_CODE (exp) == EQ_ATTR && XSTR (exp, 0) == alternative_name)
3014     return 1;
3015
3016   for (i = 0, fmt = GET_RTX_FORMAT (GET_CODE (exp));
3017        i < GET_RTX_LENGTH (GET_CODE (exp)); i++)
3018     switch (*fmt++)
3019       {
3020       case 'e':
3021       case 'u':
3022         if (compares_alternatives_p (XEXP (exp, i)))
3023           return 1;
3024         break;
3025
3026       case 'E':
3027         for (j = 0; j < XVECLEN (exp, i); j++)
3028           if (compares_alternatives_p (XVECEXP (exp, i, j)))
3029             return 1;
3030         break;
3031       }
3032
3033   return 0;
3034 }
3035
3036 /* Returns nonzero is INNER is contained in EXP.  */
3037
3038 static int
3039 contained_in_p (rtx inner, rtx exp)
3040 {
3041   int i, j;
3042   const char *fmt;
3043
3044   if (rtx_equal_p (inner, exp))
3045     return 1;
3046
3047   for (i = 0, fmt = GET_RTX_FORMAT (GET_CODE (exp));
3048        i < GET_RTX_LENGTH (GET_CODE (exp)); i++)
3049     switch (*fmt++)
3050       {
3051       case 'e':
3052       case 'u':
3053         if (contained_in_p (inner, XEXP (exp, i)))
3054           return 1;
3055         break;
3056
3057       case 'E':
3058         for (j = 0; j < XVECLEN (exp, i); j++)
3059           if (contained_in_p (inner, XVECEXP (exp, i, j)))
3060             return 1;
3061         break;
3062       }
3063
3064   return 0;
3065 }
3066
3067 /* Process DEFINE_PEEPHOLE, DEFINE_INSN, and DEFINE_ASM_ATTRIBUTES.  */
3068
3069 static void
3070 gen_insn (rtx exp, int lineno)
3071 {
3072   struct insn_def *id;
3073
3074   id = oballoc (sizeof (struct insn_def));
3075   id->next = defs;
3076   defs = id;
3077   id->def = exp;
3078   id->lineno = lineno;
3079
3080   switch (GET_CODE (exp))
3081     {
3082     case DEFINE_INSN:
3083       id->insn_code = insn_code_number;
3084       id->insn_index = insn_index_number;
3085       id->num_alternatives = count_alternatives (exp);
3086       if (id->num_alternatives == 0)
3087         id->num_alternatives = 1;
3088       id->vec_idx = 4;
3089       break;
3090
3091     case DEFINE_PEEPHOLE:
3092       id->insn_code = insn_code_number;
3093       id->insn_index = insn_index_number;
3094       id->num_alternatives = count_alternatives (exp);
3095       if (id->num_alternatives == 0)
3096         id->num_alternatives = 1;
3097       id->vec_idx = 3;
3098       break;
3099
3100     case DEFINE_ASM_ATTRIBUTES:
3101       id->insn_code = -1;
3102       id->insn_index = -1;
3103       id->num_alternatives = 1;
3104       id->vec_idx = 0;
3105       got_define_asm_attributes = 1;
3106       break;
3107
3108     default:
3109       gcc_unreachable ();
3110     }
3111 }
3112
3113 /* Process a DEFINE_DELAY.  Validate the vector length, check if annul
3114    true or annul false is specified, and make a `struct delay_desc'.  */
3115
3116 static void
3117 gen_delay (rtx def, int lineno)
3118 {
3119   struct delay_desc *delay;
3120   int i;
3121
3122   if (XVECLEN (def, 1) % 3 != 0)
3123     {
3124       message_with_line (lineno,
3125                          "number of elements in DEFINE_DELAY must be multiple of three");
3126       have_error = 1;
3127       return;
3128     }
3129
3130   for (i = 0; i < XVECLEN (def, 1); i += 3)
3131     {
3132       if (XVECEXP (def, 1, i + 1))
3133         have_annul_true = 1;
3134       if (XVECEXP (def, 1, i + 2))
3135         have_annul_false = 1;
3136     }
3137
3138   delay = oballoc (sizeof (struct delay_desc));
3139   delay->def = def;
3140   delay->num = ++num_delays;
3141   delay->next = delays;
3142   delay->lineno = lineno;
3143   delays = delay;
3144 }
3145
3146 /* Given a piece of RTX, print a C expression to test its truth value.
3147    We use AND and IOR both for logical and bit-wise operations, so
3148    interpret them as logical unless they are inside a comparison expression.
3149    The first bit of FLAGS will be nonzero in that case.
3150
3151    Set the second bit of FLAGS to make references to attribute values use
3152    a cached local variable instead of calling a function.  */
3153
3154 static void
3155 write_test_expr (rtx exp, int flags)
3156 {
3157   int comparison_operator = 0;
3158   RTX_CODE code;
3159   struct attr_desc *attr;
3160
3161   /* In order not to worry about operator precedence, surround our part of
3162      the expression with parentheses.  */
3163
3164   printf ("(");
3165   code = GET_CODE (exp);
3166   switch (code)
3167     {
3168     /* Binary operators.  */
3169     case GEU: case GTU:
3170     case LEU: case LTU:
3171       printf ("(unsigned) ");
3172       /* Fall through.  */
3173
3174     case EQ: case NE:
3175     case GE: case GT:
3176     case LE: case LT:
3177       comparison_operator = 1;
3178
3179     case PLUS:   case MINUS:  case MULT:     case DIV:      case MOD:
3180     case AND:    case IOR:    case XOR:
3181     case ASHIFT: case LSHIFTRT: case ASHIFTRT:
3182       write_test_expr (XEXP (exp, 0), flags | comparison_operator);
3183       switch (code)
3184         {
3185         case EQ:
3186           printf (" == ");
3187           break;
3188         case NE:
3189           printf (" != ");
3190           break;
3191         case GE:
3192           printf (" >= ");
3193           break;
3194         case GT:
3195           printf (" > ");
3196           break;
3197         case GEU:
3198           printf (" >= (unsigned) ");
3199           break;
3200         case GTU:
3201           printf (" > (unsigned) ");
3202           break;
3203         case LE:
3204           printf (" <= ");
3205           break;
3206         case LT:
3207           printf (" < ");
3208           break;
3209         case LEU:
3210           printf (" <= (unsigned) ");
3211           break;
3212         case LTU:
3213           printf (" < (unsigned) ");
3214           break;
3215         case PLUS:
3216           printf (" + ");
3217           break;
3218         case MINUS:
3219           printf (" - ");
3220           break;
3221         case MULT:
3222           printf (" * ");
3223           break;
3224         case DIV:
3225           printf (" / ");
3226           break;
3227         case MOD:
3228           printf (" %% ");
3229           break;
3230         case AND:
3231           if (flags & 1)
3232             printf (" & ");
3233           else
3234             printf (" && ");
3235           break;
3236         case IOR:
3237           if (flags & 1)
3238             printf (" | ");
3239           else
3240             printf (" || ");
3241           break;
3242         case XOR:
3243           printf (" ^ ");
3244           break;
3245         case ASHIFT:
3246           printf (" << ");
3247           break;
3248         case LSHIFTRT:
3249         case ASHIFTRT:
3250           printf (" >> ");
3251           break;
3252         default:
3253           gcc_unreachable ();
3254         }
3255
3256       write_test_expr (XEXP (exp, 1), flags | comparison_operator);
3257       break;
3258
3259     case NOT:
3260       /* Special-case (not (eq_attrq "alternative" "x")) */
3261       if (! (flags & 1) && GET_CODE (XEXP (exp, 0)) == EQ_ATTR
3262           && XSTR (XEXP (exp, 0), 0) == alternative_name)
3263         {
3264           printf ("which_alternative != %s", XSTR (XEXP (exp, 0), 1));
3265           break;
3266         }
3267
3268       /* Otherwise, fall through to normal unary operator.  */
3269
3270     /* Unary operators.  */
3271     case ABS:  case NEG:
3272       switch (code)
3273         {
3274         case NOT:
3275           if (flags & 1)
3276             printf ("~ ");
3277           else
3278             printf ("! ");
3279           break;
3280         case ABS:
3281           printf ("abs ");
3282           break;
3283         case NEG:
3284           printf ("-");
3285           break;
3286         default:
3287           gcc_unreachable ();
3288         }
3289
3290       write_test_expr (XEXP (exp, 0), flags);
3291       break;
3292
3293     case EQ_ATTR_ALT:
3294         {
3295           int set = XINT (exp, 0), bit = 0;
3296
3297           if (flags & 1)
3298             fatal ("EQ_ATTR_ALT not valid inside comparison");
3299
3300           if (!set)
3301             fatal ("Empty EQ_ATTR_ALT should be optimized out");
3302
3303           if (!(set & (set - 1)))
3304             {
3305               if (!(set & 0xffff))
3306                 {
3307                   bit += 16;
3308                   set >>= 16;
3309                 }
3310               if (!(set & 0xff))
3311                 {
3312                   bit += 8;
3313                   set >>= 8;
3314                 }
3315               if (!(set & 0xf))
3316                 {
3317                   bit += 4;
3318                   set >>= 4;
3319                 }
3320               if (!(set & 0x3))
3321                 {
3322                   bit += 2;
3323                   set >>= 2;
3324                 }
3325               if (!(set & 1))
3326                 bit++;
3327
3328               printf ("which_alternative %s= %d",
3329                       XINT (exp, 1) ? "!" : "=", bit);
3330             }
3331           else
3332             {
3333               printf ("%s((1 << which_alternative) & 0x%x)",
3334                       XINT (exp, 1) ? "!" : "", set);
3335             }
3336         }
3337       break;
3338
3339     /* Comparison test of an attribute with a value.  Most of these will
3340        have been removed by optimization.   Handle "alternative"
3341        specially and give error if EQ_ATTR present inside a comparison.  */
3342     case EQ_ATTR:
3343       if (flags & 1)
3344         fatal ("EQ_ATTR not valid inside comparison");
3345
3346       if (XSTR (exp, 0) == alternative_name)
3347         {
3348           printf ("which_alternative == %s", XSTR (exp, 1));
3349           break;
3350         }
3351
3352       attr = find_attr (&XSTR (exp, 0), 0);
3353       gcc_assert (attr);
3354
3355       /* Now is the time to expand the value of a constant attribute.  */
3356       if (attr->is_const)
3357         {
3358           write_test_expr (evaluate_eq_attr (exp, attr->default_val->value,
3359                                              -2, -2),
3360                            flags);
3361         }
3362       else
3363         {
3364           if (flags & 2)
3365             printf ("attr_%s", attr->name);
3366           else
3367             printf ("get_attr_%s (insn)", attr->name);
3368           printf (" == ");
3369           write_attr_valueq (attr, XSTR (exp, 1));
3370         }
3371       break;
3372
3373     /* Comparison test of flags for define_delays.  */
3374     case ATTR_FLAG:
3375       if (flags & 1)
3376         fatal ("ATTR_FLAG not valid inside comparison");
3377       printf ("(flags & ATTR_FLAG_%s) != 0", XSTR (exp, 0));
3378       break;
3379
3380     /* See if an operand matches a predicate.  */
3381     case MATCH_OPERAND:
3382       /* If only a mode is given, just ensure the mode matches the operand.
3383          If neither a mode nor predicate is given, error.  */
3384       if (XSTR (exp, 1) == NULL || *XSTR (exp, 1) == '\0')
3385         {
3386           if (GET_MODE (exp) == VOIDmode)
3387             fatal ("null MATCH_OPERAND specified as test");
3388           else
3389             printf ("GET_MODE (operands[%d]) == %smode",
3390                     XINT (exp, 0), GET_MODE_NAME (GET_MODE (exp)));
3391         }
3392       else
3393         printf ("%s (operands[%d], %smode)",
3394                 XSTR (exp, 1), XINT (exp, 0), GET_MODE_NAME (GET_MODE (exp)));
3395       break;
3396
3397     /* Constant integer.  */
3398     case CONST_INT:
3399       printf (HOST_WIDE_INT_PRINT_DEC, XWINT (exp, 0));
3400       break;
3401
3402     /* A random C expression.  */
3403     case SYMBOL_REF:
3404       print_c_condition (XSTR (exp, 0));
3405       break;
3406
3407     /* The address of the branch target.  */
3408     case MATCH_DUP:
3409       printf ("INSN_ADDRESSES_SET_P () ? INSN_ADDRESSES (INSN_UID (GET_CODE (operands[%d]) == LABEL_REF ? XEXP (operands[%d], 0) : operands[%d])) : 0",
3410               XINT (exp, 0), XINT (exp, 0), XINT (exp, 0));
3411       break;
3412
3413     case PC:
3414       /* The address of the current insn.  We implement this actually as the
3415          address of the current insn for backward branches, but the last
3416          address of the next insn for forward branches, and both with
3417          adjustments that account for the worst-case possible stretching of
3418          intervening alignments between this insn and its destination.  */
3419       printf ("insn_current_reference_address (insn)");
3420       break;
3421
3422     case CONST_STRING:
3423       printf ("%s", XSTR (exp, 0));
3424       break;
3425
3426     case IF_THEN_ELSE:
3427       write_test_expr (XEXP (exp, 0), flags & 2);
3428       printf (" ? ");
3429       write_test_expr (XEXP (exp, 1), flags | 1);
3430       printf (" : ");
3431       write_test_expr (XEXP (exp, 2), flags | 1);
3432       break;
3433
3434     default:
3435       fatal ("bad RTX code `%s' in attribute calculation\n",
3436              GET_RTX_NAME (code));
3437     }
3438
3439   printf (")");
3440 }
3441
3442 /* Given an attribute value, return the maximum CONST_STRING argument
3443    encountered.  Set *UNKNOWNP and return INT_MAX if the value is unknown.  */
3444
3445 static int
3446 max_attr_value (rtx exp, int *unknownp)
3447 {
3448   int current_max;
3449   int i, n;
3450
3451   switch (GET_CODE (exp))
3452     {
3453     case CONST_STRING:
3454       current_max = atoi (XSTR (exp, 0));
3455       break;
3456
3457     case COND:
3458       current_max = max_attr_value (XEXP (exp, 1), unknownp);
3459       for (i = 0; i < XVECLEN (exp, 0); i += 2)
3460         {
3461           n = max_attr_value (XVECEXP (exp, 0, i + 1), unknownp);
3462           if (n > current_max)
3463             current_max = n;
3464         }
3465       break;
3466
3467     case IF_THEN_ELSE:
3468       current_max = max_attr_value (XEXP (exp, 1), unknownp);
3469       n = max_attr_value (XEXP (exp, 2), unknownp);
3470       if (n > current_max)
3471         current_max = n;
3472       break;
3473
3474     default:
3475       *unknownp = 1;
3476       current_max = INT_MAX;
3477       break;
3478     }
3479
3480   return current_max;
3481 }
3482
3483 /* Given an attribute value, return the minimum CONST_STRING argument
3484    encountered.  Set *UNKNOWNP and return 0 if the value is unknown.  */
3485
3486 static int
3487 min_attr_value (rtx exp, int *unknownp)
3488 {
3489   int current_min;
3490   int i, n;
3491
3492   switch (GET_CODE (exp))
3493     {
3494     case CONST_STRING:
3495       current_min = atoi (XSTR (exp, 0));
3496       break;
3497
3498     case COND:
3499       current_min = min_attr_value (XEXP (exp, 1), unknownp);
3500       for (i = 0; i < XVECLEN (exp, 0); i += 2)
3501         {
3502           n = min_attr_value (XVECEXP (exp, 0, i + 1), unknownp);
3503           if (n < current_min)
3504             current_min = n;
3505         }
3506       break;
3507
3508     case IF_THEN_ELSE:
3509       current_min = min_attr_value (XEXP (exp, 1), unknownp);
3510       n = min_attr_value (XEXP (exp, 2), unknownp);
3511       if (n < current_min)
3512         current_min = n;
3513       break;
3514
3515     default:
3516       *unknownp = 1;
3517       current_min = INT_MAX;
3518       break;
3519     }
3520
3521   return current_min;
3522 }
3523
3524 /* Given an attribute value, return the result of ORing together all
3525    CONST_STRING arguments encountered.  Set *UNKNOWNP and return -1
3526    if the numeric value is not known.  */
3527
3528 static int
3529 or_attr_value (rtx exp, int *unknownp)
3530 {
3531   int current_or;
3532   int i;
3533
3534   switch (GET_CODE (exp))
3535     {
3536     case CONST_STRING:
3537       current_or = atoi (XSTR (exp, 0));
3538       break;
3539
3540     case COND:
3541       current_or = or_attr_value (XEXP (exp, 1), unknownp);
3542       for (i = 0; i < XVECLEN (exp, 0); i += 2)
3543         current_or |= or_attr_value (XVECEXP (exp, 0, i + 1), unknownp);
3544       break;
3545
3546     case IF_THEN_ELSE:
3547       current_or = or_attr_value (XEXP (exp, 1), unknownp);
3548       current_or |= or_attr_value (XEXP (exp, 2), unknownp);
3549       break;
3550
3551     default:
3552       *unknownp = 1;
3553       current_or = -1;
3554       break;
3555     }
3556
3557   return current_or;
3558 }
3559
3560 /* Scan an attribute value, possibly a conditional, and record what actions
3561    will be required to do any conditional tests in it.
3562
3563    Specifically, set
3564         `must_extract'    if we need to extract the insn operands
3565         `must_constrain'  if we must compute `which_alternative'
3566         `address_used'    if an address expression was used
3567         `length_used'     if an (eq_attr "length" ...) was used
3568  */
3569
3570 static void
3571 walk_attr_value (rtx exp)
3572 {
3573   int i, j;
3574   const char *fmt;
3575   RTX_CODE code;
3576
3577   if (exp == NULL)
3578     return;
3579
3580   code = GET_CODE (exp);
3581   switch (code)
3582     {
3583     case SYMBOL_REF:
3584       if (! ATTR_IND_SIMPLIFIED_P (exp))
3585         /* Since this is an arbitrary expression, it can look at anything.
3586            However, constant expressions do not depend on any particular
3587            insn.  */
3588         must_extract = must_constrain = 1;
3589       return;
3590
3591     case MATCH_OPERAND:
3592       must_extract = 1;
3593       return;
3594
3595     case EQ_ATTR_ALT:
3596       must_extract = must_constrain = 1;
3597       break;
3598
3599     case EQ_ATTR:
3600       if (XSTR (exp, 0) == alternative_name)
3601         must_extract = must_constrain = 1;
3602       else if (strcmp_check (XSTR (exp, 0), length_str) == 0)
3603         length_used = 1;
3604       return;
3605
3606     case MATCH_DUP:
3607       must_extract = 1;
3608       address_used = 1;
3609       return;
3610
3611     case PC:
3612       address_used = 1;
3613       return;
3614
3615     case ATTR_FLAG:
3616       return;
3617
3618     default:
3619       break;
3620     }
3621
3622   for (i = 0, fmt = GET_RTX_FORMAT (code); i < GET_RTX_LENGTH (code); i++)
3623     switch (*fmt++)
3624       {
3625       case 'e':
3626       case 'u':
3627         walk_attr_value (XEXP (exp, i));
3628         break;
3629
3630       case 'E':
3631         if (XVEC (exp, i) != NULL)
3632           for (j = 0; j < XVECLEN (exp, i); j++)
3633             walk_attr_value (XVECEXP (exp, i, j));
3634         break;
3635       }
3636 }
3637
3638 /* Write out a function to obtain the attribute for a given INSN.  */
3639
3640 static void
3641 write_attr_get (struct attr_desc *attr)
3642 {
3643   struct attr_value *av, *common_av;
3644
3645   /* Find the most used attribute value.  Handle that as the `default' of the
3646      switch we will generate.  */
3647   common_av = find_most_used (attr);
3648
3649   /* Write out start of function, then all values with explicit `case' lines,
3650      then a `default', then the value with the most uses.  */
3651   if (!attr->is_numeric)
3652     printf ("enum attr_%s\n", attr->name);
3653   else
3654     printf ("int\n");
3655
3656   /* If the attribute name starts with a star, the remainder is the name of
3657      the subroutine to use, instead of `get_attr_...'.  */
3658   if (attr->name[0] == '*')
3659     printf ("%s (rtx insn ATTRIBUTE_UNUSED)\n", &attr->name[1]);
3660   else if (attr->is_const == 0)
3661     printf ("get_attr_%s (rtx insn ATTRIBUTE_UNUSED)\n", attr->name);
3662   else
3663     {
3664       printf ("get_attr_%s (void)\n", attr->name);
3665       printf ("{\n");
3666
3667       for (av = attr->first_value; av; av = av->next)
3668         if (av->num_insns == 1)
3669           write_attr_set (attr, 2, av->value, "return", ";",
3670                           true_rtx, av->first_insn->def->insn_code,
3671                           av->first_insn->def->insn_index);
3672         else if (av->num_insns != 0)
3673           write_attr_set (attr, 2, av->value, "return", ";",
3674                           true_rtx, -2, 0);
3675
3676       printf ("}\n\n");
3677       return;
3678     }
3679
3680   printf ("{\n");
3681   printf ("  switch (recog_memoized (insn))\n");
3682   printf ("    {\n");
3683
3684   for (av = attr->first_value; av; av = av->next)
3685     if (av != common_av)
3686       write_attr_case (attr, av, 1, "return", ";", 4, true_rtx);
3687
3688   write_attr_case (attr, common_av, 0, "return", ";", 4, true_rtx);
3689   printf ("    }\n}\n\n");
3690 }
3691
3692 /* Given an AND tree of known true terms (because we are inside an `if' with
3693    that as the condition or are in an `else' clause) and an expression,
3694    replace any known true terms with TRUE.  Use `simplify_and_tree' to do
3695    the bulk of the work.  */
3696
3697 static rtx
3698 eliminate_known_true (rtx known_true, rtx exp, int insn_code, int insn_index)
3699 {
3700   rtx term;
3701
3702   known_true = SIMPLIFY_TEST_EXP (known_true, insn_code, insn_index);
3703
3704   if (GET_CODE (known_true) == AND)
3705     {
3706       exp = eliminate_known_true (XEXP (known_true, 0), exp,
3707                                   insn_code, insn_index);
3708       exp = eliminate_known_true (XEXP (known_true, 1), exp,
3709                                   insn_code, insn_index);
3710     }
3711   else
3712     {
3713       term = known_true;
3714       exp = simplify_and_tree (exp, &term, insn_code, insn_index);
3715     }
3716
3717   return exp;
3718 }
3719
3720 /* Write out a series of tests and assignment statements to perform tests and
3721    sets of an attribute value.  We are passed an indentation amount and prefix
3722    and suffix strings to write around each attribute value (e.g., "return"
3723    and ";").  */
3724
3725 static void
3726 write_attr_set (struct attr_desc *attr, int indent, rtx value,
3727                 const char *prefix, const char *suffix, rtx known_true,
3728                 int insn_code, int insn_index)
3729 {
3730   if (GET_CODE (value) == COND)
3731     {
3732       /* Assume the default value will be the default of the COND unless we
3733          find an always true expression.  */
3734       rtx default_val = XEXP (value, 1);
3735       rtx our_known_true = known_true;
3736       rtx newexp;
3737       int first_if = 1;
3738       int i;
3739
3740       for (i = 0; i < XVECLEN (value, 0); i += 2)
3741         {
3742           rtx testexp;
3743           rtx inner_true;
3744
3745           testexp = eliminate_known_true (our_known_true,
3746                                           XVECEXP (value, 0, i),
3747                                           insn_code, insn_index);
3748           newexp = attr_rtx (NOT, testexp);
3749           newexp = insert_right_side (AND, our_known_true, newexp,
3750                                       insn_code, insn_index);
3751
3752           /* If the test expression is always true or if the next `known_true'
3753              expression is always false, this is the last case, so break
3754              out and let this value be the `else' case.  */
3755           if (testexp == true_rtx || newexp == false_rtx)
3756             {
3757               default_val = XVECEXP (value, 0, i + 1);
3758               break;
3759             }
3760
3761           /* Compute the expression to pass to our recursive call as being
3762              known true.  */
3763           inner_true = insert_right_side (AND, our_known_true,
3764                                           testexp, insn_code, insn_index);
3765
3766           /* If this is always false, skip it.  */
3767           if (inner_true == false_rtx)
3768             continue;
3769
3770           write_indent (indent);
3771           printf ("%sif ", first_if ? "" : "else ");
3772           first_if = 0;
3773           write_test_expr (testexp, 0);
3774           printf ("\n");
3775           write_indent (indent + 2);
3776           printf ("{\n");
3777
3778           write_attr_set (attr, indent + 4,
3779                           XVECEXP (value, 0, i + 1), prefix, suffix,
3780                           inner_true, insn_code, insn_index);
3781           write_indent (indent + 2);
3782           printf ("}\n");
3783           our_known_true = newexp;
3784         }
3785
3786       if (! first_if)
3787         {
3788           write_indent (indent);
3789           printf ("else\n");
3790           write_indent (indent + 2);
3791           printf ("{\n");
3792         }
3793
3794       write_attr_set (attr, first_if ? indent : indent + 4, default_val,
3795                       prefix, suffix, our_known_true, insn_code, insn_index);
3796
3797       if (! first_if)
3798         {
3799           write_indent (indent + 2);
3800           printf ("}\n");
3801         }
3802     }
3803   else
3804     {
3805       write_indent (indent);
3806       printf ("%s ", prefix);
3807       write_attr_value (attr, value);
3808       printf ("%s\n", suffix);
3809     }
3810 }
3811
3812 /* Write a series of case statements for every instruction in list IE.
3813    INDENT is the amount of indentation to write before each case.  */
3814
3815 static void
3816 write_insn_cases (struct insn_ent *ie, int indent)
3817 {
3818   for (; ie != 0; ie = ie->next)
3819     if (ie->def->insn_code != -1)
3820       {
3821         write_indent (indent);
3822         if (GET_CODE (ie->def->def) == DEFINE_PEEPHOLE)
3823           printf ("case %d:  /* define_peephole, line %d */\n",
3824                   ie->def->insn_code, ie->def->lineno);
3825         else
3826           printf ("case %d:  /* %s */\n",
3827                   ie->def->insn_code, XSTR (ie->def->def, 0));
3828       }
3829 }
3830
3831 /* Write out the computation for one attribute value.  */
3832
3833 static void
3834 write_attr_case (struct attr_desc *attr, struct attr_value *av,
3835                  int write_case_lines, const char *prefix, const char *suffix,
3836                  int indent, rtx known_true)
3837 {
3838   if (av->num_insns == 0)
3839     return;
3840
3841   if (av->has_asm_insn)
3842     {
3843       write_indent (indent);
3844       printf ("case -1:\n");
3845       write_indent (indent + 2);
3846       printf ("if (GET_CODE (PATTERN (insn)) != ASM_INPUT\n");
3847       write_indent (indent + 2);
3848       printf ("    && asm_noperands (PATTERN (insn)) < 0)\n");
3849       write_indent (indent + 2);
3850       printf ("  fatal_insn_not_found (insn);\n");
3851     }
3852
3853   if (write_case_lines)
3854     write_insn_cases (av->first_insn, indent);
3855   else
3856     {
3857       write_indent (indent);
3858       printf ("default:\n");
3859     }
3860
3861   /* See what we have to do to output this value.  */
3862   must_extract = must_constrain = address_used = 0;
3863   walk_attr_value (av->value);
3864
3865   if (must_constrain)
3866     {
3867       write_indent (indent + 2);
3868       printf ("extract_constrain_insn_cached (insn);\n");
3869     }
3870   else if (must_extract)
3871     {
3872       write_indent (indent + 2);
3873       printf ("extract_insn_cached (insn);\n");
3874     }
3875
3876   if (av->num_insns == 1)
3877     write_attr_set (attr, indent + 2, av->value, prefix, suffix,
3878                     known_true, av->first_insn->def->insn_code,
3879                     av->first_insn->def->insn_index);
3880   else
3881     write_attr_set (attr, indent + 2, av->value, prefix, suffix,
3882                     known_true, -2, 0);
3883
3884   if (strncmp (prefix, "return", 6))
3885     {
3886       write_indent (indent + 2);
3887       printf ("break;\n");
3888     }
3889   printf ("\n");
3890 }
3891
3892 /* Search for uses of non-const attributes and write code to cache them.  */
3893
3894 static int
3895 write_expr_attr_cache (rtx p, struct attr_desc *attr)
3896 {
3897   const char *fmt;
3898   int i, ie, j, je;
3899
3900   if (GET_CODE (p) == EQ_ATTR)
3901     {
3902       if (XSTR (p, 0) != attr->name)
3903         return 0;
3904
3905       if (!attr->is_numeric)
3906         printf ("  enum attr_%s ", attr->name);
3907       else
3908         printf ("  int ");
3909
3910       printf ("attr_%s = get_attr_%s (insn);\n", attr->name, attr->name);
3911       return 1;
3912     }
3913
3914   fmt = GET_RTX_FORMAT (GET_CODE (p));
3915   ie = GET_RTX_LENGTH (GET_CODE (p));
3916   for (i = 0; i < ie; i++)
3917     {
3918       switch (*fmt++)
3919         {
3920         case 'e':
3921           if (write_expr_attr_cache (XEXP (p, i), attr))
3922             return 1;
3923           break;
3924
3925         case 'E':
3926           je = XVECLEN (p, i);
3927           for (j = 0; j < je; ++j)
3928             if (write_expr_attr_cache (XVECEXP (p, i, j), attr))
3929               return 1;
3930           break;
3931         }
3932     }
3933
3934   return 0;
3935 }
3936
3937 /* Utilities to write in various forms.  */
3938
3939 static void
3940 write_attr_valueq (struct attr_desc *attr, const char *s)
3941 {
3942   if (attr->is_numeric)
3943     {
3944       int num = atoi (s);
3945
3946       printf ("%d", num);
3947
3948       if (num > 9 || num < 0)
3949         printf (" /* 0x%x */", num);
3950     }
3951   else
3952     {
3953       write_upcase (attr->name);
3954       printf ("_");
3955       write_upcase (s);
3956     }
3957 }
3958
3959 static void
3960 write_attr_value (struct attr_desc *attr, rtx value)
3961 {
3962   int op;
3963
3964   switch (GET_CODE (value))
3965     {
3966     case CONST_STRING:
3967       write_attr_valueq (attr, XSTR (value, 0));
3968       break;
3969
3970     case CONST_INT:
3971       printf (HOST_WIDE_INT_PRINT_DEC, INTVAL (value));
3972       break;
3973
3974     case SYMBOL_REF:
3975       print_c_condition (XSTR (value, 0));
3976       break;
3977
3978     case ATTR:
3979       {
3980         struct attr_desc *attr2 = find_attr (&XSTR (value, 0), 0);
3981         printf ("get_attr_%s (%s)", attr2->name,
3982                 (attr2->is_const ? "" : "insn"));
3983       }
3984       break;
3985
3986     case PLUS:
3987       op = '+';
3988       goto do_operator;
3989     case MINUS:
3990       op = '-';
3991       goto do_operator;
3992     case MULT:
3993       op = '*';
3994       goto do_operator;
3995     case DIV:
3996       op = '/';
3997       goto do_operator;
3998     case MOD:
3999       op = '%';
4000       goto do_operator;
4001
4002     do_operator:
4003       write_attr_value (attr, XEXP (value, 0));
4004       putchar (' ');
4005       putchar (op);
4006       putchar (' ');
4007       write_attr_value (attr, XEXP (value, 1));
4008       break;
4009
4010     default:
4011       gcc_unreachable ();
4012     }
4013 }
4014
4015 static void
4016 write_upcase (const char *str)
4017 {
4018   while (*str)
4019     {
4020       /* The argument of TOUPPER should not have side effects.  */
4021       putchar (TOUPPER(*str));
4022       str++;
4023     }
4024 }
4025
4026 static void
4027 write_indent (int indent)
4028 {
4029   for (; indent > 8; indent -= 8)
4030     printf ("\t");
4031
4032   for (; indent; indent--)
4033     printf (" ");
4034 }
4035
4036 /* Write a subroutine that is given an insn that requires a delay slot, a
4037    delay slot ordinal, and a candidate insn.  It returns nonzero if the
4038    candidate can be placed in the specified delay slot of the insn.
4039
4040    We can write as many as three subroutines.  `eligible_for_delay'
4041    handles normal delay slots, `eligible_for_annul_true' indicates that
4042    the specified insn can be annulled if the branch is true, and likewise
4043    for `eligible_for_annul_false'.
4044
4045    KIND is a string distinguishing these three cases ("delay", "annul_true",
4046    or "annul_false").  */
4047
4048 static void
4049 write_eligible_delay (const char *kind)
4050 {
4051   struct delay_desc *delay;
4052   int max_slots;
4053   char str[50];
4054   const char *pstr;
4055   struct attr_desc *attr;
4056   struct attr_value *av, *common_av;
4057   int i;
4058
4059   /* Compute the maximum number of delay slots required.  We use the delay
4060      ordinal times this number plus one, plus the slot number as an index into
4061      the appropriate predicate to test.  */
4062
4063   for (delay = delays, max_slots = 0; delay; delay = delay->next)
4064     if (XVECLEN (delay->def, 1) / 3 > max_slots)
4065       max_slots = XVECLEN (delay->def, 1) / 3;
4066
4067   /* Write function prelude.  */
4068
4069   printf ("int\n");
4070   printf ("eligible_for_%s (rtx delay_insn ATTRIBUTE_UNUSED, int slot, rtx candidate_insn, int flags ATTRIBUTE_UNUSED)\n",
4071           kind);
4072   printf ("{\n");
4073   printf ("  rtx insn;\n");
4074   printf ("\n");
4075   printf ("  gcc_assert (slot < %d);\n", max_slots);
4076   printf ("\n");
4077   /* Allow dbr_schedule to pass labels, etc.  This can happen if try_split
4078      converts a compound instruction into a loop.  */
4079   printf ("  if (!INSN_P (candidate_insn))\n");
4080   printf ("    return 0;\n");
4081   printf ("\n");
4082
4083   /* If more than one delay type, find out which type the delay insn is.  */
4084
4085   if (num_delays > 1)
4086     {
4087       attr = find_attr (&delay_type_str, 0);
4088       gcc_assert (attr);
4089       common_av = find_most_used (attr);
4090
4091       printf ("  insn = delay_insn;\n");
4092       printf ("  switch (recog_memoized (insn))\n");
4093       printf ("    {\n");
4094
4095       sprintf (str, " * %d;\n      break;", max_slots);
4096       for (av = attr->first_value; av; av = av->next)
4097         if (av != common_av)
4098           write_attr_case (attr, av, 1, "slot +=", str, 4, true_rtx);
4099
4100       write_attr_case (attr, common_av, 0, "slot +=", str, 4, true_rtx);
4101       printf ("    }\n\n");
4102
4103       /* Ensure matched.  Otherwise, shouldn't have been called.  */
4104       printf ("  gcc_assert (slot >= %d);\n\n", max_slots);
4105     }
4106
4107   /* If just one type of delay slot, write simple switch.  */
4108   if (num_delays == 1 && max_slots == 1)
4109     {
4110       printf ("  insn = candidate_insn;\n");
4111       printf ("  switch (recog_memoized (insn))\n");
4112       printf ("    {\n");
4113
4114       attr = find_attr (&delay_1_0_str, 0);
4115       gcc_assert (attr);
4116       common_av = find_most_used (attr);
4117
4118       for (av = attr->first_value; av; av = av->next)
4119         if (av != common_av)
4120           write_attr_case (attr, av, 1, "return", ";", 4, true_rtx);
4121
4122       write_attr_case (attr, common_av, 0, "return", ";", 4, true_rtx);
4123       printf ("    }\n");
4124     }
4125
4126   else
4127     {
4128       /* Write a nested CASE.  The first indicates which condition we need to
4129          test, and the inner CASE tests the condition.  */
4130       printf ("  insn = candidate_insn;\n");
4131       printf ("  switch (slot)\n");
4132       printf ("    {\n");
4133
4134       for (delay = delays; delay; delay = delay->next)
4135         for (i = 0; i < XVECLEN (delay->def, 1); i += 3)
4136           {
4137             printf ("    case %d:\n",
4138                     (i / 3) + (num_delays == 1 ? 0 : delay->num * max_slots));
4139             printf ("      switch (recog_memoized (insn))\n");
4140             printf ("\t{\n");
4141
4142             sprintf (str, "*%s_%d_%d", kind, delay->num, i / 3);
4143             pstr = str;
4144             attr = find_attr (&pstr, 0);
4145             gcc_assert (attr);
4146             common_av = find_most_used (attr);
4147
4148             for (av = attr->first_value; av; av = av->next)
4149               if (av != common_av)
4150                 write_attr_case (attr, av, 1, "return", ";", 8, true_rtx);
4151
4152             write_attr_case (attr, common_av, 0, "return", ";", 8, true_rtx);
4153             printf ("      }\n");
4154           }
4155
4156       printf ("    default:\n");
4157       printf ("      gcc_unreachable ();\n");
4158       printf ("    }\n");
4159     }
4160
4161   printf ("}\n\n");
4162 }
4163
4164 /* This page contains miscellaneous utility routines.  */
4165
4166 /* Given a pointer to a (char *), return a malloc'ed string containing the
4167    next comma-separated element.  Advance the pointer to after the string
4168    scanned, or the end-of-string.  Return NULL if at end of string.  */
4169
4170 static char *
4171 next_comma_elt (const char **pstr)
4172 {
4173   const char *start;
4174
4175   start = scan_comma_elt (pstr);
4176
4177   if (start == NULL)
4178     return NULL;
4179
4180   return attr_string (start, *pstr - start);
4181 }
4182
4183 /* Return a `struct attr_desc' pointer for a given named attribute.  If CREATE
4184    is nonzero, build a new attribute, if one does not exist.  *NAME_P is
4185    replaced by a pointer to a canonical copy of the string.  */
4186
4187 static struct attr_desc *
4188 find_attr (const char **name_p, int create)
4189 {
4190   struct attr_desc *attr;
4191   int index;
4192   const char *name = *name_p;
4193
4194   /* Before we resort to using `strcmp', see if the string address matches
4195      anywhere.  In most cases, it should have been canonicalized to do so.  */
4196   if (name == alternative_name)
4197     return NULL;
4198
4199   index = name[0] & (MAX_ATTRS_INDEX - 1);
4200   for (attr = attrs[index]; attr; attr = attr->next)
4201     if (name == attr->name)
4202       return attr;
4203
4204   /* Otherwise, do it the slow way.  */
4205   for (attr = attrs[index]; attr; attr = attr->next)
4206     if (name[0] == attr->name[0] && ! strcmp (name, attr->name))
4207       {
4208         *name_p = attr->name;
4209         return attr;
4210       }
4211
4212   if (! create)
4213     return NULL;
4214
4215   attr = oballoc (sizeof (struct attr_desc));
4216   attr->name = DEF_ATTR_STRING (name);
4217   attr->first_value = attr->default_val = NULL;
4218   attr->is_numeric = attr->is_const = attr->is_special = 0;
4219   attr->next = attrs[index];
4220   attrs[index] = attr;
4221
4222   *name_p = attr->name;
4223
4224   return attr;
4225 }
4226
4227 /* Create internal attribute with the given default value.  */
4228
4229 static void
4230 make_internal_attr (const char *name, rtx value, int special)
4231 {
4232   struct attr_desc *attr;
4233
4234   attr = find_attr (&name, 1);
4235   gcc_assert (!attr->default_val);
4236
4237   attr->is_numeric = 1;
4238   attr->is_const = 0;
4239   attr->is_special = (special & ATTR_SPECIAL) != 0;
4240   attr->default_val = get_attr_value (value, attr, -2);
4241 }
4242
4243 /* Find the most used value of an attribute.  */
4244
4245 static struct attr_value *
4246 find_most_used (struct attr_desc *attr)
4247 {
4248   struct attr_value *av;
4249   struct attr_value *most_used;
4250   int nuses;
4251
4252   most_used = NULL;
4253   nuses = -1;
4254
4255   for (av = attr->first_value; av; av = av->next)
4256     if (av->num_insns > nuses)
4257       nuses = av->num_insns, most_used = av;
4258
4259   return most_used;
4260 }
4261
4262 /* Return (attr_value "n") */
4263
4264 static rtx
4265 make_numeric_value (int n)
4266 {
4267   static rtx int_values[20];
4268   rtx exp;
4269   char *p;
4270
4271   gcc_assert (n >= 0);
4272
4273   if (n < 20 && int_values[n])
4274     return int_values[n];
4275
4276   p = attr_printf (MAX_DIGITS, "%d", n);
4277   exp = attr_rtx (CONST_STRING, p);
4278
4279   if (n < 20)
4280     int_values[n] = exp;
4281
4282   return exp;
4283 }
4284
4285 static rtx
4286 copy_rtx_unchanging (rtx orig)
4287 {
4288   if (ATTR_IND_SIMPLIFIED_P (orig) || ATTR_CURR_SIMPLIFIED_P (orig))
4289     return orig;
4290
4291   ATTR_CURR_SIMPLIFIED_P (orig) = 1;
4292   return orig;
4293 }
4294
4295 /* Determine if an insn has a constant number of delay slots, i.e., the
4296    number of delay slots is not a function of the length of the insn.  */
4297
4298 static void
4299 write_const_num_delay_slots (void)
4300 {
4301   struct attr_desc *attr = find_attr (&num_delay_slots_str, 0);
4302   struct attr_value *av;
4303
4304   if (attr)
4305     {
4306       printf ("int\nconst_num_delay_slots (rtx insn)\n");
4307       printf ("{\n");
4308       printf ("  switch (recog_memoized (insn))\n");
4309       printf ("    {\n");
4310
4311       for (av = attr->first_value; av; av = av->next)
4312         {
4313           length_used = 0;
4314           walk_attr_value (av->value);
4315           if (length_used)
4316             write_insn_cases (av->first_insn, 4);
4317         }
4318
4319       printf ("    default:\n");
4320       printf ("      return 1;\n");
4321       printf ("    }\n}\n\n");
4322     }
4323 }
4324 \f
4325 /* Synthetic attributes used by insn-automata.c and the scheduler.
4326    These are primarily concerned with (define_insn_reservation)
4327    patterns.  */
4328
4329 struct insn_reserv
4330 {
4331   struct insn_reserv *next;
4332
4333   const char *name;
4334   int default_latency;
4335   rtx condexp;
4336
4337   /* Sequence number of this insn.  */
4338   int insn_num;
4339
4340   /* Whether a (define_bypass) construct names this insn in its
4341      output list.  */
4342   bool bypassed;
4343 };
4344
4345 static struct insn_reserv *all_insn_reservs = 0;
4346 static struct insn_reserv **last_insn_reserv_p = &all_insn_reservs;
4347 static size_t n_insn_reservs;
4348
4349 /* Store information from a DEFINE_INSN_RESERVATION for future
4350    attribute generation.  */
4351 static void
4352 gen_insn_reserv (rtx def)
4353 {
4354   struct insn_reserv *decl = oballoc (sizeof (struct insn_reserv));
4355
4356   decl->name            = DEF_ATTR_STRING (XSTR (def, 0));
4357   decl->default_latency = XINT (def, 1);
4358   decl->condexp         = check_attr_test (XEXP (def, 2), 0, 0);
4359   decl->insn_num        = n_insn_reservs;
4360   decl->bypassed        = false;
4361   decl->next            = 0;
4362
4363   *last_insn_reserv_p = decl;
4364   last_insn_reserv_p  = &decl->next;
4365   n_insn_reservs++;
4366 }
4367
4368 /* Store information from a DEFINE_BYPASS for future attribute
4369    generation.  The only thing we care about is the list of output
4370    insns, which will later be used to tag reservation structures with
4371    a 'bypassed' bit.  */
4372
4373 struct bypass_list
4374 {
4375   struct bypass_list *next;
4376   const char *insn;
4377 };
4378
4379 static struct bypass_list *all_bypasses;
4380 static size_t n_bypasses;
4381
4382 static void
4383 gen_bypass_1 (const char *s, size_t len)
4384 {
4385   struct bypass_list *b;
4386
4387   if (len == 0)
4388     return;
4389
4390   s = attr_string (s, len);
4391   for (b = all_bypasses; b; b = b->next)
4392     if (s == b->insn)
4393       return;  /* already got that one */
4394
4395   b = oballoc (sizeof (struct bypass_list));
4396   b->insn = s;
4397   b->next = all_bypasses;
4398   all_bypasses = b;
4399   n_bypasses++;
4400 }
4401
4402 static void
4403 gen_bypass (rtx def)
4404 {
4405   const char *p, *base;
4406
4407   for (p = base = XSTR (def, 1); *p; p++)
4408     if (*p == ',')
4409       {
4410         gen_bypass_1 (base, p - base);
4411         do
4412           p++;
4413         while (ISSPACE (*p));
4414         base = p;
4415       }
4416   gen_bypass_1 (base, p - base);
4417 }
4418
4419 /* Find and mark all of the bypassed insns.  */
4420 static void
4421 process_bypasses (void)
4422 {
4423   struct bypass_list *b;
4424   struct insn_reserv *r;
4425
4426   /* The reservation list is likely to be much longer than the bypass
4427      list.  */
4428   for (r = all_insn_reservs; r; r = r->next)
4429     for (b = all_bypasses; b; b = b->next)
4430       if (r->name == b->insn)
4431         r->bypassed = true;
4432 }
4433
4434 /* Create all of the attributes that describe automaton properties.  */
4435 static void
4436 make_automaton_attrs (void)
4437 {
4438   int i;
4439   struct insn_reserv *decl;
4440   rtx code_exp, lats_exp, byps_exp;
4441
4442   if (n_insn_reservs == 0)
4443     return;
4444
4445   code_exp = rtx_alloc (COND);
4446   lats_exp = rtx_alloc (COND);
4447
4448   XVEC (code_exp, 0) = rtvec_alloc (n_insn_reservs * 2);
4449   XVEC (lats_exp, 0) = rtvec_alloc (n_insn_reservs * 2);
4450
4451   XEXP (code_exp, 1) = make_numeric_value (n_insn_reservs + 1);
4452   XEXP (lats_exp, 1) = make_numeric_value (0);
4453
4454   for (decl = all_insn_reservs, i = 0;
4455        decl;
4456        decl = decl->next, i += 2)
4457     {
4458       XVECEXP (code_exp, 0, i)   = decl->condexp;
4459       XVECEXP (lats_exp, 0, i)   = decl->condexp;
4460
4461       XVECEXP (code_exp, 0, i+1) = make_numeric_value (decl->insn_num);
4462       XVECEXP (lats_exp, 0, i+1) = make_numeric_value (decl->default_latency);
4463     }
4464
4465   if (n_bypasses == 0)
4466     byps_exp = make_numeric_value (0);
4467   else
4468     {
4469       process_bypasses ();
4470
4471       byps_exp = rtx_alloc (COND);
4472       XVEC (byps_exp, 0) = rtvec_alloc (n_bypasses * 2);
4473       XEXP (byps_exp, 1) = make_numeric_value (0);
4474       for (decl = all_insn_reservs, i = 0;
4475            decl;
4476            decl = decl->next)
4477         if (decl->bypassed)
4478           {
4479             XVECEXP (byps_exp, 0, i)   = decl->condexp;
4480             XVECEXP (byps_exp, 0, i+1) = make_numeric_value (1);
4481             i += 2;
4482           }
4483     }
4484
4485   make_internal_attr ("*internal_dfa_insn_code", code_exp, ATTR_NONE);
4486   make_internal_attr ("*insn_default_latency",   lats_exp, ATTR_NONE);
4487   make_internal_attr ("*bypass_p",               byps_exp, ATTR_NONE);
4488 }
4489
4490 int
4491 main (int argc, char **argv)
4492 {
4493   rtx desc;
4494   struct attr_desc *attr;
4495   struct insn_def *id;
4496   rtx tem;
4497   int i;
4498
4499   progname = "genattrtab";
4500
4501   if (init_md_reader_args (argc, argv) != SUCCESS_EXIT_CODE)
4502     return (FATAL_EXIT_CODE);
4503
4504   obstack_init (hash_obstack);
4505   obstack_init (temp_obstack);
4506
4507   /* Set up true and false rtx's */
4508   true_rtx = rtx_alloc (CONST_INT);
4509   XWINT (true_rtx, 0) = 1;
4510   false_rtx = rtx_alloc (CONST_INT);
4511   XWINT (false_rtx, 0) = 0;
4512   ATTR_IND_SIMPLIFIED_P (true_rtx) = ATTR_IND_SIMPLIFIED_P (false_rtx) = 1;
4513   ATTR_PERMANENT_P (true_rtx) = ATTR_PERMANENT_P (false_rtx) = 1;
4514
4515   alternative_name = DEF_ATTR_STRING ("alternative");
4516   length_str = DEF_ATTR_STRING ("length");
4517   delay_type_str = DEF_ATTR_STRING ("*delay_type");
4518   delay_1_0_str = DEF_ATTR_STRING ("*delay_1_0");
4519   num_delay_slots_str = DEF_ATTR_STRING ("*num_delay_slots");
4520
4521   printf ("/* Generated automatically by the program `genattrtab'\n\
4522 from the machine description file `md'.  */\n\n");
4523
4524   /* Read the machine description.  */
4525
4526   while (1)
4527     {
4528       int lineno;
4529
4530       desc = read_md_rtx (&lineno, &insn_code_number);
4531       if (desc == NULL)
4532         break;
4533
4534       switch (GET_CODE (desc))
4535         {
4536         case DEFINE_INSN:
4537         case DEFINE_PEEPHOLE:
4538         case DEFINE_ASM_ATTRIBUTES:
4539           gen_insn (desc, lineno);
4540           break;
4541
4542         case DEFINE_ATTR:
4543           gen_attr (desc, lineno);
4544           break;
4545
4546         case DEFINE_DELAY:
4547           gen_delay (desc, lineno);
4548           break;
4549
4550         case DEFINE_INSN_RESERVATION:
4551           gen_insn_reserv (desc);
4552           break;
4553
4554         case DEFINE_BYPASS:
4555           gen_bypass (desc);
4556           break;
4557
4558         default:
4559           break;
4560         }
4561       if (GET_CODE (desc) != DEFINE_ASM_ATTRIBUTES)
4562         insn_index_number++;
4563     }
4564
4565   if (have_error)
4566     return FATAL_EXIT_CODE;
4567
4568   insn_code_number++;
4569
4570   /* If we didn't have a DEFINE_ASM_ATTRIBUTES, make a null one.  */
4571   if (! got_define_asm_attributes)
4572     {
4573       tem = rtx_alloc (DEFINE_ASM_ATTRIBUTES);
4574       XVEC (tem, 0) = rtvec_alloc (0);
4575       gen_insn (tem, 0);
4576     }
4577
4578   /* Expand DEFINE_DELAY information into new attribute.  */
4579   if (num_delays)
4580     expand_delays ();
4581
4582   printf ("#include \"config.h\"\n");
4583   printf ("#include \"system.h\"\n");
4584   printf ("#include \"coretypes.h\"\n");
4585   printf ("#include \"tm.h\"\n");
4586   printf ("#include \"rtl.h\"\n");
4587   printf ("#include \"tm_p.h\"\n");
4588   printf ("#include \"insn-config.h\"\n");
4589   printf ("#include \"recog.h\"\n");
4590   printf ("#include \"regs.h\"\n");
4591   printf ("#include \"real.h\"\n");
4592   printf ("#include \"output.h\"\n");
4593   printf ("#include \"insn-attr.h\"\n");
4594   printf ("#include \"toplev.h\"\n");
4595   printf ("#include \"flags.h\"\n");
4596   printf ("#include \"function.h\"\n");
4597   printf ("\n");
4598   printf ("#define operands recog_data.operand\n\n");
4599
4600   /* Make `insn_alternatives'.  */
4601   insn_alternatives = oballoc (insn_code_number * sizeof (int));
4602   for (id = defs; id; id = id->next)
4603     if (id->insn_code >= 0)
4604       insn_alternatives[id->insn_code] = (1 << id->num_alternatives) - 1;
4605
4606   /* Make `insn_n_alternatives'.  */
4607   insn_n_alternatives = oballoc (insn_code_number * sizeof (int));
4608   for (id = defs; id; id = id->next)
4609     if (id->insn_code >= 0)
4610       insn_n_alternatives[id->insn_code] = id->num_alternatives;
4611
4612   /* Construct extra attributes for automata.  */
4613   make_automaton_attrs ();
4614
4615   /* Prepare to write out attribute subroutines by checking everything stored
4616      away and building the attribute cases.  */
4617
4618   check_defs ();
4619
4620   for (i = 0; i < MAX_ATTRS_INDEX; i++)
4621     for (attr = attrs[i]; attr; attr = attr->next)
4622       attr->default_val->value
4623         = check_attr_value (attr->default_val->value, attr);
4624
4625   if (have_error)
4626     return FATAL_EXIT_CODE;
4627
4628   for (i = 0; i < MAX_ATTRS_INDEX; i++)
4629     for (attr = attrs[i]; attr; attr = attr->next)
4630       fill_attr (attr);
4631
4632   /* Construct extra attributes for `length'.  */
4633   make_length_attrs ();
4634
4635   /* Perform any possible optimizations to speed up compilation.  */
4636   optimize_attrs ();
4637
4638   /* Now write out all the `gen_attr_...' routines.  Do these before the
4639      special routines so that they get defined before they are used.  */
4640
4641   for (i = 0; i < MAX_ATTRS_INDEX; i++)
4642     for (attr = attrs[i]; attr; attr = attr->next)
4643       {
4644         if (! attr->is_special && ! attr->is_const)
4645           write_attr_get (attr);
4646       }
4647
4648   /* Write out delay eligibility information, if DEFINE_DELAY present.
4649      (The function to compute the number of delay slots will be written
4650      below.)  */
4651   if (num_delays)
4652     {
4653       write_eligible_delay ("delay");
4654       if (have_annul_true)
4655         write_eligible_delay ("annul_true");
4656       if (have_annul_false)
4657         write_eligible_delay ("annul_false");
4658     }
4659
4660   /* Write out constant delay slot info.  */
4661   write_const_num_delay_slots ();
4662
4663   write_length_unit_log ();
4664
4665   fflush (stdout);
4666   return (ferror (stdout) != 0 ? FATAL_EXIT_CODE : SUCCESS_EXIT_CODE);
4667 }