gcc/genattrtab.c

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