1 /* Dead store elimination 2 Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010 3 Free Software Foundation, Inc. 4 5 This file is part of GCC. 6 7 GCC is free software; you can redistribute it and/or modify 8 it under the terms of the GNU General Public License as published by 9 the Free Software Foundation; either version 3, or (at your option) 10 any later version. 11 12 GCC is distributed in the hope that it will be useful, 13 but WITHOUT ANY WARRANTY; without even the implied warranty of 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 GNU General Public License for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with GCC; see the file COPYING3. If not see 19 <http://www.gnu.org/licenses/>. */ 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 "tm_p.h" 28 #include "basic-block.h" 29 #include "timevar.h" 30 #include "gimple-pretty-print.h" 31 #include "tree-flow.h" 32 #include "tree-pass.h" 33 #include "tree-dump.h" 34 #include "domwalk.h" 35 #include "flags.h" 36 #include "langhooks.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 68 /* Bitmap of blocks that have had EH statements cleaned. We should 69 remove their dead edges eventually. */ 70 static bitmap need_eh_cleanup; 71 72 static bool gate_dse (void); 73 static unsigned int tree_ssa_dse (void); 74 static void dse_enter_block (struct dom_walk_data *, basic_block); 75 76 77 /* A helper of dse_optimize_stmt. 78 Given a GIMPLE_ASSIGN in STMT, find a candidate statement *USE_STMT that 79 may prove STMT to be dead. 80 Return TRUE if the above conditions are met, otherwise FALSE. */ 81 82 static bool 83 dse_possible_dead_store_p (gimple stmt, gimple *use_stmt) 84 { 85 gimple temp; 86 unsigned cnt = 0; 87 88 *use_stmt = NULL; 89 90 /* Find the first dominated statement that clobbers (part of) the 91 memory stmt stores to with no intermediate statement that may use 92 part of the memory stmt stores. That is, find a store that may 93 prove stmt to be a dead store. */ 94 temp = stmt; 95 do 96 { 97 gimple use_stmt; 98 imm_use_iterator ui; 99 bool fail = false; 100 tree defvar; 101 102 /* Limit stmt walking to be linear in the number of possibly 103 dead stores. */ 104 if (++cnt > 256) 105 return false; 106 107 if (gimple_code (temp) == GIMPLE_PHI) 108 defvar = PHI_RESULT (temp); 109 else 110 defvar = gimple_vdef (temp); 111 temp = NULL; 112 FOR_EACH_IMM_USE_STMT (use_stmt, ui, defvar) 113 { 114 cnt++; 115 116 /* If we ever reach our DSE candidate stmt again fail. We 117 cannot handle dead stores in loops. */ 118 if (use_stmt == stmt) 119 { 120 fail = true; 121 BREAK_FROM_IMM_USE_STMT (ui); 122 } 123 /* In simple cases we can look through PHI nodes, but we 124 have to be careful with loops and with memory references 125 containing operands that are also operands of PHI nodes. 126 See gcc.c-torture/execute/20051110-*.c. */ 127 else if (gimple_code (use_stmt) == GIMPLE_PHI) 128 { 129 if (temp 130 /* Make sure we are not in a loop latch block. */ 131 || gimple_bb (stmt) == gimple_bb (use_stmt) 132 || dominated_by_p (CDI_DOMINATORS, 133 gimple_bb (stmt), gimple_bb (use_stmt)) 134 /* We can look through PHIs to regions post-dominating 135 the DSE candidate stmt. */ 136 || !dominated_by_p (CDI_POST_DOMINATORS, 137 gimple_bb (stmt), gimple_bb (use_stmt))) 138 { 139 fail = true; 140 BREAK_FROM_IMM_USE_STMT (ui); 141 } 142 temp = use_stmt; 143 } 144 /* If the statement is a use the store is not dead. */ 145 else if (ref_maybe_used_by_stmt_p (use_stmt, 146 gimple_assign_lhs (stmt))) 147 { 148 fail = true; 149 BREAK_FROM_IMM_USE_STMT (ui); 150 } 151 /* If this is a store, remember it or bail out if we have 152 multiple ones (the will be in different CFG parts then). */ 153 else if (gimple_vdef (use_stmt)) 154 { 155 if (temp) 156 { 157 fail = true; 158 BREAK_FROM_IMM_USE_STMT (ui); 159 } 160 temp = use_stmt; 161 } 162 } 163 164 if (fail) 165 return false; 166 167 /* If we didn't find any definition this means the store is dead 168 if it isn't a store to global reachable memory. In this case 169 just pretend the stmt makes itself dead. Otherwise fail. */ 170 if (!temp) 171 { 172 if (is_hidden_global_store (stmt)) 173 return false; 174 175 temp = stmt; 176 break; 177 } 178 } 179 /* We deliberately stop on clobbering statements and not only on 180 killing ones to make walking cheaper. Otherwise we can just 181 continue walking until both stores have equal reference trees. */ 182 while (!stmt_may_clobber_ref_p (temp, gimple_assign_lhs (stmt))); 183 184 *use_stmt = temp; 185 186 return true; 187 } 188 189 190 /* Attempt to eliminate dead stores in the statement referenced by BSI. 191 192 A dead store is a store into a memory location which will later be 193 overwritten by another store without any intervening loads. In this 194 case the earlier store can be deleted. 195 196 In our SSA + virtual operand world we use immediate uses of virtual 197 operands to detect dead stores. If a store's virtual definition 198 is used precisely once by a later store to the same location which 199 post dominates the first store, then the first store is dead. */ 200 201 static void 202 dse_optimize_stmt (gimple_stmt_iterator gsi) 203 { 204 gimple stmt = gsi_stmt (gsi); 205 206 /* If this statement has no virtual defs, then there is nothing 207 to do. */ 208 if (!gimple_vdef (stmt)) 209 return; 210 211 /* We know we have virtual definitions. If this is a GIMPLE_ASSIGN 212 that's not also a function call, then record it into our table. */ 213 if (is_gimple_call (stmt) && gimple_call_fndecl (stmt)) 214 return; 215 216 if (gimple_has_volatile_ops (stmt)) 217 return; 218 219 if (is_gimple_assign (stmt)) 220 { 221 gimple use_stmt; 222 223 if (!dse_possible_dead_store_p (stmt, &use_stmt)) 224 return; 225 226 /* If we have precisely one immediate use at this point and the 227 stores are to the same memory location or there is a chain of 228 virtual uses from stmt and the stmt which stores to that same 229 memory location, then we may have found redundant store. */ 230 if ((gimple_has_lhs (use_stmt) 231 && (operand_equal_p (gimple_assign_lhs (stmt), 232 gimple_get_lhs (use_stmt), 0))) 233 || stmt_kills_ref_p (use_stmt, gimple_assign_lhs (stmt))) 234 { 235 /* If use_stmt is or might be a nop assignment, e.g. for 236 struct { ... } S a, b, *p; ... 237 b = a; b = b; 238 or 239 b = a; b = *p; where p might be &b, 240 or 241 *p = a; *p = b; where p might be &b, 242 or 243 *p = *u; *p = *v; where p might be v, then USE_STMT 244 acts as a use as well as definition, so store in STMT 245 is not dead. */ 246 if (stmt != use_stmt 247 && ref_maybe_used_by_stmt_p (use_stmt, gimple_assign_lhs (stmt))) 248 return; 249 250 if (dump_file && (dump_flags & TDF_DETAILS)) 251 { 252 fprintf (dump_file, " Deleted dead store '"); 253 print_gimple_stmt (dump_file, gsi_stmt (gsi), dump_flags, 0); 254 fprintf (dump_file, "'\n"); 255 } 256 257 /* Then we need to fix the operand of the consuming stmt. */ 258 unlink_stmt_vdef (stmt); 259 260 bitmap_set_bit (need_eh_cleanup, gimple_bb (stmt)->index); 261 262 /* Remove the dead store. */ 263 gsi_remove (&gsi, true); 264 265 /* And release any SSA_NAMEs set in this statement back to the 266 SSA_NAME manager. */ 267 release_defs (stmt); 268 } 269 } 270 } 271 272 static void 273 dse_enter_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, 274 basic_block bb) 275 { 276 gimple_stmt_iterator gsi; 277 278 for (gsi = gsi_last (bb_seq (bb)); !gsi_end_p (gsi); gsi_prev (&gsi)) 279 dse_optimize_stmt (gsi); 280 } 281 282 /* Main entry point. */ 283 284 static unsigned int 285 tree_ssa_dse (void) 286 { 287 struct dom_walk_data walk_data; 288 289 need_eh_cleanup = BITMAP_ALLOC (NULL); 290 291 renumber_gimple_stmt_uids (); 292 293 /* We might consider making this a property of each pass so that it 294 can be [re]computed on an as-needed basis. Particularly since 295 this pass could be seen as an extension of DCE which needs post 296 dominators. */ 297 calculate_dominance_info (CDI_POST_DOMINATORS); 298 calculate_dominance_info (CDI_DOMINATORS); 299 300 /* Dead store elimination is fundamentally a walk of the post-dominator 301 tree and a backwards walk of statements within each block. */ 302 walk_data.dom_direction = CDI_POST_DOMINATORS; 303 walk_data.initialize_block_local_data = NULL; 304 walk_data.before_dom_children = dse_enter_block; 305 walk_data.after_dom_children = NULL; 306 307 walk_data.block_local_data_size = 0; 308 walk_data.global_data = NULL; 309 310 /* Initialize the dominator walker. */ 311 init_walk_dominator_tree (&walk_data); 312 313 /* Recursively walk the dominator tree. */ 314 walk_dominator_tree (&walk_data, EXIT_BLOCK_PTR); 315 316 /* Finalize the dominator walker. */ 317 fini_walk_dominator_tree (&walk_data); 318 319 /* Removal of stores may make some EH edges dead. Purge such edges from 320 the CFG as needed. */ 321 if (!bitmap_empty_p (need_eh_cleanup)) 322 { 323 gimple_purge_all_dead_eh_edges (need_eh_cleanup); 324 cleanup_tree_cfg (); 325 } 326 327 BITMAP_FREE (need_eh_cleanup); 328 329 /* For now, just wipe the post-dominator information. */ 330 free_dominance_info (CDI_POST_DOMINATORS); 331 return 0; 332 } 333 334 static bool 335 gate_dse (void) 336 { 337 return flag_tree_dse != 0; 338 } 339 340 struct gimple_opt_pass pass_dse = 341 { 342 { 343 GIMPLE_PASS, 344 "dse", /* name */ 345 gate_dse, /* gate */ 346 tree_ssa_dse, /* execute */ 347 NULL, /* sub */ 348 NULL, /* next */ 349 0, /* static_pass_number */ 350 TV_TREE_DSE, /* tv_id */ 351 PROP_cfg | PROP_ssa, /* properties_required */ 352 0, /* properties_provided */ 353 0, /* properties_destroyed */ 354 0, /* todo_flags_start */ 355 TODO_ggc_collect 356 | TODO_verify_ssa /* todo_flags_finish */ 357 } 358 }; 359