OSDN Git Service

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