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