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