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 Free Software Foundation, Inc.
   4    Contributed by Richard Kenner (kenner@vlsi1.ultra.nyu.edu)
   5
   6 This file is part of GNU CC.
   7
   8 GNU CC is free software; you can redistribute it and/or modify
   9 it under the terms of the GNU General Public License as published by
  10 the Free Software Foundation; either version 2, or (at your option)
  11 any later version.
  12
  13 GNU CC is distributed in the hope that it will be useful,
  14 but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 GNU General Public License for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GNU CC; see the file COPYING.  If not, write to
  20 the Free Software Foundation, 59 Temple Place - Suite 330,
  21 Boston, MA 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' (RTX_UNCHANGING_P): This rtx is fully simplified
  90       independent of the insn code.
  91    `in_struct' (MEM_IN_STRUCT_P): This rtx is fully simplified
  92       for the insn code currently being processed (see optimize_attrs).
  93    `integrated' (RTX_INTEGRATED_P): This rtx is permanent and unique
  94       (see attr_rtx).
  95    `volatil' (MEM_VOLATILE_P): During simplify_by_exploding the value of an
  96       EQ_ATTR rtx is true if !volatil and false if volatil.  */
  97
  98
  99 #include "hconfig.h"
 100 #include "system.h"
 101 #include "rtl.h"
 102 #include "ggc.h"
 103 #include "gensupport.h"
 104
 105 #ifdef HAVE_SYS_RESOURCE_H
 106 # include <sys/resource.h>
 107 #endif
 108
 109 /* We must include obstack.h after <sys/time.h>, to avoid lossage with
 110    /usr/include/sys/stdtypes.h on Sun OS 4.x.  */
 111 #include "obstack.h"
 112 #include "errors.h"
 113
 114 static struct obstack obstack, obstack1, obstack2;
 115 struct obstack *rtl_obstack = &obstack;
 116 struct obstack *hash_obstack = &obstack1;
 117 struct obstack *temp_obstack = &obstack2;
 118
 119 #define obstack_chunk_alloc xmalloc
 120 #define obstack_chunk_free free
 121
 122 /* enough space to reserve for printing out ints */
 123 #define MAX_DIGITS (HOST_BITS_PER_INT * 3 / 10 + 3)
 124
 125 /* Define structures used to record attributes and values.  */
 126
 127 /* As each DEFINE_INSN, DEFINE_PEEPHOLE, or DEFINE_ASM_ATTRIBUTES is
 128    encountered, we store all the relevant information into a
 129    `struct insn_def'.  This is done to allow attribute definitions to occur
 130    anywhere in the file.  */
 131
 132 struct insn_def
 133 {
 134   int insn_code;                /* Instruction number.  */
 135   int insn_index;               /* Expression numer in file, for errors.  */
 136   struct insn_def *next;        /* Next insn in chain.  */
 137   rtx def;                      /* The DEFINE_...  */
 138   int num_alternatives;         /* Number of alternatives.  */
 139   int vec_idx;                  /* Index of attribute vector in `def'.  */
 140 };
 141
 142 /* Once everything has been read in, we store in each attribute value a list
 143    of insn codes that have that value.  Here is the structure used for the
 144    list.  */
 145
 146 struct insn_ent
 147 {
 148   int insn_code;                /* Instruction number.  */
 149   int insn_index;               /* Index of definition in file */
 150   struct insn_ent *next;        /* Next in chain.  */
 151 };
 152
 153 /* Each value of an attribute (either constant or computed) is assigned a
 154    structure which is used as the listhead of the insns that have that
 155    value.  */
 156
 157 struct attr_value
 158 {
 159   rtx value;                    /* Value of attribute.  */
 160   struct attr_value *next;      /* Next attribute value in chain.  */
 161   struct insn_ent *first_insn;  /* First insn with this value.  */
 162   int num_insns;                /* Number of insns with this value.  */
 163   int has_asm_insn;             /* True if this value used for `asm' insns */
 164 };
 165
 166 /* Structure for each attribute.  */
 167
 168 struct attr_desc
 169 {
 170   char *name;                   /* Name of attribute.  */
 171   struct attr_desc *next;       /* Next attribute.  */
 172   unsigned is_numeric   : 1;    /* Values of this attribute are numeric.  */
 173   unsigned negative_ok  : 1;    /* Allow negative numeric values.  */
 174   unsigned unsigned_p   : 1;    /* Make the output function unsigned int.  */
 175   unsigned is_const     : 1;    /* Attribute value constant for each run.  */
 176   unsigned is_special   : 1;    /* Don't call `write_attr_set'.  */
 177   unsigned func_units_p : 1;    /* this is the function_units attribute */
 178   unsigned blockage_p   : 1;    /* this is the blockage range function */
 179   struct attr_value *first_value; /* First value of this attribute.  */
 180   struct attr_value *default_val; /* Default value for this attribute.  */
 181 };
 182
 183 #define NULL_ATTR (struct attr_desc *) NULL
 184
 185 /* A range of values.  */
 186
 187 struct range
 188 {
 189   int min;
 190   int max;
 191 };
 192
 193 /* Structure for each DEFINE_DELAY.  */
 194
 195 struct delay_desc
 196 {
 197   rtx def;                      /* DEFINE_DELAY expression.  */
 198   struct delay_desc *next;      /* Next DEFINE_DELAY.  */
 199   int num;                      /* Number of DEFINE_DELAY, starting at 1.  */
 200 };
 201
 202 /* Record information about each DEFINE_FUNCTION_UNIT.  */
 203
 204 struct function_unit_op
 205 {
 206   rtx condexp;                  /* Expression TRUE for applicable insn.  */
 207   struct function_unit_op *next; /* Next operation for this function unit.  */
 208   int num;                      /* Ordinal for this operation type in unit.  */
 209   int ready;                    /* Cost until data is ready.  */
 210   int issue_delay;              /* Cost until unit can accept another insn.  */
 211   rtx conflict_exp;             /* Expression TRUE for insns incurring issue delay.  */
 212   rtx issue_exp;                /* Expression computing issue delay.  */
 213 };
 214
 215 /* Record information about each function unit mentioned in a
 216    DEFINE_FUNCTION_UNIT.  */
 217
 218 struct function_unit
 219 {
 220   const char *name;             /* Function unit name.  */
 221   struct function_unit *next;   /* Next function unit.  */
 222   int num;                      /* Ordinal of this unit type.  */
 223   int multiplicity;             /* Number of units of this type.  */
 224   int simultaneity;             /* Maximum number of simultaneous insns
 225                                    on this function unit or 0 if unlimited.  */
 226   rtx condexp;                  /* Expression TRUE for insn needing unit.  */
 227   int num_opclasses;            /* Number of different operation types.  */
 228   struct function_unit_op *ops; /* Pointer to first operation type.  */
 229   int needs_conflict_function;  /* Nonzero if a conflict function required.  */
 230   int needs_blockage_function;  /* Nonzero if a blockage function required.  */
 231   int needs_range_function;     /* Nonzero if blockage range function needed.*/
 232   rtx default_cost;             /* Conflict cost, if constant.  */
 233   struct range issue_delay;     /* Range of issue delay values.  */
 234   int max_blockage;             /* Maximum time an insn blocks the unit.  */
 235 };
 236
 237 /* Listheads of above structures.  */
 238
 239 /* This one is indexed by the first character of the attribute name.  */
 240 #define MAX_ATTRS_INDEX 256
 241 static struct attr_desc *attrs[MAX_ATTRS_INDEX];
 242 static struct insn_def *defs;
 243 static struct delay_desc *delays;
 244 static struct function_unit *units;
 245
 246 /* An expression where all the unknown terms are EQ_ATTR tests can be
 247    rearranged into a COND provided we can enumerate all possible
 248    combinations of the unknown values.  The set of combinations become the
 249    tests of the COND; the value of the expression given that combination is
 250    computed and becomes the corresponding value.  To do this, we must be
 251    able to enumerate all values for each attribute used in the expression
 252    (currently, we give up if we find a numeric attribute).
 253
 254    If the set of EQ_ATTR tests used in an expression tests the value of N
 255    different attributes, the list of all possible combinations can be made
 256    by walking the N-dimensional attribute space defined by those
 257    attributes.  We record each of these as a struct dimension.
 258
 259    The algorithm relies on sharing EQ_ATTR nodes: if two nodes in an
 260    expression are the same, the will also have the same address.  We find
 261    all the EQ_ATTR nodes by marking them MEM_VOLATILE_P.  This bit later
 262    represents the value of an EQ_ATTR node, so once all nodes are marked,
 263    they are also given an initial value of FALSE.
 264
 265    We then separate the set of EQ_ATTR nodes into dimensions for each
 266    attribute and put them on the VALUES list.  Terms are added as needed by
 267    `add_values_to_cover' so that all possible values of the attribute are
 268    tested.
 269
 270    Each dimension also has a current value.  This is the node that is
 271    currently considered to be TRUE.  If this is one of the nodes added by
 272    `add_values_to_cover', all the EQ_ATTR tests in the original expression
 273    will be FALSE.  Otherwise, only the CURRENT_VALUE will be true.
 274
 275    NUM_VALUES is simply the length of the VALUES list and is there for
 276    convenience.
 277
 278    Once the dimensions are created, the algorithm enumerates all possible
 279    values and computes the current value of the given expression.  */
 280
 281 struct dimension
 282 {
 283   struct attr_desc *attr;       /* Attribute for this dimension.  */
 284   rtx values;                   /* List of attribute values used.  */
 285   rtx current_value;            /* Position in the list for the TRUE value.  */
 286   int num_values;               /* Length of the values list.  */
 287 };
 288
 289 /* Other variables.  */
 290
 291 static int insn_code_number;
 292 static int insn_index_number;
 293 static int got_define_asm_attributes;
 294 static int must_extract;
 295 static int must_constrain;
 296 static int address_used;
 297 static int length_used;
 298 static int num_delays;
 299 static int have_annul_true, have_annul_false;
 300 static int num_units, num_unit_opclasses;
 301 static int num_insn_ents;
 302
 303 /* Used as operand to `operate_exp':  */
 304
 305 enum operator {PLUS_OP, MINUS_OP, POS_MINUS_OP, EQ_OP, OR_OP, ORX_OP, MAX_OP, MIN_OP, RANGE_OP};
 306
 307 /* Stores, for each insn code, the number of constraint alternatives.  */
 308
 309 static int *insn_n_alternatives;
 310
 311 /* Stores, for each insn code, a bitmap that has bits on for each possible
 312    alternative.  */
 313
 314 static int *insn_alternatives;
 315
 316 /* If nonzero, assume that the `alternative' attr has this value.
 317    This is the hashed, unique string for the numeral
 318    whose value is chosen alternative.  */
 319
 320 static const char *current_alternative_string;
 321
 322 /* Used to simplify expressions.  */
 323
 324 static rtx true_rtx, false_rtx;
 325
 326 /* Used to reduce calls to `strcmp' */
 327
 328 static char *alternative_name;
 329
 330 /* Indicate that REG_DEAD notes are valid if dead_or_set_p is ever
 331    called.  */
 332
 333 int reload_completed = 0;
 334
 335 /* Some machines test `optimize' in macros called from rtlanal.c, so we need
 336    to define it here.  */
 337
 338 int optimize = 0;
 339
 340 /* Simplify an expression.  Only call the routine if there is something to
 341    simplify.  */
 342 #define SIMPLIFY_TEST_EXP(EXP,INSN_CODE,INSN_INDEX)     \
 343   (RTX_UNCHANGING_P (EXP) || MEM_IN_STRUCT_P (EXP) ? (EXP)      \
 344    : simplify_test_exp (EXP, INSN_CODE, INSN_INDEX))
 345
 346 /* Simplify (eq_attr ("alternative") ...)
 347    when we are working with a particular alternative.  */
 348 #define SIMPLIFY_ALTERNATIVE(EXP)                               \
 349   if (current_alternative_string                                \
 350       && GET_CODE ((EXP)) == EQ_ATTR                            \
 351       && XSTR ((EXP), 0) == alternative_name)                   \
 352     (EXP) = (XSTR ((EXP), 1) == current_alternative_string      \
 353             ? true_rtx : false_rtx);
 354
 355 /* These are referenced by rtlanal.c and hence need to be defined somewhere.
 356    They won't actually be used.  */
 357
 358 rtx global_rtl[GR_MAX];
 359 rtx pic_offset_table_rtx;
 360
 361 static void attr_hash_add_rtx   PARAMS ((int, rtx));
 362 static void attr_hash_add_string PARAMS ((int, char *));
 363 static rtx attr_rtx             PARAMS ((enum rtx_code, ...));
 364 static char *attr_printf        PARAMS ((int, const char *, ...))
 365   ATTRIBUTE_PRINTF_2;
 366 static char *attr_string        PARAMS ((const char *, int));
 367 static rtx check_attr_test      PARAMS ((rtx, int));
 368 static rtx check_attr_value     PARAMS ((rtx, struct attr_desc *));
 369 static rtx convert_set_attr_alternative PARAMS ((rtx, int, int));
 370 static rtx convert_set_attr     PARAMS ((rtx, int, int));
 371 static void check_defs          PARAMS ((void));
 372 #if 0
 373 static rtx convert_const_symbol_ref PARAMS ((rtx, struct attr_desc *));
 374 #endif
 375 static rtx make_canonical       PARAMS ((struct attr_desc *, rtx));
 376 static struct attr_value *get_attr_value PARAMS ((rtx, struct attr_desc *, int));
 377 static rtx copy_rtx_unchanging  PARAMS ((rtx));
 378 static rtx copy_boolean         PARAMS ((rtx));
 379 static void expand_delays       PARAMS ((void));
 380 static rtx operate_exp          PARAMS ((enum operator, rtx, rtx));
 381 static void expand_units        PARAMS ((void));
 382 static rtx simplify_knowing     PARAMS ((rtx, rtx));
 383 static rtx encode_units_mask    PARAMS ((rtx));
 384 static void fill_attr           PARAMS ((struct attr_desc *));
 385 /* dpx2 compiler chokes if we specify the arg types of the args.  */
 386 static rtx substitute_address   PARAMS ((rtx, rtx (*) (rtx), rtx (*) (rtx)));
 387 static void make_length_attrs   PARAMS ((void));
 388 static rtx identity_fn          PARAMS ((rtx));
 389 static rtx zero_fn              PARAMS ((rtx));
 390 static rtx one_fn               PARAMS ((rtx));
 391 static rtx max_fn               PARAMS ((rtx));
 392 static void write_length_unit_log PARAMS ((void));
 393 static rtx simplify_cond        PARAMS ((rtx, int, int));
 394 #if 0
 395 static rtx simplify_by_alternatives PARAMS ((rtx, int, int));
 396 #endif
 397 static rtx simplify_by_exploding PARAMS ((rtx));
 398 static int find_and_mark_used_attributes PARAMS ((rtx, rtx *, int *));
 399 static void unmark_used_attributes PARAMS ((rtx, struct dimension *, int));
 400 static int add_values_to_cover  PARAMS ((struct dimension *));
 401 static int increment_current_value PARAMS ((struct dimension *, int));
 402 static rtx test_for_current_value PARAMS ((struct dimension *, int));
 403 static rtx simplify_with_current_value PARAMS ((rtx, struct dimension *, int));
 404 static rtx simplify_with_current_value_aux PARAMS ((rtx));
 405 static void clear_struct_flag PARAMS ((rtx));
 406 static int count_sub_rtxs    PARAMS ((rtx, int));
 407 static void remove_insn_ent  PARAMS ((struct attr_value *, struct insn_ent *));
 408 static void insert_insn_ent  PARAMS ((struct attr_value *, struct insn_ent *));
 409 static rtx insert_right_side    PARAMS ((enum rtx_code, rtx, rtx, int, int));
 410 static rtx make_alternative_compare PARAMS ((int));
 411 static int compute_alternative_mask PARAMS ((rtx, enum rtx_code));
 412 static rtx evaluate_eq_attr     PARAMS ((rtx, rtx, int, int));
 413 static rtx simplify_and_tree    PARAMS ((rtx, rtx *, int, int));
 414 static rtx simplify_or_tree     PARAMS ((rtx, rtx *, int, int));
 415 static rtx simplify_test_exp    PARAMS ((rtx, int, int));
 416 static void optimize_attrs      PARAMS ((void));
 417 static void gen_attr            PARAMS ((rtx));
 418 static int count_alternatives   PARAMS ((rtx));
 419 static int compares_alternatives_p PARAMS ((rtx));
 420 static int contained_in_p       PARAMS ((rtx, rtx));
 421 static void gen_insn            PARAMS ((rtx));
 422 static void gen_delay           PARAMS ((rtx));
 423 static void gen_unit            PARAMS ((rtx));
 424 static void write_test_expr     PARAMS ((rtx, int));
 425 static int max_attr_value       PARAMS ((rtx, int*));
 426 static int or_attr_value        PARAMS ((rtx, int*));
 427 static void walk_attr_value     PARAMS ((rtx));
 428 static void write_attr_get      PARAMS ((struct attr_desc *));
 429 static rtx eliminate_known_true PARAMS ((rtx, rtx, int, int));
 430 static void write_attr_set      PARAMS ((struct attr_desc *, int, rtx,
 431                                        const char *, const char *, rtx,
 432                                        int, int));
 433 static void write_attr_case     PARAMS ((struct attr_desc *, struct attr_value *,
 434                                        int, const char *, const char *, int, rtx));
 435 static void write_unit_name     PARAMS ((const char *, int, const char *));
 436 static void write_attr_valueq   PARAMS ((struct attr_desc *, const char *));
 437 static void write_attr_value    PARAMS ((struct attr_desc *, rtx));
 438 static void write_upcase        PARAMS ((const char *));
 439 static void write_indent        PARAMS ((int));
 440 static void write_eligible_delay PARAMS ((const char *));
 441 static void write_function_unit_info PARAMS ((void));
 442 static void write_complex_function PARAMS ((struct function_unit *, const char *,
 443                                           const char *));
 444 static int write_expr_attr_cache PARAMS ((rtx, struct attr_desc *));
 445 static void write_toplevel_expr PARAMS ((rtx));
 446 static void write_const_num_delay_slots PARAMS ((void));
 447 static int n_comma_elts         PARAMS ((const char *));
 448 static char *next_comma_elt     PARAMS ((const char **));
 449 static struct attr_desc *find_attr PARAMS ((const char *, int));
 450 static void make_internal_attr  PARAMS ((const char *, rtx, int));
 451 static struct attr_value *find_most_used  PARAMS ((struct attr_desc *));
 452 static rtx find_single_value    PARAMS ((struct attr_desc *));
 453 static rtx make_numeric_value   PARAMS ((int));
 454 static void extend_range        PARAMS ((struct range *, int, int));
 455 static rtx attr_eq              PARAMS ((const char *, const char *));
 456 static const char *attr_numeral PARAMS ((int));
 457 static int attr_equal_p         PARAMS ((rtx, rtx));
 458 static rtx attr_copy_rtx        PARAMS ((rtx));
 459
 460 #define oballoc(size) obstack_alloc (hash_obstack, size)
 461
 462 \f
 463 /* Hash table for sharing RTL and strings.  */
 464
 465 /* Each hash table slot is a bucket containing a chain of these structures.
 466    Strings are given negative hash codes; RTL expressions are given positive
 467    hash codes.  */
 468
 469 struct attr_hash
 470 {
 471   struct attr_hash *next;       /* Next structure in the bucket.  */
 472   int hashcode;                 /* Hash code of this rtx or string.  */
 473   union
 474     {
 475       char *str;                /* The string (negative hash codes) */
 476       rtx rtl;                  /* or the RTL recorded here.  */
 477     } u;
 478 };
 479
 480 /* Now here is the hash table.  When recording an RTL, it is added to
 481    the slot whose index is the hash code mod the table size.  Note
 482    that the hash table is used for several kinds of RTL (see attr_rtx)
 483    and for strings.  While all these live in the same table, they are
 484    completely independent, and the hash code is computed differently
 485    for each.  */
 486
 487 #define RTL_HASH_SIZE 4093
 488 struct attr_hash *attr_hash_table[RTL_HASH_SIZE];
 489
 490 /* Here is how primitive or already-shared RTL's hash
 491    codes are made.  */
 492 #define RTL_HASH(RTL) ((long) (RTL) & 0777777)
 493
 494 /* Add an entry to the hash table for RTL with hash code HASHCODE.  */
 495
 496 static void
 497 attr_hash_add_rtx (hashcode, rtl)
 498      int hashcode;
 499      rtx rtl;
 500 {
 501   register struct attr_hash *h;
 502
 503   h = (struct attr_hash *) obstack_alloc (hash_obstack,
 504                                           sizeof (struct attr_hash));
 505   h->hashcode = hashcode;
 506   h->u.rtl = rtl;
 507   h->next = attr_hash_table[hashcode % RTL_HASH_SIZE];
 508   attr_hash_table[hashcode % RTL_HASH_SIZE] = h;
 509 }
 510
 511 /* Add an entry to the hash table for STRING with hash code HASHCODE.  */
 512
 513 static void
 514 attr_hash_add_string (hashcode, str)
 515      int hashcode;
 516      char *str;
 517 {
 518   register struct attr_hash *h;
 519
 520   h = (struct attr_hash *) obstack_alloc (hash_obstack,
 521                                           sizeof (struct attr_hash));
 522   h->hashcode = -hashcode;
 523   h->u.str = str;
 524   h->next = attr_hash_table[hashcode % RTL_HASH_SIZE];
 525   attr_hash_table[hashcode % RTL_HASH_SIZE] = h;
 526 }
 527
 528 /* Generate an RTL expression, but avoid duplicates.
 529    Set the RTX_INTEGRATED_P flag for these permanent objects.
 530
 531    In some cases we cannot uniquify; then we return an ordinary
 532    impermanent rtx with RTX_INTEGRATED_P clear.
 533
 534    Args are like gen_rtx, but without the mode:
 535
 536    rtx attr_rtx (code, [element1, ..., elementn])  */
 537
 538 /*VARARGS1*/
 539 static rtx
 540 attr_rtx VPARAMS ((enum rtx_code code, ...))
 541 {
 542 #ifndef ANSI_PROTOTYPES
 543   enum rtx_code code;
 544 #endif
 545   va_list p;
 546   register int i;               /* Array indices...                     */
 547   register const char *fmt;     /* Current rtx's format...              */
 548   register rtx rt_val = NULL_RTX;/* RTX to return to caller...          */
 549   int hashcode;
 550   register struct attr_hash *h;
 551   struct obstack *old_obstack = rtl_obstack;
 552
 553   VA_START (p, code);
 554
 555 #ifndef ANSI_PROTOTYPES
 556   code = va_arg (p, enum rtx_code);
 557 #endif
 558
 559   /* For each of several cases, search the hash table for an existing entry.
 560      Use that entry if one is found; otherwise create a new RTL and add it
 561      to the table.  */
 562
 563   if (GET_RTX_CLASS (code) == '1')
 564     {
 565       rtx arg0 = va_arg (p, rtx);
 566
 567       /* A permanent object cannot point to impermanent ones.  */
 568       if (! RTX_INTEGRATED_P (arg0))
 569         {
 570           rt_val = rtx_alloc (code);
 571           XEXP (rt_val, 0) = arg0;
 572           va_end (p);
 573           return rt_val;
 574         }
 575
 576       hashcode = ((HOST_WIDE_INT) code + RTL_HASH (arg0));
 577       for (h = attr_hash_table[hashcode % RTL_HASH_SIZE]; h; h = h->next)
 578         if (h->hashcode == hashcode
 579             && GET_CODE (h->u.rtl) == code
 580             && XEXP (h->u.rtl, 0) == arg0)
 581           goto found;
 582
 583       if (h == 0)
 584         {
 585           rtl_obstack = hash_obstack;
 586           rt_val = rtx_alloc (code);
 587           XEXP (rt_val, 0) = arg0;
 588         }
 589     }
 590   else if (GET_RTX_CLASS (code) == 'c'
 591            || GET_RTX_CLASS (code) == '2'
 592            || GET_RTX_CLASS (code) == '<')
 593     {
 594       rtx arg0 = va_arg (p, rtx);
 595       rtx arg1 = va_arg (p, rtx);
 596
 597       /* A permanent object cannot point to impermanent ones.  */
 598       if (! RTX_INTEGRATED_P (arg0) || ! RTX_INTEGRATED_P (arg1))
 599         {
 600           rt_val = rtx_alloc (code);
 601           XEXP (rt_val, 0) = arg0;
 602           XEXP (rt_val, 1) = arg1;
 603           va_end (p);
 604           return rt_val;
 605         }
 606
 607       hashcode = ((HOST_WIDE_INT) code + RTL_HASH (arg0) + RTL_HASH (arg1));
 608       for (h = attr_hash_table[hashcode % RTL_HASH_SIZE]; h; h = h->next)
 609         if (h->hashcode == hashcode
 610             && GET_CODE (h->u.rtl) == code
 611             && XEXP (h->u.rtl, 0) == arg0
 612             && XEXP (h->u.rtl, 1) == arg1)
 613           goto found;
 614
 615       if (h == 0)
 616         {
 617           rtl_obstack = hash_obstack;
 618           rt_val = rtx_alloc (code);
 619           XEXP (rt_val, 0) = arg0;
 620           XEXP (rt_val, 1) = arg1;
 621         }
 622     }
 623   else if (GET_RTX_LENGTH (code) == 1
 624            && GET_RTX_FORMAT (code)[0] == 's')
 625     {
 626       char *arg0 = va_arg (p, char *);
 627
 628       if (code == SYMBOL_REF)
 629         arg0 = attr_string (arg0, strlen (arg0));
 630
 631       hashcode = ((HOST_WIDE_INT) code + RTL_HASH (arg0));
 632       for (h = attr_hash_table[hashcode % RTL_HASH_SIZE]; h; h = h->next)
 633         if (h->hashcode == hashcode
 634             && GET_CODE (h->u.rtl) == code
 635             && XSTR (h->u.rtl, 0) == arg0)
 636           goto found;
 637
 638       if (h == 0)
 639         {
 640           rtl_obstack = hash_obstack;
 641           rt_val = rtx_alloc (code);
 642           XSTR (rt_val, 0) = arg0;
 643         }
 644     }
 645   else if (GET_RTX_LENGTH (code) == 2
 646            && GET_RTX_FORMAT (code)[0] == 's'
 647            && GET_RTX_FORMAT (code)[1] == 's')
 648     {
 649       char *arg0 = va_arg (p, char *);
 650       char *arg1 = va_arg (p, char *);
 651
 652       hashcode = ((HOST_WIDE_INT) code + RTL_HASH (arg0) + RTL_HASH (arg1));
 653       for (h = attr_hash_table[hashcode % RTL_HASH_SIZE]; h; h = h->next)
 654         if (h->hashcode == hashcode
 655             && GET_CODE (h->u.rtl) == code
 656             && XSTR (h->u.rtl, 0) == arg0
 657             && XSTR (h->u.rtl, 1) == arg1)
 658           goto found;
 659
 660       if (h == 0)
 661         {
 662           rtl_obstack = hash_obstack;
 663           rt_val = rtx_alloc (code);
 664           XSTR (rt_val, 0) = arg0;
 665           XSTR (rt_val, 1) = arg1;
 666         }
 667     }
 668   else if (code == CONST_INT)
 669     {
 670       HOST_WIDE_INT arg0 = va_arg (p, HOST_WIDE_INT);
 671       if (arg0 == 0)
 672         {
 673           va_end (p);
 674           return false_rtx;
 675         }
 676       if (arg0 == 1)
 677         {
 678           va_end (p);
 679           return true_rtx;
 680         }
 681       goto nohash;
 682     }
 683   else
 684     {
 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       va_end (p);
 722       return rt_val;
 723     }
 724
 725   rtl_obstack = old_obstack;
 726   va_end (p);
 727   attr_hash_add_rtx (hashcode, rt_val);
 728   RTX_INTEGRATED_P (rt_val) = 1;
 729   return rt_val;
 730
 731  found:
 732   va_end (p);
 733   return h->u.rtl;
 734 }
 735
 736 /* Create a new string printed with the printf line arguments into a space
 737    of at most LEN bytes:
 738
 739    rtx attr_printf (len, format, [arg1, ..., argn])  */
 740
 741 /*VARARGS2*/
 742 static char *
 743 attr_printf VPARAMS ((register int len, const char *fmt, ...))
 744 {
 745 #ifndef ANSI_PROTOTYPES
 746   register int len;
 747   const char *fmt;
 748 #endif
 749   va_list p;
 750   register char *str;
 751
 752   VA_START (p, fmt);
 753
 754 #ifndef ANSI_PROTOTYPES
 755   len = va_arg (p, int);
 756   fmt = va_arg (p, const char *);
 757 #endif
 758
 759   /* Print the string into a temporary location.  */
 760   str = (char *) alloca (len);
 761   vsprintf (str, fmt, p);
 762   va_end (p);
 763
 764   return attr_string (str, strlen (str));
 765 }
 766
 767 static rtx
 768 attr_eq (name, value)
 769      const char *name, *value;
 770 {
 771   return attr_rtx (EQ_ATTR, attr_string (name, strlen (name)),
 772                    attr_string (value, strlen (value)));
 773 }
 774
 775 static const char *
 776 attr_numeral (n)
 777      int n;
 778 {
 779   return XSTR (make_numeric_value (n), 0);
 780 }
 781
 782 /* Return a permanent (possibly shared) copy of a string STR (not assumed
 783    to be null terminated) with LEN bytes.  */
 784
 785 static char *
 786 attr_string (str, len)
 787      const char *str;
 788      int len;
 789 {
 790   register struct attr_hash *h;
 791   int hashcode;
 792   int i;
 793   register char *new_str;
 794
 795   /* Compute the hash code.  */
 796   hashcode = (len + 1) * 613 + (unsigned)str[0];
 797   for (i = 1; i <= len; i += 2)
 798     hashcode = ((hashcode * 613) + (unsigned)str[i]);
 799   if (hashcode < 0)
 800     hashcode = -hashcode;
 801
 802   /* Search the table for the string.  */
 803   for (h = attr_hash_table[hashcode % RTL_HASH_SIZE]; h; h = h->next)
 804     if (h->hashcode == -hashcode && h->u.str[0] == str[0]
 805         && !strncmp (h->u.str, str, len))
 806       return h->u.str;                  /* <-- return if found.  */
 807
 808   /* Not found; create a permanent copy and add it to the hash table.  */
 809   new_str = (char *) obstack_alloc (hash_obstack, len + 1);
 810   bcopy (str, new_str, len);
 811   new_str[len] = '\0';
 812   attr_hash_add_string (hashcode, new_str);
 813
 814   return new_str;                       /* Return the new string.  */
 815 }
 816
 817 /* Check two rtx's for equality of contents,
 818    taking advantage of the fact that if both are hashed
 819    then they can't be equal unless they are the same object.  */
 820
 821 static int
 822 attr_equal_p (x, y)
 823      rtx x, y;
 824 {
 825   return (x == y || (! (RTX_INTEGRATED_P (x) && RTX_INTEGRATED_P (y))
 826                      && rtx_equal_p (x, y)));
 827 }
 828 \f
 829 /* Copy an attribute value expression,
 830    descending to all depths, but not copying any
 831    permanent hashed subexpressions.  */
 832
 833 static rtx
 834 attr_copy_rtx (orig)
 835      register rtx orig;
 836 {
 837   register rtx copy;
 838   register int i, j;
 839   register RTX_CODE code;
 840   register const char *format_ptr;
 841
 842   /* No need to copy a permanent object.  */
 843   if (RTX_INTEGRATED_P (orig))
 844     return orig;
 845
 846   code = GET_CODE (orig);
 847
 848   switch (code)
 849     {
 850     case REG:
 851     case QUEUED:
 852     case CONST_INT:
 853     case CONST_DOUBLE:
 854     case SYMBOL_REF:
 855     case CODE_LABEL:
 856     case PC:
 857     case CC0:
 858       return orig;
 859
 860     default:
 861       break;
 862     }
 863
 864   copy = rtx_alloc (code);
 865   PUT_MODE (copy, GET_MODE (orig));
 866   copy->in_struct = orig->in_struct;
 867   copy->volatil = orig->volatil;
 868   copy->unchanging = orig->unchanging;
 869   copy->integrated = orig->integrated;
 870
 871   format_ptr = GET_RTX_FORMAT (GET_CODE (copy));
 872
 873   for (i = 0; i < GET_RTX_LENGTH (GET_CODE (copy)); i++)
 874     {
 875       switch (*format_ptr++)
 876         {
 877         case 'e':
 878           XEXP (copy, i) = XEXP (orig, i);
 879           if (XEXP (orig, i) != NULL)
 880             XEXP (copy, i) = attr_copy_rtx (XEXP (orig, i));
 881           break;
 882
 883         case 'E':
 884         case 'V':
 885           XVEC (copy, i) = XVEC (orig, i);
 886           if (XVEC (orig, i) != NULL)
 887             {
 888               XVEC (copy, i) = rtvec_alloc (XVECLEN (orig, i));
 889               for (j = 0; j < XVECLEN (copy, i); j++)
 890                 XVECEXP (copy, i, j) = attr_copy_rtx (XVECEXP (orig, i, j));
 891             }
 892           break;
 893
 894         case 'n':
 895         case 'i':
 896           XINT (copy, i) = XINT (orig, i);
 897           break;
 898
 899         case 'w':
 900           XWINT (copy, i) = XWINT (orig, i);
 901           break;
 902
 903         case 's':
 904         case 'S':
 905           XSTR (copy, i) = XSTR (orig, i);
 906           break;
 907
 908         default:
 909           abort ();
 910         }
 911     }
 912   return copy;
 913 }
 914 \f
 915 /* Given a test expression for an attribute, ensure it is validly formed.
 916    IS_CONST indicates whether the expression is constant for each compiler
 917    run (a constant expression may not test any particular insn).
 918
 919    Convert (eq_attr "att" "a1,a2") to (ior (eq_attr ... ) (eq_attrq ..))
 920    and (eq_attr "att" "!a1") to (not (eq_attr "att" "a1")).  Do the latter
 921    test first so that (eq_attr "att" "!a1,a2,a3") works as expected.
 922
 923    Update the string address in EQ_ATTR expression to be the same used
 924    in the attribute (or `alternative_name') to speed up subsequent
 925    `find_attr' calls and eliminate most `strcmp' calls.
 926
 927    Return the new expression, if any.   */
 928
 929 static rtx
 930 check_attr_test (exp, is_const)
 931      rtx exp;
 932      int is_const;
 933 {
 934   struct attr_desc *attr;
 935   struct attr_value *av;
 936   const char *name_ptr, *p;
 937   rtx orexp, newexp;
 938
 939   switch (GET_CODE (exp))
 940     {
 941     case EQ_ATTR:
 942       /* Handle negation test.  */
 943       if (XSTR (exp, 1)[0] == '!')
 944         return check_attr_test (attr_rtx (NOT,
 945                                           attr_eq (XSTR (exp, 0),
 946                                                    &XSTR (exp, 1)[1])),
 947                                 is_const);
 948
 949       else if (n_comma_elts (XSTR (exp, 1)) == 1)
 950         {
 951           attr = find_attr (XSTR (exp, 0), 0);
 952           if (attr == NULL)
 953             {
 954               if (! strcmp (XSTR (exp, 0), "alternative"))
 955                 {
 956                   XSTR (exp, 0) = alternative_name;
 957                   /* This can't be simplified any further.  */
 958                   RTX_UNCHANGING_P (exp) = 1;
 959                   return exp;
 960                 }
 961               else
 962                 fatal ("Unknown attribute `%s' in EQ_ATTR", XSTR (exp, 0));
 963             }
 964
 965           if (is_const && ! attr->is_const)
 966             fatal ("Constant expression uses insn attribute `%s' in EQ_ATTR",
 967                    XSTR (exp, 0));
 968
 969           /* Copy this just to make it permanent,
 970              so expressions using it can be permanent too.  */
 971           exp = attr_eq (XSTR (exp, 0), XSTR (exp, 1));
 972
 973           /* It shouldn't be possible to simplify the value given to a
 974              constant attribute, so don't expand this until it's time to
 975              write the test expression.  */
 976           if (attr->is_const)
 977             RTX_UNCHANGING_P (exp) = 1;
 978
 979           if (attr->is_numeric)
 980             {
 981               for (p = XSTR (exp, 1); *p; p++)
 982                 if (*p < '0' || *p > '9')
 983                    fatal ("Attribute `%s' takes only numeric values",
 984                           XSTR (exp, 0));
 985             }
 986           else
 987             {
 988               for (av = attr->first_value; av; av = av->next)
 989                 if (GET_CODE (av->value) == CONST_STRING
 990                     && ! strcmp (XSTR (exp, 1), XSTR (av->value, 0)))
 991                   break;
 992
 993               if (av == NULL)
 994                 fatal ("Unknown value `%s' for `%s' attribute",
 995                        XSTR (exp, 1), XSTR (exp, 0));
 996             }
 997         }
 998       else
 999         {
1000           /* Make an IOR tree of the possible values.  */
1001           orexp = false_rtx;
1002           name_ptr = XSTR (exp, 1);
1003           while ((p = next_comma_elt (&name_ptr)) != NULL)
1004             {
1005               newexp = attr_eq (XSTR (exp, 0), p);
1006               orexp = insert_right_side (IOR, orexp, newexp, -2, -2);
1007             }
1008
1009           return check_attr_test (orexp, is_const);
1010         }
1011       break;
1012
1013     case ATTR_FLAG:
1014       break;
1015
1016     case CONST_INT:
1017       /* Either TRUE or FALSE.  */
1018       if (XWINT (exp, 0))
1019         return true_rtx;
1020       else
1021         return false_rtx;
1022
1023     case IOR:
1024     case AND:
1025       XEXP (exp, 0) = check_attr_test (XEXP (exp, 0), is_const);
1026       XEXP (exp, 1) = check_attr_test (XEXP (exp, 1), is_const);
1027       break;
1028
1029     case NOT:
1030       XEXP (exp, 0) = check_attr_test (XEXP (exp, 0), is_const);
1031       break;
1032
1033     case MATCH_INSN:
1034     case MATCH_OPERAND:
1035       if (is_const)
1036         fatal ("RTL operator \"%s\" not valid in constant attribute test",
1037                GET_RTX_NAME (GET_CODE (exp)));
1038       /* These cases can't be simplified.  */
1039       RTX_UNCHANGING_P (exp) = 1;
1040       break;
1041
1042     case LE:  case LT:  case GT:  case GE:
1043     case LEU: case LTU: case GTU: case GEU:
1044     case NE:  case EQ:
1045       if (GET_CODE (XEXP (exp, 0)) == SYMBOL_REF
1046           && GET_CODE (XEXP (exp, 1)) == SYMBOL_REF)
1047         exp = attr_rtx (GET_CODE (exp),
1048                         attr_rtx (SYMBOL_REF, XSTR (XEXP (exp, 0), 0)),
1049                         attr_rtx (SYMBOL_REF, XSTR (XEXP (exp, 1), 0)));
1050       /* These cases can't be simplified.  */
1051       RTX_UNCHANGING_P (exp) = 1;
1052       break;
1053
1054     case SYMBOL_REF:
1055       if (is_const)
1056         {
1057           /* These cases are valid for constant attributes, but can't be
1058              simplified.  */
1059           exp = attr_rtx (SYMBOL_REF, XSTR (exp, 0));
1060           RTX_UNCHANGING_P (exp) = 1;
1061           break;
1062         }
1063     default:
1064       fatal ("RTL operator \"%s\" not valid in attribute test",
1065              GET_RTX_NAME (GET_CODE (exp)));
1066     }
1067
1068   return exp;
1069 }
1070 \f
1071 /* Given an expression, ensure that it is validly formed and that all named
1072    attribute values are valid for the given attribute.  Issue a fatal error
1073    if not.  If no attribute is specified, assume a numeric attribute.
1074
1075    Return a perhaps modified replacement expression for the value.  */
1076
1077 static rtx
1078 check_attr_value (exp, attr)
1079      rtx exp;
1080      struct attr_desc *attr;
1081 {
1082   struct attr_value *av;
1083   const char *p;
1084   int i;
1085
1086   switch (GET_CODE (exp))
1087     {
1088     case CONST_INT:
1089       if (attr && ! attr->is_numeric)
1090         fatal ("CONST_INT not valid for non-numeric `%s' attribute",
1091                attr->name);
1092
1093       if (INTVAL (exp) < 0 && ! attr->negative_ok)
1094         fatal ("Negative numeric value specified for `%s' attribute",
1095                attr->name);
1096
1097       break;
1098
1099     case CONST_STRING:
1100       if (! strcmp (XSTR (exp, 0), "*"))
1101         break;
1102
1103       if (attr == 0 || attr->is_numeric)
1104         {
1105           p = XSTR (exp, 0);
1106           if (attr && attr->negative_ok && *p == '-')
1107             p++;
1108           for (; *p; p++)
1109             if (*p > '9' || *p < '0')
1110               fatal ("Non-numeric value for numeric `%s' attribute",
1111                      attr ? attr->name : "internal");
1112           break;
1113         }
1114
1115       for (av = attr->first_value; av; av = av->next)
1116         if (GET_CODE (av->value) == CONST_STRING
1117             && ! strcmp (XSTR (av->value, 0), XSTR (exp, 0)))
1118           break;
1119
1120       if (av == NULL)
1121         fatal ("Unknown value `%s' for `%s' attribute",
1122                XSTR (exp, 0), attr ? attr->name : "internal");
1123
1124       break;
1125
1126     case IF_THEN_ELSE:
1127       XEXP (exp, 0) = check_attr_test (XEXP (exp, 0),
1128                                        attr ? attr->is_const : 0);
1129       XEXP (exp, 1) = check_attr_value (XEXP (exp, 1), attr);
1130       XEXP (exp, 2) = check_attr_value (XEXP (exp, 2), attr);
1131       break;
1132
1133     case PLUS:
1134     case MINUS:
1135     case MULT:
1136     case DIV:
1137     case MOD:
1138       if (attr && !attr->is_numeric)
1139         fatal ("Invalid operation `%s' for non-numeric attribute value",
1140                GET_RTX_NAME (GET_CODE (exp)));
1141       /* FALLTHRU */
1142
1143     case IOR:
1144     case AND:
1145       XEXP (exp, 0) = check_attr_value (XEXP (exp, 0), attr);
1146       XEXP (exp, 1) = check_attr_value (XEXP (exp, 1), attr);
1147       break;
1148
1149     case FFS:
1150       XEXP (exp, 0) = check_attr_value (XEXP (exp, 0), attr);
1151       break;
1152
1153     case COND:
1154       if (XVECLEN (exp, 0) % 2 != 0)
1155         fatal ("First operand of COND must have even length");
1156
1157       for (i = 0; i < XVECLEN (exp, 0); i += 2)
1158         {
1159           XVECEXP (exp, 0, i) = check_attr_test (XVECEXP (exp, 0, i),
1160                                                  attr ? attr->is_const : 0);
1161           XVECEXP (exp, 0, i + 1)
1162             = check_attr_value (XVECEXP (exp, 0, i + 1), attr);
1163         }
1164
1165       XEXP (exp, 1) = check_attr_value (XEXP (exp, 1), attr);
1166       break;
1167
1168     case ATTR:
1169       {
1170         struct attr_desc *attr2 = find_attr (XSTR (exp, 0), 0);
1171         if (attr2 == NULL)
1172           fatal ("Unknown attribute `%s' in ATTR", XSTR (exp, 0));
1173         else if ((attr && attr->is_const) && ! attr2->is_const)
1174           fatal ("Non-constant attribute `%s' referenced from `%s'",
1175                  XSTR (exp, 0), attr->name);
1176         else if (attr
1177                  && (attr->is_numeric != attr2->is_numeric
1178                      || (! attr->negative_ok && attr2->negative_ok)))
1179           fatal ("Numeric attribute mismatch calling `%s' from `%s'",
1180                  XSTR (exp, 0), attr->name);
1181       }
1182       break;
1183
1184     case SYMBOL_REF:
1185       /* A constant SYMBOL_REF is valid as a constant attribute test and
1186          is expanded later by make_canonical into a COND.  In a non-constant
1187          attribute test, it is left be.  */
1188       return attr_rtx (SYMBOL_REF, XSTR (exp, 0));
1189
1190     default:
1191       fatal ("Invalid operation `%s' for attribute value",
1192              GET_RTX_NAME (GET_CODE (exp)));
1193     }
1194
1195   return exp;
1196 }
1197 \f
1198 /* Given an SET_ATTR_ALTERNATIVE expression, convert to the canonical SET.
1199    It becomes a COND with each test being (eq_attr "alternative "n") */
1200
1201 static rtx
1202 convert_set_attr_alternative (exp, num_alt, insn_index)
1203      rtx exp;
1204      int num_alt;
1205      int insn_index;
1206 {
1207   rtx condexp;
1208   int i;
1209
1210   if (XVECLEN (exp, 1) != num_alt)
1211     fatal ("Bad number of entries in SET_ATTR_ALTERNATIVE for insn %d",
1212            insn_index);
1213
1214   /* Make a COND with all tests but the last.  Select the last value via the
1215      default.  */
1216   condexp = rtx_alloc (COND);
1217   XVEC (condexp, 0) = rtvec_alloc ((num_alt - 1) * 2);
1218
1219   for (i = 0; i < num_alt - 1; i++)
1220     {
1221       const char *p;
1222       p = attr_numeral (i);
1223
1224       XVECEXP (condexp, 0, 2 * i) = attr_eq (alternative_name, p);
1225 #if 0
1226       /* Sharing this EQ_ATTR rtl causes trouble.  */
1227       XVECEXP (condexp, 0, 2 * i) = rtx_alloc (EQ_ATTR);
1228       XSTR (XVECEXP (condexp, 0, 2 * i), 0) = alternative_name;
1229       XSTR (XVECEXP (condexp, 0, 2 * i), 1) = p;
1230 #endif
1231       XVECEXP (condexp, 0, 2 * i + 1) = XVECEXP (exp, 1, i);
1232     }
1233
1234   XEXP (condexp, 1) = XVECEXP (exp, 1, i);
1235
1236   return attr_rtx (SET, attr_rtx (ATTR, XSTR (exp, 0)), condexp);
1237 }
1238 \f
1239 /* Given a SET_ATTR, convert to the appropriate SET.  If a comma-separated
1240    list of values is given, convert to SET_ATTR_ALTERNATIVE first.  */
1241
1242 static rtx
1243 convert_set_attr (exp, num_alt, insn_index)
1244      rtx exp;
1245      int num_alt;
1246      int insn_index;
1247 {
1248   rtx newexp;
1249   const char *name_ptr;
1250   char *p;
1251   int n;
1252
1253   /* See how many alternative specified.  */
1254   n = n_comma_elts (XSTR (exp, 1));
1255   if (n == 1)
1256     return attr_rtx (SET,
1257                      attr_rtx (ATTR, XSTR (exp, 0)),
1258                      attr_rtx (CONST_STRING, XSTR (exp, 1)));
1259
1260   newexp = rtx_alloc (SET_ATTR_ALTERNATIVE);
1261   XSTR (newexp, 0) = XSTR (exp, 0);
1262   XVEC (newexp, 1) = rtvec_alloc (n);
1263
1264   /* Process each comma-separated name.  */
1265   name_ptr = XSTR (exp, 1);
1266   n = 0;
1267   while ((p = next_comma_elt (&name_ptr)) != NULL)
1268     XVECEXP (newexp, 1, n++) = attr_rtx (CONST_STRING, p);
1269
1270   return convert_set_attr_alternative (newexp, num_alt, insn_index);
1271 }
1272 \f
1273 /* Scan all definitions, checking for validity.  Also, convert any SET_ATTR
1274    and SET_ATTR_ALTERNATIVE expressions to the corresponding SET
1275    expressions.  */
1276
1277 static void
1278 check_defs ()
1279 {
1280   struct insn_def *id;
1281   struct attr_desc *attr;
1282   int i;
1283   rtx value;
1284
1285   for (id = defs; id; id = id->next)
1286     {
1287       if (XVEC (id->def, id->vec_idx) == NULL)
1288         continue;
1289
1290       for (i = 0; i < XVECLEN (id->def, id->vec_idx); i++)
1291         {
1292           value = XVECEXP (id->def, id->vec_idx, i);
1293           switch (GET_CODE (value))
1294             {
1295             case SET:
1296               if (GET_CODE (XEXP (value, 0)) != ATTR)
1297                 fatal ("Bad attribute set in pattern %d", id->insn_index);
1298               break;
1299
1300             case SET_ATTR_ALTERNATIVE:
1301               value = convert_set_attr_alternative (value,
1302                                                     id->num_alternatives,
1303                                                     id->insn_index);
1304               break;
1305
1306             case SET_ATTR:
1307               value = convert_set_attr (value, id->num_alternatives,
1308                                         id->insn_index);
1309               break;
1310
1311             default:
1312               fatal ("Invalid attribute code `%s' for pattern %d",
1313                      GET_RTX_NAME (GET_CODE (value)), id->insn_index);
1314             }
1315
1316           if ((attr = find_attr (XSTR (XEXP (value, 0), 0), 0)) == NULL)
1317             fatal ("Unknown attribute `%s' for pattern number %d",
1318                    XSTR (XEXP (value, 0), 0), id->insn_index);
1319
1320           XVECEXP (id->def, id->vec_idx, i) = value;
1321           XEXP (value, 1) = check_attr_value (XEXP (value, 1), attr);
1322         }
1323     }
1324 }
1325 \f
1326 #if 0
1327 /* Given a constant SYMBOL_REF expression, convert to a COND that
1328    explicitly tests each enumerated value.  */
1329
1330 static rtx
1331 convert_const_symbol_ref (exp, attr)
1332      rtx exp;
1333      struct attr_desc *attr;
1334 {
1335   rtx condexp;
1336   struct attr_value *av;
1337   int i;
1338   int num_alt = 0;
1339
1340   for (av = attr->first_value; av; av = av->next)
1341     num_alt++;
1342
1343   /* Make a COND with all tests but the last, and in the original order.
1344      Select the last value via the default.  Note that the attr values
1345      are constructed in reverse order.  */
1346
1347   condexp = rtx_alloc (COND);
1348   XVEC (condexp, 0) = rtvec_alloc ((num_alt - 1) * 2);
1349   av = attr->first_value;
1350   XEXP (condexp, 1) = av->value;
1351
1352   for (i = num_alt - 2; av = av->next, i >= 0; i--)
1353     {
1354       char *p, *string;
1355       rtx value;
1356
1357       string = p = (char *) oballoc (2
1358                                      + strlen (attr->name)
1359                                      + strlen (XSTR (av->value, 0)));
1360       strcpy (p, attr->name);
1361       strcat (p, "_");
1362       strcat (p, XSTR (av->value, 0));
1363       for (; *p != '\0'; p++)
1364         *p = TOUPPER (*p);
1365
1366       value = attr_rtx (SYMBOL_REF, string);
1367       RTX_UNCHANGING_P (value) = 1;
1368
1369       XVECEXP (condexp, 0, 2 * i) = attr_rtx (EQ, exp, value);
1370
1371       XVECEXP (condexp, 0, 2 * i + 1) = av->value;
1372     }
1373
1374   return condexp;
1375 }
1376 #endif
1377 \f
1378 /* Given a valid expression for an attribute value, remove any IF_THEN_ELSE
1379    expressions by converting them into a COND.  This removes cases from this
1380    program.  Also, replace an attribute value of "*" with the default attribute
1381    value.  */
1382
1383 static rtx
1384 make_canonical (attr, exp)
1385      struct attr_desc *attr;
1386      rtx exp;
1387 {
1388   int i;
1389   rtx newexp;
1390
1391   switch (GET_CODE (exp))
1392     {
1393     case CONST_INT:
1394       exp = make_numeric_value (INTVAL (exp));
1395       break;
1396
1397     case CONST_STRING:
1398       if (! strcmp (XSTR (exp, 0), "*"))
1399         {
1400           if (attr == 0 || attr->default_val == 0)
1401             fatal ("(attr_value \"*\") used in invalid context.");
1402           exp = attr->default_val->value;
1403         }
1404
1405       break;
1406
1407     case SYMBOL_REF:
1408       if (!attr->is_const || RTX_UNCHANGING_P (exp))
1409         break;
1410       /* The SYMBOL_REF is constant for a given run, so mark it as unchanging.
1411          This makes the COND something that won't be considered an arbitrary
1412          expression by walk_attr_value.  */
1413       RTX_UNCHANGING_P (exp) = 1;
1414 #if 0
1415       /* ??? Why do we do this?  With attribute values { A B C D E }, this
1416          tends to generate (!(x==A) && !(x==B) && !(x==C) && !(x==D)) rather
1417          than (x==E). */
1418       exp = convert_const_symbol_ref (exp, attr);
1419       RTX_UNCHANGING_P (exp) = 1;
1420       exp = check_attr_value (exp, attr);
1421       /* Goto COND case since this is now a COND.  Note that while the
1422          new expression is rescanned, all symbol_ref notes are marked as
1423          unchanging.  */
1424       goto cond;
1425 #else
1426       exp = check_attr_value (exp, attr);
1427       break;
1428 #endif
1429
1430     case IF_THEN_ELSE:
1431       newexp = rtx_alloc (COND);
1432       XVEC (newexp, 0) = rtvec_alloc (2);
1433       XVECEXP (newexp, 0, 0) = XEXP (exp, 0);
1434       XVECEXP (newexp, 0, 1) = XEXP (exp, 1);
1435
1436       XEXP (newexp, 1) = XEXP (exp, 2);
1437
1438       exp = newexp;
1439       /* Fall through to COND case since this is now a COND.  */
1440
1441     case COND:
1442       {
1443         int allsame = 1;
1444         rtx defval;
1445
1446         /* First, check for degenerate COND.  */
1447         if (XVECLEN (exp, 0) == 0)
1448           return make_canonical (attr, XEXP (exp, 1));
1449         defval = XEXP (exp, 1) = make_canonical (attr, XEXP (exp, 1));
1450
1451         for (i = 0; i < XVECLEN (exp, 0); i += 2)
1452           {
1453             XVECEXP (exp, 0, i) = copy_boolean (XVECEXP (exp, 0, i));
1454             XVECEXP (exp, 0, i + 1)
1455               = make_canonical (attr, XVECEXP (exp, 0, i + 1));
1456             if (! rtx_equal_p (XVECEXP (exp, 0, i + 1), defval))
1457               allsame = 0;
1458           }
1459         if (allsame)
1460           return defval;
1461       }
1462       break;
1463
1464     default:
1465       break;
1466     }
1467
1468   return exp;
1469 }
1470
1471 static rtx
1472 copy_boolean (exp)
1473      rtx exp;
1474 {
1475   if (GET_CODE (exp) == AND || GET_CODE (exp) == IOR)
1476     return attr_rtx (GET_CODE (exp), copy_boolean (XEXP (exp, 0)),
1477                      copy_boolean (XEXP (exp, 1)));
1478   return exp;
1479 }
1480 \f
1481 /* Given a value and an attribute description, return a `struct attr_value *'
1482    that represents that value.  This is either an existing structure, if the
1483    value has been previously encountered, or a newly-created structure.
1484
1485    `insn_code' is the code of an insn whose attribute has the specified
1486    value (-2 if not processing an insn).  We ensure that all insns for
1487    a given value have the same number of alternatives if the value checks
1488    alternatives.  */
1489
1490 static struct attr_value *
1491 get_attr_value (value, attr, insn_code)
1492      rtx value;
1493      struct attr_desc *attr;
1494      int insn_code;
1495 {
1496   struct attr_value *av;
1497   int num_alt = 0;
1498
1499   value = make_canonical (attr, value);
1500   if (compares_alternatives_p (value))
1501     {
1502       if (insn_code < 0 || insn_alternatives == NULL)
1503         fatal ("(eq_attr \"alternatives\" ...) used in non-insn context");
1504       else
1505         num_alt = insn_alternatives[insn_code];
1506     }
1507
1508   for (av = attr->first_value; av; av = av->next)
1509     if (rtx_equal_p (value, av->value)
1510         && (num_alt == 0 || av->first_insn == NULL
1511             || insn_alternatives[av->first_insn->insn_code]))
1512       return av;
1513
1514   av = (struct attr_value *) oballoc (sizeof (struct attr_value));
1515   av->value = value;
1516   av->next = attr->first_value;
1517   attr->first_value = av;
1518   av->first_insn = NULL;
1519   av->num_insns = 0;
1520   av->has_asm_insn = 0;
1521
1522   return av;
1523 }
1524 \f
1525 /* After all DEFINE_DELAYs have been read in, create internal attributes
1526    to generate the required routines.
1527
1528    First, we compute the number of delay slots for each insn (as a COND of
1529    each of the test expressions in DEFINE_DELAYs).  Then, if more than one
1530    delay type is specified, we compute a similar function giving the
1531    DEFINE_DELAY ordinal for each insn.
1532
1533    Finally, for each [DEFINE_DELAY, slot #] pair, we compute an attribute that
1534    tells whether a given insn can be in that delay slot.
1535
1536    Normal attribute filling and optimization expands these to contain the
1537    information needed to handle delay slots.  */
1538
1539 static void
1540 expand_delays ()
1541 {
1542   struct delay_desc *delay;
1543   rtx condexp;
1544   rtx newexp;
1545   int i;
1546   char *p;
1547
1548   /* First, generate data for `num_delay_slots' function.  */
1549
1550   condexp = rtx_alloc (COND);
1551   XVEC (condexp, 0) = rtvec_alloc (num_delays * 2);
1552   XEXP (condexp, 1) = make_numeric_value (0);
1553
1554   for (i = 0, delay = delays; delay; i += 2, delay = delay->next)
1555     {
1556       XVECEXP (condexp, 0, i) = XEXP (delay->def, 0);
1557       XVECEXP (condexp, 0, i + 1)
1558         = make_numeric_value (XVECLEN (delay->def, 1) / 3);
1559     }
1560
1561   make_internal_attr ("*num_delay_slots", condexp, 0);
1562
1563   /* If more than one delay type, do the same for computing the delay type.  */
1564   if (num_delays > 1)
1565     {
1566       condexp = rtx_alloc (COND);
1567       XVEC (condexp, 0) = rtvec_alloc (num_delays * 2);
1568       XEXP (condexp, 1) = make_numeric_value (0);
1569
1570       for (i = 0, delay = delays; delay; i += 2, delay = delay->next)
1571         {
1572           XVECEXP (condexp, 0, i) = XEXP (delay->def, 0);
1573           XVECEXP (condexp, 0, i + 1) = make_numeric_value (delay->num);
1574         }
1575
1576       make_internal_attr ("*delay_type", condexp, 1);
1577     }
1578
1579   /* For each delay possibility and delay slot, compute an eligibility
1580      attribute for non-annulled insns and for each type of annulled (annul
1581      if true and annul if false).  */
1582  for (delay = delays; delay; delay = delay->next)
1583    {
1584      for (i = 0; i < XVECLEN (delay->def, 1); i += 3)
1585        {
1586          condexp = XVECEXP (delay->def, 1, i);
1587          if (condexp == 0) condexp = false_rtx;
1588          newexp = attr_rtx (IF_THEN_ELSE, condexp,
1589                             make_numeric_value (1), make_numeric_value (0));
1590
1591          p = attr_printf (sizeof ("*delay__") + MAX_DIGITS*2, "*delay_%d_%d",
1592                           delay->num, i / 3);
1593          make_internal_attr (p, newexp, 1);
1594
1595          if (have_annul_true)
1596            {
1597              condexp = XVECEXP (delay->def, 1, i + 1);
1598              if (condexp == 0) condexp = false_rtx;
1599              newexp = attr_rtx (IF_THEN_ELSE, condexp,
1600                                 make_numeric_value (1),
1601                                 make_numeric_value (0));
1602              p = attr_printf (sizeof ("*annul_true__") + MAX_DIGITS*2,
1603                               "*annul_true_%d_%d", delay->num, i / 3);
1604              make_internal_attr (p, newexp, 1);
1605            }
1606
1607          if (have_annul_false)
1608            {
1609              condexp = XVECEXP (delay->def, 1, i + 2);
1610              if (condexp == 0) condexp = false_rtx;
1611              newexp = attr_rtx (IF_THEN_ELSE, condexp,
1612                                 make_numeric_value (1),
1613                                 make_numeric_value (0));
1614              p = attr_printf (sizeof ("*annul_false__") + MAX_DIGITS*2,
1615                               "*annul_false_%d_%d", delay->num, i / 3);
1616              make_internal_attr (p, newexp, 1);
1617            }
1618        }
1619    }
1620 }
1621 \f
1622 /* This function is given a left and right side expression and an operator.
1623    Each side is a conditional expression, each alternative of which has a
1624    numerical value.  The function returns another conditional expression
1625    which, for every possible set of condition values, returns a value that is
1626    the operator applied to the values of the two sides.
1627
1628    Since this is called early, it must also support IF_THEN_ELSE.  */
1629
1630 static rtx
1631 operate_exp (op, left, right)
1632      enum operator op;
1633      rtx left, right;
1634 {
1635   int left_value, right_value;
1636   rtx newexp;
1637   int i;
1638
1639   /* If left is a string, apply operator to it and the right side.  */
1640   if (GET_CODE (left) == CONST_STRING)
1641     {
1642       /* If right is also a string, just perform the operation.  */
1643       if (GET_CODE (right) == CONST_STRING)
1644         {
1645           left_value = atoi (XSTR (left, 0));
1646           right_value = atoi (XSTR (right, 0));
1647           switch (op)
1648             {
1649             case PLUS_OP:
1650               i = left_value + right_value;
1651               break;
1652
1653             case MINUS_OP:
1654               i = left_value - right_value;
1655               break;
1656
1657             case POS_MINUS_OP:  /* The positive part of LEFT - RIGHT.  */
1658               if (left_value > right_value)
1659                 i = left_value - right_value;
1660               else
1661                 i = 0;
1662               break;
1663
1664             case OR_OP:
1665             case ORX_OP:
1666               i = left_value | right_value;
1667               break;
1668
1669             case EQ_OP:
1670               i = left_value == right_value;
1671               break;
1672
1673             case RANGE_OP:
1674               i = (left_value << (HOST_BITS_PER_INT / 2)) | right_value;
1675               break;
1676
1677             case MAX_OP:
1678               if (left_value > right_value)
1679                 i = left_value;
1680               else
1681                 i = right_value;
1682               break;
1683
1684             case MIN_OP:
1685               if (left_value < right_value)
1686                 i = left_value;
1687               else
1688                 i = right_value;
1689               break;
1690
1691             default:
1692               abort ();
1693             }
1694
1695           if (i == left_value)
1696             return left;
1697           if (i == right_value)
1698             return right;
1699           return make_numeric_value (i);
1700         }
1701       else if (GET_CODE (right) == IF_THEN_ELSE)
1702         {
1703           /* Apply recursively to all values within.  */
1704           rtx newleft = operate_exp (op, left, XEXP (right, 1));
1705           rtx newright = operate_exp (op, left, XEXP (right, 2));
1706           if (rtx_equal_p (newleft, newright))
1707             return newleft;
1708           return attr_rtx (IF_THEN_ELSE, XEXP (right, 0), newleft, newright);
1709         }
1710       else if (GET_CODE (right) == COND)
1711         {
1712           int allsame = 1;
1713           rtx defval;
1714
1715           newexp = rtx_alloc (COND);
1716           XVEC (newexp, 0) = rtvec_alloc (XVECLEN (right, 0));
1717           defval = XEXP (newexp, 1) = operate_exp (op, left, XEXP (right, 1));
1718
1719           for (i = 0; i < XVECLEN (right, 0); i += 2)
1720             {
1721               XVECEXP (newexp, 0, i) = XVECEXP (right, 0, i);
1722               XVECEXP (newexp, 0, i + 1)
1723                 = operate_exp (op, left, XVECEXP (right, 0, i + 1));
1724               if (! rtx_equal_p (XVECEXP (newexp, 0, i + 1),
1725                                  defval))
1726                 allsame = 0;
1727             }
1728
1729           /* If the resulting cond is trivial (all alternatives
1730              give the same value), optimize it away.  */
1731           if (allsame)
1732             {
1733               if (!ggc_p)
1734                 obstack_free (rtl_obstack, newexp);
1735               return operate_exp (op, left, XEXP (right, 1));
1736             }
1737
1738           /* If the result is the same as the RIGHT operand,
1739              just use that.  */
1740           if (rtx_equal_p (newexp, right))
1741             {
1742               if (!ggc_p)
1743                 obstack_free (rtl_obstack, newexp);
1744               return right;
1745             }
1746
1747           return newexp;
1748         }
1749       else
1750         fatal ("Badly formed attribute value");
1751     }
1752
1753   /* A hack to prevent expand_units from completely blowing up: ORX_OP does
1754      not associate through IF_THEN_ELSE.  */
1755   else if (op == ORX_OP && GET_CODE (right) == IF_THEN_ELSE)
1756     {
1757       return attr_rtx (IOR, left, right);
1758     }
1759
1760   /* Otherwise, do recursion the other way.  */
1761   else if (GET_CODE (left) == IF_THEN_ELSE)
1762     {
1763       rtx newleft = operate_exp (op, XEXP (left, 1), right);
1764       rtx newright = operate_exp (op, XEXP (left, 2), right);
1765       if (rtx_equal_p (newleft, newright))
1766         return newleft;
1767       return attr_rtx (IF_THEN_ELSE, XEXP (left, 0), newleft, newright);
1768     }
1769   else if (GET_CODE (left) == COND)
1770     {
1771       int allsame = 1;
1772       rtx defval;
1773
1774       newexp = rtx_alloc (COND);
1775       XVEC (newexp, 0) = rtvec_alloc (XVECLEN (left, 0));
1776       defval = XEXP (newexp, 1) = operate_exp (op, XEXP (left, 1), right);
1777
1778       for (i = 0; i < XVECLEN (left, 0); i += 2)
1779         {
1780           XVECEXP (newexp, 0, i) = XVECEXP (left, 0, i);
1781           XVECEXP (newexp, 0, i + 1)
1782             = operate_exp (op, XVECEXP (left, 0, i + 1), right);
1783           if (! rtx_equal_p (XVECEXP (newexp, 0, i + 1),
1784                              defval))
1785             allsame = 0;
1786         }
1787
1788       /* If the cond is trivial (all alternatives give the same value),
1789          optimize it away.  */
1790       if (allsame)
1791         {
1792           if (!ggc_p)
1793             obstack_free (rtl_obstack, newexp);
1794           return operate_exp (op, XEXP (left, 1), right);
1795         }
1796
1797       /* If the result is the same as the LEFT operand,
1798          just use that.  */
1799       if (rtx_equal_p (newexp, left))
1800         {
1801           if (!ggc_p)
1802             obstack_free (rtl_obstack, newexp);
1803           return left;
1804         }
1805
1806       return newexp;
1807     }
1808
1809   else
1810     fatal ("Badly formed attribute value.");
1811   /* NOTREACHED */
1812   return NULL;
1813 }
1814 \f
1815 /* Once all attributes and DEFINE_FUNCTION_UNITs have been read, we
1816    construct a number of attributes.
1817
1818    The first produces a function `function_units_used' which is given an
1819    insn and produces an encoding showing which function units are required
1820    for the execution of that insn.  If the value is non-negative, the insn
1821    uses that unit; otherwise, the value is a one's compliment mask of units
1822    used.
1823
1824    The second produces a function `result_ready_cost' which is used to
1825    determine the time that the result of an insn will be ready and hence
1826    a worst-case schedule.
1827
1828    Both of these produce quite complex expressions which are then set as the
1829    default value of internal attributes.  Normal attribute simplification
1830    should produce reasonable expressions.
1831
1832    For each unit, a `<name>_unit_ready_cost' function will take an
1833    insn and give the delay until that unit will be ready with the result
1834    and a `<name>_unit_conflict_cost' function is given an insn already
1835    executing on the unit and a candidate to execute and will give the
1836    cost from the time the executing insn started until the candidate
1837    can start (ignore limitations on the number of simultaneous insns).
1838
1839    For each unit, a `<name>_unit_blockage' function is given an insn
1840    already executing on the unit and a candidate to execute and will
1841    give the delay incurred due to function unit conflicts.  The range of
1842    blockage cost values for a given executing insn is given by the
1843    `<name>_unit_blockage_range' function.  These values are encoded in
1844    an int where the upper half gives the minimum value and the lower
1845    half gives the maximum value.  */
1846
1847 static void
1848 expand_units ()
1849 {
1850   struct function_unit *unit, **unit_num;
1851   struct function_unit_op *op, **op_array, ***unit_ops;
1852   rtx unitsmask;
1853   rtx readycost;
1854   rtx newexp;
1855   const char *str;
1856   int i, j, u, num, nvalues;
1857
1858   /* Rebuild the condition for the unit to share the RTL expressions.
1859      Sharing is required by simplify_by_exploding.  Build the issue delay
1860      expressions.  Validate the expressions we were given for the conditions
1861      and conflict vector.  Then make attributes for use in the conflict
1862      function.  */
1863
1864   for (unit = units; unit; unit = unit->next)
1865     {
1866       unit->condexp = check_attr_test (unit->condexp, 0);
1867
1868       for (op = unit->ops; op; op = op->next)
1869         {
1870           rtx issue_delay = make_numeric_value (op->issue_delay);
1871           rtx issue_exp = issue_delay;
1872
1873           /* Build, validate, and simplify the issue delay expression.  */
1874           if (op->conflict_exp != true_rtx)
1875             issue_exp = attr_rtx (IF_THEN_ELSE, op->conflict_exp,
1876                                   issue_exp, make_numeric_value (0));
1877           issue_exp = check_attr_value (make_canonical (NULL_ATTR,
1878                                                         issue_exp),
1879                                         NULL_ATTR);
1880           issue_exp = simplify_knowing (issue_exp, unit->condexp);
1881           op->issue_exp = issue_exp;
1882
1883           /* Make an attribute for use in the conflict function if needed.  */
1884           unit->needs_conflict_function = (unit->issue_delay.min
1885                                            != unit->issue_delay.max);
1886           if (unit->needs_conflict_function)
1887             {
1888               str = attr_printf (strlen (unit->name) + sizeof ("*_cost_") + MAX_DIGITS,
1889                                  "*%s_cost_%d", unit->name, op->num);
1890               make_internal_attr (str, issue_exp, 1);
1891             }
1892
1893           /* Validate the condition.  */
1894           op->condexp = check_attr_test (op->condexp, 0);
1895         }
1896     }
1897
1898   /* Compute the mask of function units used.  Initially, the unitsmask is
1899      zero.   Set up a conditional to compute each unit's contribution.  */
1900   unitsmask = make_numeric_value (0);
1901   newexp = rtx_alloc (IF_THEN_ELSE);
1902   XEXP (newexp, 2) = make_numeric_value (0);
1903
1904   /* If we have just a few units, we may be all right expanding the whole
1905      thing.  But the expansion is 2**N in space on the number of opclasses,
1906      so we can't do this for very long -- Alpha and MIPS in particular have
1907      problems with this.  So in that situation, we fall back on an alternate
1908      implementation method.  */
1909 #define NUM_UNITOP_CUTOFF 20
1910
1911   if (num_unit_opclasses < NUM_UNITOP_CUTOFF)
1912     {
1913       /* Merge each function unit into the unit mask attributes.  */
1914       for (unit = units; unit; unit = unit->next)
1915         {
1916           XEXP (newexp, 0) = unit->condexp;
1917           XEXP (newexp, 1) = make_numeric_value (1 << unit->num);
1918           unitsmask = operate_exp (OR_OP, unitsmask, newexp);
1919         }
1920     }
1921   else
1922     {
1923       /* Merge each function unit into the unit mask attributes.  */
1924       for (unit = units; unit; unit = unit->next)
1925         {
1926           XEXP (newexp, 0) = unit->condexp;
1927           XEXP (newexp, 1) = make_numeric_value (1 << unit->num);
1928           unitsmask = operate_exp (ORX_OP, unitsmask, attr_copy_rtx (newexp));
1929         }
1930     }
1931
1932   /* Simplify the unit mask expression, encode it, and make an attribute
1933      for the function_units_used function.  */
1934   unitsmask = simplify_by_exploding (unitsmask);
1935
1936   if (num_unit_opclasses < NUM_UNITOP_CUTOFF)
1937     unitsmask = encode_units_mask (unitsmask);
1938   else
1939     {
1940       /* We can no longer encode unitsmask at compile time, so emit code to
1941          calculate it at runtime.  Rather, put a marker for where we'd do
1942          the code, and actually output it in write_attr_get().  */
1943       unitsmask = attr_rtx (FFS, unitsmask);
1944     }
1945
1946   make_internal_attr ("*function_units_used", unitsmask, 10);
1947
1948   /* Create an array of ops for each unit.  Add an extra unit for the
1949      result_ready_cost function that has the ops of all other units.  */
1950   unit_ops = (struct function_unit_op ***)
1951     alloca ((num_units + 1) * sizeof (struct function_unit_op **));
1952   unit_num = (struct function_unit **)
1953     alloca ((num_units + 1) * sizeof (struct function_unit *));
1954
1955   unit_num[num_units] = unit = (struct function_unit *)
1956     alloca (sizeof (struct function_unit));
1957   unit->num = num_units;
1958   unit->num_opclasses = 0;
1959
1960   for (unit = units; unit; unit = unit->next)
1961     {
1962       unit_num[num_units]->num_opclasses += unit->num_opclasses;
1963       unit_num[unit->num] = unit;
1964       unit_ops[unit->num] = op_array = (struct function_unit_op **)
1965         alloca (unit->num_opclasses * sizeof (struct function_unit_op *));
1966
1967       for (op = unit->ops; op; op = op->next)
1968         op_array[op->num] = op;
1969     }
1970
1971   /* Compose the array of ops for the extra unit.  */
1972   unit_ops[num_units] = op_array = (struct function_unit_op **)
1973     alloca (unit_num[num_units]->num_opclasses
1974             * sizeof (struct function_unit_op *));
1975
1976   for (unit = units, i = 0; unit; i += unit->num_opclasses, unit = unit->next)
1977     bcopy ((char *) unit_ops[unit->num], (char *) &op_array[i],
1978            unit->num_opclasses * sizeof (struct function_unit_op *));
1979
1980   /* Compute the ready cost function for each unit by computing the
1981      condition for each non-default value.  */
1982   for (u = 0; u <= num_units; u++)
1983     {
1984       rtx orexp;
1985       int value;
1986
1987       unit = unit_num[u];
1988       op_array = unit_ops[unit->num];
1989       num = unit->num_opclasses;
1990
1991       /* Sort the array of ops into increasing ready cost order.  */
1992       for (i = 0; i < num; i++)
1993         for (j = num - 1; j > i; j--)
1994           if (op_array[j-1]->ready < op_array[j]->ready)
1995             {
1996               op = op_array[j];
1997               op_array[j] = op_array[j-1];
1998               op_array[j-1] = op;
1999             }
2000
2001       /* Determine how many distinct non-default ready cost values there
2002          are.  We use a default ready cost value of 1.  */
2003       nvalues = 0; value = 1;
2004       for (i = num - 1; i >= 0; i--)
2005         if (op_array[i]->ready > value)
2006           {
2007             value = op_array[i]->ready;
2008             nvalues++;
2009           }
2010
2011       if (nvalues == 0)
2012         readycost = make_numeric_value (1);
2013       else
2014         {
2015           /* Construct the ready cost expression as a COND of each value from
2016              the largest to the smallest.  */
2017           readycost = rtx_alloc (COND);
2018           XVEC (readycost, 0) = rtvec_alloc (nvalues * 2);
2019           XEXP (readycost, 1) = make_numeric_value (1);
2020
2021           nvalues = 0; orexp = false_rtx; value = op_array[0]->ready;
2022           for (i = 0; i < num; i++)
2023             {
2024               op = op_array[i];
2025               if (op->ready <= 1)
2026                 break;
2027               else if (op->ready == value)
2028                 orexp = insert_right_side (IOR, orexp, op->condexp, -2, -2);
2029               else
2030                 {
2031                   XVECEXP (readycost, 0, nvalues * 2) = orexp;
2032                   XVECEXP (readycost, 0, nvalues * 2 + 1)
2033                     = make_numeric_value (value);
2034                   nvalues++;
2035                   value = op->ready;
2036                   orexp = op->condexp;
2037                 }
2038             }
2039           XVECEXP (readycost, 0, nvalues * 2) = orexp;
2040           XVECEXP (readycost, 0, nvalues * 2 + 1) = make_numeric_value (value);
2041         }
2042
2043       if (u < num_units)
2044         {
2045           rtx max_blockage = 0, min_blockage = 0;
2046
2047           /* Simplify the readycost expression by only considering insns
2048              that use the unit.  */
2049           readycost = simplify_knowing (readycost, unit->condexp);
2050
2051           /* Determine the blockage cost the executing insn (E) given
2052              the candidate insn (C).  This is the maximum of the issue
2053              delay, the pipeline delay, and the simultaneity constraint.
2054              Each function_unit_op represents the characteristics of the
2055              candidate insn, so in the expressions below, C is a known
2056              term and E is an unknown term.
2057
2058              We compute the blockage cost for each E for every possible C.
2059              Thus OP represents E, and READYCOST is a list of values for
2060              every possible C.
2061
2062              The issue delay function for C is op->issue_exp and is used to
2063              write the `<name>_unit_conflict_cost' function.  Symbolicly
2064              this is "ISSUE-DELAY (E,C)".
2065
2066              The pipeline delay results form the FIFO constraint on the
2067              function unit and is "READY-COST (E) + 1 - READY-COST (C)".
2068
2069              The simultaneity constraint is based on how long it takes to
2070              fill the unit given the minimum issue delay.  FILL-TIME is the
2071              constant "MIN (ISSUE-DELAY (*,*)) * (SIMULTANEITY - 1)", and
2072              the simultaneity constraint is "READY-COST (E) - FILL-TIME"
2073              if SIMULTANEITY is non-zero and zero otherwise.
2074
2075              Thus, BLOCKAGE (E,C) when SIMULTANEITY is zero is
2076
2077                  MAX (ISSUE-DELAY (E,C),
2078                       READY-COST (E) - (READY-COST (C) - 1))
2079
2080              and otherwise
2081
2082                  MAX (ISSUE-DELAY (E,C),
2083                       READY-COST (E) - (READY-COST (C) - 1),
2084                       READY-COST (E) - FILL-TIME)
2085
2086              The `<name>_unit_blockage' function is computed by determining
2087              this value for each candidate insn.  As these values are
2088              computed, we also compute the upper and lower bounds for
2089              BLOCKAGE (E,*).  These are combined to form the function
2090              `<name>_unit_blockage_range'.  Finally, the maximum blockage
2091              cost, MAX (BLOCKAGE (*,*)), is computed.  */
2092
2093           for (op = unit->ops; op; op = op->next)
2094             {
2095               rtx blockage = op->issue_exp;
2096               blockage = simplify_knowing (blockage, unit->condexp);
2097
2098               /* Add this op's contribution to MAX (BLOCKAGE (E,*)) and
2099                  MIN (BLOCKAGE (E,*)).  */
2100               if (max_blockage == 0)
2101                 max_blockage = min_blockage = blockage;
2102               else
2103                 {
2104                   max_blockage
2105                     = simplify_knowing (operate_exp (MAX_OP, max_blockage,
2106                                                      blockage),
2107                                         unit->condexp);
2108                   min_blockage
2109                     = simplify_knowing (operate_exp (MIN_OP, min_blockage,
2110                                                      blockage),
2111                                         unit->condexp);
2112                 }
2113
2114               /* Make an attribute for use in the blockage function.  */
2115               str = attr_printf (strlen (unit->name) + sizeof ("*_block_") + MAX_DIGITS,
2116                                  "*%s_block_%d", unit->name, op->num);
2117               make_internal_attr (str, blockage, 1);
2118             }
2119
2120           /* Record MAX (BLOCKAGE (*,*)).  */
2121           {
2122             int unknown;
2123             unit->max_blockage = max_attr_value (max_blockage, &unknown);
2124           }
2125
2126           /* See if the upper and lower bounds of BLOCKAGE (E,*) are the
2127              same.  If so, the blockage function carries no additional
2128              information and is not written.  */
2129           newexp = operate_exp (EQ_OP, max_blockage, min_blockage);
2130           newexp = simplify_knowing (newexp, unit->condexp);
2131           unit->needs_blockage_function
2132             = (GET_CODE (newexp) != CONST_STRING
2133                || atoi (XSTR (newexp, 0)) != 1);
2134
2135           /* If the all values of BLOCKAGE (E,C) have the same value,
2136              neither blockage function is written.  */
2137           unit->needs_range_function
2138             = (unit->needs_blockage_function
2139                || GET_CODE (max_blockage) != CONST_STRING);
2140
2141           if (unit->needs_range_function)
2142             {
2143               /* Compute the blockage range function and make an attribute
2144                  for writing its value.  */
2145               newexp = operate_exp (RANGE_OP, min_blockage, max_blockage);
2146               newexp = simplify_knowing (newexp, unit->condexp);
2147
2148               str = attr_printf (strlen (unit->name) + sizeof ("*_unit_blockage_range"),
2149                                  "*%s_unit_blockage_range", unit->name);
2150               make_internal_attr (str, newexp, 20);
2151             }
2152
2153           str = attr_printf (strlen (unit->name) + sizeof ("*_unit_ready_cost"),
2154                              "*%s_unit_ready_cost", unit->name);
2155         }
2156       else
2157         str = "*result_ready_cost";
2158
2159       /* Make an attribute for the ready_cost function.  Simplifying
2160          further with simplify_by_exploding doesn't win.  */
2161       make_internal_attr (str, readycost, 0);
2162     }
2163
2164   /* For each unit that requires a conflict cost function, make an attribute
2165      that maps insns to the operation number.  */
2166   for (unit = units; unit; unit = unit->next)
2167     {
2168       rtx caseexp;
2169
2170       if (! unit->needs_conflict_function
2171           && ! unit->needs_blockage_function)
2172         continue;
2173
2174       caseexp = rtx_alloc (COND);
2175       XVEC (caseexp, 0) = rtvec_alloc ((unit->num_opclasses - 1) * 2);
2176
2177       for (op = unit->ops; op; op = op->next)
2178         {
2179           /* Make our adjustment to the COND being computed.  If we are the
2180              last operation class, place our values into the default of the
2181              COND.  */
2182           if (op->num == unit->num_opclasses - 1)
2183             {
2184               XEXP (caseexp, 1) = make_numeric_value (op->num);
2185             }
2186           else
2187             {
2188               XVECEXP (caseexp, 0, op->num * 2) = op->condexp;
2189               XVECEXP (caseexp, 0, op->num * 2 + 1)
2190                 = make_numeric_value (op->num);
2191             }
2192         }
2193
2194       /* Simplifying caseexp with simplify_by_exploding doesn't win.  */
2195       str = attr_printf (strlen (unit->name) + sizeof ("*_cases"),
2196                          "*%s_cases", unit->name);
2197       make_internal_attr (str, caseexp, 1);
2198     }
2199 }
2200
2201 /* Simplify EXP given KNOWN_TRUE.  */
2202
2203 static rtx
2204 simplify_knowing (exp, known_true)
2205      rtx exp, known_true;
2206 {
2207   if (GET_CODE (exp) != CONST_STRING)
2208     {
2209       int unknown = 0, max;
2210       max = max_attr_value (exp, &unknown);
2211       if (! unknown)
2212         {
2213           exp = attr_rtx (IF_THEN_ELSE, known_true, exp,
2214                           make_numeric_value (max));
2215           exp = simplify_by_exploding (exp);
2216         }
2217     }
2218   return exp;
2219 }
2220
2221 /* Translate the CONST_STRING expressions in X to change the encoding of
2222    value.  On input, the value is a bitmask with a one bit for each unit
2223    used; on output, the value is the unit number (zero based) if one
2224    and only one unit is used or the one's compliment of the bitmask.  */
2225
2226 static rtx
2227 encode_units_mask (x)
2228      rtx x;
2229 {
2230   register int i;
2231   register int j;
2232   register enum rtx_code code;
2233   register const char *fmt;
2234
2235   code = GET_CODE (x);
2236
2237   switch (code)
2238     {
2239     case CONST_STRING:
2240       i = atoi (XSTR (x, 0));
2241       if (i < 0)
2242         abort (); /* The sign bit encodes a one's compliment mask.  */
2243       else if (i != 0 && i == (i & -i))
2244         /* Only one bit is set, so yield that unit number.  */
2245         for (j = 0; (i >>= 1) != 0; j++)
2246           ;
2247       else
2248         j = ~i;
2249       return attr_rtx (CONST_STRING, attr_printf (MAX_DIGITS, "%d", j));
2250
2251     case REG:
2252     case QUEUED:
2253     case CONST_INT:
2254     case CONST_DOUBLE:
2255     case SYMBOL_REF:
2256     case CODE_LABEL:
2257     case PC:
2258     case CC0:
2259     case EQ_ATTR:
2260       return x;
2261
2262     default:
2263       break;
2264     }
2265
2266   /* Compare the elements.  If any pair of corresponding elements
2267      fail to match, return 0 for the whole things.  */
2268
2269   fmt = GET_RTX_FORMAT (code);
2270   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2271     {
2272       switch (fmt[i])
2273         {
2274         case 'V':
2275         case 'E':
2276           for (j = 0; j < XVECLEN (x, i); j++)
2277             XVECEXP (x, i, j) = encode_units_mask (XVECEXP (x, i, j));
2278           break;
2279
2280         case 'e':
2281           XEXP (x, i) = encode_units_mask (XEXP (x, i));
2282           break;
2283         }
2284     }
2285   return x;
2286 }
2287 \f
2288 /* Once all attributes and insns have been read and checked, we construct for
2289    each attribute value a list of all the insns that have that value for
2290    the attribute.  */
2291
2292 static void
2293 fill_attr (attr)
2294      struct attr_desc *attr;
2295 {
2296   struct attr_value *av;
2297   struct insn_ent *ie;
2298   struct insn_def *id;
2299   int i;
2300   rtx value;
2301
2302   /* Don't fill constant attributes.  The value is independent of
2303      any particular insn.  */
2304   if (attr->is_const)
2305     return;
2306
2307   for (id = defs; id; id = id->next)
2308     {
2309       /* If no value is specified for this insn for this attribute, use the
2310          default.  */
2311       value = NULL;
2312       if (XVEC (id->def, id->vec_idx))
2313         for (i = 0; i < XVECLEN (id->def, id->vec_idx); i++)
2314           if (! strcmp (XSTR (XEXP (XVECEXP (id->def, id->vec_idx, i), 0), 0),
2315                         attr->name))
2316             value = XEXP (XVECEXP (id->def, id->vec_idx, i), 1);
2317
2318       if (value == NULL)
2319         av = attr->default_val;
2320       else
2321         av = get_attr_value (value, attr, id->insn_code);
2322
2323       ie = (struct insn_ent *) oballoc (sizeof (struct insn_ent));
2324       ie->insn_code = id->insn_code;
2325       ie->insn_index = id->insn_code;
2326       insert_insn_ent (av, ie);
2327     }
2328 }
2329 \f
2330 /* Given an expression EXP, see if it is a COND or IF_THEN_ELSE that has a
2331    test that checks relative positions of insns (uses MATCH_DUP or PC).
2332    If so, replace it with what is obtained by passing the expression to
2333    ADDRESS_FN.  If not but it is a COND or IF_THEN_ELSE, call this routine
2334    recursively on each value (including the default value).  Otherwise,
2335    return the value returned by NO_ADDRESS_FN applied to EXP.  */
2336
2337 static rtx
2338 substitute_address (exp, no_address_fn, address_fn)
2339      rtx exp;
2340      rtx (*no_address_fn) PARAMS ((rtx));
2341      rtx (*address_fn) PARAMS ((rtx));
2342 {
2343   int i;
2344   rtx newexp;
2345
2346   if (GET_CODE (exp) == COND)
2347     {
2348       /* See if any tests use addresses.  */
2349       address_used = 0;
2350       for (i = 0; i < XVECLEN (exp, 0); i += 2)
2351         walk_attr_value (XVECEXP (exp, 0, i));
2352
2353       if (address_used)
2354         return (*address_fn) (exp);
2355
2356       /* Make a new copy of this COND, replacing each element.  */
2357       newexp = rtx_alloc (COND);
2358       XVEC (newexp, 0) = rtvec_alloc (XVECLEN (exp, 0));
2359       for (i = 0; i < XVECLEN (exp, 0); i += 2)
2360         {
2361           XVECEXP (newexp, 0, i) = XVECEXP (exp, 0, i);
2362           XVECEXP (newexp, 0, i + 1)
2363             = substitute_address (XVECEXP (exp, 0, i + 1),
2364                                   no_address_fn, address_fn);
2365         }
2366
2367       XEXP (newexp, 1) = substitute_address (XEXP (exp, 1),
2368                                              no_address_fn, address_fn);
2369
2370       return newexp;
2371     }
2372
2373   else if (GET_CODE (exp) == IF_THEN_ELSE)
2374     {
2375       address_used = 0;
2376       walk_attr_value (XEXP (exp, 0));
2377       if (address_used)
2378         return (*address_fn) (exp);
2379
2380       return attr_rtx (IF_THEN_ELSE,
2381                        substitute_address (XEXP (exp, 0),
2382                                            no_address_fn, address_fn),
2383                        substitute_address (XEXP (exp, 1),
2384                                            no_address_fn, address_fn),
2385                        substitute_address (XEXP (exp, 2),
2386                                            no_address_fn, address_fn));
2387     }
2388
2389   return (*no_address_fn) (exp);
2390 }
2391 \f
2392 /* Make new attributes from the `length' attribute.  The following are made,
2393    each corresponding to a function called from `shorten_branches' or
2394    `get_attr_length':
2395
2396    *insn_default_length         This is the length of the insn to be returned
2397                                 by `get_attr_length' before `shorten_branches'
2398                                 has been called.  In each case where the length
2399                                 depends on relative addresses, the largest
2400                                 possible is used.  This routine is also used
2401                                 to compute the initial size of the insn.
2402
2403    *insn_variable_length_p      This returns 1 if the insn's length depends
2404                                 on relative addresses, zero otherwise.
2405
2406    *insn_current_length         This is only called when it is known that the
2407                                 insn has a variable length and returns the
2408                                 current length, based on relative addresses.
2409   */
2410
2411 static void
2412 make_length_attrs ()
2413 {
2414   static const char *new_names[] = {"*insn_default_length",
2415                                       "*insn_variable_length_p",
2416                                       "*insn_current_length"};
2417   static rtx (*no_address_fn[]) PARAMS ((rtx)) = {identity_fn, zero_fn, zero_fn};
2418   static rtx (*address_fn[]) PARAMS ((rtx)) = {max_fn, one_fn, identity_fn};
2419   size_t i;
2420   struct attr_desc *length_attr, *new_attr;
2421   struct attr_value *av, *new_av;
2422   struct insn_ent *ie, *new_ie;
2423
2424   /* See if length attribute is defined.  If so, it must be numeric.  Make
2425      it special so we don't output anything for it.  */
2426   length_attr = find_attr ("length", 0);
2427   if (length_attr == 0)
2428     return;
2429
2430   if (! length_attr->is_numeric)
2431     fatal ("length attribute must be numeric.");
2432
2433   length_attr->is_const = 0;
2434   length_attr->is_special = 1;
2435
2436   /* Make each new attribute, in turn.  */
2437   for (i = 0; i < sizeof new_names / sizeof new_names[0]; i++)
2438     {
2439       make_internal_attr (new_names[i],
2440                           substitute_address (length_attr->default_val->value,
2441                                               no_address_fn[i], address_fn[i]),
2442                           0);
2443       new_attr = find_attr (new_names[i], 0);
2444       for (av = length_attr->first_value; av; av = av->next)
2445         for (ie = av->first_insn; ie; ie = ie->next)
2446           {
2447             new_av = get_attr_value (substitute_address (av->value,
2448                                                          no_address_fn[i],
2449                                                          address_fn[i]),
2450                                      new_attr, ie->insn_code);
2451             new_ie = (struct insn_ent *) oballoc (sizeof (struct insn_ent));
2452             new_ie->insn_code = ie->insn_code;
2453             new_ie->insn_index = ie->insn_index;
2454             insert_insn_ent (new_av, new_ie);
2455           }
2456     }
2457 }
2458
2459 /* Utility functions called from above routine.  */
2460
2461 static rtx
2462 identity_fn (exp)
2463      rtx exp;
2464 {
2465   return exp;
2466 }
2467
2468 static rtx
2469 zero_fn (exp)
2470      rtx exp ATTRIBUTE_UNUSED;
2471 {
2472   return make_numeric_value (0);
2473 }
2474
2475 static rtx
2476 one_fn (exp)
2477      rtx exp ATTRIBUTE_UNUSED;
2478 {
2479   return make_numeric_value (1);
2480 }
2481
2482 static rtx
2483 max_fn (exp)
2484      rtx exp;
2485 {
2486   int unknown;
2487   return make_numeric_value (max_attr_value (exp, &unknown));
2488 }
2489
2490 static void
2491 write_length_unit_log ()
2492 {
2493   struct attr_desc *length_attr = find_attr ("length", 0);
2494   struct attr_value *av;
2495   struct insn_ent *ie;
2496   unsigned int length_unit_log, length_or;
2497   int unknown = 0;
2498
2499   if (length_attr == 0)
2500     return;
2501   length_or = or_attr_value (length_attr->default_val->value, &unknown);
2502   for (av = length_attr->first_value; av; av = av->next)
2503     for (ie = av->first_insn; ie; ie = ie->next)
2504       length_or |= or_attr_value (av->value, &unknown);
2505
2506   if (unknown)
2507     length_unit_log = 0;
2508   else
2509     {
2510       length_or = ~length_or;
2511       for (length_unit_log = 0; length_or & 1; length_or >>= 1)
2512         length_unit_log++;
2513     }
2514   printf ("int length_unit_log = %u;\n", length_unit_log);
2515 }
2516 \f
2517 /* Take a COND expression and see if any of the conditions in it can be
2518    simplified.  If any are known true or known false for the particular insn
2519    code, the COND can be further simplified.
2520
2521    Also call ourselves on any COND operations that are values of this COND.
2522
2523    We do not modify EXP; rather, we make and return a new rtx.  */
2524
2525 static rtx
2526 simplify_cond (exp, insn_code, insn_index)
2527      rtx exp;
2528      int insn_code, insn_index;
2529 {
2530   int i, j;
2531   /* We store the desired contents here,
2532      then build a new expression if they don't match EXP.  */
2533   rtx defval = XEXP (exp, 1);
2534   rtx new_defval = XEXP (exp, 1);
2535   int len = XVECLEN (exp, 0);
2536   rtx *tests = (rtx *) alloca (len * sizeof (rtx));
2537   int allsame = 1;
2538   char *first_spacer;
2539
2540   /* This lets us free all storage allocated below, if appropriate.  */
2541   first_spacer = (char *) obstack_finish (rtl_obstack);
2542
2543   bcopy ((char *) XVEC (exp, 0)->elem, (char *) tests, len * sizeof (rtx));
2544
2545   /* See if default value needs simplification.  */
2546   if (GET_CODE (defval) == COND)
2547     new_defval = simplify_cond (defval, insn_code, insn_index);
2548
2549   /* Simplify the subexpressions, and see what tests we can get rid of.  */
2550
2551   for (i = 0; i < len; i += 2)
2552     {
2553       rtx newtest, newval;
2554
2555       /* Simplify this test.  */
2556       newtest = SIMPLIFY_TEST_EXP (tests[i], insn_code, insn_index);
2557       tests[i] = newtest;
2558
2559       newval = tests[i + 1];
2560       /* See if this value may need simplification.  */
2561       if (GET_CODE (newval) == COND)
2562         newval = simplify_cond (newval, insn_code, insn_index);
2563
2564       /* Look for ways to delete or combine this test.  */
2565       if (newtest == true_rtx)
2566         {
2567           /* If test is true, make this value the default
2568              and discard this + any following tests.  */
2569           len = i;
2570           defval = tests[i + 1];
2571           new_defval = newval;
2572         }
2573
2574       else if (newtest == false_rtx)
2575         {
2576           /* If test is false, discard it and its value.  */
2577           for (j = i; j < len - 2; j++)
2578             tests[j] = tests[j + 2];
2579           len -= 2;
2580         }
2581
2582       else if (i > 0 && attr_equal_p (newval, tests[i - 1]))
2583         {
2584           /* If this value and the value for the prev test are the same,
2585              merge the tests.  */
2586
2587           tests[i - 2]
2588             = insert_right_side (IOR, tests[i - 2], newtest,
2589                                  insn_code, insn_index);
2590
2591           /* Delete this test/value.  */
2592           for (j = i; j < len - 2; j++)
2593             tests[j] = tests[j + 2];
2594           len -= 2;
2595         }
2596
2597       else
2598         tests[i + 1] = newval;
2599     }
2600
2601   /* If the last test in a COND has the same value
2602      as the default value, that test isn't needed.  */
2603
2604   while (len > 0 && attr_equal_p (tests[len - 1], new_defval))
2605     len -= 2;
2606
2607   /* See if we changed anything.  */
2608   if (len != XVECLEN (exp, 0) || new_defval != XEXP (exp, 1))
2609     allsame = 0;
2610   else
2611     for (i = 0; i < len; i++)
2612       if (! attr_equal_p (tests[i], XVECEXP (exp, 0, i)))
2613         {
2614           allsame = 0;
2615           break;
2616         }
2617
2618   if (len == 0)
2619     {
2620       if (!ggc_p)
2621         obstack_free (rtl_obstack, first_spacer);
2622       if (GET_CODE (defval) == COND)
2623         return simplify_cond (defval, insn_code, insn_index);
2624       return defval;
2625     }
2626   else if (allsame)
2627     {
2628       if (!ggc_p)
2629         obstack_free (rtl_obstack, first_spacer);
2630       return exp;
2631     }
2632   else
2633     {
2634       rtx newexp = rtx_alloc (COND);
2635
2636       XVEC (newexp, 0) = rtvec_alloc (len);
2637       bcopy ((char *) tests, (char *) XVEC (newexp, 0)->elem,
2638              len * sizeof (rtx));
2639       XEXP (newexp, 1) = new_defval;
2640       return newexp;
2641     }
2642 }
2643 \f
2644 /* Remove an insn entry from an attribute value.  */
2645
2646 static void
2647 remove_insn_ent (av, ie)
2648      struct attr_value *av;
2649      struct insn_ent *ie;
2650 {
2651   struct insn_ent *previe;
2652
2653   if (av->first_insn == ie)
2654     av->first_insn = ie->next;
2655   else
2656     {
2657       for (previe = av->first_insn; previe->next != ie; previe = previe->next)
2658         ;
2659       previe->next = ie->next;
2660     }
2661
2662   av->num_insns--;
2663   if (ie->insn_code == -1)
2664     av->has_asm_insn = 0;
2665
2666   num_insn_ents--;
2667 }
2668
2669 /* Insert an insn entry in an attribute value list.  */
2670
2671 static void
2672 insert_insn_ent (av, ie)
2673      struct attr_value *av;
2674      struct insn_ent *ie;
2675 {
2676   ie->next = av->first_insn;
2677   av->first_insn = ie;
2678   av->num_insns++;
2679   if (ie->insn_code == -1)
2680     av->has_asm_insn = 1;
2681
2682   num_insn_ents++;
2683 }
2684 \f
2685 /* This is a utility routine to take an expression that is a tree of either
2686    AND or IOR expressions and insert a new term.  The new term will be
2687    inserted at the right side of the first node whose code does not match
2688    the root.  A new node will be created with the root's code.  Its left
2689    side will be the old right side and its right side will be the new
2690    term.
2691
2692    If the `term' is itself a tree, all its leaves will be inserted.  */
2693
2694 static rtx
2695 insert_right_side (code, exp, term, insn_code, insn_index)
2696      enum rtx_code code;
2697      rtx exp;
2698      rtx term;
2699      int insn_code, insn_index;
2700 {
2701   rtx newexp;
2702
2703   /* Avoid consing in some special cases.  */
2704   if (code == AND && term == true_rtx)
2705     return exp;
2706   if (code == AND && term == false_rtx)
2707     return false_rtx;
2708   if (code == AND && exp == true_rtx)
2709     return term;
2710   if (code == AND && exp == false_rtx)
2711     return false_rtx;
2712   if (code == IOR && term == true_rtx)
2713     return true_rtx;
2714   if (code == IOR && term == false_rtx)
2715     return exp;
2716   if (code == IOR && exp == true_rtx)
2717     return true_rtx;
2718   if (code == IOR && exp == false_rtx)
2719     return term;
2720   if (attr_equal_p (exp, term))
2721     return exp;
2722
2723   if (GET_CODE (term) == code)
2724     {
2725       exp = insert_right_side (code, exp, XEXP (term, 0),
2726                                insn_code, insn_index);
2727       exp = insert_right_side (code, exp, XEXP (term, 1),
2728                                insn_code, insn_index);
2729
2730       return exp;
2731     }
2732
2733   if (GET_CODE (exp) == code)
2734     {
2735       rtx new = insert_right_side (code, XEXP (exp, 1),
2736                                    term, insn_code, insn_index);
2737       if (new != XEXP (exp, 1))
2738         /* Make a copy of this expression and call recursively.  */
2739         newexp = attr_rtx (code, XEXP (exp, 0), new);
2740       else
2741         newexp = exp;
2742     }
2743   else
2744     {
2745       /* Insert the new term.  */
2746       newexp = attr_rtx (code, exp, term);
2747     }
2748
2749   return SIMPLIFY_TEST_EXP (newexp, insn_code, insn_index);
2750 }
2751 \f
2752 /* If we have an expression which AND's a bunch of
2753         (not (eq_attrq "alternative" "n"))
2754    terms, we may have covered all or all but one of the possible alternatives.
2755    If so, we can optimize.  Similarly for IOR's of EQ_ATTR.
2756
2757    This routine is passed an expression and either AND or IOR.  It returns a
2758    bitmask indicating which alternatives are mentioned within EXP.  */
2759
2760 static int
2761 compute_alternative_mask (exp, code)
2762      rtx exp;
2763      enum rtx_code code;
2764 {
2765   const char *string;
2766   if (GET_CODE (exp) == code)
2767     return compute_alternative_mask (XEXP (exp, 0), code)
2768            | compute_alternative_mask (XEXP (exp, 1), code);
2769
2770   else if (code == AND && GET_CODE (exp) == NOT
2771            && GET_CODE (XEXP (exp, 0)) == EQ_ATTR
2772            && XSTR (XEXP (exp, 0), 0) == alternative_name)
2773     string = XSTR (XEXP (exp, 0), 1);
2774
2775   else if (code == IOR && GET_CODE (exp) == EQ_ATTR
2776            && XSTR (exp, 0) == alternative_name)
2777     string = XSTR (exp, 1);
2778
2779   else
2780     return 0;
2781
2782   if (string[1] == 0)
2783     return 1 << (string[0] - '0');
2784   return 1 << atoi (string);
2785 }
2786
2787 /* Given I, a single-bit mask, return RTX to compare the `alternative'
2788    attribute with the value represented by that bit.  */
2789
2790 static rtx
2791 make_alternative_compare (mask)
2792      int mask;
2793 {
2794   rtx newexp;
2795   int i;
2796
2797   /* Find the bit.  */
2798   for (i = 0; (mask & (1 << i)) == 0; i++)
2799     ;
2800
2801   newexp = attr_rtx (EQ_ATTR, alternative_name, attr_numeral (i));
2802   RTX_UNCHANGING_P (newexp) = 1;
2803
2804   return newexp;
2805 }
2806 \f
2807 /* If we are processing an (eq_attr "attr" "value") test, we find the value
2808    of "attr" for this insn code.  From that value, we can compute a test
2809    showing when the EQ_ATTR will be true.  This routine performs that
2810    computation.  If a test condition involves an address, we leave the EQ_ATTR
2811    intact because addresses are only valid for the `length' attribute.
2812
2813    EXP is the EQ_ATTR expression and VALUE is the value of that attribute
2814    for the insn corresponding to INSN_CODE and INSN_INDEX.  */
2815
2816 static rtx
2817 evaluate_eq_attr (exp, value, insn_code, insn_index)
2818      rtx exp;
2819      rtx value;
2820      int insn_code, insn_index;
2821 {
2822   rtx orexp, andexp;
2823   rtx right;
2824   rtx newexp;
2825   int i;
2826
2827   if (GET_CODE (value) == CONST_STRING)
2828     {
2829       if (! strcmp (XSTR (value, 0), XSTR (exp, 1)))
2830         newexp = true_rtx;
2831       else
2832         newexp = false_rtx;
2833     }
2834   else if (GET_CODE (value) == SYMBOL_REF)
2835     {
2836       char *p, *string;
2837
2838       if (GET_CODE (exp) != EQ_ATTR)
2839         abort();
2840
2841       string = (char *) alloca (2 + strlen (XSTR (exp, 0))
2842                                 + strlen (XSTR (exp, 1)));
2843       strcpy (string, XSTR (exp, 0));
2844       strcat (string, "_");
2845       strcat (string, XSTR (exp, 1));
2846       for (p = string; *p ; p++)
2847         *p = TOUPPER (*p);
2848
2849       newexp = attr_rtx (EQ, value,
2850                          attr_rtx (SYMBOL_REF,
2851                                    attr_string(string, strlen(string))));
2852     }
2853   else if (GET_CODE (value) == COND)
2854     {
2855       /* We construct an IOR of all the cases for which the requested attribute
2856          value is present.  Since we start with FALSE, if it is not present,
2857          FALSE will be returned.
2858
2859          Each case is the AND of the NOT's of the previous conditions with the
2860          current condition; in the default case the current condition is TRUE.
2861
2862          For each possible COND value, call ourselves recursively.
2863
2864          The extra TRUE and FALSE expressions will be eliminated by another
2865          call to the simplification routine.  */
2866
2867       orexp = false_rtx;
2868       andexp = true_rtx;
2869
2870       if (current_alternative_string)
2871         clear_struct_flag (value);
2872
2873       for (i = 0; i < XVECLEN (value, 0); i += 2)
2874         {
2875           rtx this = SIMPLIFY_TEST_EXP (XVECEXP (value, 0, i),
2876                                         insn_code, insn_index);
2877
2878           SIMPLIFY_ALTERNATIVE (this);
2879
2880           right = insert_right_side (AND, andexp, this,
2881                                      insn_code, insn_index);
2882           right = insert_right_side (AND, right,
2883                                      evaluate_eq_attr (exp,
2884                                                        XVECEXP (value, 0,
2885                                                                 i + 1),
2886                                                        insn_code, insn_index),
2887                                      insn_code, insn_index);
2888           orexp = insert_right_side (IOR, orexp, right,
2889                                      insn_code, insn_index);
2890
2891           /* Add this condition into the AND expression.  */
2892           newexp = attr_rtx (NOT, this);
2893           andexp = insert_right_side (AND, andexp, newexp,
2894                                       insn_code, insn_index);
2895         }
2896
2897       /* Handle the default case.  */
2898       right = insert_right_side (AND, andexp,
2899                                  evaluate_eq_attr (exp, XEXP (value, 1),
2900                                                    insn_code, insn_index),
2901                                  insn_code, insn_index);
2902       newexp = insert_right_side (IOR, orexp, right, insn_code, insn_index);
2903     }
2904   else
2905     abort ();
2906
2907   /* If uses an address, must return original expression.  But set the
2908      RTX_UNCHANGING_P bit so we don't try to simplify it again.  */
2909
2910   address_used = 0;
2911   walk_attr_value (newexp);
2912
2913   if (address_used)
2914     {
2915       /* This had `&& current_alternative_string', which seems to be wrong.  */
2916       if (! RTX_UNCHANGING_P (exp))
2917         return copy_rtx_unchanging (exp);
2918       return exp;
2919     }
2920   else
2921     return newexp;
2922 }
2923 \f
2924 /* This routine is called when an AND of a term with a tree of AND's is
2925    encountered.  If the term or its complement is present in the tree, it
2926    can be replaced with TRUE or FALSE, respectively.
2927
2928    Note that (eq_attr "att" "v1") and (eq_attr "att" "v2") cannot both
2929    be true and hence are complementary.
2930
2931    There is one special case:  If we see
2932         (and (not (eq_attr "att" "v1"))
2933              (eq_attr "att" "v2"))
2934    this can be replaced by (eq_attr "att" "v2").  To do this we need to
2935    replace the term, not anything in the AND tree.  So we pass a pointer to
2936    the term.  */
2937
2938 static rtx
2939 simplify_and_tree (exp, pterm, insn_code, insn_index)
2940      rtx exp;
2941      rtx *pterm;
2942      int insn_code, insn_index;
2943 {
2944   rtx left, right;
2945   rtx newexp;
2946   rtx temp;
2947   int left_eliminates_term, right_eliminates_term;
2948
2949   if (GET_CODE (exp) == AND)
2950     {
2951       left = simplify_and_tree (XEXP (exp, 0), pterm,  insn_code, insn_index);
2952       right = simplify_and_tree (XEXP (exp, 1), pterm, insn_code, insn_index);
2953       if (left != XEXP (exp, 0) || right != XEXP (exp, 1))
2954         {
2955           newexp = attr_rtx (GET_CODE (exp), left, right);
2956
2957           exp = SIMPLIFY_TEST_EXP (newexp, insn_code, insn_index);
2958         }
2959     }
2960
2961   else if (GET_CODE (exp) == IOR)
2962     {
2963       /* For the IOR case, we do the same as above, except that we can
2964          only eliminate `term' if both sides of the IOR would do so.  */
2965       temp = *pterm;
2966       left = simplify_and_tree (XEXP (exp, 0), &temp,  insn_code, insn_index);
2967       left_eliminates_term = (temp == true_rtx);
2968
2969       temp = *pterm;
2970       right = simplify_and_tree (XEXP (exp, 1), &temp, insn_code, insn_index);
2971       right_eliminates_term = (temp == true_rtx);
2972
2973       if (left_eliminates_term && right_eliminates_term)
2974         *pterm = true_rtx;
2975
2976       if (left != XEXP (exp, 0) || right != XEXP (exp, 1))
2977         {
2978           newexp = attr_rtx (GET_CODE (exp), left, right);
2979
2980           exp = SIMPLIFY_TEST_EXP (newexp, insn_code, insn_index);
2981         }
2982     }
2983
2984   /* Check for simplifications.  Do some extra checking here since this
2985      routine is called so many times.  */
2986
2987   if (exp == *pterm)
2988     return true_rtx;
2989
2990   else if (GET_CODE (exp) == NOT && XEXP (exp, 0) == *pterm)
2991     return false_rtx;
2992
2993   else if (GET_CODE (*pterm) == NOT && exp == XEXP (*pterm, 0))
2994     return false_rtx;
2995
2996   else if (GET_CODE (exp) == EQ_ATTR && GET_CODE (*pterm) == EQ_ATTR)
2997     {
2998       if (XSTR (exp, 0) != XSTR (*pterm, 0))
2999         return exp;
3000
3001       if (! strcmp (XSTR (exp, 1), XSTR (*pterm, 1)))
3002         return true_rtx;
3003       else
3004         return false_rtx;
3005     }
3006
3007   else if (GET_CODE (*pterm) == EQ_ATTR && GET_CODE (exp) == NOT
3008            && GET_CODE (XEXP (exp, 0)) == EQ_ATTR)
3009     {
3010       if (XSTR (*pterm, 0) != XSTR (XEXP (exp, 0), 0))
3011         return exp;
3012
3013       if (! strcmp (XSTR (*pterm, 1), XSTR (XEXP (exp, 0), 1)))
3014         return false_rtx;
3015       else
3016         return true_rtx;
3017     }
3018
3019   else if (GET_CODE (exp) == EQ_ATTR && GET_CODE (*pterm) == NOT
3020            && GET_CODE (XEXP (*pterm, 0)) == EQ_ATTR)
3021     {
3022       if (XSTR (exp, 0) != XSTR (XEXP (*pterm, 0), 0))
3023         return exp;
3024
3025       if (! strcmp (XSTR (exp, 1), XSTR (XEXP (*pterm, 0), 1)))
3026         return false_rtx;
3027       else
3028         *pterm = true_rtx;
3029     }
3030
3031   else if (GET_CODE (exp) == NOT && GET_CODE (*pterm) == NOT)
3032     {
3033       if (attr_equal_p (XEXP (exp, 0), XEXP (*pterm, 0)))
3034         return true_rtx;
3035     }
3036
3037   else if (GET_CODE (exp) == NOT)
3038     {
3039       if (attr_equal_p (XEXP (exp, 0), *pterm))
3040         return false_rtx;
3041     }
3042
3043   else if (GET_CODE (*pterm) == NOT)
3044     {
3045       if (attr_equal_p (XEXP (*pterm, 0), exp))
3046         return false_rtx;
3047     }
3048
3049   else if (attr_equal_p (exp, *pterm))
3050     return true_rtx;
3051
3052   return exp;
3053 }
3054 \f
3055 /* Similar to `simplify_and_tree', but for IOR trees.  */
3056
3057 static rtx
3058 simplify_or_tree (exp, pterm, insn_code, insn_index)
3059      rtx exp;
3060      rtx *pterm;
3061      int insn_code, insn_index;
3062 {
3063   rtx left, right;
3064   rtx newexp;
3065   rtx temp;
3066   int left_eliminates_term, right_eliminates_term;
3067
3068   if (GET_CODE (exp) == IOR)
3069     {
3070       left = simplify_or_tree (XEXP (exp, 0), pterm,  insn_code, insn_index);
3071       right = simplify_or_tree (XEXP (exp, 1), pterm, insn_code, insn_index);
3072       if (left != XEXP (exp, 0) || right != XEXP (exp, 1))
3073         {
3074           newexp = attr_rtx (GET_CODE (exp), left, right);
3075
3076           exp = SIMPLIFY_TEST_EXP (newexp, insn_code, insn_index);
3077         }
3078     }
3079
3080   else if (GET_CODE (exp) == AND)
3081     {
3082       /* For the AND case, we do the same as above, except that we can
3083          only eliminate `term' if both sides of the AND would do so.  */
3084       temp = *pterm;
3085       left = simplify_or_tree (XEXP (exp, 0), &temp,  insn_code, insn_index);
3086       left_eliminates_term = (temp == false_rtx);
3087
3088       temp = *pterm;
3089       right = simplify_or_tree (XEXP (exp, 1), &temp, insn_code, insn_index);
3090       right_eliminates_term = (temp == false_rtx);
3091
3092       if (left_eliminates_term && right_eliminates_term)
3093         *pterm = false_rtx;
3094
3095       if (left != XEXP (exp, 0) || right != XEXP (exp, 1))
3096         {
3097           newexp = attr_rtx (GET_CODE (exp), left, right);
3098
3099           exp = SIMPLIFY_TEST_EXP (newexp, insn_code, insn_index);
3100         }
3101     }
3102
3103   if (attr_equal_p (exp, *pterm))
3104     return false_rtx;
3105
3106   else if (GET_CODE (exp) == NOT && attr_equal_p (XEXP (exp, 0), *pterm))
3107     return true_rtx;
3108
3109   else if (GET_CODE (*pterm) == NOT && attr_equal_p (XEXP (*pterm, 0), exp))
3110     return true_rtx;
3111
3112   else if (GET_CODE (*pterm) == EQ_ATTR && GET_CODE (exp) == NOT
3113            && GET_CODE (XEXP (exp, 0)) == EQ_ATTR
3114            && XSTR (*pterm, 0) == XSTR (XEXP (exp, 0), 0))
3115     *pterm = false_rtx;
3116
3117   else if (GET_CODE (exp) == EQ_ATTR && GET_CODE (*pterm) == NOT
3118            && GET_CODE (XEXP (*pterm, 0)) == EQ_ATTR
3119            && XSTR (exp, 0) == XSTR (XEXP (*pterm, 0), 0))
3120     return false_rtx;
3121
3122   return exp;
3123 }
3124 \f
3125 /* Given an expression, see if it can be simplified for a particular insn
3126    code based on the values of other attributes being tested.  This can
3127    eliminate nested get_attr_... calls.
3128
3129    Note that if an endless recursion is specified in the patterns, the
3130    optimization will loop.  However, it will do so in precisely the cases where
3131    an infinite recursion loop could occur during compilation.  It's better that
3132    it occurs here!  */
3133
3134 static rtx
3135 simplify_test_exp (exp, insn_code, insn_index)
3136      rtx exp;
3137      int insn_code, insn_index;
3138 {
3139   rtx left, right;
3140   struct attr_desc *attr;
3141   struct attr_value *av;
3142   struct insn_ent *ie;
3143   int i;
3144   rtx newexp = exp;
3145   char *spacer = (char *) obstack_finish (rtl_obstack);
3146
3147   /* Don't re-simplify something we already simplified.  */
3148   if (RTX_UNCHANGING_P (exp) || MEM_IN_STRUCT_P (exp))
3149     return exp;
3150
3151   switch (GET_CODE (exp))
3152     {
3153     case AND:
3154       left = SIMPLIFY_TEST_EXP (XEXP (exp, 0), insn_code, insn_index);
3155       SIMPLIFY_ALTERNATIVE (left);
3156       if (left == false_rtx)
3157         {
3158           if (!ggc_p)
3159             obstack_free (rtl_obstack, spacer);
3160           return false_rtx;
3161         }
3162       right = SIMPLIFY_TEST_EXP (XEXP (exp, 1), insn_code, insn_index);
3163       SIMPLIFY_ALTERNATIVE (right);
3164       if (left == false_rtx)
3165         {
3166           if (!ggc_p)
3167             obstack_free (rtl_obstack, spacer);
3168           return false_rtx;
3169         }
3170
3171       /* If either side is an IOR and we have (eq_attr "alternative" ..")
3172          present on both sides, apply the distributive law since this will
3173          yield simplifications.  */
3174       if ((GET_CODE (left) == IOR || GET_CODE (right) == IOR)
3175           && compute_alternative_mask (left, IOR)
3176           && compute_alternative_mask (right, IOR))
3177         {
3178           if (GET_CODE (left) == IOR)
3179             {
3180               rtx tem = left;
3181               left = right;
3182               right = tem;
3183             }
3184
3185           newexp = attr_rtx (IOR,
3186                              attr_rtx (AND, left, XEXP (right, 0)),
3187                              attr_rtx (AND, left, XEXP (right, 1)));
3188
3189           return SIMPLIFY_TEST_EXP (newexp, insn_code, insn_index);
3190         }
3191
3192       /* Try with the term on both sides.  */
3193       right = simplify_and_tree (right, &left, insn_code, insn_index);
3194       if (left == XEXP (exp, 0) && right == XEXP (exp, 1))
3195         left = simplify_and_tree (left, &right, insn_code, insn_index);
3196
3197       if (left == false_rtx || right == false_rtx)
3198         {
3199           if (!ggc_p)
3200             obstack_free (rtl_obstack, spacer);
3201           return false_rtx;
3202         }
3203       else if (left == true_rtx)
3204         {
3205           return right;
3206         }
3207       else if (right == true_rtx)
3208         {
3209           return left;
3210         }
3211       /* See if all or all but one of the insn's alternatives are specified
3212          in this tree.  Optimize if so.  */
3213
3214       else if (insn_code >= 0
3215                && (GET_CODE (left) == AND
3216                    || (GET_CODE (left) == NOT
3217                        && GET_CODE (XEXP (left, 0)) == EQ_ATTR
3218                        && XSTR (XEXP (left, 0), 0) == alternative_name)
3219                    || GET_CODE (right) == AND
3220                    || (GET_CODE (right) == NOT
3221                        && GET_CODE (XEXP (right, 0)) == EQ_ATTR
3222                        && XSTR (XEXP (right, 0), 0) == alternative_name)))
3223         {
3224           i = compute_alternative_mask (exp, AND);
3225           if (i & ~insn_alternatives[insn_code])
3226             fatal ("Invalid alternative specified for pattern number %d",
3227                    insn_index);
3228
3229           /* If all alternatives are excluded, this is false.  */
3230           i ^= insn_alternatives[insn_code];
3231           if (i == 0)
3232             return false_rtx;
3233           else if ((i & (i - 1)) == 0 && insn_alternatives[insn_code] > 1)
3234             {
3235               /* If just one excluded, AND a comparison with that one to the
3236                  front of the tree.  The others will be eliminated by
3237                  optimization.  We do not want to do this if the insn has one
3238                  alternative and we have tested none of them!  */
3239               left = make_alternative_compare (i);
3240               right = simplify_and_tree (exp, &left, insn_code, insn_index);
3241               newexp = attr_rtx (AND, left, right);
3242
3243               return SIMPLIFY_TEST_EXP (newexp, insn_code, insn_index);
3244             }
3245         }
3246
3247       if (left != XEXP (exp, 0) || right != XEXP (exp, 1))
3248         {
3249           newexp = attr_rtx (AND, left, right);
3250           return SIMPLIFY_TEST_EXP (newexp, insn_code, insn_index);
3251         }
3252       break;
3253
3254     case IOR:
3255       left = SIMPLIFY_TEST_EXP (XEXP (exp, 0), insn_code, insn_index);
3256       SIMPLIFY_ALTERNATIVE (left);
3257       if (left == true_rtx)
3258         {
3259           if (!ggc_p)
3260             obstack_free (rtl_obstack, spacer);
3261           return true_rtx;
3262         }
3263       right = SIMPLIFY_TEST_EXP (XEXP (exp, 1), insn_code, insn_index);
3264       SIMPLIFY_ALTERNATIVE (right);
3265       if (right == true_rtx)
3266         {
3267           if (!ggc_p)
3268             obstack_free (rtl_obstack, spacer);
3269           return true_rtx;
3270         }
3271
3272       right = simplify_or_tree (right, &left, insn_code, insn_index);
3273       if (left == XEXP (exp, 0) && right == XEXP (exp, 1))
3274         left = simplify_or_tree (left, &right, insn_code, insn_index);
3275
3276       if (right == true_rtx || left == true_rtx)
3277         {
3278           if (!ggc_p)
3279             obstack_free (rtl_obstack, spacer);
3280           return true_rtx;
3281         }
3282       else if (left == false_rtx)
3283         {
3284           return right;
3285         }
3286       else if (right == false_rtx)
3287         {
3288           return left;
3289         }
3290
3291       /* Test for simple cases where the distributive law is useful.  I.e.,
3292             convert (ior (and (x) (y))
3293                          (and (x) (z)))
3294             to      (and (x)
3295                          (ior (y) (z)))
3296        */
3297
3298       else if (GET_CODE (left) == AND && GET_CODE (right) == AND
3299           && attr_equal_p (XEXP (left, 0), XEXP (right, 0)))
3300         {
3301           newexp = attr_rtx (IOR, XEXP (left, 1), XEXP (right, 1));
3302
3303           left = XEXP (left, 0);
3304           right = newexp;
3305           newexp = attr_rtx (AND, left, right);
3306           return SIMPLIFY_TEST_EXP (newexp, insn_code, insn_index);
3307         }
3308
3309       /* See if all or all but one of the insn's alternatives are specified
3310          in this tree.  Optimize if so.  */
3311
3312       else if (insn_code >= 0
3313           && (GET_CODE (left) == IOR
3314               || (GET_CODE (left) == EQ_ATTR
3315                   && XSTR (left, 0) == alternative_name)
3316               || GET_CODE (right) == IOR
3317               || (GET_CODE (right) == EQ_ATTR
3318                   && XSTR (right, 0) == alternative_name)))
3319         {
3320           i = compute_alternative_mask (exp, IOR);
3321           if (i & ~insn_alternatives[insn_code])
3322             fatal ("Invalid alternative specified for pattern number %d",
3323                    insn_index);
3324
3325           /* If all alternatives are included, this is true.  */
3326           i ^= insn_alternatives[insn_code];
3327           if (i == 0)
3328             return true_rtx;
3329           else if ((i & (i - 1)) == 0 && insn_alternatives[insn_code] > 1)
3330             {
3331               /* If just one excluded, IOR a comparison with that one to the
3332                  front of the tree.  The others will be eliminated by
3333                  optimization.  We do not want to do this if the insn has one
3334                  alternative and we have tested none of them!  */
3335               left = make_alternative_compare (i);
3336               right = simplify_and_tree (exp, &left, insn_code, insn_index);
3337               newexp = attr_rtx (IOR, attr_rtx (NOT, left), right);
3338
3339               return SIMPLIFY_TEST_EXP (newexp, insn_code, insn_index);
3340             }
3341         }
3342
3343       if (left != XEXP (exp, 0) || right != XEXP (exp, 1))
3344         {
3345           newexp = attr_rtx (IOR, left, right);
3346           return SIMPLIFY_TEST_EXP (newexp, insn_code, insn_index);
3347         }
3348       break;
3349
3350     case NOT:
3351       if (GET_CODE (XEXP (exp, 0)) == NOT)
3352         {
3353           left = SIMPLIFY_TEST_EXP (XEXP (XEXP (exp, 0), 0),
3354                                     insn_code, insn_index);
3355           SIMPLIFY_ALTERNATIVE (left);
3356           return left;
3357         }
3358
3359       left = SIMPLIFY_TEST_EXP (XEXP (exp, 0), insn_code, insn_index);
3360       SIMPLIFY_ALTERNATIVE (left);
3361       if (GET_CODE (left) == NOT)
3362         return XEXP (left, 0);
3363
3364       if (left == false_rtx)
3365         {
3366           if (!ggc_p)
3367             obstack_free (rtl_obstack, spacer);
3368           return true_rtx;
3369         }
3370       else if (left == true_rtx)
3371         {
3372           if (!ggc_p)
3373             obstack_free (rtl_obstack, spacer);
3374           return false_rtx;
3375         }
3376
3377       /* Try to apply De`Morgan's laws.  */
3378       else if (GET_CODE (left) == IOR)
3379         {
3380           newexp = attr_rtx (AND,
3381                              attr_rtx (NOT, XEXP (left, 0)),
3382                              attr_rtx (NOT, XEXP (left, 1)));
3383
3384           newexp = SIMPLIFY_TEST_EXP (newexp, insn_code, insn_index);
3385         }
3386       else if (GET_CODE (left) == AND)
3387         {
3388           newexp = attr_rtx (IOR,
3389                              attr_rtx (NOT, XEXP (left, 0)),
3390                              attr_rtx (NOT, XEXP (left, 1)));
3391
3392           newexp = SIMPLIFY_TEST_EXP (newexp, insn_code, insn_index);
3393         }
3394       else if (left != XEXP (exp, 0))
3395         {
3396           newexp = attr_rtx (NOT, left);
3397         }
3398       break;
3399
3400     case EQ_ATTR:
3401       if (current_alternative_string && XSTR (exp, 0) == alternative_name)
3402         return (XSTR (exp, 1) == current_alternative_string
3403                 ? true_rtx : false_rtx);
3404
3405       /* Look at the value for this insn code in the specified attribute.
3406          We normally can replace this comparison with the condition that
3407          would give this insn the values being tested for.   */
3408       if (XSTR (exp, 0) != alternative_name
3409           && (attr = find_attr (XSTR (exp, 0), 0)) != NULL)
3410         for (av = attr->first_value; av; av = av->next)
3411           for (ie = av->first_insn; ie; ie = ie->next)
3412             if (ie->insn_code == insn_code)
3413               return evaluate_eq_attr (exp, av->value, insn_code, insn_index);
3414       break;
3415
3416     default:
3417       break;
3418     }
3419
3420   /* We have already simplified this expression.  Simplifying it again
3421      won't buy anything unless we weren't given a valid insn code
3422      to process (i.e., we are canonicalizing something.).  */
3423   if (insn_code != -2 /* Seems wrong: && current_alternative_string.  */
3424       && ! RTX_UNCHANGING_P (newexp))
3425     return copy_rtx_unchanging (newexp);
3426
3427   return newexp;
3428 }
3429 \f
3430 /* Optimize the attribute lists by seeing if we can determine conditional
3431    values from the known values of other attributes.  This will save subroutine
3432    calls during the compilation.  */
3433
3434 static void
3435 optimize_attrs ()
3436 {
3437   struct attr_desc *attr;
3438   struct attr_value *av;
3439   struct insn_ent *ie;
3440   rtx newexp;
3441   int something_changed = 1;
3442   int i;
3443   struct attr_value_list { struct attr_value *av;
3444                            struct insn_ent *ie;
3445                            struct attr_desc * attr;
3446                            struct attr_value_list *next; };
3447   struct attr_value_list **insn_code_values;
3448   struct attr_value_list *ivbuf;
3449   struct attr_value_list *iv;
3450
3451   /* For each insn code, make a list of all the insn_ent's for it,
3452      for all values for all attributes.  */
3453
3454   if (num_insn_ents == 0)
3455     return;
3456
3457   /* Make 2 extra elements, for "code" values -2 and -1.  */
3458   insn_code_values
3459     = (struct attr_value_list **) alloca ((insn_code_number + 2)
3460                                           * sizeof (struct attr_value_list *));
3461   bzero ((char *) insn_code_values,
3462          (insn_code_number + 2) * sizeof (struct attr_value_list *));
3463
3464   /* Offset the table address so we can index by -2 or -1.  */
3465   insn_code_values += 2;
3466
3467   /* Allocate the attr_value_list structures using xmalloc rather than
3468      alloca, because using alloca can overflow the maximum permitted
3469      stack limit on SPARC Lynx.  */
3470   iv = ivbuf = ((struct attr_value_list *)
3471                 xmalloc (num_insn_ents * sizeof (struct attr_value_list)));
3472
3473   for (i = 0; i < MAX_ATTRS_INDEX; i++)
3474     for (attr = attrs[i]; attr; attr = attr->next)
3475       for (av = attr->first_value; av; av = av->next)
3476         for (ie = av->first_insn; ie; ie = ie->next)
3477           {
3478             iv->attr = attr;
3479             iv->av = av;
3480             iv->ie = ie;
3481             iv->next = insn_code_values[ie->insn_code];
3482             insn_code_values[ie->insn_code] = iv;
3483             iv++;
3484           }
3485
3486   /* Sanity check on num_insn_ents.  */
3487   if (iv != ivbuf + num_insn_ents)
3488     abort ();
3489
3490   /* Process one insn code at a time.  */
3491   for (i = -2; i < insn_code_number; i++)
3492     {
3493       /* Clear the MEM_IN_STRUCT_P flag everywhere relevant.
3494          We use it to mean "already simplified for this insn".  */
3495       for (iv = insn_code_values[i]; iv; iv = iv->next)
3496         clear_struct_flag (iv->av->value);
3497
3498       /* Loop until nothing changes for one iteration.  */
3499       something_changed = 1;
3500       while (something_changed)
3501         {
3502           something_changed = 0;
3503           for (iv = insn_code_values[i]; iv; iv = iv->next)
3504             {
3505               struct obstack *old = rtl_obstack;
3506               char *spacer = (char *) obstack_finish (temp_obstack);
3507
3508               attr = iv->attr;
3509               av = iv->av;
3510               ie = iv->ie;
3511               if (GET_CODE (av->value) != COND)
3512                 continue;
3513
3514               rtl_obstack = temp_obstack;
3515 #if 0 /* This was intended as a speed up, but it was slower.  */
3516               if (insn_n_alternatives[ie->insn_code] > 6
3517                   && count_sub_rtxs (av->value, 200) >= 200)
3518                 newexp = simplify_by_alternatives (av->value, ie->insn_code,
3519                                                    ie->insn_index);
3520               else
3521 #endif
3522                 newexp = simplify_cond (av->value, ie->insn_code,
3523                                         ie->insn_index);
3524
3525               rtl_obstack = old;
3526               if (newexp != av->value)
3527                 {
3528                   newexp = attr_copy_rtx (newexp);
3529                   remove_insn_ent (av, ie);
3530                   av = get_attr_value (newexp, attr, ie->insn_code);
3531                   iv->av = av;
3532                   insert_insn_ent (av, ie);
3533                   something_changed = 1;
3534                 }
3535               if (!ggc_p)
3536                 obstack_free (temp_obstack, spacer);
3537             }
3538         }
3539     }
3540
3541   free (ivbuf);
3542 }
3543
3544 #if 0
3545 static rtx
3546 simplify_by_alternatives (exp, insn_code, insn_index)
3547      rtx exp;
3548      int insn_code, insn_index;
3549 {
3550   int i;
3551   int len = insn_n_alternatives[insn_code];
3552   rtx newexp = rtx_alloc (COND);
3553   rtx ultimate;
3554
3555
3556   XVEC (newexp, 0) = rtvec_alloc (len * 2);
3557
3558   /* It will not matter what value we use as the default value
3559      of the new COND, since that default will never be used.
3560      Choose something of the right type.  */
3561   for (ultimate = exp; GET_CODE (ultimate) == COND;)
3562     ultimate = XEXP (ultimate, 1);
3563   XEXP (newexp, 1) = ultimate;
3564
3565   for (i = 0; i < insn_n_alternatives[insn_code]; i++)
3566     {
3567       current_alternative_string = attr_numeral (i);
3568       XVECEXP (newexp, 0, i * 2) = make_alternative_compare (1 << i);
3569       XVECEXP (newexp, 0, i * 2 + 1)
3570         = simplify_cond (exp, insn_code, insn_index);
3571     }
3572
3573   current_alternative_string = 0;
3574   return simplify_cond (newexp, insn_code, insn_index);
3575 }
3576 #endif
3577 \f
3578 /* If EXP is a suitable expression, reorganize it by constructing an
3579    equivalent expression that is a COND with the tests being all combinations
3580    of attribute values and the values being simple constants.  */
3581
3582 static rtx
3583 simplify_by_exploding (exp)
3584      rtx exp;
3585 {
3586   rtx list = 0, link, condexp, defval = NULL_RTX;
3587   struct dimension *space;
3588   rtx *condtest, *condval;
3589   int i, j, total, ndim = 0;
3590   int most_tests, num_marks, new_marks;
3591
3592   /* Locate all the EQ_ATTR expressions.  */
3593   if (! find_and_mark_used_attributes (exp, &list, &ndim) || ndim == 0)
3594     {
3595       unmark_used_attributes (list, 0, 0);
3596       return exp;
3597     }
3598
3599   /* Create an attribute space from the list of used attributes.  For each
3600      dimension in the attribute space, record the attribute, list of values
3601      used, and number of values used.  Add members to the list of values to
3602      cover the domain of the attribute.  This makes the expanded COND form
3603      order independent.  */
3604
3605   space = (struct dimension *) alloca (ndim * sizeof (struct dimension));
3606
3607   total = 1;
3608   for (ndim = 0; list; ndim++)
3609     {
3610       /* Pull the first attribute value from the list and record that
3611          attribute as another dimension in the attribute space.  */
3612       const char *name = XSTR (XEXP (list, 0), 0);
3613       rtx *prev;
3614
3615       if ((space[ndim].attr = find_attr (name, 0)) == 0
3616           || space[ndim].attr->is_numeric)
3617         {
3618           unmark_used_attributes (list, space, ndim);
3619           return exp;
3620         }
3621
3622       /* Add all remaining attribute values that refer to this attribute.  */
3623       space[ndim].num_values = 0;
3624       space[ndim].values = 0;
3625       prev = &list;
3626       for (link = list; link; link = *prev)
3627         if (! strcmp (XSTR (XEXP (link, 0), 0), name))
3628           {
3629             space[ndim].num_values++;
3630             *prev = XEXP (link, 1);
3631             XEXP (link, 1) = space[ndim].values;
3632             space[ndim].values = link;
3633           }
3634         else
3635           prev = &XEXP (link, 1);
3636
3637       /* Add sufficient members to the list of values to make the list
3638          mutually exclusive and record the total size of the attribute
3639          space.  */
3640       total *= add_values_to_cover (&space[ndim]);
3641     }
3642
3643   /* Sort the attribute space so that the attributes go from non-constant
3644      to constant and from most values to least values.  */
3645   for (i = 0; i < ndim; i++)
3646     for (j = ndim - 1; j > i; j--)
3647       if ((space[j-1].attr->is_const && !space[j].attr->is_const)
3648           || space[j-1].num_values < space[j].num_values)
3649         {
3650           struct dimension tmp;
3651           tmp = space[j];
3652           space[j] = space[j-1];
3653           space[j-1] = tmp;
3654         }
3655
3656   /* Establish the initial current value.  */
3657   for (i = 0; i < ndim; i++)
3658     space[i].current_value = space[i].values;
3659
3660   condtest = (rtx *) alloca (total * sizeof (rtx));
3661   condval = (rtx *) alloca (total * sizeof (rtx));
3662
3663   /* Expand the tests and values by iterating over all values in the
3664      attribute space.  */
3665   for (i = 0;; i++)
3666     {
3667       condtest[i] = test_for_current_value (space, ndim);
3668       condval[i] = simplify_with_current_value (exp, space, ndim);
3669       if (! increment_current_value (space, ndim))
3670         break;
3671     }
3672   if (i != total - 1)
3673     abort ();
3674
3675   /* We are now finished with the original expression.  */
3676   unmark_used_attributes (0, space, ndim);
3677
3678   /* Find the most used constant value and make that the default.  */
3679   most_tests = -1;
3680   for (i = num_marks = 0; i < total; i++)
3681     if (GET_CODE (condval[i]) == CONST_STRING
3682         && ! MEM_VOLATILE_P (condval[i]))
3683       {
3684         /* Mark the unmarked constant value and count how many are marked.  */
3685         MEM_VOLATILE_P (condval[i]) = 1;
3686         for (j = new_marks = 0; j < total; j++)
3687           if (GET_CODE (condval[j]) == CONST_STRING
3688               && MEM_VOLATILE_P (condval[j]))
3689             new_marks++;
3690         if (new_marks - num_marks > most_tests)
3691           {
3692             most_tests = new_marks - num_marks;
3693             defval = condval[i];
3694           }
3695         num_marks = new_marks;
3696       }
3697   /* Clear all the marks.  */
3698   for (i = 0; i < total; i++)
3699     MEM_VOLATILE_P (condval[i]) = 0;
3700
3701   /* Give up if nothing is constant.  */
3702   if (num_marks == 0)
3703     return exp;
3704
3705   /* If all values are the default, use that.  */
3706   if (total == most_tests)
3707     return defval;
3708
3709   /* Make a COND with the most common constant value the default.  (A more
3710      complex method where tests with the same value were combined didn't
3711      seem to improve things.)  */
3712   condexp = rtx_alloc (COND);
3713   XVEC (condexp, 0) = rtvec_alloc ((total - most_tests) * 2);
3714   XEXP (condexp, 1) = defval;
3715   for (i = j = 0; i < total; i++)
3716     if (condval[i] != defval)
3717       {
3718         XVECEXP (condexp, 0, 2 * j) = condtest[i];
3719         XVECEXP (condexp, 0, 2 * j + 1) = condval[i];
3720         j++;
3721       }
3722
3723   return condexp;
3724 }
3725
3726 /* Set the MEM_VOLATILE_P flag for all EQ_ATTR expressions in EXP and
3727    verify that EXP can be simplified to a constant term if all the EQ_ATTR
3728    tests have known value.  */
3729
3730 static int
3731 find_and_mark_used_attributes (exp, terms, nterms)
3732      rtx exp, *terms;
3733      int *nterms;
3734 {
3735   int i;
3736
3737   switch (GET_CODE (exp))
3738     {
3739     case EQ_ATTR:
3740       if (! MEM_VOLATILE_P (exp))
3741         {
3742           rtx link = rtx_alloc (EXPR_LIST);
3743           XEXP (link, 0) = exp;
3744           XEXP (link, 1) = *terms;
3745           *terms = link;
3746           *nterms += 1;
3747           MEM_VOLATILE_P (exp) = 1;
3748         }
3749       return 1;
3750
3751     case CONST_STRING:
3752     case CONST_INT:
3753       return 1;
3754
3755     case IF_THEN_ELSE:
3756       if (! find_and_mark_used_attributes (XEXP (exp, 2), terms, nterms))
3757         return 0;
3758     case IOR:
3759     case AND:
3760       if (! find_and_mark_used_attributes (XEXP (exp, 1), terms, nterms))
3761         return 0;
3762     case NOT:
3763       if (! find_and_mark_used_attributes (XEXP (exp, 0), terms, nterms))
3764         return 0;
3765       return 1;
3766
3767     case COND:
3768       for (i = 0; i < XVECLEN (exp, 0); i++)
3769         if (! find_and_mark_used_attributes (XVECEXP (exp, 0, i), terms, nterms))
3770           return 0;
3771       if (! find_and_mark_used_attributes (XEXP (exp, 1), terms, nterms))
3772         return 0;
3773       return 1;
3774
3775     default:
3776       return 0;
3777     }
3778 }
3779
3780 /* Clear the MEM_VOLATILE_P flag in all EQ_ATTR expressions on LIST and
3781    in the values of the NDIM-dimensional attribute space SPACE.  */
3782
3783 static void
3784 unmark_used_attributes (list, space, ndim)
3785      rtx list;
3786      struct dimension *space;
3787      int ndim;
3788 {
3789   rtx link, exp;
3790   int i;
3791
3792   for (i = 0; i < ndim; i++)
3793     unmark_used_attributes (space[i].values, 0, 0);
3794
3795   for (link = list; link; link = XEXP (link, 1))
3796     {
3797       exp = XEXP (link, 0);
3798       if (GET_CODE (exp) == EQ_ATTR)
3799         MEM_VOLATILE_P (exp) = 0;
3800     }
3801 }
3802
3803 /* Update the attribute dimension DIM so that all values of the attribute
3804    are tested.  Return the updated number of values.  */
3805
3806 static int
3807 add_values_to_cover (dim)
3808      struct dimension *dim;
3809 {
3810   struct attr_value *av;
3811   rtx exp, link, *prev;
3812   int nalt = 0;
3813
3814   for (av = dim->attr->first_value; av; av = av->next)
3815     if (GET_CODE (av->value) == CONST_STRING)
3816       nalt++;
3817
3818   if (nalt < dim->num_values)
3819     abort ();
3820   else if (nalt == dim->num_values)
3821     ; /* Ok.  */
3822   else if (nalt * 2 < dim->num_values * 3)
3823     {
3824       /* Most all the values of the attribute are used, so add all the unused
3825          values.  */
3826       prev = &dim->values;
3827       for (link = dim->values; link; link = *prev)
3828         prev = &XEXP (link, 1);
3829
3830       for (av = dim->attr->first_value; av; av = av->next)
3831         if (GET_CODE (av->value) == CONST_STRING)
3832           {
3833             exp = attr_eq (dim->attr->name, XSTR (av->value, 0));
3834             if (MEM_VOLATILE_P (exp))
3835               continue;
3836
3837             link = rtx_alloc (EXPR_LIST);
3838             XEXP (link, 0) = exp;
3839             XEXP (link, 1) = 0;
3840             *prev = link;
3841             prev = &XEXP (link, 1);
3842           }
3843       dim->num_values = nalt;
3844     }
3845   else
3846     {
3847       rtx orexp = false_rtx;
3848
3849       /* Very few values are used, so compute a mutually exclusive
3850          expression.  (We could do this for numeric values if that becomes
3851          important.)  */
3852       prev = &dim->values;
3853       for (link = dim->values; link; link = *prev)
3854         {
3855           orexp = insert_right_side (IOR, orexp, XEXP (link, 0), -2, -2);
3856           prev = &XEXP (link, 1);
3857         }
3858       link = rtx_alloc (EXPR_LIST);
3859       XEXP (link, 0) = attr_rtx (NOT, orexp);
3860       XEXP (link, 1) = 0;
3861       *prev = link;
3862       dim->num_values++;
3863     }
3864   return dim->num_values;
3865 }
3866
3867 /* Increment the current value for the NDIM-dimensional attribute space SPACE
3868    and return FALSE if the increment overflowed.  */
3869
3870 static int
3871 increment_current_value (space, ndim)
3872      struct dimension *space;
3873      int ndim;
3874 {
3875   int i;
3876
3877   for (i = ndim - 1; i >= 0; i--)
3878     {
3879       if ((space[i].current_value = XEXP (space[i].current_value, 1)) == 0)
3880         space[i].current_value = space[i].values;
3881       else
3882         return 1;
3883     }
3884   return 0;
3885 }
3886
3887 /* Construct an expression corresponding to the current value for the
3888    NDIM-dimensional attribute space SPACE.  */
3889
3890 static rtx
3891 test_for_current_value (space, ndim)
3892      struct dimension *space;
3893      int ndim;
3894 {
3895   int i;
3896   rtx exp = true_rtx;
3897
3898   for (i = 0; i < ndim; i++)
3899     exp = insert_right_side (AND, exp, XEXP (space[i].current_value, 0),
3900                              -2, -2);
3901
3902   return exp;
3903 }
3904
3905 /* Given the current value of the NDIM-dimensional attribute space SPACE,
3906    set the corresponding EQ_ATTR expressions to that value and reduce
3907    the expression EXP as much as possible.  On input [and output], all
3908    known EQ_ATTR expressions are set to FALSE.  */
3909
3910 static rtx
3911 simplify_with_current_value (exp, space, ndim)
3912      rtx exp;
3913      struct dimension *space;
3914      int ndim;
3915 {
3916   int i;
3917   rtx x;
3918
3919   /* Mark each current value as TRUE.  */
3920   for (i = 0; i < ndim; i++)
3921     {
3922       x = XEXP (space[i].current_value, 0);
3923       if (GET_CODE (x) == EQ_ATTR)
3924         MEM_VOLATILE_P (x) = 0;
3925     }
3926
3927   exp = simplify_with_current_value_aux (exp);
3928
3929   /* Change each current value back to FALSE.  */
3930   for (i = 0; i < ndim; i++)
3931     {
3932       x = XEXP (space[i].current_value, 0);
3933       if (GET_CODE (x) == EQ_ATTR)
3934         MEM_VOLATILE_P (x) = 1;
3935     }
3936
3937   return exp;
3938 }
3939
3940 /* Reduce the expression EXP based on the MEM_VOLATILE_P settings of
3941    all EQ_ATTR expressions.  */
3942
3943 static rtx
3944 simplify_with_current_value_aux (exp)
3945      rtx exp;
3946 {
3947   register int i;
3948   rtx cond;
3949
3950   switch (GET_CODE (exp))
3951     {
3952     case EQ_ATTR:
3953       if (MEM_VOLATILE_P (exp))
3954         return false_rtx;
3955       else
3956         return true_rtx;
3957     case CONST_STRING:
3958     case CONST_INT:
3959       return exp;
3960
3961     case IF_THEN_ELSE:
3962       cond = simplify_with_current_value_aux (XEXP (exp, 0));
3963       if (cond == true_rtx)
3964         return simplify_with_current_value_aux (XEXP (exp, 1));
3965       else if (cond == false_rtx)
3966         return simplify_with_current_value_aux (XEXP (exp, 2));
3967       else
3968         return attr_rtx (IF_THEN_ELSE, cond,
3969                          simplify_with_current_value_aux (XEXP (exp, 1)),
3970                          simplify_with_current_value_aux (XEXP (exp, 2)));
3971
3972     case IOR:
3973       cond = simplify_with_current_value_aux (XEXP (exp, 1));
3974       if (cond == true_rtx)
3975         return cond;
3976       else if (cond == false_rtx)
3977         return simplify_with_current_value_aux (XEXP (exp, 0));
3978       else
3979         return attr_rtx (IOR, cond,
3980                          simplify_with_current_value_aux (XEXP (exp, 0)));
3981
3982     case AND:
3983       cond = simplify_with_current_value_aux (XEXP (exp, 1));
3984       if (cond == true_rtx)
3985         return simplify_with_current_value_aux (XEXP (exp, 0));
3986       else if (cond == false_rtx)
3987         return cond;
3988       else
3989         return attr_rtx (AND, cond,
3990                          simplify_with_current_value_aux (XEXP (exp, 0)));
3991
3992     case NOT:
3993       cond = simplify_with_current_value_aux (XEXP (exp, 0));
3994       if (cond == true_rtx)
3995         return false_rtx;
3996       else if (cond == false_rtx)
3997         return true_rtx;
3998       else
3999         return attr_rtx (NOT, cond);
4000
4001     case COND:
4002       for (i = 0; i < XVECLEN (exp, 0); i += 2)
4003         {
4004           cond = simplify_with_current_value_aux (XVECEXP (exp, 0, i));
4005           if (cond == true_rtx)
4006             return simplify_with_current_value_aux (XVECEXP (exp, 0, i + 1));
4007           else if (cond == false_rtx)
4008             continue;
4009           else
4010             abort (); /* With all EQ_ATTR's of known value, a case should
4011                          have been selected.  */
4012         }
4013       return simplify_with_current_value_aux (XEXP (exp, 1));
4014
4015     default:
4016       abort ();
4017     }
4018 }
4019 \f
4020 /* Clear the MEM_IN_STRUCT_P flag in EXP and its subexpressions.  */
4021
4022 static void
4023 clear_struct_flag (x)
4024      rtx x;
4025 {
4026   register int i;
4027   register int j;
4028   register enum rtx_code code;
4029   register const char *fmt;
4030
4031   MEM_IN_STRUCT_P (x) = 0;
4032   if (RTX_UNCHANGING_P (x))
4033     return;
4034
4035   code = GET_CODE (x);
4036
4037   switch (code)
4038     {
4039     case REG:
4040     case QUEUED:
4041     case CONST_INT:
4042     case CONST_DOUBLE:
4043     case SYMBOL_REF:
4044     case CODE_LABEL:
4045     case PC:
4046     case CC0:
4047     case EQ_ATTR:
4048     case ATTR_FLAG:
4049       return;
4050
4051     default:
4052       break;
4053     }
4054
4055   /* Compare the elements.  If any pair of corresponding elements
4056      fail to match, return 0 for the whole things.  */
4057
4058   fmt = GET_RTX_FORMAT (code);
4059   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4060     {
4061       switch (fmt[i])
4062         {
4063         case 'V':
4064         case 'E':
4065           for (j = 0; j < XVECLEN (x, i); j++)
4066             clear_struct_flag (XVECEXP (x, i, j));
4067           break;
4068
4069         case 'e':
4070           clear_struct_flag (XEXP (x, i));
4071           break;
4072         }
4073     }
4074 }
4075
4076 /* Return the number of RTX objects making up the expression X.
4077    But if we count more than MAX objects, stop counting.  */
4078
4079 static int
4080 count_sub_rtxs (x, max)
4081      rtx x;
4082      int max;
4083 {
4084   register int i;
4085   register int j;
4086   register enum rtx_code code;
4087   register const char *fmt;
4088   int total = 0;
4089
4090   code = GET_CODE (x);
4091
4092   switch (code)
4093     {
4094     case REG:
4095     case QUEUED:
4096     case CONST_INT:
4097     case CONST_DOUBLE:
4098     case SYMBOL_REF:
4099     case CODE_LABEL:
4100     case PC:
4101     case CC0:
4102     case EQ_ATTR:
4103     case ATTR_FLAG:
4104       return 1;
4105
4106     default:
4107       break;
4108     }
4109
4110   /* Compare the elements.  If any pair of corresponding elements
4111      fail to match, return 0 for the whole things.  */
4112
4113   fmt = GET_RTX_FORMAT (code);
4114   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4115     {
4116       if (total >= max)
4117         return total;
4118
4119       switch (fmt[i])
4120         {
4121         case 'V':
4122         case 'E':
4123           for (j = 0; j < XVECLEN (x, i); j++)
4124             total += count_sub_rtxs (XVECEXP (x, i, j), max);
4125           break;
4126
4127         case 'e':
4128           total += count_sub_rtxs (XEXP (x, i), max);
4129           break;
4130         }
4131     }
4132   return total;
4133
4134 }
4135 \f
4136 /* Create table entries for DEFINE_ATTR.  */
4137
4138 static void
4139 gen_attr (exp)
4140      rtx exp;
4141 {
4142   struct attr_desc *attr;
4143   struct attr_value *av;
4144   const char *name_ptr;
4145   char *p;
4146
4147   /* Make a new attribute structure.  Check for duplicate by looking at
4148      attr->default_val, since it is initialized by this routine.  */
4149   attr = find_attr (XSTR (exp, 0), 1);
4150   if (attr->default_val)
4151     fatal ("Duplicate definition for `%s' attribute", attr->name);
4152
4153   if (*XSTR (exp, 1) == '\0')
4154     attr->is_numeric = 1;
4155   else
4156     {
4157       name_ptr = XSTR (exp, 1);
4158       while ((p = next_comma_elt (&name_ptr)) != NULL)
4159         {
4160           av = (struct attr_value *) oballoc (sizeof (struct attr_value));
4161           av->value = attr_rtx (CONST_STRING, p);
4162           av->next = attr->first_value;
4163           attr->first_value = av;
4164           av->first_insn = NULL;
4165           av->num_insns = 0;
4166           av->has_asm_insn = 0;
4167         }
4168     }
4169
4170   if (GET_CODE (XEXP (exp, 2)) == CONST)
4171     {
4172       attr->is_const = 1;
4173       if (attr->is_numeric)
4174         fatal ("Constant attributes may not take numeric values");
4175       /* Get rid of the CONST node.  It is allowed only at top-level.  */
4176       XEXP (exp, 2) = XEXP (XEXP (exp, 2), 0);
4177     }
4178
4179   if (! strcmp (attr->name, "length") && ! attr->is_numeric)
4180     fatal ("`length' attribute must take numeric values");
4181
4182   /* Set up the default value.  */
4183   XEXP (exp, 2) = check_attr_value (XEXP (exp, 2), attr);
4184   attr->default_val = get_attr_value (XEXP (exp, 2), attr, -2);
4185 }
4186 \f
4187 /* Given a pattern for DEFINE_PEEPHOLE or DEFINE_INSN, return the number of
4188    alternatives in the constraints.  Assume all MATCH_OPERANDs have the same
4189    number of alternatives as this should be checked elsewhere.  */
4190
4191 static int
4192 count_alternatives (exp)
4193      rtx exp;
4194 {
4195   int i, j, n;
4196   const char *fmt;
4197
4198   if (GET_CODE (exp) == MATCH_OPERAND)
4199     return n_comma_elts (XSTR (exp, 2));
4200
4201   for (i = 0, fmt = GET_RTX_FORMAT (GET_CODE (exp));
4202        i < GET_RTX_LENGTH (GET_CODE (exp)); i++)
4203     switch (*fmt++)
4204       {
4205       case 'e':
4206       case 'u':
4207         n = count_alternatives (XEXP (exp, i));
4208         if (n)
4209           return n;
4210         break;
4211
4212       case 'E':
4213       case 'V':
4214         if (XVEC (exp, i) != NULL)
4215           for (j = 0; j < XVECLEN (exp, i); j++)
4216             {
4217               n = count_alternatives (XVECEXP (exp, i, j));
4218               if (n)
4219                 return n;
4220             }
4221       }
4222
4223   return 0;
4224 }
4225 \f
4226 /* Returns non-zero if the given expression contains an EQ_ATTR with the
4227    `alternative' attribute.  */
4228
4229 static int
4230 compares_alternatives_p (exp)
4231      rtx exp;
4232 {
4233   int i, j;
4234   const char *fmt;
4235
4236   if (GET_CODE (exp) == EQ_ATTR && XSTR (exp, 0) == alternative_name)
4237     return 1;
4238
4239   for (i = 0, fmt = GET_RTX_FORMAT (GET_CODE (exp));
4240        i < GET_RTX_LENGTH (GET_CODE (exp)); i++)
4241     switch (*fmt++)
4242       {
4243       case 'e':
4244       case 'u':
4245         if (compares_alternatives_p (XEXP (exp, i)))
4246           return 1;
4247         break;
4248
4249       case 'E':
4250         for (j = 0; j < XVECLEN (exp, i); j++)
4251           if (compares_alternatives_p (XVECEXP (exp, i, j)))
4252             return 1;
4253         break;
4254       }
4255
4256   return 0;
4257 }
4258 \f
4259 /* Returns non-zero is INNER is contained in EXP.  */
4260
4261 static int
4262 contained_in_p (inner, exp)
4263      rtx inner;
4264      rtx exp;
4265 {
4266   int i, j;
4267   const char *fmt;
4268
4269   if (rtx_equal_p (inner, exp))
4270     return 1;
4271
4272   for (i = 0, fmt = GET_RTX_FORMAT (GET_CODE (exp));
4273        i < GET_RTX_LENGTH (GET_CODE (exp)); i++)
4274     switch (*fmt++)
4275       {
4276       case 'e':
4277       case 'u':
4278         if (contained_in_p (inner, XEXP (exp, i)))
4279           return 1;
4280         break;
4281
4282       case 'E':
4283         for (j = 0; j < XVECLEN (exp, i); j++)
4284           if (contained_in_p (inner, XVECEXP (exp, i, j)))
4285             return 1;
4286         break;
4287       }
4288
4289   return 0;
4290 }
4291 \f
4292 /* Process DEFINE_PEEPHOLE, DEFINE_INSN, and DEFINE_ASM_ATTRIBUTES.  */
4293
4294 static void
4295 gen_insn (exp)
4296      rtx exp;
4297 {
4298   struct insn_def *id;
4299
4300   id = (struct insn_def *) oballoc (sizeof (struct insn_def));
4301   id->next = defs;
4302   defs = id;
4303   id->def = exp;
4304
4305   switch (GET_CODE (exp))
4306     {
4307     case DEFINE_INSN:
4308       id->insn_code = insn_code_number;
4309       id->insn_index = insn_index_number;
4310       id->num_alternatives = count_alternatives (exp);
4311       if (id->num_alternatives == 0)
4312         id->num_alternatives = 1;
4313       id->vec_idx = 4;
4314       break;
4315
4316     case DEFINE_PEEPHOLE:
4317       id->insn_code = insn_code_number;
4318       id->insn_index = insn_index_number;
4319       id->num_alternatives = count_alternatives (exp);
4320       if (id->num_alternatives == 0)
4321         id->num_alternatives = 1;
4322       id->vec_idx = 3;
4323       break;
4324
4325     case DEFINE_ASM_ATTRIBUTES:
4326       id->insn_code = -1;
4327       id->insn_index = -1;
4328       id->num_alternatives = 1;
4329       id->vec_idx = 0;
4330       got_define_asm_attributes = 1;
4331       break;
4332
4333     default:
4334       abort ();
4335     }
4336 }
4337 \f
4338 /* Process a DEFINE_DELAY.  Validate the vector length, check if annul
4339    true or annul false is specified, and make a `struct delay_desc'.  */
4340
4341 static void
4342 gen_delay (def)
4343      rtx def;
4344 {
4345   struct delay_desc *delay;
4346   int i;
4347
4348   if (XVECLEN (def, 1) % 3 != 0)
4349     fatal ("Number of elements in DEFINE_DELAY must be multiple of three.");
4350
4351   for (i = 0; i < XVECLEN (def, 1); i += 3)
4352     {
4353       if (XVECEXP (def, 1, i + 1))
4354         have_annul_true = 1;
4355       if (XVECEXP (def, 1, i + 2))
4356         have_annul_false = 1;
4357     }
4358
4359   delay = (struct delay_desc *) oballoc (sizeof (struct delay_desc));
4360   delay->def = def;
4361   delay->num = ++num_delays;
4362   delay->next = delays;
4363   delays = delay;
4364 }
4365 \f
4366 /* Process a DEFINE_FUNCTION_UNIT.
4367
4368    This gives information about a function unit contained in the CPU.
4369    We fill in a `struct function_unit_op' and a `struct function_unit'
4370    with information used later by `expand_unit'.  */
4371
4372 static void
4373 gen_unit (def)
4374      rtx def;
4375 {
4376   struct function_unit *unit;
4377   struct function_unit_op *op;
4378   const char *name = XSTR (def, 0);
4379   int multiplicity = XINT (def, 1);
4380   int simultaneity = XINT (def, 2);
4381   rtx condexp = XEXP (def, 3);
4382   int ready_cost = MAX (XINT (def, 4), 1);
4383   int issue_delay = MAX (XINT (def, 5), 1);
4384
4385   /* See if we have already seen this function unit.  If so, check that
4386      the multiplicity and simultaneity values are the same.  If not, make
4387      a structure for this function unit.  */
4388   for (unit = units; unit; unit = unit->next)
4389     if (! strcmp (unit->name, name))
4390       {
4391         if (unit->multiplicity != multiplicity
4392             || unit->simultaneity != simultaneity)
4393           fatal ("Differing specifications given for `%s' function unit.",
4394                  unit->name);
4395         break;
4396       }
4397
4398   if (unit == 0)
4399     {
4400       unit = (struct function_unit *) oballoc (sizeof (struct function_unit));
4401       unit->name = name;
4402       unit->multiplicity = multiplicity;
4403       unit->simultaneity = simultaneity;
4404       unit->issue_delay.min = unit->issue_delay.max = issue_delay;
4405       unit->num = num_units++;
4406       unit->num_opclasses = 0;
4407       unit->condexp = false_rtx;
4408       unit->ops = 0;
4409       unit->next = units;
4410       units = unit;
4411     }
4412
4413   /* Make a new operation class structure entry and initialize it.  */
4414   op = (struct function_unit_op *) oballoc (sizeof (struct function_unit_op));
4415   op->condexp = condexp;
4416   op->num = unit->num_opclasses++;
4417   op->ready = ready_cost;
4418   op->issue_delay = issue_delay;
4419   op->next = unit->ops;
4420   unit->ops = op;
4421   num_unit_opclasses++;
4422
4423   /* Set our issue expression based on whether or not an optional conflict
4424      vector was specified.  */
4425   if (XVEC (def, 6))
4426     {
4427       /* Compute the IOR of all the specified expressions.  */
4428       rtx orexp = false_rtx;
4429       int i;
4430
4431       for (i = 0; i < XVECLEN (def, 6); i++)
4432         orexp = insert_right_side (IOR, orexp, XVECEXP (def, 6, i), -2, -2);
4433
4434       op->conflict_exp = orexp;
4435       extend_range (&unit->issue_delay, 1, issue_delay);
4436     }
4437   else
4438     {
4439       op->conflict_exp = true_rtx;
4440       extend_range (&unit->issue_delay, issue_delay, issue_delay);
4441     }
4442
4443   /* Merge our conditional into that of the function unit so we can determine
4444      which insns are used by the function unit.  */
4445   unit->condexp = insert_right_side (IOR, unit->condexp, op->condexp, -2, -2);
4446 }
4447 \f
4448 /* Given a piece of RTX, print a C expression to test its truth value.
4449    We use AND and IOR both for logical and bit-wise operations, so
4450    interpret them as logical unless they are inside a comparison expression.
4451    The first bit of FLAGS will be non-zero in that case.
4452
4453    Set the second bit of FLAGS to make references to attribute values use
4454    a cached local variable instead of calling a function.  */
4455
4456 static void
4457 write_test_expr (exp, flags)
4458      rtx exp;
4459      int flags;
4460 {
4461   int comparison_operator = 0;
4462   RTX_CODE code;
4463   struct attr_desc *attr;
4464
4465   /* In order not to worry about operator precedence, surround our part of
4466      the expression with parentheses.  */
4467
4468   printf ("(");
4469   code = GET_CODE (exp);
4470   switch (code)
4471     {
4472     /* Binary operators.  */
4473     case EQ: case NE:
4474     case GE: case GT: case GEU: case GTU:
4475     case LE: case LT: case LEU: case LTU:
4476       comparison_operator = 1;
4477
4478     case PLUS:   case MINUS:  case MULT:     case DIV:      case MOD:
4479     case AND:    case IOR:    case XOR:
4480     case ASHIFT: case LSHIFTRT: case ASHIFTRT:
4481       write_test_expr (XEXP (exp, 0), flags | comparison_operator);
4482       switch (code)
4483         {
4484         case EQ:
4485           printf (" == ");
4486           break;
4487         case NE:
4488           printf (" != ");
4489           break;
4490         case GE:
4491           printf (" >= ");
4492           break;
4493         case GT:
4494           printf (" > ");
4495           break;
4496         case GEU:
4497           printf (" >= (unsigned) ");
4498           break;
4499         case GTU:
4500           printf (" > (unsigned) ");
4501           break;
4502         case LE:
4503           printf (" <= ");
4504           break;
4505         case LT:
4506           printf (" < ");
4507           break;
4508         case LEU:
4509           printf (" <= (unsigned) ");
4510           break;
4511         case LTU:
4512           printf (" < (unsigned) ");
4513           break;
4514         case PLUS:
4515           printf (" + ");
4516           break;
4517         case MINUS:
4518           printf (" - ");
4519           break;
4520         case MULT:
4521           printf (" * ");
4522           break;
4523         case DIV:
4524           printf (" / ");
4525           break;
4526         case MOD:
4527           printf (" %% ");
4528           break;
4529         case AND:
4530           if (flags & 1)
4531             printf (" & ");
4532           else
4533             printf (" && ");
4534           break;
4535         case IOR:
4536           if (flags & 1)
4537             printf (" | ");
4538           else
4539             printf (" || ");
4540           break;
4541         case XOR:
4542           printf (" ^ ");
4543           break;
4544         case ASHIFT:
4545           printf (" << ");
4546           break;
4547         case LSHIFTRT:
4548         case ASHIFTRT:
4549           printf (" >> ");
4550           break;
4551         default:
4552           abort ();
4553         }
4554
4555       write_test_expr (XEXP (exp, 1), flags | comparison_operator);
4556       break;
4557
4558     case NOT:
4559       /* Special-case (not (eq_attrq "alternative" "x")) */
4560       if (! (flags & 1) && GET_CODE (XEXP (exp, 0)) == EQ_ATTR
4561           && XSTR (XEXP (exp, 0), 0) == alternative_name)
4562         {
4563           printf ("which_alternative != %s", XSTR (XEXP (exp, 0), 1));
4564           break;
4565         }
4566
4567       /* Otherwise, fall through to normal unary operator.  */
4568
4569     /* Unary operators.  */
4570     case ABS:  case NEG:
4571       switch (code)
4572         {
4573         case NOT:
4574           if (flags & 1)
4575             printf ("~ ");
4576           else
4577             printf ("! ");
4578           break;
4579         case ABS:
4580           printf ("abs ");
4581           break;
4582         case NEG:
4583           printf ("-");
4584           break;
4585         default:
4586           abort ();
4587         }
4588
4589       write_test_expr (XEXP (exp, 0), flags);
4590       break;
4591
4592     /* Comparison test of an attribute with a value.  Most of these will
4593        have been removed by optimization.   Handle "alternative"
4594        specially and give error if EQ_ATTR present inside a comparison.  */
4595     case EQ_ATTR:
4596       if (flags & 1)
4597         fatal ("EQ_ATTR not valid inside comparison");
4598
4599       if (XSTR (exp, 0) == alternative_name)
4600         {
4601           printf ("which_alternative == %s", XSTR (exp, 1));
4602           break;
4603         }
4604
4605       attr = find_attr (XSTR (exp, 0), 0);
4606       if (! attr) abort ();
4607
4608       /* Now is the time to expand the value of a constant attribute.  */
4609       if (attr->is_const)
4610         {
4611           write_test_expr (evaluate_eq_attr (exp, attr->default_val->value,
4612                                              -2, -2),
4613                            flags);
4614         }
4615       else
4616         {
4617           if (flags & 2)
4618             printf ("attr_%s", attr->name);
4619           else
4620             printf ("get_attr_%s (insn)", attr->name);
4621           printf (" == ");
4622           write_attr_valueq (attr, XSTR (exp, 1));
4623         }
4624       break;
4625
4626     /* Comparison test of flags for define_delays.  */
4627     case ATTR_FLAG:
4628       if (flags & 1)
4629         fatal ("ATTR_FLAG not valid inside comparison");
4630       printf ("(flags & ATTR_FLAG_%s) != 0", XSTR (exp, 0));
4631       break;
4632
4633     /* See if an operand matches a predicate.  */
4634     case MATCH_OPERAND:
4635       /* If only a mode is given, just ensure the mode matches the operand.
4636          If neither a mode nor predicate is given, error.  */
4637      if (XSTR (exp, 1) == NULL || *XSTR (exp, 1) == '\0')
4638         {
4639           if (GET_MODE (exp) == VOIDmode)
4640             fatal ("Null MATCH_OPERAND specified as test");
4641           else
4642             printf ("GET_MODE (operands[%d]) == %smode",
4643                     XINT (exp, 0), GET_MODE_NAME (GET_MODE (exp)));
4644         }
4645       else
4646         printf ("%s (operands[%d], %smode)",
4647                 XSTR (exp, 1), XINT (exp, 0), GET_MODE_NAME (GET_MODE (exp)));
4648       break;
4649
4650     case MATCH_INSN:
4651       printf ("%s (insn)", XSTR (exp, 0));
4652       break;
4653
4654     /* Constant integer.  */
4655     case CONST_INT:
4656       printf (HOST_WIDE_INT_PRINT_DEC, XWINT (exp, 0));
4657       break;
4658
4659     /* A random C expression.  */
4660     case SYMBOL_REF:
4661       printf ("%s", XSTR (exp, 0));
4662       break;
4663
4664     /* The address of the branch target.  */
4665     case MATCH_DUP:
4666       printf ("insn_addresses[INSN_UID (GET_CODE (operands[%d]) == LABEL_REF ? XEXP (operands[%d], 0) : operands[%d])]",
4667               XINT (exp, 0), XINT (exp, 0), XINT (exp, 0));
4668       break;
4669
4670     case PC:
4671       /* The address of the current insn.  We implement this actually as the
4672          address of the current insn for backward branches, but the last
4673          address of the next insn for forward branches, and both with
4674          adjustments that account for the worst-case possible stretching of
4675          intervening alignments between this insn and its destination.  */
4676       printf("insn_current_reference_address (insn)");
4677       break;
4678
4679     case CONST_STRING:
4680       printf ("%s", XSTR (exp, 0));
4681       break;
4682
4683     case IF_THEN_ELSE:
4684       write_test_expr (XEXP (exp, 0), flags & 2);
4685       printf (" ? ");
4686       write_test_expr (XEXP (exp, 1), flags | 1);
4687       printf (" : ");
4688       write_test_expr (XEXP (exp, 2), flags | 1);
4689       break;
4690
4691     default:
4692       fatal ("bad RTX code `%s' in attribute calculation\n",
4693              GET_RTX_NAME (code));
4694     }
4695
4696   printf (")");
4697 }
4698 \f
4699 /* Given an attribute value, return the maximum CONST_STRING argument
4700    encountered.  Set *UNKNOWNP and return INT_MAX if the value is unknown.  */
4701
4702 static int
4703 max_attr_value (exp, unknownp)
4704      rtx exp;
4705      int *unknownp;
4706 {
4707   int current_max;
4708   int i, n;
4709
4710   switch (GET_CODE (exp))
4711     {
4712     case CONST_STRING:
4713       current_max = atoi (XSTR (exp, 0));
4714       break;
4715
4716     case COND:
4717       current_max = max_attr_value (XEXP (exp, 1), unknownp);
4718       for (i = 0; i < XVECLEN (exp, 0); i += 2)
4719         {
4720           n = max_attr_value (XVECEXP (exp, 0, i + 1), unknownp);
4721           if (n > current_max)
4722             current_max = n;
4723         }
4724       break;
4725
4726     case IF_THEN_ELSE:
4727       current_max = max_attr_value (XEXP (exp, 1), unknownp);
4728       n = max_attr_value (XEXP (exp, 2), unknownp);
4729       if (n > current_max)
4730         current_max = n;
4731       break;
4732
4733     default:
4734       *unknownp = 1;
4735       current_max = INT_MAX;
4736       break;
4737     }
4738
4739   return current_max;
4740 }
4741
4742 /* Given an attribute value, return the result of ORing together all
4743    CONST_STRING arguments encountered.  Set *UNKNOWNP and return -1
4744    if the numeric value is not known.  */
4745
4746 static int
4747 or_attr_value (exp, unknownp)
4748      rtx exp;
4749      int *unknownp;
4750 {
4751   int current_or;
4752   int i;
4753
4754   switch (GET_CODE (exp))
4755     {
4756     case CONST_STRING:
4757       current_or = atoi (XSTR (exp, 0));
4758       break;
4759
4760     case COND:
4761       current_or = or_attr_value (XEXP (exp, 1), unknownp);
4762       for (i = 0; i < XVECLEN (exp, 0); i += 2)
4763         current_or |= or_attr_value (XVECEXP (exp, 0, i + 1), unknownp);
4764       break;
4765
4766     case IF_THEN_ELSE:
4767       current_or = or_attr_value (XEXP (exp, 1), unknownp);
4768       current_or |= or_attr_value (XEXP (exp, 2), unknownp);
4769       break;
4770
4771     default:
4772       *unknownp = 1;
4773       current_or = -1;
4774       break;
4775     }
4776
4777   return current_or;
4778 }
4779 \f
4780 /* Scan an attribute value, possibly a conditional, and record what actions
4781    will be required to do any conditional tests in it.
4782
4783    Specifically, set
4784         `must_extract'    if we need to extract the insn operands
4785         `must_constrain'  if we must compute `which_alternative'
4786         `address_used'    if an address expression was used
4787         `length_used'     if an (eq_attr "length" ...) was used
4788  */
4789
4790 static void
4791 walk_attr_value (exp)
4792      rtx exp;
4793 {
4794   register int i, j;
4795   register const char *fmt;
4796   RTX_CODE code;
4797
4798   if (exp == NULL)
4799     return;
4800
4801   code = GET_CODE (exp);
4802   switch (code)
4803     {
4804     case SYMBOL_REF:
4805       if (! RTX_UNCHANGING_P (exp))
4806         /* Since this is an arbitrary expression, it can look at anything.
4807            However, constant expressions do not depend on any particular
4808            insn.  */
4809         must_extract = must_constrain = 1;
4810       return;
4811
4812     case MATCH_OPERAND:
4813       must_extract = 1;
4814       return;
4815
4816     case EQ_ATTR:
4817       if (XSTR (exp, 0) == alternative_name)
4818         must_extract = must_constrain = 1;
4819       else if (strcmp (XSTR (exp, 0), "length") == 0)
4820         length_used = 1;
4821       return;
4822
4823     case MATCH_DUP:
4824       must_extract = 1;
4825       address_used = 1;
4826       return;
4827
4828     case PC:
4829       address_used = 1;
4830       return;
4831
4832     case ATTR_FLAG:
4833       return;
4834
4835     default:
4836       break;
4837     }
4838
4839   for (i = 0, fmt = GET_RTX_FORMAT (code); i < GET_RTX_LENGTH (code); i++)
4840     switch (*fmt++)
4841       {
4842       case 'e':
4843       case 'u':
4844         walk_attr_value (XEXP (exp, i));
4845         break;
4846
4847       case 'E':
4848         if (XVEC (exp, i) != NULL)
4849           for (j = 0; j < XVECLEN (exp, i); j++)
4850             walk_attr_value (XVECEXP (exp, i, j));
4851         break;
4852       }
4853 }
4854 \f
4855 /* Write out a function to obtain the attribute for a given INSN.  */
4856
4857 static void
4858 write_attr_get (attr)
4859      struct attr_desc *attr;
4860 {
4861   struct attr_value *av, *common_av;
4862
4863   /* Find the most used attribute value.  Handle that as the `default' of the
4864      switch we will generate.  */
4865   common_av = find_most_used (attr);
4866
4867   /* Write out prototype of function. */
4868   if (!attr->is_numeric)
4869     printf ("extern enum attr_%s ", attr->name);
4870   else if (attr->unsigned_p)
4871     printf ("extern unsigned int ");
4872   else
4873     printf ("extern int ");
4874   /* If the attribute name starts with a star, the remainder is the name of
4875      the subroutine to use, instead of `get_attr_...'.  */
4876   if (attr->name[0] == '*')
4877     printf ("%s PARAMS ((rtx));\n", &attr->name[1]);
4878   else
4879     printf ("get_attr_%s PARAMS ((%s));\n", attr->name,
4880             (attr->is_const ? "void" : "rtx"));
4881
4882   /* Write out start of function, then all values with explicit `case' lines,
4883      then a `default', then the value with the most uses.  */
4884   if (!attr->is_numeric)
4885     printf ("enum attr_%s\n", attr->name);
4886   else if (attr->unsigned_p)
4887     printf ("unsigned int\n");
4888   else
4889     printf ("int\n");
4890
4891   /* If the attribute name starts with a star, the remainder is the name of
4892      the subroutine to use, instead of `get_attr_...'.  */
4893   if (attr->name[0] == '*')
4894     printf ("%s (insn)\n", &attr->name[1]);
4895   else if (attr->is_const == 0)
4896     printf ("get_attr_%s (insn)\n", attr->name);
4897   else
4898     {
4899       printf ("get_attr_%s ()\n", attr->name);
4900       printf ("{\n");
4901
4902       for (av = attr->first_value; av; av = av->next)
4903         if (av->num_insns != 0)
4904           write_attr_set (attr, 2, av->value, "return", ";",
4905                           true_rtx, av->first_insn->insn_code,
4906                           av->first_insn->insn_index);
4907
4908       printf ("}\n\n");
4909       return;
4910     }
4911
4912   printf ("     rtx insn;\n");
4913   printf ("{\n");
4914
4915   if (GET_CODE (common_av->value) == FFS)
4916     {
4917       rtx p = XEXP (common_av->value, 0);
4918
4919       /* No need to emit code to abort if the insn is unrecognized; the
4920          other get_attr_foo functions will do that when we call them.  */
4921
4922       write_toplevel_expr (p);
4923
4924       printf ("\n  if (accum && accum == (accum & -accum))\n");
4925       printf ("    {\n");
4926       printf ("      int i;\n");
4927       printf ("      for (i = 0; accum >>= 1; ++i) continue;\n");
4928       printf ("      accum = i;\n");
4929       printf ("    }\n  else\n");
4930       printf ("    accum = ~accum;\n");
4931       printf ("  return accum;\n}\n\n");
4932     }
4933   else
4934     {
4935       printf ("  switch (recog_memoized (insn))\n");
4936       printf ("    {\n");
4937
4938       for (av = attr->first_value; av; av = av->next)
4939         if (av != common_av)
4940           write_attr_case (attr, av, 1, "return", ";", 4, true_rtx);
4941
4942       write_attr_case (attr, common_av, 0, "return", ";", 4, true_rtx);
4943       printf ("    }\n}\n\n");
4944     }
4945 }
4946 \f
4947 /* Given an AND tree of known true terms (because we are inside an `if' with
4948    that as the condition or are in an `else' clause) and an expression,
4949    replace any known true terms with TRUE.  Use `simplify_and_tree' to do
4950    the bulk of the work.  */
4951
4952 static rtx
4953 eliminate_known_true (known_true, exp, insn_code, insn_index)
4954      rtx known_true;
4955      rtx exp;
4956      int insn_code, insn_index;
4957 {
4958   rtx term;
4959
4960   known_true = SIMPLIFY_TEST_EXP (known_true, insn_code, insn_index);
4961
4962   if (GET_CODE (known_true) == AND)
4963     {
4964       exp = eliminate_known_true (XEXP (known_true, 0), exp,
4965                                   insn_code, insn_index);
4966       exp = eliminate_known_true (XEXP (known_true, 1), exp,
4967                                   insn_code, insn_index);
4968     }
4969   else
4970     {
4971       term = known_true;
4972       exp = simplify_and_tree (exp, &term, insn_code, insn_index);
4973     }
4974
4975   return exp;
4976 }
4977 \f
4978 /* Write out a series of tests and assignment statements to perform tests and
4979    sets of an attribute value.  We are passed an indentation amount and prefix
4980    and suffix strings to write around each attribute value (e.g., "return"
4981    and ";").  */
4982
4983 static void
4984 write_attr_set (attr, indent, value, prefix, suffix, known_true,
4985                 insn_code, insn_index)
4986      struct attr_desc *attr;
4987      int indent;
4988      rtx value;
4989      const char *prefix;
4990      const char *suffix;
4991      rtx known_true;
4992      int insn_code, insn_index;
4993 {
4994   if (GET_CODE (value) == COND)
4995     {
4996       /* Assume the default value will be the default of the COND unless we
4997          find an always true expression.  */
4998       rtx default_val = XEXP (value, 1);
4999       rtx our_known_true = known_true;
5000       rtx newexp;
5001       int first_if = 1;
5002       int i;
5003
5004       for (i = 0; i < XVECLEN (value, 0); i += 2)
5005         {
5006           rtx testexp;
5007           rtx inner_true;
5008
5009           testexp = eliminate_known_true (our_known_true,
5010                                           XVECEXP (value, 0, i),
5011                                           insn_code, insn_index);
5012           newexp = attr_rtx (NOT, testexp);
5013           newexp  = insert_right_side (AND, our_known_true, newexp,
5014                                        insn_code, insn_index);
5015
5016           /* If the test expression is always true or if the next `known_true'
5017              expression is always false, this is the last case, so break
5018              out and let this value be the `else' case.  */
5019           if (testexp == true_rtx || newexp == false_rtx)
5020             {
5021               default_val = XVECEXP (value, 0, i + 1);
5022               break;
5023             }
5024
5025           /* Compute the expression to pass to our recursive call as being
5026              known true.  */
5027           inner_true = insert_right_side (AND, our_known_true,
5028                                           testexp, insn_code, insn_index);
5029
5030           /* If this is always false, skip it.  */
5031           if (inner_true == false_rtx)
5032             continue;
5033
5034           write_indent (indent);
5035           printf ("%sif ", first_if ? "" : "else ");
5036           first_if = 0;
5037           write_test_expr (testexp, 0);
5038           printf ("\n");
5039           write_indent (indent + 2);
5040           printf ("{\n");
5041
5042           write_attr_set (attr, indent + 4,
5043                           XVECEXP (value, 0, i + 1), prefix, suffix,
5044                           inner_true, insn_code, insn_index);
5045           write_indent (indent + 2);
5046           printf ("}\n");
5047           our_known_true = newexp;
5048         }
5049
5050       if (! first_if)
5051         {
5052           write_indent (indent);
5053           printf ("else\n");
5054           write_indent (indent + 2);
5055           printf ("{\n");
5056         }
5057
5058       write_attr_set (attr, first_if ? indent : indent + 4, default_val,
5059                       prefix, suffix, our_known_true, insn_code, insn_index);
5060
5061       if (! first_if)
5062         {
5063           write_indent (indent + 2);
5064           printf ("}\n");
5065         }
5066     }
5067   else
5068     {
5069       write_indent (indent);
5070       printf ("%s ", prefix);
5071       write_attr_value (attr, value);
5072       printf ("%s\n", suffix);
5073     }
5074 }
5075 \f
5076 /* Write out the computation for one attribute value.  */
5077
5078 static void
5079 write_attr_case (attr, av, write_case_lines, prefix, suffix, indent,
5080                  known_true)
5081      struct attr_desc *attr;
5082      struct attr_value *av;
5083      int write_case_lines;
5084      const char *prefix, *suffix;
5085      int indent;
5086      rtx known_true;
5087 {
5088   struct insn_ent *ie;
5089
5090   if (av->num_insns == 0)
5091     return;
5092
5093   if (av->has_asm_insn)
5094     {
5095       write_indent (indent);
5096       printf ("case -1:\n");
5097       write_indent (indent + 2);
5098       printf ("if (GET_CODE (PATTERN (insn)) != ASM_INPUT\n");
5099       write_indent (indent + 2);
5100       printf ("    && asm_noperands (PATTERN (insn)) < 0)\n");
5101       write_indent (indent + 2);
5102       printf ("  fatal_insn_not_found (insn);\n");
5103     }
5104
5105   if (write_case_lines)
5106     {
5107       for (ie = av->first_insn; ie; ie = ie->next)
5108         if (ie->insn_code != -1)
5109           {
5110             write_indent (indent);
5111             printf ("case %d:\n", ie->insn_code);
5112           }
5113     }
5114   else
5115     {
5116       write_indent (indent);
5117       printf ("default:\n");
5118     }
5119
5120   /* See what we have to do to output this value.  */
5121   must_extract = must_constrain = address_used = 0;
5122   walk_attr_value (av->value);
5123
5124   if (must_extract)
5125     {
5126       write_indent (indent + 2);
5127       printf ("extract_insn (insn);\n");
5128     }
5129
5130   if (must_constrain)
5131     {
5132       write_indent (indent + 2);
5133       printf ("if (! constrain_operands (reload_completed))\n");
5134       write_indent (indent + 2);
5135       printf ("  fatal_insn_not_found (insn);\n");
5136     }
5137
5138   write_attr_set (attr, indent + 2, av->value, prefix, suffix,
5139                   known_true, av->first_insn->insn_code,
5140                   av->first_insn->insn_index);
5141
5142   if (strncmp (prefix, "return", 6))
5143     {
5144       write_indent (indent + 2);
5145       printf ("break;\n");
5146     }
5147   printf ("\n");
5148 }
5149 \f
5150 /* Search for uses of non-const attributes and write code to cache them.  */
5151
5152 static int
5153 write_expr_attr_cache (p, attr)
5154      rtx p;
5155      struct attr_desc *attr;
5156 {
5157   const char *fmt;
5158   int i, ie, j, je;
5159
5160   if (GET_CODE (p) == EQ_ATTR)
5161     {
5162       if (XSTR (p, 0) != attr->name)
5163         return 0;
5164
5165       if (!attr->is_numeric)
5166         printf ("  register enum attr_%s ", attr->name);
5167       else if (attr->unsigned_p)
5168         printf ("  register unsigned int ");
5169       else
5170         printf ("  register int ");
5171
5172       printf ("attr_%s = get_attr_%s (insn);\n", attr->name, attr->name);
5173       return 1;
5174     }
5175
5176   fmt = GET_RTX_FORMAT (GET_CODE (p));
5177   ie = GET_RTX_LENGTH (GET_CODE (p));
5178   for (i = 0; i < ie; i++)
5179     {
5180       switch (*fmt++)
5181         {
5182         case 'e':
5183           if (write_expr_attr_cache (XEXP (p, i), attr))
5184             return 1;
5185           break;
5186
5187         case 'E':
5188           je = XVECLEN (p, i);
5189           for (j = 0; j < je; ++j)
5190             if (write_expr_attr_cache (XVECEXP (p, i, j), attr))
5191               return 1;
5192           break;
5193         }
5194     }
5195
5196   return 0;
5197 }
5198
5199 /* Evaluate an expression at top level.  A front end to write_test_expr,
5200    in which we cache attribute values and break up excessively large
5201    expressions to cater to older compilers.  */
5202
5203 static void
5204 write_toplevel_expr (p)
5205      rtx p;
5206 {
5207   struct attr_desc *attr;
5208   int i;
5209
5210   for (i = 0; i < MAX_ATTRS_INDEX; ++i)
5211     for (attr = attrs[i]; attr ; attr = attr->next)
5212       if (!attr->is_const)
5213         write_expr_attr_cache (p, attr);
5214
5215   printf("  register unsigned long accum = 0;\n\n");
5216
5217   while (GET_CODE (p) == IOR)
5218     {
5219       rtx e;
5220       if (GET_CODE (XEXP (p, 0)) == IOR)
5221         e = XEXP (p, 1), p = XEXP (p, 0);
5222       else
5223         e = XEXP (p, 0), p = XEXP (p, 1);
5224
5225       printf ("  accum |= ");
5226       write_test_expr (e, 3);
5227       printf (";\n");
5228     }
5229   printf ("  accum |= ");
5230   write_test_expr (p, 3);
5231   printf (";\n");
5232 }
5233 \f
5234 /* Utilities to write names in various forms.  */
5235
5236 static void
5237 write_unit_name (prefix, num, suffix)
5238      const char *prefix;
5239      int num;
5240      const char *suffix;
5241 {
5242   struct function_unit *unit;
5243
5244   for (unit = units; unit; unit = unit->next)
5245     if (unit->num == num)
5246       {
5247         printf ("%s%s%s", prefix, unit->name, suffix);
5248         return;
5249       }
5250
5251   printf ("%s<unknown>%s", prefix, suffix);
5252 }
5253
5254 static void
5255 write_attr_valueq (attr, s)
5256      struct attr_desc *attr;
5257      const char *s;
5258 {
5259   if (attr->is_numeric)
5260     {
5261       int num = atoi (s);
5262
5263       printf ("%d", num);
5264
5265       /* Make the blockage range values and function units used values easier
5266          to read.  */
5267       if (attr->func_units_p)
5268         {
5269           if (num == -1)
5270             printf (" /* units: none */");
5271           else if (num >= 0)
5272             write_unit_name (" /* units: ", num, " */");
5273           else
5274             {
5275               int i;
5276               const char *sep = " /* units: ";
5277               for (i = 0, num = ~num; num; i++, num >>= 1)
5278                 if (num & 1)
5279                   {
5280                     write_unit_name (sep, i, (num == 1) ? " */" : "");
5281                     sep = ", ";
5282                   }
5283             }
5284         }
5285
5286       else if (attr->blockage_p)
5287         printf (" /* min %d, max %d */", num >> (HOST_BITS_PER_INT / 2),
5288                 num & ((1 << (HOST_BITS_PER_INT / 2)) - 1));
5289
5290       else if (num > 9 || num < 0)
5291         printf (" /* 0x%x */", num);
5292     }
5293   else
5294     {
5295       write_upcase (attr->name);
5296       printf ("_");
5297       write_upcase (s);
5298     }
5299 }
5300
5301 static void
5302 write_attr_value (attr, value)
5303      struct attr_desc *attr;
5304      rtx value;
5305 {
5306   int op;
5307
5308   switch (GET_CODE (value))
5309     {
5310     case CONST_STRING:
5311       write_attr_valueq (attr, XSTR (value, 0));
5312       break;
5313
5314     case SYMBOL_REF:
5315       fputs (XSTR (value, 0), stdout);
5316       break;
5317
5318     case ATTR:
5319       {
5320         struct attr_desc *attr2 = find_attr (XSTR (value, 0), 0);
5321         printf ("get_attr_%s (%s)", attr2->name,
5322                 (attr2->is_const ? "" : "insn"));
5323       }
5324       break;
5325
5326     case PLUS:
5327       op = '+';
5328       goto do_operator;
5329     case MINUS:
5330       op = '-';
5331       goto do_operator;
5332     case MULT:
5333       op = '*';
5334       goto do_operator;
5335     case DIV:
5336       op = '/';
5337       goto do_operator;
5338     case MOD:
5339       op = '%';
5340       goto do_operator;
5341
5342     do_operator:
5343       write_attr_value (attr, XEXP (value, 0));
5344       putchar (' ');
5345       putchar (op);
5346       putchar (' ');
5347       write_attr_value (attr, XEXP (value, 1));
5348       break;
5349
5350     default:
5351       abort ();
5352     }
5353 }
5354
5355 static void
5356 write_upcase (str)
5357      const char *str;
5358 {
5359   while (*str)
5360   {
5361     /* The argument of TOUPPER should not have side effects.  */
5362     putchar (TOUPPER(*str));
5363     str++;
5364   }
5365 }
5366
5367 static void
5368 write_indent (indent)
5369      int indent;
5370 {
5371   for (; indent > 8; indent -= 8)
5372     printf ("\t");
5373
5374   for (; indent; indent--)
5375     printf (" ");
5376 }
5377 \f
5378 /* Write a subroutine that is given an insn that requires a delay slot, a
5379    delay slot ordinal, and a candidate insn.  It returns non-zero if the
5380    candidate can be placed in the specified delay slot of the insn.
5381
5382    We can write as many as three subroutines.  `eligible_for_delay'
5383    handles normal delay slots, `eligible_for_annul_true' indicates that
5384    the specified insn can be annulled if the branch is true, and likewise
5385    for `eligible_for_annul_false'.
5386
5387    KIND is a string distinguishing these three cases ("delay", "annul_true",
5388    or "annul_false").  */
5389
5390 static void
5391 write_eligible_delay (kind)
5392   const char *kind;
5393 {
5394   struct delay_desc *delay;
5395   int max_slots;
5396   char str[50];
5397   struct attr_desc *attr;
5398   struct attr_value *av, *common_av;
5399   int i;
5400
5401   /* Compute the maximum number of delay slots required.  We use the delay
5402      ordinal times this number plus one, plus the slot number as an index into
5403      the appropriate predicate to test.  */
5404
5405   for (delay = delays, max_slots = 0; delay; delay = delay->next)
5406     if (XVECLEN (delay->def, 1) / 3 > max_slots)
5407       max_slots = XVECLEN (delay->def, 1) / 3;
5408
5409   /* Write function prelude.  */
5410
5411   printf ("int\n");
5412   printf ("eligible_for_%s (delay_insn, slot, candidate_insn, flags)\n",
5413            kind);
5414   printf ("     rtx delay_insn;\n");
5415   printf ("     int slot;\n");
5416   printf ("     rtx candidate_insn;\n");
5417   printf ("     int flags ATTRIBUTE_UNUSED;\n");
5418   printf ("{\n");
5419   printf ("  rtx insn;\n");
5420   printf ("\n");
5421   printf ("  if (slot >= %d)\n", max_slots);
5422   printf ("    abort ();\n");
5423   printf ("\n");
5424
5425   /* If more than one delay type, find out which type the delay insn is.  */
5426
5427   if (num_delays > 1)
5428     {
5429       attr = find_attr ("*delay_type", 0);
5430       if (! attr) abort ();
5431       common_av = find_most_used (attr);
5432
5433       printf ("  insn = delay_insn;\n");
5434       printf ("  switch (recog_memoized (insn))\n");
5435       printf ("    {\n");
5436
5437       sprintf (str, " * %d;\n      break;", max_slots);
5438       for (av = attr->first_value; av; av = av->next)
5439         if (av != common_av)
5440           write_attr_case (attr, av, 1, "slot +=", str, 4, true_rtx);
5441
5442       write_attr_case (attr, common_av, 0, "slot +=", str, 4, true_rtx);
5443       printf ("    }\n\n");
5444
5445       /* Ensure matched.  Otherwise, shouldn't have been called.  */
5446       printf ("  if (slot < %d)\n", max_slots);
5447       printf ("    abort ();\n\n");
5448     }
5449
5450   /* If just one type of delay slot, write simple switch.  */
5451   if (num_delays == 1 && max_slots == 1)
5452     {
5453       printf ("  insn = candidate_insn;\n");
5454       printf ("  switch (recog_memoized (insn))\n");
5455       printf ("    {\n");
5456
5457       attr = find_attr ("*delay_1_0", 0);
5458       if (! attr) abort ();
5459       common_av = find_most_used (attr);
5460
5461       for (av = attr->first_value; av; av = av->next)
5462         if (av != common_av)
5463           write_attr_case (attr, av, 1, "return", ";", 4, true_rtx);
5464
5465       write_attr_case (attr, common_av, 0, "return", ";", 4, true_rtx);
5466       printf ("    }\n");
5467     }
5468
5469   else
5470     {
5471       /* Write a nested CASE.  The first indicates which condition we need to
5472          test, and the inner CASE tests the condition.  */
5473       printf ("  insn = candidate_insn;\n");
5474       printf ("  switch (slot)\n");
5475       printf ("    {\n");
5476
5477       for (delay = delays; delay; delay = delay->next)
5478         for (i = 0; i < XVECLEN (delay->def, 1); i += 3)
5479           {
5480             printf ("    case %d:\n",
5481                     (i / 3) + (num_delays == 1 ? 0 : delay->num * max_slots));
5482             printf ("      switch (recog_memoized (insn))\n");
5483             printf ("\t{\n");
5484
5485             sprintf (str, "*%s_%d_%d", kind, delay->num, i / 3);
5486             attr = find_attr (str, 0);
5487             if (! attr) abort ();
5488             common_av = find_most_used (attr);
5489
5490             for (av = attr->first_value; av; av = av->next)
5491               if (av != common_av)
5492                 write_attr_case (attr, av, 1, "return", ";", 8, true_rtx);
5493
5494             write_attr_case (attr, common_av, 0, "return", ";", 8, true_rtx);
5495             printf ("      }\n");
5496           }
5497
5498       printf ("    default:\n");
5499       printf ("      abort ();\n");
5500       printf ("    }\n");
5501     }
5502
5503   printf ("}\n\n");
5504 }
5505 \f
5506 /* Write routines to compute conflict cost for function units.  Then write a
5507    table describing the available function units.  */
5508
5509 static void
5510 write_function_unit_info ()
5511 {
5512   struct function_unit *unit;
5513   int i;
5514
5515   /* Write out conflict routines for function units.  Don't bother writing
5516      one if there is only one issue delay value.  */
5517
5518   for (unit = units; unit; unit = unit->next)
5519     {
5520       if (unit->needs_blockage_function)
5521         write_complex_function (unit, "blockage", "block");
5522
5523       /* If the minimum and maximum conflict costs are the same, there
5524          is only one value, so we don't need a function.  */
5525       if (! unit->needs_conflict_function)
5526         {
5527           unit->default_cost = make_numeric_value (unit->issue_delay.max);
5528           continue;
5529         }
5530
5531       /* The function first computes the case from the candidate insn.  */
5532       unit->default_cost = make_numeric_value (0);
5533       write_complex_function (unit, "conflict_cost", "cost");
5534     }
5535
5536   /* Now that all functions have been written, write the table describing
5537      the function units.   The name is included for documentation purposes
5538      only.  */
5539
5540   printf ("struct function_unit_desc function_units[] = {\n");
5541
5542   /* Write out the descriptions in numeric order, but don't force that order
5543      on the list.  Doing so increases the runtime of genattrtab.c.  */
5544   for (i = 0; i < num_units; i++)
5545     {
5546       for (unit = units; unit; unit = unit->next)
5547         if (unit->num == i)
5548           break;
5549
5550       printf ("  {\"%s\", %d, %d, %d, %s, %d, %s_unit_ready_cost, ",
5551               unit->name, 1 << unit->num, unit->multiplicity,
5552               unit->simultaneity, XSTR (unit->default_cost, 0),
5553               unit->issue_delay.max, unit->name);
5554
5555       if (unit->needs_conflict_function)
5556         printf ("%s_unit_conflict_cost, ", unit->name);
5557       else
5558         printf ("0, ");
5559
5560       printf ("%d, ", unit->max_blockage);
5561
5562       if (unit->needs_range_function)
5563         printf ("%s_unit_blockage_range, ", unit->name);
5564       else
5565         printf ("0, ");
5566
5567       if (unit->needs_blockage_function)
5568         printf ("%s_unit_blockage", unit->name);
5569       else
5570         printf ("0");
5571
5572       printf ("}, \n");
5573     }
5574
5575   printf ("};\n\n");
5576 }
5577
5578 static void
5579 write_complex_function (unit, name, connection)
5580      struct function_unit *unit;
5581      const char *name, *connection;
5582 {
5583   struct attr_desc *case_attr, *attr;
5584   struct attr_value *av, *common_av;
5585   rtx value;
5586   char *str;
5587   int using_case;
5588   int i;
5589
5590   printf ("static int %s_unit_%s PARAMS ((rtx, rtx));\n", unit->name, name);
5591   printf ("static int\n");
5592   printf ("%s_unit_%s (executing_insn, candidate_insn)\n",
5593           unit->name, name);
5594   printf ("     rtx executing_insn;\n");
5595   printf ("     rtx candidate_insn;\n");
5596   printf ("{\n");
5597   printf ("  rtx insn;\n");
5598   printf ("  int casenum;\n\n");
5599   printf ("  insn = executing_insn;\n");
5600   printf ("  switch (recog_memoized (insn))\n");
5601   printf ("    {\n");
5602
5603   /* Write the `switch' statement to get the case value.  */
5604   str = (char *) alloca (strlen (unit->name) + strlen (name) + strlen (connection) + 10);
5605   sprintf (str, "*%s_cases", unit->name);
5606   case_attr = find_attr (str, 0);
5607   if (! case_attr) abort ();
5608   common_av = find_most_used (case_attr);
5609
5610   for (av = case_attr->first_value; av; av = av->next)
5611     if (av != common_av)
5612       write_attr_case (case_attr, av, 1,
5613                        "casenum =", ";", 4, unit->condexp);
5614
5615   write_attr_case (case_attr, common_av, 0,
5616                    "casenum =", ";", 4, unit->condexp);
5617   printf ("    }\n\n");
5618
5619   /* Now write an outer switch statement on each case.  Then write
5620      the tests on the executing function within each.  */
5621   printf ("  insn = candidate_insn;\n");
5622   printf ("  switch (casenum)\n");
5623   printf ("    {\n");
5624
5625   for (i = 0; i < unit->num_opclasses; i++)
5626     {
5627       /* Ensure using this case.  */
5628       using_case = 0;
5629       for (av = case_attr->first_value; av; av = av->next)
5630         if (av->num_insns
5631             && contained_in_p (make_numeric_value (i), av->value))
5632           using_case = 1;
5633
5634       if (! using_case)
5635         continue;
5636
5637       printf ("    case %d:\n", i);
5638       sprintf (str, "*%s_%s_%d", unit->name, connection, i);
5639       attr = find_attr (str, 0);
5640       if (! attr) abort ();
5641
5642       /* If single value, just write it.  */
5643       value = find_single_value (attr);
5644       if (value)
5645         write_attr_set (attr, 6, value, "return", ";\n", true_rtx, -2, -2);
5646       else
5647         {
5648           common_av = find_most_used (attr);
5649           printf ("      switch (recog_memoized (insn))\n");
5650           printf ("\t{\n");
5651
5652           for (av = attr->first_value; av; av = av->next)
5653             if (av != common_av)
5654               write_attr_case (attr, av, 1,
5655                                "return", ";", 8, unit->condexp);
5656
5657           write_attr_case (attr, common_av, 0,
5658                            "return", ";", 8, unit->condexp);
5659           printf ("      }\n\n");
5660         }
5661     }
5662
5663   /* This default case should not be needed, but gcc's analysis is not
5664      good enough to realize that the default case is not needed for the
5665      second switch statement.  */
5666   printf ("    default:\n      abort ();\n");
5667   printf ("    }\n}\n\n");
5668 }
5669 \f
5670 /* This page contains miscellaneous utility routines.  */
5671
5672 /* Given a string, return the number of comma-separated elements in it.
5673    Return 0 for the null string.  */
5674
5675 static int
5676 n_comma_elts (s)
5677      const char *s;
5678 {
5679   int n;
5680
5681   if (*s == '\0')
5682     return 0;
5683
5684   for (n = 1; *s; s++)
5685     if (*s == ',')
5686       n++;
5687
5688   return n;
5689 }
5690
5691 /* Given a pointer to a (char *), return a malloc'ed string containing the
5692    next comma-separated element.  Advance the pointer to after the string
5693    scanned, or the end-of-string.  Return NULL if at end of string.  */
5694
5695 static char *
5696 next_comma_elt (pstr)
5697      const char **pstr;
5698 {
5699   char *out_str;
5700   const char *p;
5701
5702   if (**pstr == '\0')
5703     return NULL;
5704
5705   /* Find end of string to compute length.  */
5706   for (p = *pstr; *p != ',' && *p != '\0'; p++)
5707     ;
5708
5709   out_str = attr_string (*pstr, p - *pstr);
5710   *pstr = p;
5711
5712   if (**pstr == ',')
5713     (*pstr)++;
5714
5715   return out_str;
5716 }
5717
5718 /* Return a `struct attr_desc' pointer for a given named attribute.  If CREATE
5719    is non-zero, build a new attribute, if one does not exist.  */
5720
5721 static struct attr_desc *
5722 find_attr (name, create)
5723      const char *name;
5724      int create;
5725 {
5726   struct attr_desc *attr;
5727   int index;
5728
5729   /* Before we resort to using `strcmp', see if the string address matches
5730      anywhere.  In most cases, it should have been canonicalized to do so.  */
5731   if (name == alternative_name)
5732     return NULL;
5733
5734   index = name[0] & (MAX_ATTRS_INDEX - 1);
5735   for (attr = attrs[index]; attr; attr = attr->next)
5736     if (name == attr->name)
5737       return attr;
5738
5739   /* Otherwise, do it the slow way.  */
5740   for (attr = attrs[index]; attr; attr = attr->next)
5741     if (name[0] == attr->name[0] && ! strcmp (name, attr->name))
5742       return attr;
5743
5744   if (! create)
5745     return NULL;
5746
5747   attr = (struct attr_desc *) oballoc (sizeof (struct attr_desc));
5748   attr->name = attr_string (name, strlen (name));
5749   attr->first_value = attr->default_val = NULL;
5750   attr->is_numeric = attr->negative_ok = attr->is_const = attr->is_special = 0;
5751   attr->unsigned_p = attr->func_units_p = attr->blockage_p = 0;
5752   attr->next = attrs[index];
5753   attrs[index] = attr;
5754
5755   return attr;
5756 }
5757
5758 /* Create internal attribute with the given default value.  */
5759
5760 static void
5761 make_internal_attr (name, value, special)
5762      const char *name;
5763      rtx value;
5764      int special;
5765 {
5766   struct attr_desc *attr;
5767
5768   attr = find_attr (name, 1);
5769   if (attr->default_val)
5770     abort ();
5771
5772   attr->is_numeric = 1;
5773   attr->is_const = 0;
5774   attr->is_special = (special & 1) != 0;
5775   attr->negative_ok = (special & 2) != 0;
5776   attr->unsigned_p = (special & 4) != 0;
5777   attr->func_units_p = (special & 8) != 0;
5778   attr->blockage_p = (special & 16) != 0;
5779   attr->default_val = get_attr_value (value, attr, -2);
5780 }
5781
5782 /* Find the most used value of an attribute.  */
5783
5784 static struct attr_value *
5785 find_most_used (attr)
5786      struct attr_desc *attr;
5787 {
5788   struct attr_value *av;
5789   struct attr_value *most_used;
5790   int nuses;
5791
5792   most_used = NULL;
5793   nuses = -1;
5794
5795   for (av = attr->first_value; av; av = av->next)
5796     if (av->num_insns > nuses)
5797       nuses = av->num_insns, most_used = av;
5798
5799   return most_used;
5800 }
5801
5802 /* If an attribute only has a single value used, return it.  Otherwise
5803    return NULL.  */
5804
5805 static rtx
5806 find_single_value (attr)
5807      struct attr_desc *attr;
5808 {
5809   struct attr_value *av;
5810   rtx unique_value;
5811
5812   unique_value = NULL;
5813   for (av = attr->first_value; av; av = av->next)
5814     if (av->num_insns)
5815       {
5816         if (unique_value)
5817           return NULL;
5818         else
5819           unique_value = av->value;
5820       }
5821
5822   return unique_value;
5823 }
5824
5825 /* Return (attr_value "n") */
5826
5827 static rtx
5828 make_numeric_value (n)
5829      int n;
5830 {
5831   static rtx int_values[20];
5832   rtx exp;
5833   char *p;
5834
5835   if (n < 0)
5836     abort ();
5837
5838   if (n < 20 && int_values[n])
5839     return int_values[n];
5840
5841   p = attr_printf (MAX_DIGITS, "%d", n);
5842   exp = attr_rtx (CONST_STRING, p);
5843
5844   if (n < 20)
5845     int_values[n] = exp;
5846
5847   return exp;
5848 }
5849 \f
5850 static void
5851 extend_range (range, min, max)
5852      struct range *range;
5853      int min;
5854      int max;
5855 {
5856   if (range->min > min) range->min = min;
5857   if (range->max < max) range->max = max;
5858 }
5859
5860 PTR
5861 xrealloc (old, size)
5862   PTR old;
5863   size_t size;
5864 {
5865   register PTR ptr;
5866   if (old)
5867     ptr = (PTR) realloc (old, size);
5868   else
5869     ptr = (PTR) malloc (size);
5870   if (!ptr)
5871     fatal ("virtual memory exhausted");
5872   return ptr;
5873 }
5874
5875 PTR
5876 xmalloc (size)
5877   size_t size;
5878 {
5879   register PTR val = (PTR) malloc (size);
5880
5881   if (val == 0)
5882     fatal ("virtual memory exhausted");
5883   return val;
5884 }
5885
5886 static rtx
5887 copy_rtx_unchanging (orig)
5888      register rtx orig;
5889 {
5890 #if 0
5891   register rtx copy;
5892   register RTX_CODE code;
5893 #endif
5894
5895   if (RTX_UNCHANGING_P (orig) || MEM_IN_STRUCT_P (orig))
5896     return orig;
5897
5898   MEM_IN_STRUCT_P (orig) = 1;
5899   return orig;
5900
5901 #if 0
5902   code = GET_CODE (orig);
5903   switch (code)
5904     {
5905     case CONST_INT:
5906     case CONST_DOUBLE:
5907     case SYMBOL_REF:
5908     case CODE_LABEL:
5909       return orig;
5910
5911     default:
5912       break;
5913     }
5914
5915   copy = rtx_alloc (code);
5916   PUT_MODE (copy, GET_MODE (orig));
5917   RTX_UNCHANGING_P (copy) = 1;
5918
5919   bcopy ((char *) &XEXP (orig, 0), (char *) &XEXP (copy, 0),
5920          GET_RTX_LENGTH (GET_CODE (copy)) * sizeof (rtx));
5921   return copy;
5922 #endif
5923 }
5924
5925 /* Determine if an insn has a constant number of delay slots, i.e., the
5926    number of delay slots is not a function of the length of the insn.  */
5927
5928 static void
5929 write_const_num_delay_slots ()
5930 {
5931   struct attr_desc *attr = find_attr ("*num_delay_slots", 0);
5932   struct attr_value *av;
5933   struct insn_ent *ie;
5934
5935   if (attr)
5936     {
5937       printf ("int\nconst_num_delay_slots (insn)\n");
5938       printf ("     rtx insn;\n");
5939       printf ("{\n");
5940       printf ("  switch (recog_memoized (insn))\n");
5941       printf ("    {\n");
5942
5943       for (av = attr->first_value; av; av = av->next)
5944         {
5945           length_used = 0;
5946           walk_attr_value (av->value);
5947           if (length_used)
5948             {
5949               for (ie = av->first_insn; ie; ie = ie->next)
5950               if (ie->insn_code != -1)
5951                 printf ("    case %d:\n", ie->insn_code);
5952               printf ("      return 0;\n");
5953             }
5954         }
5955
5956       printf ("    default:\n");
5957       printf ("      return 1;\n");
5958       printf ("    }\n}\n\n");
5959     }
5960 }
5961
5962 \f
5963 extern int main PARAMS ((int, char **));
5964
5965 int
5966 main (argc, argv)
5967      int argc;
5968      char **argv;
5969 {
5970   rtx desc;
5971   struct attr_desc *attr;
5972   struct insn_def *id;
5973   rtx tem;
5974   int i;
5975
5976   progname = "genattrtab";
5977
5978   if (argc <= 1)
5979     fatal ("No input file name.");
5980
5981   if (init_md_reader (argv[1]) != SUCCESS_EXIT_CODE)
5982     return (FATAL_EXIT_CODE);
5983
5984 #if defined (RLIMIT_STACK) && defined (HAVE_GETRLIMIT) && defined (HAVE_SETRLIMIT)
5985   /* Get rid of any avoidable limit on stack size.  */
5986   {
5987     struct rlimit rlim;
5988
5989     /* Set the stack limit huge so that alloca does not fail.  */
5990     getrlimit (RLIMIT_STACK, &rlim);
5991     rlim.rlim_cur = rlim.rlim_max;
5992     setrlimit (RLIMIT_STACK, &rlim);
5993   }
5994 #endif
5995
5996   progname = "genattrtab";
5997   obstack_init (rtl_obstack);
5998   obstack_init (hash_obstack);
5999   obstack_init (temp_obstack);
6000
6001   /* Set up true and false rtx's */
6002   true_rtx = rtx_alloc (CONST_INT);
6003   XWINT (true_rtx, 0) = 1;
6004   false_rtx = rtx_alloc (CONST_INT);
6005   XWINT (false_rtx, 0) = 0;
6006   RTX_UNCHANGING_P (true_rtx) = RTX_UNCHANGING_P (false_rtx) = 1;
6007   RTX_INTEGRATED_P (true_rtx) = RTX_INTEGRATED_P (false_rtx) = 1;
6008
6009   alternative_name = attr_string ("alternative", strlen ("alternative"));
6010
6011   printf ("/* Generated automatically by the program `genattrtab'\n\
6012 from the machine description file `md'.  */\n\n");
6013
6014   /* Read the machine description.  */
6015
6016   while (1)
6017     {
6018       int line_no;
6019
6020       desc = read_md_rtx (&line_no, &insn_code_number);
6021       if (desc == NULL)
6022         break;
6023
6024       switch (GET_CODE (desc))
6025         {
6026           case DEFINE_INSN:
6027           case DEFINE_PEEPHOLE:
6028           case DEFINE_ASM_ATTRIBUTES:
6029               gen_insn(desc);
6030               break;
6031
6032           case DEFINE_ATTR:
6033               gen_attr (desc);
6034               break;
6035
6036           case DEFINE_DELAY:
6037               gen_delay (desc);
6038               break;
6039
6040           case DEFINE_FUNCTION_UNIT:
6041               gen_unit (desc);
6042               break;
6043
6044           default:
6045               break;
6046         }
6047       if (GET_CODE (desc) != DEFINE_ASM_ATTRIBUTES)
6048         insn_index_number++;
6049     }
6050
6051   insn_code_number++;
6052
6053   /* If we didn't have a DEFINE_ASM_ATTRIBUTES, make a null one.  */
6054   if (! got_define_asm_attributes)
6055     {
6056       tem = rtx_alloc (DEFINE_ASM_ATTRIBUTES);
6057       XVEC (tem, 0) = rtvec_alloc (0);
6058       gen_insn (tem);
6059     }
6060
6061   /* Expand DEFINE_DELAY information into new attribute.  */
6062   if (num_delays)
6063     expand_delays ();
6064
6065   /* Expand DEFINE_FUNCTION_UNIT information into new attributes.  */
6066   if (num_units)
6067     expand_units ();
6068
6069   printf ("#include \"config.h\"\n");
6070   printf ("#include \"system.h\"\n");
6071   printf ("#include \"rtl.h\"\n");
6072   printf ("#include \"tm_p.h\"\n");
6073   printf ("#include \"insn-config.h\"\n");
6074   printf ("#include \"recog.h\"\n");
6075   printf ("#include \"regs.h\"\n");
6076   printf ("#include \"real.h\"\n");
6077   printf ("#include \"output.h\"\n");
6078   printf ("#include \"insn-attr.h\"\n");
6079   printf ("#include \"toplev.h\"\n");
6080   printf ("\n");
6081   printf ("#define operands recog_data.operand\n\n");
6082
6083   /* Make `insn_alternatives'.  */
6084   insn_alternatives = (int *) oballoc (insn_code_number * sizeof (int));
6085   for (id = defs; id; id = id->next)
6086     if (id->insn_code >= 0)
6087       insn_alternatives[id->insn_code] = (1 << id->num_alternatives) - 1;
6088
6089   /* Make `insn_n_alternatives'.  */
6090   insn_n_alternatives = (int *) oballoc (insn_code_number * sizeof (int));
6091   for (id = defs; id; id = id->next)
6092     if (id->insn_code >= 0)
6093       insn_n_alternatives[id->insn_code] = id->num_alternatives;
6094
6095   /* Prepare to write out attribute subroutines by checking everything stored
6096      away and building the attribute cases.  */
6097
6098   check_defs ();
6099   for (i = 0; i < MAX_ATTRS_INDEX; i++)
6100     for (attr = attrs[i]; attr; attr = attr->next)
6101       {
6102         attr->default_val->value
6103           = check_attr_value (attr->default_val->value, attr);
6104         fill_attr (attr);
6105       }
6106
6107   /* Construct extra attributes for `length'.  */
6108   make_length_attrs ();
6109
6110   /* Perform any possible optimizations to speed up compilation.  */
6111   optimize_attrs ();
6112
6113   /* Now write out all the `gen_attr_...' routines.  Do these before the
6114      special routines (specifically before write_function_unit_info), so
6115      that they get defined before they are used.  */
6116
6117   for (i = 0; i < MAX_ATTRS_INDEX; i++)
6118     for (attr = attrs[i]; attr; attr = attr->next)
6119       {
6120         if (! attr->is_special && ! attr->is_const)
6121           write_attr_get (attr);
6122       }
6123
6124   /* Write out delay eligibility information, if DEFINE_DELAY present.
6125      (The function to compute the number of delay slots will be written
6126      below.)  */
6127   if (num_delays)
6128     {
6129       write_eligible_delay ("delay");
6130       if (have_annul_true)
6131         write_eligible_delay ("annul_true");
6132       if (have_annul_false)
6133         write_eligible_delay ("annul_false");
6134     }
6135
6136   /* Write out information about function units.  */
6137   if (num_units)
6138     write_function_unit_info ();
6139
6140   /* Write out constant delay slot info */
6141   write_const_num_delay_slots ();
6142
6143   write_length_unit_log ();
6144
6145   fflush (stdout);
6146   return (ferror (stdout) != 0 ? FATAL_EXIT_CODE : SUCCESS_EXIT_CODE);
6147 }
6148
6149 /* Define this so we can link with print-rtl.o to get debug_rtx function.  */
6150 const char *
6151 get_insn_name (code)
6152      int code ATTRIBUTE_UNUSED;
6153 {
6154   return NULL;
6155 }