OSDN Git Service

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