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