* doc/invoke.texi: Add cpu_type power6x
[official-gcc.git] / gcc / tree.c
blob5886e18da0a2ce3b71ba013007d8ab5b33dcccc2
1 /* Language-independent node constructors for parse phase of GNU compiler.
2 Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006
4 Free Software Foundation, Inc.
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 "expression",
72 /* obstack.[ch] explicitly declined to prototype this. */
73 extern int _obstack_allocated_p (struct obstack *h, void *obj);
75 #ifdef GATHER_STATISTICS
76 /* Statistics-gathering stuff. */
78 int tree_node_counts[(int) all_kinds];
79 int tree_node_sizes[(int) all_kinds];
81 /* Keep in sync with tree.h:enum tree_node_kind. */
82 static const char * const tree_node_kind_names[] = {
83 "decls",
84 "types",
85 "blocks",
86 "stmts",
87 "refs",
88 "exprs",
89 "constants",
90 "identifiers",
91 "perm_tree_lists",
92 "temp_tree_lists",
93 "vecs",
94 "binfos",
95 "phi_nodes",
96 "ssa names",
97 "constructors",
98 "random kinds",
99 "lang_decl kinds",
100 "lang_type kinds",
101 "omp clauses"
103 #endif /* GATHER_STATISTICS */
105 /* Unique id for next decl created. */
106 static GTY(()) int next_decl_uid;
107 /* Unique id for next type created. */
108 static GTY(()) int next_type_uid = 1;
110 /* Since we cannot rehash a type after it is in the table, we have to
111 keep the hash code. */
113 struct type_hash GTY(())
115 unsigned long hash;
116 tree type;
119 /* Initial size of the hash table (rounded to next prime). */
120 #define TYPE_HASH_INITIAL_SIZE 1000
122 /* Now here is the hash table. When recording a type, it is added to
123 the slot whose index is the hash code. Note that the hash table is
124 used for several kinds of types (function types, array types and
125 array index range types, for now). While all these live in the
126 same table, they are completely independent, and the hash code is
127 computed differently for each of these. */
129 static GTY ((if_marked ("type_hash_marked_p"), param_is (struct type_hash)))
130 htab_t type_hash_table;
132 /* Hash table and temporary node for larger integer const values. */
133 static GTY (()) tree int_cst_node;
134 static GTY ((if_marked ("ggc_marked_p"), param_is (union tree_node)))
135 htab_t int_cst_hash_table;
137 /* General tree->tree mapping structure for use in hash tables. */
140 static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map)))
141 htab_t debug_expr_for_decl;
143 static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map)))
144 htab_t value_expr_for_decl;
146 static GTY ((if_marked ("tree_int_map_marked_p"), param_is (struct tree_int_map)))
147 htab_t init_priority_for_decl;
149 static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map)))
150 htab_t restrict_base_for_decl;
152 struct tree_int_map GTY(())
154 tree from;
155 unsigned short to;
157 static unsigned int tree_int_map_hash (const void *);
158 static int tree_int_map_eq (const void *, const void *);
159 static int tree_int_map_marked_p (const void *);
160 static void set_type_quals (tree, int);
161 static int type_hash_eq (const void *, const void *);
162 static hashval_t type_hash_hash (const void *);
163 static hashval_t int_cst_hash_hash (const void *);
164 static int int_cst_hash_eq (const void *, const void *);
165 static void print_type_hash_statistics (void);
166 static void print_debug_expr_statistics (void);
167 static void print_value_expr_statistics (void);
168 static int type_hash_marked_p (const void *);
169 static unsigned int type_hash_list (tree, hashval_t);
170 static unsigned int attribute_hash_list (tree, hashval_t);
172 tree global_trees[TI_MAX];
173 tree integer_types[itk_none];
175 unsigned char tree_contains_struct[256][64];
177 /* Number of operands for each OpenMP clause. */
178 unsigned const char omp_clause_num_ops[] =
180 0, /* OMP_CLAUSE_ERROR */
181 1, /* OMP_CLAUSE_PRIVATE */
182 1, /* OMP_CLAUSE_SHARED */
183 1, /* OMP_CLAUSE_FIRSTPRIVATE */
184 1, /* OMP_CLAUSE_LASTPRIVATE */
185 4, /* OMP_CLAUSE_REDUCTION */
186 1, /* OMP_CLAUSE_COPYIN */
187 1, /* OMP_CLAUSE_COPYPRIVATE */
188 1, /* OMP_CLAUSE_IF */
189 1, /* OMP_CLAUSE_NUM_THREADS */
190 1, /* OMP_CLAUSE_SCHEDULE */
191 0, /* OMP_CLAUSE_NOWAIT */
192 0, /* OMP_CLAUSE_ORDERED */
193 0 /* OMP_CLAUSE_DEFAULT */
196 const char * const omp_clause_code_name[] =
198 "error_clause",
199 "private",
200 "shared",
201 "firstprivate",
202 "lastprivate",
203 "reduction",
204 "copyin",
205 "copyprivate",
206 "if",
207 "num_threads",
208 "schedule",
209 "nowait",
210 "ordered",
211 "default"
214 /* Init tree.c. */
216 void
217 init_ttree (void)
219 /* Initialize the hash table of types. */
220 type_hash_table = htab_create_ggc (TYPE_HASH_INITIAL_SIZE, type_hash_hash,
221 type_hash_eq, 0);
223 debug_expr_for_decl = htab_create_ggc (512, tree_map_hash,
224 tree_map_eq, 0);
226 value_expr_for_decl = htab_create_ggc (512, tree_map_hash,
227 tree_map_eq, 0);
228 init_priority_for_decl = htab_create_ggc (512, tree_int_map_hash,
229 tree_int_map_eq, 0);
230 restrict_base_for_decl = htab_create_ggc (256, tree_map_hash,
231 tree_map_eq, 0);
233 int_cst_hash_table = htab_create_ggc (1024, int_cst_hash_hash,
234 int_cst_hash_eq, NULL);
236 int_cst_node = make_node (INTEGER_CST);
238 tree_contains_struct[FUNCTION_DECL][TS_DECL_NON_COMMON] = 1;
239 tree_contains_struct[TRANSLATION_UNIT_DECL][TS_DECL_NON_COMMON] = 1;
240 tree_contains_struct[TYPE_DECL][TS_DECL_NON_COMMON] = 1;
243 tree_contains_struct[CONST_DECL][TS_DECL_COMMON] = 1;
244 tree_contains_struct[VAR_DECL][TS_DECL_COMMON] = 1;
245 tree_contains_struct[PARM_DECL][TS_DECL_COMMON] = 1;
246 tree_contains_struct[RESULT_DECL][TS_DECL_COMMON] = 1;
247 tree_contains_struct[FUNCTION_DECL][TS_DECL_COMMON] = 1;
248 tree_contains_struct[TYPE_DECL][TS_DECL_COMMON] = 1;
249 tree_contains_struct[TRANSLATION_UNIT_DECL][TS_DECL_COMMON] = 1;
250 tree_contains_struct[LABEL_DECL][TS_DECL_COMMON] = 1;
251 tree_contains_struct[FIELD_DECL][TS_DECL_COMMON] = 1;
254 tree_contains_struct[CONST_DECL][TS_DECL_WRTL] = 1;
255 tree_contains_struct[VAR_DECL][TS_DECL_WRTL] = 1;
256 tree_contains_struct[PARM_DECL][TS_DECL_WRTL] = 1;
257 tree_contains_struct[RESULT_DECL][TS_DECL_WRTL] = 1;
258 tree_contains_struct[FUNCTION_DECL][TS_DECL_WRTL] = 1;
259 tree_contains_struct[LABEL_DECL][TS_DECL_WRTL] = 1;
261 tree_contains_struct[CONST_DECL][TS_DECL_MINIMAL] = 1;
262 tree_contains_struct[VAR_DECL][TS_DECL_MINIMAL] = 1;
263 tree_contains_struct[PARM_DECL][TS_DECL_MINIMAL] = 1;
264 tree_contains_struct[RESULT_DECL][TS_DECL_MINIMAL] = 1;
265 tree_contains_struct[FUNCTION_DECL][TS_DECL_MINIMAL] = 1;
266 tree_contains_struct[TYPE_DECL][TS_DECL_MINIMAL] = 1;
267 tree_contains_struct[TRANSLATION_UNIT_DECL][TS_DECL_MINIMAL] = 1;
268 tree_contains_struct[LABEL_DECL][TS_DECL_MINIMAL] = 1;
269 tree_contains_struct[FIELD_DECL][TS_DECL_MINIMAL] = 1;
270 tree_contains_struct[STRUCT_FIELD_TAG][TS_DECL_MINIMAL] = 1;
271 tree_contains_struct[NAME_MEMORY_TAG][TS_DECL_MINIMAL] = 1;
272 tree_contains_struct[SYMBOL_MEMORY_TAG][TS_DECL_MINIMAL] = 1;
274 tree_contains_struct[STRUCT_FIELD_TAG][TS_MEMORY_TAG] = 1;
275 tree_contains_struct[NAME_MEMORY_TAG][TS_MEMORY_TAG] = 1;
276 tree_contains_struct[SYMBOL_MEMORY_TAG][TS_MEMORY_TAG] = 1;
278 tree_contains_struct[STRUCT_FIELD_TAG][TS_STRUCT_FIELD_TAG] = 1;
280 tree_contains_struct[VAR_DECL][TS_DECL_WITH_VIS] = 1;
281 tree_contains_struct[FUNCTION_DECL][TS_DECL_WITH_VIS] = 1;
282 tree_contains_struct[TYPE_DECL][TS_DECL_WITH_VIS] = 1;
283 tree_contains_struct[TRANSLATION_UNIT_DECL][TS_DECL_WITH_VIS] = 1;
285 tree_contains_struct[VAR_DECL][TS_VAR_DECL] = 1;
286 tree_contains_struct[FIELD_DECL][TS_FIELD_DECL] = 1;
287 tree_contains_struct[PARM_DECL][TS_PARM_DECL] = 1;
288 tree_contains_struct[LABEL_DECL][TS_LABEL_DECL] = 1;
289 tree_contains_struct[RESULT_DECL][TS_RESULT_DECL] = 1;
290 tree_contains_struct[CONST_DECL][TS_CONST_DECL] = 1;
291 tree_contains_struct[TYPE_DECL][TS_TYPE_DECL] = 1;
292 tree_contains_struct[FUNCTION_DECL][TS_FUNCTION_DECL] = 1;
294 lang_hooks.init_ts ();
298 /* The name of the object as the assembler will see it (but before any
299 translations made by ASM_OUTPUT_LABELREF). Often this is the same
300 as DECL_NAME. It is an IDENTIFIER_NODE. */
301 tree
302 decl_assembler_name (tree decl)
304 if (!DECL_ASSEMBLER_NAME_SET_P (decl))
305 lang_hooks.set_decl_assembler_name (decl);
306 return DECL_WITH_VIS_CHECK (decl)->decl_with_vis.assembler_name;
309 /* Compute the number of bytes occupied by a tree with code CODE.
310 This function cannot be used for TREE_VEC, PHI_NODE, or STRING_CST
311 codes, which are of variable length. */
312 size_t
313 tree_code_size (enum tree_code code)
315 switch (TREE_CODE_CLASS (code))
317 case tcc_declaration: /* A decl node */
319 switch (code)
321 case FIELD_DECL:
322 return sizeof (struct tree_field_decl);
323 case PARM_DECL:
324 return sizeof (struct tree_parm_decl);
325 case VAR_DECL:
326 return sizeof (struct tree_var_decl);
327 case LABEL_DECL:
328 return sizeof (struct tree_label_decl);
329 case RESULT_DECL:
330 return sizeof (struct tree_result_decl);
331 case CONST_DECL:
332 return sizeof (struct tree_const_decl);
333 case TYPE_DECL:
334 return sizeof (struct tree_type_decl);
335 case FUNCTION_DECL:
336 return sizeof (struct tree_function_decl);
337 case NAME_MEMORY_TAG:
338 case SYMBOL_MEMORY_TAG:
339 return sizeof (struct tree_memory_tag);
340 case STRUCT_FIELD_TAG:
341 return sizeof (struct tree_struct_field_tag);
342 default:
343 return sizeof (struct tree_decl_non_common);
347 case tcc_type: /* a type node */
348 return sizeof (struct tree_type);
350 case tcc_reference: /* a reference */
351 case tcc_expression: /* an expression */
352 case tcc_statement: /* an expression with side effects */
353 case tcc_comparison: /* a comparison expression */
354 case tcc_unary: /* a unary arithmetic expression */
355 case tcc_binary: /* a binary arithmetic expression */
356 return (sizeof (struct tree_exp)
357 + (TREE_CODE_LENGTH (code) - 1) * sizeof (char *));
359 case tcc_constant: /* a constant */
360 switch (code)
362 case INTEGER_CST: return sizeof (struct tree_int_cst);
363 case REAL_CST: return sizeof (struct tree_real_cst);
364 case COMPLEX_CST: return sizeof (struct tree_complex);
365 case VECTOR_CST: return sizeof (struct tree_vector);
366 case STRING_CST: gcc_unreachable ();
367 default:
368 return lang_hooks.tree_size (code);
371 case tcc_exceptional: /* something random, like an identifier. */
372 switch (code)
374 case IDENTIFIER_NODE: return lang_hooks.identifier_size;
375 case TREE_LIST: return sizeof (struct tree_list);
377 case ERROR_MARK:
378 case PLACEHOLDER_EXPR: return sizeof (struct tree_common);
380 case TREE_VEC:
381 case OMP_CLAUSE:
382 case PHI_NODE: gcc_unreachable ();
384 case SSA_NAME: return sizeof (struct tree_ssa_name);
386 case STATEMENT_LIST: return sizeof (struct tree_statement_list);
387 case BLOCK: return sizeof (struct tree_block);
388 case VALUE_HANDLE: return sizeof (struct tree_value_handle);
389 case CONSTRUCTOR: return sizeof (struct tree_constructor);
391 default:
392 return lang_hooks.tree_size (code);
395 default:
396 gcc_unreachable ();
400 /* Compute the number of bytes occupied by NODE. This routine only
401 looks at TREE_CODE, except for PHI_NODE and TREE_VEC nodes. */
402 size_t
403 tree_size (tree node)
405 enum tree_code code = TREE_CODE (node);
406 switch (code)
408 case PHI_NODE:
409 return (sizeof (struct tree_phi_node)
410 + (PHI_ARG_CAPACITY (node) - 1) * sizeof (struct phi_arg_d));
412 case TREE_BINFO:
413 return (offsetof (struct tree_binfo, base_binfos)
414 + VEC_embedded_size (tree, BINFO_N_BASE_BINFOS (node)));
416 case TREE_VEC:
417 return (sizeof (struct tree_vec)
418 + (TREE_VEC_LENGTH (node) - 1) * sizeof(char *));
420 case STRING_CST:
421 return TREE_STRING_LENGTH (node) + offsetof (struct tree_string, str) + 1;
423 case OMP_CLAUSE:
424 return (sizeof (struct tree_omp_clause)
425 + (omp_clause_num_ops[OMP_CLAUSE_CODE (node)] - 1)
426 * sizeof (tree));
428 default:
429 return tree_code_size (code);
433 /* Return a newly allocated node of code CODE. For decl and type
434 nodes, some other fields are initialized. The rest of the node is
435 initialized to zero. This function cannot be used for PHI_NODE,
436 TREE_VEC or OMP_CLAUSE nodes, which is enforced by asserts in
437 tree_code_size.
439 Achoo! I got a code in the node. */
441 tree
442 make_node_stat (enum tree_code code MEM_STAT_DECL)
444 tree t;
445 enum tree_code_class type = TREE_CODE_CLASS (code);
446 size_t length = tree_code_size (code);
447 #ifdef GATHER_STATISTICS
448 tree_node_kind kind;
450 switch (type)
452 case tcc_declaration: /* A decl node */
453 kind = d_kind;
454 break;
456 case tcc_type: /* a type node */
457 kind = t_kind;
458 break;
460 case tcc_statement: /* an expression with side effects */
461 kind = s_kind;
462 break;
464 case tcc_reference: /* a reference */
465 kind = r_kind;
466 break;
468 case tcc_expression: /* an expression */
469 case tcc_comparison: /* a comparison expression */
470 case tcc_unary: /* a unary arithmetic expression */
471 case tcc_binary: /* a binary arithmetic expression */
472 kind = e_kind;
473 break;
475 case tcc_constant: /* a constant */
476 kind = c_kind;
477 break;
479 case tcc_exceptional: /* something random, like an identifier. */
480 switch (code)
482 case IDENTIFIER_NODE:
483 kind = id_kind;
484 break;
486 case TREE_VEC:
487 kind = vec_kind;
488 break;
490 case TREE_BINFO:
491 kind = binfo_kind;
492 break;
494 case PHI_NODE:
495 kind = phi_kind;
496 break;
498 case SSA_NAME:
499 kind = ssa_name_kind;
500 break;
502 case BLOCK:
503 kind = b_kind;
504 break;
506 case CONSTRUCTOR:
507 kind = constr_kind;
508 break;
510 default:
511 kind = x_kind;
512 break;
514 break;
516 default:
517 gcc_unreachable ();
520 tree_node_counts[(int) kind]++;
521 tree_node_sizes[(int) kind] += length;
522 #endif
524 if (code == IDENTIFIER_NODE)
525 t = ggc_alloc_zone_pass_stat (length, &tree_id_zone);
526 else
527 t = ggc_alloc_zone_pass_stat (length, &tree_zone);
529 memset (t, 0, length);
531 TREE_SET_CODE (t, code);
533 switch (type)
535 case tcc_statement:
536 TREE_SIDE_EFFECTS (t) = 1;
537 break;
539 case tcc_declaration:
540 if (CODE_CONTAINS_STRUCT (code, TS_DECL_WITH_VIS))
541 DECL_IN_SYSTEM_HEADER (t) = in_system_header;
542 if (CODE_CONTAINS_STRUCT (code, TS_DECL_COMMON))
544 if (code != FUNCTION_DECL)
545 DECL_ALIGN (t) = 1;
546 DECL_USER_ALIGN (t) = 0;
547 /* We have not yet computed the alias set for this declaration. */
548 DECL_POINTER_ALIAS_SET (t) = -1;
550 DECL_SOURCE_LOCATION (t) = input_location;
551 DECL_UID (t) = next_decl_uid++;
553 break;
555 case tcc_type:
556 TYPE_UID (t) = next_type_uid++;
557 TYPE_ALIGN (t) = BITS_PER_UNIT;
558 TYPE_USER_ALIGN (t) = 0;
559 TYPE_MAIN_VARIANT (t) = t;
561 /* Default to no attributes for type, but let target change that. */
562 TYPE_ATTRIBUTES (t) = NULL_TREE;
563 targetm.set_default_type_attributes (t);
565 /* We have not yet computed the alias set for this type. */
566 TYPE_ALIAS_SET (t) = -1;
567 break;
569 case tcc_constant:
570 TREE_CONSTANT (t) = 1;
571 TREE_INVARIANT (t) = 1;
572 break;
574 case tcc_expression:
575 switch (code)
577 case INIT_EXPR:
578 case MODIFY_EXPR:
579 case VA_ARG_EXPR:
580 case PREDECREMENT_EXPR:
581 case PREINCREMENT_EXPR:
582 case POSTDECREMENT_EXPR:
583 case POSTINCREMENT_EXPR:
584 /* All of these have side-effects, no matter what their
585 operands are. */
586 TREE_SIDE_EFFECTS (t) = 1;
587 break;
589 default:
590 break;
592 break;
594 default:
595 /* Other classes need no special treatment. */
596 break;
599 return t;
602 /* Return a new node with the same contents as NODE except that its
603 TREE_CHAIN is zero and it has a fresh uid. */
605 tree
606 copy_node_stat (tree node MEM_STAT_DECL)
608 tree t;
609 enum tree_code code = TREE_CODE (node);
610 size_t length;
612 gcc_assert (code != STATEMENT_LIST);
614 length = tree_size (node);
615 t = ggc_alloc_zone_pass_stat (length, &tree_zone);
616 memcpy (t, node, length);
618 TREE_CHAIN (t) = 0;
619 TREE_ASM_WRITTEN (t) = 0;
620 TREE_VISITED (t) = 0;
621 t->common.ann = 0;
623 if (TREE_CODE_CLASS (code) == tcc_declaration)
625 DECL_UID (t) = next_decl_uid++;
626 if ((TREE_CODE (node) == PARM_DECL || TREE_CODE (node) == VAR_DECL)
627 && DECL_HAS_VALUE_EXPR_P (node))
629 SET_DECL_VALUE_EXPR (t, DECL_VALUE_EXPR (node));
630 DECL_HAS_VALUE_EXPR_P (t) = 1;
632 if (TREE_CODE (node) == VAR_DECL && DECL_HAS_INIT_PRIORITY_P (node))
634 SET_DECL_INIT_PRIORITY (t, DECL_INIT_PRIORITY (node));
635 DECL_HAS_INIT_PRIORITY_P (t) = 1;
637 if (TREE_CODE (node) == VAR_DECL && DECL_BASED_ON_RESTRICT_P (node))
639 SET_DECL_RESTRICT_BASE (t, DECL_GET_RESTRICT_BASE (node));
640 DECL_BASED_ON_RESTRICT_P (t) = 1;
643 else if (TREE_CODE_CLASS (code) == tcc_type)
645 TYPE_UID (t) = next_type_uid++;
646 /* The following is so that the debug code for
647 the copy is different from the original type.
648 The two statements usually duplicate each other
649 (because they clear fields of the same union),
650 but the optimizer should catch that. */
651 TYPE_SYMTAB_POINTER (t) = 0;
652 TYPE_SYMTAB_ADDRESS (t) = 0;
654 /* Do not copy the values cache. */
655 if (TYPE_CACHED_VALUES_P(t))
657 TYPE_CACHED_VALUES_P (t) = 0;
658 TYPE_CACHED_VALUES (t) = NULL_TREE;
662 return t;
665 /* Return a copy of a chain of nodes, chained through the TREE_CHAIN field.
666 For example, this can copy a list made of TREE_LIST nodes. */
668 tree
669 copy_list (tree list)
671 tree head;
672 tree prev, next;
674 if (list == 0)
675 return 0;
677 head = prev = copy_node (list);
678 next = TREE_CHAIN (list);
679 while (next)
681 TREE_CHAIN (prev) = copy_node (next);
682 prev = TREE_CHAIN (prev);
683 next = TREE_CHAIN (next);
685 return head;
689 /* Create an INT_CST node with a LOW value sign extended. */
691 tree
692 build_int_cst (tree type, HOST_WIDE_INT low)
694 return build_int_cst_wide (type, low, low < 0 ? -1 : 0);
697 /* Create an INT_CST node with a LOW value zero extended. */
699 tree
700 build_int_cstu (tree type, unsigned HOST_WIDE_INT low)
702 return build_int_cst_wide (type, low, 0);
705 /* Create an INT_CST node with a LOW value in TYPE. The value is sign extended
706 if it is negative. This function is similar to build_int_cst, but
707 the extra bits outside of the type precision are cleared. Constants
708 with these extra bits may confuse the fold so that it detects overflows
709 even in cases when they do not occur, and in general should be avoided.
710 We cannot however make this a default behavior of build_int_cst without
711 more intrusive changes, since there are parts of gcc that rely on the extra
712 precision of the integer constants. */
714 tree
715 build_int_cst_type (tree type, HOST_WIDE_INT low)
717 unsigned HOST_WIDE_INT val = (unsigned HOST_WIDE_INT) low;
718 unsigned HOST_WIDE_INT hi, mask;
719 unsigned bits;
720 bool signed_p;
721 bool negative;
723 if (!type)
724 type = integer_type_node;
726 bits = TYPE_PRECISION (type);
727 signed_p = !TYPE_UNSIGNED (type);
729 if (bits >= HOST_BITS_PER_WIDE_INT)
730 negative = (low < 0);
731 else
733 /* If the sign bit is inside precision of LOW, use it to determine
734 the sign of the constant. */
735 negative = ((val >> (bits - 1)) & 1) != 0;
737 /* Mask out the bits outside of the precision of the constant. */
738 mask = (((unsigned HOST_WIDE_INT) 2) << (bits - 1)) - 1;
740 if (signed_p && negative)
741 val |= ~mask;
742 else
743 val &= mask;
746 /* Determine the high bits. */
747 hi = (negative ? ~(unsigned HOST_WIDE_INT) 0 : 0);
749 /* For unsigned type we need to mask out the bits outside of the type
750 precision. */
751 if (!signed_p)
753 if (bits <= HOST_BITS_PER_WIDE_INT)
754 hi = 0;
755 else
757 bits -= HOST_BITS_PER_WIDE_INT;
758 mask = (((unsigned HOST_WIDE_INT) 2) << (bits - 1)) - 1;
759 hi &= mask;
763 return build_int_cst_wide (type, val, hi);
766 /* These are the hash table functions for the hash table of INTEGER_CST
767 nodes of a sizetype. */
769 /* Return the hash code code X, an INTEGER_CST. */
771 static hashval_t
772 int_cst_hash_hash (const void *x)
774 tree t = (tree) x;
776 return (TREE_INT_CST_HIGH (t) ^ TREE_INT_CST_LOW (t)
777 ^ htab_hash_pointer (TREE_TYPE (t)));
780 /* Return nonzero if the value represented by *X (an INTEGER_CST tree node)
781 is the same as that given by *Y, which is the same. */
783 static int
784 int_cst_hash_eq (const void *x, const void *y)
786 tree xt = (tree) x;
787 tree yt = (tree) y;
789 return (TREE_TYPE (xt) == TREE_TYPE (yt)
790 && TREE_INT_CST_HIGH (xt) == TREE_INT_CST_HIGH (yt)
791 && TREE_INT_CST_LOW (xt) == TREE_INT_CST_LOW (yt));
794 /* Create an INT_CST node of TYPE and value HI:LOW. If TYPE is NULL,
795 integer_type_node is used. The returned node is always shared.
796 For small integers we use a per-type vector cache, for larger ones
797 we use a single hash table. */
799 tree
800 build_int_cst_wide (tree type, unsigned HOST_WIDE_INT low, HOST_WIDE_INT hi)
802 tree t;
803 int ix = -1;
804 int limit = 0;
806 if (!type)
807 type = integer_type_node;
809 switch (TREE_CODE (type))
811 case POINTER_TYPE:
812 case REFERENCE_TYPE:
813 /* Cache NULL pointer. */
814 if (!hi && !low)
816 limit = 1;
817 ix = 0;
819 break;
821 case BOOLEAN_TYPE:
822 /* Cache false or true. */
823 limit = 2;
824 if (!hi && low < 2)
825 ix = low;
826 break;
828 case INTEGER_TYPE:
829 case OFFSET_TYPE:
830 if (TYPE_UNSIGNED (type))
832 /* Cache 0..N */
833 limit = INTEGER_SHARE_LIMIT;
834 if (!hi && low < (unsigned HOST_WIDE_INT)INTEGER_SHARE_LIMIT)
835 ix = low;
837 else
839 /* Cache -1..N */
840 limit = INTEGER_SHARE_LIMIT + 1;
841 if (!hi && low < (unsigned HOST_WIDE_INT)INTEGER_SHARE_LIMIT)
842 ix = low + 1;
843 else if (hi == -1 && low == -(unsigned HOST_WIDE_INT)1)
844 ix = 0;
846 break;
847 default:
848 break;
851 if (ix >= 0)
853 /* Look for it in the type's vector of small shared ints. */
854 if (!TYPE_CACHED_VALUES_P (type))
856 TYPE_CACHED_VALUES_P (type) = 1;
857 TYPE_CACHED_VALUES (type) = make_tree_vec (limit);
860 t = TREE_VEC_ELT (TYPE_CACHED_VALUES (type), ix);
861 if (t)
863 /* Make sure no one is clobbering the shared constant. */
864 gcc_assert (TREE_TYPE (t) == type);
865 gcc_assert (TREE_INT_CST_LOW (t) == low);
866 gcc_assert (TREE_INT_CST_HIGH (t) == hi);
868 else
870 /* Create a new shared int. */
871 t = make_node (INTEGER_CST);
873 TREE_INT_CST_LOW (t) = low;
874 TREE_INT_CST_HIGH (t) = hi;
875 TREE_TYPE (t) = type;
877 TREE_VEC_ELT (TYPE_CACHED_VALUES (type), ix) = t;
880 else
882 /* Use the cache of larger shared ints. */
883 void **slot;
885 TREE_INT_CST_LOW (int_cst_node) = low;
886 TREE_INT_CST_HIGH (int_cst_node) = hi;
887 TREE_TYPE (int_cst_node) = type;
889 slot = htab_find_slot (int_cst_hash_table, int_cst_node, INSERT);
890 t = *slot;
891 if (!t)
893 /* Insert this one into the hash table. */
894 t = int_cst_node;
895 *slot = t;
896 /* Make a new node for next time round. */
897 int_cst_node = make_node (INTEGER_CST);
901 return t;
904 /* Builds an integer constant in TYPE such that lowest BITS bits are ones
905 and the rest are zeros. */
907 tree
908 build_low_bits_mask (tree type, unsigned bits)
910 unsigned HOST_WIDE_INT low;
911 HOST_WIDE_INT high;
912 unsigned HOST_WIDE_INT all_ones = ~(unsigned HOST_WIDE_INT) 0;
914 gcc_assert (bits <= TYPE_PRECISION (type));
916 if (bits == TYPE_PRECISION (type)
917 && !TYPE_UNSIGNED (type))
919 /* Sign extended all-ones mask. */
920 low = all_ones;
921 high = -1;
923 else if (bits <= HOST_BITS_PER_WIDE_INT)
925 low = all_ones >> (HOST_BITS_PER_WIDE_INT - bits);
926 high = 0;
928 else
930 bits -= HOST_BITS_PER_WIDE_INT;
931 low = all_ones;
932 high = all_ones >> (HOST_BITS_PER_WIDE_INT - bits);
935 return build_int_cst_wide (type, low, high);
938 /* Checks that X is integer constant that can be expressed in (unsigned)
939 HOST_WIDE_INT without loss of precision. */
941 bool
942 cst_and_fits_in_hwi (tree x)
944 if (TREE_CODE (x) != INTEGER_CST)
945 return false;
947 if (TYPE_PRECISION (TREE_TYPE (x)) > HOST_BITS_PER_WIDE_INT)
948 return false;
950 return (TREE_INT_CST_HIGH (x) == 0
951 || TREE_INT_CST_HIGH (x) == -1);
954 /* Return a new VECTOR_CST node whose type is TYPE and whose values
955 are in a list pointed to by VALS. */
957 tree
958 build_vector (tree type, tree vals)
960 tree v = make_node (VECTOR_CST);
961 int over1 = 0, over2 = 0;
962 tree link;
964 TREE_VECTOR_CST_ELTS (v) = vals;
965 TREE_TYPE (v) = type;
967 /* Iterate through elements and check for overflow. */
968 for (link = vals; link; link = TREE_CHAIN (link))
970 tree value = TREE_VALUE (link);
972 over1 |= TREE_OVERFLOW (value);
973 over2 |= TREE_CONSTANT_OVERFLOW (value);
976 TREE_OVERFLOW (v) = over1;
977 TREE_CONSTANT_OVERFLOW (v) = over2;
979 return v;
982 /* Return a new VECTOR_CST node whose type is TYPE and whose values
983 are extracted from V, a vector of CONSTRUCTOR_ELT. */
985 tree
986 build_vector_from_ctor (tree type, VEC(constructor_elt,gc) *v)
988 tree list = NULL_TREE;
989 unsigned HOST_WIDE_INT idx;
990 tree value;
992 FOR_EACH_CONSTRUCTOR_VALUE (v, idx, value)
993 list = tree_cons (NULL_TREE, value, list);
994 return build_vector (type, nreverse (list));
997 /* Return a new CONSTRUCTOR node whose type is TYPE and whose values
998 are in the VEC pointed to by VALS. */
999 tree
1000 build_constructor (tree type, VEC(constructor_elt,gc) *vals)
1002 tree c = make_node (CONSTRUCTOR);
1003 TREE_TYPE (c) = type;
1004 CONSTRUCTOR_ELTS (c) = vals;
1005 return c;
1008 /* Build a CONSTRUCTOR node made of a single initializer, with the specified
1009 INDEX and VALUE. */
1010 tree
1011 build_constructor_single (tree type, tree index, tree value)
1013 VEC(constructor_elt,gc) *v;
1014 constructor_elt *elt;
1015 tree t;
1017 v = VEC_alloc (constructor_elt, gc, 1);
1018 elt = VEC_quick_push (constructor_elt, v, NULL);
1019 elt->index = index;
1020 elt->value = value;
1022 t = build_constructor (type, v);
1023 TREE_CONSTANT (t) = TREE_CONSTANT (value);
1024 return t;
1028 /* Return a new CONSTRUCTOR node whose type is TYPE and whose values
1029 are in a list pointed to by VALS. */
1030 tree
1031 build_constructor_from_list (tree type, tree vals)
1033 tree t, val;
1034 VEC(constructor_elt,gc) *v = NULL;
1035 bool constant_p = true;
1037 if (vals)
1039 v = VEC_alloc (constructor_elt, gc, list_length (vals));
1040 for (t = vals; t; t = TREE_CHAIN (t))
1042 constructor_elt *elt = VEC_quick_push (constructor_elt, v, NULL);
1043 val = TREE_VALUE (t);
1044 elt->index = TREE_PURPOSE (t);
1045 elt->value = val;
1046 if (!TREE_CONSTANT (val))
1047 constant_p = false;
1051 t = build_constructor (type, v);
1052 TREE_CONSTANT (t) = constant_p;
1053 return t;
1057 /* Return a new REAL_CST node whose type is TYPE and value is D. */
1059 tree
1060 build_real (tree type, REAL_VALUE_TYPE d)
1062 tree v;
1063 REAL_VALUE_TYPE *dp;
1064 int overflow = 0;
1066 /* ??? Used to check for overflow here via CHECK_FLOAT_TYPE.
1067 Consider doing it via real_convert now. */
1069 v = make_node (REAL_CST);
1070 dp = ggc_alloc (sizeof (REAL_VALUE_TYPE));
1071 memcpy (dp, &d, sizeof (REAL_VALUE_TYPE));
1073 TREE_TYPE (v) = type;
1074 TREE_REAL_CST_PTR (v) = dp;
1075 TREE_OVERFLOW (v) = TREE_CONSTANT_OVERFLOW (v) = overflow;
1076 return v;
1079 /* Return a new REAL_CST node whose type is TYPE
1080 and whose value is the integer value of the INTEGER_CST node I. */
1082 REAL_VALUE_TYPE
1083 real_value_from_int_cst (tree type, tree i)
1085 REAL_VALUE_TYPE d;
1087 /* Clear all bits of the real value type so that we can later do
1088 bitwise comparisons to see if two values are the same. */
1089 memset (&d, 0, sizeof d);
1091 real_from_integer (&d, type ? TYPE_MODE (type) : VOIDmode,
1092 TREE_INT_CST_LOW (i), TREE_INT_CST_HIGH (i),
1093 TYPE_UNSIGNED (TREE_TYPE (i)));
1094 return d;
1097 /* Given a tree representing an integer constant I, return a tree
1098 representing the same value as a floating-point constant of type TYPE. */
1100 tree
1101 build_real_from_int_cst (tree type, tree i)
1103 tree v;
1104 int overflow = TREE_OVERFLOW (i);
1106 v = build_real (type, real_value_from_int_cst (type, i));
1108 TREE_OVERFLOW (v) |= overflow;
1109 TREE_CONSTANT_OVERFLOW (v) |= overflow;
1110 return v;
1113 /* Return a newly constructed STRING_CST node whose value is
1114 the LEN characters at STR.
1115 The TREE_TYPE is not initialized. */
1117 tree
1118 build_string (int len, const char *str)
1120 tree s;
1121 size_t length;
1123 /* Do not waste bytes provided by padding of struct tree_string. */
1124 length = len + offsetof (struct tree_string, str) + 1;
1126 #ifdef GATHER_STATISTICS
1127 tree_node_counts[(int) c_kind]++;
1128 tree_node_sizes[(int) c_kind] += length;
1129 #endif
1131 s = ggc_alloc_tree (length);
1133 memset (s, 0, sizeof (struct tree_common));
1134 TREE_SET_CODE (s, STRING_CST);
1135 TREE_CONSTANT (s) = 1;
1136 TREE_INVARIANT (s) = 1;
1137 TREE_STRING_LENGTH (s) = len;
1138 memcpy ((char *) TREE_STRING_POINTER (s), str, len);
1139 ((char *) TREE_STRING_POINTER (s))[len] = '\0';
1141 return s;
1144 /* Return a newly constructed COMPLEX_CST node whose value is
1145 specified by the real and imaginary parts REAL and IMAG.
1146 Both REAL and IMAG should be constant nodes. TYPE, if specified,
1147 will be the type of the COMPLEX_CST; otherwise a new type will be made. */
1149 tree
1150 build_complex (tree type, tree real, tree imag)
1152 tree t = make_node (COMPLEX_CST);
1154 TREE_REALPART (t) = real;
1155 TREE_IMAGPART (t) = imag;
1156 TREE_TYPE (t) = type ? type : build_complex_type (TREE_TYPE (real));
1157 TREE_OVERFLOW (t) = TREE_OVERFLOW (real) | TREE_OVERFLOW (imag);
1158 TREE_CONSTANT_OVERFLOW (t)
1159 = TREE_CONSTANT_OVERFLOW (real) | TREE_CONSTANT_OVERFLOW (imag);
1160 return t;
1163 /* Return a constant of arithmetic type TYPE which is the
1164 multiplicative identity of the set TYPE. */
1166 tree
1167 build_one_cst (tree type)
1169 switch (TREE_CODE (type))
1171 case INTEGER_TYPE: case ENUMERAL_TYPE: case BOOLEAN_TYPE:
1172 case POINTER_TYPE: case REFERENCE_TYPE:
1173 case OFFSET_TYPE:
1174 return build_int_cst (type, 1);
1176 case REAL_TYPE:
1177 return build_real (type, dconst1);
1179 case VECTOR_TYPE:
1181 tree scalar, cst;
1182 int i;
1184 scalar = build_one_cst (TREE_TYPE (type));
1186 /* Create 'vect_cst_ = {cst,cst,...,cst}' */
1187 cst = NULL_TREE;
1188 for (i = TYPE_VECTOR_SUBPARTS (type); --i >= 0; )
1189 cst = tree_cons (NULL_TREE, scalar, cst);
1191 return build_vector (type, cst);
1194 case COMPLEX_TYPE:
1195 return build_complex (type,
1196 build_one_cst (TREE_TYPE (type)),
1197 fold_convert (TREE_TYPE (type), integer_zero_node));
1199 default:
1200 gcc_unreachable ();
1204 /* Build a BINFO with LEN language slots. */
1206 tree
1207 make_tree_binfo_stat (unsigned base_binfos MEM_STAT_DECL)
1209 tree t;
1210 size_t length = (offsetof (struct tree_binfo, base_binfos)
1211 + VEC_embedded_size (tree, base_binfos));
1213 #ifdef GATHER_STATISTICS
1214 tree_node_counts[(int) binfo_kind]++;
1215 tree_node_sizes[(int) binfo_kind] += length;
1216 #endif
1218 t = ggc_alloc_zone_pass_stat (length, &tree_zone);
1220 memset (t, 0, offsetof (struct tree_binfo, base_binfos));
1222 TREE_SET_CODE (t, TREE_BINFO);
1224 VEC_embedded_init (tree, BINFO_BASE_BINFOS (t), base_binfos);
1226 return t;
1230 /* Build a newly constructed TREE_VEC node of length LEN. */
1232 tree
1233 make_tree_vec_stat (int len MEM_STAT_DECL)
1235 tree t;
1236 int length = (len - 1) * sizeof (tree) + sizeof (struct tree_vec);
1238 #ifdef GATHER_STATISTICS
1239 tree_node_counts[(int) vec_kind]++;
1240 tree_node_sizes[(int) vec_kind] += length;
1241 #endif
1243 t = ggc_alloc_zone_pass_stat (length, &tree_zone);
1245 memset (t, 0, length);
1247 TREE_SET_CODE (t, TREE_VEC);
1248 TREE_VEC_LENGTH (t) = len;
1250 return t;
1253 /* Return 1 if EXPR is the integer constant zero or a complex constant
1254 of zero. */
1257 integer_zerop (tree expr)
1259 STRIP_NOPS (expr);
1261 return ((TREE_CODE (expr) == INTEGER_CST
1262 && TREE_INT_CST_LOW (expr) == 0
1263 && TREE_INT_CST_HIGH (expr) == 0)
1264 || (TREE_CODE (expr) == COMPLEX_CST
1265 && integer_zerop (TREE_REALPART (expr))
1266 && integer_zerop (TREE_IMAGPART (expr))));
1269 /* Return 1 if EXPR is the integer constant one or the corresponding
1270 complex constant. */
1273 integer_onep (tree expr)
1275 STRIP_NOPS (expr);
1277 return ((TREE_CODE (expr) == INTEGER_CST
1278 && TREE_INT_CST_LOW (expr) == 1
1279 && TREE_INT_CST_HIGH (expr) == 0)
1280 || (TREE_CODE (expr) == COMPLEX_CST
1281 && integer_onep (TREE_REALPART (expr))
1282 && integer_zerop (TREE_IMAGPART (expr))));
1285 /* Return 1 if EXPR is an integer containing all 1's in as much precision as
1286 it contains. Likewise for the corresponding complex constant. */
1289 integer_all_onesp (tree expr)
1291 int prec;
1292 int uns;
1294 STRIP_NOPS (expr);
1296 if (TREE_CODE (expr) == COMPLEX_CST
1297 && integer_all_onesp (TREE_REALPART (expr))
1298 && integer_zerop (TREE_IMAGPART (expr)))
1299 return 1;
1301 else if (TREE_CODE (expr) != INTEGER_CST)
1302 return 0;
1304 uns = TYPE_UNSIGNED (TREE_TYPE (expr));
1305 if (TREE_INT_CST_LOW (expr) == ~(unsigned HOST_WIDE_INT) 0
1306 && TREE_INT_CST_HIGH (expr) == -1)
1307 return 1;
1308 if (!uns)
1309 return 0;
1311 /* Note that using TYPE_PRECISION here is wrong. We care about the
1312 actual bits, not the (arbitrary) range of the type. */
1313 prec = GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (expr)));
1314 if (prec >= HOST_BITS_PER_WIDE_INT)
1316 HOST_WIDE_INT high_value;
1317 int shift_amount;
1319 shift_amount = prec - HOST_BITS_PER_WIDE_INT;
1321 /* Can not handle precisions greater than twice the host int size. */
1322 gcc_assert (shift_amount <= HOST_BITS_PER_WIDE_INT);
1323 if (shift_amount == HOST_BITS_PER_WIDE_INT)
1324 /* Shifting by the host word size is undefined according to the ANSI
1325 standard, so we must handle this as a special case. */
1326 high_value = -1;
1327 else
1328 high_value = ((HOST_WIDE_INT) 1 << shift_amount) - 1;
1330 return (TREE_INT_CST_LOW (expr) == ~(unsigned HOST_WIDE_INT) 0
1331 && TREE_INT_CST_HIGH (expr) == high_value);
1333 else
1334 return TREE_INT_CST_LOW (expr) == ((unsigned HOST_WIDE_INT) 1 << prec) - 1;
1337 /* Return 1 if EXPR is an integer constant that is a power of 2 (i.e., has only
1338 one bit on). */
1341 integer_pow2p (tree expr)
1343 int prec;
1344 HOST_WIDE_INT high, low;
1346 STRIP_NOPS (expr);
1348 if (TREE_CODE (expr) == COMPLEX_CST
1349 && integer_pow2p (TREE_REALPART (expr))
1350 && integer_zerop (TREE_IMAGPART (expr)))
1351 return 1;
1353 if (TREE_CODE (expr) != INTEGER_CST)
1354 return 0;
1356 prec = (POINTER_TYPE_P (TREE_TYPE (expr))
1357 ? POINTER_SIZE : TYPE_PRECISION (TREE_TYPE (expr)));
1358 high = TREE_INT_CST_HIGH (expr);
1359 low = TREE_INT_CST_LOW (expr);
1361 /* First clear all bits that are beyond the type's precision in case
1362 we've been sign extended. */
1364 if (prec == 2 * HOST_BITS_PER_WIDE_INT)
1366 else if (prec > HOST_BITS_PER_WIDE_INT)
1367 high &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
1368 else
1370 high = 0;
1371 if (prec < HOST_BITS_PER_WIDE_INT)
1372 low &= ~((HOST_WIDE_INT) (-1) << prec);
1375 if (high == 0 && low == 0)
1376 return 0;
1378 return ((high == 0 && (low & (low - 1)) == 0)
1379 || (low == 0 && (high & (high - 1)) == 0));
1382 /* Return 1 if EXPR is an integer constant other than zero or a
1383 complex constant other than zero. */
1386 integer_nonzerop (tree expr)
1388 STRIP_NOPS (expr);
1390 return ((TREE_CODE (expr) == INTEGER_CST
1391 && (TREE_INT_CST_LOW (expr) != 0
1392 || TREE_INT_CST_HIGH (expr) != 0))
1393 || (TREE_CODE (expr) == COMPLEX_CST
1394 && (integer_nonzerop (TREE_REALPART (expr))
1395 || integer_nonzerop (TREE_IMAGPART (expr)))));
1398 /* Return the power of two represented by a tree node known to be a
1399 power of two. */
1402 tree_log2 (tree expr)
1404 int prec;
1405 HOST_WIDE_INT high, low;
1407 STRIP_NOPS (expr);
1409 if (TREE_CODE (expr) == COMPLEX_CST)
1410 return tree_log2 (TREE_REALPART (expr));
1412 prec = (POINTER_TYPE_P (TREE_TYPE (expr))
1413 ? POINTER_SIZE : TYPE_PRECISION (TREE_TYPE (expr)));
1415 high = TREE_INT_CST_HIGH (expr);
1416 low = TREE_INT_CST_LOW (expr);
1418 /* First clear all bits that are beyond the type's precision in case
1419 we've been sign extended. */
1421 if (prec == 2 * HOST_BITS_PER_WIDE_INT)
1423 else if (prec > HOST_BITS_PER_WIDE_INT)
1424 high &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
1425 else
1427 high = 0;
1428 if (prec < HOST_BITS_PER_WIDE_INT)
1429 low &= ~((HOST_WIDE_INT) (-1) << prec);
1432 return (high != 0 ? HOST_BITS_PER_WIDE_INT + exact_log2 (high)
1433 : exact_log2 (low));
1436 /* Similar, but return the largest integer Y such that 2 ** Y is less
1437 than or equal to EXPR. */
1440 tree_floor_log2 (tree expr)
1442 int prec;
1443 HOST_WIDE_INT high, low;
1445 STRIP_NOPS (expr);
1447 if (TREE_CODE (expr) == COMPLEX_CST)
1448 return tree_log2 (TREE_REALPART (expr));
1450 prec = (POINTER_TYPE_P (TREE_TYPE (expr))
1451 ? POINTER_SIZE : TYPE_PRECISION (TREE_TYPE (expr)));
1453 high = TREE_INT_CST_HIGH (expr);
1454 low = TREE_INT_CST_LOW (expr);
1456 /* First clear all bits that are beyond the type's precision in case
1457 we've been sign extended. Ignore if type's precision hasn't been set
1458 since what we are doing is setting it. */
1460 if (prec == 2 * HOST_BITS_PER_WIDE_INT || prec == 0)
1462 else if (prec > HOST_BITS_PER_WIDE_INT)
1463 high &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
1464 else
1466 high = 0;
1467 if (prec < HOST_BITS_PER_WIDE_INT)
1468 low &= ~((HOST_WIDE_INT) (-1) << prec);
1471 return (high != 0 ? HOST_BITS_PER_WIDE_INT + floor_log2 (high)
1472 : floor_log2 (low));
1475 /* Return 1 if EXPR is the real constant zero. */
1478 real_zerop (tree expr)
1480 STRIP_NOPS (expr);
1482 return ((TREE_CODE (expr) == REAL_CST
1483 && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconst0))
1484 || (TREE_CODE (expr) == COMPLEX_CST
1485 && real_zerop (TREE_REALPART (expr))
1486 && real_zerop (TREE_IMAGPART (expr))));
1489 /* Return 1 if EXPR is the real constant one in real or complex form. */
1492 real_onep (tree expr)
1494 STRIP_NOPS (expr);
1496 return ((TREE_CODE (expr) == REAL_CST
1497 && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconst1))
1498 || (TREE_CODE (expr) == COMPLEX_CST
1499 && real_onep (TREE_REALPART (expr))
1500 && real_zerop (TREE_IMAGPART (expr))));
1503 /* Return 1 if EXPR is the real constant two. */
1506 real_twop (tree expr)
1508 STRIP_NOPS (expr);
1510 return ((TREE_CODE (expr) == REAL_CST
1511 && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconst2))
1512 || (TREE_CODE (expr) == COMPLEX_CST
1513 && real_twop (TREE_REALPART (expr))
1514 && real_zerop (TREE_IMAGPART (expr))));
1517 /* Return 1 if EXPR is the real constant minus one. */
1520 real_minus_onep (tree expr)
1522 STRIP_NOPS (expr);
1524 return ((TREE_CODE (expr) == REAL_CST
1525 && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconstm1))
1526 || (TREE_CODE (expr) == COMPLEX_CST
1527 && real_minus_onep (TREE_REALPART (expr))
1528 && real_zerop (TREE_IMAGPART (expr))));
1531 /* Nonzero if EXP is a constant or a cast of a constant. */
1534 really_constant_p (tree exp)
1536 /* This is not quite the same as STRIP_NOPS. It does more. */
1537 while (TREE_CODE (exp) == NOP_EXPR
1538 || TREE_CODE (exp) == CONVERT_EXPR
1539 || TREE_CODE (exp) == NON_LVALUE_EXPR)
1540 exp = TREE_OPERAND (exp, 0);
1541 return TREE_CONSTANT (exp);
1544 /* Return first list element whose TREE_VALUE is ELEM.
1545 Return 0 if ELEM is not in LIST. */
1547 tree
1548 value_member (tree elem, tree list)
1550 while (list)
1552 if (elem == TREE_VALUE (list))
1553 return list;
1554 list = TREE_CHAIN (list);
1556 return NULL_TREE;
1559 /* Return first list element whose TREE_PURPOSE is ELEM.
1560 Return 0 if ELEM is not in LIST. */
1562 tree
1563 purpose_member (tree elem, tree list)
1565 while (list)
1567 if (elem == TREE_PURPOSE (list))
1568 return list;
1569 list = TREE_CHAIN (list);
1571 return NULL_TREE;
1574 /* Return nonzero if ELEM is part of the chain CHAIN. */
1577 chain_member (tree elem, tree chain)
1579 while (chain)
1581 if (elem == chain)
1582 return 1;
1583 chain = TREE_CHAIN (chain);
1586 return 0;
1589 /* Return the length of a chain of nodes chained through TREE_CHAIN.
1590 We expect a null pointer to mark the end of the chain.
1591 This is the Lisp primitive `length'. */
1594 list_length (tree t)
1596 tree p = t;
1597 #ifdef ENABLE_TREE_CHECKING
1598 tree q = t;
1599 #endif
1600 int len = 0;
1602 while (p)
1604 p = TREE_CHAIN (p);
1605 #ifdef ENABLE_TREE_CHECKING
1606 if (len % 2)
1607 q = TREE_CHAIN (q);
1608 gcc_assert (p != q);
1609 #endif
1610 len++;
1613 return len;
1616 /* Returns the number of FIELD_DECLs in TYPE. */
1619 fields_length (tree type)
1621 tree t = TYPE_FIELDS (type);
1622 int count = 0;
1624 for (; t; t = TREE_CHAIN (t))
1625 if (TREE_CODE (t) == FIELD_DECL)
1626 ++count;
1628 return count;
1631 /* Concatenate two chains of nodes (chained through TREE_CHAIN)
1632 by modifying the last node in chain 1 to point to chain 2.
1633 This is the Lisp primitive `nconc'. */
1635 tree
1636 chainon (tree op1, tree op2)
1638 tree t1;
1640 if (!op1)
1641 return op2;
1642 if (!op2)
1643 return op1;
1645 for (t1 = op1; TREE_CHAIN (t1); t1 = TREE_CHAIN (t1))
1646 continue;
1647 TREE_CHAIN (t1) = op2;
1649 #ifdef ENABLE_TREE_CHECKING
1651 tree t2;
1652 for (t2 = op2; t2; t2 = TREE_CHAIN (t2))
1653 gcc_assert (t2 != t1);
1655 #endif
1657 return op1;
1660 /* Return the last node in a chain of nodes (chained through TREE_CHAIN). */
1662 tree
1663 tree_last (tree chain)
1665 tree next;
1666 if (chain)
1667 while ((next = TREE_CHAIN (chain)))
1668 chain = next;
1669 return chain;
1672 /* Reverse the order of elements in the chain T,
1673 and return the new head of the chain (old last element). */
1675 tree
1676 nreverse (tree t)
1678 tree prev = 0, decl, next;
1679 for (decl = t; decl; decl = next)
1681 next = TREE_CHAIN (decl);
1682 TREE_CHAIN (decl) = prev;
1683 prev = decl;
1685 return prev;
1688 /* Return a newly created TREE_LIST node whose
1689 purpose and value fields are PARM and VALUE. */
1691 tree
1692 build_tree_list_stat (tree parm, tree value MEM_STAT_DECL)
1694 tree t = make_node_stat (TREE_LIST PASS_MEM_STAT);
1695 TREE_PURPOSE (t) = parm;
1696 TREE_VALUE (t) = value;
1697 return t;
1700 /* Return a newly created TREE_LIST node whose
1701 purpose and value fields are PURPOSE and VALUE
1702 and whose TREE_CHAIN is CHAIN. */
1704 tree
1705 tree_cons_stat (tree purpose, tree value, tree chain MEM_STAT_DECL)
1707 tree node;
1709 node = ggc_alloc_zone_pass_stat (sizeof (struct tree_list), &tree_zone);
1711 memset (node, 0, sizeof (struct tree_common));
1713 #ifdef GATHER_STATISTICS
1714 tree_node_counts[(int) x_kind]++;
1715 tree_node_sizes[(int) x_kind] += sizeof (struct tree_list);
1716 #endif
1718 TREE_SET_CODE (node, TREE_LIST);
1719 TREE_CHAIN (node) = chain;
1720 TREE_PURPOSE (node) = purpose;
1721 TREE_VALUE (node) = value;
1722 return node;
1726 /* Return the size nominally occupied by an object of type TYPE
1727 when it resides in memory. The value is measured in units of bytes,
1728 and its data type is that normally used for type sizes
1729 (which is the first type created by make_signed_type or
1730 make_unsigned_type). */
1732 tree
1733 size_in_bytes (tree type)
1735 tree t;
1737 if (type == error_mark_node)
1738 return integer_zero_node;
1740 type = TYPE_MAIN_VARIANT (type);
1741 t = TYPE_SIZE_UNIT (type);
1743 if (t == 0)
1745 lang_hooks.types.incomplete_type_error (NULL_TREE, type);
1746 return size_zero_node;
1749 if (TREE_CODE (t) == INTEGER_CST)
1750 t = force_fit_type (t, 0, false, false);
1752 return t;
1755 /* Return the size of TYPE (in bytes) as a wide integer
1756 or return -1 if the size can vary or is larger than an integer. */
1758 HOST_WIDE_INT
1759 int_size_in_bytes (tree type)
1761 tree t;
1763 if (type == error_mark_node)
1764 return 0;
1766 type = TYPE_MAIN_VARIANT (type);
1767 t = TYPE_SIZE_UNIT (type);
1768 if (t == 0
1769 || TREE_CODE (t) != INTEGER_CST
1770 || TREE_INT_CST_HIGH (t) != 0
1771 /* If the result would appear negative, it's too big to represent. */
1772 || (HOST_WIDE_INT) TREE_INT_CST_LOW (t) < 0)
1773 return -1;
1775 return TREE_INT_CST_LOW (t);
1778 /* Return the maximum size of TYPE (in bytes) as a wide integer
1779 or return -1 if the size can vary or is larger than an integer. */
1781 HOST_WIDE_INT
1782 max_int_size_in_bytes (tree type)
1784 HOST_WIDE_INT size = -1;
1785 tree size_tree;
1787 /* If this is an array type, check for a possible MAX_SIZE attached. */
1789 if (TREE_CODE (type) == ARRAY_TYPE)
1791 size_tree = TYPE_ARRAY_MAX_SIZE (type);
1793 if (size_tree && host_integerp (size_tree, 1))
1794 size = tree_low_cst (size_tree, 1);
1797 /* If we still haven't been able to get a size, see if the language
1798 can compute a maximum size. */
1800 if (size == -1)
1802 size_tree = lang_hooks.types.max_size (type);
1804 if (size_tree && host_integerp (size_tree, 1))
1805 size = tree_low_cst (size_tree, 1);
1808 return size;
1811 /* Return the bit position of FIELD, in bits from the start of the record.
1812 This is a tree of type bitsizetype. */
1814 tree
1815 bit_position (tree field)
1817 return bit_from_pos (DECL_FIELD_OFFSET (field),
1818 DECL_FIELD_BIT_OFFSET (field));
1821 /* Likewise, but return as an integer. It must be representable in
1822 that way (since it could be a signed value, we don't have the
1823 option of returning -1 like int_size_in_byte can. */
1825 HOST_WIDE_INT
1826 int_bit_position (tree field)
1828 return tree_low_cst (bit_position (field), 0);
1831 /* Return the byte position of FIELD, in bytes from the start of the record.
1832 This is a tree of type sizetype. */
1834 tree
1835 byte_position (tree field)
1837 return byte_from_pos (DECL_FIELD_OFFSET (field),
1838 DECL_FIELD_BIT_OFFSET (field));
1841 /* Likewise, but return as an integer. It must be representable in
1842 that way (since it could be a signed value, we don't have the
1843 option of returning -1 like int_size_in_byte can. */
1845 HOST_WIDE_INT
1846 int_byte_position (tree field)
1848 return tree_low_cst (byte_position (field), 0);
1851 /* Return the strictest alignment, in bits, that T is known to have. */
1853 unsigned int
1854 expr_align (tree t)
1856 unsigned int align0, align1;
1858 switch (TREE_CODE (t))
1860 case NOP_EXPR: case CONVERT_EXPR: case NON_LVALUE_EXPR:
1861 /* If we have conversions, we know that the alignment of the
1862 object must meet each of the alignments of the types. */
1863 align0 = expr_align (TREE_OPERAND (t, 0));
1864 align1 = TYPE_ALIGN (TREE_TYPE (t));
1865 return MAX (align0, align1);
1867 case SAVE_EXPR: case COMPOUND_EXPR: case MODIFY_EXPR:
1868 case INIT_EXPR: case TARGET_EXPR: case WITH_CLEANUP_EXPR:
1869 case CLEANUP_POINT_EXPR:
1870 /* These don't change the alignment of an object. */
1871 return expr_align (TREE_OPERAND (t, 0));
1873 case COND_EXPR:
1874 /* The best we can do is say that the alignment is the least aligned
1875 of the two arms. */
1876 align0 = expr_align (TREE_OPERAND (t, 1));
1877 align1 = expr_align (TREE_OPERAND (t, 2));
1878 return MIN (align0, align1);
1880 case LABEL_DECL: case CONST_DECL:
1881 case VAR_DECL: case PARM_DECL: case RESULT_DECL:
1882 if (DECL_ALIGN (t) != 0)
1883 return DECL_ALIGN (t);
1884 break;
1886 case FUNCTION_DECL:
1887 return FUNCTION_BOUNDARY;
1889 default:
1890 break;
1893 /* Otherwise take the alignment from that of the type. */
1894 return TYPE_ALIGN (TREE_TYPE (t));
1897 /* Return, as a tree node, the number of elements for TYPE (which is an
1898 ARRAY_TYPE) minus one. This counts only elements of the top array. */
1900 tree
1901 array_type_nelts (tree type)
1903 tree index_type, min, max;
1905 /* If they did it with unspecified bounds, then we should have already
1906 given an error about it before we got here. */
1907 if (! TYPE_DOMAIN (type))
1908 return error_mark_node;
1910 index_type = TYPE_DOMAIN (type);
1911 min = TYPE_MIN_VALUE (index_type);
1912 max = TYPE_MAX_VALUE (index_type);
1914 return (integer_zerop (min)
1915 ? max
1916 : fold_build2 (MINUS_EXPR, TREE_TYPE (max), max, min));
1919 /* If arg is static -- a reference to an object in static storage -- then
1920 return the object. This is not the same as the C meaning of `static'.
1921 If arg isn't static, return NULL. */
1923 tree
1924 staticp (tree arg)
1926 switch (TREE_CODE (arg))
1928 case FUNCTION_DECL:
1929 /* Nested functions are static, even though taking their address will
1930 involve a trampoline as we unnest the nested function and create
1931 the trampoline on the tree level. */
1932 return arg;
1934 case VAR_DECL:
1935 return ((TREE_STATIC (arg) || DECL_EXTERNAL (arg))
1936 && ! DECL_THREAD_LOCAL_P (arg)
1937 && ! DECL_DLLIMPORT_P (arg)
1938 ? arg : NULL);
1940 case CONST_DECL:
1941 return ((TREE_STATIC (arg) || DECL_EXTERNAL (arg))
1942 ? arg : NULL);
1944 case CONSTRUCTOR:
1945 return TREE_STATIC (arg) ? arg : NULL;
1947 case LABEL_DECL:
1948 case STRING_CST:
1949 return arg;
1951 case COMPONENT_REF:
1952 /* If the thing being referenced is not a field, then it is
1953 something language specific. */
1954 if (TREE_CODE (TREE_OPERAND (arg, 1)) != FIELD_DECL)
1955 return (*lang_hooks.staticp) (arg);
1957 /* If we are referencing a bitfield, we can't evaluate an
1958 ADDR_EXPR at compile time and so it isn't a constant. */
1959 if (DECL_BIT_FIELD (TREE_OPERAND (arg, 1)))
1960 return NULL;
1962 return staticp (TREE_OPERAND (arg, 0));
1964 case BIT_FIELD_REF:
1965 return NULL;
1967 case MISALIGNED_INDIRECT_REF:
1968 case ALIGN_INDIRECT_REF:
1969 case INDIRECT_REF:
1970 return TREE_CONSTANT (TREE_OPERAND (arg, 0)) ? arg : NULL;
1972 case ARRAY_REF:
1973 case ARRAY_RANGE_REF:
1974 if (TREE_CODE (TYPE_SIZE (TREE_TYPE (arg))) == INTEGER_CST
1975 && TREE_CODE (TREE_OPERAND (arg, 1)) == INTEGER_CST)
1976 return staticp (TREE_OPERAND (arg, 0));
1977 else
1978 return false;
1980 default:
1981 if ((unsigned int) TREE_CODE (arg)
1982 >= (unsigned int) LAST_AND_UNUSED_TREE_CODE)
1983 return lang_hooks.staticp (arg);
1984 else
1985 return NULL;
1989 /* Wrap a SAVE_EXPR around EXPR, if appropriate.
1990 Do this to any expression which may be used in more than one place,
1991 but must be evaluated only once.
1993 Normally, expand_expr would reevaluate the expression each time.
1994 Calling save_expr produces something that is evaluated and recorded
1995 the first time expand_expr is called on it. Subsequent calls to
1996 expand_expr just reuse the recorded value.
1998 The call to expand_expr that generates code that actually computes
1999 the value is the first call *at compile time*. Subsequent calls
2000 *at compile time* generate code to use the saved value.
2001 This produces correct result provided that *at run time* control
2002 always flows through the insns made by the first expand_expr
2003 before reaching the other places where the save_expr was evaluated.
2004 You, the caller of save_expr, must make sure this is so.
2006 Constants, and certain read-only nodes, are returned with no
2007 SAVE_EXPR because that is safe. Expressions containing placeholders
2008 are not touched; see tree.def for an explanation of what these
2009 are used for. */
2011 tree
2012 save_expr (tree expr)
2014 tree t = fold (expr);
2015 tree inner;
2017 /* If the tree evaluates to a constant, then we don't want to hide that
2018 fact (i.e. this allows further folding, and direct checks for constants).
2019 However, a read-only object that has side effects cannot be bypassed.
2020 Since it is no problem to reevaluate literals, we just return the
2021 literal node. */
2022 inner = skip_simple_arithmetic (t);
2024 if (TREE_INVARIANT (inner)
2025 || (TREE_READONLY (inner) && ! TREE_SIDE_EFFECTS (inner))
2026 || TREE_CODE (inner) == SAVE_EXPR
2027 || TREE_CODE (inner) == ERROR_MARK)
2028 return t;
2030 /* If INNER contains a PLACEHOLDER_EXPR, we must evaluate it each time, since
2031 it means that the size or offset of some field of an object depends on
2032 the value within another field.
2034 Note that it must not be the case that T contains both a PLACEHOLDER_EXPR
2035 and some variable since it would then need to be both evaluated once and
2036 evaluated more than once. Front-ends must assure this case cannot
2037 happen by surrounding any such subexpressions in their own SAVE_EXPR
2038 and forcing evaluation at the proper time. */
2039 if (contains_placeholder_p (inner))
2040 return t;
2042 t = build1 (SAVE_EXPR, TREE_TYPE (expr), t);
2044 /* This expression might be placed ahead of a jump to ensure that the
2045 value was computed on both sides of the jump. So make sure it isn't
2046 eliminated as dead. */
2047 TREE_SIDE_EFFECTS (t) = 1;
2048 TREE_INVARIANT (t) = 1;
2049 return t;
2052 /* Look inside EXPR and into any simple arithmetic operations. Return
2053 the innermost non-arithmetic node. */
2055 tree
2056 skip_simple_arithmetic (tree expr)
2058 tree inner;
2060 /* We don't care about whether this can be used as an lvalue in this
2061 context. */
2062 while (TREE_CODE (expr) == NON_LVALUE_EXPR)
2063 expr = TREE_OPERAND (expr, 0);
2065 /* If we have simple operations applied to a SAVE_EXPR or to a SAVE_EXPR and
2066 a constant, it will be more efficient to not make another SAVE_EXPR since
2067 it will allow better simplification and GCSE will be able to merge the
2068 computations if they actually occur. */
2069 inner = expr;
2070 while (1)
2072 if (UNARY_CLASS_P (inner))
2073 inner = TREE_OPERAND (inner, 0);
2074 else if (BINARY_CLASS_P (inner))
2076 if (TREE_INVARIANT (TREE_OPERAND (inner, 1)))
2077 inner = TREE_OPERAND (inner, 0);
2078 else if (TREE_INVARIANT (TREE_OPERAND (inner, 0)))
2079 inner = TREE_OPERAND (inner, 1);
2080 else
2081 break;
2083 else
2084 break;
2087 return inner;
2090 /* Return which tree structure is used by T. */
2092 enum tree_node_structure_enum
2093 tree_node_structure (tree t)
2095 enum tree_code code = TREE_CODE (t);
2097 switch (TREE_CODE_CLASS (code))
2099 case tcc_declaration:
2101 switch (code)
2103 case FIELD_DECL:
2104 return TS_FIELD_DECL;
2105 case PARM_DECL:
2106 return TS_PARM_DECL;
2107 case VAR_DECL:
2108 return TS_VAR_DECL;
2109 case LABEL_DECL:
2110 return TS_LABEL_DECL;
2111 case RESULT_DECL:
2112 return TS_RESULT_DECL;
2113 case CONST_DECL:
2114 return TS_CONST_DECL;
2115 case TYPE_DECL:
2116 return TS_TYPE_DECL;
2117 case FUNCTION_DECL:
2118 return TS_FUNCTION_DECL;
2119 case SYMBOL_MEMORY_TAG:
2120 case NAME_MEMORY_TAG:
2121 case STRUCT_FIELD_TAG:
2122 return TS_MEMORY_TAG;
2123 default:
2124 return TS_DECL_NON_COMMON;
2127 case tcc_type:
2128 return TS_TYPE;
2129 case tcc_reference:
2130 case tcc_comparison:
2131 case tcc_unary:
2132 case tcc_binary:
2133 case tcc_expression:
2134 case tcc_statement:
2135 return TS_EXP;
2136 default: /* tcc_constant and tcc_exceptional */
2137 break;
2139 switch (code)
2141 /* tcc_constant cases. */
2142 case INTEGER_CST: return TS_INT_CST;
2143 case REAL_CST: return TS_REAL_CST;
2144 case COMPLEX_CST: return TS_COMPLEX;
2145 case VECTOR_CST: return TS_VECTOR;
2146 case STRING_CST: return TS_STRING;
2147 /* tcc_exceptional cases. */
2148 case ERROR_MARK: return TS_COMMON;
2149 case IDENTIFIER_NODE: return TS_IDENTIFIER;
2150 case TREE_LIST: return TS_LIST;
2151 case TREE_VEC: return TS_VEC;
2152 case PHI_NODE: return TS_PHI_NODE;
2153 case SSA_NAME: return TS_SSA_NAME;
2154 case PLACEHOLDER_EXPR: return TS_COMMON;
2155 case STATEMENT_LIST: return TS_STATEMENT_LIST;
2156 case BLOCK: return TS_BLOCK;
2157 case CONSTRUCTOR: return TS_CONSTRUCTOR;
2158 case TREE_BINFO: return TS_BINFO;
2159 case VALUE_HANDLE: return TS_VALUE_HANDLE;
2160 case OMP_CLAUSE: return TS_OMP_CLAUSE;
2162 default:
2163 gcc_unreachable ();
2167 /* Return 1 if EXP contains a PLACEHOLDER_EXPR; i.e., if it represents a size
2168 or offset that depends on a field within a record. */
2170 bool
2171 contains_placeholder_p (tree exp)
2173 enum tree_code code;
2175 if (!exp)
2176 return 0;
2178 code = TREE_CODE (exp);
2179 if (code == PLACEHOLDER_EXPR)
2180 return 1;
2182 switch (TREE_CODE_CLASS (code))
2184 case tcc_reference:
2185 /* Don't look at any PLACEHOLDER_EXPRs that might be in index or bit
2186 position computations since they will be converted into a
2187 WITH_RECORD_EXPR involving the reference, which will assume
2188 here will be valid. */
2189 return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0));
2191 case tcc_exceptional:
2192 if (code == TREE_LIST)
2193 return (CONTAINS_PLACEHOLDER_P (TREE_VALUE (exp))
2194 || CONTAINS_PLACEHOLDER_P (TREE_CHAIN (exp)));
2195 break;
2197 case tcc_unary:
2198 case tcc_binary:
2199 case tcc_comparison:
2200 case tcc_expression:
2201 switch (code)
2203 case COMPOUND_EXPR:
2204 /* Ignoring the first operand isn't quite right, but works best. */
2205 return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1));
2207 case COND_EXPR:
2208 return (CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0))
2209 || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1))
2210 || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 2)));
2212 case CALL_EXPR:
2213 return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1));
2215 default:
2216 break;
2219 switch (TREE_CODE_LENGTH (code))
2221 case 1:
2222 return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0));
2223 case 2:
2224 return (CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0))
2225 || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1)));
2226 default:
2227 return 0;
2230 default:
2231 return 0;
2233 return 0;
2236 /* Return true if any part of the computation of TYPE involves a
2237 PLACEHOLDER_EXPR. This includes size, bounds, qualifiers
2238 (for QUAL_UNION_TYPE) and field positions. */
2240 static bool
2241 type_contains_placeholder_1 (tree type)
2243 /* If the size contains a placeholder or the parent type (component type in
2244 the case of arrays) type involves a placeholder, this type does. */
2245 if (CONTAINS_PLACEHOLDER_P (TYPE_SIZE (type))
2246 || CONTAINS_PLACEHOLDER_P (TYPE_SIZE_UNIT (type))
2247 || (TREE_TYPE (type) != 0
2248 && type_contains_placeholder_p (TREE_TYPE (type))))
2249 return true;
2251 /* Now do type-specific checks. Note that the last part of the check above
2252 greatly limits what we have to do below. */
2253 switch (TREE_CODE (type))
2255 case VOID_TYPE:
2256 case COMPLEX_TYPE:
2257 case ENUMERAL_TYPE:
2258 case BOOLEAN_TYPE:
2259 case POINTER_TYPE:
2260 case OFFSET_TYPE:
2261 case REFERENCE_TYPE:
2262 case METHOD_TYPE:
2263 case FUNCTION_TYPE:
2264 case VECTOR_TYPE:
2265 return false;
2267 case INTEGER_TYPE:
2268 case REAL_TYPE:
2269 /* Here we just check the bounds. */
2270 return (CONTAINS_PLACEHOLDER_P (TYPE_MIN_VALUE (type))
2271 || CONTAINS_PLACEHOLDER_P (TYPE_MAX_VALUE (type)));
2273 case ARRAY_TYPE:
2274 /* We're already checked the component type (TREE_TYPE), so just check
2275 the index type. */
2276 return type_contains_placeholder_p (TYPE_DOMAIN (type));
2278 case RECORD_TYPE:
2279 case UNION_TYPE:
2280 case QUAL_UNION_TYPE:
2282 tree field;
2284 for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
2285 if (TREE_CODE (field) == FIELD_DECL
2286 && (CONTAINS_PLACEHOLDER_P (DECL_FIELD_OFFSET (field))
2287 || (TREE_CODE (type) == QUAL_UNION_TYPE
2288 && CONTAINS_PLACEHOLDER_P (DECL_QUALIFIER (field)))
2289 || type_contains_placeholder_p (TREE_TYPE (field))))
2290 return true;
2292 return false;
2295 default:
2296 gcc_unreachable ();
2300 bool
2301 type_contains_placeholder_p (tree type)
2303 bool result;
2305 /* If the contains_placeholder_bits field has been initialized,
2306 then we know the answer. */
2307 if (TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) > 0)
2308 return TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) - 1;
2310 /* Indicate that we've seen this type node, and the answer is false.
2311 This is what we want to return if we run into recursion via fields. */
2312 TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) = 1;
2314 /* Compute the real value. */
2315 result = type_contains_placeholder_1 (type);
2317 /* Store the real value. */
2318 TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) = result + 1;
2320 return result;
2323 /* Given a tree EXP, a FIELD_DECL F, and a replacement value R,
2324 return a tree with all occurrences of references to F in a
2325 PLACEHOLDER_EXPR replaced by R. Note that we assume here that EXP
2326 contains only arithmetic expressions or a CALL_EXPR with a
2327 PLACEHOLDER_EXPR occurring only in its arglist. */
2329 tree
2330 substitute_in_expr (tree exp, tree f, tree r)
2332 enum tree_code code = TREE_CODE (exp);
2333 tree op0, op1, op2, op3;
2334 tree new;
2335 tree inner;
2337 /* We handle TREE_LIST and COMPONENT_REF separately. */
2338 if (code == TREE_LIST)
2340 op0 = SUBSTITUTE_IN_EXPR (TREE_CHAIN (exp), f, r);
2341 op1 = SUBSTITUTE_IN_EXPR (TREE_VALUE (exp), f, r);
2342 if (op0 == TREE_CHAIN (exp) && op1 == TREE_VALUE (exp))
2343 return exp;
2345 return tree_cons (TREE_PURPOSE (exp), op1, op0);
2347 else if (code == COMPONENT_REF)
2349 /* If this expression is getting a value from a PLACEHOLDER_EXPR
2350 and it is the right field, replace it with R. */
2351 for (inner = TREE_OPERAND (exp, 0);
2352 REFERENCE_CLASS_P (inner);
2353 inner = TREE_OPERAND (inner, 0))
2355 if (TREE_CODE (inner) == PLACEHOLDER_EXPR
2356 && TREE_OPERAND (exp, 1) == f)
2357 return r;
2359 /* If this expression hasn't been completed let, leave it alone. */
2360 if (TREE_CODE (inner) == PLACEHOLDER_EXPR && TREE_TYPE (inner) == 0)
2361 return exp;
2363 op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
2364 if (op0 == TREE_OPERAND (exp, 0))
2365 return exp;
2367 new = fold_build3 (COMPONENT_REF, TREE_TYPE (exp),
2368 op0, TREE_OPERAND (exp, 1), NULL_TREE);
2370 else
2371 switch (TREE_CODE_CLASS (code))
2373 case tcc_constant:
2374 case tcc_declaration:
2375 return exp;
2377 case tcc_exceptional:
2378 case tcc_unary:
2379 case tcc_binary:
2380 case tcc_comparison:
2381 case tcc_expression:
2382 case tcc_reference:
2383 switch (TREE_CODE_LENGTH (code))
2385 case 0:
2386 return exp;
2388 case 1:
2389 op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
2390 if (op0 == TREE_OPERAND (exp, 0))
2391 return exp;
2393 new = fold_build1 (code, TREE_TYPE (exp), op0);
2394 break;
2396 case 2:
2397 op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
2398 op1 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 1), f, r);
2400 if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1))
2401 return exp;
2403 new = fold_build2 (code, TREE_TYPE (exp), op0, op1);
2404 break;
2406 case 3:
2407 op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
2408 op1 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 1), f, r);
2409 op2 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 2), f, r);
2411 if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
2412 && op2 == TREE_OPERAND (exp, 2))
2413 return exp;
2415 new = fold_build3 (code, TREE_TYPE (exp), op0, op1, op2);
2416 break;
2418 case 4:
2419 op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
2420 op1 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 1), f, r);
2421 op2 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 2), f, r);
2422 op3 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 3), f, r);
2424 if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
2425 && op2 == TREE_OPERAND (exp, 2)
2426 && op3 == TREE_OPERAND (exp, 3))
2427 return exp;
2429 new = fold (build4 (code, TREE_TYPE (exp), op0, op1, op2, op3));
2430 break;
2432 default:
2433 gcc_unreachable ();
2435 break;
2437 default:
2438 gcc_unreachable ();
2441 TREE_READONLY (new) = TREE_READONLY (exp);
2442 return new;
2445 /* Similar, but look for a PLACEHOLDER_EXPR in EXP and find a replacement
2446 for it within OBJ, a tree that is an object or a chain of references. */
2448 tree
2449 substitute_placeholder_in_expr (tree exp, tree obj)
2451 enum tree_code code = TREE_CODE (exp);
2452 tree op0, op1, op2, op3;
2454 /* If this is a PLACEHOLDER_EXPR, see if we find a corresponding type
2455 in the chain of OBJ. */
2456 if (code == PLACEHOLDER_EXPR)
2458 tree need_type = TYPE_MAIN_VARIANT (TREE_TYPE (exp));
2459 tree elt;
2461 for (elt = obj; elt != 0;
2462 elt = ((TREE_CODE (elt) == COMPOUND_EXPR
2463 || TREE_CODE (elt) == COND_EXPR)
2464 ? TREE_OPERAND (elt, 1)
2465 : (REFERENCE_CLASS_P (elt)
2466 || UNARY_CLASS_P (elt)
2467 || BINARY_CLASS_P (elt)
2468 || EXPRESSION_CLASS_P (elt))
2469 ? TREE_OPERAND (elt, 0) : 0))
2470 if (TYPE_MAIN_VARIANT (TREE_TYPE (elt)) == need_type)
2471 return elt;
2473 for (elt = obj; elt != 0;
2474 elt = ((TREE_CODE (elt) == COMPOUND_EXPR
2475 || TREE_CODE (elt) == COND_EXPR)
2476 ? TREE_OPERAND (elt, 1)
2477 : (REFERENCE_CLASS_P (elt)
2478 || UNARY_CLASS_P (elt)
2479 || BINARY_CLASS_P (elt)
2480 || EXPRESSION_CLASS_P (elt))
2481 ? TREE_OPERAND (elt, 0) : 0))
2482 if (POINTER_TYPE_P (TREE_TYPE (elt))
2483 && (TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (elt)))
2484 == need_type))
2485 return fold_build1 (INDIRECT_REF, need_type, elt);
2487 /* If we didn't find it, return the original PLACEHOLDER_EXPR. If it
2488 survives until RTL generation, there will be an error. */
2489 return exp;
2492 /* TREE_LIST is special because we need to look at TREE_VALUE
2493 and TREE_CHAIN, not TREE_OPERANDS. */
2494 else if (code == TREE_LIST)
2496 op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_CHAIN (exp), obj);
2497 op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_VALUE (exp), obj);
2498 if (op0 == TREE_CHAIN (exp) && op1 == TREE_VALUE (exp))
2499 return exp;
2501 return tree_cons (TREE_PURPOSE (exp), op1, op0);
2503 else
2504 switch (TREE_CODE_CLASS (code))
2506 case tcc_constant:
2507 case tcc_declaration:
2508 return exp;
2510 case tcc_exceptional:
2511 case tcc_unary:
2512 case tcc_binary:
2513 case tcc_comparison:
2514 case tcc_expression:
2515 case tcc_reference:
2516 case tcc_statement:
2517 switch (TREE_CODE_LENGTH (code))
2519 case 0:
2520 return exp;
2522 case 1:
2523 op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2524 if (op0 == TREE_OPERAND (exp, 0))
2525 return exp;
2526 else
2527 return fold_build1 (code, TREE_TYPE (exp), op0);
2529 case 2:
2530 op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2531 op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 1), obj);
2533 if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1))
2534 return exp;
2535 else
2536 return fold_build2 (code, TREE_TYPE (exp), op0, op1);
2538 case 3:
2539 op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2540 op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 1), obj);
2541 op2 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 2), obj);
2543 if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
2544 && op2 == TREE_OPERAND (exp, 2))
2545 return exp;
2546 else
2547 return fold_build3 (code, TREE_TYPE (exp), op0, op1, op2);
2549 case 4:
2550 op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2551 op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 1), obj);
2552 op2 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 2), obj);
2553 op3 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 3), obj);
2555 if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
2556 && op2 == TREE_OPERAND (exp, 2)
2557 && op3 == TREE_OPERAND (exp, 3))
2558 return exp;
2559 else
2560 return fold (build4 (code, TREE_TYPE (exp), op0, op1, op2, op3));
2562 default:
2563 gcc_unreachable ();
2565 break;
2567 default:
2568 gcc_unreachable ();
2572 /* Stabilize a reference so that we can use it any number of times
2573 without causing its operands to be evaluated more than once.
2574 Returns the stabilized reference. This works by means of save_expr,
2575 so see the caveats in the comments about save_expr.
2577 Also allows conversion expressions whose operands are references.
2578 Any other kind of expression is returned unchanged. */
2580 tree
2581 stabilize_reference (tree ref)
2583 tree result;
2584 enum tree_code code = TREE_CODE (ref);
2586 switch (code)
2588 case VAR_DECL:
2589 case PARM_DECL:
2590 case RESULT_DECL:
2591 /* No action is needed in this case. */
2592 return ref;
2594 case NOP_EXPR:
2595 case CONVERT_EXPR:
2596 case FLOAT_EXPR:
2597 case FIX_TRUNC_EXPR:
2598 case FIX_FLOOR_EXPR:
2599 case FIX_ROUND_EXPR:
2600 case FIX_CEIL_EXPR:
2601 result = build_nt (code, stabilize_reference (TREE_OPERAND (ref, 0)));
2602 break;
2604 case INDIRECT_REF:
2605 result = build_nt (INDIRECT_REF,
2606 stabilize_reference_1 (TREE_OPERAND (ref, 0)));
2607 break;
2609 case COMPONENT_REF:
2610 result = build_nt (COMPONENT_REF,
2611 stabilize_reference (TREE_OPERAND (ref, 0)),
2612 TREE_OPERAND (ref, 1), NULL_TREE);
2613 break;
2615 case BIT_FIELD_REF:
2616 result = build_nt (BIT_FIELD_REF,
2617 stabilize_reference (TREE_OPERAND (ref, 0)),
2618 stabilize_reference_1 (TREE_OPERAND (ref, 1)),
2619 stabilize_reference_1 (TREE_OPERAND (ref, 2)));
2620 break;
2622 case ARRAY_REF:
2623 result = build_nt (ARRAY_REF,
2624 stabilize_reference (TREE_OPERAND (ref, 0)),
2625 stabilize_reference_1 (TREE_OPERAND (ref, 1)),
2626 TREE_OPERAND (ref, 2), TREE_OPERAND (ref, 3));
2627 break;
2629 case ARRAY_RANGE_REF:
2630 result = build_nt (ARRAY_RANGE_REF,
2631 stabilize_reference (TREE_OPERAND (ref, 0)),
2632 stabilize_reference_1 (TREE_OPERAND (ref, 1)),
2633 TREE_OPERAND (ref, 2), TREE_OPERAND (ref, 3));
2634 break;
2636 case COMPOUND_EXPR:
2637 /* We cannot wrap the first expression in a SAVE_EXPR, as then
2638 it wouldn't be ignored. This matters when dealing with
2639 volatiles. */
2640 return stabilize_reference_1 (ref);
2642 /* If arg isn't a kind of lvalue we recognize, make no change.
2643 Caller should recognize the error for an invalid lvalue. */
2644 default:
2645 return ref;
2647 case ERROR_MARK:
2648 return error_mark_node;
2651 TREE_TYPE (result) = TREE_TYPE (ref);
2652 TREE_READONLY (result) = TREE_READONLY (ref);
2653 TREE_SIDE_EFFECTS (result) = TREE_SIDE_EFFECTS (ref);
2654 TREE_THIS_VOLATILE (result) = TREE_THIS_VOLATILE (ref);
2656 return result;
2659 /* Subroutine of stabilize_reference; this is called for subtrees of
2660 references. Any expression with side-effects must be put in a SAVE_EXPR
2661 to ensure that it is only evaluated once.
2663 We don't put SAVE_EXPR nodes around everything, because assigning very
2664 simple expressions to temporaries causes us to miss good opportunities
2665 for optimizations. Among other things, the opportunity to fold in the
2666 addition of a constant into an addressing mode often gets lost, e.g.
2667 "y[i+1] += x;". In general, we take the approach that we should not make
2668 an assignment unless we are forced into it - i.e., that any non-side effect
2669 operator should be allowed, and that cse should take care of coalescing
2670 multiple utterances of the same expression should that prove fruitful. */
2672 tree
2673 stabilize_reference_1 (tree e)
2675 tree result;
2676 enum tree_code code = TREE_CODE (e);
2678 /* We cannot ignore const expressions because it might be a reference
2679 to a const array but whose index contains side-effects. But we can
2680 ignore things that are actual constant or that already have been
2681 handled by this function. */
2683 if (TREE_INVARIANT (e))
2684 return e;
2686 switch (TREE_CODE_CLASS (code))
2688 case tcc_exceptional:
2689 case tcc_type:
2690 case tcc_declaration:
2691 case tcc_comparison:
2692 case tcc_statement:
2693 case tcc_expression:
2694 case tcc_reference:
2695 /* If the expression has side-effects, then encase it in a SAVE_EXPR
2696 so that it will only be evaluated once. */
2697 /* The reference (r) and comparison (<) classes could be handled as
2698 below, but it is generally faster to only evaluate them once. */
2699 if (TREE_SIDE_EFFECTS (e))
2700 return save_expr (e);
2701 return e;
2703 case tcc_constant:
2704 /* Constants need no processing. In fact, we should never reach
2705 here. */
2706 return e;
2708 case tcc_binary:
2709 /* Division is slow and tends to be compiled with jumps,
2710 especially the division by powers of 2 that is often
2711 found inside of an array reference. So do it just once. */
2712 if (code == TRUNC_DIV_EXPR || code == TRUNC_MOD_EXPR
2713 || code == FLOOR_DIV_EXPR || code == FLOOR_MOD_EXPR
2714 || code == CEIL_DIV_EXPR || code == CEIL_MOD_EXPR
2715 || code == ROUND_DIV_EXPR || code == ROUND_MOD_EXPR)
2716 return save_expr (e);
2717 /* Recursively stabilize each operand. */
2718 result = build_nt (code, stabilize_reference_1 (TREE_OPERAND (e, 0)),
2719 stabilize_reference_1 (TREE_OPERAND (e, 1)));
2720 break;
2722 case tcc_unary:
2723 /* Recursively stabilize each operand. */
2724 result = build_nt (code, stabilize_reference_1 (TREE_OPERAND (e, 0)));
2725 break;
2727 default:
2728 gcc_unreachable ();
2731 TREE_TYPE (result) = TREE_TYPE (e);
2732 TREE_READONLY (result) = TREE_READONLY (e);
2733 TREE_SIDE_EFFECTS (result) = TREE_SIDE_EFFECTS (e);
2734 TREE_THIS_VOLATILE (result) = TREE_THIS_VOLATILE (e);
2735 TREE_INVARIANT (result) = 1;
2737 return result;
2740 /* Low-level constructors for expressions. */
2742 /* A helper function for build1 and constant folders. Set TREE_CONSTANT,
2743 TREE_INVARIANT, and TREE_SIDE_EFFECTS for an ADDR_EXPR. */
2745 void
2746 recompute_tree_invariant_for_addr_expr (tree t)
2748 tree node;
2749 bool tc = true, ti = true, se = false;
2751 /* We started out assuming this address is both invariant and constant, but
2752 does not have side effects. Now go down any handled components and see if
2753 any of them involve offsets that are either non-constant or non-invariant.
2754 Also check for side-effects.
2756 ??? Note that this code makes no attempt to deal with the case where
2757 taking the address of something causes a copy due to misalignment. */
2759 #define UPDATE_TITCSE(NODE) \
2760 do { tree _node = (NODE); \
2761 if (_node && !TREE_INVARIANT (_node)) ti = false; \
2762 if (_node && !TREE_CONSTANT (_node)) tc = false; \
2763 if (_node && TREE_SIDE_EFFECTS (_node)) se = true; } while (0)
2765 for (node = TREE_OPERAND (t, 0); handled_component_p (node);
2766 node = TREE_OPERAND (node, 0))
2768 /* If the first operand doesn't have an ARRAY_TYPE, this is a bogus
2769 array reference (probably made temporarily by the G++ front end),
2770 so ignore all the operands. */
2771 if ((TREE_CODE (node) == ARRAY_REF
2772 || TREE_CODE (node) == ARRAY_RANGE_REF)
2773 && TREE_CODE (TREE_TYPE (TREE_OPERAND (node, 0))) == ARRAY_TYPE)
2775 UPDATE_TITCSE (TREE_OPERAND (node, 1));
2776 if (TREE_OPERAND (node, 2))
2777 UPDATE_TITCSE (TREE_OPERAND (node, 2));
2778 if (TREE_OPERAND (node, 3))
2779 UPDATE_TITCSE (TREE_OPERAND (node, 3));
2781 /* Likewise, just because this is a COMPONENT_REF doesn't mean we have a
2782 FIELD_DECL, apparently. The G++ front end can put something else
2783 there, at least temporarily. */
2784 else if (TREE_CODE (node) == COMPONENT_REF
2785 && TREE_CODE (TREE_OPERAND (node, 1)) == FIELD_DECL)
2787 if (TREE_OPERAND (node, 2))
2788 UPDATE_TITCSE (TREE_OPERAND (node, 2));
2790 else if (TREE_CODE (node) == BIT_FIELD_REF)
2791 UPDATE_TITCSE (TREE_OPERAND (node, 2));
2794 node = lang_hooks.expr_to_decl (node, &tc, &ti, &se);
2796 /* Now see what's inside. If it's an INDIRECT_REF, copy our properties from
2797 the address, since &(*a)->b is a form of addition. If it's a decl, it's
2798 invariant and constant if the decl is static. It's also invariant if it's
2799 a decl in the current function. Taking the address of a volatile variable
2800 is not volatile. If it's a constant, the address is both invariant and
2801 constant. Otherwise it's neither. */
2802 if (TREE_CODE (node) == INDIRECT_REF)
2803 UPDATE_TITCSE (TREE_OPERAND (node, 0));
2804 else if (DECL_P (node))
2806 if (staticp (node))
2808 else if (decl_function_context (node) == current_function_decl
2809 /* Addresses of thread-local variables are invariant. */
2810 || (TREE_CODE (node) == VAR_DECL
2811 && DECL_THREAD_LOCAL_P (node)))
2812 tc = false;
2813 else
2814 ti = tc = false;
2816 else if (CONSTANT_CLASS_P (node))
2818 else
2820 ti = tc = false;
2821 se |= TREE_SIDE_EFFECTS (node);
2824 TREE_CONSTANT (t) = tc;
2825 TREE_INVARIANT (t) = ti;
2826 TREE_SIDE_EFFECTS (t) = se;
2827 #undef UPDATE_TITCSE
2830 /* Build an expression of code CODE, data type TYPE, and operands as
2831 specified. Expressions and reference nodes can be created this way.
2832 Constants, decls, types and misc nodes cannot be.
2834 We define 5 non-variadic functions, from 0 to 4 arguments. This is
2835 enough for all extant tree codes. */
2837 tree
2838 build0_stat (enum tree_code code, tree tt MEM_STAT_DECL)
2840 tree t;
2842 gcc_assert (TREE_CODE_LENGTH (code) == 0);
2844 t = make_node_stat (code PASS_MEM_STAT);
2845 TREE_TYPE (t) = tt;
2847 return t;
2850 tree
2851 build1_stat (enum tree_code code, tree type, tree node MEM_STAT_DECL)
2853 int length = sizeof (struct tree_exp);
2854 #ifdef GATHER_STATISTICS
2855 tree_node_kind kind;
2856 #endif
2857 tree t;
2859 #ifdef GATHER_STATISTICS
2860 switch (TREE_CODE_CLASS (code))
2862 case tcc_statement: /* an expression with side effects */
2863 kind = s_kind;
2864 break;
2865 case tcc_reference: /* a reference */
2866 kind = r_kind;
2867 break;
2868 default:
2869 kind = e_kind;
2870 break;
2873 tree_node_counts[(int) kind]++;
2874 tree_node_sizes[(int) kind] += length;
2875 #endif
2877 gcc_assert (TREE_CODE_LENGTH (code) == 1);
2879 t = ggc_alloc_zone_pass_stat (length, &tree_zone);
2881 memset (t, 0, sizeof (struct tree_common));
2883 TREE_SET_CODE (t, code);
2885 TREE_TYPE (t) = type;
2886 #ifdef USE_MAPPED_LOCATION
2887 SET_EXPR_LOCATION (t, UNKNOWN_LOCATION);
2888 #else
2889 SET_EXPR_LOCUS (t, NULL);
2890 #endif
2891 TREE_COMPLEXITY (t) = 0;
2892 TREE_OPERAND (t, 0) = node;
2893 TREE_BLOCK (t) = NULL_TREE;
2894 if (node && !TYPE_P (node))
2896 TREE_SIDE_EFFECTS (t) = TREE_SIDE_EFFECTS (node);
2897 TREE_READONLY (t) = TREE_READONLY (node);
2900 if (TREE_CODE_CLASS (code) == tcc_statement)
2901 TREE_SIDE_EFFECTS (t) = 1;
2902 else switch (code)
2904 case VA_ARG_EXPR:
2905 /* All of these have side-effects, no matter what their
2906 operands are. */
2907 TREE_SIDE_EFFECTS (t) = 1;
2908 TREE_READONLY (t) = 0;
2909 break;
2911 case MISALIGNED_INDIRECT_REF:
2912 case ALIGN_INDIRECT_REF:
2913 case INDIRECT_REF:
2914 /* Whether a dereference is readonly has nothing to do with whether
2915 its operand is readonly. */
2916 TREE_READONLY (t) = 0;
2917 break;
2919 case ADDR_EXPR:
2920 if (node)
2921 recompute_tree_invariant_for_addr_expr (t);
2922 break;
2924 default:
2925 if ((TREE_CODE_CLASS (code) == tcc_unary || code == VIEW_CONVERT_EXPR)
2926 && node && !TYPE_P (node)
2927 && TREE_CONSTANT (node))
2928 TREE_CONSTANT (t) = 1;
2929 if ((TREE_CODE_CLASS (code) == tcc_unary || code == VIEW_CONVERT_EXPR)
2930 && node && TREE_INVARIANT (node))
2931 TREE_INVARIANT (t) = 1;
2932 if (TREE_CODE_CLASS (code) == tcc_reference
2933 && node && TREE_THIS_VOLATILE (node))
2934 TREE_THIS_VOLATILE (t) = 1;
2935 break;
2938 return t;
2941 #define PROCESS_ARG(N) \
2942 do { \
2943 TREE_OPERAND (t, N) = arg##N; \
2944 if (arg##N &&!TYPE_P (arg##N)) \
2946 if (TREE_SIDE_EFFECTS (arg##N)) \
2947 side_effects = 1; \
2948 if (!TREE_READONLY (arg##N)) \
2949 read_only = 0; \
2950 if (!TREE_CONSTANT (arg##N)) \
2951 constant = 0; \
2952 if (!TREE_INVARIANT (arg##N)) \
2953 invariant = 0; \
2955 } while (0)
2957 tree
2958 build2_stat (enum tree_code code, tree tt, tree arg0, tree arg1 MEM_STAT_DECL)
2960 bool constant, read_only, side_effects, invariant;
2961 tree t;
2963 gcc_assert (TREE_CODE_LENGTH (code) == 2);
2965 t = make_node_stat (code PASS_MEM_STAT);
2966 TREE_TYPE (t) = tt;
2968 /* Below, we automatically set TREE_SIDE_EFFECTS and TREE_READONLY for the
2969 result based on those same flags for the arguments. But if the
2970 arguments aren't really even `tree' expressions, we shouldn't be trying
2971 to do this. */
2973 /* Expressions without side effects may be constant if their
2974 arguments are as well. */
2975 constant = (TREE_CODE_CLASS (code) == tcc_comparison
2976 || TREE_CODE_CLASS (code) == tcc_binary);
2977 read_only = 1;
2978 side_effects = TREE_SIDE_EFFECTS (t);
2979 invariant = constant;
2981 PROCESS_ARG(0);
2982 PROCESS_ARG(1);
2984 TREE_READONLY (t) = read_only;
2985 TREE_CONSTANT (t) = constant;
2986 TREE_INVARIANT (t) = invariant;
2987 TREE_SIDE_EFFECTS (t) = side_effects;
2988 TREE_THIS_VOLATILE (t)
2989 = (TREE_CODE_CLASS (code) == tcc_reference
2990 && arg0 && TREE_THIS_VOLATILE (arg0));
2992 return t;
2995 tree
2996 build3_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
2997 tree arg2 MEM_STAT_DECL)
2999 bool constant, read_only, side_effects, invariant;
3000 tree t;
3002 gcc_assert (TREE_CODE_LENGTH (code) == 3);
3004 t = make_node_stat (code PASS_MEM_STAT);
3005 TREE_TYPE (t) = tt;
3007 side_effects = TREE_SIDE_EFFECTS (t);
3009 PROCESS_ARG(0);
3010 PROCESS_ARG(1);
3011 PROCESS_ARG(2);
3013 if (code == CALL_EXPR && !side_effects)
3015 tree node;
3016 int i;
3018 /* Calls have side-effects, except those to const or
3019 pure functions. */
3020 i = call_expr_flags (t);
3021 if (!(i & (ECF_CONST | ECF_PURE)))
3022 side_effects = 1;
3024 /* And even those have side-effects if their arguments do. */
3025 else for (node = arg1; node; node = TREE_CHAIN (node))
3026 if (TREE_SIDE_EFFECTS (TREE_VALUE (node)))
3028 side_effects = 1;
3029 break;
3033 TREE_SIDE_EFFECTS (t) = side_effects;
3034 TREE_THIS_VOLATILE (t)
3035 = (TREE_CODE_CLASS (code) == tcc_reference
3036 && arg0 && TREE_THIS_VOLATILE (arg0));
3038 return t;
3041 tree
3042 build4_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
3043 tree arg2, tree arg3 MEM_STAT_DECL)
3045 bool constant, read_only, side_effects, invariant;
3046 tree t;
3048 gcc_assert (TREE_CODE_LENGTH (code) == 4);
3050 t = make_node_stat (code PASS_MEM_STAT);
3051 TREE_TYPE (t) = tt;
3053 side_effects = TREE_SIDE_EFFECTS (t);
3055 PROCESS_ARG(0);
3056 PROCESS_ARG(1);
3057 PROCESS_ARG(2);
3058 PROCESS_ARG(3);
3060 TREE_SIDE_EFFECTS (t) = side_effects;
3061 TREE_THIS_VOLATILE (t)
3062 = (TREE_CODE_CLASS (code) == tcc_reference
3063 && arg0 && TREE_THIS_VOLATILE (arg0));
3065 return t;
3068 tree
3069 build5_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
3070 tree arg2, tree arg3, tree arg4 MEM_STAT_DECL)
3072 bool constant, read_only, side_effects, invariant;
3073 tree t;
3075 gcc_assert (TREE_CODE_LENGTH (code) == 5);
3077 t = make_node_stat (code PASS_MEM_STAT);
3078 TREE_TYPE (t) = tt;
3080 side_effects = TREE_SIDE_EFFECTS (t);
3082 PROCESS_ARG(0);
3083 PROCESS_ARG(1);
3084 PROCESS_ARG(2);
3085 PROCESS_ARG(3);
3086 PROCESS_ARG(4);
3088 TREE_SIDE_EFFECTS (t) = side_effects;
3089 TREE_THIS_VOLATILE (t)
3090 = (TREE_CODE_CLASS (code) == tcc_reference
3091 && arg0 && TREE_THIS_VOLATILE (arg0));
3093 return t;
3096 tree
3097 build7_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
3098 tree arg2, tree arg3, tree arg4, tree arg5,
3099 tree arg6 MEM_STAT_DECL)
3101 bool constant, read_only, side_effects, invariant;
3102 tree t;
3104 gcc_assert (code == TARGET_MEM_REF);
3106 t = make_node_stat (code PASS_MEM_STAT);
3107 TREE_TYPE (t) = tt;
3109 side_effects = TREE_SIDE_EFFECTS (t);
3111 PROCESS_ARG(0);
3112 PROCESS_ARG(1);
3113 PROCESS_ARG(2);
3114 PROCESS_ARG(3);
3115 PROCESS_ARG(4);
3116 PROCESS_ARG(5);
3117 PROCESS_ARG(6);
3119 TREE_SIDE_EFFECTS (t) = side_effects;
3120 TREE_THIS_VOLATILE (t) = 0;
3122 return t;
3125 /* Similar except don't specify the TREE_TYPE
3126 and leave the TREE_SIDE_EFFECTS as 0.
3127 It is permissible for arguments to be null,
3128 or even garbage if their values do not matter. */
3130 tree
3131 build_nt (enum tree_code code, ...)
3133 tree t;
3134 int length;
3135 int i;
3136 va_list p;
3138 va_start (p, code);
3140 t = make_node (code);
3141 length = TREE_CODE_LENGTH (code);
3143 for (i = 0; i < length; i++)
3144 TREE_OPERAND (t, i) = va_arg (p, tree);
3146 va_end (p);
3147 return t;
3150 /* Create a DECL_... node of code CODE, name NAME and data type TYPE.
3151 We do NOT enter this node in any sort of symbol table.
3153 layout_decl is used to set up the decl's storage layout.
3154 Other slots are initialized to 0 or null pointers. */
3156 tree
3157 build_decl_stat (enum tree_code code, tree name, tree type MEM_STAT_DECL)
3159 tree t;
3161 t = make_node_stat (code PASS_MEM_STAT);
3163 /* if (type == error_mark_node)
3164 type = integer_type_node; */
3165 /* That is not done, deliberately, so that having error_mark_node
3166 as the type can suppress useless errors in the use of this variable. */
3168 DECL_NAME (t) = name;
3169 TREE_TYPE (t) = type;
3171 if (code == VAR_DECL || code == PARM_DECL || code == RESULT_DECL)
3172 layout_decl (t, 0);
3173 else if (code == FUNCTION_DECL)
3174 DECL_MODE (t) = FUNCTION_MODE;
3176 return t;
3179 /* Builds and returns function declaration with NAME and TYPE. */
3181 tree
3182 build_fn_decl (const char *name, tree type)
3184 tree id = get_identifier (name);
3185 tree decl = build_decl (FUNCTION_DECL, id, type);
3187 DECL_EXTERNAL (decl) = 1;
3188 TREE_PUBLIC (decl) = 1;
3189 DECL_ARTIFICIAL (decl) = 1;
3190 TREE_NOTHROW (decl) = 1;
3192 return decl;
3196 /* BLOCK nodes are used to represent the structure of binding contours
3197 and declarations, once those contours have been exited and their contents
3198 compiled. This information is used for outputting debugging info. */
3200 tree
3201 build_block (tree vars, tree subblocks, tree supercontext, tree chain)
3203 tree block = make_node (BLOCK);
3205 BLOCK_VARS (block) = vars;
3206 BLOCK_SUBBLOCKS (block) = subblocks;
3207 BLOCK_SUPERCONTEXT (block) = supercontext;
3208 BLOCK_CHAIN (block) = chain;
3209 return block;
3212 #if 1 /* ! defined(USE_MAPPED_LOCATION) */
3213 /* ??? gengtype doesn't handle conditionals */
3214 static GTY(()) source_locus last_annotated_node;
3215 #endif
3217 #ifdef USE_MAPPED_LOCATION
3219 expanded_location
3220 expand_location (source_location loc)
3222 expanded_location xloc;
3223 if (loc == 0)
3225 xloc.file = NULL;
3226 xloc.line = 0;
3227 xloc.column = 0;
3229 else
3231 const struct line_map *map = linemap_lookup (&line_table, loc);
3232 xloc.file = map->to_file;
3233 xloc.line = SOURCE_LINE (map, loc);
3234 xloc.column = SOURCE_COLUMN (map, loc);
3236 return xloc;
3239 #else
3241 /* Record the exact location where an expression or an identifier were
3242 encountered. */
3244 void
3245 annotate_with_file_line (tree node, const char *file, int line)
3247 /* Roughly one percent of the calls to this function are to annotate
3248 a node with the same information already attached to that node!
3249 Just return instead of wasting memory. */
3250 if (EXPR_LOCUS (node)
3251 && EXPR_LINENO (node) == line
3252 && (EXPR_FILENAME (node) == file
3253 || !strcmp (EXPR_FILENAME (node), file)))
3255 last_annotated_node = EXPR_LOCUS (node);
3256 return;
3259 /* In heavily macroized code (such as GCC itself) this single
3260 entry cache can reduce the number of allocations by more
3261 than half. */
3262 if (last_annotated_node
3263 && last_annotated_node->line == line
3264 && (last_annotated_node->file == file
3265 || !strcmp (last_annotated_node->file, file)))
3267 SET_EXPR_LOCUS (node, last_annotated_node);
3268 return;
3271 SET_EXPR_LOCUS (node, ggc_alloc (sizeof (location_t)));
3272 EXPR_LINENO (node) = line;
3273 EXPR_FILENAME (node) = file;
3274 last_annotated_node = EXPR_LOCUS (node);
3277 void
3278 annotate_with_locus (tree node, location_t locus)
3280 annotate_with_file_line (node, locus.file, locus.line);
3282 #endif
3284 /* Return a declaration like DDECL except that its DECL_ATTRIBUTES
3285 is ATTRIBUTE. */
3287 tree
3288 build_decl_attribute_variant (tree ddecl, tree attribute)
3290 DECL_ATTRIBUTES (ddecl) = attribute;
3291 return ddecl;
3294 /* Borrowed from hashtab.c iterative_hash implementation. */
3295 #define mix(a,b,c) \
3297 a -= b; a -= c; a ^= (c>>13); \
3298 b -= c; b -= a; b ^= (a<< 8); \
3299 c -= a; c -= b; c ^= ((b&0xffffffff)>>13); \
3300 a -= b; a -= c; a ^= ((c&0xffffffff)>>12); \
3301 b -= c; b -= a; b = (b ^ (a<<16)) & 0xffffffff; \
3302 c -= a; c -= b; c = (c ^ (b>> 5)) & 0xffffffff; \
3303 a -= b; a -= c; a = (a ^ (c>> 3)) & 0xffffffff; \
3304 b -= c; b -= a; b = (b ^ (a<<10)) & 0xffffffff; \
3305 c -= a; c -= b; c = (c ^ (b>>15)) & 0xffffffff; \
3309 /* Produce good hash value combining VAL and VAL2. */
3310 static inline hashval_t
3311 iterative_hash_hashval_t (hashval_t val, hashval_t val2)
3313 /* the golden ratio; an arbitrary value. */
3314 hashval_t a = 0x9e3779b9;
3316 mix (a, val, val2);
3317 return val2;
3320 /* Produce good hash value combining PTR and VAL2. */
3321 static inline hashval_t
3322 iterative_hash_pointer (void *ptr, hashval_t val2)
3324 if (sizeof (ptr) == sizeof (hashval_t))
3325 return iterative_hash_hashval_t ((size_t) ptr, val2);
3326 else
3328 hashval_t a = (hashval_t) (size_t) ptr;
3329 /* Avoid warnings about shifting of more than the width of the type on
3330 hosts that won't execute this path. */
3331 int zero = 0;
3332 hashval_t b = (hashval_t) ((size_t) ptr >> (sizeof (hashval_t) * 8 + zero));
3333 mix (a, b, val2);
3334 return val2;
3338 /* Produce good hash value combining VAL and VAL2. */
3339 static inline hashval_t
3340 iterative_hash_host_wide_int (HOST_WIDE_INT val, hashval_t val2)
3342 if (sizeof (HOST_WIDE_INT) == sizeof (hashval_t))
3343 return iterative_hash_hashval_t (val, val2);
3344 else
3346 hashval_t a = (hashval_t) val;
3347 /* Avoid warnings about shifting of more than the width of the type on
3348 hosts that won't execute this path. */
3349 int zero = 0;
3350 hashval_t b = (hashval_t) (val >> (sizeof (hashval_t) * 8 + zero));
3351 mix (a, b, val2);
3352 if (sizeof (HOST_WIDE_INT) > 2 * sizeof (hashval_t))
3354 hashval_t a = (hashval_t) (val >> (sizeof (hashval_t) * 16 + zero));
3355 hashval_t b = (hashval_t) (val >> (sizeof (hashval_t) * 24 + zero));
3356 mix (a, b, val2);
3358 return val2;
3362 /* Return a type like TTYPE except that its TYPE_ATTRIBUTE
3363 is ATTRIBUTE and its qualifiers are QUALS.
3365 Record such modified types already made so we don't make duplicates. */
3367 static tree
3368 build_type_attribute_qual_variant (tree ttype, tree attribute, int quals)
3370 if (! attribute_list_equal (TYPE_ATTRIBUTES (ttype), attribute))
3372 hashval_t hashcode = 0;
3373 tree ntype;
3374 enum tree_code code = TREE_CODE (ttype);
3376 ntype = copy_node (ttype);
3378 TYPE_POINTER_TO (ntype) = 0;
3379 TYPE_REFERENCE_TO (ntype) = 0;
3380 TYPE_ATTRIBUTES (ntype) = attribute;
3382 /* Create a new main variant of TYPE. */
3383 TYPE_MAIN_VARIANT (ntype) = ntype;
3384 TYPE_NEXT_VARIANT (ntype) = 0;
3385 set_type_quals (ntype, TYPE_UNQUALIFIED);
3387 hashcode = iterative_hash_object (code, hashcode);
3388 if (TREE_TYPE (ntype))
3389 hashcode = iterative_hash_object (TYPE_HASH (TREE_TYPE (ntype)),
3390 hashcode);
3391 hashcode = attribute_hash_list (attribute, hashcode);
3393 switch (TREE_CODE (ntype))
3395 case FUNCTION_TYPE:
3396 hashcode = type_hash_list (TYPE_ARG_TYPES (ntype), hashcode);
3397 break;
3398 case ARRAY_TYPE:
3399 hashcode = iterative_hash_object (TYPE_HASH (TYPE_DOMAIN (ntype)),
3400 hashcode);
3401 break;
3402 case INTEGER_TYPE:
3403 hashcode = iterative_hash_object
3404 (TREE_INT_CST_LOW (TYPE_MAX_VALUE (ntype)), hashcode);
3405 hashcode = iterative_hash_object
3406 (TREE_INT_CST_HIGH (TYPE_MAX_VALUE (ntype)), hashcode);
3407 break;
3408 case REAL_TYPE:
3410 unsigned int precision = TYPE_PRECISION (ntype);
3411 hashcode = iterative_hash_object (precision, hashcode);
3413 break;
3414 default:
3415 break;
3418 ntype = type_hash_canon (hashcode, ntype);
3419 ttype = build_qualified_type (ntype, quals);
3422 return ttype;
3426 /* Return a type like TTYPE except that its TYPE_ATTRIBUTE
3427 is ATTRIBUTE.
3429 Record such modified types already made so we don't make duplicates. */
3431 tree
3432 build_type_attribute_variant (tree ttype, tree attribute)
3434 return build_type_attribute_qual_variant (ttype, attribute,
3435 TYPE_QUALS (ttype));
3438 /* Return nonzero if IDENT is a valid name for attribute ATTR,
3439 or zero if not.
3441 We try both `text' and `__text__', ATTR may be either one. */
3442 /* ??? It might be a reasonable simplification to require ATTR to be only
3443 `text'. One might then also require attribute lists to be stored in
3444 their canonicalized form. */
3446 static int
3447 is_attribute_with_length_p (const char *attr, int attr_len, tree ident)
3449 int ident_len;
3450 const char *p;
3452 if (TREE_CODE (ident) != IDENTIFIER_NODE)
3453 return 0;
3455 p = IDENTIFIER_POINTER (ident);
3456 ident_len = IDENTIFIER_LENGTH (ident);
3458 if (ident_len == attr_len
3459 && strcmp (attr, p) == 0)
3460 return 1;
3462 /* If ATTR is `__text__', IDENT must be `text'; and vice versa. */
3463 if (attr[0] == '_')
3465 gcc_assert (attr[1] == '_');
3466 gcc_assert (attr[attr_len - 2] == '_');
3467 gcc_assert (attr[attr_len - 1] == '_');
3468 if (ident_len == attr_len - 4
3469 && strncmp (attr + 2, p, attr_len - 4) == 0)
3470 return 1;
3472 else
3474 if (ident_len == attr_len + 4
3475 && p[0] == '_' && p[1] == '_'
3476 && p[ident_len - 2] == '_' && p[ident_len - 1] == '_'
3477 && strncmp (attr, p + 2, attr_len) == 0)
3478 return 1;
3481 return 0;
3484 /* Return nonzero if IDENT is a valid name for attribute ATTR,
3485 or zero if not.
3487 We try both `text' and `__text__', ATTR may be either one. */
3490 is_attribute_p (const char *attr, tree ident)
3492 return is_attribute_with_length_p (attr, strlen (attr), ident);
3495 /* Given an attribute name and a list of attributes, return a pointer to the
3496 attribute's list element if the attribute is part of the list, or NULL_TREE
3497 if not found. If the attribute appears more than once, this only
3498 returns the first occurrence; the TREE_CHAIN of the return value should
3499 be passed back in if further occurrences are wanted. */
3501 tree
3502 lookup_attribute (const char *attr_name, tree list)
3504 tree l;
3505 size_t attr_len = strlen (attr_name);
3507 for (l = list; l; l = TREE_CHAIN (l))
3509 gcc_assert (TREE_CODE (TREE_PURPOSE (l)) == IDENTIFIER_NODE);
3510 if (is_attribute_with_length_p (attr_name, attr_len, TREE_PURPOSE (l)))
3511 return l;
3514 return NULL_TREE;
3517 /* Remove any instances of attribute ATTR_NAME in LIST and return the
3518 modified list. */
3520 tree
3521 remove_attribute (const char *attr_name, tree list)
3523 tree *p;
3524 size_t attr_len = strlen (attr_name);
3526 for (p = &list; *p; )
3528 tree l = *p;
3529 gcc_assert (TREE_CODE (TREE_PURPOSE (l)) == IDENTIFIER_NODE);
3530 if (is_attribute_with_length_p (attr_name, attr_len, TREE_PURPOSE (l)))
3531 *p = TREE_CHAIN (l);
3532 else
3533 p = &TREE_CHAIN (l);
3536 return list;
3539 /* Return an attribute list that is the union of a1 and a2. */
3541 tree
3542 merge_attributes (tree a1, tree a2)
3544 tree attributes;
3546 /* Either one unset? Take the set one. */
3548 if ((attributes = a1) == 0)
3549 attributes = a2;
3551 /* One that completely contains the other? Take it. */
3553 else if (a2 != 0 && ! attribute_list_contained (a1, a2))
3555 if (attribute_list_contained (a2, a1))
3556 attributes = a2;
3557 else
3559 /* Pick the longest list, and hang on the other list. */
3561 if (list_length (a1) < list_length (a2))
3562 attributes = a2, a2 = a1;
3564 for (; a2 != 0; a2 = TREE_CHAIN (a2))
3566 tree a;
3567 for (a = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (a2)),
3568 attributes);
3569 a != NULL_TREE;
3570 a = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (a2)),
3571 TREE_CHAIN (a)))
3573 if (TREE_VALUE (a) != NULL
3574 && TREE_CODE (TREE_VALUE (a)) == TREE_LIST
3575 && TREE_VALUE (a2) != NULL
3576 && TREE_CODE (TREE_VALUE (a2)) == TREE_LIST)
3578 if (simple_cst_list_equal (TREE_VALUE (a),
3579 TREE_VALUE (a2)) == 1)
3580 break;
3582 else if (simple_cst_equal (TREE_VALUE (a),
3583 TREE_VALUE (a2)) == 1)
3584 break;
3586 if (a == NULL_TREE)
3588 a1 = copy_node (a2);
3589 TREE_CHAIN (a1) = attributes;
3590 attributes = a1;
3595 return attributes;
3598 /* Given types T1 and T2, merge their attributes and return
3599 the result. */
3601 tree
3602 merge_type_attributes (tree t1, tree t2)
3604 return merge_attributes (TYPE_ATTRIBUTES (t1),
3605 TYPE_ATTRIBUTES (t2));
3608 /* Given decls OLDDECL and NEWDECL, merge their attributes and return
3609 the result. */
3611 tree
3612 merge_decl_attributes (tree olddecl, tree newdecl)
3614 return merge_attributes (DECL_ATTRIBUTES (olddecl),
3615 DECL_ATTRIBUTES (newdecl));
3618 #if TARGET_DLLIMPORT_DECL_ATTRIBUTES
3620 /* Specialization of merge_decl_attributes for various Windows targets.
3622 This handles the following situation:
3624 __declspec (dllimport) int foo;
3625 int foo;
3627 The second instance of `foo' nullifies the dllimport. */
3629 tree
3630 merge_dllimport_decl_attributes (tree old, tree new)
3632 tree a;
3633 int delete_dllimport_p = 1;
3635 /* What we need to do here is remove from `old' dllimport if it doesn't
3636 appear in `new'. dllimport behaves like extern: if a declaration is
3637 marked dllimport and a definition appears later, then the object
3638 is not dllimport'd. We also remove a `new' dllimport if the old list
3639 contains dllexport: dllexport always overrides dllimport, regardless
3640 of the order of declaration. */
3641 if (!VAR_OR_FUNCTION_DECL_P (new))
3642 delete_dllimport_p = 0;
3643 else if (DECL_DLLIMPORT_P (new)
3644 && lookup_attribute ("dllexport", DECL_ATTRIBUTES (old)))
3646 DECL_DLLIMPORT_P (new) = 0;
3647 warning (OPT_Wattributes, "%q+D already declared with dllexport attribute: "
3648 "dllimport ignored", new);
3650 else if (DECL_DLLIMPORT_P (old) && !DECL_DLLIMPORT_P (new))
3652 /* Warn about overriding a symbol that has already been used. eg:
3653 extern int __attribute__ ((dllimport)) foo;
3654 int* bar () {return &foo;}
3655 int foo;
3657 if (TREE_USED (old))
3659 warning (0, "%q+D redeclared without dllimport attribute "
3660 "after being referenced with dll linkage", new);
3661 /* If we have used a variable's address with dllimport linkage,
3662 keep the old DECL_DLLIMPORT_P flag: the ADDR_EXPR using the
3663 decl may already have had TREE_INVARIANT and TREE_CONSTANT
3664 computed.
3665 We still remove the attribute so that assembler code refers
3666 to '&foo rather than '_imp__foo'. */
3667 if (TREE_CODE (old) == VAR_DECL && TREE_ADDRESSABLE (old))
3668 DECL_DLLIMPORT_P (new) = 1;
3671 /* Let an inline definition silently override the external reference,
3672 but otherwise warn about attribute inconsistency. */
3673 else if (TREE_CODE (new) == VAR_DECL
3674 || !DECL_DECLARED_INLINE_P (new))
3675 warning (OPT_Wattributes, "%q+D redeclared without dllimport attribute: "
3676 "previous dllimport ignored", new);
3678 else
3679 delete_dllimport_p = 0;
3681 a = merge_attributes (DECL_ATTRIBUTES (old), DECL_ATTRIBUTES (new));
3683 if (delete_dllimport_p)
3685 tree prev, t;
3686 const size_t attr_len = strlen ("dllimport");
3688 /* Scan the list for dllimport and delete it. */
3689 for (prev = NULL_TREE, t = a; t; prev = t, t = TREE_CHAIN (t))
3691 if (is_attribute_with_length_p ("dllimport", attr_len,
3692 TREE_PURPOSE (t)))
3694 if (prev == NULL_TREE)
3695 a = TREE_CHAIN (a);
3696 else
3697 TREE_CHAIN (prev) = TREE_CHAIN (t);
3698 break;
3703 return a;
3706 /* Handle a "dllimport" or "dllexport" attribute; arguments as in
3707 struct attribute_spec.handler. */
3709 tree
3710 handle_dll_attribute (tree * pnode, tree name, tree args, int flags,
3711 bool *no_add_attrs)
3713 tree node = *pnode;
3715 /* These attributes may apply to structure and union types being created,
3716 but otherwise should pass to the declaration involved. */
3717 if (!DECL_P (node))
3719 if (flags & ((int) ATTR_FLAG_DECL_NEXT | (int) ATTR_FLAG_FUNCTION_NEXT
3720 | (int) ATTR_FLAG_ARRAY_NEXT))
3722 *no_add_attrs = true;
3723 return tree_cons (name, args, NULL_TREE);
3725 if (TREE_CODE (node) != RECORD_TYPE && TREE_CODE (node) != UNION_TYPE)
3727 warning (OPT_Wattributes, "%qs attribute ignored",
3728 IDENTIFIER_POINTER (name));
3729 *no_add_attrs = true;
3732 return NULL_TREE;
3735 if (TREE_CODE (node) != FUNCTION_DECL
3736 && TREE_CODE (node) != VAR_DECL)
3738 *no_add_attrs = true;
3739 warning (OPT_Wattributes, "%qs attribute ignored",
3740 IDENTIFIER_POINTER (name));
3741 return NULL_TREE;
3744 /* Report error on dllimport ambiguities seen now before they cause
3745 any damage. */
3746 else if (is_attribute_p ("dllimport", name))
3748 /* Honor any target-specific overrides. */
3749 if (!targetm.valid_dllimport_attribute_p (node))
3750 *no_add_attrs = true;
3752 else if (TREE_CODE (node) == FUNCTION_DECL
3753 && DECL_DECLARED_INLINE_P (node))
3755 warning (OPT_Wattributes, "inline function %q+D declared as "
3756 " dllimport: attribute ignored", node);
3757 *no_add_attrs = true;
3759 /* Like MS, treat definition of dllimported variables and
3760 non-inlined functions on declaration as syntax errors. */
3761 else if (TREE_CODE (node) == FUNCTION_DECL && DECL_INITIAL (node))
3763 error ("function %q+D definition is marked dllimport", node);
3764 *no_add_attrs = true;
3767 else if (TREE_CODE (node) == VAR_DECL)
3769 if (DECL_INITIAL (node))
3771 error ("variable %q+D definition is marked dllimport",
3772 node);
3773 *no_add_attrs = true;
3776 /* `extern' needn't be specified with dllimport.
3777 Specify `extern' now and hope for the best. Sigh. */
3778 DECL_EXTERNAL (node) = 1;
3779 /* Also, implicitly give dllimport'd variables declared within
3780 a function global scope, unless declared static. */
3781 if (current_function_decl != NULL_TREE && !TREE_STATIC (node))
3782 TREE_PUBLIC (node) = 1;
3785 if (*no_add_attrs == false)
3786 DECL_DLLIMPORT_P (node) = 1;
3789 /* Report error if symbol is not accessible at global scope. */
3790 if (!TREE_PUBLIC (node)
3791 && (TREE_CODE (node) == VAR_DECL
3792 || TREE_CODE (node) == FUNCTION_DECL))
3794 error ("external linkage required for symbol %q+D because of "
3795 "%qs attribute", node, IDENTIFIER_POINTER (name));
3796 *no_add_attrs = true;
3799 return NULL_TREE;
3802 #endif /* TARGET_DLLIMPORT_DECL_ATTRIBUTES */
3804 /* Set the type qualifiers for TYPE to TYPE_QUALS, which is a bitmask
3805 of the various TYPE_QUAL values. */
3807 static void
3808 set_type_quals (tree type, int type_quals)
3810 TYPE_READONLY (type) = (type_quals & TYPE_QUAL_CONST) != 0;
3811 TYPE_VOLATILE (type) = (type_quals & TYPE_QUAL_VOLATILE) != 0;
3812 TYPE_RESTRICT (type) = (type_quals & TYPE_QUAL_RESTRICT) != 0;
3815 /* Returns true iff cand is equivalent to base with type_quals. */
3817 bool
3818 check_qualified_type (tree cand, tree base, int type_quals)
3820 return (TYPE_QUALS (cand) == type_quals
3821 && TYPE_NAME (cand) == TYPE_NAME (base)
3822 /* Apparently this is needed for Objective-C. */
3823 && TYPE_CONTEXT (cand) == TYPE_CONTEXT (base)
3824 && attribute_list_equal (TYPE_ATTRIBUTES (cand),
3825 TYPE_ATTRIBUTES (base)));
3828 /* Return a version of the TYPE, qualified as indicated by the
3829 TYPE_QUALS, if one exists. If no qualified version exists yet,
3830 return NULL_TREE. */
3832 tree
3833 get_qualified_type (tree type, int type_quals)
3835 tree t;
3837 if (TYPE_QUALS (type) == type_quals)
3838 return type;
3840 /* Search the chain of variants to see if there is already one there just
3841 like the one we need to have. If so, use that existing one. We must
3842 preserve the TYPE_NAME, since there is code that depends on this. */
3843 for (t = TYPE_MAIN_VARIANT (type); t; t = TYPE_NEXT_VARIANT (t))
3844 if (check_qualified_type (t, type, type_quals))
3845 return t;
3847 return NULL_TREE;
3850 /* Like get_qualified_type, but creates the type if it does not
3851 exist. This function never returns NULL_TREE. */
3853 tree
3854 build_qualified_type (tree type, int type_quals)
3856 tree t;
3858 /* See if we already have the appropriate qualified variant. */
3859 t = get_qualified_type (type, type_quals);
3861 /* If not, build it. */
3862 if (!t)
3864 t = build_variant_type_copy (type);
3865 set_type_quals (t, type_quals);
3868 return t;
3871 /* Create a new distinct copy of TYPE. The new type is made its own
3872 MAIN_VARIANT. */
3874 tree
3875 build_distinct_type_copy (tree type)
3877 tree t = copy_node (type);
3879 TYPE_POINTER_TO (t) = 0;
3880 TYPE_REFERENCE_TO (t) = 0;
3882 /* Make it its own variant. */
3883 TYPE_MAIN_VARIANT (t) = t;
3884 TYPE_NEXT_VARIANT (t) = 0;
3886 return t;
3889 /* Create a new variant of TYPE, equivalent but distinct.
3890 This is so the caller can modify it. */
3892 tree
3893 build_variant_type_copy (tree type)
3895 tree t, m = TYPE_MAIN_VARIANT (type);
3897 t = build_distinct_type_copy (type);
3899 /* Add the new type to the chain of variants of TYPE. */
3900 TYPE_NEXT_VARIANT (t) = TYPE_NEXT_VARIANT (m);
3901 TYPE_NEXT_VARIANT (m) = t;
3902 TYPE_MAIN_VARIANT (t) = m;
3904 return t;
3907 /* Return true if the from tree in both tree maps are equal. */
3910 tree_map_eq (const void *va, const void *vb)
3912 const struct tree_map *a = va, *b = vb;
3913 return (a->from == b->from);
3916 /* Hash a from tree in a tree_map. */
3918 unsigned int
3919 tree_map_hash (const void *item)
3921 return (((const struct tree_map *) item)->hash);
3924 /* Return true if this tree map structure is marked for garbage collection
3925 purposes. We simply return true if the from tree is marked, so that this
3926 structure goes away when the from tree goes away. */
3929 tree_map_marked_p (const void *p)
3931 tree from = ((struct tree_map *) p)->from;
3933 return ggc_marked_p (from);
3936 /* Return true if the trees in the tree_int_map *'s VA and VB are equal. */
3938 static int
3939 tree_int_map_eq (const void *va, const void *vb)
3941 const struct tree_int_map *a = va, *b = vb;
3942 return (a->from == b->from);
3945 /* Hash a from tree in the tree_int_map * ITEM. */
3947 static unsigned int
3948 tree_int_map_hash (const void *item)
3950 return htab_hash_pointer (((const struct tree_int_map *)item)->from);
3953 /* Return true if this tree int map structure is marked for garbage collection
3954 purposes. We simply return true if the from tree_int_map *P's from tree is marked, so that this
3955 structure goes away when the from tree goes away. */
3957 static int
3958 tree_int_map_marked_p (const void *p)
3960 tree from = ((struct tree_int_map *) p)->from;
3962 return ggc_marked_p (from);
3964 /* Lookup an init priority for FROM, and return it if we find one. */
3966 unsigned short
3967 decl_init_priority_lookup (tree from)
3969 struct tree_int_map *h, in;
3970 in.from = from;
3972 h = htab_find_with_hash (init_priority_for_decl,
3973 &in, htab_hash_pointer (from));
3974 if (h)
3975 return h->to;
3976 return 0;
3979 /* Insert a mapping FROM->TO in the init priority hashtable. */
3981 void
3982 decl_init_priority_insert (tree from, unsigned short to)
3984 struct tree_int_map *h;
3985 void **loc;
3987 h = ggc_alloc (sizeof (struct tree_int_map));
3988 h->from = from;
3989 h->to = to;
3990 loc = htab_find_slot_with_hash (init_priority_for_decl, h,
3991 htab_hash_pointer (from), INSERT);
3992 *(struct tree_int_map **) loc = h;
3995 /* Look up a restrict qualified base decl for FROM. */
3997 tree
3998 decl_restrict_base_lookup (tree from)
4000 struct tree_map *h;
4001 struct tree_map in;
4003 in.from = from;
4004 h = htab_find_with_hash (restrict_base_for_decl, &in,
4005 htab_hash_pointer (from));
4006 return h ? h->to : NULL_TREE;
4009 /* Record the restrict qualified base TO for FROM. */
4011 void
4012 decl_restrict_base_insert (tree from, tree to)
4014 struct tree_map *h;
4015 void **loc;
4017 h = ggc_alloc (sizeof (struct tree_map));
4018 h->hash = htab_hash_pointer (from);
4019 h->from = from;
4020 h->to = to;
4021 loc = htab_find_slot_with_hash (restrict_base_for_decl, h, h->hash, INSERT);
4022 *(struct tree_map **) loc = h;
4025 /* Print out the statistics for the DECL_DEBUG_EXPR hash table. */
4027 static void
4028 print_debug_expr_statistics (void)
4030 fprintf (stderr, "DECL_DEBUG_EXPR hash: size %ld, %ld elements, %f collisions\n",
4031 (long) htab_size (debug_expr_for_decl),
4032 (long) htab_elements (debug_expr_for_decl),
4033 htab_collisions (debug_expr_for_decl));
4036 /* Print out the statistics for the DECL_VALUE_EXPR hash table. */
4038 static void
4039 print_value_expr_statistics (void)
4041 fprintf (stderr, "DECL_VALUE_EXPR hash: size %ld, %ld elements, %f collisions\n",
4042 (long) htab_size (value_expr_for_decl),
4043 (long) htab_elements (value_expr_for_decl),
4044 htab_collisions (value_expr_for_decl));
4047 /* Print out statistics for the RESTRICT_BASE_FOR_DECL hash table, but
4048 don't print anything if the table is empty. */
4050 static void
4051 print_restrict_base_statistics (void)
4053 if (htab_elements (restrict_base_for_decl) != 0)
4054 fprintf (stderr,
4055 "RESTRICT_BASE hash: size %ld, %ld elements, %f collisions\n",
4056 (long) htab_size (restrict_base_for_decl),
4057 (long) htab_elements (restrict_base_for_decl),
4058 htab_collisions (restrict_base_for_decl));
4061 /* Lookup a debug expression for FROM, and return it if we find one. */
4063 tree
4064 decl_debug_expr_lookup (tree from)
4066 struct tree_map *h, in;
4067 in.from = from;
4069 h = htab_find_with_hash (debug_expr_for_decl, &in, htab_hash_pointer (from));
4070 if (h)
4071 return h->to;
4072 return NULL_TREE;
4075 /* Insert a mapping FROM->TO in the debug expression hashtable. */
4077 void
4078 decl_debug_expr_insert (tree from, tree to)
4080 struct tree_map *h;
4081 void **loc;
4083 h = ggc_alloc (sizeof (struct tree_map));
4084 h->hash = htab_hash_pointer (from);
4085 h->from = from;
4086 h->to = to;
4087 loc = htab_find_slot_with_hash (debug_expr_for_decl, h, h->hash, INSERT);
4088 *(struct tree_map **) loc = h;
4091 /* Lookup a value expression for FROM, and return it if we find one. */
4093 tree
4094 decl_value_expr_lookup (tree from)
4096 struct tree_map *h, in;
4097 in.from = from;
4099 h = htab_find_with_hash (value_expr_for_decl, &in, htab_hash_pointer (from));
4100 if (h)
4101 return h->to;
4102 return NULL_TREE;
4105 /* Insert a mapping FROM->TO in the value expression hashtable. */
4107 void
4108 decl_value_expr_insert (tree from, tree to)
4110 struct tree_map *h;
4111 void **loc;
4113 h = ggc_alloc (sizeof (struct tree_map));
4114 h->hash = htab_hash_pointer (from);
4115 h->from = from;
4116 h->to = to;
4117 loc = htab_find_slot_with_hash (value_expr_for_decl, h, h->hash, INSERT);
4118 *(struct tree_map **) loc = h;
4121 /* Hashing of types so that we don't make duplicates.
4122 The entry point is `type_hash_canon'. */
4124 /* Compute a hash code for a list of types (chain of TREE_LIST nodes
4125 with types in the TREE_VALUE slots), by adding the hash codes
4126 of the individual types. */
4128 unsigned int
4129 type_hash_list (tree list, hashval_t hashcode)
4131 tree tail;
4133 for (tail = list; tail; tail = TREE_CHAIN (tail))
4134 if (TREE_VALUE (tail) != error_mark_node)
4135 hashcode = iterative_hash_object (TYPE_HASH (TREE_VALUE (tail)),
4136 hashcode);
4138 return hashcode;
4141 /* These are the Hashtable callback functions. */
4143 /* Returns true iff the types are equivalent. */
4145 static int
4146 type_hash_eq (const void *va, const void *vb)
4148 const struct type_hash *a = va, *b = vb;
4150 /* First test the things that are the same for all types. */
4151 if (a->hash != b->hash
4152 || TREE_CODE (a->type) != TREE_CODE (b->type)
4153 || TREE_TYPE (a->type) != TREE_TYPE (b->type)
4154 || !attribute_list_equal (TYPE_ATTRIBUTES (a->type),
4155 TYPE_ATTRIBUTES (b->type))
4156 || TYPE_ALIGN (a->type) != TYPE_ALIGN (b->type)
4157 || TYPE_MODE (a->type) != TYPE_MODE (b->type))
4158 return 0;
4160 switch (TREE_CODE (a->type))
4162 case VOID_TYPE:
4163 case COMPLEX_TYPE:
4164 case POINTER_TYPE:
4165 case REFERENCE_TYPE:
4166 return 1;
4168 case VECTOR_TYPE:
4169 return TYPE_VECTOR_SUBPARTS (a->type) == TYPE_VECTOR_SUBPARTS (b->type);
4171 case ENUMERAL_TYPE:
4172 if (TYPE_VALUES (a->type) != TYPE_VALUES (b->type)
4173 && !(TYPE_VALUES (a->type)
4174 && TREE_CODE (TYPE_VALUES (a->type)) == TREE_LIST
4175 && TYPE_VALUES (b->type)
4176 && TREE_CODE (TYPE_VALUES (b->type)) == TREE_LIST
4177 && type_list_equal (TYPE_VALUES (a->type),
4178 TYPE_VALUES (b->type))))
4179 return 0;
4181 /* ... fall through ... */
4183 case INTEGER_TYPE:
4184 case REAL_TYPE:
4185 case BOOLEAN_TYPE:
4186 return ((TYPE_MAX_VALUE (a->type) == TYPE_MAX_VALUE (b->type)
4187 || tree_int_cst_equal (TYPE_MAX_VALUE (a->type),
4188 TYPE_MAX_VALUE (b->type)))
4189 && (TYPE_MIN_VALUE (a->type) == TYPE_MIN_VALUE (b->type)
4190 || tree_int_cst_equal (TYPE_MIN_VALUE (a->type),
4191 TYPE_MIN_VALUE (b->type))));
4193 case OFFSET_TYPE:
4194 return TYPE_OFFSET_BASETYPE (a->type) == TYPE_OFFSET_BASETYPE (b->type);
4196 case METHOD_TYPE:
4197 return (TYPE_METHOD_BASETYPE (a->type) == TYPE_METHOD_BASETYPE (b->type)
4198 && (TYPE_ARG_TYPES (a->type) == TYPE_ARG_TYPES (b->type)
4199 || (TYPE_ARG_TYPES (a->type)
4200 && TREE_CODE (TYPE_ARG_TYPES (a->type)) == TREE_LIST
4201 && TYPE_ARG_TYPES (b->type)
4202 && TREE_CODE (TYPE_ARG_TYPES (b->type)) == TREE_LIST
4203 && type_list_equal (TYPE_ARG_TYPES (a->type),
4204 TYPE_ARG_TYPES (b->type)))));
4206 case ARRAY_TYPE:
4207 return TYPE_DOMAIN (a->type) == TYPE_DOMAIN (b->type);
4209 case RECORD_TYPE:
4210 case UNION_TYPE:
4211 case QUAL_UNION_TYPE:
4212 return (TYPE_FIELDS (a->type) == TYPE_FIELDS (b->type)
4213 || (TYPE_FIELDS (a->type)
4214 && TREE_CODE (TYPE_FIELDS (a->type)) == TREE_LIST
4215 && TYPE_FIELDS (b->type)
4216 && TREE_CODE (TYPE_FIELDS (b->type)) == TREE_LIST
4217 && type_list_equal (TYPE_FIELDS (a->type),
4218 TYPE_FIELDS (b->type))));
4220 case FUNCTION_TYPE:
4221 return (TYPE_ARG_TYPES (a->type) == TYPE_ARG_TYPES (b->type)
4222 || (TYPE_ARG_TYPES (a->type)
4223 && TREE_CODE (TYPE_ARG_TYPES (a->type)) == TREE_LIST
4224 && TYPE_ARG_TYPES (b->type)
4225 && TREE_CODE (TYPE_ARG_TYPES (b->type)) == TREE_LIST
4226 && type_list_equal (TYPE_ARG_TYPES (a->type),
4227 TYPE_ARG_TYPES (b->type))));
4229 default:
4230 return 0;
4234 /* Return the cached hash value. */
4236 static hashval_t
4237 type_hash_hash (const void *item)
4239 return ((const struct type_hash *) item)->hash;
4242 /* Look in the type hash table for a type isomorphic to TYPE.
4243 If one is found, return it. Otherwise return 0. */
4245 tree
4246 type_hash_lookup (hashval_t hashcode, tree type)
4248 struct type_hash *h, in;
4250 /* The TYPE_ALIGN field of a type is set by layout_type(), so we
4251 must call that routine before comparing TYPE_ALIGNs. */
4252 layout_type (type);
4254 in.hash = hashcode;
4255 in.type = type;
4257 h = htab_find_with_hash (type_hash_table, &in, hashcode);
4258 if (h)
4259 return h->type;
4260 return NULL_TREE;
4263 /* Add an entry to the type-hash-table
4264 for a type TYPE whose hash code is HASHCODE. */
4266 void
4267 type_hash_add (hashval_t hashcode, tree type)
4269 struct type_hash *h;
4270 void **loc;
4272 h = ggc_alloc (sizeof (struct type_hash));
4273 h->hash = hashcode;
4274 h->type = type;
4275 loc = htab_find_slot_with_hash (type_hash_table, h, hashcode, INSERT);
4276 *(struct type_hash **) loc = h;
4279 /* Given TYPE, and HASHCODE its hash code, return the canonical
4280 object for an identical type if one already exists.
4281 Otherwise, return TYPE, and record it as the canonical object.
4283 To use this function, first create a type of the sort you want.
4284 Then compute its hash code from the fields of the type that
4285 make it different from other similar types.
4286 Then call this function and use the value. */
4288 tree
4289 type_hash_canon (unsigned int hashcode, tree type)
4291 tree t1;
4293 /* The hash table only contains main variants, so ensure that's what we're
4294 being passed. */
4295 gcc_assert (TYPE_MAIN_VARIANT (type) == type);
4297 if (!lang_hooks.types.hash_types)
4298 return type;
4300 /* See if the type is in the hash table already. If so, return it.
4301 Otherwise, add the type. */
4302 t1 = type_hash_lookup (hashcode, type);
4303 if (t1 != 0)
4305 #ifdef GATHER_STATISTICS
4306 tree_node_counts[(int) t_kind]--;
4307 tree_node_sizes[(int) t_kind] -= sizeof (struct tree_type);
4308 #endif
4309 return t1;
4311 else
4313 type_hash_add (hashcode, type);
4314 return type;
4318 /* See if the data pointed to by the type hash table is marked. We consider
4319 it marked if the type is marked or if a debug type number or symbol
4320 table entry has been made for the type. This reduces the amount of
4321 debugging output and eliminates that dependency of the debug output on
4322 the number of garbage collections. */
4324 static int
4325 type_hash_marked_p (const void *p)
4327 tree type = ((struct type_hash *) p)->type;
4329 return ggc_marked_p (type) || TYPE_SYMTAB_POINTER (type);
4332 static void
4333 print_type_hash_statistics (void)
4335 fprintf (stderr, "Type hash: size %ld, %ld elements, %f collisions\n",
4336 (long) htab_size (type_hash_table),
4337 (long) htab_elements (type_hash_table),
4338 htab_collisions (type_hash_table));
4341 /* Compute a hash code for a list of attributes (chain of TREE_LIST nodes
4342 with names in the TREE_PURPOSE slots and args in the TREE_VALUE slots),
4343 by adding the hash codes of the individual attributes. */
4345 unsigned int
4346 attribute_hash_list (tree list, hashval_t hashcode)
4348 tree tail;
4350 for (tail = list; tail; tail = TREE_CHAIN (tail))
4351 /* ??? Do we want to add in TREE_VALUE too? */
4352 hashcode = iterative_hash_object
4353 (IDENTIFIER_HASH_VALUE (TREE_PURPOSE (tail)), hashcode);
4354 return hashcode;
4357 /* Given two lists of attributes, return true if list l2 is
4358 equivalent to l1. */
4361 attribute_list_equal (tree l1, tree l2)
4363 return attribute_list_contained (l1, l2)
4364 && attribute_list_contained (l2, l1);
4367 /* Given two lists of attributes, return true if list L2 is
4368 completely contained within L1. */
4369 /* ??? This would be faster if attribute names were stored in a canonicalized
4370 form. Otherwise, if L1 uses `foo' and L2 uses `__foo__', the long method
4371 must be used to show these elements are equivalent (which they are). */
4372 /* ??? It's not clear that attributes with arguments will always be handled
4373 correctly. */
4376 attribute_list_contained (tree l1, tree l2)
4378 tree t1, t2;
4380 /* First check the obvious, maybe the lists are identical. */
4381 if (l1 == l2)
4382 return 1;
4384 /* Maybe the lists are similar. */
4385 for (t1 = l1, t2 = l2;
4386 t1 != 0 && t2 != 0
4387 && TREE_PURPOSE (t1) == TREE_PURPOSE (t2)
4388 && TREE_VALUE (t1) == TREE_VALUE (t2);
4389 t1 = TREE_CHAIN (t1), t2 = TREE_CHAIN (t2));
4391 /* Maybe the lists are equal. */
4392 if (t1 == 0 && t2 == 0)
4393 return 1;
4395 for (; t2 != 0; t2 = TREE_CHAIN (t2))
4397 tree attr;
4398 for (attr = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (t2)), l1);
4399 attr != NULL_TREE;
4400 attr = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (t2)),
4401 TREE_CHAIN (attr)))
4403 if (TREE_VALUE (t2) != NULL
4404 && TREE_CODE (TREE_VALUE (t2)) == TREE_LIST
4405 && TREE_VALUE (attr) != NULL
4406 && TREE_CODE (TREE_VALUE (attr)) == TREE_LIST)
4408 if (simple_cst_list_equal (TREE_VALUE (t2),
4409 TREE_VALUE (attr)) == 1)
4410 break;
4412 else if (simple_cst_equal (TREE_VALUE (t2), TREE_VALUE (attr)) == 1)
4413 break;
4416 if (attr == 0)
4417 return 0;
4420 return 1;
4423 /* Given two lists of types
4424 (chains of TREE_LIST nodes with types in the TREE_VALUE slots)
4425 return 1 if the lists contain the same types in the same order.
4426 Also, the TREE_PURPOSEs must match. */
4429 type_list_equal (tree l1, tree l2)
4431 tree t1, t2;
4433 for (t1 = l1, t2 = l2; t1 && t2; t1 = TREE_CHAIN (t1), t2 = TREE_CHAIN (t2))
4434 if (TREE_VALUE (t1) != TREE_VALUE (t2)
4435 || (TREE_PURPOSE (t1) != TREE_PURPOSE (t2)
4436 && ! (1 == simple_cst_equal (TREE_PURPOSE (t1), TREE_PURPOSE (t2))
4437 && (TREE_TYPE (TREE_PURPOSE (t1))
4438 == TREE_TYPE (TREE_PURPOSE (t2))))))
4439 return 0;
4441 return t1 == t2;
4444 /* Returns the number of arguments to the FUNCTION_TYPE or METHOD_TYPE
4445 given by TYPE. If the argument list accepts variable arguments,
4446 then this function counts only the ordinary arguments. */
4449 type_num_arguments (tree type)
4451 int i = 0;
4452 tree t;
4454 for (t = TYPE_ARG_TYPES (type); t; t = TREE_CHAIN (t))
4455 /* If the function does not take a variable number of arguments,
4456 the last element in the list will have type `void'. */
4457 if (VOID_TYPE_P (TREE_VALUE (t)))
4458 break;
4459 else
4460 ++i;
4462 return i;
4465 /* Nonzero if integer constants T1 and T2
4466 represent the same constant value. */
4469 tree_int_cst_equal (tree t1, tree t2)
4471 if (t1 == t2)
4472 return 1;
4474 if (t1 == 0 || t2 == 0)
4475 return 0;
4477 if (TREE_CODE (t1) == INTEGER_CST
4478 && TREE_CODE (t2) == INTEGER_CST
4479 && TREE_INT_CST_LOW (t1) == TREE_INT_CST_LOW (t2)
4480 && TREE_INT_CST_HIGH (t1) == TREE_INT_CST_HIGH (t2))
4481 return 1;
4483 return 0;
4486 /* Nonzero if integer constants T1 and T2 represent values that satisfy <.
4487 The precise way of comparison depends on their data type. */
4490 tree_int_cst_lt (tree t1, tree t2)
4492 if (t1 == t2)
4493 return 0;
4495 if (TYPE_UNSIGNED (TREE_TYPE (t1)) != TYPE_UNSIGNED (TREE_TYPE (t2)))
4497 int t1_sgn = tree_int_cst_sgn (t1);
4498 int t2_sgn = tree_int_cst_sgn (t2);
4500 if (t1_sgn < t2_sgn)
4501 return 1;
4502 else if (t1_sgn > t2_sgn)
4503 return 0;
4504 /* Otherwise, both are non-negative, so we compare them as
4505 unsigned just in case one of them would overflow a signed
4506 type. */
4508 else if (!TYPE_UNSIGNED (TREE_TYPE (t1)))
4509 return INT_CST_LT (t1, t2);
4511 return INT_CST_LT_UNSIGNED (t1, t2);
4514 /* Returns -1 if T1 < T2, 0 if T1 == T2, and 1 if T1 > T2. */
4517 tree_int_cst_compare (tree t1, tree t2)
4519 if (tree_int_cst_lt (t1, t2))
4520 return -1;
4521 else if (tree_int_cst_lt (t2, t1))
4522 return 1;
4523 else
4524 return 0;
4527 /* Return 1 if T is an INTEGER_CST that can be manipulated efficiently on
4528 the host. If POS is zero, the value can be represented in a single
4529 HOST_WIDE_INT. If POS is nonzero, the value must be non-negative and can
4530 be represented in a single unsigned HOST_WIDE_INT. */
4533 host_integerp (tree t, int pos)
4535 return (TREE_CODE (t) == INTEGER_CST
4536 && ((TREE_INT_CST_HIGH (t) == 0
4537 && (HOST_WIDE_INT) TREE_INT_CST_LOW (t) >= 0)
4538 || (! pos && TREE_INT_CST_HIGH (t) == -1
4539 && (HOST_WIDE_INT) TREE_INT_CST_LOW (t) < 0
4540 && !TYPE_UNSIGNED (TREE_TYPE (t)))
4541 || (pos && TREE_INT_CST_HIGH (t) == 0)));
4544 /* Return the HOST_WIDE_INT least significant bits of T if it is an
4545 INTEGER_CST and there is no overflow. POS is nonzero if the result must
4546 be non-negative. We must be able to satisfy the above conditions. */
4548 HOST_WIDE_INT
4549 tree_low_cst (tree t, int pos)
4551 gcc_assert (host_integerp (t, pos));
4552 return TREE_INT_CST_LOW (t);
4555 /* Return the most significant bit of the integer constant T. */
4558 tree_int_cst_msb (tree t)
4560 int prec;
4561 HOST_WIDE_INT h;
4562 unsigned HOST_WIDE_INT l;
4564 /* Note that using TYPE_PRECISION here is wrong. We care about the
4565 actual bits, not the (arbitrary) range of the type. */
4566 prec = GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (t))) - 1;
4567 rshift_double (TREE_INT_CST_LOW (t), TREE_INT_CST_HIGH (t), prec,
4568 2 * HOST_BITS_PER_WIDE_INT, &l, &h, 0);
4569 return (l & 1) == 1;
4572 /* Return an indication of the sign of the integer constant T.
4573 The return value is -1 if T < 0, 0 if T == 0, and 1 if T > 0.
4574 Note that -1 will never be returned if T's type is unsigned. */
4577 tree_int_cst_sgn (tree t)
4579 if (TREE_INT_CST_LOW (t) == 0 && TREE_INT_CST_HIGH (t) == 0)
4580 return 0;
4581 else if (TYPE_UNSIGNED (TREE_TYPE (t)))
4582 return 1;
4583 else if (TREE_INT_CST_HIGH (t) < 0)
4584 return -1;
4585 else
4586 return 1;
4589 /* Compare two constructor-element-type constants. Return 1 if the lists
4590 are known to be equal; otherwise return 0. */
4593 simple_cst_list_equal (tree l1, tree l2)
4595 while (l1 != NULL_TREE && l2 != NULL_TREE)
4597 if (simple_cst_equal (TREE_VALUE (l1), TREE_VALUE (l2)) != 1)
4598 return 0;
4600 l1 = TREE_CHAIN (l1);
4601 l2 = TREE_CHAIN (l2);
4604 return l1 == l2;
4607 /* Return truthvalue of whether T1 is the same tree structure as T2.
4608 Return 1 if they are the same.
4609 Return 0 if they are understandably different.
4610 Return -1 if either contains tree structure not understood by
4611 this function. */
4614 simple_cst_equal (tree t1, tree t2)
4616 enum tree_code code1, code2;
4617 int cmp;
4618 int i;
4620 if (t1 == t2)
4621 return 1;
4622 if (t1 == 0 || t2 == 0)
4623 return 0;
4625 code1 = TREE_CODE (t1);
4626 code2 = TREE_CODE (t2);
4628 if (code1 == NOP_EXPR || code1 == CONVERT_EXPR || code1 == NON_LVALUE_EXPR)
4630 if (code2 == NOP_EXPR || code2 == CONVERT_EXPR
4631 || code2 == NON_LVALUE_EXPR)
4632 return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
4633 else
4634 return simple_cst_equal (TREE_OPERAND (t1, 0), t2);
4637 else if (code2 == NOP_EXPR || code2 == CONVERT_EXPR
4638 || code2 == NON_LVALUE_EXPR)
4639 return simple_cst_equal (t1, TREE_OPERAND (t2, 0));
4641 if (code1 != code2)
4642 return 0;
4644 switch (code1)
4646 case INTEGER_CST:
4647 return (TREE_INT_CST_LOW (t1) == TREE_INT_CST_LOW (t2)
4648 && TREE_INT_CST_HIGH (t1) == TREE_INT_CST_HIGH (t2));
4650 case REAL_CST:
4651 return REAL_VALUES_IDENTICAL (TREE_REAL_CST (t1), TREE_REAL_CST (t2));
4653 case STRING_CST:
4654 return (TREE_STRING_LENGTH (t1) == TREE_STRING_LENGTH (t2)
4655 && ! memcmp (TREE_STRING_POINTER (t1), TREE_STRING_POINTER (t2),
4656 TREE_STRING_LENGTH (t1)));
4658 case CONSTRUCTOR:
4660 unsigned HOST_WIDE_INT idx;
4661 VEC(constructor_elt, gc) *v1 = CONSTRUCTOR_ELTS (t1);
4662 VEC(constructor_elt, gc) *v2 = CONSTRUCTOR_ELTS (t2);
4664 if (VEC_length (constructor_elt, v1) != VEC_length (constructor_elt, v2))
4665 return false;
4667 for (idx = 0; idx < VEC_length (constructor_elt, v1); ++idx)
4668 /* ??? Should we handle also fields here? */
4669 if (!simple_cst_equal (VEC_index (constructor_elt, v1, idx)->value,
4670 VEC_index (constructor_elt, v2, idx)->value))
4671 return false;
4672 return true;
4675 case SAVE_EXPR:
4676 return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
4678 case CALL_EXPR:
4679 cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
4680 if (cmp <= 0)
4681 return cmp;
4682 return
4683 simple_cst_list_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
4685 case TARGET_EXPR:
4686 /* Special case: if either target is an unallocated VAR_DECL,
4687 it means that it's going to be unified with whatever the
4688 TARGET_EXPR is really supposed to initialize, so treat it
4689 as being equivalent to anything. */
4690 if ((TREE_CODE (TREE_OPERAND (t1, 0)) == VAR_DECL
4691 && DECL_NAME (TREE_OPERAND (t1, 0)) == NULL_TREE
4692 && !DECL_RTL_SET_P (TREE_OPERAND (t1, 0)))
4693 || (TREE_CODE (TREE_OPERAND (t2, 0)) == VAR_DECL
4694 && DECL_NAME (TREE_OPERAND (t2, 0)) == NULL_TREE
4695 && !DECL_RTL_SET_P (TREE_OPERAND (t2, 0))))
4696 cmp = 1;
4697 else
4698 cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
4700 if (cmp <= 0)
4701 return cmp;
4703 return simple_cst_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
4705 case WITH_CLEANUP_EXPR:
4706 cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
4707 if (cmp <= 0)
4708 return cmp;
4710 return simple_cst_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t1, 1));
4712 case COMPONENT_REF:
4713 if (TREE_OPERAND (t1, 1) == TREE_OPERAND (t2, 1))
4714 return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
4716 return 0;
4718 case VAR_DECL:
4719 case PARM_DECL:
4720 case CONST_DECL:
4721 case FUNCTION_DECL:
4722 return 0;
4724 default:
4725 break;
4728 /* This general rule works for most tree codes. All exceptions should be
4729 handled above. If this is a language-specific tree code, we can't
4730 trust what might be in the operand, so say we don't know
4731 the situation. */
4732 if ((int) code1 >= (int) LAST_AND_UNUSED_TREE_CODE)
4733 return -1;
4735 switch (TREE_CODE_CLASS (code1))
4737 case tcc_unary:
4738 case tcc_binary:
4739 case tcc_comparison:
4740 case tcc_expression:
4741 case tcc_reference:
4742 case tcc_statement:
4743 cmp = 1;
4744 for (i = 0; i < TREE_CODE_LENGTH (code1); i++)
4746 cmp = simple_cst_equal (TREE_OPERAND (t1, i), TREE_OPERAND (t2, i));
4747 if (cmp <= 0)
4748 return cmp;
4751 return cmp;
4753 default:
4754 return -1;
4758 /* Compare the value of T, an INTEGER_CST, with U, an unsigned integer value.
4759 Return -1, 0, or 1 if the value of T is less than, equal to, or greater
4760 than U, respectively. */
4763 compare_tree_int (tree t, unsigned HOST_WIDE_INT u)
4765 if (tree_int_cst_sgn (t) < 0)
4766 return -1;
4767 else if (TREE_INT_CST_HIGH (t) != 0)
4768 return 1;
4769 else if (TREE_INT_CST_LOW (t) == u)
4770 return 0;
4771 else if (TREE_INT_CST_LOW (t) < u)
4772 return -1;
4773 else
4774 return 1;
4777 /* Return true if CODE represents an associative tree code. Otherwise
4778 return false. */
4779 bool
4780 associative_tree_code (enum tree_code code)
4782 switch (code)
4784 case BIT_IOR_EXPR:
4785 case BIT_AND_EXPR:
4786 case BIT_XOR_EXPR:
4787 case PLUS_EXPR:
4788 case MULT_EXPR:
4789 case MIN_EXPR:
4790 case MAX_EXPR:
4791 return true;
4793 default:
4794 break;
4796 return false;
4799 /* Return true if CODE represents a commutative tree code. Otherwise
4800 return false. */
4801 bool
4802 commutative_tree_code (enum tree_code code)
4804 switch (code)
4806 case PLUS_EXPR:
4807 case MULT_EXPR:
4808 case MIN_EXPR:
4809 case MAX_EXPR:
4810 case BIT_IOR_EXPR:
4811 case BIT_XOR_EXPR:
4812 case BIT_AND_EXPR:
4813 case NE_EXPR:
4814 case EQ_EXPR:
4815 case UNORDERED_EXPR:
4816 case ORDERED_EXPR:
4817 case UNEQ_EXPR:
4818 case LTGT_EXPR:
4819 case TRUTH_AND_EXPR:
4820 case TRUTH_XOR_EXPR:
4821 case TRUTH_OR_EXPR:
4822 return true;
4824 default:
4825 break;
4827 return false;
4830 /* Generate a hash value for an expression. This can be used iteratively
4831 by passing a previous result as the "val" argument.
4833 This function is intended to produce the same hash for expressions which
4834 would compare equal using operand_equal_p. */
4836 hashval_t
4837 iterative_hash_expr (tree t, hashval_t val)
4839 int i;
4840 enum tree_code code;
4841 char class;
4843 if (t == NULL_TREE)
4844 return iterative_hash_pointer (t, val);
4846 code = TREE_CODE (t);
4848 switch (code)
4850 /* Alas, constants aren't shared, so we can't rely on pointer
4851 identity. */
4852 case INTEGER_CST:
4853 val = iterative_hash_host_wide_int (TREE_INT_CST_LOW (t), val);
4854 return iterative_hash_host_wide_int (TREE_INT_CST_HIGH (t), val);
4855 case REAL_CST:
4857 unsigned int val2 = real_hash (TREE_REAL_CST_PTR (t));
4859 return iterative_hash_hashval_t (val2, val);
4861 case STRING_CST:
4862 return iterative_hash (TREE_STRING_POINTER (t),
4863 TREE_STRING_LENGTH (t), val);
4864 case COMPLEX_CST:
4865 val = iterative_hash_expr (TREE_REALPART (t), val);
4866 return iterative_hash_expr (TREE_IMAGPART (t), val);
4867 case VECTOR_CST:
4868 return iterative_hash_expr (TREE_VECTOR_CST_ELTS (t), val);
4870 case SSA_NAME:
4871 case VALUE_HANDLE:
4872 /* we can just compare by pointer. */
4873 return iterative_hash_pointer (t, val);
4875 case TREE_LIST:
4876 /* A list of expressions, for a CALL_EXPR or as the elements of a
4877 VECTOR_CST. */
4878 for (; t; t = TREE_CHAIN (t))
4879 val = iterative_hash_expr (TREE_VALUE (t), val);
4880 return val;
4881 case CONSTRUCTOR:
4883 unsigned HOST_WIDE_INT idx;
4884 tree field, value;
4885 FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (t), idx, field, value)
4887 val = iterative_hash_expr (field, val);
4888 val = iterative_hash_expr (value, val);
4890 return val;
4892 case FUNCTION_DECL:
4893 /* When referring to a built-in FUNCTION_DECL, use the
4894 __builtin__ form. Otherwise nodes that compare equal
4895 according to operand_equal_p might get different
4896 hash codes. */
4897 if (DECL_BUILT_IN (t))
4899 val = iterative_hash_pointer (built_in_decls[DECL_FUNCTION_CODE (t)],
4900 val);
4901 return val;
4903 /* else FALL THROUGH */
4904 default:
4905 class = TREE_CODE_CLASS (code);
4907 if (class == tcc_declaration)
4909 /* DECL's have a unique ID */
4910 val = iterative_hash_host_wide_int (DECL_UID (t), val);
4912 else
4914 gcc_assert (IS_EXPR_CODE_CLASS (class));
4916 val = iterative_hash_object (code, val);
4918 /* Don't hash the type, that can lead to having nodes which
4919 compare equal according to operand_equal_p, but which
4920 have different hash codes. */
4921 if (code == NOP_EXPR
4922 || code == CONVERT_EXPR
4923 || code == NON_LVALUE_EXPR)
4925 /* Make sure to include signness in the hash computation. */
4926 val += TYPE_UNSIGNED (TREE_TYPE (t));
4927 val = iterative_hash_expr (TREE_OPERAND (t, 0), val);
4930 else if (commutative_tree_code (code))
4932 /* It's a commutative expression. We want to hash it the same
4933 however it appears. We do this by first hashing both operands
4934 and then rehashing based on the order of their independent
4935 hashes. */
4936 hashval_t one = iterative_hash_expr (TREE_OPERAND (t, 0), 0);
4937 hashval_t two = iterative_hash_expr (TREE_OPERAND (t, 1), 0);
4938 hashval_t t;
4940 if (one > two)
4941 t = one, one = two, two = t;
4943 val = iterative_hash_hashval_t (one, val);
4944 val = iterative_hash_hashval_t (two, val);
4946 else
4947 for (i = TREE_CODE_LENGTH (code) - 1; i >= 0; --i)
4948 val = iterative_hash_expr (TREE_OPERAND (t, i), val);
4950 return val;
4951 break;
4955 /* Constructors for pointer, array and function types.
4956 (RECORD_TYPE, UNION_TYPE and ENUMERAL_TYPE nodes are
4957 constructed by language-dependent code, not here.) */
4959 /* Construct, lay out and return the type of pointers to TO_TYPE with
4960 mode MODE. If CAN_ALIAS_ALL is TRUE, indicate this type can
4961 reference all of memory. If such a type has already been
4962 constructed, reuse it. */
4964 tree
4965 build_pointer_type_for_mode (tree to_type, enum machine_mode mode,
4966 bool can_alias_all)
4968 tree t;
4970 if (to_type == error_mark_node)
4971 return error_mark_node;
4973 /* In some cases, languages will have things that aren't a POINTER_TYPE
4974 (such as a RECORD_TYPE for fat pointers in Ada) as TYPE_POINTER_TO.
4975 In that case, return that type without regard to the rest of our
4976 operands.
4978 ??? This is a kludge, but consistent with the way this function has
4979 always operated and there doesn't seem to be a good way to avoid this
4980 at the moment. */
4981 if (TYPE_POINTER_TO (to_type) != 0
4982 && TREE_CODE (TYPE_POINTER_TO (to_type)) != POINTER_TYPE)
4983 return TYPE_POINTER_TO (to_type);
4985 /* First, if we already have a type for pointers to TO_TYPE and it's
4986 the proper mode, use it. */
4987 for (t = TYPE_POINTER_TO (to_type); t; t = TYPE_NEXT_PTR_TO (t))
4988 if (TYPE_MODE (t) == mode && TYPE_REF_CAN_ALIAS_ALL (t) == can_alias_all)
4989 return t;
4991 t = make_node (POINTER_TYPE);
4993 TREE_TYPE (t) = to_type;
4994 TYPE_MODE (t) = mode;
4995 TYPE_REF_CAN_ALIAS_ALL (t) = can_alias_all;
4996 TYPE_NEXT_PTR_TO (t) = TYPE_POINTER_TO (to_type);
4997 TYPE_POINTER_TO (to_type) = t;
4999 /* Lay out the type. This function has many callers that are concerned
5000 with expression-construction, and this simplifies them all. */
5001 layout_type (t);
5003 return t;
5006 /* By default build pointers in ptr_mode. */
5008 tree
5009 build_pointer_type (tree to_type)
5011 return build_pointer_type_for_mode (to_type, ptr_mode, false);
5014 /* Same as build_pointer_type_for_mode, but for REFERENCE_TYPE. */
5016 tree
5017 build_reference_type_for_mode (tree to_type, enum machine_mode mode,
5018 bool can_alias_all)
5020 tree t;
5022 /* In some cases, languages will have things that aren't a REFERENCE_TYPE
5023 (such as a RECORD_TYPE for fat pointers in Ada) as TYPE_REFERENCE_TO.
5024 In that case, return that type without regard to the rest of our
5025 operands.
5027 ??? This is a kludge, but consistent with the way this function has
5028 always operated and there doesn't seem to be a good way to avoid this
5029 at the moment. */
5030 if (TYPE_REFERENCE_TO (to_type) != 0
5031 && TREE_CODE (TYPE_REFERENCE_TO (to_type)) != REFERENCE_TYPE)
5032 return TYPE_REFERENCE_TO (to_type);
5034 /* First, if we already have a type for pointers to TO_TYPE and it's
5035 the proper mode, use it. */
5036 for (t = TYPE_REFERENCE_TO (to_type); t; t = TYPE_NEXT_REF_TO (t))
5037 if (TYPE_MODE (t) == mode && TYPE_REF_CAN_ALIAS_ALL (t) == can_alias_all)
5038 return t;
5040 t = make_node (REFERENCE_TYPE);
5042 TREE_TYPE (t) = to_type;
5043 TYPE_MODE (t) = mode;
5044 TYPE_REF_CAN_ALIAS_ALL (t) = can_alias_all;
5045 TYPE_NEXT_REF_TO (t) = TYPE_REFERENCE_TO (to_type);
5046 TYPE_REFERENCE_TO (to_type) = t;
5048 layout_type (t);
5050 return t;
5054 /* Build the node for the type of references-to-TO_TYPE by default
5055 in ptr_mode. */
5057 tree
5058 build_reference_type (tree to_type)
5060 return build_reference_type_for_mode (to_type, ptr_mode, false);
5063 /* Build a type that is compatible with t but has no cv quals anywhere
5064 in its type, thus
5066 const char *const *const * -> char ***. */
5068 tree
5069 build_type_no_quals (tree t)
5071 switch (TREE_CODE (t))
5073 case POINTER_TYPE:
5074 return build_pointer_type_for_mode (build_type_no_quals (TREE_TYPE (t)),
5075 TYPE_MODE (t),
5076 TYPE_REF_CAN_ALIAS_ALL (t));
5077 case REFERENCE_TYPE:
5078 return
5079 build_reference_type_for_mode (build_type_no_quals (TREE_TYPE (t)),
5080 TYPE_MODE (t),
5081 TYPE_REF_CAN_ALIAS_ALL (t));
5082 default:
5083 return TYPE_MAIN_VARIANT (t);
5087 /* Create a type of integers to be the TYPE_DOMAIN of an ARRAY_TYPE.
5088 MAXVAL should be the maximum value in the domain
5089 (one less than the length of the array).
5091 The maximum value that MAXVAL can have is INT_MAX for a HOST_WIDE_INT.
5092 We don't enforce this limit, that is up to caller (e.g. language front end).
5093 The limit exists because the result is a signed type and we don't handle
5094 sizes that use more than one HOST_WIDE_INT. */
5096 tree
5097 build_index_type (tree maxval)
5099 tree itype = make_node (INTEGER_TYPE);
5101 TREE_TYPE (itype) = sizetype;
5102 TYPE_PRECISION (itype) = TYPE_PRECISION (sizetype);
5103 TYPE_MIN_VALUE (itype) = size_zero_node;
5104 TYPE_MAX_VALUE (itype) = fold_convert (sizetype, maxval);
5105 TYPE_MODE (itype) = TYPE_MODE (sizetype);
5106 TYPE_SIZE (itype) = TYPE_SIZE (sizetype);
5107 TYPE_SIZE_UNIT (itype) = TYPE_SIZE_UNIT (sizetype);
5108 TYPE_ALIGN (itype) = TYPE_ALIGN (sizetype);
5109 TYPE_USER_ALIGN (itype) = TYPE_USER_ALIGN (sizetype);
5111 if (host_integerp (maxval, 1))
5112 return type_hash_canon (tree_low_cst (maxval, 1), itype);
5113 else
5114 return itype;
5117 /* Builds a signed or unsigned integer type of precision PRECISION.
5118 Used for C bitfields whose precision does not match that of
5119 built-in target types. */
5120 tree
5121 build_nonstandard_integer_type (unsigned HOST_WIDE_INT precision,
5122 int unsignedp)
5124 tree itype = make_node (INTEGER_TYPE);
5126 TYPE_PRECISION (itype) = precision;
5128 if (unsignedp)
5129 fixup_unsigned_type (itype);
5130 else
5131 fixup_signed_type (itype);
5133 if (host_integerp (TYPE_MAX_VALUE (itype), 1))
5134 return type_hash_canon (tree_low_cst (TYPE_MAX_VALUE (itype), 1), itype);
5136 return itype;
5139 /* Create a range of some discrete type TYPE (an INTEGER_TYPE,
5140 ENUMERAL_TYPE or BOOLEAN_TYPE), with low bound LOWVAL and
5141 high bound HIGHVAL. If TYPE is NULL, sizetype is used. */
5143 tree
5144 build_range_type (tree type, tree lowval, tree highval)
5146 tree itype = make_node (INTEGER_TYPE);
5148 TREE_TYPE (itype) = type;
5149 if (type == NULL_TREE)
5150 type = sizetype;
5152 TYPE_MIN_VALUE (itype) = fold_convert (type, lowval);
5153 TYPE_MAX_VALUE (itype) = highval ? fold_convert (type, highval) : NULL;
5155 TYPE_PRECISION (itype) = TYPE_PRECISION (type);
5156 TYPE_MODE (itype) = TYPE_MODE (type);
5157 TYPE_SIZE (itype) = TYPE_SIZE (type);
5158 TYPE_SIZE_UNIT (itype) = TYPE_SIZE_UNIT (type);
5159 TYPE_ALIGN (itype) = TYPE_ALIGN (type);
5160 TYPE_USER_ALIGN (itype) = TYPE_USER_ALIGN (type);
5162 if (host_integerp (lowval, 0) && highval != 0 && host_integerp (highval, 0))
5163 return type_hash_canon (tree_low_cst (highval, 0)
5164 - tree_low_cst (lowval, 0),
5165 itype);
5166 else
5167 return itype;
5170 /* Just like build_index_type, but takes lowval and highval instead
5171 of just highval (maxval). */
5173 tree
5174 build_index_2_type (tree lowval, tree highval)
5176 return build_range_type (sizetype, lowval, highval);
5179 /* Construct, lay out and return the type of arrays of elements with ELT_TYPE
5180 and number of elements specified by the range of values of INDEX_TYPE.
5181 If such a type has already been constructed, reuse it. */
5183 tree
5184 build_array_type (tree elt_type, tree index_type)
5186 tree t;
5187 hashval_t hashcode = 0;
5189 if (TREE_CODE (elt_type) == FUNCTION_TYPE)
5191 error ("arrays of functions are not meaningful");
5192 elt_type = integer_type_node;
5195 t = make_node (ARRAY_TYPE);
5196 TREE_TYPE (t) = elt_type;
5197 TYPE_DOMAIN (t) = index_type;
5199 if (index_type == 0)
5201 tree save = t;
5202 hashcode = iterative_hash_object (TYPE_HASH (elt_type), hashcode);
5203 t = type_hash_canon (hashcode, t);
5204 if (save == t)
5205 layout_type (t);
5206 return t;
5209 hashcode = iterative_hash_object (TYPE_HASH (elt_type), hashcode);
5210 hashcode = iterative_hash_object (TYPE_HASH (index_type), hashcode);
5211 t = type_hash_canon (hashcode, t);
5213 if (!COMPLETE_TYPE_P (t))
5214 layout_type (t);
5215 return t;
5218 /* Return the TYPE of the elements comprising
5219 the innermost dimension of ARRAY. */
5221 tree
5222 get_inner_array_type (tree array)
5224 tree type = TREE_TYPE (array);
5226 while (TREE_CODE (type) == ARRAY_TYPE)
5227 type = TREE_TYPE (type);
5229 return type;
5232 /* Construct, lay out and return
5233 the type of functions returning type VALUE_TYPE
5234 given arguments of types ARG_TYPES.
5235 ARG_TYPES is a chain of TREE_LIST nodes whose TREE_VALUEs
5236 are data type nodes for the arguments of the function.
5237 If such a type has already been constructed, reuse it. */
5239 tree
5240 build_function_type (tree value_type, tree arg_types)
5242 tree t;
5243 hashval_t hashcode = 0;
5245 if (TREE_CODE (value_type) == FUNCTION_TYPE)
5247 error ("function return type cannot be function");
5248 value_type = integer_type_node;
5251 /* Make a node of the sort we want. */
5252 t = make_node (FUNCTION_TYPE);
5253 TREE_TYPE (t) = value_type;
5254 TYPE_ARG_TYPES (t) = arg_types;
5256 /* If we already have such a type, use the old one. */
5257 hashcode = iterative_hash_object (TYPE_HASH (value_type), hashcode);
5258 hashcode = type_hash_list (arg_types, hashcode);
5259 t = type_hash_canon (hashcode, t);
5261 if (!COMPLETE_TYPE_P (t))
5262 layout_type (t);
5263 return t;
5266 /* Build a function type. The RETURN_TYPE is the type returned by the
5267 function. If additional arguments are provided, they are
5268 additional argument types. The list of argument types must always
5269 be terminated by NULL_TREE. */
5271 tree
5272 build_function_type_list (tree return_type, ...)
5274 tree t, args, last;
5275 va_list p;
5277 va_start (p, return_type);
5279 t = va_arg (p, tree);
5280 for (args = NULL_TREE; t != NULL_TREE; t = va_arg (p, tree))
5281 args = tree_cons (NULL_TREE, t, args);
5283 if (args == NULL_TREE)
5284 args = void_list_node;
5285 else
5287 last = args;
5288 args = nreverse (args);
5289 TREE_CHAIN (last) = void_list_node;
5291 args = build_function_type (return_type, args);
5293 va_end (p);
5294 return args;
5297 /* Build a METHOD_TYPE for a member of BASETYPE. The RETTYPE (a TYPE)
5298 and ARGTYPES (a TREE_LIST) are the return type and arguments types
5299 for the method. An implicit additional parameter (of type
5300 pointer-to-BASETYPE) is added to the ARGTYPES. */
5302 tree
5303 build_method_type_directly (tree basetype,
5304 tree rettype,
5305 tree argtypes)
5307 tree t;
5308 tree ptype;
5309 int hashcode = 0;
5311 /* Make a node of the sort we want. */
5312 t = make_node (METHOD_TYPE);
5314 TYPE_METHOD_BASETYPE (t) = TYPE_MAIN_VARIANT (basetype);
5315 TREE_TYPE (t) = rettype;
5316 ptype = build_pointer_type (basetype);
5318 /* The actual arglist for this function includes a "hidden" argument
5319 which is "this". Put it into the list of argument types. */
5320 argtypes = tree_cons (NULL_TREE, ptype, argtypes);
5321 TYPE_ARG_TYPES (t) = argtypes;
5323 /* If we already have such a type, use the old one. */
5324 hashcode = iterative_hash_object (TYPE_HASH (basetype), hashcode);
5325 hashcode = iterative_hash_object (TYPE_HASH (rettype), hashcode);
5326 hashcode = type_hash_list (argtypes, hashcode);
5327 t = type_hash_canon (hashcode, t);
5329 if (!COMPLETE_TYPE_P (t))
5330 layout_type (t);
5332 return t;
5335 /* Construct, lay out and return the type of methods belonging to class
5336 BASETYPE and whose arguments and values are described by TYPE.
5337 If that type exists already, reuse it.
5338 TYPE must be a FUNCTION_TYPE node. */
5340 tree
5341 build_method_type (tree basetype, tree type)
5343 gcc_assert (TREE_CODE (type) == FUNCTION_TYPE);
5345 return build_method_type_directly (basetype,
5346 TREE_TYPE (type),
5347 TYPE_ARG_TYPES (type));
5350 /* Construct, lay out and return the type of offsets to a value
5351 of type TYPE, within an object of type BASETYPE.
5352 If a suitable offset type exists already, reuse it. */
5354 tree
5355 build_offset_type (tree basetype, tree type)
5357 tree t;
5358 hashval_t hashcode = 0;
5360 /* Make a node of the sort we want. */
5361 t = make_node (OFFSET_TYPE);
5363 TYPE_OFFSET_BASETYPE (t) = TYPE_MAIN_VARIANT (basetype);
5364 TREE_TYPE (t) = type;
5366 /* If we already have such a type, use the old one. */
5367 hashcode = iterative_hash_object (TYPE_HASH (basetype), hashcode);
5368 hashcode = iterative_hash_object (TYPE_HASH (type), hashcode);
5369 t = type_hash_canon (hashcode, t);
5371 if (!COMPLETE_TYPE_P (t))
5372 layout_type (t);
5374 return t;
5377 /* Create a complex type whose components are COMPONENT_TYPE. */
5379 tree
5380 build_complex_type (tree component_type)
5382 tree t;
5383 hashval_t hashcode;
5385 /* Make a node of the sort we want. */
5386 t = make_node (COMPLEX_TYPE);
5388 TREE_TYPE (t) = TYPE_MAIN_VARIANT (component_type);
5390 /* If we already have such a type, use the old one. */
5391 hashcode = iterative_hash_object (TYPE_HASH (component_type), 0);
5392 t = type_hash_canon (hashcode, t);
5394 if (!COMPLETE_TYPE_P (t))
5395 layout_type (t);
5397 /* If we are writing Dwarf2 output we need to create a name,
5398 since complex is a fundamental type. */
5399 if ((write_symbols == DWARF2_DEBUG || write_symbols == VMS_AND_DWARF2_DEBUG)
5400 && ! TYPE_NAME (t))
5402 const char *name;
5403 if (component_type == char_type_node)
5404 name = "complex char";
5405 else if (component_type == signed_char_type_node)
5406 name = "complex signed char";
5407 else if (component_type == unsigned_char_type_node)
5408 name = "complex unsigned char";
5409 else if (component_type == short_integer_type_node)
5410 name = "complex short int";
5411 else if (component_type == short_unsigned_type_node)
5412 name = "complex short unsigned int";
5413 else if (component_type == integer_type_node)
5414 name = "complex int";
5415 else if (component_type == unsigned_type_node)
5416 name = "complex unsigned int";
5417 else if (component_type == long_integer_type_node)
5418 name = "complex long int";
5419 else if (component_type == long_unsigned_type_node)
5420 name = "complex long unsigned int";
5421 else if (component_type == long_long_integer_type_node)
5422 name = "complex long long int";
5423 else if (component_type == long_long_unsigned_type_node)
5424 name = "complex long long unsigned int";
5425 else
5426 name = 0;
5428 if (name != 0)
5429 TYPE_NAME (t) = get_identifier (name);
5432 return build_qualified_type (t, TYPE_QUALS (component_type));
5435 /* Return OP, stripped of any conversions to wider types as much as is safe.
5436 Converting the value back to OP's type makes a value equivalent to OP.
5438 If FOR_TYPE is nonzero, we return a value which, if converted to
5439 type FOR_TYPE, would be equivalent to converting OP to type FOR_TYPE.
5441 If FOR_TYPE is nonzero, unaligned bit-field references may be changed to the
5442 narrowest type that can hold the value, even if they don't exactly fit.
5443 Otherwise, bit-field references are changed to a narrower type
5444 only if they can be fetched directly from memory in that type.
5446 OP must have integer, real or enumeral type. Pointers are not allowed!
5448 There are some cases where the obvious value we could return
5449 would regenerate to OP if converted to OP's type,
5450 but would not extend like OP to wider types.
5451 If FOR_TYPE indicates such extension is contemplated, we eschew such values.
5452 For example, if OP is (unsigned short)(signed char)-1,
5453 we avoid returning (signed char)-1 if FOR_TYPE is int,
5454 even though extending that to an unsigned short would regenerate OP,
5455 since the result of extending (signed char)-1 to (int)
5456 is different from (int) OP. */
5458 tree
5459 get_unwidened (tree op, tree for_type)
5461 /* Set UNS initially if converting OP to FOR_TYPE is a zero-extension. */
5462 tree type = TREE_TYPE (op);
5463 unsigned final_prec
5464 = TYPE_PRECISION (for_type != 0 ? for_type : type);
5465 int uns
5466 = (for_type != 0 && for_type != type
5467 && final_prec > TYPE_PRECISION (type)
5468 && TYPE_UNSIGNED (type));
5469 tree win = op;
5471 while (TREE_CODE (op) == NOP_EXPR
5472 || TREE_CODE (op) == CONVERT_EXPR)
5474 int bitschange;
5476 /* TYPE_PRECISION on vector types has different meaning
5477 (TYPE_VECTOR_SUBPARTS) and casts from vectors are view conversions,
5478 so avoid them here. */
5479 if (TREE_CODE (TREE_TYPE (TREE_OPERAND (op, 0))) == VECTOR_TYPE)
5480 break;
5482 bitschange = TYPE_PRECISION (TREE_TYPE (op))
5483 - TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (op, 0)));
5485 /* Truncations are many-one so cannot be removed.
5486 Unless we are later going to truncate down even farther. */
5487 if (bitschange < 0
5488 && final_prec > TYPE_PRECISION (TREE_TYPE (op)))
5489 break;
5491 /* See what's inside this conversion. If we decide to strip it,
5492 we will set WIN. */
5493 op = TREE_OPERAND (op, 0);
5495 /* If we have not stripped any zero-extensions (uns is 0),
5496 we can strip any kind of extension.
5497 If we have previously stripped a zero-extension,
5498 only zero-extensions can safely be stripped.
5499 Any extension can be stripped if the bits it would produce
5500 are all going to be discarded later by truncating to FOR_TYPE. */
5502 if (bitschange > 0)
5504 if (! uns || final_prec <= TYPE_PRECISION (TREE_TYPE (op)))
5505 win = op;
5506 /* TYPE_UNSIGNED says whether this is a zero-extension.
5507 Let's avoid computing it if it does not affect WIN
5508 and if UNS will not be needed again. */
5509 if ((uns
5510 || TREE_CODE (op) == NOP_EXPR
5511 || TREE_CODE (op) == CONVERT_EXPR)
5512 && TYPE_UNSIGNED (TREE_TYPE (op)))
5514 uns = 1;
5515 win = op;
5520 if (TREE_CODE (op) == COMPONENT_REF
5521 /* Since type_for_size always gives an integer type. */
5522 && TREE_CODE (type) != REAL_TYPE
5523 /* Don't crash if field not laid out yet. */
5524 && DECL_SIZE (TREE_OPERAND (op, 1)) != 0
5525 && host_integerp (DECL_SIZE (TREE_OPERAND (op, 1)), 1))
5527 unsigned int innerprec
5528 = tree_low_cst (DECL_SIZE (TREE_OPERAND (op, 1)), 1);
5529 int unsignedp = (DECL_UNSIGNED (TREE_OPERAND (op, 1))
5530 || TYPE_UNSIGNED (TREE_TYPE (TREE_OPERAND (op, 1))));
5531 type = lang_hooks.types.type_for_size (innerprec, unsignedp);
5533 /* We can get this structure field in the narrowest type it fits in.
5534 If FOR_TYPE is 0, do this only for a field that matches the
5535 narrower type exactly and is aligned for it
5536 The resulting extension to its nominal type (a fullword type)
5537 must fit the same conditions as for other extensions. */
5539 if (type != 0
5540 && INT_CST_LT_UNSIGNED (TYPE_SIZE (type), TYPE_SIZE (TREE_TYPE (op)))
5541 && (for_type || ! DECL_BIT_FIELD (TREE_OPERAND (op, 1)))
5542 && (! uns || final_prec <= innerprec || unsignedp))
5544 win = build3 (COMPONENT_REF, type, TREE_OPERAND (op, 0),
5545 TREE_OPERAND (op, 1), NULL_TREE);
5546 TREE_SIDE_EFFECTS (win) = TREE_SIDE_EFFECTS (op);
5547 TREE_THIS_VOLATILE (win) = TREE_THIS_VOLATILE (op);
5551 return win;
5554 /* Return OP or a simpler expression for a narrower value
5555 which can be sign-extended or zero-extended to give back OP.
5556 Store in *UNSIGNEDP_PTR either 1 if the value should be zero-extended
5557 or 0 if the value should be sign-extended. */
5559 tree
5560 get_narrower (tree op, int *unsignedp_ptr)
5562 int uns = 0;
5563 int first = 1;
5564 tree win = op;
5565 bool integral_p = INTEGRAL_TYPE_P (TREE_TYPE (op));
5567 while (TREE_CODE (op) == NOP_EXPR)
5569 int bitschange
5570 = (TYPE_PRECISION (TREE_TYPE (op))
5571 - TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (op, 0))));
5573 /* Truncations are many-one so cannot be removed. */
5574 if (bitschange < 0)
5575 break;
5577 /* See what's inside this conversion. If we decide to strip it,
5578 we will set WIN. */
5580 if (bitschange > 0)
5582 op = TREE_OPERAND (op, 0);
5583 /* An extension: the outermost one can be stripped,
5584 but remember whether it is zero or sign extension. */
5585 if (first)
5586 uns = TYPE_UNSIGNED (TREE_TYPE (op));
5587 /* Otherwise, if a sign extension has been stripped,
5588 only sign extensions can now be stripped;
5589 if a zero extension has been stripped, only zero-extensions. */
5590 else if (uns != TYPE_UNSIGNED (TREE_TYPE (op)))
5591 break;
5592 first = 0;
5594 else /* bitschange == 0 */
5596 /* A change in nominal type can always be stripped, but we must
5597 preserve the unsignedness. */
5598 if (first)
5599 uns = TYPE_UNSIGNED (TREE_TYPE (op));
5600 first = 0;
5601 op = TREE_OPERAND (op, 0);
5602 /* Keep trying to narrow, but don't assign op to win if it
5603 would turn an integral type into something else. */
5604 if (INTEGRAL_TYPE_P (TREE_TYPE (op)) != integral_p)
5605 continue;
5608 win = op;
5611 if (TREE_CODE (op) == COMPONENT_REF
5612 /* Since type_for_size always gives an integer type. */
5613 && TREE_CODE (TREE_TYPE (op)) != REAL_TYPE
5614 /* Ensure field is laid out already. */
5615 && DECL_SIZE (TREE_OPERAND (op, 1)) != 0
5616 && host_integerp (DECL_SIZE (TREE_OPERAND (op, 1)), 1))
5618 unsigned HOST_WIDE_INT innerprec
5619 = tree_low_cst (DECL_SIZE (TREE_OPERAND (op, 1)), 1);
5620 int unsignedp = (DECL_UNSIGNED (TREE_OPERAND (op, 1))
5621 || TYPE_UNSIGNED (TREE_TYPE (TREE_OPERAND (op, 1))));
5622 tree type = lang_hooks.types.type_for_size (innerprec, unsignedp);
5624 /* We can get this structure field in a narrower type that fits it,
5625 but the resulting extension to its nominal type (a fullword type)
5626 must satisfy the same conditions as for other extensions.
5628 Do this only for fields that are aligned (not bit-fields),
5629 because when bit-field insns will be used there is no
5630 advantage in doing this. */
5632 if (innerprec < TYPE_PRECISION (TREE_TYPE (op))
5633 && ! DECL_BIT_FIELD (TREE_OPERAND (op, 1))
5634 && (first || uns == DECL_UNSIGNED (TREE_OPERAND (op, 1)))
5635 && type != 0)
5637 if (first)
5638 uns = DECL_UNSIGNED (TREE_OPERAND (op, 1));
5639 win = build3 (COMPONENT_REF, type, TREE_OPERAND (op, 0),
5640 TREE_OPERAND (op, 1), NULL_TREE);
5641 TREE_SIDE_EFFECTS (win) = TREE_SIDE_EFFECTS (op);
5642 TREE_THIS_VOLATILE (win) = TREE_THIS_VOLATILE (op);
5645 *unsignedp_ptr = uns;
5646 return win;
5649 /* Nonzero if integer constant C has a value that is permissible
5650 for type TYPE (an INTEGER_TYPE). */
5653 int_fits_type_p (tree c, tree type)
5655 tree type_low_bound = TYPE_MIN_VALUE (type);
5656 tree type_high_bound = TYPE_MAX_VALUE (type);
5657 bool ok_for_low_bound, ok_for_high_bound;
5658 tree tmp;
5660 /* If at least one bound of the type is a constant integer, we can check
5661 ourselves and maybe make a decision. If no such decision is possible, but
5662 this type is a subtype, try checking against that. Otherwise, use
5663 force_fit_type, which checks against the precision.
5665 Compute the status for each possibly constant bound, and return if we see
5666 one does not match. Use ok_for_xxx_bound for this purpose, assigning -1
5667 for "unknown if constant fits", 0 for "constant known *not* to fit" and 1
5668 for "constant known to fit". */
5670 /* Check if C >= type_low_bound. */
5671 if (type_low_bound && TREE_CODE (type_low_bound) == INTEGER_CST)
5673 if (tree_int_cst_lt (c, type_low_bound))
5674 return 0;
5675 ok_for_low_bound = true;
5677 else
5678 ok_for_low_bound = false;
5680 /* Check if c <= type_high_bound. */
5681 if (type_high_bound && TREE_CODE (type_high_bound) == INTEGER_CST)
5683 if (tree_int_cst_lt (type_high_bound, c))
5684 return 0;
5685 ok_for_high_bound = true;
5687 else
5688 ok_for_high_bound = false;
5690 /* If the constant fits both bounds, the result is known. */
5691 if (ok_for_low_bound && ok_for_high_bound)
5692 return 1;
5694 /* Perform some generic filtering which may allow making a decision
5695 even if the bounds are not constant. First, negative integers
5696 never fit in unsigned types, */
5697 if (TYPE_UNSIGNED (type) && tree_int_cst_sgn (c) < 0)
5698 return 0;
5700 /* Second, narrower types always fit in wider ones. */
5701 if (TYPE_PRECISION (type) > TYPE_PRECISION (TREE_TYPE (c)))
5702 return 1;
5704 /* Third, unsigned integers with top bit set never fit signed types. */
5705 if (! TYPE_UNSIGNED (type)
5706 && TYPE_UNSIGNED (TREE_TYPE (c))
5707 && tree_int_cst_msb (c))
5708 return 0;
5710 /* If we haven't been able to decide at this point, there nothing more we
5711 can check ourselves here. Look at the base type if we have one and it
5712 has the same precision. */
5713 if (TREE_CODE (type) == INTEGER_TYPE
5714 && TREE_TYPE (type) != 0
5715 && TYPE_PRECISION (type) == TYPE_PRECISION (TREE_TYPE (type)))
5716 return int_fits_type_p (c, TREE_TYPE (type));
5718 /* Or to force_fit_type, if nothing else. */
5719 tmp = copy_node (c);
5720 TREE_TYPE (tmp) = type;
5721 tmp = force_fit_type (tmp, -1, false, false);
5722 return TREE_INT_CST_HIGH (tmp) == TREE_INT_CST_HIGH (c)
5723 && TREE_INT_CST_LOW (tmp) == TREE_INT_CST_LOW (c);
5726 /* Subprogram of following function. Called by walk_tree.
5728 Return *TP if it is an automatic variable or parameter of the
5729 function passed in as DATA. */
5731 static tree
5732 find_var_from_fn (tree *tp, int *walk_subtrees, void *data)
5734 tree fn = (tree) data;
5736 if (TYPE_P (*tp))
5737 *walk_subtrees = 0;
5739 else if (DECL_P (*tp)
5740 && lang_hooks.tree_inlining.auto_var_in_fn_p (*tp, fn))
5741 return *tp;
5743 return NULL_TREE;
5746 /* Returns true if T is, contains, or refers to a type with variable
5747 size. For METHOD_TYPEs and FUNCTION_TYPEs we exclude the
5748 arguments, but not the return type. If FN is nonzero, only return
5749 true if a modifier of the type or position of FN is a variable or
5750 parameter inside FN.
5752 This concept is more general than that of C99 'variably modified types':
5753 in C99, a struct type is never variably modified because a VLA may not
5754 appear as a structure member. However, in GNU C code like:
5756 struct S { int i[f()]; };
5758 is valid, and other languages may define similar constructs. */
5760 bool
5761 variably_modified_type_p (tree type, tree fn)
5763 tree t;
5765 /* Test if T is either variable (if FN is zero) or an expression containing
5766 a variable in FN. */
5767 #define RETURN_TRUE_IF_VAR(T) \
5768 do { tree _t = (T); \
5769 if (_t && _t != error_mark_node && TREE_CODE (_t) != INTEGER_CST \
5770 && (!fn || walk_tree (&_t, find_var_from_fn, fn, NULL))) \
5771 return true; } while (0)
5773 if (type == error_mark_node)
5774 return false;
5776 /* If TYPE itself has variable size, it is variably modified. */
5777 RETURN_TRUE_IF_VAR (TYPE_SIZE (type));
5778 RETURN_TRUE_IF_VAR (TYPE_SIZE_UNIT (type));
5780 switch (TREE_CODE (type))
5782 case POINTER_TYPE:
5783 case REFERENCE_TYPE:
5784 case VECTOR_TYPE:
5785 if (variably_modified_type_p (TREE_TYPE (type), fn))
5786 return true;
5787 break;
5789 case FUNCTION_TYPE:
5790 case METHOD_TYPE:
5791 /* If TYPE is a function type, it is variably modified if the
5792 return type is variably modified. */
5793 if (variably_modified_type_p (TREE_TYPE (type), fn))
5794 return true;
5795 break;
5797 case INTEGER_TYPE:
5798 case REAL_TYPE:
5799 case ENUMERAL_TYPE:
5800 case BOOLEAN_TYPE:
5801 /* Scalar types are variably modified if their end points
5802 aren't constant. */
5803 RETURN_TRUE_IF_VAR (TYPE_MIN_VALUE (type));
5804 RETURN_TRUE_IF_VAR (TYPE_MAX_VALUE (type));
5805 break;
5807 case RECORD_TYPE:
5808 case UNION_TYPE:
5809 case QUAL_UNION_TYPE:
5810 /* We can't see if any of the fields are variably-modified by the
5811 definition we normally use, since that would produce infinite
5812 recursion via pointers. */
5813 /* This is variably modified if some field's type is. */
5814 for (t = TYPE_FIELDS (type); t; t = TREE_CHAIN (t))
5815 if (TREE_CODE (t) == FIELD_DECL)
5817 RETURN_TRUE_IF_VAR (DECL_FIELD_OFFSET (t));
5818 RETURN_TRUE_IF_VAR (DECL_SIZE (t));
5819 RETURN_TRUE_IF_VAR (DECL_SIZE_UNIT (t));
5821 if (TREE_CODE (type) == QUAL_UNION_TYPE)
5822 RETURN_TRUE_IF_VAR (DECL_QUALIFIER (t));
5824 break;
5826 case ARRAY_TYPE:
5827 /* Do not call ourselves to avoid infinite recursion. This is
5828 variably modified if the element type is. */
5829 RETURN_TRUE_IF_VAR (TYPE_SIZE (TREE_TYPE (type)));
5830 RETURN_TRUE_IF_VAR (TYPE_SIZE_UNIT (TREE_TYPE (type)));
5831 break;
5833 default:
5834 break;
5837 /* The current language may have other cases to check, but in general,
5838 all other types are not variably modified. */
5839 return lang_hooks.tree_inlining.var_mod_type_p (type, fn);
5841 #undef RETURN_TRUE_IF_VAR
5844 /* Given a DECL or TYPE, return the scope in which it was declared, or
5845 NULL_TREE if there is no containing scope. */
5847 tree
5848 get_containing_scope (tree t)
5850 return (TYPE_P (t) ? TYPE_CONTEXT (t) : DECL_CONTEXT (t));
5853 /* Return the innermost context enclosing DECL that is
5854 a FUNCTION_DECL, or zero if none. */
5856 tree
5857 decl_function_context (tree decl)
5859 tree context;
5861 if (TREE_CODE (decl) == ERROR_MARK)
5862 return 0;
5864 /* C++ virtual functions use DECL_CONTEXT for the class of the vtable
5865 where we look up the function at runtime. Such functions always take
5866 a first argument of type 'pointer to real context'.
5868 C++ should really be fixed to use DECL_CONTEXT for the real context,
5869 and use something else for the "virtual context". */
5870 else if (TREE_CODE (decl) == FUNCTION_DECL && DECL_VINDEX (decl))
5871 context
5872 = TYPE_MAIN_VARIANT
5873 (TREE_TYPE (TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (decl)))));
5874 else
5875 context = DECL_CONTEXT (decl);
5877 while (context && TREE_CODE (context) != FUNCTION_DECL)
5879 if (TREE_CODE (context) == BLOCK)
5880 context = BLOCK_SUPERCONTEXT (context);
5881 else
5882 context = get_containing_scope (context);
5885 return context;
5888 /* Return the innermost context enclosing DECL that is
5889 a RECORD_TYPE, UNION_TYPE or QUAL_UNION_TYPE, or zero if none.
5890 TYPE_DECLs and FUNCTION_DECLs are transparent to this function. */
5892 tree
5893 decl_type_context (tree decl)
5895 tree context = DECL_CONTEXT (decl);
5897 while (context)
5898 switch (TREE_CODE (context))
5900 case NAMESPACE_DECL:
5901 case TRANSLATION_UNIT_DECL:
5902 return NULL_TREE;
5904 case RECORD_TYPE:
5905 case UNION_TYPE:
5906 case QUAL_UNION_TYPE:
5907 return context;
5909 case TYPE_DECL:
5910 case FUNCTION_DECL:
5911 context = DECL_CONTEXT (context);
5912 break;
5914 case BLOCK:
5915 context = BLOCK_SUPERCONTEXT (context);
5916 break;
5918 default:
5919 gcc_unreachable ();
5922 return NULL_TREE;
5925 /* CALL is a CALL_EXPR. Return the declaration for the function
5926 called, or NULL_TREE if the called function cannot be
5927 determined. */
5929 tree
5930 get_callee_fndecl (tree call)
5932 tree addr;
5934 if (call == error_mark_node)
5935 return call;
5937 /* It's invalid to call this function with anything but a
5938 CALL_EXPR. */
5939 gcc_assert (TREE_CODE (call) == CALL_EXPR);
5941 /* The first operand to the CALL is the address of the function
5942 called. */
5943 addr = TREE_OPERAND (call, 0);
5945 STRIP_NOPS (addr);
5947 /* If this is a readonly function pointer, extract its initial value. */
5948 if (DECL_P (addr) && TREE_CODE (addr) != FUNCTION_DECL
5949 && TREE_READONLY (addr) && ! TREE_THIS_VOLATILE (addr)
5950 && DECL_INITIAL (addr))
5951 addr = DECL_INITIAL (addr);
5953 /* If the address is just `&f' for some function `f', then we know
5954 that `f' is being called. */
5955 if (TREE_CODE (addr) == ADDR_EXPR
5956 && TREE_CODE (TREE_OPERAND (addr, 0)) == FUNCTION_DECL)
5957 return TREE_OPERAND (addr, 0);
5959 /* We couldn't figure out what was being called. Maybe the front
5960 end has some idea. */
5961 return lang_hooks.lang_get_callee_fndecl (call);
5964 /* Print debugging information about tree nodes generated during the compile,
5965 and any language-specific information. */
5967 void
5968 dump_tree_statistics (void)
5970 #ifdef GATHER_STATISTICS
5971 int i;
5972 int total_nodes, total_bytes;
5973 #endif
5975 fprintf (stderr, "\n??? tree nodes created\n\n");
5976 #ifdef GATHER_STATISTICS
5977 fprintf (stderr, "Kind Nodes Bytes\n");
5978 fprintf (stderr, "---------------------------------------\n");
5979 total_nodes = total_bytes = 0;
5980 for (i = 0; i < (int) all_kinds; i++)
5982 fprintf (stderr, "%-20s %7d %10d\n", tree_node_kind_names[i],
5983 tree_node_counts[i], tree_node_sizes[i]);
5984 total_nodes += tree_node_counts[i];
5985 total_bytes += tree_node_sizes[i];
5987 fprintf (stderr, "---------------------------------------\n");
5988 fprintf (stderr, "%-20s %7d %10d\n", "Total", total_nodes, total_bytes);
5989 fprintf (stderr, "---------------------------------------\n");
5990 ssanames_print_statistics ();
5991 phinodes_print_statistics ();
5992 #else
5993 fprintf (stderr, "(No per-node statistics)\n");
5994 #endif
5995 print_type_hash_statistics ();
5996 print_debug_expr_statistics ();
5997 print_value_expr_statistics ();
5998 print_restrict_base_statistics ();
5999 lang_hooks.print_statistics ();
6002 #define FILE_FUNCTION_FORMAT "_GLOBAL__%s_%s"
6004 /* Generate a crc32 of a string. */
6006 unsigned
6007 crc32_string (unsigned chksum, const char *string)
6011 unsigned value = *string << 24;
6012 unsigned ix;
6014 for (ix = 8; ix--; value <<= 1)
6016 unsigned feedback;
6018 feedback = (value ^ chksum) & 0x80000000 ? 0x04c11db7 : 0;
6019 chksum <<= 1;
6020 chksum ^= feedback;
6023 while (*string++);
6024 return chksum;
6027 /* P is a string that will be used in a symbol. Mask out any characters
6028 that are not valid in that context. */
6030 void
6031 clean_symbol_name (char *p)
6033 for (; *p; p++)
6034 if (! (ISALNUM (*p)
6035 #ifndef NO_DOLLAR_IN_LABEL /* this for `$'; unlikely, but... -- kr */
6036 || *p == '$'
6037 #endif
6038 #ifndef NO_DOT_IN_LABEL /* this for `.'; unlikely, but... */
6039 || *p == '.'
6040 #endif
6042 *p = '_';
6045 /* Generate a name for a special-purpose function function.
6046 The generated name may need to be unique across the whole link.
6047 TYPE is some string to identify the purpose of this function to the
6048 linker or collect2; it must start with an uppercase letter,
6049 one of:
6050 I - for constructors
6051 D - for destructors
6052 N - for C++ anonymous namespaces
6053 F - for DWARF unwind frame information. */
6055 tree
6056 get_file_function_name (const char *type)
6058 char *buf;
6059 const char *p;
6060 char *q;
6062 /* If we already have a name we know to be unique, just use that. */
6063 if (first_global_object_name)
6064 p = first_global_object_name;
6065 /* If the target is handling the constructors/destructors, they
6066 will be local to this file and the name is only necessary for
6067 debugging purposes. */
6068 else if ((type[0] == 'I' || type[0] == 'D') && targetm.have_ctors_dtors)
6070 const char *file = main_input_filename;
6071 if (! file)
6072 file = input_filename;
6073 /* Just use the file's basename, because the full pathname
6074 might be quite long. */
6075 p = strrchr (file, '/');
6076 if (p)
6077 p++;
6078 else
6079 p = file;
6080 p = q = ASTRDUP (p);
6081 clean_symbol_name (q);
6083 else
6085 /* Otherwise, the name must be unique across the entire link.
6086 We don't have anything that we know to be unique to this translation
6087 unit, so use what we do have and throw in some randomness. */
6088 unsigned len;
6089 const char *name = weak_global_object_name;
6090 const char *file = main_input_filename;
6092 if (! name)
6093 name = "";
6094 if (! file)
6095 file = input_filename;
6097 len = strlen (file);
6098 q = alloca (9 * 2 + len + 1);
6099 memcpy (q, file, len + 1);
6100 clean_symbol_name (q);
6102 sprintf (q + len, "_%08X_%08X", crc32_string (0, name),
6103 crc32_string (0, flag_random_seed));
6105 p = q;
6108 buf = alloca (sizeof (FILE_FUNCTION_FORMAT) + strlen (p) + strlen (type));
6110 /* Set up the name of the file-level functions we may need.
6111 Use a global object (which is already required to be unique over
6112 the program) rather than the file name (which imposes extra
6113 constraints). */
6114 sprintf (buf, FILE_FUNCTION_FORMAT, type, p);
6116 return get_identifier (buf);
6119 #if defined ENABLE_TREE_CHECKING && (GCC_VERSION >= 2007)
6121 /* Complain that the tree code of NODE does not match the expected 0
6122 terminated list of trailing codes. The trailing code list can be
6123 empty, for a more vague error message. FILE, LINE, and FUNCTION
6124 are of the caller. */
6126 void
6127 tree_check_failed (const tree node, const char *file,
6128 int line, const char *function, ...)
6130 va_list args;
6131 char *buffer;
6132 unsigned length = 0;
6133 int code;
6135 va_start (args, function);
6136 while ((code = va_arg (args, int)))
6137 length += 4 + strlen (tree_code_name[code]);
6138 va_end (args);
6139 if (length)
6141 va_start (args, function);
6142 length += strlen ("expected ");
6143 buffer = alloca (length);
6144 length = 0;
6145 while ((code = va_arg (args, int)))
6147 const char *prefix = length ? " or " : "expected ";
6149 strcpy (buffer + length, prefix);
6150 length += strlen (prefix);
6151 strcpy (buffer + length, tree_code_name[code]);
6152 length += strlen (tree_code_name[code]);
6154 va_end (args);
6156 else
6157 buffer = (char *)"unexpected node";
6159 internal_error ("tree check: %s, have %s in %s, at %s:%d",
6160 buffer, tree_code_name[TREE_CODE (node)],
6161 function, trim_filename (file), line);
6164 /* Complain that the tree code of NODE does match the expected 0
6165 terminated list of trailing codes. FILE, LINE, and FUNCTION are of
6166 the caller. */
6168 void
6169 tree_not_check_failed (const tree node, const char *file,
6170 int line, const char *function, ...)
6172 va_list args;
6173 char *buffer;
6174 unsigned length = 0;
6175 int code;
6177 va_start (args, function);
6178 while ((code = va_arg (args, int)))
6179 length += 4 + strlen (tree_code_name[code]);
6180 va_end (args);
6181 va_start (args, function);
6182 buffer = alloca (length);
6183 length = 0;
6184 while ((code = va_arg (args, int)))
6186 if (length)
6188 strcpy (buffer + length, " or ");
6189 length += 4;
6191 strcpy (buffer + length, tree_code_name[code]);
6192 length += strlen (tree_code_name[code]);
6194 va_end (args);
6196 internal_error ("tree check: expected none of %s, have %s in %s, at %s:%d",
6197 buffer, tree_code_name[TREE_CODE (node)],
6198 function, trim_filename (file), line);
6201 /* Similar to tree_check_failed, except that we check for a class of tree
6202 code, given in CL. */
6204 void
6205 tree_class_check_failed (const tree node, const enum tree_code_class cl,
6206 const char *file, int line, const char *function)
6208 internal_error
6209 ("tree check: expected class %qs, have %qs (%s) in %s, at %s:%d",
6210 TREE_CODE_CLASS_STRING (cl),
6211 TREE_CODE_CLASS_STRING (TREE_CODE_CLASS (TREE_CODE (node))),
6212 tree_code_name[TREE_CODE (node)], function, trim_filename (file), line);
6215 /* Similar to tree_check_failed, except that instead of specifying a
6216 dozen codes, use the knowledge that they're all sequential. */
6218 void
6219 tree_range_check_failed (const tree node, const char *file, int line,
6220 const char *function, enum tree_code c1,
6221 enum tree_code c2)
6223 char *buffer;
6224 unsigned length = 0;
6225 enum tree_code c;
6227 for (c = c1; c <= c2; ++c)
6228 length += 4 + strlen (tree_code_name[c]);
6230 length += strlen ("expected ");
6231 buffer = alloca (length);
6232 length = 0;
6234 for (c = c1; c <= c2; ++c)
6236 const char *prefix = length ? " or " : "expected ";
6238 strcpy (buffer + length, prefix);
6239 length += strlen (prefix);
6240 strcpy (buffer + length, tree_code_name[c]);
6241 length += strlen (tree_code_name[c]);
6244 internal_error ("tree check: %s, have %s in %s, at %s:%d",
6245 buffer, tree_code_name[TREE_CODE (node)],
6246 function, trim_filename (file), line);
6250 /* Similar to tree_check_failed, except that we check that a tree does
6251 not have the specified code, given in CL. */
6253 void
6254 tree_not_class_check_failed (const tree node, const enum tree_code_class cl,
6255 const char *file, int line, const char *function)
6257 internal_error
6258 ("tree check: did not expect class %qs, have %qs (%s) in %s, at %s:%d",
6259 TREE_CODE_CLASS_STRING (cl),
6260 TREE_CODE_CLASS_STRING (TREE_CODE_CLASS (TREE_CODE (node))),
6261 tree_code_name[TREE_CODE (node)], function, trim_filename (file), line);
6265 /* Similar to tree_check_failed but applied to OMP_CLAUSE codes. */
6267 void
6268 omp_clause_check_failed (const tree node, const char *file, int line,
6269 const char *function, enum omp_clause_code code)
6271 internal_error ("tree check: expected omp_clause %s, have %s in %s, at %s:%d",
6272 omp_clause_code_name[code], tree_code_name[TREE_CODE (node)],
6273 function, trim_filename (file), line);
6277 /* Similar to tree_range_check_failed but applied to OMP_CLAUSE codes. */
6279 void
6280 omp_clause_range_check_failed (const tree node, const char *file, int line,
6281 const char *function, enum omp_clause_code c1,
6282 enum omp_clause_code c2)
6284 char *buffer;
6285 unsigned length = 0;
6286 enum omp_clause_code c;
6288 for (c = c1; c <= c2; ++c)
6289 length += 4 + strlen (omp_clause_code_name[c]);
6291 length += strlen ("expected ");
6292 buffer = alloca (length);
6293 length = 0;
6295 for (c = c1; c <= c2; ++c)
6297 const char *prefix = length ? " or " : "expected ";
6299 strcpy (buffer + length, prefix);
6300 length += strlen (prefix);
6301 strcpy (buffer + length, omp_clause_code_name[c]);
6302 length += strlen (omp_clause_code_name[c]);
6305 internal_error ("tree check: %s, have %s in %s, at %s:%d",
6306 buffer, omp_clause_code_name[TREE_CODE (node)],
6307 function, trim_filename (file), line);
6311 #undef DEFTREESTRUCT
6312 #define DEFTREESTRUCT(VAL, NAME) NAME,
6314 static const char *ts_enum_names[] = {
6315 #include "treestruct.def"
6317 #undef DEFTREESTRUCT
6319 #define TS_ENUM_NAME(EN) (ts_enum_names[(EN)])
6321 /* Similar to tree_class_check_failed, except that we check for
6322 whether CODE contains the tree structure identified by EN. */
6324 void
6325 tree_contains_struct_check_failed (const tree node,
6326 const enum tree_node_structure_enum en,
6327 const char *file, int line,
6328 const char *function)
6330 internal_error
6331 ("tree check: expected tree that contains %qs structure, have %qs in %s, at %s:%d",
6332 TS_ENUM_NAME(en),
6333 tree_code_name[TREE_CODE (node)], function, trim_filename (file), line);
6337 /* Similar to above, except that the check is for the bounds of a TREE_VEC's
6338 (dynamically sized) vector. */
6340 void
6341 tree_vec_elt_check_failed (int idx, int len, const char *file, int line,
6342 const char *function)
6344 internal_error
6345 ("tree check: accessed elt %d of tree_vec with %d elts in %s, at %s:%d",
6346 idx + 1, len, function, trim_filename (file), line);
6349 /* Similar to above, except that the check is for the bounds of a PHI_NODE's
6350 (dynamically sized) vector. */
6352 void
6353 phi_node_elt_check_failed (int idx, int len, const char *file, int line,
6354 const char *function)
6356 internal_error
6357 ("tree check: accessed elt %d of phi_node with %d elts in %s, at %s:%d",
6358 idx + 1, len, function, trim_filename (file), line);
6361 /* Similar to above, except that the check is for the bounds of the operand
6362 vector of an expression node. */
6364 void
6365 tree_operand_check_failed (int idx, enum tree_code code, const char *file,
6366 int line, const char *function)
6368 internal_error
6369 ("tree check: accessed operand %d of %s with %d operands in %s, at %s:%d",
6370 idx + 1, tree_code_name[code], TREE_CODE_LENGTH (code),
6371 function, trim_filename (file), line);
6374 /* Similar to above, except that the check is for the number of
6375 operands of an OMP_CLAUSE node. */
6377 void
6378 omp_clause_operand_check_failed (int idx, tree t, const char *file,
6379 int line, const char *function)
6381 internal_error
6382 ("tree check: accessed operand %d of omp_clause %s with %d operands "
6383 "in %s, at %s:%d", idx + 1, omp_clause_code_name[OMP_CLAUSE_CODE (t)],
6384 omp_clause_num_ops [OMP_CLAUSE_CODE (t)], function,
6385 trim_filename (file), line);
6387 #endif /* ENABLE_TREE_CHECKING */
6389 /* Create a new vector type node holding SUBPARTS units of type INNERTYPE,
6390 and mapped to the machine mode MODE. Initialize its fields and build
6391 the information necessary for debugging output. */
6393 static tree
6394 make_vector_type (tree innertype, int nunits, enum machine_mode mode)
6396 tree t;
6397 hashval_t hashcode = 0;
6399 /* Build a main variant, based on the main variant of the inner type, then
6400 use it to build the variant we return. */
6401 if ((TYPE_ATTRIBUTES (innertype) || TYPE_QUALS (innertype))
6402 && TYPE_MAIN_VARIANT (innertype) != innertype)
6403 return build_type_attribute_qual_variant (
6404 make_vector_type (TYPE_MAIN_VARIANT (innertype), nunits, mode),
6405 TYPE_ATTRIBUTES (innertype),
6406 TYPE_QUALS (innertype));
6408 t = make_node (VECTOR_TYPE);
6409 TREE_TYPE (t) = TYPE_MAIN_VARIANT (innertype);
6410 SET_TYPE_VECTOR_SUBPARTS (t, nunits);
6411 TYPE_MODE (t) = mode;
6412 TYPE_READONLY (t) = TYPE_READONLY (innertype);
6413 TYPE_VOLATILE (t) = TYPE_VOLATILE (innertype);
6415 layout_type (t);
6418 tree index = build_int_cst (NULL_TREE, nunits - 1);
6419 tree array = build_array_type (innertype, build_index_type (index));
6420 tree rt = make_node (RECORD_TYPE);
6422 TYPE_FIELDS (rt) = build_decl (FIELD_DECL, get_identifier ("f"), array);
6423 DECL_CONTEXT (TYPE_FIELDS (rt)) = rt;
6424 layout_type (rt);
6425 TYPE_DEBUG_REPRESENTATION_TYPE (t) = rt;
6426 /* In dwarfout.c, type lookup uses TYPE_UID numbers. We want to output
6427 the representation type, and we want to find that die when looking up
6428 the vector type. This is most easily achieved by making the TYPE_UID
6429 numbers equal. */
6430 TYPE_UID (rt) = TYPE_UID (t);
6433 hashcode = iterative_hash_host_wide_int (VECTOR_TYPE, hashcode);
6434 hashcode = iterative_hash_host_wide_int (mode, hashcode);
6435 hashcode = iterative_hash_object (TYPE_HASH (innertype), hashcode);
6436 return type_hash_canon (hashcode, t);
6439 static tree
6440 make_or_reuse_type (unsigned size, int unsignedp)
6442 if (size == INT_TYPE_SIZE)
6443 return unsignedp ? unsigned_type_node : integer_type_node;
6444 if (size == CHAR_TYPE_SIZE)
6445 return unsignedp ? unsigned_char_type_node : signed_char_type_node;
6446 if (size == SHORT_TYPE_SIZE)
6447 return unsignedp ? short_unsigned_type_node : short_integer_type_node;
6448 if (size == LONG_TYPE_SIZE)
6449 return unsignedp ? long_unsigned_type_node : long_integer_type_node;
6450 if (size == LONG_LONG_TYPE_SIZE)
6451 return (unsignedp ? long_long_unsigned_type_node
6452 : long_long_integer_type_node);
6454 if (unsignedp)
6455 return make_unsigned_type (size);
6456 else
6457 return make_signed_type (size);
6460 /* Create nodes for all integer types (and error_mark_node) using the sizes
6461 of C datatypes. The caller should call set_sizetype soon after calling
6462 this function to select one of the types as sizetype. */
6464 void
6465 build_common_tree_nodes (bool signed_char, bool signed_sizetype)
6467 error_mark_node = make_node (ERROR_MARK);
6468 TREE_TYPE (error_mark_node) = error_mark_node;
6470 initialize_sizetypes (signed_sizetype);
6472 /* Define both `signed char' and `unsigned char'. */
6473 signed_char_type_node = make_signed_type (CHAR_TYPE_SIZE);
6474 TYPE_STRING_FLAG (signed_char_type_node) = 1;
6475 unsigned_char_type_node = make_unsigned_type (CHAR_TYPE_SIZE);
6476 TYPE_STRING_FLAG (unsigned_char_type_node) = 1;
6478 /* Define `char', which is like either `signed char' or `unsigned char'
6479 but not the same as either. */
6480 char_type_node
6481 = (signed_char
6482 ? make_signed_type (CHAR_TYPE_SIZE)
6483 : make_unsigned_type (CHAR_TYPE_SIZE));
6484 TYPE_STRING_FLAG (char_type_node) = 1;
6486 short_integer_type_node = make_signed_type (SHORT_TYPE_SIZE);
6487 short_unsigned_type_node = make_unsigned_type (SHORT_TYPE_SIZE);
6488 integer_type_node = make_signed_type (INT_TYPE_SIZE);
6489 unsigned_type_node = make_unsigned_type (INT_TYPE_SIZE);
6490 long_integer_type_node = make_signed_type (LONG_TYPE_SIZE);
6491 long_unsigned_type_node = make_unsigned_type (LONG_TYPE_SIZE);
6492 long_long_integer_type_node = make_signed_type (LONG_LONG_TYPE_SIZE);
6493 long_long_unsigned_type_node = make_unsigned_type (LONG_LONG_TYPE_SIZE);
6495 /* Define a boolean type. This type only represents boolean values but
6496 may be larger than char depending on the value of BOOL_TYPE_SIZE.
6497 Front ends which want to override this size (i.e. Java) can redefine
6498 boolean_type_node before calling build_common_tree_nodes_2. */
6499 boolean_type_node = make_unsigned_type (BOOL_TYPE_SIZE);
6500 TREE_SET_CODE (boolean_type_node, BOOLEAN_TYPE);
6501 TYPE_MAX_VALUE (boolean_type_node) = build_int_cst (boolean_type_node, 1);
6502 TYPE_PRECISION (boolean_type_node) = 1;
6504 /* Fill in the rest of the sized types. Reuse existing type nodes
6505 when possible. */
6506 intQI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (QImode), 0);
6507 intHI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (HImode), 0);
6508 intSI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (SImode), 0);
6509 intDI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (DImode), 0);
6510 intTI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (TImode), 0);
6512 unsigned_intQI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (QImode), 1);
6513 unsigned_intHI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (HImode), 1);
6514 unsigned_intSI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (SImode), 1);
6515 unsigned_intDI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (DImode), 1);
6516 unsigned_intTI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (TImode), 1);
6518 access_public_node = get_identifier ("public");
6519 access_protected_node = get_identifier ("protected");
6520 access_private_node = get_identifier ("private");
6523 /* Call this function after calling build_common_tree_nodes and set_sizetype.
6524 It will create several other common tree nodes. */
6526 void
6527 build_common_tree_nodes_2 (int short_double)
6529 /* Define these next since types below may used them. */
6530 integer_zero_node = build_int_cst (NULL_TREE, 0);
6531 integer_one_node = build_int_cst (NULL_TREE, 1);
6532 integer_minus_one_node = build_int_cst (NULL_TREE, -1);
6534 size_zero_node = size_int (0);
6535 size_one_node = size_int (1);
6536 bitsize_zero_node = bitsize_int (0);
6537 bitsize_one_node = bitsize_int (1);
6538 bitsize_unit_node = bitsize_int (BITS_PER_UNIT);
6540 boolean_false_node = TYPE_MIN_VALUE (boolean_type_node);
6541 boolean_true_node = TYPE_MAX_VALUE (boolean_type_node);
6543 void_type_node = make_node (VOID_TYPE);
6544 layout_type (void_type_node);
6546 /* We are not going to have real types in C with less than byte alignment,
6547 so we might as well not have any types that claim to have it. */
6548 TYPE_ALIGN (void_type_node) = BITS_PER_UNIT;
6549 TYPE_USER_ALIGN (void_type_node) = 0;
6551 null_pointer_node = build_int_cst (build_pointer_type (void_type_node), 0);
6552 layout_type (TREE_TYPE (null_pointer_node));
6554 ptr_type_node = build_pointer_type (void_type_node);
6555 const_ptr_type_node
6556 = build_pointer_type (build_type_variant (void_type_node, 1, 0));
6557 fileptr_type_node = ptr_type_node;
6559 float_type_node = make_node (REAL_TYPE);
6560 TYPE_PRECISION (float_type_node) = FLOAT_TYPE_SIZE;
6561 layout_type (float_type_node);
6563 double_type_node = make_node (REAL_TYPE);
6564 if (short_double)
6565 TYPE_PRECISION (double_type_node) = FLOAT_TYPE_SIZE;
6566 else
6567 TYPE_PRECISION (double_type_node) = DOUBLE_TYPE_SIZE;
6568 layout_type (double_type_node);
6570 long_double_type_node = make_node (REAL_TYPE);
6571 TYPE_PRECISION (long_double_type_node) = LONG_DOUBLE_TYPE_SIZE;
6572 layout_type (long_double_type_node);
6574 float_ptr_type_node = build_pointer_type (float_type_node);
6575 double_ptr_type_node = build_pointer_type (double_type_node);
6576 long_double_ptr_type_node = build_pointer_type (long_double_type_node);
6577 integer_ptr_type_node = build_pointer_type (integer_type_node);
6579 /* Fixed size integer types. */
6580 uint32_type_node = build_nonstandard_integer_type (32, true);
6581 uint64_type_node = build_nonstandard_integer_type (64, true);
6583 /* Decimal float types. */
6584 dfloat32_type_node = make_node (REAL_TYPE);
6585 TYPE_PRECISION (dfloat32_type_node) = DECIMAL32_TYPE_SIZE;
6586 layout_type (dfloat32_type_node);
6587 TYPE_MODE (dfloat32_type_node) = SDmode;
6588 dfloat32_ptr_type_node = build_pointer_type (dfloat32_type_node);
6590 dfloat64_type_node = make_node (REAL_TYPE);
6591 TYPE_PRECISION (dfloat64_type_node) = DECIMAL64_TYPE_SIZE;
6592 layout_type (dfloat64_type_node);
6593 TYPE_MODE (dfloat64_type_node) = DDmode;
6594 dfloat64_ptr_type_node = build_pointer_type (dfloat64_type_node);
6596 dfloat128_type_node = make_node (REAL_TYPE);
6597 TYPE_PRECISION (dfloat128_type_node) = DECIMAL128_TYPE_SIZE;
6598 layout_type (dfloat128_type_node);
6599 TYPE_MODE (dfloat128_type_node) = TDmode;
6600 dfloat128_ptr_type_node = build_pointer_type (dfloat128_type_node);
6602 complex_integer_type_node = make_node (COMPLEX_TYPE);
6603 TREE_TYPE (complex_integer_type_node) = integer_type_node;
6604 layout_type (complex_integer_type_node);
6606 complex_float_type_node = make_node (COMPLEX_TYPE);
6607 TREE_TYPE (complex_float_type_node) = float_type_node;
6608 layout_type (complex_float_type_node);
6610 complex_double_type_node = make_node (COMPLEX_TYPE);
6611 TREE_TYPE (complex_double_type_node) = double_type_node;
6612 layout_type (complex_double_type_node);
6614 complex_long_double_type_node = make_node (COMPLEX_TYPE);
6615 TREE_TYPE (complex_long_double_type_node) = long_double_type_node;
6616 layout_type (complex_long_double_type_node);
6619 tree t = targetm.build_builtin_va_list ();
6621 /* Many back-ends define record types without setting TYPE_NAME.
6622 If we copied the record type here, we'd keep the original
6623 record type without a name. This breaks name mangling. So,
6624 don't copy record types and let c_common_nodes_and_builtins()
6625 declare the type to be __builtin_va_list. */
6626 if (TREE_CODE (t) != RECORD_TYPE)
6627 t = build_variant_type_copy (t);
6629 va_list_type_node = t;
6633 /* A subroutine of build_common_builtin_nodes. Define a builtin function. */
6635 static void
6636 local_define_builtin (const char *name, tree type, enum built_in_function code,
6637 const char *library_name, int ecf_flags)
6639 tree decl;
6641 decl = add_builtin_function (name, type, code, BUILT_IN_NORMAL,
6642 library_name, NULL_TREE);
6643 if (ecf_flags & ECF_CONST)
6644 TREE_READONLY (decl) = 1;
6645 if (ecf_flags & ECF_PURE)
6646 DECL_IS_PURE (decl) = 1;
6647 if (ecf_flags & ECF_NORETURN)
6648 TREE_THIS_VOLATILE (decl) = 1;
6649 if (ecf_flags & ECF_NOTHROW)
6650 TREE_NOTHROW (decl) = 1;
6651 if (ecf_flags & ECF_MALLOC)
6652 DECL_IS_MALLOC (decl) = 1;
6654 built_in_decls[code] = decl;
6655 implicit_built_in_decls[code] = decl;
6658 /* Call this function after instantiating all builtins that the language
6659 front end cares about. This will build the rest of the builtins that
6660 are relied upon by the tree optimizers and the middle-end. */
6662 void
6663 build_common_builtin_nodes (void)
6665 tree tmp, ftype;
6667 if (built_in_decls[BUILT_IN_MEMCPY] == NULL
6668 || built_in_decls[BUILT_IN_MEMMOVE] == NULL)
6670 tmp = tree_cons (NULL_TREE, size_type_node, void_list_node);
6671 tmp = tree_cons (NULL_TREE, const_ptr_type_node, tmp);
6672 tmp = tree_cons (NULL_TREE, ptr_type_node, tmp);
6673 ftype = build_function_type (ptr_type_node, tmp);
6675 if (built_in_decls[BUILT_IN_MEMCPY] == NULL)
6676 local_define_builtin ("__builtin_memcpy", ftype, BUILT_IN_MEMCPY,
6677 "memcpy", ECF_NOTHROW);
6678 if (built_in_decls[BUILT_IN_MEMMOVE] == NULL)
6679 local_define_builtin ("__builtin_memmove", ftype, BUILT_IN_MEMMOVE,
6680 "memmove", ECF_NOTHROW);
6683 if (built_in_decls[BUILT_IN_MEMCMP] == NULL)
6685 tmp = tree_cons (NULL_TREE, size_type_node, void_list_node);
6686 tmp = tree_cons (NULL_TREE, const_ptr_type_node, tmp);
6687 tmp = tree_cons (NULL_TREE, const_ptr_type_node, tmp);
6688 ftype = build_function_type (integer_type_node, tmp);
6689 local_define_builtin ("__builtin_memcmp", ftype, BUILT_IN_MEMCMP,
6690 "memcmp", ECF_PURE | ECF_NOTHROW);
6693 if (built_in_decls[BUILT_IN_MEMSET] == NULL)
6695 tmp = tree_cons (NULL_TREE, size_type_node, void_list_node);
6696 tmp = tree_cons (NULL_TREE, integer_type_node, tmp);
6697 tmp = tree_cons (NULL_TREE, ptr_type_node, tmp);
6698 ftype = build_function_type (ptr_type_node, tmp);
6699 local_define_builtin ("__builtin_memset", ftype, BUILT_IN_MEMSET,
6700 "memset", ECF_NOTHROW);
6703 if (built_in_decls[BUILT_IN_ALLOCA] == NULL)
6705 tmp = tree_cons (NULL_TREE, size_type_node, void_list_node);
6706 ftype = build_function_type (ptr_type_node, tmp);
6707 local_define_builtin ("__builtin_alloca", ftype, BUILT_IN_ALLOCA,
6708 "alloca", ECF_NOTHROW | ECF_MALLOC);
6711 tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node);
6712 tmp = tree_cons (NULL_TREE, ptr_type_node, tmp);
6713 tmp = tree_cons (NULL_TREE, ptr_type_node, tmp);
6714 ftype = build_function_type (void_type_node, tmp);
6715 local_define_builtin ("__builtin_init_trampoline", ftype,
6716 BUILT_IN_INIT_TRAMPOLINE,
6717 "__builtin_init_trampoline", ECF_NOTHROW);
6719 tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node);
6720 ftype = build_function_type (ptr_type_node, tmp);
6721 local_define_builtin ("__builtin_adjust_trampoline", ftype,
6722 BUILT_IN_ADJUST_TRAMPOLINE,
6723 "__builtin_adjust_trampoline",
6724 ECF_CONST | ECF_NOTHROW);
6726 tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node);
6727 tmp = tree_cons (NULL_TREE, ptr_type_node, tmp);
6728 ftype = build_function_type (void_type_node, tmp);
6729 local_define_builtin ("__builtin_nonlocal_goto", ftype,
6730 BUILT_IN_NONLOCAL_GOTO,
6731 "__builtin_nonlocal_goto",
6732 ECF_NORETURN | ECF_NOTHROW);
6734 tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node);
6735 tmp = tree_cons (NULL_TREE, ptr_type_node, tmp);
6736 ftype = build_function_type (void_type_node, tmp);
6737 local_define_builtin ("__builtin_setjmp_setup", ftype,
6738 BUILT_IN_SETJMP_SETUP,
6739 "__builtin_setjmp_setup", ECF_NOTHROW);
6741 tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node);
6742 ftype = build_function_type (ptr_type_node, tmp);
6743 local_define_builtin ("__builtin_setjmp_dispatcher", ftype,
6744 BUILT_IN_SETJMP_DISPATCHER,
6745 "__builtin_setjmp_dispatcher",
6746 ECF_PURE | ECF_NOTHROW);
6748 tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node);
6749 ftype = build_function_type (void_type_node, tmp);
6750 local_define_builtin ("__builtin_setjmp_receiver", ftype,
6751 BUILT_IN_SETJMP_RECEIVER,
6752 "__builtin_setjmp_receiver", ECF_NOTHROW);
6754 ftype = build_function_type (ptr_type_node, void_list_node);
6755 local_define_builtin ("__builtin_stack_save", ftype, BUILT_IN_STACK_SAVE,
6756 "__builtin_stack_save", ECF_NOTHROW);
6758 tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node);
6759 ftype = build_function_type (void_type_node, tmp);
6760 local_define_builtin ("__builtin_stack_restore", ftype,
6761 BUILT_IN_STACK_RESTORE,
6762 "__builtin_stack_restore", ECF_NOTHROW);
6764 ftype = build_function_type (void_type_node, void_list_node);
6765 local_define_builtin ("__builtin_profile_func_enter", ftype,
6766 BUILT_IN_PROFILE_FUNC_ENTER, "profile_func_enter", 0);
6767 local_define_builtin ("__builtin_profile_func_exit", ftype,
6768 BUILT_IN_PROFILE_FUNC_EXIT, "profile_func_exit", 0);
6770 /* Complex multiplication and division. These are handled as builtins
6771 rather than optabs because emit_library_call_value doesn't support
6772 complex. Further, we can do slightly better with folding these
6773 beasties if the real and complex parts of the arguments are separate. */
6775 enum machine_mode mode;
6777 for (mode = MIN_MODE_COMPLEX_FLOAT; mode <= MAX_MODE_COMPLEX_FLOAT; ++mode)
6779 char mode_name_buf[4], *q;
6780 const char *p;
6781 enum built_in_function mcode, dcode;
6782 tree type, inner_type;
6784 type = lang_hooks.types.type_for_mode (mode, 0);
6785 if (type == NULL)
6786 continue;
6787 inner_type = TREE_TYPE (type);
6789 tmp = tree_cons (NULL_TREE, inner_type, void_list_node);
6790 tmp = tree_cons (NULL_TREE, inner_type, tmp);
6791 tmp = tree_cons (NULL_TREE, inner_type, tmp);
6792 tmp = tree_cons (NULL_TREE, inner_type, tmp);
6793 ftype = build_function_type (type, tmp);
6795 mcode = BUILT_IN_COMPLEX_MUL_MIN + mode - MIN_MODE_COMPLEX_FLOAT;
6796 dcode = BUILT_IN_COMPLEX_DIV_MIN + mode - MIN_MODE_COMPLEX_FLOAT;
6798 for (p = GET_MODE_NAME (mode), q = mode_name_buf; *p; p++, q++)
6799 *q = TOLOWER (*p);
6800 *q = '\0';
6802 built_in_names[mcode] = concat ("__mul", mode_name_buf, "3", NULL);
6803 local_define_builtin (built_in_names[mcode], ftype, mcode,
6804 built_in_names[mcode], ECF_CONST | ECF_NOTHROW);
6806 built_in_names[dcode] = concat ("__div", mode_name_buf, "3", NULL);
6807 local_define_builtin (built_in_names[dcode], ftype, dcode,
6808 built_in_names[dcode], ECF_CONST | ECF_NOTHROW);
6813 /* HACK. GROSS. This is absolutely disgusting. I wish there was a
6814 better way.
6816 If we requested a pointer to a vector, build up the pointers that
6817 we stripped off while looking for the inner type. Similarly for
6818 return values from functions.
6820 The argument TYPE is the top of the chain, and BOTTOM is the
6821 new type which we will point to. */
6823 tree
6824 reconstruct_complex_type (tree type, tree bottom)
6826 tree inner, outer;
6828 if (POINTER_TYPE_P (type))
6830 inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
6831 outer = build_pointer_type (inner);
6833 else if (TREE_CODE (type) == ARRAY_TYPE)
6835 inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
6836 outer = build_array_type (inner, TYPE_DOMAIN (type));
6838 else if (TREE_CODE (type) == FUNCTION_TYPE)
6840 inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
6841 outer = build_function_type (inner, TYPE_ARG_TYPES (type));
6843 else if (TREE_CODE (type) == METHOD_TYPE)
6845 tree argtypes;
6846 inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
6847 /* The build_method_type_directly() routine prepends 'this' to argument list,
6848 so we must compensate by getting rid of it. */
6849 argtypes = TYPE_ARG_TYPES (type);
6850 outer = build_method_type_directly (TYPE_METHOD_BASETYPE (type),
6851 inner,
6852 TYPE_ARG_TYPES (type));
6853 TYPE_ARG_TYPES (outer) = argtypes;
6855 else
6856 return bottom;
6858 TYPE_READONLY (outer) = TYPE_READONLY (type);
6859 TYPE_VOLATILE (outer) = TYPE_VOLATILE (type);
6861 return outer;
6864 /* Returns a vector tree node given a mode (integer, vector, or BLKmode) and
6865 the inner type. */
6866 tree
6867 build_vector_type_for_mode (tree innertype, enum machine_mode mode)
6869 int nunits;
6871 switch (GET_MODE_CLASS (mode))
6873 case MODE_VECTOR_INT:
6874 case MODE_VECTOR_FLOAT:
6875 nunits = GET_MODE_NUNITS (mode);
6876 break;
6878 case MODE_INT:
6879 /* Check that there are no leftover bits. */
6880 gcc_assert (GET_MODE_BITSIZE (mode)
6881 % TREE_INT_CST_LOW (TYPE_SIZE (innertype)) == 0);
6883 nunits = GET_MODE_BITSIZE (mode)
6884 / TREE_INT_CST_LOW (TYPE_SIZE (innertype));
6885 break;
6887 default:
6888 gcc_unreachable ();
6891 return make_vector_type (innertype, nunits, mode);
6894 /* Similarly, but takes the inner type and number of units, which must be
6895 a power of two. */
6897 tree
6898 build_vector_type (tree innertype, int nunits)
6900 return make_vector_type (innertype, nunits, VOIDmode);
6904 /* Build RESX_EXPR with given REGION_NUMBER. */
6905 tree
6906 build_resx (int region_number)
6908 tree t;
6909 t = build1 (RESX_EXPR, void_type_node,
6910 build_int_cst (NULL_TREE, region_number));
6911 return t;
6914 /* Given an initializer INIT, return TRUE if INIT is zero or some
6915 aggregate of zeros. Otherwise return FALSE. */
6916 bool
6917 initializer_zerop (tree init)
6919 tree elt;
6921 STRIP_NOPS (init);
6923 switch (TREE_CODE (init))
6925 case INTEGER_CST:
6926 return integer_zerop (init);
6928 case REAL_CST:
6929 /* ??? Note that this is not correct for C4X float formats. There,
6930 a bit pattern of all zeros is 1.0; 0.0 is encoded with the most
6931 negative exponent. */
6932 return real_zerop (init)
6933 && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (init));
6935 case COMPLEX_CST:
6936 return integer_zerop (init)
6937 || (real_zerop (init)
6938 && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (TREE_REALPART (init)))
6939 && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (TREE_IMAGPART (init))));
6941 case VECTOR_CST:
6942 for (elt = TREE_VECTOR_CST_ELTS (init); elt; elt = TREE_CHAIN (elt))
6943 if (!initializer_zerop (TREE_VALUE (elt)))
6944 return false;
6945 return true;
6947 case CONSTRUCTOR:
6949 unsigned HOST_WIDE_INT idx;
6951 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (init), idx, elt)
6952 if (!initializer_zerop (elt))
6953 return false;
6954 return true;
6957 default:
6958 return false;
6962 /* Build an empty statement. */
6964 tree
6965 build_empty_stmt (void)
6967 return build1 (NOP_EXPR, void_type_node, size_zero_node);
6971 /* Build an OpenMP clause with code CODE. */
6973 tree
6974 build_omp_clause (enum omp_clause_code code)
6976 tree t;
6977 int size, length;
6979 length = omp_clause_num_ops[code];
6980 size = (sizeof (struct tree_omp_clause) + (length - 1) * sizeof (tree));
6982 t = ggc_alloc (size);
6983 memset (t, 0, size);
6984 TREE_SET_CODE (t, OMP_CLAUSE);
6985 OMP_CLAUSE_SET_CODE (t, code);
6987 #ifdef GATHER_STATISTICS
6988 tree_node_counts[(int) omp_clause_kind]++;
6989 tree_node_sizes[(int) omp_clause_kind] += size;
6990 #endif
6992 return t;
6996 /* Returns true if it is possible to prove that the index of
6997 an array access REF (an ARRAY_REF expression) falls into the
6998 array bounds. */
7000 bool
7001 in_array_bounds_p (tree ref)
7003 tree idx = TREE_OPERAND (ref, 1);
7004 tree min, max;
7006 if (TREE_CODE (idx) != INTEGER_CST)
7007 return false;
7009 min = array_ref_low_bound (ref);
7010 max = array_ref_up_bound (ref);
7011 if (!min
7012 || !max
7013 || TREE_CODE (min) != INTEGER_CST
7014 || TREE_CODE (max) != INTEGER_CST)
7015 return false;
7017 if (tree_int_cst_lt (idx, min)
7018 || tree_int_cst_lt (max, idx))
7019 return false;
7021 return true;
7024 /* Returns true if it is possible to prove that the range of
7025 an array access REF (an ARRAY_RANGE_REF expression) falls
7026 into the array bounds. */
7028 bool
7029 range_in_array_bounds_p (tree ref)
7031 tree domain_type = TYPE_DOMAIN (TREE_TYPE (ref));
7032 tree range_min, range_max, min, max;
7034 range_min = TYPE_MIN_VALUE (domain_type);
7035 range_max = TYPE_MAX_VALUE (domain_type);
7036 if (!range_min
7037 || !range_max
7038 || TREE_CODE (range_min) != INTEGER_CST
7039 || TREE_CODE (range_max) != INTEGER_CST)
7040 return false;
7042 min = array_ref_low_bound (ref);
7043 max = array_ref_up_bound (ref);
7044 if (!min
7045 || !max
7046 || TREE_CODE (min) != INTEGER_CST
7047 || TREE_CODE (max) != INTEGER_CST)
7048 return false;
7050 if (tree_int_cst_lt (range_min, min)
7051 || tree_int_cst_lt (max, range_max))
7052 return false;
7054 return true;
7057 /* Return true if T (assumed to be a DECL) is a global variable. */
7059 bool
7060 is_global_var (tree t)
7062 if (MTAG_P (t))
7063 return (TREE_STATIC (t) || MTAG_GLOBAL (t));
7064 else
7065 return (TREE_STATIC (t) || DECL_EXTERNAL (t));
7068 /* Return true if T (assumed to be a DECL) must be assigned a memory
7069 location. */
7071 bool
7072 needs_to_live_in_memory (tree t)
7074 return (TREE_ADDRESSABLE (t)
7075 || is_global_var (t)
7076 || (TREE_CODE (t) == RESULT_DECL
7077 && aggregate_value_p (t, current_function_decl)));
7080 /* There are situations in which a language considers record types
7081 compatible which have different field lists. Decide if two fields
7082 are compatible. It is assumed that the parent records are compatible. */
7084 bool
7085 fields_compatible_p (tree f1, tree f2)
7087 if (!operand_equal_p (DECL_FIELD_BIT_OFFSET (f1),
7088 DECL_FIELD_BIT_OFFSET (f2), OEP_ONLY_CONST))
7089 return false;
7091 if (!operand_equal_p (DECL_FIELD_OFFSET (f1),
7092 DECL_FIELD_OFFSET (f2), OEP_ONLY_CONST))
7093 return false;
7095 if (!lang_hooks.types_compatible_p (TREE_TYPE (f1), TREE_TYPE (f2)))
7096 return false;
7098 return true;
7101 /* Locate within RECORD a field that is compatible with ORIG_FIELD. */
7103 tree
7104 find_compatible_field (tree record, tree orig_field)
7106 tree f;
7108 for (f = TYPE_FIELDS (record); f ; f = TREE_CHAIN (f))
7109 if (TREE_CODE (f) == FIELD_DECL
7110 && fields_compatible_p (f, orig_field))
7111 return f;
7113 /* ??? Why isn't this on the main fields list? */
7114 f = TYPE_VFIELD (record);
7115 if (f && TREE_CODE (f) == FIELD_DECL
7116 && fields_compatible_p (f, orig_field))
7117 return f;
7119 /* ??? We should abort here, but Java appears to do Bad Things
7120 with inherited fields. */
7121 return orig_field;
7124 /* Return value of a constant X. */
7126 HOST_WIDE_INT
7127 int_cst_value (tree x)
7129 unsigned bits = TYPE_PRECISION (TREE_TYPE (x));
7130 unsigned HOST_WIDE_INT val = TREE_INT_CST_LOW (x);
7131 bool negative = ((val >> (bits - 1)) & 1) != 0;
7133 gcc_assert (bits <= HOST_BITS_PER_WIDE_INT);
7135 if (negative)
7136 val |= (~(unsigned HOST_WIDE_INT) 0) << (bits - 1) << 1;
7137 else
7138 val &= ~((~(unsigned HOST_WIDE_INT) 0) << (bits - 1) << 1);
7140 return val;
7143 /* Returns the greatest common divisor of A and B, which must be
7144 INTEGER_CSTs. */
7146 tree
7147 tree_fold_gcd (tree a, tree b)
7149 tree a_mod_b;
7150 tree type = TREE_TYPE (a);
7152 gcc_assert (TREE_CODE (a) == INTEGER_CST);
7153 gcc_assert (TREE_CODE (b) == INTEGER_CST);
7155 if (integer_zerop (a))
7156 return b;
7158 if (integer_zerop (b))
7159 return a;
7161 if (tree_int_cst_sgn (a) == -1)
7162 a = fold_build2 (MULT_EXPR, type, a,
7163 build_int_cst (type, -1));
7165 if (tree_int_cst_sgn (b) == -1)
7166 b = fold_build2 (MULT_EXPR, type, b,
7167 build_int_cst (type, -1));
7169 while (1)
7171 a_mod_b = fold_build2 (FLOOR_MOD_EXPR, type, a, b);
7173 if (!TREE_INT_CST_LOW (a_mod_b)
7174 && !TREE_INT_CST_HIGH (a_mod_b))
7175 return b;
7177 a = b;
7178 b = a_mod_b;
7182 /* Returns unsigned variant of TYPE. */
7184 tree
7185 unsigned_type_for (tree type)
7187 if (POINTER_TYPE_P (type))
7188 return lang_hooks.types.unsigned_type (size_type_node);
7189 return lang_hooks.types.unsigned_type (type);
7192 /* Returns signed variant of TYPE. */
7194 tree
7195 signed_type_for (tree type)
7197 if (POINTER_TYPE_P (type))
7198 return lang_hooks.types.signed_type (size_type_node);
7199 return lang_hooks.types.signed_type (type);
7202 /* Returns the largest value obtainable by casting something in INNER type to
7203 OUTER type. */
7205 tree
7206 upper_bound_in_type (tree outer, tree inner)
7208 unsigned HOST_WIDE_INT lo, hi;
7209 unsigned int det = 0;
7210 unsigned oprec = TYPE_PRECISION (outer);
7211 unsigned iprec = TYPE_PRECISION (inner);
7212 unsigned prec;
7214 /* Compute a unique number for every combination. */
7215 det |= (oprec > iprec) ? 4 : 0;
7216 det |= TYPE_UNSIGNED (outer) ? 2 : 0;
7217 det |= TYPE_UNSIGNED (inner) ? 1 : 0;
7219 /* Determine the exponent to use. */
7220 switch (det)
7222 case 0:
7223 case 1:
7224 /* oprec <= iprec, outer: signed, inner: don't care. */
7225 prec = oprec - 1;
7226 break;
7227 case 2:
7228 case 3:
7229 /* oprec <= iprec, outer: unsigned, inner: don't care. */
7230 prec = oprec;
7231 break;
7232 case 4:
7233 /* oprec > iprec, outer: signed, inner: signed. */
7234 prec = iprec - 1;
7235 break;
7236 case 5:
7237 /* oprec > iprec, outer: signed, inner: unsigned. */
7238 prec = iprec;
7239 break;
7240 case 6:
7241 /* oprec > iprec, outer: unsigned, inner: signed. */
7242 prec = oprec;
7243 break;
7244 case 7:
7245 /* oprec > iprec, outer: unsigned, inner: unsigned. */
7246 prec = iprec;
7247 break;
7248 default:
7249 gcc_unreachable ();
7252 /* Compute 2^^prec - 1. */
7253 if (prec <= HOST_BITS_PER_WIDE_INT)
7255 hi = 0;
7256 lo = ((~(unsigned HOST_WIDE_INT) 0)
7257 >> (HOST_BITS_PER_WIDE_INT - prec));
7259 else
7261 hi = ((~(unsigned HOST_WIDE_INT) 0)
7262 >> (2 * HOST_BITS_PER_WIDE_INT - prec));
7263 lo = ~(unsigned HOST_WIDE_INT) 0;
7266 return build_int_cst_wide (outer, lo, hi);
7269 /* Returns the smallest value obtainable by casting something in INNER type to
7270 OUTER type. */
7272 tree
7273 lower_bound_in_type (tree outer, tree inner)
7275 unsigned HOST_WIDE_INT lo, hi;
7276 unsigned oprec = TYPE_PRECISION (outer);
7277 unsigned iprec = TYPE_PRECISION (inner);
7279 /* If OUTER type is unsigned, we can definitely cast 0 to OUTER type
7280 and obtain 0. */
7281 if (TYPE_UNSIGNED (outer)
7282 /* If we are widening something of an unsigned type, OUTER type
7283 contains all values of INNER type. In particular, both INNER
7284 and OUTER types have zero in common. */
7285 || (oprec > iprec && TYPE_UNSIGNED (inner)))
7286 lo = hi = 0;
7287 else
7289 /* If we are widening a signed type to another signed type, we
7290 want to obtain -2^^(iprec-1). If we are keeping the
7291 precision or narrowing to a signed type, we want to obtain
7292 -2^(oprec-1). */
7293 unsigned prec = oprec > iprec ? iprec : oprec;
7295 if (prec <= HOST_BITS_PER_WIDE_INT)
7297 hi = ~(unsigned HOST_WIDE_INT) 0;
7298 lo = (~(unsigned HOST_WIDE_INT) 0) << (prec - 1);
7300 else
7302 hi = ((~(unsigned HOST_WIDE_INT) 0)
7303 << (prec - HOST_BITS_PER_WIDE_INT - 1));
7304 lo = 0;
7308 return build_int_cst_wide (outer, lo, hi);
7311 /* Return nonzero if two operands that are suitable for PHI nodes are
7312 necessarily equal. Specifically, both ARG0 and ARG1 must be either
7313 SSA_NAME or invariant. Note that this is strictly an optimization.
7314 That is, callers of this function can directly call operand_equal_p
7315 and get the same result, only slower. */
7318 operand_equal_for_phi_arg_p (tree arg0, tree arg1)
7320 if (arg0 == arg1)
7321 return 1;
7322 if (TREE_CODE (arg0) == SSA_NAME || TREE_CODE (arg1) == SSA_NAME)
7323 return 0;
7324 return operand_equal_p (arg0, arg1, 0);
7327 /* Returns number of zeros at the end of binary representation of X.
7329 ??? Use ffs if available? */
7331 tree
7332 num_ending_zeros (tree x)
7334 unsigned HOST_WIDE_INT fr, nfr;
7335 unsigned num, abits;
7336 tree type = TREE_TYPE (x);
7338 if (TREE_INT_CST_LOW (x) == 0)
7340 num = HOST_BITS_PER_WIDE_INT;
7341 fr = TREE_INT_CST_HIGH (x);
7343 else
7345 num = 0;
7346 fr = TREE_INT_CST_LOW (x);
7349 for (abits = HOST_BITS_PER_WIDE_INT / 2; abits; abits /= 2)
7351 nfr = fr >> abits;
7352 if (nfr << abits == fr)
7354 num += abits;
7355 fr = nfr;
7359 if (num > TYPE_PRECISION (type))
7360 num = TYPE_PRECISION (type);
7362 return build_int_cst_type (type, num);
7366 #define WALK_SUBTREE(NODE) \
7367 do \
7369 result = walk_tree (&(NODE), func, data, pset); \
7370 if (result) \
7371 return result; \
7373 while (0)
7375 /* This is a subroutine of walk_tree that walks field of TYPE that are to
7376 be walked whenever a type is seen in the tree. Rest of operands and return
7377 value are as for walk_tree. */
7379 static tree
7380 walk_type_fields (tree type, walk_tree_fn func, void *data,
7381 struct pointer_set_t *pset)
7383 tree result = NULL_TREE;
7385 switch (TREE_CODE (type))
7387 case POINTER_TYPE:
7388 case REFERENCE_TYPE:
7389 /* We have to worry about mutually recursive pointers. These can't
7390 be written in C. They can in Ada. It's pathological, but
7391 there's an ACATS test (c38102a) that checks it. Deal with this
7392 by checking if we're pointing to another pointer, that one
7393 points to another pointer, that one does too, and we have no htab.
7394 If so, get a hash table. We check three levels deep to avoid
7395 the cost of the hash table if we don't need one. */
7396 if (POINTER_TYPE_P (TREE_TYPE (type))
7397 && POINTER_TYPE_P (TREE_TYPE (TREE_TYPE (type)))
7398 && POINTER_TYPE_P (TREE_TYPE (TREE_TYPE (TREE_TYPE (type))))
7399 && !pset)
7401 result = walk_tree_without_duplicates (&TREE_TYPE (type),
7402 func, data);
7403 if (result)
7404 return result;
7406 break;
7409 /* ... fall through ... */
7411 case COMPLEX_TYPE:
7412 WALK_SUBTREE (TREE_TYPE (type));
7413 break;
7415 case METHOD_TYPE:
7416 WALK_SUBTREE (TYPE_METHOD_BASETYPE (type));
7418 /* Fall through. */
7420 case FUNCTION_TYPE:
7421 WALK_SUBTREE (TREE_TYPE (type));
7423 tree arg;
7425 /* We never want to walk into default arguments. */
7426 for (arg = TYPE_ARG_TYPES (type); arg; arg = TREE_CHAIN (arg))
7427 WALK_SUBTREE (TREE_VALUE (arg));
7429 break;
7431 case ARRAY_TYPE:
7432 /* Don't follow this nodes's type if a pointer for fear that we'll
7433 have infinite recursion. Those types are uninteresting anyway. */
7434 if (!POINTER_TYPE_P (TREE_TYPE (type))
7435 && TREE_CODE (TREE_TYPE (type)) != OFFSET_TYPE)
7436 WALK_SUBTREE (TREE_TYPE (type));
7437 WALK_SUBTREE (TYPE_DOMAIN (type));
7438 break;
7440 case BOOLEAN_TYPE:
7441 case ENUMERAL_TYPE:
7442 case INTEGER_TYPE:
7443 case REAL_TYPE:
7444 WALK_SUBTREE (TYPE_MIN_VALUE (type));
7445 WALK_SUBTREE (TYPE_MAX_VALUE (type));
7446 break;
7448 case OFFSET_TYPE:
7449 WALK_SUBTREE (TREE_TYPE (type));
7450 WALK_SUBTREE (TYPE_OFFSET_BASETYPE (type));
7451 break;
7453 default:
7454 break;
7457 return NULL_TREE;
7460 /* Apply FUNC to all the sub-trees of TP in a pre-order traversal. FUNC is
7461 called with the DATA and the address of each sub-tree. If FUNC returns a
7462 non-NULL value, the traversal is stopped, and the value returned by FUNC
7463 is returned. If PSET is non-NULL it is used to record the nodes visited,
7464 and to avoid visiting a node more than once. */
7466 tree
7467 walk_tree (tree *tp, walk_tree_fn func, void *data, struct pointer_set_t *pset)
7469 enum tree_code code;
7470 int walk_subtrees;
7471 tree result;
7473 #define WALK_SUBTREE_TAIL(NODE) \
7474 do \
7476 tp = & (NODE); \
7477 goto tail_recurse; \
7479 while (0)
7481 tail_recurse:
7482 /* Skip empty subtrees. */
7483 if (!*tp)
7484 return NULL_TREE;
7486 /* Don't walk the same tree twice, if the user has requested
7487 that we avoid doing so. */
7488 if (pset && pointer_set_insert (pset, *tp))
7489 return NULL_TREE;
7491 /* Call the function. */
7492 walk_subtrees = 1;
7493 result = (*func) (tp, &walk_subtrees, data);
7495 /* If we found something, return it. */
7496 if (result)
7497 return result;
7499 code = TREE_CODE (*tp);
7501 /* Even if we didn't, FUNC may have decided that there was nothing
7502 interesting below this point in the tree. */
7503 if (!walk_subtrees)
7505 /* But we still need to check our siblings. */
7506 if (code == TREE_LIST)
7507 WALK_SUBTREE_TAIL (TREE_CHAIN (*tp));
7508 else if (code == OMP_CLAUSE)
7509 WALK_SUBTREE_TAIL (OMP_CLAUSE_CHAIN (*tp));
7510 else
7511 return NULL_TREE;
7514 result = lang_hooks.tree_inlining.walk_subtrees (tp, &walk_subtrees, func,
7515 data, pset);
7516 if (result || ! walk_subtrees)
7517 return result;
7519 switch (code)
7521 case ERROR_MARK:
7522 case IDENTIFIER_NODE:
7523 case INTEGER_CST:
7524 case REAL_CST:
7525 case VECTOR_CST:
7526 case STRING_CST:
7527 case BLOCK:
7528 case PLACEHOLDER_EXPR:
7529 case SSA_NAME:
7530 case FIELD_DECL:
7531 case RESULT_DECL:
7532 /* None of these have subtrees other than those already walked
7533 above. */
7534 break;
7536 case TREE_LIST:
7537 WALK_SUBTREE (TREE_VALUE (*tp));
7538 WALK_SUBTREE_TAIL (TREE_CHAIN (*tp));
7539 break;
7541 case TREE_VEC:
7543 int len = TREE_VEC_LENGTH (*tp);
7545 if (len == 0)
7546 break;
7548 /* Walk all elements but the first. */
7549 while (--len)
7550 WALK_SUBTREE (TREE_VEC_ELT (*tp, len));
7552 /* Now walk the first one as a tail call. */
7553 WALK_SUBTREE_TAIL (TREE_VEC_ELT (*tp, 0));
7556 case COMPLEX_CST:
7557 WALK_SUBTREE (TREE_REALPART (*tp));
7558 WALK_SUBTREE_TAIL (TREE_IMAGPART (*tp));
7560 case CONSTRUCTOR:
7562 unsigned HOST_WIDE_INT idx;
7563 constructor_elt *ce;
7565 for (idx = 0;
7566 VEC_iterate(constructor_elt, CONSTRUCTOR_ELTS (*tp), idx, ce);
7567 idx++)
7568 WALK_SUBTREE (ce->value);
7570 break;
7572 case SAVE_EXPR:
7573 WALK_SUBTREE_TAIL (TREE_OPERAND (*tp, 0));
7575 case BIND_EXPR:
7577 tree decl;
7578 for (decl = BIND_EXPR_VARS (*tp); decl; decl = TREE_CHAIN (decl))
7580 /* Walk the DECL_INITIAL and DECL_SIZE. We don't want to walk
7581 into declarations that are just mentioned, rather than
7582 declared; they don't really belong to this part of the tree.
7583 And, we can see cycles: the initializer for a declaration
7584 can refer to the declaration itself. */
7585 WALK_SUBTREE (DECL_INITIAL (decl));
7586 WALK_SUBTREE (DECL_SIZE (decl));
7587 WALK_SUBTREE (DECL_SIZE_UNIT (decl));
7589 WALK_SUBTREE_TAIL (BIND_EXPR_BODY (*tp));
7592 case STATEMENT_LIST:
7594 tree_stmt_iterator i;
7595 for (i = tsi_start (*tp); !tsi_end_p (i); tsi_next (&i))
7596 WALK_SUBTREE (*tsi_stmt_ptr (i));
7598 break;
7600 case OMP_CLAUSE:
7601 switch (OMP_CLAUSE_CODE (*tp))
7603 case OMP_CLAUSE_PRIVATE:
7604 case OMP_CLAUSE_SHARED:
7605 case OMP_CLAUSE_FIRSTPRIVATE:
7606 case OMP_CLAUSE_LASTPRIVATE:
7607 case OMP_CLAUSE_COPYIN:
7608 case OMP_CLAUSE_COPYPRIVATE:
7609 case OMP_CLAUSE_IF:
7610 case OMP_CLAUSE_NUM_THREADS:
7611 case OMP_CLAUSE_SCHEDULE:
7612 WALK_SUBTREE (OMP_CLAUSE_OPERAND (*tp, 0));
7613 /* FALLTHRU */
7615 case OMP_CLAUSE_NOWAIT:
7616 case OMP_CLAUSE_ORDERED:
7617 case OMP_CLAUSE_DEFAULT:
7618 WALK_SUBTREE_TAIL (OMP_CLAUSE_CHAIN (*tp));
7620 case OMP_CLAUSE_REDUCTION:
7622 int i;
7623 for (i = 0; i < 4; i++)
7624 WALK_SUBTREE (OMP_CLAUSE_OPERAND (*tp, i));
7625 WALK_SUBTREE_TAIL (OMP_CLAUSE_CHAIN (*tp));
7628 default:
7629 gcc_unreachable ();
7631 break;
7633 case TARGET_EXPR:
7635 int i, len;
7637 /* TARGET_EXPRs are peculiar: operands 1 and 3 can be the same.
7638 But, we only want to walk once. */
7639 len = (TREE_OPERAND (*tp, 3) == TREE_OPERAND (*tp, 1)) ? 2 : 3;
7640 for (i = 0; i < len; ++i)
7641 WALK_SUBTREE (TREE_OPERAND (*tp, i));
7642 WALK_SUBTREE_TAIL (TREE_OPERAND (*tp, len));
7645 case DECL_EXPR:
7646 /* Walk into various fields of the type that it's defining. We only
7647 want to walk into these fields of a type in this case. Note that
7648 decls get walked as part of the processing of a BIND_EXPR.
7650 ??? Precisely which fields of types that we are supposed to walk in
7651 this case vs. the normal case aren't well defined. */
7652 if (TREE_CODE (DECL_EXPR_DECL (*tp)) == TYPE_DECL
7653 && TREE_CODE (TREE_TYPE (DECL_EXPR_DECL (*tp))) != ERROR_MARK)
7655 tree *type_p = &TREE_TYPE (DECL_EXPR_DECL (*tp));
7657 /* Call the function for the type. See if it returns anything or
7658 doesn't want us to continue. If we are to continue, walk both
7659 the normal fields and those for the declaration case. */
7660 result = (*func) (type_p, &walk_subtrees, data);
7661 if (result || !walk_subtrees)
7662 return NULL_TREE;
7664 result = walk_type_fields (*type_p, func, data, pset);
7665 if (result)
7666 return result;
7668 /* If this is a record type, also walk the fields. */
7669 if (TREE_CODE (*type_p) == RECORD_TYPE
7670 || TREE_CODE (*type_p) == UNION_TYPE
7671 || TREE_CODE (*type_p) == QUAL_UNION_TYPE)
7673 tree field;
7675 for (field = TYPE_FIELDS (*type_p); field;
7676 field = TREE_CHAIN (field))
7678 /* We'd like to look at the type of the field, but we can
7679 easily get infinite recursion. So assume it's pointed
7680 to elsewhere in the tree. Also, ignore things that
7681 aren't fields. */
7682 if (TREE_CODE (field) != FIELD_DECL)
7683 continue;
7685 WALK_SUBTREE (DECL_FIELD_OFFSET (field));
7686 WALK_SUBTREE (DECL_SIZE (field));
7687 WALK_SUBTREE (DECL_SIZE_UNIT (field));
7688 if (TREE_CODE (*type_p) == QUAL_UNION_TYPE)
7689 WALK_SUBTREE (DECL_QUALIFIER (field));
7693 WALK_SUBTREE (TYPE_SIZE (*type_p));
7694 WALK_SUBTREE_TAIL (TYPE_SIZE_UNIT (*type_p));
7696 /* FALLTHRU */
7698 default:
7699 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
7701 int i, len;
7703 /* Walk over all the sub-trees of this operand. */
7704 len = TREE_CODE_LENGTH (code);
7706 /* Go through the subtrees. We need to do this in forward order so
7707 that the scope of a FOR_EXPR is handled properly. */
7708 if (len)
7710 for (i = 0; i < len - 1; ++i)
7711 WALK_SUBTREE (TREE_OPERAND (*tp, i));
7712 WALK_SUBTREE_TAIL (TREE_OPERAND (*tp, len - 1));
7716 /* If this is a type, walk the needed fields in the type. */
7717 else if (TYPE_P (*tp))
7718 return walk_type_fields (*tp, func, data, pset);
7719 break;
7722 /* We didn't find what we were looking for. */
7723 return NULL_TREE;
7725 #undef WALK_SUBTREE_TAIL
7727 #undef WALK_SUBTREE
7729 /* Like walk_tree, but does not walk duplicate nodes more than once. */
7731 tree
7732 walk_tree_without_duplicates (tree *tp, walk_tree_fn func, void *data)
7734 tree result;
7735 struct pointer_set_t *pset;
7737 pset = pointer_set_create ();
7738 result = walk_tree (tp, func, data, pset);
7739 pointer_set_destroy (pset);
7740 return result;
7744 /* Return true if STMT is an empty statement or contains nothing but
7745 empty statements. */
7747 bool
7748 empty_body_p (tree stmt)
7750 tree_stmt_iterator i;
7751 tree body;
7753 if (IS_EMPTY_STMT (stmt))
7754 return true;
7755 else if (TREE_CODE (stmt) == BIND_EXPR)
7756 body = BIND_EXPR_BODY (stmt);
7757 else if (TREE_CODE (stmt) == STATEMENT_LIST)
7758 body = stmt;
7759 else
7760 return false;
7762 for (i = tsi_start (body); !tsi_end_p (i); tsi_next (&i))
7763 if (!empty_body_p (tsi_stmt (i)))
7764 return false;
7766 return true;
7769 #include "gt-tree.h"