OSDN Git Service

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