LCOV - code coverage report
Current view: top level - gcc - dse.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 1218 1421 85.7 %
Date: 2020-04-04 11:58:09 Functions: 50 60 83.3 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* RTL dead store elimination.
       2                 :            :    Copyright (C) 2005-2020 Free Software Foundation, Inc.
       3                 :            : 
       4                 :            :    Contributed by Richard Sandiford <rsandifor@codesourcery.com>
       5                 :            :    and Kenneth Zadeck <zadeck@naturalbridge.com>
       6                 :            : 
       7                 :            : This file is part of GCC.
       8                 :            : 
       9                 :            : GCC is free software; you can redistribute it and/or modify it under
      10                 :            : the terms of the GNU General Public License as published by the Free
      11                 :            : Software Foundation; either version 3, or (at your option) any later
      12                 :            : version.
      13                 :            : 
      14                 :            : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
      15                 :            : WARRANTY; without even the implied warranty of MERCHANTABILITY or
      16                 :            : FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
      17                 :            : for more details.
      18                 :            : 
      19                 :            : You should have received a copy of the GNU General Public License
      20                 :            : along with GCC; see the file COPYING3.  If not see
      21                 :            : <http://www.gnu.org/licenses/>.  */
      22                 :            : 
      23                 :            : #undef BASELINE
      24                 :            : 
      25                 :            : #include "config.h"
      26                 :            : #include "system.h"
      27                 :            : #include "coretypes.h"
      28                 :            : #include "backend.h"
      29                 :            : #include "target.h"
      30                 :            : #include "rtl.h"
      31                 :            : #include "tree.h"
      32                 :            : #include "gimple.h"
      33                 :            : #include "predict.h"
      34                 :            : #include "df.h"
      35                 :            : #include "memmodel.h"
      36                 :            : #include "tm_p.h"
      37                 :            : #include "gimple-ssa.h"
      38                 :            : #include "expmed.h"
      39                 :            : #include "optabs.h"
      40                 :            : #include "emit-rtl.h"
      41                 :            : #include "recog.h"
      42                 :            : #include "alias.h"
      43                 :            : #include "stor-layout.h"
      44                 :            : #include "cfgrtl.h"
      45                 :            : #include "cselib.h"
      46                 :            : #include "tree-pass.h"
      47                 :            : #include "explow.h"
      48                 :            : #include "expr.h"
      49                 :            : #include "dbgcnt.h"
      50                 :            : #include "rtl-iter.h"
      51                 :            : #include "cfgcleanup.h"
      52                 :            : #include "calls.h"
      53                 :            : 
      54                 :            : /* This file contains three techniques for performing Dead Store
      55                 :            :    Elimination (dse).
      56                 :            : 
      57                 :            :    * The first technique performs dse locally on any base address.  It
      58                 :            :    is based on the cselib which is a local value numbering technique.
      59                 :            :    This technique is local to a basic block but deals with a fairly
      60                 :            :    general addresses.
      61                 :            : 
      62                 :            :    * The second technique performs dse globally but is restricted to
      63                 :            :    base addresses that are either constant or are relative to the
      64                 :            :    frame_pointer.
      65                 :            : 
      66                 :            :    * The third technique, (which is only done after register allocation)
      67                 :            :    processes the spill slots.  This differs from the second
      68                 :            :    technique because it takes advantage of the fact that spilling is
      69                 :            :    completely free from the effects of aliasing.
      70                 :            : 
      71                 :            :    Logically, dse is a backwards dataflow problem.  A store can be
      72                 :            :    deleted if it if cannot be reached in the backward direction by any
      73                 :            :    use of the value being stored.  However, the local technique uses a
      74                 :            :    forwards scan of the basic block because cselib requires that the
      75                 :            :    block be processed in that order.
      76                 :            : 
      77                 :            :    The pass is logically broken into 7 steps:
      78                 :            : 
      79                 :            :    0) Initialization.
      80                 :            : 
      81                 :            :    1) The local algorithm, as well as scanning the insns for the two
      82                 :            :    global algorithms.
      83                 :            : 
      84                 :            :    2) Analysis to see if the global algs are necessary.  In the case
      85                 :            :    of stores base on a constant address, there must be at least two
      86                 :            :    stores to that address, to make it possible to delete some of the
      87                 :            :    stores.  In the case of stores off of the frame or spill related
      88                 :            :    stores, only one store to an address is necessary because those
      89                 :            :    stores die at the end of the function.
      90                 :            : 
      91                 :            :    3) Set up the global dataflow equations based on processing the
      92                 :            :    info parsed in the first step.
      93                 :            : 
      94                 :            :    4) Solve the dataflow equations.
      95                 :            : 
      96                 :            :    5) Delete the insns that the global analysis has indicated are
      97                 :            :    unnecessary.
      98                 :            : 
      99                 :            :    6) Delete insns that store the same value as preceding store
     100                 :            :    where the earlier store couldn't be eliminated.
     101                 :            : 
     102                 :            :    7) Cleanup.
     103                 :            : 
     104                 :            :    This step uses cselib and canon_rtx to build the largest expression
     105                 :            :    possible for each address.  This pass is a forwards pass through
     106                 :            :    each basic block.  From the point of view of the global technique,
     107                 :            :    the first pass could examine a block in either direction.  The
     108                 :            :    forwards ordering is to accommodate cselib.
     109                 :            : 
     110                 :            :    We make a simplifying assumption: addresses fall into four broad
     111                 :            :    categories:
     112                 :            : 
     113                 :            :    1) base has rtx_varies_p == false, offset is constant.
     114                 :            :    2) base has rtx_varies_p == false, offset variable.
     115                 :            :    3) base has rtx_varies_p == true, offset constant.
     116                 :            :    4) base has rtx_varies_p == true, offset variable.
     117                 :            : 
     118                 :            :    The local passes are able to process all 4 kinds of addresses.  The
     119                 :            :    global pass only handles 1).
     120                 :            : 
     121                 :            :    The global problem is formulated as follows:
     122                 :            : 
     123                 :            :      A store, S1, to address A, where A is not relative to the stack
     124                 :            :      frame, can be eliminated if all paths from S1 to the end of the
     125                 :            :      function contain another store to A before a read to A.
     126                 :            : 
     127                 :            :      If the address A is relative to the stack frame, a store S2 to A
     128                 :            :      can be eliminated if there are no paths from S2 that reach the
     129                 :            :      end of the function that read A before another store to A.  In
     130                 :            :      this case S2 can be deleted if there are paths from S2 to the
     131                 :            :      end of the function that have no reads or writes to A.  This
     132                 :            :      second case allows stores to the stack frame to be deleted that
     133                 :            :      would otherwise die when the function returns.  This cannot be
     134                 :            :      done if stores_off_frame_dead_at_return is not true.  See the doc
     135                 :            :      for that variable for when this variable is false.
     136                 :            : 
     137                 :            :      The global problem is formulated as a backwards set union
     138                 :            :      dataflow problem where the stores are the gens and reads are the
     139                 :            :      kills.  Set union problems are rare and require some special
     140                 :            :      handling given our representation of bitmaps.  A straightforward
     141                 :            :      implementation requires a lot of bitmaps filled with 1s.
     142                 :            :      These are expensive and cumbersome in our bitmap formulation so
     143                 :            :      care has been taken to avoid large vectors filled with 1s.  See
     144                 :            :      the comments in bb_info and in the dataflow confluence functions
     145                 :            :      for details.
     146                 :            : 
     147                 :            :    There are two places for further enhancements to this algorithm:
     148                 :            : 
     149                 :            :    1) The original dse which was embedded in a pass called flow also
     150                 :            :    did local address forwarding.  For example in
     151                 :            : 
     152                 :            :    A <- r100
     153                 :            :    ... <- A
     154                 :            : 
     155                 :            :    flow would replace the right hand side of the second insn with a
     156                 :            :    reference to r100.  Most of the information is available to add this
     157                 :            :    to this pass.  It has not done it because it is a lot of work in
     158                 :            :    the case that either r100 is assigned to between the first and
     159                 :            :    second insn and/or the second insn is a load of part of the value
     160                 :            :    stored by the first insn.
     161                 :            : 
     162                 :            :    insn 5 in gcc.c-torture/compile/990203-1.c simple case.
     163                 :            :    insn 15 in gcc.c-torture/execute/20001017-2.c simple case.
     164                 :            :    insn 25 in gcc.c-torture/execute/20001026-1.c simple case.
     165                 :            :    insn 44 in gcc.c-torture/execute/20010910-1.c simple case.
     166                 :            : 
     167                 :            :    2) The cleaning up of spill code is quite profitable.  It currently
     168                 :            :    depends on reading tea leaves and chicken entrails left by reload.
     169                 :            :    This pass depends on reload creating a singleton alias set for each
     170                 :            :    spill slot and telling the next dse pass which of these alias sets
     171                 :            :    are the singletons.  Rather than analyze the addresses of the
     172                 :            :    spills, dse's spill processing just does analysis of the loads and
     173                 :            :    stores that use those alias sets.  There are three cases where this
     174                 :            :    falls short:
     175                 :            : 
     176                 :            :      a) Reload sometimes creates the slot for one mode of access, and
     177                 :            :      then inserts loads and/or stores for a smaller mode.  In this
     178                 :            :      case, the current code just punts on the slot.  The proper thing
     179                 :            :      to do is to back out and use one bit vector position for each
     180                 :            :      byte of the entity associated with the slot.  This depends on
     181                 :            :      KNOWING that reload always generates the accesses for each of the
     182                 :            :      bytes in some canonical (read that easy to understand several
     183                 :            :      passes after reload happens) way.
     184                 :            : 
     185                 :            :      b) Reload sometimes decides that spill slot it allocated was not
     186                 :            :      large enough for the mode and goes back and allocates more slots
     187                 :            :      with the same mode and alias set.  The backout in this case is a
     188                 :            :      little more graceful than (a).  In this case the slot is unmarked
     189                 :            :      as being a spill slot and if final address comes out to be based
     190                 :            :      off the frame pointer, the global algorithm handles this slot.
     191                 :            : 
     192                 :            :      c) For any pass that may prespill, there is currently no
     193                 :            :      mechanism to tell the dse pass that the slot being used has the
     194                 :            :      special properties that reload uses.  It may be that all that is
     195                 :            :      required is to have those passes make the same calls that reload
     196                 :            :      does, assuming that the alias sets can be manipulated in the same
     197                 :            :      way.  */
     198                 :            : 
     199                 :            : /* There are limits to the size of constant offsets we model for the
     200                 :            :    global problem.  There are certainly test cases, that exceed this
     201                 :            :    limit, however, it is unlikely that there are important programs
     202                 :            :    that really have constant offsets this size.  */
     203                 :            : #define MAX_OFFSET (64 * 1024)
     204                 :            : 
     205                 :            : /* Obstack for the DSE dataflow bitmaps.  We don't want to put these
     206                 :            :    on the default obstack because these bitmaps can grow quite large
     207                 :            :    (~2GB for the small (!) test case of PR54146) and we'll hold on to
     208                 :            :    all that memory until the end of the compiler run.
     209                 :            :    As a bonus, delete_tree_live_info can destroy all the bitmaps by just
     210                 :            :    releasing the whole obstack.  */
     211                 :            : static bitmap_obstack dse_bitmap_obstack;
     212                 :            : 
     213                 :            : /* Obstack for other data.  As for above: Kinda nice to be able to
     214                 :            :    throw it all away at the end in one big sweep.  */
     215                 :            : static struct obstack dse_obstack;
     216                 :            : 
     217                 :            : /* Scratch bitmap for cselib's cselib_expand_value_rtx.  */
     218                 :            : static bitmap scratch = NULL;
     219                 :            : 
     220                 :            : struct insn_info_type;
     221                 :            : 
     222                 :            : /* This structure holds information about a candidate store.  */
     223                 :   15490000 : class store_info
     224                 :            : {
     225                 :            : public:
     226                 :            : 
     227                 :            :   /* False means this is a clobber.  */
     228                 :            :   bool is_set;
     229                 :            : 
     230                 :            :   /* False if a single HOST_WIDE_INT bitmap is used for positions_needed.  */
     231                 :            :   bool is_large;
     232                 :            : 
     233                 :            :   /* The id of the mem group of the base address.  If rtx_varies_p is
     234                 :            :      true, this is -1.  Otherwise, it is the index into the group
     235                 :            :      table.  */
     236                 :            :   int group_id;
     237                 :            : 
     238                 :            :   /* This is the cselib value.  */
     239                 :            :   cselib_val *cse_base;
     240                 :            : 
     241                 :            :   /* This canonized mem.  */
     242                 :            :   rtx mem;
     243                 :            : 
     244                 :            :   /* Canonized MEM address for use by canon_true_dependence.  */
     245                 :            :   rtx mem_addr;
     246                 :            : 
     247                 :            :   /* The offset of the first byte associated with the operation.  */
     248                 :            :   poly_int64 offset;
     249                 :            : 
     250                 :            :   /* The number of bytes covered by the operation.  This is always exact
     251                 :            :      and known (rather than -1).  */
     252                 :            :   poly_int64 width;
     253                 :            : 
     254                 :            :   union
     255                 :            :     {
     256                 :            :       /* A bitmask as wide as the number of bytes in the word that
     257                 :            :          contains a 1 if the byte may be needed.  The store is unused if
     258                 :            :          all of the bits are 0.  This is used if IS_LARGE is false.  */
     259                 :            :       unsigned HOST_WIDE_INT small_bitmask;
     260                 :            : 
     261                 :            :       struct
     262                 :            :         {
     263                 :            :           /* A bitmap with one bit per byte, or null if the number of
     264                 :            :              bytes isn't known at compile time.  A cleared bit means
     265                 :            :              the position is needed.  Used if IS_LARGE is true.  */
     266                 :            :           bitmap bmap;
     267                 :            : 
     268                 :            :           /* When BITMAP is nonnull, this counts the number of set bits
     269                 :            :              (i.e. unneeded bytes) in the bitmap.  If it is equal to
     270                 :            :              WIDTH, the whole store is unused.
     271                 :            : 
     272                 :            :              When BITMAP is null:
     273                 :            :              - the store is definitely not needed when COUNT == 1
     274                 :            :              - all the store is needed when COUNT == 0 and RHS is nonnull
     275                 :            :              - otherwise we don't know which parts of the store are needed.  */
     276                 :            :           int count;
     277                 :            :         } large;
     278                 :            :     } positions_needed;
     279                 :            : 
     280                 :            :   /* The next store info for this insn.  */
     281                 :            :   class store_info *next;
     282                 :            : 
     283                 :            :   /* The right hand side of the store.  This is used if there is a
     284                 :            :      subsequent reload of the mems address somewhere later in the
     285                 :            :      basic block.  */
     286                 :            :   rtx rhs;
     287                 :            : 
     288                 :            :   /* If rhs is or holds a constant, this contains that constant,
     289                 :            :      otherwise NULL.  */
     290                 :            :   rtx const_rhs;
     291                 :            : 
     292                 :            :   /* Set if this store stores the same constant value as REDUNDANT_REASON
     293                 :            :      insn stored.  These aren't eliminated early, because doing that
     294                 :            :      might prevent the earlier larger store to be eliminated.  */
     295                 :            :   struct insn_info_type *redundant_reason;
     296                 :            : };
     297                 :            : 
     298                 :            : /* Return a bitmask with the first N low bits set.  */
     299                 :            : 
     300                 :            : static unsigned HOST_WIDE_INT
     301                 :   15596200 : lowpart_bitmask (int n)
     302                 :            : {
     303                 :   15596200 :   unsigned HOST_WIDE_INT mask = HOST_WIDE_INT_M1U;
     304                 :   15596200 :   return mask >> (HOST_BITS_PER_WIDE_INT - n);
     305                 :            : }
     306                 :            : 
     307                 :            : static object_allocator<store_info> cse_store_info_pool ("cse_store_info_pool");
     308                 :            : 
     309                 :            : static object_allocator<store_info> rtx_store_info_pool ("rtx_store_info_pool");
     310                 :            : 
     311                 :            : /* This structure holds information about a load.  These are only
     312                 :            :    built for rtx bases.  */
     313                 :   18532000 : class read_info_type
     314                 :            : {
     315                 :            : public:
     316                 :            :   /* The id of the mem group of the base address.  */
     317                 :            :   int group_id;
     318                 :            : 
     319                 :            :   /* The offset of the first byte associated with the operation.  */
     320                 :            :   poly_int64 offset;
     321                 :            : 
     322                 :            :   /* The number of bytes covered by the operation, or -1 if not known.  */
     323                 :            :   poly_int64 width;
     324                 :            : 
     325                 :            :   /* The mem being read.  */
     326                 :            :   rtx mem;
     327                 :            : 
     328                 :            :   /* The next read_info for this insn.  */
     329                 :            :   class read_info_type *next;
     330                 :            : };
     331                 :            : typedef class read_info_type *read_info_t;
     332                 :            : 
     333                 :            : static object_allocator<read_info_type> read_info_type_pool ("read_info_pool");
     334                 :            : 
     335                 :            : /* One of these records is created for each insn.  */
     336                 :            : 
     337                 :            : struct insn_info_type
     338                 :            : {
     339                 :            :   /* Set true if the insn contains a store but the insn itself cannot
     340                 :            :      be deleted.  This is set if the insn is a parallel and there is
     341                 :            :      more than one non dead output or if the insn is in some way
     342                 :            :      volatile.  */
     343                 :            :   bool cannot_delete;
     344                 :            : 
     345                 :            :   /* This field is only used by the global algorithm.  It is set true
     346                 :            :      if the insn contains any read of mem except for a (1).  This is
     347                 :            :      also set if the insn is a call or has a clobber mem.  If the insn
     348                 :            :      contains a wild read, the use_rec will be null.  */
     349                 :            :   bool wild_read;
     350                 :            : 
     351                 :            :   /* This is true only for CALL instructions which could potentially read
     352                 :            :      any non-frame memory location. This field is used by the global
     353                 :            :      algorithm.  */
     354                 :            :   bool non_frame_wild_read;
     355                 :            : 
     356                 :            :   /* This field is only used for the processing of const functions.
     357                 :            :      These functions cannot read memory, but they can read the stack
     358                 :            :      because that is where they may get their parms.  We need to be
     359                 :            :      this conservative because, like the store motion pass, we don't
     360                 :            :      consider CALL_INSN_FUNCTION_USAGE when processing call insns.
     361                 :            :      Moreover, we need to distinguish two cases:
     362                 :            :      1. Before reload (register elimination), the stores related to
     363                 :            :         outgoing arguments are stack pointer based and thus deemed
     364                 :            :         of non-constant base in this pass.  This requires special
     365                 :            :         handling but also means that the frame pointer based stores
     366                 :            :         need not be killed upon encountering a const function call.
     367                 :            :      2. After reload, the stores related to outgoing arguments can be
     368                 :            :         either stack pointer or hard frame pointer based.  This means
     369                 :            :         that we have no other choice than also killing all the frame
     370                 :            :         pointer based stores upon encountering a const function call.
     371                 :            :      This field is set after reload for const function calls and before
     372                 :            :      reload for const tail function calls on targets where arg pointer
     373                 :            :      is the frame pointer.  Having this set is less severe than a wild
     374                 :            :      read, it just means that all the frame related stores are killed
     375                 :            :      rather than all the stores.  */
     376                 :            :   bool frame_read;
     377                 :            : 
     378                 :            :   /* This field is only used for the processing of const functions.
     379                 :            :      It is set if the insn may contain a stack pointer based store.  */
     380                 :            :   bool stack_pointer_based;
     381                 :            : 
     382                 :            :   /* This is true if any of the sets within the store contains a
     383                 :            :      cselib base.  Such stores can only be deleted by the local
     384                 :            :      algorithm.  */
     385                 :            :   bool contains_cselib_groups;
     386                 :            : 
     387                 :            :   /* The insn. */
     388                 :            :   rtx_insn *insn;
     389                 :            : 
     390                 :            :   /* The list of mem sets or mem clobbers that are contained in this
     391                 :            :      insn.  If the insn is deletable, it contains only one mem set.
     392                 :            :      But it could also contain clobbers.  Insns that contain more than
     393                 :            :      one mem set are not deletable, but each of those mems are here in
     394                 :            :      order to provide info to delete other insns.  */
     395                 :            :   store_info *store_rec;
     396                 :            : 
     397                 :            :   /* The linked list of mem uses in this insn.  Only the reads from
     398                 :            :      rtx bases are listed here.  The reads to cselib bases are
     399                 :            :      completely processed during the first scan and so are never
     400                 :            :      created.  */
     401                 :            :   read_info_t read_rec;
     402                 :            : 
     403                 :            :   /* The live fixed registers.  We assume only fixed registers can
     404                 :            :      cause trouble by being clobbered from an expanded pattern;
     405                 :            :      storing only the live fixed registers (rather than all registers)
     406                 :            :      means less memory needs to be allocated / copied for the individual
     407                 :            :      stores.  */
     408                 :            :   regset fixed_regs_live;
     409                 :            : 
     410                 :            :   /* The prev insn in the basic block.  */
     411                 :            :   struct insn_info_type * prev_insn;
     412                 :            : 
     413                 :            :   /* The linked list of insns that are in consideration for removal in
     414                 :            :      the forwards pass through the basic block.  This pointer may be
     415                 :            :      trash as it is not cleared when a wild read occurs.  The only
     416                 :            :      time it is guaranteed to be correct is when the traversal starts
     417                 :            :      at active_local_stores.  */
     418                 :            :   struct insn_info_type * next_local_store;
     419                 :            : };
     420                 :            : typedef struct insn_info_type *insn_info_t;
     421                 :            : 
     422                 :            : static object_allocator<insn_info_type> insn_info_type_pool ("insn_info_pool");
     423                 :            : 
     424                 :            : /* The linked list of stores that are under consideration in this
     425                 :            :    basic block.  */
     426                 :            : static insn_info_t active_local_stores;
     427                 :            : static int active_local_stores_len;
     428                 :            : 
     429                 :            : struct dse_bb_info_type
     430                 :            : {
     431                 :            :   /* Pointer to the insn info for the last insn in the block.  These
     432                 :            :      are linked so this is how all of the insns are reached.  During
     433                 :            :      scanning this is the current insn being scanned.  */
     434                 :            :   insn_info_t last_insn;
     435                 :            : 
     436                 :            :   /* The info for the global dataflow problem.  */
     437                 :            : 
     438                 :            : 
     439                 :            :   /* This is set if the transfer function should and in the wild_read
     440                 :            :      bitmap before applying the kill and gen sets.  That vector knocks
     441                 :            :      out most of the bits in the bitmap and thus speeds up the
     442                 :            :      operations.  */
     443                 :            :   bool apply_wild_read;
     444                 :            : 
     445                 :            :   /* The following 4 bitvectors hold information about which positions
     446                 :            :      of which stores are live or dead.  They are indexed by
     447                 :            :      get_bitmap_index.  */
     448                 :            : 
     449                 :            :   /* The set of store positions that exist in this block before a wild read.  */
     450                 :            :   bitmap gen;
     451                 :            : 
     452                 :            :   /* The set of load positions that exist in this block above the
     453                 :            :      same position of a store.  */
     454                 :            :   bitmap kill;
     455                 :            : 
     456                 :            :   /* The set of stores that reach the top of the block without being
     457                 :            :      killed by a read.
     458                 :            : 
     459                 :            :      Do not represent the in if it is all ones.  Note that this is
     460                 :            :      what the bitvector should logically be initialized to for a set
     461                 :            :      intersection problem.  However, like the kill set, this is too
     462                 :            :      expensive.  So initially, the in set will only be created for the
     463                 :            :      exit block and any block that contains a wild read.  */
     464                 :            :   bitmap in;
     465                 :            : 
     466                 :            :   /* The set of stores that reach the bottom of the block from it's
     467                 :            :      successors.
     468                 :            : 
     469                 :            :      Do not represent the in if it is all ones.  Note that this is
     470                 :            :      what the bitvector should logically be initialized to for a set
     471                 :            :      intersection problem.  However, like the kill and in set, this is
     472                 :            :      too expensive.  So what is done is that the confluence operator
     473                 :            :      just initializes the vector from one of the out sets of the
     474                 :            :      successors of the block.  */
     475                 :            :   bitmap out;
     476                 :            : 
     477                 :            :   /* The following bitvector is indexed by the reg number.  It
     478                 :            :      contains the set of regs that are live at the current instruction
     479                 :            :      being processed.  While it contains info for all of the
     480                 :            :      registers, only the hard registers are actually examined.  It is used
     481                 :            :      to assure that shift and/or add sequences that are inserted do not
     482                 :            :      accidentally clobber live hard regs.  */
     483                 :            :   bitmap regs_live;
     484                 :            : };
     485                 :            : 
     486                 :            : typedef struct dse_bb_info_type *bb_info_t;
     487                 :            : 
     488                 :            : static object_allocator<dse_bb_info_type> dse_bb_info_type_pool
     489                 :            :   ("bb_info_pool");
     490                 :            : 
     491                 :            : /* Table to hold all bb_infos.  */
     492                 :            : static bb_info_t *bb_table;
     493                 :            : 
     494                 :            : /* There is a group_info for each rtx base that is used to reference
     495                 :            :    memory.  There are also not many of the rtx bases because they are
     496                 :            :    very limited in scope.  */
     497                 :            : 
     498                 :            : struct group_info
     499                 :            : {
     500                 :            :   /* The actual base of the address.  */
     501                 :            :   rtx rtx_base;
     502                 :            : 
     503                 :            :   /* The sequential id of the base.  This allows us to have a
     504                 :            :      canonical ordering of these that is not based on addresses.  */
     505                 :            :   int id;
     506                 :            : 
     507                 :            :   /* True if there are any positions that are to be processed
     508                 :            :      globally.  */
     509                 :            :   bool process_globally;
     510                 :            : 
     511                 :            :   /* True if the base of this group is either the frame_pointer or
     512                 :            :      hard_frame_pointer.  */
     513                 :            :   bool frame_related;
     514                 :            : 
     515                 :            :   /* A mem wrapped around the base pointer for the group in order to do
     516                 :            :      read dependency.  It must be given BLKmode in order to encompass all
     517                 :            :      the possible offsets from the base.  */
     518                 :            :   rtx base_mem;
     519                 :            : 
     520                 :            :   /* Canonized version of base_mem's address.  */
     521                 :            :   rtx canon_base_addr;
     522                 :            : 
     523                 :            :   /* These two sets of two bitmaps are used to keep track of how many
     524                 :            :      stores are actually referencing that position from this base.  We
     525                 :            :      only do this for rtx bases as this will be used to assign
     526                 :            :      positions in the bitmaps for the global problem.  Bit N is set in
     527                 :            :      store1 on the first store for offset N.  Bit N is set in store2
     528                 :            :      for the second store to offset N.  This is all we need since we
     529                 :            :      only care about offsets that have two or more stores for them.
     530                 :            : 
     531                 :            :      The "_n" suffix is for offsets less than 0 and the "_p" suffix is
     532                 :            :      for 0 and greater offsets.
     533                 :            : 
     534                 :            :      There is one special case here, for stores into the stack frame,
     535                 :            :      we will or store1 into store2 before deciding which stores look
     536                 :            :      at globally.  This is because stores to the stack frame that have
     537                 :            :      no other reads before the end of the function can also be
     538                 :            :      deleted.  */
     539                 :            :   bitmap store1_n, store1_p, store2_n, store2_p;
     540                 :            : 
     541                 :            :   /* These bitmaps keep track of offsets in this group escape this function.
     542                 :            :      An offset escapes if it corresponds to a named variable whose
     543                 :            :      addressable flag is set.  */
     544                 :            :   bitmap escaped_n, escaped_p;
     545                 :            : 
     546                 :            :   /* The positions in this bitmap have the same assignments as the in,
     547                 :            :      out, gen and kill bitmaps.  This bitmap is all zeros except for
     548                 :            :      the positions that are occupied by stores for this group.  */
     549                 :            :   bitmap group_kill;
     550                 :            : 
     551                 :            :   /* The offset_map is used to map the offsets from this base into
     552                 :            :      positions in the global bitmaps.  It is only created after all of
     553                 :            :      the all of stores have been scanned and we know which ones we
     554                 :            :      care about.  */
     555                 :            :   int *offset_map_n, *offset_map_p;
     556                 :            :   int offset_map_size_n, offset_map_size_p;
     557                 :            : };
     558                 :            : 
     559                 :            : static object_allocator<group_info> group_info_pool ("rtx_group_info_pool");
     560                 :            : 
     561                 :            : /* Index into the rtx_group_vec.  */
     562                 :            : static int rtx_group_next_id;
     563                 :            : 
     564                 :            : 
     565                 :            : static vec<group_info *> rtx_group_vec;
     566                 :            : 
     567                 :            : 
     568                 :            : /* This structure holds the set of changes that are being deferred
     569                 :            :    when removing read operation.  See replace_read.  */
     570                 :            : struct deferred_change
     571                 :            : {
     572                 :            : 
     573                 :            :   /* The mem that is being replaced.  */
     574                 :            :   rtx *loc;
     575                 :            : 
     576                 :            :   /* The reg it is being replaced with.  */
     577                 :            :   rtx reg;
     578                 :            : 
     579                 :            :   struct deferred_change *next;
     580                 :            : };
     581                 :            : 
     582                 :            : static object_allocator<deferred_change> deferred_change_pool
     583                 :            :   ("deferred_change_pool");
     584                 :            : 
     585                 :            : static deferred_change *deferred_change_list = NULL;
     586                 :            : 
     587                 :            : /* This is true except if cfun->stdarg -- i.e. we cannot do
     588                 :            :    this for vararg functions because they play games with the frame.  */
     589                 :            : static bool stores_off_frame_dead_at_return;
     590                 :            : 
     591                 :            : /* Counter for stats.  */
     592                 :            : static int globally_deleted;
     593                 :            : static int locally_deleted;
     594                 :            : 
     595                 :            : static bitmap all_blocks;
     596                 :            : 
     597                 :            : /* Locations that are killed by calls in the global phase.  */
     598                 :            : static bitmap kill_on_calls;
     599                 :            : 
     600                 :            : /* The number of bits used in the global bitmaps.  */
     601                 :            : static unsigned int current_position;
     602                 :            : 
     603                 :            : /* Print offset range [OFFSET, OFFSET + WIDTH) to FILE.  */
     604                 :            : 
     605                 :            : static void
     606                 :          0 : print_range (FILE *file, poly_int64 offset, poly_int64 width)
     607                 :            : {
     608                 :          0 :   fprintf (file, "[");
     609                 :          0 :   print_dec (offset, file, SIGNED);
     610                 :          0 :   fprintf (file, "..");
     611                 :          0 :   print_dec (offset + width, file, SIGNED);
     612                 :          0 :   fprintf (file, ")");
     613                 :          0 : }
     614                 :            : 
     615                 :            : /*----------------------------------------------------------------------------
     616                 :            :    Zeroth step.
     617                 :            : 
     618                 :            :    Initialization.
     619                 :            : ----------------------------------------------------------------------------*/
     620                 :            : 
     621                 :            : 
     622                 :            : /* Hashtable callbacks for maintaining the "bases" field of
     623                 :            :    store_group_info, given that the addresses are function invariants.  */
     624                 :            : 
     625                 :            : struct invariant_group_base_hasher : nofree_ptr_hash <group_info>
     626                 :            : {
     627                 :            :   static inline hashval_t hash (const group_info *);
     628                 :            :   static inline bool equal (const group_info *, const group_info *);
     629                 :            : };
     630                 :            : 
     631                 :            : inline bool
     632                 :   58874300 : invariant_group_base_hasher::equal (const group_info *gi1,
     633                 :            :                                     const group_info *gi2)
     634                 :            : {
     635                 :   58874300 :   return rtx_equal_p (gi1->rtx_base, gi2->rtx_base);
     636                 :            : }
     637                 :            : 
     638                 :            : inline hashval_t
     639                 :   67822600 : invariant_group_base_hasher::hash (const group_info *gi)
     640                 :            : {
     641                 :   67822600 :   int do_not_record;
     642                 :   86531100 :   return hash_rtx (gi->rtx_base, Pmode, &do_not_record, NULL, false);
     643                 :            : }
     644                 :            : 
     645                 :            : /* Tables of group_info structures, hashed by base value.  */
     646                 :            : static hash_table<invariant_group_base_hasher> *rtx_group_table;
     647                 :            : 
     648                 :            : 
     649                 :            : /* Get the GROUP for BASE.  Add a new group if it is not there.  */
     650                 :            : 
     651                 :            : static group_info *
     652                 :   14222600 : get_group_info (rtx base)
     653                 :            : {
     654                 :   14222600 :   struct group_info tmp_gi;
     655                 :   14222600 :   group_info *gi;
     656                 :   14222600 :   group_info **slot;
     657                 :            : 
     658                 :   14222600 :   gcc_assert (base != NULL_RTX);
     659                 :            : 
     660                 :            :   /* Find the store_base_info structure for BASE, creating a new one
     661                 :            :      if necessary.  */
     662                 :   14222600 :   tmp_gi.rtx_base = base;
     663                 :   14222600 :   slot = rtx_group_table->find_slot (&tmp_gi, INSERT);
     664                 :   14222600 :   gi = *slot;
     665                 :            : 
     666                 :   14222600 :   if (gi == NULL)
     667                 :            :     {
     668                 :    4212080 :       *slot = gi = group_info_pool.allocate ();
     669                 :    4212080 :       gi->rtx_base = base;
     670                 :    4212080 :       gi->id = rtx_group_next_id++;
     671                 :    4212080 :       gi->base_mem = gen_rtx_MEM (BLKmode, base);
     672                 :    4212080 :       gi->canon_base_addr = canon_rtx (base);
     673                 :    4212080 :       gi->store1_n = BITMAP_ALLOC (&dse_bitmap_obstack);
     674                 :    4212080 :       gi->store1_p = BITMAP_ALLOC (&dse_bitmap_obstack);
     675                 :    4212080 :       gi->store2_n = BITMAP_ALLOC (&dse_bitmap_obstack);
     676                 :    4212080 :       gi->store2_p = BITMAP_ALLOC (&dse_bitmap_obstack);
     677                 :    4212080 :       gi->escaped_p = BITMAP_ALLOC (&dse_bitmap_obstack);
     678                 :    4212080 :       gi->escaped_n = BITMAP_ALLOC (&dse_bitmap_obstack);
     679                 :    4212080 :       gi->group_kill = BITMAP_ALLOC (&dse_bitmap_obstack);
     680                 :    4212080 :       gi->process_globally = false;
     681                 :    8424160 :       gi->frame_related =
     682                 :    4212080 :         (base == frame_pointer_rtx) || (base == hard_frame_pointer_rtx);
     683                 :    4212080 :       gi->offset_map_size_n = 0;
     684                 :    4212080 :       gi->offset_map_size_p = 0;
     685                 :    4212080 :       gi->offset_map_n = NULL;
     686                 :    4212080 :       gi->offset_map_p = NULL;
     687                 :    4212080 :       rtx_group_vec.safe_push (gi);
     688                 :            :     }
     689                 :            : 
     690                 :   14222600 :   return gi;
     691                 :            : }
     692                 :            : 
     693                 :            : 
     694                 :            : /* Initialization of data structures.  */
     695                 :            : 
     696                 :            : static void
     697                 :    1373160 : dse_step0 (void)
     698                 :            : {
     699                 :    1373160 :   locally_deleted = 0;
     700                 :    1373160 :   globally_deleted = 0;
     701                 :            : 
     702                 :    1373160 :   bitmap_obstack_initialize (&dse_bitmap_obstack);
     703                 :    1373160 :   gcc_obstack_init (&dse_obstack);
     704                 :            : 
     705                 :    1373160 :   scratch = BITMAP_ALLOC (&reg_obstack);
     706                 :    1373160 :   kill_on_calls = BITMAP_ALLOC (&dse_bitmap_obstack);
     707                 :            : 
     708                 :            : 
     709                 :    1373160 :   rtx_group_table = new hash_table<invariant_group_base_hasher> (11);
     710                 :            : 
     711                 :    1373160 :   bb_table = XNEWVEC (bb_info_t, last_basic_block_for_fn (cfun));
     712                 :    1373160 :   rtx_group_next_id = 0;
     713                 :            : 
     714                 :    1373160 :   stores_off_frame_dead_at_return = !cfun->stdarg;
     715                 :            : 
     716                 :    1373160 :   init_alias_analysis ();
     717                 :    1373160 : }
     718                 :            : 
     719                 :            : 
     720                 :            : 
     721                 :            : /*----------------------------------------------------------------------------
     722                 :            :    First step.
     723                 :            : 
     724                 :            :    Scan all of the insns.  Any random ordering of the blocks is fine.
     725                 :            :    Each block is scanned in forward order to accommodate cselib which
     726                 :            :    is used to remove stores with non-constant bases.
     727                 :            : ----------------------------------------------------------------------------*/
     728                 :            : 
     729                 :            : /* Delete all of the store_info recs from INSN_INFO.  */
     730                 :            : 
     731                 :            : static void
     732                 :   11121400 : free_store_info (insn_info_t insn_info)
     733                 :            : {
     734                 :   11121400 :   store_info *cur = insn_info->store_rec;
     735                 :   22290800 :   while (cur)
     736                 :            :     {
     737                 :   11169400 :       store_info *next = cur->next;
     738                 :   11169400 :       if (cur->is_large)
     739                 :       8236 :         BITMAP_FREE (cur->positions_needed.large.bmap);
     740                 :   11169400 :       if (cur->cse_base)
     741                 :   11146400 :         cse_store_info_pool.remove (cur);
     742                 :            :       else
     743                 :   22313800 :         rtx_store_info_pool.remove (cur);
     744                 :            :       cur = next;
     745                 :            :     }
     746                 :            : 
     747                 :   11121400 :   insn_info->cannot_delete = true;
     748                 :   11121400 :   insn_info->contains_cselib_groups = false;
     749                 :   11121400 :   insn_info->store_rec = NULL;
     750                 :   11121400 : }
     751                 :            : 
     752                 :            : struct note_add_store_info
     753                 :            : {
     754                 :            :   rtx_insn *first, *current;
     755                 :            :   regset fixed_regs_live;
     756                 :            :   bool failure;
     757                 :            : };
     758                 :            : 
     759                 :            : /* Callback for emit_inc_dec_insn_before via note_stores.
     760                 :            :    Check if a register is clobbered which is live afterwards.  */
     761                 :            : 
     762                 :            : static void
     763                 :          0 : note_add_store (rtx loc, const_rtx expr ATTRIBUTE_UNUSED, void *data)
     764                 :            : {
     765                 :          0 :   rtx_insn *insn;
     766                 :          0 :   note_add_store_info *info = (note_add_store_info *) data;
     767                 :            : 
     768                 :          0 :   if (!REG_P (loc))
     769                 :            :     return;
     770                 :            : 
     771                 :            :   /* If this register is referenced by the current or an earlier insn,
     772                 :            :      that's OK.  E.g. this applies to the register that is being incremented
     773                 :            :      with this addition.  */
     774                 :          0 :   for (insn = info->first;
     775                 :          0 :        insn != NEXT_INSN (info->current);
     776                 :          0 :        insn = NEXT_INSN (insn))
     777                 :          0 :     if (reg_referenced_p (loc, PATTERN (insn)))
     778                 :            :       return;
     779                 :            : 
     780                 :            :   /* If we come here, we have a clobber of a register that's only OK
     781                 :            :      if that register is not live.  If we don't have liveness information
     782                 :            :      available, fail now.  */
     783                 :          0 :   if (!info->fixed_regs_live)
     784                 :            :     {
     785                 :          0 :       info->failure = true;
     786                 :          0 :       return;
     787                 :            :     }
     788                 :            :   /* Now check if this is a live fixed register.  */
     789                 :          0 :   unsigned int end_regno = END_REGNO (loc);
     790                 :          0 :   for (unsigned int regno = REGNO (loc); regno < end_regno; ++regno)
     791                 :          0 :     if (REGNO_REG_SET_P (info->fixed_regs_live, regno))
     792                 :          0 :       info->failure = true;
     793                 :            : }
     794                 :            : 
     795                 :            : /* Callback for for_each_inc_dec that emits an INSN that sets DEST to
     796                 :            :    SRC + SRCOFF before insn ARG.  */
     797                 :            : 
     798                 :            : static int
     799                 :          0 : emit_inc_dec_insn_before (rtx mem ATTRIBUTE_UNUSED,
     800                 :            :                           rtx op ATTRIBUTE_UNUSED,
     801                 :            :                           rtx dest, rtx src, rtx srcoff, void *arg)
     802                 :            : {
     803                 :          0 :   insn_info_t insn_info = (insn_info_t) arg;
     804                 :          0 :   rtx_insn *insn = insn_info->insn, *new_insn, *cur;
     805                 :          0 :   note_add_store_info info;
     806                 :            : 
     807                 :            :   /* We can reuse all operands without copying, because we are about
     808                 :            :      to delete the insn that contained it.  */
     809                 :          0 :   if (srcoff)
     810                 :            :     {
     811                 :          0 :       start_sequence ();
     812                 :          0 :       emit_insn (gen_add3_insn (dest, src, srcoff));
     813                 :          0 :       new_insn = get_insns ();
     814                 :          0 :       end_sequence ();
     815                 :            :     }
     816                 :            :   else
     817                 :          0 :     new_insn = gen_move_insn (dest, src);
     818                 :          0 :   info.first = new_insn;
     819                 :          0 :   info.fixed_regs_live = insn_info->fixed_regs_live;
     820                 :          0 :   info.failure = false;
     821                 :          0 :   for (cur = new_insn; cur; cur = NEXT_INSN (cur))
     822                 :            :     {
     823                 :          0 :       info.current = cur;
     824                 :          0 :       note_stores (cur, note_add_store, &info);
     825                 :            :     }
     826                 :            : 
     827                 :            :   /* If a failure was flagged above, return 1 so that for_each_inc_dec will
     828                 :            :      return it immediately, communicating the failure to its caller.  */
     829                 :          0 :   if (info.failure)
     830                 :            :     return 1;
     831                 :            : 
     832                 :          0 :   emit_insn_before (new_insn, insn);
     833                 :            : 
     834                 :          0 :   return 0;
     835                 :            : }
     836                 :            : 
     837                 :            : /* Before we delete INSN_INFO->INSN, make sure that the auto inc/dec, if it
     838                 :            :    is there, is split into a separate insn.
     839                 :            :    Return true on success (or if there was nothing to do), false on failure.  */
     840                 :            : 
     841                 :            : static bool
     842                 :     137325 : check_for_inc_dec_1 (insn_info_t insn_info)
     843                 :            : {
     844                 :     137325 :   rtx_insn *insn = insn_info->insn;
     845                 :     137325 :   rtx note = find_reg_note (insn, REG_INC, NULL_RTX);
     846                 :     137325 :   if (note)
     847                 :          0 :     return for_each_inc_dec (PATTERN (insn), emit_inc_dec_insn_before,
     848                 :          0 :                              insn_info) == 0;
     849                 :            : 
     850                 :            :   /* Punt on stack pushes, those don't have REG_INC notes and we are
     851                 :            :      unprepared to deal with distribution of REG_ARGS_SIZE notes etc.  */
     852                 :     137325 :   subrtx_iterator::array_type array;
     853                 :     951222 :   FOR_EACH_SUBRTX (iter, array, PATTERN (insn), NONCONST)
     854                 :            :     {
     855                 :     813897 :       const_rtx x = *iter;
     856                 :     813897 :       if (GET_RTX_CLASS (GET_CODE (x)) == RTX_AUTOINC)
     857                 :          0 :         return false;
     858                 :            :     }
     859                 :            : 
     860                 :     137325 :   return true;
     861                 :            : }
     862                 :            : 
     863                 :            : 
     864                 :            : /* Entry point for postreload.  If you work on reload_cse, or you need this
     865                 :            :    anywhere else, consider if you can provide register liveness information
     866                 :            :    and add a parameter to this function so that it can be passed down in
     867                 :            :    insn_info.fixed_regs_live.  */
     868                 :            : bool
     869                 :     164710 : check_for_inc_dec (rtx_insn *insn)
     870                 :            : {
     871                 :     164710 :   insn_info_type insn_info;
     872                 :     164710 :   rtx note;
     873                 :            : 
     874                 :     164710 :   insn_info.insn = insn;
     875                 :     164710 :   insn_info.fixed_regs_live = NULL;
     876                 :     164710 :   note = find_reg_note (insn, REG_INC, NULL_RTX);
     877                 :     164710 :   if (note)
     878                 :          0 :     return for_each_inc_dec (PATTERN (insn), emit_inc_dec_insn_before,
     879                 :          0 :                              &insn_info) == 0;
     880                 :            : 
     881                 :            :   /* Punt on stack pushes, those don't have REG_INC notes and we are
     882                 :            :      unprepared to deal with distribution of REG_ARGS_SIZE notes etc.  */
     883                 :     164710 :   subrtx_iterator::array_type array;
     884                 :     795354 :   FOR_EACH_SUBRTX (iter, array, PATTERN (insn), NONCONST)
     885                 :            :     {
     886                 :     630645 :       const_rtx x = *iter;
     887                 :     630645 :       if (GET_RTX_CLASS (GET_CODE (x)) == RTX_AUTOINC)
     888                 :          1 :         return false;
     889                 :            :     }
     890                 :            : 
     891                 :     164709 :   return true;
     892                 :            : }
     893                 :            : 
     894                 :            : /* Delete the insn and free all of the fields inside INSN_INFO.  */
     895                 :            : 
     896                 :            : static void
     897                 :      28998 : delete_dead_store_insn (insn_info_t insn_info)
     898                 :            : {
     899                 :      28998 :   read_info_t read_info;
     900                 :            : 
     901                 :      28998 :   if (!dbg_cnt (dse))
     902                 :            :     return;
     903                 :            : 
     904                 :      28998 :   if (!check_for_inc_dec_1 (insn_info))
     905                 :            :     return;
     906                 :      28998 :   if (dump_file && (dump_flags & TDF_DETAILS))
     907                 :          0 :     fprintf (dump_file, "Locally deleting insn %d\n",
     908                 :          0 :              INSN_UID (insn_info->insn));
     909                 :            : 
     910                 :      28998 :   free_store_info (insn_info);
     911                 :      28998 :   read_info = insn_info->read_rec;
     912                 :            : 
     913                 :      29012 :   while (read_info)
     914                 :            :     {
     915                 :         14 :       read_info_t next = read_info->next;
     916                 :         14 :       read_info_type_pool.remove (read_info);
     917                 :         14 :       read_info = next;
     918                 :            :     }
     919                 :      28998 :   insn_info->read_rec = NULL;
     920                 :            : 
     921                 :      28998 :   delete_insn (insn_info->insn);
     922                 :      28998 :   locally_deleted++;
     923                 :      28998 :   insn_info->insn = NULL;
     924                 :            : 
     925                 :      28998 :   insn_info->wild_read = false;
     926                 :            : }
     927                 :            : 
     928                 :            : /* Return whether DECL, a local variable, can possibly escape the current
     929                 :            :    function scope.  */
     930                 :            : 
     931                 :            : static bool
     932                 :    1043800 : local_variable_can_escape (tree decl)
     933                 :            : {
     934                 :    1043800 :   if (TREE_ADDRESSABLE (decl))
     935                 :            :     return true;
     936                 :            : 
     937                 :            :   /* If this is a partitioned variable, we need to consider all the variables
     938                 :            :      in the partition.  This is necessary because a store into one of them can
     939                 :            :      be replaced with a store into another and this may not change the outcome
     940                 :            :      of the escape analysis.  */
     941                 :    1043800 :   if (cfun->gimple_df->decls_to_pointers != NULL)
     942                 :            :     {
     943                 :     194639 :       tree *namep = cfun->gimple_df->decls_to_pointers->get (decl);
     944                 :          0 :       if (namep)
     945                 :          0 :         return TREE_ADDRESSABLE (*namep);
     946                 :            :     }
     947                 :            : 
     948                 :            :   return false;
     949                 :            : }
     950                 :            : 
     951                 :            : /* Return whether EXPR can possibly escape the current function scope.  */
     952                 :            : 
     953                 :            : static bool
     954                 :    4343620 : can_escape (tree expr)
     955                 :            : {
     956                 :    4343620 :   tree base;
     957                 :    4343620 :   if (!expr)
     958                 :            :     return true;
     959                 :    4134220 :   base = get_base_address (expr);
     960                 :    4134220 :   if (DECL_P (base)
     961                 :    3378760 :       && !may_be_aliased (base)
     962                 :    6386020 :       && !(VAR_P (base)
     963                 :    1197590 :            && !DECL_EXTERNAL (base)
     964                 :    1197590 :            && !TREE_STATIC (base)
     965                 :    1043800 :            && local_variable_can_escape (base)))
     966                 :    1208000 :     return false;
     967                 :            :   return true;
     968                 :            : }
     969                 :            : 
     970                 :            : /* Set the store* bitmaps offset_map_size* fields in GROUP based on
     971                 :            :    OFFSET and WIDTH.  */
     972                 :            : 
     973                 :            : static void
     974                 :    4343620 : set_usage_bits (group_info *group, poly_int64 offset, poly_int64 width,
     975                 :            :                 tree expr)
     976                 :            : {
     977                 :            :   /* Non-constant offsets and widths act as global kills, so there's no point
     978                 :            :      trying to use them to derive global DSE candidates.  */
     979                 :    4343620 :   HOST_WIDE_INT i, const_offset, const_width;
     980                 :    4343620 :   bool expr_escapes = can_escape (expr);
     981                 :    4343620 :   if (offset.is_constant (&const_offset)
     982                 :    4343620 :       && width.is_constant (&const_width)
     983                 :    4343620 :       && const_offset > -MAX_OFFSET
     984                 :    4338630 :       && const_offset + const_width < MAX_OFFSET)
     985                 :   44154400 :     for (i = const_offset; i < const_offset + const_width; ++i)
     986                 :            :       {
     987                 :   39816300 :         bitmap store1;
     988                 :   39816300 :         bitmap store2;
     989                 :   39816300 :         bitmap escaped;
     990                 :   39816300 :         int ai;
     991                 :   39816300 :         if (i < 0)
     992                 :            :           {
     993                 :   31119200 :             store1 = group->store1_n;
     994                 :   31119200 :             store2 = group->store2_n;
     995                 :   31119200 :             escaped = group->escaped_n;
     996                 :   31119200 :             ai = -i;
     997                 :            :           }
     998                 :            :         else
     999                 :            :           {
    1000                 :    8697100 :             store1 = group->store1_p;
    1001                 :    8697100 :             store2 = group->store2_p;
    1002                 :    8697100 :             escaped = group->escaped_p;
    1003                 :    8697100 :             ai = i;
    1004                 :            :           }
    1005                 :            : 
    1006                 :   39816300 :         if (!bitmap_set_bit (store1, ai))
    1007                 :   11049400 :           bitmap_set_bit (store2, ai);
    1008                 :            :         else
    1009                 :            :           {
    1010                 :   28766900 :             if (i < 0)
    1011                 :            :               {
    1012                 :   23504000 :                 if (group->offset_map_size_n < ai)
    1013                 :     296894 :                   group->offset_map_size_n = ai;
    1014                 :            :               }
    1015                 :            :             else
    1016                 :            :               {
    1017                 :    5262910 :                 if (group->offset_map_size_p < ai)
    1018                 :    4775560 :                   group->offset_map_size_p = ai;
    1019                 :            :               }
    1020                 :            :           }
    1021                 :   39816300 :         if (expr_escapes)
    1022                 :   31272100 :           bitmap_set_bit (escaped, ai);
    1023                 :            :       }
    1024                 :    4343620 : }
    1025                 :            : 
    1026                 :            : static void
    1027                 :    8298570 : reset_active_stores (void)
    1028                 :            : {
    1029                 :    8298570 :   active_local_stores = NULL;
    1030                 :    8298570 :   active_local_stores_len = 0;
    1031                 :          0 : }
    1032                 :            : 
    1033                 :            : /* Free all READ_REC of the LAST_INSN of BB_INFO.  */
    1034                 :            : 
    1035                 :            : static void
    1036                 :    8298570 : free_read_records (bb_info_t bb_info)
    1037                 :            : {
    1038                 :    8298570 :   insn_info_t insn_info = bb_info->last_insn;
    1039                 :          0 :   read_info_t *ptr = &insn_info->read_rec;
    1040                 :   14554000 :   while (*ptr)
    1041                 :            :     {
    1042                 :    6255460 :       read_info_t next = (*ptr)->next;
    1043                 :    6255460 :       read_info_type_pool.remove (*ptr);
    1044                 :    6255460 :       *ptr = next;
    1045                 :            :     }
    1046                 :          0 : }
    1047                 :            : 
    1048                 :            : /* Set the BB_INFO so that the last insn is marked as a wild read.  */
    1049                 :            : 
    1050                 :            : static void
    1051                 :    2153100 : add_wild_read (bb_info_t bb_info)
    1052                 :            : {
    1053                 :    2153100 :   insn_info_t insn_info = bb_info->last_insn;
    1054                 :    2153100 :   insn_info->wild_read = true;
    1055                 :    2153100 :   free_read_records (bb_info);
    1056                 :    2153100 :   reset_active_stores ();
    1057                 :    2153100 : }
    1058                 :            : 
    1059                 :            : /* Set the BB_INFO so that the last insn is marked as a wild read of
    1060                 :            :    non-frame locations.  */
    1061                 :            : 
    1062                 :            : static void
    1063                 :    6145470 : add_non_frame_wild_read (bb_info_t bb_info)
    1064                 :            : {
    1065                 :    6145470 :   insn_info_t insn_info = bb_info->last_insn;
    1066                 :    6145470 :   insn_info->non_frame_wild_read = true;
    1067                 :    6145470 :   free_read_records (bb_info);
    1068                 :    6145470 :   reset_active_stores ();
    1069                 :    6145470 : }
    1070                 :            : 
    1071                 :            : /* Return true if X is a constant or one of the registers that behave
    1072                 :            :    as a constant over the life of a function.  This is equivalent to
    1073                 :            :    !rtx_varies_p for memory addresses.  */
    1074                 :            : 
    1075                 :            : static bool
    1076                 :   54133600 : const_or_frame_p (rtx x)
    1077                 :            : {
    1078                 :   54133600 :   if (CONSTANT_P (x))
    1079                 :            :     return true;
    1080                 :            : 
    1081                 :   45751600 :   if (GET_CODE (x) == REG)
    1082                 :            :     {
    1083                 :            :       /* Note that we have to test for the actual rtx used for the frame
    1084                 :            :          and arg pointers and not just the register number in case we have
    1085                 :            :          eliminated the frame and/or arg pointer and are using it
    1086                 :            :          for pseudos.  */
    1087                 :   32427400 :       if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx
    1088                 :            :           /* The arg pointer varies if it is not a fixed register.  */
    1089                 :   26875300 :           || (x == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM])
    1090                 :   26586800 :           || x == pic_offset_table_rtx)
    1091                 :            :         return true;
    1092                 :   26586800 :       return false;
    1093                 :            :     }
    1094                 :            : 
    1095                 :            :   return false;
    1096                 :            : }
    1097                 :            : 
    1098                 :            : /* Take all reasonable action to put the address of MEM into the form
    1099                 :            :    that we can do analysis on.
    1100                 :            : 
    1101                 :            :    The gold standard is to get the address into the form: address +
    1102                 :            :    OFFSET where address is something that rtx_varies_p considers a
    1103                 :            :    constant.  When we can get the address in this form, we can do
    1104                 :            :    global analysis on it.  Note that for constant bases, address is
    1105                 :            :    not actually returned, only the group_id.  The address can be
    1106                 :            :    obtained from that.
    1107                 :            : 
    1108                 :            :    If that fails, we try cselib to get a value we can at least use
    1109                 :            :    locally.  If that fails we return false.
    1110                 :            : 
    1111                 :            :    The GROUP_ID is set to -1 for cselib bases and the index of the
    1112                 :            :    group for non_varying bases.
    1113                 :            : 
    1114                 :            :    FOR_READ is true if this is a mem read and false if not.  */
    1115                 :            : 
    1116                 :            : static bool
    1117                 :   34165000 : canon_address (rtx mem,
    1118                 :            :                int *group_id,
    1119                 :            :                poly_int64 *offset,
    1120                 :            :                cselib_val **base)
    1121                 :            : {
    1122                 :   34165000 :   machine_mode address_mode = get_address_mode (mem);
    1123                 :   34165000 :   rtx mem_address = XEXP (mem, 0);
    1124                 :   34165000 :   rtx expanded_address, address;
    1125                 :   34165000 :   int expanded;
    1126                 :            : 
    1127                 :   34165000 :   cselib_lookup (mem_address, address_mode, 1, GET_MODE (mem));
    1128                 :            : 
    1129                 :   34165000 :   if (dump_file && (dump_flags & TDF_DETAILS))
    1130                 :            :     {
    1131                 :          0 :       fprintf (dump_file, "  mem: ");
    1132                 :          0 :       print_inline_rtx (dump_file, mem_address, 0);
    1133                 :          0 :       fprintf (dump_file, "\n");
    1134                 :            :     }
    1135                 :            : 
    1136                 :            :   /* First see if just canon_rtx (mem_address) is const or frame,
    1137                 :            :      if not, try cselib_expand_value_rtx and call canon_rtx on that.  */
    1138                 :            :   address = NULL_RTX;
    1139                 :   74097800 :   for (expanded = 0; expanded < 2; expanded++)
    1140                 :            :     {
    1141                 :   54155400 :       if (expanded)
    1142                 :            :         {
    1143                 :            :           /* Use cselib to replace all of the reg references with the full
    1144                 :            :              expression.  This will take care of the case where we have
    1145                 :            : 
    1146                 :            :              r_x = base + offset;
    1147                 :            :              val = *r_x;
    1148                 :            : 
    1149                 :            :              by making it into
    1150                 :            : 
    1151                 :            :              val = *(base + offset);  */
    1152                 :            : 
    1153                 :   19990400 :           expanded_address = cselib_expand_value_rtx (mem_address,
    1154                 :            :                                                       scratch, 5);
    1155                 :            : 
    1156                 :            :           /* If this fails, just go with the address from first
    1157                 :            :              iteration.  */
    1158                 :   19990400 :           if (!expanded_address)
    1159                 :            :             break;
    1160                 :            :         }
    1161                 :            :       else
    1162                 :            :         expanded_address = mem_address;
    1163                 :            : 
    1164                 :            :       /* Split the address into canonical BASE + OFFSET terms.  */
    1165                 :   54155400 :       address = canon_rtx (expanded_address);
    1166                 :            : 
    1167                 :   54155400 :       *offset = 0;
    1168                 :            : 
    1169                 :   54155400 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1170                 :            :         {
    1171                 :          0 :           if (expanded)
    1172                 :            :             {
    1173                 :          0 :               fprintf (dump_file, "\n   after cselib_expand address: ");
    1174                 :          0 :               print_inline_rtx (dump_file, expanded_address, 0);
    1175                 :          0 :               fprintf (dump_file, "\n");
    1176                 :            :             }
    1177                 :            : 
    1178                 :          0 :           fprintf (dump_file, "\n   after canon_rtx address: ");
    1179                 :          0 :           print_inline_rtx (dump_file, address, 0);
    1180                 :          0 :           fprintf (dump_file, "\n");
    1181                 :            :         }
    1182                 :            : 
    1183                 :   54155400 :       if (GET_CODE (address) == CONST)
    1184                 :     723265 :         address = XEXP (address, 0);
    1185                 :            : 
    1186                 :   54155400 :       address = strip_offset_and_add (address, offset);
    1187                 :            : 
    1188                 :   54155400 :       if (ADDR_SPACE_GENERIC_P (MEM_ADDR_SPACE (mem))
    1189                 :   54155400 :           && const_or_frame_p (address))
    1190                 :            :         {
    1191                 :   14222600 :           group_info *group = get_group_info (address);
    1192                 :            : 
    1193                 :   14222600 :           if (dump_file && (dump_flags & TDF_DETAILS))
    1194                 :            :             {
    1195                 :          0 :               fprintf (dump_file, "  gid=%d offset=", group->id);
    1196                 :          0 :               print_dec (*offset, dump_file);
    1197                 :          0 :               fprintf (dump_file, "\n");
    1198                 :            :             }
    1199                 :   14222600 :           *base = NULL;
    1200                 :   14222600 :           *group_id = group->id;
    1201                 :   14222600 :           return true;
    1202                 :            :         }
    1203                 :            :     }
    1204                 :            : 
    1205                 :   19942400 :   *base = cselib_lookup (address, address_mode, true, GET_MODE (mem));
    1206                 :   19942400 :   *group_id = -1;
    1207                 :            : 
    1208                 :   19942400 :   if (*base == NULL)
    1209                 :            :     {
    1210                 :     142895 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1211                 :          0 :         fprintf (dump_file, " no cselib val - should be a wild read.\n");
    1212                 :     142895 :       return false;
    1213                 :            :     }
    1214                 :   19799500 :   if (dump_file && (dump_flags & TDF_DETAILS))
    1215                 :            :     {
    1216                 :          0 :       fprintf (dump_file, "  varying cselib base=%u:%u offset = ",
    1217                 :            :                (*base)->uid, (*base)->hash);
    1218                 :          0 :       print_dec (*offset, dump_file);
    1219                 :          0 :       fprintf (dump_file, "\n");
    1220                 :            :     }
    1221                 :            :   return true;
    1222                 :            : }
    1223                 :            : 
    1224                 :            : 
    1225                 :            : /* Clear the rhs field from the active_local_stores array.  */
    1226                 :            : 
    1227                 :            : static void
    1228                 :      82948 : clear_rhs_from_active_local_stores (void)
    1229                 :            : {
    1230                 :          0 :   insn_info_t ptr = active_local_stores;
    1231                 :            : 
    1232                 :     121144 :   while (ptr)
    1233                 :            :     {
    1234                 :      38196 :       store_info *store_info = ptr->store_rec;
    1235                 :            :       /* Skip the clobbers.  */
    1236                 :      38196 :       while (!store_info->is_set)
    1237                 :          0 :         store_info = store_info->next;
    1238                 :            : 
    1239                 :      38196 :       store_info->rhs = NULL;
    1240                 :      38196 :       store_info->const_rhs = NULL;
    1241                 :            : 
    1242                 :      38196 :       ptr = ptr->next_local_store;
    1243                 :            :     }
    1244                 :          0 : }
    1245                 :            : 
    1246                 :            : 
    1247                 :            : /* Mark byte POS bytes from the beginning of store S_INFO as unneeded.  */
    1248                 :            : 
    1249                 :            : static inline void
    1250                 :     341508 : set_position_unneeded (store_info *s_info, int pos)
    1251                 :            : {
    1252                 :     341508 :   if (__builtin_expect (s_info->is_large, false))
    1253                 :            :     {
    1254                 :     230013 :       if (bitmap_set_bit (s_info->positions_needed.large.bmap, pos))
    1255                 :     230013 :         s_info->positions_needed.large.count++;
    1256                 :            :     }
    1257                 :            :   else
    1258                 :     111495 :     s_info->positions_needed.small_bitmask
    1259                 :     111495 :       &= ~(HOST_WIDE_INT_1U << pos);
    1260                 :     341508 : }
    1261                 :            : 
    1262                 :            : /* Mark the whole store S_INFO as unneeded.  */
    1263                 :            : 
    1264                 :            : static inline void
    1265                 :     240533 : set_all_positions_unneeded (store_info *s_info)
    1266                 :            : {
    1267                 :     240533 :   if (__builtin_expect (s_info->is_large, false))
    1268                 :            :     {
    1269                 :          0 :       HOST_WIDE_INT width;
    1270                 :          0 :       if (s_info->width.is_constant (&width))
    1271                 :            :         {
    1272                 :          0 :           bitmap_set_range (s_info->positions_needed.large.bmap, 0, width);
    1273                 :          0 :           s_info->positions_needed.large.count = width;
    1274                 :            :         }
    1275                 :            :       else
    1276                 :            :         {
    1277                 :            :           gcc_checking_assert (!s_info->positions_needed.large.bmap);
    1278                 :            :           s_info->positions_needed.large.count = 1;
    1279                 :            :         }
    1280                 :            :     }
    1281                 :            :   else
    1282                 :     240533 :     s_info->positions_needed.small_bitmask = HOST_WIDE_INT_0U;
    1283                 :            : }
    1284                 :            : 
    1285                 :            : /* Return TRUE if any bytes from S_INFO store are needed.  */
    1286                 :            : 
    1287                 :            : static inline bool
    1288                 :  190921000 : any_positions_needed_p (store_info *s_info)
    1289                 :            : {
    1290                 :  190921000 :   if (__builtin_expect (s_info->is_large, false))
    1291                 :            :     {
    1292                 :     110751 :       HOST_WIDE_INT width;
    1293                 :     110751 :       if (s_info->width.is_constant (&width))
    1294                 :            :         {
    1295                 :     110751 :           gcc_checking_assert (s_info->positions_needed.large.bmap);
    1296                 :     110751 :           return s_info->positions_needed.large.count < width;
    1297                 :            :         }
    1298                 :            :       else
    1299                 :            :         {
    1300                 :            :           gcc_checking_assert (!s_info->positions_needed.large.bmap);
    1301                 :            :           return s_info->positions_needed.large.count == 0;
    1302                 :            :         }
    1303                 :            :     }
    1304                 :            :   else
    1305                 :  190810000 :     return (s_info->positions_needed.small_bitmask != HOST_WIDE_INT_0U);
    1306                 :            : }
    1307                 :            : 
    1308                 :            : /* Return TRUE if all bytes START through START+WIDTH-1 from S_INFO
    1309                 :            :    store are known to be needed.  */
    1310                 :            : 
    1311                 :            : static inline bool
    1312                 :     135555 : all_positions_needed_p (store_info *s_info, poly_int64 start,
    1313                 :            :                         poly_int64 width)
    1314                 :            : {
    1315                 :     135555 :   gcc_assert (s_info->rhs);
    1316                 :     135555 :   if (!s_info->width.is_constant ())
    1317                 :            :     {
    1318                 :            :       gcc_assert (s_info->is_large
    1319                 :            :                   && !s_info->positions_needed.large.bmap);
    1320                 :            :       return s_info->positions_needed.large.count == 0;
    1321                 :            :     }
    1322                 :            : 
    1323                 :            :   /* Otherwise, if START and WIDTH are non-constant, we're asking about
    1324                 :            :      a non-constant region of a constant-sized store.  We can't say for
    1325                 :            :      sure that all positions are needed.  */
    1326                 :     135555 :   HOST_WIDE_INT const_start, const_width;
    1327                 :     135555 :   if (!start.is_constant (&const_start)
    1328                 :     135555 :       || !width.is_constant (&const_width))
    1329                 :            :     return false;
    1330                 :            : 
    1331                 :     135555 :   if (__builtin_expect (s_info->is_large, false))
    1332                 :            :     {
    1333                 :      84343 :       for (HOST_WIDE_INT i = const_start; i < const_start + const_width; ++i)
    1334                 :      74164 :         if (bitmap_bit_p (s_info->positions_needed.large.bmap, i))
    1335                 :            :           return false;
    1336                 :            :       return true;
    1337                 :            :     }
    1338                 :            :   else
    1339                 :            :     {
    1340                 :     125356 :       unsigned HOST_WIDE_INT mask
    1341                 :     125356 :         = lowpart_bitmask (const_width) << const_start;
    1342                 :     125356 :       return (s_info->positions_needed.small_bitmask & mask) == mask;
    1343                 :            :     }
    1344                 :            : }
    1345                 :            : 
    1346                 :            : 
    1347                 :            : static rtx get_stored_val (store_info *, machine_mode, poly_int64,
    1348                 :            :                            poly_int64, basic_block, bool);
    1349                 :            : 
    1350                 :            : 
    1351                 :            : /* BODY is an instruction pattern that belongs to INSN.  Return 1 if
    1352                 :            :    there is a candidate store, after adding it to the appropriate
    1353                 :            :    local store group if so.  */
    1354                 :            : 
    1355                 :            : static int
    1356                 :   84718200 : record_store (rtx body, bb_info_t bb_info)
    1357                 :            : {
    1358                 :   84718200 :   rtx mem, rhs, const_rhs, mem_addr;
    1359                 :   84718200 :   poly_int64 offset = 0;
    1360                 :   84718200 :   poly_int64 width = 0;
    1361                 :   84718200 :   insn_info_t insn_info = bb_info->last_insn;
    1362                 :   84718200 :   store_info *store_info = NULL;
    1363                 :   84718200 :   int group_id;
    1364                 :   84718200 :   cselib_val *base = NULL;
    1365                 :   84718200 :   insn_info_t ptr, last, redundant_reason;
    1366                 :   84718200 :   bool store_is_unused;
    1367                 :            : 
    1368                 :   84718200 :   if (GET_CODE (body) != SET && GET_CODE (body) != CLOBBER)
    1369                 :            :     return 0;
    1370                 :            : 
    1371                 :   82407400 :   mem = SET_DEST (body);
    1372                 :            : 
    1373                 :            :   /* If this is not used, then this cannot be used to keep the insn
    1374                 :            :      from being deleted.  On the other hand, it does provide something
    1375                 :            :      that can be used to prove that another store is dead.  */
    1376                 :   82407400 :   store_is_unused
    1377                 :   82407400 :     = (find_reg_note (insn_info->insn, REG_UNUSED, mem) != NULL);
    1378                 :            : 
    1379                 :            :   /* Check whether that value is a suitable memory location.  */
    1380                 :   82407400 :   if (!MEM_P (mem))
    1381                 :            :     {
    1382                 :            :       /* If the set or clobber is unused, then it does not effect our
    1383                 :            :          ability to get rid of the entire insn.  */
    1384                 :   65903400 :       if (!store_is_unused)
    1385                 :   55420700 :         insn_info->cannot_delete = true;
    1386                 :   65903400 :       return 0;
    1387                 :            :     }
    1388                 :            : 
    1389                 :            :   /* At this point we know mem is a mem. */
    1390                 :   16504000 :   if (GET_MODE (mem) == BLKmode)
    1391                 :            :     {
    1392                 :    1032340 :       HOST_WIDE_INT const_size;
    1393                 :    1032340 :       if (GET_CODE (XEXP (mem, 0)) == SCRATCH)
    1394                 :            :         {
    1395                 :     949001 :           if (dump_file && (dump_flags & TDF_DETAILS))
    1396                 :          0 :             fprintf (dump_file, " adding wild read for (clobber (mem:BLK (scratch))\n");
    1397                 :     949001 :           add_wild_read (bb_info);
    1398                 :     949001 :           insn_info->cannot_delete = true;
    1399                 :     949001 :           return 0;
    1400                 :            :         }
    1401                 :            :       /* Handle (set (mem:BLK (addr) [... S36 ...]) (const_int 0))
    1402                 :            :          as memset (addr, 0, 36);  */
    1403                 :      83337 :       else if (!MEM_SIZE_KNOWN_P (mem)
    1404                 :      58381 :                || maybe_le (MEM_SIZE (mem), 0)
    1405                 :            :                /* This is a limit on the bitmap size, which is only relevant
    1406                 :            :                   for constant-sized MEMs.  */
    1407                 :      58381 :                || (MEM_SIZE (mem).is_constant (&const_size)
    1408                 :      58381 :                    && const_size > MAX_OFFSET)
    1409                 :      58071 :                || GET_CODE (body) != SET
    1410                 :     141408 :                || !CONST_INT_P (SET_SRC (body)))
    1411                 :            :         {
    1412                 :      59024 :           if (!store_is_unused)
    1413                 :            :             {
    1414                 :            :               /* If the set or clobber is unused, then it does not effect our
    1415                 :            :                  ability to get rid of the entire insn.  */
    1416                 :      59024 :               insn_info->cannot_delete = true;
    1417                 :      59024 :               clear_rhs_from_active_local_stores ();
    1418                 :            :             }
    1419                 :      59024 :           return 0;
    1420                 :            :         }
    1421                 :            :     }
    1422                 :            : 
    1423                 :            :   /* We can still process a volatile mem, we just cannot delete it.  */
    1424                 :   15496000 :   if (MEM_VOLATILE_P (mem))
    1425                 :     609810 :     insn_info->cannot_delete = true;
    1426                 :            : 
    1427                 :   15496000 :   if (!canon_address (mem, &group_id, &offset, &base))
    1428                 :            :     {
    1429                 :       5943 :       clear_rhs_from_active_local_stores ();
    1430                 :            :       return 0;
    1431                 :            :     }
    1432                 :            : 
    1433                 :   15490000 :   if (GET_MODE (mem) == BLKmode)
    1434                 :      24301 :     width = MEM_SIZE (mem);
    1435                 :            :   else
    1436                 :   30931500 :     width = GET_MODE_SIZE (GET_MODE (mem));
    1437                 :            : 
    1438                 :   30980100 :   if (!endpoint_representable_p (offset, width))
    1439                 :            :     {
    1440                 :          0 :       clear_rhs_from_active_local_stores ();
    1441                 :            :       return 0;
    1442                 :            :     }
    1443                 :            : 
    1444                 :   15490000 :   if (known_eq (width, 0))
    1445                 :            :     return 0;
    1446                 :            : 
    1447                 :   15490000 :   if (group_id >= 0)
    1448                 :            :     {
    1449                 :            :       /* In the restrictive case where the base is a constant or the
    1450                 :            :          frame pointer we can do global analysis.  */
    1451                 :            : 
    1452                 :    4343620 :       group_info *group
    1453                 :    4343620 :         = rtx_group_vec[group_id];
    1454                 :    4343620 :       tree expr = MEM_EXPR (mem);
    1455                 :            : 
    1456                 :    4343620 :       store_info = rtx_store_info_pool.allocate ();
    1457                 :    4343620 :       set_usage_bits (group, offset, width, expr);
    1458                 :            : 
    1459                 :    4343620 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1460                 :            :         {
    1461                 :          0 :           fprintf (dump_file, " processing const base store gid=%d",
    1462                 :            :                    group_id);
    1463                 :          0 :           print_range (dump_file, offset, width);
    1464                 :          0 :           fprintf (dump_file, "\n");
    1465                 :            :         }
    1466                 :            :     }
    1467                 :            :   else
    1468                 :            :     {
    1469                 :   11146400 :       if (may_be_sp_based_p (XEXP (mem, 0)))
    1470                 :    9856240 :         insn_info->stack_pointer_based = true;
    1471                 :   11146400 :       insn_info->contains_cselib_groups = true;
    1472                 :            : 
    1473                 :   11146400 :       store_info = cse_store_info_pool.allocate ();
    1474                 :   11146400 :       group_id = -1;
    1475                 :            : 
    1476                 :   11146400 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1477                 :            :         {
    1478                 :          0 :           fprintf (dump_file, " processing cselib store ");
    1479                 :          0 :           print_range (dump_file, offset, width);
    1480                 :          0 :           fprintf (dump_file, "\n");
    1481                 :            :         }
    1482                 :            :     }
    1483                 :            : 
    1484                 :   15490000 :   const_rhs = rhs = NULL_RTX;
    1485                 :   15490000 :   if (GET_CODE (body) == SET
    1486                 :            :       /* No place to keep the value after ra.  */
    1487                 :   15488200 :       && !reload_completed
    1488                 :    6617530 :       && (REG_P (SET_SRC (body))
    1489                 :    2635400 :           || GET_CODE (SET_SRC (body)) == SUBREG
    1490                 :    2571910 :           || CONSTANT_P (SET_SRC (body)))
    1491                 :    6322130 :       && !MEM_VOLATILE_P (mem)
    1492                 :            :       /* Sometimes the store and reload is used for truncation and
    1493                 :            :          rounding.  */
    1494                 :   21550900 :       && !(FLOAT_MODE_P (GET_MODE (mem)) && (flag_float_store)))
    1495                 :            :     {
    1496                 :    6060200 :       rhs = SET_SRC (body);
    1497                 :    6060200 :       if (CONSTANT_P (rhs))
    1498                 :            :         const_rhs = rhs;
    1499                 :    3917240 :       else if (body == PATTERN (insn_info->insn))
    1500                 :            :         {
    1501                 :    3917240 :           rtx tem = find_reg_note (insn_info->insn, REG_EQUAL, NULL_RTX);
    1502                 :    3917240 :           if (tem && CONSTANT_P (XEXP (tem, 0)))
    1503                 :            :             const_rhs = XEXP (tem, 0);
    1504                 :            :         }
    1505                 :    6060200 :       if (const_rhs == NULL_RTX && REG_P (rhs))
    1506                 :            :         {
    1507                 :    3866860 :           rtx tem = cselib_expand_value_rtx (rhs, scratch, 5);
    1508                 :            : 
    1509                 :    3866860 :           if (tem && CONSTANT_P (tem))
    1510                 :     165357 :             const_rhs = tem;
    1511                 :            :         }
    1512                 :            :     }
    1513                 :            : 
    1514                 :            :   /* Check to see if this stores causes some other stores to be
    1515                 :            :      dead.  */
    1516                 :   15490000 :   ptr = active_local_stores;
    1517                 :   15490000 :   last = NULL;
    1518                 :   15490000 :   redundant_reason = NULL;
    1519                 :   15490000 :   mem = canon_rtx (mem);
    1520                 :            : 
    1521                 :   15490000 :   if (group_id < 0)
    1522                 :   11146400 :     mem_addr = base->val_rtx;
    1523                 :            :   else
    1524                 :            :     {
    1525                 :    4343620 :       group_info *group = rtx_group_vec[group_id];
    1526                 :    4343620 :       mem_addr = group->canon_base_addr;
    1527                 :            :     }
    1528                 :   15490000 :   if (maybe_ne (offset, 0))
    1529                 :    9095780 :     mem_addr = plus_constant (get_address_mode (mem), mem_addr, offset);
    1530                 :            : 
    1531                 :  206411000 :   while (ptr)
    1532                 :            :     {
    1533                 :  190921000 :       insn_info_t next = ptr->next_local_store;
    1534                 :  190921000 :       class store_info *s_info = ptr->store_rec;
    1535                 :  190921000 :       bool del = true;
    1536                 :            : 
    1537                 :            :       /* Skip the clobbers. We delete the active insn if this insn
    1538                 :            :          shadows the set.  To have been put on the active list, it
    1539                 :            :          has exactly on set. */
    1540                 :  190921000 :       while (!s_info->is_set)
    1541                 :          0 :         s_info = s_info->next;
    1542                 :            : 
    1543                 :  190921000 :       if (s_info->group_id == group_id && s_info->cse_base == base)
    1544                 :            :         {
    1545                 :  171942000 :           HOST_WIDE_INT i;
    1546                 :  171942000 :           if (dump_file && (dump_flags & TDF_DETAILS))
    1547                 :            :             {
    1548                 :          0 :               fprintf (dump_file, "    trying store in insn=%d gid=%d",
    1549                 :          0 :                        INSN_UID (ptr->insn), s_info->group_id);
    1550                 :          0 :               print_range (dump_file, s_info->offset, s_info->width);
    1551                 :          0 :               fprintf (dump_file, "\n");
    1552                 :            :             }
    1553                 :            : 
    1554                 :            :           /* Even if PTR won't be eliminated as unneeded, if both
    1555                 :            :              PTR and this insn store the same constant value, we might
    1556                 :            :              eliminate this insn instead.  */
    1557                 :  171942000 :           if (s_info->const_rhs
    1558                 :   61705400 :               && const_rhs
    1559                 :  171970000 :               && known_subrange_p (offset, width,
    1560                 :   55771000 :                                    s_info->offset, s_info->width)
    1561                 :      28463 :               && all_positions_needed_p (s_info, offset - s_info->offset,
    1562                 :            :                                          width)
    1563                 :            :               /* We can only remove the later store if the earlier aliases
    1564                 :            :                  at least all accesses the later one.  */
    1565                 :  171970000 :               && ((MEM_ALIAS_SET (mem) == MEM_ALIAS_SET (s_info->mem)
    1566                 :      24624 :                    || alias_set_subset_of (MEM_ALIAS_SET (mem),
    1567                 :      24624 :                                            MEM_ALIAS_SET (s_info->mem)))
    1568                 :      28385 :                   && (!MEM_EXPR (s_info->mem)
    1569                 :      28321 :                       || refs_same_for_tbaa_p (MEM_EXPR (s_info->mem),
    1570                 :      28321 :                                                MEM_EXPR (mem)))))
    1571                 :            :             {
    1572                 :      28375 :               if (GET_MODE (mem) == BLKmode)
    1573                 :            :                 {
    1574                 :          3 :                   if (GET_MODE (s_info->mem) == BLKmode
    1575                 :          3 :                       && s_info->const_rhs == const_rhs)
    1576                 :          3 :                     redundant_reason = ptr;
    1577                 :            :                 }
    1578                 :      28372 :               else if (s_info->const_rhs == const0_rtx
    1579                 :      25653 :                        && const_rhs == const0_rtx)
    1580                 :            :                 redundant_reason = ptr;
    1581                 :            :               else
    1582                 :            :                 {
    1583                 :      28347 :                   rtx val;
    1584                 :      28347 :                   start_sequence ();
    1585                 :      56694 :                   val = get_stored_val (s_info, GET_MODE (mem), offset, width,
    1586                 :      28347 :                                         BLOCK_FOR_INSN (insn_info->insn),
    1587                 :            :                                         true);
    1588                 :      28347 :                   if (get_insns () != NULL)
    1589                 :          0 :                     val = NULL_RTX;
    1590                 :      28347 :                   end_sequence ();
    1591                 :      28347 :                   if (val && rtx_equal_p (val, const_rhs))
    1592                 :            :                     redundant_reason = ptr;
    1593                 :            :                 }
    1594                 :            :             }
    1595                 :            : 
    1596                 :  171942000 :           HOST_WIDE_INT begin_unneeded, const_s_width, const_width;
    1597                 :  171942000 :           if (known_subrange_p (s_info->offset, s_info->width, offset, width))
    1598                 :            :             /* The new store touches every byte that S_INFO does.  */
    1599                 :     240533 :             set_all_positions_unneeded (s_info);
    1600                 :  171701000 :           else if ((offset - s_info->offset).is_constant (&begin_unneeded)
    1601                 :  171701000 :                    && s_info->width.is_constant (&const_s_width)
    1602                 :  171701000 :                    && width.is_constant (&const_width))
    1603                 :            :             {
    1604                 :  171701000 :               HOST_WIDE_INT end_unneeded = begin_unneeded + const_width;
    1605                 :  171701000 :               begin_unneeded = MAX (begin_unneeded, 0);
    1606                 :  171701000 :               end_unneeded = MIN (end_unneeded, const_s_width);
    1607                 :  172043000 :               for (i = begin_unneeded; i < end_unneeded; ++i)
    1608                 :     341508 :                 set_position_unneeded (s_info, i);
    1609                 :            :             }
    1610                 :            :           else
    1611                 :            :             {
    1612                 :            :               /* We don't know which parts of S_INFO are needed and
    1613                 :            :                  which aren't, so invalidate the RHS.  */
    1614                 :            :               s_info->rhs = NULL;
    1615                 :            :               s_info->const_rhs = NULL;
    1616                 :            :             }
    1617                 :            :         }
    1618                 :   18978800 :       else if (s_info->rhs)
    1619                 :            :         /* Need to see if it is possible for this store to overwrite
    1620                 :            :            the value of store_info.  If it is, set the rhs to NULL to
    1621                 :            :            keep it from being used to remove a load.  */
    1622                 :            :         {
    1623                 :    2894390 :           if (canon_output_dependence (s_info->mem, true,
    1624                 :    2894390 :                                        mem, GET_MODE (mem),
    1625                 :            :                                        mem_addr))
    1626                 :            :             {
    1627                 :    1425720 :               s_info->rhs = NULL;
    1628                 :    1425720 :               s_info->const_rhs = NULL;
    1629                 :            :             }
    1630                 :            :         }
    1631                 :            : 
    1632                 :            :       /* An insn can be deleted if every position of every one of
    1633                 :            :          its s_infos is zero.  */
    1634                 :  190921000 :       if (any_positions_needed_p (s_info))
    1635                 :            :         del = false;
    1636                 :            : 
    1637                 :     241679 :       if (del)
    1638                 :            :         {
    1639                 :     241679 :           insn_info_t insn_to_delete = ptr;
    1640                 :            : 
    1641                 :     241679 :           active_local_stores_len--;
    1642                 :     241679 :           if (last)
    1643                 :      15592 :             last->next_local_store = ptr->next_local_store;
    1644                 :            :           else
    1645                 :     226087 :             active_local_stores = ptr->next_local_store;
    1646                 :            : 
    1647                 :     241679 :           if (!insn_to_delete->cannot_delete)
    1648                 :      16551 :             delete_dead_store_insn (insn_to_delete);
    1649                 :            :         }
    1650                 :            :       else
    1651                 :            :         last = ptr;
    1652                 :            : 
    1653                 :            :       ptr = next;
    1654                 :            :     }
    1655                 :            : 
    1656                 :            :   /* Finish filling in the store_info.  */
    1657                 :   15490000 :   store_info->next = insn_info->store_rec;
    1658                 :   15490000 :   insn_info->store_rec = store_info;
    1659                 :   15490000 :   store_info->mem = mem;
    1660                 :   15490000 :   store_info->mem_addr = mem_addr;
    1661                 :   15490000 :   store_info->cse_base = base;
    1662                 :   15490000 :   HOST_WIDE_INT const_width;
    1663                 :   15490000 :   if (!width.is_constant (&const_width))
    1664                 :            :     {
    1665                 :            :       store_info->is_large = true;
    1666                 :            :       store_info->positions_needed.large.count = 0;
    1667                 :            :       store_info->positions_needed.large.bmap = NULL;
    1668                 :            :     }
    1669                 :   15490000 :   else if (const_width > HOST_BITS_PER_WIDE_INT)
    1670                 :            :     {
    1671                 :      19223 :       store_info->is_large = true;
    1672                 :      19223 :       store_info->positions_needed.large.count = 0;
    1673                 :      19223 :       store_info->positions_needed.large.bmap = BITMAP_ALLOC (&dse_bitmap_obstack);
    1674                 :            :     }
    1675                 :            :   else
    1676                 :            :     {
    1677                 :   15470800 :       store_info->is_large = false;
    1678                 :   15470800 :       store_info->positions_needed.small_bitmask
    1679                 :   15470800 :         = lowpart_bitmask (const_width);
    1680                 :            :     }
    1681                 :   15490000 :   store_info->group_id = group_id;
    1682                 :   15490000 :   store_info->offset = offset;
    1683                 :   15490000 :   store_info->width = width;
    1684                 :   15490000 :   store_info->is_set = GET_CODE (body) == SET;
    1685                 :   15490000 :   store_info->rhs = rhs;
    1686                 :   15490000 :   store_info->const_rhs = const_rhs;
    1687                 :   15490000 :   store_info->redundant_reason = redundant_reason;
    1688                 :            : 
    1689                 :            :   /* If this is a clobber, we return 0.  We will only be able to
    1690                 :            :      delete this insn if there is only one store USED store, but we
    1691                 :            :      can use the clobber to delete other stores earlier.  */
    1692                 :   15490000 :   return store_info->is_set ? 1 : 0;
    1693                 :            : }
    1694                 :            : 
    1695                 :            : 
    1696                 :            : static void
    1697                 :          0 : dump_insn_info (const char * start, insn_info_t insn_info)
    1698                 :            : {
    1699                 :          0 :   fprintf (dump_file, "%s insn=%d %s\n", start,
    1700                 :          0 :            INSN_UID (insn_info->insn),
    1701                 :          0 :            insn_info->store_rec ? "has store" : "naked");
    1702                 :          0 : }
    1703                 :            : 
    1704                 :            : 
    1705                 :            : /* If the modes are different and the value's source and target do not
    1706                 :            :    line up, we need to extract the value from lower part of the rhs of
    1707                 :            :    the store, shift it, and then put it into a form that can be shoved
    1708                 :            :    into the read_insn.  This function generates a right SHIFT of a
    1709                 :            :    value that is at least ACCESS_SIZE bytes wide of READ_MODE.  The
    1710                 :            :    shift sequence is returned or NULL if we failed to find a
    1711                 :            :    shift.  */
    1712                 :            : 
    1713                 :            : static rtx
    1714                 :      58858 : find_shift_sequence (poly_int64 access_size,
    1715                 :            :                      store_info *store_info,
    1716                 :            :                      machine_mode read_mode,
    1717                 :            :                      poly_int64 shift, bool speed, bool require_cst)
    1718                 :            : {
    1719                 :      58858 :   machine_mode store_mode = GET_MODE (store_info->mem);
    1720                 :      58858 :   scalar_int_mode new_mode;
    1721                 :      58858 :   rtx read_reg = NULL;
    1722                 :            : 
    1723                 :            :   /* Some machines like the x86 have shift insns for each size of
    1724                 :            :      operand.  Other machines like the ppc or the ia-64 may only have
    1725                 :            :      shift insns that shift values within 32 or 64 bit registers.
    1726                 :            :      This loop tries to find the smallest shift insn that will right
    1727                 :            :      justify the value we want to read but is available in one insn on
    1728                 :            :      the machine.  */
    1729                 :            : 
    1730                 :      58858 :   opt_scalar_int_mode new_mode_iter;
    1731                 :      62366 :   FOR_EACH_MODE_FROM (new_mode_iter,
    1732                 :            :                       smallest_int_mode_for_size (access_size * BITS_PER_UNIT))
    1733                 :            :     {
    1734                 :      62366 :       rtx target, new_reg, new_lhs;
    1735                 :      62366 :       rtx_insn *shift_seq, *insn;
    1736                 :      62366 :       int cost;
    1737                 :            : 
    1738                 :      62366 :       new_mode = new_mode_iter.require ();
    1739                 :     125504 :       if (GET_MODE_BITSIZE (new_mode) > BITS_PER_WORD)
    1740                 :            :         break;
    1741                 :            : 
    1742                 :            :       /* If a constant was stored into memory, try to simplify it here,
    1743                 :            :          otherwise the cost of the shift might preclude this optimization
    1744                 :            :          e.g. at -Os, even when no actual shift will be needed.  */
    1745                 :      19941 :       if (store_info->const_rhs)
    1746                 :            :         {
    1747                 :      14108 :           poly_uint64 byte = subreg_lowpart_offset (new_mode, store_mode);
    1748                 :      14108 :           rtx ret = simplify_subreg (new_mode, store_info->const_rhs,
    1749                 :            :                                      store_mode, byte);
    1750                 :      14108 :           if (ret && CONSTANT_P (ret))
    1751                 :            :             {
    1752                 :      14107 :               rtx shift_rtx = gen_int_shift_amount (new_mode, shift);
    1753                 :      14107 :               ret = simplify_const_binary_operation (LSHIFTRT, new_mode,
    1754                 :            :                                                      ret, shift_rtx);
    1755                 :      14107 :               if (ret && CONSTANT_P (ret))
    1756                 :            :                 {
    1757                 :      14107 :                   byte = subreg_lowpart_offset (read_mode, new_mode);
    1758                 :      14107 :                   ret = simplify_subreg (read_mode, ret, new_mode, byte);
    1759                 :      14107 :                   if (ret && CONSTANT_P (ret)
    1760                 :      28214 :                       && (set_src_cost (ret, read_mode, speed)
    1761                 :            :                           <= COSTS_N_INSNS (1)))
    1762                 :      14107 :                     return ret;
    1763                 :            :                 }
    1764                 :            :             }
    1765                 :            :         }
    1766                 :            : 
    1767                 :       5834 :       if (require_cst)
    1768                 :            :         return NULL_RTX;
    1769                 :            : 
    1770                 :            :       /* Try a wider mode if truncating the store mode to NEW_MODE
    1771                 :            :          requires a real instruction.  */
    1772                 :      17502 :       if (maybe_lt (GET_MODE_SIZE (new_mode), GET_MODE_SIZE (store_mode))
    1773                 :       5834 :           && !TRULY_NOOP_TRUNCATION_MODES_P (new_mode, store_mode))
    1774                 :          0 :         continue;
    1775                 :            : 
    1776                 :            :       /* Also try a wider mode if the necessary punning is either not
    1777                 :            :          desirable or not possible.  */
    1778                 :       9045 :       if (!CONSTANT_P (store_info->rhs)
    1779                 :       5834 :           && !targetm.modes_tieable_p (new_mode, store_mode))
    1780                 :       3211 :         continue;
    1781                 :            : 
    1782                 :       2623 :       new_reg = gen_reg_rtx (new_mode);
    1783                 :            : 
    1784                 :       2623 :       start_sequence ();
    1785                 :            : 
    1786                 :            :       /* In theory we could also check for an ashr.  Ian Taylor knows
    1787                 :            :          of one dsp where the cost of these two was not the same.  But
    1788                 :            :          this really is a rare case anyway.  */
    1789                 :       2623 :       target = expand_binop (new_mode, lshr_optab, new_reg,
    1790                 :            :                              gen_int_shift_amount (new_mode, shift),
    1791                 :            :                              new_reg, 1, OPTAB_DIRECT);
    1792                 :            : 
    1793                 :       2623 :       shift_seq = get_insns ();
    1794                 :       2623 :       end_sequence ();
    1795                 :            : 
    1796                 :       2623 :       if (target != new_reg || shift_seq == NULL)
    1797                 :          0 :         continue;
    1798                 :            : 
    1799                 :            :       cost = 0;
    1800                 :       5246 :       for (insn = shift_seq; insn != NULL_RTX; insn = NEXT_INSN (insn))
    1801                 :       2623 :         if (INSN_P (insn))
    1802                 :       2623 :           cost += insn_cost (insn, speed);
    1803                 :            : 
    1804                 :            :       /* The computation up to here is essentially independent
    1805                 :            :          of the arguments and could be precomputed.  It may
    1806                 :            :          not be worth doing so.  We could precompute if
    1807                 :            :          worthwhile or at least cache the results.  The result
    1808                 :            :          technically depends on both SHIFT and ACCESS_SIZE,
    1809                 :            :          but in practice the answer will depend only on ACCESS_SIZE.  */
    1810                 :            : 
    1811                 :       2623 :       if (cost > COSTS_N_INSNS (1))
    1812                 :        297 :         continue;
    1813                 :            : 
    1814                 :       2326 :       new_lhs = extract_low_bits (new_mode, store_mode,
    1815                 :            :                                   copy_rtx (store_info->rhs));
    1816                 :       2326 :       if (new_lhs == NULL_RTX)
    1817                 :          0 :         continue;
    1818                 :            : 
    1819                 :            :       /* We found an acceptable shift.  Generate a move to
    1820                 :            :          take the value from the store and put it into the
    1821                 :            :          shift pseudo, then shift it, then generate another
    1822                 :            :          move to put in into the target of the read.  */
    1823                 :       2326 :       emit_move_insn (new_reg, new_lhs);
    1824                 :       2326 :       emit_insn (shift_seq);
    1825                 :       2326 :       read_reg = extract_low_bits (read_mode, new_mode, new_reg);
    1826                 :       2326 :       break;
    1827                 :            :     }
    1828                 :            : 
    1829                 :            :   return read_reg;
    1830                 :            : }
    1831                 :            : 
    1832                 :            : 
    1833                 :            : /* Call back for note_stores to find the hard regs set or clobbered by
    1834                 :            :    insn.  Data is a bitmap of the hardregs set so far.  */
    1835                 :            : 
    1836                 :            : static void
    1837                 :      95668 : look_for_hardregs (rtx x, const_rtx pat ATTRIBUTE_UNUSED, void *data)
    1838                 :            : {
    1839                 :      95668 :   bitmap regs_set = (bitmap) data;
    1840                 :            : 
    1841                 :      95668 :   if (REG_P (x)
    1842                 :      95668 :       && HARD_REGISTER_P (x))
    1843                 :       2285 :     bitmap_set_range (regs_set, REGNO (x), REG_NREGS (x));
    1844                 :      95668 : }
    1845                 :            : 
    1846                 :            : /* Helper function for replace_read and record_store.
    1847                 :            :    Attempt to return a value of mode READ_MODE stored in STORE_INFO,
    1848                 :            :    consisting of READ_WIDTH bytes starting from READ_OFFSET.  Return NULL
    1849                 :            :    if not successful.  If REQUIRE_CST is true, return always constant.  */
    1850                 :            : 
    1851                 :            : static rtx
    1852                 :     134706 : get_stored_val (store_info *store_info, machine_mode read_mode,
    1853                 :            :                 poly_int64 read_offset, poly_int64 read_width,
    1854                 :            :                 basic_block bb, bool require_cst)
    1855                 :            : {
    1856                 :     134706 :   machine_mode store_mode = GET_MODE (store_info->mem);
    1857                 :     134706 :   poly_int64 gap;
    1858                 :     134706 :   rtx read_reg;
    1859                 :            : 
    1860                 :            :   /* To get here the read is within the boundaries of the write so
    1861                 :            :      shift will never be negative.  Start out with the shift being in
    1862                 :            :      bytes.  */
    1863                 :     134706 :   if (store_mode == BLKmode)
    1864                 :     134706 :     gap = 0;
    1865                 :     123669 :   else if (BYTES_BIG_ENDIAN)
    1866                 :            :     gap = ((store_info->offset + store_info->width)
    1867                 :            :            - (read_offset + read_width));
    1868                 :            :   else
    1869                 :     123669 :     gap = read_offset - store_info->offset;
    1870                 :            : 
    1871                 :     134706 :   if (gap.is_constant () && maybe_ne (gap, 0))
    1872                 :            :     {
    1873                 :      58858 :       poly_int64 shift = gap * BITS_PER_UNIT;
    1874                 :     117716 :       poly_int64 access_size = GET_MODE_SIZE (read_mode) + gap;
    1875                 :      58858 :       read_reg = find_shift_sequence (access_size, store_info, read_mode,
    1876                 :      58858 :                                       shift, optimize_bb_for_speed_p (bb),
    1877                 :            :                                       require_cst);
    1878                 :            :     }
    1879                 :      75848 :   else if (store_mode == BLKmode)
    1880                 :            :     {
    1881                 :            :       /* The store is a memset (addr, const_val, const_size).  */
    1882                 :      11037 :       gcc_assert (CONST_INT_P (store_info->rhs));
    1883                 :      11037 :       scalar_int_mode int_store_mode;
    1884                 :      11037 :       if (!int_mode_for_mode (read_mode).exists (&int_store_mode))
    1885                 :            :         read_reg = NULL_RTX;
    1886                 :      11037 :       else if (store_info->rhs == const0_rtx)
    1887                 :      11036 :         read_reg = extract_low_bits (read_mode, int_store_mode, const0_rtx);
    1888                 :          2 :       else if (GET_MODE_BITSIZE (int_store_mode) > HOST_BITS_PER_WIDE_INT
    1889                 :            :                || BITS_PER_UNIT >= HOST_BITS_PER_WIDE_INT)
    1890                 :            :         read_reg = NULL_RTX;
    1891                 :            :       else
    1892                 :            :         {
    1893                 :          1 :           unsigned HOST_WIDE_INT c
    1894                 :          1 :             = INTVAL (store_info->rhs)
    1895                 :          1 :               & ((HOST_WIDE_INT_1 << BITS_PER_UNIT) - 1);
    1896                 :          1 :           int shift = BITS_PER_UNIT;
    1897                 :          4 :           while (shift < HOST_BITS_PER_WIDE_INT)
    1898                 :            :             {
    1899                 :          3 :               c |= (c << shift);
    1900                 :          3 :               shift <<= 1;
    1901                 :            :             }
    1902                 :          1 :           read_reg = gen_int_mode (c, int_store_mode);
    1903                 :          1 :           read_reg = extract_low_bits (read_mode, int_store_mode, read_reg);
    1904                 :            :         }
    1905                 :            :     }
    1906                 :      64811 :   else if (store_info->const_rhs
    1907                 :       3741 :            && (require_cst
    1908                 :       1704 :                || GET_MODE_CLASS (read_mode) != GET_MODE_CLASS (store_mode)))
    1909                 :       2683 :     read_reg = extract_low_bits (read_mode, store_mode,
    1910                 :            :                                  copy_rtx (store_info->const_rhs));
    1911                 :            :   else
    1912                 :      62128 :     read_reg = extract_low_bits (read_mode, store_mode,
    1913                 :            :                                  copy_rtx (store_info->rhs));
    1914                 :     134706 :   if (require_cst && read_reg && !CONSTANT_P (read_reg))
    1915                 :          0 :     read_reg = NULL_RTX;
    1916                 :     134706 :   return read_reg;
    1917                 :            : }
    1918                 :            : 
    1919                 :            : /* Take a sequence of:
    1920                 :            :      A <- r1
    1921                 :            :      ...
    1922                 :            :      ... <- A
    1923                 :            : 
    1924                 :            :    and change it into
    1925                 :            :    r2 <- r1
    1926                 :            :    A <- r1
    1927                 :            :    ...
    1928                 :            :    ... <- r2
    1929                 :            : 
    1930                 :            :    or
    1931                 :            : 
    1932                 :            :    r3 <- extract (r1)
    1933                 :            :    r3 <- r3 >> shift
    1934                 :            :    r2 <- extract (r3)
    1935                 :            :    ... <- r2
    1936                 :            : 
    1937                 :            :    or
    1938                 :            : 
    1939                 :            :    r2 <- extract (r1)
    1940                 :            :    ... <- r2
    1941                 :            : 
    1942                 :            :    Depending on the alignment and the mode of the store and
    1943                 :            :    subsequent load.
    1944                 :            : 
    1945                 :            : 
    1946                 :            :    The STORE_INFO and STORE_INSN are for the store and READ_INFO
    1947                 :            :    and READ_INSN are for the read.  Return true if the replacement
    1948                 :            :    went ok.  */
    1949                 :            : 
    1950                 :            : static bool
    1951                 :     106359 : replace_read (store_info *store_info, insn_info_t store_insn,
    1952                 :            :               read_info_t read_info, insn_info_t read_insn, rtx *loc,
    1953                 :            :               bitmap regs_live)
    1954                 :            : {
    1955                 :     106359 :   machine_mode store_mode = GET_MODE (store_info->mem);
    1956                 :     106359 :   machine_mode read_mode = GET_MODE (read_info->mem);
    1957                 :     106359 :   rtx_insn *insns, *this_insn;
    1958                 :     106359 :   rtx read_reg;
    1959                 :     106359 :   basic_block bb;
    1960                 :            : 
    1961                 :     106359 :   if (!dbg_cnt (dse))
    1962                 :            :     return false;
    1963                 :            : 
    1964                 :            :   /* Create a sequence of instructions to set up the read register.
    1965                 :            :      This sequence goes immediately before the store and its result
    1966                 :            :      is read by the load.
    1967                 :            : 
    1968                 :            :      We need to keep this in perspective.  We are replacing a read
    1969                 :            :      with a sequence of insns, but the read will almost certainly be
    1970                 :            :      in cache, so it is not going to be an expensive one.  Thus, we
    1971                 :            :      are not willing to do a multi insn shift or worse a subroutine
    1972                 :            :      call to get rid of the read.  */
    1973                 :     106359 :   if (dump_file && (dump_flags & TDF_DETAILS))
    1974                 :          0 :     fprintf (dump_file, "trying to replace %smode load in insn %d"
    1975                 :            :              " from %smode store in insn %d\n",
    1976                 :          0 :              GET_MODE_NAME (read_mode), INSN_UID (read_insn->insn),
    1977                 :          0 :              GET_MODE_NAME (store_mode), INSN_UID (store_insn->insn));
    1978                 :     106359 :   start_sequence ();
    1979                 :     106359 :   bb = BLOCK_FOR_INSN (read_insn->insn);
    1980                 :     106359 :   read_reg = get_stored_val (store_info,
    1981                 :            :                              read_mode, read_info->offset, read_info->width,
    1982                 :            :                              bb, false);
    1983                 :     106359 :   if (read_reg == NULL_RTX)
    1984                 :            :     {
    1985                 :      45324 :       end_sequence ();
    1986                 :      45324 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1987                 :          0 :         fprintf (dump_file, " -- could not extract bits of stored value\n");
    1988                 :      45324 :       return false;
    1989                 :            :     }
    1990                 :            :   /* Force the value into a new register so that it won't be clobbered
    1991                 :            :      between the store and the load.  */
    1992                 :      61035 :   read_reg = copy_to_mode_reg (read_mode, read_reg);
    1993                 :      61035 :   insns = get_insns ();
    1994                 :      61035 :   end_sequence ();
    1995                 :            : 
    1996                 :      61035 :   if (insns != NULL_RTX)
    1997                 :            :     {
    1998                 :            :       /* Now we have to scan the set of new instructions to see if the
    1999                 :            :          sequence contains and sets of hardregs that happened to be
    2000                 :            :          live at this point.  For instance, this can happen if one of
    2001                 :            :          the insns sets the CC and the CC happened to be live at that
    2002                 :            :          point.  This does occasionally happen, see PR 37922.  */
    2003                 :      61035 :       bitmap regs_set = BITMAP_ALLOC (&reg_obstack);
    2004                 :            : 
    2005                 :      61035 :       for (this_insn = insns;
    2006                 :     247801 :            this_insn != NULL_RTX; this_insn = NEXT_INSN (this_insn))
    2007                 :            :         {
    2008                 :      93389 :           if (insn_invalid_p (this_insn, false))
    2009                 :            :             {
    2010                 :          6 :               if (dump_file && (dump_flags & TDF_DETAILS))
    2011                 :            :                 {
    2012                 :          0 :                   fprintf (dump_file, " -- replacing the loaded MEM with ");
    2013                 :          0 :                   print_simple_rtl (dump_file, read_reg);
    2014                 :          0 :                   fprintf (dump_file, " led to an invalid instruction\n");
    2015                 :            :                 }
    2016                 :          6 :               BITMAP_FREE (regs_set);
    2017                 :          6 :               return false;
    2018                 :            :             }
    2019                 :      93383 :           note_stores (this_insn, look_for_hardregs, regs_set);
    2020                 :            :         }
    2021                 :            : 
    2022                 :      61029 :       bitmap_and_into (regs_set, regs_live);
    2023                 :      61029 :       if (!bitmap_empty_p (regs_set))
    2024                 :            :         {
    2025                 :          0 :           if (dump_file && (dump_flags & TDF_DETAILS))
    2026                 :            :             {
    2027                 :          0 :               fprintf (dump_file, "abandoning replacement because sequence "
    2028                 :            :                                   "clobbers live hardregs:");
    2029                 :          0 :               df_print_regset (dump_file, regs_set);
    2030                 :            :             }
    2031                 :            : 
    2032                 :          0 :           BITMAP_FREE (regs_set);
    2033                 :          0 :           return false;
    2034                 :            :         }
    2035                 :      61029 :       BITMAP_FREE (regs_set);
    2036                 :            :     }
    2037                 :            : 
    2038                 :      61029 :   subrtx_iterator::array_type array;
    2039                 :     301439 :   FOR_EACH_SUBRTX (iter, array, *loc, NONCONST)
    2040                 :            :     {
    2041                 :     240416 :       const_rtx x = *iter;
    2042                 :     240416 :       if (GET_RTX_CLASS (GET_CODE (x)) == RTX_AUTOINC)
    2043                 :            :         {
    2044                 :          6 :           if (dump_file && (dump_flags & TDF_DETAILS))
    2045                 :          0 :             fprintf (dump_file, " -- replacing the MEM failed due to address "
    2046                 :            :                                 "side-effects\n");
    2047                 :          6 :           return false;
    2048                 :            :         }
    2049                 :            :     }
    2050                 :            : 
    2051                 :      61023 :   if (validate_change (read_insn->insn, loc, read_reg, 0))
    2052                 :            :     {
    2053                 :      44075 :       deferred_change *change = deferred_change_pool.allocate ();
    2054                 :            : 
    2055                 :            :       /* Insert this right before the store insn where it will be safe
    2056                 :            :          from later insns that might change it before the read.  */
    2057                 :      44075 :       emit_insn_before (insns, store_insn->insn);
    2058                 :            : 
    2059                 :            :       /* And now for the kludge part: cselib croaks if you just
    2060                 :            :          return at this point.  There are two reasons for this:
    2061                 :            : 
    2062                 :            :          1) Cselib has an idea of how many pseudos there are and
    2063                 :            :          that does not include the new ones we just added.
    2064                 :            : 
    2065                 :            :          2) Cselib does not know about the move insn we added
    2066                 :            :          above the store_info, and there is no way to tell it
    2067                 :            :          about it, because it has "moved on".
    2068                 :            : 
    2069                 :            :          Problem (1) is fixable with a certain amount of engineering.
    2070                 :            :          Problem (2) is requires starting the bb from scratch.  This
    2071                 :            :          could be expensive.
    2072                 :            : 
    2073                 :            :          So we are just going to have to lie.  The move/extraction
    2074                 :            :          insns are not really an issue, cselib did not see them.  But
    2075                 :            :          the use of the new pseudo read_insn is a real problem because
    2076                 :            :          cselib has not scanned this insn.  The way that we solve this
    2077                 :            :          problem is that we are just going to put the mem back for now
    2078                 :            :          and when we are finished with the block, we undo this.  We
    2079                 :            :          keep a table of mems to get rid of.  At the end of the basic
    2080                 :            :          block we can put them back.  */
    2081                 :            : 
    2082                 :      44075 :       *loc = read_info->mem;
    2083                 :      44075 :       change->next = deferred_change_list;
    2084                 :      44075 :       deferred_change_list = change;
    2085                 :      44075 :       change->loc = loc;
    2086                 :      44075 :       change->reg = read_reg;
    2087                 :            : 
    2088                 :            :       /* Get rid of the read_info, from the point of view of the
    2089                 :            :          rest of dse, play like this read never happened.  */
    2090                 :      44075 :       read_insn->read_rec = read_info->next;
    2091                 :      44075 :       read_info_type_pool.remove (read_info);
    2092                 :      44075 :       if (dump_file && (dump_flags & TDF_DETAILS))
    2093                 :            :         {
    2094                 :          0 :           fprintf (dump_file, " -- replaced the loaded MEM with ");
    2095                 :          0 :           print_simple_rtl (dump_file, read_reg);
    2096                 :          0 :           fprintf (dump_file, "\n");
    2097                 :            :         }
    2098                 :      44075 :       return true;
    2099                 :            :     }
    2100                 :            :   else
    2101                 :            :     {
    2102                 :      16948 :       if (dump_file && (dump_flags & TDF_DETAILS))
    2103                 :            :         {
    2104                 :          0 :           fprintf (dump_file, " -- replacing the loaded MEM with ");
    2105                 :          0 :           print_simple_rtl (dump_file, read_reg);
    2106                 :          0 :           fprintf (dump_file, " led to an invalid instruction\n");
    2107                 :            :         }
    2108                 :      16948 :       return false;
    2109                 :            :     }
    2110                 :            : }
    2111                 :            : 
    2112                 :            : /* Check the address of MEM *LOC and kill any appropriate stores that may
    2113                 :            :    be active.  */
    2114                 :            : 
    2115                 :            : static void
    2116                 :   20748700 : check_mem_read_rtx (rtx *loc, bb_info_t bb_info)
    2117                 :            : {
    2118                 :   20748700 :   rtx mem = *loc, mem_addr;
    2119                 :   20748700 :   insn_info_t insn_info;
    2120                 :   20748700 :   poly_int64 offset = 0;
    2121                 :   20748700 :   poly_int64 width = 0;
    2122                 :   20748700 :   cselib_val *base = NULL;
    2123                 :   20748700 :   int group_id;
    2124                 :   20748700 :   read_info_t read_info;
    2125                 :            : 
    2126                 :   20748700 :   insn_info = bb_info->last_insn;
    2127                 :            : 
    2128                 :   20748700 :   if ((MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
    2129                 :   20748700 :       || MEM_VOLATILE_P (mem))
    2130                 :            :     {
    2131                 :     977546 :       if (crtl->stack_protect_guard
    2132                 :        808 :           && (MEM_EXPR (mem) == crtl->stack_protect_guard
    2133                 :        544 :               || (crtl->stack_protect_guard_decl
    2134                 :        544 :                   && MEM_EXPR (mem) == crtl->stack_protect_guard_decl))
    2135                 :     978354 :           && MEM_VOLATILE_P (mem))
    2136                 :            :         {
    2137                 :            :           /* This is either the stack protector canary on the stack,
    2138                 :            :              which ought to be written by a MEM_VOLATILE_P store and
    2139                 :            :              thus shouldn't be deleted and is read at the very end of
    2140                 :            :              function, but shouldn't conflict with any other store.
    2141                 :            :              Or it is __stack_chk_guard variable or TLS or whatever else
    2142                 :            :              MEM holding the canary value, which really shouldn't be
    2143                 :            :              ever modified in -fstack-protector* protected functions,
    2144                 :            :              otherwise the prologue store wouldn't match the epilogue
    2145                 :            :              check.  */
    2146                 :        808 :           if (dump_file && (dump_flags & TDF_DETAILS))
    2147                 :          0 :             fprintf (dump_file, " stack protector canary read ignored.\n");
    2148                 :        808 :           insn_info->cannot_delete = true;
    2149                 :    2260780 :           return;
    2150                 :            :         }
    2151                 :            : 
    2152                 :     976738 :       if (dump_file && (dump_flags & TDF_DETAILS))
    2153                 :          0 :         fprintf (dump_file, " adding wild read, volatile or barrier.\n");
    2154                 :     976738 :       add_wild_read (bb_info);
    2155                 :     976738 :       insn_info->cannot_delete = true;
    2156                 :     976738 :       return;
    2157                 :            :     }
    2158                 :            : 
    2159                 :            :   /* If it is reading readonly mem, then there can be no conflict with
    2160                 :            :      another write. */
    2161                 :   19771100 :   if (MEM_READONLY_P (mem))
    2162                 :            :     return;
    2163                 :            : 
    2164                 :   18669000 :   if (!canon_address (mem, &group_id, &offset, &base))
    2165                 :            :     {
    2166                 :     136952 :       if (dump_file && (dump_flags & TDF_DETAILS))
    2167                 :          0 :         fprintf (dump_file, " adding wild read, canon_address failure.\n");
    2168                 :     136952 :       add_wild_read (bb_info);
    2169                 :     136952 :       return;
    2170                 :            :     }
    2171                 :            : 
    2172                 :   18532000 :   if (GET_MODE (mem) == BLKmode)
    2173                 :      48623 :     width = -1;
    2174                 :            :   else
    2175                 :   36966800 :     width = GET_MODE_SIZE (GET_MODE (mem));
    2176                 :            : 
    2177                 :   55547500 :   if (!endpoint_representable_p (offset, known_eq (width, -1) ? 1 : width))
    2178                 :            :     {
    2179                 :         82 :       if (dump_file && (dump_flags & TDF_DETAILS))
    2180                 :          0 :         fprintf (dump_file, " adding wild read, due to overflow.\n");
    2181                 :         82 :       add_wild_read (bb_info);
    2182                 :         82 :       return;
    2183                 :            :     }
    2184                 :            : 
    2185                 :   18532000 :   read_info = read_info_type_pool.allocate ();
    2186                 :   18532000 :   read_info->group_id = group_id;
    2187                 :   18532000 :   read_info->mem = mem;
    2188                 :   18532000 :   read_info->offset = offset;
    2189                 :   18532000 :   read_info->width = width;
    2190                 :   18532000 :   read_info->next = insn_info->read_rec;
    2191                 :   18532000 :   insn_info->read_rec = read_info;
    2192                 :   18532000 :   if (group_id < 0)
    2193                 :    8653030 :     mem_addr = base->val_rtx;
    2194                 :            :   else
    2195                 :            :     {
    2196                 :    9878930 :       group_info *group = rtx_group_vec[group_id];
    2197                 :    9878930 :       mem_addr = group->canon_base_addr;
    2198                 :            :     }
    2199                 :   18532000 :   if (maybe_ne (offset, 0))
    2200                 :    8146230 :     mem_addr = plus_constant (get_address_mode (mem), mem_addr, offset);
    2201                 :            : 
    2202                 :   18532000 :   if (group_id >= 0)
    2203                 :            :     {
    2204                 :            :       /* This is the restricted case where the base is a constant or
    2205                 :            :          the frame pointer and offset is a constant.  */
    2206                 :    9878930 :       insn_info_t i_ptr = active_local_stores;
    2207                 :    9878930 :       insn_info_t last = NULL;
    2208                 :            : 
    2209                 :    9878930 :       if (dump_file && (dump_flags & TDF_DETAILS))
    2210                 :            :         {
    2211                 :          0 :           if (!known_size_p (width))
    2212                 :          0 :             fprintf (dump_file, " processing const load gid=%d[BLK]\n",
    2213                 :            :                      group_id);
    2214                 :            :           else
    2215                 :            :             {
    2216                 :          0 :               fprintf (dump_file, " processing const load gid=%d", group_id);
    2217                 :          0 :               print_range (dump_file, offset, width);
    2218                 :          0 :               fprintf (dump_file, "\n");
    2219                 :            :             }
    2220                 :            :         }
    2221                 :            : 
    2222                 :   29300900 :       while (i_ptr)
    2223                 :            :         {
    2224                 :   19465300 :           bool remove = false;
    2225                 :   19465300 :           store_info *store_info = i_ptr->store_rec;
    2226                 :            : 
    2227                 :            :           /* Skip the clobbers.  */
    2228                 :   19465300 :           while (!store_info->is_set)
    2229                 :          0 :             store_info = store_info->next;
    2230                 :            : 
    2231                 :            :           /* There are three cases here.  */
    2232                 :   19465300 :           if (store_info->group_id < 0)
    2233                 :            :             /* We have a cselib store followed by a read from a
    2234                 :            :                const base. */
    2235                 :    7658160 :             remove
    2236                 :    7658160 :               = canon_true_dependence (store_info->mem,
    2237                 :    7658160 :                                        GET_MODE (store_info->mem),
    2238                 :            :                                        store_info->mem_addr,
    2239                 :            :                                        mem, mem_addr);
    2240                 :            : 
    2241                 :   11807100 :           else if (group_id == store_info->group_id)
    2242                 :            :             {
    2243                 :            :               /* This is a block mode load.  We may get lucky and
    2244                 :            :                  canon_true_dependence may save the day.  */
    2245                 :    7483520 :               if (!known_size_p (width))
    2246                 :      32871 :                 remove
    2247                 :      32871 :                   = canon_true_dependence (store_info->mem,
    2248                 :      32871 :                                            GET_MODE (store_info->mem),
    2249                 :            :                                            store_info->mem_addr,
    2250                 :            :                                            mem, mem_addr);
    2251                 :            : 
    2252                 :            :               /* If this read is just reading back something that we just
    2253                 :            :                  stored, rewrite the read.  */
    2254                 :            :               else
    2255                 :            :                 {
    2256                 :    7450650 :                   if (store_info->rhs
    2257                 :   10288800 :                       && known_subrange_p (offset, width, store_info->offset,
    2258                 :    2775760 :                                            store_info->width)
    2259                 :     105739 :                       && all_positions_needed_p (store_info,
    2260                 :            :                                                  offset - store_info->offset,
    2261                 :            :                                                  width)
    2262                 :    7555670 :                       && replace_read (store_info, i_ptr, read_info,
    2263                 :            :                                        insn_info, loc, bb_info->regs_live))
    2264                 :            :                     return;
    2265                 :            : 
    2266                 :            :                   /* The bases are the same, just see if the offsets
    2267                 :            :                      could overlap.  */
    2268                 :    7407330 :                   if (ranges_maybe_overlap_p (offset, width,
    2269                 :    7407330 :                                               store_info->offset,
    2270                 :    7407330 :                                               store_info->width))
    2271                 :            :                     remove = true;
    2272                 :            :                 }
    2273                 :            :             }
    2274                 :            : 
    2275                 :            :           /* else
    2276                 :            :              The else case that is missing here is that the
    2277                 :            :              bases are constant but different.  There is nothing
    2278                 :            :              to do here because there is no overlap.  */
    2279                 :            : 
    2280                 :    7691040 :           if (remove)
    2281                 :            :             {
    2282                 :    4643460 :               if (dump_file && (dump_flags & TDF_DETAILS))
    2283                 :          0 :                 dump_insn_info ("removing from active", i_ptr);
    2284                 :            : 
    2285                 :    4643460 :               active_local_stores_len--;
    2286                 :    4643460 :               if (last)
    2287                 :     277550 :                 last->next_local_store = i_ptr->next_local_store;
    2288                 :            :               else
    2289                 :    4365920 :                 active_local_stores = i_ptr->next_local_store;
    2290                 :            :             }
    2291                 :            :           else
    2292                 :            :             last = i_ptr;
    2293                 :   19422000 :           i_ptr = i_ptr->next_local_store;
    2294                 :            :         }
    2295                 :            :     }
    2296                 :            :   else
    2297                 :            :     {
    2298                 :    8653030 :       insn_info_t i_ptr = active_local_stores;
    2299                 :    8653030 :       insn_info_t last = NULL;
    2300                 :    8653030 :       if (dump_file && (dump_flags & TDF_DETAILS))
    2301                 :            :         {
    2302                 :          0 :           fprintf (dump_file, " processing cselib load mem:");
    2303                 :          0 :           print_inline_rtx (dump_file, mem, 0);
    2304                 :          0 :           fprintf (dump_file, "\n");
    2305                 :            :         }
    2306                 :            : 
    2307                 :   29271300 :       while (i_ptr)
    2308                 :            :         {
    2309                 :   20619000 :           bool remove = false;
    2310                 :   20619000 :           store_info *store_info = i_ptr->store_rec;
    2311                 :            : 
    2312                 :   20619000 :           if (dump_file && (dump_flags & TDF_DETAILS))
    2313                 :          0 :             fprintf (dump_file, " processing cselib load against insn %d\n",
    2314                 :          0 :                      INSN_UID (i_ptr->insn));
    2315                 :            : 
    2316                 :            :           /* Skip the clobbers.  */
    2317                 :   20619000 :           while (!store_info->is_set)
    2318                 :          0 :             store_info = store_info->next;
    2319                 :            : 
    2320                 :            :           /* If this read is just reading back something that we just
    2321                 :            :              stored, rewrite the read.  */
    2322                 :   20619000 :           if (store_info->rhs
    2323                 :     917130 :               && store_info->group_id == -1
    2324                 :     415184 :               && store_info->cse_base == base
    2325                 :   20682200 :               && known_subrange_p (offset, width, store_info->offset,
    2326                 :      62602 :                                    store_info->width)
    2327                 :       1353 :               && all_positions_needed_p (store_info,
    2328                 :            :                                          offset - store_info->offset, width)
    2329                 :   20620400 :               && replace_read (store_info, i_ptr,  read_info, insn_info, loc,
    2330                 :            :                                bb_info->regs_live))
    2331                 :            :             return;
    2332                 :            : 
    2333                 :   41236500 :           remove = canon_true_dependence (store_info->mem,
    2334                 :   20618300 :                                           GET_MODE (store_info->mem),
    2335                 :            :                                           store_info->mem_addr,
    2336                 :            :                                           mem, mem_addr);
    2337                 :            : 
    2338                 :   20618300 :           if (remove)
    2339                 :            :             {
    2340                 :    1033960 :               if (dump_file && (dump_flags & TDF_DETAILS))
    2341                 :          0 :                 dump_insn_info ("removing from active", i_ptr);
    2342                 :            : 
    2343                 :    1033960 :               active_local_stores_len--;
    2344                 :    1033960 :               if (last)
    2345                 :     185131 :                 last->next_local_store = i_ptr->next_local_store;
    2346                 :            :               else
    2347                 :     848825 :                 active_local_stores = i_ptr->next_local_store;
    2348                 :            :             }
    2349                 :            :           else
    2350                 :            :             last = i_ptr;
    2351                 :   20618300 :           i_ptr = i_ptr->next_local_store;
    2352                 :            :         }
    2353                 :            :     }
    2354                 :            : }
    2355                 :            : 
    2356                 :            : /* A note_uses callback in which DATA points the INSN_INFO for
    2357                 :            :    as check_mem_read_rtx.  Nullify the pointer if i_m_r_m_r returns
    2358                 :            :    true for any part of *LOC.  */
    2359                 :            : 
    2360                 :            : static void
    2361                 :   97277400 : check_mem_read_use (rtx *loc, void *data)
    2362                 :            : {
    2363                 :   97277400 :   subrtx_ptr_iterator::array_type array;
    2364                 :  352186000 :   FOR_EACH_SUBRTX_PTR (iter, array, loc, NONCONST)
    2365                 :            :     {
    2366                 :  254909000 :       rtx *loc = *iter;
    2367                 :  254909000 :       if (MEM_P (*loc))
    2368                 :   20748700 :         check_mem_read_rtx (loc, (bb_info_t) data);
    2369                 :            :     }
    2370                 :   97277400 : }
    2371                 :            : 
    2372                 :            : 
    2373                 :            : /* Get arguments passed to CALL_INSN.  Return TRUE if successful.
    2374                 :            :    So far it only handles arguments passed in registers.  */
    2375                 :            : 
    2376                 :            : static bool
    2377                 :      18580 : get_call_args (rtx call_insn, tree fn, rtx *args, int nargs)
    2378                 :            : {
    2379                 :      18580 :   CUMULATIVE_ARGS args_so_far_v;
    2380                 :      18580 :   cumulative_args_t args_so_far;
    2381                 :      18580 :   tree arg;
    2382                 :      18580 :   int idx;
    2383                 :            : 
    2384                 :      18580 :   INIT_CUMULATIVE_ARGS (args_so_far_v, TREE_TYPE (fn), NULL_RTX, 0, 3);
    2385                 :      18580 :   args_so_far = pack_cumulative_args (&args_so_far_v);
    2386                 :            : 
    2387                 :      18580 :   arg = TYPE_ARG_TYPES (TREE_TYPE (fn));
    2388                 :      64234 :   for (idx = 0;
    2389                 :      64234 :        arg != void_list_node && idx < nargs;
    2390                 :      45654 :        arg = TREE_CHAIN (arg), idx++)
    2391                 :            :     {
    2392                 :      49016 :       scalar_int_mode mode;
    2393                 :      49016 :       rtx reg, link, tmp;
    2394                 :            : 
    2395                 :      49016 :       if (!is_int_mode (TYPE_MODE (TREE_VALUE (arg)), &mode))
    2396                 :       3362 :         return false;
    2397                 :            : 
    2398                 :      49016 :       function_arg_info arg (mode, /*named=*/true);
    2399                 :      49016 :       reg = targetm.calls.function_arg (args_so_far, arg);
    2400                 :      49016 :       if (!reg || !REG_P (reg) || GET_MODE (reg) != mode)
    2401                 :            :         return false;
    2402                 :            : 
    2403                 :      45664 :       for (link = CALL_INSN_FUNCTION_USAGE (call_insn);
    2404                 :     120598 :            link;
    2405                 :      74934 :            link = XEXP (link, 1))
    2406                 :     120588 :         if (GET_CODE (XEXP (link, 0)) == USE)
    2407                 :            :           {
    2408                 :      91338 :             scalar_int_mode arg_mode;
    2409                 :      91338 :             args[idx] = XEXP (XEXP (link, 0), 0);
    2410                 :      91338 :             if (REG_P (args[idx])
    2411                 :      91338 :                 && REGNO (args[idx]) == REGNO (reg)
    2412                 :     137002 :                 && (GET_MODE (args[idx]) == mode
    2413                 :      74944 :                     || (is_int_mode (GET_MODE (args[idx]), &arg_mode)
    2414                 :         10 :                         && (GET_MODE_SIZE (arg_mode) <= UNITS_PER_WORD)
    2415                 :         20 :                         && (GET_MODE_SIZE (arg_mode) > GET_MODE_SIZE (mode)))))
    2416                 :            :               break;
    2417                 :            :           }
    2418                 :      45664 :       if (!link)
    2419                 :            :         return false;
    2420                 :            : 
    2421                 :      45654 :       tmp = cselib_expand_value_rtx (args[idx], scratch, 5);
    2422                 :      45654 :       if (GET_MODE (args[idx]) != mode)
    2423                 :            :         {
    2424                 :          0 :           if (!tmp || !CONST_INT_P (tmp))
    2425                 :            :             return false;
    2426                 :          0 :           tmp = gen_int_mode (INTVAL (tmp), mode);
    2427                 :            :         }
    2428                 :      45654 :       if (tmp)
    2429                 :      45654 :         args[idx] = tmp;
    2430                 :            : 
    2431                 :      45654 :       targetm.calls.function_arg_advance (args_so_far, arg);
    2432                 :            :     }
    2433                 :      15218 :   if (arg != void_list_node || idx != nargs)
    2434                 :          0 :     return false;
    2435                 :            :   return true;
    2436                 :            : }
    2437                 :            : 
    2438                 :            : /* Return a bitmap of the fixed registers contained in IN.  */
    2439                 :            : 
    2440                 :            : static bitmap
    2441                 :   15427200 : copy_fixed_regs (const_bitmap in)
    2442                 :            : {
    2443                 :   15427200 :   bitmap ret;
    2444                 :            : 
    2445                 :   15427200 :   ret = ALLOC_REG_SET (NULL);
    2446                 :   15427200 :   bitmap_and (ret, in, bitmap_view<HARD_REG_SET> (fixed_reg_set));
    2447                 :   15427200 :   return ret;
    2448                 :            : }
    2449                 :            : 
    2450                 :            : /* Apply record_store to all candidate stores in INSN.  Mark INSN
    2451                 :            :    if some part of it is not a candidate store and assigns to a
    2452                 :            :    non-register target.  */
    2453                 :            : 
    2454                 :            : static void
    2455                 :  135656000 : scan_insn (bb_info_t bb_info, rtx_insn *insn, int max_active_local_stores)
    2456                 :            : {
    2457                 :  135656000 :   rtx body;
    2458                 :  135656000 :   insn_info_type *insn_info = insn_info_type_pool.allocate ();
    2459                 :  135656000 :   int mems_found = 0;
    2460                 :  135656000 :   memset (insn_info, 0, sizeof (struct insn_info_type));
    2461                 :            : 
    2462                 :  135656000 :   if (dump_file && (dump_flags & TDF_DETAILS))
    2463                 :          0 :     fprintf (dump_file, "\n**scanning insn=%d\n",
    2464                 :          0 :              INSN_UID (insn));
    2465                 :            : 
    2466                 :  135656000 :   insn_info->prev_insn = bb_info->last_insn;
    2467                 :  135656000 :   insn_info->insn = insn;
    2468                 :  135656000 :   bb_info->last_insn = insn_info;
    2469                 :            : 
    2470                 :  135656000 :   if (DEBUG_INSN_P (insn))
    2471                 :            :     {
    2472                 :   56026100 :       insn_info->cannot_delete = true;
    2473                 :   56026100 :       return;
    2474                 :            :     }
    2475                 :            : 
    2476                 :            :   /* Look at all of the uses in the insn.  */
    2477                 :   79630100 :   note_uses (&PATTERN (insn), check_mem_read_use, bb_info);
    2478                 :            : 
    2479                 :   79630100 :   if (CALL_P (insn))
    2480                 :            :     {
    2481                 :    6476510 :       bool const_call;
    2482                 :    6476510 :       rtx call, sym;
    2483                 :    6476510 :       tree memset_call = NULL_TREE;
    2484                 :            : 
    2485                 :    6476510 :       insn_info->cannot_delete = true;
    2486                 :            : 
    2487                 :            :       /* Const functions cannot do anything bad i.e. read memory,
    2488                 :            :          however, they can read their parameters which may have
    2489                 :            :          been pushed onto the stack.
    2490                 :            :          memset and bzero don't read memory either.  */
    2491                 :    6476510 :       const_call = RTL_CONST_CALL_P (insn);
    2492                 :    6476510 :       if (!const_call
    2493                 :    6254380 :           && (call = get_call_rtx_from (insn))
    2494                 :    6254380 :           && (sym = XEXP (XEXP (call, 0), 0))
    2495                 :    6254380 :           && GET_CODE (sym) == SYMBOL_REF
    2496                 :    6012830 :           && SYMBOL_REF_DECL (sym)
    2497                 :    5847460 :           && TREE_CODE (SYMBOL_REF_DECL (sym)) == FUNCTION_DECL
    2498                 :   12323900 :           && fndecl_built_in_p (SYMBOL_REF_DECL (sym), BUILT_IN_MEMSET))
    2499                 :    6476510 :         memset_call = SYMBOL_REF_DECL (sym);
    2500                 :            : 
    2501                 :    6476510 :       if (const_call || memset_call)
    2502                 :            :         {
    2503                 :     240710 :           insn_info_t i_ptr = active_local_stores;
    2504                 :     240710 :           insn_info_t last = NULL;
    2505                 :            : 
    2506                 :     240710 :           if (dump_file && (dump_flags & TDF_DETAILS))
    2507                 :          0 :             fprintf (dump_file, "%s call %d\n",
    2508                 :          0 :                      const_call ? "const" : "memset", INSN_UID (insn));
    2509                 :            : 
    2510                 :            :           /* See the head comment of the frame_read field.  */
    2511                 :     240710 :           if (reload_completed
    2512                 :            :               /* Tail calls are storing their arguments using
    2513                 :            :                  arg pointer.  If it is a frame pointer on the target,
    2514                 :            :                  even before reload we need to kill frame pointer based
    2515                 :            :                  stores.  */
    2516                 :     120837 :               || (SIBLING_CALL_P (insn)
    2517                 :     240710 :                   && HARD_FRAME_POINTER_IS_ARG_POINTER))
    2518                 :     119873 :             insn_info->frame_read = true;
    2519                 :            : 
    2520                 :            :           /* Loop over the active stores and remove those which are
    2521                 :            :              killed by the const function call.  */
    2522                 :     274665 :           while (i_ptr)
    2523                 :            :             {
    2524                 :      33955 :               bool remove_store = false;
    2525                 :            : 
    2526                 :            :               /* The stack pointer based stores are always killed.  */
    2527                 :      33955 :               if (i_ptr->stack_pointer_based)
    2528                 :            :                 remove_store = true;
    2529                 :            : 
    2530                 :            :               /* If the frame is read, the frame related stores are killed.  */
    2531                 :       8678 :               else if (insn_info->frame_read)
    2532                 :            :                 {
    2533                 :       2422 :                   store_info *store_info = i_ptr->store_rec;
    2534                 :            : 
    2535                 :            :                   /* Skip the clobbers.  */
    2536                 :       2422 :                   while (!store_info->is_set)
    2537                 :          0 :                     store_info = store_info->next;
    2538                 :            : 
    2539                 :       2422 :                   if (store_info->group_id >= 0
    2540                 :       2422 :                       && rtx_group_vec[store_info->group_id]->frame_related)
    2541                 :            :                     remove_store = true;
    2542                 :            :                 }
    2543                 :            : 
    2544                 :            :               if (remove_store)
    2545                 :            :                 {
    2546                 :      26861 :                   if (dump_file && (dump_flags & TDF_DETAILS))
    2547                 :          0 :                     dump_insn_info ("removing from active", i_ptr);
    2548                 :            : 
    2549                 :      26861 :                   active_local_stores_len--;
    2550                 :      26861 :                   if (last)
    2551                 :         20 :                     last->next_local_store = i_ptr->next_local_store;
    2552                 :            :                   else
    2553                 :      26841 :                     active_local_stores = i_ptr->next_local_store;
    2554                 :            :                 }
    2555                 :            :               else
    2556                 :            :                 last = i_ptr;
    2557                 :            : 
    2558                 :      33955 :               i_ptr = i_ptr->next_local_store;
    2559                 :            :             }
    2560                 :            : 
    2561                 :     240710 :           if (memset_call)
    2562                 :            :             {
    2563                 :      18580 :               rtx args[3];
    2564                 :      18580 :               if (get_call_args (insn, memset_call, args, 3)
    2565                 :      15218 :                   && CONST_INT_P (args[1])
    2566                 :      14841 :                   && CONST_INT_P (args[2])
    2567                 :      19229 :                   && INTVAL (args[2]) > 0)
    2568                 :            :                 {
    2569                 :        599 :                   rtx mem = gen_rtx_MEM (BLKmode, args[0]);
    2570                 :        599 :                   set_mem_size (mem, INTVAL (args[2]));
    2571                 :        599 :                   body = gen_rtx_SET (mem, args[1]);
    2572                 :        599 :                   mems_found += record_store (body, bb_info);
    2573                 :        599 :                   if (dump_file && (dump_flags & TDF_DETAILS))
    2574                 :          0 :                     fprintf (dump_file, "handling memset as BLKmode store\n");
    2575                 :        599 :                   if (mems_found == 1)
    2576                 :            :                     {
    2577                 :        355 :                       if (active_local_stores_len++ >= max_active_local_stores)
    2578                 :            :                         {
    2579                 :          0 :                           active_local_stores_len = 1;
    2580                 :          0 :                           active_local_stores = NULL;
    2581                 :            :                         }
    2582                 :        355 :                       insn_info->fixed_regs_live
    2583                 :        355 :                         = copy_fixed_regs (bb_info->regs_live);
    2584                 :        355 :                       insn_info->next_local_store = active_local_stores;
    2585                 :        355 :                       active_local_stores = insn_info;
    2586                 :            :                     }
    2587                 :            :                 }
    2588                 :            :               else
    2589                 :      36561 :                 clear_rhs_from_active_local_stores ();
    2590                 :            :             }
    2591                 :            :         }
    2592                 :    6235800 :       else if (SIBLING_CALL_P (insn)
    2593                 :    6235800 :                && (reload_completed || HARD_FRAME_POINTER_IS_ARG_POINTER))
    2594                 :            :         /* Arguments for a sibling call that are pushed to memory are passed
    2595                 :            :            using the incoming argument pointer of the current function.  After
    2596                 :            :            reload that might be (and likely is) frame pointer based.  And, if
    2597                 :            :            it is a frame pointer on the target, even before reload we need to
    2598                 :            :            kill frame pointer based stores.  */
    2599                 :      90332 :         add_wild_read (bb_info);
    2600                 :            :       else
    2601                 :            :         /* Every other call, including pure functions, may read any memory
    2602                 :            :            that is not relative to the frame.  */
    2603                 :    6145470 :         add_non_frame_wild_read (bb_info);
    2604                 :            : 
    2605                 :    6476510 :       return;
    2606                 :            :     }
    2607                 :            : 
    2608                 :            :   /* Assuming that there are sets in these insns, we cannot delete
    2609                 :            :      them.  */
    2610                 :   73153600 :   if ((GET_CODE (PATTERN (insn)) == CLOBBER)
    2611                 :   73100600 :       || volatile_refs_p (PATTERN (insn))
    2612                 :   70909600 :       || (!cfun->can_delete_dead_exceptions && !insn_nothrow_p (insn))
    2613                 :   68874400 :       || (RTX_FRAME_RELATED_P (insn))
    2614                 :  139815000 :       || find_reg_note (insn, REG_FRAME_RELATED_EXPR, NULL_RTX))
    2615                 :    6492250 :     insn_info->cannot_delete = true;
    2616                 :            : 
    2617                 :   73153600 :   body = PATTERN (insn);
    2618                 :   73153600 :   if (GET_CODE (body) == PARALLEL)
    2619                 :            :     {
    2620                 :            :       int i;
    2621                 :   31432100 :       for (i = 0; i < XVECLEN (body, 0); i++)
    2622                 :   21498100 :         mems_found += record_store (XVECEXP (body, 0, i), bb_info);
    2623                 :            :     }
    2624                 :            :   else
    2625                 :   63219500 :     mems_found += record_store (body, bb_info);
    2626                 :            : 
    2627                 :   73153600 :   if (dump_file && (dump_flags & TDF_DETAILS))
    2628                 :          0 :     fprintf (dump_file, "mems_found = %d, cannot_delete = %s\n",
    2629                 :          0 :              mems_found, insn_info->cannot_delete ? "true" : "false");
    2630                 :            : 
    2631                 :            :   /* If we found some sets of mems, add it into the active_local_stores so
    2632                 :            :      that it can be locally deleted if found dead or used for
    2633                 :            :      replace_read and redundant constant store elimination.  Otherwise mark
    2634                 :            :      it as cannot delete.  This simplifies the processing later.  */
    2635                 :   73153600 :   if (mems_found == 1)
    2636                 :            :     {
    2637                 :   15426800 :       if (active_local_stores_len++ >= max_active_local_stores)
    2638                 :            :         {
    2639                 :         18 :           active_local_stores_len = 1;
    2640                 :         18 :           active_local_stores = NULL;
    2641                 :            :         }
    2642                 :   15426800 :       insn_info->fixed_regs_live = copy_fixed_regs (bb_info->regs_live);
    2643                 :   15426800 :       insn_info->next_local_store = active_local_stores;
    2644                 :   15426800 :       active_local_stores = insn_info;
    2645                 :            :     }
    2646                 :            :   else
    2647                 :   57726800 :     insn_info->cannot_delete = true;
    2648                 :            : }
    2649                 :            : 
    2650                 :            : 
    2651                 :            : /* Remove BASE from the set of active_local_stores.  This is a
    2652                 :            :    callback from cselib that is used to get rid of the stores in
    2653                 :            :    active_local_stores.  */
    2654                 :            : 
    2655                 :            : static void
    2656                 :     283108 : remove_useless_values (cselib_val *base)
    2657                 :            : {
    2658                 :     283108 :   insn_info_t insn_info = active_local_stores;
    2659                 :     283108 :   insn_info_t last = NULL;
    2660                 :            : 
    2661                 :    3828560 :   while (insn_info)
    2662                 :            :     {
    2663                 :    3545460 :       store_info *store_info = insn_info->store_rec;
    2664                 :    3545460 :       bool del = false;
    2665                 :            : 
    2666                 :            :       /* If ANY of the store_infos match the cselib group that is
    2667                 :            :          being deleted, then the insn cannot be deleted.  */
    2668                 :    7081640 :       while (store_info)
    2669                 :            :         {
    2670                 :    3545460 :           if ((store_info->group_id == -1)
    2671                 :    2782520 :               && (store_info->cse_base == base))
    2672                 :            :             {
    2673                 :            :               del = true;
    2674                 :            :               break;
    2675                 :            :             }
    2676                 :    3536180 :           store_info = store_info->next;
    2677                 :            :         }
    2678                 :            : 
    2679                 :    3545460 :       if (del)
    2680                 :            :         {
    2681                 :       9277 :           active_local_stores_len--;
    2682                 :       9277 :           if (last)
    2683                 :       8796 :             last->next_local_store = insn_info->next_local_store;
    2684                 :            :           else
    2685                 :        481 :             active_local_stores = insn_info->next_local_store;
    2686                 :       9277 :           free_store_info (insn_info);
    2687                 :            :         }
    2688                 :            :       else
    2689                 :            :         last = insn_info;
    2690                 :            : 
    2691                 :    3545460 :       insn_info = insn_info->next_local_store;
    2692                 :            :     }
    2693                 :     283108 : }
    2694                 :            : 
    2695                 :            : 
    2696                 :            : /* Do all of step 1.  */
    2697                 :            : 
    2698                 :            : static void
    2699                 :    1373160 : dse_step1 (void)
    2700                 :            : {
    2701                 :    1373160 :   basic_block bb;
    2702                 :    1373160 :   bitmap regs_live = BITMAP_ALLOC (&reg_obstack);
    2703                 :            : 
    2704                 :    1373160 :   cselib_init (0);
    2705                 :    1373160 :   all_blocks = BITMAP_ALLOC (NULL);
    2706                 :    1373160 :   bitmap_set_bit (all_blocks, ENTRY_BLOCK);
    2707                 :    1373160 :   bitmap_set_bit (all_blocks, EXIT_BLOCK);
    2708                 :            : 
    2709                 :            :   /* For -O1 reduce the maximum number of active local stores for RTL DSE
    2710                 :            :      since this can consume huge amounts of memory (PR89115).  */
    2711                 :    1373160 :   int max_active_local_stores = param_max_dse_active_local_stores;
    2712                 :    1373160 :   if (optimize < 2)
    2713                 :      82448 :     max_active_local_stores /= 10;
    2714                 :            : 
    2715                 :   18053900 :   FOR_ALL_BB_FN (bb, cfun)
    2716                 :            :     {
    2717                 :   16680800 :       insn_info_t ptr;
    2718                 :   16680800 :       bb_info_t bb_info = dse_bb_info_type_pool.allocate ();
    2719                 :            : 
    2720                 :   16680800 :       memset (bb_info, 0, sizeof (dse_bb_info_type));
    2721                 :   16680800 :       bitmap_set_bit (all_blocks, bb->index);
    2722                 :   16680800 :       bb_info->regs_live = regs_live;
    2723                 :            : 
    2724                 :   33361500 :       bitmap_copy (regs_live, DF_LR_IN (bb));
    2725                 :   16680800 :       df_simulate_initialize_forwards (bb, regs_live);
    2726                 :            : 
    2727                 :   16680800 :       bb_table[bb->index] = bb_info;
    2728                 :   16680800 :       cselib_discard_hook = remove_useless_values;
    2729                 :            : 
    2730                 :   16680800 :       if (bb->index >= NUM_FIXED_BLOCKS)
    2731                 :            :         {
    2732                 :   13934400 :           rtx_insn *insn;
    2733                 :            : 
    2734                 :   13934400 :           active_local_stores = NULL;
    2735                 :   13934400 :           active_local_stores_len = 0;
    2736                 :   13934400 :           cselib_clear_table ();
    2737                 :            : 
    2738                 :            :           /* Scan the insns.  */
    2739                 :  339604000 :           FOR_BB_INSNS (bb, insn)
    2740                 :            :             {
    2741                 :  162835000 :               if (INSN_P (insn))
    2742                 :  135656000 :                 scan_insn (bb_info, insn, max_active_local_stores);
    2743                 :  162835000 :               cselib_process_insn (insn);
    2744                 :  162835000 :               if (INSN_P (insn))
    2745                 :  135656000 :                 df_simulate_one_insn_forwards (bb, insn, regs_live);
    2746                 :            :             }
    2747                 :            : 
    2748                 :            :           /* This is something of a hack, because the global algorithm
    2749                 :            :              is supposed to take care of the case where stores go dead
    2750                 :            :              at the end of the function.  However, the global
    2751                 :            :              algorithm must take a more conservative view of block
    2752                 :            :              mode reads than the local alg does.  So to get the case
    2753                 :            :              where you have a store to the frame followed by a non
    2754                 :            :              overlapping block more read, we look at the active local
    2755                 :            :              stores at the end of the function and delete all of the
    2756                 :            :              frame and spill based ones.  */
    2757                 :   13934400 :           if (stores_off_frame_dead_at_return
    2758                 :   13934400 :               && (EDGE_COUNT (bb->succs) == 0
    2759                 :   13071500 :                   || (single_succ_p (bb)
    2760                 :    6053510 :                       && single_succ (bb) == EXIT_BLOCK_PTR_FOR_FN (cfun)
    2761                 :    1436200 :                       && ! crtl->calls_eh_return)))
    2762                 :            :             {
    2763                 :    2220630 :               insn_info_t i_ptr = active_local_stores;
    2764                 :    2503630 :               while (i_ptr)
    2765                 :            :                 {
    2766                 :     283007 :                   store_info *store_info = i_ptr->store_rec;
    2767                 :            : 
    2768                 :            :                   /* Skip the clobbers.  */
    2769                 :     283007 :                   while (!store_info->is_set)
    2770                 :          0 :                     store_info = store_info->next;
    2771                 :     283007 :                   if (store_info->group_id >= 0)
    2772                 :            :                     {
    2773                 :      65555 :                       group_info *group = rtx_group_vec[store_info->group_id];
    2774                 :      65555 :                       if (group->frame_related && !i_ptr->cannot_delete)
    2775                 :      12408 :                         delete_dead_store_insn (i_ptr);
    2776                 :            :                     }
    2777                 :            : 
    2778                 :     283007 :                   i_ptr = i_ptr->next_local_store;
    2779                 :            :                 }
    2780                 :            :             }
    2781                 :            : 
    2782                 :            :           /* Get rid of the loads that were discovered in
    2783                 :            :              replace_read.  Cselib is finished with this block.  */
    2784                 :   13978500 :           while (deferred_change_list)
    2785                 :            :             {
    2786                 :      44075 :               deferred_change *next = deferred_change_list->next;
    2787                 :            : 
    2788                 :            :               /* There is no reason to validate this change.  That was
    2789                 :            :                  done earlier.  */
    2790                 :      44075 :               *deferred_change_list->loc = deferred_change_list->reg;
    2791                 :      44075 :               deferred_change_pool.remove (deferred_change_list);
    2792                 :      44075 :               deferred_change_list = next;
    2793                 :            :             }
    2794                 :            : 
    2795                 :            :           /* Get rid of all of the cselib based store_infos in this
    2796                 :            :              block and mark the containing insns as not being
    2797                 :            :              deletable.  */
    2798                 :   13934400 :           ptr = bb_info->last_insn;
    2799                 :  149591000 :           while (ptr)
    2800                 :            :             {
    2801                 :  135656000 :               if (ptr->contains_cselib_groups)
    2802                 :            :                 {
    2803                 :   11083100 :                   store_info *s_info = ptr->store_rec;
    2804                 :   11083100 :                   while (s_info && !s_info->is_set)
    2805                 :          6 :                     s_info = s_info->next;
    2806                 :   11083100 :                   if (s_info
    2807                 :   11083100 :                       && s_info->redundant_reason
    2808                 :          2 :                       && s_info->redundant_reason->insn
    2809                 :          2 :                       && !ptr->cannot_delete)
    2810                 :            :                     {
    2811                 :          2 :                       if (dump_file && (dump_flags & TDF_DETAILS))
    2812                 :          0 :                         fprintf (dump_file, "Locally deleting insn %d "
    2813                 :            :                                             "because insn %d stores the "
    2814                 :            :                                             "same value and couldn't be "
    2815                 :            :                                             "eliminated\n",
    2816                 :          0 :                                  INSN_UID (ptr->insn),
    2817                 :          0 :                                  INSN_UID (s_info->redundant_reason->insn));
    2818                 :          2 :                       delete_dead_store_insn (ptr);
    2819                 :            :                     }
    2820                 :   11083100 :                   free_store_info (ptr);
    2821                 :            :                 }
    2822                 :            :               else
    2823                 :            :                 {
    2824                 :  124573000 :                   store_info *s_info;
    2825                 :            : 
    2826                 :            :                   /* Free at least positions_needed bitmaps.  */
    2827                 :  128894000 :                   for (s_info = ptr->store_rec; s_info; s_info = s_info->next)
    2828                 :    4320650 :                     if (s_info->is_large)
    2829                 :            :                       {
    2830                 :      10987 :                         BITMAP_FREE (s_info->positions_needed.large.bmap);
    2831                 :      10987 :                         s_info->is_large = false;
    2832                 :            :                       }
    2833                 :            :                 }
    2834                 :  135656000 :               ptr = ptr->prev_insn;
    2835                 :            :             }
    2836                 :            : 
    2837                 :   13934400 :           cse_store_info_pool.release ();
    2838                 :            :         }
    2839                 :   16680800 :       bb_info->regs_live = NULL;
    2840                 :            :     }
    2841                 :            : 
    2842                 :    1373160 :   BITMAP_FREE (regs_live);
    2843                 :    1373160 :   cselib_finish ();
    2844                 :    1373160 :   rtx_group_table->empty ();
    2845                 :    1373160 : }
    2846                 :            : 
    2847                 :            : 
    2848                 :            : /*----------------------------------------------------------------------------
    2849                 :            :    Second step.
    2850                 :            : 
    2851                 :            :    Assign each byte position in the stores that we are going to
    2852                 :            :    analyze globally to a position in the bitmaps.  Returns true if
    2853                 :            :    there are any bit positions assigned.
    2854                 :            : ----------------------------------------------------------------------------*/
    2855                 :            : 
    2856                 :            : static void
    2857                 :    1373160 : dse_step2_init (void)
    2858                 :            : {
    2859                 :    1373160 :   unsigned int i;
    2860                 :    1373160 :   group_info *group;
    2861                 :            : 
    2862                 :    5585240 :   FOR_EACH_VEC_ELT (rtx_group_vec, i, group)
    2863                 :            :     {
    2864                 :            :       /* For all non stack related bases, we only consider a store to
    2865                 :            :          be deletable if there are two or more stores for that
    2866                 :            :          position.  This is because it takes one store to make the
    2867                 :            :          other store redundant.  However, for the stores that are
    2868                 :            :          stack related, we consider them if there is only one store
    2869                 :            :          for the position.  We do this because the stack related
    2870                 :            :          stores can be deleted if their is no read between them and
    2871                 :            :          the end of the function.
    2872                 :            : 
    2873                 :            :          To make this work in the current framework, we take the stack
    2874                 :            :          related bases add all of the bits from store1 into store2.
    2875                 :            :          This has the effect of making the eligible even if there is
    2876                 :            :          only one store.   */
    2877                 :            : 
    2878                 :    4212080 :       if (stores_off_frame_dead_at_return && group->frame_related)
    2879                 :            :         {
    2880                 :     188297 :           bitmap_ior_into (group->store2_n, group->store1_n);
    2881                 :     188297 :           bitmap_ior_into (group->store2_p, group->store1_p);
    2882                 :     188297 :           if (dump_file && (dump_flags & TDF_DETAILS))
    2883                 :          0 :             fprintf (dump_file, "group %d is frame related ", i);
    2884                 :            :         }
    2885                 :            : 
    2886                 :    4212080 :       group->offset_map_size_n++;
    2887                 :    4212080 :       group->offset_map_n = XOBNEWVEC (&dse_obstack, int,
    2888                 :            :                                        group->offset_map_size_n);
    2889                 :    4212080 :       group->offset_map_size_p++;
    2890                 :    4212080 :       group->offset_map_p = XOBNEWVEC (&dse_obstack, int,
    2891                 :            :                                        group->offset_map_size_p);
    2892                 :    4212080 :       group->process_globally = false;
    2893                 :    4212080 :       if (dump_file && (dump_flags & TDF_DETAILS))
    2894                 :            :         {
    2895                 :          0 :           fprintf (dump_file, "group %d(%d+%d): ", i,
    2896                 :          0 :                    (int)bitmap_count_bits (group->store2_n),
    2897                 :          0 :                    (int)bitmap_count_bits (group->store2_p));
    2898                 :          0 :           bitmap_print (dump_file, group->store2_n, "n ", " ");
    2899                 :          0 :           bitmap_print (dump_file, group->store2_p, "p ", "\n");
    2900                 :            :         }
    2901                 :            :     }
    2902                 :    1373160 : }
    2903                 :            : 
    2904                 :            : 
    2905                 :            : /* Init the offset tables.  */
    2906                 :            : 
    2907                 :            : static bool
    2908                 :    1373160 : dse_step2 (void)
    2909                 :            : {
    2910                 :    1373160 :   unsigned int i;
    2911                 :    1373160 :   group_info *group;
    2912                 :            :   /* Position 0 is unused because 0 is used in the maps to mean
    2913                 :            :      unused.  */
    2914                 :    1373160 :   current_position = 1;
    2915                 :    5585240 :   FOR_EACH_VEC_ELT (rtx_group_vec, i, group)
    2916                 :            :     {
    2917                 :    4212080 :       bitmap_iterator bi;
    2918                 :    4212080 :       unsigned int j;
    2919                 :            : 
    2920                 :    4212080 :       memset (group->offset_map_n, 0, sizeof (int) * group->offset_map_size_n);
    2921                 :    4212080 :       memset (group->offset_map_p, 0, sizeof (int) * group->offset_map_size_p);
    2922                 :    4212080 :       bitmap_clear (group->group_kill);
    2923                 :            : 
    2924                 :   27372900 :       EXECUTE_IF_SET_IN_BITMAP (group->store2_n, 0, j, bi)
    2925                 :            :         {
    2926                 :   23160800 :           bitmap_set_bit (group->group_kill, current_position);
    2927                 :   23160800 :           if (bitmap_bit_p (group->escaped_n, j))
    2928                 :   17718900 :             bitmap_set_bit (kill_on_calls, current_position);
    2929                 :   23160800 :           group->offset_map_n[j] = current_position++;
    2930                 :   23160800 :           group->process_globally = true;
    2931                 :            :         }
    2932                 :    4948600 :       EXECUTE_IF_SET_IN_BITMAP (group->store2_p, 0, j, bi)
    2933                 :            :         {
    2934                 :     736518 :           bitmap_set_bit (group->group_kill, current_position);
    2935                 :     736518 :           if (bitmap_bit_p (group->escaped_p, j))
    2936                 :     685093 :             bitmap_set_bit (kill_on_calls, current_position);
    2937                 :     736518 :           group->offset_map_p[j] = current_position++;
    2938                 :     736518 :           group->process_globally = true;
    2939                 :            :         }
    2940                 :            :     }
    2941                 :    1373160 :   return current_position != 1;
    2942                 :            : }
    2943                 :            : 
    2944                 :            : 
    2945                 :            : 
    2946                 :            : /*----------------------------------------------------------------------------
    2947                 :            :   Third step.
    2948                 :            : 
    2949                 :            :   Build the bit vectors for the transfer functions.
    2950                 :            : ----------------------------------------------------------------------------*/
    2951                 :            : 
    2952                 :            : 
    2953                 :            : /* Look up the bitmap index for OFFSET in GROUP_INFO.  If it is not
    2954                 :            :    there, return 0.  */
    2955                 :            : 
    2956                 :            : static int
    2957                 :  100878000 : get_bitmap_index (group_info *group_info, HOST_WIDE_INT offset)
    2958                 :            : {
    2959                 :          0 :   if (offset < 0)
    2960                 :            :     {
    2961                 :   91117500 :       HOST_WIDE_INT offset_p = -offset;
    2962                 :   91117500 :       if (offset_p >= group_info->offset_map_size_n)
    2963                 :            :         return 0;
    2964                 :   89514400 :       return group_info->offset_map_n[offset_p];
    2965                 :            :     }
    2966                 :            :   else
    2967                 :            :     {
    2968                 :    9760310 :       if (offset >= group_info->offset_map_size_p)
    2969                 :            :         return 0;
    2970                 :    9407660 :       return group_info->offset_map_p[offset];
    2971                 :            :     }
    2972                 :            : }
    2973                 :            : 
    2974                 :            : 
    2975                 :            : /* Process the STORE_INFOs into the bitmaps into GEN and KILL.  KILL
    2976                 :            :    may be NULL. */
    2977                 :            : 
    2978                 :            : static void
    2979                 :  109477000 : scan_stores (store_info *store_info, bitmap gen, bitmap kill)
    2980                 :            : {
    2981                 :  117112000 :   while (store_info)
    2982                 :            :     {
    2983                 :    7635300 :       HOST_WIDE_INT i, offset, width;
    2984                 :    7635300 :       group_info *group_info
    2985                 :    7635300 :         = rtx_group_vec[store_info->group_id];
    2986                 :            :       /* We can (conservatively) ignore stores whose bounds aren't known;
    2987                 :            :          they simply don't generate new global dse opportunities.  */
    2988                 :    7635300 :       if (group_info->process_globally
    2989                 :    7486880 :           && store_info->offset.is_constant (&offset)
    2990                 :    7635300 :           && store_info->width.is_constant (&width))
    2991                 :            :         {
    2992                 :    7486880 :           HOST_WIDE_INT end = offset + width;
    2993                 :   75152100 :           for (i = offset; i < end; i++)
    2994                 :            :             {
    2995                 :  135330000 :               int index = get_bitmap_index (group_info, i);
    2996                 :   67587900 :               if (index != 0)
    2997                 :            :                 {
    2998                 :   66924600 :                   bitmap_set_bit (gen, index);
    2999                 :   66924600 :                   if (kill)
    3000                 :   30104400 :                     bitmap_clear_bit (kill, index);
    3001                 :            :                 }
    3002                 :            :             }
    3003                 :            :         }
    3004                 :    7635300 :       store_info = store_info->next;
    3005                 :            :     }
    3006                 :  109477000 : }
    3007                 :            : 
    3008                 :            : 
    3009                 :            : /* Process the READ_INFOs into the bitmaps into GEN and KILL.  KILL
    3010                 :            :    may be NULL.  */
    3011                 :            : 
    3012                 :            : static void
    3013                 :   60851600 : scan_reads (insn_info_t insn_info, bitmap gen, bitmap kill)
    3014                 :            : {
    3015                 :   60851600 :   read_info_t read_info = insn_info->read_rec;
    3016                 :   60851600 :   int i;
    3017                 :   60851600 :   group_info *group;
    3018                 :            : 
    3019                 :            :   /* If this insn reads the frame, kill all the frame related stores.  */
    3020                 :   60851600 :   if (insn_info->frame_read)
    3021                 :            :     {
    3022                 :     157390 :       FOR_EACH_VEC_ELT (rtx_group_vec, i, group)
    3023                 :     150074 :         if (group->process_globally && group->frame_related)
    3024                 :            :           {
    3025                 :       5521 :             if (kill)
    3026                 :       2413 :               bitmap_ior_into (kill, group->group_kill);
    3027                 :       5521 :             bitmap_and_compl_into (gen, group->group_kill);
    3028                 :            :           }
    3029                 :            :     }
    3030                 :   60851600 :   if (insn_info->non_frame_wild_read)
    3031                 :            :     {
    3032                 :            :       /* Kill all non-frame related stores.  Kill all stores of variables that
    3033                 :            :          escape.  */
    3034                 :    5118350 :       if (kill)
    3035                 :    2458480 :         bitmap_ior_into (kill, kill_on_calls);
    3036                 :    5118350 :       bitmap_and_compl_into (gen, kill_on_calls);
    3037                 :  115442000 :       FOR_EACH_VEC_ELT (rtx_group_vec, i, group)
    3038                 :  110324000 :         if (group->process_globally && !group->frame_related)
    3039                 :            :           {
    3040                 :    2471510 :             if (kill)
    3041                 :    1131970 :               bitmap_ior_into (kill, group->group_kill);
    3042                 :    2471510 :             bitmap_and_compl_into (gen, group->group_kill);
    3043                 :            :           }
    3044                 :            :     }
    3045                 :   70481900 :   while (read_info)
    3046                 :            :     {
    3047                 :  295747000 :       FOR_EACH_VEC_ELT (rtx_group_vec, i, group)
    3048                 :            :         {
    3049                 :  286117000 :           if (group->process_globally)
    3050                 :            :             {
    3051                 :   14963200 :               if (i == read_info->group_id)
    3052                 :            :                 {
    3053                 :    3966720 :                   HOST_WIDE_INT offset, width;
    3054                 :            :                   /* Reads with non-constant size kill all DSE opportunities
    3055                 :            :                      in the group.  */
    3056                 :    3966720 :                   if (!read_info->offset.is_constant (&offset)
    3057                 :    3966720 :                       || !read_info->width.is_constant (&width)
    3058                 :    3966720 :                       || !known_size_p (width))
    3059                 :            :                     {
    3060                 :            :                       /* Handle block mode reads.  */
    3061                 :      36608 :                       if (kill)
    3062                 :      17903 :                         bitmap_ior_into (kill, group->group_kill);
    3063                 :      36608 :                       bitmap_and_compl_into (gen, group->group_kill);
    3064                 :            :                     }
    3065                 :            :                   else
    3066                 :            :                     {
    3067                 :            :                       /* The groups are the same, just process the
    3068                 :            :                          offsets.  */
    3069                 :    3930110 :                       HOST_WIDE_INT j;
    3070                 :    3930110 :                       HOST_WIDE_INT end = offset + width;
    3071                 :   33728300 :                       for (j = offset; j < end; j++)
    3072                 :            :                         {
    3073                 :   59596500 :                           int index = get_bitmap_index (group, j);
    3074                 :   27920800 :                           if (index != 0)
    3075                 :            :                             {
    3076                 :   21912500 :                               if (kill)
    3077                 :   10481700 :                                 bitmap_set_bit (kill, index);
    3078                 :   21912500 :                               bitmap_clear_bit (gen, index);
    3079                 :            :                             }
    3080                 :            :                         }
    3081                 :            :                     }
    3082                 :            :                 }
    3083                 :            :               else
    3084                 :            :                 {
    3085                 :            :                   /* The groups are different, if the alias sets
    3086                 :            :                      conflict, clear the entire group.  We only need
    3087                 :            :                      to apply this test if the read_info is a cselib
    3088                 :            :                      read.  Anything with a constant base cannot alias
    3089                 :            :                      something else with a different constant
    3090                 :            :                      base.  */
    3091                 :   10996500 :                   if ((read_info->group_id < 0)
    3092                 :   16506600 :                       && canon_true_dependence (group->base_mem,
    3093                 :    5510130 :                                                 GET_MODE (group->base_mem),
    3094                 :            :                                                 group->canon_base_addr,
    3095                 :    5510130 :                                                 read_info->mem, NULL_RTX))
    3096                 :            :                     {
    3097                 :    2692080 :                       if (kill)
    3098                 :    1309820 :                         bitmap_ior_into (kill, group->group_kill);
    3099                 :    2692080 :                       bitmap_and_compl_into (gen, group->group_kill);
    3100                 :            :                     }
    3101                 :            :                 }
    3102                 :            :             }
    3103                 :            :         }
    3104                 :            : 
    3105                 :    9630320 :       read_info = read_info->next;
    3106                 :            :     }
    3107                 :   60851600 : }
    3108                 :            : 
    3109                 :            : 
    3110                 :            : /* Return the insn in BB_INFO before the first wild read or if there
    3111                 :            :    are no wild reads in the block, return the last insn.  */
    3112                 :            : 
    3113                 :            : static insn_info_t
    3114                 :    5324420 : find_insn_before_first_wild_read (bb_info_t bb_info)
    3115                 :            : {
    3116                 :    5324420 :   insn_info_t insn_info = bb_info->last_insn;
    3117                 :          0 :   insn_info_t last_wild_read = NULL;
    3118                 :            : 
    3119                 :   61497900 :   while (insn_info)
    3120                 :            :     {
    3121                 :   56272300 :       if (insn_info->wild_read)
    3122                 :            :         {
    3123                 :     569218 :           last_wild_read = insn_info->prev_insn;
    3124                 :            :           /* Block starts with wild read.  */
    3125                 :     569218 :           if (!last_wild_read)
    3126                 :            :             return NULL;
    3127                 :            :         }
    3128                 :            : 
    3129                 :   56173500 :       insn_info = insn_info->prev_insn;
    3130                 :            :     }
    3131                 :            : 
    3132                 :    5225600 :   if (last_wild_read)
    3133                 :            :     return last_wild_read;
    3134                 :            :   else
    3135                 :    5007490 :     return bb_info->last_insn;
    3136                 :            : }
    3137                 :            : 
    3138                 :            : 
    3139                 :            : /* Scan the insns in BB_INFO starting at PTR and going to the top of
    3140                 :            :    the block in order to build the gen and kill sets for the block.
    3141                 :            :    We start at ptr which may be the last insn in the block or may be
    3142                 :            :    the first insn with a wild read.  In the latter case we are able to
    3143                 :            :    skip the rest of the block because it just does not matter:
    3144                 :            :    anything that happens is hidden by the wild read.  */
    3145                 :            : 
    3146                 :            : static void
    3147                 :    5324420 : dse_step3_scan (basic_block bb)
    3148                 :            : {
    3149                 :    5324420 :   bb_info_t bb_info = bb_table[bb->index];
    3150                 :    5324420 :   insn_info_t insn_info;
    3151                 :            : 
    3152                 :    5324420 :   insn_info = find_insn_before_first_wild_read (bb_info);
    3153                 :            : 
    3154                 :            :   /* In the spill case or in the no_spill case if there is no wild
    3155                 :            :      read in the block, we will need a kill set.  */
    3156                 :    5324420 :   if (insn_info == bb_info->last_insn)
    3157                 :            :     {
    3158                 :    5007490 :       if (bb_info->kill)
    3159                 :          0 :         bitmap_clear (bb_info->kill);
    3160                 :            :       else
    3161                 :    5007490 :         bb_info->kill = BITMAP_ALLOC (&dse_bitmap_obstack);
    3162                 :            :     }
    3163                 :            :   else
    3164                 :     316929 :     if (bb_info->kill)
    3165                 :          0 :       BITMAP_FREE (bb_info->kill);
    3166                 :            : 
    3167                 :   58684900 :   while (insn_info)
    3168                 :            :     {
    3169                 :            :       /* There may have been code deleted by the dce pass run before
    3170                 :            :          this phase.  */
    3171                 :   53360500 :       if (insn_info->insn && INSN_P (insn_info->insn))
    3172                 :            :         {
    3173                 :   53336900 :           scan_stores (insn_info->store_rec, bb_info->gen, bb_info->kill);
    3174                 :   53336900 :           scan_reads (insn_info, bb_info->gen, bb_info->kill);
    3175                 :            :         }
    3176                 :            : 
    3177                 :   53360500 :       insn_info = insn_info->prev_insn;
    3178                 :            :     }
    3179                 :    5324420 : }
    3180                 :            : 
    3181                 :            : 
    3182                 :            : /* Set the gen set of the exit block, and also any block with no
    3183                 :            :    successors that does not have a wild read.  */
    3184                 :            : 
    3185                 :            : static void
    3186                 :     182815 : dse_step3_exit_block_scan (bb_info_t bb_info)
    3187                 :            : {
    3188                 :            :   /* The gen set is all 0's for the exit block except for the
    3189                 :            :      frame_pointer_group.  */
    3190                 :            : 
    3191                 :     182815 :   if (stores_off_frame_dead_at_return)
    3192                 :            :     {
    3193                 :            :       unsigned int i;
    3194                 :            :       group_info *group;
    3195                 :            : 
    3196                 :    1687850 :       FOR_EACH_VEC_ELT (rtx_group_vec, i, group)
    3197                 :            :         {
    3198                 :    1506190 :           if (group->process_globally && group->frame_related)
    3199                 :     161575 :             bitmap_ior_into (bb_info->gen, group->group_kill);
    3200                 :            :         }
    3201                 :            :     }
    3202                 :     182815 : }
    3203                 :            : 
    3204                 :            : 
    3205                 :            : /* Find all of the blocks that are not backwards reachable from the
    3206                 :            :    exit block or any block with no successors (BB).  These are the
    3207                 :            :    infinite loops or infinite self loops.  These blocks will still
    3208                 :            :    have their bits set in UNREACHABLE_BLOCKS.  */
    3209                 :            : 
    3210                 :            : static void
    3211                 :    8692100 : mark_reachable_blocks (sbitmap unreachable_blocks, basic_block bb)
    3212                 :            : {
    3213                 :    8692100 :   edge e;
    3214                 :    8692100 :   edge_iterator ei;
    3215                 :            : 
    3216                 :    8692100 :   if (bitmap_bit_p (unreachable_blocks, bb->index))
    3217                 :            :     {
    3218                 :    5681260 :       bitmap_clear_bit (unreachable_blocks, bb->index);
    3219                 :   13888900 :       FOR_EACH_EDGE (e, ei, bb->preds)
    3220                 :            :         {
    3221                 :    8207690 :           mark_reachable_blocks (unreachable_blocks, e->src);
    3222                 :            :         }
    3223                 :            :     }
    3224                 :    8692100 : }
    3225                 :            : 
    3226                 :            : /* Build the transfer functions for the function.  */
    3227                 :            : 
    3228                 :            : static void
    3229                 :     182815 : dse_step3 ()
    3230                 :            : {
    3231                 :     182815 :   basic_block bb;
    3232                 :     182815 :   sbitmap_iterator sbi;
    3233                 :     182815 :   bitmap all_ones = NULL;
    3234                 :     182815 :   unsigned int i;
    3235                 :            : 
    3236                 :     182815 :   auto_sbitmap unreachable_blocks (last_basic_block_for_fn (cfun));
    3237                 :     182815 :   bitmap_ones (unreachable_blocks);
    3238                 :            : 
    3239                 :    5872860 :   FOR_ALL_BB_FN (bb, cfun)
    3240                 :            :     {
    3241                 :    5690050 :       bb_info_t bb_info = bb_table[bb->index];
    3242                 :    5690050 :       if (bb_info->gen)
    3243                 :          0 :         bitmap_clear (bb_info->gen);
    3244                 :            :       else
    3245                 :    5690050 :         bb_info->gen = BITMAP_ALLOC (&dse_bitmap_obstack);
    3246                 :            : 
    3247                 :    5690050 :       if (bb->index == ENTRY_BLOCK)
    3248                 :            :         ;
    3249                 :    5507230 :       else if (bb->index == EXIT_BLOCK)
    3250                 :     182815 :         dse_step3_exit_block_scan (bb_info);
    3251                 :            :       else
    3252                 :    5324420 :         dse_step3_scan (bb);
    3253                 :    5690050 :       if (EDGE_COUNT (bb->succs) == 0)
    3254                 :     484411 :         mark_reachable_blocks (unreachable_blocks, bb);
    3255                 :            : 
    3256                 :            :       /* If this is the second time dataflow is run, delete the old
    3257                 :            :          sets.  */
    3258                 :    5690050 :       if (bb_info->in)
    3259                 :          0 :         BITMAP_FREE (bb_info->in);
    3260                 :    5690050 :       if (bb_info->out)
    3261                 :          0 :         BITMAP_FREE (bb_info->out);
    3262                 :            :     }
    3263                 :            : 
    3264                 :            :   /* For any block in an infinite loop, we must initialize the out set
    3265                 :            :      to all ones.  This could be expensive, but almost never occurs in
    3266                 :            :      practice. However, it is common in regression tests.  */
    3267                 :     777364 :   EXECUTE_IF_SET_IN_BITMAP (unreachable_blocks, 0, i, sbi)
    3268                 :            :     {
    3269                 :     411734 :       if (bitmap_bit_p (all_blocks, i))
    3270                 :            :         {
    3271                 :       8788 :           bb_info_t bb_info = bb_table[i];
    3272                 :       8788 :           if (!all_ones)
    3273                 :            :             {
    3274                 :       1035 :               unsigned int j;
    3275                 :       1035 :               group_info *group;
    3276                 :            : 
    3277                 :       1035 :               all_ones = BITMAP_ALLOC (&dse_bitmap_obstack);
    3278                 :       7873 :               FOR_EACH_VEC_ELT (rtx_group_vec, j, group)
    3279                 :       6838 :                 bitmap_ior_into (all_ones, group->group_kill);
    3280                 :            :             }
    3281                 :       8788 :           if (!bb_info->out)
    3282                 :            :             {
    3283                 :       8788 :               bb_info->out = BITMAP_ALLOC (&dse_bitmap_obstack);
    3284                 :       8788 :               bitmap_copy (bb_info->out, all_ones);
    3285                 :            :             }
    3286                 :            :         }
    3287                 :            :     }
    3288                 :            : 
    3289                 :     182815 :   if (all_ones)
    3290                 :       1035 :     BITMAP_FREE (all_ones);
    3291                 :     182815 : }
    3292                 :            : 
    3293                 :            : 
    3294                 :            : 
    3295                 :            : /*----------------------------------------------------------------------------
    3296                 :            :    Fourth step.
    3297                 :            : 
    3298                 :            :    Solve the bitvector equations.
    3299                 :            : ----------------------------------------------------------------------------*/
    3300                 :            : 
    3301                 :            : 
    3302                 :            : /* Confluence function for blocks with no successors.  Create an out
    3303                 :            :    set from the gen set of the exit block.  This block logically has
    3304                 :            :    the exit block as a successor.  */
    3305                 :            : 
    3306                 :            : 
    3307                 :            : 
    3308                 :            : static void
    3309                 :     484411 : dse_confluence_0 (basic_block bb)
    3310                 :            : {
    3311                 :     484411 :   bb_info_t bb_info = bb_table[bb->index];
    3312                 :            : 
    3313                 :     484411 :   if (bb->index == EXIT_BLOCK)
    3314                 :            :     return;
    3315                 :            : 
    3316                 :     301596 :   if (!bb_info->out)
    3317                 :            :     {
    3318                 :     301596 :       bb_info->out = BITMAP_ALLOC (&dse_bitmap_obstack);
    3319                 :     301596 :       bitmap_copy (bb_info->out, bb_table[EXIT_BLOCK]->gen);
    3320                 :            :     }
    3321                 :            : }
    3322                 :            : 
    3323                 :            : /* Propagate the information from the in set of the dest of E to the
    3324                 :            :    out set of the src of E.  If the various in or out sets are not
    3325                 :            :    there, that means they are all ones.  */
    3326                 :            : 
    3327                 :            : static bool
    3328                 :    8901420 : dse_confluence_n (edge e)
    3329                 :            : {
    3330                 :    8901420 :   bb_info_t src_info = bb_table[e->src->index];
    3331                 :    8901420 :   bb_info_t dest_info = bb_table[e->dest->index];
    3332                 :            : 
    3333                 :    8901420 :   if (dest_info->in)
    3334                 :            :     {
    3335                 :    8474240 :       if (src_info->out)
    3336                 :    3277390 :         bitmap_and_into (src_info->out, dest_info->in);
    3337                 :            :       else
    3338                 :            :         {
    3339                 :    5196850 :           src_info->out = BITMAP_ALLOC (&dse_bitmap_obstack);
    3340                 :    5196850 :           bitmap_copy (src_info->out, dest_info->in);
    3341                 :            :         }
    3342                 :            :     }
    3343                 :    8901420 :   return true;
    3344                 :            : }
    3345                 :            : 
    3346                 :            : 
    3347                 :            : /* Propagate the info from the out to the in set of BB_INDEX's basic
    3348                 :            :    block.  There are three cases:
    3349                 :            : 
    3350                 :            :    1) The block has no kill set.  In this case the kill set is all
    3351                 :            :    ones.  It does not matter what the out set of the block is, none of
    3352                 :            :    the info can reach the top.  The only thing that reaches the top is
    3353                 :            :    the gen set and we just copy the set.
    3354                 :            : 
    3355                 :            :    2) There is a kill set but no out set and bb has successors.  In
    3356                 :            :    this case we just return. Eventually an out set will be created and
    3357                 :            :    it is better to wait than to create a set of ones.
    3358                 :            : 
    3359                 :            :    3) There is both a kill and out set.  We apply the obvious transfer
    3360                 :            :    function.
    3361                 :            : */
    3362                 :            : 
    3363                 :            : static bool
    3364                 :    6312830 : dse_transfer_function (int bb_index)
    3365                 :            : {
    3366                 :    6312830 :   bb_info_t bb_info = bb_table[bb_index];
    3367                 :            : 
    3368                 :    6312830 :   if (bb_info->kill)
    3369                 :            :     {
    3370                 :    5605540 :       if (bb_info->out)
    3371                 :            :         {
    3372                 :            :           /* Case 3 above.  */
    3373                 :    5482640 :           if (bb_info->in)
    3374                 :     475145 :             return bitmap_ior_and_compl (bb_info->in, bb_info->gen,
    3375                 :     475145 :                                          bb_info->out, bb_info->kill);
    3376                 :            :           else
    3377                 :            :             {
    3378                 :    5007490 :               bb_info->in = BITMAP_ALLOC (&dse_bitmap_obstack);
    3379                 :    5007490 :               bitmap_ior_and_compl (bb_info->in, bb_info->gen,
    3380                 :    5007490 :                                     bb_info->out, bb_info->kill);
    3381                 :    5007490 :               return true;
    3382                 :            :             }
    3383                 :            :         }
    3384                 :            :       else
    3385                 :            :         /* Case 2 above.  */
    3386                 :            :         return false;
    3387                 :            :     }
    3388                 :            :   else
    3389                 :            :     {
    3390                 :            :       /* Case 1 above.  If there is already an in set, nothing
    3391                 :            :          happens.  */
    3392                 :     707292 :       if (bb_info->in)
    3393                 :            :         return false;
    3394                 :            :       else
    3395                 :            :         {
    3396                 :     682559 :           bb_info->in = BITMAP_ALLOC (&dse_bitmap_obstack);
    3397                 :     682559 :           bitmap_copy (bb_info->in, bb_info->gen);
    3398                 :     682559 :           return true;
    3399                 :            :         }
    3400                 :            :     }
    3401                 :            : }
    3402                 :            : 
    3403                 :            : /* Solve the dataflow equations.  */
    3404                 :            : 
    3405                 :            : static void
    3406                 :     182815 : dse_step4 (void)
    3407                 :            : {
    3408                 :     182815 :   df_simple_dataflow (DF_BACKWARD, NULL, dse_confluence_0,
    3409                 :            :                       dse_confluence_n, dse_transfer_function,
    3410                 :            :                       all_blocks, df_get_postorder (DF_BACKWARD),
    3411                 :            :                       df_get_n_blocks (DF_BACKWARD));
    3412                 :     182815 :   if (dump_file && (dump_flags & TDF_DETAILS))
    3413                 :            :     {
    3414                 :          0 :       basic_block bb;
    3415                 :            : 
    3416                 :          0 :       fprintf (dump_file, "\n\n*** Global dataflow info after analysis.\n");
    3417                 :          0 :       FOR_ALL_BB_FN (bb, cfun)
    3418                 :            :         {
    3419                 :          0 :           bb_info_t bb_info = bb_table[bb->index];
    3420                 :            : 
    3421                 :          0 :           df_print_bb_index (bb, dump_file);
    3422                 :          0 :           if (bb_info->in)
    3423                 :          0 :             bitmap_print (dump_file, bb_info->in, "  in:   ", "\n");
    3424                 :            :           else
    3425                 :          0 :             fprintf (dump_file, "  in:   *MISSING*\n");
    3426                 :          0 :           if (bb_info->gen)
    3427                 :          0 :             bitmap_print (dump_file, bb_info->gen, "  gen:  ", "\n");
    3428                 :            :           else
    3429                 :          0 :             fprintf (dump_file, "  gen:  *MISSING*\n");
    3430                 :          0 :           if (bb_info->kill)
    3431                 :          0 :             bitmap_print (dump_file, bb_info->kill, "  kill: ", "\n");
    3432                 :            :           else
    3433                 :          0 :             fprintf (dump_file, "  kill: *MISSING*\n");
    3434                 :          0 :           if (bb_info->out)
    3435                 :          0 :             bitmap_print (dump_file, bb_info->out, "  out:  ", "\n");
    3436                 :            :           else
    3437                 :          0 :             fprintf (dump_file, "  out:  *MISSING*\n\n");
    3438                 :            :         }
    3439                 :            :     }
    3440                 :     182815 : }
    3441                 :            : 
    3442                 :            : 
    3443                 :            : 
    3444                 :            : /*----------------------------------------------------------------------------
    3445                 :            :    Fifth step.
    3446                 :            : 
    3447                 :            :    Delete the stores that can only be deleted using the global information.
    3448                 :            : ----------------------------------------------------------------------------*/
    3449                 :            : 
    3450                 :            : 
    3451                 :            : static void
    3452                 :     182815 : dse_step5 (void)
    3453                 :            : {
    3454                 :     182815 :   basic_block bb;
    3455                 :    5507230 :   FOR_EACH_BB_FN (bb, cfun)
    3456                 :            :     {
    3457                 :    5324420 :       bb_info_t bb_info = bb_table[bb->index];
    3458                 :    5324420 :       insn_info_t insn_info = bb_info->last_insn;
    3459                 :    5324420 :       bitmap v = bb_info->out;
    3460                 :            : 
    3461                 :   61596800 :       while (insn_info)
    3462                 :            :         {
    3463                 :   56272300 :           bool deleted = false;
    3464                 :   56272300 :           if (dump_file && insn_info->insn)
    3465                 :            :             {
    3466                 :         46 :               fprintf (dump_file, "starting to process insn %d\n",
    3467                 :         23 :                        INSN_UID (insn_info->insn));
    3468                 :         23 :               bitmap_print (dump_file, v, "  v:  ", "\n");
    3469                 :            :             }
    3470                 :            : 
    3471                 :            :           /* There may have been code deleted by the dce pass run before
    3472                 :            :              this phase.  */
    3473                 :   56272300 :           if (insn_info->insn
    3474                 :   56248500 :               && INSN_P (insn_info->insn)
    3475                 :   56248500 :               && (!insn_info->cannot_delete)
    3476                 :   59964000 :               && (!bitmap_empty_p (v)))
    3477                 :            :             {
    3478                 :    2754360 :               store_info *store_info = insn_info->store_rec;
    3479                 :            : 
    3480                 :            :               /* Try to delete the current insn.  */
    3481                 :    2754360 :               deleted = true;
    3482                 :            : 
    3483                 :            :               /* Skip the clobbers.  */
    3484                 :    2754360 :               while (!store_info->is_set)
    3485                 :          0 :                 store_info = store_info->next;
    3486                 :            : 
    3487                 :    2754360 :               HOST_WIDE_INT i, offset, width;
    3488                 :    2754360 :               group_info *group_info = rtx_group_vec[store_info->group_id];
    3489                 :            : 
    3490                 :    2754360 :               if (!store_info->offset.is_constant (&offset)
    3491                 :    2754360 :                   || !store_info->width.is_constant (&width))
    3492                 :            :                 deleted = false;
    3493                 :            :               else
    3494                 :            :                 {
    3495                 :    2754360 :                   HOST_WIDE_INT end = offset + width;
    3496                 :    3522710 :                   for (i = offset; i < end; i++)
    3497                 :            :                     {
    3498                 :    3414380 :                       int index = get_bitmap_index (group_info, i);
    3499                 :            : 
    3500                 :    3414380 :                       if (dump_file && (dump_flags & TDF_DETAILS))
    3501                 :          0 :                         fprintf (dump_file, "i = %d, index = %d\n",
    3502                 :            :                                  (int) i, index);
    3503                 :    3414380 :                       if (index == 0 || !bitmap_bit_p (v, index))
    3504                 :            :                         {
    3505                 :    2646030 :                           if (dump_file && (dump_flags & TDF_DETAILS))
    3506                 :          0 :                             fprintf (dump_file, "failing at i = %d\n",
    3507                 :            :                                      (int) i);
    3508                 :            :                           deleted = false;
    3509                 :            :                           break;
    3510                 :            :                         }
    3511                 :            :                     }
    3512                 :            :                 }
    3513                 :     108327 :               if (deleted)
    3514                 :            :                 {
    3515                 :     108327 :                   if (dbg_cnt (dse)
    3516                 :     108327 :                       && check_for_inc_dec_1 (insn_info))
    3517                 :            :                     {
    3518                 :     108327 :                       delete_insn (insn_info->insn);
    3519                 :     108327 :                       insn_info->insn = NULL;
    3520                 :     108327 :                       globally_deleted++;
    3521                 :            :                     }
    3522                 :            :                 }
    3523                 :            :             }
    3524                 :            :           /* We do want to process the local info if the insn was
    3525                 :            :              deleted.  For instance, if the insn did a wild read, we
    3526                 :            :              no longer need to trash the info.  */
    3527                 :   56272300 :           if (insn_info->insn
    3528                 :   56140100 :               && INSN_P (insn_info->insn)
    3529                 :   56140100 :               && (!deleted))
    3530                 :            :             {
    3531                 :   56140100 :               scan_stores (insn_info->store_rec, v, NULL);
    3532                 :   56140100 :               if (insn_info->wild_read)
    3533                 :            :                 {
    3534                 :     569218 :                   if (dump_file && (dump_flags & TDF_DETAILS))
    3535                 :          0 :                     fprintf (dump_file, "wild read\n");
    3536                 :     569218 :                   bitmap_clear (v);
    3537                 :            :                 }
    3538                 :   55570900 :               else if (insn_info->read_rec
    3539                 :   50668000 :                        || insn_info->non_frame_wild_read
    3540                 :   48056200 :                        || insn_info->frame_read)
    3541                 :            :                 {
    3542                 :    7514680 :                   if (dump_file && (dump_flags & TDF_DETAILS))
    3543                 :            :                     {
    3544                 :          0 :                       if (!insn_info->non_frame_wild_read
    3545                 :          0 :                           && !insn_info->frame_read)
    3546                 :          0 :                         fprintf (dump_file, "regular read\n");
    3547                 :          0 :                       if (insn_info->non_frame_wild_read)
    3548                 :          0 :                         fprintf (dump_file, "non-frame wild read\n");
    3549                 :          0 :                       if (insn_info->frame_read)
    3550                 :          0 :                         fprintf (dump_file, "frame read\n");
    3551                 :            :                     }
    3552                 :    7514680 :                   scan_reads (insn_info, v, NULL);
    3553                 :            :                 }
    3554                 :            :             }
    3555                 :            : 
    3556                 :   56272300 :           insn_info = insn_info->prev_insn;
    3557                 :            :         }
    3558                 :            :     }
    3559                 :     182815 : }
    3560                 :            : 
    3561                 :            : 
    3562                 :            : 
    3563                 :            : /*----------------------------------------------------------------------------
    3564                 :            :    Sixth step.
    3565                 :            : 
    3566                 :            :    Delete stores made redundant by earlier stores (which store the same
    3567                 :            :    value) that couldn't be eliminated.
    3568                 :            : ----------------------------------------------------------------------------*/
    3569                 :            : 
    3570                 :            : static void
    3571                 :    1373160 : dse_step6 (void)
    3572                 :            : {
    3573                 :    1373160 :   basic_block bb;
    3574                 :            : 
    3575                 :   18053900 :   FOR_ALL_BB_FN (bb, cfun)
    3576                 :            :     {
    3577                 :   16680800 :       bb_info_t bb_info = bb_table[bb->index];
    3578                 :   16680800 :       insn_info_t insn_info = bb_info->last_insn;
    3579                 :            : 
    3580                 :  152337000 :       while (insn_info)
    3581                 :            :         {
    3582                 :            :           /* There may have been code deleted by the dce pass run before
    3583                 :            :              this phase.  */
    3584                 :  135656000 :           if (insn_info->insn
    3585                 :  135519000 :               && INSN_P (insn_info->insn)
    3586                 :  135519000 :               && !insn_info->cannot_delete)
    3587                 :            :             {
    3588                 :    3774350 :               store_info *s_info = insn_info->store_rec;
    3589                 :            : 
    3590                 :    3774350 :               while (s_info && !s_info->is_set)
    3591                 :          0 :                 s_info = s_info->next;
    3592                 :    3774350 :               if (s_info
    3593                 :    3774350 :                   && s_info->redundant_reason
    3594                 :         46 :                   && s_info->redundant_reason->insn
    3595                 :         37 :                   && INSN_P (s_info->redundant_reason->insn))
    3596                 :            :                 {
    3597                 :         37 :                   rtx_insn *rinsn = s_info->redundant_reason->insn;
    3598                 :         37 :                   if (dump_file && (dump_flags & TDF_DETAILS))
    3599                 :          0 :                     fprintf (dump_file, "Locally deleting insn %d "
    3600                 :            :                                         "because insn %d stores the "
    3601                 :            :                                         "same value and couldn't be "
    3602                 :            :                                         "eliminated\n",
    3603                 :          0 :                                         INSN_UID (insn_info->insn),
    3604                 :          0 :                                         INSN_UID (rinsn));
    3605                 :         37 :                   delete_dead_store_insn (insn_info);
    3606                 :            :                 }
    3607                 :            :             }
    3608                 :  135656000 :           insn_info = insn_info->prev_insn;
    3609                 :            :         }
    3610                 :            :     }
    3611                 :    1373160 : }
    3612                 :            : 
    3613                 :            : /*----------------------------------------------------------------------------
    3614                 :            :    Seventh step.
    3615                 :            : 
    3616                 :            :    Destroy everything left standing.
    3617                 :            : ----------------------------------------------------------------------------*/
    3618                 :            : 
    3619                 :            : static void
    3620                 :    1373160 : dse_step7 (void)
    3621                 :            : {
    3622                 :    1373160 :   bitmap_obstack_release (&dse_bitmap_obstack);
    3623                 :    1373160 :   obstack_free (&dse_obstack, NULL);
    3624                 :            : 
    3625                 :    1373160 :   end_alias_analysis ();
    3626                 :    1373160 :   free (bb_table);
    3627                 :    1373160 :   delete rtx_group_table;
    3628                 :    1373160 :   rtx_group_table = NULL;
    3629                 :    1373160 :   rtx_group_vec.release ();
    3630                 :    1373160 :   BITMAP_FREE (all_blocks);
    3631                 :    1373160 :   BITMAP_FREE (scratch);
    3632                 :            : 
    3633                 :    1373160 :   rtx_store_info_pool.release ();
    3634                 :    1373160 :   read_info_type_pool.release ();
    3635                 :    1373160 :   insn_info_type_pool.release ();
    3636                 :    1373160 :   dse_bb_info_type_pool.release ();
    3637                 :    1373160 :   group_info_pool.release ();
    3638                 :    1373160 :   deferred_change_pool.release ();
    3639                 :    1373160 : }
    3640                 :            : 
    3641                 :            : 
    3642                 :            : /* -------------------------------------------------------------------------
    3643                 :            :    DSE
    3644                 :            :    ------------------------------------------------------------------------- */
    3645                 :            : 
    3646                 :            : /* Callback for running pass_rtl_dse.  */
    3647                 :            : 
    3648                 :            : static unsigned int
    3649                 :    1373160 : rest_of_handle_dse (void)
    3650                 :            : {
    3651                 :    1373160 :   df_set_flags (DF_DEFER_INSN_RESCAN);
    3652                 :            : 
    3653                 :            :   /* Need the notes since we must track live hardregs in the forwards
    3654                 :            :      direction.  */
    3655                 :    1373160 :   df_note_add_problem ();
    3656                 :    1373160 :   df_analyze ();
    3657                 :            : 
    3658                 :    1373160 :   dse_step0 ();
    3659                 :    1373160 :   dse_step1 ();
    3660                 :    1373160 :   dse_step2_init ();
    3661                 :    1373160 :   if (dse_step2 ())
    3662                 :            :     {
    3663                 :     182815 :       df_set_flags (DF_LR_RUN_DCE);
    3664                 :     182815 :       df_analyze ();
    3665                 :     182815 :       if (dump_file && (dump_flags & TDF_DETAILS))
    3666                 :          0 :         fprintf (dump_file, "doing global processing\n");
    3667                 :     182815 :       dse_step3 ();
    3668                 :     182815 :       dse_step4 ();
    3669                 :     182815 :       dse_step5 ();
    3670                 :            :     }
    3671                 :            : 
    3672                 :    1373160 :   dse_step6 ();
    3673                 :    1373160 :   dse_step7 ();
    3674                 :            : 
    3675                 :    1373160 :   if (dump_file)
    3676                 :         54 :     fprintf (dump_file, "dse: local deletions = %d, global deletions = %d\n",
    3677                 :            :              locally_deleted, globally_deleted);
    3678                 :            : 
    3679                 :            :   /* DSE can eliminate potentially-trapping MEMs.
    3680                 :            :      Remove any EH edges associated with them.  */
    3681                 :    1363470 :   if ((locally_deleted || globally_deleted)
    3682                 :      35321 :       && cfun->can_throw_non_call_exceptions
    3683                 :    1403120 :       && purge_all_dead_edges ())
    3684                 :            :     {
    3685                 :          0 :       free_dominance_info (CDI_DOMINATORS);
    3686                 :          0 :       cleanup_cfg (0);
    3687                 :            :     }
    3688                 :            : 
    3689                 :    1373160 :   return 0;
    3690                 :            : }
    3691                 :            : 
    3692                 :            : namespace {
    3693                 :            : 
    3694                 :            : const pass_data pass_data_rtl_dse1 =
    3695                 :            : {
    3696                 :            :   RTL_PASS, /* type */
    3697                 :            :   "dse1", /* name */
    3698                 :            :   OPTGROUP_NONE, /* optinfo_flags */
    3699                 :            :   TV_DSE1, /* tv_id */
    3700                 :            :   0, /* properties_required */
    3701                 :            :   0, /* properties_provided */
    3702                 :            :   0, /* properties_destroyed */
    3703                 :            :   0, /* todo_flags_start */
    3704                 :            :   TODO_df_finish, /* todo_flags_finish */
    3705                 :            : };
    3706                 :            : 
    3707                 :            : class pass_rtl_dse1 : public rtl_opt_pass
    3708                 :            : {
    3709                 :            : public:
    3710                 :     200773 :   pass_rtl_dse1 (gcc::context *ctxt)
    3711                 :     401546 :     : rtl_opt_pass (pass_data_rtl_dse1, ctxt)
    3712                 :            :   {}
    3713                 :            : 
    3714                 :            :   /* opt_pass methods: */
    3715                 :     944101 :   virtual bool gate (function *)
    3716                 :            :     {
    3717                 :     944101 :       return optimize > 0 && flag_dse && dbg_cnt (dse1);
    3718                 :            :     }
    3719                 :            : 
    3720                 :     686579 :   virtual unsigned int execute (function *) { return rest_of_handle_dse (); }
    3721                 :            : 
    3722                 :            : }; // class pass_rtl_dse1
    3723                 :            : 
    3724                 :            : } // anon namespace
    3725                 :            : 
    3726                 :            : rtl_opt_pass *
    3727                 :     200773 : make_pass_rtl_dse1 (gcc::context *ctxt)
    3728                 :            : {
    3729                 :     200773 :   return new pass_rtl_dse1 (ctxt);
    3730                 :            : }
    3731                 :            : 
    3732                 :            : namespace {
    3733                 :            : 
    3734                 :            : const pass_data pass_data_rtl_dse2 =
    3735                 :            : {
    3736                 :            :   RTL_PASS, /* type */
    3737                 :            :   "dse2", /* name */
    3738                 :            :   OPTGROUP_NONE, /* optinfo_flags */
    3739                 :            :   TV_DSE2, /* tv_id */
    3740                 :            :   0, /* properties_required */
    3741                 :            :   0, /* properties_provided */
    3742                 :            :   0, /* properties_destroyed */
    3743                 :            :   0, /* todo_flags_start */
    3744                 :            :   TODO_df_finish, /* todo_flags_finish */
    3745                 :            : };
    3746                 :            : 
    3747                 :            : class pass_rtl_dse2 : public rtl_opt_pass
    3748                 :            : {
    3749                 :            : public:
    3750                 :     200773 :   pass_rtl_dse2 (gcc::context *ctxt)
    3751                 :     401546 :     : rtl_opt_pass (pass_data_rtl_dse2, ctxt)
    3752                 :            :   {}
    3753                 :            : 
    3754                 :            :   /* opt_pass methods: */
    3755                 :     944101 :   virtual bool gate (function *)
    3756                 :            :     {
    3757                 :     944101 :       return optimize > 0 && flag_dse && dbg_cnt (dse2);
    3758                 :            :     }
    3759                 :            : 
    3760                 :     686579 :   virtual unsigned int execute (function *) { return rest_of_handle_dse (); }
    3761                 :            : 
    3762                 :            : }; // class pass_rtl_dse2
    3763                 :            : 
    3764                 :            : } // anon namespace
    3765                 :            : 
    3766                 :            : rtl_opt_pass *
    3767                 :     200773 : make_pass_rtl_dse2 (gcc::context *ctxt)
    3768                 :            : {
    3769                 :     200773 :   return new pass_rtl_dse2 (ctxt);
    3770                 :            : }

Generated by: LCOV version 1.0

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 --enable-host-shared. GCC test suite is run with the built compiler.