gcc/genattrtab.c

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