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 ();)
 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).  We can also ignore defs that feed only into
 684              already visited PHIs.  */
 685           else if (gimple_code (def) != GIMPLE_PHI
 686                    && single_imm_use (gimple_vdef (def), &use_p, &use_stmt)
 687                    && (use_stmt == phi_def
 688                        || (gimple_code (use_stmt) == GIMPLE_PHI
 689                            && bitmap_bit_p (visited,
 690                                             SSA_NAME_VERSION
 691                                               (PHI_RESULT (use_stmt))))))
 692             defs.unordered_remove (i);
 693           else
 694             ++i;
 695         }
 696
 697       /* If all defs kill the ref we are done.  */
 698       if (defs.is_empty ())
 699         return DSE_STORE_DEAD;
 700       /* If more than one def survives fail.  */
 701       if (defs.length () > 1)
 702         {
 703           /* STMT might be partially dead and we may be able to reduce
 704              how many memory locations it stores into.  */
 705           if (byte_tracking_enabled && !gimple_clobber_p (stmt))
 706             return DSE_STORE_MAYBE_PARTIAL_DEAD;
 707           return DSE_STORE_LIVE;
 708         }
 709       temp = defs[0];
 710
 711       /* Track partial kills.  */
 712       if (byte_tracking_enabled)
 713         {
 714           clear_bytes_written_by (live_bytes, temp, ref);
 715           if (bitmap_empty_p (live_bytes))
 716             {
 717               if (by_clobber_p && !gimple_clobber_p (temp))
 718                 *by_clobber_p = false;
 719               return DSE_STORE_DEAD;
 720             }
 721         }
 722     }
 723   /* Continue walking until there are no more live bytes.  */
 724   while (1);
 725 }
 726
 727
 728 class dse_dom_walker : public dom_walker
 729 {
 730 public:
 731   dse_dom_walker (cdi_direction direction)
 732     : dom_walker (direction),
 733     m_live_bytes (PARAM_VALUE (PARAM_DSE_MAX_OBJECT_SIZE)),
 734     m_byte_tracking_enabled (false) {}
 735
 736   virtual edge before_dom_children (basic_block);
 737
 738 private:
 739   auto_sbitmap m_live_bytes;
 740   bool m_byte_tracking_enabled;
 741   void dse_optimize_stmt (gimple_stmt_iterator *);
 742 };
 743
 744 /* Delete a dead call at GSI, which is mem* call of some kind.  */
 745 static void
 746 delete_dead_call (gimple_stmt_iterator *gsi)
 747 {
 748   gimple *stmt = gsi_stmt (*gsi);
 749   if (dump_file && (dump_flags & TDF_DETAILS))
 750     {
 751       fprintf (dump_file, "  Deleted dead call: ");
 752       print_gimple_stmt (dump_file, stmt, 0, dump_flags);
 753       fprintf (dump_file, "\n");
 754     }
 755
 756   tree lhs = gimple_call_lhs (stmt);
 757   if (lhs)
 758     {
 759       tree ptr = gimple_call_arg (stmt, 0);
 760       gimple *new_stmt = gimple_build_assign (lhs, ptr);
 761       unlink_stmt_vdef (stmt);
 762       if (gsi_replace (gsi, new_stmt, true))
 763         bitmap_set_bit (need_eh_cleanup, gimple_bb (stmt)->index);
 764     }
 765   else
 766     {
 767       /* Then we need to fix the operand of the consuming stmt.  */
 768       unlink_stmt_vdef (stmt);
 769
 770       /* Remove the dead store.  */
 771       if (gsi_remove (gsi, true))
 772         bitmap_set_bit (need_eh_cleanup, gimple_bb (stmt)->index);
 773       release_defs (stmt);
 774     }
 775 }
 776
 777 /* Delete a dead store at GSI, which is a gimple assignment. */
 778
 779 static void
 780 delete_dead_assignment (gimple_stmt_iterator *gsi)
 781 {
 782   gimple *stmt = gsi_stmt (*gsi);
 783   if (dump_file && (dump_flags & TDF_DETAILS))
 784     {
 785       fprintf (dump_file, "  Deleted dead store: ");
 786       print_gimple_stmt (dump_file, stmt, 0, dump_flags);
 787       fprintf (dump_file, "\n");
 788     }
 789
 790   /* Then we need to fix the operand of the consuming stmt.  */
 791   unlink_stmt_vdef (stmt);
 792
 793   /* Remove the dead store.  */
 794   basic_block bb = gimple_bb (stmt);
 795   if (gsi_remove (gsi, true))
 796     bitmap_set_bit (need_eh_cleanup, bb->index);
 797
 798   /* And release any SSA_NAMEs set in this statement back to the
 799      SSA_NAME manager.  */
 800   release_defs (stmt);
 801 }
 802
 803 /* Attempt to eliminate dead stores in the statement referenced by BSI.
 804
 805    A dead store is a store into a memory location which will later be
 806    overwritten by another store without any intervening loads.  In this
 807    case the earlier store can be deleted.
 808
 809    In our SSA + virtual operand world we use immediate uses of virtual
 810    operands to detect dead stores.  If a store's virtual definition
 811    is used precisely once by a later store to the same location which
 812    post dominates the first store, then the first store is dead.  */
 813
 814 void
 815 dse_dom_walker::dse_optimize_stmt (gimple_stmt_iterator *gsi)
 816 {
 817   gimple *stmt = gsi_stmt (*gsi);
 818
 819   /* If this statement has no virtual defs, then there is nothing
 820      to do.  */
 821   if (!gimple_vdef (stmt))
 822     return;
 823
 824   /* Don't return early on *this_2(D) ={v} {CLOBBER}.  */
 825   if (gimple_has_volatile_ops (stmt)
 826       && (!gimple_clobber_p (stmt)
 827           || TREE_CODE (gimple_assign_lhs (stmt)) != MEM_REF))
 828     return;
 829
 830   ao_ref ref;
 831   if (!initialize_ao_ref_for_dse (stmt, &ref))
 832     return;
 833
 834   /* We know we have virtual definitions.  We can handle assignments and
 835      some builtin calls.  */
 836   if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL))
 837     {
 838       switch (DECL_FUNCTION_CODE (gimple_call_fndecl (stmt)))
 839         {
 840           case BUILT_IN_MEMCPY:
 841           case BUILT_IN_MEMMOVE:
 842           case BUILT_IN_MEMSET:
 843             {
 844               /* Occasionally calls with an explicit length of zero
 845                  show up in the IL.  It's pointless to do analysis
 846                  on them, they're trivially dead.  */
 847               tree size = gimple_call_arg (stmt, 2);
 848               if (integer_zerop (size))
 849                 {
 850                   delete_dead_call (gsi);
 851                   return;
 852                 }
 853
 854               enum dse_store_status store_status;
 855               m_byte_tracking_enabled
 856                 = setup_live_bytes_from_ref (&ref, m_live_bytes);
 857               store_status = dse_classify_store (&ref, stmt,
 858                                                  m_byte_tracking_enabled,
 859                                                  m_live_bytes);
 860               if (store_status == DSE_STORE_LIVE)
 861                 return;
 862
 863               if (store_status == DSE_STORE_MAYBE_PARTIAL_DEAD)
 864                 {
 865                   maybe_trim_memstar_call (&ref, m_live_bytes, stmt);
 866                   return;
 867                 }
 868
 869               if (store_status == DSE_STORE_DEAD)
 870                 delete_dead_call (gsi);
 871               return;
 872             }
 873
 874           default:
 875             return;
 876         }
 877     }
 878
 879   if (is_gimple_assign (stmt))
 880     {
 881       bool by_clobber_p = false;
 882
 883       /* Self-assignments are zombies.  */
 884       if (operand_equal_p (gimple_assign_rhs1 (stmt),
 885                            gimple_assign_lhs (stmt), 0))
 886         ;
 887       else
 888         {
 889           m_byte_tracking_enabled
 890             = setup_live_bytes_from_ref (&ref, m_live_bytes);
 891           enum dse_store_status store_status;
 892           store_status = dse_classify_store (&ref, stmt,
 893                                              m_byte_tracking_enabled,
 894                                              m_live_bytes, &by_clobber_p);
 895           if (store_status == DSE_STORE_LIVE)
 896             return;
 897
 898           if (store_status == DSE_STORE_MAYBE_PARTIAL_DEAD)
 899             {
 900               maybe_trim_partially_dead_store (&ref, m_live_bytes, stmt);
 901               return;
 902             }
 903         }
 904
 905       /* Now we know that use_stmt kills the LHS of stmt.  */
 906
 907       /* But only remove *this_2(D) ={v} {CLOBBER} if killed by
 908          another clobber stmt.  */
 909       if (gimple_clobber_p (stmt)
 910           && !by_clobber_p)
 911         return;
 912
 913       delete_dead_assignment (gsi);
 914     }
 915 }
 916
 917 edge
 918 dse_dom_walker::before_dom_children (basic_block bb)
 919 {
 920   gimple_stmt_iterator gsi;
 921
 922   for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi);)
 923     {
 924       dse_optimize_stmt (&gsi);
 925       if (gsi_end_p (gsi))
 926         gsi = gsi_last_bb (bb);
 927       else
 928         gsi_prev (&gsi);
 929     }
 930   return NULL;
 931 }
 932
 933 namespace {
 934
 935 const pass_data pass_data_dse =
 936 {
 937   GIMPLE_PASS, /* type */
 938   "dse", /* name */
 939   OPTGROUP_NONE, /* optinfo_flags */
 940   TV_TREE_DSE, /* tv_id */
 941   ( PROP_cfg | PROP_ssa ), /* properties_required */
 942   0, /* properties_provided */
 943   0, /* properties_destroyed */
 944   0, /* todo_flags_start */
 945   0, /* todo_flags_finish */
 946 };
 947
 948 class pass_dse : public gimple_opt_pass
 949 {
 950 public:
 951   pass_dse (gcc::context *ctxt)
 952     : gimple_opt_pass (pass_data_dse, ctxt)
 953   {}
 954
 955   /* opt_pass methods: */
 956   opt_pass * clone () { return new pass_dse (m_ctxt); }
 957   virtual bool gate (function *) { return flag_tree_dse != 0; }
 958   virtual unsigned int execute (function *);
 959
 960 }; // class pass_dse
 961
 962 unsigned int
 963 pass_dse::execute (function *fun)
 964 {
 965   need_eh_cleanup = BITMAP_ALLOC (NULL);
 966
 967   renumber_gimple_stmt_uids ();
 968
 969   /* We might consider making this a property of each pass so that it
 970      can be [re]computed on an as-needed basis.  Particularly since
 971      this pass could be seen as an extension of DCE which needs post
 972      dominators.  */
 973   calculate_dominance_info (CDI_POST_DOMINATORS);
 974   calculate_dominance_info (CDI_DOMINATORS);
 975
 976   /* Dead store elimination is fundamentally a walk of the post-dominator
 977      tree and a backwards walk of statements within each block.  */
 978   dse_dom_walker (CDI_POST_DOMINATORS).walk (fun->cfg->x_exit_block_ptr);
 979
 980   /* Removal of stores may make some EH edges dead.  Purge such edges from
 981      the CFG as needed.  */
 982   if (!bitmap_empty_p (need_eh_cleanup))
 983     {
 984       gimple_purge_all_dead_eh_edges (need_eh_cleanup);
 985       cleanup_tree_cfg ();
 986     }
 987
 988   BITMAP_FREE (need_eh_cleanup);
 989
 990   /* For now, just wipe the post-dominator information.  */
 991   free_dominance_info (CDI_POST_DOMINATORS);
 992   return 0;
 993 }
 994
 995 } // anon namespace
 996
 997 gimple_opt_pass *
 998 make_pass_dse (gcc::context *ctxt)
 999 {
1000   return new pass_dse (ctxt);
1001 }