OSDN Git Service

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