OSDN Git Service

* tree.c (get_callee_fndecl): Move DECL_ABSTRACT_ORIGIN-following...
[pf3gnuchains/gcc-fork.git] / gcc / tree.c
1 /* Language-independent node constructors for parse phase of GNU compiler.
2    Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3    1999, 2000, 2001 Free Software Foundation, Inc.
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
10 version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING.  If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
20 02111-1307, USA.  */
21
22 /* This file contains the low level primitives for operating on tree nodes,
23    including allocation, list operations, interning of identifiers,
24    construction of data type nodes and statement nodes,
25    and construction of type conversion nodes.  It also contains
26    tables index by tree code that describe how to take apart
27    nodes of that code.
28
29    It is intended to be language-independent, but occasionally
30    calls language-dependent routines defined (for C) in typecheck.c.
31
32    The low-level allocation routines oballoc and permalloc
33    are used also for allocating many other kinds of objects
34    by all passes of the compiler.  */
35
36 #include "config.h"
37 #include "system.h"
38 #include "flags.h"
39 #include "tree.h"
40 #include "tm_p.h"
41 #include "function.h"
42 #include "obstack.h"
43 #include "toplev.h"
44 #include "ggc.h"
45 #include "hashtab.h"
46 #include "output.h"
47 #include "target.h"
48 #include "langhooks.h"
49
50 #define obstack_chunk_alloc xmalloc
51 #define obstack_chunk_free free
52 /* obstack.[ch] explicitly declined to prototype this.  */
53 extern int _obstack_allocated_p PARAMS ((struct obstack *h, PTR obj));
54
55 static void unsave_expr_now_r PARAMS ((tree));
56
57 /* Objects allocated on this obstack last forever.  */
58
59 struct obstack permanent_obstack;
60
61 /* Table indexed by tree code giving a string containing a character
62    classifying the tree code.  Possibilities are
63    t, d, s, c, r, <, 1, 2 and e.  See tree.def for details.  */
64
65 #define DEFTREECODE(SYM, NAME, TYPE, LENGTH) TYPE,
66
67 char tree_code_type[MAX_TREE_CODES] = {
68 #include "tree.def"
69 };
70 #undef DEFTREECODE
71
72 /* Table indexed by tree code giving number of expression
73    operands beyond the fixed part of the node structure.
74    Not used for types or decls.  */
75
76 #define DEFTREECODE(SYM, NAME, TYPE, LENGTH) LENGTH,
77
78 int tree_code_length[MAX_TREE_CODES] = {
79 #include "tree.def"
80 };
81 #undef DEFTREECODE
82
83 /* Names of tree components.
84    Used for printing out the tree and error messages.  */
85 #define DEFTREECODE(SYM, NAME, TYPE, LEN) NAME,
86
87 const char *tree_code_name[MAX_TREE_CODES] = {
88 #include "tree.def"
89 };
90 #undef DEFTREECODE
91
92 /* Statistics-gathering stuff.  */
93 typedef enum
94 {
95   d_kind,
96   t_kind,
97   b_kind,
98   s_kind,
99   r_kind,
100   e_kind,
101   c_kind,
102   id_kind,
103   perm_list_kind,
104   temp_list_kind,
105   vec_kind,
106   x_kind,
107   lang_decl,
108   lang_type,
109   all_kinds
110 } tree_node_kind;
111
112 int tree_node_counts[(int) all_kinds];
113 int tree_node_sizes[(int) all_kinds];
114
115 static const char * const tree_node_kind_names[] = {
116   "decls",
117   "types",
118   "blocks",
119   "stmts",
120   "refs",
121   "exprs",
122   "constants",
123   "identifiers",
124   "perm_tree_lists",
125   "temp_tree_lists",
126   "vecs",
127   "random kinds",
128   "lang_decl kinds",
129   "lang_type kinds"
130 };
131
132 /* Unique id for next decl created.  */
133 static int next_decl_uid;
134 /* Unique id for next type created.  */
135 static int next_type_uid = 1;
136
137 /* Since we cannot rehash a type after it is in the table, we have to
138    keep the hash code.  */
139
140 struct type_hash
141 {
142   unsigned long hash;
143   tree type;
144 };
145
146 /* Initial size of the hash table (rounded to next prime).  */
147 #define TYPE_HASH_INITIAL_SIZE 1000
148
149 /* Now here is the hash table.  When recording a type, it is added to
150    the slot whose index is the hash code.  Note that the hash table is
151    used for several kinds of types (function types, array types and
152    array index range types, for now).  While all these live in the
153    same table, they are completely independent, and the hash code is
154    computed differently for each of these.  */
155
156 htab_t type_hash_table;
157
158 static void build_real_from_int_cst_1 PARAMS ((PTR));
159 static void set_type_quals PARAMS ((tree, int));
160 static void append_random_chars PARAMS ((char *));
161 static int type_hash_eq PARAMS ((const void*, const void*));
162 static unsigned int type_hash_hash PARAMS ((const void*));
163 static void print_type_hash_statistics PARAMS((void));
164 static void finish_vector_type PARAMS((tree));
165 static int type_hash_marked_p PARAMS ((const void *));
166 static void type_hash_mark PARAMS ((const void *));
167 static int mark_tree_hashtable_entry PARAMS((void **, void *));
168
169 /* If non-null, these are language-specific helper functions for
170    unsave_expr_now.  If present, LANG_UNSAVE is called before its
171    argument (an UNSAVE_EXPR) is to be unsaved, and all other
172    processing in unsave_expr_now is aborted.  LANG_UNSAVE_EXPR_NOW is
173    called from unsave_expr_1 for language-specific tree codes.  */
174 void (*lang_unsave) PARAMS ((tree *));
175 void (*lang_unsave_expr_now) PARAMS ((tree));
176
177 /* If non-null, these are language-specific helper functions for
178    unsafe_for_reeval.  Return negative to not handle some tree.  */
179 int (*lang_unsafe_for_reeval) PARAMS ((tree));
180
181 /* Set the DECL_ASSEMBLER_NAME for a node.  If it is the sort of thing
182    that the assembler should talk about, set DECL_ASSEMBLER_NAME to an
183    appropriate IDENTIFIER_NODE.  Otherwise, set it to the
184    ERROR_MARK_NODE to ensure that the assembler does not talk about
185    it.  */
186 void (*lang_set_decl_assembler_name)     PARAMS ((tree));
187 \f
188 tree global_trees[TI_MAX];
189 tree integer_types[itk_none];
190 \f
191 /* Set the DECL_ASSEMBLER_NAME for DECL.  */
192 void
193 set_decl_assembler_name (decl)
194      tree decl;
195 {
196   /* The language-independent code should never use the
197      DECL_ASSEMBLER_NAME for lots of DECLs.  Only FUNCTION_DECLs and
198      VAR_DECLs for variables with static storage duration need a real
199      DECL_ASSEMBLER_NAME.  */
200   if (TREE_CODE (decl) == FUNCTION_DECL
201       || (TREE_CODE (decl) == VAR_DECL 
202           && (TREE_STATIC (decl) 
203               || DECL_EXTERNAL (decl) 
204               || TREE_PUBLIC (decl))))
205     /* By default, assume the name to use in assembly code is the
206        same as that used in the source language.  (That's correct
207        for C, and GCC used to set DECL_ASSEMBLER_NAME to the same
208        value as DECL_NAME in build_decl, so this choice provides
209        backwards compatibility with existing front-ends.  */
210     SET_DECL_ASSEMBLER_NAME (decl, DECL_NAME (decl));
211   else
212     /* Nobody should ever be asking for the DECL_ASSEMBLER_NAME of
213        these DECLs -- unless they're in language-dependent code, in
214        which case lang_set_decl_assembler_name should handle things.  */
215     abort ();
216 }
217 \f
218 /* Init the principal obstacks.  */
219
220 void
221 init_obstacks ()
222 {
223   gcc_obstack_init (&permanent_obstack);
224
225   /* Initialize the hash table of types.  */
226   type_hash_table = htab_create (TYPE_HASH_INITIAL_SIZE, type_hash_hash,
227                                  type_hash_eq, 0);
228   ggc_add_deletable_htab (type_hash_table, type_hash_marked_p,
229                           type_hash_mark);
230   ggc_add_tree_root (global_trees, TI_MAX);
231   ggc_add_tree_root (integer_types, itk_none);
232
233   /* Set lang_set_decl_set_assembler_name to a default value.  */
234   lang_set_decl_assembler_name = set_decl_assembler_name;
235 }
236
237 \f
238 /* Allocate SIZE bytes in the permanent obstack
239    and return a pointer to them.  */
240
241 char *
242 permalloc (size)
243      int size;
244 {
245   return (char *) obstack_alloc (&permanent_obstack, size);
246 }
247
248 /* Allocate NELEM items of SIZE bytes in the permanent obstack
249    and return a pointer to them.  The storage is cleared before
250    returning the value.  */
251
252 char *
253 perm_calloc (nelem, size)
254      int nelem;
255      long size;
256 {
257   char *rval = (char *) obstack_alloc (&permanent_obstack, nelem * size);
258   memset (rval, 0, nelem * size);
259   return rval;
260 }
261
262 /* Compute the number of bytes occupied by 'node'.  This routine only
263    looks at TREE_CODE and, if the code is TREE_VEC, TREE_VEC_LENGTH.  */
264 size_t
265 tree_size (node)
266      tree node;
267 {
268   enum tree_code code = TREE_CODE (node);
269
270   switch (TREE_CODE_CLASS (code))
271     {
272     case 'd':  /* A decl node */
273       return sizeof (struct tree_decl);
274
275     case 't':  /* a type node */
276       return sizeof (struct tree_type);
277
278     case 'b':  /* a lexical block node */
279       return sizeof (struct tree_block);
280
281     case 'r':  /* a reference */
282     case 'e':  /* an expression */
283     case 's':  /* an expression with side effects */
284     case '<':  /* a comparison expression */
285     case '1':  /* a unary arithmetic expression */
286     case '2':  /* a binary arithmetic expression */
287       return (sizeof (struct tree_exp)
288               + (TREE_CODE_LENGTH (code) - 1) * sizeof (char *));
289
290     case 'c':  /* a constant */
291       /* We can't use TREE_CODE_LENGTH for INTEGER_CST, since the number of
292          words is machine-dependent due to varying length of HOST_WIDE_INT,
293          which might be wider than a pointer (e.g., long long).  Similarly
294          for REAL_CST, since the number of words is machine-dependent due
295          to varying size and alignment of `double'.  */
296       if (code == INTEGER_CST)
297         return sizeof (struct tree_int_cst);
298       else if (code == REAL_CST)
299         return sizeof (struct tree_real_cst);
300       else
301         return (sizeof (struct tree_common)
302                 + TREE_CODE_LENGTH (code) * sizeof (char *));
303
304     case 'x':  /* something random, like an identifier.  */
305       {
306           size_t length;
307           length = (sizeof (struct tree_common)
308                     + TREE_CODE_LENGTH (code) * sizeof (char *));
309           if (code == TREE_VEC)
310             length += (TREE_VEC_LENGTH (node) - 1) * sizeof (char *);
311           return length;
312       }
313
314     default:
315       abort ();
316     }
317 }
318
319 /* Return a newly allocated node of code CODE.
320    For decl and type nodes, some other fields are initialized.
321    The rest of the node is initialized to zero.
322
323    Achoo!  I got a code in the node.  */
324
325 tree
326 make_node (code)
327      enum tree_code code;
328 {
329   tree t;
330   int type = TREE_CODE_CLASS (code);
331   size_t length;
332 #ifdef GATHER_STATISTICS
333   tree_node_kind kind;
334 #endif
335   struct tree_common ttmp;
336   
337   /* We can't allocate a TREE_VEC without knowing how many elements
338      it will have.  */
339   if (code == TREE_VEC)
340     abort ();
341   
342   TREE_SET_CODE ((tree)&ttmp, code);
343   length = tree_size ((tree)&ttmp);
344
345 #ifdef GATHER_STATISTICS
346   switch (type)
347     {
348     case 'd':  /* A decl node */
349       kind = d_kind;
350       break;
351
352     case 't':  /* a type node */
353       kind = t_kind;
354       break;
355
356     case 'b':  /* a lexical block */
357       kind = b_kind;
358       break;
359
360     case 's':  /* an expression with side effects */
361       kind = s_kind;
362       break;
363
364     case 'r':  /* a reference */
365       kind = r_kind;
366       break;
367
368     case 'e':  /* an expression */
369     case '<':  /* a comparison expression */
370     case '1':  /* a unary arithmetic expression */
371     case '2':  /* a binary arithmetic expression */
372       kind = e_kind;
373       break;
374
375     case 'c':  /* a constant */
376       kind = c_kind;
377       break;
378
379     case 'x':  /* something random, like an identifier.  */
380       if (code == IDENTIFIER_NODE)
381         kind = id_kind;
382       else if (code == TREE_VEC)
383         kind = vec_kind;
384       else
385         kind = x_kind;
386       break;
387
388     default:
389       abort ();
390     }
391
392   tree_node_counts[(int) kind]++;
393   tree_node_sizes[(int) kind] += length;
394 #endif
395
396   t = ggc_alloc_tree (length);
397
398   memset ((PTR) t, 0, length);
399
400   TREE_SET_CODE (t, code);
401
402   switch (type)
403     {
404     case 's':
405       TREE_SIDE_EFFECTS (t) = 1;
406       TREE_TYPE (t) = void_type_node;
407       break;
408
409     case 'd':
410       if (code != FUNCTION_DECL)
411         DECL_ALIGN (t) = 1;
412       DECL_USER_ALIGN (t) = 0;
413       DECL_IN_SYSTEM_HEADER (t) = in_system_header;
414       DECL_SOURCE_LINE (t) = lineno;
415       DECL_SOURCE_FILE (t) =
416         (input_filename) ? input_filename : "<built-in>";
417       DECL_UID (t) = next_decl_uid++;
418
419       /* We have not yet computed the alias set for this declaration.  */
420       DECL_POINTER_ALIAS_SET (t) = -1;
421       break;
422
423     case 't':
424       TYPE_UID (t) = next_type_uid++;
425       TYPE_ALIGN (t) = char_type_node ? TYPE_ALIGN (char_type_node) : 0;
426       TYPE_USER_ALIGN (t) = 0;
427       TYPE_MAIN_VARIANT (t) = t;
428
429       /* Default to no attributes for type, but let target change that.  */
430       TYPE_ATTRIBUTES (t) = NULL_TREE;
431       (*targetm.set_default_type_attributes) (t);
432
433       /* We have not yet computed the alias set for this type.  */
434       TYPE_ALIAS_SET (t) = -1;
435       break;
436
437     case 'c':
438       TREE_CONSTANT (t) = 1;
439       break;
440
441     case 'e':
442       switch (code)
443         {
444         case INIT_EXPR:
445         case MODIFY_EXPR:
446         case VA_ARG_EXPR:
447         case RTL_EXPR:
448         case PREDECREMENT_EXPR:
449         case PREINCREMENT_EXPR:
450         case POSTDECREMENT_EXPR:
451         case POSTINCREMENT_EXPR:
452           /* All of these have side-effects, no matter what their
453              operands are.  */
454           TREE_SIDE_EFFECTS (t) = 1;
455           break;
456
457         default:
458           break;
459         }
460       break;
461     }
462
463   return t;
464 }
465
466 /* A front-end can reset this to an appropriate function if types need
467    special handling.  */
468
469 tree (*make_lang_type_fn) PARAMS ((enum tree_code)) = make_node;
470
471 /* Return a new type (with the indicated CODE), doing whatever
472    language-specific processing is required.  */
473
474 tree
475 make_lang_type (code)
476      enum tree_code code;
477 {
478   return (*make_lang_type_fn) (code);
479 }
480 \f
481 /* Return a new node with the same contents as NODE except that its
482    TREE_CHAIN is zero and it has a fresh uid.  */
483
484 tree
485 copy_node (node)
486      tree node;
487 {
488   tree t;
489   enum tree_code code = TREE_CODE (node);
490   size_t length;
491
492   length = tree_size (node);
493   t = ggc_alloc_tree (length);
494   memcpy (t, node, length);
495
496   TREE_CHAIN (t) = 0;
497   TREE_ASM_WRITTEN (t) = 0;
498
499   if (TREE_CODE_CLASS (code) == 'd')
500     DECL_UID (t) = next_decl_uid++;
501   else if (TREE_CODE_CLASS (code) == 't')
502     {
503       TYPE_UID (t) = next_type_uid++;
504       /* The following is so that the debug code for
505          the copy is different from the original type.
506          The two statements usually duplicate each other
507          (because they clear fields of the same union),
508          but the optimizer should catch that.  */
509       TYPE_SYMTAB_POINTER (t) = 0;
510       TYPE_SYMTAB_ADDRESS (t) = 0;
511     }
512
513   return t;
514 }
515
516 /* Return a copy of a chain of nodes, chained through the TREE_CHAIN field.
517    For example, this can copy a list made of TREE_LIST nodes.  */
518
519 tree
520 copy_list (list)
521      tree list;
522 {
523   tree head;
524   tree prev, next;
525
526   if (list == 0)
527     return 0;
528
529   head = prev = copy_node (list);
530   next = TREE_CHAIN (list);
531   while (next)
532     {
533       TREE_CHAIN (prev) = copy_node (next);
534       prev = TREE_CHAIN (prev);
535       next = TREE_CHAIN (next);
536     }
537   return head;
538 }
539
540 \f
541 /* Return a newly constructed INTEGER_CST node whose constant value
542    is specified by the two ints LOW and HI.
543    The TREE_TYPE is set to `int'.
544
545    This function should be used via the `build_int_2' macro.  */
546
547 tree
548 build_int_2_wide (low, hi)
549      unsigned HOST_WIDE_INT low;
550      HOST_WIDE_INT hi;
551 {
552   tree t = make_node (INTEGER_CST);
553
554   TREE_INT_CST_LOW (t) = low;
555   TREE_INT_CST_HIGH (t) = hi;
556   TREE_TYPE (t) = integer_type_node;
557   return t;
558 }
559
560 /* Return a new REAL_CST node whose type is TYPE and value is D.  */
561
562 tree
563 build_real (type, d)
564      tree type;
565      REAL_VALUE_TYPE d;
566 {
567   tree v;
568   int overflow = 0;
569
570   /* Check for valid float value for this type on this target machine;
571      if not, can print error message and store a valid value in D.  */
572 #ifdef CHECK_FLOAT_VALUE
573   CHECK_FLOAT_VALUE (TYPE_MODE (type), d, overflow);
574 #endif
575
576   v = make_node (REAL_CST);
577   TREE_TYPE (v) = type;
578   TREE_REAL_CST (v) = d;
579   TREE_OVERFLOW (v) = TREE_CONSTANT_OVERFLOW (v) = overflow;
580   return v;
581 }
582
583 /* Return a new REAL_CST node whose type is TYPE
584    and whose value is the integer value of the INTEGER_CST node I.  */
585
586 #if !defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
587
588 REAL_VALUE_TYPE
589 real_value_from_int_cst (type, i)
590      tree type ATTRIBUTE_UNUSED, i;
591 {
592   REAL_VALUE_TYPE d;
593
594 #ifdef REAL_ARITHMETIC
595   /* Clear all bits of the real value type so that we can later do
596      bitwise comparisons to see if two values are the same.  */
597   memset ((char *) &d, 0, sizeof d);
598
599   if (! TREE_UNSIGNED (TREE_TYPE (i)))
600     REAL_VALUE_FROM_INT (d, TREE_INT_CST_LOW (i), TREE_INT_CST_HIGH (i),
601                          TYPE_MODE (type));
602   else
603     REAL_VALUE_FROM_UNSIGNED_INT (d, TREE_INT_CST_LOW (i),
604                                   TREE_INT_CST_HIGH (i), TYPE_MODE (type));
605 #else /* not REAL_ARITHMETIC */
606   /* Some 386 compilers mishandle unsigned int to float conversions,
607      so introduce a temporary variable E to avoid those bugs.  */
608   if (TREE_INT_CST_HIGH (i) < 0 && ! TREE_UNSIGNED (TREE_TYPE (i)))
609     {
610       REAL_VALUE_TYPE e;
611
612       d = (double) (~TREE_INT_CST_HIGH (i));
613       e = ((double) ((HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT / 2))
614             * (double) ((HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT / 2)));
615       d *= e;
616       e = (double) (~TREE_INT_CST_LOW (i));
617       d += e;
618       d = (- d - 1.0);
619     }
620   else
621     {
622       REAL_VALUE_TYPE e;
623
624       d = (double) (unsigned HOST_WIDE_INT) TREE_INT_CST_HIGH (i);
625       e = ((double) ((HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT / 2))
626            * (double) ((HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT / 2)));
627       d *= e;
628       e = (double) TREE_INT_CST_LOW (i);
629       d += e;
630     }
631 #endif /* not REAL_ARITHMETIC */
632   return d;
633 }
634
635 /* Args to pass to and from build_real_from_int_cst_1.  */
636
637 struct brfic_args
638 {
639   tree type;                    /* Input: type to conver to.  */
640   tree i;                       /* Input: operand to convert.  */
641   REAL_VALUE_TYPE d;            /* Output: floating point value.  */
642 };
643
644 /* Convert an integer to a floating point value while protected by a floating
645    point exception handler.  */
646
647 static void
648 build_real_from_int_cst_1 (data)
649      PTR data;
650 {
651   struct brfic_args *args = (struct brfic_args *) data;
652
653 #ifdef REAL_ARITHMETIC
654   args->d = real_value_from_int_cst (args->type, args->i);
655 #else
656   args->d
657     = REAL_VALUE_TRUNCATE (TYPE_MODE (args->type),
658                            real_value_from_int_cst (args->type, args->i));
659 #endif
660 }
661
662 /* Given a tree representing an integer constant I, return a tree
663    representing the same value as a floating-point constant of type TYPE.
664    We cannot perform this operation if there is no way of doing arithmetic
665    on floating-point values.  */
666
667 tree
668 build_real_from_int_cst (type, i)
669      tree type;
670      tree i;
671 {
672   tree v;
673   int overflow = TREE_OVERFLOW (i);
674   REAL_VALUE_TYPE d;
675   struct brfic_args args;
676
677   v = make_node (REAL_CST);
678   TREE_TYPE (v) = type;
679
680   /* Setup input for build_real_from_int_cst_1() */
681   args.type = type;
682   args.i = i;
683
684   if (do_float_handler (build_real_from_int_cst_1, (PTR) &args))
685     /* Receive output from build_real_from_int_cst_1() */
686     d = args.d;
687   else
688     {
689       /* We got an exception from build_real_from_int_cst_1() */
690       d = dconst0;
691       overflow = 1;
692     }
693
694   /* Check for valid float value for this type on this target machine.  */
695
696 #ifdef CHECK_FLOAT_VALUE
697   CHECK_FLOAT_VALUE (TYPE_MODE (type), d, overflow);
698 #endif
699
700   TREE_REAL_CST (v) = d;
701   TREE_OVERFLOW (v) = TREE_CONSTANT_OVERFLOW (v) = overflow;
702   return v;
703 }
704
705 #endif /* not REAL_IS_NOT_DOUBLE, or REAL_ARITHMETIC */
706
707 /* Return a newly constructed STRING_CST node whose value is
708    the LEN characters at STR.
709    The TREE_TYPE is not initialized.  */
710
711 tree
712 build_string (len, str)
713      int len;
714      const char *str;
715 {
716   tree s = make_node (STRING_CST);
717
718   TREE_STRING_LENGTH (s) = len;
719   TREE_STRING_POINTER (s) = ggc_alloc_string (str, len);
720
721   return s;
722 }
723
724 /* Return a newly constructed COMPLEX_CST node whose value is
725    specified by the real and imaginary parts REAL and IMAG.
726    Both REAL and IMAG should be constant nodes.  TYPE, if specified,
727    will be the type of the COMPLEX_CST; otherwise a new type will be made.  */
728
729 tree
730 build_complex (type, real, imag)
731      tree type;
732      tree real, imag;
733 {
734   tree t = make_node (COMPLEX_CST);
735
736   TREE_REALPART (t) = real;
737   TREE_IMAGPART (t) = imag;
738   TREE_TYPE (t) = type ? type : build_complex_type (TREE_TYPE (real));
739   TREE_OVERFLOW (t) = TREE_OVERFLOW (real) | TREE_OVERFLOW (imag);
740   TREE_CONSTANT_OVERFLOW (t)
741     = TREE_CONSTANT_OVERFLOW (real) | TREE_CONSTANT_OVERFLOW (imag);
742   return t;
743 }
744
745 /* Build a newly constructed TREE_VEC node of length LEN.  */
746
747 tree
748 make_tree_vec (len)
749      int len;
750 {
751   tree t;
752   int length = (len-1) * sizeof (tree) + sizeof (struct tree_vec);
753
754 #ifdef GATHER_STATISTICS
755   tree_node_counts[(int)vec_kind]++;
756   tree_node_sizes[(int)vec_kind] += length;
757 #endif
758
759   t = ggc_alloc_tree (length);
760
761   memset ((PTR) t, 0, length);
762   TREE_SET_CODE (t, TREE_VEC);
763   TREE_VEC_LENGTH (t) = len;
764
765   return t;
766 }
767 \f
768 /* Return 1 if EXPR is the integer constant zero or a complex constant
769    of zero.  */
770
771 int
772 integer_zerop (expr)
773      tree expr;
774 {
775   STRIP_NOPS (expr);
776
777   return ((TREE_CODE (expr) == INTEGER_CST
778            && ! TREE_CONSTANT_OVERFLOW (expr)
779            && TREE_INT_CST_LOW (expr) == 0
780            && TREE_INT_CST_HIGH (expr) == 0)
781           || (TREE_CODE (expr) == COMPLEX_CST
782               && integer_zerop (TREE_REALPART (expr))
783               && integer_zerop (TREE_IMAGPART (expr))));
784 }
785
786 /* Return 1 if EXPR is the integer constant one or the corresponding
787    complex constant.  */
788
789 int
790 integer_onep (expr)
791      tree expr;
792 {
793   STRIP_NOPS (expr);
794
795   return ((TREE_CODE (expr) == INTEGER_CST
796            && ! TREE_CONSTANT_OVERFLOW (expr)
797            && TREE_INT_CST_LOW (expr) == 1
798            && TREE_INT_CST_HIGH (expr) == 0)
799           || (TREE_CODE (expr) == COMPLEX_CST
800               && integer_onep (TREE_REALPART (expr))
801               && integer_zerop (TREE_IMAGPART (expr))));
802 }
803
804 /* Return 1 if EXPR is an integer containing all 1's in as much precision as
805    it contains.  Likewise for the corresponding complex constant.  */
806
807 int
808 integer_all_onesp (expr)
809      tree expr;
810 {
811   int prec;
812   int uns;
813
814   STRIP_NOPS (expr);
815
816   if (TREE_CODE (expr) == COMPLEX_CST
817       && integer_all_onesp (TREE_REALPART (expr))
818       && integer_zerop (TREE_IMAGPART (expr)))
819     return 1;
820
821   else if (TREE_CODE (expr) != INTEGER_CST
822            || TREE_CONSTANT_OVERFLOW (expr))
823     return 0;
824
825   uns = TREE_UNSIGNED (TREE_TYPE (expr));
826   if (!uns)
827     return (TREE_INT_CST_LOW (expr) == ~(unsigned HOST_WIDE_INT) 0
828             && TREE_INT_CST_HIGH (expr) == -1);
829
830   /* Note that using TYPE_PRECISION here is wrong.  We care about the
831      actual bits, not the (arbitrary) range of the type.  */
832   prec = GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (expr)));
833   if (prec >= HOST_BITS_PER_WIDE_INT)
834     {
835       HOST_WIDE_INT high_value;
836       int shift_amount;
837
838       shift_amount = prec - HOST_BITS_PER_WIDE_INT;
839
840       if (shift_amount > HOST_BITS_PER_WIDE_INT)
841         /* Can not handle precisions greater than twice the host int size.  */
842         abort ();
843       else if (shift_amount == HOST_BITS_PER_WIDE_INT)
844         /* Shifting by the host word size is undefined according to the ANSI
845            standard, so we must handle this as a special case.  */
846         high_value = -1;
847       else
848         high_value = ((HOST_WIDE_INT) 1 << shift_amount) - 1;
849
850       return (TREE_INT_CST_LOW (expr) == ~(unsigned HOST_WIDE_INT) 0
851               && TREE_INT_CST_HIGH (expr) == high_value);
852     }
853   else
854     return TREE_INT_CST_LOW (expr) == ((unsigned HOST_WIDE_INT) 1 << prec) - 1;
855 }
856
857 /* Return 1 if EXPR is an integer constant that is a power of 2 (i.e., has only
858    one bit on).  */
859
860 int
861 integer_pow2p (expr)
862      tree expr;
863 {
864   int prec;
865   HOST_WIDE_INT high, low;
866
867   STRIP_NOPS (expr);
868
869   if (TREE_CODE (expr) == COMPLEX_CST
870       && integer_pow2p (TREE_REALPART (expr))
871       && integer_zerop (TREE_IMAGPART (expr)))
872     return 1;
873
874   if (TREE_CODE (expr) != INTEGER_CST || TREE_CONSTANT_OVERFLOW (expr))
875     return 0;
876
877   prec = (POINTER_TYPE_P (TREE_TYPE (expr))
878           ? POINTER_SIZE : TYPE_PRECISION (TREE_TYPE (expr)));
879   high = TREE_INT_CST_HIGH (expr);
880   low = TREE_INT_CST_LOW (expr);
881
882   /* First clear all bits that are beyond the type's precision in case
883      we've been sign extended.  */
884
885   if (prec == 2 * HOST_BITS_PER_WIDE_INT)
886     ;
887   else if (prec > HOST_BITS_PER_WIDE_INT)
888     high &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
889   else
890     {
891       high = 0;
892       if (prec < HOST_BITS_PER_WIDE_INT)
893         low &= ~((HOST_WIDE_INT) (-1) << prec);
894     }
895
896   if (high == 0 && low == 0)
897     return 0;
898
899   return ((high == 0 && (low & (low - 1)) == 0)
900           || (low == 0 && (high & (high - 1)) == 0));
901 }
902
903 /* Return the power of two represented by a tree node known to be a
904    power of two.  */
905
906 int
907 tree_log2 (expr)
908      tree expr;
909 {
910   int prec;
911   HOST_WIDE_INT high, low;
912
913   STRIP_NOPS (expr);
914
915   if (TREE_CODE (expr) == COMPLEX_CST)
916     return tree_log2 (TREE_REALPART (expr));
917
918   prec = (POINTER_TYPE_P (TREE_TYPE (expr))
919           ? POINTER_SIZE : TYPE_PRECISION (TREE_TYPE (expr)));
920
921   high = TREE_INT_CST_HIGH (expr);
922   low = TREE_INT_CST_LOW (expr);
923
924   /* First clear all bits that are beyond the type's precision in case
925      we've been sign extended.  */
926
927   if (prec == 2 * HOST_BITS_PER_WIDE_INT)
928     ;
929   else if (prec > HOST_BITS_PER_WIDE_INT)
930     high &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
931   else
932     {
933       high = 0;
934       if (prec < HOST_BITS_PER_WIDE_INT)
935         low &= ~((HOST_WIDE_INT) (-1) << prec);
936     }
937
938   return (high != 0 ? HOST_BITS_PER_WIDE_INT + exact_log2 (high)
939           : exact_log2 (low));
940 }
941
942 /* Similar, but return the largest integer Y such that 2 ** Y is less
943    than or equal to EXPR.  */
944
945 int
946 tree_floor_log2 (expr)
947      tree expr;
948 {
949   int prec;
950   HOST_WIDE_INT high, low;
951
952   STRIP_NOPS (expr);
953
954   if (TREE_CODE (expr) == COMPLEX_CST)
955     return tree_log2 (TREE_REALPART (expr));
956
957   prec = (POINTER_TYPE_P (TREE_TYPE (expr))
958           ? POINTER_SIZE : TYPE_PRECISION (TREE_TYPE (expr)));
959
960   high = TREE_INT_CST_HIGH (expr);
961   low = TREE_INT_CST_LOW (expr);
962
963   /* First clear all bits that are beyond the type's precision in case
964      we've been sign extended.  Ignore if type's precision hasn't been set
965      since what we are doing is setting it.  */
966
967   if (prec == 2 * HOST_BITS_PER_WIDE_INT || prec == 0)
968     ;
969   else if (prec > HOST_BITS_PER_WIDE_INT)
970     high &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
971   else
972     {
973       high = 0;
974       if (prec < HOST_BITS_PER_WIDE_INT)
975         low &= ~((HOST_WIDE_INT) (-1) << prec);
976     }
977
978   return (high != 0 ? HOST_BITS_PER_WIDE_INT + floor_log2 (high)
979           : floor_log2 (low));
980 }
981
982 /* Return 1 if EXPR is the real constant zero.  */
983
984 int
985 real_zerop (expr)
986      tree expr;
987 {
988   STRIP_NOPS (expr);
989
990   return ((TREE_CODE (expr) == REAL_CST
991            && ! TREE_CONSTANT_OVERFLOW (expr)
992            && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconst0))
993           || (TREE_CODE (expr) == COMPLEX_CST
994               && real_zerop (TREE_REALPART (expr))
995               && real_zerop (TREE_IMAGPART (expr))));
996 }
997
998 /* Return 1 if EXPR is the real constant one in real or complex form.  */
999
1000 int
1001 real_onep (expr)
1002      tree expr;
1003 {
1004   STRIP_NOPS (expr);
1005
1006   return ((TREE_CODE (expr) == REAL_CST
1007            && ! TREE_CONSTANT_OVERFLOW (expr)
1008            && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconst1))
1009           || (TREE_CODE (expr) == COMPLEX_CST
1010               && real_onep (TREE_REALPART (expr))
1011               && real_zerop (TREE_IMAGPART (expr))));
1012 }
1013
1014 /* Return 1 if EXPR is the real constant two.  */
1015
1016 int
1017 real_twop (expr)
1018      tree expr;
1019 {
1020   STRIP_NOPS (expr);
1021
1022   return ((TREE_CODE (expr) == REAL_CST
1023            && ! TREE_CONSTANT_OVERFLOW (expr)
1024            && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconst2))
1025           || (TREE_CODE (expr) == COMPLEX_CST
1026               && real_twop (TREE_REALPART (expr))
1027               && real_zerop (TREE_IMAGPART (expr))));
1028 }
1029
1030 /* Nonzero if EXP is a constant or a cast of a constant.  */
1031
1032 int
1033 really_constant_p (exp)
1034      tree exp;
1035 {
1036   /* This is not quite the same as STRIP_NOPS.  It does more.  */
1037   while (TREE_CODE (exp) == NOP_EXPR
1038          || TREE_CODE (exp) == CONVERT_EXPR
1039          || TREE_CODE (exp) == NON_LVALUE_EXPR)
1040     exp = TREE_OPERAND (exp, 0);
1041   return TREE_CONSTANT (exp);
1042 }
1043 \f
1044 /* Return first list element whose TREE_VALUE is ELEM.
1045    Return 0 if ELEM is not in LIST.  */
1046
1047 tree
1048 value_member (elem, list)
1049      tree elem, list;
1050 {
1051   while (list)
1052     {
1053       if (elem == TREE_VALUE (list))
1054         return list;
1055       list = TREE_CHAIN (list);
1056     }
1057   return NULL_TREE;
1058 }
1059
1060 /* Return first list element whose TREE_PURPOSE is ELEM.
1061    Return 0 if ELEM is not in LIST.  */
1062
1063 tree
1064 purpose_member (elem, list)
1065      tree elem, list;
1066 {
1067   while (list)
1068     {
1069       if (elem == TREE_PURPOSE (list))
1070         return list;
1071       list = TREE_CHAIN (list);
1072     }
1073   return NULL_TREE;
1074 }
1075
1076 /* Return first list element whose BINFO_TYPE is ELEM.
1077    Return 0 if ELEM is not in LIST.  */
1078
1079 tree
1080 binfo_member (elem, list)
1081      tree elem, list;
1082 {
1083   while (list)
1084     {
1085       if (elem == BINFO_TYPE (list))
1086         return list;
1087       list = TREE_CHAIN (list);
1088     }
1089   return NULL_TREE;
1090 }
1091
1092 /* Return nonzero if ELEM is part of the chain CHAIN.  */
1093
1094 int
1095 chain_member (elem, chain)
1096      tree elem, chain;
1097 {
1098   while (chain)
1099     {
1100       if (elem == chain)
1101         return 1;
1102       chain = TREE_CHAIN (chain);
1103     }
1104
1105   return 0;
1106 }
1107
1108 /* Return nonzero if ELEM is equal to TREE_VALUE (CHAIN) for any piece of
1109    chain CHAIN.  This and the next function are currently unused, but
1110    are retained for completeness.  */
1111
1112 int
1113 chain_member_value (elem, chain)
1114      tree elem, chain;
1115 {
1116   while (chain)
1117     {
1118       if (elem == TREE_VALUE (chain))
1119         return 1;
1120       chain = TREE_CHAIN (chain);
1121     }
1122
1123   return 0;
1124 }
1125
1126 /* Return nonzero if ELEM is equal to TREE_PURPOSE (CHAIN)
1127    for any piece of chain CHAIN.  */
1128
1129 int
1130 chain_member_purpose (elem, chain)
1131      tree elem, chain;
1132 {
1133   while (chain)
1134     {
1135       if (elem == TREE_PURPOSE (chain))
1136         return 1;
1137       chain = TREE_CHAIN (chain);
1138     }
1139
1140   return 0;
1141 }
1142
1143 /* Return the length of a chain of nodes chained through TREE_CHAIN.
1144    We expect a null pointer to mark the end of the chain.
1145    This is the Lisp primitive `length'.  */
1146
1147 int
1148 list_length (t)
1149      tree t;
1150 {
1151   tree tail;
1152   int len = 0;
1153
1154   for (tail = t; tail; tail = TREE_CHAIN (tail))
1155     len++;
1156
1157   return len;
1158 }
1159
1160 /* Returns the number of FIELD_DECLs in TYPE.  */
1161
1162 int
1163 fields_length (type)
1164      tree type;
1165 {
1166   tree t = TYPE_FIELDS (type);
1167   int count = 0;
1168
1169   for (; t; t = TREE_CHAIN (t))
1170     if (TREE_CODE (t) == FIELD_DECL)
1171       ++count;
1172
1173   return count;
1174 }
1175
1176 /* Concatenate two chains of nodes (chained through TREE_CHAIN)
1177    by modifying the last node in chain 1 to point to chain 2.
1178    This is the Lisp primitive `nconc'.  */
1179
1180 tree
1181 chainon (op1, op2)
1182      tree op1, op2;
1183 {
1184
1185   if (op1)
1186     {
1187       tree t1;
1188 #ifdef ENABLE_TREE_CHECKING
1189       tree t2;
1190 #endif
1191
1192       for (t1 = op1; TREE_CHAIN (t1); t1 = TREE_CHAIN (t1))
1193         ;
1194       TREE_CHAIN (t1) = op2;
1195 #ifdef ENABLE_TREE_CHECKING
1196       for (t2 = op2; t2; t2 = TREE_CHAIN (t2))
1197         if (t2 == t1)
1198           abort ();  /* Circularity created.  */
1199 #endif
1200       return op1;
1201     }
1202   else
1203     return op2;
1204 }
1205
1206 /* Return the last node in a chain of nodes (chained through TREE_CHAIN).  */
1207
1208 tree
1209 tree_last (chain)
1210      tree chain;
1211 {
1212   tree next;
1213   if (chain)
1214     while ((next = TREE_CHAIN (chain)))
1215       chain = next;
1216   return chain;
1217 }
1218
1219 /* Reverse the order of elements in the chain T,
1220    and return the new head of the chain (old last element).  */
1221
1222 tree
1223 nreverse (t)
1224      tree t;
1225 {
1226   tree prev = 0, decl, next;
1227   for (decl = t; decl; decl = next)
1228     {
1229       next = TREE_CHAIN (decl);
1230       TREE_CHAIN (decl) = prev;
1231       prev = decl;
1232     }
1233   return prev;
1234 }
1235
1236 /* Given a chain CHAIN of tree nodes,
1237    construct and return a list of those nodes.  */
1238
1239 tree
1240 listify (chain)
1241      tree chain;
1242 {
1243   tree result = NULL_TREE;
1244   tree in_tail = chain;
1245   tree out_tail = NULL_TREE;
1246
1247   while (in_tail)
1248     {
1249       tree next = tree_cons (NULL_TREE, in_tail, NULL_TREE);
1250       if (out_tail)
1251         TREE_CHAIN (out_tail) = next;
1252       else
1253         result = next;
1254       out_tail = next;
1255       in_tail = TREE_CHAIN (in_tail);
1256     }
1257
1258   return result;
1259 }
1260 \f
1261 /* Return a newly created TREE_LIST node whose
1262    purpose and value fields are PARM and VALUE.  */
1263
1264 tree
1265 build_tree_list (parm, value)
1266      tree parm, value;
1267 {
1268   tree t = make_node (TREE_LIST);
1269   TREE_PURPOSE (t) = parm;
1270   TREE_VALUE (t) = value;
1271   return t;
1272 }
1273
1274 /* Return a newly created TREE_LIST node whose
1275    purpose and value fields are PARM and VALUE
1276    and whose TREE_CHAIN is CHAIN.  */
1277
1278 tree
1279 tree_cons (purpose, value, chain)
1280      tree purpose, value, chain;
1281 {
1282   tree node;
1283
1284   node = ggc_alloc_tree (sizeof (struct tree_list));
1285
1286   memset (node, 0, sizeof (struct tree_common));
1287
1288 #ifdef GATHER_STATISTICS
1289   tree_node_counts[(int) x_kind]++;
1290   tree_node_sizes[(int) x_kind] += sizeof (struct tree_list);
1291 #endif
1292
1293   TREE_SET_CODE (node, TREE_LIST);
1294   TREE_CHAIN (node) = chain;
1295   TREE_PURPOSE (node) = purpose;
1296   TREE_VALUE (node) = value;
1297   return node;
1298 }
1299
1300 \f
1301 /* Return the size nominally occupied by an object of type TYPE
1302    when it resides in memory.  The value is measured in units of bytes,
1303    and its data type is that normally used for type sizes
1304    (which is the first type created by make_signed_type or
1305    make_unsigned_type).  */
1306
1307 tree
1308 size_in_bytes (type)
1309      tree type;
1310 {
1311   tree t;
1312
1313   if (type == error_mark_node)
1314     return integer_zero_node;
1315
1316   type = TYPE_MAIN_VARIANT (type);
1317   t = TYPE_SIZE_UNIT (type);
1318
1319   if (t == 0)
1320     {
1321       incomplete_type_error (NULL_TREE, type);
1322       return size_zero_node;
1323     }
1324
1325   if (TREE_CODE (t) == INTEGER_CST)
1326     force_fit_type (t, 0);
1327
1328   return t;
1329 }
1330
1331 /* Return the size of TYPE (in bytes) as a wide integer
1332    or return -1 if the size can vary or is larger than an integer.  */
1333
1334 HOST_WIDE_INT
1335 int_size_in_bytes (type)
1336      tree type;
1337 {
1338   tree t;
1339
1340   if (type == error_mark_node)
1341     return 0;
1342
1343   type = TYPE_MAIN_VARIANT (type);
1344   t = TYPE_SIZE_UNIT (type);
1345   if (t == 0
1346       || TREE_CODE (t) != INTEGER_CST
1347       || TREE_OVERFLOW (t)
1348       || TREE_INT_CST_HIGH (t) != 0
1349       /* If the result would appear negative, it's too big to represent.  */
1350       || (HOST_WIDE_INT) TREE_INT_CST_LOW (t) < 0)
1351     return -1;
1352
1353   return TREE_INT_CST_LOW (t);
1354 }
1355 \f
1356 /* Return the bit position of FIELD, in bits from the start of the record.
1357    This is a tree of type bitsizetype.  */
1358
1359 tree
1360 bit_position (field)
1361      tree field;
1362 {
1363
1364   return bit_from_pos (DECL_FIELD_OFFSET (field),
1365                        DECL_FIELD_BIT_OFFSET (field));
1366 }
1367
1368 /* Likewise, but return as an integer.  Abort if it cannot be represented
1369    in that way (since it could be a signed value, we don't have the option
1370    of returning -1 like int_size_in_byte can.  */
1371
1372 HOST_WIDE_INT
1373 int_bit_position (field)
1374      tree field;
1375 {
1376   return tree_low_cst (bit_position (field), 0);
1377 }
1378 \f
1379 /* Return the byte position of FIELD, in bytes from the start of the record.
1380    This is a tree of type sizetype.  */
1381
1382 tree
1383 byte_position (field)
1384      tree field;
1385 {
1386   return byte_from_pos (DECL_FIELD_OFFSET (field),
1387                         DECL_FIELD_BIT_OFFSET (field));
1388 }
1389
1390 /* Likewise, but return as an integer.  Abort if it cannot be represented
1391    in that way (since it could be a signed value, we don't have the option
1392    of returning -1 like int_size_in_byte can.  */
1393
1394 HOST_WIDE_INT
1395 int_byte_position (field)
1396      tree field;
1397 {
1398   return tree_low_cst (byte_position (field), 0);
1399 }
1400 \f
1401 /* Return the strictest alignment, in bits, that T is known to have.  */
1402
1403 unsigned int
1404 expr_align (t)
1405      tree t;
1406 {
1407   unsigned int align0, align1;
1408
1409   switch (TREE_CODE (t))
1410     {
1411     case NOP_EXPR:  case CONVERT_EXPR:  case NON_LVALUE_EXPR:
1412       /* If we have conversions, we know that the alignment of the
1413          object must meet each of the alignments of the types.  */
1414       align0 = expr_align (TREE_OPERAND (t, 0));
1415       align1 = TYPE_ALIGN (TREE_TYPE (t));
1416       return MAX (align0, align1);
1417
1418     case SAVE_EXPR:         case COMPOUND_EXPR:       case MODIFY_EXPR:
1419     case INIT_EXPR:         case TARGET_EXPR:         case WITH_CLEANUP_EXPR:
1420     case WITH_RECORD_EXPR:  case CLEANUP_POINT_EXPR:  case UNSAVE_EXPR:
1421       /* These don't change the alignment of an object.  */
1422       return expr_align (TREE_OPERAND (t, 0));
1423
1424     case COND_EXPR:
1425       /* The best we can do is say that the alignment is the least aligned
1426          of the two arms.  */
1427       align0 = expr_align (TREE_OPERAND (t, 1));
1428       align1 = expr_align (TREE_OPERAND (t, 2));
1429       return MIN (align0, align1);
1430
1431     case LABEL_DECL:     case CONST_DECL:
1432     case VAR_DECL:       case PARM_DECL:   case RESULT_DECL:
1433       if (DECL_ALIGN (t) != 0)
1434         return DECL_ALIGN (t);
1435       break;
1436
1437     case FUNCTION_DECL:
1438       return FUNCTION_BOUNDARY;
1439
1440     default:
1441       break;
1442     }
1443
1444   /* Otherwise take the alignment from that of the type.  */
1445   return TYPE_ALIGN (TREE_TYPE (t));
1446 }
1447 \f
1448 /* Return, as a tree node, the number of elements for TYPE (which is an
1449    ARRAY_TYPE) minus one. This counts only elements of the top array.  */
1450
1451 tree
1452 array_type_nelts (type)
1453      tree type;
1454 {
1455   tree index_type, min, max;
1456
1457   /* If they did it with unspecified bounds, then we should have already
1458      given an error about it before we got here.  */
1459   if (! TYPE_DOMAIN (type))
1460     return error_mark_node;
1461
1462   index_type = TYPE_DOMAIN (type);
1463   min = TYPE_MIN_VALUE (index_type);
1464   max = TYPE_MAX_VALUE (index_type);
1465
1466   return (integer_zerop (min)
1467           ? max
1468           : fold (build (MINUS_EXPR, TREE_TYPE (max), max, min)));
1469 }
1470 \f
1471 /* Return nonzero if arg is static -- a reference to an object in
1472    static storage.  This is not the same as the C meaning of `static'.  */
1473
1474 int
1475 staticp (arg)
1476      tree arg;
1477 {
1478   switch (TREE_CODE (arg))
1479     {
1480     case FUNCTION_DECL:
1481       /* Nested functions aren't static, since taking their address
1482          involves a trampoline.  */
1483       return (decl_function_context (arg) == 0 || DECL_NO_STATIC_CHAIN (arg))
1484         && ! DECL_NON_ADDR_CONST_P (arg);
1485
1486     case VAR_DECL:
1487       return (TREE_STATIC (arg) || DECL_EXTERNAL (arg))
1488         && ! DECL_NON_ADDR_CONST_P (arg);
1489
1490     case CONSTRUCTOR:
1491       return TREE_STATIC (arg);
1492
1493     case LABEL_DECL:
1494     case STRING_CST:
1495       return 1;
1496
1497       /* If we are referencing a bitfield, we can't evaluate an
1498          ADDR_EXPR at compile time and so it isn't a constant.  */
1499     case COMPONENT_REF:
1500       return (! DECL_BIT_FIELD (TREE_OPERAND (arg, 1))
1501               && staticp (TREE_OPERAND (arg, 0)));
1502
1503     case BIT_FIELD_REF:
1504       return 0;
1505
1506 #if 0
1507        /* This case is technically correct, but results in setting
1508           TREE_CONSTANT on ADDR_EXPRs that cannot be evaluated at
1509           compile time.  */
1510     case INDIRECT_REF:
1511       return TREE_CONSTANT (TREE_OPERAND (arg, 0));
1512 #endif
1513
1514     case ARRAY_REF:
1515     case ARRAY_RANGE_REF:
1516       if (TREE_CODE (TYPE_SIZE (TREE_TYPE (arg))) == INTEGER_CST
1517           && TREE_CODE (TREE_OPERAND (arg, 1)) == INTEGER_CST)
1518         return staticp (TREE_OPERAND (arg, 0));
1519
1520     default:
1521       if ((unsigned int) TREE_CODE (arg)
1522           >= (unsigned int) LAST_AND_UNUSED_TREE_CODE)
1523         return (*lang_hooks.staticp) (arg);
1524       else
1525         return 0;
1526     }
1527 }
1528 \f
1529 /* Wrap a SAVE_EXPR around EXPR, if appropriate.
1530    Do this to any expression which may be used in more than one place,
1531    but must be evaluated only once.
1532
1533    Normally, expand_expr would reevaluate the expression each time.
1534    Calling save_expr produces something that is evaluated and recorded
1535    the first time expand_expr is called on it.  Subsequent calls to
1536    expand_expr just reuse the recorded value.
1537
1538    The call to expand_expr that generates code that actually computes
1539    the value is the first call *at compile time*.  Subsequent calls
1540    *at compile time* generate code to use the saved value.
1541    This produces correct result provided that *at run time* control
1542    always flows through the insns made by the first expand_expr
1543    before reaching the other places where the save_expr was evaluated.
1544    You, the caller of save_expr, must make sure this is so.
1545
1546    Constants, and certain read-only nodes, are returned with no
1547    SAVE_EXPR because that is safe.  Expressions containing placeholders
1548    are not touched; see tree.def for an explanation of what these
1549    are used for.  */
1550
1551 tree
1552 save_expr (expr)
1553      tree expr;
1554 {
1555   tree t = fold (expr);
1556   tree inner;
1557
1558   /* We don't care about whether this can be used as an lvalue in this
1559      context.  */
1560   while (TREE_CODE (t) == NON_LVALUE_EXPR)
1561     t = TREE_OPERAND (t, 0);
1562
1563   /* If we have simple operations applied to a SAVE_EXPR or to a SAVE_EXPR and
1564      a constant, it will be more efficient to not make another SAVE_EXPR since
1565      it will allow better simplification and GCSE will be able to merge the
1566      computations if they actualy occur.  */
1567   for (inner = t;
1568        (TREE_CODE_CLASS (TREE_CODE (inner)) == '1'
1569         || (TREE_CODE_CLASS (TREE_CODE (inner)) == '2'
1570             && TREE_CONSTANT (TREE_OPERAND (inner, 1))));
1571        inner = TREE_OPERAND (inner, 0))
1572     ;
1573
1574   /* If the tree evaluates to a constant, then we don't want to hide that
1575      fact (i.e. this allows further folding, and direct checks for constants).
1576      However, a read-only object that has side effects cannot be bypassed.
1577      Since it is no problem to reevaluate literals, we just return the
1578      literal node.  */
1579   if (TREE_CONSTANT (inner)
1580       || (TREE_READONLY (inner) && ! TREE_SIDE_EFFECTS (inner))
1581       || TREE_CODE (inner) == SAVE_EXPR || TREE_CODE (inner) == ERROR_MARK)
1582     return t;
1583
1584   /* If T contains a PLACEHOLDER_EXPR, we must evaluate it each time, since
1585      it means that the size or offset of some field of an object depends on
1586      the value within another field.
1587
1588      Note that it must not be the case that T contains both a PLACEHOLDER_EXPR
1589      and some variable since it would then need to be both evaluated once and
1590      evaluated more than once.  Front-ends must assure this case cannot
1591      happen by surrounding any such subexpressions in their own SAVE_EXPR
1592      and forcing evaluation at the proper time.  */
1593   if (contains_placeholder_p (t))
1594     return t;
1595
1596   t = build (SAVE_EXPR, TREE_TYPE (expr), t, current_function_decl, NULL_TREE);
1597
1598   /* This expression might be placed ahead of a jump to ensure that the
1599      value was computed on both sides of the jump.  So make sure it isn't
1600      eliminated as dead.  */
1601   TREE_SIDE_EFFECTS (t) = 1;
1602   TREE_READONLY (t) = 1;
1603   return t;
1604 }
1605
1606 /* Arrange for an expression to be expanded multiple independent
1607    times.  This is useful for cleanup actions, as the backend can
1608    expand them multiple times in different places.  */
1609
1610 tree
1611 unsave_expr (expr)
1612      tree expr;
1613 {
1614   tree t;
1615
1616   /* If this is already protected, no sense in protecting it again.  */
1617   if (TREE_CODE (expr) == UNSAVE_EXPR)
1618     return expr;
1619
1620   t = build1 (UNSAVE_EXPR, TREE_TYPE (expr), expr);
1621   TREE_SIDE_EFFECTS (t) = TREE_SIDE_EFFECTS (expr);
1622   return t;
1623 }
1624
1625 /* Returns the index of the first non-tree operand for CODE, or the number
1626    of operands if all are trees.  */
1627
1628 int
1629 first_rtl_op (code)
1630      enum tree_code code;
1631 {
1632   switch (code)
1633     {
1634     case SAVE_EXPR:
1635       return 2;
1636     case GOTO_SUBROUTINE_EXPR:
1637     case RTL_EXPR:
1638       return 0;
1639     case WITH_CLEANUP_EXPR:
1640       return 2;
1641     case METHOD_CALL_EXPR:
1642       return 3;
1643     default:
1644       return TREE_CODE_LENGTH (code);
1645     }
1646 }
1647
1648 /* Perform any modifications to EXPR required when it is unsaved.  Does
1649    not recurse into EXPR's subtrees.  */
1650
1651 void
1652 unsave_expr_1 (expr)
1653      tree expr;
1654 {
1655   switch (TREE_CODE (expr))
1656     {
1657     case SAVE_EXPR:
1658       if (! SAVE_EXPR_PERSISTENT_P (expr))
1659         SAVE_EXPR_RTL (expr) = 0;
1660       break;
1661
1662     case TARGET_EXPR:
1663       /* Don't mess with a TARGET_EXPR that hasn't been expanded.
1664          It's OK for this to happen if it was part of a subtree that
1665          isn't immediately expanded, such as operand 2 of another
1666          TARGET_EXPR.  */
1667       if (TREE_OPERAND (expr, 1))
1668         break;
1669
1670       TREE_OPERAND (expr, 1) = TREE_OPERAND (expr, 3);
1671       TREE_OPERAND (expr, 3) = NULL_TREE;
1672       break;
1673
1674     case RTL_EXPR:
1675       /* I don't yet know how to emit a sequence multiple times.  */
1676       if (RTL_EXPR_SEQUENCE (expr) != 0)
1677         abort ();
1678       break;
1679
1680     default:
1681       if (lang_unsave_expr_now != 0)
1682         (*lang_unsave_expr_now) (expr);
1683       break;
1684     }
1685 }
1686
1687 /* Helper function for unsave_expr_now.  */
1688
1689 static void
1690 unsave_expr_now_r (expr)
1691      tree expr;
1692 {
1693   enum tree_code code;
1694
1695   /* There's nothing to do for NULL_TREE.  */
1696   if (expr == 0)
1697     return;
1698
1699   unsave_expr_1 (expr);
1700
1701   code = TREE_CODE (expr);
1702   switch (TREE_CODE_CLASS (code))
1703     {
1704     case 'c':  /* a constant */
1705     case 't':  /* a type node */
1706     case 'd':  /* A decl node */
1707     case 'b':  /* A block node */
1708       break;
1709
1710     case 'x':  /* miscellaneous: e.g., identifier, TREE_LIST or ERROR_MARK.  */
1711       if (code == TREE_LIST)
1712         {
1713           unsave_expr_now_r (TREE_VALUE (expr));
1714           unsave_expr_now_r (TREE_CHAIN (expr));
1715         }
1716       break;
1717
1718     case 'e':  /* an expression */
1719     case 'r':  /* a reference */
1720     case 's':  /* an expression with side effects */
1721     case '<':  /* a comparison expression */
1722     case '2':  /* a binary arithmetic expression */
1723     case '1':  /* a unary arithmetic expression */
1724       {
1725         int i;
1726
1727         for (i = first_rtl_op (code) - 1; i >= 0; i--)
1728           unsave_expr_now_r (TREE_OPERAND (expr, i));
1729       }
1730       break;
1731
1732     default:
1733       abort ();
1734     }
1735 }
1736
1737 /* Modify a tree in place so that all the evaluate only once things
1738    are cleared out.  Return the EXPR given.  */
1739
1740 tree
1741 unsave_expr_now (expr)
1742      tree expr;
1743 {
1744   if (lang_unsave!= 0)
1745     (*lang_unsave) (&expr);
1746   else
1747     unsave_expr_now_r (expr);
1748
1749   return expr;
1750 }
1751
1752 /* Return 0 if it is safe to evaluate EXPR multiple times,
1753    return 1 if it is safe if EXPR is unsaved afterward, or
1754    return 2 if it is completely unsafe.
1755
1756    This assumes that CALL_EXPRs and TARGET_EXPRs are never replicated in
1757    an expression tree, so that it safe to unsave them and the surrounding
1758    context will be correct.
1759
1760    SAVE_EXPRs basically *only* appear replicated in an expression tree,
1761    occasionally across the whole of a function.  It is therefore only
1762    safe to unsave a SAVE_EXPR if you know that all occurrences appear
1763    below the UNSAVE_EXPR.
1764
1765    RTL_EXPRs consume their rtl during evaluation.  It is therefore
1766    never possible to unsave them.  */
1767
1768 int
1769 unsafe_for_reeval (expr)
1770      tree expr;
1771 {
1772   int unsafeness = 0;
1773   enum tree_code code;
1774   int i, tmp;
1775   tree exp;
1776   int first_rtl;
1777
1778   if (expr == NULL_TREE)
1779     return 1;
1780
1781   code = TREE_CODE (expr);
1782   first_rtl = first_rtl_op (code);
1783
1784   switch (code)
1785     {
1786     case SAVE_EXPR:
1787     case RTL_EXPR:
1788       return 2;
1789
1790     case TREE_LIST:
1791       for (exp = expr; exp != 0; exp = TREE_CHAIN (exp))
1792         {
1793           tmp = unsafe_for_reeval (TREE_VALUE (exp));
1794           unsafeness = MAX (tmp, unsafeness);
1795         }
1796
1797       return unsafeness;
1798
1799     case CALL_EXPR:
1800       tmp = unsafe_for_reeval (TREE_OPERAND (expr, 1));
1801       return MAX (tmp, 1);
1802
1803     case TARGET_EXPR:
1804       unsafeness = 1;
1805       break;
1806
1807     default:
1808       if (lang_unsafe_for_reeval != 0)
1809         {
1810           tmp = (*lang_unsafe_for_reeval) (expr);
1811           if (tmp >= 0)
1812             return tmp;
1813         }
1814       break;
1815     }
1816
1817   switch (TREE_CODE_CLASS (code))
1818     {
1819     case 'c':  /* a constant */
1820     case 't':  /* a type node */
1821     case 'x':  /* something random, like an identifier or an ERROR_MARK.  */
1822     case 'd':  /* A decl node */
1823     case 'b':  /* A block node */
1824       return 0;
1825
1826     case 'e':  /* an expression */
1827     case 'r':  /* a reference */
1828     case 's':  /* an expression with side effects */
1829     case '<':  /* a comparison expression */
1830     case '2':  /* a binary arithmetic expression */
1831     case '1':  /* a unary arithmetic expression */
1832       for (i = first_rtl - 1; i >= 0; i--)
1833         {
1834           tmp = unsafe_for_reeval (TREE_OPERAND (expr, i));
1835           unsafeness = MAX (tmp, unsafeness);
1836         }
1837
1838       return unsafeness;
1839
1840     default:
1841       return 2;
1842     }
1843 }
1844 \f
1845 /* Return 1 if EXP contains a PLACEHOLDER_EXPR; i.e., if it represents a size
1846    or offset that depends on a field within a record.  */
1847
1848 int
1849 contains_placeholder_p (exp)
1850      tree exp;
1851 {
1852   enum tree_code code;
1853   int result;
1854
1855   if (!exp)
1856     return 0;
1857
1858   /* If we have a WITH_RECORD_EXPR, it "cancels" any PLACEHOLDER_EXPR
1859      in it since it is supplying a value for it.  */
1860   code = TREE_CODE (exp);
1861   if (code == WITH_RECORD_EXPR)
1862     return 0;
1863   else if (code == PLACEHOLDER_EXPR)
1864     return 1;
1865
1866   switch (TREE_CODE_CLASS (code))
1867     {
1868     case 'r':
1869       /* Don't look at any PLACEHOLDER_EXPRs that might be in index or bit
1870          position computations since they will be converted into a
1871          WITH_RECORD_EXPR involving the reference, which will assume
1872          here will be valid.  */
1873       return contains_placeholder_p (TREE_OPERAND (exp, 0));
1874
1875     case 'x':
1876       if (code == TREE_LIST)
1877         return (contains_placeholder_p (TREE_VALUE (exp))
1878                 || (TREE_CHAIN (exp) != 0
1879                     && contains_placeholder_p (TREE_CHAIN (exp))));
1880       break;
1881
1882     case '1':
1883     case '2':  case '<':
1884     case 'e':
1885       switch (code)
1886         {
1887         case COMPOUND_EXPR:
1888           /* Ignoring the first operand isn't quite right, but works best.  */
1889           return contains_placeholder_p (TREE_OPERAND (exp, 1));
1890
1891         case RTL_EXPR:
1892         case CONSTRUCTOR:
1893           return 0;
1894
1895         case COND_EXPR:
1896           return (contains_placeholder_p (TREE_OPERAND (exp, 0))
1897                   || contains_placeholder_p (TREE_OPERAND (exp, 1))
1898                   || contains_placeholder_p (TREE_OPERAND (exp, 2)));
1899
1900         case SAVE_EXPR:
1901           /* If we already know this doesn't have a placeholder, don't
1902              check again.  */
1903           if (SAVE_EXPR_NOPLACEHOLDER (exp) || SAVE_EXPR_RTL (exp) != 0)
1904             return 0;
1905
1906           SAVE_EXPR_NOPLACEHOLDER (exp) = 1;
1907           result = contains_placeholder_p (TREE_OPERAND (exp, 0));
1908           if (result)
1909             SAVE_EXPR_NOPLACEHOLDER (exp) = 0;
1910
1911           return result;
1912
1913         case CALL_EXPR:
1914           return (TREE_OPERAND (exp, 1) != 0
1915                   && contains_placeholder_p (TREE_OPERAND (exp, 1)));
1916
1917         default:
1918           break;
1919         }
1920
1921       switch (TREE_CODE_LENGTH (code))
1922         {
1923         case 1:
1924           return contains_placeholder_p (TREE_OPERAND (exp, 0));
1925         case 2:
1926           return (contains_placeholder_p (TREE_OPERAND (exp, 0))
1927                   || contains_placeholder_p (TREE_OPERAND (exp, 1)));
1928         default:
1929           return 0;
1930         }
1931
1932     default:
1933       return 0;
1934     }
1935   return 0;
1936 }
1937
1938 /* Return 1 if EXP contains any expressions that produce cleanups for an
1939    outer scope to deal with.  Used by fold.  */
1940
1941 int
1942 has_cleanups (exp)
1943      tree exp;
1944 {
1945   int i, nops, cmp;
1946
1947   if (! TREE_SIDE_EFFECTS (exp))
1948     return 0;
1949
1950   switch (TREE_CODE (exp))
1951     {
1952     case TARGET_EXPR:
1953     case GOTO_SUBROUTINE_EXPR:
1954     case WITH_CLEANUP_EXPR:
1955       return 1;
1956
1957     case CLEANUP_POINT_EXPR:
1958       return 0;
1959
1960     case CALL_EXPR:
1961       for (exp = TREE_OPERAND (exp, 1); exp; exp = TREE_CHAIN (exp))
1962         {
1963           cmp = has_cleanups (TREE_VALUE (exp));
1964           if (cmp)
1965             return cmp;
1966         }
1967       return 0;
1968
1969     default:
1970       break;
1971     }
1972
1973   /* This general rule works for most tree codes.  All exceptions should be
1974      handled above.  If this is a language-specific tree code, we can't
1975      trust what might be in the operand, so say we don't know
1976      the situation.  */
1977   if ((int) TREE_CODE (exp) >= (int) LAST_AND_UNUSED_TREE_CODE)
1978     return -1;
1979
1980   nops = first_rtl_op (TREE_CODE (exp));
1981   for (i = 0; i < nops; i++)
1982     if (TREE_OPERAND (exp, i) != 0)
1983       {
1984         int type = TREE_CODE_CLASS (TREE_CODE (TREE_OPERAND (exp, i)));
1985         if (type == 'e' || type == '<' || type == '1' || type == '2'
1986             || type == 'r' || type == 's')
1987           {
1988             cmp = has_cleanups (TREE_OPERAND (exp, i));
1989             if (cmp)
1990               return cmp;
1991           }
1992       }
1993
1994   return 0;
1995 }
1996 \f
1997 /* Given a tree EXP, a FIELD_DECL F, and a replacement value R,
1998    return a tree with all occurrences of references to F in a
1999    PLACEHOLDER_EXPR replaced by R.   Note that we assume here that EXP
2000    contains only arithmetic expressions or a CALL_EXPR with a
2001    PLACEHOLDER_EXPR occurring only in its arglist.  */
2002
2003 tree
2004 substitute_in_expr (exp, f, r)
2005      tree exp;
2006      tree f;
2007      tree r;
2008 {
2009   enum tree_code code = TREE_CODE (exp);
2010   tree op0, op1, op2;
2011   tree new;
2012   tree inner;
2013
2014   switch (TREE_CODE_CLASS (code))
2015     {
2016     case 'c':
2017     case 'd':
2018       return exp;
2019
2020     case 'x':
2021       if (code == PLACEHOLDER_EXPR)
2022         return exp;
2023       else if (code == TREE_LIST)
2024         {
2025           op0 = (TREE_CHAIN (exp) == 0
2026                  ? 0 : substitute_in_expr (TREE_CHAIN (exp), f, r));
2027           op1 = substitute_in_expr (TREE_VALUE (exp), f, r);
2028           if (op0 == TREE_CHAIN (exp) && op1 == TREE_VALUE (exp))
2029             return exp;
2030
2031           return tree_cons (TREE_PURPOSE (exp), op1, op0);
2032         }
2033
2034       abort ();
2035
2036     case '1':
2037     case '2':
2038     case '<':
2039     case 'e':
2040       switch (TREE_CODE_LENGTH (code))
2041         {
2042         case 1:
2043           op0 = substitute_in_expr (TREE_OPERAND (exp, 0), f, r);
2044           if (op0 == TREE_OPERAND (exp, 0))
2045             return exp;
2046
2047           if (code == NON_LVALUE_EXPR)
2048             return op0;
2049
2050           new = fold (build1 (code, TREE_TYPE (exp), op0));
2051           break;
2052
2053         case 2:
2054           /* An RTL_EXPR cannot contain a PLACEHOLDER_EXPR; a CONSTRUCTOR
2055              could, but we don't support it.  */
2056           if (code == RTL_EXPR)
2057             return exp;
2058           else if (code == CONSTRUCTOR)
2059             abort ();
2060
2061           op0 = substitute_in_expr (TREE_OPERAND (exp, 0), f, r);
2062           op1 = substitute_in_expr (TREE_OPERAND (exp, 1), f, r);
2063           if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1))
2064             return exp;
2065
2066           new = fold (build (code, TREE_TYPE (exp), op0, op1));
2067           break;
2068
2069         case 3:
2070           /* It cannot be that anything inside a SAVE_EXPR contains a
2071              PLACEHOLDER_EXPR.  */
2072           if (code == SAVE_EXPR)
2073             return exp;
2074
2075           else if (code == CALL_EXPR)
2076             {
2077               op1 = substitute_in_expr (TREE_OPERAND (exp, 1), f, r);
2078               if (op1 == TREE_OPERAND (exp, 1))
2079                 return exp;
2080
2081               return build (code, TREE_TYPE (exp),
2082                             TREE_OPERAND (exp, 0), op1, NULL_TREE);
2083             }
2084
2085           else if (code != COND_EXPR)
2086             abort ();
2087
2088           op0 = substitute_in_expr (TREE_OPERAND (exp, 0), f, r);
2089           op1 = substitute_in_expr (TREE_OPERAND (exp, 1), f, r);
2090           op2 = substitute_in_expr (TREE_OPERAND (exp, 2), f, r);
2091           if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
2092               && op2 == TREE_OPERAND (exp, 2))
2093             return exp;
2094
2095           new = fold (build (code, TREE_TYPE (exp), op0, op1, op2));
2096           break;
2097
2098         default:
2099           abort ();
2100         }
2101
2102       break;
2103
2104     case 'r':
2105       switch (code)
2106         {
2107         case COMPONENT_REF:
2108           /* If this expression is getting a value from a PLACEHOLDER_EXPR
2109              and it is the right field, replace it with R.  */
2110           for (inner = TREE_OPERAND (exp, 0);
2111                TREE_CODE_CLASS (TREE_CODE (inner)) == 'r';
2112                inner = TREE_OPERAND (inner, 0))
2113             ;
2114           if (TREE_CODE (inner) == PLACEHOLDER_EXPR
2115               && TREE_OPERAND (exp, 1) == f)
2116             return r;
2117
2118           /* If this expression hasn't been completed let, leave it
2119              alone.  */
2120           if (TREE_CODE (inner) == PLACEHOLDER_EXPR
2121               && TREE_TYPE (inner) == 0)
2122             return exp;
2123
2124           op0 = substitute_in_expr (TREE_OPERAND (exp, 0), f, r);
2125           if (op0 == TREE_OPERAND (exp, 0))
2126             return exp;
2127
2128           new = fold (build (code, TREE_TYPE (exp), op0,
2129                              TREE_OPERAND (exp, 1)));
2130           break;
2131
2132         case BIT_FIELD_REF:
2133           op0 = substitute_in_expr (TREE_OPERAND (exp, 0), f, r);
2134           op1 = substitute_in_expr (TREE_OPERAND (exp, 1), f, r);
2135           op2 = substitute_in_expr (TREE_OPERAND (exp, 2), f, r);
2136           if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
2137               && op2 == TREE_OPERAND (exp, 2))
2138             return exp;
2139
2140           new = fold (build (code, TREE_TYPE (exp), op0, op1, op2));
2141           break;
2142
2143         case INDIRECT_REF:
2144         case BUFFER_REF:
2145           op0 = substitute_in_expr (TREE_OPERAND (exp, 0), f, r);
2146           if (op0 == TREE_OPERAND (exp, 0))
2147             return exp;
2148
2149           new = fold (build1 (code, TREE_TYPE (exp), op0));
2150           break;
2151
2152         default:
2153           abort ();
2154         }
2155       break;
2156
2157     default:
2158       abort ();
2159     }
2160
2161   TREE_READONLY (new) = TREE_READONLY (exp);
2162   return new;
2163 }
2164 \f
2165 /* Stabilize a reference so that we can use it any number of times
2166    without causing its operands to be evaluated more than once.
2167    Returns the stabilized reference.  This works by means of save_expr,
2168    so see the caveats in the comments about save_expr.
2169
2170    Also allows conversion expressions whose operands are references.
2171    Any other kind of expression is returned unchanged.  */
2172
2173 tree
2174 stabilize_reference (ref)
2175      tree ref;
2176 {
2177   tree result;
2178   enum tree_code code = TREE_CODE (ref);
2179
2180   switch (code)
2181     {
2182     case VAR_DECL:
2183     case PARM_DECL:
2184     case RESULT_DECL:
2185       /* No action is needed in this case.  */
2186       return ref;
2187
2188     case NOP_EXPR:
2189     case CONVERT_EXPR:
2190     case FLOAT_EXPR:
2191     case FIX_TRUNC_EXPR:
2192     case FIX_FLOOR_EXPR:
2193     case FIX_ROUND_EXPR:
2194     case FIX_CEIL_EXPR:
2195       result = build_nt (code, stabilize_reference (TREE_OPERAND (ref, 0)));
2196       break;
2197
2198     case INDIRECT_REF:
2199       result = build_nt (INDIRECT_REF,
2200                          stabilize_reference_1 (TREE_OPERAND (ref, 0)));
2201       break;
2202
2203     case COMPONENT_REF:
2204       result = build_nt (COMPONENT_REF,
2205                          stabilize_reference (TREE_OPERAND (ref, 0)),
2206                          TREE_OPERAND (ref, 1));
2207       break;
2208
2209     case BIT_FIELD_REF:
2210       result = build_nt (BIT_FIELD_REF,
2211                          stabilize_reference (TREE_OPERAND (ref, 0)),
2212                          stabilize_reference_1 (TREE_OPERAND (ref, 1)),
2213                          stabilize_reference_1 (TREE_OPERAND (ref, 2)));
2214       break;
2215
2216     case ARRAY_REF:
2217       result = build_nt (ARRAY_REF,
2218                          stabilize_reference (TREE_OPERAND (ref, 0)),
2219                          stabilize_reference_1 (TREE_OPERAND (ref, 1)));
2220       break;
2221
2222     case ARRAY_RANGE_REF:
2223       result = build_nt (ARRAY_RANGE_REF,
2224                          stabilize_reference (TREE_OPERAND (ref, 0)),
2225                          stabilize_reference_1 (TREE_OPERAND (ref, 1)));
2226       break;
2227
2228     case COMPOUND_EXPR:
2229       /* We cannot wrap the first expression in a SAVE_EXPR, as then
2230          it wouldn't be ignored.  This matters when dealing with
2231          volatiles.  */
2232       return stabilize_reference_1 (ref);
2233
2234     case RTL_EXPR:
2235       result = build1 (INDIRECT_REF, TREE_TYPE (ref),
2236                        save_expr (build1 (ADDR_EXPR,
2237                                           build_pointer_type (TREE_TYPE (ref)),
2238                                           ref)));
2239       break;
2240
2241       /* If arg isn't a kind of lvalue we recognize, make no change.
2242          Caller should recognize the error for an invalid lvalue.  */
2243     default:
2244       return ref;
2245
2246     case ERROR_MARK:
2247       return error_mark_node;
2248     }
2249
2250   TREE_TYPE (result) = TREE_TYPE (ref);
2251   TREE_READONLY (result) = TREE_READONLY (ref);
2252   TREE_SIDE_EFFECTS (result) = TREE_SIDE_EFFECTS (ref);
2253   TREE_THIS_VOLATILE (result) = TREE_THIS_VOLATILE (ref);
2254
2255   return result;
2256 }
2257
2258 /* Subroutine of stabilize_reference; this is called for subtrees of
2259    references.  Any expression with side-effects must be put in a SAVE_EXPR
2260    to ensure that it is only evaluated once.
2261
2262    We don't put SAVE_EXPR nodes around everything, because assigning very
2263    simple expressions to temporaries causes us to miss good opportunities
2264    for optimizations.  Among other things, the opportunity to fold in the
2265    addition of a constant into an addressing mode often gets lost, e.g.
2266    "y[i+1] += x;".  In general, we take the approach that we should not make
2267    an assignment unless we are forced into it - i.e., that any non-side effect
2268    operator should be allowed, and that cse should take care of coalescing
2269    multiple utterances of the same expression should that prove fruitful.  */
2270
2271 tree
2272 stabilize_reference_1 (e)
2273      tree e;
2274 {
2275   tree result;
2276   enum tree_code code = TREE_CODE (e);
2277
2278   /* We cannot ignore const expressions because it might be a reference
2279      to a const array but whose index contains side-effects.  But we can
2280      ignore things that are actual constant or that already have been
2281      handled by this function.  */
2282
2283   if (TREE_CONSTANT (e) || code == SAVE_EXPR)
2284     return e;
2285
2286   switch (TREE_CODE_CLASS (code))
2287     {
2288     case 'x':
2289     case 't':
2290     case 'd':
2291     case 'b':
2292     case '<':
2293     case 's':
2294     case 'e':
2295     case 'r':
2296       /* If the expression has side-effects, then encase it in a SAVE_EXPR
2297          so that it will only be evaluated once.  */
2298       /* The reference (r) and comparison (<) classes could be handled as
2299          below, but it is generally faster to only evaluate them once.  */
2300       if (TREE_SIDE_EFFECTS (e))
2301         return save_expr (e);
2302       return e;
2303
2304     case 'c':
2305       /* Constants need no processing.  In fact, we should never reach
2306          here.  */
2307       return e;
2308
2309     case '2':
2310       /* Division is slow and tends to be compiled with jumps,
2311          especially the division by powers of 2 that is often
2312          found inside of an array reference.  So do it just once.  */
2313       if (code == TRUNC_DIV_EXPR || code == TRUNC_MOD_EXPR
2314           || code == FLOOR_DIV_EXPR || code == FLOOR_MOD_EXPR
2315           || code == CEIL_DIV_EXPR || code == CEIL_MOD_EXPR
2316           || code == ROUND_DIV_EXPR || code == ROUND_MOD_EXPR)
2317         return save_expr (e);
2318       /* Recursively stabilize each operand.  */
2319       result = build_nt (code, stabilize_reference_1 (TREE_OPERAND (e, 0)),
2320                          stabilize_reference_1 (TREE_OPERAND (e, 1)));
2321       break;
2322
2323     case '1':
2324       /* Recursively stabilize each operand.  */
2325       result = build_nt (code, stabilize_reference_1 (TREE_OPERAND (e, 0)));
2326       break;
2327
2328     default:
2329       abort ();
2330     }
2331
2332   TREE_TYPE (result) = TREE_TYPE (e);
2333   TREE_READONLY (result) = TREE_READONLY (e);
2334   TREE_SIDE_EFFECTS (result) = TREE_SIDE_EFFECTS (e);
2335   TREE_THIS_VOLATILE (result) = TREE_THIS_VOLATILE (e);
2336
2337   return result;
2338 }
2339 \f
2340 /* Low-level constructors for expressions.  */
2341
2342 /* Build an expression of code CODE, data type TYPE,
2343    and operands as specified by the arguments ARG1 and following arguments.
2344    Expressions and reference nodes can be created this way.
2345    Constants, decls, types and misc nodes cannot be.  */
2346
2347 tree
2348 build VPARAMS ((enum tree_code code, tree tt, ...))
2349 {
2350   tree t;
2351   int length;
2352   int i;
2353   int fro;
2354   int constant;
2355
2356   VA_OPEN (p, tt);
2357   VA_FIXEDARG (p, enum tree_code, code);
2358   VA_FIXEDARG (p, tree, tt);
2359
2360   t = make_node (code);
2361   length = TREE_CODE_LENGTH (code);
2362   TREE_TYPE (t) = tt;
2363
2364   /* Below, we automatically set TREE_SIDE_EFFECTS and TREE_READONLY for the
2365      result based on those same flags for the arguments.  But if the
2366      arguments aren't really even `tree' expressions, we shouldn't be trying
2367      to do this.  */
2368   fro = first_rtl_op (code);
2369
2370   /* Expressions without side effects may be constant if their
2371      arguments are as well.  */
2372   constant = (TREE_CODE_CLASS (code) == '<'
2373               || TREE_CODE_CLASS (code) == '1'
2374               || TREE_CODE_CLASS (code) == '2'
2375               || TREE_CODE_CLASS (code) == 'c');
2376
2377   if (length == 2)
2378     {
2379       /* This is equivalent to the loop below, but faster.  */
2380       tree arg0 = va_arg (p, tree);
2381       tree arg1 = va_arg (p, tree);
2382
2383       TREE_OPERAND (t, 0) = arg0;
2384       TREE_OPERAND (t, 1) = arg1;
2385       TREE_READONLY (t) = 1;
2386       if (arg0 && fro > 0)
2387         {
2388           if (TREE_SIDE_EFFECTS (arg0))
2389             TREE_SIDE_EFFECTS (t) = 1;
2390           if (!TREE_READONLY (arg0))
2391             TREE_READONLY (t) = 0;
2392           if (!TREE_CONSTANT (arg0))
2393             constant = 0;
2394         }
2395
2396       if (arg1 && fro > 1)
2397         {
2398           if (TREE_SIDE_EFFECTS (arg1))
2399             TREE_SIDE_EFFECTS (t) = 1;
2400           if (!TREE_READONLY (arg1))
2401             TREE_READONLY (t) = 0;
2402           if (!TREE_CONSTANT (arg1))
2403             constant = 0;
2404         }
2405     }
2406   else if (length == 1)
2407     {
2408       tree arg0 = va_arg (p, tree);
2409
2410       /* The only one-operand cases we handle here are those with side-effects.
2411          Others are handled with build1.  So don't bother checked if the
2412          arg has side-effects since we'll already have set it.
2413
2414          ??? This really should use build1 too.  */
2415       if (TREE_CODE_CLASS (code) != 's')
2416         abort ();
2417       TREE_OPERAND (t, 0) = arg0;
2418     }
2419   else
2420     {
2421       for (i = 0; i < length; i++)
2422         {
2423           tree operand = va_arg (p, tree);
2424
2425           TREE_OPERAND (t, i) = operand;
2426           if (operand && fro > i)
2427             {
2428               if (TREE_SIDE_EFFECTS (operand))
2429                 TREE_SIDE_EFFECTS (t) = 1;
2430               if (!TREE_CONSTANT (operand))
2431                 constant = 0;
2432             }
2433         }
2434     }
2435   VA_CLOSE (p);
2436
2437   TREE_CONSTANT (t) = constant;
2438   return t;
2439 }
2440
2441 /* Same as above, but only builds for unary operators.
2442    Saves lions share of calls to `build'; cuts down use
2443    of varargs, which is expensive for RISC machines.  */
2444
2445 tree
2446 build1 (code, type, node)
2447      enum tree_code code;
2448      tree type;
2449      tree node;
2450 {
2451   int length;
2452 #ifdef GATHER_STATISTICS
2453   tree_node_kind kind;
2454 #endif
2455   tree t;
2456
2457 #ifdef GATHER_STATISTICS
2458   if (TREE_CODE_CLASS (code) == 'r')
2459     kind = r_kind;
2460   else
2461     kind = e_kind;
2462 #endif
2463
2464 #ifdef ENABLE_CHECKING
2465   if (TREE_CODE_CLASS (code) == '2' 
2466       || TREE_CODE_CLASS (code) == '<'
2467       || TREE_CODE_LENGTH (code) != 1)
2468     abort ();
2469 #endif /* ENABLE_CHECKING */
2470
2471   length = sizeof (struct tree_exp);
2472
2473   t = ggc_alloc_tree (length);
2474
2475   memset ((PTR) t, 0, sizeof (struct tree_common));
2476
2477 #ifdef GATHER_STATISTICS
2478   tree_node_counts[(int) kind]++;
2479   tree_node_sizes[(int) kind] += length;
2480 #endif
2481
2482   TREE_SET_CODE (t, code);
2483
2484   TREE_TYPE (t) = type;
2485   TREE_COMPLEXITY (t) = 0;
2486   TREE_OPERAND (t, 0) = node;
2487   if (node && first_rtl_op (code) != 0)
2488     {
2489       TREE_SIDE_EFFECTS (t) = TREE_SIDE_EFFECTS (node);
2490       TREE_READONLY (t) = TREE_READONLY (node);
2491     }
2492
2493   switch (code)
2494     {
2495     case INIT_EXPR:
2496     case MODIFY_EXPR:
2497     case VA_ARG_EXPR:
2498     case RTL_EXPR:
2499     case PREDECREMENT_EXPR:
2500     case PREINCREMENT_EXPR:
2501     case POSTDECREMENT_EXPR:
2502     case POSTINCREMENT_EXPR:
2503       /* All of these have side-effects, no matter what their
2504          operands are.  */
2505       TREE_SIDE_EFFECTS (t) = 1;
2506       TREE_READONLY (t) = 0;
2507       break;
2508
2509     default:
2510       if (TREE_CODE_CLASS (code) == '1' && node && TREE_CONSTANT (node))
2511         TREE_CONSTANT (t) = 1;
2512       break;
2513     }
2514
2515   return t;
2516 }
2517
2518 /* Similar except don't specify the TREE_TYPE
2519    and leave the TREE_SIDE_EFFECTS as 0.
2520    It is permissible for arguments to be null,
2521    or even garbage if their values do not matter.  */
2522
2523 tree
2524 build_nt VPARAMS ((enum tree_code code, ...))
2525 {
2526   tree t;
2527   int length;
2528   int i;
2529
2530   VA_OPEN (p, code);
2531   VA_FIXEDARG (p, enum tree_code, code);
2532
2533   t = make_node (code);
2534   length = TREE_CODE_LENGTH (code);
2535
2536   for (i = 0; i < length; i++)
2537     TREE_OPERAND (t, i) = va_arg (p, tree);
2538
2539   VA_CLOSE (p);
2540   return t;
2541 }
2542 \f
2543 /* Create a DECL_... node of code CODE, name NAME and data type TYPE.
2544    We do NOT enter this node in any sort of symbol table.
2545
2546    layout_decl is used to set up the decl's storage layout.
2547    Other slots are initialized to 0 or null pointers.  */
2548
2549 tree
2550 build_decl (code, name, type)
2551      enum tree_code code;
2552      tree name, type;
2553 {
2554   tree t;
2555
2556   t = make_node (code);
2557
2558 /*  if (type == error_mark_node)
2559     type = integer_type_node; */
2560 /* That is not done, deliberately, so that having error_mark_node
2561    as the type can suppress useless errors in the use of this variable.  */
2562
2563   DECL_NAME (t) = name;
2564   TREE_TYPE (t) = type;
2565
2566   if (code == VAR_DECL || code == PARM_DECL || code == RESULT_DECL)
2567     layout_decl (t, 0);
2568   else if (code == FUNCTION_DECL)
2569     DECL_MODE (t) = FUNCTION_MODE;
2570
2571   return t;
2572 }
2573 \f
2574 /* BLOCK nodes are used to represent the structure of binding contours
2575    and declarations, once those contours have been exited and their contents
2576    compiled.  This information is used for outputting debugging info.  */
2577
2578 tree
2579 build_block (vars, tags, subblocks, supercontext, chain)
2580      tree vars, tags ATTRIBUTE_UNUSED, subblocks, supercontext, chain;
2581 {
2582   tree block = make_node (BLOCK);
2583
2584   BLOCK_VARS (block) = vars;
2585   BLOCK_SUBBLOCKS (block) = subblocks;
2586   BLOCK_SUPERCONTEXT (block) = supercontext;
2587   BLOCK_CHAIN (block) = chain;
2588   return block;
2589 }
2590
2591 /* EXPR_WITH_FILE_LOCATION are used to keep track of the exact
2592    location where an expression or an identifier were encountered. It
2593    is necessary for languages where the frontend parser will handle
2594    recursively more than one file (Java is one of them).  */
2595
2596 tree
2597 build_expr_wfl (node, file, line, col)
2598      tree node;
2599      const char *file;
2600      int line, col;
2601 {
2602   static const char *last_file = 0;
2603   static tree last_filenode = NULL_TREE;
2604   tree wfl = make_node (EXPR_WITH_FILE_LOCATION);
2605
2606   EXPR_WFL_NODE (wfl) = node;
2607   EXPR_WFL_SET_LINECOL (wfl, line, col);
2608   if (file != last_file)
2609     {
2610       last_file = file;
2611       last_filenode = file ? get_identifier (file) : NULL_TREE;
2612     }
2613
2614   EXPR_WFL_FILENAME_NODE (wfl) = last_filenode;
2615   if (node)
2616     {
2617       TREE_SIDE_EFFECTS (wfl) = TREE_SIDE_EFFECTS (node);
2618       TREE_TYPE (wfl) = TREE_TYPE (node);
2619     }
2620
2621   return wfl;
2622 }
2623 \f
2624 /* Return a declaration like DDECL except that its DECL_ATTRIBUTES
2625    is ATTRIBUTE.  */
2626
2627 tree
2628 build_decl_attribute_variant (ddecl, attribute)
2629      tree ddecl, attribute;
2630 {
2631   DECL_ATTRIBUTES (ddecl) = attribute;
2632   return ddecl;
2633 }
2634
2635 /* Return a type like TTYPE except that its TYPE_ATTRIBUTE
2636    is ATTRIBUTE.
2637
2638    Record such modified types already made so we don't make duplicates.  */
2639
2640 tree
2641 build_type_attribute_variant (ttype, attribute)
2642      tree ttype, attribute;
2643 {
2644   if ( ! attribute_list_equal (TYPE_ATTRIBUTES (ttype), attribute))
2645     {
2646       unsigned int hashcode;
2647       tree ntype;
2648
2649       ntype = copy_node (ttype);
2650
2651       TYPE_POINTER_TO (ntype) = 0;
2652       TYPE_REFERENCE_TO (ntype) = 0;
2653       TYPE_ATTRIBUTES (ntype) = attribute;
2654
2655       /* Create a new main variant of TYPE.  */
2656       TYPE_MAIN_VARIANT (ntype) = ntype;
2657       TYPE_NEXT_VARIANT (ntype) = 0;
2658       set_type_quals (ntype, TYPE_UNQUALIFIED);
2659
2660       hashcode = (TYPE_HASH (TREE_CODE (ntype))
2661                   + TYPE_HASH (TREE_TYPE (ntype))
2662                   + attribute_hash_list (attribute));
2663
2664       switch (TREE_CODE (ntype))
2665         {
2666         case FUNCTION_TYPE:
2667           hashcode += TYPE_HASH (TYPE_ARG_TYPES (ntype));
2668           break;
2669         case ARRAY_TYPE:
2670           hashcode += TYPE_HASH (TYPE_DOMAIN (ntype));
2671           break;
2672         case INTEGER_TYPE:
2673           hashcode += TYPE_HASH (TYPE_MAX_VALUE (ntype));
2674           break;
2675         case REAL_TYPE:
2676           hashcode += TYPE_HASH (TYPE_PRECISION (ntype));
2677           break;
2678         default:
2679           break;
2680         }
2681
2682       ntype = type_hash_canon (hashcode, ntype);
2683       ttype = build_qualified_type (ntype, TYPE_QUALS (ttype));
2684     }
2685
2686   return ttype;
2687 }
2688
2689 /* Default value of targetm.comp_type_attributes that always returns 1.  */
2690
2691 int
2692 default_comp_type_attributes (type1, type2)
2693      tree type1 ATTRIBUTE_UNUSED;
2694      tree type2 ATTRIBUTE_UNUSED;
2695 {
2696   return 1;
2697 }
2698
2699 /* Default version of targetm.set_default_type_attributes that always does
2700    nothing.  */
2701
2702 void
2703 default_set_default_type_attributes (type)
2704      tree type ATTRIBUTE_UNUSED;
2705 {
2706 }
2707
2708 /* Default version of targetm.insert_attributes that always does nothing.  */
2709 void
2710 default_insert_attributes (decl, attr_ptr)
2711      tree decl ATTRIBUTE_UNUSED;
2712      tree *attr_ptr ATTRIBUTE_UNUSED;
2713 {
2714 }
2715
2716 /* Default value of targetm.attribute_table that is empty.  */
2717 const struct attribute_spec default_target_attribute_table[] =
2718 {
2719   { NULL, 0, 0, false, false, false, NULL }
2720 };
2721
2722 /* Default value of targetm.function_attribute_inlinable_p that always
2723    returns false.  */
2724 bool
2725 default_function_attribute_inlinable_p (fndecl)
2726      tree fndecl ATTRIBUTE_UNUSED;
2727 {
2728   /* By default, functions with machine attributes cannot be inlined.  */
2729   return false;
2730 }
2731
2732 /* Return non-zero if IDENT is a valid name for attribute ATTR,
2733    or zero if not.
2734
2735    We try both `text' and `__text__', ATTR may be either one.  */
2736 /* ??? It might be a reasonable simplification to require ATTR to be only
2737    `text'.  One might then also require attribute lists to be stored in
2738    their canonicalized form.  */
2739
2740 int
2741 is_attribute_p (attr, ident)
2742      const char *attr;
2743      tree ident;
2744 {
2745   int ident_len, attr_len;
2746   const char *p;
2747
2748   if (TREE_CODE (ident) != IDENTIFIER_NODE)
2749     return 0;
2750
2751   if (strcmp (attr, IDENTIFIER_POINTER (ident)) == 0)
2752     return 1;
2753
2754   p = IDENTIFIER_POINTER (ident);
2755   ident_len = strlen (p);
2756   attr_len = strlen (attr);
2757
2758   /* If ATTR is `__text__', IDENT must be `text'; and vice versa.  */
2759   if (attr[0] == '_')
2760     {
2761       if (attr[1] != '_'
2762           || attr[attr_len - 2] != '_'
2763           || attr[attr_len - 1] != '_')
2764         abort ();
2765       if (ident_len == attr_len - 4
2766           && strncmp (attr + 2, p, attr_len - 4) == 0)
2767         return 1;
2768     }
2769   else
2770     {
2771       if (ident_len == attr_len + 4
2772           && p[0] == '_' && p[1] == '_'
2773           && p[ident_len - 2] == '_' && p[ident_len - 1] == '_'
2774           && strncmp (attr, p + 2, attr_len) == 0)
2775         return 1;
2776     }
2777
2778   return 0;
2779 }
2780
2781 /* Given an attribute name and a list of attributes, return a pointer to the
2782    attribute's list element if the attribute is part of the list, or NULL_TREE
2783    if not found.  If the attribute appears more than once, this only
2784    returns the first occurrence; the TREE_CHAIN of the return value should
2785    be passed back in if further occurrences are wanted.  */
2786
2787 tree
2788 lookup_attribute (attr_name, list)
2789      const char *attr_name;
2790      tree list;
2791 {
2792   tree l;
2793
2794   for (l = list; l; l = TREE_CHAIN (l))
2795     {
2796       if (TREE_CODE (TREE_PURPOSE (l)) != IDENTIFIER_NODE)
2797         abort ();
2798       if (is_attribute_p (attr_name, TREE_PURPOSE (l)))
2799         return l;
2800     }
2801
2802   return NULL_TREE;
2803 }
2804
2805 /* Return an attribute list that is the union of a1 and a2.  */
2806
2807 tree
2808 merge_attributes (a1, a2)
2809      tree a1, a2;
2810 {
2811   tree attributes;
2812
2813   /* Either one unset?  Take the set one.  */
2814
2815   if ((attributes = a1) == 0)
2816     attributes = a2;
2817
2818   /* One that completely contains the other?  Take it.  */
2819
2820   else if (a2 != 0 && ! attribute_list_contained (a1, a2))
2821     {
2822       if (attribute_list_contained (a2, a1))
2823         attributes = a2;
2824       else
2825         {
2826           /* Pick the longest list, and hang on the other list.  */
2827
2828           if (list_length (a1) < list_length (a2))
2829             attributes = a2, a2 = a1;
2830
2831           for (; a2 != 0; a2 = TREE_CHAIN (a2))
2832             {
2833               tree a;
2834               for (a = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (a2)),
2835                                          attributes);
2836                    a != NULL_TREE;
2837                    a = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (a2)),
2838                                          TREE_CHAIN (a)))
2839                 {
2840                   if (simple_cst_equal (TREE_VALUE (a), TREE_VALUE (a2)) == 1)
2841                     break;
2842                 }
2843               if (a == NULL_TREE)
2844                 {
2845                   a1 = copy_node (a2);
2846                   TREE_CHAIN (a1) = attributes;
2847                   attributes = a1;
2848                 }
2849             }
2850         }
2851     }
2852   return attributes;
2853 }
2854
2855 /* Given types T1 and T2, merge their attributes and return
2856   the result.  */
2857
2858 tree
2859 merge_type_attributes (t1, t2)
2860      tree t1, t2;
2861 {
2862   return merge_attributes (TYPE_ATTRIBUTES (t1),
2863                            TYPE_ATTRIBUTES (t2));
2864 }
2865
2866 /* Given decls OLDDECL and NEWDECL, merge their attributes and return
2867    the result.  */
2868
2869 tree
2870 merge_decl_attributes (olddecl, newdecl)
2871      tree olddecl, newdecl;
2872 {
2873   return merge_attributes (DECL_ATTRIBUTES (olddecl),
2874                            DECL_ATTRIBUTES (newdecl));
2875 }
2876
2877 #ifdef TARGET_DLLIMPORT_DECL_ATTRIBUTES
2878
2879 /* Specialization of merge_decl_attributes for various Windows targets.
2880
2881    This handles the following situation:
2882
2883      __declspec (dllimport) int foo;
2884      int foo;
2885
2886    The second instance of `foo' nullifies the dllimport.  */
2887
2888 tree
2889 merge_dllimport_decl_attributes (old, new)
2890      tree old;
2891      tree new;
2892 {
2893   tree a;
2894   int delete_dllimport_p;
2895
2896   old = DECL_ATTRIBUTES (old);
2897   new = DECL_ATTRIBUTES (new);
2898
2899   /* What we need to do here is remove from `old' dllimport if it doesn't
2900      appear in `new'.  dllimport behaves like extern: if a declaration is
2901      marked dllimport and a definition appears later, then the object
2902      is not dllimport'd.  */
2903   if (lookup_attribute ("dllimport", old) != NULL_TREE
2904       && lookup_attribute ("dllimport", new) == NULL_TREE)
2905     delete_dllimport_p = 1;
2906   else
2907     delete_dllimport_p = 0;
2908
2909   a = merge_attributes (old, new);
2910
2911   if (delete_dllimport_p)
2912     {
2913       tree prev,t;
2914
2915       /* Scan the list for dllimport and delete it.  */
2916       for (prev = NULL_TREE, t = a; t; prev = t, t = TREE_CHAIN (t))
2917         {
2918           if (is_attribute_p ("dllimport", TREE_PURPOSE (t)))
2919             {
2920               if (prev == NULL_TREE)
2921                 a = TREE_CHAIN (a);
2922               else
2923                 TREE_CHAIN (prev) = TREE_CHAIN (t);
2924               break;
2925             }
2926         }
2927     }
2928
2929   return a;
2930 }
2931
2932 #endif /* TARGET_DLLIMPORT_DECL_ATTRIBUTES  */
2933 \f
2934 /* Set the type qualifiers for TYPE to TYPE_QUALS, which is a bitmask
2935    of the various TYPE_QUAL values.  */
2936
2937 static void
2938 set_type_quals (type, type_quals)
2939      tree type;
2940      int type_quals;
2941 {
2942   TYPE_READONLY (type) = (type_quals & TYPE_QUAL_CONST) != 0;
2943   TYPE_VOLATILE (type) = (type_quals & TYPE_QUAL_VOLATILE) != 0;
2944   TYPE_RESTRICT (type) = (type_quals & TYPE_QUAL_RESTRICT) != 0;
2945 }
2946
2947 /* Return a version of the TYPE, qualified as indicated by the
2948    TYPE_QUALS, if one exists.  If no qualified version exists yet,
2949    return NULL_TREE.  */
2950
2951 tree
2952 get_qualified_type (type, type_quals)
2953      tree type;
2954      int type_quals;
2955 {
2956   tree t;
2957
2958   /* Search the chain of variants to see if there is already one there just
2959      like the one we need to have.  If so, use that existing one.  We must
2960      preserve the TYPE_NAME, since there is code that depends on this.  */
2961   for (t = TYPE_MAIN_VARIANT (type); t; t = TYPE_NEXT_VARIANT (t))
2962     if (TYPE_QUALS (t) == type_quals && TYPE_NAME (t) == TYPE_NAME (type))
2963       return t;
2964
2965   return NULL_TREE;
2966 }
2967
2968 /* Like get_qualified_type, but creates the type if it does not
2969    exist.  This function never returns NULL_TREE.  */
2970
2971 tree
2972 build_qualified_type (type, type_quals)
2973      tree type;
2974      int type_quals;
2975 {
2976   tree t;
2977
2978   /* See if we already have the appropriate qualified variant.  */
2979   t = get_qualified_type (type, type_quals);
2980
2981   /* If not, build it.  */
2982   if (!t)
2983     {
2984       t = build_type_copy (type);
2985       set_type_quals (t, type_quals);
2986     }
2987
2988   return t;
2989 }
2990
2991 /* Create a new variant of TYPE, equivalent but distinct.
2992    This is so the caller can modify it.  */
2993
2994 tree
2995 build_type_copy (type)
2996      tree type;
2997 {
2998   tree t, m = TYPE_MAIN_VARIANT (type);
2999
3000   t = copy_node (type);
3001
3002   TYPE_POINTER_TO (t) = 0;
3003   TYPE_REFERENCE_TO (t) = 0;
3004
3005   /* Add this type to the chain of variants of TYPE.  */
3006   TYPE_NEXT_VARIANT (t) = TYPE_NEXT_VARIANT (m);
3007   TYPE_NEXT_VARIANT (m) = t;
3008
3009   return t;
3010 }
3011 \f
3012 /* Hashing of types so that we don't make duplicates.
3013    The entry point is `type_hash_canon'.  */
3014
3015 /* Compute a hash code for a list of types (chain of TREE_LIST nodes
3016    with types in the TREE_VALUE slots), by adding the hash codes
3017    of the individual types.  */
3018
3019 unsigned int
3020 type_hash_list (list)
3021      tree list;
3022 {
3023   unsigned int hashcode;
3024   tree tail;
3025
3026   for (hashcode = 0, tail = list; tail; tail = TREE_CHAIN (tail))
3027     hashcode += TYPE_HASH (TREE_VALUE (tail));
3028
3029   return hashcode;
3030 }
3031
3032 /* These are the Hashtable callback functions.  */
3033
3034 /* Returns true if the types are equal.  */
3035
3036 static int
3037 type_hash_eq (va, vb)
3038      const void *va;
3039      const void *vb;
3040 {
3041   const struct type_hash *a = va, *b = vb;
3042   if (a->hash == b->hash
3043       && TREE_CODE (a->type) == TREE_CODE (b->type)
3044       && TREE_TYPE (a->type) == TREE_TYPE (b->type)
3045       && attribute_list_equal (TYPE_ATTRIBUTES (a->type),
3046                                TYPE_ATTRIBUTES (b->type))
3047       && TYPE_ALIGN (a->type) == TYPE_ALIGN (b->type)
3048       && (TYPE_MAX_VALUE (a->type) == TYPE_MAX_VALUE (b->type)
3049           || tree_int_cst_equal (TYPE_MAX_VALUE (a->type),
3050                                  TYPE_MAX_VALUE (b->type)))
3051       && (TYPE_MIN_VALUE (a->type) == TYPE_MIN_VALUE (b->type)
3052           || tree_int_cst_equal (TYPE_MIN_VALUE (a->type),
3053                                  TYPE_MIN_VALUE (b->type)))
3054       /* Note that TYPE_DOMAIN is TYPE_ARG_TYPES for FUNCTION_TYPE.  */
3055       && (TYPE_DOMAIN (a->type) == TYPE_DOMAIN (b->type)
3056           || (TYPE_DOMAIN (a->type)
3057               && TREE_CODE (TYPE_DOMAIN (a->type)) == TREE_LIST
3058               && TYPE_DOMAIN (b->type)
3059               && TREE_CODE (TYPE_DOMAIN (b->type)) == TREE_LIST
3060               && type_list_equal (TYPE_DOMAIN (a->type),
3061                                   TYPE_DOMAIN (b->type)))))
3062     return 1;
3063   return 0;
3064 }
3065
3066 /* Return the cached hash value.  */
3067
3068 static unsigned int
3069 type_hash_hash (item)
3070      const void *item;
3071 {
3072   return ((const struct type_hash *) item)->hash;
3073 }
3074
3075 /* Look in the type hash table for a type isomorphic to TYPE.
3076    If one is found, return it.  Otherwise return 0.  */
3077
3078 tree
3079 type_hash_lookup (hashcode, type)
3080      unsigned int hashcode;
3081      tree type;
3082 {
3083   struct type_hash *h, in;
3084
3085   /* The TYPE_ALIGN field of a type is set by layout_type(), so we
3086      must call that routine before comparing TYPE_ALIGNs.  */
3087   layout_type (type);
3088
3089   in.hash = hashcode;
3090   in.type = type;
3091
3092   h = htab_find_with_hash (type_hash_table, &in, hashcode);
3093   if (h)
3094     return h->type;
3095   return NULL_TREE;
3096 }
3097
3098 /* Add an entry to the type-hash-table
3099    for a type TYPE whose hash code is HASHCODE.  */
3100
3101 void
3102 type_hash_add (hashcode, type)
3103      unsigned int hashcode;
3104      tree type;
3105 {
3106   struct type_hash *h;
3107   void **loc;
3108
3109   h = (struct type_hash *) ggc_alloc (sizeof (struct type_hash));
3110   h->hash = hashcode;
3111   h->type = type;
3112   loc = htab_find_slot_with_hash (type_hash_table, h, hashcode, INSERT);
3113   *(struct type_hash **) loc = h;
3114 }
3115
3116 /* Given TYPE, and HASHCODE its hash code, return the canonical
3117    object for an identical type if one already exists.
3118    Otherwise, return TYPE, and record it as the canonical object
3119    if it is a permanent object.
3120
3121    To use this function, first create a type of the sort you want.
3122    Then compute its hash code from the fields of the type that
3123    make it different from other similar types.
3124    Then call this function and use the value.
3125    This function frees the type you pass in if it is a duplicate.  */
3126
3127 /* Set to 1 to debug without canonicalization.  Never set by program.  */
3128 int debug_no_type_hash = 0;
3129
3130 tree
3131 type_hash_canon (hashcode, type)
3132      unsigned int hashcode;
3133      tree type;
3134 {
3135   tree t1;
3136
3137   if (debug_no_type_hash)
3138     return type;
3139
3140   /* See if the type is in the hash table already.  If so, return it.
3141      Otherwise, add the type.  */
3142   t1 = type_hash_lookup (hashcode, type);
3143   if (t1 != 0)
3144     {
3145 #ifdef GATHER_STATISTICS
3146       tree_node_counts[(int) t_kind]--;
3147       tree_node_sizes[(int) t_kind] -= sizeof (struct tree_type);
3148 #endif
3149       return t1;
3150     }
3151   else
3152     {
3153       type_hash_add (hashcode, type);
3154       return type;
3155     }
3156 }
3157
3158 /* See if the data pointed to by the type hash table is marked.  We consider
3159    it marked if the type is marked or if a debug type number or symbol
3160    table entry has been made for the type.  This reduces the amount of
3161    debugging output and eliminates that dependency of the debug output on
3162    the number of garbage collections.  */
3163
3164 static int
3165 type_hash_marked_p (p)
3166      const void *p;
3167 {
3168   tree type = ((struct type_hash *) p)->type;
3169
3170   return ggc_marked_p (type) || TYPE_SYMTAB_POINTER (type);
3171 }
3172
3173 /* Mark the entry in the type hash table the type it points to is marked.
3174    Also mark the type in case we are considering this entry "marked" by
3175    virtue of TYPE_SYMTAB_POINTER being set.  */
3176
3177 static void
3178 type_hash_mark (p)
3179      const void *p;
3180 {
3181   ggc_mark (p);
3182   ggc_mark_tree (((struct type_hash *) p)->type);
3183 }
3184
3185 /* Mark the hashtable slot pointed to by ENTRY (which is really a
3186    `tree**') for GC.  */
3187
3188 static int
3189 mark_tree_hashtable_entry (entry, data)
3190      void **entry;
3191      void *data ATTRIBUTE_UNUSED;
3192 {
3193   ggc_mark_tree ((tree) *entry);
3194   return 1;
3195 }
3196
3197 /* Mark ARG (which is really a htab_t whose slots are trees) for 
3198    GC.  */
3199
3200 void
3201 mark_tree_hashtable (arg)
3202      void *arg;
3203 {
3204   htab_t t = *(htab_t *) arg;
3205   htab_traverse (t, mark_tree_hashtable_entry, 0);
3206 }
3207
3208 static void
3209 print_type_hash_statistics ()
3210 {
3211   fprintf (stderr, "Type hash: size %ld, %ld elements, %f collisions\n",
3212            (long) htab_size (type_hash_table),
3213            (long) htab_elements (type_hash_table),
3214            htab_collisions (type_hash_table));
3215 }
3216
3217 /* Compute a hash code for a list of attributes (chain of TREE_LIST nodes
3218    with names in the TREE_PURPOSE slots and args in the TREE_VALUE slots),
3219    by adding the hash codes of the individual attributes.  */
3220
3221 unsigned int
3222 attribute_hash_list (list)
3223      tree list;
3224 {
3225   unsigned int hashcode;
3226   tree tail;
3227
3228   for (hashcode = 0, tail = list; tail; tail = TREE_CHAIN (tail))
3229     /* ??? Do we want to add in TREE_VALUE too? */
3230     hashcode += TYPE_HASH (TREE_PURPOSE (tail));
3231   return hashcode;
3232 }
3233
3234 /* Given two lists of attributes, return true if list l2 is
3235    equivalent to l1.  */
3236
3237 int
3238 attribute_list_equal (l1, l2)
3239      tree l1, l2;
3240 {
3241    return attribute_list_contained (l1, l2)
3242           && attribute_list_contained (l2, l1);
3243 }
3244
3245 /* Given two lists of attributes, return true if list L2 is
3246    completely contained within L1.  */
3247 /* ??? This would be faster if attribute names were stored in a canonicalized
3248    form.  Otherwise, if L1 uses `foo' and L2 uses `__foo__', the long method
3249    must be used to show these elements are equivalent (which they are).  */
3250 /* ??? It's not clear that attributes with arguments will always be handled
3251    correctly.  */
3252
3253 int
3254 attribute_list_contained (l1, l2)
3255      tree l1, l2;
3256 {
3257   tree t1, t2;
3258
3259   /* First check the obvious, maybe the lists are identical.  */
3260   if (l1 == l2)
3261     return 1;
3262
3263   /* Maybe the lists are similar.  */
3264   for (t1 = l1, t2 = l2;
3265        t1 != 0 && t2 != 0
3266         && TREE_PURPOSE (t1) == TREE_PURPOSE (t2)
3267         && TREE_VALUE (t1) == TREE_VALUE (t2);
3268        t1 = TREE_CHAIN (t1), t2 = TREE_CHAIN (t2));
3269
3270   /* Maybe the lists are equal.  */
3271   if (t1 == 0 && t2 == 0)
3272      return 1;
3273
3274   for (; t2 != 0; t2 = TREE_CHAIN (t2))
3275     {
3276       tree attr;
3277       for (attr = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (t2)), l1);
3278            attr != NULL_TREE;
3279            attr = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (t2)),
3280                                     TREE_CHAIN (attr)))
3281         {
3282           if (simple_cst_equal (TREE_VALUE (t2), TREE_VALUE (attr)) == 1)
3283             break;
3284         }
3285
3286       if (attr == 0)
3287         return 0;
3288
3289       if (simple_cst_equal (TREE_VALUE (t2), TREE_VALUE (attr)) != 1)
3290         return 0;
3291     }
3292
3293   return 1;
3294 }
3295
3296 /* Given two lists of types
3297    (chains of TREE_LIST nodes with types in the TREE_VALUE slots)
3298    return 1 if the lists contain the same types in the same order.
3299    Also, the TREE_PURPOSEs must match.  */
3300
3301 int
3302 type_list_equal (l1, l2)
3303      tree l1, l2;
3304 {
3305   tree t1, t2;
3306
3307   for (t1 = l1, t2 = l2; t1 && t2; t1 = TREE_CHAIN (t1), t2 = TREE_CHAIN (t2))
3308     if (TREE_VALUE (t1) != TREE_VALUE (t2)
3309         || (TREE_PURPOSE (t1) != TREE_PURPOSE (t2)
3310             && ! (1 == simple_cst_equal (TREE_PURPOSE (t1), TREE_PURPOSE (t2))
3311                   && (TREE_TYPE (TREE_PURPOSE (t1))
3312                       == TREE_TYPE (TREE_PURPOSE (t2))))))
3313       return 0;
3314
3315   return t1 == t2;
3316 }
3317
3318 /* Returns the number of arguments to the FUNCTION_TYPE or METHOD_TYPE
3319    given by TYPE.  If the argument list accepts variable arguments,
3320    then this function counts only the ordinary arguments.  */
3321
3322 int
3323 type_num_arguments (type)
3324      tree type;
3325 {
3326   int i = 0;
3327   tree t;
3328
3329   for (t = TYPE_ARG_TYPES (type); t; t = TREE_CHAIN (t))
3330     /* If the function does not take a variable number of arguments,
3331        the last element in the list will have type `void'.  */
3332     if (VOID_TYPE_P (TREE_VALUE (t)))
3333       break;
3334     else
3335       ++i;
3336
3337   return i;
3338 }
3339
3340 /* Nonzero if integer constants T1 and T2
3341    represent the same constant value.  */
3342
3343 int
3344 tree_int_cst_equal (t1, t2)
3345      tree t1, t2;
3346 {
3347   if (t1 == t2)
3348     return 1;
3349
3350   if (t1 == 0 || t2 == 0)
3351     return 0;
3352
3353   if (TREE_CODE (t1) == INTEGER_CST
3354       && TREE_CODE (t2) == INTEGER_CST
3355       && TREE_INT_CST_LOW (t1) == TREE_INT_CST_LOW (t2)
3356       && TREE_INT_CST_HIGH (t1) == TREE_INT_CST_HIGH (t2))
3357     return 1;
3358
3359   return 0;
3360 }
3361
3362 /* Nonzero if integer constants T1 and T2 represent values that satisfy <.
3363    The precise way of comparison depends on their data type.  */
3364
3365 int
3366 tree_int_cst_lt (t1, t2)
3367      tree t1, t2;
3368 {
3369   if (t1 == t2)
3370     return 0;
3371
3372   if (! TREE_UNSIGNED (TREE_TYPE (t1)))
3373     return INT_CST_LT (t1, t2);
3374
3375   return INT_CST_LT_UNSIGNED (t1, t2);
3376 }
3377
3378 /* Returns -1 if T1 < T2, 0 if T1 == T2, and 1 if T1 > T2.  */
3379
3380 int
3381 tree_int_cst_compare (t1, t2)
3382      tree t1;
3383      tree t2;
3384 {
3385   if (tree_int_cst_lt (t1, t2))
3386     return -1;
3387   else if (tree_int_cst_lt (t2, t1))
3388     return 1;
3389   else 
3390     return 0;
3391 }
3392
3393 /* Return 1 if T is an INTEGER_CST that can be represented in a single
3394    HOST_WIDE_INT value.  If POS is nonzero, the result must be positive.  */
3395
3396 int
3397 host_integerp (t, pos)
3398      tree t;
3399      int pos;
3400 {
3401   return (TREE_CODE (t) == INTEGER_CST
3402           && ! TREE_OVERFLOW (t)
3403           && ((TREE_INT_CST_HIGH (t) == 0
3404                && (HOST_WIDE_INT) TREE_INT_CST_LOW (t) >= 0)
3405               || (! pos && TREE_INT_CST_HIGH (t) == -1
3406                   && (HOST_WIDE_INT) TREE_INT_CST_LOW (t) < 0)
3407               || (! pos && TREE_INT_CST_HIGH (t) == 0
3408                   && TREE_UNSIGNED (TREE_TYPE (t)))));
3409 }
3410
3411 /* Return the HOST_WIDE_INT least significant bits of T if it is an
3412    INTEGER_CST and there is no overflow.  POS is nonzero if the result must
3413    be positive.  Abort if we cannot satisfy the above conditions.  */
3414
3415 HOST_WIDE_INT
3416 tree_low_cst (t, pos)
3417      tree t;
3418      int pos;
3419 {
3420   if (host_integerp (t, pos))
3421     return TREE_INT_CST_LOW (t);
3422   else
3423     abort ();
3424 }
3425
3426 /* Return the most significant bit of the integer constant T.  */
3427
3428 int
3429 tree_int_cst_msb (t)
3430      tree t;
3431 {
3432   int prec;
3433   HOST_WIDE_INT h;
3434   unsigned HOST_WIDE_INT l;
3435
3436   /* Note that using TYPE_PRECISION here is wrong.  We care about the
3437      actual bits, not the (arbitrary) range of the type.  */
3438   prec = GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (t))) - 1;
3439   rshift_double (TREE_INT_CST_LOW (t), TREE_INT_CST_HIGH (t), prec,
3440                  2 * HOST_BITS_PER_WIDE_INT, &l, &h, 0);
3441   return (l & 1) == 1;
3442 }
3443
3444 /* Return an indication of the sign of the integer constant T.
3445    The return value is -1 if T < 0, 0 if T == 0, and 1 if T > 0.
3446    Note that -1 will never be returned it T's type is unsigned.  */
3447
3448 int
3449 tree_int_cst_sgn (t)
3450      tree t;
3451 {
3452   if (TREE_INT_CST_LOW (t) == 0 && TREE_INT_CST_HIGH (t) == 0)
3453     return 0;
3454   else if (TREE_UNSIGNED (TREE_TYPE (t)))
3455     return 1;
3456   else if (TREE_INT_CST_HIGH (t) < 0)
3457     return -1;
3458   else
3459     return 1;
3460 }
3461
3462 /* Compare two constructor-element-type constants.  Return 1 if the lists
3463    are known to be equal; otherwise return 0.  */
3464
3465 int
3466 simple_cst_list_equal (l1, l2)
3467      tree l1, l2;
3468 {
3469   while (l1 != NULL_TREE && l2 != NULL_TREE)
3470     {
3471       if (simple_cst_equal (TREE_VALUE (l1), TREE_VALUE (l2)) != 1)
3472         return 0;
3473
3474       l1 = TREE_CHAIN (l1);
3475       l2 = TREE_CHAIN (l2);
3476     }
3477
3478   return l1 == l2;
3479 }
3480
3481 /* Return truthvalue of whether T1 is the same tree structure as T2.
3482    Return 1 if they are the same.
3483    Return 0 if they are understandably different.
3484    Return -1 if either contains tree structure not understood by
3485    this function.  */
3486
3487 int
3488 simple_cst_equal (t1, t2)
3489      tree t1, t2;
3490 {
3491   enum tree_code code1, code2;
3492   int cmp;
3493   int i;
3494
3495   if (t1 == t2)
3496     return 1;
3497   if (t1 == 0 || t2 == 0)
3498     return 0;
3499
3500   code1 = TREE_CODE (t1);
3501   code2 = TREE_CODE (t2);
3502
3503   if (code1 == NOP_EXPR || code1 == CONVERT_EXPR || code1 == NON_LVALUE_EXPR)
3504     {
3505       if (code2 == NOP_EXPR || code2 == CONVERT_EXPR
3506           || code2 == NON_LVALUE_EXPR)
3507         return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3508       else
3509         return simple_cst_equal (TREE_OPERAND (t1, 0), t2);
3510     }
3511
3512   else if (code2 == NOP_EXPR || code2 == CONVERT_EXPR
3513            || code2 == NON_LVALUE_EXPR)
3514     return simple_cst_equal (t1, TREE_OPERAND (t2, 0));
3515
3516   if (code1 != code2)
3517     return 0;
3518
3519   switch (code1)
3520     {
3521     case INTEGER_CST:
3522       return (TREE_INT_CST_LOW (t1) == TREE_INT_CST_LOW (t2)
3523               && TREE_INT_CST_HIGH (t1) == TREE_INT_CST_HIGH (t2));
3524
3525     case REAL_CST:
3526       return REAL_VALUES_IDENTICAL (TREE_REAL_CST (t1), TREE_REAL_CST (t2));
3527
3528     case STRING_CST:
3529       return (TREE_STRING_LENGTH (t1) == TREE_STRING_LENGTH (t2)
3530               && ! memcmp (TREE_STRING_POINTER (t1), TREE_STRING_POINTER (t2),
3531                          TREE_STRING_LENGTH (t1)));
3532
3533     case CONSTRUCTOR:
3534       if (CONSTRUCTOR_ELTS (t1) == CONSTRUCTOR_ELTS (t2))
3535         return 1;
3536       else
3537         abort ();
3538
3539     case SAVE_EXPR:
3540       return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3541
3542     case CALL_EXPR:
3543       cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3544       if (cmp <= 0)
3545         return cmp;
3546       return
3547         simple_cst_list_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
3548
3549     case TARGET_EXPR:
3550       /* Special case: if either target is an unallocated VAR_DECL,
3551          it means that it's going to be unified with whatever the
3552          TARGET_EXPR is really supposed to initialize, so treat it
3553          as being equivalent to anything.  */
3554       if ((TREE_CODE (TREE_OPERAND (t1, 0)) == VAR_DECL
3555            && DECL_NAME (TREE_OPERAND (t1, 0)) == NULL_TREE
3556            && !DECL_RTL_SET_P (TREE_OPERAND (t1, 0)))
3557           || (TREE_CODE (TREE_OPERAND (t2, 0)) == VAR_DECL
3558               && DECL_NAME (TREE_OPERAND (t2, 0)) == NULL_TREE
3559               && !DECL_RTL_SET_P (TREE_OPERAND (t2, 0))))
3560         cmp = 1;
3561       else
3562         cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3563
3564       if (cmp <= 0)
3565         return cmp;
3566
3567       return simple_cst_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
3568
3569     case WITH_CLEANUP_EXPR:
3570       cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3571       if (cmp <= 0)
3572         return cmp;
3573
3574       return simple_cst_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t1, 1));
3575
3576     case COMPONENT_REF:
3577       if (TREE_OPERAND (t1, 1) == TREE_OPERAND (t2, 1))
3578         return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3579
3580       return 0;
3581
3582     case VAR_DECL:
3583     case PARM_DECL:
3584     case CONST_DECL:
3585     case FUNCTION_DECL:
3586       return 0;
3587
3588     default:
3589       break;
3590     }
3591
3592   /* This general rule works for most tree codes.  All exceptions should be
3593      handled above.  If this is a language-specific tree code, we can't
3594      trust what might be in the operand, so say we don't know
3595      the situation.  */
3596   if ((int) code1 >= (int) LAST_AND_UNUSED_TREE_CODE)
3597     return -1;
3598
3599   switch (TREE_CODE_CLASS (code1))
3600     {
3601     case '1':
3602     case '2':
3603     case '<':
3604     case 'e':
3605     case 'r':
3606     case 's':
3607       cmp = 1;
3608       for (i = 0; i < TREE_CODE_LENGTH (code1); i++)
3609         {
3610           cmp = simple_cst_equal (TREE_OPERAND (t1, i), TREE_OPERAND (t2, i));
3611           if (cmp <= 0)
3612             return cmp;
3613         }
3614
3615       return cmp;
3616
3617     default:
3618       return -1;
3619     }
3620 }
3621
3622 /* Compare the value of T, an INTEGER_CST, with U, an unsigned integer value.
3623    Return -1, 0, or 1 if the value of T is less than, equal to, or greater
3624    than U, respectively.  */
3625
3626 int
3627 compare_tree_int (t, u)
3628      tree t;
3629      unsigned int u;
3630 {
3631   if (tree_int_cst_sgn (t) < 0)
3632     return -1;
3633   else if (TREE_INT_CST_HIGH (t) != 0)
3634     return 1;
3635   else if (TREE_INT_CST_LOW (t) == u)
3636     return 0;
3637   else if (TREE_INT_CST_LOW (t) < u)
3638     return -1;
3639   else
3640     return 1;
3641 }
3642 \f
3643 /* Constructors for pointer, array and function types.
3644    (RECORD_TYPE, UNION_TYPE and ENUMERAL_TYPE nodes are
3645    constructed by language-dependent code, not here.)  */
3646
3647 /* Construct, lay out and return the type of pointers to TO_TYPE.
3648    If such a type has already been constructed, reuse it.  */
3649
3650 tree
3651 build_pointer_type (to_type)
3652      tree to_type;
3653 {
3654   tree t = TYPE_POINTER_TO (to_type);
3655
3656   /* First, if we already have a type for pointers to TO_TYPE, use it.  */
3657
3658   if (t != 0)
3659     return t;
3660
3661   /* We need a new one.  */
3662   t = make_node (POINTER_TYPE);
3663
3664   TREE_TYPE (t) = to_type;
3665
3666   /* Record this type as the pointer to TO_TYPE.  */
3667   TYPE_POINTER_TO (to_type) = t;
3668
3669   /* Lay out the type.  This function has many callers that are concerned
3670      with expression-construction, and this simplifies them all.
3671      Also, it guarantees the TYPE_SIZE is in the same obstack as the type.  */
3672   layout_type (t);
3673
3674   return t;
3675 }
3676
3677 /* Build the node for the type of references-to-TO_TYPE.  */
3678
3679 tree
3680 build_reference_type (to_type)
3681      tree to_type;
3682 {
3683   tree t = TYPE_REFERENCE_TO (to_type);
3684
3685   /* First, if we already have a type for pointers to TO_TYPE, use it.  */
3686
3687   if (t)
3688     return t;
3689
3690   /* We need a new one.  */
3691   t = make_node (REFERENCE_TYPE);
3692
3693   TREE_TYPE (t) = to_type;
3694
3695   /* Record this type as the pointer to TO_TYPE.  */
3696   TYPE_REFERENCE_TO (to_type) = t;
3697
3698   layout_type (t);
3699
3700   return t;
3701 }
3702
3703 /* Build a type that is compatible with t but has no cv quals anywhere
3704    in its type, thus
3705
3706    const char *const *const *  ->  char ***.  */
3707
3708 tree
3709 build_type_no_quals (t)
3710   tree t;
3711 {
3712   switch (TREE_CODE (t))
3713     {
3714     case POINTER_TYPE:
3715       return build_pointer_type (build_type_no_quals (TREE_TYPE (t)));
3716     case REFERENCE_TYPE:
3717       return build_reference_type (build_type_no_quals (TREE_TYPE (t)));
3718     default:
3719       return TYPE_MAIN_VARIANT (t);
3720     }
3721 }
3722
3723 /* Create a type of integers to be the TYPE_DOMAIN of an ARRAY_TYPE.
3724    MAXVAL should be the maximum value in the domain
3725    (one less than the length of the array).
3726
3727    The maximum value that MAXVAL can have is INT_MAX for a HOST_WIDE_INT.
3728    We don't enforce this limit, that is up to caller (e.g. language front end).
3729    The limit exists because the result is a signed type and we don't handle
3730    sizes that use more than one HOST_WIDE_INT.  */
3731
3732 tree
3733 build_index_type (maxval)
3734      tree maxval;
3735 {
3736   tree itype = make_node (INTEGER_TYPE);
3737
3738   TREE_TYPE (itype) = sizetype;
3739   TYPE_PRECISION (itype) = TYPE_PRECISION (sizetype);
3740   TYPE_MIN_VALUE (itype) = size_zero_node;
3741   TYPE_MAX_VALUE (itype) = convert (sizetype, maxval);
3742   TYPE_MODE (itype) = TYPE_MODE (sizetype);
3743   TYPE_SIZE (itype) = TYPE_SIZE (sizetype);
3744   TYPE_SIZE_UNIT (itype) = TYPE_SIZE_UNIT (sizetype);
3745   TYPE_ALIGN (itype) = TYPE_ALIGN (sizetype);
3746   TYPE_USER_ALIGN (itype) = TYPE_USER_ALIGN (sizetype);
3747
3748   if (host_integerp (maxval, 1))
3749     return type_hash_canon (tree_low_cst (maxval, 1), itype);
3750   else
3751     return itype;
3752 }
3753
3754 /* Create a range of some discrete type TYPE (an INTEGER_TYPE,
3755    ENUMERAL_TYPE, BOOLEAN_TYPE, or CHAR_TYPE), with
3756    low bound LOWVAL and high bound HIGHVAL.
3757    if TYPE==NULL_TREE, sizetype is used.  */
3758
3759 tree
3760 build_range_type (type, lowval, highval)
3761      tree type, lowval, highval;
3762 {
3763   tree itype = make_node (INTEGER_TYPE);
3764
3765   TREE_TYPE (itype) = type;
3766   if (type == NULL_TREE)
3767     type = sizetype;
3768
3769   TYPE_MIN_VALUE (itype) = convert (type, lowval);
3770   TYPE_MAX_VALUE (itype) = highval ? convert (type, highval) : NULL;
3771
3772   TYPE_PRECISION (itype) = TYPE_PRECISION (type);
3773   TYPE_MODE (itype) = TYPE_MODE (type);
3774   TYPE_SIZE (itype) = TYPE_SIZE (type);
3775   TYPE_SIZE_UNIT (itype) = TYPE_SIZE_UNIT (type);
3776   TYPE_ALIGN (itype) = TYPE_ALIGN (type);
3777   TYPE_USER_ALIGN (itype) = TYPE_USER_ALIGN (type);
3778
3779   if (host_integerp (lowval, 0) && highval != 0 && host_integerp (highval, 0))
3780     return type_hash_canon (tree_low_cst (highval, 0)
3781                             - tree_low_cst (lowval, 0),
3782                             itype);
3783   else
3784     return itype;
3785 }
3786
3787 /* Just like build_index_type, but takes lowval and highval instead
3788    of just highval (maxval).  */
3789
3790 tree
3791 build_index_2_type (lowval,highval)
3792      tree lowval, highval;
3793 {
3794   return build_range_type (sizetype, lowval, highval);
3795 }
3796
3797 /* Return nonzero iff ITYPE1 and ITYPE2 are equal (in the LISP sense).
3798    Needed because when index types are not hashed, equal index types
3799    built at different times appear distinct, even though structurally,
3800    they are not.  */
3801
3802 int
3803 index_type_equal (itype1, itype2)
3804      tree itype1, itype2;
3805 {
3806   if (TREE_CODE (itype1) != TREE_CODE (itype2))
3807     return 0;
3808
3809   if (TREE_CODE (itype1) == INTEGER_TYPE)
3810     {
3811       if (TYPE_PRECISION (itype1) != TYPE_PRECISION (itype2)
3812           || TYPE_MODE (itype1) != TYPE_MODE (itype2)