1 /* Dead store elimination 2 Copyright (C) 2004-2017 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 "backend.h" 24 #include "rtl.h" 25 #include "tree.h" 26 #include "gimple.h" 27 #include "tree-pass.h" 28 #include "ssa.h" 29 #include "gimple-pretty-print.h" 30 #include "fold-const.h" 31 #include "gimple-iterator.h" 32 #include "tree-cfg.h" 33 #include "tree-dfa.h" 34 #include "domwalk.h" 35 #include "tree-cfgcleanup.h" 36 #include "params.h" 37 #include "alias.h" 38 39 /* This file implements dead store elimination. 40 41 A dead store is a store into a memory location which will later be 42 overwritten by another store without any intervening loads. In this 43 case the earlier store can be deleted. 44 45 In our SSA + virtual operand world we use immediate uses of virtual 46 operands to detect dead stores. If a store's virtual definition 47 is used precisely once by a later store to the same location which 48 post dominates the first store, then the first store is dead. 49 50 The single use of the store's virtual definition ensures that 51 there are no intervening aliased loads and the requirement that 52 the second load post dominate the first ensures that if the earlier 53 store executes, then the later stores will execute before the function 54 exits. 55 56 It may help to think of this as first moving the earlier store to 57 the point immediately before the later store. Again, the single 58 use of the virtual definition and the post-dominance relationship 59 ensure that such movement would be safe. Clearly if there are 60 back to back stores, then the second is redundant. 61 62 Reviewing section 10.7.2 in Morgan's "Building an Optimizing Compiler" 63 may also help in understanding this code since it discusses the 64 relationship between dead store and redundant load elimination. In 65 fact, they are the same transformation applied to different views of 66 the CFG. */ 67 68 69 /* Bitmap of blocks that have had EH statements cleaned. We should 70 remove their dead edges eventually. */ 71 static bitmap need_eh_cleanup; 72 73 /* Return value from dse_classify_store */ 74 enum dse_store_status 75 { 76 DSE_STORE_LIVE, 77 DSE_STORE_MAYBE_PARTIAL_DEAD, 78 DSE_STORE_DEAD 79 }; 80 81 /* STMT is a statement that may write into memory. Analyze it and 82 initialize WRITE to describe how STMT affects memory. 83 84 Return TRUE if the the statement was analyzed, FALSE otherwise. 85 86 It is always safe to return FALSE. But typically better optimziation 87 can be achieved by analyzing more statements. */ 88 89 static bool 90 initialize_ao_ref_for_dse (gimple *stmt, ao_ref *write) 91 { 92 /* It's advantageous to handle certain mem* functions. */ 93 if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL)) 94 { 95 switch (DECL_FUNCTION_CODE (gimple_call_fndecl (stmt))) 96 { 97 case BUILT_IN_MEMCPY: 98 case BUILT_IN_MEMMOVE: 99 case BUILT_IN_MEMSET: 100 { 101 tree size = NULL_TREE; 102 if (gimple_call_num_args (stmt) == 3) 103 size = gimple_call_arg (stmt, 2); 104 tree ptr = gimple_call_arg (stmt, 0); 105 ao_ref_init_from_ptr_and_size (write, ptr, size); 106 return true; 107 } 108 default: 109 break; 110 } 111 } 112 else if (is_gimple_assign (stmt)) 113 { 114 ao_ref_init (write, gimple_assign_lhs (stmt)); 115 return true; 116 } 117 return false; 118 } 119 120 /* Given REF from the the alias oracle, return TRUE if it is a valid 121 memory reference for dead store elimination, false otherwise. 122 123 In particular, the reference must have a known base, known maximum 124 size, start at a byte offset and have a size that is one or more 125 bytes. */ 126 127 static bool 128 valid_ao_ref_for_dse (ao_ref *ref) 129 { 130 return (ao_ref_base (ref) 131 && ref->max_size != -1 132 && ref->size != 0 133 && ref->max_size == ref->size 134 && (ref->offset % BITS_PER_UNIT) == 0 135 && (ref->size % BITS_PER_UNIT) == 0 136 && (ref->size != -1)); 137 } 138 139 /* Normalize COPY (an ao_ref) relative to REF. Essentially when we are 140 done COPY will only refer bytes found within REF. 141 142 We have already verified that COPY intersects at least one 143 byte with REF. */ 144 145 static void 146 normalize_ref (ao_ref *copy, ao_ref *ref) 147 { 148 /* If COPY starts before REF, then reset the beginning of 149 COPY to match REF and decrease the size of COPY by the 150 number of bytes removed from COPY. */ 151 if (copy->offset < ref->offset) 152 { 153 copy->size -= (ref->offset - copy->offset); 154 copy->offset = ref->offset; 155 } 156 157 /* If COPY extends beyond REF, chop off its size appropriately. */ 158 if (copy->offset + copy->size > ref->offset + ref->size) 159 copy->size -= (copy->offset + copy->size - (ref->offset + ref->size)); 160 } 161 162 /* Clear any bytes written by STMT from the bitmap LIVE_BYTES. The base 163 address written by STMT must match the one found in REF, which must 164 have its base address previously initialized. 165 166 This routine must be conservative. If we don't know the offset or 167 actual size written, assume nothing was written. */ 168 169 static void 170 clear_bytes_written_by (sbitmap live_bytes, gimple *stmt, ao_ref *ref) 171 { 172 ao_ref write; 173 if (!initialize_ao_ref_for_dse (stmt, &write)) 174 return; 175 176 /* Verify we have the same base memory address, the write 177 has a known size and overlaps with REF. */ 178 if (valid_ao_ref_for_dse (&write) 179 && operand_equal_p (write.base, ref->base, OEP_ADDRESS_OF) 180 && write.size == write.max_size 181 && ((write.offset < ref->offset 182 && write.offset + write.size > ref->offset) 183 || (write.offset >= ref->offset 184 && write.offset < ref->offset + ref->size))) 185 { 186 normalize_ref (&write, ref); 187 bitmap_clear_range (live_bytes, 188 (write.offset - ref->offset) / BITS_PER_UNIT, 189 write.size / BITS_PER_UNIT); 190 } 191 } 192 193 /* REF is a memory write. Extract relevant information from it and 194 initialize the LIVE_BYTES bitmap. If successful, return TRUE. 195 Otherwise return FALSE. */ 196 197 static bool 198 setup_live_bytes_from_ref (ao_ref *ref, sbitmap live_bytes) 199 { 200 if (valid_ao_ref_for_dse (ref) 201 && (ref->size / BITS_PER_UNIT 202 <= PARAM_VALUE (PARAM_DSE_MAX_OBJECT_SIZE))) 203 { 204 bitmap_clear (live_bytes); 205 bitmap_set_range (live_bytes, 0, ref->size / BITS_PER_UNIT); 206 return true; 207 } 208 return false; 209 } 210 211 /* Compute the number of elements that we can trim from the head and 212 tail of ORIG resulting in a bitmap that is a superset of LIVE. 213 214 Store the number of elements trimmed from the head and tail in 215 TRIM_HEAD and TRIM_TAIL. 216 217 STMT is the statement being trimmed and is used for debugging dump 218 output only. */ 219 220 static void 221 compute_trims (ao_ref *ref, sbitmap live, int *trim_head, int *trim_tail, 222 gimple *stmt) 223 { 224 /* We use sbitmaps biased such that ref->offset is bit zero and the bitmap 225 extends through ref->size. So we know that in the original bitmap 226 bits 0..ref->size were true. We don't actually need the bitmap, just 227 the REF to compute the trims. */ 228 229 /* Now identify how much, if any of the tail we can chop off. */ 230 int last_orig = (ref->size / BITS_PER_UNIT) - 1; 231 int last_live = bitmap_last_set_bit (live); 232 *trim_tail = (last_orig - last_live) & ~0x1; 233 234 /* Identify how much, if any of the head we can chop off. */ 235 int first_orig = 0; 236 int first_live = bitmap_first_set_bit (live); 237 *trim_head = (first_live - first_orig) & ~0x1; 238 239 if ((*trim_head || *trim_tail) 240 && dump_file && (dump_flags & TDF_DETAILS)) 241 { 242 fprintf (dump_file, " Trimming statement (head = %d, tail = %d): ", 243 *trim_head, *trim_tail); 244 print_gimple_stmt (dump_file, stmt, dump_flags, 0); 245 fprintf (dump_file, "\n"); 246 } 247 } 248 249 /* STMT initializes an object from COMPLEX_CST where one or more of the 250 bytes written may be dead stores. REF is a representation of the 251 memory written. LIVE is the bitmap of stores that are actually live. 252 253 Attempt to rewrite STMT so that only the real or imaginary part of 254 the object is actually stored. */ 255 256 static void 257 maybe_trim_complex_store (ao_ref *ref, sbitmap live, gimple *stmt) 258 { 259 int trim_head, trim_tail; 260 compute_trims (ref, live, &trim_head, &trim_tail, stmt); 261 262 /* The amount of data trimmed from the head or tail must be at 263 least half the size of the object to ensure we're trimming 264 the entire real or imaginary half. By writing things this 265 way we avoid more O(n) bitmap operations. */ 266 if (trim_tail * 2 >= ref->size / BITS_PER_UNIT) 267 { 268 /* TREE_REALPART is live */ 269 tree x = TREE_REALPART (gimple_assign_rhs1 (stmt)); 270 tree y = gimple_assign_lhs (stmt); 271 y = build1 (REALPART_EXPR, TREE_TYPE (x), y); 272 gimple_assign_set_lhs (stmt, y); 273 gimple_assign_set_rhs1 (stmt, x); 274 } 275 else if (trim_head * 2 >= ref->size / BITS_PER_UNIT) 276 { 277 /* TREE_IMAGPART is live */ 278 tree x = TREE_IMAGPART (gimple_assign_rhs1 (stmt)); 279 tree y = gimple_assign_lhs (stmt); 280 y = build1 (IMAGPART_EXPR, TREE_TYPE (x), y); 281 gimple_assign_set_lhs (stmt, y); 282 gimple_assign_set_rhs1 (stmt, x); 283 } 284 285 /* Other cases indicate parts of both the real and imag subobjects 286 are live. We do not try to optimize those cases. */ 287 } 288 289 /* STMT initializes an object using a CONSTRUCTOR where one or more of the 290 bytes written are dead stores. ORIG is the bitmap of bytes stored by 291 STMT. LIVE is the bitmap of stores that are actually live. 292 293 Attempt to rewrite STMT so that only the real or imaginary part of 294 the object is actually stored. 295 296 The most common case for getting here is a CONSTRUCTOR with no elements 297 being used to zero initialize an object. We do not try to handle other 298 cases as those would force us to fully cover the object with the 299 CONSTRUCTOR node except for the components that are dead. */ 300 301 static void 302 maybe_trim_constructor_store (ao_ref *ref, sbitmap live, gimple *stmt) 303 { 304 tree ctor = gimple_assign_rhs1 (stmt); 305 306 /* This is the only case we currently handle. It actually seems to 307 catch most cases of actual interest. */ 308 gcc_assert (CONSTRUCTOR_NELTS (ctor) == 0); 309 310 int head_trim = 0; 311 int tail_trim = 0; 312 compute_trims (ref, live, &head_trim, &tail_trim, stmt); 313 314 /* Now we want to replace the constructor initializer 315 with memset (object + head_trim, 0, size - head_trim - tail_trim). */ 316 if (head_trim || tail_trim) 317 { 318 /* We want &lhs for the MEM_REF expression. */ 319 tree lhs_addr = build_fold_addr_expr (gimple_assign_lhs (stmt)); 320 321 if (! is_gimple_min_invariant (lhs_addr)) 322 return; 323 324 /* The number of bytes for the new constructor. */ 325 int count = (ref->size / BITS_PER_UNIT) - head_trim - tail_trim; 326 327 /* And the new type for the CONSTRUCTOR. Essentially it's just 328 a char array large enough to cover the non-trimmed parts of 329 the original CONSTRUCTOR. Note we want explicit bounds here 330 so that we know how many bytes to clear when expanding the 331 CONSTRUCTOR. */ 332 tree type = build_array_type_nelts (char_type_node, count); 333 334 /* Build a suitable alias type rather than using alias set zero 335 to avoid pessimizing. */ 336 tree alias_type = reference_alias_ptr_type (gimple_assign_lhs (stmt)); 337 338 /* Build a MEM_REF representing the whole accessed area, starting 339 at the first byte not trimmed. */ 340 tree exp = fold_build2 (MEM_REF, type, lhs_addr, 341 build_int_cst (alias_type, head_trim)); 342 343 /* Now update STMT with a new RHS and LHS. */ 344 gimple_assign_set_lhs (stmt, exp); 345 gimple_assign_set_rhs1 (stmt, build_constructor (type, NULL)); 346 } 347 } 348 349 /* STMT is a memcpy, memmove or memset. Decrement the number of bytes 350 copied/set by DECREMENT. */ 351 static void 352 decrement_count (gimple *stmt, int decrement) 353 { 354 tree *countp = gimple_call_arg_ptr (stmt, 2); 355 gcc_assert (TREE_CODE (*countp) == INTEGER_CST); 356 *countp = wide_int_to_tree (TREE_TYPE (*countp), (TREE_INT_CST_LOW (*countp) 357 - decrement)); 358 359 } 360 361 static void 362 increment_start_addr (gimple *stmt, tree *where, int increment) 363 { 364 if (TREE_CODE (*where) == SSA_NAME) 365 { 366 tree tem = make_ssa_name (TREE_TYPE (*where)); 367 gassign *newop 368 = gimple_build_assign (tem, POINTER_PLUS_EXPR, *where, 369 build_int_cst (sizetype, increment)); 370 gimple_stmt_iterator gsi = gsi_for_stmt (stmt); 371 gsi_insert_before (&gsi, newop, GSI_SAME_STMT); 372 *where = tem; 373 update_stmt (gsi_stmt (gsi)); 374 return; 375 } 376 377 *where = build_fold_addr_expr (fold_build2 (MEM_REF, char_type_node, 378 *where, 379 build_int_cst (ptr_type_node, 380 increment))); 381 } 382 383 /* STMT is builtin call that writes bytes in bitmap ORIG, some bytes are dead 384 (ORIG & ~NEW) and need not be stored. Try to rewrite STMT to reduce 385 the amount of data it actually writes. 386 387 Right now we only support trimming from the head or the tail of the 388 memory region. In theory we could split the mem* call, but it's 389 likely of marginal value. */ 390 391 static void 392 maybe_trim_memstar_call (ao_ref *ref, sbitmap live, gimple *stmt) 393 { 394 switch (DECL_FUNCTION_CODE (gimple_call_fndecl (stmt))) 395 { 396 case BUILT_IN_MEMCPY: 397 case BUILT_IN_MEMMOVE: 398 { 399 int head_trim, tail_trim; 400 compute_trims (ref, live, &head_trim, &tail_trim, stmt); 401 402 /* Tail trimming is easy, we can just reduce the count. */ 403 if (tail_trim) 404 decrement_count (stmt, tail_trim); 405 406 /* Head trimming requires adjusting all the arguments. */ 407 if (head_trim) 408 { 409 tree *dst = gimple_call_arg_ptr (stmt, 0); 410 increment_start_addr (stmt, dst, head_trim); 411 tree *src = gimple_call_arg_ptr (stmt, 1); 412 increment_start_addr (stmt, src, head_trim); 413 decrement_count (stmt, head_trim); 414 } 415 break; 416 } 417 418 case BUILT_IN_MEMSET: 419 { 420 int head_trim, tail_trim; 421 compute_trims (ref, live, &head_trim, &tail_trim, stmt); 422 423 /* Tail trimming is easy, we can just reduce the count. */ 424 if (tail_trim) 425 decrement_count (stmt, tail_trim); 426 427 /* Head trimming requires adjusting all the arguments. */ 428 if (head_trim) 429 { 430 tree *dst = gimple_call_arg_ptr (stmt, 0); 431 increment_start_addr (stmt, dst, head_trim); 432 decrement_count (stmt, head_trim); 433 } 434 break; 435 } 436 437 default: 438 break; 439 } 440 } 441 442 /* STMT is a memory write where one or more bytes written are dead 443 stores. ORIG is the bitmap of bytes stored by STMT. LIVE is the 444 bitmap of stores that are actually live. 445 446 Attempt to rewrite STMT so that it writes fewer memory locations. Right 447 now we only support trimming at the start or end of the memory region. 448 It's not clear how much there is to be gained by trimming from the middle 449 of the region. */ 450 451 static void 452 maybe_trim_partially_dead_store (ao_ref *ref, sbitmap live, gimple *stmt) 453 { 454 if (is_gimple_assign (stmt) 455 && TREE_CODE (gimple_assign_lhs (stmt)) != TARGET_MEM_REF) 456 { 457 switch (gimple_assign_rhs_code (stmt)) 458 { 459 case CONSTRUCTOR: 460 maybe_trim_constructor_store (ref, live, stmt); 461 break; 462 case COMPLEX_CST: 463 maybe_trim_complex_store (ref, live, stmt); 464 break; 465 default: 466 break; 467 } 468 } 469 } 470 471 /* A helper of dse_optimize_stmt. 472 Given a GIMPLE_ASSIGN in STMT that writes to REF, find a candidate 473 statement *USE_STMT that may prove STMT to be dead. 474 Return TRUE if the above conditions are met, otherwise FALSE. */ 475 476 static dse_store_status 477 dse_classify_store (ao_ref *ref, gimple *stmt, gimple **use_stmt, 478 bool byte_tracking_enabled, sbitmap live_bytes) 479 { 480 gimple *temp; 481 unsigned cnt = 0; 482 483 *use_stmt = NULL; 484 485 /* Find the first dominated statement that clobbers (part of) the 486 memory stmt stores to with no intermediate statement that may use 487 part of the memory stmt stores. That is, find a store that may 488 prove stmt to be a dead store. */ 489 temp = stmt; 490 do 491 { 492 gimple *use_stmt, *defvar_def; 493 imm_use_iterator ui; 494 bool fail = false; 495 tree defvar; 496 497 /* Limit stmt walking to be linear in the number of possibly 498 dead stores. */ 499 if (++cnt > 256) 500 return DSE_STORE_LIVE; 501 502 if (gimple_code (temp) == GIMPLE_PHI) 503 defvar = PHI_RESULT (temp); 504 else 505 defvar = gimple_vdef (temp); 506 defvar_def = temp; 507 temp = NULL; 508 FOR_EACH_IMM_USE_STMT (use_stmt, ui, defvar) 509 { 510 cnt++; 511 512 /* If we ever reach our DSE candidate stmt again fail. We 513 cannot handle dead stores in loops. */ 514 if (use_stmt == stmt) 515 { 516 fail = true; 517 BREAK_FROM_IMM_USE_STMT (ui); 518 } 519 /* In simple cases we can look through PHI nodes, but we 520 have to be careful with loops and with memory references 521 containing operands that are also operands of PHI nodes. 522 See gcc.c-torture/execute/20051110-*.c. */ 523 else if (gimple_code (use_stmt) == GIMPLE_PHI) 524 { 525 if (temp 526 /* Make sure we are not in a loop latch block. */ 527 || gimple_bb (stmt) == gimple_bb (use_stmt) 528 || dominated_by_p (CDI_DOMINATORS, 529 gimple_bb (stmt), gimple_bb (use_stmt)) 530 /* We can look through PHIs to regions post-dominating 531 the DSE candidate stmt. */ 532 || !dominated_by_p (CDI_POST_DOMINATORS, 533 gimple_bb (stmt), gimple_bb (use_stmt))) 534 { 535 fail = true; 536 BREAK_FROM_IMM_USE_STMT (ui); 537 } 538 /* Do not consider the PHI as use if it dominates the 539 stmt defining the virtual operand we are processing, 540 we have processed it already in this case. */ 541 if (gimple_bb (defvar_def) != gimple_bb (use_stmt) 542 && !dominated_by_p (CDI_DOMINATORS, 543 gimple_bb (defvar_def), 544 gimple_bb (use_stmt))) 545 temp = use_stmt; 546 } 547 /* If the statement is a use the store is not dead. */ 548 else if (ref_maybe_used_by_stmt_p (use_stmt, ref)) 549 { 550 fail = true; 551 BREAK_FROM_IMM_USE_STMT (ui); 552 } 553 /* If this is a store, remember it or bail out if we have 554 multiple ones (the will be in different CFG parts then). */ 555 else if (gimple_vdef (use_stmt)) 556 { 557 if (temp) 558 { 559 fail = true; 560 BREAK_FROM_IMM_USE_STMT (ui); 561 } 562 temp = use_stmt; 563 } 564 } 565 566 if (fail) 567 { 568 /* STMT might be partially dead and we may be able to reduce 569 how many memory locations it stores into. */ 570 if (byte_tracking_enabled && !gimple_clobber_p (stmt)) 571 return DSE_STORE_MAYBE_PARTIAL_DEAD; 572 return DSE_STORE_LIVE; 573 } 574 575 /* If we didn't find any definition this means the store is dead 576 if it isn't a store to global reachable memory. In this case 577 just pretend the stmt makes itself dead. Otherwise fail. */ 578 if (!temp) 579 { 580 if (ref_may_alias_global_p (ref)) 581 return DSE_STORE_LIVE; 582 583 temp = stmt; 584 break; 585 } 586 587 if (byte_tracking_enabled && temp) 588 clear_bytes_written_by (live_bytes, temp, ref); 589 } 590 /* Continue walking until we reach a full kill as a single statement 591 or there are no more live bytes. */ 592 while (!stmt_kills_ref_p (temp, ref) 593 && !(byte_tracking_enabled && bitmap_empty_p (live_bytes))); 594 595 *use_stmt = temp; 596 return DSE_STORE_DEAD; 597 } 598 599 600 class dse_dom_walker : public dom_walker 601 { 602 public: 603 dse_dom_walker (cdi_direction direction) 604 : dom_walker (direction), m_byte_tracking_enabled (false) 605 606 { m_live_bytes = sbitmap_alloc (PARAM_VALUE (PARAM_DSE_MAX_OBJECT_SIZE)); } 607 608 ~dse_dom_walker () { sbitmap_free (m_live_bytes); } 609 610 virtual edge before_dom_children (basic_block); 611 612 private: 613 sbitmap m_live_bytes; 614 bool m_byte_tracking_enabled; 615 void dse_optimize_stmt (gimple_stmt_iterator *); 616 }; 617 618 /* Delete a dead call at GSI, which is mem* call of some kind. */ 619 static void 620 delete_dead_call (gimple_stmt_iterator *gsi) 621 { 622 gimple *stmt = gsi_stmt (*gsi); 623 if (dump_file && (dump_flags & TDF_DETAILS)) 624 { 625 fprintf (dump_file, " Deleted dead call: "); 626 print_gimple_stmt (dump_file, stmt, dump_flags, 0); 627 fprintf (dump_file, "\n"); 628 } 629 630 tree lhs = gimple_call_lhs (stmt); 631 if (lhs) 632 { 633 tree ptr = gimple_call_arg (stmt, 0); 634 gimple *new_stmt = gimple_build_assign (lhs, ptr); 635 unlink_stmt_vdef (stmt); 636 if (gsi_replace (gsi, new_stmt, true)) 637 bitmap_set_bit (need_eh_cleanup, gimple_bb (stmt)->index); 638 } 639 else 640 { 641 /* Then we need to fix the operand of the consuming stmt. */ 642 unlink_stmt_vdef (stmt); 643 644 /* Remove the dead store. */ 645 if (gsi_remove (gsi, true)) 646 bitmap_set_bit (need_eh_cleanup, gimple_bb (stmt)->index); 647 release_defs (stmt); 648 } 649 } 650 651 /* Delete a dead store at GSI, which is a gimple assignment. */ 652 653 static void 654 delete_dead_assignment (gimple_stmt_iterator *gsi) 655 { 656 gimple *stmt = gsi_stmt (*gsi); 657 if (dump_file && (dump_flags & TDF_DETAILS)) 658 { 659 fprintf (dump_file, " Deleted dead store: "); 660 print_gimple_stmt (dump_file, stmt, dump_flags, 0); 661 fprintf (dump_file, "\n"); 662 } 663 664 /* Then we need to fix the operand of the consuming stmt. */ 665 unlink_stmt_vdef (stmt); 666 667 /* Remove the dead store. */ 668 basic_block bb = gimple_bb (stmt); 669 if (gsi_remove (gsi, true)) 670 bitmap_set_bit (need_eh_cleanup, bb->index); 671 672 /* And release any SSA_NAMEs set in this statement back to the 673 SSA_NAME manager. */ 674 release_defs (stmt); 675 } 676 677 /* Attempt to eliminate dead stores in the statement referenced by BSI. 678 679 A dead store is a store into a memory location which will later be 680 overwritten by another store without any intervening loads. In this 681 case the earlier store can be deleted. 682 683 In our SSA + virtual operand world we use immediate uses of virtual 684 operands to detect dead stores. If a store's virtual definition 685 is used precisely once by a later store to the same location which 686 post dominates the first store, then the first store is dead. */ 687 688 void 689 dse_dom_walker::dse_optimize_stmt (gimple_stmt_iterator *gsi) 690 { 691 gimple *stmt = gsi_stmt (*gsi); 692 693 /* If this statement has no virtual defs, then there is nothing 694 to do. */ 695 if (!gimple_vdef (stmt)) 696 return; 697 698 /* Don't return early on *this_2(D) ={v} {CLOBBER}. */ 699 if (gimple_has_volatile_ops (stmt) 700 && (!gimple_clobber_p (stmt) 701 || TREE_CODE (gimple_assign_lhs (stmt)) != MEM_REF)) 702 return; 703 704 ao_ref ref; 705 if (!initialize_ao_ref_for_dse (stmt, &ref)) 706 return; 707 708 /* We know we have virtual definitions. We can handle assignments and 709 some builtin calls. */ 710 if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL)) 711 { 712 switch (DECL_FUNCTION_CODE (gimple_call_fndecl (stmt))) 713 { 714 case BUILT_IN_MEMCPY: 715 case BUILT_IN_MEMMOVE: 716 case BUILT_IN_MEMSET: 717 { 718 /* Occasionally calls with an explicit length of zero 719 show up in the IL. It's pointless to do analysis 720 on them, they're trivially dead. */ 721 tree size = gimple_call_arg (stmt, 2); 722 if (integer_zerop (size)) 723 { 724 delete_dead_call (gsi); 725 return; 726 } 727 728 gimple *use_stmt; 729 enum dse_store_status store_status; 730 m_byte_tracking_enabled 731 = setup_live_bytes_from_ref (&ref, m_live_bytes); 732 store_status = dse_classify_store (&ref, stmt, &use_stmt, 733 m_byte_tracking_enabled, 734 m_live_bytes); 735 if (store_status == DSE_STORE_LIVE) 736 return; 737 738 if (store_status == DSE_STORE_MAYBE_PARTIAL_DEAD) 739 { 740 maybe_trim_memstar_call (&ref, m_live_bytes, stmt); 741 return; 742 } 743 744 if (store_status == DSE_STORE_DEAD) 745 delete_dead_call (gsi); 746 return; 747 } 748 749 default: 750 return; 751 } 752 } 753 754 if (is_gimple_assign (stmt)) 755 { 756 gimple *use_stmt; 757 758 /* Self-assignments are zombies. */ 759 if (operand_equal_p (gimple_assign_rhs1 (stmt), 760 gimple_assign_lhs (stmt), 0)) 761 use_stmt = stmt; 762 else 763 { 764 m_byte_tracking_enabled 765 = setup_live_bytes_from_ref (&ref, m_live_bytes); 766 enum dse_store_status store_status; 767 store_status = dse_classify_store (&ref, stmt, &use_stmt, 768 m_byte_tracking_enabled, 769 m_live_bytes); 770 if (store_status == DSE_STORE_LIVE) 771 return; 772 773 if (store_status == DSE_STORE_MAYBE_PARTIAL_DEAD) 774 { 775 maybe_trim_partially_dead_store (&ref, m_live_bytes, stmt); 776 return; 777 } 778 } 779 780 /* Now we know that use_stmt kills the LHS of stmt. */ 781 782 /* But only remove *this_2(D) ={v} {CLOBBER} if killed by 783 another clobber stmt. */ 784 if (gimple_clobber_p (stmt) 785 && !gimple_clobber_p (use_stmt)) 786 return; 787 788 delete_dead_assignment (gsi); 789 } 790 } 791 792 edge 793 dse_dom_walker::before_dom_children (basic_block bb) 794 { 795 gimple_stmt_iterator gsi; 796 797 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi);) 798 { 799 dse_optimize_stmt (&gsi); 800 if (gsi_end_p (gsi)) 801 gsi = gsi_last_bb (bb); 802 else 803 gsi_prev (&gsi); 804 } 805 return NULL; 806 } 807 808 namespace { 809 810 const pass_data pass_data_dse = 811 { 812 GIMPLE_PASS, /* type */ 813 "dse", /* name */ 814 OPTGROUP_NONE, /* optinfo_flags */ 815 TV_TREE_DSE, /* tv_id */ 816 ( PROP_cfg | PROP_ssa ), /* properties_required */ 817 0, /* properties_provided */ 818 0, /* properties_destroyed */ 819 0, /* todo_flags_start */ 820 0, /* todo_flags_finish */ 821 }; 822 823 class pass_dse : public gimple_opt_pass 824 { 825 public: 826 pass_dse (gcc::context *ctxt) 827 : gimple_opt_pass (pass_data_dse, ctxt) 828 {} 829 830 /* opt_pass methods: */ 831 opt_pass * clone () { return new pass_dse (m_ctxt); } 832 virtual bool gate (function *) { return flag_tree_dse != 0; } 833 virtual unsigned int execute (function *); 834 835 }; // class pass_dse 836 837 unsigned int 838 pass_dse::execute (function *fun) 839 { 840 need_eh_cleanup = BITMAP_ALLOC (NULL); 841 842 renumber_gimple_stmt_uids (); 843 844 /* We might consider making this a property of each pass so that it 845 can be [re]computed on an as-needed basis. Particularly since 846 this pass could be seen as an extension of DCE which needs post 847 dominators. */ 848 calculate_dominance_info (CDI_POST_DOMINATORS); 849 calculate_dominance_info (CDI_DOMINATORS); 850 851 /* Dead store elimination is fundamentally a walk of the post-dominator 852 tree and a backwards walk of statements within each block. */ 853 dse_dom_walker (CDI_POST_DOMINATORS).walk (fun->cfg->x_exit_block_ptr); 854 855 /* Removal of stores may make some EH edges dead. Purge such edges from 856 the CFG as needed. */ 857 if (!bitmap_empty_p (need_eh_cleanup)) 858 { 859 gimple_purge_all_dead_eh_edges (need_eh_cleanup); 860 cleanup_tree_cfg (); 861 } 862 863 BITMAP_FREE (need_eh_cleanup); 864 865 /* For now, just wipe the post-dominator information. */ 866 free_dominance_info (CDI_POST_DOMINATORS); 867 return 0; 868 } 869 870 } // anon namespace 871 872 gimple_opt_pass * 873 make_pass_dse (gcc::context *ctxt) 874 { 875 return new pass_dse (ctxt); 876 } 877