gcc/tree-ssa-dse.c

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