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