1169689Skan/* Type based alias analysis. 2169689Skan Copyright (C) 2004, 2005, 2006 Free Software Foundation, Inc. 3169689Skan Contributed by Kenneth Zadeck <zadeck@naturalbridge.com> 4169689Skan 5169689SkanThis file is part of GCC. 6169689Skan 7169689SkanGCC is free software; you can redistribute it and/or modify it under 8169689Skanthe terms of the GNU General Public License as published by the Free 9169689SkanSoftware Foundation; either version 2, or (at your option) any later 10169689Skanversion. 11169689Skan 12169689SkanGCC is distributed in the hope that it will be useful, but WITHOUT ANY 13169689SkanWARRANTY; without even the implied warranty of MERCHANTABILITY or 14169689SkanFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15169689Skanfor more details. 16169689Skan 17169689SkanYou should have received a copy of the GNU General Public License 18169689Skanalong with GCC; see the file COPYING. If not, write to the Free 19169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 20169689Skan02110-1301, USA. */ 21169689Skan 22169689Skan/* This pass determines which types in the program contain only 23169689Skan instances that are completely encapsulated by the compilation unit. 24169689Skan Those types that are encapsulated must also pass the further 25169689Skan requirement that there be no bad operations on any instances of 26169689Skan those types. 27169689Skan 28169689Skan A great deal of freedom in compilation is allowed for the instances 29169689Skan of those types that pass these conditions. 30169689Skan*/ 31169689Skan 32169689Skan/* The code in this module is called by the ipa pass manager. It 33169689Skan should be one of the later passes since its information is used by 34169689Skan the rest of the compilation. */ 35169689Skan 36169689Skan#include "config.h" 37169689Skan#include "system.h" 38169689Skan#include "coretypes.h" 39169689Skan#include "tm.h" 40169689Skan#include "tree.h" 41169689Skan#include "tree-flow.h" 42169689Skan#include "tree-inline.h" 43169689Skan#include "tree-pass.h" 44169689Skan#include "langhooks.h" 45169689Skan#include "pointer-set.h" 46169689Skan#include "ggc.h" 47169689Skan#include "ipa-utils.h" 48169689Skan#include "ipa-type-escape.h" 49169689Skan#include "c-common.h" 50169689Skan#include "tree-gimple.h" 51169689Skan#include "cgraph.h" 52169689Skan#include "output.h" 53169689Skan#include "flags.h" 54169689Skan#include "timevar.h" 55169689Skan#include "diagnostic.h" 56169689Skan#include "langhooks.h" 57169689Skan 58169689Skan/* Some of the aliasing is called very early, before this phase is 59169689Skan called. To assure that this is not a problem, we keep track of if 60169689Skan this phase has been run. */ 61169689Skanstatic bool initialized = false; 62169689Skan 63169689Skan/* This bitmap contains the set of local vars that are the lhs of 64169689Skan calls to mallocs. These variables, when seen on the rhs as part of 65169689Skan a cast, the cast are not marked as doing bad things to the type 66169689Skan even though they are generally of the form 67169689Skan "foo = (type_of_foo)void_temp". */ 68169689Skanstatic bitmap results_of_malloc; 69169689Skan 70169689Skan/* Scratch bitmap for avoiding work. */ 71169689Skanstatic bitmap been_there_done_that; 72169689Skanstatic bitmap bitmap_tmp; 73169689Skan 74169689Skan/* There are two levels of escape that types can undergo. 75169689Skan 76169689Skan EXPOSED_PARAMETER - some instance of the variable is 77169689Skan passed by value into an externally visible function or some 78169689Skan instance of the variable is passed out of an externally visible 79169689Skan function as a return value. In this case any of the fields of the 80169689Skan variable that are pointer types end up having their types marked as 81169689Skan FULL_ESCAPE. 82169689Skan 83169689Skan FULL_ESCAPE - when bad things happen to good types. One of the 84169689Skan following things happens to the type: (a) either an instance of the 85169689Skan variable has its address passed to an externally visible function, 86169689Skan (b) the address is taken and some bad cast happens to the address 87169689Skan or (c) explicit arithmetic is done to the address. 88169689Skan*/ 89169689Skan 90169689Skanenum escape_t 91169689Skan{ 92169689Skan EXPOSED_PARAMETER, 93169689Skan FULL_ESCAPE 94169689Skan}; 95169689Skan 96169689Skan/* The following two bit vectors global_types_* correspond to 97169689Skan previous cases above. During the analysis phase, a bit is set in 98169689Skan one of these vectors if an operation of the offending class is 99169689Skan discovered to happen on the associated type. */ 100169689Skan 101169689Skanstatic bitmap global_types_exposed_parameter; 102169689Skanstatic bitmap global_types_full_escape; 103169689Skan 104169689Skan/* All of the types seen in this compilation unit. */ 105169689Skanstatic bitmap global_types_seen; 106169689Skan/* Reverse map to take a canon uid and map it to a canon type. Uid's 107169689Skan are never manipulated unless they are associated with a canon 108169689Skan type. */ 109169689Skanstatic splay_tree uid_to_canon_type; 110169689Skan 111169689Skan/* Internal structure of type mapping code. This maps a canon type 112169689Skan name to its canon type. */ 113169689Skanstatic splay_tree all_canon_types; 114169689Skan 115169689Skan/* Map from type clones to the single canon type. */ 116169689Skanstatic splay_tree type_to_canon_type; 117169689Skan 118169689Skan/* A splay tree of bitmaps. An element X in the splay tree has a bit 119169689Skan set in its bitmap at TYPE_UID (TYPE_MAIN_VARIANT (Y)) if there was 120169689Skan an operation in the program of the form "&X.Y". */ 121169689Skanstatic splay_tree uid_to_addressof_down_map; 122169689Skan 123169689Skan/* A splay tree of bitmaps. An element Y in the splay tree has a bit 124169689Skan set in its bitmap at TYPE_UID (TYPE_MAIN_VARIANT (X)) if there was 125169689Skan an operation in the program of the form "&X.Y". */ 126169689Skanstatic splay_tree uid_to_addressof_up_map; 127169689Skan 128169689Skan/* Tree to hold the subtype maps used to mark subtypes of escaped 129169689Skan types. */ 130169689Skanstatic splay_tree uid_to_subtype_map; 131169689Skan 132169689Skan/* Records tree nodes seen in cgraph_create_edges. Simply using 133169689Skan walk_tree_without_duplicates doesn't guarantee each node is visited 134169689Skan once because it gets a new htab upon each recursive call from 135169689Skan scan_for_refs. */ 136169689Skanstatic struct pointer_set_t *visited_nodes; 137169689Skan 138169689Skanstatic bitmap_obstack ipa_obstack; 139169689Skan 140169689Skan/* Get the name of TYPE or return the string "<UNNAMED>". */ 141169689Skanstatic char* 142169689Skanget_name_of_type (tree type) 143169689Skan{ 144169689Skan tree name = TYPE_NAME (type); 145169689Skan 146169689Skan if (!name) 147169689Skan /* Unnamed type, do what you like here. */ 148169689Skan return (char*)"<UNNAMED>"; 149169689Skan 150169689Skan /* It will be a TYPE_DECL in the case of a typedef, otherwise, an 151169689Skan identifier_node */ 152169689Skan if (TREE_CODE (name) == TYPE_DECL) 153169689Skan { 154169689Skan /* Each DECL has a DECL_NAME field which contains an 155169689Skan IDENTIFIER_NODE. (Some decls, most often labels, may have 156169689Skan zero as the DECL_NAME). */ 157169689Skan if (DECL_NAME (name)) 158169689Skan return (char*)IDENTIFIER_POINTER (DECL_NAME (name)); 159169689Skan else 160169689Skan /* Unnamed type, do what you like here. */ 161169689Skan return (char*)"<UNNAMED>"; 162169689Skan } 163169689Skan else if (TREE_CODE (name) == IDENTIFIER_NODE) 164169689Skan return (char*)IDENTIFIER_POINTER (name); 165169689Skan else 166169689Skan return (char*)"<UNNAMED>"; 167169689Skan} 168169689Skan 169169689Skanstruct type_brand_s 170169689Skan{ 171169689Skan char* name; 172169689Skan int seq; 173169689Skan}; 174169689Skan 175169689Skan/* Splay tree comparison function on type_brand_s structures. */ 176169689Skan 177169689Skanstatic int 178169689Skancompare_type_brand (splay_tree_key sk1, splay_tree_key sk2) 179169689Skan{ 180169689Skan struct type_brand_s * k1 = (struct type_brand_s *) sk1; 181169689Skan struct type_brand_s * k2 = (struct type_brand_s *) sk2; 182169689Skan 183169689Skan int value = strcmp(k1->name, k2->name); 184169689Skan if (value == 0) 185169689Skan return k2->seq - k1->seq; 186169689Skan else 187169689Skan return value; 188169689Skan} 189169689Skan 190169689Skan/* All of the "unique_type" code is a hack to get around the sleazy 191169689Skan implementation used to compile more than file. Currently gcc does 192169689Skan not get rid of multiple instances of the same type that have been 193169689Skan collected from different compilation units. */ 194169689Skan/* This is a trivial algorithm for removing duplicate types. This 195169689Skan would not work for any language that used structural equivalence as 196169689Skan the basis of its type system. */ 197169689Skan/* Return either TYPE if this is first time TYPE has been seen an 198169689Skan compatible TYPE that has already been processed. */ 199169689Skan 200169689Skanstatic tree 201169689Skandiscover_unique_type (tree type) 202169689Skan{ 203169689Skan struct type_brand_s * brand = XNEW (struct type_brand_s); 204169689Skan int i = 0; 205169689Skan splay_tree_node result; 206169689Skan 207169689Skan brand->name = get_name_of_type (type); 208169689Skan 209169689Skan while (1) 210169689Skan { 211169689Skan brand->seq = i++; 212169689Skan result = splay_tree_lookup (all_canon_types, (splay_tree_key) brand); 213169689Skan 214169689Skan if (result) 215169689Skan { 216169689Skan /* Create an alias since this is just the same as 217169689Skan other_type. */ 218169689Skan tree other_type = (tree) result->value; 219169689Skan if (lang_hooks.types_compatible_p (type, other_type) == 1) 220169689Skan { 221169689Skan free (brand); 222169689Skan /* Insert this new type as an alias for other_type. */ 223169689Skan splay_tree_insert (type_to_canon_type, 224169689Skan (splay_tree_key) type, 225169689Skan (splay_tree_value) other_type); 226169689Skan return other_type; 227169689Skan } 228169689Skan /* Not compatible, look for next instance with same name. */ 229169689Skan } 230169689Skan else 231169689Skan { 232169689Skan /* No more instances, create new one since this is the first 233169689Skan time we saw this type. */ 234169689Skan brand->seq = i++; 235169689Skan /* Insert the new brand. */ 236169689Skan splay_tree_insert (all_canon_types, 237169689Skan (splay_tree_key) brand, 238169689Skan (splay_tree_value) type); 239169689Skan 240169689Skan /* Insert this new type as an alias for itself. */ 241169689Skan splay_tree_insert (type_to_canon_type, 242169689Skan (splay_tree_key) type, 243169689Skan (splay_tree_value) type); 244169689Skan 245169689Skan /* Insert the uid for reverse lookup; */ 246169689Skan splay_tree_insert (uid_to_canon_type, 247169689Skan (splay_tree_key) TYPE_UID (type), 248169689Skan (splay_tree_value) type); 249169689Skan 250169689Skan bitmap_set_bit (global_types_seen, TYPE_UID (type)); 251169689Skan return type; 252169689Skan } 253169689Skan } 254169689Skan} 255169689Skan 256169689Skan/* Return true if TYPE is one of the type classes that we are willing 257169689Skan to analyze. This skips the goofy types like arrays of pointers to 258169689Skan methods. */ 259169689Skanstatic bool 260169689Skantype_to_consider (tree type) 261169689Skan{ 262169689Skan /* Strip the *'s off. */ 263169689Skan type = TYPE_MAIN_VARIANT (type); 264169689Skan while (POINTER_TYPE_P (type) || TREE_CODE (type) == ARRAY_TYPE) 265169689Skan type = TYPE_MAIN_VARIANT (TREE_TYPE (type)); 266169689Skan 267169689Skan switch (TREE_CODE (type)) 268169689Skan { 269169689Skan case BOOLEAN_TYPE: 270169689Skan case COMPLEX_TYPE: 271169689Skan case ENUMERAL_TYPE: 272169689Skan case INTEGER_TYPE: 273169689Skan case QUAL_UNION_TYPE: 274169689Skan case REAL_TYPE: 275169689Skan case RECORD_TYPE: 276169689Skan case UNION_TYPE: 277169689Skan case VECTOR_TYPE: 278169689Skan case VOID_TYPE: 279169689Skan return true; 280169689Skan 281169689Skan default: 282169689Skan return false; 283169689Skan } 284169689Skan} 285169689Skan 286169689Skan/* Get the canon type of TYPE. If SEE_THRU_PTRS is true, remove all 287169689Skan the POINTER_TOs and if SEE_THRU_ARRAYS is true, remove all of the 288169689Skan ARRAY_OFs and POINTER_TOs. */ 289169689Skan 290169689Skanstatic tree 291169689Skanget_canon_type (tree type, bool see_thru_ptrs, bool see_thru_arrays) 292169689Skan{ 293169689Skan splay_tree_node result; 294169689Skan /* Strip the *'s off. */ 295169689Skan if (!type || !type_to_consider (type)) 296169689Skan return NULL; 297169689Skan 298169689Skan type = TYPE_MAIN_VARIANT (type); 299169689Skan if (see_thru_arrays) 300169689Skan while (POINTER_TYPE_P (type) || TREE_CODE (type) == ARRAY_TYPE) 301169689Skan type = TYPE_MAIN_VARIANT (TREE_TYPE (type)); 302169689Skan 303169689Skan else if (see_thru_ptrs) 304169689Skan while (POINTER_TYPE_P (type)) 305169689Skan type = TYPE_MAIN_VARIANT (TREE_TYPE (type)); 306169689Skan 307169689Skan result = splay_tree_lookup(type_to_canon_type, (splay_tree_key) type); 308169689Skan 309169689Skan if (result == NULL) 310169689Skan return discover_unique_type (type); 311169689Skan else return (tree) result->value; 312169689Skan} 313169689Skan 314169689Skan/* Same as GET_CANON_TYPE, except return the TYPE_ID rather than the 315169689Skan TYPE. */ 316169689Skan 317169689Skanstatic int 318169689Skanget_canon_type_uid (tree type, bool see_thru_ptrs, bool see_thru_arrays) 319169689Skan{ 320169689Skan type = get_canon_type (type, see_thru_ptrs, see_thru_arrays); 321169689Skan if (type) 322169689Skan return TYPE_UID(type); 323169689Skan else return 0; 324169689Skan} 325169689Skan 326169689Skan/* Return 0 if TYPE is a record or union type. Return a positive 327169689Skan number if TYPE is a pointer to a record or union. The number is 328169689Skan the number of pointer types stripped to get to the record or union 329169689Skan type. Return -1 if TYPE is none of the above. */ 330169689Skan 331169689Skanint 332169689Skanipa_type_escape_star_count_of_interesting_type (tree type) 333169689Skan{ 334169689Skan int count = 0; 335169689Skan /* Strip the *'s off. */ 336169689Skan if (!type) 337169689Skan return -1; 338169689Skan type = TYPE_MAIN_VARIANT (type); 339169689Skan while (POINTER_TYPE_P (type)) 340169689Skan { 341169689Skan type = TYPE_MAIN_VARIANT (TREE_TYPE (type)); 342169689Skan count++; 343169689Skan } 344169689Skan 345169689Skan /* We are interested in records, and unions only. */ 346169689Skan if (TREE_CODE (type) == RECORD_TYPE 347169689Skan || TREE_CODE (type) == QUAL_UNION_TYPE 348169689Skan || TREE_CODE (type) == UNION_TYPE) 349169689Skan return count; 350169689Skan else 351169689Skan return -1; 352169689Skan} 353169689Skan 354169689Skan 355169689Skan/* Return 0 if TYPE is a record or union type. Return a positive 356169689Skan number if TYPE is a pointer to a record or union. The number is 357169689Skan the number of pointer types stripped to get to the record or union 358169689Skan type. Return -1 if TYPE is none of the above. */ 359169689Skan 360169689Skanint 361169689Skanipa_type_escape_star_count_of_interesting_or_array_type (tree type) 362169689Skan{ 363169689Skan int count = 0; 364169689Skan /* Strip the *'s off. */ 365169689Skan if (!type) 366169689Skan return -1; 367169689Skan type = TYPE_MAIN_VARIANT (type); 368169689Skan while (POINTER_TYPE_P (type) || TREE_CODE (type) == ARRAY_TYPE) 369169689Skan { 370169689Skan type = TYPE_MAIN_VARIANT (TREE_TYPE (type)); 371169689Skan count++; 372169689Skan } 373169689Skan 374169689Skan /* We are interested in records, and unions only. */ 375169689Skan if (TREE_CODE (type) == RECORD_TYPE 376169689Skan || TREE_CODE (type) == QUAL_UNION_TYPE 377169689Skan || TREE_CODE (type) == UNION_TYPE) 378169689Skan return count; 379169689Skan else 380169689Skan return -1; 381169689Skan} 382169689Skan 383169689Skan 384169689Skan/* Return true if the record, or union TYPE passed in escapes this 385169689Skan compilation unit. Note that all of the pointer-to's are removed 386169689Skan before testing since these may not be correct. */ 387169689Skan 388169689Skanbool 389169689Skanipa_type_escape_type_contained_p (tree type) 390169689Skan{ 391169689Skan if (!initialized) 392169689Skan return false; 393169689Skan return !bitmap_bit_p (global_types_full_escape, 394169689Skan get_canon_type_uid (type, true, false)); 395169689Skan} 396169689Skan 397169689Skan/* Return true if a modification to a field of type FIELD_TYPE cannot 398169689Skan clobber a record of RECORD_TYPE. */ 399169689Skan 400169689Skanbool 401169689Skanipa_type_escape_field_does_not_clobber_p (tree record_type, tree field_type) 402169689Skan{ 403169689Skan splay_tree_node result; 404169689Skan int uid; 405169689Skan 406169689Skan if (!initialized) 407169689Skan return false; 408169689Skan 409169689Skan /* Strip off all of the pointer tos on the record type. Strip the 410169689Skan same number of pointer tos from the field type. If the field 411169689Skan type has fewer, it could not have been aliased. */ 412169689Skan record_type = TYPE_MAIN_VARIANT (record_type); 413169689Skan field_type = TYPE_MAIN_VARIANT (field_type); 414169689Skan while (POINTER_TYPE_P (record_type)) 415169689Skan { 416169689Skan record_type = TYPE_MAIN_VARIANT (TREE_TYPE (record_type)); 417169689Skan if (POINTER_TYPE_P (field_type)) 418169689Skan field_type = TYPE_MAIN_VARIANT (TREE_TYPE (field_type)); 419169689Skan else 420169689Skan /* However, if field_type is a union, this quick test is not 421169689Skan correct since one of the variants of the union may be a 422169689Skan pointer to type and we cannot see across that here. So we 423169689Skan just strip the remaining pointer tos off the record type 424169689Skan and fall thru to the more precise code. */ 425169689Skan if (TREE_CODE (field_type) == QUAL_UNION_TYPE 426169689Skan || TREE_CODE (field_type) == UNION_TYPE) 427169689Skan { 428169689Skan while (POINTER_TYPE_P (record_type)) 429169689Skan record_type = TYPE_MAIN_VARIANT (TREE_TYPE (record_type)); 430169689Skan break; 431169689Skan } 432169689Skan else 433169689Skan return true; 434169689Skan } 435169689Skan 436169689Skan record_type = get_canon_type (record_type, true, true); 437169689Skan /* The record type must be contained. The field type may 438169689Skan escape. */ 439169689Skan if (!ipa_type_escape_type_contained_p (record_type)) 440169689Skan return false; 441169689Skan 442169689Skan uid = TYPE_UID (record_type); 443169689Skan result = splay_tree_lookup (uid_to_addressof_down_map, (splay_tree_key) uid); 444169689Skan 445169689Skan if (result) 446169689Skan { 447169689Skan bitmap field_type_map = (bitmap) result->value; 448169689Skan uid = get_canon_type_uid (field_type, true, true); 449169689Skan /* If the bit is there, the address was taken. If not, it 450169689Skan wasn't. */ 451169689Skan return !bitmap_bit_p (field_type_map, uid); 452169689Skan } 453169689Skan else 454169689Skan /* No bitmap means no addresses were taken. */ 455169689Skan return true; 456169689Skan} 457169689Skan 458169689Skan 459169689Skan/* Add TYPE to the suspect type set. Return true if the bit needed to 460169689Skan be marked. */ 461169689Skan 462169689Skanstatic tree 463169689Skanmark_type (tree type, enum escape_t escape_status) 464169689Skan{ 465169689Skan bitmap map = NULL; 466169689Skan int uid; 467169689Skan 468169689Skan type = get_canon_type (type, true, true); 469169689Skan if (!type) 470169689Skan return NULL; 471169689Skan 472169689Skan switch (escape_status) 473169689Skan { 474169689Skan case EXPOSED_PARAMETER: 475169689Skan map = global_types_exposed_parameter; 476169689Skan break; 477169689Skan case FULL_ESCAPE: 478169689Skan map = global_types_full_escape; 479169689Skan break; 480169689Skan } 481169689Skan 482169689Skan uid = TYPE_UID (type); 483169689Skan if (bitmap_bit_p (map, uid)) 484169689Skan return type; 485169689Skan else 486169689Skan { 487169689Skan bitmap_set_bit (map, uid); 488169689Skan if (escape_status == FULL_ESCAPE) 489169689Skan { 490169689Skan /* Efficiency hack. When things are bad, do not mess around 491169689Skan with this type anymore. */ 492169689Skan bitmap_set_bit (global_types_exposed_parameter, uid); 493169689Skan } 494169689Skan } 495169689Skan return type; 496169689Skan} 497169689Skan 498169689Skan/* Add interesting TYPE to the suspect type set. If the set is 499169689Skan EXPOSED_PARAMETER and the TYPE is a pointer type, the set is 500169689Skan changed to FULL_ESCAPE. */ 501169689Skan 502169689Skanstatic void 503169689Skanmark_interesting_type (tree type, enum escape_t escape_status) 504169689Skan{ 505169689Skan if (!type) return; 506169689Skan if (ipa_type_escape_star_count_of_interesting_type (type) >= 0) 507169689Skan { 508169689Skan if ((escape_status == EXPOSED_PARAMETER) 509169689Skan && POINTER_TYPE_P (type)) 510169689Skan /* EXPOSED_PARAMETERs are only structs or unions are passed by 511169689Skan value. Anything passed by reference to an external 512169689Skan function fully exposes the type. */ 513169689Skan mark_type (type, FULL_ESCAPE); 514169689Skan else 515169689Skan mark_type (type, escape_status); 516169689Skan } 517169689Skan} 518169689Skan 519169689Skan/* Return true if PARENT is supertype of CHILD. Both types must be 520169689Skan known to be structures or unions. */ 521169689Skan 522169689Skanstatic bool 523169689Skanparent_type_p (tree parent, tree child) 524169689Skan{ 525169689Skan int i; 526169689Skan tree binfo, base_binfo; 527169689Skan if (TYPE_BINFO (parent)) 528169689Skan for (binfo = TYPE_BINFO (parent), i = 0; 529169689Skan BINFO_BASE_ITERATE (binfo, i, base_binfo); i++) 530169689Skan { 531169689Skan tree binfotype = BINFO_TYPE (base_binfo); 532169689Skan if (binfotype == child) 533169689Skan return true; 534169689Skan else if (parent_type_p (binfotype, child)) 535169689Skan return true; 536169689Skan } 537169689Skan if (TREE_CODE (parent) == UNION_TYPE 538169689Skan || TREE_CODE (parent) == QUAL_UNION_TYPE) 539169689Skan { 540169689Skan tree field; 541169689Skan /* Search all of the variants in the union to see if one of them 542169689Skan is the child. */ 543169689Skan for (field = TYPE_FIELDS (parent); 544169689Skan field; 545169689Skan field = TREE_CHAIN (field)) 546169689Skan { 547169689Skan tree field_type; 548169689Skan if (TREE_CODE (field) != FIELD_DECL) 549169689Skan continue; 550169689Skan 551169689Skan field_type = TREE_TYPE (field); 552169689Skan if (field_type == child) 553169689Skan return true; 554169689Skan } 555169689Skan 556169689Skan /* If we did not find it, recursively ask the variants if one of 557169689Skan their children is the child type. */ 558169689Skan for (field = TYPE_FIELDS (parent); 559169689Skan field; 560169689Skan field = TREE_CHAIN (field)) 561169689Skan { 562169689Skan tree field_type; 563169689Skan if (TREE_CODE (field) != FIELD_DECL) 564169689Skan continue; 565169689Skan 566169689Skan field_type = TREE_TYPE (field); 567169689Skan if (TREE_CODE (field_type) == RECORD_TYPE 568169689Skan || TREE_CODE (field_type) == QUAL_UNION_TYPE 569169689Skan || TREE_CODE (field_type) == UNION_TYPE) 570169689Skan if (parent_type_p (field_type, child)) 571169689Skan return true; 572169689Skan } 573169689Skan } 574169689Skan 575169689Skan if (TREE_CODE (parent) == RECORD_TYPE) 576169689Skan { 577169689Skan tree field; 578169689Skan for (field = TYPE_FIELDS (parent); 579169689Skan field; 580169689Skan field = TREE_CHAIN (field)) 581169689Skan { 582169689Skan tree field_type; 583169689Skan if (TREE_CODE (field) != FIELD_DECL) 584169689Skan continue; 585169689Skan 586169689Skan field_type = TREE_TYPE (field); 587169689Skan if (field_type == child) 588169689Skan return true; 589169689Skan /* You can only cast to the first field so if it does not 590169689Skan match, quit. */ 591169689Skan if (TREE_CODE (field_type) == RECORD_TYPE 592169689Skan || TREE_CODE (field_type) == QUAL_UNION_TYPE 593169689Skan || TREE_CODE (field_type) == UNION_TYPE) 594169689Skan { 595169689Skan if (parent_type_p (field_type, child)) 596169689Skan return true; 597169689Skan else 598169689Skan break; 599169689Skan } 600169689Skan } 601169689Skan } 602169689Skan return false; 603169689Skan} 604169689Skan 605169689Skan/* Return the number of pointer tos for TYPE and return TYPE with all 606169689Skan of these stripped off. */ 607169689Skan 608169689Skanstatic int 609169689Skancount_stars (tree* type_ptr) 610169689Skan{ 611169689Skan tree type = *type_ptr; 612169689Skan int i = 0; 613169689Skan type = TYPE_MAIN_VARIANT (type); 614169689Skan while (POINTER_TYPE_P (type)) 615169689Skan { 616169689Skan type = TYPE_MAIN_VARIANT (TREE_TYPE (type)); 617169689Skan i++; 618169689Skan } 619169689Skan 620169689Skan *type_ptr = type; 621169689Skan return i; 622169689Skan} 623169689Skan 624169689Skanenum cast_type { 625169689Skan CT_UP, 626169689Skan CT_DOWN, 627169689Skan CT_SIDEWAYS, 628169689Skan CT_USELESS 629169689Skan}; 630169689Skan 631169689Skan/* Check the cast FROM_TYPE to TO_TYPE. This function requires that 632169689Skan the two types have already passed the 633169689Skan ipa_type_escape_star_count_of_interesting_type test. */ 634169689Skan 635169689Skanstatic enum cast_type 636169689Skancheck_cast_type (tree to_type, tree from_type) 637169689Skan{ 638169689Skan int to_stars = count_stars (&to_type); 639169689Skan int from_stars = count_stars (&from_type); 640169689Skan if (to_stars != from_stars) 641169689Skan return CT_SIDEWAYS; 642169689Skan 643169689Skan if (to_type == from_type) 644169689Skan return CT_USELESS; 645169689Skan 646169689Skan if (parent_type_p (to_type, from_type)) return CT_UP; 647169689Skan if (parent_type_p (from_type, to_type)) return CT_DOWN; 648169689Skan return CT_SIDEWAYS; 649169689Skan} 650169689Skan 651169689Skan/* Check a cast FROM this variable, TO_TYPE. Mark the escaping types 652169689Skan if appropriate. */ 653169689Skanstatic void 654169689Skancheck_cast (tree to_type, tree from) 655169689Skan{ 656169689Skan tree from_type = get_canon_type (TREE_TYPE (from), false, false); 657169689Skan bool to_interesting_type, from_interesting_type; 658169689Skan 659169689Skan to_type = get_canon_type (to_type, false, false); 660169689Skan if (!from_type || !to_type || from_type == to_type) 661169689Skan return; 662169689Skan 663169689Skan to_interesting_type = 664169689Skan ipa_type_escape_star_count_of_interesting_type (to_type) >= 0; 665169689Skan from_interesting_type = 666169689Skan ipa_type_escape_star_count_of_interesting_type (from_type) >= 0; 667169689Skan 668169689Skan if (to_interesting_type) 669169689Skan if (from_interesting_type) 670169689Skan { 671169689Skan /* Both types are interesting. This can be one of four types 672169689Skan of cast: useless, up, down, or sideways. We do not care 673169689Skan about up or useless. Sideways casts are always bad and 674169689Skan both sides get marked as escaping. Downcasts are not 675169689Skan interesting here because if type is marked as escaping, all 676169689Skan of its subtypes escape. */ 677169689Skan switch (check_cast_type (to_type, from_type)) 678169689Skan { 679169689Skan case CT_UP: 680169689Skan case CT_USELESS: 681169689Skan case CT_DOWN: 682169689Skan break; 683169689Skan 684169689Skan case CT_SIDEWAYS: 685169689Skan mark_type (to_type, FULL_ESCAPE); 686169689Skan mark_type (from_type, FULL_ESCAPE); 687169689Skan break; 688169689Skan } 689169689Skan } 690169689Skan else 691169689Skan { 692169689Skan /* If this is a cast from the local that is a result from a 693169689Skan call to malloc, do not mark the cast as bad. */ 694169689Skan if (DECL_P (from) && !bitmap_bit_p (results_of_malloc, DECL_UID (from))) 695169689Skan mark_type (to_type, FULL_ESCAPE); 696169689Skan } 697169689Skan else if (from_interesting_type) 698169689Skan mark_type (from_type, FULL_ESCAPE); 699169689Skan} 700169689Skan 701169689Skan/* Register the parameter and return types of function FN. The type 702169689Skan ESCAPES if the function is visible outside of the compilation 703169689Skan unit. */ 704169689Skanstatic void 705169689Skancheck_function_parameter_and_return_types (tree fn, bool escapes) 706169689Skan{ 707169689Skan tree arg; 708169689Skan 709169689Skan if (TYPE_ARG_TYPES (TREE_TYPE (fn))) 710169689Skan { 711169689Skan for (arg = TYPE_ARG_TYPES (TREE_TYPE (fn)); 712169689Skan arg && TREE_VALUE (arg) != void_type_node; 713169689Skan arg = TREE_CHAIN (arg)) 714169689Skan { 715169689Skan tree type = get_canon_type (TREE_VALUE (arg), false, false); 716169689Skan if (escapes) 717169689Skan mark_interesting_type (type, EXPOSED_PARAMETER); 718169689Skan } 719169689Skan } 720169689Skan else 721169689Skan { 722169689Skan /* FIXME - According to Geoff Keating, we should never have to 723169689Skan do this; the front ends should always process the arg list 724169689Skan from the TYPE_ARG_LIST. However, Geoff is wrong, this code 725169689Skan does seem to be live. */ 726169689Skan 727169689Skan for (arg = DECL_ARGUMENTS (fn); arg; arg = TREE_CHAIN (arg)) 728169689Skan { 729169689Skan tree type = get_canon_type (TREE_TYPE (arg), false, false); 730169689Skan if (escapes) 731169689Skan mark_interesting_type (type, EXPOSED_PARAMETER); 732169689Skan } 733169689Skan } 734169689Skan if (escapes) 735169689Skan { 736169689Skan tree type = get_canon_type (TREE_TYPE (TREE_TYPE (fn)), false, false); 737169689Skan mark_interesting_type (type, EXPOSED_PARAMETER); 738169689Skan } 739169689Skan} 740169689Skan 741169689Skan/* Return true if the variable T is the right kind of static variable to 742169689Skan perform compilation unit scope escape analysis. */ 743169689Skan 744169689Skanstatic inline void 745169689Skanhas_proper_scope_for_analysis (tree t) 746169689Skan{ 747169689Skan /* If the variable has the "used" attribute, treat it as if it had a 748169689Skan been touched by the devil. */ 749169689Skan tree type = get_canon_type (TREE_TYPE (t), false, false); 750169689Skan if (!type) return; 751169689Skan 752169689Skan if (lookup_attribute ("used", DECL_ATTRIBUTES (t))) 753169689Skan { 754169689Skan mark_interesting_type (type, FULL_ESCAPE); 755169689Skan return; 756169689Skan } 757169689Skan 758169689Skan /* Do not want to do anything with volatile except mark any 759169689Skan function that uses one to be not const or pure. */ 760169689Skan if (TREE_THIS_VOLATILE (t)) 761169689Skan return; 762169689Skan 763169689Skan /* Do not care about a local automatic that is not static. */ 764169689Skan if (!TREE_STATIC (t) && !DECL_EXTERNAL (t)) 765169689Skan return; 766169689Skan 767169689Skan if (DECL_EXTERNAL (t) || TREE_PUBLIC (t)) 768169689Skan { 769169689Skan /* If the front end set the variable to be READONLY and 770169689Skan constant, we can allow this variable in pure or const 771169689Skan functions but the scope is too large for our analysis to set 772169689Skan these bits ourselves. */ 773169689Skan 774169689Skan if (TREE_READONLY (t) 775169689Skan && DECL_INITIAL (t) 776169689Skan && is_gimple_min_invariant (DECL_INITIAL (t))) 777169689Skan ; /* Read of a constant, do not change the function state. */ 778169689Skan else 779169689Skan { 780169689Skan /* The type escapes for all public and externs. */ 781169689Skan mark_interesting_type (type, FULL_ESCAPE); 782169689Skan } 783169689Skan } 784169689Skan} 785169689Skan 786169689Skan/* If T is a VAR_DECL for a static that we are interested in, add the 787169689Skan uid to the bitmap. */ 788169689Skan 789169689Skanstatic void 790169689Skancheck_operand (tree t) 791169689Skan{ 792169689Skan if (!t) return; 793169689Skan 794169689Skan /* This is an assignment from a function, register the types as 795169689Skan escaping. */ 796169689Skan if (TREE_CODE (t) == FUNCTION_DECL) 797169689Skan check_function_parameter_and_return_types (t, true); 798169689Skan 799169689Skan else if (TREE_CODE (t) == VAR_DECL) 800169689Skan has_proper_scope_for_analysis (t); 801169689Skan} 802169689Skan 803169689Skan/* Examine tree T for references. */ 804169689Skan 805169689Skanstatic void 806169689Skancheck_tree (tree t) 807169689Skan{ 808169689Skan if ((TREE_CODE (t) == EXC_PTR_EXPR) || (TREE_CODE (t) == FILTER_EXPR)) 809169689Skan return; 810169689Skan 811169689Skan while (TREE_CODE (t) == REALPART_EXPR 812169689Skan || TREE_CODE (t) == IMAGPART_EXPR 813169689Skan || handled_component_p (t)) 814169689Skan { 815169689Skan if (TREE_CODE (t) == ARRAY_REF) 816169689Skan check_operand (TREE_OPERAND (t, 1)); 817169689Skan t = TREE_OPERAND (t, 0); 818169689Skan } 819169689Skan 820169689Skan if (INDIRECT_REF_P (t)) 821169689Skan/* || TREE_CODE (t) == MEM_REF) */ 822169689Skan check_tree (TREE_OPERAND (t, 0)); 823169689Skan 824169689Skan if (SSA_VAR_P (t) || (TREE_CODE (t) == FUNCTION_DECL)) 825169689Skan check_operand (t); 826169689Skan} 827169689Skan 828169689Skan/* Create an address_of edge FROM_TYPE.TO_TYPE. */ 829169689Skanstatic void 830169689Skanmark_interesting_addressof (tree to_type, tree from_type) 831169689Skan{ 832169689Skan int from_uid; 833169689Skan int to_uid; 834169689Skan bitmap type_map; 835169689Skan splay_tree_node result; 836169689Skan 837169689Skan from_type = get_canon_type (from_type, false, false); 838169689Skan to_type = get_canon_type (to_type, false, false); 839169689Skan 840169689Skan if (!from_type || !to_type) 841169689Skan return; 842169689Skan 843169689Skan from_uid = TYPE_UID (from_type); 844169689Skan to_uid = TYPE_UID (to_type); 845169689Skan 846169689Skan gcc_assert (ipa_type_escape_star_count_of_interesting_type (from_type) == 0); 847169689Skan 848169689Skan /* Process the Y into X map pointer. */ 849169689Skan result = splay_tree_lookup (uid_to_addressof_down_map, 850169689Skan (splay_tree_key) from_uid); 851169689Skan 852169689Skan if (result) 853169689Skan type_map = (bitmap) result->value; 854169689Skan else 855169689Skan { 856169689Skan type_map = BITMAP_ALLOC (&ipa_obstack); 857169689Skan splay_tree_insert (uid_to_addressof_down_map, 858169689Skan from_uid, 859169689Skan (splay_tree_value)type_map); 860169689Skan } 861169689Skan bitmap_set_bit (type_map, TYPE_UID (to_type)); 862169689Skan 863169689Skan /* Process the X into Y reverse map pointer. */ 864169689Skan result = 865169689Skan splay_tree_lookup (uid_to_addressof_up_map, (splay_tree_key) to_uid); 866169689Skan 867169689Skan if (result) 868169689Skan type_map = (bitmap) result->value; 869169689Skan else 870169689Skan { 871169689Skan type_map = BITMAP_ALLOC (&ipa_obstack); 872169689Skan splay_tree_insert (uid_to_addressof_up_map, 873169689Skan to_uid, 874169689Skan (splay_tree_value)type_map); 875169689Skan } 876169689Skan bitmap_set_bit (type_map, TYPE_UID (to_type)); 877169689Skan} 878169689Skan 879169689Skan/* Scan tree T to see if there are any addresses taken in within T. */ 880169689Skan 881169689Skanstatic void 882169689Skanlook_for_address_of (tree t) 883169689Skan{ 884169689Skan if (TREE_CODE (t) == ADDR_EXPR) 885169689Skan { 886169689Skan tree x = get_base_var (t); 887169689Skan tree cref = TREE_OPERAND (t, 0); 888169689Skan 889169689Skan /* If we have an expression of the form "&a.b.c.d", mark a.b, 890169689Skan b.c and c.d. as having its address taken. */ 891169689Skan tree fielddecl = NULL_TREE; 892169689Skan while (cref!= x) 893169689Skan { 894169689Skan if (TREE_CODE (cref) == COMPONENT_REF) 895169689Skan { 896169689Skan fielddecl = TREE_OPERAND (cref, 1); 897169689Skan mark_interesting_addressof (TREE_TYPE (fielddecl), 898169689Skan DECL_FIELD_CONTEXT (fielddecl)); 899169689Skan } 900169689Skan else if (TREE_CODE (cref) == ARRAY_REF) 901169689Skan get_canon_type (TREE_TYPE (cref), false, false); 902169689Skan 903169689Skan cref = TREE_OPERAND (cref, 0); 904169689Skan } 905169689Skan 906169689Skan if (TREE_CODE (x) == VAR_DECL) 907169689Skan has_proper_scope_for_analysis (x); 908169689Skan } 909169689Skan} 910169689Skan 911169689Skan 912169689Skan/* Scan tree T to see if there are any casts within it. 913169689Skan LHS Is the LHS of the expression involving the cast. */ 914169689Skan 915169689Skanstatic void 916169689Skanlook_for_casts (tree lhs __attribute__((unused)), tree t) 917169689Skan{ 918169689Skan if (is_gimple_cast (t) || TREE_CODE (t) == VIEW_CONVERT_EXPR) 919169689Skan { 920169689Skan tree castfromvar = TREE_OPERAND (t, 0); 921169689Skan check_cast (TREE_TYPE (t), castfromvar); 922169689Skan } 923169689Skan else if (TREE_CODE (t) == COMPONENT_REF 924169689Skan || TREE_CODE (t) == INDIRECT_REF 925169689Skan || TREE_CODE (t) == BIT_FIELD_REF) 926169689Skan { 927169689Skan tree base = get_base_address (t); 928169689Skan while (t != base) 929169689Skan { 930169689Skan t = TREE_OPERAND (t, 0); 931169689Skan if (TREE_CODE (t) == VIEW_CONVERT_EXPR) 932169689Skan { 933169689Skan /* This may be some part of a component ref. 934169689Skan IE it may be a.b.VIEW_CONVERT_EXPR<weird_type>(c).d, AFAIK. 935169689Skan castfromref will give you a.b.c, not a. */ 936169689Skan tree castfromref = TREE_OPERAND (t, 0); 937169689Skan check_cast (TREE_TYPE (t), castfromref); 938169689Skan } 939169689Skan else if (TREE_CODE (t) == COMPONENT_REF) 940169689Skan get_canon_type (TREE_TYPE (TREE_OPERAND (t, 1)), false, false); 941169689Skan } 942169689Skan } 943169689Skan} 944169689Skan 945169689Skan/* Check to see if T is a read or address of operation on a static var 946169689Skan we are interested in analyzing. */ 947169689Skan 948169689Skanstatic void 949169689Skancheck_rhs_var (tree t) 950169689Skan{ 951169689Skan look_for_address_of (t); 952169689Skan check_tree(t); 953169689Skan} 954169689Skan 955169689Skan/* Check to see if T is an assignment to a static var we are 956169689Skan interested in analyzing. */ 957169689Skan 958169689Skanstatic void 959169689Skancheck_lhs_var (tree t) 960169689Skan{ 961169689Skan check_tree(t); 962169689Skan} 963169689Skan 964169689Skan/* This is a scaled down version of get_asm_expr_operands from 965169689Skan tree_ssa_operands.c. The version there runs much later and assumes 966169689Skan that aliasing information is already available. Here we are just 967169689Skan trying to find if the set of inputs and outputs contain references 968169689Skan or address of operations to local. FN is the function being 969169689Skan analyzed and STMT is the actual asm statement. */ 970169689Skan 971169689Skanstatic void 972169689Skanget_asm_expr_operands (tree stmt) 973169689Skan{ 974169689Skan int noutputs = list_length (ASM_OUTPUTS (stmt)); 975169689Skan const char **oconstraints 976169689Skan = (const char **) alloca ((noutputs) * sizeof (const char *)); 977169689Skan int i; 978169689Skan tree link; 979169689Skan const char *constraint; 980169689Skan bool allows_mem, allows_reg, is_inout; 981169689Skan 982169689Skan for (i=0, link = ASM_OUTPUTS (stmt); link; ++i, link = TREE_CHAIN (link)) 983169689Skan { 984169689Skan oconstraints[i] = constraint 985169689Skan = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link))); 986169689Skan parse_output_constraint (&constraint, i, 0, 0, 987169689Skan &allows_mem, &allows_reg, &is_inout); 988169689Skan 989169689Skan check_lhs_var (TREE_VALUE (link)); 990169689Skan } 991169689Skan 992169689Skan for (link = ASM_INPUTS (stmt); link; link = TREE_CHAIN (link)) 993169689Skan { 994169689Skan constraint 995169689Skan = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link))); 996169689Skan parse_input_constraint (&constraint, 0, 0, noutputs, 0, 997169689Skan oconstraints, &allows_mem, &allows_reg); 998169689Skan 999169689Skan check_rhs_var (TREE_VALUE (link)); 1000169689Skan } 1001169689Skan 1002169689Skan /* There is no code here to check for asm memory clobbers. The 1003169689Skan casual maintainer might think that such code would be necessary, 1004169689Skan but that appears to be wrong. In other parts of the compiler, 1005169689Skan the asm memory clobbers are assumed to only clobber variables 1006169689Skan that are addressable. All types with addressable instances are 1007169689Skan assumed to already escape. So, we are protected here. */ 1008169689Skan} 1009169689Skan 1010169689Skan/* Check the parameters of a function call to CALL_EXPR to mark the 1011169689Skan types that pass across the function boundary. Also check to see if 1012169689Skan this is either an indirect call, a call outside the compilation 1013169689Skan unit. */ 1014169689Skan 1015169689Skanstatic bool 1016169689Skancheck_call (tree call_expr) 1017169689Skan{ 1018169689Skan int flags = call_expr_flags(call_expr); 1019169689Skan tree operand_list = TREE_OPERAND (call_expr, 1); 1020169689Skan tree operand; 1021169689Skan tree callee_t = get_callee_fndecl (call_expr); 1022169689Skan tree argument; 1023169689Skan struct cgraph_node* callee; 1024169689Skan enum availability avail = AVAIL_NOT_AVAILABLE; 1025169689Skan 1026169689Skan for (operand = operand_list; 1027169689Skan operand != NULL_TREE; 1028169689Skan operand = TREE_CHAIN (operand)) 1029169689Skan { 1030169689Skan tree argument = TREE_VALUE (operand); 1031169689Skan check_rhs_var (argument); 1032169689Skan } 1033169689Skan 1034169689Skan if (callee_t) 1035169689Skan { 1036169689Skan tree arg_type; 1037169689Skan tree last_arg_type = NULL; 1038169689Skan callee = cgraph_node(callee_t); 1039169689Skan avail = cgraph_function_body_availability (callee); 1040169689Skan 1041169689Skan /* Check that there are no implicit casts in the passing of 1042169689Skan parameters. */ 1043169689Skan if (TYPE_ARG_TYPES (TREE_TYPE (callee_t))) 1044169689Skan { 1045169689Skan operand = operand_list; 1046169689Skan for (arg_type = TYPE_ARG_TYPES (TREE_TYPE (callee_t)); 1047169689Skan arg_type && TREE_VALUE (arg_type) != void_type_node; 1048169689Skan arg_type = TREE_CHAIN (arg_type)) 1049169689Skan { 1050169689Skan if (operand) 1051169689Skan { 1052169689Skan argument = TREE_VALUE (operand); 1053169689Skan last_arg_type = TREE_VALUE(arg_type); 1054169689Skan check_cast (last_arg_type, argument); 1055169689Skan operand = TREE_CHAIN (operand); 1056169689Skan } 1057169689Skan else 1058169689Skan /* The code reaches here for some unfortunate 1059169689Skan builtin functions that do not have a list of 1060169689Skan argument types. */ 1061169689Skan break; 1062169689Skan } 1063169689Skan } 1064169689Skan else 1065169689Skan { 1066169689Skan /* FIXME - According to Geoff Keating, we should never 1067169689Skan have to do this; the front ends should always process 1068169689Skan the arg list from the TYPE_ARG_LIST. */ 1069169689Skan operand = operand_list; 1070169689Skan for (arg_type = DECL_ARGUMENTS (callee_t); 1071169689Skan arg_type; 1072169689Skan arg_type = TREE_CHAIN (arg_type)) 1073169689Skan { 1074169689Skan if (operand) 1075169689Skan { 1076169689Skan argument = TREE_VALUE (operand); 1077169689Skan last_arg_type = TREE_TYPE(arg_type); 1078169689Skan check_cast (last_arg_type, argument); 1079169689Skan operand = TREE_CHAIN (operand); 1080169689Skan } 1081169689Skan else 1082169689Skan /* The code reaches here for some unfortunate 1083169689Skan builtin functions that do not have a list of 1084169689Skan argument types. */ 1085169689Skan break; 1086169689Skan } 1087169689Skan } 1088169689Skan 1089169689Skan /* In the case where we have a var_args function, we need to 1090169689Skan check the remaining parameters against the last argument. */ 1091169689Skan arg_type = last_arg_type; 1092169689Skan for (; 1093169689Skan operand != NULL_TREE; 1094169689Skan operand = TREE_CHAIN (operand)) 1095169689Skan { 1096169689Skan argument = TREE_VALUE (operand); 1097169689Skan if (arg_type) 1098169689Skan check_cast (arg_type, argument); 1099169689Skan else 1100169689Skan { 1101169689Skan /* The code reaches here for some unfortunate 1102169689Skan builtin functions that do not have a list of 1103169689Skan argument types. Most of these functions have 1104169689Skan been marked as having their parameters not 1105169689Skan escape, but for the rest, the type is doomed. */ 1106169689Skan tree type = get_canon_type (TREE_TYPE (argument), false, false); 1107169689Skan mark_interesting_type (type, FULL_ESCAPE); 1108169689Skan } 1109169689Skan } 1110169689Skan } 1111169689Skan 1112169689Skan /* The callee is either unknown (indirect call) or there is just no 1113169689Skan scannable code for it (external call) . We look to see if there 1114169689Skan are any bits available for the callee (such as by declaration or 1115169689Skan because it is builtin) and process solely on the basis of those 1116169689Skan bits. */ 1117169689Skan 1118169689Skan if (avail == AVAIL_NOT_AVAILABLE || avail == AVAIL_OVERWRITABLE) 1119169689Skan { 1120169689Skan /* If this is a direct call to an external function, mark all of 1121169689Skan the parameter and return types. */ 1122169689Skan for (operand = operand_list; 1123169689Skan operand != NULL_TREE; 1124169689Skan operand = TREE_CHAIN (operand)) 1125169689Skan { 1126169689Skan tree type = 1127169689Skan get_canon_type (TREE_TYPE (TREE_VALUE (operand)), false, false); 1128169689Skan mark_interesting_type (type, EXPOSED_PARAMETER); 1129169689Skan } 1130169689Skan 1131169689Skan if (callee_t) 1132169689Skan { 1133169689Skan tree type = 1134169689Skan get_canon_type (TREE_TYPE (TREE_TYPE (callee_t)), false, false); 1135169689Skan mark_interesting_type (type, EXPOSED_PARAMETER); 1136169689Skan } 1137169689Skan } 1138169689Skan return (flags & ECF_MALLOC); 1139169689Skan} 1140169689Skan 1141169689Skan/* CODE is the operation on OP0 and OP1. OP0 is the operand that we 1142169689Skan *know* is a pointer type. OP1 may be a pointer type. */ 1143169689Skanstatic bool 1144169689Skanokay_pointer_operation (enum tree_code code, tree op0, tree op1) 1145169689Skan{ 1146169689Skan tree op0type = TYPE_MAIN_VARIANT (TREE_TYPE (op0)); 1147169689Skan tree op1type = TYPE_MAIN_VARIANT (TREE_TYPE (op1)); 1148169689Skan if (POINTER_TYPE_P (op1type)) 1149169689Skan return false; 1150169689Skan switch (code) 1151169689Skan { 1152169689Skan case MULT_EXPR: 1153169689Skan case PLUS_EXPR: 1154169689Skan case MINUS_EXPR: 1155169689Skan /* TODO: Handle multiples of op0 size as well */ 1156169689Skan if (operand_equal_p (size_in_bytes (op0type), op1, 0)) 1157169689Skan return true; 1158169689Skan /* fallthrough */ 1159169689Skan 1160169689Skan default: 1161169689Skan return false; 1162169689Skan } 1163169689Skan return false; 1164169689Skan} 1165169689Skan 1166169689Skan/* TP is the part of the tree currently under the microscope. 1167169689Skan WALK_SUBTREES is part of the walk_tree api but is unused here. 1168169689Skan DATA is cgraph_node of the function being walked. */ 1169169689Skan 1170169689Skan/* FIXME: When this is converted to run over SSA form, this code 1171169689Skan should be converted to use the operand scanner. */ 1172169689Skan 1173169689Skanstatic tree 1174169689Skanscan_for_refs (tree *tp, int *walk_subtrees, void *data) 1175169689Skan{ 1176169689Skan struct cgraph_node *fn = data; 1177169689Skan tree t = *tp; 1178169689Skan 1179169689Skan switch (TREE_CODE (t)) 1180169689Skan { 1181169689Skan case VAR_DECL: 1182169689Skan if (DECL_INITIAL (t)) 1183169689Skan walk_tree (&DECL_INITIAL (t), scan_for_refs, fn, visited_nodes); 1184169689Skan *walk_subtrees = 0; 1185169689Skan break; 1186169689Skan 1187169689Skan case MODIFY_EXPR: 1188169689Skan { 1189169689Skan /* First look on the lhs and see what variable is stored to */ 1190169689Skan tree lhs = TREE_OPERAND (t, 0); 1191169689Skan tree rhs = TREE_OPERAND (t, 1); 1192169689Skan 1193169689Skan check_lhs_var (lhs); 1194169689Skan check_cast (TREE_TYPE (lhs), rhs); 1195169689Skan 1196169689Skan /* For the purposes of figuring out what the cast affects */ 1197169689Skan 1198169689Skan /* Next check the operands on the rhs to see if they are ok. */ 1199169689Skan switch (TREE_CODE_CLASS (TREE_CODE (rhs))) 1200169689Skan { 1201169689Skan case tcc_binary: 1202169689Skan { 1203169689Skan tree op0 = TREE_OPERAND (rhs, 0); 1204169689Skan tree type0 = get_canon_type (TREE_TYPE (op0), false, false); 1205169689Skan tree op1 = TREE_OPERAND (rhs, 1); 1206169689Skan tree type1 = get_canon_type (TREE_TYPE (op1), false, false); 1207169689Skan 1208169689Skan /* If this is pointer arithmetic of any bad sort, then 1209169689Skan we need to mark the types as bad. For binary 1210169689Skan operations, no binary operator we currently support 1211169689Skan is always "safe" in regard to what it would do to 1212169689Skan pointers for purposes of determining which types 1213169689Skan escape, except operations of the size of the type. 1214169689Skan It is possible that min and max under the right set 1215169689Skan of circumstances and if the moon is in the correct 1216169689Skan place could be safe, but it is hard to see how this 1217169689Skan is worth the effort. */ 1218169689Skan 1219169689Skan if (type0 && POINTER_TYPE_P (type0) 1220169689Skan && !okay_pointer_operation (TREE_CODE (rhs), op0, op1)) 1221169689Skan mark_interesting_type (type0, FULL_ESCAPE); 1222169689Skan if (type1 && POINTER_TYPE_P (type1) 1223169689Skan && !okay_pointer_operation (TREE_CODE (rhs), op1, op0)) 1224169689Skan mark_interesting_type (type1, FULL_ESCAPE); 1225169689Skan 1226169689Skan look_for_casts (lhs, op0); 1227169689Skan look_for_casts (lhs, op1); 1228169689Skan check_rhs_var (op0); 1229169689Skan check_rhs_var (op1); 1230169689Skan } 1231169689Skan break; 1232169689Skan case tcc_unary: 1233169689Skan { 1234169689Skan tree op0 = TREE_OPERAND (rhs, 0); 1235169689Skan tree type0 = get_canon_type (TREE_TYPE (op0), false, false); 1236169689Skan /* For unary operations, if the operation is NEGATE or 1237169689Skan ABS on a pointer, this is also considered pointer 1238169689Skan arithmetic and thus, bad for business. */ 1239169689Skan if (type0 && (TREE_CODE (op0) == NEGATE_EXPR 1240169689Skan || TREE_CODE (op0) == ABS_EXPR) 1241169689Skan && POINTER_TYPE_P (type0)) 1242169689Skan { 1243169689Skan mark_interesting_type (type0, FULL_ESCAPE); 1244169689Skan } 1245169689Skan check_rhs_var (op0); 1246169689Skan look_for_casts (lhs, op0); 1247169689Skan look_for_casts (lhs, rhs); 1248169689Skan } 1249169689Skan 1250169689Skan break; 1251169689Skan case tcc_reference: 1252169689Skan look_for_casts (lhs, rhs); 1253169689Skan check_rhs_var (rhs); 1254169689Skan break; 1255169689Skan case tcc_declaration: 1256169689Skan check_rhs_var (rhs); 1257169689Skan break; 1258169689Skan case tcc_expression: 1259169689Skan switch (TREE_CODE (rhs)) 1260169689Skan { 1261169689Skan case ADDR_EXPR: 1262169689Skan look_for_casts (lhs, TREE_OPERAND (rhs, 0)); 1263169689Skan check_rhs_var (rhs); 1264169689Skan break; 1265169689Skan case CALL_EXPR: 1266169689Skan /* If this is a call to malloc, squirrel away the 1267169689Skan result so we do mark the resulting cast as being 1268169689Skan bad. */ 1269169689Skan if (check_call (rhs)) 1270169689Skan bitmap_set_bit (results_of_malloc, DECL_UID (lhs)); 1271169689Skan break; 1272169689Skan default: 1273169689Skan break; 1274169689Skan } 1275169689Skan break; 1276169689Skan default: 1277169689Skan break; 1278169689Skan } 1279169689Skan *walk_subtrees = 0; 1280169689Skan } 1281169689Skan break; 1282169689Skan 1283169689Skan case ADDR_EXPR: 1284169689Skan /* This case is here to find addresses on rhs of constructors in 1285169689Skan decl_initial of static variables. */ 1286169689Skan check_rhs_var (t); 1287169689Skan *walk_subtrees = 0; 1288169689Skan break; 1289169689Skan 1290169689Skan case CALL_EXPR: 1291169689Skan check_call (t); 1292169689Skan *walk_subtrees = 0; 1293169689Skan break; 1294169689Skan 1295169689Skan case ASM_EXPR: 1296169689Skan get_asm_expr_operands (t); 1297169689Skan *walk_subtrees = 0; 1298169689Skan break; 1299169689Skan 1300169689Skan default: 1301169689Skan break; 1302169689Skan } 1303169689Skan return NULL; 1304169689Skan} 1305169689Skan 1306169689Skan 1307169689Skan/* The init routine for analyzing global static variable usage. See 1308169689Skan comments at top for description. */ 1309169689Skanstatic void 1310169689Skanipa_init (void) 1311169689Skan{ 1312169689Skan bitmap_obstack_initialize (&ipa_obstack); 1313169689Skan global_types_exposed_parameter = BITMAP_ALLOC (&ipa_obstack); 1314169689Skan global_types_full_escape = BITMAP_ALLOC (&ipa_obstack); 1315169689Skan global_types_seen = BITMAP_ALLOC (&ipa_obstack); 1316169689Skan results_of_malloc = BITMAP_ALLOC (&ipa_obstack); 1317169689Skan 1318169689Skan uid_to_canon_type = splay_tree_new (splay_tree_compare_ints, 0, 0); 1319169689Skan all_canon_types = splay_tree_new (compare_type_brand, 0, 0); 1320169689Skan type_to_canon_type = splay_tree_new (splay_tree_compare_pointers, 0, 0); 1321169689Skan uid_to_subtype_map = splay_tree_new (splay_tree_compare_ints, 0, 0); 1322169689Skan uid_to_addressof_down_map = splay_tree_new (splay_tree_compare_ints, 0, 0); 1323169689Skan uid_to_addressof_up_map = splay_tree_new (splay_tree_compare_ints, 0, 0); 1324169689Skan 1325169689Skan /* There are some shared nodes, in particular the initializers on 1326169689Skan static declarations. We do not need to scan them more than once 1327169689Skan since all we would be interested in are the addressof 1328169689Skan operations. */ 1329169689Skan visited_nodes = pointer_set_create (); 1330169689Skan initialized = true; 1331169689Skan} 1332169689Skan 1333169689Skan/* Check out the rhs of a static or global initialization VNODE to see 1334169689Skan if any of them contain addressof operations. Note that some of 1335169689Skan these variables may not even be referenced in the code in this 1336169689Skan compilation unit but their right hand sides may contain references 1337169689Skan to variables defined within this unit. */ 1338169689Skan 1339169689Skanstatic void 1340169689Skananalyze_variable (struct cgraph_varpool_node *vnode) 1341169689Skan{ 1342169689Skan tree global = vnode->decl; 1343169689Skan tree type = get_canon_type (TREE_TYPE (global), false, false); 1344169689Skan 1345169689Skan /* If this variable has exposure beyond the compilation unit, add 1346169689Skan its type to the global types. */ 1347169689Skan 1348169689Skan if (vnode->externally_visible) 1349169689Skan mark_interesting_type (type, FULL_ESCAPE); 1350169689Skan 1351169689Skan gcc_assert (TREE_CODE (global) == VAR_DECL); 1352169689Skan 1353169689Skan if (DECL_INITIAL (global)) 1354169689Skan walk_tree (&DECL_INITIAL (global), scan_for_refs, NULL, visited_nodes); 1355169689Skan} 1356169689Skan 1357169689Skan/* This is the main routine for finding the reference patterns for 1358169689Skan global variables within a function FN. */ 1359169689Skan 1360169689Skanstatic void 1361169689Skananalyze_function (struct cgraph_node *fn) 1362169689Skan{ 1363169689Skan tree decl = fn->decl; 1364169689Skan check_function_parameter_and_return_types (decl, 1365169689Skan fn->local.externally_visible); 1366169689Skan if (dump_file) 1367169689Skan fprintf (dump_file, "\n local analysis of %s", cgraph_node_name (fn)); 1368169689Skan 1369169689Skan { 1370169689Skan struct function *this_cfun = DECL_STRUCT_FUNCTION (decl); 1371169689Skan basic_block this_block; 1372169689Skan 1373169689Skan FOR_EACH_BB_FN (this_block, this_cfun) 1374169689Skan { 1375169689Skan block_stmt_iterator bsi; 1376169689Skan for (bsi = bsi_start (this_block); !bsi_end_p (bsi); bsi_next (&bsi)) 1377169689Skan walk_tree (bsi_stmt_ptr (bsi), scan_for_refs, 1378169689Skan fn, visited_nodes); 1379169689Skan } 1380169689Skan } 1381169689Skan 1382169689Skan /* There may be const decls with interesting right hand sides. */ 1383169689Skan if (DECL_STRUCT_FUNCTION (decl)) 1384169689Skan { 1385169689Skan tree step; 1386169689Skan for (step = DECL_STRUCT_FUNCTION (decl)->unexpanded_var_list; 1387169689Skan step; 1388169689Skan step = TREE_CHAIN (step)) 1389169689Skan { 1390169689Skan tree var = TREE_VALUE (step); 1391169689Skan if (TREE_CODE (var) == VAR_DECL 1392169689Skan && DECL_INITIAL (var) 1393169689Skan && !TREE_STATIC (var)) 1394169689Skan walk_tree (&DECL_INITIAL (var), scan_for_refs, 1395169689Skan fn, visited_nodes); 1396169689Skan get_canon_type (TREE_TYPE (var), false, false); 1397169689Skan } 1398169689Skan } 1399169689Skan} 1400169689Skan 1401169689Skan 1402169689Skan 1403169689Skan/* Convert a type_UID into a type. */ 1404169689Skanstatic tree 1405169689Skantype_for_uid (int uid) 1406169689Skan{ 1407169689Skan splay_tree_node result = 1408169689Skan splay_tree_lookup (uid_to_canon_type, (splay_tree_key) uid); 1409169689Skan 1410169689Skan if (result) 1411169689Skan return (tree) result->value; 1412169689Skan else return NULL; 1413169689Skan} 1414169689Skan 1415169689Skan/* Return the a bitmap with the subtypes of the type for UID. If it 1416169689Skan does not exist, return either NULL or a new bitmap depending on the 1417169689Skan value of CREATE. */ 1418169689Skan 1419169689Skanstatic bitmap 1420169689Skansubtype_map_for_uid (int uid, bool create) 1421169689Skan{ 1422169689Skan splay_tree_node result = splay_tree_lookup (uid_to_subtype_map, 1423169689Skan (splay_tree_key) uid); 1424169689Skan 1425169689Skan if (result) 1426169689Skan return (bitmap) result->value; 1427169689Skan else if (create) 1428169689Skan { 1429169689Skan bitmap subtype_map = BITMAP_ALLOC (&ipa_obstack); 1430169689Skan splay_tree_insert (uid_to_subtype_map, 1431169689Skan uid, 1432169689Skan (splay_tree_value)subtype_map); 1433169689Skan return subtype_map; 1434169689Skan } 1435169689Skan else return NULL; 1436169689Skan} 1437169689Skan 1438169689Skan/* Mark all of the supertypes and field types of TYPE as being seen. 1439169689Skan Also accumulate the subtypes for each type so that 1440169689Skan close_types_full_escape can mark a subtype as escaping if the 1441169689Skan supertype escapes. */ 1442169689Skan 1443169689Skanstatic void 1444169689Skanclose_type_seen (tree type) 1445169689Skan{ 1446169689Skan tree field; 1447169689Skan int i, uid; 1448169689Skan tree binfo, base_binfo; 1449169689Skan 1450169689Skan /* See thru all pointer tos and array ofs. */ 1451169689Skan type = get_canon_type (type, true, true); 1452169689Skan if (!type) 1453169689Skan return; 1454169689Skan 1455169689Skan uid = TYPE_UID (type); 1456169689Skan 1457169689Skan if (bitmap_bit_p (been_there_done_that, uid)) 1458169689Skan return; 1459169689Skan bitmap_set_bit (been_there_done_that, uid); 1460169689Skan 1461169689Skan /* If we are doing a language with a type hierarchy, mark all of 1462169689Skan the superclasses. */ 1463169689Skan if (TYPE_BINFO (type)) 1464169689Skan for (binfo = TYPE_BINFO (type), i = 0; 1465169689Skan BINFO_BASE_ITERATE (binfo, i, base_binfo); i++) 1466169689Skan { 1467169689Skan tree binfo_type = BINFO_TYPE (base_binfo); 1468169689Skan bitmap subtype_map = subtype_map_for_uid 1469169689Skan (TYPE_UID (TYPE_MAIN_VARIANT (binfo_type)), true); 1470169689Skan bitmap_set_bit (subtype_map, uid); 1471169689Skan close_type_seen (get_canon_type (binfo_type, true, true)); 1472169689Skan } 1473169689Skan 1474169689Skan /* If the field is a struct or union type, mark all of the 1475169689Skan subfields. */ 1476169689Skan for (field = TYPE_FIELDS (type); 1477169689Skan field; 1478169689Skan field = TREE_CHAIN (field)) 1479169689Skan { 1480169689Skan tree field_type; 1481169689Skan if (TREE_CODE (field) != FIELD_DECL) 1482169689Skan continue; 1483169689Skan 1484169689Skan field_type = TREE_TYPE (field); 1485169689Skan if (ipa_type_escape_star_count_of_interesting_or_array_type (field_type) >= 0) 1486169689Skan close_type_seen (get_canon_type (field_type, true, true)); 1487169689Skan } 1488169689Skan} 1489169689Skan 1490169689Skan/* Take a TYPE that has been passed by value to an external function 1491169689Skan and mark all of the fields that have pointer types as escaping. For 1492169689Skan any of the non pointer types that are structures or unions, 1493169689Skan recurse. TYPE is never a pointer type. */ 1494169689Skan 1495169689Skanstatic void 1496169689Skanclose_type_exposed_parameter (tree type) 1497169689Skan{ 1498169689Skan tree field; 1499169689Skan int uid; 1500169689Skan 1501169689Skan type = get_canon_type (type, false, false); 1502169689Skan if (!type) 1503169689Skan return; 1504169689Skan uid = TYPE_UID (type); 1505169689Skan gcc_assert (!POINTER_TYPE_P (type)); 1506169689Skan 1507169689Skan if (bitmap_bit_p (been_there_done_that, uid)) 1508169689Skan return; 1509169689Skan bitmap_set_bit (been_there_done_that, uid); 1510169689Skan 1511169689Skan /* If the field is a struct or union type, mark all of the 1512169689Skan subfields. */ 1513169689Skan for (field = TYPE_FIELDS (type); 1514169689Skan field; 1515169689Skan field = TREE_CHAIN (field)) 1516169689Skan { 1517169689Skan tree field_type; 1518169689Skan 1519169689Skan if (TREE_CODE (field) != FIELD_DECL) 1520169689Skan continue; 1521169689Skan 1522169689Skan field_type = get_canon_type (TREE_TYPE (field), false, false); 1523169689Skan mark_interesting_type (field_type, EXPOSED_PARAMETER); 1524169689Skan 1525169689Skan /* Only recurse for non pointer types of structures and unions. */ 1526169689Skan if (ipa_type_escape_star_count_of_interesting_type (field_type) == 0) 1527169689Skan close_type_exposed_parameter (field_type); 1528169689Skan } 1529169689Skan} 1530169689Skan 1531169689Skan/* The next function handles the case where a type fully escapes. 1532169689Skan This means that not only does the type itself escape, 1533169689Skan 1534169689Skan a) the type of every field recursively escapes 1535169689Skan b) the type of every subtype escapes as well as the super as well 1536169689Skan as all of the pointer to types for each field. 1537169689Skan 1538169689Skan Note that pointer to types are not marked as escaping. If the 1539169689Skan pointed to type escapes, the pointer to type also escapes. 1540169689Skan 1541169689Skan Take a TYPE that has had the address taken for an instance of it 1542169689Skan and mark all of the types for its fields as having their addresses 1543169689Skan taken. */ 1544169689Skan 1545169689Skanstatic void 1546169689Skanclose_type_full_escape (tree type) 1547169689Skan{ 1548169689Skan tree field; 1549169689Skan unsigned int i; 1550169689Skan int uid; 1551169689Skan tree binfo, base_binfo; 1552169689Skan bitmap_iterator bi; 1553169689Skan bitmap subtype_map; 1554169689Skan splay_tree_node address_result; 1555169689Skan 1556169689Skan /* Strip off any pointer or array types. */ 1557169689Skan type = get_canon_type (type, true, true); 1558169689Skan if (!type) 1559169689Skan return; 1560169689Skan uid = TYPE_UID (type); 1561169689Skan 1562169689Skan if (bitmap_bit_p (been_there_done_that, uid)) 1563169689Skan return; 1564169689Skan bitmap_set_bit (been_there_done_that, uid); 1565169689Skan 1566169689Skan subtype_map = subtype_map_for_uid (uid, false); 1567169689Skan 1568169689Skan /* If we are doing a language with a type hierarchy, mark all of 1569169689Skan the superclasses. */ 1570169689Skan if (TYPE_BINFO (type)) 1571169689Skan for (binfo = TYPE_BINFO (type), i = 0; 1572169689Skan BINFO_BASE_ITERATE (binfo, i, base_binfo); i++) 1573169689Skan { 1574169689Skan tree binfotype = BINFO_TYPE (base_binfo); 1575169689Skan binfotype = mark_type (binfotype, FULL_ESCAPE); 1576169689Skan close_type_full_escape (binfotype); 1577169689Skan } 1578169689Skan 1579169689Skan /* Mark as escaped any types that have been down casted to 1580169689Skan this type. */ 1581169689Skan if (subtype_map) 1582169689Skan EXECUTE_IF_SET_IN_BITMAP (subtype_map, 0, i, bi) 1583169689Skan { 1584169689Skan tree subtype = type_for_uid (i); 1585169689Skan subtype = mark_type (subtype, FULL_ESCAPE); 1586169689Skan close_type_full_escape (subtype); 1587169689Skan } 1588169689Skan 1589169689Skan /* If the field is a struct or union type, mark all of the 1590169689Skan subfields. */ 1591169689Skan for (field = TYPE_FIELDS (type); 1592169689Skan field; 1593169689Skan field = TREE_CHAIN (field)) 1594169689Skan { 1595169689Skan tree field_type; 1596169689Skan if (TREE_CODE (field) != FIELD_DECL) 1597169689Skan continue; 1598169689Skan 1599169689Skan field_type = TREE_TYPE (field); 1600169689Skan if (ipa_type_escape_star_count_of_interesting_or_array_type (field_type) >= 0) 1601169689Skan { 1602169689Skan field_type = mark_type (field_type, FULL_ESCAPE); 1603169689Skan close_type_full_escape (field_type); 1604169689Skan } 1605169689Skan } 1606169689Skan 1607169689Skan /* For all of the types A that contain this type B and were part of 1608169689Skan an expression like "&...A.B...", mark the A's as escaping. */ 1609169689Skan address_result = splay_tree_lookup (uid_to_addressof_up_map, 1610169689Skan (splay_tree_key) uid); 1611169689Skan if (address_result) 1612169689Skan { 1613169689Skan bitmap containing_classes = (bitmap) address_result->value; 1614169689Skan EXECUTE_IF_SET_IN_BITMAP (containing_classes, 0, i, bi) 1615169689Skan { 1616169689Skan close_type_full_escape (type_for_uid (i)); 1617169689Skan } 1618169689Skan } 1619169689Skan} 1620169689Skan 1621169689Skan/* Transitively close the addressof bitmap for the type with UID. 1622169689Skan This means that if we had a.b and b.c, a would have both b and c in 1623169689Skan its maps. */ 1624169689Skan 1625169689Skanstatic bitmap 1626169689Skanclose_addressof_down (int uid) 1627169689Skan{ 1628169689Skan bitmap_iterator bi; 1629169689Skan splay_tree_node result = 1630169689Skan splay_tree_lookup (uid_to_addressof_down_map, (splay_tree_key) uid); 1631169689Skan bitmap map = NULL; 1632169689Skan bitmap new_map; 1633169689Skan unsigned int i; 1634169689Skan 1635169689Skan if (result) 1636169689Skan map = (bitmap) result->value; 1637169689Skan else 1638169689Skan return NULL; 1639169689Skan 1640169689Skan if (bitmap_bit_p (been_there_done_that, uid)) 1641169689Skan return map; 1642169689Skan bitmap_set_bit (been_there_done_that, uid); 1643169689Skan 1644169689Skan /* If the type escapes, get rid of the addressof map, it will not be 1645169689Skan needed. */ 1646169689Skan if (bitmap_bit_p (global_types_full_escape, uid)) 1647169689Skan { 1648169689Skan BITMAP_FREE (map); 1649169689Skan splay_tree_remove (uid_to_addressof_down_map, (splay_tree_key) uid); 1650169689Skan return NULL; 1651169689Skan } 1652169689Skan 1653169689Skan /* The new_map will have all of the bits for the enclosed fields and 1654169689Skan will have the unique id version of the old map. */ 1655169689Skan new_map = BITMAP_ALLOC (&ipa_obstack); 1656169689Skan 1657169689Skan EXECUTE_IF_SET_IN_BITMAP (map, 0, i, bi) 1658169689Skan { 1659169689Skan bitmap submap = close_addressof_down (i); 1660169689Skan bitmap_set_bit (new_map, i); 1661169689Skan if (submap) 1662169689Skan bitmap_ior_into (new_map, submap); 1663169689Skan } 1664169689Skan result->value = (splay_tree_value) new_map; 1665169689Skan 1666169689Skan BITMAP_FREE (map); 1667169689Skan return new_map; 1668169689Skan} 1669169689Skan 1670169689Skan 1671169689Skan/* The main entry point for type escape analysis. */ 1672169689Skan 1673169689Skanstatic unsigned int 1674169689Skantype_escape_execute (void) 1675169689Skan{ 1676169689Skan struct cgraph_node *node; 1677169689Skan struct cgraph_varpool_node *vnode; 1678169689Skan unsigned int i; 1679169689Skan bitmap_iterator bi; 1680169689Skan splay_tree_node result; 1681169689Skan 1682169689Skan ipa_init (); 1683169689Skan 1684169689Skan /* Process all of the variables first. */ 1685169689Skan for (vnode = cgraph_varpool_nodes_queue; vnode; vnode = vnode->next_needed) 1686169689Skan analyze_variable (vnode); 1687169689Skan 1688169689Skan /* Process all of the functions. next 1689169689Skan 1690169689Skan We do not want to process any of the clones so we check that this 1691169689Skan is a master clone. However, we do need to process any 1692169689Skan AVAIL_OVERWRITABLE functions (these are never clones) because 1693169689Skan they may cause a type variable to escape. 1694169689Skan */ 1695169689Skan for (node = cgraph_nodes; node; node = node->next) 1696169689Skan if (node->analyzed 1697169689Skan && (cgraph_is_master_clone (node) 1698169689Skan || (cgraph_function_body_availability (node) == AVAIL_OVERWRITABLE))) 1699169689Skan analyze_function (node); 1700169689Skan 1701169689Skan 1702169689Skan pointer_set_destroy (visited_nodes); 1703169689Skan visited_nodes = NULL; 1704169689Skan 1705169689Skan /* Do all of the closures to discover which types escape the 1706169689Skan compilation unit. */ 1707169689Skan 1708169689Skan been_there_done_that = BITMAP_ALLOC (&ipa_obstack); 1709169689Skan bitmap_tmp = BITMAP_ALLOC (&ipa_obstack); 1710169689Skan 1711169689Skan /* Examine the types that we have directly seen in scanning the code 1712169689Skan and add to that any contained types or superclasses. */ 1713169689Skan 1714169689Skan bitmap_copy (bitmap_tmp, global_types_seen); 1715169689Skan EXECUTE_IF_SET_IN_BITMAP (bitmap_tmp, 0, i, bi) 1716169689Skan { 1717169689Skan tree type = type_for_uid (i); 1718169689Skan /* Only look at records and unions and pointer tos. */ 1719169689Skan if (ipa_type_escape_star_count_of_interesting_or_array_type (type) >= 0) 1720169689Skan close_type_seen (type); 1721169689Skan } 1722169689Skan bitmap_clear (been_there_done_that); 1723169689Skan 1724169689Skan /* Examine all of the types passed by value and mark any enclosed 1725169689Skan pointer types as escaping. */ 1726169689Skan bitmap_copy (bitmap_tmp, global_types_exposed_parameter); 1727169689Skan EXECUTE_IF_SET_IN_BITMAP (bitmap_tmp, 0, i, bi) 1728169689Skan { 1729169689Skan close_type_exposed_parameter (type_for_uid (i)); 1730169689Skan } 1731169689Skan bitmap_clear (been_there_done_that); 1732169689Skan 1733169689Skan /* Close the types for escape. If something escapes, then any 1734169689Skan enclosed types escape as well as any subtypes. */ 1735169689Skan bitmap_copy (bitmap_tmp, global_types_full_escape); 1736169689Skan EXECUTE_IF_SET_IN_BITMAP (bitmap_tmp, 0, i, bi) 1737169689Skan { 1738169689Skan close_type_full_escape (type_for_uid (i)); 1739169689Skan } 1740169689Skan bitmap_clear (been_there_done_that); 1741169689Skan 1742169689Skan /* Before this pass, the uid_to_addressof_down_map for type X 1743169689Skan contained an entry for Y if there had been an operation of the 1744169689Skan form &X.Y. This step adds all of the fields contained within Y 1745169689Skan (recursively) to X's map. */ 1746169689Skan 1747169689Skan result = splay_tree_min (uid_to_addressof_down_map); 1748169689Skan while (result) 1749169689Skan { 1750169689Skan int uid = result->key; 1751169689Skan /* Close the addressof map, i.e. copy all of the transitive 1752169689Skan substructures up to this level. */ 1753169689Skan close_addressof_down (uid); 1754169689Skan result = splay_tree_successor (uid_to_addressof_down_map, uid); 1755169689Skan } 1756169689Skan 1757169689Skan /* Do not need the array types and pointer types in the persistent 1758169689Skan data structures. */ 1759169689Skan result = splay_tree_min (all_canon_types); 1760169689Skan while (result) 1761169689Skan { 1762169689Skan tree type = (tree) result->value; 1763169689Skan tree key = (tree) result->key; 1764169689Skan if (POINTER_TYPE_P (type) 1765169689Skan || TREE_CODE (type) == ARRAY_TYPE) 1766169689Skan { 1767169689Skan splay_tree_remove (all_canon_types, (splay_tree_key) result->key); 1768169689Skan splay_tree_remove (type_to_canon_type, (splay_tree_key) type); 1769169689Skan splay_tree_remove (uid_to_canon_type, (splay_tree_key) TYPE_UID (type)); 1770169689Skan bitmap_clear_bit (global_types_seen, TYPE_UID (type)); 1771169689Skan } 1772169689Skan result = splay_tree_successor (all_canon_types, (splay_tree_key) key); 1773169689Skan } 1774169689Skan 1775169689Skan if (dump_file) 1776169689Skan { 1777169689Skan EXECUTE_IF_SET_IN_BITMAP (global_types_seen, 0, i, bi) 1778169689Skan { 1779169689Skan /* The pointer types are in the global_types_full_escape 1780169689Skan bitmap but not in the backwards map. They also contain 1781169689Skan no useful information since they are not marked. */ 1782169689Skan tree type = type_for_uid (i); 1783169689Skan fprintf(dump_file, "type %d ", i); 1784169689Skan print_generic_expr (dump_file, type, 0); 1785169689Skan if (bitmap_bit_p (global_types_full_escape, i)) 1786169689Skan fprintf(dump_file, " escaped\n"); 1787169689Skan else 1788169689Skan fprintf(dump_file, " contained\n"); 1789169689Skan } 1790169689Skan } 1791169689Skan 1792169689Skan /* Get rid of uid_to_addressof_up_map and its bitmaps. */ 1793169689Skan result = splay_tree_min (uid_to_addressof_up_map); 1794169689Skan while (result) 1795169689Skan { 1796169689Skan int uid = (int)result->key; 1797169689Skan bitmap bm = (bitmap)result->value; 1798169689Skan 1799169689Skan BITMAP_FREE (bm); 1800169689Skan splay_tree_remove (uid_to_addressof_up_map, (splay_tree_key) uid); 1801169689Skan result = splay_tree_successor (uid_to_addressof_up_map, uid); 1802169689Skan } 1803169689Skan 1804169689Skan /* Get rid of the subtype map. */ 1805169689Skan result = splay_tree_min (uid_to_subtype_map); 1806169689Skan while (result) 1807169689Skan { 1808169689Skan bitmap b = (bitmap)result->value; 1809169689Skan BITMAP_FREE(b); 1810169689Skan splay_tree_remove (uid_to_subtype_map, result->key); 1811169689Skan result = splay_tree_min (uid_to_subtype_map); 1812169689Skan } 1813169689Skan splay_tree_delete (uid_to_subtype_map); 1814169689Skan uid_to_subtype_map = NULL; 1815169689Skan 1816169689Skan BITMAP_FREE (global_types_exposed_parameter); 1817169689Skan BITMAP_FREE (been_there_done_that); 1818169689Skan BITMAP_FREE (bitmap_tmp); 1819169689Skan BITMAP_FREE (results_of_malloc); 1820169689Skan return 0; 1821169689Skan} 1822169689Skan 1823169689Skanstatic bool 1824169689Skangate_type_escape_vars (void) 1825169689Skan{ 1826169689Skan return (flag_unit_at_a_time != 0 && flag_ipa_type_escape 1827169689Skan /* Don't bother doing anything if the program has errors. */ 1828169689Skan && !(errorcount || sorrycount)); 1829169689Skan} 1830169689Skan 1831169689Skanstruct tree_opt_pass pass_ipa_type_escape = 1832169689Skan{ 1833169689Skan "type-escape-var", /* name */ 1834169689Skan gate_type_escape_vars, /* gate */ 1835169689Skan type_escape_execute, /* execute */ 1836169689Skan NULL, /* sub */ 1837169689Skan NULL, /* next */ 1838169689Skan 0, /* static_pass_number */ 1839169689Skan TV_IPA_TYPE_ESCAPE, /* tv_id */ 1840169689Skan 0, /* properties_required */ 1841169689Skan 0, /* properties_provided */ 1842169689Skan 0, /* properties_destroyed */ 1843169689Skan 0, /* todo_flags_start */ 1844169689Skan 0, /* todo_flags_finish */ 1845169689Skan 0 /* letter */ 1846169689Skan}; 1847169689Skan 1848