1/* Type based alias analysis. 2 Copyright (C) 2004, 2005 Free Software Foundation, Inc. 3 Contributed by Kenneth Zadeck <zadeck@naturalbridge.com> 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 pass determines which types in the program contain only 23 instances that are completely encapsulated by the compilation unit. 24 Those types that are encapsulated must also pass the further 25 requirement that there be no bad operations on any instances of 26 those types. 27 28 A great deal of freedom in compilation is allowed for the instances 29 of those types that pass these conditions. 30*/ 31 32/* The code in this module is called by the ipa pass manager. It 33 should be one of the later passes since its information is used by 34 the rest of the compilation. */ 35 36#include "config.h" 37#include "system.h" 38#include "coretypes.h" 39#include "tm.h" 40#include "tree.h" 41#include "tree-flow.h" 42#include "tree-inline.h" 43#include "tree-pass.h" 44#include "langhooks.h" 45#include "pointer-set.h" 46#include "ggc.h" 47#include "ipa-utils.h" 48#include "ipa-type-escape.h" 49#include "c-common.h" 50#include "tree-gimple.h" 51#include "cgraph.h" 52#include "output.h" 53#include "flags.h" 54#include "timevar.h" 55#include "diagnostic.h" 56#include "langhooks.h" 57 58/* Some of the aliasing is called very early, before this phase is 59 called. To assure that this is not a problem, we keep track of if 60 this phase has been run. */ 61static bool initialized = false; 62 63/* This bitmap contains the set of local vars that are the lhs of 64 calls to mallocs. These variables, when seen on the rhs as part of 65 a cast, the cast are not marked as doing bad things to the type 66 even though they are generally of the form 67 "foo = (type_of_foo)void_temp". */ 68static bitmap results_of_malloc; 69 70/* Scratch bitmap for avoiding work. */ 71static bitmap been_there_done_that; 72static bitmap bitmap_tmp; 73 74/* There are two levels of escape that types can undergo. 75 76 EXPOSED_PARAMETER - some instance of the variable is 77 passed by value into an externally visible function or some 78 instance of the variable is passed out of an externally visible 79 function as a return value. In this case any of the fields of the 80 variable that are pointer types end up having their types marked as 81 FULL_ESCAPE. 82 83 FULL_ESCAPE - when bad things happen to good types. One of the 84 following things happens to the type: (a) either an instance of the 85 variable has its address passed to an externally visible function, 86 (b) the address is taken and some bad cast happens to the address 87 or (c) explicit arithmetic is done to the address. 88*/ 89 90enum escape_t 91{ 92 EXPOSED_PARAMETER, 93 FULL_ESCAPE 94}; 95 96/* The following two bit vectors global_types_* correspond to 97 previous cases above. During the analysis phase, a bit is set in 98 one of these vectors if an operation of the offending class is 99 discovered to happen on the associated type. */ 100 101static bitmap global_types_exposed_parameter; 102static bitmap global_types_full_escape; 103 104/* All of the types seen in this compilation unit. */ 105static bitmap global_types_seen; 106/* Reverse map to take a canon uid and map it to a canon type. Uid's 107 are never manipulated unless they are associated with a canon 108 type. */ 109static splay_tree uid_to_canon_type; 110 111/* Internal structure of type mapping code. This maps a canon type 112 name to its canon type. */ 113static splay_tree all_canon_types; 114 115/* Map from type clones to the single canon type. */ 116static splay_tree type_to_canon_type; 117 118/* A splay tree of bitmaps. An element X in the splay tree has a bit 119 set in its bitmap at TYPE_UID (TYPE_MAIN_VARIANT (Y)) if there was 120 an operation in the program of the form "&X.Y". */ 121static splay_tree uid_to_addressof_down_map; 122 123/* A splay tree of bitmaps. An element Y in the splay tree has a bit 124 set in its bitmap at TYPE_UID (TYPE_MAIN_VARIANT (X)) if there was 125 an operation in the program of the form "&X.Y". */ 126static splay_tree uid_to_addressof_up_map; 127 128/* Tree to hold the subtype maps used to mark subtypes of escaped 129 types. */ 130static splay_tree uid_to_subtype_map; 131 132/* Records tree nodes seen in cgraph_create_edges. Simply using 133 walk_tree_without_duplicates doesn't guarantee each node is visited 134 once because it gets a new htab upon each recursive call from 135 scan_for_refs. */ 136static struct pointer_set_t *visited_nodes; 137 138static bitmap_obstack ipa_obstack; 139 140/* Get the name of TYPE or return the string "<UNNAMED>". */ 141static char* 142get_name_of_type (tree type) 143{ 144 tree name = TYPE_NAME (type); 145 146 if (!name) 147 /* Unnamed type, do what you like here. */ 148 return (char*)"<UNNAMED>"; 149 150 /* It will be a TYPE_DECL in the case of a typedef, otherwise, an 151 identifier_node */ 152 if (TREE_CODE (name) == TYPE_DECL) 153 { 154 /* Each DECL has a DECL_NAME field which contains an 155 IDENTIFIER_NODE. (Some decls, most often labels, may have 156 zero as the DECL_NAME). */ 157 if (DECL_NAME (name)) 158 return (char*)IDENTIFIER_POINTER (DECL_NAME (name)); 159 else 160 /* Unnamed type, do what you like here. */ 161 return (char*)"<UNNAMED>"; 162 } 163 else if (TREE_CODE (name) == IDENTIFIER_NODE) 164 return (char*)IDENTIFIER_POINTER (name); 165 else 166 return (char*)"<UNNAMED>"; 167} 168 169struct type_brand_s 170{ 171 char* name; 172 int seq; 173}; 174 175/* Splay tree comparison function on type_brand_s structures. */ 176 177static int 178compare_type_brand (splay_tree_key sk1, splay_tree_key sk2) 179{ 180 struct type_brand_s * k1 = (struct type_brand_s *) sk1; 181 struct type_brand_s * k2 = (struct type_brand_s *) sk2; 182 183 int value = strcmp(k1->name, k2->name); 184 if (value == 0) 185 return k2->seq - k1->seq; 186 else 187 return value; 188} 189 190/* All of the "unique_type" code is a hack to get around the sleazy 191 implementation used to compile more than file. Currently gcc does 192 not get rid of multiple instances of the same type that have been 193 collected from different compilation units. */ 194/* This is a trivial algorithm for removing duplicate types. This 195 would not work for any language that used structural equivalence as 196 the basis of its type system. */ 197/* Return either TYPE if this is first time TYPE has been seen an 198 compatible TYPE that has already been processed. */ 199 200static tree 201discover_unique_type (tree type) 202{ 203 struct type_brand_s * brand = xmalloc (sizeof (struct type_brand_s)); 204 int i = 0; 205 splay_tree_node result; 206 207 brand->name = get_name_of_type (type); 208 209 while (1) 210 { 211 brand->seq = i++; 212 result = splay_tree_lookup (all_canon_types, (splay_tree_key) brand); 213 214 if (result) 215 { 216 /* Create an alias since this is just the same as 217 other_type. */ 218 tree other_type = (tree) result->value; 219 if (lang_hooks.types_compatible_p (type, other_type) == 1) 220 { 221 free (brand); 222 /* Insert this new type as an alias for other_type. */ 223 splay_tree_insert (type_to_canon_type, 224 (splay_tree_key) type, 225 (splay_tree_value) other_type); 226 return other_type; 227 } 228 /* Not compatible, look for next instance with same name. */ 229 } 230 else 231 { 232 /* No more instances, create new one since this is the first 233 time we saw this type. */ 234 brand->seq = i++; 235 /* Insert the new brand. */ 236 splay_tree_insert (all_canon_types, 237 (splay_tree_key) brand, 238 (splay_tree_value) type); 239 240 /* Insert this new type as an alias for itself. */ 241 splay_tree_insert (type_to_canon_type, 242 (splay_tree_key) type, 243 (splay_tree_value) type); 244 245 /* Insert the uid for reverse lookup; */ 246 splay_tree_insert (uid_to_canon_type, 247 (splay_tree_key) TYPE_UID (type), 248 (splay_tree_value) type); 249 250 bitmap_set_bit (global_types_seen, TYPE_UID (type)); 251 return type; 252 } 253 } 254} 255 256/* Return true if TYPE is one of the type classes that we are willing 257 to analyze. This skips the goofy types like arrays of pointers to 258 methods. */ 259static bool 260type_to_consider (tree type) 261{ 262 /* Strip the *'s off. */ 263 type = TYPE_MAIN_VARIANT (type); 264 while (POINTER_TYPE_P (type) || TREE_CODE (type) == ARRAY_TYPE) 265 type = TYPE_MAIN_VARIANT (TREE_TYPE (type)); 266 267 switch (TREE_CODE (type)) 268 { 269 case BOOLEAN_TYPE: 270 case CHAR_TYPE: 271 case COMPLEX_TYPE: 272 case ENUMERAL_TYPE: 273 case INTEGER_TYPE: 274 case QUAL_UNION_TYPE: 275 case REAL_TYPE: 276 case RECORD_TYPE: 277 case UNION_TYPE: 278 case VECTOR_TYPE: 279 case VOID_TYPE: 280 return true; 281 282 default: 283 return false; 284 } 285} 286 287/* Get the canon type of TYPE. If SEE_THRU_PTRS is true, remove all 288 the POINTER_TOs and if SEE_THRU_ARRAYS is true, remove all of the 289 ARRAY_OFs and POINTER_TOs. */ 290 291static tree 292get_canon_type (tree type, bool see_thru_ptrs, bool see_thru_arrays) 293{ 294 splay_tree_node result; 295 /* Strip the *'s off. */ 296 if (!type || !type_to_consider (type)) 297 return NULL; 298 299 type = TYPE_MAIN_VARIANT (type); 300 if (see_thru_arrays) 301 while (POINTER_TYPE_P (type) || TREE_CODE (type) == ARRAY_TYPE) 302 type = TYPE_MAIN_VARIANT (TREE_TYPE (type)); 303 304 else if (see_thru_ptrs) 305 while (POINTER_TYPE_P (type)) 306 type = TYPE_MAIN_VARIANT (TREE_TYPE (type)); 307 308 result = splay_tree_lookup(type_to_canon_type, (splay_tree_key) type); 309 310 if (result == NULL) 311 return discover_unique_type (type); 312 else return (tree) result->value; 313} 314 315/* Same as GET_CANON_TYPE, except return the TYPE_ID rather than the 316 TYPE. */ 317 318static int 319get_canon_type_uid (tree type, bool see_thru_ptrs, bool see_thru_arrays) 320{ 321 type = get_canon_type (type, see_thru_ptrs, see_thru_arrays); 322 if (type) 323 return TYPE_UID(type); 324 else return 0; 325} 326 327/* Return 0 if TYPE is a record or union type. Return a positive 328 number if TYPE is a pointer to a record or union. The number is 329 the number of pointer types stripped to get to the record or union 330 type. Return -1 if TYPE is none of the above. */ 331 332int 333ipa_type_escape_star_count_of_interesting_type (tree type) 334{ 335 int count = 0; 336 /* Strip the *'s off. */ 337 if (!type) 338 return -1; 339 type = TYPE_MAIN_VARIANT (type); 340 while (POINTER_TYPE_P (type)) 341 { 342 type = TYPE_MAIN_VARIANT (TREE_TYPE (type)); 343 count++; 344 } 345 346 /* We are interested in records, and unions only. */ 347 if (TREE_CODE (type) == RECORD_TYPE 348 || TREE_CODE (type) == QUAL_UNION_TYPE 349 || TREE_CODE (type) == UNION_TYPE) 350 return count; 351 else 352 return -1; 353} 354 355 356/* Return 0 if TYPE is a record or union type. Return a positive 357 number if TYPE is a pointer to a record or union. The number is 358 the number of pointer types stripped to get to the record or union 359 type. Return -1 if TYPE is none of the above. */ 360 361int 362ipa_type_escape_star_count_of_interesting_or_array_type (tree type) 363{ 364 int count = 0; 365 /* Strip the *'s off. */ 366 if (!type) 367 return -1; 368 type = TYPE_MAIN_VARIANT (type); 369 while (POINTER_TYPE_P (type) || TREE_CODE (type) == ARRAY_TYPE) 370 { 371 type = TYPE_MAIN_VARIANT (TREE_TYPE (type)); 372 count++; 373 } 374 375 /* We are interested in records, and unions only. */ 376 if (TREE_CODE (type) == RECORD_TYPE 377 || TREE_CODE (type) == QUAL_UNION_TYPE 378 || TREE_CODE (type) == UNION_TYPE) 379 return count; 380 else 381 return -1; 382} 383 384 385/* Return true if the record, or union TYPE passed in escapes this 386 compilation unit. Note that all of the pointer-to's are removed 387 before testing since these may not be correct. */ 388 389bool 390ipa_type_escape_type_contained_p (tree type) 391{ 392 if (!initialized) 393 return false; 394 return !bitmap_bit_p (global_types_full_escape, 395 get_canon_type_uid (type, true, false)); 396} 397 398/* Return true a modification to a field of type FIELD_TYPE cannot 399 clobber a record of RECORD_TYPE. */ 400 401bool 402ipa_type_escape_field_does_not_clobber_p (tree record_type, tree field_type) 403{ 404 splay_tree_node result; 405 int uid; 406 407 if (!initialized) 408 return false; 409 410 /* Strip off all of the pointer tos on the record type. Strip the 411 same number of pointer tos from the field type. If the field 412 type has fewer, it could not have been aliased. */ 413 record_type = TYPE_MAIN_VARIANT (record_type); 414 field_type = TYPE_MAIN_VARIANT (field_type); 415 while (POINTER_TYPE_P (record_type)) 416 { 417 record_type = TYPE_MAIN_VARIANT (TREE_TYPE (record_type)); 418 if (POINTER_TYPE_P (field_type)) 419 field_type = TYPE_MAIN_VARIANT (TREE_TYPE (field_type)); 420 else 421 /* However, if field_type is a union, this quick test is not 422 correct since one of the variants of the union may be a 423 pointer to type and we cannot see across that here. So we 424 just strip the remaining pointer tos off the record type 425 and fall thru to the more precise code. */ 426 if (TREE_CODE (field_type) == QUAL_UNION_TYPE 427 || TREE_CODE (field_type) == UNION_TYPE) 428 { 429 while (POINTER_TYPE_P (record_type)) 430 record_type = TYPE_MAIN_VARIANT (TREE_TYPE (record_type)); 431 break; 432 } 433 else 434 return true; 435 } 436 437 record_type = get_canon_type (record_type, true, true); 438 /* The record type must be contained. The field type may 439 escape. */ 440 if (!ipa_type_escape_type_contained_p (record_type)) 441 return false; 442 443 uid = TYPE_UID (record_type); 444 result = splay_tree_lookup (uid_to_addressof_down_map, (splay_tree_key) uid); 445 446 if (result) 447 { 448 bitmap field_type_map = (bitmap) result->value; 449 uid = get_canon_type_uid (field_type, true, true); 450 /* If the bit is there, the address was taken. If not, it 451 wasn't. */ 452 return !bitmap_bit_p (field_type_map, uid); 453 } 454 else 455 /* No bitmap means no addresses were taken. */ 456 return true; 457} 458 459 460/* Add TYPE to the suspect type set. Return true if the bit needed to 461 be marked. */ 462 463static tree 464mark_type (tree type, enum escape_t escape_status) 465{ 466 bitmap map = NULL; 467 int uid; 468 469 type = get_canon_type (type, true, true); 470 if (!type) 471 return NULL; 472 473 switch (escape_status) 474 { 475 case EXPOSED_PARAMETER: 476 map = global_types_exposed_parameter; 477 break; 478 case FULL_ESCAPE: 479 map = global_types_full_escape; 480 break; 481 } 482 483 uid = TYPE_UID (type); 484 if (bitmap_bit_p (map, uid)) 485 return type; 486 else 487 { 488 bitmap_set_bit (map, uid); 489 if (escape_status == FULL_ESCAPE) 490 { 491 /* Efficiency hack. When things are bad, do not mess around 492 with this type anymore. */ 493 bitmap_set_bit (global_types_exposed_parameter, uid); 494 } 495 } 496 return type; 497} 498 499/* Add interesting TYPE to the suspect type set. If the set is 500 EXPOSED_PARAMETER and the TYPE is a pointer type, the set is 501 changed to FULL_ESCAPE. */ 502 503static void 504mark_interesting_type (tree type, enum escape_t escape_status) 505{ 506 if (!type) return; 507 if (ipa_type_escape_star_count_of_interesting_type (type) >= 0) 508 { 509 if ((escape_status == EXPOSED_PARAMETER) 510 && POINTER_TYPE_P (type)) 511 /* EXPOSED_PARAMETERs are only structs or unions are passed by 512 value. Anything passed by reference to an external 513 function fully exposes the type. */ 514 mark_type (type, FULL_ESCAPE); 515 else 516 mark_type (type, escape_status); 517 } 518} 519 520/* Return true if PARENT is supertype of CHILD. Both types must be 521 known to be structures or unions. */ 522 523static bool 524parent_type_p (tree parent, tree child) 525{ 526 int i; 527 tree binfo, base_binfo; 528 if (TYPE_BINFO (parent)) 529 for (binfo = TYPE_BINFO (parent), i = 0; 530 BINFO_BASE_ITERATE (binfo, i, base_binfo); i++) 531 { 532 tree binfotype = BINFO_TYPE (base_binfo); 533 if (binfotype == child) 534 return true; 535 else if (parent_type_p (binfotype, child)) 536 return true; 537 } 538 if (TREE_CODE (parent) == UNION_TYPE 539 || TREE_CODE (parent) == QUAL_UNION_TYPE) 540 { 541 tree field; 542 /* Search all of the variants in the union to see if one of them 543 is the child. */ 544 for (field = TYPE_FIELDS (parent); 545 field; 546 field = TREE_CHAIN (field)) 547 { 548 tree field_type; 549 if (TREE_CODE (field) != FIELD_DECL) 550 continue; 551 552 field_type = TREE_TYPE (field); 553 if (field_type == child) 554 return true; 555 } 556 557 /* If we did not find it, recursively ask the variants if one of 558 their children is the child type. */ 559 for (field = TYPE_FIELDS (parent); 560 field; 561 field = TREE_CHAIN (field)) 562 { 563 tree field_type; 564 if (TREE_CODE (field) != FIELD_DECL) 565 continue; 566 567 field_type = TREE_TYPE (field); 568 if (TREE_CODE (field_type) == RECORD_TYPE 569 || TREE_CODE (field_type) == QUAL_UNION_TYPE 570 || TREE_CODE (field_type) == UNION_TYPE) 571 if (parent_type_p (field_type, child)) 572 return true; 573 } 574 } 575 576 if (TREE_CODE (parent) == RECORD_TYPE) 577 { 578 tree field; 579 for (field = TYPE_FIELDS (parent); 580 field; 581 field = TREE_CHAIN (field)) 582 { 583 tree field_type; 584 if (TREE_CODE (field) != FIELD_DECL) 585 continue; 586 587 field_type = TREE_TYPE (field); 588 if (field_type == child) 589 return true; 590 /* You can only cast to the first field so if it does not 591 match, quit. */ 592 if (TREE_CODE (field_type) == RECORD_TYPE 593 || TREE_CODE (field_type) == QUAL_UNION_TYPE 594 || TREE_CODE (field_type) == UNION_TYPE) 595 { 596 if (parent_type_p (field_type, child)) 597 return true; 598 else 599 break; 600 } 601 } 602 } 603 return false; 604} 605 606/* Return the number of pointer tos for TYPE and return TYPE with all 607 of these stripped off. */ 608 609static int 610count_stars (tree* type_ptr) 611{ 612 tree type = *type_ptr; 613 int i = 0; 614 type = TYPE_MAIN_VARIANT (type); 615 while (POINTER_TYPE_P (type)) 616 { 617 type = TYPE_MAIN_VARIANT (TREE_TYPE (type)); 618 i++; 619 } 620 621 *type_ptr = type; 622 return i; 623} 624 625enum cast_type { 626 CT_UP, 627 CT_DOWN, 628 CT_SIDEWAYS, 629 CT_USELESS 630}; 631 632/* Check the cast FROM_TYPE to TO_TYPE. This function requires that 633 the two types have already passed the 634 ipa_type_escape_star_count_of_interesting_type test. */ 635 636static enum cast_type 637check_cast_type (tree to_type, tree from_type) 638{ 639 int to_stars = count_stars (&to_type); 640 int from_stars = count_stars (&from_type); 641 if (to_stars != from_stars) 642 return CT_SIDEWAYS; 643 644 if (to_type == from_type) 645 return CT_USELESS; 646 647 if (parent_type_p (to_type, from_type)) return CT_UP; 648 if (parent_type_p (from_type, to_type)) return CT_DOWN; 649 return CT_SIDEWAYS; 650} 651 652/* Check a cast FROM this variable, TO_TYPE. Mark the escaping types 653 if appropriate. */ 654static void 655check_cast (tree to_type, tree from) 656{ 657 tree from_type = get_canon_type (TREE_TYPE (from), false, false); 658 bool to_interesting_type, from_interesting_type; 659 660 to_type = get_canon_type (to_type, false, false); 661 if (!from_type || !to_type || from_type == to_type) 662 return; 663 664 to_interesting_type = 665 ipa_type_escape_star_count_of_interesting_type (to_type) >= 0; 666 from_interesting_type = 667 ipa_type_escape_star_count_of_interesting_type (from_type) >= 0; 668 669 if (to_interesting_type) 670 if (from_interesting_type) 671 { 672 /* Both types are interesting. This can be one of four types 673 of cast: useless, up, down, or sideways. We do not care 674 about up or useless. Sideways casts are always bad and 675 both sides get marked as escaping. Downcasts are not 676 interesting here because if type is marked as escaping, all 677 of its subtypes escape. */ 678 switch (check_cast_type (to_type, from_type)) 679 { 680 case CT_UP: 681 case CT_USELESS: 682 case CT_DOWN: 683 break; 684 685 case CT_SIDEWAYS: 686 mark_type (to_type, FULL_ESCAPE); 687 mark_type (from_type, FULL_ESCAPE); 688 break; 689 } 690 } 691 else 692 { 693 /* If this is a cast from the local that is a result from a 694 call to malloc, do not mark the cast as bad. */ 695 if (DECL_P (from) && !bitmap_bit_p (results_of_malloc, DECL_UID (from))) 696 mark_type (to_type, FULL_ESCAPE); 697 } 698 else if (from_interesting_type) 699 mark_type (from_type, FULL_ESCAPE); 700} 701 702/* Register the parameter and return types of function FN. The type 703 ESCAPES if the function is visible outside of the compilation 704 unit. */ 705static void 706check_function_parameter_and_return_types (tree fn, bool escapes) 707{ 708 tree arg; 709 710 if (TYPE_ARG_TYPES (TREE_TYPE (fn))) 711 { 712 for (arg = TYPE_ARG_TYPES (TREE_TYPE (fn)); 713 arg && TREE_VALUE (arg) != void_type_node; 714 arg = TREE_CHAIN (arg)) 715 { 716 tree type = get_canon_type (TREE_VALUE (arg), false, false); 717 if (escapes) 718 mark_interesting_type (type, EXPOSED_PARAMETER); 719 } 720 } 721 else 722 { 723 /* FIXME - According to Geoff Keating, we should never have to 724 do this; the front ends should always process the arg list 725 from the TYPE_ARG_LIST. However, Geoff is wrong, this code 726 does seem to be live. */ 727 728 for (arg = DECL_ARGUMENTS (fn); arg; arg = TREE_CHAIN (arg)) 729 { 730 tree type = get_canon_type (TREE_TYPE (arg), false, false); 731 if (escapes) 732 mark_interesting_type (type, EXPOSED_PARAMETER); 733 } 734 } 735 if (escapes) 736 { 737 tree type = get_canon_type (TREE_TYPE (TREE_TYPE (fn)), false, false); 738 mark_interesting_type (type, EXPOSED_PARAMETER); 739 } 740} 741 742/* Return true if the variable T is the right kind of static variable to 743 perform compilation unit scope escape analysis. */ 744 745static inline void 746has_proper_scope_for_analysis (tree t) 747{ 748 /* If the variable has the "used" attribute, treat it as if it had a 749 been touched by the devil. */ 750 tree type = get_canon_type (TREE_TYPE (t), false, false); 751 if (!type) return; 752 753 if (lookup_attribute ("used", DECL_ATTRIBUTES (t))) 754 { 755 mark_interesting_type (type, FULL_ESCAPE); 756 return; 757 } 758 759 /* Do not want to do anything with volatile except mark any 760 function that uses one to be not const or pure. */ 761 if (TREE_THIS_VOLATILE (t)) 762 return; 763 764 /* Do not care about a local automatic that is not static. */ 765 if (!TREE_STATIC (t) && !DECL_EXTERNAL (t)) 766 return; 767 768 if (DECL_EXTERNAL (t) || TREE_PUBLIC (t)) 769 { 770 /* If the front end set the variable to be READONLY and 771 constant, we can allow this variable in pure or const 772 functions but the scope is too large for our analysis to set 773 these bits ourselves. */ 774 775 if (TREE_READONLY (t) 776 && DECL_INITIAL (t) 777 && is_gimple_min_invariant (DECL_INITIAL (t))) 778 ; /* Read of a constant, do not change the function state. */ 779 else 780 { 781 /* The type escapes for all public and externs. */ 782 mark_interesting_type (type, FULL_ESCAPE); 783 } 784 } 785} 786 787/* If T is a VAR_DECL for a static that we are interested in, add the 788 uid to the bitmap. */ 789 790static void 791check_operand (tree t) 792{ 793 if (!t) return; 794 795 /* This is an assignment from a function, register the types as 796 escaping. */ 797 if (TREE_CODE (t) == FUNCTION_DECL) 798 check_function_parameter_and_return_types (t, true); 799 800 else if (TREE_CODE (t) == VAR_DECL) 801 has_proper_scope_for_analysis (t); 802} 803 804/* Examine tree T for references. */ 805 806static void 807check_tree (tree t) 808{ 809 if ((TREE_CODE (t) == EXC_PTR_EXPR) || (TREE_CODE (t) == FILTER_EXPR)) 810 return; 811 812 while (TREE_CODE (t) == REALPART_EXPR 813 || TREE_CODE (t) == IMAGPART_EXPR 814 || handled_component_p (t)) 815 { 816 if (TREE_CODE (t) == ARRAY_REF) 817 check_operand (TREE_OPERAND (t, 1)); 818 t = TREE_OPERAND (t, 0); 819 } 820 821 if (INDIRECT_REF_P (t)) 822/* || TREE_CODE (t) == MEM_REF) */ 823 check_tree (TREE_OPERAND (t, 0)); 824 825 if (SSA_VAR_P (t) || (TREE_CODE (t) == FUNCTION_DECL)) 826 check_operand (t); 827} 828 829/* Create an address_of edge FROM_TYPE.TO_TYPE. */ 830static void 831mark_interesting_addressof (tree to_type, tree from_type) 832{ 833 int from_uid; 834 int to_uid; 835 bitmap type_map; 836 splay_tree_node result; 837 838 from_type = get_canon_type (from_type, false, false); 839 to_type = get_canon_type (to_type, false, false); 840 841 if (!from_type || !to_type) 842 return; 843 844 from_uid = TYPE_UID (from_type); 845 to_uid = TYPE_UID (to_type); 846 847 gcc_assert (ipa_type_escape_star_count_of_interesting_type (from_type) == 0); 848 849 /* Process the Y into X map pointer. */ 850 result = splay_tree_lookup (uid_to_addressof_down_map, 851 (splay_tree_key) from_uid); 852 853 if (result) 854 type_map = (bitmap) result->value; 855 else 856 { 857 type_map = BITMAP_ALLOC (&ipa_obstack); 858 splay_tree_insert (uid_to_addressof_down_map, 859 from_uid, 860 (splay_tree_value)type_map); 861 } 862 bitmap_set_bit (type_map, TYPE_UID (to_type)); 863 864 /* Process the X into Y reverse map pointer. */ 865 result = 866 splay_tree_lookup (uid_to_addressof_up_map, (splay_tree_key) to_uid); 867 868 if (result) 869 type_map = (bitmap) result->value; 870 else 871 { 872 type_map = BITMAP_ALLOC (&ipa_obstack); 873 splay_tree_insert (uid_to_addressof_up_map, 874 to_uid, 875 (splay_tree_value)type_map); 876 } 877 bitmap_set_bit (type_map, TYPE_UID (to_type)); 878} 879 880/* Scan tree T to see if there are any addresses taken in within T. */ 881 882static void 883look_for_address_of (tree t) 884{ 885 if (TREE_CODE (t) == ADDR_EXPR) 886 { 887 tree x = get_base_var (t); 888 tree cref = TREE_OPERAND (t, 0); 889 890 /* If we have an expression of the form "&a.b.c.d", mark a.b, 891 b.c and c.d. as having its address taken. */ 892 tree fielddecl = NULL_TREE; 893 while (cref!= x) 894 { 895 if (TREE_CODE (cref) == COMPONENT_REF) 896 { 897 fielddecl = TREE_OPERAND (cref, 1); 898 mark_interesting_addressof (TREE_TYPE (fielddecl), 899 DECL_FIELD_CONTEXT (fielddecl)); 900 } 901 else if (TREE_CODE (cref) == ARRAY_REF) 902 get_canon_type (TREE_TYPE (cref), false, false); 903 904 cref = TREE_OPERAND (cref, 0); 905 } 906 907 if (TREE_CODE (x) == VAR_DECL) 908 has_proper_scope_for_analysis (x); 909 } 910} 911 912 913/* Scan tree T to see if there are any casts within it. 914 LHS Is the LHS of the expression involving the cast. */ 915 916static void 917look_for_casts (tree lhs __attribute__((unused)), tree t) 918{ 919 if (is_gimple_cast (t) || TREE_CODE (t) == VIEW_CONVERT_EXPR) 920 { 921 tree castfromvar = TREE_OPERAND (t, 0); 922 check_cast (TREE_TYPE (t), castfromvar); 923 } 924 else if (TREE_CODE (t) == COMPONENT_REF 925 || TREE_CODE (t) == INDIRECT_REF 926 || TREE_CODE (t) == BIT_FIELD_REF) 927 { 928 tree base = get_base_address (t); 929 while (t != base) 930 { 931 t = TREE_OPERAND (t, 0); 932 if (TREE_CODE (t) == VIEW_CONVERT_EXPR) 933 { 934 /* This may be some part of a component ref. 935 IE it may be a.b.VIEW_CONVERT_EXPR<weird_type>(c).d, AFAIK. 936 castfromref will give you a.b.c, not a. */ 937 tree castfromref = TREE_OPERAND (t, 0); 938 check_cast (TREE_TYPE (t), castfromref); 939 } 940 else if (TREE_CODE (t) == COMPONENT_REF) 941 get_canon_type (TREE_TYPE (TREE_OPERAND (t, 1)), false, false); 942 } 943 } 944} 945 946/* Check to see if T is a read or address of operation on a static var 947 we are interested in analyzing. */ 948 949static void 950check_rhs_var (tree t) 951{ 952 look_for_address_of (t); 953 check_tree(t); 954} 955 956/* Check to see if T is an assignment to a static var we are 957 interested in analyzing. */ 958 959static void 960check_lhs_var (tree t) 961{ 962 check_tree(t); 963} 964 965/* This is a scaled down version of get_asm_expr_operands from 966 tree_ssa_operands.c. The version there runs much later and assumes 967 that aliasing information is already available. Here we are just 968 trying to find if the set of inputs and outputs contain references 969 or address of operations to local. FN is the function being 970 analyzed and STMT is the actual asm statement. */ 971 972static void 973get_asm_expr_operands (tree stmt) 974{ 975 int noutputs = list_length (ASM_OUTPUTS (stmt)); 976 const char **oconstraints 977 = (const char **) alloca ((noutputs) * sizeof (const char *)); 978 int i; 979 tree link; 980 const char *constraint; 981 bool allows_mem, allows_reg, is_inout; 982 983 for (i=0, link = ASM_OUTPUTS (stmt); link; ++i, link = TREE_CHAIN (link)) 984 { 985 oconstraints[i] = constraint 986 = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link))); 987 parse_output_constraint (&constraint, i, 0, 0, 988 &allows_mem, &allows_reg, &is_inout); 989 990 check_lhs_var (TREE_VALUE (link)); 991 } 992 993 for (link = ASM_INPUTS (stmt); link; link = TREE_CHAIN (link)) 994 { 995 constraint 996 = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link))); 997 parse_input_constraint (&constraint, 0, 0, noutputs, 0, 998 oconstraints, &allows_mem, &allows_reg); 999 1000 check_rhs_var (TREE_VALUE (link)); 1001 } 1002 1003 /* There is no code here to check for asm memory clobbers. The 1004 casual maintainer might think that such code would be necessary, 1005 but that appears to be wrong. In other parts of the compiler, 1006 the asm memory clobbers are assumed to only clobber variables 1007 that are addressable. All types with addressable instances are 1008 assumed to already escape. So, we are protected here. */ 1009} 1010 1011/* Check the parameters of a function call to CALL_EXPR to mark the 1012 types that pass across the function boundary. Also check to see if 1013 this is either an indirect call, a call outside the compilation 1014 unit. */ 1015 1016static bool 1017check_call (tree call_expr) 1018{ 1019 int flags = call_expr_flags(call_expr); 1020 tree operand_list = TREE_OPERAND (call_expr, 1); 1021 tree operand; 1022 tree callee_t = get_callee_fndecl (call_expr); 1023 tree argument; 1024 struct cgraph_node* callee; 1025 enum availability avail = AVAIL_NOT_AVAILABLE; 1026 1027 for (operand = operand_list; 1028 operand != NULL_TREE; 1029 operand = TREE_CHAIN (operand)) 1030 { 1031 tree argument = TREE_VALUE (operand); 1032 check_rhs_var (argument); 1033 } 1034 1035 if (callee_t) 1036 { 1037 tree arg_type; 1038 tree last_arg_type = NULL; 1039 callee = cgraph_node(callee_t); 1040 avail = cgraph_function_body_availability (callee); 1041 1042 /* Check that there are no implicit casts in the passing of 1043 parameters. */ 1044 if (TYPE_ARG_TYPES (TREE_TYPE (callee_t))) 1045 { 1046 operand = operand_list; 1047 for (arg_type = TYPE_ARG_TYPES (TREE_TYPE (callee_t)); 1048 arg_type && TREE_VALUE (arg_type) != void_type_node; 1049 arg_type = TREE_CHAIN (arg_type)) 1050 { 1051 if (operand) 1052 { 1053 argument = TREE_VALUE (operand); 1054 last_arg_type = TREE_VALUE(arg_type); 1055 check_cast (last_arg_type, argument); 1056 operand = TREE_CHAIN (operand); 1057 } 1058 else 1059 /* The code reaches here for some unfortunate 1060 builtin functions that do not have a list of 1061 argument types. */ 1062 break; 1063 } 1064 } 1065 else 1066 { 1067 /* FIXME - According to Geoff Keating, we should never 1068 have to do this; the front ends should always process 1069 the arg list from the TYPE_ARG_LIST. */ 1070 operand = operand_list; 1071 for (arg_type = DECL_ARGUMENTS (callee_t); 1072 arg_type; 1073 arg_type = TREE_CHAIN (arg_type)) 1074 { 1075 if (operand) 1076 { 1077 argument = TREE_VALUE (operand); 1078 last_arg_type = TREE_TYPE(arg_type); 1079 check_cast (last_arg_type, argument); 1080 operand = TREE_CHAIN (operand); 1081 } 1082 else 1083 /* The code reaches here for some unfortunate 1084 builtin functions that do not have a list of 1085 argument types. */ 1086 break; 1087 } 1088 } 1089 1090 /* In the case where we have a var_args function, we need to 1091 check the remaining parameters against the last argument. */ 1092 arg_type = last_arg_type; 1093 for (; 1094 operand != NULL_TREE; 1095 operand = TREE_CHAIN (operand)) 1096 { 1097 argument = TREE_VALUE (operand); 1098 if (arg_type) 1099 check_cast (arg_type, argument); 1100 else 1101 { 1102 /* The code reaches here for some unfortunate 1103 builtin functions that do not have a list of 1104 argument types. Most of these functions have 1105 been marked as having their parameters not 1106 escape, but for the rest, the type is doomed. */ 1107 tree type = get_canon_type (TREE_TYPE (argument), false, false); 1108 mark_interesting_type (type, FULL_ESCAPE); 1109 } 1110 } 1111 } 1112 1113 /* The callee is either unknown (indirect call) or there is just no 1114 scannable code for it (external call) . We look to see if there 1115 are any bits available for the callee (such as by declaration or 1116 because it is builtin) and process solely on the basis of those 1117 bits. */ 1118 1119 if (avail == AVAIL_NOT_AVAILABLE || avail == AVAIL_OVERWRITABLE) 1120 { 1121 /* If this is a direct call to an external function, mark all of 1122 the parameter and return types. */ 1123 for (operand = operand_list; 1124 operand != NULL_TREE; 1125 operand = TREE_CHAIN (operand)) 1126 { 1127 tree type = 1128 get_canon_type (TREE_TYPE (TREE_VALUE (operand)), false, false); 1129 mark_interesting_type (type, EXPOSED_PARAMETER); 1130 } 1131 1132 if (callee_t) 1133 { 1134 tree type = 1135 get_canon_type (TREE_TYPE (TREE_TYPE (callee_t)), false, false); 1136 mark_interesting_type (type, EXPOSED_PARAMETER); 1137 } 1138 } 1139 return (flags & ECF_MALLOC); 1140} 1141 1142/* CODE is the operation on OP0 and OP1. OP0 is the operand that we 1143 *know* is a pointer type. OP1 may be a pointer type. */ 1144static bool 1145okay_pointer_operation (enum tree_code code, tree op0, tree op1) 1146{ 1147 tree op0type = TYPE_MAIN_VARIANT (TREE_TYPE (op0)); 1148 tree op1type = TYPE_MAIN_VARIANT (TREE_TYPE (op1)); 1149 if (POINTER_TYPE_P (op1type)) 1150 return false; 1151 switch (code) 1152 { 1153 case MULT_EXPR: 1154 case PLUS_EXPR: 1155 case MINUS_EXPR: 1156 /* TODO: Handle multiples of op0 size as well */ 1157 if (operand_equal_p (size_in_bytes (op0type), op1, 0)) 1158 return true; 1159 /* fallthrough */ 1160 1161 default: 1162 return false; 1163 } 1164 return false; 1165} 1166 1167/* TP is the part of the tree currently under the microscope. 1168 WALK_SUBTREES is part of the walk_tree api but is unused here. 1169 DATA is cgraph_node of the function being walked. */ 1170 1171/* FIXME: When this is converted to run over SSA form, this code 1172 should be converted to use the operand scanner. */ 1173 1174static tree 1175scan_for_refs (tree *tp, int *walk_subtrees, void *data) 1176{ 1177 struct cgraph_node *fn = data; 1178 tree t = *tp; 1179 1180 switch (TREE_CODE (t)) 1181 { 1182 case VAR_DECL: 1183 if (DECL_INITIAL (t)) 1184 walk_tree (&DECL_INITIAL (t), scan_for_refs, fn, visited_nodes); 1185 *walk_subtrees = 0; 1186 break; 1187 1188 case MODIFY_EXPR: 1189 { 1190 /* First look on the lhs and see what variable is stored to */ 1191 tree lhs = TREE_OPERAND (t, 0); 1192 tree rhs = TREE_OPERAND (t, 1); 1193 1194 check_lhs_var (lhs); 1195 check_cast (TREE_TYPE (lhs), rhs); 1196 1197 /* For the purposes of figuring out what the cast affects */ 1198 1199 /* Next check the operands on the rhs to see if they are ok. */ 1200 switch (TREE_CODE_CLASS (TREE_CODE (rhs))) 1201 { 1202 case tcc_binary: 1203 { 1204 tree op0 = TREE_OPERAND (rhs, 0); 1205 tree type0 = get_canon_type (TREE_TYPE (op0), false, false); 1206 tree op1 = TREE_OPERAND (rhs, 1); 1207 tree type1 = get_canon_type (TREE_TYPE (op1), false, false); 1208 1209 /* If this is pointer arithmetic of any bad sort, then 1210 we need to mark the types as bad. For binary 1211 operations, no binary operator we currently support 1212 is always "safe" in regard to what it would do to 1213 pointers for purposes of determining which types 1214 escape, except operations of the size of the type. 1215 It is possible that min and max under the right set 1216 of circumstances and if the moon is in the correct 1217 place could be safe, but it is hard to see how this 1218 is worth the effort. */ 1219 1220 if (type0 && POINTER_TYPE_P (type0) 1221 && !okay_pointer_operation (TREE_CODE (rhs), op0, op1)) 1222 mark_interesting_type (type0, FULL_ESCAPE); 1223 if (type1 && POINTER_TYPE_P (type1) 1224 && !okay_pointer_operation (TREE_CODE (rhs), op1, op0)) 1225 mark_interesting_type (type1, FULL_ESCAPE); 1226 1227 look_for_casts (lhs, op0); 1228 look_for_casts (lhs, op1); 1229 check_rhs_var (op0); 1230 check_rhs_var (op1); 1231 } 1232 break; 1233 case tcc_unary: 1234 { 1235 tree op0 = TREE_OPERAND (rhs, 0); 1236 tree type0 = get_canon_type (TREE_TYPE (op0), false, false); 1237 /* For unary operations, if the operation is NEGATE or 1238 ABS on a pointer, this is also considered pointer 1239 arithmetic and thus, bad for business. */ 1240 if (type0 && (TREE_CODE (op0) == NEGATE_EXPR 1241 || TREE_CODE (op0) == ABS_EXPR) 1242 && POINTER_TYPE_P (type0)) 1243 { 1244 mark_interesting_type (type0, FULL_ESCAPE); 1245 } 1246 check_rhs_var (op0); 1247 look_for_casts (lhs, op0); 1248 look_for_casts (lhs, rhs); 1249 } 1250 1251 break; 1252 case tcc_reference: 1253 look_for_casts (lhs, rhs); 1254 check_rhs_var (rhs); 1255 break; 1256 case tcc_declaration: 1257 check_rhs_var (rhs); 1258 break; 1259 case tcc_expression: 1260 switch (TREE_CODE (rhs)) 1261 { 1262 case ADDR_EXPR: 1263 look_for_casts (lhs, TREE_OPERAND (rhs, 0)); 1264 check_rhs_var (rhs); 1265 break; 1266 case CALL_EXPR: 1267 /* If this is a call to malloc, squirrel away the 1268 result so we do mark the resulting cast as being 1269 bad. */ 1270 if (check_call (rhs)) 1271 bitmap_set_bit (results_of_malloc, DECL_UID (lhs)); 1272 break; 1273 default: 1274 break; 1275 } 1276 break; 1277 default: 1278 break; 1279 } 1280 *walk_subtrees = 0; 1281 } 1282 break; 1283 1284 case ADDR_EXPR: 1285 /* This case is here to find addresses on rhs of constructors in 1286 decl_initial of static variables. */ 1287 check_rhs_var (t); 1288 *walk_subtrees = 0; 1289 break; 1290 1291 case CALL_EXPR: 1292 check_call (t); 1293 *walk_subtrees = 0; 1294 break; 1295 1296 case ASM_EXPR: 1297 get_asm_expr_operands (t); 1298 *walk_subtrees = 0; 1299 break; 1300 1301 default: 1302 break; 1303 } 1304 return NULL; 1305} 1306 1307 1308/* The init routine for analyzing global static variable usage. See 1309 comments at top for description. */ 1310static void 1311ipa_init (void) 1312{ 1313 bitmap_obstack_initialize (&ipa_obstack); 1314 global_types_exposed_parameter = BITMAP_ALLOC (&ipa_obstack); 1315 global_types_full_escape = BITMAP_ALLOC (&ipa_obstack); 1316 global_types_seen = BITMAP_ALLOC (&ipa_obstack); 1317 results_of_malloc = BITMAP_ALLOC (&ipa_obstack); 1318 1319 uid_to_canon_type = splay_tree_new (splay_tree_compare_ints, 0, 0); 1320 all_canon_types = splay_tree_new (compare_type_brand, 0, 0); 1321 type_to_canon_type = splay_tree_new (splay_tree_compare_pointers, 0, 0); 1322 uid_to_subtype_map = splay_tree_new (splay_tree_compare_ints, 0, 0); 1323 uid_to_addressof_down_map = splay_tree_new (splay_tree_compare_ints, 0, 0); 1324 uid_to_addressof_up_map = splay_tree_new (splay_tree_compare_ints, 0, 0); 1325 1326 /* There are some shared nodes, in particular the initializers on 1327 static declarations. We do not need to scan them more than once 1328 since all we would be interested in are the addressof 1329 operations. */ 1330 visited_nodes = pointer_set_create (); 1331 initialized = true; 1332} 1333 1334/* Check out the rhs of a static or global initialization VNODE to see 1335 if any of them contain addressof operations. Note that some of 1336 these variables may not even be referenced in the code in this 1337 compilation unit but their right hand sides may contain references 1338 to variables defined within this unit. */ 1339 1340static void 1341analyze_variable (struct cgraph_varpool_node *vnode) 1342{ 1343 tree global = vnode->decl; 1344 tree type = get_canon_type (TREE_TYPE (global), false, false); 1345 1346 /* If this variable has exposure beyond the compilation unit, add 1347 its type to the global types. */ 1348 1349 if (vnode->externally_visible) 1350 mark_interesting_type (type, FULL_ESCAPE); 1351 1352 if (TREE_CODE (global) == VAR_DECL) 1353 { 1354 if (DECL_INITIAL (global)) 1355 walk_tree (&DECL_INITIAL (global), scan_for_refs, 1356 NULL, visited_nodes); 1357 } 1358 else abort(); 1359} 1360 1361/* This is the main routine for finding the reference patterns for 1362 global variables within a function FN. */ 1363 1364static void 1365analyze_function (struct cgraph_node *fn) 1366{ 1367 tree decl = fn->decl; 1368 check_function_parameter_and_return_types (decl, 1369 fn->local.externally_visible); 1370 if (dump_file) 1371 fprintf (dump_file, "\n local analysis of %s", cgraph_node_name (fn)); 1372 1373 { 1374 struct function *this_cfun = DECL_STRUCT_FUNCTION (decl); 1375 basic_block this_block; 1376 1377 FOR_EACH_BB_FN (this_block, this_cfun) 1378 { 1379 block_stmt_iterator bsi; 1380 for (bsi = bsi_start (this_block); !bsi_end_p (bsi); bsi_next (&bsi)) 1381 walk_tree (bsi_stmt_ptr (bsi), scan_for_refs, 1382 fn, visited_nodes); 1383 } 1384 } 1385 1386 /* There may be const decls with interesting right hand sides. */ 1387 if (DECL_STRUCT_FUNCTION (decl)) 1388 { 1389 tree step; 1390 for (step = DECL_STRUCT_FUNCTION (decl)->unexpanded_var_list; 1391 step; 1392 step = TREE_CHAIN (step)) 1393 { 1394 tree var = TREE_VALUE (step); 1395 if (TREE_CODE (var) == VAR_DECL 1396 && DECL_INITIAL (var) 1397 && !TREE_STATIC (var)) 1398 walk_tree (&DECL_INITIAL (var), scan_for_refs, 1399 fn, visited_nodes); 1400 get_canon_type (TREE_TYPE (var), false, false); 1401 } 1402 } 1403} 1404 1405 1406 1407/* Convert a type_UID into a type. */ 1408static tree 1409type_for_uid (int uid) 1410{ 1411 splay_tree_node result = 1412 splay_tree_lookup (uid_to_canon_type, (splay_tree_key) uid); 1413 1414 if (result) 1415 return (tree) result->value; 1416 else return NULL; 1417} 1418 1419/* Return the a bitmap with the subtypes of the type for UID. If it 1420 does not exist, return either NULL or a new bitmap depending on the 1421 value of CREATE. */ 1422 1423static bitmap 1424subtype_map_for_uid (int uid, bool create) 1425{ 1426 splay_tree_node result = splay_tree_lookup (uid_to_subtype_map, 1427 (splay_tree_key) uid); 1428 1429 if (result) 1430 return (bitmap) result->value; 1431 else if (create) 1432 { 1433 bitmap subtype_map = BITMAP_ALLOC (&ipa_obstack); 1434 splay_tree_insert (uid_to_subtype_map, 1435 uid, 1436 (splay_tree_value)subtype_map); 1437 return subtype_map; 1438 } 1439 else return NULL; 1440} 1441 1442/* Mark all of the supertypes and field types of TYPE as being seen. 1443 Also accumulate the subtypes for each type so that 1444 close_types_full_escape can mark a subtype as escaping if the 1445 supertype escapes. */ 1446 1447static void 1448close_type_seen (tree type) 1449{ 1450 tree field; 1451 int i, uid; 1452 tree binfo, base_binfo; 1453 1454 /* See thru all pointer tos and array ofs. */ 1455 type = get_canon_type (type, true, true); 1456 if (!type) 1457 return; 1458 1459 uid = TYPE_UID (type); 1460 1461 if (bitmap_bit_p (been_there_done_that, uid)) 1462 return; 1463 bitmap_set_bit (been_there_done_that, uid); 1464 1465 /* If we are doing a language with a type hierarchy, mark all of 1466 the superclasses. */ 1467 if (TYPE_BINFO (type)) 1468 for (binfo = TYPE_BINFO (type), i = 0; 1469 BINFO_BASE_ITERATE (binfo, i, base_binfo); i++) 1470 { 1471 tree binfo_type = BINFO_TYPE (base_binfo); 1472 bitmap subtype_map = subtype_map_for_uid 1473 (TYPE_UID (TYPE_MAIN_VARIANT (binfo_type)), true); 1474 bitmap_set_bit (subtype_map, uid); 1475 close_type_seen (get_canon_type (binfo_type, true, true)); 1476 } 1477 1478 /* If the field is a struct or union type, mark all of the 1479 subfields. */ 1480 for (field = TYPE_FIELDS (type); 1481 field; 1482 field = TREE_CHAIN (field)) 1483 { 1484 tree field_type; 1485 if (TREE_CODE (field) != FIELD_DECL) 1486 continue; 1487 1488 field_type = TREE_TYPE (field); 1489 if (ipa_type_escape_star_count_of_interesting_or_array_type (field_type) >= 0) 1490 close_type_seen (get_canon_type (field_type, true, true)); 1491 } 1492} 1493 1494/* Take a TYPE that has been passed by value to an external function 1495 and mark all of the fields that have pointer types as escaping. For 1496 any of the non pointer types that are structures or unions, 1497 recurse. TYPE is never a pointer type. */ 1498 1499static void 1500close_type_exposed_parameter (tree type) 1501{ 1502 tree field; 1503 int uid; 1504 1505 type = get_canon_type (type, false, false); 1506 if (!type) 1507 return; 1508 uid = TYPE_UID (type); 1509 gcc_assert (!POINTER_TYPE_P (type)); 1510 1511 if (bitmap_bit_p (been_there_done_that, uid)) 1512 return; 1513 bitmap_set_bit (been_there_done_that, uid); 1514 1515 /* If the field is a struct or union type, mark all of the 1516 subfields. */ 1517 for (field = TYPE_FIELDS (type); 1518 field; 1519 field = TREE_CHAIN (field)) 1520 { 1521 tree field_type; 1522 1523 if (TREE_CODE (field) != FIELD_DECL) 1524 continue; 1525 1526 field_type = get_canon_type (TREE_TYPE (field), false, false); 1527 mark_interesting_type (field_type, EXPOSED_PARAMETER); 1528 1529 /* Only recurse for non pointer types of structures and unions. */ 1530 if (ipa_type_escape_star_count_of_interesting_type (field_type) == 0) 1531 close_type_exposed_parameter (field_type); 1532 } 1533} 1534 1535/* The next function handles the case where a type fully escapes. 1536 This means that not only does the type itself escape, 1537 1538 a) the type of every field recursively escapes 1539 b) the type of every subtype escapes as well as the super as well 1540 as all of the pointer to types for each field. 1541 1542 Note that pointer to types are not marked as escaping. If the 1543 pointed to type escapes, the pointer to type also escapes. 1544 1545 Take a TYPE that has had the address taken for an instance of it 1546 and mark all of the types for its fields as having their addresses 1547 taken. */ 1548 1549static void 1550close_type_full_escape (tree type) 1551{ 1552 tree field; 1553 unsigned int i; 1554 int uid; 1555 tree binfo, base_binfo; 1556 bitmap_iterator bi; 1557 bitmap subtype_map; 1558 splay_tree_node address_result; 1559 1560 /* Strip off any pointer or array types. */ 1561 type = get_canon_type (type, true, true); 1562 if (!type) 1563 return; 1564 uid = TYPE_UID (type); 1565 1566 if (bitmap_bit_p (been_there_done_that, uid)) 1567 return; 1568 bitmap_set_bit (been_there_done_that, uid); 1569 1570 subtype_map = subtype_map_for_uid (uid, false); 1571 1572 /* If we are doing a language with a type hierarchy, mark all of 1573 the superclasses. */ 1574 if (TYPE_BINFO (type)) 1575 for (binfo = TYPE_BINFO (type), i = 0; 1576 BINFO_BASE_ITERATE (binfo, i, base_binfo); i++) 1577 { 1578 tree binfotype = BINFO_TYPE (base_binfo); 1579 binfotype = mark_type (binfotype, FULL_ESCAPE); 1580 close_type_full_escape (binfotype); 1581 } 1582 1583 /* Mark as escaped any types that have been down casted to 1584 this type. */ 1585 if (subtype_map) 1586 EXECUTE_IF_SET_IN_BITMAP (subtype_map, 0, i, bi) 1587 { 1588 tree subtype = type_for_uid (i); 1589 subtype = mark_type (subtype, FULL_ESCAPE); 1590 close_type_full_escape (subtype); 1591 } 1592 1593 /* If the field is a struct or union type, mark all of the 1594 subfields. */ 1595 for (field = TYPE_FIELDS (type); 1596 field; 1597 field = TREE_CHAIN (field)) 1598 { 1599 tree field_type; 1600 if (TREE_CODE (field) != FIELD_DECL) 1601 continue; 1602 1603 field_type = TREE_TYPE (field); 1604 if (ipa_type_escape_star_count_of_interesting_or_array_type (field_type) >= 0) 1605 { 1606 field_type = mark_type (field_type, FULL_ESCAPE); 1607 close_type_full_escape (field_type); 1608 } 1609 } 1610 1611 /* For all of the types A that contain this type B and were part of 1612 an expression like "&...A.B...", mark the A's as escaping. */ 1613 address_result = splay_tree_lookup (uid_to_addressof_up_map, 1614 (splay_tree_key) uid); 1615 if (address_result) 1616 { 1617 bitmap containing_classes = (bitmap) address_result->value; 1618 EXECUTE_IF_SET_IN_BITMAP (containing_classes, 0, i, bi) 1619 { 1620 close_type_full_escape (type_for_uid (i)); 1621 } 1622 } 1623} 1624 1625/* Transitively close the addressof bitmap for the type with UID. 1626 This means that if we had a.b and b.c, a would have both b and c in 1627 its maps. */ 1628 1629static bitmap 1630close_addressof_down (int uid) 1631{ 1632 bitmap_iterator bi; 1633 splay_tree_node result = 1634 splay_tree_lookup (uid_to_addressof_down_map, (splay_tree_key) uid); 1635 bitmap map = NULL; 1636 bitmap new_map; 1637 unsigned int i; 1638 1639 if (result) 1640 map = (bitmap) result->value; 1641 else 1642 return NULL; 1643 1644 if (bitmap_bit_p (been_there_done_that, uid)) 1645 return map; 1646 bitmap_set_bit (been_there_done_that, uid); 1647 1648 /* If the type escapes, get rid of the addressof map, it will not be 1649 needed. */ 1650 if (bitmap_bit_p (global_types_full_escape, uid)) 1651 { 1652 BITMAP_FREE (map); 1653 splay_tree_remove (uid_to_addressof_down_map, (splay_tree_key) uid); 1654 return NULL; 1655 } 1656 1657 /* The new_map will have all of the bits for the enclosed fields and 1658 will have the unique id version of the old map. */ 1659 new_map = BITMAP_ALLOC (&ipa_obstack); 1660 1661 EXECUTE_IF_SET_IN_BITMAP (map, 0, i, bi) 1662 { 1663 bitmap submap = close_addressof_down (i); 1664 bitmap_set_bit (new_map, i); 1665 if (submap) 1666 bitmap_ior_into (new_map, submap); 1667 } 1668 result->value = (splay_tree_value) new_map; 1669 1670 BITMAP_FREE (map); 1671 return new_map; 1672} 1673 1674 1675/* The main entry point for type escape analysis. */ 1676 1677static void 1678type_escape_execute (void) 1679{ 1680 struct cgraph_node *node; 1681 struct cgraph_varpool_node *vnode; 1682 unsigned int i; 1683 bitmap_iterator bi; 1684 splay_tree_node result; 1685 1686 ipa_init (); 1687 1688 /* Process all of the variables first. */ 1689 for (vnode = cgraph_varpool_nodes_queue; vnode; vnode = vnode->next_needed) 1690 analyze_variable (vnode); 1691 1692 /* Process all of the functions. next 1693 1694 We do not want to process any of the clones so we check that this 1695 is a master clone. However, we do need to process any 1696 AVAIL_OVERWRITABLE functions (these are never clones) because 1697 they may cause a type variable to escape. 1698 */ 1699 for (node = cgraph_nodes; node; node = node->next) 1700 if (node->analyzed 1701 && (cgraph_is_master_clone (node) 1702 || (cgraph_function_body_availability (node) == AVAIL_OVERWRITABLE))) 1703 analyze_function (node); 1704 1705 1706 pointer_set_destroy (visited_nodes); 1707 visited_nodes = NULL; 1708 1709 /* Do all of the closures to discover which types escape the 1710 compilation unit. */ 1711 1712 been_there_done_that = BITMAP_ALLOC (&ipa_obstack); 1713 bitmap_tmp = BITMAP_ALLOC (&ipa_obstack); 1714 1715 /* Examine the types that we have directly seen in scanning the code 1716 and add to that any contained types or superclasses. */ 1717 1718 bitmap_copy (bitmap_tmp, global_types_seen); 1719 EXECUTE_IF_SET_IN_BITMAP (bitmap_tmp, 0, i, bi) 1720 { 1721 tree type = type_for_uid (i); 1722 /* Only look at records and unions and pointer tos. */ 1723 if (ipa_type_escape_star_count_of_interesting_or_array_type (type) >= 0) 1724 close_type_seen (type); 1725 } 1726 bitmap_clear (been_there_done_that); 1727 1728 /* Examine all of the types passed by value and mark any enclosed 1729 pointer types as escaping. */ 1730 bitmap_copy (bitmap_tmp, global_types_exposed_parameter); 1731 EXECUTE_IF_SET_IN_BITMAP (bitmap_tmp, 0, i, bi) 1732 { 1733 close_type_exposed_parameter (type_for_uid (i)); 1734 } 1735 bitmap_clear (been_there_done_that); 1736 1737 /* Close the types for escape. If something escapes, then any 1738 enclosed types escape as well as any subtypes. */ 1739 bitmap_copy (bitmap_tmp, global_types_full_escape); 1740 EXECUTE_IF_SET_IN_BITMAP (bitmap_tmp, 0, i, bi) 1741 { 1742 close_type_full_escape (type_for_uid (i)); 1743 } 1744 bitmap_clear (been_there_done_that); 1745 1746 /* Before this pass, the uid_to_addressof_down_map for type X 1747 contained an entry for Y if there had been an operation of the 1748 form &X.Y. This step adds all of the fields contained within Y 1749 (recursively) to X's map. */ 1750 1751 result = splay_tree_min (uid_to_addressof_down_map); 1752 while (result) 1753 { 1754 int uid = result->key; 1755 /* Close the addressof map, i.e. copy all of the transitive 1756 substructures up to this level. */ 1757 close_addressof_down (uid); 1758 result = splay_tree_successor (uid_to_addressof_down_map, uid); 1759 } 1760 1761 /* Do not need the array types and pointer types in the persistent 1762 data structures. */ 1763 result = splay_tree_min (all_canon_types); 1764 while (result) 1765 { 1766 tree type = (tree) result->value; 1767 tree key = (tree) result->key; 1768 if (POINTER_TYPE_P (type) 1769 || TREE_CODE (type) == ARRAY_TYPE) 1770 { 1771 splay_tree_remove (all_canon_types, (splay_tree_key) result->key); 1772 splay_tree_remove (type_to_canon_type, (splay_tree_key) type); 1773 splay_tree_remove (uid_to_canon_type, (splay_tree_key) TYPE_UID (type)); 1774 bitmap_clear_bit (global_types_seen, TYPE_UID (type)); 1775 } 1776 result = splay_tree_successor (all_canon_types, (splay_tree_key) key); 1777 } 1778 1779/* { */ 1780/* FILE * tmp = dump_file; */ 1781/* dump_file = stderr; */ 1782 if (dump_file) 1783 { 1784 EXECUTE_IF_SET_IN_BITMAP (global_types_seen, 0, i, bi) 1785 { 1786 /* The pointer types are in the global_types_full_escape 1787 bitmap but not in the backwards map. They also contain 1788 no useful information since they are not marked. */ 1789 tree type = type_for_uid (i); 1790 fprintf(dump_file, "type %d ", i); 1791 print_generic_expr (dump_file, type, 0); 1792 if (bitmap_bit_p (global_types_full_escape, i)) 1793 fprintf(dump_file, " escaped\n"); 1794 else 1795 fprintf(dump_file, " contained\n"); 1796 } 1797 } 1798/* dump_file = tmp; */ 1799/* } */ 1800 1801 /* Get rid of uid_to_addressof_up_map and its bitmaps. */ 1802 result = splay_tree_min (uid_to_addressof_up_map); 1803 while (result) 1804 { 1805 int uid = (int)result->key; 1806 bitmap bm = (bitmap)result->value; 1807 1808 BITMAP_FREE (bm); 1809 splay_tree_remove (uid_to_addressof_up_map, (splay_tree_key) uid); 1810 result = splay_tree_successor (uid_to_addressof_up_map, uid); 1811 } 1812 1813 /* Get rid of the subtype map. */ 1814 result = splay_tree_min (uid_to_subtype_map); 1815 while (result) 1816 { 1817 bitmap b = (bitmap)result->value; 1818 BITMAP_FREE(b); 1819 splay_tree_remove (uid_to_subtype_map, result->key); 1820 result = splay_tree_min (uid_to_subtype_map); 1821 } 1822 splay_tree_delete (uid_to_subtype_map); 1823 uid_to_subtype_map = NULL; 1824 1825 BITMAP_FREE (global_types_exposed_parameter); 1826 BITMAP_FREE (been_there_done_that); 1827 BITMAP_FREE (bitmap_tmp); 1828 BITMAP_FREE (results_of_malloc); 1829} 1830 1831static bool 1832gate_type_escape_vars (void) 1833{ 1834 return (flag_unit_at_a_time != 0 && flag_ipa_type_escape 1835 /* Don't bother doing anything if the program has errors. */ 1836 && !(errorcount || sorrycount)); 1837} 1838 1839struct tree_opt_pass pass_ipa_type_escape = 1840{ 1841 "type-escape-var", /* name */ 1842 gate_type_escape_vars, /* gate */ 1843 type_escape_execute, /* execute */ 1844 NULL, /* sub */ 1845 NULL, /* next */ 1846 0, /* static_pass_number */ 1847 TV_IPA_TYPE_ESCAPE, /* tv_id */ 1848 0, /* properties_required */ 1849 0, /* properties_provided */ 1850 0, /* properties_destroyed */ 1851 0, /* todo_flags_start */ 1852 0, /* todo_flags_finish */ 1853 0 /* letter */ 1854}; 1855 1856