OSDN Git Service

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