OSDN Git Service

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