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