1 /* Dead store elimination 2 Copyright (C) 2004-2015 Free Software Foundation, Inc. 3 4 This file is part of GCC. 5 6 GCC is free software; you can redistribute it and/or modify 7 it under the terms of the GNU General Public License as published by 8 the Free Software Foundation; either version 3, or (at your option) 9 any later version. 10 11 GCC is distributed in the hope that it will be useful, 12 but WITHOUT ANY WARRANTY; without even the implied warranty of 13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 GNU General Public License for more details. 15 16 You should have received a copy of the GNU General Public License 17 along with GCC; see the file COPYING3. If not see 18 <http://www.gnu.org/licenses/>. */ 19 20 #include "config.h" 21 #include "system.h" 22 #include "coretypes.h" 23 #include "tm.h" 24 #include "hash-set.h" 25 #include "machmode.h" 26 #include "vec.h" 27 #include "double-int.h" 28 #include "input.h" 29 #include "alias.h" 30 #include "symtab.h" 31 #include "wide-int.h" 32 #include "inchash.h" 33 #include "tree.h" 34 #include "fold-const.h" 35 #include "tm_p.h" 36 #include "predict.h" 37 #include "hard-reg-set.h" 38 #include "function.h" 39 #include "dominance.h" 40 #include "cfg.h" 41 #include "basic-block.h" 42 #include "gimple-pretty-print.h" 43 #include "bitmap.h" 44 #include "tree-ssa-alias.h" 45 #include "internal-fn.h" 46 #include "gimple-expr.h" 47 #include "is-a.h" 48 #include "gimple.h" 49 #include "gimple-iterator.h" 50 #include "gimple-ssa.h" 51 #include "tree-cfg.h" 52 #include "tree-phinodes.h" 53 #include "ssa-iterators.h" 54 #include "stringpool.h" 55 #include "tree-ssanames.h" 56 #include "hashtab.h" 57 #include "rtl.h" 58 #include "flags.h" 59 #include "statistics.h" 60 #include "real.h" 61 #include "fixed-value.h" 62 #include "insn-config.h" 63 #include "expmed.h" 64 #include "dojump.h" 65 #include "explow.h" 66 #include "calls.h" 67 #include "emit-rtl.h" 68 #include "varasm.h" 69 #include "stmt.h" 70 #include "expr.h" 71 #include "tree-dfa.h" 72 #include "tree-pass.h" 73 #include "domwalk.h" 74 #include "langhooks.h" 75 #include "tree-cfgcleanup.h" 76 77 /* This file implements dead store elimination. 78 79 A dead store is a store into a memory location which will later be 80 overwritten by another store without any intervening loads. In this 81 case the earlier store can be deleted. 82 83 In our SSA + virtual operand world we use immediate uses of virtual 84 operands to detect dead stores. If a store's virtual definition 85 is used precisely once by a later store to the same location which 86 post dominates the first store, then the first store is dead. 87 88 The single use of the store's virtual definition ensures that 89 there are no intervening aliased loads and the requirement that 90 the second load post dominate the first ensures that if the earlier 91 store executes, then the later stores will execute before the function 92 exits. 93 94 It may help to think of this as first moving the earlier store to 95 the point immediately before the later store. Again, the single 96 use of the virtual definition and the post-dominance relationship 97 ensure that such movement would be safe. Clearly if there are 98 back to back stores, then the second is redundant. 99 100 Reviewing section 10.7.2 in Morgan's "Building an Optimizing Compiler" 101 may also help in understanding this code since it discusses the 102 relationship between dead store and redundant load elimination. In 103 fact, they are the same transformation applied to different views of 104 the CFG. */ 105 106 107 /* Bitmap of blocks that have had EH statements cleaned. We should 108 remove their dead edges eventually. */ 109 static bitmap need_eh_cleanup; 110 111 112 /* A helper of dse_optimize_stmt. 113 Given a GIMPLE_ASSIGN in STMT that writes to REF, find a candidate 114 statement *USE_STMT that may prove STMT to be dead. 115 Return TRUE if the above conditions are met, otherwise FALSE. */ 116 117 static bool 118 dse_possible_dead_store_p (ao_ref *ref, gimple stmt, gimple *use_stmt) 119 { 120 gimple temp; 121 unsigned cnt = 0; 122 123 *use_stmt = NULL; 124 125 /* Find the first dominated statement that clobbers (part of) the 126 memory stmt stores to with no intermediate statement that may use 127 part of the memory stmt stores. That is, find a store that may 128 prove stmt to be a dead store. */ 129 temp = stmt; 130 do 131 { 132 gimple use_stmt, defvar_def; 133 imm_use_iterator ui; 134 bool fail = false; 135 tree defvar; 136 137 /* Limit stmt walking to be linear in the number of possibly 138 dead stores. */ 139 if (++cnt > 256) 140 return false; 141 142 if (gimple_code (temp) == GIMPLE_PHI) 143 defvar = PHI_RESULT (temp); 144 else 145 defvar = gimple_vdef (temp); 146 defvar_def = temp; 147 temp = NULL; 148 FOR_EACH_IMM_USE_STMT (use_stmt, ui, defvar) 149 { 150 cnt++; 151 152 /* If we ever reach our DSE candidate stmt again fail. We 153 cannot handle dead stores in loops. */ 154 if (use_stmt == stmt) 155 { 156 fail = true; 157 BREAK_FROM_IMM_USE_STMT (ui); 158 } 159 /* In simple cases we can look through PHI nodes, but we 160 have to be careful with loops and with memory references 161 containing operands that are also operands of PHI nodes. 162 See gcc.c-torture/execute/20051110-*.c. */ 163 else if (gimple_code (use_stmt) == GIMPLE_PHI) 164 { 165 if (temp 166 /* Make sure we are not in a loop latch block. */ 167 || gimple_bb (stmt) == gimple_bb (use_stmt) 168 || dominated_by_p (CDI_DOMINATORS, 169 gimple_bb (stmt), gimple_bb (use_stmt)) 170 /* We can look through PHIs to regions post-dominating 171 the DSE candidate stmt. */ 172 || !dominated_by_p (CDI_POST_DOMINATORS, 173 gimple_bb (stmt), gimple_bb (use_stmt))) 174 { 175 fail = true; 176 BREAK_FROM_IMM_USE_STMT (ui); 177 } 178 /* Do not consider the PHI as use if it dominates the 179 stmt defining the virtual operand we are processing, 180 we have processed it already in this case. */ 181 if (gimple_bb (defvar_def) != gimple_bb (use_stmt) 182 && !dominated_by_p (CDI_DOMINATORS, 183 gimple_bb (defvar_def), 184 gimple_bb (use_stmt))) 185 temp = use_stmt; 186 } 187 /* If the statement is a use the store is not dead. */ 188 else if (ref_maybe_used_by_stmt_p (use_stmt, ref)) 189 { 190 fail = true; 191 BREAK_FROM_IMM_USE_STMT (ui); 192 } 193 /* If this is a store, remember it or bail out if we have 194 multiple ones (the will be in different CFG parts then). */ 195 else if (gimple_vdef (use_stmt)) 196 { 197 if (temp) 198 { 199 fail = true; 200 BREAK_FROM_IMM_USE_STMT (ui); 201 } 202 temp = use_stmt; 203 } 204 } 205 206 if (fail) 207 return false; 208 209 /* If we didn't find any definition this means the store is dead 210 if it isn't a store to global reachable memory. In this case 211 just pretend the stmt makes itself dead. Otherwise fail. */ 212 if (!temp) 213 { 214 if (ref_may_alias_global_p (ref)) 215 return false; 216 217 temp = stmt; 218 break; 219 } 220 } 221 /* Continue walking until we reach a kill. */ 222 while (!stmt_kills_ref_p (temp, ref)); 223 224 *use_stmt = temp; 225 226 return true; 227 } 228 229 230 /* Attempt to eliminate dead stores in the statement referenced by BSI. 231 232 A dead store is a store into a memory location which will later be 233 overwritten by another store without any intervening loads. In this 234 case the earlier store can be deleted. 235 236 In our SSA + virtual operand world we use immediate uses of virtual 237 operands to detect dead stores. If a store's virtual definition 238 is used precisely once by a later store to the same location which 239 post dominates the first store, then the first store is dead. */ 240 241 static void 242 dse_optimize_stmt (gimple_stmt_iterator *gsi) 243 { 244 gimple stmt = gsi_stmt (*gsi); 245 246 /* If this statement has no virtual defs, then there is nothing 247 to do. */ 248 if (!gimple_vdef (stmt)) 249 return; 250 251 /* Don't return early on *this_2(D) ={v} {CLOBBER}. */ 252 if (gimple_has_volatile_ops (stmt) 253 && (!gimple_clobber_p (stmt) 254 || TREE_CODE (gimple_assign_lhs (stmt)) != MEM_REF)) 255 return; 256 257 /* We know we have virtual definitions. We can handle assignments and 258 some builtin calls. */ 259 if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL)) 260 { 261 switch (DECL_FUNCTION_CODE (gimple_call_fndecl (stmt))) 262 { 263 case BUILT_IN_MEMCPY: 264 case BUILT_IN_MEMMOVE: 265 case BUILT_IN_MEMSET: 266 { 267 gimple use_stmt; 268 ao_ref ref; 269 tree size = NULL_TREE; 270 if (gimple_call_num_args (stmt) == 3) 271 size = gimple_call_arg (stmt, 2); 272 tree ptr = gimple_call_arg (stmt, 0); 273 ao_ref_init_from_ptr_and_size (&ref, ptr, size); 274 if (!dse_possible_dead_store_p (&ref, stmt, &use_stmt)) 275 return; 276 277 if (dump_file && (dump_flags & TDF_DETAILS)) 278 { 279 fprintf (dump_file, " Deleted dead call '"); 280 print_gimple_stmt (dump_file, gsi_stmt (*gsi), dump_flags, 0); 281 fprintf (dump_file, "'\n"); 282 } 283 284 tree lhs = gimple_call_lhs (stmt); 285 if (lhs) 286 { 287 gimple new_stmt = gimple_build_assign (lhs, ptr); 288 unlink_stmt_vdef (stmt); 289 if (gsi_replace (gsi, new_stmt, true)) 290 bitmap_set_bit (need_eh_cleanup, gimple_bb (stmt)->index); 291 } 292 else 293 { 294 /* Then we need to fix the operand of the consuming stmt. */ 295 unlink_stmt_vdef (stmt); 296 297 /* Remove the dead store. */ 298 if (gsi_remove (gsi, true)) 299 bitmap_set_bit (need_eh_cleanup, gimple_bb (stmt)->index); 300 } 301 break; 302 } 303 default: 304 return; 305 } 306 } 307 308 if (is_gimple_assign (stmt)) 309 { 310 gimple use_stmt; 311 312 /* Self-assignments are zombies. */ 313 if (operand_equal_p (gimple_assign_rhs1 (stmt), 314 gimple_assign_lhs (stmt), 0)) 315 use_stmt = stmt; 316 else 317 { 318 ao_ref ref; 319 ao_ref_init (&ref, gimple_assign_lhs (stmt)); 320 if (!dse_possible_dead_store_p (&ref, stmt, &use_stmt)) 321 return; 322 } 323 324 /* Now we know that use_stmt kills the LHS of stmt. */ 325 326 /* But only remove *this_2(D) ={v} {CLOBBER} if killed by 327 another clobber stmt. */ 328 if (gimple_clobber_p (stmt) 329 && !gimple_clobber_p (use_stmt)) 330 return; 331 332 if (dump_file && (dump_flags & TDF_DETAILS)) 333 { 334 fprintf (dump_file, " Deleted dead store '"); 335 print_gimple_stmt (dump_file, gsi_stmt (*gsi), dump_flags, 0); 336 fprintf (dump_file, "'\n"); 337 } 338 339 /* Then we need to fix the operand of the consuming stmt. */ 340 unlink_stmt_vdef (stmt); 341 342 /* Remove the dead store. */ 343 basic_block bb = gimple_bb (stmt); 344 if (gsi_remove (gsi, true)) 345 bitmap_set_bit (need_eh_cleanup, bb->index); 346 347 /* And release any SSA_NAMEs set in this statement back to the 348 SSA_NAME manager. */ 349 release_defs (stmt); 350 } 351 } 352 353 class dse_dom_walker : public dom_walker 354 { 355 public: 356 dse_dom_walker (cdi_direction direction) : dom_walker (direction) {} 357 358 virtual void before_dom_children (basic_block); 359 }; 360 361 void 362 dse_dom_walker::before_dom_children (basic_block bb) 363 { 364 gimple_stmt_iterator gsi; 365 366 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi);) 367 { 368 dse_optimize_stmt (&gsi); 369 if (gsi_end_p (gsi)) 370 gsi = gsi_last_bb (bb); 371 else 372 gsi_prev (&gsi); 373 } 374 } 375 376 namespace { 377 378 const pass_data pass_data_dse = 379 { 380 GIMPLE_PASS, /* type */ 381 "dse", /* name */ 382 OPTGROUP_NONE, /* optinfo_flags */ 383 TV_TREE_DSE, /* tv_id */ 384 ( PROP_cfg | PROP_ssa ), /* properties_required */ 385 0, /* properties_provided */ 386 0, /* properties_destroyed */ 387 0, /* todo_flags_start */ 388 0, /* todo_flags_finish */ 389 }; 390 391 class pass_dse : public gimple_opt_pass 392 { 393 public: 394 pass_dse (gcc::context *ctxt) 395 : gimple_opt_pass (pass_data_dse, ctxt) 396 {} 397 398 /* opt_pass methods: */ 399 opt_pass * clone () { return new pass_dse (m_ctxt); } 400 virtual bool gate (function *) { return flag_tree_dse != 0; } 401 virtual unsigned int execute (function *); 402 403 }; // class pass_dse 404 405 unsigned int 406 pass_dse::execute (function *fun) 407 { 408 need_eh_cleanup = BITMAP_ALLOC (NULL); 409 410 renumber_gimple_stmt_uids (); 411 412 /* We might consider making this a property of each pass so that it 413 can be [re]computed on an as-needed basis. Particularly since 414 this pass could be seen as an extension of DCE which needs post 415 dominators. */ 416 calculate_dominance_info (CDI_POST_DOMINATORS); 417 calculate_dominance_info (CDI_DOMINATORS); 418 419 /* Dead store elimination is fundamentally a walk of the post-dominator 420 tree and a backwards walk of statements within each block. */ 421 dse_dom_walker (CDI_POST_DOMINATORS).walk (fun->cfg->x_exit_block_ptr); 422 423 /* Removal of stores may make some EH edges dead. Purge such edges from 424 the CFG as needed. */ 425 if (!bitmap_empty_p (need_eh_cleanup)) 426 { 427 gimple_purge_all_dead_eh_edges (need_eh_cleanup); 428 cleanup_tree_cfg (); 429 } 430 431 BITMAP_FREE (need_eh_cleanup); 432 433 /* For now, just wipe the post-dominator information. */ 434 free_dominance_info (CDI_POST_DOMINATORS); 435 return 0; 436 } 437 438 } // anon namespace 439 440 gimple_opt_pass * 441 make_pass_dse (gcc::context *ctxt) 442 { 443 return new pass_dse (ctxt); 444 } 445