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