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