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 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, 59 Temple Place - Suite 330, Boston, MA
  21 02111-1307, USA.  */
  22
  23 /* This program handles insn attributes and the DEFINE_DELAY and
  24    DEFINE_FUNCTION_UNIT 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_FUNCTION_UNIT.  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 and DEFINE_FUNCTION_UNIT
  74    definitions is to create arbitrarily complex expressions and have the
  75    optimization simplify them.
  76
  77    Once optimization is complete, any required routines and definitions
  78    will be written.
  79
  80    An optimization that is not yet implemented is to hoist the constant
  81    expressions entirely out of the routines and definitions that are written.
  82    A way to do this is to iterate over all possible combinations of values
  83    for constant attributes and generate a set of functions for that given
  84    combination.  An initialization function would be written that evaluates
  85    the attributes and installs the corresponding set of routines and
  86    definitions (each would be accessed through a pointer).
  87
  88    We use the flags in an RTX as follows:
  89    `unchanging' (ATTR_IND_SIMPLIFIED_P): This rtx is fully simplified
  90       independent of the insn code.
  91    `in_struct' (ATTR_CURR_SIMPLIFIED_P): This rtx is fully simplified
  92       for the insn code currently being processed (see optimize_attrs).
  93    `return_val' (ATTR_PERMANENT_P): This rtx is permanent and unique
  94       (see attr_rtx).
  95    `volatil' (ATTR_EQ_ATTR_P): During simplify_by_exploding the value of an
  96       EQ_ATTR rtx is true if !volatil and false if volatil.  */
  97
  98 #define ATTR_IND_SIMPLIFIED_P(RTX) (RTX_FLAG((RTX), unchanging))
  99 #define ATTR_CURR_SIMPLIFIED_P(RTX) (RTX_FLAG((RTX), in_struct))
 100 #define ATTR_PERMANENT_P(RTX) (RTX_FLAG((RTX), return_val))
 101 #define ATTR_EQ_ATTR_P(RTX) (RTX_FLAG((RTX), volatil))
 102
 103 #if 0
 104 #define strcmp_check(S1, S2) ((S1) == (S2)              \
 105                               ? 0                       \
 106                               : (strcmp ((S1), (S2))    \
 107                                  ? 1                    \
 108                                  : (abort (), 0)))
 109 #else
 110 #define strcmp_check(S1, S2) ((S1) != (S2))
 111 #endif
 112
 113 #include "bconfig.h"
 114 #include "system.h"
 115 #include "coretypes.h"
 116 #include "tm.h"
 117 #include "rtl.h"
 118 #include "ggc.h"
 119 #include "gensupport.h"
 120
 121 #ifdef HAVE_SYS_RESOURCE_H
 122 # include <sys/resource.h>
 123 #endif
 124
 125 /* We must include obstack.h after <sys/time.h>, to avoid lossage with
 126    /usr/include/sys/stdtypes.h on Sun OS 4.x.  */
 127 #include "obstack.h"
 128 #include "errors.h"
 129
 130 #include "genattrtab.h"
 131
 132 static struct obstack obstack1, obstack2;
 133 struct obstack *hash_obstack = &obstack1;
 134 struct obstack *temp_obstack = &obstack2;
 135
 136 /* enough space to reserve for printing out ints */
 137 #define MAX_DIGITS (HOST_BITS_PER_INT * 3 / 10 + 3)
 138
 139 /* Define structures used to record attributes and values.  */
 140
 141 /* As each DEFINE_INSN, DEFINE_PEEPHOLE, or DEFINE_ASM_ATTRIBUTES is
 142    encountered, we store all the relevant information into a
 143    `struct insn_def'.  This is done to allow attribute definitions to occur
 144    anywhere in the file.  */
 145
 146 struct insn_def
 147 {
 148   struct insn_def *next;        /* Next insn in chain.  */
 149   rtx def;                      /* The DEFINE_...  */
 150   int insn_code;                /* Instruction number.  */
 151   int insn_index;               /* Expression numer in file, for errors.  */
 152   int lineno;                   /* Line number.  */
 153   int num_alternatives;         /* Number of alternatives.  */
 154   int vec_idx;                  /* Index of attribute vector in `def'.  */
 155 };
 156
 157 /* Once everything has been read in, we store in each attribute value a list
 158    of insn codes that have that value.  Here is the structure used for the
 159    list.  */
 160
 161 struct insn_ent
 162 {
 163   struct insn_ent *next;        /* Next in chain.  */
 164   int insn_code;                /* Instruction number.  */
 165   int insn_index;               /* Index of definition in file */
 166   int lineno;                   /* Line number.  */
 167 };
 168
 169 /* Each value of an attribute (either constant or computed) is assigned a
 170    structure which is used as the listhead of the insns that have that
 171    value.  */
 172
 173 struct attr_value
 174 {
 175   rtx value;                    /* Value of attribute.  */
 176   struct attr_value *next;      /* Next attribute value in chain.  */
 177   struct insn_ent *first_insn;  /* First insn with this value.  */
 178   int num_insns;                /* Number of insns with this value.  */
 179   int has_asm_insn;             /* True if this value used for `asm' insns */
 180 };
 181
 182 /* Structure for each attribute.  */
 183
 184 struct attr_desc
 185 {
 186   char *name;                   /* Name of attribute.  */
 187   struct attr_desc *next;       /* Next attribute.  */
 188   struct attr_value *first_value; /* First value of this attribute.  */
 189   struct attr_value *default_val; /* Default value for this attribute.  */
 190   int lineno : 24;              /* Line number.  */
 191   unsigned is_numeric   : 1;    /* Values of this attribute are numeric.  */
 192   unsigned negative_ok  : 1;    /* Allow negative numeric values.  */
 193   unsigned unsigned_p   : 1;    /* Make the output function unsigned int.  */
 194   unsigned is_const     : 1;    /* Attribute value constant for each run.  */
 195   unsigned is_special   : 1;    /* Don't call `write_attr_set'.  */
 196   unsigned func_units_p : 1;    /* This is the function_units attribute.  */
 197   unsigned blockage_p   : 1;    /* This is the blockage range function.  */
 198   unsigned static_p     : 1;    /* Make the output function static.  */
 199 };
 200
 201 #define NULL_ATTR (struct attr_desc *) NULL
 202
 203 /* A range of values.  */
 204
 205 struct range
 206 {
 207   int min;
 208   int max;
 209 };
 210
 211 /* Structure for each DEFINE_DELAY.  */
 212
 213 struct delay_desc
 214 {
 215   rtx def;                      /* DEFINE_DELAY expression.  */
 216   struct delay_desc *next;      /* Next DEFINE_DELAY.  */
 217   int num;                      /* Number of DEFINE_DELAY, starting at 1.  */
 218   int lineno;                   /* Line number.  */
 219 };
 220
 221 /* Record information about each DEFINE_FUNCTION_UNIT.  */
 222
 223 struct function_unit_op
 224 {
 225   rtx condexp;                  /* Expression TRUE for applicable insn.  */
 226   struct function_unit_op *next; /* Next operation for this function unit.  */
 227   int num;                      /* Ordinal for this operation type in unit.  */
 228   int ready;                    /* Cost until data is ready.  */
 229   int issue_delay;              /* Cost until unit can accept another insn.  */
 230   rtx conflict_exp;             /* Expression TRUE for insns incurring issue delay.  */
 231   rtx issue_exp;                /* Expression computing issue delay.  */
 232   int lineno;                   /* Line number.  */
 233 };
 234
 235 /* Record information about each function unit mentioned in a
 236    DEFINE_FUNCTION_UNIT.  */
 237
 238 struct function_unit
 239 {
 240   const char *name;             /* Function unit name.  */
 241   struct function_unit *next;   /* Next function unit.  */
 242   int num;                      /* Ordinal of this unit type.  */
 243   int multiplicity;             /* Number of units of this type.  */
 244   int simultaneity;             /* Maximum number of simultaneous insns
 245                                    on this function unit or 0 if unlimited.  */
 246   rtx condexp;                  /* Expression TRUE for insn needing unit.  */
 247   int num_opclasses;            /* Number of different operation types.  */
 248   struct function_unit_op *ops; /* Pointer to first operation type.  */
 249   int needs_conflict_function;  /* Nonzero if a conflict function required.  */
 250   int needs_blockage_function;  /* Nonzero if a blockage function required.  */
 251   int needs_range_function;     /* Nonzero if blockage range function needed.  */
 252   rtx default_cost;             /* Conflict cost, if constant.  */
 253   struct range issue_delay;     /* Range of issue delay values.  */
 254   int max_blockage;             /* Maximum time an insn blocks the unit.  */
 255   int first_lineno;             /* First seen line number.  */
 256 };
 257
 258 /* Listheads of above structures.  */
 259
 260 /* This one is indexed by the first character of the attribute name.  */
 261 #define MAX_ATTRS_INDEX 256
 262 static struct attr_desc *attrs[MAX_ATTRS_INDEX];
 263 static struct insn_def *defs;
 264 static struct delay_desc *delays;
 265 static struct function_unit *units;
 266
 267 /* An expression where all the unknown terms are EQ_ATTR tests can be
 268    rearranged into a COND provided we can enumerate all possible
 269    combinations of the unknown values.  The set of combinations become the
 270    tests of the COND; the value of the expression given that combination is
 271    computed and becomes the corresponding value.  To do this, we must be
 272    able to enumerate all values for each attribute used in the expression
 273    (currently, we give up if we find a numeric attribute).
 274
 275    If the set of EQ_ATTR tests used in an expression tests the value of N
 276    different attributes, the list of all possible combinations can be made
 277    by walking the N-dimensional attribute space defined by those
 278    attributes.  We record each of these as a struct dimension.
 279
 280    The algorithm relies on sharing EQ_ATTR nodes: if two nodes in an
 281    expression are the same, the will also have the same address.  We find
 282    all the EQ_ATTR nodes by marking them ATTR_EQ_ATTR_P.  This bit later
 283    represents the value of an EQ_ATTR node, so once all nodes are marked,
 284    they are also given an initial value of FALSE.
 285
 286    We then separate the set of EQ_ATTR nodes into dimensions for each
 287    attribute and put them on the VALUES list.  Terms are added as needed by
 288    `add_values_to_cover' so that all possible values of the attribute are
 289    tested.
 290
 291    Each dimension also has a current value.  This is the node that is
 292    currently considered to be TRUE.  If this is one of the nodes added by
 293    `add_values_to_cover', all the EQ_ATTR tests in the original expression
 294    will be FALSE.  Otherwise, only the CURRENT_VALUE will be true.
 295
 296    NUM_VALUES is simply the length of the VALUES list and is there for
 297    convenience.
 298
 299    Once the dimensions are created, the algorithm enumerates all possible
 300    values and computes the current value of the given expression.  */
 301
 302 struct dimension
 303 {
 304   struct attr_desc *attr;       /* Attribute for this dimension.  */
 305   rtx values;                   /* List of attribute values used.  */
 306   rtx current_value;            /* Position in the list for the TRUE value.  */
 307   int num_values;               /* Length of the values list.  */
 308 };
 309
 310 /* Other variables.  */
 311
 312 static int insn_code_number;
 313 static int insn_index_number;
 314 static int got_define_asm_attributes;
 315 static int must_extract;
 316 static int must_constrain;
 317 static int address_used;
 318 static int length_used;
 319 static int num_delays;
 320 static int have_annul_true, have_annul_false;
 321 static int num_units, num_unit_opclasses;
 322 static int num_insn_ents;
 323
 324 int num_dfa_decls;
 325
 326 /* Used as operand to `operate_exp':  */
 327
 328 enum operator {PLUS_OP, MINUS_OP, POS_MINUS_OP, EQ_OP, OR_OP, ORX_OP, MAX_OP, MIN_OP, RANGE_OP};
 329
 330 /* Stores, for each insn code, the number of constraint alternatives.  */
 331
 332 static int *insn_n_alternatives;
 333
 334 /* Stores, for each insn code, a bitmap that has bits on for each possible
 335    alternative.  */
 336
 337 static int *insn_alternatives;
 338
 339 /* If nonzero, assume that the `alternative' attr has this value.
 340    This is the hashed, unique string for the numeral
 341    whose value is chosen alternative.  */
 342
 343 static const char *current_alternative_string;
 344
 345 /* Used to simplify expressions.  */
 346
 347 static rtx true_rtx, false_rtx;
 348
 349 /* Used to reduce calls to `strcmp' */
 350
 351 static char *alternative_name;
 352 static const char *length_str;
 353 static const char *delay_type_str;
 354 static const char *delay_1_0_str;
 355 static const char *num_delay_slots_str;
 356
 357 /* Indicate that REG_DEAD notes are valid if dead_or_set_p is ever
 358    called.  */
 359
 360 int reload_completed = 0;
 361
 362 /* Some machines test `optimize' in macros called from rtlanal.c, so we need
 363    to define it here.  */
 364
 365 int optimize = 0;
 366
 367 /* Simplify an expression.  Only call the routine if there is something to
 368    simplify.  */
 369 #define SIMPLIFY_TEST_EXP(EXP,INSN_CODE,INSN_INDEX)     \
 370   (ATTR_IND_SIMPLIFIED_P (EXP) || ATTR_CURR_SIMPLIFIED_P (EXP) ? (EXP)  \
 371    : simplify_test_exp (EXP, INSN_CODE, INSN_INDEX))
 372
 373 /* Simplify (eq_attr ("alternative") ...)
 374    when we are working with a particular alternative.  */
 375 #define SIMPLIFY_ALTERNATIVE(EXP)                               \
 376   if (current_alternative_string                                \
 377       && GET_CODE ((EXP)) == EQ_ATTR                            \
 378       && XSTR ((EXP), 0) == alternative_name)                   \
 379     (EXP) = (XSTR ((EXP), 1) == current_alternative_string      \
 380             ? true_rtx : false_rtx);
 381
 382 #define DEF_ATTR_STRING(S) (attr_string ((S), strlen (S)))
 383
 384 /* These are referenced by rtlanal.c and hence need to be defined somewhere.
 385    They won't actually be used.  */
 386
 387 rtx global_rtl[GR_MAX];
 388 rtx pic_offset_table_rtx;
 389
 390 static void attr_hash_add_rtx   (int, rtx);
 391 static void attr_hash_add_string (int, char *);
 392 static rtx attr_rtx             (enum rtx_code, ...);
 393 static rtx attr_rtx_1           (enum rtx_code, va_list);
 394 static char *attr_string        (const char *, int);
 395 static rtx check_attr_value     (rtx, struct attr_desc *);
 396 static rtx convert_set_attr_alternative (rtx, struct insn_def *);
 397 static rtx convert_set_attr     (rtx, struct insn_def *);
 398 static void check_defs          (void);
 399 static rtx make_canonical       (struct attr_desc *, rtx);
 400 static struct attr_value *get_attr_value (rtx, struct attr_desc *, int);
 401 static rtx copy_rtx_unchanging  (rtx);
 402 static rtx copy_boolean         (rtx);
 403 static void expand_delays       (void);
 404 static rtx operate_exp          (enum operator, rtx, rtx);
 405 static void expand_units        (void);
 406 static rtx simplify_knowing     (rtx, rtx);
 407 static rtx encode_units_mask    (rtx);
 408 static void fill_attr           (struct attr_desc *);
 409 static rtx substitute_address   (rtx, rtx (*) (rtx), rtx (*) (rtx));
 410 static void make_length_attrs   (void);
 411 static rtx identity_fn          (rtx);
 412 static rtx zero_fn              (rtx);
 413 static rtx one_fn               (rtx);
 414 static rtx max_fn               (rtx);
 415 static void write_length_unit_log (void);
 416 static rtx simplify_cond        (rtx, int, int);
 417 static rtx simplify_by_exploding (rtx);
 418 static int find_and_mark_used_attributes (rtx, rtx *, int *);
 419 static void unmark_used_attributes (rtx, struct dimension *, int);
 420 static int add_values_to_cover  (struct dimension *);
 421 static int increment_current_value (struct dimension *, int);
 422 static rtx test_for_current_value (struct dimension *, int);
 423 static rtx simplify_with_current_value (rtx, struct dimension *, int);
 424 static rtx simplify_with_current_value_aux (rtx);
 425 static void clear_struct_flag (rtx);
 426 static void remove_insn_ent  (struct attr_value *, struct insn_ent *);
 427 static void insert_insn_ent  (struct attr_value *, struct insn_ent *);
 428 static rtx insert_right_side    (enum rtx_code, rtx, rtx, int, int);
 429 static rtx make_alternative_compare (int);
 430 static int compute_alternative_mask (rtx, enum rtx_code);
 431 static rtx evaluate_eq_attr     (rtx, rtx, int, int);
 432 static rtx simplify_and_tree    (rtx, rtx *, int, int);
 433 static rtx simplify_or_tree     (rtx, rtx *, int, int);
 434 static rtx simplify_test_exp    (rtx, int, int);
 435 static rtx simplify_test_exp_in_temp (rtx, int, int);
 436 static void optimize_attrs      (void);
 437 static void gen_attr            (rtx, int);
 438 static int count_alternatives   (rtx);
 439 static int compares_alternatives_p (rtx);
 440 static int contained_in_p       (rtx, rtx);
 441 static void gen_insn            (rtx, int);
 442 static void gen_delay           (rtx, int);
 443 static void gen_unit            (rtx, int);
 444 static void write_test_expr     (rtx, int);
 445 static int max_attr_value       (rtx, int*);
 446 static int or_attr_value        (rtx, int*);
 447 static void walk_attr_value     (rtx);
 448 static void write_attr_get      (struct attr_desc *);
 449 static rtx eliminate_known_true (rtx, rtx, int, int);
 450 static void write_attr_set      (struct attr_desc *, int, rtx,
 451                                  const char *, const char *, rtx,
 452                                  int, int);
 453 static void write_attr_case     (struct attr_desc *, struct attr_value *,
 454                                  int, const char *, const char *, int, rtx);
 455 static void write_unit_name     (const char *, int, const char *);
 456 static void write_attr_valueq   (struct attr_desc *, const char *);
 457 static void write_attr_value    (struct attr_desc *, rtx);
 458 static void write_upcase        (const char *);
 459 static void write_indent        (int);
 460 static void write_eligible_delay (const char *);
 461 static void write_function_unit_info (void);
 462 static void write_complex_function (struct function_unit *, const char *,
 463                                     const char *);
 464 static int write_expr_attr_cache (rtx, struct attr_desc *);
 465 static void write_toplevel_expr (rtx);
 466 static void write_const_num_delay_slots (void);
 467 static char *next_comma_elt     (const char **);
 468 static struct attr_desc *find_attr (const char **, int);
 469 static struct attr_value *find_most_used  (struct attr_desc *);
 470 static rtx find_single_value    (struct attr_desc *);
 471 static void extend_range        (struct range *, int, int);
 472 static rtx attr_eq              (const char *, const char *);
 473 static const char *attr_numeral (int);
 474 static int attr_equal_p         (rtx, rtx);
 475 static rtx attr_copy_rtx        (rtx);
 476 static int attr_rtx_cost        (rtx);
 477 static bool attr_alt_subset_p (rtx, rtx);
 478 static bool attr_alt_subset_of_compl_p (rtx, rtx);
 479 static rtx attr_alt_intersection (rtx, rtx);
 480 static rtx attr_alt_union (rtx, rtx);
 481 static rtx attr_alt_complement (rtx);
 482 static bool attr_alt_bit_p (rtx, int);
 483 static rtx mk_attr_alt (int);
 484
 485 #define oballoc(size) obstack_alloc (hash_obstack, size)
 486
 487 /* Hash table for sharing RTL and strings.  */
 488
 489 /* Each hash table slot is a bucket containing a chain of these structures.
 490    Strings are given negative hash codes; RTL expressions are given positive
 491    hash codes.  */
 492
 493 struct attr_hash
 494 {
 495   struct attr_hash *next;       /* Next structure in the bucket.  */
 496   int hashcode;                 /* Hash code of this rtx or string.  */
 497   union
 498     {
 499       char *str;                /* The string (negative hash codes) */
 500       rtx rtl;                  /* or the RTL recorded here.  */
 501     } u;
 502 };
 503
 504 /* Now here is the hash table.  When recording an RTL, it is added to
 505    the slot whose index is the hash code mod the table size.  Note
 506    that the hash table is used for several kinds of RTL (see attr_rtx)
 507    and for strings.  While all these live in the same table, they are
 508    completely independent, and the hash code is computed differently
 509    for each.  */
 510
 511 #define RTL_HASH_SIZE 4093
 512 struct attr_hash *attr_hash_table[RTL_HASH_SIZE];
 513
 514 /* Here is how primitive or already-shared RTL's hash
 515    codes are made.  */
 516 #define RTL_HASH(RTL) ((long) (RTL) & 0777777)
 517
 518 /* Add an entry to the hash table for RTL with hash code HASHCODE.  */
 519
 520 static void
 521 attr_hash_add_rtx (int hashcode, rtx rtl)
 522 {
 523   struct attr_hash *h;
 524
 525   h = obstack_alloc (hash_obstack, sizeof (struct attr_hash));
 526   h->hashcode = hashcode;
 527   h->u.rtl = rtl;
 528   h->next = attr_hash_table[hashcode % RTL_HASH_SIZE];
 529   attr_hash_table[hashcode % RTL_HASH_SIZE] = h;
 530 }
 531
 532 /* Add an entry to the hash table for STRING with hash code HASHCODE.  */
 533
 534 static void
 535 attr_hash_add_string (int hashcode, char *str)
 536 {
 537   struct attr_hash *h;
 538
 539   h = obstack_alloc (hash_obstack, sizeof (struct attr_hash));
 540   h->hashcode = -hashcode;
 541   h->u.str = str;
 542   h->next = attr_hash_table[hashcode % RTL_HASH_SIZE];
 543   attr_hash_table[hashcode % RTL_HASH_SIZE] = h;
 544 }
 545
 546 /* Generate an RTL expression, but avoid duplicates.
 547    Set the ATTR_PERMANENT_P flag for these permanent objects.
 548
 549    In some cases we cannot uniquify; then we return an ordinary
 550    impermanent rtx with ATTR_PERMANENT_P clear.
 551
 552    Args are as follows:
 553
 554    rtx attr_rtx (code, [element1, ..., elementn])  */
 555
 556 static rtx
 557 attr_rtx_1 (enum rtx_code code, va_list p)
 558 {
 559   rtx rt_val = NULL_RTX;/* RTX to return to caller...           */
 560   int hashcode;
 561   struct attr_hash *h;
 562   struct obstack *old_obstack = rtl_obstack;
 563
 564   /* For each of several cases, search the hash table for an existing entry.
 565      Use that entry if one is found; otherwise create a new RTL and add it
 566      to the table.  */
 567
 568   if (GET_RTX_CLASS (code) == RTX_UNARY)
 569     {
 570       rtx arg0 = va_arg (p, rtx);
 571
 572       /* A permanent object cannot point to impermanent ones.  */
 573       if (! ATTR_PERMANENT_P (arg0))
 574         {
 575           rt_val = rtx_alloc (code);
 576           XEXP (rt_val, 0) = arg0;
 577           return rt_val;
 578         }
 579
 580       hashcode = ((HOST_WIDE_INT) code + RTL_HASH (arg0));
 581       for (h = attr_hash_table[hashcode % RTL_HASH_SIZE]; h; h = h->next)
 582         if (h->hashcode == hashcode
 583             && GET_CODE (h->u.rtl) == code
 584             && XEXP (h->u.rtl, 0) == arg0)
 585           return h->u.rtl;
 586
 587       if (h == 0)
 588         {
 589           rtl_obstack = hash_obstack;
 590           rt_val = rtx_alloc (code);
 591           XEXP (rt_val, 0) = arg0;
 592         }
 593     }
 594   else if (GET_RTX_CLASS (code) == RTX_BIN_ARITH
 595            || GET_RTX_CLASS (code) == RTX_COMM_ARITH
 596            || GET_RTX_CLASS (code) == RTX_COMPARE
 597            || GET_RTX_CLASS (code) == RTX_COMM_COMPARE)
 598     {
 599       rtx arg0 = va_arg (p, rtx);
 600       rtx arg1 = va_arg (p, rtx);
 601
 602       /* A permanent object cannot point to impermanent ones.  */
 603       if (! ATTR_PERMANENT_P (arg0) || ! ATTR_PERMANENT_P (arg1))
 604         {
 605           rt_val = rtx_alloc (code);
 606           XEXP (rt_val, 0) = arg0;
 607           XEXP (rt_val, 1) = arg1;
 608           return rt_val;
 609         }
 610
 611       hashcode = ((HOST_WIDE_INT) code + RTL_HASH (arg0) + RTL_HASH (arg1));
 612       for (h = attr_hash_table[hashcode % RTL_HASH_SIZE]; h; h = h->next)
 613         if (h->hashcode == hashcode
 614             && GET_CODE (h->u.rtl) == code
 615             && XEXP (h->u.rtl, 0) == arg0
 616             && XEXP (h->u.rtl, 1) == arg1)
 617           return h->u.rtl;
 618
 619       if (h == 0)
 620         {
 621           rtl_obstack = hash_obstack;
 622           rt_val = rtx_alloc (code);
 623           XEXP (rt_val, 0) = arg0;
 624           XEXP (rt_val, 1) = arg1;
 625         }
 626     }
 627   else if (GET_RTX_LENGTH (code) == 1
 628            && GET_RTX_FORMAT (code)[0] == 's')
 629     {
 630       char *arg0 = va_arg (p, char *);
 631
 632       arg0 = DEF_ATTR_STRING (arg0);
 633
 634       hashcode = ((HOST_WIDE_INT) code + RTL_HASH (arg0));
 635       for (h = attr_hash_table[hashcode % RTL_HASH_SIZE]; h; h = h->next)
 636         if (h->hashcode == hashcode
 637             && GET_CODE (h->u.rtl) == code
 638             && XSTR (h->u.rtl, 0) == arg0)
 639           return h->u.rtl;
 640
 641       if (h == 0)
 642         {
 643           rtl_obstack = hash_obstack;
 644           rt_val = rtx_alloc (code);
 645           XSTR (rt_val, 0) = arg0;
 646         }
 647     }
 648   else if (GET_RTX_LENGTH (code) == 2
 649            && GET_RTX_FORMAT (code)[0] == 's'
 650            && GET_RTX_FORMAT (code)[1] == 's')
 651     {
 652       char *arg0 = va_arg (p, char *);
 653       char *arg1 = va_arg (p, char *);
 654
 655       hashcode = ((HOST_WIDE_INT) code + RTL_HASH (arg0) + RTL_HASH (arg1));
 656       for (h = attr_hash_table[hashcode % RTL_HASH_SIZE]; h; h = h->next)
 657         if (h->hashcode == hashcode
 658             && GET_CODE (h->u.rtl) == code
 659             && XSTR (h->u.rtl, 0) == arg0
 660             && XSTR (h->u.rtl, 1) == arg1)
 661           return h->u.rtl;
 662
 663       if (h == 0)
 664         {
 665           rtl_obstack = hash_obstack;
 666           rt_val = rtx_alloc (code);
 667           XSTR (rt_val, 0) = arg0;
 668           XSTR (rt_val, 1) = arg1;
 669         }
 670     }
 671   else if (code == CONST_INT)
 672     {
 673       HOST_WIDE_INT arg0 = va_arg (p, HOST_WIDE_INT);
 674       if (arg0 == 0)
 675         return false_rtx;
 676       else if (arg0 == 1)
 677         return true_rtx;
 678       else
 679         goto nohash;
 680     }
 681   else
 682     {
 683       int i;            /* Array indices...                     */
 684       const char *fmt;  /* Current rtx's format...              */
 685     nohash:
 686       rt_val = rtx_alloc (code);        /* Allocate the storage space.  */
 687
 688       fmt = GET_RTX_FORMAT (code);      /* Find the right format...  */
 689       for (i = 0; i < GET_RTX_LENGTH (code); i++)
 690         {
 691           switch (*fmt++)
 692             {
 693             case '0':           /* Unused field.  */
 694               break;
 695
 696             case 'i':           /* An integer?  */
 697               XINT (rt_val, i) = va_arg (p, int);
 698               break;
 699
 700             case 'w':           /* A wide integer? */
 701               XWINT (rt_val, i) = va_arg (p, HOST_WIDE_INT);
 702               break;
 703
 704             case 's':           /* A string?  */
 705               XSTR (rt_val, i) = va_arg (p, char *);
 706               break;
 707
 708             case 'e':           /* An expression?  */
 709             case 'u':           /* An insn?  Same except when printing.  */
 710               XEXP (rt_val, i) = va_arg (p, rtx);
 711               break;
 712
 713             case 'E':           /* An RTX vector?  */
 714               XVEC (rt_val, i) = va_arg (p, rtvec);
 715               break;
 716
 717             default:
 718               abort ();
 719             }
 720         }
 721       return rt_val;
 722     }
 723
 724   rtl_obstack = old_obstack;
 725   attr_hash_add_rtx (hashcode, rt_val);
 726   ATTR_PERMANENT_P (rt_val) = 1;
 727   return rt_val;
 728 }
 729
 730 static rtx
 731 attr_rtx (enum rtx_code code, ...)
 732 {
 733   rtx result;
 734   va_list p;
 735
 736   va_start (p, code);
 737   result = attr_rtx_1 (code, p);
 738   va_end (p);
 739   return result;
 740 }
 741
 742 /* Create a new string printed with the printf line arguments into a space
 743    of at most LEN bytes:
 744
 745    rtx attr_printf (len, format, [arg1, ..., argn])  */
 746
 747 char *
 748 attr_printf (unsigned int len, const char *fmt, ...)
 749 {
 750   char str[256];
 751   va_list p;
 752
 753   va_start (p, fmt);
 754
 755   if (len > sizeof str - 1) /* Leave room for \0.  */
 756     abort ();
 757
 758   vsprintf (str, fmt, p);
 759   va_end (p);
 760
 761   return DEF_ATTR_STRING (str);
 762 }
 763
 764 static rtx
 765 attr_eq (const char *name, const char *value)
 766 {
 767   return attr_rtx (EQ_ATTR, DEF_ATTR_STRING (name), DEF_ATTR_STRING (value));
 768 }
 769
 770 static const char *
 771 attr_numeral (int n)
 772 {
 773   return XSTR (make_numeric_value (n), 0);
 774 }
 775
 776 /* Return a permanent (possibly shared) copy of a string STR (not assumed
 777    to be null terminated) with LEN bytes.  */
 778
 779 static char *
 780 attr_string (const char *str, int len)
 781 {
 782   struct attr_hash *h;
 783   int hashcode;
 784   int i;
 785   char *new_str;
 786
 787   /* Compute the hash code.  */
 788   hashcode = (len + 1) * 613 + (unsigned) str[0];
 789   for (i = 1; i <= len; i += 2)
 790     hashcode = ((hashcode * 613) + (unsigned) str[i]);
 791   if (hashcode < 0)
 792     hashcode = -hashcode;
 793
 794   /* Search the table for the string.  */
 795   for (h = attr_hash_table[hashcode % RTL_HASH_SIZE]; h; h = h->next)
 796     if (h->hashcode == -hashcode && h->u.str[0] == str[0]
 797         && !strncmp (h->u.str, str, len))
 798       return h->u.str;                  /* <-- return if found.  */
 799
 800   /* Not found; create a permanent copy and add it to the hash table.  */
 801   new_str = obstack_alloc (hash_obstack, len + 1);
 802   memcpy (new_str, str, len);
 803   new_str[len] = '\0';
 804   attr_hash_add_string (hashcode, new_str);
 805
 806   return new_str;                       /* Return the new string.  */
 807 }
 808
 809 /* Check two rtx's for equality of contents,
 810    taking advantage of the fact that if both are hashed
 811    then they can't be equal unless they are the same object.  */
 812
 813 static int
 814 attr_equal_p (rtx x, rtx y)
 815 {
 816   return (x == y || (! (ATTR_PERMANENT_P (x) && ATTR_PERMANENT_P (y))
 817                      && rtx_equal_p (x, y)));
 818 }
 819
 820 /* Copy an attribute value expression,
 821    descending to all depths, but not copying any
 822    permanent hashed subexpressions.  */
 823
 824 static rtx
 825 attr_copy_rtx (rtx orig)
 826 {
 827   rtx copy;
 828   int i, j;
 829   RTX_CODE code;
 830   const char *format_ptr;
 831
 832   /* No need to copy a permanent object.  */
 833   if (ATTR_PERMANENT_P (orig))
 834     return orig;
 835
 836   code = GET_CODE (orig);
 837
 838   switch (code)
 839     {
 840     case REG:
 841     case CONST_INT:
 842     case CONST_DOUBLE:
 843     case CONST_VECTOR:
 844     case SYMBOL_REF:
 845     case CODE_LABEL:
 846     case PC:
 847     case CC0:
 848       return orig;
 849
 850     default:
 851       break;
 852     }
 853
 854   copy = rtx_alloc (code);
 855   PUT_MODE (copy, GET_MODE (orig));
 856   ATTR_IND_SIMPLIFIED_P (copy) = ATTR_IND_SIMPLIFIED_P (orig);
 857   ATTR_CURR_SIMPLIFIED_P (copy) = ATTR_CURR_SIMPLIFIED_P (orig);
 858   ATTR_PERMANENT_P (copy) = ATTR_PERMANENT_P (orig);
 859   ATTR_EQ_ATTR_P (copy) = ATTR_EQ_ATTR_P (orig);
 860
 861   format_ptr = GET_RTX_FORMAT (GET_CODE (copy));
 862
 863   for (i = 0; i < GET_RTX_LENGTH (GET_CODE (copy)); i++)
 864     {
 865       switch (*format_ptr++)
 866         {
 867         case 'e':
 868           XEXP (copy, i) = XEXP (orig, i);
 869           if (XEXP (orig, i) != NULL)
 870             XEXP (copy, i) = attr_copy_rtx (XEXP (orig, i));
 871           break;
 872
 873         case 'E':
 874         case 'V':
 875           XVEC (copy, i) = XVEC (orig, i);
 876           if (XVEC (orig, i) != NULL)
 877             {
 878               XVEC (copy, i) = rtvec_alloc (XVECLEN (orig, i));
 879               for (j = 0; j < XVECLEN (copy, i); j++)
 880                 XVECEXP (copy, i, j) = attr_copy_rtx (XVECEXP (orig, i, j));
 881             }
 882           break;
 883
 884         case 'n':
 885         case 'i':
 886           XINT (copy, i) = XINT (orig, i);
 887           break;
 888
 889         case 'w':
 890           XWINT (copy, i) = XWINT (orig, i);
 891           break;
 892
 893         case 's':
 894         case 'S':
 895           XSTR (copy, i) = XSTR (orig, i);
 896           break;
 897
 898         default:
 899           abort ();
 900         }
 901     }
 902   return copy;
 903 }
 904
 905 /* Given a test expression for an attribute, ensure it is validly formed.
 906    IS_CONST indicates whether the expression is constant for each compiler
 907    run (a constant expression may not test any particular insn).
 908
 909    Convert (eq_attr "att" "a1,a2") to (ior (eq_attr ... ) (eq_attrq ..))
 910    and (eq_attr "att" "!a1") to (not (eq_attr "att" "a1")).  Do the latter
 911    test first so that (eq_attr "att" "!a1,a2,a3") works as expected.
 912
 913    Update the string address in EQ_ATTR expression to be the same used
 914    in the attribute (or `alternative_name') to speed up subsequent
 915    `find_attr' calls and eliminate most `strcmp' calls.
 916
 917    Return the new expression, if any.  */
 918
 919 rtx
 920 check_attr_test (rtx exp, int is_const, int lineno)
 921 {
 922   struct attr_desc *attr;
 923   struct attr_value *av;
 924   const char *name_ptr, *p;
 925   rtx orexp, newexp;
 926
 927   switch (GET_CODE (exp))
 928     {
 929     case EQ_ATTR:
 930       /* Handle negation test.  */
 931       if (XSTR (exp, 1)[0] == '!')
 932         return check_attr_test (attr_rtx (NOT,
 933                                           attr_eq (XSTR (exp, 0),
 934                                                    &XSTR (exp, 1)[1])),
 935                                 is_const, lineno);
 936
 937       else if (n_comma_elts (XSTR (exp, 1)) == 1)
 938         {
 939           attr = find_attr (&XSTR (exp, 0), 0);
 940           if (attr == NULL)
 941             {
 942               if (! strcmp (XSTR (exp, 0), "alternative"))
 943                 return mk_attr_alt (1 << atoi (XSTR (exp, 1)));
 944               else
 945                 fatal ("unknown attribute `%s' in EQ_ATTR", XSTR (exp, 0));
 946             }
 947
 948           if (is_const && ! attr->is_const)
 949             fatal ("constant expression uses insn attribute `%s' in EQ_ATTR",
 950                    XSTR (exp, 0));
 951
 952           /* Copy this just to make it permanent,
 953              so expressions using it can be permanent too.  */
 954           exp = attr_eq (XSTR (exp, 0), XSTR (exp, 1));
 955
 956           /* It shouldn't be possible to simplify the value given to a
 957              constant attribute, so don't expand this until it's time to
 958              write the test expression.  */
 959           if (attr->is_const)
 960             ATTR_IND_SIMPLIFIED_P (exp) = 1;
 961
 962           if (attr->is_numeric)
 963             {
 964               for (p = XSTR (exp, 1); *p; p++)
 965                 if (! ISDIGIT (*p))
 966                   fatal ("attribute `%s' takes only numeric values",
 967                          XSTR (exp, 0));
 968             }
 969           else
 970             {
 971               for (av = attr->first_value; av; av = av->next)
 972                 if (GET_CODE (av->value) == CONST_STRING
 973                     && ! strcmp (XSTR (exp, 1), XSTR (av->value, 0)))
 974                   break;
 975
 976               if (av == NULL)
 977                 fatal ("unknown value `%s' for `%s' attribute",
 978                        XSTR (exp, 1), XSTR (exp, 0));
 979             }
 980         }
 981       else
 982         {
 983           if (! strcmp (XSTR (exp, 0), "alternative"))
 984             {
 985               int set = 0;
 986
 987               name_ptr = XSTR (exp, 1);
 988               while ((p = next_comma_elt (&name_ptr)) != NULL)
 989                 set |= 1 << atoi (p);
 990
 991               return mk_attr_alt (set);
 992             }
 993           else
 994             {
 995               /* Make an IOR tree of the possible values.  */
 996               orexp = false_rtx;
 997               name_ptr = XSTR (exp, 1);
 998               while ((p = next_comma_elt (&name_ptr)) != NULL)
 999                 {
1000                   newexp = attr_eq (XSTR (exp, 0), p);
1001                   orexp = insert_right_side (IOR, orexp, newexp, -2, -2);
1002                 }
1003
1004               return check_attr_test (orexp, is_const, lineno);
1005             }
1006         }
1007       break;
1008
1009     case ATTR_FLAG:
1010       break;
1011
1012     case CONST_INT:
1013       /* Either TRUE or FALSE.  */
1014       if (XWINT (exp, 0))
1015         return true_rtx;
1016       else
1017         return false_rtx;
1018
1019     case IOR:
1020     case AND:
1021       XEXP (exp, 0) = check_attr_test (XEXP (exp, 0), is_const, lineno);
1022       XEXP (exp, 1) = check_attr_test (XEXP (exp, 1), is_const, lineno);
1023       break;
1024
1025     case NOT:
1026       XEXP (exp, 0) = check_attr_test (XEXP (exp, 0), is_const, lineno);
1027       break;
1028
1029     case MATCH_OPERAND:
1030       if (is_const)
1031         fatal ("RTL operator \"%s\" not valid in constant attribute test",
1032                GET_RTX_NAME (GET_CODE (exp)));
1033       /* These cases can't be simplified.  */
1034       ATTR_IND_SIMPLIFIED_P (exp) = 1;
1035       break;
1036
1037     case LE:  case LT:  case GT:  case GE:
1038     case LEU: case LTU: case GTU: case GEU:
1039     case NE:  case EQ:
1040       if (GET_CODE (XEXP (exp, 0)) == SYMBOL_REF
1041           && GET_CODE (XEXP (exp, 1)) == SYMBOL_REF)
1042         exp = attr_rtx (GET_CODE (exp),
1043                         attr_rtx (SYMBOL_REF, XSTR (XEXP (exp, 0), 0)),
1044                         attr_rtx (SYMBOL_REF, XSTR (XEXP (exp, 1), 0)));
1045       /* These cases can't be simplified.  */
1046       ATTR_IND_SIMPLIFIED_P (exp) = 1;
1047       break;
1048
1049     case SYMBOL_REF:
1050       if (is_const)
1051         {
1052           /* These cases are valid for constant attributes, but can't be
1053              simplified.  */
1054           exp = attr_rtx (SYMBOL_REF, XSTR (exp, 0));
1055           ATTR_IND_SIMPLIFIED_P (exp) = 1;
1056           break;
1057         }
1058     default:
1059       fatal ("RTL operator \"%s\" not valid in attribute test",
1060              GET_RTX_NAME (GET_CODE (exp)));
1061     }
1062
1063   return exp;
1064 }
1065
1066 /* Given an expression, ensure that it is validly formed and that all named
1067    attribute values are valid for the given attribute.  Issue a fatal error
1068    if not.  If no attribute is specified, assume a numeric attribute.
1069
1070    Return a perhaps modified replacement expression for the value.  */
1071
1072 static rtx
1073 check_attr_value (rtx exp, struct attr_desc *attr)
1074 {
1075   struct attr_value *av;
1076   const char *p;
1077   int i;
1078
1079   switch (GET_CODE (exp))
1080     {
1081     case CONST_INT:
1082       if (attr && ! attr->is_numeric)
1083         {
1084           message_with_line (attr->lineno,
1085                              "CONST_INT not valid for non-numeric attribute %s",
1086                              attr->name);
1087           have_error = 1;
1088           break;
1089         }
1090
1091       if (INTVAL (exp) < 0 && ! attr->negative_ok)
1092         {
1093           message_with_line (attr->lineno,
1094                              "negative numeric value specified for attribute %s",
1095                              attr->name);
1096           have_error = 1;
1097           break;
1098         }
1099       break;
1100
1101     case CONST_STRING:
1102       if (! strcmp (XSTR (exp, 0), "*"))
1103         break;
1104
1105       if (attr == 0 || attr->is_numeric)
1106         {
1107           p = XSTR (exp, 0);
1108           if (attr && attr->negative_ok && *p == '-')
1109             p++;
1110           for (; *p; p++)
1111             if (! ISDIGIT (*p))
1112               {
1113                 message_with_line (attr ? attr->lineno : 0,
1114                                    "non-numeric value for numeric attribute %s",
1115                                    attr ? attr->name : "internal");
1116                 have_error = 1;
1117                 break;
1118               }
1119           break;
1120         }
1121
1122       for (av = attr->first_value; av; av = av->next)
1123         if (GET_CODE (av->value) == CONST_STRING
1124             && ! strcmp (XSTR (av->value, 0), XSTR (exp, 0)))
1125           break;
1126
1127       if (av == NULL)
1128         {
1129           message_with_line (attr->lineno,
1130                              "unknown value `%s' for `%s' attribute",
1131                              XSTR (exp, 0), attr ? attr->name : "internal");
1132           have_error = 1;
1133         }
1134       break;
1135
1136     case IF_THEN_ELSE:
1137       XEXP (exp, 0) = check_attr_test (XEXP (exp, 0),
1138                                        attr ? attr->is_const : 0,
1139                                        attr ? attr->lineno : 0);
1140       XEXP (exp, 1) = check_attr_value (XEXP (exp, 1), attr);
1141       XEXP (exp, 2) = check_attr_value (XEXP (exp, 2), attr);
1142       break;
1143
1144     case PLUS:
1145     case MINUS:
1146     case MULT:
1147     case DIV:
1148     case MOD:
1149       if (attr && !attr->is_numeric)
1150         {
1151           message_with_line (attr->lineno,
1152                              "invalid operation `%s' for non-numeric attribute value",
1153                              GET_RTX_NAME (GET_CODE (exp)));
1154           have_error = 1;
1155           break;
1156         }
1157       /* Fall through.  */
1158
1159     case IOR:
1160     case AND:
1161       XEXP (exp, 0) = check_attr_value (XEXP (exp, 0), attr);
1162       XEXP (exp, 1) = check_attr_value (XEXP (exp, 1), attr);
1163       break;
1164
1165     case FFS:
1166     case CLZ:
1167     case CTZ:
1168     case POPCOUNT:
1169     case PARITY:
1170       XEXP (exp, 0) = check_attr_value (XEXP (exp, 0), attr);
1171       break;
1172
1173     case COND:
1174       if (XVECLEN (exp, 0) % 2 != 0)
1175         {
1176           message_with_line (attr->lineno,
1177                              "first operand of COND must have even length");
1178           have_error = 1;
1179           break;
1180         }
1181
1182       for (i = 0; i < XVECLEN (exp, 0); i += 2)
1183         {
1184           XVECEXP (exp, 0, i) = check_attr_test (XVECEXP (exp, 0, i),
1185                                                  attr ? attr->is_const : 0,
1186                                                  attr ? attr->lineno : 0);
1187           XVECEXP (exp, 0, i + 1)
1188             = check_attr_value (XVECEXP (exp, 0, i + 1), attr);
1189         }
1190
1191       XEXP (exp, 1) = check_attr_value (XEXP (exp, 1), attr);
1192       break;
1193
1194     case ATTR:
1195       {
1196         struct attr_desc *attr2 = find_attr (&XSTR (exp, 0), 0);
1197         if (attr2 == NULL)
1198           {
1199             message_with_line (attr ? attr->lineno : 0,
1200                                "unknown attribute `%s' in ATTR",
1201                                XSTR (exp, 0));
1202             have_error = 1;
1203           }
1204         else if (attr && attr->is_const && ! attr2->is_const)
1205           {
1206             message_with_line (attr->lineno,
1207                 "non-constant attribute `%s' referenced from `%s'",
1208                 XSTR (exp, 0), attr->name);
1209             have_error = 1;
1210           }
1211         else if (attr
1212                  && (attr->is_numeric != attr2->is_numeric
1213                      || (! attr->negative_ok && attr2->negative_ok)))
1214           {
1215             message_with_line (attr->lineno,
1216                 "numeric attribute mismatch calling `%s' from `%s'",
1217                 XSTR (exp, 0), attr->name);
1218             have_error = 1;
1219           }
1220       }
1221       break;
1222
1223     case SYMBOL_REF:
1224       /* A constant SYMBOL_REF is valid as a constant attribute test and
1225          is expanded later by make_canonical into a COND.  In a non-constant
1226          attribute test, it is left be.  */
1227       return attr_rtx (SYMBOL_REF, XSTR (exp, 0));
1228
1229     default:
1230       message_with_line (attr ? attr->lineno : 0,
1231                          "invalid operation `%s' for attribute value",
1232                          GET_RTX_NAME (GET_CODE (exp)));
1233       have_error = 1;
1234       break;
1235     }
1236
1237   return exp;
1238 }
1239
1240 /* Given an SET_ATTR_ALTERNATIVE expression, convert to the canonical SET.
1241    It becomes a COND with each test being (eq_attr "alternative "n") */
1242
1243 static rtx
1244 convert_set_attr_alternative (rtx exp, struct insn_def *id)
1245 {
1246   int num_alt = id->num_alternatives;
1247   rtx condexp;
1248   int i;
1249
1250   if (XVECLEN (exp, 1) != num_alt)
1251     {
1252       message_with_line (id->lineno,
1253                          "bad number of entries in SET_ATTR_ALTERNATIVE");
1254       have_error = 1;
1255       return NULL_RTX;
1256     }
1257
1258   /* Make a COND with all tests but the last.  Select the last value via the
1259      default.  */
1260   condexp = rtx_alloc (COND);
1261   XVEC (condexp, 0) = rtvec_alloc ((num_alt - 1) * 2);
1262
1263   for (i = 0; i < num_alt - 1; i++)
1264     {
1265       const char *p;
1266       p = attr_numeral (i);
1267
1268       XVECEXP (condexp, 0, 2 * i) = attr_eq (alternative_name, p);
1269       XVECEXP (condexp, 0, 2 * i + 1) = XVECEXP (exp, 1, i);
1270     }
1271
1272   XEXP (condexp, 1) = XVECEXP (exp, 1, i);
1273
1274   return attr_rtx (SET, attr_rtx (ATTR, XSTR (exp, 0)), condexp);
1275 }
1276
1277 /* Given a SET_ATTR, convert to the appropriate SET.  If a comma-separated
1278    list of values is given, convert to SET_ATTR_ALTERNATIVE first.  */
1279
1280 static rtx
1281 convert_set_attr (rtx exp, struct insn_def *id)
1282 {
1283   rtx newexp;
1284   const char *name_ptr;
1285   char *p;
1286   int n;
1287
1288   /* See how many alternative specified.  */
1289   n = n_comma_elts (XSTR (exp, 1));
1290   if (n == 1)
1291     return attr_rtx (SET,
1292                      attr_rtx (ATTR, XSTR (exp, 0)),
1293                      attr_rtx (CONST_STRING, XSTR (exp, 1)));
1294
1295   newexp = rtx_alloc (SET_ATTR_ALTERNATIVE);
1296   XSTR (newexp, 0) = XSTR (exp, 0);
1297   XVEC (newexp, 1) = rtvec_alloc (n);
1298
1299   /* Process each comma-separated name.  */
1300   name_ptr = XSTR (exp, 1);
1301   n = 0;
1302   while ((p = next_comma_elt (&name_ptr)) != NULL)
1303     XVECEXP (newexp, 1, n++) = attr_rtx (CONST_STRING, p);
1304
1305   return convert_set_attr_alternative (newexp, id);
1306 }
1307
1308 /* Scan all definitions, checking for validity.  Also, convert any SET_ATTR
1309    and SET_ATTR_ALTERNATIVE expressions to the corresponding SET
1310    expressions.  */
1311
1312 static void
1313 check_defs (void)
1314 {
1315   struct insn_def *id;
1316   struct attr_desc *attr;
1317   int i;
1318   rtx value;
1319
1320   for (id = defs; id; id = id->next)
1321     {
1322       if (XVEC (id->def, id->vec_idx) == NULL)
1323         continue;
1324
1325       for (i = 0; i < XVECLEN (id->def, id->vec_idx); i++)
1326         {
1327           value = XVECEXP (id->def, id->vec_idx, i);
1328           switch (GET_CODE (value))
1329             {
1330             case SET:
1331               if (GET_CODE (XEXP (value, 0)) != ATTR)
1332                 {
1333                   message_with_line (id->lineno, "bad attribute set");
1334                   have_error = 1;
1335                   value = NULL_RTX;
1336                 }
1337               break;
1338
1339             case SET_ATTR_ALTERNATIVE:
1340               value = convert_set_attr_alternative (value, id);
1341               break;
1342
1343             case SET_ATTR:
1344               value = convert_set_attr (value, id);
1345               break;
1346
1347             default:
1348               message_with_line (id->lineno, "invalid attribute code %s",
1349                                  GET_RTX_NAME (GET_CODE (value)));
1350               have_error = 1;
1351               value = NULL_RTX;
1352             }
1353           if (value == NULL_RTX)
1354             continue;
1355
1356           if ((attr = find_attr (&XSTR (XEXP (value, 0), 0), 0)) == NULL)
1357             {
1358               message_with_line (id->lineno, "unknown attribute %s",
1359                                  XSTR (XEXP (value, 0), 0));
1360               have_error = 1;
1361               continue;
1362             }
1363
1364           XVECEXP (id->def, id->vec_idx, i) = value;
1365           XEXP (value, 1) = check_attr_value (XEXP (value, 1), attr);
1366         }
1367     }
1368 }
1369
1370 /* Given a valid expression for an attribute value, remove any IF_THEN_ELSE
1371    expressions by converting them into a COND.  This removes cases from this
1372    program.  Also, replace an attribute value of "*" with the default attribute
1373    value.  */
1374
1375 static rtx
1376 make_canonical (struct attr_desc *attr, rtx exp)
1377 {
1378   int i;
1379   rtx newexp;
1380
1381   switch (GET_CODE (exp))
1382     {
1383     case CONST_INT:
1384       exp = make_numeric_value (INTVAL (exp));
1385       break;
1386
1387     case CONST_STRING:
1388       if (! strcmp (XSTR (exp, 0), "*"))
1389         {
1390           if (attr == 0 || attr->default_val == 0)
1391             fatal ("(attr_value \"*\") used in invalid context");
1392           exp = attr->default_val->value;
1393         }
1394       else
1395         XSTR (exp, 0) = DEF_ATTR_STRING (XSTR (exp, 0));
1396
1397       break;
1398
1399     case SYMBOL_REF:
1400       if (!attr->is_const || ATTR_IND_SIMPLIFIED_P (exp))
1401         break;
1402       /* The SYMBOL_REF is constant for a given run, so mark it as unchanging.
1403          This makes the COND something that won't be considered an arbitrary
1404          expression by walk_attr_value.  */
1405       ATTR_IND_SIMPLIFIED_P (exp) = 1;
1406       exp = check_attr_value (exp, attr);
1407       break;
1408
1409     case IF_THEN_ELSE:
1410       newexp = rtx_alloc (COND);
1411       XVEC (newexp, 0) = rtvec_alloc (2);
1412       XVECEXP (newexp, 0, 0) = XEXP (exp, 0);
1413       XVECEXP (newexp, 0, 1) = XEXP (exp, 1);
1414
1415       XEXP (newexp, 1) = XEXP (exp, 2);
1416
1417       exp = newexp;
1418       /* Fall through to COND case since this is now a COND.  */
1419
1420     case COND:
1421       {
1422         int allsame = 1;
1423         rtx defval;
1424
1425         /* First, check for degenerate COND.  */
1426         if (XVECLEN (exp, 0) == 0)
1427           return make_canonical (attr, XEXP (exp, 1));
1428         defval = XEXP (exp, 1) = make_canonical (attr, XEXP (exp, 1));
1429
1430         for (i = 0; i < XVECLEN (exp, 0); i += 2)
1431           {
1432             XVECEXP (exp, 0, i) = copy_boolean (XVECEXP (exp, 0, i));
1433             XVECEXP (exp, 0, i + 1)
1434               = make_canonical (attr, XVECEXP (exp, 0, i + 1));
1435             if (! rtx_equal_p (XVECEXP (exp, 0, i + 1), defval))
1436               allsame = 0;
1437           }
1438         if (allsame)
1439           return defval;
1440       }
1441       break;
1442
1443     default:
1444       break;
1445     }
1446
1447   return exp;
1448 }
1449
1450 static rtx
1451 copy_boolean (rtx exp)
1452 {
1453   if (GET_CODE (exp) == AND || GET_CODE (exp) == IOR)
1454     return attr_rtx (GET_CODE (exp), copy_boolean (XEXP (exp, 0)),
1455                      copy_boolean (XEXP (exp, 1)));
1456   if (GET_CODE (exp) == MATCH_OPERAND)
1457     {
1458       XSTR (exp, 1) = DEF_ATTR_STRING (XSTR (exp, 1));
1459       XSTR (exp, 2) = DEF_ATTR_STRING (XSTR (exp, 2));
1460     }
1461   else if (GET_CODE (exp) == EQ_ATTR)
1462     {
1463       XSTR (exp, 0) = DEF_ATTR_STRING (XSTR (exp, 0));
1464       XSTR (exp, 1) = DEF_ATTR_STRING (XSTR (exp, 1));
1465     }
1466
1467   return exp;
1468 }
1469
1470 /* Given a value and an attribute description, return a `struct attr_value *'
1471    that represents that value.  This is either an existing structure, if the
1472    value has been previously encountered, or a newly-created structure.
1473
1474    `insn_code' is the code of an insn whose attribute has the specified
1475    value (-2 if not processing an insn).  We ensure that all insns for
1476    a given value have the same number of alternatives if the value checks
1477    alternatives.  */
1478
1479 static struct attr_value *
1480 get_attr_value (rtx value, struct attr_desc *attr, int insn_code)
1481 {
1482   struct attr_value *av;
1483   int num_alt = 0;
1484
1485   value = make_canonical (attr, value);
1486   if (compares_alternatives_p (value))
1487     {
1488       if (insn_code < 0 || insn_alternatives == NULL)
1489         fatal ("(eq_attr \"alternatives\" ...) used in non-insn context");
1490       else
1491         num_alt = insn_alternatives[insn_code];
1492     }
1493
1494   for (av = attr->first_value; av; av = av->next)
1495     if (rtx_equal_p (value, av->value)
1496         && (num_alt == 0 || av->first_insn == NULL
1497             || insn_alternatives[av->first_insn->insn_code]))
1498       return av;
1499
1500   av = oballoc (sizeof (struct attr_value));
1501   av->value = value;
1502   av->next = attr->first_value;
1503   attr->first_value = av;
1504   av->first_insn = NULL;
1505   av->num_insns = 0;
1506   av->has_asm_insn = 0;
1507
1508   return av;
1509 }
1510
1511 /* After all DEFINE_DELAYs have been read in, create internal attributes
1512    to generate the required routines.
1513
1514    First, we compute the number of delay slots for each insn (as a COND of
1515    each of the test expressions in DEFINE_DELAYs).  Then, if more than one
1516    delay type is specified, we compute a similar function giving the
1517    DEFINE_DELAY ordinal for each insn.
1518
1519    Finally, for each [DEFINE_DELAY, slot #] pair, we compute an attribute that
1520    tells whether a given insn can be in that delay slot.
1521
1522    Normal attribute filling and optimization expands these to contain the
1523    information needed to handle delay slots.  */
1524
1525 static void
1526 expand_delays (void)
1527 {
1528   struct delay_desc *delay;
1529   rtx condexp;
1530   rtx newexp;
1531   int i;
1532   char *p;
1533
1534   /* First, generate data for `num_delay_slots' function.  */
1535
1536   condexp = rtx_alloc (COND);
1537   XVEC (condexp, 0) = rtvec_alloc (num_delays * 2);
1538   XEXP (condexp, 1) = make_numeric_value (0);
1539
1540   for (i = 0, delay = delays; delay; i += 2, delay = delay->next)
1541     {
1542       XVECEXP (condexp, 0, i) = XEXP (delay->def, 0);
1543       XVECEXP (condexp, 0, i + 1)
1544         = make_numeric_value (XVECLEN (delay->def, 1) / 3);
1545     }
1546
1547   make_internal_attr (num_delay_slots_str, condexp, ATTR_NONE);
1548
1549   /* If more than one delay type, do the same for computing the delay type.  */
1550   if (num_delays > 1)
1551     {
1552       condexp = rtx_alloc (COND);
1553       XVEC (condexp, 0) = rtvec_alloc (num_delays * 2);
1554       XEXP (condexp, 1) = make_numeric_value (0);
1555
1556       for (i = 0, delay = delays; delay; i += 2, delay = delay->next)
1557         {
1558           XVECEXP (condexp, 0, i) = XEXP (delay->def, 0);
1559           XVECEXP (condexp, 0, i + 1) = make_numeric_value (delay->num);
1560         }
1561
1562       make_internal_attr (delay_type_str, condexp, ATTR_SPECIAL);
1563     }
1564
1565   /* For each delay possibility and delay slot, compute an eligibility
1566      attribute for non-annulled insns and for each type of annulled (annul
1567      if true and annul if false).  */
1568   for (delay = delays; delay; delay = delay->next)
1569     {
1570       for (i = 0; i < XVECLEN (delay->def, 1); i += 3)
1571         {
1572           condexp = XVECEXP (delay->def, 1, i);
1573           if (condexp == 0)
1574             condexp = false_rtx;
1575           newexp = attr_rtx (IF_THEN_ELSE, condexp,
1576                              make_numeric_value (1), make_numeric_value (0));
1577
1578           p = attr_printf (sizeof "*delay__" + MAX_DIGITS * 2,
1579                            "*delay_%d_%d", delay->num, i / 3);
1580           make_internal_attr (p, newexp, ATTR_SPECIAL);
1581
1582           if (have_annul_true)
1583             {
1584               condexp = XVECEXP (delay->def, 1, i + 1);
1585               if (condexp == 0) condexp = false_rtx;
1586               newexp = attr_rtx (IF_THEN_ELSE, condexp,
1587                                  make_numeric_value (1),
1588                                  make_numeric_value (0));
1589               p = attr_printf (sizeof "*annul_true__" + MAX_DIGITS * 2,
1590                                "*annul_true_%d_%d", delay->num, i / 3);
1591               make_internal_attr (p, newexp, ATTR_SPECIAL);
1592             }
1593
1594           if (have_annul_false)
1595             {
1596               condexp = XVECEXP (delay->def, 1, i + 2);
1597               if (condexp == 0) condexp = false_rtx;
1598               newexp = attr_rtx (IF_THEN_ELSE, condexp,
1599                                  make_numeric_value (1),
1600                                  make_numeric_value (0));
1601               p = attr_printf (sizeof "*annul_false__" + MAX_DIGITS * 2,
1602                                "*annul_false_%d_%d", delay->num, i / 3);
1603               make_internal_attr (p, newexp, ATTR_SPECIAL);
1604             }
1605         }
1606     }
1607 }
1608
1609 /* This function is given a left and right side expression and an operator.
1610    Each side is a conditional expression, each alternative of which has a
1611    numerical value.  The function returns another conditional expression
1612    which, for every possible set of condition values, returns a value that is
1613    the operator applied to the values of the two sides.
1614
1615    Since this is called early, it must also support IF_THEN_ELSE.  */
1616
1617 static rtx
1618 operate_exp (enum operator op, rtx left, rtx right)
1619 {
1620   int left_value, right_value;
1621   rtx newexp;
1622   int i;
1623
1624   /* If left is a string, apply operator to it and the right side.  */
1625   if (GET_CODE (left) == CONST_STRING)
1626     {
1627       /* If right is also a string, just perform the operation.  */
1628       if (GET_CODE (right) == CONST_STRING)
1629         {
1630           left_value = atoi (XSTR (left, 0));
1631           right_value = atoi (XSTR (right, 0));
1632           switch (op)
1633             {
1634             case PLUS_OP:
1635               i = left_value + right_value;
1636               break;
1637
1638             case MINUS_OP:
1639               i = left_value - right_value;
1640               break;
1641
1642             case POS_MINUS_OP:  /* The positive part of LEFT - RIGHT.  */
1643               if (left_value > right_value)
1644                 i = left_value - right_value;
1645               else
1646                 i = 0;
1647               break;
1648
1649             case OR_OP:
1650             case ORX_OP:
1651               i = left_value | right_value;
1652               break;
1653
1654             case EQ_OP:
1655               i = left_value == right_value;
1656               break;
1657
1658             case RANGE_OP:
1659               i = (left_value << (HOST_BITS_PER_INT / 2)) | right_value;
1660               break;
1661
1662             case MAX_OP:
1663               if (left_value > right_value)
1664                 i = left_value;
1665               else
1666                 i = right_value;
1667               break;
1668
1669             case MIN_OP:
1670               if (left_value < right_value)
1671                 i = left_value;
1672               else
1673                 i = right_value;
1674               break;
1675
1676             default:
1677               abort ();
1678             }
1679
1680           if (i == left_value)
1681             return left;
1682           if (i == right_value)
1683             return right;
1684           return make_numeric_value (i);
1685         }
1686       else if (GET_CODE (right) == IF_THEN_ELSE)
1687         {
1688           /* Apply recursively to all values within.  */
1689           rtx newleft = operate_exp (op, left, XEXP (right, 1));
1690           rtx newright = operate_exp (op, left, XEXP (right, 2));
1691           if (rtx_equal_p (newleft, newright))
1692             return newleft;
1693           return attr_rtx (IF_THEN_ELSE, XEXP (right, 0), newleft, newright);
1694         }
1695       else if (GET_CODE (right) == COND)
1696         {
1697           int allsame = 1;
1698           rtx defval;
1699
1700           newexp = rtx_alloc (COND);
1701           XVEC (newexp, 0) = rtvec_alloc (XVECLEN (right, 0));
1702           defval = XEXP (newexp, 1) = operate_exp (op, left, XEXP (right, 1));
1703
1704           for (i = 0; i < XVECLEN (right, 0); i += 2)
1705             {
1706               XVECEXP (newexp, 0, i) = XVECEXP (right, 0, i);
1707               XVECEXP (newexp, 0, i + 1)
1708                 = operate_exp (op, left, XVECEXP (right, 0, i + 1));
1709               if (! rtx_equal_p (XVECEXP (newexp, 0, i + 1),
1710                                  defval))
1711                 allsame = 0;
1712             }
1713
1714           /* If the resulting cond is trivial (all alternatives
1715              give the same value), optimize it away.  */
1716           if (allsame)
1717             return operate_exp (op, left, XEXP (right, 1));
1718
1719           return newexp;
1720         }
1721       else
1722         fatal ("badly formed attribute value");
1723     }
1724
1725   /* A hack to prevent expand_units from completely blowing up: ORX_OP does
1726      not associate through IF_THEN_ELSE.  */
1727   else if (op == ORX_OP && GET_CODE (right) == IF_THEN_ELSE)
1728     {
1729       return attr_rtx (IOR, left, right);
1730     }
1731
1732   /* Otherwise, do recursion the other way.  */
1733   else if (GET_CODE (left) == IF_THEN_ELSE)
1734     {
1735       rtx newleft = operate_exp (op, XEXP (left, 1), right);
1736       rtx newright = operate_exp (op, XEXP (left, 2), right);
1737       if (rtx_equal_p (newleft, newright))
1738         return newleft;
1739       return attr_rtx (IF_THEN_ELSE, XEXP (left, 0), newleft, newright);
1740     }
1741   else if (GET_CODE (left) == COND)
1742     {
1743       int allsame = 1;
1744       rtx defval;
1745
1746       newexp = rtx_alloc (COND);
1747       XVEC (newexp, 0) = rtvec_alloc (XVECLEN (left, 0));
1748       defval = XEXP (newexp, 1) = operate_exp (op, XEXP (left, 1), right);
1749
1750       for (i = 0; i < XVECLEN (left, 0); i += 2)
1751         {
1752           XVECEXP (newexp, 0, i) = XVECEXP (left, 0, i);
1753           XVECEXP (newexp, 0, i + 1)
1754             = operate_exp (op, XVECEXP (left, 0, i + 1), right);
1755           if (! rtx_equal_p (XVECEXP (newexp, 0, i + 1),
1756                              defval))
1757             allsame = 0;
1758         }
1759
1760       /* If the cond is trivial (all alternatives give the same value),
1761          optimize it away.  */
1762       if (allsame)
1763         return operate_exp (op, XEXP (left, 1), right);
1764
1765       /* If the result is the same as the LEFT operand,
1766          just use that.  */
1767       if (rtx_equal_p (newexp, left))
1768         return left;
1769
1770       return newexp;
1771     }
1772
1773   else
1774     fatal ("badly formed attribute value");
1775   /* NOTREACHED */
1776   return NULL;
1777 }
1778
1779 /* Once all attributes and DEFINE_FUNCTION_UNITs have been read, we
1780    construct a number of attributes.
1781
1782    The first produces a function `function_units_used' which is given an
1783    insn and produces an encoding showing which function units are required
1784    for the execution of that insn.  If the value is non-negative, the insn
1785    uses that unit; otherwise, the value is a one's complement mask of units
1786    used.
1787
1788    The second produces a function `result_ready_cost' which is used to
1789    determine the time that the result of an insn will be ready and hence
1790    a worst-case schedule.
1791
1792    Both of these produce quite complex expressions which are then set as the
1793    default value of internal attributes.  Normal attribute simplification
1794    should produce reasonable expressions.
1795
1796    For each unit, a `<name>_unit_ready_cost' function will take an
1797    insn and give the delay until that unit will be ready with the result
1798    and a `<name>_unit_conflict_cost' function is given an insn already
1799    executing on the unit and a candidate to execute and will give the
1800    cost from the time the executing insn started until the candidate
1801    can start (ignore limitations on the number of simultaneous insns).
1802
1803    For each unit, a `<name>_unit_blockage' function is given an insn
1804    already executing on the unit and a candidate to execute and will
1805    give the delay incurred due to function unit conflicts.  The range of
1806    blockage cost values for a given executing insn is given by the
1807    `<name>_unit_blockage_range' function.  These values are encoded in
1808    an int where the upper half gives the minimum value and the lower
1809    half gives the maximum value.  */
1810
1811 static void
1812 expand_units (void)
1813 {
1814   struct function_unit *unit, **unit_num;
1815   struct function_unit_op *op, **op_array, ***unit_ops;
1816   rtx unitsmask;
1817   rtx readycost;
1818   rtx newexp;
1819   const char *str;
1820   int i, j, u, num, nvalues;
1821
1822   /* Rebuild the condition for the unit to share the RTL expressions.
1823      Sharing is required by simplify_by_exploding.  Build the issue delay
1824      expressions.  Validate the expressions we were given for the conditions
1825      and conflict vector.  Then make attributes for use in the conflict
1826      function.  */
1827
1828   for (unit = units; unit; unit = unit->next)
1829     {
1830       unit->condexp = check_attr_test (unit->condexp, 0, unit->first_lineno);
1831
1832       for (op = unit->ops; op; op = op->next)
1833         {
1834           rtx issue_delay = make_numeric_value (op->issue_delay);
1835           rtx issue_exp = issue_delay;
1836
1837           /* Build, validate, and simplify the issue delay expression.  */
1838           if (op->conflict_exp != true_rtx)
1839             issue_exp = attr_rtx (IF_THEN_ELSE, op->conflict_exp,
1840                                   issue_exp, make_numeric_value (0));
1841           issue_exp = check_attr_value (make_canonical (NULL_ATTR,
1842                                                         issue_exp),
1843                                         NULL_ATTR);
1844           issue_exp = simplify_knowing (issue_exp, unit->condexp);
1845           op->issue_exp = issue_exp;
1846
1847           /* Make an attribute for use in the conflict function if needed.  */
1848           unit->needs_conflict_function = (unit->issue_delay.min
1849                                            != unit->issue_delay.max);
1850           if (unit->needs_conflict_function)
1851             {
1852               str = attr_printf ((strlen (unit->name) + sizeof "*_cost_"
1853                                   + MAX_DIGITS),
1854                                  "*%s_cost_%d", unit->name, op->num);
1855               make_internal_attr (str, issue_exp, ATTR_SPECIAL);
1856             }
1857
1858           /* Validate the condition.  */
1859           op->condexp = check_attr_test (op->condexp, 0, op->lineno);
1860         }
1861     }
1862
1863   /* Compute the mask of function units used.  Initially, the unitsmask is
1864      zero.   Set up a conditional to compute each unit's contribution.  */
1865   unitsmask = make_numeric_value (0);
1866   newexp = rtx_alloc (IF_THEN_ELSE);
1867   XEXP (newexp, 2) = make_numeric_value (0);
1868
1869   /* If we have just a few units, we may be all right expanding the whole
1870      thing.  But the expansion is 2**N in space on the number of opclasses,
1871      so we can't do this for very long -- Alpha and MIPS in particular have
1872      problems with this.  So in that situation, we fall back on an alternate
1873      implementation method.  */
1874 #define NUM_UNITOP_CUTOFF 20
1875
1876   if (num_unit_opclasses < NUM_UNITOP_CUTOFF)
1877     {
1878       /* Merge each function unit into the unit mask attributes.  */
1879       for (unit = units; unit; unit = unit->next)
1880         {
1881           XEXP (newexp, 0) = unit->condexp;
1882           XEXP (newexp, 1) = make_numeric_value (1 << unit->num);
1883           unitsmask = operate_exp (OR_OP, unitsmask, newexp);
1884         }
1885     }
1886   else
1887     {
1888       /* Merge each function unit into the unit mask attributes.  */
1889       for (unit = units; unit; unit = unit->next)
1890         {
1891           XEXP (newexp, 0) = unit->condexp;
1892           XEXP (newexp, 1) = make_numeric_value (1 << unit->num);
1893           unitsmask = operate_exp (ORX_OP, unitsmask, attr_copy_rtx (newexp));
1894         }
1895     }
1896
1897   /* Simplify the unit mask expression, encode it, and make an attribute
1898      for the function_units_used function.  */
1899   unitsmask = simplify_by_exploding (unitsmask);
1900
1901   if (num_unit_opclasses < NUM_UNITOP_CUTOFF)
1902     unitsmask = encode_units_mask (unitsmask);
1903   else
1904     {
1905       /* We can no longer encode unitsmask at compile time, so emit code to
1906          calculate it at runtime.  Rather, put a marker for where we'd do
1907          the code, and actually output it in write_attr_get().  */
1908       unitsmask = attr_rtx (FFS, unitsmask);
1909     }
1910
1911   make_internal_attr ("*function_units_used", unitsmask,
1912                       (ATTR_NEGATIVE_OK | ATTR_FUNC_UNITS));
1913
1914   /* Create an array of ops for each unit.  Add an extra unit for the
1915      result_ready_cost function that has the ops of all other units.  */
1916   unit_ops = xmalloc ((num_units + 1) * sizeof (struct function_unit_op **));
1917   unit_num = xmalloc ((num_units + 1) * sizeof (struct function_unit *));
1918
1919   unit_num[num_units] = unit = xmalloc (sizeof (struct function_unit));
1920   unit->num = num_units;
1921   unit->num_opclasses = 0;
1922
1923   for (unit = units; unit; unit = unit->next)
1924     {
1925       unit_num[num_units]->num_opclasses += unit->num_opclasses;
1926       unit_num[unit->num] = unit;
1927       unit_ops[unit->num] = op_array =
1928         xmalloc (unit->num_opclasses * sizeof (struct function_unit_op *));
1929
1930       for (op = unit->ops; op; op = op->next)
1931         op_array[op->num] = op;
1932     }
1933
1934   /* Compose the array of ops for the extra unit.  */
1935   unit_ops[num_units] = op_array =
1936     xmalloc (unit_num[num_units]->num_opclasses
1937             * sizeof (struct function_unit_op *));
1938
1939   for (unit = units, i = 0; unit; i += unit->num_opclasses, unit = unit->next)
1940     memcpy (&op_array[i], unit_ops[unit->num],
1941             unit->num_opclasses * sizeof (struct function_unit_op *));
1942
1943   /* Compute the ready cost function for each unit by computing the
1944      condition for each non-default value.  */
1945   for (u = 0; u <= num_units; u++)
1946     {
1947       rtx orexp;
1948       int value;
1949
1950       unit = unit_num[u];
1951       op_array = unit_ops[unit->num];
1952       num = unit->num_opclasses;
1953
1954       /* Sort the array of ops into increasing ready cost order.  */
1955       for (i = 0; i < num; i++)
1956         for (j = num - 1; j > i; j--)
1957           if (op_array[j - 1]->ready < op_array[j]->ready)
1958             {
1959               op = op_array[j];
1960               op_array[j] = op_array[j - 1];
1961               op_array[j - 1] = op;
1962             }
1963
1964       /* Determine how many distinct non-default ready cost values there
1965          are.  We use a default ready cost value of 1.  */
1966       nvalues = 0; value = 1;
1967       for (i = num - 1; i >= 0; i--)
1968         if (op_array[i]->ready > value)
1969           {
1970             value = op_array[i]->ready;
1971             nvalues++;
1972           }
1973
1974       if (nvalues == 0)
1975         readycost = make_numeric_value (1);
1976       else
1977         {
1978           /* Construct the ready cost expression as a COND of each value from
1979              the largest to the smallest.  */
1980           readycost = rtx_alloc (COND);
1981           XVEC (readycost, 0) = rtvec_alloc (nvalues * 2);
1982           XEXP (readycost, 1) = make_numeric_value (1);
1983
1984           nvalues = 0;
1985           orexp = false_rtx;
1986           value = op_array[0]->ready;
1987           for (i = 0; i < num; i++)
1988             {
1989               op = op_array[i];
1990               if (op->ready <= 1)
1991                 break;
1992               else if (op->ready == value)
1993                 orexp = insert_right_side (IOR, orexp, op->condexp, -2, -2);
1994               else
1995                 {
1996                   XVECEXP (readycost, 0, nvalues * 2) = orexp;
1997                   XVECEXP (readycost, 0, nvalues * 2 + 1)
1998                     = make_numeric_value (value);
1999                   nvalues++;
2000                   value = op->ready;
2001                   orexp = op->condexp;
2002                 }
2003             }
2004           XVECEXP (readycost, 0, nvalues * 2) = orexp;
2005           XVECEXP (readycost, 0, nvalues * 2 + 1) = make_numeric_value (value);
2006         }
2007
2008       if (u < num_units)
2009         {
2010           rtx max_blockage = 0, min_blockage = 0;
2011
2012           /* Simplify the readycost expression by only considering insns
2013              that use the unit.  */
2014           readycost = simplify_knowing (readycost, unit->condexp);
2015
2016           /* Determine the blockage cost the executing insn (E) given
2017              the candidate insn (C).  This is the maximum of the issue
2018              delay, the pipeline delay, and the simultaneity constraint.
2019              Each function_unit_op represents the characteristics of the
2020              candidate insn, so in the expressions below, C is a known
2021              term and E is an unknown term.
2022
2023              We compute the blockage cost for each E for every possible C.
2024              Thus OP represents E, and READYCOST is a list of values for
2025              every possible C.
2026
2027              The issue delay function for C is op->issue_exp and is used to
2028              write the `<name>_unit_conflict_cost' function.  Symbolically
2029              this is "ISSUE-DELAY (E,C)".
2030
2031              The pipeline delay results form the FIFO constraint on the
2032              function unit and is "READY-COST (E) + 1 - READY-COST (C)".
2033
2034              The simultaneity constraint is based on how long it takes to
2035              fill the unit given the minimum issue delay.  FILL-TIME is the
2036              constant "MIN (ISSUE-DELAY (*,*)) * (SIMULTANEITY - 1)", and
2037              the simultaneity constraint is "READY-COST (E) - FILL-TIME"
2038              if SIMULTANEITY is nonzero and zero otherwise.
2039
2040              Thus, BLOCKAGE (E,C) when SIMULTANEITY is zero is
2041
2042                  MAX (ISSUE-DELAY (E,C),
2043                       READY-COST (E) - (READY-COST (C) - 1))
2044
2045              and otherwise
2046
2047                  MAX (ISSUE-DELAY (E,C),
2048                       READY-COST (E) - (READY-COST (C) - 1),
2049                       READY-COST (E) - FILL-TIME)
2050
2051              The `<name>_unit_blockage' function is computed by determining
2052              this value for each candidate insn.  As these values are
2053              computed, we also compute the upper and lower bounds for
2054              BLOCKAGE (E,*).  These are combined to form the function
2055              `<name>_unit_blockage_range'.  Finally, the maximum blockage
2056              cost, MAX (BLOCKAGE (*,*)), is computed.  */
2057
2058           for (op = unit->ops; op; op = op->next)
2059             {
2060               rtx blockage = op->issue_exp;
2061               blockage = simplify_knowing (blockage, unit->condexp);
2062
2063               /* Add this op's contribution to MAX (BLOCKAGE (E,*)) and
2064                  MIN (BLOCKAGE (E,*)).  */
2065               if (max_blockage == 0)
2066                 max_blockage = min_blockage = blockage;
2067               else
2068                 {
2069                   max_blockage
2070                     = simplify_knowing (operate_exp (MAX_OP, max_blockage,
2071                                                      blockage),
2072                                         unit->condexp);
2073                   min_blockage
2074                     = simplify_knowing (operate_exp (MIN_OP, min_blockage,
2075                                                      blockage),
2076                                         unit->condexp);
2077                 }
2078
2079               /* Make an attribute for use in the blockage function.  */
2080               str = attr_printf ((strlen (unit->name) + sizeof "*_block_"
2081                                   + MAX_DIGITS),
2082                                  "*%s_block_%d", unit->name, op->num);
2083               make_internal_attr (str, blockage, ATTR_SPECIAL);
2084             }
2085
2086           /* Record MAX (BLOCKAGE (*,*)).  */
2087           {
2088             int unknown;
2089             unit->max_blockage = max_attr_value (max_blockage, &unknown);
2090           }
2091
2092           /* See if the upper and lower bounds of BLOCKAGE (E,*) are the
2093              same.  If so, the blockage function carries no additional
2094              information and is not written.  */
2095           newexp = operate_exp (EQ_OP, max_blockage, min_blockage);
2096           newexp = simplify_knowing (newexp, unit->condexp);
2097           unit->needs_blockage_function
2098             = (GET_CODE (newexp) != CONST_STRING
2099                || atoi (XSTR (newexp, 0)) != 1);
2100
2101           /* If the all values of BLOCKAGE (E,C) have the same value,
2102              neither blockage function is written.  */
2103           unit->needs_range_function
2104             = (unit->needs_blockage_function
2105                || GET_CODE (max_blockage) != CONST_STRING);
2106
2107           if (unit->needs_range_function)
2108             {
2109               /* Compute the blockage range function and make an attribute
2110                  for writing its value.  */
2111               newexp = operate_exp (RANGE_OP, min_blockage, max_blockage);
2112               newexp = simplify_knowing (newexp, unit->condexp);
2113
2114               str = attr_printf ((strlen (unit->name)
2115                                   + sizeof "*_unit_blockage_range"),
2116                                  "*%s_unit_blockage_range", unit->name);
2117               make_internal_attr (str, newexp, (ATTR_STATIC|ATTR_BLOCKAGE|ATTR_UNSIGNED));
2118             }
2119
2120           str = attr_printf (strlen (unit->name) + sizeof "*_unit_ready_cost",
2121                              "*%s_unit_ready_cost", unit->name);
2122           make_internal_attr (str, readycost, ATTR_STATIC);
2123         }
2124       else
2125         {
2126           /* Make an attribute for the ready_cost function.  Simplifying
2127              further with simplify_by_exploding doesn't win.  */
2128           str = "*result_ready_cost";
2129           make_internal_attr (str, readycost, ATTR_NONE);
2130         }
2131     }
2132
2133   /* For each unit that requires a conflict cost function, make an attribute
2134      that maps insns to the operation number.  */
2135   for (unit = units; unit; unit = unit->next)
2136     {
2137       rtx caseexp;
2138
2139       if (! unit->needs_conflict_function
2140           && ! unit->needs_blockage_function)
2141         continue;
2142
2143       caseexp = rtx_alloc (COND);
2144       XVEC (caseexp, 0) = rtvec_alloc ((unit->num_opclasses - 1) * 2);
2145
2146       for (op = unit->ops; op; op = op->next)
2147         {
2148           /* Make our adjustment to the COND being computed.  If we are the
2149              last operation class, place our values into the default of the
2150              COND.  */
2151           if (op->num == unit->num_opclasses - 1)
2152             {
2153               XEXP (caseexp, 1) = make_numeric_value (op->num);
2154             }
2155           else
2156             {
2157               XVECEXP (caseexp, 0, op->num * 2) = op->condexp;
2158               XVECEXP (caseexp, 0, op->num * 2 + 1)
2159                 = make_numeric_value (op->num);
2160             }
2161         }
2162
2163       /* Simplifying caseexp with simplify_by_exploding doesn't win.  */
2164       str = attr_printf (strlen (unit->name) + sizeof "*_cases",
2165                          "*%s_cases", unit->name);
2166       make_internal_attr (str, caseexp, ATTR_SPECIAL);
2167     }
2168 }
2169
2170 /* Simplify EXP given KNOWN_TRUE.  */
2171
2172 static rtx
2173 simplify_knowing (rtx exp, rtx known_true)
2174 {
2175   if (GET_CODE (exp) != CONST_STRING)
2176     {
2177       int unknown = 0, max;
2178       max = max_attr_value (exp, &unknown);
2179       if (! unknown)
2180         {
2181           exp = attr_rtx (IF_THEN_ELSE, known_true, exp,
2182                           make_numeric_value (max));
2183           exp = simplify_by_exploding (exp);
2184         }
2185     }
2186   return exp;
2187 }
2188
2189 /* Translate the CONST_STRING expressions in X to change the encoding of
2190    value.  On input, the value is a bitmask with a one bit for each unit
2191    used; on output, the value is the unit number (zero based) if one
2192    and only one unit is used or the one's complement of the bitmask.  */
2193
2194 static rtx
2195 encode_units_mask (rtx x)
2196 {
2197   int i;
2198   int j;
2199   enum rtx_code code;
2200   const char *fmt;
2201
2202   code = GET_CODE (x);
2203
2204   switch (code)
2205     {
2206     case CONST_STRING:
2207       i = atoi (XSTR (x, 0));
2208       if (i < 0)
2209         /* The sign bit encodes a one's complement mask.  */
2210         abort ();
2211       else if (i != 0 && i == (i & -i))
2212         /* Only one bit is set, so yield that unit number.  */
2213         for (j = 0; (i >>= 1) != 0; j++)
2214           ;
2215       else
2216         j = ~i;
2217       return attr_rtx (CONST_STRING, attr_printf (MAX_DIGITS, "%d", j));
2218
2219     case REG:
2220     case CONST_INT:
2221     case CONST_DOUBLE:
2222     case CONST_VECTOR:
2223     case SYMBOL_REF:
2224     case CODE_LABEL:
2225     case PC:
2226     case CC0:
2227     case EQ_ATTR:
2228     case EQ_ATTR_ALT:
2229       return x;
2230
2231     default:
2232       break;
2233     }
2234
2235   /* Compare the elements.  If any pair of corresponding elements
2236      fail to match, return 0 for the whole things.  */
2237
2238   fmt = GET_RTX_FORMAT (code);
2239   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2240     {
2241       switch (fmt[i])
2242         {
2243         case 'V':
2244         case 'E':
2245           for (j = 0; j < XVECLEN (x, i); j++)
2246             XVECEXP (x, i, j) = encode_units_mask (XVECEXP (x, i, j));
2247           break;
2248
2249         case 'e':
2250           XEXP (x, i) = encode_units_mask (XEXP (x, i));
2251           break;
2252         }
2253     }
2254   return x;
2255 }
2256
2257 /* Once all attributes and insns have been read and checked, we construct for
2258    each attribute value a list of all the insns that have that value for
2259    the attribute.  */
2260
2261 static void
2262 fill_attr (struct attr_desc *attr)
2263 {
2264   struct attr_value *av;
2265   struct insn_ent *ie;
2266   struct insn_def *id;
2267   int i;
2268   rtx value;
2269
2270   /* Don't fill constant attributes.  The value is independent of
2271      any particular insn.  */
2272   if (attr->is_const)
2273     return;
2274
2275   for (id = defs; id; id = id->next)
2276     {
2277       /* If no value is specified for this insn for this attribute, use the
2278          default.  */
2279       value = NULL;
2280       if (XVEC (id->def, id->vec_idx))
2281         for (i = 0; i < XVECLEN (id->def, id->vec_idx); i++)
2282           if (! strcmp_check (XSTR (XEXP (XVECEXP (id->def, id->vec_idx, i), 0), 0),
2283                               attr->name))
2284             value = XEXP (XVECEXP (id->def, id->vec_idx, i), 1);
2285
2286       if (value == NULL)
2287         av = attr->default_val;
2288       else
2289         av = get_attr_value (value, attr, id->insn_code);
2290
2291       ie = oballoc (sizeof (struct insn_ent));
2292       ie->insn_code = id->insn_code;
2293       ie->insn_index = id->insn_code;
2294       insert_insn_ent (av, ie);
2295     }
2296 }
2297
2298 /* Given an expression EXP, see if it is a COND or IF_THEN_ELSE that has a
2299    test that checks relative positions of insns (uses MATCH_DUP or PC).
2300    If so, replace it with what is obtained by passing the expression to
2301    ADDRESS_FN.  If not but it is a COND or IF_THEN_ELSE, call this routine
2302    recursively on each value (including the default value).  Otherwise,
2303    return the value returned by NO_ADDRESS_FN applied to EXP.  */
2304
2305 static rtx
2306 substitute_address (rtx exp, rtx (*no_address_fn) (rtx),
2307                     rtx (*address_fn) (rtx))
2308 {
2309   int i;
2310   rtx newexp;
2311
2312   if (GET_CODE (exp) == COND)
2313     {
2314       /* See if any tests use addresses.  */
2315       address_used = 0;
2316       for (i = 0; i < XVECLEN (exp, 0); i += 2)
2317         walk_attr_value (XVECEXP (exp, 0, i));
2318
2319       if (address_used)
2320         return (*address_fn) (exp);
2321
2322       /* Make a new copy of this COND, replacing each element.  */
2323       newexp = rtx_alloc (COND);
2324       XVEC (newexp, 0) = rtvec_alloc (XVECLEN (exp, 0));
2325       for (i = 0; i < XVECLEN (exp, 0); i += 2)
2326         {
2327           XVECEXP (newexp, 0, i) = XVECEXP (exp, 0, i);
2328           XVECEXP (newexp, 0, i + 1)
2329             = substitute_address (XVECEXP (exp, 0, i + 1),
2330                                   no_address_fn, address_fn);
2331         }
2332
2333       XEXP (newexp, 1) = substitute_address (XEXP (exp, 1),
2334                                              no_address_fn, address_fn);
2335
2336       return newexp;
2337     }
2338
2339   else if (GET_CODE (exp) == IF_THEN_ELSE)
2340     {
2341       address_used = 0;
2342       walk_attr_value (XEXP (exp, 0));
2343       if (address_used)
2344         return (*address_fn) (exp);
2345
2346       return attr_rtx (IF_THEN_ELSE,
2347                        substitute_address (XEXP (exp, 0),
2348                                            no_address_fn, address_fn),
2349                        substitute_address (XEXP (exp, 1),
2350                                            no_address_fn, address_fn),
2351                        substitute_address (XEXP (exp, 2),
2352                                            no_address_fn, address_fn));
2353     }
2354
2355   return (*no_address_fn) (exp);
2356 }
2357
2358 /* Make new attributes from the `length' attribute.  The following are made,
2359    each corresponding to a function called from `shorten_branches' or
2360    `get_attr_length':
2361
2362    *insn_default_length         This is the length of the insn to be returned
2363                                 by `get_attr_length' before `shorten_branches'
2364                                 has been called.  In each case where the length
2365                                 depends on relative addresses, the largest
2366                                 possible is used.  This routine is also used
2367                                 to compute the initial size of the insn.
2368
2369    *insn_variable_length_p      This returns 1 if the insn's length depends
2370                                 on relative addresses, zero otherwise.
2371
2372    *insn_current_length         This is only called when it is known that the
2373                                 insn has a variable length and returns the
2374                                 current length, based on relative addresses.
2375   */
2376
2377 static void
2378 make_length_attrs (void)
2379 {
2380   static const char *new_names[] =
2381     {
2382       "*insn_default_length",
2383       "*insn_variable_length_p",
2384       "*insn_current_length"
2385     };
2386   static rtx (*const no_address_fn[]) (rtx) = {identity_fn, zero_fn, zero_fn};
2387   static rtx (*const address_fn[]) (rtx) = {max_fn, one_fn, identity_fn};
2388   size_t i;
2389   struct attr_desc *length_attr, *new_attr;
2390   struct attr_value *av, *new_av;
2391   struct insn_ent *ie, *new_ie;
2392
2393   /* See if length attribute is defined.  If so, it must be numeric.  Make
2394      it special so we don't output anything for it.  */
2395   length_attr = find_attr (&length_str, 0);
2396   if (length_attr == 0)
2397     return;
2398
2399   if (! length_attr->is_numeric)
2400     fatal ("length attribute must be numeric");
2401
2402   length_attr->is_const = 0;
2403   length_attr->is_special = 1;
2404
2405   /* Make each new attribute, in turn.  */
2406   for (i = 0; i < ARRAY_SIZE (new_names); i++)
2407     {
2408       make_internal_attr (new_names[i],
2409                           substitute_address (length_attr->default_val->value,
2410                                               no_address_fn[i], address_fn[i]),
2411                           ATTR_NONE);
2412       new_attr = find_attr (&new_names[i], 0);
2413       for (av = length_attr->first_value; av; av = av->next)
2414         for (ie = av->first_insn; ie; ie = ie->next)
2415           {
2416             new_av = get_attr_value (substitute_address (av->value,
2417                                                          no_address_fn[i],
2418                                                          address_fn[i]),
2419                                      new_attr, ie->insn_code);
2420             new_ie = oballoc (sizeof (struct insn_ent));
2421             new_ie->insn_code = ie->insn_code;
2422             new_ie->insn_index = ie->insn_index;
2423             insert_insn_ent (new_av, new_ie);
2424           }
2425     }
2426 }
2427
2428 /* Utility functions called from above routine.  */
2429
2430 static rtx
2431 identity_fn (rtx exp)
2432 {
2433   return exp;
2434 }
2435
2436 static rtx
2437 zero_fn (rtx exp ATTRIBUTE_UNUSED)
2438 {
2439   return make_numeric_value (0);
2440 }
2441
2442 static rtx
2443 one_fn (rtx exp ATTRIBUTE_UNUSED)
2444 {
2445   return make_numeric_value (1);
2446 }
2447
2448 static rtx
2449 max_fn (rtx exp)
2450 {
2451   int unknown;
2452   return make_numeric_value (max_attr_value (exp, &unknown));
2453 }
2454
2455 static void
2456 write_length_unit_log (void)
2457 {
2458   struct attr_desc *length_attr = find_attr (&length_str, 0);
2459   struct attr_value *av;
2460   struct insn_ent *ie;
2461   unsigned int length_unit_log, length_or;
2462   int unknown = 0;
2463
2464   if (length_attr == 0)
2465     return;
2466   length_or = or_attr_value (length_attr->default_val->value, &unknown);
2467   for (av = length_attr->first_value; av; av = av->next)
2468     for (ie = av->first_insn; ie; ie = ie->next)
2469       length_or |= or_attr_value (av->value, &unknown);
2470
2471   if (unknown)
2472     length_unit_log = 0;
2473   else
2474     {
2475       length_or = ~length_or;
2476       for (length_unit_log = 0; length_or & 1; length_or >>= 1)
2477         length_unit_log++;
2478     }
2479   printf ("int length_unit_log = %u;\n", length_unit_log);
2480 }
2481
2482 /* Take a COND expression and see if any of the conditions in it can be
2483    simplified.  If any are known true or known false for the particular insn
2484    code, the COND can be further simplified.
2485
2486    Also call ourselves on any COND operations that are values of this COND.
2487
2488    We do not modify EXP; rather, we make and return a new rtx.  */
2489
2490 static rtx
2491 simplify_cond (rtx exp, int insn_code, int insn_index)
2492 {
2493   int i, j;
2494   /* We store the desired contents here,
2495      then build a new expression if they don't match EXP.  */
2496   rtx defval = XEXP (exp, 1);
2497   rtx new_defval = XEXP (exp, 1);
2498   int len = XVECLEN (exp, 0);
2499   rtx *tests = xmalloc (len * sizeof (rtx));
2500   int allsame = 1;
2501   rtx ret;
2502
2503   /* This lets us free all storage allocated below, if appropriate.  */
2504   obstack_finish (rtl_obstack);
2505
2506   memcpy (tests, XVEC (exp, 0)->elem, len * sizeof (rtx));
2507
2508   /* See if default value needs simplification.  */
2509   if (GET_CODE (defval) == COND)
2510     new_defval = simplify_cond (defval, insn_code, insn_index);
2511
2512   /* Simplify the subexpressions, and see what tests we can get rid of.  */
2513
2514   for (i = 0; i < len; i += 2)
2515     {
2516       rtx newtest, newval;
2517
2518       /* Simplify this test.  */
2519       newtest = simplify_test_exp_in_temp (tests[i], insn_code, insn_index);
2520       tests[i] = newtest;
2521
2522       newval = tests[i + 1];
2523       /* See if this value may need simplification.  */
2524       if (GET_CODE (newval) == COND)
2525         newval = simplify_cond (newval, insn_code, insn_index);
2526
2527       /* Look for ways to delete or combine this test.  */
2528       if (newtest == true_rtx)
2529         {
2530           /* If test is true, make this value the default
2531              and discard this + any following tests.  */
2532           len = i;
2533           defval = tests[i + 1];
2534           new_defval = newval;
2535         }
2536
2537       else if (newtest == false_rtx)
2538         {
2539           /* If test is false, discard it and its value.  */
2540           for (j = i; j < len - 2; j++)
2541             tests[j] = tests[j + 2];
2542           i -= 2;
2543           len -= 2;
2544         }
2545
2546       else if (i > 0 && attr_equal_p (newval, tests[i - 1]))
2547         {
2548           /* If this value and the value for the prev test are the same,
2549              merge the tests.  */
2550
2551           tests[i - 2]
2552             = insert_right_side (IOR, tests[i - 2], newtest,
2553                                  insn_code, insn_index);
2554
2555           /* Delete this test/value.  */
2556           for (j = i; j < len - 2; j++)
2557             tests[j] = tests[j + 2];
2558           len -= 2;
2559           i -= 2;
2560         }
2561
2562       else
2563         tests[i + 1] = newval;
2564     }
2565
2566   /* If the last test in a COND has the same value
2567      as the default value, that test isn't needed.  */
2568
2569   while (len > 0 && attr_equal_p (tests[len - 1], new_defval))
2570     len -= 2;
2571
2572   /* See if we changed anything.  */
2573   if (len != XVECLEN (exp, 0) || new_defval != XEXP (exp, 1))
2574     allsame = 0;
2575   else
2576     for (i = 0; i < len; i++)
2577       if (! attr_equal_p (tests[i], XVECEXP (exp, 0, i)))
2578         {
2579           allsame = 0;
2580           break;
2581         }
2582
2583   if (len == 0)
2584     {
2585       if (GET_CODE (defval) == COND)
2586         ret = simplify_cond (defval, insn_code, insn_index);
2587       else
2588         ret = defval;
2589     }
2590   else if (allsame)
2591     ret = exp;
2592   else
2593     {
2594       rtx newexp = rtx_alloc (COND);
2595
2596       XVEC (newexp, 0) = rtvec_alloc (len);
2597       memcpy (XVEC (newexp, 0)->elem, tests, len * sizeof (rtx));
2598       XEXP (newexp, 1) = new_defval;
2599       ret = newexp;
2600     }
2601   free (tests);
2602   return ret;
2603 }
2604
2605 /* Remove an insn entry from an attribute value.  */
2606
2607 static void
2608 remove_insn_ent (struct attr_value *av, struct insn_ent *ie)
2609 {
2610   struct insn_ent *previe;
2611
2612   if (av->first_insn == ie)
2613     av->first_insn = ie->next;
2614   else
2615     {
2616       for (previe = av->first_insn; previe->next != ie; previe = previe->next)
2617         ;
2618       previe->next = ie->next;
2619     }
2620
2621   av->num_insns--;
2622   if (ie->insn_code == -1)
2623     av->has_asm_insn = 0;
2624
2625   num_insn_ents--;
2626 }
2627
2628 /* Insert an insn entry in an attribute value list.  */
2629
2630 static void
2631 insert_insn_ent (struct attr_value *av, struct insn_ent *ie)
2632 {
2633   ie->next = av->first_insn;
2634   av->first_insn = ie;
2635   av->num_insns++;
2636   if (ie->insn_code == -1)
2637     av->has_asm_insn = 1;
2638
2639   num_insn_ents++;
2640 }
2641
2642 /* This is a utility routine to take an expression that is a tree of either
2643    AND or IOR expressions and insert a new term.  The new term will be
2644    inserted at the right side of the first node whose code does not match
2645    the root.  A new node will be created with the root's code.  Its left
2646    side will be the old right side and its right side will be the new
2647    term.
2648
2649    If the `term' is itself a tree, all its leaves will be inserted.  */
2650
2651 static rtx
2652 insert_right_side (enum rtx_code code, rtx exp, rtx term, int insn_code, int insn_index)
2653 {
2654   rtx newexp;
2655
2656   /* Avoid consing in some special cases.  */
2657   if (code == AND && term == true_rtx)
2658     return exp;
2659   if (code == AND && term == false_rtx)
2660     return false_rtx;
2661   if (code == AND && exp == true_rtx)
2662     return term;
2663   if (code == AND && exp == false_rtx)
2664     return false_rtx;
2665   if (code == IOR && term == true_rtx)
2666     return true_rtx;
2667   if (code == IOR && term == false_rtx)
2668     return exp;
2669   if (code == IOR && exp == true_rtx)
2670     return true_rtx;
2671   if (code == IOR && exp == false_rtx)
2672     return term;
2673   if (attr_equal_p (exp, term))
2674     return exp;
2675
2676   if (GET_CODE (term) == code)
2677     {
2678       exp = insert_right_side (code, exp, XEXP (term, 0),
2679                                insn_code, insn_index);
2680       exp = insert_right_side (code, exp, XEXP (term, 1),
2681                                insn_code, insn_index);
2682
2683       return exp;
2684     }
2685
2686   if (GET_CODE (exp) == code)
2687     {
2688       rtx new = insert_right_side (code, XEXP (exp, 1),
2689                                    term, insn_code, insn_index);
2690       if (new != XEXP (exp, 1))
2691         /* Make a copy of this expression and call recursively.  */
2692         newexp = attr_rtx (code, XEXP (exp, 0), new);
2693       else
2694         newexp = exp;
2695     }
2696   else
2697     {
2698       /* Insert the new term.  */
2699       newexp = attr_rtx (code, exp, term);
2700     }
2701
2702   return simplify_test_exp_in_temp (newexp, insn_code, insn_index);
2703 }
2704
2705 /* If we have an expression which AND's a bunch of
2706         (not (eq_attrq "alternative" "n"))
2707    terms, we may have covered all or all but one of the possible alternatives.
2708    If so, we can optimize.  Similarly for IOR's of EQ_ATTR.
2709
2710    This routine is passed an expression and either AND or IOR.  It returns a
2711    bitmask indicating which alternatives are mentioned within EXP.  */
2712
2713 static int
2714 compute_alternative_mask (rtx exp, enum rtx_code code)
2715 {
2716   const char *string;
2717   if (GET_CODE (exp) == code)
2718     return compute_alternative_mask (XEXP (exp, 0), code)
2719            | compute_alternative_mask (XEXP (exp, 1), code);
2720
2721   else if (code == AND && GET_CODE (exp) == NOT
2722            && GET_CODE (XEXP (exp, 0)) == EQ_ATTR
2723            && XSTR (XEXP (exp, 0), 0) == alternative_name)
2724     string = XSTR (XEXP (exp, 0), 1);
2725
2726   else if (code == IOR && GET_CODE (exp) == EQ_ATTR
2727            && XSTR (exp, 0) == alternative_name)
2728     string = XSTR (exp, 1);
2729
2730   else if (GET_CODE (exp) == EQ_ATTR_ALT)
2731     {
2732       if (code == AND && XINT (exp, 1))
2733         return XINT (exp, 0);
2734
2735       if (code == IOR && !XINT (exp, 1))
2736         return XINT (exp, 0);
2737
2738       return 0;
2739     }
2740   else
2741     return 0;
2742
2743   if (string[1] == 0)
2744     return 1 << (string[0] - '0');
2745   return 1 << atoi (string);
2746 }
2747
2748 /* Given I, a single-bit mask, return RTX to compare the `alternative'
2749    attribute with the value represented by that bit.  */
2750
2751 static rtx
2752 make_alternative_compare (int mask)
2753 {
2754   return mk_attr_alt (mask);
2755 }
2756
2757 /* If we are processing an (eq_attr "attr" "value") test, we find the value
2758    of "attr" for this insn code.  From that value, we can compute a test
2759    showing when the EQ_ATTR will be true.  This routine performs that
2760    computation.  If a test condition involves an address, we leave the EQ_ATTR
2761    intact because addresses are only valid for the `length' attribute.
2762
2763    EXP is the EQ_ATTR expression and VALUE is the value of that attribute
2764    for the insn corresponding to INSN_CODE and INSN_INDEX.  */
2765
2766 static rtx
2767 evaluate_eq_attr (rtx exp, rtx value, int insn_code, int insn_index)
2768 {
2769   rtx orexp, andexp;
2770   rtx right;
2771   rtx newexp;
2772   int i;
2773
2774   if (GET_CODE (value) == CONST_STRING)
2775     {
2776       if (! strcmp_check (XSTR (value, 0), XSTR (exp, 1)))
2777         newexp = true_rtx;
2778       else
2779         newexp = false_rtx;
2780     }
2781   else if (GET_CODE (value) == SYMBOL_REF)
2782     {
2783       char *p;
2784       char string[256];
2785
2786       if (GET_CODE (exp) != EQ_ATTR)
2787         abort ();
2788
2789       if (strlen (XSTR (exp, 0)) + strlen (XSTR (exp, 1)) + 2 > 256)
2790         abort ();
2791
2792       strcpy (string, XSTR (exp, 0));
2793       strcat (string, "_");
2794       strcat (string, XSTR (exp, 1));
2795       for (p = string; *p; p++)
2796         *p = TOUPPER (*p);
2797
2798       newexp = attr_rtx (EQ, value,
2799                          attr_rtx (SYMBOL_REF,
2800                                    DEF_ATTR_STRING (string)));
2801     }
2802   else if (GET_CODE (value) == COND)
2803     {
2804       /* We construct an IOR of all the cases for which the requested attribute
2805          value is present.  Since we start with FALSE, if it is not present,
2806          FALSE will be returned.
2807
2808          Each case is the AND of the NOT's of the previous conditions with the
2809          current condition; in the default case the current condition is TRUE.
2810
2811          For each possible COND value, call ourselves recursively.
2812
2813          The extra TRUE and FALSE expressions will be eliminated by another
2814          call to the simplification routine.  */
2815
2816       orexp = false_rtx;
2817       andexp = true_rtx;
2818
2819       if (current_alternative_string)
2820         clear_struct_flag (value);
2821
2822       for (i = 0; i < XVECLEN (value, 0); i += 2)
2823         {
2824           rtx this = simplify_test_exp_in_temp (XVECEXP (value, 0, i),
2825                                                 insn_code, insn_index);
2826
2827           SIMPLIFY_ALTERNATIVE (this);
2828
2829           right = insert_right_side (AND, andexp, this,
2830                                      insn_code, insn_index);
2831           right = insert_right_side (AND, right,
2832                                      evaluate_eq_attr (exp,
2833                                                        XVECEXP (value, 0,
2834                                                                 i + 1),
2835                                                        insn_code, insn_index),
2836                                      insn_code, insn_index);
2837           orexp = insert_right_side (IOR, orexp, right,
2838                                      insn_code, insn_index);
2839
2840           /* Add this condition into the AND expression.  */
2841           newexp = attr_rtx (NOT, this);
2842           andexp = insert_right_side (AND, andexp, newexp,
2843                                       insn_code, insn_index);
2844         }
2845
2846       /* Handle the default case.  */
2847       right = insert_right_side (AND, andexp,
2848                                  evaluate_eq_attr (exp, XEXP (value, 1),
2849                                                    insn_code, insn_index),
2850                                  insn_code, insn_index);
2851       newexp = insert_right_side (IOR, orexp, right, insn_code, insn_index);
2852     }
2853   else
2854     abort ();
2855
2856   /* If uses an address, must return original expression.  But set the
2857      ATTR_IND_SIMPLIFIED_P bit so we don't try to simplify it again.  */
2858
2859   address_used = 0;
2860   walk_attr_value (newexp);
2861
2862   if (address_used)
2863     {
2864       /* This had `&& current_alternative_string', which seems to be wrong.  */
2865       if (! ATTR_IND_SIMPLIFIED_P (exp))
2866         return copy_rtx_unchanging (exp);
2867       return exp;
2868     }
2869   else
2870     return newexp;
2871 }
2872
2873 /* This routine is called when an AND of a term with a tree of AND's is
2874    encountered.  If the term or its complement is present in the tree, it
2875    can be replaced with TRUE or FALSE, respectively.
2876
2877    Note that (eq_attr "att" "v1") and (eq_attr "att" "v2") cannot both
2878    be true and hence are complementary.
2879
2880    There is one special case:  If we see
2881         (and (not (eq_attr "att" "v1"))
2882              (eq_attr "att" "v2"))
2883    this can be replaced by (eq_attr "att" "v2").  To do this we need to
2884    replace the term, not anything in the AND tree.  So we pass a pointer to
2885    the term.  */
2886
2887 static rtx
2888 simplify_and_tree (rtx exp, rtx *pterm, int insn_code, int insn_index)
2889 {
2890   rtx left, right;
2891   rtx newexp;
2892   rtx temp;
2893   int left_eliminates_term, right_eliminates_term;
2894
2895   if (GET_CODE (exp) == AND)
2896     {
2897       left  = simplify_and_tree (XEXP (exp, 0), pterm, insn_code, insn_index);
2898       right = simplify_and_tree (XEXP (exp, 1), pterm, insn_code, insn_index);
2899       if (left != XEXP (exp, 0) || right != XEXP (exp, 1))
2900         {
2901           newexp = attr_rtx (AND, left, right);
2902
2903           exp = simplify_test_exp_in_temp (newexp, insn_code, insn_index);
2904         }
2905     }
2906
2907   else if (GET_CODE (exp) == IOR)
2908     {
2909       /* For the IOR case, we do the same as above, except that we can
2910          only eliminate `term' if both sides of the IOR would do so.  */
2911       temp = *pterm;
2912       left = simplify_and_tree (XEXP (exp, 0), &temp, insn_code, insn_index);
2913       left_eliminates_term = (temp == true_rtx);
2914
2915       temp = *pterm;
2916       right = simplify_and_tree (XEXP (exp, 1), &temp, insn_code, insn_index);
2917       right_eliminates_term = (temp == true_rtx);
2918
2919       if (left_eliminates_term && right_eliminates_term)
2920         *pterm = true_rtx;
2921
2922       if (left != XEXP (exp, 0) || right != XEXP (exp, 1))
2923         {
2924           newexp = attr_rtx (IOR, left, right);
2925
2926           exp = simplify_test_exp_in_temp (newexp, insn_code, insn_index);
2927         }
2928     }
2929
2930   /* Check for simplifications.  Do some extra checking here since this
2931      routine is called so many times.  */
2932
2933   if (exp == *pterm)
2934     return true_rtx;
2935
2936   else if (GET_CODE (exp) == NOT && XEXP (exp, 0) == *pterm)
2937     return false_rtx;
2938
2939   else if (GET_CODE (*pterm) == NOT && exp == XEXP (*pterm, 0))
2940     return false_rtx;
2941
2942   else if (GET_CODE (exp) == EQ_ATTR_ALT && GET_CODE (*pterm) == EQ_ATTR_ALT)
2943     {
2944       if (attr_alt_subset_p (*pterm, exp))
2945         return true_rtx;
2946
2947       if (attr_alt_subset_of_compl_p (*pterm, exp))
2948         return false_rtx;
2949
2950       if (attr_alt_subset_p (exp, *pterm))
2951         *pterm = true_rtx;
2952
2953       return exp;
2954     }
2955
2956   else if (GET_CODE (exp) == EQ_ATTR && GET_CODE (*pterm) == EQ_ATTR)
2957     {
2958       if (XSTR (exp, 0) != XSTR (*pterm, 0))
2959         return exp;
2960
2961       if (! strcmp_check (XSTR (exp, 1), XSTR (*pterm, 1)))
2962         return true_rtx;
2963       else
2964         return false_rtx;
2965     }
2966
2967   else if (GET_CODE (*pterm) == EQ_ATTR && GET_CODE (exp) == NOT
2968            && GET_CODE (XEXP (exp, 0)) == EQ_ATTR)
2969     {
2970       if (XSTR (*pterm, 0) != XSTR (XEXP (exp, 0), 0))
2971         return exp;
2972
2973       if (! strcmp_check (XSTR (*pterm, 1), XSTR (XEXP (exp, 0), 1)))
2974         return false_rtx;
2975       else
2976         return true_rtx;
2977     }
2978
2979   else if (GET_CODE (exp) == EQ_ATTR && GET_CODE (*pterm) == NOT
2980            && GET_CODE (XEXP (*pterm, 0)) == EQ_ATTR)
2981     {
2982       if (XSTR (exp, 0) != XSTR (XEXP (*pterm, 0), 0))
2983         return exp;
2984
2985       if (! strcmp_check (XSTR (exp, 1), XSTR (XEXP (*pterm, 0), 1)))
2986         return false_rtx;
2987       else
2988         *pterm = true_rtx;
2989     }
2990
2991   else if (GET_CODE (exp) == NOT && GET_CODE (*pterm) == NOT)
2992     {
2993       if (attr_equal_p (XEXP (exp, 0), XEXP (*pterm, 0)))
2994         return true_rtx;
2995     }
2996
2997   else if (GET_CODE (exp) == NOT)
2998     {
2999       if (attr_equal_p (XEXP (exp, 0), *pterm))
3000         return false_rtx;
3001     }
3002
3003   else if (GET_CODE (*pterm) == NOT)
3004     {
3005       if (attr_equal_p (XEXP (*pterm, 0), exp))
3006         return false_rtx;
3007     }
3008
3009   else if (attr_equal_p (exp, *pterm))
3010     return true_rtx;
3011
3012   return exp;
3013 }
3014
3015 /* Similar to `simplify_and_tree', but for IOR trees.  */
3016
3017 static rtx
3018 simplify_or_tree (rtx exp, rtx *pterm, int insn_code, int insn_index)
3019 {
3020   rtx left, right;
3021   rtx newexp;
3022   rtx temp;
3023   int left_eliminates_term, right_eliminates_term;
3024
3025   if (GET_CODE (exp) == IOR)
3026     {
3027       left  = simplify_or_tree (XEXP (exp, 0), pterm, insn_code, insn_index);
3028       right = simplify_or_tree (XEXP (exp, 1), pterm, insn_code, insn_index);
3029       if (left != XEXP (exp, 0) || right != XEXP (exp, 1))
3030         {
3031           newexp = attr_rtx (GET_CODE (exp), left, right);
3032
3033           exp = simplify_test_exp_in_temp (newexp, insn_code, insn_index);
3034         }
3035     }
3036
3037   else if (GET_CODE (exp) == AND)
3038     {
3039       /* For the AND case, we do the same as above, except that we can
3040          only eliminate `term' if both sides of the AND would do so.  */
3041       temp = *pterm;
3042       left = simplify_or_tree (XEXP (exp, 0), &temp, insn_code, insn_index);
3043       left_eliminates_term = (temp == false_rtx);
3044
3045       temp = *pterm;
3046       right = simplify_or_tree (XEXP (exp, 1), &temp, insn_code, insn_index);
3047       right_eliminates_term = (temp == false_rtx);
3048
3049       if (left_eliminates_term && right_eliminates_term)
3050         *pterm = false_rtx;
3051
3052       if (left != XEXP (exp, 0) || right != XEXP (exp, 1))
3053         {
3054           newexp = attr_rtx (GET_CODE (exp), left, right);
3055
3056           exp = simplify_test_exp_in_temp (newexp, insn_code, insn_index);
3057         }
3058     }
3059
3060   if (attr_equal_p (exp, *pterm))
3061     return false_rtx;
3062
3063   else if (GET_CODE (exp) == NOT && attr_equal_p (XEXP (exp, 0), *pterm))
3064     return true_rtx;
3065
3066   else if (GET_CODE (*pterm) == NOT && attr_equal_p (XEXP (*pterm, 0), exp))
3067     return true_rtx;
3068
3069   else if (GET_CODE (*pterm) == EQ_ATTR && GET_CODE (exp) == NOT
3070            && GET_CODE (XEXP (exp, 0)) == EQ_ATTR
3071            && XSTR (*pterm, 0) == XSTR (XEXP (exp, 0), 0))
3072     *pterm = false_rtx;
3073
3074   else if (GET_CODE (exp) == EQ_ATTR && GET_CODE (*pterm) == NOT
3075            && GET_CODE (XEXP (*pterm, 0)) == EQ_ATTR
3076            && XSTR (exp, 0) == XSTR (XEXP (*pterm, 0), 0))
3077     return false_rtx;
3078
3079   return exp;
3080 }
3081
3082 /* Compute approximate cost of the expression.  Used to decide whether
3083    expression is cheap enough for inline.  */
3084 static int
3085 attr_rtx_cost (rtx x)
3086 {
3087   int cost = 0;
3088   enum rtx_code code;
3089   if (!x)
3090     return 0;
3091   code = GET_CODE (x);
3092   switch (code)
3093     {
3094     case MATCH_OPERAND:
3095       if (XSTR (x, 1)[0])
3096         return 10;
3097       else
3098         return 0;
3099
3100     case EQ_ATTR_ALT:
3101       return 0;
3102
3103     case EQ_ATTR:
3104       /* Alternatives don't result into function call.  */
3105       if (!strcmp_check (XSTR (x, 0), alternative_name))
3106         return 0;
3107       else
3108         return 5;
3109     default:
3110       {
3111         int i, j;
3112         const char *fmt = GET_RTX_FORMAT (code);
3113         for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3114           {
3115             switch (fmt[i])
3116               {
3117               case 'V':
3118               case 'E':
3119                 for (j = 0; j < XVECLEN (x, i); j++)
3120                   cost += attr_rtx_cost (XVECEXP (x, i, j));
3121                 break;
3122               case 'e':
3123                 cost += attr_rtx_cost (XEXP (x, i));
3124                 break;
3125               }
3126           }
3127       }
3128       break;
3129     }
3130   return cost;
3131 }
3132
3133 /* Simplify test expression and use temporary obstack in order to avoid
3134    memory bloat.  Use ATTR_IND_SIMPLIFIED to avoid unnecessary simplifications
3135    and avoid unnecessary copying if possible.  */
3136
3137 static rtx
3138 simplify_test_exp_in_temp (rtx exp, int insn_code, int insn_index)
3139 {
3140   rtx x;
3141   struct obstack *old;
3142   if (ATTR_IND_SIMPLIFIED_P (exp))
3143     return exp;
3144   old = rtl_obstack;
3145   rtl_obstack = temp_obstack;
3146   x = simplify_test_exp (exp, insn_code, insn_index);
3147   rtl_obstack = old;
3148   if (x == exp || rtl_obstack == temp_obstack)
3149     return x;
3150   return attr_copy_rtx (x);
3151 }
3152
3153 /* Returns true if S1 is a subset of S2.  */
3154
3155 static bool
3156 attr_alt_subset_p (rtx s1, rtx s2)
3157 {
3158   switch ((XINT (s1, 1) << 1) | XINT (s2, 1))
3159     {
3160     case (0 << 1) | 0:
3161       return !(XINT (s1, 0) &~ XINT (s2, 0));
3162
3163     case (0 << 1) | 1:
3164       return !(XINT (s1, 0) & XINT (s2, 0));
3165
3166     case (1 << 1) | 0:
3167       return false;
3168
3169     case (1 << 1) | 1:
3170       return !(XINT (s2, 0) &~ XINT (s1, 0));
3171
3172     default:
3173       abort ();
3174     }
3175 }
3176
3177 /* Returns true if S1 is a subset of complement of S2.  */
3178
3179 static bool attr_alt_subset_of_compl_p (rtx s1, rtx s2)
3180 {
3181   switch ((XINT (s1, 1) << 1) | XINT (s2, 1))
3182     {
3183     case (0 << 1) | 0:
3184       return !(XINT (s1, 0) & XINT (s2, 0));
3185
3186     case (0 << 1) | 1:
3187       return !(XINT (s1, 0) & ~XINT (s2, 0));
3188
3189     case (1 << 1) | 0:
3190       return !(XINT (s2, 0) &~ XINT (s1, 0));
3191
3192     case (1 << 1) | 1:
3193       return false;
3194
3195     default:
3196       abort ();
3197     }
3198 }
3199
3200 /* Return EQ_ATTR_ALT expression representing intersection of S1 and S2.  */
3201
3202 static rtx
3203 attr_alt_intersection (rtx s1, rtx s2)
3204 {
3205   rtx result = rtx_alloc (EQ_ATTR_ALT);
3206
3207   switch ((XINT (s1, 1) << 1) | XINT (s2, 1))
3208     {
3209     case (0 << 1) | 0:
3210       XINT (result, 0) = XINT (s1, 0) & XINT (s2, 0);
3211       break;
3212     case (0 << 1) | 1:
3213       XINT (result, 0) = XINT (s1, 0) & ~XINT (s2, 0);
3214       break;
3215     case (1 << 1) | 0:
3216       XINT (result, 0) = XINT (s2, 0) & ~XINT (s1, 0);
3217       break;
3218     case (1 << 1) | 1:
3219       XINT (result, 0) = XINT (s1, 0) | XINT (s2, 0);
3220       break;
3221     default:
3222       abort ();
3223     }
3224   XINT (result, 1) = XINT (s1, 1) & XINT (s2, 1);
3225
3226   return result;
3227 }
3228
3229 /* Return EQ_ATTR_ALT expression representing union of S1 and S2.  */
3230
3231 static rtx
3232 attr_alt_union (rtx s1, rtx s2)
3233 {
3234   rtx result = rtx_alloc (EQ_ATTR_ALT);
3235
3236   switch ((XINT (s1, 1) << 1) | XINT (s2, 1))
3237     {
3238     case (0 << 1) | 0:
3239       XINT (result, 0) = XINT (s1, 0) | XINT (s2, 0);
3240       break;
3241     case (0 << 1) | 1:
3242       XINT (result, 0) = XINT (s2, 0) & ~XINT (s1, 0);
3243       break;
3244     case (1 << 1) | 0:
3245       XINT (result, 0) = XINT (s1, 0) & ~XINT (s2, 0);
3246       break;
3247     case (1 << 1) | 1:
3248       XINT (result, 0) = XINT (s1, 0) & XINT (s2, 0);
3249       break;
3250     default:
3251       abort ();
3252     }
3253
3254   XINT (result, 1) = XINT (s1, 1) | XINT (s2, 1);
3255   return result;
3256 }
3257
3258 /* Return EQ_ATTR_ALT expression representing complement of S.  */
3259
3260 static rtx
3261 attr_alt_complement (rtx s)
3262 {
3263   rtx result = rtx_alloc (EQ_ATTR_ALT);
3264
3265   XINT (result, 0) = XINT (s, 0);
3266   XINT (result, 1) = 1 - XINT (s, 1);
3267
3268   return result;
3269 }
3270
3271 /* Tests whether a bit B belongs to the set represented by S.  */
3272
3273 static bool
3274 attr_alt_bit_p (rtx s, int b)
3275 {
3276   return XINT (s, 1) ^ ((XINT (s, 0) >> b) & 1);
3277 }
3278
3279 /* Return EQ_ATTR_ALT expression representing set containing elements set
3280    in E.  */
3281
3282 static rtx
3283 mk_attr_alt (int e)
3284 {
3285   rtx result = rtx_alloc (EQ_ATTR_ALT);
3286
3287   XINT (result, 0) = e;
3288   XINT (result, 1) = 0;
3289
3290   return result;
3291 }
3292
3293 /* Given an expression, see if it can be simplified for a particular insn
3294    code based on the values of other attributes being tested.  This can
3295    eliminate nested get_attr_... calls.
3296
3297    Note that if an endless recursion is specified in the patterns, the
3298    optimization will loop.  However, it will do so in precisely the cases where
3299    an infinite recursion loop could occur during compilation.  It's better that
3300    it occurs here!  */
3301
3302 static rtx
3303 simplify_test_exp (rtx exp, int insn_code, int insn_index)
3304 {
3305   rtx left, right;
3306   struct attr_desc *attr;
3307   struct attr_value *av;
3308   struct insn_ent *ie;
3309   int i;
3310   rtx newexp = exp;
3311   bool left_alt, right_alt;
3312
3313   /* Don't re-simplify something we already simplified.  */
3314   if (ATTR_IND_SIMPLIFIED_P (exp) || ATTR_CURR_SIMPLIFIED_P (exp))
3315     return exp;
3316
3317   switch (GET_CODE (exp))
3318     {
3319     case AND:
3320       left = SIMPLIFY_TEST_EXP (XEXP (exp, 0), insn_code, insn_index);
3321       SIMPLIFY_ALTERNATIVE (left);
3322       if (left == false_rtx)
3323         return false_rtx;
3324       right = SIMPLIFY_TEST_EXP (XEXP (exp, 1), insn_code, insn_index);
3325       SIMPLIFY_ALTERNATIVE (right);
3326       if (left == false_rtx)
3327         return false_rtx;
3328
3329       if (GET_CODE (left) == EQ_ATTR_ALT
3330           && GET_CODE (right) == EQ_ATTR_ALT)
3331         {
3332           exp = attr_alt_intersection (left, right);
3333           return simplify_test_exp (exp, insn_code, insn_index);
3334         }
3335
3336       /* If either side is an IOR and we have (eq_attr "alternative" ..")
3337          present on both sides, apply the distributive law since this will
3338          yield simplifications.  */
3339       if ((GET_CODE (left) == IOR || GET_CODE (right) == IOR)
3340           && compute_alternative_mask (left, IOR)
3341           && compute_alternative_mask (right, IOR))
3342         {
3343           if (GET_CODE (left) == IOR)
3344             {
3345               rtx tem = left;
3346               left = right;
3347               right = tem;
3348             }
3349
3350           newexp = attr_rtx (IOR,
3351                              attr_rtx (AND, left, XEXP (right, 0)),
3352                              attr_rtx (AND, left, XEXP (right, 1)));
3353
3354           return SIMPLIFY_TEST_EXP (newexp, insn_code, insn_index);
3355         }
3356
3357       /* Try with the term on both sides.  */
3358       right = simplify_and_tree (right, &left, insn_code, insn_index);
3359       if (left == XEXP (exp, 0) && right == XEXP (exp, 1))
3360         left = simplify_and_tree (left, &right, insn_code, insn_index);
3361
3362       if (left == false_rtx || right == false_rtx)
3363         return false_rtx;
3364       else if (left == true_rtx)
3365         {
3366           return right;
3367         }
3368       else if (right == true_rtx)
3369         {
3370           return left;
3371         }
3372       /* See if all or all but one of the insn's alternatives are specified
3373          in this tree.  Optimize if so.  */
3374
3375       if (GET_CODE (left) == NOT)
3376         left_alt = (GET_CODE (XEXP (left, 0)) == EQ_ATTR
3377                     && XSTR (XEXP (left, 0), 0) == alternative_name);
3378       else
3379         left_alt = (GET_CODE (left) == EQ_ATTR_ALT
3380                     && XINT (left, 1));
3381
3382       if (GET_CODE (right) == NOT)
3383         right_alt = (GET_CODE (XEXP (right, 0)) == EQ_ATTR
3384                      && XSTR (XEXP (right, 0), 0) == alternative_name);
3385       else
3386         right_alt = (GET_CODE (right) == EQ_ATTR_ALT
3387                      && XINT (right, 1));
3388
3389       if (insn_code >= 0
3390           && (GET_CODE (left) == AND
3391               || left_alt
3392               || GET_CODE (right) == AND
3393               || right_alt))
3394         {
3395           i = compute_alternative_mask (exp, AND);
3396           if (i & ~insn_alternatives[insn_code])
3397             fatal ("invalid alternative specified for pattern number %d",
3398                    insn_index);
3399
3400           /* If all alternatives are excluded, this is false.  */
3401           i ^= insn_alternatives[insn_code];
3402           if (i == 0)
3403             return false_rtx;
3404           else if ((i & (i - 1)) == 0 && insn_alternatives[insn_code] > 1)
3405             {
3406               /* If just one excluded, AND a comparison with that one to the
3407                  front of the tree.  The others will be eliminated by
3408                  optimization.  We do not want to do this if the insn has one
3409                  alternative and we have tested none of them!  */
3410               left = make_alternative_compare (i);
3411               right = simplify_and_tree (exp, &left, insn_code, insn_index);
3412               newexp = attr_rtx (AND, left, right);
3413
3414               return SIMPLIFY_TEST_EXP (newexp, insn_code, insn_index);
3415             }
3416         }
3417
3418       if (left != XEXP (exp, 0) || right != XEXP (exp, 1))
3419         {
3420           newexp = attr_rtx (AND, left, right);
3421           return SIMPLIFY_TEST_EXP (newexp, insn_code, insn_index);
3422         }
3423       break;
3424
3425     case IOR:
3426       left = SIMPLIFY_TEST_EXP (XEXP (exp, 0), insn_code, insn_index);
3427       SIMPLIFY_ALTERNATIVE (left);
3428       if (left == true_rtx)
3429         return true_rtx;
3430       right = SIMPLIFY_TEST_EXP (XEXP (exp, 1), insn_code, insn_index);
3431       SIMPLIFY_ALTERNATIVE (right);
3432       if (right == true_rtx)
3433         return true_rtx;
3434
3435       if (GET_CODE (left) == EQ_ATTR_ALT
3436           && GET_CODE (right) == EQ_ATTR_ALT)
3437         {
3438           exp = attr_alt_union (left, right);
3439           return simplify_test_exp (exp, insn_code, insn_index);
3440         }
3441
3442       right = simplify_or_tree (right, &left, insn_code, insn_index);
3443       if (left == XEXP (exp, 0) && right == XEXP (exp, 1))
3444         left = simplify_or_tree (left, &right, insn_code, insn_index);
3445
3446       if (right == true_rtx || left == true_rtx)
3447         return true_rtx;
3448       else if (left == false_rtx)
3449         {
3450           return right;
3451         }
3452       else if (right == false_rtx)
3453         {
3454           return left;
3455         }
3456
3457       /* Test for simple cases where the distributive law is useful.  I.e.,
3458             convert (ior (and (x) (y))
3459                          (and (x) (z)))
3460             to      (and (x)
3461                          (ior (y) (z)))
3462        */
3463
3464       else if (GET_CODE (left) == AND && GET_CODE (right) == AND
3465                && attr_equal_p (XEXP&nbs