1/* Language-independent node constructors for parse phase of GNU compiler.
2 Copyright (C) 1987-2017 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it under
7the terms of the GNU General Public License as published by the Free
8Software Foundation; either version 3, or (at your option) any later
9version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14for more details.
15
16You should have received a copy of the GNU General Public License
17along with GCC; see the file COPYING3. If not see
18<http://www.gnu.org/licenses/>. */
19
20/* This file contains the low level primitives for operating on tree nodes,
21 including allocation, list operations, interning of identifiers,
22 construction of data type nodes and statement nodes,
23 and construction of type conversion nodes. It also contains
24 tables index by tree code that describe how to take apart
25 nodes of that code.
26
27 It is intended to be language-independent but can occasionally
28 calls language-dependent routines. */
29
30#include "config.h"
31#include "system.h"
32#include "coretypes.h"
33#include "backend.h"
34#include "target.h"
35#include "tree.h"
36#include "gimple.h"
37#include "tree-pass.h"
38#include "ssa.h"
39#include "cgraph.h"
40#include "diagnostic.h"
41#include "flags.h"
42#include "alias.h"
43#include "fold-const.h"
44#include "stor-layout.h"
45#include "calls.h"
46#include "attribs.h"
47#include "toplev.h" /* get_random_seed */
48#include "output.h"
49#include "common/common-target.h"
50#include "langhooks.h"
51#include "tree-inline.h"
52#include "tree-iterator.h"
53#include "internal-fn.h"
54#include "gimple-iterator.h"
55#include "gimplify.h"
56#include "tree-dfa.h"
57#include "params.h"
58#include "langhooks-def.h"
59#include "tree-diagnostic.h"
60#include "except.h"
61#include "builtins.h"
62#include "print-tree.h"
63#include "ipa-utils.h"
64#include "selftest.h"
65#include "stringpool.h"
66#include "attribs.h"
67#include "rtl.h"
68#include "regs.h"
69#include "tree-vector-builder.h"
70
71/* Tree code classes. */
72
73#define DEFTREECODE(SYM, NAME, TYPE, LENGTH) TYPE,
74#define END_OF_BASE_TREE_CODES tcc_exceptional,
75
76const enum tree_code_class tree_code_type[] = {
77#include "all-tree.def"
78};
79
80#undef DEFTREECODE
81#undef END_OF_BASE_TREE_CODES
82
83/* Table indexed by tree code giving number of expression
84 operands beyond the fixed part of the node structure.
85 Not used for types or decls. */
86
87#define DEFTREECODE(SYM, NAME, TYPE, LENGTH) LENGTH,
88#define END_OF_BASE_TREE_CODES 0,
89
90const unsigned char tree_code_length[] = {
91#include "all-tree.def"
92};
93
94#undef DEFTREECODE
95#undef END_OF_BASE_TREE_CODES
96
97/* Names of tree components.
98 Used for printing out the tree and error messages. */
99#define DEFTREECODE(SYM, NAME, TYPE, LEN) NAME,
100#define END_OF_BASE_TREE_CODES "@dummy",
101
102static const char *const tree_code_name[] = {
103#include "all-tree.def"
104};
105
106#undef DEFTREECODE
107#undef END_OF_BASE_TREE_CODES
108
109/* Each tree code class has an associated string representation.
110 These must correspond to the tree_code_class entries. */
111
112const char *const tree_code_class_strings[] =
113{
114 "exceptional",
115 "constant",
116 "type",
117 "declaration",
118 "reference",
119 "comparison",
120 "unary",
121 "binary",
122 "statement",
123 "vl_exp",
124 "expression"
125};
126
127/* obstack.[ch] explicitly declined to prototype this. */
128extern int _obstack_allocated_p (struct obstack *h, void *obj);
129
130/* Statistics-gathering stuff. */
131
132static int tree_code_counts[MAX_TREE_CODES];
133int tree_node_counts[(int) all_kinds];
134int tree_node_sizes[(int) all_kinds];
135
136/* Keep in sync with tree.h:enum tree_node_kind. */
137static const char * const tree_node_kind_names[] = {
138 "decls",
139 "types",
140 "blocks",
141 "stmts",
142 "refs",
143 "exprs",
144 "constants",
145 "identifiers",
146 "vecs",
147 "binfos",
148 "ssa names",
149 "constructors",
150 "random kinds",
151 "lang_decl kinds",
152 "lang_type kinds",
153 "omp clauses",
154};
155
156/* Unique id for next decl created. */
157static GTY(()) int next_decl_uid;
158/* Unique id for next type created. */
159static GTY(()) unsigned next_type_uid = 1;
160/* Unique id for next debug decl created. Use negative numbers,
161 to catch erroneous uses. */
162static GTY(()) int next_debug_decl_uid;
163
164/* Since we cannot rehash a type after it is in the table, we have to
165 keep the hash code. */
166
167struct GTY((for_user)) type_hash {
168 unsigned long hash;
169 tree type;
170};
171
172/* Initial size of the hash table (rounded to next prime). */
173#define TYPE_HASH_INITIAL_SIZE 1000
174
175struct type_cache_hasher : ggc_cache_ptr_hash<type_hash>
176{
177 static hashval_t hash (type_hash *t) { return t->hash; }
178 static bool equal (type_hash *a, type_hash *b);
179
180 static int
181 keep_cache_entry (type_hash *&t)
182 {
183 return ggc_marked_p (t->type);
184 }
185};
186
187/* Now here is the hash table. When recording a type, it is added to
188 the slot whose index is the hash code. Note that the hash table is
189 used for several kinds of types (function types, array types and
190 array index range types, for now). While all these live in the
191 same table, they are completely independent, and the hash code is
192 computed differently for each of these. */
193
194static GTY ((cache)) hash_table<type_cache_hasher> *type_hash_table;
195
196/* Hash table and temporary node for larger integer const values. */
197static GTY (()) tree int_cst_node;
198
199struct int_cst_hasher : ggc_cache_ptr_hash<tree_node>
200{
201 static hashval_t hash (tree t);
202 static bool equal (tree x, tree y);
203};
204
205static GTY ((cache)) hash_table<int_cst_hasher> *int_cst_hash_table;
206
207/* Hash table for optimization flags and target option flags. Use the same
208 hash table for both sets of options. Nodes for building the current
209 optimization and target option nodes. The assumption is most of the time
210 the options created will already be in the hash table, so we avoid
211 allocating and freeing up a node repeatably. */
212static GTY (()) tree cl_optimization_node;
213static GTY (()) tree cl_target_option_node;
214
215struct cl_option_hasher : ggc_cache_ptr_hash<tree_node>
216{
217 static hashval_t hash (tree t);
218 static bool equal (tree x, tree y);
219};
220
221static GTY ((cache)) hash_table<cl_option_hasher> *cl_option_hash_table;
222
223/* General tree->tree mapping structure for use in hash tables. */
224
225
226static GTY ((cache))
227 hash_table<tree_decl_map_cache_hasher> *debug_expr_for_decl;
228
229static GTY ((cache))
230 hash_table<tree_decl_map_cache_hasher> *value_expr_for_decl;
231
232struct tree_vec_map_cache_hasher : ggc_cache_ptr_hash<tree_vec_map>
233{
234 static hashval_t hash (tree_vec_map *m) { return DECL_UID (m->base.from); }
235
236 static bool
237 equal (tree_vec_map *a, tree_vec_map *b)
238 {
239 return a->base.from == b->base.from;
240 }
241
242 static int
243 keep_cache_entry (tree_vec_map *&m)
244 {
245 return ggc_marked_p (m->base.from);
246 }
247};
248
249static GTY ((cache))
250 hash_table<tree_vec_map_cache_hasher> *debug_args_for_decl;
251
252static void set_type_quals (tree, int);
253static void print_type_hash_statistics (void);
254static void print_debug_expr_statistics (void);
255static void print_value_expr_statistics (void);
256
257tree global_trees[TI_MAX];
258tree integer_types[itk_none];
259
260bool int_n_enabled_p[NUM_INT_N_ENTS];
261struct int_n_trees_t int_n_trees [NUM_INT_N_ENTS];
262
263bool tree_contains_struct[MAX_TREE_CODES][64];
264
265/* Number of operands for each OpenMP clause. */
266unsigned const char omp_clause_num_ops[] =
267{
268 0, /* OMP_CLAUSE_ERROR */
269 1, /* OMP_CLAUSE_PRIVATE */
270 1, /* OMP_CLAUSE_SHARED */
271 1, /* OMP_CLAUSE_FIRSTPRIVATE */
272 2, /* OMP_CLAUSE_LASTPRIVATE */
273 5, /* OMP_CLAUSE_REDUCTION */
274 1, /* OMP_CLAUSE_COPYIN */
275 1, /* OMP_CLAUSE_COPYPRIVATE */
276 3, /* OMP_CLAUSE_LINEAR */
277 2, /* OMP_CLAUSE_ALIGNED */
278 1, /* OMP_CLAUSE_DEPEND */
279 1, /* OMP_CLAUSE_UNIFORM */
280 1, /* OMP_CLAUSE_TO_DECLARE */
281 1, /* OMP_CLAUSE_LINK */
282 2, /* OMP_CLAUSE_FROM */
283 2, /* OMP_CLAUSE_TO */
284 2, /* OMP_CLAUSE_MAP */
285 1, /* OMP_CLAUSE_USE_DEVICE_PTR */
286 1, /* OMP_CLAUSE_IS_DEVICE_PTR */
287 2, /* OMP_CLAUSE__CACHE_ */
288 2, /* OMP_CLAUSE_GANG */
289 1, /* OMP_CLAUSE_ASYNC */
290 1, /* OMP_CLAUSE_WAIT */
291 0, /* OMP_CLAUSE_AUTO */
292 0, /* OMP_CLAUSE_SEQ */
293 1, /* OMP_CLAUSE__LOOPTEMP_ */
294 1, /* OMP_CLAUSE_IF */
295 1, /* OMP_CLAUSE_NUM_THREADS */
296 1, /* OMP_CLAUSE_SCHEDULE */
297 0, /* OMP_CLAUSE_NOWAIT */
298 1, /* OMP_CLAUSE_ORDERED */
299 0, /* OMP_CLAUSE_DEFAULT */
300 3, /* OMP_CLAUSE_COLLAPSE */
301 0, /* OMP_CLAUSE_UNTIED */
302 1, /* OMP_CLAUSE_FINAL */
303 0, /* OMP_CLAUSE_MERGEABLE */
304 1, /* OMP_CLAUSE_DEVICE */
305 1, /* OMP_CLAUSE_DIST_SCHEDULE */
306 0, /* OMP_CLAUSE_INBRANCH */
307 0, /* OMP_CLAUSE_NOTINBRANCH */
308 1, /* OMP_CLAUSE_NUM_TEAMS */
309 1, /* OMP_CLAUSE_THREAD_LIMIT */
310 0, /* OMP_CLAUSE_PROC_BIND */
311 1, /* OMP_CLAUSE_SAFELEN */
312 1, /* OMP_CLAUSE_SIMDLEN */
313 0, /* OMP_CLAUSE_FOR */
314 0, /* OMP_CLAUSE_PARALLEL */
315 0, /* OMP_CLAUSE_SECTIONS */
316 0, /* OMP_CLAUSE_TASKGROUP */
317 1, /* OMP_CLAUSE_PRIORITY */
318 1, /* OMP_CLAUSE_GRAINSIZE */
319 1, /* OMP_CLAUSE_NUM_TASKS */
320 0, /* OMP_CLAUSE_NOGROUP */
321 0, /* OMP_CLAUSE_THREADS */
322 0, /* OMP_CLAUSE_SIMD */
323 1, /* OMP_CLAUSE_HINT */
324 0, /* OMP_CLAUSE_DEFALTMAP */
325 1, /* OMP_CLAUSE__SIMDUID_ */
326 0, /* OMP_CLAUSE__SIMT_ */
327 0, /* OMP_CLAUSE_INDEPENDENT */
328 1, /* OMP_CLAUSE_WORKER */
329 1, /* OMP_CLAUSE_VECTOR */
330 1, /* OMP_CLAUSE_NUM_GANGS */
331 1, /* OMP_CLAUSE_NUM_WORKERS */
332 1, /* OMP_CLAUSE_VECTOR_LENGTH */
333 3, /* OMP_CLAUSE_TILE */
334 2, /* OMP_CLAUSE__GRIDDIM_ */
335};
336
337const char * const omp_clause_code_name[] =
338{
339 "error_clause",
340 "private",
341 "shared",
342 "firstprivate",
343 "lastprivate",
344 "reduction",
345 "copyin",
346 "copyprivate",
347 "linear",
348 "aligned",
349 "depend",
350 "uniform",
351 "to",
352 "link",
353 "from",
354 "to",
355 "map",
356 "use_device_ptr",
357 "is_device_ptr",
358 "_cache_",
359 "gang",
360 "async",
361 "wait",
362 "auto",
363 "seq",
364 "_looptemp_",
365 "if",
366 "num_threads",
367 "schedule",
368 "nowait",
369 "ordered",
370 "default",
371 "collapse",
372 "untied",
373 "final",
374 "mergeable",
375 "device",
376 "dist_schedule",
377 "inbranch",
378 "notinbranch",
379 "num_teams",
380 "thread_limit",
381 "proc_bind",
382 "safelen",
383 "simdlen",
384 "for",
385 "parallel",
386 "sections",
387 "taskgroup",
388 "priority",
389 "grainsize",
390 "num_tasks",
391 "nogroup",
392 "threads",
393 "simd",
394 "hint",
395 "defaultmap",
396 "_simduid_",
397 "_simt_",
398 "independent",
399 "worker",
400 "vector",
401 "num_gangs",
402 "num_workers",
403 "vector_length",
404 "tile",
405 "_griddim_"
406};
407
408
409/* Return the tree node structure used by tree code CODE. */
410
411static inline enum tree_node_structure_enum
412tree_node_structure_for_code (enum tree_code code)
413{
414 switch (TREE_CODE_CLASS (code))
415 {
416 case tcc_declaration:
417 {
418 switch (code)
419 {
420 case FIELD_DECL:
421 return TS_FIELD_DECL;
422 case PARM_DECL:
423 return TS_PARM_DECL;
424 case VAR_DECL:
425 return TS_VAR_DECL;
426 case LABEL_DECL:
427 return TS_LABEL_DECL;
428 case RESULT_DECL:
429 return TS_RESULT_DECL;
430 case DEBUG_EXPR_DECL:
431 return TS_DECL_WRTL;
432 case CONST_DECL:
433 return TS_CONST_DECL;
434 case TYPE_DECL:
435 return TS_TYPE_DECL;
436 case FUNCTION_DECL:
437 return TS_FUNCTION_DECL;
438 case TRANSLATION_UNIT_DECL:
439 return TS_TRANSLATION_UNIT_DECL;
440 default:
441 return TS_DECL_NON_COMMON;
442 }
443 }
444 case tcc_type:
445 return TS_TYPE_NON_COMMON;
446 case tcc_reference:
447 case tcc_comparison:
448 case tcc_unary:
449 case tcc_binary:
450 case tcc_expression:
451 case tcc_statement:
452 case tcc_vl_exp:
453 return TS_EXP;
454 default: /* tcc_constant and tcc_exceptional */
455 break;
456 }
457 switch (code)
458 {
459 /* tcc_constant cases. */
460 case VOID_CST: return TS_TYPED;
461 case INTEGER_CST: return TS_INT_CST;
462 case REAL_CST: return TS_REAL_CST;
463 case FIXED_CST: return TS_FIXED_CST;
464 case COMPLEX_CST: return TS_COMPLEX;
465 case VECTOR_CST: return TS_VECTOR;
466 case STRING_CST: return TS_STRING;
467 /* tcc_exceptional cases. */
468 case ERROR_MARK: return TS_COMMON;
469 case IDENTIFIER_NODE: return TS_IDENTIFIER;
470 case TREE_LIST: return TS_LIST;
471 case TREE_VEC: return TS_VEC;
472 case SSA_NAME: return TS_SSA_NAME;
473 case PLACEHOLDER_EXPR: return TS_COMMON;
474 case STATEMENT_LIST: return TS_STATEMENT_LIST;
475 case BLOCK: return TS_BLOCK;
476 case CONSTRUCTOR: return TS_CONSTRUCTOR;
477 case TREE_BINFO: return TS_BINFO;
478 case OMP_CLAUSE: return TS_OMP_CLAUSE;
479 case OPTIMIZATION_NODE: return TS_OPTIMIZATION;
480 case TARGET_OPTION_NODE: return TS_TARGET_OPTION;
481
482 default:
483 gcc_unreachable ();
484 }
485}
486
487
488/* Initialize tree_contains_struct to describe the hierarchy of tree
489 nodes. */
490
491static void
492initialize_tree_contains_struct (void)
493{
494 unsigned i;
495
496 for (i = ERROR_MARK; i < LAST_AND_UNUSED_TREE_CODE; i++)
497 {
498 enum tree_code code;
499 enum tree_node_structure_enum ts_code;
500
501 code = (enum tree_code) i;
502 ts_code = tree_node_structure_for_code (code);
503
504 /* Mark the TS structure itself. */
505 tree_contains_struct[code][ts_code] = 1;
506
507 /* Mark all the structures that TS is derived from. */
508 switch (ts_code)
509 {
510 case TS_TYPED:
511 case TS_BLOCK:
512 case TS_OPTIMIZATION:
513 case TS_TARGET_OPTION:
514 MARK_TS_BASE (code);
515 break;
516
517 case TS_COMMON:
518 case TS_INT_CST:
519 case TS_REAL_CST:
520 case TS_FIXED_CST:
521 case TS_VECTOR:
522 case TS_STRING:
523 case TS_COMPLEX:
524 case TS_SSA_NAME:
525 case TS_CONSTRUCTOR:
526 case TS_EXP:
527 case TS_STATEMENT_LIST:
528 MARK_TS_TYPED (code);
529 break;
530
531 case TS_IDENTIFIER:
532 case TS_DECL_MINIMAL:
533 case TS_TYPE_COMMON:
534 case TS_LIST:
535 case TS_VEC:
536 case TS_BINFO:
537 case TS_OMP_CLAUSE:
538 MARK_TS_COMMON (code);
539 break;
540
541 case TS_TYPE_WITH_LANG_SPECIFIC:
542 MARK_TS_TYPE_COMMON (code);
543 break;
544
545 case TS_TYPE_NON_COMMON:
546 MARK_TS_TYPE_WITH_LANG_SPECIFIC (code);
547 break;
548
549 case TS_DECL_COMMON:
550 MARK_TS_DECL_MINIMAL (code);
551 break;
552
553 case TS_DECL_WRTL:
554 case TS_CONST_DECL:
555 MARK_TS_DECL_COMMON (code);
556 break;
557
558 case TS_DECL_NON_COMMON:
559 MARK_TS_DECL_WITH_VIS (code);
560 break;
561
562 case TS_DECL_WITH_VIS:
563 case TS_PARM_DECL:
564 case TS_LABEL_DECL:
565 case TS_RESULT_DECL:
566 MARK_TS_DECL_WRTL (code);
567 break;
568
569 case TS_FIELD_DECL:
570 MARK_TS_DECL_COMMON (code);
571 break;
572
573 case TS_VAR_DECL:
574 MARK_TS_DECL_WITH_VIS (code);
575 break;
576
577 case TS_TYPE_DECL:
578 case TS_FUNCTION_DECL:
579 MARK_TS_DECL_NON_COMMON (code);
580 break;
581
582 case TS_TRANSLATION_UNIT_DECL:
583 MARK_TS_DECL_COMMON (code);
584 break;
585
586 default:
587 gcc_unreachable ();
588 }
589 }
590
591 /* Basic consistency checks for attributes used in fold. */
592 gcc_assert (tree_contains_struct[FUNCTION_DECL][TS_DECL_NON_COMMON]);
593 gcc_assert (tree_contains_struct[TYPE_DECL][TS_DECL_NON_COMMON]);
594 gcc_assert (tree_contains_struct[CONST_DECL][TS_DECL_COMMON]);
595 gcc_assert (tree_contains_struct[VAR_DECL][TS_DECL_COMMON]);
596 gcc_assert (tree_contains_struct[PARM_DECL][TS_DECL_COMMON]);
597 gcc_assert (tree_contains_struct[RESULT_DECL][TS_DECL_COMMON]);
598 gcc_assert (tree_contains_struct[FUNCTION_DECL][TS_DECL_COMMON]);
599 gcc_assert (tree_contains_struct[TYPE_DECL][TS_DECL_COMMON]);
600 gcc_assert (tree_contains_struct[TRANSLATION_UNIT_DECL][TS_DECL_COMMON]);
601 gcc_assert (tree_contains_struct[LABEL_DECL][TS_DECL_COMMON]);
602 gcc_assert (tree_contains_struct[FIELD_DECL][TS_DECL_COMMON]);
603 gcc_assert (tree_contains_struct[VAR_DECL][TS_DECL_WRTL]);
604 gcc_assert (tree_contains_struct[PARM_DECL][TS_DECL_WRTL]);
605 gcc_assert (tree_contains_struct[RESULT_DECL][TS_DECL_WRTL]);
606 gcc_assert (tree_contains_struct[FUNCTION_DECL][TS_DECL_WRTL]);
607 gcc_assert (tree_contains_struct[LABEL_DECL][TS_DECL_WRTL]);
608 gcc_assert (tree_contains_struct[CONST_DECL][TS_DECL_MINIMAL]);
609 gcc_assert (tree_contains_struct[VAR_DECL][TS_DECL_MINIMAL]);
610 gcc_assert (tree_contains_struct[PARM_DECL][TS_DECL_MINIMAL]);
611 gcc_assert (tree_contains_struct[RESULT_DECL][TS_DECL_MINIMAL]);
612 gcc_assert (tree_contains_struct[FUNCTION_DECL][TS_DECL_MINIMAL]);
613 gcc_assert (tree_contains_struct[TYPE_DECL][TS_DECL_MINIMAL]);
614 gcc_assert (tree_contains_struct[TRANSLATION_UNIT_DECL][TS_DECL_MINIMAL]);
615 gcc_assert (tree_contains_struct[LABEL_DECL][TS_DECL_MINIMAL]);
616 gcc_assert (tree_contains_struct[FIELD_DECL][TS_DECL_MINIMAL]);
617 gcc_assert (tree_contains_struct[VAR_DECL][TS_DECL_WITH_VIS]);
618 gcc_assert (tree_contains_struct[FUNCTION_DECL][TS_DECL_WITH_VIS]);
619 gcc_assert (tree_contains_struct[TYPE_DECL][TS_DECL_WITH_VIS]);
620 gcc_assert (tree_contains_struct[VAR_DECL][TS_VAR_DECL]);
621 gcc_assert (tree_contains_struct[FIELD_DECL][TS_FIELD_DECL]);
622 gcc_assert (tree_contains_struct[PARM_DECL][TS_PARM_DECL]);
623 gcc_assert (tree_contains_struct[LABEL_DECL][TS_LABEL_DECL]);
624 gcc_assert (tree_contains_struct[RESULT_DECL][TS_RESULT_DECL]);
625 gcc_assert (tree_contains_struct[CONST_DECL][TS_CONST_DECL]);
626 gcc_assert (tree_contains_struct[TYPE_DECL][TS_TYPE_DECL]);
627 gcc_assert (tree_contains_struct[FUNCTION_DECL][TS_FUNCTION_DECL]);
628 gcc_assert (tree_contains_struct[IMPORTED_DECL][TS_DECL_MINIMAL]);
629 gcc_assert (tree_contains_struct[IMPORTED_DECL][TS_DECL_COMMON]);
630 gcc_assert (tree_contains_struct[NAMELIST_DECL][TS_DECL_MINIMAL]);
631 gcc_assert (tree_contains_struct[NAMELIST_DECL][TS_DECL_COMMON]);
632}
633
634
635/* Init tree.c. */
636
637void
638init_ttree (void)
639{
640 /* Initialize the hash table of types. */
641 type_hash_table
642 = hash_table<type_cache_hasher>::create_ggc (TYPE_HASH_INITIAL_SIZE);
643
644 debug_expr_for_decl
645 = hash_table<tree_decl_map_cache_hasher>::create_ggc (512);
646
647 value_expr_for_decl
648 = hash_table<tree_decl_map_cache_hasher>::create_ggc (512);
649
650 int_cst_hash_table = hash_table<int_cst_hasher>::create_ggc (1024);
651
652 int_cst_node = make_int_cst (1, 1);
653
654 cl_option_hash_table = hash_table<cl_option_hasher>::create_ggc (64);
655
656 cl_optimization_node = make_node (OPTIMIZATION_NODE);
657 cl_target_option_node = make_node (TARGET_OPTION_NODE);
658
659 /* Initialize the tree_contains_struct array. */
660 initialize_tree_contains_struct ();
661 lang_hooks.init_ts ();
662}
663
664
665/* The name of the object as the assembler will see it (but before any
666 translations made by ASM_OUTPUT_LABELREF). Often this is the same
667 as DECL_NAME. It is an IDENTIFIER_NODE. */
668tree
669decl_assembler_name (tree decl)
670{
671 if (!DECL_ASSEMBLER_NAME_SET_P (decl))
672 lang_hooks.set_decl_assembler_name (decl);
673 return DECL_ASSEMBLER_NAME_RAW (decl);
674}
675
676/* The DECL_ASSEMBLER_NAME_RAW of DECL is being explicitly set to NAME
677 (either of which may be NULL). Inform the FE, if this changes the
678 name. */
679
680void
681overwrite_decl_assembler_name (tree decl, tree name)
682{
683 if (DECL_ASSEMBLER_NAME_RAW (decl) != name)
684 lang_hooks.overwrite_decl_assembler_name (decl, name);
685}
686
687/* When the target supports COMDAT groups, this indicates which group the
688 DECL is associated with. This can be either an IDENTIFIER_NODE or a
689 decl, in which case its DECL_ASSEMBLER_NAME identifies the group. */
690tree
691decl_comdat_group (const_tree node)
692{
693 struct symtab_node *snode = symtab_node::get (node);
694 if (!snode)
695 return NULL;
696 return snode->get_comdat_group ();
697}
698
699/* Likewise, but make sure it's been reduced to an IDENTIFIER_NODE. */
700tree
701decl_comdat_group_id (const_tree node)
702{
703 struct symtab_node *snode = symtab_node::get (node);
704 if (!snode)
705 return NULL;
706 return snode->get_comdat_group_id ();
707}
708
709/* When the target supports named section, return its name as IDENTIFIER_NODE
710 or NULL if it is in no section. */
711const char *
712decl_section_name (const_tree node)
713{
714 struct symtab_node *snode = symtab_node::get (node);
715 if (!snode)
716 return NULL;
717 return snode->get_section ();
718}
719
720/* Set section name of NODE to VALUE (that is expected to be
721 identifier node) */
722void
723set_decl_section_name (tree node, const char *value)
724{
725 struct symtab_node *snode;
726
727 if (value == NULL)
728 {
729 snode = symtab_node::get (node);
730 if (!snode)
731 return;
732 }
733 else if (VAR_P (node))
734 snode = varpool_node::get_create (node);
735 else
736 snode = cgraph_node::get_create (node);
737 snode->set_section (value);
738}
739
740/* Return TLS model of a variable NODE. */
741enum tls_model
742decl_tls_model (const_tree node)
743{
744 struct varpool_node *snode = varpool_node::get (node);
745 if (!snode)
746 return TLS_MODEL_NONE;
747 return snode->tls_model;
748}
749
750/* Set TLS model of variable NODE to MODEL. */
751void
752set_decl_tls_model (tree node, enum tls_model model)
753{
754 struct varpool_node *vnode;
755
756 if (model == TLS_MODEL_NONE)
757 {
758 vnode = varpool_node::get (node);
759 if (!vnode)
760 return;
761 }
762 else
763 vnode = varpool_node::get_create (node);
764 vnode->tls_model = model;
765}
766
767/* Compute the number of bytes occupied by a tree with code CODE.
768 This function cannot be used for nodes that have variable sizes,
769 including TREE_VEC, INTEGER_CST, STRING_CST, and CALL_EXPR. */
770size_t
771tree_code_size (enum tree_code code)
772{
773 switch (TREE_CODE_CLASS (code))
774 {
775 case tcc_declaration: /* A decl node */
776 switch (code)
777 {
778 case FIELD_DECL: return sizeof (tree_field_decl);
779 case PARM_DECL: return sizeof (tree_parm_decl);
780 case VAR_DECL: return sizeof (tree_var_decl);
781 case LABEL_DECL: return sizeof (tree_label_decl);
782 case RESULT_DECL: return sizeof (tree_result_decl);
783 case CONST_DECL: return sizeof (tree_const_decl);
784 case TYPE_DECL: return sizeof (tree_type_decl);
785 case FUNCTION_DECL: return sizeof (tree_function_decl);
786 case DEBUG_EXPR_DECL: return sizeof (tree_decl_with_rtl);
787 case TRANSLATION_UNIT_DECL: return sizeof (tree_translation_unit_decl);
788 case NAMESPACE_DECL:
789 case IMPORTED_DECL:
790 case NAMELIST_DECL: return sizeof (tree_decl_non_common);
791 default:
792 gcc_checking_assert (code >= NUM_TREE_CODES);
793 return lang_hooks.tree_size (code);
794 }
795
796 case tcc_type: /* a type node */
797 switch (code)
798 {
799 case OFFSET_TYPE:
800 case ENUMERAL_TYPE:
801 case BOOLEAN_TYPE:
802 case INTEGER_TYPE:
803 case REAL_TYPE:
804 case POINTER_TYPE:
805 case REFERENCE_TYPE:
806 case NULLPTR_TYPE:
807 case FIXED_POINT_TYPE:
808 case COMPLEX_TYPE:
809 case VECTOR_TYPE:
810 case ARRAY_TYPE:
811 case RECORD_TYPE:
812 case UNION_TYPE:
813 case QUAL_UNION_TYPE:
814 case VOID_TYPE:
815 case POINTER_BOUNDS_TYPE:
816 case FUNCTION_TYPE:
817 case METHOD_TYPE:
818 case LANG_TYPE: return sizeof (tree_type_non_common);
819 default:
820 gcc_checking_assert (code >= NUM_TREE_CODES);
821 return lang_hooks.tree_size (code);
822 }
823
824 case tcc_reference: /* a reference */
825 case tcc_expression: /* an expression */
826 case tcc_statement: /* an expression with side effects */
827 case tcc_comparison: /* a comparison expression */
828 case tcc_unary: /* a unary arithmetic expression */
829 case tcc_binary: /* a binary arithmetic expression */
830 return (sizeof (struct tree_exp)
831 + (TREE_CODE_LENGTH (code) - 1) * sizeof (tree));
832
833 case tcc_constant: /* a constant */
834 switch (code)
835 {
836 case VOID_CST: return sizeof (tree_typed);
837 case INTEGER_CST: gcc_unreachable ();
838 case REAL_CST: return sizeof (tree_real_cst);
839 case FIXED_CST: return sizeof (tree_fixed_cst);
840 case COMPLEX_CST: return sizeof (tree_complex);
841 case VECTOR_CST: gcc_unreachable ();
842 case STRING_CST: gcc_unreachable ();
843 default:
844 gcc_checking_assert (code >= NUM_TREE_CODES);
845 return lang_hooks.tree_size (code);
846 }
847
848 case tcc_exceptional: /* something random, like an identifier. */
849 switch (code)
850 {
851 case IDENTIFIER_NODE: return lang_hooks.identifier_size;
852 case TREE_LIST: return sizeof (tree_list);
853
854 case ERROR_MARK:
855 case PLACEHOLDER_EXPR: return sizeof (tree_common);
856
857 case TREE_VEC: gcc_unreachable ();
858 case OMP_CLAUSE: gcc_unreachable ();
859
860 case SSA_NAME: return sizeof (tree_ssa_name);
861
862 case STATEMENT_LIST: return sizeof (tree_statement_list);
863 case BLOCK: return sizeof (struct tree_block);
864 case CONSTRUCTOR: return sizeof (tree_constructor);
865 case OPTIMIZATION_NODE: return sizeof (tree_optimization_option);
866 case TARGET_OPTION_NODE: return sizeof (tree_target_option);
867
868 default:
869 gcc_checking_assert (code >= NUM_TREE_CODES);
870 return lang_hooks.tree_size (code);
871 }
872
873 default:
874 gcc_unreachable ();
875 }
876}
877
878/* Compute the number of bytes occupied by NODE. This routine only
879 looks at TREE_CODE, except for those nodes that have variable sizes. */
880size_t
881tree_size (const_tree node)
882{
883 const enum tree_code code = TREE_CODE (node);
884 switch (code)
885 {
886 case INTEGER_CST:
887 return (sizeof (struct tree_int_cst)
888 + (TREE_INT_CST_EXT_NUNITS (node) - 1) * sizeof (HOST_WIDE_INT));
889
890 case TREE_BINFO:
891 return (offsetof (struct tree_binfo, base_binfos)
892 + vec<tree, va_gc>
893 ::embedded_size (BINFO_N_BASE_BINFOS (node)));
894
895 case TREE_VEC:
896 return (sizeof (struct tree_vec)
897 + (TREE_VEC_LENGTH (node) - 1) * sizeof (tree));
898
899 case VECTOR_CST:
900 return (sizeof (struct tree_vector)
901 + (vector_cst_encoded_nelts (node) - 1) * sizeof (tree));
902
903 case STRING_CST:
904 return TREE_STRING_LENGTH (node) + offsetof (struct tree_string, str) + 1;
905
906 case OMP_CLAUSE:
907 return (sizeof (struct tree_omp_clause)
908 + (omp_clause_num_ops[OMP_CLAUSE_CODE (node)] - 1)
909 * sizeof (tree));
910
911 default:
912 if (TREE_CODE_CLASS (code) == tcc_vl_exp)
913 return (sizeof (struct tree_exp)
914 + (VL_EXP_OPERAND_LENGTH (node) - 1) * sizeof (tree));
915 else
916 return tree_code_size (code);
917 }
918}
919
920/* Record interesting allocation statistics for a tree node with CODE
921 and LENGTH. */
922
923static void
924record_node_allocation_statistics (enum tree_code code ATTRIBUTE_UNUSED,
925 size_t length ATTRIBUTE_UNUSED)
926{
927 enum tree_code_class type = TREE_CODE_CLASS (code);
928 tree_node_kind kind;
929
930 if (!GATHER_STATISTICS)
931 return;
932
933 switch (type)
934 {
935 case tcc_declaration: /* A decl node */
936 kind = d_kind;
937 break;
938
939 case tcc_type: /* a type node */
940 kind = t_kind;
941 break;
942
943 case tcc_statement: /* an expression with side effects */
944 kind = s_kind;
945 break;
946
947 case tcc_reference: /* a reference */
948 kind = r_kind;
949 break;
950
951 case tcc_expression: /* an expression */
952 case tcc_comparison: /* a comparison expression */
953 case tcc_unary: /* a unary arithmetic expression */
954 case tcc_binary: /* a binary arithmetic expression */
955 kind = e_kind;
956 break;
957
958 case tcc_constant: /* a constant */
959 kind = c_kind;
960 break;
961
962 case tcc_exceptional: /* something random, like an identifier. */
963 switch (code)
964 {
965 case IDENTIFIER_NODE:
966 kind = id_kind;
967 break;
968
969 case TREE_VEC:
970 kind = vec_kind;
971 break;
972
973 case TREE_BINFO:
974 kind = binfo_kind;
975 break;
976
977 case SSA_NAME:
978 kind = ssa_name_kind;
979 break;
980
981 case BLOCK:
982 kind = b_kind;
983 break;
984
985 case CONSTRUCTOR:
986 kind = constr_kind;
987 break;
988
989 case OMP_CLAUSE:
990 kind = omp_clause_kind;
991 break;
992
993 default:
994 kind = x_kind;
995 break;
996 }
997 break;
998
999 case tcc_vl_exp:
1000 kind = e_kind;
1001 break;
1002
1003 default:
1004 gcc_unreachable ();
1005 }
1006
1007 tree_code_counts[(int) code]++;
1008 tree_node_counts[(int) kind]++;
1009 tree_node_sizes[(int) kind] += length;
1010}
1011
1012/* Allocate and return a new UID from the DECL_UID namespace. */
1013
1014int
1015allocate_decl_uid (void)
1016{
1017 return next_decl_uid++;
1018}
1019
1020/* Return a newly allocated node of code CODE. For decl and type
1021 nodes, some other fields are initialized. The rest of the node is
1022 initialized to zero. This function cannot be used for TREE_VEC,
1023 INTEGER_CST or OMP_CLAUSE nodes, which is enforced by asserts in
1024 tree_code_size.
1025
1026 Achoo! I got a code in the node. */
1027
1028tree
1029make_node (enum tree_code code MEM_STAT_DECL)
1030{
1031 tree t;
1032 enum tree_code_class type = TREE_CODE_CLASS (code);
1033 size_t length = tree_code_size (code);
1034
1035 record_node_allocation_statistics (code, length);
1036
1037 t = ggc_alloc_cleared_tree_node_stat (length PASS_MEM_STAT);
1038 TREE_SET_CODE (t, code);
1039
1040 switch (type)
1041 {
1042 case tcc_statement:
1043 if (code != DEBUG_BEGIN_STMT)
1044 TREE_SIDE_EFFECTS (t) = 1;
1045 break;
1046
1047 case tcc_declaration:
1048 if (CODE_CONTAINS_STRUCT (code, TS_DECL_COMMON))
1049 {
1050 if (code == FUNCTION_DECL)
1051 {
1052 SET_DECL_ALIGN (t, FUNCTION_ALIGNMENT (FUNCTION_BOUNDARY));
1053 SET_DECL_MODE (t, FUNCTION_MODE);
1054 }
1055 else
1056 SET_DECL_ALIGN (t, 1);
1057 }
1058 DECL_SOURCE_LOCATION (t) = input_location;
1059 if (TREE_CODE (t) == DEBUG_EXPR_DECL)
1060 DECL_UID (t) = --next_debug_decl_uid;
1061 else
1062 {
1063 DECL_UID (t) = allocate_decl_uid ();
1064 SET_DECL_PT_UID (t, -1);
1065 }
1066 if (TREE_CODE (t) == LABEL_DECL)
1067 LABEL_DECL_UID (t) = -1;
1068
1069 break;
1070
1071 case tcc_type:
1072 TYPE_UID (t) = next_type_uid++;
1073 SET_TYPE_ALIGN (t, BITS_PER_UNIT);
1074 TYPE_USER_ALIGN (t) = 0;
1075 TYPE_MAIN_VARIANT (t) = t;
1076 TYPE_CANONICAL (t) = t;
1077
1078 /* Default to no attributes for type, but let target change that. */
1079 TYPE_ATTRIBUTES (t) = NULL_TREE;
1080 targetm.set_default_type_attributes (t);
1081
1082 /* We have not yet computed the alias set for this type. */
1083 TYPE_ALIAS_SET (t) = -1;
1084 break;
1085
1086 case tcc_constant:
1087 TREE_CONSTANT (t) = 1;
1088 break;
1089
1090 case tcc_expression:
1091 switch (code)
1092 {
1093 case INIT_EXPR:
1094 case MODIFY_EXPR:
1095 case VA_ARG_EXPR:
1096 case PREDECREMENT_EXPR:
1097 case PREINCREMENT_EXPR:
1098 case POSTDECREMENT_EXPR:
1099 case POSTINCREMENT_EXPR:
1100 /* All of these have side-effects, no matter what their
1101 operands are. */
1102 TREE_SIDE_EFFECTS (t) = 1;
1103 break;
1104
1105 default:
1106 break;
1107 }
1108 break;
1109
1110 case tcc_exceptional:
1111 switch (code)
1112 {
1113 case TARGET_OPTION_NODE:
1114 TREE_TARGET_OPTION(t)
1115 = ggc_cleared_alloc<struct cl_target_option> ();
1116 break;
1117
1118 case OPTIMIZATION_NODE:
1119 TREE_OPTIMIZATION (t)
1120 = ggc_cleared_alloc<struct cl_optimization> ();
1121 break;
1122
1123 default:
1124 break;
1125 }
1126 break;
1127
1128 default:
1129 /* Other classes need no special treatment. */
1130 break;
1131 }
1132
1133 return t;
1134}
1135
1136/* Free tree node. */
1137
1138void
1139free_node (tree node)
1140{
1141 enum tree_code code = TREE_CODE (node);
1142 if (GATHER_STATISTICS)
1143 {
1144 tree_code_counts[(int) TREE_CODE (node)]--;
1145 tree_node_counts[(int) t_kind]--;
1146 tree_node_sizes[(int) t_kind] -= tree_size (node);
1147 }
1148 if (CODE_CONTAINS_STRUCT (code, TS_CONSTRUCTOR))
1149 vec_free (CONSTRUCTOR_ELTS (node));
1150 else if (code == BLOCK)
1151 vec_free (BLOCK_NONLOCALIZED_VARS (node));
1152 else if (code == TREE_BINFO)
1153 vec_free (BINFO_BASE_ACCESSES (node));
1154 ggc_free (node);
1155}
1156
1157/* Return a new node with the same contents as NODE except that its
1158 TREE_CHAIN, if it has one, is zero and it has a fresh uid. */
1159
1160tree
1161copy_node (tree node MEM_STAT_DECL)
1162{
1163 tree t;
1164 enum tree_code code = TREE_CODE (node);
1165 size_t length;
1166
1167 gcc_assert (code != STATEMENT_LIST);
1168
1169 length = tree_size (node);
1170 record_node_allocation_statistics (code, length);
1171 t = ggc_alloc_tree_node_stat (length PASS_MEM_STAT);
1172 memcpy (t, node, length);
1173
1174 if (CODE_CONTAINS_STRUCT (code, TS_COMMON))
1175 TREE_CHAIN (t) = 0;
1176 TREE_ASM_WRITTEN (t) = 0;
1177 TREE_VISITED (t) = 0;
1178
1179 if (TREE_CODE_CLASS (code) == tcc_declaration)
1180 {
1181 if (code == DEBUG_EXPR_DECL)
1182 DECL_UID (t) = --next_debug_decl_uid;
1183 else
1184 {
1185 DECL_UID (t) = allocate_decl_uid ();
1186 if (DECL_PT_UID_SET_P (node))
1187 SET_DECL_PT_UID (t, DECL_PT_UID (node));
1188 }
1189 if ((TREE_CODE (node) == PARM_DECL || VAR_P (node))
1190 && DECL_HAS_VALUE_EXPR_P (node))
1191 {
1192 SET_DECL_VALUE_EXPR (t, DECL_VALUE_EXPR (node));
1193 DECL_HAS_VALUE_EXPR_P (t) = 1;
1194 }
1195 /* DECL_DEBUG_EXPR is copied explicitely by callers. */
1196 if (VAR_P (node))
1197 {
1198 DECL_HAS_DEBUG_EXPR_P (t) = 0;
1199 t->decl_with_vis.symtab_node = NULL;
1200 }
1201 if (VAR_P (node) && DECL_HAS_INIT_PRIORITY_P (node))
1202 {
1203 SET_DECL_INIT_PRIORITY (t, DECL_INIT_PRIORITY (node));
1204 DECL_HAS_INIT_PRIORITY_P (t) = 1;
1205 }
1206 if (TREE_CODE (node) == FUNCTION_DECL)
1207 {
1208 DECL_STRUCT_FUNCTION (t) = NULL;
1209 t->decl_with_vis.symtab_node = NULL;
1210 }
1211 }
1212 else if (TREE_CODE_CLASS (code) == tcc_type)
1213 {
1214 TYPE_UID (t) = next_type_uid++;
1215 /* The following is so that the debug code for
1216 the copy is different from the original type.
1217 The two statements usually duplicate each other
1218 (because they clear fields of the same union),
1219 but the optimizer should catch that. */
1220 TYPE_SYMTAB_ADDRESS (t) = 0;
1221 TYPE_SYMTAB_DIE (t) = 0;
1222
1223 /* Do not copy the values cache. */
1224 if (TYPE_CACHED_VALUES_P (t))
1225 {
1226 TYPE_CACHED_VALUES_P (t) = 0;
1227 TYPE_CACHED_VALUES (t) = NULL_TREE;
1228 }
1229 }
1230 else if (code == TARGET_OPTION_NODE)
1231 {
1232 TREE_TARGET_OPTION (t) = ggc_alloc<struct cl_target_option>();
1233 memcpy (TREE_TARGET_OPTION (t), TREE_TARGET_OPTION (node),
1234 sizeof (struct cl_target_option));
1235 }
1236 else if (code == OPTIMIZATION_NODE)
1237 {
1238 TREE_OPTIMIZATION (t) = ggc_alloc<struct cl_optimization>();
1239 memcpy (TREE_OPTIMIZATION (t), TREE_OPTIMIZATION (node),
1240 sizeof (struct cl_optimization));
1241 }
1242
1243 return t;
1244}
1245
1246/* Return a copy of a chain of nodes, chained through the TREE_CHAIN field.
1247 For example, this can copy a list made of TREE_LIST nodes. */
1248
1249tree
1250copy_list (tree list)
1251{
1252 tree head;
1253 tree prev, next;
1254
1255 if (list == 0)
1256 return 0;
1257
1258 head = prev = copy_node (list);
1259 next = TREE_CHAIN (list);
1260 while (next)
1261 {
1262 TREE_CHAIN (prev) = copy_node (next);
1263 prev = TREE_CHAIN (prev);
1264 next = TREE_CHAIN (next);
1265 }
1266 return head;
1267}
1268
1269
1270/* Return the value that TREE_INT_CST_EXT_NUNITS should have for an
1271 INTEGER_CST with value CST and type TYPE. */
1272
1273static unsigned int
1274get_int_cst_ext_nunits (tree type, const wide_int &cst)
1275{
1276 gcc_checking_assert (cst.get_precision () == TYPE_PRECISION (type));
1277 /* We need extra HWIs if CST is an unsigned integer with its
1278 upper bit set. */
1279 if (TYPE_UNSIGNED (type) && wi::neg_p (cst))
1280 return cst.get_precision () / HOST_BITS_PER_WIDE_INT + 1;
1281 return cst.get_len ();
1282}
1283
1284/* Return a new INTEGER_CST with value CST and type TYPE. */
1285
1286static tree
1287build_new_int_cst (tree type, const wide_int &cst)
1288{
1289 unsigned int len = cst.get_len ();
1290 unsigned int ext_len = get_int_cst_ext_nunits (type, cst);
1291 tree nt = make_int_cst (len, ext_len);
1292
1293 if (len < ext_len)
1294 {
1295 --ext_len;
1296 TREE_INT_CST_ELT (nt, ext_len)
1297 = zext_hwi (-1, cst.get_precision () % HOST_BITS_PER_WIDE_INT);
1298 for (unsigned int i = len; i < ext_len; ++i)
1299 TREE_INT_CST_ELT (nt, i) = -1;
1300 }
1301 else if (TYPE_UNSIGNED (type)
1302 && cst.get_precision () < len * HOST_BITS_PER_WIDE_INT)
1303 {
1304 len--;
1305 TREE_INT_CST_ELT (nt, len)
1306 = zext_hwi (cst.elt (len),
1307 cst.get_precision () % HOST_BITS_PER_WIDE_INT);
1308 }
1309
1310 for (unsigned int i = 0; i < len; i++)
1311 TREE_INT_CST_ELT (nt, i) = cst.elt (i);
1312 TREE_TYPE (nt) = type;
1313 return nt;
1314}
1315
1316/* Create an INT_CST node with a LOW value sign extended to TYPE. */
1317
1318tree
1319build_int_cst (tree type, HOST_WIDE_INT low)
1320{
1321 /* Support legacy code. */
1322 if (!type)
1323 type = integer_type_node;
1324
1325 return wide_int_to_tree (type, wi::shwi (low, TYPE_PRECISION (type)));
1326}
1327
1328tree
1329build_int_cstu (tree type, unsigned HOST_WIDE_INT cst)
1330{
1331 return wide_int_to_tree (type, wi::uhwi (cst, TYPE_PRECISION (type)));
1332}
1333
1334/* Create an INT_CST node with a LOW value sign extended to TYPE. */
1335
1336tree
1337build_int_cst_type (tree type, HOST_WIDE_INT low)
1338{
1339 gcc_assert (type);
1340 return wide_int_to_tree (type, wi::shwi (low, TYPE_PRECISION (type)));
1341}
1342
1343/* Constructs tree in type TYPE from with value given by CST. Signedness
1344 of CST is assumed to be the same as the signedness of TYPE. */
1345
1346tree
1347double_int_to_tree (tree type, double_int cst)
1348{
1349 return wide_int_to_tree (type, widest_int::from (cst, TYPE_SIGN (type)));
1350}
1351
1352/* We force the wide_int CST to the range of the type TYPE by sign or
1353 zero extending it. OVERFLOWABLE indicates if we are interested in
1354 overflow of the value, when >0 we are only interested in signed
1355 overflow, for <0 we are interested in any overflow. OVERFLOWED
1356 indicates whether overflow has already occurred. CONST_OVERFLOWED
1357 indicates whether constant overflow has already occurred. We force
1358 T's value to be within range of T's type (by setting to 0 or 1 all
1359 the bits outside the type's range). We set TREE_OVERFLOWED if,
1360 OVERFLOWED is nonzero,
1361 or OVERFLOWABLE is >0 and signed overflow occurs
1362 or OVERFLOWABLE is <0 and any overflow occurs
1363 We return a new tree node for the extended wide_int. The node
1364 is shared if no overflow flags are set. */
1365
1366
1367tree
1368force_fit_type (tree type, const wide_int_ref &cst,
1369 int overflowable, bool overflowed)
1370{
1371 signop sign = TYPE_SIGN (type);
1372
1373 /* If we need to set overflow flags, return a new unshared node. */
1374 if (overflowed || !wi::fits_to_tree_p (cst, type))
1375 {
1376 if (overflowed
1377 || overflowable < 0
1378 || (overflowable > 0 && sign == SIGNED))
1379 {
1380 wide_int tmp = wide_int::from (cst, TYPE_PRECISION (type), sign);
1381 tree t = build_new_int_cst (type, tmp);
1382 TREE_OVERFLOW (t) = 1;
1383 return t;
1384 }
1385 }
1386
1387 /* Else build a shared node. */
1388 return wide_int_to_tree (type, cst);
1389}
1390
1391/* These are the hash table functions for the hash table of INTEGER_CST
1392 nodes of a sizetype. */
1393
1394/* Return the hash code X, an INTEGER_CST. */
1395
1396hashval_t
1397int_cst_hasher::hash (tree x)
1398{
1399 const_tree const t = x;
1400 hashval_t code = TYPE_UID (TREE_TYPE (t));
1401 int i;
1402
1403 for (i = 0; i < TREE_INT_CST_NUNITS (t); i++)
1404 code = iterative_hash_host_wide_int (TREE_INT_CST_ELT(t, i), code);
1405
1406 return code;
1407}
1408
1409/* Return nonzero if the value represented by *X (an INTEGER_CST tree node)
1410 is the same as that given by *Y, which is the same. */
1411
1412bool
1413int_cst_hasher::equal (tree x, tree y)
1414{
1415 const_tree const xt = x;
1416 const_tree const yt = y;
1417
1418 if (TREE_TYPE (xt) != TREE_TYPE (yt)
1419 || TREE_INT_CST_NUNITS (xt) != TREE_INT_CST_NUNITS (yt)
1420 || TREE_INT_CST_EXT_NUNITS (xt) != TREE_INT_CST_EXT_NUNITS (yt))
1421 return false;
1422
1423 for (int i = 0; i < TREE_INT_CST_NUNITS (xt); i++)
1424 if (TREE_INT_CST_ELT (xt, i) != TREE_INT_CST_ELT (yt, i))
1425 return false;
1426
1427 return true;
1428}
1429
1430/* Create an INT_CST node of TYPE and value CST.
1431 The returned node is always shared. For small integers we use a
1432 per-type vector cache, for larger ones we use a single hash table.
1433 The value is extended from its precision according to the sign of
1434 the type to be a multiple of HOST_BITS_PER_WIDE_INT. This defines
1435 the upper bits and ensures that hashing and value equality based
1436 upon the underlying HOST_WIDE_INTs works without masking. */
1437
1438tree
1439wide_int_to_tree (tree type, const wide_int_ref &pcst)
1440{
1441 tree t;
1442 int ix = -1;
1443 int limit = 0;
1444
1445 gcc_assert (type);
1446 unsigned int prec = TYPE_PRECISION (type);
1447 signop sgn = TYPE_SIGN (type);
1448
1449 /* Verify that everything is canonical. */
1450 int l = pcst.get_len ();
1451 if (l > 1)
1452 {
1453 if (pcst.elt (l - 1) == 0)
1454 gcc_checking_assert (pcst.elt (l - 2) < 0);
1455 if (pcst.elt (l - 1) == HOST_WIDE_INT_M1)
1456 gcc_checking_assert (pcst.elt (l - 2) >= 0);
1457 }
1458
1459 wide_int cst = wide_int::from (pcst, prec, sgn);
1460 unsigned int ext_len = get_int_cst_ext_nunits (type, cst);
1461
1462 if (ext_len == 1)
1463 {
1464 /* We just need to store a single HOST_WIDE_INT. */
1465 HOST_WIDE_INT hwi;
1466 if (TYPE_UNSIGNED (type))
1467 hwi = cst.to_uhwi ();
1468 else
1469 hwi = cst.to_shwi ();
1470
1471 switch (TREE_CODE (type))
1472 {
1473 case NULLPTR_TYPE:
1474 gcc_assert (hwi == 0);
1475 /* Fallthru. */
1476
1477 case POINTER_TYPE:
1478 case REFERENCE_TYPE:
1479 case POINTER_BOUNDS_TYPE:
1480 /* Cache NULL pointer and zero bounds. */
1481 if (hwi == 0)
1482 {
1483 limit = 1;
1484 ix = 0;
1485 }
1486 break;
1487
1488 case BOOLEAN_TYPE:
1489 /* Cache false or true. */
1490 limit = 2;
1491 if (IN_RANGE (hwi, 0, 1))
1492 ix = hwi;
1493 break;
1494
1495 case INTEGER_TYPE:
1496 case OFFSET_TYPE:
1497 if (TYPE_SIGN (type) == UNSIGNED)
1498 {
1499 /* Cache [0, N). */
1500 limit = INTEGER_SHARE_LIMIT;
1501 if (IN_RANGE (hwi, 0, INTEGER_SHARE_LIMIT - 1))
1502 ix = hwi;
1503 }
1504 else
1505 {
1506 /* Cache [-1, N). */
1507 limit = INTEGER_SHARE_LIMIT + 1;
1508 if (IN_RANGE (hwi, -1, INTEGER_SHARE_LIMIT - 1))
1509 ix = hwi + 1;
1510 }
1511 break;
1512
1513 case ENUMERAL_TYPE:
1514 break;
1515
1516 default:
1517 gcc_unreachable ();
1518 }
1519
1520 if (ix >= 0)
1521 {
1522 /* Look for it in the type's vector of small shared ints. */
1523 if (!TYPE_CACHED_VALUES_P (type))
1524 {
1525 TYPE_CACHED_VALUES_P (type) = 1;
1526 TYPE_CACHED_VALUES (type) = make_tree_vec (limit);
1527 }
1528
1529 t = TREE_VEC_ELT (TYPE_CACHED_VALUES (type), ix);
1530 if (t)
1531 /* Make sure no one is clobbering the shared constant. */
1532 gcc_checking_assert (TREE_TYPE (t) == type
1533 && TREE_INT_CST_NUNITS (t) == 1
1534 && TREE_INT_CST_OFFSET_NUNITS (t) == 1
1535 && TREE_INT_CST_EXT_NUNITS (t) == 1
1536 && TREE_INT_CST_ELT (t, 0) == hwi);
1537 else
1538 {
1539 /* Create a new shared int. */
1540 t = build_new_int_cst (type, cst);
1541 TREE_VEC_ELT (TYPE_CACHED_VALUES (type), ix) = t;
1542 }
1543 }
1544 else
1545 {
1546 /* Use the cache of larger shared ints, using int_cst_node as
1547 a temporary. */
1548
1549 TREE_INT_CST_ELT (int_cst_node, 0) = hwi;
1550 TREE_TYPE (int_cst_node) = type;
1551
1552 tree *slot = int_cst_hash_table->find_slot (int_cst_node, INSERT);
1553 t = *slot;
1554 if (!t)
1555 {
1556 /* Insert this one into the hash table. */
1557 t = int_cst_node;
1558 *slot = t;
1559 /* Make a new node for next time round. */
1560 int_cst_node = make_int_cst (1, 1);
1561 }
1562 }
1563 }
1564 else
1565 {
1566 /* The value either hashes properly or we drop it on the floor
1567 for the gc to take care of. There will not be enough of them
1568 to worry about. */
1569
1570 tree nt = build_new_int_cst (type, cst);
1571 tree *slot = int_cst_hash_table->find_slot (nt, INSERT);
1572 t = *slot;
1573 if (!t)
1574 {
1575 /* Insert this one into the hash table. */
1576 t = nt;
1577 *slot = t;
1578 }
1579 else
1580 ggc_free (nt);
1581 }
1582
1583 return t;
1584}
1585
1586void
1587cache_integer_cst (tree t)
1588{
1589 tree type = TREE_TYPE (t);
1590 int ix = -1;
1591 int limit = 0;
1592 int prec = TYPE_PRECISION (type);
1593
1594 gcc_assert (!TREE_OVERFLOW (t));
1595
1596 switch (TREE_CODE (type))
1597 {
1598 case NULLPTR_TYPE:
1599 gcc_assert (integer_zerop (t));
1600 /* Fallthru. */
1601
1602 case POINTER_TYPE:
1603 case REFERENCE_TYPE:
1604 /* Cache NULL pointer. */
1605 if (integer_zerop (t))
1606 {
1607 limit = 1;
1608 ix = 0;
1609 }
1610 break;
1611
1612 case BOOLEAN_TYPE:
1613 /* Cache false or true. */
1614 limit = 2;
1615 if (wi::ltu_p (wi::to_wide (t), 2))
1616 ix = TREE_INT_CST_ELT (t, 0);
1617 break;
1618
1619 case INTEGER_TYPE:
1620 case OFFSET_TYPE:
1621 if (TYPE_UNSIGNED (type))
1622 {
1623 /* Cache 0..N */
1624 limit = INTEGER_SHARE_LIMIT;
1625
1626 /* This is a little hokie, but if the prec is smaller than
1627 what is necessary to hold INTEGER_SHARE_LIMIT, then the
1628 obvious test will not get the correct answer. */
1629 if (prec < HOST_BITS_PER_WIDE_INT)
1630 {
1631 if (tree_to_uhwi (t) < (unsigned HOST_WIDE_INT) INTEGER_SHARE_LIMIT)
1632 ix = tree_to_uhwi (t);
1633 }
1634 else if (wi::ltu_p (wi::to_wide (t), INTEGER_SHARE_LIMIT))
1635 ix = tree_to_uhwi (t);
1636 }
1637 else
1638 {
1639 /* Cache -1..N */
1640 limit = INTEGER_SHARE_LIMIT + 1;
1641
1642 if (integer_minus_onep (t))
1643 ix = 0;
1644 else if (!wi::neg_p (wi::to_wide (t)))
1645 {
1646 if (prec < HOST_BITS_PER_WIDE_INT)
1647 {
1648 if (tree_to_shwi (t) < INTEGER_SHARE_LIMIT)
1649 ix = tree_to_shwi (t) + 1;
1650 }
1651 else if (wi::ltu_p (wi::to_wide (t), INTEGER_SHARE_LIMIT))
1652 ix = tree_to_shwi (t) + 1;
1653 }
1654 }
1655 break;
1656
1657 case ENUMERAL_TYPE:
1658 break;
1659
1660 default:
1661 gcc_unreachable ();
1662 }
1663
1664 if (ix >= 0)
1665 {
1666 /* Look for it in the type's vector of small shared ints. */
1667 if (!TYPE_CACHED_VALUES_P (type))
1668 {
1669 TYPE_CACHED_VALUES_P (type) = 1;
1670 TYPE_CACHED_VALUES (type) = make_tree_vec (limit);
1671 }
1672
1673 gcc_assert (TREE_VEC_ELT (TYPE_CACHED_VALUES (type), ix) == NULL_TREE);
1674 TREE_VEC_ELT (TYPE_CACHED_VALUES (type), ix) = t;
1675 }
1676 else
1677 {
1678 /* Use the cache of larger shared ints. */
1679 tree *slot = int_cst_hash_table->find_slot (t, INSERT);
1680 /* If there is already an entry for the number verify it's the
1681 same. */
1682 if (*slot)
1683 gcc_assert (wi::to_wide (tree (*slot)) == wi::to_wide (t));
1684 else
1685 /* Otherwise insert this one into the hash table. */
1686 *slot = t;
1687 }
1688}
1689
1690
1691/* Builds an integer constant in TYPE such that lowest BITS bits are ones
1692 and the rest are zeros. */
1693
1694tree
1695build_low_bits_mask (tree type, unsigned bits)
1696{
1697 gcc_assert (bits <= TYPE_PRECISION (type));
1698
1699 return wide_int_to_tree (type, wi::mask (bits, false,
1700 TYPE_PRECISION (type)));
1701}
1702
1703/* Checks that X is integer constant that can be expressed in (unsigned)
1704 HOST_WIDE_INT without loss of precision. */
1705
1706bool
1707cst_and_fits_in_hwi (const_tree x)
1708{
1709 return (TREE_CODE (x) == INTEGER_CST
1710 && (tree_fits_shwi_p (x) || tree_fits_uhwi_p (x)));
1711}
1712
1713/* Build a newly constructed VECTOR_CST with the given values of
1714 (VECTOR_CST_)LOG2_NPATTERNS and (VECTOR_CST_)NELTS_PER_PATTERN. */
1715
1716tree
1717make_vector (unsigned log2_npatterns,
1718 unsigned int nelts_per_pattern MEM_STAT_DECL)
1719{
1720 gcc_assert (IN_RANGE (nelts_per_pattern, 1, 3));
1721 tree t;
1722 unsigned npatterns = 1 << log2_npatterns;
1723 unsigned encoded_nelts = npatterns * nelts_per_pattern;
1724 unsigned length = (sizeof (struct tree_vector)
1725 + (encoded_nelts - 1) * sizeof (tree));
1726
1727 record_node_allocation_statistics (VECTOR_CST, length);
1728
1729 t = ggc_alloc_cleared_tree_node_stat (length PASS_MEM_STAT);
1730
1731 TREE_SET_CODE (t, VECTOR_CST);
1732 TREE_CONSTANT (t) = 1;
1733 VECTOR_CST_LOG2_NPATTERNS (t) = log2_npatterns;
1734 VECTOR_CST_NELTS_PER_PATTERN (t) = nelts_per_pattern;
1735
1736 return t;
1737}
1738
1739/* Return a new VECTOR_CST node whose type is TYPE and whose values
1740 are extracted from V, a vector of CONSTRUCTOR_ELT. */
1741
1742tree
1743build_vector_from_ctor (tree type, vec<constructor_elt, va_gc> *v)
1744{
1745 unsigned int nelts = TYPE_VECTOR_SUBPARTS (type);
1746 unsigned HOST_WIDE_INT idx;
1747 tree value;
1748
1749 tree_vector_builder vec (type, nelts, 1);
1750 FOR_EACH_CONSTRUCTOR_VALUE (v, idx, value)
1751 {
1752 if (TREE_CODE (value) == VECTOR_CST)
1753 for (unsigned i = 0; i < VECTOR_CST_NELTS (value); ++i)
1754 vec.quick_push (VECTOR_CST_ELT (value, i));
1755 else
1756 vec.quick_push (value);
1757 }
1758 while (vec.length () < nelts)
1759 vec.quick_push (build_zero_cst (TREE_TYPE (type)));
1760
1761 return vec.build ();
1762}
1763
1764/* Build a vector of type VECTYPE where all the elements are SCs. */
1765tree
1766build_vector_from_val (tree vectype, tree sc)
1767{
1768 int i, nunits = TYPE_VECTOR_SUBPARTS (vectype);
1769
1770 if (sc == error_mark_node)
1771 return sc;
1772
1773 /* Verify that the vector type is suitable for SC. Note that there
1774 is some inconsistency in the type-system with respect to restrict
1775 qualifications of pointers. Vector types always have a main-variant
1776 element type and the qualification is applied to the vector-type.
1777 So TREE_TYPE (vector-type) does not return a properly qualified
1778 vector element-type. */
1779 gcc_checking_assert (types_compatible_p (TYPE_MAIN_VARIANT (TREE_TYPE (sc)),
1780 TREE_TYPE (vectype)));
1781
1782 if (CONSTANT_CLASS_P (sc))
1783 {
1784 tree_vector_builder v (vectype, 1, 1);
1785 v.quick_push (sc);
1786 return v.build ();
1787 }
1788 else
1789 {
1790 vec<constructor_elt, va_gc> *v;
1791 vec_alloc (v, nunits);
1792 for (i = 0; i < nunits; ++i)
1793 CONSTRUCTOR_APPEND_ELT (v, NULL_TREE, sc);
1794 return build_constructor (vectype, v);
1795 }
1796}
1797
1798/* Something has messed with the elements of CONSTRUCTOR C after it was built;
1799 calculate TREE_CONSTANT and TREE_SIDE_EFFECTS. */
1800
1801void
1802recompute_constructor_flags (tree c)
1803{
1804 unsigned int i;
1805 tree val;
1806 bool constant_p = true;
1807 bool side_effects_p = false;
1808 vec<constructor_elt, va_gc> *vals = CONSTRUCTOR_ELTS (c);
1809
1810 FOR_EACH_CONSTRUCTOR_VALUE (vals, i, val)
1811 {
1812 /* Mostly ctors will have elts that don't have side-effects, so
1813 the usual case is to scan all the elements. Hence a single
1814 loop for both const and side effects, rather than one loop
1815 each (with early outs). */
1816 if (!TREE_CONSTANT (val))
1817 constant_p = false;
1818 if (TREE_SIDE_EFFECTS (val))
1819 side_effects_p = true;
1820 }
1821
1822 TREE_SIDE_EFFECTS (c) = side_effects_p;
1823 TREE_CONSTANT (c) = constant_p;
1824}
1825
1826/* Make sure that TREE_CONSTANT and TREE_SIDE_EFFECTS are correct for
1827 CONSTRUCTOR C. */
1828
1829void
1830verify_constructor_flags (tree c)
1831{
1832 unsigned int i;
1833 tree val;
1834 bool constant_p = TREE_CONSTANT (c);
1835 bool side_effects_p = TREE_SIDE_EFFECTS (c);
1836 vec<constructor_elt, va_gc> *vals = CONSTRUCTOR_ELTS (c);
1837
1838 FOR_EACH_CONSTRUCTOR_VALUE (vals, i, val)
1839 {
1840 if (constant_p && !TREE_CONSTANT (val))
1841 internal_error ("non-constant element in constant CONSTRUCTOR");
1842 if (!side_effects_p && TREE_SIDE_EFFECTS (val))
1843 internal_error ("side-effects element in no-side-effects CONSTRUCTOR");
1844 }
1845}
1846
1847/* Return a new CONSTRUCTOR node whose type is TYPE and whose values
1848 are in the vec pointed to by VALS. */
1849tree
1850build_constructor (tree type, vec<constructor_elt, va_gc> *vals)
1851{
1852 tree c = make_node (CONSTRUCTOR);
1853
1854 TREE_TYPE (c) = type;
1855 CONSTRUCTOR_ELTS (c) = vals;
1856
1857 recompute_constructor_flags (c);
1858
1859 return c;
1860}
1861
1862/* Build a CONSTRUCTOR node made of a single initializer, with the specified
1863 INDEX and VALUE. */
1864tree
1865build_constructor_single (tree type, tree index, tree value)
1866{
1867 vec<constructor_elt, va_gc> *v;
1868 constructor_elt elt = {index, value};
1869
1870 vec_alloc (v, 1);
1871 v->quick_push (elt);
1872
1873 return build_constructor (type, v);
1874}
1875
1876
1877/* Return a new CONSTRUCTOR node whose type is TYPE and whose values
1878 are in a list pointed to by VALS. */
1879tree
1880build_constructor_from_list (tree type, tree vals)
1881{
1882 tree t;
1883 vec<constructor_elt, va_gc> *v = NULL;
1884
1885 if (vals)
1886 {
1887 vec_alloc (v, list_length (vals));
1888 for (t = vals; t; t = TREE_CHAIN (t))
1889 CONSTRUCTOR_APPEND_ELT (v, TREE_PURPOSE (t), TREE_VALUE (t));
1890 }
1891
1892 return build_constructor (type, v);
1893}
1894
1895/* Return a new CONSTRUCTOR node whose type is TYPE. NELTS is the number
1896 of elements, provided as index/value pairs. */
1897
1898tree
1899build_constructor_va (tree type, int nelts, ...)
1900{
1901 vec<constructor_elt, va_gc> *v = NULL;
1902 va_list p;
1903
1904 va_start (p, nelts);
1905 vec_alloc (v, nelts);
1906 while (nelts--)
1907 {
1908 tree index = va_arg (p, tree);
1909 tree value = va_arg (p, tree);
1910 CONSTRUCTOR_APPEND_ELT (v, index, value);
1911 }
1912 va_end (p);
1913 return build_constructor (type, v);
1914}
1915
1916/* Return a new FIXED_CST node whose type is TYPE and value is F. */
1917
1918tree
1919build_fixed (tree type, FIXED_VALUE_TYPE f)
1920{
1921 tree v;
1922 FIXED_VALUE_TYPE *fp;
1923
1924 v = make_node (FIXED_CST);
1925 fp = ggc_alloc<fixed_value> ();
1926 memcpy (fp, &f, sizeof (FIXED_VALUE_TYPE));
1927
1928 TREE_TYPE (v) = type;
1929 TREE_FIXED_CST_PTR (v) = fp;
1930 return v;
1931}
1932
1933/* Return a new REAL_CST node whose type is TYPE and value is D. */
1934
1935tree
1936build_real (tree type, REAL_VALUE_TYPE d)
1937{
1938 tree v;
1939 REAL_VALUE_TYPE *dp;
1940 int overflow = 0;
1941
1942 /* ??? Used to check for overflow here via CHECK_FLOAT_TYPE.
1943 Consider doing it via real_convert now. */
1944
1945 v = make_node (REAL_CST);
1946 dp = ggc_alloc<real_value> ();
1947 memcpy (dp, &d, sizeof (REAL_VALUE_TYPE));
1948
1949 TREE_TYPE (v) = type;
1950 TREE_REAL_CST_PTR (v) = dp;
1951 TREE_OVERFLOW (v) = overflow;
1952 return v;
1953}
1954
1955/* Like build_real, but first truncate D to the type. */
1956
1957tree
1958build_real_truncate (tree type, REAL_VALUE_TYPE d)
1959{
1960 return build_real (type, real_value_truncate (TYPE_MODE (type), d));
1961}
1962
1963/* Return a new REAL_CST node whose type is TYPE
1964 and whose value is the integer value of the INTEGER_CST node I. */
1965
1966REAL_VALUE_TYPE
1967real_value_from_int_cst (const_tree type, const_tree i)
1968{
1969 REAL_VALUE_TYPE d;
1970
1971 /* Clear all bits of the real value type so that we can later do
1972 bitwise comparisons to see if two values are the same. */
1973 memset (&d, 0, sizeof d);
1974
1975 real_from_integer (&d, type ? TYPE_MODE (type) : VOIDmode, wi::to_wide (i),
1976 TYPE_SIGN (TREE_TYPE (i)));
1977 return d;
1978}
1979
1980/* Given a tree representing an integer constant I, return a tree
1981 representing the same value as a floating-point constant of type TYPE. */
1982
1983tree
1984build_real_from_int_cst (tree type, const_tree i)
1985{
1986 tree v;
1987 int overflow = TREE_OVERFLOW (i);
1988
1989 v = build_real (type, real_value_from_int_cst (type, i));
1990
1991 TREE_OVERFLOW (v) |= overflow;
1992 return v;
1993}
1994
1995/* Return a newly constructed STRING_CST node whose value is
1996 the LEN characters at STR.
1997 Note that for a C string literal, LEN should include the trailing NUL.
1998 The TREE_TYPE is not initialized. */
1999
2000tree
2001build_string (int len, const char *str)
2002{
2003 tree s;
2004 size_t length;
2005
2006 /* Do not waste bytes provided by padding of struct tree_string. */
2007 length = len + offsetof (struct tree_string, str) + 1;
2008
2009 record_node_allocation_statistics (STRING_CST, length);
2010
2011 s = (tree) ggc_internal_alloc (length);
2012
2013 memset (s, 0, sizeof (struct tree_typed));
2014 TREE_SET_CODE (s, STRING_CST);
2015 TREE_CONSTANT (s) = 1;
2016 TREE_STRING_LENGTH (s) = len;
2017 memcpy (s->string.str, str, len);
2018 s->string.str[len] = '\0';
2019
2020 return s;
2021}
2022
2023/* Return a newly constructed COMPLEX_CST node whose value is
2024 specified by the real and imaginary parts REAL and IMAG.
2025 Both REAL and IMAG should be constant nodes. TYPE, if specified,
2026 will be the type of the COMPLEX_CST; otherwise a new type will be made. */
2027
2028tree
2029build_complex (tree type, tree real, tree imag)
2030{
2031 tree t = make_node (COMPLEX_CST);
2032
2033 TREE_REALPART (t) = real;
2034 TREE_IMAGPART (t) = imag;
2035 TREE_TYPE (t) = type ? type : build_complex_type (TREE_TYPE (real));
2036 TREE_OVERFLOW (t) = TREE_OVERFLOW (real) | TREE_OVERFLOW (imag);
2037 return t;
2038}
2039
2040/* Build a complex (inf +- 0i), such as for the result of cproj.
2041 TYPE is the complex tree type of the result. If NEG is true, the
2042 imaginary zero is negative. */
2043
2044tree
2045build_complex_inf (tree type, bool neg)
2046{
2047 REAL_VALUE_TYPE rinf, rzero = dconst0;
2048
2049 real_inf (&rinf);
2050 rzero.sign = neg;
2051 return build_complex (type, build_real (TREE_TYPE (type), rinf),
2052 build_real (TREE_TYPE (type), rzero));
2053}
2054
2055/* Return the constant 1 in type TYPE. If TYPE has several elements, each
2056 element is set to 1. In particular, this is 1 + i for complex types. */
2057
2058tree
2059build_each_one_cst (tree type)
2060{
2061 if (TREE_CODE (type) == COMPLEX_TYPE)
2062 {
2063 tree scalar = build_one_cst (TREE_TYPE (type));
2064 return build_complex (type, scalar, scalar);
2065 }
2066 else
2067 return build_one_cst (type);
2068}
2069
2070/* Return a constant of arithmetic type TYPE which is the
2071 multiplicative identity of the set TYPE. */
2072
2073tree
2074build_one_cst (tree type)
2075{
2076 switch (TREE_CODE (type))
2077 {
2078 case INTEGER_TYPE: case ENUMERAL_TYPE: case BOOLEAN_TYPE:
2079 case POINTER_TYPE: case REFERENCE_TYPE:
2080 case OFFSET_TYPE:
2081 return build_int_cst (type, 1);
2082
2083 case REAL_TYPE:
2084 return build_real (type, dconst1);
2085
2086 case FIXED_POINT_TYPE:
2087 /* We can only generate 1 for accum types. */
2088 gcc_assert (ALL_SCALAR_ACCUM_MODE_P (TYPE_MODE (type)));
2089 return build_fixed (type, FCONST1 (TYPE_MODE (type)));
2090
2091 case VECTOR_TYPE:
2092 {
2093 tree scalar = build_one_cst (TREE_TYPE (type));
2094
2095 return build_vector_from_val (type, scalar);
2096 }
2097
2098 case COMPLEX_TYPE:
2099 return build_complex (type,
2100 build_one_cst (TREE_TYPE (type)),
2101 build_zero_cst (TREE_TYPE (type)));
2102
2103 default:
2104 gcc_unreachable ();
2105 }
2106}
2107
2108/* Return an integer of type TYPE containing all 1's in as much precision as
2109 it contains, or a complex or vector whose subparts are such integers. */
2110
2111tree
2112build_all_ones_cst (tree type)
2113{
2114 if (TREE_CODE (type) == COMPLEX_TYPE)
2115 {
2116 tree scalar = build_all_ones_cst (TREE_TYPE (type));
2117 return build_complex (type, scalar, scalar);
2118 }
2119 else
2120 return build_minus_one_cst (type);
2121}
2122
2123/* Return a constant of arithmetic type TYPE which is the
2124 opposite of the multiplicative identity of the set TYPE. */
2125
2126tree
2127build_minus_one_cst (tree type)
2128{
2129 switch (TREE_CODE (type))
2130 {
2131 case INTEGER_TYPE: case ENUMERAL_TYPE: case BOOLEAN_TYPE:
2132 case POINTER_TYPE: case REFERENCE_TYPE:
2133 case OFFSET_TYPE:
2134 return build_int_cst (type, -1);
2135
2136 case REAL_TYPE:
2137 return build_real (type, dconstm1);
2138
2139 case FIXED_POINT_TYPE:
2140 /* We can only generate 1 for accum types. */
2141 gcc_assert (ALL_SCALAR_ACCUM_MODE_P (TYPE_MODE (type)));
2142 return build_fixed (type,
2143 fixed_from_double_int (double_int_minus_one,
2144 SCALAR_TYPE_MODE (type)));
2145
2146 case VECTOR_TYPE:
2147 {
2148 tree scalar = build_minus_one_cst (TREE_TYPE (type));
2149
2150 return build_vector_from_val (type, scalar);
2151 }
2152
2153 case COMPLEX_TYPE:
2154 return build_complex (type,
2155 build_minus_one_cst (TREE_TYPE (type)),
2156 build_zero_cst (TREE_TYPE (type)));
2157
2158 default:
2159 gcc_unreachable ();
2160 }
2161}
2162
2163/* Build 0 constant of type TYPE. This is used by constructor folding
2164 and thus the constant should be represented in memory by
2165 zero(es). */
2166
2167tree
2168build_zero_cst (tree type)
2169{
2170 switch (TREE_CODE (type))
2171 {
2172 case INTEGER_TYPE: case ENUMERAL_TYPE: case BOOLEAN_TYPE:
2173 case POINTER_TYPE: case REFERENCE_TYPE:
2174 case OFFSET_TYPE: case NULLPTR_TYPE:
2175 return build_int_cst (type, 0);
2176
2177 case REAL_TYPE:
2178 return build_real (type, dconst0);
2179
2180 case FIXED_POINT_TYPE:
2181 return build_fixed (type, FCONST0 (TYPE_MODE (type)));
2182
2183 case VECTOR_TYPE:
2184 {
2185 tree scalar = build_zero_cst (TREE_TYPE (type));
2186
2187 return build_vector_from_val (type, scalar);
2188 }
2189
2190 case COMPLEX_TYPE:
2191 {
2192 tree zero = build_zero_cst (TREE_TYPE (type));
2193
2194 return build_complex (type, zero, zero);
2195 }
2196
2197 default:
2198 if (!AGGREGATE_TYPE_P (type))
2199 return fold_convert (type, integer_zero_node);
2200 return build_constructor (type, NULL);
2201 }
2202}
2203
2204
2205/* Build a BINFO with LEN language slots. */
2206
2207tree
2208make_tree_binfo (unsigned base_binfos MEM_STAT_DECL)
2209{
2210 tree t;
2211 size_t length = (offsetof (struct tree_binfo, base_binfos)
2212 + vec<tree, va_gc>::embedded_size (base_binfos));
2213
2214 record_node_allocation_statistics (TREE_BINFO, length);
2215
2216 t = ggc_alloc_tree_node_stat (length PASS_MEM_STAT);
2217
2218 memset (t, 0, offsetof (struct tree_binfo, base_binfos));
2219
2220 TREE_SET_CODE (t, TREE_BINFO);
2221
2222 BINFO_BASE_BINFOS (t)->embedded_init (base_binfos);
2223
2224 return t;
2225}
2226
2227/* Create a CASE_LABEL_EXPR tree node and return it. */
2228
2229tree
2230build_case_label (tree low_value, tree high_value, tree label_decl)
2231{
2232 tree t = make_node (CASE_LABEL_EXPR);
2233
2234 TREE_TYPE (t) = void_type_node;
2235 SET_EXPR_LOCATION (t, DECL_SOURCE_LOCATION (label_decl));
2236
2237 CASE_LOW (t) = low_value;
2238 CASE_HIGH (t) = high_value;
2239 CASE_LABEL (t) = label_decl;
2240 CASE_CHAIN (t) = NULL_TREE;
2241
2242 return t;
2243}
2244
2245/* Build a newly constructed INTEGER_CST node. LEN and EXT_LEN are the
2246 values of TREE_INT_CST_NUNITS and TREE_INT_CST_EXT_NUNITS respectively.
2247 The latter determines the length of the HOST_WIDE_INT vector. */
2248
2249tree
2250make_int_cst (int len, int ext_len MEM_STAT_DECL)
2251{
2252 tree t;
2253 int length = ((ext_len - 1) * sizeof (HOST_WIDE_INT)
2254 + sizeof (struct tree_int_cst));
2255
2256 gcc_assert (len);
2257 record_node_allocation_statistics (INTEGER_CST, length);
2258
2259 t = ggc_alloc_cleared_tree_node_stat (length PASS_MEM_STAT);
2260
2261 TREE_SET_CODE (t, INTEGER_CST);
2262 TREE_INT_CST_NUNITS (t) = len;
2263 TREE_INT_CST_EXT_NUNITS (t) = ext_len;
2264 /* to_offset can only be applied to trees that are offset_int-sized
2265 or smaller. EXT_LEN is correct if it fits, otherwise the constant
2266 must be exactly the precision of offset_int and so LEN is correct. */
2267 if (ext_len <= OFFSET_INT_ELTS)
2268 TREE_INT_CST_OFFSET_NUNITS (t) = ext_len;
2269 else
2270 TREE_INT_CST_OFFSET_NUNITS (t) = len;
2271
2272 TREE_CONSTANT (t) = 1;
2273
2274 return t;
2275}
2276
2277/* Build a newly constructed TREE_VEC node of length LEN. */
2278
2279tree
2280make_tree_vec (int len MEM_STAT_DECL)
2281{
2282 tree t;
2283 size_t length = (len - 1) * sizeof (tree) + sizeof (struct tree_vec);
2284
2285 record_node_allocation_statistics (TREE_VEC, length);
2286
2287 t = ggc_alloc_cleared_tree_node_stat (length PASS_MEM_STAT);
2288
2289 TREE_SET_CODE (t, TREE_VEC);
2290 TREE_VEC_LENGTH (t) = len;
2291
2292 return t;
2293}
2294
2295/* Grow a TREE_VEC node to new length LEN. */
2296
2297tree
2298grow_tree_vec (tree v, int len MEM_STAT_DECL)
2299{
2300 gcc_assert (TREE_CODE (v) == TREE_VEC);
2301
2302 int oldlen = TREE_VEC_LENGTH (v);
2303 gcc_assert (len > oldlen);
2304
2305 size_t oldlength = (oldlen - 1) * sizeof (tree) + sizeof (struct tree_vec);
2306 size_t length = (len - 1) * sizeof (tree) + sizeof (struct tree_vec);
2307
2308 record_node_allocation_statistics (TREE_VEC, length - oldlength);
2309
2310 v = (tree) ggc_realloc (v, length PASS_MEM_STAT);
2311
2312 TREE_VEC_LENGTH (v) = len;
2313
2314 return v;
2315}
2316
2317/* Return 1 if EXPR is the constant zero, whether it is integral, float or
2318 fixed, and scalar, complex or vector. */
2319
2320int
2321zerop (const_tree expr)
2322{
2323 return (integer_zerop (expr)
2324 || real_zerop (expr)
2325 || fixed_zerop (expr));
2326}
2327
2328/* Return 1 if EXPR is the integer constant zero or a complex constant
2329 of zero. */
2330
2331int
2332integer_zerop (const_tree expr)
2333{
2334 switch (TREE_CODE (expr))
2335 {
2336 case INTEGER_CST:
2337 return wi::to_wide (expr) == 0;
2338 case COMPLEX_CST:
2339 return (integer_zerop (TREE_REALPART (expr))
2340 && integer_zerop (TREE_IMAGPART (expr)));
2341 case VECTOR_CST:
2342 return (VECTOR_CST_NPATTERNS (expr) == 1
2343 && VECTOR_CST_DUPLICATE_P (expr)
2344 && integer_zerop (VECTOR_CST_ENCODED_ELT (expr, 0)));
2345 default:
2346 return false;
2347 }
2348}
2349
2350/* Return 1 if EXPR is the integer constant one or the corresponding
2351 complex constant. */
2352
2353int
2354integer_onep (const_tree expr)
2355{
2356 switch (TREE_CODE (expr))
2357 {
2358 case INTEGER_CST:
2359 return wi::eq_p (wi::to_widest (expr), 1);
2360 case COMPLEX_CST:
2361 return (integer_onep (TREE_REALPART (expr))
2362 && integer_zerop (TREE_IMAGPART (expr)));
2363 case VECTOR_CST:
2364 return (VECTOR_CST_NPATTERNS (expr) == 1
2365 && VECTOR_CST_DUPLICATE_P (expr)
2366 && integer_onep (VECTOR_CST_ENCODED_ELT (expr, 0)));
2367 default:
2368 return false;
2369 }
2370}
2371
2372/* Return 1 if EXPR is the integer constant one. For complex and vector,
2373 return 1 if every piece is the integer constant one. */
2374
2375int
2376integer_each_onep (const_tree expr)
2377{
2378 if (TREE_CODE (expr) == COMPLEX_CST)
2379 return (integer_onep (TREE_REALPART (expr))
2380 && integer_onep (TREE_IMAGPART (expr)));
2381 else
2382 return integer_onep (expr);
2383}
2384
2385/* Return 1 if EXPR is an integer containing all 1's in as much precision as
2386 it contains, or a complex or vector whose subparts are such integers. */
2387
2388int
2389integer_all_onesp (const_tree expr)
2390{
2391 if (TREE_CODE (expr) == COMPLEX_CST
2392 && integer_all_onesp (TREE_REALPART (expr))
2393 && integer_all_onesp (TREE_IMAGPART (expr)))
2394 return 1;
2395
2396 else if (TREE_CODE (expr) == VECTOR_CST)
2397 return (VECTOR_CST_NPATTERNS (expr) == 1
2398 && VECTOR_CST_DUPLICATE_P (expr)
2399 && integer_all_onesp (VECTOR_CST_ENCODED_ELT (expr, 0)));
2400
2401 else if (TREE_CODE (expr) != INTEGER_CST)
2402 return 0;
2403
2404 return (wi::max_value (TYPE_PRECISION (TREE_TYPE (expr)), UNSIGNED)
2405 == wi::to_wide (expr));
2406}
2407
2408/* Return 1 if EXPR is the integer constant minus one. */
2409
2410int
2411integer_minus_onep (const_tree expr)
2412{
2413 if (TREE_CODE (expr) == COMPLEX_CST)
2414 return (integer_all_onesp (TREE_REALPART (expr))
2415 && integer_zerop (TREE_IMAGPART (expr)));
2416 else
2417 return integer_all_onesp (expr);
2418}
2419
2420/* Return 1 if EXPR is an integer constant that is a power of 2 (i.e., has only
2421 one bit on). */
2422
2423int
2424integer_pow2p (const_tree expr)
2425{
2426 if (TREE_CODE (expr) == COMPLEX_CST
2427 && integer_pow2p (TREE_REALPART (expr))
2428 && integer_zerop (TREE_IMAGPART (expr)))
2429 return 1;
2430
2431 if (TREE_CODE (expr) != INTEGER_CST)
2432 return 0;
2433
2434 return wi::popcount (wi::to_wide (expr)) == 1;
2435}
2436
2437/* Return 1 if EXPR is an integer constant other than zero or a
2438 complex constant other than zero. */
2439
2440int
2441integer_nonzerop (const_tree expr)
2442{
2443 return ((TREE_CODE (expr) == INTEGER_CST
2444 && wi::to_wide (expr) != 0)
2445 || (TREE_CODE (expr) == COMPLEX_CST
2446 && (integer_nonzerop (TREE_REALPART (expr))
2447 || integer_nonzerop (TREE_IMAGPART (expr)))));
2448}
2449
2450/* Return 1 if EXPR is the integer constant one. For vector,
2451 return 1 if every piece is the integer constant minus one
2452 (representing the value TRUE). */
2453
2454int
2455integer_truep (const_tree expr)
2456{
2457 if (TREE_CODE (expr) == VECTOR_CST)
2458 return integer_all_onesp (expr);
2459 return integer_onep (expr);
2460}
2461
2462/* Return 1 if EXPR is the fixed-point constant zero. */
2463
2464int
2465fixed_zerop (const_tree expr)
2466{
2467 return (TREE_CODE (expr) == FIXED_CST
2468 && TREE_FIXED_CST (expr).data.is_zero ());
2469}
2470
2471/* Return the power of two represented by a tree node known to be a
2472 power of two. */
2473
2474int
2475tree_log2 (const_tree expr)
2476{
2477 if (TREE_CODE (expr) == COMPLEX_CST)
2478 return tree_log2 (TREE_REALPART (expr));
2479
2480 return wi::exact_log2 (wi::to_wide (expr));
2481}
2482
2483/* Similar, but return the largest integer Y such that 2 ** Y is less
2484 than or equal to EXPR. */
2485
2486int
2487tree_floor_log2 (const_tree expr)
2488{
2489 if (TREE_CODE (expr) == COMPLEX_CST)
2490 return tree_log2 (TREE_REALPART (expr));
2491
2492 return wi::floor_log2 (wi::to_wide (expr));
2493}
2494
2495/* Return number of known trailing zero bits in EXPR, or, if the value of
2496 EXPR is known to be zero, the precision of it's type. */
2497
2498unsigned int
2499tree_ctz (const_tree expr)
2500{
2501 if (!INTEGRAL_TYPE_P (TREE_TYPE (expr))
2502 && !POINTER_TYPE_P (TREE_TYPE (expr)))
2503 return 0;
2504
2505 unsigned int ret1, ret2, prec = TYPE_PRECISION (TREE_TYPE (expr));
2506 switch (TREE_CODE (expr))
2507 {
2508 case INTEGER_CST:
2509 ret1 = wi::ctz (wi::to_wide (expr));
2510 return MIN (ret1, prec);
2511 case SSA_NAME:
2512 ret1 = wi::ctz (get_nonzero_bits (expr));
2513 return MIN (ret1, prec);
2514 case PLUS_EXPR:
2515 case MINUS_EXPR:
2516 case BIT_IOR_EXPR:
2517 case BIT_XOR_EXPR:
2518 case MIN_EXPR:
2519 case MAX_EXPR:
2520 ret1 = tree_ctz (TREE_OPERAND (expr, 0));
2521 if (ret1 == 0)
2522 return ret1;
2523 ret2 = tree_ctz (TREE_OPERAND (expr, 1));
2524 return MIN (ret1, ret2);
2525 case POINTER_PLUS_EXPR:
2526 ret1 = tree_ctz (TREE_OPERAND (expr, 0));
2527 ret2 = tree_ctz (TREE_OPERAND (expr, 1));
2528 /* Second operand is sizetype, which could be in theory
2529 wider than pointer's precision. Make sure we never
2530 return more than prec. */
2531 ret2 = MIN (ret2, prec);
2532 return MIN (ret1, ret2);
2533 case BIT_AND_EXPR:
2534 ret1 = tree_ctz (TREE_OPERAND (expr, 0));
2535 ret2 = tree_ctz (TREE_OPERAND (expr, 1));
2536 return MAX (ret1, ret2);
2537 case MULT_EXPR:
2538 ret1 = tree_ctz (TREE_OPERAND (expr, 0));
2539 ret2 = tree_ctz (TREE_OPERAND (expr, 1));
2540 return MIN (ret1 + ret2, prec);
2541 case LSHIFT_EXPR:
2542 ret1 = tree_ctz (TREE_OPERAND (expr, 0));
2543 if (tree_fits_uhwi_p (TREE_OPERAND (expr, 1))
2544 && (tree_to_uhwi (TREE_OPERAND (expr, 1)) < prec))
2545 {
2546 ret2 = tree_to_uhwi (TREE_OPERAND (expr, 1));
2547 return MIN (ret1 + ret2, prec);
2548 }
2549 return ret1;
2550 case RSHIFT_EXPR:
2551 if (tree_fits_uhwi_p (TREE_OPERAND (expr, 1))
2552 && (tree_to_uhwi (TREE_OPERAND (expr, 1)) < prec))
2553 {
2554 ret1 = tree_ctz (TREE_OPERAND (expr, 0));
2555 ret2 = tree_to_uhwi (TREE_OPERAND (expr, 1));
2556 if (ret1 > ret2)
2557 return ret1 - ret2;
2558 }
2559 return 0;
2560 case TRUNC_DIV_EXPR:
2561 case CEIL_DIV_EXPR:
2562 case FLOOR_DIV_EXPR:
2563 case ROUND_DIV_EXPR:
2564 case EXACT_DIV_EXPR:
2565 if (TREE_CODE (TREE_OPERAND (expr, 1)) == INTEGER_CST
2566 && tree_int_cst_sgn (TREE_OPERAND (expr, 1)) == 1)
2567 {
2568 int l = tree_log2 (TREE_OPERAND (expr, 1));
2569 if (l >= 0)
2570 {
2571 ret1 = tree_ctz (TREE_OPERAND (expr, 0));
2572 ret2 = l;
2573 if (ret1 > ret2)
2574 return ret1 - ret2;
2575 }
2576 }
2577 return 0;
2578 CASE_CONVERT:
2579 ret1 = tree_ctz (TREE_OPERAND (expr, 0));
2580 if (ret1 && ret1 == TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (expr, 0))))
2581 ret1 = prec;
2582 return MIN (ret1, prec);
2583 case SAVE_EXPR:
2584 return tree_ctz (TREE_OPERAND (expr, 0));
2585 case COND_EXPR:
2586 ret1 = tree_ctz (TREE_OPERAND (expr, 1));
2587 if (ret1 == 0)
2588 return 0;
2589 ret2 = tree_ctz (TREE_OPERAND (expr, 2));
2590 return MIN (ret1, ret2);
2591 case COMPOUND_EXPR:
2592 return tree_ctz (TREE_OPERAND (expr, 1));
2593 case ADDR_EXPR:
2594 ret1 = get_pointer_alignment (CONST_CAST_TREE (expr));
2595 if (ret1 > BITS_PER_UNIT)
2596 {
2597 ret1 = ctz_hwi (ret1 / BITS_PER_UNIT);
2598 return MIN (ret1, prec);
2599 }
2600 return 0;
2601 default:
2602 return 0;
2603 }
2604}
2605
2606/* Return 1 if EXPR is the real constant zero. Trailing zeroes matter for
2607 decimal float constants, so don't return 1 for them. */
2608
2609int
2610real_zerop (const_tree expr)
2611{
2612 switch (TREE_CODE (expr))
2613 {
2614 case REAL_CST:
2615 return real_equal (&TREE_REAL_CST (expr), &dconst0)
2616 && !(DECIMAL_FLOAT_MODE_P (TYPE_MODE (TREE_TYPE (expr))));
2617 case COMPLEX_CST:
2618 return real_zerop (TREE_REALPART (expr))
2619 && real_zerop (TREE_IMAGPART (expr));
2620 case VECTOR_CST:
2621 {
2622 /* Don't simply check for a duplicate because the predicate
2623 accepts both +0.0 and -0.0. */
2624 unsigned count = vector_cst_encoded_nelts (expr);
2625 for (unsigned int i = 0; i < count; ++i)
2626 if (!real_zerop (VECTOR_CST_ENCODED_ELT (expr, i)))
2627 return false;
2628 return true;
2629 }
2630 default:
2631 return false;
2632 }
2633}
2634
2635/* Return 1 if EXPR is the real constant one in real or complex form.
2636 Trailing zeroes matter for decimal float constants, so don't return
2637 1 for them. */
2638
2639int
2640real_onep (const_tree expr)
2641{
2642 switch (TREE_CODE (expr))
2643 {
2644 case REAL_CST:
2645 return real_equal (&TREE_REAL_CST (expr), &dconst1)
2646 && !(DECIMAL_FLOAT_MODE_P (TYPE_MODE (TREE_TYPE (expr))));
2647 case COMPLEX_CST:
2648 return real_onep (TREE_REALPART (expr))
2649 && real_zerop (TREE_IMAGPART (expr));
2650 case VECTOR_CST:
2651 return (VECTOR_CST_NPATTERNS (expr) == 1
2652 && VECTOR_CST_DUPLICATE_P (expr)
2653 && real_onep (VECTOR_CST_ENCODED_ELT (expr, 0)));
2654 default:
2655 return false;
2656 }
2657}
2658
2659/* Return 1 if EXPR is the real constant minus one. Trailing zeroes
2660 matter for decimal float constants, so don't return 1 for them. */
2661
2662int
2663real_minus_onep (const_tree expr)
2664{
2665 switch (TREE_CODE (expr))
2666 {
2667 case REAL_CST:
2668 return real_equal (&TREE_REAL_CST (expr), &dconstm1)
2669 && !(DECIMAL_FLOAT_MODE_P (TYPE_MODE (TREE_TYPE (expr))));
2670 case COMPLEX_CST:
2671 return real_minus_onep (TREE_REALPART (expr))
2672 && real_zerop (TREE_IMAGPART (expr));
2673 case VECTOR_CST:
2674 return (VECTOR_CST_NPATTERNS (expr) == 1
2675 && VECTOR_CST_DUPLICATE_P (expr)
2676 && real_minus_onep (VECTOR_CST_ENCODED_ELT (expr, 0)));
2677 default:
2678 return false;
2679 }
2680}
2681
2682/* Nonzero if EXP is a constant or a cast of a constant. */
2683
2684int
2685really_constant_p (const_tree exp)
2686{
2687 /* This is not quite the same as STRIP_NOPS. It does more. */
2688 while (CONVERT_EXPR_P (exp)
2689 || TREE_CODE (exp) == NON_LVALUE_EXPR)
2690 exp = TREE_OPERAND (exp, 0);
2691 return TREE_CONSTANT (exp);
2692}
2693
2694/* Return first list element whose TREE_VALUE is ELEM.
2695 Return 0 if ELEM is not in LIST. */
2696
2697tree
2698value_member (tree elem, tree list)
2699{
2700 while (list)
2701 {
2702 if (elem == TREE_VALUE (list))
2703 return list;
2704 list = TREE_CHAIN (list);
2705 }
2706 return NULL_TREE;
2707}
2708
2709/* Return first list element whose TREE_PURPOSE is ELEM.
2710 Return 0 if ELEM is not in LIST. */
2711
2712tree
2713purpose_member (const_tree elem, tree list)
2714{
2715 while (list)
2716 {
2717 if (elem == TREE_PURPOSE (list))
2718 return list;
2719 list = TREE_CHAIN (list);
2720 }
2721 return NULL_TREE;
2722}
2723
2724/* Return true if ELEM is in V. */
2725
2726bool
2727vec_member (const_tree elem, vec<tree, va_gc> *v)
2728{
2729 unsigned ix;
2730 tree t;
2731 FOR_EACH_VEC_SAFE_ELT (v, ix, t)
2732 if (elem == t)
2733 return true;
2734 return false;
2735}
2736
2737/* Returns element number IDX (zero-origin) of chain CHAIN, or
2738 NULL_TREE. */
2739
2740tree
2741chain_index (int idx, tree chain)
2742{
2743 for (; chain && idx > 0; --idx)
2744 chain = TREE_CHAIN (chain);
2745 return chain;
2746}
2747
2748/* Return nonzero if ELEM is part of the chain CHAIN. */
2749
2750int
2751chain_member (const_tree elem, const_tree chain)
2752{
2753 while (chain)
2754 {
2755 if (elem == chain)
2756 return 1;
2757 chain = DECL_CHAIN (chain);
2758 }
2759
2760 return 0;
2761}
2762
2763/* Return the length of a chain of nodes chained through TREE_CHAIN.
2764 We expect a null pointer to mark the end of the chain.
2765 This is the Lisp primitive `length'. */
2766
2767int
2768list_length (const_tree t)
2769{
2770 const_tree p = t;
2771#ifdef ENABLE_TREE_CHECKING
2772 const_tree q = t;
2773#endif
2774 int len = 0;
2775
2776 while (p)
2777 {
2778 p = TREE_CHAIN (p);
2779#ifdef ENABLE_TREE_CHECKING
2780 if (len % 2)
2781 q = TREE_CHAIN (q);
2782 gcc_assert (p != q);
2783#endif
2784 len++;
2785 }
2786
2787 return len;
2788}
2789
2790/* Returns the first FIELD_DECL in the TYPE_FIELDS of the RECORD_TYPE or
2791 UNION_TYPE TYPE, or NULL_TREE if none. */
2792
2793tree
2794first_field (const_tree type)
2795{
2796 tree t = TYPE_FIELDS (type);
2797 while (t && TREE_CODE (t) != FIELD_DECL)
2798 t = TREE_CHAIN (t);
2799 return t;
2800}
2801
2802/* Concatenate two chains of nodes (chained through TREE_CHAIN)
2803 by modifying the last node in chain 1 to point to chain 2.
2804 This is the Lisp primitive `nconc'. */
2805
2806tree
2807chainon (tree op1, tree op2)
2808{
2809 tree t1;
2810
2811 if (!op1)
2812 return op2;
2813 if (!op2)
2814 return op1;
2815
2816 for (t1 = op1; TREE_CHAIN (t1); t1 = TREE_CHAIN (t1))
2817 continue;
2818 TREE_CHAIN (t1) = op2;
2819
2820#ifdef ENABLE_TREE_CHECKING
2821 {
2822 tree t2;
2823 for (t2 = op2; t2; t2 = TREE_CHAIN (t2))
2824 gcc_assert (t2 != t1);
2825 }
2826#endif
2827
2828 return op1;
2829}
2830
2831/* Return the last node in a chain of nodes (chained through TREE_CHAIN). */
2832
2833tree
2834tree_last (tree chain)
2835{
2836 tree next;
2837 if (chain)
2838 while ((next = TREE_CHAIN (chain)))
2839 chain = next;
2840 return chain;
2841}
2842
2843/* Reverse the order of elements in the chain T,
2844 and return the new head of the chain (old last element). */
2845
2846tree
2847nreverse (tree t)
2848{
2849 tree prev = 0, decl, next;
2850 for (decl = t; decl; decl = next)
2851 {
2852 /* We shouldn't be using this function to reverse BLOCK chains; we
2853 have blocks_nreverse for that. */
2854 gcc_checking_assert (TREE_CODE (decl) != BLOCK);
2855 next = TREE_CHAIN (decl);
2856 TREE_CHAIN (decl) = prev;
2857 prev = decl;
2858 }
2859 return prev;
2860}
2861
2862/* Return a newly created TREE_LIST node whose
2863 purpose and value fields are PARM and VALUE. */
2864
2865tree
2866build_tree_list (tree parm, tree value MEM_STAT_DECL)
2867{
2868 tree t = make_node (TREE_LIST PASS_MEM_STAT);
2869 TREE_PURPOSE (t) = parm;
2870 TREE_VALUE (t) = value;
2871 return t;
2872}
2873
2874/* Build a chain of TREE_LIST nodes from a vector. */
2875
2876tree
2877build_tree_list_vec (const vec<tree, va_gc> *vec MEM_STAT_DECL)
2878{
2879 tree ret = NULL_TREE;
2880 tree *pp = &ret;
2881 unsigned int i;
2882 tree t;
2883 FOR_EACH_VEC_SAFE_ELT (vec, i, t)
2884 {
2885 *pp = build_tree_list (NULL, t PASS_MEM_STAT);
2886 pp = &TREE_CHAIN (*pp);
2887 }
2888 return ret;
2889}
2890
2891/* Return a newly created TREE_LIST node whose
2892 purpose and value fields are PURPOSE and VALUE
2893 and whose TREE_CHAIN is CHAIN. */
2894
2895tree
2896tree_cons (tree purpose, tree value, tree chain MEM_STAT_DECL)
2897{
2898 tree node;
2899
2900 node = ggc_alloc_tree_node_stat (sizeof (struct tree_list) PASS_MEM_STAT);
2901 memset (node, 0, sizeof (struct tree_common));
2902
2903 record_node_allocation_statistics (TREE_LIST, sizeof (struct tree_list));
2904
2905 TREE_SET_CODE (node, TREE_LIST);
2906 TREE_CHAIN (node) = chain;
2907 TREE_PURPOSE (node) = purpose;
2908 TREE_VALUE (node) = value;
2909 return node;
2910}
2911
2912/* Return the values of the elements of a CONSTRUCTOR as a vector of
2913 trees. */
2914
2915vec<tree, va_gc> *
2916ctor_to_vec (tree ctor)
2917{
2918 vec<tree, va_gc> *vec;
2919 vec_alloc (vec, CONSTRUCTOR_NELTS (ctor));
2920 unsigned int ix;
2921 tree val;
2922
2923 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (ctor), ix, val)
2924 vec->quick_push (val);
2925
2926 return vec;
2927}
2928
2929/* Return the size nominally occupied by an object of type TYPE
2930 when it resides in memory. The value is measured in units of bytes,
2931 and its data type is that normally used for type sizes
2932 (which is the first type created by make_signed_type or
2933 make_unsigned_type). */
2934
2935tree
2936size_in_bytes_loc (location_t loc, const_tree type)
2937{
2938 tree t;
2939
2940 if (type == error_mark_node)
2941 return integer_zero_node;
2942
2943 type = TYPE_MAIN_VARIANT (type);
2944 t = TYPE_SIZE_UNIT (type);
2945
2946 if (t == 0)
2947 {
2948 lang_hooks.types.incomplete_type_error (loc, NULL_TREE, type);
2949 return size_zero_node;
2950 }
2951
2952 return t;
2953}
2954
2955/* Return the size of TYPE (in bytes) as a wide integer
2956 or return -1 if the size can vary or is larger than an integer. */
2957
2958HOST_WIDE_INT
2959int_size_in_bytes (const_tree type)
2960{
2961 tree t;
2962
2963 if (type == error_mark_node)
2964 return 0;
2965
2966 type = TYPE_MAIN_VARIANT (type);
2967 t = TYPE_SIZE_UNIT (type);
2968
2969 if (t && tree_fits_uhwi_p (t))
2970 return TREE_INT_CST_LOW (t);
2971 else
2972 return -1;
2973}
2974
2975/* Return the maximum size of TYPE (in bytes) as a wide integer
2976 or return -1 if the size can vary or is larger than an integer. */
2977
2978HOST_WIDE_INT
2979max_int_size_in_bytes (const_tree type)
2980{
2981 HOST_WIDE_INT size = -1;
2982 tree size_tree;
2983
2984 /* If this is an array type, check for a possible MAX_SIZE attached. */
2985
2986 if (TREE_CODE (type) == ARRAY_TYPE)
2987 {
2988 size_tree = TYPE_ARRAY_MAX_SIZE (type);
2989
2990 if (size_tree && tree_fits_uhwi_p (size_tree))
2991 size = tree_to_uhwi (size_tree);
2992 }
2993
2994 /* If we still haven't been able to get a size, see if the language
2995 can compute a maximum size. */
2996
2997 if (size == -1)
2998 {
2999 size_tree = lang_hooks.types.max_size (type);
3000
3001 if (size_tree && tree_fits_uhwi_p (size_tree))
3002 size = tree_to_uhwi (size_tree);
3003 }
3004
3005 return size;
3006}
3007
3008/* Return the bit position of FIELD, in bits from the start of the record.
3009 This is a tree of type bitsizetype. */
3010
3011tree
3012bit_position (const_tree field)
3013{
3014 return bit_from_pos (DECL_FIELD_OFFSET (field),
3015 DECL_FIELD_BIT_OFFSET (field));
3016}
3017
3018/* Return the byte position of FIELD, in bytes from the start of the record.
3019 This is a tree of type sizetype. */
3020
3021tree
3022byte_position (const_tree field)
3023{
3024 return byte_from_pos (DECL_FIELD_OFFSET (field),
3025 DECL_FIELD_BIT_OFFSET (field));
3026}
3027
3028/* Likewise, but return as an integer. It must be representable in
3029 that way (since it could be a signed value, we don't have the
3030 option of returning -1 like int_size_in_byte can. */
3031
3032HOST_WIDE_INT
3033int_byte_position (const_tree field)
3034{
3035 return tree_to_shwi (byte_position (field));
3036}
3037
3038/* Return the strictest alignment, in bits, that T is known to have. */
3039
3040unsigned int
3041expr_align (const_tree t)
3042{
3043 unsigned int align0, align1;
3044
3045 switch (TREE_CODE (t))
3046 {
3047 CASE_CONVERT: case NON_LVALUE_EXPR:
3048 /* If we have conversions, we know that the alignment of the
3049 object must meet each of the alignments of the types. */
3050 align0 = expr_align (TREE_OPERAND (t, 0));
3051 align1 = TYPE_ALIGN (TREE_TYPE (t));
3052 return MAX (align0, align1);
3053
3054 case SAVE_EXPR: case COMPOUND_EXPR: case MODIFY_EXPR:
3055 case INIT_EXPR: case TARGET_EXPR: case WITH_CLEANUP_EXPR:
3056 case CLEANUP_POINT_EXPR:
3057 /* These don't change the alignment of an object. */
3058 return expr_align (TREE_OPERAND (t, 0));
3059
3060 case COND_EXPR:
3061 /* The best we can do is say that the alignment is the least aligned
3062 of the two arms. */
3063 align0 = expr_align (TREE_OPERAND (t, 1));
3064 align1 = expr_align (TREE_OPERAND (t, 2));
3065 return MIN (align0, align1);
3066
3067 /* FIXME: LABEL_DECL and CONST_DECL never have DECL_ALIGN set
3068 meaningfully, it's always 1. */
3069 case LABEL_DECL: case CONST_DECL:
3070 case VAR_DECL: case PARM_DECL: case RESULT_DECL:
3071 case FUNCTION_DECL:
3072 gcc_assert (DECL_ALIGN (t) != 0);
3073 return DECL_ALIGN (t);
3074
3075 default:
3076 break;
3077 }
3078
3079 /* Otherwise take the alignment from that of the type. */
3080 return TYPE_ALIGN (TREE_TYPE (t));
3081}
3082
3083/* Return, as a tree node, the number of elements for TYPE (which is an
3084 ARRAY_TYPE) minus one. This counts only elements of the top array. */
3085
3086tree
3087array_type_nelts (const_tree type)
3088{
3089 tree index_type, min, max;
3090
3091 /* If they did it with unspecified bounds, then we should have already
3092 given an error about it before we got here. */
3093 if (! TYPE_DOMAIN (type))
3094 return error_mark_node;
3095
3096 index_type = TYPE_DOMAIN (type);
3097 min = TYPE_MIN_VALUE (index_type);
3098 max = TYPE_MAX_VALUE (index_type);
3099
3100 /* TYPE_MAX_VALUE may not be set if the array has unknown length. */
3101 if (!max)
3102 return error_mark_node;
3103
3104 return (integer_zerop (min)
3105 ? max
3106 : fold_build2 (MINUS_EXPR, TREE_TYPE (max), max, min));
3107}
3108
3109/* If arg is static -- a reference to an object in static storage -- then
3110 return the object. This is not the same as the C meaning of `static'.
3111 If arg isn't static, return NULL. */
3112
3113tree
3114staticp (tree arg)
3115{
3116 switch (TREE_CODE (arg))
3117 {
3118 case FUNCTION_DECL:
3119 /* Nested functions are static, even though taking their address will
3120 involve a trampoline as we unnest the nested function and create
3121 the trampoline on the tree level. */
3122 return arg;
3123
3124 case VAR_DECL:
3125 return ((TREE_STATIC (arg) || DECL_EXTERNAL (arg))
3126 && ! DECL_THREAD_LOCAL_P (arg)
3127 && ! DECL_DLLIMPORT_P (arg)
3128 ? arg : NULL);
3129
3130 case CONST_DECL:
3131 return ((TREE_STATIC (arg) || DECL_EXTERNAL (arg))
3132 ? arg : NULL);
3133
3134 case CONSTRUCTOR:
3135 return TREE_STATIC (arg) ? arg : NULL;
3136
3137 case LABEL_DECL:
3138 case STRING_CST:
3139 return arg;
3140
3141 case COMPONENT_REF:
3142 /* If the thing being referenced is not a field, then it is
3143 something language specific. */
3144 gcc_assert (TREE_CODE (TREE_OPERAND (arg, 1)) == FIELD_DECL);
3145
3146 /* If we are referencing a bitfield, we can't evaluate an
3147 ADDR_EXPR at compile time and so it isn't a constant. */
3148 if (DECL_BIT_FIELD (TREE_OPERAND (arg, 1)))
3149 return NULL;
3150
3151 return staticp (TREE_OPERAND (arg, 0));
3152
3153 case BIT_FIELD_REF:
3154 return NULL;
3155
3156 case INDIRECT_REF:
3157 return TREE_CONSTANT (TREE_OPERAND (arg, 0)) ? arg : NULL;
3158
3159 case ARRAY_REF:
3160 case ARRAY_RANGE_REF:
3161 if (TREE_CODE (TYPE_SIZE (TREE_TYPE (arg))) == INTEGER_CST
3162 && TREE_CODE (TREE_OPERAND (arg, 1)) == INTEGER_CST)
3163 return staticp (TREE_OPERAND (arg, 0));
3164 else
3165 return NULL;
3166
3167 case COMPOUND_LITERAL_EXPR:
3168 return TREE_STATIC (COMPOUND_LITERAL_EXPR_DECL (arg)) ? arg : NULL;
3169
3170 default:
3171 return NULL;
3172 }
3173}
3174
3175
3176
3177
3178/* Return whether OP is a DECL whose address is function-invariant. */
3179
3180bool
3181decl_address_invariant_p (const_tree op)
3182{
3183 /* The conditions below are slightly less strict than the one in
3184 staticp. */
3185
3186 switch (TREE_CODE (op))
3187 {
3188 case PARM_DECL:
3189 case RESULT_DECL:
3190 case LABEL_DECL:
3191 case FUNCTION_DECL:
3192 return true;
3193
3194 case VAR_DECL:
3195 if ((TREE_STATIC (op) || DECL_EXTERNAL (op))
3196 || DECL_THREAD_LOCAL_P (op)
3197 || DECL_CONTEXT (op) == current_function_decl
3198 || decl_function_context (op) == current_function_decl)
3199 return true;
3200 break;
3201
3202 case CONST_DECL:
3203 if ((TREE_STATIC (op) || DECL_EXTERNAL (op))
3204 || decl_function_context (op) == current_function_decl)
3205 return true;
3206 break;
3207
3208 default:
3209 break;
3210 }
3211
3212 return false;
3213}
3214
3215/* Return whether OP is a DECL whose address is interprocedural-invariant. */
3216
3217bool
3218decl_address_ip_invariant_p (const_tree op)
3219{
3220 /* The conditions below are slightly less strict than the one in
3221 staticp. */
3222
3223 switch (TREE_CODE (op))
3224 {
3225 case LABEL_DECL:
3226 case FUNCTION_DECL:
3227 case STRING_CST:
3228 return true;
3229
3230 case VAR_DECL:
3231 if (((TREE_STATIC (op) || DECL_EXTERNAL (op))
3232 && !DECL_DLLIMPORT_P (op))
3233 || DECL_THREAD_LOCAL_P (op))
3234 return true;
3235 break;
3236
3237 case CONST_DECL:
3238 if ((TREE_STATIC (op) || DECL_EXTERNAL (op)))
3239 return true;
3240 break;
3241
3242 default:
3243 break;
3244 }
3245
3246 return false;
3247}
3248
3249
3250/* Return true if T is function-invariant (internal function, does
3251 not handle arithmetic; that's handled in skip_simple_arithmetic and
3252 tree_invariant_p). */
3253
3254static bool
3255tree_invariant_p_1 (tree t)
3256{
3257 tree op;
3258
3259 if (TREE_CONSTANT (t)
3260 || (TREE_READONLY (t) && !TREE_SIDE_EFFECTS (t)))
3261 return true;
3262
3263 switch (TREE_CODE (t))
3264 {
3265 case SAVE_EXPR:
3266 return true;
3267
3268 case ADDR_EXPR:
3269 op = TREE_OPERAND (t, 0);
3270 while (handled_component_p (op))
3271 {
3272 switch (TREE_CODE (op))
3273 {
3274 case ARRAY_REF:
3275 case ARRAY_RANGE_REF:
3276 if (!tree_invariant_p (TREE_OPERAND (op, 1))
3277 || TREE_OPERAND (op, 2) != NULL_TREE
3278 || TREE_OPERAND (op, 3) != NULL_TREE)
3279 return false;
3280 break;
3281
3282 case COMPONENT_REF:
3283 if (TREE_OPERAND (op, 2) != NULL_TREE)
3284 return false;
3285 break;
3286
3287 default:;
3288 }
3289 op = TREE_OPERAND (op, 0);
3290 }
3291
3292 return CONSTANT_CLASS_P (op) || decl_address_invariant_p (op);
3293
3294 default:
3295 break;
3296 }
3297
3298 return false;
3299}
3300
3301/* Return true if T is function-invariant. */
3302
3303bool
3304tree_invariant_p (tree t)
3305{
3306 tree inner = skip_simple_arithmetic (t);
3307 return tree_invariant_p_1 (inner);
3308}
3309
3310/* Wrap a SAVE_EXPR around EXPR, if appropriate.
3311 Do this to any expression which may be used in more than one place,
3312 but must be evaluated only once.
3313
3314 Normally, expand_expr would reevaluate the expression each time.
3315 Calling save_expr produces something that is evaluated and recorded
3316 the first time expand_expr is called on it. Subsequent calls to
3317 expand_expr just reuse the recorded value.
3318
3319 The call to expand_expr that generates code that actually computes
3320 the value is the first call *at compile time*. Subsequent calls
3321 *at compile time* generate code to use the saved value.
3322 This produces correct result provided that *at run time* control
3323 always flows through the insns made by the first expand_expr
3324 before reaching the other places where the save_expr was evaluated.
3325 You, the caller of save_expr, must make sure this is so.
3326
3327 Constants, and certain read-only nodes, are returned with no
3328 SAVE_EXPR because that is safe. Expressions containing placeholders
3329 are not touched; see tree.def for an explanation of what these
3330 are used for. */
3331
3332tree
3333save_expr (tree expr)
3334{
3335 tree inner;
3336
3337 /* If the tree evaluates to a constant, then we don't want to hide that
3338 fact (i.e. this allows further folding, and direct checks for constants).
3339 However, a read-only object that has side effects cannot be bypassed.
3340 Since it is no problem to reevaluate literals, we just return the
3341 literal node. */
3342 inner = skip_simple_arithmetic (expr);
3343 if (TREE_CODE (inner) == ERROR_MARK)
3344 return inner;
3345
3346 if (tree_invariant_p_1 (inner))
3347 return expr;
3348
3349 /* If INNER contains a PLACEHOLDER_EXPR, we must evaluate it each time, since
3350 it means that the size or offset of some field of an object depends on
3351 the value within another field.
3352
3353 Note that it must not be the case that EXPR contains both a PLACEHOLDER_EXPR
3354 and some variable since it would then need to be both evaluated once and
3355 evaluated more than once. Front-ends must assure this case cannot
3356 happen by surrounding any such subexpressions in their own SAVE_EXPR
3357 and forcing evaluation at the proper time. */
3358 if (contains_placeholder_p (inner))
3359 return expr;
3360
3361 expr = build1_loc (EXPR_LOCATION (expr), SAVE_EXPR, TREE_TYPE (expr), expr);
3362
3363 /* This expression might be placed ahead of a jump to ensure that the
3364 value was computed on both sides of the jump. So make sure it isn't
3365 eliminated as dead. */
3366 TREE_SIDE_EFFECTS (expr) = 1;
3367 return expr;
3368}
3369
3370/* Look inside EXPR into any simple arithmetic operations. Return the
3371 outermost non-arithmetic or non-invariant node. */
3372
3373tree
3374skip_simple_arithmetic (tree expr)
3375{
3376 /* We don't care about whether this can be used as an lvalue in this
3377 context. */
3378 while (TREE_CODE (expr) == NON_LVALUE_EXPR)
3379 expr = TREE_OPERAND (expr, 0);
3380
3381 /* If we have simple operations applied to a SAVE_EXPR or to a SAVE_EXPR and
3382 a constant, it will be more efficient to not make another SAVE_EXPR since
3383 it will allow better simplification and GCSE will be able to merge the
3384 computations if they actually occur. */
3385 while (true)
3386 {
3387 if (UNARY_CLASS_P (expr))
3388 expr = TREE_OPERAND (expr, 0);
3389 else if (BINARY_CLASS_P (expr))
3390 {
3391 if (tree_invariant_p (TREE_OPERAND (expr, 1)))
3392 expr = TREE_OPERAND (expr, 0);
3393 else if (tree_invariant_p (TREE_OPERAND (expr, 0)))
3394 expr = TREE_OPERAND (expr, 1);
3395 else
3396 break;
3397 }
3398 else
3399 break;
3400 }
3401
3402 return expr;
3403}
3404
3405/* Look inside EXPR into simple arithmetic operations involving constants.
3406 Return the outermost non-arithmetic or non-constant node. */
3407
3408tree
3409skip_simple_constant_arithmetic (tree expr)
3410{
3411 while (TREE_CODE (expr) == NON_LVALUE_EXPR)
3412 expr = TREE_OPERAND (expr, 0);
3413
3414 while (true)
3415 {
3416 if (UNARY_CLASS_P (expr))
3417 expr = TREE_OPERAND (expr, 0);
3418 else if (BINARY_CLASS_P (expr))
3419 {
3420 if (TREE_CONSTANT (TREE_OPERAND (expr, 1)))
3421 expr = TREE_OPERAND (expr, 0);
3422 else if (TREE_CONSTANT (TREE_OPERAND (expr, 0)))
3423 expr = TREE_OPERAND (expr, 1);
3424 else
3425 break;
3426 }
3427 else
3428 break;
3429 }
3430
3431 return expr;
3432}
3433
3434/* Return which tree structure is used by T. */
3435
3436enum tree_node_structure_enum
3437tree_node_structure (const_tree t)
3438{
3439 const enum tree_code code = TREE_CODE (t);
3440 return tree_node_structure_for_code (code);
3441}
3442
3443/* Set various status flags when building a CALL_EXPR object T. */
3444
3445static void
3446process_call_operands (tree t)
3447{
3448 bool side_effects = TREE_SIDE_EFFECTS (t);
3449 bool read_only = false;
3450 int i = call_expr_flags (t);
3451
3452 /* Calls have side-effects, except those to const or pure functions. */
3453 if ((i & ECF_LOOPING_CONST_OR_PURE) || !(i & (ECF_CONST | ECF_PURE)))
3454 side_effects = true;
3455 /* Propagate TREE_READONLY of arguments for const functions. */
3456 if (i & ECF_CONST)
3457 read_only = true;
3458
3459 if (!side_effects || read_only)
3460 for (i = 1; i < TREE_OPERAND_LENGTH (t); i++)
3461 {
3462 tree op = TREE_OPERAND (t, i);
3463 if (op && TREE_SIDE_EFFECTS (op))
3464 side_effects = true;
3465 if (op && !TREE_READONLY (op) && !CONSTANT_CLASS_P (op))
3466 read_only = false;
3467 }
3468
3469 TREE_SIDE_EFFECTS (t) = side_effects;
3470 TREE_READONLY (t) = read_only;
3471}
3472
3473/* Return true if EXP contains a PLACEHOLDER_EXPR, i.e. if it represents a
3474 size or offset that depends on a field within a record. */
3475
3476bool
3477contains_placeholder_p (const_tree exp)
3478{
3479 enum tree_code code;
3480
3481 if (!exp)
3482 return 0;
3483
3484 code = TREE_CODE (exp);
3485 if (code == PLACEHOLDER_EXPR)
3486 return 1;
3487
3488 switch (TREE_CODE_CLASS (code))
3489 {
3490 case tcc_reference:
3491 /* Don't look at any PLACEHOLDER_EXPRs that might be in index or bit
3492 position computations since they will be converted into a
3493 WITH_RECORD_EXPR involving the reference, which will assume
3494 here will be valid. */
3495 return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0));
3496
3497 case tcc_exceptional:
3498 if (code == TREE_LIST)
3499 return (CONTAINS_PLACEHOLDER_P (TREE_VALUE (exp))
3500 || CONTAINS_PLACEHOLDER_P (TREE_CHAIN (exp)));
3501 break;
3502
3503 case tcc_unary:
3504 case tcc_binary:
3505 case tcc_comparison:
3506 case tcc_expression:
3507 switch (code)
3508 {
3509 case COMPOUND_EXPR:
3510 /* Ignoring the first operand isn't quite right, but works best. */
3511 return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1));
3512
3513 case COND_EXPR:
3514 return (CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0))
3515 || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1))
3516 || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 2)));
3517
3518 case SAVE_EXPR:
3519 /* The save_expr function never wraps anything containing
3520 a PLACEHOLDER_EXPR. */
3521 return 0;
3522
3523 default:
3524 break;
3525 }
3526
3527 switch (TREE_CODE_LENGTH (code))
3528 {
3529 case 1:
3530 return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0));
3531 case 2:
3532 return (CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0))
3533 || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1)));
3534 default:
3535 return 0;
3536 }
3537
3538 case tcc_vl_exp:
3539 switch (code)
3540 {
3541 case CALL_EXPR:
3542 {
3543 const_tree arg;
3544 const_call_expr_arg_iterator iter;
3545 FOR_EACH_CONST_CALL_EXPR_ARG (arg, iter, exp)
3546 if (CONTAINS_PLACEHOLDER_P (arg))
3547 return 1;
3548 return 0;
3549 }
3550 default:
3551 return 0;
3552 }
3553
3554 default:
3555 return 0;
3556 }
3557 return 0;
3558}
3559
3560/* Return true if any part of the structure of TYPE involves a PLACEHOLDER_EXPR
3561 directly. This includes size, bounds, qualifiers (for QUAL_UNION_TYPE) and
3562 field positions. */
3563
3564static bool
3565type_contains_placeholder_1 (const_tree type)
3566{
3567 /* If the size contains a placeholder or the parent type (component type in
3568 the case of arrays) type involves a placeholder, this type does. */
3569 if (CONTAINS_PLACEHOLDER_P (TYPE_SIZE (type))
3570 || CONTAINS_PLACEHOLDER_P (TYPE_SIZE_UNIT (type))
3571 || (!POINTER_TYPE_P (type)
3572 && TREE_TYPE (type)
3573 && type_contains_placeholder_p (TREE_TYPE (type))))
3574 return true;
3575
3576 /* Now do type-specific checks. Note that the last part of the check above
3577 greatly limits what we have to do below. */
3578 switch (TREE_CODE (type))
3579 {
3580 case VOID_TYPE:
3581 case POINTER_BOUNDS_TYPE:
3582 case COMPLEX_TYPE:
3583 case ENUMERAL_TYPE:
3584 case BOOLEAN_TYPE:
3585 case POINTER_TYPE:
3586 case OFFSET_TYPE:
3587 case REFERENCE_TYPE:
3588 case METHOD_TYPE:
3589 case FUNCTION_TYPE:
3590 case VECTOR_TYPE:
3591 case NULLPTR_TYPE:
3592 return false;
3593
3594 case INTEGER_TYPE:
3595 case REAL_TYPE:
3596 case FIXED_POINT_TYPE:
3597 /* Here we just check the bounds. */
3598 return (CONTAINS_PLACEHOLDER_P (TYPE_MIN_VALUE (type))
3599 || CONTAINS_PLACEHOLDER_P (TYPE_MAX_VALUE (type)));
3600
3601 case ARRAY_TYPE:
3602 /* We have already checked the component type above, so just check
3603 the domain type. Flexible array members have a null domain. */
3604 return TYPE_DOMAIN (type) ?
3605 type_contains_placeholder_p (TYPE_DOMAIN (type)) : false;
3606
3607 case RECORD_TYPE:
3608 case UNION_TYPE:
3609 case QUAL_UNION_TYPE:
3610 {
3611 tree field;
3612
3613 for (field = TYPE_FIELDS (type); field; field = DECL_CHAIN (field))
3614 if (TREE_CODE (field) == FIELD_DECL
3615 && (CONTAINS_PLACEHOLDER_P (DECL_FIELD_OFFSET (field))
3616 || (TREE_CODE (type) == QUAL_UNION_TYPE
3617 && CONTAINS_PLACEHOLDER_P (DECL_QUALIFIER (field)))
3618 || type_contains_placeholder_p (TREE_TYPE (field))))
3619 return true;
3620
3621 return false;
3622 }
3623
3624 default:
3625 gcc_unreachable ();
3626 }
3627}
3628
3629/* Wrapper around above function used to cache its result. */
3630
3631bool
3632type_contains_placeholder_p (tree type)
3633{
3634 bool result;
3635
3636 /* If the contains_placeholder_bits field has been initialized,
3637 then we know the answer. */
3638 if (TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) > 0)
3639 return TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) - 1;
3640
3641 /* Indicate that we've seen this type node, and the answer is false.
3642 This is what we want to return if we run into recursion via fields. */
3643 TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) = 1;
3644
3645 /* Compute the real value. */
3646 result = type_contains_placeholder_1 (type);
3647
3648 /* Store the real value. */
3649 TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) = result + 1;
3650
3651 return result;
3652}
3653
3654/* Push tree EXP onto vector QUEUE if it is not already present. */
3655
3656static void
3657push_without_duplicates (tree exp, vec<tree> *queue)
3658{
3659 unsigned int i;
3660 tree iter;
3661
3662 FOR_EACH_VEC_ELT (*queue, i, iter)
3663 if (simple_cst_equal (iter, exp) == 1)
3664 break;
3665
3666 if (!iter)
3667 queue->safe_push (exp);
3668}
3669
3670/* Given a tree EXP, find all occurrences of references to fields
3671 in a PLACEHOLDER_EXPR and place them in vector REFS without
3672 duplicates. Also record VAR_DECLs and CONST_DECLs. Note that
3673 we assume here that EXP contains only arithmetic expressions
3674 or CALL_EXPRs with PLACEHOLDER_EXPRs occurring only in their
3675 argument list. */
3676
3677void
3678find_placeholder_in_expr (tree exp, vec<tree> *refs)
3679{
3680 enum tree_code code = TREE_CODE (exp);
3681 tree inner;
3682 int i;
3683
3684 /* We handle TREE_LIST and COMPONENT_REF separately. */
3685 if (code == TREE_LIST)
3686 {
3687 FIND_PLACEHOLDER_IN_EXPR (TREE_CHAIN (exp), refs);
3688 FIND_PLACEHOLDER_IN_EXPR (TREE_VALUE (exp), refs);
3689 }
3690 else if (code == COMPONENT_REF)
3691 {
3692 for (inner = TREE_OPERAND (exp, 0);
3693 REFERENCE_CLASS_P (inner);
3694 inner = TREE_OPERAND (inner, 0))
3695 ;
3696
3697 if (TREE_CODE (inner) == PLACEHOLDER_EXPR)
3698 push_without_duplicates (exp, refs);
3699 else
3700 FIND_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), refs);
3701 }
3702 else
3703 switch (TREE_CODE_CLASS (code))
3704 {
3705 case tcc_constant:
3706 break;
3707
3708 case tcc_declaration:
3709 /* Variables allocated to static storage can stay. */
3710 if (!TREE_STATIC (exp))
3711 push_without_duplicates (exp, refs);
3712 break;
3713
3714 case tcc_expression:
3715 /* This is the pattern built in ada/make_aligning_type. */
3716 if (code == ADDR_EXPR
3717 && TREE_CODE (TREE_OPERAND (exp, 0)) == PLACEHOLDER_EXPR)
3718 {
3719 push_without_duplicates (exp, refs);
3720 break;
3721 }
3722
3723 /* Fall through. */
3724
3725 case tcc_exceptional:
3726 case tcc_unary:
3727 case tcc_binary:
3728 case tcc_comparison:
3729 case tcc_reference:
3730 for (i = 0; i < TREE_CODE_LENGTH (code); i++)
3731 FIND_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, i), refs);
3732 break;
3733
3734 case tcc_vl_exp:
3735 for (i = 1; i < TREE_OPERAND_LENGTH (exp); i++)
3736 FIND_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, i), refs);
3737 break;
3738
3739 default:
3740 gcc_unreachable ();
3741 }
3742}
3743
3744/* Given a tree EXP, a FIELD_DECL F, and a replacement value R,
3745 return a tree with all occurrences of references to F in a
3746 PLACEHOLDER_EXPR replaced by R. Also handle VAR_DECLs and
3747 CONST_DECLs. Note that we assume here that EXP contains only
3748 arithmetic expressions or CALL_EXPRs with PLACEHOLDER_EXPRs
3749 occurring only in their argument list. */
3750
3751tree
3752substitute_in_expr (tree exp, tree f, tree r)
3753{
3754 enum tree_code code = TREE_CODE (exp);
3755 tree op0, op1, op2, op3;
3756 tree new_tree;
3757
3758 /* We handle TREE_LIST and COMPONENT_REF separately. */
3759 if (code == TREE_LIST)
3760 {
3761 op0 = SUBSTITUTE_IN_EXPR (TREE_CHAIN (exp), f, r);
3762 op1 = SUBSTITUTE_IN_EXPR (TREE_VALUE (exp), f, r);
3763 if (op0 == TREE_CHAIN (exp) && op1 == TREE_VALUE (exp))
3764 return exp;
3765
3766 return tree_cons (TREE_PURPOSE (exp), op1, op0);
3767 }
3768 else if (code == COMPONENT_REF)
3769 {
3770 tree inner;
3771
3772 /* If this expression is getting a value from a PLACEHOLDER_EXPR
3773 and it is the right field, replace it with R. */
3774 for (inner = TREE_OPERAND (exp, 0);
3775 REFERENCE_CLASS_P (inner);
3776 inner = TREE_OPERAND (inner, 0))
3777 ;
3778
3779 /* The field. */
3780 op1 = TREE_OPERAND (exp, 1);
3781
3782 if (TREE_CODE (inner) == PLACEHOLDER_EXPR && op1 == f)
3783 return r;
3784
3785 /* If this expression hasn't been completed let, leave it alone. */
3786 if (TREE_CODE (inner) == PLACEHOLDER_EXPR && !TREE_TYPE (inner))
3787 return exp;
3788
3789 op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
3790 if (op0 == TREE_OPERAND (exp, 0))
3791 return exp;
3792
3793 new_tree
3794 = fold_build3 (COMPONENT_REF, TREE_TYPE (exp), op0, op1, NULL_TREE);
3795 }
3796 else
3797 switch (TREE_CODE_CLASS (code))
3798 {
3799 case tcc_constant:
3800 return exp;
3801
3802 case tcc_declaration:
3803 if (exp == f)
3804 return r;
3805 else
3806 return exp;
3807
3808 case tcc_expression:
3809 if (exp == f)
3810 return r;
3811
3812 /* Fall through. */
3813
3814 case tcc_exceptional:
3815 case tcc_unary:
3816 case tcc_binary:
3817 case tcc_comparison:
3818 case tcc_reference:
3819 switch (TREE_CODE_LENGTH (code))
3820 {
3821 case 0:
3822 return exp;
3823
3824 case 1:
3825 op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
3826 if (op0 == TREE_OPERAND (exp, 0))
3827 return exp;
3828
3829 new_tree = fold_build1 (code, TREE_TYPE (exp), op0);
3830 break;
3831
3832 case 2:
3833 op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
3834 op1 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 1), f, r);
3835
3836 if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1))
3837 return exp;
3838
3839 new_tree = fold_build2 (code, TREE_TYPE (exp), op0, op1);
3840 break;
3841
3842 case 3:
3843 op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
3844 op1 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 1), f, r);
3845 op2 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 2), f, r);
3846
3847 if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
3848 && op2 == TREE_OPERAND (exp, 2))
3849 return exp;
3850
3851 new_tree = fold_build3 (code, TREE_TYPE (exp), op0, op1, op2);
3852 break;
3853
3854 case 4:
3855 op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
3856 op1 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 1), f, r);
3857 op2 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 2), f, r);
3858 op3 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 3), f, r);
3859
3860 if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
3861 && op2 == TREE_OPERAND (exp, 2)
3862 && op3 == TREE_OPERAND (exp, 3))
3863 return exp;
3864
3865 new_tree
3866 = fold (build4 (code, TREE_TYPE (exp), op0, op1, op2, op3));
3867 break;
3868
3869 default:
3870 gcc_unreachable ();
3871 }
3872 break;
3873
3874 case tcc_vl_exp:
3875 {
3876 int i;
3877
3878 new_tree = NULL_TREE;
3879
3880 /* If we are trying to replace F with a constant or with another
3881 instance of one of the arguments of the call, inline back
3882 functions which do nothing else than computing a value from
3883 the arguments they are passed. This makes it possible to
3884 fold partially or entirely the replacement expression. */
3885 if (code == CALL_EXPR)
3886 {
3887 bool maybe_inline = false;
3888 if (CONSTANT_CLASS_P (r))
3889 maybe_inline = true;
3890 else
3891 for (i = 3; i < TREE_OPERAND_LENGTH (exp); i++)
3892 if (operand_equal_p (TREE_OPERAND (exp, i), r, 0))
3893 {
3894 maybe_inline = true;
3895 break;
3896 }
3897 if (maybe_inline)
3898 {
3899 tree t = maybe_inline_call_in_expr (exp);
3900 if (t)
3901 return SUBSTITUTE_IN_EXPR (t, f, r);
3902 }
3903 }
3904
3905 for (i = 1; i < TREE_OPERAND_LENGTH (exp); i++)
3906 {
3907 tree op = TREE_OPERAND (exp, i);
3908 tree new_op = SUBSTITUTE_IN_EXPR (op, f, r);
3909 if (new_op != op)
3910 {
3911 if (!new_tree)
3912 new_tree = copy_node (exp);
3913 TREE_OPERAND (new_tree, i) = new_op;
3914 }
3915 }
3916
3917 if (new_tree)
3918 {
3919 new_tree = fold (new_tree);
3920 if (TREE_CODE (new_tree) == CALL_EXPR)
3921 process_call_operands (new_tree);
3922 }
3923 else
3924 return exp;
3925 }
3926 break;
3927
3928 default:
3929 gcc_unreachable ();
3930 }
3931
3932 TREE_READONLY (new_tree) |= TREE_READONLY (exp);
3933
3934 if (code == INDIRECT_REF || code == ARRAY_REF || code == ARRAY_RANGE_REF)
3935 TREE_THIS_NOTRAP (new_tree) |= TREE_THIS_NOTRAP (exp);
3936
3937 return new_tree;
3938}
3939
3940/* Similar, but look for a PLACEHOLDER_EXPR in EXP and find a replacement
3941 for it within OBJ, a tree that is an object or a chain of references. */
3942
3943tree
3944substitute_placeholder_in_expr (tree exp, tree obj)
3945{
3946 enum tree_code code = TREE_CODE (exp);
3947 tree op0, op1, op2, op3;
3948 tree new_tree;
3949
3950 /* If this is a PLACEHOLDER_EXPR, see if we find a corresponding type
3951 in the chain of OBJ. */
3952 if (code == PLACEHOLDER_EXPR)
3953 {
3954 tree need_type = TYPE_MAIN_VARIANT (TREE_TYPE (exp));
3955 tree elt;
3956
3957 for (elt = obj; elt != 0;
3958 elt = ((TREE_CODE (elt) == COMPOUND_EXPR
3959 || TREE_CODE (elt) == COND_EXPR)
3960 ? TREE_OPERAND (elt, 1)
3961 : (REFERENCE_CLASS_P (elt)
3962 || UNARY_CLASS_P (elt)
3963 || BINARY_CLASS_P (elt)
3964 || VL_EXP_CLASS_P (elt)
3965 || EXPRESSION_CLASS_P (elt))
3966 ? TREE_OPERAND (elt, 0) : 0))
3967 if (TYPE_MAIN_VARIANT (TREE_TYPE (elt)) == need_type)
3968 return elt;
3969
3970 for (elt = obj; elt != 0;
3971 elt = ((TREE_CODE (elt) == COMPOUND_EXPR
3972 || TREE_CODE (elt) == COND_EXPR)
3973 ? TREE_OPERAND (elt, 1)
3974 : (REFERENCE_CLASS_P (elt)
3975 || UNARY_CLASS_P (elt)
3976 || BINARY_CLASS_P (elt)
3977 || VL_EXP_CLASS_P (elt)
3978 || EXPRESSION_CLASS_P (elt))
3979 ? TREE_OPERAND (elt, 0) : 0))
3980 if (POINTER_TYPE_P (TREE_TYPE (elt))
3981 && (TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (elt)))
3982 == need_type))
3983 return fold_build1 (INDIRECT_REF, need_type, elt);
3984
3985 /* If we didn't find it, return the original PLACEHOLDER_EXPR. If it
3986 survives until RTL generation, there will be an error. */
3987 return exp;
3988 }
3989
3990 /* TREE_LIST is special because we need to look at TREE_VALUE
3991 and TREE_CHAIN, not TREE_OPERANDS. */
3992 else if (code == TREE_LIST)
3993 {
3994 op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_CHAIN (exp), obj);
3995 op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_VALUE (exp), obj);
3996 if (op0 == TREE_CHAIN (exp) && op1 == TREE_VALUE (exp))
3997 return exp;
3998
3999 return tree_cons (TREE_PURPOSE (exp), op1, op0);
4000 }
4001 else
4002 switch (TREE_CODE_CLASS (code))
4003 {
4004 case tcc_constant:
4005 case tcc_declaration:
4006 return exp;
4007
4008 case tcc_exceptional:
4009 case tcc_unary:
4010 case tcc_binary:
4011 case tcc_comparison:
4012 case tcc_expression:
4013 case tcc_reference:
4014 case tcc_statement:
4015 switch (TREE_CODE_LENGTH (code))
4016 {
4017 case 0:
4018 return exp;
4019
4020 case 1:
4021 op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
4022 if (op0 == TREE_OPERAND (exp, 0))
4023 return exp;
4024
4025 new_tree = fold_build1 (code, TREE_TYPE (exp), op0);
4026 break;
4027
4028 case 2:
4029 op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
4030 op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 1), obj);
4031
4032 if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1))
4033 return exp;
4034
4035 new_tree = fold_build2 (code, TREE_TYPE (exp), op0, op1);
4036 break;
4037
4038 case 3:
4039 op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
4040 op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 1), obj);
4041 op2 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 2), obj);
4042
4043 if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
4044 && op2 == TREE_OPERAND (exp, 2))
4045 return exp;
4046
4047 new_tree = fold_build3 (code, TREE_TYPE (exp), op0, op1, op2);
4048 break;
4049
4050 case 4:
4051 op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
4052 op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 1), obj);
4053 op2 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 2), obj);
4054 op3 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 3), obj);
4055
4056 if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
4057 && op2 == TREE_OPERAND (exp, 2)
4058 && op3 == TREE_OPERAND (exp, 3))
4059 return exp;
4060
4061 new_tree
4062 = fold (build4 (code, TREE_TYPE (exp), op0, op1, op2, op3));
4063 break;
4064
4065 default:
4066 gcc_unreachable ();
4067 }
4068 break;
4069
4070 case tcc_vl_exp:
4071 {
4072 int i;
4073
4074 new_tree = NULL_TREE;
4075
4076 for (i = 1; i < TREE_OPERAND_LENGTH (exp); i++)
4077 {
4078 tree op = TREE_OPERAND (exp, i);
4079 tree new_op = SUBSTITUTE_PLACEHOLDER_IN_EXPR (op, obj);
4080 if (new_op != op)
4081 {
4082 if (!new_tree)
4083 new_tree = copy_node (exp);
4084 TREE_OPERAND (new_tree, i) = new_op;
4085 }
4086 }
4087
4088 if (new_tree)
4089 {
4090 new_tree = fold (new_tree);
4091 if (TREE_CODE (new_tree) == CALL_EXPR)
4092 process_call_operands (new_tree);
4093 }
4094 else
4095 return exp;
4096 }
4097 break;
4098
4099 default:
4100 gcc_unreachable ();
4101 }
4102
4103 TREE_READONLY (new_tree) |= TREE_READONLY (exp);
4104
4105 if (code == INDIRECT_REF || code == ARRAY_REF || code == ARRAY_RANGE_REF)
4106 TREE_THIS_NOTRAP (new_tree) |= TREE_THIS_NOTRAP (exp);
4107
4108 return new_tree;
4109}
4110
4111
4112/* Subroutine of stabilize_reference; this is called for subtrees of
4113 references. Any expression with side-effects must be put in a SAVE_EXPR
4114 to ensure that it is only evaluated once.
4115
4116 We don't put SAVE_EXPR nodes around everything, because assigning very
4117 simple expressions to temporaries causes us to miss good opportunities
4118 for optimizations. Among other things, the opportunity to fold in the
4119 addition of a constant into an addressing mode often gets lost, e.g.
4120 "y[i+1] += x;". In general, we take the approach that we should not make
4121 an assignment unless we are forced into it - i.e., that any non-side effect
4122 operator should be allowed, and that cse should take care of coalescing
4123 multiple utterances of the same expression should that prove fruitful. */
4124
4125static tree
4126stabilize_reference_1 (tree e)
4127{
4128 tree result;
4129 enum tree_code code = TREE_CODE (e);
4130
4131 /* We cannot ignore const expressions because it might be a reference
4132 to a const array but whose index contains side-effects. But we can
4133 ignore things that are actual constant or that already have been
4134 handled by this function. */
4135
4136 if (tree_invariant_p (e))
4137 return e;
4138
4139 switch (TREE_CODE_CLASS (code))
4140 {
4141 case tcc_exceptional:
4142 case tcc_type:
4143 case tcc_declaration:
4144 case tcc_comparison:
4145 case tcc_statement:
4146 case tcc_expression:
4147 case tcc_reference:
4148 case tcc_vl_exp:
4149 /* If the expression has side-effects, then encase it in a SAVE_EXPR
4150 so that it will only be evaluated once. */
4151 /* The reference (r) and comparison (<) classes could be handled as
4152 below, but it is generally faster to only evaluate them once. */
4153 if (TREE_SIDE_EFFECTS (e))
4154 return save_expr (e);
4155 return e;
4156
4157 case tcc_constant:
4158 /* Constants need no processing. In fact, we should never reach
4159 here. */
4160 return e;
4161
4162 case tcc_binary:
4163 /* Division is slow and tends to be compiled with jumps,
4164 especially the division by powers of 2 that is often
4165 found inside of an array reference. So do it just once. */
4166 if (code == TRUNC_DIV_EXPR || code == TRUNC_MOD_EXPR
4167 || code == FLOOR_DIV_EXPR || code == FLOOR_MOD_EXPR
4168 || code == CEIL_DIV_EXPR || code == CEIL_MOD_EXPR
4169 || code == ROUND_DIV_EXPR || code == ROUND_MOD_EXPR)
4170 return save_expr (e);
4171 /* Recursively stabilize each operand. */
4172 result = build_nt (code, stabilize_reference_1 (TREE_OPERAND (e, 0)),
4173 stabilize_reference_1 (TREE_OPERAND (e, 1)));
4174 break;
4175
4176 case tcc_unary:
4177 /* Recursively stabilize each operand. */
4178 result = build_nt (code, stabilize_reference_1 (TREE_OPERAND (e, 0)));
4179 break;
4180
4181 default:
4182 gcc_unreachable ();
4183 }
4184
4185 TREE_TYPE (result) = TREE_TYPE (e);
4186 TREE_READONLY (result) = TREE_READONLY (e);
4187 TREE_SIDE_EFFECTS (result) = TREE_SIDE_EFFECTS (e);
4188 TREE_THIS_VOLATILE (result) = TREE_THIS_VOLATILE (e);
4189
4190 return result;
4191}
4192
4193/* Stabilize a reference so that we can use it any number of times
4194 without causing its operands to be evaluated more than once.
4195 Returns the stabilized reference. This works by means of save_expr,
4196 so see the caveats in the comments about save_expr.
4197
4198 Also allows conversion expressions whose operands are references.
4199 Any other kind of expression is returned unchanged. */
4200
4201tree
4202stabilize_reference (tree ref)
4203{
4204 tree result;
4205 enum tree_code code = TREE_CODE (ref);
4206
4207 switch (code)
4208 {
4209 case VAR_DECL:
4210 case PARM_DECL:
4211 case RESULT_DECL:
4212 /* No action is needed in this case. */
4213 return ref;
4214
4215 CASE_CONVERT:
4216 case FLOAT_EXPR:
4217 case FIX_TRUNC_EXPR:
4218 result = build_nt (code, stabilize_reference (TREE_OPERAND (ref, 0)));
4219 break;
4220
4221 case INDIRECT_REF:
4222 result = build_nt (INDIRECT_REF,
4223 stabilize_reference_1 (TREE_OPERAND (ref, 0)));
4224 break;
4225
4226 case COMPONENT_REF:
4227 result = build_nt (COMPONENT_REF,
4228 stabilize_reference (TREE_OPERAND (ref, 0)),
4229 TREE_OPERAND (ref, 1), NULL_TREE);
4230 break;
4231
4232 case BIT_FIELD_REF:
4233 result = build_nt (BIT_FIELD_REF,
4234 stabilize_reference (TREE_OPERAND (ref, 0)),
4235 TREE_OPERAND (ref, 1), TREE_OPERAND (ref, 2));
4236 REF_REVERSE_STORAGE_ORDER (result) = REF_REVERSE_STORAGE_ORDER (ref);
4237 break;
4238
4239 case ARRAY_REF:
4240 result = build_nt (ARRAY_REF,
4241 stabilize_reference (TREE_OPERAND (ref, 0)),
4242 stabilize_reference_1 (TREE_OPERAND (ref, 1)),
4243 TREE_OPERAND (ref, 2), TREE_OPERAND (ref, 3));
4244 break;
4245
4246 case ARRAY_RANGE_REF:
4247 result = build_nt (ARRAY_RANGE_REF,
4248 stabilize_reference (TREE_OPERAND (ref, 0)),
4249 stabilize_reference_1 (TREE_OPERAND (ref, 1)),
4250 TREE_OPERAND (ref, 2), TREE_OPERAND (ref, 3));
4251 break;
4252
4253 case COMPOUND_EXPR:
4254 /* We cannot wrap the first expression in a SAVE_EXPR, as then
4255 it wouldn't be ignored. This matters when dealing with
4256 volatiles. */
4257 return stabilize_reference_1 (ref);
4258
4259 /* If arg isn't a kind of lvalue we recognize, make no change.
4260 Caller should recognize the error for an invalid lvalue. */
4261 default:
4262 return ref;
4263
4264 case ERROR_MARK:
4265 return error_mark_node;
4266 }
4267
4268 TREE_TYPE (result) = TREE_TYPE (ref);
4269 TREE_READONLY (result) = TREE_READONLY (ref);
4270 TREE_SIDE_EFFECTS (result) = TREE_SIDE_EFFECTS (ref);
4271 TREE_THIS_VOLATILE (result) = TREE_THIS_VOLATILE (ref);
4272
4273 return result;
4274}
4275
4276/* Low-level constructors for expressions. */
4277
4278/* A helper function for build1 and constant folders. Set TREE_CONSTANT,
4279 and TREE_SIDE_EFFECTS for an ADDR_EXPR. */
4280
4281void
4282recompute_tree_invariant_for_addr_expr (tree t)
4283{
4284 tree node;
4285 bool tc = true, se = false;
4286
4287 gcc_assert (TREE_CODE (t) == ADDR_EXPR);
4288
4289 /* We started out assuming this address is both invariant and constant, but
4290 does not have side effects. Now go down any handled components and see if
4291 any of them involve offsets that are either non-constant or non-invariant.
4292 Also check for side-effects.
4293
4294 ??? Note that this code makes no attempt to deal with the case where
4295 taking the address of something causes a copy due to misalignment. */
4296
4297#define UPDATE_FLAGS(NODE) \
4298do { tree _node = (NODE); \
4299 if (_node && !TREE_CONSTANT (_node)) tc = false; \
4300 if (_node && TREE_SIDE_EFFECTS (_node)) se = true; } while (0)
4301
4302 for (node = TREE_OPERAND (t, 0); handled_component_p (node);
4303 node = TREE_OPERAND (node, 0))
4304 {
4305 /* If the first operand doesn't have an ARRAY_TYPE, this is a bogus
4306 array reference (probably made temporarily by the G++ front end),
4307 so ignore all the operands. */
4308 if ((TREE_CODE (node) == ARRAY_REF
4309 || TREE_CODE (node) == ARRAY_RANGE_REF)
4310 && TREE_CODE (TREE_TYPE (TREE_OPERAND (node, 0))) == ARRAY_TYPE)
4311 {
4312 UPDATE_FLAGS (TREE_OPERAND (node, 1));
4313 if (TREE_OPERAND (node, 2))
4314 UPDATE_FLAGS (TREE_OPERAND (node, 2));
4315 if (TREE_OPERAND (node, 3))
4316 UPDATE_FLAGS (TREE_OPERAND (node, 3));
4317 }
4318 /* Likewise, just because this is a COMPONENT_REF doesn't mean we have a
4319 FIELD_DECL, apparently. The G++ front end can put something else
4320 there, at least temporarily. */
4321 else if (TREE_CODE (node) == COMPONENT_REF
4322 && TREE_CODE (TREE_OPERAND (node, 1)) == FIELD_DECL)
4323 {
4324 if (TREE_OPERAND (node, 2))
4325 UPDATE_FLAGS (TREE_OPERAND (node, 2));
4326 }
4327 }
4328
4329 node = lang_hooks.expr_to_decl (node, &tc, &se);
4330
4331 /* Now see what's inside. If it's an INDIRECT_REF, copy our properties from
4332 the address, since &(*a)->b is a form of addition. If it's a constant, the
4333 address is constant too. If it's a decl, its address is constant if the
4334 decl is static. Everything else is not constant and, furthermore,
4335 taking the address of a volatile variable is not volatile. */
4336 if (TREE_CODE (node) == INDIRECT_REF
4337 || TREE_CODE (node) == MEM_REF)
4338 UPDATE_FLAGS (TREE_OPERAND (node, 0));
4339 else if (CONSTANT_CLASS_P (node))
4340 ;
4341 else if (DECL_P (node))
4342 tc &= (staticp (node) != NULL_TREE);
4343 else
4344 {
4345 tc = false;
4346 se |= TREE_SIDE_EFFECTS (node);
4347 }
4348
4349
4350 TREE_CONSTANT (t) = tc;
4351 TREE_SIDE_EFFECTS (t) = se;
4352#undef UPDATE_FLAGS
4353}
4354
4355/* Build an expression of code CODE, data type TYPE, and operands as
4356 specified. Expressions and reference nodes can be created this way.
4357 Constants, decls, types and misc nodes cannot be.
4358
4359 We define 5 non-variadic functions, from 0 to 4 arguments. This is
4360 enough for all extant tree codes. */
4361
4362tree
4363build0 (enum tree_code code, tree tt MEM_STAT_DECL)
4364{
4365 tree t;
4366
4367 gcc_assert (TREE_CODE_LENGTH (code) == 0);
4368
4369 t = make_node (code PASS_MEM_STAT);
4370 TREE_TYPE (t) = tt;
4371
4372 return t;
4373}
4374
4375tree
4376build1 (enum tree_code code, tree type, tree node MEM_STAT_DECL)
4377{
4378 int length = sizeof (struct tree_exp);
4379 tree t;
4380
4381 record_node_allocation_statistics (code, length);
4382
4383 gcc_assert (TREE_CODE_LENGTH (code) == 1);
4384
4385 t = ggc_alloc_tree_node_stat (length PASS_MEM_STAT);
4386
4387 memset (t, 0, sizeof (struct tree_common));
4388
4389 TREE_SET_CODE (t, code);
4390
4391 TREE_TYPE (t) = type;
4392 SET_EXPR_LOCATION (t, UNKNOWN_LOCATION);
4393 TREE_OPERAND (t, 0) = node;
4394 if (node && !TYPE_P (node))
4395 {
4396 TREE_SIDE_EFFECTS (t) = TREE_SIDE_EFFECTS (node);
4397 TREE_READONLY (t) = TREE_READONLY (node);
4398 }
4399
4400 if (TREE_CODE_CLASS (code) == tcc_statement)
4401 {
4402 if (code != DEBUG_BEGIN_STMT)
4403 TREE_SIDE_EFFECTS (t) = 1;
4404 }
4405 else switch (code)
4406 {
4407 case VA_ARG_EXPR:
4408 /* All of these have side-effects, no matter what their
4409 operands are. */
4410 TREE_SIDE_EFFECTS (t) = 1;
4411 TREE_READONLY (t) = 0;
4412 break;
4413
4414 case INDIRECT_REF:
4415 /* Whether a dereference is readonly has nothing to do with whether
4416 its operand is readonly. */
4417 TREE_READONLY (t) = 0;
4418 break;
4419
4420 case ADDR_EXPR:
4421 if (node)
4422 recompute_tree_invariant_for_addr_expr (t);
4423 break;
4424
4425 default:
4426 if ((TREE_CODE_CLASS (code) == tcc_unary || code == VIEW_CONVERT_EXPR)
4427 && node && !TYPE_P (node)
4428 && TREE_CONSTANT (node))
4429 TREE_CONSTANT (t) = 1;
4430 if (TREE_CODE_CLASS (code) == tcc_reference
4431 && node && TREE_THIS_VOLATILE (node))
4432 TREE_THIS_VOLATILE (t) = 1;
4433 break;
4434 }
4435
4436 return t;
4437}
4438
4439#define PROCESS_ARG(N) \
4440 do { \
4441 TREE_OPERAND (t, N) = arg##N; \
4442 if (arg##N &&!TYPE_P (arg##N)) \
4443 { \
4444 if (TREE_SIDE_EFFECTS (arg##N)) \
4445 side_effects = 1; \
4446 if (!TREE_READONLY (arg##N) \
4447 && !CONSTANT_CLASS_P (arg##N)) \
4448 (void) (read_only = 0); \
4449 if (!TREE_CONSTANT (arg##N)) \
4450 (void) (constant = 0); \
4451 } \
4452 } while (0)
4453
4454tree
4455build2 (enum tree_code code, tree tt, tree arg0, tree arg1 MEM_STAT_DECL)
4456{
4457 bool constant, read_only, side_effects, div_by_zero;
4458 tree t;
4459
4460 gcc_assert (TREE_CODE_LENGTH (code) == 2);
4461
4462 if ((code == MINUS_EXPR || code == PLUS_EXPR || code == MULT_EXPR)
4463 && arg0 && arg1 && tt && POINTER_TYPE_P (tt)
4464 /* When sizetype precision doesn't match that of pointers
4465 we need to be able to build explicit extensions or truncations
4466 of the offset argument. */
4467 && TYPE_PRECISION (sizetype) == TYPE_PRECISION (tt))
4468 gcc_assert (TREE_CODE (arg0) == INTEGER_CST
4469 && TREE_CODE (arg1) == INTEGER_CST);
4470
4471 if (code == POINTER_PLUS_EXPR && arg0 && arg1 && tt)
4472 gcc_assert (POINTER_TYPE_P (tt) && POINTER_TYPE_P (TREE_TYPE (arg0))
4473 && ptrofftype_p (TREE_TYPE (arg1)));
4474
4475 t = make_node (code PASS_MEM_STAT);
4476 TREE_TYPE (t) = tt;
4477
4478 /* Below, we automatically set TREE_SIDE_EFFECTS and TREE_READONLY for the
4479 result based on those same flags for the arguments. But if the
4480 arguments aren't really even `tree' expressions, we shouldn't be trying
4481 to do this. */
4482
4483 /* Expressions without side effects may be constant if their
4484 arguments are as well. */
4485 constant = (TREE_CODE_CLASS (code) == tcc_comparison
4486 || TREE_CODE_CLASS (code) == tcc_binary);
4487 read_only = 1;
4488 side_effects = TREE_SIDE_EFFECTS (t);
4489
4490 switch (code)
4491 {
4492 case TRUNC_DIV_EXPR:
4493 case CEIL_DIV_EXPR:
4494 case FLOOR_DIV_EXPR:
4495 case ROUND_DIV_EXPR:
4496 case EXACT_DIV_EXPR:
4497 case CEIL_MOD_EXPR:
4498 case FLOOR_MOD_EXPR:
4499 case ROUND_MOD_EXPR:
4500 case TRUNC_MOD_EXPR:
4501 div_by_zero = integer_zerop (arg1);
4502 break;
4503 default:
4504 div_by_zero = false;
4505 }
4506
4507 PROCESS_ARG (0);
4508 PROCESS_ARG (1);
4509
4510 TREE_SIDE_EFFECTS (t) = side_effects;
4511 if (code == MEM_REF)
4512 {
4513 if (arg0 && TREE_CODE (arg0) == ADDR_EXPR)
4514 {
4515 tree o = TREE_OPERAND (arg0, 0);
4516 TREE_READONLY (t) = TREE_READONLY (o);
4517 TREE_THIS_VOLATILE (t) = TREE_THIS_VOLATILE (o);
4518 }
4519 }
4520 else
4521 {
4522 TREE_READONLY (t) = read_only;
4523 /* Don't mark X / 0 as constant. */
4524 TREE_CONSTANT (t) = constant && !div_by_zero;
4525 TREE_THIS_VOLATILE (t)
4526 = (TREE_CODE_CLASS (code) == tcc_reference
4527 && arg0 && TREE_THIS_VOLATILE (arg0));
4528 }
4529
4530 return t;
4531}
4532
4533
4534tree
4535build3 (enum tree_code code, tree tt, tree arg0, tree arg1,
4536 tree arg2 MEM_STAT_DECL)
4537{
4538 bool constant, read_only, side_effects;
4539 tree t;
4540
4541 gcc_assert (TREE_CODE_LENGTH (code) == 3);
4542 gcc_assert (TREE_CODE_CLASS (code) != tcc_vl_exp);
4543
4544 t = make_node (code PASS_MEM_STAT);
4545 TREE_TYPE (t) = tt;
4546
4547 read_only = 1;
4548
4549 /* As a special exception, if COND_EXPR has NULL branches, we
4550 assume that it is a gimple statement and always consider
4551 it to have side effects. */
4552 if (code == COND_EXPR
4553 && tt == void_type_node
4554 && arg1 == NULL_TREE
4555 && arg2 == NULL_TREE)
4556 side_effects = true;
4557 else
4558 side_effects = TREE_SIDE_EFFECTS (t);
4559
4560 PROCESS_ARG (0);
4561 PROCESS_ARG (1);
4562 PROCESS_ARG (2);
4563
4564 if (code == COND_EXPR)
4565 TREE_READONLY (t) = read_only;
4566
4567 TREE_SIDE_EFFECTS (t) = side_effects;
4568 TREE_THIS_VOLATILE (t)
4569 = (TREE_CODE_CLASS (code) == tcc_reference
4570 && arg0 && TREE_THIS_VOLATILE (arg0));
4571
4572 return t;
4573}
4574
4575tree
4576build4 (enum tree_code code, tree tt, tree arg0, tree arg1,
4577 tree arg2, tree arg3 MEM_STAT_DECL)
4578{
4579 bool constant, read_only, side_effects;
4580 tree t;
4581
4582 gcc_assert (TREE_CODE_LENGTH (code) == 4);
4583
4584 t = make_node (code PASS_MEM_STAT);
4585 TREE_TYPE (t) = tt;
4586
4587 side_effects = TREE_SIDE_EFFECTS (t);
4588
4589 PROCESS_ARG (0);
4590 PROCESS_ARG (1);
4591 PROCESS_ARG (2);
4592 PROCESS_ARG (3);
4593
4594 TREE_SIDE_EFFECTS (t) = side_effects;
4595 TREE_THIS_VOLATILE (t)
4596 = (TREE_CODE_CLASS (code) == tcc_reference
4597 && arg0 && TREE_THIS_VOLATILE (arg0));
4598
4599 return t;
4600}
4601
4602tree
4603build5 (enum tree_code code, tree tt, tree arg0, tree arg1,
4604 tree arg2, tree arg3, tree arg4 MEM_STAT_DECL)
4605{
4606 bool constant, read_only, side_effects;
4607 tree t;
4608
4609 gcc_assert (TREE_CODE_LENGTH (