OSDN Git Service

2005-12-02 Richard Guenther <rguenther@suse.de>
[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.  */
2695
2696 tree
2697 build0_stat (enum tree_code code, tree tt MEM_STAT_DECL)
2698 {
2699   tree t;
2700
2701   gcc_assert (TREE_CODE_LENGTH (code) == 0);
2702
2703   t = make_node_stat (code PASS_MEM_STAT);
2704   TREE_TYPE (t) = tt;
2705
2706   return t;
2707 }
2708
2709 tree
2710 build1_stat (enum tree_code code, tree type, tree node MEM_STAT_DECL)
2711 {
2712   int length = sizeof (struct tree_exp);
2713 #ifdef GATHER_STATISTICS
2714   tree_node_kind kind;
2715 #endif
2716   tree t;
2717
2718 #ifdef GATHER_STATISTICS
2719   switch (TREE_CODE_CLASS (code))
2720     {
2721     case tcc_statement:  /* an expression with side effects */
2722       kind = s_kind;
2723       break;
2724     case tcc_reference:  /* a reference */
2725       kind = r_kind;
2726       break;
2727     default:
2728       kind = e_kind;
2729       break;
2730     }
2731
2732   tree_node_counts[(int) kind]++;
2733   tree_node_sizes[(int) kind] += length;
2734 #endif
2735
2736   gcc_assert (TREE_CODE_LENGTH (code) == 1);
2737
2738   t = ggc_alloc_zone_pass_stat (length, &tree_zone);
2739
2740   memset (t, 0, sizeof (struct tree_common));
2741
2742   TREE_SET_CODE (t, code);
2743
2744   TREE_TYPE (t) = type;
2745 #ifdef USE_MAPPED_LOCATION
2746   SET_EXPR_LOCATION (t, UNKNOWN_LOCATION);
2747 #else
2748   SET_EXPR_LOCUS (t, NULL);
2749 #endif
2750   TREE_COMPLEXITY (t) = 0;
2751   TREE_OPERAND (t, 0) = node;
2752   TREE_BLOCK (t) = NULL_TREE;
2753   if (node && !TYPE_P (node))
2754     {
2755       TREE_SIDE_EFFECTS (t) = TREE_SIDE_EFFECTS (node);
2756       TREE_READONLY (t) = TREE_READONLY (node);
2757     }
2758
2759   if (TREE_CODE_CLASS (code) == tcc_statement)
2760     TREE_SIDE_EFFECTS (t) = 1;
2761   else switch (code)
2762     {
2763     case VA_ARG_EXPR:
2764       /* All of these have side-effects, no matter what their
2765          operands are.  */
2766       TREE_SIDE_EFFECTS (t) = 1;
2767       TREE_READONLY (t) = 0;
2768       break;
2769
2770     case MISALIGNED_INDIRECT_REF:
2771     case ALIGN_INDIRECT_REF:
2772     case INDIRECT_REF:
2773       /* Whether a dereference is readonly has nothing to do with whether
2774          its operand is readonly.  */
2775       TREE_READONLY (t) = 0;
2776       break;
2777
2778     case ADDR_EXPR:
2779       if (node)
2780         recompute_tree_invarant_for_addr_expr (t);
2781       break;
2782
2783     default:
2784       if (TREE_CODE_CLASS (code) == tcc_unary
2785           && node && !TYPE_P (node)
2786           && TREE_CONSTANT (node))
2787         TREE_CONSTANT (t) = 1;
2788       if (TREE_CODE_CLASS (code) == tcc_unary
2789           && node && TREE_INVARIANT (node))
2790         TREE_INVARIANT (t) = 1;
2791       if (TREE_CODE_CLASS (code) == tcc_reference
2792           && node && TREE_THIS_VOLATILE (node))
2793         TREE_THIS_VOLATILE (t) = 1;
2794       break;
2795     }
2796
2797   return t;
2798 }
2799
2800 #define PROCESS_ARG(N)                  \
2801   do {                                  \
2802     TREE_OPERAND (t, N) = arg##N;       \
2803     if (arg##N &&!TYPE_P (arg##N))      \
2804       {                                 \
2805         if (TREE_SIDE_EFFECTS (arg##N)) \
2806           side_effects = 1;             \
2807         if (!TREE_READONLY (arg##N))    \
2808           read_only = 0;                \
2809         if (!TREE_CONSTANT (arg##N))    \
2810           constant = 0;                 \
2811         if (!TREE_INVARIANT (arg##N))   \
2812           invariant = 0;                \
2813       }                                 \
2814   } while (0)
2815
2816 tree
2817 build2_stat (enum tree_code code, tree tt, tree arg0, tree arg1 MEM_STAT_DECL)
2818 {
2819   bool constant, read_only, side_effects, invariant;
2820   tree t;
2821
2822   gcc_assert (TREE_CODE_LENGTH (code) == 2);
2823
2824   t = make_node_stat (code PASS_MEM_STAT);
2825   TREE_TYPE (t) = tt;
2826
2827   /* Below, we automatically set TREE_SIDE_EFFECTS and TREE_READONLY for the
2828      result based on those same flags for the arguments.  But if the
2829      arguments aren't really even `tree' expressions, we shouldn't be trying
2830      to do this.  */
2831
2832   /* Expressions without side effects may be constant if their
2833      arguments are as well.  */
2834   constant = (TREE_CODE_CLASS (code) == tcc_comparison
2835               || TREE_CODE_CLASS (code) == tcc_binary);
2836   read_only = 1;
2837   side_effects = TREE_SIDE_EFFECTS (t);
2838   invariant = constant;
2839
2840   PROCESS_ARG(0);
2841   PROCESS_ARG(1);
2842
2843   TREE_READONLY (t) = read_only;
2844   TREE_CONSTANT (t) = constant;
2845   TREE_INVARIANT (t) = invariant;
2846   TREE_SIDE_EFFECTS (t) = side_effects;
2847   TREE_THIS_VOLATILE (t)
2848     = (TREE_CODE_CLASS (code) == tcc_reference
2849        && arg0 && TREE_THIS_VOLATILE (arg0));
2850
2851   return t;
2852 }
2853
2854 tree
2855 build3_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
2856              tree arg2 MEM_STAT_DECL)
2857 {
2858   bool constant, read_only, side_effects, invariant;
2859   tree t;
2860
2861   gcc_assert (TREE_CODE_LENGTH (code) == 3);
2862
2863   t = make_node_stat (code PASS_MEM_STAT);
2864   TREE_TYPE (t) = tt;
2865
2866   side_effects = TREE_SIDE_EFFECTS (t);
2867
2868   PROCESS_ARG(0);
2869   PROCESS_ARG(1);
2870   PROCESS_ARG(2);
2871
2872   if (code == CALL_EXPR && !side_effects)
2873     {
2874       tree node;
2875       int i;
2876
2877       /* Calls have side-effects, except those to const or
2878          pure functions.  */
2879       i = call_expr_flags (t);
2880       if (!(i & (ECF_CONST | ECF_PURE)))
2881         side_effects = 1;
2882
2883       /* And even those have side-effects if their arguments do.  */
2884       else for (node = arg1; node; node = TREE_CHAIN (node))
2885         if (TREE_SIDE_EFFECTS (TREE_VALUE (node)))
2886           {
2887             side_effects = 1;
2888             break;
2889           }
2890     }
2891
2892   TREE_SIDE_EFFECTS (t) = side_effects;
2893   TREE_THIS_VOLATILE (t)
2894     = (TREE_CODE_CLASS (code) == tcc_reference
2895        && arg0 && TREE_THIS_VOLATILE (arg0));
2896
2897   return t;
2898 }
2899
2900 tree
2901 build4_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
2902              tree arg2, tree arg3 MEM_STAT_DECL)
2903 {
2904   bool constant, read_only, side_effects, invariant;
2905   tree t;
2906
2907   gcc_assert (TREE_CODE_LENGTH (code) == 4);
2908
2909   t = make_node_stat (code PASS_MEM_STAT);
2910   TREE_TYPE (t) = tt;
2911
2912   side_effects = TREE_SIDE_EFFECTS (t);
2913
2914   PROCESS_ARG(0);
2915   PROCESS_ARG(1);
2916   PROCESS_ARG(2);
2917   PROCESS_ARG(3);
2918
2919   TREE_SIDE_EFFECTS (t) = side_effects;
2920   TREE_THIS_VOLATILE (t)
2921     = (TREE_CODE_CLASS (code) == tcc_reference
2922        && arg0 && TREE_THIS_VOLATILE (arg0));
2923
2924   return t;
2925 }
2926
2927 tree
2928 build7_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
2929              tree arg2, tree arg3, tree arg4, tree arg5,
2930              tree arg6 MEM_STAT_DECL)
2931 {
2932   bool constant, read_only, side_effects, invariant;
2933   tree t;
2934
2935   gcc_assert (code == TARGET_MEM_REF);
2936
2937   t = make_node_stat (code PASS_MEM_STAT);
2938   TREE_TYPE (t) = tt;
2939
2940   side_effects = TREE_SIDE_EFFECTS (t);
2941
2942   PROCESS_ARG(0);
2943   PROCESS_ARG(1);
2944   PROCESS_ARG(2);
2945   PROCESS_ARG(3);
2946   PROCESS_ARG(4);
2947   PROCESS_ARG(5);
2948   PROCESS_ARG(6);
2949
2950   TREE_SIDE_EFFECTS (t) = side_effects;
2951   TREE_THIS_VOLATILE (t) = 0;
2952
2953   return t;
2954 }
2955
2956 /* Similar except don't specify the TREE_TYPE
2957    and leave the TREE_SIDE_EFFECTS as 0.
2958    It is permissible for arguments to be null,
2959    or even garbage if their values do not matter.  */
2960
2961 tree
2962 build_nt (enum tree_code code, ...)
2963 {
2964   tree t;
2965   int length;
2966   int i;
2967   va_list p;
2968
2969   va_start (p, code);
2970
2971   t = make_node (code);
2972   length = TREE_CODE_LENGTH (code);
2973
2974   for (i = 0; i < length; i++)
2975     TREE_OPERAND (t, i) = va_arg (p, tree);
2976
2977   va_end (p);
2978   return t;
2979 }
2980 \f
2981 /* Create a DECL_... node of code CODE, name NAME and data type TYPE.
2982    We do NOT enter this node in any sort of symbol table.
2983
2984    layout_decl is used to set up the decl's storage layout.
2985    Other slots are initialized to 0 or null pointers.  */
2986
2987 tree
2988 build_decl_stat (enum tree_code code, tree name, tree type MEM_STAT_DECL)
2989 {
2990   tree t;
2991
2992   t = make_node_stat (code PASS_MEM_STAT);
2993
2994 /*  if (type == error_mark_node)
2995     type = integer_type_node; */
2996 /* That is not done, deliberately, so that having error_mark_node
2997    as the type can suppress useless errors in the use of this variable.  */
2998
2999   DECL_NAME (t) = name;
3000   TREE_TYPE (t) = type;
3001
3002   if (code == VAR_DECL || code == PARM_DECL || code == RESULT_DECL)
3003     layout_decl (t, 0);
3004   else if (code == FUNCTION_DECL)
3005     DECL_MODE (t) = FUNCTION_MODE;
3006
3007   if (CODE_CONTAINS_STRUCT (code, TS_DECL_WITH_VIS))
3008     {
3009       /* Set default visibility to whatever the user supplied with
3010          visibility_specified depending on #pragma GCC visibility.  */
3011       DECL_VISIBILITY (t) = default_visibility;
3012       DECL_VISIBILITY_SPECIFIED (t) = visibility_options.inpragma;
3013     }
3014
3015   return t;
3016 }
3017
3018 /* Builds and returns function declaration with NAME and TYPE.  */
3019
3020 tree
3021 build_fn_decl (const char *name, tree type)
3022 {
3023   tree id = get_identifier (name);
3024   tree decl = build_decl (FUNCTION_DECL, id, type);
3025
3026   DECL_EXTERNAL (decl) = 1;
3027   TREE_PUBLIC (decl) = 1;
3028   DECL_ARTIFICIAL (decl) = 1;
3029   TREE_NOTHROW (decl) = 1;
3030
3031   return decl;
3032 }
3033
3034 \f
3035 /* BLOCK nodes are used to represent the structure of binding contours
3036    and declarations, once those contours have been exited and their contents
3037    compiled.  This information is used for outputting debugging info.  */
3038
3039 tree
3040 build_block (tree vars, tree subblocks, tree supercontext, tree chain)
3041 {
3042   tree block = make_node (BLOCK);
3043
3044   BLOCK_VARS (block) = vars;
3045   BLOCK_SUBBLOCKS (block) = subblocks;
3046   BLOCK_SUPERCONTEXT (block) = supercontext;
3047   BLOCK_CHAIN (block) = chain;
3048   return block;
3049 }
3050
3051 #if 1 /* ! defined(USE_MAPPED_LOCATION) */
3052 /* ??? gengtype doesn't handle conditionals */
3053 static GTY(()) location_t *last_annotated_node;
3054 #endif
3055
3056 #ifdef USE_MAPPED_LOCATION
3057
3058 expanded_location
3059 expand_location (source_location loc)
3060 {
3061   expanded_location xloc;
3062   if (loc == 0) { xloc.file = NULL; xloc.line = 0;  xloc.column = 0; }
3063   else
3064     {
3065       const struct line_map *map = linemap_lookup (&line_table, loc);
3066       xloc.file = map->to_file;
3067       xloc.line = SOURCE_LINE (map, loc);
3068       xloc.column = SOURCE_COLUMN (map, loc);
3069     };
3070   return xloc;
3071 }
3072
3073 #else
3074
3075 /* Record the exact location where an expression or an identifier were
3076    encountered.  */
3077
3078 void
3079 annotate_with_file_line (tree node, const char *file, int line)
3080 {
3081   /* Roughly one percent of the calls to this function are to annotate
3082      a node with the same information already attached to that node!
3083      Just return instead of wasting memory.  */
3084   if (EXPR_LOCUS (node)
3085       && EXPR_LINENO (node) == line
3086       && (EXPR_FILENAME (node) == file
3087           || !strcmp (EXPR_FILENAME (node), file)))
3088     {
3089       last_annotated_node = EXPR_LOCUS (node);
3090       return;
3091     }
3092
3093   /* In heavily macroized code (such as GCC itself) this single
3094      entry cache can reduce the number of allocations by more
3095      than half.  */
3096   if (last_annotated_node
3097       && last_annotated_node->line == line
3098       && (last_annotated_node->file == file
3099           || !strcmp (last_annotated_node->file, file)))
3100     {
3101       SET_EXPR_LOCUS (node, last_annotated_node);
3102       return;
3103     }
3104
3105   SET_EXPR_LOCUS (node, ggc_alloc (sizeof (location_t)));
3106   EXPR_LINENO (node) = line;
3107   EXPR_FILENAME (node) = file;
3108   last_annotated_node = EXPR_LOCUS (node);
3109 }
3110
3111 void
3112 annotate_with_locus (tree node, location_t locus)
3113 {
3114   annotate_with_file_line (node, locus.file, locus.line);
3115 }
3116 #endif
3117 \f
3118 /* Return a declaration like DDECL except that its DECL_ATTRIBUTES
3119    is ATTRIBUTE.  */
3120
3121 tree
3122 build_decl_attribute_variant (tree ddecl, tree attribute)
3123 {
3124   DECL_ATTRIBUTES (ddecl) = attribute;
3125   return ddecl;
3126 }
3127
3128 /* Borrowed from hashtab.c iterative_hash implementation.  */
3129 #define mix(a,b,c) \
3130 { \
3131   a -= b; a -= c; a ^= (c>>13); \
3132   b -= c; b -= a; b ^= (a<< 8); \
3133   c -= a; c -= b; c ^= ((b&0xffffffff)>>13); \
3134   a -= b; a -= c; a ^= ((c&0xffffffff)>>12); \
3135   b -= c; b -= a; b = (b ^ (a<<16)) & 0xffffffff; \
3136   c -= a; c -= b; c = (c ^ (b>> 5)) & 0xffffffff; \
3137   a -= b; a -= c; a = (a ^ (c>> 3)) & 0xffffffff; \
3138   b -= c; b -= a; b = (b ^ (a<<10)) & 0xffffffff; \
3139   c -= a; c -= b; c = (c ^ (b>>15)) & 0xffffffff; \
3140 }
3141
3142
3143 /* Produce good hash value combining VAL and VAL2.  */
3144 static inline hashval_t
3145 iterative_hash_hashval_t (hashval_t val, hashval_t val2)
3146 {
3147   /* the golden ratio; an arbitrary value.  */
3148   hashval_t a = 0x9e3779b9;
3149
3150   mix (a, val, val2);
3151   return val2;
3152 }
3153
3154 /* Produce good hash value combining PTR and VAL2.  */
3155 static inline hashval_t
3156 iterative_hash_pointer (void *ptr, hashval_t val2)
3157 {
3158   if (sizeof (ptr) == sizeof (hashval_t))
3159     return iterative_hash_hashval_t ((size_t) ptr, val2);
3160   else
3161     {
3162       hashval_t a = (hashval_t) (size_t) ptr;
3163       /* Avoid warnings about shifting of more than the width of the type on
3164          hosts that won't execute this path.  */
3165       int zero = 0;
3166       hashval_t b = (hashval_t) ((size_t) ptr >> (sizeof (hashval_t) * 8 + zero));
3167       mix (a, b, val2);
3168       return val2;
3169     }
3170 }
3171
3172 /* Produce good hash value combining VAL and VAL2.  */
3173 static inline hashval_t
3174 iterative_hash_host_wide_int (HOST_WIDE_INT val, hashval_t val2)
3175 {
3176   if (sizeof (HOST_WIDE_INT) == sizeof (hashval_t))
3177     return iterative_hash_hashval_t (val, val2);
3178   else
3179     {
3180       hashval_t a = (hashval_t) val;
3181       /* Avoid warnings about shifting of more than the width of the type on
3182          hosts that won't execute this path.  */
3183       int zero = 0;
3184       hashval_t b = (hashval_t) (val >> (sizeof (hashval_t) * 8 + zero));
3185       mix (a, b, val2);
3186       if (sizeof (HOST_WIDE_INT) > 2 * sizeof (hashval_t))
3187         {
3188           hashval_t a = (hashval_t) (val >> (sizeof (hashval_t) * 16 + zero));
3189           hashval_t b = (hashval_t) (val >> (sizeof (hashval_t) * 24 + zero));
3190           mix (a, b, val2);
3191         }
3192       return val2;
3193     }
3194 }
3195
3196 /* Return a type like TTYPE except that its TYPE_ATTRIBUTE
3197    is ATTRIBUTE.
3198
3199    Record such modified types already made so we don't make duplicates.  */
3200
3201 tree
3202 build_type_attribute_variant (tree ttype, tree attribute)
3203 {
3204   if (! attribute_list_equal (TYPE_ATTRIBUTES (ttype), attribute))
3205     {
3206       hashval_t hashcode = 0;
3207       tree ntype;
3208       enum tree_code code = TREE_CODE (ttype);
3209
3210       ntype = copy_node (ttype);
3211
3212       TYPE_POINTER_TO (ntype) = 0;
3213       TYPE_REFERENCE_TO (ntype) = 0;
3214       TYPE_ATTRIBUTES (ntype) = attribute;
3215
3216       /* Create a new main variant of TYPE.  */
3217       TYPE_MAIN_VARIANT (ntype) = ntype;
3218       TYPE_NEXT_VARIANT (ntype) = 0;
3219       set_type_quals (ntype, TYPE_UNQUALIFIED);
3220
3221       hashcode = iterative_hash_object (code, hashcode);
3222       if (TREE_TYPE (ntype))
3223         hashcode = iterative_hash_object (TYPE_HASH (TREE_TYPE (ntype)),
3224                                           hashcode);
3225       hashcode = attribute_hash_list (attribute, hashcode);
3226
3227       switch (TREE_CODE (ntype))
3228         {
3229         case FUNCTION_TYPE:
3230           hashcode = type_hash_list (TYPE_ARG_TYPES (ntype), hashcode);
3231           break;
3232         case ARRAY_TYPE:
3233           hashcode = iterative_hash_object (TYPE_HASH (TYPE_DOMAIN (ntype)),
3234                                             hashcode);
3235           break;
3236         case INTEGER_TYPE:
3237           hashcode = iterative_hash_object
3238             (TREE_INT_CST_LOW (TYPE_MAX_VALUE (ntype)), hashcode);
3239           hashcode = iterative_hash_object
3240             (TREE_INT_CST_HIGH (TYPE_MAX_VALUE (ntype)), hashcode);
3241           break;
3242         case REAL_TYPE:
3243           {
3244             unsigned int precision = TYPE_PRECISION (ntype);
3245             hashcode = iterative_hash_object (precision, hashcode);
3246           }
3247           break;
3248         default:
3249           break;
3250         }
3251
3252       ntype = type_hash_canon (hashcode, ntype);
3253       ttype = build_qualified_type (ntype, TYPE_QUALS (ttype));
3254     }
3255
3256   return ttype;
3257 }
3258
3259
3260 /* Return nonzero if IDENT is a valid name for attribute ATTR,
3261    or zero if not.
3262
3263    We try both `text' and `__text__', ATTR may be either one.  */
3264 /* ??? It might be a reasonable simplification to require ATTR to be only
3265    `text'.  One might then also require attribute lists to be stored in
3266    their canonicalized form.  */
3267
3268 static int
3269 is_attribute_with_length_p (const char *attr, int attr_len, tree ident)
3270 {
3271   int ident_len;
3272   const char *p;
3273
3274   if (TREE_CODE (ident) != IDENTIFIER_NODE)
3275     return 0;
3276   
3277   p = IDENTIFIER_POINTER (ident);
3278   ident_len = IDENTIFIER_LENGTH (ident);
3279   
3280   if (ident_len == attr_len
3281       && strcmp (attr, p) == 0)
3282     return 1;
3283
3284   /* If ATTR is `__text__', IDENT must be `text'; and vice versa.  */
3285   if (attr[0] == '_')
3286     {
3287       gcc_assert (attr[1] == '_');
3288       gcc_assert (attr[attr_len - 2] == '_');
3289       gcc_assert (attr[attr_len - 1] == '_');
3290       gcc_assert (attr[1] == '_');
3291       if (ident_len == attr_len - 4
3292           && strncmp (attr + 2, p, attr_len - 4) == 0)
3293         return 1;
3294     }
3295   else
3296     {
3297       if (ident_len == attr_len + 4
3298           && p[0] == '_' && p[1] == '_'
3299           && p[ident_len - 2] == '_' && p[ident_len - 1] == '_'
3300           && strncmp (attr, p + 2, attr_len) == 0)
3301         return 1;
3302     }
3303
3304   return 0;
3305 }
3306
3307 /* Return nonzero if IDENT is a valid name for attribute ATTR,
3308    or zero if not.
3309
3310    We try both `text' and `__text__', ATTR may be either one.  */
3311
3312 int
3313 is_attribute_p (const char *attr, tree ident)
3314 {
3315   return is_attribute_with_length_p (attr, strlen (attr), ident);
3316 }
3317
3318 /* Given an attribute name and a list of attributes, return a pointer to the
3319    attribute's list element if the attribute is part of the list, or NULL_TREE
3320    if not found.  If the attribute appears more than once, this only
3321    returns the first occurrence; the TREE_CHAIN of the return value should
3322    be passed back in if further occurrences are wanted.  */
3323
3324 tree
3325 lookup_attribute (const char *attr_name, tree list)
3326 {
3327   tree l;
3328   size_t attr_len = strlen (attr_name);
3329
3330   for (l = list; l; l = TREE_CHAIN (l))
3331     {
3332       gcc_assert (TREE_CODE (TREE_PURPOSE (l)) == IDENTIFIER_NODE);
3333       if (is_attribute_with_length_p (attr_name, attr_len, TREE_PURPOSE (l)))
3334         return l;
3335     }
3336
3337   return NULL_TREE;
3338 }
3339
3340 /* Return an attribute list that is the union of a1 and a2.  */
3341
3342 tree
3343 merge_attributes (tree a1, tree a2)
3344 {
3345   tree attributes;
3346
3347   /* Either one unset?  Take the set one.  */
3348
3349   if ((attributes = a1) == 0)
3350     attributes = a2;
3351
3352   /* One that completely contains the other?  Take it.  */
3353
3354   else if (a2 != 0 && ! attribute_list_contained (a1, a2))
3355     {
3356       if (attribute_list_contained (a2, a1))
3357         attributes = a2;
3358       else
3359         {
3360           /* Pick the longest list, and hang on the other list.  */
3361
3362           if (list_length (a1) < list_length (a2))
3363             attributes = a2, a2 = a1;
3364
3365           for (; a2 != 0; a2 = TREE_CHAIN (a2))
3366             {
3367               tree a;
3368               for (a = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (a2)),
3369                                          attributes);
3370                    a != NULL_TREE;
3371                    a = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (a2)),
3372                                          TREE_CHAIN (a)))
3373                 {
3374                   if (simple_cst_equal (TREE_VALUE (a), TREE_VALUE (a2)) == 1)
3375                     break;
3376                 }
3377               if (a == NULL_TREE)
3378                 {
3379                   a1 = copy_node (a2);
3380                   TREE_CHAIN (a1) = attributes;
3381                   attributes = a1;
3382                 }
3383             }
3384         }
3385     }
3386   return attributes;
3387 }
3388
3389 /* Given types T1 and T2, merge their attributes and return
3390   the result.  */
3391
3392 tree
3393 merge_type_attributes (tree t1, tree t2)
3394 {
3395   return merge_attributes (TYPE_ATTRIBUTES (t1),
3396                            TYPE_ATTRIBUTES (t2));
3397 }
3398
3399 /* Given decls OLDDECL and NEWDECL, merge their attributes and return
3400    the result.  */
3401
3402 tree
3403 merge_decl_attributes (tree olddecl, tree newdecl)
3404 {
3405   return merge_attributes (DECL_ATTRIBUTES (olddecl),
3406                            DECL_ATTRIBUTES (newdecl));
3407 }
3408
3409 #if TARGET_DLLIMPORT_DECL_ATTRIBUTES
3410
3411 /* Specialization of merge_decl_attributes for various Windows targets.
3412
3413    This handles the following situation:
3414
3415      __declspec (dllimport) int foo;
3416      int foo;
3417
3418    The second instance of `foo' nullifies the dllimport.  */
3419
3420 tree
3421 merge_dllimport_decl_attributes (tree old, tree new)
3422 {
3423   tree a;
3424   int delete_dllimport_p = 1;
3425
3426   /* What we need to do here is remove from `old' dllimport if it doesn't
3427      appear in `new'.  dllimport behaves like extern: if a declaration is
3428      marked dllimport and a definition appears later, then the object
3429      is not dllimport'd.  We also remove a `new' dllimport if the old list
3430      contains dllexport:  dllexport always overrides dllimport, regardless
3431      of the order of declaration.  */     
3432   if (!VAR_OR_FUNCTION_DECL_P (new))
3433     delete_dllimport_p = 0;
3434   else if (DECL_DLLIMPORT_P (new)
3435            && lookup_attribute ("dllexport", DECL_ATTRIBUTES (old)))
3436     { 
3437       DECL_DLLIMPORT_P (new) = 0;
3438       warning (OPT_Wattributes, "%q+D already declared with dllexport attribute: "
3439               "dllimport ignored", new);
3440     }
3441   else if (DECL_DLLIMPORT_P (old) && !DECL_DLLIMPORT_P (new))
3442     {
3443       /* Warn about overriding a symbol that has already been used. eg:
3444            extern int __attribute__ ((dllimport)) foo;
3445            int* bar () {return &foo;}
3446            int foo;
3447       */
3448       if (TREE_USED (old))
3449         {
3450           warning (0, "%q+D redeclared without dllimport attribute "
3451                    "after being referenced with dll linkage", new);
3452           /* If we have used a variable's address with dllimport linkage,
3453               keep the old DECL_DLLIMPORT_P flag: the ADDR_EXPR using the
3454               decl may already have had TREE_INVARIANT and TREE_CONSTANT
3455               computed.
3456               We still remove the attribute so that assembler code refers
3457               to '&foo rather than '_imp__foo'.  */
3458           if (TREE_CODE (old) == VAR_DECL && TREE_ADDRESSABLE (old))
3459             DECL_DLLIMPORT_P (new) = 1;
3460         }
3461
3462       /* Let an inline definition silently override the external reference,
3463          but otherwise warn about attribute inconsistency.  */ 
3464       else if (TREE_CODE (new) == VAR_DECL
3465                || !DECL_DECLARED_INLINE_P (new))
3466         warning (OPT_Wattributes, "%q+D redeclared without dllimport attribute: "
3467                   "previous dllimport ignored", new);
3468     }
3469   else
3470     delete_dllimport_p = 0;
3471
3472   a = merge_attributes (DECL_ATTRIBUTES (old), DECL_ATTRIBUTES (new));
3473
3474   if (delete_dllimport_p) 
3475     {
3476       tree prev, t;
3477       const size_t attr_len = strlen ("dllimport"); 
3478      
3479       /* Scan the list for dllimport and delete it.  */
3480       for (prev = NULL_TREE, t = a; t; prev = t, t = TREE_CHAIN (t))
3481         {
3482           if (is_attribute_with_length_p ("dllimport", attr_len,
3483                                           TREE_PURPOSE (t)))
3484             {
3485               if (prev == NULL_TREE)
3486                 a = TREE_CHAIN (a);
3487               else
3488                 TREE_CHAIN (prev) = TREE_CHAIN (t);
3489               break;
3490             }
3491         }
3492     }
3493
3494   return a;
3495 }
3496
3497 /* Handle a "dllimport" or "dllexport" attribute; arguments as in
3498    struct attribute_spec.handler.  */
3499
3500 tree
3501 handle_dll_attribute (tree * pnode, tree name, tree args, int flags,
3502                       bool *no_add_attrs)
3503 {
3504   tree node = *pnode;
3505
3506   /* These attributes may apply to structure and union types being created,
3507      but otherwise should pass to the declaration involved.  */
3508   if (!DECL_P (node))
3509     {
3510       if (flags & ((int) ATTR_FLAG_DECL_NEXT | (int) ATTR_FLAG_FUNCTION_NEXT
3511                    | (int) ATTR_FLAG_ARRAY_NEXT))
3512         {
3513           *no_add_attrs = true;
3514           return tree_cons (name, args, NULL_TREE);
3515         }
3516       if (TREE_CODE (node) != RECORD_TYPE && TREE_CODE (node) != UNION_TYPE)
3517         {
3518           warning (OPT_Wattributes, "%qs attribute ignored",
3519                    IDENTIFIER_POINTER (name));
3520           *no_add_attrs = true;
3521         }
3522
3523       return NULL_TREE;
3524     }
3525
3526   /* Report error on dllimport ambiguities seen now before they cause
3527      any damage.  */
3528   if (is_attribute_p ("dllimport", name))
3529     {
3530       /* Honor any target-specific overrides. */ 
3531       if (!targetm.valid_dllimport_attribute_p (node))
3532         *no_add_attrs = true;
3533
3534      else if (TREE_CODE (node) == FUNCTION_DECL
3535                 && DECL_DECLARED_INLINE_P (node))
3536         {
3537           warning (OPT_Wattributes, "inline function %q+D declared as "
3538                   " dllimport: attribute ignored", node); 
3539           *no_add_attrs = true;
3540         }
3541       /* Like MS, treat definition of dllimported variables and
3542          non-inlined functions on declaration as syntax errors. */
3543      else if (TREE_CODE (node) == FUNCTION_DECL && DECL_INITIAL (node))
3544         {
3545           error ("function %q+D definition is marked dllimport", node);
3546           *no_add_attrs = true;
3547         }
3548
3549      else if (TREE_CODE (node) == VAR_DECL)
3550         {
3551           if (DECL_INITIAL (node))
3552             {
3553               error ("variable %q+D definition is marked dllimport",
3554                      node);
3555               *no_add_attrs = true;
3556             }
3557
3558           /* `extern' needn't be specified with dllimport.
3559              Specify `extern' now and hope for the best.  Sigh.  */
3560           DECL_EXTERNAL (node) = 1;
3561           /* Also, implicitly give dllimport'd variables declared within
3562              a function global scope, unless declared static.  */
3563           if (current_function_decl != NULL_TREE && !TREE_STATIC (node))
3564             TREE_PUBLIC (node) = 1;
3565         }
3566
3567       if (*no_add_attrs == false)
3568         DECL_DLLIMPORT_P (node) = 1;
3569     }
3570
3571   /*  Report error if symbol is not accessible at global scope.  */
3572   if (!TREE_PUBLIC (node)
3573       && (TREE_CODE (node) == VAR_DECL
3574           || TREE_CODE (node) == FUNCTION_DECL))
3575     {
3576       error ("external linkage required for symbol %q+D because of "
3577              "%qs attribute", node, IDENTIFIER_POINTER (name));
3578       *no_add_attrs = true;
3579     }
3580
3581   return NULL_TREE;
3582 }
3583
3584 #endif /* TARGET_DLLIMPORT_DECL_ATTRIBUTES  */
3585 \f
3586 /* Set the type qualifiers for TYPE to TYPE_QUALS, which is a bitmask
3587    of the various TYPE_QUAL values.  */
3588
3589 static void
3590 set_type_quals (tree type, int type_quals)
3591 {
3592   TYPE_READONLY (type) = (type_quals & TYPE_QUAL_CONST) != 0;
3593   TYPE_VOLATILE (type) = (type_quals & TYPE_QUAL_VOLATILE) != 0;
3594   TYPE_RESTRICT (type) = (type_quals & TYPE_QUAL_RESTRICT) != 0;
3595 }
3596
3597 /* Returns true iff cand is equivalent to base with type_quals.  */
3598
3599 bool
3600 check_qualified_type (tree cand, tree base, int type_quals)
3601 {
3602   return (TYPE_QUALS (cand) == type_quals
3603           && TYPE_NAME (cand) == TYPE_NAME (base)
3604           /* Apparently this is needed for Objective-C.  */
3605           && TYPE_CONTEXT (cand) == TYPE_CONTEXT (base)
3606           && attribute_list_equal (TYPE_ATTRIBUTES (cand),
3607                                    TYPE_ATTRIBUTES (base)));
3608 }
3609
3610 /* Return a version of the TYPE, qualified as indicated by the
3611    TYPE_QUALS, if one exists.  If no qualified version exists yet,
3612    return NULL_TREE.  */
3613
3614 tree
3615 get_qualified_type (tree type, int type_quals)
3616 {
3617   tree t;
3618
3619   if (TYPE_QUALS (type) == type_quals)
3620     return type;
3621
3622   /* Search the chain of variants to see if there is already one there just
3623      like the one we need to have.  If so, use that existing one.  We must
3624      preserve the TYPE_NAME, since there is code that depends on this.  */
3625   for (t = TYPE_MAIN_VARIANT (type); t; t = TYPE_NEXT_VARIANT (t))
3626     if (check_qualified_type (t, type, type_quals))
3627       return t;
3628
3629   return NULL_TREE;
3630 }
3631
3632 /* Like get_qualified_type, but creates the type if it does not
3633    exist.  This function never returns NULL_TREE.  */
3634
3635 tree
3636 build_qualified_type (tree type, int type_quals)
3637 {
3638   tree t;
3639
3640   /* See if we already have the appropriate qualified variant.  */
3641   t = get_qualified_type (type, type_quals);
3642
3643   /* If not, build it.  */
3644   if (!t)
3645     {
3646       t = build_variant_type_copy (type);
3647       set_type_quals (t, type_quals);
3648
3649       /* If it's a pointer type, the new variant points to the same type.  */
3650       if (TREE_CODE (type) == POINTER_TYPE)
3651         {
3652           TYPE_NEXT_PTR_TO (t) = TYPE_NEXT_PTR_TO (type);
3653           TYPE_NEXT_PTR_TO (type) = t;
3654         }
3655
3656       /* Same for a reference type.  */
3657       else if (TREE_CODE (type) == REFERENCE_TYPE)
3658         {
3659           TYPE_NEXT_REF_TO (t) = TYPE_NEXT_REF_TO (type);
3660           TYPE_NEXT_REF_TO (type) = t;
3661         }
3662     }
3663
3664   return t;
3665 }
3666
3667 /* Create a new distinct copy of TYPE.  The new type is made its own
3668    MAIN_VARIANT.  */
3669
3670 tree
3671 build_distinct_type_copy (tree type)
3672 {
3673   tree t = copy_node (type);
3674   
3675   TYPE_POINTER_TO (t) = 0;
3676   TYPE_REFERENCE_TO (t) = 0;
3677
3678   /* Make it its own variant.  */
3679   TYPE_MAIN_VARIANT (t) = t;
3680   TYPE_NEXT_VARIANT (t) = 0;
3681   
3682   return t;
3683 }
3684
3685 /* Create a new variant of TYPE, equivalent but distinct.
3686    This is so the caller can modify it.  */
3687
3688 tree
3689 build_variant_type_copy (tree type)
3690 {
3691   tree t, m = TYPE_MAIN_VARIANT (type);
3692
3693   t = build_distinct_type_copy (type);
3694   
3695   /* Add the new type to the chain of variants of TYPE.  */
3696   TYPE_NEXT_VARIANT (t) = TYPE_NEXT_VARIANT (m);
3697   TYPE_NEXT_VARIANT (m) = t;
3698   TYPE_MAIN_VARIANT (t) = m;
3699
3700   return t;
3701 }
3702 \f
3703 /* Return true if the from tree in both tree maps are equal.  */
3704
3705 int
3706 tree_map_eq (const void *va, const void *vb)
3707 {
3708   const struct tree_map  *a = va, *b = vb;
3709   return (a->from == b->from);
3710 }
3711
3712 /* Hash a from tree in a tree_map.  */
3713
3714 unsigned int
3715 tree_map_hash (const void *item)
3716 {
3717   return (((const struct tree_map *) item)->hash);
3718 }
3719
3720 /* Return true if this tree map structure is marked for garbage collection
3721    purposes.  We simply return true if the from tree is marked, so that this
3722    structure goes away when the from tree goes away.  */
3723
3724 int
3725 tree_map_marked_p (const void *p)
3726 {
3727   tree from = ((struct tree_map *) p)->from;
3728
3729   return ggc_marked_p (from);
3730 }
3731
3732 /* Return true if the trees in the tree_int_map *'s VA and VB are equal.  */
3733
3734 static int
3735 tree_int_map_eq (const void *va, const void *vb)
3736 {
3737   const struct tree_int_map  *a = va, *b = vb;
3738   return (a->from == b->from);
3739 }
3740
3741 /* Hash a from tree in the tree_int_map * ITEM.  */
3742
3743 static unsigned int
3744 tree_int_map_hash (const void *item)
3745 {
3746   return htab_hash_pointer (((const struct tree_int_map *)item)->from);
3747 }
3748
3749 /* Return true if this tree int map structure is marked for garbage collection
3750    purposes.  We simply return true if the from tree_int_map *P's from tree is marked, so that this
3