1/* Language-independent node constructors for parse phase of GNU compiler. 2 Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 3 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006 4 Free Software Foundation, Inc. 5 6This file is part of GCC. 7 8GCC is free software; you can redistribute it and/or modify it under 9the terms of the GNU General Public License as published by the Free 10Software Foundation; either version 2, or (at your option) any later 11version. 12 13GCC is distributed in the hope that it will be useful, but WITHOUT ANY 14WARRANTY; without even the implied warranty of MERCHANTABILITY or 15FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 16for more details. 17 18You should have received a copy of the GNU General Public License 19along with GCC; see the file COPYING. If not, write to the Free 20Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 2102110-1301, USA. */ 22 23/* This file contains the low level primitives for operating on tree nodes, 24 including allocation, list operations, interning of identifiers, 25 construction of data type nodes and statement nodes, 26 and construction of type conversion nodes. It also contains 27 tables index by tree code that describe how to take apart 28 nodes of that code. 29 30 It is intended to be language-independent, but occasionally 31 calls language-dependent routines defined (for C) in typecheck.c. */ 32 33#include "config.h" 34#include "system.h" 35#include "coretypes.h" 36#include "tm.h" 37#include "flags.h" 38#include "tree.h" 39#include "real.h" 40#include "tm_p.h" 41#include "function.h" 42#include "obstack.h" 43#include "toplev.h" 44#include "ggc.h" 45#include "hashtab.h" 46#include "output.h" 47#include "target.h" 48#include "langhooks.h" 49#include "tree-iterator.h" 50#include "basic-block.h" 51#include "tree-flow.h" 52#include "params.h" 53#include "pointer-set.h" 54 55/* Each tree code class has an associated string representation. 56 These must correspond to the tree_code_class entries. */ 57 58const char *const tree_code_class_strings[] = 59{ 60 "exceptional", 61 "constant", 62 "type", 63 "declaration", 64 "reference", 65 "comparison", 66 "unary", 67 "binary", 68 "statement", 69 "expression", 70}; 71 72/* APPLE LOCAL begin 6353006 */ 73tree generic_block_literal_struct_type; 74/* APPLE LOCAL end 6353006 */ 75 76/* obstack.[ch] explicitly declined to prototype this. */ 77extern int _obstack_allocated_p (struct obstack *h, void *obj); 78 79#ifdef GATHER_STATISTICS 80/* Statistics-gathering stuff. */ 81 82int tree_node_counts[(int) all_kinds]; 83int tree_node_sizes[(int) all_kinds]; 84 85/* Keep in sync with tree.h:enum tree_node_kind. */ 86static const char * const tree_node_kind_names[] = { 87 "decls", 88 "types", 89 "blocks", 90 "stmts", 91 "refs", 92 "exprs", 93 "constants", 94 "identifiers", 95 "perm_tree_lists", 96 "temp_tree_lists", 97 "vecs", 98 "binfos", 99 "phi_nodes", 100 "ssa names", 101 "constructors", 102 "random kinds", 103 "lang_decl kinds", 104 "lang_type kinds", 105 "omp clauses" 106}; 107#endif /* GATHER_STATISTICS */ 108 109/* Unique id for next decl created. */ 110static GTY(()) int next_decl_uid; 111/* Unique id for next type created. */ 112static GTY(()) int next_type_uid = 1; 113 114/* Since we cannot rehash a type after it is in the table, we have to 115 keep the hash code. */ 116 117struct type_hash GTY(()) 118{ 119 unsigned long hash; 120 tree type; 121}; 122 123/* Initial size of the hash table (rounded to next prime). */ 124#define TYPE_HASH_INITIAL_SIZE 1000 125 126/* Now here is the hash table. When recording a type, it is added to 127 the slot whose index is the hash code. Note that the hash table is 128 used for several kinds of types (function types, array types and 129 array index range types, for now). While all these live in the 130 same table, they are completely independent, and the hash code is 131 computed differently for each of these. */ 132 133static GTY ((if_marked ("type_hash_marked_p"), param_is (struct type_hash))) 134 htab_t type_hash_table; 135 136/* Hash table and temporary node for larger integer const values. */ 137static GTY (()) tree int_cst_node; 138static GTY ((if_marked ("ggc_marked_p"), param_is (union tree_node))) 139 htab_t int_cst_hash_table; 140 141/* General tree->tree mapping structure for use in hash tables. */ 142 143 144static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map))) 145 htab_t debug_expr_for_decl; 146 147static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map))) 148 htab_t value_expr_for_decl; 149 150static GTY ((if_marked ("tree_int_map_marked_p"), param_is (struct tree_int_map))) 151 htab_t init_priority_for_decl; 152 153static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map))) 154 htab_t restrict_base_for_decl; 155 156struct tree_int_map GTY(()) 157{ 158 tree from; 159 unsigned short to; 160}; 161static unsigned int tree_int_map_hash (const void *); 162static int tree_int_map_eq (const void *, const void *); 163static int tree_int_map_marked_p (const void *); 164static void set_type_quals (tree, int); 165static int type_hash_eq (const void *, const void *); 166static hashval_t type_hash_hash (const void *); 167static hashval_t int_cst_hash_hash (const void *); 168static int int_cst_hash_eq (const void *, const void *); 169static void print_type_hash_statistics (void); 170static void print_debug_expr_statistics (void); 171static void print_value_expr_statistics (void); 172static int type_hash_marked_p (const void *); 173static unsigned int type_hash_list (tree, hashval_t); 174static unsigned int attribute_hash_list (tree, hashval_t); 175 176tree global_trees[TI_MAX]; 177tree integer_types[itk_none]; 178 179unsigned char tree_contains_struct[256][64]; 180 181/* Number of operands for each OpenMP clause. */ 182unsigned const char omp_clause_num_ops[] = 183{ 184 0, /* OMP_CLAUSE_ERROR */ 185 1, /* OMP_CLAUSE_PRIVATE */ 186 1, /* OMP_CLAUSE_SHARED */ 187 1, /* OMP_CLAUSE_FIRSTPRIVATE */ 188 1, /* OMP_CLAUSE_LASTPRIVATE */ 189 4, /* OMP_CLAUSE_REDUCTION */ 190 1, /* OMP_CLAUSE_COPYIN */ 191 1, /* OMP_CLAUSE_COPYPRIVATE */ 192 1, /* OMP_CLAUSE_IF */ 193 1, /* OMP_CLAUSE_NUM_THREADS */ 194 1, /* OMP_CLAUSE_SCHEDULE */ 195 0, /* OMP_CLAUSE_NOWAIT */ 196 0, /* OMP_CLAUSE_ORDERED */ 197 0 /* OMP_CLAUSE_DEFAULT */ 198}; 199 200const char * const omp_clause_code_name[] = 201{ 202 "error_clause", 203 "private", 204 "shared", 205 "firstprivate", 206 "lastprivate", 207 "reduction", 208 "copyin", 209 "copyprivate", 210 "if", 211 "num_threads", 212 "schedule", 213 "nowait", 214 "ordered", 215 "default" 216}; 217 218/* Init tree.c. */ 219 220void 221init_ttree (void) 222{ 223 /* Initialize the hash table of types. */ 224 type_hash_table = htab_create_ggc (TYPE_HASH_INITIAL_SIZE, type_hash_hash, 225 type_hash_eq, 0); 226 227 debug_expr_for_decl = htab_create_ggc (512, tree_map_hash, 228 tree_map_eq, 0); 229 230 value_expr_for_decl = htab_create_ggc (512, tree_map_hash, 231 tree_map_eq, 0); 232 init_priority_for_decl = htab_create_ggc (512, tree_int_map_hash, 233 tree_int_map_eq, 0); 234 restrict_base_for_decl = htab_create_ggc (256, tree_map_hash, 235 tree_map_eq, 0); 236 237 int_cst_hash_table = htab_create_ggc (1024, int_cst_hash_hash, 238 int_cst_hash_eq, NULL); 239 240 int_cst_node = make_node (INTEGER_CST); 241 242 tree_contains_struct[FUNCTION_DECL][TS_DECL_NON_COMMON] = 1; 243 tree_contains_struct[TRANSLATION_UNIT_DECL][TS_DECL_NON_COMMON] = 1; 244 tree_contains_struct[TYPE_DECL][TS_DECL_NON_COMMON] = 1; 245 246 247 tree_contains_struct[CONST_DECL][TS_DECL_COMMON] = 1; 248 tree_contains_struct[VAR_DECL][TS_DECL_COMMON] = 1; 249 tree_contains_struct[PARM_DECL][TS_DECL_COMMON] = 1; 250 tree_contains_struct[RESULT_DECL][TS_DECL_COMMON] = 1; 251 tree_contains_struct[FUNCTION_DECL][TS_DECL_COMMON] = 1; 252 tree_contains_struct[TYPE_DECL][TS_DECL_COMMON] = 1; 253 tree_contains_struct[TRANSLATION_UNIT_DECL][TS_DECL_COMMON] = 1; 254 tree_contains_struct[LABEL_DECL][TS_DECL_COMMON] = 1; 255 tree_contains_struct[FIELD_DECL][TS_DECL_COMMON] = 1; 256 257 258 tree_contains_struct[CONST_DECL][TS_DECL_WRTL] = 1; 259 tree_contains_struct[VAR_DECL][TS_DECL_WRTL] = 1; 260 tree_contains_struct[PARM_DECL][TS_DECL_WRTL] = 1; 261 tree_contains_struct[RESULT_DECL][TS_DECL_WRTL] = 1; 262 tree_contains_struct[FUNCTION_DECL][TS_DECL_WRTL] = 1; 263 tree_contains_struct[LABEL_DECL][TS_DECL_WRTL] = 1; 264 265 tree_contains_struct[CONST_DECL][TS_DECL_MINIMAL] = 1; 266 tree_contains_struct[VAR_DECL][TS_DECL_MINIMAL] = 1; 267 tree_contains_struct[PARM_DECL][TS_DECL_MINIMAL] = 1; 268 tree_contains_struct[RESULT_DECL][TS_DECL_MINIMAL] = 1; 269 tree_contains_struct[FUNCTION_DECL][TS_DECL_MINIMAL] = 1; 270 tree_contains_struct[TYPE_DECL][TS_DECL_MINIMAL] = 1; 271 tree_contains_struct[TRANSLATION_UNIT_DECL][TS_DECL_MINIMAL] = 1; 272 tree_contains_struct[LABEL_DECL][TS_DECL_MINIMAL] = 1; 273 tree_contains_struct[FIELD_DECL][TS_DECL_MINIMAL] = 1; 274 tree_contains_struct[STRUCT_FIELD_TAG][TS_DECL_MINIMAL] = 1; 275 tree_contains_struct[NAME_MEMORY_TAG][TS_DECL_MINIMAL] = 1; 276 tree_contains_struct[SYMBOL_MEMORY_TAG][TS_DECL_MINIMAL] = 1; 277 278 tree_contains_struct[STRUCT_FIELD_TAG][TS_MEMORY_TAG] = 1; 279 tree_contains_struct[NAME_MEMORY_TAG][TS_MEMORY_TAG] = 1; 280 tree_contains_struct[SYMBOL_MEMORY_TAG][TS_MEMORY_TAG] = 1; 281 282 tree_contains_struct[STRUCT_FIELD_TAG][TS_STRUCT_FIELD_TAG] = 1; 283 284 tree_contains_struct[VAR_DECL][TS_DECL_WITH_VIS] = 1; 285 tree_contains_struct[FUNCTION_DECL][TS_DECL_WITH_VIS] = 1; 286 tree_contains_struct[TYPE_DECL][TS_DECL_WITH_VIS] = 1; 287 tree_contains_struct[TRANSLATION_UNIT_DECL][TS_DECL_WITH_VIS] = 1; 288 289 tree_contains_struct[VAR_DECL][TS_VAR_DECL] = 1; 290 tree_contains_struct[FIELD_DECL][TS_FIELD_DECL] = 1; 291 tree_contains_struct[PARM_DECL][TS_PARM_DECL] = 1; 292 tree_contains_struct[LABEL_DECL][TS_LABEL_DECL] = 1; 293 tree_contains_struct[RESULT_DECL][TS_RESULT_DECL] = 1; 294 tree_contains_struct[CONST_DECL][TS_CONST_DECL] = 1; 295 tree_contains_struct[TYPE_DECL][TS_TYPE_DECL] = 1; 296 tree_contains_struct[FUNCTION_DECL][TS_FUNCTION_DECL] = 1; 297 298 lang_hooks.init_ts (); 299} 300 301 302/* The name of the object as the assembler will see it (but before any 303 translations made by ASM_OUTPUT_LABELREF). Often this is the same 304 as DECL_NAME. It is an IDENTIFIER_NODE. */ 305tree 306decl_assembler_name (tree decl) 307{ 308 if (!DECL_ASSEMBLER_NAME_SET_P (decl)) 309 lang_hooks.set_decl_assembler_name (decl); 310 return DECL_WITH_VIS_CHECK (decl)->decl_with_vis.assembler_name; 311} 312 313/* Compute the number of bytes occupied by a tree with code CODE. 314 This function cannot be used for TREE_VEC, PHI_NODE, or STRING_CST 315 codes, which are of variable length. */ 316size_t 317tree_code_size (enum tree_code code) 318{ 319 switch (TREE_CODE_CLASS (code)) 320 { 321 case tcc_declaration: /* A decl node */ 322 { 323 switch (code) 324 { 325 case FIELD_DECL: 326 return sizeof (struct tree_field_decl); 327 case PARM_DECL: 328 return sizeof (struct tree_parm_decl); 329 case VAR_DECL: 330 return sizeof (struct tree_var_decl); 331 case LABEL_DECL: 332 return sizeof (struct tree_label_decl); 333 case RESULT_DECL: 334 return sizeof (struct tree_result_decl); 335 case CONST_DECL: 336 return sizeof (struct tree_const_decl); 337 case TYPE_DECL: 338 return sizeof (struct tree_type_decl); 339 case FUNCTION_DECL: 340 return sizeof (struct tree_function_decl); 341 case NAME_MEMORY_TAG: 342 case SYMBOL_MEMORY_TAG: 343 return sizeof (struct tree_memory_tag); 344 case STRUCT_FIELD_TAG: 345 return sizeof (struct tree_struct_field_tag); 346 default: 347 return sizeof (struct tree_decl_non_common); 348 } 349 } 350 351 case tcc_type: /* a type node */ 352 return sizeof (struct tree_type); 353 354 case tcc_reference: /* a reference */ 355 case tcc_expression: /* an expression */ 356 case tcc_statement: /* an expression with side effects */ 357 case tcc_comparison: /* a comparison expression */ 358 case tcc_unary: /* a unary arithmetic expression */ 359 case tcc_binary: /* a binary arithmetic expression */ 360 return (sizeof (struct tree_exp) 361 + (TREE_CODE_LENGTH (code) - 1) * sizeof (char *)); 362 363 case tcc_constant: /* a constant */ 364 switch (code) 365 { 366 case INTEGER_CST: return sizeof (struct tree_int_cst); 367 case REAL_CST: return sizeof (struct tree_real_cst); 368 case COMPLEX_CST: return sizeof (struct tree_complex); 369 case VECTOR_CST: return sizeof (struct tree_vector); 370 case STRING_CST: gcc_unreachable (); 371 default: 372 return lang_hooks.tree_size (code); 373 } 374 375 case tcc_exceptional: /* something random, like an identifier. */ 376 switch (code) 377 { 378 case IDENTIFIER_NODE: return lang_hooks.identifier_size; 379 case TREE_LIST: return sizeof (struct tree_list); 380 381 case ERROR_MARK: 382 case PLACEHOLDER_EXPR: return sizeof (struct tree_common); 383 384 case TREE_VEC: 385 case OMP_CLAUSE: 386 case PHI_NODE: gcc_unreachable (); 387 388 case SSA_NAME: return sizeof (struct tree_ssa_name); 389 390 case STATEMENT_LIST: return sizeof (struct tree_statement_list); 391 case BLOCK: return sizeof (struct tree_block); 392 case VALUE_HANDLE: return sizeof (struct tree_value_handle); 393 case CONSTRUCTOR: return sizeof (struct tree_constructor); 394 395 default: 396 return lang_hooks.tree_size (code); 397 } 398 399 default: 400 gcc_unreachable (); 401 } 402} 403 404/* Compute the number of bytes occupied by NODE. This routine only 405 looks at TREE_CODE, except for PHI_NODE and TREE_VEC nodes. */ 406size_t 407tree_size (tree node) 408{ 409 enum tree_code code = TREE_CODE (node); 410 switch (code) 411 { 412 case PHI_NODE: 413 return (sizeof (struct tree_phi_node) 414 + (PHI_ARG_CAPACITY (node) - 1) * sizeof (struct phi_arg_d)); 415 416 case TREE_BINFO: 417 return (offsetof (struct tree_binfo, base_binfos) 418 + VEC_embedded_size (tree, BINFO_N_BASE_BINFOS (node))); 419 420 case TREE_VEC: 421 return (sizeof (struct tree_vec) 422 + (TREE_VEC_LENGTH (node) - 1) * sizeof(char *)); 423 424 case STRING_CST: 425 return TREE_STRING_LENGTH (node) + offsetof (struct tree_string, str) + 1; 426 427 case OMP_CLAUSE: 428 return (sizeof (struct tree_omp_clause) 429 + (omp_clause_num_ops[OMP_CLAUSE_CODE (node)] - 1) 430 * sizeof (tree)); 431 432 default: 433 return tree_code_size (code); 434 } 435} 436 437/* Return a newly allocated node of code CODE. For decl and type 438 nodes, some other fields are initialized. The rest of the node is 439 initialized to zero. This function cannot be used for PHI_NODE, 440 TREE_VEC or OMP_CLAUSE nodes, which is enforced by asserts in 441 tree_code_size. 442 443 Achoo! I got a code in the node. */ 444 445tree 446make_node_stat (enum tree_code code MEM_STAT_DECL) 447{ 448 tree t; 449 enum tree_code_class type = TREE_CODE_CLASS (code); 450 size_t length = tree_code_size (code); 451#ifdef GATHER_STATISTICS 452 tree_node_kind kind; 453 454 switch (type) 455 { 456 case tcc_declaration: /* A decl node */ 457 kind = d_kind; 458 break; 459 460 case tcc_type: /* a type node */ 461 kind = t_kind; 462 break; 463 464 case tcc_statement: /* an expression with side effects */ 465 kind = s_kind; 466 break; 467 468 case tcc_reference: /* a reference */ 469 kind = r_kind; 470 break; 471 472 case tcc_expression: /* an expression */ 473 case tcc_comparison: /* a comparison expression */ 474 case tcc_unary: /* a unary arithmetic expression */ 475 case tcc_binary: /* a binary arithmetic expression */ 476 kind = e_kind; 477 break; 478 479 case tcc_constant: /* a constant */ 480 kind = c_kind; 481 break; 482 483 case tcc_exceptional: /* something random, like an identifier. */ 484 switch (code) 485 { 486 case IDENTIFIER_NODE: 487 kind = id_kind; 488 break; 489 490 case TREE_VEC: 491 kind = vec_kind; 492 break; 493 494 case TREE_BINFO: 495 kind = binfo_kind; 496 break; 497 498 case PHI_NODE: 499 kind = phi_kind; 500 break; 501 502 case SSA_NAME: 503 kind = ssa_name_kind; 504 break; 505 506 case BLOCK: 507 kind = b_kind; 508 break; 509 510 case CONSTRUCTOR: 511 kind = constr_kind; 512 break; 513 514 default: 515 kind = x_kind; 516 break; 517 } 518 break; 519 520 default: 521 gcc_unreachable (); 522 } 523 524 tree_node_counts[(int) kind]++; 525 tree_node_sizes[(int) kind] += length; 526#endif 527 528 if (code == IDENTIFIER_NODE) 529 t = ggc_alloc_zone_pass_stat (length, &tree_id_zone); 530 else 531 t = ggc_alloc_zone_pass_stat (length, &tree_zone); 532 533 memset (t, 0, length); 534 535 TREE_SET_CODE (t, code); 536 537 switch (type) 538 { 539 case tcc_statement: 540 TREE_SIDE_EFFECTS (t) = 1; 541 break; 542 543 case tcc_declaration: 544 if (CODE_CONTAINS_STRUCT (code, TS_DECL_WITH_VIS)) 545 DECL_IN_SYSTEM_HEADER (t) = in_system_header; 546 if (CODE_CONTAINS_STRUCT (code, TS_DECL_COMMON)) 547 { 548 if (code == FUNCTION_DECL) 549 { 550 DECL_ALIGN (t) = FUNCTION_BOUNDARY; 551 DECL_MODE (t) = FUNCTION_MODE; 552 } 553 else 554 DECL_ALIGN (t) = 1; 555 /* We have not yet computed the alias set for this declaration. */ 556 DECL_POINTER_ALIAS_SET (t) = -1; 557 } 558 DECL_SOURCE_LOCATION (t) = input_location; 559 DECL_UID (t) = next_decl_uid++; 560 561 break; 562 563 case tcc_type: 564 TYPE_UID (t) = next_type_uid++; 565 TYPE_ALIGN (t) = BITS_PER_UNIT; 566 TYPE_USER_ALIGN (t) = 0; 567 TYPE_MAIN_VARIANT (t) = t; 568 569 /* Default to no attributes for type, but let target change that. */ 570 TYPE_ATTRIBUTES (t) = NULL_TREE; 571 targetm.set_default_type_attributes (t); 572 573 /* We have not yet computed the alias set for this type. */ 574 TYPE_ALIAS_SET (t) = -1; 575 break; 576 577 case tcc_constant: 578 TREE_CONSTANT (t) = 1; 579 TREE_INVARIANT (t) = 1; 580 break; 581 582 case tcc_expression: 583 switch (code) 584 { 585 case INIT_EXPR: 586 case MODIFY_EXPR: 587 case VA_ARG_EXPR: 588 case PREDECREMENT_EXPR: 589 case PREINCREMENT_EXPR: 590 case POSTDECREMENT_EXPR: 591 case POSTINCREMENT_EXPR: 592 /* All of these have side-effects, no matter what their 593 operands are. */ 594 TREE_SIDE_EFFECTS (t) = 1; 595 break; 596 597 default: 598 break; 599 } 600 break; 601 602 default: 603 /* Other classes need no special treatment. */ 604 break; 605 } 606 607 return t; 608} 609 610/* Return a new node with the same contents as NODE except that its 611 TREE_CHAIN is zero and it has a fresh uid. */ 612 613tree 614copy_node_stat (tree node MEM_STAT_DECL) 615{ 616 tree t; 617 enum tree_code code = TREE_CODE (node); 618 size_t length; 619 620 gcc_assert (code != STATEMENT_LIST); 621 622 length = tree_size (node); 623 t = ggc_alloc_zone_pass_stat (length, &tree_zone); 624 memcpy (t, node, length); 625 626 TREE_CHAIN (t) = 0; 627 TREE_ASM_WRITTEN (t) = 0; 628 TREE_VISITED (t) = 0; 629 t->common.ann = 0; 630 631 if (TREE_CODE_CLASS (code) == tcc_declaration) 632 { 633 DECL_UID (t) = next_decl_uid++; 634 if ((TREE_CODE (node) == PARM_DECL || TREE_CODE (node) == VAR_DECL) 635 && DECL_HAS_VALUE_EXPR_P (node)) 636 { 637 SET_DECL_VALUE_EXPR (t, DECL_VALUE_EXPR (node)); 638 DECL_HAS_VALUE_EXPR_P (t) = 1; 639 } 640 if (TREE_CODE (node) == VAR_DECL && DECL_HAS_INIT_PRIORITY_P (node)) 641 { 642 SET_DECL_INIT_PRIORITY (t, DECL_INIT_PRIORITY (node)); 643 DECL_HAS_INIT_PRIORITY_P (t) = 1; 644 } 645 if (TREE_CODE (node) == VAR_DECL && DECL_BASED_ON_RESTRICT_P (node)) 646 { 647 SET_DECL_RESTRICT_BASE (t, DECL_GET_RESTRICT_BASE (node)); 648 DECL_BASED_ON_RESTRICT_P (t) = 1; 649 } 650 } 651 else if (TREE_CODE_CLASS (code) == tcc_type) 652 { 653 TYPE_UID (t) = next_type_uid++; 654 /* The following is so that the debug code for 655 the copy is different from the original type. 656 The two statements usually duplicate each other 657 (because they clear fields of the same union), 658 but the optimizer should catch that. */ 659 TYPE_SYMTAB_POINTER (t) = 0; 660 TYPE_SYMTAB_ADDRESS (t) = 0; 661 662 /* Do not copy the values cache. */ 663 if (TYPE_CACHED_VALUES_P(t)) 664 { 665 TYPE_CACHED_VALUES_P (t) = 0; 666 TYPE_CACHED_VALUES (t) = NULL_TREE; 667 } 668 } 669 670 return t; 671} 672 673/* Return a copy of a chain of nodes, chained through the TREE_CHAIN field. 674 For example, this can copy a list made of TREE_LIST nodes. */ 675 676tree 677copy_list (tree list) 678{ 679 tree head; 680 tree prev, next; 681 682 if (list == 0) 683 return 0; 684 685 head = prev = copy_node (list); 686 next = TREE_CHAIN (list); 687 while (next) 688 { 689 TREE_CHAIN (prev) = copy_node (next); 690 prev = TREE_CHAIN (prev); 691 next = TREE_CHAIN (next); 692 } 693 return head; 694} 695 696 697/* Create an INT_CST node with a LOW value sign extended. */ 698 699tree 700build_int_cst (tree type, HOST_WIDE_INT low) 701{ 702 return build_int_cst_wide (type, low, low < 0 ? -1 : 0); 703} 704 705/* Create an INT_CST node with a LOW value zero extended. */ 706 707tree 708build_int_cstu (tree type, unsigned HOST_WIDE_INT low) 709{ 710 return build_int_cst_wide (type, low, 0); 711} 712 713/* Create an INT_CST node with a LOW value in TYPE. The value is sign extended 714 if it is negative. This function is similar to build_int_cst, but 715 the extra bits outside of the type precision are cleared. Constants 716 with these extra bits may confuse the fold so that it detects overflows 717 even in cases when they do not occur, and in general should be avoided. 718 We cannot however make this a default behavior of build_int_cst without 719 more intrusive changes, since there are parts of gcc that rely on the extra 720 precision of the integer constants. */ 721 722tree 723build_int_cst_type (tree type, HOST_WIDE_INT low) 724{ 725 unsigned HOST_WIDE_INT val = (unsigned HOST_WIDE_INT) low; 726 unsigned HOST_WIDE_INT hi, mask; 727 unsigned bits; 728 bool signed_p; 729 bool negative; 730 731 if (!type) 732 type = integer_type_node; 733 734 bits = TYPE_PRECISION (type); 735 signed_p = !TYPE_UNSIGNED (type); 736 737 if (bits >= HOST_BITS_PER_WIDE_INT) 738 negative = (low < 0); 739 else 740 { 741 /* If the sign bit is inside precision of LOW, use it to determine 742 the sign of the constant. */ 743 negative = ((val >> (bits - 1)) & 1) != 0; 744 745 /* Mask out the bits outside of the precision of the constant. */ 746 mask = (((unsigned HOST_WIDE_INT) 2) << (bits - 1)) - 1; 747 748 if (signed_p && negative) 749 val |= ~mask; 750 else 751 val &= mask; 752 } 753 754 /* Determine the high bits. */ 755 hi = (negative ? ~(unsigned HOST_WIDE_INT) 0 : 0); 756 757 /* For unsigned type we need to mask out the bits outside of the type 758 precision. */ 759 if (!signed_p) 760 { 761 if (bits <= HOST_BITS_PER_WIDE_INT) 762 hi = 0; 763 else 764 { 765 bits -= HOST_BITS_PER_WIDE_INT; 766 mask = (((unsigned HOST_WIDE_INT) 2) << (bits - 1)) - 1; 767 hi &= mask; 768 } 769 } 770 771 return build_int_cst_wide (type, val, hi); 772} 773 774/* These are the hash table functions for the hash table of INTEGER_CST 775 nodes of a sizetype. */ 776 777/* Return the hash code code X, an INTEGER_CST. */ 778 779static hashval_t 780int_cst_hash_hash (const void *x) 781{ 782 tree t = (tree) x; 783 784 return (TREE_INT_CST_HIGH (t) ^ TREE_INT_CST_LOW (t) 785 ^ htab_hash_pointer (TREE_TYPE (t))); 786} 787 788/* Return nonzero if the value represented by *X (an INTEGER_CST tree node) 789 is the same as that given by *Y, which is the same. */ 790 791static int 792int_cst_hash_eq (const void *x, const void *y) 793{ 794 tree xt = (tree) x; 795 tree yt = (tree) y; 796 797 return (TREE_TYPE (xt) == TREE_TYPE (yt) 798 && TREE_INT_CST_HIGH (xt) == TREE_INT_CST_HIGH (yt) 799 && TREE_INT_CST_LOW (xt) == TREE_INT_CST_LOW (yt)); 800} 801 802/* Create an INT_CST node of TYPE and value HI:LOW. If TYPE is NULL, 803 integer_type_node is used. The returned node is always shared. 804 For small integers we use a per-type vector cache, for larger ones 805 we use a single hash table. */ 806 807tree 808build_int_cst_wide (tree type, unsigned HOST_WIDE_INT low, HOST_WIDE_INT hi) 809{ 810 tree t; 811 int ix = -1; 812 int limit = 0; 813 814 if (!type) 815 type = integer_type_node; 816 817 switch (TREE_CODE (type)) 818 { 819 case POINTER_TYPE: 820 case REFERENCE_TYPE: 821 /* Cache NULL pointer. */ 822 if (!hi && !low) 823 { 824 limit = 1; 825 ix = 0; 826 } 827 break; 828 829 case BOOLEAN_TYPE: 830 /* Cache false or true. */ 831 limit = 2; 832 if (!hi && low < 2) 833 ix = low; 834 break; 835 836 case INTEGER_TYPE: 837 case OFFSET_TYPE: 838 if (TYPE_UNSIGNED (type)) 839 { 840 /* Cache 0..N */ 841 limit = INTEGER_SHARE_LIMIT; 842 if (!hi && low < (unsigned HOST_WIDE_INT)INTEGER_SHARE_LIMIT) 843 ix = low; 844 } 845 else 846 { 847 /* Cache -1..N */ 848 limit = INTEGER_SHARE_LIMIT + 1; 849 if (!hi && low < (unsigned HOST_WIDE_INT)INTEGER_SHARE_LIMIT) 850 ix = low + 1; 851 else if (hi == -1 && low == -(unsigned HOST_WIDE_INT)1) 852 ix = 0; 853 } 854 break; 855 default: 856 break; 857 } 858 859 if (ix >= 0) 860 { 861 /* Look for it in the type's vector of small shared ints. */ 862 if (!TYPE_CACHED_VALUES_P (type)) 863 { 864 TYPE_CACHED_VALUES_P (type) = 1; 865 TYPE_CACHED_VALUES (type) = make_tree_vec (limit); 866 } 867 868 t = TREE_VEC_ELT (TYPE_CACHED_VALUES (type), ix); 869 if (t) 870 { 871 /* Make sure no one is clobbering the shared constant. */ 872 gcc_assert (TREE_TYPE (t) == type); 873 gcc_assert (TREE_INT_CST_LOW (t) == low); 874 gcc_assert (TREE_INT_CST_HIGH (t) == hi); 875 } 876 else 877 { 878 /* Create a new shared int. */ 879 t = make_node (INTEGER_CST); 880 881 TREE_INT_CST_LOW (t) = low; 882 TREE_INT_CST_HIGH (t) = hi; 883 TREE_TYPE (t) = type; 884 885 TREE_VEC_ELT (TYPE_CACHED_VALUES (type), ix) = t; 886 } 887 } 888 else 889 { 890 /* Use the cache of larger shared ints. */ 891 void **slot; 892 893 TREE_INT_CST_LOW (int_cst_node) = low; 894 TREE_INT_CST_HIGH (int_cst_node) = hi; 895 TREE_TYPE (int_cst_node) = type; 896 897 slot = htab_find_slot (int_cst_hash_table, int_cst_node, INSERT); 898 t = *slot; 899 if (!t) 900 { 901 /* Insert this one into the hash table. */ 902 t = int_cst_node; 903 *slot = t; 904 /* Make a new node for next time round. */ 905 int_cst_node = make_node (INTEGER_CST); 906 } 907 } 908 909 return t; 910} 911 912/* Builds an integer constant in TYPE such that lowest BITS bits are ones 913 and the rest are zeros. */ 914 915tree 916build_low_bits_mask (tree type, unsigned bits) 917{ 918 unsigned HOST_WIDE_INT low; 919 HOST_WIDE_INT high; 920 unsigned HOST_WIDE_INT all_ones = ~(unsigned HOST_WIDE_INT) 0; 921 922 gcc_assert (bits <= TYPE_PRECISION (type)); 923 924 if (bits == TYPE_PRECISION (type) 925 && !TYPE_UNSIGNED (type)) 926 { 927 /* Sign extended all-ones mask. */ 928 low = all_ones; 929 high = -1; 930 } 931 else if (bits <= HOST_BITS_PER_WIDE_INT) 932 { 933 low = all_ones >> (HOST_BITS_PER_WIDE_INT - bits); 934 high = 0; 935 } 936 else 937 { 938 bits -= HOST_BITS_PER_WIDE_INT; 939 low = all_ones; 940 high = all_ones >> (HOST_BITS_PER_WIDE_INT - bits); 941 } 942 943 return build_int_cst_wide (type, low, high); 944} 945 946/* Checks that X is integer constant that can be expressed in (unsigned) 947 HOST_WIDE_INT without loss of precision. */ 948 949bool 950cst_and_fits_in_hwi (tree x) 951{ 952 if (TREE_CODE (x) != INTEGER_CST) 953 return false; 954 955 if (TYPE_PRECISION (TREE_TYPE (x)) > HOST_BITS_PER_WIDE_INT) 956 return false; 957 958 return (TREE_INT_CST_HIGH (x) == 0 959 || TREE_INT_CST_HIGH (x) == -1); 960} 961 962/* Return a new VECTOR_CST node whose type is TYPE and whose values 963 are in a list pointed to by VALS. */ 964 965tree 966build_vector (tree type, tree vals) 967{ 968 tree v = make_node (VECTOR_CST); 969 int over1 = 0, over2 = 0; 970 tree link; 971 972 TREE_VECTOR_CST_ELTS (v) = vals; 973 TREE_TYPE (v) = type; 974 975 /* Iterate through elements and check for overflow. */ 976 for (link = vals; link; link = TREE_CHAIN (link)) 977 { 978 tree value = TREE_VALUE (link); 979 980 /* Don't crash if we get an address constant. */ 981 if (!CONSTANT_CLASS_P (value)) 982 continue; 983 984 over1 |= TREE_OVERFLOW (value); 985 over2 |= TREE_CONSTANT_OVERFLOW (value); 986 } 987 988 TREE_OVERFLOW (v) = over1; 989 TREE_CONSTANT_OVERFLOW (v) = over2; 990 991 return v; 992} 993 994/* Return a new VECTOR_CST node whose type is TYPE and whose values 995 are extracted from V, a vector of CONSTRUCTOR_ELT. */ 996 997tree 998build_vector_from_ctor (tree type, VEC(constructor_elt,gc) *v) 999{ 1000 tree list = NULL_TREE; 1001 unsigned HOST_WIDE_INT idx; 1002 tree value; 1003 1004 FOR_EACH_CONSTRUCTOR_VALUE (v, idx, value) 1005 list = tree_cons (NULL_TREE, value, list); 1006 return build_vector (type, nreverse (list)); 1007} 1008 1009/* Return a new CONSTRUCTOR node whose type is TYPE and whose values 1010 are in the VEC pointed to by VALS. */ 1011tree 1012build_constructor (tree type, VEC(constructor_elt,gc) *vals) 1013{ 1014 tree c = make_node (CONSTRUCTOR); 1015 TREE_TYPE (c) = type; 1016 CONSTRUCTOR_ELTS (c) = vals; 1017 return c; 1018} 1019 1020/* Build a CONSTRUCTOR node made of a single initializer, with the specified 1021 INDEX and VALUE. */ 1022tree 1023build_constructor_single (tree type, tree index, tree value) 1024{ 1025 VEC(constructor_elt,gc) *v; 1026 constructor_elt *elt; 1027 tree t; 1028 1029 v = VEC_alloc (constructor_elt, gc, 1); 1030 elt = VEC_quick_push (constructor_elt, v, NULL); 1031 elt->index = index; 1032 elt->value = value; 1033 1034 t = build_constructor (type, v); 1035 TREE_CONSTANT (t) = TREE_CONSTANT (value); 1036 return t; 1037} 1038 1039 1040/* Return a new CONSTRUCTOR node whose type is TYPE and whose values 1041 are in a list pointed to by VALS. */ 1042tree 1043build_constructor_from_list (tree type, tree vals) 1044{ 1045 tree t, val; 1046 VEC(constructor_elt,gc) *v = NULL; 1047 bool constant_p = true; 1048 1049 if (vals) 1050 { 1051 v = VEC_alloc (constructor_elt, gc, list_length (vals)); 1052 for (t = vals; t; t = TREE_CHAIN (t)) 1053 { 1054 constructor_elt *elt = VEC_quick_push (constructor_elt, v, NULL); 1055 val = TREE_VALUE (t); 1056 elt->index = TREE_PURPOSE (t); 1057 elt->value = val; 1058 if (!TREE_CONSTANT (val)) 1059 constant_p = false; 1060 } 1061 } 1062 1063 t = build_constructor (type, v); 1064 TREE_CONSTANT (t) = constant_p; 1065 return t; 1066} 1067 1068 1069/* Return a new REAL_CST node whose type is TYPE and value is D. */ 1070 1071tree 1072build_real (tree type, REAL_VALUE_TYPE d) 1073{ 1074 tree v; 1075 REAL_VALUE_TYPE *dp; 1076 int overflow = 0; 1077 1078 /* ??? Used to check for overflow here via CHECK_FLOAT_TYPE. 1079 Consider doing it via real_convert now. */ 1080 1081 v = make_node (REAL_CST); 1082 dp = ggc_alloc (sizeof (REAL_VALUE_TYPE)); 1083 memcpy (dp, &d, sizeof (REAL_VALUE_TYPE)); 1084 1085 TREE_TYPE (v) = type; 1086 TREE_REAL_CST_PTR (v) = dp; 1087 TREE_OVERFLOW (v) = TREE_CONSTANT_OVERFLOW (v) = overflow; 1088 return v; 1089} 1090 1091/* Return a new REAL_CST node whose type is TYPE 1092 and whose value is the integer value of the INTEGER_CST node I. */ 1093 1094REAL_VALUE_TYPE 1095real_value_from_int_cst (tree type, tree i) 1096{ 1097 REAL_VALUE_TYPE d; 1098 1099 /* Clear all bits of the real value type so that we can later do 1100 bitwise comparisons to see if two values are the same. */ 1101 memset (&d, 0, sizeof d); 1102 1103 real_from_integer (&d, type ? TYPE_MODE (type) : VOIDmode, 1104 TREE_INT_CST_LOW (i), TREE_INT_CST_HIGH (i), 1105 TYPE_UNSIGNED (TREE_TYPE (i))); 1106 return d; 1107} 1108 1109/* Given a tree representing an integer constant I, return a tree 1110 representing the same value as a floating-point constant of type TYPE. */ 1111 1112tree 1113build_real_from_int_cst (tree type, tree i) 1114{ 1115 tree v; 1116 int overflow = TREE_OVERFLOW (i); 1117 1118 v = build_real (type, real_value_from_int_cst (type, i)); 1119 1120 TREE_OVERFLOW (v) |= overflow; 1121 TREE_CONSTANT_OVERFLOW (v) |= overflow; 1122 return v; 1123} 1124 1125/* Return a newly constructed STRING_CST node whose value is 1126 the LEN characters at STR. 1127 The TREE_TYPE is not initialized. */ 1128 1129tree 1130build_string (int len, const char *str) 1131{ 1132 tree s; 1133 size_t length; 1134 1135 /* Do not waste bytes provided by padding of struct tree_string. */ 1136 length = len + offsetof (struct tree_string, str) + 1; 1137 1138#ifdef GATHER_STATISTICS 1139 tree_node_counts[(int) c_kind]++; 1140 tree_node_sizes[(int) c_kind] += length; 1141#endif 1142 1143 s = ggc_alloc_tree (length); 1144 1145 memset (s, 0, sizeof (struct tree_common)); 1146 TREE_SET_CODE (s, STRING_CST); 1147 TREE_CONSTANT (s) = 1; 1148 TREE_INVARIANT (s) = 1; 1149 TREE_STRING_LENGTH (s) = len; 1150 memcpy ((char *) TREE_STRING_POINTER (s), str, len); 1151 ((char *) TREE_STRING_POINTER (s))[len] = '\0'; 1152 1153 return s; 1154} 1155 1156/* Return a newly constructed COMPLEX_CST node whose value is 1157 specified by the real and imaginary parts REAL and IMAG. 1158 Both REAL and IMAG should be constant nodes. TYPE, if specified, 1159 will be the type of the COMPLEX_CST; otherwise a new type will be made. */ 1160 1161tree 1162build_complex (tree type, tree real, tree imag) 1163{ 1164 tree t = make_node (COMPLEX_CST); 1165 1166 TREE_REALPART (t) = real; 1167 TREE_IMAGPART (t) = imag; 1168 TREE_TYPE (t) = type ? type : build_complex_type (TREE_TYPE (real)); 1169 TREE_OVERFLOW (t) = TREE_OVERFLOW (real) | TREE_OVERFLOW (imag); 1170 TREE_CONSTANT_OVERFLOW (t) 1171 = TREE_CONSTANT_OVERFLOW (real) | TREE_CONSTANT_OVERFLOW (imag); 1172 return t; 1173} 1174 1175/* Return a constant of arithmetic type TYPE which is the 1176 multiplicative identity of the set TYPE. */ 1177 1178tree 1179build_one_cst (tree type) 1180{ 1181 switch (TREE_CODE (type)) 1182 { 1183 case INTEGER_TYPE: case ENUMERAL_TYPE: case BOOLEAN_TYPE: 1184 case POINTER_TYPE: case REFERENCE_TYPE: 1185 case OFFSET_TYPE: 1186 return build_int_cst (type, 1); 1187 1188 case REAL_TYPE: 1189 return build_real (type, dconst1); 1190 1191 case VECTOR_TYPE: 1192 { 1193 tree scalar, cst; 1194 int i; 1195 1196 scalar = build_one_cst (TREE_TYPE (type)); 1197 1198 /* Create 'vect_cst_ = {cst,cst,...,cst}' */ 1199 cst = NULL_TREE; 1200 for (i = TYPE_VECTOR_SUBPARTS (type); --i >= 0; ) 1201 cst = tree_cons (NULL_TREE, scalar, cst); 1202 1203 return build_vector (type, cst); 1204 } 1205 1206 case COMPLEX_TYPE: 1207 return build_complex (type, 1208 build_one_cst (TREE_TYPE (type)), 1209 fold_convert (TREE_TYPE (type), integer_zero_node)); 1210 1211 default: 1212 gcc_unreachable (); 1213 } 1214} 1215 1216/* Build a BINFO with LEN language slots. */ 1217 1218tree 1219make_tree_binfo_stat (unsigned base_binfos MEM_STAT_DECL) 1220{ 1221 tree t; 1222 size_t length = (offsetof (struct tree_binfo, base_binfos) 1223 + VEC_embedded_size (tree, base_binfos)); 1224 1225#ifdef GATHER_STATISTICS 1226 tree_node_counts[(int) binfo_kind]++; 1227 tree_node_sizes[(int) binfo_kind] += length; 1228#endif 1229 1230 t = ggc_alloc_zone_pass_stat (length, &tree_zone); 1231 1232 memset (t, 0, offsetof (struct tree_binfo, base_binfos)); 1233 1234 TREE_SET_CODE (t, TREE_BINFO); 1235 1236 VEC_embedded_init (tree, BINFO_BASE_BINFOS (t), base_binfos); 1237 1238 return t; 1239} 1240 1241 1242/* Build a newly constructed TREE_VEC node of length LEN. */ 1243 1244tree 1245make_tree_vec_stat (int len MEM_STAT_DECL) 1246{ 1247 tree t; 1248 int length = (len - 1) * sizeof (tree) + sizeof (struct tree_vec); 1249 1250#ifdef GATHER_STATISTICS 1251 tree_node_counts[(int) vec_kind]++; 1252 tree_node_sizes[(int) vec_kind] += length; 1253#endif 1254 1255 t = ggc_alloc_zone_pass_stat (length, &tree_zone); 1256 1257 memset (t, 0, length); 1258 1259 TREE_SET_CODE (t, TREE_VEC); 1260 TREE_VEC_LENGTH (t) = len; 1261 1262 return t; 1263} 1264 1265/* Return 1 if EXPR is the integer constant zero or a complex constant 1266 of zero. */ 1267 1268int 1269integer_zerop (tree expr) 1270{ 1271 STRIP_NOPS (expr); 1272 1273 return ((TREE_CODE (expr) == INTEGER_CST 1274 && TREE_INT_CST_LOW (expr) == 0 1275 && TREE_INT_CST_HIGH (expr) == 0) 1276 || (TREE_CODE (expr) == COMPLEX_CST 1277 && integer_zerop (TREE_REALPART (expr)) 1278 && integer_zerop (TREE_IMAGPART (expr)))); 1279} 1280 1281/* Return 1 if EXPR is the integer constant one or the corresponding 1282 complex constant. */ 1283 1284int 1285integer_onep (tree expr) 1286{ 1287 STRIP_NOPS (expr); 1288 1289 return ((TREE_CODE (expr) == INTEGER_CST 1290 && TREE_INT_CST_LOW (expr) == 1 1291 && TREE_INT_CST_HIGH (expr) == 0) 1292 || (TREE_CODE (expr) == COMPLEX_CST 1293 && integer_onep (TREE_REALPART (expr)) 1294 && integer_zerop (TREE_IMAGPART (expr)))); 1295} 1296 1297/* Return 1 if EXPR is an integer containing all 1's in as much precision as 1298 it contains. Likewise for the corresponding complex constant. */ 1299 1300int 1301integer_all_onesp (tree expr) 1302{ 1303 int prec; 1304 int uns; 1305 1306 STRIP_NOPS (expr); 1307 1308 if (TREE_CODE (expr) == COMPLEX_CST 1309 && integer_all_onesp (TREE_REALPART (expr)) 1310 && integer_zerop (TREE_IMAGPART (expr))) 1311 return 1; 1312 1313 else if (TREE_CODE (expr) != INTEGER_CST) 1314 return 0; 1315 1316 uns = TYPE_UNSIGNED (TREE_TYPE (expr)); 1317 if (TREE_INT_CST_LOW (expr) == ~(unsigned HOST_WIDE_INT) 0 1318 && TREE_INT_CST_HIGH (expr) == -1) 1319 return 1; 1320 if (!uns) 1321 return 0; 1322 1323 /* Note that using TYPE_PRECISION here is wrong. We care about the 1324 actual bits, not the (arbitrary) range of the type. */ 1325 prec = GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (expr))); 1326 if (prec >= HOST_BITS_PER_WIDE_INT) 1327 { 1328 HOST_WIDE_INT high_value; 1329 int shift_amount; 1330 1331 shift_amount = prec - HOST_BITS_PER_WIDE_INT; 1332 1333 /* Can not handle precisions greater than twice the host int size. */ 1334 gcc_assert (shift_amount <= HOST_BITS_PER_WIDE_INT); 1335 if (shift_amount == HOST_BITS_PER_WIDE_INT) 1336 /* Shifting by the host word size is undefined according to the ANSI 1337 standard, so we must handle this as a special case. */ 1338 high_value = -1; 1339 else 1340 high_value = ((HOST_WIDE_INT) 1 << shift_amount) - 1; 1341 1342 return (TREE_INT_CST_LOW (expr) == ~(unsigned HOST_WIDE_INT) 0 1343 && TREE_INT_CST_HIGH (expr) == high_value); 1344 } 1345 else 1346 return TREE_INT_CST_LOW (expr) == ((unsigned HOST_WIDE_INT) 1 << prec) - 1; 1347} 1348 1349/* Return 1 if EXPR is an integer constant that is a power of 2 (i.e., has only 1350 one bit on). */ 1351 1352int 1353integer_pow2p (tree expr) 1354{ 1355 int prec; 1356 HOST_WIDE_INT high, low; 1357 1358 STRIP_NOPS (expr); 1359 1360 if (TREE_CODE (expr) == COMPLEX_CST 1361 && integer_pow2p (TREE_REALPART (expr)) 1362 && integer_zerop (TREE_IMAGPART (expr))) 1363 return 1; 1364 1365 if (TREE_CODE (expr) != INTEGER_CST) 1366 return 0; 1367 1368 prec = (POINTER_TYPE_P (TREE_TYPE (expr)) 1369 ? POINTER_SIZE : TYPE_PRECISION (TREE_TYPE (expr))); 1370 high = TREE_INT_CST_HIGH (expr); 1371 low = TREE_INT_CST_LOW (expr); 1372 1373 /* First clear all bits that are beyond the type's precision in case 1374 we've been sign extended. */ 1375 1376 if (prec == 2 * HOST_BITS_PER_WIDE_INT) 1377 ; 1378 else if (prec > HOST_BITS_PER_WIDE_INT) 1379 high &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT)); 1380 else 1381 { 1382 high = 0; 1383 if (prec < HOST_BITS_PER_WIDE_INT) 1384 low &= ~((HOST_WIDE_INT) (-1) << prec); 1385 } 1386 1387 if (high == 0 && low == 0) 1388 return 0; 1389 1390 return ((high == 0 && (low & (low - 1)) == 0) 1391 || (low == 0 && (high & (high - 1)) == 0)); 1392} 1393 1394/* Return 1 if EXPR is an integer constant other than zero or a 1395 complex constant other than zero. */ 1396 1397int 1398integer_nonzerop (tree expr) 1399{ 1400 STRIP_NOPS (expr); 1401 1402 return ((TREE_CODE (expr) == INTEGER_CST 1403 && (TREE_INT_CST_LOW (expr) != 0 1404 || TREE_INT_CST_HIGH (expr) != 0)) 1405 || (TREE_CODE (expr) == COMPLEX_CST 1406 && (integer_nonzerop (TREE_REALPART (expr)) 1407 || integer_nonzerop (TREE_IMAGPART (expr))))); 1408} 1409 1410/* Return the power of two represented by a tree node known to be a 1411 power of two. */ 1412 1413int 1414tree_log2 (tree expr) 1415{ 1416 int prec; 1417 HOST_WIDE_INT high, low; 1418 1419 STRIP_NOPS (expr); 1420 1421 if (TREE_CODE (expr) == COMPLEX_CST) 1422 return tree_log2 (TREE_REALPART (expr)); 1423 1424 prec = (POINTER_TYPE_P (TREE_TYPE (expr)) 1425 ? POINTER_SIZE : TYPE_PRECISION (TREE_TYPE (expr))); 1426 1427 high = TREE_INT_CST_HIGH (expr); 1428 low = TREE_INT_CST_LOW (expr); 1429 1430 /* First clear all bits that are beyond the type's precision in case 1431 we've been sign extended. */ 1432 1433 if (prec == 2 * HOST_BITS_PER_WIDE_INT) 1434 ; 1435 else if (prec > HOST_BITS_PER_WIDE_INT) 1436 high &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT)); 1437 else 1438 { 1439 high = 0; 1440 if (prec < HOST_BITS_PER_WIDE_INT) 1441 low &= ~((HOST_WIDE_INT) (-1) << prec); 1442 } 1443 1444 return (high != 0 ? HOST_BITS_PER_WIDE_INT + exact_log2 (high) 1445 : exact_log2 (low)); 1446} 1447 1448/* Similar, but return the largest integer Y such that 2 ** Y is less 1449 than or equal to EXPR. */ 1450 1451int 1452tree_floor_log2 (tree expr) 1453{ 1454 int prec; 1455 HOST_WIDE_INT high, low; 1456 1457 STRIP_NOPS (expr); 1458 1459 if (TREE_CODE (expr) == COMPLEX_CST) 1460 return tree_log2 (TREE_REALPART (expr)); 1461 1462 prec = (POINTER_TYPE_P (TREE_TYPE (expr)) 1463 ? POINTER_SIZE : TYPE_PRECISION (TREE_TYPE (expr))); 1464 1465 high = TREE_INT_CST_HIGH (expr); 1466 low = TREE_INT_CST_LOW (expr); 1467 1468 /* First clear all bits that are beyond the type's precision in case 1469 we've been sign extended. Ignore if type's precision hasn't been set 1470 since what we are doing is setting it. */ 1471 1472 if (prec == 2 * HOST_BITS_PER_WIDE_INT || prec == 0) 1473 ; 1474 else if (prec > HOST_BITS_PER_WIDE_INT) 1475 high &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT)); 1476 else 1477 { 1478 high = 0; 1479 if (prec < HOST_BITS_PER_WIDE_INT) 1480 low &= ~((HOST_WIDE_INT) (-1) << prec); 1481 } 1482 1483 return (high != 0 ? HOST_BITS_PER_WIDE_INT + floor_log2 (high) 1484 : floor_log2 (low)); 1485} 1486 1487/* Return 1 if EXPR is the real constant zero. */ 1488 1489int 1490real_zerop (tree expr) 1491{ 1492 STRIP_NOPS (expr); 1493 1494 return ((TREE_CODE (expr) == REAL_CST 1495 && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconst0)) 1496 || (TREE_CODE (expr) == COMPLEX_CST 1497 && real_zerop (TREE_REALPART (expr)) 1498 && real_zerop (TREE_IMAGPART (expr)))); 1499} 1500 1501/* Return 1 if EXPR is the real constant one in real or complex form. */ 1502 1503int 1504real_onep (tree expr) 1505{ 1506 STRIP_NOPS (expr); 1507 1508 return ((TREE_CODE (expr) == REAL_CST 1509 && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconst1)) 1510 || (TREE_CODE (expr) == COMPLEX_CST 1511 && real_onep (TREE_REALPART (expr)) 1512 && real_zerop (TREE_IMAGPART (expr)))); 1513} 1514 1515/* Return 1 if EXPR is the real constant two. */ 1516 1517int 1518real_twop (tree expr) 1519{ 1520 STRIP_NOPS (expr); 1521 1522 return ((TREE_CODE (expr) == REAL_CST 1523 && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconst2)) 1524 || (TREE_CODE (expr) == COMPLEX_CST 1525 && real_twop (TREE_REALPART (expr)) 1526 && real_zerop (TREE_IMAGPART (expr)))); 1527} 1528 1529/* Return 1 if EXPR is the real constant minus one. */ 1530 1531int 1532real_minus_onep (tree expr) 1533{ 1534 STRIP_NOPS (expr); 1535 1536 return ((TREE_CODE (expr) == REAL_CST 1537 && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconstm1)) 1538 || (TREE_CODE (expr) == COMPLEX_CST 1539 && real_minus_onep (TREE_REALPART (expr)) 1540 && real_zerop (TREE_IMAGPART (expr)))); 1541} 1542 1543/* Nonzero if EXP is a constant or a cast of a constant. */ 1544 1545int 1546really_constant_p (tree exp) 1547{ 1548 /* This is not quite the same as STRIP_NOPS. It does more. */ 1549 while (TREE_CODE (exp) == NOP_EXPR 1550 || TREE_CODE (exp) == CONVERT_EXPR 1551 || TREE_CODE (exp) == NON_LVALUE_EXPR) 1552 exp = TREE_OPERAND (exp, 0); 1553 return TREE_CONSTANT (exp); 1554} 1555 1556/* Return first list element whose TREE_VALUE is ELEM. 1557 Return 0 if ELEM is not in LIST. */ 1558 1559tree 1560value_member (tree elem, tree list) 1561{ 1562 while (list) 1563 { 1564 if (elem == TREE_VALUE (list)) 1565 return list; 1566 list = TREE_CHAIN (list); 1567 } 1568 return NULL_TREE; 1569} 1570 1571/* Return first list element whose TREE_PURPOSE is ELEM. 1572 Return 0 if ELEM is not in LIST. */ 1573 1574tree 1575purpose_member (tree elem, tree list) 1576{ 1577 while (list) 1578 { 1579 if (elem == TREE_PURPOSE (list)) 1580 return list; 1581 list = TREE_CHAIN (list); 1582 } 1583 return NULL_TREE; 1584} 1585 1586/* Return nonzero if ELEM is part of the chain CHAIN. */ 1587 1588int 1589chain_member (tree elem, tree chain) 1590{ 1591 while (chain) 1592 { 1593 if (elem == chain) 1594 return 1; 1595 chain = TREE_CHAIN (chain); 1596 } 1597 1598 return 0; 1599} 1600 1601/* Return the length of a chain of nodes chained through TREE_CHAIN. 1602 We expect a null pointer to mark the end of the chain. 1603 This is the Lisp primitive `length'. */ 1604 1605int 1606list_length (tree t) 1607{ 1608 tree p = t; 1609#ifdef ENABLE_TREE_CHECKING 1610 tree q = t; 1611#endif 1612 int len = 0; 1613 1614 while (p) 1615 { 1616 p = TREE_CHAIN (p); 1617#ifdef ENABLE_TREE_CHECKING 1618 if (len % 2) 1619 q = TREE_CHAIN (q); 1620 gcc_assert (p != q); 1621#endif 1622 len++; 1623 } 1624 1625 return len; 1626} 1627 1628/* Returns the number of FIELD_DECLs in TYPE. */ 1629 1630int 1631fields_length (tree type) 1632{ 1633 tree t = TYPE_FIELDS (type); 1634 int count = 0; 1635 1636 for (; t; t = TREE_CHAIN (t)) 1637 if (TREE_CODE (t) == FIELD_DECL) 1638 ++count; 1639 1640 return count; 1641} 1642 1643/* Concatenate two chains of nodes (chained through TREE_CHAIN) 1644 by modifying the last node in chain 1 to point to chain 2. 1645 This is the Lisp primitive `nconc'. */ 1646 1647tree 1648chainon (tree op1, tree op2) 1649{ 1650 tree t1; 1651 1652 if (!op1) 1653 return op2; 1654 if (!op2) 1655 return op1; 1656 1657 for (t1 = op1; TREE_CHAIN (t1); t1 = TREE_CHAIN (t1)) 1658 continue; 1659 TREE_CHAIN (t1) = op2; 1660 1661#ifdef ENABLE_TREE_CHECKING 1662 { 1663 tree t2; 1664 for (t2 = op2; t2; t2 = TREE_CHAIN (t2)) 1665 gcc_assert (t2 != t1); 1666 } 1667#endif 1668 1669 return op1; 1670} 1671 1672/* Return the last node in a chain of nodes (chained through TREE_CHAIN). */ 1673 1674tree 1675tree_last (tree chain) 1676{ 1677 tree next; 1678 if (chain) 1679 while ((next = TREE_CHAIN (chain))) 1680 chain = next; 1681 return chain; 1682} 1683 1684/* Reverse the order of elements in the chain T, 1685 and return the new head of the chain (old last element). */ 1686 1687tree 1688nreverse (tree t) 1689{ 1690 tree prev = 0, decl, next; 1691 for (decl = t; decl; decl = next) 1692 { 1693 next = TREE_CHAIN (decl); 1694 TREE_CHAIN (decl) = prev; 1695 prev = decl; 1696 } 1697 return prev; 1698} 1699 1700/* Return a newly created TREE_LIST node whose 1701 purpose and value fields are PARM and VALUE. */ 1702 1703tree 1704build_tree_list_stat (tree parm, tree value MEM_STAT_DECL) 1705{ 1706 tree t = make_node_stat (TREE_LIST PASS_MEM_STAT); 1707 TREE_PURPOSE (t) = parm; 1708 TREE_VALUE (t) = value; 1709 return t; 1710} 1711 1712/* Return a newly created TREE_LIST node whose 1713 purpose and value fields are PURPOSE and VALUE 1714 and whose TREE_CHAIN is CHAIN. */ 1715 1716tree 1717tree_cons_stat (tree purpose, tree value, tree chain MEM_STAT_DECL) 1718{ 1719 tree node; 1720 1721 node = ggc_alloc_zone_pass_stat (sizeof (struct tree_list), &tree_zone); 1722 1723 memset (node, 0, sizeof (struct tree_common)); 1724 1725#ifdef GATHER_STATISTICS 1726 tree_node_counts[(int) x_kind]++; 1727 tree_node_sizes[(int) x_kind] += sizeof (struct tree_list); 1728#endif 1729 1730 TREE_SET_CODE (node, TREE_LIST); 1731 TREE_CHAIN (node) = chain; 1732 TREE_PURPOSE (node) = purpose; 1733 TREE_VALUE (node) = value; 1734 return node; 1735} 1736 1737 1738/* Return the size nominally occupied by an object of type TYPE 1739 when it resides in memory. The value is measured in units of bytes, 1740 and its data type is that normally used for type sizes 1741 (which is the first type created by make_signed_type or 1742 make_unsigned_type). */ 1743 1744tree 1745size_in_bytes (tree type) 1746{ 1747 tree t; 1748 1749 if (type == error_mark_node) 1750 return integer_zero_node; 1751 1752 type = TYPE_MAIN_VARIANT (type); 1753 t = TYPE_SIZE_UNIT (type); 1754 1755 if (t == 0) 1756 { 1757 lang_hooks.types.incomplete_type_error (NULL_TREE, type); 1758 return size_zero_node; 1759 } 1760 1761 if (TREE_CODE (t) == INTEGER_CST) 1762 t = force_fit_type (t, 0, false, false); 1763 1764 return t; 1765} 1766 1767/* Return the size of TYPE (in bytes) as a wide integer 1768 or return -1 if the size can vary or is larger than an integer. */ 1769 1770HOST_WIDE_INT 1771int_size_in_bytes (tree type) 1772{ 1773 tree t; 1774 1775 if (type == error_mark_node) 1776 return 0; 1777 1778 type = TYPE_MAIN_VARIANT (type); 1779 t = TYPE_SIZE_UNIT (type); 1780 if (t == 0 1781 || TREE_CODE (t) != INTEGER_CST 1782 || TREE_INT_CST_HIGH (t) != 0 1783 /* If the result would appear negative, it's too big to represent. */ 1784 || (HOST_WIDE_INT) TREE_INT_CST_LOW (t) < 0) 1785 return -1; 1786 1787 return TREE_INT_CST_LOW (t); 1788} 1789 1790/* Return the maximum size of TYPE (in bytes) as a wide integer 1791 or return -1 if the size can vary or is larger than an integer. */ 1792 1793HOST_WIDE_INT 1794max_int_size_in_bytes (tree type) 1795{ 1796 HOST_WIDE_INT size = -1; 1797 tree size_tree; 1798 1799 /* If this is an array type, check for a possible MAX_SIZE attached. */ 1800 1801 if (TREE_CODE (type) == ARRAY_TYPE) 1802 { 1803 size_tree = TYPE_ARRAY_MAX_SIZE (type); 1804 1805 if (size_tree && host_integerp (size_tree, 1)) 1806 size = tree_low_cst (size_tree, 1); 1807 } 1808 1809 /* If we still haven't been able to get a size, see if the language 1810 can compute a maximum size. */ 1811 1812 if (size == -1) 1813 { 1814 size_tree = lang_hooks.types.max_size (type); 1815 1816 if (size_tree && host_integerp (size_tree, 1)) 1817 size = tree_low_cst (size_tree, 1); 1818 } 1819 1820 return size; 1821} 1822 1823/* Return the bit position of FIELD, in bits from the start of the record. 1824 This is a tree of type bitsizetype. */ 1825 1826tree 1827bit_position (tree field) 1828{ 1829 return bit_from_pos (DECL_FIELD_OFFSET (field), 1830 DECL_FIELD_BIT_OFFSET (field)); 1831} 1832 1833/* Likewise, but return as an integer. It must be representable in 1834 that way (since it could be a signed value, we don't have the 1835 option of returning -1 like int_size_in_byte can. */ 1836 1837HOST_WIDE_INT 1838int_bit_position (tree field) 1839{ 1840 return tree_low_cst (bit_position (field), 0); 1841} 1842 1843/* Return the byte position of FIELD, in bytes from the start of the record. 1844 This is a tree of type sizetype. */ 1845 1846tree 1847byte_position (tree field) 1848{ 1849 return byte_from_pos (DECL_FIELD_OFFSET (field), 1850 DECL_FIELD_BIT_OFFSET (field)); 1851} 1852 1853/* Likewise, but return as an integer. It must be representable in 1854 that way (since it could be a signed value, we don't have the 1855 option of returning -1 like int_size_in_byte can. */ 1856 1857HOST_WIDE_INT 1858int_byte_position (tree field) 1859{ 1860 return tree_low_cst (byte_position (field), 0); 1861} 1862 1863/* Return the strictest alignment, in bits, that T is known to have. */ 1864 1865unsigned int 1866expr_align (tree t) 1867{ 1868 unsigned int align0, align1; 1869 1870 switch (TREE_CODE (t)) 1871 { 1872 case NOP_EXPR: case CONVERT_EXPR: case NON_LVALUE_EXPR: 1873 /* If we have conversions, we know that the alignment of the 1874 object must meet each of the alignments of the types. */ 1875 align0 = expr_align (TREE_OPERAND (t, 0)); 1876 align1 = TYPE_ALIGN (TREE_TYPE (t)); 1877 return MAX (align0, align1); 1878 1879 case SAVE_EXPR: case COMPOUND_EXPR: case MODIFY_EXPR: 1880 case INIT_EXPR: case TARGET_EXPR: case WITH_CLEANUP_EXPR: 1881 case CLEANUP_POINT_EXPR: 1882 /* These don't change the alignment of an object. */ 1883 return expr_align (TREE_OPERAND (t, 0)); 1884 1885 case COND_EXPR: 1886 /* The best we can do is say that the alignment is the least aligned 1887 of the two arms. */ 1888 align0 = expr_align (TREE_OPERAND (t, 1)); 1889 align1 = expr_align (TREE_OPERAND (t, 2)); 1890 return MIN (align0, align1); 1891 1892 /* FIXME: LABEL_DECL and CONST_DECL never have DECL_ALIGN set 1893 meaningfully, it's always 1. */ 1894 case LABEL_DECL: case CONST_DECL: 1895 case VAR_DECL: case PARM_DECL: case RESULT_DECL: 1896 case FUNCTION_DECL: 1897 gcc_assert (DECL_ALIGN (t) != 0); 1898 return DECL_ALIGN (t); 1899 1900 default: 1901 break; 1902 } 1903 1904 /* Otherwise take the alignment from that of the type. */ 1905 return TYPE_ALIGN (TREE_TYPE (t)); 1906} 1907 1908/* Return, as a tree node, the number of elements for TYPE (which is an 1909 ARRAY_TYPE) minus one. This counts only elements of the top array. */ 1910 1911tree 1912array_type_nelts (tree type) 1913{ 1914 tree index_type, min, max; 1915 1916 /* If they did it with unspecified bounds, then we should have already 1917 given an error about it before we got here. */ 1918 if (! TYPE_DOMAIN (type)) 1919 return error_mark_node; 1920 1921 index_type = TYPE_DOMAIN (type); 1922 min = TYPE_MIN_VALUE (index_type); 1923 max = TYPE_MAX_VALUE (index_type); 1924 1925 return (integer_zerop (min) 1926 ? max 1927 : fold_build2 (MINUS_EXPR, TREE_TYPE (max), max, min)); 1928} 1929 1930/* If arg is static -- a reference to an object in static storage -- then 1931 return the object. This is not the same as the C meaning of `static'. 1932 If arg isn't static, return NULL. */ 1933 1934tree 1935staticp (tree arg) 1936{ 1937 switch (TREE_CODE (arg)) 1938 { 1939 case FUNCTION_DECL: 1940 /* Nested functions are static, even though taking their address will 1941 involve a trampoline as we unnest the nested function and create 1942 the trampoline on the tree level. */ 1943 return arg; 1944 1945 case VAR_DECL: 1946 return ((TREE_STATIC (arg) || DECL_EXTERNAL (arg)) 1947 && ! DECL_THREAD_LOCAL_P (arg) 1948 && ! DECL_DLLIMPORT_P (arg) 1949 ? arg : NULL); 1950 1951 case CONST_DECL: 1952 return ((TREE_STATIC (arg) || DECL_EXTERNAL (arg)) 1953 ? arg : NULL); 1954 1955 case CONSTRUCTOR: 1956 return TREE_STATIC (arg) ? arg : NULL; 1957 1958 case LABEL_DECL: 1959 case STRING_CST: 1960 return arg; 1961 1962 case COMPONENT_REF: 1963 /* If the thing being referenced is not a field, then it is 1964 something language specific. */ 1965 if (TREE_CODE (TREE_OPERAND (arg, 1)) != FIELD_DECL) 1966 return (*lang_hooks.staticp) (arg); 1967 1968 /* If we are referencing a bitfield, we can't evaluate an 1969 ADDR_EXPR at compile time and so it isn't a constant. */ 1970 if (DECL_BIT_FIELD (TREE_OPERAND (arg, 1))) 1971 return NULL; 1972 1973 return staticp (TREE_OPERAND (arg, 0)); 1974 1975 case BIT_FIELD_REF: 1976 return NULL; 1977 1978 case MISALIGNED_INDIRECT_REF: 1979 case ALIGN_INDIRECT_REF: 1980 case INDIRECT_REF: 1981 return TREE_CONSTANT (TREE_OPERAND (arg, 0)) ? arg : NULL; 1982 1983 case ARRAY_REF: 1984 case ARRAY_RANGE_REF: 1985 if (TREE_CODE (TYPE_SIZE (TREE_TYPE (arg))) == INTEGER_CST 1986 && TREE_CODE (TREE_OPERAND (arg, 1)) == INTEGER_CST) 1987 return staticp (TREE_OPERAND (arg, 0)); 1988 else 1989 return false; 1990 1991 default: 1992 if ((unsigned int) TREE_CODE (arg) 1993 >= (unsigned int) LAST_AND_UNUSED_TREE_CODE) 1994 return lang_hooks.staticp (arg); 1995 else 1996 return NULL; 1997 } 1998} 1999 2000/* Wrap a SAVE_EXPR around EXPR, if appropriate. 2001 Do this to any expression which may be used in more than one place, 2002 but must be evaluated only once. 2003 2004 Normally, expand_expr would reevaluate the expression each time. 2005 Calling save_expr produces something that is evaluated and recorded 2006 the first time expand_expr is called on it. Subsequent calls to 2007 expand_expr just reuse the recorded value. 2008 2009 The call to expand_expr that generates code that actually computes 2010 the value is the first call *at compile time*. Subsequent calls 2011 *at compile time* generate code to use the saved value. 2012 This produces correct result provided that *at run time* control 2013 always flows through the insns made by the first expand_expr 2014 before reaching the other places where the save_expr was evaluated. 2015 You, the caller of save_expr, must make sure this is so. 2016 2017 Constants, and certain read-only nodes, are returned with no 2018 SAVE_EXPR because that is safe. Expressions containing placeholders 2019 are not touched; see tree.def for an explanation of what these 2020 are used for. */ 2021 2022tree 2023save_expr (tree expr) 2024{ 2025 tree t = fold (expr); 2026 tree inner; 2027 2028 /* If the tree evaluates to a constant, then we don't want to hide that 2029 fact (i.e. this allows further folding, and direct checks for constants). 2030 However, a read-only object that has side effects cannot be bypassed. 2031 Since it is no problem to reevaluate literals, we just return the 2032 literal node. */ 2033 inner = skip_simple_arithmetic (t); 2034 2035 if (TREE_INVARIANT (inner) 2036 || (TREE_READONLY (inner) && ! TREE_SIDE_EFFECTS (inner)) 2037 || TREE_CODE (inner) == SAVE_EXPR 2038 || TREE_CODE (inner) == ERROR_MARK) 2039 return t; 2040 2041 /* If INNER contains a PLACEHOLDER_EXPR, we must evaluate it each time, since 2042 it means that the size or offset of some field of an object depends on 2043 the value within another field. 2044 2045 Note that it must not be the case that T contains both a PLACEHOLDER_EXPR 2046 and some variable since it would then need to be both evaluated once and 2047 evaluated more than once. Front-ends must assure this case cannot 2048 happen by surrounding any such subexpressions in their own SAVE_EXPR 2049 and forcing evaluation at the proper time. */ 2050 if (contains_placeholder_p (inner)) 2051 return t; 2052 2053 t = build1 (SAVE_EXPR, TREE_TYPE (expr), t); 2054 2055 /* This expression might be placed ahead of a jump to ensure that the 2056 value was computed on both sides of the jump. So make sure it isn't 2057 eliminated as dead. */ 2058 TREE_SIDE_EFFECTS (t) = 1; 2059 TREE_INVARIANT (t) = 1; 2060 return t; 2061} 2062 2063/* Look inside EXPR and into any simple arithmetic operations. Return 2064 the innermost non-arithmetic node. */ 2065 2066tree 2067skip_simple_arithmetic (tree expr) 2068{ 2069 tree inner; 2070 2071 /* We don't care about whether this can be used as an lvalue in this 2072 context. */ 2073 while (TREE_CODE (expr) == NON_LVALUE_EXPR) 2074 expr = TREE_OPERAND (expr, 0); 2075 2076 /* If we have simple operations applied to a SAVE_EXPR or to a SAVE_EXPR and 2077 a constant, it will be more efficient to not make another SAVE_EXPR since 2078 it will allow better simplification and GCSE will be able to merge the 2079 computations if they actually occur. */ 2080 inner = expr; 2081 while (1) 2082 { 2083 if (UNARY_CLASS_P (inner)) 2084 inner = TREE_OPERAND (inner, 0); 2085 else if (BINARY_CLASS_P (inner)) 2086 { 2087 if (TREE_INVARIANT (TREE_OPERAND (inner, 1))) 2088 inner = TREE_OPERAND (inner, 0); 2089 else if (TREE_INVARIANT (TREE_OPERAND (inner, 0))) 2090 inner = TREE_OPERAND (inner, 1); 2091 else 2092 break; 2093 } 2094 else 2095 break; 2096 } 2097 2098 return inner; 2099} 2100 2101/* Return which tree structure is used by T. */ 2102 2103enum tree_node_structure_enum 2104tree_node_structure (tree t) 2105{ 2106 enum tree_code code = TREE_CODE (t); 2107 2108 switch (TREE_CODE_CLASS (code)) 2109 { 2110 case tcc_declaration: 2111 { 2112 switch (code) 2113 { 2114 case FIELD_DECL: 2115 return TS_FIELD_DECL; 2116 case PARM_DECL: 2117 return TS_PARM_DECL; 2118 case VAR_DECL: 2119 return TS_VAR_DECL; 2120 case LABEL_DECL: 2121 return TS_LABEL_DECL; 2122 case RESULT_DECL: 2123 return TS_RESULT_DECL; 2124 case CONST_DECL: 2125 return TS_CONST_DECL; 2126 case TYPE_DECL: 2127 return TS_TYPE_DECL; 2128 case FUNCTION_DECL: 2129 return TS_FUNCTION_DECL; 2130 case SYMBOL_MEMORY_TAG: 2131 case NAME_MEMORY_TAG: 2132 case STRUCT_FIELD_TAG: 2133 return TS_MEMORY_TAG; 2134 default: 2135 return TS_DECL_NON_COMMON; 2136 } 2137 } 2138 case tcc_type: 2139 return TS_TYPE; 2140 case tcc_reference: 2141 case tcc_comparison: 2142 case tcc_unary: 2143 case tcc_binary: 2144 case tcc_expression: 2145 case tcc_statement: 2146 return TS_EXP; 2147 default: /* tcc_constant and tcc_exceptional */ 2148 break; 2149 } 2150 switch (code) 2151 { 2152 /* tcc_constant cases. */ 2153 case INTEGER_CST: return TS_INT_CST; 2154 case REAL_CST: return TS_REAL_CST; 2155 case COMPLEX_CST: return TS_COMPLEX; 2156 case VECTOR_CST: return TS_VECTOR; 2157 case STRING_CST: return TS_STRING; 2158 /* tcc_exceptional cases. */ 2159 case ERROR_MARK: return TS_COMMON; 2160 case IDENTIFIER_NODE: return TS_IDENTIFIER; 2161 case TREE_LIST: return TS_LIST; 2162 case TREE_VEC: return TS_VEC; 2163 case PHI_NODE: return TS_PHI_NODE; 2164 case SSA_NAME: return TS_SSA_NAME; 2165 case PLACEHOLDER_EXPR: return TS_COMMON; 2166 case STATEMENT_LIST: return TS_STATEMENT_LIST; 2167 case BLOCK: return TS_BLOCK; 2168 case CONSTRUCTOR: return TS_CONSTRUCTOR; 2169 case TREE_BINFO: return TS_BINFO; 2170 case VALUE_HANDLE: return TS_VALUE_HANDLE; 2171 case OMP_CLAUSE: return TS_OMP_CLAUSE; 2172 2173 default: 2174 gcc_unreachable (); 2175 } 2176} 2177 2178/* Return 1 if EXP contains a PLACEHOLDER_EXPR; i.e., if it represents a size 2179 or offset that depends on a field within a record. */ 2180 2181bool 2182contains_placeholder_p (tree exp) 2183{ 2184 enum tree_code code; 2185 2186 if (!exp) 2187 return 0; 2188 2189 code = TREE_CODE (exp); 2190 if (code == PLACEHOLDER_EXPR) 2191 return 1; 2192 2193 switch (TREE_CODE_CLASS (code)) 2194 { 2195 case tcc_reference: 2196 /* Don't look at any PLACEHOLDER_EXPRs that might be in index or bit 2197 position computations since they will be converted into a 2198 WITH_RECORD_EXPR involving the reference, which will assume 2199 here will be valid. */ 2200 return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0)); 2201 2202 case tcc_exceptional: 2203 if (code == TREE_LIST) 2204 return (CONTAINS_PLACEHOLDER_P (TREE_VALUE (exp)) 2205 || CONTAINS_PLACEHOLDER_P (TREE_CHAIN (exp))); 2206 break; 2207 2208 case tcc_unary: 2209 case tcc_binary: 2210 case tcc_comparison: 2211 case tcc_expression: 2212 switch (code) 2213 { 2214 case COMPOUND_EXPR: 2215 /* Ignoring the first operand isn't quite right, but works best. */ 2216 return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1)); 2217 2218 case COND_EXPR: 2219 return (CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0)) 2220 || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1)) 2221 || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 2))); 2222 2223 case CALL_EXPR: 2224 return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1)); 2225 2226 default: 2227 break; 2228 } 2229 2230 switch (TREE_CODE_LENGTH (code)) 2231 { 2232 case 1: 2233 return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0)); 2234 case 2: 2235 return (CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0)) 2236 || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1))); 2237 default: 2238 return 0; 2239 } 2240 2241 default: 2242 return 0; 2243 } 2244 return 0; 2245} 2246 2247/* Return true if any part of the computation of TYPE involves a 2248 PLACEHOLDER_EXPR. This includes size, bounds, qualifiers 2249 (for QUAL_UNION_TYPE) and field positions. */ 2250 2251static bool 2252type_contains_placeholder_1 (tree type) 2253{ 2254 /* If the size contains a placeholder or the parent type (component type in 2255 the case of arrays) type involves a placeholder, this type does. */ 2256 if (CONTAINS_PLACEHOLDER_P (TYPE_SIZE (type)) 2257 || CONTAINS_PLACEHOLDER_P (TYPE_SIZE_UNIT (type)) 2258 || (TREE_TYPE (type) != 0 2259 && type_contains_placeholder_p (TREE_TYPE (type)))) 2260 return true; 2261 2262 /* Now do type-specific checks. Note that the last part of the check above 2263 greatly limits what we have to do below. */ 2264 switch (TREE_CODE (type)) 2265 { 2266 case VOID_TYPE: 2267 case COMPLEX_TYPE: 2268 case ENUMERAL_TYPE: 2269 case BOOLEAN_TYPE: 2270 case POINTER_TYPE: 2271 case OFFSET_TYPE: 2272 case REFERENCE_TYPE: 2273 case METHOD_TYPE: 2274 case FUNCTION_TYPE: 2275 case VECTOR_TYPE: 2276 return false; 2277 2278 case INTEGER_TYPE: 2279 case REAL_TYPE: 2280 /* Here we just check the bounds. */ 2281 return (CONTAINS_PLACEHOLDER_P (TYPE_MIN_VALUE (type)) 2282 || CONTAINS_PLACEHOLDER_P (TYPE_MAX_VALUE (type))); 2283 2284 case ARRAY_TYPE: 2285 /* We're already checked the component type (TREE_TYPE), so just check 2286 the index type. */ 2287 return type_contains_placeholder_p (TYPE_DOMAIN (type)); 2288 2289 case RECORD_TYPE: 2290 case UNION_TYPE: 2291 case QUAL_UNION_TYPE: 2292 { 2293 tree field; 2294 2295 for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field)) 2296 if (TREE_CODE (field) == FIELD_DECL 2297 && (CONTAINS_PLACEHOLDER_P (DECL_FIELD_OFFSET (field)) 2298 || (TREE_CODE (type) == QUAL_UNION_TYPE 2299 && CONTAINS_PLACEHOLDER_P (DECL_QUALIFIER (field))) 2300 || type_contains_placeholder_p (TREE_TYPE (field)))) 2301 return true; 2302 2303 return false; 2304 } 2305 2306 default: 2307 gcc_unreachable (); 2308 } 2309} 2310 2311bool 2312type_contains_placeholder_p (tree type) 2313{ 2314 bool result; 2315 2316 /* If the contains_placeholder_bits field has been initialized, 2317 then we know the answer. */ 2318 if (TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) > 0) 2319 return TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) - 1; 2320 2321 /* Indicate that we've seen this type node, and the answer is false. 2322 This is what we want to return if we run into recursion via fields. */ 2323 TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) = 1; 2324 2325 /* Compute the real value. */ 2326 result = type_contains_placeholder_1 (type); 2327 2328 /* Store the real value. */ 2329 TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) = result + 1; 2330 2331 return result; 2332} 2333 2334/* Given a tree EXP, a FIELD_DECL F, and a replacement value R, 2335 return a tree with all occurrences of references to F in a 2336 PLACEHOLDER_EXPR replaced by R. Note that we assume here that EXP 2337 contains only arithmetic expressions or a CALL_EXPR with a 2338 PLACEHOLDER_EXPR occurring only in its arglist. */ 2339 2340tree 2341substitute_in_expr (tree exp, tree f, tree r) 2342{ 2343 enum tree_code code = TREE_CODE (exp); 2344 tree op0, op1, op2, op3; 2345 tree new; 2346 tree inner; 2347 2348 /* We handle TREE_LIST and COMPONENT_REF separately. */ 2349 if (code == TREE_LIST) 2350 { 2351 op0 = SUBSTITUTE_IN_EXPR (TREE_CHAIN (exp), f, r); 2352 op1 = SUBSTITUTE_IN_EXPR (TREE_VALUE (exp), f, r); 2353 if (op0 == TREE_CHAIN (exp) && op1 == TREE_VALUE (exp)) 2354 return exp; 2355 2356 return tree_cons (TREE_PURPOSE (exp), op1, op0); 2357 } 2358 else if (code == COMPONENT_REF) 2359 { 2360 /* If this expression is getting a value from a PLACEHOLDER_EXPR 2361 and it is the right field, replace it with R. */ 2362 for (inner = TREE_OPERAND (exp, 0); 2363 REFERENCE_CLASS_P (inner); 2364 inner = TREE_OPERAND (inner, 0)) 2365 ; 2366 if (TREE_CODE (inner) == PLACEHOLDER_EXPR 2367 && TREE_OPERAND (exp, 1) == f) 2368 return r; 2369 2370 /* If this expression hasn't been completed let, leave it alone. */ 2371 if (TREE_CODE (inner) == PLACEHOLDER_EXPR && TREE_TYPE (inner) == 0) 2372 return exp; 2373 2374 op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r); 2375 if (op0 == TREE_OPERAND (exp, 0)) 2376 return exp; 2377 2378 new = fold_build3 (COMPONENT_REF, TREE_TYPE (exp), 2379 op0, TREE_OPERAND (exp, 1), NULL_TREE); 2380 } 2381 else 2382 switch (TREE_CODE_CLASS (code)) 2383 { 2384 case tcc_constant: 2385 case tcc_declaration: 2386 return exp; 2387 2388 case tcc_exceptional: 2389 case tcc_unary: 2390 case tcc_binary: 2391 case tcc_comparison: 2392 case tcc_expression: 2393 case tcc_reference: 2394 switch (TREE_CODE_LENGTH (code)) 2395 { 2396 case 0: 2397 return exp; 2398 2399 case 1: 2400 op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r); 2401 if (op0 == TREE_OPERAND (exp, 0)) 2402 return exp; 2403 2404 new = fold_build1 (code, TREE_TYPE (exp), op0); 2405 break; 2406 2407 case 2: 2408 op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r); 2409 op1 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 1), f, r); 2410 2411 if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)) 2412 return exp; 2413 2414 new = fold_build2 (code, TREE_TYPE (exp), op0, op1); 2415 break; 2416 2417 case 3: 2418 op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r); 2419 op1 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 1), f, r); 2420 op2 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 2), f, r); 2421 2422 if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1) 2423 && op2 == TREE_OPERAND (exp, 2)) 2424 return exp; 2425 2426 new = fold_build3 (code, TREE_TYPE (exp), op0, op1, op2); 2427 break; 2428 2429 case 4: 2430 op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r); 2431 op1 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 1), f, r); 2432 op2 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 2), f, r); 2433 op3 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 3), f, r); 2434 2435 if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1) 2436 && op2 == TREE_OPERAND (exp, 2) 2437 && op3 == TREE_OPERAND (exp, 3)) 2438 return exp; 2439 2440 new = fold (build4 (code, TREE_TYPE (exp), op0, op1, op2, op3)); 2441 break; 2442 2443 default: 2444 gcc_unreachable (); 2445 } 2446 break; 2447 2448 default: 2449 gcc_unreachable (); 2450 } 2451 2452 TREE_READONLY (new) = TREE_READONLY (exp); 2453 return new; 2454} 2455 2456/* Similar, but look for a PLACEHOLDER_EXPR in EXP and find a replacement 2457 for it within OBJ, a tree that is an object or a chain of references. */ 2458 2459tree 2460substitute_placeholder_in_expr (tree exp, tree obj) 2461{ 2462 enum tree_code code = TREE_CODE (exp); 2463 tree op0, op1, op2, op3; 2464 2465 /* If this is a PLACEHOLDER_EXPR, see if we find a corresponding type 2466 in the chain of OBJ. */ 2467 if (code == PLACEHOLDER_EXPR) 2468 { 2469 tree need_type = TYPE_MAIN_VARIANT (TREE_TYPE (exp)); 2470 tree elt; 2471 2472 for (elt = obj; elt != 0; 2473 elt = ((TREE_CODE (elt) == COMPOUND_EXPR 2474 || TREE_CODE (elt) == COND_EXPR) 2475 ? TREE_OPERAND (elt, 1) 2476 : (REFERENCE_CLASS_P (elt) 2477 || UNARY_CLASS_P (elt) 2478 || BINARY_CLASS_P (elt) 2479 || EXPRESSION_CLASS_P (elt)) 2480 ? TREE_OPERAND (elt, 0) : 0)) 2481 if (TYPE_MAIN_VARIANT (TREE_TYPE (elt)) == need_type) 2482 return elt; 2483 2484 for (elt = obj; elt != 0; 2485 elt = ((TREE_CODE (elt) == COMPOUND_EXPR 2486 || TREE_CODE (elt) == COND_EXPR) 2487 ? TREE_OPERAND (elt, 1) 2488 : (REFERENCE_CLASS_P (elt) 2489 || UNARY_CLASS_P (elt) 2490 || BINARY_CLASS_P (elt) 2491 || EXPRESSION_CLASS_P (elt)) 2492 ? TREE_OPERAND (elt, 0) : 0)) 2493 if (POINTER_TYPE_P (TREE_TYPE (elt)) 2494 && (TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (elt))) 2495 == need_type)) 2496 return fold_build1 (INDIRECT_REF, need_type, elt); 2497 2498 /* If we didn't find it, return the original PLACEHOLDER_EXPR. If it 2499 survives until RTL generation, there will be an error. */ 2500 return exp; 2501 } 2502 2503 /* TREE_LIST is special because we need to look at TREE_VALUE 2504 and TREE_CHAIN, not TREE_OPERANDS. */ 2505 else if (code == TREE_LIST) 2506 { 2507 op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_CHAIN (exp), obj); 2508 op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_VALUE (exp), obj); 2509 if (op0 == TREE_CHAIN (exp) && op1 == TREE_VALUE (exp)) 2510 return exp; 2511 2512 return tree_cons (TREE_PURPOSE (exp), op1, op0); 2513 } 2514 else 2515 switch (TREE_CODE_CLASS (code)) 2516 { 2517 case tcc_constant: 2518 case tcc_declaration: 2519 return exp; 2520 2521 case tcc_exceptional: 2522 case tcc_unary: 2523 case tcc_binary: 2524 case tcc_comparison: 2525 case tcc_expression: 2526 case tcc_reference: 2527 case tcc_statement: 2528 switch (TREE_CODE_LENGTH (code)) 2529 { 2530 case 0: 2531 return exp; 2532 2533 case 1: 2534 op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj); 2535 if (op0 == TREE_OPERAND (exp, 0)) 2536 return exp; 2537 else 2538 return fold_build1 (code, TREE_TYPE (exp), op0); 2539 2540 case 2: 2541 op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj); 2542 op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 1), obj); 2543 2544 if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)) 2545 return exp; 2546 else 2547 return fold_build2 (code, TREE_TYPE (exp), op0, op1); 2548 2549 case 3: 2550 op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj); 2551 op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 1), obj); 2552 op2 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 2), obj); 2553 2554 if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1) 2555 && op2 == TREE_OPERAND (exp, 2)) 2556 return exp; 2557 else 2558 return fold_build3 (code, TREE_TYPE (exp), op0, op1, op2); 2559 2560 case 4: 2561 op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj); 2562 op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 1), obj); 2563 op2 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 2), obj); 2564 op3 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 3), obj); 2565 2566 if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1) 2567 && op2 == TREE_OPERAND (exp, 2) 2568 && op3 == TREE_OPERAND (exp, 3)) 2569 return exp; 2570 else 2571 return fold (build4 (code, TREE_TYPE (exp), op0, op1, op2, op3)); 2572 2573 default: 2574 gcc_unreachable (); 2575 } 2576 break; 2577 2578 default: 2579 gcc_unreachable (); 2580 } 2581} 2582 2583/* Stabilize a reference so that we can use it any number of times 2584 without causing its operands to be evaluated more than once. 2585 Returns the stabilized reference. This works by means of save_expr, 2586 so see the caveats in the comments about save_expr. 2587 2588 Also allows conversion expressions whose operands are references. 2589 Any other kind of expression is returned unchanged. */ 2590 2591tree 2592stabilize_reference (tree ref) 2593{ 2594 tree result; 2595 enum tree_code code = TREE_CODE (ref); 2596 2597 switch (code) 2598 { 2599 case VAR_DECL: 2600 case PARM_DECL: 2601 case RESULT_DECL: 2602 /* No action is needed in this case. */ 2603 return ref; 2604 2605 case NOP_EXPR: 2606 case CONVERT_EXPR: 2607 case FLOAT_EXPR: 2608 case FIX_TRUNC_EXPR: 2609 case FIX_FLOOR_EXPR: 2610 case FIX_ROUND_EXPR: 2611 case FIX_CEIL_EXPR: 2612 result = build_nt (code, stabilize_reference (TREE_OPERAND (ref, 0))); 2613 break; 2614 2615 case INDIRECT_REF: 2616 result = build_nt (INDIRECT_REF, 2617 stabilize_reference_1 (TREE_OPERAND (ref, 0))); 2618 break; 2619 2620 case COMPONENT_REF: 2621 result = build_nt (COMPONENT_REF, 2622 stabilize_reference (TREE_OPERAND (ref, 0)), 2623 TREE_OPERAND (ref, 1), NULL_TREE); 2624 break; 2625 2626 case BIT_FIELD_REF: 2627 result = build_nt (BIT_FIELD_REF, 2628 stabilize_reference (TREE_OPERAND (ref, 0)), 2629 stabilize_reference_1 (TREE_OPERAND (ref, 1)), 2630 stabilize_reference_1 (TREE_OPERAND (ref, 2))); 2631 break; 2632 2633 case ARRAY_REF: 2634 result = build_nt (ARRAY_REF, 2635 stabilize_reference (TREE_OPERAND (ref, 0)), 2636 stabilize_reference_1 (TREE_OPERAND (ref, 1)), 2637 TREE_OPERAND (ref, 2), TREE_OPERAND (ref, 3)); 2638 break; 2639 2640 case ARRAY_RANGE_REF: 2641 result = build_nt (ARRAY_RANGE_REF, 2642 stabilize_reference (TREE_OPERAND (ref, 0)), 2643 stabilize_reference_1 (TREE_OPERAND (ref, 1)), 2644 TREE_OPERAND (ref, 2), TREE_OPERAND (ref, 3)); 2645 break; 2646 2647 case COMPOUND_EXPR: 2648 /* We cannot wrap the first expression in a SAVE_EXPR, as then 2649 it wouldn't be ignored. This matters when dealing with 2650 volatiles. */ 2651 return stabilize_reference_1 (ref); 2652 2653 /* If arg isn't a kind of lvalue we recognize, make no change. 2654 Caller should recognize the error for an invalid lvalue. */ 2655 default: 2656 return ref; 2657 2658 case ERROR_MARK: 2659 return error_mark_node; 2660 } 2661 2662 TREE_TYPE (result) = TREE_TYPE (ref); 2663 TREE_READONLY (result) = TREE_READONLY (ref); 2664 TREE_SIDE_EFFECTS (result) = TREE_SIDE_EFFECTS (ref); 2665 TREE_THIS_VOLATILE (result) = TREE_THIS_VOLATILE (ref); 2666 2667 return result; 2668} 2669 2670/* Subroutine of stabilize_reference; this is called for subtrees of 2671 references. Any expression with side-effects must be put in a SAVE_EXPR 2672 to ensure that it is only evaluated once. 2673 2674 We don't put SAVE_EXPR nodes around everything, because assigning very 2675 simple expressions to temporaries causes us to miss good opportunities 2676 for optimizations. Among other things, the opportunity to fold in the 2677 addition of a constant into an addressing mode often gets lost, e.g. 2678 "y[i+1] += x;". In general, we take the approach that we should not make 2679 an assignment unless we are forced into it - i.e., that any non-side effect 2680 operator should be allowed, and that cse should take care of coalescing 2681 multiple utterances of the same expression should that prove fruitful. */ 2682 2683tree 2684stabilize_reference_1 (tree e) 2685{ 2686 tree result; 2687 enum tree_code code = TREE_CODE (e); 2688 2689 /* We cannot ignore const expressions because it might be a reference 2690 to a const array but whose index contains side-effects. But we can 2691 ignore things that are actual constant or that already have been 2692 handled by this function. */ 2693 2694 if (TREE_INVARIANT (e)) 2695 return e; 2696 2697 switch (TREE_CODE_CLASS (code)) 2698 { 2699 case tcc_exceptional: 2700 case tcc_type: 2701 case tcc_declaration: 2702 case tcc_comparison: 2703 case tcc_statement: 2704 case tcc_expression: 2705 case tcc_reference: 2706 /* If the expression has side-effects, then encase it in a SAVE_EXPR 2707 so that it will only be evaluated once. */ 2708 /* The reference (r) and comparison (<) classes could be handled as 2709 below, but it is generally faster to only evaluate them once. */ 2710 if (TREE_SIDE_EFFECTS (e)) 2711 return save_expr (e); 2712 return e; 2713 2714 case tcc_constant: 2715 /* Constants need no processing. In fact, we should never reach 2716 here. */ 2717 return e; 2718 2719 case tcc_binary: 2720 /* Division is slow and tends to be compiled with jumps, 2721 especially the division by powers of 2 that is often 2722 found inside of an array reference. So do it just once. */ 2723 if (code == TRUNC_DIV_EXPR || code == TRUNC_MOD_EXPR 2724 || code == FLOOR_DIV_EXPR || code == FLOOR_MOD_EXPR 2725 || code == CEIL_DIV_EXPR || code == CEIL_MOD_EXPR 2726 || code == ROUND_DIV_EXPR || code == ROUND_MOD_EXPR) 2727 return save_expr (e); 2728 /* Recursively stabilize each operand. */ 2729 result = build_nt (code, stabilize_reference_1 (TREE_OPERAND (e, 0)), 2730 stabilize_reference_1 (TREE_OPERAND (e, 1))); 2731 break; 2732 2733 case tcc_unary: 2734 /* Recursively stabilize each operand. */ 2735 result = build_nt (code, stabilize_reference_1 (TREE_OPERAND (e, 0))); 2736 break; 2737 2738 default: 2739 gcc_unreachable (); 2740 } 2741 2742 TREE_TYPE (result) = TREE_TYPE (e); 2743 TREE_READONLY (result) = TREE_READONLY (e); 2744 TREE_SIDE_EFFECTS (result) = TREE_SIDE_EFFECTS (e); 2745 TREE_THIS_VOLATILE (result) = TREE_THIS_VOLATILE (e); 2746 TREE_INVARIANT (result) = 1; 2747 2748 return result; 2749} 2750 2751/* Low-level constructors for expressions. */ 2752 2753/* A helper function for build1 and constant folders. Set TREE_CONSTANT, 2754 TREE_INVARIANT, and TREE_SIDE_EFFECTS for an ADDR_EXPR. */ 2755 2756void 2757recompute_tree_invariant_for_addr_expr (tree t) 2758{ 2759 tree node; 2760 bool tc = true, ti = true, se = false; 2761 2762 /* We started out assuming this address is both invariant and constant, but 2763 does not have side effects. Now go down any handled components and see if 2764 any of them involve offsets that are either non-constant or non-invariant. 2765 Also check for side-effects. 2766 2767 ??? Note that this code makes no attempt to deal with the case where 2768 taking the address of something causes a copy due to misalignment. */ 2769 2770#define UPDATE_TITCSE(NODE) \ 2771do { tree _node = (NODE); \ 2772 if (_node && !TREE_INVARIANT (_node)) ti = false; \ 2773 if (_node && !TREE_CONSTANT (_node)) tc = false; \ 2774 if (_node && TREE_SIDE_EFFECTS (_node)) se = true; } while (0) 2775 2776 for (node = TREE_OPERAND (t, 0); handled_component_p (node); 2777 node = TREE_OPERAND (node, 0)) 2778 { 2779 /* If the first operand doesn't have an ARRAY_TYPE, this is a bogus 2780 array reference (probably made temporarily by the G++ front end), 2781 so ignore all the operands. */ 2782 if ((TREE_CODE (node) == ARRAY_REF 2783 || TREE_CODE (node) == ARRAY_RANGE_REF) 2784 && TREE_CODE (TREE_TYPE (TREE_OPERAND (node, 0))) == ARRAY_TYPE) 2785 { 2786 UPDATE_TITCSE (TREE_OPERAND (node, 1)); 2787 if (TREE_OPERAND (node, 2)) 2788 UPDATE_TITCSE (TREE_OPERAND (node, 2)); 2789 if (TREE_OPERAND (node, 3)) 2790 UPDATE_TITCSE (TREE_OPERAND (node, 3)); 2791 } 2792 /* Likewise, just because this is a COMPONENT_REF doesn't mean we have a 2793 FIELD_DECL, apparently. The G++ front end can put something else 2794 there, at least temporarily. */ 2795 else if (TREE_CODE (node) == COMPONENT_REF 2796 && TREE_CODE (TREE_OPERAND (node, 1)) == FIELD_DECL) 2797 { 2798 if (TREE_OPERAND (node, 2)) 2799 UPDATE_TITCSE (TREE_OPERAND (node, 2)); 2800 } 2801 else if (TREE_CODE (node) == BIT_FIELD_REF) 2802 UPDATE_TITCSE (TREE_OPERAND (node, 2)); 2803 } 2804 2805 node = lang_hooks.expr_to_decl (node, &tc, &ti, &se); 2806 2807 /* Now see what's inside. If it's an INDIRECT_REF, copy our properties from 2808 the address, since &(*a)->b is a form of addition. If it's a decl, it's 2809 invariant and constant if the decl is static. It's also invariant if it's 2810 a decl in the current function. Taking the address of a volatile variable 2811 is not volatile. If it's a constant, the address is both invariant and 2812 constant. Otherwise it's neither. */ 2813 if (TREE_CODE (node) == INDIRECT_REF) 2814 UPDATE_TITCSE (TREE_OPERAND (node, 0)); 2815 else if (DECL_P (node)) 2816 { 2817 if (staticp (node)) 2818 ; 2819 else if (decl_function_context (node) == current_function_decl 2820 /* Addresses of thread-local variables are invariant. */ 2821 || (TREE_CODE (node) == VAR_DECL 2822 && DECL_THREAD_LOCAL_P (node))) 2823 tc = false; 2824 else 2825 ti = tc = false; 2826 } 2827 else if (CONSTANT_CLASS_P (node)) 2828 ; 2829 else 2830 { 2831 ti = tc = false; 2832 se |= TREE_SIDE_EFFECTS (node); 2833 } 2834 2835 TREE_CONSTANT (t) = tc; 2836 TREE_INVARIANT (t) = ti; 2837 TREE_SIDE_EFFECTS (t) = se; 2838#undef UPDATE_TITCSE 2839} 2840 2841/* Build an expression of code CODE, data type TYPE, and operands as 2842 specified. Expressions and reference nodes can be created this way. 2843 Constants, decls, types and misc nodes cannot be. 2844 2845 We define 5 non-variadic functions, from 0 to 4 arguments. This is 2846 enough for all extant tree codes. */ 2847 2848tree 2849build0_stat (enum tree_code code, tree tt MEM_STAT_DECL) 2850{ 2851 tree t; 2852 2853 gcc_assert (TREE_CODE_LENGTH (code) == 0); 2854 2855 t = make_node_stat (code PASS_MEM_STAT); 2856 TREE_TYPE (t) = tt; 2857 2858 return t; 2859} 2860 2861tree 2862build1_stat (enum tree_code code, tree type, tree node MEM_STAT_DECL) 2863{ 2864 int length = sizeof (struct tree_exp); 2865#ifdef GATHER_STATISTICS 2866 tree_node_kind kind; 2867#endif 2868 tree t; 2869 2870#ifdef GATHER_STATISTICS 2871 switch (TREE_CODE_CLASS (code)) 2872 { 2873 case tcc_statement: /* an expression with side effects */ 2874 kind = s_kind; 2875 break; 2876 case tcc_reference: /* a reference */ 2877 kind = r_kind; 2878 break; 2879 default: 2880 kind = e_kind; 2881 break; 2882 } 2883 2884 tree_node_counts[(int) kind]++; 2885 tree_node_sizes[(int) kind] += length; 2886#endif 2887 2888 gcc_assert (TREE_CODE_LENGTH (code) == 1); 2889 2890 t = ggc_alloc_zone_pass_stat (length, &tree_zone); 2891 2892 memset (t, 0, sizeof (struct tree_common)); 2893 2894 TREE_SET_CODE (t, code); 2895 2896 TREE_TYPE (t) = type; 2897#ifdef USE_MAPPED_LOCATION 2898 SET_EXPR_LOCATION (t, UNKNOWN_LOCATION); 2899#else 2900 SET_EXPR_LOCUS (t, NULL); 2901#endif 2902 TREE_COMPLEXITY (t) = 0; 2903 TREE_OPERAND (t, 0) = node; 2904 TREE_BLOCK (t) = NULL_TREE; 2905 if (node && !TYPE_P (node)) 2906 { 2907 TREE_SIDE_EFFECTS (t) = TREE_SIDE_EFFECTS (node); 2908 TREE_READONLY (t) = TREE_READONLY (node); 2909 } 2910 2911 if (TREE_CODE_CLASS (code) == tcc_statement) 2912 TREE_SIDE_EFFECTS (t) = 1; 2913 else switch (code) 2914 { 2915 case VA_ARG_EXPR: 2916 /* All of these have side-effects, no matter what their 2917 operands are. */ 2918 TREE_SIDE_EFFECTS (t) = 1; 2919 TREE_READONLY (t) = 0; 2920 break; 2921 2922 case MISALIGNED_INDIRECT_REF: 2923 case ALIGN_INDIRECT_REF: 2924 case INDIRECT_REF: 2925 /* Whether a dereference is readonly has nothing to do with whether 2926 its operand is readonly. */ 2927 TREE_READONLY (t) = 0; 2928 break; 2929 2930 case ADDR_EXPR: 2931 if (node) 2932 recompute_tree_invariant_for_addr_expr (t); 2933 break; 2934 2935 default: 2936 if ((TREE_CODE_CLASS (code) == tcc_unary || code == VIEW_CONVERT_EXPR) 2937 && node && !TYPE_P (node) 2938 && TREE_CONSTANT (node)) 2939 TREE_CONSTANT (t) = 1; 2940 if ((TREE_CODE_CLASS (code) == tcc_unary || code == VIEW_CONVERT_EXPR) 2941 && node && TREE_INVARIANT (node)) 2942 TREE_INVARIANT (t) = 1; 2943 if (TREE_CODE_CLASS (code) == tcc_reference 2944 && node && TREE_THIS_VOLATILE (node)) 2945 TREE_THIS_VOLATILE (t) = 1; 2946 break; 2947 } 2948 2949 return t; 2950} 2951 2952#define PROCESS_ARG(N) \ 2953 do { \ 2954 TREE_OPERAND (t, N) = arg##N; \ 2955 if (arg##N &&!TYPE_P (arg##N)) \ 2956 { \ 2957 if (TREE_SIDE_EFFECTS (arg##N)) \ 2958 side_effects = 1; \ 2959 if (!TREE_READONLY (arg##N)) \ 2960 read_only = 0; \ 2961 if (!TREE_CONSTANT (arg##N)) \ 2962 constant = 0; \ 2963 if (!TREE_INVARIANT (arg##N)) \ 2964 invariant = 0; \ 2965 } \ 2966 } while (0) 2967 2968tree 2969build2_stat (enum tree_code code, tree tt, tree arg0, tree arg1 MEM_STAT_DECL) 2970{ 2971 bool constant, read_only, side_effects, invariant; 2972 tree t; 2973 2974 gcc_assert (TREE_CODE_LENGTH (code) == 2); 2975 2976 t = make_node_stat (code PASS_MEM_STAT); 2977 TREE_TYPE (t) = tt; 2978 2979 /* Below, we automatically set TREE_SIDE_EFFECTS and TREE_READONLY for the 2980 result based on those same flags for the arguments. But if the 2981 arguments aren't really even `tree' expressions, we shouldn't be trying 2982 to do this. */ 2983 2984 /* Expressions without side effects may be constant if their 2985 arguments are as well. */ 2986 constant = (TREE_CODE_CLASS (code) == tcc_comparison 2987 || TREE_CODE_CLASS (code) == tcc_binary); 2988 read_only = 1; 2989 side_effects = TREE_SIDE_EFFECTS (t); 2990 invariant = constant; 2991 2992 PROCESS_ARG(0); 2993 PROCESS_ARG(1); 2994 2995 TREE_READONLY (t) = read_only; 2996 TREE_CONSTANT (t) = constant; 2997 TREE_INVARIANT (t) = invariant; 2998 TREE_SIDE_EFFECTS (t) = side_effects; 2999 TREE_THIS_VOLATILE (t) 3000 = (TREE_CODE_CLASS (code) == tcc_reference 3001 && arg0 && TREE_THIS_VOLATILE (arg0)); 3002 3003 return t; 3004} 3005 3006tree 3007build3_stat (enum tree_code code, tree tt, tree arg0, tree arg1, 3008 tree arg2 MEM_STAT_DECL) 3009{ 3010 bool constant, read_only, side_effects, invariant; 3011 tree t; 3012 3013 gcc_assert (TREE_CODE_LENGTH (code) == 3); 3014 3015 t = make_node_stat (code PASS_MEM_STAT); 3016 TREE_TYPE (t) = tt; 3017 3018 side_effects = TREE_SIDE_EFFECTS (t); 3019 3020 PROCESS_ARG(0); 3021 PROCESS_ARG(1); 3022 PROCESS_ARG(2); 3023 3024 if (code == CALL_EXPR && !side_effects) 3025 { 3026 tree node; 3027 int i; 3028 3029 /* Calls have side-effects, except those to const or 3030 pure functions. */ 3031 i = call_expr_flags (t); 3032 if (!(i & (ECF_CONST | ECF_PURE))) 3033 side_effects = 1; 3034 3035 /* And even those have side-effects if their arguments do. */ 3036 else for (node = arg1; node; node = TREE_CHAIN (node)) 3037 if (TREE_SIDE_EFFECTS (TREE_VALUE (node))) 3038 { 3039 side_effects = 1; 3040 break; 3041 } 3042 } 3043 3044 TREE_SIDE_EFFECTS (t) = side_effects; 3045 TREE_THIS_VOLATILE (t) 3046 = (TREE_CODE_CLASS (code) == tcc_reference 3047 && arg0 && TREE_THIS_VOLATILE (arg0)); 3048 3049 return t; 3050} 3051 3052tree 3053build4_stat (enum tree_code code, tree tt, tree arg0, tree arg1, 3054 tree arg2, tree arg3 MEM_STAT_DECL) 3055{ 3056 bool constant, read_only, side_effects, invariant; 3057 tree t; 3058 3059 gcc_assert (TREE_CODE_LENGTH (code) == 4); 3060 3061 t = make_node_stat (code PASS_MEM_STAT); 3062 TREE_TYPE (t) = tt; 3063 3064 side_effects = TREE_SIDE_EFFECTS (t); 3065 3066 PROCESS_ARG(0); 3067 PROCESS_ARG(1); 3068 PROCESS_ARG(2); 3069 PROCESS_ARG(3); 3070 3071 TREE_SIDE_EFFECTS (t) = side_effects; 3072 TREE_THIS_VOLATILE (t) 3073 = (TREE_CODE_CLASS (code) == tcc_reference 3074 && arg0 && TREE_THIS_VOLATILE (arg0)); 3075 3076 return t; 3077} 3078 3079tree 3080build5_stat (enum tree_code code, tree tt, tree arg0, tree arg1, 3081 tree arg2, tree arg3, tree arg4 MEM_STAT_DECL) 3082{ 3083 bool constant, read_only, side_effects, invariant; 3084 tree t; 3085 3086 gcc_assert (TREE_CODE_LENGTH (code) == 5); 3087 3088 t = make_node_stat (code PASS_MEM_STAT); 3089 TREE_TYPE (t) = tt; 3090 3091 side_effects = TREE_SIDE_EFFECTS (t); 3092 3093 PROCESS_ARG(0); 3094 PROCESS_ARG(1); 3095 PROCESS_ARG(2); 3096 PROCESS_ARG(3); 3097 PROCESS_ARG(4); 3098 3099 TREE_SIDE_EFFECTS (t) = side_effects; 3100 TREE_THIS_VOLATILE (t) 3101 = (TREE_CODE_CLASS (code) == tcc_reference 3102 && arg0 && TREE_THIS_VOLATILE (arg0)); 3103 3104 return t; 3105} 3106 3107tree 3108build7_stat (enum tree_code code, tree tt, tree arg0, tree arg1, 3109 tree arg2, tree arg3, tree arg4, tree arg5, 3110 tree arg6 MEM_STAT_DECL) 3111{ 3112 bool constant, read_only, side_effects, invariant; 3113 tree t; 3114 3115 gcc_assert (code == TARGET_MEM_REF); 3116 3117 t = make_node_stat (code PASS_MEM_STAT); 3118 TREE_TYPE (t) = tt; 3119 3120 side_effects = TREE_SIDE_EFFECTS (t); 3121 3122 PROCESS_ARG(0); 3123 PROCESS_ARG(1); 3124 PROCESS_ARG(2); 3125 PROCESS_ARG(3); 3126 PROCESS_ARG(4); 3127 PROCESS_ARG(5); 3128 PROCESS_ARG(6); 3129 3130 TREE_SIDE_EFFECTS (t) = side_effects; 3131 TREE_THIS_VOLATILE (t) = 0; 3132 3133 return t; 3134} 3135 3136/* Similar except don't specify the TREE_TYPE 3137 and leave the TREE_SIDE_EFFECTS as 0. 3138 It is permissible for arguments to be null, 3139 or even garbage if their values do not matter. */ 3140 3141tree 3142build_nt (enum tree_code code, ...) 3143{ 3144 tree t; 3145 int length; 3146 int i; 3147 va_list p; 3148 3149 va_start (p, code); 3150 3151 t = make_node (code); 3152 length = TREE_CODE_LENGTH (code); 3153 3154 for (i = 0; i < length; i++) 3155 TREE_OPERAND (t, i) = va_arg (p, tree); 3156 3157 va_end (p); 3158 return t; 3159} 3160 3161/* Create a DECL_... node of code CODE, name NAME and data type TYPE. 3162 We do NOT enter this node in any sort of symbol table. 3163 3164 layout_decl is used to set up the decl's storage layout. 3165 Other slots are initialized to 0 or null pointers. */ 3166 3167tree 3168build_decl_stat (enum tree_code code, tree name, tree type MEM_STAT_DECL) 3169{ 3170 tree t; 3171 3172 t = make_node_stat (code PASS_MEM_STAT); 3173 3174/* if (type == error_mark_node) 3175 type = integer_type_node; */ 3176/* That is not done, deliberately, so that having error_mark_node 3177 as the type can suppress useless errors in the use of this variable. */ 3178 3179 DECL_NAME (t) = name; 3180 TREE_TYPE (t) = type; 3181 3182 if (code == VAR_DECL || code == PARM_DECL || code == RESULT_DECL) 3183 layout_decl (t, 0); 3184 3185 return t; 3186} 3187 3188/* Builds and returns function declaration with NAME and TYPE. */ 3189 3190tree 3191build_fn_decl (const char *name, tree type) 3192{ 3193 tree id = get_identifier (name); 3194 tree decl = build_decl (FUNCTION_DECL, id, type); 3195 3196 DECL_EXTERNAL (decl) = 1; 3197 TREE_PUBLIC (decl) = 1; 3198 DECL_ARTIFICIAL (decl) = 1; 3199 TREE_NOTHROW (decl) = 1; 3200 3201 return decl; 3202} 3203 3204 3205/* BLOCK nodes are used to represent the structure of binding contours 3206 and declarations, once those contours have been exited and their contents 3207 compiled. This information is used for outputting debugging info. */ 3208 3209tree 3210build_block (tree vars, tree subblocks, tree supercontext, tree chain) 3211{ 3212 tree block = make_node (BLOCK); 3213 3214 BLOCK_VARS (block) = vars; 3215 BLOCK_SUBBLOCKS (block) = subblocks; 3216 BLOCK_SUPERCONTEXT (block) = supercontext; 3217 BLOCK_CHAIN (block) = chain; 3218 return block; 3219} 3220 3221#if 1 /* ! defined(USE_MAPPED_LOCATION) */ 3222/* ??? gengtype doesn't handle conditionals */ 3223static GTY(()) source_locus last_annotated_node; 3224#endif 3225 3226#ifdef USE_MAPPED_LOCATION 3227 3228expanded_location 3229expand_location (source_location loc) 3230{ 3231 expanded_location xloc; 3232 if (loc == 0) { xloc.file = NULL; xloc.line = 0; xloc.column = 0; } 3233 else 3234 { 3235 const struct line_map *map = linemap_lookup (&line_table, loc); 3236 xloc.file = map->to_file; 3237 xloc.line = SOURCE_LINE (map, loc); 3238 xloc.column = SOURCE_COLUMN (map, loc); 3239 }; 3240 return xloc; 3241} 3242 3243#else 3244 3245/* Record the exact location where an expression or an identifier were 3246 encountered. */ 3247 3248void 3249annotate_with_file_line (tree node, const char *file, int line) 3250{ 3251 /* Roughly one percent of the calls to this function are to annotate 3252 a node with the same information already attached to that node! 3253 Just return instead of wasting memory. */ 3254 if (EXPR_LOCUS (node) 3255 && EXPR_LINENO (node) == line 3256 && (EXPR_FILENAME (node) == file 3257 || !strcmp (EXPR_FILENAME (node), file))) 3258 { 3259 last_annotated_node = EXPR_LOCUS (node); 3260 return; 3261 } 3262 3263 /* In heavily macroized code (such as GCC itself) this single 3264 entry cache can reduce the number of allocations by more 3265 than half. */ 3266 if (last_annotated_node 3267 && last_annotated_node->line == line 3268 && (last_annotated_node->file == file 3269 || !strcmp (last_annotated_node->file, file))) 3270 { 3271 SET_EXPR_LOCUS (node, last_annotated_node); 3272 return; 3273 } 3274 3275 SET_EXPR_LOCUS (node, ggc_alloc (sizeof (location_t))); 3276 EXPR_LINENO (node) = line; 3277 EXPR_FILENAME (node) = file; 3278 last_annotated_node = EXPR_LOCUS (node); 3279} 3280 3281void 3282annotate_with_locus (tree node, location_t locus) 3283{ 3284 annotate_with_file_line (node, locus.file, locus.line); 3285} 3286#endif 3287 3288/* Return a declaration like DDECL except that its DECL_ATTRIBUTES 3289 is ATTRIBUTE. */ 3290 3291tree 3292build_decl_attribute_variant (tree ddecl, tree attribute) 3293{ 3294 DECL_ATTRIBUTES (ddecl) = attribute; 3295 return ddecl; 3296} 3297 3298/* Borrowed from hashtab.c iterative_hash implementation. */ 3299#define mix(a,b,c) \ 3300{ \ 3301 a -= b; a -= c; a ^= (c>>13); \ 3302 b -= c; b -= a; b ^= (a<< 8); \ 3303 c -= a; c -= b; c ^= ((b&0xffffffff)>>13); \ 3304 a -= b; a -= c; a ^= ((c&0xffffffff)>>12); \ 3305 b -= c; b -= a; b = (b ^ (a<<16)) & 0xffffffff; \ 3306 c -= a; c -= b; c = (c ^ (b>> 5)) & 0xffffffff; \ 3307 a -= b; a -= c; a = (a ^ (c>> 3)) & 0xffffffff; \ 3308 b -= c; b -= a; b = (b ^ (a<<10)) & 0xffffffff; \ 3309 c -= a; c -= b; c = (c ^ (b>>15)) & 0xffffffff; \ 3310} 3311 3312 3313/* Produce good hash value combining VAL and VAL2. */ 3314static inline hashval_t 3315iterative_hash_hashval_t (hashval_t val, hashval_t val2) 3316{ 3317 /* the golden ratio; an arbitrary value. */ 3318 hashval_t a = 0x9e3779b9; 3319 3320 mix (a, val, val2); 3321 return val2; 3322} 3323 3324/* Produce good hash value combining PTR and VAL2. */ 3325static inline hashval_t 3326iterative_hash_pointer (void *ptr, hashval_t val2) 3327{ 3328 if (sizeof (ptr) == sizeof (hashval_t)) 3329 return iterative_hash_hashval_t ((size_t) ptr, val2); 3330 else 3331 { 3332 hashval_t a = (hashval_t) (size_t) ptr; 3333 /* Avoid warnings about shifting of more than the width of the type on 3334 hosts that won't execute this path. */ 3335 int zero = 0; 3336 hashval_t b = (hashval_t) ((size_t) ptr >> (sizeof (hashval_t) * 8 + zero)); 3337 mix (a, b, val2); 3338 return val2; 3339 } 3340} 3341 3342/* Produce good hash value combining VAL and VAL2. */ 3343static inline hashval_t 3344iterative_hash_host_wide_int (HOST_WIDE_INT val, hashval_t val2) 3345{ 3346 if (sizeof (HOST_WIDE_INT) == sizeof (hashval_t)) 3347 return iterative_hash_hashval_t (val, val2); 3348 else 3349 { 3350 hashval_t a = (hashval_t) val; 3351 /* Avoid warnings about shifting of more than the width of the type on 3352 hosts that won't execute this path. */ 3353 int zero = 0; 3354 hashval_t b = (hashval_t) (val >> (sizeof (hashval_t) * 8 + zero)); 3355 mix (a, b, val2); 3356 if (sizeof (HOST_WIDE_INT) > 2 * sizeof (hashval_t)) 3357 { 3358 hashval_t a = (hashval_t) (val >> (sizeof (hashval_t) * 16 + zero)); 3359 hashval_t b = (hashval_t) (val >> (sizeof (hashval_t) * 24 + zero)); 3360 mix (a, b, val2); 3361 } 3362 return val2; 3363 } 3364} 3365 3366/* Return a type like TTYPE except that its TYPE_ATTRIBUTE 3367 is ATTRIBUTE and its qualifiers are QUALS. 3368 3369 Record such modified types already made so we don't make duplicates. */ 3370 3371static tree 3372build_type_attribute_qual_variant (tree ttype, tree attribute, int quals) 3373{ 3374 if (! attribute_list_equal (TYPE_ATTRIBUTES (ttype), attribute)) 3375 { 3376 hashval_t hashcode = 0; 3377 tree ntype; 3378 enum tree_code code = TREE_CODE (ttype); 3379 3380 ntype = copy_node (ttype); 3381 3382 TYPE_POINTER_TO (ntype) = 0; 3383 TYPE_REFERENCE_TO (ntype) = 0; 3384 TYPE_ATTRIBUTES (ntype) = attribute; 3385 3386 /* Create a new main variant of TYPE. */ 3387 TYPE_MAIN_VARIANT (ntype) = ntype; 3388 TYPE_NEXT_VARIANT (ntype) = 0; 3389 set_type_quals (ntype, TYPE_UNQUALIFIED); 3390 3391 hashcode = iterative_hash_object (code, hashcode); 3392 if (TREE_TYPE (ntype)) 3393 hashcode = iterative_hash_object (TYPE_HASH (TREE_TYPE (ntype)), 3394 hashcode); 3395 hashcode = attribute_hash_list (attribute, hashcode); 3396 3397 switch (TREE_CODE (ntype)) 3398 { 3399 case FUNCTION_TYPE: 3400 hashcode = type_hash_list (TYPE_ARG_TYPES (ntype), hashcode); 3401 break; 3402 case ARRAY_TYPE: 3403 hashcode = iterative_hash_object (TYPE_HASH (TYPE_DOMAIN (ntype)), 3404 hashcode); 3405 break; 3406 case INTEGER_TYPE: 3407 hashcode = iterative_hash_object 3408 (TREE_INT_CST_LOW (TYPE_MAX_VALUE (ntype)), hashcode); 3409 hashcode = iterative_hash_object 3410 (TREE_INT_CST_HIGH (TYPE_MAX_VALUE (ntype)), hashcode); 3411 break; 3412 case REAL_TYPE: 3413 { 3414 unsigned int precision = TYPE_PRECISION (ntype); 3415 hashcode = iterative_hash_object (precision, hashcode); 3416 } 3417 break; 3418 default: 3419 break; 3420 } 3421 3422 ntype = type_hash_canon (hashcode, ntype); 3423 ttype = build_qualified_type (ntype, quals); 3424 } 3425 3426 return ttype; 3427} 3428 3429 3430/* Return a type like TTYPE except that its TYPE_ATTRIBUTE 3431 is ATTRIBUTE. 3432 3433 Record such modified types already made so we don't make duplicates. */ 3434 3435tree 3436build_type_attribute_variant (tree ttype, tree attribute) 3437{ 3438 return build_type_attribute_qual_variant (ttype, attribute, 3439 TYPE_QUALS (ttype)); 3440} 3441 3442/* Return nonzero if IDENT is a valid name for attribute ATTR, 3443 or zero if not. 3444 3445 We try both `text' and `__text__', ATTR may be either one. */ 3446/* ??? It might be a reasonable simplification to require ATTR to be only 3447 `text'. One might then also require attribute lists to be stored in 3448 their canonicalized form. */ 3449 3450static int 3451is_attribute_with_length_p (const char *attr, int attr_len, tree ident) 3452{ 3453 int ident_len; 3454 const char *p; 3455 3456 if (TREE_CODE (ident) != IDENTIFIER_NODE) 3457 return 0; 3458 3459 p = IDENTIFIER_POINTER (ident); 3460 ident_len = IDENTIFIER_LENGTH (ident); 3461 3462 if (ident_len == attr_len 3463 && strcmp (attr, p) == 0) 3464 return 1; 3465 3466 /* If ATTR is `__text__', IDENT must be `text'; and vice versa. */ 3467 if (attr[0] == '_') 3468 { 3469 gcc_assert (attr[1] == '_'); 3470 gcc_assert (attr[attr_len - 2] == '_'); 3471 gcc_assert (attr[attr_len - 1] == '_'); 3472 if (ident_len == attr_len - 4 3473 && strncmp (attr + 2, p, attr_len - 4) == 0) 3474 return 1; 3475 } 3476 else 3477 { 3478 if (ident_len == attr_len + 4 3479 && p[0] == '_' && p[1] == '_' 3480 && p[ident_len - 2] == '_' && p[ident_len - 1] == '_' 3481 && strncmp (attr, p + 2, attr_len) == 0) 3482 return 1; 3483 } 3484 3485 return 0; 3486} 3487 3488/* Return nonzero if IDENT is a valid name for attribute ATTR, 3489 or zero if not. 3490 3491 We try both `text' and `__text__', ATTR may be either one. */ 3492 3493int 3494is_attribute_p (const char *attr, tree ident) 3495{ 3496 return is_attribute_with_length_p (attr, strlen (attr), ident); 3497} 3498 3499/* Given an attribute name and a list of attributes, return a pointer to the 3500 attribute's list element if the attribute is part of the list, or NULL_TREE 3501 if not found. If the attribute appears more than once, this only 3502 returns the first occurrence; the TREE_CHAIN of the return value should 3503 be passed back in if further occurrences are wanted. */ 3504 3505tree 3506lookup_attribute (const char *attr_name, tree list) 3507{ 3508 tree l; 3509 size_t attr_len = strlen (attr_name); 3510 3511 for (l = list; l; l = TREE_CHAIN (l)) 3512 { 3513 gcc_assert (TREE_CODE (TREE_PURPOSE (l)) == IDENTIFIER_NODE); 3514 if (is_attribute_with_length_p (attr_name, attr_len, TREE_PURPOSE (l))) 3515 return l; 3516 } 3517 3518 return NULL_TREE; 3519} 3520 3521/* Remove any instances of attribute ATTR_NAME in LIST and return the 3522 modified list. */ 3523 3524tree 3525remove_attribute (const char *attr_name, tree list) 3526{ 3527 tree *p; 3528 size_t attr_len = strlen (attr_name); 3529 3530 for (p = &list; *p; ) 3531 { 3532 tree l = *p; 3533 gcc_assert (TREE_CODE (TREE_PURPOSE (l)) == IDENTIFIER_NODE); 3534 if (is_attribute_with_length_p (attr_name, attr_len, TREE_PURPOSE (l))) 3535 *p = TREE_CHAIN (l); 3536 else 3537 p = &TREE_CHAIN (l); 3538 } 3539 3540 return list; 3541} 3542 3543/* Return an attribute list that is the union of a1 and a2. */ 3544 3545tree 3546merge_attributes (tree a1, tree a2) 3547{ 3548 tree attributes; 3549 3550 /* Either one unset? Take the set one. */ 3551 3552 if ((attributes = a1) == 0) 3553 attributes = a2; 3554 3555 /* One that completely contains the other? Take it. */ 3556 3557 else if (a2 != 0 && ! attribute_list_contained (a1, a2)) 3558 { 3559 if (attribute_list_contained (a2, a1)) 3560 attributes = a2; 3561 else 3562 { 3563 /* Pick the longest list, and hang on the other list. */ 3564 3565 if (list_length (a1) < list_length (a2)) 3566 attributes = a2, a2 = a1; 3567 3568 for (; a2 != 0; a2 = TREE_CHAIN (a2)) 3569 { 3570 tree a; 3571 for (a = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (a2)), 3572 attributes); 3573 a != NULL_TREE; 3574 a = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (a2)), 3575 TREE_CHAIN (a))) 3576 { 3577 if (TREE_VALUE (a) != NULL 3578 && TREE_CODE (TREE_VALUE (a)) == TREE_LIST 3579 && TREE_VALUE (a2) != NULL 3580 && TREE_CODE (TREE_VALUE (a2)) == TREE_LIST) 3581 { 3582 if (simple_cst_list_equal (TREE_VALUE (a), 3583 TREE_VALUE (a2)) == 1) 3584 break; 3585 } 3586 else if (simple_cst_equal (TREE_VALUE (a), 3587 TREE_VALUE (a2)) == 1) 3588 break; 3589 } 3590 if (a == NULL_TREE) 3591 { 3592 a1 = copy_node (a2); 3593 TREE_CHAIN (a1) = attributes; 3594 attributes = a1; 3595 } 3596 } 3597 } 3598 } 3599 return attributes; 3600} 3601 3602/* Given types T1 and T2, merge their attributes and return 3603 the result. */ 3604 3605tree 3606merge_type_attributes (tree t1, tree t2) 3607{ 3608 return merge_attributes (TYPE_ATTRIBUTES (t1), 3609 TYPE_ATTRIBUTES (t2)); 3610} 3611 3612/* Given decls OLDDECL and NEWDECL, merge their attributes and return 3613 the result. */ 3614 3615tree 3616merge_decl_attributes (tree olddecl, tree newdecl) 3617{ 3618 return merge_attributes (DECL_ATTRIBUTES (olddecl), 3619 DECL_ATTRIBUTES (newdecl)); 3620} 3621 3622#if TARGET_DLLIMPORT_DECL_ATTRIBUTES 3623 3624/* Specialization of merge_decl_attributes for various Windows targets. 3625 3626 This handles the following situation: 3627 3628 __declspec (dllimport) int foo; 3629 int foo; 3630 3631 The second instance of `foo' nullifies the dllimport. */ 3632 3633tree 3634merge_dllimport_decl_attributes (tree old, tree new) 3635{ 3636 tree a; 3637 int delete_dllimport_p = 1; 3638 3639 /* What we need to do here is remove from `old' dllimport if it doesn't 3640 appear in `new'. dllimport behaves like extern: if a declaration is 3641 marked dllimport and a definition appears later, then the object 3642 is not dllimport'd. We also remove a `new' dllimport if the old list 3643 contains dllexport: dllexport always overrides dllimport, regardless 3644 of the order of declaration. */ 3645 if (!VAR_OR_FUNCTION_DECL_P (new)) 3646 delete_dllimport_p = 0; 3647 else if (DECL_DLLIMPORT_P (new) 3648 && lookup_attribute ("dllexport", DECL_ATTRIBUTES (old))) 3649 { 3650 DECL_DLLIMPORT_P (new) = 0; 3651 warning (OPT_Wattributes, "%q+D already declared with dllexport attribute: " 3652 "dllimport ignored", new); 3653 } 3654 else if (DECL_DLLIMPORT_P (old) && !DECL_DLLIMPORT_P (new)) 3655 { 3656 /* Warn about overriding a symbol that has already been used. eg: 3657 extern int __attribute__ ((dllimport)) foo; 3658 int* bar () {return &foo;} 3659 int foo; 3660 */ 3661 if (TREE_USED (old)) 3662 { 3663 warning (0, "%q+D redeclared without dllimport attribute " 3664 "after being referenced with dll linkage", new); 3665 /* If we have used a variable's address with dllimport linkage, 3666 keep the old DECL_DLLIMPORT_P flag: the ADDR_EXPR using the 3667 decl may already have had TREE_INVARIANT and TREE_CONSTANT 3668 computed. 3669 We still remove the attribute so that assembler code refers 3670 to '&foo rather than '_imp__foo'. */ 3671 if (TREE_CODE (old) == VAR_DECL && TREE_ADDRESSABLE (old)) 3672 DECL_DLLIMPORT_P (new) = 1; 3673 } 3674 3675 /* Let an inline definition silently override the external reference, 3676 but otherwise warn about attribute inconsistency. */ 3677 else if (TREE_CODE (new) == VAR_DECL 3678 || !DECL_DECLARED_INLINE_P (new)) 3679 warning (OPT_Wattributes, "%q+D redeclared without dllimport attribute: " 3680 "previous dllimport ignored", new); 3681 } 3682 else 3683 delete_dllimport_p = 0; 3684 3685 a = merge_attributes (DECL_ATTRIBUTES (old), DECL_ATTRIBUTES (new)); 3686 3687 if (delete_dllimport_p) 3688 { 3689 tree prev, t; 3690 const size_t attr_len = strlen ("dllimport"); 3691 3692 /* Scan the list for dllimport and delete it. */ 3693 for (prev = NULL_TREE, t = a; t; prev = t, t = TREE_CHAIN (t)) 3694 { 3695 if (is_attribute_with_length_p ("dllimport", attr_len, 3696 TREE_PURPOSE (t))) 3697 { 3698 if (prev == NULL_TREE) 3699 a = TREE_CHAIN (a); 3700 else 3701 TREE_CHAIN (prev) = TREE_CHAIN (t); 3702 break; 3703 } 3704 } 3705 } 3706 3707 return a; 3708} 3709 3710/* Handle a "dllimport" or "dllexport" attribute; arguments as in 3711 struct attribute_spec.handler. */ 3712 3713tree 3714handle_dll_attribute (tree * pnode, tree name, tree args, int flags, 3715 bool *no_add_attrs) 3716{ 3717 tree node = *pnode; 3718 3719 /* These attributes may apply to structure and union types being created, 3720 but otherwise should pass to the declaration involved. */ 3721 if (!DECL_P (node)) 3722 { 3723 if (flags & ((int) ATTR_FLAG_DECL_NEXT | (int) ATTR_FLAG_FUNCTION_NEXT 3724 | (int) ATTR_FLAG_ARRAY_NEXT)) 3725 { 3726 *no_add_attrs = true; 3727 return tree_cons (name, args, NULL_TREE); 3728 } 3729 if (TREE_CODE (node) != RECORD_TYPE && TREE_CODE (node) != UNION_TYPE) 3730 { 3731 warning (OPT_Wattributes, "%qs attribute ignored", 3732 IDENTIFIER_POINTER (name)); 3733 *no_add_attrs = true; 3734 } 3735 3736 return NULL_TREE; 3737 } 3738 3739 if (TREE_CODE (node) != FUNCTION_DECL 3740 && TREE_CODE (node) != VAR_DECL) 3741 { 3742 *no_add_attrs = true; 3743 warning (OPT_Wattributes, "%qs attribute ignored", 3744 IDENTIFIER_POINTER (name)); 3745 return NULL_TREE; 3746 } 3747 3748 /* Report error on dllimport ambiguities seen now before they cause 3749 any damage. */ 3750 else if (is_attribute_p ("dllimport", name)) 3751 { 3752 /* Honor any target-specific overrides. */ 3753 if (!targetm.valid_dllimport_attribute_p (node)) 3754 *no_add_attrs = true; 3755 3756 else if (TREE_CODE (node) == FUNCTION_DECL 3757 && DECL_DECLARED_INLINE_P (node)) 3758 { 3759 warning (OPT_Wattributes, "inline function %q+D declared as " 3760 " dllimport: attribute ignored", node); 3761 *no_add_attrs = true; 3762 } 3763 /* Like MS, treat definition of dllimported variables and 3764 non-inlined functions on declaration as syntax errors. */ 3765 else if (TREE_CODE (node) == FUNCTION_DECL && DECL_INITIAL (node)) 3766 { 3767 error ("function %q+D definition is marked dllimport", node); 3768 *no_add_attrs = true; 3769 } 3770 3771 else if (TREE_CODE (node) == VAR_DECL) 3772 { 3773 if (DECL_INITIAL (node)) 3774 { 3775 error ("variable %q+D definition is marked dllimport", 3776 node); 3777 *no_add_attrs = true; 3778 } 3779 3780 /* `extern' needn't be specified with dllimport. 3781 Specify `extern' now and hope for the best. Sigh. */ 3782 DECL_EXTERNAL (node) = 1; 3783 /* Also, implicitly give dllimport'd variables declared within 3784 a function global scope, unless declared static. */ 3785 if (current_function_decl != NULL_TREE && !TREE_STATIC (node)) 3786 TREE_PUBLIC (node) = 1; 3787 } 3788 3789 if (*no_add_attrs == false) 3790 DECL_DLLIMPORT_P (node) = 1; 3791 } 3792 3793 /* Report error if symbol is not accessible at global scope. */ 3794 if (!TREE_PUBLIC (node) 3795 && (TREE_CODE (node) == VAR_DECL 3796 || TREE_CODE (node) == FUNCTION_DECL)) 3797 { 3798 error ("external linkage required for symbol %q+D because of " 3799 "%qs attribute", node, IDENTIFIER_POINTER (name)); 3800 *no_add_attrs = true; 3801 } 3802 3803 return NULL_TREE; 3804} 3805 3806#endif /* TARGET_DLLIMPORT_DECL_ATTRIBUTES */ 3807 3808/* Set the type qualifiers for TYPE to TYPE_QUALS, which is a bitmask 3809 of the various TYPE_QUAL values. */ 3810 3811static void 3812set_type_quals (tree type, int type_quals) 3813{ 3814 TYPE_READONLY (type) = (type_quals & TYPE_QUAL_CONST) != 0; 3815 TYPE_VOLATILE (type) = (type_quals & TYPE_QUAL_VOLATILE) != 0; 3816 TYPE_RESTRICT (type) = (type_quals & TYPE_QUAL_RESTRICT) != 0; 3817} 3818 3819/* Returns true iff cand is equivalent to base with type_quals. */ 3820 3821bool 3822check_qualified_type (tree cand, tree base, int type_quals) 3823{ 3824 return (TYPE_QUALS (cand) == type_quals 3825 && TYPE_NAME (cand) == TYPE_NAME (base) 3826 /* Apparently this is needed for Objective-C. */ 3827 && TYPE_CONTEXT (cand) == TYPE_CONTEXT (base) 3828 && attribute_list_equal (TYPE_ATTRIBUTES (cand), 3829 TYPE_ATTRIBUTES (base))); 3830} 3831 3832/* Return a version of the TYPE, qualified as indicated by the 3833 TYPE_QUALS, if one exists. If no qualified version exists yet, 3834 return NULL_TREE. */ 3835 3836tree 3837get_qualified_type (tree type, int type_quals) 3838{ 3839 tree t; 3840 3841 if (TYPE_QUALS (type) == type_quals) 3842 return type; 3843 3844 /* Search the chain of variants to see if there is already one there just 3845 like the one we need to have. If so, use that existing one. We must 3846 preserve the TYPE_NAME, since there is code that depends on this. */ 3847 for (t = TYPE_MAIN_VARIANT (type); t; t = TYPE_NEXT_VARIANT (t)) 3848 if (check_qualified_type (t, type, type_quals)) 3849 return t; 3850 3851 return NULL_TREE; 3852} 3853 3854/* Like get_qualified_type, but creates the type if it does not 3855 exist. This function never returns NULL_TREE. */ 3856 3857tree 3858build_qualified_type (tree type, int type_quals) 3859{ 3860 tree t; 3861 3862 /* See if we already have the appropriate qualified variant. */ 3863 t = get_qualified_type (type, type_quals); 3864 3865 /* If not, build it. */ 3866 if (!t) 3867 { 3868 t = build_variant_type_copy (type); 3869 set_type_quals (t, type_quals); 3870 } 3871 3872 return t; 3873} 3874 3875/* Create a new distinct copy of TYPE. The new type is made its own 3876 MAIN_VARIANT. */ 3877 3878tree 3879build_distinct_type_copy (tree type) 3880{ 3881 tree t = copy_node (type); 3882 3883 TYPE_POINTER_TO (t) = 0; 3884 TYPE_REFERENCE_TO (t) = 0; 3885 3886 /* Make it its own variant. */ 3887 TYPE_MAIN_VARIANT (t) = t; 3888 TYPE_NEXT_VARIANT (t) = 0; 3889 3890 /* Note that it is now possible for TYPE_MIN_VALUE to be a value 3891 whose TREE_TYPE is not t. This can also happen in the Ada 3892 frontend when using subtypes. */ 3893 3894 return t; 3895} 3896 3897/* Create a new variant of TYPE, equivalent but distinct. 3898 This is so the caller can modify it. */ 3899 3900tree 3901build_variant_type_copy (tree type) 3902{ 3903 tree t, m = TYPE_MAIN_VARIANT (type); 3904 3905 t = build_distinct_type_copy (type); 3906 3907 /* Add the new type to the chain of variants of TYPE. */ 3908 TYPE_NEXT_VARIANT (t) = TYPE_NEXT_VARIANT (m); 3909 TYPE_NEXT_VARIANT (m) = t; 3910 TYPE_MAIN_VARIANT (t) = m; 3911 3912 return t; 3913} 3914 3915/* Return true if the from tree in both tree maps are equal. */ 3916 3917int 3918tree_map_eq (const void *va, const void *vb) 3919{ 3920 const struct tree_map *a = va, *b = vb; 3921 return (a->from == b->from); 3922} 3923 3924/* Hash a from tree in a tree_map. */ 3925 3926unsigned int 3927tree_map_hash (const void *item) 3928{ 3929 return (((const struct tree_map *) item)->hash); 3930} 3931 3932/* Return true if this tree map structure is marked for garbage collection 3933 purposes. We simply return true if the from tree is marked, so that this 3934 structure goes away when the from tree goes away. */ 3935 3936int 3937tree_map_marked_p (const void *p) 3938{ 3939 tree from = ((struct tree_map *) p)->from; 3940 3941 return ggc_marked_p (from); 3942} 3943 3944/* Return true if the trees in the tree_int_map *'s VA and VB are equal. */ 3945 3946static int 3947tree_int_map_eq (const void *va, const void *vb) 3948{ 3949 const struct tree_int_map *a = va, *b = vb; 3950 return (a->from == b->from); 3951} 3952 3953/* Hash a from tree in the tree_int_map * ITEM. */ 3954 3955static unsigned int 3956tree_int_map_hash (const void *item) 3957{ 3958 return htab_hash_pointer (((const struct tree_int_map *)item)->from); 3959} 3960 3961/* Return true if this tree int map structure is marked for garbage collection 3962 purposes. We simply return true if the from tree_int_map *P's from tree is marked, so that this 3963 structure goes away when the from tree goes away. */ 3964 3965static int 3966tree_int_map_marked_p (const void *p) 3967{ 3968 tree from = ((struct tree_int_map *) p)->from; 3969 3970 return ggc_marked_p (from); 3971} 3972/* Lookup an init priority for FROM, and return it if we find one. */ 3973 3974unsigned short 3975decl_init_priority_lookup (tree from) 3976{ 3977 struct tree_int_map *h, in; 3978 in.from = from; 3979 3980 h = htab_find_with_hash (init_priority_for_decl, 3981 &in, htab_hash_pointer (from)); 3982 if (h) 3983 return h->to; 3984 return 0; 3985} 3986 3987/* Insert a mapping FROM->TO in the init priority hashtable. */ 3988 3989void 3990decl_init_priority_insert (tree from, unsigned short to) 3991{ 3992 struct tree_int_map *h; 3993 void **loc; 3994 3995 h = ggc_alloc (sizeof (struct tree_int_map)); 3996 h->from = from; 3997 h->to = to; 3998 loc = htab_find_slot_with_hash (init_priority_for_decl, h, 3999 htab_hash_pointer (from), INSERT); 4000 *(struct tree_int_map **) loc = h; 4001} 4002 4003/* Look up a restrict qualified base decl for FROM. */ 4004 4005tree 4006decl_restrict_base_lookup (tree from) 4007{ 4008 struct tree_map *h; 4009 struct tree_map in; 4010 4011 in.from = from; 4012 h = htab_find_with_hash (restrict_base_for_decl, &in, 4013 htab_hash_pointer (from)); 4014 return h ? h->to : NULL_TREE; 4015} 4016 4017/* Record the restrict qualified base TO for FROM. */ 4018 4019void 4020decl_restrict_base_insert (tree from, tree to) 4021{ 4022 struct tree_map *h; 4023 void **loc; 4024 4025 h = ggc_alloc (sizeof (struct tree_map)); 4026 h->hash = htab_hash_pointer (from); 4027 h->from = from; 4028 h->to = to; 4029 loc = htab_find_slot_with_hash (restrict_base_for_decl, h, h->hash, INSERT); 4030 *(struct tree_map **) loc = h; 4031} 4032 4033/* Print out the statistics for the DECL_DEBUG_EXPR hash table. */ 4034 4035static void 4036print_debug_expr_statistics (void) 4037{ 4038 fprintf (stderr, "DECL_DEBUG_EXPR hash: size %ld, %ld elements, %f collisions\n", 4039 (long) htab_size (debug_expr_for_decl), 4040 (long) htab_elements (debug_expr_for_decl), 4041 htab_collisions (debug_expr_for_decl)); 4042} 4043 4044/* Print out the statistics for the DECL_VALUE_EXPR hash table. */ 4045 4046static void 4047print_value_expr_statistics (void) 4048{ 4049 fprintf (stderr, "DECL_VALUE_EXPR hash: size %ld, %ld elements, %f collisions\n", 4050 (long) htab_size (value_expr_for_decl), 4051 (long) htab_elements (value_expr_for_decl), 4052 htab_collisions (value_expr_for_decl)); 4053} 4054 4055/* Print out statistics for the RESTRICT_BASE_FOR_DECL hash table, but 4056 don't print anything if the table is empty. */ 4057 4058static void 4059print_restrict_base_statistics (void) 4060{ 4061 if (htab_elements (restrict_base_for_decl) != 0) 4062 fprintf (stderr, 4063 "RESTRICT_BASE hash: size %ld, %ld elements, %f collisions\n", 4064 (long) htab_size (restrict_base_for_decl), 4065 (long) htab_elements (restrict_base_for_decl), 4066 htab_collisions (restrict_base_for_decl)); 4067} 4068 4069/* Lookup a debug expression for FROM, and return it if we find one. */ 4070 4071tree 4072decl_debug_expr_lookup (tree from) 4073{ 4074 struct tree_map *h, in; 4075 in.from = from; 4076 4077 h = htab_find_with_hash (debug_expr_for_decl, &in, htab_hash_pointer (from)); 4078 if (h) 4079 return h->to; 4080 return NULL_TREE; 4081} 4082 4083/* Insert a mapping FROM->TO in the debug expression hashtable. */ 4084 4085void 4086decl_debug_expr_insert (tree from, tree to) 4087{ 4088 struct tree_map *h; 4089 void **loc; 4090 4091 h = ggc_alloc (sizeof (struct tree_map)); 4092 h->hash = htab_hash_pointer (from); 4093 h->from = from; 4094 h->to = to; 4095 loc = htab_find_slot_with_hash (debug_expr_for_decl, h, h->hash, INSERT); 4096 *(struct tree_map **) loc = h; 4097} 4098 4099/* Lookup a value expression for FROM, and return it if we find one. */ 4100 4101tree 4102decl_value_expr_lookup (tree from) 4103{ 4104 struct tree_map *h, in; 4105 in.from = from; 4106 4107 h = htab_find_with_hash (value_expr_for_decl, &in, htab_hash_pointer (from)); 4108 if (h) 4109 return h->to; 4110 return NULL_TREE; 4111} 4112 4113/* Insert a mapping FROM->TO in the value expression hashtable. */ 4114 4115void 4116decl_value_expr_insert (tree from, tree to) 4117{ 4118 struct tree_map *h; 4119 void **loc; 4120 4121 h = ggc_alloc (sizeof (struct tree_map)); 4122 h->hash = htab_hash_pointer (from); 4123 h->from = from; 4124 h->to = to; 4125 loc = htab_find_slot_with_hash (value_expr_for_decl, h, h->hash, INSERT); 4126 *(struct tree_map **) loc = h; 4127} 4128 4129/* Hashing of types so that we don't make duplicates. 4130 The entry point is `type_hash_canon'. */ 4131 4132/* Compute a hash code for a list of types (chain of TREE_LIST nodes 4133 with types in the TREE_VALUE slots), by adding the hash codes 4134 of the individual types. */ 4135 4136unsigned int 4137type_hash_list (tree list, hashval_t hashcode) 4138{ 4139 tree tail; 4140 4141 for (tail = list; tail; tail = TREE_CHAIN (tail)) 4142 if (TREE_VALUE (tail) != error_mark_node) 4143 hashcode = iterative_hash_object (TYPE_HASH (TREE_VALUE (tail)), 4144 hashcode); 4145 4146 return hashcode; 4147} 4148 4149/* These are the Hashtable callback functions. */ 4150 4151/* Returns true iff the types are equivalent. */ 4152 4153static int 4154type_hash_eq (const void *va, const void *vb) 4155{ 4156 const struct type_hash *a = va, *b = vb; 4157 4158 /* First test the things that are the same for all types. */ 4159 if (a->hash != b->hash 4160 || TREE_CODE (a->type) != TREE_CODE (b->type) 4161 || TREE_TYPE (a->type) != TREE_TYPE (b->type) 4162 || !attribute_list_equal (TYPE_ATTRIBUTES (a->type), 4163 TYPE_ATTRIBUTES (b->type)) 4164 || TYPE_ALIGN (a->type) != TYPE_ALIGN (b->type) 4165 || TYPE_MODE (a->type) != TYPE_MODE (b->type)) 4166 return 0; 4167 4168 switch (TREE_CODE (a->type)) 4169 { 4170 case VOID_TYPE: 4171 case COMPLEX_TYPE: 4172 case POINTER_TYPE: 4173 case REFERENCE_TYPE: 4174 return 1; 4175 4176 case VECTOR_TYPE: 4177 return TYPE_VECTOR_SUBPARTS (a->type) == TYPE_VECTOR_SUBPARTS (b->type); 4178 4179 case ENUMERAL_TYPE: 4180 if (TYPE_VALUES (a->type) != TYPE_VALUES (b->type) 4181 && !(TYPE_VALUES (a->type) 4182 && TREE_CODE (TYPE_VALUES (a->type)) == TREE_LIST 4183 && TYPE_VALUES (b->type) 4184 && TREE_CODE (TYPE_VALUES (b->type)) == TREE_LIST 4185 && type_list_equal (TYPE_VALUES (a->type), 4186 TYPE_VALUES (b->type)))) 4187 return 0; 4188 4189 /* ... fall through ... */ 4190 4191 case INTEGER_TYPE: 4192 case REAL_TYPE: 4193 case BOOLEAN_TYPE: 4194 return ((TYPE_MAX_VALUE (a->type) == TYPE_MAX_VALUE (b->type) 4195 || tree_int_cst_equal (TYPE_MAX_VALUE (a->type), 4196 TYPE_MAX_VALUE (b->type))) 4197 && (TYPE_MIN_VALUE (a->type) == TYPE_MIN_VALUE (b->type) 4198 || tree_int_cst_equal (TYPE_MIN_VALUE (a->type), 4199 TYPE_MIN_VALUE (b->type)))); 4200 4201 case OFFSET_TYPE: 4202 return TYPE_OFFSET_BASETYPE (a->type) == TYPE_OFFSET_BASETYPE (b->type); 4203 4204 case METHOD_TYPE: 4205 return (TYPE_METHOD_BASETYPE (a->type) == TYPE_METHOD_BASETYPE (b->type) 4206 && (TYPE_ARG_TYPES (a->type) == TYPE_ARG_TYPES (b->type) 4207 || (TYPE_ARG_TYPES (a->type) 4208 && TREE_CODE (TYPE_ARG_TYPES (a->type)) == TREE_LIST 4209 && TYPE_ARG_TYPES (b->type) 4210 && TREE_CODE (TYPE_ARG_TYPES (b->type)) == TREE_LIST 4211 && type_list_equal (TYPE_ARG_TYPES (a->type), 4212 TYPE_ARG_TYPES (b->type))))); 4213 4214 case ARRAY_TYPE: 4215 return TYPE_DOMAIN (a->type) == TYPE_DOMAIN (b->type); 4216 4217 case RECORD_TYPE: 4218 case UNION_TYPE: 4219 case QUAL_UNION_TYPE: 4220 return (TYPE_FIELDS (a->type) == TYPE_FIELDS (b->type) 4221 || (TYPE_FIELDS (a->type) 4222 && TREE_CODE (TYPE_FIELDS (a->type)) == TREE_LIST 4223 && TYPE_FIELDS (b->type) 4224 && TREE_CODE (TYPE_FIELDS (b->type)) == TREE_LIST 4225 && type_list_equal (TYPE_FIELDS (a->type), 4226 TYPE_FIELDS (b->type)))); 4227 4228 case FUNCTION_TYPE: 4229 return (TYPE_ARG_TYPES (a->type) == TYPE_ARG_TYPES (b->type) 4230 || (TYPE_ARG_TYPES (a->type) 4231 && TREE_CODE (TYPE_ARG_TYPES (a->type)) == TREE_LIST 4232 && TYPE_ARG_TYPES (b->type) 4233 && TREE_CODE (TYPE_ARG_TYPES (b->type)) == TREE_LIST 4234 && type_list_equal (TYPE_ARG_TYPES (a->type), 4235 TYPE_ARG_TYPES (b->type)))); 4236 4237 default: 4238 return 0; 4239 } 4240} 4241 4242/* Return the cached hash value. */ 4243 4244static hashval_t 4245type_hash_hash (const void *item) 4246{ 4247 return ((const struct type_hash *) item)->hash; 4248} 4249 4250/* Look in the type hash table for a type isomorphic to TYPE. 4251 If one is found, return it. Otherwise return 0. */ 4252 4253tree 4254type_hash_lookup (hashval_t hashcode, tree type) 4255{ 4256 struct type_hash *h, in; 4257 4258 /* The TYPE_ALIGN field of a type is set by layout_type(), so we 4259 must call that routine before comparing TYPE_ALIGNs. */ 4260 layout_type (type); 4261 4262 in.hash = hashcode; 4263 in.type = type; 4264 4265 h = htab_find_with_hash (type_hash_table, &in, hashcode); 4266 if (h) 4267 return h->type; 4268 return NULL_TREE; 4269} 4270 4271/* Add an entry to the type-hash-table 4272 for a type TYPE whose hash code is HASHCODE. */ 4273 4274void 4275type_hash_add (hashval_t hashcode, tree type) 4276{ 4277 struct type_hash *h; 4278 void **loc; 4279 4280 h = ggc_alloc (sizeof (struct type_hash)); 4281 h->hash = hashcode; 4282 h->type = type; 4283 loc = htab_find_slot_with_hash (type_hash_table, h, hashcode, INSERT); 4284 *(struct type_hash **) loc = h; 4285} 4286 4287/* Given TYPE, and HASHCODE its hash code, return the canonical 4288 object for an identical type if one already exists. 4289 Otherwise, return TYPE, and record it as the canonical object. 4290 4291 To use this function, first create a type of the sort you want. 4292 Then compute its hash code from the fields of the type that 4293 make it different from other similar types. 4294 Then call this function and use the value. */ 4295 4296tree 4297type_hash_canon (unsigned int hashcode, tree type) 4298{ 4299 tree t1; 4300 4301 /* The hash table only contains main variants, so ensure that's what we're 4302 being passed. */ 4303 gcc_assert (TYPE_MAIN_VARIANT (type) == type); 4304 4305 if (!lang_hooks.types.hash_types) 4306 return type; 4307 4308 /* See if the type is in the hash table already. If so, return it. 4309 Otherwise, add the type. */ 4310 t1 = type_hash_lookup (hashcode, type); 4311 if (t1 != 0) 4312 { 4313#ifdef GATHER_STATISTICS 4314 tree_node_counts[(int) t_kind]--; 4315 tree_node_sizes[(int) t_kind] -= sizeof (struct tree_type); 4316#endif 4317 return t1; 4318 } 4319 else 4320 { 4321 type_hash_add (hashcode, type); 4322 return type; 4323 } 4324} 4325 4326/* See if the data pointed to by the type hash table is marked. We consider 4327 it marked if the type is marked or if a debug type number or symbol 4328 table entry has been made for the type. This reduces the amount of 4329 debugging output and eliminates that dependency of the debug output on 4330 the number of garbage collections. */ 4331 4332static int 4333type_hash_marked_p (const void *p) 4334{ 4335 tree type = ((struct type_hash *) p)->type; 4336 4337 return ggc_marked_p (type) || TYPE_SYMTAB_POINTER (type); 4338} 4339 4340static void 4341print_type_hash_statistics (void) 4342{ 4343 fprintf (stderr, "Type hash: size %ld, %ld elements, %f collisions\n", 4344 (long) htab_size (type_hash_table), 4345 (long) htab_elements (type_hash_table), 4346 htab_collisions (type_hash_table)); 4347} 4348 4349/* Compute a hash code for a list of attributes (chain of TREE_LIST nodes 4350 with names in the TREE_PURPOSE slots and args in the TREE_VALUE slots), 4351 by adding the hash codes of the individual attributes. */ 4352 4353unsigned int 4354attribute_hash_list (tree list, hashval_t hashcode) 4355{ 4356 tree tail; 4357 4358 for (tail = list; tail; tail = TREE_CHAIN (tail)) 4359 /* ??? Do we want to add in TREE_VALUE too? */ 4360 hashcode = iterative_hash_object 4361 (IDENTIFIER_HASH_VALUE (TREE_PURPOSE (tail)), hashcode); 4362 return hashcode; 4363} 4364 4365/* Given two lists of attributes, return true if list l2 is 4366 equivalent to l1. */ 4367 4368int 4369attribute_list_equal (tree l1, tree l2) 4370{ 4371 return attribute_list_contained (l1, l2) 4372 && attribute_list_contained (l2, l1); 4373} 4374 4375/* Given two lists of attributes, return true if list L2 is 4376 completely contained within L1. */ 4377/* ??? This would be faster if attribute names were stored in a canonicalized 4378 form. Otherwise, if L1 uses `foo' and L2 uses `__foo__', the long method 4379 must be used to show these elements are equivalent (which they are). */ 4380/* ??? It's not clear that attributes with arguments will always be handled 4381 correctly. */ 4382 4383int 4384attribute_list_contained (tree l1, tree l2) 4385{ 4386 tree t1, t2; 4387 4388 /* First check the obvious, maybe the lists are identical. */ 4389 if (l1 == l2) 4390 return 1; 4391 4392 /* Maybe the lists are similar. */ 4393 for (t1 = l1, t2 = l2; 4394 t1 != 0 && t2 != 0 4395 && TREE_PURPOSE (t1) == TREE_PURPOSE (t2) 4396 && TREE_VALUE (t1) == TREE_VALUE (t2); 4397 t1 = TREE_CHAIN (t1), t2 = TREE_CHAIN (t2)); 4398 4399 /* Maybe the lists are equal. */ 4400 if (t1 == 0 && t2 == 0) 4401 return 1; 4402 4403 for (; t2 != 0; t2 = TREE_CHAIN (t2)) 4404 { 4405 tree attr; 4406 for (attr = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (t2)), l1); 4407 attr != NULL_TREE; 4408 attr = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (t2)), 4409 TREE_CHAIN (attr))) 4410 { 4411 if (TREE_VALUE (t2) != NULL 4412 && TREE_CODE (TREE_VALUE (t2)) == TREE_LIST 4413 && TREE_VALUE (attr) != NULL 4414 && TREE_CODE (TREE_VALUE (attr)) == TREE_LIST) 4415 { 4416 if (simple_cst_list_equal (TREE_VALUE (t2), 4417 TREE_VALUE (attr)) == 1) 4418 break; 4419 } 4420 else if (simple_cst_equal (TREE_VALUE (t2), TREE_VALUE (attr)) == 1) 4421 break; 4422 } 4423 4424 if (attr == 0) 4425 return 0; 4426 } 4427 4428 return 1; 4429} 4430 4431/* Given two lists of types 4432 (chains of TREE_LIST nodes with types in the TREE_VALUE slots) 4433 return 1 if the lists contain the same types in the same order. 4434 Also, the TREE_PURPOSEs must match. */ 4435 4436int 4437type_list_equal (tree l1, tree l2) 4438{ 4439 tree t1, t2; 4440 4441 for (t1 = l1, t2 = l2; t1 && t2; t1 = TREE_CHAIN (t1), t2 = TREE_CHAIN (t2)) 4442 if (TREE_VALUE (t1) != TREE_VALUE (t2) 4443 || (TREE_PURPOSE (t1) != TREE_PURPOSE (t2) 4444 && ! (1 == simple_cst_equal (TREE_PURPOSE (t1), TREE_PURPOSE (t2)) 4445 && (TREE_TYPE (TREE_PURPOSE (t1)) 4446 == TREE_TYPE (TREE_PURPOSE (t2)))))) 4447 return 0; 4448 4449 return t1 == t2; 4450} 4451 4452/* Returns the number of arguments to the FUNCTION_TYPE or METHOD_TYPE 4453 given by TYPE. If the argument list accepts variable arguments, 4454 then this function counts only the ordinary arguments. */ 4455 4456int 4457type_num_arguments (tree type) 4458{ 4459 int i = 0; 4460 tree t; 4461 4462 for (t = TYPE_ARG_TYPES (type); t; t = TREE_CHAIN (t)) 4463 /* If the function does not take a variable number of arguments, 4464 the last element in the list will have type `void'. */ 4465 if (VOID_TYPE_P (TREE_VALUE (t))) 4466 break; 4467 else 4468 ++i; 4469 4470 return i; 4471} 4472 4473/* Nonzero if integer constants T1 and T2 4474 represent the same constant value. */ 4475 4476int 4477tree_int_cst_equal (tree t1, tree t2) 4478{ 4479 if (t1 == t2) 4480 return 1; 4481 4482 if (t1 == 0 || t2 == 0) 4483 return 0; 4484 4485 if (TREE_CODE (t1) == INTEGER_CST 4486 && TREE_CODE (t2) == INTEGER_CST 4487 && TREE_INT_CST_LOW (t1) == TREE_INT_CST_LOW (t2) 4488 && TREE_INT_CST_HIGH (t1) == TREE_INT_CST_HIGH (t2)) 4489 return 1; 4490 4491 return 0; 4492} 4493 4494/* Nonzero if integer constants T1 and T2 represent values that satisfy <. 4495 The precise way of comparison depends on their data type. */ 4496 4497int 4498tree_int_cst_lt (tree t1, tree t2) 4499{ 4500 if (t1 == t2) 4501 return 0; 4502 4503 if (TYPE_UNSIGNED (TREE_TYPE (t1)) != TYPE_UNSIGNED (TREE_TYPE (t2))) 4504 { 4505 int t1_sgn = tree_int_cst_sgn (t1); 4506 int t2_sgn = tree_int_cst_sgn (t2); 4507 4508 if (t1_sgn < t2_sgn) 4509 return 1; 4510 else if (t1_sgn > t2_sgn) 4511 return 0; 4512 /* Otherwise, both are non-negative, so we compare them as 4513 unsigned just in case one of them would overflow a signed 4514 type. */ 4515 } 4516 else if (!TYPE_UNSIGNED (TREE_TYPE (t1))) 4517 return INT_CST_LT (t1, t2); 4518 4519 return INT_CST_LT_UNSIGNED (t1, t2); 4520} 4521 4522/* Returns -1 if T1 < T2, 0 if T1 == T2, and 1 if T1 > T2. */ 4523 4524int 4525tree_int_cst_compare (tree t1, tree t2) 4526{ 4527 if (tree_int_cst_lt (t1, t2)) 4528 return -1; 4529 else if (tree_int_cst_lt (t2, t1)) 4530 return 1; 4531 else 4532 return 0; 4533} 4534 4535/* Return 1 if T is an INTEGER_CST that can be manipulated efficiently on 4536 the host. If POS is zero, the value can be represented in a single 4537 HOST_WIDE_INT. If POS is nonzero, the value must be non-negative and can 4538 be represented in a single unsigned HOST_WIDE_INT. */ 4539 4540int 4541host_integerp (tree t, int pos) 4542{ 4543 return (TREE_CODE (t) == INTEGER_CST 4544 && ((TREE_INT_CST_HIGH (t) == 0 4545 && (HOST_WIDE_INT) TREE_INT_CST_LOW (t) >= 0) 4546 || (! pos && TREE_INT_CST_HIGH (t) == -1 4547 && (HOST_WIDE_INT) TREE_INT_CST_LOW (t) < 0 4548 && (!TYPE_UNSIGNED (TREE_TYPE (t)) 4549 || TYPE_IS_SIZETYPE (TREE_TYPE (t)))) 4550 || (pos && TREE_INT_CST_HIGH (t) == 0))); 4551} 4552 4553/* Return the HOST_WIDE_INT least significant bits of T if it is an 4554 INTEGER_CST and there is no overflow. POS is nonzero if the result must 4555 be non-negative. We must be able to satisfy the above conditions. */ 4556 4557HOST_WIDE_INT 4558tree_low_cst (tree t, int pos) 4559{ 4560 gcc_assert (host_integerp (t, pos)); 4561 return TREE_INT_CST_LOW (t); 4562} 4563 4564/* Return the most significant bit of the integer constant T. */ 4565 4566int 4567tree_int_cst_msb (tree t) 4568{ 4569 int prec; 4570 HOST_WIDE_INT h; 4571 unsigned HOST_WIDE_INT l; 4572 4573 /* Note that using TYPE_PRECISION here is wrong. We care about the 4574 actual bits, not the (arbitrary) range of the type. */ 4575 prec = GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (t))) - 1; 4576 rshift_double (TREE_INT_CST_LOW (t), TREE_INT_CST_HIGH (t), prec, 4577 2 * HOST_BITS_PER_WIDE_INT, &l, &h, 0); 4578 return (l & 1) == 1; 4579} 4580 4581/* Return an indication of the sign of the integer constant T. 4582 The return value is -1 if T < 0, 0 if T == 0, and 1 if T > 0. 4583 Note that -1 will never be returned if T's type is unsigned. */ 4584 4585int 4586tree_int_cst_sgn (tree t) 4587{ 4588 if (TREE_INT_CST_LOW (t) == 0 && TREE_INT_CST_HIGH (t) == 0) 4589 return 0; 4590 else if (TYPE_UNSIGNED (TREE_TYPE (t))) 4591 return 1; 4592 else if (TREE_INT_CST_HIGH (t) < 0) 4593 return -1; 4594 else 4595 return 1; 4596} 4597 4598/* Compare two constructor-element-type constants. Return 1 if the lists 4599 are known to be equal; otherwise return 0. */ 4600 4601int 4602simple_cst_list_equal (tree l1, tree l2) 4603{ 4604 while (l1 != NULL_TREE && l2 != NULL_TREE) 4605 { 4606 if (simple_cst_equal (TREE_VALUE (l1), TREE_VALUE (l2)) != 1) 4607 return 0; 4608 4609 l1 = TREE_CHAIN (l1); 4610 l2 = TREE_CHAIN (l2); 4611 } 4612 4613 return l1 == l2; 4614} 4615 4616/* Return truthvalue of whether T1 is the same tree structure as T2. 4617 Return 1 if they are the same. 4618 Return 0 if they are understandably different. 4619 Return -1 if either contains tree structure not understood by 4620 this function. */ 4621 4622int 4623simple_cst_equal (tree t1, tree t2) 4624{ 4625 enum tree_code code1, code2; 4626 int cmp; 4627 int i; 4628 4629 if (t1 == t2) 4630 return 1; 4631 if (t1 == 0 || t2 == 0) 4632 return 0; 4633 4634 code1 = TREE_CODE (t1); 4635 code2 = TREE_CODE (t2); 4636 4637 if (code1 == NOP_EXPR || code1 == CONVERT_EXPR || code1 == NON_LVALUE_EXPR) 4638 { 4639 if (code2 == NOP_EXPR || code2 == CONVERT_EXPR 4640 || code2 == NON_LVALUE_EXPR) 4641 return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0)); 4642 else 4643 return simple_cst_equal (TREE_OPERAND (t1, 0), t2); 4644 } 4645 4646 else if (code2 == NOP_EXPR || code2 == CONVERT_EXPR 4647 || code2 == NON_LVALUE_EXPR) 4648 return simple_cst_equal (t1, TREE_OPERAND (t2, 0)); 4649 4650 if (code1 != code2) 4651 return 0; 4652 4653 switch (code1) 4654 { 4655 case INTEGER_CST: 4656 return (TREE_INT_CST_LOW (t1) == TREE_INT_CST_LOW (t2) 4657 && TREE_INT_CST_HIGH (t1) == TREE_INT_CST_HIGH (t2)); 4658 4659 case REAL_CST: 4660 return REAL_VALUES_IDENTICAL (TREE_REAL_CST (t1), TREE_REAL_CST (t2)); 4661 4662 case STRING_CST: 4663 return (TREE_STRING_LENGTH (t1) == TREE_STRING_LENGTH (t2) 4664 && ! memcmp (TREE_STRING_POINTER (t1), TREE_STRING_POINTER (t2), 4665 TREE_STRING_LENGTH (t1))); 4666 4667 case CONSTRUCTOR: 4668 { 4669 unsigned HOST_WIDE_INT idx; 4670 VEC(constructor_elt, gc) *v1 = CONSTRUCTOR_ELTS (t1); 4671 VEC(constructor_elt, gc) *v2 = CONSTRUCTOR_ELTS (t2); 4672 4673 if (VEC_length (constructor_elt, v1) != VEC_length (constructor_elt, v2)) 4674 return false; 4675 4676 for (idx = 0; idx < VEC_length (constructor_elt, v1); ++idx) 4677 /* ??? Should we handle also fields here? */ 4678 if (!simple_cst_equal (VEC_index (constructor_elt, v1, idx)->value, 4679 VEC_index (constructor_elt, v2, idx)->value)) 4680 return false; 4681 return true; 4682 } 4683 4684 case SAVE_EXPR: 4685 return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0)); 4686 4687 case CALL_EXPR: 4688 cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0)); 4689 if (cmp <= 0) 4690 return cmp; 4691 return 4692 simple_cst_list_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1)); 4693 4694 case TARGET_EXPR: 4695 /* Special case: if either target is an unallocated VAR_DECL, 4696 it means that it's going to be unified with whatever the 4697 TARGET_EXPR is really supposed to initialize, so treat it 4698 as being equivalent to anything. */ 4699 if ((TREE_CODE (TREE_OPERAND (t1, 0)) == VAR_DECL 4700 && DECL_NAME (TREE_OPERAND (t1, 0)) == NULL_TREE 4701 && !DECL_RTL_SET_P (TREE_OPERAND (t1, 0))) 4702 || (TREE_CODE (TREE_OPERAND (t2, 0)) == VAR_DECL 4703 && DECL_NAME (TREE_OPERAND (t2, 0)) == NULL_TREE 4704 && !DECL_RTL_SET_P (TREE_OPERAND (t2, 0)))) 4705 cmp = 1; 4706 else 4707 cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0)); 4708 4709 if (cmp <= 0) 4710 return cmp; 4711 4712 return simple_cst_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1)); 4713 4714 case WITH_CLEANUP_EXPR: 4715 cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0)); 4716 if (cmp <= 0) 4717 return cmp; 4718 4719 return simple_cst_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t1, 1)); 4720 4721 case COMPONENT_REF: 4722 if (TREE_OPERAND (t1, 1) == TREE_OPERAND (t2, 1)) 4723 return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0)); 4724 4725 return 0; 4726 4727 case VAR_DECL: 4728 case PARM_DECL: 4729 case CONST_DECL: 4730 case FUNCTION_DECL: 4731 return 0; 4732 4733 default: 4734 break; 4735 } 4736 4737 /* This general rule works for most tree codes. All exceptions should be 4738 handled above. If this is a language-specific tree code, we can't 4739 trust what might be in the operand, so say we don't know 4740 the situation. */ 4741 if ((int) code1 >= (int) LAST_AND_UNUSED_TREE_CODE) 4742 return -1; 4743 4744 switch (TREE_CODE_CLASS (code1)) 4745 { 4746 case tcc_unary: 4747 case tcc_binary: 4748 case tcc_comparison: 4749 case tcc_expression: 4750 case tcc_reference: 4751 case tcc_statement: 4752 cmp = 1; 4753 for (i = 0; i < TREE_CODE_LENGTH (code1); i++) 4754 { 4755 cmp = simple_cst_equal (TREE_OPERAND (t1, i), TREE_OPERAND (t2, i)); 4756 if (cmp <= 0) 4757 return cmp; 4758 } 4759 4760 return cmp; 4761 4762 default: 4763 return -1; 4764 } 4765} 4766 4767/* Compare the value of T, an INTEGER_CST, with U, an unsigned integer value. 4768 Return -1, 0, or 1 if the value of T is less than, equal to, or greater 4769 than U, respectively. */ 4770 4771int 4772compare_tree_int (tree t, unsigned HOST_WIDE_INT u) 4773{ 4774 if (tree_int_cst_sgn (t) < 0) 4775 return -1; 4776 else if (TREE_INT_CST_HIGH (t) != 0) 4777 return 1; 4778 else if (TREE_INT_CST_LOW (t) == u) 4779 return 0; 4780 else if (TREE_INT_CST_LOW (t) < u) 4781 return -1; 4782 else 4783 return 1; 4784} 4785 4786/* Return true if CODE represents an associative tree code. Otherwise 4787 return false. */ 4788bool 4789associative_tree_code (enum tree_code code) 4790{ 4791 switch (code) 4792 { 4793 case BIT_IOR_EXPR: 4794 case BIT_AND_EXPR: 4795 case BIT_XOR_EXPR: 4796 case PLUS_EXPR: 4797 case MULT_EXPR: 4798 case MIN_EXPR: 4799 case MAX_EXPR: 4800 return true; 4801 4802 default: 4803 break; 4804 } 4805 return false; 4806} 4807 4808/* Return true if CODE represents a commutative tree code. Otherwise 4809 return false. */ 4810bool 4811commutative_tree_code (enum tree_code code) 4812{ 4813 switch (code) 4814 { 4815 case PLUS_EXPR: 4816 case MULT_EXPR: 4817 case MIN_EXPR: 4818 case MAX_EXPR: 4819 case BIT_IOR_EXPR: 4820 case BIT_XOR_EXPR: 4821 case BIT_AND_EXPR: 4822 case NE_EXPR: 4823 case EQ_EXPR: 4824 case UNORDERED_EXPR: 4825 case ORDERED_EXPR: 4826 case UNEQ_EXPR: 4827 case LTGT_EXPR: 4828 case TRUTH_AND_EXPR: 4829 case TRUTH_XOR_EXPR: 4830 case TRUTH_OR_EXPR: 4831 return true; 4832 4833 default: 4834 break; 4835 } 4836 return false; 4837} 4838 4839/* Generate a hash value for an expression. This can be used iteratively 4840 by passing a previous result as the "val" argument. 4841 4842 This function is intended to produce the same hash for expressions which 4843 would compare equal using operand_equal_p. */ 4844 4845hashval_t 4846iterative_hash_expr (tree t, hashval_t val) 4847{ 4848 int i; 4849 enum tree_code code; 4850 char class; 4851 4852 if (t == NULL_TREE) 4853 return iterative_hash_pointer (t, val); 4854 4855 code = TREE_CODE (t); 4856 4857 switch (code) 4858 { 4859 /* Alas, constants aren't shared, so we can't rely on pointer 4860 identity. */ 4861 case INTEGER_CST: 4862 val = iterative_hash_host_wide_int (TREE_INT_CST_LOW (t), val); 4863 return iterative_hash_host_wide_int (TREE_INT_CST_HIGH (t), val); 4864 case REAL_CST: 4865 { 4866 unsigned int val2 = real_hash (TREE_REAL_CST_PTR (t)); 4867 4868 return iterative_hash_hashval_t (val2, val); 4869 } 4870 case STRING_CST: 4871 return iterative_hash (TREE_STRING_POINTER (t), 4872 TREE_STRING_LENGTH (t), val); 4873 case COMPLEX_CST: 4874 val = iterative_hash_expr (TREE_REALPART (t), val); 4875 return iterative_hash_expr (TREE_IMAGPART (t), val); 4876 case VECTOR_CST: 4877 return iterative_hash_expr (TREE_VECTOR_CST_ELTS (t), val); 4878 4879 case SSA_NAME: 4880 case VALUE_HANDLE: 4881 /* we can just compare by pointer. */ 4882 return iterative_hash_pointer (t, val); 4883 4884 case TREE_LIST: 4885 /* A list of expressions, for a CALL_EXPR or as the elements of a 4886 VECTOR_CST. */ 4887 for (; t; t = TREE_CHAIN (t)) 4888 val = iterative_hash_expr (TREE_VALUE (t), val); 4889 return val; 4890 case CONSTRUCTOR: 4891 { 4892 unsigned HOST_WIDE_INT idx; 4893 tree field, value; 4894 FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (t), idx, field, value) 4895 { 4896 val = iterative_hash_expr (field, val); 4897 val = iterative_hash_expr (value, val); 4898 } 4899 return val; 4900 } 4901 case FUNCTION_DECL: 4902 /* When referring to a built-in FUNCTION_DECL, use the 4903 __builtin__ form. Otherwise nodes that compare equal 4904 according to operand_equal_p might get different 4905 hash codes. */ 4906 if (DECL_BUILT_IN (t)) 4907 { 4908 val = iterative_hash_pointer (built_in_decls[DECL_FUNCTION_CODE (t)], 4909 val); 4910 return val; 4911 } 4912 /* else FALL THROUGH */ 4913 default: 4914 class = TREE_CODE_CLASS (code); 4915 4916 if (class == tcc_declaration) 4917 { 4918 /* DECL's have a unique ID */ 4919 val = iterative_hash_host_wide_int (DECL_UID (t), val); 4920 } 4921 else 4922 { 4923 gcc_assert (IS_EXPR_CODE_CLASS (class)); 4924 4925 val = iterative_hash_object (code, val); 4926 4927 /* Don't hash the type, that can lead to having nodes which 4928 compare equal according to operand_equal_p, but which 4929 have different hash codes. */ 4930 if (code == NOP_EXPR 4931 || code == CONVERT_EXPR 4932 || code == NON_LVALUE_EXPR) 4933 { 4934 /* Make sure to include signness in the hash computation. */ 4935 val += TYPE_UNSIGNED (TREE_TYPE (t)); 4936 val = iterative_hash_expr (TREE_OPERAND (t, 0), val); 4937 } 4938 4939 else if (commutative_tree_code (code)) 4940 { 4941 /* It's a commutative expression. We want to hash it the same 4942 however it appears. We do this by first hashing both operands 4943 and then rehashing based on the order of their independent 4944 hashes. */ 4945 hashval_t one = iterative_hash_expr (TREE_OPERAND (t, 0), 0); 4946 hashval_t two = iterative_hash_expr (TREE_OPERAND (t, 1), 0); 4947 hashval_t t; 4948 4949 if (one > two) 4950 t = one, one = two, two = t; 4951 4952 val = iterative_hash_hashval_t (one, val); 4953 val = iterative_hash_hashval_t (two, val); 4954 } 4955 else 4956 for (i = TREE_CODE_LENGTH (code) - 1; i >= 0; --i) 4957 val = iterative_hash_expr (TREE_OPERAND (t, i), val); 4958 } 4959 return val; 4960 break; 4961 } 4962} 4963 4964/* Constructors for pointer, array and function types. 4965 (RECORD_TYPE, UNION_TYPE and ENUMERAL_TYPE nodes are 4966 constructed by language-dependent code, not here.) */ 4967 4968/* Construct, lay out and return the type of pointers to TO_TYPE with 4969 mode MODE. If CAN_ALIAS_ALL is TRUE, indicate this type can 4970 reference all of memory. If such a type has already been 4971 constructed, reuse it. */ 4972 4973tree 4974build_pointer_type_for_mode (tree to_type, enum machine_mode mode, 4975 bool can_alias_all) 4976{ 4977 tree t; 4978 4979 if (to_type == error_mark_node) 4980 return error_mark_node; 4981 4982 /* In some cases, languages will have things that aren't a POINTER_TYPE 4983 (such as a RECORD_TYPE for fat pointers in Ada) as TYPE_POINTER_TO. 4984 In that case, return that type without regard to the rest of our 4985 operands. 4986 4987 ??? This is a kludge, but consistent with the way this function has 4988 always operated and there doesn't seem to be a good way to avoid this 4989 at the moment. */ 4990 if (TYPE_POINTER_TO (to_type) != 0 4991 && TREE_CODE (TYPE_POINTER_TO (to_type)) != POINTER_TYPE) 4992 return TYPE_POINTER_TO (to_type); 4993 4994 /* First, if we already have a type for pointers to TO_TYPE and it's 4995 the proper mode, use it. */ 4996 for (t = TYPE_POINTER_TO (to_type); t; t = TYPE_NEXT_PTR_TO (t)) 4997 if (TYPE_MODE (t) == mode && TYPE_REF_CAN_ALIAS_ALL (t) == can_alias_all) 4998 return t; 4999 5000 t = make_node (POINTER_TYPE); 5001 5002 TREE_TYPE (t) = to_type; 5003 TYPE_MODE (t) = mode; 5004 TYPE_REF_CAN_ALIAS_ALL (t) = can_alias_all; 5005 TYPE_NEXT_PTR_TO (t) = TYPE_POINTER_TO (to_type); 5006 TYPE_POINTER_TO (to_type) = t; 5007 5008 /* Lay out the type. This function has many callers that are concerned 5009 with expression-construction, and this simplifies them all. */ 5010 layout_type (t); 5011 5012 return t; 5013} 5014 5015/* By default build pointers in ptr_mode. */ 5016 5017tree 5018build_pointer_type (tree to_type) 5019{ 5020 return build_pointer_type_for_mode (to_type, ptr_mode, false); 5021} 5022 5023/* APPLE LOCAL begin radar 5732232 - blocks */ 5024tree 5025build_block_pointer_type (tree to_type) 5026{ 5027 tree t; 5028 5029 /* APPLE LOCAL begin radar 6300081 & 6353006 */ 5030 if (!generic_block_literal_struct_type) 5031 generic_block_literal_struct_type = 5032 lang_hooks.build_generic_block_struct_type (); 5033 /* APPLE LOCAL end radar 6300081 & 6353006 */ 5034 5035 t = make_node (BLOCK_POINTER_TYPE); 5036 5037 TREE_TYPE (t) = to_type; 5038 TYPE_MODE (t) = ptr_mode; 5039 5040 /* Lay out the type. This function has many callers that are concerned 5041 with expression-construction, and this simplifies them all. */ 5042 layout_type (t); 5043 5044 return t; 5045} 5046/* APPLE LOCAL end radar 5732232 - blocks */ 5047 5048/* Same as build_pointer_type_for_mode, but for REFERENCE_TYPE. */ 5049 5050tree 5051build_reference_type_for_mode (tree to_type, enum machine_mode mode, 5052 bool can_alias_all) 5053{ 5054 tree t; 5055 5056 /* In some cases, languages will have things that aren't a REFERENCE_TYPE 5057 (such as a RECORD_TYPE for fat pointers in Ada) as TYPE_REFERENCE_TO. 5058 In that case, return that type without regard to the rest of our 5059 operands. 5060 5061 ??? This is a kludge, but consistent with the way this function has 5062 always operated and there doesn't seem to be a good way to avoid this 5063 at the moment. */ 5064 if (TYPE_REFERENCE_TO (to_type) != 0 5065 && TREE_CODE (TYPE_REFERENCE_TO (to_type)) != REFERENCE_TYPE) 5066 return TYPE_REFERENCE_TO (to_type); 5067 5068 /* First, if we already have a type for pointers to TO_TYPE and it's 5069 the proper mode, use it. */ 5070 for (t = TYPE_REFERENCE_TO (to_type); t; t = TYPE_NEXT_REF_TO (t)) 5071 if (TYPE_MODE (t) == mode && TYPE_REF_CAN_ALIAS_ALL (t) == can_alias_all) 5072 return t; 5073 5074 t = make_node (REFERENCE_TYPE); 5075 5076 TREE_TYPE (t) = to_type; 5077 TYPE_MODE (t) = mode; 5078 TYPE_REF_CAN_ALIAS_ALL (t) = can_alias_all; 5079 TYPE_NEXT_REF_TO (t) = TYPE_REFERENCE_TO (to_type); 5080 TYPE_REFERENCE_TO (to_type) = t; 5081 5082 layout_type (t); 5083 5084 return t; 5085} 5086 5087 5088/* Build the node for the type of references-to-TO_TYPE by default 5089 in ptr_mode. */ 5090 5091tree 5092build_reference_type (tree to_type) 5093{ 5094 return build_reference_type_for_mode (to_type, ptr_mode, false); 5095} 5096 5097/* Build a type that is compatible with t but has no cv quals anywhere 5098 in its type, thus 5099 5100 const char *const *const * -> char ***. */ 5101 5102tree 5103build_type_no_quals (tree t) 5104{ 5105 switch (TREE_CODE (t)) 5106 { 5107 case POINTER_TYPE: 5108 return build_pointer_type_for_mode (build_type_no_quals (TREE_TYPE (t)), 5109 TYPE_MODE (t), 5110 TYPE_REF_CAN_ALIAS_ALL (t)); 5111 case REFERENCE_TYPE: 5112 return 5113 build_reference_type_for_mode (build_type_no_quals (TREE_TYPE (t)), 5114 TYPE_MODE (t), 5115 TYPE_REF_CAN_ALIAS_ALL (t)); 5116 default: 5117 return TYPE_MAIN_VARIANT (t); 5118 } 5119} 5120 5121/* Create a type of integers to be the TYPE_DOMAIN of an ARRAY_TYPE. 5122 MAXVAL should be the maximum value in the domain 5123 (one less than the length of the array). 5124 5125 The maximum value that MAXVAL can have is INT_MAX for a HOST_WIDE_INT. 5126 We don't enforce this limit, that is up to caller (e.g. language front end). 5127 The limit exists because the result is a signed type and we don't handle 5128 sizes that use more than one HOST_WIDE_INT. */ 5129 5130tree 5131build_index_type (tree maxval) 5132{ 5133 tree itype = make_node (INTEGER_TYPE); 5134 5135 TREE_TYPE (itype) = sizetype; 5136 TYPE_PRECISION (itype) = TYPE_PRECISION (sizetype); 5137 TYPE_MIN_VALUE (itype) = size_zero_node; 5138 TYPE_MAX_VALUE (itype) = fold_convert (sizetype, maxval); 5139 TYPE_MODE (itype) = TYPE_MODE (sizetype); 5140 TYPE_SIZE (itype) = TYPE_SIZE (sizetype); 5141 TYPE_SIZE_UNIT (itype) = TYPE_SIZE_UNIT (sizetype); 5142 TYPE_ALIGN (itype) = TYPE_ALIGN (sizetype); 5143 TYPE_USER_ALIGN (itype) = TYPE_USER_ALIGN (sizetype); 5144 5145 if (host_integerp (maxval, 1)) 5146 return type_hash_canon (tree_low_cst (maxval, 1), itype); 5147 else 5148 return itype; 5149} 5150 5151/* Builds a signed or unsigned integer type of precision PRECISION. 5152 Used for C bitfields whose precision does not match that of 5153 built-in target types. */ 5154tree 5155build_nonstandard_integer_type (unsigned HOST_WIDE_INT precision, 5156 int unsignedp) 5157{ 5158 tree itype = make_node (INTEGER_TYPE); 5159 5160 TYPE_PRECISION (itype) = precision; 5161 5162 if (unsignedp) 5163 fixup_unsigned_type (itype); 5164 else 5165 fixup_signed_type (itype); 5166 5167 if (host_integerp (TYPE_MAX_VALUE (itype), 1)) 5168 return type_hash_canon (tree_low_cst (TYPE_MAX_VALUE (itype), 1), itype); 5169 5170 return itype; 5171} 5172 5173/* Create a range of some discrete type TYPE (an INTEGER_TYPE, 5174 ENUMERAL_TYPE or BOOLEAN_TYPE), with low bound LOWVAL and 5175 high bound HIGHVAL. If TYPE is NULL, sizetype is used. */ 5176 5177tree 5178build_range_type (tree type, tree lowval, tree highval) 5179{ 5180 tree itype = make_node (INTEGER_TYPE); 5181 5182 TREE_TYPE (itype) = type; 5183 if (type == NULL_TREE) 5184 type = sizetype; 5185 5186 TYPE_MIN_VALUE (itype) = fold_convert (type, lowval); 5187 TYPE_MAX_VALUE (itype) = highval ? fold_convert (type, highval) : NULL; 5188 5189 TYPE_PRECISION (itype) = TYPE_PRECISION (type); 5190 TYPE_MODE (itype) = TYPE_MODE (type); 5191 TYPE_SIZE (itype) = TYPE_SIZE (type); 5192 TYPE_SIZE_UNIT (itype) = TYPE_SIZE_UNIT (type); 5193 TYPE_ALIGN (itype) = TYPE_ALIGN (type); 5194 TYPE_USER_ALIGN (itype) = TYPE_USER_ALIGN (type); 5195 5196 if (host_integerp (lowval, 0) && highval != 0 && host_integerp (highval, 0)) 5197 return type_hash_canon (tree_low_cst (highval, 0) 5198 - tree_low_cst (lowval, 0), 5199 itype); 5200 else 5201 return itype; 5202} 5203 5204/* Just like build_index_type, but takes lowval and highval instead 5205 of just highval (maxval). */ 5206 5207tree 5208build_index_2_type (tree lowval, tree highval) 5209{ 5210 return build_range_type (sizetype, lowval, highval); 5211} 5212 5213/* Construct, lay out and return the type of arrays of elements with ELT_TYPE 5214 and number of elements specified by the range of values of INDEX_TYPE. 5215 If such a type has already been constructed, reuse it. */ 5216 5217tree 5218build_array_type (tree elt_type, tree index_type) 5219{ 5220 tree t; 5221 hashval_t hashcode = 0; 5222 5223 if (TREE_CODE (elt_type) == FUNCTION_TYPE) 5224 { 5225 error ("arrays of functions are not meaningful"); 5226 elt_type = integer_type_node; 5227 } 5228 5229 t = make_node (ARRAY_TYPE); 5230 TREE_TYPE (t) = elt_type; 5231 TYPE_DOMAIN (t) = index_type; 5232 5233 if (index_type == 0) 5234 { 5235 tree save = t; 5236 hashcode = iterative_hash_object (TYPE_HASH (elt_type), hashcode); 5237 t = type_hash_canon (hashcode, t); 5238 if (save == t) 5239 layout_type (t); 5240 return t; 5241 } 5242 5243 hashcode = iterative_hash_object (TYPE_HASH (elt_type), hashcode); 5244 hashcode = iterative_hash_object (TYPE_HASH (index_type), hashcode); 5245 t = type_hash_canon (hashcode, t); 5246 5247 if (!COMPLETE_TYPE_P (t)) 5248 layout_type (t); 5249 return t; 5250} 5251 5252/* Return the TYPE of the elements comprising 5253 the innermost dimension of ARRAY. */ 5254 5255tree 5256get_inner_array_type (tree array) 5257{ 5258 tree type = TREE_TYPE (array); 5259 5260 while (TREE_CODE (type) == ARRAY_TYPE) 5261 type = TREE_TYPE (type); 5262 5263 return type; 5264} 5265 5266/* Construct, lay out and return 5267 the type of functions returning type VALUE_TYPE 5268 given arguments of types ARG_TYPES. 5269 ARG_TYPES is a chain of TREE_LIST nodes whose TREE_VALUEs 5270 are data type nodes for the arguments of the function. 5271 If such a type has already been constructed, reuse it. */ 5272 5273tree 5274build_function_type (tree value_type, tree arg_types) 5275{ 5276 tree t; 5277 hashval_t hashcode = 0; 5278 5279 if (TREE_CODE (value_type) == FUNCTION_TYPE) 5280 { 5281 error ("function return type cannot be function"); 5282 value_type = integer_type_node; 5283 } 5284 5285 /* Make a node of the sort we want. */ 5286 t = make_node (FUNCTION_TYPE); 5287 TREE_TYPE (t) = value_type; 5288 TYPE_ARG_TYPES (t) = arg_types; 5289 5290 /* If we already have such a type, use the old one. */ 5291 hashcode = iterative_hash_object (TYPE_HASH (value_type), hashcode); 5292 hashcode = type_hash_list (arg_types, hashcode); 5293 t = type_hash_canon (hashcode, t); 5294 5295 if (!COMPLETE_TYPE_P (t)) 5296 layout_type (t); 5297 return t; 5298} 5299 5300/* Build a function type. The RETURN_TYPE is the type returned by the 5301 function. If additional arguments are provided, they are 5302 additional argument types. The list of argument types must always 5303 be terminated by NULL_TREE. */ 5304 5305tree 5306build_function_type_list (tree return_type, ...) 5307{ 5308 tree t, args, last; 5309 va_list p; 5310 5311 va_start (p, return_type); 5312 5313 t = va_arg (p, tree); 5314 for (args = NULL_TREE; t != NULL_TREE; t = va_arg (p, tree)) 5315 args = tree_cons (NULL_TREE, t, args); 5316 5317 if (args == NULL_TREE) 5318 args = void_list_node; 5319 else 5320 { 5321 last = args; 5322 args = nreverse (args); 5323 TREE_CHAIN (last) = void_list_node; 5324 } 5325 args = build_function_type (return_type, args); 5326 5327 va_end (p); 5328 return args; 5329} 5330 5331/* Build a METHOD_TYPE for a member of BASETYPE. The RETTYPE (a TYPE) 5332 and ARGTYPES (a TREE_LIST) are the return type and arguments types 5333 for the method. An implicit additional parameter (of type 5334 pointer-to-BASETYPE) is added to the ARGTYPES. */ 5335 5336tree 5337build_method_type_directly (tree basetype, 5338 tree rettype, 5339 tree argtypes) 5340{ 5341 tree t; 5342 tree ptype; 5343 int hashcode = 0; 5344 5345 /* Make a node of the sort we want. */ 5346 t = make_node (METHOD_TYPE); 5347 5348 TYPE_METHOD_BASETYPE (t) = TYPE_MAIN_VARIANT (basetype); 5349 TREE_TYPE (t) = rettype; 5350 ptype = build_pointer_type (basetype); 5351 5352 /* The actual arglist for this function includes a "hidden" argument 5353 which is "this". Put it into the list of argument types. */ 5354 argtypes = tree_cons (NULL_TREE, ptype, argtypes); 5355 TYPE_ARG_TYPES (t) = argtypes; 5356 5357 /* If we already have such a type, use the old one. */ 5358 hashcode = iterative_hash_object (TYPE_HASH (basetype), hashcode); 5359 hashcode = iterative_hash_object (TYPE_HASH (rettype), hashcode); 5360 hashcode = type_hash_list (argtypes, hashcode); 5361 t = type_hash_canon (hashcode, t); 5362 5363 if (!COMPLETE_TYPE_P (t)) 5364 layout_type (t); 5365 5366 return t; 5367} 5368 5369/* Construct, lay out and return the type of methods belonging to class 5370 BASETYPE and whose arguments and values are described by TYPE. 5371 If that type exists already, reuse it. 5372 TYPE must be a FUNCTION_TYPE node. */ 5373 5374tree 5375build_method_type (tree basetype, tree type) 5376{ 5377 gcc_assert (TREE_CODE (type) == FUNCTION_TYPE); 5378 5379 return build_method_type_directly (basetype, 5380 TREE_TYPE (type), 5381 TYPE_ARG_TYPES (type)); 5382} 5383 5384/* Construct, lay out and return the type of offsets to a value 5385 of type TYPE, within an object of type BASETYPE. 5386 If a suitable offset type exists already, reuse it. */ 5387 5388tree 5389build_offset_type (tree basetype, tree type) 5390{ 5391 tree t; 5392 hashval_t hashcode = 0; 5393 5394 /* Make a node of the sort we want. */ 5395 t = make_node (OFFSET_TYPE); 5396 5397 TYPE_OFFSET_BASETYPE (t) = TYPE_MAIN_VARIANT (basetype); 5398 TREE_TYPE (t) = type; 5399 5400 /* If we already have such a type, use the old one. */ 5401 hashcode = iterative_hash_object (TYPE_HASH (basetype), hashcode); 5402 hashcode = iterative_hash_object (TYPE_HASH (type), hashcode); 5403 t = type_hash_canon (hashcode, t); 5404 5405 if (!COMPLETE_TYPE_P (t)) 5406 layout_type (t); 5407 5408 return t; 5409} 5410 5411/* Create a complex type whose components are COMPONENT_TYPE. */ 5412 5413tree 5414build_complex_type (tree component_type) 5415{ 5416 tree t; 5417 hashval_t hashcode; 5418 5419 /* Make a node of the sort we want. */ 5420 t = make_node (COMPLEX_TYPE); 5421 5422 TREE_TYPE (t) = TYPE_MAIN_VARIANT (component_type); 5423 5424 /* If we already have such a type, use the old one. */ 5425 hashcode = iterative_hash_object (TYPE_HASH (component_type), 0); 5426 t = type_hash_canon (hashcode, t); 5427 5428 if (!COMPLETE_TYPE_P (t)) 5429 layout_type (t); 5430 5431 /* If we are writing Dwarf2 output we need to create a name, 5432 since complex is a fundamental type. */ 5433 if ((write_symbols == DWARF2_DEBUG || write_symbols == VMS_AND_DWARF2_DEBUG) 5434 && ! TYPE_NAME (t)) 5435 { 5436 const char *name; 5437 if (component_type == char_type_node) 5438 name = "complex char"; 5439 else if (component_type == signed_char_type_node) 5440 name = "complex signed char"; 5441 else if (component_type == unsigned_char_type_node) 5442 name = "complex unsigned char"; 5443 else if (component_type == short_integer_type_node) 5444 name = "complex short int"; 5445 else if (component_type == short_unsigned_type_node) 5446 name = "complex short unsigned int"; 5447 else if (component_type == integer_type_node) 5448 name = "complex int"; 5449 else if (component_type == unsigned_type_node) 5450 name = "complex unsigned int"; 5451 else if (component_type == long_integer_type_node) 5452 name = "complex long int"; 5453 else if (component_type == long_unsigned_type_node) 5454 name = "complex long unsigned int"; 5455 else if (component_type == long_long_integer_type_node) 5456 name = "complex long long int"; 5457 else if (component_type == long_long_unsigned_type_node) 5458 name = "complex long long unsigned int"; 5459 else 5460 name = 0; 5461 5462 if (name != 0) 5463 TYPE_NAME (t) = get_identifier (name); 5464 } 5465 5466 return build_qualified_type (t, TYPE_QUALS (component_type)); 5467} 5468 5469/* Return OP, stripped of any conversions to wider types as much as is safe. 5470 Converting the value back to OP's type makes a value equivalent to OP. 5471 5472 If FOR_TYPE is nonzero, we return a value which, if converted to 5473 type FOR_TYPE, would be equivalent to converting OP to type FOR_TYPE. 5474 5475 If FOR_TYPE is nonzero, unaligned bit-field references may be changed to the 5476 narrowest type that can hold the value, even if they don't exactly fit. 5477 Otherwise, bit-field references are changed to a narrower type 5478 only if they can be fetched directly from memory in that type. 5479 5480 OP must have integer, real or enumeral type. Pointers are not allowed! 5481 5482 There are some cases where the obvious value we could return 5483 would regenerate to OP if converted to OP's type, 5484 but would not extend like OP to wider types. 5485 If FOR_TYPE indicates such extension is contemplated, we eschew such values. 5486 For example, if OP is (unsigned short)(signed char)-1, 5487 we avoid returning (signed char)-1 if FOR_TYPE is int, 5488 even though extending that to an unsigned short would regenerate OP, 5489 since the result of extending (signed char)-1 to (int) 5490 is different from (int) OP. */ 5491 5492tree 5493get_unwidened (tree op, tree for_type) 5494{ 5495 /* Set UNS initially if converting OP to FOR_TYPE is a zero-extension. */ 5496 tree type = TREE_TYPE (op); 5497 unsigned final_prec 5498 = TYPE_PRECISION (for_type != 0 ? for_type : type); 5499 int uns 5500 = (for_type != 0 && for_type != type 5501 && final_prec > TYPE_PRECISION (type) 5502 && TYPE_UNSIGNED (type)); 5503 tree win = op; 5504 5505 while (TREE_CODE (op) == NOP_EXPR 5506 || TREE_CODE (op) == CONVERT_EXPR) 5507 { 5508 int bitschange; 5509 5510 /* TYPE_PRECISION on vector types has different meaning 5511 (TYPE_VECTOR_SUBPARTS) and casts from vectors are view conversions, 5512 so avoid them here. */ 5513 if (TREE_CODE (TREE_TYPE (TREE_OPERAND (op, 0))) == VECTOR_TYPE) 5514 break; 5515 5516 bitschange = TYPE_PRECISION (TREE_TYPE (op)) 5517 - TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (op, 0))); 5518 5519 /* Truncations are many-one so cannot be removed. 5520 Unless we are later going to truncate down even farther. */ 5521 if (bitschange < 0 5522 && final_prec > TYPE_PRECISION (TREE_TYPE (op))) 5523 break; 5524 5525 /* See what's inside this conversion. If we decide to strip it, 5526 we will set WIN. */ 5527 op = TREE_OPERAND (op, 0); 5528 5529 /* If we have not stripped any zero-extensions (uns is 0), 5530 we can strip any kind of extension. 5531 If we have previously stripped a zero-extension, 5532 only zero-extensions can safely be stripped. 5533 Any extension can be stripped if the bits it would produce 5534 are all going to be discarded later by truncating to FOR_TYPE. */ 5535 5536 if (bitschange > 0) 5537 { 5538 if (! uns || final_prec <= TYPE_PRECISION (TREE_TYPE (op))) 5539 win = op; 5540 /* TYPE_UNSIGNED says whether this is a zero-extension. 5541 Let's avoid computing it if it does not affect WIN 5542 and if UNS will not be needed again. */ 5543 if ((uns 5544 || TREE_CODE (op) == NOP_EXPR 5545 || TREE_CODE (op) == CONVERT_EXPR) 5546 && TYPE_UNSIGNED (TREE_TYPE (op))) 5547 { 5548 uns = 1; 5549 win = op; 5550 } 5551 } 5552 } 5553 5554 if (TREE_CODE (op) == COMPONENT_REF 5555 /* Since type_for_size always gives an integer type. */ 5556 && TREE_CODE (type) != REAL_TYPE 5557 /* Don't crash if field not laid out yet. */ 5558 && DECL_SIZE (TREE_OPERAND (op, 1)) != 0 5559 && host_integerp (DECL_SIZE (TREE_OPERAND (op, 1)), 1)) 5560 { 5561 unsigned int innerprec 5562 = tree_low_cst (DECL_SIZE (TREE_OPERAND (op, 1)), 1); 5563 int unsignedp = (DECL_UNSIGNED (TREE_OPERAND (op, 1)) 5564 || TYPE_UNSIGNED (TREE_TYPE (TREE_OPERAND (op, 1)))); 5565 type = lang_hooks.types.type_for_size (innerprec, unsignedp); 5566 5567 /* We can get this structure field in the narrowest type it fits in. 5568 If FOR_TYPE is 0, do this only for a field that matches the 5569 narrower type exactly and is aligned for it 5570 The resulting extension to its nominal type (a fullword type) 5571 must fit the same conditions as for other extensions. */ 5572 5573 if (type != 0 5574 && INT_CST_LT_UNSIGNED (TYPE_SIZE (type), TYPE_SIZE (TREE_TYPE (op))) 5575 && (for_type || ! DECL_BIT_FIELD (TREE_OPERAND (op, 1))) 5576 && (! uns || final_prec <= innerprec || unsignedp)) 5577 { 5578 win = build3 (COMPONENT_REF, type, TREE_OPERAND (op, 0), 5579 TREE_OPERAND (op, 1), NULL_TREE); 5580 TREE_SIDE_EFFECTS (win) = TREE_SIDE_EFFECTS (op); 5581 TREE_THIS_VOLATILE (win) = TREE_THIS_VOLATILE (op); 5582 } 5583 } 5584 5585 return win; 5586} 5587 5588/* Return OP or a simpler expression for a narrower value 5589 which can be sign-extended or zero-extended to give back OP. 5590 Store in *UNSIGNEDP_PTR either 1 if the value should be zero-extended 5591 or 0 if the value should be sign-extended. */ 5592 5593tree 5594get_narrower (tree op, int *unsignedp_ptr) 5595{ 5596 int uns = 0; 5597 int first = 1; 5598 tree win = op; 5599 bool integral_p = INTEGRAL_TYPE_P (TREE_TYPE (op)); 5600 5601 while (TREE_CODE (op) == NOP_EXPR) 5602 { 5603 int bitschange 5604 = (TYPE_PRECISION (TREE_TYPE (op)) 5605 - TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (op, 0)))); 5606 5607 /* Truncations are many-one so cannot be removed. */ 5608 if (bitschange < 0) 5609 break; 5610 5611 /* See what's inside this conversion. If we decide to strip it, 5612 we will set WIN. */ 5613 5614 if (bitschange > 0) 5615 { 5616 op = TREE_OPERAND (op, 0); 5617 /* An extension: the outermost one can be stripped, 5618 but remember whether it is zero or sign extension. */ 5619 if (first) 5620 uns = TYPE_UNSIGNED (TREE_TYPE (op)); 5621 /* Otherwise, if a sign extension has been stripped, 5622 only sign extensions can now be stripped; 5623 if a zero extension has been stripped, only zero-extensions. */ 5624 else if (uns != TYPE_UNSIGNED (TREE_TYPE (op))) 5625 break; 5626 first = 0; 5627 } 5628 else /* bitschange == 0 */ 5629 { 5630 /* A change in nominal type can always be stripped, but we must 5631 preserve the unsignedness. */ 5632 if (first) 5633 uns = TYPE_UNSIGNED (TREE_TYPE (op)); 5634 first = 0; 5635 op = TREE_OPERAND (op, 0); 5636 /* Keep trying to narrow, but don't assign op to win if it 5637 would turn an integral type into something else. */ 5638 if (INTEGRAL_TYPE_P (TREE_TYPE (op)) != integral_p) 5639 continue; 5640 } 5641 5642 win = op; 5643 } 5644 5645 if (TREE_CODE (op) == COMPONENT_REF 5646 /* Since type_for_size always gives an integer type. */ 5647 && TREE_CODE (TREE_TYPE (op)) != REAL_TYPE 5648 /* Ensure field is laid out already. */ 5649 && DECL_SIZE (TREE_OPERAND (op, 1)) != 0 5650 && host_integerp (DECL_SIZE (TREE_OPERAND (op, 1)), 1)) 5651 { 5652 unsigned HOST_WIDE_INT innerprec 5653 = tree_low_cst (DECL_SIZE (TREE_OPERAND (op, 1)), 1); 5654 int unsignedp = (DECL_UNSIGNED (TREE_OPERAND (op, 1)) 5655 || TYPE_UNSIGNED (TREE_TYPE (TREE_OPERAND (op, 1)))); 5656 tree type = lang_hooks.types.type_for_size (innerprec, unsignedp); 5657 5658 /* We can get this structure field in a narrower type that fits it, 5659 but the resulting extension to its nominal type (a fullword type) 5660 must satisfy the same conditions as for other extensions. 5661 5662 Do this only for fields that are aligned (not bit-fields), 5663 because when bit-field insns will be used there is no 5664 advantage in doing this. */ 5665 5666 if (innerprec < TYPE_PRECISION (TREE_TYPE (op)) 5667 && ! DECL_BIT_FIELD (TREE_OPERAND (op, 1)) 5668 && (first || uns == DECL_UNSIGNED (TREE_OPERAND (op, 1))) 5669 && type != 0) 5670 { 5671 if (first) 5672 uns = DECL_UNSIGNED (TREE_OPERAND (op, 1)); 5673 win = fold_convert (type, op); 5674 } 5675 } 5676 5677 *unsignedp_ptr = uns; 5678 return win; 5679} 5680 5681/* Nonzero if integer constant C has a value that is permissible 5682 for type TYPE (an INTEGER_TYPE). */ 5683 5684int 5685int_fits_type_p (tree c, tree type) 5686{ 5687 tree type_low_bound = TYPE_MIN_VALUE (type); 5688 tree type_high_bound = TYPE_MAX_VALUE (type); 5689 bool ok_for_low_bound, ok_for_high_bound; 5690 tree tmp; 5691 5692 /* If at least one bound of the type is a constant integer, we can check 5693 ourselves and maybe make a decision. If no such decision is possible, but 5694 this type is a subtype, try checking against that. Otherwise, use 5695 force_fit_type, which checks against the precision. 5696 5697 Compute the status for each possibly constant bound, and return if we see 5698 one does not match. Use ok_for_xxx_bound for this purpose, assigning -1 5699 for "unknown if constant fits", 0 for "constant known *not* to fit" and 1 5700 for "constant known to fit". */ 5701 5702 /* Check if C >= type_low_bound. */ 5703 if (type_low_bound && TREE_CODE (type_low_bound) == INTEGER_CST) 5704 { 5705 if (tree_int_cst_lt (c, type_low_bound)) 5706 return 0; 5707 ok_for_low_bound = true; 5708 } 5709 else 5710 ok_for_low_bound = false; 5711 5712 /* Check if c <= type_high_bound. */ 5713 if (type_high_bound && TREE_CODE (type_high_bound) == INTEGER_CST) 5714 { 5715 if (tree_int_cst_lt (type_high_bound, c)) 5716 return 0; 5717 ok_for_high_bound = true; 5718 } 5719 else 5720 ok_for_high_bound = false; 5721 5722 /* If the constant fits both bounds, the result is known. */ 5723 if (ok_for_low_bound && ok_for_high_bound) 5724 return 1; 5725 5726 /* Perform some generic filtering which may allow making a decision 5727 even if the bounds are not constant. First, negative integers 5728 never fit in unsigned types, */ 5729 if (TYPE_UNSIGNED (type) && tree_int_cst_sgn (c) < 0) 5730 return 0; 5731 5732 /* Second, narrower types always fit in wider ones. */ 5733 if (TYPE_PRECISION (type) > TYPE_PRECISION (TREE_TYPE (c))) 5734 return 1; 5735 5736 /* Third, unsigned integers with top bit set never fit signed types. */ 5737 if (! TYPE_UNSIGNED (type) 5738 && TYPE_UNSIGNED (TREE_TYPE (c)) 5739 && tree_int_cst_msb (c)) 5740 return 0; 5741 5742 /* If we haven't been able to decide at this point, there nothing more we 5743 can check ourselves here. Look at the base type if we have one and it 5744 has the same precision. */ 5745 if (TREE_CODE (type) == INTEGER_TYPE 5746 && TREE_TYPE (type) != 0 5747 && TYPE_PRECISION (type) == TYPE_PRECISION (TREE_TYPE (type))) 5748 return int_fits_type_p (c, TREE_TYPE (type)); 5749 5750 /* Or to force_fit_type, if nothing else. */ 5751 tmp = copy_node (c); 5752 TREE_TYPE (tmp) = type; 5753 tmp = force_fit_type (tmp, -1, false, false); 5754 return TREE_INT_CST_HIGH (tmp) == TREE_INT_CST_HIGH (c) 5755 && TREE_INT_CST_LOW (tmp) == TREE_INT_CST_LOW (c); 5756} 5757 5758/* Subprogram of following function. Called by walk_tree. 5759 5760 Return *TP if it is an automatic variable or parameter of the 5761 function passed in as DATA. */ 5762 5763static tree 5764find_var_from_fn (tree *tp, int *walk_subtrees, void *data) 5765{ 5766 tree fn = (tree) data; 5767 5768 if (TYPE_P (*tp)) 5769 *walk_subtrees = 0; 5770 5771 else if (DECL_P (*tp) 5772 && lang_hooks.tree_inlining.auto_var_in_fn_p (*tp, fn)) 5773 return *tp; 5774 5775 return NULL_TREE; 5776} 5777 5778/* Returns true if T is, contains, or refers to a type with variable 5779 size. For METHOD_TYPEs and FUNCTION_TYPEs we exclude the 5780 arguments, but not the return type. If FN is nonzero, only return 5781 true if a modifier of the type or position of FN is a variable or 5782 parameter inside FN. 5783 5784 This concept is more general than that of C99 'variably modified types': 5785 in C99, a struct type is never variably modified because a VLA may not 5786 appear as a structure member. However, in GNU C code like: 5787 5788 struct S { int i[f()]; }; 5789 5790 is valid, and other languages may define similar constructs. */ 5791 5792bool 5793variably_modified_type_p (tree type, tree fn) 5794{ 5795 tree t; 5796 5797/* Test if T is either variable (if FN is zero) or an expression containing 5798 a variable in FN. */ 5799#define RETURN_TRUE_IF_VAR(T) \ 5800 do { tree _t = (T); \ 5801 if (_t && _t != error_mark_node && TREE_CODE (_t) != INTEGER_CST \ 5802 && (!fn || walk_tree (&_t, find_var_from_fn, fn, NULL))) \ 5803 return true; } while (0) 5804 5805 if (type == error_mark_node) 5806 return false; 5807 5808 /* If TYPE itself has variable size, it is variably modified. */ 5809 RETURN_TRUE_IF_VAR (TYPE_SIZE (type)); 5810 RETURN_TRUE_IF_VAR (TYPE_SIZE_UNIT (type)); 5811 5812 switch (TREE_CODE (type)) 5813 { 5814 case POINTER_TYPE: 5815 case REFERENCE_TYPE: 5816 case VECTOR_TYPE: 5817 if (variably_modified_type_p (TREE_TYPE (type), fn)) 5818 return true; 5819 break; 5820 5821 case FUNCTION_TYPE: 5822 case METHOD_TYPE: 5823 /* If TYPE is a function type, it is variably modified if the 5824 return type is variably modified. */ 5825 if (variably_modified_type_p (TREE_TYPE (type), fn)) 5826 return true; 5827 break; 5828 5829 case INTEGER_TYPE: 5830 case REAL_TYPE: 5831 case ENUMERAL_TYPE: 5832 case BOOLEAN_TYPE: 5833 /* Scalar types are variably modified if their end points 5834 aren't constant. */ 5835 RETURN_TRUE_IF_VAR (TYPE_MIN_VALUE (type)); 5836 RETURN_TRUE_IF_VAR (TYPE_MAX_VALUE (type)); 5837 break; 5838 5839 case RECORD_TYPE: 5840 case UNION_TYPE: 5841 case QUAL_UNION_TYPE: 5842 /* We can't see if any of the fields are variably-modified by the 5843 definition we normally use, since that would produce infinite 5844 recursion via pointers. */ 5845 /* This is variably modified if some field's type is. */ 5846 for (t = TYPE_FIELDS (type); t; t = TREE_CHAIN (t)) 5847 if (TREE_CODE (t) == FIELD_DECL) 5848 { 5849 RETURN_TRUE_IF_VAR (DECL_FIELD_OFFSET (t)); 5850 RETURN_TRUE_IF_VAR (DECL_SIZE (t)); 5851 RETURN_TRUE_IF_VAR (DECL_SIZE_UNIT (t)); 5852 5853 if (TREE_CODE (type) == QUAL_UNION_TYPE) 5854 RETURN_TRUE_IF_VAR (DECL_QUALIFIER (t)); 5855 } 5856 break; 5857 5858 case ARRAY_TYPE: 5859 /* Do not call ourselves to avoid infinite recursion. This is 5860 variably modified if the element type is. */ 5861 RETURN_TRUE_IF_VAR (TYPE_SIZE (TREE_TYPE (type))); 5862 RETURN_TRUE_IF_VAR (TYPE_SIZE_UNIT (TREE_TYPE (type))); 5863 break; 5864 5865 default: 5866 break; 5867 } 5868 5869 /* The current language may have other cases to check, but in general, 5870 all other types are not variably modified. */ 5871 return lang_hooks.tree_inlining.var_mod_type_p (type, fn); 5872 5873#undef RETURN_TRUE_IF_VAR 5874} 5875 5876/* Given a DECL or TYPE, return the scope in which it was declared, or 5877 NULL_TREE if there is no containing scope. */ 5878 5879tree 5880get_containing_scope (tree t) 5881{ 5882 return (TYPE_P (t) ? TYPE_CONTEXT (t) : DECL_CONTEXT (t)); 5883} 5884 5885/* Return the innermost context enclosing DECL that is 5886 a FUNCTION_DECL, or zero if none. */ 5887 5888tree 5889decl_function_context (tree decl) 5890{ 5891 tree context; 5892 5893 if (TREE_CODE (decl) == ERROR_MARK) 5894 return 0; 5895 5896 /* C++ virtual functions use DECL_CONTEXT for the class of the vtable 5897 where we look up the function at runtime. Such functions always take 5898 a first argument of type 'pointer to real context'. 5899 5900 C++ should really be fixed to use DECL_CONTEXT for the real context, 5901 and use something else for the "virtual context". */ 5902 else if (TREE_CODE (decl) == FUNCTION_DECL && DECL_VINDEX (decl)) 5903 context 5904 = TYPE_MAIN_VARIANT 5905 (TREE_TYPE (TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (decl))))); 5906 else 5907 context = DECL_CONTEXT (decl); 5908 5909 while (context && TREE_CODE (context) != FUNCTION_DECL) 5910 { 5911 if (TREE_CODE (context) == BLOCK) 5912 context = BLOCK_SUPERCONTEXT (context); 5913 else 5914 context = get_containing_scope (context); 5915 } 5916 5917 return context; 5918} 5919 5920/* Return the innermost context enclosing DECL that is 5921 a RECORD_TYPE, UNION_TYPE or QUAL_UNION_TYPE, or zero if none. 5922 TYPE_DECLs and FUNCTION_DECLs are transparent to this function. */ 5923 5924tree 5925decl_type_context (tree decl) 5926{ 5927 tree context = DECL_CONTEXT (decl); 5928 5929 while (context) 5930 switch (TREE_CODE (context)) 5931 { 5932 case NAMESPACE_DECL: 5933 case TRANSLATION_UNIT_DECL: 5934 return NULL_TREE; 5935 5936 case RECORD_TYPE: 5937 case UNION_TYPE: 5938 case QUAL_UNION_TYPE: 5939 return context; 5940 5941 case TYPE_DECL: 5942 case FUNCTION_DECL: 5943 context = DECL_CONTEXT (context); 5944 break; 5945 5946 case BLOCK: 5947 context = BLOCK_SUPERCONTEXT (context); 5948 break; 5949 5950 default: 5951 gcc_unreachable (); 5952 } 5953 5954 return NULL_TREE; 5955} 5956 5957/* CALL is a CALL_EXPR. Return the declaration for the function 5958 called, or NULL_TREE if the called function cannot be 5959 determined. */ 5960 5961tree 5962get_callee_fndecl (tree call) 5963{ 5964 tree addr; 5965 5966 if (call == error_mark_node) 5967 return call; 5968 5969 /* It's invalid to call this function with anything but a 5970 CALL_EXPR. */ 5971 gcc_assert (TREE_CODE (call) == CALL_EXPR); 5972 5973 /* The first operand to the CALL is the address of the function 5974 called. */ 5975 addr = TREE_OPERAND (call, 0); 5976 5977 STRIP_NOPS (addr); 5978 5979 /* If this is a readonly function pointer, extract its initial value. */ 5980 if (DECL_P (addr) && TREE_CODE (addr) != FUNCTION_DECL 5981 && TREE_READONLY (addr) && ! TREE_THIS_VOLATILE (addr) 5982 && DECL_INITIAL (addr)) 5983 addr = DECL_INITIAL (addr); 5984 5985 /* If the address is just `&f' for some function `f', then we know 5986 that `f' is being called. */ 5987 if (TREE_CODE (addr) == ADDR_EXPR 5988 && TREE_CODE (TREE_OPERAND (addr, 0)) == FUNCTION_DECL) 5989 return TREE_OPERAND (addr, 0); 5990 5991 /* We couldn't figure out what was being called. Maybe the front 5992 end has some idea. */ 5993 return lang_hooks.lang_get_callee_fndecl (call); 5994} 5995 5996/* Print debugging information about tree nodes generated during the compile, 5997 and any language-specific information. */ 5998 5999void 6000dump_tree_statistics (void) 6001{ 6002#ifdef GATHER_STATISTICS 6003 int i; 6004 int total_nodes, total_bytes; 6005#endif 6006 6007 fprintf (stderr, "\n??? tree nodes created\n\n"); 6008#ifdef GATHER_STATISTICS 6009 fprintf (stderr, "Kind Nodes Bytes\n"); 6010 fprintf (stderr, "---------------------------------------\n"); 6011 total_nodes = total_bytes = 0; 6012 for (i = 0; i < (int) all_kinds; i++) 6013 { 6014 fprintf (stderr, "%-20s %7d %10d\n", tree_node_kind_names[i], 6015 tree_node_counts[i], tree_node_sizes[i]); 6016 total_nodes += tree_node_counts[i]; 6017 total_bytes += tree_node_sizes[i]; 6018 } 6019 fprintf (stderr, "---------------------------------------\n"); 6020 fprintf (stderr, "%-20s %7d %10d\n", "Total", total_nodes, total_bytes); 6021 fprintf (stderr, "---------------------------------------\n"); 6022 ssanames_print_statistics (); 6023 phinodes_print_statistics (); 6024#else 6025 fprintf (stderr, "(No per-node statistics)\n"); 6026#endif 6027 print_type_hash_statistics (); 6028 print_debug_expr_statistics (); 6029 print_value_expr_statistics (); 6030 print_restrict_base_statistics (); 6031 lang_hooks.print_statistics (); 6032} 6033 6034#define FILE_FUNCTION_FORMAT "_GLOBAL__%s_%s" 6035 6036/* Generate a crc32 of a string. */ 6037 6038unsigned 6039crc32_string (unsigned chksum, const char *string) 6040{ 6041 do 6042 { 6043 unsigned value = *string << 24; 6044 unsigned ix; 6045 6046 for (ix = 8; ix--; value <<= 1) 6047 { 6048 unsigned feedback; 6049 6050 feedback = (value ^ chksum) & 0x80000000 ? 0x04c11db7 : 0; 6051 chksum <<= 1; 6052 chksum ^= feedback; 6053 } 6054 } 6055 while (*string++); 6056 return chksum; 6057} 6058 6059/* P is a string that will be used in a symbol. Mask out any characters 6060 that are not valid in that context. */ 6061 6062void 6063clean_symbol_name (char *p) 6064{ 6065 for (; *p; p++) 6066 if (! (ISALNUM (*p) 6067#ifndef NO_DOLLAR_IN_LABEL /* this for `$'; unlikely, but... -- kr */ 6068 || *p == '$' 6069#endif 6070#ifndef NO_DOT_IN_LABEL /* this for `.'; unlikely, but... */ 6071 || *p == '.' 6072#endif 6073 )) 6074 *p = '_'; 6075} 6076 6077/* Generate a name for a special-purpose function function. 6078 The generated name may need to be unique across the whole link. 6079 TYPE is some string to identify the purpose of this function to the 6080 linker or collect2; it must start with an uppercase letter, 6081 one of: 6082 I - for constructors 6083 D - for destructors 6084 N - for C++ anonymous namespaces 6085 F - for DWARF unwind frame information. */ 6086 6087tree 6088get_file_function_name (const char *type) 6089{ 6090 char *buf; 6091 const char *p; 6092 char *q; 6093 6094 /* If we already have a name we know to be unique, just use that. */ 6095 if (first_global_object_name) 6096 p = first_global_object_name; 6097 /* If the target is handling the constructors/destructors, they 6098 will be local to this file and the name is only necessary for 6099 debugging purposes. */ 6100 else if ((type[0] == 'I' || type[0] == 'D') && targetm.have_ctors_dtors) 6101 { 6102 const char *file = main_input_filename; 6103 if (! file) 6104 file = input_filename; 6105 /* Just use the file's basename, because the full pathname 6106 might be quite long. */ 6107 p = strrchr (file, '/'); 6108 if (p) 6109 p++; 6110 else 6111 p = file; 6112 p = q = ASTRDUP (p); 6113 clean_symbol_name (q); 6114 } 6115 else 6116 { 6117 /* Otherwise, the name must be unique across the entire link. 6118 We don't have anything that we know to be unique to this translation 6119 unit, so use what we do have and throw in some randomness. */ 6120 unsigned len; 6121 const char *name = weak_global_object_name; 6122 const char *file = main_input_filename; 6123 6124 if (! name) 6125 name = ""; 6126 if (! file) 6127 file = input_filename; 6128 6129 len = strlen (file); 6130 q = alloca (9 * 2 + len + 1); 6131 memcpy (q, file, len + 1); 6132 clean_symbol_name (q); 6133 6134 sprintf (q + len, "_%08X_%08X", crc32_string (0, name), 6135 crc32_string (0, flag_random_seed)); 6136 6137 p = q; 6138 } 6139 6140 buf = alloca (sizeof (FILE_FUNCTION_FORMAT) + strlen (p) + strlen (type)); 6141 6142 /* Set up the name of the file-level functions we may need. 6143 Use a global object (which is already required to be unique over 6144 the program) rather than the file name (which imposes extra 6145 constraints). */ 6146 sprintf (buf, FILE_FUNCTION_FORMAT, type, p); 6147 6148 return get_identifier (buf); 6149} 6150 6151#if defined ENABLE_TREE_CHECKING && (GCC_VERSION >= 2007) 6152 6153/* Complain that the tree code of NODE does not match the expected 0 6154 terminated list of trailing codes. The trailing code list can be 6155 empty, for a more vague error message. FILE, LINE, and FUNCTION 6156 are of the caller. */ 6157 6158void 6159tree_check_failed (const tree node, const char *file, 6160 int line, const char *function, ...) 6161{ 6162 va_list args; 6163 char *buffer; 6164 unsigned length = 0; 6165 int code; 6166 6167 va_start (args, function); 6168 while ((code = va_arg (args, int))) 6169 length += 4 + strlen (tree_code_name[code]); 6170 va_end (args); 6171 if (length) 6172 { 6173 va_start (args, function); 6174 length += strlen ("expected "); 6175 buffer = alloca (length); 6176 length = 0; 6177 while ((code = va_arg (args, int))) 6178 { 6179 const char *prefix = length ? " or " : "expected "; 6180 6181 strcpy (buffer + length, prefix); 6182 length += strlen (prefix); 6183 strcpy (buffer + length, tree_code_name[code]); 6184 length += strlen (tree_code_name[code]); 6185 } 6186 va_end (args); 6187 } 6188 else 6189 buffer = (char *)"unexpected node"; 6190 6191 internal_error ("tree check: %s, have %s in %s, at %s:%d", 6192 buffer, tree_code_name[TREE_CODE (node)], 6193 function, trim_filename (file), line); 6194} 6195 6196/* Complain that the tree code of NODE does match the expected 0 6197 terminated list of trailing codes. FILE, LINE, and FUNCTION are of 6198 the caller. */ 6199 6200void 6201tree_not_check_failed (const tree node, const char *file, 6202 int line, const char *function, ...) 6203{ 6204 va_list args; 6205 char *buffer; 6206 unsigned length = 0; 6207 int code; 6208 6209 va_start (args, function); 6210 while ((code = va_arg (args, int))) 6211 length += 4 + strlen (tree_code_name[code]); 6212 va_end (args); 6213 va_start (args, function); 6214 buffer = alloca (length); 6215 length = 0; 6216 while ((code = va_arg (args, int))) 6217 { 6218 if (length) 6219 { 6220 strcpy (buffer + length, " or "); 6221 length += 4; 6222 } 6223 strcpy (buffer + length, tree_code_name[code]); 6224 length += strlen (tree_code_name[code]); 6225 } 6226 va_end (args); 6227 6228 internal_error ("tree check: expected none of %s, have %s in %s, at %s:%d", 6229 buffer, tree_code_name[TREE_CODE (node)], 6230 function, trim_filename (file), line); 6231} 6232 6233/* Similar to tree_check_failed, except that we check for a class of tree 6234 code, given in CL. */ 6235 6236void 6237tree_class_check_failed (const tree node, const enum tree_code_class cl, 6238 const char *file, int line, const char *function) 6239{ 6240 internal_error 6241 ("tree check: expected class %qs, have %qs (%s) in %s, at %s:%d", 6242 TREE_CODE_CLASS_STRING (cl), 6243 TREE_CODE_CLASS_STRING (TREE_CODE_CLASS (TREE_CODE (node))), 6244 tree_code_name[TREE_CODE (node)], function, trim_filename (file), line); 6245} 6246 6247/* Similar to tree_check_failed, except that instead of specifying a 6248 dozen codes, use the knowledge that they're all sequential. */ 6249 6250void 6251tree_range_check_failed (const tree node, const char *file, int line, 6252 const char *function, enum tree_code c1, 6253 enum tree_code c2) 6254{ 6255 char *buffer; 6256 unsigned length = 0; 6257 enum tree_code c; 6258 6259 for (c = c1; c <= c2; ++c) 6260 length += 4 + strlen (tree_code_name[c]); 6261 6262 length += strlen ("expected "); 6263 buffer = alloca (length); 6264 length = 0; 6265 6266 for (c = c1; c <= c2; ++c) 6267 { 6268 const char *prefix = length ? " or " : "expected "; 6269 6270 strcpy (buffer + length, prefix); 6271 length += strlen (prefix); 6272 strcpy (buffer + length, tree_code_name[c]); 6273 length += strlen (tree_code_name[c]); 6274 } 6275 6276 internal_error ("tree check: %s, have %s in %s, at %s:%d", 6277 buffer, tree_code_name[TREE_CODE (node)], 6278 function, trim_filename (file), line); 6279} 6280 6281 6282/* Similar to tree_check_failed, except that we check that a tree does 6283 not have the specified code, given in CL. */ 6284 6285void 6286tree_not_class_check_failed (const tree node, const enum tree_code_class cl, 6287 const char *file, int line, const char *function) 6288{ 6289 internal_error 6290 ("tree check: did not expect class %qs, have %qs (%s) in %s, at %s:%d", 6291 TREE_CODE_CLASS_STRING (cl), 6292 TREE_CODE_CLASS_STRING (TREE_CODE_CLASS (TREE_CODE (node))), 6293 tree_code_name[TREE_CODE (node)], function, trim_filename (file), line); 6294} 6295 6296 6297/* Similar to tree_check_failed but applied to OMP_CLAUSE codes. */ 6298 6299void 6300omp_clause_check_failed (const tree node, const char *file, int line, 6301 const char *function, enum omp_clause_code code) 6302{ 6303 internal_error ("tree check: expected omp_clause %s, have %s in %s, at %s:%d", 6304 omp_clause_code_name[code], tree_code_name[TREE_CODE (node)], 6305 function, trim_filename (file), line); 6306} 6307 6308 6309/* Similar to tree_range_check_failed but applied to OMP_CLAUSE codes. */ 6310 6311void 6312omp_clause_range_check_failed (const tree node, const char *file, int line, 6313 const char *function, enum omp_clause_code c1, 6314 enum omp_clause_code c2) 6315{ 6316 char *buffer; 6317 unsigned length = 0; 6318 enum omp_clause_code c; 6319 6320 for (c = c1; c <= c2; ++c) 6321 length += 4 + strlen (omp_clause_code_name[c]); 6322 6323 length += strlen ("expected "); 6324 buffer = alloca (length); 6325 length = 0; 6326 6327 for (c = c1; c <= c2; ++c) 6328 { 6329 const char *prefix = length ? " or " : "expected "; 6330 6331 strcpy (buffer + length, prefix); 6332 length += strlen (prefix); 6333 strcpy (buffer + length, omp_clause_code_name[c]); 6334 length += strlen (omp_clause_code_name[c]); 6335 } 6336 6337 internal_error ("tree check: %s, have %s in %s, at %s:%d", 6338 buffer, omp_clause_code_name[TREE_CODE (node)], 6339 function, trim_filename (file), line); 6340} 6341 6342 6343#undef DEFTREESTRUCT 6344#define DEFTREESTRUCT(VAL, NAME) NAME, 6345 6346static const char *ts_enum_names[] = { 6347#include "treestruct.def" 6348}; 6349#undef DEFTREESTRUCT 6350 6351#define TS_ENUM_NAME(EN) (ts_enum_names[(EN)]) 6352 6353/* Similar to tree_class_check_failed, except that we check for 6354 whether CODE contains the tree structure identified by EN. */ 6355 6356void 6357tree_contains_struct_check_failed (const tree node, 6358 const enum tree_node_structure_enum en, 6359 const char *file, int line, 6360 const char *function) 6361{ 6362 internal_error 6363 ("tree check: expected tree that contains %qs structure, have %qs in %s, at %s:%d", 6364 TS_ENUM_NAME(en), 6365 tree_code_name[TREE_CODE (node)], function, trim_filename (file), line); 6366} 6367 6368 6369/* Similar to above, except that the check is for the bounds of a TREE_VEC's 6370 (dynamically sized) vector. */ 6371 6372void 6373tree_vec_elt_check_failed (int idx, int len, const char *file, int line, 6374 const char *function) 6375{ 6376 internal_error 6377 ("tree check: accessed elt %d of tree_vec with %d elts in %s, at %s:%d", 6378 idx + 1, len, function, trim_filename (file), line); 6379} 6380 6381/* Similar to above, except that the check is for the bounds of a PHI_NODE's 6382 (dynamically sized) vector. */ 6383 6384void 6385phi_node_elt_check_failed (int idx, int len, const char *file, int line, 6386 const char *function) 6387{ 6388 internal_error 6389 ("tree check: accessed elt %d of phi_node with %d elts in %s, at %s:%d", 6390 idx + 1, len, function, trim_filename (file), line); 6391} 6392 6393/* Similar to above, except that the check is for the bounds of the operand 6394 vector of an expression node. */ 6395 6396void 6397tree_operand_check_failed (int idx, enum tree_code code, const char *file, 6398 int line, const char *function) 6399{ 6400 internal_error 6401 ("tree check: accessed operand %d of %s with %d operands in %s, at %s:%d", 6402 idx + 1, tree_code_name[code], TREE_CODE_LENGTH (code), 6403 function, trim_filename (file), line); 6404} 6405 6406/* Similar to above, except that the check is for the number of 6407 operands of an OMP_CLAUSE node. */ 6408 6409void 6410omp_clause_operand_check_failed (int idx, tree t, const char *file, 6411 int line, const char *function) 6412{ 6413 internal_error 6414 ("tree check: accessed operand %d of omp_clause %s with %d operands " 6415 "in %s, at %s:%d", idx + 1, omp_clause_code_name[OMP_CLAUSE_CODE (t)], 6416 omp_clause_num_ops [OMP_CLAUSE_CODE (t)], function, 6417 trim_filename (file), line); 6418} 6419#endif /* ENABLE_TREE_CHECKING */ 6420 6421/* Create a new vector type node holding SUBPARTS units of type INNERTYPE, 6422 and mapped to the machine mode MODE. Initialize its fields and build 6423 the information necessary for debugging output. */ 6424 6425static tree 6426make_vector_type (tree innertype, int nunits, enum machine_mode mode) 6427{ 6428 tree t; 6429 hashval_t hashcode = 0; 6430 6431 /* Build a main variant, based on the main variant of the inner type, then 6432 use it to build the variant we return. */ 6433 if ((TYPE_ATTRIBUTES (innertype) || TYPE_QUALS (innertype)) 6434 && TYPE_MAIN_VARIANT (innertype) != innertype) 6435 return build_type_attribute_qual_variant ( 6436 make_vector_type (TYPE_MAIN_VARIANT (innertype), nunits, mode), 6437 TYPE_ATTRIBUTES (innertype), 6438 TYPE_QUALS (innertype)); 6439 6440 t = make_node (VECTOR_TYPE); 6441 TREE_TYPE (t) = TYPE_MAIN_VARIANT (innertype); 6442 SET_TYPE_VECTOR_SUBPARTS (t, nunits); 6443 TYPE_MODE (t) = mode; 6444 TYPE_READONLY (t) = TYPE_READONLY (innertype); 6445 TYPE_VOLATILE (t) = TYPE_VOLATILE (innertype); 6446 6447 layout_type (t); 6448 6449 { 6450 tree index = build_int_cst (NULL_TREE, nunits - 1); 6451 tree array = build_array_type (innertype, build_index_type (index)); 6452 tree rt = make_node (RECORD_TYPE); 6453 6454 TYPE_FIELDS (rt) = build_decl (FIELD_DECL, get_identifier ("f"), array); 6455 DECL_CONTEXT (TYPE_FIELDS (rt)) = rt; 6456 layout_type (rt); 6457 TYPE_DEBUG_REPRESENTATION_TYPE (t) = rt; 6458 /* In dwarfout.c, type lookup uses TYPE_UID numbers. We want to output 6459 the representation type, and we want to find that die when looking up 6460 the vector type. This is most easily achieved by making the TYPE_UID 6461 numbers equal. */ 6462 TYPE_UID (rt) = TYPE_UID (t); 6463 } 6464 6465 hashcode = iterative_hash_host_wide_int (VECTOR_TYPE, hashcode); 6466 hashcode = iterative_hash_host_wide_int (mode, hashcode); 6467 hashcode = iterative_hash_object (TYPE_HASH (innertype), hashcode); 6468 return type_hash_canon (hashcode, t); 6469} 6470 6471static tree 6472make_or_reuse_type (unsigned size, int unsignedp) 6473{ 6474 if (size == INT_TYPE_SIZE) 6475 return unsignedp ? unsigned_type_node : integer_type_node; 6476 if (size == CHAR_TYPE_SIZE) 6477 return unsignedp ? unsigned_char_type_node : signed_char_type_node; 6478 if (size == SHORT_TYPE_SIZE) 6479 return unsignedp ? short_unsigned_type_node : short_integer_type_node; 6480 if (size == LONG_TYPE_SIZE) 6481 return unsignedp ? long_unsigned_type_node : long_integer_type_node; 6482 if (size == LONG_LONG_TYPE_SIZE) 6483 return (unsignedp ? long_long_unsigned_type_node 6484 : long_long_integer_type_node); 6485 6486 if (unsignedp) 6487 return make_unsigned_type (size); 6488 else 6489 return make_signed_type (size); 6490} 6491 6492/* Create nodes for all integer types (and error_mark_node) using the sizes 6493 of C datatypes. The caller should call set_sizetype soon after calling 6494 this function to select one of the types as sizetype. */ 6495 6496void 6497build_common_tree_nodes (bool signed_char, bool signed_sizetype) 6498{ 6499 error_mark_node = make_node (ERROR_MARK); 6500 TREE_TYPE (error_mark_node) = error_mark_node; 6501 6502 initialize_sizetypes (signed_sizetype); 6503 6504 /* Define both `signed char' and `unsigned char'. */ 6505 signed_char_type_node = make_signed_type (CHAR_TYPE_SIZE); 6506 TYPE_STRING_FLAG (signed_char_type_node) = 1; 6507 unsigned_char_type_node = make_unsigned_type (CHAR_TYPE_SIZE); 6508 TYPE_STRING_FLAG (unsigned_char_type_node) = 1; 6509 6510 /* Define `char', which is like either `signed char' or `unsigned char' 6511 but not the same as either. */ 6512 char_type_node 6513 = (signed_char 6514 ? make_signed_type (CHAR_TYPE_SIZE) 6515 : make_unsigned_type (CHAR_TYPE_SIZE)); 6516 TYPE_STRING_FLAG (char_type_node) = 1; 6517 6518 short_integer_type_node = make_signed_type (SHORT_TYPE_SIZE); 6519 short_unsigned_type_node = make_unsigned_type (SHORT_TYPE_SIZE); 6520 integer_type_node = make_signed_type (INT_TYPE_SIZE); 6521 unsigned_type_node = make_unsigned_type (INT_TYPE_SIZE); 6522 long_integer_type_node = make_signed_type (LONG_TYPE_SIZE); 6523 long_unsigned_type_node = make_unsigned_type (LONG_TYPE_SIZE); 6524 long_long_integer_type_node = make_signed_type (LONG_LONG_TYPE_SIZE); 6525 long_long_unsigned_type_node = make_unsigned_type (LONG_LONG_TYPE_SIZE); 6526 6527 /* Define a boolean type. This type only represents boolean values but 6528 may be larger than char depending on the value of BOOL_TYPE_SIZE. 6529 Front ends which want to override this size (i.e. Java) can redefine 6530 boolean_type_node before calling build_common_tree_nodes_2. */ 6531 boolean_type_node = make_unsigned_type (BOOL_TYPE_SIZE); 6532 TREE_SET_CODE (boolean_type_node, BOOLEAN_TYPE); 6533 TYPE_MAX_VALUE (boolean_type_node) = build_int_cst (boolean_type_node, 1); 6534 TYPE_PRECISION (boolean_type_node) = 1; 6535 6536 /* Fill in the rest of the sized types. Reuse existing type nodes 6537 when possible. */ 6538 intQI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (QImode), 0); 6539 intHI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (HImode), 0); 6540 intSI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (SImode), 0); 6541 intDI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (DImode), 0); 6542 intTI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (TImode), 0); 6543 6544 unsigned_intQI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (QImode), 1); 6545 unsigned_intHI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (HImode), 1); 6546 unsigned_intSI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (SImode), 1); 6547 unsigned_intDI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (DImode), 1); 6548 unsigned_intTI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (TImode), 1); 6549 6550 access_public_node = get_identifier ("public"); 6551 access_protected_node = get_identifier ("protected"); 6552 access_private_node = get_identifier ("private"); 6553} 6554 6555/* Call this function after calling build_common_tree_nodes and set_sizetype. 6556 It will create several other common tree nodes. */ 6557 6558void 6559build_common_tree_nodes_2 (int short_double) 6560{ 6561 /* Define these next since types below may used them. */ 6562 integer_zero_node = build_int_cst (NULL_TREE, 0); 6563 integer_one_node = build_int_cst (NULL_TREE, 1); 6564 integer_minus_one_node = build_int_cst (NULL_TREE, -1); 6565 6566 size_zero_node = size_int (0); 6567 size_one_node = size_int (1); 6568 bitsize_zero_node = bitsize_int (0); 6569 bitsize_one_node = bitsize_int (1); 6570 bitsize_unit_node = bitsize_int (BITS_PER_UNIT); 6571 6572 boolean_false_node = TYPE_MIN_VALUE (boolean_type_node); 6573 boolean_true_node = TYPE_MAX_VALUE (boolean_type_node); 6574 6575 void_type_node = make_node (VOID_TYPE); 6576 layout_type (void_type_node); 6577 6578 /* We are not going to have real types in C with less than byte alignment, 6579 so we might as well not have any types that claim to have it. */ 6580 TYPE_ALIGN (void_type_node) = BITS_PER_UNIT; 6581 TYPE_USER_ALIGN (void_type_node) = 0; 6582 6583 null_pointer_node = build_int_cst (build_pointer_type (void_type_node), 0); 6584 layout_type (TREE_TYPE (null_pointer_node)); 6585 6586 ptr_type_node = build_pointer_type (void_type_node); 6587 const_ptr_type_node 6588 = build_pointer_type (build_type_variant (void_type_node, 1, 0)); 6589 fileptr_type_node = ptr_type_node; 6590 6591 float_type_node = make_node (REAL_TYPE); 6592 TYPE_PRECISION (float_type_node) = FLOAT_TYPE_SIZE; 6593 layout_type (float_type_node); 6594 6595 double_type_node = make_node (REAL_TYPE); 6596 if (short_double) 6597 TYPE_PRECISION (double_type_node) = FLOAT_TYPE_SIZE; 6598 else 6599 TYPE_PRECISION (double_type_node) = DOUBLE_TYPE_SIZE; 6600 layout_type (double_type_node); 6601 6602 long_double_type_node = make_node (REAL_TYPE); 6603 TYPE_PRECISION (long_double_type_node) = LONG_DOUBLE_TYPE_SIZE; 6604 layout_type (long_double_type_node); 6605 6606 float_ptr_type_node = build_pointer_type (float_type_node); 6607 double_ptr_type_node = build_pointer_type (double_type_node); 6608 long_double_ptr_type_node = build_pointer_type (long_double_type_node); 6609 integer_ptr_type_node = build_pointer_type (integer_type_node); 6610 6611 /* Fixed size integer types. */ 6612 uint32_type_node = build_nonstandard_integer_type (32, true); 6613 uint64_type_node = build_nonstandard_integer_type (64, true); 6614 6615 /* Decimal float types. */ 6616 dfloat32_type_node = make_node (REAL_TYPE); 6617 TYPE_PRECISION (dfloat32_type_node) = DECIMAL32_TYPE_SIZE; 6618 layout_type (dfloat32_type_node); 6619 TYPE_MODE (dfloat32_type_node) = SDmode; 6620 dfloat32_ptr_type_node = build_pointer_type (dfloat32_type_node); 6621 6622 dfloat64_type_node = make_node (REAL_TYPE); 6623 TYPE_PRECISION (dfloat64_type_node) = DECIMAL64_TYPE_SIZE; 6624 layout_type (dfloat64_type_node); 6625 TYPE_MODE (dfloat64_type_node) = DDmode; 6626 dfloat64_ptr_type_node = build_pointer_type (dfloat64_type_node); 6627 6628 dfloat128_type_node = make_node (REAL_TYPE); 6629 TYPE_PRECISION (dfloat128_type_node) = DECIMAL128_TYPE_SIZE; 6630 layout_type (dfloat128_type_node); 6631 TYPE_MODE (dfloat128_type_node) = TDmode; 6632 dfloat128_ptr_type_node = build_pointer_type (dfloat128_type_node); 6633 6634 complex_integer_type_node = make_node (COMPLEX_TYPE); 6635 TREE_TYPE (complex_integer_type_node) = integer_type_node; 6636 layout_type (complex_integer_type_node); 6637 6638 complex_float_type_node = make_node (COMPLEX_TYPE); 6639 TREE_TYPE (complex_float_type_node) = float_type_node; 6640 layout_type (complex_float_type_node); 6641 6642 complex_double_type_node = make_node (COMPLEX_TYPE); 6643 TREE_TYPE (complex_double_type_node) = double_type_node; 6644 layout_type (complex_double_type_node); 6645 6646 complex_long_double_type_node = make_node (COMPLEX_TYPE); 6647 TREE_TYPE (complex_long_double_type_node) = long_double_type_node; 6648 layout_type (complex_long_double_type_node); 6649 6650 { 6651 tree t = targetm.build_builtin_va_list (); 6652 6653 /* Many back-ends define record types without setting TYPE_NAME. 6654 If we copied the record type here, we'd keep the original 6655 record type without a name. This breaks name mangling. So, 6656 don't copy record types and let c_common_nodes_and_builtins() 6657 declare the type to be __builtin_va_list. */ 6658 if (TREE_CODE (t) != RECORD_TYPE) 6659 t = build_variant_type_copy (t); 6660 6661 va_list_type_node = t; 6662 } 6663} 6664 6665/* A subroutine of build_common_builtin_nodes. Define a builtin function. */ 6666 6667static void 6668local_define_builtin (const char *name, tree type, enum built_in_function code, 6669 const char *library_name, int ecf_flags) 6670{ 6671 tree decl; 6672 6673 decl = lang_hooks.builtin_function (name, type, code, BUILT_IN_NORMAL, 6674 library_name, NULL_TREE); 6675 if (ecf_flags & ECF_CONST) 6676 TREE_READONLY (decl) = 1; 6677 if (ecf_flags & ECF_PURE) 6678 DECL_IS_PURE (decl) = 1; 6679 if (ecf_flags & ECF_NORETURN) 6680 TREE_THIS_VOLATILE (decl) = 1; 6681 if (ecf_flags & ECF_NOTHROW) 6682 TREE_NOTHROW (decl) = 1; 6683 if (ecf_flags & ECF_MALLOC) 6684 DECL_IS_MALLOC (decl) = 1; 6685 6686 built_in_decls[code] = decl; 6687 implicit_built_in_decls[code] = decl; 6688} 6689 6690/* Call this function after instantiating all builtins that the language 6691 front end cares about. This will build the rest of the builtins that 6692 are relied upon by the tree optimizers and the middle-end. */ 6693 6694void 6695build_common_builtin_nodes (void) 6696{ 6697 tree tmp, ftype; 6698 6699 if (built_in_decls[BUILT_IN_MEMCPY] == NULL 6700 || built_in_decls[BUILT_IN_MEMMOVE] == NULL) 6701 { 6702 tmp = tree_cons (NULL_TREE, size_type_node, void_list_node); 6703 tmp = tree_cons (NULL_TREE, const_ptr_type_node, tmp); 6704 tmp = tree_cons (NULL_TREE, ptr_type_node, tmp); 6705 ftype = build_function_type (ptr_type_node, tmp); 6706 6707 if (built_in_decls[BUILT_IN_MEMCPY] == NULL) 6708 local_define_builtin ("__builtin_memcpy", ftype, BUILT_IN_MEMCPY, 6709 "memcpy", ECF_NOTHROW); 6710 if (built_in_decls[BUILT_IN_MEMMOVE] == NULL) 6711 local_define_builtin ("__builtin_memmove", ftype, BUILT_IN_MEMMOVE, 6712 "memmove", ECF_NOTHROW); 6713 } 6714 6715 if (built_in_decls[BUILT_IN_MEMCMP] == NULL) 6716 { 6717 tmp = tree_cons (NULL_TREE, size_type_node, void_list_node); 6718 tmp = tree_cons (NULL_TREE, const_ptr_type_node, tmp); 6719 tmp = tree_cons (NULL_TREE, const_ptr_type_node, tmp); 6720 ftype = build_function_type (integer_type_node, tmp); 6721 local_define_builtin ("__builtin_memcmp", ftype, BUILT_IN_MEMCMP, 6722 "memcmp", ECF_PURE | ECF_NOTHROW); 6723 } 6724 6725 if (built_in_decls[BUILT_IN_MEMSET] == NULL) 6726 { 6727 tmp = tree_cons (NULL_TREE, size_type_node, void_list_node); 6728 tmp = tree_cons (NULL_TREE, integer_type_node, tmp); 6729 tmp = tree_cons (NULL_TREE, ptr_type_node, tmp); 6730 ftype = build_function_type (ptr_type_node, tmp); 6731 local_define_builtin ("__builtin_memset", ftype, BUILT_IN_MEMSET, 6732 "memset", ECF_NOTHROW); 6733 } 6734 6735 if (built_in_decls[BUILT_IN_ALLOCA] == NULL) 6736 { 6737 tmp = tree_cons (NULL_TREE, size_type_node, void_list_node); 6738 ftype = build_function_type (ptr_type_node, tmp); 6739 local_define_builtin ("__builtin_alloca", ftype, BUILT_IN_ALLOCA, 6740 "alloca", ECF_NOTHROW | ECF_MALLOC); 6741 } 6742 6743 tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node); 6744 tmp = tree_cons (NULL_TREE, ptr_type_node, tmp); 6745 tmp = tree_cons (NULL_TREE, ptr_type_node, tmp); 6746 ftype = build_function_type (void_type_node, tmp); 6747 local_define_builtin ("__builtin_init_trampoline", ftype, 6748 BUILT_IN_INIT_TRAMPOLINE, 6749 "__builtin_init_trampoline", ECF_NOTHROW); 6750 6751 tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node); 6752 ftype = build_function_type (ptr_type_node, tmp); 6753 local_define_builtin ("__builtin_adjust_trampoline", ftype, 6754 BUILT_IN_ADJUST_TRAMPOLINE, 6755 "__builtin_adjust_trampoline", 6756 ECF_CONST | ECF_NOTHROW); 6757 6758 tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node); 6759 tmp = tree_cons (NULL_TREE, ptr_type_node, tmp); 6760 ftype = build_function_type (void_type_node, tmp); 6761 local_define_builtin ("__builtin_nonlocal_goto", ftype, 6762 BUILT_IN_NONLOCAL_GOTO, 6763 "__builtin_nonlocal_goto", 6764 ECF_NORETURN | ECF_NOTHROW); 6765 6766 tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node); 6767 tmp = tree_cons (NULL_TREE, ptr_type_node, tmp); 6768 ftype = build_function_type (void_type_node, tmp); 6769 local_define_builtin ("__builtin_setjmp_setup", ftype, 6770 BUILT_IN_SETJMP_SETUP, 6771 "__builtin_setjmp_setup", ECF_NOTHROW); 6772 6773 tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node); 6774 ftype = build_function_type (ptr_type_node, tmp); 6775 local_define_builtin ("__builtin_setjmp_dispatcher", ftype, 6776 BUILT_IN_SETJMP_DISPATCHER, 6777 "__builtin_setjmp_dispatcher", 6778 ECF_PURE | ECF_NOTHROW); 6779 6780 tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node); 6781 ftype = build_function_type (void_type_node, tmp); 6782 local_define_builtin ("__builtin_setjmp_receiver", ftype, 6783 BUILT_IN_SETJMP_RECEIVER, 6784 "__builtin_setjmp_receiver", ECF_NOTHROW); 6785 6786 ftype = build_function_type (ptr_type_node, void_list_node); 6787 local_define_builtin ("__builtin_stack_save", ftype, BUILT_IN_STACK_SAVE, 6788 "__builtin_stack_save", ECF_NOTHROW); 6789 6790 tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node); 6791 ftype = build_function_type (void_type_node, tmp); 6792 local_define_builtin ("__builtin_stack_restore", ftype, 6793 BUILT_IN_STACK_RESTORE, 6794 "__builtin_stack_restore", ECF_NOTHROW); 6795 6796 ftype = build_function_type (void_type_node, void_list_node); 6797 local_define_builtin ("__builtin_profile_func_enter", ftype, 6798 BUILT_IN_PROFILE_FUNC_ENTER, "profile_func_enter", 0); 6799 local_define_builtin ("__builtin_profile_func_exit", ftype, 6800 BUILT_IN_PROFILE_FUNC_EXIT, "profile_func_exit", 0); 6801 6802 /* Complex multiplication and division. These are handled as builtins 6803 rather than optabs because emit_library_call_value doesn't support 6804 complex. Further, we can do slightly better with folding these 6805 beasties if the real and complex parts of the arguments are separate. */ 6806 { 6807 enum machine_mode mode; 6808 6809 for (mode = MIN_MODE_COMPLEX_FLOAT; mode <= MAX_MODE_COMPLEX_FLOAT; ++mode) 6810 { 6811 char mode_name_buf[4], *q; 6812 const char *p; 6813 enum built_in_function mcode, dcode; 6814 tree type, inner_type; 6815 6816 type = lang_hooks.types.type_for_mode (mode, 0); 6817 if (type == NULL) 6818 continue; 6819 inner_type = TREE_TYPE (type); 6820 6821 tmp = tree_cons (NULL_TREE, inner_type, void_list_node); 6822 tmp = tree_cons (NULL_TREE, inner_type, tmp); 6823 tmp = tree_cons (NULL_TREE, inner_type, tmp); 6824 tmp = tree_cons (NULL_TREE, inner_type, tmp); 6825 ftype = build_function_type (type, tmp); 6826 6827 mcode = BUILT_IN_COMPLEX_MUL_MIN + mode - MIN_MODE_COMPLEX_FLOAT; 6828 dcode = BUILT_IN_COMPLEX_DIV_MIN + mode - MIN_MODE_COMPLEX_FLOAT; 6829 6830 for (p = GET_MODE_NAME (mode), q = mode_name_buf; *p; p++, q++) 6831 *q = TOLOWER (*p); 6832 *q = '\0'; 6833 6834 built_in_names[mcode] = concat ("__mul", mode_name_buf, "3", NULL); 6835 local_define_builtin (built_in_names[mcode], ftype, mcode, 6836 built_in_names[mcode], ECF_CONST | ECF_NOTHROW); 6837 6838 built_in_names[dcode] = concat ("__div", mode_name_buf, "3", NULL); 6839 local_define_builtin (built_in_names[dcode], ftype, dcode, 6840 built_in_names[dcode], ECF_CONST | ECF_NOTHROW); 6841 } 6842 } 6843} 6844 6845/* HACK. GROSS. This is absolutely disgusting. I wish there was a 6846 better way. 6847 6848 If we requested a pointer to a vector, build up the pointers that 6849 we stripped off while looking for the inner type. Similarly for 6850 return values from functions. 6851 6852 The argument TYPE is the top of the chain, and BOTTOM is the 6853 new type which we will point to. */ 6854 6855tree 6856reconstruct_complex_type (tree type, tree bottom) 6857{ 6858 tree inner, outer; 6859 6860 if (POINTER_TYPE_P (type)) 6861 { 6862 inner = reconstruct_complex_type (TREE_TYPE (type), bottom); 6863 outer = build_pointer_type (inner); 6864 } 6865 else if (TREE_CODE (type) == ARRAY_TYPE) 6866 { 6867 inner = reconstruct_complex_type (TREE_TYPE (type), bottom); 6868 outer = build_array_type (inner, TYPE_DOMAIN (type)); 6869 } 6870 else if (TREE_CODE (type) == FUNCTION_TYPE) 6871 { 6872 inner = reconstruct_complex_type (TREE_TYPE (type), bottom); 6873 outer = build_function_type (inner, TYPE_ARG_TYPES (type)); 6874 } 6875 else if (TREE_CODE (type) == METHOD_TYPE) 6876 { 6877 tree argtypes; 6878 inner = reconstruct_complex_type (TREE_TYPE (type), bottom); 6879 /* The build_method_type_directly() routine prepends 'this' to argument list, 6880 so we must compensate by getting rid of it. */ 6881 argtypes = TYPE_ARG_TYPES (type); 6882 outer = build_method_type_directly (TYPE_METHOD_BASETYPE (type), 6883 inner, 6884 TYPE_ARG_TYPES (type)); 6885 TYPE_ARG_TYPES (outer) = argtypes; 6886 } 6887 else 6888 return bottom; 6889 6890 TYPE_READONLY (outer) = TYPE_READONLY (type); 6891 TYPE_VOLATILE (outer) = TYPE_VOLATILE (type); 6892 6893 return outer; 6894} 6895 6896/* Returns a vector tree node given a mode (integer, vector, or BLKmode) and 6897 the inner type. */ 6898tree 6899build_vector_type_for_mode (tree innertype, enum machine_mode mode) 6900{ 6901 int nunits; 6902 6903 switch (GET_MODE_CLASS (mode)) 6904 { 6905 case MODE_VECTOR_INT: 6906 case MODE_VECTOR_FLOAT: 6907 nunits = GET_MODE_NUNITS (mode); 6908 break; 6909 6910 case MODE_INT: 6911 /* Check that there are no leftover bits. */ 6912 gcc_assert (GET_MODE_BITSIZE (mode) 6913 % TREE_INT_CST_LOW (TYPE_SIZE (innertype)) == 0); 6914 6915 nunits = GET_MODE_BITSIZE (mode) 6916 / TREE_INT_CST_LOW (TYPE_SIZE (innertype)); 6917 break; 6918 6919 default: 6920 gcc_unreachable (); 6921 } 6922 6923 return make_vector_type (innertype, nunits, mode); 6924} 6925 6926/* Similarly, but takes the inner type and number of units, which must be 6927 a power of two. */ 6928 6929tree 6930build_vector_type (tree innertype, int nunits) 6931{ 6932 return make_vector_type (innertype, nunits, VOIDmode); 6933} 6934 6935 6936/* Build RESX_EXPR with given REGION_NUMBER. */ 6937tree 6938build_resx (int region_number) 6939{ 6940 tree t; 6941 t = build1 (RESX_EXPR, void_type_node, 6942 build_int_cst (NULL_TREE, region_number)); 6943 return t; 6944} 6945 6946/* Given an initializer INIT, return TRUE if INIT is zero or some 6947 aggregate of zeros. Otherwise return FALSE. */ 6948bool 6949initializer_zerop (tree init) 6950{ 6951 tree elt; 6952 6953 STRIP_NOPS (init); 6954 6955 switch (TREE_CODE (init)) 6956 { 6957 case INTEGER_CST: 6958 return integer_zerop (init); 6959 6960 case REAL_CST: 6961 /* ??? Note that this is not correct for C4X float formats. There, 6962 a bit pattern of all zeros is 1.0; 0.0 is encoded with the most 6963 negative exponent. */ 6964 return real_zerop (init) 6965 && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (init)); 6966 6967 case COMPLEX_CST: 6968 return integer_zerop (init) 6969 || (real_zerop (init) 6970 && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (TREE_REALPART (init))) 6971 && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (TREE_IMAGPART (init)))); 6972 6973 case VECTOR_CST: 6974 for (elt = TREE_VECTOR_CST_ELTS (init); elt; elt = TREE_CHAIN (elt)) 6975 if (!initializer_zerop (TREE_VALUE (elt))) 6976 return false; 6977 return true; 6978 6979 case CONSTRUCTOR: 6980 { 6981 unsigned HOST_WIDE_INT idx; 6982 6983 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (init), idx, elt) 6984 if (!initializer_zerop (elt)) 6985 return false; 6986 return true; 6987 } 6988 6989 default: 6990 return false; 6991 } 6992} 6993 6994/* Build an empty statement. */ 6995 6996tree 6997build_empty_stmt (void) 6998{ 6999 return build1 (NOP_EXPR, void_type_node, size_zero_node); 7000} 7001 7002 7003/* Build an OpenMP clause with code CODE. */ 7004 7005tree 7006build_omp_clause (enum omp_clause_code code) 7007{ 7008 tree t; 7009 int size, length; 7010 7011 length = omp_clause_num_ops[code]; 7012 size = (sizeof (struct tree_omp_clause) + (length - 1) * sizeof (tree)); 7013 7014 t = ggc_alloc (size); 7015 memset (t, 0, size); 7016 TREE_SET_CODE (t, OMP_CLAUSE); 7017 OMP_CLAUSE_SET_CODE (t, code); 7018 7019#ifdef GATHER_STATISTICS 7020 tree_node_counts[(int) omp_clause_kind]++; 7021 tree_node_sizes[(int) omp_clause_kind] += size; 7022#endif 7023 7024 return t; 7025} 7026 7027 7028/* Returns true if it is possible to prove that the index of 7029 an array access REF (an ARRAY_REF expression) falls into the 7030 array bounds. */ 7031 7032bool 7033in_array_bounds_p (tree ref) 7034{ 7035 tree idx = TREE_OPERAND (ref, 1); 7036 tree min, max; 7037 7038 if (TREE_CODE (idx) != INTEGER_CST) 7039 return false; 7040 7041 min = array_ref_low_bound (ref); 7042 max = array_ref_up_bound (ref); 7043 if (!min 7044 || !max 7045 || TREE_CODE (min) != INTEGER_CST 7046 || TREE_CODE (max) != INTEGER_CST) 7047 return false; 7048 7049 if (tree_int_cst_lt (idx, min) 7050 || tree_int_cst_lt (max, idx)) 7051 return false; 7052 7053 return true; 7054} 7055 7056/* Returns true if it is possible to prove that the range of 7057 an array access REF (an ARRAY_RANGE_REF expression) falls 7058 into the array bounds. */ 7059 7060bool 7061range_in_array_bounds_p (tree ref) 7062{ 7063 tree domain_type = TYPE_DOMAIN (TREE_TYPE (ref)); 7064 tree range_min, range_max, min, max; 7065 7066 range_min = TYPE_MIN_VALUE (domain_type); 7067 range_max = TYPE_MAX_VALUE (domain_type); 7068 if (!range_min 7069 || !range_max 7070 || TREE_CODE (range_min) != INTEGER_CST 7071 || TREE_CODE (range_max) != INTEGER_CST) 7072 return false; 7073 7074 min = array_ref_low_bound (ref); 7075 max = array_ref_up_bound (ref); 7076 if (!min 7077 || !max 7078 || TREE_CODE (min) != INTEGER_CST 7079 || TREE_CODE (max) != INTEGER_CST) 7080 return false; 7081 7082 if (tree_int_cst_lt (range_min, min) 7083 || tree_int_cst_lt (max, range_max)) 7084 return false; 7085 7086 return true; 7087} 7088 7089/* Return true if T (assumed to be a DECL) is a global variable. */ 7090 7091bool 7092is_global_var (tree t) 7093{ 7094 if (MTAG_P (t)) 7095 return (TREE_STATIC (t) || MTAG_GLOBAL (t)); 7096 else 7097 return (TREE_STATIC (t) || DECL_EXTERNAL (t)); 7098} 7099 7100/* Return true if T (assumed to be a DECL) must be assigned a memory 7101 location. */ 7102 7103bool 7104needs_to_live_in_memory (tree t) 7105{ 7106 return (TREE_ADDRESSABLE (t) 7107 || is_global_var (t) 7108 || (TREE_CODE (t) == RESULT_DECL 7109 && aggregate_value_p (t, current_function_decl))); 7110} 7111 7112/* There are situations in which a language considers record types 7113 compatible which have different field lists. Decide if two fields 7114 are compatible. It is assumed that the parent records are compatible. */ 7115 7116bool 7117fields_compatible_p (tree f1, tree f2) 7118{ 7119 if (!operand_equal_p (DECL_FIELD_BIT_OFFSET (f1), 7120 DECL_FIELD_BIT_OFFSET (f2), OEP_ONLY_CONST)) 7121 return false; 7122 7123 if (!operand_equal_p (DECL_FIELD_OFFSET (f1), 7124 DECL_FIELD_OFFSET (f2), OEP_ONLY_CONST)) 7125 return false; 7126 7127 if (!lang_hooks.types_compatible_p (TREE_TYPE (f1), TREE_TYPE (f2))) 7128 return false; 7129 7130 return true; 7131} 7132 7133/* Locate within RECORD a field that is compatible with ORIG_FIELD. */ 7134 7135tree 7136find_compatible_field (tree record, tree orig_field) 7137{ 7138 tree f; 7139 7140 for (f = TYPE_FIELDS (record); f ; f = TREE_CHAIN (f)) 7141 if (TREE_CODE (f) == FIELD_DECL 7142 && fields_compatible_p (f, orig_field)) 7143 return f; 7144 7145 /* ??? Why isn't this on the main fields list? */ 7146 f = TYPE_VFIELD (record); 7147 if (f && TREE_CODE (f) == FIELD_DECL 7148 && fields_compatible_p (f, orig_field)) 7149 return f; 7150 7151 /* ??? We should abort here, but Java appears to do Bad Things 7152 with inherited fields. */ 7153 return orig_field; 7154} 7155 7156/* Return value of a constant X. */ 7157 7158HOST_WIDE_INT 7159int_cst_value (tree x) 7160{ 7161 unsigned bits = TYPE_PRECISION (TREE_TYPE (x)); 7162 unsigned HOST_WIDE_INT val = TREE_INT_CST_LOW (x); 7163 bool negative = ((val >> (bits - 1)) & 1) != 0; 7164 7165 gcc_assert (bits <= HOST_BITS_PER_WIDE_INT); 7166 7167 if (negative) 7168 val |= (~(unsigned HOST_WIDE_INT) 0) << (bits - 1) << 1; 7169 else 7170 val &= ~((~(unsigned HOST_WIDE_INT) 0) << (bits - 1) << 1); 7171 7172 return val; 7173} 7174 7175/* Returns the greatest common divisor of A and B, which must be 7176 INTEGER_CSTs. */ 7177 7178tree 7179tree_fold_gcd (tree a, tree b) 7180{ 7181 tree a_mod_b; 7182 tree type = TREE_TYPE (a); 7183 7184 gcc_assert (TREE_CODE (a) == INTEGER_CST); 7185 gcc_assert (TREE_CODE (b) == INTEGER_CST); 7186 7187 if (integer_zerop (a)) 7188 return b; 7189 7190 if (integer_zerop (b)) 7191 return a; 7192 7193 if (tree_int_cst_sgn (a) == -1) 7194 a = fold_build2 (MULT_EXPR, type, a, 7195 build_int_cst (type, -1)); 7196 7197 if (tree_int_cst_sgn (b) == -1) 7198 b = fold_build2 (MULT_EXPR, type, b, 7199 build_int_cst (type, -1)); 7200 7201 while (1) 7202 { 7203 a_mod_b = fold_build2 (FLOOR_MOD_EXPR, type, a, b); 7204 7205 if (!TREE_INT_CST_LOW (a_mod_b) 7206 && !TREE_INT_CST_HIGH (a_mod_b)) 7207 return b; 7208 7209 a = b; 7210 b = a_mod_b; 7211 } 7212} 7213 7214/* Returns unsigned variant of TYPE. */ 7215 7216tree 7217unsigned_type_for (tree type) 7218{ 7219 if (POINTER_TYPE_P (type)) 7220 return lang_hooks.types.unsigned_type (size_type_node); 7221 return lang_hooks.types.unsigned_type (type); 7222} 7223 7224/* Returns signed variant of TYPE. */ 7225 7226tree 7227signed_type_for (tree type) 7228{ 7229 if (POINTER_TYPE_P (type)) 7230 return lang_hooks.types.signed_type (size_type_node); 7231 return lang_hooks.types.signed_type (type); 7232} 7233 7234/* Returns the largest value obtainable by casting something in INNER type to 7235 OUTER type. */ 7236 7237tree 7238upper_bound_in_type (tree outer, tree inner) 7239{ 7240 unsigned HOST_WIDE_INT lo, hi; 7241 unsigned int det = 0; 7242 unsigned oprec = TYPE_PRECISION (outer); 7243 unsigned iprec = TYPE_PRECISION (inner); 7244 unsigned prec; 7245 7246 /* Compute a unique number for every combination. */ 7247 det |= (oprec > iprec) ? 4 : 0; 7248 det |= TYPE_UNSIGNED (outer) ? 2 : 0; 7249 det |= TYPE_UNSIGNED (inner) ? 1 : 0; 7250 7251 /* Determine the exponent to use. */ 7252 switch (det) 7253 { 7254 case 0: 7255 case 1: 7256 /* oprec <= iprec, outer: signed, inner: don't care. */ 7257 prec = oprec - 1; 7258 break; 7259 case 2: 7260 case 3: 7261 /* oprec <= iprec, outer: unsigned, inner: don't care. */ 7262 prec = oprec; 7263 break; 7264 case 4: 7265 /* oprec > iprec, outer: signed, inner: signed. */ 7266 prec = iprec - 1; 7267 break; 7268 case 5: 7269 /* oprec > iprec, outer: signed, inner: unsigned. */ 7270 prec = iprec; 7271 break; 7272 case 6: 7273 /* oprec > iprec, outer: unsigned, inner: signed. */ 7274 prec = oprec; 7275 break; 7276 case 7: 7277 /* oprec > iprec, outer: unsigned, inner: unsigned. */ 7278 prec = iprec; 7279 break; 7280 default: 7281 gcc_unreachable (); 7282 } 7283 7284 /* Compute 2^^prec - 1. */ 7285 if (prec <= HOST_BITS_PER_WIDE_INT) 7286 { 7287 hi = 0; 7288 lo = ((~(unsigned HOST_WIDE_INT) 0) 7289 >> (HOST_BITS_PER_WIDE_INT - prec)); 7290 } 7291 else 7292 { 7293 hi = ((~(unsigned HOST_WIDE_INT) 0) 7294 >> (2 * HOST_BITS_PER_WIDE_INT - prec)); 7295 lo = ~(unsigned HOST_WIDE_INT) 0; 7296 } 7297 7298 return build_int_cst_wide (outer, lo, hi); 7299} 7300 7301/* Returns the smallest value obtainable by casting something in INNER type to 7302 OUTER type. */ 7303 7304tree 7305lower_bound_in_type (tree outer, tree inner) 7306{ 7307 unsigned HOST_WIDE_INT lo, hi; 7308 unsigned oprec = TYPE_PRECISION (outer); 7309 unsigned iprec = TYPE_PRECISION (inner); 7310 7311 /* If OUTER type is unsigned, we can definitely cast 0 to OUTER type 7312 and obtain 0. */ 7313 if (TYPE_UNSIGNED (outer) 7314 /* If we are widening something of an unsigned type, OUTER type 7315 contains all values of INNER type. In particular, both INNER 7316 and OUTER types have zero in common. */ 7317 || (oprec > iprec && TYPE_UNSIGNED (inner))) 7318 lo = hi = 0; 7319 else 7320 { 7321 /* If we are widening a signed type to another signed type, we 7322 want to obtain -2^^(iprec-1). If we are keeping the 7323 precision or narrowing to a signed type, we want to obtain 7324 -2^(oprec-1). */ 7325 unsigned prec = oprec > iprec ? iprec : oprec; 7326 7327 if (prec <= HOST_BITS_PER_WIDE_INT) 7328 { 7329 hi = ~(unsigned HOST_WIDE_INT) 0; 7330 lo = (~(unsigned HOST_WIDE_INT) 0) << (prec - 1); 7331 } 7332 else 7333 { 7334 hi = ((~(unsigned HOST_WIDE_INT) 0) 7335 << (prec - HOST_BITS_PER_WIDE_INT - 1)); 7336 lo = 0; 7337 } 7338 } 7339 7340 return build_int_cst_wide (outer, lo, hi); 7341} 7342 7343/* Return nonzero if two operands that are suitable for PHI nodes are 7344 necessarily equal. Specifically, both ARG0 and ARG1 must be either 7345 SSA_NAME or invariant. Note that this is strictly an optimization. 7346 That is, callers of this function can directly call operand_equal_p 7347 and get the same result, only slower. */ 7348 7349int 7350operand_equal_for_phi_arg_p (tree arg0, tree arg1) 7351{ 7352 if (arg0 == arg1) 7353 return 1; 7354 if (TREE_CODE (arg0) == SSA_NAME || TREE_CODE (arg1) == SSA_NAME) 7355 return 0; 7356 return operand_equal_p (arg0, arg1, 0); 7357} 7358 7359/* Returns number of zeros at the end of binary representation of X. 7360 7361 ??? Use ffs if available? */ 7362 7363tree 7364num_ending_zeros (tree x) 7365{ 7366 unsigned HOST_WIDE_INT fr, nfr; 7367 unsigned num, abits; 7368 tree type = TREE_TYPE (x); 7369 7370 if (TREE_INT_CST_LOW (x) == 0) 7371 { 7372 num = HOST_BITS_PER_WIDE_INT; 7373 fr = TREE_INT_CST_HIGH (x); 7374 } 7375 else 7376 { 7377 num = 0; 7378 fr = TREE_INT_CST_LOW (x); 7379 } 7380 7381 for (abits = HOST_BITS_PER_WIDE_INT / 2; abits; abits /= 2) 7382 { 7383 nfr = fr >> abits; 7384 if (nfr << abits == fr) 7385 { 7386 num += abits; 7387 fr = nfr; 7388 } 7389 } 7390 7391 if (num > TYPE_PRECISION (type)) 7392 num = TYPE_PRECISION (type); 7393 7394 return build_int_cst_type (type, num); 7395} 7396 7397 7398#define WALK_SUBTREE(NODE) \ 7399 do \ 7400 { \ 7401 result = walk_tree (&(NODE), func, data, pset); \ 7402 if (result) \ 7403 return result; \ 7404 } \ 7405 while (0) 7406 7407/* This is a subroutine of walk_tree that walks field of TYPE that are to 7408 be walked whenever a type is seen in the tree. Rest of operands and return 7409 value are as for walk_tree. */ 7410 7411static tree 7412walk_type_fields (tree type, walk_tree_fn func, void *data, 7413 struct pointer_set_t *pset) 7414{ 7415 tree result = NULL_TREE; 7416 7417 switch (TREE_CODE (type)) 7418 { 7419 case POINTER_TYPE: 7420 case REFERENCE_TYPE: 7421 /* We have to worry about mutually recursive pointers. These can't 7422 be written in C. They can in Ada. It's pathological, but 7423 there's an ACATS test (c38102a) that checks it. Deal with this 7424 by checking if we're pointing to another pointer, that one 7425 points to another pointer, that one does too, and we have no htab. 7426 If so, get a hash table. We check three levels deep to avoid 7427 the cost of the hash table if we don't need one. */ 7428 if (POINTER_TYPE_P (TREE_TYPE (type)) 7429 && POINTER_TYPE_P (TREE_TYPE (TREE_TYPE (type))) 7430 && POINTER_TYPE_P (TREE_TYPE (TREE_TYPE (TREE_TYPE (type)))) 7431 && !pset) 7432 { 7433 result = walk_tree_without_duplicates (&TREE_TYPE (type), 7434 func, data); 7435 if (result) 7436 return result; 7437 7438 break; 7439 } 7440 7441 /* ... fall through ... */ 7442 7443 case COMPLEX_TYPE: 7444 WALK_SUBTREE (TREE_TYPE (type)); 7445 break; 7446 7447 case METHOD_TYPE: 7448 WALK_SUBTREE (TYPE_METHOD_BASETYPE (type)); 7449 7450 /* Fall through. */ 7451 7452 case FUNCTION_TYPE: 7453 WALK_SUBTREE (TREE_TYPE (type)); 7454 { 7455 tree arg; 7456 7457 /* We never want to walk into default arguments. */ 7458 for (arg = TYPE_ARG_TYPES (type); arg; arg = TREE_CHAIN (arg)) 7459 WALK_SUBTREE (TREE_VALUE (arg)); 7460 } 7461 break; 7462 7463 case ARRAY_TYPE: 7464 /* Don't follow this nodes's type if a pointer for fear that 7465 we'll have infinite recursion. If we have a PSET, then we 7466 need not fear. */ 7467 if (pset 7468 || (!POINTER_TYPE_P (TREE_TYPE (type)) 7469 && TREE_CODE (TREE_TYPE (type)) != OFFSET_TYPE)) 7470 WALK_SUBTREE (TREE_TYPE (type)); 7471 WALK_SUBTREE (TYPE_DOMAIN (type)); 7472 break; 7473 7474 case BOOLEAN_TYPE: 7475 case ENUMERAL_TYPE: 7476 case INTEGER_TYPE: 7477 case REAL_TYPE: 7478 WALK_SUBTREE (TYPE_MIN_VALUE (type)); 7479 WALK_SUBTREE (TYPE_MAX_VALUE (type)); 7480 break; 7481 7482 case OFFSET_TYPE: 7483 WALK_SUBTREE (TREE_TYPE (type)); 7484 WALK_SUBTREE (TYPE_OFFSET_BASETYPE (type)); 7485 break; 7486 7487 default: 7488 break; 7489 } 7490 7491 return NULL_TREE; 7492} 7493 7494/* Apply FUNC to all the sub-trees of TP in a pre-order traversal. FUNC is 7495 called with the DATA and the address of each sub-tree. If FUNC returns a 7496 non-NULL value, the traversal is stopped, and the value returned by FUNC 7497 is returned. If PSET is non-NULL it is used to record the nodes visited, 7498 and to avoid visiting a node more than once. */ 7499 7500tree 7501walk_tree (tree *tp, walk_tree_fn func, void *data, struct pointer_set_t *pset) 7502{ 7503 enum tree_code code; 7504 int walk_subtrees; 7505 tree result; 7506 7507#define WALK_SUBTREE_TAIL(NODE) \ 7508 do \ 7509 { \ 7510 tp = & (NODE); \ 7511 goto tail_recurse; \ 7512 } \ 7513 while (0) 7514 7515 tail_recurse: 7516 /* Skip empty subtrees. */ 7517 if (!*tp) 7518 return NULL_TREE; 7519 7520 /* Don't walk the same tree twice, if the user has requested 7521 that we avoid doing so. */ 7522 if (pset && pointer_set_insert (pset, *tp)) 7523 return NULL_TREE; 7524 7525 /* Call the function. */ 7526 walk_subtrees = 1; 7527 result = (*func) (tp, &walk_subtrees, data); 7528 7529 /* If we found something, return it. */ 7530 if (result) 7531 return result; 7532 7533 code = TREE_CODE (*tp); 7534 7535 /* Even if we didn't, FUNC may have decided that there was nothing 7536 interesting below this point in the tree. */ 7537 if (!walk_subtrees) 7538 { 7539 /* But we still need to check our siblings. */ 7540 if (code == TREE_LIST) 7541 WALK_SUBTREE_TAIL (TREE_CHAIN (*tp)); 7542 else if (code == OMP_CLAUSE) 7543 WALK_SUBTREE_TAIL (OMP_CLAUSE_CHAIN (*tp)); 7544 else 7545 return NULL_TREE; 7546 } 7547 7548 result = lang_hooks.tree_inlining.walk_subtrees (tp, &walk_subtrees, func, 7549 data, pset); 7550 if (result || ! walk_subtrees) 7551 return result; 7552 7553 switch (code) 7554 { 7555 case ERROR_MARK: 7556 case IDENTIFIER_NODE: 7557 case INTEGER_CST: 7558 case REAL_CST: 7559 case VECTOR_CST: 7560 case STRING_CST: 7561 case BLOCK: 7562 case PLACEHOLDER_EXPR: 7563 case SSA_NAME: 7564 case FIELD_DECL: 7565 case RESULT_DECL: 7566 /* None of these have subtrees other than those already walked 7567 above. */ 7568 break; 7569 7570 case TREE_LIST: 7571 WALK_SUBTREE (TREE_VALUE (*tp)); 7572 WALK_SUBTREE_TAIL (TREE_CHAIN (*tp)); 7573 break; 7574 7575 case TREE_VEC: 7576 { 7577 int len = TREE_VEC_LENGTH (*tp); 7578 7579 if (len == 0) 7580 break; 7581 7582 /* Walk all elements but the first. */ 7583 while (--len) 7584 WALK_SUBTREE (TREE_VEC_ELT (*tp, len)); 7585 7586 /* Now walk the first one as a tail call. */ 7587 WALK_SUBTREE_TAIL (TREE_VEC_ELT (*tp, 0)); 7588 } 7589 7590 case COMPLEX_CST: 7591 WALK_SUBTREE (TREE_REALPART (*tp)); 7592 WALK_SUBTREE_TAIL (TREE_IMAGPART (*tp)); 7593 7594 case CONSTRUCTOR: 7595 { 7596 unsigned HOST_WIDE_INT idx; 7597 constructor_elt *ce; 7598 7599 for (idx = 0; 7600 VEC_iterate(constructor_elt, CONSTRUCTOR_ELTS (*tp), idx, ce); 7601 idx++) 7602 WALK_SUBTREE (ce->value); 7603 } 7604 break; 7605 7606 case SAVE_EXPR: 7607 WALK_SUBTREE_TAIL (TREE_OPERAND (*tp, 0)); 7608 7609 case BIND_EXPR: 7610 { 7611 tree decl; 7612 for (decl = BIND_EXPR_VARS (*tp); decl; decl = TREE_CHAIN (decl)) 7613 { 7614 /* Walk the DECL_INITIAL and DECL_SIZE. We don't want to walk 7615 into declarations that are just mentioned, rather than 7616 declared; they don't really belong to this part of the tree. 7617 And, we can see cycles: the initializer for a declaration 7618 can refer to the declaration itself. */ 7619 WALK_SUBTREE (DECL_INITIAL (decl)); 7620 WALK_SUBTREE (DECL_SIZE (decl)); 7621 WALK_SUBTREE (DECL_SIZE_UNIT (decl)); 7622 } 7623 WALK_SUBTREE_TAIL (BIND_EXPR_BODY (*tp)); 7624 } 7625 7626 case STATEMENT_LIST: 7627 { 7628 tree_stmt_iterator i; 7629 for (i = tsi_start (*tp); !tsi_end_p (i); tsi_next (&i)) 7630 WALK_SUBTREE (*tsi_stmt_ptr (i)); 7631 } 7632 break; 7633 7634 case OMP_CLAUSE: 7635 switch (OMP_CLAUSE_CODE (*tp)) 7636 { 7637 case OMP_CLAUSE_PRIVATE: 7638 case OMP_CLAUSE_SHARED: 7639 case OMP_CLAUSE_FIRSTPRIVATE: 7640 case OMP_CLAUSE_LASTPRIVATE: 7641 case OMP_CLAUSE_COPYIN: 7642 case OMP_CLAUSE_COPYPRIVATE: 7643 case OMP_CLAUSE_IF: 7644 case OMP_CLAUSE_NUM_THREADS: 7645 case OMP_CLAUSE_SCHEDULE: 7646 WALK_SUBTREE (OMP_CLAUSE_OPERAND (*tp, 0)); 7647 /* FALLTHRU */ 7648 7649 case OMP_CLAUSE_NOWAIT: 7650 case OMP_CLAUSE_ORDERED: 7651 case OMP_CLAUSE_DEFAULT: 7652 WALK_SUBTREE_TAIL (OMP_CLAUSE_CHAIN (*tp)); 7653 7654 case OMP_CLAUSE_REDUCTION: 7655 { 7656 int i; 7657 for (i = 0; i < 4; i++) 7658 WALK_SUBTREE (OMP_CLAUSE_OPERAND (*tp, i)); 7659 WALK_SUBTREE_TAIL (OMP_CLAUSE_CHAIN (*tp)); 7660 } 7661 7662 default: 7663 gcc_unreachable (); 7664 } 7665 break; 7666 7667 case TARGET_EXPR: 7668 { 7669 int i, len; 7670 7671 /* TARGET_EXPRs are peculiar: operands 1 and 3 can be the same. 7672 But, we only want to walk once. */ 7673 len = (TREE_OPERAND (*tp, 3) == TREE_OPERAND (*tp, 1)) ? 2 : 3; 7674 for (i = 0; i < len; ++i) 7675 WALK_SUBTREE (TREE_OPERAND (*tp, i)); 7676 WALK_SUBTREE_TAIL (TREE_OPERAND (*tp, len)); 7677 } 7678 7679 case DECL_EXPR: 7680 /* Walk into various fields of the type that it's defining. We only 7681 want to walk into these fields of a type in this case. Note that 7682 decls get walked as part of the processing of a BIND_EXPR. 7683 7684 ??? Precisely which fields of types that we are supposed to walk in 7685 this case vs. the normal case aren't well defined. */ 7686 if (TREE_CODE (DECL_EXPR_DECL (*tp)) == TYPE_DECL 7687 && TREE_CODE (TREE_TYPE (DECL_EXPR_DECL (*tp))) != ERROR_MARK) 7688 { 7689 tree *type_p = &TREE_TYPE (DECL_EXPR_DECL (*tp)); 7690 7691 /* Call the function for the type. See if it returns anything or 7692 doesn't want us to continue. If we are to continue, walk both 7693 the normal fields and those for the declaration case. */ 7694 result = (*func) (type_p, &walk_subtrees, data); 7695 if (result || !walk_subtrees) 7696 return NULL_TREE; 7697 7698 result = walk_type_fields (*type_p, func, data, pset); 7699 if (result) 7700 return result; 7701 7702 /* If this is a record type, also walk the fields. */ 7703 if (TREE_CODE (*type_p) == RECORD_TYPE 7704 || TREE_CODE (*type_p) == UNION_TYPE 7705 || TREE_CODE (*type_p) == QUAL_UNION_TYPE) 7706 { 7707 tree field; 7708 7709 for (field = TYPE_FIELDS (*type_p); field; 7710 field = TREE_CHAIN (field)) 7711 { 7712 /* We'd like to look at the type of the field, but we can 7713 easily get infinite recursion. So assume it's pointed 7714 to elsewhere in the tree. Also, ignore things that 7715 aren't fields. */ 7716 if (TREE_CODE (field) != FIELD_DECL) 7717 continue; 7718 7719 WALK_SUBTREE (DECL_FIELD_OFFSET (field)); 7720 WALK_SUBTREE (DECL_SIZE (field)); 7721 WALK_SUBTREE (DECL_SIZE_UNIT (field)); 7722 if (TREE_CODE (*type_p) == QUAL_UNION_TYPE) 7723 WALK_SUBTREE (DECL_QUALIFIER (field)); 7724 } 7725 } 7726 7727 WALK_SUBTREE (TYPE_SIZE (*type_p)); 7728 WALK_SUBTREE_TAIL (TYPE_SIZE_UNIT (*type_p)); 7729 } 7730 /* FALLTHRU */ 7731 7732 default: 7733 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code))) 7734 { 7735 int i, len; 7736 7737 /* Walk over all the sub-trees of this operand. */ 7738 len = TREE_CODE_LENGTH (code); 7739 7740 /* Go through the subtrees. We need to do this in forward order so 7741 that the scope of a FOR_EXPR is handled properly. */ 7742 if (len) 7743 { 7744 for (i = 0; i < len - 1; ++i) 7745 WALK_SUBTREE (TREE_OPERAND (*tp, i)); 7746 WALK_SUBTREE_TAIL (TREE_OPERAND (*tp, len - 1)); 7747 } 7748 } 7749 7750 /* If this is a type, walk the needed fields in the type. */ 7751 else if (TYPE_P (*tp)) 7752 return walk_type_fields (*tp, func, data, pset); 7753 break; 7754 } 7755 7756 /* We didn't find what we were looking for. */ 7757 return NULL_TREE; 7758 7759#undef WALK_SUBTREE_TAIL 7760} 7761#undef WALK_SUBTREE 7762 7763/* Like walk_tree, but does not walk duplicate nodes more than once. */ 7764 7765tree 7766walk_tree_without_duplicates (tree *tp, walk_tree_fn func, void *data) 7767{ 7768 tree result; 7769 struct pointer_set_t *pset; 7770 7771 pset = pointer_set_create (); 7772 result = walk_tree (tp, func, data, pset); 7773 pointer_set_destroy (pset); 7774 return result; 7775} 7776 7777 7778/* Return true if STMT is an empty statement or contains nothing but 7779 empty statements. */ 7780 7781bool 7782empty_body_p (tree stmt) 7783{ 7784 tree_stmt_iterator i; 7785 tree body; 7786 7787 if (IS_EMPTY_STMT (stmt)) 7788 return true; 7789 else if (TREE_CODE (stmt) == BIND_EXPR) 7790 body = BIND_EXPR_BODY (stmt); 7791 else if (TREE_CODE (stmt) == STATEMENT_LIST) 7792 body = stmt; 7793 else 7794 return false; 7795 7796 for (i = tsi_start (body); !tsi_end_p (i); tsi_next (&i)) 7797 if (!empty_body_p (tsi_stmt (i))) 7798 return false; 7799 7800 return true; 7801} 7802 7803 7804#include "gt-tree.h" 7805