1169689Skan/* Alias analysis for trees. 2169689Skan Copyright (C) 2004, 2005 Free Software Foundation, Inc. 3169689Skan Contributed by Diego Novillo <dnovillo@redhat.com> 4169689Skan 5169689SkanThis file is part of GCC. 6169689Skan 7169689SkanGCC is free software; you can redistribute it and/or modify 8169689Skanit under the terms of the GNU General Public License as published by 9169689Skanthe Free Software Foundation; either version 2, or (at your option) 10169689Skanany later version. 11169689Skan 12169689SkanGCC is distributed in the hope that it will be useful, 13169689Skanbut WITHOUT ANY WARRANTY; without even the implied warranty of 14169689SkanMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15169689SkanGNU General Public License for 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 19169689Skanthe Free Software Foundation, 51 Franklin Street, Fifth Floor, 20169689SkanBoston, MA 02110-1301, USA. */ 21169689Skan 22169689Skan#include "config.h" 23169689Skan#include "system.h" 24169689Skan#include "coretypes.h" 25169689Skan#include "tm.h" 26169689Skan#include "tree.h" 27169689Skan#include "rtl.h" 28169689Skan#include "tm_p.h" 29169689Skan#include "hard-reg-set.h" 30169689Skan#include "basic-block.h" 31169689Skan#include "timevar.h" 32169689Skan#include "expr.h" 33169689Skan#include "ggc.h" 34169689Skan#include "langhooks.h" 35169689Skan#include "flags.h" 36169689Skan#include "function.h" 37169689Skan#include "diagnostic.h" 38169689Skan#include "tree-dump.h" 39169689Skan#include "tree-gimple.h" 40169689Skan#include "tree-flow.h" 41169689Skan#include "tree-inline.h" 42169689Skan#include "tree-pass.h" 43169689Skan#include "tree-ssa-structalias.h" 44169689Skan#include "convert.h" 45169689Skan#include "params.h" 46169689Skan#include "ipa-type-escape.h" 47169689Skan#include "vec.h" 48169689Skan#include "bitmap.h" 49169689Skan#include "vecprim.h" 50169689Skan#include "pointer-set.h" 51169689Skan 52169689Skan/* Obstack used to hold grouping bitmaps and other temporary bitmaps used by 53169689Skan aliasing */ 54169689Skanstatic bitmap_obstack alias_obstack; 55169689Skan 56169689Skan/* 'true' after aliases have been computed (see compute_may_aliases). */ 57169689Skanbool aliases_computed_p; 58169689Skan 59169689Skan/* Structure to map a variable to its alias set and keep track of the 60169689Skan virtual operands that will be needed to represent it. */ 61169689Skanstruct alias_map_d 62169689Skan{ 63169689Skan /* Variable and its alias set. */ 64169689Skan tree var; 65169689Skan HOST_WIDE_INT set; 66169689Skan 67169689Skan /* Total number of virtual operands that will be needed to represent 68169689Skan all the aliases of VAR. */ 69169689Skan long total_alias_vops; 70169689Skan 71169689Skan /* Nonzero if the aliases for this memory tag have been grouped 72169689Skan already. Used in group_aliases. */ 73169689Skan unsigned int grouped_p : 1; 74169689Skan 75169689Skan /* Set of variables aliased with VAR. This is the exact same 76169689Skan information contained in VAR_ANN (VAR)->MAY_ALIASES, but in 77169689Skan bitmap form to speed up alias grouping. */ 78169689Skan bitmap may_aliases; 79169689Skan}; 80169689Skan 81169689Skan 82169689Skan/* Counters used to display statistics on alias analysis. */ 83169689Skanstruct alias_stats_d 84169689Skan{ 85169689Skan unsigned int alias_queries; 86169689Skan unsigned int alias_mayalias; 87169689Skan unsigned int alias_noalias; 88169689Skan unsigned int simple_queries; 89169689Skan unsigned int simple_resolved; 90169689Skan unsigned int tbaa_queries; 91169689Skan unsigned int tbaa_resolved; 92169689Skan unsigned int structnoaddress_queries; 93169689Skan unsigned int structnoaddress_resolved; 94169689Skan}; 95169689Skan 96169689Skan 97169689Skan/* Local variables. */ 98169689Skanstatic struct alias_stats_d alias_stats; 99169689Skan 100169689Skan/* Local functions. */ 101169689Skanstatic void compute_flow_insensitive_aliasing (struct alias_info *); 102169689Skanstatic void finalize_ref_all_pointers (struct alias_info *); 103169689Skanstatic void dump_alias_stats (FILE *); 104169689Skanstatic bool may_alias_p (tree, HOST_WIDE_INT, tree, HOST_WIDE_INT, bool); 105169689Skanstatic tree create_memory_tag (tree type, bool is_type_tag); 106169689Skanstatic tree get_tmt_for (tree, struct alias_info *); 107169689Skanstatic tree get_nmt_for (tree); 108169689Skanstatic void add_may_alias (tree, tree); 109169689Skanstatic void replace_may_alias (tree, size_t, tree); 110169689Skanstatic struct alias_info *init_alias_info (void); 111169689Skanstatic void delete_alias_info (struct alias_info *); 112169689Skanstatic void compute_flow_sensitive_aliasing (struct alias_info *); 113169689Skanstatic void setup_pointers_and_addressables (struct alias_info *); 114169689Skanstatic void create_global_var (void); 115169689Skanstatic void maybe_create_global_var (struct alias_info *ai); 116169689Skanstatic void group_aliases (struct alias_info *); 117169689Skanstatic void set_pt_anything (tree ptr); 118169689Skan 119169689Skan/* Global declarations. */ 120169689Skan 121169689Skan/* Call clobbered variables in the function. If bit I is set, then 122169689Skan REFERENCED_VARS (I) is call-clobbered. */ 123169689Skanbitmap call_clobbered_vars; 124169689Skan 125169689Skan/* Addressable variables in the function. If bit I is set, then 126169689Skan REFERENCED_VARS (I) has had its address taken. Note that 127169689Skan CALL_CLOBBERED_VARS and ADDRESSABLE_VARS are not related. An 128169689Skan addressable variable is not necessarily call-clobbered (e.g., a 129169689Skan local addressable whose address does not escape) and not all 130169689Skan call-clobbered variables are addressable (e.g., a local static 131169689Skan variable). */ 132169689Skanbitmap addressable_vars; 133169689Skan 134169689Skan/* When the program has too many call-clobbered variables and call-sites, 135169689Skan this variable is used to represent the clobbering effects of function 136169689Skan calls. In these cases, all the call clobbered variables in the program 137169689Skan are forced to alias this variable. This reduces compile times by not 138169689Skan having to keep track of too many V_MAY_DEF expressions at call sites. */ 139169689Skantree global_var; 140169689Skan 141169689Skan/* qsort comparison function to sort type/name tags by DECL_UID. */ 142169689Skan 143169689Skanstatic int 144169689Skansort_tags_by_id (const void *pa, const void *pb) 145169689Skan{ 146169689Skan tree a = *(tree *)pa; 147169689Skan tree b = *(tree *)pb; 148169689Skan 149169689Skan return DECL_UID (a) - DECL_UID (b); 150169689Skan} 151169689Skan 152169689Skan/* Initialize WORKLIST to contain those memory tags that are marked call 153169689Skan clobbered. Initialized WORKLIST2 to contain the reasons these 154169689Skan memory tags escaped. */ 155169689Skan 156169689Skanstatic void 157169689Skaninit_transitive_clobber_worklist (VEC (tree, heap) **worklist, 158169689Skan VEC (int, heap) **worklist2) 159169689Skan{ 160169689Skan referenced_var_iterator rvi; 161169689Skan tree curr; 162169689Skan 163169689Skan FOR_EACH_REFERENCED_VAR (curr, rvi) 164169689Skan { 165169689Skan if (MTAG_P (curr) && is_call_clobbered (curr)) 166169689Skan { 167169689Skan VEC_safe_push (tree, heap, *worklist, curr); 168169689Skan VEC_safe_push (int, heap, *worklist2, var_ann (curr)->escape_mask); 169169689Skan } 170169689Skan } 171169689Skan} 172169689Skan 173169689Skan/* Add ALIAS to WORKLIST (and the reason for escaping REASON to WORKLIST2) if 174169689Skan ALIAS is not already marked call clobbered, and is a memory 175169689Skan tag. */ 176169689Skan 177169689Skanstatic void 178169689Skanadd_to_worklist (tree alias, VEC (tree, heap) **worklist, 179169689Skan VEC (int, heap) **worklist2, 180169689Skan int reason) 181169689Skan{ 182169689Skan if (MTAG_P (alias) && !is_call_clobbered (alias)) 183169689Skan { 184169689Skan VEC_safe_push (tree, heap, *worklist, alias); 185169689Skan VEC_safe_push (int, heap, *worklist2, reason); 186169689Skan } 187169689Skan} 188169689Skan 189169689Skan/* Mark aliases of TAG as call clobbered, and place any tags on the 190169689Skan alias list that were not already call clobbered on WORKLIST. */ 191169689Skan 192169689Skanstatic void 193169689Skanmark_aliases_call_clobbered (tree tag, VEC (tree, heap) **worklist, 194169689Skan VEC (int, heap) **worklist2) 195169689Skan{ 196169689Skan unsigned int i; 197169689Skan VEC (tree, gc) *ma; 198169689Skan tree entry; 199169689Skan var_ann_t ta = var_ann (tag); 200169689Skan 201169689Skan if (!MTAG_P (tag)) 202169689Skan return; 203169689Skan ma = may_aliases (tag); 204169689Skan if (!ma) 205169689Skan return; 206169689Skan 207169689Skan for (i = 0; VEC_iterate (tree, ma, i, entry); i++) 208169689Skan { 209169689Skan if (!unmodifiable_var_p (entry)) 210169689Skan { 211169689Skan add_to_worklist (entry, worklist, worklist2, ta->escape_mask); 212169689Skan mark_call_clobbered (entry, ta->escape_mask); 213169689Skan } 214169689Skan } 215169689Skan} 216169689Skan 217169689Skan/* Tags containing global vars need to be marked as global. 218169689Skan Tags containing call clobbered vars need to be marked as call 219169689Skan clobbered. */ 220169689Skan 221169689Skanstatic void 222169689Skancompute_tag_properties (void) 223169689Skan{ 224169689Skan referenced_var_iterator rvi; 225169689Skan tree tag; 226169689Skan bool changed = true; 227169689Skan VEC (tree, heap) *taglist = NULL; 228169689Skan 229169689Skan FOR_EACH_REFERENCED_VAR (tag, rvi) 230169689Skan { 231169689Skan if (!MTAG_P (tag) || TREE_CODE (tag) == STRUCT_FIELD_TAG) 232169689Skan continue; 233169689Skan VEC_safe_push (tree, heap, taglist, tag); 234169689Skan } 235169689Skan 236169689Skan /* We sort the taglist by DECL_UID, for two reasons. 237169689Skan 1. To get a sequential ordering to make the bitmap accesses 238169689Skan faster. 239169689Skan 2. Because of the way we compute aliases, it's more likely that 240169689Skan an earlier tag is included in a later tag, and this will reduce 241169689Skan the number of iterations. 242169689Skan 243169689Skan If we had a real tag graph, we would just topo-order it and be 244169689Skan done with it. */ 245169689Skan qsort (VEC_address (tree, taglist), 246169689Skan VEC_length (tree, taglist), 247169689Skan sizeof (tree), 248169689Skan sort_tags_by_id); 249169689Skan 250169689Skan /* Go through each tag not marked as global, and if it aliases 251169689Skan global vars, mark it global. 252169689Skan 253169689Skan If the tag contains call clobbered vars, mark it call 254169689Skan clobbered. 255169689Skan 256169689Skan This loop iterates because tags may appear in the may-aliases 257169689Skan list of other tags when we group. */ 258169689Skan 259169689Skan while (changed) 260169689Skan { 261169689Skan unsigned int k; 262169689Skan 263169689Skan changed = false; 264169689Skan for (k = 0; VEC_iterate (tree, taglist, k, tag); k++) 265169689Skan { 266169689Skan VEC (tree, gc) *ma; 267169689Skan unsigned int i; 268169689Skan tree entry; 269169689Skan bool tagcc = is_call_clobbered (tag); 270169689Skan bool tagglobal = MTAG_GLOBAL (tag); 271169689Skan 272169689Skan if (tagcc && tagglobal) 273169689Skan continue; 274169689Skan 275169689Skan ma = may_aliases (tag); 276169689Skan if (!ma) 277169689Skan continue; 278169689Skan 279169689Skan for (i = 0; VEC_iterate (tree, ma, i, entry); i++) 280169689Skan { 281169689Skan /* Call clobbered entries cause the tag to be marked 282169689Skan call clobbered. */ 283169689Skan if (!tagcc && is_call_clobbered (entry)) 284169689Skan { 285169689Skan mark_call_clobbered (tag, var_ann (entry)->escape_mask); 286169689Skan tagcc = true; 287169689Skan changed = true; 288169689Skan } 289169689Skan 290169689Skan /* Global vars cause the tag to be marked global. */ 291169689Skan if (!tagglobal && is_global_var (entry)) 292169689Skan { 293169689Skan MTAG_GLOBAL (tag) = true; 294169689Skan changed = true; 295169689Skan tagglobal = true; 296169689Skan } 297169689Skan 298169689Skan /* Early exit once both global and cc are set, since the 299169689Skan loop can't do any more than that. */ 300169689Skan if (tagcc && tagglobal) 301169689Skan break; 302169689Skan } 303169689Skan } 304169689Skan } 305169689Skan VEC_free (tree, heap, taglist); 306169689Skan} 307169689Skan 308169689Skan/* Set up the initial variable clobbers and globalness. 309169689Skan When this function completes, only tags whose aliases need to be 310169689Skan clobbered will be set clobbered. Tags clobbered because they 311169689Skan contain call clobbered vars are handled in compute_tag_properties. */ 312169689Skan 313169689Skanstatic void 314169689Skanset_initial_properties (struct alias_info *ai) 315169689Skan{ 316169689Skan unsigned int i; 317169689Skan referenced_var_iterator rvi; 318169689Skan tree var; 319169689Skan tree ptr; 320169689Skan 321169689Skan FOR_EACH_REFERENCED_VAR (var, rvi) 322169689Skan { 323169689Skan if (is_global_var (var) 324169689Skan && (!var_can_have_subvars (var) 325169689Skan || get_subvars_for_var (var) == NULL)) 326169689Skan { 327169689Skan if (!unmodifiable_var_p (var)) 328169689Skan mark_call_clobbered (var, ESCAPE_IS_GLOBAL); 329169689Skan } 330169689Skan else if (TREE_CODE (var) == PARM_DECL 331169689Skan && default_def (var) 332169689Skan && POINTER_TYPE_P (TREE_TYPE (var))) 333169689Skan { 334169689Skan tree def = default_def (var); 335169689Skan get_ptr_info (def)->value_escapes_p = 1; 336169689Skan get_ptr_info (def)->escape_mask |= ESCAPE_IS_PARM; 337169689Skan } 338169689Skan } 339169689Skan 340169689Skan for (i = 0; VEC_iterate (tree, ai->processed_ptrs, i, ptr); i++) 341169689Skan { 342169689Skan struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr); 343169689Skan var_ann_t v_ann = var_ann (SSA_NAME_VAR (ptr)); 344169689Skan 345169689Skan if (pi->value_escapes_p) 346169689Skan { 347169689Skan /* If PTR escapes then its associated memory tags and 348169689Skan pointed-to variables are call-clobbered. */ 349169689Skan if (pi->name_mem_tag) 350169689Skan mark_call_clobbered (pi->name_mem_tag, pi->escape_mask); 351169689Skan 352169689Skan if (v_ann->symbol_mem_tag) 353169689Skan mark_call_clobbered (v_ann->symbol_mem_tag, pi->escape_mask); 354169689Skan 355169689Skan if (pi->pt_vars) 356169689Skan { 357169689Skan bitmap_iterator bi; 358169689Skan unsigned int j; 359169689Skan EXECUTE_IF_SET_IN_BITMAP (pi->pt_vars, 0, j, bi) 360169689Skan if (!unmodifiable_var_p (referenced_var (j))) 361169689Skan mark_call_clobbered (referenced_var (j), pi->escape_mask); 362169689Skan } 363169689Skan } 364169689Skan 365169689Skan /* If the name tag is call clobbered, so is the symbol tag 366169689Skan associated with the base VAR_DECL. */ 367169689Skan if (pi->name_mem_tag 368169689Skan && v_ann->symbol_mem_tag 369169689Skan && is_call_clobbered (pi->name_mem_tag)) 370169689Skan mark_call_clobbered (v_ann->symbol_mem_tag, pi->escape_mask); 371169689Skan 372169689Skan /* Name tags and symbol tags that we don't know where they point 373169689Skan to, might point to global memory, and thus, are clobbered. 374169689Skan 375169689Skan FIXME: This is not quite right. They should only be 376169689Skan clobbered if value_escapes_p is true, regardless of whether 377169689Skan they point to global memory or not. 378169689Skan So removing this code and fixing all the bugs would be nice. 379169689Skan It is the cause of a bunch of clobbering. */ 380169689Skan if ((pi->pt_global_mem || pi->pt_anything) 381169689Skan && pi->is_dereferenced && pi->name_mem_tag) 382169689Skan { 383169689Skan mark_call_clobbered (pi->name_mem_tag, ESCAPE_IS_GLOBAL); 384169689Skan MTAG_GLOBAL (pi->name_mem_tag) = true; 385169689Skan } 386169689Skan 387169689Skan if ((pi->pt_global_mem || pi->pt_anything) 388169689Skan && pi->is_dereferenced 389169689Skan && v_ann->symbol_mem_tag) 390169689Skan { 391169689Skan mark_call_clobbered (v_ann->symbol_mem_tag, ESCAPE_IS_GLOBAL); 392169689Skan MTAG_GLOBAL (v_ann->symbol_mem_tag) = true; 393169689Skan } 394169689Skan } 395169689Skan} 396169689Skan 397169689Skan 398169689Skan/* This variable is set to true if we are updating the used alone 399169689Skan information for SMTs, or are in a pass that is going to break it 400169689Skan temporarily. */ 401169689Skanbool updating_used_alone; 402169689Skan 403169689Skan/* Compute which variables need to be marked call clobbered because 404169689Skan their tag is call clobbered, and which tags need to be marked 405169689Skan global because they contain global variables. */ 406169689Skan 407169689Skanstatic void 408169689Skancompute_call_clobbered (struct alias_info *ai) 409169689Skan{ 410169689Skan VEC (tree, heap) *worklist = NULL; 411169689Skan VEC(int,heap) *worklist2 = NULL; 412169689Skan 413169689Skan set_initial_properties (ai); 414169689Skan init_transitive_clobber_worklist (&worklist, &worklist2); 415169689Skan while (VEC_length (tree, worklist) != 0) 416169689Skan { 417169689Skan tree curr = VEC_pop (tree, worklist); 418169689Skan int reason = VEC_pop (int, worklist2); 419169689Skan 420169689Skan mark_call_clobbered (curr, reason); 421169689Skan mark_aliases_call_clobbered (curr, &worklist, &worklist2); 422169689Skan } 423169689Skan VEC_free (tree, heap, worklist); 424169689Skan VEC_free (int, heap, worklist2); 425169689Skan compute_tag_properties (); 426169689Skan} 427169689Skan 428169689Skan 429169689Skan/* Helper for recalculate_used_alone. Return a conservatively correct 430169689Skan answer as to whether STMT may make a store on the LHS to SYM. */ 431169689Skan 432169689Skanstatic bool 433169689Skanlhs_may_store_to (tree stmt, tree sym ATTRIBUTE_UNUSED) 434169689Skan{ 435169689Skan tree lhs = TREE_OPERAND (stmt, 0); 436169689Skan 437169689Skan lhs = get_base_address (lhs); 438169689Skan 439169689Skan if (!lhs) 440169689Skan return false; 441169689Skan 442169689Skan if (TREE_CODE (lhs) == SSA_NAME) 443169689Skan return false; 444169689Skan /* We could do better here by looking at the type tag of LHS, but it 445169689Skan is unclear whether this is worth it. */ 446169689Skan return true; 447169689Skan} 448169689Skan 449169689Skan/* Recalculate the used_alone information for SMTs . */ 450169689Skan 451169689Skanvoid 452169689Skanrecalculate_used_alone (void) 453169689Skan{ 454169689Skan VEC (tree, heap) *calls = NULL; 455169689Skan block_stmt_iterator bsi; 456169689Skan basic_block bb; 457169689Skan tree stmt; 458169689Skan size_t i; 459169689Skan referenced_var_iterator rvi; 460169689Skan tree var; 461169689Skan 462169689Skan /* First, reset all the SMT used alone bits to zero. */ 463169689Skan updating_used_alone = true; 464169689Skan FOR_EACH_REFERENCED_VAR (var, rvi) 465169689Skan if (TREE_CODE (var) == SYMBOL_MEMORY_TAG) 466169689Skan { 467169689Skan SMT_OLD_USED_ALONE (var) = SMT_USED_ALONE (var); 468169689Skan SMT_USED_ALONE (var) = 0; 469169689Skan } 470169689Skan 471169689Skan /* Walk all the statements. 472169689Skan Calls get put into a list of statements to update, since we will 473169689Skan need to update operands on them if we make any changes. 474169689Skan If we see a bare use of a SMT anywhere in a real virtual use or virtual 475169689Skan def, mark the SMT as used alone, and for renaming. */ 476169689Skan FOR_EACH_BB (bb) 477169689Skan { 478169689Skan for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 479169689Skan { 480169689Skan bool iscall = false; 481169689Skan ssa_op_iter iter; 482169689Skan 483169689Skan stmt = bsi_stmt (bsi); 484169689Skan 485169689Skan if (TREE_CODE (stmt) == CALL_EXPR 486169689Skan || (TREE_CODE (stmt) == MODIFY_EXPR 487169689Skan && TREE_CODE (TREE_OPERAND (stmt, 1)) == CALL_EXPR)) 488169689Skan { 489169689Skan iscall = true; 490169689Skan VEC_safe_push (tree, heap, calls, stmt); 491169689Skan } 492169689Skan 493169689Skan FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, 494169689Skan SSA_OP_VUSE | SSA_OP_VIRTUAL_DEFS) 495169689Skan { 496169689Skan tree svar = var; 497169689Skan 498169689Skan if (TREE_CODE (var) == SSA_NAME) 499169689Skan svar = SSA_NAME_VAR (var); 500169689Skan 501169689Skan if (TREE_CODE (svar) == SYMBOL_MEMORY_TAG) 502169689Skan { 503169689Skan /* We only care about the LHS on calls. */ 504169689Skan if (iscall && !lhs_may_store_to (stmt, svar)) 505169689Skan continue; 506169689Skan 507169689Skan if (!SMT_USED_ALONE (svar)) 508169689Skan { 509169689Skan SMT_USED_ALONE (svar) = true; 510169689Skan 511169689Skan /* Only need to mark for renaming if it wasn't 512169689Skan used alone before. */ 513169689Skan if (!SMT_OLD_USED_ALONE (svar)) 514169689Skan mark_sym_for_renaming (svar); 515169689Skan } 516169689Skan } 517169689Skan } 518169689Skan } 519169689Skan } 520169689Skan 521169689Skan /* Update the operands on all the calls we saw. */ 522169689Skan if (calls) 523169689Skan { 524169689Skan for (i = 0; VEC_iterate (tree, calls, i, stmt); i++) 525169689Skan update_stmt (stmt); 526169689Skan } 527169689Skan 528169689Skan /* We need to mark SMT's that are no longer used for renaming so the 529169689Skan symbols go away, or else verification will be angry with us, even 530169689Skan though they are dead. */ 531169689Skan FOR_EACH_REFERENCED_VAR (var, rvi) 532169689Skan if (TREE_CODE (var) == SYMBOL_MEMORY_TAG) 533169689Skan { 534169689Skan if (SMT_OLD_USED_ALONE (var) && !SMT_USED_ALONE (var)) 535169689Skan mark_sym_for_renaming (var); 536169689Skan } 537169689Skan 538169689Skan VEC_free (tree, heap, calls); 539169689Skan updating_used_alone = false; 540169689Skan} 541169689Skan 542169689Skan/* Compute may-alias information for every variable referenced in function 543169689Skan FNDECL. 544169689Skan 545169689Skan Alias analysis proceeds in 3 main phases: 546169689Skan 547169689Skan 1- Points-to and escape analysis. 548169689Skan 549169689Skan This phase walks the use-def chains in the SSA web looking for three 550169689Skan things: 551169689Skan 552169689Skan * Assignments of the form P_i = &VAR 553169689Skan * Assignments of the form P_i = malloc() 554169689Skan * Pointers and ADDR_EXPR that escape the current function. 555169689Skan 556169689Skan The concept of 'escaping' is the same one used in the Java world. When 557169689Skan a pointer or an ADDR_EXPR escapes, it means that it has been exposed 558169689Skan outside of the current function. So, assignment to global variables, 559169689Skan function arguments and returning a pointer are all escape sites, as are 560169689Skan conversions between pointers and integers. 561169689Skan 562169689Skan This is where we are currently limited. Since not everything is renamed 563169689Skan into SSA, we lose track of escape properties when a pointer is stashed 564169689Skan inside a field in a structure, for instance. In those cases, we are 565169689Skan assuming that the pointer does escape. 566169689Skan 567169689Skan We use escape analysis to determine whether a variable is 568169689Skan call-clobbered. Simply put, if an ADDR_EXPR escapes, then the variable 569169689Skan is call-clobbered. If a pointer P_i escapes, then all the variables 570169689Skan pointed-to by P_i (and its memory tag) also escape. 571169689Skan 572169689Skan 2- Compute flow-sensitive aliases 573169689Skan 574169689Skan We have two classes of memory tags. Memory tags associated with the 575169689Skan pointed-to data type of the pointers in the program. These tags are 576169689Skan called "symbol memory tag" (SMT). The other class are those associated 577169689Skan with SSA_NAMEs, called "name memory tag" (NMT). The basic idea is that 578169689Skan when adding operands for an INDIRECT_REF *P_i, we will first check 579169689Skan whether P_i has a name tag, if it does we use it, because that will have 580169689Skan more precise aliasing information. Otherwise, we use the standard symbol 581169689Skan tag. 582169689Skan 583169689Skan In this phase, we go through all the pointers we found in points-to 584169689Skan analysis and create alias sets for the name memory tags associated with 585169689Skan each pointer P_i. If P_i escapes, we mark call-clobbered the variables 586169689Skan it points to and its tag. 587169689Skan 588169689Skan 589169689Skan 3- Compute flow-insensitive aliases 590169689Skan 591169689Skan This pass will compare the alias set of every symbol memory tag and 592169689Skan every addressable variable found in the program. Given a symbol 593169689Skan memory tag SMT and an addressable variable V. If the alias sets of 594169689Skan SMT and V conflict (as computed by may_alias_p), then V is marked 595169689Skan as an alias tag and added to the alias set of SMT. 596169689Skan 597169689Skan For instance, consider the following function: 598169689Skan 599169689Skan foo (int i) 600169689Skan { 601169689Skan int *p, a, b; 602169689Skan 603169689Skan if (i > 10) 604169689Skan p = &a; 605169689Skan else 606169689Skan p = &b; 607169689Skan 608169689Skan *p = 3; 609169689Skan a = b + 2; 610169689Skan return *p; 611169689Skan } 612169689Skan 613169689Skan After aliasing analysis has finished, the symbol memory tag for pointer 614169689Skan 'p' will have two aliases, namely variables 'a' and 'b'. Every time 615169689Skan pointer 'p' is dereferenced, we want to mark the operation as a 616169689Skan potential reference to 'a' and 'b'. 617169689Skan 618169689Skan foo (int i) 619169689Skan { 620169689Skan int *p, a, b; 621169689Skan 622169689Skan if (i_2 > 10) 623169689Skan p_4 = &a; 624169689Skan else 625169689Skan p_6 = &b; 626169689Skan # p_1 = PHI <p_4(1), p_6(2)>; 627169689Skan 628169689Skan # a_7 = V_MAY_DEF <a_3>; 629169689Skan # b_8 = V_MAY_DEF <b_5>; 630169689Skan *p_1 = 3; 631169689Skan 632169689Skan # a_9 = V_MAY_DEF <a_7> 633169689Skan # VUSE <b_8> 634169689Skan a_9 = b_8 + 2; 635169689Skan 636169689Skan # VUSE <a_9>; 637169689Skan # VUSE <b_8>; 638169689Skan return *p_1; 639169689Skan } 640169689Skan 641169689Skan In certain cases, the list of may aliases for a pointer may grow too 642169689Skan large. This may cause an explosion in the number of virtual operands 643169689Skan inserted in the code. Resulting in increased memory consumption and 644169689Skan compilation time. 645169689Skan 646169689Skan When the number of virtual operands needed to represent aliased 647169689Skan loads and stores grows too large (configurable with @option{--param 648169689Skan max-aliased-vops}), alias sets are grouped to avoid severe 649169689Skan compile-time slow downs and memory consumption. See group_aliases. */ 650169689Skan 651169689Skanstatic unsigned int 652169689Skancompute_may_aliases (void) 653169689Skan{ 654169689Skan struct alias_info *ai; 655259405Spfg 656169689Skan memset (&alias_stats, 0, sizeof (alias_stats)); 657169689Skan 658169689Skan /* Initialize aliasing information. */ 659169689Skan ai = init_alias_info (); 660169689Skan 661169689Skan /* For each pointer P_i, determine the sets of variables that P_i may 662169689Skan point-to. For every addressable variable V, determine whether the 663169689Skan address of V escapes the current function, making V call-clobbered 664169689Skan (i.e., whether &V is stored in a global variable or if its passed as a 665169689Skan function call argument). */ 666169689Skan compute_points_to_sets (ai); 667169689Skan 668169689Skan /* Collect all pointers and addressable variables, compute alias sets, 669169689Skan create memory tags for pointers and promote variables whose address is 670169689Skan not needed anymore. */ 671169689Skan setup_pointers_and_addressables (ai); 672169689Skan 673169689Skan /* Compute flow-sensitive, points-to based aliasing for all the name 674169689Skan memory tags. Note that this pass needs to be done before flow 675169689Skan insensitive analysis because it uses the points-to information 676169689Skan gathered before to mark call-clobbered symbol tags. */ 677169689Skan compute_flow_sensitive_aliasing (ai); 678169689Skan 679169689Skan /* Compute type-based flow-insensitive aliasing for all the type 680169689Skan memory tags. */ 681169689Skan compute_flow_insensitive_aliasing (ai); 682169689Skan 683169689Skan /* Compute call clobbering information. */ 684169689Skan compute_call_clobbered (ai); 685169689Skan 686169689Skan /* Determine if we need to enable alias grouping. */ 687169689Skan if (ai->total_alias_vops >= MAX_ALIASED_VOPS) 688169689Skan group_aliases (ai); 689169689Skan 690169689Skan /* If the program has too many call-clobbered variables and/or function 691169689Skan calls, create .GLOBAL_VAR and use it to model call-clobbering 692169689Skan semantics at call sites. This reduces the number of virtual operands 693169689Skan considerably, improving compile times at the expense of lost 694169689Skan aliasing precision. */ 695169689Skan maybe_create_global_var (ai); 696169689Skan 697169689Skan /* If the program contains ref-all pointers, finalize may-alias information 698169689Skan for them. This pass needs to be run after call-clobbering information 699169689Skan has been computed. */ 700169689Skan if (ai->ref_all_symbol_mem_tag) 701169689Skan finalize_ref_all_pointers (ai); 702169689Skan 703169689Skan /* Debugging dumps. */ 704169689Skan if (dump_file) 705169689Skan { 706169689Skan dump_referenced_vars (dump_file); 707169689Skan if (dump_flags & TDF_STATS) 708169689Skan dump_alias_stats (dump_file); 709169689Skan dump_points_to_info (dump_file); 710169689Skan dump_alias_info (dump_file); 711169689Skan } 712169689Skan 713259405Spfg /* Report strict aliasing violations. */ 714259405Spfg strict_aliasing_warning_backend (); 715259405Spfg 716169689Skan /* Deallocate memory used by aliasing data structures. */ 717169689Skan delete_alias_info (ai); 718169689Skan 719169689Skan updating_used_alone = true; 720169689Skan { 721169689Skan block_stmt_iterator bsi; 722169689Skan basic_block bb; 723169689Skan FOR_EACH_BB (bb) 724169689Skan { 725169689Skan for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 726169689Skan { 727169689Skan update_stmt_if_modified (bsi_stmt (bsi)); 728169689Skan } 729169689Skan } 730169689Skan } 731169689Skan recalculate_used_alone (); 732169689Skan updating_used_alone = false; 733169689Skan return 0; 734169689Skan} 735169689Skan 736169689Skan 737169689Skanstruct tree_opt_pass pass_may_alias = 738169689Skan{ 739169689Skan "alias", /* name */ 740169689Skan NULL, /* gate */ 741169689Skan compute_may_aliases, /* execute */ 742169689Skan NULL, /* sub */ 743169689Skan NULL, /* next */ 744169689Skan 0, /* static_pass_number */ 745169689Skan TV_TREE_MAY_ALIAS, /* tv_id */ 746169689Skan PROP_cfg | PROP_ssa, /* properties_required */ 747169689Skan PROP_alias, /* properties_provided */ 748169689Skan 0, /* properties_destroyed */ 749169689Skan 0, /* todo_flags_start */ 750169689Skan TODO_dump_func | TODO_update_ssa 751169689Skan | TODO_ggc_collect | TODO_verify_ssa 752169689Skan | TODO_verify_stmts, /* todo_flags_finish */ 753169689Skan 0 /* letter */ 754169689Skan}; 755169689Skan 756169689Skan 757169689Skan/* Data structure used to count the number of dereferences to PTR 758169689Skan inside an expression. */ 759169689Skanstruct count_ptr_d 760169689Skan{ 761169689Skan tree ptr; 762169689Skan unsigned count; 763169689Skan}; 764169689Skan 765169689Skan 766169689Skan/* Helper for count_uses_and_derefs. Called by walk_tree to look for 767169689Skan (ALIGN/MISALIGNED_)INDIRECT_REF nodes for the pointer passed in DATA. */ 768169689Skan 769169689Skanstatic tree 770169689Skancount_ptr_derefs (tree *tp, int *walk_subtrees, void *data) 771169689Skan{ 772169689Skan struct count_ptr_d *count_p = (struct count_ptr_d *) data; 773169689Skan 774169689Skan /* Do not walk inside ADDR_EXPR nodes. In the expression &ptr->fld, 775169689Skan pointer 'ptr' is *not* dereferenced, it is simply used to compute 776169689Skan the address of 'fld' as 'ptr + offsetof(fld)'. */ 777169689Skan if (TREE_CODE (*tp) == ADDR_EXPR) 778169689Skan { 779169689Skan *walk_subtrees = 0; 780169689Skan return NULL_TREE; 781169689Skan } 782169689Skan 783169689Skan if (INDIRECT_REF_P (*tp) && TREE_OPERAND (*tp, 0) == count_p->ptr) 784169689Skan count_p->count++; 785169689Skan 786169689Skan return NULL_TREE; 787169689Skan} 788169689Skan 789169689Skan 790169689Skan/* Count the number of direct and indirect uses for pointer PTR in 791169689Skan statement STMT. The two counts are stored in *NUM_USES_P and 792169689Skan *NUM_DEREFS_P respectively. *IS_STORE_P is set to 'true' if at 793169689Skan least one of those dereferences is a store operation. */ 794169689Skan 795169689Skanvoid 796169689Skancount_uses_and_derefs (tree ptr, tree stmt, unsigned *num_uses_p, 797169689Skan unsigned *num_derefs_p, bool *is_store) 798169689Skan{ 799169689Skan ssa_op_iter i; 800169689Skan tree use; 801169689Skan 802169689Skan *num_uses_p = 0; 803169689Skan *num_derefs_p = 0; 804169689Skan *is_store = false; 805169689Skan 806169689Skan /* Find out the total number of uses of PTR in STMT. */ 807169689Skan FOR_EACH_SSA_TREE_OPERAND (use, stmt, i, SSA_OP_USE) 808169689Skan if (use == ptr) 809169689Skan (*num_uses_p)++; 810169689Skan 811169689Skan /* Now count the number of indirect references to PTR. This is 812169689Skan truly awful, but we don't have much choice. There are no parent 813169689Skan pointers inside INDIRECT_REFs, so an expression like 814169689Skan '*x_1 = foo (x_1, *x_1)' needs to be traversed piece by piece to 815169689Skan find all the indirect and direct uses of x_1 inside. The only 816169689Skan shortcut we can take is the fact that GIMPLE only allows 817169689Skan INDIRECT_REFs inside the expressions below. */ 818169689Skan if (TREE_CODE (stmt) == MODIFY_EXPR 819169689Skan || (TREE_CODE (stmt) == RETURN_EXPR 820169689Skan && TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR) 821169689Skan || TREE_CODE (stmt) == ASM_EXPR 822169689Skan || TREE_CODE (stmt) == CALL_EXPR) 823169689Skan { 824169689Skan tree lhs, rhs; 825169689Skan 826169689Skan if (TREE_CODE (stmt) == MODIFY_EXPR) 827169689Skan { 828169689Skan lhs = TREE_OPERAND (stmt, 0); 829169689Skan rhs = TREE_OPERAND (stmt, 1); 830169689Skan } 831169689Skan else if (TREE_CODE (stmt) == RETURN_EXPR) 832169689Skan { 833169689Skan tree e = TREE_OPERAND (stmt, 0); 834169689Skan lhs = TREE_OPERAND (e, 0); 835169689Skan rhs = TREE_OPERAND (e, 1); 836169689Skan } 837169689Skan else if (TREE_CODE (stmt) == ASM_EXPR) 838169689Skan { 839169689Skan lhs = ASM_OUTPUTS (stmt); 840169689Skan rhs = ASM_INPUTS (stmt); 841169689Skan } 842169689Skan else 843169689Skan { 844169689Skan lhs = NULL_TREE; 845169689Skan rhs = stmt; 846169689Skan } 847169689Skan 848169689Skan if (lhs && (TREE_CODE (lhs) == TREE_LIST || EXPR_P (lhs))) 849169689Skan { 850169689Skan struct count_ptr_d count; 851169689Skan count.ptr = ptr; 852169689Skan count.count = 0; 853169689Skan walk_tree (&lhs, count_ptr_derefs, &count, NULL); 854169689Skan *is_store = true; 855169689Skan *num_derefs_p = count.count; 856169689Skan } 857169689Skan 858169689Skan if (rhs && (TREE_CODE (rhs) == TREE_LIST || EXPR_P (rhs))) 859169689Skan { 860169689Skan struct count_ptr_d count; 861169689Skan count.ptr = ptr; 862169689Skan count.count = 0; 863169689Skan walk_tree (&rhs, count_ptr_derefs, &count, NULL); 864169689Skan *num_derefs_p += count.count; 865169689Skan } 866169689Skan } 867169689Skan 868169689Skan gcc_assert (*num_uses_p >= *num_derefs_p); 869169689Skan} 870169689Skan 871169689Skan/* Initialize the data structures used for alias analysis. */ 872169689Skan 873169689Skanstatic struct alias_info * 874169689Skaninit_alias_info (void) 875169689Skan{ 876169689Skan struct alias_info *ai; 877169689Skan referenced_var_iterator rvi; 878169689Skan tree var; 879169689Skan 880169689Skan bitmap_obstack_initialize (&alias_obstack); 881169689Skan ai = XCNEW (struct alias_info); 882169689Skan ai->ssa_names_visited = sbitmap_alloc (num_ssa_names); 883169689Skan sbitmap_zero (ai->ssa_names_visited); 884169689Skan ai->processed_ptrs = VEC_alloc (tree, heap, 50); 885169689Skan ai->written_vars = BITMAP_ALLOC (&alias_obstack); 886169689Skan ai->dereferenced_ptrs_store = BITMAP_ALLOC (&alias_obstack); 887169689Skan ai->dereferenced_ptrs_load = BITMAP_ALLOC (&alias_obstack); 888169689Skan 889169689Skan /* If aliases have been computed before, clear existing information. */ 890169689Skan if (aliases_computed_p) 891169689Skan { 892169689Skan unsigned i; 893169689Skan 894169689Skan /* Similarly, clear the set of addressable variables. In this 895169689Skan case, we can just clear the set because addressability is 896169689Skan only computed here. */ 897169689Skan bitmap_clear (addressable_vars); 898169689Skan 899169689Skan /* Clear flow-insensitive alias information from each symbol. */ 900169689Skan FOR_EACH_REFERENCED_VAR (var, rvi) 901169689Skan { 902169689Skan var_ann_t ann = var_ann (var); 903169689Skan 904169689Skan ann->is_aliased = 0; 905169689Skan ann->may_aliases = NULL; 906169689Skan NUM_REFERENCES_CLEAR (ann); 907169689Skan 908169689Skan /* Since we are about to re-discover call-clobbered 909169689Skan variables, clear the call-clobbered flag. Variables that 910169689Skan are intrinsically call-clobbered (globals, local statics, 911169689Skan etc) will not be marked by the aliasing code, so we can't 912169689Skan remove them from CALL_CLOBBERED_VARS. 913169689Skan 914169689Skan NB: STRUCT_FIELDS are still call clobbered if they are for 915169689Skan a global variable, so we *don't* clear their call clobberedness 916169689Skan just because they are tags, though we will clear it if they 917169689Skan aren't for global variables. */ 918169689Skan if (TREE_CODE (var) == NAME_MEMORY_TAG 919169689Skan || TREE_CODE (var) == SYMBOL_MEMORY_TAG 920169689Skan || !is_global_var (var)) 921169689Skan clear_call_clobbered (var); 922169689Skan } 923169689Skan 924169689Skan /* Clear flow-sensitive points-to information from each SSA name. */ 925169689Skan for (i = 1; i < num_ssa_names; i++) 926169689Skan { 927169689Skan tree name = ssa_name (i); 928169689Skan 929169689Skan if (!name || !POINTER_TYPE_P (TREE_TYPE (name))) 930169689Skan continue; 931169689Skan 932169689Skan if (SSA_NAME_PTR_INFO (name)) 933169689Skan { 934169689Skan struct ptr_info_def *pi = SSA_NAME_PTR_INFO (name); 935169689Skan 936169689Skan /* Clear all the flags but keep the name tag to 937169689Skan avoid creating new temporaries unnecessarily. If 938169689Skan this pointer is found to point to a subset or 939169689Skan superset of its former points-to set, then a new 940169689Skan tag will need to be created in create_name_tags. */ 941169689Skan pi->pt_anything = 0; 942169689Skan pi->pt_null = 0; 943169689Skan pi->value_escapes_p = 0; 944169689Skan pi->is_dereferenced = 0; 945169689Skan if (pi->pt_vars) 946169689Skan bitmap_clear (pi->pt_vars); 947169689Skan } 948169689Skan } 949169689Skan } 950169689Skan 951169689Skan /* Next time, we will need to reset alias information. */ 952169689Skan aliases_computed_p = true; 953169689Skan 954169689Skan return ai; 955169689Skan} 956169689Skan 957169689Skan 958169689Skan/* Deallocate memory used by alias analysis. */ 959169689Skan 960169689Skanstatic void 961169689Skandelete_alias_info (struct alias_info *ai) 962169689Skan{ 963169689Skan size_t i; 964169689Skan referenced_var_iterator rvi; 965169689Skan tree var; 966169689Skan 967169689Skan sbitmap_free (ai->ssa_names_visited); 968169689Skan VEC_free (tree, heap, ai->processed_ptrs); 969169689Skan 970169689Skan for (i = 0; i < ai->num_addressable_vars; i++) 971169689Skan free (ai->addressable_vars[i]); 972169689Skan 973169689Skan FOR_EACH_REFERENCED_VAR(var, rvi) 974169689Skan { 975169689Skan var_ann_t ann = var_ann (var); 976169689Skan NUM_REFERENCES_CLEAR (ann); 977169689Skan } 978169689Skan 979169689Skan free (ai->addressable_vars); 980169689Skan 981169689Skan for (i = 0; i < ai->num_pointers; i++) 982169689Skan free (ai->pointers[i]); 983169689Skan free (ai->pointers); 984169689Skan 985169689Skan BITMAP_FREE (ai->written_vars); 986169689Skan BITMAP_FREE (ai->dereferenced_ptrs_store); 987169689Skan BITMAP_FREE (ai->dereferenced_ptrs_load); 988169689Skan bitmap_obstack_release (&alias_obstack); 989169689Skan free (ai); 990169689Skan 991169689Skan delete_points_to_sets (); 992169689Skan} 993169689Skan 994169689Skan/* Used for hashing to identify pointer infos with identical 995169689Skan pt_vars bitmaps. */ 996169689Skanstatic int 997169689Skaneq_ptr_info (const void *p1, const void *p2) 998169689Skan{ 999169689Skan const struct ptr_info_def *n1 = (const struct ptr_info_def *) p1; 1000169689Skan const struct ptr_info_def *n2 = (const struct ptr_info_def *) p2; 1001169689Skan return bitmap_equal_p (n1->pt_vars, n2->pt_vars); 1002169689Skan} 1003169689Skan 1004169689Skanstatic hashval_t 1005169689Skanptr_info_hash (const void *p) 1006169689Skan{ 1007169689Skan const struct ptr_info_def *n = (const struct ptr_info_def *) p; 1008169689Skan return bitmap_hash (n->pt_vars); 1009169689Skan} 1010169689Skan 1011169689Skan/* Create name tags for all the pointers that have been dereferenced. 1012169689Skan We only create a name tag for a pointer P if P is found to point to 1013169689Skan a set of variables (so that we can alias them to *P) or if it is 1014169689Skan the result of a call to malloc (which means that P cannot point to 1015169689Skan anything else nor alias any other variable). 1016169689Skan 1017169689Skan If two pointers P and Q point to the same set of variables, they 1018169689Skan are assigned the same name tag. */ 1019169689Skan 1020169689Skanstatic void 1021169689Skancreate_name_tags (void) 1022169689Skan{ 1023169689Skan size_t i; 1024169689Skan VEC (tree, heap) *with_ptvars = NULL; 1025169689Skan tree ptr; 1026169689Skan htab_t ptr_hash; 1027169689Skan 1028169689Skan /* Collect the list of pointers with a non-empty points to set. */ 1029169689Skan for (i = 1; i < num_ssa_names; i++) 1030169689Skan { 1031169689Skan tree ptr = ssa_name (i); 1032169689Skan struct ptr_info_def *pi; 1033169689Skan 1034169689Skan if (!ptr 1035169689Skan || !POINTER_TYPE_P (TREE_TYPE (ptr)) 1036169689Skan || !SSA_NAME_PTR_INFO (ptr)) 1037169689Skan continue; 1038169689Skan 1039169689Skan pi = SSA_NAME_PTR_INFO (ptr); 1040169689Skan 1041169689Skan if (pi->pt_anything || !pi->is_dereferenced) 1042169689Skan { 1043169689Skan /* No name tags for pointers that have not been 1044169689Skan dereferenced or point to an arbitrary location. */ 1045169689Skan pi->name_mem_tag = NULL_TREE; 1046169689Skan continue; 1047169689Skan } 1048169689Skan 1049169689Skan /* Set pt_anything on the pointers without pt_vars filled in so 1050169689Skan that they are assigned a symbol tag. */ 1051169689Skan if (pi->pt_vars && !bitmap_empty_p (pi->pt_vars)) 1052169689Skan VEC_safe_push (tree, heap, with_ptvars, ptr); 1053169689Skan else 1054169689Skan set_pt_anything (ptr); 1055169689Skan } 1056169689Skan 1057169689Skan /* If we didn't find any pointers with pt_vars set, we're done. */ 1058169689Skan if (!with_ptvars) 1059169689Skan return; 1060169689Skan 1061169689Skan ptr_hash = htab_create (10, ptr_info_hash, eq_ptr_info, NULL); 1062169689Skan /* Now go through the pointers with pt_vars, and find a name tag 1063169689Skan with the same pt_vars as this pointer, or create one if one 1064169689Skan doesn't exist. */ 1065169689Skan for (i = 0; VEC_iterate (tree, with_ptvars, i, ptr); i++) 1066169689Skan { 1067169689Skan struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr); 1068169689Skan tree old_name_tag = pi->name_mem_tag; 1069169689Skan struct ptr_info_def **slot; 1070169689Skan 1071169689Skan /* If PTR points to a set of variables, check if we don't 1072169689Skan have another pointer Q with the same points-to set before 1073169689Skan creating a tag. If so, use Q's tag instead of creating a 1074169689Skan new one. 1075169689Skan 1076169689Skan This is important for not creating unnecessary symbols 1077169689Skan and also for copy propagation. If we ever need to 1078169689Skan propagate PTR into Q or vice-versa, we would run into 1079169689Skan problems if they both had different name tags because 1080169689Skan they would have different SSA version numbers (which 1081169689Skan would force us to take the name tags in and out of SSA). */ 1082169689Skan 1083169689Skan slot = (struct ptr_info_def **) htab_find_slot (ptr_hash, pi, INSERT); 1084169689Skan if (*slot) 1085169689Skan pi->name_mem_tag = (*slot)->name_mem_tag; 1086169689Skan else 1087169689Skan { 1088169689Skan *slot = pi; 1089169689Skan /* If we didn't find a pointer with the same points-to set 1090169689Skan as PTR, create a new name tag if needed. */ 1091169689Skan if (pi->name_mem_tag == NULL_TREE) 1092169689Skan pi->name_mem_tag = get_nmt_for (ptr); 1093169689Skan } 1094169689Skan 1095169689Skan /* If the new name tag computed for PTR is different than 1096169689Skan the old name tag that it used to have, then the old tag 1097169689Skan needs to be removed from the IL, so we mark it for 1098169689Skan renaming. */ 1099169689Skan if (old_name_tag && old_name_tag != pi->name_mem_tag) 1100169689Skan mark_sym_for_renaming (old_name_tag); 1101169689Skan 1102169689Skan TREE_THIS_VOLATILE (pi->name_mem_tag) 1103169689Skan |= TREE_THIS_VOLATILE (TREE_TYPE (TREE_TYPE (ptr))); 1104169689Skan 1105169689Skan /* Mark the new name tag for renaming. */ 1106169689Skan mark_sym_for_renaming (pi->name_mem_tag); 1107169689Skan } 1108169689Skan htab_delete (ptr_hash); 1109169689Skan 1110169689Skan VEC_free (tree, heap, with_ptvars); 1111169689Skan} 1112169689Skan 1113169689Skan 1114169689Skan/* For every pointer P_i in AI->PROCESSED_PTRS, create may-alias sets for 1115169689Skan the name memory tag (NMT) associated with P_i. If P_i escapes, then its 1116169689Skan name tag and the variables it points-to are call-clobbered. Finally, if 1117169689Skan P_i escapes and we could not determine where it points to, then all the 1118169689Skan variables in the same alias set as *P_i are marked call-clobbered. This 1119169689Skan is necessary because we must assume that P_i may take the address of any 1120169689Skan variable in the same alias set. */ 1121169689Skan 1122169689Skanstatic void 1123169689Skancompute_flow_sensitive_aliasing (struct alias_info *ai) 1124169689Skan{ 1125169689Skan size_t i; 1126169689Skan tree ptr; 1127169689Skan 1128169689Skan for (i = 0; VEC_iterate (tree, ai->processed_ptrs, i, ptr); i++) 1129169689Skan { 1130169689Skan if (!find_what_p_points_to (ptr)) 1131169689Skan set_pt_anything (ptr); 1132169689Skan } 1133169689Skan 1134169689Skan create_name_tags (); 1135169689Skan 1136169689Skan for (i = 0; VEC_iterate (tree, ai->processed_ptrs, i, ptr); i++) 1137169689Skan { 1138169689Skan unsigned j; 1139169689Skan struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr); 1140169689Skan var_ann_t v_ann = var_ann (SSA_NAME_VAR (ptr)); 1141169689Skan bitmap_iterator bi; 1142169689Skan 1143169689Skan 1144169689Skan /* Set up aliasing information for PTR's name memory tag (if it has 1145169689Skan one). Note that only pointers that have been dereferenced will 1146169689Skan have a name memory tag. */ 1147169689Skan if (pi->name_mem_tag && pi->pt_vars) 1148169689Skan EXECUTE_IF_SET_IN_BITMAP (pi->pt_vars, 0, j, bi) 1149169689Skan { 1150169689Skan add_may_alias (pi->name_mem_tag, referenced_var (j)); 1151169689Skan add_may_alias (v_ann->symbol_mem_tag, referenced_var (j)); 1152169689Skan } 1153169689Skan } 1154169689Skan} 1155169689Skan 1156169689Skan 1157169689Skan/* Compute type-based alias sets. Traverse all the pointers and 1158169689Skan addressable variables found in setup_pointers_and_addressables. 1159169689Skan 1160169689Skan For every pointer P in AI->POINTERS and addressable variable V in 1161169689Skan AI->ADDRESSABLE_VARS, add V to the may-alias sets of P's symbol 1162169689Skan memory tag (SMT) if their alias sets conflict. V is then marked as 1163169689Skan an alias tag so that the operand scanner knows that statements 1164169689Skan containing V have aliased operands. */ 1165169689Skan 1166169689Skanstatic void 1167169689Skancompute_flow_insensitive_aliasing (struct alias_info *ai) 1168169689Skan{ 1169169689Skan size_t i; 1170169689Skan 1171169689Skan /* Initialize counter for the total number of virtual operands that 1172169689Skan aliasing will introduce. When AI->TOTAL_ALIAS_VOPS goes beyond the 1173169689Skan threshold set by --params max-alias-vops, we enable alias 1174169689Skan grouping. */ 1175169689Skan ai->total_alias_vops = 0; 1176169689Skan 1177169689Skan /* For every pointer P, determine which addressable variables may alias 1178169689Skan with P's symbol memory tag. */ 1179169689Skan for (i = 0; i < ai->num_pointers; i++) 1180169689Skan { 1181169689Skan size_t j; 1182169689Skan struct alias_map_d *p_map = ai->pointers[i]; 1183169689Skan tree tag = var_ann (p_map->var)->symbol_mem_tag; 1184169689Skan var_ann_t tag_ann = var_ann (tag); 1185169689Skan tree var; 1186169689Skan 1187169689Skan /* Call-clobbering information is not finalized yet at this point. */ 1188169689Skan if (PTR_IS_REF_ALL (p_map->var)) 1189169689Skan continue; 1190169689Skan 1191169689Skan p_map->total_alias_vops = 0; 1192169689Skan p_map->may_aliases = BITMAP_ALLOC (&alias_obstack); 1193169689Skan 1194169689Skan /* Add any pre-existing may_aliases to the bitmap used to represent 1195169689Skan TAG's alias set in case we need to group aliases. */ 1196169689Skan for (j = 0; VEC_iterate (tree, tag_ann->may_aliases, j, var); ++j) 1197169689Skan bitmap_set_bit (p_map->may_aliases, DECL_UID (var)); 1198169689Skan 1199169689Skan for (j = 0; j < ai->num_addressable_vars; j++) 1200169689Skan { 1201169689Skan struct alias_map_d *v_map; 1202169689Skan var_ann_t v_ann; 1203169689Skan bool tag_stored_p, var_stored_p; 1204169689Skan 1205169689Skan v_map = ai->addressable_vars[j]; 1206169689Skan var = v_map->var; 1207169689Skan v_ann = var_ann (var); 1208169689Skan 1209169689Skan /* Skip memory tags and variables that have never been 1210169689Skan written to. We also need to check if the variables are 1211169689Skan call-clobbered because they may be overwritten by 1212169689Skan function calls. 1213169689Skan 1214169689Skan Note this is effectively random accessing elements in 1215169689Skan the sparse bitset, which can be highly inefficient. 1216169689Skan So we first check the call_clobbered status of the 1217169689Skan tag and variable before querying the bitmap. */ 1218169689Skan tag_stored_p = is_call_clobbered (tag) 1219169689Skan || bitmap_bit_p (ai->written_vars, DECL_UID (tag)); 1220169689Skan var_stored_p = is_call_clobbered (var) 1221169689Skan || bitmap_bit_p (ai->written_vars, DECL_UID (var)); 1222169689Skan if (!tag_stored_p && !var_stored_p) 1223169689Skan continue; 1224169689Skan 1225169689Skan if (may_alias_p (p_map->var, p_map->set, var, v_map->set, false)) 1226169689Skan { 1227169689Skan size_t num_tag_refs, num_var_refs; 1228169689Skan 1229169689Skan num_tag_refs = NUM_REFERENCES (tag_ann); 1230169689Skan num_var_refs = NUM_REFERENCES (v_ann); 1231169689Skan 1232169689Skan /* Add VAR to TAG's may-aliases set. */ 1233169689Skan 1234169689Skan /* We should never have a var with subvars here, because 1235169689Skan they shouldn't get into the set of addressable vars */ 1236169689Skan gcc_assert (!var_can_have_subvars (var) 1237169689Skan || get_subvars_for_var (var) == NULL); 1238169689Skan 1239169689Skan add_may_alias (tag, var); 1240169689Skan /* Update the bitmap used to represent TAG's alias set 1241169689Skan in case we need to group aliases. */ 1242169689Skan bitmap_set_bit (p_map->may_aliases, DECL_UID (var)); 1243169689Skan 1244169689Skan /* Update the total number of virtual operands due to 1245169689Skan aliasing. Since we are adding one more alias to TAG's 1246169689Skan may-aliases set, the total number of virtual operands due 1247169689Skan to aliasing will be increased by the number of references 1248169689Skan made to VAR and TAG (every reference to TAG will also 1249169689Skan count as a reference to VAR). */ 1250169689Skan ai->total_alias_vops += (num_var_refs + num_tag_refs); 1251169689Skan p_map->total_alias_vops += (num_var_refs + num_tag_refs); 1252169689Skan 1253169689Skan 1254169689Skan } 1255169689Skan } 1256169689Skan } 1257169689Skan 1258169689Skan /* Since this analysis is based exclusively on symbols, it fails to 1259169689Skan handle cases where two pointers P and Q have different memory 1260169689Skan tags with conflicting alias set numbers but no aliased symbols in 1261169689Skan common. 1262169689Skan 1263169689Skan For example, suppose that we have two memory tags SMT.1 and SMT.2 1264169689Skan such that 1265169689Skan 1266169689Skan may-aliases (SMT.1) = { a } 1267169689Skan may-aliases (SMT.2) = { b } 1268169689Skan 1269169689Skan and the alias set number of SMT.1 conflicts with that of SMT.2. 1270169689Skan Since they don't have symbols in common, loads and stores from 1271169689Skan SMT.1 and SMT.2 will seem independent of each other, which will 1272169689Skan lead to the optimizers making invalid transformations (see 1273169689Skan testsuite/gcc.c-torture/execute/pr15262-[12].c). 1274169689Skan 1275169689Skan To avoid this problem, we do a final traversal of AI->POINTERS 1276169689Skan looking for pairs of pointers that have no aliased symbols in 1277169689Skan common and yet have conflicting alias set numbers. */ 1278169689Skan for (i = 0; i < ai->num_pointers; i++) 1279169689Skan { 1280169689Skan size_t j; 1281169689Skan struct alias_map_d *p_map1 = ai->pointers[i]; 1282169689Skan tree tag1 = var_ann (p_map1->var)->symbol_mem_tag; 1283169689Skan bitmap may_aliases1 = p_map1->may_aliases; 1284169689Skan 1285169689Skan if (PTR_IS_REF_ALL (p_map1->var)) 1286169689Skan continue; 1287169689Skan 1288169689Skan for (j = i + 1; j < ai->num_pointers; j++) 1289169689Skan { 1290169689Skan struct alias_map_d *p_map2 = ai->pointers[j]; 1291169689Skan tree tag2 = var_ann (p_map2->var)->symbol_mem_tag; 1292169689Skan bitmap may_aliases2 = p_map2->may_aliases; 1293169689Skan 1294169689Skan if (PTR_IS_REF_ALL (p_map2->var)) 1295169689Skan continue; 1296169689Skan 1297169689Skan /* If the pointers may not point to each other, do nothing. */ 1298169689Skan if (!may_alias_p (p_map1->var, p_map1->set, tag2, p_map2->set, true)) 1299169689Skan continue; 1300169689Skan 1301169689Skan /* The two pointers may alias each other. If they already have 1302169689Skan symbols in common, do nothing. */ 1303169689Skan if (bitmap_intersect_p (may_aliases1, may_aliases2)) 1304169689Skan continue; 1305169689Skan 1306169689Skan if (!bitmap_empty_p (may_aliases2)) 1307169689Skan { 1308169689Skan unsigned int k; 1309169689Skan bitmap_iterator bi; 1310169689Skan 1311169689Skan /* Add all the aliases for TAG2 into TAG1's alias set. 1312169689Skan FIXME, update grouping heuristic counters. */ 1313169689Skan EXECUTE_IF_SET_IN_BITMAP (may_aliases2, 0, k, bi) 1314169689Skan add_may_alias (tag1, referenced_var (k)); 1315169689Skan bitmap_ior_into (may_aliases1, may_aliases2); 1316169689Skan } 1317169689Skan else 1318169689Skan { 1319169689Skan /* Since TAG2 does not have any aliases of its own, add 1320169689Skan TAG2 itself to the alias set of TAG1. */ 1321169689Skan add_may_alias (tag1, tag2); 1322169689Skan bitmap_set_bit (may_aliases1, DECL_UID (tag2)); 1323169689Skan } 1324169689Skan } 1325169689Skan } 1326169689Skan 1327169689Skan if (dump_file) 1328169689Skan fprintf (dump_file, "\n%s: Total number of aliased vops: %ld\n", 1329169689Skan get_name (current_function_decl), 1330169689Skan ai->total_alias_vops); 1331169689Skan} 1332169689Skan 1333169689Skan 1334169689Skan/* Finalize may-alias information for ref-all pointers. Traverse all 1335169689Skan the addressable variables found in setup_pointers_and_addressables. 1336169689Skan 1337169689Skan If flow-sensitive alias analysis has attached a name memory tag to 1338169689Skan a ref-all pointer, we will use it for the dereferences because that 1339169689Skan will have more precise aliasing information. But if there is no 1340169689Skan name tag, we will use a special symbol tag that aliases all the 1341169689Skan call-clobbered addressable variables. */ 1342169689Skan 1343169689Skanstatic void 1344169689Skanfinalize_ref_all_pointers (struct alias_info *ai) 1345169689Skan{ 1346169689Skan size_t i; 1347169689Skan 1348169689Skan if (global_var) 1349169689Skan add_may_alias (ai->ref_all_symbol_mem_tag, global_var); 1350169689Skan else 1351169689Skan { 1352169689Skan /* First add the real call-clobbered variables. */ 1353169689Skan for (i = 0; i < ai->num_addressable_vars; i++) 1354169689Skan { 1355169689Skan tree var = ai->addressable_vars[i]->var; 1356169689Skan if (is_call_clobbered (var)) 1357169689Skan add_may_alias (ai->ref_all_symbol_mem_tag, var); 1358169689Skan } 1359169689Skan 1360169689Skan /* Then add the call-clobbered pointer memory tags. See 1361169689Skan compute_flow_insensitive_aliasing for the rationale. */ 1362169689Skan for (i = 0; i < ai->num_pointers; i++) 1363169689Skan { 1364169689Skan tree ptr = ai->pointers[i]->var, tag; 1365169689Skan if (PTR_IS_REF_ALL (ptr)) 1366169689Skan continue; 1367169689Skan tag = var_ann (ptr)->symbol_mem_tag; 1368169689Skan if (is_call_clobbered (tag)) 1369169689Skan add_may_alias (ai->ref_all_symbol_mem_tag, tag); 1370169689Skan } 1371169689Skan } 1372169689Skan} 1373169689Skan 1374169689Skan 1375169689Skan/* Comparison function for qsort used in group_aliases. */ 1376169689Skan 1377169689Skanstatic int 1378169689Skantotal_alias_vops_cmp (const void *p, const void *q) 1379169689Skan{ 1380169689Skan const struct alias_map_d **p1 = (const struct alias_map_d **)p; 1381169689Skan const struct alias_map_d **p2 = (const struct alias_map_d **)q; 1382169689Skan long n1 = (*p1)->total_alias_vops; 1383169689Skan long n2 = (*p2)->total_alias_vops; 1384169689Skan 1385169689Skan /* We want to sort in descending order. */ 1386169689Skan return (n1 > n2 ? -1 : (n1 == n2) ? 0 : 1); 1387169689Skan} 1388169689Skan 1389169689Skan/* Group all the aliases for TAG to make TAG represent all the 1390169689Skan variables in its alias set. Update the total number 1391169689Skan of virtual operands due to aliasing (AI->TOTAL_ALIAS_VOPS). This 1392169689Skan function will make TAG be the unique alias tag for all the 1393169689Skan variables in its may-aliases. So, given: 1394169689Skan 1395169689Skan may-aliases(TAG) = { V1, V2, V3 } 1396169689Skan 1397169689Skan This function will group the variables into: 1398169689Skan 1399169689Skan may-aliases(V1) = { TAG } 1400169689Skan may-aliases(V2) = { TAG } 1401169689Skan may-aliases(V2) = { TAG } */ 1402169689Skan 1403169689Skanstatic void 1404169689Skangroup_aliases_into (tree tag, bitmap tag_aliases, struct alias_info *ai) 1405169689Skan{ 1406169689Skan unsigned int i; 1407169689Skan var_ann_t tag_ann = var_ann (tag); 1408169689Skan size_t num_tag_refs = NUM_REFERENCES (tag_ann); 1409169689Skan bitmap_iterator bi; 1410169689Skan 1411169689Skan EXECUTE_IF_SET_IN_BITMAP (tag_aliases, 0, i, bi) 1412169689Skan { 1413169689Skan tree var = referenced_var (i); 1414169689Skan var_ann_t ann = var_ann (var); 1415169689Skan 1416169689Skan /* Make TAG the unique alias of VAR. */ 1417169689Skan ann->is_aliased = 0; 1418169689Skan ann->may_aliases = NULL; 1419169689Skan 1420169689Skan /* Note that VAR and TAG may be the same if the function has no 1421169689Skan addressable variables (see the discussion at the end of 1422169689Skan setup_pointers_and_addressables). */ 1423169689Skan if (var != tag) 1424169689Skan add_may_alias (var, tag); 1425169689Skan 1426169689Skan /* Reduce total number of virtual operands contributed 1427169689Skan by TAG on behalf of VAR. Notice that the references to VAR 1428169689Skan itself won't be removed. We will merely replace them with 1429169689Skan references to TAG. */ 1430169689Skan ai->total_alias_vops -= num_tag_refs; 1431169689Skan } 1432169689Skan 1433169689Skan /* We have reduced the number of virtual operands that TAG makes on 1434169689Skan behalf of all the variables formerly aliased with it. However, 1435169689Skan we have also "removed" all the virtual operands for TAG itself, 1436169689Skan so we add them back. */ 1437169689Skan ai->total_alias_vops += num_tag_refs; 1438169689Skan 1439169689Skan /* TAG no longer has any aliases. */ 1440169689Skan tag_ann->may_aliases = NULL; 1441169689Skan} 1442169689Skan 1443169689Skan 1444169689Skan/* Group may-aliases sets to reduce the number of virtual operands due 1445169689Skan to aliasing. 1446169689Skan 1447169689Skan 1- Sort the list of pointers in decreasing number of contributed 1448169689Skan virtual operands. 1449169689Skan 1450169689Skan 2- Take the first entry in AI->POINTERS and revert the role of 1451169689Skan the memory tag and its aliases. Usually, whenever an aliased 1452169689Skan variable Vi is found to alias with a memory tag T, we add Vi 1453169689Skan to the may-aliases set for T. Meaning that after alias 1454169689Skan analysis, we will have: 1455169689Skan 1456169689Skan may-aliases(T) = { V1, V2, V3, ..., Vn } 1457169689Skan 1458169689Skan This means that every statement that references T, will get 'n' 1459169689Skan virtual operands for each of the Vi tags. But, when alias 1460169689Skan grouping is enabled, we make T an alias tag and add it to the 1461169689Skan alias set of all the Vi variables: 1462169689Skan 1463169689Skan may-aliases(V1) = { T } 1464169689Skan may-aliases(V2) = { T } 1465169689Skan ... 1466169689Skan may-aliases(Vn) = { T } 1467169689Skan 1468169689Skan This has two effects: (a) statements referencing T will only get 1469169689Skan a single virtual operand, and, (b) all the variables Vi will now 1470169689Skan appear to alias each other. So, we lose alias precision to 1471169689Skan improve compile time. But, in theory, a program with such a high 1472169689Skan level of aliasing should not be very optimizable in the first 1473169689Skan place. 1474169689Skan 1475169689Skan 3- Since variables may be in the alias set of more than one 1476169689Skan memory tag, the grouping done in step (2) needs to be extended 1477169689Skan to all the memory tags that have a non-empty intersection with 1478169689Skan the may-aliases set of tag T. For instance, if we originally 1479169689Skan had these may-aliases sets: 1480169689Skan 1481169689Skan may-aliases(T) = { V1, V2, V3 } 1482169689Skan may-aliases(R) = { V2, V4 } 1483169689Skan 1484169689Skan In step (2) we would have reverted the aliases for T as: 1485169689Skan 1486169689Skan may-aliases(V1) = { T } 1487169689Skan may-aliases(V2) = { T } 1488169689Skan may-aliases(V3) = { T } 1489169689Skan 1490169689Skan But note that now V2 is no longer aliased with R. We could 1491169689Skan add R to may-aliases(V2), but we are in the process of 1492169689Skan grouping aliases to reduce virtual operands so what we do is 1493169689Skan add V4 to the grouping to obtain: 1494169689Skan 1495169689Skan may-aliases(V1) = { T } 1496169689Skan may-aliases(V2) = { T } 1497169689Skan may-aliases(V3) = { T } 1498169689Skan may-aliases(V4) = { T } 1499169689Skan 1500169689Skan 4- If the total number of virtual operands due to aliasing is 1501169689Skan still above the threshold set by max-alias-vops, go back to (2). */ 1502169689Skan 1503169689Skanstatic void 1504169689Skangroup_aliases (struct alias_info *ai) 1505169689Skan{ 1506169689Skan size_t i; 1507169689Skan tree ptr; 1508169689Skan 1509169689Skan /* Sort the POINTERS array in descending order of contributed 1510169689Skan virtual operands. */ 1511169689Skan qsort (ai->pointers, ai->num_pointers, sizeof (struct alias_map_d *), 1512169689Skan total_alias_vops_cmp); 1513169689Skan 1514169689Skan /* For every pointer in AI->POINTERS, reverse the roles of its tag 1515169689Skan and the tag's may-aliases set. */ 1516169689Skan for (i = 0; i < ai->num_pointers; i++) 1517169689Skan { 1518169689Skan size_t j; 1519169689Skan tree tag1 = var_ann (ai->pointers[i]->var)->symbol_mem_tag; 1520169689Skan bitmap tag1_aliases = ai->pointers[i]->may_aliases; 1521169689Skan 1522169689Skan /* Skip tags that have been grouped already. */ 1523169689Skan if (ai->pointers[i]->grouped_p) 1524169689Skan continue; 1525169689Skan 1526169689Skan /* See if TAG1 had any aliases in common with other symbol tags. 1527169689Skan If we find a TAG2 with common aliases with TAG1, add TAG2's 1528169689Skan aliases into TAG1. */ 1529169689Skan for (j = i + 1; j < ai->num_pointers; j++) 1530169689Skan { 1531169689Skan bitmap tag2_aliases = ai->pointers[j]->may_aliases; 1532169689Skan 1533169689Skan if (bitmap_intersect_p (tag1_aliases, tag2_aliases)) 1534169689Skan { 1535169689Skan tree tag2 = var_ann (ai->pointers[j]->var)->symbol_mem_tag; 1536169689Skan 1537169689Skan bitmap_ior_into (tag1_aliases, tag2_aliases); 1538169689Skan 1539169689Skan /* TAG2 does not need its aliases anymore. */ 1540169689Skan bitmap_clear (tag2_aliases); 1541169689Skan var_ann (tag2)->may_aliases = NULL; 1542169689Skan 1543169689Skan /* TAG1 is the unique alias of TAG2. */ 1544169689Skan add_may_alias (tag2, tag1); 1545169689Skan 1546169689Skan ai->pointers[j]->grouped_p = true; 1547169689Skan } 1548169689Skan } 1549169689Skan 1550169689Skan /* Now group all the aliases we collected into TAG1. */ 1551169689Skan group_aliases_into (tag1, tag1_aliases, ai); 1552169689Skan 1553169689Skan /* If we've reduced total number of virtual operands below the 1554169689Skan threshold, stop. */ 1555169689Skan if (ai->total_alias_vops < MAX_ALIASED_VOPS) 1556169689Skan break; 1557169689Skan } 1558169689Skan 1559169689Skan /* Finally, all the variables that have been grouped cannot be in 1560169689Skan the may-alias set of name memory tags. Suppose that we have 1561169689Skan grouped the aliases in this code so that may-aliases(a) = SMT.20 1562169689Skan 1563169689Skan p_5 = &a; 1564169689Skan ... 1565169689Skan # a_9 = V_MAY_DEF <a_8> 1566169689Skan p_5->field = 0 1567169689Skan ... Several modifications to SMT.20 ... 1568169689Skan # VUSE <a_9> 1569169689Skan x_30 = p_5->field 1570169689Skan 1571169689Skan Since p_5 points to 'a', the optimizers will try to propagate 0 1572169689Skan into p_5->field, but that is wrong because there have been 1573169689Skan modifications to 'SMT.20' in between. To prevent this we have to 1574169689Skan replace 'a' with 'SMT.20' in the name tag of p_5. */ 1575169689Skan for (i = 0; VEC_iterate (tree, ai->processed_ptrs, i, ptr); i++) 1576169689Skan { 1577169689Skan size_t j; 1578169689Skan tree name_tag = SSA_NAME_PTR_INFO (ptr)->name_mem_tag; 1579169689Skan VEC(tree,gc) *aliases; 1580169689Skan tree alias; 1581169689Skan 1582169689Skan if (name_tag == NULL_TREE) 1583169689Skan continue; 1584169689Skan 1585169689Skan aliases = var_ann (name_tag)->may_aliases; 1586169689Skan for (j = 0; VEC_iterate (tree, aliases, j, alias); j++) 1587169689Skan { 1588169689Skan var_ann_t ann = var_ann (alias); 1589169689Skan 1590169689Skan if ((!MTAG_P (alias) 1591169689Skan || TREE_CODE (alias) == STRUCT_FIELD_TAG) 1592169689Skan && ann->may_aliases) 1593169689Skan { 1594169689Skan tree new_alias; 1595169689Skan 1596169689Skan gcc_assert (VEC_length (tree, ann->may_aliases) == 1); 1597169689Skan 1598169689Skan new_alias = VEC_index (tree, ann->may_aliases, 0); 1599169689Skan replace_may_alias (name_tag, j, new_alias); 1600169689Skan } 1601169689Skan } 1602169689Skan } 1603169689Skan 1604169689Skan if (dump_file) 1605169689Skan fprintf (dump_file, 1606169689Skan "%s: Total number of aliased vops after grouping: %ld%s\n", 1607169689Skan get_name (current_function_decl), 1608169689Skan ai->total_alias_vops, 1609169689Skan (ai->total_alias_vops < 0) ? " (negative values are OK)" : ""); 1610169689Skan} 1611169689Skan 1612169689Skan 1613169689Skan/* Create a new alias set entry for VAR in AI->ADDRESSABLE_VARS. */ 1614169689Skan 1615169689Skanstatic void 1616169689Skancreate_alias_map_for (tree var, struct alias_info *ai) 1617169689Skan{ 1618169689Skan struct alias_map_d *alias_map; 1619169689Skan alias_map = XCNEW (struct alias_map_d); 1620169689Skan alias_map->var = var; 1621169689Skan alias_map->set = get_alias_set (var); 1622169689Skan ai->addressable_vars[ai->num_addressable_vars++] = alias_map; 1623169689Skan} 1624169689Skan 1625169689Skan 1626169689Skan/* Create memory tags for all the dereferenced pointers and build the 1627169689Skan ADDRESSABLE_VARS and POINTERS arrays used for building the may-alias 1628169689Skan sets. Based on the address escape and points-to information collected 1629169689Skan earlier, this pass will also clear the TREE_ADDRESSABLE flag from those 1630169689Skan variables whose address is not needed anymore. */ 1631169689Skan 1632169689Skanstatic void 1633169689Skansetup_pointers_and_addressables (struct alias_info *ai) 1634169689Skan{ 1635169689Skan size_t n_vars, num_addressable_vars, num_pointers; 1636169689Skan referenced_var_iterator rvi; 1637169689Skan tree var; 1638169689Skan VEC (tree, heap) *varvec = NULL; 1639169689Skan safe_referenced_var_iterator srvi; 1640169689Skan 1641169689Skan /* Size up the arrays ADDRESSABLE_VARS and POINTERS. */ 1642169689Skan num_addressable_vars = num_pointers = 0; 1643169689Skan 1644169689Skan FOR_EACH_REFERENCED_VAR (var, rvi) 1645169689Skan { 1646169689Skan if (may_be_aliased (var)) 1647169689Skan num_addressable_vars++; 1648169689Skan 1649169689Skan if (POINTER_TYPE_P (TREE_TYPE (var))) 1650169689Skan { 1651169689Skan /* Since we don't keep track of volatile variables, assume that 1652169689Skan these pointers are used in indirect store operations. */ 1653169689Skan if (TREE_THIS_VOLATILE (var)) 1654169689Skan bitmap_set_bit (ai->dereferenced_ptrs_store, DECL_UID (var)); 1655169689Skan 1656169689Skan num_pointers++; 1657169689Skan } 1658169689Skan } 1659169689Skan 1660169689Skan /* Create ADDRESSABLE_VARS and POINTERS. Note that these arrays are 1661169689Skan always going to be slightly bigger than we actually need them 1662169689Skan because some TREE_ADDRESSABLE variables will be marked 1663169689Skan non-addressable below and only pointers with unique symbol tags are 1664169689Skan going to be added to POINTERS. */ 1665169689Skan ai->addressable_vars = XCNEWVEC (struct alias_map_d *, num_addressable_vars); 1666169689Skan ai->pointers = XCNEWVEC (struct alias_map_d *, num_pointers); 1667169689Skan ai->num_addressable_vars = 0; 1668169689Skan ai->num_pointers = 0; 1669169689Skan 1670169689Skan /* Since we will be creating symbol memory tags within this loop, 1671169689Skan cache the value of NUM_REFERENCED_VARS to avoid processing the 1672169689Skan additional tags unnecessarily. */ 1673169689Skan n_vars = num_referenced_vars; 1674169689Skan 1675169689Skan FOR_EACH_REFERENCED_VAR_SAFE (var, varvec, srvi) 1676169689Skan { 1677169689Skan var_ann_t v_ann = var_ann (var); 1678169689Skan subvar_t svars; 1679169689Skan 1680169689Skan /* Name memory tags already have flow-sensitive aliasing 1681169689Skan information, so they need not be processed by 1682169689Skan compute_flow_insensitive_aliasing. Similarly, symbol memory 1683169689Skan tags are already accounted for when we process their 1684169689Skan associated pointer. 1685169689Skan 1686169689Skan Structure fields, on the other hand, have to have some of this 1687169689Skan information processed for them, but it's pointless to mark them 1688169689Skan non-addressable (since they are fake variables anyway). */ 1689169689Skan if (MTAG_P (var) && TREE_CODE (var) != STRUCT_FIELD_TAG) 1690169689Skan continue; 1691169689Skan 1692169689Skan /* Remove the ADDRESSABLE flag from every addressable variable whose 1693169689Skan address is not needed anymore. This is caused by the propagation 1694169689Skan of ADDR_EXPR constants into INDIRECT_REF expressions and the 1695169689Skan removal of dead pointer assignments done by the early scalar 1696169689Skan cleanup passes. */ 1697169689Skan if (TREE_ADDRESSABLE (var)) 1698169689Skan { 1699169689Skan if (!bitmap_bit_p (addressable_vars, DECL_UID (var)) 1700169689Skan && TREE_CODE (var) != RESULT_DECL 1701169689Skan && !is_global_var (var)) 1702169689Skan { 1703169689Skan bool okay_to_mark = true; 1704169689Skan 1705169689Skan /* Since VAR is now a regular GIMPLE register, we will need 1706169689Skan to rename VAR into SSA afterwards. */ 1707169689Skan mark_sym_for_renaming (var); 1708169689Skan 1709169689Skan /* If VAR can have sub-variables, and any of its 1710169689Skan sub-variables has its address taken, then we cannot 1711169689Skan remove the addressable flag from VAR. */ 1712169689Skan if (var_can_have_subvars (var) 1713169689Skan && (svars = get_subvars_for_var (var))) 1714169689Skan { 1715169689Skan subvar_t sv; 1716169689Skan 1717169689Skan for (sv = svars; sv; sv = sv->next) 1718169689Skan { 1719169689Skan if (bitmap_bit_p (addressable_vars, DECL_UID (sv->var))) 1720169689Skan okay_to_mark = false; 1721169689Skan mark_sym_for_renaming (sv->var); 1722169689Skan } 1723169689Skan } 1724169689Skan 1725169689Skan /* The address of VAR is not needed, remove the 1726169689Skan addressable bit, so that it can be optimized as a 1727169689Skan regular variable. */ 1728169689Skan if (okay_to_mark) 1729169689Skan mark_non_addressable (var); 1730169689Skan } 1731169689Skan } 1732169689Skan 1733169689Skan /* Global variables and addressable locals may be aliased. Create an 1734169689Skan entry in ADDRESSABLE_VARS for VAR. */ 1735169689Skan if (may_be_aliased (var) 1736169689Skan && (!var_can_have_subvars (var) 1737169689Skan || get_subvars_for_var (var) == NULL)) 1738169689Skan { 1739169689Skan create_alias_map_for (var, ai); 1740169689Skan mark_sym_for_renaming (var); 1741169689Skan } 1742169689Skan 1743169689Skan /* Add pointer variables that have been dereferenced to the POINTERS 1744169689Skan array and create a symbol memory tag for them. */ 1745169689Skan if (POINTER_TYPE_P (TREE_TYPE (var))) 1746169689Skan { 1747169689Skan if ((bitmap_bit_p (ai->dereferenced_ptrs_store, DECL_UID (var)) 1748169689Skan || bitmap_bit_p (ai->dereferenced_ptrs_load, DECL_UID (var)))) 1749169689Skan { 1750169689Skan tree tag; 1751169689Skan var_ann_t t_ann; 1752169689Skan 1753169689Skan /* If pointer VAR still doesn't have a memory tag 1754169689Skan associated with it, create it now or re-use an 1755169689Skan existing one. */ 1756169689Skan tag = get_tmt_for (var, ai); 1757169689Skan t_ann = var_ann (tag); 1758169689Skan 1759169689Skan /* The symbol tag will need to be renamed into SSA 1760169689Skan afterwards. Note that we cannot do this inside 1761169689Skan get_tmt_for because aliasing may run multiple times 1762169689Skan and we only create symbol tags the first time. */ 1763169689Skan mark_sym_for_renaming (tag); 1764169689Skan 1765169689Skan /* Similarly, if pointer VAR used to have another type 1766169689Skan tag, we will need to process it in the renamer to 1767169689Skan remove the stale virtual operands. */ 1768169689Skan if (v_ann->symbol_mem_tag) 1769169689Skan mark_sym_for_renaming (v_ann->symbol_mem_tag); 1770169689Skan 1771169689Skan /* Associate the tag with pointer VAR. */ 1772169689Skan v_ann->symbol_mem_tag = tag; 1773169689Skan 1774169689Skan /* If pointer VAR has been used in a store operation, 1775169689Skan then its memory tag must be marked as written-to. */ 1776169689Skan if (bitmap_bit_p (ai->dereferenced_ptrs_store, DECL_UID (var))) 1777169689Skan bitmap_set_bit (ai->written_vars, DECL_UID (tag)); 1778169689Skan 1779169689Skan /* All the dereferences of pointer VAR count as 1780169689Skan references of TAG. Since TAG can be associated with 1781169689Skan several pointers, add the dereferences of VAR to the 1782169689Skan TAG. */ 1783169689Skan NUM_REFERENCES_SET (t_ann, 1784169689Skan NUM_REFERENCES (t_ann) 1785169689Skan + NUM_REFERENCES (v_ann)); 1786169689Skan } 1787169689Skan else 1788169689Skan { 1789169689Skan /* The pointer has not been dereferenced. If it had a 1790169689Skan symbol memory tag, remove it and mark the old tag for 1791169689Skan renaming to remove it out of the IL. */ 1792169689Skan var_ann_t ann = var_ann (var); 1793169689Skan tree tag = ann->symbol_mem_tag; 1794169689Skan if (tag) 1795169689Skan { 1796169689Skan mark_sym_for_renaming (tag); 1797169689Skan ann->symbol_mem_tag = NULL_TREE; 1798169689Skan } 1799169689Skan } 1800169689Skan } 1801169689Skan } 1802169689Skan VEC_free (tree, heap, varvec); 1803169689Skan} 1804169689Skan 1805169689Skan 1806169689Skan/* Determine whether to use .GLOBAL_VAR to model call clobbering semantics. At 1807169689Skan every call site, we need to emit V_MAY_DEF expressions to represent the 1808169689Skan clobbering effects of the call for variables whose address escapes the 1809169689Skan current function. 1810169689Skan 1811169689Skan One approach is to group all call-clobbered variables into a single 1812169689Skan representative that is used as an alias of every call-clobbered variable 1813169689Skan (.GLOBAL_VAR). This works well, but it ties the optimizer hands because 1814169689Skan references to any call clobbered variable is a reference to .GLOBAL_VAR. 1815169689Skan 1816169689Skan The second approach is to emit a clobbering V_MAY_DEF for every 1817169689Skan call-clobbered variable at call sites. This is the preferred way in terms 1818169689Skan of optimization opportunities but it may create too many V_MAY_DEF operands 1819169689Skan if there are many call clobbered variables and function calls in the 1820169689Skan function. 1821169689Skan 1822169689Skan To decide whether or not to use .GLOBAL_VAR we multiply the number of 1823169689Skan function calls found by the number of call-clobbered variables. If that 1824169689Skan product is beyond a certain threshold, as determined by the parameterized 1825169689Skan values shown below, we use .GLOBAL_VAR. 1826169689Skan 1827169689Skan FIXME. This heuristic should be improved. One idea is to use several 1828169689Skan .GLOBAL_VARs of different types instead of a single one. The thresholds 1829169689Skan have been derived from a typical bootstrap cycle, including all target 1830169689Skan libraries. Compile times were found increase by ~1% compared to using 1831169689Skan .GLOBAL_VAR. */ 1832169689Skan 1833169689Skanstatic void 1834169689Skanmaybe_create_global_var (struct alias_info *ai) 1835169689Skan{ 1836169689Skan unsigned i, n_clobbered; 1837169689Skan bitmap_iterator bi; 1838169689Skan 1839169689Skan /* No need to create it, if we have one already. */ 1840169689Skan if (global_var == NULL_TREE) 1841169689Skan { 1842169689Skan /* Count all the call-clobbered variables. */ 1843169689Skan n_clobbered = 0; 1844169689Skan EXECUTE_IF_SET_IN_BITMAP (call_clobbered_vars, 0, i, bi) 1845169689Skan { 1846169689Skan n_clobbered++; 1847169689Skan } 1848169689Skan 1849169689Skan /* If the number of virtual operands that would be needed to 1850169689Skan model all the call-clobbered variables is larger than 1851169689Skan GLOBAL_VAR_THRESHOLD, create .GLOBAL_VAR. 1852169689Skan 1853169689Skan Also create .GLOBAL_VAR if there are no call-clobbered 1854169689Skan variables and the program contains a mixture of pure/const 1855169689Skan and regular function calls. This is to avoid the problem 1856169689Skan described in PR 20115: 1857169689Skan 1858169689Skan int X; 1859169689Skan int func_pure (void) { return X; } 1860169689Skan int func_non_pure (int a) { X += a; } 1861169689Skan int foo () 1862169689Skan { 1863169689Skan int a = func_pure (); 1864169689Skan func_non_pure (a); 1865169689Skan a = func_pure (); 1866169689Skan return a; 1867169689Skan } 1868169689Skan 1869169689Skan Since foo() has no call-clobbered variables, there is 1870169689Skan no relationship between the calls to func_pure and 1871169689Skan func_non_pure. Since func_pure has no side-effects, value 1872169689Skan numbering optimizations elide the second call to func_pure. 1873169689Skan So, if we have some pure/const and some regular calls in the 1874169689Skan program we create .GLOBAL_VAR to avoid missing these 1875169689Skan relations. */ 1876169689Skan if (ai->num_calls_found * n_clobbered >= (size_t) GLOBAL_VAR_THRESHOLD 1877169689Skan || (n_clobbered == 0 1878169689Skan && ai->num_calls_found > 0 1879169689Skan && ai->num_pure_const_calls_found > 0 1880169689Skan && ai->num_calls_found > ai->num_pure_const_calls_found)) 1881169689Skan create_global_var (); 1882169689Skan } 1883169689Skan 1884169689Skan /* Mark all call-clobbered symbols for renaming. Since the initial 1885169689Skan rewrite into SSA ignored all call sites, we may need to rename 1886169689Skan .GLOBAL_VAR and the call-clobbered variables. */ 1887169689Skan EXECUTE_IF_SET_IN_BITMAP (call_clobbered_vars, 0, i, bi) 1888169689Skan { 1889169689Skan tree var = referenced_var (i); 1890169689Skan 1891169689Skan /* If the function has calls to clobbering functions and 1892169689Skan .GLOBAL_VAR has been created, make it an alias for all 1893169689Skan call-clobbered variables. */ 1894169689Skan if (global_var && var != global_var) 1895169689Skan { 1896169689Skan add_may_alias (var, global_var); 1897169689Skan gcc_assert (!get_subvars_for_var (var)); 1898169689Skan } 1899169689Skan 1900169689Skan mark_sym_for_renaming (var); 1901169689Skan } 1902169689Skan} 1903169689Skan 1904169689Skan 1905169689Skan/* Return TRUE if pointer PTR may point to variable VAR. 1906169689Skan 1907169689Skan MEM_ALIAS_SET is the alias set for the memory location pointed-to by PTR 1908169689Skan This is needed because when checking for type conflicts we are 1909169689Skan interested in the alias set of the memory location pointed-to by 1910169689Skan PTR. The alias set of PTR itself is irrelevant. 1911169689Skan 1912169689Skan VAR_ALIAS_SET is the alias set for VAR. */ 1913169689Skan 1914169689Skanstatic bool 1915169689Skanmay_alias_p (tree ptr, HOST_WIDE_INT mem_alias_set, 1916169689Skan tree var, HOST_WIDE_INT var_alias_set, 1917169689Skan bool alias_set_only) 1918169689Skan{ 1919169689Skan tree mem; 1920169689Skan 1921169689Skan alias_stats.alias_queries++; 1922169689Skan alias_stats.simple_queries++; 1923169689Skan 1924169689Skan /* By convention, a variable cannot alias itself. */ 1925169689Skan mem = var_ann (ptr)->symbol_mem_tag; 1926169689Skan if (mem == var) 1927169689Skan { 1928169689Skan alias_stats.alias_noalias++; 1929169689Skan alias_stats.simple_resolved++; 1930169689Skan return false; 1931169689Skan } 1932169689Skan 1933169689Skan /* If -fargument-noalias-global is > 2, pointer arguments may 1934169689Skan not point to anything else. */ 1935169689Skan if (flag_argument_noalias > 2 && TREE_CODE (ptr) == PARM_DECL) 1936169689Skan { 1937169689Skan alias_stats.alias_noalias++; 1938169689Skan alias_stats.simple_resolved++; 1939169689Skan return false; 1940169689Skan } 1941169689Skan 1942169689Skan /* If -fargument-noalias-global is > 1, pointer arguments may 1943169689Skan not point to global variables. */ 1944169689Skan if (flag_argument_noalias > 1 && is_global_var (var) 1945169689Skan && TREE_CODE (ptr) == PARM_DECL) 1946169689Skan { 1947169689Skan alias_stats.alias_noalias++; 1948169689Skan alias_stats.simple_resolved++; 1949169689Skan return false; 1950169689Skan } 1951169689Skan 1952169689Skan /* If either MEM or VAR is a read-only global and the other one 1953169689Skan isn't, then PTR cannot point to VAR. */ 1954169689Skan if ((unmodifiable_var_p (mem) && !unmodifiable_var_p (var)) 1955169689Skan || (unmodifiable_var_p (var) && !unmodifiable_var_p (mem))) 1956169689Skan { 1957169689Skan alias_stats.alias_noalias++; 1958169689Skan alias_stats.simple_resolved++; 1959169689Skan return false; 1960169689Skan } 1961169689Skan 1962169689Skan gcc_assert (TREE_CODE (mem) == SYMBOL_MEMORY_TAG); 1963169689Skan 1964169689Skan alias_stats.tbaa_queries++; 1965169689Skan 1966169689Skan /* If the alias sets don't conflict then MEM cannot alias VAR. */ 1967169689Skan if (!alias_sets_conflict_p (mem_alias_set, var_alias_set)) 1968169689Skan { 1969169689Skan alias_stats.alias_noalias++; 1970169689Skan alias_stats.tbaa_resolved++; 1971169689Skan return false; 1972169689Skan } 1973169689Skan 1974169689Skan /* If var is a record or union type, ptr cannot point into var 1975169689Skan unless there is some operation explicit address operation in the 1976169689Skan program that can reference a field of the ptr's dereferenced 1977169689Skan type. This also assumes that the types of both var and ptr are 1978169689Skan contained within the compilation unit, and that there is no fancy 1979169689Skan addressing arithmetic associated with any of the types 1980169689Skan involved. */ 1981169689Skan 1982169689Skan if ((mem_alias_set != 0) && (var_alias_set != 0)) 1983169689Skan { 1984169689Skan tree ptr_type = TREE_TYPE (ptr); 1985169689Skan tree var_type = TREE_TYPE (var); 1986169689Skan 1987169689Skan /* The star count is -1 if the type at the end of the pointer_to 1988169689Skan chain is not a record or union type. */ 1989169689Skan if ((!alias_set_only) && 1990169689Skan ipa_type_escape_star_count_of_interesting_type (var_type) >= 0) 1991169689Skan { 1992169689Skan int ptr_star_count = 0; 1993169689Skan 1994169689Skan /* Ipa_type_escape_star_count_of_interesting_type is a little to 1995169689Skan restrictive for the pointer type, need to allow pointers to 1996169689Skan primitive types as long as those types cannot be pointers 1997169689Skan to everything. */ 1998169689Skan while (POINTER_TYPE_P (ptr_type)) 1999169689Skan /* Strip the *'s off. */ 2000169689Skan { 2001169689Skan ptr_type = TREE_TYPE (ptr_type); 2002169689Skan ptr_star_count++; 2003169689Skan } 2004169689Skan 2005169689Skan /* There does not appear to be a better test to see if the 2006169689Skan pointer type was one of the pointer to everything 2007169689Skan types. */ 2008169689Skan 2009169689Skan if (ptr_star_count > 0) 2010169689Skan { 2011169689Skan alias_stats.structnoaddress_queries++; 2012169689Skan if (ipa_type_escape_field_does_not_clobber_p (var_type, 2013169689Skan TREE_TYPE (ptr))) 2014169689Skan { 2015169689Skan alias_stats.structnoaddress_resolved++; 2016169689Skan alias_stats.alias_noalias++; 2017169689Skan return false; 2018169689Skan } 2019169689Skan } 2020169689Skan else if (ptr_star_count == 0) 2021169689Skan { 2022169689Skan /* If ptr_type was not really a pointer to type, it cannot 2023169689Skan alias. */ 2024169689Skan alias_stats.structnoaddress_queries++; 2025169689Skan alias_stats.structnoaddress_resolved++; 2026169689Skan alias_stats.alias_noalias++; 2027169689Skan return false; 2028169689Skan } 2029169689Skan } 2030169689Skan } 2031169689Skan 2032169689Skan alias_stats.alias_mayalias++; 2033169689Skan return true; 2034169689Skan} 2035169689Skan 2036169689Skan 2037169689Skan/* Add ALIAS to the set of variables that may alias VAR. */ 2038169689Skan 2039169689Skanstatic void 2040169689Skanadd_may_alias (tree var, tree alias) 2041169689Skan{ 2042169689Skan size_t i; 2043169689Skan var_ann_t v_ann = get_var_ann (var); 2044169689Skan var_ann_t a_ann = get_var_ann (alias); 2045169689Skan tree al; 2046169689Skan 2047169689Skan /* Don't allow self-referential aliases. */ 2048169689Skan gcc_assert (var != alias); 2049169689Skan 2050169689Skan /* ALIAS must be addressable if it's being added to an alias set. */ 2051169689Skan#if 1 2052169689Skan TREE_ADDRESSABLE (alias) = 1; 2053169689Skan#else 2054169689Skan gcc_assert (may_be_aliased (alias)); 2055169689Skan#endif 2056169689Skan 2057169689Skan if (v_ann->may_aliases == NULL) 2058169689Skan v_ann->may_aliases = VEC_alloc (tree, gc, 2); 2059169689Skan 2060169689Skan /* Avoid adding duplicates. */ 2061169689Skan for (i = 0; VEC_iterate (tree, v_ann->may_aliases, i, al); i++) 2062169689Skan if (alias == al) 2063169689Skan return; 2064169689Skan 2065169689Skan VEC_safe_push (tree, gc, v_ann->may_aliases, alias); 2066169689Skan a_ann->is_aliased = 1; 2067169689Skan} 2068169689Skan 2069169689Skan 2070169689Skan/* Replace alias I in the alias sets of VAR with NEW_ALIAS. */ 2071169689Skan 2072169689Skanstatic void 2073169689Skanreplace_may_alias (tree var, size_t i, tree new_alias) 2074169689Skan{ 2075169689Skan var_ann_t v_ann = var_ann (var); 2076169689Skan VEC_replace (tree, v_ann->may_aliases, i, new_alias); 2077169689Skan} 2078169689Skan 2079169689Skan 2080169689Skan/* Mark pointer PTR as pointing to an arbitrary memory location. */ 2081169689Skan 2082169689Skanstatic void 2083169689Skanset_pt_anything (tree ptr) 2084169689Skan{ 2085169689Skan struct ptr_info_def *pi = get_ptr_info (ptr); 2086169689Skan 2087169689Skan pi->pt_anything = 1; 2088169689Skan pi->pt_vars = NULL; 2089169689Skan 2090169689Skan /* The pointer used to have a name tag, but we now found it pointing 2091169689Skan to an arbitrary location. The name tag needs to be renamed and 2092169689Skan disassociated from PTR. */ 2093169689Skan if (pi->name_mem_tag) 2094169689Skan { 2095169689Skan mark_sym_for_renaming (pi->name_mem_tag); 2096169689Skan pi->name_mem_tag = NULL_TREE; 2097169689Skan } 2098169689Skan} 2099169689Skan 2100169689Skan 2101169689Skan/* Return true if STMT is an "escape" site from the current function. Escape 2102169689Skan sites those statements which might expose the address of a variable 2103169689Skan outside the current function. STMT is an escape site iff: 2104169689Skan 2105169689Skan 1- STMT is a function call, or 2106169689Skan 2- STMT is an __asm__ expression, or 2107169689Skan 3- STMT is an assignment to a non-local variable, or 2108169689Skan 4- STMT is a return statement. 2109169689Skan 2110169689Skan Return the type of escape site found, if we found one, or NO_ESCAPE 2111169689Skan if none. */ 2112169689Skan 2113169689Skanenum escape_type 2114169689Skanis_escape_site (tree stmt) 2115169689Skan{ 2116169689Skan tree call = get_call_expr_in (stmt); 2117169689Skan if (call != NULL_TREE) 2118169689Skan { 2119169689Skan if (!TREE_SIDE_EFFECTS (call)) 2120169689Skan return ESCAPE_TO_PURE_CONST; 2121169689Skan 2122169689Skan return ESCAPE_TO_CALL; 2123169689Skan } 2124169689Skan else if (TREE_CODE (stmt) == ASM_EXPR) 2125169689Skan return ESCAPE_TO_ASM; 2126169689Skan else if (TREE_CODE (stmt) == MODIFY_EXPR) 2127169689Skan { 2128169689Skan tree lhs = TREE_OPERAND (stmt, 0); 2129169689Skan 2130169689Skan /* Get to the base of _REF nodes. */ 2131169689Skan if (TREE_CODE (lhs) != SSA_NAME) 2132169689Skan lhs = get_base_address (lhs); 2133169689Skan 2134169689Skan /* If we couldn't recognize the LHS of the assignment, assume that it 2135169689Skan is a non-local store. */ 2136169689Skan if (lhs == NULL_TREE) 2137169689Skan return ESCAPE_UNKNOWN; 2138169689Skan 2139169689Skan if (TREE_CODE (TREE_OPERAND (stmt, 1)) == NOP_EXPR 2140169689Skan || TREE_CODE (TREE_OPERAND (stmt, 1)) == CONVERT_EXPR 2141169689Skan || TREE_CODE (TREE_OPERAND (stmt, 1)) == VIEW_CONVERT_EXPR) 2142169689Skan { 2143169689Skan tree from = TREE_TYPE (TREE_OPERAND (TREE_OPERAND (stmt, 1), 0)); 2144169689Skan tree to = TREE_TYPE (TREE_OPERAND (stmt, 1)); 2145169689Skan 2146169689Skan /* If the RHS is a conversion between a pointer and an integer, the 2147169689Skan pointer escapes since we can't track the integer. */ 2148169689Skan if (POINTER_TYPE_P (from) && !POINTER_TYPE_P (to)) 2149169689Skan return ESCAPE_BAD_CAST; 2150169689Skan 2151169689Skan /* Same if the RHS is a conversion between a regular pointer and a 2152169689Skan ref-all pointer since we can't track the SMT of the former. */ 2153169689Skan if (POINTER_TYPE_P (from) && !TYPE_REF_CAN_ALIAS_ALL (from) 2154169689Skan && POINTER_TYPE_P (to) && TYPE_REF_CAN_ALIAS_ALL (to)) 2155169689Skan return ESCAPE_BAD_CAST; 2156169689Skan } 2157169689Skan 2158169689Skan /* If the LHS is an SSA name, it can't possibly represent a non-local 2159169689Skan memory store. */ 2160169689Skan if (TREE_CODE (lhs) == SSA_NAME) 2161169689Skan return NO_ESCAPE; 2162169689Skan 2163169689Skan /* FIXME: LHS is not an SSA_NAME. Even if it's an assignment to a 2164169689Skan local variables we cannot be sure if it will escape, because we 2165169689Skan don't have information about objects not in SSA form. Need to 2166169689Skan implement something along the lines of 2167169689Skan 2168169689Skan J.-D. Choi, M. Gupta, M. J. Serrano, V. C. Sreedhar, and S. P. 2169169689Skan Midkiff, ``Escape analysis for java,'' in Proceedings of the 2170169689Skan Conference on Object-Oriented Programming Systems, Languages, and 2171169689Skan Applications (OOPSLA), pp. 1-19, 1999. */ 2172169689Skan return ESCAPE_STORED_IN_GLOBAL; 2173169689Skan } 2174169689Skan else if (TREE_CODE (stmt) == RETURN_EXPR) 2175169689Skan return ESCAPE_TO_RETURN; 2176169689Skan 2177169689Skan return NO_ESCAPE; 2178169689Skan} 2179169689Skan 2180169689Skan/* Create a new memory tag of type TYPE. 2181169689Skan Does NOT push it into the current binding. */ 2182169689Skan 2183169689Skanstatic tree 2184169689Skancreate_tag_raw (enum tree_code code, tree type, const char *prefix) 2185169689Skan{ 2186169689Skan tree tmp_var; 2187169689Skan tree new_type; 2188169689Skan 2189169689Skan /* Make the type of the variable writable. */ 2190169689Skan new_type = build_type_variant (type, 0, 0); 2191169689Skan TYPE_ATTRIBUTES (new_type) = TYPE_ATTRIBUTES (type); 2192169689Skan 2193169689Skan tmp_var = build_decl (code, create_tmp_var_name (prefix), 2194169689Skan type); 2195169689Skan /* Make the variable writable. */ 2196169689Skan TREE_READONLY (tmp_var) = 0; 2197169689Skan 2198169689Skan /* It doesn't start out global. */ 2199169689Skan MTAG_GLOBAL (tmp_var) = 0; 2200169689Skan TREE_STATIC (tmp_var) = 0; 2201169689Skan TREE_USED (tmp_var) = 1; 2202169689Skan 2203169689Skan return tmp_var; 2204169689Skan} 2205169689Skan 2206169689Skan/* Create a new memory tag of type TYPE. If IS_TYPE_TAG is true, the tag 2207169689Skan is considered to represent all the pointers whose pointed-to types are 2208169689Skan in the same alias set class. Otherwise, the tag represents a single 2209169689Skan SSA_NAME pointer variable. */ 2210169689Skan 2211169689Skanstatic tree 2212169689Skancreate_memory_tag (tree type, bool is_type_tag) 2213169689Skan{ 2214169689Skan var_ann_t ann; 2215169689Skan tree tag = create_tag_raw (is_type_tag ? SYMBOL_MEMORY_TAG : NAME_MEMORY_TAG, 2216169689Skan type, (is_type_tag) ? "SMT" : "NMT"); 2217169689Skan 2218169689Skan /* By default, memory tags are local variables. Alias analysis will 2219169689Skan determine whether they should be considered globals. */ 2220169689Skan DECL_CONTEXT (tag) = current_function_decl; 2221169689Skan 2222169689Skan /* Memory tags are by definition addressable. */ 2223169689Skan TREE_ADDRESSABLE (tag) = 1; 2224169689Skan 2225169689Skan ann = get_var_ann (tag); 2226169689Skan ann->symbol_mem_tag = NULL_TREE; 2227169689Skan 2228169689Skan /* Add the tag to the symbol table. */ 2229169689Skan add_referenced_var (tag); 2230169689Skan 2231169689Skan return tag; 2232169689Skan} 2233169689Skan 2234169689Skan 2235169689Skan/* Create a name memory tag to represent a specific SSA_NAME pointer P_i. 2236169689Skan This is used if P_i has been found to point to a specific set of 2237169689Skan variables or to a non-aliased memory location like the address returned 2238169689Skan by malloc functions. */ 2239169689Skan 2240169689Skanstatic tree 2241169689Skanget_nmt_for (tree ptr) 2242169689Skan{ 2243169689Skan struct ptr_info_def *pi = get_ptr_info (ptr); 2244169689Skan tree tag = pi->name_mem_tag; 2245169689Skan 2246169689Skan if (tag == NULL_TREE) 2247169689Skan tag = create_memory_tag (TREE_TYPE (TREE_TYPE (ptr)), false); 2248169689Skan return tag; 2249169689Skan} 2250169689Skan 2251169689Skan 2252169689Skan/* Return the symbol memory tag associated to pointer PTR. A memory 2253169689Skan tag is an artificial variable that represents the memory location 2254169689Skan pointed-to by PTR. It is used to model the effects of pointer 2255169689Skan de-references on addressable variables. 2256169689Skan 2257169689Skan AI points to the data gathered during alias analysis. This 2258169689Skan function populates the array AI->POINTERS. */ 2259169689Skan 2260169689Skanstatic tree 2261169689Skanget_tmt_for (tree ptr, struct alias_info *ai) 2262169689Skan{ 2263169689Skan size_t i; 2264169689Skan tree tag; 2265169689Skan tree tag_type = TREE_TYPE (TREE_TYPE (ptr)); 2266169689Skan HOST_WIDE_INT tag_set = get_alias_set (tag_type); 2267169689Skan 2268169689Skan /* We use a unique memory tag for all the ref-all pointers. */ 2269169689Skan if (PTR_IS_REF_ALL (ptr)) 2270169689Skan { 2271169689Skan if (!ai->ref_all_symbol_mem_tag) 2272169689Skan ai->ref_all_symbol_mem_tag = create_memory_tag (void_type_node, true); 2273169689Skan return ai->ref_all_symbol_mem_tag; 2274169689Skan } 2275169689Skan 2276169689Skan /* To avoid creating unnecessary memory tags, only create one memory tag 2277169689Skan per alias set class. Note that it may be tempting to group 2278169689Skan memory tags based on conflicting alias sets instead of 2279169689Skan equivalence. That would be wrong because alias sets are not 2280169689Skan necessarily transitive (as demonstrated by the libstdc++ test 2281169689Skan 23_containers/vector/cons/4.cc). Given three alias sets A, B, C 2282169689Skan such that conflicts (A, B) == true and conflicts (A, C) == true, 2283169689Skan it does not necessarily follow that conflicts (B, C) == true. */ 2284169689Skan for (i = 0, tag = NULL_TREE; i < ai->num_pointers; i++) 2285169689Skan { 2286169689Skan struct alias_map_d *curr = ai->pointers[i]; 2287169689Skan tree curr_tag = var_ann (curr->var)->symbol_mem_tag; 2288169689Skan if (tag_set == curr->set) 2289169689Skan { 2290169689Skan tag = curr_tag; 2291169689Skan break; 2292169689Skan } 2293169689Skan } 2294169689Skan 2295169689Skan /* If VAR cannot alias with any of the existing memory tags, create a new 2296169689Skan tag for PTR and add it to the POINTERS array. */ 2297169689Skan if (tag == NULL_TREE) 2298169689Skan { 2299169689Skan struct alias_map_d *alias_map; 2300169689Skan 2301169689Skan /* If PTR did not have a symbol tag already, create a new SMT.* 2302169689Skan artificial variable representing the memory location 2303169689Skan pointed-to by PTR. */ 2304169689Skan if (var_ann (ptr)->symbol_mem_tag == NULL_TREE) 2305169689Skan tag = create_memory_tag (tag_type, true); 2306169689Skan else 2307169689Skan tag = var_ann (ptr)->symbol_mem_tag; 2308169689Skan 2309169689Skan /* Add PTR to the POINTERS array. Note that we are not interested in 2310169689Skan PTR's alias set. Instead, we cache the alias set for the memory that 2311169689Skan PTR points to. */ 2312169689Skan alias_map = XCNEW (struct alias_map_d); 2313169689Skan alias_map->var = ptr; 2314169689Skan alias_map->set = tag_set; 2315169689Skan ai->pointers[ai->num_pointers++] = alias_map; 2316169689Skan } 2317169689Skan 2318169689Skan /* If the pointed-to type is volatile, so is the tag. */ 2319169689Skan TREE_THIS_VOLATILE (tag) |= TREE_THIS_VOLATILE (tag_type); 2320169689Skan 2321169689Skan /* Make sure that the symbol tag has the same alias set as the 2322169689Skan pointed-to type. */ 2323169689Skan gcc_assert (tag_set == get_alias_set (tag)); 2324169689Skan 2325169689Skan return tag; 2326169689Skan} 2327169689Skan 2328169689Skan 2329169689Skan/* Create GLOBAL_VAR, an artificial global variable to act as a 2330169689Skan representative of all the variables that may be clobbered by function 2331169689Skan calls. */ 2332169689Skan 2333169689Skanstatic void 2334169689Skancreate_global_var (void) 2335169689Skan{ 2336169689Skan global_var = build_decl (VAR_DECL, get_identifier (".GLOBAL_VAR"), 2337169689Skan void_type_node); 2338169689Skan DECL_ARTIFICIAL (global_var) = 1; 2339169689Skan TREE_READONLY (global_var) = 0; 2340169689Skan DECL_EXTERNAL (global_var) = 1; 2341169689Skan TREE_STATIC (global_var) = 1; 2342169689Skan TREE_USED (global_var) = 1; 2343169689Skan DECL_CONTEXT (global_var) = NULL_TREE; 2344169689Skan TREE_THIS_VOLATILE (global_var) = 0; 2345169689Skan TREE_ADDRESSABLE (global_var) = 0; 2346169689Skan 2347169689Skan create_var_ann (global_var); 2348169689Skan mark_call_clobbered (global_var, ESCAPE_UNKNOWN); 2349169689Skan add_referenced_var (global_var); 2350169689Skan mark_sym_for_renaming (global_var); 2351169689Skan} 2352169689Skan 2353169689Skan 2354169689Skan/* Dump alias statistics on FILE. */ 2355169689Skan 2356169689Skanstatic void 2357169689Skandump_alias_stats (FILE *file) 2358169689Skan{ 2359169689Skan const char *funcname 2360169689Skan = lang_hooks.decl_printable_name (current_function_decl, 2); 2361169689Skan fprintf (file, "\nAlias statistics for %s\n\n", funcname); 2362169689Skan fprintf (file, "Total alias queries:\t%u\n", alias_stats.alias_queries); 2363169689Skan fprintf (file, "Total alias mayalias results:\t%u\n", 2364169689Skan alias_stats.alias_mayalias); 2365169689Skan fprintf (file, "Total alias noalias results:\t%u\n", 2366169689Skan alias_stats.alias_noalias); 2367169689Skan fprintf (file, "Total simple queries:\t%u\n", 2368169689Skan alias_stats.simple_queries); 2369169689Skan fprintf (file, "Total simple resolved:\t%u\n", 2370169689Skan alias_stats.simple_resolved); 2371169689Skan fprintf (file, "Total TBAA queries:\t%u\n", 2372169689Skan alias_stats.tbaa_queries); 2373169689Skan fprintf (file, "Total TBAA resolved:\t%u\n", 2374169689Skan alias_stats.tbaa_resolved); 2375169689Skan fprintf (file, "Total non-addressable structure type queries:\t%u\n", 2376169689Skan alias_stats.structnoaddress_queries); 2377169689Skan fprintf (file, "Total non-addressable structure type resolved:\t%u\n", 2378169689Skan alias_stats.structnoaddress_resolved); 2379169689Skan} 2380169689Skan 2381169689Skan 2382169689Skan/* Dump alias information on FILE. */ 2383169689Skan 2384169689Skanvoid 2385169689Skandump_alias_info (FILE *file) 2386169689Skan{ 2387169689Skan size_t i; 2388169689Skan const char *funcname 2389169689Skan = lang_hooks.decl_printable_name (current_function_decl, 2); 2390169689Skan referenced_var_iterator rvi; 2391169689Skan tree var; 2392169689Skan 2393169689Skan fprintf (file, "\nFlow-insensitive alias information for %s\n\n", funcname); 2394169689Skan 2395169689Skan fprintf (file, "Aliased symbols\n\n"); 2396169689Skan 2397169689Skan FOR_EACH_REFERENCED_VAR (var, rvi) 2398169689Skan { 2399169689Skan if (may_be_aliased (var)) 2400169689Skan dump_variable (file, var); 2401169689Skan } 2402169689Skan 2403169689Skan fprintf (file, "\nDereferenced pointers\n\n"); 2404169689Skan 2405169689Skan FOR_EACH_REFERENCED_VAR (var, rvi) 2406169689Skan { 2407169689Skan var_ann_t ann = var_ann (var); 2408169689Skan if (ann->symbol_mem_tag) 2409169689Skan dump_variable (file, var); 2410169689Skan } 2411169689Skan 2412169689Skan fprintf (file, "\nSymbol memory tags\n\n"); 2413169689Skan 2414169689Skan FOR_EACH_REFERENCED_VAR (var, rvi) 2415169689Skan { 2416169689Skan if (TREE_CODE (var) == SYMBOL_MEMORY_TAG) 2417169689Skan dump_variable (file, var); 2418169689Skan } 2419169689Skan 2420169689Skan fprintf (file, "\n\nFlow-sensitive alias information for %s\n\n", funcname); 2421169689Skan 2422169689Skan fprintf (file, "SSA_NAME pointers\n\n"); 2423169689Skan for (i = 1; i < num_ssa_names; i++) 2424169689Skan { 2425169689Skan tree ptr = ssa_name (i); 2426169689Skan struct ptr_info_def *pi; 2427169689Skan 2428169689Skan if (ptr == NULL_TREE) 2429169689Skan continue; 2430169689Skan 2431169689Skan pi = SSA_NAME_PTR_INFO (ptr); 2432169689Skan if (!SSA_NAME_IN_FREE_LIST (ptr) 2433169689Skan && pi 2434169689Skan && pi->name_mem_tag) 2435169689Skan dump_points_to_info_for (file, ptr); 2436169689Skan } 2437169689Skan 2438169689Skan fprintf (file, "\nName memory tags\n\n"); 2439169689Skan 2440169689Skan FOR_EACH_REFERENCED_VAR (var, rvi) 2441169689Skan { 2442169689Skan if (TREE_CODE (var) == NAME_MEMORY_TAG) 2443169689Skan dump_variable (file, var); 2444169689Skan } 2445169689Skan 2446169689Skan fprintf (file, "\n"); 2447169689Skan} 2448169689Skan 2449169689Skan 2450169689Skan/* Dump alias information on stderr. */ 2451169689Skan 2452169689Skanvoid 2453169689Skandebug_alias_info (void) 2454169689Skan{ 2455169689Skan dump_alias_info (stderr); 2456169689Skan} 2457169689Skan 2458169689Skan 2459169689Skan/* Return the alias information associated with pointer T. It creates a 2460169689Skan new instance if none existed. */ 2461169689Skan 2462169689Skanstruct ptr_info_def * 2463169689Skanget_ptr_info (tree t) 2464169689Skan{ 2465169689Skan struct ptr_info_def *pi; 2466169689Skan 2467169689Skan gcc_assert (POINTER_TYPE_P (TREE_TYPE (t))); 2468169689Skan 2469169689Skan pi = SSA_NAME_PTR_INFO (t); 2470169689Skan if (pi == NULL) 2471169689Skan { 2472169689Skan pi = GGC_NEW (struct ptr_info_def); 2473169689Skan memset ((void *)pi, 0, sizeof (*pi)); 2474169689Skan SSA_NAME_PTR_INFO (t) = pi; 2475169689Skan } 2476169689Skan 2477169689Skan return pi; 2478169689Skan} 2479169689Skan 2480169689Skan 2481169689Skan/* Dump points-to information for SSA_NAME PTR into FILE. */ 2482169689Skan 2483169689Skanvoid 2484169689Skandump_points_to_info_for (FILE *file, tree ptr) 2485169689Skan{ 2486169689Skan struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr); 2487169689Skan 2488169689Skan print_generic_expr (file, ptr, dump_flags); 2489169689Skan 2490169689Skan if (pi) 2491169689Skan { 2492169689Skan if (pi->name_mem_tag) 2493169689Skan { 2494169689Skan fprintf (file, ", name memory tag: "); 2495169689Skan print_generic_expr (file, pi->name_mem_tag, dump_flags); 2496169689Skan } 2497169689Skan 2498169689Skan if (pi->is_dereferenced) 2499169689Skan fprintf (file, ", is dereferenced"); 2500169689Skan 2501169689Skan if (pi->value_escapes_p) 2502169689Skan fprintf (file, ", its value escapes"); 2503169689Skan 2504169689Skan if (pi->pt_anything) 2505169689Skan fprintf (file, ", points-to anything"); 2506169689Skan 2507169689Skan if (pi->pt_null) 2508169689Skan fprintf (file, ", points-to NULL"); 2509169689Skan 2510169689Skan if (pi->pt_vars) 2511169689Skan { 2512169689Skan unsigned ix; 2513169689Skan bitmap_iterator bi; 2514169689Skan 2515169689Skan fprintf (file, ", points-to vars: { "); 2516169689Skan EXECUTE_IF_SET_IN_BITMAP (pi->pt_vars, 0, ix, bi) 2517169689Skan { 2518169689Skan print_generic_expr (file, referenced_var (ix), dump_flags); 2519169689Skan fprintf (file, " "); 2520169689Skan } 2521169689Skan fprintf (file, "}"); 2522169689Skan } 2523169689Skan } 2524169689Skan 2525169689Skan fprintf (file, "\n"); 2526169689Skan} 2527169689Skan 2528169689Skan 2529169689Skan/* Dump points-to information for VAR into stderr. */ 2530169689Skan 2531169689Skanvoid 2532169689Skandebug_points_to_info_for (tree var) 2533169689Skan{ 2534169689Skan dump_points_to_info_for (stderr, var); 2535169689Skan} 2536169689Skan 2537169689Skan 2538169689Skan/* Dump points-to information into FILE. NOTE: This function is slow, as 2539169689Skan it needs to traverse the whole CFG looking for pointer SSA_NAMEs. */ 2540169689Skan 2541169689Skanvoid 2542169689Skandump_points_to_info (FILE *file) 2543169689Skan{ 2544169689Skan basic_block bb; 2545169689Skan block_stmt_iterator si; 2546169689Skan ssa_op_iter iter; 2547169689Skan const char *fname = 2548169689Skan lang_hooks.decl_printable_name (current_function_decl, 2); 2549169689Skan referenced_var_iterator rvi; 2550169689Skan tree var; 2551169689Skan 2552169689Skan fprintf (file, "\n\nPointed-to sets for pointers in %s\n\n", fname); 2553169689Skan 2554169689Skan /* First dump points-to information for the default definitions of 2555169689Skan pointer variables. This is necessary because default definitions are 2556169689Skan not part of the code. */ 2557169689Skan FOR_EACH_REFERENCED_VAR (var, rvi) 2558169689Skan { 2559169689Skan if (POINTER_TYPE_P (TREE_TYPE (var))) 2560169689Skan { 2561169689Skan tree def = default_def (var); 2562169689Skan if (def) 2563169689Skan dump_points_to_info_for (file, def); 2564169689Skan } 2565169689Skan } 2566169689Skan 2567169689Skan /* Dump points-to information for every pointer defined in the program. */ 2568169689Skan FOR_EACH_BB (bb) 2569169689Skan { 2570169689Skan tree phi; 2571169689Skan 2572169689Skan for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 2573169689Skan { 2574169689Skan tree ptr = PHI_RESULT (phi); 2575169689Skan if (POINTER_TYPE_P (TREE_TYPE (ptr))) 2576169689Skan dump_points_to_info_for (file, ptr); 2577169689Skan } 2578169689Skan 2579169689Skan for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si)) 2580169689Skan { 2581169689Skan tree stmt = bsi_stmt (si); 2582169689Skan tree def; 2583169689Skan FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF) 2584169689Skan if (POINTER_TYPE_P (TREE_TYPE (def))) 2585169689Skan dump_points_to_info_for (file, def); 2586169689Skan } 2587169689Skan } 2588169689Skan 2589169689Skan fprintf (file, "\n"); 2590169689Skan} 2591169689Skan 2592169689Skan 2593169689Skan/* Dump points-to info pointed to by PTO into STDERR. */ 2594169689Skan 2595169689Skanvoid 2596169689Skandebug_points_to_info (void) 2597169689Skan{ 2598169689Skan dump_points_to_info (stderr); 2599169689Skan} 2600169689Skan 2601169689Skan/* Dump to FILE the list of variables that may be aliasing VAR. */ 2602169689Skan 2603169689Skanvoid 2604169689Skandump_may_aliases_for (FILE *file, tree var) 2605169689Skan{ 2606169689Skan VEC(tree, gc) *aliases; 2607169689Skan 2608169689Skan if (TREE_CODE (var) == SSA_NAME) 2609169689Skan var = SSA_NAME_VAR (var); 2610169689Skan 2611169689Skan aliases = var_ann (var)->may_aliases; 2612169689Skan if (aliases) 2613169689Skan { 2614169689Skan size_t i; 2615169689Skan tree al; 2616169689Skan fprintf (file, "{ "); 2617169689Skan for (i = 0; VEC_iterate (tree, aliases, i, al); i++) 2618169689Skan { 2619169689Skan print_generic_expr (file, al, dump_flags); 2620169689Skan fprintf (file, " "); 2621169689Skan } 2622169689Skan fprintf (file, "}"); 2623169689Skan } 2624169689Skan} 2625169689Skan 2626169689Skan 2627169689Skan/* Dump to stderr the list of variables that may be aliasing VAR. */ 2628169689Skan 2629169689Skanvoid 2630169689Skandebug_may_aliases_for (tree var) 2631169689Skan{ 2632169689Skan dump_may_aliases_for (stderr, var); 2633169689Skan} 2634169689Skan 2635169689Skan/* Return true if VAR may be aliased. */ 2636169689Skan 2637169689Skanbool 2638169689Skanmay_be_aliased (tree var) 2639169689Skan{ 2640169689Skan /* Obviously. */ 2641169689Skan if (TREE_ADDRESSABLE (var)) 2642169689Skan return true; 2643169689Skan 2644169689Skan /* Globally visible variables can have their addresses taken by other 2645169689Skan translation units. */ 2646169689Skan 2647169689Skan if (MTAG_P (var) 2648169689Skan && (MTAG_GLOBAL (var) || TREE_PUBLIC (var))) 2649169689Skan return true; 2650169689Skan else if (!MTAG_P (var) 2651169689Skan && (DECL_EXTERNAL (var) || TREE_PUBLIC (var))) 2652169689Skan return true; 2653169689Skan 2654169689Skan /* Automatic variables can't have their addresses escape any other way. 2655169689Skan This must be after the check for global variables, as extern declarations 2656169689Skan do not have TREE_STATIC set. */ 2657169689Skan if (!TREE_STATIC (var)) 2658169689Skan return false; 2659169689Skan 2660169689Skan /* If we're in unit-at-a-time mode, then we must have seen all occurrences 2661169689Skan of address-of operators, and so we can trust TREE_ADDRESSABLE. Otherwise 2662169689Skan we can only be sure the variable isn't addressable if it's local to the 2663169689Skan current function. */ 2664169689Skan if (flag_unit_at_a_time) 2665169689Skan return false; 2666169689Skan if (decl_function_context (var) == current_function_decl) 2667169689Skan return false; 2668169689Skan 2669169689Skan return true; 2670169689Skan} 2671169689Skan 2672169689Skan 2673169689Skan/* Given two symbols return TRUE if one is in the alias set of the other. */ 2674169689Skanbool 2675169689Skanis_aliased_with (tree tag, tree sym) 2676169689Skan{ 2677169689Skan size_t i; 2678169689Skan VEC(tree,gc) *aliases; 2679169689Skan tree al; 2680169689Skan 2681169689Skan if (var_ann (sym)->is_aliased) 2682169689Skan { 2683169689Skan aliases = var_ann (tag)->may_aliases; 2684169689Skan 2685169689Skan if (aliases == NULL) 2686169689Skan return false; 2687169689Skan 2688169689Skan for (i = 0; VEC_iterate (tree, aliases, i, al); i++) 2689169689Skan if (al == sym) 2690169689Skan return true; 2691169689Skan } 2692169689Skan else 2693169689Skan { 2694169689Skan aliases = var_ann (sym)->may_aliases; 2695169689Skan 2696169689Skan if (aliases == NULL) 2697169689Skan return false; 2698169689Skan 2699169689Skan for (i = 0; VEC_iterate (tree, aliases, i, al); i++) 2700169689Skan if (al == tag) 2701169689Skan return true; 2702169689Skan } 2703169689Skan 2704169689Skan return false; 2705169689Skan} 2706169689Skan 2707169689Skan 2708169689Skan/* Given two tags return TRUE if their may-alias sets intersect. */ 2709169689Skan 2710169689Skanbool 2711169689Skanmay_aliases_intersect (tree tag1, tree tag2) 2712169689Skan{ 2713169689Skan struct pointer_set_t *set1 = pointer_set_create (); 2714169689Skan unsigned i; 2715169689Skan VEC(tree,gc) *may_aliases1 = may_aliases (tag1); 2716169689Skan VEC(tree,gc) *may_aliases2 = may_aliases (tag2); 2717169689Skan tree sym; 2718169689Skan 2719169689Skan /* Insert all the symbols from the first may-alias set into the 2720169689Skan pointer-set. */ 2721169689Skan for (i = 0; VEC_iterate (tree, may_aliases1, i, sym); i++) 2722169689Skan pointer_set_insert (set1, sym); 2723169689Skan 2724169689Skan /* Go through the second may-alias set and check if it contains symbols that 2725169689Skan are common with the first set. */ 2726169689Skan for (i = 0; VEC_iterate (tree, may_aliases2, i, sym); i++) 2727169689Skan if (pointer_set_contains (set1, sym)) 2728169689Skan { 2729169689Skan pointer_set_destroy (set1); 2730169689Skan return true; 2731169689Skan } 2732169689Skan 2733169689Skan pointer_set_destroy (set1); 2734169689Skan return false; 2735169689Skan} 2736169689Skan 2737169689Skan 2738169689Skan/* The following is based on code in add_stmt_operand to ensure that the 2739169689Skan same defs/uses/vdefs/vuses will be found after replacing a reference 2740169689Skan to var (or ARRAY_REF to var) with an INDIRECT_REF to ptr whose value 2741169689Skan is the address of var. Return a memtag for the ptr, after adding the 2742169689Skan proper may_aliases to it (which are the aliases of var, if it has any, 2743169689Skan or var itself). */ 2744169689Skan 2745169689Skanstatic tree 2746169689Skanadd_may_alias_for_new_tag (tree tag, tree var) 2747169689Skan{ 2748169689Skan var_ann_t v_ann = var_ann (var); 2749169689Skan VEC(tree, gc) *aliases = v_ann->may_aliases; 2750169689Skan 2751169689Skan /* Case 1: |aliases| == 1 */ 2752169689Skan if ((aliases != NULL) 2753169689Skan && (VEC_length (tree, aliases) == 1)) 2754169689Skan { 2755169689Skan tree ali = VEC_index (tree, aliases, 0); 2756169689Skan 2757169689Skan if (TREE_CODE (ali) == SYMBOL_MEMORY_TAG) 2758169689Skan return ali; 2759169689Skan } 2760169689Skan 2761169689Skan /* Case 2: |aliases| == 0 */ 2762169689Skan if (aliases == NULL) 2763169689Skan add_may_alias (tag, var); 2764169689Skan else 2765169689Skan { 2766169689Skan /* Case 3: |aliases| > 1 */ 2767169689Skan unsigned i; 2768169689Skan tree al; 2769169689Skan 2770169689Skan for (i = 0; VEC_iterate (tree, aliases, i, al); i++) 2771169689Skan add_may_alias (tag, al); 2772169689Skan } 2773169689Skan 2774169689Skan return tag; 2775169689Skan} 2776169689Skan 2777169689Skan/* Create a new symbol tag for PTR. Construct the may-alias list of this type 2778169689Skan tag so that it has the aliasing of VAR, or of the relevant subvars of VAR 2779169689Skan according to the location accessed by EXPR. 2780169689Skan 2781169689Skan Note, the set of aliases represented by the new symbol tag are not marked 2782169689Skan for renaming. */ 2783169689Skan 2784169689Skanvoid 2785169689Skannew_type_alias (tree ptr, tree var, tree expr) 2786169689Skan{ 2787169689Skan var_ann_t p_ann = var_ann (ptr); 2788169689Skan tree tag_type = TREE_TYPE (TREE_TYPE (ptr)); 2789169689Skan tree tag; 2790169689Skan subvar_t svars; 2791169689Skan tree ali = NULL_TREE; 2792169689Skan HOST_WIDE_INT offset, size, maxsize; 2793169689Skan tree ref; 2794169689Skan 2795169689Skan gcc_assert (p_ann->symbol_mem_tag == NULL_TREE); 2796169689Skan gcc_assert (!MTAG_P (var)); 2797169689Skan 2798169689Skan ref = get_ref_base_and_extent (expr, &offset, &size, &maxsize); 2799169689Skan gcc_assert (ref); 2800169689Skan 2801169689Skan tag = create_memory_tag (tag_type, true); 2802169689Skan p_ann->symbol_mem_tag = tag; 2803169689Skan 2804169689Skan /* Add VAR to the may-alias set of PTR's new symbol tag. If VAR has 2805169689Skan subvars, add the subvars to the tag instead of the actual var. */ 2806169689Skan if (var_can_have_subvars (var) 2807169689Skan && (svars = get_subvars_for_var (var))) 2808169689Skan { 2809169689Skan subvar_t sv; 2810169689Skan VEC (tree, heap) *overlaps = NULL; 2811169689Skan unsigned int len; 2812169689Skan 2813169689Skan for (sv = svars; sv; sv = sv->next) 2814169689Skan { 2815169689Skan bool exact; 2816169689Skan 2817169689Skan if (overlap_subvar (offset, maxsize, sv->var, &exact)) 2818169689Skan VEC_safe_push (tree, heap, overlaps, sv->var); 2819169689Skan } 2820169689Skan len = VEC_length (tree, overlaps); 2821169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 2822169689Skan fprintf (dump_file, "\nnumber of overlapping subvars = %u\n", len); 2823169689Skan gcc_assert (len); 2824169689Skan 2825169689Skan if (len == 1) 2826169689Skan ali = add_may_alias_for_new_tag (tag, VEC_index (tree, overlaps, 0)); 2827169689Skan else if (len > 1) 2828169689Skan { 2829169689Skan unsigned int k; 2830169689Skan tree sv_var; 2831169689Skan 2832169689Skan for (k = 0; VEC_iterate (tree, overlaps, k, sv_var); k++) 2833169689Skan { 2834169689Skan ali = add_may_alias_for_new_tag (tag, sv_var); 2835169689Skan 2836169689Skan if (ali != tag) 2837169689Skan { 2838169689Skan /* Can happen only if 'Case 1' of add_may_alias_for_new_tag 2839169689Skan took place. Since more than one svar was found, we add 2840169689Skan 'ali' as one of the may_aliases of the new tag. */ 2841169689Skan add_may_alias (tag, ali); 2842169689Skan ali = tag; 2843169689Skan } 2844169689Skan } 2845169689Skan } 2846169689Skan } 2847169689Skan else 2848169689Skan ali = add_may_alias_for_new_tag (tag, var); 2849169689Skan 2850169689Skan p_ann->symbol_mem_tag = ali; 2851169689Skan TREE_READONLY (tag) = TREE_READONLY (var); 2852169689Skan MTAG_GLOBAL (tag) = is_global_var (var); 2853169689Skan} 2854169689Skan 2855169689Skan/* This represents the used range of a variable. */ 2856169689Skan 2857169689Skantypedef struct used_part 2858169689Skan{ 2859169689Skan HOST_WIDE_INT minused; 2860169689Skan HOST_WIDE_INT maxused; 2861169689Skan /* True if we have an explicit use/def of some portion of this variable, 2862169689Skan even if it is all of it. i.e. a.b = 5 or temp = a.b. */ 2863169689Skan bool explicit_uses; 2864169689Skan /* True if we have an implicit use/def of some portion of this 2865169689Skan variable. Implicit uses occur when we can't tell what part we 2866169689Skan are referencing, and have to make conservative assumptions. */ 2867169689Skan bool implicit_uses; 2868169689Skan /* True if the structure is only written to or taken its address. */ 2869169689Skan bool write_only; 2870169689Skan} *used_part_t; 2871169689Skan 2872169689Skan/* An array of used_part structures, indexed by variable uid. */ 2873169689Skan 2874169689Skanstatic htab_t used_portions; 2875169689Skan 2876169689Skanstruct used_part_map 2877169689Skan{ 2878169689Skan unsigned int uid; 2879169689Skan used_part_t to; 2880169689Skan}; 2881169689Skan 2882169689Skan/* Return true if the uid in the two used part maps are equal. */ 2883169689Skan 2884169689Skanstatic int 2885169689Skanused_part_map_eq (const void *va, const void *vb) 2886169689Skan{ 2887169689Skan const struct used_part_map *a = (const struct used_part_map *) va; 2888169689Skan const struct used_part_map *b = (const struct used_part_map *) vb; 2889169689Skan return (a->uid == b->uid); 2890169689Skan} 2891169689Skan 2892169689Skan/* Hash a from uid in a used_part_map. */ 2893169689Skan 2894169689Skanstatic unsigned int 2895169689Skanused_part_map_hash (const void *item) 2896169689Skan{ 2897169689Skan return ((const struct used_part_map *)item)->uid; 2898169689Skan} 2899169689Skan 2900169689Skan/* Free a used part map element. */ 2901169689Skan 2902169689Skanstatic void 2903169689Skanfree_used_part_map (void *item) 2904169689Skan{ 2905169689Skan free (((struct used_part_map *)item)->to); 2906169689Skan free (item); 2907169689Skan} 2908169689Skan 2909169689Skan/* Lookup a used_part structure for a UID. */ 2910169689Skan 2911169689Skanstatic used_part_t 2912169689Skanup_lookup (unsigned int uid) 2913169689Skan{ 2914169689Skan struct used_part_map *h, in; 2915169689Skan in.uid = uid; 2916169689Skan h = (struct used_part_map *) htab_find_with_hash (used_portions, &in, uid); 2917169689Skan if (!h) 2918169689Skan return NULL; 2919169689Skan return h->to; 2920169689Skan} 2921169689Skan 2922169689Skan/* Insert the pair UID, TO into the used part hashtable. */ 2923169689Skan 2924169689Skanstatic void 2925169689Skanup_insert (unsigned int uid, used_part_t to) 2926169689Skan{ 2927169689Skan struct used_part_map *h; 2928169689Skan void **loc; 2929169689Skan 2930169689Skan h = XNEW (struct used_part_map); 2931169689Skan h->uid = uid; 2932169689Skan h->to = to; 2933169689Skan loc = htab_find_slot_with_hash (used_portions, h, 2934169689Skan uid, INSERT); 2935169689Skan if (*loc != NULL) 2936169689Skan free (*loc); 2937169689Skan *(struct used_part_map **) loc = h; 2938169689Skan} 2939169689Skan 2940169689Skan 2941169689Skan/* Given a variable uid, UID, get or create the entry in the used portions 2942169689Skan table for the variable. */ 2943169689Skan 2944169689Skanstatic used_part_t 2945169689Skanget_or_create_used_part_for (size_t uid) 2946169689Skan{ 2947169689Skan used_part_t up; 2948169689Skan if ((up = up_lookup (uid)) == NULL) 2949169689Skan { 2950169689Skan up = XCNEW (struct used_part); 2951169689Skan up->minused = INT_MAX; 2952169689Skan up->maxused = 0; 2953169689Skan up->explicit_uses = false; 2954169689Skan up->implicit_uses = false; 2955169689Skan up->write_only = true; 2956169689Skan } 2957169689Skan 2958169689Skan return up; 2959169689Skan} 2960169689Skan 2961169689Skan 2962169689Skan/* Create and return a structure sub-variable for field type FIELD at 2963169689Skan offset OFFSET, with size SIZE, of variable VAR. */ 2964169689Skan 2965169689Skanstatic tree 2966169689Skancreate_sft (tree var, tree field, unsigned HOST_WIDE_INT offset, 2967169689Skan unsigned HOST_WIDE_INT size) 2968169689Skan{ 2969169689Skan var_ann_t ann; 2970169689Skan tree subvar = create_tag_raw (STRUCT_FIELD_TAG, field, "SFT"); 2971169689Skan 2972169689Skan /* We need to copy the various flags from VAR to SUBVAR, so that 2973169689Skan they are is_global_var iff the original variable was. */ 2974169689Skan DECL_CONTEXT (subvar) = DECL_CONTEXT (var); 2975169689Skan MTAG_GLOBAL (subvar) = DECL_EXTERNAL (var); 2976169689Skan TREE_PUBLIC (subvar) = TREE_PUBLIC (var); 2977169689Skan TREE_STATIC (subvar) = TREE_STATIC (var); 2978169689Skan TREE_READONLY (subvar) = TREE_READONLY (var); 2979169689Skan TREE_ADDRESSABLE (subvar) = TREE_ADDRESSABLE (var); 2980169689Skan 2981169689Skan /* Add the new variable to REFERENCED_VARS. */ 2982169689Skan ann = get_var_ann (subvar); 2983169689Skan ann->symbol_mem_tag = NULL; 2984169689Skan add_referenced_var (subvar); 2985169689Skan SFT_PARENT_VAR (subvar) = var; 2986169689Skan SFT_OFFSET (subvar) = offset; 2987169689Skan SFT_SIZE (subvar) = size; 2988169689Skan return subvar; 2989169689Skan} 2990169689Skan 2991169689Skan 2992169689Skan/* Given an aggregate VAR, create the subvariables that represent its 2993169689Skan fields. */ 2994169689Skan 2995169689Skanstatic void 2996169689Skancreate_overlap_variables_for (tree var) 2997169689Skan{ 2998169689Skan VEC(fieldoff_s,heap) *fieldstack = NULL; 2999169689Skan used_part_t up; 3000169689Skan size_t uid = DECL_UID (var); 3001169689Skan 3002169689Skan up = up_lookup (uid); 3003169689Skan if (!up 3004169689Skan || up->write_only) 3005169689Skan return; 3006169689Skan 3007169689Skan push_fields_onto_fieldstack (TREE_TYPE (var), &fieldstack, 0, NULL); 3008169689Skan if (VEC_length (fieldoff_s, fieldstack) != 0) 3009169689Skan { 3010169689Skan subvar_t *subvars; 3011169689Skan fieldoff_s *fo; 3012169689Skan bool notokay = false; 3013169689Skan int fieldcount = 0; 3014169689Skan int i; 3015169689Skan HOST_WIDE_INT lastfooffset = -1; 3016169689Skan HOST_WIDE_INT lastfosize = -1; 3017169689Skan tree lastfotype = NULL_TREE; 3018169689Skan 3019169689Skan /* Not all fields have DECL_SIZE set, and those that don't, we don't 3020169689Skan know their size, and thus, can't handle. 3021169689Skan The same is true of fields with DECL_SIZE that is not an integer 3022169689Skan constant (such as variable sized fields). 3023169689Skan Fields with offsets which are not constant will have an offset < 0 3024169689Skan We *could* handle fields that are constant sized arrays, but 3025169689Skan currently don't. Doing so would require some extra changes to 3026169689Skan tree-ssa-operands.c. */ 3027169689Skan 3028169689Skan for (i = 0; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++) 3029169689Skan { 3030169689Skan if (!fo->size 3031169689Skan || TREE_CODE (fo->size) != INTEGER_CST 3032169689Skan || fo->offset < 0) 3033169689Skan { 3034169689Skan notokay = true; 3035169689Skan break; 3036169689Skan } 3037169689Skan fieldcount++; 3038169689Skan } 3039169689Skan 3040169689Skan /* The current heuristic we use is as follows: 3041169689Skan If the variable has no used portions in this function, no 3042169689Skan structure vars are created for it. 3043169689Skan Otherwise, 3044169689Skan If the variable has less than SALIAS_MAX_IMPLICIT_FIELDS, 3045169689Skan we always create structure vars for them. 3046169689Skan If the variable has more than SALIAS_MAX_IMPLICIT_FIELDS, and 3047169689Skan some explicit uses, we create structure vars for them. 3048169689Skan If the variable has more than SALIAS_MAX_IMPLICIT_FIELDS, and 3049169689Skan no explicit uses, we do not create structure vars for them. 3050169689Skan */ 3051169689Skan 3052169689Skan if (fieldcount >= SALIAS_MAX_IMPLICIT_FIELDS 3053169689Skan && !up->explicit_uses) 3054169689Skan { 3055169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 3056169689Skan { 3057169689Skan fprintf (dump_file, "Variable "); 3058169689Skan print_generic_expr (dump_file, var, 0); 3059169689Skan fprintf (dump_file, " has no explicit uses in this function, and is > SALIAS_MAX_IMPLICIT_FIELDS, so skipping\n"); 3060169689Skan } 3061169689Skan notokay = true; 3062169689Skan } 3063169689Skan 3064169689Skan /* Bail out, if we can't create overlap variables. */ 3065169689Skan if (notokay) 3066169689Skan { 3067169689Skan VEC_free (fieldoff_s, heap, fieldstack); 3068169689Skan return; 3069169689Skan } 3070169689Skan 3071169689Skan /* Otherwise, create the variables. */ 3072169689Skan subvars = lookup_subvars_for_var (var); 3073169689Skan 3074169689Skan sort_fieldstack (fieldstack); 3075169689Skan 3076169689Skan for (i = VEC_length (fieldoff_s, fieldstack); 3077169689Skan VEC_iterate (fieldoff_s, fieldstack, --i, fo);) 3078169689Skan { 3079169689Skan subvar_t sv; 3080169689Skan HOST_WIDE_INT fosize; 3081169689Skan tree currfotype; 3082169689Skan 3083169689Skan fosize = TREE_INT_CST_LOW (fo->size); 3084169689Skan currfotype = fo->type; 3085169689Skan 3086169689Skan /* If this field isn't in the used portion, 3087169689Skan or it has the exact same offset and size as the last 3088169689Skan field, skip it. */ 3089169689Skan 3090169689Skan if (((fo->offset <= up->minused 3091169689Skan && fo->offset + fosize <= up->minused) 3092169689Skan || fo->offset >= up->maxused) 3093169689Skan || (fo->offset == lastfooffset 3094169689Skan && fosize == lastfosize 3095169689Skan && currfotype == lastfotype)) 3096169689Skan continue; 3097169689Skan sv = GGC_NEW (struct subvar); 3098169689Skan sv->next = *subvars; 3099169689Skan sv->var = create_sft (var, fo->type, fo->offset, fosize); 3100169689Skan 3101169689Skan if (dump_file) 3102169689Skan { 3103169689Skan fprintf (dump_file, "structure field tag %s created for var %s", 3104169689Skan get_name (sv->var), get_name (var)); 3105169689Skan fprintf (dump_file, " offset " HOST_WIDE_INT_PRINT_DEC, 3106169689Skan SFT_OFFSET (sv->var)); 3107169689Skan fprintf (dump_file, " size " HOST_WIDE_INT_PRINT_DEC, 3108169689Skan SFT_SIZE (sv->var)); 3109169689Skan fprintf (dump_file, "\n"); 3110169689Skan } 3111169689Skan 3112169689Skan lastfotype = currfotype; 3113169689Skan lastfooffset = fo->offset; 3114169689Skan lastfosize = fosize; 3115169689Skan *subvars = sv; 3116169689Skan } 3117169689Skan 3118169689Skan /* Once we have created subvars, the original is no longer call 3119169689Skan clobbered on its own. Its call clobbered status depends 3120169689Skan completely on the call clobbered status of the subvars. 3121169689Skan 3122169689Skan add_referenced_var in the above loop will take care of 3123169689Skan marking subvars of global variables as call clobbered for us 3124169689Skan to start, since they are global as well. */ 3125169689Skan clear_call_clobbered (var); 3126169689Skan } 3127169689Skan 3128169689Skan VEC_free (fieldoff_s, heap, fieldstack); 3129169689Skan} 3130169689Skan 3131169689Skan 3132169689Skan/* Find the conservative answer to the question of what portions of what 3133169689Skan structures are used by this statement. We assume that if we have a 3134169689Skan component ref with a known size + offset, that we only need that part 3135169689Skan of the structure. For unknown cases, or cases where we do something 3136169689Skan to the whole structure, we assume we need to create fields for the 3137169689Skan entire structure. */ 3138169689Skan 3139169689Skanstatic tree 3140169689Skanfind_used_portions (tree *tp, int *walk_subtrees, void *lhs_p) 3141169689Skan{ 3142169689Skan switch (TREE_CODE (*tp)) 3143169689Skan { 3144169689Skan case MODIFY_EXPR: 3145169689Skan /* Recurse manually here to track whether the use is in the 3146169689Skan LHS of an assignment. */ 3147169689Skan find_used_portions (&TREE_OPERAND (*tp, 0), walk_subtrees, tp); 3148169689Skan return find_used_portions (&TREE_OPERAND (*tp, 1), walk_subtrees, NULL); 3149169689Skan case REALPART_EXPR: 3150169689Skan case IMAGPART_EXPR: 3151169689Skan case COMPONENT_REF: 3152169689Skan case ARRAY_REF: 3153169689Skan { 3154169689Skan HOST_WIDE_INT bitsize; 3155169689Skan HOST_WIDE_INT bitmaxsize; 3156169689Skan HOST_WIDE_INT bitpos; 3157169689Skan tree ref; 3158169689Skan ref = get_ref_base_and_extent (*tp, &bitpos, &bitsize, &bitmaxsize); 3159169689Skan if (DECL_P (ref) 3160169689Skan && var_can_have_subvars (ref) 3161169689Skan && bitmaxsize != -1) 3162169689Skan { 3163169689Skan size_t uid = DECL_UID (ref); 3164169689Skan used_part_t up; 3165169689Skan 3166169689Skan up = get_or_create_used_part_for (uid); 3167169689Skan 3168169689Skan if (bitpos <= up->minused) 3169169689Skan up->minused = bitpos; 3170169689Skan if ((bitpos + bitmaxsize >= up->maxused)) 3171169689Skan up->maxused = bitpos + bitmaxsize; 3172169689Skan 3173169689Skan if (bitsize == bitmaxsize) 3174169689Skan up->explicit_uses = true; 3175169689Skan else 3176169689Skan up->implicit_uses = true; 3177169689Skan if (!lhs_p) 3178169689Skan up->write_only = false; 3179169689Skan up_insert (uid, up); 3180169689Skan 3181169689Skan *walk_subtrees = 0; 3182169689Skan return NULL_TREE; 3183169689Skan } 3184169689Skan } 3185169689Skan break; 3186169689Skan /* This is here to make sure we mark the entire base variable as used 3187169689Skan when you take its address. Because our used portion analysis is 3188169689Skan simple, we aren't looking at casts or pointer arithmetic to see what 3189169689Skan happens when you take the address. */ 3190169689Skan case ADDR_EXPR: 3191169689Skan { 3192169689Skan tree var = get_base_address (TREE_OPERAND (*tp, 0)); 3193169689Skan 3194169689Skan if (var 3195169689Skan && DECL_P (var) 3196169689Skan && DECL_SIZE (var) 3197169689Skan && var_can_have_subvars (var) 3198169689Skan && TREE_CODE (DECL_SIZE (var)) == INTEGER_CST) 3199169689Skan { 3200169689Skan used_part_t up; 3201169689Skan size_t uid = DECL_UID (var); 3202169689Skan 3203169689Skan up = get_or_create_used_part_for (uid); 3204169689Skan 3205169689Skan up->minused = 0; 3206169689Skan up->maxused = TREE_INT_CST_LOW (DECL_SIZE (var)); 3207169689Skan up->implicit_uses = true; 3208169689Skan if (!lhs_p) 3209169689Skan up->write_only = false; 3210169689Skan 3211169689Skan up_insert (uid, up); 3212169689Skan *walk_subtrees = 0; 3213169689Skan return NULL_TREE; 3214169689Skan } 3215169689Skan } 3216169689Skan break; 3217169689Skan case CALL_EXPR: 3218169689Skan { 3219169689Skan tree *arg; 3220169689Skan for (arg = &TREE_OPERAND (*tp, 1); *arg; arg = &TREE_CHAIN (*arg)) 3221169689Skan { 3222169689Skan if (TREE_CODE (TREE_VALUE (*arg)) != ADDR_EXPR) 3223169689Skan find_used_portions (&TREE_VALUE (*arg), walk_subtrees, NULL); 3224169689Skan } 3225169689Skan *walk_subtrees = 0; 3226169689Skan return NULL_TREE; 3227169689Skan } 3228169689Skan case VAR_DECL: 3229169689Skan case PARM_DECL: 3230169689Skan case RESULT_DECL: 3231169689Skan { 3232169689Skan tree var = *tp; 3233169689Skan if (DECL_SIZE (var) 3234169689Skan && var_can_have_subvars (var) 3235169689Skan && TREE_CODE (DECL_SIZE (var)) == INTEGER_CST) 3236169689Skan { 3237169689Skan used_part_t up; 3238169689Skan size_t uid = DECL_UID (var); 3239169689Skan 3240169689Skan up = get_or_create_used_part_for (uid); 3241169689Skan 3242169689Skan up->minused = 0; 3243169689Skan up->maxused = TREE_INT_CST_LOW (DECL_SIZE (var)); 3244169689Skan up->implicit_uses = true; 3245169689Skan 3246169689Skan up_insert (uid, up); 3247169689Skan *walk_subtrees = 0; 3248169689Skan return NULL_TREE; 3249169689Skan } 3250169689Skan } 3251169689Skan break; 3252169689Skan 3253169689Skan default: 3254169689Skan break; 3255169689Skan 3256169689Skan } 3257169689Skan return NULL_TREE; 3258169689Skan} 3259169689Skan 3260169689Skan/* Create structure field variables for structures used in this function. */ 3261169689Skan 3262169689Skanstatic unsigned int 3263169689Skancreate_structure_vars (void) 3264169689Skan{ 3265169689Skan basic_block bb; 3266169689Skan safe_referenced_var_iterator rvi; 3267169689Skan VEC (tree, heap) *varvec = NULL; 3268169689Skan tree var; 3269169689Skan 3270169689Skan used_portions = htab_create (10, used_part_map_hash, used_part_map_eq, 3271169689Skan free_used_part_map); 3272169689Skan 3273169689Skan FOR_EACH_BB (bb) 3274169689Skan { 3275169689Skan block_stmt_iterator bsi; 3276169689Skan for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 3277169689Skan { 3278169689Skan walk_tree_without_duplicates (bsi_stmt_ptr (bsi), 3279169689Skan find_used_portions, 3280169689Skan NULL); 3281169689Skan } 3282169689Skan } 3283169689Skan FOR_EACH_REFERENCED_VAR_SAFE (var, varvec, rvi) 3284169689Skan { 3285169689Skan /* The C++ FE creates vars without DECL_SIZE set, for some reason. */ 3286169689Skan if (var 3287169689Skan && DECL_SIZE (var) 3288169689Skan && var_can_have_subvars (var) 3289169689Skan && !MTAG_P (var) 3290169689Skan && TREE_CODE (DECL_SIZE (var)) == INTEGER_CST) 3291169689Skan create_overlap_variables_for (var); 3292169689Skan } 3293169689Skan htab_delete (used_portions); 3294169689Skan VEC_free (tree, heap, varvec); 3295169689Skan return 0; 3296169689Skan} 3297169689Skan 3298169689Skanstatic bool 3299169689Skangate_structure_vars (void) 3300169689Skan{ 3301169689Skan return flag_tree_salias != 0; 3302169689Skan} 3303169689Skan 3304169689Skanstruct tree_opt_pass pass_create_structure_vars = 3305169689Skan{ 3306169689Skan "salias", /* name */ 3307169689Skan gate_structure_vars, /* gate */ 3308169689Skan create_structure_vars, /* execute */ 3309169689Skan NULL, /* sub */ 3310169689Skan NULL, /* next */ 3311169689Skan 0, /* static_pass_number */ 3312169689Skan 0, /* tv_id */ 3313169689Skan PROP_cfg, /* properties_required */ 3314169689Skan 0, /* properties_provided */ 3315169689Skan 0, /* properties_destroyed */ 3316169689Skan 0, /* todo_flags_start */ 3317169689Skan TODO_dump_func, /* todo_flags_finish */ 3318169689Skan 0 /* letter */ 3319169689Skan}; 3320169689Skan 3321169689Skan/* Reset the DECL_CALL_CLOBBERED flags on our referenced vars. In 3322169689Skan theory, this only needs to be done for globals. */ 3323169689Skan 3324169689Skanstatic unsigned int 3325169689Skanreset_cc_flags (void) 3326169689Skan{ 3327169689Skan tree var; 3328169689Skan referenced_var_iterator rvi; 3329169689Skan 3330169689Skan FOR_EACH_REFERENCED_VAR (var, rvi) 3331169689Skan DECL_CALL_CLOBBERED (var) = false; 3332169689Skan return 0; 3333169689Skan} 3334169689Skan 3335169689Skanstruct tree_opt_pass pass_reset_cc_flags = 3336169689Skan{ 3337169689Skan NULL, /* name */ 3338169689Skan NULL, /* gate */ 3339169689Skan reset_cc_flags, /* execute */ 3340169689Skan NULL, /* sub */ 3341169689Skan NULL, /* next */ 3342169689Skan 0, /* static_pass_number */ 3343169689Skan 0, /* tv_id */ 3344169689Skan PROP_referenced_vars |PROP_cfg, /* properties_required */ 3345169689Skan 0, /* properties_provided */ 3346169689Skan 0, /* properties_destroyed */ 3347169689Skan 0, /* todo_flags_start */ 3348169689Skan 0, /* todo_flags_finish */ 3349169689Skan 0 /* letter */ 3350169689Skan}; 3351