1/* Dead store elimination 2 Copyright (C) 2004, 2005 Free Software Foundation, Inc. 3 4This file is part of GCC. 5 6GCC is free software; you can redistribute it and/or modify 7it under the terms of the GNU General Public License as published by 8the Free Software Foundation; either version 2, or (at your option) 9any later version. 10 11GCC is distributed in the hope that it will be useful, 12but WITHOUT ANY WARRANTY; without even the implied warranty of 13MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14GNU General Public License for more details. 15 16You should have received a copy of the GNU General Public License 17along with GCC; see the file COPYING. If not, write to 18the Free Software Foundation, 51 Franklin Street, Fifth Floor, 19Boston, MA 02110-1301, USA. */ 20 21#include "config.h" 22#include "system.h" 23#include "coretypes.h" 24#include "tm.h" 25#include "ggc.h" 26#include "tree.h" 27#include "rtl.h" 28#include "tm_p.h" 29#include "basic-block.h" 30#include "timevar.h" 31#include "diagnostic.h" 32#include "tree-flow.h" 33#include "tree-pass.h" 34#include "tree-dump.h" 35#include "domwalk.h" 36#include "flags.h" 37 38/* This file implements dead store elimination. 39 40 A dead store is a store into a memory location which will later be 41 overwritten by another store without any intervening loads. In this 42 case the earlier store can be deleted. 43 44 In our SSA + virtual operand world we use immediate uses of virtual 45 operands to detect dead stores. If a store's virtual definition 46 is used precisely once by a later store to the same location which 47 post dominates the first store, then the first store is dead. 48 49 The single use of the store's virtual definition ensures that 50 there are no intervening aliased loads and the requirement that 51 the second load post dominate the first ensures that if the earlier 52 store executes, then the later stores will execute before the function 53 exits. 54 55 It may help to think of this as first moving the earlier store to 56 the point immediately before the later store. Again, the single 57 use of the virtual definition and the post-dominance relationship 58 ensure that such movement would be safe. Clearly if there are 59 back to back stores, then the second is redundant. 60 61 Reviewing section 10.7.2 in Morgan's "Building an Optimizing Compiler" 62 may also help in understanding this code since it discusses the 63 relationship between dead store and redundant load elimination. In 64 fact, they are the same transformation applied to different views of 65 the CFG. */ 66 67 68struct dse_global_data 69{ 70 /* This is the global bitmap for store statements. 71 72 Each statement has a unique ID. When we encounter a store statement 73 that we want to record, set the bit corresponding to the statement's 74 unique ID in this bitmap. */ 75 bitmap stores; 76}; 77 78/* We allocate a bitmap-per-block for stores which are encountered 79 during the scan of that block. This allows us to restore the 80 global bitmap of stores when we finish processing a block. */ 81struct dse_block_local_data 82{ 83 bitmap stores; 84}; 85 86/* Basic blocks of the potentially dead store and the following 87 store, for memory_address_same. */ 88struct address_walk_data 89{ 90 basic_block store1_bb, store2_bb; 91}; 92 93static bool gate_dse (void); 94static unsigned int tree_ssa_dse (void); 95static void dse_initialize_block_local_data (struct dom_walk_data *, 96 basic_block, 97 bool); 98static void dse_optimize_stmt (struct dom_walk_data *, 99 basic_block, 100 block_stmt_iterator); 101static void dse_record_phis (struct dom_walk_data *, basic_block); 102static void dse_finalize_block (struct dom_walk_data *, basic_block); 103static void record_voperand_set (bitmap, bitmap *, unsigned int); 104 105static unsigned max_stmt_uid; /* Maximal uid of a statement. Uids to phi 106 nodes are assigned using the versions of 107 ssa names they define. */ 108 109/* Returns uid of statement STMT. */ 110 111static unsigned 112get_stmt_uid (tree stmt) 113{ 114 if (TREE_CODE (stmt) == PHI_NODE) 115 return SSA_NAME_VERSION (PHI_RESULT (stmt)) + max_stmt_uid; 116 117 return stmt_ann (stmt)->uid; 118} 119 120/* Set bit UID in bitmaps GLOBAL and *LOCAL, creating *LOCAL as needed. */ 121 122static void 123record_voperand_set (bitmap global, bitmap *local, unsigned int uid) 124{ 125 /* Lazily allocate the bitmap. Note that we do not get a notification 126 when the block local data structures die, so we allocate the local 127 bitmap backed by the GC system. */ 128 if (*local == NULL) 129 *local = BITMAP_GGC_ALLOC (); 130 131 /* Set the bit in the local and global bitmaps. */ 132 bitmap_set_bit (*local, uid); 133 bitmap_set_bit (global, uid); 134} 135 136/* Initialize block local data structures. */ 137 138static void 139dse_initialize_block_local_data (struct dom_walk_data *walk_data, 140 basic_block bb ATTRIBUTE_UNUSED, 141 bool recycled) 142{ 143 struct dse_block_local_data *bd 144 = VEC_last (void_p, walk_data->block_data_stack); 145 146 /* If we are given a recycled block local data structure, ensure any 147 bitmap associated with the block is cleared. */ 148 if (recycled) 149 { 150 if (bd->stores) 151 bitmap_clear (bd->stores); 152 } 153} 154 155/* Helper function for memory_address_same via walk_tree. Returns 156 non-NULL if it finds an SSA_NAME which is part of the address, 157 such that the definition of the SSA_NAME post-dominates the store 158 we want to delete but not the store that we believe makes it 159 redundant. This indicates that the address may change between 160 the two stores. */ 161 162static tree 163memory_ssa_name_same (tree *expr_p, int *walk_subtrees ATTRIBUTE_UNUSED, 164 void *data) 165{ 166 struct address_walk_data *walk_data = data; 167 tree expr = *expr_p; 168 tree def_stmt; 169 basic_block def_bb; 170 171 if (TREE_CODE (expr) != SSA_NAME) 172 return NULL_TREE; 173 174 /* If we've found a default definition, then there's no problem. Both 175 stores will post-dominate it. And def_bb will be NULL. */ 176 if (expr == default_def (SSA_NAME_VAR (expr))) 177 return NULL_TREE; 178 179 def_stmt = SSA_NAME_DEF_STMT (expr); 180 def_bb = bb_for_stmt (def_stmt); 181 182 /* DEF_STMT must dominate both stores. So if it is in the same 183 basic block as one, it does not post-dominate that store. */ 184 if (walk_data->store1_bb != def_bb 185 && dominated_by_p (CDI_POST_DOMINATORS, walk_data->store1_bb, def_bb)) 186 { 187 if (walk_data->store2_bb == def_bb 188 || !dominated_by_p (CDI_POST_DOMINATORS, walk_data->store2_bb, 189 def_bb)) 190 /* Return non-NULL to stop the walk. */ 191 return def_stmt; 192 } 193 194 return NULL_TREE; 195} 196 197/* Return TRUE if the destination memory address in STORE1 and STORE2 198 might be modified after STORE1, before control reaches STORE2. */ 199 200static bool 201memory_address_same (tree store1, tree store2) 202{ 203 struct address_walk_data walk_data; 204 205 walk_data.store1_bb = bb_for_stmt (store1); 206 walk_data.store2_bb = bb_for_stmt (store2); 207 208 return (walk_tree (&TREE_OPERAND (store1, 0), memory_ssa_name_same, 209 &walk_data, NULL) 210 == NULL); 211} 212 213/* Attempt to eliminate dead stores in the statement referenced by BSI. 214 215 A dead store is a store into a memory location which will later be 216 overwritten by another store without any intervening loads. In this 217 case the earlier store can be deleted. 218 219 In our SSA + virtual operand world we use immediate uses of virtual 220 operands to detect dead stores. If a store's virtual definition 221 is used precisely once by a later store to the same location which 222 post dominates the first store, then the first store is dead. */ 223 224static void 225dse_optimize_stmt (struct dom_walk_data *walk_data, 226 basic_block bb ATTRIBUTE_UNUSED, 227 block_stmt_iterator bsi) 228{ 229 struct dse_block_local_data *bd 230 = VEC_last (void_p, walk_data->block_data_stack); 231 struct dse_global_data *dse_gd = walk_data->global_data; 232 tree stmt = bsi_stmt (bsi); 233 stmt_ann_t ann = stmt_ann (stmt); 234 235 /* If this statement has no virtual defs, then there is nothing 236 to do. */ 237 if (ZERO_SSA_OPERANDS (stmt, (SSA_OP_VMAYDEF|SSA_OP_VMUSTDEF))) 238 return; 239 240 /* We know we have virtual definitions. If this is a MODIFY_EXPR that's 241 not also a function call, then record it into our table. */ 242 if (get_call_expr_in (stmt)) 243 return; 244 245 if (ann->has_volatile_ops) 246 return; 247 248 if (TREE_CODE (stmt) == MODIFY_EXPR) 249 { 250 use_operand_p first_use_p = NULL_USE_OPERAND_P; 251 use_operand_p use_p = NULL; 252 tree use_stmt, temp; 253 tree defvar = NULL_TREE, usevar = NULL_TREE; 254 bool fail = false; 255 use_operand_p var2; 256 def_operand_p var1; 257 ssa_op_iter op_iter; 258 259 /* We want to verify that each virtual definition in STMT has 260 precisely one use and that all the virtual definitions are 261 used by the same single statement. When complete, we 262 want USE_STMT to refer to the one statement which uses 263 all of the virtual definitions from STMT. */ 264 use_stmt = NULL; 265 FOR_EACH_SSA_MUST_AND_MAY_DEF_OPERAND (var1, var2, stmt, op_iter) 266 { 267 defvar = DEF_FROM_PTR (var1); 268 usevar = USE_FROM_PTR (var2); 269 270 /* If this virtual def does not have precisely one use, then 271 we will not be able to eliminate STMT. */ 272 if (! has_single_use (defvar)) 273 { 274 fail = true; 275 break; 276 } 277 278 /* Get the one and only immediate use of DEFVAR. */ 279 single_imm_use (defvar, &use_p, &temp); 280 gcc_assert (use_p != NULL_USE_OPERAND_P); 281 first_use_p = use_p; 282 283 /* If the immediate use of DEF_VAR is not the same as the 284 previously find immediate uses, then we will not be able 285 to eliminate STMT. */ 286 if (use_stmt == NULL) 287 use_stmt = temp; 288 else if (temp != use_stmt) 289 { 290 fail = true; 291 break; 292 } 293 } 294 295 if (fail) 296 { 297 record_voperand_set (dse_gd->stores, &bd->stores, ann->uid); 298 return; 299 } 300 301 /* Skip through any PHI nodes we have already seen if the PHI 302 represents the only use of this store. 303 304 Note this does not handle the case where the store has 305 multiple V_{MAY,MUST}_DEFs which all reach a set of PHI nodes in the 306 same block. */ 307 while (use_p != NULL_USE_OPERAND_P 308 && TREE_CODE (use_stmt) == PHI_NODE 309 && bitmap_bit_p (dse_gd->stores, get_stmt_uid (use_stmt))) 310 { 311 /* A PHI node can both define and use the same SSA_NAME if 312 the PHI is at the top of a loop and the PHI_RESULT is 313 a loop invariant and copies have not been fully propagated. 314 315 The safe thing to do is exit assuming no optimization is 316 possible. */ 317 if (SSA_NAME_DEF_STMT (PHI_RESULT (use_stmt)) == use_stmt) 318 return; 319 320 /* Skip past this PHI and loop again in case we had a PHI 321 chain. */ 322 single_imm_use (PHI_RESULT (use_stmt), &use_p, &use_stmt); 323 } 324 325 /* If we have precisely one immediate use at this point, then we may 326 have found redundant store. Make sure that the stores are to 327 the same memory location. This includes checking that any 328 SSA-form variables in the address will have the same values. */ 329 if (use_p != NULL_USE_OPERAND_P 330 && bitmap_bit_p (dse_gd->stores, get_stmt_uid (use_stmt)) 331 && operand_equal_p (TREE_OPERAND (stmt, 0), 332 TREE_OPERAND (use_stmt, 0), 0) 333 && memory_address_same (stmt, use_stmt)) 334 { 335 /* Make sure we propagate the ABNORMAL bit setting. */ 336 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (first_use_p))) 337 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (usevar) = 1; 338 339 if (dump_file && (dump_flags & TDF_DETAILS)) 340 { 341 fprintf (dump_file, " Deleted dead store '"); 342 print_generic_expr (dump_file, bsi_stmt (bsi), dump_flags); 343 fprintf (dump_file, "'\n"); 344 } 345 /* Then we need to fix the operand of the consuming stmt. */ 346 FOR_EACH_SSA_MUST_AND_MAY_DEF_OPERAND (var1, var2, stmt, op_iter) 347 { 348 single_imm_use (DEF_FROM_PTR (var1), &use_p, &temp); 349 SET_USE (use_p, USE_FROM_PTR (var2)); 350 } 351 /* Remove the dead store. */ 352 bsi_remove (&bsi, true); 353 354 /* And release any SSA_NAMEs set in this statement back to the 355 SSA_NAME manager. */ 356 release_defs (stmt); 357 } 358 359 record_voperand_set (dse_gd->stores, &bd->stores, ann->uid); 360 } 361} 362 363/* Record that we have seen the PHIs at the start of BB which correspond 364 to virtual operands. */ 365static void 366dse_record_phis (struct dom_walk_data *walk_data, basic_block bb) 367{ 368 struct dse_block_local_data *bd 369 = VEC_last (void_p, walk_data->block_data_stack); 370 struct dse_global_data *dse_gd = walk_data->global_data; 371 tree phi; 372 373 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 374 if (!is_gimple_reg (PHI_RESULT (phi))) 375 record_voperand_set (dse_gd->stores, 376 &bd->stores, 377 get_stmt_uid (phi)); 378} 379 380static void 381dse_finalize_block (struct dom_walk_data *walk_data, 382 basic_block bb ATTRIBUTE_UNUSED) 383{ 384 struct dse_block_local_data *bd 385 = VEC_last (void_p, walk_data->block_data_stack); 386 struct dse_global_data *dse_gd = walk_data->global_data; 387 bitmap stores = dse_gd->stores; 388 unsigned int i; 389 bitmap_iterator bi; 390 391 /* Unwind the stores noted in this basic block. */ 392 if (bd->stores) 393 EXECUTE_IF_SET_IN_BITMAP (bd->stores, 0, i, bi) 394 { 395 bitmap_clear_bit (stores, i); 396 } 397} 398 399static unsigned int 400tree_ssa_dse (void) 401{ 402 struct dom_walk_data walk_data; 403 struct dse_global_data dse_gd; 404 basic_block bb; 405 406 /* Create a UID for each statement in the function. Ordering of the 407 UIDs is not important for this pass. */ 408 max_stmt_uid = 0; 409 FOR_EACH_BB (bb) 410 { 411 block_stmt_iterator bsi; 412 413 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 414 stmt_ann (bsi_stmt (bsi))->uid = max_stmt_uid++; 415 } 416 417 /* We might consider making this a property of each pass so that it 418 can be [re]computed on an as-needed basis. Particularly since 419 this pass could be seen as an extension of DCE which needs post 420 dominators. */ 421 calculate_dominance_info (CDI_POST_DOMINATORS); 422 423 /* Dead store elimination is fundamentally a walk of the post-dominator 424 tree and a backwards walk of statements within each block. */ 425 walk_data.walk_stmts_backward = true; 426 walk_data.dom_direction = CDI_POST_DOMINATORS; 427 walk_data.initialize_block_local_data = dse_initialize_block_local_data; 428 walk_data.before_dom_children_before_stmts = NULL; 429 walk_data.before_dom_children_walk_stmts = dse_optimize_stmt; 430 walk_data.before_dom_children_after_stmts = dse_record_phis; 431 walk_data.after_dom_children_before_stmts = NULL; 432 walk_data.after_dom_children_walk_stmts = NULL; 433 walk_data.after_dom_children_after_stmts = dse_finalize_block; 434 walk_data.interesting_blocks = NULL; 435 436 walk_data.block_local_data_size = sizeof (struct dse_block_local_data); 437 438 /* This is the main hash table for the dead store elimination pass. */ 439 dse_gd.stores = BITMAP_ALLOC (NULL); 440 walk_data.global_data = &dse_gd; 441 442 /* Initialize the dominator walker. */ 443 init_walk_dominator_tree (&walk_data); 444 445 /* Recursively walk the dominator tree. */ 446 walk_dominator_tree (&walk_data, EXIT_BLOCK_PTR); 447 448 /* Finalize the dominator walker. */ 449 fini_walk_dominator_tree (&walk_data); 450 451 /* Release the main bitmap. */ 452 BITMAP_FREE (dse_gd.stores); 453 454 /* For now, just wipe the post-dominator information. */ 455 free_dominance_info (CDI_POST_DOMINATORS); 456 return 0; 457} 458 459static bool 460gate_dse (void) 461{ 462 return flag_tree_dse != 0; 463} 464 465struct tree_opt_pass pass_dse = { 466 "dse", /* name */ 467 gate_dse, /* gate */ 468 tree_ssa_dse, /* execute */ 469 NULL, /* sub */ 470 NULL, /* next */ 471 0, /* static_pass_number */ 472 TV_TREE_DSE, /* tv_id */ 473 PROP_cfg 474 | PROP_ssa 475 | PROP_alias, /* properties_required */ 476 0, /* properties_provided */ 477 0, /* properties_destroyed */ 478 0, /* todo_flags_start */ 479 TODO_dump_func 480 | TODO_ggc_collect 481 | TODO_verify_ssa, /* todo_flags_finish */ 482 0 /* letter */ 483}; 484