LCOV - code coverage report
Current view: top level - gcc - tree-ssa-dse.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 98.3 % 781 768
Test Date: 2026-11-14 16:39:50 Functions: 100.0 % 31 31
Legend: Lines:     hit not hit

            Line data    Source code
       1              : /* Dead and redundant store elimination
       2              :    Copyright (C) 2004-2026 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 "tree-cfgcleanup.h"
      35              : #include "alias.h"
      36              : #include "tree-ssa-loop.h"
      37              : #include "tree-ssa-dse.h"
      38              : #include "builtins.h"
      39              : #include "gimple-fold.h"
      40              : #include "tree-eh.h"
      41              : #include "cfganal.h"
      42              : #include "cgraph.h"
      43              : #include "ipa-modref-tree.h"
      44              : #include "ipa-modref.h"
      45              : #include "target.h"
      46              : #include "tree-ssa-loop-niter.h"
      47              : #include "cfgloop.h"
      48              : #include "tree-data-ref.h"
      49              : #include "internal-fn.h"
      50              : #include "tree-ssa.h"
      51              : 
      52              : /* This file implements dead store elimination.
      53              : 
      54              :    A dead store is a store into a memory location which will later be
      55              :    overwritten by another store without any intervening loads.  In this
      56              :    case the earlier store can be deleted or trimmed if the store
      57              :    was partially dead.
      58              : 
      59              :    A redundant store is a store into a memory location which stores
      60              :    the exact same value as a prior store to the same memory location.
      61              :    While this can often be handled by dead store elimination, removing
      62              :    the redundant store is often better than removing or trimming the
      63              :    dead store.
      64              : 
      65              :    In our SSA + virtual operand world we use immediate uses of virtual
      66              :    operands to detect these cases.  If a store's virtual definition
      67              :    is used precisely once by a later store to the same location which
      68              :    post dominates the first store, then the first store is dead.  If
      69              :    the data stored is the same, then the second store is redundant.
      70              : 
      71              :    The single use of the store's virtual definition ensures that
      72              :    there are no intervening aliased loads and the requirement that
      73              :    the second load post dominate the first ensures that if the earlier
      74              :    store executes, then the later stores will execute before the function
      75              :    exits.
      76              : 
      77              :    It may help to think of this as first moving the earlier store to
      78              :    the point immediately before the later store.  Again, the single
      79              :    use of the virtual definition and the post-dominance relationship
      80              :    ensure that such movement would be safe.  Clearly if there are
      81              :    back to back stores, then the second is makes the first dead.  If
      82              :    the second store stores the same value, then the second store is
      83              :    redundant.
      84              : 
      85              :    Reviewing section 10.7.2 in Morgan's "Building an Optimizing Compiler"
      86              :    may also help in understanding this code since it discusses the
      87              :    relationship between dead store and redundant load elimination.  In
      88              :    fact, they are the same transformation applied to different views of
      89              :    the CFG.  */
      90              : 
      91              : static void delete_dead_or_redundant_call (gimple_stmt_iterator *, const char *);
      92              : 
      93              : /* Bitmap of blocks that have had EH statements cleaned.  We should
      94              :    remove their dead edges eventually.  */
      95              : static bitmap need_eh_cleanup;
      96              : static bitmap need_ab_cleanup;
      97              : 
      98              : /* STMT is a statement that may write into memory.  Analyze it and
      99              :    initialize WRITE to describe how STMT affects memory.  When
     100              :    MAY_DEF_OK is true then the function initializes WRITE to what
     101              :    the stmt may define.
     102              : 
     103              :    Return TRUE if the statement was analyzed, FALSE otherwise.
     104              : 
     105              :    It is always safe to return FALSE.  But typically better optimization
     106              :    can be achieved by analyzing more statements.  */
     107              : 
     108              : static bool
     109    240150667 : initialize_ao_ref_for_dse (gimple *stmt, ao_ref *write, bool may_def_ok = false)
     110              : {
     111              :   /* It's advantageous to handle certain mem* functions.  */
     112    240150667 :   if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL))
     113              :     {
     114      5349916 :       switch (DECL_FUNCTION_CODE (gimple_call_fndecl (stmt)))
     115              :         {
     116      1094027 :         case BUILT_IN_MEMCPY:
     117      1094027 :         case BUILT_IN_MEMMOVE:
     118      1094027 :         case BUILT_IN_MEMSET:
     119      1094027 :         case BUILT_IN_MEMCPY_CHK:
     120      1094027 :         case BUILT_IN_MEMMOVE_CHK:
     121      1094027 :         case BUILT_IN_MEMSET_CHK:
     122      1094027 :         case BUILT_IN_STRNCPY:
     123      1094027 :         case BUILT_IN_STRNCPY_CHK:
     124      1094027 :           {
     125      1094027 :             tree size = gimple_call_arg (stmt, 2);
     126      1094027 :             tree ptr = gimple_call_arg (stmt, 0);
     127      1094027 :             ao_ref_init_from_ptr_and_size (write, ptr, size);
     128      1094027 :             return true;
     129              :           }
     130              : 
     131              :         /* A calloc call can never be dead, but it can make
     132              :            subsequent stores redundant if they store 0 into
     133              :            the same memory locations.  */
     134         3649 :         case BUILT_IN_CALLOC:
     135         3649 :           {
     136         3649 :             tree nelem = gimple_call_arg (stmt, 0);
     137         3649 :             tree selem = gimple_call_arg (stmt, 1);
     138         3649 :             tree lhs;
     139         3649 :             if (TREE_CODE (nelem) == INTEGER_CST
     140         3072 :                 && TREE_CODE (selem) == INTEGER_CST
     141         6504 :                 && (lhs = gimple_call_lhs (stmt)) != NULL_TREE)
     142              :               {
     143         2844 :                 tree size = fold_build2 (MULT_EXPR, TREE_TYPE (nelem),
     144              :                                          nelem, selem);
     145         2844 :                 ao_ref_init_from_ptr_and_size (write, lhs, size);
     146         2844 :                 return true;
     147              :               }
     148              :           }
     149              : 
     150              :         default:
     151              :           break;
     152              :         }
     153              :     }
     154    234800751 :   else if (is_gimple_call (stmt)
     155    234800751 :            && gimple_call_internal_p (stmt))
     156              :     {
     157       522164 :       switch (gimple_call_internal_fn (stmt))
     158              :         {
     159         1309 :         case IFN_LEN_STORE:
     160         1309 :         case IFN_MASK_STORE:
     161         1309 :         case IFN_MASK_LEN_STORE:
     162         1309 :           {
     163         1309 :             internal_fn ifn = gimple_call_internal_fn (stmt);
     164         1309 :             int stored_value_index = internal_fn_stored_value_index (ifn);
     165         1309 :             int len_index = internal_fn_len_index (ifn);
     166         1309 :             if (ifn == IFN_LEN_STORE)
     167              :               {
     168            0 :                 tree len = gimple_call_arg (stmt, len_index);
     169            0 :                 tree bias = gimple_call_arg (stmt, len_index + 1);
     170            0 :                 if (tree_fits_uhwi_p (len))
     171              :                   {
     172            0 :                     ao_ref_init_from_ptr_and_size (write,
     173              :                                                    gimple_call_arg (stmt, 0),
     174              :                                                    int_const_binop (MINUS_EXPR,
     175              :                                                                     len, bias));
     176            0 :                     return true;
     177              :                   }
     178              :               }
     179              :             /* We cannot initialize a must-def ao_ref (in all cases) but we
     180              :                can provide a may-def variant.  */
     181         1309 :             if (may_def_ok)
     182              :               {
     183         1271 :                 ao_ref_init_from_ptr_and_range (
     184              :                   write, gimple_call_arg (stmt, 0), true, 0, -1,
     185         1271 :                   tree_to_poly_int64 (TYPE_SIZE (
     186              :                     TREE_TYPE (gimple_call_arg (stmt, stored_value_index)))));
     187         1271 :                 return true;
     188              :               }
     189              :             break;
     190              :           }
     191              :         default:;
     192              :         }
     193              :     }
     194    239052525 :   if (tree lhs = gimple_get_lhs (stmt))
     195              :     {
     196    224061591 :       if (TREE_CODE (lhs) != SSA_NAME
     197    224061591 :           && (may_def_ok || !stmt_could_throw_p (cfun, stmt)))
     198              :         {
     199    207166476 :           ao_ref_init (write, lhs);
     200    207166476 :           return true;
     201              :         }
     202              :     }
     203              :   return false;
     204              : }
     205              : 
     206              : /* Given REF from the alias oracle, return TRUE if it is a valid
     207              :    kill memory reference for dead store elimination, false otherwise.
     208              : 
     209              :    In particular, the reference must have a known base, known maximum
     210              :    size, start at a byte offset and have a size that is one or more
     211              :    bytes.  */
     212              : 
     213              : static bool
     214    174346258 : valid_ao_ref_kill_for_dse (ao_ref *ref)
     215              : {
     216    174346258 :   return (ao_ref_base (ref)
     217    174346258 :           && known_size_p (ref->max_size)
     218    173998470 :           && maybe_ne (ref->size, 0)
     219    173980730 :           && known_eq (ref->max_size, ref->size)
     220    347812474 :           && known_ge (ref->offset, 0));
     221              : }
     222              : 
     223              : /* Given REF from the alias oracle, return TRUE if it is a valid
     224              :    load or store memory reference for dead store elimination, false otherwise.
     225              : 
     226              :    Unlike for valid_ao_ref_kill_for_dse we can accept writes where max_size
     227              :    is not same as size since we can handle conservatively the larger range.  */
     228              : 
     229              : static bool
     230     39191033 : valid_ao_ref_for_dse (ao_ref *ref)
     231              : {
     232     39191033 :   return (ao_ref_base (ref)
     233     39191033 :           && known_size_p (ref->max_size)
     234     77877655 :           && known_ge (ref->offset, 0));
     235              : }
     236              : 
     237              : /* Initialize OFFSET and SIZE to a range known to contain REF
     238              :    where the boundaries are divisible by BITS_PER_UNIT (bit still in bits).
     239              :    Return false if this is impossible.  */
     240              : 
     241              : static bool
     242    107117677 : get_byte_aligned_range_containing_ref (ao_ref *ref, poly_int64 *offset,
     243              :                                        HOST_WIDE_INT *size)
     244              : {
     245            0 :   if (!known_size_p (ref->max_size))
     246              :     return false;
     247    107117677 :   *offset = aligned_lower_bound (ref->offset, BITS_PER_UNIT);
     248    107117677 :   poly_int64 end = aligned_upper_bound (ref->offset + ref->max_size,
     249              :                                         BITS_PER_UNIT);
     250    107117677 :   return (end - *offset).is_constant (size);
     251              : }
     252              : 
     253              : /* Initialize OFFSET and SIZE to a range known to be contained REF
     254              :    where the boundaries are divisible by BITS_PER_UNIT (but still in bits).
     255              :    Return false if this is impossible.  */
     256              : 
     257              : static bool
     258     99866798 : get_byte_aligned_range_contained_in_ref (ao_ref *ref, poly_int64 *offset,
     259              :                                          HOST_WIDE_INT *size)
     260              : {
     261     99866798 :   if (!known_size_p (ref->size)
     262     99866798 :       || !known_eq (ref->size, ref->max_size))
     263              :     return false;
     264     99866798 :   *offset = aligned_upper_bound (ref->offset, BITS_PER_UNIT);
     265     99866798 :   poly_int64 end = aligned_lower_bound (ref->offset + ref->max_size,
     266              :                                         BITS_PER_UNIT);
     267              :   /* For bit accesses we can get -1 here, but also 0 sized kill is not
     268              :      useful.  */
     269     99866798 :   if (!known_gt (end, *offset))
     270              :     return false;
     271     99715755 :   return (end - *offset).is_constant (size);
     272              : }
     273              : 
     274              : /* Compute byte range (returned iN REF_OFFSET and RET_SIZE) for access COPY
     275              :    inside REF.  If KILL is true, then COPY represent a kill and the byte range
     276              :    needs to be fully contained in bit range given by COPY.  If KILL is false
     277              :    then the byte range returned must contain the range of COPY.  */
     278              : 
     279              : static bool
     280    103567759 : get_byte_range (ao_ref *copy, ao_ref *ref, bool kill,
     281              :                 HOST_WIDE_INT *ret_offset, HOST_WIDE_INT *ret_size)
     282              : {
     283    103567759 :   HOST_WIDE_INT copy_size, ref_size;
     284    103567759 :   poly_int64 copy_offset, ref_offset;
     285    103567759 :   HOST_WIDE_INT diff;
     286              : 
     287              :   /* First translate from bits to bytes, rounding to bigger or smaller ranges
     288              :      as needed.  Kills needs to be always rounded to smaller ranges while
     289              :      uses and stores to larger ranges.  */
     290    103567759 :   if (kill)
     291              :     {
     292     99866798 :       if (!get_byte_aligned_range_contained_in_ref (copy, &copy_offset,
     293              :                                                     &copy_size))
     294              :         return false;
     295              :     }
     296              :   else
     297              :     {
     298      3700961 :       if (!get_byte_aligned_range_containing_ref (copy, &copy_offset,
     299              :                                                   &copy_size))
     300              :         return false;
     301              :     }
     302              : 
     303    103416716 :   if (!get_byte_aligned_range_containing_ref (ref, &ref_offset, &ref_size)
     304              :       || !ordered_p (copy_offset, ref_offset))
     305              :     return false;
     306              : 
     307              :   /* Switch sizes from bits to bytes so we do not need to care about
     308              :      overflows.  Offset calculation needs to stay in bits until we compute
     309              :      the difference and can switch to HOST_WIDE_INT.  */
     310    103416716 :   copy_size /= BITS_PER_UNIT;
     311    103416716 :   ref_size /= BITS_PER_UNIT;
     312              : 
     313              :   /* If COPY starts before REF, then reset the beginning of
     314              :      COPY to match REF and decrease the size of COPY by the
     315              :      number of bytes removed from COPY.  */
     316    103416716 :   if (maybe_lt (copy_offset, ref_offset))
     317              :     {
     318      9864077 :       if (!(ref_offset - copy_offset).is_constant (&diff)
     319      9864077 :           || copy_size < diff / BITS_PER_UNIT)
     320              :         return false;
     321      2806437 :       copy_size -= diff / BITS_PER_UNIT;
     322      2806437 :       copy_offset = ref_offset;
     323              :     }
     324              : 
     325     96359076 :   if (!(copy_offset - ref_offset).is_constant (&diff)
     326     96359076 :       || ref_size <= diff / BITS_PER_UNIT)
     327              :     return false;
     328              : 
     329              :   /* If COPY extends beyond REF, chop off its size appropriately.  */
     330      6416364 :   HOST_WIDE_INT limit = ref_size - diff / BITS_PER_UNIT;
     331              : 
     332      6416364 :   if (copy_size > limit)
     333      1153698 :     copy_size = limit;
     334      6416364 :   *ret_size = copy_size;
     335      6416364 :   if (!(copy_offset - ref_offset).is_constant (ret_offset))
     336              :     return false;
     337      6416364 :   *ret_offset /= BITS_PER_UNIT;
     338      6416364 :   return true;
     339              : }
     340              : 
     341              : /* Update LIVE_BYTES tracking REF for write to WRITE:
     342              :    Verify we have the same base memory address, the write
     343              :    has a known size and overlaps with REF.  */
     344              : static void
     345    174346258 : clear_live_bytes_for_ref (sbitmap live_bytes, ao_ref *ref, ao_ref *write)
     346              : {
     347    174346258 :   HOST_WIDE_INT start, size;
     348              : 
     349    174346258 :   if (valid_ao_ref_kill_for_dse (write)
     350    173465940 :       && operand_equal_p (write->base, ref->base, OEP_ADDRESS_OF)
     351    274213056 :       && get_byte_range (write, ref, true, &start, &size))
     352      2715403 :     bitmap_clear_range (live_bytes, start, size);
     353    174346258 : }
     354              : 
     355              : /* Clear any bytes written by STMT from the bitmap LIVE_BYTES.  The base
     356              :    address written by STMT must match the one found in REF, which must
     357              :    have its base address previously initialized.
     358              : 
     359              :    This routine must be conservative.  If we don't know the offset or
     360              :    actual size written, assume nothing was written.  */
     361              : 
     362              : static void
     363    188266150 : clear_bytes_written_by (sbitmap live_bytes, gimple *stmt, ao_ref *ref)
     364              : {
     365    188266150 :   ao_ref write;
     366              : 
     367    188266150 :   if (gcall *call = dyn_cast <gcall *> (stmt))
     368              :     {
     369      4963525 :       bool interposed;
     370      4963525 :       modref_summary *summary = get_modref_function_summary (call, &interposed);
     371              : 
     372      4963525 :       if (summary && !interposed)
     373       742043 :         for (auto kill : summary->kills)
     374        52843 :           if (kill.get_ao_ref (as_a <gcall *> (stmt), &write))
     375        52819 :             clear_live_bytes_for_ref (live_bytes, ref, &write);
     376              :     }
     377    188266150 :   if (!initialize_ao_ref_for_dse (stmt, &write))
     378              :     return;
     379              : 
     380    174293439 :   clear_live_bytes_for_ref (live_bytes, ref, &write);
     381              : }
     382              : 
     383              : /* REF is a memory write.  Extract relevant information from it and
     384              :    initialize the LIVE_BYTES bitmap.  If successful, return TRUE.
     385              :    Otherwise return FALSE.  */
     386              : 
     387              : static bool
     388     32582847 : setup_live_bytes_from_ref (ao_ref *ref, sbitmap live_bytes)
     389              : {
     390     32582847 :   HOST_WIDE_INT const_size;
     391     32582847 :   if (valid_ao_ref_for_dse (ref)
     392     32114696 :       && ((aligned_upper_bound (ref->offset + ref->max_size, BITS_PER_UNIT)
     393     32114696 :            - aligned_lower_bound (ref->offset,
     394     32114696 :                                   BITS_PER_UNIT)).is_constant (&const_size))
     395     32114696 :       && (const_size / BITS_PER_UNIT <= param_dse_max_object_size)
     396     64370104 :       && const_size > 1)
     397              :     {
     398     31787030 :       bitmap_clear (live_bytes);
     399     31787030 :       bitmap_set_range (live_bytes, 0, const_size / BITS_PER_UNIT);
     400     31787030 :       return true;
     401              :     }
     402              :   return false;
     403              : }
     404              : 
     405              : /* Compute the number of stored bytes that we can trim from the head and
     406              :    tail of REF.  LIVE is the bitmap of stores to REF that are still live.
     407              : 
     408              :    Store the number of bytes trimmed from the head and tail in TRIM_HEAD
     409              :    and TRIM_TAIL respectively.
     410              : 
     411              :    STMT is the statement being trimmed and is used for debugging dump
     412              :    output only.  */
     413              : 
     414              : static void
     415      3509521 : compute_trims (ao_ref *ref, sbitmap live, int *trim_head, int *trim_tail,
     416              :                gimple *stmt)
     417              : {
     418      3509521 :   *trim_head = 0;
     419      3509521 :   *trim_tail = 0;
     420              : 
     421              :   /* We use bitmaps biased such that ref->offset is contained in bit zero and
     422              :      the bitmap extends through ref->max_size, so we know that in the original
     423              :      bitmap bits 0 .. ref->max_size were true.  But we need to check that this
     424              :      covers the bytes of REF exactly.  */
     425      3509521 :   const unsigned int offset_align = known_alignment (ref->offset);
     426      3509521 :   const unsigned int size_align = known_alignment (ref->size);
     427      3509521 :   if ((offset_align > 0 && offset_align < BITS_PER_UNIT)
     428      3509232 :       || (size_align > 0 && size_align < BITS_PER_UNIT)
     429      7018753 :       || !known_eq (ref->size, ref->max_size))
     430        12475 :     return;
     431              : 
     432              :   /* Now identify how much, if any of the tail we can chop off.  */
     433      3497046 :   HOST_WIDE_INT const_size;
     434      3497046 :   int last_live = bitmap_last_set_bit (live);
     435      3497046 :   if (ref->size.is_constant (&const_size))
     436              :     {
     437      3497046 :       int last_orig = (const_size / BITS_PER_UNIT) - 1;
     438              :       /* We can leave inconvenient amounts on the tail as
     439              :          residual handling in mem* and str* functions is usually
     440              :          reasonably efficient.  */
     441      3497046 :       *trim_tail = last_orig - last_live;
     442              : 
     443              :       /* But don't trim away out of bounds accesses, as this defeats
     444              :          proper warnings.
     445              : 
     446              :          We could have a type with no TYPE_SIZE_UNIT or we could have a VLA
     447              :          where TYPE_SIZE_UNIT is not a constant.  */
     448      3497046 :       if (*trim_tail
     449        10336 :           && TYPE_SIZE_UNIT (TREE_TYPE (ref->base))
     450        10336 :           && TREE_CODE (TYPE_SIZE_UNIT (TREE_TYPE (ref->base))) == INTEGER_CST
     451      3507381 :           && compare_tree_int (TYPE_SIZE_UNIT (TREE_TYPE (ref->base)),
     452              :                                last_orig) <= 0)
     453          128 :         *trim_tail = 0;
     454              :     }
     455              : 
     456              :   /* Identify how much, if any of the head we can chop off.  */
     457      3497046 :   int first_orig = 0;
     458      3497046 :   int first_live = bitmap_first_set_bit (live);
     459      3497046 :   *trim_head = first_live - first_orig;
     460              : 
     461              :   /* If REF is aligned, try to maintain this alignment if it reduces
     462              :      the number of (power-of-two sized aligned) writes to memory.  */
     463      3497046 :   unsigned int align_bits;
     464      3497046 :   unsigned HOST_WIDE_INT bitpos;
     465      3401604 :   if ((*trim_head || *trim_tail)
     466       101018 :       && last_live - first_live >= 2
     467        98601 :       && ao_ref_alignment (ref, &align_bits, &bitpos)
     468        80211 :       && align_bits >= 32
     469        79834 :       && bitpos == 0
     470      3572530 :       && align_bits % BITS_PER_UNIT == 0)
     471              :     {
     472        75484 :       unsigned int align_units = align_bits / BITS_PER_UNIT;
     473        75484 :       if (align_units > 16)
     474              :         align_units = 16;
     475        77444 :       while ((first_live | (align_units - 1)) > (unsigned int)last_live)
     476         1960 :         align_units >>= 1;
     477              : 
     478        75484 :       if (*trim_head)
     479              :         {
     480        71115 :           unsigned int pos = first_live & (align_units - 1);
     481        79271 :           for (unsigned int i = 1; i <= align_units; i <<= 1)
     482              :             {
     483        79271 :               unsigned int mask = ~(i - 1);
     484        79271 :               unsigned int bytes = align_units - (pos & mask);
     485        79271 :               if (wi::popcount (bytes) <= 1)
     486              :                 {
     487        71115 :                   *trim_head &= mask;
     488        71115 :                   break;
     489              :                 }
     490              :             }
     491              :         }
     492              : 
     493        75484 :       if (*trim_tail)
     494              :         {
     495         7209 :           unsigned int pos = last_live & (align_units - 1);
     496        10478 :           for (unsigned int i = 1; i <= align_units; i <<= 1)
     497              :             {
     498        10478 :               int mask = i - 1;
     499        10478 :               unsigned int bytes = (pos | mask) + 1;
     500        10478 :               if ((last_live | mask) > (last_live + *trim_tail))
     501              :                 break;
     502        10478 :               if (wi::popcount (bytes) <= 1)
     503              :                 {
     504         7209 :                   unsigned int extra = (last_live | mask) - last_live;
     505         7209 :                   *trim_tail -= extra;
     506         7209 :                   break;
     507              :                 }
     508              :             }
     509              :         }
     510              :     }
     511              : 
     512      3497046 :   if ((*trim_head || *trim_tail) && dump_file && (dump_flags & TDF_DETAILS))
     513              :     {
     514           18 :       fprintf (dump_file, "  Trimming statement (head = %d, tail = %d): ",
     515              :                *trim_head, *trim_tail);
     516           18 :       print_gimple_stmt (dump_file, stmt, 0, dump_flags);
     517           18 :       fprintf (dump_file, "\n");
     518              :     }
     519              : }
     520              : 
     521              : /* STMT initializes an object from COMPLEX_CST where one or more of the bytes
     522              :    written may be dead stores.  REF is a representation of the memory written.
     523              :    LIVE is the bitmap of stores to REF that are still live.
     524              : 
     525              :    Attempt to rewrite STMT so that only the real or the imaginary part of the
     526              :    object is actually stored.  */
     527              : 
     528              : static void
     529         6061 : maybe_trim_complex_store (ao_ref *ref, sbitmap live, gimple *stmt)
     530              : {
     531         6061 :   int trim_head, trim_tail;
     532         6061 :   compute_trims (ref, live, &trim_head, &trim_tail, stmt);
     533              : 
     534              :   /* The amount of data trimmed from the head or tail must be at
     535              :      least half the size of the object to ensure we're trimming
     536              :      the entire real or imaginary half.  By writing things this
     537              :      way we avoid more O(n) bitmap operations.  */
     538         6061 :   if (known_ge (trim_tail * 2 * BITS_PER_UNIT, ref->size))
     539              :     {
     540              :       /* TREE_REALPART is live */
     541            2 :       tree x = TREE_REALPART (gimple_assign_rhs1 (stmt));
     542            2 :       tree y = gimple_assign_lhs (stmt);
     543            2 :       y = build1 (REALPART_EXPR, TREE_TYPE (x), y);
     544            2 :       gimple_assign_set_lhs (stmt, y);
     545            2 :       gimple_assign_set_rhs1 (stmt, x);
     546              :     }
     547         6059 :   else if (known_ge (trim_head * 2 * BITS_PER_UNIT, ref->size))
     548              :     {
     549              :       /* TREE_IMAGPART is live */
     550            3 :       tree x = TREE_IMAGPART (gimple_assign_rhs1 (stmt));
     551            3 :       tree y = gimple_assign_lhs (stmt);
     552            3 :       y = build1 (IMAGPART_EXPR, TREE_TYPE (x), y);
     553            3 :       gimple_assign_set_lhs (stmt, y);
     554            3 :       gimple_assign_set_rhs1 (stmt, x);
     555              :     }
     556              : 
     557              :   /* Other cases indicate parts of both the real and imag subobjects
     558              :      are live.  We do not try to optimize those cases.  */
     559         6061 : }
     560              : 
     561              : /* STMT initializes an object using a CONSTRUCTOR where one or more of the
     562              :    bytes written are dead stores.  REF is a representation of the memory
     563              :    written.  LIVE is the bitmap of stores to REF that are still live.
     564              : 
     565              :    Attempt to rewrite STMT so that it writes fewer memory locations.
     566              : 
     567              :    The most common case for getting here is a CONSTRUCTOR with no elements
     568              :    being used to zero initialize an object.  We do not try to handle other
     569              :    cases as those would force us to fully cover the object with the
     570              :    CONSTRUCTOR node except for the components that are dead.
     571              :    Also handles integer stores of 0 which can happen with memset/memcpy optimizations.  */
     572              : 
     573              : static void
     574      3364622 : maybe_trim_constructor_store (ao_ref *ref, sbitmap live, gimple *stmt, bool was_integer_cst)
     575              : {
     576      3364622 :   tree ctor = gimple_assign_rhs1 (stmt);
     577              : 
     578              :   /* This is the only case we currently handle.  It actually seems to
     579              :      catch most cases of actual interest.  */
     580      3871198 :   gcc_assert (was_integer_cst ? integer_zerop (ctor) : CONSTRUCTOR_NELTS (ctor) == 0);
     581              : 
     582      3364622 :   int head_trim = 0;
     583      3364622 :   int tail_trim = 0;
     584      3364622 :   compute_trims (ref, live, &head_trim, &tail_trim, stmt);
     585              : 
     586              :   /* Now we want to replace the constructor initializer
     587              :      with memset (object + head_trim, 0, size - head_trim - tail_trim).  */
     588      3364622 :   if (head_trim || tail_trim)
     589              :     {
     590              :       /* We want &lhs for the MEM_REF expression.  */
     591        94151 :       tree lhs_addr = build_fold_addr_expr (gimple_assign_lhs (stmt));
     592              : 
     593        94151 :       STRIP_USELESS_TYPE_CONVERSION (lhs_addr);
     594              : 
     595        94151 :       if (! is_gimple_min_invariant (lhs_addr))
     596        18508 :         return;
     597              : 
     598              :       /* The number of bytes for the new constructor.  */
     599        75643 :       poly_int64 ref_bytes = exact_div (ref->size, BITS_PER_UNIT);
     600        75643 :       poly_int64 count = ref_bytes - head_trim - tail_trim;
     601              : 
     602              :       /* And the new type for the CONSTRUCTOR.  Essentially it's just
     603              :          a char array large enough to cover the non-trimmed parts of
     604              :          the original CONSTRUCTOR.  Note we want explicit bounds here
     605              :          so that we know how many bytes to clear when expanding the
     606              :          CONSTRUCTOR.  */
     607        75643 :       tree type = build_array_type_nelts (char_type_node, count);
     608              : 
     609              :       /* Build a suitable alias type rather than using alias set zero
     610              :          to avoid pessimizing.  */
     611        75643 :       tree alias_type = reference_alias_ptr_type (gimple_assign_lhs (stmt));
     612              : 
     613              :       /* Build a MEM_REF representing the whole accessed area, starting
     614              :          at the first byte not trimmed.  */
     615        75643 :       tree exp = fold_build2 (MEM_REF, type, lhs_addr,
     616              :                               build_int_cst (alias_type, head_trim));
     617              : 
     618              :       /* Now update STMT with a new RHS and LHS.  */
     619        75643 :       gimple_assign_set_lhs (stmt, exp);
     620        75643 :       gimple_assign_set_rhs1 (stmt, build_constructor (type, NULL));
     621              :     }
     622              : }
     623              : 
     624              : /* STMT is a memcpy, memmove or memset.  Decrement the number of bytes
     625              :    copied/set by DECREMENT.  */
     626              : static void
     627          848 : decrement_count (gimple *stmt, int decrement)
     628              : {
     629          848 :   tree *countp = gimple_call_arg_ptr (stmt, 2);
     630          848 :   gcc_assert (TREE_CODE (*countp) == INTEGER_CST);
     631         1696 :   *countp = wide_int_to_tree (TREE_TYPE (*countp), (TREE_INT_CST_LOW (*countp)
     632          848 :                                                     - decrement));
     633          848 : }
     634              : 
     635              : static void
     636          782 : increment_start_addr (gimple *stmt, tree *where, int increment)
     637              : {
     638          782 :   if (tree lhs = gimple_call_lhs (stmt))
     639            6 :     if (where == gimple_call_arg_ptr (stmt, 0))
     640              :       {
     641            6 :         gassign *newop = gimple_build_assign (lhs, unshare_expr (*where));
     642            6 :         gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
     643            6 :         gsi_insert_after (&gsi, newop, GSI_SAME_STMT);
     644            6 :         gimple_call_set_lhs (stmt, NULL_TREE);
     645            6 :         update_stmt (stmt);
     646              :       }
     647              : 
     648          782 :   if (TREE_CODE (*where) == SSA_NAME)
     649              :     {
     650          217 :       tree tem = make_ssa_name (TREE_TYPE (*where));
     651          217 :       gassign *newop
     652          217 :         = gimple_build_assign (tem, POINTER_PLUS_EXPR, *where,
     653          217 :                                build_int_cst (sizetype, increment));
     654          217 :       gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
     655          217 :       gsi_insert_before (&gsi, newop, GSI_SAME_STMT);
     656          217 :       *where = tem;
     657          217 :       update_stmt (stmt);
     658          217 :       return;
     659              :     }
     660              : 
     661          565 :   *where = build_fold_addr_expr (fold_build2 (MEM_REF, char_type_node,
     662              :                                               *where,
     663              :                                               build_int_cst (ptr_type_node,
     664              :                                                              increment)));
     665          565 :   STRIP_USELESS_TYPE_CONVERSION (*where);
     666              : }
     667              : 
     668              : /* STMT is builtin call that writes bytes in bitmap ORIG, some bytes are dead
     669              :    (ORIG & ~NEW) and need not be stored.  Try to rewrite STMT to reduce
     670              :    the amount of data it actually writes.
     671              : 
     672              :    Right now we only support trimming from the head or the tail of the
     673              :    memory region.  In theory we could split the mem* call, but it's
     674              :    likely of marginal value.  */
     675              : 
     676              : static void
     677       138838 : maybe_trim_memstar_call (ao_ref *ref, sbitmap live, gimple *stmt)
     678              : {
     679       138838 :   int head_trim, tail_trim;
     680       138838 :   switch (DECL_FUNCTION_CODE (gimple_call_fndecl (stmt)))
     681              :     {
     682         4645 :     case BUILT_IN_STRNCPY:
     683         4645 :     case BUILT_IN_STRNCPY_CHK:
     684         4645 :       compute_trims (ref, live, &head_trim, &tail_trim, stmt);
     685         4645 :       if (head_trim)
     686              :         {
     687              :           /* Head trimming of strncpy is only possible if we can
     688              :              prove all bytes we would trim are non-zero (or we could
     689              :              turn the strncpy into memset if there must be zero
     690              :              among the head trimmed bytes).  If we don't know anything
     691              :              about those bytes, the presence or absence of '\0' bytes
     692              :              in there will affect whether it acts for the non-trimmed
     693              :              bytes as memset or memcpy/strncpy.  */
     694           74 :           c_strlen_data lendata = { };
     695           74 :           int orig_head_trim = head_trim;
     696           74 :           tree srcstr = gimple_call_arg (stmt, 1);
     697           74 :           if (!get_range_strlen (srcstr, &lendata, /*eltsize=*/1)
     698           74 :               || !tree_fits_uhwi_p (lendata.minlen))
     699            8 :             head_trim = 0;
     700           66 :           else if (tree_to_uhwi (lendata.minlen) < (unsigned) head_trim)
     701              :             {
     702           60 :               head_trim = tree_to_uhwi (lendata.minlen);
     703           60 :               if ((orig_head_trim & (UNITS_PER_WORD - 1)) == 0)
     704            0 :                 head_trim &= ~(UNITS_PER_WORD - 1);
     705              :             }
     706           74 :           if (orig_head_trim != head_trim
     707           68 :               && dump_file
     708           82 :               && (dump_flags & TDF_DETAILS))
     709            8 :             fprintf (dump_file,
     710              :                      "  Adjusting strncpy trimming to (head = %d,"
     711              :                      " tail = %d)\n", head_trim, tail_trim);
     712              :         }
     713         4645 :       goto do_memcpy;
     714              : 
     715        94387 :     case BUILT_IN_MEMCPY:
     716        94387 :     case BUILT_IN_MEMMOVE:
     717        94387 :     case BUILT_IN_MEMCPY_CHK:
     718        94387 :     case BUILT_IN_MEMMOVE_CHK:
     719        94387 :       compute_trims (ref, live, &head_trim, &tail_trim, stmt);
     720              : 
     721        99032 :     do_memcpy:
     722              :       /* Tail trimming is easy, we can just reduce the count.  */
     723        99032 :       if (tail_trim)
     724           75 :         decrement_count (stmt, tail_trim);
     725              : 
     726              :       /* Head trimming requires adjusting all the arguments.  */
     727        99032 :       if (head_trim)
     728              :         {
     729              :           /* For __*_chk need to adjust also the last argument.  */
     730          125 :           if (gimple_call_num_args (stmt) == 4)
     731              :             {
     732           49 :               tree size = gimple_call_arg (stmt, 3);
     733           49 :               if (!tree_fits_uhwi_p (size))
     734              :                 break;
     735            7 :               if (!integer_all_onesp (size))
     736              :                 {
     737            7 :                   unsigned HOST_WIDE_INT sz = tree_to_uhwi (size);
     738            7 :                   if (sz < (unsigned) head_trim)
     739              :                     break;
     740            7 :                   tree arg = wide_int_to_tree (TREE_TYPE (size),
     741            7 :                                                sz - head_trim);
     742            7 :                   gimple_call_set_arg (stmt, 3, arg);
     743              :                 }
     744              :             }
     745           83 :           tree *dst = gimple_call_arg_ptr (stmt, 0);
     746           83 :           increment_start_addr (stmt, dst, head_trim);
     747           83 :           tree *src = gimple_call_arg_ptr (stmt, 1);
     748           83 :           increment_start_addr (stmt, src, head_trim);
     749           83 :           decrement_count (stmt, head_trim);
     750              :         }
     751              :       break;
     752              : 
     753        39806 :     case BUILT_IN_MEMSET:
     754        39806 :     case BUILT_IN_MEMSET_CHK:
     755        39806 :       compute_trims (ref, live, &head_trim, &tail_trim, stmt);
     756              : 
     757              :       /* Tail trimming is easy, we can just reduce the count.  */
     758        39806 :       if (tail_trim)
     759           74 :         decrement_count (stmt, tail_trim);
     760              : 
     761              :       /* Head trimming requires adjusting all the arguments.  */
     762        39806 :       if (head_trim)
     763              :         {
     764              :           /* For __*_chk need to adjust also the last argument.  */
     765          616 :           if (gimple_call_num_args (stmt) == 4)
     766              :             {
     767            7 :               tree size = gimple_call_arg (stmt, 3);
     768            7 :               if (!tree_fits_uhwi_p (size))
     769              :                 break;
     770            7 :               if (!integer_all_onesp (size))
     771              :                 {
     772            7 :                   unsigned HOST_WIDE_INT sz = tree_to_uhwi (size);
     773            7 :                   if (sz < (unsigned) head_trim)
     774              :                     break;
     775            7 :                   tree arg = wide_int_to_tree (TREE_TYPE (size),
     776            7 :                                                sz - head_trim);
     777            7 :                   gimple_call_set_arg (stmt, 3, arg);
     778              :                 }
     779              :             }
     780          616 :           tree *dst = gimple_call_arg_ptr (stmt, 0);
     781          616 :           increment_start_addr (stmt, dst, head_trim);
     782          616 :           decrement_count (stmt, head_trim);
     783              :         }
     784              :       break;
     785              : 
     786              :     default:
     787              :       break;
     788              :     }
     789       138838 : }
     790              : 
     791              : /* STMT is a memory write where one or more bytes written are dead stores.
     792              :    REF is a representation of the memory written.  LIVE is the bitmap of
     793              :    stores to REF that are still live.
     794              : 
     795              :    Attempt to rewrite STMT so that it writes fewer memory locations.  Right
     796              :    now we only support trimming at the start or end of the memory region.
     797              :    It's not clear how much there is to be gained by trimming from the middle
     798              :    of the region.  */
     799              : 
     800              : static void
     801     26978867 : maybe_trim_partially_dead_store (ao_ref *ref, sbitmap live, gimple *stmt)
     802              : {
     803     26978867 :   if (is_gimple_assign (stmt)
     804     26978867 :       && TREE_CODE (gimple_assign_lhs (stmt)) != TARGET_MEM_REF)
     805              :     {
     806     25614211 :       switch (gimple_assign_rhs_code (stmt))
     807              :         {
     808       506576 :         case CONSTRUCTOR:
     809       506576 :           maybe_trim_constructor_store (ref, live, stmt, false);
     810       506576 :           break;
     811         6061 :         case COMPLEX_CST:
     812         6061 :           maybe_trim_complex_store (ref, live, stmt);
     813         6061 :           break;
     814      9023366 :         case INTEGER_CST:
     815      9023366 :           if (integer_zerop (gimple_assign_rhs1 (stmt))
     816      9023366 :               && type_has_mode_precision_p (TREE_TYPE (gimple_assign_lhs (stmt))))
     817      2858046 :             maybe_trim_constructor_store (ref, live, stmt, true);
     818              :           break;
     819              :         default:
     820              :           break;
     821              :         }
     822              :     }
     823     26978867 : }
     824              : 
     825              : /* Return TRUE if USE_REF reads bytes from LIVE where live is
     826              :    derived from REF, a write reference.
     827              : 
     828              :    While this routine may modify USE_REF, it's passed by value, not
     829              :    location.  So callers do not see those modifications.  */
     830              : 
     831              : static bool
     832      3700961 : live_bytes_read (ao_ref *use_ref, ao_ref *ref, sbitmap live)
     833              : {
     834              :   /* We have already verified that USE_REF and REF hit the same object.
     835              :      Now verify that there's actually an overlap between USE_REF and REF.  */
     836      3700961 :   HOST_WIDE_INT start, size;
     837      3700961 :   if (get_byte_range (use_ref, ref, false, &start, &size))
     838              :     {
     839              :       /* If USE_REF covers all of REF, then it will hit one or more
     840              :          live bytes.   This avoids useless iteration over the bitmap
     841              :          below.  */
     842      3700961 :       if (start == 0 && known_eq (size * 8, ref->size))
     843              :         return true;
     844              : 
     845              :       /* Now check if any of the remaining bits in use_ref are set in LIVE.  */
     846       989401 :       return bitmap_any_bit_in_range_p (live, start, (start + size - 1));
     847              :     }
     848              :   return true;
     849              : }
     850              : 
     851              : /* Callback for dse_classify_store calling for_each_index.  Verify that
     852              :    indices are invariant in the loop with backedge PHI in basic-block DATA.  */
     853              : 
     854              : static bool
     855      2780031 : check_name (tree, tree *idx, void *data)
     856              : {
     857      2780031 :   basic_block phi_bb = (basic_block) data;
     858      2780031 :   if (TREE_CODE (*idx) == SSA_NAME
     859      1853760 :       && !SSA_NAME_IS_DEFAULT_DEF (*idx)
     860      4490516 :       && dominated_by_p (CDI_DOMINATORS, gimple_bb (SSA_NAME_DEF_STMT (*idx)),
     861              :                          phi_bb))
     862      1532018 :     return false;
     863              :   return true;
     864              : }
     865              : 
     866              : /* STMT stores the value 0 into one or more memory locations
     867              :    (via memset, empty constructor, calloc call, etc).
     868              : 
     869              :    See if there is a subsequent store of the value 0 to one
     870              :    or more of the same memory location(s).  If so, the subsequent
     871              :    store is redundant and can be removed.
     872              : 
     873              :    The subsequent stores could be via memset, empty constructors,
     874              :    simple MEM stores, etc.  */
     875              : 
     876              : static void
     877      4346123 : dse_optimize_redundant_stores (gimple *stmt)
     878              : {
     879      4346123 :   int cnt = 0;
     880              : 
     881              :   /* TBAA state of STMT, if it is a call it is effectively alias-set zero.  */
     882      4346123 :   alias_set_type earlier_set = 0;
     883      4346123 :   alias_set_type earlier_base_set = 0;
     884      4346123 :   if (is_gimple_assign (stmt))
     885              :     {
     886      4287007 :       ao_ref lhs_ref;
     887      4287007 :       ao_ref_init (&lhs_ref, gimple_assign_lhs (stmt));
     888      4287007 :       earlier_set = ao_ref_alias_set (&lhs_ref);
     889      4287007 :       earlier_base_set = ao_ref_base_alias_set (&lhs_ref);
     890              :     }
     891              : 
     892              :   /* We could do something fairly complex and look through PHIs
     893              :      like DSE_CLASSIFY_STORE, but it doesn't seem to be worth
     894              :      the effort.
     895              : 
     896              :      Look at all the immediate uses of the VDEF (which are obviously
     897              :      dominated by STMT).   See if one or more stores 0 into the same
     898              :      memory locations a STMT, if so remove the immediate use statements.  */
     899      4346123 :   tree defvar = gimple_vdef (stmt);
     900      4346123 :   imm_use_iterator ui;
     901      4346123 :   gimple *use_stmt;
     902      9745197 :   FOR_EACH_IMM_USE_STMT (use_stmt, ui, defvar)
     903              :     {
     904              :       /* Limit stmt walking.  */
     905      5420300 :       if (++cnt > param_dse_max_alias_queries_per_store)
     906              :         break;
     907              : 
     908              :       /* If USE_STMT stores 0 into one or more of the same locations
     909              :          as STMT and STMT would kill USE_STMT, then we can just remove
     910              :          USE_STMT.  */
     911      5420300 :       tree fndecl;
     912      5420300 :       if ((is_gimple_assign (use_stmt)
     913      3834304 :            && gimple_vdef (use_stmt)
     914      3146015 :            && gimple_assign_single_p (use_stmt)
     915      3146015 :            && !gimple_has_volatile_ops (use_stmt)
     916      2984593 :            && initializer_zerop (gimple_assign_rhs1 (use_stmt)))
     917      7792291 :           || (gimple_call_builtin_p (use_stmt, BUILT_IN_NORMAL)
     918       165329 :               && (fndecl = gimple_call_fndecl (use_stmt)) != NULL
     919       165329 :               && (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMSET
     920       144208 :                   || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMSET_CHK)
     921        21212 :               && integer_zerop (gimple_call_arg (use_stmt, 1))))
     922              :         {
     923      1480987 :           ao_ref write;
     924              : 
     925      1480987 :           if (!initialize_ao_ref_for_dse (use_stmt, &write))
     926              :             break;
     927              : 
     928      1459761 :           if (valid_ao_ref_for_dse (&write)
     929      1459761 :               && stmt_kills_ref_p (stmt, &write))
     930              :             {
     931         5655 :               gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
     932         5655 :               if (is_gimple_assign (use_stmt))
     933              :                 {
     934         5612 :                   ao_ref lhs_ref;
     935         5612 :                   ao_ref_init (&lhs_ref, gimple_assign_lhs (use_stmt));
     936         5612 :                   if ((earlier_set == ao_ref_alias_set (&lhs_ref)
     937          786 :                        || alias_set_subset_of (ao_ref_alias_set (&lhs_ref),
     938              :                                                earlier_set))
     939         5785 :                       && (earlier_base_set == ao_ref_base_alias_set (&lhs_ref)
     940          472 :                           || alias_set_subset_of
     941          472 :                                (ao_ref_base_alias_set (&lhs_ref),
     942              :                                                   earlier_base_set)))
     943         4928 :                     delete_dead_or_redundant_assignment (&gsi, "redundant",
     944              :                                                          need_eh_cleanup,
     945              :                                                          need_ab_cleanup);
     946              :                 }
     947           43 :               else if (is_gimple_call (use_stmt))
     948              :                 {
     949           43 :                   if ((earlier_set == 0
     950            1 :                        || alias_set_subset_of (0, earlier_set))
     951           43 :                       && (earlier_base_set == 0
     952            0 :                           || alias_set_subset_of (0, earlier_base_set)))
     953           42 :                   delete_dead_or_redundant_call (&gsi, "redundant");
     954              :                 }
     955              :               else
     956            0 :                 gcc_unreachable ();
     957              :             }
     958              :         }
     959      4346123 :     }
     960      4346123 : }
     961              : 
     962              : /* Return whether PHI contains ARG as an argument.  */
     963              : 
     964              : static bool
     965      4310637 : contains_phi_arg (gphi *phi, tree arg)
     966              : {
     967     33105418 :   for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i)
     968     29063816 :     if (gimple_phi_arg_def (phi, i) == arg)
     969              :       return true;
     970              :   return false;
     971              : }
     972              : 
     973              : /* Hash map of the memory use in a GIMPLE assignment to its
     974              :    data reference.  If NULL data-ref analysis isn't used.  */
     975              : static hash_map<gimple *, data_reference_p> *dse_stmt_to_dr_map;
     976              : 
     977              : /* A helper of dse_optimize_stmt.
     978              :    Given a GIMPLE_ASSIGN in STMT that writes to REF, classify it
     979              :    according to downstream uses and defs.  Sets *BY_CLOBBER_P to true
     980              :    if only clobber statements influenced the classification result.
     981              :    Returns the classification.  */
     982              : 
     983              : static dse_store_status
     984     43749084 : dse_classify_store (ao_ref *ref, gimple *stmt,
     985              :                     bool byte_tracking_enabled, sbitmap live_bytes,
     986              :                     bool *by_clobber_p, tree stop_at_vuse, int &cnt,
     987              :                     bitmap visited)
     988              : {
     989     43749084 :   gimple *temp;
     990     43749084 :   std::unique_ptr<data_reference, void(*)(data_reference_p)>
     991     43749084 :     dra (nullptr, free_data_ref);
     992              : 
     993     43749084 :   if (by_clobber_p)
     994     43160910 :     *by_clobber_p = true;
     995              : 
     996              :   /* Find the first dominated statement that clobbers (part of) the
     997              :      memory stmt stores to with no intermediate statement that may use
     998              :      part of the memory stmt stores.  That is, find a store that may
     999              :      prove stmt to be a dead store.  */
    1000     43749084 :   temp = stmt;
    1001    549635782 :   do
    1002              :     {
    1003    296692433 :       gimple *use_stmt;
    1004    296692433 :       imm_use_iterator ui;
    1005    296692433 :       bool fail = false;
    1006    296692433 :       tree defvar;
    1007              : 
    1008    296692433 :       if (gimple_code (temp) == GIMPLE_PHI)
    1009              :         {
    1010     20827187 :           defvar = PHI_RESULT (temp);
    1011     20827187 :           bitmap_set_bit (visited, SSA_NAME_VERSION (defvar));
    1012              :         }
    1013              :       else
    1014    551730492 :         defvar = gimple_vdef (temp);
    1015              : 
    1016    296692433 :       auto_vec<gimple *, 10> defs;
    1017    296692433 :       gphi *first_phi_def = NULL;
    1018    296692433 :       gphi *last_phi_def = NULL;
    1019              : 
    1020    296692433 :       auto_vec<tree, 10> worklist;
    1021    296692433 :       worklist.quick_push (defvar);
    1022              : 
    1023    299566555 :       do
    1024              :         {
    1025    299566555 :           defvar = worklist.pop ();
    1026              :           /* If we're instructed to stop walking at region boundary, do so.  */
    1027    299566555 :           if (defvar == stop_at_vuse)
    1028              :             return DSE_STORE_LIVE;
    1029              : 
    1030    299554421 :           use_operand_p usep;
    1031    643122746 :           FOR_EACH_IMM_USE_FAST (usep, ui, defvar)
    1032              :             {
    1033    373587745 :               use_stmt = USE_STMT (usep);
    1034              : 
    1035              :               /* Limit stmt walking.  */
    1036    373587745 :               if (++cnt > param_dse_max_alias_queries_per_store)
    1037              :                 {
    1038              :                   fail = true;
    1039              :                   break;
    1040              :                 }
    1041              : 
    1042              :               /* In simple cases we can look through PHI nodes, but we
    1043              :                  have to be careful with loops and with memory references
    1044              :                  containing operands that are also operands of PHI nodes.
    1045              :                  See gcc.c-torture/execute/20051110-*.c.  */
    1046    373303843 :               if (gphi *phi = dyn_cast <gphi *> (use_stmt))
    1047              :                 {
    1048              :                   /* Look through single-argument PHIs.  */
    1049     41246204 :                   if (gimple_phi_num_args (phi) == 1)
    1050      3411985 :                     worklist.safe_push (gimple_phi_result (phi));
    1051              :                   else
    1052              :                     {
    1053              :                       /* If we visit this PHI by following a backedge then we
    1054              :                          have to make sure ref->ref only refers to SSA names
    1055              :                          that are invariant with respect to the loop
    1056              :                          represented by this PHI node.  We handle irreducible
    1057              :                          regions by relying on backedge marking and identifying
    1058              :                          the head of the (sub-)region.  */
    1059     37834219 :                       edge e = gimple_phi_arg_edge
    1060     37834219 :                                  (phi, PHI_ARG_INDEX_FROM_USE (usep));
    1061     37834219 :                       if (e->flags & EDGE_DFS_BACK)
    1062              :                         {
    1063      3386869 :                           basic_block rgn_head
    1064      3386869 :                             = nearest_common_dominator (CDI_DOMINATORS,
    1065              :                                                         gimple_bb (phi),
    1066              :                                                         e->src);
    1067      3386869 :                           if (!for_each_index (ref->ref
    1068              :                                                ? &ref->ref : &ref->base,
    1069              :                                                check_name, rgn_head))
    1070      1532018 :                             return DSE_STORE_LIVE;
    1071              :                         }
    1072              :                       /* If we already visited this PHI ignore it for further
    1073              :                          processing.  But note we have to check each incoming
    1074              :                          edge above.  */
    1075     72604402 :                       if (!bitmap_bit_p (visited,
    1076     36302201 :                                          SSA_NAME_VERSION (PHI_RESULT (phi))))
    1077              :                         {
    1078     27026550 :                           defs.safe_push (phi);
    1079     27026550 :                           if (!first_phi_def)
    1080     22910317 :                             first_phi_def = phi;;
    1081              :                           last_phi_def = phi;
    1082              :                         }
    1083              :                     }
    1084              :                 }
    1085              :               /* If the statement is a use the store is not dead.  */
    1086    332057639 :               else if (ref_maybe_used_by_stmt_p (use_stmt, ref))
    1087              :                 {
    1088     28214799 :                   if (dse_stmt_to_dr_map
    1089      6149378 :                       && ref->ref
    1090     34260626 :                       && is_gimple_assign (use_stmt))
    1091              :                     {
    1092      1231978 :                       if (!dra)
    1093      1226789 :                         dra.reset (create_data_ref (NULL, NULL, ref->ref, stmt,
    1094              :                                                     false, false));
    1095      1231978 :                       bool existed_p;
    1096      1231978 :                       data_reference_p &drb
    1097      1231978 :                         = dse_stmt_to_dr_map->get_or_insert (use_stmt,
    1098              :                                                              &existed_p);
    1099      1231978 :                       if (!existed_p)
    1100       744167 :                         drb = create_data_ref (NULL, NULL,
    1101              :                                                gimple_assign_rhs1 (use_stmt),
    1102              :                                                use_stmt, false, false);
    1103      1231978 :                       if (!dr_may_alias_p (dra.get (), drb, NULL))
    1104              :                         {
    1105        17826 :                           if (gimple_vdef (use_stmt))
    1106           16 :                             defs.safe_push (use_stmt);
    1107         8913 :                           continue;
    1108              :                         }
    1109              :                     }
    1110              : 
    1111              :                   /* Handle common cases where we can easily build an ao_ref
    1112              :                      structure for USE_STMT and in doing so we find that the
    1113              :                      references hit non-live bytes and thus can be ignored.
    1114              : 
    1115              :                      TODO: We can also use modref summary to handle calls.  */
    1116     28205886 :                   if (byte_tracking_enabled
    1117     28205886 :                       && is_gimple_assign (use_stmt))
    1118              :                     {
    1119      5148425 :                       ao_ref use_ref;
    1120      5148425 :                       ao_ref_init (&use_ref, gimple_assign_rhs1 (use_stmt));
    1121      5148425 :                       if (valid_ao_ref_for_dse (&use_ref)
    1122      5115784 :                           && operand_equal_p (use_ref.base, ref->base,
    1123              :                                               OEP_ADDRESS_OF)
    1124      8849386 :                           && !live_bytes_read (&use_ref, ref, live_bytes))
    1125              :                         {
    1126              :                           /* If this is a store, remember it as we possibly
    1127              :                              need to walk the defs uses.  */
    1128         4772 :                           if (gimple_vdef (use_stmt))
    1129          452 :                             defs.safe_push (use_stmt);
    1130         2386 :                           continue;
    1131              :                         }
    1132              :                     }
    1133              : 
    1134              :                   fail = true;
    1135              :                   break;
    1136              :                 }
    1137              :               /* We have visited ourselves already so ignore STMT for the
    1138              :                  purpose of chaining.  */
    1139    303842840 :               else if (use_stmt == stmt)
    1140              :                 ;
    1141              :               /* If this is a store, remember it as we possibly need to walk the
    1142              :                  defs uses.  */
    1143    908282823 :               else if (gimple_vdef (use_stmt))
    1144    260947470 :                 defs.safe_push (use_stmt);
    1145      1532018 :             }
    1146              :         }
    1147    596044806 :       while (!fail && !worklist.is_empty ());
    1148              : 
    1149    295148281 :       if (fail)
    1150              :         {
    1151              :           /* STMT might be partially dead and we may be able to reduce
    1152              :              how many memory locations it stores into.  */
    1153     28487402 :           if (byte_tracking_enabled && !gimple_clobber_p (stmt))
    1154     25555010 :             return DSE_STORE_MAYBE_PARTIAL_DEAD;
    1155              :           return DSE_STORE_LIVE;
    1156              :         }
    1157              : 
    1158              :       /* If we didn't find any definition this means the store is dead
    1159              :          if it isn't a store to global reachable memory.  In this case
    1160              :          just pretend the stmt makes itself dead.  Otherwise fail.  */
    1161    266660879 :       if (defs.is_empty ())
    1162              :         {
    1163      2786361 :           if (ref_may_alias_global_p (ref, false))
    1164              :             {
    1165        41373 :               basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (defvar));
    1166              :               /* Assume that BUILT_IN_UNREACHABLE and BUILT_IN_UNREACHABLE_TRAP
    1167              :                  do not need to keep (global) memory side-effects live.
    1168              :                  We do not have virtual operands on BUILT_IN_UNREACHABLE
    1169              :                  but we can do poor mans reachability when the last
    1170              :                  definition we want to elide is in the block that ends
    1171              :                  in such a call.  */
    1172        41373 :               if (EDGE_COUNT (def_bb->succs) == 0)
    1173        56906 :                 if (gcall *last = dyn_cast <gcall *> (*gsi_last_bb (def_bb)))
    1174          601 :                   if (gimple_call_builtin_p (last, BUILT_IN_UNREACHABLE)
    1175          601 :                       || gimple_call_builtin_p (last,
    1176              :                                                 BUILT_IN_UNREACHABLE_TRAP))
    1177              :                     {
    1178          433 :                       if (by_clobber_p)
    1179          433 :                         *by_clobber_p = false;
    1180              :                       return DSE_STORE_DEAD;
    1181              :                     }
    1182              :               return DSE_STORE_LIVE;
    1183              :             }
    1184              : 
    1185      2744988 :           if (by_clobber_p)
    1186      2741392 :             *by_clobber_p = false;
    1187              :           return DSE_STORE_DEAD;
    1188              :         }
    1189              : 
    1190              :       /* Process defs and remove those we need not process further.  */
    1191    546274539 :       for (unsigned i = 0; i < defs.length ();)
    1192              :         {
    1193    282464009 :           gimple *def = defs[i];
    1194    282464009 :           gimple *use_stmt;
    1195    282464009 :           use_operand_p use_p;
    1196    282464009 :           tree vdef = (gimple_code (def) == GIMPLE_PHI
    1197    307282241 :                        ? gimple_phi_result (def) : gimple_vdef (def));
    1198    282464009 :           gphi *phi_def;
    1199              :           /* If the path to check starts with a kill we do not need to
    1200              :              process it further.
    1201              :              ???  With byte tracking we need only kill the bytes currently
    1202              :              live.  */
    1203    282464009 :           if (stmt_kills_ref_p (def, ref))
    1204              :             {
    1205      2688519 :               if (by_clobber_p && !gimple_clobber_p (def))
    1206       669318 :                 *by_clobber_p = false;
    1207      2688519 :               defs.unordered_remove (i);
    1208              :             }
    1209              :           /* If the path ends here we do not need to process it further.
    1210              :              This for example happens with calls to noreturn functions.  */
    1211    279775490 :           else if (has_zero_uses (vdef))
    1212              :             {
    1213              :               /* But if the store is to global memory it is definitely
    1214              :                  not dead.  */
    1215      2961737 :               if (ref_may_alias_global_p (ref, false))
    1216        63988 :                 return DSE_STORE_LIVE;
    1217      2897749 :               defs.unordered_remove (i);
    1218              :             }
    1219              :           /* In addition to kills we can remove defs whose only use
    1220              :              is another def in defs.  That can only ever be PHIs of which
    1221              :              we track two for simplicity reasons, the first and last in
    1222              :              {first,last}_phi_def (we fail for multiple PHIs anyways).
    1223              :              We can also ignore defs that feed only into
    1224              :              already visited PHIs.  */
    1225    276813753 :           else if (single_imm_use (vdef, &use_p, &use_stmt)
    1226    276813753 :                    && (use_stmt == first_phi_def
    1227    239239068 :                        || use_stmt == last_phi_def
    1228    239130730 :                        || (gimple_code (use_stmt) == GIMPLE_PHI
    1229     16057881 :                            && bitmap_bit_p (visited,
    1230     16057881 :                                             SSA_NAME_VERSION
    1231              :                                               (PHI_RESULT (use_stmt))))))
    1232              :             {
    1233      6788806 :               defs.unordered_remove (i);
    1234      6788806 :               if (def == first_phi_def)
    1235              :                 first_phi_def = NULL;
    1236      6048699 :               else if (def == last_phi_def)
    1237       256152 :                 last_phi_def = NULL;
    1238              :             }
    1239              :           /* If def is a PHI and one of its arguments is another PHI node still
    1240              :              in consideration we can defer processing it.  */
    1241    270024947 :           else if ((phi_def = dyn_cast <gphi *> (def))
    1242     23870770 :                    && ((last_phi_def
    1243     23870770 :                         && phi_def != last_phi_def
    1244      2282709 :                         && contains_phi_arg (phi_def,
    1245              :                                              gimple_phi_result (last_phi_def)))
    1246     23728384 :                        || (first_phi_def
    1247     23728384 :                            && phi_def != first_phi_def
    1248      2027928 :                            && contains_phi_arg
    1249      2027928 :                                 (phi_def, gimple_phi_result (first_phi_def)))))
    1250              :             {
    1251       269035 :               defs.unordered_remove (i);
    1252       269035 :               if (phi_def == first_phi_def)
    1253              :                 first_phi_def = NULL;
    1254       186461 :               else if (phi_def == last_phi_def)
    1255       256152 :                 last_phi_def = NULL;
    1256              :             }
    1257              :           else
    1258    269755912 :             ++i;
    1259              :         }
    1260              : 
    1261              :       /* If all defs kill the ref we are done.  */
    1262    307559614 :       if (defs.is_empty ())
    1263              :         return DSE_STORE_DEAD;
    1264              :       /* If more than one def survives we have to analyze multiple
    1265              :          paths.  We can handle this by recursing, sharing 'visited'
    1266              :          to avoid redundant work and limiting it by shared 'cnt'.
    1267              :          For now do not bother with byte-tracking in this case.  */
    1268    264153214 :       while (defs.length () > 1)
    1269              :         {
    1270     11151922 :           if (dse_classify_store (ref, defs.last (), false, NULL,
    1271              :                                   by_clobber_p, stop_at_vuse, cnt,
    1272              :                                   visited) != DSE_STORE_DEAD)
    1273              :             break;
    1274      6934582 :           byte_tracking_enabled = false;
    1275      6934582 :           defs.pop ();
    1276              :         }
    1277              :       /* If more than one def survives fail.  */
    1278    257218632 :       if (defs.length () > 1)
    1279              :         {
    1280              :           /* STMT might be partially dead and we may be able to reduce
    1281              :              how many memory locations it stores into.  */
    1282      4217340 :           if (byte_tracking_enabled && !gimple_clobber_p (stmt))
    1283      1631391 :             return DSE_STORE_MAYBE_PARTIAL_DEAD;
    1284              :           return DSE_STORE_LIVE;
    1285              :         }
    1286    253001292 :       temp = defs[0];
    1287              : 
    1288              :       /* Track partial kills.  */
    1289    253001292 :       if (byte_tracking_enabled)
    1290              :         {
    1291    188266150 :           clear_bytes_written_by (live_bytes, temp, ref);
    1292    188266150 :           if (bitmap_empty_p (live_bytes))
    1293              :             {
    1294        57943 :               if (by_clobber_p && !gimple_clobber_p (temp))
    1295        57766 :                 *by_clobber_p = false;
    1296              :               return DSE_STORE_DEAD;
    1297              :             }
    1298              :         }
    1299    296692433 :     }
    1300              :   /* Continue walking until there are no more live bytes.  */
    1301              :   while (1);
    1302     43749084 : }
    1303              : 
    1304              : dse_store_status
    1305     32597162 : dse_classify_store (ao_ref *ref, gimple *stmt,
    1306              :                     bool byte_tracking_enabled, sbitmap live_bytes,
    1307              :                     bool *by_clobber_p, tree stop_at_vuse)
    1308              : {
    1309     32597162 :   int cnt = 0;
    1310     32597162 :   auto_bitmap visited;
    1311     32597162 :   return dse_classify_store (ref, stmt, byte_tracking_enabled, live_bytes,
    1312     32597162 :                              by_clobber_p, stop_at_vuse, cnt, visited);
    1313     32597162 : }
    1314              : 
    1315              : 
    1316              : /* Delete a dead call at GSI, which is mem* call of some kind.  */
    1317              : static void
    1318         7099 : delete_dead_or_redundant_call (gimple_stmt_iterator *gsi, const char *type)
    1319              : {
    1320         7099 :   gimple *stmt = gsi_stmt (*gsi);
    1321         7099 :   if (dump_file && (dump_flags & TDF_DETAILS))
    1322              :     {
    1323           18 :       fprintf (dump_file, "  Deleted %s call: ", type);
    1324           18 :       print_gimple_stmt (dump_file, stmt, 0, dump_flags);
    1325           18 :       fprintf (dump_file, "\n");
    1326              :     }
    1327              : 
    1328         7099 :   basic_block bb = gimple_bb (stmt);
    1329         7099 :   tree lhs = gimple_call_lhs (stmt);
    1330         7099 :   if (lhs)
    1331              :     {
    1332         1220 :       tree ptr = gimple_call_arg (stmt, 0);
    1333         1220 :       gimple *new_stmt = gimple_build_assign (lhs, ptr);
    1334         1220 :       unlink_stmt_vdef (stmt);
    1335         1220 :       if (gsi_replace (gsi, new_stmt, true))
    1336          396 :         bitmap_set_bit (need_eh_cleanup, bb->index);
    1337              :     }
    1338              :   else
    1339              :     {
    1340              :       /* Then we need to fix the operand of the consuming stmt.  */
    1341         5879 :       unlink_stmt_vdef (stmt);
    1342              : 
    1343              :       /* Remove the dead store.  */
    1344         5879 :       if (gsi_remove (gsi, true))
    1345            3 :         bitmap_set_bit (need_eh_cleanup, bb->index);
    1346         5879 :       release_defs (stmt);
    1347              :     }
    1348         7099 : }
    1349              : 
    1350              : /* Delete a dead store at GSI, which is a gimple assignment. */
    1351              : 
    1352              : void
    1353      2307117 : delete_dead_or_redundant_assignment (gimple_stmt_iterator *gsi,
    1354              :                                      const char *type,
    1355              :                                      bitmap need_eh_cleanup,
    1356              :                                      bitmap need_ab_cleanup)
    1357              : {
    1358      2307117 :   gimple *stmt = gsi_stmt (*gsi);
    1359      2307117 :   if (dump_file && (dump_flags & TDF_DETAILS))
    1360              :     {
    1361          112 :       fprintf (dump_file, "  Deleted %s store: ", type);
    1362          112 :       print_gimple_stmt (dump_file, stmt, 0, dump_flags);
    1363          112 :       fprintf (dump_file, "\n");
    1364              :     }
    1365              : 
    1366              :   /* Then we need to fix the operand of the consuming stmt.  */
    1367      2307117 :   unlink_stmt_vdef (stmt);
    1368              : 
    1369              :   /* Remove the dead store.  */
    1370      2307117 :   basic_block bb = gimple_bb (stmt);
    1371      2307117 :   if (need_ab_cleanup && stmt_can_make_abnormal_goto (stmt))
    1372            5 :     bitmap_set_bit (need_ab_cleanup, bb->index);
    1373      2307117 :   if (gsi_remove (gsi, true) && need_eh_cleanup)
    1374          103 :     bitmap_set_bit (need_eh_cleanup, bb->index);
    1375              : 
    1376              :   /* And release any SSA_NAMEs set in this statement back to the
    1377              :      SSA_NAME manager.  */
    1378      2307117 :   release_defs (stmt);
    1379      2307117 : }
    1380              : 
    1381              : /* Try to prove, using modref summary, that all memory written to by a call is
    1382              :    dead and remove it.  Assume that if return value is written to memory
    1383              :    it is already proved to be dead.  */
    1384              : 
    1385              : static bool
    1386     17937371 : dse_optimize_call (gimple_stmt_iterator *gsi, sbitmap live_bytes)
    1387              : {
    1388     17937371 :   gcall *stmt = dyn_cast <gcall *> (gsi_stmt (*gsi));
    1389              : 
    1390     17743273 :   if (!stmt)
    1391              :     return false;
    1392              : 
    1393     17743273 :   tree callee = gimple_call_fndecl (stmt);
    1394              : 
    1395     17743273 :   if (!callee)
    1396              :     return false;
    1397              : 
    1398              :   /* Pure/const functions are optimized by normal DCE
    1399              :      or handled as store above.  */
    1400     17002391 :   int flags = gimple_call_flags (stmt);
    1401     17002391 :   if ((flags & (ECF_PURE|ECF_CONST|ECF_NOVOPS))
    1402           96 :       && !(flags & (ECF_LOOPING_CONST_OR_PURE)))
    1403              :     return false;
    1404              : 
    1405     17002389 :   cgraph_node *node = cgraph_node::get (callee);
    1406     17002389 :   if (!node)
    1407              :     return false;
    1408              : 
    1409     16991879 :   if ((stmt_could_throw_p (cfun, stmt)
    1410      7469373 :        && !cfun->can_delete_dead_exceptions)
    1411     19724911 :       || ((gimple_call_flags (stmt) & ECF_NORETURN)
    1412      2208297 :           && gimple_call_ctrl_altering_p (stmt)))
    1413              :     return false;
    1414              : 
    1415              :   /* If return value is used the call is not dead.  */
    1416     10047272 :   tree lhs = gimple_call_lhs (stmt);
    1417     10047272 :   if (lhs && TREE_CODE (lhs) == SSA_NAME)
    1418              :     {
    1419      2526639 :       imm_use_iterator ui;
    1420      2526639 :       gimple *use_stmt;
    1421      2720768 :       FOR_EACH_IMM_USE_STMT (use_stmt, ui, lhs)
    1422      2660814 :         if (!is_gimple_debug (use_stmt))
    1423      2526639 :           return false;
    1424              :     }
    1425              : 
    1426              :   /* Verify that there are no side-effects except for return value
    1427              :      and memory writes tracked by modref.  */
    1428      7580587 :   modref_summary *summary = get_modref_function_summary (node);
    1429      7580587 :   if (!summary || !summary->try_dse)
    1430              :     return false;
    1431              : 
    1432        73686 :   bool by_clobber_p = false;
    1433              : 
    1434              :   /* Walk all memory writes and verify that they are dead.  */
    1435       223096 :   for (auto base_node : summary->stores->bases)
    1436       226027 :     for (auto ref_node : base_node->refs)
    1437       231146 :       for (auto access_node : ref_node->accesses)
    1438              :         {
    1439        76067 :           tree arg = access_node.get_call_arg (stmt);
    1440              : 
    1441        76067 :           if (!arg || !POINTER_TYPE_P (TREE_TYPE (arg)))
    1442        72048 :             return false;
    1443              : 
    1444        76066 :           if (integer_zerop (arg)
    1445        76078 :               && !targetm.addr_space.zero_address_valid
    1446           12 :                     (TYPE_ADDR_SPACE (TREE_TYPE (arg))))
    1447           12 :             continue;
    1448              : 
    1449        76054 :           ao_ref ref;
    1450              : 
    1451        76054 :           if (!access_node.get_ao_ref (stmt, &ref))
    1452              :             return false;
    1453        76054 :           ref.ref_alias_set = ref_node->ref;
    1454        76054 :           ref.base_alias_set = base_node->base;
    1455              : 
    1456        76054 :           bool byte_tracking_enabled
    1457        76054 :               = setup_live_bytes_from_ref (&ref, live_bytes);
    1458        76054 :           enum dse_store_status store_status;
    1459              : 
    1460        76054 :           store_status = dse_classify_store (&ref, stmt,
    1461              :                                              byte_tracking_enabled,
    1462              :                                              live_bytes, &by_clobber_p);
    1463        76054 :           if (store_status != DSE_STORE_DEAD)
    1464              :             return false;
    1465              :         }
    1466         1638 :   delete_dead_or_redundant_assignment (gsi, "dead", need_eh_cleanup,
    1467              :                                        need_ab_cleanup);
    1468         1638 :   return true;
    1469              : }
    1470              : 
    1471              : /* Attempt to eliminate dead stores in the statement referenced by BSI.
    1472              : 
    1473              :    A dead store is a store into a memory location which will later be
    1474              :    overwritten by another store without any intervening loads.  In this
    1475              :    case the earlier store can be deleted.
    1476              : 
    1477              :    In our SSA + virtual operand world we use immediate uses of virtual
    1478              :    operands to detect dead stores.  If a store's virtual definition
    1479              :    is used precisely once by a later store to the same location which
    1480              :    post dominates the first store, then the first store is dead.  */
    1481              : 
    1482              : static void
    1483     57855761 : dse_optimize_stmt (function *fun, gimple_stmt_iterator *gsi, sbitmap live_bytes)
    1484              : {
    1485     57855761 :   gimple *stmt = gsi_stmt (*gsi);
    1486              : 
    1487              :   /* Don't return early on *this_2(D) ={v} {CLOBBER}.  */
    1488     57855761 :   if (gimple_has_volatile_ops (stmt)
    1489     57855761 :       && (!gimple_clobber_p (stmt)
    1490      7030586 :           || TREE_CODE (gimple_assign_lhs (stmt)) != MEM_REF))
    1491     55468606 :     return;
    1492              : 
    1493     50403530 :   ao_ref ref;
    1494              :   /* If this is not a store we can still remove dead call using
    1495              :      modref summary.  Note we specifically allow ref to be initialized
    1496              :      to a conservative may-def since we are looking for followup stores
    1497              :      to kill all of it.  */
    1498     50403530 :   if (!initialize_ao_ref_for_dse (stmt, &ref, true))
    1499              :     {
    1500     17892112 :       dse_optimize_call (gsi, live_bytes);
    1501     17892112 :       return;
    1502              :     }
    1503              : 
    1504              :   /* We know we have virtual definitions.  We can handle assignments and
    1505              :      some builtin calls.  */
    1506     32511418 :   if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL)
    1507     32511418 :       && !gimple_call_ctrl_altering_p (stmt))
    1508              :     {
    1509       466799 :       tree fndecl = gimple_call_fndecl (stmt);
    1510       466799 :       switch (DECL_FUNCTION_CODE (fndecl))
    1511              :         {
    1512       464921 :         case BUILT_IN_MEMCPY:
    1513       464921 :         case BUILT_IN_MEMMOVE:
    1514       464921 :         case BUILT_IN_STRNCPY:
    1515       464921 :         case BUILT_IN_MEMSET:
    1516       464921 :         case BUILT_IN_MEMCPY_CHK:
    1517       464921 :         case BUILT_IN_MEMMOVE_CHK:
    1518       464921 :         case BUILT_IN_STRNCPY_CHK:
    1519       464921 :         case BUILT_IN_MEMSET_CHK:
    1520       464921 :           {
    1521              :             /* Occasionally calls with an explicit length of zero
    1522              :                show up in the IL.  It's pointless to do analysis
    1523              :                on them, they're trivially dead.  */
    1524       464921 :             tree size = gimple_call_arg (stmt, 2);
    1525       464921 :             if (integer_zerop (size))
    1526              :               {
    1527           50 :                 delete_dead_or_redundant_call (gsi, "dead");
    1528           50 :                 return;
    1529              :               }
    1530              : 
    1531              :             /* If this is a memset call that initializes an object
    1532              :                to zero, it may be redundant with an earlier memset
    1533              :                or empty CONSTRUCTOR of a larger object.  */
    1534       464871 :             if ((DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMSET
    1535       364515 :                  || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMSET_CHK)
    1536       465174 :                 && integer_zerop (gimple_call_arg (stmt, 1)))
    1537        57238 :               dse_optimize_redundant_stores (stmt);
    1538              : 
    1539       464871 :             enum dse_store_status store_status;
    1540       464871 :             bool byte_tracking_enabled
    1541       464871 :               = setup_live_bytes_from_ref (&ref, live_bytes);
    1542       464871 :             store_status = dse_classify_store (&ref, stmt,
    1543              :                                                byte_tracking_enabled,
    1544              :                                                live_bytes);
    1545       464871 :             if (store_status == DSE_STORE_LIVE)
    1546              :               return;
    1547              : 
    1548       145845 :             if (store_status == DSE_STORE_MAYBE_PARTIAL_DEAD)
    1549              :               {
    1550       138838 :                 maybe_trim_memstar_call (&ref, live_bytes, stmt);
    1551       138838 :                 return;
    1552              :               }
    1553              : 
    1554         7007 :             if (store_status == DSE_STORE_DEAD)
    1555         7007 :               delete_dead_or_redundant_call (gsi, "dead");
    1556              :             return;
    1557              :           }
    1558              : 
    1559         1878 :         case BUILT_IN_CALLOC:
    1560              :           /* We already know the arguments are integer constants.  */
    1561         1878 :           dse_optimize_redundant_stores (stmt);
    1562         1878 :           return;
    1563              : 
    1564              :         default:
    1565              :           return;
    1566              :         }
    1567              :     }
    1568     32044619 :   else if (is_gimple_call (stmt)
    1569     32044619 :            && gimple_call_internal_p (stmt))
    1570              :     {
    1571       152056 :       switch (gimple_call_internal_fn (stmt))
    1572              :         {
    1573         1271 :         case IFN_LEN_STORE:
    1574         1271 :         case IFN_MASK_STORE:
    1575         1271 :         case IFN_MASK_LEN_STORE:
    1576         1271 :           {
    1577         1271 :             enum dse_store_status store_status;
    1578         1271 :             store_status = dse_classify_store (&ref, stmt, false, live_bytes);
    1579         1271 :             if (store_status == DSE_STORE_DEAD)
    1580            0 :               delete_dead_or_redundant_call (gsi, "dead");
    1581              :             return;
    1582              :           }
    1583              :         default:;
    1584              :         }
    1585              :     }
    1586              : 
    1587     32043348 :   bool by_clobber_p = false;
    1588              : 
    1589              :   /* Check if this statement stores zero to a memory location,
    1590              :      and if there is a subsequent store of zero to the same
    1591              :      memory location.  If so, remove the subsequent store.  */
    1592     32043348 :   if (gimple_assign_single_p (stmt)
    1593     32043348 :       && initializer_zerop (gimple_assign_rhs1 (stmt)))
    1594      4287007 :     dse_optimize_redundant_stores (stmt);
    1595              : 
    1596              :   /* Self-assignments are zombies.  */
    1597     32043348 :   if (is_gimple_assign (stmt)
    1598     62591285 :       && operand_equal_p (gimple_assign_rhs1 (stmt),
    1599     30547937 :                           gimple_assign_lhs (stmt), 0))
    1600              :     ;
    1601              :   else
    1602              :     {
    1603     32041922 :       bool byte_tracking_enabled
    1604     32041922 :           = setup_live_bytes_from_ref (&ref, live_bytes);
    1605     32041922 :       enum dse_store_status store_status;
    1606     32041922 :       store_status = dse_classify_store (&ref, stmt,
    1607              :                                          byte_tracking_enabled,
    1608              :                                          live_bytes, &by_clobber_p);
    1609     32041922 :       if (store_status == DSE_STORE_LIVE)
    1610              :         return;
    1611              : 
    1612     29428263 :       if (store_status == DSE_STORE_MAYBE_PARTIAL_DEAD)
    1613              :         {
    1614     26978867 :           maybe_trim_partially_dead_store (&ref, live_bytes, stmt);
    1615     26978867 :           return;
    1616              :         }
    1617              :     }
    1618              : 
    1619              :   /* Now we know that use_stmt kills the LHS of stmt.  */
    1620              : 
    1621              :   /* But only remove *this_2(D) ={v} {CLOBBER} if killed by
    1622              :      another clobber stmt.  */
    1623      2450822 :   if (gimple_clobber_p (stmt)
    1624      2450822 :       && !by_clobber_p)
    1625              :     return;
    1626              : 
    1627      2395619 :   if (is_gimple_call (stmt)
    1628      2395619 :       && (gimple_has_side_effects (stmt)
    1629        55449 :           || (stmt_could_throw_p (fun, stmt)
    1630            5 :               && !fun->can_delete_dead_exceptions)))
    1631              :     {
    1632              :       /* See if we can remove complete call.  */
    1633        45259 :       if (dse_optimize_call (gsi, live_bytes))
    1634              :         return;
    1635              :       /* Make sure we do not remove a return slot we cannot reconstruct
    1636              :          later.  */
    1637        45241 :       if (gimple_call_return_slot_opt_p (as_a <gcall *>(stmt))
    1638        45241 :           && (TREE_ADDRESSABLE (TREE_TYPE (gimple_call_fntype (stmt)))
    1639        14871 :               || !poly_int_tree_p
    1640        14871 :                     (TYPE_SIZE (TREE_TYPE (gimple_call_fntype (stmt))))))
    1641              :         return;
    1642        36795 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1643              :         {
    1644            1 :           fprintf (dump_file, "  Deleted dead store in call LHS: ");
    1645            1 :           print_gimple_stmt (dump_file, stmt, 0, dump_flags);
    1646            1 :           fprintf (dump_file, "\n");
    1647              :         }
    1648        36795 :       gimple_call_set_lhs (stmt, NULL_TREE);
    1649        36795 :       update_stmt (stmt);
    1650              :     }
    1651      2350360 :   else if (!stmt_could_throw_p (fun, stmt)
    1652      2350360 :            || fun->can_delete_dead_exceptions)
    1653      2300281 :     delete_dead_or_redundant_assignment (gsi, "dead", need_eh_cleanup,
    1654              :                                          need_ab_cleanup);
    1655              : }
    1656              : 
    1657              : namespace {
    1658              : 
    1659              : const pass_data pass_data_dse =
    1660              : {
    1661              :   GIMPLE_PASS, /* type */
    1662              :   "dse", /* name */
    1663              :   OPTGROUP_NONE, /* optinfo_flags */
    1664              :   TV_TREE_DSE, /* tv_id */
    1665              :   ( PROP_cfg | PROP_ssa ), /* properties_required */
    1666              :   0, /* properties_provided */
    1667              :   0, /* properties_destroyed */
    1668              :   0, /* todo_flags_start */
    1669              :   0, /* todo_flags_finish */
    1670              : };
    1671              : 
    1672              : class pass_dse : public gimple_opt_pass
    1673              : {
    1674              : public:
    1675      1485900 :   pass_dse (gcc::context *ctxt)
    1676      2971800 :     : gimple_opt_pass (pass_data_dse, ctxt), use_dr_analysis_p (false)
    1677              :   {}
    1678              : 
    1679              :   /* opt_pass methods: */
    1680      1188720 :   opt_pass * clone () final override { return new pass_dse (m_ctxt); }
    1681       297180 :   void set_pass_param (unsigned n, bool param) final override
    1682              :     {
    1683       297180 :       gcc_assert (n == 0);
    1684       297180 :       use_dr_analysis_p = param;
    1685       297180 :     }
    1686      5747194 :   bool gate (function *) final override { return flag_tree_dse != 0; }
    1687              :   unsigned int execute (function *) final override;
    1688              : 
    1689              : private:
    1690              :   bool use_dr_analysis_p;
    1691              : }; // class pass_dse
    1692              : 
    1693              : unsigned int
    1694      5722492 : pass_dse::execute (function *fun)
    1695              : {
    1696      5722492 :   unsigned todo = 0;
    1697      5722492 :   bool released_def = false;
    1698              : 
    1699      5722492 :   need_eh_cleanup = BITMAP_ALLOC (NULL);
    1700      5722492 :   need_ab_cleanup = BITMAP_ALLOC (NULL);
    1701      5722492 :   auto_sbitmap live_bytes (param_dse_max_object_size);
    1702      5722492 :   if (flag_expensive_optimizations && use_dr_analysis_p)
    1703       978196 :     dse_stmt_to_dr_map = new hash_map<gimple *, data_reference_p>;
    1704              : 
    1705      5722492 :   renumber_gimple_stmt_uids (fun);
    1706              : 
    1707      5722492 :   calculate_dominance_info (CDI_DOMINATORS);
    1708              : 
    1709              :   /* Dead store elimination is fundamentally a reverse program order walk.  */
    1710      5722492 :   int *rpo = XNEWVEC (int, n_basic_blocks_for_fn (fun) - NUM_FIXED_BLOCKS);
    1711      5722492 :   auto_bitmap exit_bbs;
    1712      5722492 :   bitmap_set_bit (exit_bbs, EXIT_BLOCK);
    1713      5722492 :   edge entry = single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (fun));
    1714      5722492 :   int n = rev_post_order_and_mark_dfs_back_seme (fun, entry,
    1715              :                                                  exit_bbs, false, rpo, NULL);
    1716     60240691 :   for (int i = n; i != 0; --i)
    1717              :     {
    1718     48795707 :       basic_block bb = BASIC_BLOCK_FOR_FN (fun, rpo[i-1]);
    1719     48795707 :       gimple_stmt_iterator gsi;
    1720              : 
    1721    458858364 :       for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi);)
    1722              :         {
    1723    361266950 :           gimple *stmt = gsi_stmt (gsi);
    1724              : 
    1725    491515842 :           if (gimple_vdef (stmt))
    1726     57855761 :             dse_optimize_stmt (fun, &gsi, live_bytes);
    1727    606822378 :           else if (def_operand_p
    1728    303411189 :                      def_p = single_ssa_def_operand (stmt, SSA_OP_DEF))
    1729              :             {
    1730              :               /* When we remove dead stores make sure to also delete trivially
    1731              :                  dead SSA defs.  */
    1732     66145105 :               if (has_zero_uses (DEF_FROM_PTR (def_p))
    1733      2171323 :                   && !gimple_has_side_effects (stmt)
    1734      2161006 :                   && !is_ctrl_altering_stmt (stmt)
    1735     68304449 :                   && (!stmt_could_throw_p (fun, stmt)
    1736        89682 :                       || fun->can_delete_dead_exceptions))
    1737              :                 {
    1738      2069764 :                   if (dump_file && (dump_flags & TDF_DETAILS))
    1739              :                     {
    1740           11 :                       fprintf (dump_file, "  Deleted trivially dead stmt: ");
    1741           11 :                       print_gimple_stmt (dump_file, stmt, 0, dump_flags);
    1742           11 :                       fprintf (dump_file, "\n");
    1743              :                     }
    1744      2069764 :                   if (gsi_remove (&gsi, true) && need_eh_cleanup)
    1745            2 :                     bitmap_set_bit (need_eh_cleanup, bb->index);
    1746      2069764 :                   release_defs (stmt);
    1747      2069764 :                   released_def = true;
    1748              :                 }
    1749              :             }
    1750    361266950 :           if (gsi_end_p (gsi))
    1751       600264 :             gsi = gsi_last_bb (bb);
    1752              :           else
    1753    404693751 :             gsi_prev (&gsi);
    1754              :         }
    1755     48795707 :       bool removed_phi = false;
    1756     67357204 :       for (gphi_iterator si = gsi_start_phis (bb); !gsi_end_p (si);)
    1757              :         {
    1758     18561497 :           gphi *phi = si.phi ();
    1759     18561497 :           if (has_zero_uses (gimple_phi_result (phi)))
    1760              :             {
    1761       231288 :               if (dump_file && (dump_flags & TDF_DETAILS))
    1762              :                 {
    1763            0 :                   fprintf (dump_file, "  Deleted trivially dead PHI: ");
    1764            0 :                   print_gimple_stmt (dump_file, phi, 0, dump_flags);
    1765            0 :                   fprintf (dump_file, "\n");
    1766              :                 }
    1767       231288 :               remove_phi_node (&si, true);
    1768       231288 :               removed_phi = true;
    1769       231288 :               released_def = true;
    1770              :             }
    1771              :           else
    1772     18330209 :             gsi_next (&si);
    1773              :         }
    1774     48795707 :       if (removed_phi && gimple_seq_empty_p (phi_nodes (bb)))
    1775              :         todo |= TODO_cleanup_cfg;
    1776              :     }
    1777      5722492 :   free (rpo);
    1778              : 
    1779              :   /* Removal of stores may make some EH edges dead.  Purge such edges from
    1780              :      the CFG as needed.  */
    1781      5722492 :   if (!bitmap_empty_p (need_eh_cleanup))
    1782              :     {
    1783          401 :       gimple_purge_all_dead_eh_edges (need_eh_cleanup);
    1784          401 :       todo |= TODO_cleanup_cfg;
    1785              :     }
    1786      5722492 :   if (!bitmap_empty_p (need_ab_cleanup))
    1787              :     {
    1788            4 :       gimple_purge_all_dead_abnormal_call_edges (need_ab_cleanup);
    1789            4 :       todo |= TODO_cleanup_cfg;
    1790              :     }
    1791              : 
    1792      5722492 :   BITMAP_FREE (need_eh_cleanup);
    1793      5722492 :   BITMAP_FREE (need_ab_cleanup);
    1794              : 
    1795      5722492 :   if (released_def)
    1796       610031 :     free_numbers_of_iterations_estimates (fun);
    1797              : 
    1798      5722492 :   if (flag_expensive_optimizations && use_dr_analysis_p)
    1799              :     {
    1800      1722363 :       for (auto i = dse_stmt_to_dr_map->begin ();
    1801      1722363 :            i != dse_stmt_to_dr_map->end (); ++i)
    1802       744167 :         free_data_ref ((*i).second);
    1803      1956392 :       delete dse_stmt_to_dr_map;
    1804       978196 :       dse_stmt_to_dr_map = NULL;
    1805              :     }
    1806              : 
    1807      5722492 :   return todo;
    1808      5722492 : }
    1809              : 
    1810              : } // anon namespace
    1811              : 
    1812              : gimple_opt_pass *
    1813       297180 : make_pass_dse (gcc::context *ctxt)
    1814              : {
    1815       297180 :   return new pass_dse (ctxt);
    1816              : }
        

Generated by: LCOV version 2.5.0-beta

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto,rust,m2 --enable-host-shared. GCC test suite is run with the built compiler.