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