OSDN Git Service

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