OSDN Git Service

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