1/* Dead and redundant store elimination 2 Copyright (C) 2004-2022 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 3, 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 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 "tree-cfgcleanup.h" 35#include "alias.h" 36#include "tree-ssa-loop.h" 37#include "tree-ssa-dse.h" 38#include "builtins.h" 39#include "gimple-fold.h" 40#include "gimplify.h" 41#include "tree-eh.h" 42#include "cfganal.h" 43#include "cgraph.h" 44#include "ipa-modref-tree.h" 45#include "ipa-modref.h" 46#include "target.h" 47#include "tree-ssa-loop-niter.h" 48 49/* This file implements dead store elimination. 50 51 A dead store is a store into a memory location which will later be 52 overwritten by another store without any intervening loads. In this 53 case the earlier store can be deleted or trimmed if the store 54 was partially dead. 55 56 A redundant store is a store into a memory location which stores 57 the exact same value as a prior store to the same memory location. 58 While this can often be handled by dead store elimination, removing 59 the redundant store is often better than removing or trimming the 60 dead store. 61 62 In our SSA + virtual operand world we use immediate uses of virtual 63 operands to detect these cases. If a store's virtual definition 64 is used precisely once by a later store to the same location which 65 post dominates the first store, then the first store is dead. If 66 the data stored is the same, then the second store is redundant. 67 68 The single use of the store's virtual definition ensures that 69 there are no intervening aliased loads and the requirement that 70 the second load post dominate the first ensures that if the earlier 71 store executes, then the later stores will execute before the function 72 exits. 73 74 It may help to think of this as first moving the earlier store to 75 the point immediately before the later store. Again, the single 76 use of the virtual definition and the post-dominance relationship 77 ensure that such movement would be safe. Clearly if there are 78 back to back stores, then the second is makes the first dead. If 79 the second store stores the same value, then the second store is 80 redundant. 81 82 Reviewing section 10.7.2 in Morgan's "Building an Optimizing Compiler" 83 may also help in understanding this code since it discusses the 84 relationship between dead store and redundant load elimination. In 85 fact, they are the same transformation applied to different views of 86 the CFG. */ 87 88static void delete_dead_or_redundant_call (gimple_stmt_iterator *, const char *); 89 90/* Bitmap of blocks that have had EH statements cleaned. We should 91 remove their dead edges eventually. */ 92static bitmap need_eh_cleanup; 93static bitmap need_ab_cleanup; 94 95/* STMT is a statement that may write into memory. Analyze it and 96 initialize WRITE to describe how STMT affects memory. When 97 MAY_DEF_OK is true then the function initializes WRITE to what 98 the stmt may define. 99 100 Return TRUE if the statement was analyzed, FALSE otherwise. 101 102 It is always safe to return FALSE. But typically better optimziation 103 can be achieved by analyzing more statements. */ 104 105static bool 106initialize_ao_ref_for_dse (gimple *stmt, ao_ref *write, bool may_def_ok = false) 107{ 108 /* It's advantageous to handle certain mem* functions. */ 109 if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL)) 110 { 111 switch (DECL_FUNCTION_CODE (gimple_call_fndecl (stmt))) 112 { 113 case BUILT_IN_MEMCPY: 114 case BUILT_IN_MEMMOVE: 115 case BUILT_IN_MEMSET: 116 case BUILT_IN_MEMCPY_CHK: 117 case BUILT_IN_MEMMOVE_CHK: 118 case BUILT_IN_MEMSET_CHK: 119 case BUILT_IN_STRNCPY: 120 case BUILT_IN_STRNCPY_CHK: 121 { 122 tree size = gimple_call_arg (stmt, 2); 123 tree ptr = gimple_call_arg (stmt, 0); 124 ao_ref_init_from_ptr_and_size (write, ptr, size); 125 return true; 126 } 127 128 /* A calloc call can never be dead, but it can make 129 subsequent stores redundant if they store 0 into 130 the same memory locations. */ 131 case BUILT_IN_CALLOC: 132 { 133 tree nelem = gimple_call_arg (stmt, 0); 134 tree selem = gimple_call_arg (stmt, 1); 135 tree lhs; 136 if (TREE_CODE (nelem) == INTEGER_CST 137 && TREE_CODE (selem) == INTEGER_CST 138 && (lhs = gimple_call_lhs (stmt)) != NULL_TREE) 139 { 140 tree size = fold_build2 (MULT_EXPR, TREE_TYPE (nelem), 141 nelem, selem); 142 ao_ref_init_from_ptr_and_size (write, lhs, size); 143 return true; 144 } 145 } 146 147 default: 148 break; 149 } 150 } 151 else if (tree lhs = gimple_get_lhs (stmt)) 152 { 153 if (TREE_CODE (lhs) != SSA_NAME 154 && (may_def_ok || !stmt_could_throw_p (cfun, stmt))) 155 { 156 ao_ref_init (write, lhs); 157 return true; 158 } 159 } 160 return false; 161} 162 163/* Given REF from the alias oracle, return TRUE if it is a valid 164 kill memory reference for dead store elimination, false otherwise. 165 166 In particular, the reference must have a known base, known maximum 167 size, start at a byte offset and have a size that is one or more 168 bytes. */ 169 170static bool 171valid_ao_ref_kill_for_dse (ao_ref *ref) 172{ 173 return (ao_ref_base (ref) 174 && known_size_p (ref->max_size) 175 && maybe_ne (ref->size, 0) 176 && known_eq (ref->max_size, ref->size) 177 && known_ge (ref->offset, 0)); 178} 179 180/* Given REF from the alias oracle, return TRUE if it is a valid 181 load or store memory reference for dead store elimination, false otherwise. 182 183 Unlike for valid_ao_ref_kill_for_dse we can accept writes where max_size 184 is not same as size since we can handle conservatively the larger range. */ 185 186static bool 187valid_ao_ref_for_dse (ao_ref *ref) 188{ 189 return (ao_ref_base (ref) 190 && known_size_p (ref->max_size) 191 && known_ge (ref->offset, 0)); 192} 193 194/* Initialize OFFSET and SIZE to a range known to contain REF 195 where the boundaries are divisible by BITS_PER_UNIT (bit still in bits). 196 Return false if this is impossible. */ 197 198static bool 199get_byte_aligned_range_containing_ref (ao_ref *ref, poly_int64 *offset, 200 HOST_WIDE_INT *size) 201{ 202 if (!known_size_p (ref->max_size)) 203 return false; 204 *offset = aligned_lower_bound (ref->offset, BITS_PER_UNIT); 205 poly_int64 end = aligned_upper_bound (ref->offset + ref->max_size, 206 BITS_PER_UNIT); 207 return (end - *offset).is_constant (size); 208} 209 210/* Initialize OFFSET and SIZE to a range known to be contained REF 211 where the boundaries are divisible by BITS_PER_UNIT (but still in bits). 212 Return false if this is impossible. */ 213 214static bool 215get_byte_aligned_range_contained_in_ref (ao_ref *ref, poly_int64 *offset, 216 HOST_WIDE_INT *size) 217{ 218 if (!known_size_p (ref->size) 219 || !known_eq (ref->size, ref->max_size)) 220 return false; 221 *offset = aligned_upper_bound (ref->offset, BITS_PER_UNIT); 222 poly_int64 end = aligned_lower_bound (ref->offset + ref->max_size, 223 BITS_PER_UNIT); 224 /* For bit accesses we can get -1 here, but also 0 sized kill is not 225 useful. */ 226 if (!known_gt (end, *offset)) 227 return false; 228 return (end - *offset).is_constant (size); 229} 230 231/* Compute byte range (returned iN REF_OFFSET and RET_SIZE) for access COPY 232 inside REF. If KILL is true, then COPY represent a kill and the byte range 233 needs to be fully contained in bit range given by COPY. If KILL is false 234 then the byte range returned must contain the range of COPY. */ 235 236static bool 237get_byte_range (ao_ref *copy, ao_ref *ref, bool kill, 238 HOST_WIDE_INT *ret_offset, HOST_WIDE_INT *ret_size) 239{ 240 HOST_WIDE_INT copy_size, ref_size; 241 poly_int64 copy_offset, ref_offset; 242 HOST_WIDE_INT diff; 243 244 /* First translate from bits to bytes, rounding to bigger or smaller ranges 245 as needed. Kills needs to be always rounded to smaller ranges while 246 uses and stores to larger ranges. */ 247 if (kill) 248 { 249 if (!get_byte_aligned_range_contained_in_ref (copy, ©_offset, 250 ©_size)) 251 return false; 252 } 253 else 254 { 255 if (!get_byte_aligned_range_containing_ref (copy, ©_offset, 256 ©_size)) 257 return false; 258 } 259 260 if (!get_byte_aligned_range_containing_ref (ref, &ref_offset, &ref_size) 261 || !ordered_p (copy_offset, ref_offset)) 262 return false; 263 264 /* Switch sizes from bits to bytes so we do not need to care about 265 overflows. Offset calculation needs to stay in bits until we compute 266 the difference and can switch to HOST_WIDE_INT. */ 267 copy_size /= BITS_PER_UNIT; 268 ref_size /= BITS_PER_UNIT; 269 270 /* If COPY starts before REF, then reset the beginning of 271 COPY to match REF and decrease the size of COPY by the 272 number of bytes removed from COPY. */ 273 if (maybe_lt (copy_offset, ref_offset)) 274 { 275 if (!(ref_offset - copy_offset).is_constant (&diff) 276 || copy_size < diff / BITS_PER_UNIT) 277 return false; 278 copy_size -= diff / BITS_PER_UNIT; 279 copy_offset = ref_offset; 280 } 281 282 if (!(copy_offset - ref_offset).is_constant (&diff) 283 || ref_size <= diff / BITS_PER_UNIT) 284 return false; 285 286 /* If COPY extends beyond REF, chop off its size appropriately. */ 287 HOST_WIDE_INT limit = ref_size - diff / BITS_PER_UNIT; 288 289 if (copy_size > limit) 290 copy_size = limit; 291 *ret_size = copy_size; 292 if (!(copy_offset - ref_offset).is_constant (ret_offset)) 293 return false; 294 *ret_offset /= BITS_PER_UNIT; 295 return true; 296} 297 298/* Update LIVE_BYTES tracking REF for write to WRITE: 299 Verify we have the same base memory address, the write 300 has a known size and overlaps with REF. */ 301static void 302clear_live_bytes_for_ref (sbitmap live_bytes, ao_ref *ref, ao_ref *write) 303{ 304 HOST_WIDE_INT start, size; 305 306 if (valid_ao_ref_kill_for_dse (write) 307 && operand_equal_p (write->base, ref->base, OEP_ADDRESS_OF) 308 && get_byte_range (write, ref, true, &start, &size)) 309 bitmap_clear_range (live_bytes, start, size); 310} 311 312/* Clear any bytes written by STMT from the bitmap LIVE_BYTES. The base 313 address written by STMT must match the one found in REF, which must 314 have its base address previously initialized. 315 316 This routine must be conservative. If we don't know the offset or 317 actual size written, assume nothing was written. */ 318 319static void 320clear_bytes_written_by (sbitmap live_bytes, gimple *stmt, ao_ref *ref) 321{ 322 ao_ref write; 323 324 if (gcall *call = dyn_cast <gcall *> (stmt)) 325 { 326 bool interposed; 327 modref_summary *summary = get_modref_function_summary (call, &interposed); 328 329 if (summary && !interposed) 330 for (auto kill : summary->kills) 331 if (kill.get_ao_ref (as_a <gcall *> (stmt), &write)) 332 clear_live_bytes_for_ref (live_bytes, ref, &write); 333 } 334 if (!initialize_ao_ref_for_dse (stmt, &write)) 335 return; 336 337 clear_live_bytes_for_ref (live_bytes, ref, &write); 338} 339 340/* REF is a memory write. Extract relevant information from it and 341 initialize the LIVE_BYTES bitmap. If successful, return TRUE. 342 Otherwise return FALSE. */ 343 344static bool 345setup_live_bytes_from_ref (ao_ref *ref, sbitmap live_bytes) 346{ 347 HOST_WIDE_INT const_size; 348 if (valid_ao_ref_for_dse (ref) 349 && ((aligned_upper_bound (ref->offset + ref->max_size, BITS_PER_UNIT) 350 - aligned_lower_bound (ref->offset, 351 BITS_PER_UNIT)).is_constant (&const_size)) 352 && (const_size / BITS_PER_UNIT <= param_dse_max_object_size) 353 && const_size > 1) 354 { 355 bitmap_clear (live_bytes); 356 bitmap_set_range (live_bytes, 0, const_size / BITS_PER_UNIT); 357 return true; 358 } 359 return false; 360} 361 362/* Compute the number of elements that we can trim from the head and 363 tail of ORIG resulting in a bitmap that is a superset of LIVE. 364 365 Store the number of elements trimmed from the head and tail in 366 TRIM_HEAD and TRIM_TAIL. 367 368 STMT is the statement being trimmed and is used for debugging dump 369 output only. */ 370 371static void 372compute_trims (ao_ref *ref, sbitmap live, int *trim_head, int *trim_tail, 373 gimple *stmt) 374{ 375 /* We use sbitmaps biased such that ref->offset is bit zero and the bitmap 376 extends through ref->size. So we know that in the original bitmap 377 bits 0..ref->size were true. We don't actually need the bitmap, just 378 the REF to compute the trims. */ 379 380 /* Now identify how much, if any of the tail we can chop off. */ 381 HOST_WIDE_INT const_size; 382 int last_live = bitmap_last_set_bit (live); 383 if (ref->size.is_constant (&const_size)) 384 { 385 int last_orig = (const_size / BITS_PER_UNIT) - 1; 386 /* We can leave inconvenient amounts on the tail as 387 residual handling in mem* and str* functions is usually 388 reasonably efficient. */ 389 *trim_tail = last_orig - last_live; 390 391 /* But don't trim away out of bounds accesses, as this defeats 392 proper warnings. 393 394 We could have a type with no TYPE_SIZE_UNIT or we could have a VLA 395 where TYPE_SIZE_UNIT is not a constant. */ 396 if (*trim_tail 397 && TYPE_SIZE_UNIT (TREE_TYPE (ref->base)) 398 && TREE_CODE (TYPE_SIZE_UNIT (TREE_TYPE (ref->base))) == INTEGER_CST 399 && compare_tree_int (TYPE_SIZE_UNIT (TREE_TYPE (ref->base)), 400 last_orig) <= 0) 401 *trim_tail = 0; 402 } 403 else 404 *trim_tail = 0; 405 406 /* Identify how much, if any of the head we can chop off. */ 407 int first_orig = 0; 408 int first_live = bitmap_first_set_bit (live); 409 *trim_head = first_live - first_orig; 410 411 /* If REF is aligned, try to maintain this alignment if it reduces 412 the number of (power-of-two sized aligned) writes to memory. */ 413 unsigned int align_bits; 414 unsigned HOST_WIDE_INT bitpos; 415 if ((*trim_head || *trim_tail) 416 && last_live - first_live >= 2 417 && ao_ref_alignment (ref, &align_bits, &bitpos) 418 && align_bits >= 32 419 && bitpos == 0 420 && align_bits % BITS_PER_UNIT == 0) 421 { 422 unsigned int align_units = align_bits / BITS_PER_UNIT; 423 if (align_units > 16) 424 align_units = 16; 425 while ((first_live | (align_units - 1)) > (unsigned int)last_live) 426 align_units >>= 1; 427 428 if (*trim_head) 429 { 430 unsigned int pos = first_live & (align_units - 1); 431 for (unsigned int i = 1; i <= align_units; i <<= 1) 432 { 433 unsigned int mask = ~(i - 1); 434 unsigned int bytes = align_units - (pos & mask); 435 if (wi::popcount (bytes) <= 1) 436 { 437 *trim_head &= mask; 438 break; 439 } 440 } 441 } 442 443 if (*trim_tail) 444 { 445 unsigned int pos = last_live & (align_units - 1); 446 for (unsigned int i = 1; i <= align_units; i <<= 1) 447 { 448 int mask = i - 1; 449 unsigned int bytes = (pos | mask) + 1; 450 if ((last_live | mask) > (last_live + *trim_tail)) 451 break; 452 if (wi::popcount (bytes) <= 1) 453 { 454 unsigned int extra = (last_live | mask) - last_live; 455 *trim_tail -= extra; 456 break; 457 } 458 } 459 } 460 } 461 462 if ((*trim_head || *trim_tail) 463 && dump_file && (dump_flags & TDF_DETAILS)) 464 { 465 fprintf (dump_file, " Trimming statement (head = %d, tail = %d): ", 466 *trim_head, *trim_tail); 467 print_gimple_stmt (dump_file, stmt, 0, dump_flags); 468 fprintf (dump_file, "\n"); 469 } 470} 471 472/* STMT initializes an object from COMPLEX_CST where one or more of the 473 bytes written may be dead stores. REF is a representation of the 474 memory written. LIVE is the bitmap of stores that are actually live. 475 476 Attempt to rewrite STMT so that only the real or imaginary part of 477 the object is actually stored. */ 478 479static void 480maybe_trim_complex_store (ao_ref *ref, sbitmap live, gimple *stmt) 481{ 482 int trim_head, trim_tail; 483 compute_trims (ref, live, &trim_head, &trim_tail, stmt); 484 485 /* The amount of data trimmed from the head or tail must be at 486 least half the size of the object to ensure we're trimming 487 the entire real or imaginary half. By writing things this 488 way we avoid more O(n) bitmap operations. */ 489 if (known_ge (trim_tail * 2 * BITS_PER_UNIT, ref->size)) 490 { 491 /* TREE_REALPART is live */ 492 tree x = TREE_REALPART (gimple_assign_rhs1 (stmt)); 493 tree y = gimple_assign_lhs (stmt); 494 y = build1 (REALPART_EXPR, TREE_TYPE (x), y); 495 gimple_assign_set_lhs (stmt, y); 496 gimple_assign_set_rhs1 (stmt, x); 497 } 498 else if (known_ge (trim_head * 2 * BITS_PER_UNIT, ref->size)) 499 { 500 /* TREE_IMAGPART is live */ 501 tree x = TREE_IMAGPART (gimple_assign_rhs1 (stmt)); 502 tree y = gimple_assign_lhs (stmt); 503 y = build1 (IMAGPART_EXPR, TREE_TYPE (x), y); 504 gimple_assign_set_lhs (stmt, y); 505 gimple_assign_set_rhs1 (stmt, x); 506 } 507 508 /* Other cases indicate parts of both the real and imag subobjects 509 are live. We do not try to optimize those cases. */ 510} 511 512/* STMT initializes an object using a CONSTRUCTOR where one or more of the 513 bytes written are dead stores. ORIG is the bitmap of bytes stored by 514 STMT. LIVE is the bitmap of stores that are actually live. 515 516 Attempt to rewrite STMT so that only the real or imaginary part of 517 the object is actually stored. 518 519 The most common case for getting here is a CONSTRUCTOR with no elements 520 being used to zero initialize an object. We do not try to handle other 521 cases as those would force us to fully cover the object with the 522 CONSTRUCTOR node except for the components that are dead. */ 523 524static void 525maybe_trim_constructor_store (ao_ref *ref, sbitmap live, gimple *stmt) 526{ 527 tree ctor = gimple_assign_rhs1 (stmt); 528 529 /* This is the only case we currently handle. It actually seems to 530 catch most cases of actual interest. */ 531 gcc_assert (CONSTRUCTOR_NELTS (ctor) == 0); 532 533 int head_trim = 0; 534 int tail_trim = 0; 535 compute_trims (ref, live, &head_trim, &tail_trim, stmt); 536 537 /* Now we want to replace the constructor initializer 538 with memset (object + head_trim, 0, size - head_trim - tail_trim). */ 539 if (head_trim || tail_trim) 540 { 541 /* We want &lhs for the MEM_REF expression. */ 542 tree lhs_addr = build_fold_addr_expr (gimple_assign_lhs (stmt)); 543 544 if (! is_gimple_min_invariant (lhs_addr)) 545 return; 546 547 /* The number of bytes for the new constructor. */ 548 poly_int64 ref_bytes = exact_div (ref->size, BITS_PER_UNIT); 549 poly_int64 count = ref_bytes - head_trim - tail_trim; 550 551 /* And the new type for the CONSTRUCTOR. Essentially it's just 552 a char array large enough to cover the non-trimmed parts of 553 the original CONSTRUCTOR. Note we want explicit bounds here 554 so that we know how many bytes to clear when expanding the 555 CONSTRUCTOR. */ 556 tree type = build_array_type_nelts (char_type_node, count); 557 558 /* Build a suitable alias type rather than using alias set zero 559 to avoid pessimizing. */ 560 tree alias_type = reference_alias_ptr_type (gimple_assign_lhs (stmt)); 561 562 /* Build a MEM_REF representing the whole accessed area, starting 563 at the first byte not trimmed. */ 564 tree exp = fold_build2 (MEM_REF, type, lhs_addr, 565 build_int_cst (alias_type, head_trim)); 566 567 /* Now update STMT with a new RHS and LHS. */ 568 gimple_assign_set_lhs (stmt, exp); 569 gimple_assign_set_rhs1 (stmt, build_constructor (type, NULL)); 570 } 571} 572 573/* STMT is a memcpy, memmove or memset. Decrement the number of bytes 574 copied/set by DECREMENT. */ 575static void 576decrement_count (gimple *stmt, int decrement) 577{ 578 tree *countp = gimple_call_arg_ptr (stmt, 2); 579 gcc_assert (TREE_CODE (*countp) == INTEGER_CST); 580 *countp = wide_int_to_tree (TREE_TYPE (*countp), (TREE_INT_CST_LOW (*countp) 581 - decrement)); 582} 583 584static void 585increment_start_addr (gimple *stmt, tree *where, int increment) 586{ 587 if (tree lhs = gimple_call_lhs (stmt)) 588 if (where == gimple_call_arg_ptr (stmt, 0)) 589 { 590 gassign *newop = gimple_build_assign (lhs, unshare_expr (*where)); 591 gimple_stmt_iterator gsi = gsi_for_stmt (stmt); 592 gsi_insert_after (&gsi, newop, GSI_SAME_STMT); 593 gimple_call_set_lhs (stmt, NULL_TREE); 594 update_stmt (stmt); 595 } 596 597 if (TREE_CODE (*where) == SSA_NAME) 598 { 599 tree tem = make_ssa_name (TREE_TYPE (*where)); 600 gassign *newop 601 = gimple_build_assign (tem, POINTER_PLUS_EXPR, *where, 602 build_int_cst (sizetype, increment)); 603 gimple_stmt_iterator gsi = gsi_for_stmt (stmt); 604 gsi_insert_before (&gsi, newop, GSI_SAME_STMT); 605 *where = tem; 606 update_stmt (stmt); 607 return; 608 } 609 610 *where = build_fold_addr_expr (fold_build2 (MEM_REF, char_type_node, 611 *where, 612 build_int_cst (ptr_type_node, 613 increment))); 614} 615 616/* STMT is builtin call that writes bytes in bitmap ORIG, some bytes are dead 617 (ORIG & ~NEW) and need not be stored. Try to rewrite STMT to reduce 618 the amount of data it actually writes. 619 620 Right now we only support trimming from the head or the tail of the 621 memory region. In theory we could split the mem* call, but it's 622 likely of marginal value. */ 623 624static void 625maybe_trim_memstar_call (ao_ref *ref, sbitmap live, gimple *stmt) 626{ 627 int head_trim, tail_trim; 628 switch (DECL_FUNCTION_CODE (gimple_call_fndecl (stmt))) 629 { 630 case BUILT_IN_STRNCPY: 631 case BUILT_IN_STRNCPY_CHK: 632 compute_trims (ref, live, &head_trim, &tail_trim, stmt); 633 if (head_trim) 634 { 635 /* Head trimming of strncpy is only possible if we can 636 prove all bytes we would trim are non-zero (or we could 637 turn the strncpy into memset if there must be zero 638 among the head trimmed bytes). If we don't know anything 639 about those bytes, the presence or absence of '\0' bytes 640 in there will affect whether it acts for the non-trimmed 641 bytes as memset or memcpy/strncpy. */ 642 c_strlen_data lendata = { }; 643 int orig_head_trim = head_trim; 644 tree srcstr = gimple_call_arg (stmt, 1); 645 if (!get_range_strlen (srcstr, &lendata, /*eltsize=*/1) 646 || !tree_fits_uhwi_p (lendata.minlen)) 647 head_trim = 0; 648 else if (tree_to_uhwi (lendata.minlen) < (unsigned) head_trim) 649 { 650 head_trim = tree_to_uhwi (lendata.minlen); 651 if ((orig_head_trim & (UNITS_PER_WORD - 1)) == 0) 652 head_trim &= ~(UNITS_PER_WORD - 1); 653 } 654 if (orig_head_trim != head_trim 655 && dump_file 656 && (dump_flags & TDF_DETAILS)) 657 fprintf (dump_file, 658 " Adjusting strncpy trimming to (head = %d," 659 " tail = %d)\n", head_trim, tail_trim); 660 } 661 goto do_memcpy; 662 663 case BUILT_IN_MEMCPY: 664 case BUILT_IN_MEMMOVE: 665 case BUILT_IN_MEMCPY_CHK: 666 case BUILT_IN_MEMMOVE_CHK: 667 compute_trims (ref, live, &head_trim, &tail_trim, stmt); 668 669 do_memcpy: 670 /* Tail trimming is easy, we can just reduce the count. */ 671 if (tail_trim) 672 decrement_count (stmt, tail_trim); 673 674 /* Head trimming requires adjusting all the arguments. */ 675 if (head_trim) 676 { 677 /* For __*_chk need to adjust also the last argument. */ 678 if (gimple_call_num_args (stmt) == 4) 679 { 680 tree size = gimple_call_arg (stmt, 3); 681 if (!tree_fits_uhwi_p (size)) 682 break; 683 if (!integer_all_onesp (size)) 684 { 685 unsigned HOST_WIDE_INT sz = tree_to_uhwi (size); 686 if (sz < (unsigned) head_trim) 687 break; 688 tree arg = wide_int_to_tree (TREE_TYPE (size), 689 sz - head_trim); 690 gimple_call_set_arg (stmt, 3, arg); 691 } 692 } 693 tree *dst = gimple_call_arg_ptr (stmt, 0); 694 increment_start_addr (stmt, dst, head_trim); 695 tree *src = gimple_call_arg_ptr (stmt, 1); 696 increment_start_addr (stmt, src, head_trim); 697 decrement_count (stmt, head_trim); 698 } 699 break; 700 701 case BUILT_IN_MEMSET: 702 case BUILT_IN_MEMSET_CHK: 703 compute_trims (ref, live, &head_trim, &tail_trim, stmt); 704 705 /* Tail trimming is easy, we can just reduce the count. */ 706 if (tail_trim) 707 decrement_count (stmt, tail_trim); 708 709 /* Head trimming requires adjusting all the arguments. */ 710 if (head_trim) 711 { 712 /* For __*_chk need to adjust also the last argument. */ 713 if (gimple_call_num_args (stmt) == 4) 714 { 715 tree size = gimple_call_arg (stmt, 3); 716 if (!tree_fits_uhwi_p (size)) 717 break; 718 if (!integer_all_onesp (size)) 719 { 720 unsigned HOST_WIDE_INT sz = tree_to_uhwi (size); 721 if (sz < (unsigned) head_trim) 722 break; 723 tree arg = wide_int_to_tree (TREE_TYPE (size), 724 sz - head_trim); 725 gimple_call_set_arg (stmt, 3, arg); 726 } 727 } 728 tree *dst = gimple_call_arg_ptr (stmt, 0); 729 increment_start_addr (stmt, dst, head_trim); 730 decrement_count (stmt, head_trim); 731 } 732 break; 733 734 default: 735 break; 736 } 737} 738 739/* STMT is a memory write where one or more bytes written are dead 740 stores. ORIG is the bitmap of bytes stored by STMT. LIVE is the 741 bitmap of stores that are actually live. 742 743 Attempt to rewrite STMT so that it writes fewer memory locations. Right 744 now we only support trimming at the start or end of the memory region. 745 It's not clear how much there is to be gained by trimming from the middle 746 of the region. */ 747 748static void 749maybe_trim_partially_dead_store (ao_ref *ref, sbitmap live, gimple *stmt) 750{ 751 if (is_gimple_assign (stmt) 752 && TREE_CODE (gimple_assign_lhs (stmt)) != TARGET_MEM_REF) 753 { 754 switch (gimple_assign_rhs_code (stmt)) 755 { 756 case CONSTRUCTOR: 757 maybe_trim_constructor_store (ref, live, stmt); 758 break; 759 case COMPLEX_CST: 760 maybe_trim_complex_store (ref, live, stmt); 761 break; 762 default: 763 break; 764 } 765 } 766} 767 768/* Return TRUE if USE_REF reads bytes from LIVE where live is 769 derived from REF, a write reference. 770 771 While this routine may modify USE_REF, it's passed by value, not 772 location. So callers do not see those modifications. */ 773 774static bool 775live_bytes_read (ao_ref *use_ref, ao_ref *ref, sbitmap live) 776{ 777 /* We have already verified that USE_REF and REF hit the same object. 778 Now verify that there's actually an overlap between USE_REF and REF. */ 779 HOST_WIDE_INT start, size; 780 if (get_byte_range (use_ref, ref, false, &start, &size)) 781 { 782 /* If USE_REF covers all of REF, then it will hit one or more 783 live bytes. This avoids useless iteration over the bitmap 784 below. */ 785 if (start == 0 && known_eq (size * 8, ref->size)) 786 return true; 787 788 /* Now check if any of the remaining bits in use_ref are set in LIVE. */ 789 return bitmap_bit_in_range_p (live, start, (start + size - 1)); 790 } 791 return true; 792} 793 794/* Callback for dse_classify_store calling for_each_index. Verify that 795 indices are invariant in the loop with backedge PHI in basic-block DATA. */ 796 797static bool 798check_name (tree, tree *idx, void *data) 799{ 800 basic_block phi_bb = (basic_block) data; 801 if (TREE_CODE (*idx) == SSA_NAME 802 && !SSA_NAME_IS_DEFAULT_DEF (*idx) 803 && dominated_by_p (CDI_DOMINATORS, gimple_bb (SSA_NAME_DEF_STMT (*idx)), 804 phi_bb)) 805 return false; 806 return true; 807} 808 809/* STMT stores the value 0 into one or more memory locations 810 (via memset, empty constructor, calloc call, etc). 811 812 See if there is a subsequent store of the value 0 to one 813 or more of the same memory location(s). If so, the subsequent 814 store is redundant and can be removed. 815 816 The subsequent stores could be via memset, empty constructors, 817 simple MEM stores, etc. */ 818 819static void 820dse_optimize_redundant_stores (gimple *stmt) 821{ 822 int cnt = 0; 823 824 /* TBAA state of STMT, if it is a call it is effectively alias-set zero. */ 825 alias_set_type earlier_set = 0; 826 alias_set_type earlier_base_set = 0; 827 if (is_gimple_assign (stmt)) 828 { 829 ao_ref lhs_ref; 830 ao_ref_init (&lhs_ref, gimple_assign_lhs (stmt)); 831 earlier_set = ao_ref_alias_set (&lhs_ref); 832 earlier_base_set = ao_ref_base_alias_set (&lhs_ref); 833 } 834 835 /* We could do something fairly complex and look through PHIs 836 like DSE_CLASSIFY_STORE, but it doesn't seem to be worth 837 the effort. 838 839 Look at all the immediate uses of the VDEF (which are obviously 840 dominated by STMT). See if one or more stores 0 into the same 841 memory locations a STMT, if so remove the immediate use statements. */ 842 tree defvar = gimple_vdef (stmt); 843 imm_use_iterator ui; 844 gimple *use_stmt; 845 FOR_EACH_IMM_USE_STMT (use_stmt, ui, defvar) 846 { 847 /* Limit stmt walking. */ 848 if (++cnt > param_dse_max_alias_queries_per_store) 849 break; 850 851 /* If USE_STMT stores 0 into one or more of the same locations 852 as STMT and STMT would kill USE_STMT, then we can just remove 853 USE_STMT. */ 854 tree fndecl; 855 if ((is_gimple_assign (use_stmt) 856 && gimple_vdef (use_stmt) 857 && (gimple_assign_single_p (use_stmt) 858 && initializer_zerop (gimple_assign_rhs1 (use_stmt)))) 859 || (gimple_call_builtin_p (use_stmt, BUILT_IN_NORMAL) 860 && (fndecl = gimple_call_fndecl (use_stmt)) != NULL 861 && (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMSET 862 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMSET_CHK) 863 && integer_zerop (gimple_call_arg (use_stmt, 1)))) 864 { 865 ao_ref write; 866 867 if (!initialize_ao_ref_for_dse (use_stmt, &write)) 868 break; 869 870 if (valid_ao_ref_for_dse (&write) 871 && stmt_kills_ref_p (stmt, &write)) 872 { 873 gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt); 874 if (is_gimple_assign (use_stmt)) 875 { 876 ao_ref lhs_ref; 877 ao_ref_init (&lhs_ref, gimple_assign_lhs (use_stmt)); 878 if ((earlier_set == ao_ref_alias_set (&lhs_ref) 879 || alias_set_subset_of (ao_ref_alias_set (&lhs_ref), 880 earlier_set)) 881 && (earlier_base_set == ao_ref_base_alias_set (&lhs_ref) 882 || alias_set_subset_of 883 (ao_ref_base_alias_set (&lhs_ref), 884 earlier_base_set))) 885 delete_dead_or_redundant_assignment (&gsi, "redundant", 886 need_eh_cleanup, 887 need_ab_cleanup); 888 } 889 else if (is_gimple_call (use_stmt)) 890 { 891 if ((earlier_set == 0 892 || alias_set_subset_of (0, earlier_set)) 893 && (earlier_base_set == 0 894 || alias_set_subset_of (0, earlier_base_set))) 895 delete_dead_or_redundant_call (&gsi, "redundant"); 896 } 897 else 898 gcc_unreachable (); 899 } 900 } 901 } 902} 903 904/* A helper of dse_optimize_stmt. 905 Given a GIMPLE_ASSIGN in STMT that writes to REF, classify it 906 according to downstream uses and defs. Sets *BY_CLOBBER_P to true 907 if only clobber statements influenced the classification result. 908 Returns the classification. */ 909 910dse_store_status 911dse_classify_store (ao_ref *ref, gimple *stmt, 912 bool byte_tracking_enabled, sbitmap live_bytes, 913 bool *by_clobber_p, tree stop_at_vuse) 914{ 915 gimple *temp; 916 int cnt = 0; 917 auto_bitmap visited; 918 919 if (by_clobber_p) 920 *by_clobber_p = true; 921 922 /* Find the first dominated statement that clobbers (part of) the 923 memory stmt stores to with no intermediate statement that may use 924 part of the memory stmt stores. That is, find a store that may 925 prove stmt to be a dead store. */ 926 temp = stmt; 927 do 928 { 929 gimple *use_stmt; 930 imm_use_iterator ui; 931 bool fail = false; 932 tree defvar; 933 934 if (gimple_code (temp) == GIMPLE_PHI) 935 { 936 defvar = PHI_RESULT (temp); 937 bitmap_set_bit (visited, SSA_NAME_VERSION (defvar)); 938 } 939 else 940 defvar = gimple_vdef (temp); 941 942 /* If we're instructed to stop walking at region boundary, do so. */ 943 if (defvar == stop_at_vuse) 944 return DSE_STORE_LIVE; 945 946 auto_vec<gimple *, 10> defs; 947 gimple *first_phi_def = NULL; 948 gimple *last_phi_def = NULL; 949 FOR_EACH_IMM_USE_STMT (use_stmt, ui, defvar) 950 { 951 /* Limit stmt walking. */ 952 if (++cnt > param_dse_max_alias_queries_per_store) 953 { 954 fail = true; 955 break; 956 } 957 958 /* In simple cases we can look through PHI nodes, but we 959 have to be careful with loops and with memory references 960 containing operands that are also operands of PHI nodes. 961 See gcc.c-torture/execute/20051110-*.c. */ 962 if (gimple_code (use_stmt) == GIMPLE_PHI) 963 { 964 /* If we already visited this PHI ignore it for further 965 processing. */ 966 if (!bitmap_bit_p (visited, 967 SSA_NAME_VERSION (PHI_RESULT (use_stmt)))) 968 { 969 /* If we visit this PHI by following a backedge then we have 970 to make sure ref->ref only refers to SSA names that are 971 invariant with respect to the loop represented by this 972 PHI node. */ 973 if (dominated_by_p (CDI_DOMINATORS, gimple_bb (stmt), 974 gimple_bb (use_stmt)) 975 && !for_each_index (ref->ref ? &ref->ref : &ref->base, 976 check_name, gimple_bb (use_stmt))) 977 return DSE_STORE_LIVE; 978 defs.safe_push (use_stmt); 979 if (!first_phi_def) 980 first_phi_def = use_stmt; 981 last_phi_def = use_stmt; 982 } 983 } 984 /* If the statement is a use the store is not dead. */ 985 else if (ref_maybe_used_by_stmt_p (use_stmt, ref)) 986 { 987 /* Handle common cases where we can easily build an ao_ref 988 structure for USE_STMT and in doing so we find that the 989 references hit non-live bytes and thus can be ignored. 990 991 TODO: We can also use modref summary to handle calls. */ 992 if (byte_tracking_enabled 993 && is_gimple_assign (use_stmt)) 994 { 995 ao_ref use_ref; 996 ao_ref_init (&use_ref, gimple_assign_rhs1 (use_stmt)); 997 if (valid_ao_ref_for_dse (&use_ref) 998 && operand_equal_p (use_ref.base, ref->base, 999 OEP_ADDRESS_OF) 1000 && !live_bytes_read (&use_ref, ref, live_bytes)) 1001 { 1002 /* If this is a store, remember it as we possibly 1003 need to walk the defs uses. */ 1004 if (gimple_vdef (use_stmt)) 1005 defs.safe_push (use_stmt); 1006 continue; 1007 } 1008 } 1009 1010 fail = true; 1011 break; 1012 } 1013 /* We have visited ourselves already so ignore STMT for the 1014 purpose of chaining. */ 1015 else if (use_stmt == stmt) 1016 ; 1017 /* If this is a store, remember it as we possibly need to walk the 1018 defs uses. */ 1019 else if (gimple_vdef (use_stmt)) 1020 defs.safe_push (use_stmt); 1021 } 1022 1023 if (fail) 1024 { 1025 /* STMT might be partially dead and we may be able to reduce 1026 how many memory locations it stores into. */ 1027 if (byte_tracking_enabled && !gimple_clobber_p (stmt)) 1028 return DSE_STORE_MAYBE_PARTIAL_DEAD; 1029 return DSE_STORE_LIVE; 1030 } 1031 1032 /* If we didn't find any definition this means the store is dead 1033 if it isn't a store to global reachable memory. In this case 1034 just pretend the stmt makes itself dead. Otherwise fail. */ 1035 if (defs.is_empty ()) 1036 { 1037 if (ref_may_alias_global_p (ref, false)) 1038 return DSE_STORE_LIVE; 1039 1040 if (by_clobber_p) 1041 *by_clobber_p = false; 1042 return DSE_STORE_DEAD; 1043 } 1044 1045 /* Process defs and remove those we need not process further. */ 1046 for (unsigned i = 0; i < defs.length ();) 1047 { 1048 gimple *def = defs[i]; 1049 gimple *use_stmt; 1050 use_operand_p use_p; 1051 tree vdef = (gimple_code (def) == GIMPLE_PHI 1052 ? gimple_phi_result (def) : gimple_vdef (def)); 1053 /* If the path to check starts with a kill we do not need to 1054 process it further. 1055 ??? With byte tracking we need only kill the bytes currently 1056 live. */ 1057 if (stmt_kills_ref_p (def, ref)) 1058 { 1059 if (by_clobber_p && !gimple_clobber_p (def)) 1060 *by_clobber_p = false; 1061 defs.unordered_remove (i); 1062 } 1063 /* If the path ends here we do not need to process it further. 1064 This for example happens with calls to noreturn functions. */ 1065 else if (has_zero_uses (vdef)) 1066 { 1067 /* But if the store is to global memory it is definitely 1068 not dead. */ 1069 if (ref_may_alias_global_p (ref, false)) 1070 return DSE_STORE_LIVE; 1071 defs.unordered_remove (i); 1072 } 1073 /* In addition to kills we can remove defs whose only use 1074 is another def in defs. That can only ever be PHIs of which 1075 we track two for simplicity reasons, the first and last in 1076 {first,last}_phi_def (we fail for multiple PHIs anyways). 1077 We can also ignore defs that feed only into 1078 already visited PHIs. */ 1079 else if (single_imm_use (vdef, &use_p, &use_stmt) 1080 && (use_stmt == first_phi_def 1081 || use_stmt == last_phi_def 1082 || (gimple_code (use_stmt) == GIMPLE_PHI 1083 && bitmap_bit_p (visited, 1084 SSA_NAME_VERSION 1085 (PHI_RESULT (use_stmt)))))) 1086 defs.unordered_remove (i); 1087 else 1088 ++i; 1089 } 1090 1091 /* If all defs kill the ref we are done. */ 1092 if (defs.is_empty ()) 1093 return DSE_STORE_DEAD; 1094 /* If more than one def survives fail. */ 1095 if (defs.length () > 1) 1096 { 1097 /* STMT might be partially dead and we may be able to reduce 1098 how many memory locations it stores into. */ 1099 if (byte_tracking_enabled && !gimple_clobber_p (stmt)) 1100 return DSE_STORE_MAYBE_PARTIAL_DEAD; 1101 return DSE_STORE_LIVE; 1102 } 1103 temp = defs[0]; 1104 1105 /* Track partial kills. */ 1106 if (byte_tracking_enabled) 1107 { 1108 clear_bytes_written_by (live_bytes, temp, ref); 1109 if (bitmap_empty_p (live_bytes)) 1110 { 1111 if (by_clobber_p && !gimple_clobber_p (temp)) 1112 *by_clobber_p = false; 1113 return DSE_STORE_DEAD; 1114 } 1115 } 1116 } 1117 /* Continue walking until there are no more live bytes. */ 1118 while (1); 1119} 1120 1121 1122/* Delete a dead call at GSI, which is mem* call of some kind. */ 1123static void 1124delete_dead_or_redundant_call (gimple_stmt_iterator *gsi, const char *type) 1125{ 1126 gimple *stmt = gsi_stmt (*gsi); 1127 if (dump_file && (dump_flags & TDF_DETAILS)) 1128 { 1129 fprintf (dump_file, " Deleted %s call: ", type); 1130 print_gimple_stmt (dump_file, stmt, 0, dump_flags); 1131 fprintf (dump_file, "\n"); 1132 } 1133 1134 basic_block bb = gimple_bb (stmt); 1135 tree lhs = gimple_call_lhs (stmt); 1136 if (lhs) 1137 { 1138 tree ptr = gimple_call_arg (stmt, 0); 1139 gimple *new_stmt = gimple_build_assign (lhs, ptr); 1140 unlink_stmt_vdef (stmt); 1141 if (gsi_replace (gsi, new_stmt, true)) 1142 bitmap_set_bit (need_eh_cleanup, bb->index); 1143 } 1144 else 1145 { 1146 /* Then we need to fix the operand of the consuming stmt. */ 1147 unlink_stmt_vdef (stmt); 1148 1149 /* Remove the dead store. */ 1150 if (gsi_remove (gsi, true)) 1151 bitmap_set_bit (need_eh_cleanup, bb->index); 1152 release_defs (stmt); 1153 } 1154} 1155 1156/* Delete a dead store at GSI, which is a gimple assignment. */ 1157 1158void 1159delete_dead_or_redundant_assignment (gimple_stmt_iterator *gsi, 1160 const char *type, 1161 bitmap need_eh_cleanup, 1162 bitmap need_ab_cleanup) 1163{ 1164 gimple *stmt = gsi_stmt (*gsi); 1165 if (dump_file && (dump_flags & TDF_DETAILS)) 1166 { 1167 fprintf (dump_file, " Deleted %s store: ", type); 1168 print_gimple_stmt (dump_file, stmt, 0, dump_flags); 1169 fprintf (dump_file, "\n"); 1170 } 1171 1172 /* Then we need to fix the operand of the consuming stmt. */ 1173 unlink_stmt_vdef (stmt); 1174 1175 /* Remove the dead store. */ 1176 basic_block bb = gimple_bb (stmt); 1177 if (need_ab_cleanup && stmt_can_make_abnormal_goto (stmt)) 1178 bitmap_set_bit (need_ab_cleanup, bb->index); 1179 if (gsi_remove (gsi, true) && need_eh_cleanup) 1180 bitmap_set_bit (need_eh_cleanup, bb->index); 1181 1182 /* And release any SSA_NAMEs set in this statement back to the 1183 SSA_NAME manager. */ 1184 release_defs (stmt); 1185} 1186 1187/* Try to prove, using modref summary, that all memory written to by a call is 1188 dead and remove it. Assume that if return value is written to memory 1189 it is already proved to be dead. */ 1190 1191static bool 1192dse_optimize_call (gimple_stmt_iterator *gsi, sbitmap live_bytes) 1193{ 1194 gcall *stmt = dyn_cast <gcall *> (gsi_stmt (*gsi)); 1195 1196 if (!stmt) 1197 return false; 1198 1199 tree callee = gimple_call_fndecl (stmt); 1200 1201 if (!callee) 1202 return false; 1203 1204 /* Pure/const functions are optimized by normal DCE 1205 or handled as store above. */ 1206 int flags = gimple_call_flags (stmt); 1207 if ((flags & (ECF_PURE|ECF_CONST|ECF_NOVOPS)) 1208 && !(flags & (ECF_LOOPING_CONST_OR_PURE))) 1209 return false; 1210 1211 cgraph_node *node = cgraph_node::get (callee); 1212 if (!node) 1213 return false; 1214 1215 if (stmt_could_throw_p (cfun, stmt) 1216 && !cfun->can_delete_dead_exceptions) 1217 return false; 1218 1219 /* If return value is used the call is not dead. */ 1220 tree lhs = gimple_call_lhs (stmt); 1221 if (lhs && TREE_CODE (lhs) == SSA_NAME) 1222 { 1223 imm_use_iterator ui; 1224 gimple *use_stmt; 1225 FOR_EACH_IMM_USE_STMT (use_stmt, ui, lhs) 1226 if (!is_gimple_debug (use_stmt)) 1227 return false; 1228 } 1229 1230 /* Verify that there are no side-effects except for return value 1231 and memory writes tracked by modref. */ 1232 modref_summary *summary = get_modref_function_summary (node); 1233 if (!summary || !summary->try_dse) 1234 return false; 1235 1236 bool by_clobber_p = false; 1237 1238 /* Walk all memory writes and verify that they are dead. */ 1239 for (auto base_node : summary->stores->bases) 1240 for (auto ref_node : base_node->refs) 1241 for (auto access_node : ref_node->accesses) 1242 { 1243 tree arg = access_node.get_call_arg (stmt); 1244 1245 if (!arg || !POINTER_TYPE_P (TREE_TYPE (arg))) 1246 return false; 1247 1248 if (integer_zerop (arg) 1249 && !targetm.addr_space.zero_address_valid 1250 (TYPE_ADDR_SPACE (TREE_TYPE (arg)))) 1251 continue; 1252 1253 ao_ref ref; 1254 1255 if (!access_node.get_ao_ref (stmt, &ref)) 1256 return false; 1257 ref.ref_alias_set = ref_node->ref; 1258 ref.base_alias_set = base_node->base; 1259 1260 bool byte_tracking_enabled 1261 = setup_live_bytes_from_ref (&ref, live_bytes); 1262 enum dse_store_status store_status; 1263 1264 store_status = dse_classify_store (&ref, stmt, 1265 byte_tracking_enabled, 1266 live_bytes, &by_clobber_p); 1267 if (store_status != DSE_STORE_DEAD) 1268 return false; 1269 } 1270 delete_dead_or_redundant_assignment (gsi, "dead", need_eh_cleanup, 1271 need_ab_cleanup); 1272 return true; 1273} 1274 1275/* Attempt to eliminate dead stores in the statement referenced by BSI. 1276 1277 A dead store is a store into a memory location which will later be 1278 overwritten by another store without any intervening loads. In this 1279 case the earlier store can be deleted. 1280 1281 In our SSA + virtual operand world we use immediate uses of virtual 1282 operands to detect dead stores. If a store's virtual definition 1283 is used precisely once by a later store to the same location which 1284 post dominates the first store, then the first store is dead. */ 1285 1286static void 1287dse_optimize_stmt (function *fun, gimple_stmt_iterator *gsi, sbitmap live_bytes) 1288{ 1289 gimple *stmt = gsi_stmt (*gsi); 1290 1291 /* Don't return early on *this_2(D) ={v} {CLOBBER}. */ 1292 if (gimple_has_volatile_ops (stmt) 1293 && (!gimple_clobber_p (stmt) 1294 || TREE_CODE (gimple_assign_lhs (stmt)) != MEM_REF)) 1295 return; 1296 1297 ao_ref ref; 1298 /* If this is not a store we can still remove dead call using 1299 modref summary. Note we specifically allow ref to be initialized 1300 to a conservative may-def since we are looking for followup stores 1301 to kill all of it. */ 1302 if (!initialize_ao_ref_for_dse (stmt, &ref, true)) 1303 { 1304 dse_optimize_call (gsi, live_bytes); 1305 return; 1306 } 1307 1308 /* We know we have virtual definitions. We can handle assignments and 1309 some builtin calls. */ 1310 if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL)) 1311 { 1312 tree fndecl = gimple_call_fndecl (stmt); 1313 switch (DECL_FUNCTION_CODE (fndecl)) 1314 { 1315 case BUILT_IN_MEMCPY: 1316 case BUILT_IN_MEMMOVE: 1317 case BUILT_IN_STRNCPY: 1318 case BUILT_IN_MEMSET: 1319 case BUILT_IN_MEMCPY_CHK: 1320 case BUILT_IN_MEMMOVE_CHK: 1321 case BUILT_IN_STRNCPY_CHK: 1322 case BUILT_IN_MEMSET_CHK: 1323 { 1324 /* Occasionally calls with an explicit length of zero 1325 show up in the IL. It's pointless to do analysis 1326 on them, they're trivially dead. */ 1327 tree size = gimple_call_arg (stmt, 2); 1328 if (integer_zerop (size)) 1329 { 1330 delete_dead_or_redundant_call (gsi, "dead"); 1331 return; 1332 } 1333 1334 /* If this is a memset call that initializes an object 1335 to zero, it may be redundant with an earlier memset 1336 or empty CONSTRUCTOR of a larger object. */ 1337 if ((DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMSET 1338 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMSET_CHK) 1339 && integer_zerop (gimple_call_arg (stmt, 1))) 1340 dse_optimize_redundant_stores (stmt); 1341 1342 enum dse_store_status store_status; 1343 bool byte_tracking_enabled 1344 = setup_live_bytes_from_ref (&ref, live_bytes); 1345 store_status = dse_classify_store (&ref, stmt, 1346 byte_tracking_enabled, 1347 live_bytes); 1348 if (store_status == DSE_STORE_LIVE) 1349 return; 1350 1351 if (store_status == DSE_STORE_MAYBE_PARTIAL_DEAD) 1352 { 1353 maybe_trim_memstar_call (&ref, live_bytes, stmt); 1354 return; 1355 } 1356 1357 if (store_status == DSE_STORE_DEAD) 1358 delete_dead_or_redundant_call (gsi, "dead"); 1359 return; 1360 } 1361 1362 case BUILT_IN_CALLOC: 1363 /* We already know the arguments are integer constants. */ 1364 dse_optimize_redundant_stores (stmt); 1365 return; 1366 1367 default: 1368 return; 1369 } 1370 } 1371 1372 bool by_clobber_p = false; 1373 1374 /* Check if this statement stores zero to a memory location, 1375 and if there is a subsequent store of zero to the same 1376 memory location. If so, remove the subsequent store. */ 1377 if (gimple_assign_single_p (stmt) 1378 && initializer_zerop (gimple_assign_rhs1 (stmt))) 1379 dse_optimize_redundant_stores (stmt); 1380 1381 /* Self-assignments are zombies. */ 1382 if (is_gimple_assign (stmt) 1383 && operand_equal_p (gimple_assign_rhs1 (stmt), 1384 gimple_assign_lhs (stmt), 0)) 1385 ; 1386 else 1387 { 1388 bool byte_tracking_enabled 1389 = setup_live_bytes_from_ref (&ref, live_bytes); 1390 enum dse_store_status store_status; 1391 store_status = dse_classify_store (&ref, stmt, 1392 byte_tracking_enabled, 1393 live_bytes, &by_clobber_p); 1394 if (store_status == DSE_STORE_LIVE) 1395 return; 1396 1397 if (store_status == DSE_STORE_MAYBE_PARTIAL_DEAD) 1398 { 1399 maybe_trim_partially_dead_store (&ref, live_bytes, stmt); 1400 return; 1401 } 1402 } 1403 1404 /* Now we know that use_stmt kills the LHS of stmt. */ 1405 1406 /* But only remove *this_2(D) ={v} {CLOBBER} if killed by 1407 another clobber stmt. */ 1408 if (gimple_clobber_p (stmt) 1409 && !by_clobber_p) 1410 return; 1411 1412 if (is_gimple_call (stmt) 1413 && (gimple_has_side_effects (stmt) 1414 || (stmt_could_throw_p (fun, stmt) 1415 && !fun->can_delete_dead_exceptions))) 1416 { 1417 /* See if we can remove complete call. */ 1418 if (dse_optimize_call (gsi, live_bytes)) 1419 return; 1420 /* Make sure we do not remove a return slot we cannot reconstruct 1421 later. */ 1422 if (gimple_call_return_slot_opt_p (as_a <gcall *>(stmt)) 1423 && (TREE_ADDRESSABLE (TREE_TYPE (gimple_call_fntype (stmt))) 1424 || !poly_int_tree_p 1425 (TYPE_SIZE (TREE_TYPE (gimple_call_fntype (stmt)))))) 1426 return; 1427 if (dump_file && (dump_flags & TDF_DETAILS)) 1428 { 1429 fprintf (dump_file, " Deleted dead store in call LHS: "); 1430 print_gimple_stmt (dump_file, stmt, 0, dump_flags); 1431 fprintf (dump_file, "\n"); 1432 } 1433 gimple_call_set_lhs (stmt, NULL_TREE); 1434 update_stmt (stmt); 1435 } 1436 else 1437 delete_dead_or_redundant_assignment (gsi, "dead", need_eh_cleanup, 1438 need_ab_cleanup); 1439} 1440 1441namespace { 1442 1443const pass_data pass_data_dse = 1444{ 1445 GIMPLE_PASS, /* type */ 1446 "dse", /* name */ 1447 OPTGROUP_NONE, /* optinfo_flags */ 1448 TV_TREE_DSE, /* tv_id */ 1449 ( PROP_cfg | PROP_ssa ), /* properties_required */ 1450 0, /* properties_provided */ 1451 0, /* properties_destroyed */ 1452 0, /* todo_flags_start */ 1453 0, /* todo_flags_finish */ 1454}; 1455 1456class pass_dse : public gimple_opt_pass 1457{ 1458public: 1459 pass_dse (gcc::context *ctxt) 1460 : gimple_opt_pass (pass_data_dse, ctxt) 1461 {} 1462 1463 /* opt_pass methods: */ 1464 opt_pass * clone () { return new pass_dse (m_ctxt); } 1465 virtual bool gate (function *) { return flag_tree_dse != 0; } 1466 virtual unsigned int execute (function *); 1467 1468}; // class pass_dse 1469 1470unsigned int 1471pass_dse::execute (function *fun) 1472{ 1473 unsigned todo = 0; 1474 bool released_def = false; 1475 1476 need_eh_cleanup = BITMAP_ALLOC (NULL); 1477 need_ab_cleanup = BITMAP_ALLOC (NULL); 1478 auto_sbitmap live_bytes (param_dse_max_object_size); 1479 1480 renumber_gimple_stmt_uids (fun); 1481 1482 calculate_dominance_info (CDI_DOMINATORS); 1483 1484 /* Dead store elimination is fundamentally a reverse program order walk. */ 1485 int *rpo = XNEWVEC (int, n_basic_blocks_for_fn (fun) - NUM_FIXED_BLOCKS); 1486 int n = pre_and_rev_post_order_compute_fn (fun, NULL, rpo, false); 1487 for (int i = n; i != 0; --i) 1488 { 1489 basic_block bb = BASIC_BLOCK_FOR_FN (fun, rpo[i-1]); 1490 gimple_stmt_iterator gsi; 1491 1492 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi);) 1493 { 1494 gimple *stmt = gsi_stmt (gsi); 1495 1496 if (gimple_vdef (stmt)) 1497 dse_optimize_stmt (fun, &gsi, live_bytes); 1498 else if (def_operand_p 1499 def_p = single_ssa_def_operand (stmt, SSA_OP_DEF)) 1500 { 1501 /* When we remove dead stores make sure to also delete trivially 1502 dead SSA defs. */ 1503 if (has_zero_uses (DEF_FROM_PTR (def_p)) 1504 && !gimple_has_side_effects (stmt) 1505 && !is_ctrl_altering_stmt (stmt) 1506 && (!stmt_could_throw_p (fun, stmt) 1507 || fun->can_delete_dead_exceptions)) 1508 { 1509 if (dump_file && (dump_flags & TDF_DETAILS)) 1510 { 1511 fprintf (dump_file, " Deleted trivially dead stmt: "); 1512 print_gimple_stmt (dump_file, stmt, 0, dump_flags); 1513 fprintf (dump_file, "\n"); 1514 } 1515 if (gsi_remove (&gsi, true) && need_eh_cleanup) 1516 bitmap_set_bit (need_eh_cleanup, bb->index); 1517 release_defs (stmt); 1518 released_def = true; 1519 } 1520 } 1521 if (gsi_end_p (gsi)) 1522 gsi = gsi_last_bb (bb); 1523 else 1524 gsi_prev (&gsi); 1525 } 1526 bool removed_phi = false; 1527 for (gphi_iterator si = gsi_start_phis (bb); !gsi_end_p (si);) 1528 { 1529 gphi *phi = si.phi (); 1530 if (has_zero_uses (gimple_phi_result (phi))) 1531 { 1532 if (dump_file && (dump_flags & TDF_DETAILS)) 1533 { 1534 fprintf (dump_file, " Deleted trivially dead PHI: "); 1535 print_gimple_stmt (dump_file, phi, 0, dump_flags); 1536 fprintf (dump_file, "\n"); 1537 } 1538 remove_phi_node (&si, true); 1539 removed_phi = true; 1540 released_def = true; 1541 } 1542 else 1543 gsi_next (&si); 1544 } 1545 if (removed_phi && gimple_seq_empty_p (phi_nodes (bb))) 1546 todo |= TODO_cleanup_cfg; 1547 } 1548 free (rpo); 1549 1550 /* Removal of stores may make some EH edges dead. Purge such edges from 1551 the CFG as needed. */ 1552 if (!bitmap_empty_p (need_eh_cleanup)) 1553 { 1554 gimple_purge_all_dead_eh_edges (need_eh_cleanup); 1555 todo |= TODO_cleanup_cfg; 1556 } 1557 if (!bitmap_empty_p (need_ab_cleanup)) 1558 { 1559 gimple_purge_all_dead_abnormal_call_edges (need_ab_cleanup); 1560 todo |= TODO_cleanup_cfg; 1561 } 1562 1563 BITMAP_FREE (need_eh_cleanup); 1564 BITMAP_FREE (need_ab_cleanup); 1565 1566 if (released_def) 1567 free_numbers_of_iterations_estimates (fun); 1568 1569 return todo; 1570} 1571 1572} // anon namespace 1573 1574gimple_opt_pass * 1575make_pass_dse (gcc::context *ctxt) 1576{ 1577 return new pass_dse (ctxt); 1578} 1579