1169689Skan/* Dead store elimination 2169689Skan Copyright (C) 2004, 2005 Free Software Foundation, Inc. 3169689Skan 4169689SkanThis file is part of GCC. 5169689Skan 6169689SkanGCC is free software; you can redistribute it and/or modify 7169689Skanit under the terms of the GNU General Public License as published by 8169689Skanthe Free Software Foundation; either version 2, or (at your option) 9169689Skanany later version. 10169689Skan 11169689SkanGCC is distributed in the hope that it will be useful, 12169689Skanbut WITHOUT ANY WARRANTY; without even the implied warranty of 13169689SkanMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14169689SkanGNU General Public License for more details. 15169689Skan 16169689SkanYou should have received a copy of the GNU General Public License 17169689Skanalong with GCC; see the file COPYING. If not, write to 18169689Skanthe Free Software Foundation, 51 Franklin Street, Fifth Floor, 19169689SkanBoston, MA 02110-1301, USA. */ 20169689Skan 21169689Skan#include "config.h" 22169689Skan#include "system.h" 23169689Skan#include "coretypes.h" 24169689Skan#include "tm.h" 25169689Skan#include "ggc.h" 26169689Skan#include "tree.h" 27169689Skan#include "rtl.h" 28169689Skan#include "tm_p.h" 29169689Skan#include "basic-block.h" 30169689Skan#include "timevar.h" 31169689Skan#include "diagnostic.h" 32169689Skan#include "tree-flow.h" 33169689Skan#include "tree-pass.h" 34169689Skan#include "tree-dump.h" 35169689Skan#include "domwalk.h" 36169689Skan#include "flags.h" 37169689Skan 38169689Skan/* This file implements dead store elimination. 39169689Skan 40169689Skan A dead store is a store into a memory location which will later be 41169689Skan overwritten by another store without any intervening loads. In this 42169689Skan case the earlier store can be deleted. 43169689Skan 44169689Skan In our SSA + virtual operand world we use immediate uses of virtual 45169689Skan operands to detect dead stores. If a store's virtual definition 46169689Skan is used precisely once by a later store to the same location which 47169689Skan post dominates the first store, then the first store is dead. 48169689Skan 49169689Skan The single use of the store's virtual definition ensures that 50169689Skan there are no intervening aliased loads and the requirement that 51169689Skan the second load post dominate the first ensures that if the earlier 52169689Skan store executes, then the later stores will execute before the function 53169689Skan exits. 54169689Skan 55169689Skan It may help to think of this as first moving the earlier store to 56169689Skan the point immediately before the later store. Again, the single 57169689Skan use of the virtual definition and the post-dominance relationship 58169689Skan ensure that such movement would be safe. Clearly if there are 59169689Skan back to back stores, then the second is redundant. 60169689Skan 61169689Skan Reviewing section 10.7.2 in Morgan's "Building an Optimizing Compiler" 62169689Skan may also help in understanding this code since it discusses the 63169689Skan relationship between dead store and redundant load elimination. In 64169689Skan fact, they are the same transformation applied to different views of 65169689Skan the CFG. */ 66169689Skan 67169689Skan 68169689Skanstruct dse_global_data 69169689Skan{ 70169689Skan /* This is the global bitmap for store statements. 71169689Skan 72169689Skan Each statement has a unique ID. When we encounter a store statement 73169689Skan that we want to record, set the bit corresponding to the statement's 74169689Skan unique ID in this bitmap. */ 75169689Skan bitmap stores; 76169689Skan}; 77169689Skan 78169689Skan/* We allocate a bitmap-per-block for stores which are encountered 79169689Skan during the scan of that block. This allows us to restore the 80169689Skan global bitmap of stores when we finish processing a block. */ 81169689Skanstruct dse_block_local_data 82169689Skan{ 83169689Skan bitmap stores; 84169689Skan}; 85169689Skan 86169689Skan/* Basic blocks of the potentially dead store and the following 87169689Skan store, for memory_address_same. */ 88169689Skanstruct address_walk_data 89169689Skan{ 90169689Skan basic_block store1_bb, store2_bb; 91169689Skan}; 92169689Skan 93169689Skanstatic bool gate_dse (void); 94169689Skanstatic unsigned int tree_ssa_dse (void); 95169689Skanstatic void dse_initialize_block_local_data (struct dom_walk_data *, 96169689Skan basic_block, 97169689Skan bool); 98169689Skanstatic void dse_optimize_stmt (struct dom_walk_data *, 99169689Skan basic_block, 100169689Skan block_stmt_iterator); 101169689Skanstatic void dse_record_phis (struct dom_walk_data *, basic_block); 102169689Skanstatic void dse_finalize_block (struct dom_walk_data *, basic_block); 103169689Skanstatic void record_voperand_set (bitmap, bitmap *, unsigned int); 104169689Skan 105169689Skanstatic unsigned max_stmt_uid; /* Maximal uid of a statement. Uids to phi 106169689Skan nodes are assigned using the versions of 107169689Skan ssa names they define. */ 108169689Skan 109169689Skan/* Returns uid of statement STMT. */ 110169689Skan 111169689Skanstatic unsigned 112169689Skanget_stmt_uid (tree stmt) 113169689Skan{ 114169689Skan if (TREE_CODE (stmt) == PHI_NODE) 115169689Skan return SSA_NAME_VERSION (PHI_RESULT (stmt)) + max_stmt_uid; 116169689Skan 117169689Skan return stmt_ann (stmt)->uid; 118169689Skan} 119169689Skan 120169689Skan/* Set bit UID in bitmaps GLOBAL and *LOCAL, creating *LOCAL as needed. */ 121169689Skan 122169689Skanstatic void 123169689Skanrecord_voperand_set (bitmap global, bitmap *local, unsigned int uid) 124169689Skan{ 125169689Skan /* Lazily allocate the bitmap. Note that we do not get a notification 126169689Skan when the block local data structures die, so we allocate the local 127169689Skan bitmap backed by the GC system. */ 128169689Skan if (*local == NULL) 129169689Skan *local = BITMAP_GGC_ALLOC (); 130169689Skan 131169689Skan /* Set the bit in the local and global bitmaps. */ 132169689Skan bitmap_set_bit (*local, uid); 133169689Skan bitmap_set_bit (global, uid); 134169689Skan} 135169689Skan 136169689Skan/* Initialize block local data structures. */ 137169689Skan 138169689Skanstatic void 139169689Skandse_initialize_block_local_data (struct dom_walk_data *walk_data, 140169689Skan basic_block bb ATTRIBUTE_UNUSED, 141169689Skan bool recycled) 142169689Skan{ 143169689Skan struct dse_block_local_data *bd 144169689Skan = VEC_last (void_p, walk_data->block_data_stack); 145169689Skan 146169689Skan /* If we are given a recycled block local data structure, ensure any 147169689Skan bitmap associated with the block is cleared. */ 148169689Skan if (recycled) 149169689Skan { 150169689Skan if (bd->stores) 151169689Skan bitmap_clear (bd->stores); 152169689Skan } 153169689Skan} 154169689Skan 155169689Skan/* Helper function for memory_address_same via walk_tree. Returns 156169689Skan non-NULL if it finds an SSA_NAME which is part of the address, 157169689Skan such that the definition of the SSA_NAME post-dominates the store 158169689Skan we want to delete but not the store that we believe makes it 159169689Skan redundant. This indicates that the address may change between 160169689Skan the two stores. */ 161169689Skan 162169689Skanstatic tree 163169689Skanmemory_ssa_name_same (tree *expr_p, int *walk_subtrees ATTRIBUTE_UNUSED, 164169689Skan void *data) 165169689Skan{ 166169689Skan struct address_walk_data *walk_data = data; 167169689Skan tree expr = *expr_p; 168169689Skan tree def_stmt; 169169689Skan basic_block def_bb; 170169689Skan 171169689Skan if (TREE_CODE (expr) != SSA_NAME) 172169689Skan return NULL_TREE; 173169689Skan 174169689Skan /* If we've found a default definition, then there's no problem. Both 175169689Skan stores will post-dominate it. And def_bb will be NULL. */ 176169689Skan if (expr == default_def (SSA_NAME_VAR (expr))) 177169689Skan return NULL_TREE; 178169689Skan 179169689Skan def_stmt = SSA_NAME_DEF_STMT (expr); 180169689Skan def_bb = bb_for_stmt (def_stmt); 181169689Skan 182169689Skan /* DEF_STMT must dominate both stores. So if it is in the same 183169689Skan basic block as one, it does not post-dominate that store. */ 184169689Skan if (walk_data->store1_bb != def_bb 185169689Skan && dominated_by_p (CDI_POST_DOMINATORS, walk_data->store1_bb, def_bb)) 186169689Skan { 187169689Skan if (walk_data->store2_bb == def_bb 188169689Skan || !dominated_by_p (CDI_POST_DOMINATORS, walk_data->store2_bb, 189169689Skan def_bb)) 190169689Skan /* Return non-NULL to stop the walk. */ 191169689Skan return def_stmt; 192169689Skan } 193169689Skan 194169689Skan return NULL_TREE; 195169689Skan} 196169689Skan 197169689Skan/* Return TRUE if the destination memory address in STORE1 and STORE2 198169689Skan might be modified after STORE1, before control reaches STORE2. */ 199169689Skan 200169689Skanstatic bool 201169689Skanmemory_address_same (tree store1, tree store2) 202169689Skan{ 203169689Skan struct address_walk_data walk_data; 204169689Skan 205169689Skan walk_data.store1_bb = bb_for_stmt (store1); 206169689Skan walk_data.store2_bb = bb_for_stmt (store2); 207169689Skan 208169689Skan return (walk_tree (&TREE_OPERAND (store1, 0), memory_ssa_name_same, 209169689Skan &walk_data, NULL) 210169689Skan == NULL); 211169689Skan} 212169689Skan 213169689Skan/* Attempt to eliminate dead stores in the statement referenced by BSI. 214169689Skan 215169689Skan A dead store is a store into a memory location which will later be 216169689Skan overwritten by another store without any intervening loads. In this 217169689Skan case the earlier store can be deleted. 218169689Skan 219169689Skan In our SSA + virtual operand world we use immediate uses of virtual 220169689Skan operands to detect dead stores. If a store's virtual definition 221169689Skan is used precisely once by a later store to the same location which 222169689Skan post dominates the first store, then the first store is dead. */ 223169689Skan 224169689Skanstatic void 225169689Skandse_optimize_stmt (struct dom_walk_data *walk_data, 226169689Skan basic_block bb ATTRIBUTE_UNUSED, 227169689Skan block_stmt_iterator bsi) 228169689Skan{ 229169689Skan struct dse_block_local_data *bd 230169689Skan = VEC_last (void_p, walk_data->block_data_stack); 231169689Skan struct dse_global_data *dse_gd = walk_data->global_data; 232169689Skan tree stmt = bsi_stmt (bsi); 233169689Skan stmt_ann_t ann = stmt_ann (stmt); 234169689Skan 235169689Skan /* If this statement has no virtual defs, then there is nothing 236169689Skan to do. */ 237169689Skan if (ZERO_SSA_OPERANDS (stmt, (SSA_OP_VMAYDEF|SSA_OP_VMUSTDEF))) 238169689Skan return; 239169689Skan 240169689Skan /* We know we have virtual definitions. If this is a MODIFY_EXPR that's 241169689Skan not also a function call, then record it into our table. */ 242169689Skan if (get_call_expr_in (stmt)) 243169689Skan return; 244169689Skan 245169689Skan if (ann->has_volatile_ops) 246169689Skan return; 247169689Skan 248169689Skan if (TREE_CODE (stmt) == MODIFY_EXPR) 249169689Skan { 250169689Skan use_operand_p first_use_p = NULL_USE_OPERAND_P; 251169689Skan use_operand_p use_p = NULL; 252169689Skan tree use_stmt, temp; 253169689Skan tree defvar = NULL_TREE, usevar = NULL_TREE; 254169689Skan bool fail = false; 255169689Skan use_operand_p var2; 256169689Skan def_operand_p var1; 257169689Skan ssa_op_iter op_iter; 258169689Skan 259169689Skan /* We want to verify that each virtual definition in STMT has 260169689Skan precisely one use and that all the virtual definitions are 261169689Skan used by the same single statement. When complete, we 262169689Skan want USE_STMT to refer to the one statement which uses 263169689Skan all of the virtual definitions from STMT. */ 264169689Skan use_stmt = NULL; 265169689Skan FOR_EACH_SSA_MUST_AND_MAY_DEF_OPERAND (var1, var2, stmt, op_iter) 266169689Skan { 267169689Skan defvar = DEF_FROM_PTR (var1); 268169689Skan usevar = USE_FROM_PTR (var2); 269169689Skan 270169689Skan /* If this virtual def does not have precisely one use, then 271169689Skan we will not be able to eliminate STMT. */ 272169689Skan if (! has_single_use (defvar)) 273169689Skan { 274169689Skan fail = true; 275169689Skan break; 276169689Skan } 277169689Skan 278169689Skan /* Get the one and only immediate use of DEFVAR. */ 279169689Skan single_imm_use (defvar, &use_p, &temp); 280169689Skan gcc_assert (use_p != NULL_USE_OPERAND_P); 281169689Skan first_use_p = use_p; 282169689Skan 283169689Skan /* If the immediate use of DEF_VAR is not the same as the 284169689Skan previously find immediate uses, then we will not be able 285169689Skan to eliminate STMT. */ 286169689Skan if (use_stmt == NULL) 287169689Skan use_stmt = temp; 288169689Skan else if (temp != use_stmt) 289169689Skan { 290169689Skan fail = true; 291169689Skan break; 292169689Skan } 293169689Skan } 294169689Skan 295169689Skan if (fail) 296169689Skan { 297169689Skan record_voperand_set (dse_gd->stores, &bd->stores, ann->uid); 298169689Skan return; 299169689Skan } 300169689Skan 301169689Skan /* Skip through any PHI nodes we have already seen if the PHI 302169689Skan represents the only use of this store. 303169689Skan 304169689Skan Note this does not handle the case where the store has 305169689Skan multiple V_{MAY,MUST}_DEFs which all reach a set of PHI nodes in the 306169689Skan same block. */ 307169689Skan while (use_p != NULL_USE_OPERAND_P 308169689Skan && TREE_CODE (use_stmt) == PHI_NODE 309169689Skan && bitmap_bit_p (dse_gd->stores, get_stmt_uid (use_stmt))) 310169689Skan { 311169689Skan /* A PHI node can both define and use the same SSA_NAME if 312169689Skan the PHI is at the top of a loop and the PHI_RESULT is 313169689Skan a loop invariant and copies have not been fully propagated. 314169689Skan 315169689Skan The safe thing to do is exit assuming no optimization is 316169689Skan possible. */ 317169689Skan if (SSA_NAME_DEF_STMT (PHI_RESULT (use_stmt)) == use_stmt) 318169689Skan return; 319169689Skan 320169689Skan /* Skip past this PHI and loop again in case we had a PHI 321169689Skan chain. */ 322169689Skan single_imm_use (PHI_RESULT (use_stmt), &use_p, &use_stmt); 323169689Skan } 324169689Skan 325169689Skan /* If we have precisely one immediate use at this point, then we may 326169689Skan have found redundant store. Make sure that the stores are to 327169689Skan the same memory location. This includes checking that any 328169689Skan SSA-form variables in the address will have the same values. */ 329169689Skan if (use_p != NULL_USE_OPERAND_P 330169689Skan && bitmap_bit_p (dse_gd->stores, get_stmt_uid (use_stmt)) 331169689Skan && operand_equal_p (TREE_OPERAND (stmt, 0), 332169689Skan TREE_OPERAND (use_stmt, 0), 0) 333169689Skan && memory_address_same (stmt, use_stmt)) 334169689Skan { 335169689Skan /* Make sure we propagate the ABNORMAL bit setting. */ 336169689Skan if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (first_use_p))) 337169689Skan SSA_NAME_OCCURS_IN_ABNORMAL_PHI (usevar) = 1; 338169689Skan 339169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 340169689Skan { 341169689Skan fprintf (dump_file, " Deleted dead store '"); 342169689Skan print_generic_expr (dump_file, bsi_stmt (bsi), dump_flags); 343169689Skan fprintf (dump_file, "'\n"); 344169689Skan } 345169689Skan /* Then we need to fix the operand of the consuming stmt. */ 346169689Skan FOR_EACH_SSA_MUST_AND_MAY_DEF_OPERAND (var1, var2, stmt, op_iter) 347169689Skan { 348169689Skan single_imm_use (DEF_FROM_PTR (var1), &use_p, &temp); 349169689Skan SET_USE (use_p, USE_FROM_PTR (var2)); 350169689Skan } 351169689Skan /* Remove the dead store. */ 352169689Skan bsi_remove (&bsi, true); 353169689Skan 354169689Skan /* And release any SSA_NAMEs set in this statement back to the 355169689Skan SSA_NAME manager. */ 356169689Skan release_defs (stmt); 357169689Skan } 358169689Skan 359169689Skan record_voperand_set (dse_gd->stores, &bd->stores, ann->uid); 360169689Skan } 361169689Skan} 362169689Skan 363169689Skan/* Record that we have seen the PHIs at the start of BB which correspond 364169689Skan to virtual operands. */ 365169689Skanstatic void 366169689Skandse_record_phis (struct dom_walk_data *walk_data, basic_block bb) 367169689Skan{ 368169689Skan struct dse_block_local_data *bd 369169689Skan = VEC_last (void_p, walk_data->block_data_stack); 370169689Skan struct dse_global_data *dse_gd = walk_data->global_data; 371169689Skan tree phi; 372169689Skan 373169689Skan for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 374169689Skan if (!is_gimple_reg (PHI_RESULT (phi))) 375169689Skan record_voperand_set (dse_gd->stores, 376169689Skan &bd->stores, 377169689Skan get_stmt_uid (phi)); 378169689Skan} 379169689Skan 380169689Skanstatic void 381169689Skandse_finalize_block (struct dom_walk_data *walk_data, 382169689Skan basic_block bb ATTRIBUTE_UNUSED) 383169689Skan{ 384169689Skan struct dse_block_local_data *bd 385169689Skan = VEC_last (void_p, walk_data->block_data_stack); 386169689Skan struct dse_global_data *dse_gd = walk_data->global_data; 387169689Skan bitmap stores = dse_gd->stores; 388169689Skan unsigned int i; 389169689Skan bitmap_iterator bi; 390169689Skan 391169689Skan /* Unwind the stores noted in this basic block. */ 392169689Skan if (bd->stores) 393169689Skan EXECUTE_IF_SET_IN_BITMAP (bd->stores, 0, i, bi) 394169689Skan { 395169689Skan bitmap_clear_bit (stores, i); 396169689Skan } 397169689Skan} 398169689Skan 399169689Skanstatic unsigned int 400169689Skantree_ssa_dse (void) 401169689Skan{ 402169689Skan struct dom_walk_data walk_data; 403169689Skan struct dse_global_data dse_gd; 404169689Skan basic_block bb; 405169689Skan 406169689Skan /* Create a UID for each statement in the function. Ordering of the 407169689Skan UIDs is not important for this pass. */ 408169689Skan max_stmt_uid = 0; 409169689Skan FOR_EACH_BB (bb) 410169689Skan { 411169689Skan block_stmt_iterator bsi; 412169689Skan 413169689Skan for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 414169689Skan stmt_ann (bsi_stmt (bsi))->uid = max_stmt_uid++; 415169689Skan } 416169689Skan 417169689Skan /* We might consider making this a property of each pass so that it 418169689Skan can be [re]computed on an as-needed basis. Particularly since 419169689Skan this pass could be seen as an extension of DCE which needs post 420169689Skan dominators. */ 421169689Skan calculate_dominance_info (CDI_POST_DOMINATORS); 422169689Skan 423169689Skan /* Dead store elimination is fundamentally a walk of the post-dominator 424169689Skan tree and a backwards walk of statements within each block. */ 425169689Skan walk_data.walk_stmts_backward = true; 426169689Skan walk_data.dom_direction = CDI_POST_DOMINATORS; 427169689Skan walk_data.initialize_block_local_data = dse_initialize_block_local_data; 428169689Skan walk_data.before_dom_children_before_stmts = NULL; 429169689Skan walk_data.before_dom_children_walk_stmts = dse_optimize_stmt; 430169689Skan walk_data.before_dom_children_after_stmts = dse_record_phis; 431169689Skan walk_data.after_dom_children_before_stmts = NULL; 432169689Skan walk_data.after_dom_children_walk_stmts = NULL; 433169689Skan walk_data.after_dom_children_after_stmts = dse_finalize_block; 434169689Skan walk_data.interesting_blocks = NULL; 435169689Skan 436169689Skan walk_data.block_local_data_size = sizeof (struct dse_block_local_data); 437169689Skan 438169689Skan /* This is the main hash table for the dead store elimination pass. */ 439169689Skan dse_gd.stores = BITMAP_ALLOC (NULL); 440169689Skan walk_data.global_data = &dse_gd; 441169689Skan 442169689Skan /* Initialize the dominator walker. */ 443169689Skan init_walk_dominator_tree (&walk_data); 444169689Skan 445169689Skan /* Recursively walk the dominator tree. */ 446169689Skan walk_dominator_tree (&walk_data, EXIT_BLOCK_PTR); 447169689Skan 448169689Skan /* Finalize the dominator walker. */ 449169689Skan fini_walk_dominator_tree (&walk_data); 450169689Skan 451169689Skan /* Release the main bitmap. */ 452169689Skan BITMAP_FREE (dse_gd.stores); 453169689Skan 454169689Skan /* For now, just wipe the post-dominator information. */ 455169689Skan free_dominance_info (CDI_POST_DOMINATORS); 456169689Skan return 0; 457169689Skan} 458169689Skan 459169689Skanstatic bool 460169689Skangate_dse (void) 461169689Skan{ 462169689Skan return flag_tree_dse != 0; 463169689Skan} 464169689Skan 465169689Skanstruct tree_opt_pass pass_dse = { 466169689Skan "dse", /* name */ 467169689Skan gate_dse, /* gate */ 468169689Skan tree_ssa_dse, /* execute */ 469169689Skan NULL, /* sub */ 470169689Skan NULL, /* next */ 471169689Skan 0, /* static_pass_number */ 472169689Skan TV_TREE_DSE, /* tv_id */ 473169689Skan PROP_cfg 474169689Skan | PROP_ssa 475169689Skan | PROP_alias, /* properties_required */ 476169689Skan 0, /* properties_provided */ 477169689Skan 0, /* properties_destroyed */ 478169689Skan 0, /* todo_flags_start */ 479169689Skan TODO_dump_func 480169689Skan | TODO_ggc_collect 481169689Skan | TODO_verify_ssa, /* todo_flags_finish */ 482169689Skan 0 /* letter */ 483169689Skan}; 484