OSDN Git Service

157d7f2d15a004f35fdfb8472caa92dab4150ddb
[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       abort ();
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   if (code == TREE_VEC || code == PHI_NODE)
232     abort ();
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       abort ();
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 #ifdef ENABLE_CHECKING
370   if (code == STATEMENT_LIST)
371     abort ();
372 #endif
373
374   length = tree_size (node);
375   t = ggc_alloc_zone_stat (length, tree_zone PASS_MEM_STAT);
376   memcpy (t, node, length);
377
378   TREE_CHAIN (t) = 0;
379   TREE_ASM_WRITTEN (t) = 0;
380   TREE_VISITED (t) = 0;
381   t->common.ann = 0;
382
383   if (TREE_CODE_CLASS (code) == 'd')
384     DECL_UID (t) = next_decl_uid++;
385   else if (TREE_CODE_CLASS (code) == 't')
386     {
387       TYPE_UID (t) = next_type_uid++;
388       /* The following is so that the debug code for
389          the copy is different from the original type.
390          The two statements usually duplicate each other
391          (because they clear fields of the same union),
392          but the optimizer should catch that.  */
393       TYPE_SYMTAB_POINTER (t) = 0;
394       TYPE_SYMTAB_ADDRESS (t) = 0;
395       
396       /* Do not copy the values cache.  */
397       if (TYPE_CACHED_VALUES_P(t))
398         {
399           TYPE_CACHED_VALUES_P (t) = 0;
400           TYPE_CACHED_VALUES (t) = NULL_TREE;
401         }
402     }
403
404   return t;
405 }
406
407 /* Return a copy of a chain of nodes, chained through the TREE_CHAIN field.
408    For example, this can copy a list made of TREE_LIST nodes.  */
409
410 tree
411 copy_list (tree list)
412 {
413   tree head;
414   tree prev, next;
415
416   if (list == 0)
417     return 0;
418
419   head = prev = copy_node (list);
420   next = TREE_CHAIN (list);
421   while (next)
422     {
423       TREE_CHAIN (prev) = copy_node (next);
424       prev = TREE_CHAIN (prev);
425       next = TREE_CHAIN (next);
426     }
427   return head;
428 }
429
430 \f
431 /* Create an INT_CST node with a LOW value sign extended.  */
432
433 tree
434 build_int_cst (tree type, HOST_WIDE_INT low)
435 {
436   return build_int_cst_wide (type, low, low < 0 ? -1 : 0);
437 }
438
439 /* Create an INT_CST node with a LOW value zero extended.  */
440
441 tree
442 build_int_cstu (tree type, unsigned HOST_WIDE_INT low)
443 {
444   return build_int_cst_wide (type, low, 0);
445 }
446
447 /* Create an INT_CST node with a LOW value zero or sign extended depending
448    on the type.  */
449
450 tree
451 build_int_cst_type (tree type, HOST_WIDE_INT low)
452 {
453   unsigned HOST_WIDE_INT val = (unsigned HOST_WIDE_INT) low;
454   unsigned bits;
455   bool signed_p;
456   bool negative;
457   tree ret;
458
459   if (!type)
460     type = integer_type_node;
461
462   bits = TYPE_PRECISION (type);
463   signed_p = !TYPE_UNSIGNED (type);
464   negative = ((val >> (bits - 1)) & 1) != 0;
465
466   if (signed_p && negative)
467     {
468       if (bits < HOST_BITS_PER_WIDE_INT)
469         val = val | ((~(unsigned HOST_WIDE_INT) 0) << bits);
470       ret = build_int_cst_wide (type, val, ~(unsigned HOST_WIDE_INT) 0);
471     }
472   else
473     {
474       if (bits < HOST_BITS_PER_WIDE_INT)
475         val = val & ~((~(unsigned HOST_WIDE_INT) 0) << bits);
476       ret = build_int_cst_wide (type, val, 0);
477     }
478
479   return ret;
480 }
481
482 /* Create an INT_CST node of TYPE and value HI:LOW.  If TYPE is NULL,
483    integer_type_node is used.  */
484
485 tree
486 build_int_cst_wide (tree type, unsigned HOST_WIDE_INT low, HOST_WIDE_INT hi)
487 {
488   tree t;
489   int ix = -1;
490   int limit = 0;
491
492   if (!type)
493     type = integer_type_node;
494
495   switch (TREE_CODE (type))
496     {
497     case POINTER_TYPE:
498     case REFERENCE_TYPE:
499       /* Cache NULL pointer.  */
500       if (!hi && !low)
501         {
502           limit = 1;
503           ix = 0;
504         }
505       break;
506
507     case BOOLEAN_TYPE:
508       /* Cache false or true.  */
509       limit = 2;
510       if (!hi && low < 2)
511         ix = low;
512       break;
513
514     case INTEGER_TYPE:
515     case CHAR_TYPE:
516     case OFFSET_TYPE:
517       if (TYPE_UNSIGNED (type))
518         {
519           /* Cache 0..N */
520           limit = INTEGER_SHARE_LIMIT;
521           if (!hi && low < (unsigned HOST_WIDE_INT)INTEGER_SHARE_LIMIT)
522             ix = low;
523         }
524       else
525         {
526           /* Cache -1..N */
527           limit = INTEGER_SHARE_LIMIT + 1;
528           if (!hi && low < (unsigned HOST_WIDE_INT)INTEGER_SHARE_LIMIT)
529             ix = low + 1;
530           else if (hi == -1 && low == -(unsigned HOST_WIDE_INT)1)
531             ix = 0;
532         }
533       break;
534     default:
535       break;
536     }
537
538   if (ix >= 0)
539     {
540       if (!TYPE_CACHED_VALUES_P (type))
541         {
542           TYPE_CACHED_VALUES_P (type) = 1;
543           TYPE_CACHED_VALUES (type) = make_tree_vec (limit);
544         }
545
546       t = TREE_VEC_ELT (TYPE_CACHED_VALUES (type), ix);
547       if (t)
548         {
549           /* Make sure no one is clobbering the shared constant.  */
550           if (TREE_TYPE (t) != type)
551             abort ();
552           if (TREE_INT_CST_LOW (t) != low || TREE_INT_CST_HIGH (t) != hi)
553             abort ();
554           return t;
555         }
556     }
557
558   t = make_node (INTEGER_CST);
559
560   TREE_INT_CST_LOW (t) = low;
561   TREE_INT_CST_HIGH (t) = hi;
562   TREE_TYPE (t) = type;
563
564   if (ix >= 0)
565     TREE_VEC_ELT (TYPE_CACHED_VALUES (type), ix) = t;
566
567   return t;
568 }
569
570 /* Checks that X is integer constant that can be expressed in (unsigned)
571    HOST_WIDE_INT without loss of precision.  */
572
573 bool
574 cst_and_fits_in_hwi (tree x)
575 {
576   if (TREE_CODE (x) != INTEGER_CST)
577     return false;
578
579   if (TYPE_PRECISION (TREE_TYPE (x)) > HOST_BITS_PER_WIDE_INT)
580     return false;
581
582   return (TREE_INT_CST_HIGH (x) == 0
583           || TREE_INT_CST_HIGH (x) == -1);
584 }
585
586 /* Return a new VECTOR_CST node whose type is TYPE and whose values
587    are in a list pointed by VALS.  */
588
589 tree
590 build_vector (tree type, tree vals)
591 {
592   tree v = make_node (VECTOR_CST);
593   int over1 = 0, over2 = 0;
594   tree link;
595
596   TREE_VECTOR_CST_ELTS (v) = vals;
597   TREE_TYPE (v) = type;
598
599   /* Iterate through elements and check for overflow.  */
600   for (link = vals; link; link = TREE_CHAIN (link))
601     {
602       tree value = TREE_VALUE (link);
603
604       over1 |= TREE_OVERFLOW (value);
605       over2 |= TREE_CONSTANT_OVERFLOW (value);
606     }
607
608   TREE_OVERFLOW (v) = over1;
609   TREE_CONSTANT_OVERFLOW (v) = over2;
610
611   return v;
612 }
613
614 /* Return a new CONSTRUCTOR node whose type is TYPE and whose values
615    are in a list pointed to by VALS.  */
616 tree
617 build_constructor (tree type, tree vals)
618 {
619   tree c = make_node (CONSTRUCTOR);
620   TREE_TYPE (c) = type;
621   CONSTRUCTOR_ELTS (c) = vals;
622
623   /* ??? May not be necessary.  Mirrors what build does.  */
624   if (vals)
625     {
626       TREE_SIDE_EFFECTS (c) = TREE_SIDE_EFFECTS (vals);
627       TREE_READONLY (c) = TREE_READONLY (vals);
628       TREE_CONSTANT (c) = TREE_CONSTANT (vals);
629       TREE_INVARIANT (c) = TREE_INVARIANT (vals);
630     }
631
632   return c;
633 }
634
635 /* Return a new REAL_CST node whose type is TYPE and value is D.  */
636
637 tree
638 build_real (tree type, REAL_VALUE_TYPE d)
639 {
640   tree v;
641   REAL_VALUE_TYPE *dp;
642   int overflow = 0;
643
644   /* ??? Used to check for overflow here via CHECK_FLOAT_TYPE.
645      Consider doing it via real_convert now.  */
646
647   v = make_node (REAL_CST);
648   dp = ggc_alloc (sizeof (REAL_VALUE_TYPE));
649   memcpy (dp, &d, sizeof (REAL_VALUE_TYPE));
650
651   TREE_TYPE (v) = type;
652   TREE_REAL_CST_PTR (v) = dp;
653   TREE_OVERFLOW (v) = TREE_CONSTANT_OVERFLOW (v) = overflow;
654   return v;
655 }
656
657 /* Return a new REAL_CST node whose type is TYPE
658    and whose value is the integer value of the INTEGER_CST node I.  */
659
660 REAL_VALUE_TYPE
661 real_value_from_int_cst (tree type, tree i)
662 {
663   REAL_VALUE_TYPE d;
664
665   /* Clear all bits of the real value type so that we can later do
666      bitwise comparisons to see if two values are the same.  */
667   memset (&d, 0, sizeof d);
668
669   real_from_integer (&d, type ? TYPE_MODE (type) : VOIDmode,
670                      TREE_INT_CST_LOW (i), TREE_INT_CST_HIGH (i),
671                      TYPE_UNSIGNED (TREE_TYPE (i)));
672   return d;
673 }
674
675 /* Given a tree representing an integer constant I, return a tree
676    representing the same value as a floating-point constant of type TYPE.  */
677
678 tree
679 build_real_from_int_cst (tree type, tree i)
680 {
681   tree v;
682   int overflow = TREE_OVERFLOW (i);
683
684   v = build_real (type, real_value_from_int_cst (type, i));
685
686   TREE_OVERFLOW (v) |= overflow;
687   TREE_CONSTANT_OVERFLOW (v) |= overflow;
688   return v;
689 }
690
691 /* Return a newly constructed STRING_CST node whose value is
692    the LEN characters at STR.
693    The TREE_TYPE is not initialized.  */
694
695 tree
696 build_string (int len, const char *str)
697 {
698   tree s = make_node (STRING_CST);
699
700   TREE_STRING_LENGTH (s) = len;
701   TREE_STRING_POINTER (s) = ggc_alloc_string (str, len);
702
703   return s;
704 }
705
706 /* Return a newly constructed COMPLEX_CST node whose value is
707    specified by the real and imaginary parts REAL and IMAG.
708    Both REAL and IMAG should be constant nodes.  TYPE, if specified,
709    will be the type of the COMPLEX_CST; otherwise a new type will be made.  */
710
711 tree
712 build_complex (tree type, tree real, tree imag)
713 {
714   tree t = make_node (COMPLEX_CST);
715
716   TREE_REALPART (t) = real;
717   TREE_IMAGPART (t) = imag;
718   TREE_TYPE (t) = type ? type : build_complex_type (TREE_TYPE (real));
719   TREE_OVERFLOW (t) = TREE_OVERFLOW (real) | TREE_OVERFLOW (imag);
720   TREE_CONSTANT_OVERFLOW (t)
721     = TREE_CONSTANT_OVERFLOW (real) | TREE_CONSTANT_OVERFLOW (imag);
722   return t;
723 }
724
725 /* Build a BINFO with LEN language slots.  */
726
727 tree
728 make_tree_binfo_stat (unsigned base_binfos MEM_STAT_DECL)
729 {
730   tree t;
731   size_t length = (offsetof (struct tree_binfo, base_binfos)
732                    + VEC_embedded_size (tree, base_binfos));
733
734 #ifdef GATHER_STATISTICS
735   tree_node_counts[(int) binfo_kind]++;
736   tree_node_sizes[(int) binfo_kind] += length;
737 #endif
738
739   t = ggc_alloc_zone_stat (length, tree_zone PASS_MEM_STAT);
740
741   memset (t, 0, offsetof (struct tree_binfo, base_binfos));
742
743   TREE_SET_CODE (t, TREE_BINFO);
744
745   VEC_embedded_init (tree, BINFO_BASE_BINFOS (t), base_binfos);
746
747   return t;
748 }
749
750
751 /* Build a newly constructed TREE_VEC node of length LEN.  */
752
753 tree
754 make_tree_vec_stat (int len MEM_STAT_DECL)
755 {
756   tree t;
757   int length = (len - 1) * sizeof (tree) + sizeof (struct tree_vec);
758
759 #ifdef GATHER_STATISTICS
760   tree_node_counts[(int) vec_kind]++;
761   tree_node_sizes[(int) vec_kind] += length;
762 #endif
763
764   t = ggc_alloc_zone_stat (length, tree_zone PASS_MEM_STAT);
765
766   memset (t, 0, length);
767
768   TREE_SET_CODE (t, TREE_VEC);
769   TREE_VEC_LENGTH (t) = len;
770
771   return t;
772 }
773 \f
774 /* Return 1 if EXPR is the integer constant zero or a complex constant
775    of zero.  */
776
777 int
778 integer_zerop (tree expr)
779 {
780   STRIP_NOPS (expr);
781
782   return ((TREE_CODE (expr) == INTEGER_CST
783            && ! TREE_CONSTANT_OVERFLOW (expr)
784            && TREE_INT_CST_LOW (expr) == 0
785            && TREE_INT_CST_HIGH (expr) == 0)
786           || (TREE_CODE (expr) == COMPLEX_CST
787               && integer_zerop (TREE_REALPART (expr))
788               && integer_zerop (TREE_IMAGPART (expr))));
789 }
790
791 /* Return 1 if EXPR is the integer constant one or the corresponding
792    complex constant.  */
793
794 int
795 integer_onep (tree expr)
796 {
797   STRIP_NOPS (expr);
798
799   return ((TREE_CODE (expr) == INTEGER_CST
800            && ! TREE_CONSTANT_OVERFLOW (expr)
801            && TREE_INT_CST_LOW (expr) == 1
802            && TREE_INT_CST_HIGH (expr) == 0)
803           || (TREE_CODE (expr) == COMPLEX_CST
804               && integer_onep (TREE_REALPART (expr))
805               && integer_zerop (TREE_IMAGPART (expr))));
806 }
807
808 /* Return 1 if EXPR is an integer containing all 1's in as much precision as
809    it contains.  Likewise for the corresponding complex constant.  */
810
811 int
812 integer_all_onesp (tree expr)
813 {
814   int prec;
815   int uns;
816
817   STRIP_NOPS (expr);
818
819   if (TREE_CODE (expr) == COMPLEX_CST
820       && integer_all_onesp (TREE_REALPART (expr))
821       && integer_zerop (TREE_IMAGPART (expr)))
822     return 1;
823
824   else if (TREE_CODE (expr) != INTEGER_CST
825            || TREE_CONSTANT_OVERFLOW (expr))
826     return 0;
827
828   uns = TYPE_UNSIGNED (TREE_TYPE (expr));
829   if (!uns)
830     return (TREE_INT_CST_LOW (expr) == ~(unsigned HOST_WIDE_INT) 0
831             && TREE_INT_CST_HIGH (expr) == -1);
832
833   /* Note that using TYPE_PRECISION here is wrong.  We care about the
834      actual bits, not the (arbitrary) range of the type.  */
835   prec = GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (expr)));
836   if (prec >= HOST_BITS_PER_WIDE_INT)
837     {
838       HOST_WIDE_INT high_value;
839       int shift_amount;
840
841       shift_amount = prec - HOST_BITS_PER_WIDE_INT;
842
843       if (shift_amount > HOST_BITS_PER_WIDE_INT)
844         /* Can not handle precisions greater than twice the host int size.  */
845         abort ();
846       else if (shift_amount == HOST_BITS_PER_WIDE_INT)
847         /* Shifting by the host word size is undefined according to the ANSI
848            standard, so we must handle this as a special case.  */
849         high_value = -1;
850       else
851         high_value = ((HOST_WIDE_INT) 1 << shift_amount) - 1;
852
853       return (TREE_INT_CST_LOW (expr) == ~(unsigned HOST_WIDE_INT) 0
854               && TREE_INT_CST_HIGH (expr) == high_value);
855     }
856   else
857     return TREE_INT_CST_LOW (expr) == ((unsigned HOST_WIDE_INT) 1 << prec) - 1;
858 }
859
860 /* Return 1 if EXPR is an integer constant that is a power of 2 (i.e., has only
861    one bit on).  */
862
863 int
864 integer_pow2p (tree expr)
865 {
866   int prec;
867   HOST_WIDE_INT high, low;
868
869   STRIP_NOPS (expr);
870
871   if (TREE_CODE (expr) == COMPLEX_CST
872       && integer_pow2p (TREE_REALPART (expr))
873       && integer_zerop (TREE_IMAGPART (expr)))
874     return 1;
875
876   if (TREE_CODE (expr) != INTEGER_CST || TREE_CONSTANT_OVERFLOW (expr))
877     return 0;
878
879   prec = (POINTER_TYPE_P (TREE_TYPE (expr))
880           ? POINTER_SIZE : TYPE_PRECISION (TREE_TYPE (expr)));
881   high = TREE_INT_CST_HIGH (expr);
882   low = TREE_INT_CST_LOW (expr);
883
884   /* First clear all bits that are beyond the type's precision in case
885      we've been sign extended.  */
886
887   if (prec == 2 * HOST_BITS_PER_WIDE_INT)
888     ;
889   else if (prec > HOST_BITS_PER_WIDE_INT)
890     high &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
891   else
892     {
893       high = 0;
894       if (prec < HOST_BITS_PER_WIDE_INT)
895         low &= ~((HOST_WIDE_INT) (-1) << prec);
896     }
897
898   if (high == 0 && low == 0)
899     return 0;
900
901   return ((high == 0 && (low & (low - 1)) == 0)
902           || (low == 0 && (high & (high - 1)) == 0));
903 }
904
905 /* Return 1 if EXPR is an integer constant other than zero or a
906    complex constant other than zero.  */
907
908 int
909 integer_nonzerop (tree expr)
910 {
911   STRIP_NOPS (expr);
912
913   return ((TREE_CODE (expr) == INTEGER_CST
914            && ! TREE_CONSTANT_OVERFLOW (expr)
915            && (TREE_INT_CST_LOW (expr) != 0
916                || TREE_INT_CST_HIGH (expr) != 0))
917           || (TREE_CODE (expr) == COMPLEX_CST
918               && (integer_nonzerop (TREE_REALPART (expr))
919                   || integer_nonzerop (TREE_IMAGPART (expr)))));
920 }
921
922 /* Return the power of two represented by a tree node known to be a
923    power of two.  */
924
925 int
926 tree_log2 (tree expr)
927 {
928   int prec;
929   HOST_WIDE_INT high, low;
930
931   STRIP_NOPS (expr);
932
933   if (TREE_CODE (expr) == COMPLEX_CST)
934     return tree_log2 (TREE_REALPART (expr));
935
936   prec = (POINTER_TYPE_P (TREE_TYPE (expr))
937           ? POINTER_SIZE : TYPE_PRECISION (TREE_TYPE (expr)));
938
939   high = TREE_INT_CST_HIGH (expr);
940   low = TREE_INT_CST_LOW (expr);
941
942   /* First clear all bits that are beyond the type's precision in case
943      we've been sign extended.  */
944
945   if (prec == 2 * HOST_BITS_PER_WIDE_INT)
946     ;
947   else if (prec > HOST_BITS_PER_WIDE_INT)
948     high &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
949   else
950     {
951       high = 0;
952       if (prec < HOST_BITS_PER_WIDE_INT)
953         low &= ~((HOST_WIDE_INT) (-1) << prec);
954     }
955
956   return (high != 0 ? HOST_BITS_PER_WIDE_INT + exact_log2 (high)
957           : exact_log2 (low));
958 }
959
960 /* Similar, but return the largest integer Y such that 2 ** Y is less
961    than or equal to EXPR.  */
962
963 int
964 tree_floor_log2 (tree expr)
965 {
966   int prec;
967   HOST_WIDE_INT high, low;
968
969   STRIP_NOPS (expr);
970
971   if (TREE_CODE (expr) == COMPLEX_CST)
972     return tree_log2 (TREE_REALPART (expr));
973
974   prec = (POINTER_TYPE_P (TREE_TYPE (expr))
975           ? POINTER_SIZE : TYPE_PRECISION (TREE_TYPE (expr)));
976
977   high = TREE_INT_CST_HIGH (expr);
978   low = TREE_INT_CST_LOW (expr);
979
980   /* First clear all bits that are beyond the type's precision in case
981      we've been sign extended.  Ignore if type's precision hasn't been set
982      since what we are doing is setting it.  */
983
984   if (prec == 2 * HOST_BITS_PER_WIDE_INT || prec == 0)
985     ;
986   else if (prec > HOST_BITS_PER_WIDE_INT)
987     high &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
988   else
989     {
990       high = 0;
991       if (prec < HOST_BITS_PER_WIDE_INT)
992         low &= ~((HOST_WIDE_INT) (-1) << prec);
993     }
994
995   return (high != 0 ? HOST_BITS_PER_WIDE_INT + floor_log2 (high)
996           : floor_log2 (low));
997 }
998
999 /* Return 1 if EXPR is the real constant zero.  */
1000
1001 int
1002 real_zerop (tree expr)
1003 {
1004   STRIP_NOPS (expr);
1005
1006   return ((TREE_CODE (expr) == REAL_CST
1007            && ! TREE_CONSTANT_OVERFLOW (expr)
1008            && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconst0))
1009           || (TREE_CODE (expr) == COMPLEX_CST
1010               && real_zerop (TREE_REALPART (expr))
1011               && real_zerop (TREE_IMAGPART (expr))));
1012 }
1013
1014 /* Return 1 if EXPR is the real constant one in real or complex form.  */
1015
1016 int
1017 real_onep (tree expr)
1018 {
1019   STRIP_NOPS (expr);
1020
1021   return ((TREE_CODE (expr) == REAL_CST
1022            && ! TREE_CONSTANT_OVERFLOW (expr)
1023            && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconst1))
1024           || (TREE_CODE (expr) == COMPLEX_CST
1025               && real_onep (TREE_REALPART (expr))
1026               && real_zerop (TREE_IMAGPART (expr))));
1027 }
1028
1029 /* Return 1 if EXPR is the real constant two.  */
1030
1031 int
1032 real_twop (tree expr)
1033 {
1034   STRIP_NOPS (expr);
1035
1036   return ((TREE_CODE (expr) == REAL_CST
1037            && ! TREE_CONSTANT_OVERFLOW (expr)
1038            && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconst2))
1039           || (TREE_CODE (expr) == COMPLEX_CST
1040               && real_twop (TREE_REALPART (expr))
1041               && real_zerop (TREE_IMAGPART (expr))));
1042 }
1043
1044 /* Return 1 if EXPR is the real constant minus one.  */
1045
1046 int
1047 real_minus_onep (tree expr)
1048 {
1049   STRIP_NOPS (expr);
1050
1051   return ((TREE_CODE (expr) == REAL_CST
1052            && ! TREE_CONSTANT_OVERFLOW (expr)
1053            && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconstm1))
1054           || (TREE_CODE (expr) == COMPLEX_CST
1055               && real_minus_onep (TREE_REALPART (expr))
1056               && real_zerop (TREE_IMAGPART (expr))));
1057 }
1058
1059 /* Nonzero if EXP is a constant or a cast of a constant.  */
1060
1061 int
1062 really_constant_p (tree exp)
1063 {
1064   /* This is not quite the same as STRIP_NOPS.  It does more.  */
1065   while (TREE_CODE (exp) == NOP_EXPR
1066          || TREE_CODE (exp) == CONVERT_EXPR
1067          || TREE_CODE (exp) == NON_LVALUE_EXPR)
1068     exp = TREE_OPERAND (exp, 0);
1069   return TREE_CONSTANT (exp);
1070 }
1071 \f
1072 /* Return first list element whose TREE_VALUE is ELEM.
1073    Return 0 if ELEM is not in LIST.  */
1074
1075 tree
1076 value_member (tree elem, tree list)
1077 {
1078   while (list)
1079     {
1080       if (elem == TREE_VALUE (list))
1081         return list;
1082       list = TREE_CHAIN (list);
1083     }
1084   return NULL_TREE;
1085 }
1086
1087 /* Return first list element whose TREE_PURPOSE is ELEM.
1088    Return 0 if ELEM is not in LIST.  */
1089
1090 tree
1091 purpose_member (tree elem, tree list)
1092 {
1093   while (list)
1094     {
1095       if (elem == TREE_PURPOSE (list))
1096         return list;
1097       list = TREE_CHAIN (list);
1098     }
1099   return NULL_TREE;
1100 }
1101
1102 /* Return nonzero if ELEM is part of the chain CHAIN.  */
1103
1104 int
1105 chain_member (tree elem, tree chain)
1106 {
1107   while (chain)
1108     {
1109       if (elem == chain)
1110         return 1;
1111       chain = TREE_CHAIN (chain);
1112     }
1113
1114   return 0;
1115 }
1116
1117 /* Return the length of a chain of nodes chained through TREE_CHAIN.
1118    We expect a null pointer to mark the end of the chain.
1119    This is the Lisp primitive `length'.  */
1120
1121 int
1122 list_length (tree t)
1123 {
1124   tree p = t;
1125 #ifdef ENABLE_TREE_CHECKING
1126   tree q = t;
1127 #endif
1128   int len = 0;
1129
1130   while (p)
1131     {
1132       p = TREE_CHAIN (p);
1133 #ifdef ENABLE_TREE_CHECKING
1134       if (len % 2)
1135         q = TREE_CHAIN (q);
1136       if (p == q)
1137         abort ();
1138 #endif
1139       len++;
1140     }
1141
1142   return len;
1143 }
1144
1145 /* Returns the number of FIELD_DECLs in TYPE.  */
1146
1147 int
1148 fields_length (tree type)
1149 {
1150   tree t = TYPE_FIELDS (type);
1151   int count = 0;
1152
1153   for (; t; t = TREE_CHAIN (t))
1154     if (TREE_CODE (t) == FIELD_DECL)
1155       ++count;
1156
1157   return count;
1158 }
1159
1160 /* Concatenate two chains of nodes (chained through TREE_CHAIN)
1161    by modifying the last node in chain 1 to point to chain 2.
1162    This is the Lisp primitive `nconc'.  */
1163
1164 tree
1165 chainon (tree op1, tree op2)
1166 {
1167   tree t1;
1168
1169   if (!op1)
1170     return op2;
1171   if (!op2)
1172     return op1;
1173
1174   for (t1 = op1; TREE_CHAIN (t1); t1 = TREE_CHAIN (t1))
1175     continue;
1176   TREE_CHAIN (t1) = op2;
1177
1178 #ifdef ENABLE_TREE_CHECKING
1179   {
1180     tree t2;
1181     for (t2 = op2; t2; t2 = TREE_CHAIN (t2))
1182       if (t2 == t1)
1183         abort ();  /* Circularity created.  */
1184   }
1185 #endif
1186
1187   return op1;
1188 }
1189
1190 /* Return the last node in a chain of nodes (chained through TREE_CHAIN).  */
1191
1192 tree
1193 tree_last (tree chain)
1194 {
1195   tree next;
1196   if (chain)
1197     while ((next = TREE_CHAIN (chain)))
1198       chain = next;
1199   return chain;
1200 }
1201
1202 /* Reverse the order of elements in the chain T,
1203    and return the new head of the chain (old last element).  */
1204
1205 tree
1206 nreverse (tree t)
1207 {
1208   tree prev = 0, decl, next;
1209   for (decl = t; decl; decl = next)
1210     {
1211       next = TREE_CHAIN (decl);
1212       TREE_CHAIN (decl) = prev;
1213       prev = decl;
1214     }
1215   return prev;
1216 }
1217 \f
1218 /* Return a newly created TREE_LIST node whose
1219    purpose and value fields are PARM and VALUE.  */
1220
1221 tree
1222 build_tree_list_stat (tree parm, tree value MEM_STAT_DECL)
1223 {
1224   tree t = make_node_stat (TREE_LIST PASS_MEM_STAT);
1225   TREE_PURPOSE (t) = parm;
1226   TREE_VALUE (t) = value;
1227   return t;
1228 }
1229
1230 /* Return a newly created TREE_LIST node whose
1231    purpose and value fields are PURPOSE and VALUE
1232    and whose TREE_CHAIN is CHAIN.  */
1233
1234 tree
1235 tree_cons_stat (tree purpose, tree value, tree chain MEM_STAT_DECL)
1236 {
1237   tree node;
1238
1239   node = ggc_alloc_zone_stat (sizeof (struct tree_list),
1240                               tree_zone PASS_MEM_STAT);
1241
1242   memset (node, 0, sizeof (struct tree_common));
1243
1244 #ifdef GATHER_STATISTICS
1245   tree_node_counts[(int) x_kind]++;
1246   tree_node_sizes[(int) x_kind] += sizeof (struct tree_list);
1247 #endif
1248
1249   TREE_SET_CODE (node, TREE_LIST);
1250   TREE_CHAIN (node) = chain;
1251   TREE_PURPOSE (node) = purpose;
1252   TREE_VALUE (node) = value;
1253   return node;
1254 }
1255
1256 \f
1257 /* Return the size nominally occupied by an object of type TYPE
1258    when it resides in memory.  The value is measured in units of bytes,
1259    and its data type is that normally used for type sizes
1260    (which is the first type created by make_signed_type or
1261    make_unsigned_type).  */
1262
1263 tree
1264 size_in_bytes (tree type)
1265 {
1266   tree t;
1267
1268   if (type == error_mark_node)
1269     return integer_zero_node;
1270
1271   type = TYPE_MAIN_VARIANT (type);
1272   t = TYPE_SIZE_UNIT (type);
1273
1274   if (t == 0)
1275     {
1276       lang_hooks.types.incomplete_type_error (NULL_TREE, type);
1277       return size_zero_node;
1278     }
1279
1280   if (TREE_CODE (t) == INTEGER_CST)
1281     t = force_fit_type (t, 0, false, false);
1282
1283   return t;
1284 }
1285
1286 /* Return the size of TYPE (in bytes) as a wide integer
1287    or return -1 if the size can vary or is larger than an integer.  */
1288
1289 HOST_WIDE_INT
1290 int_size_in_bytes (tree type)
1291 {
1292   tree t;
1293
1294   if (type == error_mark_node)
1295     return 0;
1296
1297   type = TYPE_MAIN_VARIANT (type);
1298   t = TYPE_SIZE_UNIT (type);
1299   if (t == 0
1300       || TREE_CODE (t) != INTEGER_CST
1301       || TREE_OVERFLOW (t)
1302       || TREE_INT_CST_HIGH (t) != 0
1303       /* If the result would appear negative, it's too big to represent.  */
1304       || (HOST_WIDE_INT) TREE_INT_CST_LOW (t) < 0)
1305     return -1;
1306
1307   return TREE_INT_CST_LOW (t);
1308 }
1309 \f
1310 /* Return the bit position of FIELD, in bits from the start of the record.
1311    This is a tree of type bitsizetype.  */
1312
1313 tree
1314 bit_position (tree field)
1315 {
1316   return bit_from_pos (DECL_FIELD_OFFSET (field),
1317                        DECL_FIELD_BIT_OFFSET (field));
1318 }
1319
1320 /* Likewise, but return as an integer.  Abort if it cannot be represented
1321    in that way (since it could be a signed value, we don't have the option
1322    of returning -1 like int_size_in_byte can.  */
1323
1324 HOST_WIDE_INT
1325 int_bit_position (tree field)
1326 {
1327   return tree_low_cst (bit_position (field), 0);
1328 }
1329 \f
1330 /* Return the byte position of FIELD, in bytes from the start of the record.
1331    This is a tree of type sizetype.  */
1332
1333 tree
1334 byte_position (tree field)
1335 {
1336   return byte_from_pos (DECL_FIELD_OFFSET (field),
1337                         DECL_FIELD_BIT_OFFSET (field));
1338 }
1339
1340 /* Likewise, but return as an integer.  Abort if it cannot be represented
1341    in that way (since it could be a signed value, we don't have the option
1342    of returning -1 like int_size_in_byte can.  */
1343
1344 HOST_WIDE_INT
1345 int_byte_position (tree field)
1346 {
1347   return tree_low_cst (byte_position (field), 0);
1348 }
1349 \f
1350 /* Return the strictest alignment, in bits, that T is known to have.  */
1351
1352 unsigned int
1353 expr_align (tree t)
1354 {
1355   unsigned int align0, align1;
1356
1357   switch (TREE_CODE (t))
1358     {
1359     case NOP_EXPR:  case CONVERT_EXPR:  case NON_LVALUE_EXPR:
1360       /* If we have conversions, we know that the alignment of the
1361          object must meet each of the alignments of the types.  */
1362       align0 = expr_align (TREE_OPERAND (t, 0));
1363       align1 = TYPE_ALIGN (TREE_TYPE (t));
1364       return MAX (align0, align1);
1365
1366     case SAVE_EXPR:         case COMPOUND_EXPR:       case MODIFY_EXPR:
1367     case INIT_EXPR:         case TARGET_EXPR:         case WITH_CLEANUP_EXPR:
1368     case CLEANUP_POINT_EXPR:
1369       /* These don't change the alignment of an object.  */
1370       return expr_align (TREE_OPERAND (t, 0));
1371
1372     case COND_EXPR:
1373       /* The best we can do is say that the alignment is the least aligned
1374          of the two arms.  */
1375       align0 = expr_align (TREE_OPERAND (t, 1));
1376       align1 = expr_align (TREE_OPERAND (t, 2));
1377       return MIN (align0, align1);
1378
1379     case LABEL_DECL:     case CONST_DECL:
1380     case VAR_DECL:       case PARM_DECL:   case RESULT_DECL:
1381       if (DECL_ALIGN (t) != 0)
1382         return DECL_ALIGN (t);
1383       break;
1384
1385     case FUNCTION_DECL:
1386       return FUNCTION_BOUNDARY;
1387
1388     default:
1389       break;
1390     }
1391
1392   /* Otherwise take the alignment from that of the type.  */
1393   return TYPE_ALIGN (TREE_TYPE (t));
1394 }
1395 \f
1396 /* Return, as a tree node, the number of elements for TYPE (which is an
1397    ARRAY_TYPE) minus one. This counts only elements of the top array.  */
1398
1399 tree
1400 array_type_nelts (tree type)
1401 {
1402   tree index_type, min, max;
1403
1404   /* If they did it with unspecified bounds, then we should have already
1405      given an error about it before we got here.  */
1406   if (! TYPE_DOMAIN (type))
1407     return error_mark_node;
1408
1409   index_type = TYPE_DOMAIN (type);
1410   min = TYPE_MIN_VALUE (index_type);
1411   max = TYPE_MAX_VALUE (index_type);
1412
1413   return (integer_zerop (min)
1414           ? max
1415           : fold (build2 (MINUS_EXPR, TREE_TYPE (max), max, min)));
1416 }
1417 \f
1418 /* If arg is static -- a reference to an object in static storage -- then
1419    return the object.  This is not the same as the C meaning of `static'.
1420    If arg isn't static, return NULL.  */
1421
1422 tree
1423 staticp (tree arg)
1424 {
1425   switch (TREE_CODE (arg))
1426     {
1427     case FUNCTION_DECL:
1428       /* Nested functions aren't static, since taking their address
1429          involves a trampoline.  */
1430       return ((decl_function_context (arg) == 0 || DECL_NO_STATIC_CHAIN (arg))
1431               && ! DECL_NON_ADDR_CONST_P (arg)
1432               ? arg : NULL);
1433
1434     case VAR_DECL:
1435       return ((TREE_STATIC (arg) || DECL_EXTERNAL (arg))
1436               && ! DECL_THREAD_LOCAL (arg)
1437               && ! DECL_NON_ADDR_CONST_P (arg)
1438               ? arg : NULL);
1439
1440     case CONSTRUCTOR:
1441       return TREE_STATIC (arg) ? arg : NULL;
1442
1443     case LABEL_DECL:
1444     case STRING_CST:
1445       return arg;
1446
1447     case COMPONENT_REF:
1448       /* If the thing being referenced is not a field, then it is
1449          something language specific.  */
1450       if (TREE_CODE (TREE_OPERAND (arg, 1)) != FIELD_DECL)
1451         return (*lang_hooks.staticp) (arg);
1452
1453       /* If we are referencing a bitfield, we can't evaluate an
1454          ADDR_EXPR at compile time and so it isn't a constant.  */
1455       if (DECL_BIT_FIELD (TREE_OPERAND (arg, 1)))
1456         return NULL;
1457
1458       return staticp (TREE_OPERAND (arg, 0));
1459
1460     case BIT_FIELD_REF:
1461       return NULL;
1462
1463     case INDIRECT_REF:
1464       return TREE_CONSTANT (TREE_OPERAND (arg, 0)) ? arg : NULL;
1465
1466     case ARRAY_REF:
1467     case ARRAY_RANGE_REF:
1468       if (TREE_CODE (TYPE_SIZE (TREE_TYPE (arg))) == INTEGER_CST
1469           && TREE_CODE (TREE_OPERAND (arg, 1)) == INTEGER_CST)
1470         return staticp (TREE_OPERAND (arg, 0));
1471       else
1472         return false;
1473
1474     default:
1475       if ((unsigned int) TREE_CODE (arg)
1476           >= (unsigned int) LAST_AND_UNUSED_TREE_CODE)
1477         return lang_hooks.staticp (arg);
1478       else
1479         return NULL;
1480     }
1481 }
1482 \f
1483 /* Wrap a SAVE_EXPR around EXPR, if appropriate.
1484    Do this to any expression which may be used in more than one place,
1485    but must be evaluated only once.
1486
1487    Normally, expand_expr would reevaluate the expression each time.
1488    Calling save_expr produces something that is evaluated and recorded
1489    the first time expand_expr is called on it.  Subsequent calls to
1490    expand_expr just reuse the recorded value.
1491
1492    The call to expand_expr that generates code that actually computes
1493    the value is the first call *at compile time*.  Subsequent calls
1494    *at compile time* generate code to use the saved value.
1495    This produces correct result provided that *at run time* control
1496    always flows through the insns made by the first expand_expr
1497    before reaching the other places where the save_expr was evaluated.
1498    You, the caller of save_expr, must make sure this is so.
1499
1500    Constants, and certain read-only nodes, are returned with no
1501    SAVE_EXPR because that is safe.  Expressions containing placeholders
1502    are not touched; see tree.def for an explanation of what these
1503    are used for.  */
1504
1505 tree
1506 save_expr (tree expr)
1507 {
1508   tree t = fold (expr);
1509   tree inner;
1510
1511   /* If the tree evaluates to a constant, then we don't want to hide that
1512      fact (i.e. this allows further folding, and direct checks for constants).
1513      However, a read-only object that has side effects cannot be bypassed.
1514      Since it is no problem to reevaluate literals, we just return the
1515      literal node.  */
1516   inner = skip_simple_arithmetic (t);
1517
1518   if (TREE_INVARIANT (inner)
1519       || (TREE_READONLY (inner) && ! TREE_SIDE_EFFECTS (inner))
1520       || TREE_CODE (inner) == SAVE_EXPR
1521       || TREE_CODE (inner) == ERROR_MARK)
1522     return t;
1523
1524   /* If INNER contains a PLACEHOLDER_EXPR, we must evaluate it each time, since
1525      it means that the size or offset of some field of an object depends on
1526      the value within another field.
1527
1528      Note that it must not be the case that T contains both a PLACEHOLDER_EXPR
1529      and some variable since it would then need to be both evaluated once and
1530      evaluated more than once.  Front-ends must assure this case cannot
1531      happen by surrounding any such subexpressions in their own SAVE_EXPR
1532      and forcing evaluation at the proper time.  */
1533   if (contains_placeholder_p (inner))
1534     return t;
1535
1536   t = build1 (SAVE_EXPR, TREE_TYPE (expr), t);
1537
1538   /* This expression might be placed ahead of a jump to ensure that the
1539      value was computed on both sides of the jump.  So make sure it isn't
1540      eliminated as dead.  */
1541   TREE_SIDE_EFFECTS (t) = 1;
1542   TREE_INVARIANT (t) = 1;
1543   return t;
1544 }
1545
1546 /* Look inside EXPR and into any simple arithmetic operations.  Return
1547    the innermost non-arithmetic node.  */
1548
1549 tree
1550 skip_simple_arithmetic (tree expr)
1551 {
1552   tree inner;
1553
1554   /* We don't care about whether this can be used as an lvalue in this
1555      context.  */
1556   while (TREE_CODE (expr) == NON_LVALUE_EXPR)
1557     expr = TREE_OPERAND (expr, 0);
1558
1559   /* If we have simple operations applied to a SAVE_EXPR or to a SAVE_EXPR and
1560      a constant, it will be more efficient to not make another SAVE_EXPR since
1561      it will allow better simplification and GCSE will be able to merge the
1562      computations if they actually occur.  */
1563   inner = expr;
1564   while (1)
1565     {
1566       if (TREE_CODE_CLASS (TREE_CODE (inner)) == '1')
1567         inner = TREE_OPERAND (inner, 0);
1568       else if (TREE_CODE_CLASS (TREE_CODE (inner)) == '2')
1569         {
1570           if (TREE_INVARIANT (TREE_OPERAND (inner, 1)))
1571             inner = TREE_OPERAND (inner, 0);
1572           else if (TREE_INVARIANT (TREE_OPERAND (inner, 0)))
1573             inner = TREE_OPERAND (inner, 1);
1574           else
1575             break;
1576         }
1577       else
1578         break;
1579     }
1580
1581   return inner;
1582 }
1583
1584 /* Returns the index of the first non-tree operand for CODE, or the number
1585    of operands if all are trees.  */
1586
1587 int
1588 first_rtl_op (enum tree_code code)
1589 {
1590   switch (code)
1591     {
1592     default:
1593       return TREE_CODE_LENGTH (code);
1594     }
1595 }
1596
1597 /* Return which tree structure is used by T.  */
1598
1599 enum tree_node_structure_enum
1600 tree_node_structure (tree t)
1601 {
1602   enum tree_code code = TREE_CODE (t);
1603
1604   switch (TREE_CODE_CLASS (code))
1605     {
1606     case 'd':   return TS_DECL;
1607     case 't':   return TS_TYPE;
1608     case 'r': case '<': case '1': case '2': case 'e': case 's':
1609       return TS_EXP;
1610     default:  /* 'c' and 'x' */
1611       break;
1612     }
1613   switch (code)
1614     {
1615       /* 'c' cases.  */
1616     case INTEGER_CST:           return TS_INT_CST;
1617     case REAL_CST:              return TS_REAL_CST;
1618     case COMPLEX_CST:           return TS_COMPLEX;
1619     case VECTOR_CST:            return TS_VECTOR;
1620     case STRING_CST:            return TS_STRING;
1621       /* 'x' cases.  */
1622     case ERROR_MARK:            return TS_COMMON;
1623     case IDENTIFIER_NODE:       return TS_IDENTIFIER;
1624     case TREE_LIST:             return TS_LIST;
1625     case TREE_VEC:              return TS_VEC;
1626     case PHI_NODE:              return TS_PHI_NODE;
1627     case SSA_NAME:              return TS_SSA_NAME;
1628     case PLACEHOLDER_EXPR:      return TS_COMMON;
1629     case STATEMENT_LIST:        return TS_STATEMENT_LIST;
1630     case BLOCK:                 return TS_BLOCK;
1631     case TREE_BINFO:            return TS_BINFO;
1632     case VALUE_HANDLE:          return TS_VALUE_HANDLE;
1633
1634     default:
1635       abort ();
1636     }
1637 }
1638 \f
1639 /* Return 1 if EXP contains a PLACEHOLDER_EXPR; i.e., if it represents a size
1640    or offset that depends on a field within a record.  */
1641
1642 bool
1643 contains_placeholder_p (tree exp)
1644 {
1645   enum tree_code code;
1646
1647   if (!exp)
1648     return 0;
1649
1650   code = TREE_CODE (exp);
1651   if (code == PLACEHOLDER_EXPR)
1652     return 1;
1653
1654   switch (TREE_CODE_CLASS (code))
1655     {
1656     case 'r':
1657       /* Don't look at any PLACEHOLDER_EXPRs that might be in index or bit
1658          position computations since they will be converted into a
1659          WITH_RECORD_EXPR involving the reference, which will assume
1660          here will be valid.  */
1661       return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0));
1662
1663     case 'x':
1664       if (code == TREE_LIST)
1665         return (CONTAINS_PLACEHOLDER_P (TREE_VALUE (exp))
1666                 || CONTAINS_PLACEHOLDER_P (TREE_CHAIN (exp)));
1667       break;
1668
1669     case '1':
1670     case '2':  case '<':
1671     case 'e':
1672       switch (code)
1673         {
1674         case COMPOUND_EXPR:
1675           /* Ignoring the first operand isn't quite right, but works best.  */
1676           return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1));
1677
1678         case COND_EXPR:
1679           return (CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0))
1680                   || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1))
1681                   || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 2)));
1682
1683         default:
1684           break;
1685         }
1686
1687       switch (first_rtl_op (code))
1688         {
1689         case 1:
1690           return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0));
1691         case 2:
1692           return (CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0))
1693                   || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1)));
1694         default:
1695           return 0;
1696         }
1697
1698     default:
1699       return 0;
1700     }
1701   return 0;
1702 }
1703
1704 /* Return 1 if any part of the computation of TYPE involves a PLACEHOLDER_EXPR.
1705    This includes size, bounds, qualifiers (for QUAL_UNION_TYPE) and field
1706    positions.  */
1707
1708 bool
1709 type_contains_placeholder_p (tree type)
1710 {
1711   /* If the size contains a placeholder or the parent type (component type in
1712      the case of arrays) type involves a placeholder, this type does.  */
1713   if (CONTAINS_PLACEHOLDER_P (TYPE_SIZE (type))
1714       || CONTAINS_PLACEHOLDER_P (TYPE_SIZE_UNIT (type))
1715       || (TREE_TYPE (type) != 0
1716           && type_contains_placeholder_p (TREE_TYPE (type))))
1717     return 1;
1718
1719   /* Now do type-specific checks.  Note that the last part of the check above
1720      greatly limits what we have to do below.  */
1721   switch (TREE_CODE (type))
1722     {
1723     case VOID_TYPE:
1724     case COMPLEX_TYPE:
1725     case ENUMERAL_TYPE:
1726     case BOOLEAN_TYPE:
1727     case CHAR_TYPE:
1728     case POINTER_TYPE:
1729     case OFFSET_TYPE:
1730     case REFERENCE_TYPE:
1731     case METHOD_TYPE:
1732     case FILE_TYPE:
1733     case FUNCTION_TYPE:
1734       return 0;
1735
1736     case INTEGER_TYPE:
1737     case REAL_TYPE:
1738       /* Here we just check the bounds.  */
1739       return (CONTAINS_PLACEHOLDER_P (TYPE_MIN_VALUE (type))
1740               || CONTAINS_PLACEHOLDER_P (TYPE_MAX_VALUE (type)));
1741
1742     case ARRAY_TYPE:
1743     case SET_TYPE:
1744     case VECTOR_TYPE:
1745       /* We're already checked the component type (TREE_TYPE), so just check
1746          the index type.  */
1747       return type_contains_placeholder_p (TYPE_DOMAIN (type));
1748
1749     case RECORD_TYPE:
1750     case UNION_TYPE:
1751     case QUAL_UNION_TYPE:
1752       {
1753         static tree seen_types = 0;
1754         tree field;
1755         bool ret = 0;
1756
1757         /* We have to be careful here that we don't end up in infinite
1758            recursions due to a field of a type being a pointer to that type
1759            or to a mutually-recursive type.  So we store a list of record
1760            types that we've seen and see if this type is in them.  To save
1761            memory, we don't use a list for just one type.  Here we check
1762            whether we've seen this type before and store it if not.  */
1763         if (seen_types == 0)
1764           seen_types = type;
1765         else if (TREE_CODE (seen_types) != TREE_LIST)
1766           {
1767             if (seen_types == type)
1768               return 0;
1769
1770             seen_types = tree_cons (NULL_TREE, type,
1771                                     build_tree_list (NULL_TREE, seen_types));
1772           }
1773         else
1774           {
1775             if (value_member (type, seen_types) != 0)
1776               return 0;
1777
1778             seen_types = tree_cons (NULL_TREE, type, seen_types);
1779           }
1780
1781         for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
1782           if (TREE_CODE (field) == FIELD_DECL
1783               && (CONTAINS_PLACEHOLDER_P (DECL_FIELD_OFFSET (field))
1784                   || (TREE_CODE (type) == QUAL_UNION_TYPE
1785                       && CONTAINS_PLACEHOLDER_P (DECL_QUALIFIER (field)))
1786                   || type_contains_placeholder_p (TREE_TYPE (field))))
1787             {
1788               ret = true;
1789               break;
1790             }
1791
1792         /* Now remove us from seen_types and return the result.  */
1793         if (seen_types == type)
1794           seen_types = 0;
1795         else
1796           seen_types = TREE_CHAIN (seen_types);
1797
1798         return ret;
1799       }
1800
1801     default:
1802       abort ();
1803     }
1804 }
1805
1806 /* Return 1 if EXP contains any expressions that produce cleanups for an
1807    outer scope to deal with.  Used by fold.  */
1808
1809 int
1810 has_cleanups (tree exp)
1811 {
1812   int i, nops, cmp;
1813
1814   if (! TREE_SIDE_EFFECTS (exp))
1815     return 0;
1816
1817   switch (TREE_CODE (exp))
1818     {
1819     case TARGET_EXPR:
1820     case WITH_CLEANUP_EXPR:
1821       return 1;
1822
1823     case CLEANUP_POINT_EXPR:
1824       return 0;
1825
1826     case CALL_EXPR:
1827       for (exp = TREE_OPERAND (exp, 1); exp; exp = TREE_CHAIN (exp))
1828         {
1829           cmp = has_cleanups (TREE_VALUE (exp));
1830           if (cmp)
1831             return cmp;
1832         }
1833       return 0;
1834
1835     case DECL_EXPR:
1836       return (DECL_INITIAL (DECL_EXPR_DECL (exp))
1837               && has_cleanups (DECL_INITIAL (DECL_EXPR_DECL (exp))));
1838
1839     default:
1840       break;
1841     }
1842
1843   /* This general rule works for most tree codes.  All exceptions should be
1844      handled above.  If this is a language-specific tree code, we can't
1845      trust what might be in the operand, so say we don't know
1846      the situation.  */
1847   if ((int) TREE_CODE (exp) >= (int) LAST_AND_UNUSED_TREE_CODE)
1848     return -1;
1849
1850   nops = first_rtl_op (TREE_CODE (exp));
1851   for (i = 0; i < nops; i++)
1852     if (TREE_OPERAND (exp, i) != 0)
1853       {
1854         int type = TREE_CODE_CLASS (TREE_CODE (TREE_OPERAND (exp, i)));
1855         if (type == 'e' || type == '<' || type == '1' || type == '2'
1856             || type == 'r' || type == 's')
1857           {
1858             cmp = has_cleanups (TREE_OPERAND (exp, i));
1859             if (cmp)
1860               return cmp;
1861           }
1862       }
1863
1864   return 0;
1865 }
1866 \f
1867 /* Given a tree EXP, a FIELD_DECL F, and a replacement value R,
1868    return a tree with all occurrences of references to F in a
1869    PLACEHOLDER_EXPR replaced by R.   Note that we assume here that EXP
1870    contains only arithmetic expressions or a CALL_EXPR with a
1871    PLACEHOLDER_EXPR occurring only in its arglist.  */
1872
1873 tree
1874 substitute_in_expr (tree exp, tree f, tree r)
1875 {
1876   enum tree_code code = TREE_CODE (exp);
1877   tree op0, op1, op2;
1878   tree new;
1879   tree inner;
1880
1881   /* We handle TREE_LIST and COMPONENT_REF separately.  */
1882   if (code == TREE_LIST)
1883     {
1884       op0 = SUBSTITUTE_IN_EXPR (TREE_CHAIN (exp), f, r);
1885       op1 = SUBSTITUTE_IN_EXPR (TREE_VALUE (exp), f, r);
1886       if (op0 == TREE_CHAIN (exp) && op1 == TREE_VALUE (exp))
1887         return exp;
1888
1889       return tree_cons (TREE_PURPOSE (exp), op1, op0);
1890     }
1891   else if (code == COMPONENT_REF)
1892    {
1893      /* If this expression is getting a value from a PLACEHOLDER_EXPR
1894         and it is the right field, replace it with R.  */
1895      for (inner = TREE_OPERAND (exp, 0);
1896           TREE_CODE_CLASS (TREE_CODE (inner)) == 'r';
1897           inner = TREE_OPERAND (inner, 0))
1898        ;
1899      if (TREE_CODE (inner) == PLACEHOLDER_EXPR
1900          && TREE_OPERAND (exp, 1) == f)
1901        return r;
1902
1903      /* If this expression hasn't been completed let, leave it alone.  */
1904      if (TREE_CODE (inner) == PLACEHOLDER_EXPR && TREE_TYPE (inner) == 0)
1905        return exp;
1906
1907      op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
1908      if (op0 == TREE_OPERAND (exp, 0))
1909        return exp;
1910
1911      new = fold (build3 (COMPONENT_REF, TREE_TYPE (exp),
1912                          op0, TREE_OPERAND (exp, 1), NULL_TREE));
1913    }
1914   else
1915     switch (TREE_CODE_CLASS (code))
1916       {
1917       case 'c':
1918       case 'd':
1919         return exp;
1920
1921       case 'x':
1922       case '1':
1923       case '2':
1924       case '<':
1925       case 'e':
1926       case 'r':
1927         switch (first_rtl_op (code))
1928           {
1929           case 0:
1930             return exp;
1931
1932           case 1:
1933             op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
1934             if (op0 == TREE_OPERAND (exp, 0))
1935               return exp;
1936
1937             new = fold (build1 (code, TREE_TYPE (exp), op0));
1938             break;
1939
1940           case 2:
1941             op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
1942             op1 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 1), f, r);
1943
1944             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1))
1945               return exp;
1946
1947             new = fold (build2 (code, TREE_TYPE (exp), op0, op1));
1948             break;
1949
1950           case 3:
1951             op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
1952             op1 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 1), f, r);
1953             op2 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 2), f, r);
1954
1955             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
1956                 && op2 == TREE_OPERAND (exp, 2))
1957               return exp;
1958
1959             new = fold (build3 (code, TREE_TYPE (exp), op0, op1, op2));
1960             break;
1961
1962           default:
1963             abort ();
1964           }
1965         break;
1966
1967       default:
1968         abort ();
1969       }
1970
1971   TREE_READONLY (new) = TREE_READONLY (exp);
1972   return new;
1973 }
1974
1975 /* Similar, but look for a PLACEHOLDER_EXPR in EXP and find a replacement
1976    for it within OBJ, a tree that is an object or a chain of references.  */
1977
1978 tree
1979 substitute_placeholder_in_expr (tree exp, tree obj)
1980 {
1981   enum tree_code code = TREE_CODE (exp);
1982   tree op0, op1, op2, op3;
1983
1984   /* If this is a PLACEHOLDER_EXPR, see if we find a corresponding type
1985      in the chain of OBJ.  */
1986   if (code == PLACEHOLDER_EXPR)
1987     {
1988       tree need_type = TYPE_MAIN_VARIANT (TREE_TYPE (exp));
1989       tree elt;
1990
1991       for (elt = obj; elt != 0;
1992            elt = ((TREE_CODE (elt) == COMPOUND_EXPR
1993                    || TREE_CODE (elt) == COND_EXPR)
1994                   ? TREE_OPERAND (elt, 1)
1995                   : (TREE_CODE_CLASS (TREE_CODE (elt)) == 'r'
1996                      || TREE_CODE_CLASS (TREE_CODE (elt)) == '1'
1997                      || TREE_CODE_CLASS (TREE_CODE (elt)) == '2'
1998                      || TREE_CODE_CLASS (TREE_CODE (elt)) == 'e')
1999                   ? TREE_OPERAND (elt, 0) : 0))
2000         if (TYPE_MAIN_VARIANT (TREE_TYPE (elt)) == need_type)
2001           return elt;
2002
2003       for (elt = obj; elt != 0;
2004            elt = ((TREE_CODE (elt) == COMPOUND_EXPR
2005                    || TREE_CODE (elt) == COND_EXPR)
2006                   ? TREE_OPERAND (elt, 1)
2007                   : (TREE_CODE_CLASS (TREE_CODE (elt)) == 'r'
2008                      || TREE_CODE_CLASS (TREE_CODE (elt)) == '1'
2009                      || TREE_CODE_CLASS (TREE_CODE (elt)) == '2'
2010                      || TREE_CODE_CLASS (TREE_CODE (elt)) == 'e')
2011                   ? TREE_OPERAND (elt, 0) : 0))
2012         if (POINTER_TYPE_P (TREE_TYPE (elt))
2013             && (TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (elt)))
2014                 == need_type))
2015           return fold (build1 (INDIRECT_REF, need_type, elt));
2016
2017       /* If we didn't find it, return the original PLACEHOLDER_EXPR.  If it
2018          survives until RTL generation, there will be an error.  */
2019       return exp;
2020     }
2021
2022   /* TREE_LIST is special because we need to look at TREE_VALUE
2023      and TREE_CHAIN, not TREE_OPERANDS.  */
2024   else if (code == TREE_LIST)
2025     {
2026       op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_CHAIN (exp), obj);
2027       op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_VALUE (exp), obj);
2028       if (op0 == TREE_CHAIN (exp) && op1 == TREE_VALUE (exp))
2029         return exp;
2030
2031       return tree_cons (TREE_PURPOSE (exp), op1, op0);
2032     }
2033   else
2034     switch (TREE_CODE_CLASS (code))
2035       {
2036       case 'c':
2037       case 'd':
2038         return exp;
2039
2040       case 'x':
2041       case '1':
2042       case '2':
2043       case '<':
2044       case 'e':
2045       case 'r':
2046       case 's':
2047         switch (first_rtl_op (code))
2048           {
2049           case 0:
2050             return exp;
2051
2052           case 1:
2053             op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2054             if (op0 == TREE_OPERAND (exp, 0))
2055               return exp;
2056             else
2057               return fold (build1 (code, TREE_TYPE (exp), op0));
2058
2059           case 2:
2060             op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2061             op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 1), obj);
2062
2063             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1))
2064               return exp;
2065             else
2066               return fold (build2 (code, TREE_TYPE (exp), op0, op1));
2067
2068           case 3:
2069             op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2070             op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 1), obj);
2071             op2 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 2), obj);
2072
2073             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
2074                 && op2 == TREE_OPERAND (exp, 2))
2075               return exp;
2076             else
2077               return fold (build3 (code, TREE_TYPE (exp), op0, op1, op2));
2078
2079           case 4:
2080             op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2081             op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 1), obj);
2082             op2 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 2), obj);
2083             op3 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 3), obj);
2084
2085             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
2086                 && op2 == TREE_OPERAND (exp, 2)
2087                 && op3 == TREE_OPERAND (exp, 3))
2088               return exp;
2089             else
2090               return fold (build4 (code, TREE_TYPE (exp), op0, op1, op2, op3));
2091
2092           default:
2093             abort ();
2094           }
2095         break;
2096
2097       default:
2098         abort ();
2099       }
2100 }
2101 \f
2102 /* Stabilize a reference so that we can use it any number of times
2103    without causing its operands to be evaluated more than once.
2104    Returns the stabilized reference.  This works by means of save_expr,
2105    so see the caveats in the comments about save_expr.
2106
2107    Also allows conversion expressions whose operands are references.
2108    Any other kind of expression is returned unchanged.  */
2109
2110 tree
2111 stabilize_reference (tree ref)
2112 {
2113   tree result;
2114   enum tree_code code = TREE_CODE (ref);
2115
2116   switch (code)
2117     {
2118     case VAR_DECL:
2119     case PARM_DECL:
2120     case RESULT_DECL:
2121       /* No action is needed in this case.  */
2122       return ref;
2123
2124     case NOP_EXPR:
2125     case CONVERT_EXPR:
2126     case FLOAT_EXPR:
2127     case FIX_TRUNC_EXPR:
2128     case FIX_FLOOR_EXPR:
2129     case FIX_ROUND_EXPR:
2130     case FIX_CEIL_EXPR:
2131       result = build_nt (code, stabilize_reference (TREE_OPERAND (ref, 0)));
2132       break;
2133
2134     case INDIRECT_REF:
2135       result = build_nt (INDIRECT_REF,
2136                          stabilize_reference_1 (TREE_OPERAND (ref, 0)));
2137       break;
2138
2139     case COMPONENT_REF:
2140       result = build_nt (COMPONENT_REF,
2141                          stabilize_reference (TREE_OPERAND (ref, 0)),
2142                          TREE_OPERAND (ref, 1), NULL_TREE);
2143       break;
2144
2145     case BIT_FIELD_REF:
2146       result = build_nt (BIT_FIELD_REF,
2147                          stabilize_reference (TREE_OPERAND (ref, 0)),
2148                          stabilize_reference_1 (TREE_OPERAND (ref, 1)),
2149                          stabilize_reference_1 (TREE_OPERAND (ref, 2)));
2150       break;
2151
2152     case ARRAY_REF:
2153       result = build_nt (ARRAY_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 ARRAY_RANGE_REF:
2160       result = build_nt (ARRAY_RANGE_REF,
2161                          stabilize_reference (TREE_OPERAND (ref, 0)),
2162                          stabilize_reference_1 (TREE_OPERAND (ref, 1)),
2163                          TREE_OPERAND (ref, 2), TREE_OPERAND (ref, 3));
2164       break;
2165
2166     case COMPOUND_EXPR:
2167       /* We cannot wrap the first expression in a SAVE_EXPR, as then
2168          it wouldn't be ignored.  This matters when dealing with
2169          volatiles.  */
2170       return stabilize_reference_1 (ref);
2171
2172       /* If arg isn't a kind of lvalue we recognize, make no change.
2173          Caller should recognize the error for an invalid lvalue.  */
2174     default:
2175       return ref;
2176
2177     case ERROR_MARK:
2178       return error_mark_node;
2179     }
2180
2181   TREE_TYPE (result) = TREE_TYPE (ref);
2182   TREE_READONLY (result) = TREE_READONLY (ref);
2183   TREE_SIDE_EFFECTS (result) = TREE_SIDE_EFFECTS (ref);
2184   TREE_THIS_VOLATILE (result) = TREE_THIS_VOLATILE (ref);
2185
2186   return result;
2187 }
2188
2189 /* Subroutine of stabilize_reference; this is called for subtrees of
2190    references.  Any expression with side-effects must be put in a SAVE_EXPR
2191    to ensure that it is only evaluated once.
2192
2193    We don't put SAVE_EXPR nodes around everything, because assigning very
2194    simple expressions to temporaries causes us to miss good opportunities
2195    for optimizations.  Among other things, the opportunity to fold in the
2196    addition of a constant into an addressing mode often gets lost, e.g.
2197    "y[i+1] += x;".  In general, we take the approach that we should not make
2198    an assignment unless we are forced into it - i.e., that any non-side effect
2199    operator should be allowed, and that cse should take care of coalescing
2200    multiple utterances of the same expression should that prove fruitful.  */
2201
2202 tree
2203 stabilize_reference_1 (tree e)
2204 {
2205   tree result;
2206   enum tree_code code = TREE_CODE (e);
2207
2208   /* We cannot ignore const expressions because it might be a reference
2209      to a const array but whose index contains side-effects.  But we can
2210      ignore things that are actual constant or that already have been
2211      handled by this function.  */
2212
2213   if (TREE_INVARIANT (e))
2214     return e;
2215
2216   switch (TREE_CODE_CLASS (code))
2217     {
2218     case 'x':
2219     case 't':
2220     case 'd':
2221     case '<':
2222     case 's':
2223     case 'e':
2224     case 'r':
2225       /* If the expression has side-effects, then encase it in a SAVE_EXPR
2226          so that it will only be evaluated once.  */
2227       /* The reference (r) and comparison (<) classes could be handled as
2228          below, but it is generally faster to only evaluate them once.  */
2229       if (TREE_SIDE_EFFECTS (e))
2230         return save_expr (e);
2231       return e;
2232
2233     case 'c':
2234       /* Constants need no processing.  In fact, we should never reach
2235          here.  */
2236       return e;
2237
2238     case '2':
2239       /* Division is slow and tends to be compiled with jumps,
2240          especially the division by powers of 2 that is often
2241          found inside of an array reference.  So do it just once.  */
2242       if (code == TRUNC_DIV_EXPR || code == TRUNC_MOD_EXPR
2243           || code == FLOOR_DIV_EXPR || code == FLOOR_MOD_EXPR
2244           || code == CEIL_DIV_EXPR || code == CEIL_MOD_EXPR
2245           || code == ROUND_DIV_EXPR || code == ROUND_MOD_EXPR)
2246         return save_expr (e);
2247       /* Recursively stabilize each operand.  */
2248       result = build_nt (code, stabilize_reference_1 (TREE_OPERAND (e, 0)),
2249                          stabilize_reference_1 (TREE_OPERAND (e, 1)));
2250       break;
2251
2252     case '1':
2253       /* Recursively stabilize each operand.  */
2254       result = build_nt (code, stabilize_reference_1 (TREE_OPERAND (e, 0)));
2255       break;
2256
2257     default:
2258       abort ();
2259     }
2260
2261   TREE_TYPE (result) = TREE_TYPE (e);
2262   TREE_READONLY (result) = TREE_READONLY (e);
2263   TREE_SIDE_EFFECTS (result) = TREE_SIDE_EFFECTS (e);
2264   TREE_THIS_VOLATILE (result) = TREE_THIS_VOLATILE (e);
2265   TREE_INVARIANT (result) = 1;
2266
2267   return result;
2268 }
2269 \f
2270 /* Low-level constructors for expressions.  */
2271
2272 /* A helper function for build1 and constant folders.  Set TREE_CONSTANT,
2273    TREE_INVARIANT, and TREE_SIDE_EFFECTS for an ADDR_EXPR.  */
2274
2275 void
2276 recompute_tree_invarant_for_addr_expr (tree t)
2277 {
2278   tree node;
2279   bool tc = true, ti = true, se = false;
2280
2281   /* We started out assuming this address is both invariant and constant, but
2282      does not have side effects.  Now go down any handled components and see if
2283      any of them involve offsets that are either non-constant or non-invariant.
2284      Also check for side-effects.
2285
2286      ??? Note that this code makes no attempt to deal with the case where
2287      taking the address of something causes a copy due to misalignment.  */
2288
2289 #define UPDATE_TITCSE(NODE)  \
2290 do { tree _node = (NODE); \
2291      if (_node && !TREE_INVARIANT (_node)) ti = false; \
2292      if (_node && !TREE_CONSTANT (_node)) tc = false; \
2293      if (_node && TREE_SIDE_EFFECTS (_node)) se = true; } while (0)
2294
2295   for (node = TREE_OPERAND (t, 0); handled_component_p (node);
2296        node = TREE_OPERAND (node, 0))
2297     {
2298       /* If the first operand doesn't have an ARRAY_TYPE, this is a bogus
2299          array reference (probably made temporarily by the G++ front end),
2300          so ignore all the operands.  */
2301       if ((TREE_CODE (node) == ARRAY_REF
2302            || TREE_CODE (node) == ARRAY_RANGE_REF)
2303           && TREE_CODE (TREE_TYPE (TREE_OPERAND (node, 0))) == ARRAY_TYPE)
2304         {
2305           UPDATE_TITCSE (TREE_OPERAND (node, 1));
2306           if (TREE_OPERAND (node, 2))
2307             UPDATE_TITCSE (TREE_OPERAND (node, 2));
2308           if (TREE_OPERAND (node, 3))
2309             UPDATE_TITCSE (TREE_OPERAND (node, 3));
2310         }
2311       /* Likewise, just because this is a COMPONENT_REF doesn't mean we have a
2312          FIELD_DECL, apparently.  The G++ front end can put something else
2313          there, at least temporarily.  */
2314       else if (TREE_CODE (node) == COMPONENT_REF
2315                && TREE_CODE (TREE_OPERAND (node, 1)) == FIELD_DECL)
2316         {
2317           if (TREE_OPERAND (node, 2))
2318             UPDATE_TITCSE (TREE_OPERAND (node, 2));
2319         }
2320       else if (TREE_CODE (node) == BIT_FIELD_REF)
2321         UPDATE_TITCSE (TREE_OPERAND (node, 2));
2322     }
2323
2324   /* Now see what's inside.  If it's an INDIRECT_REF, copy our properties from
2325      it.  If it's a decl, it's invariant and constant if the decl is static.
2326      It's also invariant if it's a decl in the current function.  (Taking the
2327      address of a volatile variable is not volatile.)  If it's a constant,
2328      the address is both invariant and constant.  Otherwise it's neither.  */
2329   if (TREE_CODE (node) == INDIRECT_REF)
2330     {
2331       /* If this is &((T*)0)->field, then this is a form of addition.  */
2332       if (TREE_CODE (TREE_OPERAND (node, 0)) != INTEGER_CST)
2333         UPDATE_TITCSE (node);
2334     }
2335   else if (DECL_P (node))
2336     {
2337       if (staticp (node))
2338         ;
2339       else if (decl_function_context (node) == current_function_decl)
2340         tc = false;
2341       else
2342         ti = tc = false;
2343     }
2344   else if (TREE_CODE_CLASS (TREE_CODE (node)) == 'c')
2345     ;
2346   else
2347     {
2348       ti = tc = false;
2349       se |= TREE_SIDE_EFFECTS (node);
2350     }
2351
2352   TREE_CONSTANT (t) = tc;
2353   TREE_INVARIANT (t) = ti;
2354   TREE_SIDE_EFFECTS (t) = se;
2355 #undef UPDATE_TITCSE
2356 }
2357
2358 /* Build an expression of code CODE, data type TYPE, and operands as
2359    specified.  Expressions and reference nodes can be created this way.
2360    Constants, decls, types and misc nodes cannot be.
2361
2362    We define 5 non-variadic functions, from 0 to 4 arguments.  This is
2363    enough for all extant tree codes.  These functions can be called
2364    directly (preferably!), but can also be obtained via GCC preprocessor
2365    magic within the build macro.  */
2366
2367 tree
2368 build0_stat (enum tree_code code, tree tt MEM_STAT_DECL)
2369 {
2370   tree t;
2371
2372 #ifdef ENABLE_CHECKING
2373   if (TREE_CODE_LENGTH (code) != 0)
2374     abort ();
2375 #endif
2376
2377   t = make_node_stat (code PASS_MEM_STAT);
2378   TREE_TYPE (t) = tt;
2379
2380   return t;
2381 }
2382
2383 tree
2384 build1_stat (enum tree_code code, tree type, tree node MEM_STAT_DECL)
2385 {
2386   int length = sizeof (struct tree_exp);
2387 #ifdef GATHER_STATISTICS
2388   tree_node_kind kind;
2389 #endif
2390   tree t;
2391
2392 #ifdef GATHER_STATISTICS
2393   switch (TREE_CODE_CLASS (code))
2394     {
2395     case 's':  /* an expression with side effects */
2396       kind = s_kind;
2397       break;
2398     case 'r':  /* a reference */
2399       kind = r_kind;
2400       break;
2401     default:
2402       kind = e_kind;
2403       break;
2404     }
2405
2406   tree_node_counts[(int) kind]++;
2407   tree_node_sizes[(int) kind] += length;
2408 #endif
2409
2410 #ifdef ENABLE_CHECKING
2411   if (TREE_CODE_LENGTH (code) != 1)
2412     abort ();
2413 #endif /* ENABLE_CHECKING */
2414
2415   t = ggc_alloc_zone_stat (length, tree_zone PASS_MEM_STAT);
2416
2417   memset (t, 0, sizeof (struct tree_common));
2418
2419   TREE_SET_CODE (t, code);
2420
2421   TREE_TYPE (t) = type;
2422 #ifdef USE_MAPPED_LOCATION
2423   SET_EXPR_LOCATION (t, UNKNOWN_LOCATION);
2424 #else
2425   SET_EXPR_LOCUS (t, NULL);
2426 #endif
2427   TREE_COMPLEXITY (t) = 0;
2428   TREE_OPERAND (t, 0) = node;
2429   TREE_BLOCK (t) = NULL_TREE;
2430   if (node && !TYPE_P (node) && first_rtl_op (code) != 0)
2431     {
2432       TREE_SIDE_EFFECTS (t) = TREE_SIDE_EFFECTS (node);
2433       TREE_READONLY (t) = TREE_READONLY (node);
2434     }
2435
2436   if (TREE_CODE_CLASS (code) == 's')
2437     TREE_SIDE_EFFECTS (t) = 1;
2438   else switch (code)
2439     {
2440     case INIT_EXPR:
2441     case MODIFY_EXPR:
2442     case VA_ARG_EXPR:
2443     case PREDECREMENT_EXPR:
2444     case PREINCREMENT_EXPR:
2445     case POSTDECREMENT_EXPR:
2446     case POSTINCREMENT_EXPR:
2447       /* All of these have side-effects, no matter what their
2448          operands are.  */
2449       TREE_SIDE_EFFECTS (t) = 1;
2450       TREE_READONLY (t) = 0;
2451       break;
2452
2453     case INDIRECT_REF:
2454       /* Whether a dereference is readonly has nothing to do with whether
2455          its operand is readonly.  */
2456       TREE_READONLY (t) = 0;
2457       break;
2458
2459     case ADDR_EXPR:
2460       if (node)
2461         recompute_tree_invarant_for_addr_expr (t);
2462       break;
2463
2464     default:
2465       if (TREE_CODE_CLASS (code) == '1' && node && !TYPE_P (node)
2466           && TREE_CONSTANT (node))
2467         TREE_CONSTANT (t) = 1;
2468       if (TREE_CODE_CLASS (code) == '1' && node && TREE_INVARIANT (node))
2469         TREE_INVARIANT (t) = 1;
2470       if (TREE_CODE_CLASS (code) == 'r' && node && TREE_THIS_VOLATILE (node))
2471         TREE_THIS_VOLATILE (t) = 1;
2472       break;
2473     }
2474
2475   return t;
2476 }
2477
2478 #define PROCESS_ARG(N)                  \
2479   do {                                  \
2480     TREE_OPERAND (t, N) = arg##N;       \
2481     if (arg##N &&!TYPE_P (arg##N) && fro > N) \
2482       {                                 \
2483         if (TREE_SIDE_EFFECTS (arg##N)) \
2484           side_effects = 1;             \
2485         if (!TREE_READONLY (arg##N))    \
2486           read_only = 0;                \
2487         if (!TREE_CONSTANT (arg##N))    \
2488           constant = 0;                 \
2489         if (!TREE_INVARIANT (arg##N))   \
2490           invariant = 0;                \
2491       }                                 \
2492   } while (0)
2493
2494 tree
2495 build2_stat (enum tree_code code, tree tt, tree arg0, tree arg1 MEM_STAT_DECL)
2496 {
2497   bool constant, read_only, side_effects, invariant;
2498   tree t;
2499   int fro;
2500
2501 #ifdef ENABLE_CHECKING
2502   if (TREE_CODE_LENGTH (code) != 2)
2503     abort ();
2504 #endif
2505
2506   t = make_node_stat (code PASS_MEM_STAT);
2507   TREE_TYPE (t) = tt;
2508
2509   /* Below, we automatically set TREE_SIDE_EFFECTS and TREE_READONLY for the
2510      result based on those same flags for the arguments.  But if the
2511      arguments aren't really even `tree' expressions, we shouldn't be trying
2512      to do this.  */
2513   fro = first_rtl_op (code);
2514
2515   /* Expressions without side effects may be constant if their
2516      arguments are as well.  */
2517   constant = (TREE_CODE_CLASS (code) == '<'
2518               || TREE_CODE_CLASS (code) == '2');
2519   read_only = 1;
2520   side_effects = TREE_SIDE_EFFECTS (t);
2521   invariant = constant;
2522
2523   PROCESS_ARG(0);
2524   PROCESS_ARG(1);
2525
2526   TREE_READONLY (t) = read_only;
2527   TREE_CONSTANT (t) = constant;
2528   TREE_INVARIANT (t) = invariant;
2529   TREE_SIDE_EFFECTS (t) = side_effects;
2530   TREE_THIS_VOLATILE (t)
2531     = TREE_CODE_CLASS (code) == 'r' && arg0 && TREE_THIS_VOLATILE (arg0);
2532
2533   return t;
2534 }
2535
2536 tree
2537 build3_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
2538              tree arg2 MEM_STAT_DECL)
2539 {
2540   bool constant, read_only, side_effects, invariant;
2541   tree t;
2542   int fro;
2543
2544 #ifdef ENABLE_CHECKING
2545   if (TREE_CODE_LENGTH (code) != 3)
2546     abort ();
2547 #endif
2548
2549   t = make_node_stat (code PASS_MEM_STAT);
2550   TREE_TYPE (t) = tt;
2551
2552   fro = first_rtl_op (code);
2553
2554   side_effects = TREE_SIDE_EFFECTS (t);
2555
2556   PROCESS_ARG(0);
2557   PROCESS_ARG(1);
2558   PROCESS_ARG(2);
2559
2560   if (code == CALL_EXPR && !side_effects)
2561     {
2562       tree node;
2563       int i;
2564
2565       /* Calls have side-effects, except those to const or
2566          pure functions.  */
2567       i = call_expr_flags (t);
2568       if (!(i & (ECF_CONST | ECF_PURE)))
2569         side_effects = 1;
2570
2571       /* And even those have side-effects if their arguments do.  */
2572       else for (node = arg1; node; node = TREE_CHAIN (node))
2573         if (TREE_SIDE_EFFECTS (TREE_VALUE (node)))
2574           {
2575             side_effects = 1;
2576             break;
2577           }
2578     }
2579
2580   TREE_SIDE_EFFECTS (t) = side_effects;
2581   TREE_THIS_VOLATILE (t)
2582     = TREE_CODE_CLASS (code) == 'r' && arg0 && TREE_THIS_VOLATILE (arg0);
2583
2584   return t;
2585 }
2586
2587 tree
2588 build4_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
2589              tree arg2, tree arg3 MEM_STAT_DECL)
2590 {
2591   bool constant, read_only, side_effects, invariant;
2592   tree t;
2593   int fro;
2594
2595 #ifdef ENABLE_CHECKING
2596   if (TREE_CODE_LENGTH (code) != 4)
2597     abort ();
2598 #endif
2599
2600   t = make_node_stat (code PASS_MEM_STAT);
2601   TREE_TYPE (t) = tt;
2602
2603   fro = first_rtl_op (code);
2604
2605   side_effects = TREE_SIDE_EFFECTS (t);
2606
2607   PROCESS_ARG(0);
2608   PROCESS_ARG(1);
2609   PROCESS_ARG(2);
2610   PROCESS_ARG(3);
2611
2612   TREE_SIDE_EFFECTS (t) = side_effects;
2613   TREE_THIS_VOLATILE (t)
2614     = TREE_CODE_CLASS (code) == 'r' && arg0 && TREE_THIS_VOLATILE (arg0);
2615
2616   return t;
2617 }
2618
2619 /* Backup definition for non-gcc build compilers.  */
2620
2621 tree
2622 (build) (enum tree_code code, tree tt, ...)
2623 {
2624   tree t, arg0, arg1, arg2, arg3;
2625   int length = TREE_CODE_LENGTH (code);
2626   va_list p;
2627
2628   va_start (p, tt);
2629   switch (length)
2630     {
2631     case 0:
2632       t = build0 (code, tt);
2633       break;
2634     case 1:
2635       arg0 = va_arg (p, tree);
2636       t = build1 (code, tt, arg0);
2637       break;
2638     case 2:
2639       arg0 = va_arg (p, tree);
2640       arg1 = va_arg (p, tree);
2641       t = build2 (code, tt, arg0, arg1);
2642       break;
2643     case 3:
2644       arg0 = va_arg (p, tree);
2645       arg1 = va_arg (p, tree);
2646       arg2 = va_arg (p, tree);
2647       t = build3 (code, tt, arg0, arg1, arg2);
2648       break;
2649     case 4:
2650       arg0 = va_arg (p, tree);
2651       arg1 = va_arg (p, tree);
2652       arg2 = va_arg (p, tree);
2653       arg3 = va_arg (p, tree);
2654       t = build4 (code, tt, arg0, arg1, arg2, arg3);
2655       break;
2656     default:
2657       abort ();
2658     }
2659   va_end (p);
2660
2661   return t;
2662 }
2663
2664 /* Similar except don't specify the TREE_TYPE
2665    and leave the TREE_SIDE_EFFECTS as 0.
2666    It is permissible for arguments to be null,
2667    or even garbage if their values do not matter.  */
2668
2669 tree
2670 build_nt (enum tree_code code, ...)
2671 {
2672   tree t;
2673   int length;
2674   int i;
2675   va_list p;
2676
2677   va_start (p, code);
2678
2679   t = make_node (code);
2680   length = TREE_CODE_LENGTH (code);
2681
2682   for (i = 0; i < length; i++)
2683     TREE_OPERAND (t, i) = va_arg (p, tree);
2684
2685   va_end (p);
2686   return t;
2687 }
2688 \f
2689 /* Create a DECL_... node of code CODE, name NAME and data type TYPE.
2690    We do NOT enter this node in any sort of symbol table.
2691
2692    layout_decl is used to set up the decl's storage layout.
2693    Other slots are initialized to 0 or null pointers.  */
2694
2695 tree
2696 build_decl_stat (enum tree_code code, tree name, tree type MEM_STAT_DECL)
2697 {
2698   tree t;
2699
2700   t = make_node_stat (code PASS_MEM_STAT);
2701
2702 /*  if (type == error_mark_node)
2703     type = integer_type_node; */
2704 /* That is not done, deliberately, so that having error_mark_node
2705    as the type can suppress useless errors in the use of this variable.  */
2706
2707   DECL_NAME (t) = name;
2708   TREE_TYPE (t) = type;
2709
2710   if (code == VAR_DECL || code == PARM_DECL || code == RESULT_DECL)
2711     layout_decl (t, 0);
2712   else if (code == FUNCTION_DECL)
2713     DECL_MODE (t) = FUNCTION_MODE;
2714
2715   /* Set default visibility to whatever the user supplied with
2716      visibility_specified depending on #pragma GCC visibility.  */
2717   DECL_VISIBILITY (t) = default_visibility;
2718   DECL_VISIBILITY_SPECIFIED (t) = visibility_options.inpragma;
2719
2720   return t;
2721 }
2722 \f
2723 /* BLOCK nodes are used to represent the structure of binding contours
2724    and declarations, once those contours have been exited and their contents
2725    compiled.  This information is used for outputting debugging info.  */
2726
2727 tree
2728 build_block (tree vars, tree tags ATTRIBUTE_UNUSED, tree subblocks,
2729              tree supercontext, tree chain)
2730 {
2731   tree block = make_node (BLOCK);
2732
2733   BLOCK_VARS (block) = vars;
2734   BLOCK_SUBBLOCKS (block) = subblocks;
2735   BLOCK_SUPERCONTEXT (block) = supercontext;
2736   BLOCK_CHAIN (block) = chain;
2737   return block;
2738 }
2739
2740 #if 1 /* ! defined(USE_MAPPED_LOCATION) */
2741 /* ??? gengtype doesn't handle conditionals */
2742 static GTY(()) tree last_annotated_node;
2743 #endif
2744
2745 #ifdef USE_MAPPED_LOCATION
2746
2747 expanded_location
2748 expand_location (source_location loc)
2749 {
2750   expanded_location xloc;
2751   if (loc == 0) { xloc.file = NULL; xloc.line = 0;  xloc.column = 0; }
2752   else
2753     {
2754       const struct line_map *map = linemap_lookup (&line_table, loc);
2755       xloc.file = map->to_file;
2756       xloc.line = SOURCE_LINE (map, loc);
2757       xloc.column = SOURCE_COLUMN (map, loc);
2758     };
2759   return xloc;
2760 }
2761
2762 #else
2763
2764 /* Record the exact location where an expression or an identifier were
2765    encountered.  */
2766
2767 void
2768 annotate_with_file_line (tree node, const char *file, int line)
2769 {
2770   /* Roughly one percent of the calls to this function are to annotate
2771      a node with the same information already attached to that node!
2772      Just return instead of wasting memory.  */
2773   if (EXPR_LOCUS (node)
2774       && (EXPR_FILENAME (node) == file
2775           || ! strcmp (EXPR_FILENAME (node), file))
2776       && EXPR_LINENO (node) == line)
2777     {
2778       last_annotated_node = node;
2779       return;
2780     }
2781
2782   /* In heavily macroized code (such as GCC itself) this single
2783      entry cache can reduce the number of allocations by more
2784      than half.  */
2785   if (last_annotated_node
2786       && EXPR_LOCUS (last_annotated_node)
2787       && (EXPR_FILENAME (last_annotated_node) == file
2788           || ! strcmp (EXPR_FILENAME (last_annotated_node), file))
2789       && EXPR_LINENO (last_annotated_node) == line)
2790     {
2791       SET_EXPR_LOCUS (node, EXPR_LOCUS (last_annotated_node));
2792       return;
2793     }
2794
2795   SET_EXPR_LOCUS (node, ggc_alloc (sizeof (location_t)));
2796   EXPR_LINENO (node) = line;
2797   EXPR_FILENAME (node) = file;
2798   last_annotated_node = node;
2799 }
2800
2801 void
2802 annotate_with_locus (tree node, location_t locus)
2803 {
2804   annotate_with_file_line (node, locus.file, locus.line);
2805 }
2806 #endif
2807 \f
2808 /* Return a declaration like DDECL except that its DECL_ATTRIBUTES
2809    is ATTRIBUTE.  */
2810
2811 tree
2812 build_decl_attribute_variant (tree ddecl, tree attribute)
2813 {
2814   DECL_ATTRIBUTES (ddecl) = attribute;
2815   return ddecl;
2816 }
2817
2818 /* Borrowed from hashtab.c iterative_hash implementation.  */
2819 #define mix(a,b,c) \
2820 { \
2821   a -= b; a -= c; a ^= (c>>13); \
2822   b -= c; b -= a; b ^= (a<< 8); \
2823   c -= a; c -= b; c ^= ((b&0xffffffff)>>13); \
2824   a -= b; a -= c; a ^= ((c&0xffffffff)>>12); \
2825   b -= c; b -= a; b = (b ^ (a<<16)) & 0xffffffff; \
2826   c -= a; c -= b; c = (c ^ (b>> 5)) & 0xffffffff; \
2827   a -= b; a -= c; a = (a ^ (c>> 3)) & 0xffffffff; \
2828   b -= c; b -= a; b = (b ^ (a<<10)) & 0xffffffff; \
2829   c -= a; c -= b; c = (c ^ (b>>15)) & 0xffffffff; \
2830 }
2831
2832
2833 /* Produce good hash value combining VAL and VAL2.  */
2834 static inline hashval_t
2835 iterative_hash_hashval_t (hashval_t val, hashval_t val2)
2836 {
2837   /* the golden ratio; an arbitrary value.  */
2838   hashval_t a = 0x9e3779b9;
2839
2840   mix (a, val, val2);
2841   return val2;
2842 }
2843
2844 /* Produce good hash value combining PTR and VAL2.  */
2845 static inline hashval_t
2846 iterative_hash_pointer (void *ptr, hashval_t val2)
2847 {
2848   if (sizeof (ptr) == sizeof (hashval_t))
2849     return iterative_hash_hashval_t ((size_t) ptr, val2);
2850   else
2851     {
2852       hashval_t a = (hashval_t) (size_t) ptr;
2853       /* Avoid warnings about shifting of more than the width of the type on
2854          hosts that won't execute this path.  */
2855       int zero = 0;
2856       hashval_t b = (hashval_t) ((size_t) ptr >> (sizeof (hashval_t) * 8 + zero));
2857       mix (a, b, val2);
2858       return val2;
2859     }
2860 }
2861
2862 /* Produce good hash value combining VAL and VAL2.  */
2863 static inline hashval_t
2864 iterative_hash_host_wide_int (HOST_WIDE_INT val, hashval_t val2)
2865 {
2866   if (sizeof (HOST_WIDE_INT) == sizeof (hashval_t))
2867     return iterative_hash_hashval_t (val, val2);
2868   else
2869     {
2870       hashval_t a = (hashval_t) val;
2871       /* Avoid warnings about shifting of more than the width of the type on
2872          hosts that won't execute this path.  */
2873       int zero = 0;
2874       hashval_t b = (hashval_t) (val >> (sizeof (hashval_t) * 8 + zero));
2875       mix (a, b, val2);
2876       if (sizeof (HOST_WIDE_INT) > 2 * sizeof (hashval_t))
2877         {
2878           hashval_t a = (hashval_t) (val >> (sizeof (hashval_t) * 16 + zero));
2879           hashval_t b = (hashval_t) (val >> (sizeof (hashval_t) * 24 + zero));
2880           mix (a, b, val2);
2881         }
2882       return val2;
2883     }
2884 }
2885
2886 /* Return a type like TTYPE except that its TYPE_ATTRIBUTE
2887    is ATTRIBUTE.
2888
2889    Record such modified types already made so we don't make duplicates.  */
2890
2891 tree
2892 build_type_attribute_variant (tree ttype, tree attribute)
2893 {
2894   if (! attribute_list_equal (TYPE_ATTRIBUTES (ttype), attribute))
2895     {
2896       hashval_t hashcode = 0;
2897       tree ntype;
2898       enum tree_code code = TREE_CODE (ttype);
2899
2900       ntype = copy_node (ttype);
2901
2902       TYPE_POINTER_TO (ntype) = 0;
2903       TYPE_REFERENCE_TO (ntype) = 0;
2904       TYPE_ATTRIBUTES (ntype) = attribute;
2905
2906       /* Create a new main variant of TYPE.  */
2907       TYPE_MAIN_VARIANT (ntype) = ntype;
2908       TYPE_NEXT_VARIANT (ntype) = 0;
2909       set_type_quals (ntype, TYPE_UNQUALIFIED);
2910
2911       hashcode = iterative_hash_object (code, hashcode);
2912       if (TREE_TYPE (ntype))
2913         hashcode = iterative_hash_object (TYPE_HASH (TREE_TYPE (ntype)),
2914                                           hashcode);
2915       hashcode = attribute_hash_list (attribute, hashcode);
2916
2917       switch (TREE_CODE (ntype))
2918         {
2919         case FUNCTION_TYPE:
2920           hashcode = type_hash_list (TYPE_ARG_TYPES (ntype), hashcode);
2921           break;
2922         case ARRAY_TYPE:
2923           hashcode = iterative_hash_object (TYPE_HASH (TYPE_DOMAIN (ntype)),
2924                                             hashcode);
2925           break;
2926         case INTEGER_TYPE:
2927           hashcode = iterative_hash_object
2928             (TREE_INT_CST_LOW (TYPE_MAX_VALUE (ntype)), hashcode);
2929           hashcode = iterative_hash_object
2930             (TREE_INT_CST_HIGH (TYPE_MAX_VALUE (ntype)), hashcode);
2931           break;
2932         case REAL_TYPE:
2933           {
2934             unsigned int precision = TYPE_PRECISION (ntype);
2935             hashcode = iterative_hash_object (precision, hashcode);
2936           }
2937           break;
2938         default:
2939           break;
2940         }
2941
2942       ntype = type_hash_canon (hashcode, ntype);
2943       ttype = build_qualified_type (ntype, TYPE_QUALS (ttype));
2944     }
2945
2946   return ttype;
2947 }
2948
2949 /* Return nonzero if IDENT is a valid name for attribute ATTR,
2950    or zero if not.
2951
2952    We try both `text' and `__text__', ATTR may be either one.  */
2953 /* ??? It might be a reasonable simplification to require ATTR to be only
2954    `text'.  One might then also require attribute lists to be stored in
2955    their canonicalized form.  */
2956
2957 int
2958 is_attribute_p (const char *attr, tree ident)
2959 {
2960   int ident_len, attr_len;
2961   const char *p;
2962
2963   if (TREE_CODE (ident) != IDENTIFIER_NODE)
2964     return 0;
2965
2966   if (strcmp (attr, IDENTIFIER_POINTER (ident)) == 0)
2967     return 1;
2968
2969   p = IDENTIFIER_POINTER (ident);
2970   ident_len = strlen (p);
2971   attr_len = strlen (attr);
2972
2973   /* If ATTR is `__text__', IDENT must be `text'; and vice versa.  */
2974   if (attr[0] == '_')
2975     {
2976       if (attr[1] != '_'
2977           || attr[attr_len - 2] != '_'
2978           || attr[attr_len - 1] != '_')
2979         abort ();
2980       if (ident_len == attr_len - 4
2981           && strncmp (attr + 2, p, attr_len - 4) == 0)
2982         return 1;
2983     }
2984   else
2985     {
2986       if (ident_len == attr_len + 4
2987           && p[0] == '_' && p[1] == '_'
2988           && p[ident_len - 2] == '_' && p[ident_len - 1] == '_'
2989           && strncmp (attr, p + 2, attr_len) == 0)
2990         return 1;
2991     }
2992
2993   return 0;
2994 }
2995
2996 /* Given an attribute name and a list of attributes, return a pointer to the
2997    attribute's list element if the attribute is part of the list, or NULL_TREE
2998    if not found.  If the attribute appears more than once, this only
2999    returns the first occurrence; the TREE_CHAIN of the return value should
3000    be passed back in if further occurrences are wanted.  */
3001
3002 tree
3003 lookup_attribute (const char *attr_name, tree list)
3004 {
3005   tree l;
3006
3007   for (l = list; l; l = TREE_CHAIN (l))
3008     {
3009       if (TREE_CODE (TREE_PURPOSE (l)) != IDENTIFIER_NODE)
3010         abort ();
3011       if (is_attribute_p (attr_name, TREE_PURPOSE (l)))
3012         return l;
3013     }
3014
3015   return NULL_TREE;
3016 }
3017
3018 /* Return an attribute list that is the union of a1 and a2.  */
3019
3020 tree
3021 merge_attributes (tree a1, tree a2)
3022 {
3023   tree attributes;
3024
3025   /* Either one unset?  Take the set one.  */
3026
3027   if ((attributes = a1) == 0)
3028     attributes = a2;
3029
3030   /* One that completely contains the other?  Take it.  */
3031
3032   else if (a2 != 0 && ! attribute_list_contained (a1, a2))
3033     {
3034       if (attribute_list_contained (a2, a1))
3035         attributes = a2;
3036       else
3037         {
3038           /* Pick the longest list, and hang on the other list.  */
3039
3040           if (list_length (a1) < list_length (a2))
3041             attributes = a2, a2 = a1;
3042
3043           for (; a2 != 0; a2 = TREE_CHAIN (a2))
3044             {
3045               tree a;
3046               for (a = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (a2)),
3047                                          attributes);
3048                    a != NULL_TREE;
3049                    a = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (a2)),
3050                                          TREE_CHAIN (a)))
3051                 {
3052                   if (simple_cst_equal (TREE_VALUE (a), TREE_VALUE (a2)) == 1)
3053                     break;
3054                 }
3055               if (a == NULL_TREE)
3056                 {
3057                   a1 = copy_node (a2);
3058                   TREE_CHAIN (a1) = attributes;
3059                   attributes = a1;
3060                 }
3061             }
3062         }
3063     }
3064   return attributes;
3065 }
3066
3067 /* Given types T1 and T2, merge their attributes and return
3068   the result.  */
3069
3070 tree
3071 merge_type_attributes (tree t1, tree t2)
3072 {
3073   return merge_attributes (TYPE_ATTRIBUTES (t1),
3074                            TYPE_ATTRIBUTES (t2));
3075 }
3076
3077 /* Given decls OLDDECL and NEWDECL, merge their attributes and return
3078    the result.  */
3079
3080 tree
3081 merge_decl_attributes (tree olddecl, tree newdecl)
3082 {
3083   return merge_attributes (DECL_ATTRIBUTES (olddecl),
3084                            DECL_ATTRIBUTES (newdecl));
3085 }
3086
3087 #if TARGET_DLLIMPORT_DECL_ATTRIBUTES
3088
3089 /* Specialization of merge_decl_attributes for various Windows targets.
3090
3091    This handles the following situation:
3092
3093      __declspec (dllimport) int foo;
3094      int foo;
3095
3096    The second instance of `foo' nullifies the dllimport.  */
3097
3098 tree
3099 merge_dllimport_decl_attributes (tree old, tree new)
3100 {
3101   tree a;
3102   int delete_dllimport_p;
3103
3104   old = DECL_ATTRIBUTES (old);
3105   new = DECL_ATTRIBUTES (new);
3106
3107   /* What we need to do here is remove from `old' dllimport if it doesn't
3108      appear in `new'.  dllimport behaves like extern: if a declaration is
3109      marked dllimport and a definition appears later, then the object
3110      is not dllimport'd.  */
3111   if (lookup_attribute ("dllimport", old) != NULL_TREE
3112       && lookup_attribute ("dllimport", new) == NULL_TREE)
3113     delete_dllimport_p = 1;
3114   else
3115     delete_dllimport_p = 0;
3116
3117   a = merge_attributes (old, new);
3118
3119   if (delete_dllimport_p)
3120     {
3121       tree prev, t;
3122
3123       /* Scan the list for dllimport and delete it.  */
3124       for (prev = NULL_TREE, t = a; t; prev = t, t = TREE_CHAIN (t))
3125         {
3126           if (is_attribute_p ("dllimport", TREE_PURPOSE (t)))
3127             {
3128               if (prev == NULL_TREE)
3129                 a = TREE_CHAIN (a);
3130               else
3131                 TREE_CHAIN (prev) = TREE_CHAIN (t);
3132               break;
3133             }
3134         }
3135     }
3136
3137   return a;
3138 }
3139
3140 /* Handle a "dllimport" or "dllexport" attribute; arguments as in
3141    struct attribute_spec.handler.  */
3142
3143 tree
3144 handle_dll_attribute (tree * pnode, tree name, tree args, int flags,
3145                       bool *no_add_attrs)
3146 {
3147   tree node = *pnode;
3148
3149   /* These attributes may apply to structure and union types being created,
3150      but otherwise should pass to the declaration involved.  */
3151   if (!DECL_P (node))
3152     {
3153       if (flags & ((int) ATTR_FLAG_DECL_NEXT | (int) ATTR_FLAG_FUNCTION_NEXT
3154                    | (int) ATTR_FLAG_ARRAY_NEXT))
3155         {
3156           *no_add_attrs = true;
3157           return tree_cons (name, args, NULL_TREE);
3158         }
3159       if (TREE_CODE (node) != RECORD_TYPE && TREE_CODE (node) != UNION_TYPE)
3160         {
3161           warning ("`%s' attribute ignored", IDENTIFIER_POINTER (name));
3162           *no_add_attrs = true;
3163         }
3164
3165       return NULL_TREE;
3166     }
3167
3168   /* Report error on dllimport ambiguities seen now before they cause
3169      any damage.  */
3170   if (is_attribute_p ("dllimport", name))
3171     {
3172       /* Like MS, treat definition of dllimported variables and
3173          non-inlined functions on declaration as syntax errors.  We
3174          allow the attribute for function definitions if declared
3175          inline.  */
3176       if (TREE_CODE (node) == FUNCTION_DECL  && DECL_INITIAL (node)
3177           && !DECL_DECLARED_INLINE_P (node))
3178         {
3179           error ("%Jfunction `%D' definition is marked dllimport.", node, node);
3180           *no_add_attrs = true;
3181         }
3182
3183       else if (TREE_CODE (node) == VAR_DECL)
3184         {
3185           if (DECL_INITIAL (node))
3186             {
3187               error ("%Jvariable `%D' definition is marked dllimport.",
3188                      node, node);
3189               *no_add_attrs = true;
3190             }
3191
3192           /* `extern' needn't be specified with dllimport.
3193              Specify `extern' now and hope for the best.  Sigh.  */
3194           DECL_EXTERNAL (node) = 1;
3195           /* Also, implicitly give dllimport'd variables declared within
3196              a function global scope, unless declared static.  */
3197           if (current_function_decl != NULL_TREE && !TREE_STATIC (node))
3198             TREE_PUBLIC (node) = 1;
3199         }
3200     }
3201
3202   /*  Report error if symbol is not accessible at global scope.  */
3203   if (!TREE_PUBLIC (node)
3204       && (TREE_CODE (node) == VAR_DECL
3205           || TREE_CODE (node) == FUNCTION_DECL))
3206     {
3207       error ("%Jexternal linkage required for symbol '%D' because of "
3208              "'%s' attribute.", node, node, IDENTIFIER_POINTER (name));
3209       *no_add_attrs = true;
3210     }
3211
3212   return NULL_TREE;
3213 }
3214
3215 #endif /* TARGET_DLLIMPORT_DECL_ATTRIBUTES  */
3216 \f
3217 /* Set the type qualifiers for TYPE to TYPE_QUALS, which is a bitmask
3218    of the various TYPE_QUAL values.  */
3219
3220 static void
3221 set_type_quals (tree type, int type_quals)
3222 {
3223   TYPE_READONLY (type) = (type_quals & TYPE_QUAL_CONST) != 0;
3224   TYPE_VOLATILE (type) = (type_quals & TYPE_QUAL_VOLATILE) != 0;
3225   TYPE_RESTRICT (type) = (type_quals & TYPE_QUAL_RESTRICT) != 0;
3226 }
3227
3228 /* Returns true iff cand is equivalent to base with type_quals.  */
3229
3230 bool
3231 check_qualified_type (tree cand, tree base, int type_quals)
3232 {
3233   return (TYPE_QUALS (cand) == type_quals
3234           && TYPE_NAME (cand) == TYPE_NAME (base)
3235           /* Apparently this is needed for Objective-C.  */
3236           && TYPE_CONTEXT (cand) == TYPE_CONTEXT (base)
3237           && attribute_list_equal (TYPE_ATTRIBUTES (cand),
3238                                    TYPE_ATTRIBUTES (base)));
3239 }
3240
3241 /* Return a version of the TYPE, qualified as indicated by the
3242    TYPE_QUALS, if one exists.  If no qualified version exists yet,
3243    return NULL_TREE.  */
3244
3245 tree
3246 get_qualified_type (tree type, int type_quals)
3247 {
3248   tree t;
3249
3250   if (TYPE_QUALS (type) == type_quals)
3251     return type;
3252
3253   /* Search the chain of variants to see if there is already one there just
3254      like the one we need to have.  If so, use that existing one.  We must
3255      preserve the TYPE_NAME, since there is code that depends on this.  */
3256   for (t = TYPE_MAIN_VARIANT (type); t; t = TYPE_NEXT_VARIANT (t))
3257     if (check_qualified_type (t, type, type_quals))
3258       return t;
3259
3260   return NULL_TREE;
3261 }
3262
3263 /* Like get_qualified_type, but creates the type if it does not
3264    exist.  This function never returns NULL_TREE.  */
3265
3266 tree
3267 build_qualified_type (tree type, int type_quals)
3268 {
3269   tree t;
3270
3271   /* See if we already have the appropriate qualified variant.  */
3272   t = get_qualified_type (type, type_quals);
3273
3274   /* If not, build it.  */
3275   if (!t)
3276     {
3277       t = build_variant_type_copy (type);
3278       set_type_quals (t, type_quals);
3279     }
3280
3281   return t;
3282 }
3283
3284 /* Create a new distinct copy of TYPE.  The new type is made its own
3285    MAIN_VARIANT.  */
3286
3287 tree
3288 build_distinct_type_copy (tree type)
3289 {
3290   tree t = copy_node (type);
3291   
3292   TYPE_POINTER_TO (t) = 0;
3293   TYPE_REFERENCE_TO (t) = 0;
3294
3295   /* Make it its own variant.  */
3296   TYPE_MAIN_VARIANT (t) = t;
3297   TYPE_NEXT_VARIANT (t) = 0;
3298   
3299   return t;
3300 }
3301
3302 /* Create a new variant of TYPE, equivalent but distinct.
3303    This is so the caller can modify it.  */
3304
3305 tree
3306 build_variant_type_copy (tree type)
3307 {
3308   tree t, m = TYPE_MAIN_VARIANT (type);
3309
3310   t = build_distinct_type_copy (type);
3311   
3312   /* Add the new type to the chain of variants of TYPE.  */
3313   TYPE_NEXT_VARIANT (t) = TYPE_NEXT_VARIANT (m);
3314   TYPE_NEXT_VARIANT (m) = t;
3315   TYPE_MAIN_VARIANT (t) = m;
3316
3317   return t;
3318 }
3319 \f
3320 /* Hashing of types so that we don't make duplicates.
3321    The entry point is `type_hash_canon'.  */
3322
3323 /* Compute a hash code for a list of types (chain of TREE_LIST nodes
3324    with types in the TREE_VALUE slots), by adding the hash codes
3325    of the individual types.  */
3326
3327 unsigned int
3328 type_hash_list (tree list, hashval_t hashcode)
3329 {
3330   tree tail;
3331
3332   for (tail = list; tail; tail = TREE_CHAIN (tail))
3333     if (TREE_VALUE (tail) != error_mark_node)
3334       hashcode = iterative_hash_object (TYPE_HASH (TREE_VALUE (tail)),
3335                                         hashcode);
3336
3337   return hashcode;
3338 }
3339
3340 /* These are the Hashtable callback functions.  */
3341
3342 /* Returns true iff the types are equivalent.  */
3343
3344 static int
3345 type_hash_eq (const void *va, const void *vb)
3346 {
3347   const struct type_hash *a = va, *b = vb;
3348
3349   /* First test the things that are the same for all types.  */
3350   if (a->hash != b->hash
3351       || TREE_CODE (a->type) != TREE_CODE (b->type)
3352       || TREE_TYPE (a->type) != TREE_TYPE (b->type)
3353       || !attribute_list_equal (TYPE_ATTRIBUTES (a->type),
3354                                  TYPE_ATTRIBUTES (b->type))
3355       || TYPE_ALIGN (a->type) != TYPE_ALIGN (b->type)
3356       || TYPE_MODE (a->type) != TYPE_MODE (b->type))
3357     return 0;
3358
3359   switch (TREE_CODE (a->type))
3360     {
3361     case VOID_TYPE:
3362     case COMPLEX_TYPE:
3363     case VECTOR_TYPE:
3364     case POINTER_TYPE:
3365     case REFERENCE_TYPE:
3366       return 1;
3367
3368     case ENUMERAL_TYPE:
3369       if (TYPE_VALUES (a->type) != TYPE_VALUES (b->type)
3370           && !(TYPE_VALUES (a->type)
3371                && TREE_CODE (TYPE_VALUES (a->type)) == TREE_LIST
3372                && TYPE_VALUES (b->type)
3373                && TREE_CODE (TYPE_VALUES (b->type)) == TREE_LIST
3374                && type_list_equal (TYPE_VALUES (a->type),
3375                                    TYPE_VALUES (b->type))))
3376         return 0;
3377
3378       /* ... fall through ... */
3379
3380     case INTEGER_TYPE:
3381     case REAL_TYPE:
3382     case BOOLEAN_TYPE:
3383     case CHAR_TYPE:
3384       return ((TYPE_MAX_VALUE (a->type) == TYPE_MAX_VALUE (b->type)
3385                || tree_int_cst_equal (TYPE_MAX_VALUE (a->type),
3386                                       TYPE_MAX_VALUE (b->type)))
3387               && (TYPE_MIN_VALUE (a->type) == TYPE_MIN_VALUE (b->type)
3388                   || tree_int_cst_equal (TYPE_MIN_VALUE (a->type),
3389                                          TYPE_MIN_VALUE (b->type))));
3390
3391     case OFFSET_TYPE:
3392       return TYPE_OFFSET_BASETYPE (a->type) == TYPE_OFFSET_BASETYPE (b->type);
3393
3394     case METHOD_TYPE:
3395       return (TYPE_METHOD_BASETYPE (a->type) == TYPE_METHOD_BASETYPE (b->type)
3396               && (TYPE_ARG_TYPES (a->type) == TYPE_ARG_TYPES (b->type)
3397                   || (TYPE_ARG_TYPES (a->type)
3398                       && TREE_CODE (TYPE_ARG_TYPES (a->type)) == TREE_LIST
3399                       && TYPE_ARG_TYPES (b->type)
3400                       && TREE_CODE (TYPE_ARG_TYPES (b->type)) == TREE_LIST
3401                       && type_list_equal (TYPE_ARG_TYPES (a->type),
3402                                           TYPE_ARG_TYPES (b->type)))));
3403
3404     case ARRAY_TYPE:
3405     case SET_TYPE:
3406       return TYPE_DOMAIN (a->type) == TYPE_DOMAIN (b->type);
3407
3408     case RECORD_TYPE:
3409     case UNION_TYPE:
3410     case QUAL_UNION_TYPE:
3411       return (TYPE_FIELDS (a->type) == TYPE_FIELDS (b->type)
3412               || (TYPE_FIELDS (a->type)
3413                   && TREE_CODE (TYPE_FIELDS (a->type)) == TREE_LIST
3414                   && TYPE_FIELDS (b->type)
3415                   && TREE_CODE (TYPE_FIELDS (b->type)) == TREE_LIST
3416                   && type_list_equal (TYPE_FIELDS (a->type),
3417                                       TYPE_FIELDS (b->type))));
3418
3419     case FUNCTION_TYPE:
3420       return (TYPE_ARG_TYPES (a->type) == TYPE_ARG_TYPES (b->type)
3421               || (TYPE_ARG_TYPES (a->type)
3422                   && TREE_CODE (TYPE_ARG_TYPES (a->type)) == TREE_LIST
3423                   && TYPE_ARG_TYPES (b->type)
3424                   && TREE_CODE (TYPE_ARG_TYPES (b->type)) == TREE_LIST
3425                   && type_list_equal (TYPE_ARG_TYPES (a->type),
3426                                       TYPE_ARG_TYPES (b->type))));
3427
3428     default:
3429       return 0;
3430     }
3431 }
3432
3433 /* Return the cached hash value.  */
3434
3435 static hashval_t
3436 type_hash_hash (const void *item)
3437 {
3438   return ((const struct type_hash *) item)->hash;
3439 }
3440
3441 /* Look in the type hash table for a type isomorphic to TYPE.
3442    If one is found, return it.  Otherwise return 0.  */
3443
3444 tree
3445 type_hash_lookup (hashval_t hashcode, tree type)
3446 {
3447   struct type_hash *h, in;
3448
3449   /* The TYPE_ALIGN field of a type is set by layout_type(), so we
3450      must call that routine before comparing TYPE_ALIGNs.  */
3451   layout_type (type);
3452
3453   in.hash = hashcode;
3454   in.type = type;
3455
3456   h = htab_find_with_hash (type_hash_table, &in, hashcode);
3457   if (h)
3458     return h->type;
3459   return NULL_TREE;
3460 }
3461
3462 /* Add an entry to the type-hash-table
3463    for a type TYPE whose hash code is HASHCODE.  */
3464
3465 void
3466 type_hash_add (hashval_t hashcode, tree type)
3467 {
3468   struct type_hash *h;
3469   void **loc;
3470
3471   h = ggc_alloc (sizeof (struct type_hash));
3472   h->hash = hashcode;
3473   h->type = type;
3474   loc = htab_find_slot_with_hash (type_hash_table, h, hashcode, INSERT);
3475   *(struct type_hash **) loc = h;
3476 }
3477
3478 /* Given TYPE, and HASHCODE its hash code, return the canonical
3479    object for an identical type if one already exists.
3480    Otherwise, return TYPE, and record it as the canonical object.
3481
3482    To use this function, first create a type of the sort you want.
3483    Then compute its hash code from the fields of the type that
3484    make it different from other similar types.
3485    Then call this function and use the value.  */
3486
3487 tree
3488 type_hash_canon (unsigned int hashcode, tree type)
3489 {
3490   tree t1;
3491
3492   /* The hash table only contains main variants, so ensure that's what we're
3493      being passed.  */
3494   if (TYPE_MAIN_VARIANT (type) != type)
3495     abort ();
3496
3497   if (!lang_hooks.types.hash_types)
3498     return type;
3499
3500   /* See if the type is in the hash table already.  If so, return it.
3501      Otherwise, add the type.  */
3502   t1 = type_hash_lookup (hashcode, type);
3503   if (t1 != 0)
3504     {
3505 #ifdef GATHER_STATISTICS
3506       tree_node_counts[(int) t_kind]--;
3507       tree_node_sizes[(int) t_kind] -= sizeof (struct tree_type);
3508 #endif
3509       return t1;
3510     }
3511   else
3512     {
3513       type_hash_add (hashcode, type);
3514       return type;
3515     }
3516 }
3517
3518 /* See if the data pointed to by the type hash table is marked.  We consider
3519    it marked if the type is marked or if a debug type number or symbol
3520    table entry has been made for the type.  This reduces the amount of
3521    debugging output and eliminates that dependency of the debug output on
3522    the number of garbage collections.  */
3523
3524 static int
3525 type_hash_marked_p (const void *p)
3526 {
3527   tree type = ((struct type_hash *) p)->type;
3528
3529   return ggc_marked_p (type) || TYPE_SYMTAB_POINTER (type);
3530 }
3531
3532 static void
3533 print_type_hash_statistics (void)
3534 {
3535   fprintf (stderr, "Type hash: size %ld, %ld elements, %f collisions\n",
3536            (long) htab_size (type_hash_table),
3537            (long) htab_elements (type_hash_table),
3538            htab_collisions (type_hash_table));
3539 }
3540
3541 /* Compute a hash code for a list of attributes (chain of TREE_LIST nodes
3542    with names in the TREE_PURPOSE slots and args in the TREE_VALUE slots),
3543    by adding the hash codes of the individual attributes.  */
3544
3545 unsigned int
3546 attribute_hash_list (tree list, hashval_t hashcode)
3547 {
3548   tree tail;
3549
3550   for (tail = list; tail; tail = TREE_CHAIN (tail))
3551     /* ??? Do we want to add in TREE_VALUE too? */
3552     hashcode = iterative_hash_object
3553       (IDENTIFIER_HASH_VALUE (TREE_PURPOSE (tail)), hashcode);
3554   return hashcode;
3555 }
3556
3557 /* Given two lists of attributes, return true if list l2 is
3558    equivalent to l1.  */
3559
3560 int
3561 attribute_list_equal (tree l1, tree l2)
3562 {
3563   return attribute_list_contained (l1, l2)
3564          && attribute_list_contained (l2, l1);
3565 }
3566
3567 /* Given two lists of attributes, return true if list L2 is
3568    completely contained within L1.  */
3569 /* ??? This would be faster if attribute names were stored in a canonicalized
3570    form.  Otherwise, if L1 uses `foo' and L2 uses `__foo__', the long method
3571    must be used to show these elements are equivalent (which they are).  */
3572 /* ??? It's not clear that attributes with arguments will always be handled
3573    correctly.  */
3574
3575 int
3576 attribute_list_contained (tree l1, tree l2)
3577 {
3578   tree t1, t2;
3579
3580   /* First check the obvious, maybe the lists are identical.  */
3581   if (l1 == l2)
3582     return 1;
3583
3584   /* Maybe the lists are similar.  */
3585   for (t1 = l1, t2 = l2;
3586        t1 != 0 && t2 != 0
3587         && TREE_PURPOSE (t1) == TREE_PURPOSE (t2)
3588         && TREE_VALUE (t1) == TREE_VALUE (t2);
3589        t1 = TREE_CHAIN (t1), t2 = TREE_CHAIN (t2));
3590
3591   /* Maybe the lists are equal.  */
3592   if (t1 == 0 && t2 == 0)
3593     return 1;
3594
3595   for (; t2 != 0; t2 = TREE_CHAIN (t2))
3596     {
3597       tree attr;
3598       for (attr = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (t2)), l1);
3599            attr != NULL_TREE;
3600            attr = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (t2)),
3601                                     TREE_CHAIN (attr)))
3602         {
3603           if (simple_cst_equal (TREE_VALUE (t2), TREE_VALUE (attr)) == 1)
3604             break;
3605         }
3606
3607       if (attr == 0)
3608         return 0;
3609
3610       if (simple_cst_equal (TREE_VALUE (t2), TREE_VALUE (attr)) != 1)
3611         return 0;
3612     }
3613
3614   return 1;
3615 }
3616
3617 /* Given two lists of types
3618    (chains of TREE_LIST nodes with types in the TREE_VALUE slots)
3619    return 1 if the lists contain the same types in the same order.
3620    Also, the TREE_PURPOSEs must match.  */
3621
3622 int
3623 type_list_equal (tree l1, tree l2)
3624 {
3625   tree t1, t2;
3626
3627   for (t1 = l1, t2 = l2; t1 && t2; t1 = TREE_CHAIN (t1), t2 = TREE_CHAIN (t2))
3628     if (TREE_VALUE (t1) != TREE_VALUE (t2)
3629         || (TREE_PURPOSE (t1) != TREE_PURPOSE (t2)
3630             && ! (1 == simple_cst_equal (TREE_PURPOSE (t1), TREE_PURPOSE (t2))
3631                   && (TREE_TYPE (TREE_PURPOSE (t1))
3632                       == TREE_TYPE (TREE_PURPOSE (t2))))))
3633       return 0;
3634
3635   return t1 == t2;
3636 }
3637
3638 /* Returns the number of arguments to the FUNCTION_TYPE or METHOD_TYPE
3639    given by TYPE.  If the argument list accepts variable arguments,
3640    then this function counts only the ordinary arguments.  */
3641
3642 int
3643 type_num_arguments (tree type)
3644 {
3645   int i = 0;
3646   tree t;
3647
3648   for (t = TYPE_ARG_TYPES (type); t; t = TREE_CHAIN (t))
3649     /* If the function does not take a variable number of arguments,
3650        the last element in the list will have type `void'.  */
3651     if (VOID_TYPE_P (TREE_VALUE (t)))
3652       break;
3653     else
3654       ++i;
3655
3656   return i;
3657 }
3658
3659 /* Nonzero if integer constants T1 and T2
3660    represent the same constant value.  */
3661
3662 int
3663 tree_int_cst_equal (tree t1, tree t2)
3664 {
3665   if (t1 == t2)
3666     return 1;
3667
3668   if (t1 == 0 || t2 == 0)
3669     return 0;
3670
3671   if (TREE_CODE (t1) == INTEGER_CST
3672       && TREE_CODE (t2) == INTEGER_CST
3673       && TREE_INT_CST_LOW (t1) == TREE_INT_CST_LOW (t2)
3674       && TREE_INT_CST_HIGH (t1) == TREE_INT_CST_HIGH (t2))
3675     return 1;
3676
3677   return 0;
3678 }
3679
3680 /* Nonzero if integer constants T1 and T2 represent values that satisfy <.
3681    The precise way of comparison depends on their data type.  */
3682
3683 int
3684 tree_int_cst_lt (tree t1, tree t2)
3685 {
3686   if (t1 == t2)
3687     return 0;
3688
3689   if (TYPE_UNSIGNED (TREE_TYPE (t1)) != TYPE_UNSIGNED (TREE_TYPE (t2)))
3690     {
3691       int t1_sgn = tree_int_cst_sgn (t1);
3692       int t2_sgn = tree_int_cst_sgn (t2);
3693
3694       if (t1_sgn < t2_sgn)
3695         return 1;
3696       else if (t1_sgn > t2_sgn)
3697         return 0;
3698       /* Otherwise, both are non-negative, so we compare them as
3699          unsigned just in case one of them would overflow a signed
3700          type.  */
3701     }
3702   else if (!TYPE_UNSIGNED (TREE_TYPE (t1)))
3703     return INT_CST_LT (t1, t2);
3704
3705   return INT_CST_LT_UNSIGNED (t1, t2);
3706 }
3707
3708 /* Returns -1 if T1 < T2, 0 if T1 == T2, and 1 if T1 > T2.  */
3709
3710 int
3711 tree_int_cst_compare (tree t1, tree t2)
3712 {
3713   if (tree_int_cst_lt (t1, t2))
3714     return -1;
3715   else if (tree_int_cst_lt (t2, t1))
3716     return 1;
3717   else
3718     return 0;
3719 }
3720
3721 /* Return 1 if T is an INTEGER_CST that can be manipulated efficiently on
3722    the host.  If POS is zero, the value can be represented in a single
3723    HOST_WIDE_INT.  If POS is nonzero, the value must be positive and can
3724    be represented in a single unsigned HOST_WIDE_INT.  */
3725
3726 int
3727 host_integerp (tree t, int pos)
3728 {
3729   return (TREE_CODE (t) == INTEGER_CST
3730           && ! TREE_OVERFLOW (t)
3731           && ((TREE_INT_CST_HIGH (t) == 0
3732                && (HOST_WIDE_INT) TREE_INT_CST_LOW (t) >= 0)
3733               || (! pos && TREE_INT_CST_HIGH (t) == -1
3734                   && (HOST_WIDE_INT) TREE_INT_CST_LOW (t) < 0
3735                   && !TYPE_UNSIGNED (TREE_TYPE (t)))
3736               || (pos && TREE_INT_CST_HIGH (t) == 0)));
3737 }
3738
3739 /* Return the HOST_WIDE_INT least significant bits of T if it is an
3740    INTEGER_CST and there is no overflow.  POS is nonzero if the result must
3741    be positive.  Abort if we cannot satisfy the above conditions.  */
3742
3743 HOST_WIDE_INT
3744 tree_low_cst (tree t, int pos)
3745 {
3746   if (host_integerp (t, pos))
3747     return TREE_INT_CST_LOW (t);
3748   else
3749     abort ();
3750 }
3751
3752 /* Return the most significant bit of the integer constant T.  */
3753
3754 int
3755 tree_int_cst_msb (tree t)
3756 {
3757   int prec;
3758   HOST_WIDE_INT h;
3759   unsigned HOST_WIDE_INT l;
3760
3761   /* Note that using TYPE_PRECISION here is wrong.  We care about the
3762      actual bits, not the (arbitrary) range of the type.  */
3763   prec = GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (t))) - 1;
3764   rshift_double (TREE_INT_CST_LOW (t), TREE_INT_CST_HIGH (t), prec,
3765                  2 * HOST_BITS_PER_WIDE_INT, &l, &h, 0);
3766   return (l & 1) == 1;
3767 }
3768
3769 /* Return an indication of the sign of the integer constant T.
3770    The return value is -1 if T < 0, 0 if T == 0, and 1 if T > 0.
3771    Note that -1 will never be returned it T's type is unsigned.  */
3772
3773 int
3774 tree_int_cst_sgn (tree t)
3775 {
3776   if (TREE_INT_CST_LOW (t) == 0 && TREE_INT_CST_HIGH (t) == 0)
3777     return 0;
3778   else if (TYPE_UNSIGNED (TREE_TYPE (t)))
3779     return 1;
3780   else if (TREE_INT_CST_HIGH (t) < 0)
3781     return -1;
3782   else
3783     return 1;
3784 }
3785
3786 /* Compare two constructor-element-type constants.  Return 1 if the lists
3787    are known to be equal; otherwise return 0.  */
3788
3789 int
3790 simple_cst_list_equal (tree l1, tree l2)
3791 {
3792   while (l1 != NULL_TREE && l2 != NULL_TREE)
3793     {
3794       if (simple_cst_equal (TREE_VALUE (l1), TREE_VALUE (l2)) != 1)
3795         return 0;
3796
3797       l1 = TREE_CHAIN (l1);
3798       l2 = TREE_CHAIN (l2);
3799     }
3800
3801   return l1 == l2;
3802 }
3803
3804 /* Return truthvalue of whether T1 is the same tree structure as T2.
3805    Return 1 if they are the same.
3806    Return 0 if they are understandably different.
3807    Return -1 if either contains tree structure not understood by
3808    this function.  */
3809
3810 int
3811 simple_cst_equal (tree t1, tree t2)
3812 {
3813   enum tree_code code1, code2;
3814   int cmp;
3815   int i;
3816
3817   if (t1 == t2)
3818     return 1;
3819   if (t1 == 0 || t2 == 0)
3820     return 0;
3821
3822   code1 = TREE_CODE (t1);
3823   code2 = TREE_CODE (t2);
3824
3825   if (code1 == NOP_EXPR || code1 == CONVERT_EXPR || code1 == NON_LVALUE_EXPR)
3826     {
3827       if (code2 == NOP_EXPR || code2 == CONVERT_EXPR
3828           || code2 == NON_LVALUE_EXPR)
3829         return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3830       else
3831         return simple_cst_equal (TREE_OPERAND (t1, 0), t2);
3832     }
3833
3834   else if (code2 == NOP_EXPR || code2 == CONVERT_EXPR
3835            || code2 == NON_LVALUE_EXPR)
3836     return simple_cst_equal (t1, TREE_OPERAND (t2, 0));
3837
3838   if (code1 != code2)
3839     return 0;
3840
3841   switch (code1)
3842     {
3843     case INTEGER_CST:
3844       return (TREE_INT_CST_LOW (t1) == TREE_INT_CST_LOW (t2)
3845               && TREE_INT_CST_HIGH (t1) == TREE_INT_CST_HIGH (t2));
3846
3847     case REAL_CST:
3848       return REAL_VALUES_IDENTICAL (TREE_REAL_CST (t1), TREE_REAL_CST (t2));
3849
3850     case STRING_CST:
3851       return (TREE_STRING_LENGTH (t1) == TREE_STRING_LENGTH (t2)
3852               && ! memcmp (TREE_STRING_POINTER (t1), TREE_STRING_POINTER (t2),
3853                          TREE_STRING_LENGTH (t1)));
3854
3855     case CONSTRUCTOR:
3856       return simple_cst_list_equal (CONSTRUCTOR_ELTS (t1),
3857                                     CONSTRUCTOR_ELTS (t2));
3858
3859     case SAVE_EXPR:
3860       return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3861
3862     case CALL_EXPR:
3863       cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3864       if (cmp <= 0)
3865         return cmp;
3866       return
3867         simple_cst_list_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
3868
3869     case TARGET_EXPR:
3870       /* Special case: if either target is an unallocated VAR_DECL,
3871          it means that it's going to be unified with whatever the
3872          TARGET_EXPR is really supposed to initialize, so treat it
3873          as being equivalent to anything.  */
3874       if ((TREE_CODE (TREE_OPERAND (t1, 0)) == VAR_DECL
3875            && DECL_NAME (TREE_OPERAND (t1, 0)) == NULL_TREE
3876            && !DECL_RTL_SET_P (TREE_OPERAND (t1, 0)))
3877           || (TREE_CODE (TREE_OPERAND (t2, 0)) == VAR_DECL
3878               && DECL_NAME (TREE_OPERAND (t2, 0)) == NULL_TREE
3879               && !DECL_RTL_SET_P (TREE_OPERAND (t2, 0))))
3880         cmp = 1;
3881       else
3882         cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3883
3884       if (cmp <= 0)
3885         return cmp;
3886
3887       return simple_cst_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
3888
3889     case WITH_CLEANUP_EXPR:
3890       cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3891       if (cmp <= 0)
3892         return cmp;
3893
3894       return simple_cst_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t1, 1));
3895
3896     case COMPONENT_REF:
3897       if (TREE_OPERAND (t1, 1) == TREE_OPERAND (t2, 1))
3898         return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3899
3900       return 0;
3901
3902     case VAR_DECL:
3903     case PARM_DECL:
3904     case CONST_DECL:
3905     case FUNCTION_DECL:
3906       return 0;
3907
3908     default:
3909       break;
3910     }
3911
3912   /* This general rule works for most tree codes.  All exceptions should be
3913      handled above.  If this is a language-specific tree code, we can't
3914      trust what might be in the operand, so say we don't know
3915      the situation.  */
3916   if ((int) code1 >= (int) LAST_AND_UNUSED_TREE_CODE)
3917     return -1;
3918
3919   switch (TREE_CODE_CLASS (code1))
3920     {
3921     case '1':
3922     case '2':
3923     case '<':
3924     case 'e':
3925     case 'r':
3926     case 's':
3927       cmp = 1;
3928       for (i = 0; i < TREE_CODE_LENGTH (code1); i++)
3929         {
3930           cmp = simple_cst_equal (TREE_OPERAND (t1, i), TREE_OPERAND (t2, i));
3931           if (cmp <= 0)
3932             return cmp;
3933         }
3934
3935       return cmp;
3936
3937     default:
3938       return -1;
3939     }
3940 }
3941
3942 /* Compare the value of T, an INTEGER_CST, with U, an unsigned integer value.
3943    Return -1, 0, or 1 if the value of T is less than, equal to, or greater
3944    than U, respectively.  */
3945
3946 int
3947 compare_tree_int (tree t, unsigned HOST_WIDE_INT u)
3948 {
3949   if (tree_int_cst_sgn (t) < 0)
3950     return -1;
3951   else if (TREE_INT_CST_HIGH (t) != 0)
3952     return 1;
3953   else if (TREE_INT_CST_LOW (t) == u)
3954     return 0;
3955   else if (TREE_INT_CST_LOW (t) < u)
3956     return -1;
3957   else
3958     return 1;
3959 }
3960
3961 /* Return true if CODE represents an associative tree code.  Otherwise
3962    return false.  */
3963 bool
3964 associative_tree_code (enum tree_code code)
3965 {
3966   switch (code)
3967     {
3968     case BIT_IOR_EXPR:
3969     case BIT_AND_EXPR:
3970     case BIT_XOR_EXPR:
3971     case PLUS_EXPR:
3972     case MULT_EXPR:
3973     case MIN_EXPR:
3974     case MAX_EXPR:
3975       return true;
3976
3977     default:
3978       break;
3979     }
3980   return false;
3981 }
3982
3983 /* Return true if CODE represents an commutative tree code.  Otherwise
3984    return false.  */
3985 bool
3986 commutative_tree_code (enum tree_code code)
3987 {
3988   switch (code)
3989     {
3990     case PLUS_EXPR:
3991     case MULT_EXPR:
3992     case MIN_EXPR:
3993     case MAX_EXPR:
3994     case BIT_IOR_EXPR:
3995     case BIT_XOR_EXPR:
3996     case BIT_AND_EXPR:
3997     case NE_EXPR:
3998     case EQ_EXPR:
3999     case UNORDERED_EXPR:
4000     case ORDERED_EXPR:
4001     case UNEQ_EXPR:
4002     case LTGT_EXPR:
4003     case TRUTH_AND_EXPR:
4004     case TRUTH_XOR_EXPR:
4005     case TRUTH_OR_EXPR:
4006       return true;
4007
4008     default:
4009       break;
4010     }
4011   return false;
4012 }
4013
4014 /* Generate a hash value for an expression.  This can be used iteratively
4015    by passing a previous result as the "val" argument.
4016
4017    This function is intended to produce the same hash for expressions which
4018    would compare equal using operand_equal_p.  */
4019
4020 hashval_t
4021 iterative_hash_expr (tree t, hashval_t val)
4022 {
4023   int i;
4024   enum tree_code code;
4025   char class;
4026
4027   if (t == NULL_TREE)
4028     return iterative_hash_pointer (t, val);
4029
4030   code = TREE_CODE (t);
4031
4032   switch (code)
4033     {
4034     /* Alas, constants aren't shared, so we can't rely on pointer
4035        identity.  */
4036     case INTEGER_CST:
4037       val = iterative_hash_host_wide_int (TREE_INT_CST_LOW (t), val);
4038       return iterative_hash_host_wide_int (TREE_INT_CST_HIGH (t), val);
4039     case REAL_CST:
4040       {
4041         unsigned int val2 = real_hash (TREE_REAL_CST_PTR (t));
4042
4043         return iterative_hash_hashval_t (val2, val);
4044       }
4045     case STRING_CST:
4046       return iterative_hash (TREE_STRING_POINTER (t),
4047                              TREE_STRING_LENGTH (t), val);
4048     case COMPLEX_CST:
4049       val = iterative_hash_expr (TREE_REALPART (t), val);
4050       return iterative_hash_expr (TREE_IMAGPART (t), val);
4051     case VECTOR_CST:
4052       return iterative_hash_expr (TREE_VECTOR_CST_ELTS (t), val);
4053
4054     case SSA_NAME:
4055     case VALUE_HANDLE:
4056       /* we can just compare by pointer.  */
4057       return iterative_hash_pointer (t, val);
4058
4059     case TREE_LIST:
4060       /* A list of expressions, for a CALL_EXPR or as the elements of a
4061          VECTOR_CST.  */
4062       for (; t; t = TREE_CHAIN (t))
4063         val = iterative_hash_expr (TREE_VALUE (t), val);
4064       return val;
4065     default:
4066       class = TREE_CODE_CLASS (code);
4067
4068       if (class == 'd')
4069         {
4070           /* Decls we can just compare by pointer.  */
4071           val = iterative_hash_pointer (t, val);
4072         }
4073       else if (IS_EXPR_CODE_CLASS (class))
4074         {
4075           val = iterative_hash_object (code, val);
4076
4077           /* Don't hash the type, that can lead to having nodes which
4078              compare equal according to operand_equal_p, but which
4079              have different hash codes.  */
4080           if (code == NOP_EXPR
4081               || code == CONVERT_EXPR
4082               || code == NON_LVALUE_EXPR)
4083             {
4084               /* Make sure to include signness in the hash computation.  */
4085               val += TYPE_UNSIGNED (TREE_TYPE (t));
4086               val = iterative_hash_expr (TREE_OPERAND (t, 0), val);
4087             }
4088
4089           else if (commutative_tree_code (code))
4090             {
4091               /* It's a commutative expression.  We want to hash it the same
4092                  however it appears.  We do this by first hashing both operands
4093                  and then rehashing based on the order of their independent
4094                  hashes.  */
4095               hashval_t one = iterative_hash_expr (TREE_OPERAND (t, 0), 0);
4096               hashval_t two = iterative_hash_expr (TREE_OPERAND (t, 1), 0);
4097               hashval_t t;
4098
4099               if (one > two)
4100                 t = one, one = two, two = t;
4101
4102               val = iterative_hash_hashval_t (one, val);
4103               val = iterative_hash_hashval_t (two, val);
4104             }
4105           else
4106             for (i = first_rtl_op (code) - 1; i >= 0; --i)
4107               val = iterative_hash_expr (TREE_OPERAND (t, i), val);
4108         }
4109       else
4110         abort ();
4111       return val;
4112       break;
4113     }
4114 }
4115 \f
4116 /* Constructors for pointer, array and function types.
4117    (RECORD_TYPE, UNION_TYPE and ENUMERAL_TYPE nodes are
4118    constructed by language-dependent code, not here.)  */
4119
4120 /* Construct, lay out and return the type of pointers to TO_TYPE with
4121    mode MODE.  If CAN_ALIAS_ALL is TRUE, indicate this type can
4122    reference all of memory. If such a type has already been
4123    constructed, reuse it.  */
4124
4125 tree
4126 build_pointer_type_for_mode (tree to_type, enum machine_mode mode,
4127                              bool can_alias_all)
4128 {
4129   tree t;
4130
4131   /* In some cases, languages will have things that aren't a POINTER_TYPE
4132      (such as a RECORD_TYPE for fat pointers in Ada) as TYPE_POINTER_TO.
4133      In that case, return that type without regard to the rest of our
4134      operands.
4135
4136      ??? This is a kludge, but consistent with the way this function has
4137      always operated and there doesn't seem to be a good way to avoid this
4138      at the moment.  */
4139   if (TYPE_POINTER_TO (to_type) != 0
4140       && TREE_CODE (TYPE_POINTER_TO (to_type)) != POINTER_TYPE)
4141     return TYPE_POINTER_TO (to_type);
4142
4143   /* First, if we already have a type for pointers to TO_TYPE and it's
4144      the proper mode, use it.  */
4145   for (t = TYPE_POINTER_TO (to_type); t; t = TYPE_NEXT_PTR_TO (t))
4146     if (TYPE_MODE (t) == mode && TYPE_REF_CAN_ALIAS_ALL (t) == can_alias_all)
4147       return t;
4148
4149   t = make_node (POINTER_TYPE);
4150
4151   TREE_TYPE (t) = to_type;
4152   TYPE_MODE (t) = mode;
4153   TYPE_REF_CAN_ALIAS_ALL (t) = can_alias_all;
4154   TYPE_NEXT_PTR_TO (t) = TYPE_POINTER_TO (to_type);
4155   TYPE_POINTER_TO (to_type) = t;
4156
4157   /* Lay out the type.  This function has many callers that are concerned
4158      with expression-construction, and this simplifies them all.  */
4159   layout_type (t);
4160
4161   return t;
4162 }
4163
4164 /* By default build pointers in ptr_mode.  */
4165
4166 tree
4167 build_pointer_type (tree to_type)
4168 {
4169   return build_pointer_type_for_mode (to_type, ptr_mode, false);
4170 }
4171
4172 /* Same as build_pointer_type_for_mode, but for REFERENCE_TYPE.  */
4173
4174 tree
4175 build_reference_type_for_mode (tree to_type, enum machine_mode mode,
4176                                bool can_alias_all)
4177 {
4178   tree t;
4179
4180   /* In some cases, languages will have things that aren't a REFERENCE_TYPE
4181      (such as a RECORD_TYPE for fat pointers in Ada) as TYPE_REFERENCE_TO.
4182      In that case, return that type without regard to the rest of our
4183      operands.
4184
4185      ??? This is a kludge, but consistent with the way this function has
4186      always operated and there doesn't seem to be a good way to avoid this
4187      at the moment.  */
4188   if (TYPE_REFERENCE_TO (to_type) != 0
4189       && TREE_CODE (TYPE_REFERENCE_TO (to_type)) != REFERENCE_TYPE)
4190     return TYPE_REFERENCE_TO (to_type);
4191
4192   /* First, if we already have a type for pointers to TO_TYPE and it's
4193      the proper mode, use it.  */
4194   for (t = TYPE_REFERENCE_TO (to_type); t; t = TYPE_NEXT_REF_TO (t))
4195     if (TYPE_MODE (t) == mode && TYPE_REF_CAN_ALIAS_ALL (t) == can_alias_all)
4196       return t;
4197
4198   t = make_node (REFERENCE_TYPE);
4199
4200   TREE_TYPE (t) = to_type;
4201   TYPE_MODE (t) = mode;
4202   TYPE_REF_CAN_ALIAS_ALL (t) = can_alias_all;
4203   TYPE_NEXT_REF_TO (t) = TYPE_REFERENCE_TO (to_type);
4204   TYPE_REFERENCE_TO (to_type) = t;
4205
4206   layout_type (t);
4207
4208   return t;
4209 }
4210
4211
4212 /* Build the node for the type of references-to-TO_TYPE by default
4213    in ptr_mode.  */
4214
4215 tree
4216 build_reference_type (tree to_type)
4217 {
4218   return build_reference_type_for_mode (to_type, ptr_mode, false);
4219 }
4220
4221 /* Build a type that is compatible with t but has no cv quals anywhere
4222    in its type, thus
4223
4224    const char *const *const *  ->  char ***.  */
4225
4226 tree
4227 build_type_no_quals (tree t)
4228 {
4229   switch (TREE_CODE (t))
4230     {
4231     case POINTER_TYPE:
4232       return build_pointer_type_for_mode (build_type_no_quals (TREE_TYPE (t)),
4233                                           TYPE_MODE (t),
4234                                           TYPE_REF_CAN_ALIAS_ALL (t));
4235     case REFERENCE_TYPE:
4236       return
4237         build_reference_type_for_mode (build_type_no_quals (TREE_TYPE (t)),
4238                                        TYPE_MODE (t),
4239                                        TYPE_REF_CAN_ALIAS_ALL (t));
4240     default:
4241       return TYPE_MAIN_VARIANT (t);
4242     }
4243 }
4244
4245 /* Create a type of integers to be the TYPE_DOMAIN of an ARRAY_TYPE.
4246    MAXVAL should be the maximum value in the domain
4247    (one less than the length of the array).
4248
4249    The maximum value that MAXVAL can have is INT_MAX for a HOST_WIDE_INT.
4250    We don't enforce this limit, that is up to caller (e.g. language front end).
4251    The limit exists because the result is a signed type and we don't handle
4252    sizes that use more than one HOST_WIDE_INT.  */
4253
4254 tree
4255 build_index_type (tree maxval)
4256 {
4257   tree itype = make_node (INTEGER_TYPE);
4258
4259   TREE_TYPE (itype) = sizetype;
4260   TYPE_PRECISION (itype) = TYPE_PRECISION (sizetype);
4261   TYPE_MIN_VALUE (itype) = size_zero_node;
4262   TYPE_MAX_VALUE (itype) = convert (sizetype, maxval);
4263   TYPE_MODE (itype) = TYPE_MODE (sizetype);
4264   TYPE_SIZE (itype) = TYPE_SIZE (sizetype);
4265   TYPE_SIZE_UNIT (itype) = TYPE_SIZE_UNIT (sizetype);
4266   TYPE_ALIGN (itype) = TYPE_ALIGN (sizetype);
4267   TYPE_USER_ALIGN (itype) = TYPE_USER_ALIGN (sizetype);
4268
4269   if (host_integerp (maxval, 1))
4270     return type_hash_canon (tree_low_cst (maxval, 1), itype);
4271   else
4272     return itype;
4273 }
4274
4275 /* Builds a signed or unsigned integer type of precision PRECISION.
4276    Used for C bitfields whose precision does not match that of
4277    built-in target types.  */
4278 tree
4279 build_nonstandard_integer_type (unsigned HOST_WIDE_INT precision,
4280                                 int unsignedp)
4281 {
4282   tree itype = make_node (INTEGER_TYPE);
4283
4284   TYPE_PRECISION (itype) = precision;
4285
4286   if (unsignedp)
4287     fixup_unsigned_type (itype);
4288   else
4289     fixup_signed_type (itype);
4290
4291   if (host_integerp (TYPE_MAX_VALUE (itype), 1))
4292     return type_hash_canon (tree_low_cst (TYPE_MAX_VALUE (itype), 1), itype);
4293
4294   return itype;
4295 }
4296
4297 /* Create a range of some discrete type TYPE (an INTEGER_TYPE,
4298    ENUMERAL_TYPE, BOOLEAN_TYPE, or CHAR_TYPE), with
4299    low bound LOWVAL and high bound HIGHVAL.
4300    if TYPE==NULL_TREE, sizetype is used.  */
4301
4302 tree
4303 build_range_type (tree type, tree lowval, tree highval)
4304 {
4305   tree itype = make_node (INTEGER_TYPE);
4306
4307   TREE_TYPE (itype) = type;
4308   if (type == NULL_TREE)
4309     type = sizetype;
4310
4311   TYPE_MIN_VALUE (itype) = convert (type, lowval);
4312   TYPE_MAX_VALUE (itype) = highval ? convert (type, highval) : NULL;
4313
4314   TYPE_PRECISION (itype) = TYPE_PRECISION (type);
4315   TYPE_MODE (itype) = TYPE_MODE (type);
4316   TYPE_SIZE (itype) = TYPE_SIZE (type);
4317   TYPE_SIZE_UNIT (itype) = TYPE_SIZE_UNIT (type);
4318   TYPE_ALIGN (itype) = TYPE_ALIGN (type);
4319   TYPE_USER_ALIGN (itype) = TYPE_USER_ALIGN (type);
4320
4321   if (host_integerp (lowval, 0) && highval != 0 && host_integerp (highval, 0))
4322     return type_hash_canon (tree_low_cst (highval, 0)
4323                             - tree_low_cst (lowval, 0),
4324                             itype);
4325   else
4326     return itype;
4327 }
4328
4329 /* Just like build_index_type, but takes lowval and highval instead
4330    of just highval (maxval).  */
4331
4332 tree
4333 build_index_2_type (tree lowval, tree highval)
4334 {
4335   return build_range_type (sizetype, lowval, highval);
4336 }
4337
4338 /* Construct, lay out and return the type of arrays of elements with ELT_TYPE
4339    and number of elements specified by the range of values of INDEX_TYPE.
4340    If such a type has already been constructed, reuse it.  */
4341
4342 tree
4343 build_array_type (tree elt_type, tree index_type)
4344 {
4345   tree t;
4346   hashval_t hashcode = 0;
4347
4348   if (TREE_CODE (elt_type) == FUNCTION_TYPE)
4349     {
4350       error ("arrays of functions are not meaningful");
4351       elt_type = integer_type_node;
4352     }
4353
4354   t = make_node (ARRAY_TYPE);
4355   TREE_TYPE (t) = elt_type;
4356   TYPE_DOMAIN (t) = index_type;
4357
4358   if (index_type == 0)
4359     return t;
4360
4361   hashcode = iterative_hash_object (TYPE_HASH (elt_type), hashcode);
4362   hashcode = iterative_hash_object (TYPE_HASH (index_type), hashcode);
4363   t = type_hash_canon (hashcode, t);
4364
4365   if (!COMPLETE_TYPE_P (t))
4366     layout_type (t);
4367   return t;
4368 }
4369
4370 /* Return the TYPE of the elements comprising
4371    the innermost dimension of ARRAY.  */
4372
4373 tree
4374 get_inner_array_type (tree array)
4375 {
4376   tree type = TREE_TYPE (array);
4377
4378   while (TREE_CODE (type) == ARRAY_TYPE)
4379     type = TREE_TYPE (type);
4380
4381   return type;
4382 }
4383
4384 /* Construct, lay out and return
4385    the type of functions returning type VALUE_TYPE
4386    given arguments of types ARG_TYPES.
4387    ARG_TYPES is a chain of TREE_LIST nodes whose TREE_VALUEs
4388    are data type nodes for the arguments of the function.
4389    If such a type has already been constructed, reuse it.  */
4390
4391 tree
4392 build_function_type (tree value_type, tree arg_types)
4393 {
4394   tree t;
4395   hashval_t hashcode = 0;
4396
4397   if (TREE_CODE (value_type) == FUNCTION_TYPE)
4398     {
4399       error ("function return type cannot be function");
4400       value_type = integer_type_node;
4401     }
4402
4403   /* Make a node of the sort we want.  */
4404   t = make_node (FUNCTION_TYPE);
4405   TREE_TYPE (t) = value_type;
4406   TYPE_ARG_TYPES (t) = arg_types;
4407
4408   /* If we already have such a type, use the old one.  */
4409   hashcode = iterative_hash_object (TYPE_HASH (value_type), hashcode);
4410   hashcode = type_hash_list (arg_types, hashcode);
4411   t = type_hash_canon (hashcode, t);
4412
4413   if (!COMPLETE_TYPE_P (t))
4414     layout_type (t);
4415   return t;
4416 }
4417
4418 /* Build a function type.  The RETURN_TYPE is the type returned by the
4419    function.  If additional arguments are provided, they are
4420    additional argument types.  The list of argument types must always
4421    be terminated by NULL_TREE.  */
4422
4423 tree
4424 build_function_type_list (tree return_type, ...)
4425 {
4426   tree t, args, last;
4427   va_list p;
4428
4429   va_start (p, return_type);
4430
4431   t = va_arg (p, tree);
4432   for (args = NULL_TREE; t != NULL_TREE; t = va_arg (p, tree))
4433     args = tree_cons (NULL_TREE, t, args);
4434
4435   last = args;
4436   args = nreverse (args);
4437   TREE_CHAIN (last) = void_list_node;
4438   args = build_function_type (return_type, args);
4439
4440   va_end (p);
4441   return args;
4442 }
4443
4444 /* Build a METHOD_TYPE for a member of BASETYPE.  The RETTYPE (a TYPE)
4445    and ARGTYPES (a TREE_LIST) are the return type and arguments types
4446    for the method.  An implicit additional parameter (of type
4447    pointer-to-BASETYPE) is added to the ARGTYPES.  */
4448
4449 tree
4450 build_method_type_directly (tree basetype,
4451                             tree rettype,
4452                             tree argtypes)
4453 {
4454   tree t;
4455   tree ptype;
4456   int hashcode = 0;
4457
4458   /* Make a node of the sort we want.  */
4459   t = make_node (METHOD_TYPE);
4460
4461   TYPE_METHOD_BASETYPE (t) = TYPE_MAIN_VARIANT&nbs