OSDN Git Service

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