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