gcc/genattrtab.c

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