2007-05-27 H.J. Lu <hongjiu.lu@intel.com>
[official-gcc.git] / gcc / tree.c
blob2d96bd7af8747c2a30f041fd4b77c160cfe63ec3
1 /* Language-independent node constructors for parse phase of GNU compiler.
2 Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007
4 Free Software Foundation, Inc.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 2, or (at your option) any later
11 version.
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.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING. If not, write to the Free
20 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
21 02110-1301, USA. */
23 /* This file contains the low level primitives for operating on tree nodes,
24 including allocation, list operations, interning of identifiers,
25 construction of data type nodes and statement nodes,
26 and construction of type conversion nodes. It also contains
27 tables index by tree code that describe how to take apart
28 nodes of that code.
30 It is intended to be language-independent, but occasionally
31 calls language-dependent routines defined (for C) in typecheck.c. */
33 #include "config.h"
34 #include "system.h"
35 #include "coretypes.h"
36 #include "tm.h"
37 #include "flags.h"
38 #include "tree.h"
39 #include "real.h"
40 #include "tm_p.h"
41 #include "function.h"
42 #include "obstack.h"
43 #include "toplev.h"
44 #include "ggc.h"
45 #include "hashtab.h"
46 #include "output.h"
47 #include "target.h"
48 #include "langhooks.h"
49 #include "tree-iterator.h"
50 #include "basic-block.h"
51 #include "tree-flow.h"
52 #include "params.h"
53 #include "pointer-set.h"
55 /* Each tree code class has an associated string representation.
56 These must correspond to the tree_code_class entries. */
58 const char *const tree_code_class_strings[] =
60 "exceptional",
61 "constant",
62 "type",
63 "declaration",
64 "reference",
65 "comparison",
66 "unary",
67 "binary",
68 "statement",
69 "vl_exp",
70 "expression",
71 "gimple_stmt"
74 /* obstack.[ch] explicitly declined to prototype this. */
75 extern int _obstack_allocated_p (struct obstack *h, void *obj);
77 #ifdef GATHER_STATISTICS
78 /* Statistics-gathering stuff. */
80 int tree_node_counts[(int) all_kinds];
81 int tree_node_sizes[(int) all_kinds];
83 /* Keep in sync with tree.h:enum tree_node_kind. */
84 static const char * const tree_node_kind_names[] = {
85 "decls",
86 "types",
87 "blocks",
88 "stmts",
89 "refs",
90 "exprs",
91 "constants",
92 "identifiers",
93 "perm_tree_lists",
94 "temp_tree_lists",
95 "vecs",
96 "binfos",
97 "phi_nodes",
98 "ssa names",
99 "constructors",
100 "random kinds",
101 "lang_decl kinds",
102 "lang_type kinds",
103 "omp clauses",
104 "gimple statements"
106 #endif /* GATHER_STATISTICS */
108 /* Unique id for next decl created. */
109 static GTY(()) int next_decl_uid;
110 /* Unique id for next type created. */
111 static GTY(()) int next_type_uid = 1;
113 /* Since we cannot rehash a type after it is in the table, we have to
114 keep the hash code. */
116 struct type_hash GTY(())
118 unsigned long hash;
119 tree type;
122 /* Initial size of the hash table (rounded to next prime). */
123 #define TYPE_HASH_INITIAL_SIZE 1000
125 /* Now here is the hash table. When recording a type, it is added to
126 the slot whose index is the hash code. Note that the hash table is
127 used for several kinds of types (function types, array types and
128 array index range types, for now). While all these live in the
129 same table, they are completely independent, and the hash code is
130 computed differently for each of these. */
132 static GTY ((if_marked ("type_hash_marked_p"), param_is (struct type_hash)))
133 htab_t type_hash_table;
135 /* Hash table and temporary node for larger integer const values. */
136 static GTY (()) tree int_cst_node;
137 static GTY ((if_marked ("ggc_marked_p"), param_is (union tree_node)))
138 htab_t int_cst_hash_table;
140 /* General tree->tree mapping structure for use in hash tables. */
143 static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map)))
144 htab_t debug_expr_for_decl;
146 static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map)))
147 htab_t value_expr_for_decl;
149 static GTY ((if_marked ("tree_priority_map_marked_p"),
150 param_is (struct tree_priority_map)))
151 htab_t init_priority_for_decl;
153 static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map)))
154 htab_t restrict_base_for_decl;
156 static void set_type_quals (tree, int);
157 static int type_hash_eq (const void *, const void *);
158 static hashval_t type_hash_hash (const void *);
159 static hashval_t int_cst_hash_hash (const void *);
160 static int int_cst_hash_eq (const void *, const void *);
161 static void print_type_hash_statistics (void);
162 static void print_debug_expr_statistics (void);
163 static void print_value_expr_statistics (void);
164 static int type_hash_marked_p (const void *);
165 static unsigned int type_hash_list (tree, hashval_t);
166 static unsigned int attribute_hash_list (tree, hashval_t);
168 tree global_trees[TI_MAX];
169 tree integer_types[itk_none];
171 unsigned char tree_contains_struct[MAX_TREE_CODES][64];
173 /* Number of operands for each OpenMP clause. */
174 unsigned const char omp_clause_num_ops[] =
176 0, /* OMP_CLAUSE_ERROR */
177 1, /* OMP_CLAUSE_PRIVATE */
178 1, /* OMP_CLAUSE_SHARED */
179 1, /* OMP_CLAUSE_FIRSTPRIVATE */
180 1, /* OMP_CLAUSE_LASTPRIVATE */
181 4, /* OMP_CLAUSE_REDUCTION */
182 1, /* OMP_CLAUSE_COPYIN */
183 1, /* OMP_CLAUSE_COPYPRIVATE */
184 1, /* OMP_CLAUSE_IF */
185 1, /* OMP_CLAUSE_NUM_THREADS */
186 1, /* OMP_CLAUSE_SCHEDULE */
187 0, /* OMP_CLAUSE_NOWAIT */
188 0, /* OMP_CLAUSE_ORDERED */
189 0 /* OMP_CLAUSE_DEFAULT */
192 const char * const omp_clause_code_name[] =
194 "error_clause",
195 "private",
196 "shared",
197 "firstprivate",
198 "lastprivate",
199 "reduction",
200 "copyin",
201 "copyprivate",
202 "if",
203 "num_threads",
204 "schedule",
205 "nowait",
206 "ordered",
207 "default"
210 /* Init tree.c. */
212 void
213 init_ttree (void)
215 /* Initialize the hash table of types. */
216 type_hash_table = htab_create_ggc (TYPE_HASH_INITIAL_SIZE, type_hash_hash,
217 type_hash_eq, 0);
219 debug_expr_for_decl = htab_create_ggc (512, tree_map_hash,
220 tree_map_eq, 0);
222 value_expr_for_decl = htab_create_ggc (512, tree_map_hash,
223 tree_map_eq, 0);
224 init_priority_for_decl = htab_create_ggc (512, tree_priority_map_hash,
225 tree_priority_map_eq, 0);
226 restrict_base_for_decl = htab_create_ggc (256, tree_map_hash,
227 tree_map_eq, 0);
229 int_cst_hash_table = htab_create_ggc (1024, int_cst_hash_hash,
230 int_cst_hash_eq, NULL);
232 int_cst_node = make_node (INTEGER_CST);
234 tree_contains_struct[FUNCTION_DECL][TS_DECL_NON_COMMON] = 1;
235 tree_contains_struct[TRANSLATION_UNIT_DECL][TS_DECL_NON_COMMON] = 1;
236 tree_contains_struct[TYPE_DECL][TS_DECL_NON_COMMON] = 1;
239 tree_contains_struct[CONST_DECL][TS_DECL_COMMON] = 1;
240 tree_contains_struct[VAR_DECL][TS_DECL_COMMON] = 1;
241 tree_contains_struct[PARM_DECL][TS_DECL_COMMON] = 1;
242 tree_contains_struct[RESULT_DECL][TS_DECL_COMMON] = 1;
243 tree_contains_struct[FUNCTION_DECL][TS_DECL_COMMON] = 1;
244 tree_contains_struct[TYPE_DECL][TS_DECL_COMMON] = 1;
245 tree_contains_struct[TRANSLATION_UNIT_DECL][TS_DECL_COMMON] = 1;
246 tree_contains_struct[LABEL_DECL][TS_DECL_COMMON] = 1;
247 tree_contains_struct[FIELD_DECL][TS_DECL_COMMON] = 1;
250 tree_contains_struct[CONST_DECL][TS_DECL_WRTL] = 1;
251 tree_contains_struct[VAR_DECL][TS_DECL_WRTL] = 1;
252 tree_contains_struct[PARM_DECL][TS_DECL_WRTL] = 1;
253 tree_contains_struct[RESULT_DECL][TS_DECL_WRTL] = 1;
254 tree_contains_struct[FUNCTION_DECL][TS_DECL_WRTL] = 1;
255 tree_contains_struct[LABEL_DECL][TS_DECL_WRTL] = 1;
257 tree_contains_struct[CONST_DECL][TS_DECL_MINIMAL] = 1;
258 tree_contains_struct[VAR_DECL][TS_DECL_MINIMAL] = 1;
259 tree_contains_struct[PARM_DECL][TS_DECL_MINIMAL] = 1;
260 tree_contains_struct[RESULT_DECL][TS_DECL_MINIMAL] = 1;
261 tree_contains_struct[FUNCTION_DECL][TS_DECL_MINIMAL] = 1;
262 tree_contains_struct[TYPE_DECL][TS_DECL_MINIMAL] = 1;
263 tree_contains_struct[TRANSLATION_UNIT_DECL][TS_DECL_MINIMAL] = 1;
264 tree_contains_struct[LABEL_DECL][TS_DECL_MINIMAL] = 1;
265 tree_contains_struct[FIELD_DECL][TS_DECL_MINIMAL] = 1;
266 tree_contains_struct[STRUCT_FIELD_TAG][TS_DECL_MINIMAL] = 1;
267 tree_contains_struct[NAME_MEMORY_TAG][TS_DECL_MINIMAL] = 1;
268 tree_contains_struct[SYMBOL_MEMORY_TAG][TS_DECL_MINIMAL] = 1;
269 tree_contains_struct[MEMORY_PARTITION_TAG][TS_DECL_MINIMAL] = 1;
271 tree_contains_struct[STRUCT_FIELD_TAG][TS_MEMORY_TAG] = 1;
272 tree_contains_struct[NAME_MEMORY_TAG][TS_MEMORY_TAG] = 1;
273 tree_contains_struct[SYMBOL_MEMORY_TAG][TS_MEMORY_TAG] = 1;
274 tree_contains_struct[MEMORY_PARTITION_TAG][TS_MEMORY_TAG] = 1;
276 tree_contains_struct[STRUCT_FIELD_TAG][TS_STRUCT_FIELD_TAG] = 1;
277 tree_contains_struct[MEMORY_PARTITION_TAG][TS_MEMORY_PARTITION_TAG] = 1;
279 tree_contains_struct[VAR_DECL][TS_DECL_WITH_VIS] = 1;
280 tree_contains_struct[FUNCTION_DECL][TS_DECL_WITH_VIS] = 1;
281 tree_contains_struct[TYPE_DECL][TS_DECL_WITH_VIS] = 1;
282 tree_contains_struct[TRANSLATION_UNIT_DECL][TS_DECL_WITH_VIS] = 1;
284 tree_contains_struct[VAR_DECL][TS_VAR_DECL] = 1;
285 tree_contains_struct[FIELD_DECL][TS_FIELD_DECL] = 1;
286 tree_contains_struct[PARM_DECL][TS_PARM_DECL] = 1;
287 tree_contains_struct[LABEL_DECL][TS_LABEL_DECL] = 1;
288 tree_contains_struct[RESULT_DECL][TS_RESULT_DECL] = 1;
289 tree_contains_struct[CONST_DECL][TS_CONST_DECL] = 1;
290 tree_contains_struct[TYPE_DECL][TS_TYPE_DECL] = 1;
291 tree_contains_struct[FUNCTION_DECL][TS_FUNCTION_DECL] = 1;
293 lang_hooks.init_ts ();
297 /* The name of the object as the assembler will see it (but before any
298 translations made by ASM_OUTPUT_LABELREF). Often this is the same
299 as DECL_NAME. It is an IDENTIFIER_NODE. */
300 tree
301 decl_assembler_name (tree decl)
303 if (!DECL_ASSEMBLER_NAME_SET_P (decl))
304 lang_hooks.set_decl_assembler_name (decl);
305 return DECL_WITH_VIS_CHECK (decl)->decl_with_vis.assembler_name;
308 /* Compare ASMNAME with the DECL_ASSEMBLER_NAME of DECL. */
310 bool
311 decl_assembler_name_equal (tree decl, tree asmname)
313 tree decl_asmname = DECL_ASSEMBLER_NAME (decl);
315 if (decl_asmname == asmname)
316 return true;
318 /* If the target assembler name was set by the user, things are trickier.
319 We have a leading '*' to begin with. After that, it's arguable what
320 is the correct thing to do with -fleading-underscore. Arguably, we've
321 historically been doing the wrong thing in assemble_alias by always
322 printing the leading underscore. Since we're not changing that, make
323 sure user_label_prefix follows the '*' before matching. */
324 if (IDENTIFIER_POINTER (decl_asmname)[0] == '*')
326 const char *decl_str = IDENTIFIER_POINTER (decl_asmname) + 1;
327 size_t ulp_len = strlen (user_label_prefix);
329 if (ulp_len == 0)
331 else if (strncmp (decl_str, user_label_prefix, ulp_len) == 0)
332 decl_str += ulp_len;
333 else
334 return false;
336 return strcmp (decl_str, IDENTIFIER_POINTER (asmname)) == 0;
339 return false;
342 /* Compute the number of bytes occupied by a tree with code CODE.
343 This function cannot be used for nodes that have variable sizes,
344 including TREE_VEC, PHI_NODE, STRING_CST, and CALL_EXPR. */
345 size_t
346 tree_code_size (enum tree_code code)
348 switch (TREE_CODE_CLASS (code))
350 case tcc_declaration: /* A decl node */
352 switch (code)
354 case FIELD_DECL:
355 return sizeof (struct tree_field_decl);
356 case PARM_DECL:
357 return sizeof (struct tree_parm_decl);
358 case VAR_DECL:
359 return sizeof (struct tree_var_decl);
360 case LABEL_DECL:
361 return sizeof (struct tree_label_decl);
362 case RESULT_DECL:
363 return sizeof (struct tree_result_decl);
364 case CONST_DECL:
365 return sizeof (struct tree_const_decl);
366 case TYPE_DECL:
367 return sizeof (struct tree_type_decl);
368 case FUNCTION_DECL:
369 return sizeof (struct tree_function_decl);
370 case NAME_MEMORY_TAG:
371 case SYMBOL_MEMORY_TAG:
372 return sizeof (struct tree_memory_tag);
373 case STRUCT_FIELD_TAG:
374 return sizeof (struct tree_struct_field_tag);
375 case MEMORY_PARTITION_TAG:
376 return sizeof (struct tree_memory_partition_tag);
377 default:
378 return sizeof (struct tree_decl_non_common);
382 case tcc_type: /* a type node */
383 return sizeof (struct tree_type);
385 case tcc_reference: /* a reference */
386 case tcc_expression: /* an expression */
387 case tcc_statement: /* an expression with side effects */
388 case tcc_comparison: /* a comparison expression */
389 case tcc_unary: /* a unary arithmetic expression */
390 case tcc_binary: /* a binary arithmetic expression */
391 return (sizeof (struct tree_exp)
392 + (TREE_CODE_LENGTH (code) - 1) * sizeof (tree));
394 case tcc_gimple_stmt:
395 return (sizeof (struct gimple_stmt)
396 + (TREE_CODE_LENGTH (code) - 1) * sizeof (char *));
398 case tcc_constant: /* a constant */
399 switch (code)
401 case INTEGER_CST: return sizeof (struct tree_int_cst);
402 case REAL_CST: return sizeof (struct tree_real_cst);
403 case COMPLEX_CST: return sizeof (struct tree_complex);
404 case VECTOR_CST: return sizeof (struct tree_vector);
405 case STRING_CST: gcc_unreachable ();
406 default:
407 return lang_hooks.tree_size (code);
410 case tcc_exceptional: /* something random, like an identifier. */
411 switch (code)
413 case IDENTIFIER_NODE: return lang_hooks.identifier_size;
414 case TREE_LIST: return sizeof (struct tree_list);
416 case ERROR_MARK:
417 case PLACEHOLDER_EXPR: return sizeof (struct tree_common);
419 case TREE_VEC:
420 case OMP_CLAUSE:
421 case PHI_NODE: gcc_unreachable ();
423 case SSA_NAME: return sizeof (struct tree_ssa_name);
425 case STATEMENT_LIST: return sizeof (struct tree_statement_list);
426 case BLOCK: return sizeof (struct tree_block);
427 case VALUE_HANDLE: return sizeof (struct tree_value_handle);
428 case CONSTRUCTOR: return sizeof (struct tree_constructor);
430 default:
431 return lang_hooks.tree_size (code);
434 default:
435 gcc_unreachable ();
439 /* Compute the number of bytes occupied by NODE. This routine only
440 looks at TREE_CODE, except for those nodes that have variable sizes. */
441 size_t
442 tree_size (tree node)
444 enum tree_code code = TREE_CODE (node);
445 switch (code)
447 case PHI_NODE:
448 return (sizeof (struct tree_phi_node)
449 + (PHI_ARG_CAPACITY (node) - 1) * sizeof (struct phi_arg_d));
451 case TREE_BINFO:
452 return (offsetof (struct tree_binfo, base_binfos)
453 + VEC_embedded_size (tree, BINFO_N_BASE_BINFOS (node)));
455 case TREE_VEC:
456 return (sizeof (struct tree_vec)
457 + (TREE_VEC_LENGTH (node) - 1) * sizeof (tree));
459 case STRING_CST:
460 return TREE_STRING_LENGTH (node) + offsetof (struct tree_string, str) + 1;
462 case OMP_CLAUSE:
463 return (sizeof (struct tree_omp_clause)
464 + (omp_clause_num_ops[OMP_CLAUSE_CODE (node)] - 1)
465 * sizeof (tree));
467 default:
468 if (TREE_CODE_CLASS (code) == tcc_vl_exp)
469 return (sizeof (struct tree_exp)
470 + (VL_EXP_OPERAND_LENGTH (node) - 1) * sizeof (tree));
471 else
472 return tree_code_size (code);
476 /* Return a newly allocated node of code CODE. For decl and type
477 nodes, some other fields are initialized. The rest of the node is
478 initialized to zero. This function cannot be used for PHI_NODE,
479 TREE_VEC or OMP_CLAUSE nodes, which is enforced by asserts in
480 tree_code_size.
482 Achoo! I got a code in the node. */
484 tree
485 make_node_stat (enum tree_code code MEM_STAT_DECL)
487 tree t;
488 enum tree_code_class type = TREE_CODE_CLASS (code);
489 size_t length = tree_code_size (code);
490 #ifdef GATHER_STATISTICS
491 tree_node_kind kind;
493 switch (type)
495 case tcc_declaration: /* A decl node */
496 kind = d_kind;
497 break;
499 case tcc_type: /* a type node */
500 kind = t_kind;
501 break;
503 case tcc_statement: /* an expression with side effects */
504 kind = s_kind;
505 break;
507 case tcc_reference: /* a reference */
508 kind = r_kind;
509 break;
511 case tcc_expression: /* an expression */
512 case tcc_comparison: /* a comparison expression */
513 case tcc_unary: /* a unary arithmetic expression */
514 case tcc_binary: /* a binary arithmetic expression */
515 kind = e_kind;
516 break;
518 case tcc_constant: /* a constant */
519 kind = c_kind;
520 break;
522 case tcc_gimple_stmt:
523 kind = gimple_stmt_kind;
524 break;
526 case tcc_exceptional: /* something random, like an identifier. */
527 switch (code)
529 case IDENTIFIER_NODE:
530 kind = id_kind;
531 break;
533 case TREE_VEC:
534 kind = vec_kind;
535 break;
537 case TREE_BINFO:
538 kind = binfo_kind;
539 break;
541 case PHI_NODE:
542 kind = phi_kind;
543 break;
545 case SSA_NAME:
546 kind = ssa_name_kind;
547 break;
549 case BLOCK:
550 kind = b_kind;
551 break;
553 case CONSTRUCTOR:
554 kind = constr_kind;
555 break;
557 default:
558 kind = x_kind;
559 break;
561 break;
563 default:
564 gcc_unreachable ();
567 tree_node_counts[(int) kind]++;
568 tree_node_sizes[(int) kind] += length;
569 #endif
571 if (code == IDENTIFIER_NODE)
572 t = ggc_alloc_zone_pass_stat (length, &tree_id_zone);
573 else
574 t = ggc_alloc_zone_pass_stat (length, &tree_zone);
576 memset (t, 0, length);
578 TREE_SET_CODE (t, code);
580 switch (type)
582 case tcc_statement:
583 TREE_SIDE_EFFECTS (t) = 1;
584 break;
586 case tcc_declaration:
587 if (CODE_CONTAINS_STRUCT (code, TS_DECL_WITH_VIS))
588 DECL_IN_SYSTEM_HEADER (t) = in_system_header;
589 if (CODE_CONTAINS_STRUCT (code, TS_DECL_COMMON))
591 if (code != FUNCTION_DECL)
592 DECL_ALIGN (t) = 1;
593 DECL_USER_ALIGN (t) = 0;
594 /* We have not yet computed the alias set for this declaration. */
595 DECL_POINTER_ALIAS_SET (t) = -1;
597 DECL_SOURCE_LOCATION (t) = input_location;
598 DECL_UID (t) = next_decl_uid++;
600 break;
602 case tcc_type:
603 TYPE_UID (t) = next_type_uid++;
604 TYPE_ALIGN (t) = BITS_PER_UNIT;
605 TYPE_USER_ALIGN (t) = 0;
606 TYPE_MAIN_VARIANT (t) = t;
607 TYPE_CANONICAL (t) = t;
609 /* Default to no attributes for type, but let target change that. */
610 TYPE_ATTRIBUTES (t) = NULL_TREE;
611 targetm.set_default_type_attributes (t);
613 /* We have not yet computed the alias set for this type. */
614 TYPE_ALIAS_SET (t) = -1;
615 break;
617 case tcc_constant:
618 TREE_CONSTANT (t) = 1;
619 TREE_INVARIANT (t) = 1;
620 break;
622 case tcc_expression:
623 switch (code)
625 case INIT_EXPR:
626 case MODIFY_EXPR:
627 case VA_ARG_EXPR:
628 case PREDECREMENT_EXPR:
629 case PREINCREMENT_EXPR:
630 case POSTDECREMENT_EXPR:
631 case POSTINCREMENT_EXPR:
632 /* All of these have side-effects, no matter what their
633 operands are. */
634 TREE_SIDE_EFFECTS (t) = 1;
635 break;
637 default:
638 break;
640 break;
642 case tcc_gimple_stmt:
643 switch (code)
645 case GIMPLE_MODIFY_STMT:
646 TREE_SIDE_EFFECTS (t) = 1;
647 break;
649 default:
650 break;
653 default:
654 /* Other classes need no special treatment. */
655 break;
658 return t;
661 /* Return a new node with the same contents as NODE except that its
662 TREE_CHAIN is zero and it has a fresh uid. */
664 tree
665 copy_node_stat (tree node MEM_STAT_DECL)
667 tree t;
668 enum tree_code code = TREE_CODE (node);
669 size_t length;
671 gcc_assert (code != STATEMENT_LIST);
673 length = tree_size (node);
674 t = ggc_alloc_zone_pass_stat (length, &tree_zone);
675 memcpy (t, node, length);
677 if (!GIMPLE_TUPLE_P (node))
678 TREE_CHAIN (t) = 0;
679 TREE_ASM_WRITTEN (t) = 0;
680 TREE_VISITED (t) = 0;
681 t->base.ann = 0;
683 if (TREE_CODE_CLASS (code) == tcc_declaration)
685 DECL_UID (t) = next_decl_uid++;
686 if ((TREE_CODE (node) == PARM_DECL || TREE_CODE (node) == VAR_DECL)
687 && DECL_HAS_VALUE_EXPR_P (node))
689 SET_DECL_VALUE_EXPR (t, DECL_VALUE_EXPR (node));
690 DECL_HAS_VALUE_EXPR_P (t) = 1;
692 if (TREE_CODE (node) == VAR_DECL && DECL_HAS_INIT_PRIORITY_P (node))
694 SET_DECL_INIT_PRIORITY (t, DECL_INIT_PRIORITY (node));
695 DECL_HAS_INIT_PRIORITY_P (t) = 1;
697 if (TREE_CODE (node) == VAR_DECL && DECL_BASED_ON_RESTRICT_P (node))
699 SET_DECL_RESTRICT_BASE (t, DECL_GET_RESTRICT_BASE (node));
700 DECL_BASED_ON_RESTRICT_P (t) = 1;
703 else if (TREE_CODE_CLASS (code) == tcc_type)
705 TYPE_UID (t) = next_type_uid++;
706 /* The following is so that the debug code for
707 the copy is different from the original type.
708 The two statements usually duplicate each other
709 (because they clear fields of the same union),
710 but the optimizer should catch that. */
711 TYPE_SYMTAB_POINTER (t) = 0;
712 TYPE_SYMTAB_ADDRESS (t) = 0;
714 /* Do not copy the values cache. */
715 if (TYPE_CACHED_VALUES_P(t))
717 TYPE_CACHED_VALUES_P (t) = 0;
718 TYPE_CACHED_VALUES (t) = NULL_TREE;
722 return t;
725 /* Return a copy of a chain of nodes, chained through the TREE_CHAIN field.
726 For example, this can copy a list made of TREE_LIST nodes. */
728 tree
729 copy_list (tree list)
731 tree head;
732 tree prev, next;
734 if (list == 0)
735 return 0;
737 head = prev = copy_node (list);
738 next = TREE_CHAIN (list);
739 while (next)
741 TREE_CHAIN (prev) = copy_node (next);
742 prev = TREE_CHAIN (prev);
743 next = TREE_CHAIN (next);
745 return head;
749 /* Create an INT_CST node with a LOW value sign extended. */
751 tree
752 build_int_cst (tree type, HOST_WIDE_INT low)
754 /* Support legacy code. */
755 if (!type)
756 type = integer_type_node;
758 return build_int_cst_wide (type, low, low < 0 ? -1 : 0);
761 /* Create an INT_CST node with a LOW value zero extended. */
763 tree
764 build_int_cstu (tree type, unsigned HOST_WIDE_INT low)
766 return build_int_cst_wide (type, low, 0);
769 /* Create an INT_CST node with a LOW value in TYPE. The value is sign extended
770 if it is negative. This function is similar to build_int_cst, but
771 the extra bits outside of the type precision are cleared. Constants
772 with these extra bits may confuse the fold so that it detects overflows
773 even in cases when they do not occur, and in general should be avoided.
774 We cannot however make this a default behavior of build_int_cst without
775 more intrusive changes, since there are parts of gcc that rely on the extra
776 precision of the integer constants. */
778 tree
779 build_int_cst_type (tree type, HOST_WIDE_INT low)
781 unsigned HOST_WIDE_INT low1;
782 HOST_WIDE_INT hi;
784 gcc_assert (type);
786 fit_double_type (low, low < 0 ? -1 : 0, &low1, &hi, type);
788 return build_int_cst_wide (type, low1, hi);
791 /* Create an INT_CST node of TYPE and value HI:LOW. The value is truncated
792 and sign extended according to the value range of TYPE. */
794 tree
795 build_int_cst_wide_type (tree type,
796 unsigned HOST_WIDE_INT low, HOST_WIDE_INT high)
798 fit_double_type (low, high, &low, &high, type);
799 return build_int_cst_wide (type, low, high);
802 /* These are the hash table functions for the hash table of INTEGER_CST
803 nodes of a sizetype. */
805 /* Return the hash code code X, an INTEGER_CST. */
807 static hashval_t
808 int_cst_hash_hash (const void *x)
810 tree t = (tree) x;
812 return (TREE_INT_CST_HIGH (t) ^ TREE_INT_CST_LOW (t)
813 ^ htab_hash_pointer (TREE_TYPE (t)));
816 /* Return nonzero if the value represented by *X (an INTEGER_CST tree node)
817 is the same as that given by *Y, which is the same. */
819 static int
820 int_cst_hash_eq (const void *x, const void *y)
822 tree xt = (tree) x;
823 tree yt = (tree) y;
825 return (TREE_TYPE (xt) == TREE_TYPE (yt)
826 && TREE_INT_CST_HIGH (xt) == TREE_INT_CST_HIGH (yt)
827 && TREE_INT_CST_LOW (xt) == TREE_INT_CST_LOW (yt));
830 /* Create an INT_CST node of TYPE and value HI:LOW.
831 The returned node is always shared. For small integers we use a
832 per-type vector cache, for larger ones we use a single hash table. */
834 tree
835 build_int_cst_wide (tree type, unsigned HOST_WIDE_INT low, HOST_WIDE_INT hi)
837 tree t;
838 int ix = -1;
839 int limit = 0;
841 gcc_assert (type);
843 switch (TREE_CODE (type))
845 case POINTER_TYPE:
846 case REFERENCE_TYPE:
847 /* Cache NULL pointer. */
848 if (!hi && !low)
850 limit = 1;
851 ix = 0;
853 break;
855 case BOOLEAN_TYPE:
856 /* Cache false or true. */
857 limit = 2;
858 if (!hi && low < 2)
859 ix = low;
860 break;
862 case INTEGER_TYPE:
863 case OFFSET_TYPE:
864 if (TYPE_UNSIGNED (type))
866 /* Cache 0..N */
867 limit = INTEGER_SHARE_LIMIT;
868 if (!hi && low < (unsigned HOST_WIDE_INT)INTEGER_SHARE_LIMIT)
869 ix = low;
871 else
873 /* Cache -1..N */
874 limit = INTEGER_SHARE_LIMIT + 1;
875 if (!hi && low < (unsigned HOST_WIDE_INT)INTEGER_SHARE_LIMIT)
876 ix = low + 1;
877 else if (hi == -1 && low == -(unsigned HOST_WIDE_INT)1)
878 ix = 0;
880 break;
882 case ENUMERAL_TYPE:
883 break;
885 default:
886 gcc_unreachable ();
889 if (ix >= 0)
891 /* Look for it in the type's vector of small shared ints. */
892 if (!TYPE_CACHED_VALUES_P (type))
894 TYPE_CACHED_VALUES_P (type) = 1;
895 TYPE_CACHED_VALUES (type) = make_tree_vec (limit);
898 t = TREE_VEC_ELT (TYPE_CACHED_VALUES (type), ix);
899 if (t)
901 /* Make sure no one is clobbering the shared constant. */
902 gcc_assert (TREE_TYPE (t) == type);
903 gcc_assert (TREE_INT_CST_LOW (t) == low);
904 gcc_assert (TREE_INT_CST_HIGH (t) == hi);
906 else
908 /* Create a new shared int. */
909 t = make_node (INTEGER_CST);
911 TREE_INT_CST_LOW (t) = low;
912 TREE_INT_CST_HIGH (t) = hi;
913 TREE_TYPE (t) = type;
915 TREE_VEC_ELT (TYPE_CACHED_VALUES (type), ix) = t;
918 else
920 /* Use the cache of larger shared ints. */
921 void **slot;
923 TREE_INT_CST_LOW (int_cst_node) = low;
924 TREE_INT_CST_HIGH (int_cst_node) = hi;
925 TREE_TYPE (int_cst_node) = type;
927 slot = htab_find_slot (int_cst_hash_table, int_cst_node, INSERT);
928 t = *slot;
929 if (!t)
931 /* Insert this one into the hash table. */
932 t = int_cst_node;
933 *slot = t;
934 /* Make a new node for next time round. */
935 int_cst_node = make_node (INTEGER_CST);
939 return t;
942 /* Builds an integer constant in TYPE such that lowest BITS bits are ones
943 and the rest are zeros. */
945 tree
946 build_low_bits_mask (tree type, unsigned bits)
948 unsigned HOST_WIDE_INT low;
949 HOST_WIDE_INT high;
950 unsigned HOST_WIDE_INT all_ones = ~(unsigned HOST_WIDE_INT) 0;
952 gcc_assert (bits <= TYPE_PRECISION (type));
954 if (bits == TYPE_PRECISION (type)
955 && !TYPE_UNSIGNED (type))
957 /* Sign extended all-ones mask. */
958 low = all_ones;
959 high = -1;
961 else if (bits <= HOST_BITS_PER_WIDE_INT)
963 low = all_ones >> (HOST_BITS_PER_WIDE_INT - bits);
964 high = 0;
966 else
968 bits -= HOST_BITS_PER_WIDE_INT;
969 low = all_ones;
970 high = all_ones >> (HOST_BITS_PER_WIDE_INT - bits);
973 return build_int_cst_wide (type, low, high);
976 /* Checks that X is integer constant that can be expressed in (unsigned)
977 HOST_WIDE_INT without loss of precision. */
979 bool
980 cst_and_fits_in_hwi (tree x)
982 if (TREE_CODE (x) != INTEGER_CST)
983 return false;
985 if (TYPE_PRECISION (TREE_TYPE (x)) > HOST_BITS_PER_WIDE_INT)
986 return false;
988 return (TREE_INT_CST_HIGH (x) == 0
989 || TREE_INT_CST_HIGH (x) == -1);
992 /* Return a new VECTOR_CST node whose type is TYPE and whose values
993 are in a list pointed to by VALS. */
995 tree
996 build_vector (tree type, tree vals)
998 tree v = make_node (VECTOR_CST);
999 int over = 0;
1000 tree link;
1002 TREE_VECTOR_CST_ELTS (v) = vals;
1003 TREE_TYPE (v) = type;
1005 /* Iterate through elements and check for overflow. */
1006 for (link = vals; link; link = TREE_CHAIN (link))
1008 tree value = TREE_VALUE (link);
1010 /* Don't crash if we get an address constant. */
1011 if (!CONSTANT_CLASS_P (value))
1012 continue;
1014 over |= TREE_OVERFLOW (value);
1017 TREE_OVERFLOW (v) = over;
1018 return v;
1021 /* Return a new VECTOR_CST node whose type is TYPE and whose values
1022 are extracted from V, a vector of CONSTRUCTOR_ELT. */
1024 tree
1025 build_vector_from_ctor (tree type, VEC(constructor_elt,gc) *v)
1027 tree list = NULL_TREE;
1028 unsigned HOST_WIDE_INT idx;
1029 tree value;
1031 FOR_EACH_CONSTRUCTOR_VALUE (v, idx, value)
1032 list = tree_cons (NULL_TREE, value, list);
1033 return build_vector (type, nreverse (list));
1036 /* Return a new CONSTRUCTOR node whose type is TYPE and whose values
1037 are in the VEC pointed to by VALS. */
1038 tree
1039 build_constructor (tree type, VEC(constructor_elt,gc) *vals)
1041 tree c = make_node (CONSTRUCTOR);
1042 TREE_TYPE (c) = type;
1043 CONSTRUCTOR_ELTS (c) = vals;
1044 return c;
1047 /* Build a CONSTRUCTOR node made of a single initializer, with the specified
1048 INDEX and VALUE. */
1049 tree
1050 build_constructor_single (tree type, tree index, tree value)
1052 VEC(constructor_elt,gc) *v;
1053 constructor_elt *elt;
1054 tree t;
1056 v = VEC_alloc (constructor_elt, gc, 1);
1057 elt = VEC_quick_push (constructor_elt, v, NULL);
1058 elt->index = index;
1059 elt->value = value;
1061 t = build_constructor (type, v);
1062 TREE_CONSTANT (t) = TREE_CONSTANT (value);
1063 return t;
1067 /* Return a new CONSTRUCTOR node whose type is TYPE and whose values
1068 are in a list pointed to by VALS. */
1069 tree
1070 build_constructor_from_list (tree type, tree vals)
1072 tree t, val;
1073 VEC(constructor_elt,gc) *v = NULL;
1074 bool constant_p = true;
1076 if (vals)
1078 v = VEC_alloc (constructor_elt, gc, list_length (vals));
1079 for (t = vals; t; t = TREE_CHAIN (t))
1081 constructor_elt *elt = VEC_quick_push (constructor_elt, v, NULL);
1082 val = TREE_VALUE (t);
1083 elt->index = TREE_PURPOSE (t);
1084 elt->value = val;
1085 if (!TREE_CONSTANT (val))
1086 constant_p = false;
1090 t = build_constructor (type, v);
1091 TREE_CONSTANT (t) = constant_p;
1092 return t;
1096 /* Return a new REAL_CST node whose type is TYPE and value is D. */
1098 tree
1099 build_real (tree type, REAL_VALUE_TYPE d)
1101 tree v;
1102 REAL_VALUE_TYPE *dp;
1103 int overflow = 0;
1105 /* ??? Used to check for overflow here via CHECK_FLOAT_TYPE.
1106 Consider doing it via real_convert now. */
1108 v = make_node (REAL_CST);
1109 dp = ggc_alloc (sizeof (REAL_VALUE_TYPE));
1110 memcpy (dp, &d, sizeof (REAL_VALUE_TYPE));
1112 TREE_TYPE (v) = type;
1113 TREE_REAL_CST_PTR (v) = dp;
1114 TREE_OVERFLOW (v) = overflow;
1115 return v;
1118 /* Return a new REAL_CST node whose type is TYPE
1119 and whose value is the integer value of the INTEGER_CST node I. */
1121 REAL_VALUE_TYPE
1122 real_value_from_int_cst (tree type, tree i)
1124 REAL_VALUE_TYPE d;
1126 /* Clear all bits of the real value type so that we can later do
1127 bitwise comparisons to see if two values are the same. */
1128 memset (&d, 0, sizeof d);
1130 real_from_integer (&d, type ? TYPE_MODE (type) : VOIDmode,
1131 TREE_INT_CST_LOW (i), TREE_INT_CST_HIGH (i),
1132 TYPE_UNSIGNED (TREE_TYPE (i)));
1133 return d;
1136 /* Given a tree representing an integer constant I, return a tree
1137 representing the same value as a floating-point constant of type TYPE. */
1139 tree
1140 build_real_from_int_cst (tree type, tree i)
1142 tree v;
1143 int overflow = TREE_OVERFLOW (i);
1145 v = build_real (type, real_value_from_int_cst (type, i));
1147 TREE_OVERFLOW (v) |= overflow;
1148 return v;
1151 /* Return a newly constructed STRING_CST node whose value is
1152 the LEN characters at STR.
1153 The TREE_TYPE is not initialized. */
1155 tree
1156 build_string (int len, const char *str)
1158 tree s;
1159 size_t length;
1161 /* Do not waste bytes provided by padding of struct tree_string. */
1162 length = len + offsetof (struct tree_string, str) + 1;
1164 #ifdef GATHER_STATISTICS
1165 tree_node_counts[(int) c_kind]++;
1166 tree_node_sizes[(int) c_kind] += length;
1167 #endif
1169 s = ggc_alloc_tree (length);
1171 memset (s, 0, sizeof (struct tree_common));
1172 TREE_SET_CODE (s, STRING_CST);
1173 TREE_CONSTANT (s) = 1;
1174 TREE_INVARIANT (s) = 1;
1175 TREE_STRING_LENGTH (s) = len;
1176 memcpy ((char *) TREE_STRING_POINTER (s), str, len);
1177 ((char *) TREE_STRING_POINTER (s))[len] = '\0';
1179 return s;
1182 /* Return a newly constructed COMPLEX_CST node whose value is
1183 specified by the real and imaginary parts REAL and IMAG.
1184 Both REAL and IMAG should be constant nodes. TYPE, if specified,
1185 will be the type of the COMPLEX_CST; otherwise a new type will be made. */
1187 tree
1188 build_complex (tree type, tree real, tree imag)
1190 tree t = make_node (COMPLEX_CST);
1192 TREE_REALPART (t) = real;
1193 TREE_IMAGPART (t) = imag;
1194 TREE_TYPE (t) = type ? type : build_complex_type (TREE_TYPE (real));
1195 TREE_OVERFLOW (t) = TREE_OVERFLOW (real) | TREE_OVERFLOW (imag);
1196 return t;
1199 /* Return a constant of arithmetic type TYPE which is the
1200 multiplicative identity of the set TYPE. */
1202 tree
1203 build_one_cst (tree type)
1205 switch (TREE_CODE (type))
1207 case INTEGER_TYPE: case ENUMERAL_TYPE: case BOOLEAN_TYPE:
1208 case POINTER_TYPE: case REFERENCE_TYPE:
1209 case OFFSET_TYPE:
1210 return build_int_cst (type, 1);
1212 case REAL_TYPE:
1213 return build_real (type, dconst1);
1215 case VECTOR_TYPE:
1217 tree scalar, cst;
1218 int i;
1220 scalar = build_one_cst (TREE_TYPE (type));
1222 /* Create 'vect_cst_ = {cst,cst,...,cst}' */
1223 cst = NULL_TREE;
1224 for (i = TYPE_VECTOR_SUBPARTS (type); --i >= 0; )
1225 cst = tree_cons (NULL_TREE, scalar, cst);
1227 return build_vector (type, cst);
1230 case COMPLEX_TYPE:
1231 return build_complex (type,
1232 build_one_cst (TREE_TYPE (type)),
1233 fold_convert (TREE_TYPE (type), integer_zero_node));
1235 default:
1236 gcc_unreachable ();
1240 /* Build a BINFO with LEN language slots. */
1242 tree
1243 make_tree_binfo_stat (unsigned base_binfos MEM_STAT_DECL)
1245 tree t;
1246 size_t length = (offsetof (struct tree_binfo, base_binfos)
1247 + VEC_embedded_size (tree, base_binfos));
1249 #ifdef GATHER_STATISTICS
1250 tree_node_counts[(int) binfo_kind]++;
1251 tree_node_sizes[(int) binfo_kind] += length;
1252 #endif
1254 t = ggc_alloc_zone_pass_stat (length, &tree_zone);
1256 memset (t, 0, offsetof (struct tree_binfo, base_binfos));
1258 TREE_SET_CODE (t, TREE_BINFO);
1260 VEC_embedded_init (tree, BINFO_BASE_BINFOS (t), base_binfos);
1262 return t;
1266 /* Build a newly constructed TREE_VEC node of length LEN. */
1268 tree
1269 make_tree_vec_stat (int len MEM_STAT_DECL)
1271 tree t;
1272 int length = (len - 1) * sizeof (tree) + sizeof (struct tree_vec);
1274 #ifdef GATHER_STATISTICS
1275 tree_node_counts[(int) vec_kind]++;
1276 tree_node_sizes[(int) vec_kind] += length;
1277 #endif
1279 t = ggc_alloc_zone_pass_stat (length, &tree_zone);
1281 memset (t, 0, length);
1283 TREE_SET_CODE (t, TREE_VEC);
1284 TREE_VEC_LENGTH (t) = len;
1286 return t;
1289 /* Return 1 if EXPR is the integer constant zero or a complex constant
1290 of zero. */
1293 integer_zerop (tree expr)
1295 STRIP_NOPS (expr);
1297 return ((TREE_CODE (expr) == INTEGER_CST
1298 && TREE_INT_CST_LOW (expr) == 0
1299 && TREE_INT_CST_HIGH (expr) == 0)
1300 || (TREE_CODE (expr) == COMPLEX_CST
1301 && integer_zerop (TREE_REALPART (expr))
1302 && integer_zerop (TREE_IMAGPART (expr))));
1305 /* Return 1 if EXPR is the integer constant one or the corresponding
1306 complex constant. */
1309 integer_onep (tree expr)
1311 STRIP_NOPS (expr);
1313 return ((TREE_CODE (expr) == INTEGER_CST
1314 && TREE_INT_CST_LOW (expr) == 1
1315 && TREE_INT_CST_HIGH (expr) == 0)
1316 || (TREE_CODE (expr) == COMPLEX_CST
1317 && integer_onep (TREE_REALPART (expr))
1318 && integer_zerop (TREE_IMAGPART (expr))));
1321 /* Return 1 if EXPR is an integer containing all 1's in as much precision as
1322 it contains. Likewise for the corresponding complex constant. */
1325 integer_all_onesp (tree expr)
1327 int prec;
1328 int uns;
1330 STRIP_NOPS (expr);
1332 if (TREE_CODE (expr) == COMPLEX_CST
1333 && integer_all_onesp (TREE_REALPART (expr))
1334 && integer_zerop (TREE_IMAGPART (expr)))
1335 return 1;
1337 else if (TREE_CODE (expr) != INTEGER_CST)
1338 return 0;
1340 uns = TYPE_UNSIGNED (TREE_TYPE (expr));
1341 if (TREE_INT_CST_LOW (expr) == ~(unsigned HOST_WIDE_INT) 0
1342 && TREE_INT_CST_HIGH (expr) == -1)
1343 return 1;
1344 if (!uns)
1345 return 0;
1347 /* Note that using TYPE_PRECISION here is wrong. We care about the
1348 actual bits, not the (arbitrary) range of the type. */
1349 prec = GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (expr)));
1350 if (prec >= HOST_BITS_PER_WIDE_INT)
1352 HOST_WIDE_INT high_value;
1353 int shift_amount;
1355 shift_amount = prec - HOST_BITS_PER_WIDE_INT;
1357 /* Can not handle precisions greater than twice the host int size. */
1358 gcc_assert (shift_amount <= HOST_BITS_PER_WIDE_INT);
1359 if (shift_amount == HOST_BITS_PER_WIDE_INT)
1360 /* Shifting by the host word size is undefined according to the ANSI
1361 standard, so we must handle this as a special case. */
1362 high_value = -1;
1363 else
1364 high_value = ((HOST_WIDE_INT) 1 << shift_amount) - 1;
1366 return (TREE_INT_CST_LOW (expr) == ~(unsigned HOST_WIDE_INT) 0
1367 && TREE_INT_CST_HIGH (expr) == high_value);
1369 else
1370 return TREE_INT_CST_LOW (expr) == ((unsigned HOST_WIDE_INT) 1 << prec) - 1;
1373 /* Return 1 if EXPR is an integer constant that is a power of 2 (i.e., has only
1374 one bit on). */
1377 integer_pow2p (tree expr)
1379 int prec;
1380 HOST_WIDE_INT high, low;
1382 STRIP_NOPS (expr);
1384 if (TREE_CODE (expr) == COMPLEX_CST
1385 && integer_pow2p (TREE_REALPART (expr))
1386 && integer_zerop (TREE_IMAGPART (expr)))
1387 return 1;
1389 if (TREE_CODE (expr) != INTEGER_CST)
1390 return 0;
1392 prec = (POINTER_TYPE_P (TREE_TYPE (expr))
1393 ? POINTER_SIZE : TYPE_PRECISION (TREE_TYPE (expr)));
1394 high = TREE_INT_CST_HIGH (expr);
1395 low = TREE_INT_CST_LOW (expr);
1397 /* First clear all bits that are beyond the type's precision in case
1398 we've been sign extended. */
1400 if (prec == 2 * HOST_BITS_PER_WIDE_INT)
1402 else if (prec > HOST_BITS_PER_WIDE_INT)
1403 high &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
1404 else
1406 high = 0;
1407 if (prec < HOST_BITS_PER_WIDE_INT)
1408 low &= ~((HOST_WIDE_INT) (-1) << prec);
1411 if (high == 0 && low == 0)
1412 return 0;
1414 return ((high == 0 && (low & (low - 1)) == 0)
1415 || (low == 0 && (high & (high - 1)) == 0));
1418 /* Return 1 if EXPR is an integer constant other than zero or a
1419 complex constant other than zero. */
1422 integer_nonzerop (tree expr)
1424 STRIP_NOPS (expr);
1426 return ((TREE_CODE (expr) == INTEGER_CST
1427 && (TREE_INT_CST_LOW (expr) != 0
1428 || TREE_INT_CST_HIGH (expr) != 0))
1429 || (TREE_CODE (expr) == COMPLEX_CST
1430 && (integer_nonzerop (TREE_REALPART (expr))
1431 || integer_nonzerop (TREE_IMAGPART (expr)))));
1434 /* Return the power of two represented by a tree node known to be a
1435 power of two. */
1438 tree_log2 (tree expr)
1440 int prec;
1441 HOST_WIDE_INT high, low;
1443 STRIP_NOPS (expr);
1445 if (TREE_CODE (expr) == COMPLEX_CST)
1446 return tree_log2 (TREE_REALPART (expr));
1448 prec = (POINTER_TYPE_P (TREE_TYPE (expr))
1449 ? POINTER_SIZE : TYPE_PRECISION (TREE_TYPE (expr)));
1451 high = TREE_INT_CST_HIGH (expr);
1452 low = TREE_INT_CST_LOW (expr);
1454 /* First clear all bits that are beyond the type's precision in case
1455 we've been sign extended. */
1457 if (prec == 2 * HOST_BITS_PER_WIDE_INT)
1459 else if (prec > HOST_BITS_PER_WIDE_INT)
1460 high &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
1461 else
1463 high = 0;
1464 if (prec < HOST_BITS_PER_WIDE_INT)
1465 low &= ~((HOST_WIDE_INT) (-1) << prec);
1468 return (high != 0 ? HOST_BITS_PER_WIDE_INT + exact_log2 (high)
1469 : exact_log2 (low));
1472 /* Similar, but return the largest integer Y such that 2 ** Y is less
1473 than or equal to EXPR. */
1476 tree_floor_log2 (tree expr)
1478 int prec;
1479 HOST_WIDE_INT high, low;
1481 STRIP_NOPS (expr);
1483 if (TREE_CODE (expr) == COMPLEX_CST)
1484 return tree_log2 (TREE_REALPART (expr));
1486 prec = (POINTER_TYPE_P (TREE_TYPE (expr))
1487 ? POINTER_SIZE : TYPE_PRECISION (TREE_TYPE (expr)));
1489 high = TREE_INT_CST_HIGH (expr);
1490 low = TREE_INT_CST_LOW (expr);
1492 /* First clear all bits that are beyond the type's precision in case
1493 we've been sign extended. Ignore if type's precision hasn't been set
1494 since what we are doing is setting it. */
1496 if (prec == 2 * HOST_BITS_PER_WIDE_INT || prec == 0)
1498 else if (prec > HOST_BITS_PER_WIDE_INT)
1499 high &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
1500 else
1502 high = 0;
1503 if (prec < HOST_BITS_PER_WIDE_INT)
1504 low &= ~((HOST_WIDE_INT) (-1) << prec);
1507 return (high != 0 ? HOST_BITS_PER_WIDE_INT + floor_log2 (high)
1508 : floor_log2 (low));
1511 /* Return 1 if EXPR is the real constant zero. */
1514 real_zerop (tree expr)
1516 STRIP_NOPS (expr);
1518 return ((TREE_CODE (expr) == REAL_CST
1519 && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconst0))
1520 || (TREE_CODE (expr) == COMPLEX_CST
1521 && real_zerop (TREE_REALPART (expr))
1522 && real_zerop (TREE_IMAGPART (expr))));
1525 /* Return 1 if EXPR is the real constant one in real or complex form. */
1528 real_onep (tree expr)
1530 STRIP_NOPS (expr);
1532 return ((TREE_CODE (expr) == REAL_CST
1533 && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconst1))
1534 || (TREE_CODE (expr) == COMPLEX_CST
1535 && real_onep (TREE_REALPART (expr))
1536 && real_zerop (TREE_IMAGPART (expr))));
1539 /* Return 1 if EXPR is the real constant two. */
1542 real_twop (tree expr)
1544 STRIP_NOPS (expr);
1546 return ((TREE_CODE (expr) == REAL_CST
1547 && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconst2))
1548 || (TREE_CODE (expr) == COMPLEX_CST
1549 && real_twop (TREE_REALPART (expr))
1550 && real_zerop (TREE_IMAGPART (expr))));
1553 /* Return 1 if EXPR is the real constant minus one. */
1556 real_minus_onep (tree expr)
1558 STRIP_NOPS (expr);
1560 return ((TREE_CODE (expr) == REAL_CST
1561 && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconstm1))
1562 || (TREE_CODE (expr) == COMPLEX_CST
1563 && real_minus_onep (TREE_REALPART (expr))
1564 && real_zerop (TREE_IMAGPART (expr))));
1567 /* Nonzero if EXP is a constant or a cast of a constant. */
1570 really_constant_p (tree exp)
1572 /* This is not quite the same as STRIP_NOPS. It does more. */
1573 while (TREE_CODE (exp) == NOP_EXPR
1574 || TREE_CODE (exp) == CONVERT_EXPR
1575 || TREE_CODE (exp) == NON_LVALUE_EXPR)
1576 exp = TREE_OPERAND (exp, 0);
1577 return TREE_CONSTANT (exp);
1580 /* Return first list element whose TREE_VALUE is ELEM.
1581 Return 0 if ELEM is not in LIST. */
1583 tree
1584 value_member (tree elem, tree list)
1586 while (list)
1588 if (elem == TREE_VALUE (list))
1589 return list;
1590 list = TREE_CHAIN (list);
1592 return NULL_TREE;
1595 /* Return first list element whose TREE_PURPOSE is ELEM.
1596 Return 0 if ELEM is not in LIST. */
1598 tree
1599 purpose_member (tree elem, tree list)
1601 while (list)
1603 if (elem == TREE_PURPOSE (list))
1604 return list;
1605 list = TREE_CHAIN (list);
1607 return NULL_TREE;
1610 /* Return nonzero if ELEM is part of the chain CHAIN. */
1613 chain_member (tree elem, tree chain)
1615 while (chain)
1617 if (elem == chain)
1618 return 1;
1619 chain = TREE_CHAIN (chain);
1622 return 0;
1625 /* Return the length of a chain of nodes chained through TREE_CHAIN.
1626 We expect a null pointer to mark the end of the chain.
1627 This is the Lisp primitive `length'. */
1630 list_length (tree t)
1632 tree p = t;
1633 #ifdef ENABLE_TREE_CHECKING
1634 tree q = t;
1635 #endif
1636 int len = 0;
1638 while (p)
1640 p = TREE_CHAIN (p);
1641 #ifdef ENABLE_TREE_CHECKING
1642 if (len % 2)
1643 q = TREE_CHAIN (q);
1644 gcc_assert (p != q);
1645 #endif
1646 len++;
1649 return len;
1652 /* Returns the number of FIELD_DECLs in TYPE. */
1655 fields_length (tree type)
1657 tree t = TYPE_FIELDS (type);
1658 int count = 0;
1660 for (; t; t = TREE_CHAIN (t))
1661 if (TREE_CODE (t) == FIELD_DECL)
1662 ++count;
1664 return count;
1667 /* Concatenate two chains of nodes (chained through TREE_CHAIN)
1668 by modifying the last node in chain 1 to point to chain 2.
1669 This is the Lisp primitive `nconc'. */
1671 tree
1672 chainon (tree op1, tree op2)
1674 tree t1;
1676 if (!op1)
1677 return op2;
1678 if (!op2)
1679 return op1;
1681 for (t1 = op1; TREE_CHAIN (t1); t1 = TREE_CHAIN (t1))
1682 continue;
1683 TREE_CHAIN (t1) = op2;
1685 #ifdef ENABLE_TREE_CHECKING
1687 tree t2;
1688 for (t2 = op2; t2; t2 = TREE_CHAIN (t2))
1689 gcc_assert (t2 != t1);
1691 #endif
1693 return op1;
1696 /* Return the last node in a chain of nodes (chained through TREE_CHAIN). */
1698 tree
1699 tree_last (tree chain)
1701 tree next;
1702 if (chain)
1703 while ((next = TREE_CHAIN (chain)))
1704 chain = next;
1705 return chain;
1708 /* Reverse the order of elements in the chain T,
1709 and return the new head of the chain (old last element). */
1711 tree
1712 nreverse (tree t)
1714 tree prev = 0, decl, next;
1715 for (decl = t; decl; decl = next)
1717 next = TREE_CHAIN (decl);
1718 TREE_CHAIN (decl) = prev;
1719 prev = decl;
1721 return prev;
1724 /* Return a newly created TREE_LIST node whose
1725 purpose and value fields are PARM and VALUE. */
1727 tree
1728 build_tree_list_stat (tree parm, tree value MEM_STAT_DECL)
1730 tree t = make_node_stat (TREE_LIST PASS_MEM_STAT);
1731 TREE_PURPOSE (t) = parm;
1732 TREE_VALUE (t) = value;
1733 return t;
1736 /* Return a newly created TREE_LIST node whose
1737 purpose and value fields are PURPOSE and VALUE
1738 and whose TREE_CHAIN is CHAIN. */
1740 tree
1741 tree_cons_stat (tree purpose, tree value, tree chain MEM_STAT_DECL)
1743 tree node;
1745 node = ggc_alloc_zone_pass_stat (sizeof (struct tree_list), &tree_zone);
1747 memset (node, 0, sizeof (struct tree_common));
1749 #ifdef GATHER_STATISTICS
1750 tree_node_counts[(int) x_kind]++;
1751 tree_node_sizes[(int) x_kind] += sizeof (struct tree_list);
1752 #endif
1754 TREE_SET_CODE (node, TREE_LIST);
1755 TREE_CHAIN (node) = chain;
1756 TREE_PURPOSE (node) = purpose;
1757 TREE_VALUE (node) = value;
1758 return node;
1762 /* Return the size nominally occupied by an object of type TYPE
1763 when it resides in memory. The value is measured in units of bytes,
1764 and its data type is that normally used for type sizes
1765 (which is the first type created by make_signed_type or
1766 make_unsigned_type). */
1768 tree
1769 size_in_bytes (tree type)
1771 tree t;
1773 if (type == error_mark_node)
1774 return integer_zero_node;
1776 type = TYPE_MAIN_VARIANT (type);
1777 t = TYPE_SIZE_UNIT (type);
1779 if (t == 0)
1781 lang_hooks.types.incomplete_type_error (NULL_TREE, type);
1782 return size_zero_node;
1785 return t;
1788 /* Return the size of TYPE (in bytes) as a wide integer
1789 or return -1 if the size can vary or is larger than an integer. */
1791 HOST_WIDE_INT
1792 int_size_in_bytes (tree type)
1794 tree t;
1796 if (type == error_mark_node)
1797 return 0;
1799 type = TYPE_MAIN_VARIANT (type);
1800 t = TYPE_SIZE_UNIT (type);
1801 if (t == 0
1802 || TREE_CODE (t) != INTEGER_CST
1803 || TREE_INT_CST_HIGH (t) != 0
1804 /* If the result would appear negative, it's too big to represent. */
1805 || (HOST_WIDE_INT) TREE_INT_CST_LOW (t) < 0)
1806 return -1;
1808 return TREE_INT_CST_LOW (t);
1811 /* Return the maximum size of TYPE (in bytes) as a wide integer
1812 or return -1 if the size can vary or is larger than an integer. */
1814 HOST_WIDE_INT
1815 max_int_size_in_bytes (tree type)
1817 HOST_WIDE_INT size = -1;
1818 tree size_tree;
1820 /* If this is an array type, check for a possible MAX_SIZE attached. */
1822 if (TREE_CODE (type) == ARRAY_TYPE)
1824 size_tree = TYPE_ARRAY_MAX_SIZE (type);
1826 if (size_tree && host_integerp (size_tree, 1))
1827 size = tree_low_cst (size_tree, 1);
1830 /* If we still haven't been able to get a size, see if the language
1831 can compute a maximum size. */
1833 if (size == -1)
1835 size_tree = lang_hooks.types.max_size (type);
1837 if (size_tree && host_integerp (size_tree, 1))
1838 size = tree_low_cst (size_tree, 1);
1841 return size;
1844 /* Return the bit position of FIELD, in bits from the start of the record.
1845 This is a tree of type bitsizetype. */
1847 tree
1848 bit_position (tree field)
1850 return bit_from_pos (DECL_FIELD_OFFSET (field),
1851 DECL_FIELD_BIT_OFFSET (field));
1854 /* Likewise, but return as an integer. It must be representable in
1855 that way (since it could be a signed value, we don't have the
1856 option of returning -1 like int_size_in_byte can. */
1858 HOST_WIDE_INT
1859 int_bit_position (tree field)
1861 return tree_low_cst (bit_position (field), 0);
1864 /* Return the byte position of FIELD, in bytes from the start of the record.
1865 This is a tree of type sizetype. */
1867 tree
1868 byte_position (tree field)
1870 return byte_from_pos (DECL_FIELD_OFFSET (field),
1871 DECL_FIELD_BIT_OFFSET (field));
1874 /* Likewise, but return as an integer. It must be representable in
1875 that way (since it could be a signed value, we don't have the
1876 option of returning -1 like int_size_in_byte can. */
1878 HOST_WIDE_INT
1879 int_byte_position (tree field)
1881 return tree_low_cst (byte_position (field), 0);
1884 /* Return the strictest alignment, in bits, that T is known to have. */
1886 unsigned int
1887 expr_align (tree t)
1889 unsigned int align0, align1;
1891 switch (TREE_CODE (t))
1893 case NOP_EXPR: case CONVERT_EXPR: case NON_LVALUE_EXPR:
1894 /* If we have conversions, we know that the alignment of the
1895 object must meet each of the alignments of the types. */
1896 align0 = expr_align (TREE_OPERAND (t, 0));
1897 align1 = TYPE_ALIGN (TREE_TYPE (t));
1898 return MAX (align0, align1);
1900 case GIMPLE_MODIFY_STMT:
1901 /* We should never ask for the alignment of a gimple statement. */
1902 gcc_unreachable ();
1904 case SAVE_EXPR: case COMPOUND_EXPR: case MODIFY_EXPR:
1905 case INIT_EXPR: case TARGET_EXPR: case WITH_CLEANUP_EXPR:
1906 case CLEANUP_POINT_EXPR:
1907 /* These don't change the alignment of an object. */
1908 return expr_align (TREE_OPERAND (t, 0));
1910 case COND_EXPR:
1911 /* The best we can do is say that the alignment is the least aligned
1912 of the two arms. */
1913 align0 = expr_align (TREE_OPERAND (t, 1));
1914 align1 = expr_align (TREE_OPERAND (t, 2));
1915 return MIN (align0, align1);
1917 case LABEL_DECL: case CONST_DECL:
1918 case VAR_DECL: case PARM_DECL: case RESULT_DECL:
1919 if (DECL_ALIGN (t) != 0)
1920 return DECL_ALIGN (t);
1921 break;
1923 case FUNCTION_DECL:
1924 return FUNCTION_BOUNDARY;
1926 default:
1927 break;
1930 /* Otherwise take the alignment from that of the type. */
1931 return TYPE_ALIGN (TREE_TYPE (t));
1934 /* Return, as a tree node, the number of elements for TYPE (which is an
1935 ARRAY_TYPE) minus one. This counts only elements of the top array. */
1937 tree
1938 array_type_nelts (tree type)
1940 tree index_type, min, max;
1942 /* If they did it with unspecified bounds, then we should have already
1943 given an error about it before we got here. */
1944 if (! TYPE_DOMAIN (type))
1945 return error_mark_node;
1947 index_type = TYPE_DOMAIN (type);
1948 min = TYPE_MIN_VALUE (index_type);
1949 max = TYPE_MAX_VALUE (index_type);
1951 return (integer_zerop (min)
1952 ? max
1953 : fold_build2 (MINUS_EXPR, TREE_TYPE (max), max, min));
1956 /* If arg is static -- a reference to an object in static storage -- then
1957 return the object. This is not the same as the C meaning of `static'.
1958 If arg isn't static, return NULL. */
1960 tree
1961 staticp (tree arg)
1963 switch (TREE_CODE (arg))
1965 case FUNCTION_DECL:
1966 /* Nested functions are static, even though taking their address will
1967 involve a trampoline as we unnest the nested function and create
1968 the trampoline on the tree level. */
1969 return arg;
1971 case VAR_DECL:
1972 return ((TREE_STATIC (arg) || DECL_EXTERNAL (arg))
1973 && ! DECL_THREAD_LOCAL_P (arg)
1974 && ! DECL_DLLIMPORT_P (arg)
1975 ? arg : NULL);
1977 case CONST_DECL:
1978 return ((TREE_STATIC (arg) || DECL_EXTERNAL (arg))
1979 ? arg : NULL);
1981 case CONSTRUCTOR:
1982 return TREE_STATIC (arg) ? arg : NULL;
1984 case LABEL_DECL:
1985 case STRING_CST:
1986 return arg;
1988 case COMPONENT_REF:
1989 /* If the thing being referenced is not a field, then it is
1990 something language specific. */
1991 if (TREE_CODE (TREE_OPERAND (arg, 1)) != FIELD_DECL)
1992 return (*lang_hooks.staticp) (arg);
1994 /* If we are referencing a bitfield, we can't evaluate an
1995 ADDR_EXPR at compile time and so it isn't a constant. */
1996 if (DECL_BIT_FIELD (TREE_OPERAND (arg, 1)))
1997 return NULL;
1999 return staticp (TREE_OPERAND (arg, 0));
2001 case BIT_FIELD_REF:
2002 return NULL;
2004 case MISALIGNED_INDIRECT_REF:
2005 case ALIGN_INDIRECT_REF:
2006 case INDIRECT_REF:
2007 return TREE_CONSTANT (TREE_OPERAND (arg, 0)) ? arg : NULL;
2009 case ARRAY_REF:
2010 case ARRAY_RANGE_REF:
2011 if (TREE_CODE (TYPE_SIZE (TREE_TYPE (arg))) == INTEGER_CST
2012 && TREE_CODE (TREE_OPERAND (arg, 1)) == INTEGER_CST)
2013 return staticp (TREE_OPERAND (arg, 0));
2014 else
2015 return false;
2017 default:
2018 if ((unsigned int) TREE_CODE (arg)
2019 >= (unsigned int) LAST_AND_UNUSED_TREE_CODE)
2020 return lang_hooks.staticp (arg);
2021 else
2022 return NULL;
2026 /* Wrap a SAVE_EXPR around EXPR, if appropriate.
2027 Do this to any expression which may be used in more than one place,
2028 but must be evaluated only once.
2030 Normally, expand_expr would reevaluate the expression each time.
2031 Calling save_expr produces something that is evaluated and recorded
2032 the first time expand_expr is called on it. Subsequent calls to
2033 expand_expr just reuse the recorded value.
2035 The call to expand_expr that generates code that actually computes
2036 the value is the first call *at compile time*. Subsequent calls
2037 *at compile time* generate code to use the saved value.
2038 This produces correct result provided that *at run time* control
2039 always flows through the insns made by the first expand_expr
2040 before reaching the other places where the save_expr was evaluated.
2041 You, the caller of save_expr, must make sure this is so.
2043 Constants, and certain read-only nodes, are returned with no
2044 SAVE_EXPR because that is safe. Expressions containing placeholders
2045 are not touched; see tree.def for an explanation of what these
2046 are used for. */
2048 tree
2049 save_expr (tree expr)
2051 tree t = fold (expr);
2052 tree inner;
2054 /* If the tree evaluates to a constant, then we don't want to hide that
2055 fact (i.e. this allows further folding, and direct checks for constants).
2056 However, a read-only object that has side effects cannot be bypassed.
2057 Since it is no problem to reevaluate literals, we just return the
2058 literal node. */
2059 inner = skip_simple_arithmetic (t);
2061 if (TREE_INVARIANT (inner)
2062 || (TREE_READONLY (inner) && ! TREE_SIDE_EFFECTS (inner))
2063 || TREE_CODE (inner) == SAVE_EXPR
2064 || TREE_CODE (inner) == ERROR_MARK)
2065 return t;
2067 /* If INNER contains a PLACEHOLDER_EXPR, we must evaluate it each time, since
2068 it means that the size or offset of some field of an object depends on
2069 the value within another field.
2071 Note that it must not be the case that T contains both a PLACEHOLDER_EXPR
2072 and some variable since it would then need to be both evaluated once and
2073 evaluated more than once. Front-ends must assure this case cannot
2074 happen by surrounding any such subexpressions in their own SAVE_EXPR
2075 and forcing evaluation at the proper time. */
2076 if (contains_placeholder_p (inner))
2077 return t;
2079 t = build1 (SAVE_EXPR, TREE_TYPE (expr), t);
2081 /* This expression might be placed ahead of a jump to ensure that the
2082 value was computed on both sides of the jump. So make sure it isn't
2083 eliminated as dead. */
2084 TREE_SIDE_EFFECTS (t) = 1;
2085 TREE_INVARIANT (t) = 1;
2086 return t;
2089 /* Look inside EXPR and into any simple arithmetic operations. Return
2090 the innermost non-arithmetic node. */
2092 tree
2093 skip_simple_arithmetic (tree expr)
2095 tree inner;
2097 /* We don't care about whether this can be used as an lvalue in this
2098 context. */
2099 while (TREE_CODE (expr) == NON_LVALUE_EXPR)
2100 expr = TREE_OPERAND (expr, 0);
2102 /* If we have simple operations applied to a SAVE_EXPR or to a SAVE_EXPR and
2103 a constant, it will be more efficient to not make another SAVE_EXPR since
2104 it will allow better simplification and GCSE will be able to merge the
2105 computations if they actually occur. */
2106 inner = expr;
2107 while (1)
2109 if (UNARY_CLASS_P (inner))
2110 inner = TREE_OPERAND (inner, 0);
2111 else if (BINARY_CLASS_P (inner))
2113 if (TREE_INVARIANT (TREE_OPERAND (inner, 1)))
2114 inner = TREE_OPERAND (inner, 0);
2115 else if (TREE_INVARIANT (TREE_OPERAND (inner, 0)))
2116 inner = TREE_OPERAND (inner, 1);
2117 else
2118 break;
2120 else
2121 break;
2124 return inner;
2127 /* Return which tree structure is used by T. */
2129 enum tree_node_structure_enum
2130 tree_node_structure (tree t)
2132 enum tree_code code = TREE_CODE (t);
2134 switch (TREE_CODE_CLASS (code))
2136 case tcc_declaration:
2138 switch (code)
2140 case FIELD_DECL:
2141 return TS_FIELD_DECL;
2142 case PARM_DECL:
2143 return TS_PARM_DECL;
2144 case VAR_DECL:
2145 return TS_VAR_DECL;
2146 case LABEL_DECL:
2147 return TS_LABEL_DECL;
2148 case RESULT_DECL:
2149 return TS_RESULT_DECL;
2150 case CONST_DECL:
2151 return TS_CONST_DECL;
2152 case TYPE_DECL:
2153 return TS_TYPE_DECL;
2154 case FUNCTION_DECL:
2155 return TS_FUNCTION_DECL;
2156 case SYMBOL_MEMORY_TAG:
2157 case NAME_MEMORY_TAG:
2158 case STRUCT_FIELD_TAG:
2159 case MEMORY_PARTITION_TAG:
2160 return TS_MEMORY_TAG;
2161 default:
2162 return TS_DECL_NON_COMMON;
2165 case tcc_type:
2166 return TS_TYPE;
2167 case tcc_reference:
2168 case tcc_comparison:
2169 case tcc_unary:
2170 case tcc_binary:
2171 case tcc_expression:
2172 case tcc_statement:
2173 case tcc_vl_exp:
2174 return TS_EXP;
2175 case tcc_gimple_stmt:
2176 return TS_GIMPLE_STATEMENT;
2177 default: /* tcc_constant and tcc_exceptional */
2178 break;
2180 switch (code)
2182 /* tcc_constant cases. */
2183 case INTEGER_CST: return TS_INT_CST;
2184 case REAL_CST: return TS_REAL_CST;
2185 case COMPLEX_CST: return TS_COMPLEX;
2186 case VECTOR_CST: return TS_VECTOR;
2187 case STRING_CST: return TS_STRING;
2188 /* tcc_exceptional cases. */
2189 /* FIXME tuples: eventually this should be TS_BASE. For now, nothing
2190 returns TS_BASE. */
2191 case ERROR_MARK: return TS_COMMON;
2192 case IDENTIFIER_NODE: return TS_IDENTIFIER;
2193 case TREE_LIST: return TS_LIST;
2194 case TREE_VEC: return TS_VEC;
2195 case PHI_NODE: return TS_PHI_NODE;
2196 case SSA_NAME: return TS_SSA_NAME;
2197 case PLACEHOLDER_EXPR: return TS_COMMON;
2198 case STATEMENT_LIST: return TS_STATEMENT_LIST;
2199 case BLOCK: return TS_BLOCK;
2200 case CONSTRUCTOR: return TS_CONSTRUCTOR;
2201 case TREE_BINFO: return TS_BINFO;
2202 case VALUE_HANDLE: return TS_VALUE_HANDLE;
2203 case OMP_CLAUSE: return TS_OMP_CLAUSE;
2205 default:
2206 gcc_unreachable ();
2210 /* Return 1 if EXP contains a PLACEHOLDER_EXPR; i.e., if it represents a size
2211 or offset that depends on a field within a record. */
2213 bool
2214 contains_placeholder_p (tree exp)
2216 enum tree_code code;
2218 if (!exp)
2219 return 0;
2221 code = TREE_CODE (exp);
2222 if (code == PLACEHOLDER_EXPR)
2223 return 1;
2225 switch (TREE_CODE_CLASS (code))
2227 case tcc_reference:
2228 /* Don't look at any PLACEHOLDER_EXPRs that might be in index or bit
2229 position computations since they will be converted into a
2230 WITH_RECORD_EXPR involving the reference, which will assume
2231 here will be valid. */
2232 return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0));
2234 case tcc_exceptional:
2235 if (code == TREE_LIST)
2236 return (CONTAINS_PLACEHOLDER_P (TREE_VALUE (exp))
2237 || CONTAINS_PLACEHOLDER_P (TREE_CHAIN (exp)));
2238 break;
2240 case tcc_unary:
2241 case tcc_binary:
2242 case tcc_comparison:
2243 case tcc_expression:
2244 switch (code)
2246 case COMPOUND_EXPR:
2247 /* Ignoring the first operand isn't quite right, but works best. */
2248 return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1));
2250 case COND_EXPR:
2251 return (CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0))
2252 || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1))
2253 || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 2)));
2255 default:
2256 break;
2259 switch (TREE_CODE_LENGTH (code))
2261 case 1:
2262 return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0));
2263 case 2:
2264 return (CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0))
2265 || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1)));
2266 default:
2267 return 0;
2270 case tcc_vl_exp:
2271 switch (code)
2273 case CALL_EXPR:
2275 tree arg;
2276 call_expr_arg_iterator iter;
2277 FOR_EACH_CALL_EXPR_ARG (arg, iter, exp)
2278 if (CONTAINS_PLACEHOLDER_P (arg))
2279 return 1;
2280 return 0;
2282 default:
2283 return 0;
2286 default:
2287 return 0;
2289 return 0;
2292 /* Return true if any part of the computation of TYPE involves a
2293 PLACEHOLDER_EXPR. This includes size, bounds, qualifiers
2294 (for QUAL_UNION_TYPE) and field positions. */
2296 static bool
2297 type_contains_placeholder_1 (tree type)
2299 /* If the size contains a placeholder or the parent type (component type in
2300 the case of arrays) type involves a placeholder, this type does. */
2301 if (CONTAINS_PLACEHOLDER_P (TYPE_SIZE (type))
2302 || CONTAINS_PLACEHOLDER_P (TYPE_SIZE_UNIT (type))
2303 || (TREE_TYPE (type) != 0
2304 && type_contains_placeholder_p (TREE_TYPE (type))))
2305 return true;
2307 /* Now do type-specific checks. Note that the last part of the check above
2308 greatly limits what we have to do below. */
2309 switch (TREE_CODE (type))
2311 case VOID_TYPE:
2312 case COMPLEX_TYPE:
2313 case ENUMERAL_TYPE:
2314 case BOOLEAN_TYPE:
2315 case POINTER_TYPE:
2316 case OFFSET_TYPE:
2317 case REFERENCE_TYPE:
2318 case METHOD_TYPE:
2319 case FUNCTION_TYPE:
2320 case VECTOR_TYPE:
2321 return false;
2323 case INTEGER_TYPE:
2324 case REAL_TYPE:
2325 /* Here we just check the bounds. */
2326 return (CONTAINS_PLACEHOLDER_P (TYPE_MIN_VALUE (type))
2327 || CONTAINS_PLACEHOLDER_P (TYPE_MAX_VALUE (type)));
2329 case ARRAY_TYPE:
2330 /* We're already checked the component type (TREE_TYPE), so just check
2331 the index type. */
2332 return type_contains_placeholder_p (TYPE_DOMAIN (type));
2334 case RECORD_TYPE:
2335 case UNION_TYPE:
2336 case QUAL_UNION_TYPE:
2338 tree field;
2340 for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
2341 if (TREE_CODE (field) == FIELD_DECL
2342 && (CONTAINS_PLACEHOLDER_P (DECL_FIELD_OFFSET (field))
2343 || (TREE_CODE (type) == QUAL_UNION_TYPE
2344 && CONTAINS_PLACEHOLDER_P (DECL_QUALIFIER (field)))
2345 || type_contains_placeholder_p (TREE_TYPE (field))))
2346 return true;
2348 return false;
2351 default:
2352 gcc_unreachable ();
2356 bool
2357 type_contains_placeholder_p (tree type)
2359 bool result;
2361 /* If the contains_placeholder_bits field has been initialized,
2362 then we know the answer. */
2363 if (TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) > 0)
2364 return TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) - 1;
2366 /* Indicate that we've seen this type node, and the answer is false.
2367 This is what we want to return if we run into recursion via fields. */
2368 TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) = 1;
2370 /* Compute the real value. */
2371 result = type_contains_placeholder_1 (type);
2373 /* Store the real value. */
2374 TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) = result + 1;
2376 return result;
2379 /* Given a tree EXP, a FIELD_DECL F, and a replacement value R,
2380 return a tree with all occurrences of references to F in a
2381 PLACEHOLDER_EXPR replaced by R. Note that we assume here that EXP
2382 contains only arithmetic expressions or a CALL_EXPR with a
2383 PLACEHOLDER_EXPR occurring only in its arglist. */
2385 tree
2386 substitute_in_expr (tree exp, tree f, tree r)
2388 enum tree_code code = TREE_CODE (exp);
2389 tree op0, op1, op2, op3;
2390 tree new;
2391 tree inner;
2393 /* We handle TREE_LIST and COMPONENT_REF separately. */
2394 if (code == TREE_LIST)
2396 op0 = SUBSTITUTE_IN_EXPR (TREE_CHAIN (exp), f, r);
2397 op1 = SUBSTITUTE_IN_EXPR (TREE_VALUE (exp), f, r);
2398 if (op0 == TREE_CHAIN (exp) && op1 == TREE_VALUE (exp))
2399 return exp;
2401 return tree_cons (TREE_PURPOSE (exp), op1, op0);
2403 else if (code == COMPONENT_REF)
2405 /* If this expression is getting a value from a PLACEHOLDER_EXPR
2406 and it is the right field, replace it with R. */
2407 for (inner = TREE_OPERAND (exp, 0);
2408 REFERENCE_CLASS_P (inner);
2409 inner = TREE_OPERAND (inner, 0))
2411 if (TREE_CODE (inner) == PLACEHOLDER_EXPR
2412 && TREE_OPERAND (exp, 1) == f)
2413 return r;
2415 /* If this expression hasn't been completed let, leave it alone. */
2416 if (TREE_CODE (inner) == PLACEHOLDER_EXPR && TREE_TYPE (inner) == 0)
2417 return exp;
2419 op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
2420 if (op0 == TREE_OPERAND (exp, 0))
2421 return exp;
2423 new = fold_build3 (COMPONENT_REF, TREE_TYPE (exp),
2424 op0, TREE_OPERAND (exp, 1), NULL_TREE);
2426 else
2427 switch (TREE_CODE_CLASS (code))
2429 case tcc_constant:
2430 case tcc_declaration:
2431 return exp;
2433 case tcc_exceptional:
2434 case tcc_unary:
2435 case tcc_binary:
2436 case tcc_comparison:
2437 case tcc_expression:
2438 case tcc_reference:
2439 switch (TREE_CODE_LENGTH (code))
2441 case 0:
2442 return exp;
2444 case 1:
2445 op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
2446 if (op0 == TREE_OPERAND (exp, 0))
2447 return exp;
2449 new = fold_build1 (code, TREE_TYPE (exp), op0);
2450 break;
2452 case 2:
2453 op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
2454 op1 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 1), f, r);
2456 if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1))
2457 return exp;
2459 new = fold_build2 (code, TREE_TYPE (exp), op0, op1);
2460 break;
2462 case 3:
2463 op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
2464 op1 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 1), f, r);
2465 op2 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 2), f, r);
2467 if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
2468 && op2 == TREE_OPERAND (exp, 2))
2469 return exp;
2471 new = fold_build3 (code, TREE_TYPE (exp), op0, op1, op2);
2472 break;
2474 case 4:
2475 op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
2476 op1 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 1), f, r);
2477 op2 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 2), f, r);
2478 op3 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 3), f, r);
2480 if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
2481 && op2 == TREE_OPERAND (exp, 2)
2482 && op3 == TREE_OPERAND (exp, 3))
2483 return exp;
2485 new = fold (build4 (code, TREE_TYPE (exp), op0, op1, op2, op3));
2486 break;
2488 default:
2489 gcc_unreachable ();
2491 break;
2493 case tcc_vl_exp:
2495 tree copy = NULL_TREE;
2496 int i;
2497 int n = TREE_OPERAND_LENGTH (exp);
2498 for (i = 1; i < n; i++)
2500 tree op = TREE_OPERAND (exp, i);
2501 tree newop = SUBSTITUTE_IN_EXPR (op, f, r);
2502 if (newop != op)
2504 copy = copy_node (exp);
2505 TREE_OPERAND (copy, i) = newop;
2508 if (copy)
2509 new = fold (copy);
2510 else
2511 return exp;
2514 default:
2515 gcc_unreachable ();
2518 TREE_READONLY (new) = TREE_READONLY (exp);
2519 return new;
2522 /* Similar, but look for a PLACEHOLDER_EXPR in EXP and find a replacement
2523 for it within OBJ, a tree that is an object or a chain of references. */
2525 tree
2526 substitute_placeholder_in_expr (tree exp, tree obj)
2528 enum tree_code code = TREE_CODE (exp);
2529 tree op0, op1, op2, op3;
2531 /* If this is a PLACEHOLDER_EXPR, see if we find a corresponding type
2532 in the chain of OBJ. */
2533 if (code == PLACEHOLDER_EXPR)
2535 tree need_type = TYPE_MAIN_VARIANT (TREE_TYPE (exp));
2536 tree elt;
2538 for (elt = obj; elt != 0;
2539 elt = ((TREE_CODE (elt) == COMPOUND_EXPR
2540 || TREE_CODE (elt) == COND_EXPR)
2541 ? TREE_OPERAND (elt, 1)
2542 : (REFERENCE_CLASS_P (elt)
2543 || UNARY_CLASS_P (elt)
2544 || BINARY_CLASS_P (elt)
2545 || VL_EXP_CLASS_P (elt)
2546 || EXPRESSION_CLASS_P (elt))
2547 ? TREE_OPERAND (elt, 0) : 0))
2548 if (TYPE_MAIN_VARIANT (TREE_TYPE (elt)) == need_type)
2549 return elt;
2551 for (elt = obj; elt != 0;
2552 elt = ((TREE_CODE (elt) == COMPOUND_EXPR
2553 || TREE_CODE (elt) == COND_EXPR)
2554 ? TREE_OPERAND (elt, 1)
2555 : (REFERENCE_CLASS_P (elt)
2556 || UNARY_CLASS_P (elt)
2557 || BINARY_CLASS_P (elt)
2558 || VL_EXP_CLASS_P (elt)
2559 || EXPRESSION_CLASS_P (elt))
2560 ? TREE_OPERAND (elt, 0) : 0))
2561 if (POINTER_TYPE_P (TREE_TYPE (elt))
2562 && (TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (elt)))
2563 == need_type))
2564 return fold_build1 (INDIRECT_REF, need_type, elt);
2566 /* If we didn't find it, return the original PLACEHOLDER_EXPR. If it
2567 survives until RTL generation, there will be an error. */
2568 return exp;
2571 /* TREE_LIST is special because we need to look at TREE_VALUE
2572 and TREE_CHAIN, not TREE_OPERANDS. */
2573 else if (code == TREE_LIST)
2575 op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_CHAIN (exp), obj);
2576 op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_VALUE (exp), obj);
2577 if (op0 == TREE_CHAIN (exp) && op1 == TREE_VALUE (exp))
2578 return exp;
2580 return tree_cons (TREE_PURPOSE (exp), op1, op0);
2582 else
2583 switch (TREE_CODE_CLASS (code))
2585 case tcc_constant:
2586 case tcc_declaration:
2587 return exp;
2589 case tcc_exceptional:
2590 case tcc_unary:
2591 case tcc_binary:
2592 case tcc_comparison:
2593 case tcc_expression:
2594 case tcc_reference:
2595 case tcc_statement:
2596 switch (TREE_CODE_LENGTH (code))
2598 case 0:
2599 return exp;
2601 case 1:
2602 op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2603 if (op0 == TREE_OPERAND (exp, 0))
2604 return exp;
2605 else
2606 return fold_build1 (code, TREE_TYPE (exp), op0);
2608 case 2:
2609 op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2610 op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 1), obj);
2612 if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1))
2613 return exp;
2614 else
2615 return fold_build2 (code, TREE_TYPE (exp), op0, op1);
2617 case 3:
2618 op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2619 op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 1), obj);
2620 op2 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 2), obj);
2622 if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
2623 && op2 == TREE_OPERAND (exp, 2))
2624 return exp;
2625 else
2626 return fold_build3 (code, TREE_TYPE (exp), op0, op1, op2);
2628 case 4:
2629 op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2630 op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 1), obj);
2631 op2 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 2), obj);
2632 op3 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 3), obj);
2634 if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
2635 && op2 == TREE_OPERAND (exp, 2)
2636 && op3 == TREE_OPERAND (exp, 3))
2637 return exp;
2638 else
2639 return fold (build4 (code, TREE_TYPE (exp), op0, op1, op2, op3));
2641 default:
2642 gcc_unreachable ();
2644 break;
2646 case tcc_vl_exp:
2648 tree copy = NULL_TREE;
2649 int i;
2650 int n = TREE_OPERAND_LENGTH (exp);
2651 for (i = 1; i < n; i++)
2653 tree op = TREE_OPERAND (exp, i);
2654 tree newop = SUBSTITUTE_PLACEHOLDER_IN_EXPR (op, obj);
2655 if (newop != op)
2657 if (!copy)
2658 copy = copy_node (exp);
2659 TREE_OPERAND (copy, i) = newop;
2662 if (copy)
2663 return fold (copy);
2664 else
2665 return exp;
2668 default:
2669 gcc_unreachable ();
2673 /* Stabilize a reference so that we can use it any number of times
2674 without causing its operands to be evaluated more than once.
2675 Returns the stabilized reference. This works by means of save_expr,
2676 so see the caveats in the comments about save_expr.
2678 Also allows conversion expressions whose operands are references.
2679 Any other kind of expression is returned unchanged. */
2681 tree
2682 stabilize_reference (tree ref)
2684 tree result;
2685 enum tree_code code = TREE_CODE (ref);
2687 switch (code)
2689 case VAR_DECL:
2690 case PARM_DECL:
2691 case RESULT_DECL:
2692 /* No action is needed in this case. */
2693 return ref;
2695 case NOP_EXPR:
2696 case CONVERT_EXPR:
2697 case FLOAT_EXPR:
2698 case FIX_TRUNC_EXPR:
2699 result = build_nt (code, stabilize_reference (TREE_OPERAND (ref, 0)));
2700 break;
2702 case INDIRECT_REF:
2703 result = build_nt (INDIRECT_REF,
2704 stabilize_reference_1 (TREE_OPERAND (ref, 0)));
2705 break;
2707 case COMPONENT_REF:
2708 result = build_nt (COMPONENT_REF,
2709 stabilize_reference (TREE_OPERAND (ref, 0)),
2710 TREE_OPERAND (ref, 1), NULL_TREE);
2711 break;
2713 case BIT_FIELD_REF:
2714 result = build_nt (BIT_FIELD_REF,
2715 stabilize_reference (TREE_OPERAND (ref, 0)),
2716 stabilize_reference_1 (TREE_OPERAND (ref, 1)),
2717 stabilize_reference_1 (TREE_OPERAND (ref, 2)));
2718 break;
2720 case ARRAY_REF:
2721 result = build_nt (ARRAY_REF,
2722 stabilize_reference (TREE_OPERAND (ref, 0)),
2723 stabilize_reference_1 (TREE_OPERAND (ref, 1)),
2724 TREE_OPERAND (ref, 2), TREE_OPERAND (ref, 3));
2725 break;
2727 case ARRAY_RANGE_REF:
2728 result = build_nt (ARRAY_RANGE_REF,
2729 stabilize_reference (TREE_OPERAND (ref, 0)),
2730 stabilize_reference_1 (TREE_OPERAND (ref, 1)),
2731 TREE_OPERAND (ref, 2), TREE_OPERAND (ref, 3));
2732 break;
2734 case COMPOUND_EXPR:
2735 /* We cannot wrap the first expression in a SAVE_EXPR, as then
2736 it wouldn't be ignored. This matters when dealing with
2737 volatiles. */
2738 return stabilize_reference_1 (ref);
2740 /* If arg isn't a kind of lvalue we recognize, make no change.
2741 Caller should recognize the error for an invalid lvalue. */
2742 default:
2743 return ref;
2745 case ERROR_MARK:
2746 return error_mark_node;
2749 TREE_TYPE (result) = TREE_TYPE (ref);
2750 TREE_READONLY (result) = TREE_READONLY (ref);
2751 TREE_SIDE_EFFECTS (result) = TREE_SIDE_EFFECTS (ref);
2752 TREE_THIS_VOLATILE (result) = TREE_THIS_VOLATILE (ref);
2754 return result;
2757 /* Subroutine of stabilize_reference; this is called for subtrees of
2758 references. Any expression with side-effects must be put in a SAVE_EXPR
2759 to ensure that it is only evaluated once.
2761 We don't put SAVE_EXPR nodes around everything, because assigning very
2762 simple expressions to temporaries causes us to miss good opportunities
2763 for optimizations. Among other things, the opportunity to fold in the
2764 addition of a constant into an addressing mode often gets lost, e.g.
2765 "y[i+1] += x;". In general, we take the approach that we should not make
2766 an assignment unless we are forced into it - i.e., that any non-side effect
2767 operator should be allowed, and that cse should take care of coalescing
2768 multiple utterances of the same expression should that prove fruitful. */
2770 tree
2771 stabilize_reference_1 (tree e)
2773 tree result;
2774 enum tree_code code = TREE_CODE (e);
2776 /* We cannot ignore const expressions because it might be a reference
2777 to a const array but whose index contains side-effects. But we can
2778 ignore things that are actual constant or that already have been
2779 handled by this function. */
2781 if (TREE_INVARIANT (e))
2782 return e;
2784 switch (TREE_CODE_CLASS (code))
2786 case tcc_exceptional:
2787 case tcc_type:
2788 case tcc_declaration:
2789 case tcc_comparison:
2790 case tcc_statement:
2791 case tcc_expression:
2792 case tcc_reference:
2793 case tcc_vl_exp:
2794 /* If the expression has side-effects, then encase it in a SAVE_EXPR
2795 so that it will only be evaluated once. */
2796 /* The reference (r) and comparison (<) classes could be handled as
2797 below, but it is generally faster to only evaluate them once. */
2798 if (TREE_SIDE_EFFECTS (e))
2799 return save_expr (e);
2800 return e;
2802 case tcc_constant:
2803 /* Constants need no processing. In fact, we should never reach
2804 here. */
2805 return e;
2807 case tcc_binary:
2808 /* Division is slow and tends to be compiled with jumps,
2809 especially the division by powers of 2 that is often
2810 found inside of an array reference. So do it just once. */
2811 if (code == TRUNC_DIV_EXPR || code == TRUNC_MOD_EXPR
2812 || code == FLOOR_DIV_EXPR || code == FLOOR_MOD_EXPR
2813 || code == CEIL_DIV_EXPR || code == CEIL_MOD_EXPR
2814 || code == ROUND_DIV_EXPR || code == ROUND_MOD_EXPR)
2815 return save_expr (e);
2816 /* Recursively stabilize each operand. */
2817 result = build_nt (code, stabilize_reference_1 (TREE_OPERAND (e, 0)),
2818 stabilize_reference_1 (TREE_OPERAND (e, 1)));
2819 break;
2821 case tcc_unary:
2822 /* Recursively stabilize each operand. */
2823 result = build_nt (code, stabilize_reference_1 (TREE_OPERAND (e, 0)));
2824 break;
2826 default:
2827 gcc_unreachable ();
2830 TREE_TYPE (result) = TREE_TYPE (e);
2831 TREE_READONLY (result) = TREE_READONLY (e);
2832 TREE_SIDE_EFFECTS (result) = TREE_SIDE_EFFECTS (e);
2833 TREE_THIS_VOLATILE (result) = TREE_THIS_VOLATILE (e);
2834 TREE_INVARIANT (result) = 1;
2836 return result;
2839 /* Low-level constructors for expressions. */
2841 /* A helper function for build1 and constant folders. Set TREE_CONSTANT,
2842 TREE_INVARIANT, and TREE_SIDE_EFFECTS for an ADDR_EXPR. */
2844 void
2845 recompute_tree_invariant_for_addr_expr (tree t)
2847 tree node;
2848 bool tc = true, ti = true, se = false;
2850 /* We started out assuming this address is both invariant and constant, but
2851 does not have side effects. Now go down any handled components and see if
2852 any of them involve offsets that are either non-constant or non-invariant.
2853 Also check for side-effects.
2855 ??? Note that this code makes no attempt to deal with the case where
2856 taking the address of something causes a copy due to misalignment. */
2858 #define UPDATE_TITCSE(NODE) \
2859 do { tree _node = (NODE); \
2860 if (_node && !TREE_INVARIANT (_node)) ti = false; \
2861 if (_node && !TREE_CONSTANT (_node)) tc = false; \
2862 if (_node && TREE_SIDE_EFFECTS (_node)) se = true; } while (0)
2864 for (node = TREE_OPERAND (t, 0); handled_component_p (node);
2865 node = TREE_OPERAND (node, 0))
2867 /* If the first operand doesn't have an ARRAY_TYPE, this is a bogus
2868 array reference (probably made temporarily by the G++ front end),
2869 so ignore all the operands. */
2870 if ((TREE_CODE (node) == ARRAY_REF
2871 || TREE_CODE (node) == ARRAY_RANGE_REF)
2872 && TREE_CODE (TREE_TYPE (TREE_OPERAND (node, 0))) == ARRAY_TYPE)
2874 UPDATE_TITCSE (TREE_OPERAND (node, 1));
2875 if (TREE_OPERAND (node, 2))
2876 UPDATE_TITCSE (TREE_OPERAND (node, 2));
2877 if (TREE_OPERAND (node, 3))
2878 UPDATE_TITCSE (TREE_OPERAND (node, 3));
2880 /* Likewise, just because this is a COMPONENT_REF doesn't mean we have a
2881 FIELD_DECL, apparently. The G++ front end can put something else
2882 there, at least temporarily. */
2883 else if (TREE_CODE (node) == COMPONENT_REF
2884 && TREE_CODE (TREE_OPERAND (node, 1)) == FIELD_DECL)
2886 if (TREE_OPERAND (node, 2))
2887 UPDATE_TITCSE (TREE_OPERAND (node, 2));
2889 else if (TREE_CODE (node) == BIT_FIELD_REF)
2890 UPDATE_TITCSE (TREE_OPERAND (node, 2));
2893 node = lang_hooks.expr_to_decl (node, &tc, &ti, &se);
2895 /* Now see what's inside. If it's an INDIRECT_REF, copy our properties from
2896 the address, since &(*a)->b is a form of addition. If it's a decl, it's
2897 invariant and constant if the decl is static. It's also invariant if it's
2898 a decl in the current function. Taking the address of a volatile variable
2899 is not volatile. If it's a constant, the address is both invariant and
2900 constant. Otherwise it's neither. */
2901 if (TREE_CODE (node) == INDIRECT_REF)
2902 UPDATE_TITCSE (TREE_OPERAND (node, 0));
2903 else if (DECL_P (node))
2905 if (staticp (node))
2907 else if (decl_function_context (node) == current_function_decl
2908 /* Addresses of thread-local variables are invariant. */
2909 || (TREE_CODE (node) == VAR_DECL
2910 && DECL_THREAD_LOCAL_P (node)))
2911 tc = false;
2912 else
2913 ti = tc = false;
2915 else if (CONSTANT_CLASS_P (node))
2917 else
2919 ti = tc = false;
2920 se |= TREE_SIDE_EFFECTS (node);
2923 TREE_CONSTANT (t) = tc;
2924 TREE_INVARIANT (t) = ti;
2925 TREE_SIDE_EFFECTS (t) = se;
2926 #undef UPDATE_TITCSE
2929 /* Build an expression of code CODE, data type TYPE, and operands as
2930 specified. Expressions and reference nodes can be created this way.
2931 Constants, decls, types and misc nodes cannot be.
2933 We define 5 non-variadic functions, from 0 to 4 arguments. This is
2934 enough for all extant tree codes. */
2936 tree
2937 build0_stat (enum tree_code code, tree tt MEM_STAT_DECL)
2939 tree t;
2941 gcc_assert (TREE_CODE_LENGTH (code) == 0);
2943 t = make_node_stat (code PASS_MEM_STAT);
2944 TREE_TYPE (t) = tt;
2946 return t;
2949 tree
2950 build1_stat (enum tree_code code, tree type, tree node MEM_STAT_DECL)
2952 int length = sizeof (struct tree_exp);
2953 #ifdef GATHER_STATISTICS
2954 tree_node_kind kind;
2955 #endif
2956 tree t;
2958 #ifdef GATHER_STATISTICS
2959 switch (TREE_CODE_CLASS (code))
2961 case tcc_statement: /* an expression with side effects */
2962 kind = s_kind;
2963 break;
2964 case tcc_reference: /* a reference */
2965 kind = r_kind;
2966 break;
2967 default:
2968 kind = e_kind;
2969 break;
2972 tree_node_counts[(int) kind]++;
2973 tree_node_sizes[(int) kind] += length;
2974 #endif
2976 gcc_assert (TREE_CODE_LENGTH (code) == 1);
2978 t = ggc_alloc_zone_pass_stat (length, &tree_zone);
2980 memset (t, 0, sizeof (struct tree_common));
2982 TREE_SET_CODE (t, code);
2984 TREE_TYPE (t) = type;
2985 #ifdef USE_MAPPED_LOCATION
2986 SET_EXPR_LOCATION (t, UNKNOWN_LOCATION);
2987 #else
2988 SET_EXPR_LOCUS (t, NULL);
2989 #endif
2990 TREE_OPERAND (t, 0) = node;
2991 TREE_BLOCK (t) = NULL_TREE;
2992 if (node && !TYPE_P (node))
2994 TREE_SIDE_EFFECTS (t) = TREE_SIDE_EFFECTS (node);
2995 TREE_READONLY (t) = TREE_READONLY (node);
2998 if (TREE_CODE_CLASS (code) == tcc_statement)
2999 TREE_SIDE_EFFECTS (t) = 1;
3000 else switch (code)
3002 case VA_ARG_EXPR:
3003 /* All of these have side-effects, no matter what their
3004 operands are. */
3005 TREE_SIDE_EFFECTS (t) = 1;
3006 TREE_READONLY (t) = 0;
3007 break;
3009 case MISALIGNED_INDIRECT_REF:
3010 case ALIGN_INDIRECT_REF:
3011 case INDIRECT_REF:
3012 /* Whether a dereference is readonly has nothing to do with whether
3013 its operand is readonly. */
3014 TREE_READONLY (t) = 0;
3015 break;
3017 case ADDR_EXPR:
3018 if (node)
3019 recompute_tree_invariant_for_addr_expr (t);
3020 break;
3022 default:
3023 if ((TREE_CODE_CLASS (code) == tcc_unary || code == VIEW_CONVERT_EXPR)
3024 && node && !TYPE_P (node)
3025 && TREE_CONSTANT (node))
3026 TREE_CONSTANT (t) = 1;
3027 if ((TREE_CODE_CLASS (code) == tcc_unary || code == VIEW_CONVERT_EXPR)
3028 && node && TREE_INVARIANT (node))
3029 TREE_INVARIANT (t) = 1;
3030 if (TREE_CODE_CLASS (code) == tcc_reference
3031 && node && TREE_THIS_VOLATILE (node))
3032 TREE_THIS_VOLATILE (t) = 1;
3033 break;
3036 return t;
3039 #define PROCESS_ARG(N) \
3040 do { \
3041 TREE_OPERAND (t, N) = arg##N; \
3042 if (arg##N &&!TYPE_P (arg##N)) \
3044 if (TREE_SIDE_EFFECTS (arg##N)) \
3045 side_effects = 1; \
3046 if (!TREE_READONLY (arg##N)) \
3047 read_only = 0; \
3048 if (!TREE_CONSTANT (arg##N)) \
3049 constant = 0; \
3050 if (!TREE_INVARIANT (arg##N)) \
3051 invariant = 0; \
3053 } while (0)
3055 tree
3056 build2_stat (enum tree_code code, tree tt, tree arg0, tree arg1 MEM_STAT_DECL)
3058 bool constant, read_only, side_effects, invariant;
3059 tree t;
3061 gcc_assert (TREE_CODE_LENGTH (code) == 2);
3063 #if 1
3064 /* FIXME tuples: Statement's aren't expressions! */
3065 if (code == GIMPLE_MODIFY_STMT)
3066 return build_gimple_modify_stmt_stat (arg0, arg1 PASS_MEM_STAT);
3067 #else
3068 /* Must use build_gimple_modify_stmt to construct GIMPLE_MODIFY_STMTs. */
3069 gcc_assert (code != GIMPLE_MODIFY_STMT);
3070 #endif
3072 t = make_node_stat (code PASS_MEM_STAT);
3073 TREE_TYPE (t) = tt;
3075 /* Below, we automatically set TREE_SIDE_EFFECTS and TREE_READONLY for the
3076 result based on those same flags for the arguments. But if the
3077 arguments aren't really even `tree' expressions, we shouldn't be trying
3078 to do this. */
3080 /* Expressions without side effects may be constant if their
3081 arguments are as well. */
3082 constant = (TREE_CODE_CLASS (code) == tcc_comparison
3083 || TREE_CODE_CLASS (code) == tcc_binary);
3084 read_only = 1;
3085 side_effects = TREE_SIDE_EFFECTS (t);
3086 invariant = constant;
3088 PROCESS_ARG(0);
3089 PROCESS_ARG(1);
3091 TREE_READONLY (t) = read_only;
3092 TREE_CONSTANT (t) = constant;
3093 TREE_INVARIANT (t) = invariant;
3094 TREE_SIDE_EFFECTS (t) = side_effects;
3095 TREE_THIS_VOLATILE (t)
3096 = (TREE_CODE_CLASS (code) == tcc_reference
3097 && arg0 && TREE_THIS_VOLATILE (arg0));
3099 return t;
3103 /* Build a GIMPLE_MODIFY_STMT node. This tree code doesn't have a
3104 type, so we can't use build2 (a.k.a. build2_stat). */
3106 tree
3107 build_gimple_modify_stmt_stat (tree arg0, tree arg1 MEM_STAT_DECL)
3109 tree t;
3111 t = make_node_stat (GIMPLE_MODIFY_STMT PASS_MEM_STAT);
3112 /* ?? We don't care about setting flags for tuples... */
3113 GIMPLE_STMT_OPERAND (t, 0) = arg0;
3114 GIMPLE_STMT_OPERAND (t, 1) = arg1;
3115 return t;
3118 tree
3119 build3_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
3120 tree arg2 MEM_STAT_DECL)
3122 bool constant, read_only, side_effects, invariant;
3123 tree t;
3125 gcc_assert (TREE_CODE_LENGTH (code) == 3);
3126 gcc_assert (TREE_CODE_CLASS (code) != tcc_vl_exp);
3128 t = make_node_stat (code PASS_MEM_STAT);
3129 TREE_TYPE (t) = tt;
3131 /* As a special exception, if COND_EXPR has NULL branches, we
3132 assume that it is a gimple statement and always consider
3133 it to have side effects. */
3134 if (code == COND_EXPR
3135 && tt == void_type_node
3136 && arg1 == NULL_TREE
3137 && arg2 == NULL_TREE)
3138 side_effects = true;
3139 else
3140 side_effects = TREE_SIDE_EFFECTS (t);
3142 PROCESS_ARG(0);
3143 PROCESS_ARG(1);
3144 PROCESS_ARG(2);
3146 TREE_SIDE_EFFECTS (t) = side_effects;
3147 TREE_THIS_VOLATILE (t)
3148 = (TREE_CODE_CLASS (code) == tcc_reference
3149 && arg0 && TREE_THIS_VOLATILE (arg0));
3151 return t;
3154 tree
3155 build4_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
3156 tree arg2, tree arg3 MEM_STAT_DECL)
3158 bool constant, read_only, side_effects, invariant;
3159 tree t;
3161 gcc_assert (TREE_CODE_LENGTH (code) == 4);
3163 t = make_node_stat (code PASS_MEM_STAT);
3164 TREE_TYPE (t) = tt;
3166 side_effects = TREE_SIDE_EFFECTS (t);
3168 PROCESS_ARG(0);
3169 PROCESS_ARG(1);
3170 PROCESS_ARG(2);
3171 PROCESS_ARG(3);
3173 TREE_SIDE_EFFECTS (t) = side_effects;
3174 TREE_THIS_VOLATILE (t)
3175 = (TREE_CODE_CLASS (code) == tcc_reference
3176 && arg0 && TREE_THIS_VOLATILE (arg0));
3178 return t;
3181 tree
3182 build5_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
3183 tree arg2, tree arg3, tree arg4 MEM_STAT_DECL)
3185 bool constant, read_only, side_effects, invariant;
3186 tree t;
3188 gcc_assert (TREE_CODE_LENGTH (code) == 5);
3190 t = make_node_stat (code PASS_MEM_STAT);
3191 TREE_TYPE (t) = tt;
3193 side_effects = TREE_SIDE_EFFECTS (t);
3195 PROCESS_ARG(0);
3196 PROCESS_ARG(1);
3197 PROCESS_ARG(2);
3198 PROCESS_ARG(3);
3199 PROCESS_ARG(4);
3201 TREE_SIDE_EFFECTS (t) = side_effects;
3202 TREE_THIS_VOLATILE (t)
3203 = (TREE_CODE_CLASS (code) == tcc_reference
3204 && arg0 && TREE_THIS_VOLATILE (arg0));
3206 return t;
3209 tree
3210 build7_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
3211 tree arg2, tree arg3, tree arg4, tree arg5,
3212 tree arg6 MEM_STAT_DECL)
3214 bool constant, read_only, side_effects, invariant;
3215 tree t;
3217 gcc_assert (code == TARGET_MEM_REF);
3219 t = make_node_stat (code PASS_MEM_STAT);
3220 TREE_TYPE (t) = tt;
3222 side_effects = TREE_SIDE_EFFECTS (t);
3224 PROCESS_ARG(0);
3225 PROCESS_ARG(1);
3226 PROCESS_ARG(2);
3227 PROCESS_ARG(3);
3228 PROCESS_ARG(4);
3229 PROCESS_ARG(5);
3230 PROCESS_ARG(6);
3232 TREE_SIDE_EFFECTS (t) = side_effects;
3233 TREE_THIS_VOLATILE (t) = 0;
3235 return t;
3238 /* Similar except don't specify the TREE_TYPE
3239 and leave the TREE_SIDE_EFFECTS as 0.
3240 It is permissible for arguments to be null,
3241 or even garbage if their values do not matter. */
3243 tree
3244 build_nt (enum tree_code code, ...)
3246 tree t;
3247 int length;
3248 int i;
3249 va_list p;
3251 gcc_assert (TREE_CODE_CLASS (code) != tcc_vl_exp);
3253 va_start (p, code);
3255 t = make_node (code);
3256 length = TREE_CODE_LENGTH (code);
3258 for (i = 0; i < length; i++)
3259 TREE_OPERAND (t, i) = va_arg (p, tree);
3261 va_end (p);
3262 return t;
3265 /* Similar to build_nt, but for creating a CALL_EXPR object with
3266 ARGLIST passed as a list. */
3268 tree
3269 build_nt_call_list (tree fn, tree arglist)
3271 tree t;
3272 int i;
3274 t = build_vl_exp (CALL_EXPR, list_length (arglist) + 3);
3275 CALL_EXPR_FN (t) = fn;
3276 CALL_EXPR_STATIC_CHAIN (t) = NULL_TREE;
3277 for (i = 0; arglist; arglist = TREE_CHAIN (arglist), i++)
3278 CALL_EXPR_ARG (t, i) = TREE_VALUE (arglist);
3279 return t;
3282 /* Create a DECL_... node of code CODE, name NAME and data type TYPE.
3283 We do NOT enter this node in any sort of symbol table.
3285 layout_decl is used to set up the decl's storage layout.
3286 Other slots are initialized to 0 or null pointers. */
3288 tree
3289 build_decl_stat (enum tree_code code, tree name, tree type MEM_STAT_DECL)
3291 tree t;
3293 t = make_node_stat (code PASS_MEM_STAT);
3295 /* if (type == error_mark_node)
3296 type = integer_type_node; */
3297 /* That is not done, deliberately, so that having error_mark_node
3298 as the type can suppress useless errors in the use of this variable. */
3300 DECL_NAME (t) = name;
3301 TREE_TYPE (t) = type;
3303 if (code == VAR_DECL || code == PARM_DECL || code == RESULT_DECL)
3304 layout_decl (t, 0);
3305 else if (code == FUNCTION_DECL)
3306 DECL_MODE (t) = FUNCTION_MODE;
3308 return t;
3311 /* Builds and returns function declaration with NAME and TYPE. */
3313 tree
3314 build_fn_decl (const char *name, tree type)
3316 tree id = get_identifier (name);
3317 tree decl = build_decl (FUNCTION_DECL, id, type);
3319 DECL_EXTERNAL (decl) = 1;
3320 TREE_PUBLIC (decl) = 1;
3321 DECL_ARTIFICIAL (decl) = 1;
3322 TREE_NOTHROW (decl) = 1;
3324 return decl;
3328 /* BLOCK nodes are used to represent the structure of binding contours
3329 and declarations, once those contours have been exited and their contents
3330 compiled. This information is used for outputting debugging info. */
3332 tree
3333 build_block (tree vars, tree subblocks, tree supercontext, tree chain)
3335 tree block = make_node (BLOCK);
3337 BLOCK_VARS (block) = vars;
3338 BLOCK_SUBBLOCKS (block) = subblocks;
3339 BLOCK_SUPERCONTEXT (block) = supercontext;
3340 BLOCK_CHAIN (block) = chain;
3341 return block;
3344 #if 1 /* ! defined(USE_MAPPED_LOCATION) */
3345 /* ??? gengtype doesn't handle conditionals */
3346 static GTY(()) source_locus last_annotated_node;
3347 #endif
3349 #ifdef USE_MAPPED_LOCATION
3351 expanded_location
3352 expand_location (source_location loc)
3354 expanded_location xloc;
3355 if (loc == 0)
3357 xloc.file = NULL;
3358 xloc.line = 0;
3359 xloc.column = 0;
3361 else
3363 const struct line_map *map = linemap_lookup (&line_table, loc);
3364 xloc.file = map->to_file;
3365 xloc.line = SOURCE_LINE (map, loc);
3366 xloc.column = SOURCE_COLUMN (map, loc);
3368 return xloc;
3371 #else
3373 /* Record the exact location where an expression or an identifier were
3374 encountered. */
3376 void
3377 annotate_with_file_line (tree node, const char *file, int line)
3379 /* Roughly one percent of the calls to this function are to annotate
3380 a node with the same information already attached to that node!
3381 Just return instead of wasting memory. */
3382 if (EXPR_LOCUS (node)
3383 && EXPR_LINENO (node) == line
3384 && (EXPR_FILENAME (node) == file
3385 || !strcmp (EXPR_FILENAME (node), file)))
3387 last_annotated_node = EXPR_LOCUS (node);
3388 return;
3391 /* In heavily macroized code (such as GCC itself) this single
3392 entry cache can reduce the number of allocations by more
3393 than half. */
3394 if (last_annotated_node
3395 && last_annotated_node->line == line
3396 && (last_annotated_node->file == file
3397 || !strcmp (last_annotated_node->file, file)))
3399 SET_EXPR_LOCUS (node, last_annotated_node);
3400 return;
3403 SET_EXPR_LOCUS (node, ggc_alloc (sizeof (location_t)));
3404 EXPR_LINENO (node) = line;
3405 EXPR_FILENAME (node) = file;
3406 last_annotated_node = EXPR_LOCUS (node);
3409 void
3410 annotate_with_locus (tree node, location_t locus)
3412 annotate_with_file_line (node, locus.file, locus.line);
3414 #endif
3416 /* Source location accessor functions. */
3419 /* The source location of this expression. Non-tree_exp nodes such as
3420 decls and constants can be shared among multiple locations, so
3421 return nothing. */
3422 location_t
3423 expr_location (tree node)
3425 #ifdef USE_MAPPED_LOCATION
3426 if (GIMPLE_STMT_P (node))
3427 return GIMPLE_STMT_LOCUS (node);
3428 return EXPR_P (node) ? node->exp.locus : UNKNOWN_LOCATION;
3429 #else
3430 if (GIMPLE_STMT_P (node))
3431 return EXPR_HAS_LOCATION (node)
3432 ? *GIMPLE_STMT_LOCUS (node) : UNKNOWN_LOCATION;
3433 return EXPR_HAS_LOCATION (node) ? *node->exp.locus : UNKNOWN_LOCATION;
3434 #endif
3437 void
3438 set_expr_location (tree node, location_t locus)
3440 #ifdef USE_MAPPED_LOCATION
3441 if (GIMPLE_STMT_P (node))
3442 GIMPLE_STMT_LOCUS (node) = locus;
3443 else
3444 EXPR_CHECK (node)->exp.locus = locus;
3445 #else
3446 annotate_with_locus (node, locus);
3447 #endif
3450 bool
3451 expr_has_location (tree node)
3453 #ifdef USE_MAPPED_LOCATION
3454 return expr_location (node) != UNKNOWN_LOCATION;
3455 #else
3456 return expr_locus (node) != NULL;
3457 #endif
3460 #ifdef USE_MAPPED_LOCATION
3461 source_location *
3462 #else
3463 source_locus
3464 #endif
3465 expr_locus (tree node)
3467 #ifdef USE_MAPPED_LOCATION
3468 if (GIMPLE_STMT_P (node))
3469 return &GIMPLE_STMT_LOCUS (node);
3470 return EXPR_P (node) ? &node->exp.locus : (location_t *) NULL;
3471 #else
3472 if (GIMPLE_STMT_P (node))
3473 return GIMPLE_STMT_LOCUS (node);
3474 /* ?? The cast below was originally "(location_t *)" in the macro,
3475 but that makes no sense. ?? */
3476 return EXPR_P (node) ? node->exp.locus : (source_locus) NULL;
3477 #endif
3480 void
3481 set_expr_locus (tree node,
3482 #ifdef USE_MAPPED_LOCATION
3483 source_location *loc
3484 #else
3485 source_locus loc
3486 #endif
3489 #ifdef USE_MAPPED_LOCATION
3490 if (loc == NULL)
3492 if (GIMPLE_STMT_P (node))
3493 GIMPLE_STMT_LOCUS (node) = UNKNOWN_LOCATION;
3494 else
3495 EXPR_CHECK (node)->exp.locus = UNKNOWN_LOCATION;
3497 else
3499 if (GIMPLE_STMT_P (node))
3500 GIMPLE_STMT_LOCUS (node) = *loc;
3501 else
3502 EXPR_CHECK (node)->exp.locus = *loc;
3504 #else
3505 if (GIMPLE_STMT_P (node))
3506 GIMPLE_STMT_LOCUS (node) = loc;
3507 else
3508 EXPR_CHECK (node)->exp.locus = loc;
3509 #endif
3512 const char **
3513 expr_filename (tree node)
3515 #ifdef USE_MAPPED_LOCATION
3516 if (GIMPLE_STMT_P (node))
3517 return &LOCATION_FILE (GIMPLE_STMT_LOCUS (node));
3518 return &LOCATION_FILE (EXPR_CHECK (node)->exp.locus);
3519 #else
3520 if (GIMPLE_STMT_P (node))
3521 return &GIMPLE_STMT_LOCUS (node)->file;
3522 return &(EXPR_CHECK (node)->exp.locus->file);
3523 #endif
3526 int *
3527 expr_lineno (tree node)
3529 #ifdef USE_MAPPED_LOCATION
3530 if (GIMPLE_STMT_P (node))
3531 return &LOCATION_LINE (GIMPLE_STMT_LOCUS (node));
3532 return &LOCATION_LINE (EXPR_CHECK (node)->exp.locus);
3533 #else
3534 if (GIMPLE_STMT_P (node))
3535 return &GIMPLE_STMT_LOCUS (node)->line;
3536 return &EXPR_CHECK (node)->exp.locus->line;
3537 #endif
3540 /* Return a declaration like DDECL except that its DECL_ATTRIBUTES
3541 is ATTRIBUTE. */
3543 tree
3544 build_decl_attribute_variant (tree ddecl, tree attribute)
3546 DECL_ATTRIBUTES (ddecl) = attribute;
3547 return ddecl;
3550 /* Borrowed from hashtab.c iterative_hash implementation. */
3551 #define mix(a,b,c) \
3553 a -= b; a -= c; a ^= (c>>13); \
3554 b -= c; b -= a; b ^= (a<< 8); \
3555 c -= a; c -= b; c ^= ((b&0xffffffff)>>13); \
3556 a -= b; a -= c; a ^= ((c&0xffffffff)>>12); \
3557 b -= c; b -= a; b = (b ^ (a<<16)) & 0xffffffff; \
3558 c -= a; c -= b; c = (c ^ (b>> 5)) & 0xffffffff; \
3559 a -= b; a -= c; a = (a ^ (c>> 3)) & 0xffffffff; \
3560 b -= c; b -= a; b = (b ^ (a<<10)) & 0xffffffff; \
3561 c -= a; c -= b; c = (c ^ (b>>15)) & 0xffffffff; \
3565 /* Produce good hash value combining VAL and VAL2. */
3566 static inline hashval_t
3567 iterative_hash_hashval_t (hashval_t val, hashval_t val2)
3569 /* the golden ratio; an arbitrary value. */
3570 hashval_t a = 0x9e3779b9;
3572 mix (a, val, val2);
3573 return val2;
3576 /* Produce good hash value combining PTR and VAL2. */
3577 static inline hashval_t
3578 iterative_hash_pointer (void *ptr, hashval_t val2)
3580 if (sizeof (ptr) == sizeof (hashval_t))
3581 return iterative_hash_hashval_t ((size_t) ptr, val2);
3582 else
3584 hashval_t a = (hashval_t) (size_t) ptr;
3585 /* Avoid warnings about shifting of more than the width of the type on
3586 hosts that won't execute this path. */
3587 int zero = 0;
3588 hashval_t b = (hashval_t) ((size_t) ptr >> (sizeof (hashval_t) * 8 + zero));
3589 mix (a, b, val2);
3590 return val2;
3594 /* Produce good hash value combining VAL and VAL2. */
3595 static inline hashval_t
3596 iterative_hash_host_wide_int (HOST_WIDE_INT val, hashval_t val2)
3598 if (sizeof (HOST_WIDE_INT) == sizeof (hashval_t))
3599 return iterative_hash_hashval_t (val, val2);
3600 else
3602 hashval_t a = (hashval_t) val;
3603 /* Avoid warnings about shifting of more than the width of the type on
3604 hosts that won't execute this path. */
3605 int zero = 0;
3606 hashval_t b = (hashval_t) (val >> (sizeof (hashval_t) * 8 + zero));
3607 mix (a, b, val2);
3608 if (sizeof (HOST_WIDE_INT) > 2 * sizeof (hashval_t))
3610 hashval_t a = (hashval_t) (val >> (sizeof (hashval_t) * 16 + zero));
3611 hashval_t b = (hashval_t) (val >> (sizeof (hashval_t) * 24 + zero));
3612 mix (a, b, val2);
3614 return val2;
3618 /* Return a type like TTYPE except that its TYPE_ATTRIBUTE
3619 is ATTRIBUTE and its qualifiers are QUALS.
3621 Record such modified types already made so we don't make duplicates. */
3623 static tree
3624 build_type_attribute_qual_variant (tree ttype, tree attribute, int quals)
3626 if (! attribute_list_equal (TYPE_ATTRIBUTES (ttype), attribute))
3628 hashval_t hashcode = 0;
3629 tree ntype;
3630 enum tree_code code = TREE_CODE (ttype);
3632 ntype = copy_node (ttype);
3634 TYPE_POINTER_TO (ntype) = 0;
3635 TYPE_REFERENCE_TO (ntype) = 0;
3636 TYPE_ATTRIBUTES (ntype) = attribute;
3638 if (TYPE_STRUCTURAL_EQUALITY_P (ttype))
3639 SET_TYPE_STRUCTURAL_EQUALITY (ntype);
3640 else
3641 TYPE_CANONICAL (ntype)
3642 = build_qualified_type (TYPE_CANONICAL (ttype), quals);
3644 /* Create a new main variant of TYPE. */
3645 TYPE_MAIN_VARIANT (ntype) = ntype;
3646 TYPE_NEXT_VARIANT (ntype) = 0;
3647 set_type_quals (ntype, TYPE_UNQUALIFIED);
3649 hashcode = iterative_hash_object (code, hashcode);
3650 if (TREE_TYPE (ntype))
3651 hashcode = iterative_hash_object (TYPE_HASH (TREE_TYPE (ntype)),
3652 hashcode);
3653 hashcode = attribute_hash_list (attribute, hashcode);
3655 switch (TREE_CODE (ntype))
3657 case FUNCTION_TYPE:
3658 hashcode = type_hash_list (TYPE_ARG_TYPES (ntype), hashcode);
3659 break;
3660 case ARRAY_TYPE:
3661 hashcode = iterative_hash_object (TYPE_HASH (TYPE_DOMAIN (ntype)),
3662 hashcode);
3663 break;
3664 case INTEGER_TYPE:
3665 hashcode = iterative_hash_object
3666 (TREE_INT_CST_LOW (TYPE_MAX_VALUE (ntype)), hashcode);
3667 hashcode = iterative_hash_object
3668 (TREE_INT_CST_HIGH (TYPE_MAX_VALUE (ntype)), hashcode);
3669 break;
3670 case REAL_TYPE:
3672 unsigned int precision = TYPE_PRECISION (ntype);
3673 hashcode = iterative_hash_object (precision, hashcode);
3675 break;
3676 default:
3677 break;
3680 ntype = type_hash_canon (hashcode, ntype);
3682 /* If the target-dependent attributes make NTYPE different from
3683 its canonical type, we will need to use structural equality
3684 checks for this qualified type. */
3685 if (!targetm.comp_type_attributes (ntype, ttype))
3686 SET_TYPE_STRUCTURAL_EQUALITY (ntype);
3688 ttype = build_qualified_type (ntype, quals);
3691 return ttype;
3695 /* Return a type like TTYPE except that its TYPE_ATTRIBUTE
3696 is ATTRIBUTE.
3698 Record such modified types already made so we don't make duplicates. */
3700 tree
3701 build_type_attribute_variant (tree ttype, tree attribute)
3703 return build_type_attribute_qual_variant (ttype, attribute,
3704 TYPE_QUALS (ttype));
3707 /* Return nonzero if IDENT is a valid name for attribute ATTR,
3708 or zero if not.
3710 We try both `text' and `__text__', ATTR may be either one. */
3711 /* ??? It might be a reasonable simplification to require ATTR to be only
3712 `text'. One might then also require attribute lists to be stored in
3713 their canonicalized form. */
3715 static int
3716 is_attribute_with_length_p (const char *attr, int attr_len, tree ident)
3718 int ident_len;
3719 const char *p;
3721 if (TREE_CODE (ident) != IDENTIFIER_NODE)
3722 return 0;
3724 p = IDENTIFIER_POINTER (ident);
3725 ident_len = IDENTIFIER_LENGTH (ident);
3727 if (ident_len == attr_len
3728 && strcmp (attr, p) == 0)
3729 return 1;
3731 /* If ATTR is `__text__', IDENT must be `text'; and vice versa. */
3732 if (attr[0] == '_')
3734 gcc_assert (attr[1] == '_');
3735 gcc_assert (attr[attr_len - 2] == '_');
3736 gcc_assert (attr[attr_len - 1] == '_');
3737 if (ident_len == attr_len - 4
3738 && strncmp (attr + 2, p, attr_len - 4) == 0)
3739 return 1;
3741 else
3743 if (ident_len == attr_len + 4
3744 && p[0] == '_' && p[1] == '_'
3745 && p[ident_len - 2] == '_' && p[ident_len - 1] == '_'
3746 && strncmp (attr, p + 2, attr_len) == 0)
3747 return 1;
3750 return 0;
3753 /* Return nonzero if IDENT is a valid name for attribute ATTR,
3754 or zero if not.
3756 We try both `text' and `__text__', ATTR may be either one. */
3759 is_attribute_p (const char *attr, tree ident)
3761 return is_attribute_with_length_p (attr, strlen (attr), ident);
3764 /* Given an attribute name and a list of attributes, return a pointer to the
3765 attribute's list element if the attribute is part of the list, or NULL_TREE
3766 if not found. If the attribute appears more than once, this only
3767 returns the first occurrence; the TREE_CHAIN of the return value should
3768 be passed back in if further occurrences are wanted. */
3770 tree
3771 lookup_attribute (const char *attr_name, tree list)
3773 tree l;
3774 size_t attr_len = strlen (attr_name);
3776 for (l = list; l; l = TREE_CHAIN (l))
3778 gcc_assert (TREE_CODE (TREE_PURPOSE (l)) == IDENTIFIER_NODE);
3779 if (is_attribute_with_length_p (attr_name, attr_len, TREE_PURPOSE (l)))
3780 return l;
3783 return NULL_TREE;
3786 /* Remove any instances of attribute ATTR_NAME in LIST and return the
3787 modified list. */
3789 tree
3790 remove_attribute (const char *attr_name, tree list)
3792 tree *p;
3793 size_t attr_len = strlen (attr_name);
3795 for (p = &list; *p; )
3797 tree l = *p;
3798 gcc_assert (TREE_CODE (TREE_PURPOSE (l)) == IDENTIFIER_NODE);
3799 if (is_attribute_with_length_p (attr_name, attr_len, TREE_PURPOSE (l)))
3800 *p = TREE_CHAIN (l);
3801 else
3802 p = &TREE_CHAIN (l);
3805 return list;
3808 /* Return an attribute list that is the union of a1 and a2. */
3810 tree
3811 merge_attributes (tree a1, tree a2)
3813 tree attributes;
3815 /* Either one unset? Take the set one. */
3817 if ((attributes = a1) == 0)
3818 attributes = a2;
3820 /* One that completely contains the other? Take it. */
3822 else if (a2 != 0 && ! attribute_list_contained (a1, a2))
3824 if (attribute_list_contained (a2, a1))
3825 attributes = a2;
3826 else
3828 /* Pick the longest list, and hang on the other list. */
3830 if (list_length (a1) < list_length (a2))
3831 attributes = a2, a2 = a1;
3833 for (; a2 != 0; a2 = TREE_CHAIN (a2))
3835 tree a;
3836 for (a = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (a2)),
3837 attributes);
3838 a != NULL_TREE;
3839 a = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (a2)),
3840 TREE_CHAIN (a)))
3842 if (TREE_VALUE (a) != NULL
3843 && TREE_CODE (TREE_VALUE (a)) == TREE_LIST
3844 && TREE_VALUE (a2) != NULL
3845 && TREE_CODE (TREE_VALUE (a2)) == TREE_LIST)
3847 if (simple_cst_list_equal (TREE_VALUE (a),
3848 TREE_VALUE (a2)) == 1)
3849 break;
3851 else if (simple_cst_equal (TREE_VALUE (a),
3852 TREE_VALUE (a2)) == 1)
3853 break;
3855 if (a == NULL_TREE)
3857 a1 = copy_node (a2);
3858 TREE_CHAIN (a1) = attributes;
3859 attributes = a1;
3864 return attributes;
3867 /* Given types T1 and T2, merge their attributes and return
3868 the result. */
3870 tree
3871 merge_type_attributes (tree t1, tree t2)
3873 return merge_attributes (TYPE_ATTRIBUTES (t1),
3874 TYPE_ATTRIBUTES (t2));
3877 /* Given decls OLDDECL and NEWDECL, merge their attributes and return
3878 the result. */
3880 tree
3881 merge_decl_attributes (tree olddecl, tree newdecl)
3883 return merge_attributes (DECL_ATTRIBUTES (olddecl),
3884 DECL_ATTRIBUTES (newdecl));
3887 #if TARGET_DLLIMPORT_DECL_ATTRIBUTES
3889 /* Specialization of merge_decl_attributes for various Windows targets.
3891 This handles the following situation:
3893 __declspec (dllimport) int foo;
3894 int foo;
3896 The second instance of `foo' nullifies the dllimport. */
3898 tree
3899 merge_dllimport_decl_attributes (tree old, tree new)
3901 tree a;
3902 int delete_dllimport_p = 1;
3904 /* What we need to do here is remove from `old' dllimport if it doesn't
3905 appear in `new'. dllimport behaves like extern: if a declaration is
3906 marked dllimport and a definition appears later, then the object
3907 is not dllimport'd. We also remove a `new' dllimport if the old list
3908 contains dllexport: dllexport always overrides dllimport, regardless
3909 of the order of declaration. */
3910 if (!VAR_OR_FUNCTION_DECL_P (new))
3911 delete_dllimport_p = 0;
3912 else if (DECL_DLLIMPORT_P (new)
3913 && lookup_attribute ("dllexport", DECL_ATTRIBUTES (old)))
3915 DECL_DLLIMPORT_P (new) = 0;
3916 warning (OPT_Wattributes, "%q+D already declared with dllexport attribute: "
3917 "dllimport ignored", new);
3919 else if (DECL_DLLIMPORT_P (old) && !DECL_DLLIMPORT_P (new))
3921 /* Warn about overriding a symbol that has already been used. eg:
3922 extern int __attribute__ ((dllimport)) foo;
3923 int* bar () {return &foo;}
3924 int foo;
3926 if (TREE_USED (old))
3928 warning (0, "%q+D redeclared without dllimport attribute "
3929 "after being referenced with dll linkage", new);
3930 /* If we have used a variable's address with dllimport linkage,
3931 keep the old DECL_DLLIMPORT_P flag: the ADDR_EXPR using the
3932 decl may already have had TREE_INVARIANT and TREE_CONSTANT
3933 computed.
3934 We still remove the attribute so that assembler code refers
3935 to '&foo rather than '_imp__foo'. */
3936 if (TREE_CODE (old) == VAR_DECL && TREE_ADDRESSABLE (old))
3937 DECL_DLLIMPORT_P (new) = 1;
3940 /* Let an inline definition silently override the external reference,
3941 but otherwise warn about attribute inconsistency. */
3942 else if (TREE_CODE (new) == VAR_DECL
3943 || !DECL_DECLARED_INLINE_P (new))
3944 warning (OPT_Wattributes, "%q+D redeclared without dllimport attribute: "
3945 "previous dllimport ignored", new);
3947 else
3948 delete_dllimport_p = 0;
3950 a = merge_attributes (DECL_ATTRIBUTES (old), DECL_ATTRIBUTES (new));
3952 if (delete_dllimport_p)
3954 tree prev, t;
3955 const size_t attr_len = strlen ("dllimport");
3957 /* Scan the list for dllimport and delete it. */
3958 for (prev = NULL_TREE, t = a; t; prev = t, t = TREE_CHAIN (t))
3960 if (is_attribute_with_length_p ("dllimport", attr_len,
3961 TREE_PURPOSE (t)))
3963 if (prev == NULL_TREE)
3964 a = TREE_CHAIN (a);
3965 else
3966 TREE_CHAIN (prev) = TREE_CHAIN (t);
3967 break;
3972 return a;
3975 /* Handle a "dllimport" or "dllexport" attribute; arguments as in
3976 struct attribute_spec.handler. */
3978 tree
3979 handle_dll_attribute (tree * pnode, tree name, tree args, int flags,
3980 bool *no_add_attrs)
3982 tree node = *pnode;
3984 /* These attributes may apply to structure and union types being created,
3985 but otherwise should pass to the declaration involved. */
3986 if (!DECL_P (node))
3988 if (flags & ((int) ATTR_FLAG_DECL_NEXT | (int) ATTR_FLAG_FUNCTION_NEXT
3989 | (int) ATTR_FLAG_ARRAY_NEXT))
3991 *no_add_attrs = true;
3992 return tree_cons (name, args, NULL_TREE);
3994 if (TREE_CODE (node) != RECORD_TYPE && TREE_CODE (node) != UNION_TYPE)
3996 warning (OPT_Wattributes, "%qs attribute ignored",
3997 IDENTIFIER_POINTER (name));
3998 *no_add_attrs = true;
4001 return NULL_TREE;
4004 if (TREE_CODE (node) != FUNCTION_DECL
4005 && TREE_CODE (node) != VAR_DECL)
4007 *no_add_attrs = true;
4008 warning (OPT_Wattributes, "%qs attribute ignored",
4009 IDENTIFIER_POINTER (name));
4010 return NULL_TREE;
4013 /* Report error on dllimport ambiguities seen now before they cause
4014 any damage. */
4015 else if (is_attribute_p ("dllimport", name))
4017 /* Honor any target-specific overrides. */
4018 if (!targetm.valid_dllimport_attribute_p (node))
4019 *no_add_attrs = true;
4021 else if (TREE_CODE (node) == FUNCTION_DECL
4022 && DECL_DECLARED_INLINE_P (node))
4024 warning (OPT_Wattributes, "inline function %q+D declared as "
4025 " dllimport: attribute ignored", node);
4026 *no_add_attrs = true;
4028 /* Like MS, treat definition of dllimported variables and
4029 non-inlined functions on declaration as syntax errors. */
4030 else if (TREE_CODE (node) == FUNCTION_DECL && DECL_INITIAL (node))
4032 error ("function %q+D definition is marked dllimport", node);
4033 *no_add_attrs = true;
4036 else if (TREE_CODE (node) == VAR_DECL)
4038 if (DECL_INITIAL (node))
4040 error ("variable %q+D definition is marked dllimport",
4041 node);
4042 *no_add_attrs = true;
4045 /* `extern' needn't be specified with dllimport.
4046 Specify `extern' now and hope for the best. Sigh. */
4047 DECL_EXTERNAL (node) = 1;
4048 /* Also, implicitly give dllimport'd variables declared within
4049 a function global scope, unless declared static. */
4050 if (current_function_decl != NULL_TREE && !TREE_STATIC (node))
4051 TREE_PUBLIC (node) = 1;
4054 if (*no_add_attrs == false)
4055 DECL_DLLIMPORT_P (node) = 1;
4058 /* Report error if symbol is not accessible at global scope. */
4059 if (!TREE_PUBLIC (node)
4060 && (TREE_CODE (node) == VAR_DECL
4061 || TREE_CODE (node) == FUNCTION_DECL))
4063 error ("external linkage required for symbol %q+D because of "
4064 "%qs attribute", node, IDENTIFIER_POINTER (name));
4065 *no_add_attrs = true;
4068 return NULL_TREE;
4071 #endif /* TARGET_DLLIMPORT_DECL_ATTRIBUTES */
4073 /* Set the type qualifiers for TYPE to TYPE_QUALS, which is a bitmask
4074 of the various TYPE_QUAL values. */
4076 static void
4077 set_type_quals (tree type, int type_quals)
4079 TYPE_READONLY (type) = (type_quals & TYPE_QUAL_CONST) != 0;
4080 TYPE_VOLATILE (type) = (type_quals & TYPE_QUAL_VOLATILE) != 0;
4081 TYPE_RESTRICT (type) = (type_quals & TYPE_QUAL_RESTRICT) != 0;
4084 /* Returns true iff cand is equivalent to base with type_quals. */
4086 bool
4087 check_qualified_type (tree cand, tree base, int type_quals)
4089 return (TYPE_QUALS (cand) == type_quals
4090 && TYPE_NAME (cand) == TYPE_NAME (base)
4091 /* Apparently this is needed for Objective-C. */
4092 && TYPE_CONTEXT (cand) == TYPE_CONTEXT (base)
4093 && attribute_list_equal (TYPE_ATTRIBUTES (cand),
4094 TYPE_ATTRIBUTES (base)));
4097 /* Return a version of the TYPE, qualified as indicated by the
4098 TYPE_QUALS, if one exists. If no qualified version exists yet,
4099 return NULL_TREE. */
4101 tree
4102 get_qualified_type (tree type, int type_quals)
4104 tree t;
4106 if (TYPE_QUALS (type) == type_quals)
4107 return type;
4109 /* Search the chain of variants to see if there is already one there just
4110 like the one we need to have. If so, use that existing one. We must
4111 preserve the TYPE_NAME, since there is code that depends on this. */
4112 for (t = TYPE_MAIN_VARIANT (type); t; t = TYPE_NEXT_VARIANT (t))
4113 if (check_qualified_type (t, type, type_quals))
4114 return t;
4116 return NULL_TREE;
4119 /* Like get_qualified_type, but creates the type if it does not
4120 exist. This function never returns NULL_TREE. */
4122 tree
4123 build_qualified_type (tree type, int type_quals)
4125 tree t;
4127 /* See if we already have the appropriate qualified variant. */
4128 t = get_qualified_type (type, type_quals);
4130 /* If not, build it. */
4131 if (!t)
4133 t = build_variant_type_copy (type);
4134 set_type_quals (t, type_quals);
4136 if (TYPE_STRUCTURAL_EQUALITY_P (type))
4137 /* Propagate structural equality. */
4138 SET_TYPE_STRUCTURAL_EQUALITY (t);
4139 else if (TYPE_CANONICAL (type) != type)
4140 /* Build the underlying canonical type, since it is different
4141 from TYPE. */
4142 TYPE_CANONICAL (t) = build_qualified_type (TYPE_CANONICAL (type),
4143 type_quals);
4144 else
4145 /* T is its own canonical type. */
4146 TYPE_CANONICAL (t) = t;
4150 return t;
4153 /* Create a new distinct copy of TYPE. The new type is made its own
4154 MAIN_VARIANT. If TYPE requires structural equality checks, the
4155 resulting type requires structural equality checks; otherwise, its
4156 TYPE_CANONICAL points to itself. */
4158 tree
4159 build_distinct_type_copy (tree type)
4161 tree t = copy_node (type);
4163 TYPE_POINTER_TO (t) = 0;
4164 TYPE_REFERENCE_TO (t) = 0;
4166 /* Set the canonical type either to a new equivalence class, or
4167 propagate the need for structural equality checks. */
4168 if (TYPE_STRUCTURAL_EQUALITY_P (type))
4169 SET_TYPE_STRUCTURAL_EQUALITY (t);
4170 else
4171 TYPE_CANONICAL (t) = t;
4173 /* Make it its own variant. */
4174 TYPE_MAIN_VARIANT (t) = t;
4175 TYPE_NEXT_VARIANT (t) = 0;
4177 /* Note that it is now possible for TYPE_MIN_VALUE to be a value
4178 whose TREE_TYPE is not t. This can also happen in the Ada
4179 frontend when using subtypes. */
4181 return t;
4184 /* Create a new variant of TYPE, equivalent but distinct. This is so
4185 the caller can modify it. TYPE_CANONICAL for the return type will
4186 be equivalent to TYPE_CANONICAL of TYPE, indicating that the types
4187 are considered equal by the language itself (or that both types
4188 require structural equality checks). */
4190 tree
4191 build_variant_type_copy (tree type)
4193 tree t, m = TYPE_MAIN_VARIANT (type);
4195 t = build_distinct_type_copy (type);
4197 /* Since we're building a variant, assume that it is a non-semantic
4198 variant. This also propagates TYPE_STRUCTURAL_EQUALITY_P. */
4199 TYPE_CANONICAL (t) = TYPE_CANONICAL (type);
4201 /* Add the new type to the chain of variants of TYPE. */
4202 TYPE_NEXT_VARIANT (t) = TYPE_NEXT_VARIANT (m);
4203 TYPE_NEXT_VARIANT (m) = t;
4204 TYPE_MAIN_VARIANT (t) = m;
4206 return t;
4209 /* Return true if the from tree in both tree maps are equal. */
4212 tree_map_base_eq (const void *va, const void *vb)
4214 const struct tree_map_base *a = va, *b = vb;
4215 return (a->from == b->from);
4218 /* Hash a from tree in a tree_map. */
4220 unsigned int
4221 tree_map_base_hash (const void *item)
4223 return htab_hash_pointer (((const struct tree_map_base *)item)->from);
4226 /* Return true if this tree map structure is marked for garbage collection
4227 purposes. We simply return true if the from tree is marked, so that this
4228 structure goes away when the from tree goes away. */
4231 tree_map_base_marked_p (const void *p)
4233 return ggc_marked_p (((struct tree_map_base *) p)->from);
4236 unsigned int
4237 tree_map_hash (const void *item)
4239 return (((const struct tree_map *) item)->hash);
4242 /* Return the initialization priority for DECL. */
4244 priority_type
4245 decl_init_priority_lookup (tree decl)
4247 struct tree_priority_map *h;
4248 struct tree_map_base in;
4250 gcc_assert (VAR_OR_FUNCTION_DECL_P (decl));
4251 gcc_assert (TREE_CODE (decl) == VAR_DECL
4252 ? DECL_HAS_INIT_PRIORITY_P (decl)
4253 : DECL_STATIC_CONSTRUCTOR (decl));
4254 in.from = decl;
4255 h = htab_find (init_priority_for_decl, &in);
4256 return h ? h->init : DEFAULT_INIT_PRIORITY;
4259 /* Return the finalization priority for DECL. */
4261 priority_type
4262 decl_fini_priority_lookup (tree decl)
4264 struct tree_priority_map *h;
4265 struct tree_map_base in;
4267 gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
4268 gcc_assert (DECL_STATIC_DESTRUCTOR (decl));
4269 in.from = decl;
4270 h = htab_find (init_priority_for_decl, &in);
4271 return h ? h->fini : DEFAULT_INIT_PRIORITY;
4274 /* Return the initialization and finalization priority information for
4275 DECL. If there is no previous priority information, a freshly
4276 allocated structure is returned. */
4278 static struct tree_priority_map *
4279 decl_priority_info (tree decl)
4281 struct tree_priority_map in;
4282 struct tree_priority_map *h;
4283 void **loc;
4285 in.base.from = decl;
4286 loc = htab_find_slot (init_priority_for_decl, &in, INSERT);
4287 h = *loc;
4288 if (!h)
4290 h = GGC_CNEW (struct tree_priority_map);
4291 *loc = h;
4292 h->base.from = decl;
4293 h->init = DEFAULT_INIT_PRIORITY;
4294 h->fini = DEFAULT_INIT_PRIORITY;
4297 return h;
4300 /* Set the initialization priority for DECL to PRIORITY. */
4302 void
4303 decl_init_priority_insert (tree decl, priority_type priority)
4305 struct tree_priority_map *h;
4307 gcc_assert (VAR_OR_FUNCTION_DECL_P (decl));
4308 h = decl_priority_info (decl);
4309 h->init = priority;
4312 /* Set the finalization priority for DECL to PRIORITY. */
4314 void
4315 decl_fini_priority_insert (tree decl, priority_type priority)
4317 struct tree_priority_map *h;
4319 gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
4320 h = decl_priority_info (decl);
4321 h->fini = priority;
4324 /* Look up a restrict qualified base decl for FROM. */
4326 tree
4327 decl_restrict_base_lookup (tree from)
4329 struct tree_map *h;
4330 struct tree_map in;
4332 in.base.from = from;
4333 h = htab_find_with_hash (restrict_base_for_decl, &in,
4334 htab_hash_pointer (from));
4335 return h ? h->to : NULL_TREE;
4338 /* Record the restrict qualified base TO for FROM. */
4340 void
4341 decl_restrict_base_insert (tree from, tree to)
4343 struct tree_map *h;
4344 void **loc;
4346 h = ggc_alloc (sizeof (struct tree_map));
4347 h->hash = htab_hash_pointer (from);
4348 h->base.from = from;
4349 h->to = to;
4350 loc = htab_find_slot_with_hash (restrict_base_for_decl, h, h->hash, INSERT);
4351 *(struct tree_map **) loc = h;
4354 /* Print out the statistics for the DECL_DEBUG_EXPR hash table. */
4356 static void
4357 print_debug_expr_statistics (void)
4359 fprintf (stderr, "DECL_DEBUG_EXPR hash: size %ld, %ld elements, %f collisions\n",
4360 (long) htab_size (debug_expr_for_decl),
4361 (long) htab_elements (debug_expr_for_decl),
4362 htab_collisions (debug_expr_for_decl));
4365 /* Print out the statistics for the DECL_VALUE_EXPR hash table. */
4367 static void
4368 print_value_expr_statistics (void)
4370 fprintf (stderr, "DECL_VALUE_EXPR hash: size %ld, %ld elements, %f collisions\n",
4371 (long) htab_size (value_expr_for_decl),
4372 (long) htab_elements (value_expr_for_decl),
4373 htab_collisions (value_expr_for_decl));
4376 /* Print out statistics for the RESTRICT_BASE_FOR_DECL hash table, but
4377 don't print anything if the table is empty. */
4379 static void
4380 print_restrict_base_statistics (void)
4382 if (htab_elements (restrict_base_for_decl) != 0)
4383 fprintf (stderr,
4384 "RESTRICT_BASE hash: size %ld, %ld elements, %f collisions\n",
4385 (long) htab_size (restrict_base_for_decl),
4386 (long) htab_elements (restrict_base_for_decl),
4387 htab_collisions (restrict_base_for_decl));
4390 /* Lookup a debug expression for FROM, and return it if we find one. */
4392 tree
4393 decl_debug_expr_lookup (tree from)
4395 struct tree_map *h, in;
4396 in.base.from = from;
4398 h = htab_find_with_hash (debug_expr_for_decl, &in, htab_hash_pointer (from));
4399 if (h)
4400 return h->to;
4401 return NULL_TREE;
4404 /* Insert a mapping FROM->TO in the debug expression hashtable. */
4406 void
4407 decl_debug_expr_insert (tree from, tree to)
4409 struct tree_map *h;
4410 void **loc;
4412 h = ggc_alloc (sizeof (struct tree_map));
4413 h->hash = htab_hash_pointer (from);
4414 h->base.from = from;
4415 h->to = to;
4416 loc = htab_find_slot_with_hash (debug_expr_for_decl, h, h->hash, INSERT);
4417 *(struct tree_map **) loc = h;
4420 /* Lookup a value expression for FROM, and return it if we find one. */
4422 tree
4423 decl_value_expr_lookup (tree from)
4425 struct tree_map *h, in;
4426 in.base.from = from;
4428 h = htab_find_with_hash (value_expr_for_decl, &in, htab_hash_pointer (from));
4429 if (h)
4430 return h->to;
4431 return NULL_TREE;
4434 /* Insert a mapping FROM->TO in the value expression hashtable. */
4436 void
4437 decl_value_expr_insert (tree from, tree to)
4439 struct tree_map *h;
4440 void **loc;
4442 h = ggc_alloc (sizeof (struct tree_map));
4443 h->hash = htab_hash_pointer (from);
4444 h->base.from = from;
4445 h->to = to;
4446 loc = htab_find_slot_with_hash (value_expr_for_decl, h, h->hash, INSERT);
4447 *(struct tree_map **) loc = h;
4450 /* Hashing of types so that we don't make duplicates.
4451 The entry point is `type_hash_canon'. */
4453 /* Compute a hash code for a list of types (chain of TREE_LIST nodes
4454 with types in the TREE_VALUE slots), by adding the hash codes
4455 of the individual types. */
4457 unsigned int
4458 type_hash_list (tree list, hashval_t hashcode)
4460 tree tail;
4462 for (tail = list; tail; tail = TREE_CHAIN (tail))
4463 if (TREE_VALUE (tail) != error_mark_node)
4464 hashcode = iterative_hash_object (TYPE_HASH (TREE_VALUE (tail)),
4465 hashcode);
4467 return hashcode;
4470 /* These are the Hashtable callback functions. */
4472 /* Returns true iff the types are equivalent. */
4474 static int
4475 type_hash_eq (const void *va, const void *vb)
4477 const struct type_hash *a = va, *b = vb;
4479 /* First test the things that are the same for all types. */
4480 if (a->hash != b->hash
4481 || TREE_CODE (a->type) != TREE_CODE (b->type)
4482 || TREE_TYPE (a->type) != TREE_TYPE (b->type)
4483 || !attribute_list_equal (TYPE_ATTRIBUTES (a->type),
4484 TYPE_ATTRIBUTES (b->type))
4485 || TYPE_ALIGN (a->type) != TYPE_ALIGN (b->type)
4486 || TYPE_MODE (a->type) != TYPE_MODE (b->type))
4487 return 0;
4489 switch (TREE_CODE (a->type))
4491 case VOID_TYPE:
4492 case COMPLEX_TYPE:
4493 case POINTER_TYPE:
4494 case REFERENCE_TYPE:
4495 return 1;
4497 case VECTOR_TYPE:
4498 return TYPE_VECTOR_SUBPARTS (a->type) == TYPE_VECTOR_SUBPARTS (b->type);
4500 case ENUMERAL_TYPE:
4501 if (TYPE_VALUES (a->type) != TYPE_VALUES (b->type)
4502 && !(TYPE_VALUES (a->type)
4503 && TREE_CODE (TYPE_VALUES (a->type)) == TREE_LIST
4504 && TYPE_VALUES (b->type)
4505 && TREE_CODE (TYPE_VALUES (b->type)) == TREE_LIST
4506 && type_list_equal (TYPE_VALUES (a->type),
4507 TYPE_VALUES (b->type))))
4508 return 0;
4510 /* ... fall through ... */
4512 case INTEGER_TYPE:
4513 case REAL_TYPE:
4514 case BOOLEAN_TYPE:
4515 return ((TYPE_MAX_VALUE (a->type) == TYPE_MAX_VALUE (b->type)
4516 || tree_int_cst_equal (TYPE_MAX_VALUE (a->type),
4517 TYPE_MAX_VALUE (b->type)))
4518 && (TYPE_MIN_VALUE (a->type) == TYPE_MIN_VALUE (b->type)
4519 || tree_int_cst_equal (TYPE_MIN_VALUE (a->type),
4520 TYPE_MIN_VALUE (b->type))));
4522 case OFFSET_TYPE:
4523 return TYPE_OFFSET_BASETYPE (a->type) == TYPE_OFFSET_BASETYPE (b->type);
4525 case METHOD_TYPE:
4526 return (TYPE_METHOD_BASETYPE (a->type) == TYPE_METHOD_BASETYPE (b->type)
4527 && (TYPE_ARG_TYPES (a->type) == TYPE_ARG_TYPES (b->type)
4528 || (TYPE_ARG_TYPES (a->type)
4529 && TREE_CODE (TYPE_ARG_TYPES (a->type)) == TREE_LIST
4530 && TYPE_ARG_TYPES (b->type)
4531 && TREE_CODE (TYPE_ARG_TYPES (b->type)) == TREE_LIST
4532 && type_list_equal (TYPE_ARG_TYPES (a->type),
4533 TYPE_ARG_TYPES (b->type)))));
4535 case ARRAY_TYPE:
4536 return TYPE_DOMAIN (a->type) == TYPE_DOMAIN (b->type);
4538 case RECORD_TYPE:
4539 case UNION_TYPE:
4540 case QUAL_UNION_TYPE:
4541 return (TYPE_FIELDS (a->type) == TYPE_FIELDS (b->type)
4542 || (TYPE_FIELDS (a->type)
4543 && TREE_CODE (TYPE_FIELDS (a->type)) == TREE_LIST
4544 && TYPE_FIELDS (b->type)
4545 && TREE_CODE (TYPE_FIELDS (b->type)) == TREE_LIST
4546 && type_list_equal (TYPE_FIELDS (a->type),
4547 TYPE_FIELDS (b->type))));
4549 case FUNCTION_TYPE:
4550 return (TYPE_ARG_TYPES (a->type) == TYPE_ARG_TYPES (b->type)
4551 || (TYPE_ARG_TYPES (a->type)
4552 && TREE_CODE (TYPE_ARG_TYPES (a->type)) == TREE_LIST
4553 && TYPE_ARG_TYPES (b->type)
4554 && TREE_CODE (TYPE_ARG_TYPES (b->type)) == TREE_LIST
4555 && type_list_equal (TYPE_ARG_TYPES (a->type),
4556 TYPE_ARG_TYPES (b->type))));
4558 default:
4559 return 0;
4563 /* Return the cached hash value. */
4565 static hashval_t
4566 type_hash_hash (const void *item)
4568 return ((const struct type_hash *) item)->hash;
4571 /* Look in the type hash table for a type isomorphic to TYPE.
4572 If one is found, return it. Otherwise return 0. */
4574 tree
4575 type_hash_lookup (hashval_t hashcode, tree type)
4577 struct type_hash *h, in;
4579 /* The TYPE_ALIGN field of a type is set by layout_type(), so we
4580 must call that routine before comparing TYPE_ALIGNs. */
4581 layout_type (type);
4583 in.hash = hashcode;
4584 in.type = type;
4586 h = htab_find_with_hash (type_hash_table, &in, hashcode);
4587 if (h)
4588 return h->type;
4589 return NULL_TREE;
4592 /* Add an entry to the type-hash-table
4593 for a type TYPE whose hash code is HASHCODE. */
4595 void
4596 type_hash_add (hashval_t hashcode, tree type)
4598 struct type_hash *h;
4599 void **loc;
4601 h = ggc_alloc (sizeof (struct type_hash));
4602 h->hash = hashcode;
4603 h->type = type;
4604 loc = htab_find_slot_with_hash (type_hash_table, h, hashcode, INSERT);
4605 *(struct type_hash **) loc = h;
4608 /* Given TYPE, and HASHCODE its hash code, return the canonical
4609 object for an identical type if one already exists.
4610 Otherwise, return TYPE, and record it as the canonical object.
4612 To use this function, first create a type of the sort you want.
4613 Then compute its hash code from the fields of the type that
4614 make it different from other similar types.
4615 Then call this function and use the value. */
4617 tree
4618 type_hash_canon (unsigned int hashcode, tree type)
4620 tree t1;
4622 /* The hash table only contains main variants, so ensure that's what we're
4623 being passed. */
4624 gcc_assert (TYPE_MAIN_VARIANT (type) == type);
4626 if (!lang_hooks.types.hash_types)
4627 return type;
4629 /* See if the type is in the hash table already. If so, return it.
4630 Otherwise, add the type. */
4631 t1 = type_hash_lookup (hashcode, type);
4632 if (t1 != 0)
4634 #ifdef GATHER_STATISTICS
4635 tree_node_counts[(int) t_kind]--;
4636 tree_node_sizes[(int) t_kind] -= sizeof (struct tree_type);
4637 #endif
4638 return t1;
4640 else
4642 type_hash_add (hashcode, type);
4643 return type;
4647 /* See if the data pointed to by the type hash table is marked. We consider
4648 it marked if the type is marked or if a debug type number or symbol
4649 table entry has been made for the type. This reduces the amount of
4650 debugging output and eliminates that dependency of the debug output on
4651 the number of garbage collections. */
4653 static int
4654 type_hash_marked_p (const void *p)
4656 tree type = ((struct type_hash *) p)->type;
4658 return ggc_marked_p (type) || TYPE_SYMTAB_POINTER (type);
4661 static void
4662 print_type_hash_statistics (void)
4664 fprintf (stderr, "Type hash: size %ld, %ld elements, %f collisions\n",
4665 (long) htab_size (type_hash_table),
4666 (long) htab_elements (type_hash_table),
4667 htab_collisions (type_hash_table));
4670 /* Compute a hash code for a list of attributes (chain of TREE_LIST nodes
4671 with names in the TREE_PURPOSE slots and args in the TREE_VALUE slots),
4672 by adding the hash codes of the individual attributes. */
4674 unsigned int
4675 attribute_hash_list (tree list, hashval_t hashcode)
4677 tree tail;
4679 for (tail = list; tail; tail = TREE_CHAIN (tail))
4680 /* ??? Do we want to add in TREE_VALUE too? */
4681 hashcode = iterative_hash_object
4682 (IDENTIFIER_HASH_VALUE (TREE_PURPOSE (tail)), hashcode);
4683 return hashcode;
4686 /* Given two lists of attributes, return true if list l2 is
4687 equivalent to l1. */
4690 attribute_list_equal (tree l1, tree l2)
4692 return attribute_list_contained (l1, l2)
4693 && attribute_list_contained (l2, l1);
4696 /* Given two lists of attributes, return true if list L2 is
4697 completely contained within L1. */
4698 /* ??? This would be faster if attribute names were stored in a canonicalized
4699 form. Otherwise, if L1 uses `foo' and L2 uses `__foo__', the long method
4700 must be used to show these elements are equivalent (which they are). */
4701 /* ??? It's not clear that attributes with arguments will always be handled
4702 correctly. */
4705 attribute_list_contained (tree l1, tree l2)
4707 tree t1, t2;
4709 /* First check the obvious, maybe the lists are identical. */
4710 if (l1 == l2)
4711 return 1;
4713 /* Maybe the lists are similar. */
4714 for (t1 = l1, t2 = l2;
4715 t1 != 0 && t2 != 0
4716 && TREE_PURPOSE (t1) == TREE_PURPOSE (t2)
4717 && TREE_VALUE (t1) == TREE_VALUE (t2);
4718 t1 = TREE_CHAIN (t1), t2 = TREE_CHAIN (t2));
4720 /* Maybe the lists are equal. */
4721 if (t1 == 0 && t2 == 0)
4722 return 1;
4724 for (; t2 != 0; t2 = TREE_CHAIN (t2))
4726 tree attr;
4727 for (attr = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (t2)), l1);
4728 attr != NULL_TREE;
4729 attr = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (t2)),
4730 TREE_CHAIN (attr)))
4732 if (TREE_VALUE (t2) != NULL
4733 && TREE_CODE (TREE_VALUE (t2)) == TREE_LIST
4734 && TREE_VALUE (attr) != NULL
4735 && TREE_CODE (TREE_VALUE (attr)) == TREE_LIST)
4737 if (simple_cst_list_equal (TREE_VALUE (t2),
4738 TREE_VALUE (attr)) == 1)
4739 break;
4741 else if (simple_cst_equal (TREE_VALUE (t2), TREE_VALUE (attr)) == 1)
4742 break;
4745 if (attr == 0)
4746 return 0;
4749 return 1;
4752 /* Given two lists of types
4753 (chains of TREE_LIST nodes with types in the TREE_VALUE slots)
4754 return 1 if the lists contain the same types in the same order.
4755 Also, the TREE_PURPOSEs must match. */
4758 type_list_equal (tree l1, tree l2)
4760 tree t1, t2;
4762 for (t1 = l1, t2 = l2; t1 && t2; t1 = TREE_CHAIN (t1), t2 = TREE_CHAIN (t2))
4763 if (TREE_VALUE (t1) != TREE_VALUE (t2)
4764 || (TREE_PURPOSE (t1) != TREE_PURPOSE (t2)
4765 && ! (1 == simple_cst_equal (TREE_PURPOSE (t1), TREE_PURPOSE (t2))
4766 && (TREE_TYPE (TREE_PURPOSE (t1))
4767 == TREE_TYPE (TREE_PURPOSE (t2))))))
4768 return 0;
4770 return t1 == t2;
4773 /* Returns the number of arguments to the FUNCTION_TYPE or METHOD_TYPE
4774 given by TYPE. If the argument list accepts variable arguments,
4775 then this function counts only the ordinary arguments. */
4778 type_num_arguments (tree type)
4780 int i = 0;
4781 tree t;
4783 for (t = TYPE_ARG_TYPES (type); t; t = TREE_CHAIN (t))
4784 /* If the function does not take a variable number of arguments,
4785 the last element in the list will have type `void'. */
4786 if (VOID_TYPE_P (TREE_VALUE (t)))
4787 break;
4788 else
4789 ++i;
4791 return i;
4794 /* Nonzero if integer constants T1 and T2
4795 represent the same constant value. */
4798 tree_int_cst_equal (tree t1, tree t2)
4800 if (t1 == t2)
4801 return 1;
4803 if (t1 == 0 || t2 == 0)
4804 return 0;
4806 if (TREE_CODE (t1) == INTEGER_CST
4807 && TREE_CODE (t2) == INTEGER_CST
4808 && TREE_INT_CST_LOW (t1) == TREE_INT_CST_LOW (t2)
4809 && TREE_INT_CST_HIGH (t1) == TREE_INT_CST_HIGH (t2))
4810 return 1;
4812 return 0;
4815 /* Nonzero if integer constants T1 and T2 represent values that satisfy <.
4816 The precise way of comparison depends on their data type. */
4819 tree_int_cst_lt (tree t1, tree t2)
4821 if (t1 == t2)
4822 return 0;
4824 if (TYPE_UNSIGNED (TREE_TYPE (t1)) != TYPE_UNSIGNED (TREE_TYPE (t2)))
4826 int t1_sgn = tree_int_cst_sgn (t1);
4827 int t2_sgn = tree_int_cst_sgn (t2);
4829 if (t1_sgn < t2_sgn)
4830 return 1;
4831 else if (t1_sgn > t2_sgn)
4832 return 0;
4833 /* Otherwise, both are non-negative, so we compare them as
4834 unsigned just in case one of them would overflow a signed
4835 type. */
4837 else if (!TYPE_UNSIGNED (TREE_TYPE (t1)))
4838 return INT_CST_LT (t1, t2);
4840 return INT_CST_LT_UNSIGNED (t1, t2);
4843 /* Returns -1 if T1 < T2, 0 if T1 == T2, and 1 if T1 > T2. */
4846 tree_int_cst_compare (tree t1, tree t2)
4848 if (tree_int_cst_lt (t1, t2))
4849 return -1;
4850 else if (tree_int_cst_lt (t2, t1))
4851 return 1;
4852 else
4853 return 0;
4856 /* Return 1 if T is an INTEGER_CST that can be manipulated efficiently on
4857 the host. If POS is zero, the value can be represented in a single
4858 HOST_WIDE_INT. If POS is nonzero, the value must be non-negative and can
4859 be represented in a single unsigned HOST_WIDE_INT. */
4862 host_integerp (tree t, int pos)
4864 return (TREE_CODE (t) == INTEGER_CST
4865 && ((TREE_INT_CST_HIGH (t) == 0
4866 && (HOST_WIDE_INT) TREE_INT_CST_LOW (t) >= 0)
4867 || (! pos && TREE_INT_CST_HIGH (t) == -1
4868 && (HOST_WIDE_INT) TREE_INT_CST_LOW (t) < 0
4869 && !TYPE_UNSIGNED (TREE_TYPE (t)))
4870 || (pos && TREE_INT_CST_HIGH (t) == 0)));
4873 /* Return the HOST_WIDE_INT least significant bits of T if it is an
4874 INTEGER_CST and there is no overflow. POS is nonzero if the result must
4875 be non-negative. We must be able to satisfy the above conditions. */
4877 HOST_WIDE_INT
4878 tree_low_cst (tree t, int pos)
4880 gcc_assert (host_integerp (t, pos));
4881 return TREE_INT_CST_LOW (t);
4884 /* Return the most significant bit of the integer constant T. */
4887 tree_int_cst_msb (tree t)
4889 int prec;
4890 HOST_WIDE_INT h;
4891 unsigned HOST_WIDE_INT l;
4893 /* Note that using TYPE_PRECISION here is wrong. We care about the
4894 actual bits, not the (arbitrary) range of the type. */
4895 prec = GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (t))) - 1;
4896 rshift_double (TREE_INT_CST_LOW (t), TREE_INT_CST_HIGH (t), prec,
4897 2 * HOST_BITS_PER_WIDE_INT, &l, &h, 0);
4898 return (l & 1) == 1;
4901 /* Return an indication of the sign of the integer constant T.
4902 The return value is -1 if T < 0, 0 if T == 0, and 1 if T > 0.
4903 Note that -1 will never be returned if T's type is unsigned. */
4906 tree_int_cst_sgn (tree t)
4908 if (TREE_INT_CST_LOW (t) == 0 && TREE_INT_CST_HIGH (t) == 0)
4909 return 0;
4910 else if (TYPE_UNSIGNED (TREE_TYPE (t)))
4911 return 1;
4912 else if (TREE_INT_CST_HIGH (t) < 0)
4913 return -1;
4914 else
4915 return 1;
4918 /* Compare two constructor-element-type constants. Return 1 if the lists
4919 are known to be equal; otherwise return 0. */
4922 simple_cst_list_equal (tree l1, tree l2)
4924 while (l1 != NULL_TREE && l2 != NULL_TREE)
4926 if (simple_cst_equal (TREE_VALUE (l1), TREE_VALUE (l2)) != 1)
4927 return 0;
4929 l1 = TREE_CHAIN (l1);
4930 l2 = TREE_CHAIN (l2);
4933 return l1 == l2;
4936 /* Return truthvalue of whether T1 is the same tree structure as T2.
4937 Return 1 if they are the same.
4938 Return 0 if they are understandably different.
4939 Return -1 if either contains tree structure not understood by
4940 this function. */
4943 simple_cst_equal (tree t1, tree t2)
4945 enum tree_code code1, code2;
4946 int cmp;
4947 int i;
4949 if (t1 == t2)
4950 return 1;
4951 if (t1 == 0 || t2 == 0)
4952 return 0;
4954 code1 = TREE_CODE (t1);
4955 code2 = TREE_CODE (t2);
4957 if (code1 == NOP_EXPR || code1 == CONVERT_EXPR || code1 == NON_LVALUE_EXPR)
4959 if (code2 == NOP_EXPR || code2 == CONVERT_EXPR
4960 || code2 == NON_LVALUE_EXPR)
4961 return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
4962 else
4963 return simple_cst_equal (TREE_OPERAND (t1, 0), t2);
4966 else if (code2 == NOP_EXPR || code2 == CONVERT_EXPR
4967 || code2 == NON_LVALUE_EXPR)
4968 return simple_cst_equal (t1, TREE_OPERAND (t2, 0));
4970 if (code1 != code2)
4971 return 0;
4973 switch (code1)
4975 case INTEGER_CST:
4976 return (TREE_INT_CST_LOW (t1) == TREE_INT_CST_LOW (t2)
4977 && TREE_INT_CST_HIGH (t1) == TREE_INT_CST_HIGH (t2));
4979 case REAL_CST:
4980 return REAL_VALUES_IDENTICAL (TREE_REAL_CST (t1), TREE_REAL_CST (t2));
4982 case STRING_CST:
4983 return (TREE_STRING_LENGTH (t1) == TREE_STRING_LENGTH (t2)
4984 && ! memcmp (TREE_STRING_POINTER (t1), TREE_STRING_POINTER (t2),
4985 TREE_STRING_LENGTH (t1)));
4987 case CONSTRUCTOR:
4989 unsigned HOST_WIDE_INT idx;
4990 VEC(constructor_elt, gc) *v1 = CONSTRUCTOR_ELTS (t1);
4991 VEC(constructor_elt, gc) *v2 = CONSTRUCTOR_ELTS (t2);
4993 if (VEC_length (constructor_elt, v1) != VEC_length (constructor_elt, v2))
4994 return false;
4996 for (idx = 0; idx < VEC_length (constructor_elt, v1); ++idx)
4997 /* ??? Should we handle also fields here? */
4998 if (!simple_cst_equal (VEC_index (constructor_elt, v1, idx)->value,
4999 VEC_index (constructor_elt, v2, idx)->value))
5000 return false;
5001 return true;
5004 case SAVE_EXPR:
5005 return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
5007 case CALL_EXPR:
5008 cmp = simple_cst_equal (CALL_EXPR_FN (t1), CALL_EXPR_FN (t2));
5009 if (cmp <= 0)
5010 return cmp;
5011 if (call_expr_nargs (t1) != call_expr_nargs (t2))
5012 return 0;
5014 tree arg1, arg2;
5015 call_expr_arg_iterator iter1, iter2;
5016 for (arg1 = first_call_expr_arg (t1, &iter1),
5017 arg2 = first_call_expr_arg (t2, &iter2);
5018 arg1 && arg2;
5019 arg1 = next_call_expr_arg (&iter1),
5020 arg2 = next_call_expr_arg (&iter2))
5022 cmp = simple_cst_equal (arg1, arg2);
5023 if (cmp <= 0)
5024 return cmp;
5026 return arg1 == arg2;
5029 case TARGET_EXPR:
5030 /* Special case: if either target is an unallocated VAR_DECL,
5031 it means that it's going to be unified with whatever the
5032 TARGET_EXPR is really supposed to initialize, so treat it
5033 as being equivalent to anything. */
5034 if ((TREE_CODE (TREE_OPERAND (t1, 0)) == VAR_DECL
5035 && DECL_NAME (TREE_OPERAND (t1, 0)) == NULL_TREE
5036 && !DECL_RTL_SET_P (TREE_OPERAND (t1, 0)))
5037 || (TREE_CODE (TREE_OPERAND (t2, 0)) == VAR_DECL
5038 && DECL_NAME (TREE_OPERAND (t2, 0)) == NULL_TREE
5039 && !DECL_RTL_SET_P (TREE_OPERAND (t2, 0))))
5040 cmp = 1;
5041 else
5042 cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
5044 if (cmp <= 0)
5045 return cmp;
5047 return simple_cst_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
5049 case WITH_CLEANUP_EXPR:
5050 cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
5051 if (cmp <= 0)
5052 return cmp;
5054 return simple_cst_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t1, 1));
5056 case COMPONENT_REF:
5057 if (TREE_OPERAND (t1, 1) == TREE_OPERAND (t2, 1))
5058 return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
5060 return 0;
5062 case VAR_DECL:
5063 case PARM_DECL:
5064 case CONST_DECL:
5065 case FUNCTION_DECL:
5066 return 0;
5068 default:
5069 break;
5072 /* This general rule works for most tree codes. All exceptions should be
5073 handled above. If this is a language-specific tree code, we can't
5074 trust what might be in the operand, so say we don't know
5075 the situation. */
5076 if ((int) code1 >= (int) LAST_AND_UNUSED_TREE_CODE)
5077 return -1;
5079 switch (TREE_CODE_CLASS (code1))
5081 case tcc_unary:
5082 case tcc_binary:
5083 case tcc_comparison:
5084 case tcc_expression:
5085 case tcc_reference:
5086 case tcc_statement:
5087 cmp = 1;
5088 for (i = 0; i < TREE_CODE_LENGTH (code1); i++)
5090 cmp = simple_cst_equal (TREE_OPERAND (t1, i), TREE_OPERAND (t2, i));
5091 if (cmp <= 0)
5092 return cmp;
5095 return cmp;
5097 default:
5098 return -1;
5102 /* Compare the value of T, an INTEGER_CST, with U, an unsigned integer value.
5103 Return -1, 0, or 1 if the value of T is less than, equal to, or greater
5104 than U, respectively. */
5107 compare_tree_int (tree t, unsigned HOST_WIDE_INT u)
5109 if (tree_int_cst_sgn (t) < 0)
5110 return -1;
5111 else if (TREE_INT_CST_HIGH (t) != 0)
5112 return 1;
5113 else if (TREE_INT_CST_LOW (t) == u)
5114 return 0;
5115 else if (TREE_INT_CST_LOW (t) < u)
5116 return -1;
5117 else
5118 return 1;
5121 /* Return true if CODE represents an associative tree code. Otherwise
5122 return false. */
5123 bool
5124 associative_tree_code (enum tree_code code)
5126 switch (code)
5128 case BIT_IOR_EXPR:
5129 case BIT_AND_EXPR:
5130 case BIT_XOR_EXPR:
5131 case PLUS_EXPR:
5132 case MULT_EXPR:
5133 case MIN_EXPR:
5134 case MAX_EXPR:
5135 return true;
5137 default:
5138 break;
5140 return false;
5143 /* Return true if CODE represents a commutative tree code. Otherwise
5144 return false. */
5145 bool
5146 commutative_tree_code (enum tree_code code)
5148 switch (code)
5150 case PLUS_EXPR:
5151 case MULT_EXPR:
5152 case MIN_EXPR:
5153 case MAX_EXPR:
5154 case BIT_IOR_EXPR:
5155 case BIT_XOR_EXPR:
5156 case BIT_AND_EXPR:
5157 case NE_EXPR:
5158 case EQ_EXPR:
5159 case UNORDERED_EXPR:
5160 case ORDERED_EXPR:
5161 case UNEQ_EXPR:
5162 case LTGT_EXPR:
5163 case TRUTH_AND_EXPR:
5164 case TRUTH_XOR_EXPR:
5165 case TRUTH_OR_EXPR:
5166 return true;
5168 default:
5169 break;
5171 return false;
5174 /* Generate a hash value for an expression. This can be used iteratively
5175 by passing a previous result as the "val" argument.
5177 This function is intended to produce the same hash for expressions which
5178 would compare equal using operand_equal_p. */
5180 hashval_t
5181 iterative_hash_expr (tree t, hashval_t val)
5183 int i;
5184 enum tree_code code;
5185 char class;
5187 if (t == NULL_TREE)
5188 return iterative_hash_pointer (t, val);
5190 code = TREE_CODE (t);
5192 switch (code)
5194 /* Alas, constants aren't shared, so we can't rely on pointer
5195 identity. */
5196 case INTEGER_CST:
5197 val = iterative_hash_host_wide_int (TREE_INT_CST_LOW (t), val);
5198 return iterative_hash_host_wide_int (TREE_INT_CST_HIGH (t), val);
5199 case REAL_CST:
5201 unsigned int val2 = real_hash (TREE_REAL_CST_PTR (t));
5203 return iterative_hash_hashval_t (val2, val);
5205 case STRING_CST:
5206 return iterative_hash (TREE_STRING_POINTER (t),
5207 TREE_STRING_LENGTH (t), val);
5208 case COMPLEX_CST:
5209 val = iterative_hash_expr (TREE_REALPART (t), val);
5210 return iterative_hash_expr (TREE_IMAGPART (t), val);
5211 case VECTOR_CST:
5212 return iterative_hash_expr (TREE_VECTOR_CST_ELTS (t), val);
5214 case SSA_NAME:
5215 case VALUE_HANDLE:
5216 /* we can just compare by pointer. */
5217 return iterative_hash_pointer (t, val);
5219 case TREE_LIST:
5220 /* A list of expressions, for a CALL_EXPR or as the elements of a
5221 VECTOR_CST. */
5222 for (; t; t = TREE_CHAIN (t))
5223 val = iterative_hash_expr (TREE_VALUE (t), val);
5224 return val;
5225 case CONSTRUCTOR:
5227 unsigned HOST_WIDE_INT idx;
5228 tree field, value;
5229 FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (t), idx, field, value)
5231 val = iterative_hash_expr (field, val);
5232 val = iterative_hash_expr (value, val);
5234 return val;
5236 case FUNCTION_DECL:
5237 /* When referring to a built-in FUNCTION_DECL, use the
5238 __builtin__ form. Otherwise nodes that compare equal
5239 according to operand_equal_p might get different
5240 hash codes. */
5241 if (DECL_BUILT_IN (t))
5243 val = iterative_hash_pointer (built_in_decls[DECL_FUNCTION_CODE (t)],
5244 val);
5245 return val;
5247 /* else FALL THROUGH */
5248 default:
5249 class = TREE_CODE_CLASS (code);
5251 if (class == tcc_declaration)
5253 /* DECL's have a unique ID */
5254 val = iterative_hash_host_wide_int (DECL_UID (t), val);
5256 else
5258 gcc_assert (IS_EXPR_CODE_CLASS (class));
5260 val = iterative_hash_object (code, val);
5262 /* Don't hash the type, that can lead to having nodes which
5263 compare equal according to operand_equal_p, but which
5264 have different hash codes. */
5265 if (code == NOP_EXPR
5266 || code == CONVERT_EXPR
5267 || code == NON_LVALUE_EXPR)
5269 /* Make sure to include signness in the hash computation. */
5270 val += TYPE_UNSIGNED (TREE_TYPE (t));
5271 val = iterative_hash_expr (TREE_OPERAND (t, 0), val);
5274 else if (commutative_tree_code (code))
5276 /* It's a commutative expression. We want to hash it the same
5277 however it appears. We do this by first hashing both operands
5278 and then rehashing based on the order of their independent
5279 hashes. */
5280 hashval_t one = iterative_hash_expr (TREE_OPERAND (t, 0), 0);
5281 hashval_t two = iterative_hash_expr (TREE_OPERAND (t, 1), 0);
5282 hashval_t t;
5284 if (one > two)
5285 t = one, one = two, two = t;
5287 val = iterative_hash_hashval_t (one, val);
5288 val = iterative_hash_hashval_t (two, val);
5290 else
5291 for (i = TREE_OPERAND_LENGTH (t) - 1; i >= 0; --i)
5292 val = iterative_hash_expr (TREE_OPERAND (t, i), val);
5294 return val;
5295 break;
5299 /* Constructors for pointer, array and function types.
5300 (RECORD_TYPE, UNION_TYPE and ENUMERAL_TYPE nodes are
5301 constructed by language-dependent code, not here.) */
5303 /* Construct, lay out and return the type of pointers to TO_TYPE with
5304 mode MODE. If CAN_ALIAS_ALL is TRUE, indicate this type can
5305 reference all of memory. If such a type has already been
5306 constructed, reuse it. */
5308 tree
5309 build_pointer_type_for_mode (tree to_type, enum machine_mode mode,
5310 bool can_alias_all)
5312 tree t;
5314 if (to_type == error_mark_node)
5315 return error_mark_node;
5317 /* In some cases, languages will have things that aren't a POINTER_TYPE
5318 (such as a RECORD_TYPE for fat pointers in Ada) as TYPE_POINTER_TO.
5319 In that case, return that type without regard to the rest of our
5320 operands.
5322 ??? This is a kludge, but consistent with the way this function has
5323 always operated and there doesn't seem to be a good way to avoid this
5324 at the moment. */
5325 if (TYPE_POINTER_TO (to_type) != 0
5326 && TREE_CODE (TYPE_POINTER_TO (to_type)) != POINTER_TYPE)
5327 return TYPE_POINTER_TO (to_type);
5329 /* First, if we already have a type for pointers to TO_TYPE and it's
5330 the proper mode, use it. */
5331 for (t = TYPE_POINTER_TO (to_type); t; t = TYPE_NEXT_PTR_TO (t))
5332 if (TYPE_MODE (t) == mode && TYPE_REF_CAN_ALIAS_ALL (t) == can_alias_all)
5333 return t;
5335 t = make_node (POINTER_TYPE);
5337 TREE_TYPE (t) = to_type;
5338 TYPE_MODE (t) = mode;
5339 TYPE_REF_CAN_ALIAS_ALL (t) = can_alias_all;
5340 TYPE_NEXT_PTR_TO (t) = TYPE_POINTER_TO (to_type);
5341 TYPE_POINTER_TO (to_type) = t;
5343 if (TYPE_STRUCTURAL_EQUALITY_P (to_type))
5344 SET_TYPE_STRUCTURAL_EQUALITY (t);
5345 else if (TYPE_CANONICAL (to_type) != to_type)
5346 TYPE_CANONICAL (t)
5347 = build_pointer_type_for_mode (TYPE_CANONICAL (to_type),
5348 mode, can_alias_all);
5350 /* Lay out the type. This function has many callers that are concerned
5351 with expression-construction, and this simplifies them all. */
5352 layout_type (t);
5354 return t;
5357 /* By default build pointers in ptr_mode. */
5359 tree
5360 build_pointer_type (tree to_type)
5362 return build_pointer_type_for_mode (to_type, ptr_mode, false);
5365 /* Same as build_pointer_type_for_mode, but for REFERENCE_TYPE. */
5367 tree
5368 build_reference_type_for_mode (tree to_type, enum machine_mode mode,
5369 bool can_alias_all)
5371 tree t;
5373 /* In some cases, languages will have things that aren't a REFERENCE_TYPE
5374 (such as a RECORD_TYPE for fat pointers in Ada) as TYPE_REFERENCE_TO.
5375 In that case, return that type without regard to the rest of our
5376 operands.
5378 ??? This is a kludge, but consistent with the way this function has
5379 always operated and there doesn't seem to be a good way to avoid this
5380 at the moment. */
5381 if (TYPE_REFERENCE_TO (to_type) != 0
5382 && TREE_CODE (TYPE_REFERENCE_TO (to_type)) != REFERENCE_TYPE)
5383 return TYPE_REFERENCE_TO (to_type);
5385 /* First, if we already have a type for pointers to TO_TYPE and it's
5386 the proper mode, use it. */
5387 for (t = TYPE_REFERENCE_TO (to_type); t; t = TYPE_NEXT_REF_TO (t))
5388 if (TYPE_MODE (t) == mode && TYPE_REF_CAN_ALIAS_ALL (t) == can_alias_all)
5389 return t;
5391 t = make_node (REFERENCE_TYPE);
5393 TREE_TYPE (t) = to_type;
5394 TYPE_MODE (t) = mode;
5395 TYPE_REF_CAN_ALIAS_ALL (t) = can_alias_all;
5396 TYPE_NEXT_REF_TO (t) = TYPE_REFERENCE_TO (to_type);
5397 TYPE_REFERENCE_TO (to_type) = t;
5399 if (TYPE_STRUCTURAL_EQUALITY_P (to_type))
5400 SET_TYPE_STRUCTURAL_EQUALITY (t);
5401 else if (TYPE_CANONICAL (to_type) != to_type)
5402 TYPE_CANONICAL (t)
5403 = build_reference_type_for_mode (TYPE_CANONICAL (to_type),
5404 mode, can_alias_all);
5406 layout_type (t);
5408 return t;
5412 /* Build the node for the type of references-to-TO_TYPE by default
5413 in ptr_mode. */
5415 tree
5416 build_reference_type (tree to_type)
5418 return build_reference_type_for_mode (to_type, ptr_mode, false);
5421 /* Build a type that is compatible with t but has no cv quals anywhere
5422 in its type, thus
5424 const char *const *const * -> char ***. */
5426 tree
5427 build_type_no_quals (tree t)
5429 switch (TREE_CODE (t))
5431 case POINTER_TYPE:
5432 return build_pointer_type_for_mode (build_type_no_quals (TREE_TYPE (t)),
5433 TYPE_MODE (t),
5434 TYPE_REF_CAN_ALIAS_ALL (t));
5435 case REFERENCE_TYPE:
5436 return
5437 build_reference_type_for_mode (build_type_no_quals (TREE_TYPE (t)),
5438 TYPE_MODE (t),
5439 TYPE_REF_CAN_ALIAS_ALL (t));
5440 default:
5441 return TYPE_MAIN_VARIANT (t);
5445 /* Create a type of integers to be the TYPE_DOMAIN of an ARRAY_TYPE.
5446 MAXVAL should be the maximum value in the domain
5447 (one less than the length of the array).
5449 The maximum value that MAXVAL can have is INT_MAX for a HOST_WIDE_INT.
5450 We don't enforce this limit, that is up to caller (e.g. language front end).
5451 The limit exists because the result is a signed type and we don't handle
5452 sizes that use more than one HOST_WIDE_INT. */
5454 tree
5455 build_index_type (tree maxval)
5457 tree itype = make_node (INTEGER_TYPE);
5459 TREE_TYPE (itype) = sizetype;
5460 TYPE_PRECISION (itype) = TYPE_PRECISION (sizetype);
5461 TYPE_MIN_VALUE (itype) = size_zero_node;
5462 TYPE_MAX_VALUE (itype) = fold_convert (sizetype, maxval);
5463 TYPE_MODE (itype) = TYPE_MODE (sizetype);
5464 TYPE_SIZE (itype) = TYPE_SIZE (sizetype);
5465 TYPE_SIZE_UNIT (itype) = TYPE_SIZE_UNIT (sizetype);
5466 TYPE_ALIGN (itype) = TYPE_ALIGN (sizetype);
5467 TYPE_USER_ALIGN (itype) = TYPE_USER_ALIGN (sizetype);
5469 if (host_integerp (maxval, 1))
5470 return type_hash_canon (tree_low_cst (maxval, 1), itype);
5471 else
5473 /* Since we cannot hash this type, we need to compare it using
5474 structural equality checks. */
5475 SET_TYPE_STRUCTURAL_EQUALITY (itype);
5476 return itype;
5480 /* Builds a signed or unsigned integer type of precision PRECISION.
5481 Used for C bitfields whose precision does not match that of
5482 built-in target types. */
5483 tree
5484 build_nonstandard_integer_type (unsigned HOST_WIDE_INT precision,
5485 int unsignedp)
5487 tree itype = make_node (INTEGER_TYPE);
5489 TYPE_PRECISION (itype) = precision;
5491 if (unsignedp)
5492 fixup_unsigned_type (itype);
5493 else
5494 fixup_signed_type (itype);
5496 if (host_integerp (TYPE_MAX_VALUE (itype), 1))
5497 return type_hash_canon (tree_low_cst (TYPE_MAX_VALUE (itype), 1), itype);
5499 return itype;
5502 /* Create a range of some discrete type TYPE (an INTEGER_TYPE,
5503 ENUMERAL_TYPE or BOOLEAN_TYPE), with low bound LOWVAL and
5504 high bound HIGHVAL. If TYPE is NULL, sizetype is used. */
5506 tree
5507 build_range_type (tree type, tree lowval, tree highval)
5509 tree itype = make_node (INTEGER_TYPE);
5511 TREE_TYPE (itype) = type;
5512 if (type == NULL_TREE)
5513 type = sizetype;
5515 TYPE_MIN_VALUE (itype) = fold_convert (type, lowval);
5516 TYPE_MAX_VALUE (itype) = highval ? fold_convert (type, highval) : NULL;
5518 TYPE_PRECISION (itype) = TYPE_PRECISION (type);
5519 TYPE_MODE (itype) = TYPE_MODE (type);
5520 TYPE_SIZE (itype) = TYPE_SIZE (type);
5521 TYPE_SIZE_UNIT (itype) = TYPE_SIZE_UNIT (type);
5522 TYPE_ALIGN (itype) = TYPE_ALIGN (type);
5523 TYPE_USER_ALIGN (itype) = TYPE_USER_ALIGN (type);
5525 if (host_integerp (lowval, 0) && highval != 0 && host_integerp (highval, 0))
5526 return type_hash_canon (tree_low_cst (highval, 0)
5527 - tree_low_cst (lowval, 0),
5528 itype);
5529 else
5530 return itype;
5533 /* Just like build_index_type, but takes lowval and highval instead
5534 of just highval (maxval). */
5536 tree
5537 build_index_2_type (tree lowval, tree highval)
5539 return build_range_type (sizetype, lowval, highval);
5542 /* Construct, lay out and return the type of arrays of elements with ELT_TYPE
5543 and number of elements specified by the range of values of INDEX_TYPE.
5544 If such a type has already been constructed, reuse it. */
5546 tree
5547 build_array_type (tree elt_type, tree index_type)
5549 tree t;
5550 hashval_t hashcode = 0;
5552 if (TREE_CODE (elt_type) == FUNCTION_TYPE)
5554 error ("arrays of functions are not meaningful");
5555 elt_type = integer_type_node;
5558 t = make_node (ARRAY_TYPE);
5559 TREE_TYPE (t) = elt_type;
5560 TYPE_DOMAIN (t) = index_type;
5562 if (index_type == 0)
5564 tree save = t;
5565 hashcode = iterative_hash_object (TYPE_HASH (elt_type), hashcode);
5566 t = type_hash_canon (hashcode, t);
5567 if (save == t)
5568 layout_type (t);
5570 if (TYPE_CANONICAL (t) == t)
5572 if (TYPE_STRUCTURAL_EQUALITY_P (elt_type))
5573 SET_TYPE_STRUCTURAL_EQUALITY (t);
5574 else if (TYPE_CANONICAL (elt_type) != elt_type)
5575 TYPE_CANONICAL (t)
5576 = build_array_type (TYPE_CANONICAL (elt_type), index_type);
5579 return t;
5582 hashcode = iterative_hash_object (TYPE_HASH (elt_type), hashcode);
5583 hashcode = iterative_hash_object (TYPE_HASH (index_type), hashcode);
5584 t = type_hash_canon (hashcode, t);
5586 if (!COMPLETE_TYPE_P (t))
5587 layout_type (t);
5589 if (TYPE_CANONICAL (t) == t)
5591 if (TYPE_STRUCTURAL_EQUALITY_P (elt_type)
5592 || TYPE_STRUCTURAL_EQUALITY_P (index_type))
5593 SET_TYPE_STRUCTURAL_EQUALITY (t);
5594 else if (TYPE_CANONICAL (elt_type) != elt_type
5595 || TYPE_CANONICAL (index_type) != index_type)
5596 TYPE_CANONICAL (t)
5597 = build_array_type (TYPE_CANONICAL (elt_type),
5598 TYPE_CANONICAL (index_type));
5601 return t;
5604 /* Return the TYPE of the elements comprising
5605 the innermost dimension of ARRAY. */
5607 tree
5608 get_inner_array_type (tree array)
5610 tree type = TREE_TYPE (array);
5612 while (TREE_CODE (type) == ARRAY_TYPE)
5613 type = TREE_TYPE (type);
5615 return type;
5618 /* Construct, lay out and return
5619 the type of functions returning type VALUE_TYPE
5620 given arguments of types ARG_TYPES.
5621 ARG_TYPES is a chain of TREE_LIST nodes whose TREE_VALUEs
5622 are data type nodes for the arguments of the function.
5623 If such a type has already been constructed, reuse it. */
5625 tree
5626 build_function_type (tree value_type, tree arg_types)
5628 tree t;
5629 hashval_t hashcode = 0;
5631 if (TREE_CODE (value_type) == FUNCTION_TYPE)
5633 error ("function return type cannot be function");
5634 value_type = integer_type_node;
5637 /* Make a node of the sort we want. */
5638 t = make_node (FUNCTION_TYPE);
5639 TREE_TYPE (t) = value_type;
5640 TYPE_ARG_TYPES (t) = arg_types;
5642 /* We don't have canonicalization of function types, yet. */
5643 SET_TYPE_STRUCTURAL_EQUALITY (t);
5645 /* If we already have such a type, use the old one. */
5646 hashcode = iterative_hash_object (TYPE_HASH (value_type), hashcode);
5647 hashcode = type_hash_list (arg_types, hashcode);
5648 t = type_hash_canon (hashcode, t);
5650 if (!COMPLETE_TYPE_P (t))
5651 layout_type (t);
5652 return t;
5655 /* Build a function type. The RETURN_TYPE is the type returned by the
5656 function. If additional arguments are provided, they are
5657 additional argument types. The list of argument types must always
5658 be terminated by NULL_TREE. */
5660 tree
5661 build_function_type_list (tree return_type, ...)
5663 tree t, args, last;
5664 va_list p;
5666 va_start (p, return_type);
5668 t = va_arg (p, tree);
5669 for (args = NULL_TREE; t != NULL_TREE; t = va_arg (p, tree))
5670 args = tree_cons (NULL_TREE, t, args);
5672 if (args == NULL_TREE)
5673 args = void_list_node;
5674 else
5676 last = args;
5677 args = nreverse (args);
5678 TREE_CHAIN (last) = void_list_node;
5680 args = build_function_type (return_type, args);
5682 va_end (p);
5683 return args;
5686 /* Build a METHOD_TYPE for a member of BASETYPE. The RETTYPE (a TYPE)
5687 and ARGTYPES (a TREE_LIST) are the return type and arguments types
5688 for the method. An implicit additional parameter (of type
5689 pointer-to-BASETYPE) is added to the ARGTYPES. */
5691 tree
5692 build_method_type_directly (tree basetype,
5693 tree rettype,
5694 tree argtypes)
5696 tree t;
5697 tree ptype;
5698 int hashcode = 0;
5700 /* Make a node of the sort we want. */
5701 t = make_node (METHOD_TYPE);
5703 TYPE_METHOD_BASETYPE (t) = TYPE_MAIN_VARIANT (basetype);
5704 TREE_TYPE (t) = rettype;
5705 ptype = build_pointer_type (basetype);
5707 /* The actual arglist for this function includes a "hidden" argument
5708 which is "this". Put it into the list of argument types. */
5709 argtypes = tree_cons (NULL_TREE, ptype, argtypes);
5710 TYPE_ARG_TYPES (t) = argtypes;
5712 /* We don't have canonicalization of method types yet. */
5713 SET_TYPE_STRUCTURAL_EQUALITY (t);
5715 /* If we already have such a type, use the old one. */
5716 hashcode = iterative_hash_object (TYPE_HASH (basetype), hashcode);
5717 hashcode = iterative_hash_object (TYPE_HASH (rettype), hashcode);
5718 hashcode = type_hash_list (argtypes, hashcode);
5719 t = type_hash_canon (hashcode, t);
5721 if (!COMPLETE_TYPE_P (t))
5722 layout_type (t);
5724 return t;
5727 /* Construct, lay out and return the type of methods belonging to class
5728 BASETYPE and whose arguments and values are described by TYPE.
5729 If that type exists already, reuse it.
5730 TYPE must be a FUNCTION_TYPE node. */
5732 tree
5733 build_method_type (tree basetype, tree type)
5735 gcc_assert (TREE_CODE (type) == FUNCTION_TYPE);
5737 return build_method_type_directly (basetype,
5738 TREE_TYPE (type),
5739 TYPE_ARG_TYPES (type));
5742 /* Construct, lay out and return the type of offsets to a value
5743 of type TYPE, within an object of type BASETYPE.
5744 If a suitable offset type exists already, reuse it. */
5746 tree
5747 build_offset_type (tree basetype, tree type)
5749 tree t;
5750 hashval_t hashcode = 0;
5752 /* Make a node of the sort we want. */
5753 t = make_node (OFFSET_TYPE);
5755 TYPE_OFFSET_BASETYPE (t) = TYPE_MAIN_VARIANT (basetype);
5756 TREE_TYPE (t) = type;
5758 /* If we already have such a type, use the old one. */
5759 hashcode = iterative_hash_object (TYPE_HASH (basetype), hashcode);
5760 hashcode = iterative_hash_object (TYPE_HASH (type), hashcode);
5761 t = type_hash_canon (hashcode, t);
5763 if (!COMPLETE_TYPE_P (t))
5764 layout_type (t);
5766 if (TYPE_CANONICAL (t) == t)
5768 if (TYPE_STRUCTURAL_EQUALITY_P (basetype)
5769 || TYPE_STRUCTURAL_EQUALITY_P (type))
5770 SET_TYPE_STRUCTURAL_EQUALITY (t);
5771 else if (TYPE_CANONICAL (basetype) != basetype
5772 || TYPE_CANONICAL (type) != type)
5773 TYPE_CANONICAL (t)
5774 = build_offset_type (TYPE_CANONICAL (basetype),
5775 TYPE_CANONICAL (type));
5778 return t;
5781 /* Create a complex type whose components are COMPONENT_TYPE. */
5783 tree
5784 build_complex_type (tree component_type)
5786 tree t;
5787 hashval_t hashcode;
5789 /* Make a node of the sort we want. */
5790 t = make_node (COMPLEX_TYPE);
5792 TREE_TYPE (t) = TYPE_MAIN_VARIANT (component_type);
5794 /* If we already have such a type, use the old one. */
5795 hashcode = iterative_hash_object (TYPE_HASH (component_type), 0);
5796 t = type_hash_canon (hashcode, t);
5798 if (!COMPLETE_TYPE_P (t))
5799 layout_type (t);
5801 if (TYPE_CANONICAL (t) == t)
5803 if (TYPE_STRUCTURAL_EQUALITY_P (component_type))
5804 SET_TYPE_STRUCTURAL_EQUALITY (t);
5805 else if (TYPE_CANONICAL (component_type) != component_type)
5806 TYPE_CANONICAL (t)
5807 = build_complex_type (TYPE_CANONICAL (component_type));
5810 /* If we are writing Dwarf2 output we need to create a name,
5811 since complex is a fundamental type. */
5812 if ((write_symbols == DWARF2_DEBUG || write_symbols == VMS_AND_DWARF2_DEBUG)
5813 && ! TYPE_NAME (t))
5815 const char *name;
5816 if (component_type == char_type_node)
5817 name = "complex char";
5818 else if (component_type == signed_char_type_node)
5819 name = "complex signed char";
5820 else if (component_type == unsigned_char_type_node)
5821 name = "complex unsigned char";
5822 else if (component_type == short_integer_type_node)
5823 name = "complex short int";
5824 else if (component_type == short_unsigned_type_node)
5825 name = "complex short unsigned int";
5826 else if (component_type == integer_type_node)
5827 name = "complex int";
5828 else if (component_type == unsigned_type_node)
5829 name = "complex unsigned int";
5830 else if (component_type == long_integer_type_node)
5831 name = "complex long int";
5832 else if (component_type == long_unsigned_type_node)
5833 name = "complex long unsigned int";
5834 else if (component_type == long_long_integer_type_node)
5835 name = "complex long long int";
5836 else if (component_type == long_long_unsigned_type_node)
5837 name = "complex long long unsigned int";
5838 else
5839 name = 0;
5841 if (name != 0)
5842 TYPE_NAME (t) = build_decl (TYPE_DECL, get_identifier (name), t);
5845 return build_qualified_type (t, TYPE_QUALS (component_type));
5848 /* Return OP, stripped of any conversions to wider types as much as is safe.
5849 Converting the value back to OP's type makes a value equivalent to OP.
5851 If FOR_TYPE is nonzero, we return a value which, if converted to
5852 type FOR_TYPE, would be equivalent to converting OP to type FOR_TYPE.
5854 If FOR_TYPE is nonzero, unaligned bit-field references may be changed to the
5855 narrowest type that can hold the value, even if they don't exactly fit.
5856 Otherwise, bit-field references are changed to a narrower type
5857 only if they can be fetched directly from memory in that type.
5859 OP must have integer, real or enumeral type. Pointers are not allowed!
5861 There are some cases where the obvious value we could return
5862 would regenerate to OP if converted to OP's type,
5863 but would not extend like OP to wider types.
5864 If FOR_TYPE indicates such extension is contemplated, we eschew such values.
5865 For example, if OP is (unsigned short)(signed char)-1,
5866 we avoid returning (signed char)-1 if FOR_TYPE is int,
5867 even though extending that to an unsigned short would regenerate OP,
5868 since the result of extending (signed char)-1 to (int)
5869 is different from (int) OP. */
5871 tree
5872 get_unwidened (tree op, tree for_type)
5874 /* Set UNS initially if converting OP to FOR_TYPE is a zero-extension. */
5875 tree type = TREE_TYPE (op);
5876 unsigned final_prec
5877 = TYPE_PRECISION (for_type != 0 ? for_type : type);
5878 int uns
5879 = (for_type != 0 && for_type != type
5880 && final_prec > TYPE_PRECISION (type)
5881 && TYPE_UNSIGNED (type));
5882 tree win = op;
5884 while (TREE_CODE (op) == NOP_EXPR
5885 || TREE_CODE (op) == CONVERT_EXPR)
5887 int bitschange;
5889 /* TYPE_PRECISION on vector types has different meaning
5890 (TYPE_VECTOR_SUBPARTS) and casts from vectors are view conversions,
5891 so avoid them here. */
5892 if (TREE_CODE (TREE_TYPE (TREE_OPERAND (op, 0))) == VECTOR_TYPE)
5893 break;
5895 bitschange = TYPE_PRECISION (TREE_TYPE (op))
5896 - TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (op, 0)));
5898 /* Truncations are many-one so cannot be removed.
5899 Unless we are later going to truncate down even farther. */
5900 if (bitschange < 0
5901 && final_prec > TYPE_PRECISION (TREE_TYPE (op)))
5902 break;
5904 /* See what's inside this conversion. If we decide to strip it,
5905 we will set WIN. */
5906 op = TREE_OPERAND (op, 0);
5908 /* If we have not stripped any zero-extensions (uns is 0),
5909 we can strip any kind of extension.
5910 If we have previously stripped a zero-extension,
5911 only zero-extensions can safely be stripped.
5912 Any extension can be stripped if the bits it would produce
5913 are all going to be discarded later by truncating to FOR_TYPE. */
5915 if (bitschange > 0)
5917 if (! uns || final_prec <= TYPE_PRECISION (TREE_TYPE (op)))
5918 win = op;
5919 /* TYPE_UNSIGNED says whether this is a zero-extension.
5920 Let's avoid computing it if it does not affect WIN
5921 and if UNS will not be needed again. */
5922 if ((uns
5923 || TREE_CODE (op) == NOP_EXPR
5924 || TREE_CODE (op) == CONVERT_EXPR)
5925 && TYPE_UNSIGNED (TREE_TYPE (op)))
5927 uns = 1;
5928 win = op;
5933 if (TREE_CODE (op) == COMPONENT_REF
5934 /* Since type_for_size always gives an integer type. */
5935 && TREE_CODE (type) != REAL_TYPE
5936 /* Don't crash if field not laid out yet. */
5937 && DECL_SIZE (TREE_OPERAND (op, 1)) != 0
5938 && host_integerp (DECL_SIZE (TREE_OPERAND (op, 1)), 1))
5940 unsigned int innerprec
5941 = tree_low_cst (DECL_SIZE (TREE_OPERAND (op, 1)), 1);
5942 int unsignedp = (DECL_UNSIGNED (TREE_OPERAND (op, 1))
5943 || TYPE_UNSIGNED (TREE_TYPE (TREE_OPERAND (op, 1))));
5944 type = lang_hooks.types.type_for_size (innerprec, unsignedp);
5946 /* We can get this structure field in the narrowest type it fits in.
5947 If FOR_TYPE is 0, do this only for a field that matches the
5948 narrower type exactly and is aligned for it
5949 The resulting extension to its nominal type (a fullword type)
5950 must fit the same conditions as for other extensions. */
5952 if (type != 0
5953 && INT_CST_LT_UNSIGNED (TYPE_SIZE (type), TYPE_SIZE (TREE_TYPE (op)))
5954 && (for_type || ! DECL_BIT_FIELD (TREE_OPERAND (op, 1)))
5955 && (! uns || final_prec <= innerprec || unsignedp))
5957 win = build3 (COMPONENT_REF, type, TREE_OPERAND (op, 0),
5958 TREE_OPERAND (op, 1), NULL_TREE);
5959 TREE_SIDE_EFFECTS (win) = TREE_SIDE_EFFECTS (op);
5960 TREE_THIS_VOLATILE (win) = TREE_THIS_VOLATILE (op);
5964 return win;
5967 /* Return OP or a simpler expression for a narrower value
5968 which can be sign-extended or zero-extended to give back OP.
5969 Store in *UNSIGNEDP_PTR either 1 if the value should be zero-extended
5970 or 0 if the value should be sign-extended. */
5972 tree
5973 get_narrower (tree op, int *unsignedp_ptr)
5975 int uns = 0;
5976 int first = 1;
5977 tree win = op;
5978 bool integral_p = INTEGRAL_TYPE_P (TREE_TYPE (op));
5980 while (TREE_CODE (op) == NOP_EXPR)
5982 int bitschange
5983 = (TYPE_PRECISION (TREE_TYPE (op))
5984 - TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (op, 0))));
5986 /* Truncations are many-one so cannot be removed. */
5987 if (bitschange < 0)
5988 break;
5990 /* See what's inside this conversion. If we decide to strip it,
5991 we will set WIN. */
5993 if (bitschange > 0)
5995 op = TREE_OPERAND (op, 0);
5996 /* An extension: the outermost one can be stripped,
5997 but remember whether it is zero or sign extension. */
5998 if (first)
5999 uns = TYPE_UNSIGNED (TREE_TYPE (op));
6000 /* Otherwise, if a sign extension has been stripped,
6001 only sign extensions can now be stripped;
6002 if a zero extension has been stripped, only zero-extensions. */
6003 else if (uns != TYPE_UNSIGNED (TREE_TYPE (op)))
6004 break;
6005 first = 0;
6007 else /* bitschange == 0 */
6009 /* A change in nominal type can always be stripped, but we must
6010 preserve the unsignedness. */
6011 if (first)
6012 uns = TYPE_UNSIGNED (TREE_TYPE (op));
6013 first = 0;
6014 op = TREE_OPERAND (op, 0);
6015 /* Keep trying to narrow, but don't assign op to win if it
6016 would turn an integral type into something else. */
6017 if (INTEGRAL_TYPE_P (TREE_TYPE (op)) != integral_p)
6018 continue;
6021 win = op;
6024 if (TREE_CODE (op) == COMPONENT_REF
6025 /* Since type_for_size always gives an integer type. */
6026 && TREE_CODE (TREE_TYPE (op)) != REAL_TYPE
6027 /* Ensure field is laid out already. */
6028 && DECL_SIZE (TREE_OPERAND (op, 1)) != 0
6029 && host_integerp (DECL_SIZE (TREE_OPERAND (op, 1)), 1))
6031 unsigned HOST_WIDE_INT innerprec
6032 = tree_low_cst (DECL_SIZE (TREE_OPERAND (op, 1)), 1);
6033 int unsignedp = (DECL_UNSIGNED (TREE_OPERAND (op, 1))
6034 || TYPE_UNSIGNED (TREE_TYPE (TREE_OPERAND (op, 1))));
6035 tree type = lang_hooks.types.type_for_size (innerprec, unsignedp);
6037 /* We can get this structure field in a narrower type that fits it,
6038 but the resulting extension to its nominal type (a fullword type)
6039 must satisfy the same conditions as for other extensions.
6041 Do this only for fields that are aligned (not bit-fields),
6042 because when bit-field insns will be used there is no
6043 advantage in doing this. */
6045 if (innerprec < TYPE_PRECISION (TREE_TYPE (op))
6046 && ! DECL_BIT_FIELD (TREE_OPERAND (op, 1))
6047 && (first || uns == DECL_UNSIGNED (TREE_OPERAND (op, 1)))
6048 && type != 0)
6050 if (first)
6051 uns = DECL_UNSIGNED (TREE_OPERAND (op, 1));
6052 win = fold_convert (type, op);
6056 *unsignedp_ptr = uns;
6057 return win;
6060 /* Nonzero if integer constant C has a value that is permissible
6061 for type TYPE (an INTEGER_TYPE). */
6064 int_fits_type_p (tree c, tree type)
6066 tree type_low_bound = TYPE_MIN_VALUE (type);
6067 tree type_high_bound = TYPE_MAX_VALUE (type);
6068 bool ok_for_low_bound, ok_for_high_bound;
6069 unsigned HOST_WIDE_INT low;
6070 HOST_WIDE_INT high;
6072 /* If at least one bound of the type is a constant integer, we can check
6073 ourselves and maybe make a decision. If no such decision is possible, but
6074 this type is a subtype, try checking against that. Otherwise, use
6075 fit_double_type, which checks against the precision.
6077 Compute the status for each possibly constant bound, and return if we see
6078 one does not match. Use ok_for_xxx_bound for this purpose, assigning -1
6079 for "unknown if constant fits", 0 for "constant known *not* to fit" and 1
6080 for "constant known to fit". */
6082 /* Check if C >= type_low_bound. */
6083 if (type_low_bound && TREE_CODE (type_low_bound) == INTEGER_CST)
6085 if (tree_int_cst_lt (c, type_low_bound))
6086 return 0;
6087 ok_for_low_bound = true;
6089 else
6090 ok_for_low_bound = false;
6092 /* Check if c <= type_high_bound. */
6093 if (type_high_bound && TREE_CODE (type_high_bound) == INTEGER_CST)
6095 if (tree_int_cst_lt (type_high_bound, c))
6096 return 0;
6097 ok_for_high_bound = true;
6099 else
6100 ok_for_high_bound = false;
6102 /* If the constant fits both bounds, the result is known. */
6103 if (ok_for_low_bound && ok_for_high_bound)
6104 return 1;
6106 /* Perform some generic filtering which may allow making a decision
6107 even if the bounds are not constant. First, negative integers
6108 never fit in unsigned types, */
6109 if (TYPE_UNSIGNED (type) && tree_int_cst_sgn (c) < 0)
6110 return 0;
6112 /* Second, narrower types always fit in wider ones. */
6113 if (TYPE_PRECISION (type) > TYPE_PRECISION (TREE_TYPE (c)))
6114 return 1;
6116 /* Third, unsigned integers with top bit set never fit signed types. */
6117 if (! TYPE_UNSIGNED (type)
6118 && TYPE_UNSIGNED (TREE_TYPE (c))
6119 && tree_int_cst_msb (c))
6120 return 0;
6122 /* If we haven't been able to decide at this point, there nothing more we
6123 can check ourselves here. Look at the base type if we have one and it
6124 has the same precision. */
6125 if (TREE_CODE (type) == INTEGER_TYPE
6126 && TREE_TYPE (type) != 0
6127 && TYPE_PRECISION (type) == TYPE_PRECISION (TREE_TYPE (type)))
6128 return int_fits_type_p (c, TREE_TYPE (type));
6130 /* Or to fit_double_type, if nothing else. */
6131 low = TREE_INT_CST_LOW (c);
6132 high = TREE_INT_CST_HIGH (c);
6133 return !fit_double_type (low, high, &low, &high, type);
6136 /* Stores bounds of an integer TYPE in MIN and MAX. If TYPE has non-constant
6137 bounds or is a POINTER_TYPE, the maximum and/or minimum values that can be
6138 represented (assuming two's-complement arithmetic) within the bit
6139 precision of the type are returned instead. */
6141 void
6142 get_type_static_bounds (tree type, mpz_t min, mpz_t max)
6144 if (!POINTER_TYPE_P (type) && TYPE_MIN_VALUE (type)
6145 && TREE_CODE (TYPE_MIN_VALUE (type)) == INTEGER_CST)
6146 mpz_set_double_int (min, tree_to_double_int (TYPE_MIN_VALUE (type)),
6147 TYPE_UNSIGNED (type));
6148 else
6150 if (TYPE_UNSIGNED (type))
6151 mpz_set_ui (min, 0);
6152 else
6154 double_int mn;
6155 mn = double_int_mask (TYPE_PRECISION (type) - 1);
6156 mn = double_int_sext (double_int_add (mn, double_int_one),
6157 TYPE_PRECISION (type));
6158 mpz_set_double_int (min, mn, false);
6162 if (!POINTER_TYPE_P (type) && TYPE_MAX_VALUE (type)
6163 && TREE_CODE (TYPE_MAX_VALUE (type)) == INTEGER_CST)
6164 mpz_set_double_int (max, tree_to_double_int (TYPE_MAX_VALUE (type)),
6165 TYPE_UNSIGNED (type));
6166 else
6168 if (TYPE_UNSIGNED (type))
6169 mpz_set_double_int (max, double_int_mask (TYPE_PRECISION (type)),
6170 true);
6171 else
6172 mpz_set_double_int (max, double_int_mask (TYPE_PRECISION (type) - 1),
6173 true);
6177 /* Subprogram of following function. Called by walk_tree.
6179 Return *TP if it is an automatic variable or parameter of the
6180 function passed in as DATA. */
6182 static tree
6183 find_var_from_fn (tree *tp, int *walk_subtrees, void *data)
6185 tree fn = (tree) data;
6187 if (TYPE_P (*tp))
6188 *walk_subtrees = 0;
6190 else if (DECL_P (*tp)
6191 && lang_hooks.tree_inlining.auto_var_in_fn_p (*tp, fn))
6192 return *tp;
6194 return NULL_TREE;
6197 /* Returns true if T is, contains, or refers to a type with variable
6198 size. For METHOD_TYPEs and FUNCTION_TYPEs we exclude the
6199 arguments, but not the return type. If FN is nonzero, only return
6200 true if a modifier of the type or position of FN is a variable or
6201 parameter inside FN.
6203 This concept is more general than that of C99 'variably modified types':
6204 in C99, a struct type is never variably modified because a VLA may not
6205 appear as a structure member. However, in GNU C code like:
6207 struct S { int i[f()]; };
6209 is valid, and other languages may define similar constructs. */
6211 bool
6212 variably_modified_type_p (tree type, tree fn)
6214 tree t;
6216 /* Test if T is either variable (if FN is zero) or an expression containing
6217 a variable in FN. */
6218 #define RETURN_TRUE_IF_VAR(T) \
6219 do { tree _t = (T); \
6220 if (_t && _t != error_mark_node && TREE_CODE (_t) != INTEGER_CST \
6221 && (!fn || walk_tree (&_t, find_var_from_fn, fn, NULL))) \
6222 return true; } while (0)
6224 if (type == error_mark_node)
6225 return false;
6227 /* If TYPE itself has variable size, it is variably modified. */
6228 RETURN_TRUE_IF_VAR (TYPE_SIZE (type));
6229 RETURN_TRUE_IF_VAR (TYPE_SIZE_UNIT (type));
6231 switch (TREE_CODE (type))
6233 case POINTER_TYPE:
6234 case REFERENCE_TYPE:
6235 case VECTOR_TYPE:
6236 if (variably_modified_type_p (TREE_TYPE (type), fn))
6237 return true;
6238 break;
6240 case FUNCTION_TYPE:
6241 case METHOD_TYPE:
6242 /* If TYPE is a function type, it is variably modified if the
6243 return type is variably modified. */
6244 if (variably_modified_type_p (TREE_TYPE (type), fn))
6245 return true;
6246 break;
6248 case INTEGER_TYPE:
6249 case REAL_TYPE:
6250 case ENUMERAL_TYPE:
6251 case BOOLEAN_TYPE:
6252 /* Scalar types are variably modified if their end points
6253 aren't constant. */
6254 RETURN_TRUE_IF_VAR (TYPE_MIN_VALUE (type));
6255 RETURN_TRUE_IF_VAR (TYPE_MAX_VALUE (type));
6256 break;
6258 case RECORD_TYPE:
6259 case UNION_TYPE:
6260 case QUAL_UNION_TYPE:
6261 /* We can't see if any of the fields are variably-modified by the
6262 definition we normally use, since that would produce infinite
6263 recursion via pointers. */
6264 /* This is variably modified if some field's type is. */
6265 for (t = TYPE_FIELDS (type); t; t = TREE_CHAIN (t))
6266 if (TREE_CODE (t) == FIELD_DECL)
6268 RETURN_TRUE_IF_VAR (DECL_FIELD_OFFSET (t));
6269 RETURN_TRUE_IF_VAR (DECL_SIZE (t));
6270 RETURN_TRUE_IF_VAR (DECL_SIZE_UNIT (t));
6272 if (TREE_CODE (type) == QUAL_UNION_TYPE)
6273 RETURN_TRUE_IF_VAR (DECL_QUALIFIER (t));
6275 break;
6277 case ARRAY_TYPE:
6278 /* Do not call ourselves to avoid infinite recursion. This is
6279 variably modified if the element type is. */
6280 RETURN_TRUE_IF_VAR (TYPE_SIZE (TREE_TYPE (type)));
6281 RETURN_TRUE_IF_VAR (TYPE_SIZE_UNIT (TREE_TYPE (type)));
6282 break;
6284 default:
6285 break;
6288 /* The current language may have other cases to check, but in general,
6289 all other types are not variably modified. */
6290 return lang_hooks.tree_inlining.var_mod_type_p (type, fn);
6292 #undef RETURN_TRUE_IF_VAR
6295 /* Given a DECL or TYPE, return the scope in which it was declared, or
6296 NULL_TREE if there is no containing scope. */
6298 tree
6299 get_containing_scope (tree t)
6301 return (TYPE_P (t) ? TYPE_CONTEXT (t) : DECL_CONTEXT (t));
6304 /* Return the innermost context enclosing DECL that is
6305 a FUNCTION_DECL, or zero if none. */
6307 tree
6308 decl_function_context (tree decl)
6310 tree context;
6312 if (TREE_CODE (decl) == ERROR_MARK)
6313 return 0;
6315 /* C++ virtual functions use DECL_CONTEXT for the class of the vtable
6316 where we look up the function at runtime. Such functions always take
6317 a first argument of type 'pointer to real context'.
6319 C++ should really be fixed to use DECL_CONTEXT for the real context,
6320 and use something else for the "virtual context". */
6321 else if (TREE_CODE (decl) == FUNCTION_DECL && DECL_VINDEX (decl))
6322 context
6323 = TYPE_MAIN_VARIANT
6324 (TREE_TYPE (TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (decl)))));
6325 else
6326 context = DECL_CONTEXT (decl);
6328 while (context && TREE_CODE (context) != FUNCTION_DECL)
6330 if (TREE_CODE (context) == BLOCK)
6331 context = BLOCK_SUPERCONTEXT (context);
6332 else
6333 context = get_containing_scope (context);
6336 return context;
6339 /* Return the innermost context enclosing DECL that is
6340 a RECORD_TYPE, UNION_TYPE or QUAL_UNION_TYPE, or zero if none.
6341 TYPE_DECLs and FUNCTION_DECLs are transparent to this function. */
6343 tree
6344 decl_type_context (tree decl)
6346 tree context = DECL_CONTEXT (decl);
6348 while (context)
6349 switch (TREE_CODE (context))
6351 case NAMESPACE_DECL:
6352 case TRANSLATION_UNIT_DECL:
6353 return NULL_TREE;
6355 case RECORD_TYPE:
6356 case UNION_TYPE:
6357 case QUAL_UNION_TYPE:
6358 return context;
6360 case TYPE_DECL:
6361 case FUNCTION_DECL:
6362 context = DECL_CONTEXT (context);
6363 break;
6365 case BLOCK:
6366 context = BLOCK_SUPERCONTEXT (context);
6367 break;
6369 default:
6370 gcc_unreachable ();
6373 return NULL_TREE;
6376 /* CALL is a CALL_EXPR. Return the declaration for the function
6377 called, or NULL_TREE if the called function cannot be
6378 determined. */
6380 tree
6381 get_callee_fndecl (tree call)
6383 tree addr;
6385 if (call == error_mark_node)
6386 return call;
6388 /* It's invalid to call this function with anything but a
6389 CALL_EXPR. */
6390 gcc_assert (TREE_CODE (call) == CALL_EXPR);
6392 /* The first operand to the CALL is the address of the function
6393 called. */
6394 addr = CALL_EXPR_FN (call);
6396 STRIP_NOPS (addr);
6398 /* If this is a readonly function pointer, extract its initial value. */
6399 if (DECL_P (addr) && TREE_CODE (addr) != FUNCTION_DECL
6400 && TREE_READONLY (addr) && ! TREE_THIS_VOLATILE (addr)
6401 && DECL_INITIAL (addr))
6402 addr = DECL_INITIAL (addr);
6404 /* If the address is just `&f' for some function `f', then we know
6405 that `f' is being called. */
6406 if (TREE_CODE (addr) == ADDR_EXPR
6407 && TREE_CODE (TREE_OPERAND (addr, 0)) == FUNCTION_DECL)
6408 return TREE_OPERAND (addr, 0);
6410 /* We couldn't figure out what was being called. Maybe the front
6411 end has some idea. */
6412 return lang_hooks.lang_get_callee_fndecl (call);
6415 /* Print debugging information about tree nodes generated during the compile,
6416 and any language-specific information. */
6418 void
6419 dump_tree_statistics (void)
6421 #ifdef GATHER_STATISTICS
6422 int i;
6423 int total_nodes, total_bytes;
6424 #endif
6426 fprintf (stderr, "\n??? tree nodes created\n\n");
6427 #ifdef GATHER_STATISTICS
6428 fprintf (stderr, "Kind Nodes Bytes\n");
6429 fprintf (stderr, "---------------------------------------\n");
6430 total_nodes = total_bytes = 0;
6431 for (i = 0; i < (int) all_kinds; i++)
6433 fprintf (stderr, "%-20s %7d %10d\n", tree_node_kind_names[i],
6434 tree_node_counts[i], tree_node_sizes[i]);
6435 total_nodes += tree_node_counts[i];
6436 total_bytes += tree_node_sizes[i];
6438 fprintf (stderr, "---------------------------------------\n");
6439 fprintf (stderr, "%-20s %7d %10d\n", "Total", total_nodes, total_bytes);
6440 fprintf (stderr, "---------------------------------------\n");
6441 ssanames_print_statistics ();
6442 phinodes_print_statistics ();
6443 #else
6444 fprintf (stderr, "(No per-node statistics)\n");
6445 #endif
6446 print_type_hash_statistics ();
6447 print_debug_expr_statistics ();
6448 print_value_expr_statistics ();
6449 print_restrict_base_statistics ();
6450 lang_hooks.print_statistics ();
6453 #define FILE_FUNCTION_FORMAT "_GLOBAL__%s_%s"
6455 /* Generate a crc32 of a string. */
6457 unsigned
6458 crc32_string (unsigned chksum, const char *string)
6462 unsigned value = *string << 24;
6463 unsigned ix;
6465 for (ix = 8; ix--; value <<= 1)
6467 unsigned feedback;
6469 feedback = (value ^ chksum) & 0x80000000 ? 0x04c11db7 : 0;
6470 chksum <<= 1;
6471 chksum ^= feedback;
6474 while (*string++);
6475 return chksum;
6478 /* P is a string that will be used in a symbol. Mask out any characters
6479 that are not valid in that context. */
6481 void
6482 clean_symbol_name (char *p)
6484 for (; *p; p++)
6485 if (! (ISALNUM (*p)
6486 #ifndef NO_DOLLAR_IN_LABEL /* this for `$'; unlikely, but... -- kr */
6487 || *p == '$'
6488 #endif
6489 #ifndef NO_DOT_IN_LABEL /* this for `.'; unlikely, but... */
6490 || *p == '.'
6491 #endif
6493 *p = '_';
6496 /* Generate a name for a special-purpose function function.
6497 The generated name may need to be unique across the whole link.
6498 TYPE is some string to identify the purpose of this function to the
6499 linker or collect2; it must start with an uppercase letter,
6500 one of:
6501 I - for constructors
6502 D - for destructors
6503 N - for C++ anonymous namespaces
6504 F - for DWARF unwind frame information. */
6506 tree
6507 get_file_function_name (const char *type)
6509 char *buf;
6510 const char *p;
6511 char *q;
6513 /* If we already have a name we know to be unique, just use that. */
6514 if (first_global_object_name)
6515 p = first_global_object_name;
6516 /* If the target is handling the constructors/destructors, they
6517 will be local to this file and the name is only necessary for
6518 debugging purposes. */
6519 else if ((type[0] == 'I' || type[0] == 'D') && targetm.have_ctors_dtors)
6521 const char *file = main_input_filename;
6522 if (! file)
6523 file = input_filename;
6524 /* Just use the file's basename, because the full pathname
6525 might be quite long. */
6526 p = strrchr (file, '/');
6527 if (p)
6528 p++;
6529 else
6530 p = file;
6531 p = q = ASTRDUP (p);
6532 clean_symbol_name (q);
6534 else
6536 /* Otherwise, the name must be unique across the entire link.
6537 We don't have anything that we know to be unique to this translation
6538 unit, so use what we do have and throw in some randomness. */
6539 unsigned len;
6540 const char *name = weak_global_object_name;
6541 const char *file = main_input_filename;
6543 if (! name)
6544 name = "";
6545 if (! file)
6546 file = input_filename;
6548 len = strlen (file);
6549 q = alloca (9 * 2 + len + 1);
6550 memcpy (q, file, len + 1);
6551 clean_symbol_name (q);
6553 sprintf (q + len, "_%08X_%08X", crc32_string (0, name),
6554 crc32_string (0, get_random_seed (false)));
6556 p = q;
6559 buf = alloca (sizeof (FILE_FUNCTION_FORMAT) + strlen (p) + strlen (type));
6561 /* Set up the name of the file-level functions we may need.
6562 Use a global object (which is already required to be unique over
6563 the program) rather than the file name (which imposes extra
6564 constraints). */
6565 sprintf (buf, FILE_FUNCTION_FORMAT, type, p);
6567 return get_identifier (buf);
6570 #if defined ENABLE_TREE_CHECKING && (GCC_VERSION >= 2007)
6572 /* Complain that the tree code of NODE does not match the expected 0
6573 terminated list of trailing codes. The trailing code list can be
6574 empty, for a more vague error message. FILE, LINE, and FUNCTION
6575 are of the caller. */
6577 void
6578 tree_check_failed (const tree node, const char *file,
6579 int line, const char *function, ...)
6581 va_list args;
6582 char *buffer;
6583 unsigned length = 0;
6584 int code;
6586 va_start (args, function);
6587 while ((code = va_arg (args, int)))
6588 length += 4 + strlen (tree_code_name[code]);
6589 va_end (args);
6590 if (length)
6592 va_start (args, function);
6593 length += strlen ("expected ");
6594 buffer = alloca (length);
6595 length = 0;
6596 while ((code = va_arg (args, int)))
6598 const char *prefix = length ? " or " : "expected ";
6600 strcpy (buffer + length, prefix);
6601 length += strlen (prefix);
6602 strcpy (buffer + length, tree_code_name[code]);
6603 length += strlen (tree_code_name[code]);
6605 va_end (args);
6607 else
6608 buffer = (char *)"unexpected node";
6610 internal_error ("tree check: %s, have %s in %s, at %s:%d",
6611 buffer, tree_code_name[TREE_CODE (node)],
6612 function, trim_filename (file), line);
6615 /* Complain that the tree code of NODE does match the expected 0
6616 terminated list of trailing codes. FILE, LINE, and FUNCTION are of
6617 the caller. */
6619 void
6620 tree_not_check_failed (const tree node, const char *file,
6621 int line, const char *function, ...)
6623 va_list args;
6624 char *buffer;
6625 unsigned length = 0;
6626 int code;
6628 va_start (args, function);
6629 while ((code = va_arg (args, int)))
6630 length += 4 + strlen (tree_code_name[code]);
6631 va_end (args);
6632 va_start (args, function);
6633 buffer = alloca (length);
6634 length = 0;
6635 while ((code = va_arg (args, int)))
6637 if (length)
6639 strcpy (buffer + length, " or ");
6640 length += 4;
6642 strcpy (buffer + length, tree_code_name[code]);
6643 length += strlen (tree_code_name[code]);
6645 va_end (args);
6647 internal_error ("tree check: expected none of %s, have %s in %s, at %s:%d",
6648 buffer, tree_code_name[TREE_CODE (node)],
6649 function, trim_filename (file), line);
6652 /* Similar to tree_check_failed, except that we check for a class of tree
6653 code, given in CL. */
6655 void
6656 tree_class_check_failed (const tree node, const enum tree_code_class cl,
6657 const char *file, int line, const char *function)
6659 internal_error
6660 ("tree check: expected class %qs, have %qs (%s) in %s, at %s:%d",
6661 TREE_CODE_CLASS_STRING (cl),
6662 TREE_CODE_CLASS_STRING (TREE_CODE_CLASS (TREE_CODE (node))),
6663 tree_code_name[TREE_CODE (node)], function, trim_filename (file), line);
6666 /* Similar to tree_check_failed, except that instead of specifying a
6667 dozen codes, use the knowledge that they're all sequential. */
6669 void
6670 tree_range_check_failed (const tree node, const char *file, int line,
6671 const char *function, enum tree_code c1,
6672 enum tree_code c2)
6674 char *buffer;
6675 unsigned length = 0;
6676 enum tree_code c;
6678 for (c = c1; c <= c2; ++c)
6679 length += 4 + strlen (tree_code_name[c]);
6681 length += strlen ("expected ");
6682 buffer = alloca (length);
6683 length = 0;
6685 for (c = c1; c <= c2; ++c)
6687 const char *prefix = length ? " or " : "expected ";
6689 strcpy (buffer + length, prefix);
6690 length += strlen (prefix);
6691 strcpy (buffer + length, tree_code_name[c]);
6692 length += strlen (tree_code_name[c]);
6695 internal_error ("tree check: %s, have %s in %s, at %s:%d",
6696 buffer, tree_code_name[TREE_CODE (node)],
6697 function, trim_filename (file), line);
6701 /* Similar to tree_check_failed, except that we check that a tree does
6702 not have the specified code, given in CL. */
6704 void
6705 tree_not_class_check_failed (const tree node, const enum tree_code_class cl,
6706 const char *file, int line, const char *function)
6708 internal_error
6709 ("tree check: did not expect class %qs, have %qs (%s) in %s, at %s:%d",
6710 TREE_CODE_CLASS_STRING (cl),
6711 TREE_CODE_CLASS_STRING (TREE_CODE_CLASS (TREE_CODE (node))),
6712 tree_code_name[TREE_CODE (node)], function, trim_filename (file), line);
6716 /* Similar to tree_check_failed but applied to OMP_CLAUSE codes. */
6718 void
6719 omp_clause_check_failed (const tree node, const char *file, int line,
6720 const char *function, enum omp_clause_code code)
6722 internal_error ("tree check: expected omp_clause %s, have %s in %s, at %s:%d",
6723 omp_clause_code_name[code], tree_code_name[TREE_CODE (node)],
6724 function, trim_filename (file), line);
6728 /* Similar to tree_range_check_failed but applied to OMP_CLAUSE codes. */
6730 void
6731 omp_clause_range_check_failed (const tree node, const char *file, int line,
6732 const char *function, enum omp_clause_code c1,
6733 enum omp_clause_code c2)
6735 char *buffer;
6736 unsigned length = 0;
6737 enum omp_clause_code c;
6739 for (c = c1; c <= c2; ++c)
6740 length += 4 + strlen (omp_clause_code_name[c]);
6742 length += strlen ("expected ");
6743 buffer = alloca (length);
6744 length = 0;
6746 for (c = c1; c <= c2; ++c)
6748 const char *prefix = length ? " or " : "expected ";
6750 strcpy (buffer + length, prefix);
6751 length += strlen (prefix);
6752 strcpy (buffer + length, omp_clause_code_name[c]);
6753 length += strlen (omp_clause_code_name[c]);
6756 internal_error ("tree check: %s, have %s in %s, at %s:%d",
6757 buffer, omp_clause_code_name[TREE_CODE (node)],
6758 function, trim_filename (file), line);
6762 #undef DEFTREESTRUCT
6763 #define DEFTREESTRUCT(VAL, NAME) NAME,
6765 static const char *ts_enum_names[] = {
6766 #include "treestruct.def"
6768 #undef DEFTREESTRUCT
6770 #define TS_ENUM_NAME(EN) (ts_enum_names[(EN)])
6772 /* Similar to tree_class_check_failed, except that we check for
6773 whether CODE contains the tree structure identified by EN. */
6775 void
6776 tree_contains_struct_check_failed (const tree node,
6777 const enum tree_node_structure_enum en,
6778 const char *file, int line,
6779 const char *function)
6781 internal_error
6782 ("tree check: expected tree that contains %qs structure, have %qs in %s, at %s:%d",
6783 TS_ENUM_NAME(en),
6784 tree_code_name[TREE_CODE (node)], function, trim_filename (file), line);
6788 /* Similar to above, except that the check is for the bounds of a TREE_VEC's
6789 (dynamically sized) vector. */
6791 void
6792 tree_vec_elt_check_failed (int idx, int len, const char *file, int line,
6793 const char *function)
6795 internal_error
6796 ("tree check: accessed elt %d of tree_vec with %d elts in %s, at %s:%d",
6797 idx + 1, len, function, trim_filename (file), line);
6800 /* Similar to above, except that the check is for the bounds of a PHI_NODE's
6801 (dynamically sized) vector. */
6803 void
6804 phi_node_elt_check_failed (int idx, int len, const char *file, int line,
6805 const char *function)
6807 internal_error
6808 ("tree check: accessed elt %d of phi_node with %d elts in %s, at %s:%d",
6809 idx + 1, len, function, trim_filename (file), line);
6812 /* Similar to above, except that the check is for the bounds of the operand
6813 vector of an expression node EXP. */
6815 void
6816 tree_operand_check_failed (int idx, tree exp, const char *file,
6817 int line, const char *function)
6819 int code = TREE_CODE (exp);
6820 internal_error
6821 ("tree check: accessed operand %d of %s with %d operands in %s, at %s:%d",
6822 idx + 1, tree_code_name[code], TREE_OPERAND_LENGTH (exp),
6823 function, trim_filename (file), line);
6826 /* Similar to above, except that the check is for the number of
6827 operands of an OMP_CLAUSE node. */
6829 void
6830 omp_clause_operand_check_failed (int idx, tree t, const char *file,
6831 int line, const char *function)
6833 internal_error
6834 ("tree check: accessed operand %d of omp_clause %s with %d operands "
6835 "in %s, at %s:%d", idx + 1, omp_clause_code_name[OMP_CLAUSE_CODE (t)],
6836 omp_clause_num_ops [OMP_CLAUSE_CODE (t)], function,
6837 trim_filename (file), line);
6839 #endif /* ENABLE_TREE_CHECKING */
6841 /* Create a new vector type node holding SUBPARTS units of type INNERTYPE,
6842 and mapped to the machine mode MODE. Initialize its fields and build
6843 the information necessary for debugging output. */
6845 static tree
6846 make_vector_type (tree innertype, int nunits, enum machine_mode mode)
6848 tree t;
6849 hashval_t hashcode = 0;
6851 /* Build a main variant, based on the main variant of the inner type, then
6852 use it to build the variant we return. */
6853 if ((TYPE_ATTRIBUTES (innertype) || TYPE_QUALS (innertype))
6854 && TYPE_MAIN_VARIANT (innertype) != innertype)
6855 return build_type_attribute_qual_variant (
6856 make_vector_type (TYPE_MAIN_VARIANT (innertype), nunits, mode),
6857 TYPE_ATTRIBUTES (innertype),
6858 TYPE_QUALS (innertype));
6860 t = make_node (VECTOR_TYPE);
6861 TREE_TYPE (t) = TYPE_MAIN_VARIANT (innertype);
6862 SET_TYPE_VECTOR_SUBPARTS (t, nunits);
6863 TYPE_MODE (t) = mode;
6864 TYPE_READONLY (t) = TYPE_READONLY (innertype);
6865 TYPE_VOLATILE (t) = TYPE_VOLATILE (innertype);
6867 if (TYPE_STRUCTURAL_EQUALITY_P (innertype))
6868 SET_TYPE_STRUCTURAL_EQUALITY (t);
6869 else if (TYPE_CANONICAL (innertype) != innertype
6870 || mode != VOIDmode)
6871 TYPE_CANONICAL (t)
6872 = make_vector_type (TYPE_CANONICAL (innertype), nunits, VOIDmode);
6874 layout_type (t);
6877 tree index = build_int_cst (NULL_TREE, nunits - 1);
6878 tree array = build_array_type (innertype, build_index_type (index));
6879 tree rt = make_node (RECORD_TYPE);
6881 TYPE_FIELDS (rt) = build_decl (FIELD_DECL, get_identifier ("f"), array);
6882 DECL_CONTEXT (TYPE_FIELDS (rt)) = rt;
6883 layout_type (rt);
6884 TYPE_DEBUG_REPRESENTATION_TYPE (t) = rt;
6885 /* In dwarfout.c, type lookup uses TYPE_UID numbers. We want to output
6886 the representation type, and we want to find that die when looking up
6887 the vector type. This is most easily achieved by making the TYPE_UID
6888 numbers equal. */
6889 TYPE_UID (rt) = TYPE_UID (t);
6892 hashcode = iterative_hash_host_wide_int (VECTOR_TYPE, hashcode);
6893 hashcode = iterative_hash_host_wide_int (mode, hashcode);
6894 hashcode = iterative_hash_object (TYPE_HASH (innertype), hashcode);
6895 return type_hash_canon (hashcode, t);
6898 static tree
6899 make_or_reuse_type (unsigned size, int unsignedp)
6901 if (size == INT_TYPE_SIZE)
6902 return unsignedp ? unsigned_type_node : integer_type_node;
6903 if (size == CHAR_TYPE_SIZE)
6904 return unsignedp ? unsigned_char_type_node : signed_char_type_node;
6905 if (size == SHORT_TYPE_SIZE)
6906 return unsignedp ? short_unsigned_type_node : short_integer_type_node;
6907 if (size == LONG_TYPE_SIZE)
6908 return unsignedp ? long_unsigned_type_node : long_integer_type_node;
6909 if (size == LONG_LONG_TYPE_SIZE)
6910 return (unsignedp ? long_long_unsigned_type_node
6911 : long_long_integer_type_node);
6913 if (unsignedp)
6914 return make_unsigned_type (size);
6915 else
6916 return make_signed_type (size);
6919 /* Create nodes for all integer types (and error_mark_node) using the sizes
6920 of C datatypes. The caller should call set_sizetype soon after calling
6921 this function to select one of the types as sizetype. */
6923 void
6924 build_common_tree_nodes (bool signed_char, bool signed_sizetype)
6926 error_mark_node = make_node (ERROR_MARK);
6927 TREE_TYPE (error_mark_node) = error_mark_node;
6929 initialize_sizetypes (signed_sizetype);
6931 /* Define both `signed char' and `unsigned char'. */
6932 signed_char_type_node = make_signed_type (CHAR_TYPE_SIZE);
6933 TYPE_STRING_FLAG (signed_char_type_node) = 1;
6934 unsigned_char_type_node = make_unsigned_type (CHAR_TYPE_SIZE);
6935 TYPE_STRING_FLAG (unsigned_char_type_node) = 1;
6937 /* Define `char', which is like either `signed char' or `unsigned char'
6938 but not the same as either. */
6939 char_type_node
6940 = (signed_char
6941 ? make_signed_type (CHAR_TYPE_SIZE)
6942 : make_unsigned_type (CHAR_TYPE_SIZE));
6943 TYPE_STRING_FLAG (char_type_node) = 1;
6945 short_integer_type_node = make_signed_type (SHORT_TYPE_SIZE);
6946 short_unsigned_type_node = make_unsigned_type (SHORT_TYPE_SIZE);
6947 integer_type_node = make_signed_type (INT_TYPE_SIZE);
6948 unsigned_type_node = make_unsigned_type (INT_TYPE_SIZE);
6949 long_integer_type_node = make_signed_type (LONG_TYPE_SIZE);
6950 long_unsigned_type_node = make_unsigned_type (LONG_TYPE_SIZE);
6951 long_long_integer_type_node = make_signed_type (LONG_LONG_TYPE_SIZE);
6952 long_long_unsigned_type_node = make_unsigned_type (LONG_LONG_TYPE_SIZE);
6954 /* Define a boolean type. This type only represents boolean values but
6955 may be larger than char depending on the value of BOOL_TYPE_SIZE.
6956 Front ends which want to override this size (i.e. Java) can redefine
6957 boolean_type_node before calling build_common_tree_nodes_2. */
6958 boolean_type_node = make_unsigned_type (BOOL_TYPE_SIZE);
6959 TREE_SET_CODE (boolean_type_node, BOOLEAN_TYPE);
6960 TYPE_MAX_VALUE (boolean_type_node) = build_int_cst (boolean_type_node, 1);
6961 TYPE_PRECISION (boolean_type_node) = 1;
6963 /* Fill in the rest of the sized types. Reuse existing type nodes
6964 when possible. */
6965 intQI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (QImode), 0);
6966 intHI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (HImode), 0);
6967 intSI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (SImode), 0);
6968 intDI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (DImode), 0);
6969 intTI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (TImode), 0);
6971 unsigned_intQI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (QImode), 1);
6972 unsigned_intHI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (HImode), 1);
6973 unsigned_intSI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (SImode), 1);
6974 unsigned_intDI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (DImode), 1);
6975 unsigned_intTI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (TImode), 1);
6977 access_public_node = get_identifier ("public");
6978 access_protected_node = get_identifier ("protected");
6979 access_private_node = get_identifier ("private");
6982 /* Call this function after calling build_common_tree_nodes and set_sizetype.
6983 It will create several other common tree nodes. */
6985 void
6986 build_common_tree_nodes_2 (int short_double)
6988 /* Define these next since types below may used them. */
6989 integer_zero_node = build_int_cst (NULL_TREE, 0);
6990 integer_one_node = build_int_cst (NULL_TREE, 1);
6991 integer_minus_one_node = build_int_cst (NULL_TREE, -1);
6993 size_zero_node = size_int (0);
6994 size_one_node = size_int (1);
6995 bitsize_zero_node = bitsize_int (0);
6996 bitsize_one_node = bitsize_int (1);
6997 bitsize_unit_node = bitsize_int (BITS_PER_UNIT);
6999 boolean_false_node = TYPE_MIN_VALUE (boolean_type_node);
7000 boolean_true_node = TYPE_MAX_VALUE (boolean_type_node);
7002 void_type_node = make_node (VOID_TYPE);
7003 layout_type (void_type_node);
7005 /* We are not going to have real types in C with less than byte alignment,
7006 so we might as well not have any types that claim to have it. */
7007 TYPE_ALIGN (void_type_node) = BITS_PER_UNIT;
7008 TYPE_USER_ALIGN (void_type_node) = 0;
7010 null_pointer_node = build_int_cst (build_pointer_type (void_type_node), 0);
7011 layout_type (TREE_TYPE (null_pointer_node));
7013 ptr_type_node = build_pointer_type (void_type_node);
7014 const_ptr_type_node
7015 = build_pointer_type (build_type_variant (void_type_node, 1, 0));
7016 fileptr_type_node = ptr_type_node;
7018 float_type_node = make_node (REAL_TYPE);
7019 TYPE_PRECISION (float_type_node) = FLOAT_TYPE_SIZE;
7020 layout_type (float_type_node);
7022 double_type_node = make_node (REAL_TYPE);
7023 if (short_double)
7024 TYPE_PRECISION (double_type_node) = FLOAT_TYPE_SIZE;
7025 else
7026 TYPE_PRECISION (double_type_node) = DOUBLE_TYPE_SIZE;
7027 layout_type (double_type_node);
7029 long_double_type_node = make_node (REAL_TYPE);
7030 TYPE_PRECISION (long_double_type_node) = LONG_DOUBLE_TYPE_SIZE;
7031 layout_type (long_double_type_node);
7033 float_ptr_type_node = build_pointer_type (float_type_node);
7034 double_ptr_type_node = build_pointer_type (double_type_node);
7035 long_double_ptr_type_node = build_pointer_type (long_double_type_node);
7036 integer_ptr_type_node = build_pointer_type (integer_type_node);
7038 /* Fixed size integer types. */
7039 uint32_type_node = build_nonstandard_integer_type (32, true);
7040 uint64_type_node = build_nonstandard_integer_type (64, true);
7042 /* Decimal float types. */
7043 dfloat32_type_node = make_node (REAL_TYPE);
7044 TYPE_PRECISION (dfloat32_type_node) = DECIMAL32_TYPE_SIZE;
7045 layout_type (dfloat32_type_node);
7046 TYPE_MODE (dfloat32_type_node) = SDmode;
7047 dfloat32_ptr_type_node = build_pointer_type (dfloat32_type_node);
7049 dfloat64_type_node = make_node (REAL_TYPE);
7050 TYPE_PRECISION (dfloat64_type_node) = DECIMAL64_TYPE_SIZE;
7051 layout_type (dfloat64_type_node);
7052 TYPE_MODE (dfloat64_type_node) = DDmode;
7053 dfloat64_ptr_type_node = build_pointer_type (dfloat64_type_node);
7055 dfloat128_type_node = make_node (REAL_TYPE);
7056 TYPE_PRECISION (dfloat128_type_node) = DECIMAL128_TYPE_SIZE;
7057 layout_type (dfloat128_type_node);
7058 TYPE_MODE (dfloat128_type_node) = TDmode;
7059 dfloat128_ptr_type_node = build_pointer_type (dfloat128_type_node);
7061 complex_integer_type_node = build_complex_type (integer_type_node);
7062 complex_float_type_node = build_complex_type (float_type_node);
7063 complex_double_type_node = build_complex_type (double_type_node);
7064 complex_long_double_type_node = build_complex_type (long_double_type_node);
7067 tree t = targetm.build_builtin_va_list ();
7069 /* Many back-ends define record types without setting TYPE_NAME.
7070 If we copied the record type here, we'd keep the original
7071 record type without a name. This breaks name mangling. So,
7072 don't copy record types and let c_common_nodes_and_builtins()
7073 declare the type to be __builtin_va_list. */
7074 if (TREE_CODE (t) != RECORD_TYPE)
7075 t = build_variant_type_copy (t);
7077 va_list_type_node = t;
7081 /* A subroutine of build_common_builtin_nodes. Define a builtin function. */
7083 static void
7084 local_define_builtin (const char *name, tree type, enum built_in_function code,
7085 const char *library_name, int ecf_flags)
7087 tree decl;
7089 decl = add_builtin_function (name, type, code, BUILT_IN_NORMAL,
7090 library_name, NULL_TREE);
7091 if (ecf_flags & ECF_CONST)
7092 TREE_READONLY (decl) = 1;
7093 if (ecf_flags & ECF_PURE)
7094 DECL_IS_PURE (decl) = 1;
7095 if (ecf_flags & ECF_NORETURN)
7096 TREE_THIS_VOLATILE (decl) = 1;
7097 if (ecf_flags & ECF_NOTHROW)
7098 TREE_NOTHROW (decl) = 1;
7099 if (ecf_flags & ECF_MALLOC)
7100 DECL_IS_MALLOC (decl) = 1;
7102 built_in_decls[code] = decl;
7103 implicit_built_in_decls[code] = decl;
7106 /* Call this function after instantiating all builtins that the language
7107 front end cares about. This will build the rest of the builtins that
7108 are relied upon by the tree optimizers and the middle-end. */
7110 void
7111 build_common_builtin_nodes (void)
7113 tree tmp, ftype;
7115 if (built_in_decls[BUILT_IN_MEMCPY] == NULL
7116 || built_in_decls[BUILT_IN_MEMMOVE] == NULL)
7118 tmp = tree_cons (NULL_TREE, size_type_node, void_list_node);
7119 tmp = tree_cons (NULL_TREE, const_ptr_type_node, tmp);
7120 tmp = tree_cons (NULL_TREE, ptr_type_node, tmp);
7121 ftype = build_function_type (ptr_type_node, tmp);
7123 if (built_in_decls[BUILT_IN_MEMCPY] == NULL)
7124 local_define_builtin ("__builtin_memcpy", ftype, BUILT_IN_MEMCPY,
7125 "memcpy", ECF_NOTHROW);
7126 if (built_in_decls[BUILT_IN_MEMMOVE] == NULL)
7127 local_define_builtin ("__builtin_memmove", ftype, BUILT_IN_MEMMOVE,
7128 "memmove", ECF_NOTHROW);
7131 if (built_in_decls[BUILT_IN_MEMCMP] == NULL)
7133 tmp = tree_cons (NULL_TREE, size_type_node, void_list_node);
7134 tmp = tree_cons (NULL_TREE, const_ptr_type_node, tmp);
7135 tmp = tree_cons (NULL_TREE, const_ptr_type_node, tmp);
7136 ftype = build_function_type (integer_type_node, tmp);
7137 local_define_builtin ("__builtin_memcmp", ftype, BUILT_IN_MEMCMP,
7138 "memcmp", ECF_PURE | ECF_NOTHROW);
7141 if (built_in_decls[BUILT_IN_MEMSET] == NULL)
7143 tmp = tree_cons (NULL_TREE, size_type_node, void_list_node);
7144 tmp = tree_cons (NULL_TREE, integer_type_node, tmp);
7145 tmp = tree_cons (NULL_TREE, ptr_type_node, tmp);
7146 ftype = build_function_type (ptr_type_node, tmp);
7147 local_define_builtin ("__builtin_memset", ftype, BUILT_IN_MEMSET,
7148 "memset", ECF_NOTHROW);
7151 if (built_in_decls[BUILT_IN_ALLOCA] == NULL)
7153 tmp = tree_cons (NULL_TREE, size_type_node, void_list_node);
7154 ftype = build_function_type (ptr_type_node, tmp);
7155 local_define_builtin ("__builtin_alloca", ftype, BUILT_IN_ALLOCA,
7156 "alloca", ECF_NOTHROW | ECF_MALLOC);
7159 tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node);
7160 tmp = tree_cons (NULL_TREE, ptr_type_node, tmp);
7161 tmp = tree_cons (NULL_TREE, ptr_type_node, tmp);
7162 ftype = build_function_type (void_type_node, tmp);
7163 local_define_builtin ("__builtin_init_trampoline", ftype,
7164 BUILT_IN_INIT_TRAMPOLINE,
7165 "__builtin_init_trampoline", ECF_NOTHROW);
7167 tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node);
7168 ftype = build_function_type (ptr_type_node, tmp);
7169 local_define_builtin ("__builtin_adjust_trampoline", ftype,
7170 BUILT_IN_ADJUST_TRAMPOLINE,
7171 "__builtin_adjust_trampoline",
7172 ECF_CONST | ECF_NOTHROW);
7174 tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node);
7175 tmp = tree_cons (NULL_TREE, ptr_type_node, tmp);
7176 ftype = build_function_type (void_type_node, tmp);
7177 local_define_builtin ("__builtin_nonlocal_goto", ftype,
7178 BUILT_IN_NONLOCAL_GOTO,
7179 "__builtin_nonlocal_goto",
7180 ECF_NORETURN | ECF_NOTHROW);
7182 tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node);
7183 tmp = tree_cons (NULL_TREE, ptr_type_node, tmp);
7184 ftype = build_function_type (void_type_node, tmp);
7185 local_define_builtin ("__builtin_setjmp_setup", ftype,
7186 BUILT_IN_SETJMP_SETUP,
7187 "__builtin_setjmp_setup", ECF_NOTHROW);
7189 tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node);
7190 ftype = build_function_type (ptr_type_node, tmp);
7191 local_define_builtin ("__builtin_setjmp_dispatcher", ftype,
7192 BUILT_IN_SETJMP_DISPATCHER,
7193 "__builtin_setjmp_dispatcher",
7194 ECF_PURE | ECF_NOTHROW);
7196 tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node);
7197 ftype = build_function_type (void_type_node, tmp);
7198 local_define_builtin ("__builtin_setjmp_receiver", ftype,
7199 BUILT_IN_SETJMP_RECEIVER,
7200 "__builtin_setjmp_receiver", ECF_NOTHROW);
7202 ftype = build_function_type (ptr_type_node, void_list_node);
7203 local_define_builtin ("__builtin_stack_save", ftype, BUILT_IN_STACK_SAVE,
7204 "__builtin_stack_save", ECF_NOTHROW);
7206 tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node);
7207 ftype = build_function_type (void_type_node, tmp);
7208 local_define_builtin ("__builtin_stack_restore", ftype,
7209 BUILT_IN_STACK_RESTORE,
7210 "__builtin_stack_restore", ECF_NOTHROW);
7212 ftype = build_function_type (void_type_node, void_list_node);
7213 local_define_builtin ("__builtin_profile_func_enter", ftype,
7214 BUILT_IN_PROFILE_FUNC_ENTER, "profile_func_enter", 0);
7215 local_define_builtin ("__builtin_profile_func_exit", ftype,
7216 BUILT_IN_PROFILE_FUNC_EXIT, "profile_func_exit", 0);
7218 /* Complex multiplication and division. These are handled as builtins
7219 rather than optabs because emit_library_call_value doesn't support
7220 complex. Further, we can do slightly better with folding these
7221 beasties if the real and complex parts of the arguments are separate. */
7223 enum machine_mode mode;
7225 for (mode = MIN_MODE_COMPLEX_FLOAT; mode <= MAX_MODE_COMPLEX_FLOAT; ++mode)
7227 char mode_name_buf[4], *q;
7228 const char *p;
7229 enum built_in_function mcode, dcode;
7230 tree type, inner_type;
7232 type = lang_hooks.types.type_for_mode (mode, 0);
7233 if (type == NULL)
7234 continue;
7235 inner_type = TREE_TYPE (type);
7237 tmp = tree_cons (NULL_TREE, inner_type, void_list_node);
7238 tmp = tree_cons (NULL_TREE, inner_type, tmp);
7239 tmp = tree_cons (NULL_TREE, inner_type, tmp);
7240 tmp = tree_cons (NULL_TREE, inner_type, tmp);
7241 ftype = build_function_type (type, tmp);
7243 mcode = BUILT_IN_COMPLEX_MUL_MIN + mode - MIN_MODE_COMPLEX_FLOAT;
7244 dcode = BUILT_IN_COMPLEX_DIV_MIN + mode - MIN_MODE_COMPLEX_FLOAT;
7246 for (p = GET_MODE_NAME (mode), q = mode_name_buf; *p; p++, q++)
7247 *q = TOLOWER (*p);
7248 *q = '\0';
7250 built_in_names[mcode] = concat ("__mul", mode_name_buf, "3", NULL);
7251 local_define_builtin (built_in_names[mcode], ftype, mcode,
7252 built_in_names[mcode], ECF_CONST | ECF_NOTHROW);
7254 built_in_names[dcode] = concat ("__div", mode_name_buf, "3", NULL);
7255 local_define_builtin (built_in_names[dcode], ftype, dcode,
7256 built_in_names[dcode], ECF_CONST | ECF_NOTHROW);
7261 /* HACK. GROSS. This is absolutely disgusting. I wish there was a
7262 better way.
7264 If we requested a pointer to a vector, build up the pointers that
7265 we stripped off while looking for the inner type. Similarly for
7266 return values from functions.
7268 The argument TYPE is the top of the chain, and BOTTOM is the
7269 new type which we will point to. */
7271 tree
7272 reconstruct_complex_type (tree type, tree bottom)
7274 tree inner, outer;
7276 if (TREE_CODE (type) == POINTER_TYPE)
7278 inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
7279 outer = build_pointer_type_for_mode (inner, TYPE_MODE (type),
7280 TYPE_REF_CAN_ALIAS_ALL (type));
7282 else if (TREE_CODE (type) == REFERENCE_TYPE)
7284 inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
7285 outer = build_reference_type_for_mode (inner, TYPE_MODE (type),
7286 TYPE_REF_CAN_ALIAS_ALL (type));
7288 else if (TREE_CODE (type) == ARRAY_TYPE)
7290 inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
7291 outer = build_array_type (inner, TYPE_DOMAIN (type));
7293 else if (TREE_CODE (type) == FUNCTION_TYPE)
7295 inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
7296 outer = build_function_type (inner, TYPE_ARG_TYPES (type));
7298 else if (TREE_CODE (type) == METHOD_TYPE)
7300 tree argtypes;
7301 inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
7302 /* The build_method_type_directly() routine prepends 'this' to argument list,
7303 so we must compensate by getting rid of it. */
7304 argtypes = TYPE_ARG_TYPES (type);
7305 outer = build_method_type_directly (TYPE_METHOD_BASETYPE (type),
7306 inner,
7307 TYPE_ARG_TYPES (type));
7308 TYPE_ARG_TYPES (outer) = argtypes;
7310 else
7311 return bottom;
7313 TYPE_READONLY (outer) = TYPE_READONLY (type);
7314 TYPE_VOLATILE (outer) = TYPE_VOLATILE (type);
7316 return outer;
7319 /* Returns a vector tree node given a mode (integer, vector, or BLKmode) and
7320 the inner type. */
7321 tree
7322 build_vector_type_for_mode (tree innertype, enum machine_mode mode)
7324 int nunits;
7326 switch (GET_MODE_CLASS (mode))
7328 case MODE_VECTOR_INT:
7329 case MODE_VECTOR_FLOAT:
7330 nunits = GET_MODE_NUNITS (mode);
7331 break;
7333 case MODE_INT:
7334 /* Check that there are no leftover bits. */
7335 gcc_assert (GET_MODE_BITSIZE (mode)
7336 % TREE_INT_CST_LOW (TYPE_SIZE (innertype)) == 0);
7338 nunits = GET_MODE_BITSIZE (mode)
7339 / TREE_INT_CST_LOW (TYPE_SIZE (innertype));
7340 break;
7342 default:
7343 gcc_unreachable ();
7346 return make_vector_type (innertype, nunits, mode);
7349 /* Similarly, but takes the inner type and number of units, which must be
7350 a power of two. */
7352 tree
7353 build_vector_type (tree innertype, int nunits)
7355 return make_vector_type (innertype, nunits, VOIDmode);
7359 /* Build RESX_EXPR with given REGION_NUMBER. */
7360 tree
7361 build_resx (int region_number)
7363 tree t;
7364 t = build1 (RESX_EXPR, void_type_node,
7365 build_int_cst (NULL_TREE, region_number));
7366 return t;
7369 /* Given an initializer INIT, return TRUE if INIT is zero or some
7370 aggregate of zeros. Otherwise return FALSE. */
7371 bool
7372 initializer_zerop (tree init)
7374 tree elt;
7376 STRIP_NOPS (init);
7378 switch (TREE_CODE (init))
7380 case INTEGER_CST:
7381 return integer_zerop (init);
7383 case REAL_CST:
7384 /* ??? Note that this is not correct for C4X float formats. There,
7385 a bit pattern of all zeros is 1.0; 0.0 is encoded with the most
7386 negative exponent. */
7387 return real_zerop (init)
7388 && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (init));
7390 case COMPLEX_CST:
7391 return integer_zerop (init)
7392 || (real_zerop (init)
7393 && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (TREE_REALPART (init)))
7394 && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (TREE_IMAGPART (init))));
7396 case VECTOR_CST:
7397 for (elt = TREE_VECTOR_CST_ELTS (init); elt; elt = TREE_CHAIN (elt))
7398 if (!initializer_zerop (TREE_VALUE (elt)))
7399 return false;
7400 return true;
7402 case CONSTRUCTOR:
7404 unsigned HOST_WIDE_INT idx;
7406 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (init), idx, elt)
7407 if (!initializer_zerop (elt))
7408 return false;
7409 return true;
7412 default:
7413 return false;
7417 /* Build an empty statement. */
7419 tree
7420 build_empty_stmt (void)
7422 return build1 (NOP_EXPR, void_type_node, size_zero_node);
7426 /* Build an OpenMP clause with code CODE. */
7428 tree
7429 build_omp_clause (enum omp_clause_code code)
7431 tree t;
7432 int size, length;
7434 length = omp_clause_num_ops[code];
7435 size = (sizeof (struct tree_omp_clause) + (length - 1) * sizeof (tree));
7437 t = ggc_alloc (size);
7438 memset (t, 0, size);
7439 TREE_SET_CODE (t, OMP_CLAUSE);
7440 OMP_CLAUSE_SET_CODE (t, code);
7442 #ifdef GATHER_STATISTICS
7443 tree_node_counts[(int) omp_clause_kind]++;
7444 tree_node_sizes[(int) omp_clause_kind] += size;
7445 #endif
7447 return t;
7450 /* Set various status flags when building a CALL_EXPR object T. */
7452 static void
7453 process_call_operands (tree t)
7455 bool side_effects;
7457 side_effects = TREE_SIDE_EFFECTS (t);
7458 if (!side_effects)
7460 int i, n;
7461 n = TREE_OPERAND_LENGTH (t);
7462 for (i = 1; i < n; i++)
7464 tree op = TREE_OPERAND (t, i);
7465 if (op && TREE_SIDE_EFFECTS (op))
7467 side_effects = 1;
7468 break;
7472 if (!side_effects)
7474 int i;
7476 /* Calls have side-effects, except those to const or
7477 pure functions. */
7478 i = call_expr_flags (t);
7479 if (!(i & (ECF_CONST | ECF_PURE)))
7480 side_effects = 1;
7482 TREE_SIDE_EFFECTS (t) = side_effects;
7485 /* Build a tcc_vl_exp object with code CODE and room for LEN operands. LEN
7486 includes the implicit operand count in TREE_OPERAND 0, and so must be >= 1.
7487 Except for the CODE and operand count field, other storage for the
7488 object is initialized to zeros. */
7490 tree
7491 build_vl_exp_stat (enum tree_code code, int len MEM_STAT_DECL)
7493 tree t;
7494 int length = (len - 1) * sizeof (tree) + sizeof (struct tree_exp);
7496 gcc_assert (TREE_CODE_CLASS (code) == tcc_vl_exp);
7497 gcc_assert (len >= 1);
7499 #ifdef GATHER_STATISTICS
7500 tree_node_counts[(int) e_kind]++;
7501 tree_node_sizes[(int) e_kind] += length;
7502 #endif
7504 t = ggc_alloc_zone_pass_stat (length, &tree_zone);
7506 memset (t, 0, length);
7508 TREE_SET_CODE (t, code);
7510 /* Can't use TREE_OPERAND to store the length because if checking is
7511 enabled, it will try to check the length before we store it. :-P */
7512 t->exp.operands[0] = build_int_cst (sizetype, len);
7514 return t;
7518 /* Build a CALL_EXPR of class tcc_vl_exp with the indicated RETURN_TYPE
7519 and FN and a null static chain slot. ARGLIST is a TREE_LIST of the
7520 arguments. */
7522 tree
7523 build_call_list (tree return_type, tree fn, tree arglist)
7525 tree t;
7526 int i;
7528 t = build_vl_exp (CALL_EXPR, list_length (arglist) + 3);
7529 TREE_TYPE (t) = return_type;
7530 CALL_EXPR_FN (t) = fn;
7531 CALL_EXPR_STATIC_CHAIN (t) = NULL_TREE;
7532 for (i = 0; arglist; arglist = TREE_CHAIN (arglist), i++)
7533 CALL_EXPR_ARG (t, i) = TREE_VALUE (arglist);
7534 process_call_operands (t);
7535 return t;
7538 /* Build a CALL_EXPR of class tcc_vl_exp with the indicated RETURN_TYPE and
7539 FN and a null static chain slot. NARGS is the number of call arguments
7540 which are specified as "..." arguments. */
7542 tree
7543 build_call_nary (tree return_type, tree fn, int nargs, ...)
7545 tree ret;
7546 va_list args;
7547 va_start (args, nargs);
7548 ret = build_call_valist (return_type, fn, nargs, args);
7549 va_end (args);
7550 return ret;
7553 /* Build a CALL_EXPR of class tcc_vl_exp with the indicated RETURN_TYPE and
7554 FN and a null static chain slot. NARGS is the number of call arguments
7555 which are specified as a va_list ARGS. */
7557 tree
7558 build_call_valist (tree return_type, tree fn, int nargs, va_list args)
7560 tree t;
7561 int i;
7563 t = build_vl_exp (CALL_EXPR, nargs + 3);
7564 TREE_TYPE (t) = return_type;
7565 CALL_EXPR_FN (t) = fn;
7566 CALL_EXPR_STATIC_CHAIN (t) = NULL_TREE;
7567 for (i = 0; i < nargs; i++)
7568 CALL_EXPR_ARG (t, i) = va_arg (args, tree);
7569 process_call_operands (t);
7570 return t;
7573 /* Build a CALL_EXPR of class tcc_vl_exp with the indicated RETURN_TYPE and
7574 FN and a null static chain slot. NARGS is the number of call arguments
7575 which are specified as a tree array ARGS. */
7577 tree
7578 build_call_array (tree return_type, tree fn, int nargs, tree *args)
7580 tree t;
7581 int i;
7583 t = build_vl_exp (CALL_EXPR, nargs + 3);
7584 TREE_TYPE (t) = return_type;
7585 CALL_EXPR_FN (t) = fn;
7586 CALL_EXPR_STATIC_CHAIN (t) = NULL_TREE;
7587 for (i = 0; i < nargs; i++)
7588 CALL_EXPR_ARG (t, i) = args[i];
7589 process_call_operands (t);
7590 return t;
7594 /* Returns true if it is possible to prove that the index of
7595 an array access REF (an ARRAY_REF expression) falls into the
7596 array bounds. */
7598 bool
7599 in_array_bounds_p (tree ref)
7601 tree idx = TREE_OPERAND (ref, 1);
7602 tree min, max;
7604 if (TREE_CODE (idx) != INTEGER_CST)
7605 return false;
7607 min = array_ref_low_bound (ref);
7608 max = array_ref_up_bound (ref);
7609 if (!min
7610 || !max
7611 || TREE_CODE (min) != INTEGER_CST
7612 || TREE_CODE (max) != INTEGER_CST)
7613 return false;
7615 if (tree_int_cst_lt (idx, min)
7616 || tree_int_cst_lt (max, idx))
7617 return false;
7619 return true;
7622 /* Returns true if it is possible to prove that the range of
7623 an array access REF (an ARRAY_RANGE_REF expression) falls
7624 into the array bounds. */
7626 bool
7627 range_in_array_bounds_p (tree ref)
7629 tree domain_type = TYPE_DOMAIN (TREE_TYPE (ref));
7630 tree range_min, range_max, min, max;
7632 range_min = TYPE_MIN_VALUE (domain_type);
7633 range_max = TYPE_MAX_VALUE (domain_type);
7634 if (!range_min
7635 || !range_max
7636 || TREE_CODE (range_min) != INTEGER_CST
7637 || TREE_CODE (range_max) != INTEGER_CST)
7638 return false;
7640 min = array_ref_low_bound (ref);
7641 max = array_ref_up_bound (ref);
7642 if (!min
7643 || !max
7644 || TREE_CODE (min) != INTEGER_CST
7645 || TREE_CODE (max) != INTEGER_CST)
7646 return false;
7648 if (tree_int_cst_lt (range_min, min)
7649 || tree_int_cst_lt (max, range_max))
7650 return false;
7652 return true;
7655 /* Return true if T (assumed to be a DECL) must be assigned a memory
7656 location. */
7658 bool
7659 needs_to_live_in_memory (tree t)
7661 if (TREE_CODE (t) == SSA_NAME)
7662 t = SSA_NAME_VAR (t);
7664 return (TREE_ADDRESSABLE (t)
7665 || is_global_var (t)
7666 || (TREE_CODE (t) == RESULT_DECL
7667 && aggregate_value_p (t, current_function_decl)));
7670 /* There are situations in which a language considers record types
7671 compatible which have different field lists. Decide if two fields
7672 are compatible. It is assumed that the parent records are compatible. */
7674 bool
7675 fields_compatible_p (tree f1, tree f2)
7677 if (!operand_equal_p (DECL_FIELD_BIT_OFFSET (f1),
7678 DECL_FIELD_BIT_OFFSET (f2), OEP_ONLY_CONST))
7679 return false;
7681 if (!operand_equal_p (DECL_FIELD_OFFSET (f1),
7682 DECL_FIELD_OFFSET (f2), OEP_ONLY_CONST))
7683 return false;
7685 if (!lang_hooks.types_compatible_p (TREE_TYPE (f1), TREE_TYPE (f2)))
7686 return false;
7688 return true;
7691 /* Locate within RECORD a field that is compatible with ORIG_FIELD. */
7693 tree
7694 find_compatible_field (tree record, tree orig_field)
7696 tree f;
7698 for (f = TYPE_FIELDS (record); f ; f = TREE_CHAIN (f))
7699 if (TREE_CODE (f) == FIELD_DECL
7700 && fields_compatible_p (f, orig_field))
7701 return f;
7703 /* ??? Why isn't this on the main fields list? */
7704 f = TYPE_VFIELD (record);
7705 if (f && TREE_CODE (f) == FIELD_DECL
7706 && fields_compatible_p (f, orig_field))
7707 return f;
7709 /* ??? We should abort here, but Java appears to do Bad Things
7710 with inherited fields. */
7711 return orig_field;
7714 /* Return value of a constant X. */
7716 HOST_WIDE_INT
7717 int_cst_value (tree x)
7719 unsigned bits = TYPE_PRECISION (TREE_TYPE (x));
7720 unsigned HOST_WIDE_INT val = TREE_INT_CST_LOW (x);
7721 bool negative = ((val >> (bits - 1)) & 1) != 0;
7723 gcc_assert (bits <= HOST_BITS_PER_WIDE_INT);
7725 if (negative)
7726 val |= (~(unsigned HOST_WIDE_INT) 0) << (bits - 1) << 1;
7727 else
7728 val &= ~((~(unsigned HOST_WIDE_INT) 0) << (bits - 1) << 1);
7730 return val;
7734 /* Return an unsigned type the same as TYPE in other respects. */
7736 static tree
7737 get_unsigned_type (tree type)
7739 return get_signed_or_unsigned_type (1, type);
7742 /* Returns unsigned variant of TYPE. */
7744 tree
7745 unsigned_type_for (tree type)
7747 if (POINTER_TYPE_P (type))
7748 return get_unsigned_type (size_type_node);
7749 return get_unsigned_type (type);
7752 /* Returns signed variant of TYPE. */
7754 tree
7755 signed_type_for (tree type)
7757 if (POINTER_TYPE_P (type))
7758 return lang_hooks.types.signed_type (size_type_node);
7759 return lang_hooks.types.signed_type (type);
7762 /* Returns the largest value obtainable by casting something in INNER type to
7763 OUTER type. */
7765 tree
7766 upper_bound_in_type (tree outer, tree inner)
7768 unsigned HOST_WIDE_INT lo, hi;
7769 unsigned int det = 0;
7770 unsigned oprec = TYPE_PRECISION (outer);
7771 unsigned iprec = TYPE_PRECISION (inner);
7772 unsigned prec;
7774 /* Compute a unique number for every combination. */
7775 det |= (oprec > iprec) ? 4 : 0;
7776 det |= TYPE_UNSIGNED (outer) ? 2 : 0;
7777 det |= TYPE_UNSIGNED (inner) ? 1 : 0;
7779 /* Determine the exponent to use. */
7780 switch (det)
7782 case 0:
7783 case 1:
7784 /* oprec <= iprec, outer: signed, inner: don't care. */
7785 prec = oprec - 1;
7786 break;
7787 case 2:
7788 case 3:
7789 /* oprec <= iprec, outer: unsigned, inner: don't care. */
7790 prec = oprec;
7791 break;
7792 case 4:
7793 /* oprec > iprec, outer: signed, inner: signed. */
7794 prec = iprec - 1;
7795 break;
7796 case 5:
7797 /* oprec > iprec, outer: signed, inner: unsigned. */
7798 prec = iprec;
7799 break;
7800 case 6:
7801 /* oprec > iprec, outer: unsigned, inner: signed. */
7802 prec = oprec;
7803 break;
7804 case 7:
7805 /* oprec > iprec, outer: unsigned, inner: unsigned. */
7806 prec = iprec;
7807 break;
7808 default:
7809 gcc_unreachable ();
7812 /* Compute 2^^prec - 1. */
7813 if (prec <= HOST_BITS_PER_WIDE_INT)
7815 hi = 0;
7816 lo = ((~(unsigned HOST_WIDE_INT) 0)
7817 >> (HOST_BITS_PER_WIDE_INT - prec));
7819 else
7821 hi = ((~(unsigned HOST_WIDE_INT) 0)
7822 >> (2 * HOST_BITS_PER_WIDE_INT - prec));
7823 lo = ~(unsigned HOST_WIDE_INT) 0;
7826 return build_int_cst_wide (outer, lo, hi);
7829 /* Returns the smallest value obtainable by casting something in INNER type to
7830 OUTER type. */
7832 tree
7833 lower_bound_in_type (tree outer, tree inner)
7835 unsigned HOST_WIDE_INT lo, hi;
7836 unsigned oprec = TYPE_PRECISION (outer);
7837 unsigned iprec = TYPE_PRECISION (inner);
7839 /* If OUTER type is unsigned, we can definitely cast 0 to OUTER type
7840 and obtain 0. */
7841 if (TYPE_UNSIGNED (outer)
7842 /* If we are widening something of an unsigned type, OUTER type
7843 contains all values of INNER type. In particular, both INNER
7844 and OUTER types have zero in common. */
7845 || (oprec > iprec && TYPE_UNSIGNED (inner)))
7846 lo = hi = 0;
7847 else
7849 /* If we are widening a signed type to another signed type, we
7850 want to obtain -2^^(iprec-1). If we are keeping the
7851 precision or narrowing to a signed type, we want to obtain
7852 -2^(oprec-1). */
7853 unsigned prec = oprec > iprec ? iprec : oprec;
7855 if (prec <= HOST_BITS_PER_WIDE_INT)
7857 hi = ~(unsigned HOST_WIDE_INT) 0;
7858 lo = (~(unsigned HOST_WIDE_INT) 0) << (prec - 1);
7860 else
7862 hi = ((~(unsigned HOST_WIDE_INT) 0)
7863 << (prec - HOST_BITS_PER_WIDE_INT - 1));
7864 lo = 0;
7868 return build_int_cst_wide (outer, lo, hi);
7871 /* Return nonzero if two operands that are suitable for PHI nodes are
7872 necessarily equal. Specifically, both ARG0 and ARG1 must be either
7873 SSA_NAME or invariant. Note that this is strictly an optimization.
7874 That is, callers of this function can directly call operand_equal_p
7875 and get the same result, only slower. */
7878 operand_equal_for_phi_arg_p (tree arg0, tree arg1)
7880 if (arg0 == arg1)
7881 return 1;
7882 if (TREE_CODE (arg0) == SSA_NAME || TREE_CODE (arg1) == SSA_NAME)
7883 return 0;
7884 return operand_equal_p (arg0, arg1, 0);
7887 /* Returns number of zeros at the end of binary representation of X.
7889 ??? Use ffs if available? */
7891 tree
7892 num_ending_zeros (tree x)
7894 unsigned HOST_WIDE_INT fr, nfr;
7895 unsigned num, abits;
7896 tree type = TREE_TYPE (x);
7898 if (TREE_INT_CST_LOW (x) == 0)
7900 num = HOST_BITS_PER_WIDE_INT;
7901 fr = TREE_INT_CST_HIGH (x);
7903 else
7905 num = 0;
7906 fr = TREE_INT_CST_LOW (x);
7909 for (abits = HOST_BITS_PER_WIDE_INT / 2; abits; abits /= 2)
7911 nfr = fr >> abits;
7912 if (nfr << abits == fr)
7914 num += abits;
7915 fr = nfr;
7919 if (num > TYPE_PRECISION (type))
7920 num = TYPE_PRECISION (type);
7922 return build_int_cst_type (type, num);
7926 #define WALK_SUBTREE(NODE) \
7927 do \
7929 result = walk_tree (&(NODE), func, data, pset); \
7930 if (result) \
7931 return result; \
7933 while (0)
7935 /* This is a subroutine of walk_tree that walks field of TYPE that are to
7936 be walked whenever a type is seen in the tree. Rest of operands and return
7937 value are as for walk_tree. */
7939 static tree
7940 walk_type_fields (tree type, walk_tree_fn func, void *data,
7941 struct pointer_set_t *pset)
7943 tree result = NULL_TREE;
7945 switch (TREE_CODE (type))
7947 case POINTER_TYPE:
7948 case REFERENCE_TYPE:
7949 /* We have to worry about mutually recursive pointers. These can't
7950 be written in C. They can in Ada. It's pathological, but
7951 there's an ACATS test (c38102a) that checks it. Deal with this
7952 by checking if we're pointing to another pointer, that one
7953 points to another pointer, that one does too, and we have no htab.
7954 If so, get a hash table. We check three levels deep to avoid
7955 the cost of the hash table if we don't need one. */
7956 if (POINTER_TYPE_P (TREE_TYPE (type))
7957 && POINTER_TYPE_P (TREE_TYPE (TREE_TYPE (type)))
7958 && POINTER_TYPE_P (TREE_TYPE (TREE_TYPE (TREE_TYPE (type))))
7959 && !pset)
7961 result = walk_tree_without_duplicates (&TREE_TYPE (type),
7962 func, data);
7963 if (result)
7964 return result;
7966 break;
7969 /* ... fall through ... */
7971 case COMPLEX_TYPE:
7972 WALK_SUBTREE (TREE_TYPE (type));
7973 break;
7975 case METHOD_TYPE:
7976 WALK_SUBTREE (TYPE_METHOD_BASETYPE (type));
7978 /* Fall through. */
7980 case FUNCTION_TYPE:
7981 WALK_SUBTREE (TREE_TYPE (type));
7983 tree arg;
7985 /* We never want to walk into default arguments. */
7986 for (arg = TYPE_ARG_TYPES (type); arg; arg = TREE_CHAIN (arg))
7987 WALK_SUBTREE (TREE_VALUE (arg));
7989 break;
7991 case ARRAY_TYPE:
7992 /* Don't follow this nodes's type if a pointer for fear that
7993 we'll have infinite recursion. If we have a PSET, then we
7994 need not fear. */
7995 if (pset
7996 || (!POINTER_TYPE_P (TREE_TYPE (type))
7997 && TREE_CODE (TREE_TYPE (type)) != OFFSET_TYPE))
7998 WALK_SUBTREE (TREE_TYPE (type));
7999 WALK_SUBTREE (TYPE_DOMAIN (type));
8000 break;
8002 case OFFSET_TYPE:
8003 WALK_SUBTREE (TREE_TYPE (type));
8004 WALK_SUBTREE (TYPE_OFFSET_BASETYPE (type));
8005 break;
8007 default:
8008 break;
8011 return NULL_TREE;
8014 /* Apply FUNC to all the sub-trees of TP in a pre-order traversal. FUNC is
8015 called with the DATA and the address of each sub-tree. If FUNC returns a
8016 non-NULL value, the traversal is stopped, and the value returned by FUNC
8017 is returned. If PSET is non-NULL it is used to record the nodes visited,
8018 and to avoid visiting a node more than once. */
8020 tree
8021 walk_tree (tree *tp, walk_tree_fn func, void *data, struct pointer_set_t *pset)
8023 enum tree_code code;
8024 int walk_subtrees;
8025 tree result;
8027 #define WALK_SUBTREE_TAIL(NODE) \
8028 do \
8030 tp = & (NODE); \
8031 goto tail_recurse; \
8033 while (0)
8035 tail_recurse:
8036 /* Skip empty subtrees. */
8037 if (!*tp)
8038 return NULL_TREE;
8040 /* Don't walk the same tree twice, if the user has requested
8041 that we avoid doing so. */
8042 if (pset && pointer_set_insert (pset, *tp))
8043 return NULL_TREE;
8045 /* Call the function. */
8046 walk_subtrees = 1;
8047 result = (*func) (tp, &walk_subtrees, data);
8049 /* If we found something, return it. */
8050 if (result)
8051 return result;
8053 code = TREE_CODE (*tp);
8055 /* Even if we didn't, FUNC may have decided that there was nothing
8056 interesting below this point in the tree. */
8057 if (!walk_subtrees)
8059 /* But we still need to check our siblings. */
8060 if (code == TREE_LIST)
8061 WALK_SUBTREE_TAIL (TREE_CHAIN (*tp));
8062 else if (code == OMP_CLAUSE)
8063 WALK_SUBTREE_TAIL (OMP_CLAUSE_CHAIN (*tp));
8064 else
8065 return NULL_TREE;
8068 result = lang_hooks.tree_inlining.walk_subtrees (tp, &walk_subtrees, func,
8069 data, pset);
8070 if (result || !walk_subtrees)
8071 return result;
8073 switch (code)
8075 case ERROR_MARK:
8076 case IDENTIFIER_NODE:
8077 case INTEGER_CST:
8078 case REAL_CST:
8079 case VECTOR_CST:
8080 case STRING_CST:
8081 case BLOCK:
8082 case PLACEHOLDER_EXPR:
8083 case SSA_NAME:
8084 case FIELD_DECL:
8085 case RESULT_DECL:
8086 /* None of these have subtrees other than those already walked
8087 above. */
8088 break;
8090 case TREE_LIST:
8091 WALK_SUBTREE (TREE_VALUE (*tp));
8092 WALK_SUBTREE_TAIL (TREE_CHAIN (*tp));
8093 break;
8095 case TREE_VEC:
8097 int len = TREE_VEC_LENGTH (*tp);
8099 if (len == 0)
8100 break;
8102 /* Walk all elements but the first. */
8103 while (--len)
8104 WALK_SUBTREE (TREE_VEC_ELT (*tp, len));
8106 /* Now walk the first one as a tail call. */
8107 WALK_SUBTREE_TAIL (TREE_VEC_ELT (*tp, 0));
8110 case COMPLEX_CST:
8111 WALK_SUBTREE (TREE_REALPART (*tp));
8112 WALK_SUBTREE_TAIL (TREE_IMAGPART (*tp));
8114 case CONSTRUCTOR:
8116 unsigned HOST_WIDE_INT idx;
8117 constructor_elt *ce;
8119 for (idx = 0;
8120 VEC_iterate(constructor_elt, CONSTRUCTOR_ELTS (*tp), idx, ce);
8121 idx++)
8122 WALK_SUBTREE (ce->value);
8124 break;
8126 case SAVE_EXPR:
8127 WALK_SUBTREE_TAIL (TREE_OPERAND (*tp, 0));
8129 case BIND_EXPR:
8131 tree decl;
8132 for (decl = BIND_EXPR_VARS (*tp); decl; decl = TREE_CHAIN (decl))
8134 /* Walk the DECL_INITIAL and DECL_SIZE. We don't want to walk
8135 into declarations that are just mentioned, rather than
8136 declared; they don't really belong to this part of the tree.
8137 And, we can see cycles: the initializer for a declaration
8138 can refer to the declaration itself. */
8139 WALK_SUBTREE (DECL_INITIAL (decl));
8140 WALK_SUBTREE (DECL_SIZE (decl));
8141 WALK_SUBTREE (DECL_SIZE_UNIT (decl));
8143 WALK_SUBTREE_TAIL (BIND_EXPR_BODY (*tp));
8146 case STATEMENT_LIST:
8148 tree_stmt_iterator i;
8149 for (i = tsi_start (*tp); !tsi_end_p (i); tsi_next (&i))
8150 WALK_SUBTREE (*tsi_stmt_ptr (i));
8152 break;
8154 case OMP_CLAUSE:
8155 switch (OMP_CLAUSE_CODE (*tp))
8157 case OMP_CLAUSE_PRIVATE:
8158 case OMP_CLAUSE_SHARED:
8159 case OMP_CLAUSE_FIRSTPRIVATE:
8160 case OMP_CLAUSE_LASTPRIVATE:
8161 case OMP_CLAUSE_COPYIN:
8162 case OMP_CLAUSE_COPYPRIVATE:
8163 case OMP_CLAUSE_IF:
8164 case OMP_CLAUSE_NUM_THREADS:
8165 case OMP_CLAUSE_SCHEDULE:
8166 WALK_SUBTREE (OMP_CLAUSE_OPERAND (*tp, 0));
8167 /* FALLTHRU */
8169 case OMP_CLAUSE_NOWAIT:
8170 case OMP_CLAUSE_ORDERED:
8171 case OMP_CLAUSE_DEFAULT:
8172 WALK_SUBTREE_TAIL (OMP_CLAUSE_CHAIN (*tp));
8174 case OMP_CLAUSE_REDUCTION:
8176 int i;
8177 for (i = 0; i < 4; i++)
8178 WALK_SUBTREE (OMP_CLAUSE_OPERAND (*tp, i));
8179 WALK_SUBTREE_TAIL (OMP_CLAUSE_CHAIN (*tp));
8182 default:
8183 gcc_unreachable ();
8185 break;
8187 case TARGET_EXPR:
8189 int i, len;
8191 /* TARGET_EXPRs are peculiar: operands 1 and 3 can be the same.
8192 But, we only want to walk once. */
8193 len = (TREE_OPERAND (*tp, 3) == TREE_OPERAND (*tp, 1)) ? 2 : 3;
8194 for (i = 0; i < len; ++i)
8195 WALK_SUBTREE (TREE_OPERAND (*tp, i));
8196 WALK_SUBTREE_TAIL (TREE_OPERAND (*tp, len));
8199 case DECL_EXPR:
8200 /* If this is a TYPE_DECL, walk into the fields of the type that it's
8201 defining. We only want to walk into these fields of a type in this
8202 case and not in the general case of a mere reference to the type.
8204 The criterion is as follows: if the field can be an expression, it
8205 must be walked only here. This should be in keeping with the fields
8206 that are directly gimplified in gimplify_type_sizes in order for the
8207 mark/copy-if-shared/unmark machinery of the gimplifier to work with
8208 variable-sized types.
8210 Note that DECLs get walked as part of processing the BIND_EXPR. */
8211 if (TREE_CODE (DECL_EXPR_DECL (*tp)) == TYPE_DECL)
8213 tree *type_p = &TREE_TYPE (DECL_EXPR_DECL (*tp));
8214 if (TREE_CODE (*type_p) == ERROR_MARK)
8215 return NULL_TREE;
8217 /* Call the function for the type. See if it returns anything or
8218 doesn't want us to continue. If we are to continue, walk both
8219 the normal fields and those for the declaration case. */
8220 result = (*func) (type_p, &walk_subtrees, data);
8221 if (result || !walk_subtrees)
8222 return result;
8224 result = walk_type_fields (*type_p, func, data, pset);
8225 if (result)
8226 return result;
8228 /* If this is a record type, also walk the fields. */
8229 if (TREE_CODE (*type_p) == RECORD_TYPE
8230 || TREE_CODE (*type_p) == UNION_TYPE
8231 || TREE_CODE (*type_p) == QUAL_UNION_TYPE)
8233 tree field;
8235 for (field = TYPE_FIELDS (*type_p); field;
8236 field = TREE_CHAIN (field))
8238 /* We'd like to look at the type of the field, but we can
8239 easily get infinite recursion. So assume it's pointed
8240 to elsewhere in the tree. Also, ignore things that
8241 aren't fields. */
8242 if (TREE_CODE (field) != FIELD_DECL)
8243 continue;
8245 WALK_SUBTREE (DECL_FIELD_OFFSET (field));
8246 WALK_SUBTREE (DECL_SIZE (field));
8247 WALK_SUBTREE (DECL_SIZE_UNIT (field));
8248 if (TREE_CODE (*type_p) == QUAL_UNION_TYPE)
8249 WALK_SUBTREE (DECL_QUALIFIER (field));
8253 /* Same for scalar types. */
8254 else if (TREE_CODE (*type_p) == BOOLEAN_TYPE
8255 || TREE_CODE (*type_p) == ENUMERAL_TYPE
8256 || TREE_CODE (*type_p) == INTEGER_TYPE
8257 || TREE_CODE (*type_p) == REAL_TYPE)
8259 WALK_SUBTREE (TYPE_MIN_VALUE (*type_p));
8260 WALK_SUBTREE (TYPE_MAX_VALUE (*type_p));
8263 WALK_SUBTREE (TYPE_SIZE (*type_p));
8264 WALK_SUBTREE_TAIL (TYPE_SIZE_UNIT (*type_p));
8266 /* FALLTHRU */
8268 default:
8269 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code))
8270 || IS_GIMPLE_STMT_CODE_CLASS (TREE_CODE_CLASS (code)))
8272 int i, len;
8274 /* Walk over all the sub-trees of this operand. */
8275 len = TREE_OPERAND_LENGTH (*tp);
8277 /* Go through the subtrees. We need to do this in forward order so
8278 that the scope of a FOR_EXPR is handled properly. */
8279 if (len)
8281 for (i = 0; i < len - 1; ++i)
8282 WALK_SUBTREE (GENERIC_TREE_OPERAND (*tp, i));
8283 WALK_SUBTREE_TAIL (GENERIC_TREE_OPERAND (*tp, len - 1));
8286 /* If this is a type, walk the needed fields in the type. */
8287 else if (TYPE_P (*tp))
8288 return walk_type_fields (*tp, func, data, pset);
8289 break;
8292 /* We didn't find what we were looking for. */
8293 return NULL_TREE;
8295 #undef WALK_SUBTREE_TAIL
8297 #undef WALK_SUBTREE
8299 /* Like walk_tree, but does not walk duplicate nodes more than once. */
8301 tree
8302 walk_tree_without_duplicates (tree *tp, walk_tree_fn func, void *data)
8304 tree result;
8305 struct pointer_set_t *pset;
8307 pset = pointer_set_create ();
8308 result = walk_tree (tp, func, data, pset);
8309 pointer_set_destroy (pset);
8310 return result;
8314 /* Return true if STMT is an empty statement or contains nothing but
8315 empty statements. */
8317 bool
8318 empty_body_p (tree stmt)
8320 tree_stmt_iterator i;
8321 tree body;
8323 if (IS_EMPTY_STMT (stmt))
8324 return true;
8325 else if (TREE_CODE (stmt) == BIND_EXPR)
8326 body = BIND_EXPR_BODY (stmt);
8327 else if (TREE_CODE (stmt) == STATEMENT_LIST)
8328 body = stmt;
8329 else
8330 return false;
8332 for (i = tsi_start (body); !tsi_end_p (i); tsi_next (&i))
8333 if (!empty_body_p (tsi_stmt (i)))
8334 return false;
8336 return true;
8339 tree *
8340 tree_block (tree t)
8342 char const c = TREE_CODE_CLASS (TREE_CODE (t));
8344 if (IS_EXPR_CODE_CLASS (c))
8345 return &t->exp.block;
8346 else if (IS_GIMPLE_STMT_CODE_CLASS (c))
8347 return &GIMPLE_STMT_BLOCK (t);
8348 gcc_unreachable ();
8349 return NULL;
8352 tree *
8353 generic_tree_operand (tree node, int i)
8355 if (GIMPLE_STMT_P (node))
8356 return &GIMPLE_STMT_OPERAND (node, i);
8357 return &TREE_OPERAND (node, i);
8360 tree *
8361 generic_tree_type (tree node)
8363 if (GIMPLE_STMT_P (node))
8364 return &void_type_node;
8365 return &TREE_TYPE (node);
8368 /* Build and return a TREE_LIST of arguments in the CALL_EXPR exp.
8369 FIXME: don't use this function. It exists for compatibility with
8370 the old representation of CALL_EXPRs where a list was used to hold the
8371 arguments. Places that currently extract the arglist from a CALL_EXPR
8372 ought to be rewritten to use the CALL_EXPR itself. */
8373 tree
8374 call_expr_arglist (tree exp)
8376 tree arglist = NULL_TREE;
8377 int i;
8378 for (i = call_expr_nargs (exp) - 1; i >= 0; i--)
8379 arglist = tree_cons (NULL_TREE, CALL_EXPR_ARG (exp, i), arglist);
8380 return arglist;
8383 #include "gt-tree.h"