gcc/tree-ssa-dse.c

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