gcc/genattrtab.c

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